圖神經網路綜述：方法及應用

整理 | 耿玉霞，浙江大學直博生。研究方向：知識圖譜，零樣本學習，自然語言處理等。

責編 | Jane

近日，清華劉知遠老師組在 arXiv 上發表了一篇關於圖神經網路的綜述，本次論文淺嘗在分享這篇論文的基礎上，對圖神經網路的相關方法及應用作一次梳理。

一、前言

圖神經網路(GraphNeural Networks, GNNs)，主要針對非歐幾里得空間結構（圖結構）的數據進行處理。具有以下特點：

忽略節點的輸入順序；

在計算過程中，節點的表示受其周圍鄰居節點的影響，而圖本身連接不變；

圖結構的表示，使得可以進行基於圖的推理。

二、圖神經網路模型

通常，圖神經網路由兩個模塊組成：傳播模塊(PropagationModule)和輸出模塊(Output Module)，具體地：

（1）Propagation Module：圖中節點之間傳遞信息並更新狀態；

aggregator: 對於一個節點v, 通過聚合其周圍節點的信息，學習其潛在表示h_v (state embedding)。

其中，x_v為節點v的features，x_co[v]為其周圍邊的features，h_ne[v]表示節點v周圍鄰居節點的state embedding，x_ne[v]表示周圍節點的features。

updater: 更新節點的stateembedding。

（2）Output Module：基於節點和邊的向量表示根據不同的任務定義目標函數

在監督學習場景中，對於一個特定的節點，其監督信號表示為：t_v，lossfunction定義為：

常見的圖神經網路有：圖卷積神經網路(GraphConvolutional Networks, GCNs)，門控圖神經網路(Gated Graph Neural Networks,GGNNs)以及基於Attention機制的GraphAttention Networks(GAT)，下面詳細介紹這三種網路：

1、圖卷積神經網路（GCN）

（1）基於譜方法(Spectral Methods):

相關論文： Kipf T N, Welling M.Semi-supervised classification with graph convolutional networks.

通過計算圖拉普拉斯運算元(Graph Laplacian)的特徵分解，在Fourier域定義卷積計算。對於輸入信號x和卷積核_=():

其中，表示圖結構的Graph Laplacian矩陣可分解為：

上式的計算將卷積核近似為切比雪夫多項式，並進行化簡：

最終得到GCN網路中的表示：

aggregator:

updater:

但是以上方法有幾點不足，卷積核的學習依賴圖拉普拉斯矩陣的特徵分解，對於圖結構有一定的要求，在固定結構上學習的模型，無法遷移到其他結構的模型上。

（2）基於非譜方法(Non-spectral Methods):

在圖上直接定義卷積計算，將不同size的鄰居節點考慮在內，同時保持像CNN一樣的局部卷積不變性。

DCNNs：基於擴散卷積的思想的網路；

GraphSAGE：採樣固定size的鄰居節點，同時通過mean,LSTM, pooling等方式聚合周圍節點的信息。

2、門控圖神經網路（GGNN）

相關論文： Li Y, Tarlow D, Brockschmidt M,et al. Gated graph sequence neural networks.

提高圖結構信息的long-term傳播能力

將圖中的edge信息考慮在內

將圖矩陣作如下表示，不同類型的邊採用不同類型的傳播矩陣，同時，用 A^(out)和 A^(in) 分別表示節點的入度信息和出度信息。

計算圖傳播信息：

（1）Propagation module

initialization step

pass information：矩陣A中包含了當前節點與其他節點的交互信息

節點的state embedding h_，與其他節點的交互信息a_通過GRU單元進行融合：

update gate

reset gate

activate

（2）Output module

node-level

graph-level

其中，i,j表示兩個全連接神經網路。

3、注意力圖神經網路（GAT）

相關論文： Velickovic, Petar, et al. Graphattention networks.

為節點的不同的鄰居節點指定不同權重

節點-鄰居節點對的計算可並行化，相比於GCN等網路，速度較快

節點權重的計算：

節點信息的更新：

由「Attentionis all you need」一文中提出的 head attention，GAT 網路中也使用了 headattention：

三、圖神經網路應用

1、Structural Scenarios

主要應用於其數據結構為圖結構的場景，如蛋白質分子結構圖、KnowledgeGraph 等。以 KnowledgeGraph 中應用 GNN 為例：

相關論文： Hamaguchi T, et al. Knowledgetransfer for out-of-knowledge-base entities: a graph neural network approach.

論文主要針對 KG 中的 out-of-knowledge-base(OOKB) 實體，進行知識庫補全等任務。

a、OOKB實體定義：

