Tighter Bounds for Personalized PageRank

We study Personalized PageRank (PPR), where for nodes $s,t$ in a graph $G$, $\pi(s,t)$ is the probability that an $\alpha$-decay random walk from $s$ ends at $t$. Two key queries are: Single-Source PPR (SSPPR), computing $\pi(s,\cdot)$ for fixed $s$, and Single-Target PPR (STPPR), computing $\pi(\cdot,t)$ for fixed $t$. SSPPR is studied under absolute error (SSPPR-A), requiring $|\hat{\pi}(s,t)-\pi(s,t)|\le \epsilon$, and relative error (SSPPR-R), requiring $|\hat{\pi}(s,t)-\pi(s,t)|\le c\pi(s,t)$ for $t$ with $\pi(s,t)\ge \delta$; STPPR adopts the same relative criterion. These queries support web search, recommendation, sparsification, and graph neural networks. The best known upper bounds are $O(\min(\tfrac{\log(1/\epsilon)}{\epsilon^{2}},\tfrac{\sqrt{m\log n}}{\epsilon},m\log\tfrac{1}{\epsilon}))$ for SSPPR-A and $O(\min(\tfrac{\log(1/\delta)}{\delta},\sqrt{\tfrac{m\log n}{\delta}},m\log\tfrac{\log n}{\delta m}))$ for SSPPR-R, while lower bounds remain $\Omega(\min(n,1/\epsilon))$, $\Omega(\min(m,1/\delta))$, and $\Omega(\min(n,1/\delta))$, leaving large gaps. We close these gaps by (i) presenting a Monte Carlo algorithm that tightens the SSPPR-A upper bound to $O(1/\epsilon^{2})$, and (ii) proving, via an arc-centric construction, lower bounds $\Omega(\min(m,\tfrac{\log(1/\delta)}{\delta}))$ for SSPPR-R, $\Omega(\min(m,\tfrac{1}{\epsilon^{2}}))$ (and intermediate $\Omega(\min(m,\tfrac{\log(1/\epsilon)}{\epsilon}))$) for SSPPR-A, and $\Omega(\min(m,\tfrac{n}{\delta}\log n))$ for STPPR. For practical settings ($\delta=\Theta(1/n)$, $\epsilon=\Theta(n^{-1/2})$, $m\in\Omega(n\log n)$) these bounds meet the best known upper bounds, establishing the optimality of Monte Carlo and FORA for SSPPR-R, our algorithm for SSPPR-A, and RBS for STPPR, and yielding a near-complete complexity landscape for PPR queries.