摘? 要：為解決圖神經(jīng)網(wǎng)絡（GNN）上不平衡節(jié)點的分類問題，提出一種Bagging集成模型，該模型使用圖卷積網(wǎng)絡（GCN）作為基分類器。在該模型中，先對若干基分類器進行并行訓練，然后使用多數(shù)投票的方式對這些基分類器的預測結果進行集成，最終完成分類任務。實驗結果表明，該文提出的模型顯著優(yōu)于其他現(xiàn)有基線方法，驗證了其在不平衡節(jié)點分類中的有效性。

關鍵詞：圖神經(jīng)網(wǎng)絡；不平衡節(jié)點分類；集成學習

中圖分類號：TP183? ? 文獻標識碼：A? ? 文章編號：2096-4706（2023）03-0029-04

Ensemble Graph Neural Network Model for Imbalanced Node Classification

GUO Mengxin

（Taiyuan Normal University， Jinzhong? 030619， China）

Abstract： To solve the classification problem of unbalanced nodes on graph neural network （GNN）， a Bagging ensemble model is proposed， which uses GCN as the base classifier. In this model， several base classifiers are trained in parallel， and then the prediction results of these base classifiers are integrated by majority voting to complete the classification task finally. Experimental results show that the proposed model in this paper is significantly superior to other existing baseline methods， and its effectiveness in unbalanced node classification is verified.

Keywords： graph neural network; imbalanced node classification; ensemble learning

0? 引? 言

近年來，隨著圖神經(jīng)網(wǎng)絡（Graph Neural Network， GNN）的發(fā)展，在圖學習方面取得了很大的進步。一個典型的任務是半監(jiān)督節(jié)點分類，GNN展現(xiàn)了其優(yōu)異的性能，并正在迅速發(fā)展，例如，圖卷積網(wǎng)絡（Graph Convolutional Network， GCN）[1]通過使用簡化的一階近似有效地利用譜域中的特征；GraphSage[2]利用了空域中的特征，并且能更好地適應不同的圖形拓撲。盡管取得了這些進展，但現(xiàn)有的工作還是主要集中在平衡的節(jié)點分類上。

在許多實際應用中，我們經(jīng)常面臨不平衡節(jié)點分類問題。因為我們只得到了有限的標記數(shù)據(jù)，這使得有標簽的少數(shù)類樣本非常少，所以半監(jiān)督設置就會進一步放大類不平衡問題。而多數(shù)類可能會主導GNN的損失函數(shù)，使得訓練的GNN對這些多數(shù)類進行過度分類，無法準確預測少數(shù)類樣本，所以不平衡節(jié)點分類給現(xiàn)有的GNN帶來了挑戰(zhàn)，這一問題導致許多具有不平衡類分布的實際應用無法采用GNN，因此，開發(fā)用于類不平衡節(jié)點分類的GNN是非常重要的。

在機器學習領域，傳統(tǒng)的類不平衡問題得到了廣泛的研究。主要有三種方法：數(shù)據(jù)級方法、算法級方法和混合方法。然而，節(jié)點之間的關系是圖數(shù)據(jù)中的關鍵信息，傳統(tǒng)的機器學習技術則假設樣本是獨立同分布的，因此，傳統(tǒng)的不平衡學習算法并不適用于圖數(shù)據(jù)。

雖然對傳統(tǒng)數(shù)據(jù)的不平衡分類進行了很好的研究，但對類不平衡問題的圖神經(jīng)網(wǎng)絡算法研究還比較有限。DRGCN[3]是解決圖上類不平衡問題的先驅(qū)工作，該方法提出了一個類條件對抗正則化器和一個潛在N分布對齊正則化器，但不能擴展到大型圖；GraphSMOTE[4]通過預訓練邊生成器，從而將SMOTE推廣到圖域，從而為來自SMOTE的新合成節(jié)點添加關系信息。然而，計算所有節(jié)點對之間的相似度和預訓練邊生成器的任務非常繁重。

