Near-Optimality for Single-Source Personalized PageRank

doi:10.1145/3801906

Near-Optimality for Single-Source Personalized PageRank

2026-05-01

0

PRE

AI

DOI：10.1145/3801906

原文求助

摘要

En 中文

单源个性化PageRank（SSPPR）查询是图OLAP中的一个基本问题，已被广泛应用于各种数据驱动应用中。对于图G中的源节点s，SSPPR测量每个节点t（属于G）的PPR分数pi(s, t)，其中pi(s, t)是从s出发的alpha衰减随机游走终止于t的概率。尽管数十年的研究，已知理论与实际之间仍存在显著差距。在两种标准精度保证下——绝对误差（SSPPR-A），要求对所有t满足|pi(s, t)-r(s, t)|<=ε，以及相对误差（SSPPR-R），要求对所有pi(s, t)>=Vδ的t满足|pi(s, t)-r(s, t)|<=c·pi(s, t)——[6, 39, 43]的最佳已知上界分别为O(min(log(1/ε)/ε², m log n/ε, m log(1/ε)))（对于V SSPPR-A）和O(min(log(1/δ)/δ, m log(n/mδ)))（对于SSPPR-R）（n和m分别表示节点和边的数量）。同时，仅已知平凡的下界——Q(min(n,1/ε)) [42]和Q(min(n,1/δ))，留下了巨大的理论差距尚未填补。本研究缩小甚至填补了这一差距。在上界方面，我们将SSPPR-A和SSPPR-R查询的计算复杂度分别紧化至O(1/ε²)和O(min(log(1/δ)/δ, m + n log(n) log(log(n)/mδ))。这些结果在log(1/ε)和log(log(n)mδ)的因子上改进了最佳已知界。在下界方面，在标准弧中心模型下，我们建立了更强的结果：SSPPR-A为Ω(min(m, 1/ε²))（改进m/n或1/ε），SSPPR-R为Ω(min(m, log(1/δ)/δ))（改进m/n或log(1/δ))。这些发现显著强化了PPR计算的理论基础：对于SSPPR-R，我们的新上界和下界在m∈Θ(n log²(n))的图和任意阈值δ下（1/δ∈O(poly(n))）一致，表明我们在大多数图分布下实现了理论最优性；SSPPR-A查询在较宽松的绝对误差要求（即较大ε）下达到部分最优性，其上界简化为O(1/ε²)，这与我们新的下界结果一致。据我们所知，这是首次为SSPPR查询建立最优算法结果的工作。此外，我们提出的技术和结果可推广至其他相关主题。我们的下界框架自然扩展至单目标个性化PageRank（STPPR）查询，在标准弧中心模型下将其下界从Q(min(n, 1/δ))改进至Ω(min(m, n/δ·log n))。这一新结果也与[36]中建立的上界一致，揭示了其最优性并突显了其理论普适性。

Keyword:

Personalized PageRank

Upper Bound

Lower Bound

Near-Optimality for Single-Source Personalized PageRank

摘要

期刊

机构

引用论文