《深入淺出圖神經網絡》讀書筆記（8. 圖分類）

文章目錄

• 8. 圖分類
• • 8.1 基于全局池化的圖分類
  • 8.2 基于階層化池化的圖分類
  • • 8.2.1 基于圖坍縮的池化機制
    • • 1.圖坍縮
      • 2.DIFFPOOL
      • 3.EigenPooling
    • 8.2.2 基于TopK的池化機制
    • 8.2.3 基于邊收縮的池化機制

8. 圖分類

對于非規則結構的圖資料，之前的固定大小滑窗形式的池化操作不再适用，在圖分類中實作階層化池化的機制，是GNN需要解決的基礎問題。

8.1 基于全局池化的圖分類

讀出機制對經過K輪疊代的所有節點進行一次性聚合操作，進而輸出圖的全局表示：

y = R ( h i ( k ) ∣ ∀ v i ∈ V ) y=R({\pmb h_i^{(k)} |\forall v_i\in V }) y=R(hhhi(k)​∣∀vi​∈V)

讀出機制可以使用MAX、SUM等函數；

還有一種做法是引入一個與所有節點相連的虛拟節點，将全圖的表示等價于這個虛拟節點的表示。

注意：損失結構資訊；适合小圖資料。

8.2 基于階層化池化的圖分類

三種方案：

1. 基于圖坍縮的池化機制：将圖劃分為不同的子圖，然後将子圖視為超級節點，進而形成一個坍縮的圖。
2. 基于TopK的池化機制：對圖中的每個節點學習出一個分數，基于這個分數的排序丢棄一些低分數的節點，這類方法借鑒了CNN最大池化的思想：将更重要的資訊篩選出來。不同的是圖資料種難以實作局部滑窗操作，是以使用分數篩選；
3. 基于邊收縮的池化機制：邊收縮是指并行地将圖中的邊移除，并将被移除邊的兩個節點合并，保持它們的連接配接關系，其思路是通過歸并操作來逐漸學習圖的全局資訊的方法。

8.2.1 基于圖坍縮的池化機制

1.圖坍縮

圖G，某種劃分得到K個子圖 { G ( k ) } k = 1 K \{{G^{(k)}} \}_{k=1}^K {G(k)}k=1K​, Γ ( k ) \Gamma^{(k)} Γ(k)表示子圖 G ( k ) G^{(k)} G(k)中的節點清單。

簇配置設定矩陣 S ∈ R N × K S\in R^{N\times K} S∈RN×K，其定義如下： S i j = 1 S_{ij}=1 Sij​=1當且僅當 v i ∈ Γ ( j ) v_i\in \Gamma^{(j)} vi​∈Γ(j).

S T A S S^TAS STAS的意義：第i個簇與第j個簇的連接配接強度。

A coar = S T A S A_{\text{coar}}=S^TAS Acoar​=STAS

表述了圖坍縮之後的超級節點之間的連接配接強度，其中包含了超級節點自身内部的連接配接強度，如果隻需要考慮超級節點之間的連接配接強度 A coar [ i , i ] = 0 A_{\text{coar}}[i,i]=0 Acoar​[i,i]=0。

采樣算子 C ∈ R N × N k C\in R^{N\times N_k} C∈RN×Nk​,其定義為： C i j ( k ) = 1 C_{ij}^{(k)}=1 Cij(k)​=1,當且僅當 Γ j ( k ) = v i \Gamma_j^{(k)}=v_i Γj(k)​=vi​.

C是節點在原圖和子圖中順序關系的一個訓示矩陣。

下采樣：

x ( k ) = ( C ( k ) ) T x \pmb x^{(k)}=(C^{(k)})^T\pmb x xxx(k)=(C(k))Txxx

上采樣：

x ˉ = C ( k ) x \bar{\pmb x}=C^{(k)}\pmb x xxxˉ=C(k)xxx

鄰接矩陣A的劃分使用采樣算子：

A ( k ) = ( C ( k ) ) T A C ( k ) A^{(k)}=(C^{(k)})^TAC^{(k)} A(k)=(C(k))TAC(k)

