Abstract
Message passing-based graph neural networks (GNNs) have achieved significant success in various real-world applications. However, training GNNs on large-scale graphs is hindered by the "neighbor explosion problem," where node dependencies increase exponentially with the number of layers. Subgraph-wise sampling methods address this by discarding messages outside mini-batches during backward passes, but this often leads to inaccurate gradient estimation and a lack of convergence guarantees. We propose Local Message Compensation (LMC), the first subgraph-wise sampling method with provable convergence. LMC retrieves discarded messages by reformulating backward passes as a message-passing process and applying efficient compensations in both forward and backward passes. Our theoretical analysis shows that LMC converges to first-order stationary points, while experiments on large-scale benchmarks demonstrate that LMC significantly outperforms state-of-the-art methods in training efficiency.
Introduction
Training Graph Neural Networks (GNNs) on massive datasets is a significant computational challenge. The standard GNN paradigm relies on message passing, where nodes update their features by aggregating information from their neighbors. While effective, this leads to the neighbor explosion problem: in a multi-layer GNN, a single node's update depends on an exponentially growing number of neighbors across the graph. On large-scale graphs, a single mini-batch can quickly require loading nearly the entire graph into GPU memory, making standard training infeasible.
To mitigate this, researchers developed subgraph-wise sampling techniques (such as Cluster-GCN or GraphSAINT). These methods restrict training to a small sampled subgraph, ignoring connections that lead outside the mini-batch. While this approach is memory-efficient, it introduces biased gradients. By discarding "messages" from outside the sampled subgraph, the model's learning trajectory becomes imprecise. Until now, these methods lacked a rigorous mathematical proof of convergence, limiting their reliability in critical applications.
Local Message Compensation (LMC)
LMC addresses the gradient bias of subgraph sampling by introducing a novel compensation mechanism. The core innovation lies in treating the backward pass as a message-passing process, allowing the model to "recover" lost information without the full computational cost of the entire graph.
1. Backward Pass as Message Passing
The authors reformulate the standard backpropagation chain rule into a message-passing formulation. This insight allows the gradient computation to be treated with the same logic as node feature updates, making it possible to apply similar sampling and compensation strategies to both passes.
2. The Compensation Mechanism
Instead of simply ignoring nodes outside the sampled mini-batch, LMC estimates their contribution using a convex combination of two sources:
- Incomplete up-to-date values: Information from the immediate 1-hop neighbors of the mini-batch that are currently in memory.
- Historical values: Stored embeddings and auxiliary variables from previous training iterations.
By focusing on the interactions between mini-batch nodes and their immediate 1-hop neighbors—and filling in the gaps with historical data—LMC computes highly accurate gradients. This "one-shot" sampling approach keeps computational complexity linear relative to the number of layers, avoiding the exponential growth of traditional methods.
Theoretical Convergence
The most significant contribution of LMC is the first convergence proof for subgraph-wise sampling. The authors demonstrate that by using their compensation mechanism, LMC converges to first-order stationary points. This elevates subgraph sampling from a heuristic approach to a mathematically sound optimization strategy. LMC explicitly decomposes gradient error into "bias from discarded messages" and "variance from sampling," using compensation to shrink the bias toward zero.
Experimental Results
The authors evaluated LMC on several large-scale benchmark datasets, including REDDIT, PPI (Protein-Protein Interaction), FLICKR, and ogbn-arxiv.
- Efficiency: LMC demonstrates superior speed compared to state-of-the-art methods like GNNAutoScale (GAS). On the REDDIT dataset, LMC achieved a 2x speedup in reaching full-batch accuracy levels.
- Robustness to Batch Size: Unlike previous methods that fail when batch sizes are small, LMC remains stable even with a batch size of 1. This is because the compensation mechanism effectively manages the information loss that usually cripples small-batch subgraph training.
- Accuracy: Across all major datasets, LMC matches or slightly exceeds the prediction accuracy of full-batch training, proving that the method does not sacrifice model quality for training speed.
Discussion and Limitations
While LMC provides a robust framework for GNN training, it is not without trade-offs. Like other methods relying on historical values, LMC faces the staleness problem, where historical data may not perfectly represent the current model weights if they are several iterations old. Additionally, storing historical embeddings requires significant storage overhead (system RAM or disk), which must be managed for truly massive graphs.
In conclusion, LMC bridges the gap between the practical efficiency of subgraph sampling and the theoretical rigor of full-batch training. By providing the first provable convergence guarantee in this domain, LMC offers a reliable and high-performance solution for scaling GNNs to real-world, large-scale graph data.
Summary updated