超圖不變量與變換的穩定性

超圖不變量與變換的穩定性

Stability of Hypergraph Invariants and Transformations

https://arxiv.org/pdf/2412.02020

摘要：

圖是復雜系統中對成對交互進行建模的基本工具。然而，許多現實世界系統涉及多方交互，這些交互無法被標準圖完全捕獲。超圖通過允許邊連接任意數量的頂點來推廣圖，提供了一個更具表達力的框架。在本文中，我們受度量空間的Gromov-Hausdorff距離啟發，在超圖空間上引入了一種新的度量。我們建立了常見超圖變換的Lipschitz性質，這些變換將超圖映射為圖，其中包括一種與單鏈接層次聚類有關聯的新型圖化方法。此外，我們通過來自基本匯總統計量和拓撲數據分析技術的不變量，推導出了超圖距離的下界。最后，我們在最優傳輸的背景下探討了代價函數的穩定性性質。我們在這一方向上的結果考慮了Hausdorff映射的Lipschitz性，以及代價函數極限下非負交叉曲率性質的保持性。

1 引言

圖是表示包含交互作用的數據的標準形式，在生態學[16]、基因調控[30]、蛋白質柔性[19]、社交網絡分析[10]以及眾多其他領域的應用中無處不在。由于其固有結構，圖僅能捕獲對象之間的成對交互，而在對復雜系統進行建模時，考慮多方交互往往是自然的。超圖是一種類圖結構，它更一般地允許任意數量的頂點通過一條邊相互關聯。超圖能夠展現捕獲諸如生態系統營養級之間或合作網絡中論文之間復雜交互作用所需的多種連接可能性，而這些在更基礎的圖表示中將會丟失[15]。圖1展示了一個源自基因關系數據集的超圖示例。

本文從度量幾何的視角探討圖與超圖理論中的若干問題。鑒于其在純數學與應用數學中的普遍性，亟需能夠比較圖結構（尤其是定義于不同節點集上的圖結構）的方法；近幾十年來得到充分發展的一個途徑是通過類Gromov-Hausdorff構造對它們進行比較。Gromov-Hausdorff距離著名地為緊度量空間賦予了度量結構[18]，且近年來已被擴展用于比較（廣義）圖結構[6, 8]。具體細節見下文第2.1節，但此類圖距離的基本機制在于：在待比較圖的節點之間尋找一種對齊方式，使得某一畸變函數最小化。

本文中，我們將圖之間的Gromov-Hausdorff距離推廣為超圖空間上的一種新度量。由于超圖的邊編碼了節點間非嚴格成對的關系，超圖間的比較需同時建立節點與邊的對齊；Gromov-Hausdorff距離的結構為此類推廣提供了自然形式，具體見定義2.13。盡管該新度量在現實超圖數據分析中具有潛在應用，但本文的重點在于該度量的理論性質。具體而言，本文的貢獻集中于該度量的穩定性性質——即證明某些超圖不變量定義了至相對簡單表示空間的Lipschitz映射。

1.1 主要結果與大綱

我們現在概述本文并描述我們的主要貢獻：

1.2 相關工作

除了上述指出的相關工作和結果引用外，我們要將本文的方法與文獻 [9] 中的作者（及其合作者）的方法進行比較。那篇論文也考慮了類超圖對象通用模型上的度量；其中的主要區別在于，超圖的節點和邊被賦予了概率測度，從而使得最優傳輸理論中的方法變得適用。具體而言，那里的構造借用了 Mémoli 的 Gromov-Wasserstein 距離 [25, 7] 以及最近引入的 co-optimal transport（協同最優傳輸）框架 [29] 的思想。圖化（graphifications）的 Lipschitz 性質在 [9] 中也被考慮過，但這里使用的證明技術是新穎的（而且我們相信，事實上，它們可以被調整以提供比 [9] 中出現的更好的 Lipschitz 常數）。此外，本文使用的是 Gromov-Hausdorff 距離的一種變體（而不是 Gromov-Wasserstein 距離），這可以說是一個在理論上更基礎的構造。