這樣就可以計算簇内之間的連接配接關系。

确定簇内節點的融合方法，可以将結果表示為超級節點上的信号。疊代重複上述過程，就能獲得越來越全局的圖信号。一個執行個體如下：

2.DIFFPOOL

首個将圖坍縮與GNN結合起來的圖層面任務學習的算法。DIFFPOOL提出了一個可學習的簇配置設定矩陣。具體來說，首先通過一個GNN對每個節點進行特征學習，然後通過另一個GNN為每個節點學習出所屬各個簇的機率分布：

Z ( l ) = G N N l , e m b e d ( A ( l ) , H ( l ) ) S ( l ) = softmax ( G N N l , p o o l ( A ( l ) , H ( l ) ) ) H ( l + 1 ) = S ( l ) T Z ( l ) A ( l + 1 ) = S ( l ) T A S ( l ) Z^{(l)}=GNN_{l,embed}(A^{(l)},H^{(l)})\\ S^{(l)}=\text{softmax}({GNN_{l,pool}}(A^{(l)},H^{(l)}))\\ H^{(l+1)}={S^{(l)}}^TZ^{(l)}\\ A^{(l+1)}={S^{(l)}}^TA{S^{(l)}} Z(l)=GNNl,embed​(A(l),H(l))S(l)=softmax(GNNl,pool​(A(l),H(l)))H(l+1)=S(l)TZ(l)A(l+1)=S(l)TAS(l)

後兩個公式被稱為DIFFPOOL層，前一個是融合，明顯是加和節點特征，後一個是簇間鄰接矩陣的計算。

前兩個式子是通過GNN學習得到的，學習目的不同，參數不同。

DIFFPOOL有一個非常重要的特性：排列不變性。GCN也是具有排列不變性的，是以上述使用GNN若是GCN，那麼節點是否重新排列并不影響節點聚合成簇的結果。

3.EigenPooling

圖坍縮使用譜聚類算法來進行劃分，基本思路是先将資料變換到特征空間以凸顯更好的區分度，然後執行聚類操作（比如選擇Kmeans算法進行聚類，此時簇配置設定就是一種硬配置設定，保證了稀疏性）。

池化操作選用頻譜資訊來表示子圖資訊的統一整合：

假設子圖 G ( k ) G^{(k)} G(k)的拉普拉斯矩陣為 L ( k ) L^{(k)} L(k)，對應特征向量 u 1 ( k ) , u 2 ( k ) , . . . , u N k ( k ) \pmb u_1^{(k)},\pmb u_2^{(k)},...,\pmb u_{N_k}^{(k)} uuu1(k)​,uuu2(k)​,...,uuuNk​(k)​，可以使用上采樣算子 C ( k ) C^{(k)} C(k)将該特征向量（子圖上的傅裡葉基）上采樣到整個圖：

u ˉ l ( k ) = C ( k ) u l ( k ) \bar {\pmb u}_l^{(k)}=C^{(k)}{\pmb u}_l^{(k)} uuuˉl(k)​=C(k)uuul(k)​

池化算子 Θ l ∈ R N × K \Theta_l\in R^{N\times K} Θl​∈RN×K，我們将所有子圖的第 l l l個特征向量按行方向組織起來形成矩陣 Θ l \Theta_l Θl​，即：

Θ l = [ u l ( 1 ) , . . . , u l ( k ) ] \Theta_l=[{\pmb u}_l^{(1)},...,{\pmb u}_l^{(k)}] Θl​=[uuul(1)​,...,uuul(k)​]

由于子圖的節點數量不同，是以特征向量的數量也不同。用 N m a x = max ⁡ k = 1 , . . . , K N k N_{max}=\max_{k=1,...,K}N_k Nmax​=maxk=1,...,K​Nk​表示子圖中的最大節點數。然後，若子圖 G ( k ) G^{(k)} G(k)的節點數小于 N m a x N_{max} Nmax​，可以将 u l ( k ) ( N k < l < N m a x ) \pmb u_l^{(k)}(N_k<l<N_{max}) uuul(k)​(Nk​<l<Nmax​)設定為 0 ∈ R N k × 1 \pmb 0\in R^{N_k\times 1} 000∈RNk​×1.

