Angle-based Graph Neural Network Method for Anomaly Detection in High Dimensional Data

doi:10.19678/j.issn.1000-3428.0067948

Abstract

Abstract:

In high-dimensional data spaces, most data are located at the edges of the high-dimensional space and distributed sparsely, resulting in the problem of "curse of dimensionality", which makes existing anomaly detection methods unable to ensure the accuracy of anomaly detection. To address this problem, an Angle-based Graph Neural Network(A-GNN) high-dimensional data anomaly detection method is proposed. First, the data used for training are expanded by uniformly sampling the data space and perturbing the initial training data. Second, the k-nearest neighbor relationship is used to construct a k-nearest neighbor relationship graph of the training data, and the variance of the k-nearest neighbor element distance weighted angle is used as the initial anomaly factor for the nodes in the k-nearest neighbor relationship graph. Finally, by training a GNN model, information exchange between nodes is achieved, enabling adjacent nodes to learn from each other and effectively evaluate anomalies. The A-GNN method is experimentally compared with nine typical anomaly detection methods on six natural datasets. The results demonstrate that A-GNN achieved the highest Area Under the Curve(AUC) value in five datasets, which can significantly improve the anomaly detection accuracy of various dimensions of data. On some true high-dimensional data, the AUC of anomaly detection increased by more than 40%. Compared with three k-nearest neighbor-based anomaly detection methods at different k values, A-GNN can effectively avoid the impact of k values on detection results by utilizing information exchange between GNN nodes, and the method has stronger robustness.

Key words: anomaly detection, angle-based anomaly assessment, Graph Neural Network(GNN), high-dimensional data, k-nearest neighbor

摘要：

在高维数据空间中，数据大都处于高维空间边缘且分布十分稀疏，由此引起的“维度灾难”问题导致现有异常检测方法无法保证异常检测精度。为解决该问题，提出一种基于角度的图神经网络高维数据异常检测方法A-GNN。首先通过数据空间的均匀采样和初始训练数据的扰动来扩充用于训练的数据；然后利用k近邻关系构造训练数据的k近邻关系图，并以k近邻元素距离加权角度的方差作为近邻关系图节点的初始异常因子；最后通过训练图神经网络模型，实现节点间的信息交互，使得相邻节点能够互相学习，从而进行有效的异常评估。在6个自然数据集上将A-GNN方法与9种典型异常检测方法进行实验对比，结果表明：A-GNN在5个数据集中取得了最高的AUC值，其能够大幅提升各种维度数据的异常检测精度，在一些“真高维数据”上异常检测的AUC值提升达40%以上；在不同k值下与3种基于k近邻的异常检测方法相比，A-GNN利用图神经网络节点间的信息交互能有效避免k值对检测结果的影响，方法具有更强的鲁棒性。

关键词: 异常检测, 基于角度的异常评估, 图神经网络, 高维数据, k近邻

Jun WANG, Huixia LAI, Yue WAN, Shi ZHANG. Angle-based Graph Neural Network Method for Anomaly Detection in High Dimensional Data[J]. Computer Engineering, 2024, 50(3): 156-165.

王俊, 赖会霞, 万玥, 张仕. 基于角度的图神经网络高维数据异常检测方法[J]. 计算机工程, 2024, 50(3): 156-165.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0067948

https://www.ecice06.com/EN/Y2024/V50/I3/156

Figures/Tables 15

Fig.1 Procedure of A-GNN model

Fig.2 Schematic diagram of information transmission

Fig.3 Schematic diagram of information aggregation between nodes

Fig.4 The cumulative information and dimensional relationship of PCA results of six datasets

References 36

