什么是高階網絡？

什么是高階網絡？

What Are Higher-Order Networks?

https://ora.ox.ac.uk/objects/uuid:acfb9de6-9299-4b7b-86ed-51038304a9d7/files/rws859g36t

摘要

利用圖論語言對復雜系統和數據進行基于網絡的建模，已成為跨越多個不同學科的重要課題?？梢哉f，這種基于圖的視角之所以成功，源于圖的相對簡單性：圖不過是由一組頂點和一組邊構成，用于描述這些頂點對（pairs）之間的關系。這種簡單的組合結構使得圖成為具有可解釋性且靈活的建模工具。然而，圖作為系統模型的這種簡單性，最近在文獻中受到了審視。具體而言，已有觀點從不同角度指出，需要高階網絡（higher-order networks），以超越圖所 encapsulated（概括/封裝）的成對關系建模范式。在這篇綜述文章中，我們對這些最新進展進行了盤點。我們的目標是闡明：(i) 什么是高階網絡，(ii) 為何它們是有趣的研究對象，以及 (iii) 它們如何在應用中發揮作用。

關鍵詞。 網絡，圖，超圖，單純復形，拓撲，動力學，統計學，關系數據，數據分析

I. 引言

近幾十年來，人們對網絡和由相互連接的實體組成的網絡動力學系統的興趣激增，旨在理解各種復雜系統。例子范圍從生物系統（如基因調控網絡）到基礎設施系統（如交通網絡）[283, 20, 225]。

術語“網絡”（network）通常指“圖”（graph），這是一種由頂點（或節點）和邊（或鏈接）組成的組合結構。在這種抽象中，節點代表系統中的實體，邊表示哪些實體相互作用。將系統表示為圖對于深入了解系統的結構和動力學特征一直至關重要：圖屬性可用于確定重要節點 [118, 232, 129]，揭示系統的模塊化結構 [114, 261]，或者——如果每個節點是一個動力學單元——闡明集體網絡動力學，如同步 [282]。這些想法已擴展到加權圖、符號圖、有向圖以及具有多種邊或節點類型的圖（如多層圖或多重圖）。然而，任何基于圖的方法的一個局限性在于，根據定義，所有關系都是二元（dyadic）或成對（pairwise）關系，因為圖中的邊是成對關系。例如，在網絡動力學中，二元交互通常反映在運動方程中，即兩個給定節點之間的交互獨立于網絡中的任何其他節點。

然而，在許多現實世界系統中，網絡交互和關系是非二元的（nondyadic），涉及兩個以上節點的聯合非線性交互。例如，在社會經濟系統中，基于群體的交互很常見，活動通常在多個代理人（例如，買方、賣方、經紀人）之間共同協調 [49]。生化系統中的反應通常涉及兩個以上的物種[178]，或者兩種試劑可能僅在酶存在的情況下相互作用。三個或更多節點之間非線性交互的重要性在社會科學研究中也一直備受爭論 [98]。例如，結構平衡理論暗示社交網絡中的三元關系將按照俗語規則演化：“朋友的朋友是我的朋友”和“敵人的敵人是我的朋友” [202]。最近對大型在線社交網絡的分析證實，這些網絡確實極其平衡 [106]。同樣，同伴壓力、聯盟和同盟的形成以及經紀活動是常見社會現象的例子，這些現象確實涉及多人的交織活動，而不僅僅是成對；參見 [26] 以討論更多示例和參考文獻。也有人認為，聯合交互對于觀察多個相互作用物種中的競爭模式至關重要 [1, 192]。

為了充分捕捉任何此類網絡的屬性，至關重要的是要超越僅捕捉二元關系的圖，并闡明多元（polyadic）網絡交互的影響 [30, 290, 26]。多元交互和關系在文獻中已在各種名稱下被討論，包括超二元（supra-dyadic）、非成對（nonpairwise）、高階（higher-order）或單純形（simplicial）。在下文中，我們將把具有此類交互的網絡統稱為高階網絡。但是高階網絡究竟是什么？它們在數學上如何表示？有哪些工具可用于分析它們？

導致命名差異的一個潛在原因是，高階網絡出現在不同研究領域的各種背景中，這些領域通常具有稍微不同的動機、研究問題和數學工具。本文的主要目的是提供關于高階網絡及其數學表示的整合視角，并回顧這一非常活躍的研究領域的近期進展，重點關注基礎問題和數學工具。因此，我們的綜述補充了其他近期的調查，包括一個更側重于物理學的視角 [26]，該視角以廣泛的參考文獻列表為特色，討論了不同高階模型之間的關系及依賴建模 [290]，以及關于高階網絡上信號處理的調查 [264]。具體而言，我們將在三個背景下討論高階網絡，它們已發現特定的應用：

• 數據的拓撲和幾何（第3節）：高階網絡如何幫助理解數據集的“形狀”？
• 關系數據的分析和建模（第4節）：如何對高階關系進行統計建模，以及使用此類統計模型有哪些優勢？
• 高階網絡動力學系統（第5節）：高階交互如何影響耦合動力學單元的集體動力學？

我們相信，這份關于高階網絡的綜述可以為許多主要被單獨考慮的研究領域提供一種共同語言。我們要強調這些領域之間的差異和相似之處，并制定長期研究展望。

1.1. 超越二元交互：從圖到高階網絡。

1.1.1. 拓撲與幾何：理解數據的“形狀”

