最近了解了一下GNN，寫本文概述以加深理解，主要參考一下兩篇綜述文章：

清華大學孫茂松組的 Graph Neural Networks: A Review of Methods and ApplicationsIEEE Fellow, Philip S. Yu的 A Comprehensive Survey on Graph Neural Networks

符號定義

GNN( Graph Neural Networks )簡介

之前深度學習

主要關注例如文字的序列結構、例如圖片的平面結構，現在處理這些數據的做法也比較成熟，關注序列任務的NLP領域多用RNN、Transformer、CNN對數據進行Encoder，而關注平面結構的CV領域更多使用CNN及其各種變體對數據進行Encoder。在現實世界中更多的數據表示並不是序列或者平面這種簡單的排列，而是表現為更為複雜的圖結構，如社交網路、商品-店鋪-人之間的關係、分子結構等等.

圖是由節點及連接節點的邊構成的，現在熱門的基於深度學習的GNN就是用來處理圖類型數據的網路，而該網路的目標就是學習每個節點v的表示 h_v in mathbb{R}^m ，而每個節點的表示由該節點的特徵、與該節點連接的邊的特徵、該節點的鄰居表示和它鄰居節點的特徵計算得到：

h_v = f(x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]})

對於關注節點的任務，可以直接拿 h_v 的表示去完成特定任務，而對於關注整個圖的任務這可以通過將所有的節點的表示做Pooling或其他方法獲得一個全局的表示信息然後去做相應的任務。

GNN分類--按更新方式分類

如圖所示，GNN主要分為圖卷積網路(GCN)、基於注意力更新的圖網路(GAT)、基於門控的更新的圖網路、具有跳邊的圖網路.

各種GCN

圖卷積網路是目前最主要（重要）的圖網路，GCN按照更新方式又可以分為基於譜的和基於空間的。

基於譜的GCN

我們常用的GCN模型長這樣：

我們常用的GCN模型長這樣：

H^{t+1} = ilde{A}H^{t}W \ ilde{A} = I_n + D^{- frac{1}{2} }A D^{- frac{1}{2} }

對於這個式子直覺告訴我這和NLP裡面的Self-Attention的聚合過程也太像了吧，把 ilde{A} 換成我們Attention時計算出來的權重矩陣，簡直一模一樣。這裡的A是一個鄰接矩陣，若兩個節點之間存在一種關係（有邊）則對應鄰接矩陣A上的一個非零值（權重），如果沒有關係則對應0，而 D^{- frac{1}{2} } 在這個式子裡面起到的作用就是歸一化，單位陣 I 起到的作用是添加一個自己到自己的邊，這個A對應於Attention里的權重矩陣也很符合直覺。

這個公式很容易理解，它就是一個圖卷積神經網路， ilde{A} 充當卷積核，不過看起來和我們見過的卷積操作好像相差比較大，不過這個公式並不是和我們直覺的想法一樣得來的，而是經歷了一個漫長的過程。

在繼續介紹之前先講一個圖信號處理領域的一個結論：

定義歸一化的拉普拉斯矩陣 mathbf{L} = mathbf{I}_n - D^{- frac{1}{2} } A D^{- frac{1}{2} } ， 拉普拉斯矩陣是實對稱矩陣，可以對其進行譜分解得到 mathbf{L} = mathbf{U} Lambda mathbf{U}^T ， 其中 mathbf{U} 是酉矩陣（即矩陣的列向量兩兩正交，且 U^{-1} = U^T ）。 圖信號 hin mathbb{R}^N 是圖中第i個節點 h_i 的表示向量,信號h的圖傅里葉變換定義為 mathcal{F}(h)=U^Th ,逆傅里葉變換為 mathcal{F}^{-1}(hat{h})=Uhat{h}, hat{h} 表示圖傅里葉變換對信號h的輸出。因為我理論基礎不足，只能根據直覺解釋這個過程，在信號處理中，傅里葉變換就是將在時域的信號變換到頻域，而所用到的所有的餘弦/正弦函數都是正交向量（無窮維向量），每一個正弦/餘弦函數就是一個頻域的基，所以傅里葉變換終究還是一個變基的過程，就是將信號從一個空間通過改變基的表示映射到另一個空間。上文中提到的 U 矩陣作為一個酉矩陣（列向量兩兩正交）顯然滿足作為一組基(且是標準正交基)的條件，我們可以通過 U 矩陣將 h 映射到另一個空間，該空間就是圖的頻域空間，至於為什麼選擇矩陣 U 作為變換矩陣而不是隨便選一個酉矩陣作為變換矩陣，應該是因為這個 U 矩陣是和圖的結構密切相關的（由該圖的歸一化拉普拉斯矩陣譜分解得到的）。

