Iterative Methods via Locally Evolving Set Process

Given the damping factor α and precision tolerance ε, citetandersen2006local introduced Approximate Personalized PageRank (APPR), the textitde facto local method for approximating the PPR vector, with runtime bounded by Theta(1/(αε)) independent of the graph size. Recently, citetfountoulakis2022open asked whether faster local algorithms could be developed using tildeO(1/(√αε)) operations. By noticing that APPR is a local variant of Gauss-Seidel, this paper explores the question of textitwhether standard iterative solvers can be effectively localized. We propose to use the textitlocally evolving set process, a novel framework to characterize the algorithm locality, and demonstrate that many standard solvers can be effectively localized. Let overlineoperatornamevol (St) and overlineγt be the running average of volume and the residual ratio of active nodes textstyle St during the process. We show overlineoperatornamevol (St)/overlineγt ≤ 1/ε and prove APPR admits a new runtime bound tildeO(overlineoperatornamevol(St)/(αoverlineγt)) mirroring the actual performance. Furthermore, when the geometric mean of residual reduction is Theta(√α), then there exists c ∈ (0,2) such that the local Chebyshev method has runtime tildeO(overlineoperatornamevol(St)/(√α(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.