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

## Abstract

Abstract As Graph Neural Networks (GNNs) become more pervasive, it becomes paramount to build robust tools for computing explanations of their predictions.
A key desideratum is that these explanations are faithful , i.e. , that they portray an accurate picture of the GNN’s reasoning process.
A number of different faithfulness metrics exist, begging the question of what is faithfulness exactly, and what are its properties.
We begin by showing that existing metrics are not interchangeable – i.e. , explanations attaining high faithfulness according to one metric may be unfaithful according to others – and can be systematically insensitive to important properties of the explanation, and suggest how to address these issues.
We proceed to show that, surprisingly, optimizing for faithfulness is not always a sensible design goal. Specifically, we show that for injective regular GNN architectures, perfectly faithful explanations are completely uninformative.
The situation is different for modular GNNs, such as self-explainable and domain-invariant architectures, where optimizing faithfulness does not compromise informativeness, and is also unexpectedly tied to out-of-distribution generalization.

## 1 Introduction

The increasing popularity of GNNs [, , ] for even high-stakes [] tasks has prompted the development of tools for explaining their decisions.
Regular GNNs are opaque and explanations must be extracted in a post-hoc fashion using specialized algorithms [], while self-explainable GNNs employ a modular setup to natively output explanations for their own predictions [].
A key metric of explanation quality is faithfulness [, , , , , , , ]. Intuitively, an explanation is faithful insofar as it highlights all and only those elements – edges and/or node features – of the input graph that are truly relevant for the prediction.
Faithfulness ensures an explanation portrays an accurate picture of the GNN’s reasoning process, and thus supports understanding, trust modulation, and debugging [].

Existing faithfulness metrics measure the stability of the model’s output to perturbations of the input graph – e.g., to ensure that modifying those elements that are marked as irrelevant by the explanation has in fact no effect – yet differ in many details.
For instance, some metrics perturb the input by zeroing-out all irrelevant node features [] while others delete a subset of edges instead []; cf. Section 3 for an overview.
Unfortunately, the literature provide little guidance on what metric should be used and on how to tune GNN architectures for optimal faithfulness.
We aim to fill this gap.

Existing metrics are not interchangeable. As a first contribution, in Section 3.1 we parameterize existing metrics along two dimensions: how stability is measured and what perturbations are allowed.
We show that different parameter choices yield rather different metrics, in the sense that explanations that are faithful for one metric are not faithful according to others.
Hence, faithfulness measurements cannot be interpreted unless these parameters are provided. This is relevant in high-stakes applications such as loan approval, in which explanation providers could manipulate (but withhold) the parameters to mislead explanation consumers into overestimating the faithfulness of explanations [].

Not all existing metrics are equally reliable. Next, in Section 3.2 we uncover systematic issues with popular faithfulness metrics.
Specifically, we show they are insensitive to the number of irrelevant elements captured by the explanation, and argue that this issue can be avoided with an appropriate choice of parameters.

Is faithfulness worth optimizing for? In Section 4 we study to what extent optimizing for faithfulness is a sensible design goal.
We show that for injective GNNs, explanations achieving strict (that is, perfect) faithfulness are not informative, and identify a natural trade-off between expressiveness of the model and usefulness of faithful explanations.
Then we show that for modular GNNs, including self-explainable GNNs and GNNs designed for domain invariance, strict faithfulness explanations are not necessarily trivial and evaluate several practical strategies for improving faithfulness, highlighting a trade-off between strict faithfulness and learnability.
Finally, in Section 5 we show that faithfulness plays a central, yet so far neglected, role in domain invariance. Specifically, while prior work [, , , ] focuses on developing techniques for encouraging GNNs to isolate and use the domain invariant portion of the input, we show that this provides no guarantees unless this subgraph is also faithful.

## 2 Graph Neural Networks and Faithfulness

Throughout, we indicate graphs as $G=(V,E)$ and annotated graphs as $G_{A}=(G,X)$, where ${\bm{\mathrm{x}}}_{u}\in\mathbb{R}^{d}$ are per-node features.
We denote the $k$-hop neighborhood of $u$ as $N_{k}(u)$, and shorten $N_{1}(u)$ to $N(u)$, $|G|=|V|$ to $n$, and $\lVert G\rVert=|E|$ to $m$.

Graph Neural Networks (GNN) [] are discriminative classifiers that, given an input graph $G_{A}$, define a conditional distribution $p_{\theta}(\cdot\mid G_{A})$ over candidate labels.
In graph classification, the label $y\in\{1,\ldots,c\}$ applies to the whole graph, while in node classification it is a vector ${\bm{\mathrm{y}}}\in\{1,\ldots,c\}^{n}$ with one element per node.
Inference in GNNs is opaque, in that it relies on message passing of embedding vectors along the graph’s topology.
Usually, this amounts to recursively applying an aggregation operation of the form:

$$ ${\bm{\mathrm{h}}}^{\ell}_{u}=\mathsf{aggr}({\bm{\mathrm{h}}}^{\ell-1}_{u},\{{ \bm{\mathrm{h}}}^{\ell-1}_{v}\ :\ v\in N(u)\})$ (1) $$

to all nodes $u$, from the bottom to the top layer. Here, ${\bm{\mathrm{h}}}^{0}_{u}={\bm{\mathrm{x}}}_{u}$ are the node features, ${\bm{\mathrm{h}}}^{\ell}_{u}$ the node embeddings at the $\ell$-th layer, and $\mathsf{aggr}$ a learnable non-linear aggregation function.
We refer to this form of aggregation as *local*, as opposed to *non-local* aggregation where $\mathsf{aggr}$ runs over nodes outside of $N(u)$, e.g., by means of virtual nodes [].
In node classification, the top-layer node embeddings are stacked into a matrix $H^{L}\in\mathbb{R}^{n\times d}$, which is fed to a dense layer to obtain a label distribution $p_{\theta}({\bm{\mathrm{Y}}}\mid G_{A})=\mathrm{softmax}(H^{L}W)$, where $W\in\mathbb{R}^{d\times c}$ are weights.
In graph classification, they are aggregated into an overall embedding ${\bm{\mathrm{h}}}_{G}=\mathsf{aggr}_{G}(\{{\bm{\mathrm{h}}}_{u}^{L}:u\in V\})$, also fed to a dense layer.

Explainations and Faithfulness. There exist a number of post-hoc techniques [, , ] that given a GNN $p_{\theta}$ can extract a local explanation for any target decision $(G_{A},\hat{y})$. These explanations identify a subgraph $R_{A}$ capturing those elements – edges and/or features – deemed relevant for said decision.
Unfortunately, explanations output by post-hoc approaches may fail to identify all and only the truly relevant elements, in which case we say they are not faithful to the GNN’s reasoning process [, ]. Lack of faithfulness hinders understanding, trust allocation, and debugging [].

This has prompted the development of self-explainable GNNs (SE-GNNs), a class of GNNs that natively output explanations without any post-hoc analysis [, ].
SE-GNNs comprise two modules: the detector $f$ extracts a class-discriminative subgraph $R_{A}$ from the input, and the classifier $g$ uses $R_{A}$, and only $R_{A}$, to infer a prediction. In this context, $R_{A}$ acts as a local explanation.
Both modules are GNNs, and the detector is encouraged to output human interpretable explanations by leveraging attention [, , , ], high-level concepts or prototypes [, , , , ], or other techniques [, , ].

In practice, the detector outputs per-element relevance scores (usually in $[0,1]$), which are then used to identify an explanation subgraph $R_{A}$ via, e.g., thresholding. Moreover, the node features $X^{R}\in\mathbb{R}^{n\times n}$ of $R_{A}$ are derived from, but not necessarily identical to, those of $G_{A}$. These remarks will become relevant when discussing strategies for improving faithfulness in Section 4.2.

Faithfulness and Domain Invariance. As we will show in Section 5, faithfulness also plays a key role for domain-invariant GNNs (DI-GNNs), which aim to generalize across multiple related domains [, , , ].
The underlying assumption is that the label $y$ and the input $G_{A}$ are determined by a set of domain-invariant factors. The input graph, however, also contains domain-dependent elements, hence, in order to generalize, the model has to successfully identify and use the invariant subgraph [, ].
Like SE-GNNs, DI-GNNs are modular, i.e., include a detector $f$ for identifying the invariant subgraph $R_{A}$ and a classifier $g$ taking $R_{A}$ as input. The detector is encouraged to output invariant subgraphs through specialized regularization terms and training strategies [, , , ].

## 3 Pitfalls of Faithfulness Estimation

In the remainder, we fix a GNN $p_{\theta}$ and a decision $(G_{A},\hat{y})$ and study the faithfulness of a corresponding local explanation $R_{A}$.
Intuitively, an explanation is faithful as long as it sufficient, i.e., if keeping it fixed shields the model’s output from changes to its complement $C_{A}$, and necessary, i.e., if altering it affects the model’s output even if the complement $C_{A}$ is kept fixed [, , , ].

Formally, we say that an explanation $R_{A}$ is strictly sufficient if no change to the complement $C_{A}$ induces any change to the model’s output, i.e., $\lnot\exists C_{A}^{\prime}\ .\ p_{\theta}(\cdot\mid G_{A}^{\prime})\not\equiv
p
_{\theta}(\cdot\mid G_{A})$, where $G_{A}^{\prime}$ is obtained by joining $R_{A}$ and $C_{A}^{\prime}$; and strictly necessary if all changes to the explanation lead to a change, i.e., $\forall R_{A}^{\prime}\ .\ p_{\theta}(\cdot\mid G_{A}^{\prime})\not\equiv p_{
\theta}(\cdot\mid G_{A})$, where $G_{A}^{\prime}$ conjoins $R_{A}^{\prime}$ and $C_{A}$. A strictly faithful explanation satisfies both conditions.
Existing metrics relaxing these notions by restricting the set of alternative graphs $G_{A}^{\prime}$ they consider and by replacing logical equivalence with the expected change in model output [].
Specifically, unfaithfulness [] estimates sufficiency as the Kullback-Leibler divergence between the original label distribution and that obtained after zeroing-out all irrelevant features from $G_{A}$.
Fidelity minus [, , ] instead erases all edges and features deemed irrelevant by the explanation and measures the change in likelihood of the prediction $\hat{y}$.(^1^11A variant based on the difference in accuracy also exists [].)
Robust fidelity minus $\mathsf{RFid}\scalebox{0.9}{-}(R_{A},y)$ does the same but repeatedly deletes random edges from $C_{A}$ [, , ].
Finally, probability of sufficiency $\mathsf{PS}(R_{A},y)$ estimates how often the model’s prediction changes after multiplying the node features with the relevance scores output by the detector [].
Metrics for necessity are specular, i.e., they manipulate the input by removing relevant elements instead, and include fidelity plus $\mathsf{Fid}\scalebox{0.9}{+}$, robust fidelity plus $\mathsf{RFid}\scalebox{0.9}{+}$, and probability of necessity $\mathsf{PN}$.(^2^22In node classification, deleting the explanation never not removes the target node.)

