审稿人直呼简洁，单点PageRank终极版！人大STOC论文让复杂度优化至「理论最优」

在信息爆炸的互联网时代，应如何根据重要性对搜索得到的网页进行排名并呈现给用户？

这个问题困扰了无数早期的搜索引擎。

破局者来自Google，创始人Sergey Brin和Lawrence Page提出的网页排名算法PageRank为这个难题提供了一个开创性的解决方案：为每个网页都计算了一个重要性得分，即PageRank得分，得分越高表示该网页质量越好，在信息检索时的重要性越高。

因此，在给用户反馈网页搜索结果时，此类重要网页应被排在更前面，以期用户具有较好的搜索体验。

考虑到互联网的庞大规模，「如何高效地计算出互联网上各网页的PageRank得分？」，这一问题自PageRank提出后便受到了研究者的长期关注，所研究问题大致可分为两类：

1. 计算互联网上所有网页的PageRank得分，更通用地，如果将互联网中的网页链接结构转化为一个图结构，网页对应图节点，网页间的链接关系对应节点间的连边，此类问题即希望高效地计算出图上所有节点的PageRank得分；

2. 与之相对地，另一类问题关注互联网上少量特定网页的PageRank得分计算，例如，计算某几个知名网站的PageRank得分，这类问题被称为单点PageRank计算（single-node PageRank）。

对于上述两类问题，第一类的研究已基本成熟，但第二类「单点PageRank计算」的计算复杂度还远未至最优。

最近，中国人民大学的研究人员在2024年的ACM计算理论年会（ACM Symposium on Theory of Computing，STOC）上发表了一篇论文将单点PageRank的计算复杂度优化至级别，同时给出了与之相匹配的理论下界，证明了其所提复杂度上下界的最优性。

图片

论文链接：https://arxiv.org/abs/2403.12648

论文的所有作者均来自人大，包括魏哲巍教授、文继荣教授、博士生王涵之和杨铭基。

这项研究解决了单点PageRank计算这一有着多年研究历史的难题，但其所给出的达到最优计算复杂度的理论证明却十分简洁。

几位STOC审稿人如此评价道：

「文中给出的证明出奇得短而简洁，却又是难以想到的，这令我感到吃惊。」

「这篇文章用十分精巧的分析解决了一个已被大量研究的问题。」

PageRank定义思想

Google最初基于如下两点给出了网页PageRank得分的计算方式：

1. 大家普遍倾向于引用质量较高的网页，如果一个网页被大量网页所引用，其质量应较好，故应提高其PageRank得分，从而提高其在搜索结果中的排名；

2. 另一方面，若一个网页已知较为重要（如知名机构的官网），则其所引用的网页也应较为重要。故一个PageRank得分较高的网页所引用的网页也应具有较高的PageRank得分，在搜索结果中的排名也应较高。

图片

由此，Google将各网页的初始PageRank得分都设为1，再根据上述两点规则对各网页的PageRank得分进行迭代更新直至各网页的PageRank得分收敛，从而以一种简洁而优雅的方式完成了互联网上网页重要性的量化，有效提高了Google搜索引擎的检索质量。

PageRank算法具有简洁的定义形式和良好的数学性质，其在被提出后即受到了广泛关注，相关计算形式后被视为图结构中节点中心性的一种重要衡量方式，被应用于网络分析、信息检索、推荐系统、图神经网络，甚至化学、生物和神经科学等领域中。PageRank也因其重要性和影响力被评为「数据挖掘十大算法」之一。

单点PageRank计算

单点PageRank计算作为PageRank研究中的一类重要问题，期望对互联网上一小部分目标网页的PageRank得分进行高效计算。

自2004年起，学者们就开始尝试以亚线性复杂度为目标进行算法设计，即希望在不获取整个互联网结构的情况下完成计算。

这里之所以强调亚线性时间复杂度，是因为当今互联网的规模过大，但传统的PageRank迭代算法需要对整个网络进行若干轮迭代计算直至各个网页的PageRank指标收敛，而在大数据时代海量的网页面前，这种全局迭代算法的计算代价变得难以忍受，也与该问题的输出大小（即几个目标网页的PageRank分值）差距过大。

然而，单点PageRank的计算直至2018年才首次有亚线性时间的算法被提出，且算法结构非常复杂，所得计算复杂度与该问题的理论下界间仍有一定差距，未达到理论最优。

中国人民大学的研究改进了单点PageRank问题的计算复杂度，将该问题的计算复杂度优化至理论最优，与该问题计算复杂度的理论下界完全匹配。

