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

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

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

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

超圖屬于高階網絡家族，是建模現實世界中群體交互的一種自然且強大的選擇。例如，在建模可能不僅涉及兩人，而是三人或更多人的協作網絡時，使用超圖使我們能夠超越成對（二元）模式進行探索，并捕捉群體（多元）模式。超圖的數學復雜性既為超圖挖掘帶來了機遇，也帶來了挑戰。超圖挖掘的目標是發現不同領域真實世界超圖中反復出現的結構性質，我們稱之為模式。為了發現模式，我們需要工具。我們將超圖挖掘工具分為三類：（1）零模型（用于檢驗觀測模式的顯著性）；（2）結構元素（即超圖中的子結構，例如開三角與閉三角）；（3）結構量（即用于計算超圖模式的數值工具，例如傳遞性）。此外，還存在超圖生成器，其目標是生成能夠忠實表征真實世界超圖的合成超圖。在本綜述中，我們對超圖挖掘的當前研究格局進行全面概述，涵蓋模式、工具與生成器三個方面。我們為每一類內容提供了系統的分類體系，并就超圖挖掘的未來研究方向進行了深入探討。

CCS 概念：? 計算數學 → 超圖；隨機圖；圖算法；? 計算理論 → 圖算法分析；? 信息系統 → 數據挖掘；? 以人為中心的計算 → 社交網絡分析。

附加關鍵詞與短語：超圖挖掘，超圖生成器，高階網絡

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

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

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

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

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

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

2 預備知識

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

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

3 工具

在本節中，我們介紹用于超圖結構模式的挖掘工具。3 通常，工具包括任何可用于定義或挖掘超圖結構模式的事物。典型的工具包括零模型、結構元素和結構量。在圖 5 中，我們為下文將要介紹的工具提供了一個概覽分類體系。

3.1 零模型

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

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

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

3.2 結構元素

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

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

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

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

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

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

3.3 結構量

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

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

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

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

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

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

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

4 結構模式

在本節中，我們介紹真實世界超圖中的結構模式（有關真實世界中公開可用且常用的超圖數據集列表，請參閱補充文檔 [1] 的表 1）。結構模式是指在不同領域的真實世界超圖（及其所建模的真實世界系統）中反復出現的結構特征 [28]。我們將結構模式分類如下：

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

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

4.1 靜態模式

我們首先介紹靜態模式。這些模式描述了節點和超邊的結構性質，以及真實世界超圖的整體特征。靜態模式不包括那些與時間變化相關的模式。

4.1.1 節點級模式。我們將調查與單個節點性質相關的靜態模式，節點是超圖中的基本元素。

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

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

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

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

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

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

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

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

P7. 重尾群組度分布。我們已經看到真實世界超圖中存在（單個）節點度的重尾分布（見 P1）。現在我們深入探討真實世界超圖中節點群組的度分布（見 Q1）。群組度的分布已被幾位研究人員研究過：

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

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

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

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

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

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

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

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

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

結構模式的強大表征能力進一步驗證了它們作為分析真實世界超圖工具的有用性和意義。此外，結構模式還可用作結構特征 [16, 102–105]，用于具有各種下游應用的機器學習（見第 6.2 節）。

4.1.4 超圖級模式。我們現在將調查超圖級靜態模式。超圖級模式涉及超圖作為整體的性質，檢查它們使我們對真實世界超圖獲得宏觀見解。

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

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

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

4.2 動態模式

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

4.2.1 超邊級模式。我們現在將調查超邊級動態模式（hyperedge-level dynamic patterns），描述超邊出現之間的時間關系。

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

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

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

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

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

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

4.2.2 子超圖級模式。我們現在將調查子超圖級動態模式。此類模式描述了節點和/或超邊組合的時間行為。

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

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

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

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

與整個超圖中超邊的時間局部性（P17）相比，自我網絡內的時間局部性為局部超圖演化提供了獨特的見解。

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

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

