公沛良 艾麗華

隨著信息科技的快速發(fā)展與推廣,人們收集、存儲數(shù)據(jù)的能力得到了飛速提升.在很多實際任務中我們可以很容易地獲取大量未標記(Unlabeled)的數(shù)據(jù),而標記數(shù)據(jù)往往是極其昂貴和耗時的,因此“標記數(shù)據(jù)少,未標記數(shù)據(jù)多”的現(xiàn)象較為明顯.若只使用少量有標記樣本進行學習,而忽略大量未標記數(shù)據(jù)是對數(shù)據(jù)資源的浪費.此外,由于圖結(jié)構(gòu)能夠很自然地用于對社交關系、生物分子結(jié)構(gòu)及出版物引用關系等復雜系統(tǒng)建模,因此以半監(jiān)督學習的方式分析基于圖建模的這類問題是非常關鍵且有意義的.節(jié)點分類作為圖分析中的一項重要研究,受到了越來越多研究者的關注,并廣泛用于社交關系網(wǎng)絡的用戶畫像[1]、引文網(wǎng)絡的文獻分類[2]、風控系統(tǒng)中的異常檢測[3]等領域.

近年來,國內(nèi)外學者提出了很多基于圖的傳統(tǒng)的學習方法用來有效地解決節(jié)點分類問題,這類方法通常將問題用一個包括節(jié)點及邊的圖 G(V,E)來建模,圖上的節(jié)點集 V 表示樣本,每個節(jié)點一般會有一些特征描述且與某個固定的類別標簽相關聯(lián),而邊集 E 一般是有權值的,并且權值的大小表示樣本之間的相似性程度.當給定部分有標記的圖時,通過使用少量有標記的數(shù)據(jù)和大量無標記數(shù)據(jù)的特征信息在已構(gòu)建的圖結(jié)構(gòu)上共同學習一個模型,從而實現(xiàn)對未標記節(jié)點的分類.基于圖的傳統(tǒng)分類方法,在發(fā)展過程中主要形成了以下分支,一類是基于標簽傳播思想的設計方法[4-8];另一類是基于圖嵌入的方法[9-12].基于標簽傳播思想的方法主要是將有標記樣本的標簽信息在圖上傳播,并利用圖拉普拉斯正則項約束有較大邊權重的相鄰節(jié)點具有相同的類別.Zhu 等[4]提出的標簽傳播(Label propagation)方法,使用一個約束的標簽分配函數(shù),對每個未標記樣本實例選擇相鄰節(jié)點中類別標簽數(shù)量最多的作為自己的標簽類型,隨著類別標簽的不斷傳播,使得最終緊密相連的節(jié)點數(shù)據(jù)有相同的類別標簽.Talukdar 等[5]提出的方法是標簽傳播方法的一種變體,它允許對已標記節(jié)點的預測標簽進行改變,引入了節(jié)點的不確定性,這種設計方式解決了標簽傳播算法中某些已標記信息是噪聲卻無法在傳播過程中對其進行修復的問題.Belkin 等[6]提出了流行正則(Manifold regularization)方法,目標函數(shù)設計時考慮了再生核希爾伯特空間(Reproducing kernel Hilbert spaces,RKHS)中參數(shù)化的核函數(shù)且正則項中引入了樣本的幾何邊緣分布信息.Weston 等[7]提出的半監(jiān)督嵌入(Semi-supervised embedding)方法將適用于淺層半監(jiān)督學習技術(如內(nèi)核方法)的非線性嵌入算法應用到了深層結(jié)構(gòu)中,并且拓展了目標函數(shù)的正則項.迭代分類算法(Iterative classification algorithm,ICA)[8]則是在評估局部分類器與分配新標簽之間采用一個迭代的過程,在每次迭代時,根據(jù)其相鄰節(jié)點的當前預測標簽對圖上節(jié)點數(shù)據(jù)進行分類.