**Table 1: 1 recovers existing faithfulness metrics for approriate choices of divergence $d$ and interventional distributions $p_{R}$ and $p_{C}$.**
| Metric | Estimates | Divergence $d$ | Distribution $q$ |
| --- | --- | --- | --- |
| $\mathsf{Unf}$ [] | $\mathsf{Suf}$ | $\mathsf{KL}(p_{\theta}(\cdot\mid G_{A}),p_{\theta}(\cdot\mid G_{A}^{\prime}))$ | zero out all irrelevant features |
| $\mathsf{Fid}\scalebox{0.9}{-}$ [, , ] |  | $|p_{\theta}(\hat{y}\mid G_{A})-p_{\theta}(\hat{y}\mid G_{A}^{\prime})|$ | zero out all irrelevant features, delete all irrelevant edges |
| $\mathsf{RFid}\scalebox{0.9}{-}$ [, , ] |  | " | delete a random subset of irrelevant edges |
| $\mathsf{PS}$ [] |  | $\mathbbm{1}\!\left\{p_{\theta}(\hat{y}\mid G_{A})=p_{\theta}(\hat{y}\mid G_{A}<br>^{\prime})\right\}$ | multiply all irrelevant elements by relevance scores |
| $\mathsf{Fid}\scalebox{0.9}{+}$ [, , ] | $\mathsf{Nec}$ | $|p_{\theta}(\hat{y}\mid G_{A})-p_{\theta}(\hat{y}\mid G_{A}^{\prime})|$ | zero out all relevant features, delete all relevant edges |
| $\mathsf{RFid}\scalebox{0.9}{+}$ [, , ] |  | " | delete a random subset of relevant edges |
| $\mathsf{PN}$ [] |  | $\mathbbm{1}\!\left\{p_{\theta}(\hat{y}\mid G_{A})\neq p_{\theta}(\hat{y}\mid G<br>_{A}^{\prime})\right\}$ | multiply all relevant elements by relevance scores |

While existing metrics differ in many several details, they nicely fit the same common format:

###### Definition 1 .

Let $d$ be a divergence, $p_{R}$ a distribution over supergraphs of $R_{A}$, and $p_{C}$ a distribution over supergraphs of $C_{A}$.
Also, let $\Delta_{d}(G_{A},G_{A}^{\prime})=d(p_{\theta}(\cdot\mid G_{A})\ \|\ p_{\theta}
(\cdot\mid G_{A}^{\prime}))$
measure the impact of replacing $G_{A}$ with $G_{A}^{\prime}$ on the label distribution.(^3^33We drop the dependency on $\hat{y}$ for brevity.)
Then, the degree of sufficiency and degree of necessity of an explanation $R_{A}$ for a decision $(G_{A},\hat{y})$ are:

$$ $\mathsf{Suf}_{d,p_{R}}(R_{A})=\mathbb{E}_{G_{A}^{\prime}\sim p_{R}}[\Delta_{d} (G_{A},G_{A}^{\prime})],\quad\mathsf{Nec}_{d,p_{C}}(R_{A})=\mathbb{E}_{G_{A}^{ \prime}\sim p_{C}}[\Delta_{d}(G_{A},G_{A}^{\prime})]$ (2) $$

The expectations in Eq. 2 are potentially unbounded, but they can be normalized to the range $[0,1]$, the higher the better, via a non-linear transformation, i.e., taking $\exp(-\mathsf{Suf}_{d,p_{R}}(R_{A}))$ and $1-\exp(-\mathsf{Nec}_{d,p_{C}}(R_{A}))$.
Table 1 shows that 1 recovers all existing metrics for appropriate choices of divergence $d$ and interventional distributions $p_{R}$ and $p_{C}$.
Alternative choices immediately yield additional metrics.

Both sufficiency and necessity matter, yet there exists a natural tension between them. For instance, explanations covering a larger portion of $G_{A}$ likely attain higher sufficiency but lower necessity.
This motivates us to define the degree of faithfulness $\mathsf{Faith}_{d,p_{R},p_{C}}(R_{A})$ as the harmonic mean of normalized sufficiency and necessity, which is biased towards the lower of the two.
We henceforth suppress the dependency on $d$, $p_{R}$ and $p_{C}$ whenever it is clear from context.

###### Definition 1 .

### 3.1 Faithfulness metrics are not interchangable

A first key observation is that, despite falling into a common template, existing metrics are not interchangeable, in the sense that explanations that are highly faithful according to one metric can be arbitrarily unfaithful for the others.
We formalize this in the following proposition:

[]
(Informal.) Let $(p_{R},p_{C})$ and $(p_{R}^{\prime},p_{C}^{\prime})$ two pairs of interventional distributions.
Then, depending on $p_{\theta}$ and $G_{A}$, $|\mathsf{Suf}_{d,p_{R}}(R_{A})-\mathsf{Suf}_{d,p_{R}^{\prime}}(R_{A})|$ and $|\mathsf{Nec}_{d,p_{C}}(R_{A})-\mathsf{Nec}_{d,p_{C}^{\prime}}(R_{A})|$ can be as large as the natural range of $d$.

All proofs (as well as relevant discussion) can be found in Appendix A.
In essence, Section 3.1 means that faithfulness results cannot be properly interpreted unless the parameters $d$, $p_{R}$ and $p_{C}$ are known.
In practice, this entails that explanation producers – such as banks and algorithm designers – responsible for certifying the faithfulness of explanations cannot withhold the parameters used in the computation, least end-users blindly trust explanations that are not sufficiently faithful for their down-stream applications.

### 3.2 Not all faithfulness estimators are equally good

Given this large variety of metrics, it is natural to wonder whether they are all equally good.
As we will show, it turns out this is not the case because – surprisingly – commonly used necessity metrics are insensitive to the number of irrelevant edges in the explanation.

$\mathsf{Fid}\scalebox{0.9}{+}$ is systematically invariant to truly irrelevant edges. In the following, we assume $R_{A}$ contains $m$ truly relevant edges, that is, such that if any of them is removed from $G$ yield a new graph $G^{\prime}$ such that $\Delta(G,G^{\prime})\neq 0$.
We begin by showing that metrics that estimate necessity using a single modified graph $G_{A}^{\prime}$ obtained by deleting the whole explanation $R_{A}$,(^4^44In node classification, the node whose prediction is being explained is not removed even if it belongs to $R$.) such as $\mathsf{Fid}\scalebox{0.9}{+}$, suffer from this issue.
To see this, note that in an $L$-layer GNN with local $\mathsf{aggr}$, messages from nodes outside of $N_{L}(u)$ cannot influence the prediction of node $u$.
Now, consider a 1-layer GNN $p_{\theta}$ for node classification and an input line graph $u_{1}\leftarrow u_{2}\leftarrow\ldots\leftarrow u_{n}$.
Since there is only one layer, only the messages from $N_{1}(u_{1})=\{u_{1},u_{2}\}$ can contribute to the distribution of $Y_{1}$.
However, $\mathsf{Fid}\scalebox{0.9}{+}$ associates the same value to both $R_{A}=N_{2}(u_{1})$ and to $R_{A}^{\prime}=G_{A}$, which contains arbitrarily many irrelevant nodes.
In fact, for $R_{A}$ it deletes $u_{2}$, while for $R_{A}^{\prime}$ it deletes $u_{2},\ldots,u_{n}$: in both cases, the model predicts $Y_{1}$ using ${\bm{\mathrm{x}}}_{1}$ only, meaning that $\mathsf{Fid}\scalebox{0.9}{+}$ will attain the same value.
Note that, when the edge relevance scores are binary, $\mathsf{PN}$ behaves exactly like $\mathsf{Fid}\scalebox{0.9}{+}$, in which case it also suffers from this issue.

$\mathsf{RFid}\scalebox{0.9}{+}$ is systematically invariant to truly irrelevant edges. So does $\mathsf{RFid}\scalebox{0.9}{+}$. To see this, consider a 1-layer GNN for node prediction, and let $G_{A}$ be an $n$-node star graph with $u_{1}$ as its center, and assume that only the edges between $u_{1}$, $u_{2}$ and $u_{3}$ are truly relevant to $p_{\theta}(Y_{1}\mid G_{A})$. Now, take two explanations: $R=\{u_{1},u_{2},u_{3}\}$ covers all and only the truly relevant edges, and $R^{\prime}=G$. Like above, it turns out that $\mathsf{RFid}\scalebox{0.9}{+}(R)=\mathsf{RFid}\scalebox{0.9}{+}(R^{\prime})$. In fact, $\mathsf{RFid}\scalebox{0.9}{+}$ estimates necessity by removing edges in an IID fashion, which means that the probability that it deletes the edges between $u_{1}$, $u_{2}$, and $u_{3}$ from $R$ is the same regardless of how many other edges appear in the explanation.
We formalize this intuition in the following result:

[]
Fix a divergence $d$ and a threshold $\epsilon>0$. Let $R$ contain $r$ truly relevant edges. Then, $\mathsf{RFid}\scalebox{0.9}{+}(R)$ does not depend on $\lVert R\rVert-r$.

The question is then how to instantiate $\mathsf{Nec}$ such that it does depend on the number of irrelevant elements.
We next show that this can be achieved by letting $p_{C}$ be the uniform distribution over all subgraphs of $R_{A}$.
Since marginalizing over all subgraphs is intractable, we also show that simply averaging over a smaller subset of graphs obtained by erasing $b$ edges from the explanation itself also avoids the issue.
We summarize our findings as follows:

[]
Fix any divergence $d$ and a constant budget $b\geq 1$.
Let $\mathcal{S}_{R}^{b}$ be the set of subgraphs of $G$ obtained by deleting $b$ edges from $R$ while keeping $C$ fixed, and $\mathcal{A}_{R}^{b}=\{G^{\prime}\in\mathcal{S}_{R}^{b}:\Delta(G,G^{\prime})
\geq\epsilon\}$ those subgraphs that lead to a large enough change in $\Delta$. Also, let $\mathcal{S}_{R}=\mathcal{S}_{R}^{1}\cup\ldots\cup\mathcal{S}_{R}^{m}$ and similarly for $\mathcal{A}_{R}$.
Given an explanation $R$ containing $r$ truly relevant edges, $\mathsf{Nec}(R)$ computed using a uniform $p_{C}$ over $\mathcal{S}_{R}$ depends on the number of irrelevant edges $\lVert R\rVert-r$.
The same holds if $\mathsf{Nec}(R)$ is computed using a uniform $p_{C}$ over $\mathcal{S}_{R}^{b}$.

This result highlights that, by selecting an appropriate interventional distribution $p_{C}$, it is possible to design a necessity metric that appropriately accounts for the number of irrelevant edges.

The choice of budget $b$ can bias necessity. In fact, Section 3.2 may fail if b depends on the size of the input graph or the size of the explanation. This occurs because the numerator and denominator of $|\mathcal{A}_{R}^{b}|/|\mathcal{S}_{R}^{b}|$ both depend on b, and thus can act as a confounding variable.
Specifically, if b depends on $\lVert R\rVert$, the metric – once again – does not properly account for irrelevant items in the explanation, as the number of deletions increases according to the size of the explanation.
Indeed, a numerical simulation shows that the probability of deleting at least one truly relevant edge does not depend on the number of irrelevant ones in the explanation, if b is proportional to the explanation size
(see Fig. 4 in the Appendix).
On the other hand, if b is proportional to the size of the input graph $G$, the number of deletions depends also on the size of the complement, resulting in a metric confounded by the complement of the explanation.(^5^55From a causal perspective, letting b depend on the size of $G$ opens a backdoor path from $G$ to $\mathsf{Nec}$, confounding $\mathsf{Nec}$ [].)
This is best seen in the following example:

###### Example 1 .

Fix an explanation $R$ composed of two edges, only one of which is truly relevant.
If $G$ has $10$ edges, fixing a budget of deletion as $10\%$ of the graph size yields a modified graph $G^{\prime}$ such that $P(G^{\prime}\in\mathcal{A}^{1}_{R})=\frac{1}{2}$.
Instead, if $G$ has $20$ edges, then $P(G^{\prime}\in\mathcal{A}^{2}_{R})=1$.
Hence, despite $R$ being fixed, the probability of sampling truly relevant edges drastically changes.

We propose to avoid these issues by fixing a budget that is proportional to a data set-wide statistic, such as average graph size $\bar{m}=1/|\mathcal{D}|\sum_{G\in\mathcal{D}}\lVert G\rVert$, where $\mathcal{D}$ is the set of graphs. This way, it no longer directly depends on the size of any specific input graph or explanation, while still being adaptive to the target task.

Figure: Figure 1: Dependency of the necessity metrics on the size of the explanation. $\mathsf{RFid}\scalebox{0.9}{+}$ and $\mathsf{Nec}$ of explanations output by LECI on Motif2-Basis (averaged over 5 seeds) for different explanation sizes (x-axis) and metric hyper-parameter $\kappa,b\in\{3\%,5\%\}$. $\mathsf{RFid}\scalebox{0.9}{+}$ assigns similar or even higher scores to larger explanations, while $\mathsf{Nec}$ (with a budget $b$ proportional to the average graph size $\bar{m}$) decreases for increasing explanation size, as expected.
Refer to caption: x1.png

Based on these observations, in our experiments we adopt a uniform $p_{C}(G)$ over subgraphs of size $\lVert G\rVert-b$, where b is a hyper-parameter, which will be denoted as $p_{C}^{b}(G)$.
The practical difference between $\mathsf{RFid}\scalebox{0.9}{+}$ and $\mathsf{Nec}$ with $p_{C}^{b}$ is exemplified in the following analysis, where we evaluate the necessity of explanations of the modular architecture GSAT [] over the benchmark Motif2-Basis [], and for different $\mathsf{RFid}\scalebox{0.9}{+}$ edge-deletion probability $\kappa$ and budget b. Since GSAT outputs explanation scores in the $[0,1]$ range, we obtain a relevant input subgraph by discretizing the explanation mask at different size ratios, as common in XAI evaluation [, ]. The results provided in Fig. 1 show that $\mathsf{RFid}\scalebox{0.9}{+}$ assigns close-to-constants scores to explanations at different size ratios, while our previously discussed $\mathsf{Nec}$ tends to penalize larger explanation. We provide in Section C.2 a further comparison of the two metrics.

###### Example 1 .

## 4 Is Faithfulness Worth Optimizing For?

We show that for regular injective GNNs, strict faithful explanations are trivial, highlighting a trade-off between explainability and expressivity.
For modular GNNs, instead, non-trivial strictly faithful explanations are possible provided certain conditions are met. We then empirically verify that some of these conditions are hard to achieve for practical models, suggesting a trade-off between strict faithfulness and learnability.

### 4.1 The Case of Regular GNNs

Recall that an explanation is strictly faithful (cf. Section 3) when no change to the complement $C_{A}$ of $R_{A}$ affects the model’s output, and when all elements in $R_{A}$ contribute to the final prediction.
In the following, we show that for regular GNNs strictly faithful explanations are completely uninformative.
To build intuition, notice that strictly sufficient explanations must subsume the computational graph of the prediction, that is, the subgraph of $G_{A}$ induced by all nodes whose messages influence the label distribution. In node classification, this is the $L$-hop neighborhood of the target node, and in graph classification the whole input graph.
More formally:

[]
Consider a binary classification task and an $L$-layer injective GNN:
i) For node classification that only uses local aggregators. Then an explanation $R_{A}$ for a decision $(G_{A},\hat{y}_{u})$ is strictly faithful wrt $p_{R}$ iff it subsumes $N_{L}(u)$.
ii) For graph classification. Then an explanation $R_{A}$ for a decision $(G_{A},\hat{y})$ is strictly faithful wrt $p_{R}$ iff it subsumes all of $G_{A}$.

Note that in both cases the explanation does not depend on the learned weights at all, hence strictly faithful explanations are trivial. This is a direct consequence of injectivity, a prerequisite for GNNs to implement the Weisfeiler-Lehman test [, ], and highlights a trade-off between expressivity and explainability.(^6^66Of course, one can obtain more informative explanations by giving up on strict faithfulness and instead aiming at producing explanations that are both faithful enough and smaller than the entire computational graph.) For regular GNNs, even forgoing injectivity does not give an easy way to obtain non-trivial strictly faithful explanations. In the next section, we show how this is instead attainable with modular GNN architectures.

### 4.2 The Case of Modular GNNs

For modular GNNs like SE-GNNs and DI-GNNs, non-trivial strictly faithful explanations are attainable, at least in theory. In fact, the following proposition characterizes a set of simple architectural choices making strict faithfulness achievable:

[]
Consider a binary classification task. Let ${p_{\theta}}$ be a modular GNN with detector $f$ and an injective classifier $g$ for graph or node classification. If $f$ is stable, i.e., it always predicts the same $R_{A}$ for all $G_{A}^{\prime}\sim p_{R}$, and implements all of the following strategies:

- •
Hard Scores (HS): it outputs binary 0 0–$1$ relevance scores;
- •
Content Features (CF): the node features of $R_{A}$ are taken directly from the node features of $G_{A}$;
- •
Explanation Readout (ER): (for graph classification only) $\mathsf{aggr}_{G}$ only aggregates embeddings from $R_{A}$ (as opposed to all of $G_{A}$);

then $R_{A}$ is strictly faithful.

By additionally choosing $f$ to be non-injective, non-trivial strictly faithful explanations can be obtained.
Albeit not strictly necessary if the strategies in Section 4.2 are in place, another useful strategy is ensuring the locality of the aggregation function $\mathsf{aggr}$ (LA), as non-local aggregations (cf. Section 2) can easily mix the information of the explanation with that of its complement, and can create unwanted dependencies between any pair of nodes in the graph.

Despite their simplicity, these strategies can greatly impact expressivity and learning in practice.
In fact, binary relevance scores (prescribed by HS) are notoriously hard to differentiate through [, , , ], and non-local aggregators (forbidden by LA) are popular choices to increase the expressivity of GNNs [, , ].
Overall, Section 4.2 testifies that most popular modular models indeed lack one or more of the above desiderata in favor of better downstream performance.

In the remainder of this section, we empirically investigate the impact of integrating popular modular architectures with the strategies they lack, measuring their effect on both faithfulness and final accuracy.

Figure: Table 2: Popular modular architectures fail to fully implement faithfulness-enforcing strategies. SE-GNNs at the top and DI-GNNs on the bottom. ✗/✓ means that both variants exist and the choice is made via cross-validation.

Experimental setup:
We benchmarked six representative modular architectures, listed in Section 4.2, following their respective evaluation testbed for graph classification.
The datasets chosen for evaluation are picked from the usual evaluation routines for respectively SE-GNNs and DI-GNNs. For DI-GNNs, the chosen benchmarks can be divided into datasets with known domain-invariant input motifs (Motif2-Basis, CMNIST-Color), datasets with presumed domain-invariant input motifs (LBAPcore), and datasets where domain-invariant input motif are not expected (SST2). This last case is especially problematic, as no clear advantage is expected in focusing on a subset of the input graph. The full experimental setup is detailed in Appendix B.

Results and discussion:
Table 3 and Table 4 show the results for the base SE-GNNs and DI-GNNs architectures and their augmented variants.
The results suggest that it is possible to improve faithfulness by applying the missing strategies above, yet not consistently across strategies, models, and datasets. Specifically, the strategy with the lightest impact on model architecture, namely ER, is the one achieving the best results, improving faithfulness over the base model in 13 out of 21 cases and being on par in 4. Conversely, more impactful strategies like HS and LA yield less consistent results. For example, HS severely compromises the training of GSAT in Motif2-Basis and Motif-Size, resulting in a train and test accuracy around $50\%$. When combining strategies, faithfulness generally improves when the individual strategies yield positive results.
Among all datasets, SST2 is confirmed to be the most difficult to improve on. Indeed, models tend to output explanations that cover the entire input graph for this dataset (see
Section C.1 for the details).

These results suggest that, while potentially useful, strict faithfulness is a hard goal to achieve and not all strategies encouraging it are viable in practice.
Increasing the degree of faithfulness is a convenient strategy when strict faithfulness is out of reach.
Necessity can intuitively be encouraged via sparsification techniques [, ], whereas encouraging stability of the detector $f$ (using approaches like contrastive learning [, ], adversarial training [], or data augmentation []) is a natural option for encouraging sufficiency, regardless of the properties of the classifier $g$ built on top of it.

**Table 3: Test set accuracy and faithfulness of SE-GNNs augmented with the strategies delineated in Section 4.2, averaged over 5 seeds. Improvements over the base model are in green, worsenings in red. We do not augment GISST on BaMS, Motif2-Basis, and Motif-Size since these data sets have constant input features for all nodes, meaning that these strategies have no effect.**
| Dataset | BaMS | Motif2 | Motif-Size | BBBP |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | $\mathsf{Acc}$ | $\mathsf{Faith}$ | $\mathsf{Acc}$ | $\mathsf{Faith}$ | $\mathsf{Acc}$ | $\mathsf{Faith}$ | $\mathsf{Acc}$ | $\mathsf{Faith}$ |
| GSAT | 100 $\pm$ 00 | 35 $\pm$ 03 | 92 $\pm$ 01 | 61 $\pm$ 01 | 90 $\pm$ 01 | 60 $\pm$ 02 | 79 $\pm$ 04 | 27 $\pm$ 08 |
| GSAT + ER | 100 $\pm$ 00 | 35 $\pm$ 03 | 92 $\pm$ 01 | 63 $\pm$ 01 | 90 $\pm$ 01 | 65 $\pm$ 01 | 80 $\pm$ 02 | 33 $\pm$ 04 |
| GSAT + HS | 98 $\pm$ 01 | 21 $\pm$ 06 | 53 $\pm$ 02 | 24 $\pm$ 05 | 54 $\pm$ 03 | 22 $\pm$ 05 | 71 $\pm$ 01 | 31 $\pm$ 09 |
| GSAT + ER + HS | 99 $\pm$ 01 | 24 $\pm$ 04 | 57 $\pm$ 04 | 37 $\pm$ 03 | 56 $\pm$ 07 | 29 $\pm$ 09 | 73 $\pm$ 02 | 33 $\pm$ 02 |
| GISST | 100 $\pm$ 00 | 25 $\pm$ 03 | 92 $\pm$ 01 | 53 $\pm$ 02 | 92 $\pm$ 00 | 50 $\pm$ 02 | 84 $\pm$ 03 | 23 $\pm$ 11 |
| GISST + ER | - | - | - | - | - | - | 85 $\pm$ 06 | 27 $\pm$ 06 |
| GISST + HS | - | - | - | - | - | - | 83 $\pm$ 05 | 19 $\pm$ 07 |
| GISST + ER + HS | - | - | - | - | - | - | 81 $\pm$ 07 | 15 $\pm$ 09 |
| RAGE | 96 $\pm$ 01 | 33 $\pm$ 05 | 83 $\pm$ 02 | 64 $\pm$ 04 | 74 $\pm$ 09 | 63 $\pm$ 07 | 82 $\pm$ 01 | 33 $\pm$ 04 |
| RAGE + ER | 96 $\pm$ 02 | 33 $\pm$ 02 | 85 $\pm$ 06 | 66 $\pm$ 03 | 71 $\pm$ 09 | 55 $\pm$ 07 | 84 $\pm$ 01 | 33 $\pm$ 05 |
| RAGE + HS | 97 $\pm$ 01 | 46 $\pm$ 03 | 85 $\pm$ 01 | 65 $\pm$ 02 | 78 $\pm$ 07 | 65 $\pm$ 09 | 84 $\pm$ 02 | 46 $\pm$ 02 |
| RAGE + ER +<br>HS | 96 $\pm$ 01 | 46 $\pm$ 04 | 83 $\pm$ 04 | 64 $\pm$ 04 | 75 $\pm$ 08 | 62 $\pm$ 12 | 82 $\pm$ 01 | 43 $\pm$ 03 |

