姓名：謝童? 學號：16020188008? 轉(zhuǎn)自微信公眾號 機器之心

深度學習在多個領(lǐng)域中實現(xiàn)成功，如聲學犀农、圖像和自然語言處理惰赋。但是，將深度學習應(yīng)用于普遍存在的圖數(shù)據(jù)仍然存在問題呵哨，這是由于圖數(shù)據(jù)的獨特特性赁濒。近期，該領(lǐng)域出現(xiàn)大量研究孟害，極大地提升了圖分析技術(shù)拒炎。清華大學朱文武等人綜述了應(yīng)用于圖的不同深度學習方法。

他們將現(xiàn)有方法分為三個大類：半監(jiān)督方法挨务，包括圖神經(jīng)網(wǎng)絡(luò)和圖卷積網(wǎng)絡(luò)击你；無監(jiān)督方法，包括圖自編碼器谎柄；近期新的研究方法丁侄，包括圖循環(huán)神經(jīng)網(wǎng)絡(luò)和圖強化學習。然后按照這些方法的發(fā)展史對它們進行系統(tǒng)概述朝巫。該研究還分析了這些方法的區(qū)別鸿摇，以及如何合成不同的架構(gòu)。最后劈猿，該研究簡單列舉了這些方法的應(yīng)用范圍拙吉，并討論了潛在方向。

引言

近十年揪荣，深度學習成為人工智能和機器學習這頂皇冠上的明珠庐镐，在聲學、圖像和自然語言處理領(lǐng)域展示了頂尖的性能变逃。深度學習提取數(shù)據(jù)底層復雜模式的表達能力廣受認可必逆。但是，現(xiàn)實世界中普遍存在的圖卻是個難點，圖表示對象及其關(guān)系名眉，如社交網(wǎng)絡(luò)粟矿、電商網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和交通網(wǎng)絡(luò)损拢。圖也被認為是包含豐富潛在價值的復雜結(jié)構(gòu)陌粹。因此，如何利用深度學習方法進行圖數(shù)據(jù)分析近年來吸引了大量的研究者關(guān)注福压。該問題并不尋常掏秩，因為將傳統(tǒng)深度學習架構(gòu)應(yīng)用到圖中存在多項挑戰(zhàn)：

不規(guī)則領(lǐng)域：與圖像不同，音頻和文本具備清晰的網(wǎng)格結(jié)構(gòu)荆姆，而圖則屬于不規(guī)則領(lǐng)域蒙幻，這使得一些基礎(chǔ)數(shù)學運算無法泛化至圖。例如胆筒，為圖數(shù)據(jù)定義的卷積和池化操作并不是直接的邮破，而這些是卷積神經(jīng)網(wǎng)絡(luò)（CNN）中的基礎(chǔ)操作。這通常被稱為幾何深度學習問題 [7]仆救。

多變的結(jié)構(gòu)和任務(wù)：圖具備多樣化的結(jié)構(gòu)抒和，因此比較復雜。例如彤蔽，圖可以是同質(zhì)的也可以是異質(zhì)的摧莽，可以是加權(quán)的也可以不加權(quán)，可以是有符號的也可以是無符號的顿痪。此外范嘱，圖任務(wù)也有很多種，從節(jié)點問題（如節(jié)點分類和連接預(yù)測）到圖問題（如圖分類和圖生成）不一而足员魏。多變的結(jié)構(gòu)和任務(wù)需要不同的模型架構(gòu)來解決特定的問題丑蛤。

可擴展性和并行化：在大數(shù)據(jù)時代，實際的圖數(shù)據(jù)很容易擴展成數(shù)百萬節(jié)點和邊撕阎，如社交網(wǎng)絡(luò)或電商網(wǎng)絡(luò)受裹。因此，如何設(shè)計可擴展模型（最好具備線性時間復雜度）成為關(guān)鍵的問題虏束。此外棉饶，由于圖中的節(jié)點和邊是互連的，通常需要作為一個整體來建模镇匀，因此如何實施并行化計算是另一個關(guān)鍵問題照藻。

跨學科：圖通常與其他學科有關(guān)，如生物學汗侵、化學或社會科學幸缕。這種跨學科性質(zhì)提供了機會群发，當然也有挑戰(zhàn)：領(lǐng)域知識可用于解決特定問題，但集成領(lǐng)域知識可能使模型設(shè)計更難发乔。例如熟妓，在生成分子圖時，目標函數(shù)和化學約束通常是不可微的栏尚，因此無法輕松使用基于梯度的訓練方法起愈。

