Interpretable Prototype-based Graph Information Bottleneck
Authors: Sangwoo Seo
Sungwon Kim
Chanyoung Park
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph neural network
Explainable AI
Interpretability

Abstract: The success of Graph Neural Networks (GNNs) has led to a need for understanding their decision-making process and providing explanations for their predictions, which has given rise to explainable AI (XAI) that offers transparent explanations for black-box models. Recently, the use of prototypes has successfully improved the explainability of models by learning prototypes to imply training graphs that affect the prediction. However, these approaches tend to provide prototypes with excessive information from the entire graph, leading to the exclusion of key substructures or the inclusion of irrelevant substructures, which can limit both the interpretability and the performance of the model in downstream tasks. In this work, we propose a novel framework of explainable GNNs, called interpretable Prototype-based Graph Information Bottleneck (PGIB) that incorporates prototype learning within the information bottleneck framework to provide prototypes with the key subgraph from the input graph that is important for the model prediction. This is the first work that incorporates prototype learning into the process of identifying the key subgraphs that have a critical impact on the prediction performance. Extensive experiments, including qualitative analysis, demonstrate that PGIB outperforms state-of-the-art methods in terms of both prediction performance and explainability.

Interpretable Prototype-based Graph Information Bottleneck
Sangwoo Seo' Sungwon Kim' Chanyoung Park
KAIST
(sangrooseo@kaiist.cm ac kr, swkim@kaist. ac, kr, cy. ww.pparkkaist..cc.. ac. kr)
Abstract
The success of Graph Neural Networks (GNNs) has led need for understanding their decision-making process and providing explanations for their predictions, which has given rise to explainable Al (XAI) that offers transparent explanations for black-box models. Recently, the use of prototypes has successfully improved the explainability models by learning prototypes to imply training graphs that affect the prediction. However, these approaches tend to provide prototypes with exces- sive information from the entire graph, leading to the exclusion of key substructures the inclusion of irrelevant substructures, which limit both the interpretability and the performance of the model in downstream tasks. this work, we propose a novel framework of explainable GNNs, called interpretable Prototype-based Graph Information Bottleneck (PGIB), that incorporates prototype learning within the in- formation bottleneck framework to provide prototypes with the key subgraph from the input graph that is important for the model prediction. This is the first work that incorporates prototype learning into the process of identifying the key subgraphs that have a critical impact on the prediction performance. Extensive experiments, including qualitative analysis, demonstrate that PGIB outperforms state-of-the- methods in terms of both prediction performance and explainability. The source code of PGIB available at https: //t///gtttt///t// com/ sang- woo- www-see/PGG. seo/PGIB.
Introduction
With the success of Graph Neural Networks (GNNs) in wide range of deep learning tasks, there has been an increasing demand for exploring the decision-making process of these models and providing explanations for their predictions. To address this demand, explainable AI (XAI) has emerged way to understand black-box models by providing transparent explanations for their predictions. This approach can improve the credibility of models and ensure transparency in their decision-making processes. As a result, XAI is actively being used in various applications, such as medical, finance, security, and chemistry [3, 26].
In general, explainability can be viewed from two perspectives: 1) improving the interpretability by providing explanations for the model's predictions, and 2) providing the reasoning process behind the model prediction by giving explanations for the model's training process. Improving the interpretability in GNNs involves detecting important substructures during the inference phase, which useful for tasks such as identifying functional groups (i.e., important substructures) in molecular chemistry [29, 33, 23, 12]. On the other hand, it also important provide the reasoning process for why the model predicts in a certain way, which requires an in in-depth analysis of the training phase, so to understand the model in more fundamental level. Through this reasoning process, can visualize and analyze how the model makes correct or incorrect decisions, thus obtaining crucial information for improving its performance.
Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Input graph,
Prototype graphs. Sy...
Input graph.
Prototype graphs, Sy.
Sp
Spi
NOs
(a) ProtGNN
(b) PGIB
Figure 1: Comparison of the learned prototypes between ProtGNN and PGIB.
In recent years, there has been a growing interest in exploring the reasoning process to provide greater transparency and explainability in deep learning models. These approaches can be generally classified into two main categories: 1) post-hoc approaches, and 2) built-in approaches. Post-hoc approaches focus on exploring the model outputs by visualizing the degree of activation of neurons through measuring their contribution based on gradients of the model predictions. For instance, recent works [14, 9, 34] use techniques such as saliency maps and class activation maps to visualize the activated areas during the model's prediction process. However, these approaches require separate explanatory model for each trained model, resulting in the need for new explanatory model for additional training data and different models [2, 15]. In order to address the aforementioned challenges, buill-in approaches aim to integrate the generation of explanations into the model training process. One such approach is prototype learning, which involves learning prototypes that represent each class of the input data, which are then compared with new instances to make predictions. ProtGNN [35], for instance, measures the similarity between the embedding of an input graph and each prototype, providing explanations through the similarity calculation and making predictions for the input graph based on its similarity with the learned prototypes. More precisely, ProtGNN projects each learned prototype onto the closest training graph, enabling it to provide explanations of primary structures for its prediction.
However, since ProtGNN compares the graph-level embedding of an input graph with the learned prototypes, the model overlooks the key substructures in the input graph while also potentially including uninformative substructures. This not only results in a degradation the reasoning process, but also limits the performance on the downstream tasks. Figure ((a) shows the prototype graphs in the training set (i.c., Gp. denoted as bold edges) detected by ProtGNN for an imput molecule (i.e., G) that belongs to the "mutagenic" class. Despite the NO₂ structure being the key functional group for classifying a given molecule as "mutagenic," Gp detected by ProtGNN tends to include numerous ring structures (i.e., uninformative substructures) that commonly found throughout the input graph, and exclude NO₂ structures (i.e.. key substructures) in learned prototype graphs, which is mainly due to the fact that the input graph G is considered in the whole graph-level. As a result, it is crucial to identify a key subgraph within the input graph that holds essential information for the learning of prototypes, which in turn enhances both the explanation of the reasoning process and the performance on the downstream tasks. Among the various solutions for detecting important subgraphs, the Information Bottleneck (IB) has emerged as one of the most effective methods [27, 31], and it has been demonstrated that key subgraphs detected based on IB can contribute to performance improvement in various tasks such as relational learning [11] and structure learning [19]. We aim to approach the IB principle from the perspective of prototypes to convey important substructure information to the prototypes.
the interpretability of
To this end, we propose a novel framework of explainable GNNs, called Interpretable Prototype-base based Graph Information Bottleneck (PGIB). The main idea is to incorporate prototype learning within the Information Bottleneck (IB) framework, which enables the prototypes to capture the essential key subgraph of the input graph detected by the IB framework. Specifically, PGIB involves prototypes (i.e., 9p) in a process that maximizes the mutual information between the learnable key subgraph (i.e.. Gout) of the input graph (i.c.. 9) and target information (i.c., Y). which allows the prototypes to interact with the subgraph. This enables the learning of prototypes Gp based on the key subgraph Goub within the input graph G, leading to more precise explanation of the reasoning process and improvement in the performance on the downstream tasks. To the best of our knowledge, this is the first work that combines the process of optimizing the reasoning process and interpretability by identifying the key subgraphs that have critical impact on the prediction performance. In Figure (bb, PGIB shown to successfully detect the key subgraph Goub that includes NO, from the input graph G, even when the ring structures are dominant in G. It is important to note that PGIB is highly efficient detecting Gsub from G since PGIB adopts a learnable masking technique, effectively resolving the time complexity issue. Last but not least, since the number of prototypes for each

---

class is determined before training, some of the learned prototypes may share similar semanties, which negatively affects the model interpretability for which the small size and low complexity are desirable |6, 25, 17]. Hence, we propose method for effectively merging the prototypes, which in turn contributes to enhancing both the explanation of the reasoning process and the performance on the downstream tasks.
We conducted extensive experiments to evaluate the effectiveness and interpretability of the reasoning process of PGIB in graph classification tasks. Our results show that PGIB outperforms recent state- of-the-art methods, including existing prototype learning-base and IB- methods. Moreover, we evaluated the ability of PGIB in capturing the label information by evaluating the classification performance using only the detected subgraph Ssub- We also conducted a qualitative analysis that visualizes the subgraph Souh and prototype graph Gp. suggesting the ability of PGIB in detecting the key subgraph. Overall, our results show that PGIB significantly improves the interpretability of both Ssub and Op in the reasoning process, while simultaneously improving the performance in downstream tasks.
In summary, our main contributions can be summarized as follows: 1) We propose an effective approach, PGIB, that not only improves the interpretability of the reasoning process, but also the overall performance in downstream tasks by incorporating the prototype learning in a process of detecting key subgraphs based on the IB framework. 2) We provide theoretical background with our method that utilizes interpretable prototypes in the process of optimizing Grub- 3) Extensive experiments, including qualitative analysis, demonstrate that PGIB outperforms state-of-the-as methods in terms of both prediction performance and explainability.
2 Preliminaries
In this section, we introduce notations used throughout the paper followed by the definitions of IB and IB-Graph.
Notations. We use G AX) to denote a graph, where V. E, A and X denote the set of nodes and edges, the adjacency matrix and node features, respectively. We assume that each node 2/ V is associated with feature vector x,, which is the i-th row of X. We use ((G.. y1). (92, y2),... (GN, }
}} to denote the set of N graphs with its corresponding labels. The graph labels are given by a set of K classes C 21, K). and the ground truth label of graph G, is denoted by Yi E C. We use Guus to denote a subgraph of G, and use Grub to denote the complementary structure of Gsub in G. We also introduce the prototype layer, which consists
M where M is the total number of prototypes, and of a set of prototypes Zp = { { "0,,'" "g.
each prototype zH, is a learnable parameter vector that serves as the latent representation of the prototypical part (i.e., Gp) of graph G. We allocate J prototypes for each class, i.e., M K x J.
Graph Information Bottleneck. The mutual information between two random variables X and Y, i... (X;Y), is defined as follows:
p(r,y) v) drdy p(x)p(y)
I(x;Y) -
p(x, v) log
(I)
Given the input X and its associated label Y, the Information Bottleneck (IB) [21] aims to obtain a bottleneck variable Z by optimizing the following objective:
min (Y:: + 3I(X:
(2)
where 3 is the Lagrange multiplier used to control the trade-off between the two terms. IB principle has recently been applied to learning a bottleneck graph, named IB-Gr,hh, for a given graph G, which retains the minimal sufficient information in terms of G's properties [31]. This approach is motivated by the Graph Information Bottleneck (GIB) principle, which seeks to identify an informative yet compressed subgraph Gous from the original graph G by optimizing the following objective:
min - ((Y: :Gub) + BT(G; Geub), Sxub
where Y is the label of G. The first term maximizes the mutual information between the graph label and the compressed subgraph, which ensures that the compressed subgraph contains as much information as possible about the graph label. The second term minimizes the mutual information between the input graph and the compressed subgraph, which ensures that the compressed subgraph contains minimal information about the input graph.
3

---

Sinu
ONN
Readost
input graph
Siymold
= Aphe (1 Aaje
Protstops
Pr.Pa....PP
Subgruph Layar
Protetypa Lager
Figure 2: The architecture of our proposed PGIB. PGIB generates subgraph Geub by injecting noise to identify core subgraphs, and it is used to compute similarity scores between prototypes in the prototype layer. The trained prototypes play a crucial role visualizing the reasoning processes during training in an interpretable manner. PGIB also involves merging pairs of similar prototypes to decrease the number of prototypes. Finally, the integrated prototypes are utilized to predict the graph labels in the fully connected layer.
Methodology
In this section, we present our proposed method, called PGIB. We introduce Prototype-based Graph Information Bottleneck (Section 3.1), each layer in the architecture (Section 3.2 3,4), and the interpretability stabilization process (Section 3.5). which enhances the interpretability and the tracking capabilities of the reasoning process during the model training.
Model Architecture. Figure 2 presents overview of PGIB. We first generate the representations of nodes in the input graph using a GNN encoder. Then, the node representations are passed to the subgraph extraction layer that assigns each node in G to either Goub or Geub. Next, compute the M similarities between the embedding Zg... and the set of prototypes Zp = {zbb :....... E in the prototype layer. Finally, we merge the prototypes that are semantically similar, which are then used to generate the final prediction.
3.1 Prototype-based Graph Information Bottleneck
PGIB is novel explainable GNN framework that incorporates the prototype learning within the IB framework, thereby enabling the prototypes to capture the essential key subgraph of the input graph detected by the IB framework. More precisely, we reformulate the GIB objective shown in Equation by decomposing the first term, i.e., I(Y: Gsub), with respect to the prototype 9p using the chain rule of mutual information in order to examine the impact of the joint information between Goub and Gp on Y as follows:
min -VY Gp) + ((Y:GllGmn)) +3 (G; Ganc).
(4)
4
Section 3.3
Section 3.2
Please refer to Appendix A.I for detailed proof of Equation 4. In the following sections, describe how each term is optimized during training.
3.2 Subgraph Extraction Layer (Minimizing I(G; Gsub))
The goal of the subgraph extraction layer is to extract informative subgraph Goub from G that contains minimal information about G. We minimize T I(G Grub) by training the model to inject noise into insignificant subgraphs Gout. while injecting less noise into more informative ones Grub [32]. Specifically, given the representation of node U; i.e., h; we compute the probability p; with an MLP followed by a sigmoid function, which is then used to replace the representation h; obtain the final representation z; as follows:
= SigmoidddMP(Ph
= Ash: + (1 Adte, where X; ~ Bernoullip::) and e of,
That is, the learned probability y3 enables selective preservation of information in Gaus. and based on this probability, the quantity of information transmitted from h, to z; can be flexibly adjusted to compress the information from G to Goub. This approach not only retains interpretability within the

---

subgraph itself, but also potentially facilitates the learning of prototypes that are introduced in the next step. Following [32], we minimize the upper bound of [[; (sub) as follows:
1 I(Gb) _ 155(- log + 2 2|V=l B²) =: (5.
A
(6)
where A = E1 (1-),)) and B lVll A Thus, minimizing Ckt allows us to minimize
Th
the upper bound of I(;; Gsub). After noise injection, we compute the embedding ze... through a graph readout function such max pooling and sum pooling. For further details and analysis of the different graph readout functions, please refer to Appendix A.4.2.
3.3 Prototype Layer (Minimizing - ; 9p) + I(Y: (pP9plguub))
The prototype layer involves allocation of fixed number of prototypes for each class. The prototypes are required to capture the most significant graph patterns that can aid in the identification of the graphs within each class. To begin with, we define the similarity score between the prototype zgp and the embedding zg... obtained from noise injection as follows:
[Zg... 20p 18 +
g(zg.uu mo,)) = log
(7)
[2ggus
zG, 11 +
where zg, is the prototype and shares the same dimension as Zg.ux*
3.3.1 Minimizing - Gond 9p)
We derive the lower bound of [(;; Gsub, 9p) as follows:
Proposition 1. (Lower bound of T(Y; Gaub, 9p)) Given sigmificant subgraph Gaus for graph G, its label
information Y, prototype graph 9p and similarity function y, we have
T(Y; Goub; fp)
Ey, [log p (Y|Ssub; [p)] Fy p(Y))
2 Er,o.ub [log p (Y/ (Grub, Fp)}] } Ey P(Y)
(8)
2 Ey Ey [log qo (1 (Gaud, G.))] =: Leta (26 (Yly (Goub, Gp))
where go (Yly (Goub; {p)) is the variational approximation the true posterior p (Ylr (Isub: 9p)).
Equation 8 demonstrates that the maximization of the mutual information I(Y; Geut: Fp) can be attained by minimizing the classification loss, denoted as Cets- This maximization of mutual informa- tion between the label Y and the similarity information 7 (Grub, Gp) promotes the subgraph Gous and prototype Gp to possess predictive capabilities concerning the graph label Y. In practical applications, the cross-entropy loss is chosen for categorical Y. For comprehensive understanding of the deriva- tion process of Equation 8, refer to the Appendix A.2. Note that the similarity between Goub and 9p. i..., 7 (Grub, Gp), is computed by the similarity score defined in Equation 7, i.c., g g(Zg.us: Zg,).
3.3.2 Minimizing I(Y; (plus)))
We investigate the mutual information, denoted as I(Y; Gn (Ssu), from the perspective of the inter- action between Suuh and G,. We decompose I GplG.us) into the sum of two terms based on the chain rule of mutual information follows:
(ylouu) = I(Gp; Yuut) - I(Gsubi Gp)-
(9)
It is important to note that the first term, i.c., 1 g(Gp Y. Yrabt), minimizes the mutual information between Gp and the joint variables (Y, Gsub), which eliminates the information about Y related to Goub from G,,. However, since our goal is not to solely minimize TG Y, Geub) but to ensure the interpretability of the prototype Gp. including this term leads diminished interpretabilityy of Gp- Consequently, we excluded the first term during training, and only consider the second term, i... ((G 9p), to simultaneously guarantee the interpretability of both Gaub and 9y. A detailed derivation for Equation 9 is given in Appendix A.3. From now on, we describe approaches for minimizing the second term. Inspired by [11], we introduce two different approaches for minimizing -I Gp).
5

---

1) Variational IB-based approach. We obtain the upper bound of - (I Gp) using the variational IB-based approach as follows:
(Gubb 9p) S Re 1- go (9p19uo) == L3n1 (Gsus, pp):
(10)
where (Gp19gub) is the variation approximation of p(pp)9sub). Equation 10 shows that the maxi- mization of the mutual information subu 9p) can be attained by minimizing (9 Sp). We select single-layer linear transformation as modeling option for g6 to minimize the information loss of Gaud when predicting Gp.
2) Contrastive learning- based approach. Recent studies on contrastive learning [20, 30, 7] have proven that minimizing contrastive loss is equivalent to maximizing the mutual information between two variables. Hence, we additionally propose a variant of PGIB, i.e., PGlBe that minimizes the contrastive loss instead of minimizing the lower bound as defined in Equation 10. More preciscly, we consider Gp and Geub with the same label as positive pair, and the contrastive loss is defined as follows:
Σ EP
exp(g(za; 20/)/T)
1:2 op
2311
log
(1I)
TE
Σ #Py
exp(g(Zg) 200 )/-)
A op
where 7 is the temperature hyperparameter, n denotes the number of graphs in batch, and and indicate indices of positive and negative samples, respectively. Py, is the set of prototypes that belong class y,. We effectively confer interpretability to Gp by increasing its similarity with each Geub-
3.4 Prediction Layer
We obtain the set of similarity scores r E RR whose m-th element Vm = g(zg. 2 denotes the similarity score between Zg.us and zg, as defined in Equation 7. Then, we compute the final predicted probability π E RKK by passing r and Zg... through a linear layer with weights w, followed by the softmax function. Specifically, w[m, :] denotes weight assigned to T'm i.e. (Zzz)). Finally, calculate the cross-entropy classification loss, follows:
Cele
I( c) log(Te).
(12)
N
3.5 Interpretability Stabilization
Merging Prototypes. Since the number of prototypes for each class is determined before training, some of the learned prototypes may share similar semantics, which negatively affects the model interpretability for which the small size and low complexity are desirable [6, 25]. Inspired by [17], we propose a method to effectively merge the prototypes for graph-structin enhances the explanation of the reasoning process and improves performance on downstream tasks while reducing model complexity. The main idea to merge prototypes based on the similarity between prototype pairs using the embeddings Zgsub. This similarity utilizes all training subgraphs (i.e., U Gsud. where X' the training set) by measuring the disparity between g(zg...: z0;) and GEN g(zg.us) 2gg) as follows:
data, which, in turn,
M2zg Rof) =
Elolzonn: - g g(zon 2 2z
(13)
LaEx
Then, for every pair (Zgy: : zoz] that falls within the highest & percent of similar pairs, the prototype Zgz and its corresponding weights w (Zzg)) are removed, and the weights w(zg;) are updated to the sum of w(2g)) and w(zzg). We combine the & percentage of the most similar prototype pairs based on the calculated similarity scores.
Prototype Projection. Since the learned prototypes are embedding vectors that cannot be directly interpreted, we project each prototype zg,, onto the nearest latent training subgraph from the same class. This process establishes a conceptual equivalence between each prototype and a training subgraph, thereby enhancing interpretability of the prototypes. Specifically, we update prototype zop of class k (i.e., (i, IPx) by performing the following operation:

---

mig 2 z0, Ila, where 2 [c Subgraph(G.) si ys = k) (14)
20p
REZ
In the Equation 14, we use Monte Carlo Tree Search (MCTS) [18] to explore training subgraphs و during prototype projection.
Connectivity Loss. For an input graph G. we construct a node assignment Sg E R|ve|>2 based on the probability values that are computed by Equation 5. Specifically, Sglj, 0] and Sg [j. 1] denote the probability of node v E Vg belonging to Geub and Geub. respectively. Following [31], poor initialization of the matrix S may result in the proximity of its elements S[j 0] and S 1 for Vuy E Vs.. leading to an unstable connectivity of Gruh- This instability can have adverse effects on the subgraph generation process. To enhance the interpretability of Ssuh by inducing a compact topology, we utilize a batch-wise loss function as follows:
Loon = |[Nom ABSB) - 12/1
(15)
|Vo Xx2
and AB E R - 1o.1
E IVoll
where SB E Rial matrix at the batch level, respectively. 12 2-by-2 identity matrix, || || is the Frobenius norm and Norm(-) is the row normalization. Minimizing Leen indicates that if ny is in Gubb its neighbors also have a high probability be in Goud, while if o; Godd, its neighbors have low probability to be in Goub-
are the node assignment and the adjacency
Final Objectives. Finally, we define the objective of our model the sum of the losses follows:
Liotal = Lets + ar CMr + az + a3Ccon
(16)
where 01, 02 and 03 are pypee-parameters that adjust the weights of the losses. A detailed ablation study for each loss term is provided in Appendix A.4.1 for further analysis.
4
Experiments
4.1
Experimental Settings
Each dataset is split into training, validation, and test sets with ratio of 80%, 10%, and 10%, respec- tively. All models are trained for 300 epochs using the Adam optimizer with a learning rate of 0.005. GIN [28] is used as the encoder for all models used in the experiment. We evaluate the performance based on accuracy, which averaged over 10 independent runs with different random seeds. For sim- plicity, the hyperparameters 01,, 022 and ag in Equation 16 are set to 0.0001, 0.01 to 0.1 and 5, respec- tively. The prototype merge operation starts at epoch 100 and is performed every 50 epochs thereafter. We set the number of prototypes per class to 7 and combine 30% of the most similar prototype pairs.
4.2 Graph Classification
Datasets and Baselines. We use the MUTAG [16], PROTEINS [1], NCII [24], and DD[5] datasets. These are datasets related to molecules or bioinformatics, and are widely used for evaluations on graph classification. We consider three GNN baselines, including GCN [10], GIN [28], GAT [22]. In addition, we compare PGIB with several ofate-of-the-arr built-in models that integrate explanation functionality internally, including a prototype-
method ProtGNN [35], and IB-based models
such as GIB [31], VGIB [32], and GSAT [13]. Further details about the baselines and datasets are provided in Appendix A.5 and A.6, respectively.
Experiment Results. Experimental results for graph classification are presented in the Table 1. In the table. PGIB and PGIBcont represent our proposed methods. PGIB utilizes a Variational IB-based approach, while PGIBcont employs a Contrastive learning- based approach to maximize (Gutii (Section 3.3.2). We have the following observations: 1) All variants of PGIB outperform the baselines including both the prototype-based and IB -a-ddedd methods on all datasets. Notably, PGIBs incorporate the crucial information of the key subgraph, which significantly contributes to enhancing the classification performance. PGIB achieves a significant improvement of up to 5.6% compared to the runner-up baseline. 2) We observe that PGIB performs relatively better than PGIB. We attribute this to the nature of the contrastive loss, which is generally shown to be effective classifying instances between different classes, allowing the prototypes learned based on the contrastive loss to be more distinguishable from one another.
7

---

Table Evaluation on graph classification (aceuracy).
Methods
Dataset
GCN
GIN
GAT
ProiGNN
GIB
VGIB
GSAT
PGIB
PG
MUTAG
74.5017.89
80.5027.89
73.5017.43
80.5019.07
79.00a6.24
81.0016.63
80.8818.94
85.0047.07
85.50a5.22
PROTEINS
72.8344.23
70.30+4.84
71.35+4.85
73.8344.22
75.25=5.92
73.66+3.32
69.64x4.71
77.1442.19
77.50+2.42
NCII
73.16#3349
75.04+2.08
66.05=1.03
74.13+2.11 10
64.65=6.78
63.75+3.37
68.1342.64
77.65#2.20
78.25+2.13
DD
72,53+4.51 72.04+3.62
70.81+4.33
69.15+4.33
72.61
72.77+5.63
71,93+2.74
73,36+l 880
73.70=2.14
4.3
Graph Interpretation
In this section, we evaluate the process of extracting subgraphs that possess the most similar properties of the original graph. We present qualitative results including subgraph visualizations, and conduct quantitative experiments to measure how accurately explanations capture the important components that contribute to the model's ' predictions.
Datasets and Baselines. We use four molecular properties from the ZINC [8] dataset, which consists of 250,000 molecules, for graph interpretation. QED measures the likelihood of a molecule being drug and DRD2 indicates the probability of a molecule being active on dopamine type 2 receptors. HLM-CLint and RLM represent estimates of in vitro human and rat liver microsomal metabolic stability (mL/min/g as base 10 logarithm). We compare PGIB cont with several representative interpre- tation models, including GNNexplainer [29], PGexplainer [12], GIB [31], and VGIB [32]. Note that as PGIB shows similar results with PGIB cont. cont. we only report the results of PGIB cont for simplicity. Further details on baselines and datasets are described in Appendix A.5 and A.6, respectively.
Qualitative Analysis. Figure 3(a)-(d) present the visualization of subgraphs in Mutag dataset. According to [29, 4), the NO₂ functional group known to be a cause mutagenicity, while the carbon ring is substructure that is not related to mutagenicity. In the figure, the bold edges connect the nodes that the models consider important. The NO₂ group in Mutag correctly identified by PGIB, while VGIB, ProtGNN, and GNNexplainer fail to recognize all NO₂ groups or include other unnecessary substructures. Figure 3(e)-(h) present the visualization of subgraphs in BA-2Motiß dataset. We observe that PGIB accurately recognizes motif graphs containing the label information such as a house or a five-node cycle, but other models have difficulty in detecting the complete motifs.
Quantitative Analysis. Although visualizing the explanations generated by models plays a crucial role assessing various explanation models, relying solely on qualitative evaluations may not always be reliable due to their subjective nature. Therefore, we also perform quantitative experiments using the Fidelity metric [14, 34].
The Fidelity metric quantifies the extent to which explanations accurately capture the important components that contribute the model's predictions. Specifically, let yı and ği denote the ground- truth and predicted values for the i-th input graph, respectively. Moreover, k denotes the sparsity score of the selected subgraph in which nodes whose importance scores obtained by Equation are among the top-(A: x 100) % within the original graph, and its prediction is denoted by of. Additionally, ji- denotes the prediction based on the remaining subgraph. The Fidelity scores are computed as follows:
N
N
F_ N
Σ
T(u = 0.) I(y, -.f), F
Σ
I(y. 5.) - I( -)
(17)
N
where I[(: De)) is the binary indicator which returns if y/s Di. and O otherwise. In other words, they measure how well the predictions made solely based on the extracted subgraph (i.e., FF. and the remaining subgraph (i.e., F4) mimic the predictions made based on the entire graph, respectively. Hence, a low value of F_ and a high value of F_ indicate better explainability of the model.
Table 2 shows the fidelity scores on four datasets the sparsity score of k
Table 2: Evaluation on graph interpretation (Fidelity scores).
Method
F.
0.5. Our proposed model outperforms both post-hoc and built-in state-of-the- art explanation models in
RLM
HLM-CLint
QED
DRD2
RLM
HLM-CLant
QED
DRD2
GNNexplaner
0.478
0.616
0.498
0.43
0.894
0,778
0.601
0.740
PGexplainer
0.502
0.620
0.560
0.686
GiB
0.483
0.643
0.525
0.428
0.654
0.781
0.601
0.724
VGIB
0.463
0.579
0.487
0.424
0.765
0.792
0627
0.756
FOlB
0.F1
0.593
0.247
PGIB + merge
0.415
0.543
0.447
0.379
0.765
0.796
0.635
0.781
all datasets. Furthermore,
merging prototypes achieves significant improvements in terms of interpretability. This implics
8

---

(x) cont
(b) vGin
(c) ProtGNN
(d) GHNexplainer
(e) pott
(f] VGIB
(p) ProtoRN
(h) cHneexplainer
Figure 3: Explanation visualizations on Mutag (a-d) and BA-2Motifs (e-h)
20
VGR
0.5
64
0.4
0.6
0.4
0.05
9.5
0.15
0.50
076
MS
Sparaity
Sparaity
Sparati
Sparaal
RLM-CLint
(b) HLM-CLint
(c) QED
(d) DRD2
(4) 0.000s
[o m1
Figure 4: Comparisons of fidelity scores over sparsity scores k. Figure 5: Gp visualization over
that decreasing the number of prototypes eliminate uninformative substructures and emphasize key substructures, which increases the interpretability of the extracted subgraphs. Figure 4 visualizes the comparison of fidelity scores various sparsity scores of subgraphs. To ensure fair compari- son, the fidelity scores are compared under the same subgraph sparsity, as the difference between the predictions of the original graph and subgraph strongly depends the level of sparsity. We observe that PGIB com achieves the best performance in most sparsity environments on the four datasets.
4.4 Hyperparameter Analysis
In Figure 6, conduct sensitivity analysis on the hyperparameters 0n and 0g of the final loss (Equation 16) relevant mutual information. Note that on and 02 are related minimizing T(G; wub) and maximizing (G 9p), respectively. 1) Figure 6(a) shows a significant decrease in performance when becomes large, i.c., when the model focuses on compressing the subgraphs. This is because too much compression of subgraphs results in the loss of important information, ultimately having a negative impact on the downstream performance. However, when = 0 (i.e.. G = Goubi no compression at all). uninformative information would be included in Gsub, which incurs a performance degradation. 2) Figure 6(b) visualizes the change in performance depending on a2. A small value of 0:2 prevents information from Gvub to Gp. whereas excessive value 02 allows the influence of Grus dominate the prototypes Gp. both of which lead to performance deterioration. For example, in Mutag dataset, a low value of a2 ultimately results in Gp not obtaining label-relevant information (i.e., NO2) that is captured by Geub (See Figure 5(a)). On the other hand, high value of ag hinders the formation of diverse prototypes (See Figure 5(b)).
Figure 6: Impact of a; and a2 on PROTEINS dataset.
75
1000
0.33
0,6801
2.01
(3) m
sufficient transmission
Conclusion and Future work
We propose novel framework of explainable GNNs, called interpretable Prototype- based Graph Information Bottleneck (PGIB), that integrates prototype learning into the information bottleneck framework. The main idea PGIB to learn prototypes that capture subgraphs containing key structures relevant to the label information, and to merge the semantically similar prototypes for better model interpretability and model complexity. Experimental results show that PGIB achieves improvements not only in the performance downstream tasks, but also provides more precise

---

explanation of the reasoning process. For future work, we plan to further extend the upplicability of PGIB by integrating domain knowledge into prototype learning by imposing constraints on subgraphs. We expect that this approach would enable the learning of prototypes that align with the domain knowledge as they obtain domain-specific information from the subgraphs.
Acknowledgments and Disclosure of Funding
This work was supported by Institute of Information & Communications Technology Planning (yaluation(IITP) grant funded by the Korea governmen((MSITT) (RS- PRS-2023-00216011 No.2022-0- 00077), and the National Research Foundation of Korea(NRF) funded by Ministry of Science and ICT (NRF-2022M3JJA1106000))
References
[1] K. M. Borgwardt, C. S. Ong, S. Schönauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl_))i47-is5t 1):44-i56,, 2005.
[2] C. Chen, O. Li, D. Tao, A. Bareett, C. Rudin, and J. K. Su. This looks like that: deep learning for interpretable image recognition. Advances in neural information processing systems, 32, 2019.
[3] M. Cranmer, A. Sanchez Gonzalez, P. Battaglia, R. Xu, K. Cranmer, D. Spergel, and S. Ho. Discovering symbolic models from deep learning with inductive biases. In Advances in Neural Information Processing Systems, pages 77429-17443 2020.
[4] A. K. Debnath, Lopez de Compadre, Debnath, A. Shusterman, and C. Hansch. Structure- relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
[5] D. Dobson and A. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-788 2003.
[6] F. Delei-Velez and B. Kim. A roadmap for rigorous science of interpretability. arXiv preprint VrXiv:/702.00S
2(1), 2017.
[7] R. D. Hjelm, A. Fedorov, S. Savoie-Marchildon. K. Grewal, P. Bachman, A. Trischler, and Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 180.::6880000 2018.
[8] J. Irwin and B. Shoichet. Zinc- free database of commercially available compounds for virtual screening. Journal of chemical information and modeling, 177 2005.
[9] G. Jaume, P. Pati, B. Bozorgtabar, A. Foncubierta, A. M. Anniciello, F. Feroce, T. Rau, J.- Thiran, M. Gabrani, and O. Goksel. Quantifying explainers of graph neural networks in computational pathology. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 8106-81 16, 2021.
[10] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 2016.
[11] N. Lee, D. Hyun, G. S. Na, S. Kim, J. Lee, and C. Park. Conditional graph information bottleneck for molecular relational learning. arXiv preprint arXiv:2305.01520. 2023.
[12] D. Luo, W. Cheng, D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang. Parameterized explainer for graph neural network. In Advances in Neural Information Processing Systems, pages 19620-19631, 2020.
[13] S. Miao, M. Liu, and P. Li. Interpretable and generalizable graph learning via stochastic attention mechanism. International Conference on Machine Learning, pages 55524-15543 PMLR, 2022.
10

