AIMing for Explainability in GNNs

We appreciate the feedback and have revised the manuscript accordingly.

The paper substantially lacks references to previous works, and many claims central to the proposed contribution are contradicted by the literature.

We have refined the introduction and related work section, considering the points raised by reviewers.

Line 143 says "Explainers do not have to be deterministic". I wonder which kind of insights a human can extrapolate from a black-box when the explanation for a certain fixed output changes when the explanation is non-deterministic. Also, PGExplainer is indicated as a non-deterministic algorithm. However, once the explainer is trained, it is fully deterministic. Only the training of such an explainer is non-deterministic. This should be clarified in the text.

We added clarification to the manuscript.

The authors are proposing to evaluate graph explanation with a suite of 12 evaluation metrics. Such a high number of metrics, in my opinion, makes the assessment of different explainers difficult, making comparison hard.

The broader set of metrics is intended to highlight the strengths and weaknesses of different methods by assessing multiple properties, which is challenging with aggregated metrics alone. Depending on the use case, these metrics could be selectively aggregated or only a subset could be used.

The proposed model is difficult to understand, and Figure 3 does not provide enough information. I would suggest annotating the figure with more detail and providing a more intuitive explanation.

We have provided additional explanations for Figure 3 in the updated manuscript.

Some important implementation details for ensuring reproducibility are lacking, like how the Elbow method for obtaining explanation threshold is implemented. I suggest providing more details on this

Code is shared to ensure reproducibility. We have also included a more precise information on the Elbow method in the Appendix.

Thank you for the feedback and for noting the corrections in notation and punctuation. We have updated the manuscript accordingly.

1 Introduction Structure and Clarity: The logic in the introduction is somewhat unclear. The authors should clearly state their two main objectives: (1) to propose new evaluation metrics for GNN explainability, and (2) to introduce XGKN, a GNN model with inherent interpretability. After discussing the shortcomings of existing methods, the authors should introduce their model XGKN, explaining how it addresses the identified limitations. This should be followed by a clear explanation of the shortcomings of current evaluation metrics, leading to their motivation for proposing new metrics. Additionally, it would be helpful to move the related work to a separate section, so the introduction can focus more on the motivation and contributions. The current contribution section lacks clarity and should be more explicit about the novelty of the work

We revised the introduction section to improve clarity.

Line 160: The explanation for contrastivity is not clear. Contrastivity measures the distinguishability between explanations for different predictions. The authors should clarify their reasoning behind the current formula and explain how it relates to the concept of contrastivity as typically understood in the field.

We reference Contrastivity defined as in Co-12 [1], where "Contrastivity addresses the discriminativeness of explanations with respect to a ground-truth label or other target".

In lines 149 and 167, the definitions of A1 and A2 rely on the explanation of ground truth. However, for real-world datasets where ground truth is not available, it is unclear how this would be handled. The authors could propose alternative metrics for cases without ground truth or discuss how their method could be adapted for such scenarios.

AIM metrics are proposed to assess models where ground truths are not available. But in case they are, it is reasonable to assess accuracy using them. Some metrics are not possible to evaluate (e.g. model-level explanations for considered post-hoc explainers), in that case they are skipped in evaluation (see Figure 2).

Figure and Table Organization: Figures 4 and Table 4 should be combined with Figure 2 and Table 3, respectively. This would allow for better comparison between the performance of the proposed method and existing methods, making it easier to assess improvements.

Improvements were proposed based on results achieved in Figure 2 and Table 3. Combined results from figures are in Appendix. We have included earlier results into Figure 4 (dehighlighted) to make the comparison between models easier.

5. Overall Organization and Presentation: While the paper presents innovative ideas, the structure and presentation need significant improvement. It is recommended to first introduce the proposed method (XGKN), followed by the proposed metrics. In the experiments section, the authors should use their proposed metrics to evaluate both existing methods and their own. Additionally, the limitations of existing metrics should be clearly stated, and the authors should explain how their proposed metrics address these limitations.

