# Implicit Regularization of Mini-Batch Training in Graph Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 31 references that are in the map.
- First posted on arXiv 21 May 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [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)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [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)
- [Stochastic Gradient Descent as Approximate Bayesian Inference](https://mlsanity.com/paper/1704.04289/) (2017)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [On the Origin of Implicit Regularization in Stochastic Gradient Descent](https://mlsanity.com/paper/2101.12176/) (2021)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Implicit Gradient Regularization](https://mlsanity.com/paper/2009.11162/) (2020)
- [A Bayesian Perspective on Generalization and Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06451/) (2017)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks](https://mlsanity.com/paper/1710.11029/) (2017)
- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [PyG 2.0: Scalable Learning on Real World Graphs](https://mlsanity.com/paper/2507.16991/) (2025)
- [On the Implicit Bias of Adam](https://mlsanity.com/paper/2309.00079/) (2023)
- [Implicit regularization in Heavy-ball momentum accelerated stochastic gradient descent](https://mlsanity.com/paper/2302.00849/) (2023)
- [GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Data](https://mlsanity.com/paper/2409.14500/) (2024)
- [Layer-Neighbor Sampling -- Defusing Neighborhood Explosion in GNNs](https://mlsanity.com/paper/2210.13339/) (2022)

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

- [Batch Before You Lift: Scalable Topological Deep Learning on Large Graphs](https://mlsanity.com/paper/2610.12247/) (2026)

## Abstract (arXiv)

Mini-batch training of Graph Neural Networks (GNNs) is fundamentally different from training on i.i.d. data: sampling a subgraph alters the topology and introduces boundary effects, leading prior work to develop structure-aware samplers that preserve local connectivity and reduce embedding variance. Surprisingly, we demonstrate that the simplest possible scheme, Random Node Sampling (RNS), training on the induced subgraph of uniformly sampled nodes, matches or outperforms full-graph training on 8 of 10 datasets at a fraction of the wall-clock time and memory. To explain this, we apply backward error analysis to graph mini-batch Stochastic Gradient Descent (SGD) and show that it implicitly minimizes the sampled loss plus a regularizer proportional to the mini-batch gradient variance, a quantity directly shaped by the sampler. Although RNS discards local structure, it produces mini-batches whose expected loss is closer to the full-graph loss, and whose per-batch gradients have lower variance, yielding a better implicit objective. Our analysis reframes the choice of graph sampler as a form of implicit regularization, and identifies RNS as a strong, theoretically grounded method for scalable GNN training.