這是一篇GNN的綜述, 發(fā)表于2021年的TNNLS. 這篇博客旨在對GNN的基本概念做一些記錄.

論文地址: 論文

1. 引言, 背景與定義

對于圖像數據來說, CNN具有平移不變性和局部連接性, 因此可以在歐氏空間上良好地學習. 然而, 對于具有圖結構的數據(例如社交網絡 化學分子等)就需要用GNN來學習.

最早期的GNN網絡是遵循類似RNN的循環(huán)迭代式的(RecGNN), 主要的對象是DAG(有向無環(huán)圖). 這個方式停止的條件是節(jié)點的表示趨于穩(wěn)定.

后來發(fā)展出了卷積圖網絡(ConvGNN), 主要有基于譜域(頻域)的和基于空域的. 除此之外, 還發(fā)展出了圖自編碼器(Graph autoencoders, GAEs)和時空(spatial-temporal)GNN.

因此這篇文章主要就把GNN分成了這四種:

• 循環(huán)GNN
• 卷積GNN
• 圖自編碼器
• 時空GNN

后面, 作者主要講了GNN與兩個任務的區(qū)別:

GNN與network embedding. network embedding旨在將一個網絡的節(jié)點編碼成低維度的向量表示, 并保持網絡的拓撲結構不變, 這樣降維之后, 一些分類, 聚類等任務, 就可以通過傳統的機器學習方法實現(例如SVM). 因此, GNN和network embedding的關系是, GNN可以通過一個圖自編碼器來學習一個低維的表示, 即network embedding的任務. 總而言之, network embedding主要是通過降維來實現應用機器學習方法的目的.

GNN與圖的核方法(graph kernel methods). 圖的核方法主要是將一個圖編碼到一個向量空間, 以便應用SVM之類的任務(圖的層面).

2. 分類和框架

如前所述, 本文將GNN分成了四類, 如下圖所示:

節(jié)點分類任務的ConvGNN. 對于每一個節(jié)點, 在每次迭代中聚合它臨近節(jié)點的信息(圖卷積), 最后通過一個非線性變換對節(jié)點進行分類. 其中$X\in {\mathbb{R}}^{n\times d}$表示節(jié)點特征拼成的矩陣.

圖分類任務的ConvGNN. 在圖卷積操作后, 使用一個池化層, 將圖粗糙化成一個子圖, 得到圖的高階表示(higher representations). 最后用一個readout函數, 對圖進行分類.

用于network embedding的圖自編碼器. 先用圖卷積得到每個節(jié)點的embedding, 然后解碼器在給定embedding的情況下計算成對距離. 在應用非線性激活函數后, 解碼器重構圖鄰接矩陣. 通過最小化真實鄰接矩陣與重構鄰接矩陣之間的差異來訓練網絡.

時空GNN. 對每個timestep的GNN都應用卷積, 隨后跟一個 1D-CNN 層對時序特征進行提取. 輸出層是一個線性變換,為每個節(jié)點生成一個預測,例如它在下一個時間步的未來值.

3. 循環(huán)GNN

循環(huán)GNN一般都是GNN早期的開山之作, 由于計算量的限制, 一般都是應用于有向無環(huán)圖的. The Graph Neural Network Model(IEEE Trans. Neural Network, 2009)提出了一個更具有普適性的方式, 可以應用于各種圖. 節(jié)點更新方式如下式:

為了保證收斂性, $f$必須是一個收縮映射. 如果$f$是神經網絡的話, 則必須加入罰項.

除此之外, 門控GNNGated graph sequence neural networks, (arxiv, 2015)將門控單元(GRU)作為上述的$f$函數, 減少了收斂時間. 其節(jié)點更新用上一個隱藏態(tài)和臨近節(jié)點隱藏態(tài)的線性映射組成, 如下式:

$$h_v^{(t)}=GRU(h_v^{(t?1)},\sum _{u\in N(v)}W{h}_u^{(t?1)})$$

這個網絡的訓練用通過時間的反向傳播(RNN的反向傳播方式)進行梯度下降.

總體來說, 循環(huán)GNN的方式類似RNN, 是作用于離散的節(jié)點上面. 但是循環(huán)GNN每次(層)用的更新函數$f$是同一個, 因此必須保證收斂性.

4. 卷積GNN

與循環(huán)GNN不同, 卷積GNN的每一層都是可學習的不同參數, 具有固定層數, 和循環(huán)GNN區(qū)別如下:

卷積GNN基本分為兩類, 基于譜的(頻域的)和基于空域的.

A. 基于譜的卷積GNN