基于圖嵌入的方法,其主要動機是希望對每個節(jié)點學習一個低維的向量表示,同時使該向量表示盡可能的保持原來的拓撲結(jié)構(gòu)關系及特征屬性.Perozzi 等[9]提出的深度游動(Deepwalk)算法作為經(jīng)典的圖嵌入方法,它在圖上利用隨機游動的路徑構(gòu)造節(jié)點序列,然后使用SkipGram 模型[13]更新學習節(jié)點的表示,最終利用學習到的低維向量實現(xiàn)對圖上節(jié)點數(shù)據(jù)的分類.Line[10]和Node2Vec[11]方法則使用更復雜的隨機游動模型或廣度優(yōu)先搜索策略進一步拓展了深度游動算法.Yang 等[12]提出了基于圖嵌入的半監(jiān)督學習框架,通過注入類別標簽的方式來學習每個節(jié)點的嵌入表示,實現(xiàn)對圖上節(jié)點的分類.

雖然基于圖的傳統(tǒng)的分類方法在節(jié)點分類任務上已取得了一定的分類效果,但是這類方法仍存在著一些不足.例如標簽傳播等算法在對未標記節(jié)點分類時只使用了類別標簽和圖結(jié)構(gòu)信息,而沒有利用節(jié)點本身的特征屬性信息.深度游動等算法只使用了圖結(jié)構(gòu)信息來學習低維特征表達,沒有利用標簽信息來輔助節(jié)點表示的學習.沒有充分利用已有的信息會使最終分類精度及泛化性能受到較大影響.

近幾年來,卷積神經(jīng)網(wǎng)絡在計算機視覺[14]、語音識別[15]等機器學習任務上取得了巨大的成功,但由于圖數(shù)據(jù)的每個節(jié)點鄰域大小不一,基于核的卷積在網(wǎng)格上的平穩(wěn)性已無法滿足,因此無法直接將卷積神經(jīng)網(wǎng)絡用到圖分析問題上,如何將卷積網(wǎng)絡拓展到處理圖數(shù)據(jù)的研究得到了越來越多的關注.根據(jù)卷積定義方式的不同,將卷積神經(jīng)網(wǎng)絡推廣到圖數(shù)據(jù)的方法概括為以下類別:一類是空間域上的卷積方法[16-19];另一類是譜域上的卷積方法[2,20-21].空間域上的卷積方法是在圖的節(jié)點上直接定義卷積,該方法遵循了傳統(tǒng)卷積神經(jīng)網(wǎng)絡的做法.對于圖上的每個節(jié)點,卷積被定義為對其鄰域內(nèi)所有節(jié)點的加權平均函數(shù),且加權函數(shù)表征了鄰域?qū)δ繕斯?jié)點的影響.該類方法的主要困難在于如何定義一個卷積算子來處理不同鄰域大小的節(jié)點數(shù)據(jù),并且保持卷積神經(jīng)網(wǎng)絡權值共享的屬性.Niepert 等[16]提出了一種從任意圖結(jié)構(gòu)中提取局部連通區(qū)域的通用方法,不過其采用的方法是將局部圖先轉(zhuǎn)換為一維的序列然后再使用傳統(tǒng)的一維卷積進行處理,該方法的主要缺點是轉(zhuǎn)換序列之前需要首先定義節(jié)點的優(yōu)先順序.Velickovic 等[17]提出圖關注網(wǎng)絡(Graph attention network)方法,采用注意力機制學習中心節(jié)點與每個相鄰節(jié)點特征向量之間的相關性來獲得不同的權重,并通過特征權重來聚合相鄰節(jié)點的特征表示.Gao 等[18]提出的大規(guī)模可學習圖網(wǎng)絡(Large-scale learnable GCN)方法,通過對鄰域節(jié)點的單個特征值大小排序以實現(xiàn)數(shù)據(jù)預處理,訓練時采用傳統(tǒng)的卷積方法.圖采樣與聚合(Graph sample and aggregate)方法[19]從一階鄰居中采樣固定數(shù)量的鄰居節(jié)點,并使用某種聚集方法(如平均值、最大池化或LSTM 等)將采樣節(jié)點信息聚合來更新中心節(jié)點的特征表示,其在大規(guī)模圖上表現(xiàn)出了較好的性能.

