層超圖網(wǎng)絡

層超圖網(wǎng)絡 Sheaf Hypergraph Networks

https://arxiv.org/pdf/2309.17116

摘要

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

1 引言

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

需要更強大、更靈活的數(shù)學構(gòu)造來更好地捕捉現(xiàn)實世界交互的復雜性。層（sheaves）為圖提供了一種合適的增強方式，能夠?qū)崿F(xiàn)更多樣化、更具表達力的表示。胞腔層[18]能夠?qū)?shù)據(jù)附加到圖上，其方法是為節(jié)點關(guān)聯(lián)向量空間，并配備一種沿邊傳遞信息的機制。這種方法允許更豐富的數(shù)據(jù)表示，并增強了建模復雜交互的能力。

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

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

我們的主要貢獻總結(jié)如下：

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

2 相關(guān)工作

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

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

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

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

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

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

3 超圖層拉普拉斯算子

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

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

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

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

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

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

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

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

定義 4. 我們?nèi)缦乱氤瑘D H 關(guān)于信號 x 的非線性層超圖拉普拉斯算子：

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

3.3 層超圖網(wǎng)絡

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

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

4 實驗分析

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

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

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

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

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

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

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

5 結(jié)論

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

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