Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs

Thank you for your feedback. Please find below our answers to your questions.

---

W1

We completely agree. We do not claim that all faithfulness metrics should be consistent with each other, but we do point out that existing ones do not and that, therefore, care should be taken when choosing and communicating faithfulness results.

Indeed, differences between ranking metrics, just like for others, are well-documented, and oftentimes multiple metrics are reported to show the generalizability of the results [1,2,3]. A similar argument applies to Accuracy and F1 score, where one is chosen over the other based on insights about the class distribution.

For faithfulness, to the best of our knowledge, such differences have not been documented, and in fact, previous works typically choose faithfulness metrics without motivating their choice and considering the distribution of interventions more like an implementation detail rather than a key factor of the metric being evaluated [4,5,6]. For instance, we showed that some necessity metrics do not properly account for the number of irrelevant edges in the explanation (Prop. 2-3), therefore encoding different semantics than expected.

For the sake of completeness, we added a discussion on how to choose the most appropriate metric configuration depending on the task at hand in the revised Appx. C.4.

---

W2: Details of Prop. 4 are missing

Thank you for pointing this out. Prop. 4 works for any choice of $p_C$ and $p_R$ subsampling the input graph, just like the ones present in Table 1. This is because any perturbation sampled from them will inevitably lead to a change in the model's output, due to our injectivity assumption. As for $d$, the statement holds for any divergence between output probability distributions, and $d$ being the difference in the prediction likelihood. We updated the statement and proof of Prop. 4 accordingly.

Prop. 4, therefore, holds for any faithfulness metric fitting this template.

---

W2: What does "$p_R$ matches $N_L(u)$" mean in Prop. 4?

We believe this is a slight misunderstanding. In fact, "match" was referred to "$R_A$", and not to "$p_R$". Therefore, "matches" simply means the explanation’s topology should be equal to either $N_L(u)$ or $G_A$, which in both cases is the computational graph of the prediction.

We rephrased Prop. 4 to remove this ambiguity.

---

W3 & W5c

Thank you for pointing this out. Our results hold for both node and graph classification. Recalling that given a node $u$, modular GNNs would output an explanation $R_A \subseteq N_L(u)$, our results can be interpreted as follows:

• Def 1, Def 2, and Prop 1 are expressed in terms of an input graph $G_A$, but the definitions are general and hold also for node-level tasks. In this setting, $C_A = N_L(u) \setminus R_A$. Then, the definitions apply verbatim.
• Prop. 2 and 3 focus on the explanation $R_A$, thus apply directly to node-level tasks. In fact, the example of Figure 1 is about a node classification task as it offers an easier intuition.
• Prop 4 differs based on the task. This is already specified in the statement.
• Prop 5 and Thm. 1 hold for both node and graph tasks, provided they respect the domain-invariance assumptions listed in Section 5.

We clarified this in line 160 of the revised PDF.

---

W4: The superiority of the new metric is not explored

We claim that some necessity metrics are better than others: we have shown both theoretically (Prop. 2 and Example 1) and empirically (Fig 2 and Appx. D.2) that our variant of $p_C^b$ is better at penalizing overly large explanations.

We did not claim superiority of specific sufficiency metrics. What we argue is that different choices of $p_R$ can lead to radically different faithfulness semantics, so if one does not clarify what $p_R$ they used, faithfulness results can be easily misinterpreted.

---

W4: The authors report Acc and faithfulness. Their connections to the paper's key contribution are unclear. The relationship between Acc and faithfulness is underexplored.

Table 3 and Table 4 are connected with our second main contribution, which in addition to showing the impossibility of faithfulness for injective GNNs, aims to investigate the practical relationship between some architectural desiderata for modular GNNs and faithfulness (lines 20-23). We include Acc as a sanity check to assess whether faithfulness strategies consistently affect Acc. A formal link between OOD Acc and Faithfulness is then investigated in Section 5, with also a measure of their correlation in lines 494-495.

