PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Graph Anomaly Detection: A Survey and New Perspectives

Hezhe Qiao, Hanghang Tong, Bo An, Irwin King, Charu Aggarwal, Guansong Pang

arXiv:2409.09957v2cs.LGcs.AI

TL;DR

Graph structure makes traditional anomaly detection methods unsuitable, while popular GNN designs can smooth away differences between normal and abnormal instances. This survey reviews deep GAD through a taxonomy of methods and reports that supervised methods generally outperform unsupervised ones, with exceptions on datasets with injected anomalies.

  • Problem

    Traditional anomaly detection methods cannot be directly applied to graph data, and popular GNN designs may make normal and abnormal instances indistinguishable through over-smoothing.

    Source: §I · p. 1

  • Method

    The survey analyzes GAD complexities and reviews deep methods through perspectives on GNN backbones, proxy tasks, and graph anomaly measures.

    Source: §I · p. 1

  • Results

    Supervised methods generally outperform unsupervised methods, but unsupervised reconstruction- and contrastive-learning methods can perform best on datasets with injected anomalies.

    Source: Appendix D · p. 21

  • Takeaways & Limitations

    The survey identifies six future research directions for addressing GAD’s unique challenges.

    Source: §VIII · p. 17

    Interpretability in GAD remains largely unexplored, despite the importance of explaining anomaly predictions in real applications.

    Source: B. Major Challenges · p. 4

Abstract

from arXiv · show

Graph anomaly detection (GAD), which aims to identify unusual graph instances (nodes, edges, subgraphs, or graphs), has attracted increasing attention in recent years due to its significance in a wide range of applications. Deep learning approaches, graph neural networks (GNNs) in particular, have been emerging as a promising paradigm for GAD, owing to its strong capability in capturing complex structure and/or node attributes in graph data. Considering the large number of methods proposed for GNN-based GAD, it is of paramount importance to summarize the methodologies and findings in the existing GAD studies, so that we can pinpoint effective model designs for tackling open GAD problems. To this end, in this work we aim to present a comprehensive review of deep learning approaches for GAD. Existing GAD surveys are focused on task-specific discussions, making it difficult to understand the technical insights of existing methods and their limitations in addressing some unique challenges in GAD. To fill this gap, we first discuss the problem complexities and their resulting challenges in GAD, and then provide a systematic review of current deep GAD methods from three novel perspectives of methodology, including GNN backbone design, proxy task design for GAD, and graph anomaly measures. To deepen the discussions, we further propose a taxonomy of 13 fine-grained method categories under these three perspectives to provide more in-depth insights into the model designs and their capabilities. To facilitate the experiments and validation, we also summarize a collection of widely-used GAD datasets and empirical comparison. We further discuss multiple open problems to inspire more future high-quality research. A continuously updated repository for datasets, links to the codes of algorithms, and empirical comparison is available at https://github.com/mala-lab/Awesome-Deep-Graph-Anomaly-Detection.

I. INTRODUCTION

The survey reviews deep GAD methods and the challenges that shape their design, organizing methods by GNN backbone, proxy task, and graph anomaly measures. It also highlights the diversity of graph abnormalities and the need to account for graph structure, scale, and context.

I. INTRODUCTION

  • Earlier GAD surveys often focus on non-deep methods, general anomaly detection, task-specific reviews, or performance benchmarks, limiting insight into methods’ technical designs and challenges.The survey addresses this gap by reviewing problem complexities, deep GAD methods, datasets, and empirical comparisons.Source: §I · pp. 1–2
  • The survey organizes deep GAD methods into 13 fine-grained categories spanning GNN backbones, proxy tasks, and graph anomaly measures.The taxonomy examines methods’ intuitions, assumptions, learning objectives, advantages, disadvantages, and capabilities.Source: §I · p. 2
  • The survey identifies six future research directions and summarizes representative methods, widely used datasets, and empirical comparisons.It frames the directions as open problems for addressing GAD’s unique challenges.Source: §I · p. 2

