圖網路重磅綜述：基於圖的深度學習方法

導語

深度學習在多個領域中做到成功，如聲學、圖像和自然語言處理。但是，將深度學習應用於普遍存在的圖數據仍然存在問題，這是由於圖數據的獨特特性。近期，該領域出現大量研究，極大地提升了圖分析技術。清華大學朱文武等人綜述了應用於圖的不同深度學習方法。

來源：機器之心

論文題目：Deep Learning on Graphs: A Survey

論文地址：https://arxiv.org/abs/1812.04202

作者：張子威、崔鵬、朱文武

本文作者將現有方法分為三個大類：半監督方法，包括圖神經網路和圖卷積網路；無監督方法，包括圖自編碼器；近期新的研究方法，包括圖循環神經網路和圖強化學習。然後按照這些方法的發展史對它們進行系統概述。該研究還分析了這些方法的區別，以及如何合成不同的架構。最後，該研究簡單列舉了這些方法的應用範圍，並討論了潛在方向。

引言

近十年，深度學習成為人工智能和機器學習這頂皇冠上的明珠，在聲學、圖像和自然語言處理領域展示了頂尖的性能。深度學習提取數據底層複雜模式的表達能力廣受認可。但是，現實世界中普遍存在的圖卻是個難點，圖表示對象及其關係，如社交網路、電商網路、生物網路和交通網路。圖也被認為是包含豐富潛在價值的複雜結構。因此，如何利用深度學習方法進行圖數據分析近年來吸引了大量的研究者關注。該問題並不尋常，因為將傳統深度學習架構應用到圖中存在多項挑戰：

不規則領域：與圖像不同，音頻和文本具備清晰的網格結構，而圖則屬於不規則領域，這使得一些基礎數學運算無法泛化至圖。例如，為圖數據定義的卷積和池化操作並不是直接的，而這些是卷積神經網路（CNN）中的基礎操作。這通常被稱為幾何深度學習問題 [7]。

多變的結構和任務：圖具備多樣化的結構，因此比較複雜。例如，圖可以是同質的也可以是異質的，可以是加權的也可以不加權，可以是有符號的也可以是無符號的。此外，圖任務也有很多種，從節點問題（如節點分類和連接預測）到圖問題（如圖分類和圖生成）不一而足。多變的結構和任務需要不同的模型架構來解決特定的問題。

可擴展性和並行化：在大數據時代，實際的圖數據很容易擴展成數百萬節點和邊，如社交網路或電商網路。因此，如何設計可擴展模型（最好具備線性時間複雜度）成為關鍵的問題。此外，由於圖中的節點和邊是互連的，通常需要作為一個整體來建模，因此如何實施並行化計算是另一個關鍵問題。

跨學科：圖通常與其他學科有關，如生物學、化學或社會科學。這種跨學科性質提供了機會，當然也有挑戰：領域知識可用於解決特定問題，但集成領域知識可能使模型設計更難。例如，在生成分子圖時，目標函數和化學約束通常是不可微的，因此無法輕鬆使用基於梯度的訓練方法。

為了解決這些挑戰，研究人員付出了大量努力，因此該領域有大量相關論文和方法的文獻。之前研究採用的架構也是變化萬千，從監督式方法到無監督方法，從卷積網路到遞歸網路都有。但是，幾乎沒有什麼研究系統性概述這些方法之間的區別和聯繫。

本研究嘗試通過對圖深度學習方法的綜述填補這一空白。

圖 1：圖深度學習方法分類。

如圖 1 所示，該研究將現有方法分為三個大類：半監督方法、無監督方法和近期進展。具體來說，半監督方法包括圖神經網路（GNN）和圖卷積網路（GCN），無監督方法主要包括圖自編碼器（GAE），近期進展包括圖循環神經網路和圖強化學習。這些方法的主要區別如表 1 所示。

表 1：圖深度學習方法的主要區別。

