SpringerLink
Log in

Deep Detection of Anomalies in Static Attributed Graph

  • Conference paper
  • First Online:
Machine Learning, Image Processing, Network Security and Data Sciences (MIND 2020)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 1241))

Abstract

While online social media is one of the greatest innovations of modern man, it often gets used to perform a barrage of malicious activities which can be anomalous in nature. The area of anomaly detection deals with this challenging task. In this paper, we methodically investigate anomaly detection for the modern content driven attributed graphs. Since labeled graph data is not available for scientific research, we work with a synthetically generated dataset with an unsupervised learning approach to prove that both attribute as well as structure should be considered. We also investigate whether deep learning in this context brings an additional advantage in anomaly detection. We extend the recent work in this area, with an innovative combination of attributed graph embedding with graph convolution technique.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (Canada)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (Canada)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (Canada)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Savage, D., Zhang, X., **nghuo, Y., Chou, P., Wang, Q.: Anomaly detection in online social networks. Soc. Netw. 39, 62–70 (2014)

    Article  Google Scholar 

  2. Rose, Y., Qiu, H., Wen, Z., Lin, C.Y., Liu, Y.: A survey on social media anomaly detection. ACM SIGKDD Explor. Newsl. 18(1), 1–14 (2016)

    Article  Google Scholar 

  3. Abraham, B., Box, G.E.P.: Bayesian analysis of some outlier problems in time series. Biometrika 66(2), 229–236 (1979)

    Article  MathSciNet  Google Scholar 

  4. Kruegel, C., Mutz, D., Robertson, W., Valeur, F.: Bayesian event classification for intrusion detection. In: Proceedings 19th Annual Computer Security Applications Conference, pp. 14–23. IEEE (2003)

    Google Scholar 

  5. Ma, J., Perkins, S.: Time-series novelty detection using one-class support vector machines. In: Proceedings of the International Joint Conference on Neural Networks, vol. 3, pp. 1741–1745. IEEE (2003)

    Google Scholar 

  6. Ma, J., Perkins, S.: Online novelty detection on temporal sequences. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 613–618 (2003)

    Google Scholar 

  7. Li, K.L., Huang, H.K., Tian, S.F., Xu, W.: Improving one-class SVM for anomaly detection. In: Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No. 03EX693), vol. 5, pp. 3077–3081. IEEE (2003)

    Google Scholar 

  8. Perdisci, R., Ariu, D., Fogla, P., Giacinto, G., Lee, W.: McPAD: a multiple classifier system for accurate payload-based anomaly detection. Comput. Netw. 53(6), 864–881 (2009)

    Article  Google Scholar 

  9. Moradi, M., Zulkernine, M.: A neural network based system for intrusion detection and classification of attacks. In: Proceedings of the IEEE International Conference on Advances in Intelligent Systems-Theory and Applications, pp. 15–18 (2004)

    Google Scholar 

  10. Augusteijn, M.F., Folkert, B.A.: Neural network classification and novelty detection. Int. J. Remote Sens. 23(14), 2891–2902 (2002)

    Article  Google Scholar 

  11. Pires, A., Santos-Pereira, C.: Using clustering and robust estimators to detect outliers in multivariate data (2005)

    Google Scholar 

  12. Eskin, F., Portnoy, L., Stolfo, S.: Intrusion detection with unlabeled data using clustering. In: Proceedings of ACM CSS Workshop on Data Mining Applied to Security (2001)

    Google Scholar 

  13. Beutel, A., Xu, W., Guruswami, V., Palow, C., Faloutsos, C.: Copycatch: stop** group attacks by spotting lockstep behavior in social networks. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 119–130 (2013)

    Google Scholar 

  14. Liu, F.T., Ting, K.M., Zhou, Z.H.: Isolation forest. In: 2008 Eighth IEEE International Conference on Data Mining, pp. 413–422. IEEE (2008)

    Google Scholar 

  15. Puggini, L., McLoone, S.: An enhanced variable selection and isolation forest based methodology for anomaly detection with oes data. Eng. Appl. Artif. Intell. 67, 126–135 (2018)

    Article  Google Scholar 

  16. Sun, L., Versteeg, S., Boztas, S., Rao, A.: Detecting anomalous user behavior using an extended isolation forest algorithm: an enterprise case study. ar**v preprint ar**v:1609.06676 (2016)

  17. Susto, G.A., Beghi, A., McLoone, S.: Anomaly detection through on-line isolation forest: an application to plasma etching. In: 2017 28th Annual SEMI Advanced Semiconductor Manufacturing Conference (ASMC), pp. 89–94. IEEE (2017)

    Google Scholar 

  18. Xu, D., Wang, Y., Meng, Y., Zhang, Z.: An improved data anomaly detection method based on isolation forest. In: 2017 10th International Symposium on Computational Intelligence and Design (ISCID), vol. 2, pp. 287–291. IEEE (2017)

    Google Scholar 

  19. An, J., Cho, S.: Variational autoencoder based anomaly detection using reconstruction probability. Spec. Lect. IE 2(1), 1–18 (2015)

    Google Scholar 

  20. **ao, C., Freeman, D.M., Hwa, T.: Detecting clusters of fake accounts in online social networks. In: Proceedings of the 8th ACM Workshop on Artificial Intelligence and Security, pp. 91–101 (2015)

    Google Scholar 

  21. Zheng, X., Zeng, Z., Chen, Z., Yuanlong, Y., Rong, C.: Detecting spammers on social networks. Neurocomputing 159, 27–34 (2015)

    Article  Google Scholar 

  22. Viswanath, B., et al.: Towards detecting anomalous user behavior in online social networks. In: 23rd \(\{\)USENIX\(\}\) Security Symposium (\(\{\)USENIX\(\}\) Security 14), pp. 223–238 (2014)

    Google Scholar 

  23. Hassanzadeh, R., Nayak, R., Stebila, D.: Analyzing the effectiveness of graph metrics for anomaly detection in online social networks. In: Wang, X.S., Cruz, I., Delis, A., Huang, G. (eds.) WISE 2012. LNCS, vol. 7651, pp. 624–630. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35063-4_45

    Chapter  Google Scholar 

  24. Kaur, R., Kaur, M., Singh, S.: A novel graph centrality based approach to analyze anomalous nodes with negative behavior. Procedia Comput. Sci. 78, 556–562 (2016)

    Article  Google Scholar 

  25. Akoglu, L., McGlohon, M., Faloutsos, C.: Oddball: spotting anomalies in weighted graphs. In: Zaki, M.J., Yu, J.X., Ravindran, B., Pudi, V. (eds.) PAKDD 2010. LNCS (LNAI), vol. 6119, pp. 410–421. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13672-6_40

    Chapter  Google Scholar 

  26. Huang, J., Sun, H., Han, J., Deng, H., Sun, Y., Liu, Y.: Shrink: a structural clustering algorithm for detecting hierarchical communities in networks. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management, pp. 219–228 (2010)

    Google Scholar 

  27. Doostari, M.A., Zeinali, R., Lashkari, H., Ajamzamani, M.: Fuzzy node-fuzzy graph (2013)

    Google Scholar 

  28. Chen, Z., Hendrix, W., Samatova, N.F.: Community-based anomaly detection in evolutionary networks. J. Intell. Inf. Syst. 39(1), 59–85 (2012). https://doi.org/10.1007/s10844-011-0183-2

    Article  Google Scholar 

  29. Ying, X., Wu, X., Barbará, D.: Spectrum based fraud detection in social networks. In: 2011 IEEE 27th International Conference on Data Engineering, pp. 912–923. IEEE (2011)

    Google Scholar 

  30. Hamilton, W.L., Ying, R., Leskovec, J.: Representation learning on graphs: methods and applications. ar**v preprint ar**v:1709.05584 (2017)

  31. Cai, H., Zheng, V.W., Chang, K.C.C.: A comprehensive survey of graph embedding: problems, techniques, and applications. IEEE Trans. Knowl. Data Eng. 30(9), 1616–1637 (2018)

    Article  Google Scholar 

  32. Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701–710 (2014)

    Google Scholar 

  33. Grover, A., Leskovec, J.: node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 855–864 (2016)

    Google Scholar 

  34. Wang, D., Cui, P., Zhu, W.: Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1225–1234 (2016)

    Google Scholar 

  35. Cao, S., Lu, W., Xu, Q.: Deep neural networks for learning graph representations. In: Thirtieth AAAI Conference on Artificial Intelligence (2016)

    Google Scholar 

  36. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. ar**v preprint ar**v:1609.02907 (2016)

  37. Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, pp. 1024–1034 (2017)

    Google Scholar 

  38. Zheng, L., Li, Z., Li, J., Li, Z., Gao, J.: Addgraph: anomaly detection in dynamic graph using attention-based temporal GCN. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 4419–4425. AAAI Press (2019)

    Google Scholar 

  39. Ding, K., Li, J., Bhanushali, R., Liu, H.: Deep anomaly detection on attributed networks. In: Proceedings of the 2019 SIAM International Conference on Data Mining, pp. 594–602. SIAM (2019)

    Google Scholar 

  40. Huang, X., Li, J., Hu, X.: Accelerated attributed network embedding. In: Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 633–641. SIAM (2017)

    Google Scholar 

  41. Klimt, B., Yang, Y.: The enron corpus: a new dataset for email classification research. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) ECML 2004. LNCS (LNAI), vol. 3201, pp. 217–226. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30115-8_22

    Chapter  Google Scholar 

  42. Vengertsev, D., Thakkar, H.: Anomaly detection in graph: unsupervised learning, graph-based features and deep architecture (2015)

    Google Scholar 

  43. Largeron, C., Mougel, P.N., Rabbany, R., Zaïane, O.R.: Generating attributed networks with communities. PloS one, 10(4), 54–62 (2015)

    Google Scholar 

  44. Leskovec, J., Adamic, L.A., Huberman, B.A.: The dynamics of viral marketing. ACM Trans. Web (TWEB) 1(1), 5 (2007)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. PES University, Bengaluru, India

    Prakhyat G. Kulkarni, S. Y. Praneet, R. B. Raghav & Bhaskarjyoti Das

