基于子圖劃分的多尺度節點分類方法

李浩然 張紅梅

(桂林電子科技大學信息與通信學院 廣西 桂林 541004)

0 引 言

近年來,隨著圖卷積神經網絡(Graph Convolutional Networks,GCNs)理論的發展和成熟,成為了當前圖領域研究的重要理論。常見的圖任務包括節點分類[1]、鏈接預測[2]等。但傳統圖神經網絡在對大規模圖數據進行處理時通常存在著由于模型層數過深引起的過平滑問題,即迭代地進行鄰域特征提取導致每個節點都學習到了圖中其他所有節點的信息,使每個節點的特征信息都趨于一個相似的值,這對于節點分類是非常不利的。因此,圖神經網絡中的過平滑問題亟待進一步的研究。

1 相關工作

1.1 GCNs

圖神經網絡(Graph Neural Networks,GNNs)這一概念是由Gori等[3]首次提出;Bruna等[4]則通過傅里葉變換將圖的拉普拉斯矩陣從空間域轉換至頻域,基于卷積定理,創造性地提出了圖卷積神經網絡GCNs的概念;后來,Kipf等[1]和Defferrard等[5]在原始GCNs的基礎上分別提出了兩種簡化的方法,在降低算法復雜度的同時極大地提高了算法的效率。另外,為了解決算法的可擴展性問題,Hamilton等[6]和Velickovic等[7]又提出幾種基于空間域的方法,通過聚集鄰居節點的信息直接在圖上執行卷積操作,同樣達到了不錯的效果。

1.2 DeepGCNs

在圖神經網絡的研究中,不乏有人提出通過擴展模型的深度來提高算法的準確率。例如Kipf等[1]采用殘差連接的方法對GCNs模型進行堆疊,但當網絡增至2層以上時,模型性能反而會隨著層數的疊加而下降。Li等[8]提出過平滑問題是限制圖卷積神經網絡深度擴展的主要原因。這是由于GCNs通過逐層迭代來聚集高階鄰域信息,在經過足夠多層網絡后,同一連通分量內每個節點都會聚集到各自的特征信息,導致該連通分量內所有節點的特征信息都會收斂于一個相同的值。于是Chiang等[9]提出了一種Cluster-GCN,利用改變網絡結構來優化特征提取過程,一定程度上緩解了過平滑的問題,但子圖劃分同樣帶來了部分特征信息的損失,對算法準確率造成了影響。Abu-EI-Haija等[10]則設計了一種具有優良局部拓撲結構的N-GCN網絡,通過對較小尺寸的卷積核進行組合,實現了對深層特征的等效,避免了過平滑的問題,但在處理大規模數據集時,由于組合了多個卷積核的算法機制,導致模型對于顯存的消耗十分巨大。

2 方法設計

2.1 子圖劃分方法

為了解決圖神經網絡中的過平滑問題,在訓練前采用一種數據預處理方法,具體是將原始圖劃分為多個子圖,每個子圖各屬于一個連通分量,各個連通分量之間通過邊緣互相連接,但并不進行信息交換;連通分量內部節點互相連接,以此限制節點只能在其所屬的連通分量內進行特征的聚集和更新。將圖劃分出越多的子圖,過平滑現象就會越不明顯,在極端情況下,將每個節點作為一個子圖,節點之間都不進行信息傳遞,則完全不會出現過平滑的問題,但同時節點也無法學習到鄰域內的信息。圖1展示了節點在兩幅圖上的鄰域擴展過程。

圖1 節點鄰域擴展過程示例

圖1中,以節點0作為中心節點進行分析,節點1代表一階鄰居節點,節點2代表二階鄰居節點,節點3代表三階鄰居節點,虛線代表兩個子圖(連通分量)之間的連接。左圖代表原始的圖數據,經過三次鄰域擴展后,中心節點提取到了圖中所有節點的信息;右圖則代表經過劃分后的圖,刪除了連通分量之間的連線,將原始圖分為了兩個子圖,經過兩次鄰域擴展后,中心節點提取了其所在子圖內所有的鄰域信息。對子圖內鄰域特征的提取已經足夠表示中心節點的性質,所以,對整幅圖的信息提取在鄰域搜索的過程中浪費了大量的計算資源。

本文采用圖聚類算法Metis[11]對圖數據進行子圖劃分,一般分為三個步驟:粗化階段、初始劃分階段和細化階段。首先,粗化過程主要是將原始圖中的部分邊和節點逐層合并為新的節點表示,并保存粗化過程中的節點映射關系,最后得到節點數較少但具有原圖特征和性質的縮略圖,以此降低劃分過程中的計算復雜度。其次,在初始劃分階段將縮略圖中的節點分為規模大致相等的c部分(c值一般通過經驗設定,并在實驗中進行微調)。最后,在細化階段按照節點映射關系逐步將縮略圖還原為原始圖,并在還原過程中對節點劃分狀態進行微調和優化。該算法旨在使子圖內的連接遠多于子圖間的連接,以更完整地保留原始圖數據的局部結構和特征信息。以G=(V,E)為例,將其分為c個子圖,表示為:

