Robust Counterfactual Explanations on Graph Neural Networks
Authors: Mohit Bajaj
Lingyang Chu
Zi Yu Xue
Jian Pei
Lanjun Wang
Peter Cho-Ho Lam
Yong Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Counterfactual
explanations
GNN
robust
graph neural networks
interpretation
explainable AI
decision logic

Abstract: Massive deployment of Graph Neural Networks (GNNs) in high-stake applications generates a strong demand for explanations that are robust to noise and align well with human intuition. Most existing methods generate explanations by identifying a subgraph of an input graph that has a strong correlation with the prediction. These explanations are not robust to noise because independently optimizing the correlation for a single input can easily overfit noise. Moreover, they are not counterfactual because removing an identified subgraph from an input graph does not necessarily change the prediction result. In this paper, we propose a novel method to generate robust counterfactual explanations on GNNs by explicitly modelling the common decision logic of GNNs on similar input graphs. Our explanations are naturally robust to noise because they are produced from the common decision boundaries of a GNN that govern the predictions of many similar input graphs. The explanations are also counterfactual because removing the set of edges identified by an explanation from the input graph changes the prediction significantly. Exhaustive experiments on many public datasets demonstrate the superior performance of our method.

Robust Counterfactual Explanations on Graph Neural Networks
Mohit Bajaj** Lingyang Chu
Zi Yu Xue
Jian Pei
Lanjun Wang' Peter Cho-Ho Lam
Yong Zhang'
Huawei Technologies Canada Co., Ltd.
McMMatter University
The University of British Columbia
Simon Fraser University
[mohit. bajaji, zi yu.uuue, lanjun jun wangunn,, cho hoo hamm yong.
com
chul9@mcmaster.c ca, jpei
.ct.cc.ssuu.c. sfu.ca
Abstract
Massive deployment of Graph Neural Networks (GNNs) high-stake applications generates a strong demand for explanations that are robust to noise and align well with human intuition. Most existing methods generate explanations by identifying subgraph of an input graph that has strong correlation with the prediction. These explanations are not robust to noise because independently optimizing the correlation for single input can easily overfit noise. Moreover, they not counterfactual because removing an identified subgraph from an input graph does not necessarily change the prediction result. In this paper, we propose a novel method generate robust counterfactual explanations modelling the common decision logic GNNs on similar input graphs. Our explanations are naturally robust to noise because they are produced from the common decision boundaries of GNN that govern the predictions of many similar input graphs. The explanations are also counterfactual because removing the set of edges identified by an explanation from the input graph changes the prediction significantly. Exhaustive experiments on many public datasets demonstrate the superior performance of our method.
GNNs by explicitly
Introduction
Graph Neural Networks (GNNs) [22, 37, 50] have achieved great practical successes in many real- world applications, such as chemistry [31], molecular biology [17], social networks [3] and epidemic modelling [34]. For most of these applications, explaining predictions made by GNN model is crucial for establishing trust with end-users, identifying the cause of prediction, and even discovering potential deficiencies of a GNN model before massive deployment. Ideally, an explanation should be able to answer questions like "Would the prediction of the GNN model change if certain part of an input molecule is removed?" in the context of predicting whether an artificial molecule is active for a certain type of proteins [19, 41], "Would an item recommended still be recommended if customer had not purchased some other items in the past?" for GNN built for recommendation systems [9, 44].
Counterfactual explanations [28] in the form of "If X had not occurred, would not have oc- curred" [26] are the principled way to answer such questions and thus are highly desirable for GNNs. In the context of GNNs, counterfactual explanation identifies small subset of edges of the input graph instance such that removing those edges significantly changes the prediction made by the GNN. Counterfactual explanations are usually concise and easy to understand [28, 36] because they align well with the human intuition describe a causal situation [26]. To make explanations more trustworthy, the counterfactual explanation should be robust to noise, that is, some slight changes on
"qqual contribution.
35th Conference Neural Information Processing Systems (NeurIPS 2021).

---

an input graph do not change the explanation significantly. This idea aligns well with the notion of robustness discussed for DNN explanations in computer vision domain [11]. According Ghorbani et al. [11] many interpretations on neural networks are fragile as it is easier to generate adversarial perturbations that produce perceptively indistinguishable inputs that are assigned the same predicted label, yet have very different interpretations. Here, the concepts of "fragile" "robustness" describe the same concept from opposite perspectives. An interpretation is said to be fragile if systematic perturbations can lead to dramatically different interpretations without changing the label. Otherwise, the interpretation is said be robust.
How to produce robust counterfactual explanations on predictions made by general graph neural networks is novel problem that has not been systematically studied before. As to be discussed in Section 2, most GNN explanation methods [45, 25, 46, 37, 32] are neither counterfactual nor robust. These methods mostly focus on identifying a subgraph of an input graph that achieves a high correlation with the prediction result. Such explanations are usually not counterfactual because, due to the high non-convexity of GNNs, removing a subgraph that achieves high correlation does not necessarily change the prediction result. Moreover, many existing methods [45, 25, 37, 32] are not robust to noise and may change significantly upon slight modifications on input graphs, because the explanation of every single input graph prediction is independently optimized maximize the correlation with the prediction, thus an explanation can easily overfit the noise in the data.
In this paper?, we develop RCExplainer, novel method produce robust counterfactual explanations on GNNs. The key idea is to first model the common decision logic of a GNN by set of decision regions where each decision region governs the predictions on large number of graphs, and then extract robust counterfactual explanations by a deep neural network that explores the decision logic carried by the linear decision boundaries of the decision regions. We make the following contributions.
First, we model the decision logic of a GNN by a set of decision regions, where each decision region is induced by set of linear decision boundaries of the GNN. We propose an unsupervised method to find decision regions for each class such that each decision region governs the prediction of multiple graph samples predicted to be the same class. The linear decision boundaries of the decision region capture the common decision logic on all the graph instances inside the decision region, thus do not easily overfit the noise of an individual graph instance. By exploring the common decision logic encoded in the linear boundaries, we are able to produce counterfactual explanations that are inherently robust noise.
Second, based on the linear boundaries of the decision region, we propose novel loss function to train a neural network that produces a robust counterfactual explanation as a small subset of edges of an input graph. The loss function is designed to directly optimize the explainability and counterfactual property of the subset of edges, such that: 1) the subgraph induced by the edges lies within the decision region, thus has prediction consistent with the input graph; and 2) deleting the subset of edges from the input graph produces remainder subgraph that lies outside the decision region, thus the prediction on the remainder subgraph changes significantly.
Last, we conduct comprehensive experimental study to compare our method with the state-of-the-art methods fidelity, robustness, accuracy and efficiency. All the results solidly demonstrate the superior performance of our approach.
2 Related work
The existing GNN explanation methods [46, 37, 32, 25] generally fall into two categories: model level explanation [46] and instance level explanation [37, 45, 32, 25).
A model level explanation method [46] produces high-level explanation about the general behaviors of GNN independent from input examples. This may be achieved by synthesizing set of artificial graph instances such that each artificial graph instance maximizes the prediction score on a certain class. The weakness of model level explanation methods is that input graph instance may not contain an artificial graph instance, and removing an artificial graph from an input graph does not necessarily change the prediction. As a result, model level explanations are substantially different from counterfactual explanations, because the synthesized artificial graphs do not provide insights into how the GNN makes its prediction on a specific input graph instance.
The instance level explanation methods [37, 45, 32, 25] explain the prediction(s) made by a GNN on specific input graph instance or multiple instances by identifying a subgraph of an input graph
2 Ottee versions of the paper are available at https://ariivoog//bb//000..

