{"ID":2892738,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.14462","arxiv_id":"2507.14462","title":"Near-Optimality for Single-Source Personalized PageRank","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2507.14462","url_pdf":"https://arxiv.org/pdf/2507.14462v5","authors":"[\"Xinpeng Jiang\",\"Haoyu Liu\",\"Siqiang Luo\",\"Xiaokui Xiao\"]","published":"2025-07-19T03:32:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}