崔彩霞 王 杰 龐天杰 梁吉業(yè)

圖數(shù)據(jù)分析挖掘在服務(wù)經(jīng)濟和社會發(fā)展中具有基礎(chǔ)性作用,有效感知、挖掘、利用圖數(shù)據(jù),可為相關(guān)產(chǎn)業(yè)的發(fā)展提供巨大的助推力.圖數(shù)據(jù)分析挖掘任務(wù)包括節(jié)點分類[1]、鏈路預(yù)測[2]、推薦系統(tǒng)[3]等，節(jié)點分類作為其中一項重要的任務(wù)受到越來越多的關(guān)注.例如：在社交網(wǎng)絡(luò)中識別用戶是人類用戶還是機器人用戶[4]；在蛋白質(zhì)互作用網(wǎng)絡(luò)中預(yù)測蛋白質(zhì)功能類型[5]；在引文網(wǎng)絡(luò)中識別文檔主題[6]等.

近年來，圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Networks，GNNs)[7-10]因其對非歐數(shù)據(jù)強大的表示學(xué)習(xí)能力，在節(jié)點分類任務(wù)上表現(xiàn)出良好的性能.然而，現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)的研究大多基于不同類節(jié)點平衡的假設(shè)，即不同類標(biāo)記節(jié)點數(shù)量大致是相同的.而在一些實際問題中，收集到的標(biāo)記節(jié)點往往是不平衡的，某些類的標(biāo)記節(jié)點數(shù)量遠大于其它類別.同時由于標(biāo)注代價較高、涉及個人隱私等原因，節(jié)點分類任務(wù)也面臨只有少部分的節(jié)點被標(biāo)注而大量的節(jié)點沒有標(biāo)注的問題.例如，在社交網(wǎng)絡(luò)虛假賬號識別[11]中，正常賬號遠多于虛假賬號，數(shù)量嚴重失衡，而且由于賬號涉及隱私等原因，只有少部分賬號被標(biāo)注，而大量的賬號是無標(biāo)記的.因此，監(jiān)督信息缺乏和節(jié)點不平衡給節(jié)點分類任務(wù)帶來巨大的挑戰(zhàn).

已有一些研究將傳統(tǒng)的重采樣[12]、重加權(quán)[13]、集成學(xué)習(xí)[14]等不平衡處理技術(shù)應(yīng)用到不平衡節(jié)點分類問題上，使其分類性能得到一定程度的提升.

在重采樣方面，Zhao等[15]和Qu等[16]利用上采樣技術(shù)改善節(jié)點的不平衡問題.具體來說，Zhao等[15]提出GraphSMOTE，將SMOTE(Synthetic Mino-rity Over-sampling Technique)上采樣算法[17]推廣到圖上，通過插值方式在潛在空間合成少數(shù)類節(jié)點，再使用一個預(yù)訓(xùn)練的邊緣生成器預(yù)測合成節(jié)點與原節(jié)點之間的連通性.通過這種方式，使不同類節(jié)點達到平衡，提升節(jié)點分類的性能.Qu等[16]提出ImGAGN(Imbalanced Network Embedding via Generative Ad-versarial Graph Networks)，利用生成對抗網(wǎng)絡(luò)(Generative Adversarial Network, GAN)生成少數(shù)類節(jié)點，實現(xiàn)對少數(shù)類的上采樣，使標(biāo)記節(jié)點達到平衡，提升不平衡節(jié)點二分類的性能.

在重加權(quán)方面，Chen等[18]提出ReNode，根據(jù)標(biāo)記節(jié)點對類邊界的相對位置自適應(yīng)地重新加權(quán)，緩解節(jié)點不平衡對分類性能的影響，然而該方法依賴類邊界，在監(jiān)督信息缺乏時確定的類邊界可能不準(zhǔn).

在集成學(xué)習(xí)方面，Sun等[19]提出AdaGCN(Ada-boosting Graph Convolutional Network)，以圖卷積網(wǎng)絡(luò)(Graph Convolutional Network, GCN)[7]為基分類器，利用前一個GCN的誤差更新下一個GCN的樣本權(quán)值，以此糾正錯分樣本，提高分類性能.Shi等[20]提出Boosting-GNN，使用GNN作為基分類器進行Boosting集成，即在每次提升訓(xùn)練時，為前一次未正確分類的訓(xùn)練樣本設(shè)置更高的權(quán)重，從而提高分類精度和可靠性.

