Graph Neural Network Based Anomaly Detection in Dynamic Networks
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61772346, U1809206, 61532001, 61332006, 61332014, 61328202, U1401256); China MOE and China Mobile Joint Research Foundation (MCM20170503)

  • Article
  • | |
  • Metrics
  • |
  • Reference [42]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    Dynamic graph structured data is ubiquitous in real-life applications. Mining outliers on dynamic networks is an important problem, which is very useful for many practical applications. Most traditional network outlier detection algorithms focus mainly on the strutraulal anomaly, ignoring the nodes and edges' attributes, and the time-varying features as well. This study proposes a graph neural network based network anomaly detection algorithm which can capture the nodes and edges' attributes and time-varying features and fully uses these features to learn a representation vector for each node. Specifically, the proposed algorithm improves an unsupervised graph neural network framework called DGI. Based on DGI, a new danamic DGI algorithm is proposed, which is called Dynamic-DGI, for dynamic networks. Dynamic-DGI can simultaneously extracts the abnormal characteristics of the network itself and the abnormal characteristics of the network changes. The experimental results show that the proposed algorithm is better than the state-of-the-art anomaly detection algorithm SpotLight, and is significantly better than the traditional network representation learning algorithms. In addition to improving the accuracy, the proposed algorithmis also able to mine interesting anomalies in the network.

    Reference
    [1] Carley KM. Dynamic Network Analysis. CMU, 2003.
    [2] Eswaran D, Faloutsos C. Sedanspot:Detecting anomalies in edge streams. In:Proc. of the Int'l Conf. on Data Mining (ICDM). 2018. 953-958.
    [3] Gupta M, Gao J, Sun Y, et al. Integrating community matching and outlier detection for mining evolutionary community outliers. In:Proc. of the 9th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2012. 859-867.
    [4] Heard NA, Weston DJ, Platanioti K, et al. Bayesian anomaly detection methods for social networks. The Annals of Applied Statistics, 2010,4(2):645-662.
    [5] Noble CC, Cook DJ. Graph-based anomaly detection. In:Proc. of the 9th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2013. 631-636.
    [6] Ranshous S, Shen S, Koutra D, et al. Anomaly detection in dynamic networks:A survey. Wiley Interdisciplinary Reviews:Computational Statistics, 2015,7(3):223-247.
    [7] Savage D, Zhang X, Yu X, et al. Anomaly detection in online social networks. Social Networks, 2014,39:62-70.
    [8] Akoglu L, Tong H, Koutra D. Graph based anomaly detection and description:A survey. Data Mining and Knowledge Discovery, 2015,29(3):626-688.
    [9] Perozzi B, Al-Rfou R, Skiena S. Deepwalk:Online learning of social representations. In:Proc. of the 20th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2014. 701-710.
    [10] Guha S, Mishra N, Roy G, et al. Robust random cut forest based anomaly detection on streams. In:Proc. of the Int'l Conf. on Machine Learning (ICML). 2016. 2712-2721.
    [11] Bronstein MM, Bruna J, Lecun Y, et al. Geometric deep learning:Going beyond euclidean data. IEEE Signal Processing Magazine, 2017,34(4):18-42.
    [12] Monti F, Boscaini D, Masci J, et al. Geometric deep learning on graphs and manifolds using mixture model cnns. In:Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). 2017. 5115-5124.
    [13] Zhou J, Cui G, Zhang Z, et al. Graph neural networks:A review of methods and applications. arXiv preprint arXiv:1812.08434, 2018.
    [14] Hochreiter S, Schmidhuber JU. Long short-term memory. Neural Computation, 1997,9(8):1735-1780.
    [15] Aggarwal CC, Zhao Y, Philip SY. Outlier detection in graph streams. In:Proc. of the 27th Int'l Conf. on Data Engineering (ICDE). 2011. 399-409.
    [16] Ranshous S, Harenberg S, Sharma K, et al. A scalable approach for outlier detection in edge streams using sketch-based approximations. In:Proc. of the 2016 SIAM Int'l Conf. on Data Mining (SDM). 2016. 189-197.
    [17] Manzoor E, Milajerdi SM, Akoglu L. Fast memory-efficient anomaly detection in streaming heterogeneous graphs. In:Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2016. 1035-1044.
    [18] Eswaran D, Faloutsos C, Guha S, et al. Spotlight:Detecting anomalies in streaming graphs. In:Proc. of the 24th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2018. 1378-1386.
    [19] Yu W, Cheng W, Aggarwal CC, et al. Netwalk:A flexible deep embedding approach for anomaly detection in dynamic networks. In:Proc. of the 24th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2018. 2672-2681.
    [20] Huyan K, Fan X, Yu LT, Luo ZX. Graph based neural network regression strategy for facial image superresolution. Ruan Jian Xue Bao/Journal of Software, 2018,29(4):914-925(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5405.htm[doi:10.13328/j.cnki.jos.005405]
    [21] Qu Q, Yu HT, Huang RY. Graph convolutional network based social network Spammer detection technology. Chinese Journal of Network and Information Security, 2018,30(5):43-50(in Chinese with English abstract).
    [22] Ning SQ, Guo MZ, Ren SJ. A semi-supervised method for cancer clinical outcome prediction based on graph convolution network. Intelligent Computer and Applications, 2018,8(6):44-48(in Chinese with English abstract).
    [23] Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering. In:Proc. of the Advances in Neural Information Processing Systems (NIPS). 2016. 3844-3852.
    [24] Henaff M, Bruna J, Lecun Y. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.05163, 2015.
    [25] Kipf TN, Welling M. Semi-Supervised classification with graph convolutional networks. In:Proc. of the Int'l Conf. on Learning Representations (ICLR). 2017.
    [26] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks. In:Proc. of the Int'l Conf. on Learning Representations (ICLR). 2018.
    [27] Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs. In:Proc. of the Advances in Neural Information Processing Systems (NIPS). 2017. 1024-1034.
    [28] Hjelm RD, Fedorov A, Lavoie-Marchildon S, et al. Learning deep representations by mutual information estimation and maximization. In:Proc. of the Int'l Conf. on Learning Representations (ICLR). 2018.
    [29] Veličković P, Fedus W, Hamilton WL, et al. Deep graph infomax. In:Proc. of the Int'l Conf. on Learning Representations (ICLR). 2018.
    [30] Weber M, Domeniconi G, Chen J, et al. Anti-Money laundering in bitcoin:Experimenting with graph convolutional networks for financial forensics. In:Proc. of the 25th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD), Workshop on Anomaly Detection in Finance. 2019.
    [31] Xu K, Li C, Tian Y, et al. Representation learning on graphs with jumping knowledge networks. In:Proc. of the Int'l Conf. on Machine Learning (ICML). 2018.
    [32] Sharafaldin I, Lashkari AH, Ghorbani AA. Toward generating a new intrusion detection dataset and intrusion traffic characterization. In:Proc. of the 4th Int'l Conf. on Information Systems Security and Privacy (ICISSP). 2018.
    [33] Akoglu L, Faloutsos C. Anomaly, event, and fraud detection in large network datasets. In:Proc. of the 6th ACM Int'l Conf. on Web Search and Data Mining (WSDM). 2013. 773-774.
    [34] Kumar S, Hamilton WL, Leskovec J, et al. Community interaction and conflict on the Web. In:Proc. of the 2018 World Wide Web Conf. on World Wide Web (WWW). 2018. 933-943.
    [35] SNAP Datasets:Stanford Large Network Dataset Collection. Stanford University, 2014.
    [36] Grover A, Leskovec J. node2vec:Scalable feature learning for networks. In:Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2016. 855-864.
    [37] Wang D, Cui P, Zhu W. Structural deep network embedding. In:Proc. of the 22nd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD). 2016. 1225-1234.
    [38] Laurens VDM, Geoffrey H. Visualizing data using t-SNE. Journal of Machine Learning Research, 2008,9(11):2579-2605.
    附中文参考文献:
    [20] 呼延康,樊鑫,余乐天,罗钟铉.图神经网络回归的人脸超分辨率重建.软件学报,2018,29(4):914-925. http://www.jos.org.cn/1000-9825/5405.htm[doi:10.13328/j.cnki.jos.005405]
    [21] 曲强,于洪涛,黄瑞阳.基于图卷积网络的社交网络Spammer检测技术.网络与信息安全学报,2018,30(5):43-50.
    [22] 宁世琦,郭茂祖,任世军.基于图卷积网络的癌症临床结果预测的半监督学习方法.智能计算机与应用,2018,8(6):44-48.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

郭嘉琰,李荣华,张岩,王国仁.基于图神经网络的动态网络异常检测算法.软件学报,2020,31(3):748-762

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 19,2019
  • Revised:November 25,2019
  • Online: January 10,2020
  • Published: March 06,2020
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063