我們在引言的最后對闡述風格做一點說明。由于我們的一些結果是將 [26, 6, 28, 8, 22] 的結果擴展到超網絡的設定，我們通常旨在對我們的貢獻進行精簡的陳述。我們關于超網絡的所有結果都是新穎的，但是當它們的證明可以通過對度量空間或網絡背景下現有證明進行微小調整而得出時，我們會省略或簡述證明，并指引讀者閱讀文獻中的相關結果——例如命題 2.17、定理 4 和定理 5 就是這種情況。另一方面，我們的幾個結果是完全新的，或者需要與之前出現過的不同的證明技術，在這種情況下我們會提供完整的細節——參見，例如，定理 3 和定理 7。

2 超網絡與超網絡距離

本節介紹了全文將要研究的主要結構。首先，我們在定義中將（加權）超網絡定義為類度量空間結構，這為超圖的概念提供了一種自然且深遠的推廣。其次，我們擴展了 Gromov-Hausdorff 距離的構造，以定義超網絡結構之間的一種新距離。我們首先回顧一些相關背景。

2.1 網絡 Gromov-Hausdorff 距離

Gromov-Hausdorff (GH) 距離最早由 Edwards [14] 研究，后來被 Gromov [18] 重新發現并普及，它是度量幾何中的一個基本工具。我們參考 [2] 作為其基本性質的標準參考資料，并參考 [26]，其中建立了進一步的重要性質，例如基于度量不變量的某些下界。

2.2 加權超網絡

超圖的概念是對圖的概念的推廣：超圖中的邊允許連接任意數量的頂點，而非僅兩個。我們如下對此進行精確化。

超圖通常被可視化為維恩圖，其中節點集繪制為點的集合，超邊則描繪為陰影區域——參見圖2的示例及其二值關聯函數。圖5展示了一個加權超圖及其對應的加權關聯函數。通過放棄 Y ? P ( X ) 的要求，可獲得一種靈活的超圖模型。仿照文獻[6]在圖的一般模型設定中以及文獻[9]在帶有附加概率數據的超圖模型（即所謂的測度超網絡）設定中使用的術語，我們如下定義我們的研究對象。

2.3 超網絡之間的距離

我們現在定義超網絡之間的一種距離，該距離在結構上類似于定義2.1中的網絡Gromov-Hausdorff距離 。

2.4 超網絡距離的映射表述

下一個結果表明，超網絡 GH 距離的映射表述等于定義 2.13 中定義的超網絡 GH 距離。這模仿了文獻 [6, 命題 9] 中證明的網絡 GH 距離的情形。此處的證明是相似的，因此我們省略它。我們的重構形式將在下文第 4.2 節中用于將超網絡 GH 距離與持久同調聯系起來。

3 圖化

超圖分析中的一種常用技術是將超圖轉換為具有更易處理結構的傳統圖 [31]。在本節中，我們考慮幾種特定的圖化（graphifications），或者說將（加權）超圖轉換為（加權）圖的操作。本節的目標是證明這些操作關于 是 Lipschitz 的。

3.1 圖化映射的定義

直觀上，二部圖化通過定義兩個節點集來表示超圖——一個對應于原始超圖的節點，另一個對應于超邊——并以一種反映原始超圖結構的二部方式將它們連接起來。

應當注意到，二部圖化是可逆的，即原始超圖可以從其二部表示中重構出來。這一點將在下文的第 3.2 節中得到驗證。后續的操作不具有相同的性質。

這些圖化操作的簡單示例在圖 3 中展示。團擴展和線圖映射在網絡函數層面的行為在圖 4 中明確展示。

3.2 二部網絡

3.3 親和網絡

定義3.3中引入的團擴展和線圖圖化僅考察節點與超邊之間的局部結構：假設 ω ω 編碼了一個加權關聯矩陣，團擴展僅在存在某個同時包含兩個節點的超邊時才連接它們，類似的情形也適用于線圖。我們在下文提出一種稱為親和網絡的新構造，它以一種能更全局地理解節點（或超邊）如何相互關聯的方式，擴展了上述圖化方法。我們首先從一些預備概念開始。

