Boundary Oversampling Based Graph Node Imbalance Classification Algorithm

doi:10.3778/j.issn.1002-8331.2310-0438

Abstract

Abstract: In the real world, financial fraud detection and disease diagnosis are typical instances of graph imbalanced problems. Graph neural networks based on oversampling are among the commonly employed methods to address such issues. However, this approach encounters challenges in ensuring the diversity of generated boundary samples, which can lead to a reduction in classification performance. This paper introduces a graph node imbalanced classification algorithm based on borderline oversampling (ImBS) to enhance the diversity of generated samples. Firstly, ImBS selects high-confidence samples from each class as sampling anchors using a two-layer graph neural classification network, enhancing the representativeness of the anchors. Next, to make the distribution of generated samples more reasonable, this paper utilizes the obtained confusion matrix from the previous step to calculate the distribution ratio of misclassified instances in the minority class. Based on this distribution ratio, an adaptive computation of the number of generated samples among different classes is proposed. Building upon this, a hybrid oversampling method based on anchors is introduced. It oversamples boundary nodes by blending dissimilar anchor features, aiming to increase sample diversity and expand the decision boundary of the minority class. Additionally, to prevent the generation of harmful connections, this paper introduces a personalized PageRank method for neighborhood distribution of oversampled samples. Experimental results on three real datasets (Cora, CiteSeer, and Cora-Full) demonstrate a clear advantage of this method in comparison to nine representative approaches.

Key words: graph neural network, imbalanced node classification, boundary oversampling

摘要： 在现实世界中，金融欺诈检测和疾病诊断是典型的图不平衡问题，基于过采样的图神经网络是解决此类问题的常用方法之一。然而，该方法难以保证生成边界样本的多样性，易导致分类性能下降。提出一种基于边界过采样的图节点不平衡分类算法（ImBS）来提升生成样本的多样性。ImBS通过双层图神经分类网络选择出每个类别中高置信度样本作为采样锚点，提高锚点的代表性。为了使生成样本分布更加合理，利用上一步得到的混淆矩阵，计算少数类误判的分布比例。并基于该分布比例，自适应计算不同类间生成的样本数量。在此基础上，提出基于锚点的混合过采样方法。通过混合异类锚点特征的方式过采样边界节点，达到增加样本多样性和扩展少数类决策边界的目的。此外，为了防止产生有害连接，引入个性化PageRank方法，为过采样样本生成邻域分布。在三个真实的数据集（Cora、CiteSeer和Cora-Ful）上的实验表明，该方法与9个代表性的方法对比具有明显优势。

关键词: 图神经网络, 不平衡节点分类, 边界过采样

WU Tianhao, DONG Minggang, TAN Ruoqi. Boundary Oversampling Based Graph Node Imbalance Classification Algorithm[J]. Computer Engineering and Applications, 2024, 60(13): 92-101.

武天昊, 董明刚, 谭若琦. 基于边界过采样的图节点不平衡分类算法[J]. 计算机工程与应用, 2024, 60(13): 92-101.

References

[1] YE X B, GUAN Q, LUO W, et al. Molecular substructure graph attention network for molecular property identification in drug discovery[J]. Pattern Recognition, 2022, 128: 108659.
[2] PENG H, LI J, HE Y, et al. Large-scale hierarchical text classification with recursively regularized deep graph-CNN[C]//Proceedings of the 2018 World Wide Web Conference on World Wide Web(WWW’18), Lyon, France, 2018: 1063-1072.
[3] WANG D, QI Y, LIN J, et al. A semi-supervised graph attentive network for financial fraud detection[C]//Proceedings of the 2019 IEEE International Conference on Data Mining (ICDM), Beijing, China, 2019: 598-607.
[4] YING R, HE R, CHEN K, et al. Graph convolutional neural networks for web-scale recommender systems[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, United Kingdom, 2018: 974-983.
[5] LIU Y, SUN Z, ZHANG W. Improving fraud detection via hierarchical attention-based graph neural network[J]. Journal of Information Security and Applications, 2023, 72: 103399.
[6] ZHANG J, HE X, QING L, et al. Multi-relation graph convolutional network for Alzheimer’s disease diagnosis using structural MRI[J]. Knowledge-Based Systems, 2023, 270: 110546.
[7] GORI M, MONFARDINI G, SCARSELLI F. A new model for learning in graph domains[C]//Proceedings of the 2005 IEEE International Joint Conference on Neural Networks, Montreal, 2005: 729-734.
[8] LUO X, ZHAO Y, QIN Y, et al. Towards semi-supervised universal graph classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2023: 1-13.
[9] WANG Z, WANG Q, ZHU T, et al. Extending LINE for network embedding with completely imbalanced labels[J]. International Journal of Data Warehousing and Mining, 2020, 16(3): 20-36.
[10] CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2002, 16: 321-357.
[11] YUN S, KIM K, YOON K, et al. LTE4G: long-tail experts for graph neural networks[C]//Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022: 2434-2443.
[12] ZHAO T, ZHANG X, WANG S. GraphSMOTE: imbalanced node classification on graphs with graph neural networks[C]//Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021: 833-841.
[13] QU L, ZHU H, ZHENG R, et al. ImGAGN: imbalanced network embedding via generative adversarial graph networks[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021: 1390-1398.
[14] PARK J, SONG J G, YANG E. GraphENS: neighbor-aware ego network synthesis for class-imbalanced node classification[C]//Proceedings of the International Conference on Learning Representations, 2022.
[15] ANDERSEN R, CHUNG F, LANG K. Local graph partitioning using PageRank vectors[C]//Proceedings of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), Berkeley, CA, USA, 2006: 475-486.
[16] SEN P, NAMATA G, BILGIC M, et al. Collective classification in network data[J]. AI Magazine, 2008, 29(3): 93-106.
[17] BOJCHEVSKI A, GüNNEMANN S. Deep Gaussian embedding of graphs: unsupervised inductive learning via ranking[J]. arXiv:1707.03815, 2017.
[18] YUAN B, MA X L. Sampling + reweighting: boosting the performance of AdaBoost on imbalanced datasets[C]//Proceedings of the 2012 International Joint Conference on Neural Networks (IJCNN), Brisbane, Australia, 2012: 1-6.
[19] ANDO S, HUANG C Y. Deep over-sampling framework for classifying imbalanced data[M]//CECI M, HOLLMéN J, TODOROVSKI L, et al. Machine learning and knowledge discovery in databases. Cham: Springer International Publishing, 2017: 770-785.
[20] KINGMA D P, BA J. Adam: a method for stochastic optimization[J]. arXiv:1412.6980, 2014.