Cross-View Negative-Free Contrastive Learning for Graph Anomaly Detection with High-Order Structure Augmentation

doi:10.3778/j.issn.1673-9418.2308043

Abstract

Abstract: Graph anomaly detection has practical applications in various fields, such as cyber security, financial evaluation and medical care. Recently, contrastive-based and generative-based detection frameworks have achieved remarkable performance improvements. However, most of the existing paradigms overlook the drawback that the GCN-based framework may unconsciously aggregate abnormal nodes with their neighborhood normal partners. Moreover, these detection algorithms lack attention to high-order structural information. These lead to a reduction in the distinction between normal nodes and their opponents. To bridge the gaps above, this paper proposes a cross-view negative-free contrastive learning utilizing high-order structure for graph anomaly detection (CNCL-GAD) in this paper. Especially, different from the existing single-view contrastive paradigm, this paper develops the high-order structure as the augmented view to introduce more global abnormality discrimination with multi-view contrastive learning for graph anomaly detection (GAD). Then, to mitigate the false-negative phenomenon of imbalanced data in GAD tasks where the majority of selected contrastive negative samples are normal subgraphs, this paper proposes the cross-view negative-free contrastive strategy to only pull the positive subgraphs’ pairs between two views as close as possible. Furthermore, this paper integrates intra-view node-subgraph contrastive modules, attribute reconstruction modules, and cross-view subgraph-subgraph contrastive modules to simultaneously obtain more distinctions on structure and attribute. The extensive experiments conducted on benchmark datasets show that the proposed method achieves competitive or even superior performance compared with existing competitors.

Key words: negative-free contrastive, graph anomaly detection, high-order structure

摘要： 图异常检测在网络安全、金融评估和医疗保健等多个领域都有广泛的实际应用。近年来，基于对比学习和基于生成重构的图异常检测算法框架取得了显著的性能提升。然而，大多数基于图神经网络的范式忽略了一个内在的缺点，即可能会无意识地将异常节点与其邻域正常节点聚合在一起。此外，现有的检测算法缺乏对高阶结构信息的关注，导致正常节点与异常节点之间的判别性下降。为了改善以上缺点，提出了一种高阶结构增强的跨视图无负样本对比的图异常检测算法（CNCL-GAD）。与现有的单视图对比范式不同，提出了以高阶结构信息作为增强视图，通过多视图对比学习方法为图异常检测任务（GAD）引入更多、更丰富的判别信息。为了缓解图异常检测任务中正常样本与异常样本类别不平衡导致的对比负样本对大多数是同一类别的现象，提出了跨视图无负样本对比策略，即只将两个视图之间的正样本子图对拉近。将视图内节点-子图对比模块、属性重构模块和跨视图子图-子图对比模块联合训练，以获得更好的检测性能。在现有的公开数据集上进行了大量实验，与其他竞争算法相比，所提出的算法实现了有竞争力甚至更优越的性能。

关键词: 无负样本对比, 图异常检测, 高阶结构