在訓練過程中未被訓練到的實體，無法得到其 embedding 表示，從而無法預測其與知識庫中其他實體之間的關係。如下圖中在測試期間新出現的實體「Blade-Runner」，或者說新出現的三元組「(Blade-Runner,based-on, Do-Androids-Dream-of-Electric-Sheep?)」（圖中紅線所示部分）。

我們的任務則定義為：基於知識庫中已存在的三元組（2）和當前新出現的三元組（1），預測當前新實體與知識庫中其他實體之間的關係（即三元組3）。

同時，OOKB 實體即哪些與知識庫中已存在的實體直接相連的實體，基於此，可以通過知識庫中現有的實體表示得到 OOKB 實體表示。

b、這篇文章利用 GNN 中節點表示的方式，對 OOKB 實體進行表示：

其中，T_head 表示以 OOKB 實體為尾實體的三元組集合，T_tail 表示以 OOKB 實體為頭實體的三元組集合，通過其周圍鄰居的頭尾實體對當前實體進行表示。

T_head, T_tail 分別表示聚合三元組信息的函數，論文中為 batchnormalization function。

經 GNN 傳播的節點狀態表示為：

c、模型的輸出模塊利用 TransE 等經典模型，進行知識庫補全任務。

2、Non-structural Scenarios

主要應用於其數據結構為非圖結構的場景，如圖片、文本等。在此類場景中，應用GNN通常有兩種方式：

利用具有圖結構信息的外部資源，如 KnowledgeGraph 等；

探索此類數據中隱含的圖結構，如文本的句法數結構。

（1）圖片相關任務：

Image Classification, i.e., zero-shot, few-shot

Visual Reasoning, i.e., VQA

Semantic Segmentation

其中，圖片分類任務零樣本學習和少樣本學習的相關論文有：

Zero-shot recognition via semantic embeddings and knowledge graphs

Rethinking knowledge graph propagation for zero-shot learning

Multi-label zero-shot learning with structured knowledge graphs

The more you know: Using knowledge graphs forimage classification

Few-shot learning with graph neural networks

（2）NLP相關任務：

Text Classification

Sequence Labeling

Neural machine translation

Relation Extraction

Event Extraction

以機器翻譯的一篇論文為例，通過將 sourcelanguage 的句法結構圖輸 GNN 進行 encode，繼而附加 Attention layer 和 decoder 層，輸出 target language 序列。

相關論文： Beck D, Haffari G, Cohn T.Graph-to-sequence learning using gated graph neural networks.

這篇文章以「Graph tosequence」為要點，實驗部分包括兩個任務，其中一個是 AMR 圖輸出序列，另一個做 syntax-aware 的機器翻譯任務。

其中，AMR Graph 為從句子的句法表示中抽象出來的語義表示語言，具體相似語義的句子有相同的 AMR Graph。如下圖左所示。

模型在 Seq2seq 模型的基礎上，以 AMR graph 為輸入，通過 GGNN 網路進行 encode，經過 Attention 層和 RNNdecoder 輸出序列。GGNN encoder 部分表示為：

其中，表示當前節點與周圍節點相連邊的參數，l_e 表示不同邊的類型。

但隨著 Graph 中邊類型的增多，很容易引起參數爆炸的問題，因此，本文提出了一種融合 Graph 中 edge 信息的方式，即將 edge 轉化為附加的節點(no labelled edges)。具體地，通過將 Graph 轉化為對應的二分圖。上圖中的句法結構圖對應的二分圖如下所示：

由此，graph 中的邊的類型只有一種。

四、Open problems

圖神經網路目前雖被廣泛利用，但存在不少問題亟待解決：

（1）Shallowstructure：多層的圖神經網路，可能會導致 over-smoothing的問題，如 GCN 等網路，一些論文中也嘗試用 Skip connection 的方式加以解決；

（2）Dynamicgraphs：GNN 目前僅能處理一些靜態圖，對於實時增加/減少的節點和邊則無法很好地處理；

（3）Non-structuralscenarios：在處理非圖結構的數據時，希望利用其中內在的結構，而目前從 raw data 中生成 graph 的方法仍需改善；

（4）Scalability

五、總結

本文中總結了近年來常用的幾種圖神經網路模型，並就其應用場景進行了進一步的探討。總的來說，圖神經網路強大的計算能力，對圖結構數據的友好處理，深受研究者們的喜愛，但其仍存在很多需要解決的問題，也是我們可以進一步研究的方向。

最後，送上這份值得大家收藏的論文地址

論文鏈接：

https://arxiv.org/pdf/1812.08434.pdf

GNN相關論文列錶鏈接：

https://github.com/thunlp/GNNPapers

（本文為AI科技大本營轉載文章，轉載請聯繫作者，禁止二次轉載）

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