超圖計算 Hypergraph Computation

第一部分介紹超圖計算的基礎(chǔ)知識

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

前言

人工智能如今已無處不在，并在全球范圍內(nèi)推動著工業(yè)與日常生活的發(fā)展。我們正處于“大數(shù)據(jù)”時代，可以獲取海量信息，這些信息過于繁雜，人類已難以自行處理。在計算機視覺和社交媒體等各個領(lǐng)域，這些大數(shù)據(jù)背后甚至蘊含著極其復(fù)雜的關(guān)聯(lián)關(guān)系。例如，圖像中像素間的復(fù)雜關(guān)聯(lián)揭示了其語義信息，而社交帖子間的不同類型關(guān)聯(lián)則能推斷出用戶的情緒。因此，開發(fā)有效的人工智能方法來挖掘此類復(fù)雜的數(shù)據(jù)關(guān)聯(lián)，已成為一項緊迫卻充滿挑戰(zhàn)的任務(wù)。

圖已被廣泛用于表達(dá)數(shù)據(jù)關(guān)聯(lián)。圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，由頂點集合與邊構(gòu)成，用于表示頂點之間的成對關(guān)聯(lián)。近年來，圖學(xué)習(xí)與圖神經(jīng)網(wǎng)絡(luò)在研究領(lǐng)域與工業(yè)界均引起了廣泛關(guān)注，并已成為十分熱門的課題。需要指出的是，現(xiàn)實世界遠(yuǎn)比單純的成對連接復(fù)雜得多，因此基于圖的方法在高階關(guān)聯(lián)建模方面仍存在局限性。

超圖作為圖的一種推廣形式，能夠?qū)?shù)據(jù)間的此類高階關(guān)聯(lián)進行刻畫，并在過去數(shù)十年間得到了研究。近年來，超圖相關(guān)人工智能方法的研究日益盛行，并已被應(yīng)用于計算機視覺、社交媒體分析等領(lǐng)域。我們注意到，目前尚缺一本能夠系統(tǒng)介紹該領(lǐng)域最新成果的理論專著，因此著手開始了本書的編寫工作。我們將這些嘗試總結(jié)為一種全新的計算范式，稱為“超圖計算”，即利用超圖表達(dá)數(shù)據(jù)底層的高階關(guān)聯(lián)，進而針對不同的應(yīng)用在超圖上開展語義計算。

在本書中，我們介紹了超圖計算的最新進展，內(nèi)容涵蓋從超圖建模到超圖神經(jīng)網(wǎng)絡(luò)。超圖計算的應(yīng)用也得到了討論。我們還總結(jié)了超圖計算領(lǐng)域的最新成果與實用工具。本書既可被視為一部理論著作，亦可作為指導(dǎo)如何在實踐中運用超圖計算的手冊。

書籍組織結(jié)構(gòu)

本書共包含 13 章，分為 3 個部分。第一部分介紹超圖計算的基礎(chǔ)知識。在此部分中，第 1 章闡述了超圖的基本知識、應(yīng)用與發(fā)展歷史。第 2 章介紹了超圖的數(shù)學(xué)基礎(chǔ)。第 3 章提供了超圖計算的三種通用范式。

第二部分聚焦于超圖建模與學(xué)習(xí)技術(shù)。超圖計算的第一步是構(gòu)建超圖以刻畫數(shù)據(jù)間的高階關(guān)聯(lián)，該內(nèi)容在第 4 章中給出。第 5 章隨后提供了典型的超圖計算任務(wù)，包括標(biāo)簽傳播、數(shù)據(jù)聚類、代價敏感學(xué)習(xí)以及鏈接預(yù)測。我們在第 6 章進一步介紹了用于超圖優(yōu)化的超圖結(jié)構(gòu)演化方法。第 7 章介紹了超圖上的神經(jīng)網(wǎng)絡(luò)。超圖計算的實際應(yīng)用需要具備處理大規(guī)模數(shù)據(jù)的能力，因此，我們在第 8 章對大規(guī)模超圖計算進行了廣泛介紹。

第三部分介紹了超圖計算在若干領(lǐng)域的應(yīng)用，包括第 9 章的社交媒體分析、第 10 章的醫(yī)學(xué)與生物應(yīng)用，以及第 11 章的計算機視覺。本部分還在第 12 章介紹了 DeepHypergraph 庫——一個基于 Python 的超圖計算庫，并在第 13 章介紹了超圖計算研究的未來發(fā)展方向。

第1章 引言

摘要 數(shù)據(jù)之間的高階關(guān)聯(lián)廣泛存在于各種實際應(yīng)用中。與僅能建模兩個主體之間成對關(guān)系的簡單圖相比，超圖是一種靈活且具有代表性的模型，可用于表述高階關(guān)聯(lián)。基于超圖模型，已有大量研究致力于設(shè)計計算框架并分析高階關(guān)聯(lián)。在本章中，我們簡要介紹超圖計算，包括其背景、定義、歷史、近期挑戰(zhàn)與研究目標(biāo)。

1.1 背景

