PaperlayerView exact revision on arXiv

Source-linked AI summary

GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detection

Jianheng Tang, Fengrui Hua, Ziqi Gao, Peilin Zhao, Jia Li

arXiv:2306.12251v2cs.LG

TL;DR

Supervised GAD lacks a comprehensive benchmark, and comparisons between tree ensembles and GNNs and evaluations on large graphs remain limited. GADBench evaluates models across real-world datasets and supervised settings. Its experiments find that tree ensembles with neighborhood aggregation generally outperform GNNs designed for GAD.

  • Problem

    Comprehensive evidence comparing supervised GAD models, including tree ensembles and GNNs and performance on large graphs, is limited.

    Source: §1 · p. 1

  • Method

    GADBench compares 29 models on 10 real-world datasets in semi-supervised and fully supervised settings.

    Source: §1 · p. 2

  • Results

    Tree ensembles with simple neighborhood aggregation generally outperform other models, including GNNs designed for GAD.

    Source: §5 · p. 10

  • Takeaways & Limitations

    The results underscore the importance of fair, comprehensive comparisons for understanding model capabilities in GAD.

    Source: §5 · p. 10

    The benchmark primarily treats datasets as static graphs; heterogeneous and inductive settings have only received preliminary study.

    Source: §5 · p. 10

Abstract

from arXiv · show

With a long history of traditional Graph Anomaly Detection (GAD) algorithms and recently popular Graph Neural Networks (GNNs), it is still not clear (1) how they perform under a standard comprehensive setting, (2) whether GNNs can outperform traditional algorithms such as tree ensembles, and (3) how about their efficiency on large-scale graphs. In response, we introduce GADBench -- a benchmark tool dedicated to supervised anomalous node detection in static graphs. GADBench facilitates a detailed comparison across 29 distinct models on ten real-world GAD datasets, encompassing thousands to millions ($\sim$6M) nodes. Our main finding is that tree ensembles with simple neighborhood aggregation can outperform the latest GNNs tailored for the GAD task. We shed light on the current progress of GAD, setting a robust groundwork for subsequent investigations in this domain. GADBench is open-sourced at https://github.com/squareRoot3/GADBench.

1 Introduction

The introduction identifies gaps in supervised GAD benchmarking, comparisons between tree ensembles and GNNs, and evaluations on large graphs. GADBench addresses these gaps with a broad evaluation and finds that tree ensembles with neighborhood aggregation perform especially well.

Motivation

  • The paper identifies three evaluation gaps: no comprehensive supervised GAD benchmark, no systematic tree-ensemble–GNN comparison, and limited exploration of large graphs.The latest GAD benchmark available to the authors, BOND, evaluates only unsupervised methods, despite many models relying on labels.Source: §1 · pp. 1–2

Benchmark scope

  • GADBench evaluates 29 models on 10 real-world datasets in semi-supervised and fully supervised settings, with and without hyperparameter tuning.The evaluation includes non-graph models, standard GNNs, GAD-specific GNNs, and tree ensembles with simple neighborhood aggregation.Source: §1 · p. 2

Findings

  • Tree ensembles with neighbor aggregation achieve superior performance among the evaluated models, while most standard GNNs are unsuitable for GAD and GAD-specific GNNs need tuning.The findings are reported from experiments across the benchmark.Source: §1 · p. 2

Contributions

  • The benchmark standardizes dataset selection, metrics, model training, and hyperparameter tuning, and makes its models, datasets, and protocols openly available.The repository is intended to support reproducibility and evaluation of additional datasets and models.Source: §1 · p. 2

2 Preliminaries and Related Work

The paper defines its task as detecting anomalous nodes in a static attributed graph using labeled nodes. It reviews classical methods, GNN adaptations, and tree ensembles, emphasizing challenges that motivate its benchmark and models.

Task definition

  • Given a subset of labeled nodes in a static attributed graph, the task is to classify the remaining nodes as normal or anomalous.The graph is represented by nodes, an adjacency matrix, and node features.Source: §2 · p. 2

GAD challenges

  • GAD poses challenges from class imbalance, connected nodes with differing features and labels, and anomalies that mimic normal features and connections.These challenges affect training and neighborhood message passing.Source: §2 · p. 3

Classical methods

  • Classical approaches use graph patterns and learning methods, but most are designed for plain graphs and make limited use of node labels.Examples include statistical patterns, community structure, egonets, spectral analysis, random walks, residual and relational learning, and Bayesian models.Source: §2 · p. 3

GNNs for GAD

  • GAD-specific GNNs adapt message passing, aggregation, sampling, or spectral filters to address camouflage, heterophily, and imbalance.Examples include camouflage-resistant aggregation, imbalance-aware sampling, and frequency-based approaches.Source: §2 · p. 3