高維點云數據通常包含某些幾何或拓撲信息。拓撲工具能夠對拓撲或幾何結構進行分類，例如，檢測數據中可能的聚類。作為一個例子，考慮圖 1A 中展示的 Isomap 算法 [287]，該算法旨在學習點云數據的低維表示。Isomap 的核心思想是，如果假設觀測到的數據是來自嵌入在更大樣本空間中的低維流形的含噪樣本，我們可以構建一個圖，作為該連續對象的離散近似：頂點對應于數據點，如果對應數據點之間的距離小于某個預定義參數 ε ε，則兩個頂點由一條邊連接。由此產生的（一族）圖提供了數據的低維表示。許多流行的算法遵循這一范式的變體：(i) 將每個數據點映射到圖中的一個頂點，(ii) 根據基于原始數據點成對（pairwise）相似性或距離的某些標準定義邊，以及 (iii) 分析構建的圖以提取節點的低維表示，從而提供與這些節點關聯的原始數據點的嵌入。例如，擴散映射（diffusion maps）[82] 或拉普拉斯特征映射（Laplacian eigenmaps）[27]，基于從以上述方式構建的圖導出的拉普拉斯矩陣的（縮放）特征向量來定義嵌入坐標。關于這類流形學習算法的概述，另請參閱書籍 [201] 及其中的參考文獻。

1.1.2. 通過高階網絡對關系數據進行建模。

網絡的統計分析，例如社交網絡中的友誼關系，一直是網絡分析的核心話題。在此背景下我們要理解的數據通常是關系數據（relational data），即關于實體集合（sets of entities）如何相互關聯的數據（見圖 2）。進一步的例子包括合著網絡、生態關系（捕食-被捕食或互利共生），或描述萬維網的超鏈接圖，僅舉幾例。與 1.1.1 和 1.1.3 小節討論的拓撲/幾何或動力學視角相比，采用這種視角時，我們主要關注關系本身的統計建模，而不是分析這些關系以了解網絡的某些拓撲和幾何形狀。換句話說，我們的目標是提供一個統計模型，該模型指定觀察到一組給定關系的概率。

在許多應用中，關系是記錄在恰好兩個實體之間的——例如從一個網頁到另一個網頁的超鏈接，或兩個人之間的友誼連接——這自然導致了連接這兩個實體的（二元）圖中的邊，其中實體表示為頂點。因此，關系數據的典型模型定義了一組圖上的概率分布。一個簡單的例子是 Erd?s–Rényi 模型，它假定對于給定的基數為 N N 的頂點集 V V，任何兩個對象之間存在成對關系的概率是固定的 p p。其他例子包括配置模型（configuration models）、隨機塊模型（stochastic block models）或指數隨機圖模型（exponential random graph models）。

然而，正如上面提到的合著例子所說明的那樣，關系數據可能包含包含兩個以上實體的集合：一篇論文可能有兩名以上的作者共同署名。與其將這種多個實體之間的關系分解為多個二元關系，我們可以嘗試保持這些關系集合的完整性，并在我們的統計模型中直接考慮它們。這就變得有必要在超圖或單純復形的空間上開發概率模型。我們在第 4 節討論并回顧此類統計模型，以及在其開發和分析中出現的問題。

1.1.3. 高階網絡動力學系統。

網絡動力學系統為許多由相互作用的動力學實體組成的現實世界系統提供了一種自然的抽象。這些系統包括耦合神經元網絡、電網、相互作用物種的生態網絡以及網絡上的流行病過程 [46]。一個網絡動力學系統通常由 (i) 若干個具有狀態變量的動力學節點組成，這些變量根據微分方程演化，以及 (ii) 一個網絡結構組成，該結構捕捉哪些節點相互作用以及它們如何相互作用（函數形式）。主要問題是，集體網絡動力學——所有節點的聯合動力學，例如同步——如何與網絡結構相關聯？

在傳統網絡動力學系統中，節點間的相互作用由圖來捕捉；參見圖 3。該圖可能基于實際的物理連接（例如，兩個節點之間的物理電力線），作為建模選擇強加的（例如，圖上的動力學系統），從數據推斷的（例如，當時間序列相關時在兩個節點之間放置一條邊），或者作為節點狀態之間依賴關系的形式描述給出的（例如，在耦合細胞系統中）。此外，網絡相互作用通常是可加的：對于 Kuramoto 振子網絡 [183, 2, 254]——網絡動力學系統最顯著的例子之一——兩個振子對第三個振子的聯合效應是兩個單獨（非線性）效應的總和。當不同節點隨時間演化（最終）表現一致時，就會發生同步。此類動力學特性受代表網絡的圖的特性影響。例如，經典結果將底層圖的譜與網絡動力學系統的同步特性聯系起來 [238]。

網絡動力學系統的一個自然推廣是允許三個或更多振子之間的聯合非線性相互作用——這導致了一個高階網絡動力學系統。然而，這種推廣引發了以下問題：什么是捕捉此類相互作用的合適組合結構？動力學特性（如同步）如何與該結構的特性相關聯？一種方法是在超圖或單純復形上定義動力學系統，但這存在一些注意事項。正如我們將在第 5 節討論的那樣，對于耦合振子網絡，坐標變換也可能為加法耦合的系統產生“有效”的非二元相互作用；參見圖 3。事實上，動力學系統的（高階）網絡表示在坐標變換下不一定是不變的。然而，更重要的是，如果一個高階網絡動力學系統通過坐標變換與一個二元網絡動力學系統相關聯，它將表現出相同的動力學特性。換句話說，如果存在這樣的變換，那么整個系統可以等價地由一個有效（二元）網絡來描述，而不需要高階網絡表示。我們將在第 5 節更詳細地討論這些方面及其對建模的影響。

1.1.4. 一個例子：高階相互作用的多個方面

