TL;DR
The Sequential Aggregation and Rematerialization (SAR) scheme enables distributed, full-batch training of Graph Neural Networks (GNNs) on massive graphs by sequentially reconstructing and freeing pieces of the computational graph during the backward pass. This approach achieves linear memory scaling per worker, allowing training on graphs with billions of edges—like the 111M-node ogbn-papers100M—without the noise and bias inherent in traditional sampling-based methods.
The Challenge of Large-Scale GNN Training
Training GNNs on large-scale graphs is notoriously difficult due to "neighbor explosion." In a GNN, a node's output depends on its neighbors, their neighbors, and so on. For deep networks on dense graphs, a single node's output can eventually depend on almost the entire graph.
Standard "full-batch" training (using the whole graph at once) quickly runs out of memory (OOM). To cope, researchers often use sampling-based methods (training on small subgraphs) or non-learnable message passing. However, sampling introduces noisy gradient estimates and can be complex to tune, while non-learnable methods limit the model's expressive power. Even standard "domain-parallel" distributed training fails because each worker still needs to store a massive portion of the computational graph to perform backpropagation.
The SAR Framework and Fused Attention Kernels
The authors introduce two primary innovations to overcome these memory bottlenecks:
1. Sequential Aggregation and Rematerialization (SAR)
Instead of building and storing the entire computational graph during the forward pass, SAR "rematerializes" it piece-by-piece during the backward pass.
- Forward Pass: Workers fetch remote node features, aggregate them incrementally, and then discard the remote data.
- Backward Pass: Workers re-fetch the necessary remote data to reconstruct a small piece of the computational graph, calculate gradients, and immediately free that memory.
This ensures that no worker ever holds more than a small, constant number of graph partitions in memory at once.
2. Fused Attention Kernels (FAK)
For Graph Attention Networks (GATs), calculating and storing attention coefficients for every edge is a massive memory sink. The authors developed custom kernels that calculate these coefficients "on the fly" during both forward and backward passes, further reducing the memory footprint and speeding up computation by reducing slow memory I/O.
Experimental Evaluation and Scalability
The authors evaluated SAR on some of the largest publicly available benchmarks from the Open Graph Benchmark (OGB), including ogbn-products (124M edges) and ogbn-papers100M (3.2B edges).
Key Insights
- Linear Memory Scaling: SAR's memory requirement per worker scales as $O(1/N)$, where $N$ is the number of workers. This means you can handle arbitrarily large graphs simply by adding more machines to the cluster.
- The "Free" Rematerialization: For many GNNs (like GraphSage), the gradients don't actually depend on the input features. In these cases, SAR provides massive memory savings with zero additional communication overhead during the backward pass.
- Efficiency: On the massive
ogbn-papers100Mdataset, SAR was nearly 4x more memory efficient than standard domain-parallel training when using 128 workers. In fact, standard methods suffered OOM errors on 32 machines where SAR succeeded.
Discussion and Future Directions
While SAR enables unprecedented scale for full-batch GNNs, it can become communication-bound at very high worker counts due to the need for data re-fetching in the backward pass. Future work could extend SAR to tasks like link prediction or graph property prediction. Despite requiring minor modifications to existing training code, SAR provides a robust path for training high-fidelity GNNs on the world's largest graphs without sacrificing accuracy for scalability.
Summary updated