# Influence-Based Mini-Batching for Graph Neural Networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 18 Dec 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [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)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Reliable Graph Neural Networks via Robust Aggregation](https://mlsanity.com/paper/2010.15651/) (2020)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [Bandit Samplers for Training Graph Neural Networks](https://mlsanity.com/paper/2006.05806/) (2020)

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

- [Towards Quantifying Long-Range Interactions in Graph Machine Learning: a Large Graph Dataset and a Measurement](https://mlsanity.com/paper/2503.09008/) (2025)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [Mixture of Weak & Strong Experts on Graphs](https://mlsanity.com/paper/2311.05185/) (2023)
- [Task-Oriented GNNs Training on Large Knowledge Graphs for Accurate and Efficient Modeling](https://mlsanity.com/paper/2403.05752/) (2024)
- [On the Initialization of Graph Neural Networks](https://mlsanity.com/paper/2312.02622/) (2023)
- [Accurate and Scalable Graph Neural Networks via Message Invariance](https://mlsanity.com/paper/2502.19693/) (2025)
- [BatchGNN: Efficient CPU-Based Distributed GNN Training on Very Large Graphs](https://mlsanity.com/paper/2306.13814/) (2023)
- [A Local Graph Limits Perspective on Sampling-Based GNNs](https://mlsanity.com/paper/2310.10953/) (2023)
- [MuseGNN: Forming Scalable, Convergent GNN Layers that Minimize a Sampling-Based Energy](https://mlsanity.com/paper/2310.12457/) (2023)
- [BANGS: Game-Theoretic Node Selection for Graph Self-Training](https://mlsanity.com/paper/2410.09348/) (2024)
- [An LLM-Guided Query-Aware Inference System for GNN Models on Large Knowledge Graphs](https://mlsanity.com/paper/2603.04545/) (2026)
- [Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants](https://mlsanity.com/paper/2409.06998/) (2024)
- [Visiting Distant Neighbors in Graph Convolutional Networks](https://mlsanity.com/paper/2301.10960/) (2023)
- [Minibatch Selection for Language Models via Partition Matroid Constrained Gradient Matching](https://mlsanity.com/paper/2606.07954/) (2026)
- [CoRe-GNN: Multilevel Message passing on Coarsened graphs](https://mlsanity.com/paper/2608.02128/) (2026)

## Abstract (arXiv)

Using graph neural networks for large graphs is challenging since there is no clear way of constructing mini-batches. To solve this, previous methods have relied on sampling or graph clustering. While these approaches often lead to good training convergence, they introduce significant overhead due to expensive random data accesses and perform poorly during inference. In this work we instead focus on model behavior during inference. We theoretically model batch construction via maximizing the influence score of nodes on the outputs. This formulation leads to optimal approximation of the output when we do not have knowledge of the trained model. We call the resulting method influence-based mini-batching (IBMB). IBMB accelerates inference by up to 130x compared to previous methods that reach similar accuracy. Remarkably, with adaptive optimization and the right training schedule IBMB can also substantially accelerate training, thanks to precomputed batches and consecutive memory accesses. This results in up to 18x faster training per epoch and up to 17x faster convergence per runtime compared to previous methods.