Authors
  1. Prakhyat G. Kulkarni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Y. Praneet
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. B. Raghav
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Bhaskarjyoti Das
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Prakhyat G. Kulkarni or R. B. Raghav .

Editor information

Editors and Affiliations

  1. National Institute of Technology Silchar, Silchar, India

    Arup Bhattacharjee

  2. National Institute Of Technology Silchar, Silchar, India

    Samir Kr. Borgohain

  3. National Institute of Technology Silchar, Silchar, India

    Badal Soni

  4. National Institute of Technology Kurukshetra, Kurukshetra, India

    Gyanendra Verma

  5. University of Eastern Finland, Kuopio, Finland

    **ao-Zhi Gao

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kulkarni, P.G., Praneet, S.Y., Raghav, R.B., Das, B. (2020). Deep Detection of Anomalies in Static Attributed Graph. In: Bhattacharjee, A., Borgohain, S., Soni, B., Verma, G., Gao, XZ. (eds) Machine Learning, Image Processing, Network Security and Data Sciences. MIND 2020. Communications in Computer and Information Science, vol 1241. Springer, Singapore. https://doi.org/10.1007/978-981-15-6318-8_50

Download citation

  • DOI: https://doi.org/10.1007/978-981-15-6318-8_50

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-15-6317-1

  • Online ISBN: 978-981-15-6318-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation