Space complexity describes how an algorithm’s memory requirements grow as its input grows. For graph neural networks, it helps determine whether available hardware can hold the graph, node features, intermediate values, and other algorithm data. section 7.2.1
Use space complexity when choosing algorithms for graphs of different sizes:
- Small graphs, with hundreds to a few thousand nodes and edges, can usually run on standard hardware. section 7.2.1
- Medium graphs, with tens of thousands of nodes and edges, may require more sophisticated algorithms or GPUs. section 7.2.1
- Large graphs, ranging from hundreds of thousands to billions of nodes and edges, often require distributed computing and specialized scalable algorithms. section 7.2.1
- High space complexity can limit dataset size, even when an algorithm’s predictive performance is suitable. section 7.2.1 section 7.6
Express space complexity with Big O notation, which describes how memory usage grows as input size changes. Compare the published complexity of a GNN algorithm with the graph size, available memory, and intended workflow. A standalone comparison can be difficult because GNNs combine diverse operations such as matrix multiplications. section 7.6.1
GCN versus GraphSAGE
A GCN is listed with space complexity O(Lnd + Ld²) and poor memory characteristics because it stores the entire adjacency matrix and node features. GraphSAGE is listed with O(bk^L) space complexity and better memory characteristics through neighborhood sampling and mini-batching, although repeated sampled nodes can introduce redundant computation. section 7.6.1
Table 7.3 Factors on the scalability of two graph algorithms: GCN and GraphSAGE.
|
Algorithm
|
Time Complexity
|
Space Complexity
|
Memory/Epoch Time/Convergence Speed
|
Notes
|
|---|---|---|---|---|
|
GCN
|
O(
Lnd²)
|
O(
Lnd +
Ld²)
|
Memory: Bad
Epoch time: Good
Convergence speed: Bad
|
Pros:
Spectral convolution: Efficient and suitable for large-scale graphs
Versatility: Applicable to various graph-related problems
Node feature learning: Rich feature learning that captures the topological structure of the graph
Con:
High memory and time complexity due to the need to store the entire adjacency matrix and node features
|
|
GraphSAGE
|
O(
Lbd²
k
L)
|
O(
bk
L)
|
Memory: Good
Epoch time: Bad
Convergence speed: Good
|
Pro:
Solves GCN’s scalability problem by using neighborhood sampling and mini-batching
Cons:
May introduce redundant computations when sampled nodes appear multiple times in the neighborhood
Keeps
O(
bk
L) nodes in memory for each batch, but the loss is computed only on b of them
|
|
n = Number of nodes in the graph
d = Dimensions of the node feature representation
L = Number of message-passing iterations or layers in the algorithm
k = Number of neighbors sampled per hop
b = Number of nodes in a mini-batch
|
||||
Compare GCN and GraphSAGE across time complexity, space complexity, memory, epoch time, convergence speed, and scalability trade-offs. section 7.6.1
