Provably Fast Asynchronous And Distributed Algorithms For Pagerank Centrality Computation

This paper considers the PageRank centrality computation problem on large graphs. We study asynchronous and distributed algorithms which are operated by aggregating information from local neighbors iteratively. Unlike prior works which rely on stochastic gradient descent (SGD) applied on a least square objective, we derive a stochastic approximation (SA) scheme for solving the PageRank problem by discretizing a linear system of ordinary differential equations. Our approach results in a family of asynchronous and distributed algorithms applicable for fixed and random topologies. Convergence rates are analyzed for both settings. In the fixed topology setting, we prove that the SA-based PageRank algorithm converges faster than the prior SGD-based method for large graphs. Numerical experiments support our findings.