GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking

Q1. Whether adversarially adding the number of edges has an impact on the sufficiency of the factual explainers leading to different experimental results in Figure 2 or Table 4.

Response: We have extended our stability experiments to more datasets for feature perturbation and adversarial attacks (Figures G and H, respectively). The behavior is similar to the topological noise attack explained in Section 4.2; the stability decays with the higher noise and inductive methods handle noise better than transductive.

As requested, we also provide a sufficiency score with explanations generated by the topological noise attack. The results are provided in Figure F. In summary, when the noise increases, the sufficiency drops for most cases, but not in all scenarios. This shows that despite the changes in the explanations caused by the noise, GNNs may still predict the same class under noisy conditions.

Q2. Most experimental results do not seem to provide explanations about the experimental phenomena and comparisons of the advantages and disadvantages of different explanation methods. For example, why the stability of CF^2 has dropped significantly on the IMDB-B and AIDS datasets in Fig. 3.

Response: We appreciate this feedback and now provide clear insights on trends observed across the experiments in the revised manuscript. CF^2 is a transductive method. This lies at the core of the trends observed. Specifically, transductive methods lack generalizable capability to unseen data. Furthermore, the stability is worse on denser datasets such as IMDB-B since due to the presence of more edges, the search space of explanation is larger. Transductive methods such as CF^2 and GNNExplainer witness higher deterioration in stability in such harder situations due to being transductive.

Q3. For the experimental results of stability against topological noise, why are the GEM and SubgraphX not used.

Response: We have updated Fig. 3 by adding GEM and SubgraphX. GEM has two-steps (distillation + generation) and one can add noise in any of these two steps. We have added noise before the distillation step, which makes it comparable to other methods. On the other hand, SubgraphX is time-consuming while providing subpar efficacy in terms of robustness compared to other explainers. For example, SubgraphX consumes $\approx 26.5$ hours to run on 435 test graphs in the Mutagenicity dataset. The inclusion of GEM and SubgraphX in Fig. 3 does not affect our conclusions.

Q4. There are differences between different factual explainers on different datasets. Is there a benchmark to select a proper explainers in practice.

Response: This is an excellent question and is the ultimate objective of this study! The choice of the explainer depends on various factors and we make the following recommendations. We have now added a flowchart to help the user in selecting the most appropriate. This recommendation has now also been added as a flowchart (Fig. S in App. K). The same flowchart is presented in text below. We have added this discussion in the manuscript (App. K). We have also referred this discussion in the conclusions (Sec. 5).

• For counter-factual reasoning, we recommend RCExplainer for graph classification and CF-GNNExplainer for node classification.
• For factual reasoning, if the goal is to do node or graph classification, we need to first decide if we need an inductive reasoner or transductive. While an inductive reasoner is more suitable, we want to generalize to large volumes of unseen graphs, transductive is suitable for explaining single instances. In case of inductive, we recommend RCExplainer, while for transductive GNNExplainer stands out as the method of choice. These two algorithms had the highest sufficiency on average. In addition, RCExplainer displayed stability in the face of noise injection.
• For different task generalization beyond node and graph classification, one can consider using TAGExplainer.
• In high-stakes applications, we recommend RCExplainer due to consistent results across different runs and robustness to noise.
• If computation time is important, we recommend an inductive reasoner since they only involve a forward pass through the corresponding neural network. Transductive reasoners train the parameters on the input and hence is significantly slower in practice.

While the above is a guideline, we emphasize that there is no one-size-fits-all benchmark for selecting the ideal explainer. The choice depends on the characteristics of the application in hand and/or the dataset. The above flowchart takes these factors into account to streamline the decision process.

Q1. I believe there is some space for improvement in the paper's presentation. I suggest some important metrics, such as necessity and reproducibility can be expressed in mathematical equations. This can bring convenience for readers to understand the concepts.

Response: Thank you for this suggestion. We now define all metrics mathematically in Table 3 while discussing the metrics in Sec. 3 of the revised manuscript. The relevant metrics are reproduced verbatim below for easy access.

