今天給大家介紹的是Twitter研究團隊發(fā)表的一篇論文，該研究針對大規(guī)模圖神經(jīng)網(wǎng)絡(luò)訓(xùn)練的問題，提出的一種新的結(jié)構(gòu)更加簡單的模型——SIGN，這種模型的提出使得計算復(fù)雜度大大降低，能夠有效地處理大規(guī)模圖結(jié)構(gòu)，在多個開放的數(shù)據(jù)集上與主流的模型進行評估對比，SIGN更具有競爭優(yōu)勢。

在圖上進行的深度學(xué)習(xí)，也稱為幾何深度學(xué)習(xí)(GDL)或者圖表示學(xué)習(xí)(GRL)，在短短幾年的時間就從最初的籍籍無名發(fā)展成為機器學(xué)習(xí)最突出的領(lǐng)域之一。圖深度學(xué)習(xí)模型在各種不同的領(lǐng)域都非常成功，其中包括社交網(wǎng)絡(luò)鏈路預(yù)測、社交媒體虛假新聞預(yù)測、人物交互、粒子物理、藥物重定位、發(fā)現(xiàn)抗癌食品等。但是通常越簡單的結(jié)構(gòu)在許多應(yīng)用中越能發(fā)揮重要作用，特別是圖卷積網(wǎng)絡(luò)(GCN)。圖卷積網(wǎng)絡(luò)旨在將CNN推廣到圖結(jié)構(gòu)數(shù)據(jù)中，目前已經(jīng)在圖上開發(fā)了很多類似卷積運算的模型，例如第一代圖卷積網(wǎng)絡(luò)模型-頻譜圖卷積神經(jīng)網(wǎng)絡(luò)(Spectral graph CNNs)，基于切比雪夫多項式的ChebNet等。而目前的研究主要集中在小規(guī)模數(shù)據(jù)集上，對于能夠擴展到例如Facebook、Twitter等大規(guī)模社交網(wǎng)絡(luò)圖上的模型研究相對較少。解決大規(guī)模數(shù)據(jù)集已經(jīng)成為GNN廣泛應(yīng)用的一個主要挑戰(zhàn)。對于普通的神經(jīng)網(wǎng)絡(luò)而言，損失函數(shù)通常都能夠拆分到每一個觀測樣本上面，實現(xiàn)并行計算，而GNN每一個節(jié)點的損失都依賴于其他節(jié)點的信息，并且節(jié)點鄰居的數(shù)量往往是隨度數(shù)的增加呈現(xiàn)指數(shù)級增長的，從而導(dǎo)致計算量大和存儲困難等缺點。目前是通過圖采樣的方法來降低訓(xùn)練GNN的成本，譬如GraphSAGE、ClusterGCN和GraphSAINT等，但是圖采樣技術(shù)會引起損失。

在這篇文章中，作者提出了一種新的可推廣至大規(guī)模圖結(jié)構(gòu)的模型——SIGN(Scalable Inception Graph Neural Networks)，并且這個模型在設(shè)置不同值的情況下還能擴展為GCN、S-GCN、ChebNet等模型。這種思想受到Inception網(wǎng)絡(luò)的啟發(fā)，預(yù)先設(shè)置不同大小的卷積核，可以很快地進行訓(xùn)練和推理。盡管這種新型結(jié)構(gòu)簡單，但是在大規(guī)模圖數(shù)據(jù)集上不僅可與目前性能最佳的模型相媲美，而且顯著加快了訓(xùn)練速度。

（1）符號說明

將一個無向有權(quán)圖定義為，其中W為n*n的鄰接矩陣（對稱矩陣），為度矩陣，表示每個節(jié)點的度數(shù)之和(對角陣)，并且假設(shè)每個節(jié)點具有d維的特征，X為包含所有節(jié)點特征向量的矩陣（n*d）。使用歸一化的拉普拉斯矩陣：（Symmetric normalized Laplacian）[使用拉普拉斯矩陣的原因之一是其為半正定矩陣，為特征分解做準(zhǔn)備]。而每一個節(jié)點的拉普拉斯量可以表示為以下的局部加權(quán)平均值：

這里可以參考拉普拉斯算子和拉普拉斯矩陣的關(guān)系，拉普拉斯算子計算了周圍點與中心點的梯度差，可以計算一個點到它所有自由度上微小擾動的增益，則通過圖來表示就是任意一個節(jié)點i變化到節(jié)點j所帶來的增益，并將這種增益進行歸一化。接下來對拉普拉斯矩陣進行譜分解，，很明顯為正交的特征向量，對角陣為特征值。這里將特征向量視為傅里葉變換的基（因為這里的特征向量是n個線性無關(guān)的正交向量），那么圖上的傅里葉變換可表示為，而利用卷積實現(xiàn)類比，將卷積運算推廣到圖上可得到如下表示：

其中為Hadamard product（哈達馬積），對于兩個維度相同的向量、矩陣、張量進行對應(yīng)位置的逐元素乘積運算。

（2）圖卷積的發(fā)展

Spectral graphCNNs：簡單粗暴地將圖上的傅里葉變換變成卷積核，存在的弊端（1）在進行前向傳播的時候，需要進行特征分解和矩陣乘積運算，達到

的復(fù)雜度（2）需要n個卷積核（3）卷積核不具有spatiallocalization（4）在圖上學(xué)習(xí)到的卷積核不具有擴展性。

