GNNBoundary: Towards Explaining Graph Neural Networks through the Lens of Decision Boundaries
Authors: Xiaoqi Wang
Han Wei Shen
Venue: ICLR 2024 poster (2024)
Keywords: AI Interpretability
Graph Neural Networks
Model-Level Explanation of Neural Networks
Decision Boundaries
Primary area: societal considerations including fairness, safety, privacy

Abstract: While Graph Neural Networks (GNNs) have achieved remarkable performance on various machine learning tasks on graph data, they also raised questions regarding their transparency and interpretability. Recently, there have been extensive research efforts to explain the decision-making process of GNNs. These efforts often focus on explaining why a certain prediction is made for a particular instance, or what discriminative features the GNNs try to detect for each class. However, to the best of our knowledge, there is no existing study on understanding the decision boundaries of GNNs, even though the decision-making process of GNNs is directly determined by the decision boundaries. To bridge this research gap, we propose a model-level explainability method called GNNBoundary, which attempts to gain deeper insights into the decision boundaries of graph classifiers. Specifically, we first develop an algorithm to identify the pairs of classes whose decision regions are adjacent. For an adjacent class pair, the near-boundary graphs between them are effectively generated by optimizing a novel objective function specifically designed for boundary graph generation. Thus, by analyzing the nearboundary graphs, the important characteristics of decision boundaries can be uncovered. To evaluate the efficacy of GNNBoundary, we conduct experiments on both synthetic and public real-world datasets. The results demonstrate that, via the analysis of faithful near-boundary graphs generated by GNNBoundary, we can thoroughly assess the robustness and generalizability of the explained GNNs. The official implementation can be found at https://github.com/yolandalalala/GNNBoundary.

