Anomaly-Aware Variational Graph Autoencoder Based Graph-Level Anomaly Detection Algorithm

Lin Fu; Li Mingkang; Luo Xuexiong; Zhang Shuhao; Zhang Yue; Wang Zitong

doi:10.7544/issn1000-1239.202440177

Journal of Computer Research and Development > 2024 > 61(8): 1968-1981. > DOI: 10.7544/issn1000-1239.202440177 CSTR: 32373.14.issn1000-1239.202440177

Lin Fu, Li Mingkang, Luo Xuexiong, Zhang Shuhao, Zhang Yue, Wang Zitong. Anomaly-Aware Variational Graph Autoencoder Based Graph-Level Anomaly Detection Algorithm[J]. Journal of Computer Research and Development, 2024, 61(8): 1968-1981. DOI: 10.7544/issn1000-1239.202440177

Citation:

PDF (1872 KB)

Anomaly-Aware Variational Graph Autoencoder Based Graph-Level Anomaly Detection Algorithm

1.
School of Computer Science, Wuhan University, Wuhan 430072
2.
School of Computing, Macquarie University, Sydney, Australia 2122
3.
School of Cyber Science and Engineering, Wuhan University, Wuhan 430072

More Information

Author Bio:
Lin Fu: born in 1978. PhD, associate professor. His main research interests include graph neural network, data mining, and machine learning

Li Mingkang: born in 2001. Master candidate. His main research interests include graph neural network and machine learning

Luo Xuexiong: born in 1995. PhD candidate. His main research interests include graph neural network, graph anomaly detection, and brain graph analysis

Zhang Shuhao: born in 2003. Undergraduate. His main research interests include knowledge graph and machine learning

Zhang Yue: born in 2000. Master candidate. His main research interests include graph model and machine learning

Wang Zitong: born in 2001. Master candidate. His main research interests include knowledge graph and intelligent computing
Received Date: March 14, 2024
Revised Date: May 14, 2024
Available Online: July 04, 2024

Graphical Abstract

Abstract

Abstract

Graph anomaly detection plays a crucial role in identifying abnormal patterns within complex data structures, and finds applications in various domains such as malicious molecule identification, financial fraud detection, and social network analysis. While existing research in graph anomaly detection predominantly focuses on node-level anomaly detection, there is a scarcity of methods specifically designed for graph-level anomaly detection. Moreover, these methods often fail to adequately explore anomalous graph data, are sensitive to anomaly labels, struggle to capture features of anomalous samples effectively, exhibit poor model generalization, and suffer from performance reversal issues. There is a need for improvement in anomaly detection capabilities. we propose an anomaly-aware variational graph autoencoder based graph-level anomaly detection algorithm (VGAE-D), which utilizes an anomaly-aware variational graph autoencoder to simultaneously extract features from normal and anomalous graph data. This algorithm distinguishes the encoding information of normal and anomalous graphs in the encoding space, further exploring the graph encoding information to compute anomaly scores. Experimental evaluations on eight publicly available datasets from diverse domains demonstrate the effectiveness of the proposed graph-level anomaly detection algorithm. The results indicate that VGAE-D can efficiently identify anomalous graphs in different datasets, outperforming mainstream graph-level anomaly detection methods. Additionally, the algorithm exhibits a capability for learning from few anomalous samples, mitigating the issue of performance inversion to a large extent.

FullText(HTML)

References (47)

References

