DAGAD: Data Augmentation for Graph Anomaly Detection

Fanzhen Liu, Xiaoxiao Ma, Jia Wu, Shan Xue, Amin Beheshti, Chuan Zhou, Hao Peng, Quan Z. Sheng, Charu C. Aggarwal

Abstract

Graph Anomaly Detection (GAD) is a critical task in identifying rare, malicious, or unusual entities within complex networks. However, the field faces two significant hurdles: the extreme scarcity of labeled anomalous samples and the overwhelming prevalence of normal nodes, which leads to severe class imbalance. This paper introduces DAGAD (Data Augmentation-based Graph Anomaly Detection), a novel framework designed to overcome these challenges. By generating synthetic training samples in the embedding space and employing a specialized complementary learning strategy, DAGAD effectively identifies "needles in a haystack" that traditional Graph Neural Networks (GNNs) often miss. Experimental results on real-world benchmarks show that DAGAD achieves a minimum 19% improvement in recall over state-of-the-art baselines.

Introduction

In real-world networks—ranging from social media platforms to financial transaction webs—anomalies often represent high-stakes events like fraud, cyberattacks, or system failures. Detecting these nodes is difficult because anomalies are rare by definition, making it expensive and often impossible to acquire large labeled datasets. Furthermore, standard GNNs are prone to "majority class bias," where the model achieves high overall accuracy by simply predicting all nodes as benign, failing to catch the critical anomalies.

Existing unsupervised methods typically rely on reconstruction errors, assuming anomalies will not fit the general pattern of the graph. However, these methods fail to leverage the valuable, albeit limited, knowledge provided by known labeled anomalies. DAGAD bridges this gap by using data augmentation to enrich the training set and a tailored learning module to handle class imbalance.

The DAGAD Framework

The DAGAD framework is composed of three integrated modules designed to extract maximum signal from limited data:

1. Information Fusion Module

To capture the complexity of graph data, DAGAD utilizes two GNN encoders (supporting both Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT)). These encoders map node attributes and local graph topology into low-dimensional embeddings, ensuring that both structural and feature-based information are preserved.

2. Graph Data Augmentation Module

Rather than manipulating the raw graph structure—which is computationally expensive and risks destroying essential patterns—DAGAD performs augmentation in the embedding space. It generates synthetic "pseudo-anomalies" by concatenating original representations with permuted ones. This process creates a richer variety of training samples, helping the model learn more robust and discriminative decision boundaries.

3. Imbalance-Tailored Learning Module

This module employs a "complementary learning" setup using two classifiers:

  • Classifier $C_a$: This classifier is intentionally encouraged to "overfit" on the few known anomalies using standard Cross Entropy loss. It acts as an expert on the rare class.
  • Classifier $C_b$: The final detector, which uses a Generalized Cross Entropy (GCE) loss and trains on both original and augmented samples.
  • Dynamic Weighting: A weighting mechanism ($\omega$) allows $C_a$ to guide $C_b$, distilling high-signal features into the main detector and preventing it from falling into the majority class bias trap.

Experimental Evaluation

The authors evaluated DAGAD on three widely used real-world attributed graph benchmarks: BlogCatalog (social network), ACM (citation network), and Flickr (image-sharing network). To simulate real-world conditions, the authors used a 20/80 split for training and testing, maintaining the naturally low proportion of anomalies.

Key Results

DAGAD was compared against 10 state-of-the-art baselines, including DOMINANT, AnomalyDAE, and OCGNN. The results highlight several strengths:

  • Superior Recall: DAGAD achieved at least a 19% improvement in Recall across all datasets, demonstrating a significantly higher capability for catching "bad actors."
  • Robust F1-Scores: On the BlogCatalog dataset, DAGAD-GCN achieved a Macro-F1 of 0.8400, nearly doubling the performance of several popular deep learning baselines.
  • Ablation Success: Removing either the augmentation module or the imbalance-tailored loss led to a massive performance drop (e.g., F1-score dropping from ~0.84 to ~0.17 on BlogCatalog), confirming that both components are essential to the framework's success.

Discussion and Insights

DAGAD demonstrates that augmentation in the embedding space is more efficient and controllable than raw graph manipulation. Furthermore, the concept of "sacrificial overfitting" proves powerful; by letting one classifier focus exclusively on rare anomalies, the system can extract discriminative features that a balanced classifier would ignore. Finally, the paper reinforces that class-wise loss weighting is non-negotiable in imbalanced tasks, as it ensures the model treats the identification of a single anomaly as more valuable than the identification of a single normal node.

Limitations and Future Work

Despite its success, DAGAD has areas for further refinement. On the ACM dataset, a baseline called DONE achieved a slightly higher AUC, suggesting that DAGAD could benefit from more sophisticated structural and attribute reconstruction objectives. Additionally, the model's sensitivity to hyper-parameters ($\alpha$ and $\beta$) remains a challenge for deployment in new, unlabeled domains. Future work may also focus on optimizing the GNN encoding phase to improve scalability for extremely large-scale graphs with billions of edges.

Summary updated

BibTeX
@inproceedings{liu2022dagad,
  author = {Fanzhen Liu and Xiaoxiao Ma and Jia Wu and Jian Yang and Shan Xue and Amin Beheshti and Chuan Zhou and Hao Peng and Quan Z. Sheng and Charu C. Aggarwal},
  title = {{DAGAD: Data Augmentation for Graph Anomaly Detection}},
  booktitle = {22nd IEEE International Conference on Data Mining ICDM},
  year = {2022},
  url = {https://openreview.net/forum?id=Q9WTzwXxgN},
}
Figure