Own-work bound for a recursive PageRank call
ProvedNearlyOptimalPPR.Computation.recursive_own_work_boundalgorithm-analysisgraph-theorypagerank
Fix the exact-solve primitive model. There are positive constants and a positive integer such that every created call, at every finite prefix, satisfies
Here , , and are its level, scale, and block size. Own work counts the actual debits produced by this call, excluding descendant debits. The input graph is finite and undirected with a nonisolated seed, , and .
This is the nonrecursive cost component of Lemma 4.4. It includes adjacency-row discovery, control visits, assembly and propagation, and exact solves, including completed budget-crossing updates. The constants depend only on the primitive model; neither closure nor termination is assumed.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open Finset Matrix NearlyOptimalPPR.Computation open scoped ENNReal
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_own_work_bound (m : SolveModel) :
∃ (C : ℝ) (c : ℕ), 0 < C ∧ 0 < c ∧
∀ (n : ℕ) (g : InputGraph n) (s : Fin n) (α ε : ℝ) (ℓ : ℕ) (schedule : BlockSchedule)
(T id : ℕ) (info : CallInformation),
(0 < α ∧ α ≤ 1/2) → (0 < ε ∧ ε ≤ 1) → 0 < g.graph.degree s →
let run := recursiveRun m g s α (rootThreshold ε ℓ) ℓ schedule
(run T).information id=some info →
(∑ k ∈ range T, ownStepCharge m g α ℓ (run k) id) ≤
ENNReal.ofReal (overhead C c ε ℓ*(info.scale^2/info.block+
if info.level=ℓ then info.scale*info.block else 0)) := 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 4.4 p.18 and its own-work accounting pp.28–29; Algorithms 6–9.