Revisiting Graph-Level Anomaly Detection: From Partially to Fully Unsupervised Learning
Open Access
- 12 April 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 901-912
Abstract
Graph-level anomaly detection (GLAD) is a critical task to identify graphs with abnormal properties in various domains, ranging from fraudulent social networks to malicious botnets on online platforms. The dominant paradigm for existing GLAD detectors has been partially unsupervised, relying on training data composed exclusively of normal samples. However, this partially unsupervised paradigm inevitably requires a costly expert filtering process to ensure the training data is free of anomalies. This creates a significant gap between current approaches and the real-world necessity of a fully unsupervised paradigm, which involves training a model directly on real-world data ''as-is'', with its inherent mix of normal and anomalous samples. To bridge this gap, we incorporate uncertainty learning into GLAD to promote fully unsupervised learning. We propose two frameworks: Score Uncertainty Learning (SUL) and Graph-data Uncertainty Learning (GUL). Specifically, SUL enhances existing GLAD detectors by modeling uncertainty through Gaussian distributions over the detectors' predictions, adaptively attenuating the influence of potential anomalies. GUL is an end-to-end framework that iteratively optimizes anomaly detection and uncertainty modeling via an Expectation-Maximization algorithm. In addition, we develop a dedicated loss that utilizes potential anomalies to enhance the effectiveness and robustness of GUL. Empirical results on sixteen benchmark datasets, covering real-world graphs from social networks and online platforms, demonstrate the superiority of our methods and highlight the promise of incorporating uncertainty into fully unsupervised GLAD.Keywords
Funding Information
- Australian Research Council Projects (DP260100944)
- Australian Research Council Projects (FT250100159)
This publication has 17 references indexed in Scilit:
- Learning Subgraph-Based Normality for Interpretable Graph-Level Anomaly DetectionIEEE Transactions on Information Forensics and Security, 2025
- Revisiting Attack-Caused Structural Distribution Shift in Graph Anomaly DetectionIEEE Transactions on Knowledge and Data Engineering, 2024
- On Using Classification Datasets to Evaluate Graph Outlier Detection: Peculiar Observations and New InsightsBig Data, 2023
- A review of uncertainty quantification in deep learning: Techniques, applications and challengesInformation Fusion, 2021
- A Unifying Review of Deep and Shallow Anomaly DetectionProceedings of the IEEE, 2021
- Graph based anomaly detection and description: a surveyData Mining and Knowledge Discovery, 2014
- The expectation-maximization algorithmIEEE Signal Processing Magazine, 1996
- Uncertainties in risk analysis: Six levels of treatmentReliability Engineering & System Safety, 1996
- Estimating the mean and variance of the target probability distribution1994
- Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicityJournal of Medicinal Chemistry, 1991