讓我們通過考察秀麗隱桿線蟲（Caenorhabditis elegans）的例子，來凸顯上述討論視角之間的差異。這種線蟲的完整連接組（connectome）——即神經元之間的物理連接——已被繪制出來。重要的是，每只線蟲的連接組都是相同的，因此有望通過以（高階）網絡的形式分析該連接組，來揭示線蟲內部神經信息處理的重要特征。現在，我們可以提出幾種類型的問題。首先，我們可能對該連接組的拓撲特征感興趣，通過使用第3節中的技術來分析該網絡的“形狀”[270]。例如，持續同調（persistent homology）可以為該特定連接組的拓撲特征提供洞察。其次，我們可能對構建連接組數據的概率網絡模型感興趣（第4節）。盡管每只線蟲的連接組都相同，因此秀麗隱桿線蟲的連接組本身并不具有隨機性，但將這些連接視為關系數據并嘗試為其擬合概率模型，仍可能為我們提供某些洞見；例如，某些連接模式的出現頻率是否高于或低于預期。例如，通過與隨機零模型進行比較，我們可以評估連接組的某些特征純屬偶然出現的可能性有多大 [304, 138]。第三，網絡特性有助于理解秀麗隱桿線蟲神經元網絡的集體動力學 [293, 18, 304]。盡管人們可能直觀地將連接組視為一張圖，但非加性網絡耦合以及有效（或間接）相互作用均可引出一個高階網絡動力學系統（第5節）。

1.2. 缺失的環節：未涵蓋的主題

還有一些其他主題可以直觀地從高階網絡的視角來考慮，但超出了本綜述的范圍。我們在此給出一個簡要概述，并提供進一步閱讀的參考文獻。

多重網絡（Multiplex Networks）。 多重網絡、多層網絡（multilayer）以及網絡的網絡（networks of networks）已被提出作為存在不同類型交互的系統的建模范式 [177]。這些范式旨在解釋不同類型的鏈接，例如通信網絡中的不同模態（電話、短信、電子郵件）。然而，在大多數情況下，這些交互是二元的（dyadic），因此可以用傳統網絡來表示。

用于序列數據的高階馬爾可夫模型（Higher-Order Markov Models for Sequential Data）。定義在網絡上的馬爾可夫模型已成為描述和建模不同實體間信息、能量、質量、資金等流動的一種流行方法。如果其演化由（一階）馬爾可夫過程給出，則該過程可以被視為圖上的隨機游走 [203]。然而，許多在網絡上經驗觀察到的流動確實具有某種路徑依賴性。因此，需要高階馬爾可夫鏈模型 [185]。

高階圖模型與馬爾可夫隨機場（Higher-Order Graphical Models and Markov Random Fields）。 諸如伊辛模型（Ising model）之類的馬爾可夫隨機場以及更一般的圖模型，也已被擴展為能夠解釋多個實體之間交互的高階模型。例如，對于伊辛模型，人們尋求了包含三階交互的擴展，以對小鼠的社會交互進行建模 [267]。關于在圖模型中引入高階交互的其他工作包括 [313, 242, 180]。請注意，圖模型當然可以用來描述各種類型對象上的概率分布，包括圖以及第4節中討論的圖的推廣。然而，第4節的重點在于二元和非二元關系數據的統計模型，而不是內置于統計模型中的高階依賴關系，例如擴展伊辛模型中的三階交互 [267]。

圖信號處理與單純形信號處理（Graph Signal Processing and Simplicial Signal Processing）。 圖信號處理是信號處理中一個相對較新的領域，它處理支撐于圖節點上的信號，旨在將插值、信號平滑、采樣和濾波等信號處理技術轉化并擴展到圖領域 [268, 230]。最近，有人提議將這些思想擴展到單純復形和超圖；參見例如 [311, 21, 264, 262]。

基于張量的模型、基于張量的算法及其應用（Tensor Based Models, Tensor Based Algorithms, and Applications）。 由于（二元）網絡可以通過鄰接矩陣或拉普拉斯矩陣等矩陣來描述，張量提供了網絡模型可以擴展的另一個可能方向。例如，我們可以考慮基于張量的高階網絡生成過程?；蛘?，我們可以使用基于張量的算法（如張量分解）來分析高階網絡數據。例子包括將張量分解應用于時間相關網絡中的社區檢測 [119]，或模體（motifs）的譜聚類 [31]，以及基于張量的中心性分析 [130]。

1.3. 本文大綱。 本文的其余部分結構如下。在第2節中，我們匯總了全文將使用的數學概念。在第3節中，我們討論如何分析數據的拓撲與幾何，并重點介紹高階網絡如何幫助理解數據集的結構特征。在第4節中，我們討論高階關系模型，以及它們如何有助于描述和理解關系數據。在第5節中，我們討論高階網絡動力學系統及其與傳統網絡動力學系統的關系。最后，我們在第6節以討論和進一步研究的問題展望作為結語。

2. 圖、超圖和單純復形簡述

超圖和單純復形是能夠對高階交互進行編碼的數學對象。在1.1小節非正式介紹的基礎上，我們在此匯總這些對象的定義。

像圖一樣，超圖也可以擴展以包含方向性和權重；參見例如 [16] 及其中的參考文獻。在統計學的高階網絡背景下，我們可以將整數權重理解為某些邊出現多次的超圖。

3. (高階) 網絡數據的幾何與拓撲

正如 1.1.1 小節所述，拓撲數據分析 (TDA) 的一個核心思想是通過拓撲對象（如單純復形）來描述經驗觀測數據，例如點云。該拓撲對象的性質隨后提供了一種描述數據的方法。歐拉示性數 χ χ 就是此類性質的一個例子，它在適當的意義上給出了大小的度量 [259]。同樣，我們將在下一節描述的同調 (homology)，提供了一種度量單純復形性質的方法，例如連通分量和環的數量。事實上，同調與歐拉示性數密切相關，但它提供了關于單純復形拓撲結構的更詳細描述。在下文中，在討論如何利用這些概念描述數據的高階結構之前，我們首先關注作為單純復形重要拓撲性質的同調。關于這些拓撲概念的更多信息，請參見 [144, 219, 6, 126, 205, 206, 125, 265]。

3.2. 持續同調。 持續同調（Persistent Homology, PH）是拓撲數據分析（TDA）中的重要工具之一。PH 通過研究數據多個尺度上的同調，實現了對數據中有意義的拓撲和幾何特征的量化。

定義 3.7（見 [59, 101, 124]）。單純復形 K K 的一個濾過（filtration）是一列嵌套的單純復形，