A. Major Problem Complexities

  • Graph anomalies depend on connected context, and what is abnormal can differ across static, dynamic, homophilic, and heterophilic graphs.An instance abnormal at one time step may appear normal in the graph’s evolution; abnormality can also differ between homophilic and heterophilic graphs.Source: A. Major Problem Complexities · p. 2
  • Large graphs make it costly to load the structural relations needed to assess anomalies using global context.Modern applications can involve millions or billions of nodes or edges, while global analysis may require the full graph or many of its relations.Source: A. Major Problem Complexities · p. 2
  • Graph anomalies can occur in nodes, edges, subgraphs, or whole graphs, and vary across attributes, structure, and local or global context.Attribute, structural, contextual, and local-affinity anomalies can combine in ways that differ from conventional anomaly types.Source: A. Major Problem Complexities · pp. 2–3
  • GAD also faces rare and potentially unknown anomalies, long-tailed graph data, and anomalous instances that camouflage themselves as normal locally or globally.Knowing one anomaly type may not generalize to others, which can vary by graph component and structural context.Source: A. Major Problem Complexities · p. 3

B. Major Challenges

Deep GAD must model structural context without smoothing away anomalies, while addressing scale, anomaly diversity, class imbalance, and robustness and interpretability. The paper also frames GAD as scoring graph instances across node, edge, subgraph, and graph levels.

B. Major Challenges

  • Structural context affects anomaly scores across graph types, while oversmoothing can make abnormal and normal instances indistinguishable.The challenge is to capture diverse structural influences while avoiding this loss of distinction.Source: B. Major Challenges · p. 3
  • Large graphs make modeling global or higher-order structure computationally difficult, and subgraph or sampling methods can omit structural information.This can yield suboptimal performance, particularly for unsupervised GAD.Source: B. Major Challenges · p. 3
  • Methods must generalize across attribute, structural, and mixed anomalies, although many existing approaches target a specific anomaly type.The challenge is greater when training data does not show every possible anomaly class.Source: B. Major Challenges · p. 3
  • Normal instances greatly outnumber anomalies, which can bias training toward normal patterns and leave models weak at recognizing anomalies.Poorly chosen detection thresholds can worsen imbalance effects for some methods.Source: B. Major Challenges · pp. 3–4
  • Real-world GAD must handle camouflage and unknown-anomaly contamination, while producing explanations useful for investigating detections.For fraud detection, explanations may need to link activity to particular transaction attributes, relations, and times.Source: B. Major Challenges · p. 4

A. Preliminaries

  • GAD learns a scoring function over nodes, edges, subgraphs, or whole graphs, typically assuming normal instances greatly outnumber abnormal ones.The score is intended to rank normal instances below abnormal ones.Source: A. Preliminaries · p. 5

B. Categorization of Deep GAD Methods

The survey organizes deep GAD methods into three technical perspectives and 13 fine-grained categories. Within GNN backbone design, it distinguishes discriminative and generative methods and details aggregation mechanisms for discriminative GNNs.

B. Categorization of Deep GAD Methods

  • The taxonomy groups deep GAD methods by GNN backbone design, proxy-task design, and graph anomaly measures, then divides them into 13 fine-grained categories.The categories are intended to clarify model designs and their capabilities in addressing GAD challenges.Source: B. Categorization of Deep GAD Methods · p. 5

IV. GNN BACKBONE DESIGN

A. Discriminative GNNs

  • Discriminative GNNs use supervised learning on labeled normal and abnormal instances, adapting message passing to capture majority or deviation patterns.They typically optimize cross-entropy and use the predicted abnormal probability or its inverse as an anomaly score.Source: A. Discriminative GNNs · p. 5

1) Aggregation Mechanism:

  • Aggregation assumes connected instances from the same class share characteristics; heterophily can hinder discrimination, while repeated neighborhood aggregation can blur subtle anomalies.The survey frames tailored feature aggregation as a way to learn more distinguishable normal and abnormal representations.Source: 1) Aggregation Mechanism · p. 6
  • Aggregation designs include hard or soft neighborhood edge selection and edge synthesis, with examples using inconsistency-weighted connections, class-balanced subgraphs, and distant nodes.Edge selection can lose important structure, while synthesis can add noise or irrelevant structure.Source: 1) Aggregation Mechanism · pp. 6–7

A. Discriminative GNNs

  • End-to-end imbalanced classification can use available abnormal examples without graph reconstruction, reducing memory use and improving scalability, but requires labeled data.The methods may be inapplicable or less effective when such labels are difficult to obtain.Source: 1) Aggregation Mechanism · p. 7

