論文鏈接：
代碼鏈接：
.com//SGC
GCN在學(xué)習(xí)圖的表示方面已經(jīng)引起了廣泛的關(guān)注，應(yīng)用也非常廣泛。GCNs的靈感主要來(lái)自最近的一些深度學(xué)習(xí)方法，因此可能會(huì)繼承不必要的復(fù)雜度和冗余計(jì)算。文中通過(guò)反復(fù)消除GCN層之間的非線性并將得到的函數(shù)折疊成一個(gè)線性變換來(lái)減少GCNs的額外復(fù)雜度。并從理論上分析了得到的線性模型SGC，并證明了SGC相當(dāng)于一個(gè)固定的低通道濾波器和一個(gè)線性分類器。實(shí)驗(yàn)結(jié)果表明，這些簡(jiǎn)化不會(huì)對(duì)許多下游應(yīng)用的準(zhǔn)確性產(chǎn)生負(fù)面影響。此外python檢測(cè)網(wǎng)絡(luò)連通性，得到的SGC模型可擴(kuò)展到更大的數(shù)據(jù)集，并且比產(chǎn)生兩個(gè)數(shù)量級(jí)的加速。
1 相關(guān)介紹
1.1 Graph (SGC)提出的背景
傳統(tǒng)的機(jī)器學(xué)習(xí)方法的復(fù)雜度變化趨勢(shì)都是從簡(jiǎn)單到復(fù)雜。例如從線性到非線性MLP，從簡(jiǎn)單的線性圖片到CNN都是這個(gè)趨勢(shì)。GCN也是源于傳統(tǒng)的機(jī)器學(xué)習(xí)方法，繼承了這個(gè)復(fù)雜度的變化。此文的目的就是要把非線性的GCN轉(zhuǎn)化成一個(gè)簡(jiǎn)單的線性模型SGC，通過(guò)反復(fù)消除GCN層之間的非線性并將得到的函數(shù)折疊成一個(gè)線性變換來(lái)減少GCNs的額外復(fù)雜度。
SGC中的特征提取等價(jià)在每個(gè)特征的維度上應(yīng)用了單個(gè)固定的。
1.2 SGC效果
實(shí)驗(yàn)表明
2 Graph 簡(jiǎn)化的圖卷積
2.1 符號(hào)定義
數(shù)據(jù)集中只知道部分節(jié)點(diǎn)的標(biāo)簽，目標(biāo)是預(yù)測(cè)未知的節(jié)點(diǎn)的標(biāo)簽。
2.2 圖卷積網(wǎng)絡(luò)GCN
GCN vs MLP
GCNs和MLPs相似，都是通過(guò)多層網(wǎng)絡(luò)學(xué)習(xí)一個(gè)節(jié)點(diǎn)的特征向量Xi，然后再把這個(gè)學(xué)到的特征向量送入的一個(gè)線性分類器中進(jìn)行分類任務(wù)。一個(gè)k層GCN與k 層MLP在應(yīng)用于圖中每個(gè)節(jié)點(diǎn)的特征向量Xi是相同的，不同之處在于每個(gè)節(jié)點(diǎn)的隱藏表示在每一層的輸入時(shí)是取的它的鄰居的平均。
每個(gè)圖中的卷積層和節(jié)點(diǎn)表示都是使用三個(gè)策略來(lái)更新
特征傳播
GCN的特征傳播是區(qū)別MLP的，因?yàn)槊恳粚拥妮斎攵际枪?jié)點(diǎn)局部鄰居的平均值：
（2）
用一個(gè)簡(jiǎn)單的矩陣運(yùn)算來(lái)表示公式（2）的更新：
（3）
用公式（2）對(duì)所有節(jié)點(diǎn)進(jìn)行同時(shí)更新，得到了一個(gè)簡(jiǎn)單的稀疏矩陣乘法：
(4)
這一步平滑了沿著圖的邊的局部隱藏表示，并最終支持在局部連接的節(jié)點(diǎn)之間進(jìn)行類似的預(yù)測(cè)。
and
在局部平滑之后，一個(gè)GCN層就等于一個(gè)標(biāo)準(zhǔn)的MLP。每一個(gè)層對(duì)應(yīng)一個(gè)可學(xué)習(xí)的權(quán)重矩陣
python檢測(cè)網(wǎng)絡(luò)連通性，所以平滑處理了的隱藏特征表示是線性轉(zhuǎn)換的（后面乘一個(gè)參數(shù)矩陣是線性的）。最后在逐節(jié)點(diǎn)應(yīng)用一個(gè)非線性激活函數(shù)，例如ReLU就可以得到輸出的特征表示
(5)
分類器
對(duì)于節(jié)點(diǎn)分類任務(wù)，最后一層和MLP相似，都是使用一個(gè)分類器預(yù)測(cè)節(jié)點(diǎn)的標(biāo)簽，一個(gè)K KK層的GCN的所有節(jié)點(diǎn)的類別預(yù)測(cè)可以寫作：
(6)
2.3 簡(jiǎn)化的圖卷積SGC
在傳統(tǒng)的MLP中，層數(shù)變深加強(qiáng)了網(wǎng)絡(luò)的表達(dá)能力，因?yàn)樗试S創(chuàng)建特征的層次結(jié)構(gòu)，例如，第二層的特征構(gòu)建在第一層特征的基礎(chǔ)上。在GCNs中，每一層都有一個(gè)重要的函數(shù):在每一層中，隱藏的表示在1跳距離的鄰居之間求平均值。這意味著在k kk層之后，一個(gè)節(jié)點(diǎn)從圖中所有k kk跳的節(jié)點(diǎn)處獲得特征信息。這種效果類似于卷積神經(jīng)網(wǎng)絡(luò)，深度增加了內(nèi)部特征的感受野。雖然卷積網(wǎng)絡(luò)可以在層數(shù)加深時(shí)提升性能(Deep with depth， 2016)，但通常MLP的深度只限于為3至4層。
線性化
假設(shè)GCN層之間的非線性不是最關(guān)鍵的，最關(guān)鍵的是局部鄰居的平均聚合操作。因此，考慮刪除每層之間的非線性轉(zhuǎn)換函數(shù)（如ReLU），只保留最終的(以獲得概率輸出)。得到的模型是線性的
(7)
簡(jiǎn)化如下
(8)
這個(gè)簡(jiǎn)化的版本就叫做 Graph (SGC)。
邏輯回歸
公式（8）給了SGC的一個(gè)自然直觀的解釋：SGC由兩部分組成
一個(gè)固定的（沒(méi)有參數(shù)，-free）的特征提取器（或平滑器 ）
特征提取器后是一個(gè)線性邏輯回歸分類器
可以看出，由于計(jì)算不需要權(quán)值，因此可以把這部分計(jì)算作為特征的預(yù)處理步驟，整個(gè)模型的訓(xùn)練可以直接簡(jiǎn)化為對(duì)預(yù)處理特征的多類邏輯回歸。
優(yōu)化細(xì)節(jié)
邏輯回歸的訓(xùn)練是一個(gè)凸優(yōu)化問(wèn)題，可以用任何有效的二階方法或隨機(jī)梯度下降法進(jìn)行執(zhí)行(Large-scale with ，2010)。在圖連通模式足夠稀疏的情況下，SGD可以很自然地運(yùn)用在非常大的圖上，SGC的訓(xùn)練比GCN快得多。
3 譜分析
文中從圖卷積的角度來(lái)研究SGC，并證明了SGC在圖譜域上對(duì)于應(yīng)一個(gè)固定的濾波器。此外，還證明了在原始圖上添加自循環(huán)，即 trick，可以有效地縮小底層圖的譜。在這個(gè)縮放的譜域上，SGC充當(dāng)一個(gè)低通濾波器，在圖上生成平滑的特征。因此，鄰居節(jié)點(diǎn)傾向于共享相似的表示，從而實(shí)現(xiàn)預(yù)測(cè)。
3.1 在圖上的初步做法
經(jīng)過(guò)傅里葉變換的信號(hào)x和濾波器g的GCN卷積操作為
(11)
推導(dǎo)過(guò)程可以看GCN原始論文：Semi- with Graph 用圖卷積進(jìn)行半監(jiān)督分類
最后，通過(guò)將卷積推廣到d dd維的通道輸入中的多個(gè)濾波器上，并在每一層之間用非線性激活函數(shù)的分層模型，就得到了如公式(5)所定義的GCN傳播規(guī)則
(5)
3.2 SGC and Low-Pass 簡(jiǎn)化的圖卷積和低通濾波器
定理1
對(duì)于一個(gè)簡(jiǎn)單，沒(méi)有孤立節(jié)點(diǎn)的無(wú)向圖。令
分別是對(duì)稱歸一化的拉普拉斯矩陣
的最小和最大的特征值。
的最小和最大的特征值。則有
(12)
關(guān)于定理1的證明，可參考文中提供的附錄部分。
從定理1可以看出，當(dāng)γ>0 \gamma>0γ>0時(shí)，相當(dāng)于圖中添加了自循環(huán)，則歸一化的拉普拉斯矩陣的最大特征值會(huì)變小。
圖2描述了在Cora數(shù)據(jù)集上使用的三種情況下特征值（頻率）的變化和濾波器系數(shù)（譜系數(shù)）的變化關(guān)系
4 相關(guān)工作
4.1 圖神經(jīng)網(wǎng)絡(luò)
4.2 其他在圖上的工作
在圖上的方法可分為兩類：graph 和graph 。
graph
5 實(shí)驗(yàn)結(jié)果
5.1 &
圖3是在和數(shù)據(jù)集上的效率對(duì)比圖
顯然，SGC是效率最高的
SGC中是預(yù)先計(jì)算的，SGC訓(xùn)練的時(shí)候只需要學(xué)習(xí)一個(gè)權(quán)重矩陣Θ，減少了內(nèi)存的使用。
由于S通常是稀疏的，而K通常比較小，因此，可以用稀疏稠密矩陣乘法進(jìn)行計(jì)算
無(wú)法在上對(duì)GaAN和DGI的訓(xùn)練時(shí)間進(jìn)行基準(zhǔn)測(cè)試，因?yàn)閷?shí)驗(yàn)沒(méi)有發(fā)布
GPU： GTX 1080 Ti
在大圖上由于內(nèi)存要求不能進(jìn)行GCN的訓(xùn)練。和等方法使用采樣的方法減少鄰居數(shù)量來(lái)處理這個(gè)問(wèn)題。Deep Graph （ICLR，2019）通過(guò)限制模型的size來(lái)解決這個(gè)問(wèn)題
SGC訓(xùn)練的時(shí)候比使用快速采樣的快兩個(gè)數(shù)量級(jí)，并且性能幾乎沒(méi)有損失
5.2 下游任務(wù)
使用5個(gè)下游任務(wù)來(lái)研究SGC的適應(yīng)性：
Text
Semi- user
Zero-shot image
Graph
圖分類要求模型使用圖結(jié)構(gòu)對(duì)圖進(jìn)行分類。
（How are graph ?，ICLR 2019）從理論上證明了GCNs不足以區(qū)分特定的圖結(jié)構(gòu)，并證明了GIN更具表現(xiàn)力，在各種圖分類數(shù)據(jù)集上獲得了 state-of-the-art的結(jié)果。
將DCGCN中的GCN替換為SGC，分別獲得NCI1和數(shù)據(jù)集上的71.0%和76.2%，這與GCN相當(dāng)，但遠(yuǎn)遠(yuǎn)落后于GIN。
在QM8量子化學(xué)數(shù)據(jù)集上，更高級(jí)的和LNet在QM8上得到0.01MAE，遠(yuǎn)遠(yuǎn)超過(guò)SGC的0.03 MAE。