# Layer-Neighbor Sampling -- Defusing Neighborhood Explosion in GNNs

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 36 references that are in the map.
- First posted on arXiv 24 Oct 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [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)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [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)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [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)
- [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)
- [Distributed Hybrid CPU and GPU training for Graph Neural Networks on Billion-Scale Graphs](https://mlsanity.com/paper/2112.15345/) (2021)
- [Bandit Samplers for Training Graph Neural Networks](https://mlsanity.com/paper/2006.05806/) (2020)
- [Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs](https://mlsanity.com/paper/2106.06150/) (2021)
- [A Biased Graph Neural Network Sampler with Near-Optimal Regret](https://mlsanity.com/paper/2103.01089/) (2021)
- [Adaptive normalization for IPW estimation](https://mlsanity.com/paper/2106.07695/) (2021)
- [Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks](https://mlsanity.com/paper/2206.00583/) (2022)
- [On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction](https://mlsanity.com/paper/2103.02696/) (2021)

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

- [GraphPFN: A Prior-Data Fitted Graph Foundation Model](https://mlsanity.com/paper/2509.21489/) (2025)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [A Scalable and Effective Alternative to Graph Transformers](https://mlsanity.com/paper/2406.12059/) (2024)
- [MassiveGNN: Efficient Training via Prefetching for Massively Connected Distributed Graphs](https://mlsanity.com/paper/2410.22697/) (2024)
- [Accurate and Scalable Graph Neural Networks via Message Invariance](https://mlsanity.com/paper/2502.19693/) (2025)
- [LMAE4Eth: Generalizable and Robust Ethereum Fraud Detection by Exploring Transaction Semantics and Masked Graph Embedding](https://mlsanity.com/paper/2509.03939/) (2025)
- [A Local Graph Limits Perspective on Sampling-Based GNNs](https://mlsanity.com/paper/2310.10953/) (2023)
- [Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNs](https://mlsanity.com/paper/2504.13266/) (2025)
- [Efficient GNN Training Through Structure-Aware Randomized Mini-Batching](https://mlsanity.com/paper/2504.18082/) (2025)
- [PromptGCN: Bridging Subgraph Gaps in Lightweight GCNs](https://mlsanity.com/paper/2410.10089/) (2024)
- [Implicit Regularization of Mini-Batch Training in Graph Neural Networks](https://mlsanity.com/paper/2605.22480/) (2026)
- [Cooperative Minibatching in Graph Neural Networks](https://mlsanity.com/paper/2310.12403/) (2023)
- [Vision Paper: Designing Graph Neural Networks in Compliance with the European Artificial Intelligence Act](https://mlsanity.com/paper/2410.22120/) (2024)
- [Enhanced Soups for Graph Neural Networks](https://mlsanity.com/paper/2503.11612/) (2025)
- [ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphs](https://mlsanity.com/paper/2512.14908/) (2025)
- [BLISS: Bandit Layer Importance Sampling Strategy for Efficient Training of Graph Neural Networks](https://mlsanity.com/paper/2512.22388/) (2025)
- [Weighted Graph Clustering via Scale Contraction and Graph Structure Learning](https://mlsanity.com/paper/2601.17307/) (2026)
- [KidMesh: Computational Mesh Reconstruction for Pediatric Congenital Hydronephrosis Using Deep Neural Networks](https://mlsanity.com/paper/2602.13299/) (2026)
- [MetaSieve: Faster Relational Deep Learning through SQL-Based Metapath Selection](https://mlsanity.com/paper/2608.25903/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have received significant attention recently, but training them at a large scale remains a challenge. Mini-batch training coupled with sampling is used to alleviate this challenge. However, existing approaches either suffer from the neighborhood explosion phenomenon or have poor performance. To address these issues, we propose a new sampling algorithm called LAyer-neighBOR sampling (LABOR). It is designed to be a direct replacement for Neighbor Sampling (NS) with the same fanout hyperparameter while sampling up to 7 times fewer vertices, without sacrificing quality. By design, the variance of the estimator of each vertex matches NS from the point of view of a single vertex. Moreover, under the same vertex sampling budget constraints, LABOR converges faster than existing layer sampling approaches and can use up to 112 times larger batch sizes compared to NS.