EUVIMEDEUVIMED entdecken
Crossref

Near-Optimality for Single-Source Personalized PageRank

Xinpeng Jiang, Haoyu Liu, Siqiang Luo, Xiaokui Xiao

Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-21

DOI: 10.1145/3801906 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Xinpeng Jiang und 3 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben. Gefördert von: NTU SUG-NAP, Singapore National Research Foundation, AI Singapore.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Single Source Personalized PageRank (SSPPR) query is a fundamental problem in graph OLAP, and has been extensively studied across various data-driven applications. For a source node s in a graph G, SSPPR measures the PPR score π (s, t ) for every node t ∈ G, where π(s, t ) is the probability that an α-decay random walk starting from s terminates at t . Despite decades of research, a significant gap remains between the known. Under two standard accuracy guarantees—absolute error (SSPPR-A), requiring |π̂(s, t ) - π (s, t ) | ≤ ε for all t, and relative error (SSPPR-R), requiring |π̂ (s, t ) ? π (s, t ) | ≤ c · π (s, t ) for all t with π (s, t ) ≥ δ-the best-known upper bounds by [6, 39, 43] collectively yield O ( min(log(1/ε )/ε 2 , √ m log n /ε, m log(1/ε ) ) ) for SSPPR-A and O ( min ( log(1/ n )/δ, √ m log( n /δ ), m log( log( n )/ m δ ) )) for SSPPR-R ( n , m denote the number of nodes and edges). Meanwhile, only trivial lower bounds are known—Ω(min( n , 1/ε ) ) [42] and Ω(min( n , 1/δ ) )—leaving a substantial theoretical gap yet to be closed. This work narrows or even closes this gap. On the upper bound side, we tighten the computational complexities of the SSPPR-A and SSPPR-R queries to O(1/ε 2 ) and O ( min ( log(1/δ )/δ, m + n log( n ) log( log( n )/ m δ ) )) , respectively. These results improve upon the best-known bounds by factors of log(1/ε) and log( log( n ) m δ ). On the lower bound side, under the standard arc-centric model,we establish sig nificantly stronger results: Ω(min( m , 1/ε 2 ) ) for SSPPR-A (improving by m / n or 1/ε) and Ω(min( m , log(1/δ )/δ ) ) for SSPPR-R (improving by m / n or log(1/δ)). These findings substantially strengthen the theoretical foundations of PPR computation: For SSPPR-R, our new upper and lower bounds coincide for graphs with m ∈ Ω( n log 2 ( n )) and any threshold δ, 1/δ ∈ O(poly( n )), indicating that we have achieved theoretical optimality under most graph regimes; the SSPPR-A query attains partial optimality under rough absolute error requirements (i.e., larger ε), where the upper bound simplifies to O(1/ε 2 ). This also matches our new lower bound result. To the best of our knowledge, this is the first work to establish an optimal algorithmic result for SSPPR queries. Further, our proposed techniques and results are generalizable to other relevant topics. Our lower-bound framework naturally extends to the Single-Target Personalized PageRank (STPPR) query, improving its lower bound from Ω(min( n , 1/δ ) ) to Ω(min( m , n /δ · log n ) ) under standard arc-centric model. This new result also matches the upper bound established in [36], revealing the optimality and underscoring its theoretical versatility.

Förderung

  • NTU SUG-NAP
  • Singapore National Research Foundation
  • AI Singapore
  • Singapore Ministry of Education

Zitieren

APA

Jiang, X., Liu, H., Luo, S., & Xiao, X. (2026). Near-Optimality for Single-Source Personalized PageRank. Proceedings of the ACM on Management of Data, 4(2), 1-21. https://doi.org/10.1145/3801906

Vancouver

Jiang X, Liu H, Luo S, Xiao X. Near-Optimality for Single-Source Personalized PageRank. Proceedings of the ACM on Management of Data. 2026;4(2):1-21. doi:10.1145/3801906

BibTeX
@article{Jiang2026,
  author = {Jiang, Xinpeng and Liu, Haoyu and Luo, Siqiang and Xiao, Xiaokui},
  title = {Near-Optimality for Single-Source Personalized PageRank},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {2},
  pages = {1--21},
  doi = {10.1145/3801906}
}
Kostenlos starten →