基于層次對比學(xué)習(xí)的半監(jiān)督節(jié)點分類算法

李雅琪 王 杰 王 鋒 梁吉業(yè)

近年來,深度學(xué)習(xí)在很多領(lǐng)域都具有長足的進(jìn)展[1-2],但是深度學(xué)習(xí)的成功需要使用大量的標(biāo)記數(shù)據(jù).然而,在許多實際問題中,標(biāo)記樣本的獲取是相當(dāng)困難的,需要耗費巨大的人力、物力和財力,通常無標(biāo)記樣本的數(shù)量遠(yuǎn)大于標(biāo)記樣本的數(shù)量.因此,如何使用少量的標(biāo)記數(shù)據(jù)結(jié)合大量的無標(biāo)記數(shù)據(jù)進(jìn)行訓(xùn)練是機器學(xué)習(xí)領(lǐng)域廣泛關(guān)注的問題之一[3].

半監(jiān)督學(xué)習(xí)(Semi-Supervised Learning, SSL)[4]是應(yīng)對上述問題的主流方法之一.SSL能夠在沒有外界干預(yù)的情況下,同時利用少量的標(biāo)記樣本和大量的無標(biāo)記樣本進(jìn)行學(xué)習(xí),改善學(xué)習(xí)性能.目前,半監(jiān)督學(xué)習(xí)方法大致可分為5類:生成式方法[5]、半監(jiān)督SVM(Semi-Supervised Support Vector Machine)[6]、圖半監(jiān)督學(xué)習(xí)[7-8]、基于分歧的方法[9]和基于深度學(xué)習(xí)的方法[10-11].其中,圖半監(jiān)督學(xué)習(xí)由于其概念清晰、可解釋性強且性能優(yōu)越,受到學(xué)者們越來越多的關(guān)注.

然而,圖半監(jiān)督學(xué)習(xí)在標(biāo)記樣本較少時性能退化嚴(yán)重,使用更少的標(biāo)注代價學(xué)習(xí)高效的模型是圖半監(jiān)督學(xué)習(xí)面臨的挑戰(zhàn)之一.研究者們通過直接增強監(jiān)督信息和間接增強監(jiān)督信息的方式緩解標(biāo)記樣本過少的問題.

直接增強監(jiān)督信息的方法包括標(biāo)簽傳播或自訓(xùn)練技術(shù).Zhu等[15]提出基于高斯隨機場與調(diào)和函數(shù)的半監(jiān)督學(xué)習(xí)方法,構(gòu)造相似度矩陣,讓每個樣本的類標(biāo)記信息在空間中傳播.Sun等[16]提出M3S(Mulit-stage Self-Supervised),基于DeepCluster[17],在每個訓(xùn)練階段為未標(biāo)記節(jié)點分配偽標(biāo)記.You等[18]提出Node Clustering,利用節(jié)點特征之間的相似性進(jìn)行聚類,將簇索引作為自監(jiān)督學(xué)習(xí)的偽標(biāo)記,分配給所有節(jié)點.Li等[19]訓(xùn)練圖卷積神經(jīng)網(wǎng)絡(luò)(Graph Convolutional Network, GCN)[20],利用特征提取增強監(jiān)督信息.但標(biāo)簽傳播或自訓(xùn)練技術(shù)存在一些缺點,如偽標(biāo)記錯誤的累積.尤其是當(dāng)標(biāo)記節(jié)點特別稀疏時,會引入大量的噪聲,影響標(biāo)記的傳播過程.

間接增強監(jiān)督信息的方法是指通過挖掘數(shù)據(jù)的分布信息發(fā)現(xiàn)潛在規(guī)律,從而彌補監(jiān)督信息的不足.在這方面,圖自監(jiān)督學(xué)習(xí)通過精心設(shè)計的代理任務(wù)而不依賴人工標(biāo)注提取信息,從數(shù)據(jù)中挖掘自身的監(jiān)督信息,從而學(xué)習(xí)到對下游任務(wù)有價值的表示[21-23].

圖自監(jiān)督學(xué)習(xí)方法包括預(yù)測式自監(jiān)督學(xué)習(xí)方法、生成式自監(jiān)督學(xué)習(xí)方法和圖對比學(xué)習(xí)方法(Graph Contrastive Learning, GCL).預(yù)測式自監(jiān)督學(xué)習(xí)方法將數(shù)據(jù)中自生成標(biāo)記作為監(jiān)督信號進(jìn)行學(xué)習(xí).生成式自監(jiān)督學(xué)習(xí)方法將完整的圖或子圖作為監(jiān)督信號,用于重構(gòu)輸入數(shù)據(jù)的特征或結(jié)構(gòu).圖對比學(xué)習(xí)方法通過區(qū)分正對和負(fù)對進(jìn)行訓(xùn)練.其中,圖對比學(xué)習(xí)方法由于具有強大的學(xué)習(xí)表示性能成為當(dāng)下研究的熱點.

圖對比學(xué)習(xí)通過圖數(shù)據(jù)增強為每個節(jié)點生成多視圖表示,同一節(jié)點生成的節(jié)點表示視為正例對,而從不同節(jié)點生成的節(jié)點表示視為負(fù)例對.圖對比學(xué)習(xí)的主要目標(biāo)是在最大化正例對的一致性的同時最小化負(fù)例對的一致性[24].

盡管圖對比學(xué)習(xí)方法已得到廣泛研究,但是存在如下不足:1)通過反復(fù)試錯為每個數(shù)據(jù)集手動選擇數(shù)據(jù)增強方案;2)引入昂貴的領(lǐng)域特定知識作為指導(dǎo)以獲得數(shù)據(jù)增強;3)大多會改變圖語義信息,丟棄一些重要的節(jié)點和邊,使模型學(xué)習(xí)對不重要的節(jié)點和邊緣擾動不敏感[29].因此,圖對比方法中保持圖的語義,同時減少人工的干預(yù)是必要的.

基于上述分析,本文提出基于層次對比學(xué)習(xí)的半監(jiān)督節(jié)點分類算法(Semi-Supervised Node Classi-fication Algorithm Based on Hierarchical Contrastive Learning, SSC-HCL).不使用圖數(shù)據(jù)增強的方式生成視圖,而是將不同層次的圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Network, GNN)表示作為相關(guān)視圖進(jìn)行對比,保留圖的語義信息.在此基礎(chǔ)上,設(shè)計半監(jiān)督對比損失,結(jié)合半監(jiān)督任務(wù)和對比學(xué)習(xí),可以有效利用少量標(biāo)記信息提供監(jiān)督信息,改進(jìn)節(jié)點表示,進(jìn)而改善節(jié)點分類任務(wù)的效果.一方面可以緩解繁瑣的搜索,學(xué)習(xí)更好的節(jié)點表示,另一方面可以對不同跳鄰居學(xué)到的節(jié)點表示進(jìn)行約束,緩解由于數(shù)據(jù)增強及深度加深帶來的語義破壞問題.在4個基準(zhǔn)數(shù)據(jù)集上的實驗驗證SSC-HCL的優(yōu)越性.

1 基于層次對比學(xué)習(xí)的半監(jiān)督節(jié)點分類算法

1.1 圖半監(jiān)督學(xué)習(xí)問題定義

設(shè)G=(V,ε)表示一個無向圖,其中,

V={v1,v2,…,vN}

表示N個節(jié)點的集合,包括l個標(biāo)記樣本

Dl={(x1,y1),(x2,y2),…,(xl,yl),

yi∈{1,2,…,C}},

C表示樣本的類別,和u個無標(biāo)記樣本

Du={(xl+1),(xl+2),…,(xl+u)},

通常,l?u.ε?V×V表示節(jié)點之間的邊集.X∈RN×F表示節(jié)點的特征矩陣,F表示特征維度,Y表示節(jié)點的標(biāo)記矩陣.

A=[aij]∈RN×N

表示節(jié)點的鄰接矩陣.

D=diag(d1,d2,…,dN)

表示A的度矩陣,

表示頂點i的度.

1.2 圖神經(jīng)網(wǎng)絡(luò)

圖神經(jīng)網(wǎng)絡(luò)的目標(biāo)是學(xué)習(xí)一個編碼器

f(X,A)∈RN×F′,

以圖的特征和結(jié)構(gòu)作為輸入,產(chǎn)生低維的節(jié)點嵌入,即F′?F.GCN的卷積層傳播公式為

