Iterative Methods via Locally Evolving Set Process Baojian Zhou 1,2 Yifan Sun 3

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.