Research map / Graph learning / Graph self-supervised learning
Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that graph autoencoders can reconstruct unseen, more-structured graphs better than training graphs ("reconstruction flip") and proposes MuSE, which summarizes multiple statistics (mean, std) of node-feature and adjacency reconstruction errors as features for one-class graph-level anomaly detection.
Problem
Graph autoencoder-based graph-level anomaly detection assumes anomalous graphs have high mean reconstruction error, but unseen graphs with dissimilar or stronger structural patterns can be reconstructed as well or better than training graphs, causing detection failures.
Approach
Identify the "reconstruction flip" phenomenon both empirically and theoretically (single-layer linear GAE on community and cycle synthetic graphs), and replace the mean-only reconstruction error score with a fixed-size vector of multiple summary statistics (mean and standard deviation) of node-feature and adjacency reconstruction error distributions, fed to a one-class classifier.
Key results
- MuSE attains the best average ranking (A.R. 2.2) among 14 compared methods across 10 graph classification-based GLAD datasets, best on 8 of 10 datasets for GLAD methods.
- MuSE reaches 99.7 AUROC on AIDS and 80.5 on DD, with up to 16.2% gain over the second-best GLAD method (OCGTL) on NCI1.
- MuSE shows the smallest performance drop among the three strongest GLAD methods under 10-30% training-set contamination.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use multifaceted summaries of node-feature and adjacency reconstruction errors instead of learned SSL graph embeddings | MuSE versus SSL-based two-stage baselines · 8 of 10 datasets | AUROC ×100 | Helped |
| remove node-feature reconstruction errors (ablation) | MuSE · GLAD benchmarks | AUROC ×100: 80.5 (2.3) -> 79.4 (3.7) on DD; 78.4 (5.7) -> 72.2 (4.0) on Reddit | Mixed |
| remove adjacency-matrix reconstruction errors (ablation) | MuSE · GLAD benchmarks | AUROC ×100: 80.5 (2.3) -> 61.8 (7.6) on DD; 78.4 (2.2) -> 64.7 (7.1) on Protein | Mixed |
| remove mean aggregation (ablation) | MuSE · GLAD benchmarks | AUROC ×100: 78.4 (2.2) -> 68.1 (5.5) on Protein; 69.2 (3.5) -> 66.2 (6.5) on IMDB | Mixed |
| remove standard-deviation aggregation (ablation) | MuSE · GLAD benchmarks | AUROC ×100: 69.2 (3.5) -> 70.7 (3.7) on IMDB; 67.5 (3.4) -> 62.0 (2.4) on MUTAG | Mixed |
Surprising findings
- Graph autoencoders trained on graphs with a community pattern can reconstruct unseen graphs with stronger pattern strength with lower error than the training graphs (reconstruction flip).
- Several graph-kernel-based GLAD methods perform worse than random guessing on graph classification-based GLAD benchmarks, as reported in prior work.
Limitations
- Theoretical analysis is restricted to a single-layer linear GAE and two synthetic patterns (community and cycle).
- MuSE reconstructs the full adjacency matrix, giving O(n^2) complexity, limiting scalability to large graphs.
- Evaluation uses graph classification datasets as proxies for anomalies rather than ground-truth graph-level anomalies.
Experimental setup
Datasets: DD Protein NCI1 AIDS Reddit IMDB MUTAG DHFR BZR ER Syn-Com Syn-Cycle
Benchmarks: DD Protein NCI1 AIDS Reddit IMDB MUTAG DHFR BZR ER
Metrics: AUROC average ranking
Baselines: DOMINANT-G OCGTL GLocalKD GLADC GLAM HIMNET SIGNET GraphCL-1 GAE-1 GraphMAE-1 GraphCL-2 GAE-2
Builds on: GAE GraphMAE GraphCL OCGTL GLADC
Closest papers by meaning
- ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection (AAAI 2024 · similarity 0.90)
- CurvGAD: Leveraging Curvature for Enhanced Graph Anomaly Detection (ICML 2025 · similarity 0.88)
- Leveraging Diffusion Model as Pseudo-Anomalous Graph Generator for Graph-Level Anomaly Detection (ICML 2025 · similarity 0.88)
- ARC: A Generalist Graph Anomaly Detector with In-Context Learning (NeurIPS 2024 · similarity 0.88)
- Graph Anomaly Detection as Dynamical Transport: Training-Free Scoring via Empirical Bayes (NeurIPS 2026 · similarity 0.88)
- Unifying Unsupervised Graph-Level Anomaly Detection and Out-of-Distribution Detection: A Benchmark (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.