Graph Anomaly Detection via Prototype-Aware Label Propagation (Student Abstract)

Hui Tang, Xun Liang, Sensen ZhangAAAI 2024 · DOI

TL;DR

This paper introduces LP-GAD, a novel method for detecting anomalies in attributed graphs. It tackles the challenge of limited labeled anomalies by using label propagation to generate high-quality pseudo-labels, refined by a prototype-aware strategy that leverages class distribution information. LP-GAD demonstrates superior performance compared to existing state-of-the-art methods.

What Problem Does This Paper Address?

Detecting anomalies in attributed graphs is a critical but challenging task. Anomalies can be hidden within the graph's structure, its attributes, or a combination of both. Traditional methods often struggle due to the scarcity of labeled anomalies, which are expensive and time-consuming to obtain, requiring specialized domain knowledge. While self-supervised learning (SSL) approaches can learn representations without labels, they often lack the necessary prior knowledge of abnormal samples. Semi-supervised learning (SemSL) methods, which use a few labeled anomalies, can suffer from overfitting and oversmoothing, especially when dealing with highly imbalanced datasets. A common assumption in graph-based anomaly detection is that connected nodes share similar labels, but this doesn't always hold true for anomalies. LP-GAD aims to overcome these limitations by effectively leveraging limited labeled data to infer and refine pseudo-labels for unlabeled nodes.

Methods

LP-GAD employs a two-module approach: a label generator and a target network.

  • Label Generator: This module generates high-quality pseudo-labels for unlabeled nodes. It leverages graph propagation to infer these labels by considering inconsistencies in both graph structure and node attributes between normal and abnormal samples.
  • Structure Pseudo-Labels: It models label propagation as a Markov Diffusion Process, using different operators to diffuse labels across the graph. A self-gating mechanism is used to learn the importance of these operators, allowing the model to capture both global and local graph contexts.
  • Attribute Pseudo-Labels: It reweights attributes based on their influence scores to enhance the probability of identifying anomalies during label propagation.
  • Prototype-Aware Strategy: To mitigate potential out-of-domain results from directly training with pseudo-labels and to refine them, LP-GAD introduces a prototype-aware strategy. This strategy uses class distribution information to model semantic relationships between normal and anomalous nodes. It calculates prototype embeddings for each class and then iteratively updates the pseudo-labels using a moving-average mechanism that incorporates a Jaccard coefficient to measure the similarity between the generated pseudo-labels and the target network's predictions. This mechanism helps correct and refine the pseudo-labels, reducing the influence of the prototype knowledge when the pseudo-labels are already close to the target network's predictions.

Datasets

The paper evaluates LP-GAD on six anomaly datasets. Specific dataset names mentioned are:

  • BlogCatalog
  • Flickr
  • ACM
  • Cora
  • Citeseer
  • PubMed

The paper references "Adbench: Anomaly detection benchmark" (Han et al. 2022) for details on these datasets.

Key Insights and Ideas

  • Pseudo-labeling is powerful, but needs refinement: Generating pseudo-labels via graph propagation is a promising direction for anomaly detection with limited labels. However, directly using these labels can lead to inaccuracies.
  • Structure and attribute inconsistencies are key: Exploiting both structural and attribute-based differences between normal and anomalous nodes is crucial for generating informative pseudo-labels.
  • Prototype knowledge corrects for label scarcity: Incorporating class prototypes helps to ground the pseudo-labeling process, preventing it from drifting too far from the true class distributions, especially when labeled anomalies are scarce.
  • Adaptive diffusion for graph structure: Using a self-gating mechanism to learn the importance of different diffusion operators allows the model to adaptively capture relevant structural information at various scales.

Key Results

LP-GAD achieves strong performance across the evaluated datasets. Specifically:

  • It outperforms other baseline methods on six anomaly datasets, achieving the best anomaly detection performance except for the Cora dataset.
  • Compared to SSL baselines, LP-GAD shows significant improvements: 2.97% on Flickr (AUC) and 2.84% on PubMed (F1-macro).
  • It surpasses SemSL methods like PC-GNN and Meta-GDN by effectively overcoming the limitations of relying solely on limited labeled data.

Limitations and Future Work

  • Limitations: The paper acknowledges that the research on label propagation for graph anomaly detection is still in its infancy. The current approach might still be susceptible to issues arising from highly complex or noisy graph structures.
  • Future Work: The authors suggest that the application of label propagation in detecting anomalies warrants further exploration. This implies potential for developing more sophisticated propagation strategies, exploring different ways to incorporate prior knowledge, and extending the method to other graph-related tasks.

Summary updated

BibTeX
@inproceedings{tang2024graph,
  author = {Hui Tang and Xun Liang and Sensen Zhang},
  title = {{Graph Anomaly Detection via Prototype-Aware Label Propagation (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30518},
}
Figure