基于图潜向量分布学习的图过采样方法

doi:10.3778/j.issn.1673-9418.2407119

摘要/Abstract

摘要： 现实世界中许多图数据存在类别分布不平衡的问题，其通常表现在节点、边和图三个级别。常用的基于过采样的图级不平衡处理方法，因样本缺乏多样性，会导致模型过拟合。针对该问题，提出一种图潜向量分布学习的图过采样方法（GLRD-GAN）。提出一种图潜向量分布学习方法，利用预训练的图变分自编码器（VGAE）和全连接神经网络学习少数类图样本在低维空间内的潜向量分布，在该分布上随机采样潜向量信息并与原少数类潜向量融合，保证了少数类潜向量的多样性。设计了一种基于双解码器的图样本生成器，经预训练的内积解码器和图卷积解码器充分利用采样的潜向量来分别生成图数据的拓扑结构和节点特征。通过GAN判别器检测生成样本的真伪和类别，监督生成样本的有效性，实现多样性的少数类图样本生成。在5个具有代表性的长尾图数据集上进行了对比实验和可视化观察，结果表明提出的基于图潜向量分布学习的图过采样方法在Acc和F1值上较其他方法平均高出1%~4%，且能够生成有效的少数类图样本。

关键词: 长尾问题, 图变分自编码器, 图潜向量, 生成对抗网络

Abstract: In the real world, many graph datasets suffer from class imbalance issues, typically manifesting at the node, edge, and graph levels. Common oversampling-based methods for addressing graph-level imbalance often lead to model overfitting due to a lack of sample diversity. To address this issue, a graph latent representation distribution learning-based graph oversampling method (GLRD-GAN) is proposed. Firstly, a graph latent representation distribution learning method is introduced, utilizing a pre-trained variational graph auto-encoder (VGAE) and a fully connected neural network to learn the latent representation distribution of minority class graph samples in the low-dimensional space. The latent representation information is randomly sampled on this distribution and fused with the original minority class latent representation, ensuring the diversity of the minority class latent representation. Secondly, a dual-decoder-based graph generator is designed. The pre-trained inner product decoder and graph convolution decoder make full use of the sampled latent representations to generate the topological structure and node features of graph data, respectively. Finally, a GAN discriminator is employed to detect the authenticity and class of the generated graphs, supervising the effectiveness of the generated samples, thereby achieving the generation of diverse minority class graph samples. Comparative experiments and visualization observations are conducted on five representative long-tail graph datasets. The results show that the proposed graph latent representation distribution learning-based graph oversampling method outperforms other methods by 1% to 4% in terms of Acc and F1 scores, and can generate effective minority class graph samples.

Key words: long-tail problem, variational graph auto-encoder, graph latent representation, generative adversarial network

任博, 董明刚, 于扬, 卢贤睿. 基于图潜向量分布学习的图过采样方法[J]. 计算机科学与探索, 2025, 19(7): 1808-1819.

