Graph anomaly detection (GAD) has various applications in finance, healthcare, and security. Graph Neural Networks (GNNs) are now the primary method for GAD, treating it as a task of semisupervised node classification (normal vs. anomalous). However, most traditional GNNs aggregate and average embeddings from all neighbors, without considering their labels, which can hinder detecting actual anomalies. To address this issue, previous methods try to selectively aggregate neighbors. However, the same selection strategy is applied regardless of normal and anomalous classes, which does not fully solve this issue. This study discovers that nodes with different classes yet similar neighbor label distributions (NLD) tend to have opposing loss curves, which we term it as “loss rivalry”. By introducing Contextual Stochastic Block Model (CSBM) and defining NLD distance, we explain this phenomenon theoretically and propose a Bi-level optimization Graph Neural Network (BioGNN), based on these observations. In a nutshell, the lower level of BioGNN segregates nodes based on their classes and NLD, while the upper level trains the anomaly detector using separation outcomes. Our experiments demonstrate that BioGNN outperforms state-of-the-art methods and effectively mitigates “loss rivalry”. Codes are available at https://github.com/blacksingular/Bio-GNN.
Citation:
@inproceedings{gao2024graph,
title = {Graph Anomaly Detection with Bi-level Optimization},
author = {Gao, Yuan and Fang, Junfeng and Sui, Yongduo and Li, Yangyang and Wang, Xiang and Feng, Huamin and Zhang, Yongdong},
booktitle = {Proceedings of the ACM Web Conference 2024 (WWW '24)},
year = {2024}
}