為了解決這些挑戰(zhàn)，研究人員付出了大量努力译仗，因此該領(lǐng)域有大量相關(guān)論文和方法的文獻抬虽。之前研究采用的架構(gòu)也是變化萬千，從監(jiān)督式方法到無監(jiān)督方法，從卷積網(wǎng)絡(luò)到遞歸網(wǎng)絡(luò)都有。但是采够，幾乎沒有什么研究系統(tǒng)性概述這些方法之間的區(qū)別和聯(lián)系。

本研究嘗試通過對圖深度學習方法的綜述填補這一空白。如圖 1 所示滑绒，該研究將現(xiàn)有方法分為三個大類：半監(jiān)督方法闷堡、無監(jiān)督方法和近期進展。具體來說疑故，半監(jiān)督方法包括圖神經(jīng)網(wǎng)絡(luò)（GNN）和圖卷積網(wǎng)絡(luò)（GCN）杠览，無監(jiān)督方法主要包括圖自編碼器（GAE），近期進展包括圖循環(huán)神經(jīng)網(wǎng)絡(luò)和圖強化學習纵势。這些方法的主要區(qū)別如表 1 所示踱阿。大體上，GNN 和 GCN 是半監(jiān)督方法钦铁，因為它們利用節(jié)點屬性和節(jié)點標簽端到端地訓練模型參數(shù)软舌，而 GAE 主要使用無監(jiān)督方法學習表征。近期的先進方法使用其它獨特的算法（不歸屬前兩個類別）牛曹。除了這些高層次的區(qū)別外佛点，在模型架構(gòu)上也存在很大不同。本論文主要按照這些方法的發(fā)展史和如何解決圖問題進行詳細綜述黎比。本研究還分析了這些模型的區(qū)別超营，以及如何合成不同的架構(gòu)。文章最后阅虫，簡單概述了這些方法的應(yīng)用和潛在方向演闭。

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

表 1：圖深度學習方法的主要區(qū)別颓帝。

表 2：常用符號表米碰。

圖神經(jīng)網(wǎng)絡(luò)（GNN）

這部分介紹適用于圖數(shù)據(jù)的最初半監(jiān)督方法——圖神經(jīng)網(wǎng)絡(luò)（GNN）窝革。

GNN 的來源可以追溯到「前深度學習」時代。GNN 的思路很簡單：為了編碼圖的結(jié)構(gòu)信息见间，可以用低維狀態(tài)向量 s_i（1 ≤ i ≤ N）表示每個節(jié)點 v_i聊闯。受遞歸神經(jīng)網(wǎng)絡(luò)的啟發(fā)，這里采用狀態(tài)的遞歸定義：

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

對于圖任務(wù)，這些研究建議添加一個對應(yīng)整個圖獨特屬性的特殊節(jié)點史侣。為學習模型參數(shù)拴泌，可采用以下半監(jiān)督方法：在使用雅各比方法迭代地求解 Eq. (1)，使之達到穩(wěn)定點之后惊橱，使用 Almeida-Pineda 算法執(zhí)行一個梯度下降步蚪腐，以最小化任務(wù)特定的目標函數(shù)（例如回歸任務(wù)的預(yù)測值和真值之間的平方誤差）；然后税朴，重復該過程直到收斂回季。

在 Eqs. (1)(2) 這兩個簡單公式的幫助下，GNN 扮演了兩個重要角色正林。GNN 結(jié)合了處理圖數(shù)據(jù)的一些早期方法泡一，如遞歸神經(jīng)網(wǎng)絡(luò)和馬爾可夫鏈。GNN 的理念也為未來研究提供了一些啟發(fā)：未來我們會發(fā)現(xiàn)觅廓，一些當前最優(yōu)的 GCN 實際上具備與 Eq. (1) 類似的公式鼻忠，同時也遵循與近鄰交換信息的框架。事實上杈绸，GNN 和 GCN 可以被統(tǒng)一成一個框架帖蔓，GNN 等同于使用相同層到達穩(wěn)定狀態(tài)的 GCN。

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

GNN 的一個重大改進是門控圖-序列神經(jīng)網(wǎng)絡(luò)（Gated Graph Sequence Neural Network邑跪，GGS-NN）[26]次坡。其作者將 Eq. (1) 的遞歸定義換成了門控循環(huán)單元（GRU）[27]呼猪，從而移除了對「壓縮映射」的需求，并且該網(wǎng)絡(luò)支持使用現(xiàn)代優(yōu)化技術(shù)砸琅。Eq. (1) 被替換成：

