在信息爆炸的互聯(lián)網(wǎng)時(shí)代，應(yīng)如何根據(jù)重要性對(duì)搜索得到的網(wǎng)頁(yè)進(jìn)行排名并呈現(xiàn)給用戶？

這個(gè)問題困擾了無數(shù)早期的搜索引擎。

破局者來自Google，創(chuàng)始人Sergey Brin和Lawrence Page提出的網(wǎng)頁(yè)排名算法PageRank為這個(gè)難題提供了一個(gè)開創(chuàng)性的解決方案：為每個(gè)網(wǎng)頁(yè)都計(jì)算了一個(gè)重要性得分，即PageRank得分，得分越高表示該網(wǎng)頁(yè)質(zhì)量越好，在信息檢索時(shí)的重要性越高。

因此，在給用戶反饋網(wǎng)頁(yè)搜索結(jié)果時(shí)，此類重要網(wǎng)頁(yè)應(yīng)被排在更前面，以期用戶具有較好的搜索體驗(yàn)。

考慮到互聯(lián)網(wǎng)的龐大規(guī)模，「如何高效地計(jì)算出互聯(lián)網(wǎng)上各網(wǎng)頁(yè)的PageRank得分？」，這一問題自PageRank提出后便受到了研究者的長(zhǎng)期關(guān)注，所研究問題大致可分為兩類：

1. 計(jì)算互聯(lián)網(wǎng)上所有網(wǎng)頁(yè)的PageRank得分，更通用地，如果將互聯(lián)網(wǎng)中的網(wǎng)頁(yè)鏈接結(jié)構(gòu)轉(zhuǎn)化為一個(gè)圖結(jié)構(gòu)，網(wǎng)頁(yè)對(duì)應(yīng)圖節(jié)點(diǎn)，網(wǎng)頁(yè)間的鏈接關(guān)系對(duì)應(yīng)節(jié)點(diǎn)間的連邊，此類問題即希望高效地計(jì)算出圖上所有節(jié)點(diǎn)的PageRank得分；

2. 與之相對(duì)地，另一類問題關(guān)注互聯(lián)網(wǎng)上少量特定網(wǎng)頁(yè)的PageRank得分計(jì)算，例如，計(jì)算某幾個(gè)知名網(wǎng)站的PageRank得分，這類問題被稱為單點(diǎn)PageRank計(jì)算（single-node PageRank）。

對(duì)于上述兩類問題，第一類的研究已基本成熟，但第二類「單點(diǎn)PageRank計(jì)算」的計(jì)算復(fù)雜度還遠(yuǎn)未至最優(yōu)。

最近，中國(guó)人民大學(xué)的研究人員在2024年的ACM計(jì)算理論年會(huì)（ACM Symposium on Theory of Computing，STOC）上發(fā)表了一篇論文將單點(diǎn)PageRank的計(jì)算復(fù)雜度優(yōu)化至級(jí)別，同時(shí)給出了與之相匹配的理論下界，證明了其所提復(fù)雜度上下界的最優(yōu)性。

圖片

論文鏈接：https://arxiv.org/abs/2403.12648

論文的所有作者均來自人大，包括魏哲巍教授、文繼榮教授、博士生王涵之和楊銘基。

這項(xiàng)研究解決了單點(diǎn)PageRank計(jì)算這一有著多年研究歷史的難題，但其所給出的達(dá)到最優(yōu)計(jì)算復(fù)雜度的理論證明卻十分簡(jiǎn)潔。

幾位STOC審稿人如此評(píng)價(jià)道：

「文中給出的證明出奇得短而簡(jiǎn)潔，卻又是難以想到的，這令我感到吃驚?！?/p>

「這篇文章用十分精巧的分析解決了一個(gè)已被大量研究的問題。」

PageRank定義思想

Google最初基于如下兩點(diǎn)給出了網(wǎng)頁(yè)P(yáng)ageRank得分的計(jì)算方式：

1. 大家普遍傾向于引用質(zhì)量較高的網(wǎng)頁(yè)，如果一個(gè)網(wǎng)頁(yè)被大量網(wǎng)頁(yè)所引用，其質(zhì)量應(yīng)較好，故應(yīng)提高其PageRank得分，從而提高其在搜索結(jié)果中的排名；

2. 另一方面，若一個(gè)網(wǎng)頁(yè)已知較為重要（如知名機(jī)構(gòu)的官網(wǎng)），則其所引用的網(wǎng)頁(yè)也應(yīng)較為重要。故一個(gè)PageRank得分較高的網(wǎng)頁(yè)所引用的網(wǎng)頁(yè)也應(yīng)具有較高的PageRank得分，在搜索結(jié)果中的排名也應(yīng)較高。

圖片

由此，Google將各網(wǎng)頁(yè)的初始PageRank得分都設(shè)為1，再根據(jù)上述兩點(diǎn)規(guī)則對(duì)各網(wǎng)頁(yè)的PageRank得分進(jìn)行迭代更新直至各網(wǎng)頁(yè)的PageRank得分收斂，從而以一種簡(jiǎn)潔而優(yōu)雅的方式完成了互聯(lián)網(wǎng)上網(wǎng)頁(yè)重要性的量化，有效提高了Google搜索引擎的檢索質(zhì)量。

