**Comment:**
**Thank you for the response and additional experiments conducted. Indeed, existing counterfactual GNN explanation works seem to leave edge insertion un-considered, despite extensive studies on perturbing edges to change prediction results in the adversarial attack area. However, I am still not totally convinced w.r.t the significance of this work. As mentioned in Weakness 2, the "inductive" part of this work, training a deep model to learn the perturbation of graphs, seems to be limited in novelty. It follows the framework of existing "model-based" explainer, like PGExplainer.**

**I would like to raise my score to weak reject, as my concern w.r.t the novelty and contribution of this work persists.**

*Response:*

First, we thank the reviewer for engaging with us and raising our rating to Weak Reject.

In this respose, we comprehensively establish how our work bears negligible resemblance to PGExplainer across the entire spectrum of problem formulation, methodology, and the consequent impact on empirical performance. Please do let us know if there are any additional clarifications that we can offer. **If no further concerns remain, we appeal to the reviewer to kindly consider increasing the rating of our work if that's indeed the case.**

* **Problem Formulation:** PGExplainer is an inductive factual explainer whereas InduCE is an inductive counterfactual explainer. In a factual explainer, the goal is to find the smallest subgraph of a graph, such that this subgraph is enough for the GNN to predict the label of the input graph. Counter-factual explanation, on the other hand, seeks to introduce the minimal perturbations to the input graph, so that the GNN prediction changes.

* **Methodology:** Owing to the fundamental difference in the problem itself, **while graph perturbation with the intent to change the GNN's prediction is the core objective in InduCE, this very concept does not exist in PGExplainer** (or in any factual explainers). Hence, there exists no similarity in the methodologies.
* PGExplainer learns approximated discrete masks for edges to explain the black-box GNN  predictions. These edge masks are learned by training a parameterized mask predictor. For a given input graph, it first learns node representations, then obtains edge representations by concatenating respective node embeddings.  The predictor uses these edge embeddings to predict an importance score for each edge. Then the approximated discrete masks are sampled via the re-parameterization trick. Finally the mask predictor is trained to maximize the mutual information between the original predictions and new predictions.
* InduCE uses a completely different algorithm that does not use masks anywhere in the algorithm. InduCE is based on reinforcement learning, where it creates an augmented state space of features, degree, entropy and one-hot encoded labels for a node. We pass this state to the policy network to generate a probability distribution over the action space. Here the action space correspond to possible edge edits. An action is then sampled, the respective edit is made and the marginal reward is computed. This is done till a maximum budget is exhausted or a valid counterfactual is formed, i.e., the label of the node flips. We train the policy to favour actions that maximize the expected reward. Our reward is formulated to prefer edits that minimally perturb the graph while minimizing the likelihood of the label. This is done so that the label flips, and the counterfactual size remains small.
* **Empirical Performance:** In order to further solidify our claims, we report the comparison of InduCE-inductive with PGExplainer. To adopt PG-explainer for counter-factual analysis, as standard in the literature, we remove the factual explanation from the input graph. As visible below, PG-explainer is not at all competitive.

Results:
### Treecycles
| Method           | Fidelity (%) ↓  | Size ↓  | Accuracy (%) ↑ |
|------------------|----------------------|--------------|---------------------|
| InduCE-inductive |                    0 | 2.31 +- 1.44 |               96.65 |
| GEM              |                   95 |            6 |               88.97 |
| PGExplainer      |                34.72 |            6 |               76.85 |

### Treegrids
| Method           | Fidelity (%) ↓  | Size ↓  | Accuracy (%) ↑ |
|------------------|----------------------|--------------|---------------------|
| InduCE-inductive |                    0 | 4.67 +- 2.91 |               91.05 |
| GEM              |                   97 |            6 |               94.57 |
| PGExplainer      |                41.09 |            6 |               66.93 |
### BAShapes
| Method           | Fidelity (%) ↓  | Size ↓  | Accuracy (%) ↑ |
|------------------|----------------------|--------------|---------------------|
| InduCE-inductive |                  2.6 | 4.37 +- 3.53 |               64.40 |
| GEM              |                   17 |            6 |               98.44 |
| PGExplainer      |                 6.58 |            6 |               89.25 |

We hope this addresses the issue with the novelty claims.

We hope this comprehensively establishes the differentiation with PGExplainer. The **novelty** of our work is therefore:

* First Counter-factual explanation algorithm over GNN to predict inductively and enable edge edits. This leads to significant improvement in performance over all baselines across a host of metrics.
* From an algorithmic standpoint, InduCE uses policy gradients to learn the optimal set of perturbations. This is the first use of policy gradients in the space of counter-factual explanation over GNNs.
* A formal proof establishing that counter-factual analysis is NP-hard.
* Comprehensive empirical evaluation over four baseline algorithms showcasing the superiority of InduCE in counter-factual GNN explanation.

[1] Yuan, H., Yu, H., Gui, S. and Ji, S., 2022. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence

[2] Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H. and Zhang, X., 2020. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33, pp.19620-19631.