持續同調受益于理論支撐，這些理論證明了條形碼對輸入數據的小擾動具有魯棒性 [81]。持續同調是可計算的，有許多軟件實現可用，我們建議讀者參閱教程和“用戶指南” [231, 244, 218, 70, 236] 以獲取更多信息。

注記 3.8。 定義單純上同調（simplicial cohomology）并為給定單純復形 K K 的濾過計算上同調群的條形碼也是可能的。一般來說，上同調比同調更強大。但對于域 F F 上的系數，上同調群與同調群是對偶的，更一般地，它們通過萬有系數定理（Universal Coefficient Theorem）相關聯。在我們在此考慮的設置中，同調和上同調產生相同的條形碼 [94, Proposition 2.3]，這就是為什么人們通常不區分持續同調和持續上同調的原因。

擴展持續同調的數學理論仍然是一個活躍的研究領域。例如，當數據無法編碼為濾過（即空間的嵌套序列）時，或者如果數據集最好用兩個參數（即雙濾過）進行分析時，那么之字形持續性（zig-zag persistence）[61, 60] 或多參數持續同調 [64, 63] 可能分別更合適。這些及其他同調對象的計算正在積極開發和實施中，以便應用于實際 [148, 62, 213, 258, 142, 172, 191]。研究有向網絡的高階類比的一個活躍研究領域是有向代數拓撲的數學領域，其旨在捕捉數據中的周期性 [107]。近年來，某些有向復形的持續同調 [200]、持續路徑同調 [78, 96] 以及加權路徑同調也已被提出 [195]。

最終，為了分析數據，我們需要比較持續性計算的輸出。實現這一點最常見的方法是將條形碼轉換為向量格式，這可以采取各種形式，例如持續性圖像（persistence images）或持續性景觀（persistence landscapes），或者可以基于核方法，然后可以使用統計學和機器學習中的工具進行解釋 [3, 184, 69, 52]。為拓撲開發此類統計工具，包括假設檢驗、自助法（bootstrapping）和定義形狀統計，是另一個重要的相關研究領域 [250, 110, 301, 111, 245]。

3.3. 持續同調的應用

持續同調已在現實世界的復雜系統中得到廣泛應用。3 例如，持續同調也被用于描述材料科學中的三維結構 [255, 152] 以及分析傳感器網絡（參見兩篇易于理解的入門文章 [93, 251]）。不同的應用有不同類型的輸入數據，例如高維空間中的點云、網絡數據（節點和關系）、圖像（方形網格中的灰度像素數據），或作為給定超圖的數據。

當數據以點云形式給出時，需要確定合適的濾過參數以及要構建的相應復形 [125, 59, 102, 101]。對于持續同調，所選的濾過高度依賴于具體應用（參見例如 [278, 281]），并且該濾過可能會將用戶限制在特定的軟件上。雖然超圖數據的同調或持續同調是可行的 [50, 248]，但這需要合適的濾過。本節討論的應用主要集中在單純復形或其 1-骨架（圖）上，這兩者都是超圖的類型。

使用拓撲方法研究神經科學問題最早是在 20 世紀 60 年代提出的 [310]。神經科學數據的可獲得性以及數學理論和計算的進步使該領域得以蓬勃發展。計算拓撲和高階網絡已被證明在分析全譜系腦數據方面是成功的，這些數據范圍從功能網絡 [270]，到分支神經元的形態學 [167]，到結構（突觸）連接性 [246]，到位置細胞（place cells）[127]，到秀麗隱桿線蟲的連接組 [147]，再到腦部疾病的成像 [90, 51]。我們在此不列出拓撲神經科學研究的詳盡清單，而是建議讀者參閱幾篇近期的綜述文章 [91, 149, 43]。

高階網絡也被證明在基因組學和進化生物學 [243, 65]、結構生物學 [302]，以及諸如血管網絡 [28, 280, 54] 等結構的分析中非常有用。概述拓撲技術（例如在生物學中）潛力的參考文獻包括 [43, 9, 243, 281]。近期的研究表明，高階網絡結構和計算拓撲可能有助于分析生物系統的復雜數學模型 [289, 175, 221, 207]。使用高階網絡來分析諸如癌癥 [15, 226, 280, 131] 等疾病，為結合數據和數學模型提供了可能性 [279, 297]。雖然某些化學反應模型的結構可以使用持續同調來區分 [298]，但其他模型最好編碼為超圖并使用離散里奇曲率（discrete Ricci curvature）進行分析 [104]。

更一般地，許多生物過程，包括神經科學中的過程，可以被建模為動力學系統，我們也可以嘗試使用拓撲工具來理解它們。事實上，研究拓撲與動力學之間的關系有著深厚的根源，可以追溯到 Morse-Smale 動力學系統。Harer、Perea、Robins、Mischaikow 和 Mukherjee 等人（參見 [240, 249, 141, 161, 214] 及其中的參考文獻）開發了使用拓撲方法分析時間序列數據和動力學系統的工具。Memoli、Munch 及其同事一直在擴展持續同調理論和方法，以分析時變系統，范圍涵蓋動態點云、動態圖形式的集體行為以及 Hopf 分岔檢測 [217, 174, 176, 292]。生長圖（Growing graphs）也已使用節點濾過階復形（node-filtered order complexes）[42] 進行了分析。時變數據已使用拓撲摘要（topological summaries）進行了分析，如葡萄藤圖（vineyards）、Crocker 圖（crocker plots）和多參數秩函數（multiparameter rank functions）[303]，而時間網絡（temporal networks）已使用持續路徑同調（persistent path homology）[77] 進行了分析。不同網絡結構（例如環狀晶格和環面）以及單純復形上的傳染動力學也已使用持續同調進行了分析 [286, 157]。動力學也發生在更一般的超圖上，這激發了超越持續同調的方法 [58]。

3.4. 霍奇拉普拉斯算子與霍奇理論