許多自然系統(tǒng)與人工系統(tǒng)的基本要素彼此之間存在依賴關(guān)系，需要關(guān)聯(lián)建模與分析方法來研究這些依賴。從不同視角來看，圖結(jié)構(gòu)無處不在，總體而言，現(xiàn)實世界中的所有對象都是基于其與其他對象的連接關(guān)系來定義的。這些連接可以描述為圖，圖是許多場景中的一種常見數(shù)據(jù)結(jié)構(gòu)。例如，圖可以描繪城市中的路徑，其中每條路徑用一條邊表示，以展示兩個位置之間的空間連接。圖也被用于航空路線圖，其中每個頂點代表一個機場，每條邊代表一條航線。

近年來，最具挑戰(zhàn)性的數(shù)據(jù)處理問題來自于關(guān)聯(lián)數(shù)據(jù)，而不僅僅是離散數(shù)據(jù)。如何挖掘數(shù)據(jù)背后潛在的連接關(guān)系，已成為許多應(yīng)用中一項緊迫且重要的任務(wù)。通常，圖被用來表述數(shù)據(jù)之間的此類關(guān)聯(lián)。圖是一種非線性數(shù)據(jù)結(jié)構(gòu)，由一組頂點和邊組成。其中，圖中的頂點代表待分析的主體，圖中的邊則是連接圖中兩個頂點的線段。圖1.1展示了一個圖的示例。

作為建模數(shù)據(jù)間成對關(guān)聯(lián)的常用方式，系統(tǒng)中的組成部分可由圖的頂點表示，而組成部分之間的關(guān)聯(lián)則由邊來描述。通過這種方式，關(guān)聯(lián)模式被抽象為圖的拓?fù)浣Y(jié)構(gòu)。在過去幾十年中，由于計算能力的限制，圖論在實際應(yīng)用中并不容易實施。近年來，隨著信息技術(shù)與計算能力的進步，圖論展現(xiàn)了其實用價值。隨著數(shù)據(jù)規(guī)模的增長，科學(xué)家們提出了網(wǎng)絡(luò)科學(xué)的概念。網(wǎng)絡(luò)科學(xué)的研究可應(yīng)用于多個領(lǐng)域。例如，通過研究互聯(lián)網(wǎng)上終端之間的連接關(guān)系，可以估計網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)男省θ穗H關(guān)系的研究有助于理解人們相互交流、傳播信息以及形成社群的方式。研究傳染病的傳播鏈有助于及時預(yù)測風(fēng)險，從而阻斷傳播途徑并防止其擴散。人們還發(fā)現(xiàn)，許多生物、社會、信息及其他真實網(wǎng)絡(luò)在其要素之間的連接上具有非平凡的結(jié)構(gòu)模式。這些模式反映了整個網(wǎng)絡(luò)有意義的特征。例如，小世界現(xiàn)象（網(wǎng)絡(luò)中的平均路徑長度不會隨網(wǎng)絡(luò)規(guī)模的增大而顯著增加）廣泛存在于社交網(wǎng)絡(luò)中[1]。另一個例子是無標(biāo)度網(wǎng)絡(luò)[2]，其中頂點度分布遵循冪律分布，這種現(xiàn)象在某些生物代謝網(wǎng)絡(luò)中已被觀察到[3]。

需要注意的是，世界遠(yuǎn)比單純的成對連接復(fù)雜得多。典型例子包括社交網(wǎng)絡(luò)、蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)以及腦網(wǎng)絡(luò)。在社交網(wǎng)絡(luò)中，用戶的個體特征與用戶之間的交互模式相關(guān)。具有相似特征的用戶更可能相互連接以形成社交群體。用戶的社交關(guān)系也會影響其畫像刻畫。我們注意到，這些用戶之間的關(guān)聯(lián)不僅僅是成對連接，還包括群體式的連接，這比成對連接更為復(fù)雜。圖1.2展示了一個社交連接的示例，其中每個用戶可能與兩個或更多其他用戶或項目具有不同類型的連接。

在人腦網(wǎng)絡(luò)中，大腦皮層包含超過1011個神經(jīng)元，而具有相似功能與連接的一簇神經(jīng)元形成一個核團。這些核團可進一步劃分為不同腦區(qū)，從而形成一個多層級、多尺度的復(fù)雜腦網(wǎng)絡(luò)。例如，全腦圖譜包括島葉與扣帶回、額葉、枕葉、頂葉等區(qū)域，這些區(qū)域可進一步細(xì)分為AAL圖譜[4]中提供的90個腦區(qū)，如海馬與旁海馬。每個神經(jīng)元可擁有超過10,000個突觸，這些突觸可將腦內(nèi)的神經(jīng)元與身體其他部位的神經(jīng)元連接，或?qū)⑸窠?jīng)元與肌肉連接。神經(jīng)元之間的連接極為復(fù)雜，盡管圖是建模此類腦內(nèi)關(guān)聯(lián)的典型方式，但很難用圖來精確表述這些連接。

此類復(fù)雜關(guān)聯(lián)，即高階關(guān)聯(lián)而非成對關(guān)聯(lián)，在現(xiàn)實世界數(shù)據(jù)中非常普遍。為了研究這些復(fù)雜系統(tǒng)，有必要對其要素之間的高階關(guān)系進行表征與分析。實證研究表明，系統(tǒng)的關(guān)聯(lián)模式往往在系統(tǒng)功能中扮演重要角色。近年來，越來越多的研究者開始關(guān)注這一領(lǐng)域，并應(yīng)用高階關(guān)聯(lián)建模與分析方法。

