Semi-Supervised Classification with Graph Convolutional Networks

1、四個(gè)問(wèn)題

要解決什么問(wèn)題？

• 半監(jiān)督任務(wù)。給定一個(gè)圖，其中一部節(jié)點(diǎn)已知標(biāo)簽，剩下的未知，要對(duì)整個(gè)圖上的節(jié)點(diǎn)進(jìn)行分類(lèi)。

用了什么方法解決？

• 提出了一種卷積神經(jīng)網(wǎng)絡(luò)的變種，即提出了一種新的圖卷積方法。
• 使用譜圖卷積（spectral graph convolution）的局部一階近似，來(lái)確定卷積結(jié)構(gòu)。
• 所提出的的網(wǎng)絡(luò)可以學(xué)習(xí)圖上局部結(jié)構(gòu)的特征，并進(jìn)行編碼。

效果如何？

• 在引文網(wǎng)絡(luò)（citation network）和知識(shí)圖譜（knowledge graph）等的數(shù)據(jù)集上比其之前的方法效果更好。

還存在什么問(wèn)題？

• 最大的問(wèn)題就是對(duì)GPU顯存的占用較大，要使用較大規(guī)模的圖來(lái)訓(xùn)練網(wǎng)絡(luò)只能用CPU替代。
• 文中的模型只是為無(wú)向圖設(shè)計(jì)的，并不支持對(duì)邊特征的提取。盡管能夠?qū)⒁粋€(gè)有向圖看做一個(gè)無(wú)向加權(quán)聯(lián)合圖，但這個(gè)模型對(duì)于有向圖的支持能力還是有限。

2、論文概述

1、簡(jiǎn)介

• 使用神經(jīng)網(wǎng)絡(luò)$f(X,A)$對(duì)圖的結(jié)構(gòu)進(jìn)行編碼，對(duì)所有帶標(biāo)簽的節(jié)點(diǎn)進(jìn)行有監(jiān)督訓(xùn)練。
• $X$是輸入數(shù)據(jù)，$A$是圖鄰接矩陣。
• 在圖的鄰接矩陣上調(diào)整$f(?)$能讓模型從監(jiān)督損失$L_0$。

2、圖上的快速近似卷積

• 圖卷積的前向傳播公式：

$$H^{(l+1)}=\sigma ({\tilde{D}}^{?\frac{1}{2}}\tilde{A}{\tilde{D}}^{?\frac{1}{2}}{H}^{(l)}{W}^{(l)})\text{\hspace{1em}(1)}$$

• $ \tilde{A} = A + I_N $ 是無(wú)向圖$G$的自環(huán)鄰接矩陣。
• $I_N$是單位矩陣。
• $ \tilde{D}{ii} = \sum_j \tilde{A}{ij} $ 是$\tilde{A}$的度矩陣。
• $W^{(l)}$是可訓(xùn)練的權(quán)重矩陣，即網(wǎng)絡(luò)的參數(shù)。
• $\sigma (?)$是激活函數(shù)，比如ReLU。
• $H^{(l)}\in {\mathbb{R}}^{N\times D}$是第$l$層的激活矩陣，即網(wǎng)絡(luò)的輸出。$H^{(0)}=X$，第一層為輸入。

2、譜圖卷積

2.1、原始GCN

• 將圖卷積通過(guò)傅里葉變換拓展到圖的頻域中。
• 對(duì)于一個(gè)輸入信號(hào)$x\in {\mathbb{R}}^N$，在傅里葉域中取一個(gè)$\theta \in {\mathbb{R}}^N$為參數(shù)的濾波器$g_{\theta }=diag(\theta )$：
• $$g_{\theta }?x=U{g}_{\theta }{U}^{?}x\text{\hspace{1em}(2)}$$
  • $U$是圖的拉普拉斯矩陣$L$的特征向量矩陣。
  • 拉普拉斯矩陣：$L=I_N?D^{?\frac{1}{2}}A{D}^{?\frac{1}{2}}=U\Lambda U^T$。
    • $\Lambda$是拉普拉斯矩陣$L$的特征值組成的對(duì)角矩陣。
    • $U^{T}x$就是圖上的傅里葉變換。
  • 也可以將$g_{\theta }$看成是拉普拉斯矩陣$L$的一系列特征值組成的對(duì)角矩陣$g_{\theta }(\Lambda )$。
  • 公式(2)中做的事就是，借助傅里葉變換，將原始信號(hào)$x$變換到頻域，在頻域乘上一個(gè)信號(hào)，再做傅里葉逆變換還原到空域。由傅里葉變換的特性有，在頻域相乘相當(dāng)于空域卷積，這樣就回避了空域上對(duì)不確定結(jié)構(gòu)的圖進(jìn)行卷積的問(wèn)題。
