高階交互建模的統(tǒng)計(jì)視角

高階交互建模的統(tǒng)計(jì)視角

A statistical perspective on higher-order interactions modeling

https://hal.science/hal-05571097v1/file/Hypergraph_review.pdf

摘要：

對(duì)高階交互（HOI）進(jìn)行建模已成為復(fù)雜系統(tǒng)分析中的一個(gè)關(guān)鍵挑戰(zhàn)，因?yàn)樵S多現(xiàn)象不能僅通過成對(duì)關(guān)系來完全捕捉。超圖通過允許兩個(gè)以上實(shí)體之間的交互來泛化圖，為表示這種復(fù)雜的依賴關(guān)系提供了一個(gè)強(qiáng)大的框架。采用統(tǒng)計(jì)和概率的視角對(duì)超圖建模，我們提出了對(duì)這個(gè)新興研究領(lǐng)域的引導(dǎo)式導(dǎo)覽。

我們首先說明HOI在真實(shí)世界系統(tǒng)中的普遍性，在這些系統(tǒng)中，交互通常涉及實(shí)體組而不是孤立的對(duì)。然后我們介紹超圖的基礎(chǔ)概念和符號(hào)，討論它們的描述性統(tǒng)計(jì)、基于圖的表示，以及與它們的復(fù)雜性相關(guān)的挑戰(zhàn)。我們進(jìn)一步探索超圖的各種統(tǒng)計(jì)模型，并解決節(jié)點(diǎn)聚類這一關(guān)鍵任務(wù)。最后，我們通過概述該領(lǐng)域中的一些開放性挑戰(zhàn)來結(jié)束。

關(guān)鍵詞：超圖模型，節(jié)點(diǎn)聚類，

1 引言

對(duì)高階交互（HOI）建模日益增長(zhǎng)的興趣源于這樣一種認(rèn)識(shí)：許多現(xiàn)象從根本上說比僅靠成對(duì)關(guān)系所能捕捉的要復(fù)雜得多。雖然網(wǎng)絡(luò)及其作為圖的數(shù)學(xué)表示捕捉了實(shí)體對(duì)之間的交互，但HOI本質(zhì)上具有不同的性質(zhì)，因?yàn)樗鼈兛赡苌婕皟蓚€(gè)以上元素的交互。考慮HOI提供了一種更豐富、更具表現(xiàn)力的方式來對(duì)各個(gè)不同領(lǐng)域的復(fù)雜交互進(jìn)行建模，范圍從社會(huì)網(wǎng)絡(luò)分析（早期在Simmel 1902a,b中得到認(rèn)可）或合著關(guān)系（Roy和Ravindran 2015），到生態(tài)系統(tǒng)（Muyinda等 2020）、神經(jīng)科學(xué)（Chelaru等 2021）或化學(xué)（Restrepo 2026）等。

最近關(guān)于HOI的綜述包括Battiston等（2020）；Bick等（2023）；Torres等（2021），它們主要關(guān)注來自物理學(xué)的復(fù)雜系統(tǒng)視角。我們選擇關(guān)注HOI的統(tǒng)計(jì)建模和概率視角（Lee等 2025也采用了這一視角），并將主要關(guān)注超圖。

本綜述不涉及的內(nèi)容。HOI分析是在數(shù)據(jù)收集步驟之后進(jìn)行的，在該步驟中，HOI可以直接被觀察到，或者從初步數(shù)據(jù)中推斷出來（例如Lizotte等 2023）。這里不討論這些HOI的構(gòu)建或推斷。單純復(fù)形（Bianconi 2021）通常被作為超圖的替代方案來建模HOI。它們帶有拓?fù)淇臻g中的節(jié)點(diǎn)位置，這一特征可能被證明是非常有用的。然而，有效的結(jié)構(gòu)強(qiáng)加了一種嵌套性質(zhì)，其中假設(shè)交互實(shí)體的每一個(gè)子集都在進(jìn)行交互。雖然這種假設(shè)對(duì)于例如鄰近交互（見下一節(jié)）可能是合適的，但在大多數(shù)應(yīng)用中，這顯得過于嚴(yán)格（合著例子是這種假設(shè)不合適的最突出的情況）。此外，即使在這種假設(shè)可能不是一個(gè)強(qiáng)約束的情況下，人們也可能會(huì)質(zhì)疑將這種補(bǔ)充信息引入建模的適當(dāng)性（例如，因?yàn)樗赡軙?huì)引入額外的噪聲）。關(guān)于HOI的單純性水平（即包含結(jié)構(gòu)）的一個(gè)有趣探索可以在Landry等（2024）中找到。