Ensemble models

  • The paper combines tree ensembles with parameter-free neighborhood aggregation to use both structural and feature information for GAD.It presents this straightforward combination as a way to revisit tree ensembles’ potential to outperform GNNs.Source: §2 · p. 3

3 The Setup of GADBench

GADBench evaluates 29 models on 10 real-world datasets, selected for organic anomalies, domain diversity, scale, and anomaly prevalence. Its protocols cover supervised settings, performance metrics, resource use, and hyperparameter tuning.

3.1 Benchmark Models

  • The benchmark groups 29 models across classical methods, standard and specialized GNNs, and tree ensembles with neighbor aggregation.The tree ensemble variants use parameter-free aggregation and feed aggregated node features to Random Forest or XGBoost.Source: §3.1 · p. 4

3.2 Benchmark Datasets

  • The 10 datasets contain naturally occurring anomalies, span several application domains and graph sizes, and each has more than 100 anomalies with an anomaly ratio no greater than 25%.Datasets with fewer than 5,000 nodes and the Enron dataset were excluded under the selection criteria.Source: §3.2 · p. 5, Table 3 · p. 5

3.3 Other Details

  • Evaluation includes fully supervised splits and a semi-supervised set of 100 labels per dataset, averaged over ten random splits.The semi-supervised labels comprise 20 anomalous and 80 normal nodes; metrics include AUROC, AUPRC, and Rec@K, alongside running time and memory consumption.Source: §3.3 · pp. 5–6
  • To compare default performance with tuned performance, the benchmark uses original-paper defaults and random search over predefined hyperparameter spaces.A random set of hyperparameters is selected for each model during one trial on each dataset.Source: §3.3 · p. 6

4 Experimental Results

Across the benchmark comparisons, tree ensembles with neighbor aggregation generally outperform GNNs and are more efficient, while results vary with tuning, evaluation setting, and feature type. The experiments also examine aggregation depth and decision-boundary differences that help characterize these comparisons.

4.1 Overall Comparison

  • Most standard GNNs remain subpar after tuning; GraphSAGE is an exception, improving average AUPRC by 10.4% with optimal hyperparameters.GCN and GIN perform on par with MLP, while BGNN varies across datasets.Source: §4.1 · p. 6, Table 4 · p. 8
  • With default hyperparameters, XGB-Graph exceeds BWGNN by 2.0% AUROC, 12.9% AUPRC, and 9.8% Rec@K in fully supervised evaluation.Figure 1 compares model performance, wall-clock time, and DGraph-Fin memory use.Source: §4.1 · p. 6, Figure 1 · p. 7
  • With defaults, RF-Graph exceeds GHRN by 2.8% AUROC, 8.0% AUPRC, and 3.1% Rec@K semi-supervised, while tree ensembles also use less time and memory.After tuning, RF-Graph and XGB-Graph still prevail on 6 of 10 datasets.Source: §4.1 · p. 6, Figure 1 · p. 7, Table 4 · p. 8
  • Specialized GNN performance strongly depends on tuning: optimized BWGNN can surpass RF-Graph and XGB-Graph on Reddit, but specialized GNNs often require more time and memory.All specialized GNNs improve after a hyperparameter search.Source: §4.1 · pp. 6–7, Figure 1 · p. 7
  • Applying neighborhood aggregation to XGBoost raises semi-supervised average AUPRC across 10 datasets from 37.5% to 38.9%, with no significant boost in the fully supervised setting.The authors identify neighborhood aggregation as a potential strategy for label scarcity.Source: §4.1 · p. 8

4.2 Specialized Experiments in Heterogeneous and Inductive Settings

  • Considering edge heterogeneity does not improve Amazon results but improves Yelp results; CARE-GNN outperforms the others under label-scarce conditions.In inductive evaluation, XGB-Graph leads across metrics on Elliptic, while GHRN is most robust on DGraph-Fin.Source: Table 5 · p. 8, §4.2 · p. 9, Table 6 · p. 9
  • Increasing aggregation layers from zero to two improves performance on most datasets, while additional layers bring no significant gains and may add computational and memory overhead.Two layers are adequate in most instances for XGB-Graph and RF-Graph.Source: §4.2 · p. 9, Figure 2 · p. 9

4.3 Why and When Do Tree Ensembles with Neighbor Aggregation Outperform GNNs?

  • On Amazon, RF-Graph’s more intricate boundaries distinguish intertwined normal and anomalous nodes better than GIN’s smoother boundaries; on Weibo, XGB-Graph classifies dispersed anomaly clusters that challenge BWGNN.The authors connect these examples to tree ensembles’ complex, disjoint boundaries and GNNs’ typically simple, continuous boundaries.Source: §4.3 · pp. 9–10, Figure 3 · p. 10

5 Conclusion and Future Plan

GADBench’s evaluation finds that tree ensembles with simple neighborhood aggregation generally outperform other tested models, including GAD-specific GNNs. The benchmark currently focuses on static graphs, with heterogeneous and inductive settings studied only preliminarily.

5 Conclusion and Future Plan

  • Across 29 models and 10 real-world datasets, tree ensembles with simple neighborhood aggregation generally outperform other models, including GNNs designed for GAD.The authors examine this finding through decision boundaries and node feature types.Source: §5 · p. 10
  • The authors make GADBench open-source to foster further research, algorithm refinement, and more informed evaluations and comparisons.They describe it as a long-term project intended to evolve into a more robust and scalable GAD toolbox.Source: §5 · p. 10
  • GADBench focuses on static graphs for compatibility with most baselines, while heterogeneous and inductive settings have only preliminary studies.Future plans include broader GAD scenarios, newer models and datasets, and more complex graphs and anomalies.Source: §5 · p. 10

Classic Methods

The classic-methods catalog covers conventional feature-based learners, tree ensembles, and outlier-scoring approaches. It also describes neighborhood averaging as a post-processing technique and its use in a BWGNN case study.

Classic Methods

  • The catalog includes MLP, KNN, SVM, Random Forest, and XGBoost as classic methods for prediction or classification.Random Forest combines tree predictions by averaging or voting, while XGBoost iteratively adds trees to correct earlier errors.Source: Classic Methods · p. 17
  • XGBOD combines unsupervised outlier-detector scores with original features and uses an XGBoost classifier for outlier detection.The generated abnormality scores are appended as additional features.Source: Classic Methods · p. 17
  • Neighborhood Averaging post-processes an outlier detector’s scores by averaging them with scores of neighbors in feature space.GADBench integrates the technique into BWGNN as a case study.Source: Classic Methods · p. 17

Standard GNN Architectures

The benchmark catalog includes general-purpose GNN architectures and models adapted to graph anomaly detection. The specialized methods address challenges such as imbalance, heterophily, camouflage, and frequency characteristics.

Standard GNN Architectures

  • Standard architectures include GCN, ChebNet, GIN, GraphSAGE, GAT, Graph Transformer, PNA, BGNN, RGCN, and HGT.Their designs span neighborhood aggregation, spectral convolution, attention, joint tree-and-GNN training, and heterogeneous graphs.Source: Standard GNN Architectures · p. 17

GNNs Specialized for Graph Anomaly Detection

  • Specialized methods include GAS, DCI, PC-GNN, BernNet, GAT-sep, and AMNet, with designs targeting spam detection, representation learning, imbalance, heterophily, and graph signals.PC-GNN uses label-balanced sampling and learnable neighbor selection; GAT-sep separates ego and neighbor embeddings.Source: GNNs Specialized for Graph Anomaly… · p. 18
  • Other specialized models include BWGNN and GHRN for frequency and heterophily issues, plus CARE-GNN and H2-FDetector for fraud-related graph settings.BWGNN uses flexible filters to address high-frequency anomalies; GHRN prunes inter-class edges, while CARE-GNN targets camouflage and H2-FDetector models homophilic and heterophilic interactions.Source: GNNs Specialized for Graph Anomaly… · p. 18

B Detailed Description of Datasets in GADBench

The dataset descriptions cover varied graph domains, node types, features, and anomaly or prediction targets. The accompanying table is specified as an overview of datasets, feature types, dimensions, and descriptions.

B Detailed Description of Datasets in GADBench

  • Reddit is a user-subreddit graph with verified banned-user labels and 672,447 interactions, using LIWC text-category features.It covers one month of posts and focuses on 1,000 active subreddits and 10,000 engaged users.Source: B Detailed Description of Datasets in… · p. 18
  • Weibo links users to hashtags; users with at least five qualifying rapid-post activities are labeled suspicious.The graph has 8,405 users and 61,964 hashtags; features include post location and bag-of-words.Source: B Detailed Description of Datasets in… · p. 18
  • YelpChi targets reviews that unfairly promote or demote businesses, with edges linking shared reviewers, products and ratings, or product-month reviews.Source: B Detailed Description of Datasets in… · p. 18
  • Amazon targets paid fake-review writers in Musical Instruments and represents user relations through shared products, ratings, and review similarity.Source: B Detailed Description of Datasets in… · pp. 18–19
  • The dataset table lists each dataset’s node feature type, feature dimension, and detailed description.Source: Table 7 · p. 19
  • T-Finance and T-Social use expert-labeled anomalies such as fraud, money laundering, and online gambling; their edges represent transactions and sustained friendships, respectively.T-Finance nodes have 10-dimensional account features; T-Social shares T-Finance annotations and features.Source: B Detailed Description of Datasets in… · p. 19
  • Tolokers predicts which crowd workers were banned, while Questions predicts which medicine-topic users remained active at period end.Tolokers connects workers who performed the same task; Questions connects users through answer interactions and uses mean FastText description embeddings.Source: B Detailed Description of Datasets in… · p. 19
  • Elliptic maps Bitcoin transactions to licit or illicit entities, while DGraph-Fin represents financial users and emergency-contact links, with overdue behavior labeled anomalous.Elliptic has over 200,000 transaction nodes, 234,000 directed payment flows, and 166 features; DGraph-Fin has over 3 million nodes and 4 million dynamic edges.Source: B Detailed Description of Datasets in… · p. 19

