CNN已老，GNN來了！清華大學孫茂松組一文綜述GNN

新智元報道

來源：Arxiv 編輯：文強，肖琴，大明

【新智元導讀】深度學習無法進行因果推理，而圖模型(GNN)或是解決方案之一。清華大學孫茂松教授組發表綜述論文，全面闡述GNN及其方法和應用，並提出一個能表徵各種不同GNN模型中傳播步驟的統一表示。文中圖表，建議高清列印過塑貼放手邊作參考。

深度學習的最大軟肋是什麼？

這個問題的回答仁者見仁，但圖靈獎得主Judea Pearl大概有99.9%的幾率會說，是無法進行因果推理。

對於這個問題，業界正在進行積極探索，而其中一個很有前景的方向就是圖神經網路(Graph Neural Network, GNN)。

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

作者：周界*、崔淦渠*、張正彥*，楊成，劉知遠，孫茂松

「圖神經網路是連接主義與符號主義的有機結合，不僅使深度學習模型能夠應用在圖這種非歐幾里德結構上，還為深度學習模型賦予了一定的因果推理能力。」論文的共同第一作者周界說。

「在深度學習方法的魯棒性與可解釋性受到質疑的今天，圖神經網路可能為今後人工智慧的發展提供了一個可行的方向。」

GNN最近在深度學習領域受到了廣泛關注。然而，對於想要快速了解這一領域的研究人員來說，可能會面臨著模型複雜、應用門類眾多的問題。

「本文希望為讀者提供一個更高層次的視角，快速了解GNN領域不同模型的動機與優勢。」周界告訴新智元：「同時，通過對不同的應用進行分類，方便不同領域的研究者快速了解將GNN應用到不同領域的文獻。」

毫不誇張地說，論文中的圖表對於想要了解學習GNN乃至因果推理等方向的研究者來說，簡直應該高清列印過塑然後貼在牆上以作參考——

GNN的各種變體，通過比對各自的 aggregator & updater，就能輕鬆分辨不同的GNN模型。這只是這篇綜述強大圖表的一個示例。

想要快速了解GNN，看這篇文章絕對沒錯

在內容上，模型方面，本文從GNN原始模型的構建方式與存在的問題出發，介紹了對其進行不同改進的GNN變體，包括如何處理不同的圖的類型、如何進行高效的信息傳遞以及如何加速訓練過程。最後介紹了幾個近年來提出的通用框架，它們總結概括了多個現有的方法，具有較強的表達能力。

在應用上，文章將GNN的應用領域分為了結構化場景、非結構化場景以及其他場景並介紹了諸如物理、化學、圖像、文本、圖生成模型、組合優化問題等經典的GNN應用。

典型應用場景介紹

文章最後提出了四個開放性問題，包括如何處理堆疊多層GNN造成的平滑問題，如何處理動態變化的圖結構，如何使用通用的方法處理非結構化的數據以及如何將其擴展到更大規模的網路上。

作者還整理了一個GNN論文列表：

https://github.com/thunlp/GNNPapers

原始GNN及其局限性

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

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

最後，我們介紹了三個通用框架，分別是message passing neural network (MPNN)，non-local neural network (NLNN)，以及graph network(GN)。MPNN結合了各種圖神經網路和圖卷積網路方法；NLNN結合了幾種「self-attention」類型的方法；而圖網路GN可以概括本文提到的幾乎所有圖神經網路變體。

圖神經網路

如前所述，圖神經網路(GNN)的概念最早是Scarselli等人在2009年提出的，它擴展了現有的神經網路，用於處理圖(graph)中表示的數據。在圖中，每個節點是由其特性和相關節點定義的。

雖然實驗結果表明，GNN是建模結構化數據的強大架構，但原始GNN仍存在一些局限性。

首先，對於固定節點，原始GNN迭代更新節點的隱藏狀態是低效的。如果放寬了固定點的假設，我們可以設計一個多層的GNN來得到節點及其鄰域的穩定表示。

其次，GNN在迭代中使用相同的參數，而大多數流行的神經網路在不同的層中使用不同的參數，這是一種分層特徵提取方法。此外，節點隱藏狀態的更新是一個順序過程，可以從RNN內核(如GRU 和 LSTM)中獲益。

第三，在邊上也有一些無法在原始GNN中建模的信息特徵。此外，如何學習邊的隱藏狀態也是一個重要的問題。

最後，如果我們把焦點放在節點的表示上而不是圖形上，就不適合使用固定點，因為在固定點上的表示的分布在數值上是平滑的，區分每個節點的信息量也比較少。

圖神經網路的變體

在這一節，我們提出圖神經網路的幾種變體。首先是在不同圖類型上運行的變體，這些變體擴展了原始模型的表示能力。其次，我們列出了在傳播步驟進行修改（卷積、門機制、注意力機制和skip connection）的幾種變體，這些模型可以更好地學習表示。最後，我們描述了使用高級訓練方法的標題，這些方法提高了訓練效率。

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

一覽GNN的不同變體

圖的類型(Graph Types)

在原始GNN中，輸入的圖由帶有標籤信息的節點和無向的邊組成，這是最簡單的圖形格式。然而，世界上有許多不同的圖形。這裡，我們將介紹一些用於建模不同類型圖形的方法。

圖類型的變體

有向圖(Directed Graphs )