在圖與網(wǎng)絡(luò)科學(xué)的機器學(xué)習(xí)發(fā)展初期，僅使用圖來建模網(wǎng)絡(luò)或關(guān)聯(lián)，系統(tǒng)要素之間的關(guān)聯(lián)通常由圖的拓?fù)浣Y(jié)構(gòu)來描述。因此，成對連接可以在圖中得以描述，但系統(tǒng)中大量的語義信息可能丟失，網(wǎng)絡(luò)中的描述性特征也無法被提取。一些被廣泛討論的網(wǎng)絡(luò)屬性，如度中心性、半局部中心性與接近中心性，均基于此類靜態(tài)單一網(wǎng)絡(luò)模型。數(shù)據(jù)背后潛在的高階信息不得不退化為成對信息進行處理，這可能導(dǎo)致嚴(yán)重的信息損失。隨著大數(shù)據(jù)的發(fā)展，數(shù)據(jù)的爆炸式增長展現(xiàn)出其復(fù)雜性與多樣性，這呼喚更復(fù)雜的數(shù)據(jù)建模方法。針對復(fù)雜數(shù)據(jù)類型、復(fù)雜拓?fù)浣Y(jié)構(gòu)與復(fù)雜連接模式的網(wǎng)絡(luò)建模方法應(yīng)運而生。例如，社交網(wǎng)絡(luò)中個體之間的社交親密度可有強弱之分，具有頂點間關(guān)聯(lián)權(quán)重分布的系統(tǒng)可采用加權(quán)網(wǎng)絡(luò)[5]進行建模。此外，電力網(wǎng)絡(luò)與通信網(wǎng)絡(luò)在基礎(chǔ)設(shè)施建設(shè)中相互依賴：通信網(wǎng)絡(luò)的頂點向電力網(wǎng)絡(luò)的頂點提供控制信號，而電力網(wǎng)絡(luò)的頂點則向通信網(wǎng)絡(luò)的頂點供應(yīng)電力。不同網(wǎng)絡(luò)之間的相互依賴關(guān)系可采用依賴圖[6]進行建模。另一個例子是航空運輸網(wǎng)絡(luò)，其中頂點之間的航線可能屬于不同的航空公司。針對對象類型與關(guān)聯(lián)關(guān)系的異質(zhì)性，研究者提出了多層網(wǎng)絡(luò)或圖的概念[7]。最后一個例子是物種網(wǎng)絡(luò)中的生態(tài)食物鏈會隨季節(jié)性環(huán)境條件的變化而改變。對于動態(tài)系統(tǒng)，研究者引入了時序網(wǎng)絡(luò)[8]的概念來表述主體之間的關(guān)聯(lián)。

盡管基于圖的方法已發(fā)展數(shù)十年并取得了巨大進展，但它們?nèi)源嬖诰窒扌浴＿@些圖模型能更好地表述系統(tǒng)中元素之間的二元關(guān)系，但可能忽略三個或更多元素之間的高階關(guān)聯(lián)。近年來，許多研究表明，在大多數(shù)應(yīng)用中，對高階關(guān)聯(lián)進行建模與優(yōu)化甚至更為重要[9–11]。例如，在生物圈系統(tǒng)中，物種之間的高階相互作用確保了物種多樣性的穩(wěn)定[10]。不同網(wǎng)絡(luò)的高階特征可有效區(qū)分其所屬領(lǐng)域[11]。隨著網(wǎng)絡(luò)科學(xué)的快速發(fā)展，數(shù)據(jù)與關(guān)聯(lián)的復(fù)雜性迅速增加。在生物信息、社會計算與圖像處理等領(lǐng)域，存在大量多模態(tài)、異構(gòu)、高層級的數(shù)據(jù)，亟需有效的高階關(guān)聯(lián)建模與優(yōu)化方法。

作為計算機科學(xué)、物理學(xué)與生物學(xué)等多個不同領(lǐng)域交叉研究的主題，高階關(guān)聯(lián)建模與優(yōu)化在近幾十年受到了廣泛關(guān)注。現(xiàn)實世界中許多系統(tǒng)存在大量高階關(guān)系[12]。例如，在社交網(wǎng)絡(luò)中，人們以三人或更多人為一組進行交流；在學(xué)術(shù)網(wǎng)絡(luò)中，多位作者合作撰寫一篇文章。生物網(wǎng)絡(luò)中的蛋白質(zhì)相互作用可能發(fā)生在多個蛋白質(zhì)之間，基因表達(dá)則由生物分子之間的高階相互作用驅(qū)動[13]。元素之間的高階關(guān)聯(lián)難以用簡單圖的拓?fù)浣Y(jié)構(gòu)來描述。在此情況下，研究者引入了相應(yīng)的數(shù)學(xué)表達(dá)形式，如集系[14]、單純復(fù)形與超圖[15]。然而，如何將這些數(shù)學(xué)表達(dá)形式部署到計算范式中仍是一個開放性問題。高階關(guān)聯(lián)的復(fù)雜度遠(yuǎn)高于成對關(guān)聯(lián)，這為計算范式帶來了新的挑戰(zhàn)。

