層超圖網絡 Sheaf Hypergraph Networks

https://arxiv.org/pdf/2309.17116

摘要

高階關系在自然界中廣泛存在，眾多現象涉及超越簡單成對連接的復雜交互。因此，高階處理領域的進展能夠加速需要結構化數據的各個領域的發展。當前方法通常使用超圖來表示這些交互。我們通過為超圖引入胞腔層（cellular sheaves）來增強這種表示，這是一種數學構造，它在保持傳統超圖局部高階連通性的同時，為其添加了額外結構。受文獻中現有拉普拉斯算子的啟發，我們開發了兩種獨特的層超圖拉普拉斯算子公式：線性和非線性。我們的理論分析表明，將層（sheaves）融入超圖拉普拉斯算子中，比標準超圖擴散提供了更具表達力的歸納偏置，從而為有效建模復雜數據結構創造了一個強有力的工具。我們利用這些層超圖拉普拉斯算子設計了兩類模型：層超圖神經網絡與層超圖卷積網絡。這些模型推廣了文獻中常見的經典超圖網絡。通過大量實驗，我們證明了這種推廣顯著提升了性能，在多個用于超圖節點分類的基準數據集上取得了頂尖結果。

1 引言

關系數據在現實場景中的普遍存在，促使基于圖的方法在眾多領域得到快速發展并廣泛應用[1–4]。然而，圖的一個主要局限性在于其無法表示超越成對關系的交互。相比之下，現實世界中的交互往往是復雜且多層面的。有證據表明，高階關系經常出現在神經科學[5, 6]、化學[7]、環境科學[8, 9]和社交網絡[10]中。因此，學習強大且有意義的超圖表示已成為深度學習中一個充滿前景且快速發展的子領域[11–16]。然而，當前基于超圖的模型難以有效捕捉高階關系。如[17]所述，傳統的超圖神經網絡常常面臨過平滑問題。當我們在超圖內部傳播信息時，節點的表示會在鄰域內趨于一致。這種效應阻礙了超圖模型捕捉局部高階細微特征的能力。

需要更強大、更靈活的數學構造來更好地捕捉現實世界交互的復雜性。層（sheaves）為圖提供了一種合適的增強方式，能夠實現更多樣化、更具表達力的表示。胞腔層[18]能夠將數據附加到圖上，其方法是為節點關聯向量空間，并配備一種沿邊傳遞信息的機制。這種方法允許更豐富的數據表示，并增強了建模復雜交互的能力。

出于對更具表達力結構的需求，我們為超圖引入了胞腔層，它允許表示更復雜的動態，同時保留超圖固有的高階連通性。我們迎接這一非平凡挑戰，將兩種常用的超圖拉普拉斯算子[19, 11]進行推廣，以融入層所提供的更豐富結構。理論上，我們證明了使用我們提出的層超圖拉普拉斯算子推導出的擴散過程，比經典超圖擴散誘導了更具表達力的歸納偏置。借助這種增強的歸納偏置，我們構建并測試了兩個強大的神經網絡，它們能夠推斷和處理超圖層結構：層超圖神經網絡（SheafHyperGNN）和層超圖卷積網絡（SheafHyperGCN）。

超圖胞腔層的引入擴展了表示復雜交互的潛力，并為更先進的技術奠定了基礎。通過利用層結構推廣超圖拉普拉斯算子，我們能夠更好地捕捉現實世界數據的細微差別與復雜性。此外，我們的理論分析提供了證據，表明層超圖拉普拉斯算子體現了更具表達力的歸納偏置，這對于獲得強大的表示至關重要。

我們的主要貢獻總結如下：

1. 我們為超圖引入了胞腔層，這是一種數學構造，通過為每個節點和超邊關聯一個向量空間，并配備使它們之間能夠進行信息傳遞的線性投影，從而為超圖增強了額外結構。
2. 我們提出了線性和非線性的層超圖拉普拉斯算子，推廣了文獻中常用的標準超圖拉普拉斯算子。我們還對這些拉普拉斯算子擴散過程所產生的歸納偏置進行了理論刻畫，展示了利用這些新穎工具有效建模復雜現象的優勢。
3. 這兩種層超圖拉普拉斯算子構成了專為超圖處理設計的兩種新穎架構的基礎：層超圖神經網絡和層超圖卷積網絡。實驗結果表明，這些模型取得了頂尖性能，在眾多基準數據集上超越了現有方法。