We updated the revised PDF in line 363 clarifying this.

---

W5a

Good point. We have rearranged them.

W5b

These details were available in Appx. B.2.2. We added them in line 264 and updated the y-axis to indicate that it refers to necessity computed by the two metrics.

Thank you for your feedback.

---

RW1.a)

We apologize for any confusion. We have revised our manuscript to clarify that our criticism is not so much about interchangeability per se, as we agreed that evaluation metrics can naturally disagree, but rather about how these metrics are used. Our main concern is that GNN developers or certification bodies might use faithfulness metrics without much thought, assuming they are interchangeable, while they are not. In practice, this can lead to unreliable or biased rankings of proposed architectures and their explanations.

To make this more concrete, we have compared empirically how changing the distribution $p_R$ computing the sufficiency alters the absolute values of SUF significantly and also the ranking of GNN models in practice.

In particular, we tested four different distributions:

• $p_R^{id_1}$ and $p_R^{ood_1}$ replace the complement $C_A = G_A \setminus R_A$ of an input graph with that of another sample $G_A’$, taken respectively from the ID or OOD data split.
• $p_R^{id_2}$ and $p_R^{ood_2}$ subsample the complement of each graph by randomly removing a fixed budget of edges. The metric is computed either on ID or OOD samples, respectively.

The table below shows for each distribution the ranking of models and the value of SUF between parentheses.

In two cases out of four, just changing the type of perturbation allowed by $p_R$ (replacing the complement vs removing random edges; across columns) changes the ranking of models. Instead, changing the graph distribution (ID vs OOD; across rows) alters the ranking in every case.

We will replace the example in Figure 1 of the PDF with this table by tomorrow.

---

RW1.b)

We focus on GNNs, where this trend does not apply. Besides papers that propose new metrics (like the ones we reference in the text), papers that propose new methods or survey papers generally tend to stick to a single definition [5,6,7,8,9]. We agree the trend you point out is good and needed, and our work can be viewed as an attempt to start this trend also for GNNs.

[7] Interpreting Graph Neural Networks for NLP with Differentiable Edge Masking. 2022

[8] A Survey on Explainability of Graph Neural Networks. 2023

[9] A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability. 2024

---

RW4)

Please note that we address “Reconsidering Faithfulness”, and not “Reconsidering Faithfulness Metrics”. What we mean by this is that we aim at reconsidering faithfulness from a broader perspective, and not just in the way it is computed. In fact, the paper is organised into three main contributions, each touching different aspects of faithfulness:

• Reconsidering how faithfulness metrics are implemented (Section 3)
• Reconsidering how GNN architectures aim to achieve faithful explanations (Section 4)
• Reconsidering the role of faithfulness outside of the XAI community, and in particular its role in the Domain Invariance literature (Section 5)

We believe that under this lens those three sections and all the experiments fit the overall message of “Reconsidering Faithfulness”. We will update the Introduction by adding the following sentence at the end:

"Overall, the previous three main contributions move towards reconsidering faithfulness in a broad sense, i.e., by i) reconsidering how it is computed, ii) reconsidering how GNN architectures aim at achieving it, and iii) reconsidering its role outside of the XAI literature."

---

The key message of Fig 2 is not clear

Thank you for the feedback. We will streamline the discussion of Figure 2 in the main text, strengthening the link between our theoretical analysis of necessity metrics and Figure 2. Also, as the picture can be difficult to grasp, we will replace it with a textual description capturing its core idea, along with all the details needed to understand the key takeaways of this empirical analysis.

We will update the PDF by tomorrow.

---

We appreciate your valuable feedback and we'll remain available for any further clarification.

We thank the reviewer for their feedback. We are glad they found our contribution novel and supported by an in-depth analysis and solid experiments. Below we address their remarks.

---

