點(diǎn)擊藍(lán)字

關(guān)注我們

AI TIME歡迎每一位AI愛(ài)好者的加入！

點(diǎn)擊?閱讀原文?觀看作者直播講解回放！

作者簡(jiǎn)介

孫浩鑫，復(fù)旦大學(xué)博士生，主要研究方向?yàn)榇笠?guī)模圖上快速算法設(shè)計(jì)。

概述

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

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

AITIME

02

Contributions

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

AITIME

03

Spanning Converging Forest

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

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

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

AITIME

04

Sampling Algorithm SFQ

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

AITIME

05

Static Graphs-- SFQ

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

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

AITIME

06

Static Graphs-- SFQPLUS

AITIME

07

Algorithms SFQ and SFQPLUS

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

AITIME

08

Evolving Graphs

AITIME

09

Edge Insertions

AITIME

10

Edge Deletions

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

AITIME

11

Pruning Technique

AITIME

12

Experiments

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

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

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

本篇文章由陳研整理

點(diǎn)擊? 閱讀原文 觀看作者直播講解回放！

往期精彩文章推薦

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

?關(guān)于AI TIME?

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

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

?

我知道你

在看

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

留言

點(diǎn)擊 閱讀原文?觀看作者直播講解回放！