• 這是最原始的GCN，但是這套方法的缺點(diǎn)就是計(jì)算非常復(fù)雜，每次需要對(duì)矩陣進(jìn)行分解，如果圖的規(guī)模非常大，這會(huì)帶來(lái)巨大的計(jì)算開(kāi)銷(xiāo)。

2.2、加速版本的GCN

• 為了減少計(jì)算量，有人提出一個(gè)特殊的卷積核設(shè)計(jì)方法，即：將$g_{\theta }(\Lambda )$用切比雪夫多項(xiàng)式進(jìn)行$K$階逼近。
• 切比雪夫多項(xiàng)式：
  • $T_0(x)=1$
  • $T_1(x)=x$
  • $T_k(x)=2x{T}_{k?1}(x)?T_{k?1}(x)$
• 改進(jìn)的卷積核：
  • $$g_{{\theta }^{\prime }}(\Lambda )\approx \sum _{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{\Lambda })\text{\hspace{1em}(3)}$$
    • $\tilde{\Lambda }=\frac{2}{{\lambda }_{\max }}\Lambda ?I_N$。${\lambda }_{max}$是拉普拉斯矩陣$L$中最大的特征值。
    • ${\theta }^{\prime }\in {\mathbb{R}}^K$是切比雪夫多項(xiàng)式的系數(shù)。
• 將該卷積核代入圖卷積的公式：
  • $$g_{{\theta }^{\prime }}?x\approx \sum _{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{L})x\text{\hspace{1em}(4)}$$
    • $\tilde{L}=\frac{2}{{\lambda }_{\max }}L?I_N$。
    • 這個(gè)公式為拉普拉斯算子的$K$階切比雪夫多項(xiàng)式形式，即它受到距離中央節(jié)點(diǎn)$K$步以?xún)?nèi)的節(jié)點(diǎn)影響。
• 這里的加速版本的GCN，將參數(shù)減少到了$K$個(gè)，并且不再需要對(duì)拉普拉斯矩陣做特征分解，直接使用即可。

2.3、線(xiàn)性模型

• $K=1$時(shí)，模型有兩個(gè)參數(shù)，GCN公式：
• $$g_{{\theta }^{\prime }}?x\approx \sum _{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{L})x\text{\hspace{1em}(4)}$$
• 這里的公式(4)就對(duì)應(yīng)一個(gè)GCN層。
• 作者在論文中提到，通過(guò)使用這種形式的GCN，我們可以緩解模型在圖的局部結(jié)構(gòu)上的過(guò)擬合。此外，很大程度上減小了計(jì)算開(kāi)銷(xiāo)，使得我們可以堆疊多個(gè)GCN來(lái)獲得一個(gè)更深的模型，提取特征。
• 近似地認(rèn)為${\lambda }_{max}\approx 2$，公式(5)可以簡(jiǎn)化為下式：
• $$g_{{\theta }^{\prime }}?x\approx {\theta }_0^{\prime }x+{\theta }_1^{\prime }\left(L?I_N\right)x={\theta }_0^{\prime }x?{\theta }_1^{\prime }{D}^{?\frac{1}{2}}A{D}^{?\frac{1}{2}}x\text{\hspace{1em}(5)}$$
  • 這里有兩個(gè)自由參數(shù)：${\theta }_0^{\prime }$和${\theta }_1^{\prime }$。濾波器的參數(shù)在整個(gè)圖上共享。
  • 通過(guò)連續(xù)堆疊這種形式的濾波器，可以作用到卷積節(jié)點(diǎn)的$K$階領(lǐng)域上，其中$K$是卷積層的個(gè)數(shù)。
