基于子圖劃分的多尺度節(jié)點(diǎn)分類方法

李浩然 張紅梅

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

0 引 言

近年來(lái),隨著圖卷積神經(jīng)網(wǎng)絡(luò)(Graph Convolutional Networks,GCNs)理論的發(fā)展和成熟,成為了當(dāng)前圖領(lǐng)域研究的重要理論。常見(jiàn)的圖任務(wù)包括節(jié)點(diǎn)分類[1]、鏈接預(yù)測(cè)[2]等。但傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)在對(duì)大規(guī)模圖數(shù)據(jù)進(jìn)行處理時(shí)通常存在著由于模型層數(shù)過(guò)深引起的過(guò)平滑問(wèn)題,即迭代地進(jìn)行鄰域特征提取導(dǎo)致每個(gè)節(jié)點(diǎn)都學(xué)習(xí)到了圖中其他所有節(jié)點(diǎn)的信息,使每個(gè)節(jié)點(diǎn)的特征信息都趨于一個(gè)相似的值,這對(duì)于節(jié)點(diǎn)分類是非常不利的。因此,圖神經(jīng)網(wǎng)絡(luò)中的過(guò)平滑問(wèn)題亟待進(jìn)一步的研究。

1 相關(guān)工作

1.1 GCNs

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

1.2 DeepGCNs

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

2 方法設(shè)計(jì)

2.1 子圖劃分方法

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

圖1 節(jié)點(diǎn)鄰域擴(kuò)展過(guò)程示例

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

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

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

(1)

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

2.2 Graph-Inception網(wǎng)絡(luò)結(jié)構(gòu)

本節(jié)結(jié)合N-GCN的網(wǎng)絡(luò)框架,將對(duì)模型寬度的拓展工作應(yīng)用于圖神經(jīng)網(wǎng)絡(luò)研究領(lǐng)域,設(shè)計(jì)了一種Graph-Inception網(wǎng)絡(luò),網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。

圖2 Graph-Inception網(wǎng)絡(luò)結(jié)構(gòu)

從節(jié)點(diǎn)特征信息流向的角度進(jìn)行分析,當(dāng)圖神經(jīng)網(wǎng)絡(luò)采用了上述結(jié)構(gòu)之后,模型中就同時(shí)存在了兩種節(jié)點(diǎn)特征聚集的方式,分別是橫向擴(kuò)展的鄰域特征聚集方式用來(lái)提取圖的局部結(jié)構(gòu)信息,以及縱向擴(kuò)展的層間特征聚集方法用來(lái)提取圖的層級(jí)表征信息。

橫向特征聚集方式對(duì)應(yīng)Graph-Inception結(jié)構(gòu)中的GCN,為每個(gè)圖卷積神經(jīng)網(wǎng)絡(luò)設(shè)置不同尺寸的卷積核,以提取目標(biāo)節(jié)點(diǎn)多尺度感受野內(nèi)的鄰域表征信息。本文選擇了文獻(xiàn)[5]中提出的圖卷積神經(jīng)網(wǎng)絡(luò),如式(4)所示,利用切比雪夫多項(xiàng)式對(duì)原始圖卷積核[4]進(jìn)行化簡(jiǎn)。其中K代表切比雪夫多項(xiàng)式的階數(shù),特別地,也可以代表圖卷積核的尺寸,通過(guò)改變K值便能改變圖卷積核的感受野以提取到不同尺寸鄰域內(nèi)的信息。

另一方面,既然深層特征存在問(wèn)題,那就將淺層的特征保留下來(lái),通過(guò)對(duì)一些較小尺寸的卷積核進(jìn)行組合,將所有卷積層的輸出結(jié)果拼接為一個(gè)高維特征圖,以實(shí)現(xiàn)對(duì)模型深度擴(kuò)展的等效?？v向特征聚集方式就是基于這樣的思想,通過(guò)對(duì)不同感受野下GCN的輸出進(jìn)行拼接,使結(jié)果包含不同層的層級(jí)表征。一方面,這樣的做法即使不需要深層的網(wǎng)絡(luò)模型也能提取到豐富的特征信息;另一方面,采用這樣的多頭機(jī)制,即使某一個(gè)圖卷積神經(jīng)網(wǎng)絡(luò)的輸入存在噪聲或擾動(dòng)時(shí),分類子網(wǎng)的權(quán)重會(huì)向其他GCN中的信息進(jìn)行轉(zhuǎn)移,從而起到了一定的修正和優(yōu)化作用。

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

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