---

[14] P. E. Pope. S. Kolouri, M. Rostami, C. Martin, and H. Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10772-10781, 2019.
[15] C. Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence. 1(5):206-25 215,,-215220 2019.
[16] M. Rupp, Tkatchenko, K.-R. Müller, and O. Von Lilienfeld. Fast and accurate modeling of molecular atomization energies with machine learning, Physical review letters, 108(5):05830,, 2012.
[17] D. Rymarezyk, t.. Struski, Tabor, and Zielinski. Protopshare: Prototypical parts sharing for similarity discovery in interpretable image classification. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1420-1430, 2021.
[18) D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, Huang, A. Guez, T. Hubert, Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nalure, 550 (7676):354-35) 109,,,99222 2017.
[19] Q Sun, J. Li, H. Peng. J. Wu, X. Fu, C. Ji, and S. Philip. Graph structure learning with variational information bottleneck. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 4163-4174, 2022.
[20] Y. Tian, D. Krishnan, and Isola. Contrastive multiview coding. Computer Vision-ECC' 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI 16, pages 776-794, Springer, 2020.
[21] N. Tishby, F. C. Pereira, and W. Bialek, The information bottleneck method. arXiv preprint physics/0004057, 2000.
[22] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint arXi:: 10903, 2017.
[23] M. Vu and M. T. Thai, Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In Advances in Neural Information Processing Systems, pages 12225-12235, 2020.
[24] N. Wale, I. A. Watson, and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14:347-375, 2008
[25] T. Wang. Gaining free or low-cost interpretability with interpretable partial substitute. In International Conference on Machine Learning, pages 6505-6514. PMLR, 2019.
[26] Wencel-Delord and F. Glorius. C-h bond activation enables the rapid construction and late-stage diversification of functional molecules. Nature chemistry, 565):369-375 2013.
[27] T. Wu, H. Ren, P. Li, and J. Leskovec. Graph information bottleneck. Advances in Neural Information Processing Systems, 33:20437-20448, 2020.
[28] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: /810000000 2018.
[29] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec. Gnnexplainer: Generating explana- tions for graph neural networks. Advances in Neural Information Processing Systems, pages 9251, 2019.
[30] Y. You, T. Chen, Y. Sui, T. Chen, Z. Wang, and Y. Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-5823, 2020.
[31] Yu, Xu, Y. Rong. Y. Bian, Huang, and R. He. Graph information bottleneck for subgraph recognition. In International Conference Learning Representations, 2021.
[32] J. Yu, J. Cao, and R. He. Improving subgraph recognition with variational graph information bottleneck. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 19396-19405 2022.
11

