點擊藍(lán)字

關(guān)注我們

AI TIME歡迎每一位AI愛好者的加入！

點擊?閱讀原文?觀看作者直播講解回放！

作者簡介

孫浩鑫，復(fù)旦大學(xué)博士生，主要研究方向為大規(guī)模圖上快速算法設(shè)計。

概述

森林矩陣在網(wǎng)絡(luò)科學(xué)、觀點動力學(xué)和機(jī)器學(xué)習(xí)相關(guān)應(yīng)用中扮演著至關(guān)重要的角色，深刻刻畫了網(wǎng)絡(luò)的結(jié)構(gòu)信息與內(nèi)在聯(lián)系。在本文中，我們研究了在演化中的圖（與靜態(tài)圖相比，更準(zhǔn)確地代表了現(xiàn)實世界網(wǎng)絡(luò)的動態(tài)特性）中查詢森林矩陣元素的問題。為了應(yīng)對演化圖所帶來的獨特挑戰(zhàn)，我們首先為靜態(tài)圖中森林矩陣元素查詢提出了兩種近似算法，SFQ和SFQPlus。SFQ采用了森林矩陣的概率解釋，而SFQPlus則結(jié)合了一種新穎的方差減少技術(shù)，我們理論證明了SFQPlus擁有更小的方差，因而可以提供更高的精確度。基于這兩種算法，我們進(jìn)一步設(shè)計了兩種動態(tài)算法，這些算法的核心是高效地維護(hù)一系列帶根的生成森林列表。這種方法確保了更新（包括邊的添加和刪除）以及查詢矩陣元素的運行時間復(fù)雜度為，并且提供了森林矩陣元素的無偏估計。最后，通過在各種真實世界網(wǎng)絡(luò)上進(jìn)行廣泛的實驗，我們證明了我們算法的效率和有效性。特別是，我們的算法可以擴(kuò)展到擁有超過四千萬個節(jié)點的大規(guī)模網(wǎng)絡(luò)中。

論文地址：https://dl.acm.org/doi/10.1145/3637528.3671822

AITIME

01

Background

本文首先定義了森林矩陣Ω，它是單位矩陣I與拉普拉斯矩陣L和的逆矩陣。拉普拉斯矩陣L由圖的度矩陣D減去鄰接矩陣A得到。森林矩陣在有向圖中的元素值介于0到1之間，且每行元素之和為1，表現(xiàn)為行隨機(jī)矩陣。其對角元素在網(wǎng)絡(luò)分析中作為森林中心性指標(biāo)具有特別意義，已經(jīng)有研究深入探討了森林中心性的性質(zhì)與應(yīng)用。其非對角元素則可用來衡量兩點之間“距離”的遠(yuǎn)近，也有重要意義。

除此之外，在采用數(shù)學(xué)建?？坍嬌鐣^點的傳播與擴(kuò)散時，森林矩陣在Friedkin-Johnsen(FJ)模型中被視為核心矩陣。該模型是觀點動力學(xué)領(lǐng)域的著名模型，曾被用來解釋巴黎協(xié)定達(dá)成共識的過程。然而，鑒于社交網(wǎng)絡(luò)等現(xiàn)實世界的網(wǎng)絡(luò)不斷變化，本文關(guān)注于在不斷演化的圖上面提出快速查詢森林矩陣元素的方法，以適應(yīng)網(wǎng)絡(luò)的動態(tài)特性。

AITIME

02

Contributions

該研究的貢獻(xiàn)主要體現(xiàn)在兩個方面：首先，在靜態(tài)圖領(lǐng)域，研究者提出了森林矩陣元素的概率解釋，并開發(fā)了兩種快速算法SFQ和SFQ+，其中SFQ+算法通過引入創(chuàng)新的方差減少技術(shù)，實現(xiàn)了性能上的顯著提升。其次，針對演化圖，研究者專注于邊的插入和刪除操作，因為節(jié)點的插入和刪除可以看成一系列連續(xù)的邊的增刪操作。為此，作者設(shè)計了一種策略，利用特定的內(nèi)存數(shù)據(jù)結(jié)構(gòu)存儲圖信息，并在圖更新時快速調(diào)整該結(jié)構(gòu)，以實現(xiàn)在O(1)時間內(nèi)快速更新和查詢所需元素。

AITIME

03

Spanning Converging Forest

作者首先介紹了帶根生成森林的概念，并解釋了為何稱之為森林矩陣，原因在于該矩陣的元素與圖上的帶根生成森林緊密相關(guān)。

隨后，研究者闡釋了帶根生成樹的定義：它是一個連通圖且形態(tài)為樹，具有一個特定的根節(jié)點，該節(jié)點的出度為0，而樹中其他所有節(jié)點的出度均為1。帶根生成森林由多個這樣的連通分支組成，每個分支都是一棵以特定節(jié)點為根的樹。

例如，通過觀察提供的圖示，可以看到左側(cè)的圖是一個包含五個頂點和多條邊的小型圖。而右側(cè)的圖則展示了該圖中的一棵生成森林，其中三節(jié)點和五節(jié)點被選為根節(jié)點，而圖中的其他節(jié)點則是森林中的普通成員。

