Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs
Authors: Steve Azzolin
Antonio Longa
Stefano Teso
Andrea Passerini
Venue: ICLR 2025 Poster (2025)
Keywords: Explainability
Trustworthiness
Faithfulness
Self-Explainable GNNs
Primary area: learning on graphs and other geometries & topologies
TL;DR: What is faithfulness exactly? We provide an answer to this question by providing a unified view of existing metrics, studying its role in self-explainable and domain-invariant modular GNNs.

Abstract: As Graph Neural Networks (GNNs) become more pervasive, it becomes paramount to build reliable tools for explaining their predictions.
A core desideratum is that explanations are *faithful*, i.e., that they portray an accurate picture of the GNN's reasoning process.
However, a number of different faithfulness metrics exist, begging the question of what is faithfulness exactly and how to achieve it.
We make three key contributions.
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 *systematically ignore important properties of explanations*.
We proceed to show that, surprisingly, *optimizing for faithfulness is not always a sensible design goal*.  Specifically, we prove that for injective regular GNN architectures, perfectly faithful explanations are completely uninformative.
This does not apply to modular GNNs, such as self-explainable and domain-invariant architectures, prompting us to study the relationship between architectural choices and faithfulness.
Finally, we show that *faithfulness is tightly linked to out-of-distribution generalization*, in that simply ensuring that a GNN can correctly recognize the domain-invariant subgraph, as prescribed by the literature, does not guarantee that it is invariant unless this subgraph is also faithful.
All our code can be found in the supplementary material.

Published as a conference paper at ICLR 2025
RECONSIDERING FAITHFULNESS IN REGULAR, SELF- SELF-EXPLAINABLE, AND DOMAIN INVARIANT GNNS
Steve Azzolin"
Antonio Longa*
Stefano Teso"
Andrea Passerini"
ABSTRACT
As Graph Neural Networks (GNNs) become more pervasive, it becomes paramount to build reliable tools for explaining their predictions. A core desideratum is that explanations are faithful, Le., that they portray accurate picture of the GNN's reasoning process. However, a number of different faithfulness metrics exist, begging the question of what is faithfulness exactly and how achieve it. We make three key contributions. We begin by showing that existing metrics are not interchungeable i.e., explanations attaining high faithfulness according to one metric may be unfaithful according to others and can systematically ignore important properties of explanations. We proceed to show that, surprisingly, optimizing for faithfulness is not always a sensible design goal. Specifically, we prove that for injective regular GNN architectures, perfectly faithful explanations are completely uninformative. This does not apply to modular GNNs, such as self-explainable and domain-invariant architectures, prompting us to study the relationship between architectural choices and faithfulness. Finally, we show that faithifulness is rightly linked to out-of-distrnn offdiistribttion generalization, in that simply ensuring that GNN correctly recognize the domain-invariant subgraph, prescribed by the literature, does not guarantee that it is invariant unless this subgraph is also faithful. The code is publicly available on GitHub'.
INTRODUCTION
The increasing popularity of GNNs (Scarselli et al., 2008; Kipf and Welling, 2016; Veličković et al., 2018) 8) for even high-stakes tasks (Agarwal et al., 2023) has prompted the development of tools for explaining their decisions. Regular GNNs are opaque that their decisions can only explained in post-hoc fashion using specialized tools (Longa et al., 2024), whereas self-explainable GNNs are designed to natively output explanations for their predictions (Kakkad et al., 2023). key metric for evaluating explanations is faithfulness (Pope al., 2019; Yuan et al., 2022; Amara al., 2022; Zhao et al., 2023; Tan et al., 2022: Zheng et al., 2023). Intuitively, an explanation is faithful as long as highlights all and only those elements edges and/or node features of the input graph that truly relevant for the prediction. Faithful explanations, therefore, portray an accurate picture of the GNN's working and thus support understanding, trust allocation, and debugging (Teso al., 2023).
Existing faithfulness metrics assess the stability of the model's output to perturbations of the input -e.g., to ensure that modifying the elements marked irrelevant by the explanation has in fact no effect - yet differ in many non-trivial details. For instance, some metrics perturb the input by zeroing out all irrelevant node features (Agarwal al., 2023) while others delete subset of edges (Zheng et al., 2023); see Section 3 for an overview. Unfortunately, the literature provides little guidance on selecting appropriate metrics and tuning GNN architectures for faithfulness.
Not all metrics are the same. (Section 3) 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 may not be faithful according to others. These differences are far reaching. In fact, we show that different metrics can rank explanation algorithms differently and that popular metrics can be systematically insensitive to the number of irrelevant elements captured by the explanation.
We begin by parameterizing existing metrics along two
University of Trento, (name. surnasue Qunaat..iiuniini.i hhtpps//gg wttp://cc.oeeeeeeee///////////// http:/ttwww....eeeeeeeee/ooottta

---

Published as a conference paper at ICLR 2025
It follows that faithfulness measurements cannot be interpreted unless their parameters are known: this is relevant when evaluating XAI algorithm and in high-stakes applications, like loan approval, where explanation providers could manipulate (but withhold) the parameters to mislead end-users into overestimating the faithfulness of their explanations (Bordt et al., 2022).
Is faithfulness always worth optimizing for? (Section 4) Then, we study to what extent optimizing for faithfulness a sensible design goal. We show that for GNNs satisfying injectivity, explana- tions achieving perfect faithfulness are not informative, and identify a natural trade-off between expressiveness of the model and usefulness of faithful explanations. At the same time, we show that for self- celf-exlainnable GNNs and domain invariant GNNs, which employ modular architecture, strict faithful explanations can be informative, and evaluate how architectural design choices can impact faithfulness, highlighting how popular models implicitly penalize faithfulness.
Faithfulness is key to OOD generalization. (Section 5) Finally, we highlight the central but so far neglected role of faithfulness in domain invariance. Prior work (Cai et al., 2023; Chen al., 2023; Gui et al., 2023; Jiang et al., 2023) tackles domain invariance by constructing modular GNNs that isolate the domain invariant portion of the input and use it for prediction. We show that extracting domain invariant subgraph is not enough for GNN to be truly domain invariant: unless the subgraph is also faithful, the information from the fomain-dependee influence the prediction, thus preventing domain invariance. This reveals key limitation of current design and evaluation strategies for domain-invarian GNNs, which neglect faithfulness altogether.
components of the imput can still
Overall, our hope is that these contributions will prompt researchers to reconsider faithfulness in a broad sense, i.e., to reconsider i) how it should be computed, äi how GNN architectures should achieving it, and iii) its role outside of the XAI literature.
2 GRAPH NEURAL NETWORKS AND FAITHFULNESS
Throughout, we indicate graphs as G = E) and annotated graphs GA XG,X), where Xa E IR are per-node features. We denote multisets as (f...)), the k-hop neighborhood of u as (u), and shorten N1 (u) to (u)), and ||G|| = [ to
Graph Neural Networks (GNN) (Scarselli et al., 2008) are discriminative classifiers that, given an input graph Ga, define conditional distribution po(. Ga) over candidate labels. In graph classification, the label y E {1..... c} applies to the whole graph, while in node classification vector y E {l....,d c) with one element per node. Inference in GNNs opaque, in that relies on message passing of embedding vectors along the graph's topology. Usually, this amounts to recursively applying an
operation of the form:
h update(h" (-1 aggr
aggr(((h) (Hh, E N()))))
to all nodes u, from the bottom to the top layer. Here, h² x. the node features, h. the node embeddings at the f-th layer, update a learnable non-linear function, and aggr a permutation- invariant neighborhood aggregator (Bacciu et al., 2020; Bronstein et al., 2021). We refer to this form of aggregation as local, as opposed to non-local aggregation where aggr runs over nodes outside of N (u), e.g., via virtual nodes (Sestak et al., 2024). In node classification, the top-layer embeddings are stacked into a matrix H E Raxd which is fed to dense layer to obtain a label distribution Po G = softmax H WW), where W E dx are weights. In graph classification, they are aggregated into an overall embedding h = (ggra(((())) : u E V)), also fed to a dense layer.
Explanations and Faithfulness. There exist number of post-hoc techniques (Longa et al., 2024; Agarwal et al., 2023; Kakkad et al., 2023) that given a GNN ps can extract local explanation for any target decision (G .) These explanations identify subgraph RA of GA 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 say they are not faithful to the GNN's reasoning process (Longa et al., 2024; Agarwal et al., 2023). Lack of faithfulness hinders understanding. trust modulation, and debugging (Teso et al., 2023).
This has prompted the development of self-explainable GNNs (SE-GNNs), a class of GNNs that natively output explanations without any post-hoc analysis (Kakkad et al., 2023; Christiansen et al., "The tacit assumption in the XAI and domain invariance literature that these elements exists.
2

---

Published as a conference paper at ICLR 2025
2023). SE-GNNs comprise two modules: the detector f extracts a class ditsimiisrim subgraph RA from the imput, and the classifier 9 uses RA, and only RĄ, to infer a prediction. In this context, RA acts local explanation. Both modules are GNNs, and the detector is encouraged to output human interpretable explanations by leveraging attention (Miao et al., 2022a; Lin et al., 2020; Serra and Niepert, 2022; Wu et al., 2022). high-level concepts prototypes (Zhang al., 2022; Ragno et al., 2022; Dai and Wang, 2021; 2022; Magister et al., 2022), or other techniques (Yu et al., 2020; 2022; Miao et al., 2022b; Giunchiglia et al., 2022).
In practice, the detector outputs per-element relevance scores (usually in [o, 1), which are then used to identify an explanation subgraph RA via, e.g., thresholding or topK. Importantly, the node features X R|Ra|xd xx of R. are derived from, but not necessarily identical to, those of G These remarks will become relevant when discussing strategies for improving faithfulness in Section 4.2.
Domain Invariance. Domain-invariant GNNs (DI-GNNs) aim to generalize across related domains (Cai et al., 2023; Chen et al., 2023; Gui et al., 2023; Jiang et al., 2023). The underlying assumption is that the label y depends only on (hidden) comain--nvarian factors, while the input graph GA is contaminated by domain-dependent elements. The literature suggests that, in order to generalize across domains, DI-GNNs have to be plausible, that is, they should recover the (unobserved) truly invariant subgraph as well as possible (Schölkopf et al., 2021; Jiang et al., 2023).
Like SE-G SE-GNNs, DI-GNNS are modular, i.e., they pair a detector f for identifying the invariant subgraph RA, which plays the role of an explanation, with classifier taking RA as input. The detector is encouraged to output highly plausible subgraphs through specialized regularization terms and training strategies (Li et al., 2022: Chen et al., 2022: 2023; Gui et al., 2023). We will show in Section that this is not enough to ensure the model as a whole is domain invariant.
ARE ALL FAITHFULNESS METRICS THE SAME?
In the remainder, we fix a GNN pa and decision (G 9) and study the faithfulness of corre- sponding local explanation Ra- Intuitively, an explanation is faithful insofar as it is sufficient, ie.. keeping fixed shields the model's output from changes to its complement CA. and necessary, i.e. altering it affects the model's s output even if the complement C'A is kept fixed (Watson et al., 2021; Beckers, 2022; Marques-Sin Silva and Ignatiev, 2022; Darwiche and Hirth, 2023).
Definition 1. An explanation RA is strictly sufficient if no change to the complement CA does induce any change in the model's ss output, strictly necessary all changes to the explanation do, and strictly faithful if it satisfies both conditions.
Existing metries make these notions practical by restricting the set of changes they consider and by implementing less strict measures of change in model output SSunchez-Lengeliig et al., 2020). Specifically, unfaithfulness (Unf) (Agarwal et al., 2023) estimates sufficiency as the Kullback- divergence between the original label distribution and that obtained after zeroing-out all irrelevant features from G. Fidelity minus (Fid-) (Pope et al., 2019; Yuan et al., 2022; Amara et al., 2022) instead erases all edges and features deemed irrelevant by the explanation and measures the change in likelihood of the prediction j.+ Robust fidelity minus (RFid-) does the same but repeatedly deletes random edges from C. (Zhao et al., 2023; Amara et al., 2023; Zheng et al., 2023). Finally, probability of sufficiency (PS) estimates how often the model's ss prediction changes after multiplying the node features with the relevance scores output by the detector (Tan et al., 2022). Metrics for necessity specular, i.e., they manipulate the input by removing relevant elements instead, and include fidelity plus (Fid+), robust fidelity plus (RFid+), and prebability of necessity (PN).
While existing metrics differ in many details, they nicely fit the same common format:
Definition 2. Let d be divergence, pr distribution over supergraphs of RA, and pc a distribution over supergraphs of CA. Also, let (a G'A)) = d(pe(- G || pe(- G²)) measure the impact of replacing GA with G'A on the label distribution." 5 Then, the degree of sufficiency and degree of necessity of an explanation RA for a decision (G v) are:
Suf dn (RA) = EGr,--a ( G.))], Necd,po (RA) EGg-pelleee ( G'a)l
(2)
'We focus on graph classification, but our results also hold for node classification unless otherwise specified.
AA variant based on the difference in accuracy also exists (Yuan et al., 2022).
Wee drop the dependency on the label(s) for brevity.
3

---

Published as a conference paper at ICLR 2025
Table Definition recovers existing faithfulneess metries for appropriate choices of divergence and interventional distributions pn. and PC-
Metric
Estimates
Divergence df
Allowed changes
Unf
Suf
KL(pe(- Pa). ())
zero out all irrelevant features
Fid-
ppol Ga) - ppl( G
zero out all irrelevant features, delete all irrelevant edges delete random subset of irrelevant edges
RFid-
PS
Hpa(ū GA) = Polt G))))
multiply all irrelevant elements by relevance scores
Fid+ RFid+
Nec
pol GA) po(g G)))
zero out all relevant features, delete all relevant edges delete a random subset of relevant edges
PN
(p GA) / pa(O G))) multiply all relevant elements by relevance scores
The expectations in Eq. (2) are potentially unbounded, but can be normalized to [o, 1). the higher the better, via non-linear transformation, i.e., taking exp(-Suf (Ra)) and 1 eeeeeexpeeeeeeeeee Table shows that Definition 2 recovers all existing metrics for appropriate choices of divergence d and distributions pn and Pc- Alternative choices yield additional metries that differ in how they estimate the model's response to input modifications (Appendix C.4).
(Ra)).
While both sufficiency and necessity matter, there exists a natural tension between them. For instance, explanations covering a larger portion of GA likely attain higher sufficiency but lower necessity. This motivates us to define the degree of faithfulness Faitha.pa.pe (Ra) 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. PR and pC whenever it is clear from context.
3.1 FAITHFULNESS METRICS ARE NOT INTERCHANGABLE
A first key observation is that, despite falling into a common template, existing metries 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:
Proposition 1. Let (pR, Pc) be pair of distributions as per Definition 2. Then, depending on pe and G.. it is possible to find (F' Pc)) such that |Suf a.p. (RA) - Sufa,p, (Ra)) and |Neca.pe (RA) Neca.p' (Ra) are large the natural range of d.
All proofs and relevant discussion are in Appendix A and Appendix C.5. In essence, Proposition 1 means that faithfulness results cannot be properly interpreted unless the parameters d, PR and PC are known. This entails that explanation producers such as banks and algorithm designers responsible for certifying the faithfulness of explanations cannot withhold the parameters they used in the computation, lest end- users blindly trust explanations that are not sufficiently faithful for their downstream applications.
To understand the practical implications of our result, we report in Table the Suf values and ranking of expla- nations produced by three popular modular GNNs (see Table 4) on the if (Gui et al., 2023) dataset. This comes with in-distribution (ID) and dustof-distribution (OOD) splits, allowing us to sample perturbations from different graph distributions. We consider different distri- butions PR. as follows:
Table 2: Model ranking and absolute Suf values for different distributions PR, av- eraged over seeds: both can signifi- cantly change.
Split
Model
Motif2
cdi PR
uda PR
LECI
1 (81 # m)
(82 +
idi PR and PR allow replacing the complement CA GA RAA of the input graph with that of another sample G" = C% U R's taken from the same split, and ii) removing random edges from CA-
ID
GSAT
2 (78
1 (84 1
RA
CIGA
3 (65 m))
3 (73 06)
cods
poda
PR
LECI
2 (83 i 06)
1 [88 4: 06)
OOD
6SAT
3 (76 ::2 m)
3 (79 a: m)
ids and oods only subsample the complement of each graph by randomly removing fixed budget of edges.
CTGA
1 (85 a m))
2 (86 a m))
Metrics are reported for both ID or OOD splits. Over- all, changing pn alters the ranking of the models, This
4

---

Published as a conference paper at ICLR 2025
confirms that care needs to be taken when picking metric for comparing XAI algorithms and explanations, as metrics are not interchangeable. See Appendix C.5 for additional results.
3.2 NOT ALL NECESSITY ESTIMATORS ARE EQUALLY RELIABLE
The non-interchangeabiliyy of metrics becomes particularly significant not all estimators equally reliable. In fact, as we show next, commonly used necessity metrics are insensitive to the number of irrelevant elements in the explanation. Recall that evaluating necessity involves assessing the model's 's sensitivity to changes to the explanation RA itself. Assuming that RA contains truly relevant edges (i.e., removing them impacts the label distribution) we would like RA* necessity to worsen as the number of truly irrelevant edges
RA || - it covers grows.
Necessity metrics are systematically invariant to truly irrelevant edges. Existing metries do not satisfy this desideratum. This is because they delete either all of RA (e.g., Fid+ and PN) or an IID subset of edges thereof (RFid+). To see why this is problematic, consider a node classification task and a target node 11, and split the graph G'a into two subsets: those nodes whose messages can impact the distribution of Yi, and those that cannot. For injective L--ayer GNNs, these sets are (u() and G' \ NN respectively, there are not enough layers for messages coming from the latter to reach u1
Now, consider 1-layer GNN for node classification and an input line graph 11 < U2 f- f- Un- Since there is only one layer, only the messages from (1n) = {u1, u22 can contribute to the distribution of Y1. By deleting all of RA, Fid+ and PN disconnect uh from all other nodes, and as such they cannot distinguish between a "perfect" explanation R = Ni (ui) and a "bad" explanation R' = (w1) that contains arbitrary many irrelevant edges, as in both cases the prediction made using 41 only. See Fig. 2 in the Appendix for an illustration. An analogous reasoning applies to RFid+, which removes edges in an IID fashion. This means that the probability that deletes the edge between h1 and U2 is the same regardless of how many other edges appear in the explanation. We formalize this observation in the following proposition:
Proposition 2. Fix divergence d and a threshold > 0. Let R contain truly relevant edges. Then, Fid+ (R)+ PN R), and RFid+ RR) do not depend on [|]]] - r.
How can we ensure that Nec depends on the number of irrelevant elements? We next show that by selecting an appropriate distribution pc, necessity can be made to account for the number of irrelevant edges. This can be achieved by erasing b edges from the explanation, with some constraints on how b is chosen. Specifically, if depends on ||Rl], the metric - once again - does not properly the number of deletions increases according to
account for irrelevant items in the explanation, the size of the explanation. Indeed, a numerical simulation shows that the probability of deleting at least one truly relevant edge does not depend the number of irrelevant ones in the explanation, if b is proportional to the explanation size (see Fig. 6 in the Appendix). On the other hand, if is proportional to the size of the input graph G, the number of deletions depends also on the size of the complement, resulting in metric confounded by the complement of the explanation". This is best seen in the following example:
Example 1. Fix an explanation R composed of two edges {e1,e2), where only ej is truly relevant. If G has 10 edges, fixing budget of deletion as 10% of the graph size yields a modified graph G' such that the probability of removing e₁ is 1.2 Instead, if G has 20 edges. the probability of removing it is Hence, despite R being fixed, the probability of sampling truly relevant edges drastically changes.
We propose to avoid these issues by fixing a budget b that is proportional to a data set-wide statistic. such as average the graph size m l/ EGED | G*|, where D is the set of graphs. This way, no longer directly depends on the size of any specific input graph or explanation, while still being adaptive to the target task. The considerations above can be formalized in the following result:
Proposition 3. Fix any divergence d and constant hudget b 2 1. Let Sh be the set of subgraphs of G obtained by deleting b edges from Rt while keeping C fixed. Given an explanation R. containing truly relevant edges, Nec (R) computed using uniform pc over Sh depends on the number of irrelevant edges || r.
6 In node classification. the node whose prediction is being explained is never removed.
Thhe dependency of h on G can be modeled as a causal graph Nec + RA + G - b + Nec, which contains the backdoor path RA + G + b Nec confounding the estimation of Nec (Pearl, 2009).
5