池化過程如下：

X l = Θ l T X X_l=\Theta_l^TX Xl​=ΘlT​X

X l X_l Xl​在每個子圖第 l l l個特征向量作用下得到的, X l X_l Xl​的第k行表示的是第k個超級節點在 Θ l \Theta_l Θl​的作用下的表示向量。按照該機制，我們需要設計 N m a x N_{max} Nmax​個池化算子進行同樣的操作，再進行列方向拼接，結果如下：

X p o o l e d = [ X 0 , . . . , X N m a x ] X_{pooled}=[X_0,...,X_{N_{max}}] Xpooled​=[X0​,...,XNmax​​]

具體執行個體可見下圖：

由于低頻資訊的有效性，取 H < < N max ⁡ H<<N_{\max} H<<Nmax​

X coar = X p o o k e d = [ X 0 , . . . , X H ] X_{\text{coar}}=X_{pooked}=[X_0,...,X_H] Xcoar​=Xpooked​=[X0​,...,XH​]

設全圖上的信号為 x \pmb x xxx，有

( u ˉ l ( k ) ) T x = ( u l ( k ) ) T ( C ( k ) ) T x = ( u l ( k ) ) T x ( k ) (\bar {\pmb u}_l^{(k)})^T\pmb x=({\pmb u}_l^{(k)})^T(C^{(k)})^T\pmb x=({\pmb u}_l^{(k)})^T\pmb x^{(k)} (uuuˉl(k)​)Txxx=(uuul(k)​)T(C(k))Txxx=(uuul(k)​)Txxx(k)

其輸出表示子圖上的信号在子圖上對應的第 l l l個特征向量上的傅裡葉系數。

8.2.2 基于TopK的池化機制

這是一個不斷丢棄節點的過程。具體來說，首先設定一個表示池化率的超參數 k k k, k ∈ ( 0 , 1 ) k\in (0,1) k∈(0,1),接着學習出一個表示節點重要度的值z并并對其進行降序排序，将全圖 N N N個節點下采樣到 k N kN kN​個節點。

i = top − rank ( z , k N ) X ′ = X i , : A ′ = A i , i \pmb i=\text{top}-\text{rank}(\pmb z,kN)\\ X^{'}=X_{i,:}\\ A^{'}=A_{i,i} iii=top−rank(zzz,kN)X′=Xi,:​A′=Ai,i​

X i , : X_{i,:} Xi,:​表示按照向量i的值對特征矩陣進行行切片， A i , i A_{i,i} Ai,i​表示按照向量 i \pmb i iii的值對鄰接矩陣同時進行行切片和列切片。DIFFPOOL配置設定同樣的問題需要 k N 2 kN^2 kN2的空間複雜度來配置設定簇資訊，而基于Topk的池化機制，每次隻需要從原圖中丢棄 ( 1 − k ) N (1-k)N (1−k)N的節點即可。

節點重要度的計算：

a.為圖分類模型設定一個全局的基向量 p \pmb p p​p​​p,将節點特征向量在該基向量上的投影當作重要度：

z = X p ∣ ∣ p ∣ ∣ \pmb z=\frac{X_{\pmb p}}{||\pmb p||} zzz=∣∣p​p​​p∣∣Xp​p​​p​​

兩個作用：

1. 可以以投影大小來确定Topk的排序；
2. 投影大小還起到了一個梯度門限的作用，投影較小的節點僅有較小的梯度更新幅度，相對地，投影較大的節點會獲得更加充分的梯度資訊。