2 相關工作

圖上的層。 利用現實世界數據中的圖結構已推動醫療保健[1]、生物化學[2]、社交網絡[20]、推薦系統[3]、交通預測[21]等多個領域的進步，圖神經網絡（GNN）已成為圖表示的標準。然而，在異配設置中，當具有不同標簽的節點更有可能相連時，直接處理圖結構會導致性能不佳。文獻[22]通過以胞腔層[18]的形式為圖附加額外的幾何結構來解決這一問題。

圖上的胞腔層為每個節點和每條邊關聯一個向量空間，并為每個關聯對提供這些空間之間的線性投影。為了考量這種更復雜的幾何結構，SheafNN [23] 通過將圖拉普拉斯算子替換為層拉普拉斯算子[27]，對經典GNN [24–26] 進行了推廣。研究者探索了基于高維層的神經網絡，其中的層結構要么從圖中學習得到[22]，要么出于效率考慮進行確定性推斷[28]。近期的方法集成了注意力機制[29]，或用波動方程替代了傳播過程[30]。在最新進展中，層神經網絡被發現能顯著提升推薦系統的性能，因為它們改進了圖神經網絡的局限性[31]。

在異構圖領域，為不同類型的邊學習獨特消息傳遞函數的概念已十分成熟。然而，與RGCN [32]等異構圖方法相比，基于層的方法在處理該任務的方式上存在區別。后者為每種關聯關系學習獨立的參數，而基于層的方法則依賴于與節點和超邊相關的特征，動態預測每種關系的投影。因此，層網絡中的參數總量不會隨著超邊數量的增加而急劇膨脹。這一差異凸顯了兩種方法在底層范式上的根本性轉變。

超圖網絡。 圖雖然有用，但有一個顯著的局限性：它們只能表示成對關系。許多自然現象涉及復雜的高階交互[33–35, 9]，需要像超圖這樣更通用的結構。近年來，針對超圖結構已開發出多種深度學習方法。HyperGNN [11] 將超圖擴展為加權團，并應用類似于GCN [24] 的消息傳遞。HNHN [36] 通過引入非線性操作對此進行了改進，而HyperGCN [37] 則使用非線性拉普拉斯算子僅連接差異最顯著的節點。與GNN領域的趨勢相似，注意力模型在超圖領域也日益普及。HCHA [38] 使用一種基于注意力的關聯矩陣，該矩陣基于節點與超邊的相似度計算得出。類似地，HERALD [39] 利用可學習的距離來推斷軟關聯矩陣。另一方面，HEAT [15] 通過使用Transformer [40] 在每個超邊內部傳播信息來構建消息。

許多超圖神經網絡（HNN）方法可被視為兩階段框架：1）將消息從節點發送至超邊；2）將消息從超邊傳回節點。因此，[41] 提出了一種通用框架，其中第一階段采用平均算子，而第二階段則可使用任何現有的GNN模塊。類似地，[42] 使用DeepSet函數[43]或Transformer[40]來實現這兩個階段，而[44] 在兩個階段均使用類GNN聚合器，并為每個（節點，超邊）對分配不同的消息。

相比之下，我們提出了一種新穎的模型，旨在通過將胞腔層附加到超圖結構上，并依據該層在模型內部擴散信息，來改進超圖處理。我們將首先介紹超圖的胞腔層，證明相關拉普拉斯算子的一些性質，隨后提出并評估基于層超圖拉普拉斯算子的兩種架構。

3 超圖層拉普拉斯算子

之前的工作側重于通過依賴定義超圖拉普拉斯算子（Laplacian）的各種方法來創建超圖表示。在這項工作中，我們將專注于兩種定義：如文獻 [11] 中使用的超圖拉普拉斯算子的線性版本，以及如文獻 [37] 中的超圖拉普拉斯算子的非線性版本。我們將擴展這兩種定義以融入超圖層結構，分析由此產生的優勢，并基于每一種定義提出兩種不同的神經網絡架構。關于兩種提出的層超圖拉普拉斯算子的直觀對比，請參見圖 1。

3.1 線性層超圖拉普拉斯算子