超圖作為圖的推廣，能夠表述數(shù)據(jù)之間的高階關(guān)聯(lián)，近年來得到了深入研究。在本書中，我們將介紹超圖計算的最新進展，從超圖建模到超圖神經(jīng)網(wǎng)絡(luò)。下文我們首先介紹超圖的基本定義，然后展示超圖的應(yīng)用與研究歷史。最后，我們總結(jié)我們在超圖計算方面的工作以及本書的結(jié)構(gòu)。

1.2 超圖的定義

超圖是離散數(shù)學(xué)中的一個重要概念，它是圖的推廣。因此，超圖的許多概念都可以參照眾所周知的圖的定義來定義。超圖被定義為一對超頂點集（hypervertex set）和超邊集（hyperedge set）。超頂點集，也稱為頂點集，是一個有限集，而超邊代表頂點集的子集。由于超邊可以連接任意數(shù)量的頂點，因此超圖可以建模比圖更一般類型的關(guān)系。超圖的階（order）和大小（size）可以基于頂點集和超邊集來定義，即，超圖的階代表頂點集的基數(shù)（cardinality），超圖的大小表示超邊集的基數(shù)。

與圖類似，可以定義兩種特定類型的超圖，包括空超圖（empty hypergraph）和平凡超圖（trivial hypergraph）。

• 空超圖是指具有空頂點集和空超邊集的超圖。
• 平凡超圖是指具有非空頂點集和空超邊集的超圖。

一般來說，除非另有說明，超圖具有非空頂點集和非空超邊集，并且不包含空超邊。

孤立點（isolated vertex）是指不包含在任何超邊中的頂點。如果存在一個包含這兩個頂點的超邊，則稱兩個頂點是相鄰的（adjacent）。如果兩條超邊具有非空交集，則稱它們是相交的（incident，注：此處原文用incident描述超邊間的相交關(guān)系）。

子超圖和部分超圖定義如下：

• 給定超圖的導(dǎo)出子超圖（induced sub-hypergraph）是指其頂點集是給定超圖的子集，且超邊僅包含一個元素或者（超邊與頂點子集的）交集元素個數(shù)不少于兩個的超圖。
• 給定超圖的子超圖（sub-hypergraph）是指其頂點集和超邊集均為給定超圖對應(yīng)集合的子集的超圖。
• 部分超圖（partial hypergraph）是指其超邊集是給定超圖的子集的超圖。

基于度可以定義兩種特殊類型的超圖：

• 正則超圖（regular hypergraph）是指所有頂點具有相同度的超圖。
• 均勻超圖（uniform hypergraph）是指所有超邊具有相同度的超圖。

連通性的概念定義如下。 環(huán) （loop）表示僅包含一個元素的超邊。 路徑 （path）是一個頂點-超邊交替序列，其中頂點屬于序列中連續(xù)的超邊。 圈 （cycle）是指首頂點與末頂點相同的路徑。路徑的 長度 是路徑中頂點的數(shù)量。如果兩個頂點在路徑中，則該路徑 連接 這兩個頂點。如果任意一對頂點都是連通的，則稱該超圖是 連通的 （connected），否則它是 不連通的 （disconnected）。兩個頂點之間的 距離 是連接這兩個頂點的路徑的最小長度。超圖的 直徑 是所有頂點對之間的最大距離。

除了圖 1.3，還有其他典型的超圖圖示，如圖 1.4 所示。在圖 1.4a 中，每個圓圈代表一條超邊。在圖 1.4b 中，所有相同顏色的線代表一條超邊，它們連接該超邊中的頂點。在圖 1.4c 中，每個空心圓表示一條超邊（原文誤寫為hypergraph），相同顏色的線連接該超邊中的頂點。

值得注意的是，超圖型結(jié)構(gòu)在許多應(yīng)用中可能并不明顯，它們隱藏在可以直接觀察到的數(shù)據(jù)背后。在某些情況下，我們可能只能捕獲數(shù)據(jù)中的一些成對關(guān)聯(lián)，而需要基于這些觀察重構(gòu)高階關(guān)聯(lián)。例如，一些流行的引文網(wǎng)絡(luò)，如 Cora, Citeseer 和 PubMed [16]，被廣泛用于分析，然而所有這些數(shù)據(jù)集僅包含圖類型數(shù)據(jù)，即將文章視為頂點，將引文關(guān)系視為鏈接。在這種情況下，為了挖掘這些數(shù)據(jù)之間的高階關(guān)聯(lián)，我們需要將這些數(shù)據(jù)轉(zhuǎn)換為超圖。作為一種典型方法，可以生成共著超圖（co-authorship hypergraph），它將文章表述為頂點，而具有相同作者的文章由一條超邊連接。以類似的方式，可以生成共引超圖（co-citation hypergraph），它同樣將文章視為頂點，而具有相同引文的文章被視為一條超邊。

1.3 超圖的應(yīng)用

由于超圖在復(fù)雜關(guān)聯(lián)建模方面具有優(yōu)越性，它已被應(yīng)用于多個學(xué)科領(lǐng)域，包括生物學(xué)、經(jīng)濟學(xué)和社會學(xué)，從而推動了智能化應(yīng)用的發(fā)展。在本部分中，我們介紹超圖的幾個典型應(yīng)用，以幫助理解這一強大工具。

