Revisiting Local Computation of PageRank: Simple and Optimal

We revisit ApproxContributions, the classic local graph exploration algorithm proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng (WAW 07, Internet Math. 08) for computing an epsilon-approximation of the PageRank contribution vector for a target node t on a graph with n nodes and m edges. We give a worst-case complexity bound of it as O(n Pi(t)/epsilon center dot min(Delta(in),Delta(out),root m)), where Pi(t) is the PageRank score of t, and Delta(in) and Delta(out) are the maximum in-degree and out-degree of the graph, resp. We also give a lower bound of Omega(min(Delta(in)/delta,Delta(out)/delta,root m/delta,m)) for detecting ts delta-contributing set, showing that the simple ApproxContributions algorithm is already optimal. As ApproxContributions has become a cornerstone for computing random-walk probabilities, our results and techniques can be applied to derive better bounds for various relevant problems. In particular, we investigate the computational complexity of locally estimating a nodes PageRank centrality. We improve the best-known upper bound of (O) over tilde (n(2/3)center dot min(Delta(1/3)(out),m(1/6))) given by Bressan, Peserico, and Pretto (SICOMP 23) to O(n(1/2)center dot min(Delta(1/2)(in),Delta(1/2)(out),m(1/4))) by combining ApproxContributions with Monte Carlo sampling. We also improve their lower bound of Omega(min(n(1/2)Delta(1/2)(out),n(1/3)m(1/3))) to Omega(n(1/2)center dot min(Delta(1/2)(in),Delta(1/2)(out),m(1/4))) if min(Delta(in),Delta(out))=Omega(n(1/3)), and to Omega(n(1/2-gamma)(min(Delta(in),Delta(out)))(1/2+gamma)) otherwise, where gamma > 0 is an arbitrarily small constant. Our matching upper and lower bounds resolve the open problem of whether one can tighten the bounds given by Bressan, Peserico, and Pretto (FOCS 18, SICOMP 23). Remarkably, the techniques and analyses for proving all our results are surprisingly simple.