而譜域上的卷積方法基于圖傅里葉變換[22]及卷積理論等,先將圖上的節(jié)點數(shù)據(jù)及濾波器變換到譜域中進行運算,然后再將譜域上得到的乘積結(jié)果通過圖傅里葉逆變換轉(zhuǎn)回到空間域得到最終卷積結(jié)果.該類方法首先由Bruna 等[20]提出,之后Defferrard 等[21]使用多項式近似譜濾波器的方式加速了卷積運算.Kipf 等[2]使用一階線性逼近,進一步簡化了計算,取得了較好的分類效果.但是通常該類方法節(jié)點的鄰域組成較為簡單,每次聚集節(jié)點特征時只考慮到直接相連的鄰居節(jié)點信息,而忽視了非直接相連的鄰域信息,因此每次提取節(jié)點特征時不能夠充分利用到豐富的圖結(jié)構(gòu)信息,導致忽略了某些潛在的有利信息.即使可通過堆疊多層網(wǎng)絡實現(xiàn)對二階及更高階鄰居節(jié)點信息的整合,但是由于圖卷積網(wǎng)絡采用多層消息聚合的方案,當堆疊多層網(wǎng)絡后往往導致過平滑現(xiàn)象而使分類性能不增反降[23].目前GCN 通常局限于淺層網(wǎng)絡,一般使用2 層網(wǎng)絡時分類效果最好,雖然為了加深網(wǎng)絡可以使用殘差連接等技巧,但即使使用了這些技巧,也只是勉強保持性能不下降,并沒有提高性能.

針對這些問題,本文希望在保持淺層網(wǎng)絡的前提下,能更好地利用到更豐富的結(jié)構(gòu)信息來實現(xiàn)對節(jié)點特征表示的學習,提升最終的節(jié)點分類效果.本文提出在利用切比雪夫二階截斷展開多項式構(gòu)造卷積模塊的基礎上,精簡模型參數(shù),并進行重標準化等優(yōu)化處理,使得構(gòu)造的二階近似譜圖卷積模塊在每次更新節(jié)點特征表示時能夠更有效地融合二階鄰居節(jié)點的特征信息,從而進一步提高節(jié)點分類的精度.

1 二階近似譜圖卷積網(wǎng)絡模型

本文提出了一種用于對圖節(jié)點分類的二階鄰域近似譜圖卷積網(wǎng)絡模型,總體框架描述圖如圖1 所示.該網(wǎng)絡模型共包含兩層(隱層和輸出層),網(wǎng)絡的輸入數(shù)據(jù)為節(jié)點的屬性矩陣 Xin∈RN×C,它表示含有 N 個節(jié)點且每個節(jié)點使用 C 維向量進行描述的屬性矩陣.隱層(Hidden layer)使用本文設計的二階近似譜圖卷積模塊提取節(jié)點的隱特征表示,然后對得到的隱特征表示做非線性激活,得到隱層輸出Hout∈RN×H,其中H 為隱層特征維數(shù),并把結(jié)果送入網(wǎng)絡的輸出層(Output layer),在輸出層中使用構(gòu)造的卷積模塊對從隱層送入的數(shù)據(jù)做卷積處理,然后通過分類函數(shù)(Softmax function)預測每個節(jié)點的類別分布,得到Oout∈RN×W,其中W 為類別個數(shù),最終實現(xiàn)對節(jié)點的分類.

圖1 本文構(gòu)造的二階鄰域譜圖卷積網(wǎng)絡描述圖Fig.1 A schematic diagram of our two-order neighborhood spectral convolution network

下面分別從譜圖卷積理論基礎、二階近似卷積模塊設計、分層前向傳播網(wǎng)絡實現(xiàn)及模型的損失函數(shù)構(gòu)造等幾個方面對本文提出的模型進行詳細闡述.

1.1 譜圖卷積基礎

令 G(V,E)表示一個無向權重圖,其中 V 是頂點集,E?V ×V是邊集,A∈RN×N表示圖的鄰接矩陣,x∈RN表示圖信號,它的第 i個分量 xi表示 V中第 i 個頂點的信號值.標準化的圖拉普拉斯矩陣被定義為其中 IN是N階的單位矩陣,D∈RN×N是對角矩陣且對角元素值存在一組正交的特征向量和對應的非負特征值由于L 為對稱矩陣可對角化,經(jīng)譜分解有 L=UΛUT,其中Λ=diag{λ0,λ1,···,λN－1}∈RN×N.

當給定圖上的一個信號x∈RN,x經(jīng)圖傅里葉變換后,得到=UTx∈RN[24].圖傅里葉變換使我們能夠應用圖濾波器 g 實現(xiàn)對圖信號x的譜圖卷積.具體表示為