為了使我們的貢獻(xiàn)保持相對(duì)簡(jiǎn)潔，這里將不涵蓋HOI上的動(dòng)力學(xué)以及HOI的時(shí)間方面。最后，貝葉斯超圖是概率模型，其中一組隨機(jī)變量的依賴關(guān)系由HOI描述，從而泛化了貝葉斯網(wǎng)絡(luò)（Javidian等 2020）。因此，該主題與我們?cè)诖岁P(guān)注的已觀察到的HOI無關(guān)。

2 展現(xiàn)HOI的系統(tǒng)示例

借鑒Holme在其時(shí)間網(wǎng)絡(luò)綜述（Holme 2015）中的方法，我們首先對(duì)數(shù)據(jù)集類型，以及更廣泛地說，對(duì)HOI自然發(fā)生的系統(tǒng)，進(jìn)行一次快速的引導(dǎo)式導(dǎo)覽。有趣的是，Holme引用的很大一部分系統(tǒng)在其原始格式中似乎是HOI，隨后被簡(jiǎn)化為成對(duì)交互。我們沒有提供出現(xiàn)HOI的數(shù)據(jù)集或出版物的詳盡列表，而是強(qiáng)調(diào)這類數(shù)據(jù)的潛在普遍性。還要注意，任何二部網(wǎng)絡(luò)都自然地產(chǎn)生一個(gè)HOI，或者換種說法，迄今為止許多HOI一直被視為二部網(wǎng)絡(luò)。我們?cè)?.2節(jié)討論這兩種方法之間的差異。

社會(huì)科學(xué)和動(dòng)物行為學(xué)。社會(huì)交互是主要關(guān)注點(diǎn)，并推動(dòng)了網(wǎng)絡(luò)科學(xué)中絕大多數(shù)建模的發(fā)展。雖然二元交互是最簡(jiǎn)單的，但在社會(huì)學(xué)文獻(xiàn)中早就認(rèn)可了更大規(guī)模交互的作用和重要性（Simmel 1902a,b）。人類和動(dòng)物（分別地）是社會(huì)交互中考慮的經(jīng)典實(shí)體集。現(xiàn)在，這些交互中的大多數(shù)要么作為原始HOI進(jìn)行采樣，要么可以像成對(duì)交互那樣從原始數(shù)據(jù)中自然構(gòu)建。射頻識(shí)別數(shù)據(jù)就是這種情況，其中記錄了個(gè)體位置，并且交互發(fā)生在位于給定半徑球體內(nèi)的實(shí)體之間；以及在記錄人類/動(dòng)物聚集的野外觀察中1。通信可能包括經(jīng)典的電子郵件交換（具有多個(gè)接收者）或電話會(huì)議（在人類之間）以及非語言群體交互（Webb等 2023）。科學(xué)合作（例如合著）可能是HOI最突出的例子（例如Battiston等 2025；Roy和Ravindran 2015），也是解釋HOI與所有成對(duì)交互的團(tuán)之間差異的完美玩具示例。這些數(shù)據(jù)的變體包括在Web平臺(tái)上發(fā)布的軟件開發(fā)（Schueller等 2022）。更廣泛的合作方法涉及這樣的系統(tǒng)：當(dāng)個(gè)人在同一家公司董事會(huì)共同任職時(shí)，他們會(huì)形成一個(gè)HOI（Aksoy等 2020）。同樣，現(xiàn)在經(jīng)典的“悲慘世界”數(shù)據(jù)集描述了維克多·雨果小說中的人物在書的不同場(chǎng)景中如何交互，已經(jīng)從HOI的角度進(jìn)行了研究（Aksoy等 2020）。對(duì)于出演電影的演員也可以這樣做（例如，使用從互聯(lián)網(wǎng)電影數(shù)據(jù)庫(kù)中提取的數(shù)據(jù)）。

