# Accelerating Graph Sampling for Graph Machine Learning using GPUs

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

## Key facts

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

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

- [BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing](https://mlsanity.com/paper/2112.08541/) (2021)
- [PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm](https://mlsanity.com/paper/2203.00638/) (2022)
- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [Towards Training Billion Parameter Graph Neural Networks for Atomic Simulations](https://mlsanity.com/paper/2203.09697/) (2022)
- [MariusGNN: Resource-Efficient Out-of-Core Training of Graph Neural Networks](https://mlsanity.com/paper/2202.02365/) (2022)
- [The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey](https://mlsanity.com/paper/2305.13854/) (2023)
- [Scalable Graph Neural Network Training: The Case for Sampling](https://mlsanity.com/paper/2105.02315/) (2021)
- [Quiver: Supporting GPUs for Low-Latency, High-Throughput GNN Serving with Workload Awareness](https://mlsanity.com/paper/2305.10863/) (2023)
- [Graph Neural Network Training Systems: A Performance Comparison of Full-Graph and Mini-Batch](https://mlsanity.com/paper/2406.00552/) (2024)
- [GSplit: Scaling Graph Neural Network Training on Large Graphs via Split-Parallelism](https://mlsanity.com/paper/2303.13775/) (2023)
- [Distributed Matrix-Based Sampling for Graph Neural Network Training](https://mlsanity.com/paper/2311.02909/) (2023)
- [NeutronOrch: Rethinking Sample-based GNN Training under CPU-GPU Heterogeneous Environments](https://mlsanity.com/paper/2311.13225/) (2023)
- [GNNFlow: A Distributed Framework for Continuous Temporal GNN Learning on Dynamic Graphs](https://mlsanity.com/paper/2311.17410/) (2023)
- [FreshGNN: Reducing Memory Access via Stable Historical Embeddings for Graph Neural Network Training](https://mlsanity.com/paper/2301.07482/) (2023)
- [GraphScale: A Framework to Enable Machine Learning over Billion-node Graphs](https://mlsanity.com/paper/2407.15452/) (2024)
- [Characterizing the Efficiency of Graph Neural Network Frameworks with a Magnifying Glass](https://mlsanity.com/paper/2211.03021/) (2022)
- [FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale](https://mlsanity.com/paper/2409.14939/) (2024)
- [Bottleneck Analysis of Dynamic Graph Neural Network Inference on CPU and GPU](https://mlsanity.com/paper/2210.03900/) (2022)
- [Distributed Graph Embedding with Information-Oriented Random Walks](https://mlsanity.com/paper/2303.15702/) (2023)
- [TASER: Temporal Adaptive Sampling for Fast and Accurate Dynamic Graph Representation Learning](https://mlsanity.com/paper/2402.05396/) (2024)
- [Hardware/Software Co-Programmable Framework for Computational SSDs to Accelerate Deep Learning Service on Large-Scale Graphs](https://mlsanity.com/paper/2201.09189/) (2022)
- [Single-GPU GNN Systems: Traps and Pitfalls](https://mlsanity.com/paper/2402.03548/) (2024)
- [LSM-GNN: Large-scale Storage-based Multi-GPU GNN Training by Optimizing Data Transfer Scheme](https://mlsanity.com/paper/2407.15264/) (2024)
- [Scaling Graph Neural Networks for Particle Track Reconstruction](https://mlsanity.com/paper/2504.04670/) (2025)
- [Scalable Neural Network Training over Distributed Graphs](https://mlsanity.com/paper/2302.13053/) (2023)
- [Armada: Memory-Efficient Distributed Training of Large-Scale Graph Neural Networks](https://mlsanity.com/paper/2502.17846/) (2025)
- [Grappa: Gradient-Only Communication for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2602.01872/) (2026)
- [NOMAD: Generating Embeddings for Massive Distributed Graphs](https://mlsanity.com/paper/2604.09419/) (2026)
- [Directly Optimizing Mean Demographic Parity for Nonlinear Regression](https://mlsanity.com/paper/2607.05098/) (2026)

## Abstract (arXiv)

Representation learning algorithms automatically learn the features of data. Several representation learning algorithms for graph data, such as DeepWalk, node2vec, and GraphSAGE, sample the graph to produce mini-batches that are suitable for training a DNN. However, sampling time can be a significant fraction of training time, and existing systems do not efficiently parallelize sampling. Sampling is an embarrassingly parallel problem and may appear to lend itself to GPU acceleration, but the irregularity of graphs makes it hard to use GPU resources effectively. This paper presents NextDoor, a system designed to effectively perform graph sampling on GPUs. NextDoor employs a new approach to graph sampling that we call transit-parallelism, which allows load balancing and caching of edges. NextDoor provides end-users with a high-level abstraction for writing a variety of graph sampling algorithms. We implement several graph sampling applications, and show that NextDoor runs them orders of magnitude faster than existing systems.