# Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 45 references that are in the map.
- First posted on arXiv 4 May 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [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)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1911.07323/) (2019)
- [Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics](https://mlsanity.com/paper/1908.02591/) (2019)
- [DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs](https://mlsanity.com/paper/2010.05337/) (2020)
- [DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks](https://mlsanity.com/paper/2104.06700/) (2021)
- [GNNAdvisor: An Adaptive and Efficient Runtime System for GNN Acceleration on GPUs](https://mlsanity.com/paper/2006.06608/) (2020)
- [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)
- [Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining](https://mlsanity.com/paper/2110.08450/) (2021)
- [Distributed Hybrid CPU and GPU training for Graph Neural Networks on Billion-Scale Graphs](https://mlsanity.com/paper/2112.15345/) (2021)
- [Bandit Samplers for Training Graph Neural Networks](https://mlsanity.com/paper/2006.05806/) (2020)
- [Marius: Learning Massive Graph Embeddings on a Single Machine](https://mlsanity.com/paper/2101.08358/) (2021)
- [Large Graph Convolutional Network Training with GPU-Oriented Data Communication Architecture](https://mlsanity.com/paper/2103.03330/) (2021)
- [Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs](https://mlsanity.com/paper/2106.06150/) (2021)
- [Stochastic Gradient Descent with Biased but Consistent Gradient Estimators](https://mlsanity.com/paper/1807.11880/) (2018)

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

- [Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems](https://mlsanity.com/paper/2406.00809/) (2024)
- [Graph Neural Network Training Systems: A Performance Comparison of Full-Graph and Mini-Batch](https://mlsanity.com/paper/2406.00552/) (2024)
- [Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective](https://mlsanity.com/paper/2311.13279/) (2023)
- [The Shape of Money Laundering: Subgraph Representation Learning on the Blockchain with the Elliptic2 Dataset](https://mlsanity.com/paper/2404.19109/) (2024)
- [Distributed Matrix-Based Sampling for Graph Neural Network Training](https://mlsanity.com/paper/2311.02909/) (2023)
- [MassiveGNN: Efficient Training via Prefetching for Massively Connected Distributed Graphs](https://mlsanity.com/paper/2410.22697/) (2024)
- [GraNNDis: Efficient Unified Distributed Training Framework for Deep GNNs on Large Clusters](https://mlsanity.com/paper/2311.06837/) (2023)
- [Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNs](https://mlsanity.com/paper/2504.13266/) (2025)
- [Deal: Distributed End-to-End GNN Inference for All Nodes](https://mlsanity.com/paper/2503.02960/) (2025)
- [Rudder: Steering Prefetching in Distributed GNN Training using LLM Agents](https://mlsanity.com/paper/2602.23556/) (2026)
- [PerOS: Personalized Self-Adapting Operating Systems in the Cloud](https://mlsanity.com/paper/2404.00057/) (2024)
- [SDT-GNN: Streaming-based Distributed Training Framework for Graph Neural Networks](https://mlsanity.com/paper/2404.02300/) (2024)
- [Distributed Training of Large Graph Neural Networks with Variable Communication Rates](https://mlsanity.com/paper/2406.17611/) (2024)
- [Armada: Memory-Efficient Distributed Training of Large-Scale Graph Neural Networks](https://mlsanity.com/paper/2502.17846/) (2025)
- [Communication-free Sampling and 4D Hybrid Parallelism for Scalable Mini-batch GNN Training](https://mlsanity.com/paper/2604.02651/) (2026)
- [Taurus: Accelerating Out-of-Core Graph Neural Network Inference on Billion-Scale Graphs](https://mlsanity.com/paper/2607.17374/) (2026)

## Abstract (arXiv)

Training and inference with graph neural networks (GNNs) on massive graphs has been actively studied since the inception of GNNs, owing to the widespread use and success of GNNs in applications such as recommendation systems and financial forensics. This paper is concerned with minibatch training and inference with GNNs that employ node-wise sampling in distributed settings, where the necessary partitioning of vertex features across distributed storage causes feature communication to become a major bottleneck that hampers scalability. To significantly reduce the communication volume without compromising prediction accuracy, we propose a policy for caching data associated with frequently accessed vertices in remote partitions. The proposed policy is based on an analysis of vertex-wise inclusion probabilities (VIP) during multi-hop neighborhood sampling, which may expand the neighborhood far beyond the partition boundaries of the graph. VIP analysis not only enables the elimination of the communication bottleneck, but it also offers a means to organize in-memory data by prioritizing GPU storage for the most frequently accessed vertex features. We present SALIENT++, which extends the prior state-of-the-art SALIENT system to work with partitioned feature data and leverages the VIP-driven caching policy. SALIENT++ retains the local training efficiency and scalability of SALIENT by using a deep pipeline and drastically reducing communication volume while consuming only a fraction of the storage required by SALIENT. We provide experimental results with the Open Graph Benchmark data sets and demonstrate that training a 3-layer GraphSAGE model with SALIENT++ on 8 single-GPU machines is 7.1 faster than with SALIENT on 1 single-GPU machine, and 12.7 faster than with DistDGL on 8 single-GPU machines.