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

1 Introduction

Graph-structured data are ubiquitous in a wide range of domains, including biochemistry [Guo et al., 2022], finance [Rajput and Singh, 2022], and social networks [Xia et al.,

∗Corresponding author.

2021; Ju et al., 2024]. In many of these domains, it is crucial to identify graphs that exhibit a significant deviation from the majority in the graph collection [Qiao et al., 2025; Yang et al., 2026], a task formalized as Graph-level Anomaly Detection (GLAD). Detecting such anomalous graphs is essential for uncovering rare events, mitigating risks, and driving scientific discovery. Compared to identifying anomalous nodes [Lin et al., 2024; Niu et al., 2025] or edges [Lee et al., 2024] in a single graph, GLAD highlights its significance in understanding the structure features of different graphs.

A rich line of GLAD algorithms has recently been developed, among which two paradigms have shown promise. The first paradigm adopts a global perspective, aggregating node representations learned via Graph Neural Networks (GNNs) [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018;

Xu et al., 2019; Lin et al., 2025] into a graph embedding, which is subsequently scored for anomaly detection [Zhao and Akoglu, 2020; Luo et al., 2022; Zhang et al., 2022a; Ma et al., 2023; Zhang et al., 2024; Kim et al., 2024; Chen et al., 2025; Zhang et al., 2026]. The second takes a subgraphoriented perspective [Liu et al., 2023; Yang et al., 2025; Zhang et al., 2025], aiming to identify subgraphs that capture the essential differences between normal and anomalous graphs. Despite their effectiveness, both paradigms are limited by the fixed perspective on graph structures.

In GLAD, the key differences among anomalous and normal graphs often involve multiple levels of structure granularity. As illustrated in Figure 1 (b), a graph can be progressively coarsened into multiple levels of structure granularity; at particular granularities, certain graphs exhibit anomalous characteristics due to significant structural deviations from other graphs. In contrast, the global aggregation in the first paradigm may obscure discriminative signals that differentiate normal and anomalous graphs. Subgraph-oriented approaches of the second paradigm implicitly assume that the distinction between normal and anomalous graphs can be attributed solely to the presence or absence of certain subgraphs, may fail to account for anomalies arising from longrange dependencies across the graph. As shown in Figure 1 (a), the real-world graphs often violate this assumption, especially for graphs with complex relational structures (e.g., social networks), where subgraphs exhibit high variability and do not uniquely characterize abnormality. Hence, because GLAD can benefit from a multi-granular perspective, it is essential to develop a method that considers such structures.

To effectively distinguish anomalous graphs from normal ones based on the multi-granular structure learning, two core challenges arise. Challenge #1: How to extract multiple levels of structure granularity under an unsupervised manner? The scarcity of labeled anomalies in real-world scenarios necessitates unsupervised extraction of multi-granular graph representations. Hierarchical graph pooling methods [Ying et al., 2018; Lee et al., 2019; Gao and Ji, 2019; Duval and Malliaros, 2022] can derive multiple granularities through graph coarsening, but they are primarily designed for supervised classification objectives rather than anomaly-sensitive graph structure learning. Challenge #2: How to achieve granularity-aware anomaly scoring? In GLAD, abnormalities may manifest at specific granularities, and anomalous patterns may vary across granularities. Therefore, the model must adaptively learn across multiple levels of structure granularity to quantify the anomaly degree of graphs.

To address the above challenges, we propose M-GLAD, an unsupervised GLAD model via multi-granular graph structure learning. M-GLAD captures multiple levels of structure granularity through a structure abstraction module. For each input graph, it produces a sequence of coarsened graphs at different levels of granularity. To enable granularity-aware anomaly scoring, we introduce the Prototype-guided Multigranular Information Bottleneck (PMIB), an unsupervised graph representation framework tailored for the GLAD task. The PMIB maximizes the mutual information between the learnable granularity-specific prototype and input graphs at the corresponding granularity. The granularity-specific prototypes are parameterized graphs that summarize the typical normal characteristics of graphs at a specific granularity. During inference, the anomaly score of a test graph is obtained by aggregating deviations at different granularities, where each deviation measures the discrepancy between the coarsened graph and the corresponding learnable granularityspecific prototype. To this end, our contributions can be summarized as follows:

