# Efficient GNN Training Through Structure-Aware Randomized Mini-Batching

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 45 references that are in the map.
- First posted on arXiv 25 Apr 2025.

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

- [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)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [HyGCN: A GCN Accelerator with Hybrid Architecture](https://mlsanity.com/paper/2001.02514/) (2020)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [GNNAdvisor: An Adaptive and Efficient Runtime System for GNN Acceleration on GPUs](https://mlsanity.com/paper/2006.06608/) (2020)
- [BGL: GPU-Efficient GNN Training by Optimizing Graph Data I/O and Preprocessing](https://mlsanity.com/paper/2112.08541/) (2021)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining](https://mlsanity.com/paper/2110.08450/) (2021)
- [IGB: Addressing The Gaps In Labeling, Features, Heterogeneity, and Size of Public Graph Datasets for Deep Learning Research](https://mlsanity.com/paper/2302.13522/) (2023)
- [Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs](https://mlsanity.com/paper/2106.06150/) (2021)
- [I-GCN: A Graph Convolutional Network Accelerator with Runtime Locality Enhancement through Islandization](https://mlsanity.com/paper/2203.03606/) (2022)
- [Layer-Neighbor Sampling -- Defusing Neighborhood Explosion in GNNs](https://mlsanity.com/paper/2210.13339/) (2022)
- [Domain-Specialized Cache Management for Graph Analytics](https://mlsanity.com/paper/2001.09783/) (2020)
- [Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study](https://mlsanity.com/paper/2409.11129/) (2024)

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

- [LHGEL: Large Heterogeneous Graph Ensemble Learning using Batch View Aggregation](https://mlsanity.com/paper/2510.03432/) (2025)
- [COMBA: Cross Batch Aggregation for Learning Large Graphs with Context Gating State Space Models](https://mlsanity.com/paper/2602.17893/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) enable learning on realworld graphs and mini-batch training has emerged as the de facto standard for training GNNs because it can scale to very large graphs and improve convergence. Current mini-batch construction policies largely ignore efficiency considerations of GNN training. Specifically, existing mini-batching techniques employ randomization schemes to improve accuracy and convergence. However, these randomization schemes are often agnostic to the structural properties of the graph (for eg. community structure), resulting in highly irregular memory access patterns during GNN training that make suboptimal use of on-chip GPU caches. On the other hand, while deterministic mini-batching based solely on graph structure delivers fast runtime performance, the lack of randomness compromises both the final model accuracy and training convergence speed. In this paper, we present Community-structure-aware Randomized Mini-batching (COMM-RAND), a novel methodology that bridges the gap between the above extremes. COMM-RAND allows practitioners to explore the space between pure randomness and pure graph structural awareness during mini-batch construction, leading to significantly more efficient GNN training with similar accuracy. We evaluated COMM-RAND across four popular graph learning benchmarks. COMM-RAND cuts down GNN training time by up to 2.76x (1.8x on average) while achieving an accuracy that is within 1.79% points (0.42% on average) compared to popular random mini-batching approaches.