Iterative Methods via Locally Evolving Set Process

Given the damping factor $\alpha$ and precision tolerance $\epsilon$, \citet{andersen2006local} introduced Approximate Personalized PageRank (APPR), the $\mathit{\text{de}}\mathit{\text{facto}}\mathit{\text{local}}\mathit{\text{method}}$ for approximating the PPR vector, with runtime bounded by $\mathrm{\Theta }(1\mathrm{/}(\alpha \epsilon ))$ independent of the graph size. Recently, \citet{fountoulakis2022open} asked whether faster local algorithms could be developed using $\tilde{O}(1\mathrm{/}(\sqrt{\alpha }\epsilon ))$ operations. By noticing that APPR is a local variant of Gauss-Seidel, this paper explores the question of $\mathit{\text{whether}}\mathit{\text{standard}}\mathit{\text{iterative}}\mathit{\text{solvers}}\mathit{\text{can}}\mathit{\text{be}}\mathit{\text{effectively}}\mathit{\text{localized}}$. We propose to use the $\mathit{\text{locally}}\mathit{\text{evolving}}\mathit{\text{set}}\mathit{\text{process}}$, a novel framework to characterize the algorithm locality, and demonstrate that many standard solvers can be effectively localized. Let $\stackrel{}{\mathrm{vol}}(S_t)$ and ${\bar{\gamma }}_t$ be the running average of volume and the residual ratio of active nodes $S_t$ during the process. We show $\stackrel{}{\mathrm{vol}}(S_t)\mathrm{/}{\bar{\gamma }}_t\le 1\mathrm{/}\epsilon$ and prove APPR admits a new runtime bound $\tilde{O}(\stackrel{}{\mathrm{vol}}(S_t)\mathrm{/}(\alpha {\bar{\gamma }}_t))$ mirroring the actual performance. Furthermore, when the geometric mean of residual reduction is $\mathrm{\Theta }(\sqrt{\alpha })$, then there exists $c\in (0,2)$ such that the local Chebyshev method has runtime $\tilde{O}(\stackrel{}{\mathrm{vol}}(S_t)\mathrm{/}(\sqrt{\alpha }(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.