《深入淺出圖神經網絡》讀書筆記（7.GNN的變體與架構）

文章目錄

• 7. GNN的變體與架構
• • 7.1 GraphSAGE
  • • 7.1.1 采樣鄰居
    • 7.1.2 聚合鄰居
    • 7.1.3 算法過程
  • 7.4 GNN的通用架構
  • • 7.4.1 MPNN
    • 7.4.2 NLNN
    • 7.4.3 GN

7. GNN的變體與架構

GNN圖神經網絡，神經網絡技術運用于圖資料的學習任務中去的一大類方法。

空域角度下的GCN本質上是一個疊代式地聚合鄰居的過程，這啟發了一大類模型對于這種聚合操作的重新設計，這些設計在某些方面大大加強了GNN對于圖資料的适應性。解構這些設計能夠提出一些GNN的通用表達架構，為GNN模型設計工作提供統一範式。

7.1 GraphSAGE

本節的GraphSAGE從兩個方面對GCN做了改動：

1. 通過采樣鄰居的政策将GCN由全圖的訓練方式改造為中心的小批量訓練方式，這使得大規模圖資料的分布式訓練成為可能；
2. 該算法對聚合鄰居的操作進行了拓展，提出了替換GCN操作的幾種新的方式。

7.1.1 采樣鄰居

根據梯度下降時小批量的思想，為了提高效率，我們也可以将這種思想遷移到聚合鄰居的操作上。對鄰居進行随機采樣來控制實際運算時節點k階子圖的資料規模，在此基礎上對采樣的子圖進行随機組合來完成小批量式的訓練。

上圖如果使用GCN，模型層數為2時，所有節點都需要參與計算。

如果我們隻考慮節點的k階子圖，仍有以下問題：

1. 子圖節點數指數級增長。圖中節點度的均值 d ˉ \bar d dˉ，執行k層，那麼需要計算 ∑ i = 1 k d ˉ i 個 節 點 , 其 中 i 為 層 數 \sum_{i=1}^k\bar d^i個節點,其中i為層數 ∑i=1k​dˉi個節點,其中i為層數。
2. 真實世界中圖資料節點的度往往呈現幂律分布，存在一些度數很大的超級節點，很難處理。

解決：采樣鄰居時控制子圖的發散率。設定第k層的鄰居采樣倍率為 S k S_k Sk​，每個節點采樣的一階鄰居數不能超過 S k S_k Sk​。這裡GraphSAGE選擇了均勻分布，這樣大量減少了計算複雜度。

7.1.2 聚合鄰居

提出了幾種新的操作形式：

1. 聚合操作必須對聚合節點的數量做到自适應。不管節點鄰居數量如何，聚合操作後輸出次元必須一緻，一般是一個統一長度的向量；
2. 聚合操作的結點具有排列不變性。對于我們熟知的2D圖像資料與1D序列資料，前者包含空間順序，後者包含時序順序。由于圖資料是無序的資料結構，鄰居節點的排序順序與輸出結果無關。即 A g g ( v 1 , v 2 ) = A g g ( v 2 , v 1 ) Agg(v_1,v_2)=Agg(v_2,v_1) Agg(v1​,v2​)=Agg(v2​,v1​).
3. 聚合操作可導，這樣可以友善優化模型。

比較符合的操作算子：

平均/加和算子： W 和 b \pmb W和\pmb b WWW和bbb是聚合操作的學習參數：

A g g s u m = σ ( S U M { W h j + b j , ∀ v j ∈ N ( v i ) } ) Agg^{sum}=\sigma(SUM\{\pmb W\pmb h_j+\pmb b_j,\forall v_j\in N(v_i)\}) Aggsum=σ(SUM{WWWhhhj​+bbbj​,∀vj​∈N(vi​)})

池化聚合算子：最大池化操作如下：

A g g p o o l = M A X { σ ( W h j + b ) , ∀ v j ∈ N ( v i ) } Agg^{pool}=MAX\{\sigma(\pmb W\pmb h_j+\pmb b ),\forall v_j\in N(v_i)\} Aggpool=MAX{σ(WWWhhhj​+bbb),∀vj​∈N(vi​)}