---

instance that achieves a high correlation with the prediction on the input graph. GNNExplainer [45] removes redundant edges from an input graph instance to produce an explanation that maximizes the mutual information between the distribution of subgraphs of the input graph and the GNN's prediction. Following the same idea by Ying et al. [45], PGExplainer [25] parameterizes the genera- tion process of explanations by a deep neural network, and trains it to maximize similar mutual information based loss used by GNNExplainer [45]. The trained deep neural network is then applied to generate explanations for a single input graph instance or a group of input graphs. MEG [30] incorporates strong domain knowledge in chemistry with a reinforcement learning framework to produce counterfactual explanations on GNNs specifically built for compound prediction, but the heavy reliance domain knowledge largely limits its applicability
general GNNs. The recently
proposed CF-GNNExpl [24] independently optimizes the counterfactual property for each explanation but ignores the correlation between the prediction and the explanation.
Some studies [32, 37] also adapt the existing explanation methods of image-oriented deep neural networks to produce instance level explanations for GNNs. Pope al. [32] extend several gradient based methods [33, 35, 49] to explain predictions made by GNNs. The explanations are prone to gradient saturation [12] and may also be misleading [1] due to the heavy reliance
noisy gradients. Velickovic al. [37] extend the attention mechanism [7. 8] to identify the nodes in an input graph that contribute the most to the prediction. This method has to retrain the GNN with the altered architecture and the inserted attention layers. Thus, the explanations may not be faithful to the original GNN.
Instance level explanations from most of the methods are usually not counterfactual because, due to the non-convexity of GNNs, removing an explanation subgraph from the input graph does not necessarily change the prediction result. Moreover, those methods [45, 25, 37, 32, 24] are usually not robust noise because the explanation of every single input graph prediction is independently optimized. Thus, an explanation can easily overfit the noise inside input graphs and may change significantly upon slight modifications input graphs.
To tackle the weaknesses in the existing methods, in this paper, we directly optimize the counterfactual property of an explanation along with the correlation between the explanation and the prediction. Our explanations are also much more robust to modifications on input graphs, because they are produced from the common decision logic on large group of similar input graphs, which do not easily overfit the noise of an individual graph sample.
Please note that our study is substantially different from adversarial attacks on GNNs. The adversarial attacking methods [51, 53, 42, 43, 20] use adversarial examples to change the predictions of GNNs but ignore the explainability of the generated adversarial examples [10]. Thus, the adversarial examples generated by adversarial attacks may not explain the original prediction.
Our method is substantially different from the above works because we focus on explaining the prediction by directly optimizing the counterfactual property of an explanation along with correlation of the explanation with the prediction. We also require that the explanation is generally valid for a large set of similar graph instances by extracting it from the common linear decision boundaries of large decision region.
3 Problem Formulation
Denote by G = {V, E} a graph where V= [11, U2...., Jn is the set o nodes and E CVVVV the set of edges. The edge structure of a graph described by an adjacency matrix E 10,1) where Aij = 1 if there is an edge between node ii and By; and Aij = O otherwise.
Denote by é GNN model that maps graph to probability distribution over a set of classes denoted by C. Let D denote the set of graphs that are used train the GNN model c. We focus on GNNs that adopt piecewise linear activation functions, such as MaxOut [14] and the family of ReL.U [13, 15, 29].
The robust counterfactual explanation problem is defined as follows.
Definition 1 (Robust Counterfactual Explanation Problem) Given a GNN model & trained on
set of graphs D. for an imput graph G = {V. E}, our goal is to explain why G is predicted by the
GNN model as GiG) by identifying a small subset of edges S C F, such that (1) removing the set of
edges in S from G that causes the maximum drop in the confidence of the original prediction; and (2) S is stable and doesn't I change when the edges and the feature representations of the nodes of G are perturbed by random noise.
3

---

