A Survey on Hypergraph Mining: Patterns, Tools, and Generators

超圖挖掘綜述：模式、工具與生成器

https://arxiv.org/pdf/2401.08878v2

超圖屬于高階網(wǎng)絡(luò)家族，是建模現(xiàn)實世界中群體交互的一種自然且強(qiáng)大的選擇。例如，在建?？赡懿粌H涉及兩人，而是三人或更多人的協(xié)作網(wǎng)絡(luò)時，使用超圖使我們能夠超越成對（二元）模式進(jìn)行探索，并捕捉群體（多元）模式。超圖的數(shù)學(xué)復(fù)雜性既為超圖挖掘帶來了機(jī)遇，也帶來了挑戰(zhàn)。超圖挖掘的目標(biāo)是發(fā)現(xiàn)不同領(lǐng)域真實世界超圖中反復(fù)出現(xiàn)的結(jié)構(gòu)性質(zhì)，我們稱之為模式。為了發(fā)現(xiàn)模式，我們需要工具。我們將超圖挖掘工具分為三類：（1）零模型（用于檢驗觀測模式的顯著性）；（2）結(jié)構(gòu)元素（即超圖中的子結(jié)構(gòu)，例如開三角與閉三角）；（3）結(jié)構(gòu)量（即用于計算超圖模式的數(shù)值工具，例如傳遞性）。此外，還存在超圖生成器，其目標(biāo)是生成能夠忠實表征真實世界超圖的合成超圖。在本綜述中，我們對超圖挖掘的當(dāng)前研究格局進(jìn)行全面概述，涵蓋模式、工具與生成器三個方面。我們?yōu)槊恳活悆?nèi)容提供了系統(tǒng)的分類體系，并就超圖挖掘的未來研究方向進(jìn)行了深入探討。

CCS 概念：? 計算數(shù)學(xué) → 超圖；隨機(jī)圖；圖算法；? 計算理論 → 圖算法分析；? 信息系統(tǒng) → 數(shù)據(jù)挖掘；? 以人為中心的計算 → 社交網(wǎng)絡(luò)分析。

附加關(guān)鍵詞與短語：超圖挖掘，超圖生成器，高階網(wǎng)絡(luò)

1 引言
群體交互在復(fù)雜的現(xiàn)實世界中普遍存在，并出現(xiàn)在多種情境下，包括科研協(xié)作 [16]、蛋白質(zhì)相互作用 [53] 以及商品聯(lián)合購買 [174] 等。這些涉及多個個體或?qū)嶓w的高階交互，可以被自然且有效地建模為超圖 [14, 160]。

超圖是（成對）圖的推廣，由節(jié)點和超邊組成。與圖中只能連接兩個節(jié)點的邊不同，超邊被定義為節(jié)點的非空子集，自然地建模了涉及任意數(shù)量節(jié)點的交互。超邊大小的靈活性賦予了超圖強(qiáng)大的表達(dá)能力，使其能夠準(zhǔn)確建模圖所難以勝任的廣泛群體交互。例如，在圖1中，在合著超圖中，每個節(jié)點代表一位研究者，每條超邊代表一項合著關(guān)系，涉及構(gòu)成該超邊的各個節(jié)點所對應(yīng)的研究者。需要注意的是，合著關(guān)系并不適合用圖中的邊來表示。當(dāng)三位研究者合作發(fā)表一篇論文時，若連接所有可能的研究者配對，將無法區(qū)分這一群體交互與三篇由不同研究者配對合著的論文。超圖這種固有的表達(dá)能力促使其在諸多領(lǐng)域得到應(yīng)用，包括推薦系統(tǒng) [170]、計算機(jī)視覺 [113]、自然語言處理 [43]、社交網(wǎng)絡(luò)分析 [8]、金融分析 [176]、生物信息學(xué) [53] 以及電路設(shè)計 [64]。

受使用（成對）圖建模成功理解現(xiàn)實世界系統(tǒng)的啟發(fā)（參見綜述 [28]），近期研究深入探討了建模這些系統(tǒng)的真實世界超圖的結(jié)構(gòu)。超圖建模，尤其是每條超邊大小的靈活性，引入了圖論背景下未曾考慮的獨特視角。這為超圖挖掘帶來了新的機(jī)遇與挑戰(zhàn)：超圖挖掘旨在通過發(fā)現(xiàn)并解釋不同領(lǐng)域真實世界超圖中反復(fù)出現(xiàn)的結(jié)構(gòu)性質(zhì)的成因，來增進(jìn)我們對底層系統(tǒng)的理解。此類反復(fù)出現(xiàn)的結(jié)構(gòu)性質(zhì)通常被稱為（結(jié)構(gòu)）模式1。因此，專門的挖掘工具（例如，用于定義結(jié)構(gòu)模式的元素與量度）已被開發(fā)出來，以分析超圖獨特的結(jié)構(gòu)特征。利用這些工具，研究者已揭示了真實世界超圖中多種非平凡的局部結(jié)構(gòu)模式 [16, 102, 118] 與全局結(jié)構(gòu)模式 [45, 94]。這些模式中的大多數(shù)能夠清晰地區(qū)分真實世界超圖與隨機(jī)超圖，且通常伴隨直觀的解釋或底層機(jī)制。它們顯著增進(jìn)了我們對現(xiàn)實世界系統(tǒng)的理解。

超圖生成器（或超圖生成模型）對于驗證我們對結(jié)構(gòu)性質(zhì)的理解非常有用。通過復(fù)現(xiàn)觀測到的模式，這些模型中的機(jī)制為真實世界模式提供了合理的解釋。正因如此，結(jié)合超圖結(jié)構(gòu)模式的普遍性，超圖生成器在近期研究中日益受到關(guān)注 [17, 45, 59, 101]。這些生成器能夠成功生成合成超圖，復(fù)現(xiàn)真實世界超圖中觀測到的特定模式，從而為理解與預(yù)測超圖結(jié)構(gòu)提供寶貴見解。此類合成超圖對于模擬與評估超圖算法也具有重要價值，尤其在收集或追蹤真實世界超圖不切實際的情境下。此外，這些生成器還可用于創(chuàng)建匿名化數(shù)據(jù)集（具體而言，即結(jié)構(gòu)上與給定數(shù)據(jù)集相近的合成數(shù)據(jù)集），正如在圖數(shù)據(jù)上已廣泛開展的做法 [128]。

范圍。在本綜述中，我們深入探討了關(guān)于真實世界超圖挖掘的廣泛研究，旨在對該領(lǐng)域的當(dāng)前研究狀態(tài)進(jìn)行全面分析。我們的綜述涵蓋了超圖挖掘的多個方面，包括結(jié)構(gòu)模式（即在不同領(lǐng)域的真實世界超圖中反復(fù)出現(xiàn)的結(jié)構(gòu)性質(zhì)）、挖掘工具（例如，用于定義模式的結(jié)構(gòu)元素與結(jié)構(gòu)量），以及能夠復(fù)現(xiàn)并從而闡明模式的生成器。對于每種工具，我們闡釋其背后的直觀思想及其與先前概念的關(guān)聯(lián)。我們?yōu)槟Ｊ脚c生成器提供了系統(tǒng)的分類體系（即類別劃分）。對于模式，我們首先依據(jù)是否考慮時間演化，將其劃分為靜態(tài)模式與動態(tài)模式。隨后，我們根據(jù)每種模式所定義的最小單元，將模式進(jìn)一步細(xì)分為不同層級：節(jié)點層級、超邊層級、子超圖層級與超圖層級。對于生成器，我們依據(jù)其生成的是完整超圖還是子超圖，將其劃分為全超圖生成器與子超圖生成器。隨后，我們依據(jù)其生成的是靜態(tài)超圖還是動態(tài)（即時序）超圖，將生成器進(jìn)一步劃分為靜態(tài)生成器與動態(tài)生成器。我們基于生成器的輸出、需求以及復(fù)現(xiàn)特定模式的能力，對其進(jìn)行了系統(tǒng)比較。綜上所述，本綜述聚焦于真實世界超圖中涌現(xiàn)的模式，以及旨在復(fù)現(xiàn)這些真實世界模式的生成器。有關(guān)本綜述所涵蓋研究工作的年份范圍概覽，請參見表1。

相關(guān)綜述。真實世界圖挖掘領(lǐng)域擁有豐富的歷史背景，由此催生了大量模式與生成器的研究。Chakrabarti 與 Faloutsos [28] 對真實世界圖中的模式及圖生成器進(jìn)行了全面概述。Drobyshevskiy 與 Turdakov [47] 以及 Bonifati 等人 [20] 則聚焦于圖生成器，對其進(jìn)行了詳細(xì)分類。近年來，學(xué)界對超圖的興趣日益增長。Antelmi 等人 [7]、Gao 等人 [60] 以及 Zhang 等人 [181] 對超圖學(xué)習(xí)進(jìn)行了系統(tǒng)性綜述。Kim 等人 [90] 專門對超圖神經(jīng)網(wǎng)絡(luò)進(jìn)行了深入綜述。Preti 等人 [139] 總結(jié)了高階網(wǎng)絡(luò)（包括超圖）的高級分析技術(shù)。部分綜述聚焦于超圖的應(yīng)用，包括可視化 [56] 與劃分 [25]。Torres 等人 [160] 廣泛探討了包括超圖在內(nèi)的不同數(shù)學(xué)框架，以表征高階復(fù)雜系統(tǒng)。類似地，Battiston 等人 [14] 從動力系統(tǒng)與隨機(jī)過程的視角，考察了超圖作為建模高階交互工具的有效性。此外，已有多個為超圖分析構(gòu)建的開源庫 [6, 76, 116]。在本綜述中，我們系統(tǒng)性地考察真實世界超圖中的結(jié)構(gòu)模式，以統(tǒng)一的超圖模式分類體系呈現(xiàn)超圖挖掘的最新進(jìn)展，并探討其在超圖生成及其他下游任務(wù)中的實際應(yīng)用。有關(guān)本綜述結(jié)構(gòu)的可視化圖示，請參見圖2。

