Survey of Attribute Graph Anomaly Detection Based on Deep Learning

doi:10.3778/j.issn.1002-8331.2204-0315

Abstract

Abstract: Anomaly detection has always been one of the research hotspots in the field of data mining, and its task is to identify rare observations in massive data. With the development of graph data mining, attribute graph anomaly detection has received wide attention in various areas. However, attribute graphs have become a difficult problem in anomaly detection due to their complex topology and rich attribute information. Deep learning methods have shown superior performance in capturing complex information in attribute graphs, and have been proven to be very effective methods for solving the problem of anomaly detection in attribute graphs. Firstly, a brief overview of common graph anomaly detection, attribute graph anomaly detection and representation learning related methods are given. Secondly, the latest deep learning anomaly detection methods are introduced and classified as static and dynamic attribute graphs. Finally, the application scenarios, existing problems and challenges of attribute graph anomaly detection are discussed, and the future research directions are prospected.

Key words: anomaly detection, attribute graph, graph data mining, deep learning

摘要： 异常检测一直以来都是数据挖掘领域的研究热点之一，其任务是在海量数据中识别罕见的观测对象。随着图数据挖掘的发展，属性图异常检测在各个领域广受关注。然而，属性图因其复杂的拓扑结构和丰富的属性信息成为异常检测一大难点。深度学习方法在捕捉属性图复杂的信息中展现出优越性能，已被证实是解决属性图异常检测问题非常有效的方法。对普通图异常检测和属性图异常检测以及表示学习相关方法进行简要概述；其次从静态属性图和动态属性图两方面对最新深度学习异常检测方法进行介绍与分类；对常见数据集上的实验结果进行了对比、分析；对属性图异常检测的应用场景、存在的问题以及面临的挑战进行讨论，展望了未来的研究方向。

关键词: 异常检测, 属性图, 图数据挖掘, 深度学习

ZHANG Yiyang, QIAN Yurong, TAO Wenbin, LENG Hongyong, LI Zichen, MA Mengnan. Survey of Attribute Graph Anomaly Detection Based on Deep Learning[J]. Computer Engineering and Applications, 2022, 58(19): 1-13.

张伊扬, 钱育蓉, 陶文彬, 冷洪勇, 李自臣, 马梦楠. 基于深度学习的属性图异常检测综述[J]. 计算机工程与应用, 2022, 58(19): 1-13.

References

