Towards Self-Interpretable Graph-Level Anomaly Detection
Authors: Yixin Liu
Kaize Ding
Qinghua Lu
Fuyi Li
Leo Yu Zhang
Shirui Pan
Venue: NeurIPS 2023 poster (2023)
Keywords: Anomaly Detection
Graph Neural Networks
Explanation
Self-Interpretation

Abstract: Graph-level anomaly detection (GLAD) aims to identify graphs that exhibit notable dissimilarity compared to the majority in a collection. However, current works primarily focus on evaluating graph-level abnormality while failing to provide meaningful explanations for the predictions, which largely limits their reliability and application scope. In this paper, we investigate a new challenging problem, explainable GLAD, where the learning objective is to predict the abnormality of each graph sample with corresponding explanations, i.e., the vital subgraph that leads to the predictions. To address this challenging problem, we propose a Self-Interpretable Graph aNomaly dETection model (SIGNET for short) that detects anomalous graphs as well as generates informative explanations simultaneously. Specifically, we first introduce the multi-view subgraph information bottleneck (MSIB) framework, serving as the design basis of our self-interpretable GLAD approach. This way SIGNET is able to not only measure the abnormality of each graph based on cross-view mutual information but also provide informative graph rationales by extracting bottleneck subgraphs from the input graph and its dual hypergraph in a self-supervised way. Extensive experiments on 16 datasets demonstrate the anomaly detection capability and self-interpretability of SIGNET.