1	CAO B K, MAO M A, VIIDU S, et al. Collective fraud detection capturing inter-transaction dependency[EB/OL]. [2023-05-05]. http://proceedings.mlr.press/v71/cao18a/cao18a.pdf.
2	TAO J R, LIN J S, ZHANG S Z, et al. MVAN: multi-view attention networks for real money trading detection in online games[C]// Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York, USA: ACM Press, 2019: 2536-2546.
3	BHATIA S, HOOI B, YOON M, et al. Midas: microcluster-based detector of anomalies in edge streams. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(4): 3242- 3249. doi: 10.1609/aaai.v34i04.5724
4	FAN H Y, ZHANG F B, LI Z Y. Anomalydae: dual autoencoder for anomaly detection on attributed networks[C]//Proceedings of 2020 IEEE International Conference on Acoustics, Speech and Signal Processing. Washington D. C., USA: IEEE Press, 2020: 5685-5689.
5	LI Z, ZHAO Y, FU J L. SynC: a copula based framework for generating synthetic data from aggregated sources[C]//Proceedings of International Conference on Data Mining Workshops. Washington D. C., USA: IEEE Press, 2020: 571-578.
6	FERNANDO T, DENMAN S, AHMEDT-ARISTIZABAL D, et al. Neural memory plasticity for medical anomaly detection. Neural Networks, 2020, 127, 67- 81. doi: 10.1016/j.neunet.2020.04.011
7	VERLEYSEN M, FRANÇOIS D. The curse of dimensionality in data mining and time series prediction[EB/OL]. [2023-05-05]. https://link.springer.com/chapter/10.1007/11494669_93.
8	RAMASWAMY S, RASTOGI R, SHIM K. Efficient algorithms for mining outliers from large data sets[C]//Proceedings of 2000 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2000: 427-438.
9	BREUNIG M M, KRIEGEL H P, NG R T, et al. LOF: identifying density-based local outliers[C]//Proceedings of 2000 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2000: 93-104.
10	ESTER M, KRIEGEL H, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[EB/OL]. [2023-05-05]. https://cdn.aaai.org/KDD/1996/KDD96-037.pdf.
11	LIU F T, TING K M, ZHOU Z H. Isolation forest[C]//Proceedings of the 8th IEEE International Conference on Data Mining. Washington D. C., USA: IEEE Press, 2008: 413-422.
12	SCHÖLKOPF B, WILLIAMSON R, SMOLA A, et al. Support vector method for novelty detection[EB/OL]. [2023-05-05]. https://dl.acm.org/doi/10.5555/3009657.3009740.
13	CHEN J H, SATHE S, AGGARWAL C, et al. Outlier detection with autoencoder ensembles[EB/OL]. [2023-05-05]. https://epubs.siam.org/doi/pdf/10.1137/1.9781611974973.11.
14	AN J, CHO S. Variational autoencoder based anomaly detection using reconstruction probability. Special Lecture on IE, 2015, 2(1): 1- 18.
15	RUFF L, VANDERMEULEN R, GOERNITZ N, et al. Deep one-class classification[EB/OL]. [2023-05-05]. https://ml.cs.uni-kl.de/publications/2018/deep-svdd.pdf.
16	LIU Y, LI Z, ZHOU C, et al. Generative adversarial active learning for unsupervised outlier detection. IEEE Transactions on Knowledge and Data Engineering, 2019, 32(8): 1517- 1528.
17	GOODGE A, HOOI B, NG S K, et al. LUNAR: unifying local outlier detection methods via graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 2022, 36(6): 6737- 6745. doi: 10.1609/aaai.v36i6.20629
18	PANG G S, SHEN C H, CAO L B, et al. Deep learning for anomaly detection: a review. ACM Computing Surveys, 2021, 54(2): 38.
19	KRIEGEL H P, SCHUBERT M, ZIMEK A. Angle-based outlier detection in high-dimensional data[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2008: 444-452.
20	SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model. IEEE Transactions on Neural Networks, 2009, 20(1): 61- 80. doi: 10.1109/TNN.2008.2005605
21	GOLDSTEIN M, DENGEL A. Histogram-Based Outlier Score (HBOS): a fast unsupervised anomaly detection algorithm[EB/OL]. [2023-05-05]. https://www.researchgate.net/publication/231614824_Histogram-based_Outlier_Score_HBOS_A_fast_Unsupervised_Anomaly_Detection_Algorithm.
22	LI Z, ZHAO Y, BOTTA N, et al. COPOD: copula-based outlier detection[C]//Proceedings of IEEE International Conference on Data Mining. Washington D. C., USA: IEEE Press, 2020: 1118-1123.
23	TANG J, CHEN Z X, FU A W C, et al. Enhancing effectiveness of outlier detections for low density patterns[EB/OL]. [2023-05-05]. https://link.springer.com/chapter/10.1007/3-540-47887-6_53.
24	BANDARAGODA T R, TING K M, ALBRECHT D, et al. Isolation-based anomaly detection using nearest-neighbor ensembles. Computational Intelligence, 2018, 34(4): 968- 998. doi: 10.1111/coin.12156
25	SHYU M, CHEN S, SARINNAPAKORN K, et al. A novel anomaly detection scheme based on principal component classifier[EB/OL]. [2023-05-05]. https://www.researchgate.net/publication/228709094_A_Novel_Anomaly_Detection_Scheme_Based_on_Principal_Component_Classifier.
26	张仕, 赖会霞, 肖如良, 等. 开放环境多分布特性的局部敏感哈希检索方法. 软件学报, 2022, 33(4): 1200- 1217. URL
	ZHANG S, LAI H X, XIAO R L, et al. Open environmental locality-sensitive hashing retrieval for multiple distributed characteristics. Journal of Software, 2022, 33(4): 1200- 1217. URL
27	PHAM N, PAGH R. A near-linear time approximation algorithm for angle-based outlier detection in high-dimensional data[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2012: 877-885.
28	余立苹, 李云飞, 朱世行. 基于高维数据流的异常检测算法. 计算机工程, 2018, 44(1): 51- 55. URL
	YU L P, LI Y F, ZHU S X. Anomaly detection algorithm based on high-dimensional data stream. Computer Engineering, 2018, 44(1): 51- 55. URL
29	ZOU H, HASTIE T, TIBSHIRANI R. Sparse principal component analysis. Journal of Computational and Graphical Statistics, 2006, 15(2): 265- 286. doi: 10.1198/106186006X113430
30	PEVNÝ T. Loda: lightweight on-line detector of anomalies. Machine Learning, 2016, 102(2): 275- 304. doi: 10.1007/s10994-015-5521-0
31	KRIZHEVSKY A, SUTSKEVER I, HINTON G E. ImageNet classification with deep convolutional neural networks. Communications of the ACM, 2017, 60(6): 84- 90. doi: 10.1145/3065386
32	SIMONYAN K, ZISSERMAN A. Very deep convolutional networks for large-scale image recognition[EB/OL]. [2023-05-05]. https://arxiv.org/abs/1409.1556.
33	HE K M, ZHANG X Y, REN S Q, et al. Deep residual learning for image recognition[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Washington D. C., USA: IEEE Press, 2016: 770-778.
34	ZONG B, SONG Q, MIN M R, et al. Deep autoencoding Gaussian mixture model for unsupervised anomaly detection[EB/OL]. [2023-05-05]. https://sites.cs.ucsb.edu/~bzong/doc/iclr18-dagmm.pdf.
35	DENG A L, HOOI B. Graph neural network-based anomaly detection in multivariate time series. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35(5): 4027- 4035. doi: 10.1609/aaai.v35i5.16523
36	SIPPLE J. Interpretable, multidimensional, multimodal anomaly detection with negative sampling for detection of device failure[C]//Proceedings of the 37th International Conference on Machine Learning. New York, USA: ACM Press, 2020: 9016-9025.

[1]	LI Zelin, LÜ Zhaofeng, CHEN Fuqiang, LI Ke. Entity Alignment Model Based on Multi-Hop Information Fusion [J]. Computer Engineering, 2024, 50(9): 142-152.
[2]	Xingyu HE, Yixin ZHOU, Dongxu LUO, Guisong YANG. Education Resource Recommendation Based on Graph Neural Network and Multi-Subject Rating [J]. Computer Engineering, 2024, 50(7): 13-22.
[3]	Xuanyu ZHOU, Lianhua WU, Qinhua ZHENG, Tianxing XIAO, Zixuan WANG, Simin ZHANG. Weakly Supervised Video Anomaly Detection Method for Rope Skipping Combined with Semantic Prompts and Memory Enhancement [J]. Computer Engineering, 2024, 50(7): 87-95.
[4]	LI Yongfei, LI Mingyang, CHANG Xin, CAO Kexin. Anomaly Detection of IoT Water Quality Monitoring Data Based on Explainable Deep Learning [J]. Computer Engineering, 2024, 50(6): 179-187.
[5]	SUN Wenjie, LI Zongmin, SUN Haomiao. Multi-Agent Reinforcement Learning Value Function Factorization Approach Based on Graph Neural Network [J]. Computer Engineering, 2024, 50(5): 62-70.
[6]	YOU Ben, LI Xiaohong, YAO Jin, FENG Shaojie. Semi-supervised Classification for Short Text Based on Multi-grained Graphs and Attention Mechanism [J]. Computer Engineering, 2024, 50(5): 83-90.
[7]	ZHANG Baoxin, YANG Dan, NIE Tiezheng, KOU Yue. Recommendation Method Based on Self-supervised Multi-view Graph Collaborative Filtering [J]. Computer Engineering, 2024, 50(5): 100-110.
[8]	Bohan WANG, Xiaoyan JIANG, Liuyi FAN. Semantic Segmentation Improvement Method Based on Deep Supervision for the Construction of Latent Space [J]. Computer Engineering, 2024, 50(3): 191-199.
[9]	Bochao ZHAO, Jiajun MA, Lei CUI, Wenpeng LUAN, Jing ZHU. Anomaly Detection for Photovoltaic Based on Improved VMD-XGBoost-BiLSTM Combination Model [J]. Computer Engineering, 2024, 50(3): 306-316.
[10]	GU Yuheng, PAN Jiacheng, QIAN Jiangbo, DONG Yihong. Research Progress on Graph Neural Network Classification Methods for Alzheimer's Disease [J]. Computer Engineering, 2024, 50(10): 35-50.
[11]	Zhiqiang WU, Qing XIE, Lin LI, Yongjian LIU. Graph Neural Network Recommendation Algorithm Based on Multimodal Fusion [J]. Computer Engineering, 2024, 50(1): 91-100.
[12]	Jiajing GU, Dan YANG, Tiezheng NIE, Yue KOU. Recommendation Algorithm Based on Multi-view Fusion Cross-layer Contrastive Learning [J]. Computer Engineering, 2024, 50(1): 120-128.
[13]	Xiaoli LIU, Yitong WANG. Multi-density Graph-based Session Recommendation Using Self-supervised Learning [J]. Computer Engineering, 2023, 49(9): 60-68, 78.
[14]	CHEN Zhonglei, YI Peng, CHEN Xiang, HU Tao. Real-time Anomaly Detection Framework via System Calls Based on Integrated Learning [J]. Computer Engineering, 2023, 49(6): 162-169,179.
[15]	WANG Ailing, MA Wenzhen, ZOU Ziming, ZHONG Jia. Anomaly Detection of Satellite Engineering Parameters Based on Domain Adaptation [J]. Computer Engineering, 2023, 49(5): 29-37,47.

Please choose a citation manager

Content to export