大體上，GNN 和 GCN 是半監督方法，因為它們利用節點屬性和節點標籤端到端地訓練模型參數，而 GAE 主要使用無監督方法學習表征。近期的先進方法使用其它獨特的算法（不歸屬前兩個類別）。除了這些高層次的區別外，在模型架構上也存在很大不同。本論文主要按照這些方法的發展史和如何解決圖問題進行詳細綜述。本研究還分析了這些模型的區別，以及如何合成不同的架構。文章最後，簡單概述了這些方法的應用和潛在方向。

表 2：常用符號表。

圖神經網路（GNN）

這部分介紹適用於圖數據的最初半監督方法——圖神經網路（GNN）。

GNN 的來源可以追溯到「前深度學習」時代。GNN 的思路很簡單：為了編碼圖的結構信息，可以用低維狀態向量 s_i（1 ≤ i ≤ N）表示每個節點 v_i。受遞歸神經網路的啟發，這里採用狀態的遞歸定義：

其中 F(·) 是待學習的參數函數。得到 s_i 以後，使用另一個參數函數 O(·) 獲取最終輸出：

對於圖任務，這些研究建議添加一個對應整個圖獨特屬性的特殊節點。為學習模型參數，可採用以下半監督方法：在使用雅各比方法迭代地求解 Eq. (1)，使之達到穩定點之後，使用 Almeida-Pineda 算法執行一個梯度下降步，以最小化任務特定的目標函數（例如回歸任務的預測值和真值之間的平方誤差）；然後，重復該過程直到收斂。

在 Eqs. (1)(2) 這兩個簡單公式的幫助下，GNN 扮演了兩個重要角色。GNN 結合了處理圖數據的一些早期方法，如遞歸神經網路和馬爾可夫鏈。GNN 的理念也為未來研究提供了一些啟發：未來我們會發現，一些當前最優的 GCN 實際上具備與 Eq. (1) 類似的公式，同時也遵循與近鄰交換信息的框架。事實上，GNN 和 GCN 可以被統一成一個框架，GNN 等同於使用相同層到達穩定狀態的 GCN。

盡管 GNN 理論上很重要，它也有一些缺陷。首先，要確保 Eq. (1) 有唯一解，F(·) 必須是「壓縮映射」（contraction map），這嚴重限制了建模能力。其次，由於梯度下降步之間需要很多次迭代，GNN 的計算成本高昂。由於這些缺陷、算力的缺乏（那時候 GPU 並未廣泛用於深度學習）以及缺乏研究興趣，當時 GNN 並不為社區所熟知。

GNN 的一個重大改進是門控圖-序列神經網路（Gated Graph Sequence Neural Network，GGS-NN）[26]。其作者將 Eq. (1) 的遞歸定義換成了門控循環單元（GRU）[27]，從而移除了對「壓縮映射」的需求，並且該網路支持使用現代優化技術。Eq. (1) 被替換成：

GNN 及其擴展有很多應用。如 CommNet [29] 使用 GNN 學習 AI 系統中的多智能體溝通，它將每個智能體作為一個節點，並在執行動作前先與其他智能體進行多個時間步的溝通來更新智能體狀態。Interaction Network (IN) [30] 使用 GNN 進行物理推理，它將對象表示為節點、將關係表示為邊、使用偽時間作為模擬系統。VAIN [31] 引入了注意力機制來衡量不同的交互，從而改進了 CommNet 和 IN。關係網路 (RN) [32] 使用 GNN 作為關係推理模塊，來增強其他神經網路，在視覺問答任務上取得了不錯的結果。

圖卷積網路（GCN）

表 3：不同圖卷積網路（GCN）的對比。

圖自編碼器（GAE）

自編碼器（AE）及其變體在無監督學習中得到廣泛使用，它適合在沒有監督信息的情況下學習圖的節點表征。這部分首先介紹圖自編碼器，然後介紹圖變分自編碼器和其他改進版變體。

GAE 的主要特徵見下表：

表 4：不同圖自編碼器（GAE）的對比。

自編碼器

