論文 | 圖網(wǎng)絡(luò)理論之Deeper Insights into GCN

新學(xué)期！VTS三只小豬繼續(xù)沖鴨裕坊！

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

AAAI2018

*文章總體思路：1. 證明GCN實(shí)際上是一種拉普拉斯平滑 ——> 所以深層GCN會造成過度平滑的問題包竹，使結(jié)點(diǎn)特征變得不可區(qū)分 ——> 但淺層GCN也有問題，在半監(jiān)督學(xué)習(xí)中標(biāo)簽很少的情況下無法將標(biāo)簽傳播到整個(gè)圖中 ——> 2. 提出協(xié)同訓(xùn)練和自訓(xùn)練

摘要

本文對GCN模型進(jìn)行了深入的研究碍庵，并解決了它的基本局限性：

1. 證明了GCN模型的圖卷積實(shí)際上是拉普拉斯平滑（Laplacian smoothing）的一種特殊形式，這是GCN工作的關(guān)鍵原因悟狱，但它也帶來了由過多卷積層導(dǎo)致的過度平滑（over-smoothing）的潛在問題静浴。

2. 為了克服淺層結(jié)構(gòu)的GCN模型的局限性，本文提出了協(xié)同訓(xùn)練（co-training）和自訓(xùn)練（self-training）兩種方法來訓(xùn)練GCN挤渐。

本文的方法在學(xué)習(xí)中顯著提高了GCN苹享，只使用很少的標(biāo)簽，并且免除了它們需要額外的標(biāo)簽來進(jìn)行驗(yàn)證浴麻。實(shí)驗(yàn)做的不錯(cuò)得问！

1. 文章簡介

GCN模型過深存在的問題 ? ?本文證明了GCN模型的圖卷積只是拉普拉斯平滑的一種特殊形式，它混合了節(jié)點(diǎn)及其鄰近點(diǎn)的特征软免。平滑操作使同一簇中的結(jié)點(diǎn)特征相似宫纬，從而大大簡化了分類任務(wù)，這是GCN工作如此出色的關(guān)鍵原因膏萧。然而漓骚，它也帶來了過度平滑的潛在擔(dān)憂蝌衔。如果一個(gè)GCN有很多卷積層，輸出特征可能會過度平滑蝌蹂，不同簇的結(jié)點(diǎn)可能變得不可區(qū)分噩斟。在只有幾個(gè)卷積層的小數(shù)據(jù)集上，特征混合發(fā)生得很快孤个，如圖2所示剃允。此外，向GCN添加更多的層將使其更難訓(xùn)練齐鲤。

圖2?空手道俱樂部網(wǎng)絡(luò)的結(jié)點(diǎn)嵌入（1斥废、2、3佳遂、4营袜、5層GCN）

GCN模型過淺存在的問題? ? 淺層GCN模型（如Kipf和Welling 2017中使用的兩層GCN）有其自身的局限性。除了需要許多額外的標(biāo)簽來進(jìn)行驗(yàn)證外丑罪，它還受到卷積核的局部特性的影響荚板。當(dāng)只給出很少的標(biāo)簽時(shí)，一個(gè)較淺的GCN就不能有效地將標(biāo)簽傳播到整個(gè)數(shù)據(jù)圖中吩屹。如圖1所示跪另，隨著訓(xùn)練規(guī)模（*有標(biāo)簽樣本占比）的縮小，GCN的性能會迅速下降煤搜，即使是有500個(gè)附加標(biāo)簽進(jìn)行驗(yàn)證的GCN免绿。

圖1 四種模型在Cora數(shù)據(jù)集上的性能比較

