Approximating Single-Source Personalized PageRank with Absolute Error Guarantees

Personalized PageRank (PPR) is an extensively studied and applied node proximity measure in graphs. For a pair of nodes s and t on a graph G=(V,E), the PPR value π(s,t) is defined as the probability that an α-discounted random walk from s terminates at t, where the walk terminates with probability α at each step. We study the classic Single-Source PPR query, which asks for PPR approximations from a given source node s to all nodes in the graph. Specifically, we aim to provide approximations with absolute error guarantees, ensuring that the resultant PPR estimates hatπ(s,t) satisfy maxt∈ Vbig|hatπ(s,t)-π(s,t)big|≤varepsilon for a given error bound varepsilon. We propose an algorithm that achieves this with high probability, with an expected running time of - widetildeObig(√m/varepsilonbig) for directed graphs, where m=|E|; - widetildeObig(√dmax/varepsilonbig) for undirected graphs, where dmax is the maximum node degree in the graph; - widetildeOleft(nγ-1/2/varepsilonright) for power-law graphs, where n=|V| and γ∈left(frac12,1right) is the extent of the power law. These sublinear bounds improve upon existing results. We also study the case when degree-normalized absolute error guarantees are desired, requiring maxt∈ Vbig|hatπ(s,t)/d(t)-π(s,t)/d(t)big|≤varepsilond for a given error bound varepsilond, where the graph is undirected and d(t) is the degree of node t. We give an algorithm that provides this error guarantee with high probability, achieving an expected complexity of widetildeOleft(√sumt∈ Vπ(s,t)/d(t)big/varepsilondright). This improves over the previously known O(1/varepsilond) complexity.