Research map / Learning theory and algorithms / Sample complexity
Accelerated Evolving Set Processes for Local PageRank Computation
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 Accelerated Evolving Set Process (AESP), wrapping localized inexact accelerated proximal point steps around local solvers (LocGD, LocAPPR) to compute PPR in about O(1/sqrt(alpha)) local evolving set processes.
Problem
Computing single-source Personalized PageRank locally with an epsilon-approximation, where standard local methods scale as 1/alpha, and accelerated methods risk touching the whole graph because momentum breaks monotonic l1-norm decrease of the residual/gradient.
Approach
Nested evolving set processes: a Catalyst-style accelerated inexact proximal point outer loop, where each inner subproblem has a well-conditioned shifted linear system (condition number about (1+eta)/(eta+alpha)) solved locally by LocGD or LocAPPR, which guarantees monotone l1 gradient decrease and local running time.
Key results
- Theory: AESP-PPR runs O(1/sqrt(alpha)) outer iterations, with time complexity min{O~(m/sqrt(alpha)), O~(R^2/(sqrt(alpha) eps^2))}.
- Experiments on graphs up to 244M nodes and 1.728B edges (alpha=0.01, eps=1e-6) show faster early-stage convergence than APPR and APPR-opt.
- Speedups over LocAPPR and LocGD grow as alpha decreases on com-dblp (alpha in 1e-3 to 1e-1, eps=1e-7).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply AESP with LocAPPR instead of standard local methods | PPR computation · ogb-mag240m, ogbn-papers100M, com-friendster, wiki-en21 | early-stage convergence | Helped |
| Use AESP-LocAPPR rather than the other evaluated methods | PPR computation on real-world graphs · Four large-scale real-world graphs | efficiency | Helped |
| Apply AESP with LocGD or LocAPPR rather than non-accelerated local methods | PPR computation · com-dblp; varying damping factor | operations and running time | Helped |
| Initialize each inner process with the momentum iterate (ablation) | AESP-LocAPPR · com-dblp | outer-loop iterations | Helped |
| Initialize each inner process with zero instead of the momentum iterate (ablation) | AESP-LocAPPR · com-dblp | outer-loop iterations | Hurt |
| Initialize each inner process with the previous estimate instead of the momentum iterate (ablation) | AESP-LocAPPR · com-dblp | outer-loop iterations | Hurt |
Surprising findings
- The constant R is not universally bounded in theory; it is only empirically small and insensitive to graph size and condition number.
- Momentum-based warm start (z0 = y^(t-1)) gave the best overall performance among the tested initializations.
Limitations
- Constant R is not bounded universally across configurations, so the bound is not fully graph-independent in theory.
- When eps < 1/sqrt(m) the bound degrades to O~(m/sqrt(alpha)).
- Extension to the variational PPR formulation (ISTA or coordinate descent) is open due to non-negativity requirements.
Experimental setup
Datasets: com-dblp ogb-mag240m ogbn-papers100M com-friendster wiki-en21
Benchmarks: com-dblp ogb-mag240m ogbn-papers100M com-friendster wiki-en21
Metrics: log error ||D^-1(pi_hat - pi)||_inf number of operations (volume) running time
Baselines: APPR APPR-opt LocGD LocCH ASPR
Builds on: APPR Catalyst evolving set process FISTA-style accelerated gradient
Closest papers by meaning
- Iterative Methods via Locally Evolving Set Process (NeurIPS 2024 · similarity 0.89)
- Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank (NeurIPS 2026 · similarity 0.89)
- Fast Algorithms for Hypergraph PageRank with Applications to Semi-Supervised Learning (ICML 2024 · similarity 0.85)
- Faster Local Solvers for Graph Diffusion Equations (NeurIPS 2024 · similarity 0.85)
- PageRank Bandits for Link Prediction (NeurIPS 2024 · similarity 0.83)
- Differentially Private Graph Diffusion with Applications in Personalized PageRanks (NeurIPS 2024 · similarity 0.83)
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.