基于隨機重構(gòu)圖結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)分類算法

劉穎穎,葉海良,楊 冰,曹飛龍

(中國計量大學 理學院,浙江 杭州 310018)

圖是基本的數(shù)據(jù)結(jié)構(gòu),在實際生活中這些數(shù)據(jù)來自社交媒體、交通、語言學和化學[1-3]等領(lǐng)域。圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Networks, GNN)[4]架構(gòu)廣泛應(yīng)用于節(jié)點分類[5-7]、圖分類[8-9]、鏈接預(yù)測[10-11]等任務(wù)中,它通過對這些圖結(jié)構(gòu)數(shù)據(jù)執(zhí)行鄰居聚合,實現(xiàn)特征提取。

經(jīng)典的圖卷積網(wǎng)絡(luò)(Graph Convolutional Networks, GCNs)[12]及其變體在消息傳遞機制中的關(guān)鍵步驟是特征聚合,即節(jié)點從拓撲鄰居中聚合信息。然而,最近的研究揭示了特征聚合過程中的一些問題。Li等[11]研究發(fā)現(xiàn),圖神經(jīng)網(wǎng)絡(luò)對在節(jié)點特征執(zhí)行聚合的過程中,破壞了原始特征空間的節(jié)點相似性,這意味著節(jié)點在其鄰居節(jié)點中獲得信息量受限。為了解決此問題,Wei等人[13]通過實驗證明了k-近鄰(k-nearest neighbor,kNN)圖結(jié)構(gòu)[14]可以作為原始圖結(jié)構(gòu)信息的補充,在特征聚合過程中捕獲比原始鄰接矩陣更多的相似信息。

另外,大多數(shù)GCNs的特征傳播過程有特定的傳播規(guī)則,這種確定性傳播[12,15]往往使節(jié)點對其鄰域有很大的依賴性,使節(jié)點在更新的過程中很輕易地被數(shù)據(jù)潛在的噪聲所誤導。一些研究通過轉(zhuǎn)換節(jié)點信息[15-17]或重構(gòu)圖結(jié)構(gòu)[18-19]等方法來解決這一問題。Feng等[15]通過設(shè)計的隨機傳播將局部節(jié)點信息傳遞到其鄰域,不足的是該模型隨機刪除部分節(jié)點信息從而損失了完整節(jié)點信息。GraphSAGE[16]通過訓練一組聚合器函數(shù)聚合局部鄰域的特征來生成每個節(jié)點的單個嵌入,不足的是并沒有繼續(xù)通過轉(zhuǎn)換節(jié)點鄰域探索重構(gòu)的圖結(jié)構(gòu)。Du等[19]將圖神經(jīng)網(wǎng)絡(luò)拓展到局部特征以提取任意圖結(jié)構(gòu)數(shù)據(jù),但該方法通過控制濾波器接受域來控制局部特征輸入,導致了網(wǎng)絡(luò)模型在整個輸入圖中過于關(guān)注相鄰的圖結(jié)構(gòu)局部視角。

此外,已有研究[20-22]發(fā)現(xiàn)使用跨層的跳躍連接來加強淺層信息,可以加強淺層特征在架構(gòu)中的表達能力和指導效率。Chen等[23]利用恒等映射和初始殘差連接的組合擴充了模型的層數(shù),保證了當模型疊加更多層時模型的淺層信息仍然可以被補充。Li等[24]利用殘差連接[25]和擴張卷積[26]的結(jié)合,通過加強淺層信息的指導解決了模型梯度消失的問題。以上模型存在的問題是提取的淺層節(jié)點與深層更新節(jié)點沒有做信息變換,因此并沒有真正增加模型輸入的多樣性。