一個代表性應(yīng)用是社會計算。過去幾十年間，社交媒體數(shù)據(jù)迅速增長，這些數(shù)據(jù)可提供潛在的群體層面洞察。超圖[17]是從數(shù)據(jù)中發(fā)現(xiàn)復(fù)雜且隱藏關(guān)聯(lián)的有用工具，其中超圖結(jié)構(gòu)可用于表述社交網(wǎng)絡(luò)中的高階關(guān)聯(lián)。

在推薦系統(tǒng)中，超圖被用于建模用戶-物品網(wǎng)絡(luò)、刻畫用戶畫像，并進一步預(yù)測用戶偏好（未來交互行為）。給定僅包含用戶與物品歷史交互信息的原始用戶-物品網(wǎng)絡(luò)，超圖[17]可區(qū)分性地表述用戶與物品之間各自的高階連接性，并執(zhí)行協(xié)同過濾任務(wù)。有時，用戶和物品可能附帶不同的屬性或特征。例如，用戶端信息可能包括性別、年齡和性格，而物品端信息可能包含類別、文本描述和圖像。這些屬性信息有助于捕捉用戶偏好。因此，超圖在推薦系統(tǒng)中的另一個應(yīng)用是屬性建模與推斷。

另一個流行但具有挑戰(zhàn)性的社交媒體計算應(yīng)用是情感分析，其目標(biāo)是在社交媒體語境中識別人們的真實情緒與態(tài)度。然而，社交媒體數(shù)據(jù)的多模態(tài)性與復(fù)雜性使該任務(wù)更加困難。例如，一條推文中可能同時包含文本、圖像和視頻。此外，帖子之間存在時間、地理位置和用戶偏好等維度上的復(fù)雜關(guān)系。因此，如何挖掘推文之間的復(fù)雜關(guān)系并分析用戶情感已成為一個緊迫問題。為此，超圖[18]可用于表述每個樣本之間的關(guān)聯(lián)，并考慮到不同情緒具有各自特征，且情感分析應(yīng)基于多源信息的聯(lián)合分析，從而實現(xiàn)魯棒且準(zhǔn)確的多模態(tài)情感預(yù)測。就社會事件檢測而言，由于單條帖子存在噪聲且內(nèi)容不足，難以傳達(dá)清晰全面的信息，探索一組高度相關(guān)的帖子變得更為重要。超圖[19]可用于表征不同推文之間異構(gòu)數(shù)據(jù)的關(guān)系，憑借其在建模不同帖子、模態(tài)和時間數(shù)據(jù)之間高階關(guān)聯(lián)方面的優(yōu)勢，從而實現(xiàn)實時社會事件檢測。具體而言，每條微博與其若干文本相關(guān)和視覺相關(guān)的微博相連，形成兩條超邊。接下來，通過超圖割方法將關(guān)于同一主題的微博聚合在一起，生成微博團（microblog clique），即由一組高度相關(guān)推文構(gòu)成的基本單元。

超圖在醫(yī)學(xué)與生物應(yīng)用中也展現(xiàn)了其優(yōu)勢。過去幾十年間，產(chǎn)生了海量的生物與醫(yī)學(xué)數(shù)據(jù)。這些數(shù)據(jù)具有復(fù)雜性、異構(gòu)性和多模態(tài)性，且數(shù)據(jù)內(nèi)部與數(shù)據(jù)之間的關(guān)聯(lián)相互交織。通過拼接超邊組，超圖[20–22]可自然地容納多模態(tài)或異構(gòu)數(shù)據(jù)。此外，通過這種方式，它可以區(qū)分性地利用這些數(shù)據(jù)之間的互補信息。以下流程可用于描述超圖計算如何應(yīng)用于生物與醫(yī)學(xué)任務(wù)：（1）將醫(yī)學(xué)圖像、圖像塊或生物實體建模為頂點，并基于其特征相似性或高階拓?fù)溥B接用超邊將它們連接起來；（2）使用一系列超圖計算方法學(xué)習(xí)數(shù)據(jù)之間的高階關(guān)聯(lián)。在此類應(yīng)用中，超圖已被用于：基于磁共振成像（MRI）的輕度認(rèn)知障礙（MCI）識別[23]、基于CT成像的新冠肺炎（COVID-19）識別[24]、基于腦功能網(wǎng)絡(luò)的自閉癥譜系障礙（ASD）識別[25]、醫(yī)學(xué)圖像檢索[26]等。

上述示例僅是超圖應(yīng)用的一小部分。超圖計算技術(shù)可用于任何數(shù)據(jù)之間存在高階復(fù)雜關(guān)聯(lián)的場景，例如計算機視覺、知識圖譜等。

1.4 超圖研究的歷史 1.4.1 超圖的拓?fù)渑c著色