---

[33] H. Yuan, J. Tang, X. Hu, and S. Ji. Xgnn: Towards model-level explanations of graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 430 430-438, 2020.
[34] H. Yuan, H. Yu, S. Gui, and S. Ji. Explainability in graph neural networks: A taxonomic survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[35] Z. Zhang, Q. Liu, H. Wang, C. Lu, and C. Lee. Protgnn: Towards self-explaining graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 9127-9135, 2022.
12


Reviews:
[{"review_id": "6gRj3wyZJy", "reviewer": "Reviewer_fJjc", "summary": "This paper investigates the usage of prototype learning for GNN explainability, focusing in particular on identifying key subgraphs through the graph information bottleneck principle.\n\nExtensive experiments are conducted, which consider several baselines and different molecular datasets.", "questions": "See previous point.", "limitations": "See previous point on better discussing the limitations of the results.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The scope of the paper is well-defined, and the goal of the novel method is relevant.\n- The method is well described and motivated, and the code has been made available to improve reproducibility.\n- The baselines include diverse, recent SOTA methods. Different real-world datasets have been used. Overall, the experiments appear robust.", "weaknesses": "- The main weakness in my opinion is that it is hard to conclude that the proposed method consistently outperforms all the baselines across all the metrics, given the reported results. For example, are the results in Table 1 statistically significant, given how large the confidence interval is? Similarly, in Table 2 for F+, VGIB reports the same results (why they are not bold?). \nI think that the proposed method clearly has an advantage for some properties/metrics, but the complexity of the results should be better discussed n the text. I suggest (1) extending the discussion about the limitations of the model and (2) extending the analysis to investigate in what contexts (and why) the model significantly outperforms the baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "---\n**Weaknesses**\n\n**Q1.** The main weakness in my opinion is that it is hard to conclude that the proposed method consistently outperforms all the baselines across all the metrics, given the reported results. For example, are the results in Table 1 statistically significant, given how large the confidence interval is? Similarly, in Table 2 for F+, VGIB reports the same results (why they are not bold?).\n\n**A.** Thank you for your valuable feedback. To address your concern, we have conducted a statistical analysis, specifically a paired t-test (n=10), providing the p-value and the confidence interval. We perform a t-test between our methods and the runner-up baseline. Here are the results of the experiments.\n\n---\n| Table 1 (Paired t-test) |          |         |             |\n|:-----------------------:|:--------:|:-------:|:-----------:|\n|         Dataset         | baseline | p-value |      CI     |\n|          MUTAG          |   VGIB   |  0.0606 |  (0.0, inf) |\n|         PROTEINS        |    GIB   |  0.0080 | (0.01, inf) |\n|           NCI1          |  ProtGNN |  0.0006 | (0.02, inf) |\n|            DD           |   VGIB   |  0.0962 |   0.0962   |\n\nWe established a confidence level of 95% and an alternative hypothesis indicating that the mean differences between our method (PGIBcont) and the baseline are greater than 0. With the exception of MUTAG and DD datasets, the p-values are sufficiently small to reject the null hypothesis, while the two datasets (MUTAG and DD) still exhibit values that are relatively close to the significance level. For the MUTAG dataset, which inherently contains a small number of data points (188 instances), the outcomes tend to exhibit a larger standard deviation (as indicated by [1], [2] ). In DD dataset, IB based methods tend to have a large standard deviation. However, we would like to highlight that our method does not exhibit such tendencies even if it is based on IB. We attribute this to the consideration of various prototypes beyond merely the substructures of the input graphs.\nRegarding Table 2 for F+, we apologize for any confusion that we may have caused. Thank you for bringing this to our attention. We will make sure to fix them for the revised version. \n\n[1] Sui, Y., Wang, X., Wu, J., Lin, M., He, X., & Chua, T. S. Causal attention for interpretable and generalizable graph classification. KDD 2022\n\n[2] Yu, J., Xu, T., Rong, Y., Bian, Y., Huang, J., & He, R. (2020). Graph information bottleneck for subgraph recognition. arXiv preprint arXiv:2010.05563.\n\n---\n\n**Q2.** I think that the proposed method clearly has an advantage for some properties/metrics, but the complexity of the results should be better discussed n the text. I suggest (1) extending the discussion about the limitations of the model and (2) extending the analysis to investigate in what contexts (and why) the model significantly outperforms the baseline.\n\n**A.**  Thank you for your valuable suggestion regarding further discussions on advantages and limitations of our proposed method.\n- **A further limitation of our model**: Beyond the limitation we mentioned in A.7, the performance of our proposed method can be compromised when graphs in the dataset inherently lack task-relevant substructures (e.g., social network data, traffic network data, etc). This is mainly because the key underlying assumption of our model is the existence of task-relevant important substructures.\n- **When and why our method performs well**: Conversely, our proposed method demonstrates strong performance when the dataset comprises explicit label-representing substructures, as seen in molecular graphs, due to its capacity to capture subgraphs and conduct predictions. Additionally, the complex correlation between the substructure and various prototypes can be actively used for label prediction, which can improve both label prediction performance and interpretability.\n\nWe thank the reviewer for the valuable suggestion, and we will make sure to include the above discussions in the revised paper.\n"}, {"review_id": "g604l9C48g", "reviewer": "Reviewer_Q5w4", "summary": "The paper introduces a new design of interpretable graph neural networks (GNNs) that combines ideas from information bottleneck approaches and prototype based approaches for by-design interpertation. The system titled PGIB extracts a subgraph from a given input graph and compares the embedding of the extracted subgraph in latent space to a set of learnt prototype subgraphs for final prediction. The authors evaluate their method on multiple datasets and baselines for classification performance and fidelity and demonstrate their efficacy for both.", "questions": "1. **Hyperparameter selection:** -- I am a little puzzled by the hyperparameter choices selection. For eg. is the performance drop in Fig. 6(a) \"drastic\". It is just 2-3% drop in mean performance throughout from $\\alpha_1=0$ to $1$. Am I understanding the graph incorrectly? The behaviour you highlight in A.4.3 is expected but I am rather thinking how is the performance still so high if the subgraphs are too compressed for $\\alpha_1=1$? Similarly $\\alpha_2$ choice also seems arbitrary based on the Fig. 6(b) with even less performance variation. \n\n2. **Ablation** -- The number of prototypes and parameters for merge operation. How were they determined? How do they affect the interpretability and performance?\n\n3. Typos in line 126 (\"is maximizes\"), line 312 (\"Fidlity\"), Fig 4 ('sparcity') ", "limitations": "Authors discuss these in supplementary. I would prefer to have the limitations in the main paper.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The presented idea is novel. I have not seen any previous approach combining information bottleneck principles with prototype based classification.\n\n2. The choice of baselines for comparison and overall experimental setup is solid. The main results in the paper are also convincing and positively reflect for the method.\n\n3. The paper is generally well written with clear motivations.\n\n", "weaknesses": "1. The paper while reading gives sense of having too many moving parts. \n\n2. Hyperparameter selection is understudied and feels arbitrary. The ablation studies should be strengthened.\n\n3. Interpretation analysis --  Various choices in the system (loss weights or otherwise) are not well studied from the lens of interpretability. There are comments made around $\\alpha_1, \\alpha_2$ in Sec 4.4 but are not very well supported, with sparing analysis in appendix. At the very least for multiple choices you should include qualitative results specially for the ones for which you have some insights.\n\nOverall it's a decent paper but various choices the authors make need to be better supported experimentally.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "---\n\n**Weaknesses**\n\n**W1.** Too many moving parts.\n\n**A1.** Thank you for your valuable feedback. We will make adjustments to the placement of the figures and tables to ensure they are easy to follow in our paper.\n\n---\n\n**W2.** Hyperparameter selection / Ablation studies.\n\n**A2.**  We sincerely appreciate your feedback. To provide further clarity in our analysis of PGIB, we conducted an ablation study at a more fine-grained level than what was initially presented in the paper. We will include these additional results and analysis to provide a better understanding of our model. Here are the results and the corresponding analysis: \n\n**Table R1.**\n| **$\\alpha_1$** |    **0**   | **0.0001** |  **0.001** |  **0.01**  |   **0.1**   |    **1**   |\n|:--------------:|:----------:|:----------:|:----------:|:----------:|:-----------:|:----------:|\n|    PROTEINS    |  76.8±3.16 | **77.50±2.42** | 75.72±2.32 | 75.54±3.04 |  73.75±5.37 | 73.48±4.25 |\n|      NCI1      | 75.21±1.41 | **78.25±2.13** | 73.75±3.04 | 74.09±3.15 |  72.55±2.55 | 69.09±2.18 |\n\n**Table R2.**\n| $\\alpha_2$   | 0          | 0.0001         | 0.001      | 0.01             | 0.1        | 1          |\n|----------|------------|----------------|------------|------------------|------------|------------|\n| PROTEINS | 75.98±2.84 | 76.43±2.89 | 76.25±2.23 | 76.16±4.47       | **77.50±2.42** | 75.18±2.10 |\n| NCI1     | 74.79±1.59 | 76.16±2.92     | 75.84±2.91 | **78.25 ± 2.13** | 76.71±2.80 | 72.21±1.96 |\n\nTable R1 and R2 show that it is important to select appropriate parameters, as $\\alpha_1$ has a significant influence on the degree of compression of the subgraph, and $\\alpha_2$  plays an important role in learning the prototype, respectively.\n\n**Table R3.**\n| The number of prototypes | 3 → 1       | 4 → 2      | 5 → 3      | 6 → 4      | 7 → 5          | 8 → 6          | 9 → 7      |\n|--------------------------|-------------|------------|------------|------------|----------------|----------------|------------|\n| MUTAG                    | 81.5±3.91   | 82.0±6.4   | 84.5±4.7   | 85.0±5     | **85.5±5.22**  | 84.5±3.5       | 85.0±4.47  |\n| PROTEINS                 | 70.18.±2.19 | 71.7±3.02  | 74.4±2.11  | 75.26±2.82 | **77.5±2.42**  | 76.25±2.37     | 75.27±3.39 |\n| NCI1                     | 74.97±1.68  | 77.1±1.80  | 76.7±2.00  | 77.59±1.66 | 78.25±2.13     | **78.81±1.84** | 77.0±1.79  |\n| DD                       | 69.50±2.52  | 73.78±3.94 | 74.79±3.19 | 75.20±3.12 | **76.13±3.76** | 74.04±2.77     | 76.04±2.74 |\n\nTable R3 shows the importance of selecting a sufficient number of prototypes. For example, 4→2 indicates 4 prototypes per class, which are then merged to 2 prototypes per class. Since the number of prototypes determines the diversity of prototypes, a small number of prototypes hinders the formation of diverse prototypes.\n\n---\n\n**W3.** Interpretation analysis \n\n**A3.**  Thank you for your valuable feedback. We have attached a pdf file containing interpretation analysis to the global response. We hope this response adequately addresses your concern. \n\n---\n\n**Questions**\n\n**Q1.** Hyperparameter selection\n\n**A.** Thank you for sharing your insights on our experiments. To further clarify our analysis of Figure 6 and A.4.3, we have extended the analysis for $\\alpha_1$ and $\\alpha_2$ and also included performance evaluation using additional dataset.\n\n- Regarding the term “drastic” in Figure 6(a)\n  -  We understand that it might be subjective. We want to emphasize that similarly to other GIB methods [1,2], the overall performance of our method is primarily influenced by the classification loss. This explains why the performance remains relatively high even when the value of $\\alpha_1$ is high. In the context of $\\alpha_1$, the term \"drastic\" refers to the relative impact on the performance within a specific range of $\\alpha_1$ values. We have observed a similar tendency in the results of additional dataset as well in Table R1. \n\n- Regrading the Less Variation in Performance in Figure 6(b)\n  -  As we mentioned before, the overall performance of our method is mainly affected by the classification loss. To conduct a more comprehensive analysis of the performance variation influenced by $\\alpha_2$, we conducted experiments on an additional dataset in Table R2. These results demonstrate that although it exhibits less variation in performance compared to the effect of $\\alpha_1$, it still clearly illustrates the performance gap between the model with an appropriate $\\alpha_2$ and the model without it.\n  -  Furthermore, we want to emphasize that $\\alpha_2$ significantly impacts the interpretability of the reasoning process in the Figure PDF-1. As we addressed in the global response, $\\alpha_2$ plays a crucial role in ensuring the interpretability of prototypes, thereby enhancing our model's overall explainability.\n\n**Q2.**  Ablation\n\n**A.**  Thank you for raising this important point and for your valuable suggestion. As mentioned earlier, in Table R3, we have conducted additional experiments where we varied the number of prototypes per class and the final number of prototypes after merging them.\nAdditionally, we conducted interpretation visualizations of $\\mathcal{G}_ {p}$ based on the number of prototypes in Figure PDF-4. When the number of prototypes is small, the prototypes do not contain diverse substructures. This limitation arises due to the necessity of making predictions using a restricted number of prototypes. On the other hand, if the number of prototypes is large, a greater diversity of prototypes can be achieved because various and complex information can be obtained from $\\mathcal{G}_ {sub}$.\n\n[1] Yu, Junchi, et al. \"Graph information bottleneck for subgraph recognition.\" arXiv 2020\n\n[2] Yu, Junchi, et al. \"Improving subgraph recognition with variational graph information bottleneck.\" CVPR 2022\n\n**Q3.** Typos\n\nWe appreciate your attention to the overlooked typos. We will make sure to fix them for the revised version.\n"}, {"review_id": "vl74daB5Yz", "reviewer": "Reviewer_DMtB", "summary": "Interpretable graph learning can promote the use of graph-based scientific applications by providing model explanations. This paper focuses on extracting key subgraphs and employing a case-based reasoning process (also known as prototype learning) for model prediction. To make the extracted substructures more informative, the information bottleneck theory is incorporated into the subgraph extraction. Several strategies, such as prototype merging and connectivity constraints, are used to improve the model's interpretability and accuracy. Finally, this paper provides both qualitative and quantitative analyses of the model's interpretability and performance.", "questions": "1.\tWhat is the physical meaning of $p_i$ in Eq. 5? It seems to represent the extent of interference on the node representation. It is unclear how this practice can be considered as selecting a subgraph, making the physical meaning of connectivity loss also unclear.\n2.\tWhy adding interference to the nodes according to the probability $p_i$ yields the representation of the subgraph? Is the subgraph representation obtained in this way equal to $f_g(G_{sub})$?\n3.\tIn Eq. 8, how is the first inequality derived?\n", "limitations": "The authors have discussed the limitations and societal impacts.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.\tThe idea of using prototype learning to explain key substructures of the input graph is intuitive and reasonable.\n2.\tThe extension of information bottleneck theory to prototype learning is inspiring and has practical utility in a wide range of application scenarios. In particular, it can help compress excessive information from the input graph and provide more fine-grained explanations, including key subgraphs and representative examples.\n3.\tThe paper is well-organized and easy to follow.\n", "weaknesses": "1.\tThe related works are not properly cited. For example, the prototype merging method is quite similar to the one used in ProtoPShare [1], yet the author simply claims that \"We propose a method to effectively merge the prototypes\" (Line 224), without mentioning any existing works. This can confuse readers about the technical contribution.\n[1] Rymarczyk, Dawid, et al. \"Protopshare: Prototypical parts sharing for similarity discovery in interpretable image classification.\" Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021.\n2.\tThe paper's experiments are not sound enough. Firstly, the paper should include at least one black-box GNN model for performance prediction. Secondly, when evaluating the fidelity scores, ProtGNN should not be excluded (Section 4.3). Third, the paper is missing ablation studies for some proposed components, such as Connectivity loss.\n3.\tThe design of dropping the first term in equation 9 (in Section 3.3.2) is not well-motivated. The goal is to minimize the whole $I(Y;\\mathcal{G}p|\\mathcal{G}{sub})$ instead of the single term $I(\\mathcal{G}p ; \\mathcal{G}{sub})$. The paper should provide essential theoretical analysis to better illustrate the effectiveness and rationality of this optimization goal.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1** Thanks for raising this issue. In fact, we are aware of ProtoPShare, and thus we cited it in Sec 3.5 Line 223 reference “[15]”. While ProtoPShare is the first work that applies prototype merging in image classification, our work is the first work to demonstrate the effectiveness of prototype merging in graph-structured data. We fully agree that the sentence in Line 224 “We propose ... ” may have confused the reviewer, and we will make sure to revise along with an explicit citation: “Inspired by ProtoPShare “[15]”, we propose a prototype merging technique for graph-structured data..” \n\n **W2**  \n-**Black-Box GNN**  \n\nFind results attached in pdf (Tab P1). We observe our model outperforms black-box GNNs.\n\n-**Fidelity Scores of ProtGNN**  \n\nWe would like to clarify that measuring the fidelity score of ProtGNN is not possible. We explain reasons:\n- First, recall that our model provides interpretability in two aspects: 1) model’s prediction based on the substructure of the input graph (i.e., $G_{sub}$) (Sec 4.3), and 2) model’s reasoning process based on the visualization of learned prototypes (i.e., $G_p$) (Apx 4.4).\n- Moreover, fidelity score quantifies the extent to which explanations accurately capture the important components that contribute to the model prediction (Line 307), meaning that fidelity score is measured based on $G_{sub}$ and not $G_p$.\n- However, ProtGNN is method for explaining the model’s reasoning process based on $G_p$, and it does not extract key subgraph $G_{sub}$. Hence, its fidelity score cannot be measured.\n\nWe may still consider using $G_p$ to compute the fidelity score. However, as $G_p$ is obtained by projecting prototypes onto the training graphs, $G_p$‘s produced by different methods would be projected onto different training graphs, which means that different graphs are to be compared for same target. This variability makes it challenging to fairly compare fidelity scores across different graphs. Therefore, we only compare fidelity scores with methods that provide interpretability for $G_{sub}$ (GIB, VGIB, and PGIB). \n\n-**Ablation**\n\nExperiment on connectivity loss is shown in A.4.1. To provide further clarity in our analysis of PGIB, we conducted an ablation study including the connectivity loss at a more fine-grained level in Table R1, R2, and Table PDF-2. Additionally, interpretation visualization of $G_{sub}$ varying with Connectivity Loss is presented in Figure PDF-3.\n\n**W3**\nNote that the two terms in Eq 9 originate from $-I(Y;G_{sub})$, which is the 1st term in Eq 3. That is, minimizing $-I(Y;G_{sub})$ aims to increase the information regarding $Y$ in $G_{sub}$, and thus the two terms in Eq 9 both aim to increase the information regarding Y in $G_{sub}$.  Given this fact, it is intuitive that minimizing the 1st term in Eq 9, i.e., $I(G_p;Y,G_{sub})$, aims to reduce the information of Y from $G_p$, which eventually increases the information regarding Y in $G_{sub}$. In other words, $I(G_p;Y,G_{sub})$ includes removing the quantity of Y from $G_p$, because it solely aims to maximize $I(Y;G_{sub})$. However, our goal is to establish an interaction between $G_p$ and $G_{sub}$ to enhance both performance and interpretability of reasoning process. For this reason, we excluded the 1st term.\n\n**Q1**\n\n**-Eq.5**\nEq. 5 controls the degree of interference in the node representation. $p_i$ is learned from node representation $h_i$ through MLP, and it attenuates the information of $G$ by injecting noise into node representation. ϵ is the noise sampled from parametric noise distribution. We assign each node a probability of being replaced by noise ϵ, and $p_i$ controls the information transmitted from $h_i$ and ϵ to $z_i$, e.g., when $p_i$ = 1, all information from $h_i$ is transmitted to $z_i$. Conversely, when $p_i = 0$, $z_i$ contains only noise ϵ and does not include any information from $h_i$. In short, we expect unimportant nodes to be replaced by noise ϵ, while remaining nodes constitute an important subgraph.\n\n**-Connectivity Loss**\nIt aims to minimize the number of isolated nodes in $G_{sub}$, and promote connected subgraphs in order to enhance interpretability of $G_{sub}$. Specifically, $S_g$[j, 0] and $S_g$[j, 1] denote the probability of node $v_j$ ∈ $V_g$ belonging to $G_{sub}$ and $\\bar{G}_{sub}$, respectively.\n\n$a_{11}=\\sum_{i,j}A_{ij}p(V_i\\in G_{sub}|V_i)p(V_j \\in G_{sub}|V_j),$\n$a_{12}=\\sum_{i,j}A_{ij}p(V_i\\in G_{sub}|V_i)p(V_j \\in \\bar{G}_{sub}|V_j).$\n\nFor example, we use $a_{11}$ and $a_{12}$ to denote the element (1,1) and the element (1,2) of $S^TAS$. Minimizing Lcon causes a11/(a11+a12) to approach 1, indicating that if Vi is in Gsub, its neighbors also have a high probability to be in $G_{sub}$. On the other hand, minimizing $L_{con}$ causes $\\frac{a_{12}}{a_{11}+a_{12}}$ to approach 0, indicating that when $V_i$ is in $G_{sub}$, its neighbors have a low probability to be in $\\bar{G}_{sub}$.\n\nIn other words, $L_{con}$ aims to minimize the number of isolated nodes in a subgraph $G_{sub}$ by adjusting the node selection probabilities based on the connectivity information of $G$, which leads to stable connectivity.\n\n**Q2**\nRefer to our answer to Q1 for why adding interference yields the representation of the subgraph. Moreover, since we adopt the max pooling for $f_g$, the subgraph representation obtained in this way is equal to $f_g(G_{sub})$.\n\n**Q3**\nBy definition we can derive,\n\n$I(Y;G_{sub},G_p) = E_ {Y,G_{sub},G_p}  [\\log p(Y|G_{sub},G_p)-p(Y)]$,\n\n$I(Y;γ(G_{sub},G_p)) = E_{Y,G_{sub},G_p}  [\\log p(Y| γ(G_{sub},G_p))-p(Y)]$.\n\nAdditionally it is known that the following holds due to information loss in mutual information [1].\n\n$I(Y;G_{sub},G_p) ≥ I(Y; γ(G_{sub}, G_p))$\n\nTherefore, we can obtain following inequality:\n\n${E}_ {Y,G_{sub},G_p}[\\log p (Y |G_{sub}, G_p)] - E_Y [\\log p(Y)] ≥ E_{Y,G_{sub},G_p} [\\log p(Y |γ(G_{sub}, G_p))]−E_Y[\\log p(Y )]$\n\n[1] Learning invariant graph representations for out-of-distribution generalization. NIPS22"}, {"review_id": "DATPM6cXgP", "reviewer": "Reviewer_qf5C", "summary": "The authors propose a new GNN explanation framework, which combines prototype learning and the information bottleneck. They define the Prototype-based Graph Information Bottleneck framework in detail, and experiments have demonstrated the effectiveness of their proposed framework.", "questions": "1.I wonder if the authors' proposed approach can alleviate the OOD problem which is widely discussed in the explanation GNNs[1,2].\n\n2.I notice that the authors obtain two types of subgraphs, one in the Subgraph Extraction Layer and one in the Prototype Projection. In practice, which type of subgraph do we use as the final interpretation? What if the two types of subgraphs conflict? \n\n3.If the interpretability of the prototypes is not considered,  can the Prototype Projection method  be removed?\n\nReferences:\n\n[1] Debiasing graph neural networks via learning disentangled causal substructure.\n\n[2] Causal attention for interpretable and generalizable graph classiﬁcation.\n\n\n", "limitations": "See Weaknesses for details.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.The authors introduce the Graph Information Bottleneck based on prototype learning, which makes a significant improvement over the baseline methods.\n\n2.The experiments are comprehensive and there are many additional experiments in the appendix.\n\n3.The paper is well written.\n\n\n", "weaknesses": "1.I argue that the novelty of the paper is limited by the fact that both the IB approach and the prototype approach have been well discussed before, and the authors seem to have simply combined the two methods together.\n\n2.The number of prototypes per class is an important hyperparameter and the author should add a hyperparameter analysis of it.\n\n3.I am not quite sure about the differences between PGIB and ProtGNN. If I use the GIB strategy in ProtGNN, what effect will it have?\n\n4.In this paper, authors use GIN as a backbone. However, PGIB as a model-agnostic approach should be validated on more GNN structures, e.g. GCN, GraphSage.\n\n\nOthers:\n\n1.Line 143 \"PGIB s a novel \" ->\"PGIB is a novel \"\n\n2.Line 275 \"This is because When\" -> \"This is because when\"\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1.**  \n**# Method Selection Inspired by Motivation and Purpose**  \nAs highlighted in our introduction, ProtGNN utilizes prototypes to explain the model's training process (i.e., reasoning process (RP)). However, we found that ProtGNN overlooks the key substructures in input graphs, leading to less informative RP and decreased performance in downstream tasks (Fig. 1(a)). Drawing from this observation, we recognize the importance of including informative information from the input graphs, while excluding uninformative information in the RP.\nThe key to addressing these challenges is through identifying the key substructure of an input graph. Among the methods available for extracting key substructures (e.g., GNNexplainer, PGexplainer, subgraphX, IB), we chose the IB-based approach because it is currently the most effective approach for identifying important substructures during the learning process. Unlike post-hoc methods, IB allows us to extract key substructures during the training process, aligning with our objectives. We would be delighted if the novelty of our work is recognized in the motivation behind our choices, rather than merely in the method itself.  \n**# Theoretical Analysis for a Well-Designed Loss Function**  \nAdditionally, we want to clarify that our approach goes beyond a simple combination of existing methods. We designed and implemented our loss function based on a thorough theoretical analysis. Our work is the first paper to provide a theoretical framework for approaching IB from the perspective of prototypes. Specifically, we introduced a $L_{MI}^2$ loss, which not only improves the interpretability of the RP (See Fig 1(b)), but also the model performance on downstream tasks (See Fig 6(b)). The newly introduced loss, $L_{MI}^2$, plays a key role in enabling the mutual interaction between $G_{sub}$ obtained from the IB approach, and the prototype $G_p$.  \n**# Interpretability Stabilization via Prototypes Merging**\nLastly, it is important to note that, inspired by ProtoPShare, our work is the first work that introduces an effective method for merging prototypes in the graph domain, aimed at enhancing not only both the explanation of the reasoning process, but also the overall performance on downstream tasks. \nWe hope that this clarification highlights the contributions of our research and provides a better understanding of our work's motivations and goals.   \n\n**W2.**  \nWe have conducted additional experiments where we varied the number of prototypes per class. Table PDF-5 shows the results of the graph classification according to the number of prototypes. \nAdditionally, we conducted interpretation visualizations of $G_p$ based on the number of prototypes in Figure PDF-4. When the number of prototypes is small, the prototypes do not contain diverse substructures. This limitation arises due to the necessity of making predictions using a restricted number of prototypes. On the other hand, if the number of prototypes is large, a greater diversity of prototypes can be achieved because various and complex information can be obtained from $G_{sub}$.  \n\n**W3.**  \nAs mentioned in our response to W1, a naive combination of ProtGNN and GIB allows each to operate independently. As such, this simple combination does not consider the loss functions like $L_{MI}^2$ in PGIB, and thus, it leads to an uninformative reasoning process. This is because the prototypes may not adequately capture the key substructures that significantly influence the downstream label prediction. We want to emphasize that a naive combination of the prototype approach and the GIB approach is insufficient to enhance the interpretability of the reasoning process and the performance on downstream tasks; careful design of the losses is crucial.\n\n**W4.**  \nWe appreciate your valuable suggestions. In response, we conducted additional experiments using various GNN structures. The results are shown in the Table-P3. It demonstrates the strong performance of our model on different backbones.\n\n**Others**  \nWe appreciate your attention to the overlooked typos. We will make sure to fix them in the revised version.  \n\n**Q1.**  \nWe sincerely appreciate your feedback, and we fully agree with your suggestion to include an OOD task. For these experiments, we utilized real-world molecule graphs, and followed existing studies [3,4] for OOD in which the data is split based on scaffold (i.e., scaffold split).   \n\n[3] Li, Haoyang, et al. \"Ood-gnn: Out-of-distribution generalized graph neural network.\" TKDE (2022).  \n[4] Gui, Shurui, et al. \"Good: A graph out-of-distribution benchmark.\" NIPS (2022).\n\nWe conducted scaffold-based OOD experiments to evaluate the generalization performance of our model. We split our dataset based on the scaffold in a ratio of 8:1:1 and obtain a train and test dataset with totally different distribution by including the scaffold containing the most data in training set. Table-P4 is the result of the experiment, and it demonstrates the generalization performance of our model in an OOD setting.\n\n**Q2.**  \nWe would like to emphasize that explainability can be viewed from two perspectives: 1) interpretability of the model's predictions, and 2) interpretability of the model's reasoning process. As you mentioned, we obtain two types of subgraphs: a) from the Subgraph Extraction Layer, and b) from the Prototype Projection.  \n\n- 'a)' provide interpretation for the model's predictions, giving insights into which subgraph is considered important when the model makes a final prediction.  \n- 'b)' provide interpretation for the reasoning process. In other words, each class can be represented by the prototypes, and we can interpret how the model represents each class during the training process.  \n\nWe understand the reviewer’s confusion, and we will make sure to clearly explain them in the paper. \n\n**Q3.**  \nYes. If there is no need to interpret the reasoning process, it can be removed.\n\n"}]

