清華大學圖神經網路綜述:模型與應用
機器之心專欄
作者:PaperWeekly
近年來,圖神經網路的研究成為深度學習領域的熱點,機器之心曾介紹過清華大學朱文武等人綜述的圖網路。近日,清華大學孫茂松組在 arXiv 上發布預印版綜述文章 Graph Neural Networks: A Review of Methods and Applications。
該文總結了近年來圖神經網路領域的經典模型與典型應用,並提出了四個開放性問題。對於希望快速了解這一領域的讀者,不妨先從這篇文章看起。
除了這篇綜述外,文章作者在 Github 中更新了該領域的參考文章列表(https://github.com/thunlp/GNNPapers),供各位讀者參考查看。
引言
圖是一種數據結構,它對一組對象(節點)及其關係(邊)進行建模。近年來,由於圖結構的強大表現力,用機器學習方法分析圖的研究越來越受到重視。圖神經網路(GNN)是一類基於深度學習的處理圖域信息的方法。由於其較好的性能和可解釋性,GNN 最近已成為一種廣泛應用的圖分析方法。
GNN 的第一個動機源於卷積神經網路(CNN)。CNN 的廣泛應用帶來了機器學習領域的突破並開啟了深度學習的新時代。然而 CNN 只能在規則的 Euclidean 數據上運行,如圖像(2 維網格)和文本(1 維序列)。如何將 CNN 應用於圖結構這一非歐幾里德空間,成為 GNN 模型重點解決的問題。
圖1. 左:圖像(歐幾里得空間) 右:圖(非歐幾里德空間)
GNN 的另一個動機來自圖嵌入(Graph Embedding),它學習圖中節點、邊或子圖的低維向量空間表示。DeepWalk、LINE、SDNE 等方法在網路表示學習領域取得了很大的成功。然而,這些方法在計算上較為複雜並且在大規模上的圖上並不是最優的,GNN 旨在解決這些問題。
這篇文章對圖神經網路進行了廣泛的總結,並做出了以下貢獻:
文章詳細介紹了圖神經網路的經典模型。主要包括其原始模型,不同的變體和幾個通用框架。
文章將圖神經網路的應用系統地歸類為結構化場景、非結構化場景和其他場景中,並介紹了不同場景中的主要應用。
本文為未來的研究提出四個未解決的問題。文章對每個問題進行了詳細分析,並提出未來的研究方向。
模型
在模型這一部分中,文章首先介紹了最經典的圖神經網路模型 GNN,具體闡述了 GNN 的模型與計算方式,然而 GNN 模型仍然存在一定的限制,比如較高的計算複雜度以及表示能力不足等等。
後續的很多工作致力於解決 GNN 存在的種種問題,在 2.2 一節中文章詳細介紹了 GNN 的不同變體。具體來說,文章分別介紹了適應於不同圖類型、採用不同的信息傳遞方式以及採用了不同的訓練方法的變體。
圖2. 不同的GNN變體
在 2.2.1 節中,文章介紹了處理不同圖類型的 GNN 變體,包括有向圖、異質圖和具有邊信息的圖。在 2.2.2 節中,文章對於採用不同信息傳遞方式的變體進行了總結與概括。主要分為以下四個類別:
卷積。Graph Convolutional Network(GCN)希望將卷積操作應用在圖結構數據上,主要分為Spectral Method和Spatial Method(Non-spectral Method)兩類。Spectral Method希望使用譜分解的方法,應用圖的拉普拉斯矩陣分解進行節點的信息收集。Spatial Method直接使用圖的拓撲結構,根據圖的鄰居信息進行信息收集。
注意力機制。Graph Attention Network 致力於將注意力機制應用在圖中的信息收集階段。
門機制。這些變體將門機制應用於節點更新階段。Gated graph neural network 將 GRU 機制應用於節點更新。很多工作致力於將 LSTM 應用於不同類型的圖上,根據具體情境的不同,可以分為 Tree LSTM、Graph LSTM 和 Sentence LSTM 等。
殘差連接。注意到堆疊多層圖神經網路可能引起信息平滑的問題,很多工作將殘差機制應用於圖神經網路中,文中介紹了 Highway GNN 和 Jump Knowledge Network 兩種不同的處理方式。
文章還對於不同的信息傳遞方式進行了公式化總結。簡單來說,信息傳遞函數主要包括信息收集(agggregation)和節點信息更新(update)兩個部分,在表格中列出了每種方法的不同配置。
表1. 採用不同消息傳遞函數的GNN變體總結
在 2.2.3 節中,文章介紹了 GNN 的不同訓練方法。譬如 GraphSAGE 從附近的鄰居收集信息,並且能夠應用於 inductive learning 領域;FastGCN 使用了 importance sampling 的方法,使用採樣替代使用節點所有的鄰居信息,加快了訓練過程。
在 2.3 節中,文章介紹了近年來文獻中提出的圖神經網路通用框架 MPNN(Message Passing Neural Network)、NLNN(Non-local Neural Network)以及 Deepmind 的 GN(Graph Network)。
MPNN 將模型總結為信息傳遞階段和節點更新階段,概括了多種圖神經網路和圖卷積神經網路方法。NLNN 總結了很多種基於自注意力機制的方法。GN 提出了更加通用的模型,能夠總結概括幾乎所有文中提到的框架,並且擁有更加靈活的表示能力、易於配置的塊內結構以及易於組合的多模塊架構。
圖3. GN Block組合成複雜網路結構
應用
GNN 被應用在眾多的領域,文章具體將應用分為了結構化場景、非結構化場景以及其他三個類別。
在結構化場景中,GNN 被廣泛應用在社交網路、推薦系統、物理系統、化學分子預測、知識圖譜等領域。文章中主要介紹了其在物理、化學、生物和知識圖譜中的部分應用。在非結構領域,文章主要介紹了在圖像和文本中的應用。在其他領域,文章介紹了圖生成模型以及使用 GNN 來解決組合優化問題的場景。
圖4. GNN的應用示例
表2. 文章介紹的應用總結
開放問題
文章最後提出了圖神經網路領域的四個開放問題:
1. 淺層結構。經驗上使用更多參數的神經網路能夠得到更好的實驗效果,然而堆疊多層的 GNN 卻會產生 over-smoothing 的問題。具體來說,堆疊層數越多,節點考慮的鄰居個數也會越多,導致最終所有節點的表示會趨向於一致。
2. 動態圖。目前大部分方法關注於在靜態圖上的處理,對於如何處理節點信息和邊信息隨著時間步動態變化的圖仍是一個開放問題。
3. 非結構化場景。雖然很多工作應用於非結構化的場景(比如文本),然而並沒有通用的方法用於處理非結構化的數據。
4. 擴展性。雖然已經有一些方法嘗試解決這個問題,將圖神經網路的方法應用於大規模數據上仍然是一個開放性問題。
本文為機器之心專欄,轉載請聯繫本公眾號獲得授權。
------------------------------------------------
![](https://pic.pimg.tw/zzuyanan/1488615166-1259157397.png)
![](https://pic.pimg.tw/zzuyanan/1482887990-2595557020.jpg)
※NeurIPS 2018最佳論文出爐:UT陳天琦、華為上榜
※每3位新碼農中就有2個是單身?來自31000人的調查報告顯示……
TAG:機器之心 |