# RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 62 references that are in the map.
- First posted on arXiv 19 Oct 2022.

## Builds on (most cited first, 30 of 46)

- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [EIE: Efficient Inference Engine on Compressed Deep Neural Network](https://mlsanity.com/paper/1602.01528/) (2016)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [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)
- [Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks](https://mlsanity.com/paper/1907.04595/) (2019)
- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs](https://mlsanity.com/paper/2010.05337/) (2020)
- [GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training](https://mlsanity.com/paper/2009.03294/) (2020)
- [Monarch: Expressive Structured Matrices for Efficient and Accurate Training](https://mlsanity.com/paper/2204.00595/) (2022)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks](https://mlsanity.com/paper/2104.06700/) (2021)
- [A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking](https://mlsanity.com/paper/2210.07494/) (2022)
- [Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth](https://mlsanity.com/paper/2105.04550/) (2021)
- [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020)

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

- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)
- [LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora](https://mlsanity.com/paper/2510.10114/) (2025)
- [Compress, Then Prompt: Improving Accuracy-Efficiency Trade-off of LLM Inference with Transferable Prompt](https://mlsanity.com/paper/2305.11186/) (2023)
- [On Efficient Training of Large-Scale Deep Learning Models: A Literature Review](https://mlsanity.com/paper/2304.03589/) (2023)
- [MaxK-GNN: Extremely Fast GPU Kernel Design for Accelerating Graph Neural Networks Training](https://mlsanity.com/paper/2312.08656/) (2023)
- [Entity Alignment with Noisy Annotations from Large Language Models](https://mlsanity.com/paper/2405.16806/) (2024)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Neuro-Symbolic Entity Alignment via Variational Inference](https://mlsanity.com/paper/2410.04153/) (2024)
- [SORSA: Singular Values and Orthonormal Regularized Singular Vectors Adaptation of Large Language Models](https://mlsanity.com/paper/2409.00055/) (2024)
- [LoSemB: Logic-Guided Semantic Bridging for Inductive Tool Retrieval](https://mlsanity.com/paper/2508.07690/) (2025)
- [Boolean Satisfiability via Imitation Learning](https://mlsanity.com/paper/2509.25411/) (2025)
- [AdvSynGNN: Structure-Adaptive Graph Neural Nets via Adversarial Synthesis and Self-Corrective Propagation](https://mlsanity.com/paper/2602.17071/) (2026)

## Abstract (arXiv)

The training of graph neural networks (GNNs) is extremely time consuming because sparse graph-based operations are hard to be accelerated by hardware. Prior art explores trading off the computational precision to reduce the time complexity via sampling-based approximation. Based on the idea, previous works successfully accelerate the dense matrix based operations (e.g., convolution and linear) with negligible accuracy drop. However, unlike dense matrices, sparse matrices are stored in the irregular data format such that each row/column may have different number of non-zero entries. Thus, compared to the dense counterpart, approximating sparse operations has two unique challenges (1) we cannot directly control the efficiency of approximated sparse operation since the computation is only executed on non-zero entries; (2) sub-sampling sparse matrices is much more inefficient due to the irregular data format. To address the issues, our key idea is to control the accuracy-efficiency trade off by optimizing computation resource allocation layer-wisely and epoch-wisely. Specifically, for the first challenge, we customize the computation resource to different sparse operations, while limit the total used resource below a certain budget. For the second challenge, we cache previous sampled sparse matrices to reduce the epoch-wise sampling overhead. Finally, we propose a switching mechanisms to improve the generalization of GNNs trained with approximated operations. To this end, we propose Randomized Sparse Computation, which for the first time demonstrate the potential of training GNNs with approximated operations. In practice, rsc can achieve up to 11.6× speedup for a single sparse operation and a 1.6× end-to-end wall-clock time speedup with negligible accuracy drop.