摘要：本文我們將主要介紹各種典型的圖神經網路的網路架構和訓練方法。
本文我們將主要介紹各種典型的圖神經網路的網路架構和訓練方法。文章《A Comprehensive Survey on Graph Neural Networks》[1]提供了一個全面的圖神經網路(GNNs)概述，並且將最新的圖神經網路分為四類，即遞迴圖神經網路(RecGNNs)、卷積圖神經網路(ConvGNNs)、圖自動編碼器(GAEs)和時空圖神經網路(STGNNs)。在圖神經網的實際應用中，卷積圖神經網路的使用最為廣泛，因此，本文將重點介紹ConvGNNs一類網路模型，如上圖GNN Roadmap所示。
1. 歐式空間卷積在講卷積圖神經網路（非歐空間做卷積）之前，我們先來回顧下卷積神經網路（歐式空間做卷積）的過程。有一張如下圖所示的6*6的image，我們在做卷積的時候，通常會使用一個固定大小的卷積核，比如3*3，然後根據設定的步長滑動整張6*6的image，在每一次滑動之處與原圖相應位置做內積。如下圖為卷積核滑動兩次之後的結果。
但是對於非歐空間的圖結構，我們無法找到一個固定大小的卷積核去滑動整個圖區域，如下圖所示。
這時我們就要針對圖的特殊結構，藉助歐式空間的卷積方法和圖結構特徵，提出兩種卷積圖神經網路的卷積方案：
方案一：
參考CNN的思想，對每個節點的鄰居進行某種方式的加權求和，即Spatial-based convolution。
方案二：
參考傳統的訊號處理的方法，對原始訊號進行處理，引入濾波器來定義圖卷積，圖卷積運算被解釋為從圖訊號中去除噪聲，即Spectral-based convolution。
本篇我們將主要介紹基於空間的卷積圖神經網路方法和對應的典型的網路架構。
2. Spatial-based Convolution在講基於空間的卷積圖神經網路方法之前，我們先引入兩個術語：
lAggregate：
用當前層的某節點鄰居狀態特徵更新下一層該節點的狀態特徵（下左圖）。比如下圖，我們想要將
（下標代表節點的索引，上標代表當前在第幾層卷積操作）透過圖卷積的方式轉變成
，我們可以透過某種加權求和的方式將 Layer i的
以及
的鄰居節點的feature整合起來，從而得到
的feature，其它節點一樣的道理，最後得到Layeri+1的hidden state。
lReadout：
把所有節點的狀態特徵集合起來代表整個圖的狀態特徵（下右圖）。即採用某種sum或者average的方式將所有nodes的feature抽象成一個hidden state，並以此代表整張圖的feature。
2.1圖神經網路(Neural Network for Graphs，NN4G)[2]NN4G在圖神經網路領域算是比較早（2009）的提出的卷積圖神經網路模型，其透過直接將節點的鄰域資訊相加來進行圖卷積，表示式如下：
其中v表示圖中某個節點的索引，K代表當前所在的卷積層數。 N(v)表示節點v的所有鄰居。f()是啟用函式，比如Relu，W和θ是待學習的模型引數，即下圖中的W，下圖中Hidden Layer 1中的
的獲得是將
以及其鄰居的資訊進行相加，並透過加權的方式整合input layer在該節點的資訊
，轉成矩陣形式就是：
其中矩陣A就是圖網路的鄰接矩陣。
而readout層則透過對每一層的所有節點資訊的取平均，即下圖中所有紫色節點 ，從而獲得每一層圖的representation，並對每一層的資訊透過求和平均的方式進行整個圖的representation更新，即：
對於NN4G，其具體的計算過程可以用下面這幅圖概括。NN4G也是卷積圖神經網路的代表性結構，後續的卷積圖神經網路都是或多或少的在NN4G的基礎上做一些簡單的修改（Aggregate）而獲得。所以理解NN4G的運算流程對於理解基於空間的卷積圖神經網路至關重要。
2.2.擴散卷積神經網路(Diffusion Convolutional Neural Network, DCNN)[3]DCNN在Aggregate階段給出了不一樣的方法，DCNN將圖卷積視為擴散過程，它假設資訊以一定的轉移機率從一個節點轉移到鄰近的節點，使資訊分佈在幾輪後達到均衡。如下圖所示，第一層的
的結果是與
距離為1的節點的featue的求和平均，同理第二層的
則是與
距離為2的節點的featue的求和平均，這樣我們對每一層的卷積操作可以用以下公式表示：
其中K表示層數，
代表轉移矩陣，D是節點度矩陣，A是鄰接矩陣，
就代表了卷積所能觀測到的節點鄰居範圍，K=1時表示對距離為1的鄰居節點的卷積，K=2時表示對距離為2的鄰居節點的卷積。當我們計算出了每一層的節點的feature的時候，我們需要對每一層的節點feature進行concatenation成一個矩陣
，然後透過一些線性變換對每個節點在不同層的feature做特徵變換，如下圖所示，最終得到整張圖或者每個節點的特徵矩陣y。
2.3混合模型(Mixture Model Networks, MoNET)[4]透過上述模型，我們可以發現，當計算某個節點在某一層的hidden state的時候，對於該節點的所有鄰居上述演算法都是一視同仁。但是實際情況可能是任何兩個節點之間的關係是有區別的。比如在一副社交關係圖譜中，某個個體和其所連線的所有個體親密關係通常不會相同。這就需要一種新的aggregate方式來解決。
MoNET同樣是定義了一種新的Aggregate的方式，在Aggregate階段不是簡單的對鄰居節點feature的平均求和，而是透過加權的方式，權重的計算則是透過衡量節點之間的度的距離方式，即：
當然這裡只是提出了一種權重的計算方式，實際實現中可以選擇不同的權重實現方式。其中
表示節x 的度，圖中的w則是特徵變換（比如NN），經過NN對節點feature進行編碼，最後對某一節點的鄰居節點特徵加權求和。
2.4圖取樣聚合模型(Graph Sample and aggregate, GraphSAGE)[5]GraphSAGE主要是透過對鄰居節點取樣的方法對節點資訊進行更新，即圖中的Step 1，然後再對這些取樣的節點資訊進行某種方式的聚合，主要有Mean\Pooling\LSTM三種aggregate的方法，即圖中的Step 2，Step 3則是利用聚合資訊進行當前節點label或者鄰居節點的預測，預測的方式有兩種，一種是無監督學習方式。無監督學習基於圖的損失函式希望臨近的頂點具有相似的向量表示（公式的前半部分），同時讓分離的頂點的表示儘可能區分（公式的後半部分），損失函式如下：
其中v是u的臨近節點，
是負取樣樣本的分佈，即對遠離節點v的節點的取樣，Q是負取樣的個數，z是待學習的節點特徵。第二種是有監督學習方式，監督學習形式根據任務的不同直接設定目標函式即可，如最常用的節點分類任務使用交叉熵損失函式等。
2.5圖注意神經網路(Graph Attention Networks, GAT)[6]注意力機制已經在傳統神經網路CNN和RNN中有了成功的實踐，並且使用attention後模型的效能在特定任務上都有不少的提升。GAT是將attention機制實現在卷積圖神經網路之中。這裡的attention就是一種用來計算節點與鄰居之間權重的方式，最後透過加權求和的方式更新節點的feature，節點間權重的計算公式如下：
其中
是模型更新之後的權重表示式，
是節點v相對於節點u的attention值，w是模型學習的引數。
下圖就是GAT模型的圖卷積層的更新過程，其中 e(energy)就是attention的權重。
3. 總結本篇博文主要介紹了Spatial-based Convolution（基於空間的卷積圖神經網路），以NN4G為基礎，分別介紹了DCNN，MONET，GrapgSAGE，GAT等卷積圖神經網路結構以及其實現的方式。對於想要在圖神經網路進行實踐的同學，可以先學習一些開源的圖神經網路框架。目前完成度較好的圖神經網路框架主要是基於PyTorch和MXNet的DGL (Deep GraphLibrary)和PyG(PyTorch Geometric)。
參考文獻
[1] ]Wu Z , Pan S , Chen F , et al. A Comprehensive Survey on Graph NeuralNetworks[J]. IEEE Transactions on Neural Networks and Learning Systems,2019.
[2] A. Micheli, "Neural Network for Graphs: A Contextual ConstructiveApproach," in IEEE Transactions on Neural Networks, vol. 20, no. 3, pp.498-511, March 2009, doi: 10.1109/TNN.2008.2010350.
[3] https://arxiv.org/abs/1511.02136
[4]https://arxiv.org/pdf/1611.08402.pdf
[5] https://arxiv.org/pdf/1706.02216.pdf
[6]https://arxiv.org/pdf/1710.10903.pdf
[7]https://mp.weixin.qq.com/s?__biz=MzkwNDE5MDY5Mg==&mid=2247486844&idx=1&sn=6ae21b181c208aa67bcd597572e0d840&chksm=c08b82f7f7fc0be178ac3b11d9df15280d74149c5246a7de641e927d13190afe7ce1f9d603e9&scene=21#wechat_redirect
[8].http://speech.ee.ntu.edu.tw/~tlkagk/courses/ML2020/GNN.pdf