Sparse graph Strucutre
The need of graph structure
Graph convolution can be classified into spectral-based graph convolution and spatial-based graph convolution. Spectral-based graph convolution relys on the algebaric operations, including +
, -
, *
, which are applied to features with graph structure. Spatial-based graph convolution relys on the indexing operations, since spatial-based graph convolution always indexes the neighbors of vertex. A graph structure can be use under two view point of a part of algebaric operations or an indexing structure.
Message-passing neural network requires to access neighbor information for each vertex. Messages are passed from a vertex's neighbors to itself. A efficient indexing data structure is required to access incident edges or neighbor vertices from a specific vertex.
SparseGraph
SparseGraph is implemented with sparse matrix. It is built on top of built-in sparse matrix, SparseMatrixCSC
. SparseMatrixCSC
can be used as a regular matrix and performs algebaric operations with matrix or vectors.
To benefit message-passing scheme, making a graph structure as an indexing structure is important. A well-designed indexing structure is made to leverage the sparse format of SparseMatrixCSC
, which is in CSC format. CSC format stores sparse matrix in a highly compressed manner. Comparing to traditional COO format, CSC format compresses the column indices into column pointers. All values are stored in single vector. If we want to index the sparse matrix A
, the row indices can be fetched by rowvals[colptr[j]:(colptr[j+1]-1)]
and the non-zero values can be indexed by nzvals[colptr[j]:(colptr[j+1]-1)]
. The edge indices are designed in the same manner edges[colptr[j]:(colptr[j+1]-1)]
. This way matches the need of indexing neighbors of vertex. This makes neighbor indices or values close together. It takes $O(1)$ to get negihbor indices, instead of searching neighbor in $O(N)$. Thus, SparseGraph
takes both advantages of both algebaric operations and indexing operations.
Create SparseGraph
SparseGraph
accepts adjacency matrix, adjacency list, and almost all graphs defined in JuliaGraphs.
julia> using GraphSignals, LightGraphs
julia> ug = SimpleGraph(4)
{4, 0} undirected simple Int64 graph
julia> add_edge!(ug, 1, 2); add_edge!(ug, 1, 3); add_edge!(ug, 1, 4);
julia> add_edge!(ug, 2, 3); add_edge!(ug, 3, 4);
julia> sg = SparseGraph(ug)
SparseGraph(#V=4, #E=5)
The indexed adjacency list is a list of list strucutre. The inner list consists of a series of tuples containing a vertex index and a edge index, respectively.
Operate SparseGraph
as graph
It supports basic graph APIs for querying graph information, including number of vertices nv
and number of edges ne
.
julia> is_directed(sg)
false
julia> nv(sg)
4
julia> ne(sg)
5
julia> eltype(sg)
Int64
julia> has_vertex(sg, 3)
true
julia> has_edge(sg, 1, 2)
true
We can compare two graph structure if they are equivalent or not.
julia> adjm = [0 1 1 1; 1 0 1 0; 1 1 0 1; 1 0 1 0]
4×4 Matrix{Int64}:
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
julia> sg2 = SparseGraph(adjm, false)
SparseGraph(#V=4, #E=5)
julia> sg == sg2
true
We can also iterate over edges.
julia> for (i, e) in edges(sg)
println("edge index: ", i, ", edge: ", e)
end
edge index: 1, edge: (2, 1)
edge index: 2, edge: (3, 1)
edge index: 3, edge: (3, 2)
edge index: 4, edge: (4, 1)
edge index: 5, edge: (4, 3)
Edge index is the index for each edge. It is used to index edge features.
Indexing operations
To get neighbors of a specified vertex, neighbors
is used by passing a SparseGraph
object and a vertex index. A vector of neighbor vertex index is returned.
julia> neighbors(sg, 1)
3-element view(::Vector{Int64}, 1:3) with eltype Int64:
2
3
4
To get incident edges of a specified vertex, incident_edges
can be used and it will return edge indices.
julia> incident_edges(sg, 1)
3-element view(::Vector{Int64}, 1:3) with eltype Int64:
1
2
4
An edge index can be fetched by querying an edge, for example, edge (1, 2)
and edge (2, 1)
refers to the same edge with index 1
.
julia> edge_index(sg, 1, 2)
1
julia> edge_index(sg, 2, 1)
1
One can have the opportunity to index the underlying sparse matrix.
julia> sg[1, 2]
1
julia> sg[2, 1]
1
Aggregate over neighbors
In message-passing scheme, it is always to aggregate node features or edge feature from neighbors. For convention, edge_scatter
and neighbor_scatter
are used to apply aggregate operations over edge features or neighbor vertex features. The actual aggregation is supported by scatter
operations.
julia> nf = rand(10, 4);
julia> neighbor_scatter(+, nf, sg)
10×4 Matrix{Float64}:
1.54937 1.03974 1.72926 1.03974
1.38554 0.775991 1.34106 0.775991
1.13192 0.424888 1.34657 0.424888
2.23452 1.63226 2.436 1.63226
0.815662 0.718865 1.25237 0.718865
2.35763 1.42174 2.26442 1.42174
1.94051 1.44812 1.71694 1.44812
1.83641 1.89104 1.80857 1.89104
2.43027 1.92217 2.37003 1.92217
1.58177 1.16149 1.87467 1.16149
For example, neighbor_scatter
aggregates node features nf
via neighbors in graph sg
by +
operation.
julia> ef = rand(9, 5);
julia> edge_scatter(+, ef, sg)
9×4 Matrix{Float64}:
2.22577 0.967172 1.92781 1.92628
1.4842 1.20605 2.30014 0.849819
2.20728 1.01527 0.899094 1.35062
1.09119 0.589925 1.62597 1.51175
1.42288 1.63764 1.23445 0.693258
1.57561 0.926591 1.72599 0.690108
1.68402 0.544808 1.58687 1.70676
1.10908 1.0898 1.05256 0.508157
2.33764 1.26419 1.87927 1.11151
Or, edge_scatter
aggregates edge features ef
via incident edges in graph sg
by +
operation.
SparseGraph
APIs
Missing docstring for SparseGraph
. Check Documenter's build log for details.
Missing docstring for GraphSignals.neighbors
. Check Documenter's build log for details.
Missing docstring for incident_edges
. Check Documenter's build log for details.
Missing docstring for neighbor_scatter
. Check Documenter's build log for details.
Missing docstring for edge_scatter
. Check Documenter's build log for details.
Internals
In the design of SparseGraph
, it resolve the problem of indexing edge features. For a graph, edge is represented in (i, j)
and edge features are considered as a matrix ef
with edge number in its column. The problem is to unifiedly fetch corresponding edge feature ef[:, k]
for edge (i, j)
over directed and undirected graph. To resolve this issue, edge index is set to be the unique index for each edge. Further, aggregate_index
is designed to generate indices for aggregating from neighbor nodes or incident edges. Conclusively, it provides the core operations needed in message-passing scheme.