綜上所述，現(xiàn)有方法側(cè)重于使用重采樣、重加權(quán)或集成學(xué)習(xí)的方式處理節(jié)點的不平衡問題，未同時考慮監(jiān)督信息缺乏與節(jié)點不平衡這兩個問題，從而不能保證節(jié)點分類性能的提升.

自監(jiān)督學(xué)習(xí)[21]可在不依賴標(biāo)簽的情況下，從數(shù)據(jù)本身信息學(xué)習(xí)到數(shù)據(jù)的有效表示，已成功應(yīng)用到計算機視覺[22-23]、自然語言處理[24-25]、圖數(shù)據(jù)分析挖掘[26-30]等領(lǐng)域.根據(jù)模型結(jié)構(gòu)與目標(biāo)的不同，自監(jiān)督學(xué)習(xí)通常分為兩類[31]：基于生成的自監(jiān)督學(xué)習(xí)與基于對比的自監(jiān)督學(xué)習(xí).基于生成的自監(jiān)督學(xué)習(xí)的目的是恢復(fù)輸入數(shù)據(jù)中缺失的部分，通過重構(gòu)誤差學(xué)習(xí)表示，如自編碼器[32]、BERT(Bidirectional En-coder Representations from Transformers)[24]等.基于對比的自監(jiān)督學(xué)習(xí)(即對比學(xué)習(xí))通過對比正負樣本的相似度，拉近正樣本，推開負樣本，構(gòu)建有效表示，如MoCo(Momentum Contrast)[22]、SimCLR[23]等.

類似地，圖自監(jiān)督學(xué)習(xí)也分為基于生成的圖自監(jiān)督學(xué)習(xí)與基于對比的圖自監(jiān)督學(xué)習(xí).基于生成的圖自監(jiān)督學(xué)習(xí)關(guān)注節(jié)點/邊特征或鄰接矩陣的重構(gòu)問題，如經(jīng)典的圖自編碼器(Graph Auto-Encoder, GAE)[33]與GraphMAE[34].基于對比的圖自監(jiān)督學(xué)習(xí)旨在最大化輸入圖在不同視圖上的表示一致性，如GraphCL(Graph Contrastive Learning)[26]、DGI(Deep Graph Infomax)[29]等.特別地，自監(jiān)督學(xué)習(xí)也應(yīng)用到不平衡分類研究中.Yang等[35]和Liu等[36]探索自監(jiān)督學(xué)習(xí)在不平衡圖像分類上的應(yīng)用，通過實驗分析得出自監(jiān)督學(xué)習(xí)可增強圖像數(shù)據(jù)的表達能力，提升分類性能.

因此，本文將自監(jiān)督學(xué)習(xí)這一有效工具引入不平衡節(jié)點分類問題中，提出基于自監(jiān)督學(xué)習(xí)的不平衡節(jié)點分類算法(Imbalanced Node Classification Algorithm Based on Self-Supervised Learning， ImSSL).一方面借助自監(jiān)督學(xué)習(xí)擴充監(jiān)督信息，另一方面增強節(jié)點的表達能力.此外，在交叉熵損失和自監(jiān)督對比損失的基礎(chǔ)上，設(shè)計語義約束損失(Semantic Constraint Loss， SCL)，以此保持圖數(shù)據(jù)增強中語義的一致性.在3個真實的圖數(shù)據(jù)集上執(zhí)行的大量實驗表明，ImSSL性能較優(yōu).

1 問題描述

本文研究的問題是半監(jiān)督不平衡節(jié)點分類，即在有標(biāo)記節(jié)點集D中，一些類的節(jié)點數(shù)遠多于另一些類.

假設(shè)圖G的節(jié)點有m個類C1,C2,…,Cm，|Ci|表示屬于第i個類的標(biāo)記節(jié)點的數(shù)目，則不平衡比(Imbalance Ratio， IR)定義如下：

(1)

2 基于自監(jiān)督學(xué)習(xí)的不平衡節(jié)點分類算法