GNN 及其擴展有很多應(yīng)用宋距。如 CommNet [29] 使用 GNN 學習 AI 系統(tǒng)中的多智能體溝通，它將每個智能體作為一個節(jié)點症脂，并在執(zhí)行動作前先與其他智能體進行多個時間步的溝通來更新智能體狀態(tài)谚赎。Interaction Network (IN) [30] 使用 GNN 進行物理推理，它將對象表示為節(jié)點诱篷、將關(guān)系表示為邊壶唤、使用偽時間作為模擬系統(tǒng)。VAIN [31] 引入了注意力機制來衡量不同的交互棕所，從而改進了 CommNet 和 IN闸盔。關(guān)系網(wǎng)絡(luò) (RN) [32] 使用 GNN 作為關(guān)系推理模塊，來增強其他神經(jīng)網(wǎng)絡(luò)琳省，在視覺問答任務(wù)上取得了不錯的結(jié)果迎吵。

圖卷積網(wǎng)絡(luò)（GCN）

表 3：不同圖卷積網(wǎng)絡(luò)（GCN）的對比。

圖自編碼器（GAE）

自編碼器（AE）及其變體在無監(jiān)督學習中得到廣泛使用针贬，它適合在沒有監(jiān)督信息的情況下學習圖的節(jié)點表征击费。這部分首先介紹圖自編碼器，然后介紹圖變分自編碼器和其他改進版變體坚踩。

GAE 的主要特征見下表：

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

自編碼器

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

實驗證明 SAE 優(yōu)于非深度學習基線模型皆警。但是拦宣，由于其理論分析不正確，支持其有效性的底層機制尚未得到解釋信姓。

結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入（Structure Deep Network Embedding鸵隧，SDNE）[76] 解決了這個難題，它表明 Eq. (35) 中的 L2 重建損失對應(yīng)二階估計意推，即如果兩個節(jié)點具備類似的近鄰豆瘫，則它們共享類似的隱藏表征。受表明一階估計重要性的網(wǎng)絡(luò)嵌入方法的啟發(fā)菊值，SDNE 修改了目標函數(shù)外驱，添加了一個類似于拉普拉斯特征映射的項：

圖 7：SDNE 框架圖育灸。節(jié)點的一階估計和二階估計都使用深度自編碼器來保存。

受到其他研究的啟發(fā)昵宇，DNGR [77] 將 Eq. (35) 中的轉(zhuǎn)換矩陣 P 替換成隨機 surfing 概率的正逐點互信息（PPMI）矩陣磅崭。這樣，原始特征可以與圖的隨機游走概率關(guān)聯(lián)起來瓦哎。但是砸喻，構(gòu)建這樣的輸入矩陣需要 O(N^2 ) 的時間復雜度，無法擴展到大規(guī)模圖杭煎。

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

解碼器是簡單的雙線性函數(shù)：

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

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

變分自編碼器

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

至于均值和方差矩陣的編碼器旬痹，作者采用 [36] 中的 GCN：

由于完整圖需要重建，其時間復雜度為 O(N^2)讨越。

受 SDNE 和 G2G 的啟發(fā)两残，DVNE [82] 提出另一個用于圖數(shù)據(jù)的 VAE，它也將每個節(jié)點表示為高斯分布把跨。但與之前使用 KL 散度作為度量的研究不同人弓，DVNE 使用 Wasserstein 距離來保留節(jié)點相似度的傳遞性。與 SDNE 和 G2G 類似着逐，DVNE 也在目標函數(shù)中保留一階估計和二階估計：

重建損失為：

圖 8：DVNE 框架圖崔赌。DVNE 使用 VAE 將節(jié)點表示為高斯分布，并采用 Wasserstein 距離來保留節(jié)點相似度的傳遞性耸别。

其他改進

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

近期進展

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

圖循環(huán)神經(jīng)網(wǎng)絡(luò)（Graph RNN）

You et al. [94] 將 Graph RNN 應(yīng)用到圖生成問題中囊扳。他們使用兩個 RNN吩翻，一個用于生成新節(jié)點兜看，另一個自回歸地為新添加的節(jié)點生成邊。他們展示了這種分層 RNN 架構(gòu)可以從輸入圖中高效學習狭瞎，且時間復雜度也是可接受的细移。

動態(tài)圖神經(jīng)網(wǎng)絡(luò)（Dynamic Graph Neural Network，DGNN）[95] 使用時間感知 LSTM [100] 來學習動態(tài)圖中的節(jié)點表征熊锭。在建立新的邊之后弧轧，DGNN 使用 LSTM 更新兩個交互節(jié)點（interacting node）及其直接近鄰的表征，即考慮一步傳播效應(yīng)（one-step propagation effect）碗殷。作者展示了時間感知 LSTM 可以很好地建模邊結(jié)構(gòu)的已建立順序以及時間間隔精绎，這反過來惠及大量圖應(yīng)用。

也可以將 Graph RNN 結(jié)合其他架構(gòu)锌妻，如 GCN 或 GAE代乃。例如，RMGCNN [96] 將 LSTM 應(yīng)用于 GCN 的結(jié)果仿粹，以漸進地重建圖（如圖 10 所示）搁吓。該方法旨在解決圖稀疏性問題。動態(tài) GCN [97] 使用 LSTM 收集動態(tài)網(wǎng)絡(luò)中不同時間片的 GCN 結(jié)果吭历，旨在捕獲時空圖信息堕仔。

