來(lái)源:Arxiv ,新智元

深度學(xué)習(xí)的最大軟肋是什么？

這個(gè)問(wèn)題的回答仁者見(jiàn)仁,，但圖靈獎(jiǎng)得主Judea Pearl大概有99.9%的幾率會(huì)說(shuō),，是無(wú)法進(jìn)行因果推理。

對(duì)于這個(gè)問(wèn)題,，業(yè)界正在進(jìn)行積極探索,，而其中一個(gè)很有前景的方向就是圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Network, GNN)。

最近,，清華大學(xué)孫茂松教授組在 arXiv 發(fā)布了論文 Graph Neural Networks: A Review of Methods and Applications,，作者對(duì)現(xiàn)有的GNN模型做了詳盡且全面的綜述。

作者：周界*,、崔淦渠*,、張正彥*，楊成,，劉知遠(yuǎn),，孫茂松

“圖神經(jīng)網(wǎng)絡(luò)是連接主義與符號(hào)主義的有機(jī)結(jié)合，不僅使深度學(xué)習(xí)模型能夠應(yīng)用在圖這種非歐幾里德結(jié)構(gòu)上,，還為深度學(xué)習(xí)模型賦予了一定的因果推理能力,。”論文的共同第一作者周界說(shuō),。

“在深度學(xué)習(xí)方法的魯棒性與可解釋性受到質(zhì)疑的今天,，圖神經(jīng)網(wǎng)絡(luò)可能為今后人工智能的發(fā)展提供了一個(gè)可行的方向?！?/span>

GNN最近在深度學(xué)習(xí)領(lǐng)域受到了廣泛關(guān)注,。然而，對(duì)于想要快速了解這一領(lǐng)域的研究人員來(lái)說(shuō)，可能會(huì)面臨著模型復(fù)雜,、應(yīng)用門類眾多的問(wèn)題,。

“本文希望為讀者提供一個(gè)更高層次的視角，快速了解GNN領(lǐng)域不同模型的動(dòng)機(jī)與優(yōu)勢(shì),?！敝芙绺嬖V新智元：“同時(shí)，通過(guò)對(duì)不同的應(yīng)用進(jìn)行分類,，方便不同領(lǐng)域的研究者快速了解將GNN應(yīng)用到不同領(lǐng)域的文獻(xiàn),。”

毫不夸張地說(shuō),，論文中的圖表對(duì)于想要了解學(xué)習(xí)GNN乃至因果推理等方向的研究者來(lái)說(shuō),，簡(jiǎn)直應(yīng)該高清打印過(guò)塑然后貼在墻上以作參考——

GNN的各種變體，通過(guò)比對(duì)各自的 aggregator & updater,，就能輕松分辨不同的GNN模型,。這只是這篇綜述強(qiáng)大圖表的一個(gè)示例。

在內(nèi)容上,，模型方面，本文從GNN原始模型的構(gòu)建方式與存在的問(wèn)題出發(fā),，介紹了對(duì)其進(jìn)行不同改進(jìn)的GNN變體,，包括如何處理不同的圖的類型、如何進(jìn)行高效的信息傳遞以及如何加速訓(xùn)練過(guò)程,。最后介紹了幾個(gè)近年來(lái)提出的通用框架,，它們總結(jié)概括了多個(gè)現(xiàn)有的方法，具有較強(qiáng)的表達(dá)能力,。

在應(yīng)用上,，文章將GNN的應(yīng)用領(lǐng)域分為了結(jié)構(gòu)化場(chǎng)景、非結(jié)構(gòu)化場(chǎng)景以及其他場(chǎng)景并介紹了諸如物理,、化學(xué),、圖像、文本,、圖生成模型,、組合優(yōu)化問(wèn)題等經(jīng)典的GNN應(yīng)用。

典型應(yīng)用場(chǎng)景介紹

文章最后提出了四個(gè)開(kāi)放性問(wèn)題,，包括如何處理堆疊多層GNN造成的平滑問(wèn)題,，如何處理動(dòng)態(tài)變化的圖結(jié)構(gòu)，如何使用通用的方法處理非結(jié)構(gòu)化的數(shù)據(jù)以及如何將其擴(kuò)展到更大規(guī)模的網(wǎng)絡(luò)上,。

