超圖協同最優傳輸：度量與范疇性質

超圖協同最優傳輸：度量與范疇性質

Hypergraph Co-Optimal Transport: Metric and Categorical Properties

https://arxiv.org/abs/2112.03904

摘要

超圖捕獲了數據中的多路關系，因此它們在高階網絡分析、計算機視覺、幾何處理和機器學習中已得到諸多應用。在本文中，我們利用最優傳輸的相關要素，為研究超圖空間構建了理論基礎。通過在超圖的節點和超邊上賦予概率測度，并結合能夠捕獲局部與全局結構的關系信息來豐富超圖，我們獲得了一個用于研究全體超圖集合的通用且魯棒的框架。首先，我們基于Redko等人的協同最優傳輸框架引入了一種超圖距離，并研究了其理論性質。其次，我們將把超圖轉換為圖的常見方法形式化為超圖空間與圖空間之間的映射，并研究了這些映射的函子性質與Lipschitz界。最后，我們通過多個實例展示了我們的超圖協同最優傳輸（HyperCOT）框架的多功能性。

關鍵詞：超圖，超圖度量，最優傳輸，范疇論，超圖匹配

1 引言

對超圖的研究源于高階網絡分析。圖通常用于編碼網絡安全、生物學、社會學和物理基礎設施等復雜系統中的數據，其中節點代表實體，邊代表實體之間的成對關系。然而，現實世界的數據包含豐富的多路關系。例如，Patania 等人 [50] 研究了來自 arXiv 的科學論文合著關系，其中一篇論文代表了幾位作者之間的多路關系；Cencetti 等人 [16] 發現，在以異質動力學為特征的人類面對面交流中，高階交互無處不在。

這些多路關系能更好地被超圖捕獲。一個超圖由一個節點集合和一個節點子集集合組成，其元素被稱為超邊。超圖推廣了圖的概念，圖僅僅是每個超邊恰好包含兩個節點的超圖。例如，超圖可用于表示分子結構，其中節點是單個原子，超邊代表原子對之間的共價鍵或多個原子之間的多中心鍵（見 [8, 第7.1章] 和 [39]）。超圖還可以對細胞網絡進行建模 [37]，其中蛋白質復合物是由多個蛋白質組成的超邊。Lotito 等人證明了高階模體在社會學、生物學和技術領域的多個超圖數據集 [45] 中所具有的信息價值。

超圖也出現在計算機視覺、幾何處理、模式識別和機器學習的應用中，在這些領域中，在兩個特征集之間建立對應關系是一個基本問題。對應問題傳統上被表述為圖匹配問題 [32, 70]：每個圖的構建均以節點表示特征，以邊表示特征之間的成對關系。例如，在幾何處理中，特征的絕對位置不如其成對關系重要，例如在施加平移和旋轉不變性時。然而，在建立對應關系時，成對關系不足以納入特征之間的高階關系——這可以通過超圖匹配問題來解決 [17, 42]。

近年來，Gromov-Wasserstein (GW) 框架——最初是作為比較度量測度空間的工具而開發的 [46, 47]——已被擴展到概率圖匹配任務中 [19, 22, 34, 63, 71, 75, 76]。該框架的詳細內容見第2.1節，但其大致思路如下。最優傳輸度量通常用于比較公共度量空間上的概率分布，并被廣泛認為是量化幾何測量中不確定性的強大框架 [52, 62]。相比之下，GW 距離用于獲取不同空間之間的對應關系，從而允許對先驗不可比的空間進行比較 [46, 47]。GW 距離基于尋找兩個度量空間中點之間的概率對齊，以最小化整體度量失真目標。該方法的諸多優勢包括可通過梯度下降 [28, 53] 或反向傳播 [74] 進行計算，在圖劃分 [21, 75] 等任務中達到最先進的性能，以及具有底層的黎曼理論框架 [20, 65]。這些成功推動了面向超圖的 GW 框架的開發，這也是本文的目標。我們的貢獻包括：