2) Feature Transformation:

Feature transformation focuses GNNs on discriminative features by transforming graph-instance representations or raw attributes, using gradient scoring or spectral filters. These approaches can capture information beyond local graph properties, but their effectiveness depends on the selected features and graph type.

2) Feature Transformation:

  • Feature transformation targets discriminative information by transforming GNN representations or raw attributes, using gradient information or spectral graph filters.The approach assumes raw attributes or graph structure contain irrelevant or noisy information that should be discarded during feature aggregation.Source: 2) Feature Transformation · p. 7
  • Gradient-based scoring selects the top K representation features with the largest class-specific gradient scores; GDN uses this approach in a supervised manner.The score reflects a feature's contribution to anomaly detection, and selected features are often invariant to structure distribution shift.Source: 2) Feature Transformation · p. 7
  • Spectral filters transform attributes into latent representations by separating low-frequency normal patterns from high-frequency deviations associated with abnormal nodes.Graph Fourier filtering uses Laplacian spectral properties to capture these frequency variations.Source: 2) Feature Transformation · pp. 7–8
  • AMNet adaptively combines mixed-frequency graph signals, while BWGNN uses band-pass filters motivated by the transfer of energy toward higher frequencies as anomaly degree increases.For heterophilic graphs, SEC-GFD partitions the spectrum into hybrid frequency bands, and SplitGNN combines a band-pass filter with a tunable Beta Wavelet GNN.Source: 2) Feature Transformation · p. 8
  • Feature transformation can extract features from noisy data and represent connectivity, centrality, and community structure beyond local graph properties.It avoids costly graph-structure reconstruction, making it suitable for large-scale GAD, but a single scoring criterion or filter may miss important discriminative features.Source: 2) Feature Transformation · p. 8
  • Spectral GNNs are primarily designed for homogeneous graphs and may not suit heterogeneous graphs with different node types.A feature scoring criterion or spectral filter may also overlook information crucial to GAD.Source: 2) Feature Transformation · p. 8

B. Generative GNNs

Generative GNNs augment graph data by synthesizing instances to address anomaly scarcity and variation. Feature interpolation creates representations from existing instances and is used to address biased GAD, with benefits and limitations for anomaly diversity and sample quality.

B. Generative GNNs

  • Generative GNNs synthesize graph instances to augment training data, providing pseudo-anomaly information in response to the scarcity and variation of anomalies.A generator uses an existing instance, graph attributes and structure, and auxiliary information; the augmented data is then used with a one-class or binary classification loss.Source: B. Generative GNNs · p. 8

1) Feature Interpolation:

  • Feature interpolation creates a new graph-instance representation as a convex combination of two existing representations from the same class.The approach assumes interpolated representations can align with representations of anomaly-class instances.Source: 1) Feature Interpolation · pp. 8–9
  • GraphSMOTE, GraphMixup, and GraphENS use feature interpolation for biased GAD in closed-set supervised settings, without targeting unknown anomaly types absent from labeled training examples.GraphSMOTE also trains an edge generator to model connections between existing and generated nodes; GraphMixup interpolates in semantic relation spaces to mitigate out-of-domain samples from direct interpolation.Source: 1) Feature Interpolation · p. 9
  • Feature interpolation offers a simple way to add samples for under-represented anomaly classes, and mixing representations can diversify training data.The review states this may improve a GAD model's generalization.Source: 1) Feature Interpolation · p. 9
  • Feature interpolation can mitigate imbalance and may generate abnormal instances unlike training anomalies, potentially improving generalization to unknown anomalies.It generates node representations but not graph structure, so methods typically need an additional local structure generator; ambiguous samples may also make normal and anomaly classes harder to separate.Source: 1) Feature Interpolation · p. 9

2) Noise Perturbation:

Noise perturbation methods generate graph instances using prior-driven noise, which can incorporate prior knowledge of normality or abnormality into training. They can diversify samples and support detection of different anomalies, but may produce out-of-domain instances and require careful noise-level selection.

