# Bandit Samplers for Training Graph Neural Networks

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

## Key facts

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

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

- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs](https://mlsanity.com/paper/2106.06150/) (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)
- [Do We Need Anisotropic Graph Neural Networks?](https://mlsanity.com/paper/2104.01481/) (2021)
- [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)
- [Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching](https://mlsanity.com/paper/2305.03152/) (2023)
- [Influence-Based Mini-Batching for Graph Neural Networks](https://mlsanity.com/paper/2212.09083/) (2022)
- [FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficiently](https://mlsanity.com/paper/2401.14702/) (2024)
- [IGLU: Efficient GCN Training via Lazy Updates](https://mlsanity.com/paper/2109.13995/) (2021)
- [GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks](https://mlsanity.com/paper/2310.03399/) (2023)
- [Graph Generative Model for Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2207.04396/) (2022)
- [Learning Stochastic Graph Neural Networks with Constrained Variance](https://mlsanity.com/paper/2201.12611/) (2022)
- [Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks](https://mlsanity.com/paper/2206.00583/) (2022)
- [DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training](https://mlsanity.com/paper/2405.05231/) (2024)
- [InferTurbo: A Scalable System for Boosting Full-graph Inference of Graph Neural Network over Huge Graphs](https://mlsanity.com/paper/2307.00228/) (2023)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (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)
- [PromptGCN: Bridging Subgraph Gaps in Lightweight GCNs](https://mlsanity.com/paper/2410.10089/) (2024)
- [Hierarchical Estimation for Effective and Efficient Sampling Graph Neural Network](https://mlsanity.com/paper/2211.09813/) (2022)
- [Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks](https://mlsanity.com/paper/2312.01342/) (2023)
- [Acceleration Algorithms in GNNs: A Survey](https://mlsanity.com/paper/2405.04114/) (2024)
- [BLISS: Bandit Layer Importance Sampling Strategy for Efficient Training of Graph Neural Networks](https://mlsanity.com/paper/2512.22388/) (2025)
- [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)

Several sampling algorithms with variance reduction have been proposed for accelerating the training of Graph Convolution Networks (GCNs). However, due to the intractable computation of optimal sampling distribution, these sampling algorithms are suboptimal for GCNs and are not applicable to more general graph neural networks (GNNs) where the message aggregator contains learned weights rather than fixed weights, such as Graph Attention Networks (GAT). The fundamental reason is that the embeddings of the neighbors or learned weights involved in the optimal sampling distribution are changing during the training and not known a priori, but only partially observed when sampled, thus making the derivation of an optimal variance reduced samplers non-trivial. In this paper, we formulate the optimization of the sampling variance as an adversary bandit problem, where the rewards are related to the node embeddings and learned weights, and can vary constantly. Thus a good sampler needs to acquire variance information about more neighbors (exploration) while at the same time optimizing the immediate sampling variance (exploit). We theoretically show that our algorithm asymptotically approaches the optimal variance within a factor of 3. We show the efficiency and effectiveness of our approach on multiple datasets.