作者還整理了一個(gè)GNN論文列表：

https://github.com/thunlp/GNNPapers

以下是小編對(duì)這篇綜述的部分摘譯,，點(diǎn)擊閱讀原文查看 arXiv 論文,。

GNN的概念首先是在F. Scarselli等人的論文The graph neural network model（F. Scarselli et. al. 2009）中提出的。在這里,，我們描述了原始的GNN,，并列舉了原始GNN在表示能力和訓(xùn)練效率方面的局限性。

接著,，我們介紹了幾種不同的GNN變體,，這些變體具有不同的圖形類型，利用不同的傳播函數(shù)和訓(xùn)練方法,。

最后,，我們介紹了三個(gè)通用框架，分別是message passing neural network (MPNN),，non-local neural network (NLNN),，以及graph network(GN)。MPNN結(jié)合了各種圖神經(jīng)網(wǎng)絡(luò)和圖卷積網(wǎng)絡(luò)方法,；NLNN結(jié)合了幾種“self-attention”類型的方法,；而圖網(wǎng)絡(luò)GN可以概括本文提到的幾乎所有圖神經(jīng)網(wǎng)絡(luò)變體,。

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

如前所述,，圖神經(jīng)網(wǎng)絡(luò)(GNN)的概念最早是Scarselli等人在2009年提出的，它擴(kuò)展了現(xiàn)有的神經(jīng)網(wǎng)絡(luò),，用于處理圖(graph)中表示的數(shù)據(jù),。在圖中，每個(gè)節(jié)點(diǎn)是由其特性和相關(guān)節(jié)點(diǎn)定義的,。

雖然實(shí)驗(yàn)結(jié)果表明,，GNN是建模結(jié)構(gòu)化數(shù)據(jù)的強(qiáng)大架構(gòu)，但原始GNN仍存在一些局限性,。

首先,，對(duì)于固定節(jié)點(diǎn)，原始GNN迭代更新節(jié)點(diǎn)的隱藏狀態(tài)是低效的,。如果放寬了固定點(diǎn)的假設(shè),，我們可以設(shè)計(jì)一個(gè)多層的GNN來(lái)得到節(jié)點(diǎn)及其鄰域的穩(wěn)定表示。

其次,，GNN在迭代中使用相同的參數(shù),，而大多數(shù)流行的神經(jīng)網(wǎng)絡(luò)在不同的層中使用不同的參數(shù)，這是一種分層特征提取方法,。此外,，節(jié)點(diǎn)隱藏狀態(tài)的更新是一個(gè)順序過(guò)程，可以從RNN內(nèi)核(如GRU 和 LSTM)中獲益,。

第三,，在邊上也有一些無(wú)法在原始GNN中建模的信息特征,。此外，如何學(xué)習(xí)邊的隱藏狀態(tài)也是一個(gè)重要的問(wèn)題,。

最后,，如果我們把焦點(diǎn)放在節(jié)點(diǎn)的表示上而不是圖形上，就不適合使用固定點(diǎn),，因?yàn)樵诠潭c(diǎn)上的表示的分布在數(shù)值上是平滑的,，區(qū)分每個(gè)節(jié)點(diǎn)的信息量也比較少。

在這一節(jié),，我們提出圖神經(jīng)網(wǎng)絡(luò)的幾種變體,。首先是在不同圖類型上運(yùn)行的變體，這些變體擴(kuò)展了原始模型的表示能力,。其次,，我們列出了在傳播步驟進(jìn)行修改（卷積、門機(jī)制,、注意力機(jī)制和skip connection）的幾種變體,，這些模型可以更好地學(xué)習(xí)表示。最后,，我們描述了使用高級(jí)訓(xùn)練方法的標(biāo)題,，這些方法提高了訓(xùn)練效率。

圖2概述了GNN的不同變體,。

一覽GNN的不同變體

圖的類型(Graph Types)

在原始GNN中,，輸入的圖由帶有標(biāo)簽信息的節(jié)點(diǎn)和無(wú)向的邊組成，這是最簡(jiǎn)單的圖形格式,。然而,，世界上有許多不同的圖形。這里,，我們將介紹一些用于建模不同類型圖形的方法,。

圖類型的變體

• 有向圖(Directed Graphs )

