pith. sign in

arxiv: 2512.16087 · v5 · submitted 2025-12-18 · 💻 cs.DS

Instance-Optimality in PageRank Computation

Mikkel Thorup , Hanzhi Wang This is my paper

Pith reviewed 2026-05-16 21:50 UTC · model grok-4.3

classification 💻 cs.DS
keywords PageRankinstance optimalitybidirectional algorithmdirected graphsgraph algorithmsestimation algorithms
0
0 comments X

The pith

An adaptive bidirectional algorithm is instance-optimal up to polylog factors for PageRank estimation in bounded-degree graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that an adaptive version of the classic bidirectional algorithm estimates a vertex's PageRank to constant relative error and constant probability in instance-optimal time up to polylog factors. This holds for all directed graphs on n vertices where the maximum in-degree and out-degree are each at most a constant fraction of n. The optimality means no correct algorithm can be asymptotically faster on any individual graph from this class. The result extends to graphs with only polylog many high-degree vertices, which includes every sparse graph with O(n) edges, and carries over fully to multigraphs but only partially to weighted simple graphs.

Core claim

We prove that an adaptive variant of the simple classic bidirectional algorithm is instance-optimal up to a polylogarithmic factor for all directed graphs of order n whose maximum in- and out-degrees are at most a constant fraction of n. In other words, there is no correct algorithm that can be faster than our algorithm on any such graph by more than a polylogarithmic factor. We further extend the instance-optimality to all graphs in which at most a polylogarithmic number of vertices have unbounded degrees. This covers all sparse graphs with O(n) edges.

What carries the argument

The adaptive bidirectional algorithm, which performs forward and backward walks with adaptive stopping rules to produce PageRank estimates.

If this is right

  • Running time of the adaptive bidirectional algorithm is within polylog of the best possible on every bounded-degree graph.
  • The optimality result applies to every sparse graph with tilde-O(n) edges.
  • The bidirectional algorithm is instance-optimal on all multigraphs without degree restrictions.
  • Weighted simple graphs inherit nearly the same restrictions as unweighted ones.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • For PageRank queries on real-world sparse networks the bidirectional method is near-optimal without graph-specific tuning.
  • High-degree vertices appear to be the primary barrier to instance-optimality for this problem.
  • Similar adaptive-search techniques may yield instance-optimal algorithms for other centrality measures on bounded-degree graphs.

Load-bearing premise

Maximum in- and out-degrees are at most a constant fraction of n, or at most polylog vertices violate the bound.

What would settle it

A bounded-degree graph together with an algorithm that estimates PageRank to constant relative error faster than the adaptive bidirectional algorithm by more than a polylogarithmic factor.

Figures

Figures reproduced from arXiv: 2512.16087 by Hanzhi Wang, Mikkel Thorup.