[1] Yuan, H., Yu, H., Gui, S. and Ji, S., 2022. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence

[2] Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H. and Zhang, X., 2020. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33, pp.19620-19631.

**After reading the rebuttal, I believe the authors only partially address my concerns. For example, to evaluate the interpretation, there are some other metrics that are commonly used such as fidelity, stability, sparsity, coherence, coverage and etc. Only using the ground truth may not be sufficient to evaluate a good interpretation method. Thus I would like to maintain my score.**

*Response:*

* **Fidelity:** We humbly point out to the reviewer that **we have already reported** the metric fidelity across all our experiments (Tables 2,3,4,5,7,8,9,12,13).
* **Sparsity:** Please find below the sparsity values. As can be observed, like in other metrics, InduCE continues to outperform the baselines.

Transductive methods

| Dataset             | Tree Cycle | Tree Grid | BA-Shapes |
|---------------------|------------|--------------|--------------|
| InduCE-transductive |   **0.99** |     **0.99** |     **0.99** |
| CFGNNExplainer      |   0.93   |    0.95   |     **0.99** |
| CF^2                |  0.52      |    0.59      | 0.92         |

Inductive methods
| Dataset             | Tree Cycle | Tree Grid | BA-Shapes |
|---------------------|------------|-----------|-----------|
| InduCE-inductive    |     **0.90** |     **0.88** |     **0.99** |
| GEM                 |  0.54          |    0.77       |     0.88      |

* **Stability:** Stability is a metric for factual analysis **and not counter-factual explanation**. In fact, ***stability is the anti-thesis of counter-factual explanation***. Hence, neither is it applicable to our work, nor has it been used to explain any counter-factual explainer in the literature. Below we elaborate why.
Stability is defined as follows [5]:

> Given a node $u$ and its perturbation $u^{\prime}$ (i.e., we slightly perturb the neighorbodhood of $u$), an explanation $\mathbf{E}_u$ corresponding to node $u$ is said to be stable if: $$ \mathcal{D}\left(\mathbf{E}u, \mathbf{E}{u^{\prime}}\right) \leq \delta $$
> where $\mathbf{E}u^{\prime}$ is the explanation for $u^{\prime}$, $\mathcal{D}$ is a distance metric, $\delta$ is an infinitesimally small constant.

More simply, if two nodes have similar neighborhood topologies, their factual explanations should be similar. This is the anti-thesis of counter-factual explanation, since here our goal is to find the $u'$, i.e., a very small perturbation, such that their labels, and therefore explanations, are maximally different.

For counterfactual explanation $u^{\prime}$ the objective satisfied is $f(A_u + u^{\prime}) \neq f(A_u)$. Here, $A_u$ is the adjacency matrix of the k-hop neighbourhood of $u$ and $f$ is the black-box GNN. So basically, if we consider $A_u + u^{\prime}$ as the perturbed matrix, then the counterfactual explanation for $u$, now will be $A_u - u^{\prime}$, which semantically is adding back the deleted edges, and deleting the added edges.

* **Coherence and Coverage**: We have surveyed all well known papers on the topic of GNN explanability (GNNExplainer[4], our baselines[1,2,3] or survey papers [5,6,7].). We are unable to find any work using these metrics. Therefore, we request the reviewer to cite their definition and a source where they have been used to evaluate counter-factual explainer. We would gladly evaluate our method on the proposed metrics, if they are feasible for our setting.

We hope the additional empirical data and clarifications address all outstanding concerns. We would be happy to engage with the reviewer if any of the outlined limitations remain open. If not, we humbly appeal to the reviewer to consider raising our score.

[1] Lucic, A., Ter Hoeve, M.A., Tolomei, G., De Rijke, M. and Silvestri, F., 2022, May. Cf-GNNExplainer: Counterfactual explanations for graph neural networks. In International Conference on Artificial Intelligence and Statistics (pp. 4499-4511). PMLR.

[2] Tan, J., Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y. and Zhang, Y., 2022, April. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022 (pp. 1018-1027).

[3] Lin, W., Lan, H. and Li, B., 2021, July. Generative causal explanations for graph neural networks. In International Conference on Machine Learning (pp. 6666-6679). PMLR.

[4] Ying, Z., Bourgeois, D., You, J., Zitnik, M. and Leskovec, J., 2019. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32

[5] Agarwal, C., Zitnik, M. and Lakkaraju, H., 2022, May. Probing GNN explainers: A rigorous theoretical and empirical analysis of GNN explanation methods. In International Conference on Artificial Intelligence and Statistics (pp. 8969-8996). PMLR.

[6] Guo, Z., Xiao, T., Aggarwal, C., Liu, H. and Wang, S., 2023. Counterfactual Learning on Graphs: A Survey. arXiv preprint arXiv:2304.01391.Vancouver

[7] Yuan, H., Yu, H., Gui, S. and Ji, S., 2022. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence

-----------------------------------------------------

**Summary of key points in the rebuttal**

