近日，威尼斯84881高瓴人工智能学院魏哲巍、文继荣团队的论文被ACM计算理论年会（ACM Symposium on Theory of Computing，STOC）录用。ACM计算理论年会（STOC）始于 1969年，是理论计算机科学领域最顶级的国际会议之一，在整个计算机科学领域享有崇高的声望，属于公认难度最高的会议之一，被中国计算机学会（CCF）推荐为A类国际会议。本届STOC会议将于2024年6月24日至6月28日在加拿大温哥华召开。

本篇论文的所有作者均来自威尼斯84881，论文作者为魏哲巍教授、文继荣教授、博士生王涵之和杨铭基。本文是首篇由人大师生独立完成的STOC论文，也是高瓴人工智能学院师生发表于STOC会议的第二篇论文，学院首篇STOC论文由王子贺团队于2023年6月发表。

论文介绍

论文题目：Revisiting Local Computation of PageRank: Simple and Optimal

论文作者：王涵之、魏哲巍、文继荣、杨铭基

（同等贡献，遵从理论计算机惯例作者顺序按照作者姓氏首字母的字母序排列）

通讯作者：魏哲巍

论文概述：PageRank是一种重要的图分析指标，其最初由Google公司的两位创始人提出以计算Google搜索引擎上的网页重要性排名，后成为一种经典的图节点中心性衡量指标，被广泛应用于社交网络、信息检索、推荐系统，甚至生物、化学、神经科学等领域。

2007年，Reid Andersen、Christian Borgs、Jennifer Chayes、John E. Hopcroft、Vahab S. Mirrokni和Shang-Hua Teng开始关注大图上PageRank contributions的计算问题，即给定图上一个节点t作为目标节点，希望寻找图上所有对节点t的PageRank分值影响较大的节点。Andersen等人联合提出了ApproxContributions算法，借助大图上局部搜索的方式完成PageRank contributions的计算。ApproxContributions算法（后又称LocalPush、Backward Search、Backward Push等）自提出后获得了广泛关注，现已成为PageRank计算的基石算法，其各种变形被广泛应用于图节点邻近度与相似度计算、随机游走概率计算、社区发现等多类图分析问题的求解中。

但是，ApproxContributions算法自提出至今，其在最坏情况下的计算时间复杂度（worst-case computational complexity）始终缺乏有意义的分析结果。Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng在2007年留于WAW会议上的开放问题“ApproxContributions算法的最坏时间复杂度是否能摆脱对图中节点度数的依赖？”虽经多年研究但始终未被解决。

本文给出了ApproxContributions算法在arc-centric graph-access model下的最坏时间复杂度上界，并给出了与之匹配的理论下界，证明了原始的ApproxContributions算法已至最优，从而回答了上述2007年提出的开放问题。特别地，本文所给出的分析方法十分简洁，且分析结果已至最优。

进一步地，本文将该分析结果应用于有向图上单点PageRank的计算问题（single-node PageRank computation）中，给出了arc-centric graph-access model下该问题的最坏时间复杂度和与之匹配的理论下界，回答了Marco Bressan、Enoch Peserico和Luca Pretto于FOCS 2018、SICOMP 2023上提出的开放问题“单点PageRank计算问题的时间复杂度上、下界间的理论差距是否可被消除？”。本文对该问题的分析过程亦非常简洁，且分析结果已至最优。