此外，霍奇拉普拉斯算子使得局部動力學過程的嚴格定義成為可能，例如在邊（節點對）和高階實體的域中的擴散和一致性動力學 [215, 194, 154, 260, 233, 234]。這些思想也與（單純）復形上的信號處理緊密相連 [132, 22, 21, 23, 24, 264, 305, 306, 262, 252]，在其中人們可以基于此類霍奇拉普拉斯算子定義諸如卷積等操作，甚至為單純復形定義圖神經網絡的類比物 [253, 47, 99, 128, 53, 41, 139]?；谙嚓P思想，人們還可以構建去中心化協議來解決傳感器網絡中的覆蓋問題 [284]，對網絡內的節點進行排序 [160]，或者分解博弈 [56]。

4. 使用高階網絡模型理解關系數據

在本節中，我們描述（高階）網絡如何被用于研究關系數據。在展開更廣泛的討論之前，我們在 4.1 小節強調與迄今為止討論的高階模型視角的差異，然后在 4.2 小節對高階數據在數學上的含義進行更詳細的討論。隨后，我們在 4.3 小節討論基于單純復形和超圖的此類數據的各種概率模型，并在 4.4 小節指出幾個應用場景。

4.1. 關系數據與從數據創建的關系

對數據之間的關系進行建模當然是本綜述的一個主題，在第 3 節中結合拓撲和幾何進行了討論，在第 5 節中結合動力學進行了討論。然而，當我們將焦點轉向關系數據本身時，我們在旨在理解的內容以及通常使用的數學工具方面存在差異。因此，（高階）網絡在分析中所扮演的角色也有所不同。

第 3 節和第 5 節實際上關注的是理解與網絡中節點關聯的數據（例如時間序列）是如何在拓撲、幾何或動力學上組織的，以及我們如何利用這些節點之間的關系來更好地理解該數據。請注意，在 1.1.1 小節描述的“幾何與拓撲”場景的核心，是構建適當的圖和高階對象以理解關于數據（通常是點云數據）的某些拓撲和幾何問題的想法。例如，根據測量得到的點云數據，按照最近鄰規則構建一個圖，其中每個數據點成為一個節點。然后，所得圖拉普拉斯算子的特征向量被用作描述數據的新坐標系。類似地，在考慮動力學網絡（1.1.3 小節）時，核心問題是我們如何通過分析底層的高階網絡來理解系統的（全局）動力學。

相比之下，在對關系數據進行建模時，我們通常對理解與節點關聯的數據不感興趣，而是我們測量并旨在建模的數據直接以關系的形式出現，例如友誼鏈接或合作關系。例如，我們可能希望通過指定每次合作發生的可能性來對合作網絡進行建模。換句話說，要建模的數據是（高階）網絡或復形的（超）邊或面的集合。雖然也可以嘗試僅從節點觀測中推斷此類關系，例如通過測量節點變量之間的相關性，但在下文中，我們將主要關注那些感興趣的關系可以直接被測量的場景。這包含了一大類數據，包括共現關系、合作、隸屬關系，或質量、能量、資金等的流動。

4.2. 描述高階關系數據

值得注意的是，數據建模范式（抽象）的選擇對下游分析可用工具有著深遠的影響。如果系統可以恰當地由單純復形表示，那么我們就有大量來自應用拓撲學和拓撲數據分析（TDA）的工具可用，我們可以用它們來調查數據的各種特征，例如同調方面的問題（例如，作者合作空間中是否存在空白？）。相比之下，盡管原則上超圖提供了更靈活的數據抽象，但可用的工具相對較少。我們建議讀者參閱最近的綜述 [290]，以獲取關于相關（高階）數據建模表示的更深入討論。

4.3. 高階網絡的概率模型

除非我們的目標僅僅是進行描述性分析，否則一旦我們選擇了合適的框架來表示高階數據，我們通常需要為這類數據定義一個合適的概率或統計模型，以便進行進一步的統計分析。在下文中，我們將討論高階網絡概率模型研究中的一些方向。與其提供完整的討論，我們這里的目標是突出一些促使了進一步數學探究的模型。為了更詳盡的概述，可以參考 [26]。

作為起點，并為了確立本節的術語，在例 4.2 中我們探討了 Erd?s–Rényi 隨機圖模型，并介紹了該模型向高階網絡的推廣，我們將在本節稍后更詳細地描述這些推廣。首先，我們形式化地定義一個統計模型。在本節中，當我們使用術語模型或概率模型時，我們通常是指形式上的統計模型，并以此定義為準則。

4.3.1. 單純復形和胞腔復形的概率模型

隨機單純復形和胞腔復形的研究仍然是一個相對新興的研究領域。在此可以區分出兩條主要的研究路線。首先，有一些復形的隨機模型可以被視為隨機圖模型的推廣，例如上文討論的著名的 Erd?s–Rényi (ER) 隨機圖模型。關于這些推廣和結果的早期綜述，請參閱 [165, 88, 166]。其次，有一些隨機幾何復形的模型。與第一種模型（也可以被視為隨機抽象（單純）復形的模型）相比，這些幾何模型的構建通常與 TDA（見第3節）中考慮的設置更為接近，因此作為此類應用的零模型具有特別的相關性。

隨機抽象單純復形。 該方向最早的模型之一是由 Linial 和 Meshulam [196] 提出的。他們的模型從一個完全圖（一個完全的 1-骨架）開始，然后以概率 p p 獨立隨機地添加 2-單純形。他們表明，就像在 ER 模型中任何采樣圖關于零階同調群（即連通分量）存在閾值現象一樣（即，一旦超過某些連接概率，就會出現巨大的連通分量且圖幾乎肯定是連通的），在他們的隨機 2-復形模型中，關于一階同調群也存在相應的閾值現象。這些結果后來得到了完善和擴展 [17, 153, 198]；例如，[210] 給出了隨機 n n 維復形的類似結果。