更有意思的是，这篇论文所给出的最优复杂度结果，是对一个提出于2016年WSDM论文上的算法BiPPR进行计算复杂度重新分析得到的。

图片

具体而言，在单点PageRank计算中，有两个常用的基础算子：蒙特卡洛采样（Monte Carlo Sampling）和确定性概率倒推（简称Push算法），分别于2005年和2007年提出。

其中，蒙特卡洛采样的思路是将单点PageRank计算转化为随机游走概率估计。此处随机游走对应的一个直观的动态过程：想象一名用户在互联网上冲浪，其随机点开一个网页进行浏览，在浏览过程中可能沿该网页中内嵌的链接进行网页跳转，亦可能在浏览到某网页时结束上网冲浪。

可以证明，互联网上任意一个网页t的PageRank分值，即等于一名用户在互联网上随意浏览网页时，浏览到网页t且在浏览网页t后即结束上网冲浪这一事件发生的概率。

图片

借助PageRank的上述概率含义，蒙特卡洛采样方法的思路为：在互联网上重复网页浏览过程多次，记录浏览到网页且在浏览网页后即结束上网冲浪这一事件发生的次数，用该次数占网页浏览过程重复次数的比例，作为对网页的PageRank得分的估计。

蒙特卡洛采样方法简洁、直接，是单点PageRank计算的基础方法，但其劣势为，在估计较小的PageRank分值会消耗大量的时间。在蒙特卡洛采样方法之后，来自UCSD、微软、康奈尔、波士顿大学的学者Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng在2007年提出了单点PageRank计算的另一个重要方法：确定性概率倒推（多被称为Push算法）。

确定性概率倒推方法可被理解为蒙特卡洛采样中随机游走的逆过程，其擅长估计较小的PageRank分值，与蒙特卡洛采样方法优势互补。但确定性概率倒推方法的计算复杂度分析始终缺乏有意义的结论，为此，Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng还在其论文的最后留下了开放性问题，希望在确定性概率倒推的计算复杂度分析方面有所突破。

2016年，斯坦福大学和康奈尔大学的三名学者Lofgren、Banerjee和Goel在WSDM会议上提出了BiPPR算法，其核心思想是给出了蒙特卡洛采样和确定性概率倒推两个基础方法的一种巧妙的结合方式，以期兼容二者优势。但是，由于确定性概率倒推计算复杂度的缺乏有意义的结果，BiPPR算法在最坏情况下的计算复杂度亦不明朗。

在BiPPR方法被提出之后，研究者们多次尝试改进BiPPR算法，其中最具代表性的是来自意大利罗马大学和帕多瓦大学的三名学者Bressan、Peserico、Pretto于2018年FOCS会议上提出的算法，其将蒙特卡洛采样和确定性倒推方法各自复杂化，并修改了两个方法的结合方式，最终得到了的计算复杂度结果，其中n和m分别为图节点数和边数、∆为图节点最大出度，此处表示隐去了对数因子的大O表示法。该复杂度结果是首个亚线性级别（即o(m+n)级别）的单点PageRank计算复杂度结果。

但是，得到该复杂度的算法结构非常复杂，且与计算复杂度下界之间存在较大差距。2023年，该复杂度被进一步优化至，但算法结构仍然复杂，与理论下界间仍有差距。

老算法新分析：基础算法的巧妙结合与简洁分析

中国人民大学今年的这篇STOC论文重新分析了2016年提出的BiPPR算法的计算复杂度，证明其复杂度可被约束为级别。同时，人大这篇论文还给出了与其复杂度上界相匹配的理论下界，证明其复杂度结果达到了理论最优。

该论文的核心思路可以概括为两点：其一，蒙特卡洛采样和确定性概率倒推两个基础方法优势互补，如果能将二者巧妙地结合起来，则可以有效提高该问题的计算效率；其二，BiPPR算法已经给出了一种很好的结合蒙特卡洛采样和确定性概率倒推的方法，之所以之前未得到理想的复杂度结论，主要在于确定性概率倒推方法的计算复杂度不清晰。

由此，人大STOC论文首先对确定性概率倒推方法在最坏情况下的计算复杂度进行了分析，首次给出了有效的复杂度结果，同时证明了所得复杂度的最优性，从而回答了Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng在2007年提出的关于确定性概率倒推方法计算复杂度的开放性问题。

该论文进一步将该复杂度分析用于对BiPPR方法的计算复杂度分析中，最终解决了单点PageRank计算这一有着多年研究历史的难题。

参考资料：

https://arxiv.org/abs/2403.12648