mlsanityData to 7 Oct 2026

Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedy

arXiv 2410.20366 ↗First posted 27 Oct 2024cs.LG cs.SIcited by 13

Not on the map. Why?

Abstract (arXiv)

Graph autoencoders (Graph-AEs) learn representations of given graphs by aiming to accurately reconstruct them. A notable application of Graph-AEs is graph-level anomaly detection (GLAD), whose objective is to identify graphs with anomalous topological structures and/or node features compared to the majority of the graph population. Graph-AEs for GLAD regard a graph with a high mean reconstruction error (i.e. mean of errors from all node pairs and/or nodes) as anomalies. Namely, the methods rest on the assumption that they would better reconstruct graphs with similar characteristics to the majority. We, however, report non-trivial counter-examples, a phenomenon we call reconstruction flip, and highlight the limitations of the existing Graph-AE-based GLAD methods. Specifically, we empirically and theoretically investigate when this assumption holds and when it fails. Through our analyses, we further argue that, while the reconstruction errors for a given graph are effective features for GLAD, leveraging the multifaceted summaries of the reconstruction errors, beyond just mean, can further strengthen the features. Thus, we propose a novel and simple GLAD method, named MUSE. The key innovation of MUSE involves taking multifaceted summaries of reconstruction errors as graph features for GLAD. This surprisingly simple method obtains SOTA performance in GLAD, performing best overall among 14 methods across 10 datasets.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 34 of its 58 references that are in the map. First posted on arXiv 27 Oct 2024.

Builds on

34 of 58 references.

References · 34

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2017Deformable Convolutional Networkscited by 1,481
  7. 2016Variational Graph Auto-Encoderscited by 1,373
  8. 2020Graph Contrastive Learning with Augmentationscited by 1,203
  9. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  10. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  11. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  12. 2019Graph U-Netscited by 489
22 more
  1. 2022GraphMAE: Self-Supervised Masked Graph Autoencoderscited by 443
  2. 2022SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentationcited by 171
  3. 2023GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learnercited by 131
  4. 2014Propagation Kernelscited by 88
  5. 2021Deep Graph-level Anomaly Detection by Glocal Knowledge Distillationcited by 67
  6. 2019Image Deformation Meta-Networks for One-Shot Learningcited by 56
  7. 2020A Large-Scale Database for Graph Representation Learningcited by 54
  8. 2020On Using Classification Datasets to Evaluate Graph-Level Outlier Detection: Peculiar Observations and New Insightscited by 53
  9. 2022Raising the Bar in Graph-level Anomaly Detectioncited by 45
  10. 2023Diversity-Measurable Anomaly Detectioncited by 41
  11. 2023Towards Self-Interpretable Graph-Level Anomaly Detectioncited by 41
  12. 2020Explainable Classification of Brain Networks via Contrast Subgraphscited by 26
  13. 2023Towards Deep Attention in Graph Neural Networks: Problems and Remediescited by 24
  14. 2022Directed Graph Auto-Encoderscited by 22
  15. 2024A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guidecited by 22
  16. 2023Graph-level Anomaly Detection via Hierarchical Memory Networkscited by 16
  17. 2024HypeBoy: Generative Self-Supervised Representation Learning on Hypergraphscited by 15
  18. 2023Classification of Edge-dependent Labels of Nodes in Hypergraphscited by 14
  19. 2023RARE: Robust Masked Graph Autoencodercited by 10
  20. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9
  21. 2022Graph Anomaly Detection with Unsupervised GNNscited by 8
  22. 2024Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 7; 2026: 6.

13 papers.

Sort:

By area:

  1. 2026FedCIGAR: A Personalized Reconstruction Approach for Federated Graph-level Anomaly Detectioncited by 6
  2. 2025A Survey on Foundation-Model-Based Industrial Defect Detectioncited by 5
  3. 2025Graph Evidential Learning for Anomaly Detectioncited by 5
  4. 2025'Hello, World!': Making GNNs Talk with LLMscited by 2
  5. 2025Learnable Kernel Density Estimation for Graphs and Its Application to Graph-Level Anomaly Detectioncited by 2
  6. 2025Learning to Flow from Generative Pretext Tasks for Neural Architecture Encodingcited by 1
  7. 2026Detect by Yourself: Self-Designing Agentic Workflows for Few-Shot Graph Anomaly Detectioncited by 1
  8. 2025DeNoise: Learning Robust Graph Representations for Unsupervised Graph-Level Anomaly Detectioncited by 0
  9. 2025Physic-HM: Restoring Physical Generative Logic in Multimodal Anomaly Detection via Hierarchical Modulationcited by 0
  10. 2026Interpretable Graph-Level Anomaly Detection via Contrast with Normal Prototypescited by 0
  11. 2026GAD in the Wild: Benchmarking Graph Anomaly Detection under Realistic Deployment Challengescited by 0
  12. 2026Cross-Domain Industrial Fault Detection by Causal Mechanism Monitoringcited by 0
1 more
  1. 2026GLASS: Graph-Language Alignment with Spherical Scoring for Transferable Graph-Level Anomaly Detectioncited by 0