Chapter 2 Mathematical Foundations of Hypergraph

超圖的數學基礎（第二章）

https://link.springer.com/book/10.1007/978-981-99-0185-2

摘要

在本章中，我們介紹超圖的數學基礎，并給出用于促進對超圖結構深入理解與分析的數學符號。超圖由一組頂點和超邊組成，它是圖的一種推廣，其中加權超圖用于量化超邊或頂點的相對重要性。超圖也可分為兩大類，即無向超圖表示與有向超圖表示。后者進一步將一條超邊內的頂點劃分為源頂點集與目標頂點集，以對更復雜的關聯關系進行建模。此外，我們從結構轉換與表達能力的角度，討論了超圖與圖之間的關系。簡單圖與超圖之間最直觀的差異可從階的大小與鄰接的表達方式中觀察到。超圖可通過團展開、星展開和線展開轉換為簡單圖。此外，基于隨機游走與馬爾可夫鏈的證明，建立了具有邊獨立頂點權重的超圖與加權圖之間的關系。

2.1 引言

高階復雜網絡建模的重要性已在第1章中討論過。在本章中，我們介紹超圖的基礎知識。在超圖中，邊度通常高于簡單圖（簡單圖的邊度為2）。不同于圖結構僅能利用2度邊對成對連接進行建模，超圖能夠對實際數據之間遠比成對關系更為復雜的關聯關系進行建模。正因其對數據復雜關聯建模的多功能性與實用性，超圖上的機器學習已引起越來越多的關注。 超圖上的機器學習方法因其優勢，已被應用于眾多現實場景中。在計算機視覺領域，已利用超圖完成了廣泛的任務，包括圖像檢索[1]與3D物體分類[2]、視頻分割[3]、行人重識別[4]、高光譜圖像分析[5]、地標檢索[6]以及視覺跟蹤[7]。針對這些任務，可將大量對象嵌入到超圖結構中。在不同任務中，超圖結構可用于刻畫各類對象之間的關聯關系。在圖像檢索[3]中，不同圖像間的關聯可在超圖中建模，其中每個頂點表示一幅圖像，超邊可通過尋找相似的圖像特征生成。在3D物體分類[2]中，不同3D物體間的關聯可在超圖中建模，其中每個頂點表示一個3D物體，超邊可基于這些3D物體間的相似性生成。在行人重識別[4]中，可構建一個超圖結構，其中每個頂點代表一張個人圖像，超邊可基于特征空間中的相似性生成。類似的建模嘗試也已部署于醫學圖像分析與生物信息學研究中，用于基因識別[8, 9]、疾病預測[10, 11]、子類型識別[12]以及功能網絡分析[13]。 在詳細展開超圖計算范式、超圖建模及其他相關方法與應用之前，本章首先介紹超圖的預備知識及其多種表示形式。我們還從四個方面將超圖結構與圖結構進行了對比。

2.2 超圖的預備知識

此處簡要討論超圖的基本概念。表2.1提供了貫穿本章的超圖主要符號與定義。我們首先分別介紹無向超圖與有向超圖，隨后介紹K一致超圖、概率超圖、超圖與二分圖的關系，以及超圖上的權重。

2.2.1 無向超圖

傳統的超圖結構在頂點之間建立關聯，利用單條超邊連接多個具有關聯的頂點。在關聯矩陣 H 中，同一條超邊上的所有頂點都被賦值為 1。鄰接矩陣 H 按照公式 (2.1) 計算，其元素取值為 0 或 1。每一行代表超圖中的每個頂點，列代表所有超邊。每一列代表該超邊上的頂點集合。

給定如公式 (2.1) 計算的關聯矩陣 H H，所有元素取值為 0 或 1。值得注意的是，一條超邊上不同頂點的連接權重可能是不同的。例如，某些頂點在超邊中連接緊密且權重較高，而其他頂點權重可能較低。也就是說， H H 每一列的和為 1（或者不為 1，視具體應用和目標而定），其數值代表頂點在該超邊上的重要性。

