Dual-discriminative Graph Neural Network for Imbalanced Graph-level Anomaly Detection

Ge Zhang, Zhenyu Yang, Jia Wu, Jian Yang, Shan Xue, Hao Peng, Jianlin Su, Chuan Zhou, Quan Z. Sheng, Leman Akoglu, Charu C. AggarwalNeurIPS 2022 · OpenReview

Overview

The authors present iGAD, a novel Graph Neural Network (GNN) designed to find rare, anomalous graphs within large datasets. By combining a specialized convolution that preserves node-specific attributes with a learnable random walk kernel to identify "weird" substructures—and wrapping it all in a loss function designed for extreme class imbalance—iGAD significantly outperforms state-of-the-art methods in identifying anti-cancer molecules and other graph-level anomalies.

The Challenge of Graph-Level Anomaly Detection

Graph-level anomaly detection (GLAD) is the task of finding a few "odd" graphs in a sea of normal ones. Consider a drug discovery database where only a handful of molecules exhibit a specific toxic side effect or a rare anti-cancer property.

This task is notoriously difficult for three main reasons:

  1. Attribute Anomalies: A graph might be anomalous because a specific node has an unusual property (e.g., a specific atom at the end of a molecular chain).
  2. Structural Anomalies: A graph might be anomalous because of how it is put together (e.g., a specific ring structure or "substructure").
  3. The Imbalance Problem: Anomalies are, by definition, rare. In standard training, the "normal" graphs are so overwhelming that the model simply learns to ignore the anomalies to achieve high average accuracy.

Existing GNNs often fail here because their "neighborhood aggregation" mechanism tends to smooth out unique node features, and they struggle to count or identify complex structural patterns like cycles or specific star-shapes.

The iGAD Architecture

The authors propose iGAD (imbalanced Graph-level Anomaly Detection), which uses a "dual-discriminative" architecture to tackle both attribute and structural anomalies simultaneously.

Architecture of iGAD

The model relies on three core innovations:

  • Anomalous Attribute-aware Graph Convolution: Instead of just averaging a node's features with its neighbors (which causes "over-smoothing"), iGAD concatenates the node’s own features with the features of its $k$-hop neighborhoods. This keeps the unique "signal" of individual nodes from being washed out.
  • Anomalous Substructure-aware Deep Random Walk Kernel (Deep RWK): To catch structural anomalies, the authors use Random Walk Kernels. They treat the "anomalous substructures" as learnable parameters. The model essentially "imagines" what a weird structure looks like and then checks how many random walk sequences the input graph shares with that imaginary structure.
  • PMI-based Loss Function: To handle the fact that anomalies are rare, they replace standard cross-entropy loss with one based on Point Mutual Information (PMI). This forces the model to prioritize the correlation between a graph and its label, preventing the majority (normal) class from dominating the gradients during training.

Datasets and Key Insights

The model was evaluated on four real-world molecular datasets from PubChem: SW-620 (Colon cancer), MOLT-4 (Leukemia), MCF-7 (Breast cancer), and PC-3 (Prostate cancer). In these datasets, molecules that show anti-cancer activity are labeled as "anomalous" (the rare, interesting cases), while inactive ones are "normal."

Several key insights emerged from the design of iGAD:

  • Preserving the Individual: Standard GNNs are designed to make nodes more like their neighbors. For anomaly detection, you want the "weird" node to stand out. Concatenation is a simple but effective fix for this.
  • Learning the "Shape" of Trouble: By making the adjacency matrices of the substructures learnable parameters, the model actually learns to identify specific motifs (like triangles or 4-cycles) that characterize anomalies in a specific dataset.
  • Information over Probability: Standard loss functions care about the probability of a label. PMI-based loss cares about how much information the graph provides about the label. This is a crucial distinction when one class is 10x or 100x more common than the other.

Key Results

iGAD was compared against standard GNNs (GCN, GIN, DGCNN) and specialized anomaly detection algorithms.

Performance comparison of iGAD against baselines
  • Superior Detection: iGAD consistently achieved the highest AUC (Area Under the Curve) and F-score across all four datasets. For example, on the SW-620 dataset, iGAD achieved an AUC of ~85.8%, significantly higher than standard GCN (~74.9%).
  • Massive Recall Gains: The most impressive jump was in Recall(A)—the ability to actually find the anomalies. On the MCF-7 dataset, standard DGCNN had a Recall(A) of only 11.07%, while the iGAD version jumped to an impressive 73.38%.
  • Ablation Success: The experiments showed that both the specialized convolution and the Deep RWK were necessary; removing either one dropped the performance significantly.

Limitations and Future Work

The authors acknowledge two main limitations. First is Positional Blindness: iGAD can tell if a graph has an anomalous attribute or structure, but it doesn't necessarily capture where that attribute is located within the overall graph topology. Second is its Supervised Nature: iGAD is excellent at finding anomalies similar to those it has seen in training, but it might struggle with entirely "out-of-distribution" anomalies that follow patterns never exposed during the training phase.

Future work may involve developing specific solutions to capture the positional information of nodes and substructures to further refine detection capabilities.

Summary updated

Abstract

Graph-level anomaly detection aims to distinguish anomalous graphs in a graph dataset from normal graphs. Anomalous graphs represent a very few but essential patterns in the real world. The anomalous property of a graph may be referable to its anomalous attributes of particular nodes and anomalous substructures that refer to a subset of nodes and edges in the graph. In addition, due to the imbalance nature of anomaly problem, anomalous information will be diluted by normal graphs with overwhelming quantities. Various anomaly notions in the attributes and/or substructures and the imbalance nature together make detecting anomalous graphs a non-trivial task. In this paper, we propose a graph neural network for graph-level anomaly detection, namely iGAD. Specifically, an anomalous graph attribute-aware graph convolution and an anomalous graph substructure-aware deep Random Walk Kernel (deep RWK) are welded into a graph neural network to achieve the dual-discriminative ability on anomalous attributes and substructures. Deep RWK in iGAD makes up for the deficiency of graph convolution in distinguishing structural information caused by the simple neighborhood aggregation mechanism. Further, we propose a Point Mutual Information (PMI)-based loss function to target the problems caused by imbalance distributions. PMI-based loss function enables iGAD to capture essential correlation between input graphs and their anomalous/normal properties. We evaluate iGAD on four real-world graph datasets. Extensive experiments demonstrate the superiority of iGAD on the graph-level anomaly detection task.
BibTeX
@inproceedings{zhang2022dual,
  author = {Ge Zhang and Zhenyu Yang and Jia Wu and Jian Yang and Shan Xue and Hao Peng and Jianlin Su and Chuan Zhou and Quan Z. Sheng and Leman Akoglu and Charu C. Aggarwal},
  title = {{Dual-discriminative Graph Neural Network for Imbalanced Graph-level Anomaly Detection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=QNYX5L1EOd},
}
Figure