超圖計算范式（三）

第三章 超圖計算范式

《超圖計算 Hypergraph Computation》

Chapter 3 Hypergraph Computation Paradigms

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

摘要
本章介紹了三種超圖計算范式，包括超圖內計算、超圖間計算和超圖結構計算。超圖內計算表示旨在進行超圖的表示學習，其中每個主體由其組成部分構成的超圖來表示。超圖間計算旨在進行超圖中頂點的表示學習，其中每個主體是超圖中的一個頂點。超圖結構計算旨在進行超圖結構預測，其目標是發現頂點之間的連接。本章是對超圖計算范式的總體介紹，以展示如何在超圖計算框架中對任務進行形式化。

3.1 引言
超圖計算大致可分為三類：超圖的表示學習，其中每個主體由其組成部分構成的超圖來表示；超圖中頂點的表示學習，其中每個主體是超圖中的一個頂點；以及超圖結構預測，其目標是發現頂點之間的連接。這三種計算范式可分別命名為超圖內計算、超圖間計算和超圖結構計算。在本章中，我們將介紹與這三個方向相對應的廣義計算范式，并展示如何在這些超圖計算框架中對實際任務進行形式化。需要指出的是，范式中所涉廣義函數的具體實現不在本章介紹，因為它們屬于超圖計算框架中特定定義的函數或模塊的一部分，將在后續章節中闡述。

3.2 超圖內計算

超圖內計算旨在利用內部組件信息學習單個主體的表示，其中該主體各組件之間的相關性被形式化為一個超圖。在此超圖中，該主體的組成部分被視為頂點集合，而它們之間的高階相關性則由超邊建模。通過這種方式，單個主體被轉化為一個超圖。由于該超圖是由主體自身的組成部分生成的，我們可以將該超圖命名為該主體的超圖內（intra-hypergraph）。

圖像表示與理解 [1–3] 是典型的超圖內計算應用。例如，一幅圖像可以被分割為一組圖塊（patches），且每個圖塊由超圖中的一個頂點表示。該超圖可以根據這些圖塊的語義和空間信息生成。隨后，這些圖塊的信息及其高階相關性可以同時用于學習圖像的表示。

在此范式中，待分析的主體被視為一個整體系統，而超圖內用于對系統內部的相關性進行建模。這一過程如圖 3.1 所示。

3.3 超圖間計算

超圖間計算旨在通過考慮一個主體與其他主體之間的相關性來學習該主體的表示。在此超圖中，每個主體（包括目標主體）都被視為頂點的集合，而它們之間的高階相關性則由超邊建模。通過這種方式，這一組主體被轉化為一個超圖。由于該超圖是由跨主體的相關性生成的，我們可以將此超圖命名為該主體的超圖間（inter-hypergraph）。

主體分類與檢索 [4–7] 是典型的超圖間計算應用。例如，我們將一幅圖像作為目標主體，并且我們也可以擁有一個待處理的圖像池。每幅圖像可以由超圖中的一個頂點表示。該超圖可以根據這些圖像的語義和空間信息生成。隨后，這些圖像的信息及其高階相關性可以同時用于學習目標圖像的表示。

3.4 超圖結構計算

超圖結構計算旨在在存在缺失連接和不準確初始結構的情況下，學習數據之間的高階相關性。執行超圖結構計算通常有兩種場景：要么是超邊集合不完整，要么是頂點與超邊之間的隸屬關系不完整。推薦系統和藥物發現 [8–10] 是典型的超圖結構計算應用。例如，在推薦系統中，超邊描述了物品和用戶之間具有特定語義的連接。超邊的數量是固定的，并且頂點和超邊的特征都可以作為輸入獲取。在這里，超圖結構計算的目標是預測一個頂點是否屬于某個超邊。如果預測出一個新的超邊，我們就可以獲得新的連接來指示這些關系。然而，在知識超圖中，超邊展示了現實世界中的事實，這些事實通常高度不完整。期望通過超圖結構計算基于現有連接推斷出缺失的連接。因此，在第二種情況下，超圖結構計算的目標不僅是優化現有連接，還要推斷未觀察到的連接。

例如，在實踐中，注意力分數可以用作該函數的一個實例。

這表明新的超圖結構是根據特定的先驗信息在原始超圖結構的基礎上進行更新的。

為了引導超圖結構的演化以更準確地模擬數據相關性，有必要基于訓練數據和先驗信息來評估超圖結構的質量。如果有關于超圖結構的部分真實值（ground truth）信息，可以直接評估相關性建模的性能。然而，在大多數情況下，超圖結構并沒有金標準。因此，我們可能需要使用新的超圖執行下游任務，并通過下游任務的結果間接評估超圖計算的性能。在此，我們要參考圖 3.1，超圖結構計算可以在超圖內和超圖間計算框架下進行。

3.5 總結

在本章中，我們針對不同場景介紹了三種超圖計算范式。這三種范式分別是超圖內計算（intra-hypergraph computation）、超圖間計算（inter-hypergraph computation）和超圖結構計算（hypergraph structure computation），它們分別側重于：利用內部組件信息學習單個主體的表示、通過考慮主體與其他主體之間的相關性來學習主體的表示，以及在存在缺失連接和不準確初始結構的情況下學習數據之間的高階相關性。本章概述了如何使用超圖計算，而詳細的超圖計算理論、方法及應用將在后續章節中介紹。

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