ReLU(·)=max(0,·).

1.3 算法介紹

本文提出基于層次對比學(xué)習(xí)的半監(jiān)督節(jié)點分類算法(SSC-HCL),框架如圖1所示.

SSC-HCL將原始圖G=(X,A)的結(jié)構(gòu)和特征作為輸入,采用GCN對圖進(jìn)行編碼,在學(xué)習(xí)的過程中,將不同層次上得到的嵌入表示作為不同的視圖,用作對比學(xué)習(xí).同時,使用半監(jiān)督對比損失,最大化多個視圖上學(xué)得表示的一致性,通過迭代優(yōu)化學(xué)習(xí)節(jié)點的表示.

圖1 SSC-HCL結(jié)構(gòu)圖

具體地,SSC-HCL(以三層為例)通過在圖G上應(yīng)用GCN,得到第1層～第3層視圖表示:

其中,

表示歸一化鄰接矩陣.然后,將層次視圖設(shè)計為對比視圖,以增大正例對的相似性、降低負(fù)例對的相似性為目的,改進(jìn)圖的嵌入表示.

半監(jiān)督對比損失同時利用大量的無標(biāo)記樣本和少量的標(biāo)記樣本,為僅使用無標(biāo)記樣本的對比學(xué)習(xí)提供豐富的監(jiān)督信息,幫助模型學(xué)習(xí)更好的節(jié)點表示,進(jìn)一步提高模型性能.在學(xué)習(xí)的過程中,使用評分函數(shù)衡量節(jié)點編碼特征的相似度,目標(biāo)是盡可能地增大同一類別的節(jié)點之間的相似度,盡可能地減小不同類別的節(jié)點之間的相似度,指導(dǎo)學(xué)習(xí)過程.半監(jiān)督對比損失分為兩部分:監(jiān)督對比損失和無監(jiān)督對比損失.

SSC-HCL的半監(jiān)督對比損失機制如圖2所示.使用xi表示視圖中的節(jié)點,如果xi為標(biāo)記節(jié)點,xi的正例為與它具有同類的標(biāo)記節(jié)點,負(fù)例為與它具有不同類的標(biāo)記節(jié)點,即圖2中的紫色箭頭和藍(lán)色箭頭指向的節(jié)點分別表示節(jié)點xi的正例和負(fù)例.如果xi為無標(biāo)記節(jié)點,xi的正例為另一個視圖上它本身,負(fù)例為除xi之外的其它節(jié)點,即圖2中的綠色箭頭和紅色箭頭指向的節(jié)點分別表示節(jié)點xi的正例和負(fù)例.

圖2 半監(jiān)督對比損失機制示意圖

無監(jiān)督對比損失表示如下:

同時,為了充分利用稀缺但有價值的標(biāo)記樣本,使用監(jiān)督對比損失為學(xué)習(xí)節(jié)點表示提供額外的監(jiān)督信號.監(jiān)督對比損失表示如下:

其中,II[·]表示指示函數(shù),在[·]內(nèi)為真和假時分別取值為1和0.

半監(jiān)督對比損失結(jié)合無監(jiān)督對比損失和監(jiān)督對比損失,表示如下:

(1)

使用交叉熵?fù)p失衡量網(wǎng)絡(luò)的實際輸出與真實標(biāo)記之間的差異,即

(2)

結(jié)合半監(jiān)督對比損失和交叉熵?fù)p失,得到整體的網(wǎng)絡(luò)輸出,總體的目標(biāo)損失函數(shù)表示如下:

(3)

其中,λ>0表示半監(jiān)督對比損失和交叉熵?fù)p失之間的相對權(quán)重,k表示第s層和第s+1層上的半監(jiān)督對比損失.

最終,第i個節(jié)點的預(yù)測函數(shù)表示如下:

1.4 算法步驟

SSC-HCL的詳細(xì)訓(xùn)練過程如算法1所示.

算法1SSC-HCL(以三層為例)

輸入特征矩陣X,鄰接矩陣A,標(biāo)記矩陣Y,

迭代次數(shù)N

輸出未標(biāo)記節(jié)點的標(biāo)記

初始化隨機初始化模型參數(shù)