隨機幾何單純復形。 類似于隨機抽象單純復形模型可以被視為對著名隨機圖模型的擴展，也存在將隨機幾何隨機圖模型擴展到單純復形的擴展。與其提供詳盡的討論，我們這里的目標再次是提供一些關鍵論文和觀點的指引。為了更全面的近期綜述，感興趣的讀者可以查閱 Kahle [163] 以及 Bobrowski 和 Kahle [44] 的綜述（另見 [26]）。

復形的隨機幾何模型作為 TDA（見第3節）的零模型特別相關。特別是，此類模型使我們能夠理解從隨機幾何數據構建單純復形時出現的各種統計量，例如歐拉示性數 [113]、同調 [45]，或將持續同調應用于隨機幾何數據時出現的持續圖（persistence diagrams）的其他統計量 [111]。

單純復形的最大熵和潛變量模型。 上述描述的模型是高度風格化的模型，允許進行理論探索。然而，對于單純形數據的零模型假設檢驗，我們可能會發現一個模型，它固定某些觀測到的統計量，同時隨機化數據的所有其他特征。形式上，這個想法可以通過單純復形的最大熵模型來實現，例如配置模型（configuration model）[89, 309]（它保持觀測數據的觀測到的（單純形）度序列）或指數隨機單純形模型（exponential random simplex models）[316]（關于指數隨機圖和超圖模型的定義，見下一節）。到目前為止，這些模型大多是在計算上進行探索的，關于它們的理論性質知之甚少。除了最大熵模型外，另一類重要的隨機單純復形模型是潛變量模型。例如，在隨機幾何復形的情況下，給定一些觀測到的單純形數據，我們可能希望推斷出與該數據兼容的潛在幾何。由此產生的幾何隨后可以被解釋為觀測到的單純形數據的一種隱藏原因形式。在幾何模型的領域之外，潛變量模型的研究在單純復形建模方面受到的關注很少（另見 [26]），但主要局限于一般的超圖。

4.3.2. 超圖的概率模型

與隨機單純復形和胞腔復形的研究一致，一般隨機超圖概率模型的研究仍然相當年輕。雖然在理論上幾類模型足夠靈活以建模各種各樣的效應，但在實踐中，只有少數特定的超圖概率模型得到了詳細研究。大多數已發展的超圖統計模型在某種程度上是簡單的，因此，傾向于像上一節描述的隨機單純復形模型那樣被用作零模型。然而，值得注意的是，超圖的幾種模型，特別是那些作為指數隨機圖模型（ERGMs）擴展的模型，其根源在于分類數據分析，這是一個處理離散數據集的統計學領域，因此受益于一些現有的參數估計和擬合優度檢驗方法。這為我們提供了一些處理高階關系數據的工具。在這里，我們描述幾種超圖的概率模型，從 ER 隨機圖的推廣開始，進而轉向上一節暗示的配置模型。最后，我們討論 ERGMs，這是一個包括超圖 β β模型以及諸如超圖隨機塊模型等潛變量模型的家族。

[121] 和 [75] 都展示了配置模型作為超圖零模型的有用性，前者側重于描述來自在線照片分享網站數據的三部超圖，后者側重于各種合作和通信網絡。最近，Chodrow 和 Mellor [74] 將配置模型擴展到了標注超圖（annotated hypergraphs），這是有向超圖的推廣，其中每個頂點在每條邊中都有一個“角色”。

指數隨機圖模型。 也許超圖最靈活的概率模型家族是指數族，可以被描述為指數隨機圖模型的擴展。這個框架對分析特別有幫助，因為如果模型是對數線性的，那么就可以使用分類數據分析中的工具。

[121] 和 [75] 都展示了配置模型作為超圖零模型的有用性，前者側重于描述來自在線照片分享網站數據的三部超圖，后者側重于各種合作和通信網絡。最近，Chodrow 和 Mellor [74] 將配置模型擴展到了標注超圖（annotated hypergraphs），這是有向超圖的推廣，其中每個頂點在每條邊中都有一個“角色”。

指數隨機圖模型。 也許超圖最靈活的概率模型家族是指數族，可以被描述為指數隨機圖模型的擴展。這個框架對分析特別有幫助，因為如果模型是對數線性的，那么就可以使用分類數據分析中的工具。

雖然當每個頂點的簇成員身份已知時，超圖隨機塊模型可用于測試超圖數據集中的同質性（homophily）效應，但它們的主要應用之一（如下一節所述）是在每個頂點的簇成員身份未知時用于社區發現和聚類。在這種情況下，模型變成了潛變量模型，目標變成了試圖確定每個節點最可能的成員身份分配。對于圖，推斷通常使用坐標上升法（coordinate ascent methods）完成，例如期望最大化（EM）算法的變體、MCMC 方法和變分方法（此類方法的概述可在 [187] 中找到）；這些方法才剛剛開始為超圖開發 [171]。

最簡單的超圖隨機塊模型形式傾向于生成同一社區中所有節點具有相似度的圖，然而，對于應用而言，希望擁有一個節點度可以表現出某種異質性的模型。在圖的設置中，也允許度異質性的隨機塊模型被稱為度校正隨機塊模型（degree-corrected stochastic block models）。在指數族設置中，這些模型的充分統計量是通過取相應隨機塊模型的充分統計量并附加頂點的度序列而獲得的 [307]。從圖轉向超圖，已經提出了允許度異質性的超圖隨機塊模型的類似變體。例如，在 [171] 中，Ke, Shi, 和 Xia 定義了度校正超圖隨機塊模型，并開發了一種使用張量分解進行社區發現的方法。此外，度校正超圖隨機塊模型構成了 Chodrow, Veldt, 和 Benson 在 [76] 中描述的聚類算法的基礎，他們在其中通過幾個數據集展示了它們對于檢測真實社區（ground truth communities）的有用性。值得注意的是，[76] 中描述的模型也允許邊大小的異質性，這意味著在這種情況下，模型是在具有不同邊大小的超圖上的概率分布集合。