2 預(yù)備知識

雖然星擴(kuò)展包含了超圖中所有的關(guān)聯(lián)信息，但節(jié)點和超邊都被統(tǒng)一表示為節(jié)點。然而，由于節(jié)點和超邊具有截然不同的特征 [173]，這種對稱處理可能并不理想。在大多數(shù)超圖操作、結(jié)構(gòu)元素和數(shù)量計算中，節(jié)點和超邊是被區(qū)別對待的，從而打破了這種對稱性，而這在星擴(kuò)展中是無法實現(xiàn)的。參見圖 3 以獲取上述兩種二元投影的示例。

B8. 時序超圖。與上文介紹的靜態(tài)超圖相比，時序超圖（temporal hypergraphs，也稱為動態(tài)超圖 dynamic hypergraphs）不僅描述了超圖的結(jié)構(gòu)信息，還描述了其時間演化。

3 工具

在本節(jié)中，我們介紹用于超圖結(jié)構(gòu)模式的挖掘工具。3 通常，工具包括任何可用于定義或挖掘超圖結(jié)構(gòu)模式的事物。典型的工具包括零模型、結(jié)構(gòu)元素和結(jié)構(gòu)量。在圖 5 中，我們?yōu)橄挛膶⒁榻B的工具提供了一個概覽分類體系。

3.1 零模型

我們首先介紹零模型（null models）。零模型的概念對于顯著性檢驗 [141] 非常重要，在顯著性檢驗中，人們通常證明觀測到的現(xiàn)象在零模型中幾乎不可能發(fā)生，從而表明觀測到的現(xiàn)象是顯著的、非平凡的或令人驚訝的。對于成對圖，許多隨機(jī)圖模型已被用作零模型，包括 Erd?s-Rényi 模型 [49] 和 Chung-Lu 模型 [38]。零模型是超圖生成模型，通常 (1) 依賴于基本信息（例如，節(jié)點度和邊大?。?，并且 (2) 缺乏超出給定信息來復(fù)現(xiàn)真實模式的設(shè)計或機(jī)制。因此，它們很容易無法以全面的方式捕捉真實世界超圖的性質(zhì)。相比之下，第 5 節(jié)中作為“生成器”討論的超圖生成模型旨在有效地復(fù)現(xiàn)真實的結(jié)構(gòu)模式。此外，零模型和生成器服務(wù)于不同的目的。零模型主要用于與真實超圖進(jìn)行比較，例如在假設(shè)檢驗中或驗證在真實世界超圖中觀測到的模式的顯著性。相比之下，生成器旨在復(fù)現(xiàn)真實世界超圖中觀測到的真實模式，有助于解釋和理解產(chǎn)生這些模式的底層機(jī)制。

N1. 配置模型 (Configuration model)。配置模型旨在生成保留節(jié)點度分布和超邊大小分布的隨機(jī)超圖 [33]。這與成對圖（pairwise graphs）的配置模型不同，后者僅保留度分布。請注意，存在更先進(jìn)的超圖生成器，可被視為廣義配置模型。我們將在第 5 節(jié)介紹它們。在實踐中，人們可以使用存根匹配（stub matching），這種方法速度快，但可能會產(chǎn)生包含重復(fù)節(jié)點的超邊；或者使用成對重排（pairwise reshuffling），這種方法避免了包含重復(fù)節(jié)點的超邊，但速度較慢 [33]。

N2. 隨機(jī)填充模型 (Random filling model)。隨機(jī)填充模型是配置模型（見 N1）的一個簡單變體，它保留超邊大小分布，但不保留節(jié)點度分布。具體而言，給定一個超圖，它生成的超邊大小要么精確遵循原始超邊大小分布（要么是根據(jù)該分布進(jìn)行采樣）。對于每條超邊，其組成節(jié)點是從所有節(jié)點中均勻隨機(jī)采樣的。

3.2 結(jié)構(gòu)元素

結(jié)構(gòu)元素包括子結(jié)構(gòu)（例如，子超圖；見定義 2.1），以及它們之間的關(guān)系和相互作用。這些元素有助于我們揭示超圖的底層結(jié)構(gòu)，并且通常是定義結(jié)構(gòu)模式所依據(jù)的對象。

E1. 開三角與閉三角。三角形（即三節(jié)點團(tuán)）是成對圖（pairwise graphs）中的重要基元，因為它們被用于衡量各種結(jié)構(gòu)性質(zhì)，如社區(qū)結(jié)構(gòu) [157] 和傳遞性 [77]。在超圖的語境下，三角形可以分為開三角（open）和閉三角（closed），它們描述了三個節(jié)點之間不同種類的高階交互 [16]。如圖 6(b) 所示，在開三角中，每對節(jié)點都在一個或多個超邊中共現(xiàn)，但這三個節(jié)點不共享任何超邊。相反，在閉三角中，所有三個節(jié)點共同出現(xiàn)在至少一條超邊中。值得注意的是，這一概念也可以擴(kuò)展到高階。? 例如，考慮圖 6 中展示的超圖。在這個超圖中，節(jié)點 2、3 和 5 形成一個開三角，而節(jié)點 3、5 和 8 形成一個閉三角。重要的是，閉三角（要求至少有一條包含三個節(jié)點的超邊）無法在成對圖中定義，它們捕捉了超圖獨有的高階局部結(jié)構(gòu)。

E4. 時序超圖模體（TH-motifs）。為了描述三條相連時序超邊的時間動態(tài)，除了重疊模式外，還定義了 96 種時序超圖模體（TH-motifs）[103, 104]。從結(jié)構(gòu)角度來看，TH-motifs 遵循 H-motifs（見 E3）的概念，通過考慮 H-motifs 中使用的相同七個子集的空性。在時間方面，TH-motifs 是為在短時間間隔內(nèi)出現(xiàn)的三條時序超邊定義的，并考慮了時間局部性（temporal locality）。此外，TH-motifs 的定義納入了這三條時序超邊的相對到達(dá)順序，這使得能夠進(jìn)一步刻畫那些在靜態(tài) H-motifs 中無法區(qū)分的模式。

E5. 自我網(wǎng)絡(luò)（Ego-networks）。以單個節(jié)點為中心的交互通常通過構(gòu)建自我網(wǎng)絡(luò)（ego-network）[124] 來分析，其中中心節(jié)點被稱為自我節(jié)點（ego-node，或簡稱 ego）。自我網(wǎng)絡(luò)對其自我節(jié)點 u 與 u 的鄰居（稱為alter-nodes，或簡稱 alters）之間的交互進(jìn)行建模。Comrie 和 Kleinberg [40] 通過考慮不同范圍的交互，定義了三種類型的自我網(wǎng)絡(luò)（星型自我網(wǎng)絡(luò)、輻射型自我網(wǎng)絡(luò)和收縮型自我網(wǎng)絡(luò)）。

E10. 超圖社區(qū)（Hypergraph communities）。社區(qū)的概念（即內(nèi)部連接緊密且與外部節(jié)點連接相對稀疏的節(jié)點組）已在成對圖上得到廣泛研究 [57]。該概念已被擴(kuò)展至超圖 [2, 146, 179]。在超圖中，社區(qū)是指這樣的節(jié)點組：與屬于不同社區(qū)的節(jié)點相比，同一社區(qū)內(nèi)的節(jié)點更有可能共同形成超邊。聚類（Clustering）是將節(jié)點分組為社區(qū)的過程，已有許多算法被提出用于發(fā)現(xiàn)超圖中的社區(qū) [54, 80, 110]。

E11. 其他稠密子結(jié)構(gòu)（Other dense substructures）。人們提出了超圖中重要群體的各種定義，其中一個常見的類別是基于稠密子結(jié)構(gòu)來定義重要群體?；诠?jié)點子集具有高平均度（即高密度；見 Q10）的條件，人們提出了“稠密子超圖”的各種定義 [18, 72, 74, 96]。例如，Musciotto 等人 [129] 提出根據(jù)節(jié)點交互的一致性程度來定義稠密子結(jié)構(gòu)。最近，Veldt 等人 [165] 提出考慮具有不同 p 值的度序列的 p -范數(shù)，從而允許靈活地強(qiáng)調(diào)節(jié)點度，并將這一思想應(yīng)用于定義廣義稠密子圖。這一思想也可以推廣用于定義稠密子超圖。

3.3 結(jié)構(gòu)量

