CLEAR: Generative Counterfactual Explanations on Graphs
Authors: Jing Ma
Ruocheng Guo
Saumitra Mishra
Aidong Zhang
Jundong Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: Counterfactual explanations
graph
explainability

Abstract: Counterfactual explanations promote explainability in machine learning models by answering the question “how should the input instance be altered to obtain a desired predicted label?". The comparison of this instance before and after perturbation can enhance human interpretation. Most existing studies on counterfactual explanations are limited in tabular data or image data. In this paper, we study the problem of counterfactual explanation generation on graphs. A few studies have explored to generate counterfactual explanations on graphs, but many challenges of this problem are still not well-addressed: 1) optimizing in the discrete and disorganized space of graphs; 2) generalizing on unseen graphs; 3) maintaining the causality in the generated counterfactuals without prior knowledge of the causal model. To tackle these challenges, we propose a novel framework CLEAR which aims to generate counterfactual explanations on graphs for graph-level prediction models. Specifically, CLEAR leverages a graph variational autoencoder based mechanism to facilitate its optimization and generalization, and promotes causality by leveraging an auxiliary variable to better identify the causal model. Extensive experiments on both synthetic and real-world graphs validate the superiority of CLEAR over state-of-the-art counterfactual explanation methods on graphs in different aspects.  

CLEAR: Generative Counterfactual Explanations on Graphs
Jing Ma University of Virginia Charlottesvilll, VA, USA
Ruocheng Guo Bytedance AI Lab London, UK ju rguo, agu.aau@@gail.ccom
Saumitra Mishra J.P. Morgan Al Research London, UK saumi www.mmisssa@pmrrre.e....e com
Aidong Zhang
Jundong Li University of Virginia Charlottesville, VA. USA jundongdvirginia. edu
University of Virginia
Charlottesville, VA, USA
aidong@virginia.c
Abstract
Counterfactual explanations promote explainability in machine learning models by answering the question "how should inpur instance be perturbed to obtain desired predicted label?". The comparison of this instance before and after pertur- bation can enhance human interpretation. Most existing studies on counterfactual explanations are limited in tabular data or image data. In this work, we study the problem of counterfactual explanation generation on graphs. A few studies have explored counterfactual explanations on graphs, but many challenges of this problem are still not well-addressed: 1) optimizing in the discrete and disorganized space of graphs; 2) generalizing unseen graphs; and 3) maintaining the causality in the generated counterfactuals without prior knowledge of the causal model. To tackle these challenges, we propose novel framework CLEAR which aims to generate counterfactual explanations on graphs for graph-level prediction models. Specifically, CLEAR leverages graph variational autoencoder based mechanism to facilitate its optimization and generalization, and promotes causality by leverag- ing an auxiliary variable to better identify the underlying causal model. Extensive experiments on both synthetic and real-world graphs validate the superiority of CLEAR over the state-of-the-an art methods different aspects.
Introduction
To facilitate explainability in opaque machine learning (ML) models (e.g., how predictions are made by a model, and what to do to achieve desired outcome), explainable artificial intelligence (XAI) [1] has recently attracted significant attention in many communities. Among the existing work of XAI, special class, i... counterfactual explanation (CFE) [2], promotes model explainability by answering the following question: "For specific instance, how should the inpul features X be slightly perturbed to new features X' obtain different predicted label (often a desired label) from ML models?" The original instance whose prediction needs to be explained is called an explainee instance, and the generated instances after perturbation are referred as "counterfactual explanations". Generally, CFE promotes human interpretation through the comparison between X and X'. With its intuitive nature, CFEs can be deployed in various real-world scenarios such as loan application and legal framework [3]. Different from traditional CFE studies [2, 3, 4, 5] on tabular or image data, recently, CFE on graphs is also an emerging field in many domains with graph structure data such as molecular analysis [6] and professional networking [7]. For example, consider grant application prediction [8] model with each input instance as a graph representing a research team's 's collaboration network,
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

where each node represents a team member, and each edge signifies a collaboration relationship between them. Team leaders can improve their teams for next application by changing the original graph according to the counterfactual with a desired predicted label (application being granted). If the counterfactual is more dense than the original, the team leader may then encourage more team collaborations. To this end, in this work, we investigate the problem of generating counterfactual explanations on graphs. As shown in Fig. 1, given a prediction model / on graphs, for a graph instance G. we aim to generate counterfactuals (c.g.. GCr) which are slightly different from G w.r.t. their node features or graph structures to elicit a desired model prediction. Specifically, we focus on graph-level prediction without any assumptions of the prediction model type and its model access, ic., f can be a black box with unknown structure.
Recently, a few studies [9, 6, 10, 11, 12, 13] explore extend CFEs into graphs. However, this problem still remains a daunting task due to the following key challenges: 1) Optimization: Different from tradi- tional data, the space of perturbation operations on graphs (e.g.. add/remove nodes/edges) is discrete, dis- organized, and vast, which brings difficulties for op- timization in CFE generation. Most existing methods [6. 11] search for graph counterfactuals by enumer- ating all the possible perturbation operations on the current graph. However, such enumeration graphs is of high complexity, and it is also challenging to solve an optimization problem in such a complex search space. Few graph CFE methods which enable gradient- based optimization either rely on domain knowledge [6] or assumptions [10] about the prediction model to facilitate optimization. However, these knowledge and assumptions limit their applications in different scenarios. 2) Generalization: The discrete and disorganized nature of graphs also brings challenges for the generalization of CFE methods on unseen graphs, as is hard sequentialize the process of graph CFE generation and then generalize it. Most existing CFE methods on graphs [9, 12] solve an optimization problem for each explainee graph separately. These methods, however, cannot be generalized to new graphs. 3) Causality: It is challenging to generate counterfactuals that are consistent with the underlying causality. Specifically, causal relations may exist among different node features and the graph struc- ture. In the aforementioned example. for each team, after establishing more collaborations, the team culture may be causally influenced. Incorporating causality can generate more realistic and feasible counterfactuals [4]. but most existing CFE methods either cannot handle causality, or require too much prior knowledge about the causal relations in data.
Original (G)
Graph models
X
f(G) 0
T
Counteriactul explunation geserator
Same prediction model
Different predicted labels
Counterfactual (F
V VSGOF)= =1
model
Figure I: An example of CFE on graphs.
To address the aforementioned challenges. in this work, we propose a novel framework - generative CounterfactuaL ExplAnation Rate for graphs (CLEAR). At a high level, CLEAR is generative, model-agnostic CFE generation framework for graph prediction models. For any explainee graph instance, CLEAR aims to generate counterfactuals with slight perturbations on the explainee graph to elicit desired predicted label, and the counterfactuals are encouraged to be in line with the underlying causality. More specifically, to facilitate the optimization of the CFE generator, we map each graph into latent representation space, and output the counterfactuals as probabilistic fully-connected graph with node features and graph structure similar as the explainee graph. In this way, the framework is differentiable and enables gradient- based optimization. To promote generalization of the CFE generator on unseen graphs, we propose a generative way to construct the counterfactuals. After training the CFE generator, it can be efficiently deployed to generate (multiple) counterfactuals on unseen graphs, rather than retraining from scratch. To generate more realistic counterfactuals without explicit prior knowledge of the causal relations, inspired by the recent progress in nonlinear independent component analysis (ICA) [14] and its connection with causality [15], we make an exploration to promote causality in counterfactuals by leveraging an auxiliary variable to better identify the latent causal relations. The main contributions of this work can be summarized as follows: 1) Problem. We study an important problem: counterfactual explanation generation on graphs. We analyze its challenges including optimization, generalization, and causality, To the best of our knowledge, this is the first work jointly addressing all these challenges of this problem. 2) Method. We propose a novel framework CLEAR to generate counterfactual explanations for graphs. CLEAR can generalize unseen graphs, and promote causality in the counterfactuals. 3) Experiments. We conduct extensive experiments on both synthetic and real-world graphs to validate the superiority of our method over ofate-of-the-arr baselines of graph CFE generation.
2