4.4. 分析高階關系數據：應用實例。 讓我們現在考慮一些應用實例，這些實例基于關系數據的分析（從統計學的角度）。

基于超圖的技術被考慮用于分析關系數據的應用包括異常檢測 [269]、種群分層 [294]，以及大眾分類法（folksonomies）的分析 [312, 121]。我們要再次提到 Chodrow 等人 [75, 74] 關于超圖配置模型的工作，這些模型可以作為各種統計應用的零模型。

在網絡設置中，關系數據最流行的分析之一是社區發現（或網絡聚類），其目標是將系統中的頂點集劃分為若干組，使得這些組彼此之間比與網絡其余部分更相似?；陉P于構成良好社區的各種概念 [261]，存在大量用于網絡的社區發現方法 [114]。不出所料，社區發現問題也被考慮用于高階關系數據。例如，Vazquez [295] 展示了使用貝葉斯框架檢測超圖社區的一些早期工作。一些更具理論性的工作包括 Ghoshdastidar 和 Dukkipati [123, 122]，他們在植入劃分模型（一種特定類型的隨機塊模型）下分析了超圖的譜聚類及其一致性。Kim, Bandeira, 和 Goemans [173] 考慮了針對類似超圖隨機塊模型的平方和方法，而 Chien, Lin, 和 Wang [73] 分析了 d d 元（ d d-wise）超圖隨機塊模型的社區發現最優速率，其中超邊的概率依賴于超邊中包含的頂點的頂點塊分配分布。此外，高階關系數據的社區發現激發了譜超圖理論 [10, 67, 66, 193, 291, 314] 以及超圖割和分裂函數 [146, 296, 308] 方面的大量工作。

由于高階關系數據也可以通過單純復形進行抽象，因此也有許多工作使用這種建模視角，通常將來自拓撲數據分析（TDA，第3節）的工具與統計工具相結合。特別是，已經有關于將網絡中三元閉包的概念（即如果兩個節點有共同鄰居，它們傾向于連接）推廣到高階網絡的工作 [29, 235]。雖然這些工作關注的是（高階）網絡的拓撲如何演化，但也有一些用于分析網絡上邊數據的高階模型，這些模型利用霍奇分解來以一致的方式提取聚合排名 [160]，或者用于在網絡和單純復形上平滑和過濾流及軌跡 [24, 263, 23, 159, 260]。

5. 具有高階交互的網絡動力學系統

網絡動力學系統描述了相互作用的動力學節點的聯合演化。節點之間的耦合可以導致引人入勝的集體網絡動力學，如同步，即節點步調一致地演化。一個關鍵問題是網絡交互——包括網絡結構以及耦合的函數形式——如何塑造這種集體動力學。雖然傳統上使用圖來編碼網絡結構，但我們關注更一般的、“高階”方法來捕捉耦合結構。自然地，這產生了諸如以下問題：什么樣的高階結構適合網絡動力學系統？高階交互如何塑造動力學？在這里，我們關注節點/頂點是動力學單元的網絡動力學系統，盡管最近也討論了具有動力學（超）邊的（高階）網絡 [212, 227]。當然，網絡動力學系統可以產生數據（例如，通過對軌跡進行采樣），前面幾節概述的方法可以應用于這些數據。然而，在這里我們將采用更一般的動力學系統方法來闡明相互作用的動力學系統的一般性質。

5.2. 具有高階交互的網絡動力學系統

對于一般的網絡動力學系統，每個節點的狀態演化可能無法像 (5.1) 中那樣表示為成對交互的疊加。例如，假設動力學按照以下方程演化：

類似于我們通過將 A A 解釋為鄰接矩陣從而將圖 G G 與成對動力學 (5.1) 相關聯，我們可能希望將適當的（組合）數學結構與高階交互項相關聯。與圖的情況類似，隨后我們可以分析這個數學對象，并希望闡明高階系統 (5.3) 的一些有趣的動力學性質。這種推理引出了一系列問題：

(Q1) 高階網絡交互的動力學后果是什么？

(Q2) 高階交互對于理解現實系統的動力學是否至關重要？

(Q3) 是否存在適當的結構（超圖、單純復形等）來表示一般耦合的網絡動力學系統，例如 (5.2)？

直觀上，由于 (5.3) 與 (5.1) 相比在右側展示了一類更一般的向量場，我們可以預期高階網絡將表現出許多新現象。因此，如果一個現實系統只能根據高階交互 (5.3) 來表示，我們可以認為這些高階交互確實至關重要。然而，對我們上述例子進行稍加仔細的審視表明，這個問題有些微妙。例如，對于耦合細胞系統 (5.1)，盡管通常該系統將是一個具有高階交互的網絡動力學系統，但就與該系統的關聯而言，存在一個有意義的基于圖的描述。此外，展開式 (5.3) 通常不是唯一的，我們可以將許多可能的高階網絡與形式為 (5.2) 的系統相關聯。事實上，我們認為問題 (Q2) 和 (Q3) 沒有定義明確的答案，我們將在 5.4.1 小節討論選擇適當的結構如何是一個視角問題。在回到這些概念性問題之前，我們將首先更具體地探討問題 (Q1) 和 (Q2) 的某些方面，并概述文獻中迄今為止給出的一些部分答案。

5.3. 網絡動力學系統中高階交互的影響

在下文中，我們將討論高階網絡交互對動力學的一些后果，以及為何考慮這些后果可能至關重要（參見上一節中的 (Q1) 和 (Q2)）。我們專注于在各種現實世界動力學系統中相關的具體例子，而不是試圖給出一個全面的概述；關于更廣泛的參考文獻列表，請參見 [26]。

