| Paper ID | SPTM-4.2 |
| Paper Title |
PROVABLY FAST ASYNCHRONOUS AND DISTRIBUTED ALGORITHMS FOR PAGERANK CENTRALITY COMPUTATION |
| Authors |
Yiran He, Hoi-To Wai, The Chinese University of Hong Kong, Hong Kong SAR China |
| Session | SPTM-4: Estimation, Detection and Learning over Networks 2 |
| Location | Gather.Town |
| Session Time: | Tuesday, 08 June, 14:00 - 14:45 |
| Presentation Time: | Tuesday, 08 June, 14:00 - 14:45 |
| Presentation |
Poster
|
| Topic |
Signal Processing Theory and Methods: Signal Processing over Networks |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| 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. |