**Table 4: OOD test set accuracy and faithfulness of DI-GNNs augmented with the strategies delineated in Section 4.2, averaged over 5 seeds.**
| Dataset | Motif2 | CMNIST | LBAPcore | SST2 |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | $\mathsf{Acc}$ | $\mathsf{Faith}$ | $\mathsf{Acc}$ | $\mathsf{Faith}$ | $\mathsf{Acc}$ | $\mathsf{Faith}$ | $\mathsf{Acc}$ | $\mathsf{Faith}$ |
| LECI | 85 $\pm$ 07 | 58 $\pm$ 02 | 26 $\pm$ 10 | 48 $\pm$ 11 | 71 $\pm$ 01 | 37 $\pm$ 03 | 83 $\pm$ 01 | 26 $\pm$ 02 |
| LECI + ER | 86 $\pm$ 03 | 59 $\pm$ 02 | 58 $\pm$ 12 | 58 $\pm$ 03 | 71 $\pm$ 01 | 42 $\pm$ 04 | 82 $\pm$ 01 | 13 $\pm$ 02 |
| LECI + HS | 86 $\pm$ 04 | 57 $\pm$ 02 | 34 $\pm$ 10 | 57 $\pm$ 01 | 72 $\pm$ 01 | 25 $\pm$ 02 | 83 $\pm$ 01 | 18 $\pm$ 03 |
| LECI + LA | - | - | 46 $\pm$ 11 | 57 $\pm$ 03 | 69 $\pm$ 01 | 36 $\pm$ 09 | 81 $\pm$ 05 | 20 $\pm$ 04 |
| LECI + ER + HS + LA | 79 $\pm$ 11 | 55 $\pm$ 02 | 75 $\pm$ 06 | 61 $\pm$ 01 | 59 $\pm$ 02 | 24 $\pm$ 01 | 81 $\pm$ 02 | 16 $\pm$ 01 |
| CIGA | 46 $\pm$ 10 | 38 $\pm$ 08 | 23 $\pm$ 03 | 36 $\pm$ 03 | 69 $\pm$ 01 | 20 $\pm$ 10 | 76 $\pm$ 06 | 18 $\pm$ 01 |
| CIGA + ER | 45 $\pm$ 09 | 54 $\pm$ 04 | 23 $\pm$ 02 | 43 $\pm$ 07 | 59 $\pm$ 07 | 07 $\pm$ 03 | 74 $\pm$ 03 | 16 $\pm$ 01 |
| CIGA + CF | 53 $\pm$ 07 | 49 $\pm$ 02 | 13 $\pm$ 01 | 49 $\pm$ 09 | 49 $\pm$ 12 | 04 $\pm$ 01 | 55 $\pm$ 07 | 09 $\pm$ 12 |
| CIGA + LA | 41 $\pm$ 00 | 39 $\pm$ 05 | 30 $\pm$ 09 | 41 $\pm$ 03 | 68 $\pm$ 01 | 25 $\pm$ 17 | 79 $\pm$ 03 | 16 $\pm$ 01 |
| CIGA + ER + CF + LA | 47 $\pm$ 08 | 39 $\pm$ 07 | 23 $\pm$ 03 | 50 $\pm$ 02 | 66 $\pm$ 01 | 28 $\pm$ 17 | 76 $\pm$ 08 | 15 $\pm$ 02 |
| GSAT | 75 $\pm$ 06 | 58 $\pm$ 01 | 25 $\pm$ 04 | 48 $\pm$ 03 | 70 $\pm$ 03 | 32 $\pm$ 06 | 79 $\pm$ 04 | 22 $\pm$ 04 |
| GSAT + ER | 59 $\pm$ 06 | 60 $\pm$ 06 | 30 $\pm$ 06 | 48 $\pm$ 01 | 67 $\pm$ 01 | 36 $\pm$ 03 | 81 $\pm$ 01 | 23 $\pm$ 04 |
| GSAT + HS | 86 $\pm$ 03 | 42 $\pm$ 07 | 14 $\pm$ 03 | 44 $\pm$ 04 | 71 $\pm$ 01 | 30 $\pm$ 01 | 80 $\pm$ 02 | 17 $\pm$ 02 |
| GSAT + LA | 63 $\pm$ 08 | 58 $\pm$ 01 | 27 $\pm$ 03 | 46 $\pm$ 04 | 69 $\pm$ 03 | 39 $\pm$ 05 | 81 $\pm$ 01 | 21 $\pm$ 04 |
| GSAT + ER + HS + LA | 64 $\pm$ 08 | 47 $\pm$ 03 | 17 $\pm$ 02 | 51 $\pm$ 05 | 70 $\pm$ 01 | 33 $\pm$ 04 | 80 $\pm$ 01 | 17 $\pm$ 01 |

Finally, results in Table 4 show instances of DI-GNNs where faithfulness-enforcing strategies also
improved OOD generalization abilities. In the next section we formally investigate the relationship between faithfulness and OOD generalization.

## 5 The Importance of Faithfulness for Domain Invariance

Finally, we study the impact of faithfulness – and lack thereof – on domain invariance.
In the domain invariance literature [, ], one distinguishes between in-distribution (ID) and out-of-distribution (OOD) data, sampled from $p^{id}(G_{A},Y)$ and $p^{ood}(G_{A},Y)$, respectively, and the goal is to learn a DI-GNN $p_{\theta}$ that generalizes from ID to OOD data.
We begin by showing that, even if the graphs $R_{A}$ extracted by a DI-GNN (cf. Section 2) are domain invariant, unless they are also strictly sufficient, the model’s prediction is not domain invariant.

[]
Let ${p_{\theta}}$ be a modular DI-GNN such that the detector $f$ outputs graphs $R_{A}$ that are maximally domain-invariant, i.e., that comprise all and only those elements that are constant across the target domains.
If $R_{A}$ is not strictly sufficient, then the prediction is not domain invariant.

This result is significant because DI-GNNs typically optimize only for domain invariance of the extracted subgraph $R_{A}$, neglecting how this is then used by the classifier on top.
The next result highlights that the degree of faithfulness of $R_{A}$ – and specifically, that of sufficiency – plays a direct role in ensuring the model predictions are in fact domain invariant.

[]
(Informal) Let ${p_{\theta}}$ be a deterministic DI-GNN with detector $f$ and classifier $g$, and $p^{id}(G_{A},Y)$ and $p^{ood}(G_{A},Y)$ be the ID and OOD empirical distributions, respectively. Then:

$$ $\displaystyle\Big{|}\mathbb{E}_{(G_{A},y)\sim p^{id}}[{p_{\theta}}(y\mid G_{A} )]\ -\$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{ood}}[{p_{\theta}}(y\mid G_{A})]\Big {|}$ (3) $\displaystyle\leq\mathbb{E}_{R_{A}^{*}}\left[k_{1}(\lambda_{\text{topo}}^{id}+ \lambda_{\text{topo}}^{ood})+k_{2}(\lambda_{\text{feat}}^{id}+\lambda_{\text{ feat}}^{ood})+(\lambda_{\text{suff}}^{id}+\lambda_{\text{suff}}^{ood})\right].$ $$

Here, $\mathbb{E}_{R_{A}^{*}}$ runs over all possible maximally invariant subgraphs, $k_{1},k_{2}>0$ are Lipschitz constants of ${p_{\theta}}$, $\lambda_{\text{topo}}^{id}$, $\lambda_{\text{topo}}^{id}$ $\lambda_{\text{feat}}^{ood}$, and $\lambda_{\text{feat}}^{ood}$ measure the (negated) degree of domain invariance of the detector’s output (with respect to topology and features, respectively), and $\lambda_{\text{suff}}^{id},\lambda_{\text{suff}}^{ood}$ are the degree of sufficiency for ID and OOD data.

Note that the degree of invariance is computed as the *plausibility* [] of $R_{A}$ with respect to the (domain-invariant) ground truth. In essence, Section 5 shows that a DI-GNN has a consistent behavior between ID and OOD data if
i) $R_{A}$ is in fact invariant across domains, and
ii) $R_{A}$ is highly sufficient.

We stress that while necessity does not appear in the bound, it becomes important if we wish the invariant subgraph to be non-trivial and human-understandable. Indeed, Fig. 2 shows a statistically significant anti-correlation (Pearson’s correlation $-0.83$, $p$-value $0.01$) between the difference in average prediction’s likelihood between ID and OOD data, and the combination of the degree of domain-invariance and faithfulness.
Notably, the same applies, yet with a slightly weaker correlation of $-0.74$ (p-value $0.02$), when replacing likelihood with accuracy. See Appendix B for further details.

Figure: Figure 2: Likelihood, faithfulness and domain-invariance are correlated. The plot shows the difference in likelihood between splits. The red line is the best linear fit. Best viewed in color.
Refer to caption: x2.png

## 6 Related Work

Modular architectures. Modular GNNs have become a popular architectural design choice for seeking trustworthiness, either in the form of explainable [, , , ] or confounding-free predictions [, , , ] (see Jiang et al. [] for a detailed survey), also in deep neural networks for non-relational data [, ].
In both settings, the quality of the explanation – or any other sparse representation used to communicate across the two modules – is known to play a crucial role, for users and stakeholders, and for ensuring fair and generalizable model outputs [, , ]. Despite being designed primarily for faithfulness, as the prediction depends on the explanation only, little attention has been paid to measuring *how well* the classifier adheres its own explanations, an issue that can completely prevent trust allocation [].
Indeed, recent work has shown how for popular SE-GNNs architectures, the classifier seems to be more faithful to randomly generated subgraphs than to its own explanations [].
In this work, we investigate the reasons for this behavior, discuss the applicability of faithfulness-enforcing strategies and extend the analysis to DI-GNNs.