關(guān)于超圖應(yīng)用的研究有著悠久的歷史。1943年，Prenowitz等人[27]首次將幾種幾何學(xué)（射影幾何、描述幾何和球面幾何）闡釋為超群或多群。Prenowitz等人[28]構(gòu)建了連接空間上的幾何（Geometries on Join Spaces），這是一種獨特的超群，已被證明是研究圖、超圖、二元關(guān)系、模糊集和粗糙集等多種主題的有價值工具。1996年，Rosenberg等人[29]首次在最廣泛的意義上探討了超結(jié)構(gòu)（超圖）與二元關(guān)系之間的聯(lián)系。隨后，Corsini和Leoreanu[30]也對此進行了研究。Rosenberg等人[29]于1996年首次開發(fā)了與模糊集相關(guān)的連接空間。Corsini、Leoreanu和Tofan[31]均重新審視了這些結(jié)構(gòu)。Zahedi等人[32]也推進了將超圖與模糊集相聯(lián)系以及考察配備有模糊結(jié)構(gòu)的代數(shù)結(jié)構(gòu)的概念。

超圖著色是一項典型且重要的任務(wù)，自上世紀(jì)以來一直備受關(guān)注。它是組合數(shù)學(xué)的基礎(chǔ)，正如Kierstead等人[33]所述，可用于確定某些圖的色數(shù)界限。Lu等人[34]提出了這些算法來解決不同的優(yōu)化問題，如分治問題和劃分問題，其中超圖著色也可用于尋找單色路徑和圈。Voloshin等人[35, 36]描述了如何對混合超圖進行著色，混合超圖被劃分為超邊族和反超邊族。在這種情況下，他們進一步將其應(yīng)用于能源供應(yīng)問題。

尋找大匹配的問題與界定超圖色指數(shù)的問題密切相關(guān)（請注意，正常邊著色的色類構(gòu)成一個匹配）。作為圖研究中的一個經(jīng)典主題，匹配理論發(fā)展得非常完善，可追溯至20世紀(jì)30年代的研究[37]。Tutte定理[38]是對包含完美匹配的圖的一種刻畫。Edmonds等人[39]提出了開花算法（Blossom algorithm），該算法能在多項式時間內(nèi)找出包含完美匹配的圖中的最大匹配。上述方法是超圖相關(guān)研究的早期工作。

1.4.2 超圖劃分、聚類與機器學(xué)習(xí)

超圖劃分是超圖領(lǐng)域的另一個重要問題。《并行計算百科全書》[1]中定義，超圖劃分涉及將超圖劃分為兩個或多個大致相等的部分，使得連接不同部分中頂點的超邊的代價函數(shù)最小化。在許多情況下，該定義過于嚴(yán)格，且實際應(yīng)用中常需劃分為兩個以上的部分。Karypis等人[40]提出了hMetis算法，該算法基于超圖的多級粗化。該方法從最小的粗化超圖開始，迭代地對其進行二分。George等人[41]進一步開發(fā)了hMeTiS-Kway算法，該算法采用粗化-細(xì)化范式直接構(gòu)建超圖的K路劃分，以解決K路超圖劃分問題。

此外，Papa等人[42]提供了幾種劃分超圖的方法，并將聚類定義為“將頂點合并為稱為簇的更大頂點組的過程，以便從輸入超圖計算出一個更粗的超圖。”文中還列舉了劃分與聚類的若干應(yīng)用，包括超大規(guī)模集成電路（VLSI）設(shè)計、數(shù)值線性代數(shù)、自動定理證明和形式驗證。文獻中已描述了若干相關(guān)應(yīng)用與方法。欲了解更多細(xì)節(jié)，文獻[43]發(fā)表了一篇關(guān)于聚類集成技術(shù)的綜述，其中也涵蓋了超圖劃分技術(shù)。聚類與劃分通常需要多級策略，這些策略在以往的研究中已得到充分探討。它們已被廣泛應(yīng)用于VLSI設(shè)計[40]、并行科學(xué)計算[44–46]、圖像分類[47]以及社交網(wǎng)絡(luò)[48, 49]等領(lǐng)域。

進入本世紀(jì)以來，超圖已被應(yīng)用于機器學(xué)習(xí)領(lǐng)域。文獻[48]引入了直推式超圖學(xué)習(xí)，給出了用于預(yù)測超圖上頂點標(biāo)簽的目標(biāo)函數(shù)的基本數(shù)學(xué)表述。由于超圖學(xué)習(xí)的性能與超圖的建模質(zhì)量密切相關(guān)，一些研究致力于進一步為超圖中的組件分配權(quán)重，包括超邊權(quán)重、頂點權(quán)重以及超邊依賴的頂點權(quán)重[50, 51]。為了加速超圖上的標(biāo)簽傳播過程，文獻進一步引入了多超圖交叉擴散方法，用于建模多模態(tài)數(shù)據(jù)之間的高階關(guān)聯(lián)并實現(xiàn)多模態(tài)信息融合[52]。

1.4.3 超圖上的深度學(xué)習(xí)

超圖結(jié)構(gòu)的高階表示研究也受到了深度學(xué)習(xí)強大學(xué)習(xí)與建模能力的啟發(fā)。一般來說，大多數(shù)針對超圖的深度學(xué)習(xí)方法可分為基于譜的方法和基于空間的方法。

