Iterative Methods via Locally Evolving Set Process

Code

• github.com/baojian/LocalCH
  Officialnone★ 1

Abstract

Given the damping factor and precision tolerance , andersen2006local 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, fountoulakis2022open asked whether faster local algorithms could be developed using O(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 O(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 O(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.

Reproductions