基于GraphSage節點度重要性聚合的網絡節點分類研究

鄒長寬, 田小平, 張曉燕, 張雨晴, 杜磊

(北京石油化工學院信息工程學院，北京 102617)

在計算機領域，“圖”是一種把實體網絡抽象出來的數據結構。圖中的頂點和邊也分別被稱為節點和關系。例如，社交網絡中的用戶可看作節點，用戶之間是否關注可看作關系。圖數據采用非歐幾里得式數據結構進行存儲，其中心節點的鄰居節點數量和節點順序不固定，不滿足平移不變性[1]，很難定義卷積核，導致傳統的卷神經網絡方法無法處理。圖神經網絡的基本思想是通過結合節點自身和鄰居節點的特征來迭代更新節點的表示[2]，是解決此問題的一種有效方法，最近幾年受到研究者們的廣泛關注。

節點分類是圖神經網絡中一類最為廣泛的應用，其目的是使用已提供標簽的節點信息表示新的節點特征，并對未標明類別的節點進行分類。除了應用于基于社交網絡，還可以應用于生物網絡和引文網絡[3]。

傳統節點分類方法主要是基于表示學習的圖嵌入方法。如DeepWalk方法[4]，通過在圖中隨機游走并對游走的節點使用SkipGram模型[5]來實現對節點的表示學習。LINE方法[6]在引入一階相似度和二階相似度的基礎上來學習到節點間的高階相似性。其中，一階相似度表示節點間是否有聯系，二階相似度則表示節點鄰居的相似程度。Node2vec方法[7]使用深度優先策略和廣度優先策略代替了隨機游走策略，不僅能讓模型自己學習如何游走，還能讓模型更有效地結合圖結構來實現節點的表示學習。以上方法有兩個明顯的缺點：①基于圖嵌入方法的計算量會隨著節點數呈線性增長且無法處理節點的自身特征；②直接的嵌入方法缺乏泛化能力，無法推廣到新的圖上。

為了尋找一種有效的節點分類方法，學者們將卷積神經網絡的思想拓展到圖數據上，加速了圖神經網絡的發展。Brua等[8]提出了Spectral Network，通過基于圖對應的拉普拉斯矩陣的特征分解，在傅里葉域中定義卷積運算實現了節點分類，但這種方法計算復雜度高。基于此，Defferrard等[9]提出了ChebyNet,省去了計算拉普拉斯矩陣的過程。Kipf等[10]改進了ChebyNet網絡并使用一階卷積核，提出了圖卷積網絡(graph convolutional network,GCN)。Hamilton等[3]提出了歸納式學習的圖神經網絡模型GraphSage，GraphSage沒有使用圖的拉普拉斯矩陣，通過對節點鄰居信息的聚合來表示出一個新的信息，不同的聚合方式會有不同的效果。Hu等[11]利用多層感知機設計的圖多層感知機(Graph-multilayer perceptron,Graph-MLP)模型將圖結構融入到節點的特征變換過程當中，使得模型在節點間鄰接信息缺失的情況下仍能保持有效的分類。

基于此，通過在GraphSage聚合函數中引入節點自身特征信息和圖結構相關信息，提出了可用于監督學習GraphSage-Degree節點分類模型，該模型首先從圖中獲取節點度，即節點在網絡中的連接邊數，然后根據節點度判斷節點在鄰域中的重要性，最后以重要性為權值來聚合節點的特征信息，為研究節點度在節點分類中的作用提供了科學依據。

1 網絡模型

1.1 GraphSage設計

傳統的圖神經網絡在訓練模型時同時對所有訓練節點及其特征進行操作，但由于計算機的內存限制，這種方法有可能導致分類失敗。因此，GraphSage使用小批量的訓練方式，即在訓練時的每一輪epoch中，又分成若干次小訓練，每一次小訓練只使用20個訓練數據。

GraphSage模型主要由3個步驟組成，即采樣、聚合和分類，具體如下。

