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

arXiv: https://arxiv.org/abs/2302.00924 · HTML: https://mlsanity.com/paper/2302.00924/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 35 references that are in the map.
- First posted on arXiv 2 Feb 2023.

## Builds on (most cited first, 23 of 23)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Implicit Graph Neural Networks](https://mlsanity.com/paper/2009.06211/) (2020)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [GraphFM: Improving Large-Scale GNN Training via Feature Momentum](https://mlsanity.com/paper/2206.07161/) (2022)
- [D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems](https://mlsanity.com/paper/1911.12665/) (2019)

## Built on by (most cited first, 26 of 26)

- [VQGraph: Rethinking Graph Representation Space for Bridging GNNs and MLPs](https://mlsanity.com/paper/2308.02117/) (2023)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Label Deconvolution for Node Representation Learning on Large-scale Attributed Graphs against Learning Bias](https://mlsanity.com/paper/2309.14907/) (2023)
- [GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks](https://mlsanity.com/paper/2310.03399/) (2023)
- [Mixture of Weak & Strong Experts on Graphs](https://mlsanity.com/paper/2311.05185/) (2023)
- [A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design](https://mlsanity.com/paper/2309.03208/) (2023)
- [Multi-Modal CLIP-Informed Protein Editing](https://mlsanity.com/paper/2407.19296/) (2024)
- [Fast and Distributed Equivariant Graph Neural Networks by Virtual Node Learning](https://mlsanity.com/paper/2506.19482/) (2025)
- [Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report](https://mlsanity.com/paper/2501.04570/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Accurate and Scalable Graph Neural Networks via Message Invariance](https://mlsanity.com/paper/2502.19693/) (2025)
- [A Local Graph Limits Perspective on Sampling-Based GNNs](https://mlsanity.com/paper/2310.10953/) (2023)
- [GraNNDis: Efficient Unified Distributed Training Framework for Deep GNNs on Large Clusters](https://mlsanity.com/paper/2311.06837/) (2023)
- [Scalable Expressiveness through Preprocessed Graph Perturbations](https://mlsanity.com/paper/2406.11714/) (2024)
- [Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks](https://mlsanity.com/paper/2410.05416/) (2024)
- [FALCON: Feature-Label Constrained Graph Net Collapse for Memory Efficient GNNs](https://mlsanity.com/paper/2312.16542/) (2023)
- [PromptGCN: Bridging Subgraph Gaps in Lightweight GCNs](https://mlsanity.com/paper/2410.10089/) (2024)
- [Asymmetric Learning for Graph Neural Network based Link Prediction](https://mlsanity.com/paper/2303.00170/) (2023)
- [Provably Convergent Subgraph-wise Sampling for Fast GNN Training](https://mlsanity.com/paper/2303.11081/) (2023)
- [Fast and Effective GNN Training through Sequences of Random Path Graphs](https://mlsanity.com/paper/2306.04828/) (2023)
- [On the Equivalence of Graph Convolution and Mixup](https://mlsanity.com/paper/2310.00183/) (2023)
- [Cooperative Minibatching in Graph Neural Networks](https://mlsanity.com/paper/2310.12403/) (2023)
- [Acceleration Algorithms in GNNs: A Survey](https://mlsanity.com/paper/2405.04114/) (2024)
- [Using Subgraph GNNs for Node Classification:an Overlooked Potential Approach](https://mlsanity.com/paper/2503.06614/) (2025)
- [VISAGNN: Versatile Staleness-Aware Efficient Training on Large-Scale Graphs](https://mlsanity.com/paper/2511.12434/) (2025)
- [Bridging Global Intent with Local Details: A Hierarchical Representation Approach for Semantic Validation in Text-to-SQL](https://mlsanity.com/paper/2512.22744/) (2025)

## Abstract (arXiv)

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.