為了克服這一局限，充分發(fā)揮GCN模型的潛能擦盾，本文提出了一種協(xié)同訓(xùn)練（co-training）方法和一種自訓(xùn)練（self-training）方法來訓(xùn)練GCN嘲驾。通過將一個(gè)GCN與一個(gè)隨機(jī)游走模型（random walk）進(jìn)行聯(lián)合訓(xùn)練，后者可以在探索全局圖拓?fù)渲醒a(bǔ)充前者迹卢。通過對GCN的自訓(xùn)練辽故，可以利用其特征提取能力來克服其局限性。將協(xié)同訓(xùn)練和自訓(xùn)練方法結(jié)合起來腐碱，可以大大改進(jìn)具有極少標(biāo)簽的半監(jiān)督學(xué)習(xí)的GCN模型誊垢，并且免除了它需要額外的標(biāo)簽數(shù)據(jù)進(jìn)行驗(yàn)證的要求。如圖1所示症见，本文方法大幅度完勝GCN喂走。

簡而言之，本文的主要?jiǎng)?chuàng)新點(diǎn)是：1）對半監(jiān)督學(xué)習(xí)的GCN模型提出了新的見解和分析谋作；2）提出了改進(jìn)半監(jiān)督學(xué)習(xí)的GCN模型的解決方案芋肠。

3. 分析

盡管GCN模型具有良好的學(xué)習(xí)性能，但其半監(jiān)督學(xué)習(xí)的機(jī)制尚不明確遵蚜。本節(jié)將更詳細(xì)地介紹GCN模型业栅，分析其工作的原因秒咐，并指出其局限性。

3.1 GCN為何有效

*本節(jié)證明圖卷積是一種特殊形式的拉普拉斯平滑碘裕。

拉普拉斯平滑 ? ?考慮一層GCN携取，包括兩步：

1）對X進(jìn)行圖卷積生成新的特征矩陣Y：

$Y=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X$ ? ? (8)

2）將新的特征矩陣Y輸入全卷積層。顯然帮孔，圖卷積是關(guān)鍵雷滋。

那就讓我們好好看看圖卷積。假設(shè)每個(gè)結(jié)點(diǎn)都加上自循環(huán)文兢，則新圖的鄰接矩陣為 $\tilde{A} =A+I$ .輸入特征每個(gè)通道上的拉普拉斯平滑定義為：

$\hat{\textbf{y}} _i=(1-\gamma)\textbf{x}_i+\gamma\sum_j\frac{\tilde{a}_{ij} }{d_i}\textbf{x}_j$ , ? (for? $1\leq i\leq n$ ). ? ?(9)

其中 $0<\gamma\leq1$ 是控制當(dāng)前結(jié)點(diǎn)特征與其相鄰特征之間權(quán)重的參數(shù)晤斩。將拉普拉斯平滑寫成矩陣形式：

$\hat{Y} =X-\gamma\tilde{D}^{-1}\tilde{L} X=(I-\gamma\tilde{D}^{-1}\tilde{L} )X$ ? ? (10)

其中， $\tilde{L}= \tilde{D}-\tilde{A}$ . 令 $\gamma=1$ 姆坚，則有 $\hat{Y} =\tilde{D}^{-1}\tilde{A} X$ 澳泵，這是拉普拉斯平滑的標(biāo)準(zhǔn)形式。

若將歸一化拉普拉斯 $\tilde{D}^{-1}\tilde{L}$ 替換為對稱歸一化拉普拉斯 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 兼呵，令 $\gamma=1$ 兔辅，則 $Y=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X$ ，也就是式8中的圖卷積击喂。因此维苔，我們稱圖卷積是拉普拉斯平滑的一種特殊形式——對稱拉普拉斯平滑。注意懂昂，這里的平滑仍然包括當(dāng)前結(jié)點(diǎn)特征介时，因?yàn)槊總€(gè)結(jié)點(diǎn)都加上了自循環(huán)，是自己的鄰居結(jié)點(diǎn)凌彬。

拉普拉斯平滑將結(jié)點(diǎn)的新特征計(jì)算為其自身及其相鄰結(jié)點(diǎn)的加權(quán)平均值沸柔。由于同一簇中的結(jié)點(diǎn)往往是密集連接的，平滑處理使它們的特征相似铲敛，這使得后續(xù)的分類任務(wù)更加容易褐澎。如表1所示，僅應(yīng)用一次平滑就可以獲得巨大的性能增益原探。