步驟1采樣。如果模型在學習節點表示的過程中使用所有的鄰居節點，則會因為鄰居節點集合的大小不確定導致計算復雜度不可控。針對每一個節點，GraphSage以其為中心將整個圖結構數據由內到外分成k層。這樣位于第l(1≤l≤k)層的每個節點采樣Sl個鄰居節點，采樣時若鄰居節點數不足Sl個則使用全部鄰居節點，否則從鄰居節點中隨機采樣Sl個節點。缺省情況下，k值選擇2，需要保證S1S2≤500[3]。圖1為k=2，S1=3，S2=2時的采樣示意圖。圖1中用虛線劃分鄰居節點所在層次，具有十字標志的節點為中心節點，具有一條橫線的節點為采樣的一階鄰居節點，具有兩條橫線的節點為采樣的二階鄰居節點，空白節點為未被采樣到的節點，箭頭表示沿著節點之間邊的采樣方向。

用虛線劃分鄰居節點所在層次；箭頭表示沿著節點之間邊的采樣方向

步驟2聚合。通過聚合操作可以完成對鄰居節點特征的整合輸出，聚合時必須要對聚合節點的數量做到自適應,不管節點的鄰居數量為多少，聚合后輸出的維度必須是一致的。聚合時首先將二階節點的特征聚合到對應的一階節點，然后再將一階節點的特征聚合到中心節點，最后根據聚合出的中心節點特征進行分類。圖2為節點聚合示意圖，箭頭表示沿著節點之間邊的聚合方向。

(1)

(2)

對k-1層的所有節點執行式(1)和式(2)的步驟，便可得到該層所有節點學習后的特征。繼續對k-2層節點執行以上步驟便可得到k-2層所有節點學習后的特征。

兩層GraphSage模型的聚合及學習過程如圖3所示。

圖3 節點聚合及學習過程

步驟3分類。GraphSage將完全學習后的特征首先經過一個全連接層，接著使用LogSoftmax函數分類。設分成m類，xi,c表示經過全連接層后節點i為c類別的初始值，則xi,c的LogSoftmax值pi,c的計算公式為

(3)

式(3)中：pi,c為把節點i預測為c類的概率，得到節點在所有類別上的LogSoftmax值后，最大的值對應的類別即為該節點輸出的預測類別。

GraphSage使用交叉熵函數計算損失，計算公式為

(4)

式(4)中：L為損失函數；n為節點個數；i為觀測節點；m為類別個數；yi,c為節點i真實類別是否為c類的判決值，只能選0或1，可當常數看。

接著通過梯度下降算法不斷優化模型，使得損失函數盡可能最小。

1.2 聚合函數設計

GraphSage中Mean聚合函數按照鄰居節點的個數取每個鄰居節點特征的均值，其計算公式為

(5)

GraphSage中Max聚合函數逐元素取鄰居節點特征的最大值，計算公式為

(6)

對輸入圖節點的鄰接矩陣A，其大小為M×N，即A為一個M行N列的矩陣,記為AM×N。鄰接矩陣AM×N表示節點之間的連接關系，若第i個節點和第j個節點之間有連接，那么對應的鄰接矩陣元素Ai,j=1，否則Ai,j=0。節點度為該節點與其他節點的連接邊數，可以用圖的鄰接矩陣計算，節點i的度計算公式為

(7)

節點度常用來表示節點在網絡中的重要程度或者影響力[12]。王建偉等[13]同時使用節點度和其鄰居節點度來衡量節點的重要性，即認為節點及其鄰居節點的度越大，該節點在網絡中就越重要，含有的信息也可能更多。且一般認為網絡中相鄰的節點屬性相似[14]，含有的特征信息也可能相似，而節點之間越相似，其對彼此的影響也越大[15]。因此，所設計的聚合函數根據鄰居節點的重要性進行聚合，即鄰居節點中的節點度越大，聚合時能夠提供更多的信息。

在計算節點重要性時，是在每個節點的鄰居節點集合內部單獨進行計算，得到的是該節點在所屬鄰居節點集合內部的重要性，而并非節點在整個圖中的重要性。設鄰居節點vi的度為dvi，則按照節點度的大小把鄰居節點vi的重要性w(vi)定義為