$$\text{Sufficiency}(\mathcal{S}) = \frac{\sum_{i=1}^{|\mathbb{G}|} \mathbb{1}(\Phi({\mathcal{G}_S^i}) = \Phi(\mathcal{G}^i))}{|\mathbb{G}|}$$ $$\text{Necessity}(\mathcal{N}) = \frac{\sum_{i=1}^{|\mathbb{G}|} \mathbb{1}(\Phi(\mathcal{R}^i) \neq \Phi(\mathcal{G}^i))}{|\mathbb{G}|}$$ $$\text{Stability}(\mathcal{E}_X, \mathcal{E}'_X) = \frac{\vert\mathcal{E}_X\cap\mathcal{E}'_X\vert}{\vert\mathcal{E}_X\cup\mathcal{E}'_X\vert}$$ $$\text{Reproducibility}^{+}(\mathcal{R^+}) = \frac{ACC(\Phi_S)}{ACC(\Phi)}$$ $$\text{Reproducibility}^{-}(\mathcal{R^-}) = \frac{ACC(\Phi_R)}{ACC(\Phi)}$$

• $\mathbb{G} = \{\mathcal{G}^1, \mathcal{G}^2, \dots, \mathcal{G}^n\}$, the set of all graphs.
• ${\mathcal{G}^i_S}$ is the explanation subgraph of $\mathcal{G}^i$
• $\mathbb{G}_S = \{\mathcal{G}^1_S, \mathcal{G}^2_S, \dots, \mathcal{G}^n_S\}$ is the set of explanations.
• $\mathcal{R}^i = \mathcal{G} - \mathcal{G}^i_S$
• $\mathbb{R} = \{\mathcal{R}^1, \mathcal{R}^2, \dots, \mathcal{R}^n\}$ is the set of residual graphs.
• $\Phi$, $\Phi_S$, and $\Phi_R$ are the models trained on $\mathbb{G}$, $\mathbb{\mathbb{G}}_S$, and $\mathbb{\mathbb{R}}$, respectively. All models are trained on the same labels.
• $\Phi(\mathbb{G}^i)$ is the model's prediction on $\mathbb{G}^i$.
• $\mathcal{E}_X$ and $\mathcal{E}'_X$ are the set of edges in the explanations on the original graph and after noise injection.
• $ACC(\Phi)$ is the test accuracy of the model $\Phi$.

Q2. The notations of A(G_s) in Equation 1 should be A(G').

Response: We have fixed it. Thanks for pointing this out.

Q3. In definition 2, the prediction of the perturbated graph is defined to be different from the counterpart of the original graph. I think this is valid for binary classification. For multi-classification problems, the counterfactual reasoning should be associated with a pre-assigned label.

Response: Thank you for the suggestions. This has been incorporated in Def. 2. The relevant text is reproduced verbatim below.

In case of multi-class classification, if one wishes to switch to a target class label(s), then the optimization objective is modified as $\mathcal{G}^*=\arg\min_{\mathcal{G}'\in\mathbb{G},\: \Phi(\mathcal{G}')=\mathbb{C}} \; dist(\mathcal{G},\mathcal{G}')$, where $\mathbb{C}$ is the set of desired class labels and $\mathbb{G}$ is the set of all graphs one may construct by perturbing $\mathcal{G}$.

Q4. The definitions of fidelity, necessity, and reproducibility seem to be vague. The fidelity in section 4 (under figure 2) is not clear, "some works have used the term fidelity instead of sufficiency" has no citations.

Response: As noted in our response to Q1, we have now provided mathematical definitions of all the metrics in Table 3. Furthermore, we have removed the term Fidelity from our manuscript and consistently use only Sufficiency.

Q1. The conclusions from the empirical comparison are not clear. It would be better to summarize the conclusions from the empirical comparison and provide conceptual insights, such as how would the results guide the future design of GNN explanation methods.

Response: This is an excellent suggestion. We appreciate the constructive feedback. To incorporate this suggestion, we have now made the following changes.

• The conclusion section (Section 5) has been expanded to discuss research directions that may potentially yield solutions to the primary limitations identified in this study, namely - incorporating generative modeling in counterfactual reasoning to address feasibility concerns, and migrating towards ante-hoc reasoning to address instability and non-reproducibility. Current explainers are post-hoc in nature, wherein the explanations are generated post the completion of GNN training. In this pipeline, the explainers have no visibility to how the GNN reacts to perturbations on the input data, initialization seeds, etc. In the ante-hoc paradigm, the GNN and the explainer are jointly trained.
• For each experiment, we have added a paragraph titled "Insights" to clearly discuss the take-aways and provide explanations for the trends observed.

Q2. Discussion of the existing works needs more structure. Current discussion of the related works is based on the summary for each method. It would be better to provide more structures of the current works, such as what methods the existing ones share in common.

Response: We have incorporated this suggestion through the following mechanisms:

• Tables 1 and 2 characterize different factual and counterfactual methods, respectively, along various dimensions such as scoring function, intended task (such as graph/node classification), modeling paradigm (transductive vs. inductive), etc. Through these tables, it is now easy to derive the common principles shared across algorithms.
• We have also re-structured the related work discussion (Sec. 2.1) based on these tables to better elucidate the common design principles and enable easier abstraction of their conceptual designs.

Q3. It would be better to clearly define how the sufficiency score is computed.

Response: We have added the mathematical formulation of sufficiency as well as all other metrics used in our work (See Table 3 in the revised manuscript). The relevant portion is reproduced verbatim below.

Sufficiency encodes the ratio of graphs for which the prediction derived from the explanation matches the prediction obtained from the complete graph.

$$\text{Sufficiency}(\mathcal{S}) = \frac{\sum_{i=1}^{|\mathbb{G}|} \mathbb{1}(\Phi({\mathcal{G}_S^i}) = \Phi(\mathcal{G}^i))}{|\mathbb{G}|}$$ $$\text{Necessity}(\mathcal{N}) = \frac{\sum_{i=1}^{|\mathbb{G}|} \mathbb{1}(\Phi(\mathcal{R}^i) \neq \Phi(\mathcal{G}^i))}{|\mathbb{G}|}$$ $$\text{Stability}(\mathcal{E}_X, \mathcal{E}'_X) = \frac{\vert\mathcal{E}_X\cap\mathcal{E}'_X\vert}{\vert\mathcal{E}_X\cup\mathcal{E}'_X\vert}$$ $$\text{Reproducibility}^{+}(\mathcal{R^+}) = \frac{ACC(\Phi_S)}{ACC(\Phi)}$$ $$\text{Reproducibility}^{-}(\mathcal{R^-}) = \frac{ACC(\Phi_R)}{ACC(\Phi)}$$

• $\mathbb{G} = \{\mathcal{G}^1, \mathcal{G}^2, \dots, \mathcal{G}^n\}$, the set of all graphs.
• ${\mathcal{G}^i_S}$ is the explanation subgraph of $\mathcal{G}^i$
• $\mathbb{G}_S = \{\mathcal{G}^1_S, \mathcal{G}^2_S, \dots, \mathcal{G}^n_S\}$ is the set of explanations.
• $\mathcal{R}^i = \mathcal{G} - \mathcal{G}^i_S$
• $\mathbb{R} = \{\mathcal{R}^1, \mathcal{R}^2, \dots, \mathcal{R}^n\}$ is the set of residual graphs.
• $\Phi$, $\Phi_S$, and $\Phi_R$ are the models trained on $\mathbb{G}$, $\mathbb{\mathbb{G}}_S$, and $\mathbb{\mathbb{R}}$, respectively. All models are trained on the same labels.
• $\Phi(\mathbb{G}^i)$ is the model's prediction on $\mathbb{G}^i$.
• $\mathcal{E}_X$ and $\mathcal{E}'_X$ are the set of edges in the explanations on the original graph and after noise injection.
• $ACC(\Phi)$ is the test accuracy of the model $\Phi$.

Q1. Lack of creativity and significance: The authors conducted an evaluation to measure many explainers' performances, but did not come up with a novel solution to overcome the discovered challenges. Also, the conclusions are not insightful enough with further analysis. Based on this reason, it is hard to regard this paper as a research paper.

Response: The Call for Papers for ICLR 2024 includes 'Datasets and Benchmarks' (refer to https://iclr.cc/Conferences/2024/CallForPapers), and our submission falls within this category. Benchmarking papers are not anticipated to present novel solutions; rather, the focus is on conducting a comprehensive empirical evaluation in a relevant area and offering fresh insights previously undiscovered. It is a reasonable expectation from a benchmarking paper to propose potential directions for addressing identified limitations, as we have done in Section 5. Based on the suggestions provided, we have further expanded our discussion on potential solutions in the revised manuscript.

Q2. Poor layout: The layout of words and tables is too dense, such as Table 1, 4, 5, and 8. Numbers inside table are too small and hard to read.

Response: We appreciate this constructive feedback. We have thoroughly revisited all sections of the paper and have ensured the fonts are large enough to be comfortably legible in the revised manuscript. We have also increased spacing around tables. We hope these changes have effectively addressed the presentation-related concerns.

Dear Reviewer,

Since we are only a day away from the completion of the discussion phase, we are eagerly awaiting your feedback on the revised manuscript. We have addressed all of the presentation related concerns and present a significantly expanded discussion on potential solutions to the previously undiscovered shortcomings of the explainability methods with regards to stability, feasibility and reproducibility.

Finally, we wish to clarify again that our submission has been made to the Dataset and Benchmark category of ICLR.

Please do let us know if there are any additional clarifications or experiments that we can offer. We would love to discuss more if any concern still remains. Otherwise, we would appreciate it if you could support the paper by increasing the score.

regards,

Authors