自然科學(xué)。

神經(jīng)科學(xué)和連接組學(xué)是人類大腦內(nèi)部HOI數(shù)據(jù)的重要來源，最近的方法依賴于功能磁共振成像數(shù)據(jù)（Santoro等 2024）或腦電圖和腦磁圖信號(hào)（Bilbao等 2026）。在考慮遺傳疾病時(shí)也會(huì)出現(xiàn)HOI，其中基因突變與特定疾病有關(guān)（Aksoy等 2020），或者在交互實(shí)體是代謝物的代謝通路中（Cervellini等 2026）。更一般地，HOI在化學(xué)中用于描述參與化學(xué)反應(yīng)的組分（Flamm等 2015）。生態(tài)學(xué)見證了針對(duì)HOI的關(guān)注度激增，其圍繞的核心思想是大多數(shù)成對(duì)交互實(shí)際上是由額外的參與者介導(dǎo)的（Bimler和Mayfield 2023；Mayfield和Stouffer 2017）。

3 HOI的概念、符號(hào)和表示

我們首先在本節(jié)中給出圍繞超圖概念的基本定義，它將作為我們表示HOI的標(biāo)準(zhǔn)形式。隨后，我們將繼續(xù)討論HOI的圖表示，并強(qiáng)調(diào)其局限性。

3.1 超圖

超圖上的描述性統(tǒng)計(jì)。

引入的一些用于描述圖的概念在超圖中找到了直接的推廣，而另一些概念，由于超圖相對(duì)于圖的復(fù)雜性增加，導(dǎo)致其定義具有更多的變異性。密度的情況就是如此。一個(gè)基本的定義將簡(jiǎn)單地計(jì)算超邊的數(shù)量除以此類超邊的最大數(shù)量，從而引入

在圖統(tǒng)計(jì)文獻(xiàn)中，傳遞性（transitivity）或聚類度量（clustering measures）的概念扮演著重要角色。這些本質(zhì)上基于成對(duì)交互的概念，因?yàn)樗鼈兞炕恕澳闩笥训呐笥岩彩悄愕呐笥选钡膬A向。這些概念在超圖世界中沒有自然的推廣（盡管存在一些嘗試性的定義，參見例如 Kim et al. 2023）。盡管如此，這些量也與“三角形”（即長(zhǎng)度為3的環(huán)）的頻率有關(guān)，并且轉(zhuǎn)向更一般的模體（motif）頻率概念，人們可以自然地將這些推廣到超圖背景下，唯一的限制是模體多樣性的復(fù)雜性增加（Juul et al. 2024; Lotito et al. 2022）。

大規(guī)模超圖特征。 盡管在21世紀(jì)初，大量文獻(xiàn)探索了大規(guī)模真實(shí)圖的特征，導(dǎo)致了諸如度數(shù)的無標(biāo)度分布或小世界特性等一般規(guī)律的 formulization，但這種大規(guī)模探索迄今為止受到的關(guān)注很少。這可能是由于這些數(shù)據(jù)的計(jì)算復(fù)雜性，或者是結(jié)構(gòu)的更大多樣性阻礙了一般規(guī)則的出現(xiàn)。在中等規(guī)模上，我們要提到 Do et al. (2020); Lee et al. (2021) 探索了來自不同領(lǐng)域的十三個(gè)真實(shí)世界超圖的特征，后一篇參考文獻(xiàn)重點(diǎn)關(guān)注超邊的重疊。

3.2 圖表示

由于其復(fù)雜性，將超圖簡(jiǎn)化為更簡(jiǎn)單的對(duì)象（如圖）是很誘人的（參見圖2作為說明），因?yàn)樗鼈兏菀滋幚怼Ｈ欢@是以丟失信息或放松某些約束為代價(jià)的，正如我們現(xiàn)在解釋的那樣。