我們將濫用記號，并在此后省略能量與親和度的下標。泛函的定義域由上下文即可明確，這將使后續方程更為簡潔。我們現在準備定義一對新的圖化映射。

注記 3.9. 推論 3.8 與文獻 [9, 定理 11] 密切相關，該文獻為在節點和超邊集上引入權重（以概率測度的形式）的團擴展和線圖映射的版本建立了類似的 Lipschitz 界。那篇文章并未考慮廣義親和網絡構造，且其證明策略與定理 3 和推論 3.8 的證明策略不同。我們在此給出的證明提供了改進的 Lipschitz 界，并且我們推測它們可以被調整以加強加權情形下的結果。

然而，節點1和5之間的親和度為0.4，這是它們之間所有鏈上的最大能量，這樣一條鏈可以通過超邊B構建。如果我們要計算完整的節點親和網絡，其加權鄰接矩陣可見圖6（左）。我們在圖6（右）中通過類似樹狀圖（dendrogram）的圖（參見[3]）進一步表示了該超網絡的親和結構。網絡的節點出現在其對角線元素所在的層級（因為這是其最大值），然后當節點子集的每個元素都大于或等于該值時，節點在該層級被聚類。

4 下限

本節基于經典Gromov-Hausdorff距離背景下出現的類似下界[26, 8]，介紹了超網絡Gromov-Hausdorff距離的幾個可計算下界。

4.1 基本不變量

超網絡GH距離的第一組下界涉及有限超網絡的幾個不變量。

由此得到的網絡不變量對應于文獻[26, 第3節]（在度量空間背景下）和[8, 第4節]（在網絡背景下）中曾考慮過的那些不變量。

本節的主要定理表明，這些不變量關于超網絡Gromov-Hausdorff距離是穩定的。為了精確地陳述該定理，我們回顧一下度量空間 ( Z , d ) 中一對子集 A 和 B 之間的Hausdorff距離由下式給出：

我們得到以下直接推論。

推論 4.2. 定義 4.1 中的每個超網絡不變量在弱同構下都是不變的，即定理 4 中引入的比較這些不變量的方法在超網絡弱同構時結果為零。

例 4.3. 考慮圖 7 中所示加權函數的兩個超網絡。這些超網絡的各種不變量測量值記錄在表 1 中。方程 (21) 和 (20) 給出了 0.05 的下界。此外，在考慮節點不變量時，方程 (17)、(18) 和 (19) 也給出了相同的 0.05 下界。然而，如果我們考慮后三個不變量的邊變體，則三者均得到 0.15 的下界。

4.2 持久同調

持久同調是拓撲數據分析（TDA）的一種方法，特別適用于理解數據集的底層拓撲結構，并在計算生物學、圖像分類、網絡分析等諸多領域有大量應用；關于這些應用的進一步參考文獻，請參見綜述文章 [13, 17, 1]。在本小節中，我們假設讀者熟悉 TDA 和持久同調的基本構造，如專著 [11] 中所述。

最常見的情形是，持久同調方法應用于具有單純映射的單參數單純復形族——這種結構被稱為過濾單純復形（filtered simplicial complex）。我們現在描述一個自然關聯于任意有限超圖的過濾單純復形。下文所見的 Dowker 過濾是文獻 [6] 中網絡 Dowker 過濾的推廣，其起源可追溯至 [12]。

5 代價函數的穩定性

前兩節考慮了超網絡Gromov-Hausdorff距離的下界，其靈感來源于將超網絡視為超圖廣義模型的視角。在本節中，我們轉變這一視角，將超網絡視為代價函數，例如最優傳輸理論中出現的那些（參見例2.8）。由于這一轉變，我們放棄了最后兩節中的有限性假設，轉而研究一般的超網絡。

5.2 非負交叉曲率

在近期的工作 [22] 中，作者引入了最優傳輸理論 [24] 中著名的 Ma-Trudinger-Wang 條件的一個綜合版本（synthetic version）。與其中使用的形式體系相比，可以立即看出它很好地契合了本文提出的框架。我們回顧 [22, 定義 1.1]，并使用本文的術語進行陳述。

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