Approximating Single-Source Personalized PageRank with Absolute Error Guarantees

Abstract

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 $\ddot{I}€(s,t)$ is defined as the probability that an $\hat{I}\pm$-discounted random walk from $s$ terminates at $t$, where the walk terminates with probability $\hat{I}\pm$ 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{\ddot{I}}€(s,t)$ satisfy ${\max }_{t\in V}|\hat{\ddot{I}}€(s,t)-\ddot{I}€(s,t)|\le \epsilon$ for a given error bound $\epsilon$. We propose an algorithm that achieves this with high probability, with an expected running time of - $\tilde{O}(\sqrt{m}/\epsilon )$ for directed graphs, where $m=|E|$; - $\tilde{O}(\sqrt{d_{\max }}/\epsilon )$ for undirected graphs, where $d_{\max }$ is the maximum node degree in the graph; - $\tilde{O}\left(n^{{\hat{I}}^3-1/2}/\epsilon \right)$ for power-law graphs, where $n=|V|$ and ${\hat{I}}^3\in \left(\frac{1}{2},1\right)$ 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 ${\max }_{t\in V}|\hat{\ddot{I}}€(s,t)/d(t)-\ddot{I}€(s,t)/d(t)|\le {\epsilon }_d$ for a given error bound ${\epsilon }_d$, 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 $\tilde{O}\left(\sqrt{{\sum }_{t\in V}\ddot{I}€(s,t)/d(t)}/{\epsilon }_d\right)$. This improves over the previously known $O(1/{\epsilon }_d)$ complexity.

25 pages, ICDT 2024