Figure 1
Figure 1. Figure 1: Sketch of the constructions of the graphs [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
read the original abstract

We study the problem of estimating a vertex's PageRank within a constant relative error, with constant probability. We prove that an adaptive variant of the simple classic bidirectional algorithm is instance-optimal up to a polylogarithmic factor for all directed graphs of order $n$ whose maximum in- and out-degrees are at most a constant fraction of $n$. In other words, there is no correct algorithm that can be faster than our algorithm on any such graph by more than a polylogarithmic factor. We further extend the instance-optimality to all graphs in which at most a polylogarithmic number of vertices have unbounded degrees. This covers all sparse graphs with $\tilde{O}(n)$ edges. In addition, we provide a counterexample showing that the bidirectional algorithm is not instance-optimal for graphs whose degrees are mostly equal to $n$. We also consider weighted graphs and multigraphs. We show that the bidirectional algorithm is instance-optimal on \emph{all} multigraphs, but for weighted simple graphs, we have almost the same limitations as for unweighted simple graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that an adaptive variant of the classic bidirectional algorithm for estimating a vertex's PageRank to constant relative error (with constant probability) is instance-optimal up to a polylogarithmic factor on all directed graphs of order n whose maximum in- and out-degrees are at most a constant fraction of n. It establishes this via matching upper and lower bounds, supplies an explicit counterexample showing the necessity of the degree restriction, extends the claim to graphs with at most polylogarithmically many high-degree vertices (covering all Õ(n)-edge graphs), and treats weighted graphs and multigraphs, proving optimality on all multigraphs while retaining similar limitations for weighted simple graphs.

Significance. If the bounds hold, the work establishes the first instance-optimal PageRank estimator (up to polylog) under a natural degree restriction that captures all sparse directed graphs. This is a substantive advance in the complexity of local graph algorithms, as it shows that adaptivity in the bidirectional method matches the information-theoretic lower bound on every qualifying instance. The counterexample and multigraph result further delineate the precise boundary of the optimality claim.

major comments (2)
  1. [§5] §5 (lower-bound construction): the explicit family of instances used to prove the matching lower bound must be shown to force any correct algorithm to perform Ω(1/ε²) queries in the worst case; the current sketch leaves open whether the adaptive adversary can be realized without additional polylog overhead that would weaken the claimed tightness.
  2. [§7] §7 (extension to polylog high-degree vertices): the reduction from the bounded-degree case to the general sparse case claims the extra cost is absorbed into the polylog factor, but the argument does not explicitly bound the number of high-degree vertices that must be fully explored when they lie on the relevant PageRank paths; a concrete charging argument or potential function is needed to confirm the overall complexity remains Õ(1/ε²).
minor comments (2)
  1. [Abstract] The abstract states the degree bound as 'a constant fraction of n'; the body should introduce a fixed constant α < 1 and restate all theorems with this explicit parameter for clarity.
  2. [Notation] Notation for the polylogarithmic factor is sometimes written as polylog(n) and sometimes as Õ(·); adopt a single convention (preferably Õ) throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the detailed comments on Sections 5 and 7. We address each point below and will incorporate clarifications and expanded arguments into the revised manuscript.

read point-by-point responses

  1. Referee: [§5] §5 (lower-bound construction): the explicit family of instances used to prove the matching lower bound must be shown to force any correct algorithm to perform Ω(1/ε²) queries in the worst case; the current sketch leaves open whether the adaptive adversary can be realized without additional polylog overhead that would weaken the claimed tightness.

    Authors: We agree that the sketch in Section 5 would benefit from an explicit description of the adaptive adversary. In the full proof, the family of instances is constructed so that any algorithm (adaptive or not) must perform Ω(1/ε²) queries with constant probability; the adversary reveals edges only along paths that are consistent with the PageRank mass distribution and does not introduce extra polylogarithmic overhead beyond the Ω(1/ε²) term. We will expand the sketch to include the precise adversary strategy and a short argument confirming that the query lower bound holds tightly. revision: yes

  2. Referee: [§7] §7 (extension to polylog high-degree vertices): the reduction from the bounded-degree case to the general sparse case claims the extra cost is absorbed into the polylog factor, but the argument does not explicitly bound the number of high-degree vertices that must be fully explored when they lie on the relevant PageRank paths; a concrete charging argument or potential function is needed to confirm the overall complexity remains Õ(1/ε²).

    Authors: We thank the referee for this observation. The reduction in Section 7 bounds the number of high-degree vertices that can lie on relevant PageRank paths by the polylogarithmic allowance; each such vertex contributes at most a constant factor to the bidirectional search cost, which is absorbed into the overall Õ(1/ε²) bound. We will add an explicit charging argument (or potential function) that accounts for the exploration cost of these vertices and confirms that the total complexity remains Õ(1/ε²) with high probability. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes instance-optimality of the adaptive bidirectional PageRank estimator via explicit lower-bound constructions that apply to arbitrary correct algorithms on graphs satisfying the stated degree bound. The bound is treated as both necessary (via counterexample) and sufficient, with no parameters fitted from the paper's own outputs, no self-definitional reductions, and no load-bearing self-citations or imported uniqueness theorems. The derivation chain relies on standard algorithmic analysis and remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The analysis relies on standard probabilistic analysis of random walks and graph traversal; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Directed graphs with maximum in- and out-degrees at most a constant fraction of n
    This degree bound is the condition under which the instance-optimality theorem is stated and proven.

pith-pipeline@v0.9.0 · 5486 in / 1381 out tokens · 58522 ms · 2026-05-16T21:50:33.240673+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages · 1 internal anchor

  1. [1]

    Chayes, John E

    [ABC+08] Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Vahab S. Mir- rokni, and Shang-Hua Teng. Local computation of PageRank contributions.Internet Mathematics, 5(1):23–45, 2008.doi:10.1080/15427951.2008.10129302. [BBCT14] Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Shang-Hua Teng. Mul- tiscale matrix sampling and s...

    work page doi:10.1080/15427951.2008.10129302 2008

  2. [2]

    Estimating random-walk probabilities in directed graphs

    URL:https://doi.org/10.48550/arXiv.2504.16481, arXiv:2504.16481, doi:10.48550/ARXIV.2504.16481. [BM08] Ziv Bar-Yossef and Li-Tal Mashiach. Local approximation of PageRank and reverse PageRank. InProceedings of the 17th ACM International Conference on Information and Knowledge Management, pages 279–288, 2008.doi:10.1145/1458082.1458122. 26 [BP11] Marco Bre...

    work page internal anchor Pith review doi:10.48550/arxiv.2504.16481 2008

  3. [3]

    [LBG16] Peter Lofgren, Siddhartha Banerjee, and Ashish Goel

    doi:10.1007/978-3-319-26784-5\_13. [LBG16] Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Personalized PageRank es- timation and search: a bidirectional approach. In Proceedings of the 9th ACM International Conference on Web Search and Data Mining, pages 163–172,

    work page doi:10.1007/978-3-319-26784-5

  4. [4]

    [LBGC14] Peter Lofgren, Siddhartha Banerjee, Ashish Goel, and Seshadhri Comandur

    doi:10.1145/2835776.2835823. [LBGC14] Peter Lofgren, Siddhartha Banerjee, Ashish Goel, and Seshadhri Comandur. FAST- PPR: scaling Personalized PageRank estimation for large graphs. InProceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1436–1445, 2014.doi:10.1145/2623330.2623745. [Rou20] Tim Roughgarden...

    work page doi:10.1145/2835776.2835823 2014

  5. [5]

    [WW23] Hanzhi Wang and Zhewei Wei

    doi: 10.1145/3637528.3671820. [WW23] Hanzhi Wang and Zhewei Wei. Estimating single-node PageRank in˜O min dt, √m time. Proceedings of the VLDB Endowment, 16(11):2949–2961, 2023.doi:10.14778/ 3611479.3611500. [WWG+20] Hanzhi Wang, Zhewei Wei, Junhao Gan, Sibo Wang, and Zengfeng Huang. Personal- ized PageRank to a target node, revisited. InProceedings of th...

    work page doi:10.1145/3637528.3671820 2023

  6. [6]

    27 [WWWY24] Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, and Mingji Yang

    doi:10.1145/3394486.3403108. 27 [WWWY24] Hanzhi Wang, Zhewei Wei, Ji-Rong Wen, and Mingji Yang. Revisiting local computa- tionofPageRank: Simpleandoptimal. In Proceedings of the 56th Annual ACM Sympo- sium on Theory of Computing, pages 911–922, 2024.doi:10.1145/3618260.3649661. 28

    work page doi:10.1145/3394486.3403108 2024