学院新闻

2023年11月，中国人民大学高瓴人工智能学院魏哲巍、文继荣教授团队的学术论文“Approximating Single-Source Personalized PageRank with Absolute Error Guarantees”被中国计算机学会（CCF）推荐的国际数据库理论会议（International Conference on Database Theory，ICDT）录用。这是中国人民大学师生首次在该国际学术会议上发表论文。ICDT是一个知名的国际会议，专注于数据管理领域的理论研究，涵盖了数据管理算法、数据模型和查询语言、数据管理系统等领域的基础理论研究。

论文介绍

论文题目：Approximating Single-Source Personalized PageRank with Absolute Error Guarantees

作者（同等贡献，按字母序排序）：魏哲巍，文继荣，杨铭基

论文概述：Personalized PageRank（PPR）是在图数据上被广泛研究和应用的一种节点邻近度度量指标。对于图G=(V,E)上的一对节点s和t，t关于s的PPR值定义为从s开始的α-衰减随机游走终止于t的概率，其中α-衰减随机游走指在每一步都以概率α终止的随机游走。我们研究了经典的单源PPR查询，即求出从给定的源节点s到图中所有节点的PPR估计。具体来说，我们旨在提供具有绝对误差保证的近似值，即确保计算得到的PPR估计值与真实值之间的绝对误差均不超过误差界限ε。我们提出了一个高概率实现这一目标的算法，其在有n个节点m条边的图上的期望运行时间为：

- 针对有向图，时间为soft-O(m^{1/2}/ε)，其中soft-O为省略polylog(n)项的大O记号；

- 针对无向图，时间为soft-O(d_{max}^{1/2}/ε)，其中d_{max}是图中的最大节点度数；

- 针对幂律图，时间为soft-O(n^{γ−1/2}/ε)，其中γ∈(1/2,1) 是幂律分布的指数。

这些亚线性的复杂度界改进了现有结果。我们还研究了在无向图上需要度归一化的绝对误差保证时的情况，即要求对每个节点t的PPR估计值与真实值之间的绝对误差不超过误差界限ε_d乘以节点t的度数。我们给出了一种以高概率提供这种误差保证的算法，其期望复杂度比之前已知的 O(1/ε_d) 复杂度渐进更优。