Animate: Unsupervised Attributed Graph Anomaly Detection with Masked Graph Transformers

Jingtao Hu, Yi Zhang, Jingcan Duan, Xinwang Liu, En ZhuSSRN 2024 · DOI

TL;DR

This paper introduces ANIMATE, a novel unsupervised graph anomaly detection (UGAD) method that leverages Graph Transformers and a masked autoencoder approach. By capturing global graph structures and focusing on reconstructing normal patterns, ANIMATE effectively identifies anomalous nodes in real-world datasets, outperforming existing state-of-the-art methods.

What Problem Does This Paper Address?

Attributed graphs are increasingly used to represent complex data in various sensor networks. Identifying anomalies within these graphs, known as Unsupervised Graph Anomaly Detection (UGAD), is crucial for applications like industrial monitoring and fraud detection. Traditional methods, often based on Graph Neural Networks (GNNs), struggle with issues like local aggregation limitations and over-smoothing, which hinder their ability to capture global graph structures and effectively distinguish anomalies from normal data, especially in imbalanced datasets where anomalies are scarce. This paper aims to address these limitations by proposing a method that can better learn normal patterns and identify deviations.

Methods

The proposed method, ANIMATE, is an encoder-decoder architecture built upon Graph Transformers. Key components include:

  • Graph Transformers: Unlike GNNs with local receptive fields, Graph Transformers utilize a self-attention mechanism to capture global graph information. This allows them to consider relationships between distant nodes, which is beneficial for anomaly detection. They achieve this by computing attention weights based on feature similarity rather than fixed edges, preventing anomalies from being smoothed out by their neighbors.
  • Masked Autoencoder (MAE) Approach: ANIMATE employs a masking strategy where a portion of nodes are randomly masked. The encoder then processes the visible nodes, and the decoder attempts to reconstruct the masked nodes. This increases the difficulty of reconstruction, particularly for anomalous nodes, thereby widening the gap in reconstruction error between normal and anomalous nodes.
  • Graphormer Backbone: The encoder and decoder are based on Graphormer, which incorporates specialized positional embeddings (centrality and spatial encoding) to capture global topology and contextual information within the graph.
  • Self-Paced Enhancement (SPE): To further refine the normality model, SPE is introduced. It adaptively assigns weights to nodes based on their reconstruction loss, prioritizing the learning of normal patterns by down-weighting nodes with high reconstruction loss (potential anomalies) in subsequent iterations. This is a novel adaptation of self-paced learning for UGAD.

Datasets

The paper evaluates ANIMATE on four real-world benchmark datasets with organic anomalies:

  • Disney: A co-purchase network of movies.
  • Books: A graph of book purchases.
  • Reddit: A social network dataset.
  • Yelp: A dataset of restaurant reviews.

The authors specifically chose real-world datasets with organic anomalies to avoid potential data leakage issues associated with synthetic anomaly injection.

Key Insights and Ideas

  • Global Receptive Field is Key: The paper strongly advocates for the superiority of Graph Transformers' global receptive field over GNNs' local aggregation for UGAD. This global view is essential for understanding the overall structure and identifying deviations.
  • Masking Enhances Anomaly Discrimination: The MAE approach, by making reconstruction harder, effectively amplifies the difference in reconstruction error between normal and anomalous nodes, making anomalies easier to detect.
  • Focusing on Normality is Crucial: The core idea of UGAD is to learn what is normal and flag deviations. The SPE strategy directly implements this by adaptively focusing the model's learning on reliable normal patterns.
  • Real-World Anomalies Matter: The use of datasets with organic anomalies highlights the practical relevance of the proposed method, moving beyond synthetic benchmarks.

Key Results

ANIMATE consistently achieved the best performance across all four real-world benchmark datasets, as measured by ROC-AUC.

  • On the Books dataset, ANIMATE achieved 70.48% AUC, outperforming the second-best method by 16.11%.
  • On the Yelp dataset, ANIMATE achieved 64.30% AUC, outperforming the second-best method by 9.89%.
  • The paper also demonstrates that ANIMATE is extensible to large-scale datasets, a common challenge for Transformer-based models, due to its batch-wise processing.
  • Ablation studies showed that the Self-Paced Enhancement (SPE) module significantly improved performance, yielding gains of 0.49% to 20.19% AUC across datasets.

Limitations and Future Work

  • Parameter Sensitivity: While the paper analyzes parameter sensitivity, there's always room for further optimization of parameters like masking ratio and learning rates for specific applications.
  • Future Work: The authors suggest exploring ways to further improve the Transformer architecture for UGAD tasks, indicating ongoing research in this area. They also mention that in the future, they will explore how to further improve the architecture of Transformers for UGAD tasks.

Summary updated

BibTeX
@misc{hu2024animate,
  author = {Jingtao Hu and Yi Zhang and Jingcan Duan and Jin Hu and Xinwang Liu and En Zhu},
  title = {{Animate: Unsupervised Attributed Graph Anomaly Detection with Masked Graph Transformers}},
  year = {2024},
  doi = {10.2139/ssrn.4954429},
  howpublished = {SSRN},
}
Figure