C.1 Metrics

The section defines classification metrics for ranking anomaly predictions and reports runtime and peak memory to characterize model efficiency.

C.1 Metrics

  • AUPRC summarizes the precision–recall curve as a weighted mean of precision across thresholds, using recall increases as weights.Precision is the share of positive predictions that are true positives; recall is the share of positive labels that are true positives.Source: §C.1 · pp. 19–20
  • AUROC measures discrimination through the area under the ROC curve, which plots true-positive rate against false-positive rate across thresholds.A score of 1 indicates perfect discrimination, while 0.5 corresponds to random guessing.Source: §C.1 · p. 20
  • Rec@K measures recall among the top-ranked predictions, with k set to the number of actual test outliers.In this setting, Rec@K is equivalent to precision at k and F1 score at k.Source: §C.1 · p. 20
  • Runtime is measured from experiment start to completion and does not distinguish CPU from GPU computation time.Source: §C.1 · p. 20
  • Peak CPU and GPU memory are recorded during supervised training on DGraph-Fin to assess resource requirements.Source: §C.1 · p. 20

C.2 Additional Experimental Details

The experimental details describe GADBench’s software stack, model implementations, tuning procedure, hardware, and extension interface.

C.2 Additional Experimental Details

  • GADBench is built on PyTorch 1.12 and DGL 1.0, with GNNs implemented in DGL and classic models integrated from their respective libraries.KNN, SVM, and RF use Scikit-Learn; XGBoost uses its official implementation, and XGBOD uses PyOD.Source: §C.2 · p. 20
  • Experiments ran on a Linux server with an AMD EPYC 75F3 32-Core CPU, 64GB RAM, and an NVIDIA RTX A6000 GPU with 48G memory.Source: §C.2 · p. 20
  • Random search selects the configuration with the best validation AUPRC, but RGCN, CARE-GNN, and H2-FDetector were not tuned because of limited data.Source: §C.2 · p. 20
  • The toolkit accepts DGL graphs with binary node labels and models that output node anomaly scores, and the authors plan to add models and datasets.Source: §C.2 · p. 20

D Additional Experimental Results

Additional experiments examine neighborhood averaging across supervised settings and provide model comparisons under default and tuned hyperparameters.

D Additional Experimental Results

  • Tables 11 and 12 report each model’s performance under semi-supervised and fully supervised settings, respectively, using default hyperparameters; Table 13 presents per-dataset AUROC and Rec@K after hyperparameter tuning.Table 13 consolidates information from Table 4.Source: D Additional Experimental Results · p. 20
  • Figure 4 complements Figure 3 with further decision-boundary examples, using blue and red for anomalous and normal points and predicted regions.Source: Figure 4 · p. 21
  • In the semi-supervised setting, neighborhood averaging improves the four evaluated methods’ AUPRC by 1.4%–3.7%, while fully supervised effects vary by baseline.In the fully supervised setting, it helps weaker GIN, leaves BWGNN similar, and may reduce XGB-Graph and RF-Graph performance.Source: D Additional Experimental Results · pp. 20–21

E More Details About Plotting Decision Boundaries

The section compares tree-based and neural decision boundaries on learned node embeddings and documents related hyperparameter and performance tables.

E More Details About Plotting Decision Boundaries

  • GIN’s t-SNE embeddings intertwine normal and anomalous nodes, and its smooth boundaries misclassify normal nodes; XGBoost forms more intricate boundaries.The comparison approximates GIN versus RF-Graph by classifying GIN embeddings with an MLP and Random Forest.Source: E More Details About Plotting Decision… · p. 21
  • On Weibo, BWGNN embeddings form dispersed anomaly clusters that an MLP struggles to separate, while XGBoost classifies them successfully; similar observations hold on T-Finance and Tolokers.Source: E More Details About Plotting Decision… · p. 21
  • Tables 8 and 9 provide default hyperparameters and random-search spaces for MLP/GNN models and non-deep-learning models, respectively.Source: Table 8 · p. 22, Table 9 · p. 23
  • Tables 10–13 cover neighborhood-averaging effects, default semi- and fully supervised metrics, and tuned AUROC and Rec@K results.Table 13 averages the first nine datasets, excluding T-Social; out-of-time indicates random search did not finish within a day.Source: Table 10 · p. 23, Table 11 · p. 24, Table 12 · p. 25
Loading 2306.12251v2…