Learning subgraph-based normality for interpretable graph-level anomaly detection

Graph-level anomaly detection (GLAD) aims to identify graphs that significantly deviate from others in a graph dataset. Existing methods predominantly rely on standard Graph Neural Networks (GNNs) to learn graph representations, but they often overlook subgraph-level information, which provides essential structural and semantic cues for distinguishing normal and anomalous graphs. This limitation not only compromises the detection performance but also hinders the interpretability of GLAD predictions. To address these challenges, we propose NGLAD, a novel framework that introduces the concept of normality-relevant subgraphs that capture shared patterns across normal graphs. These subgraphs serve as key indicators to distinguish normal graphs from anomalies that that often lack or deviate from such patterns. During model training, by explicitly modeling the shared subgraph patterns inherent in normal graphs through a Subgraph Extractor and a Normality Learner, NGLAD identifies the subgraphs most relevant to normality. Leveraging the One-class Information Bottleneck principle, these modules ensure that the extracted subgraphs retain only the most informative features of normality while filtering out irrelevant nodes and edges. During inference, NGLAD detects anomalies by evaluating inconsistencies in representations between the input graph and its extracted subgraph. Extensive evaluations on synthetic and real-world datasets demonstrate that NGLAD significantly outperforms state-of-the-art methods in detection performance while offering interpretable explanations.