---

2 Preliminaries
A graph G () is specified with its node feature X and adjacency matrix A. We have graph prediction model f g + +y, where & and y represent the space of graphs and labels, respectively. In this work, we assume that we can access the prediction of f for any input graph, but we do not assume the access of any knowledge of the prediction model itself. For graph G E we denote the output of the prediction model as Y = f(G). A counterfactual GCP = (X (CCF is expected to be similar as the original explainee graph G. but the predicted label for GCF made by f (i.e., yCF J(GCF) should be different from f(G). With a desired label Y (here Y + Y), the counterfactual GCF is considered to be valid if and only if Y YCF. In this paper, we mainly focus on graph classification, but our framework can also be extended other tasks such as node classification, as discussed in Appendix D.
Suppose we have a set of graphs sampled from the space G, and different graphs may have different numbers of nodes and edges. counterfactual explanation generator can generate counterfactuals for any input graph G w.r.t. its desired predicted label Y As aforementioned. most existing CFE methods graphs have limitations in three aspects: optimization, generalization, and causality. Next, we provide more background of causality, The causal relations between different variables (c.g., node features, degree, etc.) in the data can be described with a structural causal model (SCM):
Definition (Structural Causal Model) A structural causal model (SCM) [15] is denoted by triple (U. V. F): U is set of exogenous variables, and V is set of endogenous variables. The structural equations F= { (F,,... Fv1 determine the value for each V V.E V with V, v-= V.=FF.PAA, (PA, U:), here PA, S V, denotes the "parents" of Vi, and U; CU.
Definition 2. (Causality in CFE) For an explainee graph G, a counterfactual GCF satisfies causality the change from G to GCF is consistent with the underlying structural causal model.
Example: the aforementioned grant application
example, for research team which has been rejected for an application before (as the graph G in Fig. 2). to get the next application approved, a valid counter- factual may suggest this team to improve the number of collaborations between team members. Based on woal-world observations, we assume that an additional causal relation exists: the number of team collabora- tions causally affects the team culture. For example, for the same team, if more collaborations had been established, then the team culture should have been improved in terms of better member engagement and respect for diversity. The SCM is illustrated in Fig. 2, where we leave out the exogenous variables for simplicity. Although the team culture usually does not affect the result of grant application, the counterfactuals with team culture changed correspondingly when the number of collaborations changes are more consistent with the ground-truth SCM. G in Fig. 2 shows an example of such counterfactuals. In contrast, if counterfactual improves team's 's number collaborations alone without improving the team culture (see G. in Fig. 2), then it violates the causality. As discussed in [4], traditional CFE methods often optimize a single instance, and are prone to perturb different features independently, thus they often fail to satisfy the causality.
Counterfactual CF
Team culture
of collatorations
Causality
Grant application
Original (f)
Counterfactual(55
Causality
Figure 2: An example of causality in CFE.
The Proposed Framework - CLEAR
In this section, we describe a novel generative framework - CLEAR, which addresses the problem of counterfactual explanation generation for graphs. First, we introduce its backbone CLEAR- VAE to enable optimization on graphs and generalization on unseen graph instances. This backbone is based on graph variational outo-encoder (VAE) [16] mechanism. On top of CLEAR-VAL we then promote the causality of CFEs with an auxiliary variable.
3.1 CLEAR- VAE: Backbone of Graph Generative Counterfactual Explanations
Different from most existing methods [9, 12] for CFE generation on graphs which focus on a single graph instance, CLEAR is based on generative backbone CLEAR-VAL VAE which can efficiently
3

---

Original graph (G)
Auxiliary
KLAP QQ)
Counterfactual (G cF)
variable S
Encoder
Decoder
Sampling
Black
Similarity loss (G, GF)
Black box
f(G)=Y Y
Counterfactual prediction loss (("))
yer
=F(G
Nodes
Node features
Edges
Inserted nodes
Perturbed node features
Inserted edges
Deleted nodes
Graph representations
Deleted edges
Figure 3: An illustration of the proposed framework CLEAR.
generate CFEs for different graphs after training, even for the graphs that do not appear in the training data. As shown in Fig. 3, CLEAR-VEL VAE follows traditional graph VAE [16] architecture with an encoder and decoder. The encoder maps each original graph G (X, A) into latent space representation Z, then the decoder generates counterfactual GCF based on the latent representation Z. Following the VAE mechanism as in [16, 17] and its recent application in CFE generation for tabular data [4, 18), the optimization objective is based on the evidence lower bound (ELBO). which lower bound for the log likelihood In P(GCF|Y* G). Here, P(GCF G¹) is the probability
of the generated counterfactual GCF conditioned Y*. The ELBO for CLEAR VAE can be derived as follows:
input explainee graph G and desired label
P(P G) 2 Bolln P(GCF 2, Y", G)]
(1)
where Q refers to the approximate posterior distribution Q(ZIG, and KL(-11-) means the Kullback-Leibler (KL) divergence. The first term P(GEFIZ,Y" Y", xxx G') denotes the probability of the generated counterfactual conditioned the representation Z and the desired label Y Due the lack of ground-trutt counterfactuals, maximizing this term can be considered generating valid graph counterfactuals w.r.t. the desired label Y*, thus we replace this term with =Elld(G, GCF) + + ((f(GeF) F) Y")), where d(.,-) is similarity loss, which is distance metric measure the difference between and GCF I(-) the counterfactual prediction loss to measure the difference between the predicted label f(GCF) and the desired label Y*. In summary, these two terms encourage the model to output counterfactuals which similar as the input graph but elicit the desired predicted label. is hyperparameter to control the weight of the counterfactual prediction loss. Overall, the loss function of CLEAR CLEAR-VAE is:
hard to directly optimize this term. But inspired by [4],
= Eo[[GG, GCF) a ((F Y,Y")) }
(2)
Encoder. In the encoder, the input includes node features X and graph structure A of the explainee graph G, as well the desired label y*, the output is latent representation Z. The encoder learns the distribution Q(Z Y*). We use Gaussian distribution P,Z Y*) (N(u((Y)) diag) diag(o?(Y"))) as prior, and enforce the learned distribution Q(Z|G,Y) to be close to the prior by minimizing their KL divergence. Here, He (Y") and diag(o?(Y"))) are mean and diagonal covariance of the prior distribution learned by a neural network module. Z is sampled from the learned distribution QZIGG, Y*) with the widely-used reparameterization trick [17].
Decoder. In the decoder, the input includes Z and Y*, while the output is the counterfactual GCP CF )CF). Different counterfactuals can be generated for one explainee graph by sampling Z from Q(ZiG, Y*) for multiple times. The adjancency matrix often discrete, and if edge from node i to node j exists, otherwise A 0). To facilitate optimization, inspired by recent graph generative models [9, 16),
typically assumed to include only binary values (AG.,)
our decoder outputs a probabilistic adjacency matrix ÅCF with elements in range [0, 1], and then generates a binary adjancency matrix ACF by sampling from Bernoulli distribution with probabilities in ACF We calculate the similarity loss in Eq. (2) as:
d(G,G d AA ) B 2xdxx dx,
(3)

---

where d and dx are metrics to measure the distance between two graphs w.r.t. their graph structures and node features, respectively. 3 controls the weight for the similarity loss w.r.t. node features. More details of model implementation are in Appendix B.
3.2 CLEAR: Improving the Causality in Counterfactual Explanations
To further incorporate the causality in the generated CFEs, most existing studies [4, 19, 20] leverage certain prior knowledge (e.g.. given path diagram which depicts the causal relations among variables) of the SCM. However, it is often difficult to obtain sufficient prior knowledge of the SCM in real-world data, especially for graph data. In this work, we do not assume the access of the prior knowledge of SCM, and only assume that the observational data is available. However, the key challenge, as shown in [19], is that it is impossible to identify the ground-truth SCM from observational data without additional assumptions w.r.t. the structural equations and the exogenous variables, because different SCMs may result in the same observed data distribution. Considering that different SCMs can generate different counterfactuals, the identifiability of SCM is an obstacle of promoting causality in CFE. Fortunately, enlightened by recent progress in nonlinear independent component analysis (ICA) [14, 21], we make an initial exploration to promote causality in CFE by improving the identifiability of the latent variables in our CFE generator with the help of an auxiliary observed variable. This CFE generator is denoted by CLEAR.
In nonlinear independent component amalysis (ICA) [14, 21, 22, 23], it is assumed that the observed data, c.g., X, is generated from a smooth and invertible nonlinear transformation of independent latent variables (referred to as sources) Z. Identifying the sources and the transformation are the key goals in nonlinear ICA. Similarly, traditional VAE models also assume that the observed features X are generated by set of latent variables Z. However, traditional VAEs cannot be directly used for nonlinear ICA as they lack identifiability. i.e., we can find different Z that lead to the same observed data distribution p.X). Recent studies [14] have shown that the identifiability of VAE models can be improved with an auxiliary observed variable S (e.g.. a time index or class label), which enables us to use VAE for nonlinear ICA problem. As discussed in [22, 23), a SCM can be considered as a nonlinear ICA model if the exogenous variables in the SCM are considered as the sources in nonlinear ICA. Similar connections can be built between the structural equations in SCM and the transformations in ICA. Such connections shed a light on improving the identifiability of the underlying SCM without much explicit prior knowledge of the SCM.
With this idea, based on the backbone CLEAR- VAE, CLEAR improves the causality in counterfactuals by promoting identifiability with an observed auxiliary variable S. Intuitively, we expect the graph VAE can capture the exogenous variables of the SCM in its representations Z, and approximate the data generation process from the exogenous variables to the observed data, which consistent with the SCM. Here, for each graph, the auxiliary variable S can provide additional information for CLEAR to better identify the exogenous variables in the SCM, and thus can elicit counterfactuals with better causality. To achieve this goal, following the previous work of nonlinear ICA [14, 21], we make the following assumption:
Assumption 1. We assume that the prior on the latent variubles P(Z[S) is conditionally factorial.
With this assumption, the original data can be stratified by different values of S, and each separated data stratum can be considered to be generated by the ground-trute -tuth SCM under certain constraints (e.g., the range of values that the exogenous variables can take). When the constraints become more restricted, the space of possible SCMs that can generate the same data distribution in each data stratum shrinks. In this way, the identification of the trouhd-truth SCM can be easier if we leverage the auxiliary variable S. Here, with the auxiliary variable S, we infer the ELBO of CLEAR:
Theorem 1. The evidence lower bound (ELBO) to optimize the framework CLEAR is:
In PP "S,Y", G) 2 P IZ,S,Y" G)] the detailed proof is shown in Appendix A.
(4)
Loss function of CLEAR. Based on the above ELBO, the final loss function of CLEAR is:
L = Egld(G, GCT) + a ((f(GC())) Y*) +
(5)
Encoder and Decoder. The encoder takes the input G, S, and Y and outputs Z as the latent representation. We use Gaussian prior P S,
S, Y*) (N Y*), di Y)) with its
5

---

mean and diagonal covariance learned by neural network, and we encourage the learned approximate posterior QZZG, SY approach the prior by minimizing their KL divergence. Similar to the backbone -LEAR-VAE, the decoder takes the inputs Z and Y* to generate one or multiple counterfactuals GCF for each explainee graph. More implementation details are in Appendix B.
4 Experiment
In this section, we evaluate our framework CLEAR with extensive experiments on both synthetic and real-world graphs. In particular, we answer the following research questions in our experiments: RQ1: How does CLEARR perform compared to state-of-the-art baselines? RQ2: How do different components in CLEAR contribute to the performance? RQ3: How can the generated CFEs promote model explainability? RQ4: How does CLEAR perform under different settings of hyperparameters?
4.1 Baselines
We use the following baselines for comparison: 1) Random: For each explainee graph, it randomly perturbs the graph structure for at most T steps. Stop if desired predicted label is achieved. 2) EG-IST: For each explainee graph, randomly inserts edges into it for at most steps. 3) EG-RM: For each explainee graph, it randomly removes edges for at most T steps. 4) GNNExplainer: GNNExplainer [12] is proposed to identify the most important subgraphs for prediction. We apply it for CFE generation by removing the important subgraphs identified by GNNExplainer. 5) CF- GNNExplainer: CF- GF-ENNxxxll [9] is proposed for generating counterfactual ego networks in node classification tasks. We adapt CF- CF-GNNExplainer for graph classification by taking the whole graph (instead of the ego network of any specific node) as input, and optimizing the model until the graph classification (instead of node classification) label has been changed to the desired one. 6) MEG: MEG [6] is a reinforcement learning based CFE generation method. In all the experiments, we set T 150. More details of the baseline setup can be referred in Appendix B.
4.2
Datasets
We evaluate our method on three datasets, including a synthetic dataset and two datasets with real- world graphs. (1) Community. This dataset contains synthetic graphs generated by the Frdös-Rénye (E-R) model [24]. In this dataset, each graph consists of two 10-node communities. The label Y is determined by the average node degree in the first community (denoted by deg, (A)). According to the causal model (in Appendix B), when deg, (A) increases (decreases), the average node degree in the second community deg, (4) should decrease (increase) correspondingly. We take this causal relation deg;(A) + degg(A) as our causal relation of interest, and denote it R. Correspondingly, we define causal constraint for later evaluation of causality: "(deg, (ACF) ) > deg, (A)) = (ACF) deg2(A)) OR "(deg, (ACF)- deg, (A)) = (ACC) > deg, (4))" (2) Ogbg-molhiv. In this dataset, each graph stands for molecule, where each node represents an atom, and each edge is a chemical bond. As the ground-truth causal model is unavailable, we simulate the label Y and causal relation of interest R. (3) IMDB-M. This dataset contains movie collaboration networks from IMDB, In each graph, each node represents an actor or an actress, and each edge represents the collaboration between two actors actresses in the same movie. Similarly as the above datasets, we simulate the label Y and causal relation of interest R, and define causal constraints corresponding to R. is worth mentioning that the causal relation of interest R in the three datasets covers different types of causal relations respectively: i) causal relations between variables in node features X; iii) between variables in A and in X. Thereby we comprehensively evaluate the performance of CLEAR in leveraging different modalities (node features and graph structure) of graphs to fit in different types of causal relations. More details about datasets are in Appendix B.
graph structure A; ii) between variables
4.3 Evaluation Metrics
Validity: the proportion of counterfactuals which obtain the desired labels.
Σ EENM NOF Σ Exeweey ( = =b Validity = N
1
(6)
where N is the number of graph instances, NCF,', is the number of counterfactuals generated for each graph. GCF CP
(t,))* A (t.j)) denotes the j-th counterfactual generated for the i-th graph instance.
(b.5) Here, yf is the realization of Y for the i-th graph. 1(-) is an indicator function which outputs 1 when the input condition is true, otherwise it outputs 0.

---

Table 1: The performance (mean + standard deviation ten repeated executions) of different methods of CFEs on graphs. The best results are in bold, and the runner-up results are underlined.
Datasets
Methods
Validity (t)
Proximity (()
Prosimity (1)
Causlity (1)
Time (
Kandom
= 0.05
NIA
0.77 0.02
0.52 0.06
0.20 0.20::0.000
EG-IST
0.53 + 0.05
N/A
0.06 = 0.03
0.13 0.06
0.27 0.03
EG-RMV
U.53 = 0.04
N/A
0.85 + 0.01
0.03 0.02
0.01
Community
GNNEsplainer
0.52 1 0.06
NIA
0.71 0.01
0.05 0.00
2.87 0.008
CI-ONNExplaine
0.90 + 0.04
N/A
0.72 = 0.00
0.14
25.14
MEG
0.88 1 0.04
NIA
0.71 0.01
0.10
27.29 1.32
CIEARiours)
0.94 0.02 0.02
0.91 + 0.01
0.77 + 0.00
0.03 0.65
0.03
0.01 0.001
Kandom
0.48 0.09
N/A
0.87 0.02
0.46
0.07
EG-IST
0.18 + 0.09
N/A
0.83 = 0.03
0.46
0.19
EG-RM
0.483
N/A
0.96 0.01
0.09
0.17 0.004
Ogbg-molliv
GNNExplainer
0.50 = 0.01
N/A
0.92 = 0.00
2.78 0..10
CF-CiNNEsplainr
N/A
0.92
0.00
27.93
MEG
0.49 0.03
N/A
0.93 + 0.01
0.50 0.10
22.39 1 2.20
CLEARiours)
0.98 0.01
0.02
0.95
0.64 0.02
0.01
Raniom
0.50 0.04
N/A
0.67 0.01
0.43 0.08
0
EG-IST
U.56 0.12
N/A
0.67 + 0.06
1.07
EG RM
0.45 0.11
NEA
0.75 - 0.03
0.53 1.31..005
0.18 0.002
IMDB-M
GNNExplainer
0.43 0.10
N/A
0.62 = 0.02
0.50
2.46 0.50
CF-GNNExplainer
0.02
N/A
0.74
0.00
22.21
MEG
U.90 + 0.02
N/A
0.72 = 0.02
0.51 0.00
24.12 + 1.08
CLEAR(our))
0.96 + 0.01
+ 0.00
0.75
0.73
0.01 0.00
Proximity: the similarity between the generated counterfactuals and the input graph. Specifically, we separately evaluate the proximity w.r.t. node features and graph structure, respectively.
Proximity
1 N
Σ NCF [
Σ
simx(X
X (1.)). Proximity A= N [E|M] SE(NCF]
Σ
sim (A (0) (1.)):
CF
NCF
SE(NCF]
where we use cosine similarity for simx (+), and accuracy for s
As it is difficult to obtain the true SCMs for worldworld data, we focus on the causal relation of interest R mentioned in dataset description. Similarly as [4], we measure the causality by reporting the ratio of counterfactuals which satisfy the causal constraints corresponding to R.
Causality:
Time: the average time cost (seconds) of generating a counterfactual for a single graph instance.
4.4 Setup
We set the desired label Y* for each graph as its flipped label (e.g.. if then Y 1). For each graph, we generate three counterfactuals for it (NCF = 3). Other setup details are in Appendix B.
4.5 RQ1: Performance of Different Methods
To evaluate framework CLEAR, compare its CFE generation performance against the state- of-the-art baselines. From the results in Table 1, we summarize the main observations as follows: 1) Validity and proximity. Our framework CLEAR achieves good performance in validity and proximity. This observation validates the effectiveness of our method in achieving the basic target of CFE generation. a) In validity, CLEAR obviously outperforms all baselines on most datasets. Random, EG-IST, and EG-RM perform the worst due their random nature; GNNExplainer can only remove edges and nodes, which also limits its validity: NF-GNNExxllaier and MEG perform well as their optimization is designed for CFE generation; b) In Proximity A. CLEAR outperforms all non-random baselines. EG-RM performs the best in Proximity, because most graphs are very sparse, thus only removing edges can change the graph relatively less than other methods. As the baselines either cannot perturb node features, their perturbation approach on node features cannot fit well in our setting, we do not compare Proximity with them. 2) Time. CLEAR significantly outperforms all baselines in time efficiency. Most of the baselines generate CFEs in an iterative way. and MEG needs to enumerate all perturbations at each step. GNNExplainer and ET-GGNNEpla optimize on every single instance, which limits their generalization. All the above reasons erode their time efficiency. While our framework. the generative mechanism enables efficient CFE generation and generalization on unseen graphs, thus brings substantial improvement in time efficiency. 3) Causality. CLEAR dramatically outperforms all baselines in causality. We contribute the superiority of framework w.r.t causality in two key factors: a) different from some basclines (c.g., GNNExplainer) optimized each single graph, our framework can better capture the causal relations among different
7