結(jié)構(gòu)量（Structural quantities）是用于定義進(jìn)而挖掘超圖模式的數(shù)值工具。通常，我們針對特定的結(jié)構(gòu)量，將真實世界超圖與由零模型生成的隨機(jī)超圖進(jìn)行比較，并展示顯著的數(shù)值差異。

Q3. 距離（Distances）。基于局部連通性信息（例如，游走和路徑；見 B3），人們提出了超邊中的各種距離度量。Vasilyeva 等人 [163] 以及 Li 和 Fadlallah [109] 提出了基于超圖上隨機(jī)游走的距離度量。Aksoy 等人 [4] 提出了一種考慮超圖中高階連通性的距離度量，Preti 等人 [138] 為該度量提出了一種快速近似算法。這些距離度量已被用于定義節(jié)點和邊的中心性分?jǐn)?shù) [51, 177]，并應(yīng)用于真實任務(wù)，如關(guān)鍵基因識別 [53]。

Q4. 中心性分?jǐn)?shù)（Centrality scores）。人們提出了各種分?jǐn)?shù)來衡量超圖中節(jié)點和邊的結(jié)構(gòu)中心性。除了基于距離的分?jǐn)?shù)（見 Q3），還有幾種基于鄰接/關(guān)聯(lián)/拉普拉斯矩陣（見 B2 和 B7）的特征值或特征向量的譜中心性分?jǐn)?shù)（spectral centrality scores）被提出 [15, 95, 161]。Xie 等人 [171] 利用引力模型引入了節(jié)點中心性，而 Hu 等人 [71] 基于馮·諾依曼熵（von Neumann entropy）定義了中心性。

Q7. 同配性（Assortativity）。同配性的概念量化了成對圖中相似節(jié)點相鄰的傾向 [133]。高同配性值表明，與不相似的節(jié)點相比，相似節(jié)點更有可能相鄰。相似性（similarity）通常是相對于節(jié)點度來定義的，即，如果節(jié)點具有相似的度，則被視為相似。Landry 和 Restrepo [97] 通過捕捉超邊內(nèi)節(jié)點間的度相關(guān)性如何偏離隨機(jī)情況下的預(yù)期，將同配性的概念擴(kuò)展到了超圖。

Q8. 單純性（Simpliciality）。由于超邊大小的靈活性，一條超邊可以封裝其他超邊（見 E8）。超圖單純性（simpliciality）通過評估大超邊包含所有可能的較小子集的程度，量化了這種層次結(jié)構(gòu)在超圖中展現(xiàn)得如何。具體而言，超圖的單純性是包含所有潛在子集的極大超邊數(shù)量與超邊總數(shù)的比率 [98]。較高的比率表明超圖由許多完全封裝了所有較小交互的超邊組成，反映了強(qiáng)烈的包含結(jié)構(gòu)。

Q9. 特征剖面（CPs）。為了更好地分析給定超圖的結(jié)構(gòu)性質(zhì)，我們可以同時考察多個感興趣的結(jié)構(gòu)模式（例如，H-motifs）來構(gòu)建該超圖的特征剖面（CP）。為此，第一步是獲取每個模式的數(shù)值頻率，例如，對于 H-motifs，我們可以簡單地計數(shù)它們的實例。然后，對于每個模式，通過將其在給定超圖中的頻率與在隨機(jī)超圖中的頻率進(jìn)行比較，我們可以確定其統(tǒng)計顯著性。最后，CP [102, 125] 是一個向量，它總結(jié)了整個超圖關(guān)于各種模式的結(jié)構(gòu)模式，允許在不同規(guī)模的可能變化的超圖之間進(jìn)行有意義的比較。

Q14. 模塊度（Modularity）。為了評估成對圖中的社區(qū)結(jié)構(gòu)強(qiáng)度（見 E10），Newman [132] 引入了模塊度（modularity）的概念。高模塊度值意味著與屬于不同社區(qū)的節(jié)點對相比，每個社區(qū)內(nèi)的節(jié)點對之間更有可能存在邊，因此它意味著強(qiáng)烈的社區(qū)結(jié)構(gòu) [19]。模塊度的概念已通過多種方式擴(kuò)展到了超圖 [62, 80, 131, 175]。模塊度測量了給定超圖中的社區(qū)結(jié)構(gòu)強(qiáng)度與參考隨機(jī)超圖之間的差異。值得注意的是，Chodrow [33] 考慮了具有各種參考隨機(jī)超圖定義的廣義模塊度。

4 結(jié)構(gòu)模式

在本節(jié)中，我們介紹真實世界超圖中的結(jié)構(gòu)模式（有關(guān)真實世界中公開可用且常用的超圖數(shù)據(jù)集列表，請參閱補充文檔 [1] 的表 1）。結(jié)構(gòu)模式是指在不同領(lǐng)域的真實世界超圖（及其所建模的真實世界系統(tǒng)）中反復(fù)出現(xiàn)的結(jié)構(gòu)特征 [28]。我們將結(jié)構(gòu)模式分類如下：

• 靜態(tài)模式與動態(tài)模式。靜態(tài)模式描述了靜態(tài)超圖或時序超圖（見 B8）單個快照的特征，而動態(tài)模式描述了時序超圖隨時間的演化。與關(guān)注結(jié)構(gòu)行為的靜態(tài)模式相比，動態(tài)模式提供了關(guān)于時間行為的額外見解，例如群體交互的形成與持續(xù)性。
• 節(jié)點級、超邊級、子超圖級與超圖級模式。模式的級別取決于用于定義該模式的基本元素。如果一個模式描述了單個節(jié)點（或超邊）的某些性質(zhì)，則將其歸類為節(jié)點級（相應(yīng)地，超邊級）模式。描述整個超圖性質(zhì)的模式被稱為超圖級模式。定義在節(jié)點和/或超邊的特定組合上的模式被歸類為子超圖級模式。

這兩種分類形式是正交的，通過它們的組合總共形成了八個子類別。在圖 9 中，我們提供了下文將要介紹的結(jié)構(gòu)模式分類體系的概覽。本節(jié)側(cè)重于描述觀察到的模式，而不深入探討其背后的具體原因。在第 5 節(jié)中，我們要通過簡單的機(jī)制復(fù)現(xiàn)這些模式，旨在揭示潛在的解釋。

4.1 靜態(tài)模式

我們首先介紹靜態(tài)模式。這些模式描述了節(jié)點和超邊的結(jié)構(gòu)性質(zhì)，以及真實世界超圖的整體特征。靜態(tài)模式不包括那些與時間變化相關(guān)的模式。

4.1.1 節(jié)點級模式。我們將調(diào)查與單個節(jié)點性質(zhì)相關(guān)的靜態(tài)模式，節(jié)點是超圖中的基本元素。

P1. 重尾度分布。真實世界超圖的度分布（見 B4）通常表現(xiàn)出重尾分布 [94]，大多是冪律分布（見 B5）。這表明少數(shù)節(jié)點參與了異常多的群體交互，而大多數(shù)節(jié)點僅參與少量交互。在成對圖上也觀察到了類似模式，? 它們部分由“富者愈富”[52] 解釋，這暗示了一個時間過程，其中度數(shù)較高的節(jié)點隨著時間的推移更有可能更快地增加其度數(shù)。少數(shù)高度數(shù)節(jié)點被稱為樞紐（hubs）[13]，它們在許多應(yīng)用中發(fā)揮著重要作用。

P2. 重尾超核度分布。對于節(jié)點，其度可以被視為一種中心性度量，其超核度（見 Q2）也是如此。Bu 等人 [22] 觀察到，在真實世界超圖中，節(jié)點的超核度通常表現(xiàn)出重尾分布（見 B5）。這意味著存在涉及少數(shù)節(jié)點的高度稠密子超圖，而大多數(shù)節(jié)點不屬于此類子超圖。核度（Coreness）是超核度在成對圖中的對應(yīng)概念，也已知在真實世界圖中通常表現(xiàn)出重尾分布 [155]。對于許多中心性分?jǐn)?shù)（見 Q4），雖然未明確討論重尾分布，但通常存在中心性值顯著高于其他節(jié)點的節(jié)點 [15, 71, 171]。

P3. 核心 - 邊緣結(jié)構(gòu)。許多真實世界超圖具有核心 - 邊緣結(jié)構(gòu)，其中我們有核心節(jié)點和邊緣節(jié)點。大量超邊應(yīng)在核心節(jié)點之間形成，而邊緣節(jié)點彼此之間連接不佳（即，不在許多超邊中共存），并且應(yīng)主要存在于至少有一個核心節(jié)點存在的超邊中 [5, 136, 162]。成對圖中的類似結(jié)構(gòu)也已被研究 [21]。

4.1.2 超邊級模式。我們現(xiàn)在將調(diào)查超邊級靜態(tài)模式。就像節(jié)點一樣，超邊也是超圖中的基本結(jié)構(gòu)元素（見 B1）。因此，檢查超邊級模式使能夠從不同角度洞察真實世界超圖的結(jié)構(gòu)特征。