I highly suggest the authors include a section summarizing key takeaways and practical guidance on selecting appropriate faithfulness metrics for various GNN explanation settings, tailored to different types of models

We have added a discussion of what choosing different interventional distributions ($p_R$ and $p_C$) and divergences ($d$) might entail in Appendix C.4 of the updated PDF. In short, some choices yield “stricter” faithfulness metrics and others “looser” metrics, and there is a monotonic relationship between these.

To see this, consider two different choices for $p_R$:

• Strictest choice: $p^1_R$ allows to modify the complement of the explanation in every conceivable way via node/edge addition and removal and arbitrary feature perturbations. Being strictly sufficient wrt $p^1_R$ means being invariant to any possible change to the complement.

• Loosest choice: $p^2_R$ allows only node/edge removal. This is the most narrow distribution, and it corresponds to most metrics in Table 1.

Similar arguments hold for $p_C$ and $d$, see Appendix C.4.

Clearly, there is a monotonic relationship between metrics: achieving high sufficiency (resp. faithfulness) wrt a stricter metric entails high sufficiency (resp. faithfulness) wrt looser metrics.

The choice of best metric is however application dependent. Stricter metrics are tighter and make sense in high-stakes applications, where faithfulness is a must, and for providing adversarial robustness guarantees (for, e.g., Machine Learning as a Service), while looser metrics are more meaningful if adversarial inputs are not a concern.

These insights apply to both post-hoc and modular settings.

Our key point is however that some metrics are surprisingly flawed, as we show for common necessity metrics in Section 3.2.

---

How to determine if the explanation is not strictly sufficient? It would be beneficial to improve the paper by providing a concrete example or procedure for determining if an explanation fails to be strictly sufficient

Testing if an explanation is not strictly sufficient amounts to finding a counterexample showing that a modification outside of the explanation leads to a large enough prediction change. This can be done naively with Monte Carlo sampling from $p_R$, or by devising more efficient algorithms inspired to, for example, finding adversarial examples [1].

We added in Appendix C.3 a discussion regarding testing for non-strict sufficiency, along with the sketch of an algorithm.

[1] Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. NeurIPS 2024.

We thank the reviewer for their feedback. We are glad they found our analysis well motivated and interesting, and useful for identifying pitfalls of faithfulness research. Below we address their remarks.

---

The relation between faithfulness and out-of-distribution performance is unclear. It would be beneficial if the authors could provide a brief explanation describing this relation in simple terms.

Thank you for the suggestion. We have updated the Faithfulness is key to OOD generalization paragraph (lines 64+) to provide a clearer intuition, as follows:

“Specifically, prior work tackles domain invariance by constructing DIGNNs that isolate the domain invariant portion of the input and use it for prediction. We show that extracting a domain invariant subgraph is not enough for a truly domain invariant GNN: unless the subgraph is also faithful, the information from the domain-dependent components of the input can still influence the prediction, thus preventing domain invariance. This highlights a key limitation in current design and evaluation strategies for DIGNNs, which neglect faithfulness altogether.”

We had to postpone the actual analysis to Section 5 due to space constraints.

---

The paper lacks a clear description and implication of the theoretical analysis.

Our theoretical analysis is structured as follows:

• Prop. 1 shows that faithfulness metrics are not interchangeable, meaning that explanations may be faithful wrt to one metric but arbitrarily unfaithful wrt to others. The implication is that faithfulness values must be properly contextualized wrt the parameters $p_C$, $p_R$, and $d$ to avoid misinterpretations (lines 185-196).

• Prop. 2 and 3 formalize the intuition that different necessity metrics have different semantics. We provide intuition for each proof right before each statement. Their practical implications are explored in Section 3.2. In short, we illustrate how to devise a necessity metric that properly accounts for the number of truly irrelevant items (wrongly) covered by an explanation.

• Prop. 4 shows that for injective regular GNNs, the explanation must cover the entire computational graph. This result implies that faithful explanations do not depend on model weights, and are thus uninformative (line 315)