對於該結論的嚴格推倒過程可以參考The Emerging Field of Signal Processing on Graphs這篇論文。

下面開始繼續介紹GCN，定義對每個節點v的卷積操作， g star h ，卷積有一個性質:時域的卷積既是在頻域的乘積，所以為了計算方便可以先將信號做傅里葉變換到頻域之後再做逆變換即可得到卷積結果，其中 g是與拉普拉斯矩陣的特徵值相關的。所以圖上的卷積定義為：

g star h = mathcal{F}^{-1}( mathcal{F}(g odot mathcal{F}( h) ) = mathbf{U}( mathbf{U}^T g odot mathbf{U}^T h )

這裡如果將 mathbf{U}^T g 參數化為 g_{ heta}(Lambda)簡記為 g_{ heta} ，上式將簡化為 gstar h = mathbf{U}g_{ heta} mathbf{U}^T h ，基於譜的卷積都是如此定義，區別在於 g_{ heta} 的不同選擇。

最簡單的方法是直接另 g_{ heta}=diag{ heta_1, heta_2, cdots, heta_n } ，此處 heta 是與拉普拉斯矩陣特徵值相關的.

可惜這種簡單的計算方法每次都要對 mathbf{L} 矩陣進行譜分解，參數數量和圖的大小一致（大小為n），且每次都是全局卷積學習參數的複雜度會非常高，不僅如此，每次卷積涉及到的大規模矩陣乘法耗時也是 mathbf{O}(n^2) ，還有一個問題是現在的做法沒有很好的應用節點之間的空間特性（距離遠近）。

為了解決上面的問題有人提出一種巧妙地方法即下面要講的 ChebNet

首先解決參數數量和局部卷積簡化參數學習難度的問題。

我們希望用更少的（與圖大小無關）的參數來表示卷積核，對 heta 的參數表示進行壓縮，另

g{ heta} = diag( sum^{K}_{j=0} alpha j lambda_1^j dots sum_{j=0}^K alpha j lambda_n^j) = sum_{j=0}^K alpha _j Lambda^j

其中 Lambda = diag(lambda_1 cdots lambda_n) （拉普拉斯矩陣的特徵值）

這樣由:

mathbf{L}^2 = mathbf{U} Lambda mathbf{U}^T mathbf{U} Lambda mathbf{U}^T \ mathbf{U} mathbf{U}^T = I_n

得

egin{aligned} g_{ heta} star h &= mathbf{U} sum^{K}_{j=0} alpha_{j} Lambda_{j} mathbf{U}^{T} h \ &= sum_{j=0}^{K} alpha_{j} mathbf{U} Lambda^{j} mathbf{U}^{T}h \ &= sum^{K}_{j=0} alpha_{j} mathbf{L}^{j} h end{aligned}

現在的圖卷積已經不用進行譜分解了，這裡只需要計算 mathbf{L}^{j} ，其中 mathbf{L} 是由鄰接矩陣導出來的（加上自回歸的邊後，每個位置是否為0是相同的），我們學習圖論的時候知道通過計算鄰接矩陣的k次方得到的矩陣非0位置表示兩個節點存在長度為k的路徑，這樣的卷積具有很好的空間局部性，我們可以通過控制k來決定每個節點的表示僅由與其距離不超過k的節點及其關係決定，不像之前的圖卷積計算當前節點會用到全局所有節點的信息，更能運用好spatial localization，且現在需要學習的參數數量變為了與圖無關的K個。

現在來解決每次卷積計算複雜度為 mathbf{O}(n^2) 的問題

這裡用到Chebyshev polynomial，該多項式是遞歸定義的：

T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x) \ T_{0} = 1, T_1 = x

為了能夠簡化卷積的計算複雜度，我們發現卷積核的計算需要計算 Lambda^j , 將卷積核定義為如下可以遞歸計算的方式可以減少計算量。

g_{ heta}(Lambda) = sum_{k=0}^{K-1} heta_k T_k( ilde{Lambda} ) \ 其中 ilde{Lambda} = frac{2Lambda}{lambda_{max}} - I_n

然後通過和上面類似的推倒得到遞歸的卷積計算方式：

y = g_{ heta} ( mathbf{L} )x = sum_{k=0}^{K-1} heta_k T_k( ilde{ mathbf{L} })x \ ilde{ mathbf{L} } = frac{2}{ lambda _{max}} mathbf{L} - mathbf{I}_N

現在的卷積操作已經能滿足上面提出的所有要求了。

在此基礎上的變種

很多時候K不需要取的很大就能獲得很好的效果，當K=2時，即只取前兩項可以得到：