---

Published as a conference paper at ICLR 2025
Table 4: Popular modular GNNs fail to fully implement (HS, ER, CF, LA). XIV means that both variants exist and the choice is made via cross-validation.
SE-GNNs
HS
ER
CF
LA
DI-GNNs
HS
ER
CF
LA
GISST (Lin et al., 2020)
X
x
V
CIGA (Chen ct al., 2022)
TopK
V
XIV
XIV
GSAT (Miao et al., 2022a)
X
X
V
XIV
GSAT (Miao et al., 2022a)
X
X
/
XIV
RAGE (Kosan et al., 2023)
X
x
V
LECT (Gui et al., 2023)
X
X
/
XIV
In essence, propose measuring necessity using Pc that is uniform subgraphs of size ||G|| b. where b a hyper-parameter and set as above. We denote the resulting distribution F'c-
Experimental analysis. We empirically compare our proposed Nec metric and RFid+ for assessing the necessity of expla- nations produced by GSAT (Miao al., 2022a) trained on Mctif2 (Gui et al., 2022). We measure them at two differ- ent topK selection thresholds (Amara et al., 2022). measuring how metrics behave for larger explanations. Confirming our theoretical analysis, RFid+ assigns close to constant scores to unnecessarily large explanations (Proposition 2), whereas Nec equipped with our proposed pe sensibly penalizes larger expla- nations (Proposition 3). Metrics are normalized ensuring the higher the better, d is set to be the L1 divergence, and values are averaged over 5 seeds. For RFid+, the degetien probability about metric implementation in Appendix B.2.2 and further comparisons in Appendix D.2.
Table Necessity values for GSAT explanations on Motifa f2. Nec with p penalizes larger explana- tions, whereas RFid+ does not.
Metric
Top-30%
Top-90%
RFid+ (1)
1
21 =
Nec (t) 54 +
34 +
0.3, while for Nec the budget 0.3m. We provide more details
Is FAITHFULNESS WORTH OPTIMIZING FOR?
We show that for regular injective GNNs, striet faithful explanations are trivial, highlighting a trade- off between explainability and expressivity. For modular GNNs, instead, non-trivial strictly faithful explanations are theoretically attainable provided certain conditions are met, see Appendix C.2. We then verify that popular modular GNNs fail in fulfilling those conditions, highlighting strong limitation in their current design principles.
4.1 FOR INJECTIVE REGULAR GNNS STRICTLY FAITHFUL EXPLANATIONS ARE TRIVIAL
Recall that an explanation R is strictly faithful when change to the complement CA affects the model's output, and when all elements R. contribute to the final prediction (see Section 3). 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 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:
Proposition 4. Consider binary classification task, an L-layer injective GNN, any PC and pr not allowing the addition of new elements, and d being either a divergence between distributions or the difference prediction likelihood: i) for node classification that only uses local aggregators, an explanation RA for a decision (G I.) is strictly faithful iff it matches N1(u). il) For graph classification, an explanation R. for a decision (G U) is strictly faithful iff matches G..
In both cases strictly faithful explanations do not depend on the learned weights at all and, as such, are uninformative. This is direct consequence of injectivity. prerequisite for GNNs to implement the Weiseeiler-Lehman test (Xu et al., 2018; Bianchi and Lachi, 2024), and highlights a trade-off between expressivity and explainability." This finding also complements existing negative results on (even non-injective) regular GNNs which provide no easy way of obtaining strictly faithful explanations (Amara et al., 2022; Longa et al., 2024; Li et al., 2024).
$Of course, one can obtain more informative explanations by giving up strict faithfulness and instead aiming at producing explanations that both faithful enough and smaller than the entire computational graph.