P4. 重尾大小分布。成對圖與超圖之間的一個根本區(qū)別在于，超邊具有可變的大小，連接任意數(shù)量的節(jié)點，而成對圖中的邊只能連接兩個節(jié)點。因此，超邊的一個關(guān)鍵性質(zhì)是其大小，即在一條超邊中共現(xiàn)的節(jié)點數(shù)量。真實世界超圖中超邊大小的分布往往遵循重尾分布 [94]（見 B5）。這意味著存在大量小尺寸超邊，而極大超邊也往往存在。

P5. 高同質(zhì)性。超邊的同質(zhì)性（見 Q5）衡量超邊中的節(jié)點在結(jié)構(gòu)上的相似程度。Lee 等人 [101] 觀察到，真實世界超圖中的超邊往往比通過 HyperCL 模型（見 E3）獲得的隨機(jī)超圖中的超邊具有顯著更高的同質(zhì)性。這一模式意味著真實世界超邊更有可能由結(jié)構(gòu)相似的節(jié)點填充，而不是隨機(jī)選擇的節(jié)點。

P6. 實質(zhì)性封裝。LaRock 和 Lambiotte [99] 通過與隨機(jī)超圖比較，研究了真實世界超圖中的封裝（見 E8），其中相同大小的超邊被分組在一起，并且每個超邊組內(nèi)的節(jié)點標(biāo)簽被隨機(jī)排列。這保持了相同大小超邊之間的重疊模式，同時隨機(jī)化了不同大小超邊之間的重疊模式。他們觀察到，與相應(yīng)隨機(jī)超圖中的超邊相比，真實世界超圖中的超邊往往表現(xiàn)出顯著更高程度的封裝（即，封裝更頻繁地發(fā)生）。這一模式突出了真實世界超圖中超邊之間高互連性的一個方面。

4.1.3 子超圖級模式我們現(xiàn)在將調(diào)查子超圖級靜態(tài)模式。子超圖級模式是指那些既不涉及單個節(jié)點/超邊，也不涉及整個超圖的模式。相反，它們是定義在節(jié)點和/或超邊的組合上的，例如，節(jié)點的子集和超邊對。

P7. 重尾群組度分布。我們已經(jīng)看到真實世界超圖中存在（單個）節(jié)點度的重尾分布（見 P1）?，F(xiàn)在我們深入探討真實世界超圖中節(jié)點群組的度分布（見 Q1）。群組度的分布已被幾位研究人員研究過：

P8. 重尾交集大小分布。我們已經(jīng)看到真實世界超圖中（單個）超邊大小遵循重尾分布（見 P4）。我們現(xiàn)在將范圍擴(kuò)展到超邊對并研究超邊交集。研究超邊交集使我們能夠從不同角度研究超圖的連通性。Kook 等人 [94] 觀察到，真實世界超圖中超邊對的交集大小分布遵循重尾分布。此外，他們還觀察到真實世界超圖中的一些超邊對共享大量公共節(jié)點（即，大交集），這在由隨機(jī)填充模型（見 N2）生成的隨機(jī)超圖中是無法觀察到的。

P9. 實質(zhì)性的高階連通性。Kim 和 Goh [87] 從另一個角度研究了超邊交集。他們提出構(gòu)建圖來描述具有不同閾值 m 的超圖的高階連通性（見 E7），其中每條超邊在構(gòu)建的圖中表示為一個節(jié)點，如果兩條對應(yīng)的超邊共享至少 m 個公共節(jié)點，則構(gòu)建圖中的兩個節(jié)點相鄰。他們觀察到，真實世界超圖傾向于在較高的 m 值下保持大的連通分量，而在通過配置模型（見 E1）獲得的隨機(jī)超圖中則不然，這表明真實世界超圖中存在實質(zhì)性的超邊交集，這與上述觀察（見 P8）一致。

P10. 高傳遞性。幾位研究人員研究并擴(kuò)展了超圖中的傳遞性（見 Q6），從不同角度觀察到真實世界超圖中的高傳遞性：

這些模式通常意味著，如果（群組）節(jié)點共享公共鄰居，它們更有可能在超邊中共同出現(xiàn)。

P11. 密集重疊的自我網(wǎng)絡(luò)。超圖的密度（見 Q10）或重疊度（見 Q11）衡量了其超邊相互重疊的程度。Lee 等人 [101] 觀察到，在星型自我網(wǎng)絡(luò)（見 E5）中，真實世界超圖中星型自我網(wǎng)絡(luò)的密度和重疊度顯著大于通過 HYPERCL 模型（見 E3）獲得的隨機(jī)超圖中的密度和重疊度。這意味著真實世界超圖中的超邊比隨機(jī)對應(yīng)物中的超邊具有更多的局部重疊，這也與高傳遞性相關(guān)（見 P10）。

P12. 社區(qū)結(jié)構(gòu)。社區(qū)（見 E10）在真實世界超圖中普遍存在，這通過使用擴(kuò)展的（歸一化）割（見 Q12）[67, 110, 164, 166]、電導(dǎo)（見 Q13）[68, 159, 164] 和模塊度（見 Q14）[62] 量化的強(qiáng)社區(qū)結(jié)構(gòu)得以證明。Contisciani 等人 [41] 觀察到真實世界超圖中重疊社區(qū)的普遍性，并提出了一種統(tǒng)計方法來檢測此類社區(qū)。Lotito 等人 [119] 進(jìn)一步觀察到真實世界超圖中的層次化（即社區(qū)被進(jìn)一步劃分為更小的社區(qū)）和多尺度（即社區(qū)存在于各種尺度上）社區(qū)結(jié)構(gòu)。值得注意的是，Torres 等人 [160] 指出，相同原始數(shù)據(jù)的不同超圖表示可能會展示不同的社區(qū)結(jié)構(gòu)。

P13. 稠密子超圖。真實世界超圖通常表現(xiàn)出稠密子結(jié)構(gòu)（見 E11），其特征為高密度（見 Q10）或高重疊度（見 Q11）。它們的存在與同一組（或相似）節(jié)點在多個超邊中重復(fù)共現(xiàn)有關(guān) [17, 101]。一些研究表明，與隨機(jī)超圖相比，真實世界超圖傾向于表現(xiàn)出更稠密的子超圖 [33, 101]。

P14. 模式的強(qiáng)表征能力。幾種度量與模式可以作為超圖的有效表征工具。具體而言，真實世界超圖來自不同的領(lǐng)域（或字段），并且通常觀察到同一領(lǐng)域內(nèi)的超圖在某些度量和模式方面是相似的，而不同領(lǐng)域中的超圖則相對不相似。

• Benson 等人 [16] 使用開三角和閉三角（見 E1）的計數(shù)來表征真實世界超圖。具體而言，開三角數(shù)量與閉三角數(shù)量的比率是區(qū)分不同領(lǐng)域超圖的有用度量。
• Lotito 等人 [118] 使用高階網(wǎng)絡(luò)模態(tài)（HO-motifs；見 E2）的頻率來表征真實世界超圖。具體而言，同一領(lǐng)域內(nèi)的超圖表現(xiàn)出相似的 HO-motifs 歸一化計數(shù)分布，而來自不同領(lǐng)域的超圖則表現(xiàn)出顯著差異。Juul 等人 [79] 觀察到關(guān)于 m -模式（見 E2）分布的類似現(xiàn)象。
• Lee 等人 [102] 使用 H-模體（見 E3）構(gòu)建真實世界超圖的特征剖面（CPs；見 Q9）。此類 CPs 基于 H-模體總結(jié)局部結(jié)構(gòu)模式，并且基于 CPs 可以清晰地區(qū)分來自不同領(lǐng)域的真實世界超圖。
• LaRock 和 Lambiotte [99] 觀察到，來自同一領(lǐng)域的超圖表現(xiàn)出相似的與封裝相關(guān)的模式（例如，封裝程度如何隨超邊大小變化），而此類模式在不同領(lǐng)域中則有所不同。此外，Landry 等人 [98] 觀察到，同一領(lǐng)域內(nèi)的超圖表現(xiàn)出相似水平的單純性（見 Q8），而來自不同領(lǐng)域的超圖則顯示不同水平的單純性。

結(jié)構(gòu)模式的強(qiáng)大表征能力進(jìn)一步驗證了它們作為分析真實世界超圖工具的有用性和意義。此外，結(jié)構(gòu)模式還可用作結(jié)構(gòu)特征 [16, 102–105]，用于具有各種下游應(yīng)用的機(jī)器學(xué)習(xí)（見第 6.2 節(jié)）。

4.1.4 超圖級模式。我們現(xiàn)在將調(diào)查超圖級靜態(tài)模式。超圖級模式涉及超圖作為整體的性質(zhì)，檢查它們使我們對真實世界超圖獲得宏觀見解。

P15. 偏斜奇異值分布。真實世界超圖的不同矩陣表示的奇異值分解（SVD）可以提供關(guān)于超圖結(jié)構(gòu)性質(zhì)的重要見解。具體而言，檢查奇異值分布的偏斜性可以提供關(guān)于超圖內(nèi)底層層次結(jié)構(gòu)和社區(qū)結(jié)構(gòu)（見 P12）的信息，正如研究人員對成對圖所做的那樣 [46, 85, 150]。

