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

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

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

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

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

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

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

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

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

圖片

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

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

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

幾位STOC審稿人如此評價道：

「文中給出的證明出奇得短而簡潔，卻又是難以想到的，這令我感到吃驚。」

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

PageRank定義思想

Google最初基于如下兩點給出了網(wǎng)頁PageRank得分的計算方式：

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

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

圖片

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

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

單點PageRank計算

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

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

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

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

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

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

圖片

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

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

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

圖片

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

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

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

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

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

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

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

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

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

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

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

參考資料：

https://arxiv.org/abs/2403.12648