# Hierarchical graph sampling based minibatch learning with chain preservation and variance reduction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 43 references that are in the map.
- First posted on arXiv 2 Mar 2025.

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

- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [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)
- [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)
- [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)
- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [A Survey on Deep Active Learning: Recent Advances and New Frontiers](https://mlsanity.com/paper/2405.00334/) (2024)
- [BNS-GCN: Efficient Full-Graph Training of Graph Convolutional Networks with Partition-Parallelism and Random Boundary Node Sampling](https://mlsanity.com/paper/2203.10983/) (2022)
- [Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network](https://mlsanity.com/paper/2002.07206/) (2020)
- [Scalable Graph Neural Network Training: The Case for Sampling](https://mlsanity.com/paper/2105.02315/) (2021)
- [GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks](https://mlsanity.com/paper/2310.03399/) (2023)
- [AGS-GNN: Attribute-guided Sampling for Graph Neural Networks](https://mlsanity.com/paper/2405.15218/) (2024)
- [Exploring ordered patterns in the adjacency matrix for improving machine learning on complex networks](https://mlsanity.com/paper/2301.08364/) (2023)
- [Core-periphery structure requires something else in the network](https://mlsanity.com/paper/1710.07076/) (2017)
- [Sampling unknown large networks restricted by low sampling rates](https://mlsanity.com/paper/2308.14279/) (2023)
- [Weighted Jump in Random Walk Graph Sampling](https://mlsanity.com/paper/2209.12767/) (2022)
- [Generative Models and Learning Algorithms for Core-Periphery Structured Graphs](https://mlsanity.com/paper/2210.01489/) (2022)

## Abstract (arXiv)

Graph sampling-based Graph Convolutional Networks (GCNs) decouple sampling from forward and backward propagation during minibatch training, enhancing scalability with respect to layer depth and graph size. We propose HIS_GCNs, a hierarchical importance sampling-based learning method. By constructing minibatches using sampled subgraphs, HIS_GCNs focuses on the importance of both the core and periphery in a scale-free training graph. Specifically, it preserves the centrum of the core in most minibatches, which maintains connectivity between periphery nodes, and samples periphery edges without core node interference, which allows longer chains composed entirely of low-degree nodes remain within the same minibatch. HIS_GCNs can maximize the discrete Ricci curvature (i.e., Ollivier-Ricci curvatures) of the edges in a subgraph, enabling preservation of important chains for information propagation. This approach can achieve a low node embedding variance and a high convergence speed. Diverse experiments on Graph Neural Networks (GNNs) with node classification tasks confirmed the superior performance of HIS_GCNs in terms of both accuracy and training time. Open-source code (https://github.com/HuQiaCHN/HIS-GCN).