# Approximate Graph Propagation

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2021.

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

- [SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization](https://mlsanity.com/paper/2207.09179/) (2022)
- [Instant Graph Neural Networks for Dynamic Graphs](https://mlsanity.com/paper/2206.01379/) (2022)
- [Rethinking Node-wise Propagation for Large-scale Graph Learning](https://mlsanity.com/paper/2402.06128/) (2024)
- [Decoupled Graph Neural Networks for Large Dynamic Graphs](https://mlsanity.com/paper/2305.08273/) (2023)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation](https://mlsanity.com/paper/2305.09958/) (2023)
- [Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks](https://mlsanity.com/paper/2406.05482/) (2024)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [Privacy-Preserving Graph Embedding based on Local Differential Privacy](https://mlsanity.com/paper/2310.11060/) (2023)
- [GegenNet: Spectral Convolutional Neural Networks for Link Sign Prediction in Signed Bipartite Graphs](https://mlsanity.com/paper/2508.19907/) (2025)
- [Unifews: You Need Fewer Operations for Efficient Graph Neural Networks](https://mlsanity.com/paper/2403.13268/) (2024)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach](https://mlsanity.com/paper/2501.11823/) (2025)
- [Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds](https://mlsanity.com/paper/2306.08967/) (2023)
- [Fast and Robust Contextual Node Representation Learning over Dynamic Graphs](https://mlsanity.com/paper/2411.07123/) (2024)
- [Optimal Propagation for Graph Neural Networks](https://mlsanity.com/paper/2205.02998/) (2022)
- [Acceleration Algorithms in GNNs: A Survey](https://mlsanity.com/paper/2405.04114/) (2024)
- [Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective](https://mlsanity.com/paper/2405.19649/) (2024)
- [Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach](https://mlsanity.com/paper/2412.10789/) (2024)
- [Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation](https://mlsanity.com/paper/2510.10105/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

Efficient computation of node proximity queries such as transition probabilities, Personalized PageRank, and Katz are of fundamental importance in various graph mining and learning tasks. In particular, several recent works leverage fast node proximity computation to improve the scalability of Graph Neural Networks (GNN). However, prior studies on proximity computation and GNN feature propagation are on a case-by-case basis, with each paper focusing on a particular proximity measure. In this paper, we propose Approximate Graph Propagation (AGP), a unified randomized algorithm that computes various proximity queries and GNN feature propagation, including transition probabilities, Personalized PageRank, heat kernel PageRank, Katz, SGC, GDC, and APPNP. Our algorithm provides a theoretical bounded error guarantee and runs in almost optimal time complexity. We conduct an extensive experimental study to demonstrate AGP's effectiveness in two concrete applications: local clustering with heat kernel PageRank and node classification with GNNs. Most notably, we present an empirical study on a billion-edge graph Papers100M, the largest publicly available GNN dataset so far. The results show that AGP can significantly improve various existing GNN models' scalability without sacrificing prediction accuracy.