Y=Softmax(MLP(H))

(7)

式中:Y代表模型預(yù)測(cè)節(jié)點(diǎn)的標(biāo)簽矩陣。

2.3 算法步驟

本節(jié)將給出基于子圖劃分的多尺度節(jié)點(diǎn)分類方法的具體步驟:

Step1首先利用預(yù)處理方法對(duì)原始圖G進(jìn)行子圖劃分。

Step2將每個(gè)子圖中的所有節(jié)點(diǎn)視為一個(gè)batch,輸入Graph-Inception網(wǎng)絡(luò),并經(jīng)過(guò)MLP處理后得到模型的輸出。

Step3使用模型預(yù)測(cè)的分類結(jié)果與真實(shí)標(biāo)簽計(jì)算負(fù)對(duì)數(shù)似然損失NLL,并計(jì)算損失函數(shù)的梯度,利用梯度對(duì)參數(shù)進(jìn)行優(yōu)化。

Step4開(kāi)始訓(xùn)練,重復(fù)Step 2、Step 3,直至損失函數(shù)連續(xù)10次迭代后不再下降時(shí),停止訓(xùn)練。

3 實(shí)驗(yàn)仿真與分析

3.1 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集介紹

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

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

表1 數(shù)據(jù)集主要參數(shù)

3.2 模型與超參數(shù)設(shè)置

模型設(shè)置:本文中的模型采用了圖2所示的網(wǎng)絡(luò)結(jié)構(gòu),并采用4個(gè)GCN網(wǎng)絡(luò),RNN采用LSTM網(wǎng)絡(luò)。

超參數(shù)設(shè)置:參照文獻(xiàn)[10]中采用四種感受野K的組合,并分別設(shè)置為1、2、3、4;參照文獻(xiàn)[9]將PPI數(shù)據(jù)集劃分為50個(gè)子圖,將Reddit數(shù)據(jù)集劃分為1 500個(gè)子圖,將Amazon數(shù)據(jù)集劃分為200個(gè)子圖;初始學(xué)習(xí)率設(shè)置為0.005;每經(jīng)過(guò)200個(gè)epoch將學(xué)習(xí)率降低為原來(lái)的0.5倍;batch-size設(shè)置為128。選擇Adam作為參數(shù)優(yōu)化器,使用L2正則化防止訓(xùn)練時(shí)過(guò)擬合,選擇負(fù)對(duì)數(shù)似然函數(shù)NLL作為損失函數(shù)。

3.3 準(zhǔn)確率分析

為了驗(yàn)證本文方法的有效性,采用N-GCN和Cluster-GCN作為對(duì)比模型進(jìn)行實(shí)驗(yàn),檢測(cè)準(zhǔn)確率對(duì)比如表2所示?？梢钥闯?本節(jié)提出的Graph-Inception網(wǎng)絡(luò)在節(jié)點(diǎn)分類任務(wù)中的準(zhǔn)確率表現(xiàn)上取得了明顯的提升。與Cluster-GCN相比,在總節(jié)點(diǎn)數(shù)較少的PPI數(shù)據(jù)集上,本文方法的準(zhǔn)確率提高了0.44百分點(diǎn);而在節(jié)點(diǎn)數(shù)目相對(duì)較多的Amazon和Reddit數(shù)據(jù)集上,本文方法分別得到了0.84百分點(diǎn)和3.07百分點(diǎn)的提升?？梢钥闯?本文方法對(duì)于規(guī)模越大的數(shù)據(jù)集準(zhǔn)確率提升越明顯,這是因?yàn)樵谧訄D劃分的過(guò)程中,一些邊被屏蔽導(dǎo)致部分信息丟失,大數(shù)據(jù)集仍能保留多數(shù)特征信息,而越小的數(shù)據(jù)集由于信息損失后不足以保證自身表示的完整性。

另一方面,從表2中數(shù)據(jù)看出,使用N-GCN對(duì)Reddit數(shù)據(jù)進(jìn)行處理時(shí),由于數(shù)據(jù)集過(guò)大以及N-GCN算法機(jī)制的原因,導(dǎo)致訓(xùn)練時(shí)占用內(nèi)存過(guò)高,導(dǎo)致GPU溢出,無(wú)法正常進(jìn)行訓(xùn)練。側(cè)面驗(yàn)證了基于子圖劃分的預(yù)處理方法的必要性。

表2 模型檢測(cè)準(zhǔn)確率(%)

3.4 計(jì)算效率分析