用於圖的 AE 來源於稀疏自編碼器（Sparse Autoencoder，SAE）。其基本思路是，將鄰接矩陣或其變體作為節點的原始特徵，從而將 AE 作為降維方法來學習低維節點表征。具體來說，SAE 使用以下 L2 重建損失：

實驗證明 SAE 優於非深度學習基線模型。但是，由於其理論分析不正確，支持其有效性的底層機制尚未得到解釋。

結構深度網路嵌入（Structure Deep Network Embedding，SDNE）[76] 解決了這個難題，它表明 Eq. (35) 中的 L2 重建損失對應二階可能，即如果兩個節點具備類似的近鄰，則它們共享類似的隱藏表征。受表明一階可能重要性的網路嵌入方法的啟發，SDNE 修改了目標函數，添加了一個類似於拉普拉斯特徵映射的項：

圖 7：SDNE 框架圖。節點的一階可能和二階可能都使用深度自編碼器來保存。

受到其他研究的啟發，DNGR [77] 將 Eq. (35) 中的轉換矩陣 P 替換成隨機 surfing 概率的正逐點互信息（PPMI）矩陣。這樣，原始特徵可以與圖的隨機遊走概率關聯起來。但是，構建這樣的輸入矩陣需要 O(N^2 ) 的時間複雜度，無法擴展到大規模圖。

GC-MC [78] 進一步採取了不同的自編碼器方法，它使用 [36] 中的 GCN 作為編碼器：

解碼器是簡單的雙線性函數：

DRNE [79] 沒有重建鄰接矩陣或其變體，而是提出另一種修改：使用 LSTM 聚合近鄰信息，從而直接重建節點的低維向量。具體來說，DRNE 最小化以下目標函數：

與之前研究將節點映射到低維向量的做法不同，Graph2Gauss (G2G) [80] 提出將每個節點編碼為高斯分布 h_i = N (M(i, :), diag (Σ(i, :)))，以捕獲節點的不確定性。具體來說，作者將從節點屬性到高斯分布均值和方差的深度映射作為編碼器：

變分自編碼器

與之前的自編碼器不同，變分自編碼器（VAE）是另一種將降維與生成模型結合的深度學習方法。VAE 首次在 [81] 中提出用於建模圖數據，其解碼器是一個簡單的線性乘積：

至於均值和方差矩陣的編碼器，作者採用 [36] 中的 GCN：

由於完整圖需要重建，其時間複雜度為 O(N^2)。

受 SDNE 和 G2G 的啟發，DVNE [82] 提出另一個用於圖數據的 VAE，它也將每個節點表示為高斯分布。但與之前使用 KL 散度作為度量的研究不同，DVNE 使用 Wasserstein 距離來保留節點相似度的傳遞性。與 SDNE 和 G2G 類似，DVNE 也在目標函數中保留一階可能和二階可能：

重建損失為：

圖 8：DVNE 框架圖。DVNE 使用 VAE 將節點表示為高斯分布，並採用 Wasserstein 距離來保留節點相似度的傳遞性。

其他改進

圖 9：ARGA/ARVGA 框架圖。該方法向 GAE 添加了對抗訓練機制。（圖中的符號與本文主題略有不同，圖中的 X 和 Z 分別對應 F^V and H。

近期進展

下表展示了近期進展中多種方法的特徵。

圖循環神經網路（Graph RNN）

You et al. [94] 將 Graph RNN 應用到圖生成問題中。他們使用兩個 RNN，一個用於生成新節點，另一個自回歸地為新添加的節點生成邊。他們展示了這種分層 RNN 架構可以從輸入圖中高效學習，且時間複雜度也是可接受的。

動態圖神經網路（Dynamic Graph Neural Network，DGNN）[95] 使用時間感知 LSTM [100] 來學習動態圖中的節點表征。在建立新的邊之後，DGNN 使用 LSTM 更新兩個交互節點（interacting node）及其直接近鄰的表征，即考慮一步傳播效應（one-step propagation effect）。作者展示了時間感知 LSTM 可以很好地建模邊結構的已建立順序以及時間間隔，這反過來惠及大量圖應用。