為解決上述問題,本文設(shè)計了基于隨機重構(gòu)圖結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)分類算法。原始圖結(jié)構(gòu)中自適應(yīng)地融合kNN圖結(jié)構(gòu),可以有效保持同類節(jié)點相似性。通過隨機節(jié)點特征轉(zhuǎn)換節(jié)點鄰域信息,使重構(gòu)圖上的節(jié)點特征在傳播過程中具有隨機性,解決了節(jié)點對鄰域依賴性高的問題。此外,模型對初始信息進行多支提取,額外的消息傳遞可以幫助圖神經(jīng)網(wǎng)絡(luò)更好地吸收和嵌入淺層特征信息。

總之,基于隨機重構(gòu)圖結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)分類算法是重構(gòu)圖結(jié)構(gòu)和隨機特征結(jié)合的方法,整體框架上加入多支淺層特征,使模型更有效地完成節(jié)點分類任務(wù)。首先,原始圖結(jié)構(gòu)根據(jù)隨機特征所得到的分數(shù)向量自適應(yīng)地與kNN圖結(jié)構(gòu)信息融合,得到隨機重構(gòu)圖。進一步,模型中加入基于層數(shù)自適應(yīng)的多支淺層信息提取塊,使模型隨著層數(shù)的加深將更多淺層信息補充到圖結(jié)構(gòu)中。最后,提出的方法使用分類損失和自監(jiān)督損失聯(lián)合優(yōu)化來學習模型參數(shù)。模型在半監(jiān)督和全監(jiān)督節(jié)點分類任務(wù)上取得較高精度,在數(shù)據(jù)集上的實驗結(jié)果驗證了所提模型的正確性和有效性。

1 基于隨機重構(gòu)圖結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)分類算法

1.1 前期準備

圖相似度量學習:為了捕獲特征空間中節(jié)點的圖結(jié)構(gòu)信息,基于節(jié)點特征矩陣構(gòu)造kNN圖,定義Ak為kNN圖的鄰接矩陣,Dk為kNN圖的度矩陣。本文采用余弦相似性方法用兩個節(jié)點的向量夾角的余弦值度量節(jié)點之間的差異。給定的節(jié)點對xi,xj,計算其余弦相似度為

(1)

根據(jù)相似度得分為每個節(jié)點選擇k個最相似節(jié)點,建立節(jié)點之間的相關(guān)性,從而構(gòu)造出kNN圖結(jié)構(gòu)。

1.2 整體網(wǎng)絡(luò)框架

本文設(shè)計了基于隨機重構(gòu)圖結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)分類算法來保持同類節(jié)點相似性,并解決聚合過程中對節(jié)點對鄰域依賴性高的問題,模型的概述如圖1。首先,對原始圖同時執(zhí)行kNN構(gòu)造k近鄰圖,以及隨機特征變換得到隨機特征,并根據(jù)權(quán)重值增強隨機特征中保留的節(jié)點信息。其次,通過自適應(yīng)特征融合和自適應(yīng)自環(huán)學習完成圖結(jié)構(gòu)重構(gòu),從而自適應(yīng)地調(diào)整節(jié)點特征之間的信息,完成節(jié)點特征的更新。最后,加入提取的多支淺層信息,通過對參數(shù)的控制實現(xiàn)當層數(shù)加深時補充更多的淺層信息。

圖1 基于隨機重構(gòu)圖結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)分類算法框架Figure 1 Framework for classification algorithm of graph neural network based on random reconstructed graph structure

多支淺層信息提取塊:隨著網(wǎng)絡(luò)深度的增加,節(jié)點特征將逐漸收斂到相同的值,從而導致節(jié)點難以區(qū)分。為了提高節(jié)點分類性能,在模型中加入提取的多支淺層信息,其節(jié)點信息由參數(shù)α(l)控制,參數(shù)α(l)隨著分支的數(shù)量遞增,通過補充更多的淺層信息。在中間層中多支淺層信息的第l支特征定義為

(2)

(3)

隨機特征變換:隨機特征變換轉(zhuǎn)換了鄰域節(jié)點信息,它控制著在聚合過程中特征與重構(gòu)圖結(jié)構(gòu)的隨機傳播,隨機特征變換如圖2所示。隨機特征變換有兩個步驟。首先,節(jié)點特征與丟棄矩陣相乘,對節(jié)點信息進行部分丟棄;其中,丟棄矩