可以用DNN模型代替 W h j + b j \pmb W\pmb h_j+\pmb b_j WWWhhhj​+bbbj​.

7.1.3 算法過程

此圖參考的是知乎大師兄的相關内容，大家可以去看看。

上述算法的基本思路：先将小批量集合B内的中心節點聚合操作所要涉及的k階子圖全部一次性周遊處理，然後在這些節點上進行K次聚合操作的疊代式計算。

1-7行就是周遊操作，把所有需要計算的節點尋找到構成集合 B 0 , B 1 , B 2 , . . . , B k B^0,B^1,B^2,...,B^k B0,B1,B2,...,Bk，分别代表每層選取的點集合，其中 B 0 B^0 B0是最外層;9-15行是聚合操作，11行是調用聚合 操作完成對每個節點鄰居特征的整合輸出；12行是将聚合後的鄰居特征與中心節點上一層的特征進行拼接，然後送到一個單層網絡裡得到中心節點新的特征向量，13行對節點的特征向量進行歸一化處理，将所有節點的向量都統一到機關尺度上.

由上圖可知，采樣由内到外，聚合由外到内。B是中心節點的特征集合，可以看到最終聚合得到的是中心節點的特征向量。

這個算法計算過程沒有拉普拉斯矩陣的參與，每個節點的特征學習過程僅僅隻與其k階鄰居相關，而不需要考慮全圖的結構資訊，這樣的方法适合做歸納學習（歸納學習，指可以對在訓練階段見不到的資料（新節點或者新圖）直接進行預測而不需要重新訓練的學習方法）。與之相對的是轉導學習（所有的資料在訓練階段都可以拿到，學習過程是作用在這個固定的資料上的，一旦資料發生改變需要重新進行學習訓練），典型的有圖上的随機遊走算法。

7.2 介紹了注意力機制和圖注意力網絡（GAT），7.3介紹了R-GCN和知識圖譜，旨在解決異構圖的問題，詳細見書P134-P142。這兩種均是GNN通用架構的特殊形式。書上介紹足夠簡潔。

7.4 GNN的通用架構

三種通用架構：

1. 消息傳播神經網絡（Message Passing Neural Network）MPNN
2. 非局部神經網絡（Non-Local Neural Network）NLNN
3. 圖網絡（Graph Network）GN

7.4.1 MPNN

基本思路：節點的表示向量通過消息函數M和更新函數U進行K輪消息傳播機制的疊代後得到的，傳播過程如下：

m i ( k + 1 ) = ∑ v j ∈ N ( v i ) M ( k ) ( h i ( k ) , h j ( k ) , e i j ) h i ( k + 1 ) = U ( k ) ( h i ( k ) , m i ( k + 1 ) ) \pmb m_i^{(k+1)}=\sum_{v_j\in N(v_i)}M^{(k)}(\pmb h_i^{(k)},\pmb h_j^{(k)},\pmb e_{ij} )\\ \pmb h_i(k+1)=U^{(k)} (\pmb h_i^{(k)} ,\pmb m_i^{(k+1)}) mmmi(k+1)​=vj​∈N(vi​)∑​M(k)(hhhi(k)​,hhhj(k)​,eeeij​)hhhi​(k+1)=U(k)(hhhi(k)​,mmmi(k+1)​)

e i j \pmb e_{ij} eeeij​表示邊<i,j>上的特征向量，k表示第k次消息傳播。

消息函數的輸入由邊本身以及兩側節點構成，使用RDF三元組表示這樣的輸入：

Source ⟶ Predict Object \text{Source}\stackrel{\text{Predict}}{\longrightarrow}\text{Object} Source⟶Predict​Object

在消息函數作用下，圖裡面所有的RDF都會向外廣播消息，之後這些消息沿着邊方向傳播到RDF的兩側節點處進行聚合，聚合後的消息會在之後的更新函數作用下對節點特征進行更新，如下圖：

其實邊也是可能具有特征向量的，如果對邊始終維護一個狀态向量，可以參見GN的做法。