• 對于真實世界超圖的關(guān)聯(lián)矩陣（見 B2），已觀察到偏斜奇異值分布（即，當(dāng)我們按降序排列奇異值時，值顯著下降）[94]。
• Do 等人 [45] 考慮了一種使用多級分解（見 E6）的不同矩陣表示方式，并觀察到真實世界超圖的每個 k 層分解圖的鄰接矩陣的奇異值是偏斜的。

奇異值的大小反映了對應(yīng)節(jié)點（對于關(guān)聯(lián)矩陣）或節(jié)點組（對于多級分解圖的鄰接矩陣）的結(jié)構(gòu)重要性（例如，影響力）。因此，上述觀察表明，真實世界超圖中的一些節(jié)點或節(jié)點組比其他節(jié)點或節(jié)點組普遍得多且更具影響力。

4.2 動態(tài)模式

我們現(xiàn)在介紹動態(tài)模式（dynamic patterns）。給定時序超圖，動態(tài)模式描述了超圖內(nèi)部及超圖本身的時間演化或變化。

4.2.1 超邊級模式。我們現(xiàn)在將調(diào)查超邊級動態(tài)模式（hyperedge-level dynamic patterns），描述超邊出現(xiàn)之間的時間關(guān)系。

P16. 頻繁的超邊重復(fù)。過去事件的重演在各種系統(tǒng)中很普遍。超邊重復(fù)（Hyperedge repetition），即過去超邊的重演，也在真實世界超圖的演化中被觀察到。

• Benson 等人 [17] 觀察到，許多超邊在真實世界時序超圖的演化過程中重復(fù)出現(xiàn)。
• Lee 和 Shin [103, 104] 進(jìn)一步觀察到，真實世界時序超圖中超邊重復(fù)次數(shù)的分布通常遵循重尾分布。
• Lee 和 Shin [103, 104] 還觀察到，與隨機(jī)超圖相比，超邊重復(fù)在真實世界超圖中發(fā)生得更頻繁（即，同一條超邊兩次出現(xiàn)之間的時間間隔更短）。隨機(jī)超圖是使用 HYPERCL（見 N3）生成的，且超邊的時間戳是從原始時間戳隨機(jī)重排的。
• Cencetti 等人 [27] 使用了突發(fā)行為（bursty behaviors，即同一條超邊在短時間間隔內(nèi)重復(fù)多次）的概念，并觀察到突發(fā)行為在真實世界超圖中比在通過隨機(jī)打亂相同大小的時序超邊時間戳獲得的隨機(jī)超圖中更為普遍。

上述工作的作者普遍觀察到，與隨機(jī)對應(yīng)物相比，超邊重復(fù)在真實世界超圖中更為常見，尤其是對于大超邊。

P17. 時間局部性。在成對圖演化中，時間局部性（temporal locality）指的是新交互更類似于近期交互而非較早交互的傾向 [100, 122]。對真實世界超圖中超邊的結(jié)構(gòu)相似性與其出現(xiàn)時間之間關(guān)系的考察也揭示了時間局部性的存在。

除了整個超邊的重復(fù)行為（見 P16），關(guān)于超邊內(nèi)子集重復(fù)的時間局部性，為時序超圖演化提供了獨特的見解。

P18. 時間強(qiáng)化。隨著時序超圖的演化，新超邊的組成受到先前超邊的影響。時間強(qiáng)化（temporal reinforcement）現(xiàn)象描述了先前超邊如何影響新超邊的組成。具體而言，Cencetti 等人 [27] 觀察到，如果一組節(jié)點在過去曾在多條超邊中共同出現(xiàn)，那么同一組節(jié)點在未來更有可能繼續(xù)在某些超邊中共同出現(xiàn)，并且隨著過去共現(xiàn)期長度的增加，這種可能性也會增加。這種模式使我們能夠分析群體交互的時間穩(wěn)定性。

4.2.2 子超圖級模式。我們現(xiàn)在將調(diào)查子超圖級動態(tài)模式。此類模式描述了節(jié)點和/或超邊組合的時間行為。

P19. 冪律持續(xù)性。在真實世界時序超圖中，同一組節(jié)點可能會隨時間推移在多個超邊中共同出現(xiàn)。一組節(jié)點的持續(xù)性（persistence）量化了它們隨時間共同出現(xiàn)的一致性（見 Q15）。Choo 和 Shin [37] 觀察到，在真實世界時序超圖中，持續(xù)性（具體而言，即持續(xù)性值與具有該持續(xù)性值的節(jié)點組數(shù)量之間的關(guān)系）通常遵循冪律分布。該模式意味著總體而言，大多數(shù)節(jié)點組具有較低的持續(xù)性值，但也存在少數(shù)持續(xù)性異常高的節(jié)點組。這種模式與上述超邊級模式（見 P16-P18）相關(guān)。然而，通過考慮超邊內(nèi)的組成節(jié)點組而非整個超邊，它提供了一個獨特的視角。

P20. 單純閉包。單純閉包（simplicial closure）的概念將成對圖中的三元閉包（triadic closure）[156] 概念擴(kuò)展到了超圖，暗示了閉三角（或其高階對應(yīng)物）形成的可能機(jī)制（見 E1）。Benson 等人 [16] 考察了真實世界超圖中三個節(jié)點之間閉三角的出現(xiàn)（即單純閉包事件的發(fā)生）與其在團(tuán)擴(kuò)展（見 B6）中的成對連接之間的關(guān)系。值得注意的是，他們通過計算團(tuán)擴(kuò)展中的邊重復(fù)次數(shù)考慮了邊權(quán)重，即他們計算了每對節(jié)點共同出現(xiàn)的超邊數(shù)量。他們觀察到了單純閉包的存在，即，隨著團(tuán)擴(kuò)展中考慮節(jié)點之間的連接數(shù)量和/或權(quán)重的增加，單純閉包事件的可能性趨于增加。這種模式可以很容易地用于超邊預(yù)測 [16]，擴(kuò)展了三元閉包在鏈路預(yù)測 [73] 中的效用。

P21. 自我網(wǎng)絡(luò)中的時間局部性。識別真實世界超圖中自我網(wǎng)絡(luò)（見 E5）的時間增長模式，是理解和預(yù)測圍繞單個節(jié)點的群體交互動態(tài)的重要一步。正如單個超邊的演化表現(xiàn)出時間局部性（見 P17）一樣，自我網(wǎng)絡(luò)的演化也表現(xiàn)出時間局部性。

• Comrie 和 Kleinberg [40] 觀察到，在自我網(wǎng)絡(luò)內(nèi)部，時間戳更接近的超邊也傾向于表現(xiàn)出結(jié)構(gòu)相似性，即共享大量節(jié)點。具體而言，他們通過自我網(wǎng)絡(luò)中時間連續(xù)邊的平均交集大小（見 Q16）來衡量結(jié)構(gòu)相似性。此外，他們觀察到隨著自我網(wǎng)絡(luò)隨時間演化和增長，這種結(jié)構(gòu)相似性會降低。
• 他們還從 alter 網(wǎng)絡(luò)（見 E5）的角度探索了時間局部性，并觀察到 alter 網(wǎng)絡(luò)內(nèi)兩條連續(xù)超邊之間的平均時間間隔短于通過隨機(jī)打亂超邊順序獲得的隨機(jī)超圖中的時間間隔。

與整個超圖中超邊的時間局部性（P17）相比，自我網(wǎng)絡(luò)內(nèi)的時間局部性為局部超圖演化提供了獨特的見解。

P22. 自我網(wǎng)絡(luò)的人擇原理。回想一下，輻射型和收縮型自我網(wǎng)絡(luò)可能包含僅由不包含自我節(jié)點的 alter 節(jié)點組成的超邊（見 E5）。因此，此類自我網(wǎng)絡(luò)的形成甚至可能在自我節(jié)點介入之前就已經(jīng)開始。Comrie 和 Kleinberg [40] 探索了自我節(jié)點進(jìn)入其自身自我網(wǎng)絡(luò)的時間點。

• 在收縮型自我網(wǎng)絡(luò)中，我們經(jīng)常觀察到自我節(jié)點的到達(dá)時間與自我網(wǎng)絡(luò)的大小之間存在近乎完美的正相關(guān)關(guān)系。具體而言，如果自我網(wǎng)絡(luò)較大，自我節(jié)點更有可能較晚到達(dá)。此外，與通過隨機(jī)打亂超邊順序獲得的隨機(jī)網(wǎng)絡(luò)相比，自我節(jié)點傾向于在真實世界的收縮型自我網(wǎng)絡(luò)中較晚到達(dá)。
• 在輻射型自我網(wǎng)絡(luò)中經(jīng)常注意到一種類似但相對較弱的趨勢。在輻射型自我網(wǎng)絡(luò)中，即使它們具有相當(dāng)大的規(guī)模，自我節(jié)點通常在引入第五條超邊之前出現(xiàn)。此外，正如在收縮型自我網(wǎng)絡(luò)中一樣，與通過隨機(jī)打亂超邊順序獲得的隨機(jī)網(wǎng)絡(luò)相比，自我節(jié)點傾向于在真實世界的輻射型自我網(wǎng)絡(luò)中較晚到達(dá)。

這些模式為自我網(wǎng)絡(luò)構(gòu)建的底層機(jī)制提供了見解，被稱為自我網(wǎng)絡(luò)的人擇原理（anthropic principles），這類似于人類研究史前歷史的方式。