圖2 輸入層中隨機圖結(jié)構(gòu)重構(gòu)圖Figure 2 Random graph structure reconstruction graph in the input layer

經(jīng)過變換得到的隨機特征為

(4)

式(4)中,θ=diag(k1,k2,…,kn)為丟棄矩陣,特別地,ki符合伯努利分布,即ki=Bernoulli(1-ρ),ρ為丟棄因子控制著初始特征的向量置零比例。att為根據(jù)初始特征計算的每個節(jié)點的權(quán)重系數(shù),其表達式為

att=δ(HWran+bran)。

(5)

隨機圖結(jié)構(gòu)重構(gòu):本文設(shè)計一種自適應(yīng)融合機制,在圖結(jié)構(gòu)和節(jié)點特征融合時嵌入分數(shù)向量權(quán)重系數(shù)。原始圖結(jié)構(gòu)中融合kNN圖可以加強節(jié)點之間的相關(guān)性,解決在傳統(tǒng)特征聚合過程中節(jié)點相似性破壞的問題。在獲得隨機特征和kNN圖之后,第k層的融合傳播矩陣為

(6)

(7)

(8)

式(8)中,Φ(m)為自環(huán)權(quán)重矩陣,v(m)為自環(huán)偏置。重構(gòu)圖的傳播矩陣為

(9)

(10)

1.3 損失函數(shù)

在文中的半監(jiān)督和全監(jiān)督任務(wù)中,為有效的保持節(jié)點的相似性,在其損失函數(shù)上設(shè)計一個分類損失和自監(jiān)督學習損失的組合。

分類損失:針對節(jié)點分類任務(wù)對樣本標簽進行軟化處理以獲取更光滑的損失函數(shù):

(11)

自監(jiān)督學習損失:采用自監(jiān)督學習策略[25],從給定的節(jié)點對的獲取偽標簽,預(yù)測節(jié)點之間的特征相似性,有效地保持特征和結(jié)構(gòu)的相似性。其損失函數(shù)為

(12)

因此,該框架最終完整的損失函數(shù)為

L=Lclass+Lself。

(13)

2 實驗及結(jié)果分析

2.1 數(shù)據(jù)集

本文的實驗使用三個引文網(wǎng)絡(luò)數(shù)據(jù)集:Cora、Citeseer和Pubmed。表1統(tǒng)計了實驗中三個基準數(shù)據(jù)集的組成。

表1 實驗中使用的數(shù)據(jù)集的統(tǒng)計數(shù)據(jù)Table 1 Statistics of datasets used in experiments

Cora是由機器學習相關(guān)論文組成的數(shù)據(jù)集。它有2708個樣本點,每個樣本點都有1433個特征。樣本點表示科學論文,這些科學論文分為以下七個類別:1)基于案例;2)遺傳算法;3)神經(jīng)網(wǎng)絡(luò);4)概率法;5)強化學習;6)規(guī)則學習;7)理論。每個樣本點都與其他樣本點存在聯(lián)系,因此樣本點組成了一個連通的圖。

Citeseer是一個關(guān)于論文之間引用或被引用的數(shù)據(jù)集,由3 327篇論文的圖表組成。論文分為六類:代理、人工智能、數(shù)據(jù)庫、信息檢索、機器語言和HCI人機交互。數(shù)據(jù)集有兩種文件:.content文件和.cites文件。

Pubmed是由19 717篇與糖尿病相關(guān)論文組成的數(shù)據(jù)集。Pubmed中的每篇論文都由TF-IDF加權(quán)詞向量表示。TF-IDF表示評估其中一份文件的重要程度。

2.2 實驗設(shè)置