• 我們擴展了 Redko 等人 [55] 的協同最優傳輸（co-optimal transport）框架，以定義一種基于最優傳輸的超圖間距離。為了奠定堅實的理論基礎，我們引入了一種廣義的超圖概念，稱為測度超網絡（measure hypernetwork），見第 2.2 節。隨后，我們建立了超圖距離的基本性質；特別是，我們證明了它是測度超網絡空間上的偽度量（pseudometric），該偽度量在模去距離為 0 的等價關系后，誘導了測度網絡空間上的完備測地度量（Theorem 1）。
• 我們在測度（超）網絡空間上引入了范疇結構。通過這一視角，我們將把超圖轉換為圖的常見變換（例如，關聯圖、團擴展和線圖）作為從超網絡范疇到網絡范疇的函子進行研究。我們還研究了它們關于我們的超網絡距離以及網絡空間上的 GW 距離的 Lipschitz 性質。我們證明了關聯圖映射是將我們的距離映射到 GW 距離的一種新變體的函子等距映射（Theorem 10）。接著，我們引入了團擴展和線圖映射的單參數族，并證明了它們是 Lipschitz 函子（Theorem 11）。
• 我們獲得了一些關于測度（超）網絡范疇的結構結果。命題 17 展示了文獻中某些度量的同構概念與范疇論意義上的同構是等價的。我們范疇中各種極限構造的（不）存在性在命題 21 和 22 中得以確立。
• 我們在第 5 節通過多個示例展示了我們要用于超圖匹配和比較的開源計算框架 [1]。我們的方法被整合到一個基于超圖簡化拓撲算法 [78] 的框架中；特別是，我們的超圖距離被用于突顯現實世界數據集中感興趣的簡化層級。

  1.1 相關工作

超圖度量、相似度與不相似度測量。 盡管有大量數據可以建模為超圖，但文獻中對超圖之間的度量尚未進行廣泛探索。Karonski 和 Palka [36] 將定義在同一節點集上的超圖視為聚類，并定義了這些聚類之間的 Marczewski–Steinhaus (MS) 距離。MS 距離是在集合的 Hausdorff 度量的一種推廣基礎上修改得到的。Karonski 和 Palka 還討論了由具有相同終端頂點集的有向樹（arborescences）生成的超圖之間的距離。與 MS 距離相比，我們的超圖距離不要求超圖定義在同一組節點上；更重要的是，我們的距離具有良好的度量性質，顯式編碼了節點與超邊之間的結構關系，并自然衍生出有意義的超圖匹配。Lee 等人 [42] 將編輯距離從圖推廣到了超圖。然而，這種距離并不實用，因為圖編輯距離的計算是 NP 難的 [77]，且近似是 APX 難的 [44]。Smaniotto 和 Pelillo [61] 最近利用最大公共子超圖定義了屬性超圖之間的距離；然而，計算兩個超圖之間的最大相似性子超圖同構是 NP 完全的。相比之下，通過遵循協同最優傳輸的優化程序，我們的超圖距離可以被高效地近似。另一種超圖比較方法見于 [67]，該方法將超圖轉換為圖，并應用標準的圖相似度或不相似度度量。超圖也可以被編碼為張量 [3]，從而可以通過它們的張量表示進行譜比較。[27] 中的工作描述了一個原則性的超圖匹配框架，并提議使用該框架超越等距不變形狀匹配，以獲得在相似、仿射和射影變換下的不變性。然而，[27] 中的框架為每個超邊構建固定大小的超圖，不適用于輸入數據為任意超圖的情況。相比之下，我們的超圖距離可以接受任意一對超圖作為輸入。

最優傳輸與 Gromov-Wasserstein 距離。 如上所述，Gromov-Wasserstein (GW) 距離本質上只需要對要比較的空間中編碼成對關系信息的方陣 [19]，因此非常適合通過鄰接矩陣、最短路徑距離或譜表示來比較圖 [21, 71, 76]。然而，超圖通常編碼的不僅僅是成對關系；我們將 GW 框架擴展到超圖的策略是直接處理多路關系（在有限設置中建模為編碼節點-超邊關系的矩形矩陣），并利用 [55] 中最近開發的協同最優傳輸框架。使用該框架，我們能夠在比較超圖時同時推斷節點-節點和超邊-超邊的對應關系。

2 超網絡：理論形式化

本節介紹了測度超網絡（measured hypernetworks）的基本概念及其之間的距離。

2.1 背景：測度網絡

圖（graph）是一個二元組 ( V , E ) ，其中 V 是節點（nodes）的集合， E 是 V 的 2 元子集的集合，其中每一個子集被稱為一條邊（edge）。下文給出了圖這一概念的深遠推廣。

2.2 測度超網絡與超網絡距離

超圖是一個二元組 ( X , Y ) ，其中 X 是節點的集合， Y 是 X 的子集族，其中的每個子集被稱為一條超邊。圖 1 展示了一些簡單的超圖以及不同的超圖可視化技術。

我們現在準備好定義測度超網絡之間的距離，這是 Redko 等人在 [55] 中引入的協同最優傳輸框架的直接擴展。

2.3 超網絡距離的性質

在下述示例中，我們指出，基本弱同構的概念為描述超圖簡化中使用的一種過程（稱為節點與超邊坍縮 [78]）提供了一種形式化框架。

3 圖化

超圖分析與機器學習中的一個常用技術是將超圖轉換為傳統圖，后者具有更易處理的結構（例如，[1, 54, 67, 73]）。在本節中，我們將圖化形式化為從測度超網絡范疇到測度網絡范疇的函子研究。

3.1 超圖到圖的變換

。。。。。。。

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