團(tuán)圖（Clique graph）。 超圖的團(tuán)圖（也稱為2-截面、團(tuán)展開或團(tuán)約簡(jiǎn)）具有相同的節(jié)點(diǎn)集，以及共享超邊的節(jié)點(diǎn)之間的邊。超圖中的每條超邊實(shí)際上在圖中被約簡(jiǎn)為一個(gè)完全團(tuán)。也可以使用加權(quán)版本，將關(guān)于超邊大小的部分信息轉(zhuǎn)移到投影圖中。在任何情況下，這種樸素表示丟失了大量信息，并且不可能從團(tuán)圖重構(gòu)超邊。

線圖（Line graph）。 超圖的線圖具有對(duì)應(yīng)于該超圖超邊的頂點(diǎn)，以及重疊超邊（即共享至少一個(gè)節(jié)點(diǎn)）之間的邊。同樣，這種表示丟失了信息（關(guān)于共享了多少以及哪些節(jié)點(diǎn)），并且不可能從其線圖（唯一）恢復(fù)超圖。線圖主要用于總結(jié)超邊之間的鄰接關(guān)系（當(dāng)兩個(gè)超邊共享一個(gè)節(jié)點(diǎn)時(shí)，它們是相鄰的）。

二部圖。超圖的一種更精細(xì)的圖表示形式在于考慮其二部表示（或星擴(kuò)展圖），其中超圖的節(jié)點(diǎn)構(gòu)成第一部分節(jié)點(diǎn)，而超邊集構(gòu)成第二部分節(jié)點(diǎn)。當(dāng)原始節(jié)點(diǎn)在超圖中屬于某個(gè)原始超邊（現(xiàn)在是第二部分的一個(gè)節(jié)點(diǎn)）時(shí)，就在二部圖中從該原始節(jié)點(diǎn)畫一條邊指向該超邊。在某些條件下，這是一個(gè)無損的過程。更準(zhǔn)確地說，給定一個(gè)（簡(jiǎn)單）二部圖并選擇其中一部分作為原始節(jié)點(diǎn)集，人們可以在這個(gè)節(jié)點(diǎn)集上重構(gòu)一個(gè)唯一的（多重集）超圖，該超圖最終可能包含多個(gè)超邊和自環(huán)（見圖3）。換句話說，二部圖可以嵌入到超圖的一般空間中，而簡(jiǎn)單超圖可以投影到二部圖中。

4 超圖的統(tǒng)計(jì)模型

4.1 隨機(jī)性在于超邊：二部圖模型的局限性

從上一節(jié)可以看出，使用二部圖模型來推導(dǎo)超圖模型似乎是自然的。然而，這可能會(huì)帶來一些額外的代價(jià)，正如我們現(xiàn)在解釋的那樣。

隨機(jī)圖的配置模型包括從 n n 個(gè)節(jié)點(diǎn)上的所有可能圖集合中進(jìn)行均勻采樣，同時(shí)遵守規(guī)定的度序列。對(duì)于超圖，這些模型首先由 Ghoshal et al. (2009) 引入，重點(diǎn)關(guān)注三部（tripartite）和 3-均勻超圖。后來，Chodrow (2020) 將此框架擴(kuò)展到了非均勻情況。在這些工作中，節(jié)點(diǎn)度和超邊大小都保持固定——這是依賴于超圖二部表示的結(jié)果。配置模型對(duì)于采樣那些匹配觀測(cè)數(shù)據(jù)集的度序列（以及超邊大小）的圖（或超圖）特別有價(jià)值，通常通過洗牌算法實(shí)現(xiàn)。因此，它經(jīng)常作為統(tǒng)計(jì)分析中的零模型被采用。然而，從該模型中進(jìn)行精確采樣（相對(duì)于近似采樣）提出了重大挑戰(zhàn)，特別是對(duì)于超圖（詳見 Chodrow 2020 第 4 節(jié)）。

