# Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 49 references that are in the map.
- First posted on arXiv 14 Dec 2024.

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

- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [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)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited](https://mlsanity.com/paper/2202.03580/) (2022)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [Efficient Algorithms for Personalized PageRank Computation: A Survey](https://mlsanity.com/paper/2403.05198/) (2024)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Personalized PageRank to a Target Node, Revisited](https://mlsanity.com/paper/2006.11876/) (2020)
- [Efficient Estimation of Heat Kernel PageRank for Local Clustering](https://mlsanity.com/paper/1904.02707/) (2019)
- [Sublinear Time Spectral Density Estimation](https://mlsanity.com/paper/2104.03461/) (2021)
- [Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push](https://mlsanity.com/paper/2101.03652/) (2021)
- [Personalized PageRank Estimation and Search: A Bidirectional Approach](https://mlsanity.com/paper/1507.05999/) (2015)
- [Subset Node Representation Learning over Large Dynamic Graphs](https://mlsanity.com/paper/2106.01570/) (2021)
- [Personalized PageRank to a Target Node](https://mlsanity.com/paper/1304.4658/) (2013)
- [Accelerating Personalized PageRank Vector Computation](https://mlsanity.com/paper/2306.02102/) (2023)
- [Computing Heat Kernel Pagerank and a Local Clustering Algorithm](https://mlsanity.com/paper/1503.03155/) (2015)
- [Scalable and Effective Conductance-based Graph Clustering](https://mlsanity.com/paper/2211.12511/) (2022)
- [A Local Updating Algorithm for Personalized PageRank via Chebyshev Polynomials](https://mlsanity.com/paper/2110.02538/) (2021)
- [Approximating Single-Source Personalized PageRank with Absolute Error Guarantees](https://mlsanity.com/paper/2401.01019/) (2024)

## Abstract (arXiv)

Graph propagation (GP) computation plays a crucial role in graph data analysis, supporting various applications such as graph node similarity queries, graph node ranking, graph clustering, and graph neural networks. Existing methods, mainly relying on power iteration or push computation frameworks, often face challenges with slow convergence rates when applied to large-scale graphs. To address this issue, we propose a novel and powerful approach that accelerates power iteration and push methods using Chebyshev polynomials. Specifically, we first present a novel Chebyshev expansion formula for general GP functions, offering a new perspective on GP computation and achieving accelerated convergence. Building on these theoretical insights, we develop a novel Chebyshev power iteration method (ltwocheb) and a novel Chebyshev push method (chebpush). Our ltwocheb method demonstrates an approximate acceleration of O(√N) compared to existing power iteration techniques for both personalized PageRank and heat kernel PageRank computations, which are well-studied GP problems. For chebpush, we propose an innovative subset Chebyshev recurrence technique, enabling the design of a push-style local algorithm with provable error guarantee and reduced time complexity compared to existing push methods. We conduct extensive experiments using 5 large real-world datasets to evaluate our proposed algorithms, demonstrating their superior efficiency compared to state-of-the-art approaches.