Unsupervised Graph-Level Anomaly Detection via Multi-granular Graph Structure Learning

Abstract

Graph-level anomaly detection (GLAD) aims to identify graphs that deviate from the majority in a dataset of graphs. Existing methods typically adopt either a global aggregation perspective that summarizes nodes within a graph into a representation vector, or a subgraph-oriented perspective which regards certain local subgraphs as indicators of anomalous properties. However, both paradigms operate from a fixed perspective and may fail to identify anomalous graphs whose discriminative characteristics manifest at multiple levels of structure granularity, where each level features the coarsened graphs at a specific granularity. In this paper, we propose M-GLAD, an unsupervised GLAD method via multi-granular graph structure learning. M-GLAD is grounded in the Prototype-guided Multi-granular Information Bottleneck (PMIB) principle. PMIB aims to measure the mutual information between coarsened graphs at the specific level of structure granularity and the learnable granularity-specific prototypes that summarize normal patterns of graphs at each granularity. The multiple levels of structure granularity of graphs and prototypes are abstracted by a graph structure abstraction module. This formulation enables granularity-aware anomaly scoring that considers anomalous characteristics across different levels of structure granularity. Extensive experiments on eight real-world graph datasets demonstrate that M-GLAD achieves superior performance over competitive baselines.