[(V1,E1),(V2,E2),…,(Vt,Et),…,(Vc,Ec)]

(1)

式中:Vt代表子圖Gt中的節點集合,Et是指Vt中節點之間的連線,t∈[1,c]。新圖中的鄰接矩陣與原始鄰接矩陣之間的關系表示為:

2.2 Graph-Inception網絡結構

本節結合N-GCN的網絡框架,將對模型寬度的拓展工作應用于圖神經網絡研究領域,設計了一種Graph-Inception網絡,網絡結構如圖2所示。

圖2 Graph-Inception網絡結構

從節點特征信息流向的角度進行分析,當圖神經網絡采用了上述結構之后,模型中就同時存在了兩種節點特征聚集的方式,分別是橫向擴展的鄰域特征聚集方式用來提取圖的局部結構信息,以及縱向擴展的層間特征聚集方法用來提取圖的層級表征信息。

橫向特征聚集方式對應Graph-Inception結構中的GCN,為每個圖卷積神經網絡設置不同尺寸的卷積核,以提取目標節點多尺度感受野內的鄰域表征信息。本文選擇了文獻[5]中提出的圖卷積神經網絡,如式(4)所示,利用切比雪夫多項式對原始圖卷積核[4]進行化簡。其中K代表切比雪夫多項式的階數,特別地,也可以代表圖卷積核的尺寸,通過改變K值便能改變圖卷積核的感受野以提取到不同尺寸鄰域內的信息。

另一方面,既然深層特征存在問題,那就將淺層的特征保留下來,通過對一些較小尺寸的卷積核進行組合,將所有卷積層的輸出結果拼接為一個高維特征圖,以實現對模型深度擴展的等效。縱向特征聚集方式就是基于這樣的思想,通過對不同感受野下GCN的輸出進行拼接,使結果包含不同層的層級表征。一方面,這樣的做法即使不需要深層的網絡模型也能提取到豐富的特征信息;另一方面,采用這樣的多頭機制,即使某一個圖卷積神經網絡的輸入存在噪聲或擾動時,分類子網的權重會向其他GCN中的信息進行轉移,從而起到了一定的修正和優化作用。

式中:X=‖(X1,X2,…,Xc),Xc代表子圖Gc對應的特征矩陣。

將所有GCN的輸出經過拼接后輸入循環神經網絡(RNN),利用循環單元中的邏輯門結構為每個輸出分配合適的權重,從而使特征矩陣中能自適應地融合進豐富的層級表征信息;再通過一個多層感知機(MLP)輸出最終的特征;最后經過Softmax操作,便得到了Graph-Inception網絡的輸出:

Y=Softmax(MLP(H))

(7)

式中:Y代表模型預測節點的標簽矩陣。

2.3 算法步驟

本節將給出基于子圖劃分的多尺度節點分類方法的具體步驟:

Step1首先利用預處理方法對原始圖G進行子圖劃分。

Step2將每個子圖中的所有節點視為一個batch,輸入Graph-Inception網絡,并經過MLP處理后得到模型的輸出。

Step3使用模型預測的分類結果與真實標簽計算負對數似然損失NLL,并計算損失函數的梯度,利用梯度對參數進行優化。

Step4開始訓練,重復Step 2、Step 3,直至損失函數連續10次迭代后不再下降時,停止訓練。

3 實驗仿真與分析

3.1 實驗環境和數據集介紹

實驗硬件環境:8核Inter(R)Xeon(R)處理器,32 GB內存;NVIDIA GeForce GTX 1080Ti的GPU,16 GB內存。軟件環境為64位Windows 10、CUDA10.2、Python 3.7、Pytorch1.5.0。

為了研究和驗證本文實驗的有效性,本文選擇了三個節點任務數據集,下面對數據集中的內容進行簡單介紹。PPI:是一個包含了24幅圖的蛋白質相互作用網絡數據集,每幅圖代表不同的人體組織。節點代表不同的蛋白質,節點特征包括位置基因信息、基因序列特征和免疫學特征,預測任務是對蛋白質的功能進行判斷;Reddit:是一個包含了Reddit網站中232 000個帖子的社交數據集,圖中節點代表帖子,如果兩個帖子被同一個用戶評論過,則建立一條邊,節點的特征通過Glove詞嵌入方法生成,預測任務是對帖子所屬的子論壇進行判斷;Amazon:該數據集包括亞馬遜網站中Computers和Photo品類的共同購買關系圖,其中節點代表商品,節點特征是由商品評價的詞袋編碼產生,邊緣表示經常一起購買的產品,預測任務是對產品的類別進行判斷。數據集主要參數如表1所示。

表1 數據集主要參數

3.2 模型與超參數設置

