Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (6): 118-127.doi: 10.11896/jsjkx.230600168

• Database & Big Data & Data Science • Previous Articles     Next Articles

Study on Anomalous Evolution Pattern on Temporal Networks

WU Nannan1, GUO Zehao1, ZHAO Yiming1, YU Wei2, SUN Ying1,3, WANG Wenjun1   

  1. 1 College of Intelligence and Computing,Tianjin University,Tianjin 300354,China
    2 School of International Business,Zhejiang Yuexiu University,Shaoxing,Zhejiang 312069,China
    3 School of Mining and Coal,Inner Mongolia University of Science and Technology,Baotou,Inner Mongolia 014010,China
  • Received:2023-06-21 Revised:2023-11-27 Online:2024-06-15 Published:2024-06-05
  • About author:WU Nannan,born in 1986,Ph.D,asso-ciate professor,is a senior member of CCF(No.33693S).His main research interests include artificial intelligence and graph anomaly mining.
  • Supported by:
    National Key R & D Program of China(31400),Natural Science Foundation of Inner Mongolia Autonomous Region,China(2022LHMS06008) and National Natural Science Foundation of China(62102262,62272311).

PDF (PC)

505

Abstract: The competitive methods for anomalous subgraphs detection have been successfully applied to tasks like event detection in social networks,traffic congestion detection in road networks,etc.However,few studies have been initiated in the dynamic evolution of anomalous subgraphs in attributed graphs.For multiple anomalous subgraph evolving pattern,it is the first dynamic graph-based study to capture multi-anomalies connected on time intervals.This study proposes an approach,namely dynamic evolution of multiple anomalous subgraphs scanning(DE-MASS),to detect the most anomalous evolutionary pattern,which consists of multiple anomalous subgraphs on attributed graphs.The DE-MASS outperforms the competitive baselines in the Weibo real dataset,computer traffic real dataset,and captures the evolution patterns of anomalous subgraphs on three real-world applications:traffic congestion detection in urban road networks(Beijing,Tianjin,and Nanjing in China),event detection in the social network(Weibo)and cyber-attack detection in computer traffic network.

Key words: Anomaly detection, Subgraph, Dynamic graph, Non-parametric scan statistics

CLC Number: 

  • TP311
