Near-Optimality for Single-Source Personalized PageRank

Abstract

The \emph{Single-Source Personalized PageRank} (SSPPR) query is central to graph OLAP, measuring the probability $\ddot{I}€(s,t)$ that an $\hat{I}\pm$-decay random walk from node $s$ terminates at $t$. Despite decades of research, a significant gap remains between upper and lower bounds for its computational complexity. Existing upper bounds are $O\left(\min \left(\frac{\log (1/\hat{I}\mu )}{\hat{I}{\mu }^2},\frac{\sqrt{m\log n}}{\hat{I}}\mu ,m\log \frac{1}{\hat{I}}\mu \right)\right)$ for SSPPR-A and $O\left(\min \left(\frac{\log (1/n)}{\hat{I}}´,\sqrt{m\log (n/\hat{I}´)},m\log \left(\frac{\log (n)}{m\hat{I}´}\right)\right)\right)$ for SSPPR-R, with trivial lower bounds of $\hat{I}\text{c◯}(\min (n,1/\hat{I}\mu ))$ and $\hat{I}\text{c◯}(\min (n,1/\hat{I}´))$. This work narrows or closes this gap. We improve the upper bounds for SSPPR-A and SSPPR-R to $O\left(\frac{1}{\hat{I}{\mu }^2}\right)$ and $O\left(\min \left(\frac{\log (1/\hat{I}´)}{\hat{I}}´,m+n\log (n)\log \left(\frac{\log (n)}{m\hat{I}´}\right)\right)\right)$, respectively, offering improvements by factors of $\log (1/\hat{I}\mu )$ and $\log \left(\frac{\log (n)}{m\hat{I}´}\right)$. On the lower bound side, we establish stronger results: $\hat{I}\text{c◯}(\min (m,1/\hat{I}{\mu }^2))$ for SSPPR-A and $\hat{I}\text{c◯}(\min (m,\frac{\log (1/\hat{I}´)}{\hat{I}}´))$ for SSPPR-R, strengthening theoretical foundations. Our upper and lower bounds for SSPPR-R coincide for graphs with $m\in \hat{I}\text{c◯}(n{\log }^{2}n)$ and any threshold $\hat{I}´,1/\hat{I}´\in O(\text{poly}(n))$, achieving theoretical optimality in most graph regimes. The SSPPR-A query attains partial optimality for large error thresholds, matching our new lower bound. This is the first optimal result for SSPPR queries. Our techniques generalize to the Single-Target Personalized PageRank (STPPR) query, improving its lower bound from $\hat{I}\text{c◯}(\min (n,1/\hat{I}´))$ to $\hat{I}\text{c◯}(\min (m,\frac{n}{\hat{I}}´\log n))$, matching the upper bound and revealing its optimality.

To appear in PODS 2026