Faithfulness. In the Explainable AI [] and GNN literature [], sufficiency and faithfulness are often conflated, however explanations that are not necessary cannot be faithful, as they open to trivially sufficient yet uninformative explanations.
Faithfulness is also sometimes defined as the correlation between the explainers “performance” and that of the model, that is, to what extent corrupting the input alters the model’s performance []. However, this is narrow to model and explainer performance and does not reflect the degree to which a classifier relies on the provided explanation for making its prediction.
Our notion of faithfulness is rooted in notions from causal explainability [] and disentanglement in causal representation learning [, ].
Like Beckers [], we argue that absolute measurements of sufficiency, and more generally faithfulness, are uninformative unless properly contextualized, in our case by the choice of parameters used for the measurements. Following [], we argue this leaves room for adversarial explanation providers to supply explanations that optimize their objective rather than that of the explanation consumer.

## 7 Discussion and Broader Impact

We have studied the faithfulness of explanations in regular and modular GNNs.
Our results indicate that, despite conforming to a shared template, existing faithfulness metrics are not interchangeable and in fact some even suffer from systematic issues, which we show can be avoided with an appropriate choice of hyperparameters.
We have also shown that optimizing for faithfulness is not always a sensible design goal, and analyzed – theoretically and empirically – both strategies for improving faithfulness in modular GNNs and the importance of faithfulness for domain invariance.
From a societal perspective, the aim of this work is to shed light on the non-trivial nature of explanation faithfulness, warning against its unqualified reporting and interpretation. It can thus contribute to the development of truly interpretable and trustworthy models for networked data.

## Appendix A Proofs

### A.1 Proof of Section 3.1

See 3.1

###### Proof.

We prove the statement for graph classification; the case of node classification is analogous.

Assume $R_{A}$ attains a perfect degree of sufficiency according to $p_{R}$, i.e., $\mathsf{Suf}_{p_{R}}(R_{A})=0$, and take $p_{R}^{\prime}$ such that $\mathcal{S}\cap\mathcal{S}^{\prime}=\varnothing$, where we shortened $\mathcal{S}=\mathrm{supp}(p_{R})$ and $\mathcal{S}^{\prime}=\mathrm{supp}(p_{R}^{\prime})$. Also, assume that both supports are finite.
Then:

$$ $\displaystyle|\mathsf{Suf}_{p_{R}}(R_{A})-\mathsf{Suf}_{p_{R}^{\prime}}(R_{A})|$ $\displaystyle=\Big{|}\sum_{G_{A}^{\prime}\in\mathcal{S}}\Delta(G_{A},G_{A}^{ \prime})p_{R}(G_{A}^{\prime})+\sum_{G_{A}^{\prime}\in\mathcal{S}^{\prime}} \Delta(G_{A},G_{A}^{\prime})p_{R}^{\prime}(G_{A}^{\prime})\Big{|}$ (4) $$

The two sums have no terms in common, so we can independently control the second one through our choice of interventional distribution $p_{R}^{\prime}$. In fact, it is maximized by those distributions that associate all probability mass to graphs $G_{A}^{\prime}$ for which $\Delta(G_{A},G_{A}^{\prime})$ is largest, e.g., counterfactuals.
As long as at least one counterfactual $G_{A}^{\prime}$ exists that includes $R_{A}$ as a subgraph, then $p_{R}^{\prime}$ can allocate all probability mass to it, in which case the right sum becomes as large as $\operatorname*{argmax}_{{\bm{\mathrm{p}}},{\bm{\mathrm{q}}}}d({\bm{\mathrm{p}}
},{\bm{\mathrm{q}}})$, that is, as large as the natural range of the divergence $d$.

A similar reasoning applies to $\mathsf{Nec}$. Take $R_{A}$ such that for all $R_{A}^{\prime}\in\mathrm{supp}(p_{C})$ it holds that $\Delta(G_{A},G_{A}^{\prime})>\tau$ for some desired threshold $\tau$. As long as there exists a graph $G_{A}^{\prime}\supseteq C_{A}$ such that $p_{\theta}(\cdot\mid G_{A})\equiv p_{\theta}(\cdot\mid G_{A}^{\prime})$, then we can always choose an interventional distribution $p_{C}$ that allocates all mass to it. Hence, $\mathsf{Nec}_{p_{C}^{\prime}}(R_{A})=0$ and the difference in necessity will be at least $\tau$.
∎

This simple result warrants some discussion.
First, we note that the assumptions it hinges on are rather weak. Its two key requirements are that:
i) $\mathcal{S}$ and $\mathcal{S}^{\prime}$ are finite: this is the case for all existing metrics, whose interventional distributions are defined over the set of subgraphs of the input graph, which are finitely many;
ii) The GNN admits counterfactuals that subsume $R_{A}$ (for sufficiency) or inputs that subsume $C_{A}$ and map to the predicted label $\hat{y}$ (for necessity), both frequent occurrences in practice.

Second, the construction behind the proof also mimics actual differences between faithfulness metrics from the literature.
In fact, ignoring differences in choice of divergence, the main difference between unfaithfulness (which allocates non-zero probability only to subgraphs obtained by deleting features from the input), fidelity minus (which deletes all edges), and robust fidelity minus (which deletes a random subset of edges at random) is exactly their interventional distributions $p_{R}$, which also happen to have either disjoint or almost disjoint supports (in which case the a similar result applies almost verbatim).
Our construction then amounts to saying that there are many practical situations in which one can achieve good unfaithfulness and poor fidelity minus, or vice versa.

Let us briefly discuss the relationship between metrics having the same interventional distribution but different divergences $d$ and $d^{\prime}$.
On the bright side, it is easy to see that, as long as both $d$ and $d^{\prime}$ are proper divergences, an explanation $R_{A}$ achieving perfect sufficiency according to one will also attain perfect sufficiency according to the other, precisely because perfect sufficiency is attained when $\Delta(G_{A},G_{A}^{\prime})=0$ for all $G_{A}^{\prime}\sim p_{R}$, which can occur if and only if both divergenes are zero (by definition of divergence). The same holds for the degree of necessity.
For non-optimal sufficiency and necessity, the difference due to replacing divergences is governed by well-known inequalities, such as Hölder’s (between $L_{p}$ distances) and Pinsker’s (relating the $\mathsf{KL}$ to the $L_{1}$ distance).

The situation is different if $d$ is a proper divergence (say, the $\mathsf{KL}$ divergence) and $d^{\prime}$ is a difference in likelihoods. In this case, there are situations in which the two quantities can differ.
To see this, consider an multi-class classification problem, target decision $(G_{A},\hat{y})$ and a modified input $G_{A}^{\prime}\sim p_{R}$ such that i) $p_{\theta}(\hat{y}\mid G_{A})=p_{\theta}(\hat{y}\mid G_{A}^{\prime})$, but ii) the two label distributions have disjoint support. In this case, the $\mathsf{KL}$ divergence between them would be unbounded, yet the difference in likelihood would be null.
Depending on the choice of $p_{R}$, this can yield a large difference between degrees of sufficiency (and similarly for necessity).

###### Proof.

### A.2 Proof of Section 3.2

See 3.2

###### Proof.

$\mathsf{RFid}\scalebox{0.9}{+}$ corrupts the explanation $R$ by deleting edges independently at random. Formally, let $U_{j}$ be a random variable determining whether edge $e_{j}$ is kept, such that $U_{j}\sim Bernoulli(\kappa)$, with $\kappa$ a user-provided hyperparameter.
As in Section 3.2, let $\mathcal{S}_{R}$ be the set of all subgraphs of $G$ obtained by leaving the complement of $R$ unmodified, and $\mathcal{A}_{R}$ those subgraphs that lead to a large enough change in likelihood, that is, $\mathcal{A}_{R}=\{G^{\prime}\in\mathcal{S}_{R}:\Delta(G,G^{\prime})\geq\epsilon\}$, we can study $\mathsf{RFid}\scalebox{0.9}{+}$ in terms of how likely the corrupted graphs $G^{\prime}$ it samples have missing relevant edges, i.e., $P(G^{\prime}\in\mathcal{A}_{R})$.

$$ $\displaystyle P(G^{\prime}\in\mathcal{A}_{R})$ $\displaystyle=1-P(G^{\prime}\notin\mathcal{A}_{R})$ (5) $\displaystyle=1-P(U_{1}=1,\ldots,U_{m}=1)$ (6) $\displaystyle=1-\prod_{j=1}^{m}P(U_{j}=1)$ (7) $\displaystyle=1-\kappa^{m}$ (8) $$

In the second to last step, we made use of the independence of all $U_{i}$’s.
which does not depend on the number of irrelevant edges $\lVert R\rVert-r$.
∎

###### Proof.

### A.3 Proof of Section 3.2

See 3.2

###### Proof.

Let $p_{C}$ be the uniform distribution over $\mathcal{S}_{R}$. Then, the probability of sampling a perturbed graph $G^{\prime}\sim p_{C}(G)$ such that $G^{\prime}\in\mathcal{A}_{R}$ is exactly $|\mathcal{A}_{R}|/|\mathcal{S}_{R}|$.
Now, $|\mathcal{A}_{R}|$ is exactly $(2^{r}-1)\cdot 2^{\lVert R\rVert-r}$, while $|\mathcal{S}_{R}|$ is $2^{\lVert R\rVert}-1$. Hence, $\mathsf{Nec}$ depends on both the number of truly relevant edges $r$ and on the size of the explanation, as expected.
When choosing instead a budget b of deletions, and a uniform $p_{C}(G)$ over subgraphs with $\lVert G\rVert-b$ edges, $P(G^{\prime}\in\mathcal{A}_{R}^{b})=|\mathcal{A}_{R}^{b}|/|\mathcal{S}_{R}^{b}|$.
Note that $|\mathcal{S}_{R}^{b}|=\binom{\lVert R\rVert}{b}$, while $|\mathcal{A}_{R}^{b}|=\sum_{c=1}^{b}\binom{r}{c}\binom{\lVert R\rVert-r}{r-c}$.
∎

###### Proof.

### A.4 Proof of Section 4.1

See 4.1

###### Proof.

Before proceeding, it is useful to introduce the notion of computational graph, that is, the subgraph of $G_{A}$ induced by those nodes whose messages are relevant for determining the label distribution $P(Y_{u}\mid G_{A})$ or $P(Y\mid G_{A})$.
For node classification, it is easy to see that for GNNs with local aggregators, the only messages reaching $u$ are those coming from nodes within $N_{L}(u)$, and for injective GNNs all such messages impact the label distribution.
For graph classification, which is implicitly global, all nodes in the computational graph are the entirety of $G_{A}$.

Next, we show that if $R_{A}$ does not subsume the entirety of the computational graph, then when computing strict sufficiency we can always alterations those elements of the computation graph that fall in the complement $C_{A}$.
By injectivity of $p_{\theta}$, any change to the features or edges of the computational graph yields a difference in label distribution, necessarily affecting both classes, and therefore any divergence or difference in likelihood $d$.
It follows that $R_{A}$ cannot be strictly sufficient for any $d$, and therefore neither strictly faithful.