由于單個模型很難準確預測不平衡數(shù)據(jù)集上的罕見點和少數(shù)點，總體性能有限，而集成學習可以聚合多個基分類器從而提高分類器泛化性能。所以，我們提出了一種圖卷積網(wǎng)絡集成學習模型來處理不平衡節(jié)點分類問題。具體來講，將Bagging[5]算法與GCN相結合，通過并行化訓練GCN分類器，并根據(jù)多數(shù)投票方式來確定最終分類結果，從而提高GCN在不平衡節(jié)點分類的性能。

實驗結果表明，與現(xiàn)有的不平衡節(jié)點分類方法相比，本文提出的集成模型顯著優(yōu)于其他基線方法，能更有效地解決不平衡節(jié)點分類問題。

1? 相關工作

1.1? 類不平衡問題

類不平衡問題在實際應用中很常見，長期以來一直是機器學習領域的經(jīng)典研究方向。針對該問題的傳統(tǒng)方法通?？煞譃槿?，即數(shù)據(jù)級、算法級和混合型。數(shù)據(jù)級方法通過過采樣少數(shù)類或欠采樣多數(shù)類來平衡訓練實例，如隨機欠采樣和SMOTE[6]過采樣等。而算法級方法通過為每個類別分配不同的權重來緩解類不平衡問題，如重加權?；旌闲头椒ㄊ菍⑸鲜鲆粋€或兩個類別的多個算法結合起來，如SMOTEBoost和UnderOverBagging等。此外，研究人員引入了一些新方法，如度量學習、元學習，還有基于神經(jīng)網(wǎng)絡的不平衡數(shù)據(jù)學習方法，然而，我們的目標是解決圖結構上的類不平衡問題，所以這些算法并不適用。

最近，人們提出了一些不平衡網(wǎng)絡嵌入方法來解決圖結構數(shù)據(jù)的不平衡學習問題[7-10]。如RECT[11]在學習類級語義嵌入之上提出了兩個正則化術語，以解決極端情況下的不平衡學習，DRGCN提出了兩種正則化方法來解決不平衡網(wǎng)絡嵌入問題，GraphSMote使用GNN編碼器學習節(jié)點嵌入，并使用額外的邊生成器生成連接合成少數(shù)節(jié)點的邊。

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

近年來，隨著對非歐幾里得空間學習和樣本間豐富關系信息建模需求的增加，GNN受到了越來越多的關注，并得到了快速發(fā)展。GNN將卷積神經(jīng)網(wǎng)絡推廣到圖結構數(shù)據(jù)，并在圖結構數(shù)據(jù)建模方面顯示出了強大的能力。一般來說，現(xiàn)有的GNN框架可以分為兩類，即基于譜域的和基于空域的?；谧V域的圖卷積網(wǎng)絡通過計算圖的拉普拉斯特征分解來定義傅里葉變換中的卷積運算，如GCN，它是目前使用最廣泛的GNN之一?；诳沼虻膱D卷積網(wǎng)絡直接定義在圖上，對目標節(jié)點及其拓撲鄰居進行操作，從而實現(xiàn)對圖結構的聚合，如GraphSage。

盡管各種GNN都取得了成功，但是這些方法沒有考慮類不平衡問題，由于這一問題廣泛存在于現(xiàn)實應用中，可能會降低GNN的性能，因此不適用于不平衡節(jié)點分類問題。

2? 模型方法

2.1? 問題描述