基于譜的GNN基本對于無向圖而言, 我們可以用(歸一化的)圖Laplace矩陣唯一的表示這個圖的拓撲性質:

$$L=I_n?D^{?1/2}A{D}^{?1/2}$$

其中$D$為對角矩陣, 每個對角元素為鄰接陣對應行的和, 也就是這個節(jié)點的度.

我們可以看出, 對于Laplace矩陣的$(i,j)$個元素:
如果$i=j$, $a_{i,j}=0,d_{i,j}=deg(v_i),l_{i,j}=1$
如果$i\ne j$, $v_i,v_j$不相連, $a_{i,j}=0,l_{i,j}=0$
如果$i\ne j$, $v_i,v_j$相連, $a_{i,j}=1,l_{i,j}=?1/\sqrt{deg(v_i)deg(v_j)}$
因此, 圖Laplace矩陣可以唯一表示圖

容易看出Laplace矩陣是實對稱的, 因此是半正定的, 因此具有非負特征值. 我們可以對其做特征值分解:

$$L=U\Lambda U^T$$

因此我們可以基于Laplace矩陣的特征值分解定義圖的Fourier變換:

$$\mathcal{F}(\hat{x})=U^T\hat{x}$$

由于$U{U}^T=I$, 因此可以立即定義圖的逆Fourier變換:

$${\mathcal{F}}^{?1}(x)=Ux$$

所以圖Fourier變換實際上就是將圖信號$x$投影到一個標準正交基構成的空間中, 換句話說, $x$可以表示成$U$的列向量的線性組合: $x={\sum }_i{\hat{x}}_i{u}_i$, 這就是正 逆Fourier變換的關系(和信號處理中的一致).

我們考慮將圖信號經過濾波器, 根據卷積定理(時域卷積的Fourier變換對應頻域乘積), 有:

$$\begin{gathered} x?g={\mathcal{F}}^{?1}(\mathcal{F}(x)\odot \mathcal{F}(g)) \\ =U(U^{T}x\odot U^{T}g) \end{gathered}$$
其中$\odot$表示element-wise乘法. 如果我們記$g_{\theta }=diag(U^{T}g)$, 則$U^{T}x\odot U^{T}g=g_{\theta }{U}^{T}x$, 所以

$$x?g=U{g}_{\theta }{U}^{T}x$$

譜GNN的關鍵在于如何選擇濾波器$g_{\theta }$.

在實際中, 我們考慮網絡的第$k$層, 輸入和輸出的通道數分別為$f_{k?1},f_k$, 則該層第$j$個通道的輸出為:

$$H_{:,j}^{(k)}=\sigma (\sum _{i=1}^{f_{k?1}}U{\Theta }_{i,j}^{(k)}{U}^T{H}_{:,i}^{(k?1)})\in {\mathbb{R}}^n$$

其中${\Theta }_{i,j}^{(k)}$是對角陣, 對角元素為一組可學習的參數.

然而, 這樣的方式有三個缺點:

1. 圖的任何擾動對特征值和特征向量的影響都很大(特征值分解的性質)
2. 學習到的濾波器是域相關的, 這意味著它們不能應用于具有不同結構的圖.
3. 特征值分解的復雜度很高($O(n^3)$).

為了解決復雜度高的問題, ChebNet和GCN經過幾個簡化將復雜度降為線性復雜度. ChebNet用Chebyshev多項式來估計濾波器$g_{\theta }$, 即

$$g_{\theta }=\sum _{i=1}^K{\theta }_i{T}_i(\tilde{\Lambda }),\tilde{\Lambda }=2\Lambda /{\lambda }_{max}?I_n$$
這樣$\tilde{\Lambda }$中的值都落在$[?1,1]$內. $T_i(x)$表示Chebyshev多項式, 按照如下遞推定義:

$T_0(x)=1$
$T_1(x)=x$
$T_i(x)=2x{T}_{i?1}(x)?T_{i?2}(x)$

帶入, 就得到按照Chebyshev多項式估計的圖卷積結果如下:

$$x?g=U(\sum _{i=1}^K{\theta }_i{T}_i(\tilde{\Lambda }))U^{T}x$$

可以用數學歸納法證明拉普拉斯矩陣的Chebyshev多項式矩陣和特征值矩陣具有如下關系(?):

$$T_i(\tilde{L})=U{T}_i(\tilde{\Lambda })U^T,\tilde{L}=2L/{\lambda }_{max}?I_n$$

因此有

$$x?g=U(\sum _{i=1}^K{\theta }_i{T}_i(\tilde{\Lambda }))U^{T}x=\sum _{i=1}^K{\theta }_i{T}_i(\tilde{L})x$$