Towards Seff-Interpretabee Graph-Level Anomaly Detection
Yixin Liu', Kaize Ding', Qinghua Lu Fuyi Li Leo Yu Zhang Shirui Pan *Monash University, WNorthwestern University, $Daa661, CSIRO, Worthwest A&F University, 'hhe University of Adelaide, Griffith University yixin. wwwumonashhhh.....mmm edu, kaize ding@northwester..ee. edu, qinghua lu@data61 csiro. au, fuyi 11 @nwsuaf edu. leo. aeo..hhnnggriffiite edu. au, 8. p.n@@griffth edu au
Abstract
Graph-level anomaly detection (GLAD) aims to identify graphs that exhibit notable dissimilarity compared to the majority in a collection. However, current works primarily focus on evaluating graph-level abnormality while failing to provide meaningful explanations for the predictions, which largely limits their reliability and application scope. In this paper, investigate explainable GLAD, where the learning objective to predict the abnormality of each graph sample with corresponding explanations, i.c. the vital subgraph that leads to the predictions. To address this challenging problem, we propose Self-Interpretable Graph aNomaly dETection model (SIGNET for short) that detects anomalous graphs as well as generates informative explanations simul- taneously. Specifically, we first introduce the multi- subgraph information bottleneck (MSIB) framework, serving as the design basis of our self-interpretable GLAD approach. This way SIGNET able not only measure the abnormality of each graph based on cross-view mutual information but also provide informative graph rationales by extracting bottleneck subgraphs from the input graph and its dual hypergraph in a self-supervised way. Extensive experiments on 16 datasets demonstrate the anomaly detection capability and self-inierpreeabbiiiy of SIGNET.
challenging problem,
Introduction
Graphs are ubiquitous data structures in numerous domains, including chemistry, traffic, and social networks 2 3 Among machine learning tasks for graph data, graph-level anomaly detection (GLAD) is a challenge that aims to identify the graphs that exhibit substantial dissimilarity from the majority of graphs in collection 4 GLAD presents great potential for various real-world scenarios, such as toxic molecule recognition [ and pathogenic brain mechanism discovery (6). Recently, GLAD has drawn increasing research attention, with advanced techniques being applied to this task, e.g., knowledge distillation 4 and one-class classification 7
Despite their promising performance, existing works predict abnormal graphs by designing various GLAD architectures; however, they fail provide explanations for the prediction, i.e., illustrating why these graphs are recognized as anomalies. In real-world applications, it of great significance to make anomaly detection models explainable (10]. From the perspective of models, valid explainability makes GLAD models trustworthy to meet safety and security requirements [TT] For example, an explainable fraud detection model can pinpoint specific fraudulent behaviors when identifying defrauders, which enhances the reliability of predictions. From the perspective of data, an anomaly detection model with explainability can
mainly aim to answer how to
"Corresponding Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(o) GLAD problem
Dataset
(b) Explainoble 6LAD problem
anomaly score 0.94
anomaly score 0..4
GLAD model
Explainable GLAD model
explanation
Figure 1: A toy example to illustrate (a) GLAD problem and (b) explainable GLAD problem.
help us explicitly understand the anomalous patterns of the dataset, which further supports human experts in data understanding (12). For instance, an explainable GLAD model for molecules can summarize the functional groups that cause abnormality, enabling researchers to deeply investigate the properties of compounds. Hence, the broad applications of interpreting anomaly detection results motivate us investigate the problem of Explainable GLAD where the GLAD model is expected to measure the abnormality of each graph sample as well as provide meaningful explanations of the predictions during the inference time. As an example shown Fig. [ the GLAD model also extracts a graph rationale [33 [4] corresponding to the predicted anomaly score. Although there are few studies [10 15 [6] proposed to explain anomaly detection results for visual or tabular data, explainable GLAD remains underexplored and it is non-trivial to apply those methods to our problem due to the discrete nature of irregular graph-structure data [17.
Towards the goal of designing an explainable GLAD model, two essential challenges need to be solved with careful design: Challenge 1 how make the GLAD model eete-interrretalle" Even though we can leverage existing post-hoc explainers [1] for GNNs to explain the predictions of the GLAD model, such post-hoc explainers are not synergistically learned with the detection models, resulting in the risk of wrong, biased, and sub-optimal explanations [2] 22 Hence, developing self-interpretable GL.A model which detects graph-Ievel anomalies with explanations inherently is more desirable and requires urgent research efforts. Challenge 2 - how to learn meaningful graph explanations without using supervision signals? For the problem of GLAD, ground-trutt anomalies usually unavailable during training, raising significant challenges to both detecting anomalies and providing meaningful explanations. Since most of the existing seff-interpretable GNNs [3 21 [2]
merely focus the (semi- Jsppevvidd setting, in particular the node/grapi classification tasks, how to design a self-interpretable model for the explainable GLAD problem where ground-true -ruth labels are inaccessible remains challenging task.
To solve the above challenges, in this paper, we develop novel Self-Interpreeablle Graph aNomaly dETection model (SIGNET for short). Based on the information bottleneck (IB) principle, we first propose multi-view subgraph information bottleneck (MSIB) framework, serving as the design basis of our self-interpretabll GLAD model. Under the MSIB framework, the instantiated GLAD model is able to predict the abnormality of each graph as well as generate corresponding explanations without relying on ground-truth anomalies simultaneously. To learn the self- self-interpretable GLAD model without ground-truie -ruth anomalies, we introduce the dual hypergraph as a supplemental view of the original graph and employ unified bottleneck subgraph extractor to extract corresponding graph rationales. By further conducting multi-view learning among the extracted graph rationales, SIGNET is able to learn the feature patterns from both node and edge perspectives in purely self-supervised manner. During the test phase, we can directly measure the abnormality of each graph sample based on its inter-view agreement (i.e., cross-view mutual information) and derive the corresponding graph rationales for the purpose of explaining the prediction. To sum up, our contribution is three-fold:
Problem. We propose to investigate the explainable GLAD problem that has broad application prospects. To the best of our knowledge, this is the first attempt to study the explainability problem for graph-level anomaly detection.
Algorithm. We propose novel self-interpretable GLAD model termed SIGNET, which infers graph-level anomaly scores and subgraph- explanations simultaneously with the multi-view subgraph information bottleneck framework.
IIn this paper, we distinguish the terms "explainability" and "interpretability"" following a recent survey paper [8]: "explainable artificial intelligence" is widespread and high-level concept, hence we define the research problem as "explainable GLAD"; for the model that can provide interpretations of the predictions of itself, we consider it "interpretable" ieff-interprettable" Detailed definitions provided in Appendix A.

---

Evaluation. We perform extensive experiments to corroborate the anomaly detection performance and seff-interpretation ability of SIGNET via thorough comparisons with state-of-the methods on 16 benchmark datasets.
2 Preliminaries and Related Work
In this section, we introduce the preliminaries and briefly review the related works. A more compre- hensive literature review can be found in Appendix B.
Notations. Let G = (V. & X) be a simple graph with n nodes and m edges, where the set of nodes and is the set of edges. The node features are included by feature matrix X E Ruxd, and the connectivity among the nodes is represented by adjacency matrix A E R=**. Unlike simple graphs where each edge only connects two nodes, "hypergraph" is generalization of traditional graph structure in which hyperedges connect more than two nodes. We define a hypergraph with n* nodes and m" hyperedges as G = (V",E" X'), where V*, and X* E R" xdj are the node set, hyperedge set, and node feature matrix respectively. To indicate the higher-order relations among arbitrary numbers of nodes within a hypergraph, we use an incidence matrix M R xmm" to represent the interaction between n nodes and m² hyperedges. Alternatively, simple graph and a hypergraph and be represented by G (A, X) and G (M* Xx). respectively. We denote the Shannon mutual information (MI) of two random variables A and B as T(A; B).
Graph Neural Networks (GNNs). GNNs are the extension of deep neural networks onto graph data, which have been applied to various graph learning tasks 2 23
24
25
26
27 28). Mainstream
GNNs usually follow the paradigm of message passing 2
23
24
26 Some studies termed
hypergraph neural networks (HGNNs) also apply GNNs to hypergraphs 29 30 31. The formulations of GNN and HGNN are in Appendix C. To make the predictions understandable, some efforts try to uncover the explanation for GNNs [18 32 A branch of methods, termed post-hoc GNN explainers, use specialized models explain the behavior of trained GNN 199 20 33 Meanwhile, some self- interpretable GNNs can intrinsically provide explanations for predictions using interpretable designs in GNN architectures scenarios, how to interpret unsupervised anomaly detection models still remains open.
13
22 While these methods mainly aim at supervised classification
Information Bottleneck (IB). IB is an information theory-based approach for representation learn- ing that trains the encoder by preserving the information that is relevant to label prediction while minimizing the amount of superfluous information [34] 35| 36). Formally, given the data X and the label Y. IB principle aims to find the representation Z by maximizing the following objective: maxz I Y) (I ; Z), where 8 is hyper- paper-parameter to trade off informativeness and com- pression. To extend IB onto unsupervised learning scenarios, Multi-view Information Bottleneck (MIB) 37 provides an optimizable target for unsupervised multi-view learning. which alleviates the reliance on label Y. Given two different and distinguishable views V1 and V/2 of the same data X, the objective of MIB is to learn sufficient and compact representations Zı and Ze for two views respectively. Taking view V1 as an example, by factorizing the MI between V/1 and Z1, we can identify two components: 1(V;; 21) = [(V1; 2 V22) + 1(V2; Zi), where the first term is the superfluous information that is expected to be minimized, and the second term is the predictive information that should be maximized. Then, Z, can be learned using a relaxed Lagrangian objective:
max I(2; 3vI((i; 2,
(I)
where 31 is a trade-off parameter. By optimizing Fq.. 1 and its counterpart in view V2, we can learn informative and compact Z₁ and Ze by extracting the information from each other.
IB principle is also proven to be effective in graph learning tasks, such as graph contrastive learn-
ing [88 39), subgraph recognition [17 40), graph-based recommendation 4TI, and robust graph
representation learning 22 43 Nevertheless, how to leverage the idea of IB on graph anomaly
detection tasks is still open problem.
Graph-level Anomaly Detection (GLAD). GLAD aims to recognize anomalous graphs from set of graphs by learning an anomaly score for each graph sample to indicate its degree of abnormality 4 & 9. Recent studies try to address the GLAD problem with various advanced techniques, such as knowledge distillation 4 one-class classification [7]. transformation learning (8),
3

---

and deep graph kernel [44]. However, these methods can only learn the anomaly score but fail to provide explanations, i.c., the graph rationale causing the abnormality, for their predictions.
Problem Formulation. Based on this mainstream unsupervised GLAD paradigm [4] [7,8) 1 in this paper, we present novel research problem termed explainable GLAD), where the GLAD model is expected to provide the anomaly score as well as the explanations of such a prediction for each testing graph sample. Formally, the proposed research problem can be formulated by:
Definition 2.1 (Explainable graph-level anomaly detection). Given the training set Grr that contains number of normal graphs, we aim at learning explainable GLAD model f G (TR, G) that is able to predict the abnormality of graph and provide corresponding explanations. In specific, given graph G2 from the test set Gte with normal and abnormal graphs, the model can generate an output pair f(G) = (st. (s,.G(et) where 8, is the anomaly score that indicates the abnormality degree of G,, and G( is the subgraph of G2 that explains why G2 is identified as a normal/abnormal sample.
3 Methodology
This section details the proposed model SIGNET for explainable GLAD. Firstly, we derive multi-view subgraph information bottleneck (MSIB) framework (Sec. (51) that allows us to identify anomalies with causal interpretations provided. Then, we provide the instantiation of the components in MSIB framework, including view construction (Sec. 3.2). bottle subgraph extraction (Sec. (Sec.3.3). and cross- view mutual information (MI) maximization (See. (.4), which compose the SIGNET model. Finally, we introduce the self-interpretable GLAD inference (Sec. 3.5) of SIGNET. The overall learning
pipeline of SIGNET is demonstrated in Fig. 2(a)
3.1 MSIB Framework Overview
To achieve the goal of self-interprettable GLAD, an unsupervised learning approach that can jointly predict the abnormality of graphs and yield corresponding explanations is required. Inspired by the concept of information bottleneck (IB) and graph multi-view learning [36] 37 45). we propose multi-view subgraph information bottleneck (MSIB), a self-interpretable and self-supervised learning framework for GLAD. The learning objective of MSIB is to optimize the "bottleneck subgraphs", the vital substructure two distinct views of a graph, by maximizing the predictive structural information shared by both graph views while minimizing the superfluous information that is irrelevant to the cross-view agreement. Such an objective can be optimized in a self-supervised manner, without the guidance of ground-truth labels. Due to the observation that latent anomaly patterns of graphs can be effectively captured by multi-view learning R 9. we can directly use the cross- cross-view agreement, i.e., the MI between two views, to evaluate the abnormality of a graph sample. Simultaneously, the extracted bottleneck subgraphs provide us with graph rationales explain the anomaly detection predictions, since they contain the most compact substructure sourced from the original data and the most discriminative knowledge for the predicted abnormality, i.e., the estimated cross-view MI.
Formally, in the proposed MSIB framework, we assume each graph sample G has two different and distinguishable views GD and G2, Then, taking view G as an example, the target of MSIB is to learn bottleneck subgraph (+) for G by optimizing the following objective:
max I(G I G1(s)
-
(2)
Similar to MIB (Eq. (1 the optimization for G2(+), the bottleneck subgraph of G², can be written in the same format. Then, by parameterizing bottleneck subgraph extraction and unifying the domain of bottleneck subgraphs, the objective can be transferred to minimize a tractable loss function:
LMSIB (s) (G2())) + BDDKL (Po(G (5) ( G²2
where po ( (")) and py: (G2(s) G2) are the bottleneck subgraph extractors (parameterized by 0 and 1 for G¹ and G respectively, D (.) is the symmetrized Hellback-Leiblee (SKL) divergence, and B is trade-off hyper-parameter. Detailed deductions from Eq. (2) to Eq. (3) in Appendix D.
MSIB framework can guide us to build seff-interpretable GLAD model. The first term in Eq. (3) tries to maximize the MI between the bottleneck subgraphs from two views, which not only prompts the

---

view construction
(i)) battleneck
(tii) cross-view MI maximization
subgnaph extraction
Input graphs
G
h
maximize
k
GNN encoder
during training
Bottleneck subgraph extractor
DHT
DHT
provide explonations
I
1
HGNN encoder
indicates abrormality during inference
2"
6:
h
G
The overall pipeline of SIGNET
(b) DHT
Figure 2: (a) The overall pipeline of the proposed model SIGNET, consisting of (i) view construction, (ii) bottleneck subgraph extraction, and (ii) cross-view MI maximization. (b) An illustration of dual hypergraph transformation (DHT), where the nodes and edges (-) in the original graph correspond to hyperedges (...) and nodes in its dual hypergraph, respectively.
model to capture vital subgraphs but also helps capture the cross-view matching patterns for anomaly detection. The second term in Eq. (3) is a regularization term to align the extractors, which ensures the compactness of bottleneck subgraphs. During inference, (G) G2(+) can be regarded as a measure of abnormality. Meanwhile, the bottleneck subgraphs extracted by Po and ps: can serve as explanations. In the following subsections, we take SIGNET as practical implementation of MSIB framework. We illustrate the instantiations of view construction (G" and GP), subgraph extractors (pe and Pv), MI estimation (I)) G2()))), )), and explainable GLAD inference, respectively.
3.2 Dual Hypergraph-based View Construction
To implement MSIB framework for GLAD, the first step is construct two different and distin- guishable views G' and G2 for each sample G. In multi-view learning approaches [37 46
47
48
general strategy is using stochastic perturbation-ban based data augmentation (e.g., edge modification [46]
and feature perturbation (47)) to create multiple views. Despite their success in graph representation view constructions are not appropriate in SIGNET for the following reasons. 1) Low sensitivity to anomalies. Due to the similarity of normal and anomalous graphs in real-world data, perturbations may create anomaly- data from normal data as the augmented view [49]. In this case. maximizing the cross-view MI would result in reduced sensitivity of the model towards distinguishing between normal and abnormal data, hindering the performance of anomaly detection [50]. 2) Less differentiation. In the principle of MIB, two views should be distinguishable and mutually redundant (37). However, the views created by graph pertur- bation from the same sample can be similar to each other, which violates the assumption of our basic framework. 3) Harmful instability. The MI 7 ((G)(*) (²(+)) for abnormality measurement is highly related to the contents of two views. Nevertheless, the view contents generated by stochastic pertur- bation can be quite unstable due to the randomness, leading to inaccurate estimation of abnormality.
learning [46] 47 48), we claim that perturbation-
Considering the above limitations, perturbation-free, distinct, and stable strategy is required for view construction. To this end, we utilize dual hypergraph transformation (DHT) [51 construct the opposite view of the original graph. Concretely, for a graph sample G, we define the first view as itself (i.e., G = G) and the second view as its dual hypergraph G (i.e., G = G*). Based on the hypergraph duality 152 (3), dual hypergraph can be acquired from the original simple graph with DHT: each edge of the original graph is transformed into node of the dual hypergraph, and each node of the original graph is transformed into hyperedge of the dual hypergraph (51). As the example shown in Fig. 2(b) the structural roles of nodes and edges are interchanged by DHT, and the incidence matrix M of the dual hypergraph is the transpose of the incidence matrix of the original graph. To initialize the node features X E Xm of G", we either the original edge features (if available), or construct edge-level features from the original node features or according to edge-level geometric property.
The DHTT-based view construction brings several advantages. Firstly, the dual hypergraph has significantly distinct contents from the original view, which caters to the needs for differentiation in
5

---

MIB. Secondly, the dual hypergraph pays more attention to the edge-level information, encouraging the model to capture not only node-level but also edge-level anomaly patters. Thirdly, DHT is bijective mapping between two views, avoiding confusion between normal and abnormal samples. Fourthly, DHT' is randomness-free. ensuring the stable estimation of MI.
3.3 Bottleneck Subgraph Extraction
In MSIB framework, bottleneck subgraph extraction is key component that learns to refine the core rationale for abnormality explanations. Following the procedure of MSIB, we need to establish two bottleneck subgraph extractors for the original view G and dual hypergraph view G respectively. To model the discrete subgraph extraction process in differentiable manner with neural networks, following previous methods [4 22], we introduce continuous relaxation into the subgraph extractors. Specifically, for the original view G, model the subgraph extractor with po (G G)
He (v E )(*| (G). In practice, the GNN-based extractor takes G as input and outputs node probability vector p E RT*1, where each entry indicates the probability that the corresponding node belongs to G(+), Similarly, for the dual hypergraph view G an edge-centric HGNN serves as the subgraph extractor Ps. It takes G* as input and outputs an edge probability vector p* E RR=x1 that indicates if the dual nodes (corresponding to the edges in the original graphs) belong to G*(s), Once the probability vectors are calculated, the subgraph extraction can be executed by:
G-00= = (A, (A. O GO(,) = (M', x = (M", X Op)),
where @ is the row-wise production. Then, to implement the second term in Eq. (3) we can lift the node probabilities p edge probabilities p' by Píte,,) = P.P5, where I(ess) the index of edge connecting node v and Uj. After re-probabilizing p', the SKI. divergence between p' and p can be computed the regularization term in MSIB framework.
Although the above "two-extractor" design correlates to the theoretical framework of MSIB, in practice, it is non-trivial to ensure the consistency of two generated subgraphs only with an SKL divergence loss. The main reason is that the input and architectures of two extractors are quite different, leading to the difficulty in output alignment. However, the consistency of two bottleneck subgraphs not only guarantees the informativeness of cross-view MI for abnormality measurement, but also affects the quality of explanations. Considering the significance of preserving consistency, we use a single extractor to generate bottleneck subgraphs for two views. In specific, the bottleneck subgraph extractor first takes the original graph G as its input and outputs the node probability vector for the bottleneck subgraph extraction of Gl=), Then, leveraging the node-edge correspondence in DHT, we can directly lift the node probabilities to edge probability vector p* via Pi(e.,) = P.P, and re- o--robbbilization operation. p" can be used to extract subgraph for the dual hypergraph view. In this way, the generated bottleneck subgraphs two views can be highly correlated, enhaneing the quality of GLAD prediction (MI) and its explanations. Meanwhile, such a "single-extractor design further simplifies the model architecture by removing extra extractor and loss function (i.e., the DSKL term in Eq. (3). reducing the model complexity. Empirical comparison in Sec. 4.4 also validates the effectiveness of this design.
3.4 Cross-view MI Maximization
After bottleneck subgraph extraction, the next step is to maximize the MI [(G()) (*())) between the bottleneck subgraphs from two views. The estimated MI, in the testing phase, can be used to evaluate the graph-level abnormality. Owing to the discrete and complex nature of graph-structured data, is difficult to directly estimate the MI between two subgraphs. Alternatively, a feasible solution is to obtain compact representations for two subgraphs, and then, calculate the representation-lett MI as substitute. In SIGNET, we use message passing-bass based GNN and HGNN with pooling layer (formulated in Appendix C) to learn the subgraph representations ho and ho- for G(a) and (+),) respectively. In this case, I (G((); Go()) can be transferred into a tractable term, i... the MI between subgraph representations I (hgoo; hg+()).
After that, the MI term ((bo h ) can be maximized by using sample-based differentiable MI Jensen-Shannon Shannon (JS) estimator (54). Donsker- Varadhan (DV) estima-
lower bounds (37] such as Jensen-

---

tor [55] and Info-NCE estimator [56]. Due to its strong robustness and generalization ability [37 57]. we employ Info-NCE for MI estimation in SIGNET. Specifically, given a batch of graph samples B = (G1, GB), the training loss of SIGNET can be written by:
C (hogo (oo(
1
Σ
(Alh (no())n + ho("))
2|
2
G,EB
GEEB
erp (k((hot ha
E(hato, bo:()) = log
EG,eBra, exp S Su )
where fi(::-) is the cosine similarity function, T is the temperature hyper-parameter, and ( h a(o)) is calculated following ((h ahhaj ao(0))
3.5 Self-Interpretable GLAD Inference
In this subsection, we introduce the self-intern ceff-interpretable GLAD inference protocol with SIGNET (marked in red in Fig. 2(a) that composed of two parts: anomaly scoring and explanation.
Anomaly scoring. By minimizing Eq. (5) on training data, the cross-view matching patterns normal samples are well captured, leading to a higher MI for normal data; the contrary, the anomalies with anomalous attributal and structural characteristics tend to violate the matching patterns, resulting in their lower cross- view MI in model. Leveraging this property, during inference, the negative of MI can indicate the abnormality of testing data. For a testing sample Gg its anomaly score 8; can be calculated by s; = (h ( where the MI is estimated by Info-NCE.
Explanation. SIGNET, the bottleneck subgraph extractor is able to pinpoint the key substructure of the input graph under the guidance of MSIB framework. The learned bottleneck subgraphs are the most discriminative components of graph samples and are highly related to the anomaly scores. Therefore, can directly regard the bottleneck subgraphs the explanations of anomaly detection results. In specific, the node probabilities p and edge probabilities p can indicate the significance of nodes and edges, respectively. In practical inference, can pick the nodes/edges with top-k probabilities use threshold-based strategy acquire fixed-size explanation subgraph G(es).
More discussion about methodology. including the pseudo-code algorithm of SIGNET, the comparison between SIGNET and existing method, and the complexity analysis of SIGNET, is illustrated in Appendix E.
Experiments
In this section, extensive experiments are conducted answer three research questions:
RQ1: Can SIGNET provide informative explanations for the detection results?
RQ2: How effective SIGNET on identifying anomalous graph samples?
RQ3: What are the contributions of the core designs in SIGNET model?
4.1
Experimental Setup
Datasets. For the explainable GLAD task, we introduce 6 datasets with ground truth explanations, including three synthetic datasets and three real-world datasets. Details are demonstrated below. We also verify the anomaly detection performance of SIGNET on 10 TU datasets [58], following the setting in (4. Detailed statisties and visualization datasets are demonstrated in Appendix F.I.
BT- BM-MN, and BM-MS are three synthetic dataset created by following [13] 19]. Each graph composed of one base (Tree, Ladder, or Wheel) and one or more motifs that decide the abnormality of the graph. For BM-MTT (motif type), each normal graph has house motif and each anomaly has a 5-cycle motif. For BM-MN (motif number), each normal graph has house motifs and each anomaly has 3 or 4 house motifs. For BM-MS (motif size), each normal graph has a cycle motif with 3-5 nodes and each anomaly has a cycle motif with 6-9 nodes. The ground-truth -runt explanations are defined as the nodes/edges within motifs.
7

---

Table 1: Explanation performance in terms of NX-AUC and EX-AUC (in percent, mean + std). The best and runner-up results are highlighted with bold and underline, respectively.
Dataset
Metric
OCGIN-GE
GLoxaIKD-GE
OCGTL-GE
OCGIN-IG
GLesalD-PPi
OCGTL-PG
STGNET
BM-MT
NX-AUC
EX-AUC
62 02.03
18 2lissus
20.11a9
29t a8.67au..
49 49.80 se
45. 25.70
64.88mm2
74.00
72.72210.1
77.69 13.91111.
78. 78.41:aas
BM-MN
NX-AUC
46 25
60:02enav
50.17es14
48 10
40 40.53a8.t
56.31es.10
51.1esm
78.68ea
71.36
76, 76.57
AX-AUC
52. 4361.7
50. 13
53. 4.
76.43:
BM-MS
EX-AUC
29. 10a2 ze
66.8 66.87
43.67
82 32.53.
77. 17.15e
79. 18
MNIST-O
NX-AUC
19. 48eaas
50.11
38, 87.877
70. 500.88
49.75a0.35
41.42=2:40
39.53ea.01
51.09
39.25ies.os
72.78:7.2
MNIST-1
AX-
EX-AUC
48. 21
18. 00.3.2
40. 20.50s..50
28
47.04:1..0
45.20e1.11
47 47.98
49.21es
57 0de..8
:4.83:5.24
68. 3..44:
MUTAG
NX-AUC
EX-AUC
61.92
18. 99.99
47.05
09.70s1.13
45.80
19.51sam
46.22
70:47.5.0
65.00
75.60 25.60
78.05...19
MNIST-O and MNIST-1 are two GLAD datasets derived from MNIST-75sp superpixel dataset [59] Following [60], we consider specific class (i.e., digit 0 or I) as the normal class, and regard the samples belonging to other classes as anomalies. The ground-truth explanations are the nodes/edges with nonzero pixel values.
MUTAG is a molecular property prediction dataset [61]. We set nonmutagenic molecules as normal samples and mutagenic molecules as anomalies. Following 20 -NO2 and -NH2 in mutagenic
molecules are viewed as ground-truth explanations.
Baselines. Considering their competitive performance, consider three state-of- -hrt deep GLAD methods, i.c., OCGIN 77. GLocalKD [4], and OCGTL (8) as baselines. To provide explanations for them, we integrate two mainstream post-hoc GNN explainers, i.e., GNNExplainer [19] (GE for short)
and PGExplainer [20] (PG for short) into the deep GLAD methods. For GLAD tasks, we further
introduce the baselines composed of a graph kernel (i.e., Weisfeiler-Lehman kernel (WL) 62 or
Propagation kernel (PK) 63) and a detector (i.e., iFForett (iF) 64 or one-class SVM (OCSVM) 65
Metrics and Implementation. For interpretation evaluation, report explanation ROC-AUCs at node level (NX-AUC) and edge level (EX-AUC) respectively, similar to 19 20 performance, report the ROC-AUC w.r.t. anomaly scores and labels (AD-AUC) 5 times for all experiments and record the average performance. In SIGNET, we use GIN (2 and Hyper-Conv 30] as the GNN and HGNN encoders. The bottleneck subgraph extractor is selected from GIN [2] and MLP. We perform grid search to pick the key hyper-parametee in SIGNET and baselines. More details of implementation and infrastructures are in Appendix F. Our code is available at httpg/thww..cmm/iiiiiiiiu///////
For GLAD
7 We repeat
4.2 Explainability Results (RQ1)
Quantitative evaluation. In Table I we report the node- level and edge-level explanation ACC 22) on 6 datasets, Note that PGExplainer (20) can only provide edge-level explanations natively. We have the following observa- tions: 1) SIGNET achieves SOTA performance in almost all scenarios. Compared to the best baselines, the average performance gains of SIGNET are 27.89% in NX-AUC and 8.99% in EX-AUC. The superior performance ver- ifies the significance of learning to interpret and detect with a unified model. 2) The post-hoc explainers are not compatible with all GLAD models. For instance, PGEx- plainer works relevantly well with GLocalKD but cannot provide informative explanations for OCGIN. The GN- NExplainer, unfortunately, exhibits poor performance in most scenarios. 3) SIGNET has larger performance gains on real-world datasets, which illustrates the potential of SIGNET in explaining real-world GLAD tasks. 4) Despite its superior performance, the stubility of SIGNET rele- vantly average. Especially the synthetic datasets, can find that the standard deviations of
Dataset
Motif'
Explaration by SIGNET
normal
anomaly
nommal
anomaly
BM-MT
BM--N
x3-4
t
BM-MS
xx3-5
xx6s
Figure 3: Visualization of explanation
results w.r.t. node and edge probabilities.

---

Table 2: Anomaly detection performance in terms of AD-AUC (in percent, mean + std). The best and runner-up results are highlighted with bold and underline, respectively.
Dataset
PK-OCSVM
PK-iF
WL-OCSVM
WL-IF
OCGIN
GLocalD
OCGIL
SIGNET
BM-MT
52. 38
45.30a1 co
53, 36.362 os
501 00.30:00.0
73.33e6
74.94 ta
US 40.61
95 80 75
BM-MN
56 80
76 60
29.93 20.90=020
39.35+281
77.51=30:
99.19:0.05
93.41=1.0
79.34:0.52
16.00
16.19
58.00.3.44
65.00
94-01::4.0
MNIST-0
48.89=2.19
59. 59.58
67
30.27=2245
69.54.2.6
82 62.29-11
80.68-2.54
25.225222 57
MNIST-1
43.45.11-38
18.9715554
63.641240
3..05_3..
98. 10.00
000004
97 .7 10.36
90.1215.3
MUTAG
13.30
13.0
19.6422..9
29.07=0.32
37.59k8.90
63-4142.40
PROTBINS+
50. 60.40::499
60. 00.70a2..0 86
31.361224 35
61. .3.00::. 64
70.80 70.89
77. 540 16
76.51+1.00
75:22
ENZYMES
53. 13.66
61 30..
50.24 (5.244..
51 31.00_3341
58. 77.7752.00
61.31
02.00639.00
62. 966.
50.12+5.44
01.13300.2
78.16+s.0r
93.27=44 19
97.27
DHER
47.91
62. +2..0
50.24
50.29 20.29
49.23
56.71
50.90=2..6
74.01:4.o
BZR
46.85155.31
65.3216.10
5015661544
32.46_3.30
65.9
09.42 7.24
63.9418440
81 11.4411
COX2
60.05-+2.00
DD
18.30=53.0
71.92+2.41
47.99 4..99
70.31:1100
72.27=1.83
80. 12:5 24
79, 78.4842222
72.72a5.01
NCII
49.90.11::
50.58.1.3M
50.6631..22
50.74_1.70
71.98.1.21
68.48
73.44
74. 11.8891200
IMDH-B
50.76:9.10
50:201:0.0
52200158.41
64 04:006.9.2
REDDIT-B
25.68=2.24
16.7249.42
19.31
28. 28.201-0.32
73.93es.03
77.85=243
86.81=2.10
82.78e111
Avg. Rank
6.6
8.1
6.2
6.4
4.1
2.8
2.1
1.7
NX-AUC and EX-AUC are large. We speculate that the instability is due to the lack of labels that provide reliable supervisory signals for anomaly detection explanations.
Qualitative evaluation. To better understand the behavior of SIGNET, we visualize the explanations (i.e., node and edge probabilities) in Fig. We can witness that SIGNET can assign larger probabilities for the nodes and edges within the discriminative motifs, providing valid explanations for the GLAD predictions. In contrast, the probabilities of base subgraphs are uniformly small, indicating that SIGNET able to ignore the unrelated substructure. However, we can still witness some irrelevant nodes included in the explanations in the anomaly sample of BM-MN dataset, which indicates that SIGNET may generate noisy explanations in some special cases.
4.3 Anomaly Detection Results (RQ2)
To investigate the anomaly detection performance of SIGNET, we conduct experiments on 16 datasets and summarize the results in Table 2 The following observations can be concluded: 1) SIGNET outperforms all baselines main reason is that SIGNET can capture graph patterns at node and edge level with two distinct the key substructure during anomaly scoring. 2) The deep GLAD methods
the rest. The 10 datasets and achieves competitive performance
views and concentrate generally perform better than dernel-based methods, indicating that GNN-based deep learning models effective in identifying anomalous graphs. To sum up, SIGNET can not only accurately detect anomalies but also provide informative interpretations for the predictions.
4.4 Ablation Study (RQ3)
We perform ablation studies to evalu- ate the effectiveness of core designs in SIGNET, i.e., dual hypergraph- based view construction, single extractor, and InfoNCE MI estimator. We re- place these components with alterna- tive designs, and the results are il- lustrated in Table 3 We consider two strategies for view construction: augmentation-batt based view construc-
Table 3: Performance of SIGNET and its variants.
Variunt
BM-MS
MNIST-0
NX-AUC
EX-AUC
AD.AUC
NX.AUC
EX-AUC
AD-AUC
Aug. View Str. View
66.87
64.48
63.26
41.82
39.25
48.75
70.36
68.27
92.79
51.73
50.40
50.29
w Dexr
59.22
2E. w/o DSKt.
73.54
37.15
87.84
57.92
43.65
80.97
MI Est. 70.35
68.96
75.21
30.06
63.85
71.78
DV MI Est.
72.53
74.16
74.87
00.90
70:28
70.31
STGIET
76.42
79.48
94.01
70.38
72.78
83.25
tion [6]] (Aug. View) and structural
property- based view construction [50] (Str. View). As we discussed in Sec. 3.2 perturbation-baase graph augmentation is not appropriate for GLAD tasks, leading to its poor performance. The structural property-based strategy has better performance on BM-BT but still performs weakly on MNIST-O, In contrast, dual hypergraph-baat bassdd view construction a better strategy that jointly considers node-level and edge-level information, contributing to optimal detection and explanation performance. We also test the performance of SIGNET with two extractors (2F) and discuss the contribution of SKI. diver- gence. We can find that even with the help of DSKL. the two-extractor version still underperforms

---

the original SIGNET with one extractor. Meanwhile, we can witness that compared to JS [54] and DV [55] MI estimators, Info-NCE estimator can lead to superior performance, especially for anomaly detection.
5 Conclusion
This paper presents a novel and practical research problem, explainable graph-level anomaly detec- tion (GLAD). Based on the information bottleneck principle, we deduce the framework multi-view subgraph information bottleneck (MSIB) to address the explainable GLAD problem. We develop a new method termed SIGNET by instantiating MSIB framework with advanced neural modules. Extensive experiments verify the effectiveness of SIGNET in identifying anomalies and providing explanations. A limitation our paper is that we mainly focus on purely unsupervised GLAD scenar- ios where ground-truth labels are entirely unavailable. As result, for few-shot or semi-supervised GLAD scenarios [4 where a few labels are accessible, SIGNET cannot directly leverage them for model training and self-interpretation. We leave the exploration of supervised/semiisupere self-interpretabbl GLAD problems in future works.
Acknowledgment
S. Pan was partially supported by Australian Research Council (ARC) Future Fellowship (FT210100097). F. Li was supported by the National Natural Scientific Foundation of China (No. 62202388) and the National Key Research and Development Program of China (No. A022YFF1000100)
References
[1] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A compre- hensive survey graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24, 2020.
[2] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations. 2019.
[3] Xin Zheng, Yixin Liu, Zhifeng Bao, Meng Fang, Xia Hu, Alan Wee-Chung Liew, and Shirui Pan. Towards data-centric graph machine learning: Review and outlook. arXiv preprint arXiv:2309. 10979, 2023.
Rongrong Ma. Guansong Pang, Ling Chen, and Anton van den Hengel. Deep graph-level anomaly detection by glocal knowledge distillation. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pages 104-714,77 2022.
[5] Charu C Aggarwal and Haixun Wang. Graph data management and mining: survey of algorithms and applications. Managing and mining graph data, pages 13-68, 2010.
[6] Tommaso Lanciano, Francesco Bonchi, and Aristides Gionis. Explainable classification of brain networks via contrast subgraphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3308-3318, 2020.
[7] Lingxiao Zhao and Leman Akoglu. On using classification datasets to evaluate graph outlier detection: Peculiar observations and new insights. Big Data, 2021.
[8] Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph. Raising the bar in graph- level anomaly detection. In Proceedings of the Thirty-Firs. International Joint Conference Artificial Intelligence, IJCAI-22, pages 2196-2203, 2022.
[9] Xuexiong Luo, Jia Wu, Jian Yang, Shan Xue, Hao Peng, Chuan Zhou, Hongyang Chen, Zhao Li, and Quan Sheng. Deep graph level anomaly detection with contrastive learning. Scientific Reports, 12(1):19867, 2022.
[10] Philipp Liznerski, Lukas Ruff, Robert A Vandermeulen. Billy Joe Franks, Marius Kloft, and Klaus Robert Muller. Explainable deep one-class classification. In International Conference on Learning Representations, 2021.
[11] Suseela T Sarasamma, Qiuming A Zhu, and Julie Huff. Hierarchical kohonenen net for anomaly detection in network security. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cyberneties), 35(2):302- 312, 2005.
10

---

[12] Grégoire Montavon, Wojciech Samek, and Klaus-Robert Müller. Methods for interpreting and understand- ing deep neural networks. Digital signal processing, 73:1-15, 2018.
[13] Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat- Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022.
[14] Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan Hc, and Tat-Seng Chua. Let invariant rationalc discovery inspire graph contrastive learning. In International Conference on Machine Learning, pages 13052-13065. PMLR, 2022.
[15] Hongzuo Xu, Yijie Wang, Songlei Jian, Zhenyu Huang, Yongjun Wang, Ning Liu, and Fei Li. Beyond outlier detection: Outlier interpretation by attention-guia -oudddd triplet deviation network. In Proceedings of the Web Conference 2021, pages 1328 1339,,13..0100 2021.
[16] Wonwoo Cho. Jeonghoon Park, and Jacgul Choo. Training auxiliary prototypical classifiers for explainable anomaly detection medical image segmentation. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 2624 2633, 2023.
[17] Junchi Yu, Tingyang Xu, Rong, Yatao Bian, Junzhou Huang, and Ran He. Graph information bottleneck for subgraph recognition. In International Conference on Learning Representations, 2021.
[18] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[19] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik. and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
[20] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 13:19660-1963, 2020.
[21] Eayan Dai and Suhang Wang. Towards self-explainable graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 302-311, 2021.
[22] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524 15543,, PMLR, 2022.
[23] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[24] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, volume 30, 2017.
[25] Kaize Ding, Jundong Li. Rohit Bhanushali, and Huan Liu. Deep anomaly detection on attributed networks. In Proceedings of the 2019 SIAM International Conference on Data Mining, pages 594-602. SIAM, 2019.
[26] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[27] Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph leamning: A survey. ACM SIGKDD Explorations Newsletter, 24(2):61-77, 2022.
[28] Yixin Liu, Kaize Ding, Jianling Wang, Vincent Lee, Huan Liu, and Shirui Pan. Learning strong graph neural networks with weak information. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2023.
[29] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3558-3565, 2019.
[30] Song Bai, Feihu Zhang, and Philip HS Torr. Hypergraph convolution and hypergraph attention. Pattern Recognition, 110 107637, 2021.
[31] Naganand Yadati, Madhav Nimishakavi, Prateek Yaday, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. Advances in neural information processing systems, 32, 2019.
[32] He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong, and Jian Pei. Trustworthy graph neural networks: Aspects, methods and trends. arXiv preprint arXiv:2205.07424. 2022.
11

---

[33] Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33:12225-12233 2020.
[34] N TISHBY. The information bottleneck method. In Proceedings of the 37-thAnnual Allerton Conference Communication, 2000, 2000.
[35] Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (itw), pages 1-5. IEEE, 2015.
[36] Alexander A Alemi, Ian Fischer, Joshua V Dillon, and Kevin Murphy. Deep variational information bottleneck. In International Conference on Learning Representations, 2017.
[37] Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata. Learning robust represen- tations via multi-view information bottleneck. In International Conference on Learning Representations, 2020.
[38] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances Neural Information Processing Systems, 14:15920-15933, 2021.
[39] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information-awwre graph contrastive learning. Advances in Neural Information Processing Systems, 14:30414-30422 2021.
[40] Junchi Yu, Jie Cao, and Ran He. Improving subgraph recognition with variational graph information bottleneck. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 19396-19405, 2022.
[41] Chunyu Wei, Jian Liang, Di Liu, and Fei Wang. Contrastive graph structure learning via information bottleneck for recommendation. Advances in Neural Information Processing Systems, 35:20407-20420, 2022.
[42] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. Advances in Neural Information Processing Systems, 33:20437-20048, 2020.
[43] Qingyun Sun, Jianxin Li, Hao Peng, Jia Wu, Xingcheng Fu, Cheng Ji, and S Yu Philip. Graph structure learning with variational information bottleneck. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 4165-4174, 2022.
[44] Ge Zhang, Zhenyu Yang, Jia Wu, Jian Yang. Shan Xue, Hao Peng, Jianlin Su, Chuan Zhou, Quan Z Shenng. Leman Akoglu, al. mual-discriminative graph neural network for imbalanced graph-level anomaly detection. Advances in Neural Information Processing Systems, 35:24144-241577 2022.
[45] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pages 4116-4126. PMIR, 2020.
[46] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, volume 33, pages 5812-5823, 2020.
[47] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pages 2069-2080, 2021.
[48] Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent CS Lee, and Shirui Pan. Beyond smoothing: Unsu- pervised graph representation learning with edge heterophily discriminating. In Proceedings of the AAAI conference artificial intelligence, volume 37, pages 451 451444,2, 2023.
[49] Izhak Golan and Ran El- Yani.. Deep anomaly detection using geometric transformations. Advances in neural information processing systems, 31, 2018.
[50] Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. Good-d: On unsupervised graph out-of -utto--distribution detection. In Proceedings of the Sixteenth ACM International Conference Web Search and Data Mining, pages 339-347, 2023.
[51] Jachyeong Jo. Jinheon Back, Seul Lee, Dongki Kim, Minki Kang, and Sung Ju Hwang. Edge representation learning with hypergraphs. Advances in Neural Information Processing Systems, 34:7534-7546, 2021.
[52] Claude Berge. Graphs and hypergraphs. North-Holland Pub, Co., 1973.
[53] Edward R Scheinerman and Daniel H Ullman. Fractional graph theory: a rational approach to the theory of graphs. Courier Corporation, 2011.
12

---

[54] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
[55] Monroe D Donsker and SR Srinivasa Varadhan. Asymptotic evaluation of certain markow process expectations for large time, i. Communications Pure and Applied Mathematics, 28(1):1-47, 1975.
[56] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint arXiv:1807.03748. 2018.
[57] Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PMLR. 2020.
[58] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: collection of benehmark datasets for learning with graphs. In JCML Workshop. 2020.
[59] Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks, Advances neural information processing xystems, 32, 2019.
[60] Lukas Ruff, Rohert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexander Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. In International conference on machine learning, pages 4393-4402. PMLR, 2018.
[61] Asim Kumar Debnath, Rosa I. Lopez Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786 797777 1991.
[62] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lhhman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[63] Marion Neumann, Roman Garnett Christian Bauckhage, and Kristian Kersting. Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102:209-2455 2016.
[64] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In 2008 eighth ieee international conference data mining, pages 413-422. IEEE, 2008.
[65] Larry M Manevitz and Malik Yousef, One-class syms for document classification. Journal of machine Learning research, 139-))))33-15,,, 2001.
13


Reviews:
[{"review_id": "zetcjBwvCr", "reviewer": "Reviewer_6qZe", "summary": "This paper studies graph-level anomaly detection (GLAD), which aims to find the anomalous graphs. To construct an explainable GLAD under an unsupervised manner, the authors first proposed a multi-view subgraph information bottleneck (MSIB) framework and then introduce a dual hypergraph as a supplemental view of the original graph. The core contribution of the paper is the designing of a self-explainable GLAD model. ", "questions": "1. Suggestion: the authors should discuss more and provide more examples about the explanabilty of the model in RQ1 and in Figure 3. There are only visualizations for synthetic datasets. I believe readers would be more interested in these (rather than performance). The advantages of the proposed explanable GLAD model over existing explanable models should be clearly presented. ", "limitations": "Authors slightly discussed the model limitations in the Conclusion section. More discussions w.r.t. complexity and dataset-type applicability are needed. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Explainable AI is important for many real-world applications that highlight interpretability and security. The proposed framework is explainable by the model itself (rather than post-hoc explainers). \n\n1. Using two different and distinguishable views to train the MSIB framework for graph-level anomaly detection is reasonable and sound. The authors also used cross-view MI maximization for estimating MI between two compact subgraph representations. ", "weaknesses": "1. The authors stated \"this is the first attempt to study the explainability problem for anomaly detection on graph-structured data\". However, there are works on node-level graph anomaly detection, both supervised and unsupervised and self-supervised. Better use \"graph-level anomaly detection\" here. \n\n1. The proposed model is a little heavy and introduces non-trivial computational overhead. The trade-off between scalability and interpretability (there are also other efficient methods for explainable graph-level representation learning) should be considered. Complexity and run-time analysis should be reflected in the paper -- given the overhead of computing on multiple subgraphs. \n\n1. Statistics of all datasets should be provided, e.g., avg. number of nodes, density of the graph.\n\n1. All methods on GLAD seem to be unstable and less robust on the detection performance (with extremely high std). The evaluation of the effectiveness of the proposed method (RQ2 and RQ3) seems to be trivial and \"boring\". I suggest the authors to emphasize more on the RQ1.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Reviewer 6qZe**\n\nWe appreciate Reviewer 6qZe for the positive review and constructive comments. We provide our responses as follows.\n\n**Q1: Complexity and run-time analysis of the proposed method**\n\n**A1:** We appreciate your concern regarding the computational overhead and the trade-off between scalability and interpretability in our proposed model. In response to these concerns, we conduct a comprehensive time complexity analysis, which is attached to the general response and will display in the revised paper. The analysis shows that the time complexity of SIGNET is $\\mathcal{O}(NLd^2(m+n) + Nnd(d_f+d_{f*}) + NBd)$, which is comparable to mainstream GNN-based models, including our baselines. From the analysis, we can also find that although the self-interpretable block (i.e., subgraph extractor) may introduce some additional time complexity, it is designed as a lightweight module compared to the entire anomaly detection framework and would not increase the overall scale of time complexity.\n\nAdditionally, we provide a comparison between our method and baseline methods (including GOOD-D [1], the strong baseline pointed out by Reviewer QzdR) in terms of running time per epoch, as shown in the table below. This comparison illustrates that while our method provides self-interpretation capabilities, it still maintains competitive running efficiency. Specifically, on the dataset with larger graphs (MNIST-0), the runtime per epoch is very close to the most efficient baseline OCGIN, and is 6.5x faster than the strong baseline OCGTL. Therefore, the running efficiency of SIGNET would not be a large concern.\n\n|Dataset|OCGIN|GLocalKD|OCGTL|GOOD-D|SIGNET(ours)|\n|-|-|-|-|-|-|\n|BM-MT|0.0457s|0.0535s|0.2624s|0.3036s|0.0720s|\n|MNIST-0|0.1213s|0.3498s |0.8019s|0.5937s|0.1273s |\n\n[1] Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. Good-d: On unsupervised graph out-of-distribution detection. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 339–347, 2023.\n\n**Q2: More discussion for explainability (RQ1)**\n\n**A2:** We appreciate your interest in the explainability of our proposed GLAD method and the importance of providing more examples and discussions. In the revised version of our paper, we will dedicate more attention to the model's explainability, discussing it in greater detail and providing additional examples. We acknowledge the significance of visualizations, as they offer a clear and intuitive understanding of the model's explanations. According to your suggestion, we have prepared more visualization results, which are included in the attached PDF and will be incorporated into the revised paper. These visualizations include the results on a real-world dataset MUTAG dataset. More visualization examples will be displayed when we open-source our code. I hope the extra results can address your concerns about the explainability of our method.\n\n**Q3: Detailed statistics of datasets**\n\n**A3:** Thanks for the kind suggestion! In response to the space limitations, we will move the dataset statistics to Appendix F in the supplementary material. We understand the importance of easy access, so we will clearly highlight the specific section in the revised version. Additionally, we will include more details, such as the density of graphs, as suggested by the reviewers. \n\n**Q4: Statement about “first attempt” contribution**\n\n**A4:** We appreciate your suggestion. While there have been previous works on node-level graph anomaly detection, our paper specifically focuses on the explainability problem for graph-level anomaly detection. To clarify this, we will use the term “graph-level anomaly detection” as our first-attempt contribution in the revised version. Thank you for helping us improve the accuracy of our paper. \n"}, {"review_id": "VU1w3wzgN0", "reviewer": "Reviewer_yuBa", "summary": "To overcome the disadvantage of existing anomaly detection methods that fail to provide meaningful explanations for the predictions, this paper proposes SIGNET to (1) detects anomalous graphs and (2) generate informative explanations. To achieve this, the paper devises a multi-view subgraph information bottleneck framework to extract the informative subgraphs as explanations. Empirical results on 16 datasets verify the effectiveness of the proposed method.", "questions": "- For the anomaly detection performance, Table 2 shows that SIGNET is outperformed by the three baselines in some cases. What are the reasons here? Is there a natural tradeoff between accuracy and interpretability?\n- The MI estimation appears many times. How does the paper conduct the MI estimation in a tractable and differentiable way? Equation (3) seems confusing for including the MI and SKL divergence. \n- Besides, how does Equation (5) correlate with Equation (3), is Equation (5) also an MI estimation?", "limitations": "Please refer to the above Weaknesses and Questions. \n\nI would consider raising my score if the above questions are well answered.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The investigated problem is novel and important, as robustness and interpretability are the key sub-areas of trustworthy graph learning.\n- The paper is easy to follow, with generally clear writing and illustration.\n- The proposed SIGNET is technically solid, with good and competitive empirical results.\n- Some preliminary analyses in terms of information theory are conducted.", "weaknesses": "- The technical contributions are neutral. The proposed MSIB framework seems to be a combination of information bottleneck and graph multi-view learning, while the novelty and difficulty are not clear.\n- The answers to \"RQ1: Can SIGNET provide informative explanations for the detection results\" are not convincing enough, which should be the key contribution of the paper. The reasons are as follows.\n- The two compared GNN explainers, GNNExplainer and PGExplainer, are not up-to-date. The latest and state-of-the-art explainers, e.g., GSAT (ICML'22) [22], should also be considered and discussed. \n- Note that GSAT is also derived from the information bottleneck, which shares a similar design as the proposed SIGNET. I would suggest the paper discuss more the connection and differences.\n- Besides, directly combining GNN explainers and anomaly detection methods, e.g., OCGIN-GE, can be sub-optimal, as shown in Table 1. The paper should explain more about the baseline settings, that is, why such a combination is reasonable, but the results show that it does not work well in most cases.\n- The few cases shown in Figure 3 are insufficient, which are not promising and convincing enough. It seems that SIGNET learns to capture the same (similar) functional sub-graph (or motif) for both normal and anomaly samples. I would suggest the paper show more cases and provide an in-depth analysis, which will add more value to the main contribution, i.e., interpretability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Reviewer yuBa**\n\nWe appreciate Reviewer yuBa for the perception of our contributions and thank the reviewer for the insightful feedback. We provide our responses as follows.\n\n**Q1: Technical contribution of this paper**\n\n**A1:** Thanks for the valuable feedback. Our work embarks on an important and challenging research direction, representing the first step towards integrating self-interpretability into graph-level anomaly detection (GLAD), thereby serving as an inspirational catalyst for future advancements in this domain. It's essential to note that our proposed method transcends a mere combination of existing techniques. The Multi-View Subgraph Information Bottleneck (MSIB) framework is thoughtfully crafted to address the demands of unsupervised self-interpretable GLAD with sound motivation and solid deduction. Building upon this framework, we introduce several innovative designs to effectively tackle the intricacies of the research problem. We greatly value the reviewer's feedback and wish to emphasize that our paper introduces a pioneering GLAD method with inherent self-interpretability, carving a unique path distinct from existing approaches, and our work holds the potential to inspire future research in the evolving field of GLAD.\n\n**Q2: Compared to state-of-the-art explainers**\n\n**A2:** Thanks for the kind suggestion. We understand the importance of considering other state-of-the-art explainers for comparison. However, regarding GSAT, we acknowledge that it is a self-interpretable GNN that requires labels for training. Unfortunately, in our GLAD setting, we do not have access to labels. As a result, we cannot directly compare our approach with GSAT.\n\nTo address the reviewer's concern and ensure comprehensive evaluation, we have introduced one of the latest post-hoc explainers, RC-Explainer (TPAMI 2022 [1]), for comparison. The comparison (w.r.t. EX-AUC) below shows that SIGNET continues to outperform RC-Explainer on three datasets, reaffirming that the combination of trained detectors and post-hoc explainers typically provides sub-optimal explainability.\n\n|Methods|BM-MN|MNIST-0|MNIST-1|\n|-|-|-|-|\n|GLocalKD-RC|71.87|63.56|61.67| \n|OCGTL-RC|68.50|66.83|63.22|\n|SIGNET|83.45|72.78|74.83|\n\n[1] Wang et al. \"Reinforced causal explainer for graph neural networks.\" IEEE TPAMI (2022).\n\n**Q3: Connection and differences with GSAT**\n\n**A3:** Thanks for the valuable comment. Following the reviewer's suggestion, we will include the connections and differences between our method (SIGNET) and GSAT in the revised paper, see P4 in general response.\n\n**Q4: Discussion about “detector+explainer” baselines**\n\n**A4:** Thanks for your valuable feedback! Regarding the implementation details, we will add them to the revised paper and we also attach them to P2 in general response. We claim that the combination is reasonable because the mechanism of post-hoc explainers is to parameterize the input graph and find the input that can generate the ideal output under several conditions, serving as the explanation. Since the baseline GLAD methods are deep learning models with graph-level input and scalar output, it is feasible to use the post-hoc explainer to explain their prediction, similar to the explanation process of classification models. \n\nHowever, such a combination would lead to sub-optimal performance since the GLAD model and explainer are trained independently, which might not ensure optimal alignment between the two components during training. Consequently, this leads to the mismatch between the generated explanations and true decision boundaries learned by GLAD model. In contrast, SIGNET avoids this potential mismatch by incorporating interpretability into the detection model, allowing for joint learning of prediction and interpretation. By optimizing a unified objective for detection and explanation, SIGNET can align its learned decision boundaries with the generated explanations effectively. \n\n**Q5: More case studies**\n\n**A5:** Thanks for the valuable suggestion! In response to your feedback, we have prepared more visualization results (including real-world dataset MUTAG), which are included in the attached PDF. With the new results, we will provide a detailed analysis in the revised paper.\n\n**Q6: Discussion about anomaly detection (AD) performance**\n\n**A6:** Thanks for the kind suggestion. While SIGNET has demonstrated strong AD performance on most benchmark datasets, we acknowledge that there are cases where it is outperformed by some of the baselines. A possible reason for this is the dataset characteristics. Different datasets may have varying levels of complexity and distribution of anomalies, which can impact the performance of AD methods. Some baselines might be more suitable for certain datasets due to their specific design and assumptions, leading to their better performance. \n\n**Q7: Details of MI estimation in SIGNET**\n\n**A7:** Thanks for the thoughtful comment. MI plays a critical role in our proposed MSIB framework, specifically in the first term of Eq.(3). However, estimating MI can be challenging, especially with limited examples instead of the variable distribution itself. Fortunately, [2] introduced parametrized MI estimators that offer a tractable and differentiable way to estimate MI using neural networks. In SIGNET, we adopt the Info-NCE (Eq.(5)) for MI estimation due to its generalization ability (see the 2nd paragraph of Sec. 3.4). Experiments in Sec. 4.4 shows the superiority of Info-NCE over other estimators.\n\nTo correlate Eq.(3) with Eq.(5), instead of minimizing the SKL between two extractors, we utilize a unified subgraph extractor to estimate the subgraph for both views (see the 2nd paragraph of Sec. 3.3). This naturally aligns the two distributions without the need to minimize their SKL. Consequently, we can omit the second term in Eq.(3), leading to Eq.(5).\n\n[2] Tschannen et al. \"On Mutual Information Maximization for Representation Learning.\" ICLR (2020)."}, {"review_id": "nuunwQFG0v", "reviewer": "Reviewer_vtQs", "summary": "The paper tackles the task of graph anomaly detection. It proposes a multi-view subgraph information bottleneck framework that is used to introduce SIGNET, a self-interpretable graph anomaly detection method. The method leverages the dual hypergraph transformation to obtain two views of the same graph, which are subsequently used for a mutual information maximization objective. The resulting model can then be employed to detect anomalous samples in the dataset and provides an implicit explainability mechanism that can highlight salient regions of the graph.\n", "questions": "- Do the datasets used contain anomalies in the training set? I would love to see an analysis of the performance with respect to the anomaly contamination percentage in the training data.\n\n- The overall objective would also be interesting for general unsupervised graph representation learning. Have the authors tried using the graph representations for downstream tasks? I'm not requesting this experiment to be done since it's outside the scope of the paper; it's just something I have thought about while reading it. I imagine the results would not be great since the two views are somewhat similar.\n\n- Did the authors search for any hyperparameters for the baselines?\n\n- Did the authors examine any other qualitative results?", "limitations": "- The authors have addressed their limitations regarding the inability to use ground-truth labels when training their model, making it entirely unsupervised. Expanding the discussion of the limitations, potentially with negative qualitative results, would be beneficial. Discussing FP/FN samples obtained by picking some anomaly threshold would also be interesting since the model could provide explanations.\n", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written, and the ideas presented are exposed in an easy-to-follow manner.\n\n- The authors present compelling arguments for their design choices, an ablation study, and the derivation of the loss function in the Supplementary materials.\n\n- The Supplementary materials contain the code for the proposed approach and various details about the experimental setup, such as the hyperparameter pool used during hyperparameter selection.\n\n- The quantitative results are compelling, and the proposed method obtains the best results in most cases. Adequate baselines were selected for the experiments, containing both neural approaches and more classical AD methods, such as the OC-SVM with a WL kernel.", "weaknesses": "- The paper focuses on presenting an explainability/interpretability mechanism instead of an anomaly detection pipeline with an explainability mechanism built in. The usage of the dual hypergraph view in the context of training an anomaly detector is novel in its own right. The main results for anomaly detection in Table 2 are also good. An explainability mechanism is a very important addition, but I would prefer it not to be the paper's primary focus. The strong emphasis on explainability made me think that the authors were not confident in the anomaly detection model, which in my eyes, should be pitched as the main strength of the paper.\n\n- The qualitative analysis of the explanations is somewhat lacking. A more detailed caption for Fig. 3, which also explains what the highlighted nodes and edges represent, would improve readability. It looks to me that the model highlights the motifs in both the normal and anomaly scenarios, but I would have expected it to highlight the motif in the anomalous graphs more. I would also like more qualitative results, especially on real-world datasets. Figure 3 is overall somewhat confusing and makes me feel like the examples might be cherry-picked.\n\n- As far as I'm aware, the NX-AUC and EX-AUC metrics are not very common. Please consider expanding their meaning in the main paper or the Supplementary materials.\n\n- I don't particularly like the \"cartoon\"-style fonts used in Fig. 1 and Fig. 2., please consider some alternatives. However, this is a subjective stylistic opinion and won't affect my final score for the paper. \n\n- I have not seen any mention of hyperparameter selection for the baselines. Some classical methods (such as the OC-SVM) are particularly sensitive to hyperparameters. Please consider adding a discussion regarding this.\n\n- It would be insightful if the paper would further discuss potential limitations and negative results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Reviewer vtQs**\n\nWe appreciate Reviewer vtQs for the valuable feedback and acknowledge our technical contributions and the effectiveness of the proposed method. We address the concerns raised by the reviewer as follows.\n\n**Q1: The main focus of this paper** \n\n**A1:** Thank you for your valuable feedback and perspective on our paper. We want to clarify that the primary focus of our paper is to develop a self-interpretable graph-level anomaly detection method with robust anomaly detection capability and promising explainability for its predictions. We are confident in both of these capabilities, and they have been substantiated by the results of our experiments in Sections 4.2 and 4.3, respectively. However, it should be noted that self-interpretability is a novel property for graph-level detection methods, representing a \"zero-to-one\" innovation. As a result, we have placed additional emphasis on introducing and explaining this innovative aspect, which may inadvertently overshadow the strength of our anomaly detection model. We appreciate your valuable insight, and based on your suggestion, we will revise our paper to ensure a more balanced presentation of both the detection capability and the novel self-interpretability feature. \n\n**Q2: Insufficient qualitative analysis**\n\n**A2:** Thanks for the valuable suggestion! We have prepared more visualization results, which are included in the attached PDF and will be incorporated into the revised version of the paper. These additional visualizations cover not only three synthetic datasets but also a real-world dataset, namely MUTAG. To address your concern about the confusion in Figure 3, we will provide a more detailed caption that explains what the highlighted nodes and edges represent. Also, we will discuss the new results in more depth. Notably, the visualization examples are randomly selected rather than cherry-picked. As a result, you can witness some cases where SIGNET does not work perfectly in our new results.\n\n**Q3: The meaning of evaluation metrics**\n\n**A3:** We understand the importance of clarity and ensuring that the metrics used in our study are well-defined for readers. In the revised version of the paper, we will provide a more detailed explanation (P3 in general response) of the NX-AUC and EX-AUC metrics.\n\n**Q4: Hyper-parameters of baselines**\n\n**A4:** We apologize for the oversight in not mentioning the hyperparameter selection process for the baselines. Allow us to provide more clarity on this matter. To ensure robust and reliable results, we conducted a comprehensive grid search to obtain the best hyperparameter configurations for the baselines. Specifically, for deep GLAD methods, we performed grid searches on key hyperparameters (e.g., layer number and hidden dimensions). For post-hoc explainers, we conducted grid searches on their post-hoc training iterations and learning rates. As for shallow GLAD methods, we focused on searching for key hyperparameters such as the training iterations of detectors and kernel-specific parameters. We are committed to adding a more specific discussion regarding this in the revised version of the paper.\n\n**Q5: More discussion about limitations**\n\n**A5:** We appreciate your suggestion to discuss potential limitations and negative results in our paper.  In the revised version of our paper, we will include a dedicated section to address the potential limitations of our proposed method, SIGNET, and also discuss any negative results that we encountered during our research. For the method, While SIGNET performs well across various datasets, there might be specific datasets where its performance is not optimal. We will discuss the dataset characteristics that could impact the method's generalization and suggest ways to address this issue. For the negative results, we will transparently share any experiments or scenarios where SIGNET did not perform as expected or where its interpretability might be limited. \n\n**Q6: Anomalies in training set**\n\n**A6:** Thanks for the thoughtful comment! In this study, we adhere to the common practice of unsupervised graph-level anomaly detection, using a training set comprising only normal samples without any anomalies. Theoretically, adding anomalies to the training set may decrease the performance of all methods, including our proposed approach. However, it is important to note that some baseline methods are not specifically designed to handle scenarios with training data containing anomalies. Consequently, including anomalies in the training set could lead to unfair comparisons, as these baseline methods might not perform optimally in such settings. Although we recognize the significance of analyzing performance with varying levels of anomaly contamination in the training data, we have decided to leave this investigation for future work.\n\n**Q7: Style of figures**\n\n**A7:** Thanks for the valuable suggestion. In our figures, the cartoon-style fonts were chosen to provide a high-level explanation of the research question and the proposed method. The intention was to present a clear and visually engaging representation of the high-level concepts in another style, without delving into the specifics of the learning process. However, we also recognize the importance of maintaining a balance between clarity and aesthetics. In the revised version, we will explore alternative font styles that can still convey the high-level explanation effectively while aligning with academic standards.\n\n**Q8: Potential applications on unsupervised graph representation learning**\n\n**A8:** We agree that exploring the use of our framework for unsupervised graph representation learning could be promising. However, in this paper, our main focus is on the specific problem of unsupervised graph-level anomaly detection. In future works, we will consider exploring the use of our framework for unsupervised graph representation learning and its impact on various tasks. "}, {"review_id": "4T4qPgCwJx", "reviewer": "Reviewer_QzdR", "summary": "Inspired by the multi-view information bottleneck and dual hypergraph transformation, this paper proposed a self-explainable anomalous graph detection method called SIGNET. The method has three key designs in the model training stage: 1) Dual hypergraph-based view construction, 2) Bottleneck subgraph extraction, and 3) Cross-view maximization. Anomalous graph detection and graph rationale extraction will be achieved through maximizing the mutual information between the representations of graph rationale extracted from the original graph view and hyper-graph view. During inference, the anomaly score of a test graph is determined by the negative mutual information between the representations of its two graph rationales from different views.", "questions": "1. How does the equation (1) improve unsupervised representation? In other words, why does the Mutual information between $V_1$ and $Z_1$ need to be minimized when $V_2$ is known? And, why does the mutual information between $V_2$ and $Z_1$ need to be maximize? \n2. What are the key connections between unsupervised representation and graph-level anomaly detection? In this paper, graph-level anomaly detection is not a completely unsupervised problem, because labelled normal graphs work as the supervision information. \n(The answers to the above two questions 1 and 2 will help me understand why MIB can be applied to graph-level anomaly detection problems.)\n3. Why DHT-based view is useful for detecting anomalous graphs? More fine-grained discussions are important. For example, for a normal graph and an anomalous graph, what does their DHT-based view look like? If this is difficult to depict, it would be beneficial to explain why, for a normal graph, the mutual information between the representation of subgraph extracted from the original graph view and the DHT-based view should be high, while for an anomalous graph, the mutual information between representations of two different views should be low when two graph views share a single extractor?  (I have read the content from line 210 to line 215.  question: why the distinct content between dual hyper-graph and original view can benefit anomaly detection? What exactly are these distinctions?).\n4. It is reasonable to use the same extractor to replace minimizing the SKL divergence? \n5. Questions about the Loss function (5): Minimizing (5) is equal to maximizing $I(\\mathbf h_{G_i^{(s)}}, \\mathbf h_{G_i^{\\star (s)}})$. Hence, for $l(\\mathbf h_{G_i^{(s)}}, \\mathbf h_{G_i^{\\star (s)}})$, a larger numerator and a smaller denominator are expected. My question is, what is the meaning of the small denominator? Why do we need to make the representation $\\mathbf h_{G_i^{(s)}}$ of graph rationales about normal graph $i$ to be dissimilar from $\\mathbf h_{G_j^{(s)}}$ representation of graph rationales about normal graph $j$? Shouldn't normal graphs have similar representations (in experiments, authors use the graphs from the same class as normal graph)? In this way, the representations of their graph rationales should also be similar. \n6. In experiments, how to use GE and PE to explain the predictions of OCGIN, GLocalKD, and OCGTL? The loss function of GE and PE is designed for graph classification. \n7. The proposed method has connection with infoNCE loss and contrastive learning, a contrastive learning-based graph-level anomaly detection baseline is needed. GOOD-D [2] is a suitable choice.\n\n[2] Liu et al, GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection, WSDM 2023.\n\n", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The problem studied in this paper is important and interesting. It is essential to understand the subgraphs make a graph anomalous. \n2. This paper provides a clear summary of the challenges of self-interpretable GLAD and why existing explainers for GNNs cannot be applied to graph-level anomaly detection.\n3. This paper is well-structured. \n", "weaknesses": "1. Despite having a clear framework, it is still hard to get the motivations behind employing multi-view information bottleneck (MIB) and dual hypergraph transformation (DHT) to solve self-interpretable graph-level anomaly detection.  Much like GAST [1], authors draw inspiration from information theory to extract subgraphs as the explanation of model prediction, but they fail to adequately discuss the underlying intuition or theoretical basis for how MIB and DHT specifically address graph-level anomaly detection. \n2. The dataset used in experiments is relatively small-scale, and time complexity analysis is lacking. If there are difficulties in conducting experiments on large-scale graph data, time complexity analysis is necessary.\n3. More related work about anomaly detection and explainers of anomaly detection is expected. \n\n[1] Miao et al. Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism, ICML 2022.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Reviewer QzdR**\n\nWe are grateful to Reviewer QzdR for providing insightful feedback. Due to the limitation of space, we only reply to some core questions as below. For Questions 1/4/6 in the review, we will discuss them later.\n\n**Q1: Motivation behind using MIB and DHT**\n\n**A1:** We appreciate the reviewer for the insightful comment. We discuss the motivations as follows: \n\n**MIB**: We want to mention that in (unsupervised) graph-level anomaly detection (GLAD), the training phase only contains normal graphs, and the goal is to detect abnormal graphs during the test phase. Since we do not have any knowledge of labeled abnormal graphs during training, it is hard to learn a precise decision boundary between normal and anomalous graphs. Due to the lack of ground-truth knowledge of abnormal graphs during training, we try to leverage self-supervised (unsupervised) learning, in particular MIB to build the GLAD model, which characterizes the distribution of normal graphs and provides a good indicator for measuring the abnormality of test graphs. Also, by extracting the bottleneck subgraphs from our MSIB framework, we are able to provide self-interpretability when detecting anomalies.\n\n**DHT**: As our goal is to learn the normal data distribution through self-supervised learning, however, simply augmenting the input graph with stochastic perturbation may introduce anomalous graphs, leading to unexpected performance degradation. In contrast, the DHT-based view construction avoids perturbing the original graph's semantic knowledge and provides a new view of the input graph, enabling us to capture consistent matching patterns between the two views. Additionally, the dual hypergraph approach prioritizes edge-level information, encouraging the model to recognize both node-level and edge-level anomaly patterns. Consequently, the node-edge matching pattern becomes a focal point for model learning and serves as an indicator for normal/abnormal graphs. For instance, if a normal pattern is a star-shaped motif, the node patterns (e.g., high-degree center node) and edge patterns (e.g., connections between center/tail nodes) of this motif can be effectively captured by maximizing the agreement between the original view and the DHT view. In cases where an anomaly with a similar but distinct motif (e.g., clique) is introduced, it would exhibit a lower mutual information (MI) value due to the disruption of node-edge matching patterns, which can help us to better detect the abnormal graphs during the test phase.\n\n**Q2: Experiments on large-scale datasets and complexity analysis**\n\n**A2:** Thank you for your valuable feedback regarding the scalability and time complexity analysis. In response to your suggestions, we conducted additional experiments on two large-scale datasets with more samples, BM-MT-20k and MNIST-0-6k. The content of datasets is similar to BM-MT and MNIST-0. The results below demonstrate that our method can handle datasets with a large number of graphs, verifying the scalability of our method. Note that SIGNET can also handle datasets with large graphs (e.g., REDDIT-B with 429.6 avg. #node), as shown in our main paper. Furthermore, we have included a comprehensive time complexity analysis of our method, which is attached in P1 of general response.\n\n|Dataset|AD-AUC|NX-AUC|EX-AUC|Runtime|\n|-|-|-|-|-|\n|BM-MT-20k|95.75%|81.85%|80.59%|2.5561s|\n|MNIST-0-6k|82.25%|74.08%|76.35%|0.6247s|\n\n**Q3: Connections between unsupervised representation and graph-level anomaly detection**\n\n**A3:** We appreciate the reviewer for raising this concern. Following the previous literature on GLAD, we want to mention that the training graphs only contain normal ones, and the goal is to detect abnormal graphs during the test phase. Since we do not have any knowledge of labeled abnormal graphs during training, it is hard to learn precise decision boundaries between normal and anomalous graphs. Therefore, we try to leverage unsupervised/self-supervised learning to build the graph-level anomaly detection model, which characterizes the distribution of normal graphs and provides an indicator (i.e., cross-view MI) for measuring the abnormality of test graphs.\n\n**Q4: Why minimize the MI between graph rationale and other normal graphs** \n\n**A4:** We appreciate your insightful question. Firstly, the Info-NCE mutual information estimator theoretically requires negative samples in its denominator to prevent collapse, i.e.,  all input pairs are estimated to have large MI. To meet this requirement efficiently, we opted to use other samples in the same batch as negative samples, which is an efficient strategy without extra cost. During the model design phase, we explored stochastic graph perturbation to generate synthetic negative samples. However, this approach proved less effective, unstable, and time-consuming. Empirically, using other normal samples as negative samples has shown effectiveness. Secondly, despite normal samples belonging to the same class or having similar properties, their graph rationales can differ from each other. For instance, in the BM-MS dataset, the rationales may include rings of different sizes; in the MUTAG dataset, they can be -NH2 or -NO2. Hence, maximizing the similarity between a graph and the rationales of other graphs may lead to mismatching and hurt stability and performance. Instead, maximizing the similarity of each graph to its own rationale proves to be a reliable strategy. Therefore, we opted to use Info-NCE to ensure that each graph has a larger similarity to its own rationale rather than to others' rationales. We hope this explanation addresses your query and provides better insight into our approach.\n\n**Q5: New baseline**\n\n**A5:** Thank you for providing a strong anomaly detection baseline GOOD-D that makes our experiments more convincing. We will include a comparison with GOOD-D, see attached PDF, where SIGNET outperforms GOOD-D with a significant performance gap of 7.40%."}]

Author rebuttal:
**General Response**

We sincerely thank all the reviewers for their valuable and insightful comments. We are glad that the reviewers find that the studied problem is novel and significant (Reviewer 6qZe, yuBa, and QzdR), the proposed method is novel and well-motivated (Reviewer 6qZe, yuBa, and vtQs), the theoretical analysis is sound (Reviewer yuBa), the empirical studies are adequate and reasonable (Reviewer vtQs), and the writing is smooth and has a good storyline (Reviewer yuBa, vtQs, and QzdR). 

To the best of our efforts, we provided detailed responses to address the concerns raised by each reviewer in the following. Meanwhile, we carefully revised the paper according to the reviewers’ comments. We will incorporate all the feedback in the final version. ​​Specifically, the main revisions we made are as follows.

* We have added extra experiments to discuss the scalability on large-scale datasets and running efficiency of the proposed method (please see the Reply to Reviewrs 6qZe and QzdR for details). 
* We have analyzed the time complexity of the proposed method (see the attached paragraph P1 below). The discussion shows that the complexity of the proposed method is comparable to mainstream GNN-based models.
* We have added more qualitative experiments, i.e., more visualization of explanation results, including results on real-world dataset (see the attached PDF).
* We have illustrated the implementation details of our baselines, i.e., the GLAD methods with post-hoc explainers (see the attached paragraph P2 below). 
* We have added detailed explanations for our evaluation metrics, i.e., NX-AUC and EX-AUC (see the attached paragraph P3 below).
* We have highlighted the comparisons between our method (SIGNET) and a representative self-interpretable GNN, GSAT (see the attached paragraph P4 below). 

**P1: Complexity Analysis of SIGNET.** Within this paragraph, we denote the average numbers of nodes and edges as $n$ and $m$ respectively, and denote the number of graphs and batch size as $N$ and $B$ respectively. At each training iteration, we first conduct DHT to obtain the dual hypergraph, which requires $\mathcal{O}(N(m+n))$. Then, the GNN-based extractor that calculates probability consumes $\mathcal{O}(NL_1md_1+NL_1nd_1^2 + Nnd_1d_f)$ complexity, where $L_1$ and $d_1$ are the layer number and latent dimension of the extractor, respectively. The bottleneck subgraph extraction for two views requires $\mathcal{O}(N(m+n))$ in total. For the GNN and HGNN encoders, their time complexities are $\mathcal{O}(NL_2md_2+NL_2nd_2^2 + Nnd_2d_f)$ and $\mathcal{O}(NL_2nd_2+NL_2md_2^2 + Nnd_2d_{f*})$ respectively, where  $L_2$ and $d_2$ denote their layer number and latent dimension. Finally, the Info-NCE loss requires $\mathcal{O}(NBd_2)$ complexity. To simplify the overall complexity, we denote the larger terms within $L_1$ and $L_2$ as $L$, and the larger terms between $d_1$ and $d_2$ as $d$. After ignoring the smaller terms, the overall complexity of SIGNET is $\mathcal{O}(NLd^2(m+n) + Nnd(d_f+d_{f*}) + NBd)$.

**P2: Implementation of GLAD methods with post-hoc explainers.** Given a GLAD model and post-hoc explainer, at first, we train the GLAD model independently on the training set. After sufficient training, the GLAD model is able to map each input graph into a scalar, i.e., its anomaly score. To address the uncertainty of the anomaly score boundaries, we apply a linear scaling function to map the scores into the [0,1] range and then use a sigmoid function to convert each score into a probability for binary classification. Subsequently, we integrate the post-hoc explainer with the probabilitized output of the GLAD model and optimize the explainer accordingly.

**P3: Evaluation metrics.** In this paper, we use “explanation Area Under the Curve (AUC)” to evaluate the explanation performance, following previous works [19,20]. We employ both node-level and edge-level explanation AUCs for comparison (NX-AUC and EX-AUC for short, respectively). Specifically, we tackle the explanation problem by framing it as a binary classification task for nodes and edges. We designate nodes and edges inside the explanation subgraph as positive instances and the rest as negative. The importance weights generated by the explanation methods serve as prediction scores. An effective explanation method should assign higher weights to nodes and edges within the ground truth subgraphs compared to those outside. To quantitatively evaluate the performance, we use the AUC as the metric for this binary classification problem. A higher AUC indicates better performance in providing meaningful explanations.

**P4: Comparison between GSAT and SIGNET**

Connections:
Both GSAT and SIGNET use information bottleneck principle as theoretical foundation of their explanation target that extracts the explanation subgraph. Both of them adopt neural networks to parameterize input graph and make the explanation differentiable, which is a common design among explainable GNNs. 

Differences:
* Different targeted tasks: GSAT focuses on a graph classification where labels are available to train the interpretation module. Differently, SIGNET targets unsupervised GLAD, a more challenging task with unavailable labels during training.
* Different theoretical framework: GSAT is designed based on the original information bottleneck framework, tailored to its targeted supervised setting. In contrast, SIGNET is based on the multi-view subgraph information bottleneck (MSIB) framework derived in this paper, specifically designed for unsupervised GLAD.
* Different learning objectives: GSAT is trained using cross-entropy loss, a commonly used classification loss. In contrast, SIGNET is optimized using an Info-NCE loss, aiming to maximize the MI between each graph and its rational subgraph.
* Different graph view for graph learning: GSAT only considers the original view for graph learning, while SIGNET considers both the original and DHT views.

Meta-review: The paper proposes the SIGNET approach for interpretable graph level anomaly detection. They first propose the multi-view subgraph information bottleneck (MSIB), which generates two views via dual hypergraph transform (DHT), then uses an information bottleneck approach to find the most informative subgraph as explanation. 

Reviewers gave borderline to positive scores (6655). Strengths include the problem importance, well-designed method, and compelling empirical results. Issues raised include efficiency, novelty, and comparison to explainability baselines. In my view, the paper does introduce significant novel contributions, particular the focus on obtaining subgraphs for explaining graph anomalies; the method design utilizing information bottleneck to obtain subgraphs, and the use of dual hypergraph transform, which is an interesting and reasonable choice (as it is a deterministic and nontrivial transformation). Moreover, the case studies are interesting and show that the method indeed generates meaningful explanations, e.g. identifying the NH2 and NO2 subgraphs as explanations for the MUTAG dataset (matching ground truth), and cycles as explanations on some synthetic datasets. 

For the remaining concerns, the rebuttal helped to address these satisfactorily, e.g. adding complexity analysis, experiments on larger datasets, additional baselines, and additional explanation results. Overall, reviewers and AC find the paper to be well-motivated by an important problem, novel, well-written, and with strong quantitative and qualitative empirical results. Hence, I recommend acceptance. 

Authors are requested to note the suggested improvements / action items arising from discussion with the reviewers, such as adding the new empirical results to the final manuscript, and other clarifications to the paper arising from reviewer discussion (related work, hyperparameters, limitations, etc.)
Decision: Accept (poster)