Forcing bound for recursive PageRank reference potentials
ProvedNearlyOptimalPPR.Computation.recursive_forcing_boundgraph-theorylinear-algebrapagerank
Let be the PageRank matrix, the seed vector, and the virtual reference potential of an open recursive level. At every finite reachable prefix,
coordinatewise. Here are the open ancestor thresholds and is the degree vector. The graph is finite and undirected with a nonisolated seed, and .
This inequality controls the negative part of the adjusted forcing vector in the full-solve comparison. It is the reference-potential estimate used in the proof of Lemma 5.8; no termination hypothesis is needed.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis open NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_forcing_bound (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(hα : 0 < α ∧ α < 1) (hq : 0 < q) (hs : 0 < g.graph.degree s)
(ℓ : ℕ) (schedule : BlockSchedule) (t : ℕ) :
ForcingInvariant g s α (recursiveRun m g s α q ℓ schedule t) := by sorrySource
Li, Xu, Yang, Zhou, Nearly optimal Personalized PageRank computation, STOC 2027 submission #884, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/884.pdf, Lemma 5.8 and its reference-potential comparison in Section 5, pp.26–28; Algorithms 6–9.