圖神經網路：從gnn網路的綜述看當前流行的gnn網路的幾種模型形式

左乘矩陣幾何意義

近年來，深度學習領域關於圖神經網路（Graph Neural Networks，GNN）的研究熱情日益高漲，圖神經網路已經成為各大深度學習頂會的研究熱點。GNN處理非結構化資料時的出色能力使其在網路資料分析、推薦系統、物理建模、自然語言處理和圖上的組合最佳化問題方面都取得了新的突破。

圖神經網路有很多比較好的綜述［1］［2］［3］可以參考，更多的論文可以參考清華大學整理的GNN paper list［4］ 。

本篇文章將從一個更直觀的角度對當前經典流行的GNN網路，包括

GCN、GraphSAGE、GAT、GAE

以及graph pooling策略

DiffPool

等等做一個簡單的小結。

筆者注：行文如有錯誤或者表述不當之處，還望批評指正！

一、為什麼需要圖神經網路？

隨著機器學習、深度學習的發展，語音、影象、自然語言處理逐漸取得了很大的突破，然而語音、影象、文字都是很簡單的序列或者網格資料，是很結構化的資料，深度學習很善於處理該種類型的資料（圖1）。

圖1

然而現實世界中並不是所有的事物都可以表示成一個序列或者一個網格，例如社交網路、知識圖譜、複雜的檔案系統等（圖2），也就是說很多事物都是非結構化的。

圖2

相比於簡單的文字和影象，這種網路型別的非結構化的資料非常複雜，處理它的難點包括：

圖的大小是任意的，圖的拓撲結構複雜，沒有像影象一樣的空間區域性性

圖沒有固定的節點順序，或者說沒有一個參考節點

圖經常是動態圖，而且包含多模態的特徵

那麼對於這類資料我們該如何建模呢？能否將深度學習進行擴充套件使得能夠建模該類資料呢？這些問題促使了圖神經網路的出現與發展。

二. 圖神經網路是什麼樣子的？

相比較於神經網路最基本的網路結構全連線層（MLP），特徵矩陣乘以權重矩陣，圖神經網路多了一個鄰接矩陣。計算形式很簡單，三個矩陣相乘再加上一個非線性變換（圖3）。

圖3

因此一個比較常見的圖神經網路的應用模式如下圖（圖4），輸入是一個圖，經過多層圖卷積等各種操作以及啟用函式，最終得到各個節點的表示，以便於進行節點分類、連結預測、圖與子圖的生成等等任務。

圖4

上面是一個對圖神經網路比較簡單直觀的感受與理解，實際其背後的原理邏輯還是比較複雜的，這個後面再慢慢細說，接下來將以幾個經典的GNN models為線來介紹圖神經網路的發展歷程

深度學習與圖網路

關注圖網路、圖表示學習，最近頂會頂刊動態以及機器學習基本方法，包括無監督學習、半監督學習、弱監督學習、元學習等209篇原創內容

公眾號

三、圖神經網路的幾個經典模型與發展

1 . Graph Convolution Networks(GCN)[5]

GCN可謂是圖神經網路的“開山之作”，它首次將影象處理中的卷積操作簡單的用到圖結構資料處理中來，並且給出了具體的推導，這裡面涉及到複雜的譜圖理論，具體推到可以參考［6］［7］。推導過程還是比較複雜的，然而最後的結果卻非常簡單（ 圖5）。

圖5

我們來看一下這個式子，天吶，這不就是聚合鄰居節點的特徵然後做一個線性變換嗎？沒錯，確實是這樣，同時為了使得GCN能夠捕捉到K-hop的鄰居節點的資訊，作者還堆疊多層GCN layers，如堆疊K層有：

上述式子還可以使用矩陣形式表示如下，

其中 是歸一化之後的鄰接矩陣， 相當於給 層的所有節點的embedding做了一次線性變換，左乘以鄰接矩陣表示對每個節點來說，該節點的特徵表示為鄰居節點特徵相加之後的結果。（注意將 換成矩陣 就是圖3所說的三矩陣相乘）

那麼GCN的效果如何呢？作者將GCN放到節點分類任務上，分別在Citeseer、Cora、Pubmed、NELL等資料集上進行實驗，相比於傳統方法提升還是很顯著的，這很有可能是得益於GCN善於編碼圖的結構資訊，能夠學習到更好的節點表示。

圖6

當然，其實GCN的缺點也是很顯然易見的，

第一，GCN需要將整個圖放到記憶體和視訊記憶體，這將非常耗記憶體和視訊記憶體，處理不了大圖；第二，GCN在訓練時需要知道整個圖的結構資訊

（包括待預測的節點）， 這在現實某些任務中也不能實現（比如用今天訓練的圖模型預測明天的資料，那麼明天的節點是拿不到的）。