其中,* 代表卷積運算,g(Λ)=diag{g(λ0),g(λ1),···,g(λN－1)},它控制圖信號x中每個分量的頻率如何改變.然而通過式(1)應用圖濾波對信號x進行處理,需要對 L 進行譜分解,因此需要較高的計算代價.

Hammond 等[22]首先證明了使用切比雪夫多項式可以較好地近似 g(λ).之后,Defferrard 等[21]使用切比雪夫多項式擬合卷積核構(gòu)建用于圖分類的卷積神經(jīng)網(wǎng)絡.而GCN 方法[2]作為一階近似譜圖卷積方法,利用切比雪夫一階截斷展開式構(gòu)造了譜圖卷積模型.首先它利用遞推式構(gòu)造基礎卷積模塊為

其中,x∈RN為圖信號,為模型參數(shù),L 是標準化的拉普拉斯矩陣,IN為N維的單位矩陣,A為鄰接矩陣,D 為對角矩陣且元素值λmax為L 的最大特征值,由于標準化的拉普拉斯矩陣的特征值范圍為[0,2],因此調(diào)整范圍后的拉普拉斯矩陣

經(jīng)過對基礎模型約簡及推導,得到最終卷積模塊為

1.2 二階近似譜圖卷積模塊設計

由于切比雪夫多項式具有最佳一致逼近的特性,在擬合譜圖濾波器實現(xiàn)譜圖卷積時,具有較低的擬合誤差,同時避免了對拉普拉斯矩陣的譜分解,大大降低了計算復雜度.另外,一階GCN 節(jié)點的鄰域組成較為簡單,每次提取節(jié)點特征時只考慮到直接相連的鄰居節(jié)點信息,而忽視了非直接相連的鄰域信息,因此本文在構(gòu)造卷積核時,使用切比雪夫遞推式構(gòu)造二階截斷展開多項式作為設計二階近似譜圖卷積模塊的基礎,基礎卷積模塊為

其中,x∈RN為圖信號,為模型參數(shù),為調(diào)整范圍后的拉普拉斯矩陣.

為了限制模型參數(shù)的數(shù)量,減少過擬合,我們對基礎卷積模塊的參數(shù)個數(shù)進行約簡,一方面考慮到不同階鄰居節(jié)點對中心節(jié)點具有不同影響作用;另一方面希望后面能進一步對卷積模塊作因式分解約簡,使模型更簡單有效,我們令得到

由于不同節(jié)點邊的數(shù)量及邊的權重幅值不同,這將會導致邊多的(或者邊權重幅值大的)節(jié)點在聚合后的特征值遠遠大于邊少的(或者邊權重幅值小的)節(jié)點,為了消除這一問題,使構(gòu)造的卷積模塊有助于模型訓練時更加穩(wěn)定有效,分別對式(6)中的兩部分進行重新標準化處理并將其表示為

及其

將該卷積模塊推廣到具有 C 個輸入通道的信號 X∈RN×C和 F 個濾波器上得到最終構(gòu)造的二階近似譜圖卷積模塊為

其中,Θ∈RC×F是一個濾波器參數(shù)矩陣,表示輸入信號卷積之后的結(jié)果,F 為卷積后數(shù)據(jù)的特征維數(shù).由式(8)可知,最終構(gòu)造的卷積模塊在每次更新節(jié)點特征表示時能夠按照不同權重融合二階鄰域的節(jié)點信息,并且使用重標準化分別對行和列進行歸一化處理,使得模型的訓練變得更加穩(wěn)定有效.

1.3 二階鄰域譜圖卷積網(wǎng)絡前向分層傳播過程

為了以端到端的方式將構(gòu)造的卷積模塊用于圖節(jié)點的分類,本小節(jié)詳細闡述二階鄰域譜圖卷積網(wǎng)絡的前向分層傳播過程的實現(xiàn),網(wǎng)絡輸入層的數(shù)據(jù)Xin∈RN×C經(jīng)過隱層(第1 個卷積層)卷積運算及非線性激活處理后,得到節(jié)點的隱特征表示Hout∈RN×H,網(wǎng)絡在隱層中的處理過程可以表示為

將隱層中得到的節(jié)點隱特征表示Hout∈RN×H送入網(wǎng)絡的輸出層,經(jīng)過輸出層的卷積操作及歸一化指數(shù)函數(shù)處理得到每個節(jié)點的標簽預測結(jié)果Oout∈RN×W,網(wǎng)絡輸出層的處理過程表示為

