# Faster Local Solvers for Graph Diffusion Equations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 81 references that are in the map.
- First posted on arXiv 29 Oct 2024.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [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)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data](https://mlsanity.com/paper/2108.01099/) (2021)
- [Beltrami Flow and Neural Diffusion on Graphs](https://mlsanity.com/paper/2110.09443/) (2021)
- [Topology-Imbalance Learning for Semi-Supervised Node Classification](https://mlsanity.com/paper/2110.04099/) (2021)
- [GREAD: Graph Neural Reaction-Diffusion Networks](https://mlsanity.com/paper/2211.14208/) (2022)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections](https://mlsanity.com/paper/2403.16030/) (2024)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [Instant Graph Neural Networks for Dynamic Graphs](https://mlsanity.com/paper/2206.01379/) (2022)
- [FREDE: Anytime Graph Embeddings](https://mlsanity.com/paper/2006.04746/) (2020)
- [Subset Node Anomaly Tracking over Large Dynamic Graphs](https://mlsanity.com/paper/2205.09786/) (2022)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [Approximate Personalized PageRank on Dynamic Graphs](https://mlsanity.com/paper/1603.07796/) (2016)
- [When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks](https://mlsanity.com/paper/1702.05499/) (2017)

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

- [Fast and Robust Contextual Node Representation Learning over Dynamic Graphs](https://mlsanity.com/paper/2411.07123/) (2024)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)

## Abstract (arXiv)

Efficient computation of graph diffusion equations (GDEs), such as Personalized PageRank, Katz centrality, and the Heat kernel, is crucial for clustering, training neural networks, and many other graph-related problems. Standard iterative methods require accessing the whole graph per iteration, making them time-consuming for large-scale graphs. While existing local solvers approximate diffusion vectors through heuristic local updates, they often operate sequentially and are typically designed for specific diffusion types, limiting their applicability. Given that diffusion vectors are highly localizable, as measured by the participation ratio, this paper introduces a novel framework for approximately solving GDEs using a local diffusion process. This framework reveals the suboptimality of existing local solvers. Furthermore, our approach effectively localizes standard iterative solvers by designing simple and provably sublinear time algorithms. These new local solvers are highly parallelizable, making them well-suited for implementation on GPUs. We demonstrate the effectiveness of our framework in quickly obtaining approximate diffusion vectors, achieving up to a hundred-fold speed improvement, and its applicability to large-scale dynamic graphs. Our framework could also facilitate more efficient local message-passing mechanisms for GNNs.