用于不平衡節點分類的集成圖神經網絡模型

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

關鍵詞：圖神經網絡；不平衡節點分類；集成學習

中圖分類號：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? 引? 言

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

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

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

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

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

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

1? 相關工作

1.1? 類不平衡問題

類不平衡問題在實際應用中很常見，長期以來一直是機器學習領域的經典研究方向。針對該問題的傳統方法通常可分為三類，即數據級、算法級和混合型。數據級方法通過過采樣少數類或欠采樣多數類來平衡訓練實例，如隨機欠采樣和SMOTE[6]過采樣等。而算法級方法通過為每個類別分配不同的權重來緩解類不平衡問題，如重加權。混合型方法是將上述一個或兩個類別的多個算法結合起來，如SMOTEBoost和UnderOverBagging等。此外，研究人員引入了一些新方法，如度量學習、元學習，還有基于神經網絡的不平衡數據學習方法，然而，我們的目標是解決圖結構上的類不平衡問題，所以這些算法并不適用。

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

1.2? 圖神經網絡

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

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

2? 模型方法

2.1? 問題描述

在本文中，我們使用G={V， A， F}表示一個屬性網絡，其中V={v1，…，vn}是n個節點的集合，A∈Rn×n是G的鄰接矩陣，F∈Rn×d表示節點的屬性矩陣，其中F[ j，：]1×d是節點j的節點屬性，d是節點屬性的維度。訓練集中，VL代表有標簽的節點，YL是其對應的標簽，VU代表無標簽的節點，YU是其對應的標簽，共有m個類別，{C1，…，Cm}，|Ci|是第i類的大小，指屬于該類別的樣本數量，我們使用不平衡率? 來衡量類不平衡的程度。給定節點類不平衡的屬性網絡G，以及節點VL子集的標簽，我們的目標是學習一個對多數類節點和少數類節點都有效的分類器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。每個節點與一個F維特征向量相關聯，X∈Rn×F表示所有節點的特征矩陣。我們使用具有兩層的半監督分類GCN模型作為基分類器，每層的計算變換為：

（1）

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

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

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

（3）

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

（4）

2.3? 圖神經網絡集成模型（Bagging-GCN）

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

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

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

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

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

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

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

基分類器GCN

迭代次數m

步驟：forM=1 to m

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

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

end for

輸出：

3? 實驗結果及分析

3.1? 數據集

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

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

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

3.2? 實驗設置

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

3.3? 評價指標

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

3.4? 實驗對比模型

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

Origin：原始實現。

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

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

SMOTE：通過在輸入空間內插值來生成樣本。

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

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

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

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

3.5? 實驗結果

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

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

3.5.2? 基分類器數量的影響

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

4? 結? 論

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

參考文獻：

[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—），女，漢族，山西呂梁人，碩士研究生在讀，研究方向：智能數據開發與應用。

收稿日期：2022-10-07