優(yōu)先依附（PA）模型已在 Wang et al. (2010) 中提出，其中引入了超邊增長(zhǎng)和超邊優(yōu)先依附的思想。這些想法后來在 Guo et al. (2016) 中得到完善，最近又在 Jung et al. (2026) 中得到完善。Barthelemy (2022) 為頂點(diǎn)屬于邊的概率提出了一個(gè)非常通用的公式，因此歸結(jié)為依賴于二部圖表示。他的方法包括 Erd?s-Rényi 類模型、配置模型、（某種）PA 模型以及隨機(jī)幾何模型。后一種模型旨在具有生成性，并且不容易適用于統(tǒng)計(jì)推斷。

4.3 潛在空間和塊模型

超圖的潛在空間模型（LSM）提出了為超過 2 個(gè)潛在位置的子集構(gòu)建鄰近指標(biāo)或度量的問題。Turnbull et al. 提出了一種隨機(jī)幾何超圖模型，其中一旦某些半徑的潛在位置球體相交，節(jié)點(diǎn)之間就會(huì)形成超邊。為了避免強(qiáng)加單純復(fù)形結(jié)構(gòu)，半徑隨節(jié)點(diǎn)子集大小而異（隨其增加），從而防止自動(dòng)包含較小子集。這個(gè)確定性框架隨后通過一個(gè)隨機(jī)步驟進(jìn)行了增強(qiáng)，盡管這引入了可識(shí)別性挑戰(zhàn)，這些挑戰(zhàn)通過在推斷期間的先驗(yàn)分布得到緩解。Lyu et al. (2023) 提出了一種基于張量的 LSM，但僅限于 3-均勻超圖。節(jié)點(diǎn)子集的鄰近度量也可以依賴于其（相對(duì)）潛在位置的平均值（例如算術(shù)平均、幾何平均、H?lder 平均等）。這是 Fritz et al. (2026) 追求的途徑，并結(jié)合了潛在雙曲空間，利用更具表現(xiàn)力的幾何結(jié)構(gòu)來處理分層和嵌入結(jié)構(gòu)。該工作還包含了一個(gè)用于超圖統(tǒng)計(jì)分析的最有前途的工具：樣本到總體（sample-to-population）估計(jì)過程，包括用近似值替換模型似然，其中僅對(duì)未發(fā)生的交互進(jìn)行采樣，而發(fā)生的交互（即超邊）全部包含在內(nèi)。

塊模型將在第 5 節(jié)討論，因?yàn)樗鼈兊碾x散潛在空間直接與節(jié)點(diǎn)聚類相關(guān)。我們?cè)诖颂岬?Ng and Murphy (2022) 的工作，該工作提出了超邊上的混合模型，因此與節(jié)點(diǎn)聚類無關(guān)。最后，Balasubramanian (2021) 提出了一種非參數(shù)超圖元（hypergraphon）模型，但僅限于均勻情況。

5 超圖上的節(jié)點(diǎn)聚類

我們?cè)趯ふ沂裁礃拥木垲愵愋停?/strong>

最簡(jiǎn)單的聚類類型是社區(qū)（community），在圖的背景下，其特征是內(nèi)部連接緊密但外部連接較弱的節(jié)點(diǎn)組。出現(xiàn)的第一個(gè)問題是：超圖中的社區(qū)是什么？人們可以認(rèn)為超邊構(gòu)成了（重疊的）社區(qū)，在這種情況下聚類是直接觀察到的。一個(gè)更精細(xì)的定義會(huì)指出，經(jīng)常共享相同超邊的節(jié)點(diǎn)形成一個(gè)社區(qū)。這里的一個(gè)關(guān)鍵挑戰(zhàn)是是否應(yīng)該考慮這些超邊的大小？例如，在圖1的玩具超圖中是否存在社區(qū)結(jié)構(gòu)？在那里，節(jié)點(diǎn)組{1,2,3,4}和{5,6,7}具有同樣多的內(nèi)部和外部超邊（分別為一個(gè)），但內(nèi)部超邊的大小更大。事實(shí)上，可能存在各種各樣的定義，這在文獻(xiàn)中產(chǎn)生了同樣多樣化的提議。