In the definition, the first requirement requires that the explanation S is counterfactual, and the second requirement requires that the explanation is robust to noisy changes on the edges and nodes of G.
4 Method
In this section, we first introduce how to extract the common decision logic of a GNN on a large set of graphs with the same predicted class. This is achieved by a decision region induced by a set of linear decision boundaries of the GNN. Then, based on the linear boundaries of the decision region, we propose a novel loss function to train a neural network that produces robust counterfactual explanations. Last, we discuss the time complexity of our method when generating explanations.
4.1 Modelling Decision Regions
Following the routines of many deep neural network explanation methods [33, 48], we extract the decision region of a GNN in the d-dimensional output space Od of the last convolution layer of the GNN. The features generated by the last convolution layer are more conceptually meaningful and more robust to noise than those raw features of input graphs, such as vertices and edges [52, 2]. Denote by Oye the mapping function realized by the graph convolution layers that maps an input graph G to its graph embedding &ge (G) E 04,, and by oe the mapping function realized by the fully connected layers that maps the graph embedding & (G) to predicted distribution over the classes in C. The overall prediction (G)) made by the GNN can be written as (GG) = Φ (e(@ge(())
For the GNNs that adopt piecewise linear activation functions for the hidden neurons, such as MaxOut [14] and the family of ReLU [13, 15, 29], the decision logic of ofc in the space Odd is characterized by a piecewise linear decision boundary formed by connected pieces of decision hyperplanes in Od [1]. We call these hyperplanes linear decision boundaries (LDBs), and denote by H the set of LDBs induced by éfe. The set of LDBs in H partitions the space Od into large number of convex polytopes. A convex polytope is formed by a subset of LDBs in H. All the graphs whose graph embeddings are contained in the same convex polytope are predicted as the same class [4]. Therefore, the LDBs of convex polytope encode the common decision logic of dscc on all the graphs whose graph embeddings lie within the convex polytope [4]. Here, a graph G is covered by a convex polytope if the graph embedding (G) is contained in the convex polytope.
Based on the above insight, polytope that satisfies the following two properties. First, the decision region should be induced by a subset of the LDBs in H. In this way. when we extract counterfactual explanations from the LDBs, the explanations are loyal the real decision logic of the GNN. Second, the decision region should cover many graph instances in the training dataset D, and all the covered graphs should be predicted as the same class. In this way, the LDBs of the decision region capture the common decision logic on all the graphs covered by the decision region. Here, the requirement of covering larger number of graphs ensures that the common decision logic is general, and thus it is less likely to overfit the noise of individual graph instance. As result, the counterfactual explanations extracted from the LDBs of the decision region are insensitive to slight changes in the input graphs. Our method can be easily generalized to incorporate prediction confidence in the coverage measure, such as considering the count of graphs weighted by prediction confidence. To keep our discussion simple, do not pursue this detail further in the paper.
model the decision region for set of graph instances
convex
Next, we illustrate how to extract a decision region satisfying the above two requirements. The key idea is to find a convex polytope covering a large set of graph instances in D that are predicted as the same class c E C.
Denote by D. S. D the set of graphs in D predicted as a class e E C, by P C H a set of LDBs that partition the space Od into set of convex polytopes, and by r(P, c) the convex polytope induced by P that covers the largest number of graphs in D... Denote by g(P, e) the number of graphs in D. covered by r(P,c), c). and by h(P, e) the number of graphs in 1) that are covered by r(P, c) but are not predicted as class c. We extract decision region covering a large set of graph instances in D. by solving the following constrained optimization problem.
max g(P,c), S.t. h(P,c) =0 PCH
(1)
This formulation realizes the two properties of decision regions because P C H ensures that the decision region is induced by subset of LDBs in H. maximizing g(P, c) requires that r(P, c) covers

---