z = X p ∣ ∣ p ∣ ∣ , i = top − rank ( z , k N ) X ′ = ( X ⊙ tanh ( z ) ) i , : A ′ = A i , i \pmb z=\frac{X_{\pmb p}}{||\pmb p||},\pmb i=\text{top}-\text{rank}(\pmb z,kN)\\ X^{'}={(X\odot\text{tanh}(\pmb z))}_{i,:}\\ A^{'}=A_{i,i} zzz=∣∣p​p​​p∣∣Xp​p​​p​​,iii=top−rank(zzz,kN)X′=(X⊙tanh(zzz))i,:​A′=Ai,i​

點乘是利用節點的重要度對節點特征做了一次收縮變換，進一步強化了對重要度高的節點的梯度學習。——gpool層。

但是上述做法缺乏對所有節點的有效資訊的融合，是以在gpool層後跟一個讀出層，實作該尺度下的圖全局資訊的一次性聚合。具體實作是将全局平均池化和全局最大池化拼接起來：

s = 1 N ∑ i = 1 N x i ′ ∣ ∣ max ⁡ i = 1 N x i ′ \pmb s=\frac{1}{N}\sum_{i=1}^{N}\pmb x_i^{'}||\max_{i=1}^N \pmb x_i^{'} sss=N1​i=1∑N​xxxi′​∣∣i=1maxN​xxxi′​

全圖表示，将各層s相加：

s = ∑ l = 1 L s ( l ) \pmb s=\sum_{l=1}^L\pmb s^{(l)} sss=l=1∑L​sss(l)

b.使用一個GNN對節點重要度進行學習，這樣能更好地利用圖的結構資訊對節點的重要度進行學習。

8.2.3 基于邊收縮的池化機制

基本思想：疊代式地對每條邊上的節點進行兩兩歸并形成一個新的節點，同時保留合并前兩個節點的連接配接關系到新節點上。

存在問題：每個節點有多條邊，但是每個節點隻能從屬于一條邊進行邊收縮，如何選擇？

EdgePool設計了一個邊上的分數，根據該分數進行非重複式地挑選與合并。

過程如下：

計算每條邊的原始分數：

r i j = w T [ h i ∣ ∣ h j ] + b r_{ij}=\pmb w^T[\pmb h_i||\pmb h_j]+b rij​=wwwT[hhhi​∣∣hhhj​]+b

對原始分數沿鄰居節點進行歸一化：

s i j = softmax j ( r i j ) s_{ij}=\text{softmax}_j(r_{ij}) sij​=softmaxj​(rij​)

得到上述分數之後，接下來對所有的 s i j s_{ij} sij​進行排序，依次選擇該分數最高并且未被選中的兩個節點進行收縮操作。細節如下：

a為原始分數，b為 e r e^r er，c為歸一化之後的結果，先合并最高的 v 3 , v 4 v_3,v_4 v3​,v4​，再合并較高的 v 1 , v 2 v_1,v_2 v1​,v2​.

合并之後的節點特征可以使用求和的方式：

h i j = s ( h i + h j ) , s = max ⁡ ( s i j , s j i ) \pmb h_{ij}=s(\pmb h_i+\pmb h_j),s=\max(s_{ij},s_{ji}) hhhij​=s(hhhi​+hhhj​),s=max(sij​,sji​)

s同樣是收縮作用。

oe4-1669389714951)]

a為原始分數，b為 e r e^r er，c為歸一化之後的結果，先合并最高的 v 3 , v 4 v_3,v_4 v3​,v4​，再合并較高的 v 1 , v 2 v_1,v_2 v1​,v2​.

合并之後的節點特征可以使用求和的方式：

h i j = s ( h i + h j ) , s = max ⁡ ( s i j , s j i ) \pmb h_{ij}=s(\pmb h_i+\pmb h_j),s=\max(s_{ij},s_{ji}) hhhij​=s(hhhi​+hhhj​),s=max(sij​,sji​)

s同樣是收縮作用。

這種方法節點的融合都是從邊進行的，契合了圖的結構資訊；保留了融合之後圖中連接配接的稀疏性，空間複雜度低；作為一種端到端的池化機制，可以廣泛地整合到各個GNN模型中，以完成圖分類任務的學習。