# Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 145 of its 269 references that are in the map.
- First posted on arXiv 19 May 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Learning Mesh-Based Simulation with Graph Networks](https://mlsanity.com/paper/2010.03409/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)

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

- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey](https://mlsanity.com/paper/2305.13854/) (2023)
- [CIN++: Enhancing Topological Message Passing](https://mlsanity.com/paper/2306.03561/) (2023)
- [LL-GNN: Low Latency Graph Neural Networks on FPGAs for High Energy Physics](https://mlsanity.com/paper/2209.14065/) (2022)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers](https://mlsanity.com/paper/2311.18526/) (2023)
- [Multi-Flow Transmission in Wireless Interference Networks: A Convergent Graph Learning Approach](https://mlsanity.com/paper/2303.15544/) (2023)
- [Cached Operator Reordering: A Unified View for Fast GNN Training](https://mlsanity.com/paper/2308.12093/) (2023)
- [An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training](https://mlsanity.com/paper/2308.15602/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Scalable training of graph convolutional neural networks for fast and accurate predictions of HOMO-LUMO gap in molecules](https://mlsanity.com/paper/2207.11333/) (2022)
- [A hybrid numerical methodology coupling Reduced Order Modeling and Graph Neural Networks for non-parametric geometries: applications to structural dynamics problems](https://mlsanity.com/paper/2406.02615/) (2024)
- [Edge Graph Intelligence: Reciprocally Empowering Edge Networks with Graph Intelligence](https://mlsanity.com/paper/2407.15320/) (2024)
- [GCN-ABFT: Low-Cost Online Error Checking for Graph Convolutional Networks](https://mlsanity.com/paper/2412.18534/) (2024)
- [PGT-I: Scaling Spatiotemporal GNNs with Memory-Efficient Distributed Training](https://mlsanity.com/paper/2507.11683/) (2025)
- [Serving Graph Neural Networks With Distributed Fog Servers For Smart IoT Services](https://mlsanity.com/paper/2307.01684/) (2023)
- [Graph Neural Networks Gone Hogwild](https://mlsanity.com/paper/2407.00494/) (2024)
- [STen: Productive and Efficient Sparsity in PyTorch](https://mlsanity.com/paper/2304.07613/) (2023)
- [Parallel-friendly Spatio-Temporal Graph Learning for Photovoltaic Degradation Analysis at Scale](https://mlsanity.com/paper/2402.08470/) (2024)
- [Forecasting at Full Spectrum: Holistic Multi-Granular Traffic Modeling under High-Throughput Inference Regimes](https://mlsanity.com/paper/2505.01279/) (2025)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks](https://mlsanity.com/paper/2410.21006/) (2024)
- [Inference-friendly Graph Compression for Graph Neural Networks](https://mlsanity.com/paper/2504.13034/) (2025)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [AI Factories: It's time to rethink the Cloud-HPC divide](https://mlsanity.com/paper/2509.12849/) (2025)
- [Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification](https://mlsanity.com/paper/2603.29148/) (2026)
- [Communication-free Sampling and 4D Hybrid Parallelism for Scalable Mini-batch GNN Training](https://mlsanity.com/paper/2604.02651/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) are among the most powerful tools in deep learning. They routinely solve complex problems on unstructured networks, such as node classification, graph classification, or link prediction, with high accuracy. However, both inference and training of GNNs are complex, and they uniquely combine the features of irregular graph processing with dense and regular computations. This complexity makes it very challenging to execute GNNs efficiently on modern massively parallel architectures. To alleviate this, we first design a taxonomy of parallelism in GNNs, considering data and model parallelism, and different forms of pipelining. Then, we use this taxonomy to investigate the amount of parallelism in numerous GNN models, GNN-driven machine learning tasks, software frameworks, or hardware accelerators. We use the work-depth model, and we also assess communication volume and synchronization. We specifically focus on the sparsity/density of the associated tensors, in order to understand how to effectively apply techniques such as vectorization. We also formally analyze GNN pipelining, and we generalize the established Message-Passing class of GNN models to cover arbitrary pipeline depths, facilitating future optimizations. Finally, we investigate different forms of asynchronicity, navigating the path for future asynchronous parallel GNN pipelines. The outcomes of our analysis are synthesized in a set of insights that help to maximize GNN performance, and a comprehensive list of challenges and opportunities for further research into efficient GNN computations. Our work will help to advance the design of future GNNs.