(8)

式(8)中：w(vi)的取值范圍為[0,1]。

由w(vi)可以定義所使用的聚合操作。

(9)

從式(9)中可以發現，聚和后特征為各個鄰居節點特征以重要性為權值的加權和，特征每個位置上的聚合操作對應為

(10)

針對vi的度dvi，做以下處理。

(11)

式(11)中：D為人為設置的整數參數，用于限制使用的節點度大小，D的取值一般不超過每層的節點采樣參數S。

從式(11)中可以看出，小于等于D值的節點度不做處理，將所有大于D的節點度限制為D。適當的D值可以防止聚合時過度聚合具有大節點度節點的特征，保證各個鄰居節點的特征都可以有效的參與到聚合中來。

2 實驗準備

2.1 實驗數據集

使用的Cora、Citeseer和Pubmed為 GCN[10]所使用的3個數據集，數據集下載網址為：https://github.com/tkipf/gcn。

數據集的詳細信息如表1所示。其中節點數、邊數、特征數及類別數分別表示數據集中總的數據個數、所有節點間總的連接邊數、每個節點所具有的特征數及數據集中節點總的類別數。數據集的劃分參考GCN[10]中的方式，訓練節點數量為數據集中類別數的20倍，驗證節點為500，測試節點為1 000。

表1 數據集介紹及劃分

2.2 實驗過程

為了驗證GraphSage-Degree的有效性，實驗選取了以下方法進行比較。①DeepWalk[4]：通過在圖中進行隨機游走的方式，對節點采樣并學習節點的表示；②LINE[6]：引入了兩種節點相似度，構造了節點的鄰域；③node2vec[7]：摒棄了DeepWalk中隨機游走的方式，定義了深度優先和廣度優先兩種游走策略；④GCN[10]：圖卷積神經網絡，對圖節點的拉普拉斯矩陣進行了對稱歸一化；⑤GraphSage-Mean[3]：使用對鄰居節點特征均值聚合的GraphSage模型；⑥GraphSage-Max[3]：使用對鄰居節點特征逐元素取最大值的聚合方式；⑦Graph-MLP[11]：使用多層感知機構成的節點分類模型。

在實驗中，GCN，GraphSage和Graph-MLP的參數設置均參考各自論文，epoch均為100，各個模型所學習的節點特征最終大小，即embedding維度均為128。DeepWalk、LINE和node2vec的其他參數參考張陶等[16]的研究，參數設置如表2所示。

表2 參數設置

2.3 參數D分析

聚合函數中的參數D限制著模型中節點聚合過程中所使用的節點度值，在Cora、Citeseer和Pubmed數據集上分析了不同D值對分類效果的影響，D取值為0～10的整數，D=0時表明不對節點度進行限制，即使用節點原始的度值。不同D值在各個數據集的分類結果如圖4所示。

圖4 不同D值下的分類結果

在Cora數據集中，最大值和最小值分別在D=8和D=1時取得，差值比例為1.7%；在Citeseer數據集中，最大值和最小值分別在D=3和D=7時取得，差值比例為1.4%；在Pubmed數據集中，最大值和最小值分別在D=3和D=10時取得，差值比例為1.4%；從數據中可以發現，D值并不是越大越好。節點度越大，意味著與該節點連接的節點就越多，也就意味著該節點有更大的可能性與不同屬性的節點連接，從而導致其含有的特征信息較為雜亂。如果此時聚合該節點信息時不做處理將會很大概率影響分類效果，而D值就在此起了一個限制大度數節點的作用。因為不同的數據集數據內容不同，節點特征不同，節點度也不盡相同，所以每個數據集對D值的偏好也就不同。

2.4 實驗結果及分析

選擇macro-F1和micro-F1作為對不同模型進行節點分類效果的評價指標。

對于分類問題，可以根據真實類別與模型預測類別的組合劃分為真正例(true positive,TP)、真反例(true negative,TN)、假正例(false positive,TP)、假反例(false negative，FN)，如表3所示。