多層結(jié)構(gòu) ? ?從表1也可以看出乱凿，2層FCN僅比1層FCN略有改善顽素，但2層GCN比1層GCN有較大幅度的改善咽弦。這是因?yàn)樵诘谝粚拥募せ钌显俅螒?yīng)用平滑，使得同一簇中結(jié)點(diǎn)的輸出特征更加相似胁出，從而進(jìn)一步簡化了分類任務(wù)型型。

表1 FCN和GCN比較

3.2 GCN何時(shí)失效

*本節(jié)證明深層圖卷積即過度平滑，會使結(jié)點(diǎn)特征收斂到相同的值全蝶。

一個(gè)GCN中應(yīng)該包括多少個(gè)卷積層闹蒜？當(dāng)然不是越多越好寺枉。一方面，多層GCN很難訓(xùn)練绷落。另一方面姥闪，重復(fù)應(yīng)用拉普拉斯平滑可能會混合來自不同簇的結(jié)點(diǎn)特征，使它們無法區(qū)分砌烁，如圖2所示筐喳。

下面將證明通過多次重復(fù)應(yīng)用拉普拉斯平滑，圖中每個(gè)連通分支內(nèi)的結(jié)點(diǎn)特征將收斂到相同的值函喉。對于對稱拉普拉斯平滑避归，它們將收斂到與結(jié)點(diǎn)度的平方根成比例。

基于上述定理管呵，過度平滑會使特征難以區(qū)分梳毙，影響分類精度，并且深層GCN會使得網(wǎng)絡(luò)難以訓(xùn)練捐下。然而由于圖卷積是一個(gè)局部濾波器——相鄰特征向量的線性組合账锹，淺層GCN不能充分地將標(biāo)簽信息傳播到只有幾個(gè)標(biāo)簽的整個(gè)圖中。如圖1所示蔑担，隨著訓(xùn)練規(guī)模的縮小牌废，GCN的性能（有或無驗(yàn)證）會迅速下降。事實(shí)上啤握，GCN的準(zhǔn)確度下降速度遠(yuǎn)遠(yuǎn)快于label propagation的準(zhǔn)確度鸟缕。由于label propagation只使用圖信息，而GCN同時(shí)使用結(jié)構(gòu)和結(jié)點(diǎn)特性排抬，因此它反映了GCN模型在探索全局圖結(jié)構(gòu)方面的不足懂从。

在（kipf和welling 2017）中，GCN模型的另一個(gè)問題是蹲蒲，它需要一個(gè)額外的驗(yàn)證集番甩，用于提前終止訓(xùn)練，這是使用驗(yàn)證集的預(yù)測精度進(jìn)行模型選擇届搁。如果我們在不使用驗(yàn)證集的情況下對訓(xùn)練數(shù)據(jù)進(jìn)行GCN優(yōu)化缘薛，則性能將顯著下降。如圖1所示卡睦，未經(jīng)驗(yàn)證的GCN的性能比經(jīng)驗(yàn)證的GCN明顯下降宴胧。在（kipf和welling 2017）中，作者使用了另外一組500個(gè)標(biāo)記數(shù)據(jù)進(jìn)行驗(yàn)證表锻，這遠(yuǎn)遠(yuǎn)超過了訓(xùn)練數(shù)據(jù)的總數(shù)恕齐。這當(dāng)然是不可取的，因?yàn)樗茐牧税氡O(jiān)督學(xué)習(xí)的目的瞬逊。此外显歧，它使得將GCN與其他方法進(jìn)行比較變得不公平仪或，因?yàn)閘abel propagation等其他方法可能根本不需要驗(yàn)證數(shù)據(jù)。

4. 方法

