# Unsupervised Graph Outlier Detection: Problem Revisit, New Insight, and Superior Method

arXiv: https://arxiv.org/abs/2210.12941 · HTML: https://mlsanity.com/paper/2210.12941/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 24 Oct 2022.

## Builds on (most cited first, 19 of 19)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters](https://mlsanity.com/paper/2008.08692/) (2020)
- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning](https://mlsanity.com/paper/2103.00113/) (2021)
- [Deep Learning for Anomaly Detection: A Review](https://mlsanity.com/paper/2007.02500/) (2020)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [AnomalyDAE: Dual autoencoder for anomaly detection on attributed networks](https://mlsanity.com/paper/2002.03665/) (2020)
- [BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs](https://mlsanity.com/paper/2206.10071/) (2022)
- [Generative and Contrastive Self-Supervised Learning for Graph Anomaly Detection](https://mlsanity.com/paper/2108.09896/) (2021)
- [DAGAD: Data Augmentation for Graph Anomaly Detection](https://mlsanity.com/paper/2210.09766/) (2022)
- [Multi-scale Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/1912.04144/) (2019)

## Built on by (most cited first, 15 of 15)

- [Zero-shot Generalist Graph Anomaly Detection with Unified Neighborhood Prompts](https://mlsanity.com/paper/2410.14886/) (2024)
- [ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection](https://mlsanity.com/paper/2312.14535/) (2023)
- [Uncertainty in Graph Neural Networks: A Survey](https://mlsanity.com/paper/2403.07185/) (2024)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [SmoothGNN: Smoothing-aware GNN for Unsupervised Node Anomaly Detection](https://mlsanity.com/paper/2405.17525/) (2024)
- [Towards Fair Graph Anomaly Detection: Problem, Benchmark Datasets, and Evaluation](https://mlsanity.com/paper/2402.15988/) (2024)
- [Learning-Based Link Anomaly Detection in Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2405.18050/) (2024)
- [Graph Anomaly Detection at Group Level: A Topology Pattern Enhanced Unsupervised Approach](https://mlsanity.com/paper/2308.01063/) (2023)
- [Enhancing Fairness in Unsupervised Graph Anomaly Detection through Disentanglement](https://mlsanity.com/paper/2406.00987/) (2024)
- [CAMERA: Adapting to Semantic Camouflage in Unsupervised Text-Attributed Graph Fraud Detection](https://mlsanity.com/paper/2605.20032/) (2026)
- [UMGAD: Unsupervised Multiplex Graph Anomaly Detection](https://mlsanity.com/paper/2411.12556/) (2024)
- [Detecting Anomalies in Dynamic Graphs via Memory enhanced Normality](https://mlsanity.com/paper/2403.09039/) (2024)
- [Unsupervised Graph Anomaly Detection via Multi-Hypersphere Heterophilic Graph Learning](https://mlsanity.com/paper/2503.12037/) (2025)
- [Towards Anomaly-Aware Pre-Training and Fine-Tuning for Graph Anomaly Detection](https://mlsanity.com/paper/2504.14250/) (2025)
- [Enhancing Fairness in Autoencoders for Node-Level Graph Anomaly Detection](https://mlsanity.com/paper/2508.10785/) (2025)

## Abstract (arXiv)

A large number of studies on Graph Outlier Detection (GOD) have emerged in recent years due to its wide applications, in which Unsupervised Node Outlier Detection (UNOD) on attributed networks is an important area. UNOD focuses on detecting two kinds of typical outliers in graphs: the structural outlier and the contextual outlier. Most existing works conduct experiments based on datasets with injected outliers. However, we find that the most widely-used outlier injection approach has a serious data leakage issue. By only utilizing such data leakage, a simple approach can achieve state-of-the-art performance in detecting outliers. In addition, we observe that existing algorithms have a performance drop with the mitigated data leakage issue. The other major issue is on balanced detection performance between the two types of outliers, which has not been considered by existing studies. In this paper, we analyze the cause of the data leakage issue in depth since the injection approach is a building block to advance UNOD. Moreover, we devise a novel variance-based model to detect structural outliers, which outperforms existing algorithms significantly and is more robust at kinds of injection settings. On top of this, we propose a new framework, Variance based Graph Outlier Detection (VGOD), which combines our variance-based model and attribute reconstruction model to detect outliers in a balanced way. Finally, we conduct extensive experiments to demonstrate the effectiveness and efficiency of VGOD. The results on 5 real-world datasets validate that VGOD achieves not only the best performance in detecting outliers but also a balanced detection performance between structural and contextual outliers.