• To the best of our knowledge, we are the first to advance unsupervised GLAD from the exploration of multiple levels of structure granularity.
• We propose M-GLAD, an unsupervised multi-granular GLAD framework equipped with the PMIB principle. The framework learns granularity-specific prototypes to capture the typical characteristics shared by graphs and enables granularity-aware anomaly scoring.
• Extensive experiments on real-world graph datasets show that M-GLAD achieves superior performance and validate the effectiveness of distinguishing between normal and anomalous graphs through multi-granular graph structure learning.

2 RelatedWork

Global-aggregation based GLAD methods. With the development of GNNs, many recent GLAD methods have moved toward representation learning paradigms that characterize each graph using the graph embedding. For instance, deep one-class classification methods [Zhao and Akoglu, 2020; Qiu et al., 2022; Zhang et al., 2024] optimize hyperspherebased objectives to learn compact normal graph representations, using distances to the hypersphere center as anomaly scores. Reconstruction-based approaches [Luo et al., 2022; Kim et al., 2024; Chen et al., 2025] rely on graph autoencoders or their variational variants, where reconstruction discrepancies indicate anomalies. Knowledge-distillation based methods [Ma et al., 2022] model normal graphs via random distillation, using prediction errors as anomaly scores. There are also other approaches separating the normal and anomalous graphs in the representation space through geometric or spectral objectives [Dong et al., 2024].

Subgraph-oriented GLAD methods. Another line of GLAD methods emphasizes local structural patterns, extracting discriminative subgraphs [Zhang et al., 2021; Zhang and Li, 2021; Zhao et al., 2022] from graphs as evidence for anomaly detection. For example, SIGNET [Liu et al., 2023] learns a subgraph extractor and detects graph-level anomalies based on the abnormality of extracted subgraphs. Building on this paradigm, GLADPro [Yang et al., 2025] further improves the subgraph-level anomaly modeling to better characterize the difference between normal and anomalous graphs.

Despite empirical success, they are generally incapable of capturing graph-level anomalies whose discriminative characteristics emerge at multiple levels of structural granularity. Specifically, global aggregation-based approaches can easily smooth the subtle anomaly signals embedded in fine-grained structures. In contrast, subgraph-basedmethods typically rely on strong assumptions about structural regularity; however, the presence of diverse or irregular subgraphs does not necessarily indicate anomalies.

3 Preliminaries

Graph. A graph is denoted as G = (V, E,X,A), where V and E are the node and edge sets, respectively. X ∈ R|V|×d is the node attribute matrix, and A ∈ {0, 1}|V|×|V| is the adjacency matrix. For a graph G, its multiple levels of structure granularity can be represented by a graph sequence {G (l) }Ll=0 with G (0) = G, where G (l) = (V (l) , E (l) , X(l) , A(l) ).

Granularity-specific Prototype. We define the granularityspecific prototype as G (l) p = (V (l) p , E (l) p ,X(l) p ,A(l) p ), for l = {0, 1, ..., L}. Each granularity-specific prototype is designed to capture the typical patterns shared by normal graphs at the corresponding level of structure granularity. The attribute matrix X(0) p and adjacency matrix A(0) p are initialized by the method described in Section 4.2. Prototypes at the deeper level of granularities (l > 0) are coarsened from the original prototype G (0) p . X(l) p and A(l) p for l > 0 are learnable, with each element in matrices being an updatable parameter.

Graph Convolution. At the t-th layer of a GNN, the node representation is updated by

where N(v;A) denotes the neighborhood of node v induced by A, fAgg(·) aggregates information from the neighbors, and fUpdate(·) updates the node representation.

Multi-view Information Bottleneck (MIB). MIB is an unsupervised formulation of the information bottleneck (IB)

