Open-Set Graph Anomaly Detection via Normal Structure Regularisation
Qizhou Wang, Guansong Pang, Mahsa Salehi, Xiaokun Xia, Christopher Leckie
Abstract
This paper considers an important Graph Anomaly Detection (GAD) task, namely open-set GAD, which aims to train a detection model using a small number of normal and anomaly nodes (referred to as seen anomalies) to detect both seen anomalies and unseen anomalies (i.e., anomalies that cannot be illustrated the training anomalies). Those labelled training data provide crucial prior knowledge about abnormalities for GAD models, enabling substantially reduced detection errors. However, current supervised GAD methods tend to over-emphasise fitting the seen anomalies, leading to many errors of detecting the unseen anomalies as normal nodes. Further, existing open-set AD models were introduced to handle Euclidean data, failing to effectively capture discriminative features from graph structure and node attributes for GAD. In this work, we propose a novel open-set GAD approach, namely normal structure regularisation (NSReg), to achieve generalised detection ability to unseen anomalies, while maintaining its effectiveness on detecting seen anomalies. The key idea in NSReg is to introduce a regularisation term that enforces the learning of compact, semantically-rich representations of normal nodes based on their structural relations to other nodes. When being optimised with supervised anomaly detection losses, the regularisation term helps incorporate strong normality into the modelling, and thus, it effectively avoids overfitting the seen anomalies and learns a better normality decision boundary, largely reducing the false negatives of detecting unseen anomalies as normal. Extensive empirical results on seven real-world datasets show that NSReg significantly outperforms state-of-the-art competing methods by at least 14% AUC-ROC on the unseen anomaly classes and by 10% AUC-ROC on all anomaly classes.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
8 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Normality Calibration in Semi-supervised Graph Anomaly Detection cites Rethinking Graph Neural Networks for Anomaly Detection
- Normality Calibration in Semi-supervised Graph Anomaly Detection cites Generative Semi-supervised Graph Anomaly Detection
- Normality Calibration in Semi-supervised Graph Anomaly Detection cites Deep Semi-Supervised Anomaly Detection
- AnomalyGFM: Graph Foundation Model for Zero/Few-shot Anomaly Detection cites Rethinking Graph Neural Networks for Anomaly Detection
- Out-of-Distribution Generalized Graph Anomaly Detection with Homophily-aware Environment Mixup cites Rethinking Graph Neural Networks for Anomaly Detection
- Generative Semi-supervised Graph Anomaly Detection cites Rethinking Graph Neural Networks for Anomaly Detection
- Correcting False Alarms from Unseen: Adapting Graph Anomaly Detectors at Test Time cites Rethinking Graph Neural Networks for Anomaly Detection
Cited by top-tier papers8
- Generative Semi-supervised Graph Anomaly DetectionHezhe Qiao, Qingsong Wen, Xiaoli Li, Ee-Peng Lim et al.NeurIPS 2024 · 48 citations
- AnomalyGFM: Graph Foundation Model for Zero/Few-shot Anomaly DetectionHezhe Qiao, Chaoxi Niu, Ling Chen, Guansong PangKDD 2025 · 8 citations
- Correcting False Alarms from Unseen: Adapting Graph Anomaly Detectors at Test TimeJunjun Pan, Yixin Liu, Chuan Zhou, Fei Xiong et al.AAAI 2026 · 5 citations
- Out-of-Distribution Generalized Graph Anomaly Detection with Homophily-aware Environment MixupSibo Tian, Xin Wang, Zeyang Zhang, Haibo Chen et al.NeurIPS 2025 · 3 citations
- Normality Calibration in Semi-supervised Graph Anomaly DetectionGuolei Zeng, Hezhe Qiao, Guoguo Ai, Jinsong Guo et al.ICML 2026 · 1 citation
Builds on16
- Open Graph Benchmark: Datasets for Machine Learning on GraphsWeihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong et al.NeurIPS 2020 · 3,935 citations
- Towards Total Recall in Industrial Anomaly DetectionKarsten Roth, Latha Pemula, Joaquin Zepeda, Bernhard Schölkopf et al.CVPR 2022 · 1,301 citations
- Deep Semi-Supervised Anomaly DetectionLukas Ruff, Robert A. Vandermeulen, Nico Görnitz, Alexander Binder et al.ICLR 2020 · 678 citations
- Rethinking Graph Neural Networks for Anomaly DetectionJianheng Tang, Jiajin Li, Ziqi Gao, Jia LiICML 2022 · 365 citations
- Learning and Evaluating Representations for Deep One-Class ClassificationKihyuk Sohn, Chun-Liang Li, Jinsung Yoon, Minho Jin et al.ICLR 2021 · 243 citations
Related papers
- Dynamic Multi-sample Mixup with Gradient Exploration for Open-set Graph Anomaly DetectionCaiyang Yu, Wei Ju, Haixin Wang, Yifan Wang et al.ICLR 2026
- Anomaly Heterogeneity Learning for Open-Set Supervised Anomaly DetectionJiawen Zhu, Choubo Ding, Yu Tian, Guansong PangCVPR 2024 · 28 citations
- ARC: A Generalist Graph Anomaly Detector with In-Context LearningYixin Liu, Shiyuan Li, Yu Zheng, Qingfeng Chen et al.NeurIPS 2024 · 73 citations
- How to use Graph Data in the Wild to Help Graph Anomaly Detection?Yuxuan Cao, Jiarong Xu, Chen Zhao, Jiaan Wang et al.KDD 2025 · 1 citation
- Catching Both Gray and Black Swans: Open-set Supervised Anomaly DetectionChoubo Ding, Guansong Pang, Chunhua ShenCVPR 2022 · 163 citations