[1]	Jiang Qiangrong, Ma Jiajia. A novel graph kernel on chemical compound classification[J]. Journal of Bioinformatics and Computational Biology, 2018, 16(6): 1850026 doi: 10.1142/S0219720018500269
[2]	Newman M E J, Watts D J, Strogatz S H. Random graph models of social networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(suppl_1): 2566−2572.
[3]	陈波冯,李靖东,卢兴见,等. 基于深度学习的图异常检测综述[J]. 计算机研究与发展,2021,58(7):1436−1455 doi: 10.7544/issn1000-1239.2021.20200685 Chen Bofeng, Li Jingdong, Lu Xingjian, et al. Survey of deep learning based graph anomaly detection methods[J]. Journal of Computer Research and Development, 2021, 58(7): 1436−1455 (in Chinese) doi: 10.7544/issn1000-1239.2021.20200685
[4]	Jiang Jiangguo, Chen Jiuming, Gu Tianbo, et al. Anomaly detection with graph convolutional networks for insider threat and fraud detection[C]//Proc of IEEE Military Communications Conf. Piscataway, NJ: IEEE, 2019: 109−114
[5]	Pourhabibi T, Ong K L, Kam B, et al. Fraud detection: A systematic literature review of graph-based anomaly detection approaches[J]. Decision Support Systems, 2020, 133: 1−15
[6]	Zhang Ge, Wu Jia, Yang Jian, et al. Fraudre: Fraud detection dual-resistant to graph inconsistency and imbalance[C]//Proc of IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2021: 867−876
[7]	Zhao Tong, Jiang Tianwen, 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
[8]	Liu Yixin, Li Zhao, Pan Shirui, 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
[9]	Zhao Lingxiao, Akoglu L. On using classification datasets to evaluate graph outlier detection: Peculiar bservations and new insights[J]. Big Data, 2023, 11(3): 151−180 doi: 10.1089/big.2021.0069
[10]	Qiu Chen, Kloft M, Mandt S, et al. Raising the bar in graph-level anomaly detection[C]//Proc of Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2022: 2196−2203
[11]	Ma Rongrong, Pang Guangsong, Chen Lingpang, et al. Deep graph-level anomaly detection by glocal knowledge distillation[C]//Proc of the 15th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2022: 704−714
[12]	Liu Yixin, Ding Kaize, Liu Huan, et al. GOOD-D: On unsupervised graph out-of-distribution detection[C]//Proc of the 16th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2023: 339−347
[13]	Pan Shirui, Hu Ruiqi, Long Guodong, et al. Adversarially regularized graph autoencoder for graph embedding[C]//Proc of Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2018: 2609−2615
[14]	Kipf T N, Welling M. Variational graph auto-encoders[J]. Stat, 2016, 1050: 21
[15]	Reiser P, Neubert M, Eberhard A, et al. Graph neural networks for materials science and chemistry[J]. Communications Materials, 2022, 3(1): 1−18 doi: 10.1038/s43246-022-00315-6
[16]	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
[17]	Micheli A. Neural network for graphs: A contextual constructive approach[J]. IEEE Transactions on Neural Networks, 2009, 20(3): 498−511 doi: 10.1109/TNN.2008.2010350
[18]	Chen Ming, Wei Zhewei, Huang Zengfeng, et al. Simple and deep graph convolutional networks[C]//Proc of Int Conf on Machine Learning. New York: ACM, 2020: 1725−1735
[19]	Gao Hongyang, Wang Zhengyang, Ji Shuiwang. Large-scale learnable graph convolutional networks[C]//Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2018: 1416−1424
[20]	Wu Fe, Souza A, Zhang Tianyi, et al. Simplifying graph convolutional networks[C]//International Conference on Machine Learning. New York : ACM, 2019: 6861−6871.
[21]	Xu K, Hu Weihua, Leskovec J, et al. How powerful are graph neural networks?[C]//Proc of Int Conf on Learning Representations. https://doi.org/10.48550/arXiv.1810.00826
[22]	Fan Shaohua, Wang Xiao, Shi Chuan, et al. One2multi graph autoencoder for multi-view graph clustering[C]// Proc of The Web Conf. New York: ACM, 2020: 3070−3076
[23]	Hou Zhenyu, Liu Xiao, Cen Yukuo, et al. Graphmae: Self-supervised masked graph autoencoders[C]//Proc of the 28th ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2022: 594−604
[24]	Velickovic P, Cucurull G, Casanova A, et al. Graph attention networks[J]. Stat, 2018, 1050: 4
[25]	Wang Xiao, Ji Houye, Shi Chuan, et al. Heterogeneous graph attention network[C]//Proc of the World Wide Web Conf. New York: ACM, 2019: 2022−2032
[26]	Ji Ziwei, Lee N, Frieske R, et al. Survey of hallucination in natural language generation[J]. ACM Computing Surveys, 2023, 55(12): 1−38
[27]	Chakrabarti D. Autopart: Parameter-free graph partitioning and outlier detection[C]//Proc of European Conf on Principles of Data Mining and Knowledge Discovery. Berlin: Springer, 2004: 112−124
[28]	Kuang Da, Ding C, Park H. Symmetric nonnegative matrix factorization for graph clustering[C]//Proc of the 2012 SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2012: 106−117
[29]	Nikulin V, Huang T H. Unsupervised dimensionality reduction via gradient-based matrix factorization with two adaptive learning rates[C]//Proc of ICML Workshop on Unsupervised and Transfer Learning. New York: ACM, 2012: 181−194
[30]	Nguyen H T, Liang P J, Akoglu L. Anomaly detection in large labeled multi-graph databases[J]. arXiv preprint, arXiv: 2010.03600, 2020
[31]	Shervashidze N, Schweitzer P, Van Leeuwen E J, et al. Weisfeiler-Lehman graph kernels[J]. Journal of Machine Learning Research, 2011, 12(9): 2539−2561
[32]	Neumann M, Garnett R, Bauckhage C, et al. Propagation kernels: Efficient graph kernels from propagated information[J]. Machine Learning, 2016, 102: 209−245 doi: 10.1007/s10994-015-5517-9
[33]	Scherer P, Lio P. Learning distributed representations of graphs with Geo2DR[J]. arXiv preprint, arXiv: 2003.05926, 2020
[34]	Liu F T, Ting Kaiming, Zhou Zhihua. Isolation forest[C]// Proc of Int Confon Data Mining. Piscataway, NJ: IEEE, 2008: 413−422
[35]	Breunig M M, Kriegel H P, Ng R T, et al. LOF: Identifying density-based local outliers[C]//Proc of the 2000 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2000: 93−104
[36]	Schölkopf B, Williamson R C, Smola A, et al. Support vector method for novelty detection[J]. Advances in Neural Information Processing Systems, 1999, 12: 583−588
[37]	Eswaran D, Faloutsos C, Guha S, et al. Spotlight: Detecting anomalies in streaming graphs[C]//Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2018: 1378−1386
[38]	Zheng Li, Li Zhenpeng, Li Jianli, et al. AddGraph: Anomaly detection in dynamic graph using attention-based temporal GCN[C]//Proc of Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2019: 3−7
[39]	Manzoor E, Milajerdi S M, Akoglu L. Fast memory-efficient anomaly detection in streaming heterogeneous graphs[C]//Proc of the 22nd ACM SIGKDD International Conf on Knowledge Discovery and Data Mining. New York: ACM, 2016: 1035−1044
[40]	Yu Wenchao, Cheng Wei, Aggarwal C C, et al. Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks[C]//Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2018: 2672−2681
[41]	Zhao Lingxiao, Sawlani S, Srinivasan A, et al. Graph anomaly detection with unsupervised GNNs[J]. arXiv preprint, arXiv: 2210.09535, 2022
[42]	Luo Xuexiong, Wu Jia, Yang Jian, et al. Deep graph level anomaly detection with contrastive learning[J]. Scientific Reports, 2022, 12(1): 19867 doi: 10.1038/s41598-022-22086-3
[43]	Lin Fu, Luo Xuexiong, Wu Jia, et al. Discriminative graph-level anomaly detection via dual-students-teacher model[C]//Proc of Int Conf on Advanced Data Mining and Applications. Berlin: Springer, 2023: 261−276
[44]	Haefely W. Tranquilizers[J]. psychopharmacolosy, 1983, 2: 92-182.
[45]	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 doi: 10.1021/ci034143r
[46]	Zhang Zheng, Deng Xiaogang. Anomaly detection using improved DeepSVDD model with data structure preservation[J]. Pattern Recognition Letters, 2021, 148: 1−6 doi: 10.1016/j.patrec.2021.04.020
[47]	Van der Maaten L, Hinton G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9(11): 2579−2605