---

Published as a conference paper at ICLR 2025
Table 5: Test set accuracy and faithfulness SE-GNNS augmented with the strategies outlined in Sec- tion 4.2, averaged over 5 seeds. We do not augment GI CISST on BaMS, Mot f2, and Mot i ff-Sizzz ie since these datasets have constant input features for all nodes, making the modifications ineffective.
Dataset
BaMS
Motif2
Motif f-ize-
BBBP
Acc
Faith
Acc
Faith
Acc
Faith
Acc
Faith
GSAT
100 :00
1:03
1:01
0:
90 1:01
60 1 02
04
1.08
GSAT ER
1.0
1:01
0:0
90 1:01
65
80 12
1.04
GSAT
0:01
1:02
06
54 1:03
22 1 05
o1
1.09
GSAT ER + HS
0:00
0:04
=:0
56 0:
29 + 09
02
GISST
100
25
53
92
50
84
23
GISST ER
85
27
GESST HS
83
GESST ER HS
81
RAGE
96
33 05
83
64 0:
74 4: 09
63 +
82
33 4:04
RAGE ER
96
33 0:
85
66
71
55
84
33 1:
RAGE HS
97
46
85
65
78 0:07
65
84 00
46
RACE ER HS
96 01
46 0:04
83
64 1:11
75 1:08
62 1
82
43 1:03
4.2 THE CASE OF MODULAR GNNS
Modular GNNs are explicitly designed so that their predictions at least on paper - depend solely on the explanation they extract, yet popular modular architectures suffer from poor faithfulness (Christiansen et al., 2023). To better understand this phenomenon, we analyze four "architectural desiderata", whose absence enables information leak from the complement to the explanation, allowing the complement to influence the label distribution and thus compromising faithfulness:
Content Features (CF): since the message passing of the detector is unconditional its predicted edge relevance score, the classifier should have access to raw input (or content) features, contrarily to using the detector's 's latent representation which heavily leaked;
Hard Scores (HS): the detector f should associate exact zero importance to information in the complement, thus preventing update and aggr from mixing information from RA and Ca in g:
Explanation Readout (ER): (for graph classification only) the final graph global readout should aggregate only over RA. Since explanations are often soft edge masks over the entire graph, scaling the node embedding according to their average importance scores can still reduce the impact of irrleevnt nodes;
Local Aggregations (LA): non-local aggregations (see 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.
All these architectural desiderata encourage enforce the classifier y rely solely on RA for making predictions. In the remainder of this Section, we empirically investigate the impact on faithfulness of integrating popular models with the desiderata they lack, reporting their accuracy as a sanity check.
Experimental analysis. We benchmarked six representative modular architectures, listed in Table 4, following their respective evaluation testbed for graph classification. The datasets chosen for evalu- ation are picked from the usual evaluation routines for SE-GNN, and DI-GNNs respectively. For DI-GNNs, the chosen benchmarks can be divided into datasets with known comain-invariane input motifs (Mot i22 Basis, CMNIS -T--SST-Coll datasets with presumed domain-invarian input motifs (LBAP and datasets where domain-invariant input motif are not expected (SST2). This last case is especially problematic, graph. The full experimental setup is detailed in Appendix B.
clear advantage is expected in focusing subset of the input
Table 5 and Table 6 show the results for the original SE-GNNs and DI-GNNs architectures and their augmented variants. Overall, we show that simple but often neglected architectural design choices greatly impact faithfulness. Our major findings are follows:
(i) Local explanations are not always helpful. LBAP core and SST2 are the hardest datasets to improve and, generally, have worse faithfulness and accuracy scores. This raises doubts about the
7

---

Published as a conference paper at ICLR 2025
Table 6: 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
core
Acc
Faith
Acc
Faith
Acc
Faith
Acc
Faith
LECI
85 07
58 m
26
48
71
43
83
LECI + ER
86 08
59 02
58 12
58 08
71 0:
46
82 01
13
LECI + HS
86 0:
57 1:
34 1.10
57 0:
72 1
24 1:
83 1:
18 1:
LECT + LA
46 =
57 = 08
69 2:
31 03
81 06
20 24
LECI + ER + HS LA
79 11
55 02
75 05
61 01
59 02
21 01
81 02
16 +
CIGA
46
38
23
36
69
33
76
18
CIGA + ER
45 00
54
23 02
43
59
09
74
16
CIGA + CF
53 07
49
13 01
49
49
03
55 07
09 1.12
CIGA + LA
30 09
41 = 05
68 1:
34 08
79 =:
16 1:10
CIGA + ER + CF+ LA
47 08
39 07
23 03
50 02
66 01
23
76 06
15 12
GSAT
58
25
48
70
40
79
22
GSAT + ER
59
60
30 06
48
67
32
81
23
GAAT + HS
86 08
42 m
14 03
44
71 1:
28 01
80 1:
17 1:10
GSAT + LA
27 0:03
46 = 04
69 t:
44 02
81 01
21 14
GSAT + ER HS LA
64 08
47 + 0
17 0:
51 05
70 +
38 03
80 01
17 +:
suitability of these rather popular datasets for evaluating local GNN explanations, as evidenced by the fact that explanations tend to cover the entire graph with similar or nearly identical scores (see Appendix D.I for the details). Indeed, standard GIN (Xu et al., 2018) trained without any OOD regularization achieves scores 69.7 and 79.7 respectively, confirming that GNNs might not have an advantage in focusing more closely align with the explanation is likely to force it to either discard information or assign uniform weights across the entire topology, ultimately reducing both faithfulness and accuracy.
sparse input subgraph. Therefore, any strategy that pushes the model to
(ii) HS can significantly alter model behavior. Although RAGE seems to benefit from HS, as improves both faithfulness and accuracy in every dataset, it severely compromises the training of GSAT in Mot footff2 22 and i f-iiffiiii -iize, resulting in a train and test accuracy of around 50%. In fact, exact-zero scores for irrelevant edges are certainly desirable, yet it is known that it is hard to deal with exact zeros in common gradient-base based learning. More advanced techniques are therefore advocated for reliably implementing hard scores (Serra and Niepert, 2022).
(iii) ER, LA, and CF can be effective in promoting faithfulness. Motivated by these observations, next we focus on the remaining datasets, where GNNs can identify sensible local explanations. ER improves faithfulness in 10 cases out of 15, while leaving it unchanged in four. In two cases in particular, whilst faithfulness increases, accuracy drops. This a natural effect of being faithful: the explanation is not plausible enough", the accuracy shall drop. When prompting CIGA to use input features (CF), faithfulness increases by 33% on Mot if2 and CMNIST on average. Similarly, LA improves average by 9.5% faithfulness and by 38% accuracy on CMNIST. In general, imposing all desiderata jointly is beneficial when individually they also are.
Take-away. On the one hand, these results question the current dexign of modular GNNs, suggesting that popular models include architectural components that implicitly penalize faithfulness, and that the factors contributing to faithfulness may be more nuanced than previously assumed.
On the other, they show that merely preventing information from the complement to leak into the prediction is insufficient to fully address the problem. A rather complementary direction of investigation is that of making the detector f more stable to irrelevant modifications. In fact, assuming a classifier perfectly implementing the desiderata above and an explanation R,, is easy to see that if the detector changes the predicted explanation for modified graph G²A 2 RA, then the final prediction can arbitrarily change, thus also Suf does.
Training time strategies are also likely to play a role. For example, necessity can intuitively be encouraged via sparsification techniques (Lin al., 2020; Kosan al., 2023), whereas approaches like contrastive learning (Chen et al., 2022; 2023), adversarial training (Gui et al., 2023), or data
"C GA and GSAT score around 0.25 of WloU plausibility on Mat i F2. See Appendix B.2 for details
8

---

Published as a conference paper at ICLR 2025
augmentation (Wu et al., 2022) are natural options for encouraging sufficiency. We plan to investigate how those insights translate into new faithful-by deessn modular architectures in future work.
5 FAITHFULNESS IS KEY FOR DOMAIN INVARIANCE
Finally, we study the impact of faithfulness and lack thereof- on domain invariance. In the domain invariance literature (Chen et al., 2022; Gui et al., 2023), one distinguishes between in-distribution (ID) and out-of-distribution (OOD) data, sampled from (G., Y) and pood (Ga. Y). respectively, and the goal is to learn DI-GNN pe that generalizes from ID to OOD data. Input graphs are assumed to consist of an invariant R2 S GA and spurious subgraph, with the ground-truth label only depending on the invariant subgraph domain-invarian manner, that is, pY R2 prod I2a)) (Cai et al., 2023; Chen al., 2023; Jiang et al., 2023). Modular DI- GNNs are designed to output subgraph RA (which plays the role of an explanation) and its degree of invariance is proportional to its plausibility, i.e., how closely matches R4
1.0
GOODMatif basis
GOODMati22 basis
0.8
GOODMotif size
CIGA
likellhood difference
0.6
GSAT
0.4
0.0
-0.2
falthfulnees domain invariance
Figure 1: 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.
We begin by showing that, even if the graphs RA extracted by a DI-GNN (see Section 2) are maximally plausible, unless they are also strictly sufficient, the model's 's prediction is not domain invariant. To build intuition, take DI-GNN that, for some input, outputs a perfectly invariant explanation RA. Now, if the explanation is not strictly sufficient, by definition there exists a modification the complement of RA (which is domain-dependent that alters the predicted class distribution. Thus the model as a whole cannot be fomain-invarian
Proposition 5. Let po be a modular DI-GNN such that the detector I outputs graphs RA that are maximally plausible, ie., that comprise all and only those elements that are constant across the target domains. If RA is not strictly sufficient, then the prediction is not domain invariant.
This result is significant because DI-GNNs typically optimize only for the invariance of the extracted subgraph R.A. neglecting how the classifier uses it afterward. The next result highlights that the degree of faithfulness of RA- and specifically, that of sufficiency - plays a direct role in ensuring that the model's 's predictions are truly domain-invariant. In fact, the following Theorem bounds the difference in likelihood between ID and OOD as a proxy to measure the change in the fit of the data, so that a small difference corresponds many generalisation bounds available in literature (Redko et al., 2020), ours pertains specifically to explanation quality, both in terms of degree of invariance and degree of sufficiency.
consistent model behavior across domains. Differently from the
Theorem 1. (Informal) Let pe be a deterministic DI-GNN with detector f and classifier g. and pdd (G Y) and pood (GA, Y)) be the ID and OOD empirical distributions, respectively. Then:
E ( (poly GA)] E(GAAi)>poo (poly Ga)I|
EER; [K1 (Nid + -ood
( Year + >oea
( (dd
>
Here, ER; runs over all possible invariant subgraphs, k1, k2 > O are Lipschitz constants of pe. Nape Xood Xid" and Xood measure the implausibility of the detector's output (with respect to topology and features, respectively), and Sug. Xood are the degree of sufficiency for ID and OOD data.
The Theorem is proved by applying the triangular inequality and basic properties of the expectation and relies two main assumptions: the domain invariance of R and the Lipschitzness of GNNs. In essence, Theorem shows that a DI-GNN that fits well the ID data will fit well the OOD data RA is i) plausible (low Atopo and Aeatt, thus invariant across domains), and ii) highly sufficient (low

---

Published as a conference paper at ICLR 2025
Aeufy). An illustration of the interplay between the LHS and the RHS of Theorem 1 is provided in Appendix C.I. The practical relevance of this result is twofold: it suggests that researchers should also consider sufficiency when evaluating DI-GNNs, well as focus the invariance of both topology and feature, rather than topology only as often done (see Table 8).
We stress that while necessity does not appear in the bound, it becomes important if wish the invariant subgraph to be non-trivial. Indeed, Fig. shows a statistically significant anti-correlation (Pearson's 's correlation -0.83, p-value 0.01) between the difference in average prediction's 's likelihood between ID and OOD data, and the combination of the degree of domain-invarianee 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.
6 RELATED WORK
Modular architectures. Modular GNNs are widely used for seeking trustworthiness, either in the form of explainable (Lin et al., 2020; Miao et al., 2022b: Kosan al., 2023) or confounding-free predictions (Wu et al., 2022; Chen et al., 2022; Gui et al., 2023) (see Jiang et al. (2023) for a survey), also in deep neural networks for non-relational data (Koh al., 2020; Marconato et al., 2022). Explanation quality is critical for interpretability and for ensuring fair and generalizable predictions (Amara et al., 2022; Miao et al., 2022a; Longa et al., 2024). Despite being primarily designed for faithfulness, the prediction depends the explanation only, little attention has been paid to measuring how well the classifier adheres to its own explanations, an issue that can completely prevent trust allocation (Agarwal et al., 2024). 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 explanations (Christiansen al., 2023). In this work, we investigate the reasons for this behavior, discuss the applicability of faithfulness-enforein strategies and extend the analysis to DI-GNNs.
Faithfulness. In the Explainable AI (Samek et al., 2021) and GNN literature (Agarwal et al., 2023), sufficiency and faithfulness are often conflated, however, disregarding necessity opens to trivially sufficient yet uninformative explanations. Faithfulness is also sometimes defined as the correlation between the explainer's "performance" and that of the model, that is, to what extent worsening model performance worsen also the plausibility of explanations (Sanchez-Lengeling et al., 2020). However, this is evaluating model and explainer performance separately 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 causal explainability (Beckers, 2022) and disentanglement in causal representation learning (Suter et al., 2019; Schölkopf et al., 2021). Like Beckers (2022), we argue that absolute measurements of sufficiency, and more generally faithfulness, our case by the choice of parameters used for the measurements. Following Bordt et al. (2022), we argue this leaves room for adversarial explanation providers to supply explanations that optimize their objective rather than that of the explanation consumer.
uninformative unless properly contextualized, in propert
7 KEY TAKEAWAYS AND BROADER IMPACT
We have studied the faithfulness of explanations in regular and modular GNNs. Our results indicate that, despite conforming
shared template, existing faithfulness metrics are not interchangeable (Proposition 1) and in fact some even suffer from systematic issues (Proposition 2), which we show can be avoided with an appropriate choice of parameters (Proposition 3). We have also shown that optimizing for faithfulness is not always a sensible design goal (Proposition 4) and that improving the faithfulness of SE- GNNs and DI-GNN- is non-trivial, suggesting limitations in the current design of modular GNN. We also proved that faithfulness plays a surprisingly central role for domain invariance, in that modular GNNs tailored for domain invariance cannot be invariant unless their explanations are also sufficient (Proposition 5 and Theorem l). This suggests that research on DI-GNNs should focus on sufficiency, which it currently neglects.
Our experiments explore simple yet overlooked design choices to enhance faithfulness in modular GNNs, showing benefits for SOTA architectures. Developing truly faithful-by deeign solutions remains challenge for future work. In addition, our notion of faithfulness relies on input-level modifications of the graph topology. While this doesn't 't impact training or inference time, its evaluation can be slow for large input graphs, requiring more efficient implementations.
Limitations:
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
All authors have read and approved the ICLR Code of Ethics. As for societal consequences, the aim of this work to shed light 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.
REPRODUCIBILIT STATEMENT
The proofs of all theoretical results are provided in Appendix A. Details about the experiments, along with details about metries and implementation, are available in Appendix B. Our source code made available in the supplemental.
ACKNOWLEDGEMENT
Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do necessarily reflect those of the European Union the European Health and Digital Executive Agency (HaDEA), Neither the European Union nor the granting authority can be held responsible for them. Grant Agreement no. 101 TANGO.
The authors are grateful to Emanuele Marconato for useful discussions and to Manfred Jaeger for his feedback on an earlier version of this manuscript.
REFERENCES
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61 -800, 2008.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint (Xix:1609.0290) 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
Antonio Longa, Steve Azzolin, Gabriele Santin, Giulia Cencetti, Pietro Lio, Bruno Lepri. and Andrea Passerini. Explaining the explainers in graph neural networks: a comparative study, ACM Comput. doi: 10. 145//6964644
Surv., 2024. ISSN 0360-0300.
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. A survey on explainability graph neural networks. arXiv preprint arXiv:2306.00 01958, 2023.
Phillip Pope, Soheil Kolouri, Mohammad Rostami, Charles Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10772-10781, 2019.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks:
A taxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5): 5782-5799, 2022.
Kenza Amara, Zhitao Ying. Zitao Zhang, Zhichao Han, Yang Zhao, Yinan Shan. Ulrik Brandes, Sebastian Schemm, and Ce Zhang. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. In Learning Graphs Conference, pages 44-1. PMLR, 2022.
Tianxiang Zhao, Dongsheng Luo, Xiang Zhang, and Suhang Wang. Towards faithful and consistent explanations for graph neural networks. In Proceedings of the Sixteenth ACM International Conference Web Search and Data Mining, WSDM '23, page 634-642, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394079. doi: 10.1145/3539597. 3570421. URL https:ttpp............ //t::://ooiooooo 11t.1/11311999....1 3570442.

---

Published as a conference paper at ICLR 2025
Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022, WWW '22, page 1018-102)) New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781 9781450390965 doi: 10.1 10.14445/48447733511 1948. URL htwps:ttt//.cc........t /doi org/10..//..oo /111//3444444 344334884444 3581
Xu Zheng, Farhad Shirami, Tianchun Wang, Wei Cheng, Zhuomin Chen, Haifeng Chen, Hua Wei, and Dongsheng Luo. Towards robust fidelity for evaluating explainability of graph neural networks, 2023.
Stefano Teso, Öznur Alkan, Wolfang Stammer, and Elizabeth Daly. Leveraging explanations in interactive machine learning: An overview. Frontiers in Artificial Intelligence, 2023.
Sebastian Bordt, Michèle Finck, Eric Raidl, and Ulrike von Luxburg. Post-hoc explanations fail to achieve their purpose in adversarial contexts. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 891-905, 2022.
Hengrui Cai, Yixin Wang, Michael Jordan, and Rui Song. On learning necessary and sufficient causal graphs, 2023.
Yongqiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. Rethinking invariant graph representation learning without environment partitions. ICLR 2023 Workshop on Domain Generalization, 2023.
Shurui Gui, Meng Liu, Xiner Li, Youzhi Luo, and Shuiwang Ji. Joint learning of label and environment causal independence for graph out-of-distribution generalization. arXiv preprint arXiv:2306.0110. 2023.
Wenzhao Jiang, Hao Liu, and Hui Xiong. Survey trustworthy graph neural networks: From causal perspective, 2023.
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs Neural Networks, 129:203-222 221, 2020. ISSN 0893-6080.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: /2144.
Grids, groups, graphs, geodesics, and gauges, 2021. URL https: 13478.
Florian Sestak, Lisa Schneckenreiter, Johannes Brandstetter, Sepp Hochreiter, Andreas Mayr, and Günter Klambauer. Vn-egnn: E(3)-equivariant graph neural networks with virtual nodes enhance protein binding site identification, 2024.
Marc Christiansen, Lea Villadsen, Zhigiang Zhong, Stefano Teso, and Davide Mottin. How faithful are self-explainable gnns? arXiv preprint arXiv:2308. 15096, 2023.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524-15543. PMLR, 2022a.
Chris Lin, Gerald J Sun, Krishna C Bulusu, Jonathan R Dry, and Marylens Hernandez. Graph neural networks including sparse interpretability. arXiv preprint arXiv:0007.00119 2020.
Giuseppe Serra and Mathias Niepert. Learning to explain graph neural networks. arXiv preprint
arXiv:2209. 14402, 2022.
Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. arXiv preprint arXiv:2201.12877 12872, 2022.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Cheekong Lee. Protgnn: Towards self-
explaining graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9127-9135, 2022.
Alessio Ragno, Biagio La Rosa, and Roberto Capobianco. Prototype- interpretable graph neural networks. IEEE Transactions Artificial Intelligence, 2022.
12

---

Published as a conference paper at ICLR 2025
Enyan Dai and Suhang Wang. Towards self-explainable graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 302-311, 2021.
Enyan Dai and Suhang Wang. Towards prototype-based self-explainable graph neural network. arXiv preprint arXiv:2210.01974, 2022.
Lucie Charlotte Magister, Pietro Barbiero, Dmitry Kazhdan, Federico Siciliano, Gabriele Ciravegna, Fabrizio Silvestri, Mateja Jamnik, and Pietro Lio. Encoding concepts in graph neural networks. arXiv preprint arXiv:2207. 13586,, 2022.
Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. Graph information bottleneck for subgraph recognition. In International Conference on Learning Representations, 2020.
Junchi Yu, Jie Cao, and Ran He. Improving subgraph recognition with variational graph informa- tion bottleneck. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 19395-19405, 2022.
Siqi Miao, Yunan Luo, Mia Liu, and Pan Li. Interpretable geometric deep learning via learnable randomness injection. In The Eleventh International Conference on Learning Representations, 2022b.
Valentina Giunchiglia, Chirag Varun Shukla, Guadalupe Gonzalez, and Chirag Agarwal. Towards training GNNs using explanation directed message passing. In The First Learning on Graphs Conference, 2022. URL https:tpp/..c wwwp//ppeeweeeeeeeeeeeee
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Towards causal representation learning, 2021.
Haoyang Li, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning invariant graph representations for ofddisriibutiinn generalization. Advances in Neural Information Processing Systems, 35: 18828-11411, 2022.
Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, MA Kaili, Binghui Xie, Tongliang Liu, Bo Han, and James Cheng. Learning causally invariant representations for out-of-distribution generalization on graphs. Advances in Neural Information Processing Systems, 35:22131-22 221148, 2022.
David S Watson, Limor Gultchin, Ankur Taly, and Luciano Floridi. Local explanations via necessity and sufficiency: Unifying theory and practice. In Uncertainty in Artificial Intelligence, pages 1392. PMLR, 2021.
Sander Beckers. Causal explanations and xai. In Conference on Causal Learning and Reasoning, pages 90-109. PMLR, 2022.
Joao Marques-Silva and Alexey Ignatiev. Delivering trustworthy ai through formal xai. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 12342-12350, 2022.
Adnan Darwiche and Auguste Hirth. On the (complete) reasons behind decisions. Journal of Logic, Language and Information, 32(1):633-8)) 88, 2023.
Benjamin Sanchez-Lengeling, Jennifer Wei, Brian Lee, Emily Reif, Peter Wang. Wesley Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko. Evaluating attribution for graph neural networks. Advances in neural information processing systems, 33:5898 -910,,900 2020.
Kenza Amara, Mennatallah El-Assady, and Rex Ying. Glnx-eval: Towards in-distribution evaluation of graph neural network explanations. In XAI in Action: Past, Present, and Future Applications, 2023. URL https: hwtp///enneeee.eeee/pe net www.oooomoowooooooeooooo
Judea Pearl. Causality. Cambridge university press, 2009.
Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: A graph distribuuii benchmark. In Thirty-sitth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. URL https: htt.ttttt////eeeeeee
/ http:////p///e/ee/////tt/ee/eeet net forum? d= p-h.
13

---

Published as a conference paper at ICLR 2025
Mert Kosan, Arlei Silva, and Ambuj Singh. Robust ante-hoc graph explainer using bilevel optimiza- tion, 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Zhong Li, Simon Geisler, Yuhang Wang, Stephan Günnemann, and Matthijs van Leeuwen. Ex- plainable graph neural networks under fire, 2024. URL /tRLttt:///xxiiiorrro wwtpv///rrg//////4//// 06417.
levgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younès Bennani. A sur- vey on domain adaptation theory: learning bounds and theoretical guarantees. arXiv preprint arXiv:2004. 11822,, 2020.
Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International Conference on Machine Learning (ICML., volume 119 of Proceedings of Machine Learning Research, pages 5338-5348. PMLR, 2020.
Emanuele Marconato, Andrea Passerini, and Stefano Teso. Glancenets: Interpretabile, leak-proof concept-based models. In NeurlPS, 2022.
Chirag Agarwal, Sree Harsha Tanneru, and Himabindu Lakkaraju. Faithfulness vs. plausibility: On the (unlabbibbil of explanations from large language models, 2024.
Wojciech Samek, Grégoire Montavon, Sebastian Lapuschkin, Christopher J. Anders, and Klaus- Robert Müller. Explaining deep neural networks and beyond: A review methods and applications. Proceedings of the IEEE, 109(3):247-278 2021. doi: 10.1 10.1199//RO...221..3000
Raphael Suter, Djordje Miladinovic, Bernhard Schölkopf, and Stefan Bauer. Robustly disentangled causal mechanisms: Validating deep representations for interventional robustness. International Conference Machine Leurning, pages 6056-6065. PMLR, 2019.
Bernhard Schölkopf, Francesco Locatello, Stefan Bauer, Nan Rosemary Ke, Nal Kalchbrenner, Anirudh Goyal, and Yoshua Bengio. Toward causal representation learning. Proceedings of the IEEE, 2021.
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pictro Lio, and Andrea Passerini. Global explainabil- ity of gnns via logic combination of learned concepts. In The Eleventh International Conference on Learning Representations, 2022.
Sergey Dorogovtsev and Jose FF Mendes. Evolution of networks. Advances in physics, 51(4): 1079-1187, 2002.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 92)):513-530, 2018
Ines Filipa Martins, Ana L Teixeira, Luis Pinheiro, and Andre O Falcao. A bayesian approach to in silico blood-brain barrier penetration modeling. Journal of chemical information and modeling, 52 16),16 2012.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometrie deep learning graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 51 15-5144, 2017.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal attention for interpretable and generalizable graph classification. Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '22, page 1696-1705. New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 1400393850 doi: 10.1 14445/3534678.35559 URL https: //ooi www.ooog///.... 1..00.11.555 1141 http://doooooooo....//o//
3539366.
14