Forepoch=1 toNdo

通過GCN得到第1層的嵌入表示Z1

通過GCN得到第2層的嵌入表示Z2

通過GCN得到第3層的嵌入表示Z3

由式(2)計算交叉熵?fù)p失lce

由式(3)計算總體目標(biāo)損失l

根據(jù)梯度下降方法,更新參數(shù)l

End for

預(yù)測未標(biāo)記節(jié)點的標(biāo)記

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

2.1 實驗數(shù)據(jù)集與實驗設(shè)置

為了驗證本文算法的有效性,在Cora[33]、CiteSeer[33]、PubMed[33]、Amazon Photo[34]這4個基準(zhǔn)數(shù)據(jù)集上進(jìn)行實驗,數(shù)據(jù)集信息如表1所示.Cora、CiteSeer、PubMed為引文網(wǎng)絡(luò)數(shù)據(jù)集,節(jié)點表示文檔,邊表示文檔之間的引用關(guān)系,每個文檔都由一個詞袋向量表示相應(yīng)的詞存在或不存在.Amazon Photo數(shù)據(jù)集是亞馬遜產(chǎn)品聯(lián)合購買數(shù)據(jù)集,節(jié)點表示商品,邊表示兩種商品經(jīng)常被同時購買,節(jié)點特征表示產(chǎn)品評論,類別標(biāo)簽由產(chǎn)品的類別給出.

表1 實驗數(shù)據(jù)集信息

在Cora、CiteSeer、PubMed數(shù)據(jù)集上,本文使用與Yang等[35]相同的訓(xùn)練集、驗證集、測試集劃分方式,即每類隨機抽取20個節(jié)點作為標(biāo)記數(shù)據(jù)進(jìn)行訓(xùn)練,500個節(jié)點用于驗證,1 000個節(jié)點用于測試.在Amazon Photo數(shù)據(jù)集上,每類隨機抽取30個節(jié)點作為標(biāo)記數(shù)據(jù)進(jìn)行訓(xùn)練,隨機抽取30個節(jié)點用于驗證,其余節(jié)點用于測試.

2.2 基線方法

本文選擇如下對比方法.

1)DeepWalk[12].基于圖嵌入的方法,通過隨機游走學(xué)習(xí)節(jié)點的嵌入表示.

2)Chebyshev[13].基于圖卷積的方法,把CNN擴展到非歐數(shù)據(jù)上.

3)GATs[14].使用注意力機制學(xué)習(xí)鄰居節(jié)點的權(quán)重,對鄰居節(jié)點的特征加權(quán)求和,為不同的節(jié)點分配不同的權(quán)重.

4)文獻(xiàn)[15]方法.傳統(tǒng)的基于圖的半監(jiān)督學(xué)習(xí)方法,通過節(jié)點之間的邊傳播標(biāo)簽,將標(biāo)簽分配給未標(biāo)記節(jié)點.

5)GCN[20].對圖數(shù)據(jù)進(jìn)行操作的經(jīng)典的圖卷積神經(jīng)網(wǎng)絡(luò).

6)DGI[25].最大化圖局部和全局的互信息,學(xué)習(xí)節(jié)點表示.

7)文獻(xiàn)[26]方法.最大化圖的多視圖編碼表示之間的互信息,學(xué)習(xí)節(jié)點表示.

8)GMI[27].對比輸入圖和每個節(jié)點的隱藏表示之間的相關(guān)性,學(xué)習(xí)節(jié)點表示.

9)GRACE[28].利用節(jié)點級對比目標(biāo)的無監(jiān)督圖表示學(xué)習(xí)框架.

2.3 實驗結(jié)果

本節(jié)計算各方法10次運行的平均分類準(zhǔn)確率以評估性能.各方法在4個數(shù)據(jù)集上的結(jié)果如表2所示,表中黑體數(shù)字表示最優(yōu)值.由表可見,SSC-HCL優(yōu)于對比方法,在Cora、CiteSeer、PubMed、Amazon Photo數(shù)據(jù)集上與次佳方法的分類準(zhǔn)確率相比,分別提升0.8%、0.6%、0.5%和1.2%.因此可以看出,利用不同層次進(jìn)行對比學(xué)習(xí),能夠更好地保留圖的節(jié)點特征和拓?fù)湫畔?學(xué)得更好的表示,從而驗證SSC-HCL的有效性.