就基于譜的方法而言，F(xiàn)eng等人[53]提出了超圖神經(jīng)網(wǎng)絡(luò)（HGNNs），以基于超圖拉普拉斯矩陣建模非成對關(guān)系。所提出的方法可自然地用于建模多模態(tài)數(shù)據(jù)。使用超圖神經(jīng)網(wǎng)絡(luò)對圖像進行分類也是可行的[54]。利用超圖譜理論的工具，Yadati等人[55]提出了HyperGCN，旨在利用圖卷積網(wǎng)絡(luò)（GCNs）在超圖上訓(xùn)練GCN以進行半監(jiān)督學(xué)習(xí)。就基于空間的方法而言，Jiang等人[56]通過擴展動態(tài)超圖學(xué)習(xí)，提出了一種動態(tài)超圖神經(jīng)網(wǎng)絡(luò)，該網(wǎng)絡(luò)能夠在每一層自適應(yīng)地改變超圖結(jié)構(gòu)。與底層結(jié)構(gòu)預(yù)先定義好的超圖卷積不同，Bai等人[57]提出了一種超圖注意力機制策略，用于學(xué)習(xí)超邊的動態(tài)連接，該機制在圖中與任務(wù)相關(guān)的部分傳播并聚集信息，從而生成更具判別性的頂點嵌入。此外，Gao等人[58]提出了一種通用超圖神經(jīng)網(wǎng)絡(luò)框架，可應(yīng)用于多種類型的超圖，如無向超圖、有向超圖、概率超圖、頂點/超邊加權(quán)超圖等。

針對同構(gòu)與異構(gòu)超圖，Zhang等人[59]提出了一種基于自注意力的超圖神經(jīng)網(wǎng)絡(luò)（Hyper-SAGNN）。通過將超圖映射到加權(quán)屬性線圖，Bandyopadhyay等人[60]實現(xiàn)了一種雙單射（bi-injective）超圖結(jié)構(gòu)。Huang等人[61]提出了UniGNN，該模型通過闡釋圖與超圖神經(jīng)網(wǎng)絡(luò)中的消息傳遞過程，能夠?qū)⑼ㄓ肎NN模型泛化至超圖。這些針對超圖的神經(jīng)網(wǎng)絡(luò)方法通過在處理過程中融入高階關(guān)聯(lián)，實現(xiàn)了表示學(xué)習(xí)。

1.5 超圖計算：挑戰(zhàn)與目標(biāo)

與圖及其他結(jié)構(gòu)相比，超圖在高階關(guān)聯(lián)建模方面具有優(yōu)勢。為了在實踐中利用這一優(yōu)勢，可以使用超圖來表述此類關(guān)聯(lián)，并相應(yīng)地執(zhí)行計算任務(wù)。在本部分中，我們總結(jié)超圖計算的目標(biāo)，特別是其中的主要挑戰(zhàn)與內(nèi)部任務(wù)。

下面我們給出超圖計算的定義：超圖計算是指利用超圖表述數(shù)據(jù)底層的高階關(guān)聯(lián)，然后針對不同的應(yīng)用在超圖上進行語義計算。

超圖計算的主要挑戰(zhàn)與目標(biāo)包含三個方面，包括如何生成超圖、如何處理大規(guī)模數(shù)據(jù)以及如何在超圖上進行學(xué)習(xí)。

1. 如何生成超圖。 在大多數(shù)情況下，超圖結(jié)構(gòu)并非顯式存在。可觀測到的可能是非結(jié)構(gòu)化數(shù)據(jù)（如圖像、視頻和離散信號）以及兩個主體之間的成對關(guān)系。為了將底層的高階關(guān)聯(lián)揭示為超圖，需要定義其生成方式。更重要的是，觀測數(shù)據(jù)可能含有噪聲、存在缺失，且往往呈現(xiàn)多模態(tài)特性。如何描述這些數(shù)據(jù)同樣面臨挑戰(zhàn)。在這種情況下，很難基于這些數(shù)據(jù)生成準(zhǔn)確的超圖結(jié)構(gòu)。因此，如何生成超圖，特別是針對特定任務(wù)生成良好的超圖結(jié)構(gòu)，是實踐中的首要挑戰(zhàn)。
2. 如何處理大規(guī)模數(shù)據(jù)。 計算復(fù)雜度是圖數(shù)據(jù)面臨的一個主要問題，對于超圖而言也同樣嚴(yán)峻。許多應(yīng)用（如社交媒體和腦神經(jīng)元網(wǎng)絡(luò)）中的數(shù)據(jù)規(guī)模達(dá)到百萬級或更高。面對如此大規(guī)模的數(shù)據(jù)，如何高效且有效地在超圖上進行存儲與計算仍需進一步研究。
3. 如何在超圖上進行學(xué)習(xí)。 給定一個超圖，可以在其結(jié)構(gòu)上開展學(xué)習(xí)任務(wù)，設(shè)計超圖上的標(biāo)簽傳播方法至關(guān)重要。除了傳統(tǒng)的特征表示方法外，連接關(guān)系本身也可作為表示。鑒于超圖提供了此類高階關(guān)聯(lián)，在超圖上學(xué)習(xí)新的表示十分有益。因此，如何在超圖上進行表示學(xué)習(xí)是一個重要課題。

