Graph based anomaly detection and description: a survey

By Leman Akoglu, Hanghang Tong, Danai Koutra. Data mining and knowledge discovery, 2014

1,621 citations recorded by the source corpus.

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 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 give a general framework for the algorithms categorized under various settings: unsupervised versus (semi-)supervised approaches, for static versus dynamic graphs, for attributed versus plain graphs. We highlight the effectiveness, scalability, generality, and robustness aspects of the methods. What is more, we stress the importance of anomaly 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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/ae74522002f9093fbf63a20efb57d80ee2f4f564

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Robust Graph Representation Learning via Neural Sparsification (2020, background): “…in the center of many machine learning tasks on graphs, such as name disambigua-1 tion in citation networks (Zhang et al., 2018), spam detection in social networks (Akoglu et al., 2015), recommendations in online marketing (Ying et al., 2018), and many others (Yu et al., 2018; Li et al., 2018).”
Graph convolutional networks: a comprehensive review (2019, background): “Graphs naturally arise in many real-world applications, including social analysis [1], fraud detection [2, 3], traffic prediction [4], computer vision [5], and many more.”
UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats (2020, methodology): “Akoglu et al. determine graph or subgraph similarity for anomaly detection by catego-rizing graphs based on their properties (i.e., static vs. dynamic , plain vs. attributed ) [8].”
NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks (2018, methodology): “Anomaly detection (a.k.a outlier detection) in dynamically changing networks is a long-standing problem deeply motivated in a number of application domains, such as social media, security, public health, and computational biology [1, 5, 7, 16, 33].”
Artificial intelligence based anomaly detection of energy consumption in buildings: A review, current trends and new perspectives (2021, background): “For instance, the authors in [161, 162], consider the house, power generator, electric network, rooms, and appliances as nodes; and edges stand for the existing connection between a specific room and the operation of an appliance.”
A Survey of Learning Causality with Data: Problems and Methods (2018, background): “Although anomaly detection has been well studied in machine learning and data mining [1, 2, 24], detection of instances that are irregular in causal effects and relationships is still an open problem.”
Local Modeling of Attributed Graphs: Algorithms and Applications (2016, background): “Graph anomaly detection [4] is a problem of pressing concern, with broad applications including network security, spam/fraud detection (in social networks, financial networks, etc.”
Towards Federated Graph Learning for Collaborative Financial Crimes Detection (2019, background): “The paper in [Akoglu et al., 2015] provides a good review of prior art about graph-based approaches for general anomaly detection problems.”
Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters (2020, background): “Graphbased methods connect entities with different relations and reveal the suspiciousness of these entities at the graph level, since fraudsters with the same goal tend to connect with each other [1].”
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, methodology): “As for graph anomaly detection, Akoglu et al. [25], Ran-shous et al. [48], and Jennifer and Kumar [49] put their concentration on graph anomaly detection, reviewing many conventional approaches in this area, including statistical models and machine learning techniques.”
Radar: Residual Analysis for Anomaly Detection in Attributed Networks (2017, methodology): “Anomaly detection methods in attributed networks can be grouped into: 1) Structure-based methods 2) Communitybased methods [Akoglu et al., 2014].”
Entity Embedding-Based Anomaly Detection for Heterogeneous Categorical Events (2016, methodology): “There is some work on applying graph mining methods for anomaly detection in graph [Tong et al. , 2008; Akoglu et al. , 2014].”
REV2: Fraudulent User Prediction in Rating Platforms (2018, background): “A survey on network-based fraud detection can be found in [3].”
A Survey on Network Embedding (2017, methodology): “Anomaly detection has been widely investigated in previous work [67].”
A Survey on Anomaly Detection for Technical Systems using LSTM Networks (2021, background): “Applying contextual anomaly detection can contribute to a better anomaly detection by emphasizing or discarding a certain anomaly, thereby reducing false positives or by finding the root cause for a certain anomaly with the help of meta data, also referred to as anomaly attribution [15,16,17].”