2. Graph Sample and Aggregate(GraphSAGE)[8]

為了解決GCN的兩個缺點問題，GraphSAGE被提了出來。在介紹GraphSAGE之前，先介紹一下Inductive learning和Transductive learning。注意到圖資料和其他型別資料的不同，圖資料中的每一個節點可以透過邊的關係利用其他節點的資訊。這就導致一個問題，GCN輸入了整個圖，訓練節點收集鄰居節點資訊的時候，用到了測試和驗證集的樣本，我們把這個稱為Transductive learning。然而，我們所處理的大多數的機器學習問題都是Inductive learning，因為我們刻意的將樣本集分為訓練/驗證/測試，並且訓練的時候只用訓練樣本。這樣對圖來說有個好處，可以處理圖中新來的節點，可以利用已知節點的資訊為未知節點生成embedding，GraphSAGE就是這麼幹的。

GraphSAGE是一個Inductive Learning框架，具體實現中，訓練時它僅僅保留訓練樣本到訓練樣本的邊，然後包含Sample和Aggregate兩大步驟，Sample是指如何對鄰居的個數進行取樣，Aggregate是指拿到鄰居節點的embedding之後如何匯聚這些embedding以更新自己的embedding資訊。下圖展示了GraphSAGE學習的一個過程，

圖7

第一步，對鄰居取樣

第二步，取樣後的鄰居embedding傳到節點上來，並使用一個聚合函式聚合這些鄰居資訊以更新節點的embedding

第三步，根據更新後的embedding預測節點的標籤

接下來，我們詳細的說明一個訓練好的GrpahSAGE是如何給一個新的節點生成embedding的（即一個前向傳播的過程），如下演算法圖：

首先，（line1）演算法首先初始化輸入的圖中所有節點的特徵向量，（line3）對於每個節點 ，拿到它取樣後的鄰居節點 後，（line4）利用聚合函式聚合鄰居節點的資訊，（line5）並結合自身embedding透過一個非線性變換更新自身的embedding表示。

注意到演算法裡面的 ，它是指聚合器的數量，也是指權重矩陣的數量，還是網路的層數，這是因為

每一層網路中聚合器和權重矩陣是共享的

。網路的層數可以理解為需要最大訪問的鄰居的跳數（hops），比如在圖7中，紅色節點的更新拿到了它一、二跳鄰居的資訊，那麼網路層數就是2。為了更新紅色節點，首先在第一層（k=1），我們會將藍色節點的資訊聚合到紅色解節點上，將綠色節點的資訊聚合到藍色節點上。在第二層（k=2）紅色節點的embedding被再次更新，不過這次用到的是更新後的藍色節點embedding，這樣就保證了紅色節點更新後的embedding包括藍色和綠色節點的資訊，也就是兩跳資訊。

為了看的更清晰，我們將更新某個節點的過程展開來看，如圖8分別為更新節點A和更新節點B的過程，可以看到更新不同的節點過程每一層網路中聚合器和權重矩陣都是共享的。

圖8

那麼GraphSAGE

Sample

是怎麼做的呢？GraphSAGE是採用定長抽樣的方法，具體來說，定義需要的鄰居個數 ，然後採用有放回的重取樣/負取樣方法達到 。保證每個節點（取樣後的）鄰居個數一致，這樣是為了把多個節點以及它們的鄰居拼接成Tensor送到GPU中進行批訓練。

那麼GraphSAGE 有哪些

聚合器

呢？主要有三個，

這裡說明的一點是Mean Aggregator和GCN的做法基本是一致的（GCN實際上是求和）。

到此為止，整個模型的架構就講完了，那麼GraphSAGE是如何學習聚合器的引數以及權重矩陣 呢？如果是

有監督

的情況下，可以使用每個節點的預測lable和真實lable的交叉熵作為損失函式。如果是在

無監督

的情況下，可以假設相鄰的節點的embedding表示儘可能相近，因此可以設計出如下的損失函式，

那麼GrpahSAGE的實際實驗效果如何呢？作者在Citation、Reddit、PPI資料集上分別給出了無監督和完全有監督的結果，相比於傳統方法提升還是很明顯。

至此，GraphSAGE介紹完畢。我們來總結一下，GraphSAGE的一些優點，

（1）利用取樣機制，很好的解決了GCN必須要知道全部圖的資訊問題，克服了GCN訓練時記憶體和視訊記憶體的限制，即使對於未知的新節點，也能得到其表示

（2）聚合器和權重矩陣的引數對於所有的節點是共享的

（3）模型的引數的數量與圖的節點個數無關，這使得GraphSAGE能夠處理更大的圖

（4）既能處理有監督任務也能處理無監督任務

（就喜歡這樣解決了問題，方法又簡潔，效果還好的idea！！！）