AITIME

04

Sampling Algorithm SFQ

作者通過矩陣森林定理闡釋了森林矩陣元素的含義，它代表在均勻生成的帶根生成森林中，節(jié)點i的根為節(jié)點j的概率。為了生成這樣的均勻帶根生成森林，研究者采用了Wilson算法的擴(kuò)展版本，Wilson提出的原始的算法可以返回一個給定根節(jié)點的生成樹，這里作者使用了它的拓展版本，用于生成帶根生成森林。左側(cè)的圖示展示了這一過程的起始步驟。

AITIME

05

Static Graphs-- SFQ

在前面的圖中，作者通過新增一個第6個頂點x，并在原圖中加入五條指向新節(jié)點x的新邊，這樣生成了拓展圖。接著，使用Wilson算法生成了一個以x為根的生成樹。第三步，刪除了新頂點x及其指向它的邊，從而獲得了一個均勻的帶根生成森林。這種方法具有O(n)的時間復(fù)雜度，適用于大規(guī)模網(wǎng)絡(luò)，并且支持并行處理，能夠在多個核上同時運行，顯著提高了效率。

作者提出了一種基礎(chǔ)算法，稱為SFQ算法。該算法在查詢時，基于已采樣的l個森林，計算節(jié)點的根為節(jié)點的概率。SFQ算法的時間復(fù)雜度為O(l)，這表明它在處理查詢時效率較高。

AITIME

06

Static Graphs-- SFQPLUS

AITIME

07

Algorithms SFQ and SFQPLUS

作者在靜態(tài)圖上提出了兩種算法：SFQ和SFQ Plus。SFQ算法首先利用了威爾遜算法的擴(kuò)展和矩陣森林定理，并且提供了一個無偏估計。而SFQ Plus算法由于聚合了更多的信息，不僅保持了無偏估計的特性，還擁有比SFQ更小的方差，從而提供了更優(yōu)的結(jié)果。簡而言之，研究者提出的第二個算法，SFQ Plus，在性能上超越了最初的SFQ算法。

AITIME

08

Evolving Graphs

AITIME

09

Edge Insertions

AITIME

10

Edge Deletions

具體而言，對應(yīng)下列算法的中的第二行-第九行。

AITIME

11

Pruning Technique

AITIME

12

Experiments

本文的算法通過一系列實驗驗證了其性能，結(jié)果表明，該算法能夠高效地處理大規(guī)模網(wǎng)絡(luò)，例如在推特網(wǎng)絡(luò)上，算法能夠順利處理達(dá)到四千萬節(jié)點的圖，且運行過程中沒有出現(xiàn)問題。這展示了算法在處理大規(guī)模數(shù)據(jù)集時的穩(wěn)定性和可靠性。

森林矩陣的對角元有重要意義，可用于衡量節(jié)點的中心性。作者首先對算法的對角元精度進(jìn)行了測試，發(fā)現(xiàn)以平均相對誤差為衡量標(biāo)準(zhǔn)，相較于SFQ算法，提出的SFQPlus算法精度有顯著提高。作者在演化圖與靜態(tài)圖上都進(jìn)行了實驗，發(fā)現(xiàn)算法在演化圖上的誤差高于靜態(tài)圖，這可能是由于生成森林?jǐn)?shù)量增加導(dǎo)致相關(guān)性增強(qiáng)，使得誤差隨迭代次數(shù)增長。這一現(xiàn)象指明了未來研究需要關(guān)注的優(yōu)化方向。

同時，常數(shù)時間的復(fù)雜度使得算法在查詢和更新速度上表現(xiàn)出色，無論是在中小規(guī)模網(wǎng)絡(luò)還是在擁有千萬節(jié)點的大規(guī)模網(wǎng)絡(luò)。如下表格展示了，當(dāng)網(wǎng)絡(luò)節(jié)點規(guī)模達(dá)到千萬級別，當(dāng)前最優(yōu)秀的圖求解器算法也無法在短時間內(nèi)返回查詢結(jié)果，而本文提出的算法則可以在極短時間內(nèi)返回結(jié)果。

本篇文章由陳研整理

點擊? 閱讀原文 觀看作者直播講解回放！

往期精彩文章推薦

論文解讀 | ACL2024 Outstanding Paper：因果指導(dǎo)的主動學(xué)習(xí)方法：助力大語言模型自動識別并去除偏見

?關(guān)于AI TIME?

AI TIME源起于2019年，旨在發(fā)揚科學(xué)思辨精神，邀請各界人士對人工智能理論、算法和場景應(yīng)用的本質(zhì)問題進(jìn)行探索，加強(qiáng)思想碰撞，鏈接全球AI學(xué)者、行業(yè)專家和愛好者，希望以辯論的形式，探討人工智能和人類未來之間的矛盾，探索人工智能領(lǐng)域的未來。

迄今為止，AI TIME已經(jīng)邀請了1800多位海內(nèi)外講者，舉辦了逾600場活動，超700萬人次觀看。

?

我知道你

在看

提出觀點，表達(dá)想法，歡迎

留言

點擊 閱讀原文?觀看作者直播講解回放！