We thank all reviewers for the constructive feedback and suggestions. Please find a point-by-point response to how these suggestions have been addressed. The key revisions include:
1. **Scalability Experiments:** We have performed additional experiments to demonstrate scalability to million-scale graphs.
2. **Incorporation of additions on baselines:** We have conducted new experiments by extending the baselines with the ability to add edges. These new experiments demonstrate:
* The performance of the baselines deteriorate following this change.
* InduCE continues to outperform all baselines.
4. **Accuracy Vs. Size experiment:** We have conducted additional expeirment to analyze the relaitonship between accuracy of explanations with size. Our experiments reveal that, in general, as the explanation size increases, the accuracy drops.
5. **Clarifications:** We have clarified/addressed the various misunderstandings and presentation issues.

With these changes, we hope the reviewers will find our manuscript acceptable. We would be happy to engage further with the reviewers in case there are queries/suggestions to improve our work further.

**Rating: Reject**

**There is not a discussion of related works in this paper.**

*Response* We would like to humbly point to our Section 1 titled "Introduction and Related Work" (See Sec 1), where we discuss the related works. In this section, there is a specific subsection (**highlighted in bold**) called "Existing Works" that discusses the papers relevant to our work.

**Besides, authors claim that existing counterfactual explanation works can only remove edges, which may not be true.**

*Response:* We are not aware of any counter-factual explainer for node classification on graphs that can add edges. If the reviewer is aware of any such algorithm, we request the reviewer to cite it. We will be happy to include it in our work.

Nonetheless, we have conducted additional experiments by extending CF-GNNExplainer and CF^2 with edge additions. As visible in the table below, InduCE, continues to outperform the baselines. We note that when additions are allowed, for both baselines the performance deteriorates (more significantly for CF-GNNexplainer). While it is hard to pin-point the exact reason, we hypothesize this behavior is a consequence of the fact that the search space of graph edits dramatically increases when additions are allowed. The increase in search space makes the combinatorial modelling task of *learning* the right set of edits harder. InduCE does not suffer from this limitation, since its RL-based selection algorithm is built from the ground-up keeping additions in mind.

### Treecycles
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 49 | 1.05 +- 0.23 | 100 |
| CF-GNNExplainer (add + del)| 100 | Null | Null |
| CF^2 (del) | 0 | 7.33 +- 3.64 | 40.60 |
| CF^2 (add + del) | 13.89 | 28.34 +- 7.56 | 19.24 |
| InduCE-transductive | 0 | 1.01 +- 0.12 | 97.22 |
| InduCE-inductive | 0 | 2.31 +- 1.44 | 96.65 |

### Treegrids
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 10 | 1.37 +- 0.58 | 92.24 |
| CF-GNNExplainer (add + del)| 100 | Null | Null |
| CF^2 (del) | 0 | 11.74 +- 4.86 | 45.15 |
| CF^2 (add + del) | 28.68 | 12.90 +- 7.71 | 27.44 |
| InduCE-transductive | 0 | 1.01 +- 0.12 | 98.45 |
| InduCE-inductive | 0 | 4.67 +- 2.91 | 91.05 |

### BA-shapes
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 37 | 1.31 +- 0.55 | 95.83 |
| CF-GNNExplainer (add + del)| 38.16 | 6315.44 +- 9916.50 | 17.36 |
| CF^2 (del) | 0 | 3.79 +- 1.70 | 74.50 |
| CF^2 (add + del) | 100 | Null | Null |
| InduCE-transductive | 23.7 | 1.24 +- 1.02 | 98.4 |
| InduCE-inductive | 2.6 | 4.37 +- 3.53 | 64.4 |

### Amazon-photos
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 100 | Null | NA |
| CF-GNNExplainer (add + del)| 0 | 71235.22 +- 9736.57 | NA |
| CF^2 (del) | 60 | 13.7 +- 16.99 | NA |
| CF^2 (add + del) | 70 | 6.89 +- 18.70 | NA |
| InduCE-transductive | 53.5 | 4.73 +- 4.38 | NA |
| InduCE-inductive | 93 | 6.6 +- 2.87 | NA |

Please note that for **Amazon** dataset, CF-GNNExplainer (add + del) has a fidelity of 0, but an extremely large explation size. Such counterfactual explanations are undesirable since they are destroying the whole network in order to flip node labels. Moreover, counterfactuals are prized for being human intelligible. Such large counterfactuals go against this notion.

**Notes:**
* **NULL:** When Fidelity is 100\% for an algorithm, it means that the algorithm was unable to find the counter-factual for *all* query nodes. Hence, the explanation size is undefined for such cases. We denote this event through "NULL" in the size column.
* **NA:** Accuracy is NA for Amazon, since we do not have ground truth explanations in this dataset.
* **GEM:** The baseline of GEM is not extendible to include edge additions and hence not included in the above table. Specifically, GEM has a distillation process that generates the ground truth. Distillation involves removing every edge in a node's neighbourhood iteratively and seeing its effect on the loss. The deletions are then sorted based on their effect on the loss. The top-$k$ edges ($k$ is user-specified) are used as the distilled ground truth. The explainer is later trained to generate graphs that are the same as the distilled ground truth. To extend this process for additions, the number of possible edge edits is significantly higher and the iterative process of GEM to create the distilled ground truth does not scale. In addition, it is also not clear how to set $k$ in the presence of additions.