實驗以Python3.7作為實驗環(huán)境進行網(wǎng)絡(luò)的搭建和訓練。實驗以精度(Accuracy, A)作為節(jié)點分類的性能評估指標。本文對基準數(shù)據(jù)集進行半監(jiān)督訓練和全監(jiān)督訓練,對每個數(shù)據(jù)集里的文件進行訓練、驗證和測試。實驗學習率為0.02,L2正則化系數(shù)設(shè)置為5e-4,線性層的丟棄率為0.8,隱藏層的神經(jīng)元數(shù)量為128。本模型采用自適應(yīng)學習率優(yōu)化算法(Adaptive moment estimation,Adam)[28]訓練網(wǎng)絡(luò)。多支淺層信息的放大系數(shù)α取值范圍為[1,5],隨機特征的丟棄因子ρ取值范圍為[0.1,1],自環(huán)的系數(shù)μ取值范圍為[0.000 1,0.1],損失系數(shù)λ取值范圍為[0.001,100]。本文給定取值范圍驗證集精度,為不同數(shù)據(jù)集和模型深度調(diào)整參數(shù)。

2.3 對比方法

為評估本文模型節(jié)點分類任務(wù)的成效,我們選取了具有代表性的基準圖神經(jīng)網(wǎng)絡(luò)模型進行精度比較。首先,我們列出圖卷積模型:GCNs[12]、圖注意力網(wǎng)絡(luò)(Graph Attention Networks,GAT)[10]、近似個性化傳播(Approximate Personalized Popagation of Nural Pedictions, APPNP)[29]、GCNII[23]、跳躍知識網(wǎng)絡(luò)(Jumping Knowledge Networks, JKNet)[30]。另外,在半監(jiān)督任務(wù)中還增加比較了近幾年的先進模型:自回歸滑動圖神經(jīng)網(wǎng)絡(luò)(Graph neural networks with convolutional arma filters, ARAM)[31]、節(jié)點相似性圖卷積網(wǎng)絡(luò)(Similarity Preserving Graph Convolutional Networks, SimP-GCN)[13]。最后,在全監(jiān)督任務(wù)中還增加比較了近幾年的先進模型:殘差網(wǎng)絡(luò)(Residual Network, ResNet)[21]、節(jié)點分類圖正則神經(jīng)網(wǎng)絡(luò)(Neural Graph Learning-NodeNet, NodeNet)[32]、幾何圖卷積網(wǎng)絡(luò)(Geometric Graph Convolutional Networks, Geom-GCN)[33]、邊蒸餾(Link Distillation , LinkDist)[34]、和隨機點對的對比蒸餾(Contrastive Training With Negative Links , CoLinkDist)[34]。本文采用4層的模型,為了公平起見,所有實驗的默認網(wǎng)絡(luò)層數(shù)均設(shè)置為4層,并且對三個數(shù)據(jù)集以同樣的比例劃分,進行相同的訓練和測試。

2.4 實驗結(jié)果

為全面的評價模型對節(jié)點分類任務(wù)的有效性,我們分別在Cora、Citeseer和Pubmed數(shù)據(jù)集做了半監(jiān)督實驗和全監(jiān)督實驗。

半監(jiān)督實驗如表2。對于三個基準數(shù)據(jù)集,我們將每個類的節(jié)點隨機分割為60%的訓練集、20%的驗證集、20%測試集。SimP-GCN和GCNII模型都是半監(jiān)督節(jié)點分類任務(wù)中實現(xiàn)先進性能的方法。從結(jié)果上看,GCNII和ARMA在卷積方式上的改進,使節(jié)點的更新學習方式更加高效。SimP-GCN加入kNN圖結(jié)構(gòu)信息保持了特征相似性,持續(xù)的提高了節(jié)點分類精度。本文模型在重構(gòu)圖結(jié)構(gòu)的基礎(chǔ)上使節(jié)點特征隨機性傳播,解決了節(jié)點對鄰域依賴性高的問題,優(yōu)化了特征聚合過程,使精度進一步提高。

表2 半監(jiān)督節(jié)點分類精度結(jié)果匯總