The paper is organized to first establish the desired properties for explainability, then evaluate existing GKNs in relation to these properties, and finally propose improvements based on this analysis. Existing metrics mainly focus on fidelity (referred to as Completeness in our work and aligned with the Co-12 properties), but lack evaluation of other critical properties—a limitation we aim to address.

[1] Meike Nauta et al., "From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI.", ACM Comput. Surv. 2023.

Thank you for your feedback. We have revised the manuscript and addressed your concerns in the responses below.

1). the idea of the proposed explainer is not very novel. The paper listed two other GKN approaches. On top of that, the new stuffs in this paper is not significant. Meanwhile, the performance improvement on AIM metrics over two other GKN approaches is not significant.

Our main goal is to propose a comprehensive set of metrics to evaluate XAI GNN approaches. Such framework evaluates desired properties, allows to determine shortcomings and improve methods. We showcase that by investigating GKNs. We note that improvements are not ground breaking, but that was not our objective.

2). The authors do not consider the OOD issue of the metrics that are discussed in the following papers: Cooperative explanations of graph neural networks. WSDM’23. TOWARDS ROBUST FIDELITY FOR EVALUATING EXPLAINABILITY OF GRAPH NEURAL NETWORKS. ICLR’24.

The claim that f(h(G)) is being applied ood when what is trained is f(G) is generally true, but for a range of approaches, particularly GKNNs and KerGNNS, the fact that we operate over subgraphs anyways is some sort of protection against complete ood. More generally, the question of whether an explanation---defined to be an 'importance' scored subgraph in the input---is necessary and sufficient to recover the intended prediction is quite reasonable. The main issue appears to be whether the architecture employed for f is amenable to this, and in certain cases, it is much less susceptible to ood than others.

3). The motivation is not well-written on the improvement over existing GKN approaches.

We present our motivation following an evaluation of existing GKNs, outlining our thought process and rationale for improvements.

Thank you for your feedback regarding the paper. We have revised the manuscript accordingly and added further clarifications in the responses below.

In terms of contribution 1, there are previous efforts such as GraphFramEx that try to provide some properties and eval metrics for graph explainability. Although I understand AIM is not exactly the same, it would be great if the authors can elaborate on the differences and build their insights over previous work instead of starting from scratch

The related work section has been expanded to include additional references to evaluation metrics proposed for post-hoc explainers such as GraphFramEx. We also emphasized the similarities between our metrics and those discussed in other works.

Personally I found it rather hard to compare XGKN and KerGNN by cross ref Figure 2 and Table 3 with Figure 4 and Table 4 that are 3 pages apart. But my understanding is that:

Table 3 v Table 4 -- out of 6 benchmarks, 3 KerGNN is better and 3 XGKN is better -- it would be great if the authors can elaborate on why "XGKN outperforms its predecessor, KerGNN, delivering superior results"

Our aim was to first analyze existing methods, identify their limitations, and then introduce our model (XGKN) to address these gaps, hence the paper’s structure and the division of results across two tables and two figures. Accuracy levels across models are generally comparable, with notable outliers that indicate the relative difficulty of tasks for specific models (e.g., PROTEINS for ProtGNNs and IMDB for GKNNs). Since our primary focus is on interpretability, Figures 2 and 4 are most relevant and our comments on XGKN’s performance improvements refer to these results.

In terms of times to extract explanations -- the different is quite small and probably fall in the regime of implementation details -- it would be great if the authors can elaborate on why this difference is fundamental, rather than some implication of implementation decisions.

For explanations extraction we use publicly available code with additionally needed code shared across models to achieve fair comparison. The goal was to highlight time needed to extract explanations from ProtGNN and explain that it is due to the sampling strategy that ProtGNN employs, which we do in section 3.2.2.

I didn't find a good way to compare Figure 2 and Figure 4 clearly and understand it; given the authors still have 1 page left, I would enrich 4.2.2 and really compare these two methods clearly, tease apart different datasets.

