Number of budget-restart full solves in a PageRank call
ProvedNearlyOptimalPPR.Computation.recursive_restart_countalgorithm-analysisgraph-theorypagerank
Let be finite full-solve states of one recursive PageRank call. Let contain only transitions for which the next full solve was requested by a budget restart. If and are the call's scale and block size at the first snapshot, then
The input graph is finite and undirected with a nonisolated seed, , and positive root threshold. Each full solve is a reachable permitted event of that same call; no termination hypothesis is imposed.
This is the budget-restart count used in Lemma 4.4. It separates restarts from the other exceptions to residual-mass descent.
Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_work_analysis open Finset Matrix NearlyOptimalPPR.Computation
Formal statement
theorem NearlyOptimalPPR.Computation.recursive_restart_count (m : SolveModel) (n : ℕ) (g : InputGraph n) (s : Fin n) (α q : ℝ)
(hα : 0 < α ∧ α < 1) (hq : 0 < q) (hs : 0 < g.graph.degree s)
(ℓ : ℕ) (schedule : BlockSchedule) (τ : ℕ → ℕ) (hτ : StrictMono τ) (T id : ℕ)
(hfull : ∀ i ≤ T, fullSolveEvent g (recursiveRun m g s α q ℓ schedule (τ i)) id)
(E : Finset ℕ) (hE : E ⊆ Finset.range T)
(hrestart : ∀ i ∈ E, currentPC (recursiveRun m g s α q ℓ schedule (τ (i+1)-2))=.restartDrain) :
let st := recursiveRun m g s α q ℓ schedule (τ 0)
(E.card : ℝ) ≤ 2*(kappa ℓ 0 : ℝ)*(st.frames st.top).N/(st.frames st.top).block := 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, Lemmas 5.7–5.8 pp.26–28 and the finite-prefix event-counting proof of Lemma 4.4 pp.28–29; Lemma 4.4 statement p.18.