也可以將 Graph RNN 結合其他架構，如 GCN 或 GAE。例如，RMGCNN [96] 將 LSTM 應用於 GCN 的結果，以漸進地重建圖（如圖 10 所示）。該方法旨在解決圖稀疏性問題。動態 GCN [97] 使用 LSTM 收集動態網路中不同時間片的 GCN 結果，旨在捕獲時空圖信息。

圖 10：RMGCNN 架構圖。RMGCNN 將 LSTM 添加到 GCN 中，以漸進地重建圖。

圖強化學習

GCPN [98] 使用強化學習執行目標導向的模塊化圖生成任務，以處理不可微目標和約束。具體來說，作者將圖生成建模為馬爾可夫決策過程，將生成模型作為在圖生成環境中運行的強化學習智能體。GCPN 將類似智能體動作作為連接預測問題，使用領域特定獎勵和對抗獎勵，使用 GCN 來學習節點表征，從而通過策略梯度方法做到端到端地訓練。實驗結果證明 GCPN 在多種圖生成問題上的有效性。

MolGAN [99] 採取了類似的思路，它使用強化學習來生成模塊化圖。不過它不是通過一系列動作來生成圖，而是直接生成整個圖，該方法比較適用於小分子。

結論與討論

應用。除了標準的圖推斷任務（如節點分類或圖分類）基於圖的深度學習方法還被應用於大量學科，如建模社會影響力 [103]、推薦 [51], [78], [96]、化學 [37], [41], [50], [98], [99]、物理 [104], [105]、疾病預測或藥物預測 [106]–[108]、自然語言處理 [109], [110]、計算機視覺 [111]–[114]、交通預測 [115], [116]、程序歸納 [117]，以及解決基於圖的 NP 問題 [118], [119]。

還有一些值得討論的方向：

• 不同類型的圖

圖數據的結構變化萬千，現有方法無法處理所有結構。例如，大部分方法聚焦於同質圖，很少有研究涉及異質圖，尤其是包含不同模態的圖。有符號網路（其負邊表示節點之間的衝突）也有獨特結構，對現有方法提出了挑戰。表示兩個以上對象之間複雜關係的超圖（Hypergraph）也未得到完備研究。接下來重要的一步是涉特定的深度學習模型來處理這些不同類型的圖。

• 動態圖

大部分現有方法聚焦於靜態圖。然而，很多現實中的圖是動態的，其節點、邊和特徵都會隨著時間而改變。例如，在社交網路中，人們可能建立新的社交關係、刪除舊的關係，其愛好和職位等特徵都會隨著時間改變。新用戶可能會加入社交網路，老用戶也可能離開。如何建模動態圖不斷變化的特徵，支持逐漸更新的模型參數？這個問題仍然是個開放性問題。一些初步研究嘗試使用 Graph RNN 架構解決該問題，結果令人鼓舞 [95], [97]。

• 可解釋性

由於圖通常與其他學科相關，解釋圖深度學習模型對於決策問題來說是關鍵。例如，在醫療問題中，可解釋性在將計算機經驗轉換為臨床使用中必不可少。但是，基於圖的深度學習模型比其他黑箱模型更難解釋，因為圖中的節點和邊高度關聯。

• 復合性

如前所述，很多現有架構可以結合起來使用，例如將 GCN 作為 GAE 或 Graph RNN 中的一個層。除了涉及新的構造塊以外，如何符合這些已有架構是一個有趣的未來研究方向。近期研究 Graph Networks [9] 跨出了第一步，它使用 GNN 和 GCN 的通用框架來解決關係推理問題。

總之，上述調查展示了基於圖的深度學習是一個很有前景並發展迅速的領域，機會與挑戰並存。研究基於圖的深度學習為建模關係數據提供了關鍵的構造塊，也是走向更好的機器學習和人工智能時代的重要一步。

編輯：王怡藺

PC端地址：

https://campus.swarma.org/gcou=10525

商務合作及投稿轉載｜[email protected]

◆ ◆ ◆