總結(jié)GCN模型的優(yōu)缺點(diǎn)士骤。優(yōu)點(diǎn)：1）圖卷積-拉普拉斯平滑有助于簡化分類問題范删；2）多層神經(jīng)網(wǎng)絡(luò)是一個(gè)強(qiáng)大的特征提取工具。缺點(diǎn)：1）圖卷積是一種局域?yàn)V波器拷肌，在標(biāo)簽數(shù)據(jù)較少的情況下性能不理想瓶逃；2）神經(jīng)網(wǎng)絡(luò)需要大量的標(biāo)簽數(shù)據(jù)進(jìn)行驗(yàn)證和模型選擇。

*本節(jié)提出的方法旨在解決淺層GCN在半監(jiān)督學(xué)習(xí)中標(biāo)簽很少的情況下無法將標(biāo)簽傳播到整個(gè)圖中的問題廓块，不依靠加深網(wǎng)絡(luò)的方法厢绝，而是依靠擴(kuò)大標(biāo)記數(shù)據(jù)的方法。

4.1 用隨機(jī)游走模型協(xié)同訓(xùn)練GCN

本文提出將隨機(jī)游走模型與GCN協(xié)同訓(xùn)練带猴，因?yàn)殡S機(jī)游走可以探索全局圖結(jié)構(gòu)昔汉，這是對GCN模型的補(bǔ)充。首先使用隨機(jī)游走模型來找到最有信心的結(jié)點(diǎn)——每個(gè)類的有標(biāo)簽結(jié)點(diǎn)的最近鄰點(diǎn)拴清，然后將它們添加到標(biāo)簽集以訓(xùn)練GCN靶病。與（kipf和welling 2017）不同，我們直接優(yōu)化了訓(xùn)練集中GCN的參數(shù)口予，無需額外的標(biāo)記數(shù)據(jù)進(jìn)行驗(yàn)證娄周。

我們選擇使用部分吸收（partially absorbing）隨機(jī)游走（Parwalks）作為我們的隨機(jī)游走模型。部分吸收隨機(jī)游走是一個(gè)二階馬爾可夫鏈沪停，在每個(gè)狀態(tài)下都有部分吸收煤辨。通過適當(dāng)?shù)奈赵O(shè)定，吸收概率可以很好地捕捉到全局圖結(jié)構(gòu)木张。重要的是众辨，通過求解一個(gè)簡單的線性系統(tǒng)，可以閉式計(jì)算吸收概率舷礼，并且可以通過隨機(jī)游走采樣或在結(jié)點(diǎn)中心圖的頂部放大來快速近似（鹃彻？）。

擴(kuò)展訓(xùn)練集的算法由算法1所示妻献。首先計(jì)算歸一化吸收概率矩陣 $P=(L+\alpha\Lambda)^{-1}$ ( $\Lambda$ 的選擇可能取決于數(shù)據(jù)).? $P_{i,j}$ 表示從結(jié)點(diǎn)i被結(jié)點(diǎn)j吸收的隨機(jī)游走概率蛛株，也就是i和j屬于同一種類的可能性。其次育拨，計(jì)算結(jié)點(diǎn)屬于k類的置信度谨履。將標(biāo)記的結(jié)點(diǎn)劃分為S1，S2至朗，…屉符，其中Sk表示k類的標(biāo)記數(shù)據(jù)集剧浸。對于每個(gè)種類k锹引，計(jì)算置信度向量 $\textbf{p}=\sum_{j\in S_k}P_{:,j}$ . 最后矗钟，找到t個(gè)最有信心的結(jié)點(diǎn)，并將它們添加到帶有標(biāo)簽k的訓(xùn)練集中嫌变，以訓(xùn)練GCN吨艇。

4.2 自訓(xùn)練GCN

另一種讓GCN看到更多訓(xùn)練樣本的方法是自訓(xùn)練GCN。具體來說腾啥，首先用給定的標(biāo)簽訓(xùn)練一個(gè)GCN东涡，然后通過比較SoftMax分?jǐn)?shù)，選出每個(gè)類中最有信心的預(yù)測倘待，并將它們添加到標(biāo)簽集疮跑。然后，繼續(xù)使用擴(kuò)展標(biāo)簽集對GCN進(jìn)行訓(xùn)練凸舵，使用預(yù)訓(xùn)練的GCN作為初始化祖娘。如算法2所示。