[1]	Lai Baoqiang, Li Zheng, Zhao Ruilian, Guo Junxia. Context-Aware Based API Recommendation with Diversity[J]. Journal of Computer Research and Development, 2023, 60(10): 2335-2347. DOI: 10.7544/issn1000-1239.202220317
[2]	Tang Dan, Cai Hongliang, Geng Wei. Decoding Method of Reed-Solomon Erasure Codes[J]. Journal of Computer Research and Development, 2022, 59(3): 582-596. DOI: 10.7544/issn1000-1239.20210575
[3]	Zhang Bing, Wen Zheng, Wei Xiaoyu, Ren Jiadong. InterDroid: An Interpretable Android Malware Detection Method for Conceptual Drift[J]. Journal of Computer Research and Development, 2021, 58(11): 2456-2474. DOI: 10.7544/issn1000-1239.2021.20210560
[4]	Yang Wang, Gao Mingzhe, Jiang Ting. A Malicious Code Static Detection Framework Based on Multi-Feature Ensemble Learning[J]. Journal of Computer Research and Development, 2021, 58(5): 1021-1034. DOI: 10.7544/issn1000-1239.2021.20200912
[5]	Guo Jinyang, Shao Chuanming, Wang Jing, Li Chao, Zhu Haojin, Guo Minyi. Programming and Developing Environment for FPGA Graph Processing: Survey and Exploration[J]. Journal of Computer Research and Development, 2020, 57(6): 1164-1178. DOI: 10.7544/issn1000-1239.2020.20200106
[6]	Zheng Zhen, Zhai Jidong, Li Yan, Chen Wenguang. Workload Analysis for Typical GPU Programs Using CUPTI Interface[J]. Journal of Computer Research and Development, 2016, 53(6): 1249-1262. DOI: 10.7544/issn1000-1239.2016.20148354
[7]	Jiao Sibei, Ying Lingyun, Yang Yi, Cheng Yao, Su Purui, and Feng Dengguo. An Anti-Obfuscation Method for Detecting Similarity Among Android Applications in Large Scale[J]. Journal of Computer Research and Development, 2014, 51(7): 1446-1457.
[8]	Dong Longming, Wang Ji, Chen Liqian, Dong Wei. Memory Leak Detection for Heap-Manipulating Programs Based on Local Heap Abstraction[J]. Journal of Computer Research and Development, 2012, 49(9): 1832-1842.
[9]	Ma Peijun, Wang Tiantian, and Su Xiaohong. Automatic Grading of Student Programs Based on Program Understanding[J]. Journal of Computer Research and Development, 2009, 46(7): 1136-1142.
[10]	Wang Zhaofei and Huang Chun. Static Detection of Deadlocks in OpenMP Fortran Programs[J]. Journal of Computer Research and Development, 2007, 44(3).