深入理解圖卷積神經網路(GCN)原理

語言: CN / TW / HK
時間 2022-07-01 05:15:28
主題:

深入理解圖卷積神經網路(GCN)原理

@TOC

前言

深度學習的發展日新月異，從經典的深度網路（DNN、CNN、RNN）到GAN、強化學習。深度學習覆蓋的應用場景越來越豐富。今天介紹的圖神經網路是另一類深度學習方法。雖然，圖神經網路也可以納入深度學習的範疇，但它有著自己獨特的應用場景和演算法實現，對初學者並不算太友好。GCN，全稱Graph Convolutional Network，圖卷積網路，本文主要實現對GCN的深入理解，幫助快速理解GCN的原理以及用途。

一、為什麼需要GCN

卷積神經網路（CNN）的輸入是圖片等具有歐幾里得結構的圖結構，也就是這樣的圖： CNN 從歐式空間裡面利用卷積核(kernel)來提取特徵，因為圖片是比較規則的圖結構，因此使用卷積核就可以平移提取節點特徵,即CNN的核心在於它的kernel，kernel是一個個小視窗，在圖片上平移，通過卷積的方式來提取特徵。這裡的關鍵在於圖片結構上的平移不變性：一個小視窗無論移動到圖片的哪一個位置，其內部的結構都是一模一樣的，因此CNN可以實現引數共享。這就是CNN的精髓所在。但是通常我們會遇到拓撲網路或者社交網路，即如下 圖結構

像這種圖結構，並不整齊，一個網路包含不同數量的節點，不同的節點也包含不同的鄰居，這使得傳統的CNN無法作用在該圖結構中，並且圖中的每個node之間通常具有聯絡，因此當GCN問世，解決了這一難題。

二、GCN的原理

1.圖的定義

圖結構用G=(V,E)來表示，圖包括有向圖或者無向圖，但是在GCN中只考慮無向圖，V表示node的幾何，E表示edge的幾何，n表示的是node的數量，m則表示邊的個數。 下面我們介紹一個圖結構在GCN中各種符號表示的含義： $$G=(V,E) \qquad 表示當前圖結構 \v_i\in V\qquad表示v_i是一個node \e_{ij}=(e_i,e_j)\in E\qquad表示node\quad i與j之間的邊 \N(v)={u\in V|(v,u)\in E}\qquad表示點v的所有鄰居集合 \A_{ij}\qquad表示圖的鄰接矩陣 \A_{ij}=1\qquad表示node\quad i和j之間存在邊 \D\qquad 表示當前圖的度矩陣，D是對角矩陣 \d_{ii}\in D\quad 表示A中每個節點的度 \X\in R^{n\times d}表示n個節點的特徵向量，特徵向量維度是d $$

2.GCN來了

GCN GCN神奇的地方在於，能夠聚合一個node附近的node特徵，通過加權聚合學習到node的feature從而去做一系列的預測任務。

2.1 矩陣計算公式

假設我們手頭有一批圖資料，其中有n個節點（node），每個節點都有自己的feature向量，我們設這些節點的特徵組成一個n×d維的特徵矩陣X，然後各個節點之間的關係也會形成一個$n\times n$維的鄰接矩陣A。X和A便是我們模型的輸入。

對於所有node而言，即$H^{(l)}$表示當所有階段在l層的特徵向量矩陣，$H^{(l+1)}$表示所有經過一次卷積操作之後的特徵向量矩陣。一次卷積操作的公式如下： $$H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)$$ $$\hat{A}=A+I$$ 在這個公式中： - $A+I$，$I$是單位矩陣，即對角線為1，其餘全為0 - $\tilde{D}$是$\tilde{A}$的度矩陣,計算方法$\tilde{D}=\sum{\tilde{A}_{ij}}$ - $H$是每一層的所有節點的特徵向量矩陣，對於輸入層的話，$H^{(0)}$就等於$X$,$[n,d]$維度 - σ是非線性啟用函式，如$RELU$ - $W^{(l)}$表示的是當前層卷積變換的可訓練的引數矩陣

其實就是實現了對圖中每個node的鄰居node進行加權求和，利用與引數矩陣相乘得到新一層的node的特徵。 node 利用矩陣的形式迭代計算每個node的特徵，然後通過層傳播進行卷積操作，最後更新node的特徵。

2.2 以小規模矩陣講解公式含義

公式是從矩陣的角度計算，那為什麼要這麼複雜的矩陣形式呢，首先我們用最簡單的矩陣計算來看看 $$ \begin{array}{c} H^{(l+1)}=f\left(H^{(l)}, A\right)=\sigma\left(A H^{(l)} W^{(l)}\right) \ H^{(0)}=X \in R^{n \times d} \end{array} $$ 上面的公式中 W為卷積變換的引數，可以訓練優化。A 矩陣為鄰接矩陣，Aij 不為 0 則表示節點 i，j 為鄰居，ij存在邊。H 為所有節點的特徵向量矩陣，每一行是一個節點的特徵向量，H(0) 就是 X 矩陣。A 和 H 的乘積其實就是把所有的鄰居節點向量進行相加，如下圖所示，表示$A\times H$。