---

1,4
.NC
-PX
1.4
.NC
.AA CLEAR
Performance
-NPA
-NP
CLEAR
Performance
1.2
-NPA
.NP
1.0
1.0
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
Validity
Proximity'
Proximity
Causality
0.0
Validity
Proximity
Proximitya
Causality
(a) Community
(b) Oghg-molhiv
Figure Ablation studies.
degree of com community
4.
8
degree community
4.
degree of community
4.
8
6
degree of community
degree of community 1
degree of community
(a) Original data
(b) CFEs from CLEAR-VAL VAE
(c) CFEs from CLEAR
Figure 5: Explainability through CFEs Community.
variables in data by leveraging the data distribution of the training set; b) our framework utilizes the auxiliary variable to better identify the underlying causal model and promote causality.
4.6 RQ2: Ablation Study
To evaluate the effectiveness of different components in CLEAR, we conduct ablation study with the following variants: 1) CLEAR-NC. In this variant, we remove the counterfactual prediction loss; 2) CLEAR-NPA, we remove the similarity loss w.r.t. graph structure; 3) CLEAR-NPX, we remove the similarity loss w.r.t. node features; 4) CLEAR-NP, we remove all the similarity loss; 5) CLEAR-VAL VAE, the backbone our framework. As shown in Fig. 4, we have the following observations: 1) The validity of CLEAR-NC degrades dramatically due to the lack of counterfactual prediction loss; 2) The performance w.r.t proximity is worse in CLEAR-NPA, CLEAR-NPX, and CLEAR-NP as the similarity loss is removed. Besides, removing the similarity loss can also hurt the performance of causality when the variables the causal relation of interest R are involved. For example, in Community, CLEAR-NPA performs much worse in causality (as R in Community involves node degree in graph structure), while in Ogbg-molhiv, the performance in causality of CLEAR-NPX is eroded (as R on Ogbg-molhiv involves node features): 3) The performance w.r.. causality is impeded in ELEAR-VAE, This observation validates the effectiveness of the auxiliary variable for promoting causality. Similar observations can also be found in the ablation study on the IMDB-M dataset, which is shown in Appendix C.
4.7 RQ3: Explainability through CFEs
To investigate how CFE on graphs promote model explainability, we take a closer look in the generated counterfactuals. Due to the space limit, we only show our investigation on the Community dataset. Fig. 5(a) shows the distribution of two variables: the average node degree in the first community and in the second community in the original dataset, i.e., deg, ; (A) and deg (A). Fig. 5(b) shows the distribution of these two variables in counterfactuals generated by CLEAR-VAL VAE. We observe that these counterfactuals are distributed close to the decision boundary, i.e., deg (A) = ADG,, where ADG is constant around 2. This is because that the counterfactuals are enforced to change their predicted labels with perturbation as slight as possible. Fig. 5(c) shows the distribution of these two variables deg, ( (A) and deg, (A) in counterfactuals generated by CLEAR. Different colors denote different values of the auxiliary variable S. Notice that based on the causal model (in Appendix B). the exogenous variables are distributed in a narrow range when the value of S is fixed, thus the same color also indicates similar values of exogenous variables. We observe that compared with the

---

1.0
1.0
1.00
0.9
1.0
0.8
Validity
0.8
Toxiimyy
Validity
0.6
Proximityy
0.75
Validity Proximityx
0.7
0.5
Validity
0.4
0.6
0.50
Proximityx
0.2
0.5
0.01
0.1
L.
5.0
10.0
0.01
0.1
1.0
10.0
100
0.0
a
B
Figure 6: Parameter studies Ogbg-molhiv.
color distribution in Fig. 5(b), the color distribution in Fig. 5(c) is more consistent with Fig. 5(a). This indicates that compared with CLEAR- VAE, CLEAR can better capture the values of exogenous variables, and thus the counterfactuals generated by CLEAR are more consistent with the underlying causal model. To better illustrate the explainability provided by CFE, further conduct case studies to compare the original graphs and their counterfactuals in Appendix C.
4.8
RQ4: Parameter Study
To evaluate the robustness of our method, we test the model performance under different settings of hyperparameters. We vary a E {0.01, 0.1, 1.0, 5.0, 10.0} and {0.01, 0.1, 1.0, 10.0, 100}. Due to the space limit, we only show the parameter study on Ogbg-molhiy, but similar observations can be found in other datasets. As shown in Fig. 6, the selection of and 3 controls the tradeoff between different goals in the objective function. But generally speaking, the proposed framework is not very sensitive to the hyparameter setting. More studies regarding other parameters in Appendix C.
Related Work
Counterfactual explanations on tabular data. Counterfactual explanations have attracted increasing attentions [2, 3, 5, 25J. Especially, recent works also consider more aspects CFEs, such as actionability [26, 27], sparsity [28, 29, 30], data manifold closeness [31, 32], diversity [29, 33],
feasibility [4, 27], causality [4, 19, 20]. and amortized inference [4]. These methods include model- agnostic (27, 30, 32] methods and model-accessible [2, 25] methods. Recently, a few studies [4, 10] develop generative CFE generators based variational autoencoder. However, most of current CFE approaches only focus on tabular or image datasets, and can not be directly grafted for the graph data.
Counterfactual explanations on graphs. There have been a few studies related to CFEs on graphs [6, 9, 10, 11, 12, 13]. Among them, GNNExplainer [12] identifies subgraphs which important for graph neural network (GNN) model prediction [34, 35, 36, 37, 38, 39, 40). It can be adapted generate counterfactuals by perturbing the identified important subgraphs. Similarly, RCExplainer [10] generates CFEs by removing important edges from the original graph, but is based on an assumption that GNN prediction model is partially accessible. CNxGNNExpe [9] studies counterfactual explanations for GNN models in node classification tasks. Besides, few domain-speciff methods [6, 11] are particularly designed for certain domains such as chemistry and brain diagnosis. However, all the above methods either limited in specific setting (e.g., the prediction model is accessible), or heavily based on domain knowledge. Many general and important issues in model-agnostic CFE generation on graphs still lack exploration.
Graph generative models. Many efforts [16, 41, 42, 43] have been made in graph generative models recently. Among them, Graph [16] develops VAE-based mechanism to generate graphs from continuous embeddings. GraphRNN [41] is autoregressive generative model for graphs. generates graphs by decomposing the graph generation process into a sequence of node and edge formations. Furthermore, a surge of domain-specific graph generative models [44, 45, 46) are developed with domain knowledge incorporated. Although different from CFE methods in their goals, graph generative models can serve as the cornerstone of our work for CFE generation on graphs. Our framework can be compatible with techniques in different graph generative models.
6 Conclusion
In this paper, we study an important problem of counterfactual explanations on graphs. More specifically, we aim to facilitate the optimization, generalization, and causality in CFE generation

---

on graphs. To address this problem, we propose novel framework CLEAR, which uses graph variational autoencoder mechanism enable efficient optimization in graph data, and generalization to unseen graphs. Furthermore, we promote the causality in counterfactuals by improving the model identifiability with the help of auxiliary observed variable. Extensive experiments validate the superiority of the proposed framework in different aspects. the future, more properties of the counterfactuals in graphs, such as diversity, data manifold closeness can be considered. Besides, incorporating different amount and types of prior knowledge regarding the causal models into CFE generation on graphs is also an interesting direction.
conducted to
Acknowledgements
This work is supported by the National Science Foundation under grants IIS-2006844, IIS-2144209 IIS-2223769, IIS-2106913, IIS IIS-2008208, 115-1955151, CNS-2154962, SCS-22288334 the JP Morgan Chase Faculty Research Award, the Cisco Faculty Research Award, and the 3 Cavaliers seed grant. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies.
References
[1] Pantelis Linardatos, Vasilis Papastefanopoulos, and Sotiris Kotsiantis. Explainable ai: review of machine learning interpretability methods. Entropy. 2020.
[2] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harv. JI. & Tech., 2017.
[3] Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv preprint, 2020.
[4] Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints counterfactual explanations for machine learning classifiers. arXiv preprint, 2019.
[5] Saumitra Mishra, Sanghamitra Dutta, Jason Long, and Daniele Magazzeni. A survey on the robustness of feature importance and counterfactual explanations. arXiv preprint, 2021.
[6] Danilo Numeroso and Davide Bacciu. Meg: Generating molecular counterfactual explanations for deep graph networks. arXiv preprins, 2021.
[7] Hans-Georg Wolff and Klaus Moser. Effects of networking on career success: a longitudinal study. Journal of applied psychology, 94(1): 2009.
[8] Predict grant applications. https:
[9] Ana Lucic, Maartje ter Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cf- Cf-gnnexplainer: Counterfactual explanations for graph neural networks. arXiv preprint, 2021.
[10] Mohit Bajaj. Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang. Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. NeurlPS, 2021.
[11] Carlo Abrate and Francesco Bonchi. Counterfactual graphs for explainable classification of brain networks. arXiv preprint, 2021.
[12] Rex Ying, Dylan Bourgeois. Jiaxuan You, Marinka Zitnik, and Jure Leskovee. Gnnexplainer: Generating explanations for graph neural networks. NeurlPS, 2019.
[13] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Explainability in graph neural networks:
A taxonomic survey. arXiv preprint, 2020.
[14] Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. Variational autoen- coders and nonlinear ica: A unifying framework. In AISTATS. 2020.
[15] Judea Pearl. Causality. 2009.
[16] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In ICANN, 2018.
[17] Diederik Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint, 2013.
[18] Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning model-agnostic counter- factual explanations for tabular data. In WWW, 2020.
10

---

[19] Amir-Hossein Karimi, Julius Von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algo- rithmic recourse under imperfect causal knowledge: a probabilistic approach. arXiv preprint. 2020.
[20] Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. In ACM FAccT, 2021.
[21] Aapo Hyvarinen. Hiroaki Sasaki, and Richard Turner. Nonlinear ica using auxiliary variables and generalized contrastive learning. In AISTATS, 2019.
[22] Shohei Shimizu, Patrik O Hoyer, Aapo Hyvärinen, Antti Kerminen, and Michael Jordan. A linear non-gen gou-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 2006.
[23] Ricardo Pio Monti, Kun Zhang, and Aapo Hyvärinen. Causal discovery with general non-linear relationships using non-linear ica. In Uncertainty in Artificial Intelligence, 2020.
[24] P Erdōs and A Rényi. On random graphs i. publicationes mathematicae (debrecen). 1959.
[25] Gabriele Tolomei, Fabrizio Silvestri, Andrew Haines, and Mounia Lalmas. Interpretable predictions of tree-based ensembles via actionable feature tweaking. In SIGKDD, 2017.
[26] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In ACM FAccT, 2019.
[27] Rafael Poyiadzi, Kacper Sokol, Raul Suntos-Rodriguee Tijl De Bie, and Peter Flach. Face: Feasible and actionable counterfactual explanations. In AIES, 2020.
[28] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri. Dino Pedreschi. Franco Turini, and Fosca Giannotti. Local rule-based explanations black box decision systems. arXiv preprint, 2018.
[29] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In ACM FAccT, 2020.
[30] Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counter- factual explanations. PPSN, 2020.
[31] Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. arXiv preprint, 2018.
[32] Amit Dhurandhar, Tejaswini Pedapati, Avinash Balakrishnan, Pin- Yu Chen, Karthikeyan Shan- mugam, and Ruchir Puri. Model agnostic contrastive explanations for structured data. arXiv preprint, 2019.
[33] Chris Russell. Efficient search for diverse coherent explanations. In ACM FAccT, 2019.
[34] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
[35] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018
[36] Thomas N Kipf and Max Welling. Variational graph auto-encoders. NeurIPS Workshop on Bayesian Deep Learning, 2016.
[37] Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu. Sub-graph contrast for scalable self self-supervised graph representation learning. IEEE ICDM, 2020.
[38] Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets. In
AAAI, 2018
[39] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[40] William I. Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 2020.
[41] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrun: Generat- ing realistic graphs with deep auto-regressive models. In ICML, 2018
[42] Aditya Grover, Aaron Zwcig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In ICML, 2019.

---

[43] Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey. arXiv preprint, 2022.
[44] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint, 2018.
[45] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In ICML, 2018.
[46] Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Gunter Klambauer. Fréchet chemnet distance: a metric for generative models for molecules in drug discovery. Journal of chemical information and modeling, 2018.
[47] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 2018.
[48] Greg Landrum al. Rdkit: Open-source cheminformatics. 2006.
[49] Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National (LANN,,,,, Los Alamos, NM (United States), 2008.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
(b) Did you describe the limitations of your work? [Yes] See Appendix D.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Appendix D.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
3.2 and Appendix A.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] In the submitted supplementary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4, Appendix B and C.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] All the experimental results are provided with error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix B.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix B.
(b) Did you mention the license of the assets? [Yes] See Appendix B.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] The source code of our proposed framework is included in the supplemental material.
will released after publication.
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A] The creators developed the adopted datasets based on either publicly available data or data with proper consent.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We use well-known public datasets in this paper, and they do not contain personally identifiable information or offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "qe2t1c6rW1", "reviewer": "Reviewer_xuuN", "summary": "The paper presents a framework CLEAR to generate counterfactual explanations on graphs. This framework can be helpful for promoting explainability in graph-based prediction models. Specifically, the authors use a graph variational autoencoder to generate the counterfactual graph and employ independent component analysis (ICA) to find causal relations. The generative counterfactual graphs have generalization ability and causality. Experiments show that CLEAR achieves promising performance in various evaluation metrics.", "questions": "1. The merits of ICA over the existing methods in identifying causality should be highlighted.\n2. One important metric for explanations is human interpretability requiring the generated explanations should be compact. The authors should investigate human interpretability.\n3. Counterfactual explanations can be used to defend against attackers. The authors are encouraged to conduct experiments on graphs generated by the adversarial attacks to verify the effectiveness of generated counterfactual explanations.\n4. The experiments can not well support the claimed contribution in generalization. How to evaluate the generalization ability on unseen graphs? The work lacks the evaluation of generalization on unseen graphs.\n", "limitations": "There are no potential negative societal impacts.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The paper employs two existing technologies, i.e., graph variational auto-encoder and ICA to generate the counterfactual graph. Although the two components are not new, the topic is novel. One of the contributions, optimization, is not original. Many works have employed various models to generate graphs by gradient-based optimization instead of enumeration, such as GNNExplainer, [1], and [2]. Existing works have proposed many methods, such as information flow [1] and Markov blanket [2], to identify causality among latent variables. What’s the merit of ICA over these existing methods? \n\nQuality: Technically sound with well-supported claims.  However, the following issues are suggested to be further considered: 1. The evaluation metrics are not sufficient. One important metric for explanations is human interpretability requiring the generated explanations should be compact. The authors should investigate human interpretability. 2. In addition, counterfactual explanations may be used to defend against attackers. The authors are encouraged to conduct experiments on graphs generated by the adversarial attacks to verify the effectiveness of generated counterfactual explanations. 3. The work lacks the evaluation of generalization on the unseen graph.\n\nClarity: Overall, the paper is well written and easy to understand. However, the following issues need to be clarified. 1. The motivation behind employing ICA to find causality is not clear. 2. Why the team culture is not the cause of grant application in the example of the Preliminaries Section? 3. The grant application example for describing causality in counterfactual explanations is confusing. It is advisable to describe it in mathematical form.\n\nSignificance: The method proposed in this paper would be helpful to give counterfactual explanations and promote explainability in graph-based data.\n\n[1] Lin, Wanyu, et al. \"Orphicx: A causality-inspired latent variable model for interpreting graph neural networks.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.\n\n[2] Yang, Shuai, et al. \"Learning causal representations for robust domain adaptation.\" IEEE Transactions on Knowledge and Data Engineering, 2021.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "p3baE5u-zGw", "reviewer": "Reviewer_Htsg", "summary": "In this work, the authors study the problem of generating counterfactual explanations for graphs using Graph Neural Networks (GNN). In contrast to some existing studies, the work lists three unaddressed counterfactual properties, i.e., i) discrete optimization of graphs, ii) generalization of counterfactuals on unseen graphs, and iii) ensuring causality in the generated counterfactuals without prior knowledge of the causal model. The work leverages a graph variational autoencoder-based framework to propose CLEAR (generative CounterfactuaL ExplAnation geneRator for graphs) that ensures the optimization and generalization of discrete counterfactual explanations for graphs and enforces causality by using an auxiliary variable for estimating the underlying causal model better.", "questions": "Please refer to the Strengths and Weaknesses section for questions.", "limitations": "Yes.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper nicely enumerates three important desiderata for counterfactual explanation generators for graphs and describes their utilities with respect to counterfactual explanations.\n2. The formulation of the objective for the CLEAR framework is clearly explained with proper derivations and descriptions of the individual components.\n3. Extensive experiments with both synthetic and real-world graph datasets highlight the effectiveness of the CLEAR framework as compared to the baselines and show the utility of its components.\n\nWeaknesses and Questions:\n1. One of the major drawbacks of the work is that they don't detail the perturbation mechanism used for generating counterfactuals. They mention that: \"CLEAR aims to generate counterfactuals with slight perturbations on the explainee graph to elicit a desired predicted label\" but does not describe the perturbation process. This is crucial for understanding the framework as one of the main challenges in evaluating the reliability of generated counterfactual explanations is efficiently perturbing the input data. The perturbation process for generating similar graphs using very small perturbation is unclear, i.e., how to generate perturbed instances that are not out-of-distribution samples. \n\n2. It is unclear from Section 4.7 and Appendix C.2 how the generated counterfactuals using CLEAR promote model explainability. The observation that the framework makes correct perturbation to achieve the target label by visualizing the degrees across the decision boundary is intuitive and shown in multiple previous works.\n\n3. The proposed CLEAR framework uses a generative backbone CLEAR-VAE and claims that it can generate counterfactual explanations for unseen graphs. However, it should still require graphs to belong to the same distribution as the training data.\n\n4. The paper details the problem of optimizing counterfactual explanation on graphs due to its discrete nature but then follows the optimization trick used by previous works for generating a counterfactual adjacency matrix.\n\n5. The use of GNNExplainer as a baseline is unclear. The author assigns the given graph label to all the nodes inside the graph. It would be great if the authors explain this a bit more. Are they assigning the same label to all nodes and then generating explanations for a given node? Or are they aggregating all node explanations to generate a graph-level explanation?\n\n6. It would be great if the authors can motivate using causality metric for comparison. It feels that the metric is biased towards the proposed framework as the auxiliary variable can provide additional information to identify the exogenous variables in the structural causal model, which is captured by the CLEAR-VAE training process.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LTOqVZE7qJD", "reviewer": "Reviewer_SccR", "summary": "The authors present a counterfactual generation method for graphs. The proposed method (CLEAR) aims to perturb a given graph in a way that is still close to the original while changing a classifier prediction and respecting the causality in the data generating process. This is achieved by training a graph VAE conditioned on the target label and an auxiliary variable $S$ used by the original data generating process (an SCM), which helps to identify the causal model. The overall loss encourages counterfactuals to be close (wrt a distance metric) to the original graph while achieving the desired label ($Y^*$) and inferring the correct latent structure by keeping the latent codes $Z$ close to a distribution that is conditioned on $S$ and $Y^*$. In experiments they show that the proposed method achieves a higher number of valid counterfactuals that are more proximal while keeping causal relations than previous state of the art. They also provide an ablation study on the different parts of their model.", "questions": "* Could you better motivate the counterfactual explanation problem in the introduction and the abstract? The idea is that the reader gets the \"big picture\" before you focus on the concrete problem of improving graph counterfactual methods.\n* Could you verify whether your model is or not producing the same counterfactual 3 times? (if it does it is ok, but I think this is important information for the reader to have)\n* Could you clarify what causality you want to preserve? (see clarity above)\n* Why did you skip 0.1 in the hyperparameter sweep? (see above)", "limitations": "Yes, the authors include a section in the appendix.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall Review\n===========\nOverall, this paper tackles an important problem, the method is sound, and the results are encouraging. Some points could be improved, such as motivating the need of graph counterfactuals, or checking whether the model is repeating the same counterfactual three times. Therefore I recommend \"Weak Accept\" and I would be happy to raise the score based on the rebuttal and the other reviews.\n\nStrengths\n=======\n* The problem of understanding the behavior of ML systems is an important one.\n* The proposed method is sound and it performs better compared to previous state of the art.\n* The authors provide the code, ablations, and information for reproducibility.\n\nWeaknesses\n=========\n* This work focuses strongly on the method and comparison with previous state of the art but it lacks a bit of perspective on what is the final purpose of this research. Some more motivation in the introduction and some qualitative results showing interesting findings on a real graph would make this work more appealing. I like the example in Section 2, so you can focus more on motivating the problem in general rather than giving more examples in the introduction.\n* In the ablation study there is no clear difference between VAE and CLEAR. (The difference is, however, more clear on Figure 4).\n* Since the proposed method predicts 3 counterfactuals, it could just predict three times the same (or very similar) graph. This would improve the validity metric while not adding any additional value to the user. Several recent works focus on providing a set of diverse [28, A, B] and non-trivial explanations [C] (unexpected failure modes of the model), that are more useful for the end user. In fact, in Appendix D, the authors acknowledge that optimizing for diversity is a current limitation, but it would be interesting to study whether the VAE is repeating the same graph or producing different graphs. \n\n[28] Mothilal, Ramaravind K., Amit Sharma, and Chenhao Tan. \"Explaining machine learning classifiers through diverse counterfactual explanations.\" Proceedings of the 2020 conference on fairness, accountability, and transparency. 2020.\n\n[A] Smyth, Barry, and Mark T. Keane. \"A Few Good Counterfactuals: Generating Interpretable, Plausible and Diverse Counterfactual Explanations.\" arXiv preprint arXiv:2101.09056 (2021).\n\n[B] Hvilshøj, Frederik, Alexandros Iosifidis, and Ira Assent. \"On Quantitative Evaluations of Counterfactuals.\" arXiv preprint arXiv:2111.00177 (2021).\n\n[C] Rodríguez, Pau, et al. \"Beyond trivial counterfactual explanations with diverse valuable explanations.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021.\n\n\n\nDetailed comments\n===============\nOriginality\n-----------\nThe proposed framework, and particularly the focus on causality preservation when generating counterfactuals, are novel to the best of my knowledge.\n\nQuality\n--------\nThe technical and written quality are good, assumptions are clearly stated, and proofs are provided in the Appendix.\n\nClarity\n-------\nOverall, the text is well-written and easy to follow. In section 4.7 I believe that references to Figure 8 should be to Figure 4. In Section 4.8 it is not clear why you do not test $0.1$. Many times you talk about preserving causality and, without any context, it is not clear if you mean that you are reconstructing a causal graph (with directed edges) and you want to preserve edge directions, or if you want the generated graphs to be compatible with the original SCM. After some time reading it becomes clear but it would be better if you made it more clear since the beginning. \n\nSignificance\n--------------\nGiven the increasing impact of machine learning applications in our lives, it is important to better understand how models make their predictions. However, the text does not fully transmit the significance of this work. \n\nReproducibility\n-----------------\nThe authors provide code, equations, and the necessary assumptions to reproduce their results.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept