BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs (2022-06-21T00:00:00.000000Z)

TL;DR

This work presents the first comprehensive benchmark for unsupervised outlier node detection on static attributed graphs called BOND, and benchmark the outlier detection performance of 14 methods ranging from classical matrix factorization to the latest graph neural networks.

Abstract

Detecting which nodes in graphs are outliers is a relatively new machine learning task with numerous applications. Despite the proliferation of algorithms developed in recent years for this task, there has been no standard comprehensive setting for performance evaluation. Consequently, it has been difficult to understand which methods work well and when under a broad range of settings. To bridge this gap, we present--to the best of our knowledge--the first comprehensive benchmark for unsupervised outlier node detection on static attributed graphs called BOND, with the following highlights. (1) We benchmark the outlier detection performance of 14 methods ranging from classical matrix factorization to the latest graph neural networks. (2) Using nine real datasets, our benchmark assesses how the different detection methods respond to two major types of synthetic outliers and separately to"organic"(real non-synthetic) outliers. (3) Using an existing random graph generation technique, we produce a family of synthetically generated datasets of different graph sizes that enable us to compare the running time and memory usage of the different outlier detection algorithms. Based on our experimental results, we discuss the pros and cons of existing graph outlier detection algorithms, and we highlight opportunities for future research. Importantly, our code is freely available and meant to be easily extendable: https://github.com/pygod-team/pygod/tree/main/benchmark

Authors

References106 items

DGraph: A Large-Scale Financial Dataset for Graph Anomaly Detection

ADBench: Anomaly Detection Benchmark

Hyperparameter Sensitivity in Deep Outlier Detection: Analysis and a Scalable Hyper-Ensemble Solution

Raising the Bar in Graph-level Anomaly Detection

On Equivalence of Anomaly Detection Algorithms

PyGOD: A Python Library for Graph Outlier Detection

How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision

eFraudCom: An E-commerce Fraud Detection System via Competitive Graph Neural Networks

Data Augmentation for Deep Graph Learning

Towards Similarity-Aware Time-Series Classification

ECOD: Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions

Meta Propagation Networks for Graph Few-shot Semi-supervised Learning

Higher-order Structure Based Anomaly Detection on Attributed Networks

FRAUDRE: Fraud Detection Dual-Resistant to Graph Inconsistency and Imbalance

Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning

VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization

An Empirical Study of Graph Contrastive Learning

A Synergistic Approach for Graph Anomaly Detection With Pattern Mining and Feature Learning

Decoupling Representation Learning and Classification for GNN-based Anomaly Detection

A Comprehensive Survey on Graph Anomaly Detection With Deep Learning

Training Graph Neural Networks with 1000 Layers

Unveiling Anomalous Nodes Via Random Sampling and Consensus on Graphs

Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning

Few-shot Network Anomaly Detection via Cross-network Meta-learning

Therapeutics Data Commons: Machine Learning Datasets and Tasks for Drug Discovery and Development

On Using Classification Datasets to Evaluate Graph Outlier Detection: Peculiar Observations and New Insights

A Large-Scale Database for Graph Representation Learning

Generative Adversarial Attributed Network Anomaly Detection

Error-Bounded Graph Anomaly Loss for GNNs

TODS: An Automated Time Series Outlier Detection System

Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters

Next-item Recommendation with Sequential Hypergraphs

DATE: Dual Attentive Tree-aware Embedding for Customs Fraud Detection

Inductive Anomaly Detection on Attributed Networks

Policy-GNN: Aggregation Optimization for Graph Neural Networks

Open Graph Benchmark: Datasets for Machine Learning on Graphs

Benchmarking Unsupervised Outlier Detection with Realistic Synthetic Data

Detecting Sensor Faults, Anomalies and Outliers in the Internet of Things: A Survey on the Challenges and Solutions

Improving the Accuracy, Scalability, and Performance of Graph Neural Networks with Roc

One-class graph neural networks for anomaly detection in attributed networks

Anomalydae: Dual Autoencoder for Anomaly Detection on Attributed Networks