其中,soft max(·)為歸一化指數(shù)函數(shù),用于計算每個節(jié)點最終歸屬于某一類別標簽的概率分布,以此實現(xiàn)對節(jié)點的類別標簽的預測,Θ(1)∈RH×W代表網(wǎng)絡輸出層的可學習權重參數(shù),其中 H 是每個節(jié)點隱特征表示的維數(shù),W是數(shù)據(jù)經(jīng)過該層卷積及激活操作后的特征維數(shù),由于該層是網(wǎng)絡的輸出層,因此W的值設置為與數(shù)據(jù)集的類別數(shù)相等.

最終整個譜圖卷積網(wǎng)絡模型分層傳播的過程表示為

This is Christmas night, whether you're in a snowy winter night or under the starry sky. I wish you are around by the people you loved, having a bottle of your favorite wine, get slightly drunk and be happy from your heart. Merry Christmas!

1.4 二階鄰域譜圖卷積網(wǎng)絡損失函數(shù)設計

為了引導模型在后向傳播過程中對參數(shù)的更新,我們構(gòu)造交叉熵損失函數(shù)來衡量預測數(shù)據(jù)分布與真實數(shù)據(jù)分布的差異情況.將輸入數(shù)據(jù)中的某個有標簽的節(jié)點數(shù)據(jù)表示為則經(jīng)過模型的前向分層傳播過程可得到該節(jié)點的預測結(jié)果為假設該節(jié)點真實的類別標簽為其中類別標簽使用One-Hot 編碼方式,則對該節(jié)點預測產(chǎn)生的交叉熵損失為

由于模型的復雜度越高,過擬合的風險也就越大,因此為了在模型擬合數(shù)據(jù)能力和模型的復雜度之間取得平衡,提高模型的泛化性能,我們在構(gòu)造損失函數(shù)時對模型參數(shù)使用 L2正則化約束,并將對模型參數(shù)的正則化約束表示為

最終,將以上各項結(jié)合,得到模型損失函數(shù)為

其中,ω 為超參數(shù),用于控制正則項大小,該值越大意味著對模型復雜度的約束越大.

2 實驗驗證與分析

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

本文利用4 個公開的標準數(shù)據(jù)集對模型的有效性進行驗證,具體包括3 個引文網(wǎng)絡數(shù)據(jù)集Cite-Seer[25],Cora[26],PubMed[27]和1 個知識圖數(shù)據(jù)集NELL[28].其中CiteSeer 數(shù)據(jù)集主要由計算機相關的科學出版物組成,包括人工智能、數(shù)據(jù)庫、信息檢索及機器語言等相關領域;Cora 數(shù)據(jù)集主要由機器學習相關的論文組成,涉及到神經(jīng)網(wǎng)絡、遺傳算法、概率方法、強化學習等領域;PubMed 數(shù)據(jù)集則主要由生物醫(yī)學方面的科學出版物構(gòu)成.這3 個數(shù)據(jù)集都記錄了文獻之間的引用及被引用的關系,并且對于數(shù)據(jù)集中的每篇文獻,使用去除連接字、標點符號等不能代表文檔關鍵含義的停用詞及在文檔中出現(xiàn)頻率小于10 次的詞來進行特征描述.NELL(Never ending language learning)數(shù)據(jù)集是從NELL 知識圖[28]中提取出來的數(shù)據(jù)集,通過關聯(lián)選定的NELL 實體與ClueWeb09 中的文本描述,NELL 中的每個關系被描述為一個三元組(eh,r,et),其中 eh和 et分別表示頭實體和尾實體,r 表示兩個實體間的關系.我們遵循文獻[2]中的預處理機制,為每個實體對 (eh,r,et)分配單獨的關系節(jié)點 r1和r2,作為(eh,r1)和 (et,r2),以此構(gòu)成了含有55 864個關系節(jié)點和9 891 個實體節(jié)點的二分圖結(jié)構(gòu).另外,實體節(jié)點由5 414 維稀疏特征向量描述,通過為每個關系節(jié)點分配一個不同的One-Hot 向量,使得每個圖節(jié)點的特征向量的長度均為5 414+55 864=61 278.4 個數(shù)據(jù)集的詳細統(tǒng)計信息見表1.

表1 4 個數(shù)據(jù)集的基本統(tǒng)計信息Table 1 Basic statistics information for four datasets

