PaperlayerView exact revision on arXiv

Source-linked AI summary

BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs

Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, Lichao Sun, Jundong Li, George H. Chen, Zhihao Jia, Philip S. Yu

arXiv:2206.10071v2cs.LGcs.SI

TL;DR

Graph outlier detection lacks a standard comprehensive evaluation setting despite many proposed algorithms, making broad comparisons difficult. BOND addresses this gap by benchmarking 14 methods across synthetic and organic outliers, datasets, and computational costs, finding substantial performance variation without a universal winner.

  • Problem

    Graph outlier detection lacks a comprehensive benchmark spanning algorithms, datasets, and diverse outlier types, limiting broad performance evaluation.

  • Method

    BOND benchmarks 14 representative methods on nine real datasets, evaluates synthetic and organic outliers, measures detection and computational efficiency, and provides an extensible toolkit.

  • Results

    Substantial detection-performance differences occur across algorithms, with no method universally best across datasets and settings.

  • Takeaways & Limitations

    BOND provides an accessible, extensible basis for comparing graph outlier detectors and studying their performance across outlier types and computational constraints.

  • Takeaways & Limitations

    Organic outliers may mix structural and contextual properties or fit neither type, making them more difficult to detect than patterned synthetic outliers.

Abstract

from arXiv · show

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

1 Introduction

The paper introduces BOND as a comprehensive benchmark for unsupervised outlier node detection on static attributed graphs, addressing limited evaluation across algorithms, datasets, and outlier types. It defines OND as assigning outlier scores to graph nodes without ground-truth labels and evaluates diverse methods through an extensible toolkit.

  • Motivation: Graph outlier detection identifies anomalous nodes and supports applications including spammer detection, sensor fault detection, fraudster identification, and defense against graph attacks.Unlike tabular or time-series detection, graph OD must use both graph structure and node information.
  • Motivation: Existing graph OD research lacks a comprehensive benchmark, limiting understanding of how algorithmic results generalize across settings and outlier definitions.Generalization is further complicated because applications can define outliers differently, sometimes unclearly.
  • Problem Definition: OND assigns every node in a static attributed graph a real-valued outlier score and selects the k highest-scoring nodes without using ground-truth outlier labels.The graph comprises vertices, edges, and a node attribute matrix.
  • Benchmark: BOND evaluates 14 representative OD methods across nine benchmark datasets, covering classical and deep approaches and comparing their strengths and weaknesses.Its implementation includes graph and non-graph methods through the extensible PyGOD library.
  • Benchmark: The benchmark separately examines synthetic and organic outliers, structural and contextual outliers, detection effectiveness, running time, and GPU memory consumption.Its code is freely available and designed for extension with additional algorithms.

2 Related Work

Prior work spans classical graph-feature methods, learning-based detectors, autoencoders, graph neural networks, and generative adversarial networks. BOND incorporates a diverse set of these approaches, including non-graph baselines, to support comparative evaluation.

  • Classical Methods: Classical node outlier detectors use graph-based features such as centrality measures and clustering coefficients to identify anomalous nodes.Learning-based methods seek to encode graph information more flexibly than hand-crafted features.
  • Deep Methods: Autoencoders detect outliers by learning encodings that reconstruct the original data, making them a common deep-learning approach for node outlier detection.The related work describes autoencoders as neural architectures built around reconstruction from learned encodings.
  • Deep Methods: Graph neural networks learn node representations from attributes and graph structure, and these representations are used to capture patterns relevant to outlier detection.The paper notes that GNNs have become popular for graph outlier detection.
  • Deep Methods: Generative adversarial networks can identify outliers as data points judged more fake by a discriminator trained against generated data.GANs jointly learn a generator and discriminator for distinguishing real and generated data.
  • Benchmark Coverage: BOND implements nine diverse deep detectors and also includes non-graph and classical methods for broader comparison.The benchmark’s algorithm selection spans graph use, neural-network use, publication year, and methodological core.

3 BOND

BOND organizes graph outlier detection around structural and contextual outliers, then benchmarks diverse algorithms across synthetic and organic datasets using quality and efficiency measures.

  • 3.1 Outlier Types: BOND groups graph outliers into structural outliers, which are densely connected relative to sparsely connected regular nodes, and contextual outliers, whose attributes differ from neighboring nodes.
  • 3.1 Outlier Types: Global outliers differing from all other nodes are excluded because detecting them does not require graph structure and can use tabular outlier detectors.
  • 3.1 Outlier Types: Organic outliers may be neither structural nor contextual, or may combine both types, making them harder to detect than synthetic pattern-based outliers.
  • 3.2 Datasets: BOND uses three datasets with injected synthetic outliers, six datasets containing organic outliers, and randomly generated graph data for scalability evaluation.
  • 3.3 Algorithms: The benchmark evaluates 14 diverse algorithms, spanning graph and non-graph methods, classical and deep approaches, and several GNN-based detectors.
  • 3.4 Evaluation Metrics: Detection quality is measured with ROC-AUC, Average Precision, and Recall@k, while efficiency is measured using wall-clock time and GPU memory consumption.

4 Experiments

BOND evaluates outlier node detection across synthetic and organic outliers, method categories, outlier types, and computational costs. Results show no universally best detector, strong dependence on outlier structure and graph size, and trade-offs between accuracy, stability, time, and memory.

  • Experimental design: BOND evaluates algorithms on synthetic and organic outliers, compares structural and contextual cases, and measures time and GPU memory efficiency.The benchmark uses nine real datasets and generated graphs, with ROC-AUC, average performance, stability, and potential reported under a common evaluation setup.
  • Synthetic and organic outliers: No method is universally best: only three of 14 methods achieve the best average ROC-AUC on two datasets, while DONE reaches 2.06× LOF’s average ROC-AUC on Flickr.Classical methods lead on some organic datasets but underperform many deep methods on synthetic outliers.
  • Synthetic and organic outliers: Most methods fail on organic outliers when abnormalities do not match structural or contextual patterns, whereas non-graph methods perform better on Reddit and DGraph.Weibo outliers exhibit both structural and contextual properties, while Reddit and DGraph abnormalities rely more on domain knowledge.
  • Synthetic and organic outliers: Deep learning and SGD-based methods may be sub-optimal on small graphs because limited data can hinder representation learning and increase overfitting risk.Classical Radar and ANOMALOUS also perform poorly on Disney and Books, where SGD may be problematic.
  • Structural and contextual outliers: Structural reconstruction matters for GNN detection: DOMINANT exceeds GCNAE by over 40% on structural outliers, while one-hop information can match four-hop aggregation at about 92% ROC-AUC.DOMINANT’s structural decoder reconstructs graph adjacency, whereas DONE encodes only one-hop neighbors.
  • Structural and contextual outliers: No method reaches 85% detection AUC on both structural and contextual outliers, indicating that fixed combinations of structural and contextual losses struggle to balance the two types.The benchmark identifies consistent detection across both outlier types as an open problem.
  • Computational efficiency: Classical methods run faster, while GCNAE and GUIDE use less GPU memory as graphs grow; deep models offer minibatch and distributed-training flexibility.GUIDE shifts cost to CPU time and RAM for motif extraction, whereas GCNAE benefits from a simpler architecture.

5 Discussion

BOND establishes a broad benchmark for unsupervised outlier node detection and uses its findings to identify practical limitations and future research directions. The discussion emphasizes type-aware detection, more realistic outliers, stability, scalability, model selection, and broader task coverage.

  • Discussion: BOND evaluates algorithms across synthetic and organic, structural and contextual outliers, and computational efficiency.The benchmark is designed to compare diverse OD algorithms across detection settings and resource demands.
  • Future directions: Unsupervised model selection is difficult because algorithm performance and hyperparameter sensitivity vary across datasets.The benchmark reports no universal winner and notes that AnomalyDAE performance on Weibo varies by as much as 14% across hyperparameters.
  • Future directions: Algorithm choice depends heavily on outlier type, motivating type-aware detectors when the expected outlier type is known.MLPAE and GCNAE are cited as examples for contextual outliers.
  • Future directions: Organic outliers can combine multiple types, and their detection performance differs substantially from synthetic outliers.The discussion calls for more realistic outlier-generation approaches, including perturbing generative models fitted to normal samples.
  • Future directions: Scalability remains a major challenge: most tested algorithms ran out of memory on the million-scale DGraph dataset.The paper highlights quadratic memory costs from reconstructing complete adjacency matrices and suggests scalable GNNs and more memory-efficient implementations.
  • Future directions: Future benchmarks could add meta-learning for model selection, edge-, subgraph-, and graph-level tasks, supervision, and more datasets.The paper particularly recommends more organic-outlier datasets and at least 20 datasets for statistical comparisons.

A.1 Additional Dataset Information

The benchmark combines graph datasets from citation, commerce, image, social-media, email, and financial domains. These datasets differ in graph semantics, attributes, labels, and whether outliers are synthetic or organic.

  • Datasets: Cora is a citation graph whose nodes are machine-learning papers, with sparse bag-of-words features and seven labels.
  • Datasets: Amazon is a co-purchase graph whose product nodes have bag-of-words review features and product-category labels.
  • Datasets: Flickr represents images connected by shared properties, using image-related node features from a web-image database.
  • Datasets: Weibo connects users who used the same hashtags and labels users as suspicious or benign using suspicious-event history.The dataset contains 8,405 users and 61,964 hashtags.
  • Datasets: Reddit is a user-subreddit interaction graph in which banned users are treated as outliers.It contains 168,016 interactions among extracted user and subreddit nodes.
  • Datasets: Disney and Books are Amazon co-purchase networks with product attributes and dataset-specific ground-truth labeling.Disney labels come from majority votes by high-school students, while Books labels derive from amazonfail tags.
  • Datasets: Enron represents email addresses as nodes, with spam-sending addresses treated as outliers and 20 aggregated email attributes.
  • Datasets: DGraph is a large financial-account graph with 3M nodes, 4M dynamic edges, and overdue-history labels for outliers.

A.1.2 Random Graph Generation Method

BOND uses randomly generated attributed graphs to evaluate runtime and scalability, alongside a diverse set of classical, neural, structural, and attributed OD methods. The methods differ in whether they use attributes, structure, reconstruction, clustering, adversarial training, or contrastive learning.

  • Random graph generation: Random graphs generated with fixed homophily, average degree, and feature-channel settings support runtime and scalability benchmarking.A 1,000-node graph is used for runtime testing, while multiple graph sizes are generated for scalability evaluation.
  • Outlier injection: Synthetic outlier injection targets approximately 5% of nodes, with separate parameterizations for structural and contextual outliers.Structural injection uses p = 0.2, while contextual injection sets q equal to m.
  • Baseline methods: LOF, IF, MLPAE, and SCAN provide attribute-only, tree-based, attribute-autoencoder, and structure-clustering baselines.SCAN uses graph structure alone, while LOF, IF, and MLPAE use node attributes.
  • Graph OD methods: GCNAE learns node embeddings by aggregating neighbor information and reconstructs node attributes with a GCN decoder.
  • Graph OD methods: DOMINANT, DONE, AdONE, AnomalyDAE, GAAN, GUIDE, CONAD, Radar, ANOMALOUS, and GCNAE use reconstruction, adversarial, motif, contrastive, residual, or GCN-based designs.Their outlier scores are derived from reconstruction errors, residual norms, discriminator outputs, or decoder combinations.
  • Graph OD methods: CONAD uses graph augmentation, Siamese GNN encoders, contrastive loss, and two decoders to obtain node outlier scores.

A.3 Description of Evaluation Metrics

BOND evaluates detection quality with ranking-oriented metrics and evaluates computational demands with runtime and GPU-memory measurements. The metrics emphasize class separation, precision-recall balance, and recovery of rare outliers.

  • Detection metrics: ROC-AUC measures class separation by treating outlier nodes as the positive class; 1 indicates perfect prediction and 0.5 indicates no separation.AUC is preferred over accuracy for imbalanced outlier-detection data.
  • Detection metrics: Average Precision summarizes the precision-recall curve and balances recall with precision through threshold-weighted averaging.Higher AP indicates lower false-positive and false-negative rates.
  • Detection metrics: Recall@k measures the fraction of true outliers among the top-k ranked samples, with k set to the number of ground-truth outliers.
  • Efficiency metrics: Runtime is measured from experiment start to finish without separating CPU and GPU time.
  • Efficiency metrics: GPU Memory is reported as the maximum active GPU memory used while running an algorithm.

B Additional Experimental Settings and Details