P23. 自我網(wǎng)絡(luò)的新穎率模式。自我網(wǎng)絡(luò)中新添加的超邊可能包含新穎節(jié)點（novel nodes），即此前未在自我網(wǎng)絡(luò)中出現(xiàn)過的節(jié)點。此類新穎節(jié)點的數(shù)量被稱為新穎率（novelty rate）。Comrie 和 Kleinberg [40] 調(diào)查了新穎率如何隨自我網(wǎng)絡(luò)演化而變化。

• 在星型和輻射型自我網(wǎng)絡(luò)中，平均新穎率逐漸下降直到某一點。過了那一點后，新穎率保持幾乎恒定（對于輻射型自我網(wǎng)絡(luò)）甚至顯示出增加趨勢（對于星型自我網(wǎng)絡(luò)）。
• 在收縮型自我網(wǎng)絡(luò)中，平均新穎率隨時間持續(xù)下降。

此類新穎節(jié)點總體上難以預(yù)測，且與許多實際問題相關(guān)，例如冷啟動 [151]。理解此類節(jié)點出現(xiàn)背后的機(jī)制在理論和實踐上均具有重要意義。

P24. TH-模體的強(qiáng)表征能力。時序超圖模體（TH-motifs；見 E4）是靜態(tài)超圖中定義的超圖模體（H-motifs）概念的時間擴(kuò)展。從給定時序超圖中每種 TH-模體（共 96 種）的實例計數(shù)中，時序超圖的結(jié)構(gòu)和時間模式可以總結(jié)為一個 96 維向量，稱為關(guān)于該超圖 TH-模體的特征剖面（CP；見 Q9）。利用 CPs，可以有效地區(qū)分來自不同領(lǐng)域的時序超圖，而且這種區(qū)分比僅使用靜態(tài)信息通過 H-模體實現(xiàn)的區(qū)分更為清晰 [103, 104]。這證明了 TH-模體通過捕捉時間和結(jié)構(gòu)模式來表征時序超圖的有效性。

4.2.3 超圖級模式。我們現(xiàn)在將調(diào)查超圖級動態(tài)模式。這些模式描述了超圖作為整體的特征隨時間如何變化。

P25. 重疊減少。Kook 等人 [94] 調(diào)查了真實世界時序超圖中超邊的結(jié)構(gòu)互連性隨時間如何演化。具體而言，他們觀察到所有超邊對中相交超邊對的比例隨時間趨于減少。這一觀察結(jié)果與以下發(fā)現(xiàn)一致：隨著超邊出現(xiàn)之間的時間間隔增加，超邊之間的相似性會減弱（見 P17）。

P27. 直徑收縮。直徑收縮（Shrinking diameter）是在真實世界成對圖中觀察到的另一種模式 [108]，其中有效直徑（見 Q17）通常隨著圖的增長而減小。這種趨勢可以自然地擴(kuò)展到超圖，Kook 等人 [94] 確實在真實世界超圖的演化中觀察到了這種趨勢。這表明隨著真實世界超圖規(guī)模的擴(kuò)大，信息或影響力可能會傳播得更快。

5 生成器

在本節(jié)中，我們介紹超圖生成器。我們重點關(guān)注基于真實世界超圖性質(zhì)的生成器。超圖生成器在大規(guī)模建模中起著至關(guān)重要的作用，它們通過生成模仿真實世界超圖結(jié)構(gòu)的合成數(shù)據(jù)集，促進(jìn)了基準(zhǔn)測試和可擴(kuò)展性測試。在圖 10 中，我們?yōu)橄挛膶⒁懻摰纳善魈峁┝朔诸愺w系。我們將感興趣的生成器分類如下：

• 全超圖和子超圖生成器。全超圖生成器生成完整的超圖，而子超圖生成器生成超圖的部分。
• 靜態(tài)和動態(tài)生成器。靜態(tài)生成器生成靜態(tài)超圖，而動態(tài)生成器生成動態(tài)圖（即時序超圖；見 B8）。值得注意的是，在某些工作中，作者并未明確說明所提出的生成器是生成靜態(tài)超圖還是動態(tài)超圖。對于此類情況，我們根據(jù)生成過程是否可以被解釋為具有時間依賴性的演化過程來對生成器進(jìn)行分類。例如，基于優(yōu)先依附（preferential attachment）的生成器可以自然地被解釋為演化過程，而使用節(jié)點打亂或重連的生成器則不能。

這兩種分類是正交的，因此我們總共有四個子類別。 對于每個生成器，我們提供其算法過程的摘要以及直觀理解和討論（如有）。有關(guān)每個生成器的詳細(xì)輸入和輸出，請參見表 2。

5.1 全超圖生成器

我們首先介紹全超圖生成器。全超圖生成器以一些超圖統(tǒng)計量作為輸入（通常帶有一些額外的模型特定超參數(shù)），并輸出一個完整的超圖，該超圖旨在保留真實世界超圖中的一些結(jié)構(gòu)模式。

5.1.1 靜態(tài)生成器。我們將在下面介紹靜態(tài)全超圖生成器。

G1. HYPERLAP。HYPERLAP 由 Lee 等人 [101] 提出，基于真實世界超圖中超邊的重疊模式（見 P5 和 P11）。它可以看作是 HYPERCL（見 N3）的多級擴(kuò)展，其中該擴(kuò)展有助于復(fù)現(xiàn)重疊模式。

• 算法摘要：節(jié)點被組織在多個層級中，其中每個層級包含所有節(jié)點，但粒度不同。具體而言，從上到下，某一層級的每個群組在下一層級被劃分為兩個群組，因此更深（即更接近底部）的層級包含更多的群組。在生成每條超邊時，HYPERLAP 首先采樣一個層級，然后在該層級中選擇一個群組。所選群組中的節(jié)點被采樣以填充該超邊，采樣的概率與度成正比。
• 直觀理解：由于超邊是基于群組生成的，同一群組內(nèi)的節(jié)點在結(jié)構(gòu)上是相似的，這使得生成的超邊具有高同質(zhì)性（見 P5）。由于每個自我網(wǎng)絡(luò)傾向于包含結(jié)構(gòu)相似的節(jié)點，這些節(jié)點在許多超邊中共同出現(xiàn)，因此每個自我網(wǎng)絡(luò)的密度（見 Q10）和重疊度（見 Q11）自然產(chǎn)生（見 P11）。最后，位于深層（即接近底部）小群組中的節(jié)點對或節(jié)點三元組也屬于所有較淺層（即接近頂部）層級的同一群組，因此它們被更頻繁地選擇共同形成超邊。因此，更多的超邊包含并在這些節(jié)點對或節(jié)點三元組處重疊，這意味著節(jié)點對和節(jié)點三元組的度分布呈現(xiàn)偏斜的重尾分布（見 P7）。
• Lee 等人 [101] 還提出了 HYPERLAP+，其在 HYPERLAP 的基礎(chǔ)上額外包含了一個自動超參數(shù)選擇方案。

G2. CIGAM。CIGAM（continuous influencer-guided attachment model，連續(xù)影響者引導(dǎo)依附模型），由 Papachristou 和 Kleinberg [136] 提出，旨在捕捉真實世界超圖中的核心 - 邊緣結(jié)構(gòu)（見 P3）。

• 算法摘要：每個節(jié)點被分配一個聲望值（prestige value），并且每條潛在的超邊被獨立生成，其中采樣概率由組成節(jié)點的聲望值決定。
• 直觀理解：具有高聲望值的節(jié)點被視為“核心節(jié)點”。每條生成的超邊很可能包含核心節(jié)點，這意味著一種核心 - 邊緣結(jié)構(gòu)（見 P3）。為了降低似然估計中的計算復(fù)雜度，僅考慮每條潛在超邊中的最大聲望值。
• 為節(jié)點分配聲望值的想法可以與其他超圖生成器結(jié)合，以捕捉更多性質(zhì)，例如模體（見 E2 和 E3）。

G3. HYPER-dK。由 Nakajima 等人 [130] 提出的 HYPER-dK 系列是一族超圖參考模型，它擴(kuò)展了成對圖的 dK 系列 [121]。它們生成保留節(jié)點和超邊給定局部性質(zhì)（例如，P1 和 P7）的超圖。

G5. HSBM。HSBM（hypergraph stochastic block model，超圖隨機(jī)塊模型），由 Ghoshdastidar 和 Dukkipati [61] 提出，可以生成社區(qū)結(jié)構(gòu)（見 E10 和 P12），并且對于社區(qū)發(fā)現(xiàn)很有用。

• 算法摘要：節(jié)點被劃分為多個群組（即社區(qū)），并且邊根據(jù)作為節(jié)點成員組合函數(shù)的概率生成。
• 直觀理解：社區(qū)結(jié)構(gòu)的強(qiáng)度可以通過該函數(shù)直接調(diào)整。例如，我們可以通過增加同一群組內(nèi)節(jié)點的邊概率來生成具有強(qiáng)社區(qū)結(jié)構(gòu)的超圖。
• 更廣義的模型，例如超圖審查塊模型（hypergraph censored block model）[2]、子超圖隨機(jī)塊模型 [112]、超圖度校正隨機(jī)塊模型（hypergraph degree-corrected stochastic block model）[34] 以及超圖同步生成器（hypergraph simultaneous generators）[137]，也已被考慮。

