# Accelerating Scalable Graph Neural Network Inference with Node-Adaptive Propagation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Early exit and edge inference, one of 12 directions in Efficient LLM inference and serving.
- Builds on 50 of its 64 references that are in the map.
- First posted on arXiv 17 Oct 2023.

## Placed in

- Efficient LLM inference and serving / [Early exit and edge inference](https://mlsanity.com/inference/early-exit-and-edge-inference/)

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

- [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)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [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)
- [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)
- [Large-scale Point Cloud Semantic Segmentation with Superpoint Graphs](https://mlsanity.com/paper/1711.09869/) (2017)
- [Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud](https://mlsanity.com/paper/2003.01251/) (2020)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Session-based Recommendation with Graph Neural Networks](https://mlsanity.com/paper/1811.00855/) (2018)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [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)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Distilling Knowledge from Graph Convolutional Networks](https://mlsanity.com/paper/2003.10477/) (2020)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Heterogeneous Graph Neural Networks for Malicious Account Detection](https://mlsanity.com/paper/2002.12307/) (2020)
- [Degree-Quant: Quantization-Aware Training for Graph Neural Networks](https://mlsanity.com/paper/2008.05000/) (2020)
- [Self-Supervised Learning for Recommender Systems: A Survey](https://mlsanity.com/paper/2203.15876/) (2022)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)

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

- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [A Comprehensive Survey on Imbalanced Data Learning](https://mlsanity.com/paper/2502.08960/) (2025)
- [Graph Condensation for Open-World Graph Learning](https://mlsanity.com/paper/2405.17003/) (2024)
- [RobGC: Towards Robust Graph Condensation](https://mlsanity.com/paper/2406.13200/) (2024)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [Contrastive Graph Condensation: Advancing Data Versatility through Self-Supervised Learning](https://mlsanity.com/paper/2411.17063/) (2024)
- [Apt-Serve: Adaptive Request Scheduling on Hybrid Cache for Scalable LLM Inference Serving](https://mlsanity.com/paper/2504.07494/) (2025)
- [Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants](https://mlsanity.com/paper/2409.06998/) (2024)

## Abstract (arXiv)

Graph neural networks (GNNs) have exhibited exceptional efficacy in a diverse array of applications. However, the sheer size of large-scale graphs presents a significant challenge to real-time inference with GNNs. Although existing Scalable GNNs leverage linear propagation to preprocess the features and accelerate the training and inference procedure, these methods still suffer from scalability issues when making inferences on unseen nodes, as the feature preprocessing requires the graph to be known and fixed. To further accelerate Scalable GNNs inference in this inductive setting, we propose an online propagation framework and two novel node-adaptive propagation methods that can customize the optimal propagation depth for each node based on its topological information and thereby avoid redundant feature propagation. The trade-off between accuracy and latency can be flexibly managed through simple hyper-parameters to accommodate various latency constraints. Moreover, to compensate for the inference accuracy loss caused by the potential early termination of propagation, we further propose Inception Distillation to exploit the multi-scale receptive field information within graphs. The rigorous and comprehensive experimental study on public datasets with varying scales and characteristics demonstrates that the proposed inference acceleration framework outperforms existing state-of-the-art graph inference acceleration methods in terms of accuracy and efficiency. Particularly, the superiority of our approach is notable on datasets with larger scales, yielding a 75x inference speedup on the largest Ogbn-products dataset.