我們能希望檢測(cè)到它們嗎？節(jié)點(diǎn)聚類問題與信息論極限的存在密切相關(guān)，這些極限阻礙了恢復(fù)或檢測(cè)這些聚類。這個(gè)問題最初是在均勻超圖的背景下進(jìn)行探討的，從而限制了結(jié)果的范圍。事實(shí)上，盡管超圖可以被視為不同 s s值的 s s-均勻超圖的集合，但并非所有層都包含恢復(fù)潛在底層結(jié)構(gòu)所需的信息。稀疏超圖中的非均勻結(jié)果包括 Zhen 和 Wang (2023)，其中包含模型參數(shù)和社區(qū)的收斂界，以及 Dumitriu 等 (2025)，當(dāng)模型參數(shù)已知時(shí)，該研究提供了關(guān)于社區(qū)的弱一致性結(jié)果。最近，Ruggeri 等 (2024) 建立了在非均勻超圖中有效的首個(gè)檢測(cè)結(jié)果，然而這僅限于超邊的概率表示為成對(duì)概率之和的特定設(shè)置。這種二元限制使得該模型更類似于圖的設(shè)置。

基于模型的方法 - SBM 除了社區(qū)之外，塊模型方法簡(jiǎn)單地將聚類定義為具有相同（條件）交互概率的節(jié)點(diǎn)組。過去幾年文獻(xiàn)中出現(xiàn)了許多提議，以及度校正的變體（Ghoshdastidar 和 Dukkipati 2014；Chodrow 等 2021；Yuan 等 2022；Brusa 和 Matias 2024）。

其他方法。 超圖中節(jié)點(diǎn)聚類的其他方法包括基于模塊度（modularity）的方法。模塊度定義嚴(yán)重依賴于社區(qū)的定義，并且在該領(lǐng)域已經(jīng)遵循了各種方向。讀者將在 Poda 和 Matias (2024) 中找到這些方法的比較。譜聚類提供了一種替代方案。大多數(shù)現(xiàn)有方法嚴(yán)重依賴于（加權(quán)）團(tuán)圖表示（Ghoshdastidar 和 Dukkipati 2017），代價(jià)是丟失信息，而其他方法要么局限于單純結(jié)構(gòu)，要么局限于均勻超圖（del Genio 2025）。最后，已經(jīng)提出了一些基于隨機(jī)游走的方法（Swan 和 Zhan 2021）。

6 結(jié)論與下一步挑戰(zhàn)

可擴(kuò)展性肯定是超圖建模中最具挑戰(zhàn)性的問題之一。它體現(xiàn)在兩個(gè)方面：一方面需要能夠處理潛在巨大的超邊大小，另一方面更普遍地需要處理大型系統(tǒng)（即個(gè)體和交互的數(shù)量龐大）。近似推斷無疑是朝著這個(gè)方向發(fā)展的一個(gè)有前途的途徑，例如Fritz等人（2026）所開創(chuàng)的那樣。需要開發(fā)用于統(tǒng)計(jì)分析的高效軟件，以與現(xiàn)有的庫(kù)如HyperNetX（Praggastis等人，2024）相匹配。在非均勻超圖中獲得社區(qū)檢測(cè)的不可能結(jié)果或相變閾值似乎很困難，這無疑是該領(lǐng)域接下來的挑戰(zhàn)之一。正如前面所強(qiáng)調(diào)的，均勻超圖的結(jié)果在這方面不會(huì)有幫助，因?yàn)椴⒎撬袑佣夹枰峁┬畔ⅰ４送猓ㄒ豢捎玫拈撝担≧uggeri等人，2024）嚴(yán)重依賴于二元類型的建模假設(shè)。迫切需要用于超圖中社區(qū)檢測(cè)的合成基準(zhǔn)數(shù)據(jù)。這些數(shù)據(jù)可能不應(yīng)依賴于超圖隨機(jī)塊模型（SBM），以免在與其他方法的比較中使基于模型的方法占據(jù)優(yōu)勢(shì)。已經(jīng)提出了一些不夠令人信服的方案（參見Poda和Matias 2024中的討論），這再次引發(fā)了在超圖背景下如何定義社區(qū)這一棘手的問題。

原文鏈接：https://hal.science/hal-05571097v1/file/Hypergraph_review.pdf