當然，GraphSAGE也有一些缺點，每個節點那麼多鄰居，GraphSAGE的取樣沒有考慮到不同鄰居節點的重要性不同，而且聚合計算的時候鄰居節點的重要性和當前節點也是不同的。

3. Graph Attention Networks(GAT)

［9］

為了解決GNN聚合鄰居節點的時候沒有考慮到不同的鄰居節點重要性不同的問題，GAT借鑑了Transformer的idea，引入masked self-attention機制，在計算圖中的每個節點的表示的時候，會根據鄰居節點特徵的不同來為其分配不同的權值。

具體的，對於輸入的圖，一個graph attention layer如圖9所示，

圖9

其中 採用了單層的前饋神經網路實現，計算過程如下（注意權重矩陣 對於所有的節點是共享的）：

計算完attention之後，就可以得到某個節點聚合其鄰居節點資訊的新的表示，計算過程如下：

為了提高模型的擬合能力，還引入了多頭的self-attention機制，即同時使用多個 計算self-attention，然後將計算的結果合併（連線或者求和）：

此外，由於GAT結構的特性，GAT無需使用預先構建好的圖，因此GAT既適用於Transductive Learning，又適用於Inductive Learning。

那麼GAT的具體效果如何呢？作者分別在三個Transductive Learning和一個Inductive Learning任務上進行實驗，實驗結果如下：

無論是在Transductive Learning還是在Inductive Learning的任務上，GAT的效果都要優於傳統方法的結果。

至此，GAT的介紹完畢，我們來總結一下，GAT的一些優點，

（1）訓練GCN無需瞭解整個圖結構，只需知道每個節點的鄰居節點即可

（2）計算速度快，可以在不同的節點上進行平行計算

（3）既可以用於Transductive Learning，又可以用於Inductive Learning，可以對未見過的圖結構進行處理

（仍然是簡單的idea，解決了問題，效果還好！！！）

到此，我們就介紹完了GNN中最經典的幾個模型GCN、GraphSAGE、GAT，接下來我們將針對具體的任務類別來介紹一些流行的GNN模型與方法。

四、無監督的節點表示學習（Unsupervised Node Representation）

由於標註資料的成本非常高，如果能夠利用無監督的方法很好的學習到節點的表示，將會有巨大的價值和意義，例如找到相同興趣的社群、發現大規模的圖中有趣的結構等等。

圖10

這其中比較經典的模型有

GraphSAGE、Graph Auto-Encoder（GAE）等，GraphSAGE

就是一種很好的無監督表示學習的方法，前面已經介紹了，這裡就不贅述，接下來將詳細講解後面兩個。

深度學習與圖網路

關注圖網路、圖表示學習，最近頂會頂刊動態以及機器學習基本方法，包括無監督學習、半監督學習、弱監督學習、元學習等209篇原創內容

公眾號

Graph Auto-Encoder(GAE)

［10］

在介紹Graph Auto-Encoder之前，需要先了解

自編碼器(Auto-Encoder)、變分自編碼器(Variational Auto-Encoder)，

具體可以參考［11］，這裡就不贅述。

理解了自編碼器之後，再來理解

變分圖的自編碼器

就容易多了。如圖11輸入圖的鄰接矩陣和節點的特徵矩陣，透過編碼器（圖卷積網路）學習節點低維向量表示的均值μ和方差σ，然後用解碼器（鏈路預測）生成圖。

圖11

編碼器（Encoder）採用簡單的兩層GCN網路，解碼器（Encoder）計算兩點之間存在邊的機率來重構圖，損失函式包括生成圖和原始圖之間的距離度量，以及節點表示向量分佈和正態分佈的KL-散度兩部分。具體公式如圖12所示：

圖12

另外為了做比較，作者還提出了

圖自編碼器(Graph Auto-Encoder)

，相比於變分圖的自編碼器，圖自編碼器就簡單多了，Encoder是兩層GCN，Loss只包含Reconstruction Loss。

那麼兩種圖自編碼器的效果如何呢？作者分別在Cora、Citeseer、Pubmed資料集上做Link prediction任務，實驗結果如下表，圖自編碼器（GAE）和變分圖自編碼器（VGAE）效果普遍優於傳統方法，而且變分圖自編碼器的效果更好；當然，Pumed上GAE得到了最佳結果。可能是因為Pumed網路較大，在VGAE比GAE模型複雜，所以更難調參。

五、Graph Pooling

Graph pooling

是GNN中很流行的一種操作，目的是為了獲取一整個圖的表示，主要用於處理圖級別的分類任務，例如在有監督的圖分類、文件分類等等。

圖13

Graph pooling

的方法有很多，如簡單的max pooling和mean pooling，然而這兩種pooling不高效而且忽視了節點的順序資訊；這裡介紹一種方法：

