今天新智元介紹清華大學朱文武教授組的一篇預印版綜述論文，全面回顧圖(graph)深度學習，從半監督、無監督和強化學習三大角度，系統介紹了GNN、GCN、圖自編碼器(GAE)等5大類模型及其應用和發展。

要說最近學界值得關注的趨勢，圖神經網絡(Graph Neural Network, GNN)或者說圖深度學習(Graph Deep Learning)絕對算得上一個。

昨天，阿里巴巴達摩院發布2019十大技術趨勢，其中就包括“超大規模圖神經網絡系統將賦予機器常識”：

單純的深度學習已經成熟，而結合了深度學習的圖神經網絡將端到端學習與歸納推理相結合，有望解決深度學習無法處理的關系推理、可解釋性等一系列問題。強大的圖神經網絡將會類似于由神經元等節點所形成網絡的人的大腦，機器有望成為具備常識，具有理解、認知能力的AI。

此前，新智元曾經報道過清華大學孫茂松教授組對圖神經網絡(GNN)的綜述(arxiv預印版)，全面闡述了GNN及其方法和應用，便于讀者快速了解GNN領域不同模型的動機與優勢。

今天，新智元再介紹另一篇清華大學與GNN有關的綜述，這次是朱文武教授組發布在arxiv的預印版論文Deep Learning on Graphs: A Survey。

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

在這項工作中，作者全面回顧了應用于圖(graph)的各種深度學習方法，從以下三方面系統闡述這些方法及其差異：

半監督方法，包括圖神經網絡(GNN)和圖卷積網絡(GCN)

無監督方法，包括圖自動編碼器(GAE)

最新進展，包括圖遞歸神經網絡（Graph RNN）和圖強化學習(Graph RL)

從互聯網、供應鏈、化合物的分子結構、感染的傳播途徑，到世界上最復雜的結構——人腦神經系統，都可以用圖(Graph)來表示。

然而，由于圖的特殊性，將其應用于深度學習并非易事。圖深度學習的潛力巨大已無需贅言，想要快速入門并掌握相關線索，這無疑又是一份極好的資料。

作者在論文中寫道，

我們的研究與已有文獻的不同之處在于，我們系統而全面地回顧了Graph的不同深度學習架構，而不是專注于一個特定的分支。

其次，我們關注的是不同的深度學習模型可以如何應用于圖，這與傳統的網絡嵌入不同。后者指將節點嵌入到低維向量空間中，可以被視為圖深度學習的具體例子(而且它們也可以使用非深度學習方法)。

關于網絡嵌入，可以參考朱文武老師組另一篇綜述：Peng Cui, Xiao Wang, Jian Pei, Wenwu Zhu. A Survey on Network Embedding. IEEE TKDE, 2018”

論文(點擊“閱讀原文”訪問)：https://arxiv.org/pdf/1812.04202v1.pdf

以下是新智元對這篇綜述的摘譯。

三大角度，全面回顧圖深度學習(GraphDL)

在過去10年中，深度學習一直是人工智能和機器學習領域“皇冠上的明珠”，在聲學、圖像和自然語言處理中表現出優越的性能。深度學習從底層數據提取復雜模式的表達能力已經得到充分認識。

另一方面，圖(graph)[注1：“圖”(Graphs)也被稱為“網絡”(networks)，本文交替采用這兩個術語]在現實世界中無處不在，它代表著各種對象及其相互關系，如社交網絡、電子商務網絡、生物網絡和交通網絡。

圖具有復雜的結構，其中包含豐富的潛在價值。

因此，如何利用深度學習方法進行圖數據分析，在過去的幾年里引起了相當多的研究關注。

這個問題非常重要，因為將傳統的深度學習架構應用到圖中存在幾個挑戰:

不規則域(Irregular domain)。與圖像、音頻、文本等具有清晰網格結構的數據不同，圖處于不規則的域中，使得很難將一些基本的數學運算推廣到圖中。例如，卷積神經網絡(CNN)中的基本操作“卷積”和“池化”，在圖數據中并不能直接地定義。這通常被稱為幾何深度學習問題。

不同的結構和任務。圖本身具有復雜的結構。例如，圖可以是異質的或同質的，加權的或不加權的，有符號的或無符號的。此外，圖的任務也有很大的不同，可以是node-focused問題，如節點分類和鏈接預測，也可以是graph-focused問題，如圖分類和圖生成。不同的結構和任務需要不同的模型架構來處理特定的問題。

可擴展性和并行化。在大數據時代，真實的圖很容易就會有數百萬個節點和邊，例如社交網絡或電子商務網絡。因此，如何設計具有線性時間復雜度的可擴展模型，成為一個關鍵問題。此外，由于圖的節點和邊是相互連接的，通常需要作為一個整體進行建模，因此，如何進行并行計算是另一個關鍵問題。

跨學科性。圖常常與其他學科相關聯，例如生物學、化學或社會科學。跨學科性既帶來機遇，也帶來了挑戰：領域知識可以被用來解決特定的問題，但是集成領域知識可能使得模型設計更加困難。例如，在生成分子圖(molecular graphs)時，目標函數和化學約束通常是不可微的，因此不容易應用基于梯度的訓練方法。

為了應對這些挑戰，研究人員在這一領域做出了巨大的努力，產生了豐富的相關論文和方法的文獻。采用的架構也有很大的差異，從監督到無監督，從卷積到遞歸。然而，據我們所知，很少有人系統地總結這些不同方法之間的差異和聯系。

本文試圖通過對圖深度學習方法進行全面回顧來填補這一空白。

如圖1所示，我們將現有的方法分為三大類：半監督方法、無監督方法和最近的進展。

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

具體來說，半監督方法包括圖神經網絡(GNN)和圖卷積網絡(GCN)；無監督方法主要有圖自編碼器(GAE)；最近的進展包括圖遞歸神經網絡和圖強化學習。

那么這些分類有什么區別呢？先看下這張表：

一些圖深度學習方法的主要區別

從廣義上來看，GNN和GCN是半監督的，因為它們利用節點屬性和節點標簽來針對特定任務端到端地訓練模型參數。

而GAE主要關注學習使用無監督方法的表示。最新提出的方法則使用其他一些獨特算法。

在接下來的部分，我們將詳細介紹這些方法，主要介紹它們的發展歷史，以及這些方法如何解決圖的挑戰。我們還分析了這些模型之間的差異，以及如何組合不同的架構。最后，我們簡要概述了這些方法的應用，并討論了未來的研究方向。

清晰圖表，詳盡闡述 GNN、GCN、GAE等5類模型

圖神經網絡(GNN)

圖神經網絡是圖數據最原始的半監督深度學習方法。

GNN的思路很簡單：為了編碼圖的結構信息，每個節點可以由低維狀態向量表示。對于以圖為中心的任務，建議添加一個特殊節點，這個節點具有與整個圖相對應的唯一屬性。

回顧過去，GNN統一了一些處理圖數據的早期方法，如遞歸神經網絡和馬爾可夫鏈。

展望未來，GNN中的概念具有深遠的啟示：許多最先進的GCN實際上遵循與鄰近節點交換信息的框架。事實上，GNN和GCN可以統一到一個通用框架中，GNN相當于GCN使用相同層來達到的穩定狀態。

從概念角度來看，GNN是非常重要的，但它也有幾個缺點：

首先，在其計算過程中，公式(具體公式可查看原文)中的映射必須是壓縮映射，這就嚴重限制了建模能力。

其次，由于在梯度下降步驟之間需要許多迭代，因此GNN在計算上的代價是昂貴的。

或許是因為這些原因，GNN并未被社區所熟知。

圖卷積網絡(GCN)

除了GNN，圖卷積網絡(GCN)是圖的另一類半監督方法。由于GCN通常可以像標準的CNN那樣通過反向傳播來訓練特定任務的損失，所以本文主要關注其采用的體系結構。

下表總結了本文所研究的GCN的主要特征：

不同圖卷積網絡之間的比較

可以看到在本文所研究的22種GCN方法中，從類型角度看分為兩種，一種是光譜域(Spectral)、另一種是空間域(Spatial)。

在卷積操作過程中，每種方法所采用的技術也大不相同，主要包括插值核(Interpolation Kernel)、多項式、First-order以及Random Walk等等。

在Readout方面，主要包括分層聚類、分層聚類+FC、Set2set等等技術。當然在在可擴展性、節點特征以及其它改進方面也各不相同。

圖自編碼器(GAE)

自編碼器(AE)和變分自編碼器(VAE)廣泛應用于無監督學習中，它們適用于學習無監督信息的圖節點表示。下表總結了本文所研究的GAE主要特征：

不同GAE之間的比較

可以看到，在本文所研究的10種GAE方法中，7種屬于自編碼器(AE)、3種屬于變分自編碼器(VAE)。

每種方法采用的降維方法也有所不同，主要包括L2-Reconstruction、拉普拉斯特征映射(Laplacian Eigenmap)、遞歸Reconstruction、排序、GAN等等。

在可擴展性、節點特征以及其它改進方面也各不相同。

除了上述兩個主要分類外，也有一些進展值得討論。

首先是對抗性訓練方案，尤其是生成對抗網絡(GAN)，這是最近機器學習領域的一個熱門話題。

GAN的基本思想是構建兩個相關聯的模型，一個判別器和一個生成器。生成器的目的是通過產生假數據來“欺騙”判別器，判別器的目的是區分樣本是真實數據還是由生成器產生的假數據。然后，兩個模型可以通過極大極小博弈進行聯合訓練，從而相互受益。

S. Pan等人 [83]將對抗訓練方案作為一個額外的正則化項納入GAE。整個架構如圖9所示。具體來說，編碼器用作生成器，判別器的目的是區分潛在表示是來自生成器還是來自先驗分布。這樣，自動編碼器就被強制匹配先驗分布以作為正則化。

圖9：文獻[83]中ARGA/ARVGA的框架

最新的進展

除了前面提到的半監督方法和無監督方法之外，我們在這一節中還討論了一些最新的高級方法。它們的主要特性如表5所示。

表5：一些最新進展的主要特性

圖遞歸神經網絡

遞歸神經網絡(RNN)，例如GRU或LSTM是建模序列數據的一個實際標準，在GNN中用于模擬節點狀態。

RNN也可以用于圖級別。為了消除歧義，我們將這種架構稱為Graph RNNs。

You et al. [94]將Graph RNN應用于圖生成問題。具體來說，他們采用兩個RNN，一個用于生成新的節點，另一個用于以自回歸的方式為新添加的節點生成邊。結果表明，與傳統的基于規則的圖生成模型相比，這種分層RNN結構在具有可接受的時間復雜度的同時，能夠有效地從輸入圖中學習。

動態圖神經網絡(Dynamic Graph Neural Network, DGNN)[95]提出利用 time-aware LSTM[100]來學習動態圖中的節點表示。作者表明， time-aware LSTM可以很好地建模邊形成的順序和時間間隔，從而有利于圖的廣泛應用。

也可以將Graph RNN與其他架構(如GCN或GAE)結合使用。例如RMGCNN[96]將LSTM應用于GCN的結果，逐步重構圖，如圖10所示，旨在解決圖的稀疏性問題。Dynamic GCN[97]應用LSTM在動態網絡中收集不同時間片段的GCN結果，目的是獲取空間和時間圖信息。

圖10：RMGCNN的框架

圖強化學習

GCPN[98]利用RL生成目標導向的分子圖，以處理不可導目標和約束。實驗結果證明了GCPN在各種圖生成問題中的有效性。

MolGAN[99]也采用了類似的思想，即使用RL生成分子圖。MolGAN建議直接生成完整的圖，而不是通過一系列的動作來生成圖，這對小分子很有效。

基于圖的深度學習的應用和未來方向

應用

除了標準圖推理等任務，如節點分類或圖分類，基于深度學習的方法也已經應用于廣泛的學科，如建模社會影響、推薦、化學、物理、疾病或藥物預測、自然語言處理、計算機視覺、交通預測、程序歸納、以及求解基于圖的NP問題。

這些應用還表明，基于圖的深度學習不僅有助于挖掘現有圖數據背后的豐富價值，而且還通過將關系數據自然地建模為圖，有助于推進其他學科的發展，極大地擴大了基于圖的深度學習的適用性。

以下幾個正在進行或未來的方向值得關注：

不同類型的圖。由于圖數據結構極其不同，現有的方法無法處理所有的圖數據。下一個重要的方向是設計特定的深度學習模型來處理這些不同類型的圖。

動態圖。大多數現有方法關注于靜態圖。然而，許多真實圖本質上是動態的，其中節點、邊及其特征可以隨著時間的推移而改變。例如，在社交網絡中，人們可能建立新的社會關系，刪除舊的關系，他們所扮演的角色，例如愛好和職業可以隨著時間的推移而改變。新用戶可以加入網絡，老用戶可以離開。如何對動態圖的演化特征進行建模，并支持模型參數的增量更新，在很大程度上仍是未解決的問題。

可解釋性。由于圖通常與其他學科相關，因此，對基于圖的深度學習模型作出解釋對于決策問題至關重要。例如，在醫學或與疾病有關的問題中，在將計算機實驗轉化為臨床應用方面，可解釋性是必不可少的。然而，由于圖中的節點和邊是高度互連的，基于圖的深度學習的可解釋性甚至比其他黑盒模型更具挑戰性。

組合性。如前幾節所示，許多現有的架構可以一起工作，例如使用GCN作為GAEs或Graph RNNs中的一個層。除了設計新的構建塊，如何有原則地組合這些架構是一個有趣的方向。

綜上所述，我們的研究表明，圖深度學習是一個很有前途、且發展迅速的研究領域，既有令人興奮的機會，也有挑戰。研究圖深度學習是關系數據建模的關鍵部分，是邁向更好的機器學習和人工智能時代的重要一步。