表1 中,對于3 個引文網(wǎng)絡數(shù)據(jù)集,節(jié)點表示每個數(shù)據(jù)集含有科學出版物的總個數(shù),即圖節(jié)點的數(shù)量;邊表示科學出版物之間的引用與被引用的連接數(shù)量,即圖的邊數(shù);特征描述每個出版物特征詞的個數(shù),即圖上每個節(jié)點的屬性信息的維數(shù);類別代表每一個數(shù)據(jù)集中包括的出版物的類別數(shù).對于NELL 數(shù)據(jù)集,節(jié)點表示實體節(jié)點與關系節(jié)點的總數(shù),邊表示實體節(jié)點與關系節(jié)點的連接數(shù)量,特征描述每個實體節(jié)點的特征詞個數(shù),類別代表數(shù)據(jù)集中實體節(jié)點的類別數(shù).

2.2 實驗設置

模型每一層的可學習權值參數(shù)按照Glorot &Bengio 方式[29]進行初始化,學習率設為0.01,并使用Adam 優(yōu)化器[30]對模型參數(shù)進行優(yōu)化,最大的訓練輪次為200,且當驗證集上損失值連續(xù)10 次的平均值均大于當前損失值時,模型則自動停止訓練.對于3 個引文網(wǎng)絡數(shù)據(jù)集,隱層節(jié)點的個數(shù)設置為16,為了防止過擬合,設置Dropout rate[31]為0.5,L2正則項系數(shù) ω為5×10－4,對于NELL 數(shù)據(jù)集,隱層節(jié)點的個數(shù)設置為64,Dropout rate 為0.1,正則項系數(shù) ω為1×10－5.

實驗中將本文方法與當前較為經(jīng)典和流行的方法進行比較,包括流行正則方法(ManiReg)[6]、半監(jiān)督嵌入方法(SemiEmb)[7]、深度游動方法(Deep walk)[9]、標簽傳播方法(Label propagation,LP)[4]、迭代分類算法(ICA)[8]、Planetoid 方法(Planetoid)[12]、譜卷積方法(SpectralCNN)[20]、Monet[32]方法、多項式近似卷積的方法(Cheby-Net)[21]以及GCN 方法[2].

2.3 客觀評價

2.3.1 標準數(shù)據(jù)集劃分下的節(jié)點分類結(jié)果及分析

本實驗中數(shù)據(jù)集的劃分與文獻[12]中一致,對于3 個引文網(wǎng)絡數(shù)據(jù)集,每個類別使用20 個有標簽節(jié)點用于訓練,500 個節(jié)點用于驗證,1 000 個節(jié)點用于測試.對于NELL 數(shù)據(jù)集,每個類別只使用1 個有標簽節(jié)點用于訓練,500 個節(jié)點用于驗證,969 個節(jié)點用于測試.

表2 中給出了不同方法在不同數(shù)據(jù)集上的測試結(jié)果,表中數(shù)字表示節(jié)點分類精度,所有基準方法的測試結(jié)果來自于原論文.實驗結(jié)果表明,本文構(gòu)造的二階近似譜圖卷積模型在不同數(shù)據(jù)集上的節(jié)點分類任務中的表現(xiàn)均優(yōu)于其他模型,這說明在每次更新節(jié)點表示時,通過恰當?shù)厝诤现苯余徲蛐畔⒑头侵苯余徲蛐畔⒛軌蚋映浞值乩玫綀D的結(jié)構(gòu)信息,從而能夠提取到更有效的節(jié)點特征表示,驗證了模型對節(jié)點分類的有效性.對于傳統(tǒng)的Mani-Reg、SemiEmd、LP 及DeepWalk 等方法,由于不能充分地利用到已知的給定信息(如節(jié)點特征信息或者類別標簽信息等),導致分類精度相對較低.而對于SpectralCNN、Cheby-Net、Monet 方法,由于模型的參數(shù)過于冗雜,容易導致提取到過多的噪聲信息使得測試精度下降.GCN 方法在每次更新節(jié)點特征表示時,只整合一階鄰居節(jié)點的信息而忽略了非直接的鄰域結(jié)構(gòu)信息,導致每次在更新節(jié)點特征表示時缺乏豐富的結(jié)構(gòu)信息,從而降低了分類性能.

