Leman Akoglu
Christos Faloutsos
ABSTRACT
Detecting anomalies and events in data is a vital task, with numerous applications in security, finance, health care, law enforcement, and many others. While many techniques have been developed in past years for spotting outliers and anomalies in unstructured collections of multi-dimensional points, with graph data becoming ubiquitous, techniques for structured graph data have been of focus recently. As objects in graphs have long-range correlations, novel technology has been developed for abnormality detection in graph data.
The goal of this tutorial is to provide a general, comprehensive overview of the state-of-the-art methods for anomaly, event, and fraud detection in data represented as graphs. As a key contribution, we provide a thorough exploration of both data mining and machine learning algorithms for these detection tasks. We give a general framework for the algorithms, categorized under various settings: unsupervised vs.(semi-)supervised, for static vs. dynamic data. We focus on the scalability and effectiveness aspects of the methods, and highlight results on crucial real-world applications, including accounting fraud and opinion spam detection.
- L. Akoglu, R. Chandy, and C. Faloutsos. Opinion fraud detection in review networks. In Technical Report CMU-CS-12-130, 2012.Google Scholar
- L. Akoglu and C. Faloutsos. Event detection in time series of mobile communication graphs. In Army Science Conference, 2010.Google Scholar
- L. Akoglu, M. McGlohon, and C. Faloutsos. OddBall: Spotting anomalies in weighted graphs. In PAKDD, 2010. Google ScholarDigital Library
- W. Eberle and L. B. Holder. Anomaly detection in data represented as graphs. Intell. Data Anal., 11(6):663--689, 2007. Google ScholarCross Ref
- L. Getoor, N. Friedman, D. Koller, A. Pfeffer, and B. Taskar. Probabilistic relational models. In Intro. to Stat. Relational Learning. MIT Press, 2007.Google ScholarCross Ref
- Z. Gyogyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with TrustRank. In Proc. VLDB, 2004. Google ScholarDigital Library
- M. McGlohon, S. Bay, M. G. Anderle, D. M. Steier, and C. Faloutsos. Snare: a link analytic system for graph labeling and risk detection. In KDD, pages 1265--1274, 2009. Google ScholarDigital Library
- C. C. Noble and D. J. Cook. Graph-based anomaly detection. In KDD, pages 631--636, 2003. Google ScholarDigital Library
- S. Pandit, D. H. Chau, S. Wang, and C. Faloutsos. Netprobe: a fast and scalable system for fraud detection in online auction networks. In WWW, 2007. Google ScholarDigital Library
- B. Pincombe. Anomaly detection in time series of graphs using arma processes. ASOR Bulletin., 24(4):2--10, 2005.Google Scholar
- P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93--106, 2008.Google ScholarDigital Library
- J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu. Graphscope: parameter-free mining of large time-evolving graphs. In KDD, pages 687--696, 2007. Google ScholarDigital Library
- J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. Neighborhood formation and anomaly detection in bipartite graphs. In ICDM, pages 418--425, 2005. Google ScholarDigital Library
- B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In UAI, pages 485--492, 2002. Google ScholarDigital Library
Index Terms
- Anomaly, event, and fraud detection in large network datasets
Recommendations
Graph-based anomaly detection
KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data miningAnomaly 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 ...
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