[1]DING K,LI J,AGARWAL N,et al.Inductive anomaly detection on attributed networks[C]//Proceedings of the Twenty-ninth International Conference on International Joint Conferences on Artificial Intelligence.2021:1288-1294.
[2]GUTIÉRREZ-GÓMEZ L,BOVET A,DELVENNE J C.Multi-scale anomaly detection on attributed networks[C]//Procee-dings of the AAAI Conference on Artificial Intelligence.2020:678-685.
[3]LI J,WEN J,TAI Z,et al.Bursty event detection from micro-blog:a distributed and incremental approach[J].Concurrency and Computation:Practice and Experience,2016,28(11):3115-3130.
[4]SHAO M,LI J,CHEN F,et al.An efficient approach to event detection and forecasting in dynamic multivariate social media networks[C]//Proceedings of the 26th International Conference on World Wide Web.2017:1631-1639.
[5]SHARPNACK J,SINGH A,RINALDO A.Changepoint detection over graphs with the spectral scan statistic[C]//Artificial Intelligence and Statistics.PMLR,2013:545-553.
[6]WU N,CHEN F,LI J,et al.A Nonparametric Approach to Uncovering Connected Anomalies by Tree Shaped Priors[J].IEEE Transactions on Knowledge and Data Engineering,2019,31(10):1849-1862.
[7]ZHENG L,LI Z,LI J,et al.AddGraph:Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN[C]//IJCAI.2019.
[8]LEE P,LAKSHMANAN L V S,MILIOS E E.Incrementalcluster evolution tracking from highly dynamic network data[C]//2014 IEEE 30th International Conference on Data Engineering.IEEE,2014:3-14.
[9]MONGIOVI M,BOGDANOV P,RANCA R,et al.Netspot:Spotting significant anomalous regions on dynamic networks[C]//Proceedings of the 2013 SIAM International Conference on Data Mining.Society for Industrial and AppliedMathema-tics,2013:28-36.
[10]MONGIOVI M,BOGDANOV P,SINGH A K.Mining evolving network processes[C]//2013 IEEE 13th International Confe-rence on Data Mining.IEEE,2013:537-546.
[11]SRICHARAN K,DAS K.Localizing anomalous changes in time-evolving graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.2014:1347-1358.
[12]GOEL S,BAYKAL A,PON D.Botnets:the anatomy of a case[J].Journal of Information Systems Security,2006,1(3):1-12.
[13]RUEHRUP S,URBANO P,BERGER A,et al.Botnet detection revisited:theory and practice of finding malicious P2P networks via Internet connection graphs[C]//2013 IEEEConference on Computer Communications Workshops(INFOCOM WKSHPS).IEEE,2013:435-440.
[14]YAN Q,ZHENG Y,JIANG T,et al.Peerclean:Unveiling peer-to-peer botnets through dynamic group behavior analysis[C]//2015 IEEE Conference on Computer Communications(INFOCOM).IEEE,2015:316-324.
[15]MYERS S A,ZHU C,LESKOVEC J.Information diffusion and external influence in networks[C]//Proceedings of the 18th ACM SIGKDD International Conference on KnowledgeDisco-very and Data Mining.2012:33-41.
[16]HELBING D,TREIBER M,KESTING A,et al.Theoretical vs.empirical classification and prediction of congested traffic states[J].The European Physical Journal B,2009,69:583-598.
[17]TREIBER M,KESTING A.Calibration and validation of models describing the spatiotemporal evolution of congested traffic patterns[J].arXiv:1008.1639,2010.
[18]KERNER B S,REHBORN H,ALEKSIC M,et al.Recognition and tracking of spatial-temporal congested traffic patterns on freeways[J].Transportation Research Part C:Emerging Technologies,2004,12(5):369-400.
[19]GAO J,ZHOU C,YU J X.Toward continuous pattern detection over evolving large graph with snapshot isolation[J].The VLDB Journal,2016,25:269-290.
[20]FENG C.Non-Parametric Scan Statistics for Event Detectionand Forecasting in Heterogeneous Social Media Graphs[J].Journal of Biological Chemistry,2014,268(28):1166-1175.
[21]MCFOWLAND E,SPEAKMAN S,NEILL D B.Fast genera-lized subset scan for anomalous pattern detection[J].The Journal of Machine Learning Research,2013,14(1):1533-1561.
[22]TAKAHASHI K,KULLDORFF M,TANGO T,et al.A flexibly shaped space-time scan statistic for disease outbreak detection and monitoring[J].International Journal of Health Geographics,2008,7:1-14.
[23]SPEAKMAN S,MCFOWLAND III E,NEILL D B.Scalable detection of anomalous patterns with connectivity constraints[J].Journal of Computational and Graphical Statistics,2015,24(4):1014-1033.
[24]SHAO M,LI J,CHEN F,et al.An efficient framework for detecting evolving anomalous subgraphs in dynamic networks[C]//IEEE INFOCOM 2018－IEEE Conference on Computer Communications.IEEE,2018:2258-2266.
[25]ZHANG Z,ZHAO L.Unsupervised Deep Subgraph AnomalyDetection[C]//2022 IEEE International Conference on Data Mining(ICDM).IEEE,2022:753-762.
[26]BERK R H,JONES D H.Goodness-of-fit test statistics thatdominate the Kolmogorov statistics[J].Zeitschrift Für Wahrscheinlichkeitstheorie Und Verwandte Gebiete,1979,47(1):47-59.
[27]DONOHO D,JIN J.Higher criticism for detecting sparse hete-rogeneous mixtures[J].The Annals of Statistics 2004,32(3):962-994.
[28]BANSAL M,VENKAIAH V.Improved fully polynomial timeapproximation scheme for the 0-1 multiple-choice knapsack problem[J].International Institute of Information Technology Tech Report,2004:1-9.
[29]WU N,CHEN F,LI J,et al.Efficient nonparametric subgraph detection using tree shaped priors[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2016.
[1] WU Huinan, XING Hongjie, LI Gang. Deep Multiple-sphere Support Vector Data Description Based on Variational Autoencoder with Mixture-of-Gaussians Prior [J]. Computer Science, 2024, 51(6): 135-143.
[2] LI Shasha, XING Hongjie. Robust Anomaly Detection Based on Adversarial Samples and AutoEncoder [J]. Computer Science, 2024, 51(5): 363-373.
[3] HAO Meng, TIAN Xueyang, LU Gangzhao, LIU Yi, ZHANG Weizhe, HE Hui. Transplantation and Optimization of Graph Matching Algorithm Based on Domestic DCUHeterogeneous Platform [J]. Computer Science, 2024, 51(4): 67-77.
[4] PAN Lei, LIU Xin, CHEN Junyi, CHENG Zhangtao, LIU Leyuan, ZHOU Fan. Event Prediction Based on Dynamic Graph with Local Data Augmentation [J]. Computer Science, 2024, 51(3): 118-127.
[5] ZHOU Wenhao, HU Hongtao, CHEN Xu, ZHAO Chunhui. Weakly Supervised Video Anomaly Detection Based on Dual Dynamic Memory Network [J]. Computer Science, 2024, 51(1): 243-251.
[6] LI Hui, LI Wengen, GUAN Jihong. Dually Encoded Semi-supervised Anomaly Detection [J]. Computer Science, 2023, 50(7): 53-59.
[7] SHAN Xiaohuan, SONG Rui, LI Haihai, SONG Baoyan. Event Recommendation Method with Multi-factor Feature Fusion in EBSN [J]. Computer Science, 2023, 50(7): 60-65.
[8] JIANG Linpu, CHEN Kejia. Self-supervised Dynamic Graph Representation Learning Approach Based on Contrastive Prediction [J]. Computer Science, 2023, 50(7): 207-212.
[9] HENG Hongjun, ZHOU Wenhua. Anomaly Detection Method Based on Context Information Fusion and Noise Adaptation [J]. Computer Science, 2023, 50(7): 237-245.
[10] SUN Kaiwei, WANG Zhihao, LIU Hu, RAN Xue. Maximum Overlap Single Target Tracking Algorithm Based on Attention Mechanism [J]. Computer Science, 2023, 50(6A): 220400023-5.
[11] ZHANG Guohua, YAN Xuefeng, GUAN Donghai. Anomaly Detection of Time-series Based on Multi-modal Feature Fusion [J]. Computer Science, 2023, 50(6A): 220700094-7.
[12] SUN Xuekui, DAI Hua, ZHOU Jianguo, YANG Geng, CHEN Yanli. LTTFAD:Log Template Topic Feature-based Anomaly Detection [J]. Computer Science, 2023, 50(6): 313-321.
[13] ZHAO Song, FU Hao, WANG Hongxing. Pseudo-abnormal Sample Selection for Video Anomaly Detection [J]. Computer Science, 2023, 50(5): 146-154.
[14] ZHANG Renbin, ZUO Yicong, ZHOU Zelin, WANG Long, CUI Yuhang. Multimodal Generative Adversarial Networks Based Multivariate Time Series Anomaly Detection [J]. Computer Science, 2023, 50(5): 355-362.
[15] RAO Dan, SHI Hongwei. Study on Air Traffic Flow Recognition and Anomaly Detection Based on Deep Clustering [J]. Computer Science, 2023, 50(3): 121-128.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.