Iterative Methods via Locally Evolving Set Process

Given the damping factor α and precision tolerance ϵ, Andersen et al. [2] introduced Approximate Personalized PageRank (APPR), the de facto local method for approximating the PPR vector, with runtime bounded by Θ(1/(αϵ)) independent of the graph size. Recently, Fountoulakis & Yang [12] asked whether faster local algorithms could be developed using Õ(1/(√αϵ)) operations. By noticing that APPR is a local variant of Gauss-Seidel, this paper explores the question of whether standard iterative solvers can be effectively localized. We propose to use the locally evolving set process, a novel framework to characterize the algorithm locality, and demonstrate that many standard solvers can be effectively localized. Let vol(S_t) and γ_t be the running average of volume and the residual ratio of active nodes S_t during the process. We show vol(S_t)/γ_t ≤ 1/ϵ and prove APPR admits a new runtime bound Õ(vol(S_t)/(αγ_t)) mirroring the actual performance. Furthermore, when the geometric mean of residual reduction is Θ(√α), then there exists c ∈ (0, 2) such that the local Chebyshev method has runtime Õ(vol(S_t)/(√α(2 − c))) without the monotonicity assumption. Numerical results confirm the efficiency of this novel framework and show up to a hundredfold speedup over corresponding standard solvers on real-world graphs.