a large number of graphs in De, and the constraint c) 0 ensures that all the graphs covered by ((,cc) are predicted the same class c.
Once we find a solution P the above problem, the decision region r(P, e) can be easily obtained by first counting the number of graphs in D, covered by each convex polytope induced by P, and then select the convex polytope that covers the largest number of graphs in De.
4.2 Extracting Decision Regions
The optimization problem in Equation (1) is intractable for standard GNNs, mainly because it is impractical compute H. all the LDBs of a GNN. The number of LDBs in H of a GNN is exponential with respect to the number of neurons in the worst case [27]. To address this challenge, we substitute H by a sample H of LDBs from H.
LDB in the space 0d can be written as w + = O, where is x Odd a variable, the basis term, and b corresponds to the bias. Following [4], for any input graph G, a linear boundary can be sampled from H by computing
a (max (o)x(())c(a))) maxx(0)((aa))
w
la (e))
da
and
b = max m (0)c(())
maax(()((()) w" (G))
(3)
where max1 (a)) and max (())(()) are the largest and the second largest values in the vector Φsc(a), respectively. Given an imput graph G. Equations (2) and (3) identify one LDB from H. Thus, we can sample a subset of input graphs uniformly from D, and use Equations (2) and (3) to derive a
sample of LDBs as H C H.
Now, we substitute H Equation (1) by H to produce the following problem.
max g(P,c) s.t. c)),c) S 8,
(4)
PCN
where 5 2 is tolerance parameter keep this problem feasible. The parameter 5 is required because substituting 7 by H. ignores the LDBs in H.' H. Thus, the convex polytope r(P, e) induced by subset of boundaries in H may contain instances that are not predicted as class c. We directly set 8 1(H,, c), which the smallest value of that keeps the practical problem feasible.
The problem in Equation (4) can be proven to be a Submodular Cost Submodular Cover (SCSC) problem [18] (see Appendix D for proof) that is well known to be NP-hard [5]. We adopt a greedy boundary selection method to find good solution to this problem [40]. Specifically, we initialize P
as empty set, and then iteratively select new boundary h from H. by
((P, g U (h),c) + AERYP h(P.c) - h(P (h).c)
h arg min
(5)
where ((P,c)-g(( g(P [h).e) c) is the decrease of g(P,c) when adding h into P. and h(P,c) (PU (h),c) c) is the decrease of h(P,c) when adding h into P. Both g(P, e) and c(PP,) are non-increasing when adding h E HH into P because adding a new boundary may only exclude some graphs from the convex polytope r(P,c).
Intuitively, in each iteration, Equation (5) selects a boundary h E H. such that adding h into P reduces c) the least and reduces h(P, c) the most. In this way, smaller than 5 without decreasing g(P, e) too much which produces good feasible solution to the practical problem. We add a small constant to the numerator such that, when there are multiple candidates of h that do not decrease g(P, c). can still select the h that reduces h(P, c) the most.
quickly reduce h(P,e) e) to be
We apply a peeling-off strategy iteratively extract multiple decision regions. For each class e C, we first solve the practical problem once to find a decision region r(P, c), then we remove the graphs covered by r(P,q from D.. If there are remaining graphs predicted as the class c. we continue finding the decision regions using the remaining graphs until all the graphs in D. are removed. When all the graphs in D. are removed for each class c E C, we stop the iteration and return the set of decision regions we found.
5

---

4.3 Producing Explanations
In this section, we introduce how to the LDBs of decision regions train neural network that produces a robust counterfactual explanation as a small subset of edges an input graph. We form explanations as subset of edges because GNNs make decisions by aggregating messages passed on edges. Using edges instead of vertices as explanations can provide better insights on the decision logic of GNNs.
4.3.1 The Neural Network Model
Denote by fo the neural network to generate subset of edges of an input graph G as the robust counterfactual explanation the prediction dGG). 0 represents the set of parameters of the neural network. For experiments, our explanation network f consists of fully connected layers with a ReLU activation and the hidden dimension of 64.
For any two connected vertices 0; and fyy of G, denote by and z, the embeddings produced by the last convolution layer of the GNN for the two vertices, respectively. The neural network So takes z; and 2 as the input and outputs the probability for the edge between v and by to be part of the explanation. This can be written as
Mi fo, 2z);
where My denotes the probability that the edge between ey and vy is contained in the explanation. When there is no edge between and Vy, that is, Aij O, we set M.j = 0.
For input graph G E} with n vertices and trained neural network fe, M is n-by-n matrix that carries the complete information to generate robust counterfactual explanation as a subset of edges, denoted by S S F. Concretely, we obtain S by selecting all the edges in E whose corresponding entries in M are larger than 0.5.
4.3.2 Training Model fo
For an input graph G = (V, F), denote by C F. the subset of edges produced by fo explain the prediction (GG), our goal is to train a good model fa such that the prediction on the subgraph Gs induced by S from G is consistent with o and deleting the edges S from G produces remainder subgraph G GEys such that the prediction on GEYS changes significantly from ((G).
Since producing S' by fe is discrete operation that is hard to incorporate in an end-to-end training process, define two proxy graphs to approximate Gs and GEy. respectively, such that the proxy graphs are determined by 0 through continuous functions that can be smoothly incorporated into an end-to-end training process.
The proxy graph of Gs. denoted by Gg. is defined by regarding M instead of as the adjacency matrix. That is, Gg has exactly the same graph structure as G, but the edge weights of Gg is given by the entries in M instead of A. Here, the subscript 0 means Go determined by 0.
The proxy graph of Grys, denoted by G² also have the same graph structure as G. but the edge weight between each pair of vertices iy and is defined as
Mij
if Aij 1 if Aij = 0
My
The edge weights of both Go and G are determined by 0 through continuous functions, thus we can smoothly incorporate Gg and Gy into an end-to-end training framework.
As discussed later in this section, we use regularization term force the value of each entry in My; to be close to either 0 or 1, such that Go and G better approximate Gs and GEyS respectively.
We formulate our loss function as
((0)
Σ (XCsamel (0, G) + - A) () + RRsparse (8, G) + RiRdiscreete G)}, (8) GED
where À E 1), 8 0 and μ 2 0 are the hyperparameters controlling the importance of each term. The influence of these parameters is discussed in Appendix G. The first term of our loss function requires that the prediction of the GNN on Go is consistent with the prediction on G. Intuitively, this

---

means that the edges with larger weights in Gg dominate the prediction on G. We formulate this term by requiring Go to be covered by the same decision region covering G.
Denote by He the set of LDBs that induce the decision region covering G. and by |'G the number of LDBs in Hg. For the i-th LDB h; He. denote by (x)x) w/ x b, where w, and by are the basis and bias of f4g respectively, and x E O44 is point in the space 04, The sign of (x) indicates whether a point x lies on the positive side or the negative side of h4, and the absolute value (x)] is
proportional to the distance of a point x from h4. Denote by (--) the standard sigmoid function, we formulate the first term of our loss function
samme (0, G)
1 1HG
Σ h.HH
o-BBi(One ((
such that minimizing Leame (0, G) encourages the graph embeddings (G) and (ge(Go) to lie on the same side of every LDB in Ha. Thus, Go is encouraged to be covered by the same decision region covering G.
The second term of our loss function optimizes the counterfactual property of the explanations by requiring the prediction on G to be significantly different from the prediction on G. Intuitively, this means that the set of edges with larger weights in Go good counterfactual explanations because reducing the weights of these edges significantly changes the prediction. Following the above intuition, we formulate the second term as
Lopp (0, G)
min a (B.( * B, (1 (c)))(())))) h,EHG
(10)
such that minimizing Copp (0, G) encourages the graph embeddings Øge (G) and dge(G)) to lie on the opposite sides of at least one LDB in Hg. This further means that Gi is encouraged not to be covered by the decision region covering G, thus the prediction on G can be changed significantly from the prediction on G.
Similar to [45], we use a L1 regularization R Reparse (0, G) = | on the matrix M produced by fe on an input graph G to produce a sparse matrix M, such that only small number of edges in G are selected as the counterfactual explanation. We also follow [45] to an entropy regularization
Raiiserete (0,G) = M
Σ 1
(My (og(M))) + - MM;) log(1 - M,j))
(11)
push the value of each entry in Mij be close to either 0 or 1, such that Go and Go approximate Gs and Gays well, respectively.
Now can the graphs in D and the extracted decision regions to train the neural network fa in an end-to-end manner by minimizing L(0) over 9 using back propagation. Once we finish training fe. we can first apply fe to produce the matrix M for an input graph G = (V, E.,, and then obtain the explanation S by selecting all the edges in F. whose corresponding entries in M are larger than 0.5. We do not need the extracted boundaries for inference as the the decision logic of GNN is already distilled into the explanation network f during the training.
As discussed in Appendix B. method can be easily extended to generate robust counterfactual explanations for node classification tasks.
Our method is highly efficient with time complexity O(EE)) for explaining the prediction on an input graph G. where |E| is the total number of edges in G. Additionally, the neural network fo can be directly used without retraining to predict explanations on unseen graphs. Thus our method is significantly faster than the other methods [45, 32, 47, 38] that require retraining each time when generating explanations on new input graph.
5 Experiments
We conduct series of experiments compare our method with the state-of-the-art methods in- cluding GNNExplainer [45], PGExplainer [25], PGM-Explainer [38], SubgraphX [47] and CF- GNNExplainer [24]. For the methods that identify set of vertices as an explanation, we use the set of vertices to induce subgraph from the input graph, and then use the set of edges of the induced subgraph as the explanation. For the methods that identify subgraph as an explanation, we directly use the set of edges of the identified subgraph the explanation.
7