We will include the above table and the related discussion in our revised draft.

**The contribution of this work is very similar to the model-based explainer, like PGexplainer over GNNExplainer, which has been widely used in many explainers. Its contribution and novelty seem to be limited.**

*Response:* We would like to humbly clarify that the above referred works are not counter-factual. They are factual explainers. Counter-factual explaination is a different problem altogether that requires its own specialized algorithms. The difference in their objectives have been discussed in our manuscript (please refer to the second paragraph of "Existing works"). It has already been established that when factual explanations are adopted for counter-factual reasoning by removing the factual explanation (subgraph) from the input graph, they are not effective since they lack the minimality component [1,2,3] (also mentioned in line 571 of our manuscript). [1,2,3] compare with factual explainers and on the same datasets that we have used and have shown better performance. We have outperformed these counter-factual algorithms.

* [1] Lucic, A., Ter Hoeve, M.A., Tolomei, G., De Rijke, M. and Silvestri, F., 2022, May. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In International Conference on Artificial Intelligence and Statistics (pp. 4499-4511). PMLR.
* [2] Tan, J., Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y. and Zhang, Y., 2022, April. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022 (pp. 1018-1027).
* [3] Lin, W., Lan, H. and Li, B., 2021, July. Generative causal explanations for graph neural networks. In International Conference on Machine Learning (pp. 6666-6679). PMLR.

**Appeal to the reviewer:** We hope the rebuttal clarifies that our manuscript already includes a related work section. Furthermore, this section discusses the differences with factual explainers. We further strengthen our claims of performance by extending the baselines with edge additions. **If the reviewer feels satisfied with our response, we humbly appeal to consider increasing our rating.**

-----------------------------

Rating: BA (has promised to increase score on satisfactory rebuttal)

**Do baseline methods also experience performance improvement when considering addition?**

*Response:* None of the baselines support edge additions. Thus, to address this question, we have conducted additional experiments by extending CF-GNNExplainer and CF^2 with additions. We note that when additions are allowed, for both baselines the performance deteriorates (more significantly for CF-GNNexplainer). While it is hard to pin-point the exact reason, we hypothesize this behavior is a consequence of the fact that the search space of graph edits dramatically increases when additions are allowed. The increase in search space makes the combinatorial modelling task of *learning* the right set of edits harder. InduCE does not suffer from this limitation, since its RL-based selection algorithm is built from the ground-up keeping additions in mind.

### Treecycles
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 49 | 1.05 +- 0.23 | 100 |
| CF-GNNExplainer (add + del)| 100 | Null | Null |
| CF^2 (del) | 0 | 7.33 +- 3.64 | 40.60 |
| CF^2 (add + del) | 13.89 | 28.34 +- 7.56 | 19.24 |
| InduCE-transductive | 0 | 1.01 +- 0.12 | 97.22 |
| InduCE-inductive | 0 | 2.31 +- 1.44 | 96.65 |

### Treegrids
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 10 | 1.37 +- 0.58 | 92.24 |
| CF-GNNExplainer (add + del)| 100 | Null | Null |
| CF^2 (del) | 0 | 11.74 +- 4.86 | 45.15 |
| CF^2 (add + del) | 28.68 | 12.90 +- 7.71 | 27.44 |
| InduCE-transductive | 0 | 1.01 +- 0.12 | 98.45 |
| InduCE-inductive | 0 | 4.67 +- 2.91 | 91.05 |

### BA-shapes
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 37 | 1.31 +- 0.55 | 95.83 |
| CF-GNNExplainer (add + del)| 38.16 | 6315.44 +- 9916.50 | 17.36 |
| CF^2 (del) | 0 | 3.79 +- 1.70 | 74.50 |
| CF^2 (add + del) | 100 | Null | Null |
| InduCE-transductive | 23.7 | 1.24 +- 1.02 | 98.4 |
| InduCE-inductive | 2.6 | 4.37 +- 3.53 | 64.4 |

### Amazon-photos
| Method | Fidelity (%) ↓| Size ↓ | Accuracy (%) ↑ |
|----------------------------|--------------------|-----------------------|---------------------|
| CF-GNNExplainer (del) | 100 | Null | NA |
| CF-GNNExplainer (add + del)| 0 | 71235.22 +- 9736.57 | NA |
| CF^2 (del) | 60 | 13.7 +- 16.99 | NA |
| CF^2 (add + del) | 70 | 6.89 +- 18.70 | NA |
| InduCE-transductive | 53.5 | 4.73 +- 4.38 | NA |
| InduCE-inductive | 93 | 6.6 +- 2.87 | NA |

Please note that for **Amazon** dataset, CF-GNNExplainer (add + del) has a fidelity of 0, but an extremely large explation size. Such counterfactual explanations are undesirable since they are basically destroying the whole network in order to flip node labels. For InduCE, we only allow a maximum budget for explanation size, which is more realistic.