所提出方法在三個數(shù)據(jù)集上的全監(jiān)督實驗結(jié)果如表3。GCNII、JKNet、ResGCN為深層模型,其方法著力于解決過平滑問題,成功加深模型層數(shù)從而提高節(jié)點分類精度。本文模型在全監(jiān)督節(jié)點分類的數(shù)據(jù)結(jié)果表明,當模型的層數(shù)為淺層時已表現(xiàn)出優(yōu)越性,特別是其結(jié)果已優(yōu)于其他模型在深層模型的結(jié)果。隨機圖結(jié)構(gòu)在特征聚合過程中有效的保持了節(jié)點相似度,網(wǎng)絡(luò)架構(gòu)增加多支淺層提取,在特征更新時補充淺層信息,進一步了提升節(jié)點分類性能。

表3 全監(jiān)督節(jié)點分類精度結(jié)果匯總

2.5 深度擴展模型

為了驗證多支淺層信息對增加模型深度的作用,我們對模型深度進行了拓展,并對比了單支主干模型與添加多支淺層信息的模型在半監(jiān)督實驗上的節(jié)點分類性能。在Cora、Citeseer和Pubmed數(shù)據(jù)集進行2、4、8、16、32、64、128層的深層拓展實驗。

根據(jù)圖3實驗結(jié)果表明,單支主干模型在層數(shù)超過4層時,精度發(fā)生明顯的下降。其原因隨著網(wǎng)絡(luò)層數(shù)加深GCN遭受過平滑的問題。節(jié)點的特征將趨于收斂到相同的值,節(jié)點的區(qū)分度下降,后續(xù)的節(jié)點分類任務(wù)的性能降低。添加多支淺層信息的模型突破了4層以上的網(wǎng)絡(luò)層數(shù),精度在網(wǎng)絡(luò)層數(shù)逐漸增加時仍然保持穩(wěn)定的精度。本文模型通過通過多支淺層特征提取在進行特征更新時補充淺層信息,層與層之間的跳躍連接為模型梯度傳播增加了額外的路徑,對緩解過平滑問題起到了一定作用。

圖3 不同深度的分類精度結(jié)果匯總Figure 3 Summary of classifification accuracy results with various depths

2.6 超參數(shù)討論

本小節(jié)討論了幾個超參數(shù)取不同值時對節(jié)點分類的影響效果,結(jié)果如圖4所示。我們研究了損失系數(shù)λ、自環(huán)系數(shù)μ、隨機特征丟棄因子系數(shù)ρ、多支淺層信息的放大系數(shù)α這四個超參數(shù)取不同值時,對節(jié)點分類性能的影響。實驗先選用初始化的模型參數(shù),進一步逐一變換參數(shù),以獲得每個參數(shù)單獨的影響效果。

圖4 超參數(shù)實驗節(jié)點分類精度結(jié)果匯總Figure 4 Summary of classifification accuracy results with hyperparameter experiment

損失系數(shù)調(diào)整了分類損失和自監(jiān)督學習損失的貢獻度。在Cora、Citeseer數(shù)據(jù)集上分類損失占主導作用,在Pubmed數(shù)據(jù)集上增加自監(jiān)督學習損失的比例使結(jié)果精度進一步突破,因此損失系數(shù)λ在Cora、Citeseer、Pubmed三個數(shù)據(jù)集上分別選擇為0.01,10,100。隨機特征丟棄因子其變化程度評估模型的魯棒性,在一定范圍內(nèi)對層傳遞的特征進行干擾時,節(jié)點分類精度沒有明顯的下降趨勢,因此隨機特征丟棄因子系數(shù)ρ在Cora、Citeseer、Pubmed三個數(shù)據(jù)集上分別選擇為0.2,0.3,0.2。自環(huán)系數(shù)可以為單個節(jié)點調(diào)整不同的信息,因此自環(huán)系數(shù)μ在Cora、Citeseer、Pubmed三個數(shù)據(jù)集上分別選擇為0.1,0.1,0.001。多支淺層信息的放大系數(shù)調(diào)節(jié)了每層加入淺層信息的比例,不同的系數(shù)對精度的影響說明淺層信息對模型的指導意義,因此多支淺層信息的放大系數(shù)α在Cora、Citeseer、Pubmed三個數(shù)據(jù)集上分別選擇為3,2,2。