---

(a) Mutagenicity
[b] 8A-2motils
(c) NC11
0.2
0.8-
0.5
6.4
0.3
0.3-
0.2
0.1
0.1
Sparsity (96)
Sparsiy (96)
Sparsity (%%
ICE HoLDO (Oun)
Figure 1: Fidelity performance averaged across 10 runs for the datasets at different levels of sparsity.
To demonstrate the effectiveness of the decision regions, we derive another baseline method named RCExp-NoLDB that adopts the general framework of RCExplainer but does not use the LDBs of decision regions to generate explanations. Instead, RCExp-NoL.DD directly maximizes the prediction confidence on class e for Go and minimizes the prediction confidence of class e for G²--
We evaluate the explanation performance on two typical tasks: the graph classification task that uses a GNN to predict the class of an input graph, and the node classification task that uses a GNN to predict the class of graph node. For the graph classification task, we
synthetic dataset, BA-2motifs [25], and two real-world datasets, Mutagenicity [21] and NCII [39]. For the node classification task, we use the same four synthetic datasets as used by GNNExplainer [45], namely, BA-SHAPES, BA-COMMUNITY, TREE-CYCLES and TREE-GRID.
Limited by space, we only report here the key results on the graph classification task for fidelity, robustness and efficiency. Please refer to Appendix E for details on datasets, baselines and the experiment setups. Detailed experimental comparison the node classification task will be discussed in Appendix F where we show that our method produces extremely accurate explanations. The code? is publicly available.
5.1 Fidelity
Fidelity is measured by the decrease of prediction confidence after removing the explanation (i.e., a set of edges) from the input graph [32]. We use fidelity to evaluate how counterfactual the generated explanations are the datasets Mutagenicity, NCI1 and BA-2motifs. A large fidelity score indicates stronger counterfactual characteristics. It is important to note that fidelity may be sensitive to sparsity of explanations. The sparsity of an explanation S with respect to an input graph G (V, E) is
sparsity(S,, G) = 1 [s|
r that is, the percentage of edges remaining after the explanation is removed from G. We only compare explanations with the same level of sparsity.
Figure shows the results about fidelity. Our approach achieves the best fidelity performance at all levels of sparsity. The results validate the effecttivnness of our method in producing highly counter- factual explanations. RCExplainer also significantly outperforms RCExp-NoL.DD This confirms that using LDBs of decision regions extracted from GNNs produces more faithful counterfactual explanations.
CF- JT-GNNExplainer performs the best among the rest of the methods. This is expected as optimizes the counterfactual behavior of the explanations which results in higher fidelity for the explanations in comparison those produced by other methods such as GNNExplainer and PGExplainer.
The fidelity performance of SubgraphX reported in [47] obtained by setting the features of nodes that are part of the explanation to but not removing the explanation edges from the input graph. This does not remove the message passing roles of the explanation nodes from the input graph because the edges connected to those nodes still can pass messages. In our experiments, we directly block the messages that are passed on the edges in the explanation, which completely prevents the explanation nodes in the input graph to participate in the message passing. As a result, the performance of SubgraphX drops significantly.
*Code available at https: https://marketpllas rid=e41f63d3- e346- 4891 406644440664443277
8

---

(a) Mutagenicity
[b] 8A-2molils
(c) NCI
1.0
1.0
1.0
0.0
0.9
0.9
0.8
0.8
0.8
6.2
0.7
6.-
0.8
0.6-
0.5
Neiso (5)
Noiso (56
Noiso 156
Figure 2: Noise robustness (AUC) averaged across 10 runs for the datasets at different levels noise.
5.2 Robustness Performance
In this experiment, evaluate the robustness of all methods by quantifying how much explanation changes after adding noise to the input graph. For an input graph G and the explanation Ss, we produce a perturbed graph G" by adding random noise to the node features and randomly adding or deleting some edges of the input graph such that the prediction Using the same method we obtain the explamation S' on G'. Considering top-k edges S as the ground-trute and comparing S' against them, we compute receiver operating characteristic (ROC) curve and evaluate the robustness by the area under curve (AUC) of the ROC curve. We report results for h = 8 in Figure 2. Results for other values of are included in Appendix F where we observe similar trend.
G' is consistent with the prediction
G
Figure 2 shows the AUC of GNNExplainer, PGExplainer, RCExp-NoLDB and RCExplainer different levels of noise. A higher AUC indicates better robustness. The percentage of noise shows the proportion of nodes and edges that are modified. Baselines such as PGM- PGM--Eplainer and SubgraphX are not included in this experiment as they do not output the edge weights that are required for computing AUC. We present additional robustness experiments Appendix F where we extend all the baselines to report node and edge level accuracy.
GNNExplainer performs the worst on most of the datasets, since it optimizes each graph independently without considering other graphs in the training set. Even when no noise is added, the AUC of GNNExplainer is significantly lower than I because different runs produce different explanations for the same graph prediction. PGExplainer is generally more robust than GNNExplainer because the neural network they trained to produce explanations implicitly considers all the graphs used for training. -EXplaxxxee also performs worse than RCExplainer, which means it is more susceptible to the noise compared RCExplainer.
Our method achieves the best AUC on all the datasets, because the common decision logic carried by the decision regions of a GNN is highly robust to noise. PGExplainer achieves a comparable performance
method on the Mutagenicity dataset, because the samples of this dataset share lot of common structures such as carbon rings, which makes it easier for the neural network trained by PGExplainer to identify these structures in presence of noise. However, for BA-2motifs and NCII, this is harder samples share very few structures and thus the AUC of PGExplainer drops significantly. RCExplainer also significantly outperforms RCExp-NoL.DDR on these datasets which highlights the role of decision boundaries in making our method highly robust.
Method
GNNExplainer
PGExplainer
PGM-Explainer
SubgraphX
CF- CF-GNNExplainer
RCExplainer
Time
1.2s + 0.2
0.01s 0.03
3.9
77.88
4.5
4.6s + 0.2
0.01s 0.02
Table 1: Average time cost for producing an explanation on single graph sample.
We evaluate efficiency by comparing the average computation time taken for inference on unseen graph samples. Table shows the results on the Mutagenicity dataset. Since our method also can be directly used for unseen data without any retraining, it is as efffccintt as PGExplainer and significantly faster than GNNExplainer, PGM-Explainer, SubgraphX and CF-GNNExplainer.
Efficiency.
6 Conclusion
In this paper, we develop a novel method for producing counterfactual explanations on GNNs. We extract decision boundaries from the given GNN model to formulate intuitive and effective

---

counterfactual loss function. We optimize this loss to train neural network to produce explanations with strong counterfactual characteristics. Since the decision boundaries shared by multiple samples of the same predicted class, explanations produced by our method are robust and do not overfit the noise. Our experiments on synthetic and real-life benchmark datasets strongly validate the efficacy of our method. In this work, we focus on GNNs that belong to Piecewise Linear Neural Networks (PLNNs). Extending our method to other families of GNNs and tasks such as link prediction, remains an interesting future direction.
Our method will benefit multiple fields where GNNs intensively used. By allowing the users to interpret the predictions of complex GNNs better, it will promote transparency, trust and fairness in the society. However, there also exist some inherent risks. A generated explanation may expose private information if our method is not coupled with an adequate privacy protection technique. Also, some of the ideas presented in this paper may be adopted and extended to improve adversarial attacks. Without appropriate defense mechanisms, the misuse of such attacks poses a risk of disruption in the functionality of GNNs deployed in the real world. That said, we firmly believe that these risks can be mitigated through increased awareness and proactive measures.
Acknowledgments and Disclosure of Funding
Lingyang Chu's research is supported in part by the startup grant provided by the Department of Computing and Software of McMaster University. All opinions, findings, conclusions, and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.
References
[1] J. Adebayo, J. Gilmer, M. Muelly, Goodfellow, M. Hardt, and B. Kim. Sanity checks for saliency maps. In Advances in Neural Information Processing Systems.
[2] A. Bajchevski and S. Günnemann. Certifiable robustness to graph perturbations. arXiv preprint arXiv:9900 14356, 2019.
[3] E. Cho, S. A. Myers, and J. Leskovec. Friendship and mobility: user movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1082- 1090, 2011.
[4] L. Chu, X. Hu, Hu, L. Wang, and Pei. Exact and consistent interpretation for piecewise linear neural networks: A closed form solution. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1244 1253, 2018.
[5] V. Crawford, A. Kuhnle, and M. Thai. Submodular cost submodular cover with an approximate oracle, In International Conference on Machine Learning, pages 1426-1435. PMLR, 2019.
[6] A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds, correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-799 1991.
[7] M. Denil, S. G. Colmenarcjo, S. Cabi, D. Saxton, and N. de Freitas. Programmable agents. arXiv preprint arXiv: 1706.06363. 2017.
[8] Y. Duan, M. Andrychowicz, B. C. Stadie, J. Ho, Schneider, I. Sutskever, P. Abbeel, and W. Zaremba. One-shot imitation learning. arXiv preprint
2017.
[9] Fan, Y. Ma. Q. Li, He. E. Zhao, J. Tang, and Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pages 417-426. 2019.
[10] T. Freiesleben. Counterfactual explanations & adversarial examples common grounds, essential differennee. and potential transfers. arXiv preprint arXiv:2009.00 2044:27000004887,, 2020.
[11] A. Ghorbani, A. Abid, and J. Zou. Interpretation of neural networks is fragile. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3681-3688, 2019.
[12] X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 299-256. JMLR Workshop and Conference Proceedings, 2010.
10

---

[13] X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks, In Proceedings of the fourleenth international conference on artificial intelligence and statisticx, pages 315-323. JMLR Workshop and Conference Proceedings, 2011.
[14] I. Goodfellow, D. Wande-Farley, M. Mirza, A. Courville, and Y. Bengio. Maxout networks. In International conference on machine learning, pages 1319-1327. PMLR, 2013.
[15] K. He, X. Zhang, Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Pruceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
[16] I. Holdijk, M. Boon, S. Henckens, and I.. de Jong. [re] parameterized explainer for graph neural network. In ML Reproducibility Challenge 2020, 2021.
[17] W. Huber, V. J. Carey, L.. Long, S. Falcon, and R. Gentleman. Graphs in molecular biology. BMC bioinformatics, 8(6): 1-14, 2007.
[18] R. K. Iyer and J. A. Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances in Neural Information Processing Syxtems.
[19] M. Jiang, Z. Li, S. Zhang, S. Wang. X. Wang, Q. Yuan, and Z. Wei. Drug target affinity prediction using graph neural network and contact maps. RSC Advances, 10035)200701-2071, 2020.
[20] H. Jin and X. Zhang. Latent adversarial training of graph convolution networks. In ICML Workshop on Learning and Reasoning with Graph- Srrph-Structured Representations, 2019.
[21] Kazius, R. McGuire, R. Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 113-333,,,, 2005.
[22] T. N. Kipt and M. Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Conference Truck Proceedings.
[23] M. Liu, Y. Luo, L. Wang. Y. Xie, H. Yuan, S, Gui, H. Yu, Z. Xu, J. Zhang, Y. Liu, K. Yan, H. Liu, C. Fu, B. Oztekin. X. Zhang, and S. Ji. DIG: A turnkey library for diving into graph deep learning research. arXiv preprint arXiv:2103. 12608, 2021.
[24] A. Lucic, M. ter Hoeve, G. Tolomei, M. de Rijke, and F. Silvestri. Cf Cf-gnnexplainer: Counterfactual explanations for graph neural networks. arXiv preprint arXiv22102.03222 2021.
[25] 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.
[26] C. Molnar.
Interpretable Muchine Learning.
2019. https://christophhn http:hrrriiitopoogihhhhbbbb io/
interpretable-ml-boon
[27] G. Montúfar, R. Pascanu, K. Cho, and Y. Bengio. On the number of linear regions of deep neural networks arXiv preprint 1rXiv:1402.1869, 2014.
[28] R. Moraffah, M. Karami, R. Guo, A. Raglin, and H. Liu. Causal interpretability for machine learning- problems, methods and evaluation. ACM SIGKDD Explorations Newsletter, 22(1)):8-33, 2020.
[29] V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In Ieml, 2010.
[30] D. Numeroso and D. Bacciu. Meg: Generating molecular counterfactual explanations for deep graph networks. arXiv preprint arXiv:2104 104.000000 2021.
[31] D. E. Pires. T. L. Blundell, and D. B. Ascher. pkesm: predicting small-molecule pharmacokinetic and toxicity properties using graph-based signatures. Journal of medicinal chemistry, 58(9):4066440) 4072, 2015.
[32] P. E. Pope. S. Kolouri, M. Rostami, C. E. 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-10788 2019.
[33] R. R. Selvaraju. M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In Proceedings of the IEEE international conference on computer vision, pages 61 618-66 8-626, 2017.
[34] L. Simon. M. Taylor, and Z. Kiss. Exact epidemic models on graphs using graph-automorpphis driven lumping. Journal of mathematical biology, 62(())479-505 2011.
[35] K. Simonyan, A. Vedaldi, and A. Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. ICLR, 2014.

