2025/07/19 by Jiang, Xinpeng, Liu, Haoyu, Luo, Siqiang +1 · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.14462
The 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(min((log(1/ε))/(ε2), \frac√(m log n)ε, m log \frac1ε)) for SSPPR-A and O(min(\fraclog(1/n)δ, √(m log(n/δ)), m log ((log(n))/(mδ)))) 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((1)/(ε2)) and O(min(\fraclog(1/δ)δ, m + n log(n) log ((log(n))/(mδ)))), respectively, offering improvements by factors of log(1/ε) and log((log(n))/(mδ)). On the lower bound side, we establish stronger results: Ω(min(m, 1/ε2)) for SSPPR-A and Ω(min(m, \fraclog(1/δ)δ)) for SSPPR-R, strengthening theoretical foundations. Our upper and lower bounds for SSPPR-R coincide for graphs with m ∈ Ω(n log2 n) and any threshold δ, 1/δ∈ O(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, \fracnδ log n)), matching the upper bound and revealing its optimality.