**Notes:**

* **NULL:** When Fidelity is 100\% for an algorithm, it means that the algorithm was unable to find the counter-factual for *all* query nodes. Hence, the explanation size is undefined for such cases. We denote this event through "NULL" in the size column.

* **NA:** Accuracy is NA for Amazon, since we do not have ground truth explanations in this dataset.

* **GEM:** The baseline of GEM is not extendible to include edge edits and hence not included in the above table. Specifically, GEM has a distillation process that generates the ground truth. Distillation involves removing every edge in a node's neighbourhood iteratively and seeing its effect on the loss. The deletions are then sorted based on their effect on the loss. The top-$k$ edges ($k$ is user-specified) are used as the distilled ground truth. The explainer is later trained to generate graphs that are the same as the distilled ground truth. To extend this process for additions, the number of possible edge edits is significantly higher and the iterative process of GEM to create the distilled ground truth does not scale. In addition, it is also not clear how to set $k$ in the presence of additions.

We will include the above table and the related discussion in our revised draft.

**What is the semantic difference of generated CF explanations when considering addition?**

*Response:* This is indeed an important question. In Section 4.7 of our manuscript, we present case-studies explaining the need to incorporate additions in counter-factual explanations and visually illustrate their semantic implications. We elaborate the implications further below.

The GNN output on a node is a function of its topological neighborhood. Counter-factual explanations generate the minimal change in this topology to alter the GNN output on the target node. Now, let us consider a scenario where a node belongs to class “1” if it is part of a cycle of size at least $k$; otherwise class $0$. Under this setup, if a node is part of a line graph of size $k$, the GNN would predict class label $0$. The counter-factual explanation would be to add an edge that induces a cycle of size $k$. Existing algorithms would be unable to produce this explanation, since they only consider edge deletions. Note that through deletions, it is impossible to introduce a cycle in the graph.

The above case may arise in several scenarios. In a financial network, an organization may be considered trust-worthy if it forms a cycle with at least $k$ other trust-worthy organizations. Similarly, an antibody binding pocket may exist in an antigen if it forms a cycle with two other atoms. Counter-factual explanations therefore serve two different roles: (1) it provides a recourse when the output is undesirable (Ex. As organization may use a GNN to decide on loan application and also offer recourse/explanations when a loan is denied), (2) identify vulnerabilities in a GNN by studying the counter-factual explanations and fine-tune them further.

We will incorporate the above discussion in our manuscript to better emphasize the semantic implications of edge additions in counter-factual reasoning.

**Can they provide ablation studies on INDUCE that only consider deletion? What is the resulting performance gain/drop as a result of this formulation change?**

*Response:* We humbly point out that this ablation study is already included in our work (See Sec 4.5, Table 4 and Fig. 3). Fidelity, which denotes the percentage of graphs for which we are unable to find a counter-factual explanation, increases (worsens) by $\approx 23\%$ on average when only deletions are allowed.

**In counterfactual explanation literature, inductive/transductive inference is also referred to as non-amortized/amortized acceleration [1] or non-parametric/parametric methods [2]. To reduce confusion about the terms, I suggest citing these papers.**

1. **Efficient XAI Techniques: A Taxonomic Survey**
2. **CounterNet: End-to-End Training of Counterfactual Aware Predictions**

*Response:* Thank you for pointing this out. We will certainly incorporate this suggestion.

**In the literature on counterfactual explanations, the trade-off between cost and invalidity is well-demonstrated [2, 3]. Essentially, there are two trade-off objectives: counterfactual size and accuracy. It would be interesting to see if the authors could provide some analysis of this trade-off.**

2. **CounterNet: End-to-End Training of Counterfactual Aware Predictions**
3. **Algorithmic Recourse in the Wild: Understanding the Impact of Data and Model Shifts**

*Response:* We present the accuracy vs. size trade-off for InduCE in the tables below. With higher size, the accuracy decreases. Recall, we use benchmark datasets with ground-truth explanations where a node belongs to a particular class if it belongs to a certain motif. Hence, an explanation is accurate if it includes edges from the motif. We observe that when the model fails to find short explanations, it typically deviates towards a sequence of edges outside the motif (and hence fails to flip the label till a large set of edits are made)

**Dataset: Tree-Grid**
**Induce-inductive:**

| Counterfactual Size | Avg Accuracy
|---------------------|--------------
| 1 | 1.0
| 3 | 0.97
| 5 | 0.89
| 7 | 0.88
| 10 | 0.8
| 15 | 0.73

**Induce-transductive:**

| Counterfactual Size | Avg Accuracy
|---------------------|--------------
| 1 | 0.98
| 2 | 1.0

**Dataset: BA-Shapes**
**Induce-inductive:**
| Counterfactual Size | Avg Accuracy |
|---------------------|--------------|
| 1 | 1.0 |
| 3 | 1.0 |
| 5 | 1.0 |
| 7 | 1.0 |
| 10 | 1.0 |
| 15 | 0.73 |

**Induce-transductive:**

| Counterfactual Size | Avg Accuracy |
|---------------------|--------------|
| 1 | 1.0 |
| 2 | 1.0 |
| 6 | 0.5 |
| 7 | 0.57 |

**Dataset: Tree-Cycles**
**Induce-inductive:**

| Counterfactual Size | Avg Accuracy |
|---------------------|--------------|
| 1 | 1.0 |
| 3 | 0.94 |
| 5 | 0.73 |
| 6 | 0.83 |
| 7 | 0.86 |

**Induce-transductive:**
| Counterfactual Size | Avg Accuracy |
|---------------------|--------------|
| 1 | 0.97 |
| 2 | 1.0 |

We will add the above results in the form of plots to our paper. Note that this analysis is not feasible on the real-world Amazon dataset because it has no ground-truth explanations.

**In lines 579-597, I am unsure whether the statement "having access to the embeddings of the black-box model implies not suitable for real-world scenarios" is accurate. I would argue that having access to the black-box model (including embeddings) is a realistic setting. For example, explanations generated by CF models can help ML model developers understand and debug the model. Therefore, it is not unreasonable to assume that CF explanation models can have access to the black-box models.**

*Response:* We agree that counter-factual explanations can help ML model developers understand and debug the model (Our case study in Sec 4.7 shows explicit case studies highlighting this aspect.) Our intent in this statement is to refer to scenarios where the GNN is being used by an end-user without having access to the GNN internals. Such scenarios may arise when a GNN is trained by an ML company and sold/provided as a service/tool to domain engineers for predictive analytics.

To more accurately reflect this intent, we propose to change the statement as follows:

> ..we do not assume access to the embeddings of the black-box model. Hence, our algorithm is also applicable in situations where the internal details of the GNN are hidden from the end-user due to proprietary reasons.

**Appeal to the reviewer:** We hope that the rebuttal addresses all the comments. We have also added the results for the additional experiments (baselines with edge additions, trade-off between size and accuracy) mentioned in the comments. If the reviewer feels satisfied with our response, we humbly appeal to consider increasing our rating.

------------------------

Rating: BR

**Q1. Scalability: Is the method scalable to large-scale graphs, and what is its computational complexity? Can it handle real-world graphs with millions of nodes and edges?**