Differentiable Pooling (DiffPool)。

1.DiffPool

［12］

在圖級別的任務當中，當前的很多方法是將所有的節點嵌入進行全域性池化，忽略了圖中可能存在的任何層級結構，這對於圖的分類任務來說尤其成問題，因為其目標是預測整個圖的標籤。針對這個問題，斯坦福大學團隊提出了一個用於圖分類的可微池化操作模組——

DiffPool

，可以生成圖的層級表示，並且可以以端到端的方式被各種圖神經網路整合。

DiffPool

的核心思想是透過一個

可微池化操作模組

去分層的聚合圖節點，具體的，這個

可微池化操作模組

基於GNN上一層生成的節點嵌入 以及分配矩陣 ，以端到端的方式分配給下一層的簇，然後將這些簇輸入到GNN下一層，進而實現用分層的方式堆疊多個GNN層的想法。（圖14）

圖14

那麼這個節點嵌入和分配矩陣是怎麼算的？計算完之後又是怎麼分配給下一層的？這裡就涉及到兩部分內容，一個是

分配矩陣的學習

，一個是

池化分配矩陣

。

分配矩陣的學習

這裡使用兩個分開的GNN來生成分配矩陣 和每一個簇節點新的嵌入 ，這兩個GNN都是用簇節點特徵矩陣 和粗化鄰接矩陣 作為輸入，

池化分配矩陣

計算得到分配矩陣 和每一個簇節點新的嵌入 之後，DiffPool層根據分配矩陣，對於圖中的每個節點/簇生成一個新的粗化的鄰接矩陣 與新的嵌入矩陣 ，

總的來看，每層的

DiffPool

其實就是更新每一個簇節點的嵌入和簇節點的特徵矩陣，如下公式：

至此，

DiffPool

的基本思想就講完了。那麼效果如何呢？作者在多種圖分類的基準資料集上進行實驗，如蛋白質資料集（ENZYMES，PROTEINS，D&D），社交網路資料集（REDDIT-MULTI-12K），科研合作資料集（COLLAB），實驗結果如下：

其中，

GraphSAGE

是採用全域性平均池化；

DiffPool-DET

是一種

DiffPool

變體，使用確定性圖聚類演算法生成分配矩陣；

DiffPool-NOLP

是

DiffPool

的變體，取消了連結預測目標部分。總的來說，DiffPool方法在GNN的所有池化方法中獲得最高的平均效能。

為了更好的證明DiffPool對於圖分類十分有效，論文還使用了其他GNN體系結構（Structure2Vec（s2v）），並且構造兩個變體，進行對比實驗，如下表：

可以看到DiffPool的顯著改善了S2V在ENZYMES和D&D資料集上的效能。

而且

DiffPool

可以自動的學習到恰當的簇的數量。

至此，我們來總結一下

DiffPool

的優點，

（1）可以學習層次化的pooling策略

（2）可以學習到圖的層次化表示

（3）可以以端到端的方式被各種圖神經網路整合

然而，注意到，

DiffPool

也有其侷限性，分配矩陣需要很大的空間去儲存，空間複雜度為 ， 為池化層的層數，所以無法處理很大的圖。

參考

【1】^Graph Neural Networks： A Review of Methods and Applications。 arxiv 2018 https：//arxiv。org/pdf/1812。08434。pdf【2】^A Comprehensive Survey on Graph Neural Networks。 arxiv 2019。 https：//arxiv。org/pdf/1901。00596。pdf【3】^Deep Learning on Graphs： A Survey。 arxiv 2018。 https：//arxiv。org/pdf/1812。04202。pdf【4】^GNN papers https：//github。com/thunlp/GNNPapers/blob/master/README。md【5】^Semi-Supervised Classification with Graph Convolutional Networks（ICLR2017） https：//arxiv。org/pdf/1609。02907【6】^如何理解 Graph Convolutional Network（GCN）？https：//www。zhihu。com/question/54504471【7】^GNN 系列：圖神經網路的“開山之作”CGN模型 https：//mp。weixin。qq。com/s/jBQOgP-I4FQT1EU8y72ICA【8】^Inductive Representation Learning on Large Graphs（2017NIPS） https：//cs。stanford。edu/people/jure/pubs/graphsage-nips17。pdf【9】^Graph Attention Networks（ICLR2018） https：//arxiv。org/pdf/1710。10903【10】^Variational Graph Auto-Encoders（NIPS2016） https：//arxiv。org/pdf/1611。07308【11】^VGAE（Variational graph auto-encoders）論文詳解 https：//zhuanlan。zhihu。com/p/78340397【12】^Hierarchical Graph Representation Learning withDifferentiable Pooling（NIPS2018） https：//arxiv。org/pdf/1806。08