當每個超邊恰好包含兩個節點時（因此 H H 是一個圖），內部求和將只包含一項，我們便恢復了如文獻 [22] 中公式化的圖的層拉普拉斯算子（sheaf Laplacian）。

在接下來的章節中，我們將展示使用這種層超圖擴散代替通常的超圖擴散的優勢。

直觀地說，這意味著使用 線性超圖拉普拉斯算子 應用擴散會導致相鄰節點的表示變得相似。雖然這在某些場景中是可取的，但在其他場景中可能會導致性能不佳，這種現象被稱為過平滑（over-smoothing）[17]。在下文中，我們展示了使用線性 層 超圖拉普拉斯算子應用擴散，通過隱式最小化一個更具表達力的能量函數來解決這些局限性。這使我們能夠建模使用通常的拉普拉斯算子無法觸及的現象。

該量度量了超邊莖（stalk）域中相鄰節點之間的差異，而不同于通常的超圖狄利克雷能量，后者是在節點特征域中度量這種距離。在下文中，我們將證明，使用線性層拉普拉斯算子應用超圖擴散會隱式地降低該能量。

3.2 非線性層超圖拉普拉斯算子

盡管線性超圖拉普拉斯算子通常用于處理超圖，但它在完全保留超圖結構方面存在不足[47]。為了解決這些缺點，文獻[48]引入了非線性拉普拉斯算子，并證明其譜性質與線性拉普拉斯算子相比更適用于高階處理。例如，與線性版本相比，非線性拉普拉斯算子在最小割問題中會產生更均衡的劃分，而該任務已知與半監督節點分類密切相關。此外，雖然線性拉普拉斯算子為每個超邊關聯一個團（clique），但非線性版本具有依賴更稀疏連通性的優勢。我們將采用類似的方法來推導層超圖拉普拉斯算子的非線性版本，并分析使用該算子應用擴散的好處。

定義 4. 我們如下引入超圖 H 關于信號 x 的非線性層超圖拉普拉斯算子：

盡管被最小化的勢函數發生了變化，但總體目標仍然與線性情況類似：力求在超邊莖空間內的表示之間達成連貫的一致性，而不是在輸入空間中為每個超邊生成均勻的特征。與線性場景形成對比的是，在線性場景中每個超邊需要二次方數量的邊，而非線性層超圖拉普拉斯算子將單個邊與每個超邊相關聯，從而提高了計算效率。

3.3 層超圖網絡

流行的超圖神經網絡 [45, 11, 37, 50] 從多種超圖擴散算子 [47, 48, 51] 中汲取靈感，從而產生了多樣化的消息傳遞技術。這些技術都涉及信息從節點傳播到超邊，反之亦然。我們將采用類似的策略，并基于本文中討論的層擴散機制所啟發的兩種消息傳遞方案，引入層超圖神經網絡（Sheaf Hypergraph Neural Network）和層超圖卷積網絡（Sheaf Hypergraph Convolutional Network）。

總之，本文介紹的模型，即 SheafHyperGNN 和 SheafHyperGCN，充當了經典 HyperGNN [11] 和 HyperGCN [37] 的推廣。與其傳統對應物相比，這些新模型具有更具表達力的隱式正則化。

4 實驗分析

我們在八個領域、規模和異配水平（heterophily level）各異且常用于超圖基準測試的真實世界數據集上評估我們的模型。這些數據集包括 Cora, Citeseer, Pubmed, Cora-CA, DBLP-CA [37], House [52], Senate 和 Congress [53]。為了確保與基線方法的公平比較，我們遵循 [50] 中使用的相同訓練流程，將數據隨機劃分為 50% 的訓練樣本、25% 的驗證樣本和 25% 的測試樣本，并使用不同的隨機劃分將每個模型運行 10 次。我們報告平均準確率以及標準差。

此外，我們受 [50] 引入的數據集啟發，在一組合成異配數據集上進行了實驗。遵循他們的方法，我們使用上下文超圖隨機塊模型（contextual hypergraph stochastic block model）[54–56] 生成一個包含 5000 個節點的超圖：其中一半屬于類別 0，另一半屬于類別 1。隨后，我們隨機采樣 1000 個基數（cardinality）為 15 的超邊，每個超邊恰好包含 β 個來自類別 0 的節點。異配水平計算為 α = min ? ( β , 15 ? β ) 。節點特征是從標準差為 1 的標簽依賴高斯分布中采樣的。由于原始數據集未公開，我們通過改變異配水平 α ∈ { 1 … 7 } 生成我們自己的數據集，并重新運行他們的實驗以進行公平比較。