根據表3參數可定義查準率P(precision)與查全率R(recall)，可表示為

表3 真實類別與預測類別分類結果定義

P=TP/(TP+FP)

(12)

R=TP/(TP+FN)

(13)

由P和R可以確定F1的計算公式為

F1=2PR/(P+R)

(14)

macro-F1為每一類F1的算術平均，假設數據共有n類，則macro-F1的計算公式為

(15)

對于micro-F1，首先計算micro-P和micro-R，計算公式為

(16)

(17)

則micro-F1定義為

(18)

從式(12)～式(18)可以看出，macro-F1和micro-F1通過不同的方式權衡查準率和查全率，區別在于macro-F1是計算每一個類別F1分數然后求平均，micro-F1是計算所有類別總的查準率和查全率。在分類任務中，micro-F1的值與分類準確率A(accuracy)的值大小相等。

各個模型的macro-F1和micro-F1結果分別如表4、表5所示，在Cora、Citeseer和Pubmed數據集上，本文模型GraphSage-Degree中參數D分別取值8、3和3。

表4 不同方法的macro-F1比較

表5 不同方法的micro-F1比較

本文方法與其他方法相比，在Cora、Citeseer和Pubmed數據集上的分類結果提升值及平均提升值和最大提升值如表6所示。

從表6的數據中可以看出，GCN、GraphSage和Grap-MLP模型的效果明顯優于DeepWalk、LINE和

表6 本文方法和其他方法相比的提升值

node2vec等圖嵌入算法模型，原因在于圖嵌入算法受圖結構的影響較大，而且沒有充分使用節點的特征信息。在Cora數據集上，本文方法的macro-F1分數高于GCN2.67%，提升比例約為3.6%，高于GraphSage-MLP2.24%，提升比例約為3%，高于Graph-Max2.78%，提升比例約為3.75%；micro-F1分數比GCN高2.4%，提升比例約為3.13%，比Graph-MLP高2.9%，提升比例約為3.8%，比Graph-Max高3%，提升比例約為3.94%。在Citeseer數據集上，本文方法的macro-F1分數比GraphSage-Max高1.14%，提升比例約為1.8%；micro-F1分數比GraphSage-Max高1.1%，提升比例約為1.6%。在Pubmed數據集上，本文方法的macro-F1分數比Graph-MLP高3.34%，提升比例約為4.47%；micro-F1分數比Graph-MLP高1.8%，提升比例約為2.37%。

本文方法與GCN、Graph-MLP和其他GraphSage模型相比，在Cora數據集上的結果要優于Citeseer和Pubmed數據集，可能與Citeseer數據集中節點特征數過大(3 703維)，含有信息雜亂，Pubmed數據集中節點特征數過小(500維)，難以提取出更有效的特征信息有關。

本文方法在Cora、Citeseer和Pubmed數據集上和其他方法相比，macro-F1的平均提升值分別為8.72%、10.37%和8.29%，在Pubmed上有最大提升值38.84%；micro-F1的平均提升值分別為8.97%、11.16%和6.9%，在Pubmed上有最大提升值38.39%。

3 結論

在GraphSage模型的基礎上，提出了基于節點重要性的聚合算法。該方法通過度計算節點的重要性，并根據節點重要性為權值聚合特征信息，分析了不同參數D值下的模型分類效果。與圖嵌入算法、GCN、Graph-MLP及其他GraphSage模型相比，本文方法在Cora、Citeseer和Pubmed數據集上macro-F1的平均提升值分別為8.72%、10.37%和8.29%，在Pubmed上有最大提升值38.84%；micro-F1的平均提升值分別為8.97%、11.16%和6.9%，在Pubmed上有最大提升值38.39%。本文方法在Citeseer數據集上取得的macro-F1和micro-F1分別為63.86%和68.9%，在Pubmed數據集上取得的macro-F1和micro-F1分別為78.05%和77.6%；此外，本文方法的macro-F1和micro-F1在Cora數據集上取得了最優成績，分別為76.9%和79.1%，表明本文模型在網絡節點分類上的可行性和有效性。