為了彌補監(jiān)督信息的不足，同時學(xué)習(xí)對少數(shù)類分類有利的特征表示，本文提出基于自監(jiān)督學(xué)習(xí)的不平衡節(jié)點分類算法(ImSSL).算法總體框架如圖1所示，包括數(shù)據(jù)增強模塊、圖神經(jīng)網(wǎng)絡(luò)編碼模塊與綜合損失模塊.

圖1 ImSSL總體框架圖Fig.1 Framework of ImSSL

2.1 圖數(shù)據(jù)增強模塊

圖數(shù)據(jù)增強[26]的目的是在不改變語義的情況下，通過一定的變換,創(chuàng)建新的、異于原圖的、合理的圖數(shù)據(jù).目前有如下一些常用方法.

1)基于節(jié)點丟棄的方法.對于給定圖,通過隨機丟棄一定比例的節(jié)點及其相關(guān)聯(lián)的邊生成原圖的新視圖.此方法基于一個假設(shè)：丟棄部分節(jié)點不會影響圖的語義,每個節(jié)點的丟棄概率遵循某一分布,例如相同的均勻分布或其它分布.

2)基于邊擾動的方法.對于給定圖，隨機增加或丟棄一定比例的邊，產(chǎn)生原圖的新視圖.此方法基于這樣的假設(shè)：圖的語義信息對邊有一定的魯棒性.

3)基于節(jié)點屬性掩碼的方法.對于給定圖,隨機對節(jié)點屬性掩碼進行一定比例的更改，更改其屬性值.選擇掩碼比例要考慮這種改動不會對模型的預(yù)測造成太大影響.

4)基于子圖的方法.對于給定圖,通過隨機游走采樣圖的子圖，前提是假設(shè)圖的語義在它的局部結(jié)構(gòu)中可得到較大程度的保留.

本文使用基于節(jié)點屬性掩碼的增強方法，框架具有一般性，也可使用其它圖增強方法.

2.2 圖神經(jīng)網(wǎng)絡(luò)編碼模塊

本文采用經(jīng)典的圖卷積網(wǎng)絡(luò)(GCN)[7]作為圖編碼器.一個兩層的圖卷積網(wǎng)絡(luò)的預(yù)測結(jié)果為：

(2)

其中:W(0)∈RF×S表示第0層的參數(shù);W(1)∈RS×m表示第1層的參數(shù);

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

嵌入矩陣

zi表示Z的第i行，

第i個視圖的預(yù)測結(jié)果為：

(3)

其中X(i)表示第i個視圖的特征矩陣.

第i個視圖的嵌入矩陣為:

在ImSSL中，GCN學(xué)習(xí)不同視圖的嵌入表示時權(quán)重是共享的，可減少計算量.值得注意的是，本文所提框架具有一般性，也可適應(yīng)于其它的GNN模型.

2.3 綜合損失模塊

ImSSL的損失函數(shù)包含3部分：分類損失LCE、語義約束損失LSCL和自監(jiān)督對比損失LSSL，則

L=λ1LCE+λ2LSCL+λ3LSSL,

(4)

其中，λ1、λ2和λ3表示權(quán)衡參數(shù).

本文采用交叉熵損失函數(shù)計算分類損失，則

(5)

在進行圖數(shù)據(jù)增強時，本文希望能保證圖語義的一致性，即不能因為數(shù)據(jù)增強使其預(yù)測標(biāo)簽發(fā)生大的變化.為此，設(shè)計語義約束損失，用于衡量不同視圖下類分布與原圖語義接近程度，則

(6)

(7)

其中，

sim(·)表示度量兩節(jié)點的相似度，τ表示溫度系數(shù)，

表示節(jié)點u與同一視圖其它節(jié)點的相似度之和，

表示節(jié)點u與不同視圖的節(jié)點間的相似度之和.

算法1基于自監(jiān)督學(xué)習(xí)的不平衡節(jié)點分類算法

輸入圖G的特征矩陣X，鄰接矩陣A，標(biāo)記集Y，

訓(xùn)練集D，驗證集V，測試集U，

最大迭代次數(shù)MaxIter，溫度系數(shù)τ，

權(quán)衡參數(shù)λ1、λ2、λ3

輸出測試集U的預(yù)測結(jié)果

2.FORi= 1 TOMaxIterDO

