超圖的數(shù)學(xué)基礎(chǔ)（第二章）

Chapter 2 Mathematical Foundations of Hypergraph

超圖的數(shù)學(xué)基礎(chǔ)（第二章）

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

摘要

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

2.1 引言

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

2.2 超圖的預(yù)備知識

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

2.2.1 無向超圖

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

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

存在多種規(guī)則可用于確定頂點之間是否存在關(guān)聯(lián)。對于具有圖結(jié)構(gòu)的數(shù)據(jù)，可以通過使用成對邊（pairwise edges）和 k-跳（k-hops）來生成超邊組；對于沒有圖結(jié)構(gòu)的數(shù)據(jù)，可以通過使用特征空間中的鄰居來生成。這些方法的詳細(xì)描述見第 4 章。

2.2.2 有向超圖

現(xiàn)實世界與傳統(tǒng)無向超圖表示并不相符，因為超邊可能具有方向性。因此，有向超圖結(jié)構(gòu)的表示十分重要。在每條超邊中，頂點可進一步劃分為兩個集合：源頂點集與目標(biāo)頂點集。在有向超圖中，關(guān)聯(lián)矩陣的一個平凡定義[14]如下：

2.2.3 概率超圖

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

2.2.4 K-一致超圖

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

2.2.6 超圖上的權(quán)重

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

2.3 圖與超圖的比較

作為圖的推廣，圖與超圖之間的關(guān)系是一個基本問題。在本部分中，我們從四個方面詳細(xì)介紹圖與超圖之間的關(guān)系，即關(guān)聯(lián)的階數(shù)、表示方法、結(jié)構(gòu)轉(zhuǎn)換以及兩者上的隨機游走（原文為 random work）。

2.3.3 從超圖到圖的結(jié)構(gòu)轉(zhuǎn)換

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

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

2.4 總結(jié)

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

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