Near-Optimality for Single-Source Personalized PageRank

The \emph{Single-Source Personalized PageRank} (SSPPR) query is central to graph OLAP, measuring the probability $π(s,t)$ that an $α$-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/ε)}{ε^2}, \frac{\sqrt{m \log n}}ε, m \log \frac{1}ε\right)\right)$ for SSPPR-A and $O\left(\min\left(\frac{\log(1/n)}δ, \sqrt{m \log(n/δ)}, m \log \left(\frac{\log(n)}{mδ}\right)\right)\right)$ for SSPPR-R, with trivial lower bounds of $Ω(\min(n,1/ε))$ and $Ω(\min(n,1/δ))$. This work narrows or closes this gap. We improve the upper bounds for SSPPR-A and SSPPR-R to $O\left(\frac{1}{ε^2}\right)$ and $O\left(\min\left(\frac{\log(1/δ)}δ, m + n \log(n) \log \left(\frac{\log(n)}{mδ}\right)\right)\right)$, respectively, offering improvements by factors of $\log(1/ε)$ and $\log\left(\frac{\log(n)}{mδ}\right)$. On the lower bound side, we establish stronger results: $Ω(\min(m, 1/ε^2))$ for SSPPR-A and $Ω(\min(m, \frac{\log(1/δ)}δ))$ for SSPPR-R, strengthening theoretical foundations. Our upper and lower bounds for SSPPR-R coincide for graphs with $m \in Ω(n \log^2 n)$ and any threshold $δ, 1/δ\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 $Ω(\min(n, 1/δ))$ to $Ω(\min(m, \frac{n}δ \log n))$, matching the upper bound and revealing its optimality.