協(xié)同訓(xùn)練和自訓(xùn)練相結(jié)合 ? ?為了提高標(biāo)簽的多樣性并訓(xùn)練一個(gè)更強(qiáng)大的分類器啊奄，建議將協(xié)同訓(xùn)練和自訓(xùn)練相結(jié)合渐苏。具體來說，使用隨機(jī)游走和GCN本身發(fā)現(xiàn)的最有信心的預(yù)測來擴(kuò)展標(biāo)簽集菇夸，然后使用擴(kuò)展的標(biāo)簽集繼續(xù)訓(xùn)練GCN琼富，這種方法稱為“Union”。為了找到更準(zhǔn)確的標(biāo)簽添加到標(biāo)簽集庄新，建議添加隨機(jī)游走和GCN都發(fā)現(xiàn)的最有信心的預(yù)測鞠眉，這種方法稱為“Intersection”。

注意择诈，我們在擴(kuò)展標(biāo)簽集上優(yōu)化所有方法凡蚜，而不需要任何額外的驗(yàn)證數(shù)據(jù)。只要擴(kuò)展的標(biāo)簽集包含足夠的正確標(biāo)簽吭从，我們的方法就可以訓(xùn)練出一個(gè)良好的GCN分類器朝蜘。但訓(xùn)練一個(gè)GCN需要多少標(biāo)記數(shù)據(jù)呢？建設(shè)GCN層數(shù)為 $\tau$ 涩金，基礎(chǔ)圖的平均度為 $\hat3bxpo7s$ ,通過求解 $\hatwldcjmv ^{\tau}*\eta \approx n$ 來估計(jì)標(biāo)記數(shù)量 $\eta=|V_l|$ .這背后的基本原理是估計(jì)一個(gè)具有τ層的GCN需要多少標(biāo)簽來傳播它們以覆蓋整個(gè)圖谱醇。

5. 實(shí)驗(yàn)

本文在三個(gè)常用的引文網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)：citeseer、cora和pubmed步做。在每個(gè)數(shù)據(jù)集中副渴，文檔都由一袋字特征向量來描述，也就是說全度，一個(gè)0/1值的向量表示某個(gè)字的缺失/存在煮剧。文檔之間的引用鏈接由0/1值鄰接矩陣描述。用于測試的數(shù)據(jù)集由（Yang、Cohen和Salakhuttdinov勉盅，2016）和（Kipf和Welling佑颇，2017）的作者提供。

對于ParWalks草娜，設(shè)定 $\Lambda=I,\alpha=10^{-6}$ 挑胸，對于GCN，設(shè)定和(Kipf and Welling 2017)相同：a learning rate of?0.01,?200?maximum epochs,?0.5?dropout rate,?5?×?10^{?4} L2?regularization weight, 2 convolutional layers, and?16?hidden units, which are validated on Cora by Kipf and Welling.

6. 總結(jié)

了解深層神經(jīng)網(wǎng)絡(luò)對于實(shí)現(xiàn)其在實(shí)際應(yīng)用中的全部潛能至關(guān)重要宰闰。本文有助于理解GCN模型及其在半監(jiān)督分類中的應(yīng)用茬贵。我們的分析不僅揭示了GCN模型的機(jī)制和局限性，而且提出了克服其局限性的新解決方案移袍。在未來的工作中解藻，我們計(jì)劃開發(fā)新的卷積濾波器，它與深層結(jié)構(gòu)兼容葡盗，并利用先進(jìn)的深層學(xué)習(xí)技術(shù)來提高GCN在更多基于圖的應(yīng)用中的性能舆逃。

文章標(biāo)*處為全世界最乖巧的小豬注.