---

Published as a conference paper at ICLR 2025
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztioo with gombal- In International Conference on Learning Representations, 2017. URL httpttt///peeeeeeeeeee net/
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 33:22 18-22133, 2020.
Manfrrd Jaeger. Learning and reasoning with graph data. Frontiers in Artificial Intelligence, 1124718, 2023.
Yu Song and Donglin Wang. Learning on graphs with out-of-distribution nodes. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 1635-1645. Association for Computing Machinery, 2022. ISBN 9781450393850, doi: 10.1 00.1144//534478.3339955 URL https: //o.i.////////// /ttgg/...000 11.111....1111111 1111111453331111111111111 3539457.
Xiao Luo, Yusheng Zhao, Zhengyang Mao, Yifang Qin, Wei Ju, Ming Zhang, and Yizhou Sun. Rignn: A rationale perspective for semi-supervised open-world graph classification. Transactions on Machine Learning Research, 2023.
Shaohua Fan, Xiao Wang, Yanhu Mo, Chuan Shi, and Jian Tang. Debiasing graph neural networks via learning disentangled causal substructure. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, 2024. ISBN 978171387 1088.
Fangyu Ding, Haiyang Wang, Zhixuan Chu, Tianming Li, Zhaoping Hu, and Junchi Yan. Gsina: Improving subgraph extraction for graph invariant learning via graph sinkhorn attention, 2024.
URL https: / /arxivvv.v/.//////i
org/ abs / 222224222222 07191.
Lukas Gosch, Simon Geisler, Daniel Sturm, Bertrand Charpentier, Daniel Zügner, and Stephan Günnemann. Adversarial training for graph neural networks: Pitfalls, solutions, and new directions. Advances in Neural Information Processing Systems, 36, 2024.
Jesse C Cresswell, Yi Sui, Bhargava Kumar, and Noël Vouitsis. Conformal prediction sets improve human decision making. In Forty-first International Conference on Machine Learning.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, Advances in neural information processing systems, 30, 2017
15