ChebNet 定義的過濾器在空間上是局部的, 這意味著過濾器可以獨立于圖大小提取局部特征. ChebNet的頻譜線性映射到[?1,1].

下面再來看經典的圖卷積網絡GCN. GCN是ChebNet的簡化, 取了$K=1$, 并且假定最大特征值為2, 得到

$$\begin{gathered} x?g={\theta }_{0}x+{\theta }_1(2L/{\lambda }_{max}?I_n)x \\ ={\theta }_{0}x+{\theta }_1(2(I_n?D^{?1/2}A{D}^{?1/2})/{\lambda }_{max}?I_n)x \\ ({\lambda }_{max}=2)={\theta }_{0}x?{\theta }_1{D}^{?1/2}A{D}^{?1/2}x \end{gathered}$$

為了進一步減少參數量, 防止過擬合, 假定$\theta ={\theta }_0=?{\theta }_1$, 立即有

$$x?g=\theta (I_n+D^{?1/2}A{D}^{?1/2})x$$

在經驗上, $I_n+D^{?1/2}A{D}^{?1/2}$容易造成穩(wěn)定性的問題, 因此GCN采用${\tilde{D}}^{?1/2}\tilde{A}{\tilde{D}}^{?1/2}$來代替, 其中$\tilde{A}=A+I_n,\tilde{D}$為$\tilde{A}$的度矩陣.

對這種歸一化的理解:
由于鄰接矩陣的對角元素是0, 因此$\theta (I_n+D^{?1/2}A{D}^{?1/2})x$的第一項可以認為是聚合節(jié)點自身信息, 第二項可以認為是聚合鄰近節(jié)點的信息. 然而這樣會造成不穩(wěn)定, 因此更改一下形式, 即直接添加self-loop也就是自環(huán)邊, 也就相當于給鄰接矩陣$A$加上單位陣$I_n$.

后續(xù)跟進GCN的工作主要是對于對稱矩陣的選取.

B. 基于空域的卷積GNN

實際上空域上對圖進行卷積和在典型具有歐氏空間結構的圖像上進行卷積是相似的, 如下圖所示:

例如, NN4G在每一次迭代聚合一個節(jié)點和它鄰居節(jié)點的信息, 如下式所示:

此外, 還有一種比較有意思的Diffusion GNN, 也就是將圖卷積過程視為擴散過程. 在擴散過程中, 信息按照一定的概率從一個節(jié)點傳入另一個節(jié)點, 這樣的概率和節(jié)點的度有關, 如下式:

$$H^{(k)}=f(W^{(k)}\odot P^{k}X),P=D^{?1}A$$

$P=D^{?1}A$的意義是對于度大的點, 其信息傳入相連鄰居節(jié)點的就更多(權重大)

在Diffusion Graph Convolution中, 最后的結果是將中間結果加起來, 即:

$$H=\sum _{k=0}^{K}f(P^{k}X{W}^k)$$

PGC-DGCNN按照節(jié)點之間的距離學習權重, 也就是增強距離遠的節(jié)點的作用. 具體地, 如果節(jié)點$v$到節(jié)點$u$的最短路長度為$j$, 則記$S_{v,u}^{(j)}=1$, 否則為0.

另外, 還有一種形式的空域GNN, 也就是我們所熟知的消息傳遞. 消息傳遞可以解釋成信息可以從節(jié)點沿著邊進行傳遞, 一般通常來講有固定的$K$步迭代, 這樣可以讓信息傳遞的更遠, 也就是有更大的感受野. 可以用如下公式表示:

然而, 對于graph-level的任務, 傳統的消息傳遞無法區(qū)分不同的圖結構. 為此, GIN通過調節(jié)中心節(jié)點的權重, 這樣就區(qū)分了中心節(jié)點和鄰居節(jié)點, 如下所示:

此外, 對于一個節(jié)點的鄰居節(jié)點, 不同鄰居的重要性也許是不同的, 因此GAT提出了圖注意力機制, 將聚合時鄰居節(jié)點的權重變成learnable的參數:

其中

$${\alpha }_{vu}^{(k)}=softmax(g(a^T[W^{(k)}{h}_v^{(k?1)}||W^{(k)}{h}_u^{(k?1)}]))$$

圖池化層, 圖自編碼器待更新…文章來源地址http://www.zghlxwxcb.cn/news/detail-674898.html

到了這里，關于[論文閱讀筆記25]A Comprehensive Survey on Graph Neural Networks的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！