為了驗(yàn)證本文方法的計(jì)算效率,表3展示了N-GCN和Cluster-GCN以及Graph-Inception方法在三個(gè)基準(zhǔn)數(shù)據(jù)集上的計(jì)算耗時(shí)對(duì)比,以測(cè)試集中所有節(jié)點(diǎn)的測(cè)試時(shí)間作為評(píng)價(jià)指標(biāo)?？梢钥闯?Cluster-GCN由于采用了子圖劃分的數(shù)據(jù)預(yù)處理方法,部分節(jié)點(diǎn)之間不用進(jìn)行信息交換,所需的訓(xùn)練時(shí)間最短;N-GCN由于采用了多個(gè)GCN的組合,所需訓(xùn)練時(shí)間較多;而本文方法則是在N-GCN的基礎(chǔ)上,對(duì)數(shù)據(jù)進(jìn)行了預(yù)處理,優(yōu)化了特征提取過(guò)程。因此本文方法訓(xùn)練所需的時(shí)間,與N-GCN相比較少,而與Cluster-GCN相比較多。

表3 模型檢測(cè)耗時(shí)對(duì)比 單位:s

3.5 損失值分析

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

圖3 Reddit數(shù)據(jù)集損失值變化

圖4 PPI數(shù)據(jù)集損失值變化

圖5 Amazon數(shù)據(jù)集損失值變化

3.6 子圖劃分分析

圖6-圖8展示了采用不同子圖數(shù)下本文方法在三個(gè)基準(zhǔn)數(shù)據(jù)集上的檢測(cè)準(zhǔn)確率和時(shí)間變化?？梢钥闯?隨著子圖數(shù)的增加,檢測(cè)時(shí)間也隨之變短,這是由于每個(gè)子圖內(nèi)節(jié)點(diǎn)數(shù)也在逐漸減少;通過(guò)實(shí)驗(yàn),數(shù)據(jù)集PPI、Reddit和Amazon的檢測(cè)準(zhǔn)確率分別在子圖數(shù)為50、1 500和200處取得最優(yōu)值。因此為了保證在檢測(cè)時(shí)間盡可能短的情況下檢測(cè)準(zhǔn)確率較高,選擇此組子圖數(shù)作為模型的超參數(shù)。

圖7 不同子圖數(shù)Reddit數(shù)據(jù)集檢測(cè)準(zhǔn)確率、時(shí)間變化

圖8 不同子圖數(shù)Amazon數(shù)據(jù)集檢測(cè)準(zhǔn)確率、時(shí)間變化

3.7 多尺度感受野分析

為了驗(yàn)證Graph-Inception方法中感受野對(duì)模型檢測(cè)準(zhǔn)確率的影響,表4展示了不同尺度感受野組合下本文方法在三個(gè)基準(zhǔn)數(shù)據(jù)集上的準(zhǔn)確率變化,其中K表示采用的k[1,K]的感受野組合?？梢钥闯?模型的檢測(cè)準(zhǔn)確率在如下范圍內(nèi)隨K值變大而增高,這是由于感受野越大,提取到的層級(jí)特征越豐富。但是感受野過(guò)大同樣會(huì)帶來(lái)過(guò)平滑現(xiàn)象導(dǎo)致的檢測(cè)準(zhǔn)確率降低,這在規(guī)模較小的PPI數(shù)據(jù)集上得到了體現(xiàn)。

表4 不同感受野下檢測(cè)準(zhǔn)確率對(duì)比

4 結(jié) 語(yǔ)

本文介紹了一種基于子圖劃分的多尺度節(jié)點(diǎn)分類方法,旨在從網(wǎng)絡(luò)結(jié)構(gòu)和特征聚集方式兩方面抑制圖神經(jīng)網(wǎng)絡(luò)中的過(guò)平滑問(wèn)題。首先以子圖劃分的數(shù)據(jù)預(yù)處理方式改變?cè)紙D中的鄰域結(jié)構(gòu),然后通過(guò)使用不同尺寸卷積核的組合對(duì)目標(biāo)節(jié)點(diǎn)多尺度下的鄰域特征信息進(jìn)行融合。最后通過(guò)實(shí)驗(yàn)證明,本文方法能夠有效抑制圖神經(jīng)網(wǎng)絡(luò)中的過(guò)平滑問(wèn)題,在基準(zhǔn)節(jié)點(diǎn)分類數(shù)據(jù)集PPI、Reddit和Amazon上的預(yù)測(cè)準(zhǔn)確率都取得了不同程度的提高。