• Prop. 5 shows that even if a modular GNN correctly identifies invariant subgraphs, unless the subgraph is strictly sufficient, the model as a whole cannot be domain invariant. This result demonstrates that subgraph invariance alone is not enough for truly invariant DI-GNNs (line 454-460), contrary to what is commonly assumed in the domain invariance literature.

• Theorem 1 takes a step further and shows that the degree of sufficiency and plausibility upper bound the change in prediction likelihood – a proxy to measure the OOD generalisation ability of a GNN. The implication of this result is that we can devise better DI-GNNs by also considering sufficiency when designing and evaluating them (lines 485-489).

We updated Section 7 in the uploaded revised PDF to more clearly convey the main takeaways, highlighting for each of them how they are connected to the theoretical analysis.

---

Formally, each theorem statement is followed by a proof sketch, which describes the main techniques used to derive the lower/upper bound and the practical implications of the bounds

Unfortunately, we cannot include a proof sketch for each result, due to space constraints.

However, following your suggestion, we have updated the text in lines 483-484 to briefly illustrate the main techniques and assumptions used to prove Theorem 1, as follows:

“The Theorem is proved by applying the triangular inequality and basic properties of the expectation and relies on two main assumptions: the domain invariance of $R_A^\*$, and the Lipschitzness of GNNs.”

As we mentioned, the practical implications are discussed in lines 485-489.

We are glad to hear that our comments clarified your concerns. Given that all other reviewers have now replied, and that the discussion period will end in about two days, we kindly ask whether you would consider reflecting your improved opinion in an increased score. Please let us know if there is anything else you wish us to clarify.

Regardless, thank you for your time and valuable feedback,

The Authors

We thank the reviewer for their feedback. We are glad they found our study timely and significant and our analysis rigorous and in-depth. Below we address their remarks.

---

The logical flow between sentences in the introduction could be strengthened, e.g., lines 35 and 36

We have polished the Introduction, please see the updated PDF.

If you could point us to any other passages that are unclear, we’d be glad to clarify them.

---

The abbreviation “cf.” may be confusing. Additionally, there’s a mixture of notation, specifically "|G|" and "∥G∥", which could be standardized for consistency.

We replaced “cf.” with “see” and removed usage of $|G|$ entirely.

---

While the paper highlights significant limitations in existing metrics, it would be more impactful if it suggested potential solutions or proposed a new metric that addresses these limitations

Our main goal is to highlight significant but neglected issues with existing faithfulness metrics and their usage, in the same vein as many other impactful critique papers in the XAI literature [1, 2, 3].

However, it is not true that we propose no solutions. In Section 3.2, we suggest strategies for improving necessity metrics and show both theoretically (Prop. 2 and Example 1) and empirically (Figure 2 and Appendix D.2) that our proposed $p_C^b$ is better for evaluating unnecessarily large explanations compared to existing alternatives.

[1] Adebayo et al., Sanity Checks for Saliency Maps. NeurIPS 2018.

[2] Rudin, Stop explaining black box machine learning models for high-stakes decisions and use interpretable models instead. Nature Machine Intelligence 2019.

[3] Ghorbani et al., Interpretation of Neural Networks Is Fragile. AAAI 2019.

Dear Reviewers,

We have uploaded a new revision of the PDF incorporating all the requested further clarifications. The major changes of this revision can be summarized as:

• We incorporated new experiments in the main text to communicate more concretely the practical implications of "metrics are not interchangeable" in the new Table 2

• We compacted the old Figure 1 into the new Table 3, as this allows for a more intuitive understanding of the main message. Figure 1 was however not deleted, but moved to the Appendix for completeness.

We would like to follow up to see if our responses address your concerns or if you have further questions. We would really appreciate the opportunity to discuss this further and know whether our response has addressed your concerns.

Thank you again.

The Authors