由于MPNN的消息函數作用于三元組RDF，是以對各種類型的圖資料都具有一定适應性，處理方式如下:

1. 同構圖：本身容易處理，唯一特殊的是有向權重圖，對于這類圖資料，可以把邊的正反方向看成兩種關系，借用R-GCN的思路進行處理，同時對邊上的權重可以考慮進鄰接矩陣中當作歸一化項一并處理。
2. 異構圖：考慮R-GCN方式，另外如果關系不多，可以将關系編碼成one-hot向量當作邊上的特征進行處理。
3. 屬性圖： 屬性圖中需要考慮的因素有節點的異構以及邊屬性。對于前者，如果我們追求工程上的簡化處理，在調用MPNN之前可以對不同類型的節點分别送進變換函數裡面，将異構的節點變換到同一次元的同一特征空間裡，之後當作節點同構的圖處理。對于後者，可以參考關系圖的處理方式，這裡如果邊上具有一些屬性資訊的話，按照消息函數的機制，需要對其進行特征編碼（比如類别型屬性特征進行onehot編碼或者embedding編碼）。

7.4.2 NLNN

非局部神經網絡是對注意力機制的一般性總結，GAT是它的一個個例，NLNN通過non-local操作将任意位置的輸出響應計算為所有位置特征的權重和。位置可以是圖像中的空間坐标，也可以是序列資料中的時間坐标。圖資料中可以是節點：

non-local操作定義如下：

