Provably Fast Asynchronous And Distributed Algorithms For Pagerank Centrality Computation
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{he2021provably,
author = {Yiran He and Hoi-To Wai},
title = {{Provably Fast Asynchronous And Distributed Algorithms For Pagerank Centrality Computation}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2021},
url = {https://openreview.net/forum?id=OW9YL2UdpC},
}Loading related content...