圖形的第一個變體是有向圖。無向邊可以看作是兩個有向邊，表明兩個節點之間存在著關係。然而，有向邊比無向邊能帶來更多的信息。例如，在一個知識圖中，邊從head實體開始到tail實體結束，head實體是tail實體的父類，這表明我們應該區別對待父類和子類的信息傳播過程。有向圖的實例有ADGPM (M. Kampffmeyer et. al. 2018)。

異構圖(Heterogeneous Graphs)

圖的第二個變體是異構圖，異構圖有幾種類型的節點。處理異構圖最簡單的方法是將每個節點的類型轉換為與原始特徵連接的一個one-hot特徵向量。異構圖如GraphInception。

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

圖的另外一個變體是，每條邊都有信息，比如權值或邊的類型。例如G2S和R-GCN。

使用不同訓練方法的圖變體

訓練方法變體

在傳播步驟進行修改的GNN變體

傳播步驟變體

GNN的三大通用框架

除了圖神經網路的不同變體之外，我們還介紹了幾個通用框架，旨在將不同的模型集成到一個框架中。

J. Gilmer等人(J. Gilmer et. al. 2017)提出了消息傳遞神經網路(message passing neural network， MPNN)，統一了各種圖神經網路和圖卷積網路方法。

X. Wang等人(X. Wang et. al. 2017)提出了非局部神經網路(non-local neural network, NLNN)，它結合了幾種「self-attention」風格的方法。

P. W. Battaglia等人(P. W. Battaglia et. al. 2018)提出了圖網路(graph network, GN)，它統一了統一了MPNN和NLNN方法以及許多其他變體，如交互網路(Interaction Networks)，神經物理引擎(Neural Physics Engine)，CommNet，structure2vec，GGNN，關係網路(Relation Network)，Deep Sets和Point Net。

幾個尚未解決的問題

儘管GNN在不同領域取得了巨大成功，但值得注意的是，GNN模型還不能在任何條件下，為任何圖任務提供令人滿意的解決方案。這裡，我們將陳述一些開放性問題以供進一步研究。

淺層結構

傳統的深度神經網路可以堆疊數百層，以獲得更好的性能，因為更深的結構具備更多的參數，可以顯著提高網路的表達能力。然而，GNN總是很淺，大多數不超過三層。

實驗顯示，堆疊多個GCN層將導致過度平滑，也就是說，所有頂點將收斂到相同的值。儘管一些研究人員設法解決了這個問題，但這仍然是GNN的最大局限所在。設計真正的深度GNN對於未來的研究來說是一個令人興奮的挑戰，並將對進一步深入理解GNN做出相當大的貢獻。

動態圖形另一個具有挑戰性的問題是如何處理具有動態結構的圖形。靜態圖總是穩定的，因此對其進行建模是可行的，而動態圖引入了變化的結構。當邊和節點出現或消失時，GNN不能自適應地做出改變。目前對動態GNN的研究也在積極進行中，我們認為它是一般GNN的具備穩定性和自適應性的重要里程碑。

非結構性場景

我們討論了GNN在非結構場景中的應用，但我們沒有找到從原始數據中生成圖的最佳方法。在圖像域中，一些研究可以利用CNN獲取特徵圖，然後對其進行上採樣，形成超像素作為節點，還有的直接利用一些對象檢測演算法來獲取對象節點。在文本域中，有些研究使用句法樹作為句法圖，還有的研究採用全連接圖。因此，關鍵是找到圖生成的最佳方法，使GNN在更廣泛的領域發揮更大的作用。

可擴展性問題

如何將嵌入式演算法應用於社交網路或推薦系統這類大規模網路環境，是幾乎所有圖形嵌入演算法面對的一個致命問題，GNN也不例外。對GNN進行擴展是很困難的，因為涉及其中的許多核心流程在大數據環境中都要消耗算力。

這種困難體現在幾個方面：首先，圖數據並不規則，每個節點都有自己的鄰域結構，因此不能批量化處理。其次，當存在的節點和邊數量達到數百萬時，計算圖的拉普拉斯運算元也是不可行的。此外，我們需要指出，可擴展性的高低，決定了演算法是否能夠應用於實際場景。目前已經有一些研究提出了解決這個問題的辦法，我們正在密切關注這些新進展。

結論

在過去幾年中，GNN已經成為圖領域機器學習任務的強大而實用的工具。這一進展有賴於表現力，模型靈活性和訓練演算法的進步。在本文中，我們對圖神經網路進行了全面綜述。對於GNN模型，我們引入了按圖類型、傳播類型和訓練類型分類的GNN變體。

此外，我們還總結了幾個統一表示不同GNN變體的通用框架。在應用程序分類方面，我們將GNN應用程序分為結構場景、非結構場景和其他18個場景，然後對每個場景中的應用程序進行詳細介紹。最後，我們提出了四個開放性問題，指出了圖神經網路的主要挑戰和未來的研究方向，包括模型深度、可擴展性、動態圖處理和對非結構場景的處理能力。

【加入社群】

新智元 AI 技術 + 產業社群招募中，歡迎對 AI 技術 + 產業落地感興趣的同學，加小助手微信號：aiera2015_2入群；通過審核後我們將邀請進群，加入社群後務必修改群備註（姓名 - 公司 - 職位；專業群審核較嚴，敬請諒解）。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！