The converse also holds: if $R_{A}$ covers the entire computational graph, then it necessarily strictly sufficient. This is because the complement $C_{A}$ has no overlap with the computational graph, so altering it has no impact on the label distribution.
∎

###### Proof.

### A.5 Proof of Section 4.2

See 4.2

###### Proof.

The proof is constructive.
By assumption of stability of $f$, $R$ remains the same for every modification to $C_{A}$.
By construction, models implementing the strategies listed in Section 4.2 have the classifier $g$ using no information outside the explanation making $R_{A}$ strictly sufficient. By injectivity of $g$, $R_{A}$ is also strictly necessary.
∎

###### Proof.

### A.6 Proof of Section 5

See 5

###### Proof.

We proceed by contradiction. Let $G_{A}$ be an input graph such that the explanation $R_{A}$ for model ${p_{\theta}}$ and decision $(G_{A},\hat{y})$ is perfectly domain-invariant yet not strictly sufficient. We assume that the model prediction does not depend on domain-induced spurious information, meaning that every modification applied to $C_{A}$ will not have any impact on the model prediction (according to $d$).
However, the lack of strict sufficiency implies that $\exists G_{A}^{\prime}\in\mathrm{supp}(p_{R})$ such that $\Delta(G_{A},{G_{A}}^{\prime})>0$.
This means that there exists a perturbation outside of $R_{A}$ that altered the model prediction, which is in contradiction with assuming that it does not depend on domain-induced information.
∎

###### Proof.

### A.7 Proof of Section 5

Theorem:
Let ${p_{\theta}}$ be a deterministic DI-GNN with detector $f$ and classifier $g$ and $d$ be the difference in likelihood of the predicted label.
Also, let ${p_{\theta}}$ be Lipshitz with respect to changes to both the topology and the features of the input, that is, for every pair of graphs $G_{A}=(G,X)$ and $G_{A}^{\prime}=(G^{\prime},X^{\prime})$, it must hold that:

$$ $\displaystyle\bigg{|}{p_{\theta}}(Y\mid(G,X))-{p_{\theta}}(Y\mid(G^{\prime},X) )\bigg{|}$ $\displaystyle\leq k_{1}d_{1}(G,G^{\prime})$ (10) $\displaystyle\bigg{|}{p_{\theta}}(Y\mid(G,X))-{p_{\theta}}(Y\mid(G,X^{\prime}) )\bigg{|}$ $\displaystyle\leq k_{2}d_{2}(X,X^{\prime})$ (11) $$

for suitable distance functions $d_{1}$ and $d_{2}$.
Then:

$$ $\displaystyle\Big{|}\mathbb{E}_{(G_{A},y)\sim p^{id}}[{p_{\theta}}(y\mid G_{A} )]\ -\$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{ood}}[{p_{\theta}}(y\mid G_{A})]\Big {|}$ (12) $\displaystyle\leq\mathbb{E}_{R_{A}^{*}}[k_{1}(\lambda_{\text{topo}}^{id}+ \lambda_{\text{topo}}^{ood})+k_{2}(\lambda_{\text{feat}}^{id}+\lambda_{\text{ feat}}^{ood})+(\lambda_{\text{suff}}^{id}+\lambda_{\text{suff}}^{ood})]$ $$

Here, $k_{1},k_{2}>0$ are Lipschitz constants of ${p_{\theta}}$, $\lambda_{\text{topo}}^{id}$, $\lambda_{\text{topo}}^{id}$ $\lambda_{\text{feat}}^{ood}$, and $\lambda_{\text{feat}}^{ood}$ measure the (negated) degree of domain invariance of the detector’s output (with respect to topology and features, respectively), and $\lambda_{\text{suff}}^{id},\lambda_{\text{suff}}^{ood}$ are the degree of sufficiency for ID and OOD data.

###### Proof.

Let $f^{*}$ be an *ideal* detector that for every input $G_{A}$ outputs the maximal domain-invariant subgraph $R_{A}^{*}=(R^{*},X^{R^{*}})$.
Note that, for every $(G_{A}^{id},y^{id})\sim p^{id}$ and $(G_{A}^{ood},y^{ood})\sim p^{ood}$ that share the same invariant subgraph (that is, such that $f^{*}(G_{A}^{id})=f^{*}(G_{A}^{ood})=R_{A}^{*}$) any DI-GNN constructed by stitching together $f^{*}$ and a deterministic classifier $g$ will predict the same label distribution for both graph, i.e., $p_{g}(Y\mid f^{*}(G_{A}^{id}))\equiv p_{g}(Y\mid f^{*}(G_{A}^{ood}))$.

Now, fix any invariant subgraph $R_{A}^{*}$.
When conditioning on it, it holds:

$$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{id}(G_{A},Y\mid R_{A}^{*})}[{p_{ \theta}}(y\mid f^{*}(G_{A}^{id}))]=\mathbb{E}_{(G_{A},y)\sim p^{ood}(G_{A},Y \mid R_{A}^{*})}[{p_{\theta}}(y\mid f^{*}(G_{A}^{ood}))]$ (13) $$

where the two expectations run over ID and OOD samples that share the same invariant subgraph $R_{A}^{*}$.
We proceed by noting that:

$$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\bigg{|}{p_ {\theta}}(y\mid(R^{*},X^{R^{*}}))-{p_{\theta}}(y\mid(R,X^{R^{*}}))\bigg{|}$ $\displaystyle\leq k_{1}\underbrace{\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R _{A}^{*})}[d_{1}(R^{*},R)]}_{:=\lambda_{\text{topo}}}$ (14) $$

The expectation on the right-hand side is the average topological distance of the predicted invariant subgraphs to $R_{A}^{*}$, and will be referred to as $\lambda_{\text{topo}}$.
At the same time, it also holds that:

$$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\bigg{|}{p_ {\theta}}(y\mid(R,X^{R^{*}}))-{p_{\theta}}(y\mid(R,X^{R}))\bigg{|}$ $\displaystyle\leq k_{2}\underbrace{\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R _{A}^{*})}[d_{2}(X^{R^{*}},X^{R})]}_{:=\lambda_{\text{feat}}}$ (15) $$

where the expectation on the RHS is now the average distance between the features of the predicted invariant subgraphs and those of $R_{A}^{*}$, and will be referred to as $\lambda_{\text{feat}}$.
Combining Eq. 14 and Eq. 15 using the triangular inequality, yields:

$$ $\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\bigg{|}{p_{\theta}}(y \mid R_{A}^{*})-{p_{\theta}}(y\mid R_{A})\bigg{|}\leq k_{1}\lambda_{\text{topo }}^{id}+k_{2}\lambda_{\text{feat}}^{id}$ (16) $$

This holds for any fixed $R_{A}^{*}$.

Next, we bound the expected difference between the label distribution determined by $R_{A}$ and that determined by $G_{A}$ using the degree of sufficiency.
For notational convenience, we draw complements $C_{A}^{\prime}$ rather than full modified graphs $G_{A}^{\prime}$ from $p_{R}$, and we denote the operation of joining $R_{A}$ and $C_{A}^{\prime}$ to form $G_{A}^{\prime}$ with the $\cup$ operator, and where we use the difference in prediction likelihood as divergence $d$.
We proceed as follows:

$$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\bigg{|}{p_ {\theta}}(y\mid R_{A})-{p_{\theta}}(y\mid G_{A})\bigg{|}$ (17) $\displaystyle=\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\bigg{|} \mathbb{E}_{C_{A}^{\prime}\sim p_{R}(G_{A})}\big{[}{p_{\theta}}(y\mid R_{A} \cup C_{A}^{\prime})\big{]}-{p_{\theta}}(y\mid G_{A})\bigg{|}$ (18) $\displaystyle\leq\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\mathbb {E}_{C_{A}^{\prime}\sim p_{R}(G_{A})}\bigg{|}{p_{\theta}}(y\mid R_{A}\cup C_{A }^{\prime})-{p_{\theta}}(y\mid G_{A})\bigg{|}$ (19) $\displaystyle=\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\mathsf{ Suf}(R_{A}):=\lambda_{\text{suff}}$ (20) $$

In the first to second step, we made use of the law of total probability and the product rule, for which:

$$ $\displaystyle{p_{\theta}}(y\mid R_{A})$ $\displaystyle=\sum_{C_{A}^{\prime}}p(y,C_{A}^{\prime}\mid R_{A})=\sum_{C_{A}^{ \prime}}\frac{p(y,C_{A}^{\prime},R_{A})}{p(R_{A})}=\sum_{C_{A}^{\prime}}\frac{ p(y\mid C_{A}^{\prime},R_{A})p(C_{A}^{\prime}\mid R_{A})p(R_{A})}{p(R_{A})}$ (22) $\displaystyle=\sum_{C_{A}^{\prime}}{p_{\theta}}(y\mid R_{A}\cup C_{A}^{\prime} )p_{R}(C_{A}^{\prime})=\mathbb{E}_{C_{A}^{\prime}\sim p_{R}}{p_{\theta}}(y\mid R _{A}\cup C_{A}^{\prime})$ (23) $$

Then, applying again the triangular inequality between Eq. 17 and Eq. 16 yields:

$$ $\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}\bigg{|}{p_{\theta}}(y \mid R_{A}^{*})-{p_{\theta}}(y\mid G_{A})\bigg{|}\leq k_{1}\lambda_{\text{topo }}^{id}+k_{2}\lambda_{\text{feat}}^{id}+\lambda_{\text{suff}}^{id}.$ (24) $$

The same derivation applies to $p^{ood}(G_{A})$, so we obtain:

$$ $\mathbb{E}_{(G_{A},y)\sim p^{ood}(\cdot\mid R_{A}^{*})}\bigg{|}{p_{\theta}}(y \mid R_{A}^{*})-{p_{\theta}}(y\mid G_{A})\bigg{|}\leq k_{1}\lambda_{\text{topo }}^{ood}+k_{2}\lambda_{\text{feat}}^{ood}+\lambda_{\text{suff}}^{ood},$ (25) $$

Combining these two bounds using the triangular inequality one last time, we derive:

$$ $\displaystyle\bigg{|}\mathbb{E}_{(G_{A},y)\sim p^{id}(\cdot\mid R_{A}^{*})}{p_ {\theta}}(y\mid G_{A})-$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{ood}(\cdot\mid R_{A}^{*})}{p_{\theta }}(y\mid G_{A})\bigg{|}$ (26) $\displaystyle\leq k_{1}(\lambda_{\text{topo}}^{id}+\lambda_{\text{topo}}^{ood} )+k_{2}(\lambda_{\text{feat}}^{id}+\lambda_{\text{feat}}^{ood})+(\lambda_{ \text{suff}}^{id}+\lambda_{\text{suff}}^{ood}).$ $$

Again, this holds for all choices of $R_{A}^{*}$.

Finally, we leverage these inequalities to bound the difference in likelihood between ID and OOD data as follows:

$$ $\displaystyle\mathbb{E}_{R_{A}^{*}}\left[\left|\mathbb{E}_{(G_{A},y)\sim p^{id }(\cdot\mid R_{A}^{*})}{p_{\theta}}(y\mid G_{A})-\mathbb{E}_{(G_{A},y)\sim p^{ ood}(\cdot\mid R_{A}^{*})}{p_{\theta}}(y\mid G_{A})\right|\right]$ (27) $\displaystyle\geq\bigg{|}\mathbb{E}_{R_{A}^{*}}\left[\mathbb{E}_{(G_{A},y)\sim p ^{id}(\cdot\mid R_{A}^{*})}{p_{\theta}}(y\mid G_{A})-\mathbb{E}_{(G_{A},y)\sim p ^{ood}(\cdot\mid R_{A}^{*})}{p_{\theta}}(y\mid G_{A})\right]\bigg{|}$ (28) $\displaystyle=\bigg{|}\mathbb{E}_{(G_{A},y)\sim p^{id}}{p_{\theta}}(y\mid G_{A })-\mathbb{E}_{(G_{A},y)\sim p^{ood}}{p_{\theta}}(y\mid G_{A})\bigg{|}$ (29) $$

where $\mathbb{E}_{R_{A}^{*}}$ runs over all possible maximally invariant subgraphs and no longer depends on the specific choice of
$R_{A}^{*}$.
By monotonicity of the expectation we conclude that:

$$ $\displaystyle\bigg{|}\mathbb{E}_{(G_{A},y)\sim p^{id}}{p_{\theta}}(y\mid G_{A})-$ $\displaystyle\mathbb{E}_{(G_{A},y)\sim p^{ood}}{p_{\theta}}(y\mid G_{A})\bigg{|}$ (30) $\displaystyle\leq\mathbb{E}_{R_{A}^{*}}\left[k_{1}(\lambda_{\text{topo}}^{id}+ \lambda_{\text{topo}}^{ood})+k_{2}(\lambda_{\text{feat}}^{id}+\lambda_{\text{ feat}}^{ood})+(\lambda_{\text{suff}}^{id}+\lambda_{\text{suff}}^{ood})\right]$ (31) $$

∎

###### Proof.

## Appendix B Experimental Details

### B.1 Datasets

In this study, we conduct an investigation across seven graph classification datasets commonly used for evaluating SE-GNNs and DI-GNNs. Specifically, we examine three synthetic datasets and four real-world datasets, and in the following paragraphs, we provide a detailed description of each.

#### Synthetic datasets

- •
BaMS [] is a synthetic dataset consisting of 1,000 Barabasi-Albert (BA) graphs, each with network motifs (house, grid, wheel) randomly attached at various positions. Class 0 includes plain BA graphs and BA graphs enriched with either a house, a grid, a wheel, or all three motifs together. Class 1 consists of BA graphs enriched with a combination of two motifs: a house and a grid, a house and a wheel, or a wheel and a grid. This dataset is utilized in the context of self-explainable Graph Neural Networks (GNNs), with the expected ground truth explanations being the specific motif combinations in each class.
- •
Motif2-Basis [] is a synthetic dataset comprising 24,000 graphs categorized into three classes. Each graph consists of a basis and a motif. The basis can be a ladder, a tree (or a path), or a wheel. The motifs are a house (class 0), a five-node cycle (class 1), or a crane (class 2). The dataset is divided into training (18,000 graphs), validation (3,000 graphs), and test sets (3,000 graphs).
In the context of OOD analysis, two additional sets are considered: the OOD validation set and the OOD test set. In these sets, the class-discriminative subgraph $R_{A}$ (i.e., the motifs) remains fixed, while the bases are varied. Specifically, the basis for the OOD validation set (3,000 graphs) is a circular ladder, and the basis for the OOD test(3,000 graphs) set is a Dorogovtsev-Mendes graph.[].
- •
Motif-Basis [] is specular to Motif2-Basis, where the OOD test set contains graphs generated connecting the three motifs above to simple line paths of varying length.
- •
Motif-Size [] is a synthetic dataset consisting of 24,000 graphs categorized into three classes. Similar to Motif2-Basis, each network is composed of a basis and a motif, with the motif serving as the class-discriminative subgraph $R_{A}$. The basis structures include a ladder, a tree (or a path), a wheel, a circular ladder, or a star. The motifs are a house (class 0), a five-node cycle (class 1), or a crane (class 2). The dataset is divided into training (18,000 graphs), validation (3,000 graphs), and test sets (3,000 graphs).
In the context of OOD analysis, the size of the basis is increased. Specifically, in the OOD validation set (3,000 networks), the basis sizes are increased up to three times their original size, while in the OOD test set (3,000 networks), the basis sizes are increased up to seven times.

#### Real-world datasets

- •
BBBP [] is a dataset derived from a study on modeling and predicting barrier permeability []. It comprises 2,050 compounds, with 483 labeled as positive and 1,567 as negative.
- •
CMNIST [] contains 70,000 graphs of hand-written digits transformed from the MNIST database using superpixel techniques[]. The digits are colored according to their domains and concepts. In the training set, which contains 50,000 graphs, the digits are colored using five different colors. To evaluate the model’s performance on out-of-distribution data, the validation and testing sets each contain 10,000 graphs with two new colors introduced specifically for these sets.
- •
LBAPcore [] is a molecular dataset consisting of 34,179 graphs sourced from the 311 largest chemical assays. The validation set comprises 19,028 graphs from the next largest 314 assays, while the test set includes 19,302 graphs from the smallest 314 assays.
- •
SST2 is a sentiment analysis dataset based on the NLP task of sentiment analysis, adapted from the work of Yuan et al. []. In this dataset, each sentence is transformed into a grammar tree graph, where individual words serve as nodes and their associated word embeddings act as node features. The primary task is a binary classification to predict the sentiment polarity of each sentence.The dataset comprises 70,042 graphs, divided into training, validation, and test sets. The out-of-distribution (OOD) validation and test sets are specifically created to evaluate performance on data with longer sentence lengths.

### B.2 Implementation Details

#### Training and reproducibility

The models are developed leveraging repositories provided by previous work. Specifically:

- •
CIGA, LECI and GSAT are developed based on the repository from [], using commit fb39550453b4160527f0dcf11da63de43a276ad5.
- •
RAGE is implemented using the code available at https://anonymous.4open.science/r/RAGE as described in [].
- •
For GISST, we use the repository from https://anonymous.4open.science/r/SEGNNEval, following the approach outlined in [].

To encourage reproducibility, we stick to the hyperparameters provided in each respective repository. Model selection was performed on the ID validation set.

#### Computing faithfulness

Our practical implementation of $\mathsf{Nec}$ follows the guidelines presented in Section 3.2. The idea is that choosing a fixed budget depending, for example, on a dataset-wide statistic is a simple yet sensible choice for a necessity metric properly accounting for the number of irrelevant edges present in an explanation.
Specifically, we chose the budget b as a fixed proportion of the average number of undirected edges for each split of the dataset, where the proportion ratio is set to $5\%$ in all our experiments. For each explanation, we sample a number $q_{1}$ of intervened graphs, where $q_{1}$ is fixed at $8$ in our experiments.

For $\mathsf{Suf}$, instead, we replace the complement of the explanation with that of a random sample from the same data split, joining with random connections the original explanation with the sampled complement. We repeat this operation for a number $q_{1}$ of samples for each explanation, where $q_{1}$ is fixed at $8$ in our experiments, as for $\mathsf{Nec}$.

The final faithfulness corresponds to the harmonic mean of the normalized $\mathsf{Nec}$ and normalized $\mathsf{Suf}$ scores, where we set $d$ as the $L_{1}$ divergence for both metrics, and it is computed over a subset of $q_{2}$ of input graphs, which is set to $800$ in our experiments. An ablation study to compare the resulting scores across a varying number of samples $q_{2}$ and interventions $q_{1}$ is provided in LABEL:fig:ablation_numsaplaes and LABEL:fig:ablation_expval.

#### Computing the degree of invariance

The degree of invariance appearing in Section 5 represents how close the predicted subgraph $R_{A}$ is to the truly domain-invariant input motif, which is assumed to be the only stable factor enabling for stable predictions across domains. Carrying over the terminology from XAI, we compute this quantity as the *plausibility* [] of the provided subgraph with respect to a known ground truth. Specifically, we compute the topology-wise degree of invariance as the Weighted Intersection over Union (WIoU) between the provided explanation relevance score, and the expected ground truth scores, which equal $1$ for the invariant edges in the graph, and 0 0 for the others. The feature-wise degree of invariance, instead, is unmeasured as the ground truth over invariant features is typically overlooked, and no settled evaluation testbed is available.

#### Implementation of faithfulness-enforcing strategies

As stated in Section 4.2, we modified the official source code of several models to implement the strategies proposed in Proposition 4.2.

- •
Explanation Readout (ER)
The Explanation Readout strategy computes the graph embedding by applying an aggregator solely to $R_{A}$. This involves multiplying the node mask with the node embedding before performing the final global readout. Since explanations are soft scores over $G_{A}$, this approach ensures the model adheres more closely to the soft mask.
- •
Hard Scores (HS)
To enforce the generation of binary 0-1 explanation masks by the detector $f$, we apply a technique similar to the Straight-Through (ST) trick used in the discrete Gumbel-Softmax Estimator []. Specifically, during the forward pass, we utilize the binary version of the mask, while in the backward pass, we use the continuous version.
- •
Local $\mathsf{aggr}$ (LA)
To enhance the expressivity of Graph Neural Networks (GNNs), some models incorporate virtual nodes [, , ]. We remove these virtual nodes to mitigate the risk of mixing the information of the explanation with that of its complement, which can create unwanted dependencies between pairs of nodes in the graph.

#### Changes with respect to the original codebase

Here we describe two minor changes we did to the original codebas.
Stable TopK & Permutation-Invariant Metrics. We found the original implementation of the topK operator to exhibit instabilities when used on GPU, in particular in the presence of equal scores for which alternatively the first or the last elements of the tensor are returned.
This results in order-dependent metric values, either over -or under-estimated according to the order of ground truth edges in the graph(^7^77In synthetic datasets, ground truth edges are typically the last elements as they are attached to an already generated base-graph.).

To avoid this bias and to have more predictable behavior, we switched to a stable implementation of the topK operator which always selects elements with the same score as they appear in the input tensor, and we randomly permute nodes and edges in each graph at loading time.

Undirected Explanation Scores. Accordingly to the original version of the codebase introduced in Training and Reproducibility paragraph, LECI, and GSAT are averaging the edge attention scores among directions for each undirected edge via torch_sparse.transpose. However, we found that, even by sticking to the original package versioning, the way torch_sparse.transpose is used is not weighting edge scores as expected, but rather is acting as an identity mapping. To fix this bug and to produce undirected edge scores without changing the edge attention mechanism, we average the edge scores via torch_geometric.to_undirected. More details are available in our codebase.

Table 5 compares performance scores for directed vs undirected explanation scores showing comparable performance aggregated over all datasets and models.

