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.cccssuu.c. sfu.ca
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 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 04 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 (c))
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) + AEHiP 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) + RiRdiscrette 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 (()))(())))) 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 log(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 2044000000004877,, 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 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": "avis1Em2VYO", "reviewer": "Reviewer_ZnuS", "summary": "The paper presents an approach to GNN prediction explanations based on providing modifications to the input samples to change the prediction outcomes. The idea is that those modifications are the ones that can make a human understand the reason for a prediction. For example, a post is considered misinformation due to its connections to other misinformation posts. Those connections, i.e., edges, constitute the explanation for marking a post as misinformation.\nThe idea presented in the paper consists of distilling the model learned by the GNN into a set of polytopes that bound the decision regions. This aims to make the explanation model more robust to “noise” (intended as random connections in the input graphs).\nThe loss function presented in the paper is then used to modify the input graph to move the sample away from the original region to a different region.\nThe experimental results are presented in graph classification, but the method can be extended to node classification.", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "The paper, in my opinion, has some important and strong aspects that make it interesting for the community.\nIn particular, I believe that the following are its main strengths:\n* The method is general and can be used for the three tasks usually studied in graph learning\n* Once the boundaries are found, the method consists of moving a sample from one boundary to another to change the prediction outcome. This makes the method efficient at explanation time\n* The experiments are conducted on datasets that are standard for this task.\n\nThe paper, and the research presented in the paper, suffer from the following limitations:\n* First and foremost, in all of the counterfactual explanation techniques, there is usually a component of “minimality” that is missing from this work. In general, one seeks to make a few modifications as possible to the input sample. This aspect is totally absent in this research and, in my opinion, is of fundamental importance in this area. In fact, even in the experimental section, one can see that authors always measure fidelity as a function of sparsity but, typically, one should seek the smallest modification possible and then measure fidelity, sparsity, and size of the recommendation.\n* The first half of the intuition in 4.1 makes sense, but this formulation also means that you have to use piecewise linear activation functions for this method to work. You want to extract a decision region with 2 properties:\n   * Should be induced by a subset of LDBs in H\n   * Should cover many instances in the training set, and all covered graphs should be predicted as the same classification\n* Also, it is not really clear how LDBs are related to GNNs (not really considering that you base your formulation only on GCNs) as it could be used, in principle, in all deep learning mechanisms, right? In fact, I would like the authors to comment on how the method described in 4.2 is related to GNN.\n* I find the end of 4.1 and 4.2 a bit hard to follow, but we see here that it involves sampling from H, which does not seem very robust because then the partitioning of O^d is dependent on which LDBs were sampled from H. The authors even say that r(P,c) induced by LDBs in the \\tilde{H} might have instances that aren’t predicted as the correct class. Do the explanations change depending on the sampling of H? If so, this is not robust at all.\n* Comparison to existing methods is weak:\n   * They say existing methods are not robust to noise bc they optimize for individual inputs. They cite PGExplainer here as one of the methods. Still, unless I did not understand correctly, it does not optimize for individual inputs and instead learns a general explanation model applied to individual inputs.\n   * The comparison to CF-GNNExplainer is not fair, in my opinion. The method they propose is similar to CF-GNNExplainer in the way they build the CF explanation, but it has not been properly acknowledged in the paper. Even the loss functions are very similar, but this is not properly acknowledged, as well. Both methods learn a sparsifier that is then thresholded to find the edges to be removed.\n      * Also, I do not quite understand why authors refer to CF-GNNExplorer as an adversarial attack method. From my understanding of the paper, the main goal of CF-GNNExplainer is to build CF explanations and not adversarial samples.\n* The baselines mentioned in the experiments are not CF explanations at all. This makes the experiment not convincing at all. Also, the methods are for explaining node classifiers and not graph classification models. I would appreciate some thoughts on this point.\n   * The only proper baseline method is CF-GNNExplainer, but it is reported in the Appendix, and I would not like to comment on the results there.\n* There are some unjustified claims in the paper:\n   * Lines 7-8: there is no experimental support for this claim.\n   * Lines 14-15: Authors do not do any human experiments, so they cannot claim that their method aligns well with human intuition.\n   * Line 114: the sentence “directly optimize for explainability of an explanation” means nothing. How do you define “explainability”?\n   * Lines 126-131: the definition is not a proper definition. What is “slight,” how do you quantify a “slight change”? How do you define “stable”?\n   * Line 230: I’ve found no support for this claim at all anywhere.\n   * Line 302-303: have you tried to reuse the network without retraining? Does it work as claimed in the paper?\n* The claim that the method is robust to noise is weakly supported by the experiments, in my opinion. For instance, in Mutagenicity, PGExplainer is close (although the error bars are separate) to the other two methods.\n   * Also, the robustness feature is poorly motivated in the paper. Why is it essential to be robust? If you don’t mention proper motivations, the problem definition feels rather artificial.\n\nMinor remarks:\n* Requirements require → Can you change this? It sounds a little bit odd :)\n* The sentence at lines 143-144 is broken; I cannot parse it\n* Line 147. Does FC actually mean FC + nonlinearity?\n* Can you improve the definition of what the set P is? It is not really clear. Is it a set of convex polytopes, or is it a set of LBDs?\n* Please define the positive and negative side at Line 273.\n* What is the * operator in Eq. (9)?\n* In references [1], [15], and [46] the year is missing\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not properly addressed in Section 6.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "PEofb80aTe9", "reviewer": "Reviewer_uoze", "summary": "The paper proposed a method for robust counterfactual explanation on GNN which leverages an extraction decision boundaries shared by multiple samples. It is an interesting framework and the experimental results justified the proposed method.", "questions": "", "limitations": "", "rating": 6, "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": "the topic of robust counterfactual explanations in GNN is certainly of high interest for the community and it has been, yet, poorly explored.\nAs such the work as very high potential impact. The proposed approach tackles specifically the issue of providing subgraph explanation with robustness. The proposed method is neat and the paper is easy to follow. However, I have a few concerns.\n\n1, the paper mentioned that the explanation align well with human intuition by removing the set of edges. It is less convincing to claim the human intuition here without user studies.\n\n2, the extracting decision optimization algorithm has been leveraged by SCSC. I'm curious how to make the overall efficiency much better? More complexity analysis would be more trustworthy.\n\n3, In order to better evaluation the explainability, how to quantify the significance of G_{E/S} changes? In [1], it use 'faithfulness' to justify the explainability. I hope similar notion could be adopted as explainability evaluation.\n\n[1] ERASER : A Benchmark to Evaluate Rationalized NLP Models\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1h"}, "extra_text": {}}, {"review_id": "6ZB0hoQSY-G", "reviewer": "Reviewer_SgPD", "summary": "This paper focuses on the counterfactual explanations of GNNs, and proposes a method to identify a subgraph of an input graph whose absence could cause the change of prediction. In particular, the proposed method starts from extracting the decision regions over similar graph instances: the subsets of linear decision boundaries (LDBs), which is later used to formulate the counterfactual loss function. Then a NN is used to predict the probability of each edge. Furthermore, a counterfactual term is included in the loss function to ensure the counterfactual property of explanations. Experiments are done on several datasets to illustrate the proposed model.", "questions": "", "limitations": "", "rating": 5, "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": "Originality: Though some concepts like LDB and counterfactual have been used in other domains, to my knowledge, the framework proposed by this paper is original in the field of GNN explanation. However, the definition of counterfactual explanation seems broken. Please refer to the tech comments below.\n\nQuality: This paper is well-written and the authors make their idea and the workflow clear. However, the reviewer thinks more experiments are needed to demonstrate the effectiveness of the proposed method. In addition, the definition of noise in this paper is not very clear, without which robustness can’t be clarified as well. Details will be described in following tech comments.\n\nClarity: the structure of this paper is well organized. It starts with the intuition and then get into the tech details. Each module(e.g. LDBs, counterfactual subgraph) is introduced following the pipeline of the proposed method, which makes the paper structure quite clear. \n\nSignificance: The experiments are conducted on three small datasets and consider several relevant baselines for GNN explanation. The results are significantly better than the baseline approaches on criteria fidelity and AUC save for the AUC performance on Mutagenicity. \n\nTech Comments: \n\n1. Definition of counterfactual explanation: According to the previous, the definition of counterfactual explanation is “if X had been different, Y would not have occurred”, rather than “if X had not occurred, Y would not have occurred” as claimed by the authors. That means, the authors only replace the subgraph (X) with the empty set, rather than the reference subgraph (that could be the empty or other subgraphs). Moreover, recent studies find that simply replacing the features of interest (X) with the empty could cause the distribution shift from the complete graphs. Please explain or clarify these points.\n    - Explaining image classiﬁers by counterfactual generation. In ICLR, 2019.\n\n2. Definition of noise: I cannot find a clear definition of noise in this paper. I think it’s necessary to clarify it when you are discussing robustness. For example, what does 30% noise mean? Adding random noise whose magnitude is 30% of the original node feature or randomly adding or deleting 30% edges or do them both?\n\n3. Robustness in GNN explanation field: It will be much better if the authors can explain more why the robustness defined in this paper is important. In CV domain, after adding noise to the panda picture, the NN cannot classify it correctly anymore while human being can’t see any difference between the original pic and the noisy one. However, taking mutagenicity for example, adding or deleting 30% of edges will make the original molecule a totally different one even though the GNN doesn’t change the prediction(noxious or not). In these case, it’s reasonable for an explainer to identify a different subgraph. So, I don’t think evaluating the robustness based on the similarity between S’ and S makes perfect sense to me.\n\n4. The ablation study of the counterfactual term. The effectiveness of the counterfactual part needs to be demonstrated by setting λ=1or deleting the counterfactual term L_opp in eq(8).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the main review.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new method to produce robust counterfactual explanations for the predictions of GNNs. However, reviewers raised several concerns about the method, the experiments, and the writing. Therefore, the paper cannot be accepted in the current form.
Decision: Accept (Poster)