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

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

昨天，阿里巴巴達摩院發(fā)布2019十大技術(shù)趨勢，其中就包括“超大規(guī)模圖神經(jīng)網(wǎng)絡(luò)系統(tǒng)將賦予機器常識”：

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

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

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

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

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

半監(jiān)督方法，包括圖神經(jīng)網(wǎng)絡(luò)(GNN)和圖卷積網(wǎng)絡(luò)(GCN)

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

最新進展，包括圖遞歸神經(jīng)網(wǎng)絡(luò)（Graph RNN）和圖強化學習(Graph RL)

從互聯(lián)網(wǎng)、供應(yīng)鏈、化合物的分子結(jié)構(gòu)、感染的傳播途徑，到世界上最復(fù)雜的結(jié)構(gòu)——人腦神經(jīng)系統(tǒng)，都可以用圖(Graph)來表示。

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

作者在論文中寫道，

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

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

關(guān)于網(wǎng)絡(luò)嵌入，可以參考朱文武老師組另一篇綜述：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年中，深度學習一直是人工智能和機器學習領(lǐng)域“皇冠上的明珠”，在聲學、圖像和自然語言處理中表現(xiàn)出優(yōu)越的性能。深度學習從底層數(shù)據(jù)提取復(fù)雜模式的表達能力已經(jīng)得到充分認識。

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

圖具有復(fù)雜的結(jié)構(gòu)，其中包含豐富的潛在價值。

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

這個問題非常重要，因為將傳統(tǒng)的深度學習架構(gòu)應(yīng)用到圖中存在幾個挑戰(zhàn):

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

不同的結(jié)構(gòu)和任務(wù)。圖本身具有復(fù)雜的結(jié)構(gòu)。例如，圖可以是異質(zhì)的或同質(zhì)的，加權(quán)的或不加權(quán)的，有符號的或無符號的。此外，圖的任務(wù)也有很大的不同，可以是node-focused問題，如節(jié)點分類和鏈接預(yù)測，也可以是graph-focused問題，如圖分類和圖生成。不同的結(jié)構(gòu)和任務(wù)需要不同的模型架構(gòu)來處理特定的問題。

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

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

為了應(yīng)對這些挑戰(zhàn)，研究人員在這一領(lǐng)域做出了巨大的努力，產(chǎn)生了豐富的相關(guān)論文和方法的文獻。采用的架構(gòu)也有很大的差異，從監(jiān)督到無監(jiān)督，從卷積到遞歸。然而，據(jù)我們所知，很少有人系統(tǒng)地總結(jié)這些不同方法之間的差異和聯(lián)系。

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

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

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

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

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

一些圖深度學習方法的主要區(qū)別

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

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

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

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

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

圖神經(jīng)網(wǎng)絡(luò)是圖數(shù)據(jù)最原始的半監(jiān)督深度學習方法。

GNN的思路很簡單：為了編碼圖的結(jié)構(gòu)信息，每個節(jié)點可以由低維狀態(tài)向量表示。對于以圖為中心的任務(wù)，建議添加一個特殊節(jié)點，這個節(jié)點具有與整個圖相對應(yīng)的唯一屬性。

回顧過去，GNN統(tǒng)一了一些處理圖數(shù)據(jù)的早期方法，如遞歸神經(jīng)網(wǎng)絡(luò)和馬爾可夫鏈。

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

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

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

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

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

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

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

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

不同圖卷積網(wǎng)絡(luò)之間的比較

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

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

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

圖自編碼器(GAE)

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

不同GAE之間的比較

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

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

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

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

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

GAN的基本思想是構(gòu)建兩個相關(guān)聯(lián)的模型，一個判別器和一個生成器。生成器的目的是通過產(chǎn)生假數(shù)據(jù)來“欺騙”判別器，判別器的目的是區(qū)分樣本是真實數(shù)據(jù)還是由生成器產(chǎn)生的假數(shù)據(jù)。然后，兩個模型可以通過極大極小博弈進行聯(lián)合訓練，從而相互受益。

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

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

最新的進展

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

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

圖遞歸神經(jīng)網(wǎng)絡(luò)

遞歸神經(jīng)網(wǎng)絡(luò)(RNN)，例如GRU或LSTM是建模序列數(shù)據(jù)的一個實際標準，在GNN中用于模擬節(jié)點狀態(tài)。

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

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

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

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

圖10：RMGCNN的框架

圖強化學習

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

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

基于圖的深度學習的應(yīng)用和未來方向

應(yīng)用

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

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

以下幾個正在進行或未來的方向值得關(guān)注：

不同類型的圖。由于圖數(shù)據(jù)結(jié)構(gòu)極其不同，現(xiàn)有的方法無法處理所有的圖數(shù)據(jù)。下一個重要的方向是設(shè)計特定的深度學習模型來處理這些不同類型的圖。

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

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

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

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