Anomaly Detection in Dynamic Graph Using Machine Learning Algorithms

Rabiei, Pouria; Ashrafi-Payaman, Nosratali

doi:10.22044/jadm.2024.14476.2551

Document Type : Original/Review Paper

Authors

Department of Electrical and Computer Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran.

10.22044/jadm.2024.14476.2551

Abstract

Today, the amount of data with graph structure has increased dramatically. Detecting structural anomalies in the graph, such as nodes and edges whose behavior deviates from the expected behavior of the network, is important in real-world applications. Thus, in our research work, we extract the structural characteristics of the dynamic graph by using graph convolutional neural networks, then by using temporal neural network Like GRU, we extract the short-term temporal
characteristics of the dynamic graph and by using the attention mechanism integrated with GRU, long-term temporal dependencies are considered. Finally, by using the neural network classifier, the abnormal edge is detected in each timestamp. Conducted experiments on the two datasets, UC Irvine messages and Digg with three baselines, including Goutlier, Netwalk and CMSketch illustrate our model outperform existing methods in a dynamic graph by 10 and 15% on
average on the UCI and Digg datasets respectively. We also measured the model with AUC and confusion matrix for 1, 5, and 10 percent anomaly injection.

Keywords

Main Subjects

H.3. Artificial Intelligence

References

[1] M. Khazaei, and N. Ashrafi-Payaman. "An Unsupervised Anomaly Detection Model for Weighted Heterogeneous Graph", Journal of AI and Data Mining, vlo. 11, no. 2, pp. 237-245, 2023.

[2] V. Chandola, A. Banerjee, and V. Kumar. "Anomaly detection: A survey", ACM computing surveys (CSUR), vol. 41, no. 3, pp. 1-58, 2009.

[3] V. Yepmo, G. Smits, and O. Pivert. "Anomaly explanation: A review", Data & Knowledge Engineering, vol. 137, p. 101946, 2022.

[4] A. Sgueglia, A. Di Sorbo, C. Aaron Visaggio, and G. Canfora", A systematic literature review of IoT time series anomaly detection solutions." Future Generation Computer Systems, vol. 134, pp. 170-186, 2022.

[5] C. Aggarwal, Y. Zhao, and S. Yu Philip. "Outlier detection in graph streams", In 2011 IEEE 27th international conference on data engineering, 2011, pp. 399-409.

[6] D. Eswaran, C. Faloutsos, S. Guha, and N. Mishra. "Spotlight: Detecting anomalies in streaming graphs", In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 1378-1386.

[7] S. Ranshous, S. Harenberg, K. Sharma, and N. F. Samatova. "A scalable approach for outlier detection in edge streams using sketch-based approximations", In Proceedings of the 2016 SIAM international conference on data mining, Society for Industrial and Applied Mathematics, 2016, pp. 189-197.

[8] E. Manzoor, M. Sadegh Milajerdi, and L. Akoglu. "Fast memory-efficient anomaly detection in streaming heterogeneous graphs", In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, 2016, pp. 1035-1044.

[9] K. Sricharan, and K. Das. "Localizing anomalous changes in time-evolving graphs", In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, 2014, pp. 1347-1358.

[10] W. Yu, W. Cheng, C. Aggarwal, K. Zhang, H. Chen, and W. Wang. "Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks", In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, 2018, pp. 2672-2681.

[11] Y. Liu, S. Pan, Y. Guang Wang, F. Xiong, L.Wang, Q. Chen, and V. Lee. "Anomaly detection in dynamic graphs via transformer", IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 12, pp. 12081-12094, 2021.

[12] L. Zheng, Z. Li, J. Li, Z. Li, and J. Gao. "AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN", In IJCAI, vol. 3, p. 7, 2019.

[13] C. Yang, L. Zhou, H. Wen, Z. Zhou, and Y. Wu. "H-VGRAE: A hierarchical stochastic spatial-temporal embedding method for robust anomaly detection in dynamic networks", arXiv preprint, arXiv:2007.06903, 2020.

[14] L. Cai, Z. Chen, C. Luo, J. Gui, J. Ni, D. Li, and H. Chen. "Structural temporal graph neural networks for anomaly detection in dynamic graphs", In Proceedings of the 30th ACM international conference on Information & Knowledge Management, 2021, pp. 3747-3756.

[15] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun. "Graph neural networks: A review of methods and applications", AI open Journal, vol. 1, pp. 57-81, 2020.

[16] B. Jiandong, J. Zhu, Y. Song, L. Zhao, Z. Hou, R. Du, and H. Li. "A3t-gcn: Attention temporal graph convolutional network for traffic forecasting", ISPRS International Journal of Geo-Information, vol. 10, no. 7, p. 485, 2021.

[17] A. Longa, V. Lachi, G. Santin, M. Bianchini, B. Lepri, P. Lio, F. Scarselli, and A. Passerini. "Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities", arXiv preprint, arXiv:2302.01018, 2023.

[18] Z. Yang, G. Zhang, J. Wu, J. Yang, Q. Sheng, S. Xue, C. Zhou et al. "A Comprehensive Survey of Graph-level Learning", arXiv preprint, arXiv: 2301.05860, 2023.

[19] J. Skarding, B. Gabrys, and K. Musial. "Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey", IEEE Access, vol. 9, no. 3, pp. 79143 - 79168, 2021.

[20] C. Li, Y. Liu, and L. Zou. "DynGCN: A dynamic graph convolutional network based on spatial-temporal modeling", In Web Information Systems Engineering–WISE 2020: 21st International Conference, Amsterdam, The Netherlands, October 20–24, 2020, Proceedings, Part I 21, 2020, pp. 83-95.

[21] W. Hamilton, Z. Ying, and J. Leskovec. "Inductive representation learning on large graphs", Advances in neural information processing systems, vol 30, 2017.

[22] A. Deng, and B. Hooi. "Graph neural network-based anomaly detection in multivariate time series", In Proceedings of the AAAI conference on artificial intelligence, vol. 35, no. 5, pp. 4027-4035, 2021.

[23] R. Morshedi, S. M. Matinkhah, and M. T. Sadeghi, "Intrusion Detection for IoT Network Security with Deep learning", Journal of AI and Data Mining, vol. 12, no. 1, pp. 37-55, 2024.

Anomaly Detection in Dynamic Graph Using Machine Learning Algorithms

References

References

Volume 12, Issue 3July 2024Pages 359-367

Volume 12, Issue 3
July 2024
Pages 359-367