Accelerated Evolving Set Processes for Local PageRank Computation
This work provides a faster algorithm for computing Personalized PageRank, which is beneficial for applications requiring efficient local graph analysis, such as link prediction or recommendation systems.
This paper introduces a new framework using nested evolving set processes to speed up Personalized PageRank (PPR) calculations. The method achieves an $\epsilon$-approximation of the PPR vector with a time complexity of $\tilde{\mathcal{O}}(R^2 / (\sqrt{\alpha}\epsilon^2))$, which is independent of the graph size when $1/\epsilon^2 \ll m$.
This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $ε$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $\tilde{\mathcal{O}}(1/\sqrtα)$ such linear systems, where $α$ is the damping factor. When $1/ε^2\ll m$, this implies the existence of an algorithm that computes an $\ epsilon $-approximation of the PPR vector with an overall time complexity of $\tilde{\mathcal{O}}\left(R^2 / (\sqrtαε^2)\right)$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.