ChebNet：將卷積核巧妙的設(shè)計成，其優(yōu)點在于（1）卷積核只有K個參數(shù)，一般K遠(yuǎn)小于n（2）在矩陣變換后，不需要進行特征分解，由于仍需要計算，復(fù)雜度仍為（3）卷積核具有很好的spatial localization。

GCN:改進的GCN卷積核為，在ChebNet中，K=1時整個公式可以簡化為，這樣會導(dǎo)致數(shù)值不穩(wěn)定和梯度爆炸/消失，所以加入歸一化項，是具有自環(huán)的圖的鄰接矩陣（相當(dāng)于加1）。

S-GCN：為節(jié)點分類任務(wù)而設(shè)計的，，在2019年，Wu等人提出具有大卷積核的模型實際上等效于具有多個小卷積核模型，將其改進為。

（3）圖采樣

傳統(tǒng)的圖卷積神經(jīng)網(wǎng)絡(luò)算法，如GCN、GAT、MoNet等在面對大型圖時都是無法使用的，Graph sampling（圖采樣）對應(yīng)規(guī)模較大的圖取得了一定的成功，Graphsampling主要分為Node-wise sampling（如GraphSAGE）、Layer-wise sampling和Graph-wise sampling（如目前的state-of-art方法GraphSAINT）。

首先SIGN并不是基于采樣的模型，因為采樣會產(chǎn)生誤差，而是從最近的兩個發(fā)現(xiàn)中獲得的靈感：（1）S-GCN模型雖然很簡單，但是很有效，并且與具有多個卷積層的模型有相似的效果。（2）GCN聚合機制具有簡單的卷積核，但是在精度上卻和基于更復(fù)雜聚合函數(shù)的模型相媲美。據(jù)此，SIGN模型如下所示：

其中，是一個固定的n*n維的傳播矩陣，這里可以理解為將ChebNet中拉普拉斯矩陣的變型中的假設(shè)為2，并進行修正，就得到B的表示。都是可以通過反向傳播學(xué)習(xí)到的參數(shù)，|是合并操作（concatenation），都是非線性函數(shù)，后者可以根據(jù)具體的任務(wù)而選擇，例如softmax或者sigmoid。因為可以提前計算，用分布式計算例如Apach Spark可以加快計算速度。上述公式和Inception模型很像，由參數(shù)r確定不同的大小的卷積核，特別的，r=0對應(yīng)于Inception中的1*1卷積（相當(dāng)于進行線性變換，起到降維的目的）。也正是因為這種類比，稱這種模型為SIGN。

更為巧妙的是，這個模型高度概括了ChebNet, GCN, and S-GCN這些特殊情況，譬如將激活函數(shù)設(shè)置為如下形式：

則只需改變公式中的一些值，就可以進行推廣。具體的值設(shè)置如下：

下表是SIGN模型和目前的主流算法在時間復(fù)雜度上的比較：

作者先在四個大型公開數(shù)據(jù)集進行實驗：Reddit，F(xiàn)lickr，Yelp和PPI。在Reddit和Flickr數(shù)據(jù)集上研究節(jié)點多分類問題：前者的任務(wù)是根據(jù)用戶評論預(yù)測在線帖子的社區(qū)；Flickr是基于在線圖像的描述和共同屬性對圖像進行分類。Yelp和PPI是多標(biāo)簽分類問題：前者的目的是根據(jù)客戶評論來預(yù)測業(yè)務(wù)屬性，而后者的任務(wù)則是從人體組織蛋白的相互作用中預(yù)測蛋白質(zhì)功能。具體的數(shù)據(jù)集如下表所示：

作者將SIGN和GCN，F(xiàn)astGCN，Stochastic-GCN，AS-GCN，GraphSAGE等七種方法進行了比較。下表是在四個大型數(shù)據(jù)集上比較的結(jié)果：

這里在10次迭代中計算出的F1得分平均值和標(biāo)準(zhǔn)差。能夠看出在Reddit上SIGN具有最先進的性能，同時在其他數(shù)據(jù)集上也始終保持競爭優(yōu)勢。

下表是SIGN模型和目前的主流算法在Reddit數(shù)據(jù)集上訓(xùn)練時間的比較

盡管在預(yù)處理階段它比GraphSAINT稍慢，但SIGN花費的時間只是一小部分，比GraphSAINT和GraphSAGE高出兩個數(shù)量級。整個程序是在Pytorch中進行的，但GraphSAINT3和ClusterGCN4的實現(xiàn)是在Tensorflow中的，是比PyTorch快六倍的并且GraphSAINT的預(yù)處理是并行的，但是作者的不是。

其次盡管作者的目標(biāo)是大型圖，也嘗試了較小但優(yōu)良的轉(zhuǎn)導(dǎo)數(shù)據(jù)集，以將SIGN與傳統(tǒng)GNN方法進行比較。比較結(jié)果如下表所示：

試驗結(jié)果表明SIGN在較小的數(shù)據(jù)集上也具有競爭力，其性能優(yōu)于經(jīng)典方法，并且與當(dāng)前的最新方法（DIGL）接近。

SIGN的特點在于模型的簡單性、高效性、適合大規(guī)模圖結(jié)構(gòu)。因此，SIGN非常適合于工業(yè)化的大型系統(tǒng)。這種模型在通用圖學(xué)習(xí)基準(zhǔn)上獲得了競爭性結(jié)果，同時與其他方法相比，其訓(xùn)練速度明顯加快，推理速度提高了兩個數(shù)量級，同時適用于轉(zhuǎn)導(dǎo)學(xué)習(xí)和歸納學(xué)習(xí)，而且都取得了較大的進步。

https:///abs/2004.11198