Sequential Aggregation and Rematerialization: Distributed Full-batch Training of Graph Neural Networks on Large Graphs

Hesham Mostafa

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 researchers to train on graphs with billions of edges—like the 111M-node ogbn-papers100M—without the noise and bias inherent in traditional sampling-based methods.

What Problem Does This Paper Address?

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.

Methods

The authors introduce two primary innovations:

  1. SAR (Sequential Aggregation and Rematerialization): Instead of building and storing the entire computational graph during the forward pass, SAR "rematerializes" it piece-by-piece during the backward pass.
  2. Forward Pass: Workers fetch remote node features, aggregate them incrementally, and then discard the remote data.
  3. 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.
  4. This ensures that no worker ever holds more than a small, constant number of graph partitions in memory at once.
Comparison of vanilla domain-parallel training (a) vs. SAR (b). SAR avoids storing the full computational graph by rematerializing it during the backward pass.
  1. 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.

Datasets

The authors evaluated SAR on some of the largest publicly available benchmarks from the Open Graph Benchmark (OGB):

  • ogbn-products: 2.5 million nodes, 124 million edges.
  • ogbn-papers100M: 111 million nodes, 3.2 billion edges.
  • ogbn-mag: A heterogeneous graph with 1.9 million nodes and 21 million edges (used to demonstrate SAR's generality).

Key Insights and Ideas

  • Linear Memory Scaling: The most significant "aha" moment is that 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.
  • Synergy with Fused Kernels: While re-calculating attention coefficients in the backward pass sounds slow, it actually synergizes perfectly with SAR because the data has to be re-fetched anyway. The reduced memory pressure often makes the "slower" re-calculation faster than standard implementations that struggle with memory bandwidth.

Key Results

  • Memory Efficiency: On the massive ogbn-papers100M dataset, 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.
  • Speed: For GraphSage, SAR is as fast as or slightly faster than standard distributed training. For GATs, the FAK optimization allows SAR to match the speed of standard methods while using only a fraction of the memory.
Peak memory consumption for FAK vs. standard DGL. FAK significantly reduces memory usage as the number of attention heads increases.
  • Scalability: SAR enabled the largest full-batch GNN training reported to date, maintaining competitive accuracy (e.g., 80.1% on ogbn-products) without the downsides of sampling.
Scaling results on ogbn-papers100M. SAR (red) maintains much lower peak memory than vanilla DP (blue), which OOMs at 32 machines for GAT.

Limitations and Future Work

  • Communication Bottleneck: For models like GAT that require re-fetching data in the backward pass, the system can become "communication-bound" as the number of workers increases. At very high worker counts (e.g., 128), the time spent moving data across the network can outweigh the computational gains.
  • Scope: The current work focuses primarily on node classification. The authors suggest that extending SAR to other tasks like link prediction or graph property prediction is a promising future direction.
  • Implementation: While built on top of popular libraries like DGL and PyTorch, using SAR currently requires minor modifications to existing training code (e.g., how data is loaded and how gradients are synchronized).

Summary updated

BibTeX
@inproceedings{mostafa2022sequential,
  author = {Hesham Mostafa},
  title = {{Sequential Aggregation and Rematerialization: Distributed Full-batch Training of Graph Neural Networks on Large Graphs}},
  booktitle = {MLSys},
  year = {2022},
}
Figure