# Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 37 references that are in the map.
- First posted on arXiv 1 Jun 2022.

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

- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [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)
- [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)
- [Traffic Graph Convolutional Recurrent Neural Network: A Deep Learning Framework for Network-Scale Traffic Learning and Forecasting](https://mlsanity.com/paper/1802.07007/) (2018)
- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing](https://mlsanity.com/paper/1807.02322/) (2018)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [Estimating Gradients for Discrete Random Variables by Sampling without Replacement](https://mlsanity.com/paper/2002.06043/) (2020)
- [Bandit Samplers for Training Graph Neural Networks](https://mlsanity.com/paper/2006.05806/) (2020)
- [Semi-supervised User Geolocation via Graph Convolutional Networks](https://mlsanity.com/paper/1804.08049/) (2018)
- [Rao-Blackwellized Stochastic Gradients for Discrete Distributions](https://mlsanity.com/paper/1810.04777/) (2018)
- [Robustness via Deep Low-Rank Representations](https://mlsanity.com/paper/1804.07090/) (2018)
- [Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation](https://mlsanity.com/paper/2103.04031/) (2021)

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

- [Layer-Neighbor Sampling -- Defusing Neighborhood Explosion in GNNs](https://mlsanity.com/paper/2210.13339/) (2022)
- [PromptGCN: Bridging Subgraph Gaps in Lightweight GCNs](https://mlsanity.com/paper/2410.10089/) (2024)
- [DAFOS: Dynamic Adaptive Fanout Optimization Sampler](https://mlsanity.com/paper/2507.08845/) (2025)
- [BLISS: Bandit Layer Importance Sampling Strategy for Efficient Training of Graph Neural Networks](https://mlsanity.com/paper/2512.22388/) (2025)
- [MQ-GNN: A Multi-Queue Pipelined Architecture for Scalable and Efficient GNN Training](https://mlsanity.com/paper/2601.04707/) (2026)

## Abstract (arXiv)

Multiple sampling-based methods have been developed for approximating and accelerating node embedding aggregation in graph convolutional networks (GCNs) training. Among them, a layer-wise approach recursively performs importance sampling to select neighbors jointly for existing nodes in each layer. This paper revisits the approach from a matrix approximation perspective, and identifies two issues in the existing layer-wise sampling methods: suboptimal sampling probabilities and estimation biases induced by sampling without replacement. To address these issues, we accordingly propose two remedies: a new principle for constructing sampling probabilities and an efficient debiasing algorithm. The improvements are demonstrated by extensive analyses of estimation variance and experiments on common benchmarks. Code and algorithm implementations are publicly available at https://github.com/ychen-stat-ml/GCN-layer-wise-sampling .