---

Published as a conference paper at ICLR 2025
A PROOFS
A.1 PROOF OF PROPOSITION 1
Proposition 1. Let (Pn.Pe) be pair of distributions as per Definition 2. Then, depending on and G.. it possible to find (P'r Pc)) such that [Suf duf (auu))Suua.ppp Suff (Ra) and |Neca.pc (Ra) Nec..ro (Rx) are as large as the natural range of d.
Proof. We prove the statement for graph classification; the case of node classification analogous.
Let S supp(pR) and S' supp(z/R), both finite. Assume RA attains perfect degree of sufficiency according to PR. i.e., Suf pm (Ra)= = 0. and take I'n such that S n = Ø. Then:
|Suf pm (Ra) Suf w/ (RA)l
Σ A(GA,G')PRlGC) G'ESS
E A(CAA (4) GRESS'
The two sums have no terms in common, so we can independently control the second one through our choice of interventional distribution F'g. In fact, it is maximized by those distributions that associate all probability mass to graphs G'a for which [G G'A) is largest, e.g. counterfactuals. As long as at least one counterfactual GAA exists that includes RA subgraph, then P/z can allocate all probability mass to it, in which case the right sum becomes as large as argmaxp.c d(p, q). that is, as large as the natural range of the divergence d.
A similar reasoning applies to Nec. Take RA such that for all H²'s E supp(pc) it holds that AG G¹A)) > for some desired threshold т. As long there exists a graph G' CA such that po(- GA) = (- G²1), then we can always choose an interventional distribution Pac that allocates all mass to it. Hence, Nec, (RA) 0 and the difference in necessity will be least T.
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) S and S' are finite: this is the case for all existing metries, 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 RA (for sufficiency) or inputs that subsume CA and map to the predicted label ý (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 PR. which also happen have either disjoint almost disjoint supports (in which case 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'. On the bright side, is easy see that, long as both d and d' are proper divergences, an explanation RA achieving perfect sufficiency according to one will also attain perfect sufficiency according to the other, precisely because perfect sufficiency attained when A G¹,) = 0 for all G' PR. 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 I,p distances) and Pinsker's (relating the KL to the L,, distance).
The situation is different if d is proper divergence (say, the KL divergence) and d' is difference in likelihoods. In this case, there are situations in which the two quantities can differ. To see this, consider multi-class classification problem, target decision (G. 5) and a modified input G", pR such that i) po G = P G²²). ) but ii) the two label distributions have disjoint support. In this case, the KL divergence between them would be unbounded, yet the difference in likelihood would be null. Depending on the choice of Prz this can yield a large difference between degrees of sufficiency (and similarly for necessity).
16

---

Published as a conference paper at ICLR 2025
A.2 PROOF OF PROPOSITION 2
Proposition 2. Fix divergence d and a threshold E >> O. Let R. contain truly relevant edges. Then, (R)+ PN(R), and RFid+(R) do not depend on [[]] - r.
Proof. Fid+ and PN are systematically invariant to truly irrelevant edges. We begin by showing that metrics like Fid+, which estimate necessity by deleting the whole explanation RA. 10 suffer from this issue. Consider a L-layer GNN for predicting a label of interest for a node u, and take RA C (N) which covers all truly relevant edges and R2A 3 RA. Fid+ associates the same value to both RA and R' as in both cases the model predicts Y1 using u only, meaning that, surprisingly, Fid+(RA) (RA) Fid+(R'A)) When the edge relevance scores are binary, PN behaves exactly like Fid+, in which case it also suffers from this issue.
RFid+ is systematically invariant to truly irrelevant edges. Considering the same setting above, turns out that also (Fad+(Ra) = RFid+(R', (R'A)- In fact, RFid+ estimates necessity by removing edges in an IID fashion, which means that the probability that deletes the edges in RA is the same regardless of how many other edges appear in It', \ RA. This intuition can be formalized as follows: Let U, be a random variable determining whether edge ej is kept, such that U, ~ (ernoulli(ss). with x a user-provided hyperparameter. As in Proposition 3, let Sh be the set of subgraphs of G obtained by deleting edges from R while keeping C fixed, and A {G' E S AGG G') 2 e} those subgraphs that lead to a large enough change in A. Also, let SR S U.U...US and similarly for AR- Then, we can study RFid+ in terms of how likely the corrupted graphs G' it samples have missing relevant edges, i.e., P(G' E AR).
P(G' E AR)
= 1 1 P(G' & AR)
(5)
= 1 1I- = I,..., Um = 1)
(6)
m
1 II P(U, =)
(7)
1 K
(8)
(9)
In the second to last step, we made of the independence of all U.'.. The above probability does not depend on the number of irrelevant edges || - r.
A.3 PROOF OF PROPOSITION 3
Proposition 3. Fix any divergence d and constant budget b 2 1. Let Sh be the set of subgraphs of G obtained by deleting b edges from R while keeping C fixed. Given an explanation R containing truly relevant edges, Nec R) computed using uniform Pe over Sh depends the number of irrelevant edges [|]]| -r.
Proof. Let S be the set of subgraphs of G obtained by deleting b edges from R while keeping C fixed, and A = (G' E S AAG. 2 cJ those subgraphs that lead to a large enough change in A. Then, when choosing budget b of deletions and uniform PG(G) over subgraphs with ||G]| b edges, P(G" E A = A which decreases as the number of irrelevant edges in R increases.
Note that [h)] (II)))), while I = Dd (2) (2BB""))
A.4 PROOF OF PROPOSITION 4
Proposition 4. Consider binary classification task, an L-layer injective GNN, any Pe and pr not allowing the addition of new elements, and d being either a divergence between distributions or the difference in prediction likelihood: i) for node classification that only uses local aggregators, an explanation RA for a decision (G A. Du) )
strictly faithful iff matches Nr(u). ii) For graph classification, an explanation RA for a decision (G () is strictly faithful iff it matches G
In node classification, the node whose prediction is being explained is never removed.
17

---

Published as a conference paper at ICLR 2025
Proof. Before proceeding, it is useful to introduce the notion of computational graph, that is, the subgraph of GA induced by those nodes whose messages are relevant for determining the label distribution P(Y,. G or P(Y G^) 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 Nr. (u), and for injective GNNs, all such messages impact the lahel distribution. For graph classification, which is implicitly global, all nodes in the computational graph are the entirety of GA.
Next, consider any pair of interventional distribution, PC and pc, excluding the addition of new nodes or edges. We show that if R& does not subsume the entirety of the computational graph, then when computing strict sufficiency we can always alter those elements of the computation graph that fall in the complement CA. By injectivity of pe, 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 RA cannot be strictly sufficient for any d, and therefore neither strictly faithful.
The converse also holds: if RA covers the entire computational graph, then it is necessarily strictly sufficient. This is because the complement Ca has no overlap with the computational graph, so altering it has no impact on the label distribution.
If instead, the interventional distributions allow for the addition of new items, like new nodes or new edges, then strictly faithful explanation might not exist altogether the induced perturbation can adversarially include the trivial class ciass-iicrimiiative pattern of the non-predicted class, forcing the model to always switch prediction.
A.5 PROOF OF PROPOSITION 5
Proposition 5. Let po be a modular DI-GNN such that the detector I outputs graphs RA that are maximally plausible, ie., that comprise all and only those elements that are constant across the target domains. If RA is not strictly sufficient, then the prediction is not domain invariant.
Proof. We proceed by contradiction. Let GA be an input graph such that the explanation RA for model po and decision (GA, ū) is perfectly domain-invarian yet not strictly sufficient. We assume that the model prediction does not depend on nomain-induced spurious information, meaning that every modification applied to CA will not have any impact on the model prediction (according to d). However, the lack of strict sufficiency implies that 3G"A E supp(pR) such that AG Gx')= > 0. This means that there exists perturbation outside of RA that altered the model prediction, which is in contradiction with assuming that it does not depend on domain- domain-induced information.
A.6 PROOF OF THEOREM 1
Theorem:
Let pa be a deterministic DI-GNN with detector f and classifier g and d be the difference in likelihood of the predicted label. Also, let pe be Lipshitz with respect to changes to both the topology and the features of the input, that is, for every pair of graphs G = (G,X) X) and G', (G', X'), must hold that:
PY (G,
po (G'
S kidi di (G, G')
(10)
PY (G,X)) PY I (G,X'))
< k2dy (X,X')
(11)
for suitable distance functions d1 and d2. Then:
BiGAN (plly | Ga)] - B(GAA))) (po GAAi|
(12)
S ERR (ki (Nid + (poee) + kiz (Dje + +gpadd +
+
Auff
aod
)
Here, ki,k2 > 0 are Lipschitz constants of po. Nopo Xid gree of domain invariance of the detector's 's output (with respect to topology and features, respectively), and Noug Xood are the degree of sufficiency for ID and OOD data.
topo Xpod, and >oed measure the (negated) de-
It is not affecting the difference in accuracy however, as change in prediction confidence does not always entail change in most-likely output class.
18

---

Published as a conference paper at ICLR 2025
Proof. Let f be an ideal detector that for every input GA outputs the maximal subgraph Ra (R", x² Note that, for every (G% yhd) pd and (Gxd yood) pood that share the same invariant subgraph (that is, such that f ("( (G = Ra) any DI-GNN
constructed by stitching together f* and a deterministic classifier g will predict the same label distribution for both graphs, i.e, Pa (Y (G)) = py f (G)
Now, fix any invariant subgraph R When conditioning on it, holds:
(G
f (G)) (G ( (irr))loly If (GT"
(13)
where the two expectations run over ID and OOD samples that share the same invariant subgraph Ra We proceed by noting that:
po(y (R, x y)| S ki (1n (R", R) B(GA.D)~p' ( nz) polv (R",
Augoo
(14)
The expectation on the RHS is the average topological distance of the predicted invariant subgraphs to A which corresponds to the degree of invariance (plausibility) of R. and will be referred as Atopo At the same time, it also holds that:
T (( po(y (R, - ppo (R, x²1) s 12 (( 12 x)]
(15)
where the expectation on the RHS is now the average distance between the features of the predicted invariant subgraphs and those of R and will be referred to as A Combining Eq. (14) and Eq. (15) using the triangular inequality, yields:
(( po(y R2A) - polv! Ra)
(16)
= ((GA))))p poly ( R²A)= - poly (R, (R)) + poly (R, Po(y RA)
(17)
s poly (K², po (1R, + E po (R,,X*)) - po (R, x
(18)
< Augo + Nin
(19)
This holds for any fixed R
Next, we bound the expected difference between the label distribution determined by RA and that determined by G using the degree of sufficiency. For notational convenience, we draw complements C²A rather than full modified graphs G² from PR. and we denote the operation of joining RA and Ca to form G'₁ with the J operator, and where divergence d. We proceed as follows:
the difference in prediction likelihood as
B(GAa))p' poly RA) - poly Gaa)
(20)
= -E(GA E Ec, ~ (poly) RAACCA) poly GA)
(21)
<E(GAN) (os poly! RA RAUCC) poly Ga)
(22)
-B(GAs)) Suf (Ra) = Avall
(23)
(24)
19

---

Published as a conference paper at ICLR 2025
In the first second step, made use of the law of total probability and the product rule, for which:
plu. C. C... RA)
ply RAlp(Ca Ra)p(RA)
po(y RA) = Σ
ply. CA RA) = Σ
P(RA)
p(RA)
C₁2
CAA
C²A
(25)
Σ Polyl RA UCAA)PP(CC) BoG~paPo(y RA
R UCA)
(26)
Then, applying again the triangular inequality between Eq. (20) and Eq. (16) yields:
B(GAM))-i((11))) po R²²) po Ga) s ki Ki + 12 + Add
(27)
The same derivation applies to pood (Ga), obtain:
((a po(u R2)) - po G.)) < ky Aopo + A2a + Xood
(28)
Combining these bounds using the triangular inequality last time, derive:
E (( Ga) - (pp GA)
(29)
Po(y | G pa(y Good
S E (0% ())p"()))))1)11 (G (o)dl))) ()) (1182)
(30)
< kg (Aigo + (rppp) + (Diea + Xead) + (Aidd + good )
(31)
Again, this holds for all choices of R'AA
Finally, we leverage these inequalities to bound the difference likelihood between ID and OOD data for all possible choices of Ry:
BIGAM m GA) - ((GAA)) (1n ]
ERy
(32)
> ERz ((GAN)- GA) - B(G ~p (1 GA)
(33)
E BiGa GA) B( GA)
(34)
where ER,
all possible invariant subgraphs and longer depends the specific choice of R By monotonicity of the expectation we conclude that:
E Pp (p Ga)
(35)
< ER, [k1 (Niog + (pooo + (2 id + -poad + (Aii + A }
(36)
B EXPERIMENTAL DETAILS
B. DATASETS
In this study, conduct investigation across 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, provide detailed description of each.
20

---

Published as a conference paper at ICLR 2025
Synthetic datasets
BaMS (Azzolin et al., 2022) is a synthetic dataset consisting of 1,000 Barabasi-Albert (BA) graphs, each with network motifs (house, grid, wheel) randomly attached various positions. Class includes plain BA graphs and BA graphs enriched with either a house, a grid, a wheel, or all three motifs together. Class consists of BA graphs enriched with a combination of two motifs: house and grid, a house and wheel, or 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.
(Gui al., 2023) is synthetic dataset comprising 24,000 graphs categorized into three classes. Each graph consists (or path), or wheel. The motifs are house (class 0), a five-node cycle (class 1), or 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 slass-discimminative subgraph RA (i.e., the motifs) remains fixed, while the bases vary. 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 a Dorogovtsev- Mendess graph (Dorogovtsev and Mendes, 2002).
Motiff-Baad
basis and a motif. The basis can be a ladder, a tree
Mot f-Basis is (Gui al., 2022) is specular Mot f2-Basis, is where the OOD test set contains graphs generated connecting the three motif's above to simple line paths of varying length.
Motif-Size (Gui et al., 2022) is a synthetic dataset consisting of 24,000 graphs categorized into three classes. Similar Mot i 12-Baa each network is composed of basis and motif, with the motif serving as the dlas-diisrimiinaivee subgraph RA- The basis structures include a ladder, a tree (or path), a wheel, a circular ladder, or a star. The motifs are house (class 0), 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 graphs), the basis sizes are increased up to seven times.
Real-world datasets
BBBP (Wu et al., 2018) is a dataset derived from a study on modeling and predicting barrier permeability (Martins et al., 2012). It comprises 2,050 compounds, with 483 labeled as positive and 1,567 as negative.
CMNIST-Color (Gui al., 2022) contains 70.000 graphs of hand-written digits transformed from the MNIST database using superpixel techniques (Monti et al., 2017). The digits are colored according to their domains and concepts. 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 set each contain 10,000 graphs with two new colors introduced specifically for these sets.
LBAPcore Assay (Gui et al., 2023) is 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-Iength is a sentiment analysis dataset based on the NLP task of sentiment analysis, adapted from the work of Yuan al. (Yuan et al., 2022). In this dataset, each sentence is transformed into a grammar tree graph, where individual words serve 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 outto--distribution (OOD) validation and test sets are specifically created to evaluate performance on data with longer sentence lengths.
B.2
IMPLEMENTATION DETAILS
B.2.1 TRAINING AND REPRODUCIBILITY
The models are developed leveraging repositories provided by previous work. Specifically:
21

---

Published as a conference paper at ICLR 2025
-
01
My
U1
Ug
Ug
2/
Uyy
U
(u,)
(u,)
R
R
Figure 2: Existing necessity metries are invariant to the number of truly irrelevant edges that they cover. For a line graph and a 1-layer GNN, the truly relevant edges for predicting the label of u are those in N1 ("1) = fui. uz}. However, existing necessity metrics do not distinguish between R (which contains no truly irrelevant edge) and dummy R' (which contains arbitrarily many).
CIGA, LECI and GSAT are developed based on the repository from Gui et al. (2023), using 605241666275550
commit
11d1ddddaa 1da 63de 3a27 6ad5.
RAGE is implemented using the code available at https: / anonymous.
science/
I/RAGE as described in Kosan et al. (2023).
For CISST, SECNNEVal, following the approach outlined in Lin et al. (2020).
the repository from https: hatp::s//nnnymoouus http:oyyymooss.pp..ssseee.eee scpen.ssiencc//s
To encourage reproducibility, we stick to the hyperparameters provided in each respective repos- itory, except for GSAT on BBBP and BaMS where we set the values of cod. param to 0.5 and extra_pa pam to [rru,, 10, 0.2), and for Mot f2-Basi and Mot f-$ ze in Table 5 where we set the values of ood_param to 10 and extra_pa ram to [True, 10, 0.2]. To favor a fair comparison with the other architectures, we changed the RAGE's default GNN backbone to GIN (Xu et al., 2018), using a mean global readout for the final prediction. Model selection was performed on the ID validation set.
B.2.2 COMPUTING FAITIFULNESS
Necessity: Nec follows the guidelines presented in Section 3.2. The idea is that choosing fixed budget depending, for example, on a dltaset-wide statistic is 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 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 experiments. For each explanation, we sample a number of perturbed graphs, where is fixed at 8 in our experiments and each modification deletes random edge.
Sufficiency: For Suf, instead, we apply two types of perturbations: (i) replace the complement of the explanation with that of random sample from the same data split, joining with random connections the original explanation with the sampled complement; (ii) delete random edges from the complement, as prescribed by Nec. We repeat these interventions for number y of samples for each explanation, where qı is fixed at 8 in experiments, as for Nec. Since the joining operation is performed explicitly at the input level, the resulting procedure can become computationally heavy, especially for large graphs. Alternative approaches try emulate input interventions with latent interventions, where manipulations to the embedding of explanation and complement are applied, respectively (Wu al., 2022; Sui al., 2022). We argue that this type of latent intervention is suboptimal for correct evaluation of faithfulness, as the latent vectors used for interventions are not guaranteed to sufficiently disentangle explanation and complement information, resulting in leakages.
Faithfulness: Faith corresponds to the harmonic mean of the normalized Nec and normalized Suf scores, where we set d as the L, divergence for both metrics, and it is computed over subset of Ø2 of input graphs, which is set to 800 in our experiments. Since most modular GNNs output soft edge scores, we extract the relevant subgraph via TopK selection, where the size ratios vary in {0.3, 0.6, 0.9}. Then, the resulting Faith taken as the best value across ratios. An ablation study compare the resulting scores across varying number of samples d2 and interventions 41 provided in Fig. 10 and Fig. 11. In all experiments, we use the normalized Suf and Nec, such that the values are the higher the better.
22

---

Published as a conference paper at ICLR 2025
Are faithfulness metries well calibrated? In general, all metrics outlined in Table 1 are not calibrated, in the sense that a value of, e.g., 0.5 does not have the same meaning across metrics. This issue is naturally present also in Suf and Nec, and can impair metric comparison across different hyper-parameters. Nonetheless, this is not affecting our empirical investigation as we always stick to the same hyper-parameterr
B.2.3 COMPUTING THE DEGREE OF INVARIANCE (PLAUSIBILITY)
The degree of invariance appearing in Theorem represents how close the predicted subgraph Ro to the truly for stable predictions across domains. Carrying over the terminology from XAI, we compute this quantity as the plausibility (Longa et al., 2024) of the provided subgraph with respect to a known ground truth. Specifically, we compute the ropology-wist degree of invariance as the Weighted Intersection over Union (WIoU) between the provided explanation relevance score, and the expected ground truth scores, which equal for the invariant edges in the graph, and 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. The same is done for computing the plausibility of SE-GNNs with respect to a known ground truth explanation.
input motif, which is assumed to be the only stable factor enabling
B.2.4 IMPLEMENTATION OF FAITHFULNESS-ENFOREE
STRATEGIES
As stated in Section 4.2, included the aforementioned architectural desiderata in several popular models to verify their impact on model accuracy and faithfulness. In the following, we describe how the four desiderata are implemented in practice:
Hard Scores (HS) To enforce the generation of binary 0-1 explanation masks by the detector f. we apply a technique similar the Straight-Through (ST) trick used in the discrete Gumbel-Softmax Estimator (Jang et al., 2017). Specifically, during the forward pass, we utilize the binary version of the mask, while in the backward pass, use the continuous version.
Content Features (CF) To ensure the classifier uses only raw input features, we simply replace the feature matrix with that of the input data before feeding it to the classifier g.
Explanation Readout (ER) The Explanation Readout strategy computes the graph embedding by applying global aggregator encouraging the classifier to adhere more to RA. This involves multiplying the node mask M, obtained by averaging over incident nodes the predicted edge mask, with the node embedding before performing the final global readout, i.e., h& = aggr E V ))). Since explanations are soft scores over GA. this approach ensures the model adheres more closely to the soft mask.
( (f[,,h",
Local aggr (LA) To enhance the expressivity of Graph Neural Networks (GNNs), some models incorporate virtual nodes (Barceló et al., 2020; Hu et al., 2020; Sestak al., 2024). We remove those 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.
B.2.5
CHANGES WITH RESPECT TO THE ORIGINAL CODEBASE
Here we describe two minor changes we did to the original codebase.
Metries. 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
Stable TopK & Permutation-Invarite
To avoid this bias and to have more predictable behavior, we switched to 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.
In synthetic datasets, ground truth edges are typically the last elements as they are attached to an already generated base-graph.
23

---

Published as a conference paper at ICLR 2025
Undirected Explanation Scores. Accordingly to the original version of the codebase intro- duced in Training and Reproducibility paragraph, LECI, and GSAT are averaging the edge attention scores among directions for each undirected edge via torch sparse torch_sparse transpose. However, we found that, even by sticking to the original package versioning, the way transpose is used is not weighting edge scores 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 serch_geometricc tootttouuuuue to_undi rected. More details are available in our codebase.
Table compares performance scores for directed vs undirected explanation scores showing comparable performance aggregated over all datasets and models.
Table 7: 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)
Mot i farif-BBasi Bassss
72
42 =
57 03
82 05
50 i 05
52 04
Motif2-Basia
85
46
75 06
81 06
40 +
77 06
Motif-Size
41
43
51
54
47 +
52 20:000
SST2
83
76 = 06
= 04
77 + 04
+
LBAPcore
71 = 00
69 01
70 :
72 1:00
70 1:
71 1:00
CMNIST
26 10
23 : 03
25 04
28 1:
21 1 03
38 01
C FURTHER DISCUSSION
C.I DOES EXPLANATION INVARIANCE ENTAIL INVARIANT MODELS?
To build intuition, take DI-GNN that, for some input, outputs perfectly invariant explanation RA. Now, if the explanation is not strictly sufficient, by definition there exists modification to the complement of RA (which is domain-dependen that alters the predicted class distribution. Thus the model as whole cannot be domain-invariant
This naturally fits Theorem 1. If the detector outputs perfectly invariant explanations Atopo and feat at the RHS of Eq. (3) are zero, yet the sufficiency term Xauff f can still be larger than zero, meaning that the model can fail invariance (LHS e.g., it might fit ID data properly but OOD data poorly).
We illustrate the relationship between the RHS and LHS in Fig. 3, which shows that despite CIGA having more invariant explanations than GSAT, it has worse sufficiency and they tend to ID and OOD with comparable shift. The plots report the LHS (difference in ID and OOD fit) and RHS and sufficiency) of nine DI-GNNs used in our experiments on two data sets. The x-axis shows that CIGA (yellow) tends to be more domain-invariant (plausible) than GSAT (green) despite having worse sufficiency. The y-axis shows that these models tend to fit ID and OOD data very differently, especially CIGA despite its explanations being more invariant (plausible) than GSAT 's.
As expected, explanation invariance does not entail models are domain invariant.
C.2 CAN WE ACHIEVE STRICT FAITHFULNESS. IN MODULAR GNNs?
In Proposition 4 we provide theoretical argument regarding the impossibility of injective regular GNNs to achieve strict faithfulness. Can we provide similar result for modular GNNs as well? We can answer this question with a constructive argument: Assume a perfectly stable detector f. i.e., it always predicts the same RA for all G' ~ PR- Assume also an injective classifier g such that implements HS, CF, and ER, as described in Section 4.2. Then, intuitively, the classifier uses no information outside of A. as the features is aggregating solely belong to the explanation itself. Then, RA is not changing after perturbations of the complement by the stability assumption, every deterministic GNN will achieve strict sufficiency. Then, by injectivity of g, every modification to RA will change the model output, meaning RA is also strietly necessary.
24

---

Published as a conference paper at ICLR 2025
1.0
1.0
GOODMotif basis
GOODMatif basis
GOODMotif2 basis
GOODMotif2 basis
GOODMotif size
GOODMatif size
LECI
LECI
CIGA
likellhooddifeeeeaa
llkellhaadifffrenee
0.6
0.6
0.2
0.2
0.00
0.25
0.50
0.75
1.00
1.25 1.50
1.75
2.00
1.00 1.25
1.75
2,00
degree invariance (plausibility) (1)
SUF (1)
Figure The plots shows the LHS (difference in ID and OOD likelihood) and RHS (invari- ance/plausibility and sufficiency) of Theorem for nine DI-GNNs used in our experiments on three data sets. The x-axis shows that CIGA (orange) tends be more Nomain-invarian (plausible) than GSAT (green) despite having worse sufficiency. The y-axis shows that these models tend to fit ID and OOD data very differently, especially CTGA despite its explanations being more invariant (plausible) than GSAT 's. The only model achieving considerably low likelihood difference is LECI (blue) for Mot 1alff22BBa5 and Mot fo-tif-Ber BBasis, which scores the best both in explanation invari- ance and Suf. 4 (f) stands for the lower (the higher) the better.
This nice result, however, hinders number of implementation challenges, some of which are already discussed in Section 4.2. In addition, also the possibility of learning truly injective GNN classifiers has recently been questioned (Jaeger, 2023), making this result more of a conceptual blueprint than an actual model design.
Table 8: Many popular DI-GNNs neglect the invariance of node features (Meaa)
Model
Node Feature Invariance
DIR (Wu et al., 2022)
X
VGIB (Yu et al., 2022)
x
OODGAT (Song and Wang, 2022)
X
GTL (Li et al., 2022)
X
GSAT (Miao et al., 2022a)
X
LRI (Miao al., 2022b)
CIGA (Chen et al., 2022)
X
CAL (Sui et al., 2022)
RIGNN Luo et al. (2023)
x
GALA (Chen al., 2023)
LECT (Gui et al., 2023)
DIsC (Fan al., 2024)
GSINA (Ding et al., 2024)
X
C.3 TESTING FOR NON-STRICT SUFFICIENCY
Proposition 5 showed that strict sufficiency is necessary condition for DI-GNNs to be domain invariant. In particular, even if an explanation RA captures the desired invariant subgraph, if not strictly sufficient then the prediction will not be domain invariant. Testing for non-strict sufficiency then amounts to finding a counter-exae eoumper-example of modification outside RA that leads to a change in model output, measure by the chosen d. In Algorithm I illustrate simple algorithm for testing
25

---

Published as a conference paper at ICLR 2025
non-strict sufficiency. which given as imput the imput graph G,,, the predicted invariant subgraph RA- the chosen distribution PR specifying the set of allowed modifications, and a budget perturbations it returns True if R is not strictly sufficient. If the algorithm returns False, then the explanation might still be non strictly sufficient, unless a 2 |pnl and each element of pn is sampled at least once. More efficient algorithms are possible, for example by adapting informed perturbation search under constraints as done in adversarial perturbation search (Gosch et al., 2024).
Algorithm 1 Testing for non strict sufficiency
Require: Input graph G = CA U RA, predicted invariant subgraph R,A, chosen distribution PR.
budget of perturbations о, threshold 7
Ensure: Returns True if the explanation non strictly sufficient
1: for = 1 to do
2: Sample CA ~ PR
3: G¹ C² URA
4: if (GA, Ga 2 then
5: return True
6: end if
7:
end for
8: return False
C.4 CHOOSING FAITHFULNESS PARAMETERS IS TASK DEPENDENT
In light of Definition 2 and Table 1, selecting a faithfulness metric then amounts to choosing a suitable pn. PC, and d. Proposition shows that different parameters are not interchangeable, begging the question of how to properly choose the appropriate metric. In this section, we argue that the choice of metric application dependent: stricter metrics make sense in high-stakes applications, where faithfulness is must, and for providing adversarial robustness guarantees (for, e.g., Machine Learning as a Service), while looser metrics are more meaningful adversarial inputs are not a concern. There is clear monotonic relationship between these, in that being strictly sufficient (resp. faithful) to a stricter metric implies being strictly sufficient (resp. faithful) to the looser one. To see this, consider two different choices for pn:
Strictest choice: ph allows the modification of the complement the explanation in every conceivable way via node/edge addition and removal and arbitrary feature perturbations. Being strictly sufficient wrt p/ means being invariant to any possible change to the complement.
Loosest choice: P allows only node/edge removal. This is the most narrow distribution, and corresponds to the typical setting of sufficiency metrics presented in Table 1. p finds reasonable use in controlled and low-stakes applications, where only minor perturbations are expected.
While dual argument holds for pc. showed in Section 3.2 that some necessity metrics surprisingly flawed, in that they do not capture the desired semantics. Regarding the choice instead, consider similar distinction:
Strictest choice: dt is any divergence between class probability distributions, like L, or KL. accounts for any change in the model's outputs, and it is thus desirable in scenarios where the ranking of classes matters, for example in conformal prediction sets for Human Decision Making (Cresswell et al.).
Intermediate choice: d² is the difference in prediction likelihood, and will only account for changes in the confidence of the predicted class. Thus, df is more suitable in scenarios in which only the most likely prediction is relevant.
Loosest choice: d is the difference accuracy most likely prediction. It only accounts for changes in the most likely class, neglecting any change in the model's s confidence.
Those insights apply to both post-hoe and modular GNN settings.
26

---

Published as a conference paper at ICLR 2025
C.5 FAITHFULNESS METRICS ARE NOT INTERCHANGEABLE
In this Section we complement the empirical analysis of Table 2, showing the results also for Mctif-SAe Sizie-iieeeee and CMNIST.
Table 9: Ranking of models and absolute Suf values according to different interventional distributions PR. averaged over random seeds. Results confirm that faithfulness measures can differ only based on the reference distribution, as both rankings and absolute values can significantly change.
# Ranking (Suf)
Moti f-Size
Mot 12
CMNIST
sdl PR
sif PR
si PR
sd4 PR
sdy Pg
sif PR
LECI GSAT
(79 06)
2 (83 = 06)
1 (81 + 01)
2 (82 63)
(72 19)
1 (82 + 18)
ID
(83 mz)
1 (86 01)
2 (78 01)
(84 02)
(56 13)
2 (59 + 01)
CIGA
(70 04)
3 (72 = 04)
3 (65 +
(73 06)
(30 os)
3 (43 on)
oodi
ood2 PR
oodi PR
PR ood2
PR
PR
LECI
(81 06)
= 05)
2 (83 +
(88 06)
(68 19)
= 13)
OOD
GSAT
(73 01)
= 01)
3 (76 + oz)
(79 = m3)
(50 on
(54 + 13)
CIGA
(55 + 06)
3 (70 = 08)
1 (85 + 0))
2 (86 03)
(35 + 10)
3 (45 +7)
For Mot fitif-Size and Motif2, f2, in two cases out of four just changing the type of perturbation allowed by pR (replacing the complement vs removing random edges; across columns) changes the ranking of models. Instead, changing the graph distribution (ID OOD; across rows) alters the ranking in every case. For CMNIST instead, the rankings are stable across distributions, even absolute values can still sensibly change. Overall, these results confirm that different metrics yielded by different distributions are not interchangeable.
D FURTHER EXPERIMENTS
D.1 FAILURE CASES
Table Model performance scores for SST2 and LBAPcore on ID validation set and OOD test set.
GIN
LBCI
GSAT
Dataset Model
ID val.
OOD test
ID val.
OOD test
ID val.
OOD test
SST2 LBAPcore
= 00
o
= 00
83 + ot
4:00
+ 04
92 = 00
70 0:00
92 00
71 + or
92 =m
70 = 08
As discussed in Section 4.2, SST2-Length and LBAPcore two 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 10 where even a simple regular 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 Fig. 4 and Fig. 5 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 regular-GNN-Ie -Nilkkeee behavior. This especially expected for SST2 -Lngthh which graph-adapted sentiment classification dataset where node features
contextual embeddings extracted from a BERT-lik- Transformer (Yuan et al., 2022) - which produces intrinsically globally- correlated node representations by the nature of its self-attention layers (Vaswani et al., 2017). Indeed, BERT-like Transformers are the models achieving state-of-the-an performance this task (Yuan al., 2022).
27

---

Published as a conference paper at ICLR 2025
100
60
60-
60
density
40
40-
40
0.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
explanation relevance scores
100
100
00-
60
density
40
40
40
0.00 0.50
0.75
1.00
0.25
0.75
1.00
0.00
0.25
0.50
0.75
explanation
Figure 4: Histograms of explanation relevance scores for LECI (top), and GSAT (bottom) on SST2 (seed 1). Both models failed in identifying a sparse input subgraph, assigning constant scores (or very close thereof) to every edge.
28

---

Published as a conference paper at ICLR 2025
100
density
40
40
40
0.00
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
explanation relevance
100
1.00
100
60
00-
60
density
40
40-
40
0.00
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
explanation
Figure 5: Histograms of explanation relevance scores for LECI (top), and GSAT (bottom) LBAPcore (seed 1). Both models failed in identifying sparse input subgraph, assigning constant scores (or very close thereof) to every edge.
probabilty
PR' (ORM), b=(0.]|R[i]
PR' 4 (-.0.
PIR 4PRR1) (=(05)|RRI]
10
20
30
40
50
num truly irrelevant items
Figure 6: Probability of deleting at least 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 truly relevant edges (r 5), and budget b proportional the size of the explanation, the plot shows P(R' e (R))) where R' ~ (G), for a growing number of irrelevant edges in R. The plot shows that the probability is approximately constant, i.c., does not depend on the number of irrelevant edges. The segments with decreasing behaviour (especially visible for 10% budget, the blue curve) correspond to areas where the budget is indeed constant, and thus not proportional the explanation size. For instance, between and 14 irrelevant edges, budget of 10% corresponds to deleting one edge.
29

---

Published as a conference paper at ICLR 2025
Figure Dependency of the necessity met- rics on the size of the explanation. RFid+ and Nec of explanations output by GSAT on Motif2-Bas (averaged over seeds) for dif- ferent explanation sizes (X-axis) and metric hyper- parameter K, E {3%, 5%). RFid+ assigns sim- ilar or even higher scores to larger explanations, while Nec (with budget b proportional to the average graph size m)) decreases for increasing explanation size, expected.
RND1 (x+3%) NFC (b-15)
RHD NEC (b-5%)
0.6
netessity
0.2
0.4
0.4
0.8
1.0
0.6
0.6
0.8
1.0
size ratio
D.2 SENSITIVITY RFid+ AND Nec THE EXPLANATION SIZE
As in the proof of Proposition 3, let S be the set of subgraphs of G obtained by deleting edges from R. while keeping C' fixed, and A = {G' E Sh (GG, G") 2 E} those subgraphs that lead to large enough change in A. Then, in Fig. we numerically simulate the probability of deleting at least one truly relevant edge from an explanation with a growing number of irrelevant ones, where the number of deletions proportional the explanation size. The figure shows that the probability is basically insensitive to the number of irrelevant edges.
In Fig. we integrate the results reported Table 3 and provide more detailed experiment showing that for GSAT, RFid+ is in fact insensible to the number of irrelevant edges in the explanation, while Nec with a suitable pC is not. In Fig. 8 and Fig. 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 (Gui et al., 2023) model over LEAP -Assay (Gui et al., 2022) molecular benchmark.
30

---

Published as a conference paper at ICLR 2025
10%)
NEC 38%
NEC (b=5%)
NEC (b-10%)
0.9
volue
0.4
0.0
0.5
0.8
1.0
0.4
0.6
0.8
1.0
0.4
0.6
0.8
1.0
size ratio
AFID (x (xx35%) NEC (b=3%)
AFID : (k-5%)
RFID+ (x- 10%)
1.0
NEC (b=5%)
NEC (b=10%)
0.6
value
0.2
0.6 1.0
1.0
0.4
size ratio
Figure RFid+ is insensitive to irrelevant edges. RFid+ and Nec with ph are computed for LECI and averaged across 5 seeds on f2-assisssss (top) and LBAPcore (bottom) for different explanation sizes (x-axis) and for different metric hyper-parameter s, b E (3%, 5%, 10%). RFid+ assigns similar or even higher scores to larger explanations, while Nec tends to penalize larger explanations.
31

---

Published as a conference paper at ICLR 2025
RFID+ (s 3%)) NEC (bm3%)
RFD+ (x 5%) NEC (b-5%)
RFID (K 10%)
NEC (b=10%)
0.8
value
0.4
0.0
0.4
0.6
0.8
1.0
0.4
0.6
0.8
1.0
0.4
0.6
0.8
1.0
size ratio
1.0
RFID+ 3%)
RFID+ (x 5%) (b-5%)
RFID+ 10%)
31))
NEC (b-10%)
0.0
value
0.2
0.6
1.0
1.0
0.4
size ratio
Figure RFid+ is insensitive to irrelevant edges. RFid+ and Nec with Ph are computed for GSAT and averaged across 5 seeds Moti f2-Basis (top) and LBAPcore (bottom) for different explanation sizes (x-axis) and for different metric hyper-parameter s, b E (3%, 5%, 10%]. RFid+ assigns similar or even higher scores to larger explanations, while Nec tends to penalize larger explanations.
32

---

Published as a conference paper at ICLR 2025
RAGE
Validation set
Test set
0.8
0.8
0.7
0.6
0.5
0.8
0.6
0.6
0.4
0.4
100
500
600
1500
2500
100
500
800
1500
2500
budget
Size
LECI
Validation set
OOD test
0.8
0.8
0.6
0.6
falthllnnes
0.4
0.4
0.6
0.6
0.4
100
500
800
1500
2500
500
800
1500
2500
budget
Moti2
Motik-Siee
Figure 10: Ablation study of faithfulness scores varying number of number of samples d2-
33

---

Published as a conference paper at ICLR 2025
RAGE
Validation set
Test set
0.8
0.8
0.7
0.6
0.5
0.8
0.6
0.6
0.4
0.4
16
20
12
16
20
budget
LECI
Validation set
OOD test
0.70
0.70
0.60
0.60
falthfulness
0.50
0.50
20
12
budget
Motif2
Motik-Siee
Figure 11: Ablation study of faithfulness scores across varying number of interventions 91-
34


Reviews:
[{"review_id": "cqpebYyKAr", "reviewer": "Reviewer_2N4z", "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.", "questions": "See in Weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 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.", "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.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B7dlXPXDPk", "reviewer": "Reviewer_s1hn", "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.", "questions": "Please look at the weaknesses for open questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and the motivation is very clear.\n\n2. The authors detail the importance of the faithfulness metric in graph explanations, highlighting the pitfalls of diverse metrics and the trade-offs between them.\n\n3. The paper presents an interesting analysis between regular, self-explainable, and domain-invariant graph neural networks.", "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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fa7nE3zJSv", "reviewer": "Reviewer_5LA6", "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.", "questions": "See the weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 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.\n2. The paper present an in-dept analysis of existing graph XAI metrics.\n3. The experiments are solid.", "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).\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1g57q24h6m", "reviewer": "Reviewer_feco", "summary": "In this paper, the authors study the faithfulness of explanations generated concerning Graph Neural Networks (GNNs). Specifically, they claim the following main contributions:\n\n1. 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.\n2. They prove that perfectly faithful explanations may be completely uninformative in injective GNNs.\n3. They explore the connections between faithfulness and domain invariance.", "questions": "Please address the concerns and questions in the *weakness* part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. GNN explanations' faithfulness is crucial in real-world applications and academic research.\n\n2. The experiments on four popular datasets including Motif2 show an empirical evaluation of the proposed method.", "weaknesses": "> W1. Concerning contribution 1:\n\nThey 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).\n\nHowever, \"faithfulness\" naturally can be evaluated by various metrics, and it is **unnecessary** that the evaluation results should be consistent with each other. \n\nTake 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.\n\n\n> W2: Concerning contribution 2:\n\nThey prove that perfectly faithful explanations may be completely uninformative in injective GNNs (Prop. 4).\n\nHowever, 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$\"?\n\n\n> W3. Concerning the target tasks:\n\nAre 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.\n\n> W4. Concerning the experiments:\n\nThe purpose of some experimental results is unclear. \n\nOne of the contributions is the new faithfulness metric (as well as Nec and Suf), while their superiority is not explored by further experiments. \n\nInstead, 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.\n\nIn other words, the paper proposes to \"reconsider\" the faithfulness metric, while comprehensive experiments of comparing metrics are missing.\n\n> W5. Concerning the writing:\n\nW5a. Most figures and tables are really far away from their corresponding statements, requiring to jump over the pages repeatedly.\n\nW5b. Some key statements are missing, e.g., the choice of d in Lines 279, and what does \"value\" mean in the y-axis? \n\nW5c. Are the graph- or node-level classification tasks considered? Or do different propositions/statements fit different tasks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)