# Understanding GNN Computational Graph: A Coordinated Computation, IO, and Memory Perspective

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 25 references that are in the map.
- First posted on arXiv 18 Oct 2021.

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

- [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)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition](https://mlsanity.com/paper/1801.07455/) (2018)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Graph Convolutional Networks for Text Classification](https://mlsanity.com/paper/1809.05679/) (2018)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [Learning Human-Object Interactions by Graph Parsing Neural Networks](https://mlsanity.com/paper/1808.07962/) (2018)
- [Knowledge-aware Graph Neural Networks with Label Smoothness Regularization for Recommender Systems](https://mlsanity.com/paper/1905.04413/) (2019)
- [HyGCN: A GCN Accelerator with Hybrid Architecture](https://mlsanity.com/paper/2001.02514/) (2020)
- [DNNFusion: Accelerating Deep Neural Networks Execution with Advanced Operator Fusion](https://mlsanity.com/paper/2108.13342/) (2021)
- [GNNAdvisor: An Adaptive and Efficient Runtime System for GNN Acceleration on GPUs](https://mlsanity.com/paper/2006.06608/) (2020)
- [GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks](https://mlsanity.com/paper/2007.03179/) (2020)

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

- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [TpuGraphs: A Performance Prediction Dataset on Large Tensor Computational Graphs](https://mlsanity.com/paper/2308.13490/) (2023)
- [A Comprehensive Survey on Distributed Training of Graph Neural Networks](https://mlsanity.com/paper/2211.05368/) (2022)
- [RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations](https://mlsanity.com/paper/2210.10737/) (2022)
- [DeepGate4: Efficient and Effective Representation Learning for Circuit Design at Scale](https://mlsanity.com/paper/2502.01681/) (2025)
- [Learning Large Graph Property Prediction via Graph Segment Training](https://mlsanity.com/paper/2305.12322/) (2023)
- [Cached Operator Reordering: A Unified View for Fast GNN Training](https://mlsanity.com/paper/2308.12093/) (2023)
- [GNNBENCH: Fair and Productive Benchmarking for Single-GPU GNN System](https://mlsanity.com/paper/2404.04118/) (2024)
- [Edge Graph Intelligence: Reciprocally Empowering Edge Networks with Graph Intelligence](https://mlsanity.com/paper/2407.15320/) (2024)
- [Architectural Implications of GNN Aggregation Programming Abstractions](https://mlsanity.com/paper/2310.12184/) (2023)
- [DF-GNN: Dynamic Fusion Framework for Attention Graph Neural Networks on GPUs](https://mlsanity.com/paper/2411.16127/) (2024)
- [Rethinking Efficiency and Redundancy in Training Large-scale Graphs](https://mlsanity.com/paper/2209.00800/) (2022)
- [AdaptGear: Accelerating GNN Training via Adaptive Subgraph-Level Kernels on GPUs](https://mlsanity.com/paper/2305.17408/) (2023)
- [Single-GPU GNN Systems: Traps and Pitfalls](https://mlsanity.com/paper/2402.03548/) (2024)
- [Characterizing and Understanding HGNN Training on GPUs](https://mlsanity.com/paper/2407.11790/) (2024)
- [Optimization of GNN Training Through Half-precision](https://mlsanity.com/paper/2411.01109/) (2024)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [GeoT: Tensor Centric Library for Graph Neural Network via Efficient Segment Reduction on GPU](https://mlsanity.com/paper/2404.03019/) (2024)
- [SES: Bridging the Gap Between Explainability and Prediction of Graph Neural Networks](https://mlsanity.com/paper/2407.11358/) (2024)
- [Graph Structure Prompt Learning: A Novel Methodology to Improve Performance of Graph Neural Networks](https://mlsanity.com/paper/2407.11361/) (2024)
- [MixGCN: Scalable GCN Training by Mixture of Parallelism and Mixture of Accelerators](https://mlsanity.com/paper/2501.01951/) (2025)
- [Learning Mappings in Mesh-based Simulations](https://mlsanity.com/paper/2506.12652/) (2025)
- [Morphling: Fast, Fused, and Flexible GNN Training at Scale](https://mlsanity.com/paper/2512.01678/) (2025)
- [On Efficient Scaling of GNNs via IO-Aware Layers Implementations](https://mlsanity.com/paper/2605.31500/) (2026)
- [Efficient Recommendations via Graph Coarsening and Label Propagation](https://mlsanity.com/paper/2607.22287/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have been widely used in various domains, and GNNs with sophisticated computational graph lead to higher latency and larger memory consumption. Optimizing the GNN computational graph suffers from: (1) Redundant neural operator computation. The same data are propagated through the graph structure to perform the same neural operation multiple times in GNNs, leading to redundant computation which accounts for 92.4% of total operators. (2) Inconsistent thread mapping. Efficient thread mapping schemes for vertex-centric and edge-centric operators are different. This inconsistency prohibits operator fusion to reduce memory IO. (3) Excessive intermediate data. For GNN training which is usually performed concurrently with inference, intermediate data must be stored for the backward pass, consuming 91.9% of the total memory requirement. To tackle these challenges, we propose following designs to optimize the GNN computational graph from a novel coordinated computation, IO, and memory perspective: (1) Propagation-postponed operator reorganization. We reorganize operators to perform neural operations before the propagation, thus the redundant computation is eliminated. (2) Unified thread mapping for fusion. We propose a unified thread mapping scheme for both vertex- and edge-centric operators to enable fusion and reduce IO. (3) Intermediate data recomputation. Intermediate data are recomputed during the backward pass to reduce the total memory consumption. Extensive experimental results on three typical GNN models show that, we achieve up to 2.75x end-to-end speedup, 6.89x less memory IO, and 7.73x less memory consumption over state-of-the-art frameworks.