PageRank算法具有簡(jiǎn)潔的定義形式和良好的數(shù)學(xué)性質(zhì)，其在被提出后即受到了廣泛關(guān)注，相關(guān)計(jì)算形式后被視為圖結(jié)構(gòu)中節(jié)點(diǎn)中心性的一種重要衡量方式，被應(yīng)用于網(wǎng)絡(luò)分析、信息檢索、推薦系統(tǒng)、圖神經(jīng)網(wǎng)絡(luò)，甚至化學(xué)、生物和神經(jīng)科學(xué)等領(lǐng)域中。PageRank也因其重要性和影響力被評(píng)為「數(shù)據(jù)挖掘十大算法」之一。

單點(diǎn)PageRank計(jì)算

單點(diǎn)PageRank計(jì)算作為PageRank研究中的一類重要問題，期望對(duì)互聯(lián)網(wǎng)上一小部分目標(biāo)網(wǎng)頁(yè)的PageRank得分進(jìn)行高效計(jì)算。

自2004年起，學(xué)者們就開始嘗試以亞線性復(fù)雜度為目標(biāo)進(jìn)行算法設(shè)計(jì)，即希望在不獲取整個(gè)互聯(lián)網(wǎng)結(jié)構(gòu)的情況下完成計(jì)算。

這里之所以強(qiáng)調(diào)亞線性時(shí)間復(fù)雜度，是因?yàn)楫?dāng)今互聯(lián)網(wǎng)的規(guī)模過大，但傳統(tǒng)的PageRank迭代算法需要對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行若干輪迭代計(jì)算直至各個(gè)網(wǎng)頁(yè)的PageRank指標(biāo)收斂，而在大數(shù)據(jù)時(shí)代海量的網(wǎng)頁(yè)面前，這種全局迭代算法的計(jì)算代價(jià)變得難以忍受，也與該問題的輸出大?。磶讉€(gè)目標(biāo)網(wǎng)頁(yè)的PageRank分值）差距過大。

然而，單點(diǎn)PageRank的計(jì)算直至2018年才首次有亞線性時(shí)間的算法被提出，且算法結(jié)構(gòu)非常復(fù)雜，所得計(jì)算復(fù)雜度與該問題的理論下界間仍有一定差距，未達(dá)到理論最優(yōu)。

中國(guó)人民大學(xué)的研究改進(jìn)了單點(diǎn)PageRank問題的計(jì)算復(fù)雜度，將該問題的計(jì)算復(fù)雜度優(yōu)化至理論最優(yōu)，與該問題計(jì)算復(fù)雜度的理論下界完全匹配。

更有意思的是，這篇論文所給出的最優(yōu)復(fù)雜度結(jié)果，是對(duì)一個(gè)提出于2016年WSDM論文上的算法BiPPR進(jìn)行計(jì)算復(fù)雜度重新分析得到的。

圖片

具體而言，在單點(diǎn)PageRank計(jì)算中，有兩個(gè)常用的基礎(chǔ)算子：蒙特卡洛采樣（Monte Carlo Sampling）和確定性概率倒推（簡(jiǎn)稱Push算法），分別于2005年和2007年提出。

其中，蒙特卡洛采樣的思路是將單點(diǎn)PageRank計(jì)算轉(zhuǎn)化為隨機(jī)游走概率估計(jì)。此處隨機(jī)游走對(duì)應(yīng)的一個(gè)直觀的動(dòng)態(tài)過程：想象一名用戶在互聯(lián)網(wǎng)上沖浪，其隨機(jī)點(diǎn)開一個(gè)網(wǎng)頁(yè)進(jìn)行瀏覽，在瀏覽過程中可能沿該網(wǎng)頁(yè)中內(nèi)嵌的鏈接進(jìn)行網(wǎng)頁(yè)跳轉(zhuǎn)，亦可能在瀏覽到某網(wǎng)頁(yè)時(shí)結(jié)束上網(wǎng)沖浪。

可以證明，互聯(lián)網(wǎng)上任意一個(gè)網(wǎng)頁(yè)t的PageRank分值，即等于一名用戶在互聯(lián)網(wǎng)上隨意瀏覽網(wǎng)頁(yè)時(shí)，瀏覽到網(wǎng)頁(yè)t且在瀏覽網(wǎng)頁(yè)t后即結(jié)束上網(wǎng)沖浪這一事件發(fā)生的概率。

圖片

借助PageRank的上述概率含義，蒙特卡洛采樣方法的思路為：在互聯(lián)網(wǎng)上重復(fù)網(wǎng)頁(yè)瀏覽過程多次，記錄瀏覽到網(wǎng)頁(yè)且在瀏覽網(wǎng)頁(yè)后即結(jié)束上網(wǎng)沖浪這一事件發(fā)生的次數(shù)，用該次數(shù)占網(wǎng)頁(yè)瀏覽過程重復(fù)次數(shù)的比例，作為對(duì)網(wǎng)頁(yè)的PageRank得分的估計(jì)。

