Source-linked AI summary
Graph Anomaly Detection with Graph Neural Networks: Current Status and Challenges
Hwan Kim, Byung Suk Lee, Won-Yong Shin, Sungsu Lim
TL;DR
Graph anomaly detection seeks to identify attribute or structural patterns that depart from normal graph behavior, but GNN-based methods lack a comprehensive synthesis. This survey reviews GNN approaches across graph types, anomaly types, and architectures, and highlights open challenges including explainability, class imbalance, heterogeneous graphs, and few-shot settings.
Problem
Graph anomaly detection is important for complex-system analysis, yet GNN-based methods had not received a comprehensive review organized across graph, anomaly, and architecture types.
Method
The survey categorizes and reviews GNN-based graph anomaly detection methods by static or dynamic graph type, anomaly type, and network architecture.
Results
The survey covers methods for node, edge, subgraph, and whole-graph anomalies across static and dynamic graphs, while finding that research is concentrated on static-graph node anomalies.
Takeaways & Limitations
The surveyed field is expanding beyond static node anomalies toward dynamic graphs and edge, subgraph, and graph-level anomalies.
Abstract
from arXiv · showhide
Graphs are used widely to model complex systems, and detecting anomalies in a graph is an important task in the analysis of complex systems. Graph anomalies are patterns in a graph that do not conform to normal patterns expected of the attributes and/or structures of the graph. In recent years, graph neural networks (GNNs) have been studied extensively and have successfully performed difficult machine learning tasks in node classification, link prediction, and graph classification thanks to the highly expressive capability via message passing in effectively learning graph representations. To solve the graph anomaly detection problem, GNN-based methods leverage information about the graph attributes (or features) and/or structures to learn to score anomalies appropriately. In this survey, we review the recent advances made in detecting graph anomalies using GNN models. Specifically, we summarize GNN-based methods according to the graph type (i.e., static and dynamic), the anomaly type (i.e., node, edge, subgraph, and whole graph), and the network architecture (e.g., graph autoencoder, graph convolutional network). To the best of our knowledge, this survey is the first comprehensive review of graph anomaly detection methods based on GNNs.
I. INTRODUCTION
Graphs represent complex systems through interconnected nodes and edges, optionally enriched with attributes, making graph anomaly detection important for identifying deviations from expected patterns. This survey reviews GNN-based approaches across graph types, anomaly types, and architectures.
- Graphs model complex systems through node relationships and can combine structural information with node or edge attributes.
- Graph anomaly detection identifies patterns that significantly deviate from typically observed patterns in graph attributes or structure.
- Early graph anomaly detection relied on handcrafted features and statistical methods, which are time-consuming for large, high-dimensional real-world graphs.
- GNNs use expressive message passing to learn graph representations and extract anomalous patterns from graphs with complex structures or attributes.
- The survey organizes GNN-based graph anomaly detection primarily by static versus dynamic graphs and discusses broad graph and anomaly-type coverage.
II. GNN FRAMEWORKS
GNNs learn graph representations by iteratively aggregating neighborhood information and updating node embeddings. Common architectures differ in how they sample neighbors, weight messages, or model graph geometry.
- GNN message passing aggregates information from a node’s h-hop neighbors to produce graph representations.
- At each layer, differentiable AGGREGATE and UPDATE functions combine neighborhood messages with node embeddings, while final-layer outputs provide learned representations.
- GCN combines network structure and node attributes, GraphSAGE samples neighbors for large graphs, and GAT learns neighbor weights during message passing.
- Alternative architectures address efficiency and geometric flexibility, including GSNN and GIL, which jointly uses Euclidean and hyperbolic spaces.
III. GNN-BASED GRAPH ANOMALY DETECTION
The survey classifies GNN-based graph anomaly detection methods by graph type, anomaly type, and network architecture. Static node-anomaly research dominates, while methods span autoencoders, GCNs, self-supervised learning, and other architectures.
- The survey taxonomy organizes methods by static or dynamic graphs, node, edge, subgraph, or whole-graph anomalies, and network architecture.
- 1) Anomalous Node Detection:: Most static-graph research addresses node anomalies, while edge and subgraph anomaly studies remain comparatively limited.
- 1) Anomalous Node Detection:: Static attributed-node methods combine attribute and structural information before assigning anomaly scores, with GAE approaches commonly using GCN encoders and reconstruction-based scoring.
- 1) Anomalous Node Detection:: Representative node methods address over-smoothing, high-dimensional interactions, higher-order structure, multi-view attributes, and contextual node- or subgraph-level information.
- 1) Anomalous Node Detection:: The field includes unsupervised, semi-supervised, and self-supervised GCN methods that use graph structure, attributes, hyperspherical embeddings, hop counts, or contrastive node-subgraph modeling.
2) Anomalous Edge Detection:
Static anomalous-edge detection targets atypical interactions and remains relatively limited. Existing methods score edges through anomaly-aware embedding losses or detect fraud using sampled neighborhoods and subgraph representations.
- Static anomalous-edge detection research is relatively limited, focusing on interactions that differ from typical relationships between nodes.
- AANE combines GCN-based graph autoencoding with fitting, deviation, and removal losses, assigning lower-probability edges higher anomaly likelihood.
- SubGNN extracts and relabels subgraphs near target edges, then uses an R-GIN to learn features for fraud detection.
- eFraudCom samples representative normal data and graph neighbors before using a CGNN-based detector to identify anomalous e-commerce edges.
3) Anomalous Subgraph Detection:
Anomalous subgraph detection is especially difficult because individually normal nodes and edges can form anomalous subgraphs with diverse structures and sizes. Existing work includes HO-GAT, which jointly detects anomalous nodes and subgraphs using structural, attribute, and motif information.
- Anomalous subgraphs are harder to detect because their constituent nodes and edges may appear normal individually, while subgraphs vary in structure and size.
- HO-GAT jointly detects anomalous nodes and subgraphs from structural and attribute information.It uses motifs to represent densely connected higher-order substructures and models node–motif relations with graph attention.
4) Graph-level Anomaly Detection:
Graph-level anomaly detection seeks graphs that differ markedly from most graphs in a collection, but remains relatively underexplored. GNN-based approaches include one-class GIN, transformation learning, and global–local knowledge distillation.
- Graph-level anomaly detection identifies graphs that are notably different from most graphs in a set, yet remains a limited-study task.
- OCGIN applies a one-class deep SVDD objective to graph embeddings produced by a Graph Isomorphism Network.GIN generalizes the Weisfeiler–Lehman test and provides strong graph classification capability among GNNs.
- OCGTL combines deep one-class classification with self-supervised anomaly detection and learnable transformations to address hypersphere collapse.
- GLocalKD uses stacked GCN modules and knowledge distillation to learn graph- and node-level normality for detecting local or global anomalous subgraphs.
B. GNN-based Dynamic Graph Anomaly Detection
Dynamic graph anomaly detection must account for graph structures or attributes that change over time. Existing methods combine GCNs with temporal models, while prior work has focused on node and edge anomalies rather than anomalous subgraphs.
- Dynamic graph anomaly detection addresses graphs whose structures or attributes evolve over time.
- Methods for dynamic graphs combine GCNs with RNNs, GRUs, or transformers to process temporal information.
- Prior dynamic-graph studies address node or edge anomalies, with no reported study targeting anomalous subgraphs.
1) Anomalous Edge Detection:
Dynamic edge anomaly detection combines graph representation learning with temporal modeling to capture structural, attribute, and historical information. Approaches use GCNs with GRUs, evolving GCNs, hierarchical graph processing, or temporal subgraph extraction.
- AddGraph combines GCN and GRU to integrate long- and short-term patterns for modeling normal edges from structural, attribute, and temporal information.
- DynAD uses evolving GCNs and an attention-based GRU to adaptively learn parameters and handle newly added nodes.It addresses the limitation that AddGraph requires the entire node set as input.
- A hierarchical GCN with GRU captures multi-level graph structure together with temporal features for anomaly detection.
- StrGNN extracts h-hop subgraphs around target edges, applies GCNs and pooling, and uses GRUs to model temporal dependencies.
2) Anomalous Node Detection:
The surveyed dynamic-graph methods use GNN architectures to model temporal and structural patterns for anomaly detection across software and traffic networks.
- H-VGRAE combines stacked GCN layers with dilated RNN layers to model complex stochastic and spatiotemporal variation in dynamic graphs.
- DEGCN captures evolving local node-level and global graph-level software behaviors through multi-scale graphs, directed convolutions, and graph-encoding GRUs.
- A traffic-network approach splits temporal information into Traffic Dispersion Graphs, balances attackers and normal nodes with synthetic samples, and detects anomalies using GCNs.
IV. OPPORTUNITIES AND CHALLENGES
The survey identifies unresolved challenges in explainability, anomaly identification, imbalance, heterogeneous graphs, and few-shot learning for GNN-based graph anomaly detection.
- Explainable GNNs for Detecting Graph Anomalies: GNN anomaly detectors need explainable outputs because anomaly scores and top-k rankings are difficult to interpret, while relatively little explainable-GNN work exists.
- Identification of Graph Anomalies with GNNs: Reconstruction losses can be noise-sensitive and distance-based functions can fail when anomalous and normal embeddings are distant, motivating better spaces and loss functions.
- Class Imbalance in Graph Anomaly Detection with GNNs: Rare anomalies create inevitable class imbalance, but few studies address it beyond naive negative sampling or graph-specific data augmentation.
- Anomaly Detection with GNNs from Heterogeneous Graphs: Heterogeneous graphs remain under-explored because modeling multiple node and edge relations is difficult, especially with temporal dynamics.
- Few-Shot Graph Anomaly Detection with GNNs: Few-shot graph anomaly detection has received limited study despite the availability of a few labeled anomalies in related real-world graphs.
V. CONCLUSION
The survey reviews GNN-based graph anomaly detection methods and highlights a field expanding beyond static-graph node anomalies toward dynamic and higher-level anomalies.
- The survey provides a comprehensive review of state-of-the-art graph anomaly detection methods built upon GNN models.
- Most research has focused on node anomalies in static graphs, while work is expanding toward dynamic graphs and edge, subgraph, and graph-level anomalies.