如圖1.5所示，超圖建模可簡要分為兩類，即主體內(nèi)關(guān)聯(lián)建模（intra-correlation modeling）與主體間關(guān)聯(lián)建模（inter-correlation modeling）。此處，主體內(nèi)關(guān)聯(lián)建模關(guān)注主體內(nèi)部的高階關(guān)聯(lián)。主體的組成部分被表示為頂點，這些組成部分之間的關(guān)聯(lián)在超圖中被表示為超邊。在這些情況下，稱為主體內(nèi)超圖（intra-hypergraph）的超圖旨在表示主體本身。主體間關(guān)聯(lián)建模則集中于不同主體之間的高階關(guān)聯(lián)。一組主體被表示為頂點，這些主體之間的關(guān)聯(lián)在超圖中被表示為超邊，該超圖稱為主體間超圖（inter-hypergraph）。其目標(biāo)是借助目標(biāo)主體與其他主體的關(guān)聯(lián)，學(xué)習(xí)目標(biāo)主體的表示或連接關(guān)系。

這里我們以圖像表示為例。當(dāng)選擇一幅圖像作為主體時，圖像中像素或圖像塊之間的關(guān)聯(lián)屬于主體內(nèi)關(guān)聯(lián)，可生成相應(yīng)的主體內(nèi)超圖用于圖像表示。另一方面，我們也可以觀察其他圖像進行處理。主體圖像與其他圖像之間的關(guān)聯(lián)屬于主體間關(guān)聯(lián)，同樣可生成相應(yīng)的主體間超圖用于圖像表示。也就是說，主體內(nèi)關(guān)聯(lián)與主體間關(guān)聯(lián)可被視為不同尺度下的視角。如果我們將主體本身視為目標(biāo)系統(tǒng)，那么該主體與其他主體之間的關(guān)聯(lián)就是該主體的主體間關(guān)聯(lián)，對應(yīng)一個主體間超圖。如果我們將這一組主體視為目標(biāo)系統(tǒng)，那么這些主體之間的關(guān)聯(lián)就是主體內(nèi)關(guān)聯(lián)，相應(yīng)地會導(dǎo)出一個主體內(nèi)超圖。

1.6 本書結(jié)構(gòu)

本書共包含13章，其余章節(jié)的結(jié)構(gòu)安排如下：

• 第2章 超圖的數(shù)學(xué)基礎(chǔ)。 本章介紹超圖的基礎(chǔ)數(shù)學(xué)知識，并呈現(xiàn)用于促進對超圖結(jié)構(gòu)深入理解與分析的數(shù)學(xué)符號。
• 第3章 超圖計算范式。 本章介紹三種典型的超圖計算范式，包括內(nèi)部表示計算、外部表示計算以及群體關(guān)聯(lián)計算。
• 第4章 超圖建模。 本章介紹不同的超圖建模方法，包括隱式超圖建模與顯式超圖建模。本章還提供了計算機視覺、推薦系統(tǒng)及其他應(yīng)用的示例。
• 第5章 典型超圖計算任務(wù)。 本章介紹典型的超圖計算任務(wù)，包括超圖上的標(biāo)簽傳播、超圖上的數(shù)據(jù)聚類、超圖上的不平衡學(xué)習(xí)以及超圖上的鏈接預(yù)測。
• 第6章 超圖結(jié)構(gòu)演化。 本章介紹超圖上的結(jié)構(gòu)演化方法，這些方法相應(yīng)地優(yōu)化超圖結(jié)構(gòu)，包括超圖組件優(yōu)化與超圖結(jié)構(gòu)優(yōu)化。我們簡要介紹了針對增長數(shù)據(jù)的增量學(xué)習(xí)方法。
• 第7章 超圖上的神經(jīng)網(wǎng)絡(luò)。 本章介紹超圖神經(jīng)網(wǎng)絡(luò)的最新進展，包括基于譜的方法與基于空間的方法。本章還提供了圖神經(jīng)網(wǎng)絡(luò)與超圖神經(jīng)網(wǎng)絡(luò)的對比。
• 第8章 大規(guī)模超圖計算。 本章介紹如何處理大規(guī)模數(shù)據(jù)。更具體地說，本章提供了兩類大規(guī)模超圖計算方法，即基于分解的超圖約簡與基于層次結(jié)構(gòu)的超圖學(xué)習(xí)。
• 第9章 面向社交媒體分析的超圖計算。 本章介紹超圖計算在社交媒體分析中的應(yīng)用，包括推薦系統(tǒng)、情感分析與情緒識別。
• 第10章 面向醫(yī)學(xué)與生物應(yīng)用的超圖計算。 本章介紹超圖計算在醫(yī)學(xué)與生物應(yīng)用中的應(yīng)用，包括計算機輔助診斷、基于組織病理學(xué)圖像的生存預(yù)測、藥物發(fā)現(xiàn)以及醫(yī)學(xué)圖像分割。
• 第11章 面向計算機視覺的超圖計算。 本章介紹超圖計算在計算機視覺中的應(yīng)用，包括視覺分類、三維物體檢索以及基于標(biāo)簽的社交圖像檢索。
• 第12章 DeepHypergraph庫。 本章介紹DeepHypergraph庫，這是一個基于Python的超圖計算庫。
• 第13章 結(jié)論與未來工作。 本章對本書進行總結(jié)，并介紹超圖計算的三個進一步研究方向。

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