這些模式為自我網絡構建的底層機制提供了見解，被稱為自我網絡的人擇原理（anthropic principles），這類似于人類研究史前歷史的方式。

P23. 自我網絡的新穎率模式。自我網絡中新添加的超邊可能包含新穎節點（novel nodes），即此前未在自我網絡中出現過的節點。此類新穎節點的數量被稱為新穎率（novelty rate）。Comrie 和 Kleinberg [40] 調查了新穎率如何隨自我網絡演化而變化。

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

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

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

4.2.3 超圖級模式。我們現在將調查超圖級動態模式。這些模式描述了超圖作為整體的特征隨時間如何變化。

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

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

5 生成器

在本節中，我們介紹超圖生成器。我們重點關注基于真實世界超圖性質的生成器。超圖生成器在大規模建模中起著至關重要的作用，它們通過生成模仿真實世界超圖結構的合成數據集，促進了基準測試和可擴展性測試。在圖 10 中，我們為下文將要討論的生成器提供了分類體系。我們將感興趣的生成器分類如下：

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

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

5.1 全超圖生成器

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

5.1.1 靜態生成器。我們將在下面介紹靜態全超圖生成器。

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

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

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

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

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

G5. HSBM。HSBM（hypergraph stochastic block model，超圖隨機塊模型），由 Ghoshdastidar 和 Dukkipati [61] 提出，可以生成社區結構（見 E10 和 P12），并且對于社區發現很有用。

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

5.1.2 動態生成器。我們現在將介紹動態全超圖生成器。

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

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

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

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

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

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

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

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

5.2 子超圖生成器

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

5.2.1 靜態生成器。我們將在下面介紹靜態子超圖生成器。

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

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

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

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

5.2.2 動態生成器。我們現在將介紹動態子超圖生成器。

G15. TRHC。TRHC（temporal reconstruction hill climbing，時間重構爬山法），由 Comrie 和 Kleinberg [40] 提出，主要基于關于超圖自我網絡的觀察（見 P21、P22 和 P23）。

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

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

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

6 未來應用與方向

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

6.1 在算法設計中的應用

圖挖掘模式已啟發了面向真實世界應用的創新圖算法，我們預計這些應用可以擴展至超圖挖掘。

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

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

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

6.2 在機器學習中的應用

圖模式也已被廣泛用于圖上的機器學習，這暗示了超圖模式在超圖機器學習中的潛在有用性。

圖神經網絡與通用特征表示。圖上機器學習中最常見的主題之一是特征表示，其中圖神經網絡（GNNs）常被使用。許多圖性質與模式已被考慮用于增強 GNN 的性能，包括度分布 [115] 和同配性 [158]。我們預計超圖模式將像其圖論對應物一樣，在（超）圖神經網絡以及超圖中的通用特征表示方面發揮作用。

鏈路預測與社區發現。鏈路預測和社區發現是圖上兩個傳統的機器學習問題。許多圖模式已被用于這兩個問題，包括同配性 [39] 和圖模型 [145]。我們期待看到超圖模式被用于這兩項任務。

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

推薦系統。圖是構建推薦系統的重要工具，推薦系統是機器學習中一個長期存在的研究主題，其中許多圖模式已被使用，包括圖模體 [65] 和自我網絡的結構 [48]。超圖對于此任務也很有用，尤其是捆綁推薦（bundle recommendation）[184]。我們期待超圖模式在推薦系統中得到更多應用。

6.3 廣義超圖的分析與挖掘

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

有向超圖。有向超圖（其中每條超邊內的節點被劃分為源集和目標集）已在數學和理論計算機科學領域得到研究。最近，Kim 等人 [89] 將互惠性（reciprocity）的概念擴展到了有向超圖，并研究了真實世界有向超圖中的相關模式。我們預計將在有向超圖上探索更多模式。

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

7結論

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

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