表2 分類準確率結(jié)果匯總(%)Table 2 Summary of results in terms of classification accuracy (%)

2.3.2 低標簽率下的節(jié)點分類結(jié)果及分析

由于真實數(shù)據(jù)集中的標簽率(有標記數(shù)據(jù)占的比例)通常很低,因此研究少量標記訓練數(shù)據(jù)下模型的預測性能具有重要意義.在本小節(jié)中,通過減少訓練樣本的數(shù)量來檢驗在給定有限數(shù)量的標記數(shù)據(jù)下模型是否仍然表現(xiàn)出良好的分類效果.具體地,在實驗中對于3 個引文網(wǎng)絡數(shù)據(jù)集,從每個類別中隨機選擇15,10,5 個有標簽的節(jié)點用于模型訓練,隨機選擇500 個節(jié)點作為驗證集,1 000 個節(jié)點用于對模型的測試.為了避免一次隨機劃分數(shù)據(jù)帶來的偶然性,在實驗中通過20 次隨機劃分數(shù)據(jù)集對模型進行測試,并將20 次的平均測試結(jié)果作為最終的測試精度.

圖2～ 4 中給出了不同方法(MLP,Cheby1,Cheby2,Cheby3,GCN,本文算法)在不同劃分數(shù)據(jù)集上進行20 次實驗后節(jié)點的平均分類精度(帶有標準偏差).實驗結(jié)果表明,在每個數(shù)據(jù)集上,隨著帶標簽訓練樣本個數(shù)的減少,所有模型的分類精度也隨之下降,并且標準差隨之增大.另外可以發(fā)現(xiàn)本文提出模型在不同數(shù)據(jù)集上的不同標簽率下均一致性地優(yōu)于其他模型的測試結(jié)果,且取得了更小的標準差.這表明在更低標簽率下模型也能夠表現(xiàn)出更加優(yōu)越的分類性能,驗證了模型的穩(wěn)定性.

圖2 Cora 上不同訓練集大小(每個類的標記節(jié)點數(shù))的準確率Fig.2 Accuracy for different training set sizes (number of labeled nodes per class)on Cora

圖3 CiteSeer 上不同訓練集大小(每個類的標記節(jié)點數(shù))的準確率Fig.3 Accuracy for different training set sizes (number of labeled nodes per class)on CiteSeer

圖4 PubMed 上不同訓練集大小(每個類的標記節(jié)點數(shù))的準確率Fig.4 Accuracy for different training set sizes (number of labeled nodes per class)on PubMed

2.3.3 訓練模型的計算復雜度分析

我們將本文提出的二階近似譜圖卷積網(wǎng)絡模型與一階GCN 模型(GCN)進行比較分析.具體地,網(wǎng)絡模型的層數(shù)均為2,屬性矩陣 X∈RN×C,鄰接矩陣使用稀疏矩陣存儲,圖中邊的個數(shù)為|E|(圖結(jié)構(gòu)添加自環(huán)),頂點個數(shù)為N,網(wǎng)絡第1 層得到的特征維數(shù)為H,網(wǎng)絡第2 層得到的特征維數(shù)為W.由文獻[2]可知,一階GCN 模型在網(wǎng)絡的第1 層需要乘法運算次數(shù)為|E|H +NCH,網(wǎng)絡第2 層需要的乘法運算次數(shù)為|E|W +NHW,共需要乘法運算次數(shù)為|E|(H +W)+NH(C+W),模型的計算復雜度為O(|E|CHW),由于CHW 均為特征維數(shù),與問題規(guī)模無關,因此計算復雜度與圖中邊數(shù)呈線性關系.而本文提出的模型在網(wǎng)絡第1 層需要乘法運算次數(shù)為2|E|H +NCH,網(wǎng)絡的第2 層需要乘法運算次數(shù)為2|E|W +NHW,共需要乘法運算次數(shù)為2|E|(H +W)+NH(C+W),模型的計算復雜度為O(|E|CHW).由此可以看出,本文提出的模型與一階GCN 相比,在計算復雜度的規(guī)模上是相同的,但是由于本文構(gòu)造的卷積模塊引入了二階鄰居節(jié)點的特征信息,導致相應的增加了一些乘法運算次數(shù).

2.4 二階鄰域優(yōu)勢的案例分析