2) Noise Perturbation:

  • Noise perturbation methods generate graph instances from prior-driven noise and can incorporate prior knowledge of graph normality or abnormality into training.The generated samples, together with labels for existing nodes, can guide a GAD discriminator; the noise is typically drawn from a probability distribution such as a Gaussian.Source: 2) Noise Perturbation · p. 9
  • Representation-permutation methods apply permutations to GNN representations to generate anomalous samples; examples use labeled instances or priors about anomaly structure and representation.ConsisGAD injects noise into unlabeled-node representations to produce instances that remain consistent with the originals while increasing diversity.Source: 2) Noise Perturbation · pp. 9–10
  • Denoising diffusion models progressively add scheduled Gaussian noise and reverse the process to recover representations before generating anomalous graphs.GODM synthesizes pseudo-anomalous instances close to real anomalies in latent space, while DIFFAD generates samples aligned with the original instance in egonet similarity to address labeled-anomaly scarcity.Source: 2) Noise Perturbation · p. 10
  • Generated instances may support identification of unseen anomalies and diversify training, but out-of-domain samples can weaken detection and choosing the noise level may require extensive experimentation.The review also says instance generation can enhance generalization across graph anomalies and help balance GAD training samples.Source: 2) Noise Perturbation · p. 10

V. PROXY TASK DESIGN

Proxy-task methods use learning objectives to capture normal and abnormal graph patterns without human-annotated labels. The section introduces five proxy-task families and details reconstruction methods.

V. PROXY TASK DESIGN

  • Proxy-task methods comprise reconstruction, contrastive learning, knowledge distillation, adversarial learning, and score prediction.They optimize objectives intended to capture diverse graph patterns without human-annotated labels.Source: §V · p. 10, Figure 5 · p. 10

A. Graph Reconstruction

  • Graph reconstruction uses a GNN encoder and decoder to reconstruct graph attributes and structure, optionally with an auxiliary task.Its general assumption is that normal instances reconstruct well while anomalies incur larger reconstruction errors.Source: A. Graph Reconstruction · p. 10
  • GAE-based methods extend reconstruction with attention, spectral information, community-aware representations, relation reconstruction, or multiple graph views.Examples include attention to neighbor importance and community-specific representations for encoding and decoding modularity.Source: A. Graph Reconstruction · p. 11
  • Reconstruction is a label-free, simple approach applicable to anomalous nodes, edges, and graphs.Its advantages include retaining normal information when normal instances predominate.Source: A. Graph Reconstruction · pp. 10–11
  • Reconstruction may require loading the entire graph and is vulnerable to noisy or irrelevant attributes, which can cause false positives or reduced accuracy.The survey associates reconstruction with modeling the full graph structure and detecting anomalies at different instance levels.Source: A. Graph Reconstruction · p. 11

B. Graph Contrastive Learning

Graph contrastive learning trains representations from positive and negative graph-instance pairs to capture dominant patterns without human-annotated labels. The survey describes pair-generation strategies, applications, and trade-offs.

B. Graph Contrastive Learning

  • GAD-oriented graph contrastive learning uses a GNN to represent graph instances and a contrastive loss to pull positive views together and push negative pairs apart.The framework depends on choosing positive and negative pairs that align with anomaly detection.Source: B. Graph Contrastive Learning · p. 11
  • A common assumption treats non-neighboring nodes as dissimilar, anomalous samples relative to a target node.The survey relates this assumption to datasets containing a substantial number of normal instances.Source: B. Graph Contrastive Learning · p. 11
  • Methods generate contrasts at node, subgraph, edge, and graph levels, including CoLA’s node-neighborhood subgraphs, TADDY’s dynamic edges, and SIGNET’s graph views.Negative samples may use anomaly-type prior knowledge, supervised pairs, or multi-view and multi-scale subgraph generation.Source: B. Graph Contrastive Learning · pp. 11–12
  • Local-information training can scale to large graphs, but subgraph generation may be computationally costly and learned representations still need effective anomaly scoring.Over-smoothing between normal and abnormal instances also remains a concern when methods rely on GNNs without class information.Source: B. Graph Contrastive Learning · p. 12

C. Graph Representation Distillation

The section describes teacher–student representation distillation and adversarial graph learning as proxy-task approaches for GAD. It outlines their assumptions, representative designs, and limitations.