**Table 5: Model performance scores for directed vs undirected explanation scores. Models labeled with ’(D)’ use directed edge scores.**
| Dataset / Model | LECI | CIGA | GSAT | LECI (D) | CIGA (D) | GSAT (D) |
| --- | --- | --- | --- | --- | --- | --- |
| Motif-Basis | 72 $\pm$ 06 | 42 $\pm$ 02 | 57 $\pm$ 03 | 82 $\pm$ 05 | 50 $\pm$ 05 | 52 $\pm$ 04 |
| Motif2-Basis | 85 $\pm$ 07 | 46 $\pm$ 10 | 75 $\pm$ 06 | 81 $\pm$ 06 | 40 $\pm$ 03 | 77 $\pm$ 05 |
| Motif-Size | 41 $\pm$ 06 | 43 $\pm$ 05 | 51 $\pm$ 03 | 54 $\pm$ 06 | 47 $\pm$ 02 | 52 $\pm$ 04 |
| SST2-Length | 83 $\pm$ 01 | 76 $\pm$ 06 | 79 $\pm$ 04 | 83 $\pm$ 01 | 77 $\pm$ 04 | 81 $\pm$ 02 |
| LBAPcore-Assay | 71 $\pm$ 00 | 69 $\pm$ 01 | 70 $\pm$ 00 | 72 $\pm$ 00 | 70 $\pm$ 01 | 71 $\pm$ 00 |
| CMNIST-Color | 26 $\pm$ 10 | 23 $\pm$ 03 | 25 $\pm$ 04 | 28 $\pm$ 17 | 21 $\pm$ 03 | 38 $\pm$ 04 |

## Appendix C Further Experiments

### C.1 Failure case

**Table 6: Model performance scores for SST2-Length on ID validation set and OOD test set.**
| Dataset / Model | GIN | LECI | GSAT |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| ID val. | OOD test | ID val. | OOD test | ID val. | OOD test |  |
| SST2-Length | 91 $\pm$ 00 | 80 $\pm$ 01 | 92 $\pm$ 00 | 83 $\pm$ 01 | 91 $\pm$ 00 | 79 $\pm$ 04 |

As discussed in Section 4.2, SST2-Length is a particularly challenging dataset for improving faithfulness.
We claim this may come from the task benefiting from global information being used, which clashes with the goal of modular architectures that seek sparse and local discriminative subgraphs.
Consider, in fact, the results reported in Table 6 where even a simple monolithic GNN baseline trained without any invariance-aware strategies exhibits comparable performance compared to more advanced and complex DI-GNNs.
To inspect where DI-GNNs fall short, we plot in LABEL:fig:expl_histograms the distribution of edge scores predicted by the detector of LECI and GSAT, where it is clear that they failed in identifying any sparse invariant subgraph, therefore falling back to a regular-GNN-like behavior. This is especially expected for SST2-Length, which is a graph-adapted sentiment classification dataset where node features are contextual embeddings extracted from a BERT-like Transformer [] – which produces intrinsically globally-correlated node representations by the nature of its self-attention layers []. Indeed, BERT-like Transformers are the models achieving state-of-the-art performance in this task [].

Figure: Figure 4: Probability of deleting at least one truly relevant edge is independent of the number of irrelevant edges if the deletion budget depends on the explanation size. Given an explanation $R$ with $r$ truly relevant edges ($r=5$), and a budget b proportional to the size of the explanation, the plot shows $P(R^{\prime}\in\mathcal{A}^{b}(R^{\prime}))$ where $R^{\prime}\sim p_{C}^{b}(G)$, for a growing number of irrelevant edges in $R$. The plot shows that the probability is approximately constant, i.e., it does not depend on the number of irrelevant edges. The segments with decreasing behaviour (especially visible for a $10\%$ budget, the blue curve) correspond to areas where the budget is indeed constant, and thus not proportional to the explanation size. For instance, between 1 and 14 irrelevant edges, a budget of $10\%$ corresponds to deleting one edge.
Refer to caption: x3.png

### C.2 Sensitivity of 𝖱𝖥𝗂𝖽 ⁢ + 𝖱𝖥𝗂𝖽 + \mathsf{RFid}\scalebox{0.9}{+} sansserif_RFid + and 𝖭𝖾𝖼 𝖭𝖾𝖼 \mathsf{Nec} sansserif_Nec to the explanation size

In Fig. 4, we numerically simulate the probability of deleting at least one truly relevant edge from an explanation with a growing number of irrelevant ones. The figure shows that the probability is basically insensitive to the number of irrelevant edges.

In Fig. 1 (Right) we provided an experiments showing that for GSAT, $\mathsf{RFid}\scalebox{0.9}{+}$ is in fact insensible to the number of irrelevant edges in the explanation, while $\mathsf{Nec}$ with a suitable $p_{C}$ is not. In LABEL:fig:sampling_strategies_nec and LABEL:fig:sampling_strategies_nec2 we further show that this behavior is in fact general, and occurs across different models and datasets. Specifically, for the same setting delineated in Section 3.2, we report the results also for the LECI [] model over LBAPcore-Assay [] molecular benchmark.

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: See in Weaknesses.
soundness: 2
strengths: This paper addresses a timely and impactful topic by exploring the limitations of current metrics used to evaluate the faithfulness of explanations in GNNs. The paper presents a range of experiments to support these claims, adding depth and rigor to the discussion.
summary: This paper addresses a timely and impactful topic by exploring the limitations of current metrics used to evaluate the faithfulness of explanations in graph neural networks (GNNs). The authors make three primary contributions: they highlight that existing metrics are not interchangeable, challenge the assumption that faithfulness should always be a design goal, and link faithfulness to out-of-distribution generalization.
weaknesses: 1. Clarity in Introduction: The logical flow between sentences in the introduction could be strengthened. For example, the connection between lines 35 and 36 feels disjointed, affecting readability and coherence.

2. Writing Clarity: There are instances of unclear terminology and abbreviations. For instance, the abbreviation “cf.” on line 46 may be confusing. Additionally, on line 77, there’s a mixture of notation, specifically "|G|" and "∥G∥", which could be standardized for consistency.

3. Lack of Proposed Solutions: 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. Presenting an alternative would strengthen the contributions and provide practical guidance for future research.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Please look at the weaknesses for open questions.
soundness: 3
strengths: 1. The paper is well-written and the motivation is very clear.

2. The authors detail the importance of the faithfulness metric in graph explanations, highlighting the pitfalls of diverse metrics and the trade-offs between them.

3. The paper presents an interesting analysis between regular, self-explainable, and domain-invariant graph neural networks.
summary: Faithfulness has been one of the widely used metrics in explainable artificial intelligence research. Intuitively, an explanation is said to be faithful if it accurately reflects the true reasoning process of the underlying model. However, the investigation of faithfulness with respect to graph neural networks has been limited to empirical analysis of generated explanations and proposing new metrics. In this work, the authors highlight the difference between existing faithfulness metrics and argue about the trade-off between them, i.e., existing faithfulness metrics are at odds with each other. Further, the authors show that optimizing for faithfulness is not ideal and leads to a trade-off between the expressiveness of the model and usefulness of faithful explanations.
weaknesses: 1. The relation between faithfulness and out-of-distribution performance is unclear. The statement "faithfulness is tightly linked to out-of-distribution generalization" is weak and doesn't highlight the exact implication of faithfulness on OoD performance. While the authors show the analysis in Section 5, it would be beneficial to the readers if the authors could provide a brief explanation describing this relation in simple terms.

2. The paper lacks a clear description and implication of 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 with respect to the GNN, explanation, and faithfulness. Addressing this will make the theoretical analysis of the paper much stronger.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: See the weaknesses
soundness: 3
strengths: 1. The paper show that a) existing metrics are not interchangeable. b) optimizing for faithfulness is not always a sensible design goal. c). faithfulness is tightly linked to out-of-distribution generalization. The novelty is good.
2. The paper present an in-dept analysis of existing graph XAI metrics.
3. The experiments are solid.
summary: This paper studies the faithfulness of explanations in modular GNNs. It addresses several problems in explanation metrics, and claims through analysis: 1) not all metrics are the same; 2) faithfulness metrics are not interchangeable; not all metrics are equally reliable; 3) for regular injective GNNs, strict faithful explanations are trivial. Finally, it claims faithfulness is key to OOD generalization. Extensive experiments justify the claims in the paper.
weaknesses: 1. After reading the paper, I am in question of what metrics are suggested for a GNN explanation task. Considering a normal setting, a post-hoc explainer for a trained to-be-explained GNN, how to choose the metric? Can you draw a clear conclusion throughout the analysis in the paper? Therefore, I question the significance of the paper. To improve the paper, 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 (e.g., modular GNNs).
2. In section5, 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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please address the concerns and questions in the *weakness* part.
soundness: 2
strengths: 1. GNN explanations' faithfulness is crucial in real-world applications and academic research.

2. The experiments on four popular datasets including Motif2 show an empirical evaluation of the proposed method.
summary: In this paper, the authors study the faithfulness of explanations generated concerning Graph Neural Networks (GNNs). Specifically, they claim the following main contributions:

1. They claim that current faithfulness metrics are *not interchangeable* and cannot evaluate the explanation quality precisely. These differences can cause the explanations to ignore important elements.
2. They prove that perfectly faithful explanations may be completely uninformative in injective GNNs.
3. They explore the connections between faithfulness and domain invariance.
weaknesses: > W1. Concerning contribution 1:

They claim that current faithfulness metrics are **not interchangeable** and cannot evaluate the explanation quality precisely. In other words, the faithfulness performance of an explanation can vary concerning different metrics (Proposition 1 and Sec. 3.1).

However, "faithfulness" naturally can be evaluated by various metrics, and it is **unnecessary** that the evaluation results should be consistent with each other. 

Take the ranking similarity metrics as an example: top-k intersection (precision at k), cosine similarity, NDCG, and other metrics can lead to different results. E.g., ranking A is more similar to ranking B by top-k, while ranking C is more similar to ranking B by cosine similarity, and the divergence among metric results can vary as large as possible. Similar cases can be found in prediction performance cases.


> W2: Concerning contribution 2:

They prove that perfectly faithful explanations may be completely uninformative in injective GNNs (Prop. 4).

However, the details are missing and hard to follow. Specifically, which faithfulness metric is adopted, and what does "match" mean in "$p_r$ matches $N_L(u)$" and "$p_R$ matches $G_A$"?


> W3. Concerning the target tasks:

Are the graph- or node-level classification tasks considered? Definition 1 will be strict for graph-level tasks, especially when the "output" is the distributions rather than categories.

> W4. Concerning the experiments:

The purpose of some experimental results is unclear. 

One of the contributions is the new faithfulness metric (as well as Nec and Suf), while their superiority is not explored by further experiments. 

Instead, in Table 3 and Table 4, the authors evaluate GSAT (and other backbone models) with/without augmentations by Acc and faithfulness. These models may achieve better or worse performance while their connections to the paper's key contribution are unclear. Besides, the relationship between Acc and faithfulness is underexplored.

In other words, the paper proposes to "reconsider" the faithfulness metric, while comprehensive experiments of comparing metrics are missing.

> W5. Concerning the writing:

W5a. Most figures and tables are really far away from their corresponding statements, requiring to jump over the pages repeatedly.

W5b. Some key statements are missing, e.g., the choice of d in Lines 279, and what does "value" mean in the y-axis? 

W5c. Are the graph- or node-level classification tasks considered? Or do different propositions/statements fit different tasks?

Meta-review: This is an important and timely contribution to faithfulness in GNNs. The Reviewers are unanimously in support of accepting the paper post-rebuttal, and I believe it will spark important discussions at the conference. A clear accept.

Decision: Accept (Poster)