存在多種規則可用于確定頂點之間是否存在關聯。對于具有圖結構的數據，可以通過使用成對邊（pairwise edges）和 k-跳（k-hops）來生成超邊組；對于沒有圖結構的數據，可以通過使用特征空間中的鄰居來生成。這些方法的詳細描述見第 4 章。

2.2.2 有向超圖

現實世界與傳統無向超圖表示并不相符，因為超邊可能具有方向性。因此，有向超圖結構的表示十分重要。在每條超邊中，頂點可進一步劃分為兩個集合：源頂點集與目標頂點集。在有向超圖中，關聯矩陣的一個平凡定義[14]如下：

2.2.3 概率超圖

在現實世界的關聯中，連接的強度不僅可以是二進制數，還可以是從零到一的連續數值。因此，關聯矩陣可能是一個元素范圍在 0 到 1 之間的連續矩陣，這被用來表示概率超圖。

2.2.4 K-一致超圖

在許多應用中，超圖中的超邊可能連接相同數量的頂點，這被稱為 k -一致超圖。在 k -一致超圖中，每條超邊恰好包含 k 個頂點，如圖 2.4 所示。在此定義下，簡單圖可以被視為超圖的一種特殊情況，即 2-一致超圖，其中每條超邊僅連接兩個頂點。

2.2.6 超圖上的權重

需要注意的是，超圖上存在不同的權重，這些權重為超圖結構的賦值提供了額外信息。這是一種在語義上更優選的超圖表示方式，因為超圖的不同組件，如頂點、超邊甚至子超圖，應該對關系建模產生不同的影響。例如，在推薦系統中，用戶畫像中的權重影響用戶屬性的分類。如果屬性分類不準確，基于該畫像的推薦和營銷的準確性可能會受到質疑。超圖上的主要權重信息類型是超邊權重和頂點權重，數值的大小分別指示了超邊和頂點的相對重要性。

2.3 圖與超圖的比較

作為圖的推廣，圖與超圖之間的關系是一個基本問題。在本部分中，我們從四個方面詳細介紹圖與超圖之間的關系，即關聯的階數、表示方法、結構轉換以及兩者上的隨機游走（原文為 random work）。

2.3.3 從超圖到圖的結構轉換

與簡單圖（其中所有邊的度數必須為 2）相比，超圖利用其無度數限制的超邊來編碼高階數據關聯（超越成對關系）。從某種意義上說，簡單圖可以被視為一種特殊情況，即超圖上的所有超邊度數均為 2。因此，超圖和圖是可以相互轉換的。目前，有許多方法可以將超圖轉換為簡單圖。常見的方法有團展開（clique expansion）、星展開（star expansion）和線展開（line expansion），分別如圖 2.12、2.13 和 2.14 所示。

與圖學習相比，在超圖學習中，數據在更高層次上相關，關聯模型也被擴展到了更高層級，從而在實踐中帶來了性能的提升。這只是圖和超圖本質中顯而易見的一部分。接下來，我們在隨機游走 [20] 和馬爾可夫鏈 [21] 的輔助下，從數學推導的角度深入探討圖與超圖之間的關系。隨后，我們對超圖和圖進行了數學上的比較。證明結論表明，從隨機游走的角度來看，具有邊獨立頂點權重的超圖等價于一個加權圖，而具有邊依賴頂點權重的超圖則無法簡化為加權圖。

2.4 總結

在本章中，我們介紹了超圖基礎的數學定義及其解釋。隨后，我們也展示了有向超圖的表示，它不同于無向超圖，代表了超邊內部頂點之間的關系。最后，我們從轉換和表達能力的角度討論了圖與超圖之間的關系。圖與超圖之間最直觀的差異體現在低階與高階表示以及鄰接矩陣與關聯矩陣上。團展開、星展開和線展開是將超圖轉換為簡單圖的方法。我們還從隨機游走的角度展示了圖與超圖之間的關系。具有邊獨立頂點權重的超圖等價于一個加權圖，而在圖/超圖的信息傳播過程中，具有邊依賴頂點權重的超圖無法簡化為加權圖。

原文鏈接： https://link.springer.com/book/10.1007/978-981-99-0185-2