Author rebuttal:
We appreciate the reviewers for their valuable comments on our paper. We have conducted additional qualitative analysis, which is provided in the attached PDF. In this analysis, we compare the effects of different choices for $\alpha_1$, $\alpha_2$, $\alpha_3$ (i.e., loss weights) and the number of prototypes at a more fine-grained level. 
- Impact of $\alpha_1$

As discussed in Section 4.4, the hyperparameter $\alpha_1$ has an impact on the compression of the subgraph from the entire input graph. In Figure PDF-2, when $\alpha_1$ is less than 0.01, certain parts of the key substructure, specifically NO2 in this case, are excluded, resulting in a decrease in both interpretability and performance. 
- Impact of $\alpha_2$

We have extended the scale of qualitative analysis on $\alpha_2$ shown in Figure 5 to provide a better understanding of its impact. It is crucial that the subgraphs of prototypes not only contain key structural information from the subgraph found by IB but also ensure a certain level of diversity, since each class is represented by multiple prototypes to enhance the model's capacity.
In Figure PDF-1, when we fix $\alpha_1$ to 0.1 the diversity of prototypes varies based on the degrees of $\alpha_2$. Specifically, when $\alpha_2$ becomes 1, the diversity of prototypes decreases, leading to a decline in the interpretability of the reasoning process and the overall model performance. This finding highlights the importance of selecting proper $\alpha_2$  to ensure both interpretability and performance are optimized. 
- Impact of $\alpha_3$

The hyperparameter $\alpha_3$ is associated with the connectivity loss, which plays a crucial role in the interpretability of $G_{sub}$ by promoting a compact topology. In real-world datasets, the key substructure often tends to form non-connected components without $\alpha_3$. In Figure PDF-3, when we exclude the connectivity loss from the final loss function (i.e., set $\alpha_3$ to 0), $G_{sub}$ tends to consist of multiple connected components. As a result, due to the wide and scattered range of detected subgraphs, the absence of connectivity loss results in the formation of unrealistic subgraphs.

We hope that this material highlights the contributions of our research and provides a better understanding of our work. 

Meta-review: Reviewers found this paper exciting and unanimously recommended accept.
Decision: Accept (poster)