The experiments standardize implementation, hardware, hyperparameter selection, and runtime optimization across a diverse set of graph outlier detection algorithms and datasets.

  • Experimental environment: Experiments use Python 3.7, CUDA 11.1, PyTorch 1.10, PyGOD 0.3.0, and related graph-learning libraries on a Linux server with an Intel Core i5 CPU, 64GB RAM, and GTX 1080 Ti GPU.The GPU has 12GB memory.
  • Implementation: PyGOD provides more than 10 graph outlier detection algorithms with unified APIs and optimizations, alongside fairness-oriented implementation adjustments.Radar and ANOMALOUS use gradient descent instead of their official closed-form optimization, while the same optimization techniques were applied across datasets where possible.
  • Hyperparameter selection: 20 trials randomly sample candidate hyperparameter values, with mean, standard deviation, and maximum results reported.Candidate values are specified in Table 8.
  • Dataset-specific settings: Flickr uses minibatch training because full-batch training exceeds single-GPU memory, while Reddit uses smaller hidden dimensions because of its lower feature dimension.Flickr also varies batch size, sampling size, and epochs; Reddit uses reduced hidden-dimension candidates.
  • Runtime evaluation: Runtime optimization selects the ROC-AUC score achieved within as few training epochs as possible and marks an epoch optimal once subsequent score increments remain below 0.5%.The procedure balances detection performance against computational cost.

C.1 Additional Results on Real Dataset Detection Performance

Additional tables report Average Precision and Recall@k for synthetic and organic outliers across real datasets, with variability, best expected performance, maxima, and resource failures recorded.

  • Average Precision: Average Precision is compared across three datasets with synthetic outliers and six datasets with organic outliers.Results report average performance, standard deviation, and maximum performance for each algorithm; bold marks the best expected algorithm and underlining marks the per-dataset maximum.
  • Resource outcomes: The comparisons identify GPU and CPU out-of-memory cases and time-limit failures exceeding 24 hours.OOM and TLE annotations distinguish resource constraints from reported detection performance.
  • Recall@k: Recall@k is compared across three synthetic-outlier datasets and six organic-outlier datasets, with k set to the number of labeled outliers.The tables likewise report average, standard deviation, and maximum performance.

C.2 Additional Results on Performance Variation under Different Types of Outliers

The benchmark separately evaluates detection performance for contextual and structural synthetic outliers using Average Precision and Recall@k.

  • Average Precision: Average Precision is compared among algorithms on three datasets injected with contextual and structural outliers.The tables report average performance, standard deviation, and maximum performance, while marking expected and per-dataset best results.
  • Recall@k: Recall@k is evaluated on the same three datasets, with k set to the number of outliers of each type.The comparison reports average, standard deviation, and maximum performance and records out-of-memory cases.

C.3 Additional Results on Efficiency and Scalability Analysis

The efficiency analysis compares runtime and GPU memory across algorithm settings and graph sizes, while the benchmark is intended for continued dataset and algorithm development.

  • Time consumption: Runtime is compared across five epoch counts, with total runtime reported for non-iterative LOF, IF, and SCAN.The table covers time consumption in seconds.
  • Memory scalability: GPU memory consumption is compared among deep algorithms across five graph sizes measured by node count.GPU memory measurement does not apply to LOF, IF, and SCAN.
  • Future development: The authors commit to maintaining BOND and PyGOD by improving graph outlier detection datasets and algorithms.The stated development focus includes datasets and algorithms as separate areas.

D.1 Enriching Graph OD Datasets

BOND plans to expand its graph outlier-detection testbed by adding datasets, adapting existing graph datasets, and enabling deeper statistical analysis. Its roadmap also includes maintaining PyGOD, improving scalability and accessibility, and strengthening software quality and task coverage.

  • D.1 Enriching Graph OD Datasets: BOND will monitor newly published graph outlier-detection datasets and add them to the benchmark testbed.The benchmark site will be updated as new datasets become available.
  • D.1 Enriching Graph OD Datasets: Existing graph datasets could be repurposed for outlier detection by treating rare transaction classes as anomalies and common transactions as normal.
  • D.1 Enriching Graph OD Datasets: At least 20 graph outlier-detection datasets would enable more in-depth group-wise and pairwise statistical analysis.
  • D.1 Enriching Graph OD Datasets: PyGOD will add methods, improve accessibility and scalability, incorporate automated model selection and hyperparameter tuning, and extend beyond static attributed outlier detection.
  • D.1 Enriching Graph OD Datasets: PyGOD emphasizes software robustness through automated testing across Python versions and operating systems, daily tests, and at least 90% code coverage.
  • D.1 Enriching Graph OD Datasets: The long-term vision is for PyGOD to support broader benchmarking and additional graph detection tasks.
Loading 2206.10071v2…