圖形的第一個(gè)變體是有向圖。無(wú)向邊可以看作是兩個(gè)有向邊,，表明兩個(gè)節(jié)點(diǎn)之間存在著關(guān)系,。然而，有向邊比無(wú)向邊能帶來(lái)更多的信息,。例如,，在一個(gè)知識(shí)圖中，邊從head實(shí)體開(kāi)始到tail實(shí)體結(jié)束,，head實(shí)體是tail實(shí)體的父類,，這表明我們應(yīng)該區(qū)別對(duì)待父類和子類的信息傳播過(guò)程。有向圖的實(shí)例有ADGPM (M. Kampffmeyer et. al. 2018),。

• 異構(gòu)圖(Heterogeneous Graphs)

圖的第二個(gè)變體是異構(gòu)圖,，異構(gòu)圖有幾種類型的節(jié)點(diǎn),。處理異構(gòu)圖最簡(jiǎn)單的方法是將每個(gè)節(jié)點(diǎn)的類型轉(zhuǎn)換為與原始特征連接的一個(gè)one-hot特征向量。異構(gòu)圖如GraphInception,。

• 帶邊信息的圖(Edge-informative Graph)

圖的另外一個(gè)變體是,，每條邊都有信息，比如權(quán)值或邊的類型,。例如G2S和R-GCN,。

使用不同訓(xùn)練方法的圖變體

訓(xùn)練方法變體

在傳播步驟進(jìn)行修改的GNN變體

傳播步驟變體

除了圖神經(jīng)網(wǎng)絡(luò)的不同變體之外，我們還介紹了幾個(gè)通用框架,，旨在將不同的模型集成到一個(gè)框架中,。

J. Gilmer等人(J. Gilmer et. al. 2017)提出了消息傳遞神經(jīng)網(wǎng)絡(luò)(message passing neural network， MPNN),，統(tǒng)一了各種圖神經(jīng)網(wǎng)絡(luò)和圖卷積網(wǎng)絡(luò)方法,。

X. Wang等人(X. Wang et. al. 2017)提出了非局部神經(jīng)網(wǎng)絡(luò)(non-local neural network, NLNN)，它結(jié)合了幾種“self-attention”風(fēng)格的方法,。

P. W. Battaglia等人(P. W. Battaglia et. al. 2018)提出了圖網(wǎng)絡(luò)(graph network, GN),，它統(tǒng)一了統(tǒng)一了MPNN和NLNN方法以及許多其他變體，如交互網(wǎng)絡(luò)(Interaction Networks),，神經(jīng)物理引擎(Neural Physics Engine),，CommNet，structure2vec,，GGNN,，關(guān)系網(wǎng)絡(luò)(Relation Network),，Deep Sets和Point Net,。

盡管GNN在不同領(lǐng)域取得了巨大成功，但值得注意的是,，GNN模型還不能在任何條件下,，為任何圖任務(wù)提供令人滿意的解決方案。這里,，我們將陳述一些開(kāi)放性問(wèn)題以供進(jìn)一步研究,。

淺層結(jié)構(gòu)

傳統(tǒng)的深度神經(jīng)網(wǎng)絡(luò)可以堆疊數(shù)百層，以獲得更好的性能,，因?yàn)楦畹慕Y(jié)構(gòu)具備更多的參數(shù),，可以顯著提高網(wǎng)絡(luò)的表達(dá)能力。然而,，GNN總是很淺,，大多數(shù)不超過(guò)三層。

實(shí)驗(yàn)顯示,，堆疊多個(gè)GCN層將導(dǎo)致過(guò)度平滑,，也就是說(shuō),，所有頂點(diǎn)將收斂到相同的值。盡管一些研究人員設(shè)法解決了這個(gè)問(wèn)題,，但這仍然是GNN的最大局限所在,。設(shè)計(jì)真正的深度GNN對(duì)于未來(lái)的研究來(lái)說(shuō)是一個(gè)令人興奮的挑戰(zhàn)，并將對(duì)進(jìn)一步深入理解GNN做出相當(dāng)大的貢獻(xiàn),。