REN Bo, DONG Minggang, YU Yang, LU Xianrui. Graph Oversampling Method Based on Graph Latent Representation Distribution Learning[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(7): 1808-1819.

参考文献

[1] 王兆慧, 沈华伟, 曹婍, 等. 图分类研究综述[J]. 软件学报, 2022, 33(1): 171-192.
WANG Z H, SHEN H W, CAO Q, et al. Survey on graph classification[J]. Journal of Software, 2022, 33(1): 171-192.
[2] IDAKWO G, THANGAPANDIAN S, LUTTRELL J, et al. Structure-activity relationship-based chemical classification of highly imbalanced Tox21 datasets[J]. Journal of Cheminformatics, 2020, 12: 1-19.
[3] JOHNSON J M, KHOSHGOFTAAR T M. Survey on deep learning with class imbalance[J]. Journal of Big Data, 2019, 6(1): 1-54.
[4] ZHAO T, JIANG T W, SHAN N, et al. A synergistic approach for graph anomaly detection with pattern mining and feature learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 33(6): 2393-2405.
[5] DING K Z, WANG J L, LI J D, et al. Graph prototypical networks for few-shot learning on attributed networks[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management. New York: ACM, 2020: 295-304.
[6] 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. Palo Alto: AAAI, 2020: 2879-2885.
[7] ZHAO T X, ZHANG X, WANG S H. GraphSMOTE: imbalanced node classification on graphs with graph neural networks[C]//Proceedings of the 14th ACM International Conference on Web Search and Data Mining. New York: ACM, 2021: 833-841.
[8] PARK J, SONG J, YANG E. GraphENS: neighbor-aware ego network synthesis for class-imbalanced node classification[C]//Proceedings of the 10th International Conference on Learning Representations, 2022.
[9] LIU Z M, NGUYEN T K, FANG Y. Tail-GNN: tail-node graph neural networks[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2021: 1109-1119.
[10] 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. New York: ACM, 2022: 2434-2443.
[11] KIPF T N, WELLING M. Variational graph auto-encoders[EB/OL]. [2024-05-13]. https://arxiv.org/abs/1611.07308.
[12] SIMONOVSKY M, KOMODAKIS N. GraphVAE: towards generation of small graphs using variational autoencoders[C]//Proceedings of the 27th International Conference on Artificial Neural Networks and Machine Learning. Cham: Springer, 2018: 412-422.
[13] JIN W, BARZILAY R, JAAKKOLA T. Junction tree variational autoencoder for molecular graph generation[C]//Proceedings of the 35th International Conference on Machine Learning, 2018: 2323-2332.
[14] MA C S, ZHANG X L. GF-VAE: a flow-based variational autoencoder for molecule generation[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management. New York: ACM, 2021: 1181-1190.
[15] WANG Y, ZHAO Y Y, SHAH N, et al. Imbalanced graph classification via graph-of-graph neural networks[C]//Proceedings of the 31st ACM International Conference on Information & Knowledge Management. New York: ACM, 2022: 2067-2076.
[16] ZHAO T X, LUO D S, ZHANG X, et al. TopoImb: toward topology-level imbalance in learning from graphs[C]//Proceedings of the 1st Learning on Graphs Conference, 2022: 37.
[17] TANG H, LIANG X. Where to find fascinating inter-graph super-vision: imbalanced graph classification with kernel information bottleneck[C]//Proceedings of the 31st ACM International Conference on Multimedia. New York: ACM, 2023: 3240-3249.
[18] 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.
[19] 王晓霞, 李雷孝, 林浩. SMOTE类算法研究综述[J]. 计算机科学与探索, 2024, 18(5): 1135-1159.
WANG X X, LI L X, LIN H. Survey of research on SMOTE type algorithms[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(5): 1135-1159.
[20] ZHANG H Y, CISSE M, DAUPHIN Y N, et al. Mixup: beyond empirical risk minimization[EB/OL]. [2024-05-13]. https://arxiv.org/abs/1710.09412.
[21] KINGMA D P, WELLING M. Auto-encoding variational bayes[C]//Proceedings of the 2nd International Conference on Learning Representations, 2014.
[22] 赵海霞, 石洪波, 武建, 等. 基于条件生成对抗网络的不平衡学习研究[J]. 控制与决策, 2021, 36(3): 619-628.
ZHAO H X, SHI H B, WU J, et al. Research on imbalanced learning based on conditional generative adversarial networks[J]. Control and Decision, 2021, 36(3): 619-628.
[23] XU K, HU W H, LESKOVEC J, et al. How powerful are graph neural networks?[C]//Proceedings of the 7th International Conference on Learning Representations, 2019.
[24] TOIVONEN H, SRINIVASAN A, KING R D, et al. Statistical evaluation of the predictive toxicology challenge 2000-2001[J]. Bioinformatics, 2003, 19(10): 1183-1193.
[25] DEBNATH A K, LOPEZ DE COMPADRE R L, DEBNATH G, et al. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity[J]. Journal of Medicinal Chemistry, 1991, 34(2): 786-797.
[26] BORGWARDT K M, ONG C S, SCH?NAUER S, et al. Protein function prediction via graph kernels[J]. Bioinformatics, 2005, 21.
[27] SUTHERLAND J J, O'BRIEN L A, WEAVER D F. Spline-fitting with a genetic algorithm: a method for developing classification structure-activity relationships[J]. Journal of Chemical Information and Computer Sciences, 2003, 43(6): 1906-1915.
[28] FEY M, LENSSEN J E. Fast graph representation learning with PyTorch geometric[EB/OL]. [2024-05-13]. https://arxiv.org/abs/1903.02428.
[29] SUN F Y, HOFFMANN J, VERMA V, et al. InfoGraph: unsupervised and semi-supervised graph-level representation learning via mutual information maximization[EB/OL]. [2024- 05-13]. https://arxiv.org/abs/1908.01000.
[30] YOU Y N, CHEN T L, SUI Y D, et al. Graph contrastive learning with augmentations[C]//Advances in Neural Information Processing Systems 33, 2020: 5812-5823.
[31] VELIČKOVIĆ P, CUCURULL G, CASANOVA A, et al. Graph attention networks[EB/OL]. [2024-05-13]. https://arxiv.org/abs/1710.10903.
[32] HAMILTON W, YING Z, LESKOVEC J. Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems 30, 2017: 1024-1034.
[33] BoRGWARDT K M, KRIEGEL H P. Shortest-path kernels on graphs[C]//Proceedings of the 5th IEEE International Conference on Data Mining. Piscataway: IEEE, 2005: 74-81.