Can graph neural networks count substructures?

POLITICAL DISCOURSE CONTENT ANALYSIS: A CRITICAL OVERVIEW OF A COMPUTERIZED TEXT ANALYSIS PROGRAM LINGUISTIC INQUIRY AND WORD COUNT (LIWC)

Outlier Resistant Unsupervised Deep Architectures for Attributed Network Embedding

Uncovering Coordinated Networks on Social Media

Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View

AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN

Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics

Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks

Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach

GraphSAINT: Graph Sampling Based Inductive Learning Method

Deep Anomaly Detection on Attributed Networks

PyOD: A Python Toolbox for Scalable Outlier Detection

LSCP: Locally Selective Combination in Parallel Outlier Ensembles

Outlier Aware Network Embedding for Attributed Networks

Pitfalls of Graph Neural Network Evaluation

Deep Structure Learning for Fraud Detection

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

REV2: Fraudulent User Prediction in Rating Platforms

Radar: Residual Analysis for Anomaly Detection in Attributed Networks

Anomaly Detection with Robust Deep Autoencoders

Variational Graph Auto-Encoders

Semi-Supervised Classification with Graph Convolutional Networks

FRAUDAR: Bounding Graph Fraud in the Face of Camouflage

On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study

Discovering Opinion Spammer Groups by Network Footprints

Collective Opinion Spam Detection: Bridging Review Networks and Metadata

Image-Based Recommendations on Styles and Substitutes

A Meta-Analysis of the Anomaly Detection Problem

Anomaly Detection Using Autoencoders with Nonlinear Dimensionality Reduction

Graph based anomaly detection and description: a survey

Auto-Encoding Variational Bayes

Statistical Selection of Congruent Subspaces for Mining Attributed Graphs

Ranking outlier nodes in subspaces of attributed graphs

Isolation-Based Anomaly Detection

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

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

NUS-WIDE: a real-world web image database from National University of Singapore

Collective Classification in Network Data

SCAN: a structural clustering algorithm for networks

Clustering in complex directed networks.

Statistical Comparisons of Classifiers over Multiple Data Sets

The dynamics of viral marketing

A (sub)graph isomorphism algorithm for matching large graphs

AutoPart: Parameter-Free Graph Partitioning and Outlier Detection

The Enron Corpus: A New Dataset for Email Classification Research

LOF: identifying density-based local outliers

Contrastive Attributed Network Anomaly Detection with Data Augmentation

AutoGML: Fast Automatic Model Selection for Graph Machine Learning

Towards Unsupervised HPO for Outlier Detection

TOD : T ENSOR -B ASED O UTLIER D ETECTION , A G ENERAL GPU-A CCELERATED F RAMEWORK

Automatic Unsupervised Outlier Model Selection

Revisiting Time Series Outlier Detection: Definitions and Benchmarks

SUOD: Accelerating Large-Scale Unsupervised Heterogeneous Outlier Detection

Count-gnn: Graph neural networks for subgraph isomorphism counting

Outlier Detection with Autoencoder Ensembles

Исследование влияния пола и психологических характеристик автора на количественные параметры его текста с использованием программы Linguistic Inquiry and Word Count

An Introduction to Outlier Analysis

Collective Classi!cation in Network Data

100

Linguistic Inquiry and Word Count (LIWC2007)

101

Evaluation of both detection quality and computational efﬁciency

102

Extending the scope from static attribute outlier node detection to more graph tasks, e.g., outlier detection in edges and sub-graphs. This will lead to other interesting aspects of graph OD

103

Monitoring and adding outlier node methods to PyGOD for both benchmark and general usage

104

Incorporating automated machine learning to enable intelligent model selection and hyperparameter tuning [59, 93], which may unlock some interesting perspectives of graph OD

105

In the long term, we envision PyGOD could keep evolving to support more comprehensive benchmarking, as well as other graph detection tasks and benchmarks

106

Optimizing its accessibility and scalability with the latest development in graph learning [35], which may bring us new insights into outlier node detection's scalability