[1] ZHANG M，CHEN Y.Weisfeiler-Lehman neural machine for link prediction[C]//Proceedings of the 23rd ACM SIGKDD International Conference，2017.
[2] 罗世杰，吕文韬，李凡，等.融合拓扑和属性的动态网络链路预测方法[J].计算机工程与应用：1-10（2021-11-29）[2022-04-18].http：//kns.cnki.net/kcms/detail/11.2127.TP.20211129.
1139.008.html.
LUO S J，LYU W T，LI F，et al.Dynamic network link prediction method for fusion topology and attributes[J/OL].Computer Engineering and Applications：1-10（2021-11-29）[2022-04-18].http：//kns.cnki.net/kcms/detail/11.2127.TP.
20211129.1139.008.html.
[3] EBERLE W，HOLDER L.Anomaly detection in data represented as graphs[J].Intelligent Data Analysis，2007，11（6）：663-689.
[4] 韩涛，兰雨晴，肖利民，等.一种增量并行式动态图异常检测算法[J].北京航空航天大学学报，2018，44（1）：117-124.
HAN T，LAN Y Q，XIAO L M，et al.Incremental and parallel algorithm for anomaly detection in dynamic graphs[J].Journal of Beijing University of Aeronautics and Astronautics，2018，44（1）：117-124
[5] GAO J，LIANG F，FAN W，et al.On community outliers and their efficient detection in information networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2010：813-822.
[6] ABU-EL-HAIJA S，KAPOOR A，PEROZZI B，et al.N-GCN：Multi-scale graph convolution for semi-supervised node classification[J].arXiv：1802.08888，2018.
[7] 吴越，王英，王鑫，等.基于超图卷积的异质网络半监督节点分类[J].计算机学报，2021，44（11）：2248-2260.
WU Y，WANG Y，WANG X，et al.Motif-based hypergraph convolution network for semi-supervisednode classification on heterogeneous graph[J].Chinese Journal of Computers，2021，44（11）：2248-2260.
[8] STANIFORD-CHEN S，CHEUNG S，CRAWFORD R，et al.GrIDS—A graph based intrusion detection system for large networks[C]//Proceedings of the 19th International Information Systems Security Conference，1996：361-370.
[9] AKOGLU L，TONG H，KOUTRA D.Graph based anomaly detection and description：A survey[J].Data Mining and Knowledge Discovery，2015，29（3）：626-688.
[10] AKOGLU L，MCGLOHON M，FALOUTSOS C.Oddball：Spotting anomalies in weighted graphs[C]//Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining，2010：410-421.
[11] BENGIO Y.Learning deep architectures for AI[M].[S.l.]：Now Publishers Inc，2009.
[12] WAIKHOM L，PATGIRI R.Graph neural networks：Methods，applications，and opportunities[J].arXiv：2108. 10733，2021.
[13] CROSBY T.How to detect and handle outliers[J].Technometrics，1994，16：315-316.
[14] CHANDOLA V，BANERJEE A，KUMAR V.Anomaly detection：A survey[J].ACM Computing Surveys，2009，41（3）：1-58.
[15] WANG K，CHEN D.Graph structure based anomaly behavior detection[C]//Proceedings of the 2nd International Conference on Computer Engineering，Information Science & Application Technology，2016：543-550.
[16] JEH G，WIDOM J.Simrank：A measure of structural-context similarity[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2002：538-543.
[17] CHEN H H，GILES C L.ASCOS：An asymmetric network structure context similarity measure[C]//Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining（ASONAM 2013），2013：442-449.
[18] GUGGILAM S，ZAIDI S M A，CHANDOLA V，et al.Integrated clustering and anomaly detection（incad） for streaming data[C]//Proceedings of International Conference on Computational Science，2019：45-59.
[19] ZHU J，WANG H.An improved K-means clustering algorithm[J].Microcomputer Information，2010，10（1）：193-199.
[20] HU R，AGGARWAL C C，MA S，et al.An embedding approach to anomaly detection[C]//Proceedings of IEEE 32nd International Conference on Data Engineering（ICDE），2016：385-396.
[21] HELLING T J，SCHOLTES J C，TAKES F W.A community-aware approach for identifying node anomalies in complex networks[C]//Proceedings of International Conference on Complex Networks and Their Applications，2018：244-255.
[22] PEROZZI B，AKOGLU L.Scalable anomaly ranking of attributed neighborhoods[J].arXiv：1601.06711，2016.
[23] PEROZZI B，AKOGLU L，IGLESIAS SáNCHEZ P，et al.Focused clustering and outlier detection in large attributed graphs[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2014：1346-1355.
[24] SáNCHEZ P I，MüLLER E，LAFORET F，et al.Statistical selection of congruent subspaces for mining attributed graphs[C]//Proceedings of the IEEE 13th International Conference on Data Mining，2013：647-656.
[25] MüLLER E，SáNCHEZ P I，MüLLE Y，et al.Ranking outlier nodes in subspaces of attributed graphs[C]//Proceedings of the IEEE 29th International Conference on Data Engineering Workshops（ICDEW），2013：216-222.
[26] LI J，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，2017.
[27] PENG Z，LUO M，LI J，et al.ANOMALOUS：A joint modeling approach for anomaly detection on attributed networks[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence，2018：3513-3519.
[28] RANSHOUS S，SHEN S，KOUTRA D，et al.Anomaly detection in dynamic networks：A survey[J].Wiley Interdisciplinary Reviews：Computational Statistics，2015，7（3）：223-247.
[29] CHEN F，WANG Y C，WANG B，et al.Graph representation learning：A survey[J].arXiv：1909.00958，2019.
[30] YANG C，LIU Z，ZHAO D，et al.Network representation learning with rich text information[C]//Proceedings of the 24th International Conference on Artificial Intelligence，2015：2111-2117.
[31] XIAO H，LI J，XIA H.Accelerated attributed network embedding[C]//Proceedings of the 2017 SIAM International Conference on Data Mining，2017.
[32] KIPF T N，WELLING M.Semi-supervised classification with graph convolutional networks[J].arXiv：1609.02907，2016.
[33] VELI?KOVI? P，CUCURULL G，Casanova A，et al.Graph attention networks[J].arXiv：1710.10903，2017.
[34] HAMILTON W，YING Z，LESKOVEC J.Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems，2017.
[35] ZHANG Z，YANG H，BU J，et al.ANRL：Attributed network representation learning via deep neural networks[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence，2018：3155-3161.
[36] LI J，DANI H，HU X，et al.Attributed network embedding for learning in a dynamic environment[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management，2017：387-396.
[37] LIU J，HE Z，WEI L，et al.Content to node：Self-translation network embedding[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，2018：1794-1802.
[38] HAO X，ZHANG G，MA S.Deep learning[J].International Journal of Semantic Computing，2016，10（3）：417-439.
[39] LIANG J，JACOBS P，SUN J，et al.Semi-supervised embedding in attributed networks with outliers[C]//Proceedings of the 2018 SIAM International Conference on Data Mining，2018：153-161.
[40] CHEN Z，LIU B，WANG M，et al.Generative adversarial attributed network anomaly detection[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management，2020：1989-1992.
[41] DING K，LI J，AGARWAL N，et al.Inductive anomaly detection on attributed networks[C]//Proceedings of the 29th International Joint Conference on Artificial Intelligence，2020：1288-1294.
[42] BANDYOPADHYAY S，LOKESH N，VIVEK S V，et al.Outlier resistant unsupervised deep architectures for attributed network embedding[C]//Proceedings of the Thirteenth ACM International Conference on Web Search and Data Mining，2020.
[43] DING K，LI J，BHANUSHALI R，et al.Deep anomaly detection on attributed networks[C]//Proceedings of the 2019 SIAM International Conference on Data Mining，2019：594-602.
[44] ZHU D，MA Y，LIU Y.Anomaly detection with deep graph autoencoders on attributed networks[C]//Proceedings of the 2020 IEEE Symposium on Computers and Communications，2020：1-6.
[45] TAUBIN G.A signal processing approach to fair surface design[C]//Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques，1995：351-358.
[46] LUO X，WU J，BEHESHTI A，et al.ComGA：Community-aware attributed graph anomaly detection[C]//Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining，2022：657-665.
[47] PEI Y，HUANG T，IPENBURG W V，et al.ResGCN：Attention-based deep residual modeling for anomaly detection on attributed networks[J].Machine Learning，2021，111（2）：519-541.
[48] FAN H，ZHANG F，LI Z.AnomalyDAE：Dual autoencoder for anomaly detection on attributed networks[C]//Proceedings of the 2020 IEEE International Conference on Acoustics，Speech and Signal Processing，2020.
[49] HUANG L，ZHU Y，GAO Y，et al.Hybrid-order anomaly detection on attributed networks[J].IEEE Transactions on Knowledge and Data Engineering，2021（10）：1.
[50] WANG D，LIN J，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，2019.
[51] CHEN L H，LI H，YANG W.AnomMAN：Detect anomaly on multi-view attributed networks[J].arXiv：2201.02822，2022.
[52] DING K，SHU K，SHAN X，et al.Cross-domain graph anomaly detection[J].IEEE Transactions on Neural Networks and Learning Systems，2022，33：2406-2415.
[53] WANG X，JIN B，DU Y，et al.One-class graph neural networks for anomaly detection in attributed networks[J].Neural Computing and Applications，2021，33（18）：12073-12085.
[54] ZHANG F，FAN H，WANG R，et al.Deep dual support vector data description for anomaly detection on attributed networks[J].International Journal of Intelligent Systems，2022，37（2）：1509-1528.
[55] LIU Y，LI Z，PAN S，et al.Anomaly detection on attributed networks via contrastive self-supervised learning[J].arXiv：2103.00113，2021.
[56] ZHENG Y，JIN M，LIU Y，et al.Generative and contrastive self-supervised learning for graph anomaly detection[J].arXiv：2108.09896，2021.
[57] ZHENG Y，JIN M，LIU Y，et al.From unsupervised to few-shot graph anomaly detection：A multi-scale contrastive learning approach[J].arXiv：2202.05525，2022.
[58] YU W，CHENG W，AGGARWAL C C，et al.Netwalk：A flexible deep embedding approach for anomaly detection in dynamic networks[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，2018：2672-2681.
[59] HOCHREITER S，SCHMIDHUBER J.LSTM can solve hard long time lag problems[C]//Advances in Neural Information Processing Systems，1997：473-479.
[60] YUAN S，ZHENG P，WU X，et al.Wikipedia vandal early detection：from user behavior to user embedding[C]//Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases，2017.
[61] ZHENG P，YUAN S，WU X，et al.One-class adversarial nets for fraud detection[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2019：1286-1293.
[62] CHO K，MERRIENBOER B V，GULCEHRE C，et al.Learning phrase representations using RNN encoder-decoder for statistical machine translation[J].arXiv：1406. 1078，2014.
[63] 郭嘉琰，李荣华，张岩，等.基于图神经网络的动态网络异常检测算法[J].软件学报，2020，31（3）：748-762.
GUO J Y，Li R H，ZHANG Y，et al.Graph neural network based anomaly detection in dynamic networks[J].Journal of Software，2020，31（3）：748-762.
[64] ZHENG L，LI Z，LI J，et al.AddGraph：Anomaly detection in dynamic graph using attention-based temporal GCN[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence，2019.
[65] LI J，HAN Z，CHENG H，et al.Predicting path failure in time-evolving graphs[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，2019：1279-1289.
[66] CAI L，CHEN Z，LUO C，et al.Structural temporal graph neural networks for anomaly detection in dynamic graphs[C]//Proceedings of the 30th ACM International Conference on Information & Knowledge Management，2021：3747-3756.
[67] LIU Y，PAN S，WANG Y G，et al.Anomaly detection in dynamic graphs via transformer[J].arXiv：2106.09876，2021.
[68] 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，2000.
[69] XU X，YURUK N，FENG Z，et al.Scan：A structural clustering algorithm for networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007：824-833.
[70] LI Z，XIONG H，LIU Y，et al.Detecting blackhole and volcano patterns in directed networks[C]//Proceedings of the IEEE 10th International Conference on Data Mining，2010.
[71] LIU Z，CHEN C，YANG X，et al.Heterogeneous graph neural networks for malicious account detection[C]//Proceedings of the 27th ACM International Conference on Information and Knowledge Management，2018：2077-2085.
[72] HU B，ZHANG Z，SHI C，et al.Cash-out user detection based on attributed heterogeneous information network with a hierarchical attention mechanism[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2019：946-953.
[73] FENG S，XING L，GOGAR A，et al.Distributional footprints of deceptive product reviews[C]//Proceedings of the International AAAI Conference on Web and Social Media，2012：98-105.
[74] OTT M，CHOI Y，CARDIE C，et al.Finding deceptive opinion spam by any stretch of the imagination[C]//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics：Human Language Technologies，2011.
[75] AKOGLU L，CHANDY R，FALOUTSOS C.Opinion fraud detection in online reviews by network effects[C]//Proceedings of the International AAAI Conference on Web and Social Media，2013：2-11.
[76] WANG G，XIE S，LIU B，et al.Review graph based online store review spammer detection[C]//Proceedings of the 11th IEEE International Conference on Data Mining，December 11-14，2011.
[77] FAYYAD U M，IRANI K B.Multi-interval discretization of continuous attributes as preprocessing for classification learning[J].Internal Medicine，1995（1）.
[78] FALOUTSOS D H C S P C.Detecting fraudulent personalities in networks of online auctioneers[C]//Proceedings of PKDD 2006，2006：103-114.
[79] PANDIT，SHASHANK，CHAU，et al.Netprobe：A fast and scalable system for fraud detection in online auction networks[C]//Proceedings of the 16th International Conference on World Wide Web，2007.
[80] CORTES C，PREGIBON D，VOLINSKY C.Communities of interest[C]//Proceedings of the International Conference on Advances in Intelligent Data Analysis，2001.
[81] LIU M，LIAO J，WANG J，et al.AGRM：Attention-based graph representation model for telecom fraud detection[C]//Proceedings of the IEEE International Conference on Communications（ICC），2019.
[82] SHU K，WANG S，LIU H.Beyond news content：The role of social context for fake news detection[C]//Proceedings of the 12th International Conference on Web Search and Data Mining，2019.
[83] MISHRA P，DEL TREDICI M，YANNAKOUDAKIS H，et al.Abusive language detection with graph convolutional networks[J].arXiv：1904.04073，2019.
[84] CHANDRA S，MISHRA P，YANNAKOUDAKIS H，et al.Graph-based modeling of online communities for fake news detection[J].arXiv：2008.06274，2020.