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

Zhihao Shi, Xize Liang, Jie Wang

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

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