JIN Hu, HU Jingtao, WANG Siwei, ZHU En, LUO Lei, DUAN Jingcan. Cross-View Negative-Free Contrastive Learning for Graph Anomaly Detection with High-Order Structure Augmentation[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(10): 2678-2689.

金虎, 胡婧韬, 王思为, 祝恩, 罗磊, 段景灿. 高阶结构增强的跨视图无负样本对比的图异常检测算法[J]. 计算机科学与探索, 2024, 18(10): 2678-2689.

References

[1] DING K Z, LI J D, BHANUSHALI R, et al. Deep anomaly detection on attributed networks[C]//Proceedings of the 2019 SIAM International Conference on Data Mining, Calgary, May 2-4, 2019: 594-602.
[2] LIU Z Q, CHEN C C, YANG X X, et al. Heterogeneous graph neural networks for malicious account detection[C]//Proceed-ings of the 27th ACM International Conference on Information and Knowledge Management, Torino, Oct 22-26, 2018. New York: ACM, 2018: 2077-2085.
[3] DUAN J C, WANG S W, LIU X W, et al. GADMSL: graph anomaly detection on attributed networks via multi-scale substructure learning[EB/OL]. [2023-06-14]. https://arxiv.org/abs/2211.15255.
[4] LIU K, DOU Y T, ZHAO Y, et al. BOND: benchmarking unsupervised outlier node detection on static attributed graphs[C]//Advances in Neural Information Processing Systems 36, New Orleans, Nov 29-Dec 1, 2022: 27021-27035.
[5] CHENG D W, WANG X Y, ZHANG Y, et al. Graph neural network for fraud detection via spatial-temporal attention[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(8): 3800-3813.
[6] WANG S Q, ZENG Y J, LIU X W, et al. Effective end-to-end unsupervised outlier detection via inlier priority of discriminative network[C]//Advances in Neural Information Processing Systems 33, Vancouver, Dec 10-12, 2019: 5960-5973.
[7] YU G, WANG S Q, CAI Z P, et al. Deep anomaly discovery from unlabeled videos via normality advantage and self-paced refinement[C]//Proceedings of the 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition, New Orleans, Jun 21-24, 2022. Piscataway: IEEE, 2022: 13987-13998.
[8] LIANG J Q, JACOBS P, SUN J K, et al. Semi-supervised embedding in attributed networks with outliers[C]//Proceedings of the 2018 SIAM International Conference on Data Mining, California, May 3-5, 2018: 153-161.
[9] WANG D X, LIN J B, CUI P, et al. A semi-supervised graph attentive network for financial fraud detection[C]//Proceedings of the 2019 IEEE International Conference on Data Mining, Beijing, Nov 8-11, 2019. Piscataway: IEEE, 2019: 598-607.
[10] KUMAGAI A, IWATA T, FUJIWARA Y. Semi-supervised anomaly detection on attributed graphs[C]//Proceedings of the 2021 International Joint Conference on Neural Networks, Shenzhen, Jul 18-22, 2021. Piscataway: IEEE, 2021: 1-8.
[11] CHEN Y Q, ZHOU X, HUANG T S. One-class SVM for lear-ning in image retrieval[C]//Proceedings of the 2001 International Conference on Image Processing, Thessaloniki, Oct 7-10, 2001. Piscataway: IEEE, 2001: 34-37.
[12] BREUNIG M M, KRIEGEL H P, NG R T, et al. LOF: identifying density-based local outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Texas, May 16-18, 2000. New York: ACM, 2000: 93-104.
[13] PENG Z, LUO M N, LI J D, et al. ANOMALOUS: a joint modeling approach for anomaly detection on attributed networks[C]//Proceedings of the 2018 International Joint Conference on Artificial Intelligence, Stockholm, Jul 13-19, 2018: 3513-3519.
[14] PEROZZI B, AKOGLU L. Scalable anomaly ranking of attributed neighborhoods[C]//Proceedings of the 2016 International Conference on Data Mining, Barcelona, Dec 12-15, 2016: 207-215.
[15] YUAN X, ZHOU N, YU S, et al. Higher-order structure based anomaly detection on attributed networks[C]//Proceedings of the 2021 IEEE International Conference on Big Data, Dec 15-18, 2021. Piscataway: IEEE, 2021: 2691-2700.
[16] LIU Y X, LI Z, PAN S, et al. Anomaly detection on attributed networks via contrastive self-supervised learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 33(6): 2378-2392.
[17] JIN M, LIU Y X, ZHENG Y, et al. ANEMONE: graph anomaly detection with multi-scale contrastive learning[C]//Proceedings of the 2021 ACM International Conference on Information & Knowledge Management 30, Nov 1-5, 2021. New York: ACM, 2021: 3122-3126.
[18] ZHENG Y, JIN M, LIU Y X, et al. Generative and contrastive self-supervised learning for graph anomaly detection[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(12): 12220-12233.
[19] ZHANG J Q, WANG S Z, CHEN S C. Reconstruction enhanced multi-view contrastive learning for anomaly detection on attributed networks[C]//Proceedings of the 31st International Joint Conference on Artificial Intelligence, Vienna, Jul 23-29, 2022: 2376-2382.
[20] AGGARWAL C C, YU P S. Outlier detection for high dimensional data[C]//Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, Santa Barbara, May 21-24, 2001. New York: ACM, 2001: 37-46.
[21] CHANDOLA V, BANERJEE A, KUMAR V. Anomaly detec-tion: a survey[J]. ACM Computing Surveys, 2009, 41(3): 1-58.
[22] HASELMANN M, GRUBER D P, TABATABAI P. Anomaly detection using deep learning based image completion[C]//Proceedings of the 17th IEEE International Conference on Machine Learning and Applications, Orlando, Dec 17-20, 2018. Piscataway: IEEE, 2018: 1237-1242.
[23] LIAO Q, CHAI H Y, HAN H, et al. An integrated multi-task model for fake news detection[J]. IEEE Transactions on Know-ledge and Data Engineering, 2021, 34(11): 5154-5165.
[24] DING K Z, LI J D, LIU H. Interactive anomaly detection on attributed networks[C]//Proceedings of the 12th ACM International Conference on Web Search and Data Mining, Melbourne, Feb 11-15, 2019. New York: ACM, 2019: 357-365.
[25] DUAN J C, WANG S W, ZHANG P, et al. Graph anomaly detection via multi-scale contrastive learning networks with augmented view[C]//Proceedings of the 37th AAAI Conference on Artificial Intelligence, Washington, Feb 7-14, 2023.Menlo Park: AAAI, 2023: 7459-7467.
[26] MA X X, WU J, XUE S, et al. A comprehensive survey on graph anomaly detection with deep learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(12): 12012-12038.
[27] AKOGLU L, TONG H H, KOUTRA D. Graph based anomaly detection and description: a survey[J]. Data Mining and Knowledge Discovery, 2015, 29(3): 626-688.
[28] GOODGE A, HOOI B, NG S K, et al. LUNAR: unifying local outlier detection methods via graph neural networks[C]// Proceedings of the 2022 AAAI Conference on Artificial Intelligence, Vancouver, Feb 22-Mar 1, 2022. Menlo Park: AAAI, 2022: 6737-6745.
[29] LIU J Y, XIA F, FENG X, et al. Deep graph learning for anomalous citation detection[J]. IEEE Transactions on Neural Networks and Learning Systems, 2022, 33(6): 2543-2557.
[30] DING K Z, SHU K, SHAN X, et al. Cross-domain graph anomaly detection[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 33(6): 2406-2415.
[31] ZHAO T, JIANG T W, SHAH 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.
[32] SU X, XUE S, LIU F Z, et al. A comprehensive survey on community detection with deep learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(4): 4682-4702.
[33] LI J D, DANI H, HU X, et al. Radar: residual analysis for anomaly detection in attributed networks[C]//Proceedings of the 26th International Joint Conference on Artificial Intelligence, Melbourne, Aug 19-25, 2017: 2152-2158.
[34] BANDYOPADHYAY S, LOKESH N, VIVEK S V, et al. Outlier resistant unsupervised deep architectures for attributed network embedding[C]//Proceedings of the 13th International Conference on Web Search and Data Mining, Houston, Feb 3-7, 2020: 25-33.
[35] LI Y N, HUANG X, LI J D, et al. SpecAE: spectral autoencoder for anomaly detection in attributed networks[C]//Proceedings of the 28th ACM International Conference on Information and knowledge Management, Beijing, Nov 3-7, 2019. New York: ACM, 2019: 2233-2236.
[36] WU Z H, PAN S R, CHEN F W, et al. A comprehensive survey on graph neural networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 32(1): 4-24.
[37] TU W X, ZHOU S H, LIU X W, et al. Initializing then refining: a simple graph attribute imputation network[C]//Procee-dings of the 31st International Joint Conference on Artificial Intelligence, Vienna, Jul 23-29, 2022: 3494-3500.
[38] ZHANG Z W, CUI P, ZHU W W. Deep learning on graphs: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(1): 249-270.
[39] SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2008, 20(1): 61-80.
[40] GRATTAROLA D, ZAMBON D, BIANCHI F M, et al. Under-standing pooling in graph neural networks[J]. IEEE Tran-sactions on Neural Networks and Learning Systems, 2024,35(2): 2708-2718.
[41] LIU X, ZHANG F J, HOU Z Y, et al. Self-supervised learning: generative or contrastive[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 35(1): 857-876.
[42] LIU Y, YANG X H, ZHOU S H, et al. Hard sample aware net-work for contrastive deep graph clustering[C]//Proceedings of the 37th AAAI Conference on Artificial Intelligence, Washington, Feb 7-14, 2022. Menlo Park: AAAI, 2022: 8914-8922.
[43] LIU Y X, JIN M, PAN S R, et al. Graph self-supervised learning: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(6): 5879-5900.
[44] WU M, PAN S R, ZHOU C, et al. Unsupervised domain adaptive graph convolutional networks[C]//Proceedings of the Web Conference 2020, Taipei, China, Apr 20-24, 2020: 1457-1467.
[45] HE D X, LIANG C D, HUO C Y, et al. Analyzing heterogeneous networks with missing attributes by unsupervised contrastive learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(4): 4438-4450.
[46] WANG Z H, LI Z, LI X Y, et al. Graph-based contrastive learning for description and detection of local features[J]. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(4): 4839-4851.
[47] QIU J Z, CHEN Q B, DONG Y X, et al. GCC: graph contrastive coding for graph neural network pre-training[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Aug 23-27, 2020. New York: ACM, 2020: 1150-1160.
[48] YOU Y N, CHEN T L, SUI Y D, et al. Graph contrastive learning with augmentations[C]//Advances in Neural Information Processing Systems 33, Vancouver, Dec 6-12, 2020: 5812-5823.
[49] HASSANI K, KHASAHMADI A H. Contrastive multi-view representation learning on graphs[C]//Proceedings of the 2020 International Conference on Machine Learning, Vienna, Jul 13-18, 2020: 4116-4126.
[50] ZHU Y Q, XU Y C, YU F, et al. Graph contrastive learning with adaptive augmentation[C]//Proceedings of the Web Con-ference 2021, Apr 19-23, 2021: 2069-2080.
[51] GRILL J B, STRUB F, ALTCHE F, et al. Bootstrap your own latent a new approach to self-supervised learning[C]//Advances in Neural Information Processing Systems 33, Vancouver, Dec 6-12, 2020: 21271-21284.
[52] ZBONTAR J, JING L, MISRA I, et al. Barlow twins: self-supervised learning via redundancy reduction[C]//Proceedings of the 2021 International Conference on Machine Lear-ning, Vienna, Jul 18-24, 2021: 12310-12320.
[53] BRUNA J, ZAREMBA W, SZLAM A, et al. Spectral networks and deep locally connected networks on graphs[C]//Proceedings of the 2nd International Conference on Learning Representations, Banff, Apr 14-16, 2014.
[54] TANG L, LIU H. Relational learning via latent social dimensions[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, Jun 28-Jul 1, 2001. New York: ACM, 2001: 817-826.
[55] SEN P, NAMATA G, BILGIC M, et al. Collective classification in network data[J]. AI Magazine, 2008, 29(3): 93-106.
[56] TANG J, ZHANG J, YAO L M, et al. ArnetMiner: extraction and mining of academic social networks[C]//Proceedings of the 14th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining, Las Vegas, Aug 24-27, 2008. New York: ACM, 2008: 990-998.
[57] SONG X Y, WU M X, JERMAINE C, et al. Conditional anomaly detection[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(5): 631-645.