---

[36] K. Sokol and P. A. Flach. Counterfactual explanations of machine learning predictions: opportunities and challenges for ai safety. In SafeAI@ AAAI, 2019.
[37] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Conference Track Proceedings.
[38] Vu and Thai. Pem-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in Neural Information Processing Systems.
[39] N. Wale and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and clas- sification. In Sixth International Conference Data Mining (ICDM'06), pages 678 689, 2006. doi: 10. 10.11091CDM.2006.
[40] L. A. Wolsey, An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385 393, 1982.
[41] Xiong, Z. Xiong, K. Chen, H. Jiang, and M. Zheng. Graph neural networks for automated de novo drug design. Drug Discovery Today, 2021.
[42] H. Xu, Ma, H.-C. Liu, D. Deb, H. Liu, J.-L. Tang, and A. K. Jain. Adversarial attacks and defenses in images, graphs and text: A review. International Journal of Automation and Computing, 151-77151-178, 2020.
[43] K. Xu, H. Chen, S. Liu, P.-. Chen, T.-W. Weng, M. Hong, and X. Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXtv preprint
2019.
[44] R. Yin, K. Li, G. Zhang, and J. Lu. A deeper graph neural network for recommender systems. Knowledge- Based Systems, 185: 105020, 2019.
[45] Z. Ying, D. Bourgeois, You, M. Zitnik, and Leskovee. Gnnexplainer: Generating explanations for graph neural networks. Advances in Neural Information Processing Systems, volume 32, 2019.
[46] H. Yuan, Tang, X. Hu, and S. Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery Data Mining, pages 430 438, 2020.
[47] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji. On explainability of graph neural networks via subgraph explorations. arXiv preprint
2021.
[48] M. D. Zeiler and R. Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision, pages 818-833. Springer, 2014.
[49] Zhang, S. Bargal. Lin, J. Brandt, X. Shen, and Sclaroff. Top-down neural attention by excitation backprop. International Journal of Computer Vision, 126(10):1084-1) 2018.
[50] M. Zhang and Y. Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems.
[51] D. Zügner and S. Günnemann. Adversarial attacks on graph neural networks via meta learning. arXiv preprint arXiv: 1902.98412, 2019.
[52] D. Zügner and S. Günnemann. Certifiable robustness and robust training for graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. pages 246 256, 2019.
[53] D. Zügner, Akbarnejad, and Günneeaann. Adversarial attacks neural networks for graph data, In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 2847-2856, 2018
12


