# A Biased Graph Neural Network Sampler with Near-Optimal Regret

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 40 references that are in the map.
- First posted on arXiv 1 Mar 2021.

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

- [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)
- [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)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [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)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [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)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [Heterogeneous Graph Neural Networks for Malicious Account Detection](https://mlsanity.com/paper/2002.12307/) (2020)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [Spam Review Detection with Graph Convolutional Networks](https://mlsanity.com/paper/1908.10679/) (2019)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)
- [Bandit Samplers for Training Graph Neural Networks](https://mlsanity.com/paper/2006.05806/) (2020)
- [Stochastic Optimization with Bandit Sampling](https://mlsanity.com/paper/1708.02544/) (2017)
- [Advancing GraphSAGE with A Data-Driven Node Sampling](https://mlsanity.com/paper/1904.12935/) (2019)

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

- [PLATON: Pruning Large Transformer Models with Upper Confidence Bound of Weight Importance](https://mlsanity.com/paper/2206.12562/) (2022)
- [On Generalized Degree Fairness in Graph Neural Networks](https://mlsanity.com/paper/2302.03881/) (2023)
- [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)
- [Layer-Neighbor Sampling -- Defusing Neighborhood Explosion in GNNs](https://mlsanity.com/paper/2210.13339/) (2022)
- [Not All Neighbors Are Worth Attending to: Graph Selective Attention Networks for Semi-supervised Learning](https://mlsanity.com/paper/2210.07715/) (2022)
- [Skew Class-balanced Re-weighting for Unbiased Scene Graph Generation](https://mlsanity.com/paper/2301.00351/) (2023)
- [DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training](https://mlsanity.com/paper/2405.05231/) (2024)
- [FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale](https://mlsanity.com/paper/2409.14939/) (2024)
- [Graph Belief Propagation Networks](https://mlsanity.com/paper/2106.03033/) (2021)
- [TASER: Temporal Adaptive Sampling for Fast and Accurate Dynamic Graph Representation Learning](https://mlsanity.com/paper/2402.05396/) (2024)
- [Bandit Sampling for Multiplex Networks](https://mlsanity.com/paper/2202.03621/) (2022)
- [Rethinking Efficiency and Redundancy in Training Large-scale Graphs](https://mlsanity.com/paper/2209.00800/) (2022)
- [Hardware Acceleration of Sampling Algorithms in Sample and Aggregate Graph Neural Networks](https://mlsanity.com/paper/2209.02916/) (2022)
- [Hierarchical Estimation for Effective and Efficient Sampling Graph Neural Network](https://mlsanity.com/paper/2211.09813/) (2022)
- [A Comparative Analysis of Bias Amplification in Graph Neural Network Approaches for Recommender Systems](https://mlsanity.com/paper/2301.07639/) (2023)
- [TypeBandit: Type-Level Context Allocation and Reweighting for Effective Attribute Completion in Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2604.27356/) (2026)

## Abstract (arXiv)

Graph neural networks (GNN) have recently emerged as a vehicle for applying deep network architectures to graph and relational data. However, given the increasing size of industrial datasets, in many practical situations the message passing computations required for sharing information across GNN layers are no longer scalable. Although various sampling methods have been introduced to approximate full-graph training within a tractable budget, there remain unresolved complications such as high variances and limited theoretical guarantees. To address these issues, we build upon existing work and treat GNN neighbor sampling as a multi-armed bandit problem but with a newly-designed reward function that introduces some degree of bias designed to reduce variance and avoid unstable, possibly-unbounded pay outs. And unlike prior bandit-GNN use cases, the resulting policy leads to near-optimal regret while accounting for the GNN training dynamics introduced by SGD. From a practical standpoint, this translates into lower variance estimates and competitive or superior test accuracy across several benchmarks.