g_{ heta} ( mathbf{L} )x = heta_0 x + heta_1 ilde{L} x

進一步簡化，取 lambda_{max} approx 2, heta = heta_0 = - heta_1 則：

g_{ heta star x} approx heta(I_N + D^{- frac{1}{2} }AD^{- frac{1}{2} })x

這就是本節剛開頭提到的形式。

這種形式在堆疊多層時會造成數值上的不穩定及梯度爆炸/消失問題，所以可以用到重歸一化技巧：

I_n + D^{- frac{1}{2} }AD^{- frac{1}{2} } ightarrow ilde{D}^{- frac{1}{2} }A ilde{D}^{- frac{1}{2} } , 其中 ilde{A} = A + I_N, ilde{D}_{ii} sum_{j} ilde{A}_{ij}

非基於譜的方法

基於譜的方法需要學習的參數都是與Laplacian矩陣的特徵向量和特徵值相關的，即取決於圖的結構，這樣有什麼問題呢，如果你在一個大圖或者很多同構的小圖上進行訓練是可以的，這也有很多應用場景。但是如果我們要處理很多不同結構的圖，那就不能用同一套參數來學習，不懼泛化性，比如我們對很多樹結構的句子進行分類（句子表示為依存句法樹或其他），每個句子的表示可能都不同，那就沒辦法用上面的方法做。

下面介紹幾種不依賴於圖譜的方法的GNN。

不基於譜最簡單的方法就是直接把每個節點的鄰居節點直接求和：

x = h_v + sum^{ mathcal{N}_v }_{i=1}h_i \ h_v^{} = sigma(xW_L^{ mathcal{N}_v })

這裡根據鄰居個數的不同用不同的參數W。

DCNN

DCNN的做法也很簡單：

H = f(W^c odot P^* X)

其中 P^* = {P, P^2, dots,P^K} , P是度歸一化後的臨接矩陣。不要誤會，這裡的參數和圖的結構沒有關係，這裡的參數W對應於與該節點不同距離的信息。

GraphSAGE 提出了一個更加通用的框架：

h_{ mathcal{N}_v }^t = AGGREGATE_t({h_u^{t-1}, forall u in mathcal{N}_v }) \ h_v^t = sigma(W^t cdot [h_v^{t-1}|h_{mathcal{N}_v}^t ])

這裡的AGGREGATE可以取不同的方法，GraphSAGE論文中提到可以用mean，max-pooling, sum，LSTM。 其實這是一個通用框架，本文提到的很多方法都可以套進來。

Attention

圖的信息傳遞當然也可以用attention（NLP中的每個單詞、CV中的每個像素當做一個節點，它們的attention都可以當做是在圖上的操作），通過當前節點的不同鄰居與當前節點表示上的關係計算信息流的權重, a為attention參數：

alpha_{ij} = frac{exp(LeakyReLu(a^T[Wh_i | Wh_j]))}{sum_{k in mathcal{N}_i exp(LeakyReLu(a^T[Wh_i | Wh_k])) }} \ h_i^{} = sigma( sum_{j in mathcal{N}_i} alpha_{ij}Wh_j)

為了獲得更充分（不同側重）的信息，Attention is all you need 提出的multi-head attention，可以表示為下面兩種形式

h_i^{} = |_{k=1}^K sigma( sum_{j in mathcal{N}_i } alpha_{ij}^kW^kh_j ) \ h_i^{} = sigma(frac{1}{K} sum_{k=1}^K sum_{j in mathcal{N}_i } alpha_{ij}^kW^kh_j )

其中 | 表示拼接

Skip connection

相比於傳統的網路，GNN的深度一般更淺，原因是GNN的感受野隨著深度的增加指數增大在信息傳遞過程中會引入大量雜訊。所以在GNN中也有人嘗試加入skip connection來緩解這個問題。下面是一個用Highway的方法的例子：

T(h^t) = sigma(W^th^t +b^t) \ h^{t+1} = h^{t+1} odot T(h^t) + h^t odot(1 - T(h^t))

當前的輸出還有一部分來自於上層的輸出。

Gate

Highway的方法比較簡單，還有更複雜的方法來控制信息的傳播，比如可以用GRU，LSTM的門控方式來傳遞圖的信息，這個沒啥好解釋的，看公式應該寫的很明白了，這裡只介紹一下基於GRU的GGNN：

a_v^t = A_v^T[h_1^{t-1}, cdots, h_N^{t-1}]^T+ b \ z_v^t = sigma(W^z a_v^t + U^z h_v^{t-1}) \ r_v^t = sigma(W^r a_v^t + U^rh_v^{t-1}) \ ilde{h_v^t}= tanh(Wa_v^t+ U(r_v^t odot h_v^{t-1})) \ h_v^t = (1-z_v^t) odot h_v^{t-1} + z_v^t odot ilde{h_v^t}

