LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence

Zhihao Shi, Xize Liang, Jie Wang

Training Graph Neural Networks (GNNs) on massive, real-world graphs is notoriously difficult. As you add layers to capture deeper relationships, each node's "receptive field" grows exponentially—a phenomenon known as neighbor explosion.

This paper introduces Local Message Compensation (LMC), a novel training strategy that tames this explosion while providing something rare in the world of subgraph sampling: a mathematical guarantee that the model will actually converge. By using "local message compensations"—a clever mix of historical data and partial updates—LMC corrects the gradient biases that usually plague fast GNN training. The result is up to a 2x speedup over state-of-the-art methods without sacrificing accuracy.

The Problem: Neighbor Explosion and Biased Gradients

The standard way to train GNNs is through Message Passing (MP). In each layer, a node gathers information from its neighbors. On a small graph, this is fine. On a graph with millions of nodes, computing the gradient for a single mini-batch becomes a memory nightmare. Because a node in layer $L$ depends on its neighbors in layer $L-1$, who in turn depend on their neighbors in $L-2$, the number of nodes you need to load into memory grows exponentially with the number of layers.

To solve this, researchers often use subgraph-wise sampling, where they only train on a small, self-contained chunk of the graph. While memory-efficient, it has a major flaw: it ignores "messages" from nodes outside the sampled chunk. This leads to inaccurate (biased) gradients, making training unstable and slow. Until LMC, no subgraph-wise method could theoretically guarantee it would reach a stationary point (converge) during training.

The Solution: Local Message Compensation (LMC)

LMC's core innovation is how it handles the "missing" information from outside the sampled mini-batch without triggering a neighbor explosion.

LMC Forward Pass: In-batch nodes (orange) receive standard messages from each other and historical messages (dashed) from 1-hop out-of-batch neighbors (blue).
  1. Backward Pass as Message Passing: The authors demonstrate that the backward pass (calculating gradients) can be formulated as a message-passing operation, just like the forward pass.
  2. Compensation Mechanism: Instead of ignoring the nodes outside the mini-batch, LMC "compensates" for them. It uses a convex combination of:
  3. Incomplete up-to-date messages: Data from the current mini-batch.
  4. Historical messages: Stored embeddings from previous training iterations.
  5. Efficiency: Crucially, these compensations only involve 1-hop neighbors of the mini-batch nodes. This keeps the computational cost linear while significantly improving the accuracy of the mini-batch gradient.

Unlike previous methods that might use historical values (like GAS), LMC applies this logic to both the forward and backward passes and introduces a specific weighting ($\beta_i$) to balance new and old information.

Key Insights and Results

The authors evaluated LMC on four large-scale benchmark datasets (PPI, REDDIT, FLICKR, and Ogbn-arxiv), ranging up to 232,000 nodes and 11.6 million edges.

  • Provable Convergence: This is the headline contribution. The authors provide a theoretical analysis showing that LMC converges to first-order stationary points. This elevates subgraph sampling from a "heuristic that seems to work" to a mathematically reliable algorithm.
  • Bias vs. Variance: While most sampling methods focus on reducing the variance of the gradient, LMC focuses on correcting the bias caused by discarded messages. The paper demonstrates that correcting this bias is the true key to faster convergence.
  • Robustness to Batch Size: LMC remains remarkably stable even with very small batch sizes (e.g., a single cluster). Other methods often become unstable or lose accuracy when the batch size is reduced to save memory.
  • Speed and Accuracy: LMC reached full-batch accuracy significantly faster than competitors. For example, on the REDDIT dataset using a GCN model, LMC reached the target accuracy in 381 seconds, compared to 790 seconds for GNNAutoScale (GAS) and 2,269 seconds for Feature Momentum (FM). It consistently matched or slightly exceeded the prediction performance of full-batch training.

Limitations and Future Work

While highly effective, LMC does have a few limitations:

  • Staleness: Like all methods relying on historical embeddings, LMC is susceptible to "staleness." If the model parameters change too quickly, the stored historical values become inaccurate. The convex combination mitigates this, but it remains a factor.
  • Memory Overhead: LMC needs to store historical node embeddings and auxiliary variables. While these can be stored in RAM or on a hard drive to save GPU memory, it introduces an I/O bottleneck that could limit performance on extremely large systems.
  • Hyperparameter Tuning: LMC introduces a new hyperparameter ($\beta_i$) for the compensation weight. Finding the optimal balance for a new, unseen dataset might require extra grid-search effort.

Summary updated

Abstract

The message passing-based graph neural networks (GNNs) have achieved great success in many real-world applications. However, training GNNs on large-scale graphs suffers from the well-known neighbor explosion problem, i.e., the exponentially increasing dependencies of nodes with the number of message passing layers. Subgraph-wise sampling methods---a promising class of mini-batch training techniques---discard messages outside the mini-batches in backward passes to avoid the neighbor explosion problem at the expense of gradient estimation accuracy. This poses significant challenges to their convergence analysis and convergence speeds, which seriously limits their reliable real-world applications. To address this challenge, we propose a novel subgraph-wise sampling method with a convergence guarantee, namely Local Message Compensation (LMC). To the best of our knowledge, LMC is the {\it first} subgraph-wise sampling method with provable convergence. The key idea of LMC is to retrieve the discarded messages in backward passes based on a message passing formulation of backward passes. By efficient and effective compensations for the discarded messages in both forward and backward passes, LMC computes accurate mini-batch gradients and thus accelerates convergence. We further show that LMC converges to first-order stationary points of GNNs. Experiments on large-scale benchmark tasks demonstrate that LMC significantly outperforms state-of-the-art subgraph-wise sampling methods in terms of efficiency.
BibTeX
@inproceedings{shi2023lmc,
  author = {Zhihao Shi and Xize Liang and Jie Wang},
  title = {{LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=5VBBA91N6n},
}
Figure