[图神经网络] 图节点Node表示---GCN
一. 概括
圖神經網絡已經成為深度學習領域最熾手可熱的方向之一。GCN具體思想的核心是通過拉普拉斯矩陣可以對圖信息進行特征分解的特點把該公式定義為圖卷積操作，同時圖卷積的出現也填補了神經網絡獲取拓撲圖類型特征的空白。
圖譜理論簡單的概括就是借助于圖的拉普拉斯矩陣的特征值和特征向量來研究圖的性質
GCN(Graph convolution Network)是Convets在圖結構上的自然推廣。卷積神經網絡是采用局部感知區域、共享權值和空間域上的降采樣，相對于位移、縮放和扭曲，具有穩定不變的特性，能夠很好的提取圖像的空間特征。圖結構不具備圖片的平移不變性，傳統的卷積方式不適用于圖結構。圖中每個節點的鄰域節點數目不一致，無法用同樣尺寸的卷積核進行提取.
而GCN的本質就是提取圖的結構特征，關鍵在于如何定義局部接受域(receptive field)，主要有兩種方式：
1. Spatial Approach?空域方法 --- 如何定義局部感受域或者是鄰居和節點的順序 比如給節點的邊指定方向
2. Spectral Approach? 頻域方法（譜方法）--- 通過圖的拉普拉斯矩陣的特征值和特征向量對圖結構進行處理。
?
二 圖卷積理論基礎
什么是拉普拉斯矩陣？為什么GCN要用拉普拉斯矩陣？
拉普拉斯變換后的矩陣是正定對稱矩陣，可以進行特征分解（譜分解）。
對于圖G=(V,E), 其Laplacian 矩陣的定義為L=D?A?
- L為拉普拉斯矩陣Laplacian matrix
- D為對角度矩陣Degree matrix，對角線上的元素是頂點的度，即該元素鏈接的元素的個數
- A為鄰接矩陣 Adjacency matrix ,即表示任意兩個頂點之間的鄰接關系，鄰接則為1，不鄰接則為0
看圖示例，Laplacian 矩陣的計算方法。
物理意義：這個矩陣描述圖的拉普拉斯矩陣與圖的性質之間的關系。拉普拉斯矩陣與圖的性質滿足L=D?A?這種矩陣關系，其中圖G=(V,E)的性質，體現在圖的鄰接矩陣A和圖的度矩陣D上。
在理解了這個的基礎上，還有其他的幾種拉普拉斯矩陣，上面這種拉普拉斯矩陣只是其中的一種。
通過上面的公式的物理意義，我們知道了，圖的性質可以表示在拉普拉斯矩陣之中，即圖的性質可以通過拉普拉斯矩陣體現出來。這樣，我們將圖的分析，可以變為對拉普拉斯矩陣的分析。
首次將深度學習里卷積操作引入圖數據里的方法GCN是Thomas Kpif于2017年在論文Semi-supervised classification with graph convolutional networks提出的,在他的博客里對模型解釋非常清楚。
對稱歸一化拉普拉斯算子
為何要歸一化？
采用加法規則時，對于度大的節點特征越來越大，而對于度小的節點卻相反，這可能導致網絡訓練過程中梯度爆炸或者消失的問題。
為什么GCN要用拉普拉斯矩陣？
拉普拉斯矩陣矩陣有很多良好的性質
(1)拉普拉斯矩陣是對稱矩陣，可以進行特征分解（譜分解），這就和GCN的spectral domain對應上了
(2)拉普拉斯矩陣只在中心頂點和一階相連的頂點上（1-hop neighbor）有非0元素，其余之處均為0
(3)通過拉普拉斯算子與拉普拉斯矩陣進行類比
?
三. GCN介紹
假設有一批圖數據，其中有N個節點（node），每個節點都有自己的特征，我們設這些節點的特征組成一個N×D維的矩陣X，然后各個節點之間的關系也會形成一個N×N維的矩陣A，也稱為鄰接矩陣（adjacency matrix）。
X和A便是我們模型的輸入。
GCN也是一個神經網絡層，且僅僅是一個全連接層。（下圖是一個2層的GCN例子）
它的層與層之間的傳播方式是(網絡的每一層結構)
其中，
（1）A波浪=A+I，I是單位矩陣；
（2）D波浪是A波浪的度矩陣（degree matrix）；
（3）H是每一層的特征，對于輸入層的話，H0就是X；
（4）σ是非線性激活函數。
?
?
上圖中的GCN輸入一個圖，通過若干層GCN每個node的特征從X變成了Z，但是，無論中間有多少層，node之間的連接關系，即A都是共享的。
就是說解決了上面說的不具備平移不變性問題。其思路是：借鑒CNN，將卷積分為三步：
（1）選定中心節點后，確定鄰域：對每個節點選擇固定個數的節點作為鄰居；
（2）給鄰域結點編號；
（3）參數共享：選擇固定大小的窗口進行參數共享。
?
?
假設構造一個兩層的GCN，激活函數分別采用ReLU和Softmax，則整體的正向傳播的公式為：
例如，我們有一個多分類問題，有10個類，F 被設置為10。在第2層有了10個維度的向量后，我們將這些向量通過一個softmax函數進行預測。
最后，我們針對所有帶標簽的節點計算cross entropy損失函數:
就可以訓練一個node classification的模型了。由于即使只有很少的node有標簽也能訓練，作者稱他們的方法為半監督分類。當然也可以用這個方法去做graph classification、link prediction，只是把損失函數給變化一下即可。
所以利用GCN提取出的特征，我們可以實現節點分類（node classification）、圖分類（graph classification）、邊預測（link prediction），還可以得到圖的嵌入表示（graph embedding）
?
四. GCN公式解釋
作者給出了一個由簡入繁的過程來解釋：
我們的每一層GCN的輸入都是鄰接矩陣A和node的特征H，那么我們直接做一個內積，再乘一個參數矩陣W，然后激活一下，就相當于一個簡單的神經網絡層嘛，是不是也可以呢？
實驗證明，即使就這么簡單的神經網絡層，就已經很強大了。這個簡單模型應該大家都能理解吧，這就是正常的神經網絡操作。
但是這個簡單模型有幾個局限性：
- 只使用A的話，由于A的對角線上都是0，所以在和特征矩陣H相乘的時候，只會計算一個node的所有鄰居的特征的加權和，該node自己的特征卻被忽略了。因此，我們可以做一個小小的改動，給A加上一個單位矩陣 I ，這樣就讓對角線元素變成1了。
- A是沒有經過歸一化的矩陣，這樣與特征矩陣相乘會改變特征原本的分布，產生一些不可預測的問題。所以我們對A做一個標準化處理。首先讓A的每一行加起來為1，我們可以乘以一個D的逆，D就是度矩陣。我們可以進一步把D的拆開與A相乘，得到一個對稱且歸一化的矩陣?
通過對上面兩個局限的改進，我們便得到了最終的層特征傳播公式：
公式中的與對稱歸一化拉普拉斯矩陣十分類似，而在譜圖卷積的核心就是使用對稱歸一化拉普拉斯矩陣，這也是GCN的卷積叫法的來歷。原論文中給出了完整的從譜卷積到GCN的一步步推導。
A(hat)其實它就是鄰接矩陣A做的一個歸一化。下面為了表達的方便，直接當做鄰接矩陣來分析
?
A是n×n維，H是n×m維
A矩陣的第i行和H矩陣的第j列對應元素相乘在求和就得到Q矩陣的(i,j)個元素。 仔細看看圖中高亮的那幾個向量的內部：
GCN的這一步，跟GraphSAGE是一樣的思想，都是把鄰居的特征做一個聚合（aggregation）。
在GCN中，是直接把鄰居的特征進行求和，而實際不是A跟H相乘，而是A帽子，A帽子是歸一化的A，所以實際上我畫的圖中的鄰居關系向量不應該是0,1構成的序列，而是歸一化之后的結果，所以跟H的向量相乘之后，相當于是“求平均”。
?
?
?
?
五 從數學角度簡單模擬GCN公司
從圖G中，我們有一個鄰接矩陣A和一個度矩陣D。同時我們也有特征矩陣X。
那么我們怎樣才能從鄰居節點處得到每一個節點的特征值呢？解決方法就在于A和X的相乘。
看看鄰接矩陣的第一行，我們看到節點A與節點E之間有連接，得到的矩陣第一行就是與A相連接的E節點的特征向量（如下圖）。同理，得到的矩陣的第二行是D和E的特征向量之和，通過這個方法，我們可以得到所有鄰居節點的向量之和。
計算 "和向量矩陣 "AX的第一行。
這里還有一些需要改進的地方。
此時的計算還存在上局限（1）忽略了節點本身的特征。按理得到的矩陣第一行應該包含結點A和E的信息，所以做出改進：
通過給每個節點增加一個自循環，我們得到新的鄰接矩陣
對于問題(2): 對于矩陣縮放，我們通常將矩陣乘以對角線矩陣。在當前的情況下，我們要取聚合特征的平均值，或者從數學角度上說，要根據節點度數對聚合向量矩陣X進行縮放。直覺告訴我們這里用來縮放的對角矩陣是和度矩陣D有關的東西.? 現在的問題變成了我們要如何對和向量進行縮放/歸一化？換句話說：
我們如何將鄰居的信息傳遞給特定節點？我們從我們的老朋友average開始。在這種情況下，D的逆矩陣（即，）就會用起作用。基本上，D的逆矩陣中的每個元素都是對角矩陣D中相應項的倒數。
例如，節點A的度數為2，所以我們將節點A的聚合向量乘以1/2，而節點E的度數為5，我們應該將E的聚合向量乘以1/5，以此類推。
因此，通過D取反和X的乘法，我們可以取所有鄰居節點的特征向量（包括自身節點）的平均值。
?
到目前為止一切都很好。但是你可能會問加權平均()怎么樣？直覺上，如果我們對高低度的節點區別對待，應該會更好。
但我們只是按行縮放，但忽略了對應的列（虛線框）。
為列增加一個新的縮放器
新的縮放方法給我們提供了 "加權 "的平均值。我們在這里做的是給低度的節點加更多的權重，以減少高度節點的影響。這個加權平均的想法是，我們假設低度節點會對鄰居節點產生更大的影響，而高度節點則會產生較低的影響，因為它們的影響力分散在太多的鄰居節點上。
因為進行了兩次歸一化處理，左乘和右乘了D波浪的-1/2逆。
?
假設存在一個圖
該矩陣不再是對角陣了，為了保持它是對角陣,?
這樣既得到了近似的歸一化也保持了矩陣對稱性。（左乘是行變換，右乘是列變換。）
?
| ? | ? |
| ? | ? |
?
最后總結：
?
六. GCN的優缺點：
優點：
1.理論完善；
2.可以捕捉graph的全局信息；
缺點：
1.直推式(transducive)：無法直接泛化到新加入（未見過）的節點，為新節點產生embedding需要額外的操作；
2.輸出的是節點唯一確定的embedding；
3.很難應用在超大圖上：無論是拉普拉斯計算還是圖卷積過程，因為GCN其需要對 整張圖進行計算，所以計算量會隨著節點數的增加而遞增;
4.基礎GCN是基于無向圖的;
從圖上的信息傳遞角度考慮，一次圖卷積計算，就是一次全圖計算，所以很容易想到，GCN難以應用到工業界；
?
代碼參考：https://github.com/tkipf/pygcn
總結
以上是生活随笔為你收集整理的[图神经网络] 图节点Node表示---GCN的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 网络安全中如何保护电子邮件安全
- 下一篇： Android6.0 开发中怎么实现一个