在本文中，我們使用G={V， A， F}表示一個屬性網(wǎng)絡，其中V={v1，…，vn}是n個節(jié)點的集合，A∈Rn×n是G的鄰接矩陣，F(xiàn)∈Rn×d表示節(jié)點的屬性矩陣，其中F[ j，：]1×d是節(jié)點j的節(jié)點屬性，d是節(jié)點屬性的維度。訓練集中，VL代表有標簽的節(jié)點，YL是其對應的標簽，VU代表無標簽的節(jié)點，YU是其對應的標簽，共有m個類別，{C1，…，Cm}，|Ci|是第i類的大小，指屬于該類別的樣本數(shù)量，我們使用不平衡率? 來衡量類不平衡的程度。給定節(jié)點類不平衡的屬性網(wǎng)絡G，以及節(jié)點VL子集的標簽，我們的目標是學習一個對多數(shù)類節(jié)點和少數(shù)類節(jié)點都有效的分類器f，即f （V， A， F）→Y。

2.2? GCN模型

輸入無向圖G={V， A， F}，其對應的鄰接矩陣A∈Rn×n是一個描述其邊的n×n稀疏矩陣，如果i和j之間有邊，則（i， j）項等于1，否則為0。度矩陣D是對角線矩陣，其中對角線上的值等于每個頂點的度，可以計算為di=∑jaij。每個節(jié)點與一個F維特征向量相關聯(lián)，X∈Rn×F表示所有節(jié)點的特征矩陣。我們使用具有兩層的半監(jiān)督分類GCN模型作為基分類器，每層的計算變換為：

（1）

其中， 是通過? 獲得的歸一化鄰接矩陣，W（l）是各層的可訓練權重。σ（·）表示激活函數(shù)（通常為ReLU）， 是第L隱藏層的輸入激活矩陣，其中每行表示dl維節(jié)點表示向量。初始節(jié)點表示僅為原始輸入特征：

H（0）=X? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

兩層GCN模型可以根據(jù)頂點特征X和? 定義為：

（3）

GCN通過反向傳播學習算法進行訓練。最后一層使用softmax函數(shù)進行分類，我們求所有標記節(jié)點的交叉熵損失值：

（4）

2.3? 圖神經(jīng)網(wǎng)絡集成模型（Bagging-GCN）

本文結合隨機采樣和并行集成方法來構造不平衡節(jié)點的集成分類學習模型，多個弱分類器與Bagging技術相結合，形成一個強分類器。在訓練M個基分類器之后，對M個基分類器的結果進行多數(shù)投票，可以預測輸入樣本的類別，過程如圖1所示。

集成模型中的基分類器雖然所用樣本數(shù)據(jù)屬于同一個訓練集，但是在訓練過程中對樣本數(shù)據(jù)的采樣與訓練是相互獨立的，只是對其輸出結果進行多數(shù)投票。主要原理是利用不同基分類器之間的差異性，通過各分類器的投票結果來降低分類錯誤，提高模型的泛化能力。具體實現(xiàn)過程如下：

（1）構建單個基分類器：按照實驗規(guī)定對每一類訓練樣本進行抽取，結合這些被抽取的所有樣本構建基分類器。

（2）形成集成學習系統(tǒng)：對訓練集重復執(zhí)行步驟來構建一組基分類器，并將獲取的基分類器用于Bagging集成學習。

（3）結合所有基分類器的預測值，由相對多數(shù)投票決定最終的分類結果。

在訓練學習的每次迭代中，用相應的訓練數(shù)據(jù)來訓練基分類器，M個基分類器經(jīng)過并行訓練之后，根據(jù)多數(shù)投票原則來確定集成模型的輸出。集成模型的偽代碼如下：

輸入：數(shù)據(jù)集D={（x1， y1），（x2， y2），（x3， y3），…，（xn， yn）}

基分類器GCN

迭代次數(shù)m

步驟：forM=1 to m

DM=bootstrap（D）? ?//使用訓練集進行M次采樣

GM=GCN（DM）? ? ? ?//采樣集DM訓練第M個分類器

end for

輸出：

3? 實驗結果及分析

3.1? 數(shù)據(jù)集

我們對兩個廣泛使用于節(jié)點分類的數(shù)據(jù)集Cora和BlogCatalog進行了實驗，這兩個數(shù)據(jù)集的詳細介紹如下：