為了更加顯式地揭示本文提出的二階近似譜圖卷積模型相比一階GCN 模型[2]的優(yōu)勢,我們通過案例對模型定性分析.具體地,在Cora 數(shù)據(jù)集中隨機選擇了一個使用本文方法分類正確而使用GCN方法分類錯誤的節(jié)點并記作 t,圖5(a)繪制了由該節(jié)點的一階鄰域組成的局部網(wǎng)絡,圖5(b)繪制了由該節(jié)點的兩階鄰域組成的局部網(wǎng)絡.圖中每個節(jié)點的值代表它們的真實類別標簽,節(jié)點的背景深度代表GCN 及本文模型得到的每個節(jié)點對目標節(jié)點t的特征聚合權重,顏色越深表示權重值越大.

圖5(a)展示的情況是對GCN 方法分類的一個魯棒性檢測,這是由于GCN 方法預測節(jié)點 t 的標簽時,只利用了 t 的一階鄰居以及自身的信息來進行標簽預測,而在節(jié)點 t 的一階鄰居節(jié)點中,類別標簽2和5 的數(shù)量是相同的,類別標簽3 的數(shù)量最少,相同標簽的節(jié)點特征是相近的,但是自身特征和一階鄰居特征參考的尺度是不同的,GCN 方法最終將 t 節(jié)點的類別預測為了標簽5.由圖5(b)可知,本文方法通過有效地融合目標節(jié)點的二階鄰居信息,用于增強目標節(jié)點的特征表示,從而正確地預測出了節(jié)點 t 的類別標簽為3.

圖5 目標節(jié)點t 的一階及兩階鄰域組成的局部網(wǎng)絡示意圖Fig.5 Schematic diagram of local network composed of the first-order and two-order neighborhoods of target node t

2.5 節(jié)點隱特征表示可視化分析

為了更直觀地觀測模型提取到的節(jié)點特征表示的有效性,我們使用T-SNE 方法[33]對模型在隱層提取到的節(jié)點特征表示進行可視化,如圖6 所示.圖中不同的數(shù)字表示不同的類別標簽.從圖中我們不難發(fā)現(xiàn)模型提取到的隱特征表示在投影二維空間中均表現(xiàn)出了明顯的類簇效果.具體地,以圖6(a)為例,圖中的這些聚類簇對應了Cora 數(shù)據(jù)集的7個類別標簽,驗證了模型對Cora 數(shù)據(jù)集的7 個主題類別的區(qū)分能力.同樣地,圖6(b)和圖6(c)分別表現(xiàn)出了6 個和3 個主題類別.說明通過利用豐富的結(jié)構(gòu)信息,模型在學習過程中提取到了比較有分辨力的節(jié)點特征信息.

圖6 在3 個數(shù)據(jù)集上模型隱含層學習到的隱特征表示的t-SNE 圖Fig.6 A t-SNE plot of the learned hidden feature representations of the model’s hidden layer on the three datasets

綜上所述可以看出,無論在不同數(shù)據(jù)集上通過節(jié)點分類任務進行客觀評價,還是給出的對比案例分析及隱特征表示的可視化效果,本文的方法均表現(xiàn)出了較好的效果,驗證了模型的有效性.

3 結(jié)論

針對圖上半監(jiān)督節(jié)點分類任務,本文結(jié)合切比雪夫截斷展開多項式及標準化的拉普拉斯矩陣,提出了用于譜圖卷積網(wǎng)絡的二階近似卷積模塊,首先利用切比雪夫二階截斷展開式構(gòu)造基礎模型,然后對模型進行參數(shù)精簡及優(yōu)化處理,使其更新節(jié)點特征表示時能夠更加有效地利用結(jié)構(gòu)信息,進而獲得更具表達力的節(jié)點表示,實現(xiàn)對圖上節(jié)點的分類.在公開的標準數(shù)據(jù)集上進行實驗驗證,結(jié)果表明在多種標簽率下我們的模型分類效果均優(yōu)于當前流行方法,驗證了本文提出模型的有效性.但是由于使用本文提出的方法對節(jié)點分類時,需要將整個圖結(jié)構(gòu)加載到模型中,因此很難適用于較大規(guī)模的圖.在未來的研究中,為了使模型更適應于處理較大規(guī)模的圖,我們考慮采用首先將圖劃分成多個小規(guī)模的圖,然后分別進行處理的策略進行改進.