ABSTRACT
Anomaly detection is an area that has received much attention in recent years. It has a wide variety of applications, including fraud detection and network intrusion detection. A good deal of research has been performed in this area, often using strings or attribute-value data as the medium from which anomalies are to be extracted. Little work, however, has focused on anomaly detection in graph-based data. In this paper, we introduce two techniques for graph-based anomaly detection. In addition, we introduce a new method for calculating the regularity of a graph, with applications to anomaly detection. We hypothesize that these methods will prove useful both for finding anomalies, and for determining the likelihood of successful anomaly detection within graph-based data. We provide experimental results using both real-world network intrusion data and artificially-created data.
- Cook, D. J. and Holder, L. B. Graph-Based Data Mining. IEEE Intelligent Systems, 15(2), pages 32--41, 2000. Google ScholarDigital Library
- Lee, W. and Xiang, D. Information-Theoretic Measures for Anomaly Detection. Proceedings of The 2001 IEEE Symposium on Security and Privacy, Oakland, CA, May 2001. Google ScholarDigital Library
- Maxion, R. A. and Tan, K. M. C. Benchmarking Anomaly-Based Detection Systems. International Conference on Dependable Systems and Networks, pages 623--630, New York, New York; 25--28 June 2000. Google ScholarDigital Library
- Miller, G. A. Note on the Bias of Information Estimates. Information Theory in Psychology: Problems and Methods, Free Press, 1955.Google Scholar
- Rissanen, J. Stochastic Complexity in Statistical Inquiry. World Scientific Publishing Company, 1989. Google ScholarDigital Library
- http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.htmlGoogle Scholar
Index Terms
- Graph-based anomaly detection
Recommendations
Two-stage anomaly detection algorithm via dynamic community evolution in temporal graph
AbstractDetecting anomalies from a massive amount of user behavioral data is often liken to finding a needle in a haystack. While tremendous efforts have been devoted to anomaly detection from temporal graphs, existing studies rarely consider community ...
Graph based anomaly detection and description: a survey
Detecting anomalies in data is a vital task, with numerous high-impact applications in areas such as security, finance, health care, and law enforcement. While numerous techniques have been developed in past years for spotting outliers and anomalies in ...
Scalable anomaly detection in graphs
The advantage of graph-based anomaly detection is that the relationships between elements can be analyzed for structural oddities that could represent activities such as fraud, network intrusions, or suspicious associations in a social network. ...
Comments