編碼，得到V個節(jié)點嵌入表示Z(1),Z(2),…,Z(V)；

4. 利用式(5)計算交叉熵損失LCE；

5. 利用式(6)計算語義約束損失LSCL；

6. 利用式(7)計算自監(jiān)督對比損失LSSL；

7. 利用式(4)計算綜合損失函數(shù)L；

8. 應(yīng)用梯度下降法最小化L，更新參數(shù).

9.END FOR

10.利用式(2)計算測試集U的預(yù)測標(biāo)簽.

11.RETURNU的預(yù)測結(jié)果.

2.4 時間復(fù)雜度分析

算法1的計算復(fù)雜性包括3階段：數(shù)據(jù)增強階段(第1行)、學(xué)習(xí)階段(第2～9行)和預(yù)測階段(第10行).

在數(shù)據(jù)增強階段，數(shù)據(jù)增強算法的時間復(fù)雜度為O(NF)，生成V個視圖執(zhí)行數(shù)據(jù)增強的時間復(fù)雜度為O(VNF).

在學(xué)習(xí)階段，時間復(fù)雜度如下：GCN編碼的時間復(fù)雜度為

O(|ε|FS+|ε|Sm)，

對V個視圖進行GCN編碼的時間復(fù)雜度為

O(V(|ε|FS+|ε|Sm))，

注意到m

在預(yù)測階段(第10行)，計算U個未標(biāo)記樣本的預(yù)測標(biāo)簽的時間復(fù)雜度為O(Um)=O(N).

綜上所述，算法1的時間復(fù)雜度為

O(V|ε|FS+VN3).

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

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

本文選用3個廣泛使用的引文網(wǎng)絡(luò)數(shù)據(jù)集Cora、CiteSeer和PubMed(https://linqs.soe.ucsc.edu/data)作為實驗對象.

Cora數(shù)據(jù)集由2 708篇來源于Cora數(shù)據(jù)庫上的機器學(xué)習(xí)相關(guān)論文組成, 論文之間的文獻引用鏈接有5 229條.這些文獻分別屬于機器學(xué)習(xí)理論、概率方法、基于案例的機器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)、規(guī)則學(xué)習(xí)、遺傳算法和增強學(xué)習(xí)這7種類別.這些論文經(jīng)過提取詞語,去掉停用詞,再選擇文檔中出現(xiàn)頻次小于10的詞語作為文獻特征,最終得到1 433個特征詞.數(shù)據(jù)集上每個節(jié)點使用1 433維0-1向量作為該節(jié)點的特征.

CiteSeer數(shù)據(jù)集由3 327部來源于CiteSeer數(shù)據(jù)庫的計算機相關(guān)的科學(xué)出版物組成,文獻引用鏈接有4 732條.這些文獻分別屬于人工智能、數(shù)據(jù)庫、信息檢索、機器學(xué)習(xí)、智能體和人機交互這6個類別.特征提取模式同Cora數(shù)據(jù)集一樣,最終數(shù)據(jù)集上每個節(jié)點使用3 703維的0-1向量作為節(jié)點特征信息.

PubMed數(shù)據(jù)集由19 717部來源于PubMed數(shù)據(jù)庫的與糖尿病有關(guān)的科學(xué)出版物組成,文獻引用鏈接有44 338條.這些文獻根據(jù)研究的糖尿病種類分為3類:實驗性糖尿病、1型糖尿病和2型糖尿病.文獻特征由500個單詞組成,每篇文獻對應(yīng)一個詞頻-逆文檔頻率向量(Term Frequency-Inverse Document Frequency, TF-IDF),因此,數(shù)據(jù)集上的每個節(jié)點均使用500維向量作為節(jié)點特征.

本文沿用文獻[7]和文獻[38]的半監(jiān)督節(jié)點分類設(shè)置及文獻[18]中的不平衡設(shè)置進行分析和實驗.具體地，在3個基準(zhǔn)數(shù)據(jù)集上，每類 20個標(biāo)記節(jié)點用于訓(xùn)練，500個節(jié)點用于驗證，1 000個節(jié)點用于測試.在此基礎(chǔ)上，選訓(xùn)練集上一些類作為少數(shù)類，每個少數(shù)類中隨機選取20/IR個節(jié)點，不平衡比IR設(shè)為10.數(shù)據(jù)集的詳細信息如表1所示.

表1 實驗數(shù)據(jù)集Table 1 Experimental datasets

3.2 對比算法

為了測試本文算法的性能，選擇如下半監(jiān)督不平衡節(jié)點分類中的算法進行對比.

1)GraphSMOTE[15].SMOTE在不平衡圖數(shù)據(jù)上的擴展.

2)ReNode[18].以拓撲不平衡角度研究不平衡節(jié)點分類問題的方法，根據(jù)拓撲位置對標(biāo)記節(jié)點重加權(quán).

3)AdaGCN[19].Adaboost與圖神經(jīng)網(wǎng)絡(luò)結(jié)合的集成學(xué)習(xí)模型，在Adaboost訓(xùn)練中以GCN作為基分類器.

4)DR-GCN[39].雙正則圖卷積網(wǎng)絡(luò)，解決圖數(shù)據(jù)中類不平衡學(xué)習(xí)問題.

3.3 參數(shù)設(shè)置與評價指標(biāo)

在ImSSL中，最大迭代次數(shù)設(shè)為500，模型參數(shù)τ=0.5.在每個訓(xùn)練階段使用全批次訓(xùn)練ImSSL.采用Adam(Adaptive Moment Estimation)優(yōu)化器，在PyTorch上運行.對于基線算法，使用原始文獻中的代碼.所有算法運行實驗 5次，取平均值作為最終結(jié)果.

借鑒不平衡多分類的常用評價方法[15,40-41]，使用如下3個評價指標(biāo)：Accuracy,AUC和Macro_F.這些評價指標(biāo)建立在多分類的混淆矩陣上，如表2所示，表中Nij表示分類為Cj類但實際上屬于Ci類的樣本數(shù)量.

表2 多分類的混淆矩陣Table 2 Confusion matrix for multi-class classification

第i類的查準(zhǔn)率

第i類的查全率

由Pi和Ri計算平均值，可得到宏查準(zhǔn)率

宏查全率

宏F(Macro_F)為：

Accuracy表示正確分類的樣本數(shù)量與測試樣本總數(shù)的比率，廣泛應(yīng)用于評估分類器的性能.然而，在不平衡學(xué)習(xí)的情況下，Accuracy可能會忽略少數(shù)類.因此，除了Accuracy，本文還選擇AUC和Macro_F，這兩個指標(biāo)專門用于不平衡分類.對每個類分別計算AUC和Macro_F，再進行非加權(quán)平均，這樣可更好地反映少數(shù)類的分類效果.

3.4 實驗結(jié)果

為了驗證ImSSL的有效性，首先與4種基線算法進行對比，結(jié)果如表3所示.由表可看出，相比基線方法，ImSSL的所有指標(biāo)值都最優(yōu)，可提高少數(shù)類的識別率.由此可得出：在監(jiān)督節(jié)點極度受限且不平衡時，采用解決不平衡問題的常規(guī)辦法，不論是重采樣、重加權(quán)還是集成學(xué)習(xí)，沒有同時考慮監(jiān)督信息缺

表3 各算法在3個數(shù)據(jù)集上的性能對比Table 3 Performance comparison of different algorithms on 3 datasets %

乏與節(jié)點不平衡這兩個問題，不能保證節(jié)點分類的性能.而ImSSL有效利用自監(jiān)督學(xué)習(xí)能挖掘數(shù)據(jù)內(nèi)在的結(jié)構(gòu)獲得監(jiān)督信息的特點，彌補半監(jiān)督不平衡節(jié)點分類中監(jiān)督信息的不足，同時能學(xué)習(xí)有益于少數(shù)類分類的表示，提高分類性能.

下面研究ImSSL損失函數(shù)(式(4))中約束損失與自監(jiān)督對比損失的貢獻，定義如下對比算法.

1)w/oLSCL.移除約束損失.

2)w/oLSCLLSSL.移除約束損失與自監(jiān)督對比損失.

在不平衡比為10的Cora數(shù)據(jù)集上進行對比實驗.取各自設(shè)置下5次實驗的平均結(jié)果,3種算法的消融實驗結(jié)果如表4所示.由表可見，相比w/oLSCLLSSL，增加自監(jiān)督對比損失后，w/oLSCL的3個指標(biāo)值皆有大幅提升，這說明通過自監(jiān)督方式訓(xùn)練可學(xué)習(xí)數(shù)據(jù)內(nèi)在結(jié)構(gòu)特征，是解決不平衡節(jié)點分類的有效手段.對比w/oLSCL和ImSSL可知，增加約束損失是有必要的，約束損失可以從語義上對數(shù)據(jù)增強進行指導(dǎo)，彌補圖數(shù)據(jù)上數(shù)據(jù)增強中語義的一致性.

表4 各算法在Cora數(shù)據(jù)集上的消融實驗結(jié)果Table 4 Ablation experiment results of different algorithms on Cora dataset %

下面對比GCN與ImSSL在不同不平衡比下的性能，評估不同不平衡比對ImSSL的影響.以Cora數(shù)據(jù)集作為實驗數(shù)據(jù)集，IR分別設(shè)置為1,2,5,10,20.每次實驗進行5次，平均結(jié)果如圖2所示.由圖可得，ImSSL在各種不平衡比下都能達到最優(yōu)值.隨著不平衡程度的加劇，ImSSL的改善越發(fā)顯著.下面進一步驗證自監(jiān)督學(xué)習(xí)對不平衡節(jié)點分類任務(wù)的有效性.

隨著參數(shù)λ1、λ2、λ3的取值變化，ImSSL在Cora數(shù)據(jù)集上不平衡節(jié)點的分類結(jié)果如圖3所示.λ1、λ2、λ3的取值都在[0,1]內(nèi)變化，取值間隔為0.2.

(a)Accuracy (b)Macro_F (c)AUC圖2 不平衡比不同時ImSSL與GCN的性能對比Fig.2 Performance comparison of ImSSL and GCN with different imbalance ratios

由圖3可得到如下結(jié)論.

1)當(dāng)λ1=0時，由于沒有交叉熵損失監(jiān)督指導(dǎo)優(yōu)化方向，導(dǎo)致隨機分類，表明在節(jié)點分類中交叉熵損失是不可或缺的.

2)當(dāng)λ1> 0時，在交叉熵損失指導(dǎo)下分類效果明顯提升，但當(dāng)λ2=0，λ3=0時表現(xiàn)最差，這是由于當(dāng)λ1> 0，λ2=0，λ3=0時等同于GCN，不適合不平衡節(jié)點分類.

3)對于每個圖(對應(yīng)固定的λ1取值)來說，當(dāng)λ2取值為0.8或1且λ3取值為0.8時，性能相對最好，這表明自監(jiān)督對比損失和語義約束損失在訓(xùn)練中起到重要作用，可促使不平衡節(jié)點分類獲得更優(yōu)效果.

(a)λ1=0 (b)λ1=0.2 (c)λ1=0.4

為了考察參數(shù)λ1對分類結(jié)果的影響，選取結(jié)果相對較優(yōu)的λ2、λ3的取值，即λ2=0.8、λ3=0.8，AUC值變化如圖4所示.由圖可看到，當(dāng)λ1從0開始變大時，性能提升，當(dāng)λ2達到0.2時，性能最優(yōu)，之后呈現(xiàn)下降趨勢.

圖4 λ1對分類性能的影響Fig.4 Effect of λ1 on classification performance

上述分析表明，交叉熵損失、自監(jiān)督對比損失和語義約束損失三者共同作用才能獲得較優(yōu)的不平衡節(jié)點分類結(jié)果.

4 結(jié) 束 語

監(jiān)督信息不足與節(jié)點不平衡是圖數(shù)據(jù)分析挖掘中面臨的一個重要問題.本文提出基于自監(jiān)督學(xué)習(xí)的不平衡節(jié)點分類算法(ImSSL).一方面通過自監(jiān)督學(xué)習(xí)擴充監(jiān)督信息，另一方面通過自監(jiān)督學(xué)習(xí)增強節(jié)點的表達能力.通過對比實驗驗證本文算法在不平衡節(jié)點分類問題上的優(yōu)勢.在下一步的研究工作中，將針對圖數(shù)據(jù)的動態(tài)性，開展不平衡節(jié)點分類問題的研究.