h i ′ = 1 C ( h ) ∑ ∀ j f ( h i , h j ) g ( h j ) \pmb h_i^{'}=\frac{1}{C(\pmb h)}\sum_{\forall j}f(\pmb h_i,\pmb h_j)g(\pmb h_j) hhhi′​=C(hhh)1​∀j∑​f(hhhi​,hhhj​)g(hhhj​)

i是輸出位置的索引，j是枚舉所有可能位置的索引。 f ( h i , h j ) f(\pmb h_i,\pmb h_j) f(hhhi​,hhhj​)是i和j位置上元素之間的相關度函數， g ( h j ) g(\pmb h_j) g(hhhj​)表示對輸入 h j \pmb h_j hhhj​進行變換的變換函數，因子 1 C ( h ) \frac {1}{C(\pmb h)} C(hhh)1​用于歸一化。

g一般采用線性變換: g ( h j ) = W g h j g(\pmb h_j)=W_g\pmb h_j g(hhhj​)=Wg​hhhj​,這裡 W g W_g Wg​是需要學習的權重參數。f的一些選擇：

1. 内積

   f ( h i , h j ) = θ ( h i ) T ϕ ( h j ) ， 其 中 , θ ( h i ) = W θ h i , ϕ ( h j ) = W ϕ h j , 分 别 表 示 對 輸 入 的 一 種 線 性 變 換 ， C ( h ) = ∣ h j ∣ f(\pmb h_i,\pmb h_j)=\theta(\pmb h_i)^T\phi(\pmb h_j)， \\其中,\theta(\pmb h_i)=W_\theta\pmb h_i,\phi(\pmb h_j)=W_\phi \pmb h_j,分别表示對輸入的一種線性變換，C(\pmb h)=|\pmb h_j| f(hhhi​,hhhj​)=θ(hhhi​)Tϕ(hhhj​)，其中,θ(hhhi​)=Wθ​hhhi​,ϕ(hhhj​)=Wϕ​hhhj​,分别表示對輸入的一種線性變換，C(hhh)=∣hhhj​∣

2. 全連接配接

   使用輸出為一維标量的全連接配接層定義 f f f:

   f ( h i , h j ) = σ ( w f [ θ ( h i ) ∣ ∣ ϕ ( h j ) ] ) , 其 中 ， w f 是 将 向 量 投 影 為 标 量 的 權 重 參 數 ， C ( h ) = ∣ h j ∣ f(\pmb h_i,\pmb h_j)=\sigma(w_f[\theta (\pmb h_i)|| \phi(\pmb h_j) ]),\\ 其中，w_f是将向量投影為标量的權重參數，C(\pmb h)=|\pmb h_j| f(hhhi​,hhhj​)=σ(wf​[θ(hhhi​)∣∣ϕ(hhhj​)]),其中，wf​是将向量投影為标量的權重參數，C(hhh)=∣hhhj​∣

3. 高斯函數

   f ( h i , h j ) = e θ ( h i ) T ϕ ( h j ) ， 其 中 ， C ( h ) = ∑ ∀ f f ( h i , h j ) f(\pmb h_i,\pmb h_j)=e^{\theta(\pmb h_i)^T\phi(\pmb h_j) }，\\其中，C(\pmb h)=\sum_{\forall f}f(\pmb h_i,\pmb h_j) f(hhhi​,hhhj​)=eθ(hhhi​)Tϕ(hhhj​)，其中，C(hhh)=∀f∑​f(hhhi​,hhhj​)

   對于給定的i， 1 C ( h ) \frac{1}{C(\pmb h)} C(hhh)1​表示沿次元j進行歸一化之後的值，此時 h i ′ = softmax j ( θ ( h i ) ϕ ( h j ) ) g ( h j ) \pmb h_i^{'}=\text{softmax}_j(\theta(\pmb h_i)\phi(\pmb h_j))g(\pmb h_j) hhhi′​=softmaxj​(θ(hhhi​)ϕ(hhhj​))g(hhhj​)。如果自然對數e的幂指數改成全連接配接形式，就是GAT。

7.4.3 GN

基本計算單元包含3個要素：節點的狀态 h \pmb h hhh，邊的狀态 e i j \pmb e_{ij} eeeij​，圖的狀态 u \pmb u uuu.圍繞這3個元素，有三個更新函數 ϕ \phi ϕ，三個聚合函數 ρ \rho ρ，具體如下：

e i j ′ = ϕ e ( e i j , h i , h j , u ) e i ′ ˉ = ρ e → h ( [ e i j ′ , ∀ v j ∈ N ( v i ) ] ) h i ′ = ϕ h ( e i ′ ˉ , h i , u ) e ′ ˉ = ρ e → u ( [ e i j ′ , ∀ v j ∈ E ] ) h ′ ˉ = ρ h → u ( [ h i ′ = ∀ v i ∈ V ] ) u ′ = ϕ u ( e ′ ˉ , h ′ ˉ , u ) \pmb e_{ij}^{'}=\phi^e(\pmb e_{ij},\pmb h_i,\pmb h_j,\pmb u)\\ \bar {\pmb e_i^{'}}=\rho^{e\rightarrow h}([\pmb e_{ij}^{'},\forall v_j\in N(v_i)])\quad\pmb h_i^{'}=\phi^h(\bar {\pmb e_i^{'}},\pmb h_i ,\pmb u )\\ \bar {\pmb e^{'}}=\rho^{e\rightarrow u}([\pmb e_{ij}^{'},\forall v_j\in E])\quad\bar{ \pmb h^{'}}=\rho^{h\rightarrow u}([\pmb h_i^{'}=\forall v_i\in V])\quad \pmb u^{'}=\phi^u(\bar {\pmb e^{'}},\bar {\pmb h^{'}},\pmb u) eeeij′​=ϕe(eeeij​,hhhi​,hhhj​,uuu)eeei′​ˉ​=ρe→h([eeeij′​,∀vj​∈N(vi​)])hhhi′​=ϕh(eeei′​ˉ​,hhhi​,uuu)eee′ˉ=ρe→u([eeeij′​,∀vj​∈E])hhh′ˉ=ρh→u([hhhi′​=∀vi​∈V])uuu′=ϕu(eee′ˉ,hhh′ˉ,uuu)

r{ \pmb h{'}}=\rho{h\rightarrow u}([\pmb h_i^{‘}=\forall v_i\in V])\quad \pmb u{'}=\phiu(\bar {\pmb e^{’}},\bar {\pmb h^{'}},\pmb u)

$$

GN對圖裡的節點、邊、全圖都維護了相應的狀态，這三者可以分别對應上節點層面的任務、邊層面的任務、全圖層面的任務。