其中 A_v 是臨接矩陣中與v有關的值構成的矩陣。

GNN 訓練方法

原始的GCN方法每個節點的表示依賴於圖中所有的其他節點，計算複雜度過大，且由於依賴於拉普拉斯矩陣訓練的網路不懼泛化性。

GraphSAGE對於每個節點的計算不涉及整張圖，所以效率更加高，不過為了緩解深度加深感受野指數爆炸的現象，GraphSAGE每次信息計算通過採樣只使用部分鄰居。

FastGCN對GraphSAGE的隨機採樣加以改進，針對每個節點連接其他節點個數的不同給定不同的重要性。

q(v) propto frac{1}{| mathcal{N}_v| } sum_{u in mathcal{N}_v } frac{1}{| mathcal{N}_u | }

還有一些限制感受野的其他方法，咱也不懂.

通用框架

Message Passing

該框架包含3個操作，信息傳遞操作（M），更新操作（U），讀取操作（R）：

m_v^{t+1} = sum_{w in mathcal{N}_v } M_t(h_v^t, h_w^t, e_{vw}) \ h_v^{t+1} = U_t(h_v^t, m_v^{t+1}) \ hat{y} = R({h_v^T|v in G})

其中 e_{vw} 表示邊的信息。

上文提到的GGNN套用這個框架表示為：

egin{aligned} M_t(h_v^t, h_w^t, e_{vw}) &= A_{e_{vw}}h_w^t \ U_t &= GRU(h_v^t, m_v^{t+1}) \ R &= sum_{v in V} sigma(i(h_v^T, h_v^0)) odot(j(h_v^T)) end{aligned}

NLNN

何凱明提出的Non-local Neural Networks用來捕捉圖像上的non-local信息：

h_i^i = frac{1}{C(h)} sum_{ forall j } f(h_i, h_j) g(h_j)

其中 f 用於計算i、j之間的關係， h_i^i = frac{1}{C(h)} sum_{ forall j } f(h_i, h_j) g(h_j) 表示對輸入做一個映射， frac{1}{C(h)} 表示對結果進行歸一化。其中 f 可以有不同的計算方式，比如什麼Gaussian，Embedded Gaussian， Dot product, Concatenation等。

感覺這個有點牽強。。

Graph Networks

這個就是去年火爆一時的由一群大佬聯名的Relational inductive biases, deep learning, and graph networks。

由於這個更複雜更general，先來介紹一下其中的符號表示, 這裡V的表示與文章開頭定義有所不同：

N_v 表示節點總數，N_e 表示邊的數量

圖：G = (u, V, E) , 其中 V = {h_i}_{i=1:N^v} 表示圖中的每個節點的表示，u表示全局信息， E = {(e_k, r_k, s_k)}_{k=1:N^e} , 這其中， e_k 表示邊的信息， r_k 表示接收節點， s_k 表示發送節點

分別針對邊、節點、全局節點定義了三種更新函數 phi 和三種聚合函數 ho :

e_k^{} = phi ^e(e_k, h_{rk}, h_{sk}, u) \ h_i^{} = phi ^h(ar{e}_i^{}, h_{i}, u) \ u^{} = phi ^u(ar{e}^{}, ar{h}^{}, u) \ ar{e_i^{}} = ho^{e ightarrow h} (E_i^{})\ ar{e^{}} = ho^{e ightarrow u} (E^{}) \ ar{h^{}} = ho^{h ightarrow u} (H^{}) \

其中 E_i^{} = {(e_k^{}, r_k, s_k)}_{r_k=i, k=1:N^e} , \ H^{} = {h_i^{}}_{i=1:N^v} , \ E^{} = igcup _i E_i^{} = {(e_k^{}, r_k, s_k)}_{k=1:N^e}

每個操作都很符合直覺，比如邊的表示的更新依賴於原始邊的表示、全局節點的表示及邊連接的兩個節點的表示。下面給出在該框架下的計算演算法：

最終返回全局節點、普通節點、邊的表示，在該框架下的圖任務可以是基於圖的也可以是基於節點的還可以是基於邊的。

大部分的模型都只是實現了該框架的一部分，包括上面提到的兩種通用框架也只是該框架的子集，比如上面的Message passing 框架就沒有u節點，也沒有對邊的更新，NLNN框架沒有的東西就更多了。

...

以後有時間再補充吧。如果有人看的話，有錯誤還請指出，共同進步.

^_^


推薦閱讀：
相关文章