Cora是一個引文網(wǎng)絡數(shù)據(jù)集，包含來自7個領域的2 708篇論文，每個節(jié)點都有一個1 433維的屬性向量，該圖中總共有5 429個引用鏈接。在這個數(shù)據(jù)集中，類分布是相對平衡的，所以我們使用了一個模擬的不平衡設置：選取三個隨機類作為少數(shù)類，并對其進行欠采樣。所有多數(shù)類都有20個節(jié)點作為訓練集，每個少數(shù)類的訓練節(jié)點數(shù)為20乘以不平衡率，不平衡率默認為0.5。選取500個節(jié)點作為驗證集，并在1 000個標記節(jié)點的測試集上進行預測和評估。

BlogCatalog是一個社交網(wǎng)絡數(shù)據(jù)集，共有來自38個類別的10 312名博主和333 983條友誼邊緣，數(shù)據(jù)集不包含節(jié)點屬性。然后，使用從Deepwalk獲得的64維嵌入向量對每個節(jié)點進行屬性化。此數(shù)據(jù)集中的類遵循真正的不平衡分布，14個類小于100，8個類大于500。對于此數(shù)據(jù)集，使用每個類25%的樣本進行訓練，25%用于驗證，其余50%用于測試。

3.2? 實驗設置

在我們提出的模型中，使用了7個基分類器，所有基分類器都是兩層的GCN，學習率為0.01，權重衰減為5×10-4（L2正則化），隱藏單元數(shù)為16，dropout設置為0.5，我們采用ADAM優(yōu)化算法對所有模型進行訓練，所有模型都經(jīng)過訓練直到收斂，最大訓練周期為5 000，此外，所有實驗都是在一臺機器上進行的，在Pytorch和Python 3.6中實現(xiàn)。

3.3? 評價指標

我們采用了兩個評價指標：準確率（ACC）和Macro-F1。ACC同時對所有測試節(jié)點進行計算，代表了整體分類的準確率，Macro-F1值常用于不平衡節(jié)點分類，能更好地反映不平衡節(jié)點分類模型的好壞，每一類的Macro-F1值都是單獨計算，然后對其進行非加權平均。

3.4? 實驗對比模型

為了證明我們提出模型的有效性，我們將其與其他8個基線進行了比較：

Origin：原始實現(xiàn)。

Over-Sampling：直接從少數(shù)樣本中重復抽樣。

Re-weight：將較高的損失權重分配給少數(shù)類樣本。

SMOTE：通過在輸入空間內(nèi)插值來生成樣本。

Embed-SMOTE：通過在嵌入空間內(nèi)插值對SMOTE進行擴展。

RECT：在學習類級語義嵌入之上提出了兩個正則化術語。

DRGCN：通過使用對抗訓練范式鼓勵潛在嵌入空間中的類之間的分離來解決類不平衡問題。

GraphSMOTE：構造了一個嵌入空間來編碼節(jié)點之間的相似性，在此空間合成新樣本以確保真實性，同時訓練邊生成器來建模關系信息，并將其提供給這些新樣本。

3.5? 實驗結果

3.5.1? 與基線方法的比較結果

為了評估我們提出的模型在類不平衡節(jié)點分類任務中的有效性，我們在上述兩個數(shù)據(jù)集上將其與其他八個基線進行了比較。每個實驗進行5次，以減輕隨機性。從表1中，我們可以看出，與其他分類模型相比，該模型的表現(xiàn)優(yōu)于其他所有基線，例如，與GraphSMOTE相比，我們提出的模型在Cora數(shù)據(jù)集上的Acc值和Macro-F1值分別提高了3.4%和2.3%，這些結果驗證了所提出框架的有效性。

3.5.2? 基分類器數(shù)量的影響