表2 各方法在4個數(shù)據(jù)集上的分類準(zhǔn)確率對比

為了進(jìn)一步分析模型深度對分類準(zhǔn)確率的影響,改變模型中編碼器的卷積層數(shù),設(shè)置隱藏層維度為128.SSC-HCL和GCN在不同層數(shù)上的分類準(zhǔn)確率如圖3所示.

(a)Cora (b)CiteSeer (c)PubMed

由圖3可以看出,兩層GCN編碼器的性能最佳,隨著層數(shù)的不斷增加,性能下降,多卷積層可能產(chǎn)生從較遠(yuǎn)的鄰域聚合信息的噪聲,從而降低節(jié)點表示的質(zhì)量和下游節(jié)點分類任務(wù)的性能.盡管GCN和SSC-HCL的性能都有一定下降,但SSC-HCL在不同深度下的性能大幅優(yōu)于GCN.

此外,進(jìn)一步研究不同標(biāo)記數(shù)量對方法性能的影響.對于每個數(shù)據(jù)集,為每類抽取n個標(biāo)記樣本進(jìn)行實驗,n=10,15,20,25,30.GCN、DGI、文獻(xiàn)[26]方法、GRACE、SSC-HCL在Cora、CiteSeer、PubMed數(shù)據(jù)集上的分類準(zhǔn)確率如表3～表5所示,表中黑體數(shù)字表示最優(yōu)值.

表3 各方法在Cora數(shù)據(jù)集上不同標(biāo)記數(shù)量下的分類準(zhǔn)確率

表5 各方法在PubMed數(shù)據(jù)集上不同標(biāo)記數(shù)量下的分類準(zhǔn)確率

由表3～表5可以看出,隨著標(biāo)記數(shù)量的增加,性能隨之上升,這一結(jié)果表明,樣本的標(biāo)記數(shù)量與方法性能相關(guān),標(biāo)記數(shù)量越高,分類準(zhǔn)確率越高.在3個引文網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果表明,SSC-HCL在不同標(biāo)記數(shù)量上的分類準(zhǔn)確率均最優(yōu).

為了提供更直觀地說明,在Cora數(shù)據(jù)集上,給出SSC-HCL、DGI、GMI學(xué)得的節(jié)點嵌入表示的t-SNE[36]可視化結(jié)果,具體如圖4所示,圖中不同顏色表示不同類別.由圖可觀察得出,SSC-HCL得到的子簇內(nèi)較緊湊,子簇間界限較明顯,不同顏色的子簇間重疊較少.DGI得到的紅色子簇和綠色子簇之間重疊部分較多,且屬于同類的黑色子簇之間的距離較遠(yuǎn).GMI得到的橙色子簇和黑色子簇之間重疊于左上方,且屬于同類的黑色子簇之間的距離較遠(yuǎn).結(jié)果表明,SSC-HCL能夠得到良好的節(jié)點嵌入表示.

(a)SSC-HCL (b)DGI (c)GMI

3 結(jié) 束 語

本文提出基于層次對比學(xué)習(xí)的半監(jiān)督節(jié)點分類算法(SSC-HCL).利用GCN的不同層次作為視圖進(jìn)行對比學(xué)習(xí),不需要通過圖數(shù)據(jù)增強得到視圖,從而有效緩解通過繁瑣復(fù)雜的試錯選擇數(shù)據(jù)增強方法的問題,并且對不同跳鄰居學(xué)到的節(jié)點表示進(jìn)行約束,緩解圖數(shù)據(jù)增強以及深度加深對圖語義信息造成的破壞.此外,設(shè)計半監(jiān)督對比損失,有效利用大量的無標(biāo)記樣本和少量的標(biāo)記樣本,提供豐富的監(jiān)督信息.在4個基準(zhǔn)數(shù)據(jù)集上的實驗表明SSC-HCL在節(jié)點分類任務(wù)上的有效性.今后考慮研究動態(tài)環(huán)境下的圖對比學(xué)習(xí),學(xué)習(xí)圖結(jié)構(gòu)中的豐富特征.