Graph-based Anomaly Detection and Description: A Survey

Abstract

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 unstructured collections of multi-dimensional points, with graph data becoming ubiquitous, techniques for structured {\em graph} data have been of focus recently. As objects in graphs have long-range correlations, a suite of novel technology has been developed for anomaly detection in graph data. This survey aims to provide a general, comprehensive, and structured overview of the state-of-the-art methods for anomaly detection in data represented as graphs. As a key contribution, we provide a comprehensive exploration of both data mining and machine learning algorithms for these {\em detection} tasks. we give a general framework for the algorithms categorized under various settings: unsupervised vs. (semi-)supervised approaches, for static vs. dynamic graphs, for attributed vs. plain graphs. We highlight the effectiveness, scalability, generality, and robustness aspects of the methods. What is more, we stress the importance of anomaly {\em attribution} and highlight the major techniques that facilitate digging out the root cause, or the `why', of the detected anomalies for further analysis and sense-making. Finally, we present several real-world applications of graph-based anomaly detection in diverse domains, including financial, auction, computer traffic, and social networks. We conclude our survey with a discussion on open theoretical and practical challenges in the field.

Survey on Graph-Based Anomaly Detection. Algorithms and Applications. Static Graphs. Dynamic Graphs. Graph Anomaly Description. 49 pages (without citations)

References in corpus (6)

• Modularity and community structure in networks
• A Comprehensive Survey of Data Mining-based Fraud Detection Research
• DELTACON: A Principled Massive-Graph Similarity Function
• Empirical Comparison of Algorithms for Network Community Detection
• Simrank++: Query rewriting through link analysis of the click graph
• Estimating the Prevalence of Deception in Online Review Communities

Cited by in corpus (15)

• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• Alleviating Structural Distribution Shift in Graph Anomaly Detection
• Statistically-Robust Clustering Techniques for Mapping Spatial Hotspots: A Survey
• LTE4G: Long-Tail Experts for Graph Neural Networks
• Improving Generalizability of Graph Anomaly Detection Models via Data Augmentation
• Multi-scale Anomaly Detection on Attributed Networks
• Anomaly Detection in Partially Observed Traffic Networks
• Action Sequence Augmentation for Early Graph-based Anomaly Detection
• GraphZero: Breaking Symmetry for Efficient Graph Mining
• A General Framework for Estimating Graphlet Statistics via Random Walk
• Node-Differentially Private Estimation of the Number of Connected Components
• Temporal graph-based approach for behavioural entity classification
• Community-Level Anomaly Detection for Anti-Money Laundering
• Multi-representations Space Separation based Graph-level Anomaly-aware Detection
• Coverage-based Outlier Explanation