Response: We provide detailed complexity analysis of our algorithm in Sec 3.5. The computation complexity of generating a node explanation is $\mathcal{O}(\delta(\mathcal{|V|} + \mathcal{|E|})$, where $\mathcal{V}$ and $\mathcal{E}$ are the sets of nodes and edges, and $\delta$ is the maximum number of allowed edits. Note that the $(\mathcal{|V|} + \mathcal{|E|})$ component in the complexity results from the requirement to run the original GNN following each edit and check whether the label has flipped. Hence, the short answer to the above question is that *if the original GNN scales, then the explainer scales as well.*

We showcase this with concrete empirical data in the table below. We have added a new dataset, ogbg-arxiv, which contains millions of edges.

| Dataset | #Nodes | #Edges | Density | Avg Running time per node (in ms) |
|---------------|--------|---------|---------|-----------------------------------|
| Tree-Cycle | 871 | 1,950 | 2.23 | 60.56 |
| Tree-Grid | 1,231 | 3,410 | 2.77 | 13.67 |
| BA-Shapes | 700 | 4,100 | 5.86 | 89.91 |
| ogbg-arxiv | 169,343 | 1,166,243 | 6.89 | 172.81 |
| Amazon-photos | 7,487 | 119,043 | 15.89 | 5242.32 |

We note that the growth of the running time is more closely correlated with the network density than the size. In a GNN with $\ell$ layers, only the $\ell$-hop neighborhood of the target node matters. Although this $\ell$-hop neighborhood may span the entire graph in the worst case, in practice, that is typically not the case. The span of the $\ell$-hop neighborhood is a function of the network density and hence, more than the graph size, the density of the graph affects the performance.

We will include the above scalability experiment in our manuscript. We also note that Table 6 already presents running time results per test set (i.e., all nodes in the test set) for the three datasets of Tree-Cycle, Tree-Grid and BA-shapes.

**Q2. Unclear impact on model performance: The paper does not provide a clear analysis of how the proposed method affects the performance of the GNN model itself, which is an important consideration when adopting interpretability techniques.**

Response: It appears the above comment is a misunderstanding. The proposed explanation method (and the baselines as well) does not alter the GNN’s prediction (or training). It provides post-hoc analyses. Hence, the question of affecting the GNN performance does not arise. We will state this explicitly at the start of the experiments section to leave no room for ambiguity.

**Q3. Explanation quality: How can the quality of the generated explanations be assessed, and what metrics are suitable for evaluating the interpretability and usefulness of the explanations?**

Response: There exist well-established metrics for evaluating efficacy of counter-factual explanations in the literature [1,2,3], which are explanation size (smaller is better), fidelity (the ability to find recourse, i.e., flip the label), and accuracy/usefulness of the explanation. We use these standard metrics for our evaluation as well (See Sec 4.2.2).

We emphasize that we use three datasets with **pre-annotated ground-truth explanations.** These datasets have been curated specifically for evaluating explainability and hence, it is easy to evaluate usefullness of the explanation. An explanation is useful, if it is part of the ground truth, which is measured using the *accuracy* metric.

If the reviewer feels some additional metrics should also be included, we would appreciate if the reviewer can share those. We would be happy to include in our study.

**Q4. User evaluation: How do domain experts or end-users perceive the explanations provided by the proposed method? It would be valuable to conduct user studies to assess the effectiveness of the explanations in real-world applications.**

*Response:* As explained above, our datasets are already pre-annotated with ground-truth explanations (these are standard benchmark datasets that have been used by all GNN explainability papers). Hence, effectiveness of our explanations is measured in terms of accuracy. This is the standard setup used across all GNN counterfactual explainability papers.

We also point to Section 4.7, which includes case-studies visually illustrating the interpretability of the explanations.

**Q5. Limited comparison: The paper does not compare its approach with other relevant methods, such as [3] and [27]. The authors argue that this method is only applicable to graph classification, but their own method can also be applied to graph classification problems, which suggests that a comparison would be valuable.**

*Response:* Graph classification is a different problem from node classification. There is no clear way how our method may be adopted for graph classification or alternatively, how [3, 27] can be adopted for node classification. There are two fundamental differences in these problem spaces.
1. Graph classification requires an aggregation step to convert the set of node embeddings into a graph-level embedding. This aggregation step requires specialized algorithms for graph-level explanation algorithms. In addition, the loss function is also per graph and not per node. Hence, there is no clear path to adopting our technique for graph classification and vice-versa.
2. Node classification is typically performed on large graphs containing hundreds to thousands of nodes. Graph classification is performed on smaller graphs containing less than hundred nodes. Hence, methods for graph classification do not scale to our setup. The non-scalability results from the need to compute node embeddings for ***all*** nodes of the graph and then aggregate, which is not required in node-level tasks.

**Q6. Black-box nature of RL: Although the paper aims to address the interpretability issue in GNNs, the proposed method relies on reinforcement learning, which is itself a black-box approach. This may raise questions about the trustworthiness of the generated explanations.**

*Response:* The output of the RL algorithm is a set of edge edits that changes the prediction of the GNN on a target node. There is no uncertainty associated with the change in the GNN prediction. Hence, the need to explain the impact of the edits itself does not arise.

We agree that one may question the semantic interpretation of the edits, which an RL algorithm will not be able to answer. This is a limitation of this work as well as all existing counter-factual explanation algorithms (even those beyond GNNs). We will be happy to state this explicitly in the conclusion section of our work.

**Q7. Insufficient exploration of alternatives: The paper could benefit from a more in-depth exploration and discussion of alternative approaches to interpreting GNNs, which would help to better position the proposed method in the context of existing research.**

*Response:* Thank you for the suggestion. We will expand the discussion on related works. We propose to make the following concrete changes:

1. We have already included discussions on factual and counter-factual explainers (Sec 1, Subsection "Existing works"). We will expand by also including a paragraph on neuron-level explainers ([1,2,3]).

* [1] Azzolin, S., Longa, A., Barbiero, P., Lio, P., & Passerini, A., ICLR 2023, Global Explainability of GNNs via Logic Combination of Learned Concepts.
* [2] Xuanyuan, H., Barbiero, P., Georgiev, D., Magister, L. C., & Lió, P., AAAI 2023, Global Concept-Based Interpretability for Graph Neural Networks via Neuron Analysis.
* [3] Junfeng Fang Xiang Wang An Zhang Zemin Liu Xiangnan He Tat-Seng Chua, WSDM 2023, Cooperative Explanations of Graph Neural Networks.

2. We will expand on the discussion on why factual reasoners are not adequate for counter-factual explainers. We will also cite results from the literature that has established this empirically.

4. We will add a paragraph on the rich body of work on node classification through GNNs and therefore the need to explain node classification. In this paragraph, we will also point out why explainers for graph classification do not generalize to node classification (our response to Q5 above)

**Appeal to the reviewer:** We hope the rebuttal clarifies the major concrens and addreses all the comments. We have also provided additional experiments to showcase the scalability of our approach. If the reviewer feels satisfied with our response, we humbly appeal to consider increasing our rating.

-------------------

Rating: BR

**There is a confusing expression, in line 220. "There is an edge between two nodes $𝑣_𝑖, 𝑣_𝑗 \in \mathcal{V}$ if $𝑣_𝑖$ corresponds to some set $𝑆 \in \mathcal{S},\: 𝑢$ corresponds to item $𝑢 \in 𝑈$, and $𝑢 \in \mathcal{𝑆}$." $v_j$ and $u$ are confusing. Does $v_j$ equal $u$?**

*Response:* Sorry for this error. Indeed, $v_j$ equals $u$. We will correct this as follows:

> There is an edge between two nodes $𝑣_𝑖, 𝑣_𝑗 \in \mathcal{V}$ if $𝑣_𝑖$ corresponds to some set $𝑆 \in \mathcal{S},\: \textbf{v_j}$ corresponds to item $𝑢 \in 𝑈$, and $𝑢 \in \mathcal{𝑆}$.

**It is confusing why should node $v$ cover all class in line 225. In general, a node is classified as one class and at least covers one class.**

*Response:* Node $v$ needs to cover all nodes (and not classes) in set $U$. This is analogous to covering all items in $U$ (recall we have an item node corresponding to each item). Since we are allowed to only add edges between nodes in set $N$ to nodes in set $S$, minimizing explanation size is equivalent to selecting those nodes in $S$ (i.e., adding edge to), whose union covers all items in U (the objective of set cover).

To more explcitly bring out this aspect, we will add a more detailed proof in the Appendix along with a figure that explains the transformation of a set-cover instance to a counter-factual explanation instance.

**There is no reward convergence proof in this paper.**

*Response:* We use Policy Gradients (citation 22 in our manuscript) to learn the parameters of the Markov Decision Process. The convergence proof of policy gradient is available in "The Policy Gradient Theorem" of [1]. We will refer to this theorem of [1] to surface convergence of InduCE.

[1] Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA.

**Equation 10 seems intuitively reasonable, but it is difficult to understand the motivation of this equation.**

*Response:* Eq. 10 has two components in the denominator. The size of the explanation in terms of number of edge edits and the quality of the explanation in terms of log-likelihood of the data. The higher the size, the inferior is the explanation. Similarly, the higher the log-likelihood of the data, the worse is the explanation since we want the label of the target node $v$ to flip. Hence, we put both these terms in the denominator of the reward function. $\beta$ is a weight parameter to control the importance of size of explanation vs. the likelihood to flip label.

We will explain the motivation behind Eq. 10 by including the above discussion.

**There are many NULL in Table 10 and 11.**

*Response:* In Tables 8 and 9, we present the fidelity values of the various algorithms on the Amazon dataset. When Fidelity is 100\% for an algorithm, it means that the algorithm is unable to find the counter-factual for ***all*** query nodes. In Table 10 and 11, we present the explanation sizes. Whenever Fidelity is 100\%, the question of explanation size does not arise since no explanations were found. We denote this event through "NULL". As can be observed in Tables 8-9, the proposed algorithm InduCE has the lowest Fidelity across all cases and consenquently the least number of NULL values in Tables 10-11. In constrast, the entries for the baselines in Tables 10-11 are mostly NULL, since their fidelity itself is 100\% in Tables 8-9.

While we briefly explain the meaning of "NULL" in the captions of Tables 10-11, we will expand their descriptions to leave no room for ambiguity.

**When to stop the training？ It is unclear in figure 2 when to stop training.**

*Response:* As noted in Fig. 2, the RL algorithm continues to sample edits till either a max budget $\delta$ is reached or the label of the target node flips. Once this happens, the loss is backpropagated to fine-tune the model parameters (typically, we collect losses over a batch of nodes and then backpropagate). This process is repeated over epochs till the loss on a validation set saturates (i.e., the validation loss does not decrease beyond $\alpha$ over $\gamma$ epochs where $\alpha$ and $\gamma$ are hyper-parameters). We retain 10% of the train set for validation. We will include these details in the appendix with a reference from the main paper as well as in caption of Figure 2.

**Baseline methods are not enough. There are no other explainer methods, such as PGMExplainer, PGExplainer, IGExplainer, etc, except counterfactual methods.**

*Response:* We would like to humbly clarify that the above referred works are factual explainers. Counter-factual explaination is a different problem altogether that requires its own specialized algorithms. The difference in their objectives have been discussed in our manuscript (please refer to the second paragraph of "Existing works"). It has been already been established that when factual explanations are adopted for counter-factual reasoning by removing the factual explanation (subgraph) from the input graph, they are not effective since they lack the minimality component [1,2,3] (also mentioned in line 571 of our manuscript). [1,2,3] compare with factual explainers and on the same datasets that we have used and have shown better performance. We have outperformed these counter-factual algorithms. Hence, repeating an experiment that is already available in the literature would not generate any new information other than establishing reproducibility.

* [1] Lucic, A., Ter Hoeve, M.A., Tolomei, G., De Rijke, M. and Silvestri, F., 2022, May. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In International Conference on Artificial Intelligence and Statistics (pp. 4499-4511). PMLR.
* [2] Tan, J., Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y. and Zhang, Y., 2022, April. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022 (pp. 1018-1027).
* [3] Lin, W., Lan, H. and Li, B., 2021, July. Generative causal explanations for graph neural networks. In International Conference on Machine Learning (pp. 6666-6679). PMLR.

**Appeal to the reviewer:** We hope the rebuttal clarifies all the concerns raised in the comments from the reviewer. If the reviewer feels satisfied with our response, we humbly appeal to consider increasing our rating.