C. Graph Representation Distillation

  • Distillation-based GAD treats teacher–student representation differences as anomaly signals, assuming distillation extracts prevalent normal graph patterns.A GNN-based student is trained to replicate representations from a teacher model.Source: C. Graph Representation Distillation · p. 12
  • Distillation designs include random-GCN teachers, two students trained separately on normal and abnormal graphs, and a pretrained anomaly detector as teacher.GlocaKD uses KL divergence, while GLADST uses a heuristic-trained teacher and FGAD uses a pretrained detector.Source: C. Graph Representation Distillation · pp. 12–13
  • Distillation can yield smaller, more efficient models and may improve generalization across graph types, but teacher choice and student capacity constrain transfer.An unsuitable teacher may provide nonoptimal knowledge, and a student may fail to capture the teacher’s nuances.Source: C. Graph Representation Distillation · p. 13

D. Adversarial Graph Learning

  • Adversarial graph learning trains a generator to produce samples from a prior and a discriminator to distinguish generated instances from real data.The generator is intended to capture normality, while the discriminator’s output commonly informs anomaly scoring.Source: D. Adversarial Graph Learning · p. 13
  • GAN-based methods can generate samples for learning beyond observed abnormalities, but realistic graph generation is difficult and training is less stable than other GNN methods.The survey notes uses for unseen anomalies and for generating extensive abnormal samples to support more balanced GAD.Source: D. Adversarial Graph Learning · pp. 13–14

E. Score Prediction

Score-prediction methods train a GNN to predict anomaly scores, using limited labeled normal and abnormal instances and a prior distribution. The section discusses the deviation-loss approach and its assumptions and limitations.

E. Score Prediction

  • Score prediction trains a GNN-based predictor to directly output anomaly scores, including in settings where only some graph instances are labeled.The approach assumes normal-instance scores follow a prior distribution and abnormal-instance scores deviate from it.Source: E. Score Prediction · p. 14
  • DevNet uses a Z-score-based deviation loss with class labels and a predefined margin based on a prior distribution.The deviation score uses the estimated mean and standard deviation of scores under that prior.Source: E. Score Prediction · p. 14
  • Graph adaptations include Meta-GDN’s small number of labeled anomalies, SAD’s dynamic-graph contrastive learning, and WEDGE’s subgraph-level deviation loss.These methods use deviation loss to separate scores from prior-based reference scores.Source: E. Score Prediction · p. 14
  • The approach can scale to large graphs and support generalized GAD when some graph instances are labeled, but depends on the prior and predefined margin.The survey also notes that a single prior may not capture dependent scores across graph instances.Source: E. Score Prediction · p. 14

VI. GRAPH ANOMALY MEASURES

The survey organizes graph anomaly measures into four families; this section details one-class distance and community adherence as two ways to score abnormality.

A. One-class Classification Measure

  • One-class measures score distance from a center, assuming normal instances fit a hypersphere while anomalies lie farther away.GNNs learn the instance representations; cited methods add auxiliary tasks to reduce model collapse. The approach needs no labeled anomalies and can handle isolated nodes, but varied normal patterns and collapse remain challenges.Source: A. One-class Classification Measure · pp. 14–15

B. Community Adherence

  • Community-adherence methods cluster learned instance representations and score anomalies by distance to the nearest community center.MHGL learns multiple fine-grained normal patterns, while Netwalk uses k-means for node and edge groups; these methods are sensitive to cluster settings and community-detection quality.Source: B. Community Adherence · p. 15
  • Community structure can capture normality beyond one-hop neighborhoods and support interpreting anomalies as deviations from expected community behavior.The methods assume normal instances adhere to at least one community, unlike anomalies.Source: B. Community Adherence · p. 15

C. Local Affinity

Local affinity scores neighborhood similarity, while graph isolation scores how readily an instance is separated in a learned representation space.

C. Local Affinity

  • Local affinity treats weak neighborhood similarity as anomalous, using signals such as connections, representation similarity, or subgraph clustering.TAM maximizes node affinity after removing non-homophily edges; CLAD measures neighbor discrepancy, while PREM contrasts ego networks with neighboring instances. The approach can be interpretable but depends on specified graph properties and is primarily node-focused.Source: C. Local Affinity · pp. 15–16

