超圖計算 Hypergraph Computation（一）

超圖計算 Hypergraph Computation

第一部分介紹超圖計算的基礎知識

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

前言

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

圖已被廣泛用于表達數據關聯。圖是一種非線性數據結構，由頂點集合與邊構成，用于表示頂點之間的成對關聯。近年來，圖學習與圖神經網絡在研究領域與工業界均引起了廣泛關注，并已成為十分熱門的課題。需要指出的是，現實世界遠比單純的成對連接復雜得多，因此基于圖的方法在高階關聯建模方面仍存在局限性。

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

在本書中，我們介紹了超圖計算的最新進展，內容涵蓋從超圖建模到超圖神經網絡。超圖計算的應用也得到了討論。我們還總結了超圖計算領域的最新成果與實用工具。本書既可被視為一部理論著作，亦可作為指導如何在實踐中運用超圖計算的手冊。

書籍組織結構

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

第二部分聚焦于超圖建模與學習技術。超圖計算的第一步是構建超圖以刻畫數據間的高階關聯，該內容在第 4 章中給出。第 5 章隨后提供了典型的超圖計算任務，包括標簽傳播、數據聚類、代價敏感學習以及鏈接預測。我們在第 6 章進一步介紹了用于超圖優化的超圖結構演化方法。第 7 章介紹了超圖上的神經網絡。超圖計算的實際應用需要具備處理大規模數據的能力，因此，我們在第 8 章對大規模超圖計算進行了廣泛介紹。

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

第1章 引言

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

1.1 背景

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

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

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

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

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

此類復雜關聯，即高階關聯而非成對關聯，在現實世界數據中非常普遍。為了研究這些復雜系統，有必要對其要素之間的高階關系進行表征與分析。實證研究表明，系統的關聯模式往往在系統功能中扮演重要角色。近年來，越來越多的研究者開始關注這一領域，并應用高階關聯建模與分析方法。

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

盡管基于圖的方法已發展數十年并取得了巨大進展，但它們仍存在局限性。這些圖模型能更好地表述系統中元素之間的二元關系，但可能忽略三個或更多元素之間的高階關聯。近年來，許多研究表明，在大多數應用中，對高階關聯進行建模與優化甚至更為重要[9–11]。例如，在生物圈系統中，物種之間的高階相互作用確保了物種多樣性的穩定[10]。不同網絡的高階特征可有效區分其所屬領域[11]。隨著網絡科學的快速發展，數據與關聯的復雜性迅速增加。在生物信息、社會計算與圖像處理等領域，存在大量多模態、異構、高層級的數據，亟需有效的高階關聯建模與優化方法。

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

超圖作為圖的推廣，能夠表述數據之間的高階關聯，近年來得到了深入研究。在本書中，我們將介紹超圖計算的最新進展，從超圖建模到超圖神經網絡。下文我們首先介紹超圖的基本定義，然后展示超圖的應用與研究歷史。最后，我們總結我們在超圖計算方面的工作以及本書的結構。

1.2 超圖的定義

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

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

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

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

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

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

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

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

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

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

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

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

1.3 超圖的應用

由于超圖在復雜關聯建模方面具有優越性，它已被應用于多個學科領域，包括生物學、經濟學和社會學，從而推動了智能化應用的發展。在本部分中，我們介紹超圖的幾個典型應用，以幫助理解這一強大工具。

一個代表性應用是社會計算。過去幾十年間，社交媒體數據迅速增長，這些數據可提供潛在的群體層面洞察。超圖[17]是從數據中發現復雜且隱藏關聯的有用工具，其中超圖結構可用于表述社交網絡中的高階關聯。

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

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

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

上述示例僅是超圖應用的一小部分。超圖計算技術可用于任何數據之間存在高階復雜關聯的場景，例如計算機視覺、知識圖譜等。

1.4 超圖研究的歷史 1.4.1 超圖的拓撲與著色

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

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

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

1.4.2 超圖劃分、聚類與機器學習

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

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

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

1.4.3 超圖上的深度學習

超圖結構的高階表示研究也受到了深度學習強大學習與建模能力的啟發。一般來說，大多數針對超圖的深度學習方法可分為基于譜的方法和基于空間的方法。

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

針對同構與異構超圖，Zhang等人[59]提出了一種基于自注意力的超圖神經網絡（Hyper-SAGNN）。通過將超圖映射到加權屬性線圖，Bandyopadhyay等人[60]實現了一種雙單射（bi-injective）超圖結構。Huang等人[61]提出了UniGNN，該模型通過闡釋圖與超圖神經網絡中的消息傳遞過程，能夠將通用GNN模型泛化至超圖。這些針對超圖的神經網絡方法通過在處理過程中融入高階關聯，實現了表示學習。

1.5 超圖計算：挑戰與目標

與圖及其他結構相比，超圖在高階關聯建模方面具有優勢。為了在實踐中利用這一優勢，可以使用超圖來表述此類關聯，并相應地執行計算任務。在本部分中，我們總結超圖計算的目標，特別是其中的主要挑戰與內部任務。

下面我們給出超圖計算的定義：超圖計算是指利用超圖表述數據底層的高階關聯，然后針對不同的應用在超圖上進行語義計算。

超圖計算的主要挑戰與目標包含三個方面，包括如何生成超圖、如何處理大規模數據以及如何在超圖上進行學習。

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

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

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

1.6 本書結構

本書共包含13章，其余章節的結構安排如下：

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

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