動(dòng)態(tài)圖形另一個(gè)具有挑戰(zhàn)性的問(wèn)題是如何處理具有動(dòng)態(tài)結(jié)構(gòu)的圖形,。靜態(tài)圖總是穩(wěn)定的，因此對(duì)其進(jìn)行建模是可行的,，而動(dòng)態(tài)圖引入了變化的結(jié)構(gòu),。當(dāng)邊和節(jié)點(diǎn)出現(xiàn)或消失時(shí)，GNN不能自適應(yīng)地做出改變,。目前對(duì)動(dòng)態(tài)GNN的研究也在積極進(jìn)行中,，我們認(rèn)為它是一般GNN的具備穩(wěn)定性和自適應(yīng)性的重要里程碑。

非結(jié)構(gòu)性場(chǎng)景

我們討論了GNN在非結(jié)構(gòu)場(chǎng)景中的應(yīng)用,，但我們沒(méi)有找到從原始數(shù)據(jù)中生成圖的最佳方法,。在圖像域中，一些研究可以利用CNN獲取特征圖,，然后對(duì)其進(jìn)行上采樣,，形成超像素作為節(jié)點(diǎn)，還有的直接利用一些對(duì)象檢測(cè)算法來(lái)獲取對(duì)象節(jié)點(diǎn),。在文本域中,，有些研究使用句法樹(shù)作為句法圖，還有的研究采用全連接圖,。因此,，關(guān)鍵是找到圖生成的最佳方法，使GNN在更廣泛的領(lǐng)域發(fā)揮更大的作用,。

可擴(kuò)展性問(wèn)題

如何將嵌入式算法應(yīng)用于社交網(wǎng)絡(luò)或推薦系統(tǒng)這類大規(guī)模網(wǎng)絡(luò)環(huán)境,，是幾乎所有圖形嵌入算法面對(duì)的一個(gè)致命問(wèn)題，GNN也不例外,。對(duì)GNN進(jìn)行擴(kuò)展是很困難的,，因?yàn)樯婕捌渲械脑S多核心流程在大數(shù)據(jù)環(huán)境中都要消耗算力。

這種困難體現(xiàn)在幾個(gè)方面：首先,，圖數(shù)據(jù)并不規(guī)則,，每個(gè)節(jié)點(diǎn)都有自己的鄰域結(jié)構(gòu)，因此不能批量化處理,。其次,，當(dāng)存在的節(jié)點(diǎn)和邊數(shù)量達(dá)到數(shù)百萬(wàn)時(shí)，計(jì)算圖的拉普拉斯算子也是不可行的,。此外,，我們需要指出,，可擴(kuò)展性的高低，決定了算法是否能夠應(yīng)用于實(shí)際場(chǎng)景,。目前已經(jīng)有一些研究提出了解決這個(gè)問(wèn)題的辦法,，我們正在密切關(guān)注這些新進(jìn)展。

在過(guò)去幾年中,，GNN已經(jīng)成為圖領(lǐng)域機(jī)器學(xué)習(xí)任務(wù)的強(qiáng)大而實(shí)用的工具,。這一進(jìn)展有賴于表現(xiàn)力，模型靈活性和訓(xùn)練算法的進(jìn)步,。在本文中,，我們對(duì)圖神經(jīng)網(wǎng)絡(luò)進(jìn)行了全面綜述。對(duì)于GNN模型,，我們引入了按圖類型,、傳播類型和訓(xùn)練類型分類的GNN變體。

此外,，我們還總結(jié)了幾個(gè)統(tǒng)一表示不同GNN變體的通用框架,。在應(yīng)用程序分類方面，我們將GNN應(yīng)用程序分為結(jié)構(gòu)場(chǎng)景,、非結(jié)構(gòu)場(chǎng)景和其他18個(gè)場(chǎng)景,，然后對(duì)每個(gè)場(chǎng)景中的應(yīng)用程序進(jìn)行詳細(xì)介紹。最后,，我們提出了四個(gè)開(kāi)放性問(wèn)題,，指出了圖神經(jīng)網(wǎng)絡(luò)的主要挑戰(zhàn)和未來(lái)的研究方向，包括模型深度,、可擴(kuò)展性,、動(dòng)態(tài)圖處理和對(duì)非結(jié)構(gòu)場(chǎng)景的處理能力。

廣告 & 商務(wù)合作請(qǐng)加微信：kellyhyw    

投稿請(qǐng)發(fā)送至：mary.hu@aisdk.com