# C-SAW: A Framework for Graph Sampling and Random Walk on GPUs

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

## Key facts

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

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

- [BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing](https://mlsanity.com/paper/2112.08541/) (2021)
- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [Scalable Graph Neural Network Training: The Case for Sampling](https://mlsanity.com/paper/2105.02315/) (2021)
- [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)
- [GNNFlow: A Distributed Framework for Continuous Temporal GNN Learning on Dynamic Graphs](https://mlsanity.com/paper/2311.17410/) (2023)
- [Tango: rethinking quantization for graph neural network training on GPUs](https://mlsanity.com/paper/2308.00890/) (2023)
- [Mining User-aware Multi-relations for Fake News Detection in Large Scale Online Social Networks](https://mlsanity.com/paper/2212.10778/) (2022)
- [FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale](https://mlsanity.com/paper/2409.14939/) (2024)
- [TASER: Temporal Adaptive Sampling for Fast and Accurate Dynamic Graph Representation Learning](https://mlsanity.com/paper/2402.05396/) (2024)
- [Towards Ideal Temporal Graph Neural Networks: Evaluations and Conclusions after 10,000 GPU Hours](https://mlsanity.com/paper/2412.20256/) (2024)
- [NOMAD: Generating Embeddings for Massive Distributed Graphs](https://mlsanity.com/paper/2604.09419/) (2026)

## Abstract (arXiv)

Many applications require to learn, mine, analyze and visualize large-scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Many applications have requirements to analyze, transform, visualize and learn large scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Recent literatures convey that graph sampling/random walk could be an efficient solution. In this paper, we propose, to the best of our knowledge, the first GPU-based framework for graph sampling/random walk. First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two optimizations for collision migration. Third, towards supporting graphs that exceed GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory sampling, such as workload-aware scheduling and batched multi-instance sampling. In its entirety, our framework constantly outperforms the state-of-the-art projects. First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two novel optimizations for collision migration. Third, towards supporting graphs that exceed the GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory and multi-GPU sampling, such as workload-aware scheduling and batched multi-instance sampling. Taken together, our framework constantly outperforms the state of the art projects in addition to the capability of supporting a wide range of sampling and random walk algorithms.