$$ \left[\begin{array}{cccc} 0 & 1 & 1 & 0 \ 1 & 0 & 0 & 0 \ 1 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{array}\right]\left[\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \ 2 & 2 & 2 & 2 & 2 \ 3 & 3 & 3 & 3 & 3 \ 4 & 4 & 4 & 4 & 4 \end{array}\right]=\left[\begin{array}{ccccc} 5 & 5 & 5 & 5 & 5 \ 1 & 1 & 1 & 1 & 1 \ 5 & 5 & 5 & 5 & 5 \ 3 & 3 & 3 & 3 & 3 \end{array}\right] $$ $A$表示的是鄰接矩陣，$H$表示的是4個node，每個node有一個5維的feature向量，將$A和H$直接相乘會得到右邊矩陣AH的結果。得到 AH 之後再和 W訓練引數 相乘，最後經過啟用函式 σ 就得到下一層4個node的特徵向量了。

但是上面的公式存在一些問題，$AH$ 只獲得了某個節點的鄰居資訊，而忽略了節點本身資訊。為了解決這個問題，我們可以將矩陣 $A$中對角線的值設為 1，即每個節點會指向自身，新的卷積公式如下： $$ \begin{aligned} H^{(l+1)} &=\sigma\left(\tilde{A} H^{(l)} W^{(l)}\right) \ \tilde{A} &=A+I_{n} \end{aligned} $$ I為單位矩陣，即對角線為 1，其餘為 0。即使用上面的卷積公式即可把節點自身的資訊也考慮進去，但是這個公式仍然存在問題：矩陣 A 沒有歸一化，AH 會把節點所有鄰居的向量都相加，這樣經過多層卷積後某些節點的特徵向量的值會很大。因為鄰接矩陣沒有被規範化，這在提取圖特徵時可能存在問題，比如鄰居節點多的節點傾向於有更大的特徵值。 通常使用對稱歸一化的方法： 歸一化的意思就是在聚合一個node節點的鄰居節點特徵時 $$ \begin{array}{l} A=D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \ A_{i j}=\frac{A_{i j}}{\sqrt{d_{i}} \sqrt{d_{j}}} \end{array} $$

2.3 綜上所述：

我們首先為了考慮A中所有node的自身特徵，將$A$加上$I$變成$\tilde{A}$，然後為了考慮在聚合node的鄰居節點特徵的時候會出現特徵向量不斷相加導致鄰居節點更多的節點特徵更大的現象，我們使用了對稱歸一化。 這樣一來就能得到GCN的層傳播公式，$$H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)$$

以一個二層的GCN為例 $$ \begin{array}{c} \hat{A}=\widetilde{D}^{-\frac{1}{2}} \tilde{A} \widetilde{D}^{-\frac{1}{2}} \ Z=\operatorname{softmax}\left(\hat{A} \operatorname{ReLu}\left(\hat{A} X W^{(0)}\right) W^{(1)}\right) \end{array} $$ GCN 可以用最後一層卷積層得到的節點特徵向量進行預測，即最後一層輸出層要用softmax操作，前面的0層到1層的非線性激勵函式採用的$ReLu$。

三、GCN有多牛

在看了上面的公式以及訓練方法之後，GCN好像並沒有什麼特別之處，但是結合GCN論文中所貼出來的結果，原來GCN這麼牛，在原資料中同類別的node，經過GCN的提取出的embedding，已經在空間上自動聚類了 聚類 深入探究GCN為什麼這麼強的原因其實正是考慮到了圖中每一個node的鄰居關係，這與傳統的CNN是不同的，並且在其背後的數學公式之美也值得我們研究，具體的深究GCN公式計算請參考如何理解 Graph Convolutional Network（GCN）

總結

至此，我們已經深入理解了GCN的相關概念，其實就是利用圖中的每個結點無時無刻不因為鄰居和更遠的點的影響而在改變著自己的狀態直到最終的平衡，關係越親近的鄰居影響越大。 node之間通過互相影響以及W引數矩陣的訓練，最終學習到每一個node的特徵。

同時GCN的層數也不宜過多，簡單說就是gcn層數多了會使得每個點的embedding比較相近，這樣子對於後面的節點分類等loss函式不利，當然可以通過各種normalize來抵消一些影響。從熱力學角度看啊，每個節點embedding看作是節點溫度，gcn每次卷積可以看作是每個節點和周圍節點在做熱量交換。在沒有外部熱量源的條件下（節點沒有額外的標籤label），如果圖是全聯通的，多次卷積最後就會使得每個節點的溫度，也就是embedding變成一樣的。

下篇文章我們將討論使用DGL實現GCN以及GAT的引入。

「」