5.1.2 動態(tài)生成器。我們現(xiàn)在將介紹動態(tài)全超圖生成器。

G8. HYPERPA。HYPERPA 由 Do 等人 [45] 提出，基于關(guān)于 k k 層分解圖（見 P7、P10 和 P15）的觀察。它是優(yōu)先依附（preferential attachment）[12] 的群組級擴(kuò)展，其核心思想是新節(jié)點更有可能依附于現(xiàn)有的高度數(shù)節(jié)點，使得“富”節(jié)點更“富”。例如，合著過許多論文的研究人員很可能擁有共同的興趣，這將導(dǎo)致未來更多的合作。

• 算法摘要：對于每個節(jié)點 v v，HYPERPA 首先采樣“新”超邊的數(shù)量。對于每條“新”超邊，HYPERPA 采樣一個超邊大小 s s，然后使用優(yōu)先依附以與群組度（見 Q1）成正比的概率將節(jié)點 v v 依附到一個大小為 ( s ? 1 ) 的群組上。
• 直觀理解：眾所周知，優(yōu)先依附能夠產(chǎn)生具有偏斜度分布（見 P1）、高聚類系數(shù)、小直徑等特征的圖。直觀地看，HYPERPA 也產(chǎn)生具有推廣到超圖的類似模式的超圖（見 P7、P10 和 P15）。值得注意的是，HYPERPA 中的優(yōu)先依附是以群組方式進(jìn)行的，這產(chǎn)生了偏斜的群組（以及單個）度（見 P1 和 P7）。
• HYPERPA 以動態(tài)方式生成超邊。然而，超邊的時間戳在觀察和評估中均未考慮。將觀察和評估擴(kuò)展到時序超圖將是一個有趣的未來方向。有關(guān)超圖中優(yōu)先依附的更一般討論，請參閱 [144]。

G9. HMPA。HMPA（high-modularity preferential attachment，高模塊度優(yōu)先依附），由 Giroire 等人 [62] 提出，也使用了優(yōu)先依附的思想。該生成器還考慮了具有高模塊度（見 Q14）的社區(qū)結(jié)構(gòu)（見 P12），這是在真實世界超圖中觀察到的。

• 算法摘要：節(jié)點被顯式劃分為社區(qū)（見 E10）。在每個時間步，要么生成一個新節(jié)點并將其依附到一個社區(qū)，要么利用現(xiàn)有節(jié)點生成一條新超邊。在生成每條新超邊時，HMPA 首先采樣一組社區(qū)，然后確定要從每個社區(qū)中選擇的節(jié)點數(shù)量。在每個社區(qū)內(nèi)，節(jié)點以優(yōu)先依附的方式按照與其度成正比的概率被選擇。
• 直觀理解：社區(qū)結(jié)構(gòu)是通過劃分節(jié)點直接施加的。人們可以操縱采樣概率以鼓勵更多由少數(shù)社區(qū)甚至單個社區(qū)中的節(jié)點組成的超邊，這意味著高模塊度。
• 在這個生成器中，社區(qū)是不相交的，且社區(qū)成員資格是固定的。擁有更靈活的社區(qū)結(jié)構(gòu)（例如重疊社區(qū) [26, 41]（見 P12））可能是有益的。

G10. HYPERFF。HYPERFF 由 Kook 等人 [94] 提出，基于關(guān)于真實世界超圖演化的觀察（見 P25、P26 和 P27）。正如其名所示，該生成器的靈感來自于成對圖上的森林火災(zāi)模型（forest fire model）[108]。

• 算法摘要：在每個時間步，一個新節(jié)點加入，并且選擇一個現(xiàn)有節(jié)點作為大使節(jié)點（ambassador node），“森林火災(zāi)”由此開始。森林火災(zāi)通過現(xiàn)有的超邊隨機(jī)蔓延。當(dāng)它終止時，從每個被“燒毀”的節(jié)點開始一場新的森林火災(zāi)，并且本輪被燒毀的節(jié)點與新節(jié)點共同形成一條超邊。
• 直觀理解：作者的動機(jī)來自于合著網(wǎng)絡(luò)中的真實世界場景。在每個時間步，新節(jié)點代表加入研究社區(qū)的新學(xué)生，大使節(jié)點代表新學(xué)生的導(dǎo)師，而類森林火災(zāi)的過程代表了研究人員相互合作的真實世界過程。
• Ko 等人 [92] 還開發(fā)了 HYPERFF 的一個簡化且數(shù)學(xué)上易于處理的版本，這導(dǎo)出了關(guān)于期望超邊大小、超邊數(shù)量和節(jié)點度的閉式方程。然而，簡化版本在復(fù)現(xiàn)真實世界模式方面的能力較弱，特別是關(guān)于直徑收縮（見 P27）的模式。
• HYPERFF 側(cè)重于以宏觀方式保留真實世界超圖模式。進(jìn)一步考慮微觀模式（例如超邊排序或重復(fù)）將是一個有趣的未來方向。

G11. THERA。THERA（transitive hypergraph generator，傳遞性超圖生成器），由 Kim 等人 [88] 提出，基于關(guān)于真實世界超圖傳遞性的觀察（見 P10）。

• 算法摘要：節(jié)點被組織在具有多個層級的層次結(jié)構(gòu)（具體而言，是一棵樹）中，其中節(jié)點被劃分為不相交的層級，更深（即更接近葉子）的層級包含更多節(jié)點，并且每個層級的節(jié)點被分割成不相交的群組。群組大小在不同層級間是相同的，因此在更深層級有更多的群組。在生成超邊時，以某種概率，THERA 在群組內(nèi)局部生成它，而以剩余概率，THERA 在整個節(jié)點集內(nèi)全局生成它，其中較淺層級的節(jié)點更有可能被選擇。
• 直觀理解：社區(qū)結(jié)構(gòu)（見 E12）自然地產(chǎn)生了高傳遞性（見 P10）。層次結(jié)構(gòu)允許不同層級的節(jié)點以不同的概率被選擇，這意味著現(xiàn)實的偏斜度分布，具體而言是大量的小度數(shù)節(jié)點和少量的大度數(shù)節(jié)點（見 P1）。
• THERA 的超參數(shù)必須手動選擇。如果有一個能自動選擇超參數(shù)的擬合算法將是理想的。

5.2 子超圖生成器

現(xiàn)在，我們介紹子超圖生成器。與全超圖生成器不同，子超圖生成器輸出給定超圖的一個子圖，同時保留某些性質(zhì)。

5.2.1 靜態(tài)生成器。我們將在下面介紹靜態(tài)子超圖生成器。

G13. MiDaS。MiDaS（minimum degree biased sampling of hyperedges，超邊的最小度偏差采樣），由 Choe 等人 [35, 36] 提出，旨在生成給定超邊（注：原文此處疑似筆誤，上下文應(yīng)為超圖）的代表性子超圖，其中給定超圖的性質(zhì)（例如，P1、P4、P7、P8 和 P15）得到良好保留。

• 算法摘要：在 MiDaS 中，超邊被逐個采樣。每條超邊的采樣概率由其中的最小節(jié)點度決定。使用訓(xùn)練好的線性回歸模型來自動調(diào)節(jié)對高度數(shù)節(jié)點的偏差程度。
• 直觀理解：MiDaS 通過引入關(guān)于節(jié)點度的偏差擴(kuò)展了隨機(jī)超邊采樣。MiDaS 的設(shè)計動機(jī)來自兩個觀察：(1) 隨機(jī)超邊采樣總體上效果良好，但無法生成具有高連通性（見 B3）和足夠高度數(shù)節(jié)點（見 P1）的子超圖，(2) 保留度分布與保留其他幾個超圖性質(zhì)密切相關(guān)。
• 雖然 MiDaS 僅直接考慮關(guān)于節(jié)點度的偏差（見 P1），但它保留了許多其他超圖性質(zhì)（例如，P4、P7、P8 和 P15）。
• 研究保留節(jié)點度與保留其他超圖性質(zhì)之間強(qiáng)聯(lián)系背后的深層原因?qū)⒑苡腥?。此外，考慮時間信息（如果可用）可能有利于性能。

G14. HRW。HRW（hybrid random walk，混合隨機(jī)游走），由 Zhang 等人 [182] 提出，使用通過超圖上的隨機(jī)游走進(jìn)行采樣。采樣的（即訪問的）節(jié)點和超邊用于估計輸入超圖的統(tǒng)計量，例如節(jié)點度和超邊大小分布（見 B4）。

• 算法摘要：HRW 通過具有單獨節(jié)點和超邊轉(zhuǎn)移的馬爾可夫鏈蒙特卡洛（MCMC）獲得節(jié)點和超邊樣本。輸入超圖的統(tǒng)計量基于采樣的節(jié)點和超邊進(jìn)行估計。
• 直觀理解：在超邊上樸素地構(gòu)建馬爾可夫鏈具有高的時間和空間復(fù)雜度。HRW 分離了節(jié)點和超邊轉(zhuǎn)移，以避免考慮節(jié)點和超邊的組合，從而降低了狀態(tài)空間的復(fù)雜度。
• 他們還提出了提高 HRW 采樣效率和估計準(zhǔn)確性的技術(shù)。這些技術(shù)包括使用提升馬爾可夫鏈（lifted Markov chains）[31] 的非回溯策略以加速收斂，以及跳過策略以加速轉(zhuǎn)移。