我們改變了基分類器的數(shù)量，用不同的評價指標檢驗了我們提出的模型在Cora數(shù)據(jù)集上的分類性能?；诸惼鞯臄?shù)量從3個增加到11個，訓練集、驗證集和測試集的劃分采取前面的方式。我們分別進行了10次實驗，每個基分類器分別訓練了200個周期，表2顯示了實驗的平均結果。實驗結果表明，當基分類器數(shù)量較少時，分類性能隨著基分類器數(shù)量的增加而提高，當基分類器的數(shù)目達到一定程度時，由于過擬合，各項指標都會降低。

4? 結? 論

在本文中，為了解決圖中節(jié)點的類不平衡問題，我們提出了一種圖神經(jīng)網(wǎng)絡集成學習模型。在所提出的模型中，采用Bagging集成學習方法，多個GCN被用作基分類器，用每個基分類器對數(shù)據(jù)特征進行提取和學習，所有基分類器并行訓練，最后對這些模型訓練所得結果進行多數(shù)投票確定最終結果。在兩個數(shù)據(jù)集上的實驗結果表明，本文提出的方法在不平衡節(jié)點分類任務上優(yōu)于其他基線。在之后的研究中，我們希望將該模型擴展到更多的應用領域。

參考文獻：

[1] KIPF T N，WELLING M. Semi-Supervised Classification with Graph Convolutional Networks [J/OL].arXiv： 1609.02907 [cs.LG].[2022-09-26].https：//arxiv.org/abs/1609.02907v3.

[2] HAMILTON W L，YING R，LESKOVEC J. Inductive representation learning on large graphs [C]//NIPS'17：Proceedings of the 31st International Conference on Neural Information Processing Systems.Long Beach：Curran Associates Inc.，2017：1025–1035.

[3] SHI M，TANG Y F，ZHU X Q，et al. Multi-Class Imbalanced Graph Convolutional Network Learning [C]//Proceedings of the 29th International Joint Conference on Artificial Intelligence.Yokohama：[s.n.]，2021：2862-2868.

[4] ZHAO T X，ZHANG X，WANG S H. GraphSMOTE：Imbalanced Node Classification on Graphs with Graph Neural Networks [J/OL].arXiv： 2103.08826 [cs.LG].[2022-09-20].https：//arxiv.org/abs/2103.08826.

[5] BREIMAN L. Bagging Predictors [J].Machine learning，1996，24（2）：123-140.

[6] FERN?NDEZ A，GARCIA S，HERRERA F，et al. SMOTE for Learning from Imbalanced Data：Progress and Challenges，Marking the 15-year Anniversary [J].The Journal of Artificial Intelligence Research，2018，61：863-905.

[7] CHEN D L，LIN Y K，ZHAO G X，et al.Topology-Imbalance Learning for Semi-Supervised Node Classification [J/OL].arXiv： 2110.04099 [cs.LG].[2022-09-20].https：//arxiv.org/abs/2110.04099.

[8] WU L R，LIN H T，GAO Z Y，et al. GraphMixup：Improving Class-Imbalanced Node Classification on Graphs by Self-supervised Context Prediction [J/OL].arXiv： 2106.11133 [cs.LG].[2022-09-20].https：//arxiv.org/abs/2106.11133.

[9] WANG Y，AGGARWAL C，DERR T.Distance-wise Prototypical Graph Neural Network in Node Imbalance Classification [J/OL]. arXiv： 2110.12035 [cs.LG].[2022-09-20].https：//arxiv.org/abs/2110.12035v1.

[10] LIU Y，AO X，QIN Z D，et al. Pick and Choose： A GNN-based Imbalanced Learning Approach for Fraud Detection [C]//Proceedings of the Web Conference 2021.Ljubljana：Association for Computing Machinery.2021：3168-3177.

[11] WANG Z，YE X J，WANG C K，et al. Network Embedding With Completely-Imbalanced Labels [J].IEEE Transactions on Knowledge and Data Engineering，2021，33（11）：3634-3647.

作者簡介：郭夢昕（1996—），女，漢族，山西呂梁人，碩士研究生在讀，研究方向：智能數(shù)據(jù)開發(fā)與應用。

收稿日期：2022-10-07