• 進(jìn)一步簡(jiǎn)化公式(5)中的模型，公式如下：
• $$g_{\theta }?x\approx \theta \left(I_N+D^{?\frac{1}{2}}A{D}^{?\frac{1}{2}}\right)x\text{\hspace{1em}(6)}$$
  • 這里令$\theta ={\theta }_0^{\prime }=?{\theta }_1^{\prime }$，將公式(5)中的兩個(gè)參數(shù)都替換成了$\theta$。
  • 但是，這里的$I_N+D^{?\frac{1}{2}}A{D}^{?\frac{1}{2}}$的特征值范圍為$[0,2]$，這可能會(huì)導(dǎo)致數(shù)值不穩(wěn)定和梯度消失/爆炸。所以還需要增加一步歸一化操作。
  • 歸一化：
    • $$I_N+D^{?\frac{1}{2}}A{D}^{?\frac{1}{2}}\to {\tilde{D}}^{?\frac{1}{2}}\tilde{A}{\tilde{D}}^{?\frac{1}{2}}$$
    • $$\tilde{A}=A+I_N$$
    • $${\tilde{D}}_{ii}=\sum _j{\tilde{A}}_{ij}$$
• 現(xiàn)在可以將卷積操作推廣到信號(hào)$X\in {\mathbb{R}}^{C\times F}$，輸入通道數(shù)為$C$，有$F$個(gè)濾波器。推廣的圖卷積形式如下：
• $$Z={\tilde{D}}^{?\frac{1}{2}}\tilde{A}{\tilde{D}}^{?\frac{1}{2}}X\Theta \text{\hspace{1em}(7)}$$
  • $\Theta \in {\mathbb{R}}^{C\times F}$是濾波器的參數(shù)矩陣。
  • $Z\in {\mathbb{R}}^{N\times F}$是卷積后輸出的信號(hào)矩陣。

3、半監(jiān)督節(jié)點(diǎn)分類(lèi)

• 回到半監(jiān)督任務(wù)上，前面介紹了優(yōu)化后的圖卷積結(jié)構(gòu)。在現(xiàn)在的半監(jiān)督任務(wù)中，作者希望通過(guò)已知的數(shù)據(jù)$X$和鄰接矩陣$A$來(lái)訓(xùn)練圖卷積網(wǎng)絡(luò)$f(X,A)$。 作者認(rèn)為，在鄰接矩陣中包含了一些$X$中沒(méi)有的隱含的圖的結(jié)構(gòu)信息，而我們可以利用這些信息進(jìn)行推理。
• 下圖中，左圖是一個(gè)GCN網(wǎng)絡(luò)示意圖，輸入有$C$維特征，輸出有$F$維特征，中間有若干隱藏層，$X$是訓(xùn)練數(shù)據(jù)，$Y$是標(biāo)簽。右圖是使用一個(gè)兩層GCN在Cora數(shù)據(jù)集上（只是用了5%的標(biāo)簽）得到的可視化結(jié)果。

3.1、實(shí)例

• 在預(yù)處理中，首先計(jì)算好：$\hat{A}={\tilde{D}}^{?\frac{1}{2}}\tilde{A}{\tilde{D}}^{?\frac{1}{2}}$。
• 然后，前向傳播的模型可以寫(xiě)成下式：
• $$Z=f(X,A)=\mathrm{softmax}\left(\hat{A}\mathrm{ReLU}\left(\hat{A}X{W}^{(0)}\right)W^{(1)}\right)\text{\hspace{1em}(8)}$$
  • 這是一個(gè)很簡(jiǎn)單的兩層GCN。
  • $W^{(0)}\in {\mathbb{R}}^{C\times H}$是輸入到隱藏層的權(quán)重矩陣，隱藏層上的特征維度是$H$。
  • $W^{(1)}\in {\mathbb{R}}^{H\times F}$是隱藏層到輸出的權(quán)重矩陣。
  • $softmax$就不多說(shuō)了。
• 損失函數(shù)采用交叉熵，評(píng)估所有有標(biāo)簽的數(shù)據(jù)：
• $$\mathcal{L}=?\sum _{l\in {\mathcal{Y}}_L}\sum _{f=1}^F{Y}_{lf}\ln Z_{lf}\text{\hspace{1em}(9)}$$
• ${\mathcal{Y}}_L$為帶標(biāo)簽節(jié)點(diǎn)組成的集合。
• 訓(xùn)練：SGD，引入了BN和Dropout。

4、實(shí)驗(yàn)

• 數(shù)據(jù)集描述：
• 半監(jiān)督分類(lèi)準(zhǔn)確率：

3、參考資料

• Semi-Supervised Classification with Graph Convolutional Networks

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的论文笔记：Semi-Supervised Classification with Graph Convolutional Networks的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。