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