2.7 消融分析

本節(jié)討論了模型中不同模塊對實驗性能的影響,構(gòu)建了8組自身消融對比實驗。我們在實驗設(shè)置相同的條件下,對Cora、Citeseer、Pubmed數(shù)據(jù)集在原模型的基礎(chǔ)上進行對比實驗。實驗結(jié)果如表4,表中“-”表示模型中不增加該模塊,“√”表示模型中使用該模塊。特別地,H表示直接輸入初始特征,Hran表示對初始特征做丟棄和增強操作,融合機制表示將kNN和輸入特征自適應(yīng)融合。

表4 消融實驗節(jié)點分類精度結(jié)果匯總Table 4 Summary of classifification accuracy results with ablation experiment

模型A結(jié)果精度不能優(yōu)于模型B結(jié)果精度,這驗證了學習圖結(jié)構(gòu)和節(jié)點信息都是必不可少的;模型C、模型D與模型E分別驗證了隨機特征中丟棄和增強的作用,通過結(jié)果表明單獨使用其中一個模塊并不如兩者結(jié)合使用,驗證了增強局部節(jié)點信息對協(xié)調(diào)圖結(jié)構(gòu)數(shù)據(jù)的重要性。模型F在kNN圖結(jié)構(gòu)信息和原始圖結(jié)構(gòu)融合過程加入自適應(yīng)優(yōu)化操作。它進一步支持了簡單地結(jié)合結(jié)構(gòu)和特征是不夠的,驗證了重構(gòu)圖結(jié)構(gòu)融合過程的重要性;模型G為模型中每一層的圖結(jié)構(gòu)補充了多樣性的淺層信息,并緩解網(wǎng)絡(luò)加深過程中過平滑問題的發(fā)生;最后,模型H加入自監(jiān)督損失函數(shù),自監(jiān)督學習策略可以捕獲復雜特征的相似關(guān)系。

2.8 算法時間復雜度分析

在相同的實驗條件下,在Cora、Citeseer、Pubmed 3個數(shù)據(jù)集上對比了本文模型與GCN每輪的實驗時間,通過表5中的實驗結(jié)果分析模型的算法時間復雜度。本文模型對節(jié)點進行相似度計算得到kNN圖結(jié)構(gòu),并通過隨機特征變換丟棄部分節(jié)點特征。這些操作雖然增加了模型的訓練時間,但本文模型的精度得到了一定的提升。

表5 對比實驗時間結(jié)果匯總Table 5 Comparison of experimental time results summary s

3 結(jié) 語

本文提出了基于隨機重構(gòu)圖結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)分類算法,以解決大多數(shù)GCNs在特征傳播過程中出現(xiàn)相似性被破壞和節(jié)點過于依賴鄰域的問題。首先,輸入圖根據(jù)隨機特征得到的分數(shù)向量對原始圖和kNN圖兩種圖結(jié)構(gòu)自適應(yīng)地構(gòu)造出隨機圖結(jié)構(gòu)。然后,通過增加多支淺層信息提取單元優(yōu)化網(wǎng)絡(luò)架構(gòu),在特征更新時補充淺層信息。最后,在分類損失的基礎(chǔ)上加入了自監(jiān)督學習損失,更好地保持節(jié)點對的相似性,使節(jié)點分類任務(wù)的性能得到進一步提升。

本文在多個數(shù)據(jù)集的節(jié)點分類任務(wù)上分別做了半監(jiān)督和全監(jiān)督實驗,實驗結(jié)果均有0.9%～2.3%的提升。在未來,我們將有機會探索可變形的卷積層,構(gòu)建每一層不同k值的kNN圖結(jié)構(gòu),進一步挖掘圖結(jié)構(gòu)在圖神經(jīng)網(wǎng)絡(luò)的潛力。