5.2.2 動態(tài)生成器。我們現(xiàn)在將介紹動態(tài)子超圖生成器。

G15. TRHC。TRHC（temporal reconstruction hill climbing，時間重構(gòu)爬山法），由 Comrie 和 Kleinberg [40] 提出，主要基于關(guān)于超圖自我網(wǎng)絡(luò)的觀察（見 P21、P22 和 P23）。

• 算法摘要：給定一個自我網(wǎng)絡(luò)，TRHC 為給定自我網(wǎng)絡(luò)中的超邊分配時間順序。從初始順序開始，TRHC 不斷交換超邊對以提高不同順序的“適應(yīng)度”（fitness），其中“適應(yīng)度”由監(jiān)督模型評估。當(dāng)無法再改進(jìn)時，過程終止。
• 直觀理解：監(jiān)督模型經(jīng)過訓(xùn)練，以便它應(yīng)該給更好地匹配觀察的時間順序更高的“適應(yīng)度”值。因此，提高“適應(yīng)度”應(yīng)該使時間順序更類似于觀察到的模式。
• 該生成器僅限于預(yù)測完全給定的一組超邊的順序，并且也僅限于超圖自我網(wǎng)絡(luò)。此外，在真實世界場景中，一組超邊的多個不同順序可能同樣可能且現(xiàn)實。研究偏序（例如，因果關(guān)系 [120]）可能是一個有趣的方向。

G16. CRU。CRU（correlated repeated unions，相關(guān)重復(fù)并集），由 Benson 等人 [17] 提出，主要基于關(guān)于真實世界時序超圖中時間行為的觀察（見 P17 和 P20）。

• 算法摘要：CRU 以順序方式生成子超圖（例如，星型自我網(wǎng)絡(luò)；見 E5）中的超邊。對于每條新超邊，假設(shè)其大小和其中此前從未出現(xiàn)過的新節(jié)點數(shù)量是已知的。為了找到剩余節(jié)點來填充超邊，CRU 從現(xiàn)有超邊中采樣一條超邊，其中較近的超邊更有可能被選擇。所選超邊中的每個節(jié)點以采樣概率 p p獨立地復(fù)制到新超邊中，直到新超邊被填滿。如果新超邊未被填滿，則重復(fù)相同的過程。
• 直觀理解：從現(xiàn)有超邊采樣建立了新超邊與現(xiàn)有超邊之間的時間相關(guān)性（見 P17）。時間局部性的程度由對近期超邊的偏差控制，而相關(guān)性的程度（即子集的重復(fù)）由采樣概率 p p 決定。
• 所需的輸入信息包括每條新超邊的大小和其中新節(jié)點的數(shù)量，這可能是不現(xiàn)實地強(qiáng)的。用較弱的預(yù)言機(jī)（oracle）保留所考慮的模式將是一個具有挑戰(zhàn)性但有趣的未來方向。

6 未來應(yīng)用與方向

在本節(jié)中，我們討論超圖挖掘，尤其是超圖模式的未來應(yīng)用與方向。我們主要討論與圖挖掘相關(guān)的現(xiàn)有應(yīng)用與研究主題，特別是本綜述所討論內(nèi)容的圖論對應(yīng)物。由于大多數(shù)超圖模式是從圖模式推廣而來的，我們預(yù)計圖挖掘的許多現(xiàn)有應(yīng)用與方向在未來也將被擴(kuò)展并推廣至超圖。有關(guān)包含更多參考文獻(xiàn)的深入討論，請參閱補充文檔 [1]。

6.1 在算法設(shè)計中的應(yīng)用

圖挖掘模式已啟發(fā)了面向真實世界應(yīng)用的創(chuàng)新圖算法，我們預(yù)計這些應(yīng)用可以擴(kuò)展至超圖挖掘。

度分布。關(guān)于真實世界圖通常表現(xiàn)出重尾度分布的觀察已被用于圖算法的設(shè)計，包括分布式圖算法 [149]、圖遍歷算法 [180] 等。基于超圖中的類似模式（見 P1 和 P15），上述應(yīng)用有可能擴(kuò)展至超圖。

時間局部性。在許多真實世界時序圖中，觀察到時間局部性，即在較小時間窗口內(nèi)出現(xiàn)的邊更有可能相互交互。這一性質(zhì)已被用于設(shè)計用于三角形計數(shù) [100] 和圖遍歷 [93] 的高效算法。在超圖中已觀察到幾種與時間局部性相關(guān)的模式（見 P17 和 P21），我們預(yù)計此類模式將有助于時序超圖算法的設(shè)計。

直徑。真實世界圖中的小直徑已被考慮用于設(shè)計大規(guī)模圖挖掘算法 [83]。因此，在真實世界超圖中觀察到的收縮直徑（見 P27）也可能有助于大規(guī)模超圖挖掘。

6.2 在機(jī)器學(xué)習(xí)中的應(yīng)用

圖模式也已被廣泛用于圖上的機(jī)器學(xué)習(xí)，這暗示了超圖模式在超圖機(jī)器學(xué)習(xí)中的潛在有用性。

圖神經(jīng)網(wǎng)絡(luò)與通用特征表示。圖上機(jī)器學(xué)習(xí)中最常見的主題之一是特征表示，其中圖神經(jīng)網(wǎng)絡(luò)（GNNs）常被使用。許多圖性質(zhì)與模式已被考慮用于增強(qiáng) GNN 的性能，包括度分布 [115] 和同配性 [158]。我們預(yù)計超圖模式將像其圖論對應(yīng)物一樣，在（超）圖神經(jīng)網(wǎng)絡(luò)以及超圖中的通用特征表示方面發(fā)揮作用。

鏈路預(yù)測與社區(qū)發(fā)現(xiàn)。鏈路預(yù)測和社區(qū)發(fā)現(xiàn)是圖上兩個傳統(tǒng)的機(jī)器學(xué)習(xí)問題。許多圖模式已被用于這兩個問題，包括同配性 [39] 和圖模型 [145]。我們期待看到超圖模式被用于這兩項任務(wù)。

異常檢測。異常檢測是另一個傳統(tǒng)的機(jī)器學(xué)習(xí)問題，而基于圖的異常檢測 [3] 是一個流行的子主題。許多圖模式已被用于基于圖的異常檢測，包括圖模體 [135] 和 k k-核 [155]。我們預(yù)計超圖模式在此應(yīng)用中會有更多用途。

推薦系統(tǒng)。圖是構(gòu)建推薦系統(tǒng)的重要工具，推薦系統(tǒng)是機(jī)器學(xué)習(xí)中一個長期存在的研究主題，其中許多圖模式已被使用，包括圖模體 [65] 和自我網(wǎng)絡(luò)的結(jié)構(gòu) [48]。超圖對于此任務(wù)也很有用，尤其是捆綁推薦（bundle recommendation）[184]。我們期待超圖模式在推薦系統(tǒng)中得到更多應(yīng)用。

6.3 廣義超圖的分析與挖掘

在本綜述中，我們主要討論了簡單超圖（即無向且無權(quán)的超圖）。下面，我們希望討論幾種類型的廣義超圖。

有向超圖。有向超圖（其中每條超邊內(nèi)的節(jié)點被劃分為源集和目標(biāo)集）已在數(shù)學(xué)和理論計算機(jī)科學(xué)領(lǐng)域得到研究。最近，Kim 等人 [89] 將互惠性（reciprocity）的概念擴(kuò)展到了有向超圖，并研究了真實世界有向超圖中的相關(guān)模式。我們預(yù)計將在有向超圖上探索更多模式。

加權(quán)超圖。本綜述中提到的大多數(shù)工作處理的是無權(quán)的真實世界超圖，或明確地將數(shù)據(jù)集預(yù)處理為無權(quán)超圖，盡管有些工作考慮了超邊的重復(fù) [17, 103]。最近，學(xué)界對具有邊依賴節(jié)點權(quán)重（即一個節(jié)點在不同超邊中可以具有不同權(quán)重）的超圖也日益感興趣 [32]。我們預(yù)計將在加權(quán)超圖上探索更多模式。

7結(jié)論

超圖是一種寶貴的數(shù)學(xué)框架，用于建模各種真實世界場景中復(fù)雜的群體交互。超圖固有的復(fù)雜性既為超圖挖掘帶來了機(jī)遇，也帶來了挑戰(zhàn)，而超圖挖掘最近已日益受到關(guān)注。本綜述全面考察了迄今為止超圖挖掘領(lǐng)域的進(jìn)展，并對超圖的模式、工具與生成器提供了全面的概述。我們還提出了完整的分類體系，以增進(jìn)對各個方面的結(jié)構(gòu)化理解。最后，我們提出了若干研究方向。我們希望本綜述能為研究人員和從業(yè)者提供寶貴的資源與見解，從而推動超圖在各領(lǐng)域的基礎(chǔ)研究與實際應(yīng)用的發(fā)展。

原文鏈接：https://arxiv.org/pdf/2401.08878v2