實驗在單塊具有 48GB 顯存的 NVIDIA Quadro RTX 8000 GPU 上執行。除非另有說明，我們的結果代表了每個架構通過使用隨機搜索進行超參數優化所獲得的最佳性能。關于所有模型選擇和超參數的詳細信息可以在補充材料中找到。

與近期方法的比較。 我們還將文獻中的幾種近期模型進行了比較，例如 HCHA [38], HNHN [36], AllDeepSets [42], AllSetTransformer [42], UniGCNII [57], HyperND [58], 和 ED-HNN [50]。我們的模型在所有真實世界數據集上取得了具有競爭力的結果，并在其中五個數據集上達到了最先進的（state-of-the-art）性能（表 1）。這些結果證實了使用層拉普拉斯算子處理超圖的優勢。我們還在合成異配數據集上將我們的模型與一系列基線進行了比較。結果如表 3 所示。我們要表現最好的模型 SheafHyperGNN，在所有異配水平上始終優于其他模型。請注意，我們要利用層結構增強經典超圖處理的框架并不局限于本文測試的兩種傳統模型（HyperGNN 和 HyperGCN）。大多數近期的最先進方法，例如 ED-HNN，可以很容易地被調整以學習和處理我們要新穎的胞腔層超圖，而不是標準超圖，從而推動超圖領域的進一步發展。

在接下來的章節中，我們進行了一系列消融研究，以更深入地了解我們的模型。我們將探索各種類型的限制映射，分析網絡深度變化時性能如何變化，并研究莖維度對最終精度的重要性。

深度的影響。 眾所周知，在超圖網絡中堆疊多層會導致模型性能下降，特別是在異配設置中。這種現象被稱為過平滑，在圖 [59] 和超圖文獻 [17] 中都有深入研究。為了分析我們的模型受此限制的程度，我們在合成數據集的最異配版本（ α = 7 ）上訓練了一系列模型。對于 SheafHyperGNN 及其 HyperGNN 等效模型，我們將層數在 1 到 8 之間變化。在圖 2 中，我們觀察到雖然 HyperGNN 在超過 3 層時表現出性能下降，但 SheafHyperGNN 的性能保持基本恒定。在比較 SheafHyperGCN 與 HyperGCN 時，非線性版本也觀察到了類似結果（結果在補充材料中）。這些結果表明我們的模型在異配設置中具有潛在優勢，允許構建更深的架構。

調查特征多樣性。 我們的理論分析表明，雖然傳統超圖網絡傾向于為相鄰節點產生相似特征，但我們的層超圖網絡減少了更復雜的超邊莖空間中相鄰節點之間的距離。結果是，節點的特征不會變得統一，保留了它們的個體身份。我們通過計算 HyperGNN 和 SheafHyperGNN 的狄利克雷能量（圖 2 中的陰影區域）作為相鄰節點之間相似度的度量來經驗性地評估這一點。結果與理論分析一致：雖然增加 HyperGNN 的深度會創建均勻的特征，但 SheafHyperGNN 不受此限制的影響，鼓勵節點之間的多樣性。

5 結論

在本文中，我們引入了超圖的胞腔層，這是一種建立在經典超圖結構之上、用于建模高階關系的富有表達力的工具。此外，我們提出了兩個模型，分別基于線性和非線性層超圖拉普拉斯算子，能夠推斷并處理層超圖結構。我們證明了與這些模型相關的擴散過程誘導了一種更具表達力的隱式正則化，擴展了與標準超圖擴散相關的能量。這種新穎的架構推廣了經典超圖網絡，且我們通過實驗表明，它在多個數據集上優于現有方法。我們在 HyperGNN 和 HyperGCN 中用層超圖拉普拉斯算子替換超圖拉普拉斯算子的技術，建立了一個通用的框架，可用于“層化”（sheafify）其他超圖架構。我們相信，層超圖能夠為快速發展的超圖領域的進一步進步做出貢獻，其影響將遠遠超出本文所呈現的結果。

原文鏈接： https://arxiv.org/pdf/2309.17116