principle [Tishby et al., 2000; Tishby and Zaslavsky, 2015; Wu et al., 2020]. Specifically, MIB exploits complementary views of the same data instance to learn its representations in an unsupervised fashion [Bachman et al., 2019; Hassani and Khasahmadi, 2020; Xu et al., 2024]. Given two complementary views V1 and V2 of the same instance, MIB learns a representation Z1 from view V1 that is maximally predictive of view V2, while suppressing information that is specific to V1. Formally, MIB can be formulated as the following constrained optimization:

where β1 is a trade-off coefficient. A symmetric objective for V2 is defined analogously.

Problem Formulation. Given a training set Dtr consisting exclusively of normal graphs, GLAD aims to learn a scoring function f : G → score(G) that assigns each input graph an anomaly score. In M-GLAD, the final anomaly score is obtained by aggregating granularity-specific scores across multiple levels: score(G) = Agg({score(l) (G)}Ll=0 ), where score(l) (G) denotes the score at granularity l and Agg(·) specifies the scoring strategy (formalized in Section 4.5).

4 Methodology

This section describes the methodology of M-GLAD, and Figure 2 provides an illustration of the overall framework.

4.1 PMIB Framework Overview

Inspired by the MIB principle and prototype learning [Zhang et al., 2022b; Dai and Wang, 2025], we propose PMIB, a Prototype-guided Multi-granular Information Bottleneck objective that guides the optimization of M-GLAD.

To capture shared patterns of normal graphs at a specific level of structure granularity, we introduce learnable granularity-specific prototypes G (l) p , where l = {0, 1, ...,L}. The discrepancy between a graph and the prototype quantifies abnormality: normal graphs align with prototypes across granularities, whereas anomalies deviate due to atypical patterns. To operationalize this principle, PMIB defines two complementary views at each granularity l: (i) instance graph view, denoting the coarsened graph G (l) at granularity l, and (ii) prototype graph view, defined as the corresponding prototype G (l) p at the same granularity. For the instance graph view, PMIB enforces an information bottleneck objective to ensure that the coarsened graph G (l+1) at the next granularity level preserves information consistent with the prototype G (l) p , while suppressing instance-specific redundancies irrelevant to normality. Formally,

where β1 is a trade-off parameter. Symmetrically, the prototype view is governed by the dual bottleneck objective:

where β2 is defined analogously.

The final PMIB objective is the negative of the sum of the two symmetric bottleneck objectives in Eqs. (3) and (4). Since directly minimizing this objective is intractable, we optimize a tractable variational upper bound instead:

where pθ(G (l+1) | G (l) ) and qϕ(G (l+1) p | G (l) p ) denote the instance and prototype transition distributions induced by the graph and prototype encoders, respectively, DSKL(·) denotes the symmetrized Kullback-Leibler (SKL) divergence and β is a trade-off hyper-parameter. Detailed derivations of the upper bound are provided in the supplementary 1 . This formulation encourages the instance and prototype views to align on normal patterns, while allowing deviations to signal anomalies. We denote the mutual information (MI) loss (the first term) as L(l) MI , and the SKL divergence loss (the second term) as L(l) SKL . Their concrete computation is detailed in Section 4.4.

In the following, we first describe how to obtain the initial prototype G (0) p (Section 4.2). Then, we introduce the graph structure abstraction to coarsen input graphs and prototypes (Section 4.3), followed by PMIB optimization (Section 4.4). Finally, we present granularity-specific anomaly scoring to quantify the degree of graph abnormality (Section 4.5).

1 https://github.com/Lab821-gz/M-GLAD/blob/main/

M-GLAD supplementary.pdf

4.2 Prototype Graph Construction

At each level of structure granularity, normal graphs are associated with a shared granularity-specific prototype. The initial prototype is represented as G (0) p = (V (l) p , E (l) p ,X(0) p ,A(0) p ). Next, we introduce how to initialize the attribute matrix X(0) p and the adjacency matrix A(0) p .

Attribute matrix initializing. We first obtain node embeddings for normal graphs in the training set Dtr:

