# Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2020.

## Built on by (most cited first, 30 of 54)

- [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)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking](https://mlsanity.com/paper/2210.07494/) (2022)
- [PipeGCN: Efficient Full-Graph Training of Graph Convolutional Networks with Pipelined Feature Communication](https://mlsanity.com/paper/2203.10428/) (2022)
- [BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Sampling](https://mlsanity.com/paper/2203.10983/) (2022)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [GraphFM: Improving Large-Scale GNN Training via Feature Momentum](https://mlsanity.com/paper/2206.07161/) (2022)
- [Linear-Time Graph Neural Networks for Scalable Recommendations](https://mlsanity.com/paper/2402.13973/) (2024)
- [LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence](https://mlsanity.com/paper/2302.00924/) (2023)
- [Self-supervised Graph Neural Networks without explicit negative sampling](https://mlsanity.com/paper/2103.14958/) (2021)
- [Learn Locally, Correct Globally: A Distributed Algorithm for Training Graph Neural Networks](https://mlsanity.com/paper/2111.08202/) (2021)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Ginex: SSD-enabled Billion-scale Graph Neural Network Training on a Single Machine via Provably Optimal In-memory Caching](https://mlsanity.com/paper/2208.09151/) (2022)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [A Biased Graph Neural Network Sampler with Near-Optimal Regret](https://mlsanity.com/paper/2103.01089/) (2021)
- [LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation](https://mlsanity.com/paper/2302.01503/) (2023)
- [Topology-aware Embedding Memory for Continual Learning on Expanding Networks](https://mlsanity.com/paper/2401.13200/) (2024)
- [RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations](https://mlsanity.com/paper/2210.10737/) (2022)
- [MSPipe: Efficient Temporal GNN Training via Staleness-Aware Pipeline](https://mlsanity.com/paper/2402.15113/) (2024)
- [Scalable Graph Neural Network Training: The Case for Sampling](https://mlsanity.com/paper/2105.02315/) (2021)
- [Adaptive Message Quantization and Parallelization for Distributed Full-graph GNN Training](https://mlsanity.com/paper/2306.01381/) (2023)
- [Hypergraph Pre-training with Graph Neural Networks](https://mlsanity.com/paper/2105.10862/) (2021)
- [Self-supervised Graphs for Audio Representation Learning with Limited Labeled Data](https://mlsanity.com/paper/2202.00097/) (2022)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficiently](https://mlsanity.com/paper/2401.14702/) (2024)
- [Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks](https://mlsanity.com/paper/2101.07706/) (2021)
- [IGLU: Efficient GCN Training via Lazy Updates](https://mlsanity.com/paper/2109.13995/) (2021)

## Abstract (arXiv)

Sampling methods (e.g., node-wise, layer-wise, or subgraph) has become an indispensable strategy to speed up training large-scale Graph Neural Networks (GNNs). However, existing sampling methods are mostly based on the graph structural information and ignore the dynamicity of optimization, which leads to high variance in estimating the stochastic gradients. The high variance issue can be very pronounced in extremely large graphs, where it results in slow convergence and poor generalization. In this paper, we theoretically analyze the variance of sampling methods and show that, due to the composite structure of empirical risk, the variance of any sampling method can be decomposed into textitembedding approximation variance in the forward stage and textitstochastic gradient variance in the backward stage that necessities mitigating both types of variance to obtain faster convergence rate. We propose a decoupled variance reduction strategy that employs (approximate) gradient information to adaptively sample nodes with minimal variance, and explicitly reduces the variance introduced by embedding approximation. We show theoretically and empirically that the proposed method, even with smaller mini-batch sizes, enjoys a faster convergence rate and entails a better generalization compared to the existing methods.