D. Graph Isolation

  • Graph-isolation methods encode instances with a GNN, then score them by the difficulty of isolating their representations.Isolation is efficient and can scale to large graphs, but effectiveness depends on expressive representations and incorporating the isolation heuristic into GNN learning is difficult.Source: D. Graph Isolation · p. 16

VII. RESEARCH OPPORTUNITIES

The survey identifies six open research directions for deep GAD and concludes by framing them as opportunities to advance methods for real-life tasks.

VII. RESEARCH OPPORTUNITIES

  • Anomaly measures beyond proxy tasks and traditional measures could better capture holistic graph structure and attributes for GAD.The survey points to local node affinity as one example of a more dedicated measure.Source: §VII · p. 16
  • GAD methods designed for large, heterogeneous, or streaming graphs are needed because current methods mainly target small-scale, static, or homogeneous data.Streaming settings may restrict graph access at each time step and require adaptation as patterns evolve.Source: §VII · pp. 16–17
  • Camouflage and training-data contamination remain challenges: camouflage approaches often need prior knowledge, and contaminated anomalies can bias message passing.Semi-supervision with labeled normal instances or training on truncated graphs are cited as possible approaches.Source: §VII · p. 17
  • Interpretable GAD needs to explain why an instance is anomalous within graph structure, potentially using local structure, human feedback, or domain knowledge.The survey also notes that anomaly explanations may be leveraged to improve detection performance.Source: §VII · p. 17
  • Open-set supervised GAD trains with labeled normal and seen anomalies while allowing anomaly classes absent from training examples.The survey describes this as a more realistic setting than the closed-set assumption and suggests modeling normal patterns alongside seen anomalies to avoid overfitting them.Source: §VII · p. 17
  • Foundation models and large language models are proposed as directions for GAD, including zero- or few-shot, inductive, and text-described interpretable detection.The survey cites existing image and video anomaly-detection tuning approaches and graph-related prompt or in-context methods as motivation.Source: §VII · p. 17

VIII. CONCLUSION

  • The survey synthesizes deep GAD by reviewing assumptions, advantages, disadvantages, and challenge coverage across fine-grained method categories.It concludes that addressing the six directions may lead to more advanced methods for real-life GAD tasks.Source: §VIII · p. 17

APPENDIX

The appendix characterizes representative methods and datasets, compares reported performance, and discusses patterns across methods and evaluation settings.

APPENDIX A ALGORITHMS

  • Representative methods are mostly supervised or unsupervised, with backbone-based approaches mostly supervised and proxy-task or anomaly-measure approaches mostly unsupervised.The appendix also distinguishes evaluations using real anomalies, synthetic injected anomalies, or both, and notes newer semi-supervised and open-set settings.Source: Appendix A · p. 21

APPENDIX B DATASETS

  • The appendix collects public node-level, graph-level, and dynamic GAD datasets, including synthetic datasets with injected anomalies and real-world datasets with genuine anomalies.Dataset statistics include nodes, edges, anomaly ratios, and whether anomalies are real or injected.Source: Appendix B · p. 21

APPENDIX C QUANTITATIVE COMPARISON

  • The empirical comparison compiles original-paper results across node- and graph-level datasets, using AUROC, AUPRC, F1, and runtime comparisons.Runtime may not be directly comparable because methods were evaluated in different experimental environments.Source: Appendix C · p. 21

APPENDIX D EXPLANATION/ANALYSIS ON PERFORMANCE

  • Supervised methods generally outperform unsupervised methods, but unsupervised reconstruction and contrastive methods can lead on injected-anomaly datasets.Performance advantages are often dataset-specific; reconstruction methods may not scale to very large datasets, and graph-level methods are mostly unsupervised and designed for homogeneous graphs.Source: Appendix D · p. 21
  • F1 is reported by few studies, all supervised, and generally improves as the number of labeled nodes increases.Source: Appendix D · p. 21
  • Unsupervised methods typically take longer than semi-supervised and supervised methods, while supervised-loss optimization generally has lower computational costs.The survey attributes the higher unsupervised runtime to tasks such as reconstruction, contrastive learning, and local-affinity calculation.Source: Appendix D · p. 21

Related papers

Loading 2409.09957v2…