蒙特卡洛采樣方法簡(jiǎn)潔、直接，是單點(diǎn)PageRank計(jì)算的基礎(chǔ)方法，但其劣勢(shì)為，在估計(jì)較小的PageRank分值會(huì)消耗大量的時(shí)間。在蒙特卡洛采樣方法之后，來自UCSD、微軟、康奈爾、波士頓大學(xué)的學(xué)者Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng在2007年提出了單點(diǎn)PageRank計(jì)算的另一個(gè)重要方法：確定性概率倒推（多被稱為Push算法）。

確定性概率倒推方法可被理解為蒙特卡洛采樣中隨機(jī)游走的逆過程，其擅長(zhǎng)估計(jì)較小的PageRank分值，與蒙特卡洛采樣方法優(yōu)勢(shì)互補(bǔ)。但確定性概率倒推方法的計(jì)算復(fù)雜度分析始終缺乏有意義的結(jié)論，為此，Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng還在其論文的最后留下了開放性問題，希望在確定性概率倒推的計(jì)算復(fù)雜度分析方面有所突破。

2016年，斯坦福大學(xué)和康奈爾大學(xué)的三名學(xué)者Lofgren、Banerjee和Goel在WSDM會(huì)議上提出了BiPPR算法，其核心思想是給出了蒙特卡洛采樣和確定性概率倒推兩個(gè)基礎(chǔ)方法的一種巧妙的結(jié)合方式，以期兼容二者優(yōu)勢(shì)。但是，由于確定性概率倒推計(jì)算復(fù)雜度的缺乏有意義的結(jié)果，BiPPR算法在最壞情況下的計(jì)算復(fù)雜度亦不明朗。

在BiPPR方法被提出之后，研究者們多次嘗試改進(jìn)BiPPR算法，其中最具代表性的是來自意大利羅馬大學(xué)和帕多瓦大學(xué)的三名學(xué)者Bressan、Peserico、Pretto于2018年FOCS會(huì)議上提出的算法，其將蒙特卡洛采樣和確定性倒推方法各自復(fù)雜化，并修改了兩個(gè)方法的結(jié)合方式，最終得到了的計(jì)算復(fù)雜度結(jié)果，其中n和m分別為圖節(jié)點(diǎn)數(shù)和邊數(shù)、?為圖節(jié)點(diǎn)最大出度，此處表示隱去了對(duì)數(shù)因子的大O表示法。該復(fù)雜度結(jié)果是首個(gè)亞線性級(jí)別（即o(m+n)級(jí)別）的單點(diǎn)PageRank計(jì)算復(fù)雜度結(jié)果。

但是，得到該復(fù)雜度的算法結(jié)構(gòu)非常復(fù)雜，且與計(jì)算復(fù)雜度下界之間存在較大差距。2023年，該復(fù)雜度被進(jìn)一步優(yōu)化至，但算法結(jié)構(gòu)仍然復(fù)雜，與理論下界間仍有差距。

老算法新分析：基礎(chǔ)算法的巧妙結(jié)合與簡(jiǎn)潔分析

中國(guó)人民大學(xué)今年的這篇STOC論文重新分析了2016年提出的BiPPR算法的計(jì)算復(fù)雜度，證明其復(fù)雜度可被約束為級(jí)別。同時(shí)，人大這篇論文還給出了與其復(fù)雜度上界相匹配的理論下界，證明其復(fù)雜度結(jié)果達(dá)到了理論最優(yōu)。

該論文的核心思路可以概括為兩點(diǎn)：其一，蒙特卡洛采樣和確定性概率倒推兩個(gè)基礎(chǔ)方法優(yōu)勢(shì)互補(bǔ)，如果能將二者巧妙地結(jié)合起來，則可以有效提高該問題的計(jì)算效率；其二，BiPPR算法已經(jīng)給出了一種很好的結(jié)合蒙特卡洛采樣和確定性概率倒推的方法，之所以之前未得到理想的復(fù)雜度結(jié)論，主要在于確定性概率倒推方法的計(jì)算復(fù)雜度不清晰。

由此，人大STOC論文首先對(duì)確定性概率倒推方法在最壞情況下的計(jì)算復(fù)雜度進(jìn)行了分析，首次給出了有效的復(fù)雜度結(jié)果，同時(shí)證明了所得復(fù)雜度的最優(yōu)性，從而回答了Andersen、Borgs、Chayes、Hopcroft、Mirrokni和Teng在2007年提出的關(guān)于確定性概率倒推方法計(jì)算復(fù)雜度的開放性問題。

該論文進(jìn)一步將該復(fù)雜度分析用于對(duì)BiPPR方法的計(jì)算復(fù)雜度分析中，最終解決了單點(diǎn)PageRank計(jì)算這一有著多年研究歷史的難題。

參考資料：

https://arxiv.org/abs/2403.12648