圖神經網路+池化模塊，斯坦福等提出層級圖表徵學習

選自arXiv，作者：Rex Ying等，機器之心編譯，參與：李詩萌、劉曉坤。

圖網路（GN）在深度學習短板即因果推理上擁有巨大潛力，很有可能成為機器學習領域的下一個增長點，而圖神經網路（GNN）正屬於圖網路的子集。GNN 近期在圖形分類任務上得到了當前最佳的結果，但其存在平面化的局限，因而不能將圖形分層表徵。現實應用中，很多圖形信息都是層級表徵的，例如地圖、概念圖、流程圖等，捕獲層級信息將能更加完整高效地表徵圖形，應用價值很高。在本文中，來自斯坦福等大學的研究者通過在 GNN 中結合一種類似 CNN 中空間池化的操作——可微池化，實現了圖形的分層表徵。該方法在大部分圖形分類基準上都取得了當前最佳的表現，並在較簡單的約束下就能自動捕獲層級結構。

近年來人們開發圖形神經網路的興趣持續激增。圖形神經網路即可以在如社交網路數據 [16,21,36] 或基於圖形的分子表徵 [7,11,15] 的圖形結構數據上運行的一般的深度學習架構。GNN 一般是將底層圖形作為計算圖，通過在圖上傳遞、轉換和聚合節點特徵信息學習神經網路基元以生成單個節點嵌入。生成的節點嵌入可以作為輸入，用於如節點分類或連接預測的任何可微預測層，完整的模型可以通過端到端的方式訓練。

然而，現有的 GNN 結構的主要限制在於太過平坦，因為它們僅通過圖形的邊傳播信息，無法以分層的方式推斷和聚合信息。例如，為了成功編碼有機分子的圖形結構，就要編碼局部分子結構（如單個的原子和與這些原子直接相連的鍵）和分子圖的粗粒結構（如在分子中表示功能單元的原子基團和鍵）。對圖形分類任務而言缺少分層結構尤其成問題，因為這類任務是要預測與整個圖相關的標籤。在圖分類任務中應用 GNN，標準的方法是針對圖中所有的節點生成嵌入，然後對這些節點嵌入進行全局池化，如簡單地求和或在數據集上運行神經網路 [7,11,15,25]。這種全局池化方法忽略了可能出現在圖中的層級結構，也阻礙了研究人員針對完整圖形的預測任務建立有效的 GNN 模型。

研究者在此提出了 DIFFPOOL，這是一個可以分層和端到端的方式應用於不同圖神經網路的可微圖池化模塊（圖 1）。DIFFPOOL 允許開發可以學習在圖的層級表徵上運行的更深度的 GNN 模型。他們開發了一個和 CNN 中的空間池化操作相似的變體，空間池化可以讓深度 CNN 在一張表徵越來越粗糙的圖上迭代運行。與標準 CNN 相比，GNN 的挑戰在於圖不包含空間局部性的自然概念，也就是說，不能將所有節點簡單地以「m*m 補丁」的方式池化在一張圖上，因為圖複雜的拓撲結構排除了任何直接、決定性的「補丁」的定義。此外，與圖像數據不同，圖形數據集中包含的圖形節點數和邊數都不同，這使得定義通用的圖形池化操作符更具挑戰性。

為了解決上述問題，我們需要一個可以學習如何聚合節點以在底層圖形上建立層級多層支架的模型。DIFFPOOL 在深度 GNN 的每一層學習了可微分的軟分配，基於學習到的嵌入，將節點映射為一組聚類。以該方法為框架，我們通過分層的方式「堆疊」了 GNN 層建立了深度 GNN（圖 1）：GNN 模塊中 l 層的輸入節點對應 GNN 模塊中 1 層（1 個 GNN 模塊）學到的簇。因此，DIFFPOOL 的每一層都能使圖形越來越粗糙，然後訓練後的 DIFFPOOL 就可以產生任何輸入圖形的層級表徵。本研究展示了 DIFFPOOL 可以結合到不同的 GNN 方法中，這使準確率平均提高了 7%，並且在五個基準圖形分類任務中，有四個達到了當前最佳水平。最後，DIFFPOOL 可以學習到與輸入圖中明確定義的集合相對應的可解釋的層級簇。

4 實驗

為了回答下列問題，將 DIFFPOOL 與最優秀的圖分類方法相比，研究者評估了 DIFFPOOL 的優勢：

• Q1：與其他已提出的 GNN 池化方法（如使用排序池化 [39] 或 SET2SET 方法 [15]）相比，DIFFPOOL 如何？
• Q2：與現有最好的圖分類任務模型（包括 GNN 和基於核的方法）相比，結合了 DIFFPOOL 的 GNN 如何？
• Q3：DIFFPOOL 對輸入圖計算了有意義且可解釋的簇嗎？

