Unsupervised Graph Outlier Detection: Problem Revisit, New Insight, and Superior Method (2022-10-24T00:00:00.000000Z)

TL;DR

A novel variance-based model is devised to detect structural outliers, which outperforms existing algorithms significantly and is more robust at kinds of injection settings and a new framework is proposed, Variance-based Graph Outlier Detection (VGOD), which combines the variance- based model and attribute reconstruction model to detect outliers in a balanced way.

Abstract

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.

References42 items

DAGAD: Data Augmentation for Graph Anomaly Detection

BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs

Decoupling the Depth and Scope of Graph Neural Networks

Higher-order Structure Based Anomaly Detection on Attributed Networks

Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods

ANEMONE: Graph Anomaly Detection with Multi-Scale Contrastive Learning

Generative and Contrastive Self-Supervised Learning for Graph Anomaly Detection

A Comprehensive Survey on Graph Anomaly Detection With Deep Learning

To the Best of Our Knowledge

Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning

Error-Bounded Graph Anomaly Loss for GNNs

RoSANE: Robust and scalable attributed network embedding for sparse networks

Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters

Deep Learning for Anomaly Detection

A comprehensive survey of anomaly detection techniques for high dimensional big data

Inductive Anomaly Detection on Attributed Networks

Anomalydae: Dual Autoencoder for Anomaly Detection on Attributed Networks

Outlier Resistant Unsupervised Deep Architectures for Attributed Network Embedding

Multi-scale Anomaly Detection on Attributed Networks

Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks

Deep Anomaly Detection on Attributed Networks

Interactive Anomaly Detection on Attributed Networks

How Powerful are Graph Neural Networks?

A Survey on Deep Learning

ANOMALOUS: A Joint Modeling Approach for Anomaly Detection on Attributed Networks

Graph Attention Networks

Radar: Residual Analysis for Anomaly Detection in Attributed Networks

Inductive Representation Learning on Large Graphs

Neural Message Passing for Quantum Chemistry

Semi-Supervised Classification with Graph Convolutional Networks

Area Under the Receiver Operating Characteristic Curve (AUC) for the CBM, M-65SNP, BRR, BA, BC, B-LASSO and G-BLUP.

Graph based anomaly detection and description: a survey

Non-Negative Residual Matrix Factorization with Application to Graph Anomaly Detection

Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms

Leakage in data mining: formulation, detection, and avoidance

AutoPart: Parameter-Free Graph Partitioning and Outlier Detection

Contrastive Attributed Network Anomaly Detection with Data Augmentation

A Comprehensive Survey on Graph Neural Networks

THE REDUCTION OF A GRAPH TO CANONICAL FORM AND THE ALGEBRA WHICH APPEARS THEREIN

Extensive experiments are conducted to demonstrate that our approach achieves the best detection performance and the detection balance

We analyze the cause of data leakage in depth, give suggestions for the future design of the outlier injection approach, and purpose a new approach for injecting structural outliers

We propose a novel variance-based model and a new VGOD framework, which outperforms existing algorithms in detecting outliers and alleviates the issue of balanced detection