where GNNemb is built upon the graph convolution, and each row of H represents a node embedding in a graph G. Let Utr denote the representation matrix of all nodes from graphs in Dtr, we initialize the prototype node attributes by:

where KMeans(·) denotes the k-means clustering algorithm, and k = |V (0) p | specifies the number of clusters, corresponding to the number of nodes in the prototype G (0) p . In practice, |Vp(0) | is set to the average number of nodes of the graphs in the training set Dtr.

Adjacency matrix initializing. To equip the prototype with structural information [Cai et al., 2025], we initial the adjacency matrix as:A(0) p = T (X(0) p X(0)⊤ p ), (8)

where T (·) is a symmetric mapping that transforms pairwise latent similarities into non-negative edge weights. This yields an adaptive prototype structure that co-evolves with X(0) p and captures shared structural regularities. Prototypes at next levels (l > 0) of structure granularity can be obtained through the module of graph structure abstraction.

4.3 Graph Structure Abstraction

To obtain multiple levels of granularities in graph structures, we introduce a graph structure abstraction module that progressively coarsens graphs and prototypes via hierarchical graph pooling [Islam et al., 2023; Wang et al., 2024]. For clarity, we describe the procedure using the instance graph as an example; the same operations are applied to the prototype in parallel. At the level l of the structure granularity, node representations are first updated using the GNN:

where H(l) denote the node embeddings of the graph G (l) , with H(l) p defined analogously for the prototype. Following [Ying et al., 2018], we employ a separate pooling GNN with the same graph convolution operator as GNNemb to generate soft cluster assignments:

where each row of S(l) defines a categorical distribution over Kl clusters at granularity l + 1, and Kl = ⌈r · |V (l) |⌉ is determined by a coarsening ratio r.

In practice, we aim to obtain near one-hot cluster assignments for each node. Since sampling from the categorical distributions in S(l) to achieve true one-hot assignments is non-differentiable, we instead employ a differentiable relaxation, i.e., the Gumbel-Softmax trick [Jang et al., 2017], which provides a differentiable reparameterization of the categorical sampling process. The resulting matrix, denoted as ˆS(l) , serves as a near one-hot approximation of S(l) , enabling gradient-based optimization. The attribute and the adjacency matrix of G (l+1) are obtained as below:

By recursively applying the structure abstraction process described above, we obtain multiple levels of granularity for the graph G, denoted as {G (l) }Ll=0 .

The same iterative graph structure abstraction process is applied to the initial prototype graph G (0) p , thereby constructing coarser prototype series {G (l) p }Ll=1 at different levels of structure granularity.

4.4 The Optimization of PMIB

After completing obtaining different levels of structure granularity of the input graphs and learnable prototypes, we optimize the PMIB objective in Eq. (5) by explicitly estimating the two loss terms, L(l) MI and L(l) SKL , at each granularity level. We next instantiate these two terms in a tractable and differentiable way.

The MI Term. Directly computing the MI between graphs is intractable. Therefore, to evaluate L(l) MI , we first encode the instance graph G (l) and the prototype G (l) p into their graphlevel embeddings, z(l) and p(l) :

where READOUT(·) denotes a global pooling operator. To tractably approximate this MI term, we optimize a symmetric InfoNCE loss over graph-prototype pairs.

(i) Graphs-to-prototype. For each instance representation z(l) i , the corresponding granularity-specific prototype p(l) serves as the positive sample, while prototypes from other granularities act as negative samples:

where B denotes the mini-batch, s(·, ·) is the cosine similarity function, and τ is the temperature hyper-parameter. This term encourages instance representations to align closely with their corresponding prototype while remaining distinguishable from prototypes at other granularities.

(ii) Prototype-to-graphs. Symmetrically, for each prototype p(l) , the instance representations z(l) i within the same granularity serve as positive samples, while instances from other granularities are treated as negatives:

where j indexes instances in the mini-batch. This symmetric term ensures that prototypes are also pulled towards their corresponding instance representations.

Finally, the MI termL(l) MI is expressed as the average of the two InfoNCE losses:

The SKL divergence term. For the SKL regularizer, we approximate L(l) SKL using a tractable surrogate based on the consistency of cluster usage, i.e., the normalized frequency of node assignments to each cluster, between coarsening processes. To instantiate the SKL term in Eq. (5), we interpret pθ(G (l+1) | G (l) ) and qϕ(G (l+1) p | G (l) p ) as implicit coarsening distributions induced by Gumbel-softmax pooling for the instance and prototype, respectively. As these distributions are intractable, we instead compare their permutation-invariant cluster usage summaries. At granularity l, the pooling module outputs a row-stochastic assignment matrix S(l) . Due to the permutation ambiguity of cluster indices, we summarize assignments by:

where u(l) denotes the cluster usage distribution induced by the assignment matrix S(l) . The SKL regularizer at granularity l is then defined as:

where u(l) i and u(l) p denote the cluster usage distributions of the i-th instance graph and the prototype at granularity l, respectively, and ϵ > 0 is a small constant for numerical stability. This symmetric formulation encourages the instance graphs and prototype graphs to adopt consistent coarsening behaviors while remaining invariant to cluster permutations.

Overall objective. Therefore, upon deriving tractable estimators for the MI and SKL terms, the overall training objective of M-GLAD can be formulated as:

4.5 Anomaly Scoring

Given a test graph G ′ , we define its granularity-specific anomaly score as:score(l) (G ′ ) = -L(l) MI (G ′ ), (19)

where larger values indicate lower consistency between the instance and the prototype, and consequently imply a higher likelihood of being anomalous. We then aggregate {score(l) (G ′ )}Ll=0 according to the scoring strategy Agg(·):

where Agg(·) is instantiated as avg, max, or a weighted function. For the weighted variant, we adopt geometrically decaying aggregation across different levels of structure granularity. Specifically,

where wl = γ l ∑Lk=0 γ k , l and k index the granularity level, and γ l denotes the exponential weighting factor assigned to granularity l. Larger γ assigns higher weights to the deeper levels of structure granularity. Time complexity analysis can be found in supplementary materials.

5 Experiments

5.1 Experimental Setup

Datasets. We conduct experiments on eight graph datasets from the TU Dataset Collection [Morris et al., 2020]. These datasets span multiple domains, including bioinformatics networks (PROTEINS-F, ENZYMES, DD), molecular networks (AIDS, BZR, COX2, MUTAG), and social networks (IMDBB), following the setting in [Liu et al., 2023].

Baselines. We compare M-GLADwith the following stateof-the-art GLAD methods: (1) Global-aggregation based GLAD methods. These approaches, including OCGIN [Zhao and Akoglu, 2020], OCGTL [Qiu et al., 2022], GOODD [Liu et al., 2022], GLocalKD [Ma et al., 2022], MUSE [Kim et al., 2024], and DO2HSC [Zhang et al., 2024], adopt a global perspective by learning node-level representations via GNNs and aggregating them into graph-level embeddings for anomaly scoring. (2) Subgraph-oriented GLAD methods. These methods, including SIGNET [Liu et al., 2023] and GLADPro [Yang et al., 2025], aim to identify subgraphs that can distinguish anomalous graphs from normal ones.

Metrics and Implementation. We use GIN [Xu et al., 2019] as the GNN backbone. The default number of granularities is set to L = 2, and the trade-off coefficient is β = 0.01. For GLAD performance, we report AUC and AUPR as evaluation metrics. All experiments are repeated five times with different random seeds, and the average performance and standard deviation are reported. Our code is available at https://github.com/Lab821-gz/M-GLAD. More settings are provided in supplementary materials.

5.2 Main Results