4.1 基礎方法

在圖分類的性能比較中，研究者考慮了基於 GNN 和現有最好的基於核的方法。

基於 GNN 的方法

• 帶有全局平均池化的 GRAPHSAGE[16]。這裡忽略了其他如 [21] 中提出的 GNN 變體，因為從經驗上講，GraphSAGE 在任務中獲得了更好的表現。
• STRUCTURE2VEC（S2V）[7] 當前是最好的圖形表徵學習演算法，該演算法將潛在變數模型和 GNN 結合在一起。該演算法用的也是全局平均池化。
• CNN 中用於圖形的邊緣條件過濾器（ECC）[35] 將邊緣信息整合到 GCN 模型中，使用圖形粗化演算法進行池化操作。
• PATCHYSAN[29] 為每個節點定義了接受域（鄰域），並使用了規範節點排序，對節點嵌入的線性序列應用了卷積操作。
• SET2SET 通過聚合替代了傳統 GNN 架構的全局平均池化。Set2Set 聚合的性能優於之前工作 [15] 中的平均池化。我們以 GRAPHSAGE 作為基礎的 GNN 模型。
• SORTPOOL[39] 應用了 GNN 結構，在排好序的節點嵌入上做了單層軟池化，然後進行了 1D 卷積。

表 1：分類準確率（%）。與 GRAPHSAGE 相比，最右列給出了準確率的相對增長。

4.2 圖形分類結果

表 2：應用 DIFFPOOL 到 S2V 的準確率結果。

圖 2：DIFFPOOL 的層級聚合分布的圖，樣例圖形來自 COLLAB。左圖（a）表示兩層的層級聚合，第二層的節點與第一層的聚合簇相對應。（用顏色表示連接各層的節點/聚合簇，虛線用來表示簇。）右邊的兩個圖（（b）和（c））顯示了不同圖形的兩個更多的樣例。注意，儘管我們全局地將聚合簇的數量設置為節點的 25%，GNN 會自動學習到合適的有意義的簇的數量，並將其分配給不同的圖形。

4.3 DIFFPOOL 中聚合簇分配的分析

層級聚合結構。為了解決 Q3，研究者通過可視化不同層的簇分配研究了 DIFFPOOL 學習有意義節點簇的程度。圖 2 展示了一個來自 COLLAB 數據集的圖形在第一層和第二層節點分配的可視化圖，圖中節點顏色表示屬於哪個聚合簇。通過得到簇的分配概率的 argmax 值決定節點屬於哪個簇。研究者甚至觀察到，在僅基於圖形分類目標函數學習簇分配時，DIFFPOOL 還是可以捕獲層級聚合結構。

密集和稀疏的子圖結構。此外，研究者還觀察到 DIFFPOOL 可以以非均勻的方式將節點坍縮（collapse）成軟簇，並且傾向於將密集連接的子圖坍縮成簇。因為 GNN 可以有效地在密集的、類似團的子圖（直徑較小）上傳遞信息，因此在這樣密集的子圖上池化所有節點不太可能會損失結構信息。這直觀地解釋了為什麼對 DIFFPOOL 而言坍縮密集子圖是有用的池化策略。相比之下，稀疏子圖可能會包含許多像路徑結構、循環結構和樹狀結構等有趣的結構，由於稀疏導致的大直徑，GNN 可能無法通過信息傳遞捕獲這些結構。因此，DIFFPOOL 可以通過分別池化稀疏子圖的不同部分，學習在現有的稀疏子圖區域中捕獲有意義的結構（如圖 2 所示）。

論文：Hierarchical Graph Representation Learning with Differentiable Pooling

論文地址：https://arxiv.org/pdf/1806.08804.pdf

近期，通過有效地學習節點嵌入改變了圖表徵學習領域，圖神經網路（GNN）在節點分類和連接預測這樣的任務中得到了最佳結果。但現有的 GNN 方法本質上講還是平面的，因為無法學習圖形的層級表徵——這對於圖形分類任務而言尤其成問題，因為圖形分類任務的目的是預測與整個圖像相關的標籤。我們在此提出了 DIFFPOOL，這是一個可微分的圖形池化模塊，該模塊可以產生圖形的層級表徵，還可以以端到端的方式與多個圖神經網路結構結合。DIFFPOOL 在深度 GNN 的每一層針對節點學習可微分的軟簇分配，將節點映射到一組簇中去，然後這些簇作為粗化輸入，輸入到 GNN 下一層。實驗結果表明現有的 GNN 方法與 DIFFPOOL 結合後，在圖形分類基準中的準確率平均可以提高 5～10%，與現有的所有池化方法相比，在 5 個基準數據集中，有 4 個都得到了當前最佳的表現。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！