End-to-End Abnormal Subgraph Detection via Subgraph-Level Contrastive Learning

Abnormal subgraph (AS) detection plays a significant role in ensuring the security of many high-impact domains. Unlike node anomaly detection, identifying subgraph anomalies is extremely challenging due to the exponentially large subgraph space caused by various combinations of nodes and edges. Moreover, in the absence of supervisory signals, how to quantify the abnormality of subgraphs poses another pressing challenge. Traditional methods typically rely on handcrafted subgraph anomaly measures, making it hard to handle potential unknown anomalies with limited prior knowledge. Recent deep learning-based techniques are predominantly designed to discover individual node anomalies, which could be suboptimal for AS detection due to the inconsideration of collaborative behaviors between nodes in the subgraph. In fact, existing studies have put very little effort into this task, and even dedicated performance evaluation metrics are not yet available. To address the above challenges and promote related research, in this article, we propose a end-to-end unsupervised subgraph anomaly detection framework (EndSubG), which jointly models subgraph partition and AS detection as a whole instead of treating them as two separate stages. Specifically, EndSubG uncovers potential AS boundaries that violate the Homophily assumption by modeling the edge existence probability, then achieves anomaly-aware graph embedding and subgraph partition based on the refined topology. By forming a coarsened subgraph network, EndSubG picks out subgraph anomalies by learning the "subgraph-vicinity" matching patterns. Additionally, we design an evaluation metric weighted normalized mutual information centered on AS (AS-WNMI) specifically for subgraph anomaly detection, which is a variant of vanilla NMI and quantifies detection performance from both subgraph partition and anomaly recognition. The experimental results on synthetic and real-world datasets corroborate the superiority of end-to-end unsupervised subgraph anomaly detection framework (EndSubG) in terms of area under the curve (AUC), average precision (AP), and AS-WNMI. We also provide an intuitive analysis of the detected subgraphs through visualization for better understanding.