模型設置:本文中的模型采用了圖2所示的網絡結構,并采用4個GCN網絡,RNN采用LSTM網絡。

超參數設置:參照文獻[10]中采用四種感受野K的組合,并分別設置為1、2、3、4;參照文獻[9]將PPI數據集劃分為50個子圖,將Reddit數據集劃分為1 500個子圖,將Amazon數據集劃分為200個子圖;初始學習率設置為0.005;每經過200個epoch將學習率降低為原來的0.5倍;batch-size設置為128。選擇Adam作為參數優化器,使用L2正則化防止訓練時過擬合,選擇負對數似然函數NLL作為損失函數。

3.3 準確率分析

為了驗證本文方法的有效性,采用N-GCN和Cluster-GCN作為對比模型進行實驗,檢測準確率對比如表2所示。可以看出,本節提出的Graph-Inception網絡在節點分類任務中的準確率表現上取得了明顯的提升。與Cluster-GCN相比,在總節點數較少的PPI數據集上,本文方法的準確率提高了0.44百分點;而在節點數目相對較多的Amazon和Reddit數據集上,本文方法分別得到了0.84百分點和3.07百分點的提升。可以看出,本文方法對于規模越大的數據集準確率提升越明顯,這是因為在子圖劃分的過程中,一些邊被屏蔽導致部分信息丟失,大數據集仍能保留多數特征信息,而越小的數據集由于信息損失后不足以保證自身表示的完整性。

另一方面,從表2中數據看出,使用N-GCN對Reddit數據進行處理時,由于數據集過大以及N-GCN算法機制的原因,導致訓練時占用內存過高,導致GPU溢出,無法正常進行訓練。側面驗證了基于子圖劃分的預處理方法的必要性。

表2 模型檢測準確率(%)

3.4 計算效率分析

為了驗證本文方法的計算效率,表3展示了N-GCN和Cluster-GCN以及Graph-Inception方法在三個基準數據集上的計算耗時對比,以測試集中所有節點的測試時間作為評價指標。可以看出,Cluster-GCN由于采用了子圖劃分的數據預處理方法,部分節點之間不用進行信息交換,所需的訓練時間最短;N-GCN由于采用了多個GCN的組合,所需訓練時間較多;而本文方法則是在N-GCN的基礎上,對數據進行了預處理,優化了特征提取過程。因此本文方法訓練所需的時間,與N-GCN相比較少,而與Cluster-GCN相比較多。

表3 模型檢測耗時對比 單位:s

3.5 損失值分析

圖3-圖5展示了N-GCN和Cluster-GCN以及Graph-Inception方法在三個基準數據集上的損失函數曲線變化。通過對比可以看出,本文方法在訓練過程中可以使損失曲線更早地收斂,且損失值最終能夠收斂至一個更小的數值,這是由于循環單元中的門結構對于噪聲信息的傳播具有很好的抑制能力。其中,Cluster-GCN相比于另外兩個模型損失值較高,原因可能在于子圖劃分導致部分信息丟失,側面驗證了多尺度下特征提取的必要性。

圖3 Reddit數據集損失值變化

圖4 PPI數據集損失值變化

圖5 Amazon數據集損失值變化

3.6 子圖劃分分析

圖6-圖8展示了采用不同子圖數下本文方法在三個基準數據集上的檢測準確率和時間變化。可以看出,隨著子圖數的增加,檢測時間也隨之變短,這是由于每個子圖內節點數也在逐漸減少;通過實驗,數據集PPI、Reddit和Amazon的檢測準確率分別在子圖數為50、1 500和200處取得最優值。因此為了保證在檢測時間盡可能短的情況下檢測準確率較高,選擇此組子圖數作為模型的超參數。

圖7 不同子圖數Reddit數據集檢測準確率、時間變化

圖8 不同子圖數Amazon數據集檢測準確率、時間變化

3.7 多尺度感受野分析

為了驗證Graph-Inception方法中感受野對模型檢測準確率的影響,表4展示了不同尺度感受野組合下本文方法在三個基準數據集上的準確率變化,其中K表示采用的k[1,K]的感受野組合。可以看出,模型的檢測準確率在如下范圍內隨K值變大而增高,這是由于感受野越大,提取到的層級特征越豐富。但是感受野過大同樣會帶來過平滑現象導致的檢測準確率降低,這在規模較小的PPI數據集上得到了體現。

表4 不同感受野下檢測準確率對比

4 結 語

本文介紹了一種基于子圖劃分的多尺度節點分類方法,旨在從網絡結構和特征聚集方式兩方面抑制圖神經網絡中的過平滑問題。首先以子圖劃分的數據預處理方式改變原始圖中的鄰域結構,然后通過使用不同尺寸卷積核的組合對目標節點多尺度下的鄰域特征信息進行融合。最后通過實驗證明,本文方法能夠有效抑制圖神經網絡中的過平滑問題,在基準節點分類數據集PPI、Reddit和Amazon上的預測準確率都取得了不同程度的提高。