We have updated Figure 4 to include prior results (dehighlighted) to make comparison easier. Nevertheless, Figure 6 in the Appendix provides results for all datasets, aggregated appropriately.

Thank you for your feedback regarding the paper, we have updated the manuscript accordingly.

Completeness (without): I(f(G\f(h(G)) != c) the formula is wrong, I guess it should be I(f(G \ h(G)) != c). Also, this metric exists and is called fidelity- (or sufficiency).

We corrected typo in the formula and added reference to fidelity. We follow the Co-12 [1] naming convention to unify evaluation framework for different modalities, e.g. our Completeness definition is similar to the accuracy-based fidelity [2].

Consistency: this is poorly formalized, as IoU(h(G),h(G)) is 1 by construction. You should clarify (and formally write) that this is computed by picking explanations from a distribution (I guess).

We corrected the formula.

Continuity: While this is sensible with low-level data (like pixels), it's not necessarily sensible with discrete structures like graphs, where the the ground truth could be a motif, and removing elements of the motif could end up changing the label of the graph. Indeed, measures like explanation fidelity (especially robust fidelity+), encode the fact that removing elements that are part of the explanation should have an impact on the prediction of the model (and thus, on the resulting post-hoc explanation).

The goal is to measure if background noise affect explanations. We have modified the noising process to generate the perturbed graph such that it excludes parts of graph that are part of initial graph explanations. This metric is related to robustness [3], but fundamentally distinct. Our experiments using this modified noising process appear to indicate little difference from the original results, although we appreciate that there could be more complex situations where this distinction is relevant.

Contrastivity: the definition doesn't seem to fit the description in Table 1

We have updated the definition, which should hopefully clarify the confusion.

For model-level metrics, correctness seems to be closer to a (model-level) definition of robust fidelity+, but in this set of metrics is somehow in contradiction with consistency in the instance-level metrics.

Our Model-level Correctness assesses changes in explanations when interpretable model parts (prototypes or graph kernels that guide explanation extraction) are modified. We do not see how this relates to robust fidelity+ (assuming that review refers to [2]) or conflicts with instance-level consistency.

M3: Compactness - I am not sure this is about compactness, I would rather talk about non-redundancy.

Compactness in [1] covers size but also redundancy. We adopt this terminology to remain faithful to the Co-12 nomenclature.

Talking about interpretable GNNs, the authors only focus on prototype-based and kernel-based GNNs. However, the literature on interpretable GNNs is much richer. For instance, all methods based on attention are missing

Attention-based methods are now included in the related work section.

Additionally, only two explainers are evaluated, while plenty of (more recent) explainers have been proposed in the literature.

Our focus is on interpretable GNNs that provide model-level explanations, specifically graph kernel and prototype networks. To provide context and demonstrate the versatility of our approach, we also include two popular post-hoc explainers. Our goal was not to determine the best existing explainer but to establish a framework, detailing desired properties which should be optimized in future XAI GNN models. We focus on enhancing graph kernel networks, recognizing their potential for XAI. To this end, we identify desirable properties for XAI, outline graph kernel networks’ limitations, compare them to prototype networks (since they are most obvious alternative), and suggest improvements.

Finally, the authors propose a SHAP-based approach to extract explanations from interpretable GNNs, which is fine. But post-hoc explainers can still be applied to interpretable GNNs, so it is not true that no solution exists. The authors should show that their approach is better in extracting explanations from interpretable GNNs.

While post-hoc explainers can extract explanations from interpretable GNNs, this setup complicates evaluation; it’s unclear whether limitations stem from the GNN’s interpretability or the explainer’s efficacy. For clarity, we use SHAP as a more straightforward method. Additionally, we show that explanations from post-hoc baselines are suboptimal, suggesting caution in relying solely on these approaches.

[1] Meike Nauta et al., "From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI.", ACM Comput. Surv. 2023.

[2] Xu Zheng et al., "Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks," ICLR 2024.

[3] 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.