圖 10：RMGCNN 架構(gòu)圖。RMGCNN 將 LSTM 添加到 GCN 中晌区，以漸進地重建圖摩骨。

圖強化學習

GCPN [98] 使用強化學習執(zhí)行目標導向的模塊化圖生成任務(wù)，以處理不可微目標和約束朗若。具體來說恼五，作者將圖生成建模為馬爾可夫決策過程，將生成模型作為在圖生成環(huán)境中運行的強化學習智能體捡偏。GCPN 將類似智能體動作作為連接預(yù)測問題唤冈，使用領(lǐng)域特定獎勵和對抗獎勵峡迷，使用 GCN 來學習節(jié)點表征银伟，從而通過策略梯度方法實現(xiàn)端到端地訓練。實驗結(jié)果證明 GCPN 在多種圖生成問題上的有效性绘搞。

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

結(jié)論與討論

應(yīng)用蒿褂。除了標準的圖推斷任務(wù)（如節(jié)點分類或圖分類）基于圖的深度學習方法還被應(yīng)用于大量學科圆米，如建模社會影響力 [103]卒暂、推薦 [51], [78], [96]、化學 [37], [41], [50], [98], [99]娄帖、物理 [104], [105]也祠、疾病預(yù)測或藥物預(yù)測 [106]–[108]、自然語言處理 [109], [110]近速、計算機視覺 [111]–[114]诈嘿、交通預(yù)測 [115], [116]、程序歸納 [117]削葱，以及解決基于圖的 NP 問題 [118], [119]奖亚。

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

不同類型的圖。圖數(shù)據(jù)的結(jié)構(gòu)變化萬千析砸，現(xiàn)有方法無法處理所有結(jié)構(gòu)昔字。例如，大部分方法聚焦于同質(zhì)圖首繁，很少有研究涉及異質(zhì)圖李滴，尤其是包含不同模態(tài)的圖。有符號網(wǎng)絡(luò)（其負邊表示節(jié)點之間的沖突）也有獨特結(jié)構(gòu)蛮瞄，對現(xiàn)有方法提出了挑戰(zhàn)所坯。表示兩個以上對象之間復雜關(guān)系的超圖（Hypergraph）也未得到完備研究。接下來重要的一步是涉特定的深度學習模型來處理這些不同類型的圖挂捅。

動態(tài)圖芹助。大部分現(xiàn)有方法聚焦于靜態(tài)圖。然而闲先，很多現(xiàn)實中的圖是動態(tài)的状土，其節(jié)點、邊和特征都會隨著時間而改變伺糠。例如蒙谓，在社交網(wǎng)絡(luò)中，人們可能建立新的社交關(guān)系训桶、刪除舊的關(guān)系累驮，其愛好和職位等特征都會隨著時間改變。新用戶可能會加入社交網(wǎng)絡(luò)舵揭，老用戶也可能離開谤专。如何建模動態(tài)圖不斷變化的特征，支持逐漸更新的模型參數(shù)午绳？這個問題仍然是個開放性問題置侍。一些初步研究嘗試使用 Graph RNN 架構(gòu)解決該問題，結(jié)果令人鼓舞 [95], [97]。

可解釋性蜡坊。由于圖通常與其他學科相關(guān)杠输，解釋圖深度學習模型對于決策問題來說是關(guān)鍵。例如秕衙，在醫(yī)療問題中抬伺，可解釋性在將計算機經(jīng)驗轉(zhuǎn)換為臨床使用中必不可少。但是灾梦，基于圖的深度學習模型比其他黑箱模型更難解釋峡钓，因為圖中的節(jié)點和邊高度關(guān)聯(lián)。

復合性若河。如前所述能岩，很多現(xiàn)有架構(gòu)可以結(jié)合起來使用，例如將 GCN 作為 GAE 或 Graph RNN 中的一個層萧福。除了涉及新的構(gòu)造塊以外拉鹃，如何符合這些已有架構(gòu)是一個有趣的未來研究方向。近期研究 Graph Networks [9] 跨出了第一步鲫忍，它使用 GNN 和 GCN 的通用框架來解決關(guān)系推理問題膏燕。

總之，上述調(diào)查展示了基于圖的深度學習是一個很有前景并發(fā)展迅速的領(lǐng)域悟民，機會與挑戰(zhàn)并存坝辫。研究基于圖的深度學習為建模關(guān)系數(shù)據(jù)提供了關(guān)鍵的構(gòu)造塊，也是走向更好的機器學習和人工智能時代的重要一步射亏。