Research map / Graph learning / Graph algorithms and clustering
Faster Local Solvers for Graph Diffusion Equations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a local diffusion process framework that localizes standard iterative solvers (SOR, gradient descent, Chebyshev) to compute PPR, Katz, and heat kernel vectors, yielding sublinear-time, GPU-parallelizable local solvers.
Problem
Computing graph diffusion equations (PPR, Katz, heat kernel) on large graphs is expensive because standard iterative solvers touch the whole graph each iteration, while existing local push solvers are sequential and specific to one diffusion type.
Approach
Model local diffusion as a locally evolving active-set process and localize standard solvers (SOR, gradient descent, Chebyshev) by updating only active nodes; APPR is shown to be a special case of local SOR, and local GD is shown to be parallelizable with sublinear runtime bounds in terms of average active volume and participation-ratio-based localization.
Key results
- Local solvers achieve speedups over standard counterparts in operations; e.g., LocalGD reaches 1137.41x on ogbn-papers100M and 904.21x on ogbn-products for PPR.
- Across 18 graphs, the paper reports speedups of more than 100x in most cases for five datasets, and up to a hundredfold overall.
- In dynamic PPR-based GNN training (InstantGNN with LocalSOR), the method is reported as roughly twice as fast as the standard local propagation counterpart on ogbn-arxiv and ogbn-products with similar accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| localize GD | GD · ogbn-papers100M PPR | speedup ratio: 1137.41 | Helped |
| localize GD | GD · ogbn-products PPR | speedup ratio: 904.21 | Helped |
| localize GS | GS · ogbn-arxiv PPR | speedup ratio: 392.26 | Helped |
| localize CH | CH · Citeseer PPR | speedup ratio: 5.86 | Helped |
| use local solvers instead of global counterparts | PPR, Katz, and HK solvers · lower-precision wiki-talk | speedup | Helped |
| use local solvers instead of global counterparts | PPR, Katz, and HK solvers · high-precision wiki-talk (ε from 2^-17 to 2^-32) | speedup | Hurt |
| use LocalGD on GPU | GD on GPU · wiki-talk PPR | running time | Helped |
| use LocalSOR for dynamic PPR propagation | InstantGNN · ogbn-arxiv dynamic graph | training time | Helped |
Surprising findings
- LocalGS and LocalGD have the best overall speedups, even though LocalSOR and LocalCH converge faster per iteration, because the iteration counts at epsilon=1/n are already small.
- Speedups diminish and can become worse than standard solvers when very high precision is required.
Limitations
- No proven accelerated sublinear bounds for LocalSOR (with omega*) and LocalCH; monotonicity fails for these.
- Speedup is insignificant when epsilon is very small (high precision).
- Focuses mainly on PPR and Katz; other GDEs and the local message-passing idea for GNNs remain future work.
Experimental setup
Datasets: cora citeseer ogbn-arxiv ogbn-products ogbn-papers100M wiki-talk
Metrics: number of operations (speedup ratio) running time testing accuracy
Baselines: APPR (GS) AKatz AHK SOR/GS-SOR GD Chebyshev (CH) InstantGNN
Builds on: APPR (approximate personalized PageRank push) Gauss-Seidel / SOR InstantGNN APPNP
Closest papers by meaning
- A Generalized Neural Diffusion Framework on Graphs (AAAI 2024 · similarity 0.89)
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.88)
- Iterative Methods via Locally Evolving Set Process (NeurIPS 2024 · similarity 0.87)
- Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.86)
- Efficient and Scalable Graph Generation through Iterative Local Expansion (ICLR 2024 · similarity 0.86)
- Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.