Reviews:
[{"review_id": "r01XolWMZAe", "reviewer": "Reviewer_gQ2w", "summary": "This paper studies the problem of generating explanations for graph classifications. In particular, the paper focuses on the robustness of the explanation. A new explanation generation method is proposed where the key is a new learning objective of the generation model. The objective considers the prototype of each class to eliminate the impact of noise. Extensive experiments on benchmark datasets validate the effectiveness and efficiency of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strong points:\n1. This paper studies an important problem about the explanation of graph classification.\n2. This paper highlights the robustness of explanations and proposes a new method to enhance the robustness.\n3. Extensive experiments are conducted.\n\nWeak points:\n1. The paper is not well written with many unclear points. For instance, \n- Definition 1 is unclear due to the vague descriptions such as \"significantly\" and \"slight changes\".\n- Is the counterfactual same as the concept in causal theory? If so, the requirement of counterfactual (the first requirement of the explanation) should be revised. In causal theory, the change of outcome variable (prediction) is not necessary for a counterfactual.\n\n2. \"For experiments, our explanation network f consists of 2 fully connected layers with a ReLU activation and the hidden dimension of 64.\" It would be better to explain the intuition of the network design and explore the structure of the explanation network.\n\n3. \"CF-GNNExplainer [20] is only included in the results of node classification, because the source code of CF-GNNExplainer is not available and [20] reports performance on only node classification tasks.\"\nThis is a ridiculous excuse for not reporting the performance of an important baseline! (This makes me decrease the rating)\n\n4. The authors argue the importance of aligning well between the generated explanation and human intuition. How does the proposed method achieve this target?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "bDLZ1FKsTTK", "reviewer": "Reviewer_BMo4", "summary": "This paper proposes a GNN explanation model to generate counterfactural and noise-robust explanations. The explanations are produced by a neural network as a set of edges where before and after removing them will result in a large deviation in the final prediction. To train such as neural network, instead of directly maximizing the deviation (in terms of confidence score) before and after removing the edges, the paper leverages common decision boundaries summarized from the linear decision boundaries of the GNN over the training graphs so that removing the edges cause many violations of the common decision boundaries. This way, the explanation is more robust to noise and does not overfit to individual instances. Experiments demonstrate the fidelity and robustness of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Quality: Overall, I feel the paper makes a solid contribution for explaining GNNs. The motivation of generating conunterfactual explanations robust to noise is convincing, and the proposed solution is technically sound. By summarizing common decision boundaries from the linear decision boundaries of the GNN, the proposed method find edges removing which cause the maximum violations of these decision boundaries. It makes sense to me to use common decision boundaries instead of prediction scores to measure the \"importance\" of an edge, because it is more robust to noise and generates explanations based on consistency with the whole training data instead of individuals. The experiments on fidelity and robustness validate that the method generates high-quality and robust-to-noise explanations for GNNs. One concern is that many approximations are made to transform those NP-hard optimization problems to greedy/continuous problems. This results in no gurantees in the solutions. I would like the authors to explain more about the effects (on solution quality and efficiency) of such approximations.\n\nOriginality and Significance: Since I am not an expert in GNN explanability, I can hardly evaluate the originality and significance of the method, such as how counterfactual explanations are generated for models other than GNNs, and whether the proposed method makes a simple modification to existing methods for explaining general neural networks. I will listen to other reviewers' comments on this part.\n\nClarity: The writing of this paper can be improved. For example, \"common decision boundary\" appears first in the abstract, however its concrete explanation does not appear until section 4.1. I would suggest avoid such technical terms in abstract, and explain (define) \"common decision boundary/logic\" explicitly in the introduction. Also, the sentence \"Our explanations are naturally robust to noise because they are produced from the common decision boundaries of a GNN that govern the predictions of many similar input graphs\" is not straightforward to me. I spent a hard time trying to understand why the proposed method is robust to noise, until I understand common decision boundary in the very late part of the paper.\n\nI give a score 6 with a low confidence due to my limited knowledge in this area. I am willing to adjust my score if other reviewers help endorse its originality and significance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors comment on the potential privacy concerns of the generated explanations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "BtrtmFqt5L7", "reviewer": "Reviewer_Vbh5", "summary": "This paper introduces a robustness explanations method on graph neural networks (RCExplainer) against random noise. To achieve their goals, they first model the common decision logic of a GNN and then extract robust counterfactual explanations by neural networks that explore the decision logic carried by the linear decision boundaries of the decision regions. \nTheir conducted experiments have verified the effectiveness of the proposed framework.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "There are several major concerns in this work.\n\n1. Authors may put more effort to improve the presentation/writing of the paper.\n\n\n2. The task is a little bit weird for me. \n Can random noise affect/change the GNN's prediction (e.g., node's label)? \nIf yes,  it would be better to investigate whether there are some correlations between GNNs and explainer.\nIt's not easy to understand how to conduct a robust GNN Explainer on non-robust GNNs. If the perturbations can change the GNN's prediction, it has a high chance to change the subgraph generated by the proposed method.\n\nAlthough this work doesn't work on adversarial attacks on GNNs model, they are suggested to perturb the graph data via some GNNs attacking methods to solid their methods, instead of random noise. \n\nHow to add the random noise? Is it for the entire graph data or individual node? \nFor the explanation on a target node,  if added noise is far away from the local neighbors of the target node, it's meaningless to study their robustness and it's also hard to change the explanation results.\n\n3. Modeling decision regions for robust explainer is not well motivated. \nAre there any other solutions? What are the detailed advantages of modeling decision boundaries for train GNN Explainers in their proposed methods?\n\n4. It would be better to analyze the computation time for training, although the proposed method doesn't require too much time for inference.\nThe inference time of their methods basically depends on their designed neural networks. As they only compute a score on the embedding of two nodes, it works very efficiently.  \n\n5. CF-GNNExplainer ->\"CF-GNNExplainer [20] is only included in the results of node classification, because the source code of CF-GNNExplainer is not available \"\nThe code has already been released three months ago. You can check at GitHub.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A", "review_text": "", "extra_scores": {"ethical_concerns": "N.A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "AfVty4pRh0-", "reviewer": "Reviewer_1Uri", "summary": "The paper deals with the problem of generating counterfactual explanations for GNNs. The proposed approach is based on directly optimizing the counterfactual explanations in an end-to-end learning scheme. The proposed framework is validated on both synthetic and real data. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Originality: The problem of generating counterfactual explanations form GNNs is very interesting, and worth investigating. The proposed methodology is definitely relevant and valid. Contrary to the existing work, the proposed approach 1) explicitly models the common decision logic of GNNs on similar input graphs and 2) tends to promote that removing the set of edges identified by an explanation from the input\ngraph changes the prediction significantly. \n\nQuality: The paper is technically sound. The framework is well validated with experimental results on both real and synthetic data. The discussion on the performance of the method on the mutagenicity dataset (in terms of AUC) is interesting. I would expect that a similar discussion on how the graph model/topology affect the performance of the algorithm to be very informative. \n\nClarity: The paper is generally well written. However, adding a block diagram of the architecture in the main text is needed (Fig. 3 of the appendix). Moreover, some qualitative results on the explanations (similar to table 4 of the appendix) and the difference from the existing works would help the reader to position the paper and appreciate the contribution. \n\nSome additional minor comments:\n\n- line 143: the sentence \"Because the feature….” Is not grammatically correct. \n- Specify what are the GNNs that are used in the experiments.  \n\nSignificance: The obtain results are interesting and will probably be used by the research community. \n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors elaborate on the limitations and societal impact in the conclusion section. The points that they raise are valid. I would add as a limitation of the existing work the lack of ability to deal with weighted edges. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues occur from this paper. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall the reviewers agree that this work contributes a valid, useful method for robust counterfactual explanations on GNNs (itself of significant importance) that is well evaluated and explained. Note the reviewers have pointed out several places where the write up could be improved, and the authors are advised to address these in the final version of the work.
Decision: Accept (Poster)