Published as a conference paper at ICLR 2024
TOWARDS EXPLAINING GRAPH NEURAL NETWORKS THROUGH THE LENS OF DECI-
GNNBOUNDARY:
SION BOUNDARIES
Xiaoqi Wang
Han- Shen
The Ohio State University wang. 5502@osu. edu
The Ohio State University shen. 940osuu.dii
ABSTRACT
While Graph Neural Networks (GNNs) have achieved remarkable performance on various machine learning tasks on graph data, they also raised questions regarding their transparency and interpretability. Recently, there have been extensive re- search efforts explain the decision-making process of GNNs. These efforts of- ten focus on explaining why a certain prediction is made for a particular instance, what discriminative features the GNNs try detect for each class. However, to the best of our knowledge, there no existing study on understanding the de- cision boundaries of GNNs, even though the decision-making process of GNNs is directly determined by the decision boundaries. To bridge this research gap, we propose model-level explainability method called GNNBoundary, which at- tempts to gain deeper insights into the decision boundaries of graph classifiers. Specifically, we first develop an algorithm identify the pairs of classes whose decision regions are adjacent. For an adjacent class pair, the near-boundary graphs between them are effectively generated by optimizing a novel objective function specifically designed for boundary graph generation. Thus, by analyzing the near- boundary graphs, the important characteristics decision boundaries can be un- covered. To evaluate the efficacy of GNNBoundary, we conduct experiments on both synthetic and public real-world datasets. The results demonstrate that, via the analysis of faithful near-boundary graphs generated by GNNBoundary. we can thoroughly assess the robustness and generalizability of the explained GNNs. The official implementation can be found at this GitHub repository
INTRODUCTION
Graph Neural Networks (GNNs) are widely recognized as powerful tools for modeling graph data across various domains, including chemistry, social networks, transportation, etc (Lin et al. (022). However, their success has raised questions regarding their transparency and interpretabiliity as GNNs are often regarded as black-box models, similar to other types of deep learning models (Wu et al. 2022). The complexity of GNNs makes it challenging for humans comprehend their Docision-making processes, posing a significant obstacle to their application in real-world problems (Chen al. (0236). For example, Partin al. (2023) utilized GNN to predict cancer response (sensitive or resistant) to drug treatments. Nonetheless, if the decision- not adequately verified by humans, we cannot fully trust its prediction in real-world scenarios, especially when it comes to serious matters such as human lives. This underscores the necessity for developing methods to ensure the explainability of GNNs, enabling humans to gain insights into their inner working mechanisms and build trust in their decisions.
process of this GNN
Over the past few years, there has been a growing interest explaining GNNs, leading to extensive research efforts. These studies can be broadly categorized into two main groups: instance-level explanations (Ying et al.) 2019; Luo et al. (020) and model-level explanations Yuaan et al. 2020 Wang & Shen (023). Instance-leve explanations are designed to explain why certain prediction is being made for a specific instance, while model-level explanations aim to disclose high-level decision-making processes without respect any particular instances. In this paper, the proposed

---

Published as a conference paper at ICLR 2024
method can also be categorized model-level explanation. However, unlike the existing model- level explanation methods, we attempt to open the black box of GNNs from a different perspective.
Mounlry
Conthnun Nelmnten
DMM
Detaet
Parn
Demplecte
The overview of GNNBoundary. Given a trained GNN, GNNBoundary first identifies adjacent class pairs, and then generates boundary graphs for each pair. The generated boundary graphs can facilitate a deeper understanding of the decision boundaries of GNN.
Figure 1:
In general, existing model-level methods explain the GNNs by generating a feature descriptor for each class in the graph classification task (Chen et al. 2023a). By analyzing the feature descriptors for each class they generate, one can understand the decision-making rule of the GNNs for individual classes (Wang & Shen 2023). However, they often fail to answer the following questions when explaining the GNNs; (i) which classes are more similar to each other such that the explained GNN will easily get confused? (ii) in what circumstances will the GNN be more uncertain and less confident about its predictions? (iii) how to obtain a comprehensive overview of its decision- making schema that effectively captures the complex relationships between different classes? All of these questions are imperative for understanding the internal mechanism of GNNs, which strongly motivated us to get a deeper understanding of their decision boundary rather than solely focusing on individual classes. We believe that analyzing the decision boundary of GNNs is an indispensable step to fully understand their decision decision-making process, and we are taking the first step in this direction.
In this paper, we propose model-level explainability method, GNNBoundary, to explain the deci- sion boundaries of GNNs on graph classification tasks. Specifically, we first introduce an algorithm to identify pairs of classes whose decision regions are adjacent, given the fact that the decision boundaries would only exist between those class pairs. For each adjacent class pair, GNNBoundary generates graphs that are extremely close to the decision boundary by optimizing a novel objective function specifically designed for satisfying the two desired properties we propose for boundary graph generation. To facilitate the optimization process, dynamic regularization scheduler is in- troduced to reduce the likelihood of trapping in the local minima. In the experimental study, we quantitatively and qualitatively evaluated the efficiency and effectiveness of GNNBoundary on both synthetic and public real-world datasets. The experimental results show that we could consistently generate faithful near-boundary graphs for each adjacent class pair. More importantly, we have demonstrated in the case studies that the generated boundary graphs can be utilized to measure the boundary thickness, boundary margin, and boundary complexity of GNNs trained on three datasets. These three metrics would allow us gain deep insights into the complexity of decision boundaries, the potential risk of misclassification on unseen data, and the model robustness to perturbation.
2 RELATED WORK
Instance-Level Explanations of GNNs. Instance-level explanation methods provide input- dependent explanations for the explained GNNs. Their main goal is to explain why a certain pre- diction made for a particular instance. Specifically, the important input features that contribute the most to model predictions are identified for given instance. Based on a recent survey (Kakkad al. 2023). instance-level explanation methods can be decomposed into five different categories: decomposition methods (Schnake et al., (021). gradient-based methods (Pope et al. 2019), sur- rogate methods (Duval & Malliaros 202 1), perturbation-baser methods (Ying et al. 2019), and
baasra methods (Luo et al. 2020 They determine the important input features for the prediction of a particular instance in a different way.
Model-Level Explanations of GNNs. On the contrary, model-level explanation methods focus on explaining the high-level decision-makingg process of GNNs which is not specific to any particular instance. However, this is much less explored than instance-level methods. Generally speaking, the existing level-level methods often produce a feature descriptor to describe the most discrimi- native features GNNs try detect for each class. This feature descriptor could be in the form of
2

---

Published as a conference paper at ICLR 2024
an explanation graph (Wang & Shen, 2023 Yuan et al. 2020 or logic formula (Azzolin et al. 2023). GNNBoundary also fall into this category. Similar to GNNtnterrree (Wang & Shen 2023). >
GNNBoundary also adopts the Gumbel-Softma trick Oang al. 2016) to generate graph that minimizes an objective function. However, there is a fundamental difference in the objective func- tion: GNNBoundary attempts to generate the graphs lying on decision boundaries, whereas GN- NInterpreter aims at generating graphs with the most discriminative pattern of individual classes. It is worth mentioning that, the best of our knowledge, GNNBoundary is the first explainability method that focuses on explaining and analyzing the decision boundaries of GNNs.
Explaining Decision Boundary of Neural Networks. Although there are no previous studies on explaining the decision boundaries of GNNs, there are few studies on analyzing the decision bound- aries of Convolutional Neural Networks (CNNs) or Multilayer Perceptron (MIP). summary, they mainly focus on analyzing model robustness (Yang et al., 2020), the dynamic of margin during training (Mickisch et al., 2020), and model generalizability (Guan & Loew 2020). One common ap- proach is generating baandbounssries instances and analyzing those instances to gain insights about the characteristies of decision boundaries (Berk et al. 2022). Inspired by this idea, we also aim to generate boundary graphs with the purpose of understanding the decision boundaries of GNNs. Given those boundary graphs, we have demonstrated in the case studies that the robustness and generalizability of GNNs could be adequately assessed.
3 BACKGROUND
Notations. A graph is denoted by G (V,E), where V fui, U2...UN) } is the node set and C V V is the edge set. M and N represent the number of edges and nodes, respectively. The node adjacency information is encoded by adjaceney matrix A (0, (0,1jxxx /N where di when there exists an edge connecting node o2 and node új. and aij = otherwise. Besides, the node attributes are represented by the node feature matrix E TR N xd For a graph neural network with L layers, Φi denotes the embedding function composed of the first / layers of the network which takes as input a graph G, while yp denotes the scoring function that corresponds to the last L- layers of the network f before softmax.
Graph Neural Networks. The general idea of GNNs is the wessage--assingg schema, which can be decomposed into three operations: computing messages, aggregating messages, and updating the hidden node representations (Wang et al.) (021). For each GNN layer 1, these three opera-
tions will be performed sequentially to produce the hidden node representations ( (x)
where H Nx Specifically, at the computing messages step, the messages m (I)
Compute(h)) (h"""(()) "1-"",n.-') (1 are computed based on the hidden node representation of node ey and By at the previous layer. Then, the messages propagated from the neighboring nodes are aggregated with a function m Aggregate((m1] |u; E NN; Lastly, the output hidden representation at
the current layer is updated via h( = Update(m!"" ()) h ()) based on the aggregated message and the hidden representation of itself at the previous layer.
Decision Region and Decision Boundary. Given a graph classifier f with L layers, it parti-
tions the input graph space and each embedding space into C' decision regions {R! (0) E [L, O]} for each layer I, where we denote R. R!!)) as the decision region for the input space. For each graph G E Re. the graph classifier f predicts G as class c, where = (Gg Besides. the decision boundary between class e and class C2 is defined as Be, og {G
fo, (G) fez (G) > (G), Vc' # cı, 22 when the graph classifier believes that the graph G has an equal probability of belonging to class e₁ and c2. For the embedding spaces, we define B(!)
cillez (H(),, (m (H))) ( (Ho))), ((n((H))) Vc # C2)
4 GNNBOUNDARY
We propose a model-level explainability method, GNNBoundary, to explain the high-level decision- making process of GNNs from the perspective of decision boundaries. We first develop an algorithm to identify the pairs of classes that have adjacent decision regions. Then, we design novel objective
3

---

Published as a conference paper at ICLR 2024
function that can effectively generate faithful near-boundary graphs for adjacent class pairs via the Gumbel-SSfftax trick (Jang et al. 2016). Besides, to facilitate the optimization, a dynamic regular- ization scheduler is introduced to reduce the likelihood of being trapped in the local minima. Thus, the generated near-boundary graphs can be used to analyze the robustness and generalizability of GNNs. A high-level overview of GNNBaun is shown in Figure
4.1 IDENTIFYING ADJACENT CLASSES
In order to find a boundary graph Ge Gelllea E Beg is important to know how likely Ge llez actually exists. However, this information can not be directly obtained from the input graph space. Instead, can be estimated from the embedding space of f. because Geyllez exists only if boundary embeddings (()) eyllcz E ((()
E: llea exist in the embedding space. We can determine the likelihood that Ger lee exists
by measuring how ubiquitously H
calle2 exists in between Rey and R We define the ubiquity of eillez as the probability that (1) exists in between pair of embeddings H = (G,G,, E R!!)
((
eillez
and H = (G,),)) R2g For simplicity, we choose to use the embedding space of the last hidden layer output, where the decision boundaries are linear. Thus, we define the degree of adjacency of
two classes e₁ and as the ubiquity of H cillez and e₁ and C2 is said to be adjacent if their degree of adjacency is greater than certain threshold.
To find the class pairs e₁ and c2. where boundary graph Gealle= is more likely to exist, we develop an algorithm (shown in Algorithm [ to measure the degree of adjacency between pair of classes. Following the definitions above, we apply Monte Carlo to randomly sample pairs of graphs
Ge, E Re, and G. E Res then determine if (I-1) E B( can be found by interpolating between H(4-1) and H!L-1) Due the linearity of the decision boundary, this be done by checking if we need to pass through any other decision region R&--1) when walking from H!! (Z--1) H!! in a straight line. As a result, the degree of adjacency between e₁ and 0o can be derived by computing the ratio of H (1-1)
oillez found in K sampled pairs. By choosing a proper threshold, the adjacent class pairs can be identified from the adjacency degree matrix for each pair of classes.
Algorithm 1: Measure the Degree of Adjacency of a Class Pair
count
< 0
for k + 1...K do Randomly sample two graphs G1, E Rey and G2, Rey
Compute score
II xE(O.1]
1 (cr,es) (arg max m/- (1 + (1 -
e
score * 0 then
count count + 1
return
4.2 LEARNING OBJECTIVE OF BOUNDARY GRAPHS GENERATION
To effectively generate boundary graphs, the learning objective needs to be properly defined to balance the trade-off between the two boundary classes. For the sake of effective and efficient opti- mization, propose two desired properties of the objective function for the purpose of boundary graph generation. Suppose ej and Co is an adjacent class pair of our interest. (1) For b E (cI, )2). the objective function should encourage p(b) if p(b) < 0.5 and discourage p(b) otherwise. For b & {c1, ).). the objective function should always discourage posterior probability p(b'). (2) The objective function should always encourage logit values f()), for b {ci, and discourage f(G), for b' & (2). As suggested by Berk et al. (2022). the cross-entropy loss below seems to naturally fit our purpose and also satisfy the desired property (1),
min ( = min
(Ptarget) la log a (f())
G
cE[L.C]
4

---

Published as a conference paper at ICLR 2024
where a denotes the softmax function and Ptarget is C-dimensional vector whose c1-th and cy-th element are both 0.5, and all other elements are O. However, we can show that minimizing the cross- entropy loss above is not efficient enough for the specific purpose of generating boundary graphs, as it does not satisfy the desired property (2). We have proved the following proposition in Apppeddix A Proposition 4.1. Minimizing the cross-entropy loss is equivalent to minimizing the function below,
min Σ f(G)v .u-pp (b')
E f(G)), (0.5 -0pppppp (0.5-pp(b))) (b)).
(2)
(Eler.c))
bE(C1,02)
where p" (c) is the detached version (no gradient) of the posterior probability p(c) = off(G))
Corollary 4.1. In certain cases, even b belongs one of the boundary classes, namely b 02), minimizing the cross-entropy loss would still discourage the logit value f(G)).
From Corollary 4.1, it shows a clear limitation of cross-entropy loss that the logit value for either ci or 02 can be minimized in some scenarios, which somehow contradicts our purpose of generating a boundary graph that is as similar as possible to both с₁ and 02 in terms of the discriminative graph patterns. Therefore, we propose a novel objective function that encourages p(c) p(c) = 0.3 while ensuring f(G)), and f(G)e,
never minimized throughout training. The proposed objective function of generating boundary graphs, which satisfies the two desired properties, is written as
min (G)) min Σ 3f(G)) -p 20))
Σ af(G)) (1 (1- (1-p(())) (b))² (p000 (3)
Vgla..))
where a and are constant hyper-parameters. In addition to satisfying the two aforementioned desired properties, comparing to Equation 2 the additional square on the logit weight terms, (1
(b))² and (b)),, further promote or penalize logit values that deviate significantly from the target class probability vector Ptarget- Based on our empirical observations in [Appendix Cl this adaptive loss function effectively generates near-boundary graphs with faster convergence and a reduced likelihood of being trapped in local minima.
4.3 LEARNING BOUNDARY GRAPII DISTRIBUTION
Due to the discrete nature of the graph data, the objective function in Equation 3jaannot be directly optimized via gradient-based methods, because V C(G) does not exist. To resolve this issue, we continuously relax the graph G and optimize the objective function via reparameterization trick (ang et al. (016), inspired by Waang & Shen (2023) and et al.] (2020). Adopting the reparame- terization trick with continuous relaxation of graphs has the advantage that it can make our approach applicable to generating boundary graphs with discrete node features and discrete edge features effi- ciently and effectively. Here, we only present the mathematical formulation for generating boundary graphs with discrete node features but without edge features for simplicity.
Assuming the boundary graph is Gilbert random graph (iilbert 1959) and the node features independently distributed, we formulate the boundary graph distribution as follows,
P(G) II P(z) VVV
II P(ay)
(4)
(BS,0))EE
where aij 1 if node i and fy are connected and aij = O otherwise, and 2; denotes a cate- gorical node feature of node eq. A straightforward instantiation of P(a.) and P(z)) are d.j Bernoulli (O.g) and 2; ~ Categorical(p.) with ||P:11 = 1. To make the graph G = (A, 2) differen- tiable with respect to our objective function, we continuously relax a, to be ā.j E [0, 1] and z to be z, E [0, 1] || = 1. Since the Concrete distribution (Maddison et al. 2016) is continuous ver- Ta) to control the approxima-
sion of Categorical distribution with closed-form density, we have d.j ~
and 2; Concrete( Çi, Tz), where Ta and T= are the tion of Categorical distribution, wij E Ω and Ç; E Z. To make the sampling procedure of ā.j and 2, differentiable, the Gumbel-Softmar trick (Jang al. (016) is adopted to sample âæ and a; as: ā.j = sigmoid ((wij + log - log(1 - e)) /Ta) and z, Softmax ( (C:: log(-log e)) /T=), where e Uniform(0.1). Thanks to this trick, we can sample āij and 2, an approximation of ag and 2; in a differentiable sampling procedure. Thus, the distribution of boundary graphs can be learned by minimizing the following objective function via Monte Carlo and gradient descent,
min L(G) = min Eo~P(a) Z)] ze min E, ( 2)] z min A.Z
1
Σ C(A, Z).
(5)
0,P
0,
f2 K
5

---

Published as a conference paper at ICLR 2024
4.4 TRAINING GNNBOUNDARY
Near-Bowe yrar-Boundary Criterion. The training procedure should terminate when it successfully generates a boundary graph. However, it is practically possible generate boundary graph Geillez Beglle with or (f(G)) = a (f(()) 0.5 exactly. Thus, relaxed criterion is needed to determine whether a graph G approximately belongs to Be, c2 We define the near-boundary criterion as,
(G)) 1
(G))
6
Regularization. In addition to the proposed objective function in Equation 3 we apply multiple regularization terms to facilitate the training process and impose desired constrants on the generated boundary graphs. Following GNNInterpreter (Wang & Shen 2023), our regularization terms include L, and 122 regularizations Rr., for E (1,2) 2) that mitigates saturating gradient problem, as well as the budget penalty Rbudget that encourages the succinet boundary graph be generated.
Roudget Softplus (Isiggooid(())) - B)),
where B is the anticipated maximum number of edges in the boundary graph G.
Dynamic Regularization Scheduler. Due to the unique characteristics of the graph data opti- mization problem, where budget penalty is employed to regulate the graph size, this additional constraint may potentially hinder convergence. To mitigate this side effect, we propose a dynamic scheduling method within the training procedure that adaptively adjusts the budget penalty weight. Intuitively speaking, we impose smaller budget penalty weight when the input graph does not meet the near-boundary criterion and progressively increase the weight as it approaches the target. Formally, the budget penalty weight budget for iteration is recursively defined as,
(()
(1) W budget =
(t-1) 1[0(G0)) 1(-V(G(0))(tan (A (t-1) budget))
budget Sine
-deec
where G Ea-P(a) for iteration t, and budget+ Sinc, and Sdec are hyper-parameters for initial weight, weight increment, and weight decrement, respectively. Compared with constant scheduling budget penalty, dynamic scheduling prevents the budget penalty from interfering with the main loss function during the early stage of the optimization and thus facilitates the convergence of optimization. The overall training procedure for GNNBoundary is presented in Algorithm
Algorithm 2: Training GNNBoundary with Dynamic Regularization Scheduler
Initialize sampler parameters Q2 and Z for each iteration do Sample a batch of k graphs [G1...Gk from sampler with parameters Q and Z budget" Rbuuggr (S2) + wr Rr, (S2, Z)
loss + * Σ. ((Gx) + (t)
Minimize loss with respect to Ω and Z
(E = 1 and the size of B[G] B then return 52 and Z
EVALUATION AND CASE STUDY
To thoroughly assess the efficacy and effectiveness of GNNBoundary, we conduct experimental studies on both synthetic and real-world datasets. First, a detailed description of the datasets will be presented in Section 5.1 For these datasets, the adjacent class pairs and the faithfulness of generated boundary graphs will be evaluated and discussed in Section 5.2. Lastly, we will perform three case studies Section 5.3 to showcase how the generated boundary graphs can assist in analyzing the decision boundaries. The additional experimental details can be found in Appendix B
5.1 DATASETS AND GRAPH CLASSIFIERS
We evaluated GNNBoundary on one synthetic dataset and two real-world datasets. Motif a syn- thetically generated dataset following the same generation procedure GNNInterpreter (Wang &

---

Published as a conference paper at ICLR 2024
It contains four classes: House, House-X, X, Complete-4, and Complete-5, each of which corresponds to a motif that would appear in the graphs. A graph classifier has been trained on its training set with 10.378 graphs and obtained test accuracy of 0.99 on 1,153 test graphs. Collab Yaanaddag & Vishwanathan 2015) is a real-world dataset related to the scientific Collaboration net- work in multiple different helds. The classes in this dataset represent ego networks of researchers in three scientific fields in physics: High Energy (HE), Condensed Matter (CM), and Astro. Collab contains 4,500 training graphs and 500 test graphs, and the trained graph classifier achieves a test accuracy of 0.74. Enzymes (Borgwardt et al. 2005) is real-world molecule dataset with 6 classes and 3 types of nodes. Each class corresponds one type of enzyme. The graph classifier to be explained is trained on 540 graphs and tested on 60 graphs with a test accuracy of 0.52.
Shen 2023).
5.2 EVALUATION RESULTS
On these three datasets, we carefully analyzed the degree of adjacency between every pair of classes and quantitatively evaluated the near-boundary graphs generated by GNNBoundary. Unfortunately, since there is no existing work on understanding the decision boundaries of GNNs, we have no existing approach to compare with. However, to better assess the effectiveness of GNNBoundary, we created baseline method that generates boundary graphs by connecting a randomly sampled pair of graphs, G1 E RRy G2 E Rey. with random edge. It follows general idea that the boundary graphs should contain the discriminative features of both C1 and c2. Due to the page limit, the quantitative comparison with another baseline approach using cross-entropy loss and the qualitative comparison with GNNInterpreter are presented in Appendix Cland Appendix D respectively.
Adjacency between Classes. First, it is essential to identify pairs of classes with adjacent decision It is worth noting that the sampled graph pairs, G1.6 E Re, and G2.2 E
regions via Algorithm [ Reg could be either the true graphs from the training data the synthetically generated graphs. In this experimental study, we choose to use the synthetic graphs generated by GNNInterpreter because do not want to make assumptions about having full access to the training data of the GNNs being explained. With the threshold value of 0.8, we identified 3, 2. and 6 adjacent class pairs, for the Motif, Collab, and Enzymes datasets, respectively (see Figure 2). For the Motif dataset, it is interesting to see that three non-adjacent pairs indeed are easier to differentiate compared with 3 adjacent pairs, based on the true motif presented in |Figure 4) For example, regarding Complete-5 vs. House, Complete-5 has much more edge connectivity than House.
10
Hig
1.00
0:90
1:00
11oss
1.00
1.50
0.00
0.
0:2
0.07
1.00
0.52
0.08
0.6
6.70
0.82
88
35
603
9.92
Makk
0.00
1.50
0.29
244
-04
0104
0:00
0:51
04
1.00
02
0.00
0.00
1.00
02
805
1:00
0.61
0.70
0.01
1.00
0.80
02
High
Condersed
Apro
48
House Haxee Compl4 Camp-5
0.0
(a) Collab
(b) Motif
(c) Enzymes
The degree of adjacency between every pair of classes. It is computed with 10,000 ran- domly sampled pairs of graphs generated by GNNInterpreter.
Figure 2:
Generated Boundary Graphs. To demonstrate the effectiveness of GNNBoundary on generating faithful boundary graphs, we generated 500 near-boundary graphs for each adjacent class pair, given the nou--bondary criterion Puin = 0.45 and Pmax 0.55. Based on Table it evident that the average predicted class probability of those generated boundary graphs are all centered around 0.5 with a very small standard deviation, for all GNNs trained on three datasets. This result demonstrates that we can consistently generate boundary graphs that are extremely close to the decision bound- ary of interest. However, the boundary graphs generated by the random baseline approach obtain an average prediction probability far away from 0.5 for all three datasets, even though each gener- ated graph combines a pair of training graphs from both e₁ and c2. It is clear that GNNBoundary significantly outperforms the baseline approach on all three datasets.
7

---

Published as a conference paper at ICLR 2024
Table 1: The quantitative evaluation of boundary graphs generated by both GNNBoundary and the baseline approach. The average predicted class probability of 500 generated boundary graphs along with the corresponding standard deviation presented below. Besides, the complexity (Equation ITp is computed with the boundary graphs generated by GNNBoundary, ranging from 0 to
GNNBoundary
Baseline
Datasel
22
Complexity
p(c)
p(c))
p(c,)
p(ay)
House HouseX
6.55e-8
0.501 = 0.028
0.499 + 0.028 0,041 = 0.136
0.949 = 0.145
Motif
House Comp4
6.55e-8
0.498 + 0.028
0.501
0.028
0.279 1.379+0..20 0.278
0.717
0.717+0.250 0.285
HouseX Comps
2.57e-7
0.491 1 0.026
0.509
0.026
0.007
0.049
0.993
0.049
HE
CM
0.0463
0.473
0.325
0.333
Collab
HR
Astro
0.0246
0.526 + 0.013
0.466
0.013
0.364
+.4644004422
0.631
0.465
EC1
EC4
0.0754
0.489
- 0.023
0.487
0.021
0.249
0.219 0.365
ECI
EC5
0.1413
0.492
= 0.023
0,489
0.025 0.242
0.365
0.360
0,430
EC1
EC6
0,1492
0.485
1 0.028
0.472
1 0.017
0.225
0.351
0.358
Enzymes
EC2
EC3
0.2325
0.488 0.025
0,488
- 0.025
0.1
0.290
0.239
0,363
BC4
EC5
0.1363
0,480
1 0.024
0.486
1 0.024
268
0.381
0.351 0.419
BC5
EC6
0.2120
0.481
+ 0.022
0.486
+ 0.023
0.391
+ 0.432
0.269
- 0.368
5.3
CASE STUDY
In these case studies, we utilized the generated boundary graphs, which served as an approximation to the decision boundary learned by GNNs, to measure the boundary thickness, boundary margin, and boundary complexity. Each of them provides unique insights into the decision boundaries the explained GNNs from different perspectives. In these case studies, G. E R. are all generated by GNNntterrreter rather than obtained from the training data. This decision is driven by two primary reasons: (i) we aim to avoid making assumptions about the accessibility of training data, and (ii) we hope to gain insights into the decision boundaries that extend beyond in-distribution data.
Boundary Margin. A classifier with a large margin can have better generalization properties and robustness to input perturbation (Elsayed et al. 2018). Formally, following Yang et al. (2020), the asymmetric margin of boundaries can be defined as,
Φff c1, 02) = min Getle))) (G.)) (G
(9)
where (Gey: Gelllea) could be any pair that Go, E Re, and Ge,lle, E B Ica. and Φi is the graph em- bedding function of graph classifier f. As pointed out by Elsayed et al. (218)), the margin of deep networks can be defined based on any intermediate representation of the classifier and the ultimate decision boundary. In this paper, for the choice of di, we calculate the boundary margin based on the output embedding from the graph pooling layer, in line with the standard practices for interpret- ing deep neural networks (Bajaj et al., 20.1). Given the graphs generated by GNNBoundary, the asymmetric boundary margin for each adjacent pair is presented in Figuure 3 which demonstrates the inherent relationship between margin and robustness to perturbation. For the GNN trained on Mo- tif, the margin from RHowsex to HHouse||Housex is 1.64 smaller than the margin to |House||[ooppi which would potentially result in higher risk of misclassifying House into Comp4 compared with XouseX. This is further verified by the confusion matrix in Figure 3 For the GNN trained on Col- lab, the margin from RHE to BHEi is smaller than the margin to BEE|CC.. which also expose a higher potential risk of misclassifying HE into Astro compared with CM (consistent with the con- fusion matrix). Similar observation can be obtained for the GNN on Enzymes, by comparing the margin from RECI to BECIJECS and that from RECI to BECIJEC4. Therefore, since the risk of misclassification is inherently related to the robustness of boundaries to perturbation, our case study shows that larger margin may suggest greater robustness to perturbation over graphs.
Boundary Thickness. It has been shown that thick decision boundaries enhance the model robust- ness, whereas thin decision boundaries would result in overfitting and reduced robustness (Yang et al. 2020). Following Yang et al. 2020), the asymmetric boundary thickness is defined as follows,
((f,,,0,,0)) = EiG,, Gegley) [kb](G..) du (Ga 1/¹ (220((((()))) (oon (hhee)))) dt (10)
where h(t) (1 - t)- di (lG + oi (Ge (lo)) for [0. 1], di is the graph embedding function of graph classifier f. G., E Rey, and Goilles E Bey Similar to Yang et al. (2020), we let y 0.75 when computing the asymmetric boundary thickness in Figure 3 From analyzing the boundary
8

---

Published as a conference paper at ICLR 2024
thickness matrix of GNNs trained on three datasets, we can identify their corresponding thickest and thinnest decision boundaries. For example, for the GNN trained on Collab, the thickest boundary is from RuE to CiEIjI with thickness of 11.52. This indicates that GHE might have greater adversarial robustness and out-of-distribution robustness with respect to Condensed Matter.
Boundary Complexity. The complexity of decision boundaries measures their generalization abil- ity, which is crucial in determining how effectively the GNNs will perform on unseen graphs. Similar to Guan & Loew (2020), the complexity measure ranging from 0 to I can be computed by
T(J,,, (2) = H(2/I/AI)) log D = (- (-Σ ((A/IAA)))) (og/lll))oo@AA///A1/11) log(A+/1/11))) / log D
(11)
where À denotes the eigenvalues of the covariance matrix of X llea and XeIllca E ( X is formed by the é (lag)) A G llez E Bell The embedding of the last hidden layer ΦL-1 is chosen because this measurement of complexity is only applicable to linearly separable boundaries. For each adjacent pair, the complexity measure is presented in Table 1 It is interesting to observe that the boundaries of the GNN trained on Enzymes exhibit the highest complexity among all the explained GNNs, while the boundaries of the GNN for Motif are the simplest. In general, the real- world datasets are anticipated to be more challenging and the tasks involving more classes can even make the decision-making rules more complex. Therefore, the observation that the GNN trained on Enzymes possesses the most intricate boundaries closely aligns with our expectations.
Boundary Thickness
Boundary Margin
Confusion Matrix
Honee
1.64
5.11
Hause
6:7
Heabe
23
100
2000
20
QL94
0607
23
Motif
1.
Comp-
Comp-
Gomp-
Houre Herrekk Compul Comp-5
Can Delilie Hodee
Hoor Houpeo Compul Comp-5
Pleciched
High
Thangg
2015
Collab
Dettor
100
NRT
2710
Jehr
133
13
1290
Soider Bounder
Avto
Lavigy
Praciaee
23
Enzymes
60A
2
BGI Decidio Soundary
Dectiion Doansbry
Prediced
Figure 3: Three metrics for analyzing the decision boundaries of GNNs trained on three datasets.
CONCLUSION
In this paper, we take the first step toward explaining the GNNs through the lens of decision bound- aries. We propose a model-level explainability method, GNNBoundary, which attempts to under- stand the decision boundaries of GNNs by generating and analyzing boundary graphs. Specifically, we first develop an algorithm to identify the pairs of classes that have adjacent decision regions. Given the adjacent class pairs, we generate faithful near-boundary graphs by optimizing novel objective function tailored to satisfy the two desired properties we propose for boundary graph gen- eration. The experimental results on both real-world and synthetic datasets have shown that we could consistently generate faithful hear-boundary graphs. More importantly, our case studies illus- trate that the boundary graphs generated by GNNBoundary can be utilized to measure the boundary thickness, boundary margin, and complexity of the boundary. In essence, through the analysis of boundary graphs generated by GNNBoundary, we can obtaín profound insights into the robustness to perturbation, pave the way for establishing unwavering trust in decisions made by GNNs and encouraging in- creasing deployment of GNNs in real-world applications.
robustness, and generalizability of GNNs. These insights would
9

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENT
The work was supported in part by the US Department of Energy SciDAC program DE-SC0021360, National Science Foundation Division of Information and Intelligent Systems II5-1955764, and National Science Foundation Office of Advanced Cyberinfrastrrcture OAC-2112606.
REFERENCES
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini. Global explain- ability of GNNs via logic combination learned concepts. In International Conference on Learn ing Representations, pp. 1-19, 2023.
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. Advances in Neural Infor- mation Processing Systems, 14:5644-56555 2021.
Jane Berk, Martin Jaszewski, Charles-Alban Deledalle, and Shibin Parameswaran. U-deepdig: Scal- able deep decision boundary instance generation. In IEEE International Conference on Image Processing, pp. 2961-2965, 2022.
Karsten M Borgwardt, Cheng Soon Ong. Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21:i47-i56, 2005.
Jialin Chen, Kenza Amara, Junchi Yu, and Rex Ying. Generative explanations for graph neural network: Methods and evaluations. arXiv:2311.05766 2023a.
Jialin Chen, Shirley Wu, Abhijit Gupta, and Zhitao Ying. D4explainer: In-distribution explanations of graph neural network via discrete denoising diffusion. In Conference on Neural Information Processing Systems, 2023b.
Alexandre Duval and Fragkiskos Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In European Conference Machine Learning and Knowledge Discovery in Databases, 2021.
Gamaleldin Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. Advances in neural information processing systems, 31, 2018.
E. N. Gilbert. Random graphs. The Annals of Mathematical Statistics, 30(4):1141-1144 1959. ISSN 00034851.
Shuyue Guan and Murray Loew. Analysis of generalizability of deep neural networks based on the complexity decision boundary. In IEEE International Conference on Machine Learning and Applications, pp. 101-106, 2020.
Eric Jang, Shixiang Gu and Ben Poole. Categorical reparameterizztion with gumbel-softmax. arXiv:1611.01144, 2016.
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. A survey explainability graph neural networks. arXiv:2306.01955. 2023.
Wanyu Lin, Hao Lan, Hao Wang, and Baochun Li. Orphicx: A causality-inspired latent variable model for interpreting graph neural networks. Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pp. 13729-13738, 2022.
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 Pro- cessing Systems, 33, 2020.
Christopher Maddison, Andriy Mnih, and Yee Tch. The concrete distribution: A continuous relax- ation of discrete random variables. 11 2016.
10

---

Published as a conference paper at ICLR 2024
David Mickisch, Felix Assion, Florens Greßner, Wiebke Günther, and Mariele Motta. Understand- ing the decision boundary of deep neural networks: An empirical study. arXi::2002.01810, 2020.
Alexander Partin, Thomas Brettin, Yitan Zhu, Oleksandr Narykov, Austin Clyde, Jamie Overbeek, and Rick L Stevens. Deep learning methods for drug response prediction in cancer: predominant and emerging trends. Frontiers in Medicine, 10:1086097, 2023.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10772-10781, 2019.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schütt, Klaus-Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(11):7511-7596 2021.
Xiaoqi Wang and Han Wei Shen. GNNInterpreter: A probabilistic generative model-level explana- tion for graph neural networks. In International Conference on Learning Representations, 2023.
Xiaoqi Wang, Kevin Yen, Yifan Hu, and Han-Wei Shen. Deepgd: A deep learning framework for graph drawing using gnn. IEEE Computer Graphics and Applications, 41(5):32-44 2021.
Bingzhe Wu, Jintang Li, Junchi Yu, Yatao Bian, Hengtong Zhang, CHaochao Chen, Chengbin Hou, Guoji Fu, Liang Chen, Tingyang Xu, et al. A survey of trustworthy graph learning: Reliability, explainability, and privacy protection. arXiv:2205. 10014, 2022.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374, 2015.
Yaoqing Yang, Rajiv Khanna, Yaodong Yu, Amir Gholami, Kurt Keutzer, Joseph E Gonzalez, Kan- nan Ramchandran, and Michael Mahoney, Boundary thickness and robustness learning models. Advances in Neural Information Processing Systems, 33:6223 6234, 2020.
Rex Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Gen- erating explanations for graph neural networks. Advances in Neural Information Processing Sys- tems, 32:9240-9251, 12 2019.
Hao Yuan, Jilling Tang, Xia Hu, and Shuiwang XGNN: Towards model-level explanations of graph neural networks. pp. 430 438, 08 2020. doi: 10. 141143339944400.000000..

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
Proof of Proposition 4.1
12
B Experimental Details
13
Comparison with Cross-Entropy Loss
13
Qualitative Comparison with GNNInterpreter
A PROOF OF PROPOSITION
Proof. Let (L- be the logits predicted by f. The cross-entropy loss function defined as
=
Σ cE|1.C1
Ptarget ) log (x))
(12)
Then, we have
==
Σ
(Ptarget)e log.llloooooee (x)
(13)
cE[1,C]
e=c
Σ (Ptarget)c log Σn c
(14)
CE[1,C]
Σ
(Ptargetle : (xc - logsumexp(xx))
(15)
cE[1,C]
logsumexp(x))
Ptarget X
(16)
(17)
Take the gradient of the function L with respect to x
VxC
logsumexp(x)
Ptarget
(18)
Ox
Softmax(x)
Psarget
(19)
In the specific case of finding boundary graphs for ej and c2, we have
[o(x). 0.5, CE (2) ac
(20)
Or.
(x(x).. c$ 02)
Next, let's compute the partial derivatives of Equation
V 0x
Σ
f(G), (0.5-)((b)) +
Σ
f(G), (²((b)
(21)
bE(c)
Σ To (p 0.5) + Σ
Ty p²))"(()
(22)
Fx
be (E(())2))
(23)
12

---

Published as a conference paper at ICLR 2024
Then get
0L
[p'(c)- 0.5,
CE 02)
(24)
dx.
(p)(c),
c 02)
[o(x) 0.5,
CE 02
(25)
(x(x)
c# (2)
Oc OC
Vc
(26)
Oz.
Oz.
Therefore, with gradient back-propagation, minimizing cross-entropy loss defined by Equation is the same as minimizing Equation 2
B EXPERIMENTAL DETAILS
The experiments were conducted on an Apple M1 Max processor. In terms of software configu- ration, the models developed using Python 3.10. For auto-differentiation and numerical op- timization tasks, PyTorch 2.0 was utilized. The Graph Convolutional Network (GCN) architecture was selected for both the Collab and Motif datasets and was constructed using the PyTorch Gcomet- library.
ric 2.2 framework. Vector gather-scatter operations were managed using the Py Additionally, the generation and manipulation of graph data were facilitated through the NetworkX library. Regarding hyperparameter configurations, we set the temperature of the Concrete Distribu- tion T to 0. The sample size for every Monte Carlo sampling is set at 32. For the optimization procedure, we employed the Stochastic Gradient Descent (SGD) optimizer with learning rate of 1. Pertaining to the regularization weights for RL, and R both are consistently set to across all experimental runs.
C COMPARISON WITH CROSS-ENTROPY ENTROPY Loss
Table The quantitative comparison terms of convergence speed between the proposed adaptive boundary loss and the cross-entropy loss. The success rate measures how many times the near- boundary graphs can be successfully generated within 500 iterations of optimization over 1000 runs. The average convergence iteration the expected number of iterations required for convergence over all the successful runs out of 1000. The numbers in bold indicate the superior performance.
Success Rate
Average Convergence Iteration
Dataset
C1
C2
Cross-entropy Baseline
Cross-entropy Baseline
GNNBoumdary
GNNBoundary
House
HouseX
0.86
0.80
136.25
180.30
Motif
House
Comp4
1.00
1,00
20.44
24.69
HouseX
Comp5
0.76
0.55
178.95
158.76
HB
CM
1.00
0.95
46.62
50.80
Collab
HE
Astro
1.00
0.98
15.70
17.07
ECI
EC4
0.63
0.47
177.79
224.60
EC1
EC5
0.96
0.87
88.39
87.12
BCI
EC6
0.75
0.25
138.75
180.00
Enzymes
FC2
EC3
0.74
0.66
136.43
172.39
BC4
EC5
0.57
0.43
167.71
251.79
EC5
EC6
1.00
0.98
80.40
115.82
Even though there no existing method for understanding the decision boundaries of GNNs, we still manage compare performance with some proper baseline approaches. In addition to the random baseline approach mentioned in Section the manuscript, we also evaluate the compara- tive performance of GNNBoundary with the proposed adaptive loss function against GNNBoundary
13

---

Published as a conference paper at ICLR 2024
with the cross-entropy loss. Cross-entropy loss is a commonly used objective function for generat- ing boundary cases of Deep Neural Networks or Convolutional Neural Networks Berk et al. (2022) However, based on Proposition 4.1 and Corollary 4.1 minimizing the cross-entropy loss has limi- tation that the logit value of boundary classes will be discouraged in some scenarios, which hinders the convergence during the optimization. Thus, propose an adaptive loss function (see Equaa] tion 3) to mitigate this issue such that optimizing the proposed adaptive loss fuucciin is less likely to be trapped in local minima without converging. Therefore, in this section, we conducted exper- iments to empirically compare the convergence speed of our loss function and cross-entrope loss function.
To evaluate the comparative performance, we assessed the convergence speed by measuring the success rate and average convergence rate. Namely, the success rate measures how many times the boundary graphs satisfying the near-boundary criterion in [[Equation can be successfully generated within 500 iterations; the average convergence rate is the expected number of iterations required for convergence, if the near-boundary graphs are successfully generated within 500 iterations. We evaluated these two metrics by optimizing both loss functions for 1000 runs. As shown in Table 2 for all adjacent pairs in all three datasets, GNNBoundary obtains significantly higher success rate within 500 iterations. Also, comparing the average convergence iteration, GNNBoundary can converge within substantially smaller number of iterations on average, for almost all adjacent pairs across three datasets. In conclusion, this empirical result has demonstrated that the adaptive boundary loss function we proposed can effectively and consistently generate near-boundary graphs with faster convergence and reduced likelihood of being trapped in local minima.
D QUALITATIVE COMPARISON WITH GNNINTERPRETER
Given the fact that GNNBoundary is model-level explanation method for GNNs, it would be meaningful if we could compare it with the existing model-level explanation methods. The existing model-level explainability method often focuses on extracting discriminative features for each class in the graph classification task. However, different from other model-level explanation methods, GNNBoundary focuses on understanding the decision boundaries of GNNs. Obviously, we have a totally different objective than the existing model-level explanation methods so the quantitative comparison might not make sense here. Therefore, in this section, we aim to qualitatively compare with an existing model-level explanation method called GNNIntrepreter (Wang & Shen 2023). In Figure 4. we present the qualitative examples of boundary graphs generated by GNNBoundary, and the examples of explanation graphs generated by GNNInterpreter.
In general, qualitatively analyzing the explanation graphs for GNNs trained on real-world datasets would be very challenging, because the ground-truth class features for most real-world graph classi- fication datasets are not known. Otherwise, we can directly use some greedy rule-based algorithms to classify the graphs without the need to train GNN model. Therefore, for real-world datasets, hu- mans cannot form a meaningful expectation for the generated explanation graphs since the ground truth features of each class are unknown. For this reason, our qualitative analysis would mainly focus on the synthetic dataset, Motif.
Through the qualitative analysis of the generated boundary graphs, we indeed observed several in- teresting patterns indicating that the boundary graphs share some commonalities with both boundary classes but do not belong any of them. For example, the boundary graph between House-X and Comp-5 has much denser edge connectivity than the boundary graph between House-X and House, even though those two boundary graphs are both predicted as House-X with almost 0.5 probability. For another example, we observed that the boundary graph between House and Comp-4 contains only a single purple node while the boundary graph between House and House-X has 4 purple nodes, which may be caused by the fact that Comp-4 does not have a purple node but both House-X and House has a purple node. However, we also realized that the boundary graphs generated by GNNBoundary might not be fully consistent with the general expectations of humans regarding the boundary graphs to some extent. This actually indicates a potential discrepancy between the bound- ary graphs in the belief of humans and the boundary graphs in the belief of the models. In other words, the boundary graphs presented in Figure 4. in fact, reflect the difference in the decision- making rules between GNNs and humans.
14

---

Published as a conference paper at ICLR 2024
Collab
GNNinteeppretr
Training Examples
Condensed
Energy
Astro
GINBooudaar
Motif
GNNiiteerpretr
Ground-Iruth Modile
Comp--
Hause-X
Comp-4
GNNBoundary
Enzymes
GNNinterpreter
Training Examples
EC1
EC2
EC3
EC4
EGS
EC8
GNNBoundary
Figure 4: The gualitative comparison of explanation graphs between GNNBoundary and GNNIN- terpreter. addition to the explanation graphs, we also present an example of true graph for each class in the Collab and Enzymes dataset, and the ground-truth motif corresponding with each class the Motif dataset.
Speaking of GNNInterpreter, since their explanation graph is generated trigger specific response (the class of interest) from the GNN as much as possible, their explanation graph is supposed to en- capsulate all the discrininative features of the target class. To be specific, the explanation graphs generated by GNNInterpreter will be classified by the GNNs as the target class with probability of the explanation graphs generated by GNNBoundary will be classified by the GNNs as two boundary classes with equal probability. Therefore, we should set completely different expecta- tion for the explanation graphs generated by GNNInterpreter. For House-X, House, and Comp-4 in the Motif dataset, can observe clear discrepancy between the ground-truth motif and the explanation graphs generated by GNNInterpreter. In other words, the GNN trained on Motif will misclassify the explanation graphs generated by the GNNnterpreter since they actually do not tain the ground-truth motifs. This is similar to what we observed the boundary graph generated by GNNBoundary, which indicates potential flaw in the decision -aaiinnnnm-agggggggg rules of GNNs.
15


Reviews:
[{"review_id": "nYN5eXk5zY", "reviewer": "Reviewer_hgmZ", "summary": "In this paper, the authors propose to investigate the explanation problem on graph classification tasks. Specifically, the authors propose to consider an innovative perspective from the decision boundaries of classification GNNs on graph classification. The authors, particularly, aim to generate graphs that exactly lie on the boundary such that practitioners can leverage such generated graphs for explanations to understand the behavior of the trained GNNs. The authors further conduct experiments on both synthetic and real-world datasets to demonstrate the effectiveness of their work.", "questions": "Have the authors considered using more datasets, involving more graphs and classes? We are curious about the performance of the framework on such datasets. Our concern is that experiments on two datasets with 3 and 4 classes, respectively, are not convincing enough.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The authors explore the important problem of explanations on graph classification tasks, which are crucial for a variety of real-world scenarios. \n\n2. Originating from the innovative perspective of decision boundaries of GNNs between any pair of classes, the authors propose to generate graphs that exactly lie on the boundary based on the minimization of cross-entropy loss. \n\n3. The experiments demonstrate the effectiveness of the proposed framework in explaining the classification GNNs.", "weaknesses": "1. Throughout the introduction, the authors do not provide sufficient references to support the claims proposed. For example, the first three sentences in the first paragraph do not involve any references, which will make the statement less reliable. Similar issues also exist in the third and fourth paragraphs.\n\n\n2. The authors do not provide a thorough figure to illustrate the overall procedure of the proposed method. As a result, even though the core idea is straightforward, the process is somewhat unclear to readers.\n\n3. The experiments are only conducted on two datasets, one being synthetic and another being real-world. The most important problem is that two datasets are not enough. Furthermore, these datasets are relatively small, and more importantly, the number of classes is extremely small (3 for Motif and 4 for COLLAB). We know that some graph classification datasets have only a small number of classes, however, as an explanation method, the authors should further explore the possibility of the method on larger datasets with a larger number of classes. This is also because the computation between different pairs of classes will significantly increase when the number of classes is larger.\n\n4. As a novel method, we understand that the authors cannot find enough baselines for comparison. However, it is still possible to create several baselines for comparison. Otherwise, the comparison cannot be considered fair.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aWO3S8EXlL", "reviewer": "Reviewer_9PKK", "summary": "The work studies explainability for GNNs by introducing  the notion of boundaries between predicted classes. The core of the contribution is to propose a method to find the boundaries, both which class appears to be adjacent to which, and to find examples of graphs on thes boundaries. Then the authors study some metrics computed on these boundaries (margin, thickness, complexity) that contribute to model-level explainability for GNNs.", "questions": "- I don't see anything intuitive in the case of Collab graphs. Is this dataset really a good one to illustrate the method ? We don't have ground truth for the elements of explainability in this case, do we ?\n\n- For Motif dataset, we have more intuition. Yet, I don't see why it's normal that they is no boundary between Comp-4 and House-X. There is only 1 added node and I wouldn't have said that the GNN rely that much to the number of nodes. Also, is it possible to understand the shape of the graphs on the found boundaries ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of explainability through the decision boundaries is simple, very elegant and relevant and, as far as I know, novel for GNNs.\n\n- The work is well conducted (one understands well how algorithm 1 and then 2 are built), justified from the existing literature, and globally well written.\n\n- The derivation of the objective function, eq. (5), is nicely done, showing the limitation one would have by using directly the cross-entropy loss.\n\n- The numerical experiments are adequate.", "weaknesses": "- The qualitative interpretation of the results, that are especially elaborated from the study of 2 datasets and Figure 2 that shows what classes there are and what are the boundaries, is difficult to fully agree with.\n\t\n\n- There is no real comparison of the elements of explainability for GNNs obtained by the proposed method to what the existing, yet different, explainability methods provide.\nThe work proposes, in 5.3, only a study of the metrics of the present work in some use case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qtn0jsUcfs", "reviewer": "Reviewer_oN5P", "summary": "In this paper, a novel model-level explanation method of GNNs called GNNBoundary is introduced, aimed at revealing the inner workings of GNNs by analyzing their decision boundaries. Unlike existing model-level methods, GNNBoundary approaches GNN explainability from a fresh perspective by identifying adjacent class pairs and generating graphs that lie on decision boundaries. Through this approach, the paper enables a deeper understanding of the decision-making process of GNNs, assessing their robustness, generalizability, and the potential risk of misclassification on unseen data. The method is evaluated on synthetic and real-world datasets, demonstrating its effectiveness in generating faithful boundary graphs and providing valuable insights into decision boundaries' complexity and model robustness.", "questions": "1. The boundary graph you showed is not so explicit why it's at the boundary. How will it help with GNN explanation? The case study part seems only considering the dataset part not the model part.\n2. For graph-level tasks, one may think about tasks of molecules. They have edge types in the graph and can GNNboundary be applied to molecules? And now the boundary graph seems not similar to each of the class sample. Will it be better in the molecule fields?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper introduces an innovative model-level explanation method, GNNBoundary, which focuses on revealing the decision boundaries of GNNs. This approach offers a fresh perspective on explaining GNNs and has the potential to provide valuable insights into their behavior.\n* The paper includes a comprehensive evaluation of GNNBoundary on both synthetic and real-world datasets. It provides quantitative and qualitative evidence of the method's efficiency and effectiveness in generating faithful boundary graphs and offering insights into GNN behavior.", "weaknesses": "* The paper only gives the boundary graph but not further analysis of how to use the boundary graph to analysis GNNs.\n* The paper doesn't include relational graphs that include the most well-knowned graph tasks, molecule tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2H5LFP296y", "reviewer": "Reviewer_F52p", "summary": "This paper introduces GNNBoundary, a  methodology designed to generate boundary graphs for Graph Neural Networks (GNNs), aiming to provide a deeper understanding of their decision boundaries. The GNNBoundary first identify the adjacent classes and then generate boundary graphs with cross-entropy loss.  The authors conduct extensive experiments and case studies on both synthetic and real-world datasets to validate the effectiveness of GNNBoundary. The generated boundary graphs are utilized to analyze various aspects of decision boundaries, including boundary thickness, margin, and complexity.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses an important and timely topic in the domain of GNNs, focusing on explainability and interpretability, which are crucial for the adoption of GNNs in real-world applications.\n2. The paper is well-structured and easy to follow. \n3. The paper provides a thorough evaluation of GNNBoundary, and the results seem to demonstrate the effectiveness of the approach.", "weaknesses": "1. In Section 3, the decision boundary is characterized by a scenario where a graph $G$ is equally probable to belong to classes $c_1$ and $c_2$. However, achieving this exact equality in probabilities is practically challenging. A more feasible approach might be to define the decision boundary within a specific interval or range of probabilities, ensuring a more robust and attainable characterization.\n\n2. In Section 4.2, the authors state: \"if traversal through decision region $R_{c3}$ is necessary, then $R_{c1}$ and $R_{c2}$ are not adjacent.\" However, the linkage between this statement and Algorithm 1 is not immediately clear. To enhance comprehension, it would be beneficial for the authors to provide a more explicit explanation or illustration of how this concept is integrated into or related to the steps and operations outlined in Algorithm 1. \n\n3. There is no formal math definition of adjacency of decision region. The adjacency of decision region should be defined on the input space i.e., the graph sapce. However, the degree of adjacenct of class pair in algorithm 1 is only a quantitively approximation of the adjacency and obtained on the embedding space. \n\n4. Although the methods use some techniques to generate discrete node feature and edges, the degree of graphs should be varying even in one dataset. How do you determin the degree of boundary graphs which seems can only be pre-determined. \n\n5. The proposed GNNBoundary methods seems not be specific for graph fields. The author should compare it with other methods in more general fields such as  [Berk et al., 2022], discuss its applicability in more general fields. Also the author could concentrate more on graph since the name of method is GNNBoundary. \n\n\n6. There are some other typos such as the subscript of $\\phi$ in Line 4 of algorithm have different meaning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)