今天給大家介紹香港中文大學和新加坡國立大學一起在ICLR2020上發(fā)布的一篇論文，該論文針對實際使用中GNN在圖結(jié)構(gòu)數(shù)據(jù)中能夠獲得多少性能的問題，提出了兩種可以度量從圖中獲取的信息的數(shù)量和質(zhì)量的平滑度指標，以及一個使用上述平滑度指標的GNN框架CS-GNN。實驗顯示，在不同類型的圖上，對于特定任務(wù)而言，CS-GNN相比于現(xiàn)有的模型有更好的效果。
簡介
圖是很重要的數(shù)據(jù)結(jié)構(gòu)，它可以準確表達對象（節(jié)點）之間的各種關(guān)系（邊）。近些年來，國內(nèi)外研究人員對GNN在諸如節(jié)點分類和邊預測之類的任務(wù)上進行了廣泛的研究。長期的研究顯示，GNN通過利用圖結(jié)構(gòu)數(shù)據(jù)中的關(guān)系信息，在基準數(shù)據(jù)集上實現(xiàn)了對傳統(tǒng)方法的改進。它所產(chǎn)生的突破性結(jié)果促使人們在探索例如計算機視覺，自然語言處理，化學，生物學和社交網(wǎng)絡(luò)等不同領(lǐng)域時廣泛使用GNN及其衍生模型。
本文作者主要做出了兩個貢獻：（1）提出兩個圖平滑度度量標準，用于幫助理解GNN中圖信息的使用；（2）提出一種新的GNN模型，，該模型可以使用平滑度值來改善對圖信息的使用。
作者認為GNN之所以優(yōu)于現(xiàn)有的基于歐幾里得（Euclidean）的方法，其主要原因之一是因為GNN可以獲得來自對象鄰域的豐富信息。GNN通過例如均值、求和、注意力等聚合器收集鄰域信息，然后將聚合的特征向量和節(jié)點本身的特征向量合并為一個新的特征向量。經(jīng)過多輪聚合后，節(jié)點的特征向量可用于諸如節(jié)點分類之類的任務(wù)。因此，圖結(jié)構(gòu)數(shù)據(jù)帶來的性能提高與鄰域信息的數(shù)量和質(zhì)量有很大關(guān)系。為此，作者提出了兩個關(guān)于節(jié)點特征和標簽的平滑度度量，用來測量節(jié)點鄰域信息的數(shù)量和質(zhì)量。
作者還認為在實際任務(wù)中并非節(jié)點的所有鄰居都包含相關(guān)信息，在給定任務(wù)中，鄰居節(jié)點提供相關(guān)信息的同時也會提供相關(guān)干擾，簡單地使用聚合器聚合鄰居節(jié)點的特征向量常常不能達到最佳性能。為了解決這個問題，作者提出了一個新模型CS-GNN，該模型使用平滑度指標，選擇性地聚合鄰域信息，可以有效地放大有用信息并減少負面信息干擾。
2
方法與模型
作者提出了兩個圖平滑度度量標準，分別為特征平滑度和標簽平滑度。其中特征平滑度用于描述信息的數(shù)量，特征平滑度越大意味著周圍環(huán)境可以提供的信息越多。標簽平滑度用于描述信息的質(zhì)量，標簽平滑度越小意味著積極信息越多，干擾越少。
2.1 特征平滑度
根據(jù)圖1特征平滑度定義，較大的λf表示圖的特征信號具有較高的頻率，這意味著圖中的兩個連通的節(jié)點v和v'的特征向量xv和xv’有很大可能不相似，換句話說，較大的λf意味著具有不同特征的節(jié)點更傾向于連接在一起。作者認為對于具有較高頻率特征集的圖，目標節(jié)點可以從其周圍獲得更多的信息。
圖1 特征平滑度定義
為了證明λf與從周圍環(huán)境中獲得的信息之間的關(guān)系，作者提出了相關(guān)定理并進行了證明，圖2為作者提出的相關(guān)定理。作者提出較大的λf表示GNN模型可以從圖形數(shù)據(jù)中獲取更多信息。這里的DKL（S || C）在使用平均聚合器時產(chǎn)生的，作者表示即使特征平滑度λf是常數(shù)，其他聚合器（例如池化和權(quán)重）也可能具有不同的DKL（S || C）值。
圖2 相關(guān)定理
2.2 標簽平滑度
根據(jù)圖3標簽平滑度定義，，較大的λl意味著具有不同標簽的節(jié)點傾向于連接在一起，在這種情況下，周圍環(huán)境對該任務(wù)產(chǎn)生了更大的負面干擾。作者認為較小的λl意味著節(jié)點可以從其周圍獲得更多積極信息。在使用λl來度量周圍信息時，需要有標簽的數(shù)據(jù)進行訓練，當一些圖結(jié)構(gòu)數(shù)據(jù)沒有很多有標簽節(jié)點的時候，作者提出使用標記數(shù)據(jù)的子集來估計λl，這也可以獲得良好的結(jié)果。
圖3 標簽平滑度定義
2.3 CS-GNN
本文中作者所提出的CS-GNN使用加權(quán)和聚合器，合并函數(shù)為連接。為了計算每K輪的系數(shù)，作者采用了乘法注意力機制，通過將鄰居節(jié)點的特征向量與節(jié)點的自身特征向量相乘來獲得注意力系數(shù)，并應用softmax函數(shù)進行歸一化，第k輪中的每個系數(shù)a(k)i,j定義如圖4所示：
圖4 第k輪中的每個系數(shù)a(k)i,j定義
為了提高對周圍信息的利用，作者在CS-GNN使用了特征平滑度和標簽平滑度來控制周圍信息的使用，具體使用方法如下：（1）使用λl（標簽平滑度）來丟棄帶有負面信息的鄰居節(jié)點，即如果a(k)i,j小于第r個最小注意力系數(shù)的值，則將a(k)i,j置為0，這樣可以去除這些鄰居節(jié)點的干擾，保留節(jié)點自身的功能。（2）使用λf（特征平滑度）來估計獲取信息的數(shù)量，并用它來設(shè)置上下文向量的維度。較大的尺寸會引起注意力機制的波動，而較小的尺寸會限制其表達力，因此設(shè)置適當?shù)某叽缈梢垣@得較好的性能。（3）使用了和GAT不同的注意力系數(shù)表示方法，作者使用了q(k)i,j,即節(jié)點vi與鄰居vj的特征向量之差。之所以使用q(k)i,j，作者表示較大的λf表示節(jié)點及其鄰居的特征更不相似，這意味著鄰居可以貢獻更多的信息。因此，通過使用q(k)i,j，當節(jié)點vi及其相鄰節(jié)點vj的特征較為不相似/相似時，我們可以獲得更大/更小的a(k)i,j，圖5為使用加權(quán)和聚合器執(zhí)行K輪聚合時，節(jié)點a的表示向量。
圖5 第k輪節(jié)點a的特征向量
現(xiàn)實世界的圖通常包含一些輔助信息，例如節(jié)點和邊的屬性，局部拓撲特征和邊方向等。作者提到CS-GNN可以包含豐富的輔助信息，并使用這些信息來提高性能。作者以局部拓撲特征為例，在注意力機制中，獲得局部拓撲特征后將它納入到節(jié)點特征信息中，從而將其視為節(jié)點特征信息的一部分，圖6為將局部拓撲特征tvi納入到節(jié)點特征信息公式，圖7為在全連接層中使用局部拓撲特征tvi獲得預測標簽公式
圖6 節(jié)點使用局部拓撲特征tvi
圖7 預測標簽使用局部拓撲特征tvi
3
實驗
作者的實驗分為二部分，第一部分先比較了CS-GNN和經(jīng)典模型在節(jié)點分類任務(wù)上的效果，第二部分評估了不同特征平滑度和標簽平滑度對基于神經(jīng)網(wǎng)絡(luò)的方法在給定任務(wù)上性能的影響。
作者采用了三種類型的方法作比較，分別為基于拓撲的方法，基于特征的方法和GNN方法，每種方法選擇了幾種代表性模型，基于拓撲的方法選用了struc2vec (Ribeiro et al., 2017), GraphWave (Donnat et al., 2018) 和Label Propagation (Zhu & Ghahramani, 2002)，基于特征的方法選用了LogisticRegression 和MLP（Multilayer Perceptron），GNN方法則選用了GCN,GraphSAGE和GAT。
作者采用了五個現(xiàn)實世界的數(shù)據(jù)集作為實驗數(shù)據(jù)集，包括Citeseer, Cora,PubMed三個引用網(wǎng)絡(luò)，一個亞馬遜的計算機聯(lián)合采購網(wǎng)絡(luò)和一個邊界網(wǎng)關(guān)協(xié)議（BGP）網(wǎng)絡(luò)。作者將數(shù)據(jù)集的70%用于訓練，10%用于驗證，20%用于測試，使用F1-Micro分數(shù)來衡量每種方法的節(jié)點分類性能，并對所有模型使用默認參數(shù)或與CS-GNN相同的參數(shù)。
表1 平滑度值
表1報告了每個數(shù)據(jù)集的兩個平滑度值。Amazon的λf值比其余的要大得多，而PubMed的λf值最小,這意味著Amazon中大多數(shù)節(jié)點的特征向量是不相似的，而對于PubMed而言則相反。對于標簽平滑度λl，BGP（small）的值比其他數(shù)據(jù)集要大得多，這意味著大多數(shù)連接節(jié)點具有不同的標簽。由于BGP（完整）包含許多未標記的節(jié)點，因此作者使用BGP（small）的λl作為估算值。
表2 節(jié)點分類結(jié)果
表二顯示了不同的模型在五種數(shù)據(jù)集上的節(jié)點分類效果，從分類結(jié)果數(shù)據(jù)上看基于拓撲的方法Label Propagation在引用網(wǎng)絡(luò)和Amazon網(wǎng)絡(luò)有很好的表現(xiàn)，作者認為原因是Label Propagation在社區(qū)檢測上有較好效果，而從圖的較小λl值推斷出這些圖包含許多社區(qū)結(jié)構(gòu)，即較小的λl意味著許多節(jié)點與其鄰居具有相同的類別標簽，而連接在一起并且屬于同一類別的節(jié)點往往會形成一個社區(qū)。而對于BGP數(shù)據(jù)集而言，struc2vec和GraphWave則有更好的表現(xiàn)。對于基于特征的方法，Logistic Regression and MLP在五種數(shù)據(jù)集上均有相差不大的不錯表現(xiàn)。
對于GNN方法而言，除了PubMed和BGP，GCN和GraphSAGE在其他數(shù)據(jù)集上均有相同的表現(xiàn)，GAT和CS-GNN也有相似效果。作者認為造成這些結(jié)果的主要原因是PubMed數(shù)據(jù)集的λf較小，這意味著節(jié)點從周圍環(huán)境獲取的信息較少，而BGP的λl較大，這意味著節(jié)點從周圍環(huán)境獲取的大多數(shù)信息是負面干擾 在這樣的情況下，GraphSAGE和CS-GNN因為使用連接為合并函數(shù)從而保留節(jié)點自己的特征，因此在PubMed和BGP上相比于其他模型效果更好。而對于其他數(shù)據(jù)集，GAT和CS-GNN的F1-Micro得分比所有其他模型都高得多?？傮w而言，作者認為CS-GNN是在所有數(shù)據(jù)集上都具有較好表現(xiàn)的模型。
為了更好的驗證平滑度對實驗結(jié)果的影響，減少其他因素的干擾，作者通過在Amazon單一數(shù)據(jù)集上進行實驗的方法來驗證平滑度的影響。為了改變平滑度，作者對二種平滑度分別進行了相應操作：（1）為了改變λf，作者將節(jié)點的特征向量廣播到其鄰居，當節(jié)點接收到特征向量時，它會將其當前特征向量和接收到的那些特征向量的平均值作為新的特征向量，然后再將新的特征向量廣播到其鄰居。這樣一直迭代下去，節(jié)點特征會收斂到相同的值，λf的值會逐漸減小（2）為了調(diào)整λl，作者隨機丟棄連接兩個具有不同標簽的節(jié)點的一部分邊，去除這些邊會降低λl的值，節(jié)點可以從其相鄰節(jié)點獲得更多的正面信息。
圖8為平滑度的影響，從圖中可以看到隨著廣播輪數(shù)的增加，λf的值相應的減少,GNN模型的效果也隨之下降。相反，當λl的值下降時，GNN模型的效果都隨之提高?？偟膩碚f，GNN模型能夠在圖結(jié)構(gòu)數(shù)據(jù)有較大的λf和較小的λl時從周圍節(jié)點獲得更多的正面信息，從而在節(jié)點分類等任務(wù)上有很好的表現(xiàn)。
圖8 平滑度的影響
4
總結(jié)
在這篇文章中，作者研究了如何測量GNN從圖中獲取信息的數(shù)量和質(zhì)量，并提出了特征平滑度和標簽平滑度二種平滑度指標。然后，作者還提出了CS-GNN模型，用于應用上述平滑度指標來改善對圖信息的使用。通過多個數(shù)據(jù)集以及多個模型在給定任務(wù)上性能的比較，實驗結(jié)果證明CS-GNN相比于現(xiàn)有模型能夠獲得更多有用信息，在給定任務(wù)上的實驗效果優(yōu)于其他模型。
參考資料
https://iclr.cc/virtual_2020/poster_rkeIIkHKvS.html
聯(lián)系客服