5.3.3. 神經科學。 非加性高階相互作用也在神經網絡的動力學中發揮著功能性作用（參見例如 [11, 158] 及其中的參考文獻）。為了理解高階相互作用對集體網絡動力學的影響，Memmesheimer 和 Timme [209] 考慮了在每個神經元的輸入（樹突）處具有非線性放大和飽和的神經網絡。具體來說，他們考慮了具有非加性輸入函數 σ σ 的漏積分發放（leaky integrate-and-fire）神經元。如果給定神經元的輸入較低，則輸入線性相加。稍大的輸入會被超線性放大，然后飽和至每個神經元的整體最大興奮度。雖然 [209] 中考慮的耦合描述了非連續動力學，但該耦合是非加性的，如 (5.3) 所示，且每個神經元的輸入非線性地依賴于其所有發出尖峰（spike）的輸入神經元的聯合狀態。除了同步活動的傳播 [209] 之外，這些非加性相互作用還允許高頻振蕩 [208] 和記憶過程 [158] 的出現。

5.3.4. 傳染、擴散及其他具有高階交互的網絡動力學。 雖然我們僅考慮由常微分方程確定的網絡動力學系統，但高階相互作用也出現在離散時間動力學系統或具有離散狀態空間的系統中。這包括，例如，單純形上的傳染動力學 [157, 92, 48, 151]，其中一個節點的傳染取決于兩個或更多節點的聯合狀態；或者具有非成對交互和重連的適應性選民模型 [155]。獲得對此類動力學分析見解的一種可能方法是捕捉高階交互的平均場方法：例如，這些方法可以揭示此類系統中的臨界轉變如何從次臨界變為超臨界，反之亦然 [182]。高階動力學過程的其他例子包括超圖上的意見形成和一致性過程 [95, 223, 224, 150]，擴散過程 [58, 57, 260, 247, 211]（另見 3.4 小節），以及復制者動力學 [8]。

最后，注意任何超圖都可以與其二分關聯圖（bipartite incidence graph）同一化，該圖捕捉節點和超邊之間的成對關聯關系（參見 4.3.2 小節）。在最近將耦合細胞框架推廣到高階網絡動力學的背景下 [4]，對于簇同步模式，一個給出了關于另一個的信息，但這幾種視角并不等價。

這進一步強調了一個觀點：關于網絡動力學系統中高階交互重要性的任何問題——因此也就是 5.2 小節中問題 (Q2) 和 (Q3) 的答案——都是微妙的。即使是具有加性交互的振子網絡（即連接可以簡單地由圖編碼），在（高階）相位約化中也會產生非加性的有效交互。換句話說，將圖上的網絡動力學系統的動力學約化到一個吸引的低維不變流形（如環面）——即系統維度的約化——是以更復雜的耦合結構為代價的，這種結構編碼了不變環面鄰域內向量場的非線性。從這個角度來看，同樣的動力學效應，例如不連續同步躍遷 [182]，可以在沒有高階交互的耦合非線性振子 [55] 和具有高階交互的相位振子 [272] 中被觀察到，這就不足為奇了：網絡動力學系統可能只是通過坐標變換相互關聯。這提供了一個機會，將具有高階交互的網絡動力學（具有特定網絡結構的動力學系統）與一般動力學系統理論的結果聯系起來。

6. 討論

開發用于建模和分析高階網絡的各種工具，為批判性思考以及在不同的應用中對所使用的工具類型進行甄別帶來了新的機遇。通常情況下，當數據以矩陣形式存在時，該矩陣會被解釋為圖的鄰接矩陣或加權鄰接矩陣。在許多情況下，這種解釋是合理的，并在應用領域帶來了令人興奮的新見解。例如，圖（如連接組或相互作用組）是成對關系數據的自然數學結構。然而，在其他時候，使用圖解釋是出于無奈——因為缺乏分析高階結構的工具，所以投影到圖集合上一直是進行有趣分析的少數幾種方法之一。然而，這種方法的代價是丟失了高階關系和結構，以及一些意義。例如，在幾篇論文中對將合作網絡分析為圖與分析為超圖進行了比較和對比，這些文章中的每一篇都說明了當把合作網絡視為超圖思考時可以獲得的新見解 [105, 170, 199, 274]。擁有用于高階網絡的工具，如本綜述中討論的那些，使得此類分析成為可能，并且重要的是，它促使我們在分析數據時對所做出的選擇更加自覺。在建模和分析方面，新工具的開發引出了以下問題：在做出建模決策時，我們應如何思考所做出的權衡？我們如何平衡可解釋性和便利性？而且，對于具有定量思維的人來說最重要的是，是否有辦法開發一個指導框架來幫助回答這些問題？

盡管這里討論的高階網絡的三個方面通常被分開研究（并由不同的學術群體研究），但它們是相互關聯的。一個例子是神經科學中的結構-功能關系：神經細胞的結構網絡及其連接的屬性如何與網絡動力學系統的動力學屬性相關聯？一方面，人們可以分析連接性本身的結構特征：無論是為小規模網絡（如胃神經節 [143] 或秀麗隱桿線蟲（參見 1.1.4 小節））顯式提取，還是使用諸如擴散張量成像等技術在大尺度上提取，這些數據都已從（高階）網絡的角度進行了分析。當然，這些神經系統會產生非加性高階效應發揮作用的動力學（參見 5.3.3 小節）。這些動力學最終決定了神經系統的功能。動力學本身——無論是來自神經記錄的實證數據，還是來自神經模型網絡動力學系統的合成數據——都可以被視為通過使用基于相關性的技術將其投影到（高階）網絡上而進行分析的數據 [25]。

新興的高階網絡領域開辟了令人興奮的新方向。雖然它有時可能看起來像是多個領域結果的拼湊，但我們相信通過交叉融合可以獲益良多；這篇綜合性的綜述和展望是朝著這個方向邁出的一步。我們期待在未來看到這些研究方向的成果。

https://ora.ox.ac.uk/objects/uuid:acfb9de6-9299-4b7b-86ed-51038304a9d7/files/rws859g36t