To evaluate the performance of M-GLAD, we compare it with eight state-of-the-art methods on eight real-world datasets. Based on the results in Table 1, we make the following observations. (1) M-GLAD achieves the best performance on 7 out of 8 TU benchmark datasets in terms of both AUC and AUPR. These results demonstrate the effectiveness and robustness of M-GLAD across diverse domains. (2) Global aggregation-based detectors such as GLocalKD, MUSE, and DO2HSC exhibit considerable performance variability across datasets, with large standard deviations on datastes including AIDS, BZR, and MUTAG. (3) Subgraph-oriented methods, particularly GLADPro, show notably lower AUPR scores on datasets such as PROTEINS-F, BZR, and COX2. The experiment results suggest that anomalous graphs are typically defined by multi-level structural patterns.

5.3 Ablation Study

To evaluate the importance of different components in MGLAD, we conduct three types of ablation studies. The experimental results are reported in Table 2. (1) We test the impact of the SKL divergence regularization term. Without the SKL regularization that enforces consistency between the prototype view and the instance graph view, the model fails to effectively align the extracted prototype features with the graph information, resulting in consistent performance degradation. (2) We evaluate the role of graph structure abstraction module. Removing the graph structure abstraction module degrades the ability to capture informative structural patterns at different granularities, resulting in inferior GLAD performance across datasets. (3) We examine the effect of prototype modeling by replacing the learned prototypes with randomly initialized ones. This replacement leads to a noticeable performance drop, indicating that data-driven prototype learning is crucial for capturing intrinsic graph structures and summarizing typical normal patterns.

5.4 Parameter Sensitivity

We evaluate the sensitivity to M-GLAD of four key hyperparameters: the number of coarsening layers L, the coarsening ratio r, the loss weight β, and the scoring strategy Agg(·). As shown in Figure 3(a), varying L from 1 to 5 results in only minor performance changes, with most datasets such as PROTEINS-F, IMDB-B, and MUTAG achieving optimal or near-optimal performance at L = 2. This indicates that moderate graph abstraction is sufficient, as too few coarsening layers may capture insufficient structural information, while overly deep coarsening can introduce noise and degrade performance. Figure 3(b) illustrates the impact of the coarsening ratio r. A moderate ratio provides an effective balance between redundancy removal and structure preservation. On most datasets such as MUTAG, IMDB-B, and COX2, the best performance is achieved at r = 0.7 or 0.8, while extreme values degrade performance due to under- or over-coarsening. Regarding the loss weight β, Figure 3(c) shows stable performance over a wide range, while overly large values degrade performance, indicating that the auxiliary loss acts as an effective regularizer without dominating optimization. Finally, Figure 3(d) shows that weighted scoring slightly outperforms avg and max while remaining stable across different γ values. This suggests that controlled aggregation of anomaly evidence across multiple coarsening levels is more effective, as the most discriminative granularity varies across datasets.

5.5 ACase Study

Figure 4 visualizes how anomalies manifest at different granularities under graph structure abstraction. For l = 0 and l = 1, the anomalous graph appears similar to the normal one, showing no clear abnormal patterns from the visualized structures. In contrast, at the coarser granularity l = 2, a clear discrepancy emerges: the anomalous graph forms a ring-like structure that is absent from the normal graph. This suggests that anomalies can be more distinguishable at certain granularities, thereby motivating multi-granularity modeling.

6 Conclusion

In this paper, we propose M-GLAD, an unsupervised GLAD framework that models anomalies from a multigranular structural perspective. M-GLAD progressively abstracts graph structures into multiple granularities and adopts the Prototype-guided Multi-granular Information Bottleneck (PMIB) to characterize normal patterns with learnable prototypes and quantify anomaly evidence via cross-granularity discrepancies. By aggregating such evidence, M-GLAD enables granularity-aware anomaly scoring. Extensive experiments on eight real-world graph datasets show that M-GLAD consistently outperforms the competitive methods.

Acknowledgments

This work was supported in part by the Shanghai Pujiang Program (No. 24PJA004), NSFC (No. 92570118, 62376088 and 62372146), Hebei Natural Science Foundation (No. F2024202047), Hebei Yanzhao Golden Platform Talent Gathering Programme Core Talent Project (Education Platform) (No. HJZD202509), Fundamental Research Funds for the Central Universities (No. 26D112010 and 2232025D-33).