GNN Explanations that do not Explain and How to find Them
Authors: Steve Azzolin
Stefano Teso
Bruno Lepri
Andrea Passerini
Sagar Malhotra
Venue: ICLR 2026 Poster (2026)
Keywords: graph neural networks
explainability
self-explainable
auditing
faithfulness
Primary area: interpretability and explainable AI
TL;DR: We found that Self-explainable Graph Neural Networks can output explanations that do not explain. We also found that faithfulness metrics can fail to detect these explanations. To solve this undetectability, we propose a benchmark and a new metric.

Abstract: Explanations provided by Self-explainable Graph Neural Networks (SE-GNNs) are fundamental for understanding the model's inner workings and for identifying potential misuse of sensitive attributes.
Although recent works have highlighted that these explanations can be suboptimal and potentially misleading, a characterization of their failure cases is unavailable.
In this work, we identify a critical failure of SE-GNN explanations: *explanations can be unambiguously unrelated to how the SE-GNNs infer labels.*
We show that, on the one hand, many SE-GNNs can achieve optimal true risk while producing these degenerate explanations, and on the other, most faithfulness metrics can fail to identify these failure modes.
Our empirical analysis reveals that degenerate explanations can be maliciously planted (allowing an attacker to hide the use of sensitive attributes) and can also emerge naturally, highlighting the need for reliable auditing.
To address this, we introduce a novel faithfulness metric that reliably marks degenerate explanations as unfaithful, in both malicious and natural settings.
Our code is available on [GitHub](https://github.com/steveazzolin/gnn_deg_expl).

Published as a conference paper at ICLR 2026
GNN EXPLANATIONS THAT DO NOT EXPLAIN AND How TO FIND THEM
Steve Azzolin Stefano Teso
Bruno Lepri!
Andrea Passerini!
Sagar Malhotra 8
ABSTRACT
Explanations provided by Self-explainable Graph Neural Networks (SE-GNNs) are fundamental for understanding the model's inner workings and for identifying potential misuse sensitive attributes. Although recent works have highlighted that these explanations can be suboptimal and potentially misleading, characterization of their failure cases is unavailable. In this work, we identify a critical failure of be unambiguously unrelated how the SE-GNNs infer labels. We show that, on the one hand, many SE-GNNs can achieve optimal true risk while producing these degenerate explanations, and on the other, most faithfulness metrics can fail to identify these failure modes. Our empirical analysis reveals that degenerate explanations can be maliciously planted (allowing attacker to hide the use of sensitive attributes) and can also emerge naturally, highlighting the need for reliable auditing. To address this, we introduce a novel faithfulness metric that reliably marks degenerate explanations as unfaithful, in both malicious and natural settings.
SE-GNN explanations: explanations
INTRODUCTION
Seff-Explainable GNNs (SE-GNNs) combine the predictive power of standard GNNs with ante-hoc explainability (Miao et al., 2022a; Chen et al., 2024). They couple an explanation extractor, which identifies explanatory subgraphs, with classifier that uses these subgraphs to generate predictions. Being designed with explainability in mind, SE-GNNs promise to be genuinely interpretable and therefore suitable for high-risk use cases, e.g., power grid analysis (Varbella et al., 2024), health forecast (Hu et al., 2024), and drug discovery (Wong et al., 2024).
Despite their promise, previous work has highlighted weaknesses in SE-GNNs' explanations. For instance, they can be redundant (Tai et al., 2025), ambiguous (Azzolin et al., 2025b), may not fully reflect the individual importance of each of their sub-components (Chen et al., 2024), and can be affected by spurious correlations (Wu et al., 2022). Nonetheless, little research has focused on whether there exist cases in which SE-GNN- catastrophically fail to provide meaningful explanations.
In this work, we identify critical failure case of SE-GNN' explanations: explanations can be unrelated to the SE-GNN's inner workings (see Fig. for an example). Such explanations are unambiguously unfaithful, undermining the original purpose of SE-GNNs, raising the risk of ex- planations concealing the use of protected attributes, and impairing model debugging and scientific discovery. First, we theoretically show that, under mild assumptions, several SE- GE-GNNs can output these unfaithful explanations while achieving optimal loss. We then exploit this result to answer the following questions positively:
RQI: Can SE-GNN be manipulated to output maliciously defined unfaithful explanations?
RQ2: Can these unfaithful explanations go undetected by faithfulness metrics?
RQ3: Can these unfaithful explanations also emerge without manipulation?
To address the undetectability of these unfaithful explanations, we present a benchmark for faithful- ness metrics and novel evaluation metrie, EST, that is shown be more robust. More generally, our work warns practitioners from blindly trusting SE-GNN explanations, highlights avenues to make these models more reliable, and provides users with more reliable tools to audit their explanations.
Conresponding author: wtwee. azzolineuninn....
University of Trento, Italy
Fondazione Bruno Kessler, Italy
TU Wien, Austria

---

Published as a conference paper at ICLR 2026
2 BACKGROUND
Graph Classification. We consider the standard supervised graph classification setting, where the goal is to learn a deterministic graph classifier ff mapping from the set of graphs G to the set of labels ), typically implemented
GNN (Bacciu et al., 2020). A graph G (V, E) is defined as a set V of nodes connected by edges E, and both can have features associated with them. We write R C G to denote that R is subgraph of G, and [G] to denote the size of the graph in terms of nodes, edges, or both, as will be clear by the context. Subgraphs may preserve all, some, or none of the features.
Self-explainable GNNs. SE-GNNS aim to enhance the interpretability of graph classifiers by generating explanations during inference (Miao et al., 2022a;b; Chen et al., 2024). An SE-GNN consists of two components: (1) an explanation extractor e that maps the input graph G to subgraph e(G) = R S G, and (2) a classifier g that takes R as input and produces the final prediction:
S(G) - g(e(G))
The explanation extractor e can either produce per-edge relevance scores Pue = (a, E [0, 1]. or per-node relevance scores P.. = e(G),, E [0. 1], which are thresholded or top-k selected to form the explanatory subgraph R (Wu et al., 2022; Tai et al., 2025). We will focus on per-node relevance scores, but our analysis also applies to per-edge scores. Also, we say the explanation extractor is hard if it outputs scores in {r, 1). where r is either 0 or an speGNic hyperparameter; the precise value will be clear from the context. We will assume [ > 0 to prove our theoretical result.
Faithfulness metrics. At high level, faith- fulness metrics assess whether the predictor's output changes upon perturbing the input (Az- zolin et al., 2025a). Metrics that estimate an ex- planation's 's sufficiency perturb the complement of the explanation subgraph while keeping the rest unchanged, while metries that evaluate its necessity do the opposite. An explanation is con- sidered highly faithful if perturbing the comple- ment does not induce large shift, and if perturb- ing the explanation does. Different metrics also differ based on the set of perturbations I they allow: i & ii) Complement removal and Expla- nation removal metrics erase the complement and the explanation altogether, respectively; iil) Edge removal metrics erase edges random; iv) Complement swap metrics replace the com- plement of an explanation with that of another graph. With a slight abuse of notation, we use G' E if G' is obtainable from G by applying the perturbations given by I. We summarize existing metries in Table 1.
Table Taxonomy of popular faithfulness met- rics, grouped by whether they estimate necessity vs. sufficiency of explanations, and by the family of perturbations I they employ.
Perturbations
Type
Metrics
Explanation
Fid+ (Yuan et al., 2022)
Nec.
removal
PN (Tan et al., 2022)
RFid+ (Zheng et al., 2023)
Nec.
Edge removal
Nec (Azzolin et al., 2025a)
Fid- (Yuan et al., 2022)
Complement
Suff.
PS (Tan al., 2022)
removal
GEF (Agarwal et al., 2023)
RFid- (Zheng et al., 2023)
Suff.
Edge removal
SimOAR (Fang et al., 2023)
Complement
Suff.
Suf (Azzolin et al., 2025a)
swap
Suff
All
EST (Ours. Definition 1)
3 SE-GNNs'S EXPLANATIONS THAT DO NOT EXPLAIN
In this section, we study SE-GNNs through the lens of their loss functions, and provide a sufficient condition to achieve optimal true risk for several representative SE-GNNs, namely, GSAT (Miao et al., 2022a), LRI (Miao et al., 2022b), CAL (Sui et al., 2022), GMT-lin (Chen et al., 2024), and SMGNN (Azzolin et al., 2025b). Surprisingly, this condition is met by degenerate explanations highlighting recurrent patterns with no dlaus-iiscrmmiative power, like background pixels for object recognition or punctuation for text classification.
We formalize a class of such recurrent patterns for graphs as an anchor set: a set of single-node subgraphs 2
|}|] and 2, G. for all instances G G and for all 2 Z. Anchor sets can be seen as a collection of prototypes, one for each class, appearing in every graph.
/= { where
As example, green (O) and violet (O) nodes form anchor set 2 in Fig. 1. Nodes in an anchor
2

---

Published as a conference paper at ICLR 2026
G
R
Task
= (#blue #red}
y
i
e(G)
g(R)
Anchor set
2 = (0,0)
==1
9=1
Figure 1: SE-GNNs couple an explanation extractor producing an explanation R, and a classifier
using R to infer the prediction. We identify critical failure case of SE-GNNs, Le., degenerate explanations explanations that encode the label but are unrelated to how the model actually infers it. this example, green (O) and violet (o) nodes appear identically in every graph and form an anchor set 2, hence they have no tlass-discrmminatii power by construction (see Section 3 and Example for details). Yet the explanation extractor e can exploit them to secretly encode the predicted label while hiding the use of red and blue nodes. Such explanations are highly unfaithful and mislead users by falsely suggesting that green and violet nodes are relevant for the label.
set have no diariiiscrem power, as they appear in every sample. Nonetheless, we show that picking them explanations can be optimal solution for SE-GNNs.
Theorem 1. Let Dyxy be a data distribution with deterministic ground truth labeling function G V, e be a hard explanation extractor, and Z (Zylyey be an anchor set. Then, there exists an explanation extractor e(G) = Zo(G) and a classifier g(2y) implemented by GSAT, LRT, CAL, GMT-lin or SMGNN achieves optimal true-risk.
such that the SE-GNN g
The proof is provided in Appendix B. Theorem shows that the explanation extractor can use any recurrent set of nodes as label-encoding explanations for the classifier. These explanations are unambiguously unfaithful. To see this, consider highly accurate SE-GNN. If it relied solely explanations from the anchor set Z, it would be unable to predict the label at all, as these nodes constant across graphs. In order to attain high accuracy, must be looking other parts of the input graph, yet these are not revealed by the explanation. Hence, Theorem shows that SE-GNNs with optimal true risk can provide completely unfaithful explanations. This gives rise rather counterintuitive degenerate explanations, as depicted in the following example.
Let us consider the binary graph classification dataset RBGV, where graphs are com- posed of red and blue nodes randomly connected (see Fig. 1). Positive graphs are those where the number of blue nodes (#blue) exceeds the number of red nodes (#red). Every instance further contains two single isolated nodes, one green (Ugreen) and one violet (Upiotet). Therefore, green and violet nodes form a valid anchor sei 2, and are completely irrelevant to the task that only depends on red and blue nodes. However, the following SE-GNN's explanation extractor and classifier g can achieve perfect task accuracy while providing explanations consisting of green and violet nodes:
Example 1.
if R Ugreen
Ugreen Uyiolet
if #red 2 #buu
R R=e(G)
g(R)
1
if R Uviolet otherwise
if #blue > #red
0.5
Notably, Theorem 1 can be extended beyond sets of nodes appearing in all graphs (see Appendix B.2 for formal analysis): First, members of mutually-exclusin sets nodes appear across graphs, the explanation extractor
partition them into class-specific blocks {{20.... , 2n Joey, which the classifier then maps to the respective labels. Second, the explanation extractor can encode predictions inside subgraphs if no node-level anchor set (or class-specifh partition) exists. In fact, discuss in Section 6 an SE-GNN where the optimization avoids single-node degenerate explanations but still highlights task- iireeerteev subgraphs.
consequence Theorem is that the same explanation can appear for opposite classes for different optimal SE-GNNs, i.e., explanations fail to be consistent (Dasgupta et al., 2022). Specifically, given
3

---

Published as a conference paper at ICLR 2026
an optimal SE-GNN per Theorem 1 and permutation : + y of class indices, it is possible to construct another SE-GNN, say ,E-GNN,, composed of
e (G) == ()((()) and In(2y) :=
that also achieves optimal true risk. This is made intuitive by Example 1, where it is possible to swap Ugreen with Upiiiiet. across classes in Eq. (2) without altering the final predictions.
As final remark, although Theorem 1 covers a broad range of SE-GNNs, alternative formulations outside its scope exist, such as D DIR (Wu et al., 2022) and SUNNY (Deng & Shen, 2024). These models enforce compact explanations through an explanation-selection mechanism retaining a fixed ratio K of nodes, with K a hyperparameter. We will empirically show in Section 6 that an inappropriate choice of this hyperparameter can, however, still force the label to be encoded in degenerate explanations.
Takeaways. Theorem shows that SE-GNN explanation extractor e can output perfect label-encoding subgraphs which, with an appropriate classifier 9. provide optimal truc-risk. Yet such label- tabel-encoding subgraphs can be completely degenerate. These explanations are highly unfaithful, as they only need to convey an encoding of the label to the classifier, without giving any insight into how the overall model arrives at the decision. Next, we show that a malicious attacker can exploit this failure case to make SE-GNNs output fabricated explanations concealing the model's inner workings.
4 RQI: CAN SE-GNN EXPLANATIONS BE MANIPULATED?
We introduce an attack to SE-GNNs aimed at training accurate models that, however, provide explanations unambiguously unrelated how SE-GNNs infer their predictions. This is significant in two distinct ways: First, it shows how an attacker can manipulate explanations without impairing accuracy, potentially misleading users and concealing reliance on protected features. Second, offers a controlled, reproducible setup for evaluating faithfulness metrics, as we will discuss in Section 5.
Setup Our attack comprises two main steps: First, the attacker defines designated malicious explanation for each class; Second, they encourage an SE-GNN to output the designated explanation while optimizing for downstream performance. In practice, it amounts training the SE-GNN using regular classification loss Les paired with a binary cross-entropy loss Leaps designed to push the relevance scores of nodes belonging to the designated explanation p% to and the rest to O, that is:
min 9.
Σ Larlg, e, G,y) + Lezpi G,y), G.y
(espi(e, G. G. = [
1
Σ BCE(e(G)u. (3)
NEV
To ensure Lerpt does not conflict with other regularization terms, it is preferable to deactivate these. We provide further details in Appendix D.1.2.
Datasets and designated explanations We empirically evaluate this attack on one synthetic dataset- RBGV, introduced in Example 1 and three real- wallworld datasets: MNISTsp (Knyazev et al., 2019), MUTAG (Debnath et al., 1991), and SST2P.' To underscore the counterintuitive nature of our results, we will focus on designated explanations belonging to an anchor set, which are therefore unrelated to the task being solved. Specifically, our designated explanations include only nodes that i) are not predictive of the label, and ii) can be used by the SE-GNN to encode its prediction. Examples include green/violet nodes for RBGV, background pixels for MNTSTsp, and punctuation for SST2P. We report in Appendix 1 the full list of the designated explanations for each dataset in use in our experiments. Under ideal circumstances, model that always and only relies on these unrelated subgraphs should be weakly predictive of the true label. Surprisingly, however, SE-GNNs can be trained achieve high accuracy even when using them as explanations. As it turns out, they can do so by. in essence, encoding the predicted label in the (relevance scores of the) explanation itself. even when the highlighted subgraph alone is uninformative for the label.
Evaluation metries We assess the success of the attack by comparing the task accuracy of the attacked model with that of an unmanipulated baseline. Also, to evaluate how well the predicted explanations align with the designated ones, we compute the Fi score" between predicted and designated relevance
*SST2P is variant of SST2 (Yuan et al.. 2022) where we ensure single '.' and single " to be present in every graph. To avoid the emergence of unwanted correlations, append them isolated nodes and with fixed embeddings Ō (for "") and i (for (.)) More details available in Appendix D.4.
We prefer F, over AUCROC (Luo al., 2020), which ignores non-sparse yet accurate relevance scores.
4

---

Published as a conference paper at ICLR 2026
scores. Specifically, for each node, binarize relevance scores as (pr, 0.9) if p/ = and (p > 0.13 if p. = 0- to penalize uncertain relevance scores, and then report the average across classes. The Fi score is computed only nodes from correctly classified graphs, as designated explanations cannot be learned if the underlying model fails to infer the right label.
Results Table 2 lists the results of attacking three representative SE-GNN architectures, namely GSAT (Miao et al., 2022a), DIR (Wu et al., 2022), and SMGNN (Azzolin et al., 2025b), averaged over five random seeds. Crucially, the attack always succeeds: all attacked models output explanations similar to the designated ones (Fi 2 92%). The exception is SMGNN on SST2P (Fi R 59%). This because the SST2P test set includes
Ofi---iiiiiitttinnn (OOD) graphs (Wu et al., 2022), which are inherently more difficult to recognize for models not designed for OOD generalization. In fact, computing the F1 on the in-distribution validation set yields much higher value (F) = 96.5 + 0.8), supporting this observation. We report several example explanations for each dataset in Appendix E.2.
Yet, attacked models perform comparably to their unmanipulated counterparts. The excep- tion SST2P, where attacked models slightly underperformed: the difference is however within one standard deviation for two models out of three. Another interesting case is MNISTsp: while the manipulated GSAT performs slightly worse (-1% Acc), DIR and SMGNN perform surprisingly better (+50% and +5% Acc, re- spectively). This suggests that encoding the pre- dicted label into the explanation can help models improve their own prediction accuracy during training. We will expand on this in Section 6.
Table 2: SE-GNNS can be successfully attacked to output arbitrary explanations while making accurate predictions. We report the test accuracy of unmanipulated models trained following stan- dard practices, cf. Appendix D.I, (Natural), and of models trained according to Eq. (3) (Attack). We also report, for the latter, the test Fi score com- puted for the designated explanation of Table
Natural
Attack
Dataset
Model
Acc
Acc
Fj score
GSAT
100.0 =u
99.1 1:
99.7 =:22
For transparency, we report in Appendix E.3 some cases in which the attack failed to match the designated explanation exactly. Nonetheless, even in these cases, we show that it still managed to force the models into concealing the features they are truly relying on.
R3GV
99.8
99.8
99.4
SMGNN
100.0 =
100.0 a
99.6 +:
GSAT
94.7 +:0
93.8 +u
93.6 +
MN
DIR
41.8 = ms
94.7 a:
96.3 e
SMONN
89.9
95.3
94.9
GSAT
80.6 6:
79.6 a
95.0 2:68
MUTAG
DIR
76.1 1.37
77.5 1.33
92.6 1.36
SMGNN
79.2
78.2 t
94.9 68
These results allow us to answer RQ1 in the affirmative: in the vast majority of cases, our attack successfully teaches SE-GNNs to output degenerate explanations unrelated the task at hand, all without degrading (and sometimes improving) predictive performance.
GSAT
84.0
82.6
97.2
SST2P
DTR
84.3 1:
82.3 1:
95.8 1
SMGNN
83.1 +:
82.8 +2
59.2 = u.3
Consequences for evaluating plausibility. Our attack can be naturally employed to teach SE-GNNs to output plausible but unfaithful explanations. We test this empirically in Appendix 1, due space constraints: in this experiment, the attacked SE-GNNs learn to output highly plausible explanations, i.c., explanations very close to human-defined ground-truth explanations, but are shown also rely on attributes that do not appear in the predicted explanations. This result entails that evaluating the plausibility of explanations (Miao et al., 2022a; Wu et al., 2022; Chen et al., 2024; Tai et al., 2025), i.e. how well they match human expectations, does not reflect their trustworthiness.
RQ2: CAN UNFAITHFUL EXPLANATIONS GO UNDETECTED?
As we just saw, plausibility metrics cannot detect unfaithful explanations. The question is whether metrics explicitly designed to measure faithfulness, in fact, can. This question is currently unanswered: so far, faithfulness metrics have been validated either by comparing them against ground-truth explanations by correlating them with rankings induced by progressively randomized explanations (Fang et al., 2023; Zheng et al., 2023; 2025). Neither setup explicitly tests whether they can identify known-unfaithful explanations.
We fill this gap by proposing an empirical benchmark (Section 5.1) that exploits the failure cases outlined in Section 3 for evaluating faithfulness metrics in practice. Overall, our results indicate that
5

---

Published as a conference paper at ICLR 2026
Table 3: Previous metries can fail to reject degenerate explanations. We report RejRatio, for representative metrics from Table 1 and for EST (Definition 1). Cases where no edges could be removed are marked with '." Bold entries (underlined) indicate best (second best) results.
Dataset
Model
RejRatior
Fid-
Fid+
Suf
Nec
CF
RFid-
RFid+
EST (ours)
SMGNN
12
20
00
05
00
48
RBGV
GSAT
12 21
15
03
50
11
49
DIR
2
27 24
03 03
39 + 08
08 + 06
=
SMGNN
88
58
99
55
92
99
75
100
MNISTsP
GSAT
65 09
38 00
99 01
44 a: 05
95 +: 0z
99 01
61 0:04
100 0000
DIR
93 on
55 on
99 01
54 05
91 + o1
99 + 01
69 =007
100 0:00
SMGNN
59
05
99
57
55
72
65
96
MUTAG
GSAT
+:2
05 02
00
53 07
68 + 17
70 + 14
61 = 05
DIR
70 13
04 = oo
99 = 00
54 = m
69 + us
75 + on
62 =: 04
97 :: 02
SMGNN
08
44
14 05
23 1: m
04 1
54
SST2P
GSAT
3:
07 =
37 + 18
+ 08
d: 15
DIR
50 12
09 06
12 1: 06
42 1: 10
05 1:
49 03
existing faithfulness metrics can be surprisingly ineffective. To amend this issue, we introduce simple but more reliable metric (Section 5.2).
BENCHMARK OF FAITHFUUNESS METRICS
Section 4 shows that one manipulate SE-GNNs output degenerate unfaithful explanations. In this section, we exploit this result to construct a controlled benchmark where faithfulness metrics are evaluated based how well they can judge inown-unfaithfu explanations, where these extracted from the manipulated models Section 4.
Experimental setup:
We select set of representative faithfulness metrics from Table 1, one for each family of perturbation. We also include the Counterfactual Fidelity (CF) (Chen et al., 2024), a metric that does not readily fit into Table 1, it perturbs both the complement and the explanation based on the raw relevance scores, which may not be available (Ma et al., 2025). Details about metric implementations are provided in Appendix D.6.
To find common evaluation setup across metrics, we adopt a similar setting as Bhattacharjee & von Luxburg (2024) where auditor is asked to validate set of explanations given by an external provider, rejecting those that are unfaithful. In particular, given set D {(G,, R;)} of input graphs and associated explanations, we define the rejection ratio for metrics estimating sufficiency as:
RejRatio, (D) = D
Σ (G.R)ED
max Hg(e(G)) # g(e(G)))) Geez
(4)
RejRatio, computes the fraction of instances deemed unfaithful by each metric, where I the set of perturbations allowed by the metric in use (cf. Table 1). For necessity metrics, the inner condition is replaced with (g)) = g(e(G")) }. To make the computation tractable, Eq. (4) evaluated on a budget of perturbations per sample, fixed to 50 across metrics. Details are available in Appendix D.2.
Results: Table reports the RejRatio values computed for the attacked models of Section and, for completeness, the metrics themselves in Table 6. Since those models are trained to output unfaithful explanations intentionally, we aim to observe as large rejection ratios as possible. However, Table 3 shows that some metrics catastrophically fail to reject these explanations, shown by the ratios around zero for Suf, RFid-, and CF in RBGV, for Fid- in SST2P, and Fid+ in MUTAG.
In conclusion, these results positively answer RQ2: previous faithfulness metrics can fail detect the known-unfen -nfon-unfathfuu explanations extracted in Section 4. To solve the undetectability unfaithful explanations, introduce evaluation metric that is shown to be more robust.

---

Published as a conference paper at ICLR 2026
5.2 SPOTTING THE FAILURE CASES: A RELIABLE FAITHFULNESS METRIC
We observe that existing metrics can fail because each of them focuses on restricted set of perturba- tions, such as edge or complement removals, and for each of them, it is possible to construct unfaithful explanations evading detection under the chosen perturbations. For instance, sufficiency metrics that only perturb edges cannot probe models that rely primarily on nodes for their decisions." 3 This is best seen in Example 1, where the explanations Ugreen and Vesolet will go undetected by any metric perturbing only edges, and Ugreen will also be undetected by any metric testing only complement removals, as feeding Eq. (2) with G' = Ugreen preserves the prediction. This observation generalizes to the case where sufficiency and necessity are evaluated jointly, as discussed in Appendix F.I.
Building on these observations, we propose the Extension Sufficiency Test (EST) metrie: Definition 1 (EST), Let G be an input graph with prediction g(e(G)) and associated explanation R = e(G), and d(.) suitable distance measure. Then, EST estimates the sufficiency of R as follows:
EST(R,
max RCG'SG
([(ee()).,(e(())))
(5)
EST is a simple but robust faithfulness metric that avoids the previously underlined issues by holistically considering all supergraphs G" of R contained in G. regardless of what perturbations are necessary for constructing them fromfrom R. Note that EST, similarly to previous metrics (Hase et al., 2021; Zheng et al., 2023), may create an OOD supergraph G" whose prediction differs from that of G just because it is OOD, leading to a large (i.e., worse) EST value regardless of whether was faithful. However, without access the model or to the data distribution, it is impossible to know whether G' is OOD or if it was obtained by perturbing the features the model is relying on. For this reason, we prioritize more conservative metric that, although it may flag faithful explanations as unfaithful, it reliably marks the unfaithful ones as such, minimizing the risks of users being deceived. We provide more details and algorithm implementing EST in Appendix D.6 and Algorithm 1.
To avoid the computationally prohibitive cost of enumerating all possible supergraphs of R within G in Definition 1, we fix a budget of supergraphs test in practice. Also, note that EST estimates only the sufficiency of explanations; since the classifier may be sensitive to changes in the explanation even when unfaithful, necessity metries are unsuitable for identifying the failure cases in Section 3 (see Appendix F.2). We additionally leverage existing literature on SE-GNNs to theoretically characterize which family of explanations is deemed unfaithful by EST, by relating Definition 1 with increasingly weaker formal notions of explanations (Azzolin et al., 2025b). This analysis, reported in Appendix F.3, shows that EST provably labels the class of explanations including Ugreen and Uviolet in Example 1 as unfaithful. We now proceed to analyze how EST fares at the benchmark introduced in Section 5.1.
Results. The last column of Table lists the results for EST, which is the only metric consistently achieving the highest- or close to thereof rejection rejectonn ratios across every configuration while keeping a relatively low standard deviation. In particular, in all the cases where previous metrics score a rejection ratio around zero, EST rejects at least x 50% of degenerate explanations. This result can be easily further improved by increasing the budget of allowed perturbations. In fact, we show in the appendix (Fig. 2) that the rejection ratio of EST monotonically increases with the budget, reaching s 65%. Other metrics, instead, either do not benefit from larger budgets or flatten around R 17%. In addition, EST also correctly recognizes non-degenerate explanations that include all relevant information, which are instead erroneously rejected by Suf and CF, as shown in Appendix E.4.
We proceed analyze how EST behaves in natural settings, and to verify whether the failure cases of Section 3 can in fact emerge even without malicious attacks.
6 RQ3: CAN DEGENERATE EXPLANATIONS EMERGE NATURALLY?
Finally, we show that SE-GNNs can output degenerate explanations - similar to those presented in Section 4 - without any explicit manipulation, and that EST is effective in finding them.
In practice, we compute EST's rejection ratios for each SE-GNN across the dataset and complement this with qualitative analysis of explanation examples, reported in the appendix. This analysis aligns
3 "thhough GNNs ideally depend on both topology and node features (Bechler-Speicher et al., 2025), reliable faithfulness metric should remain robust when only one of these is truly relevant.
7

---

Published as a conference paper at ICLR 2026
Table 4: A natural training of SE-GNNs can result in degenerate explanations. We report test accuracy, rejection ratios for EST, Fid-, and RFid-, and some case-by-case illustrations of representa- tive explanations. AUCROC reported only for datasets with known ground truth explanation. This analysis is performed only for well-performing models.
Dataset
Model
Test Acc
AUCROC
RejRatioz Fid-
Iilustration
EST
RFid-
GSAT
100.0 =000
59.3 09.
12.0 n19
6.2 + 124
Fig. 11
RBCV
DIR (K 1%)
98.0 4:03
70.2 188
27.7 m3
30.3 166
Fig. 12
SMGNN
98.9 001
86.8 2044
54.1
77.6 196
Fig. 13
MNISTsP
GSAT
94.7 0.
82.5 a 1.53
2.4 20
14
5.3 4.50
Fig. 14
DIR (K
10%)
20.0 29
SMCNN
86.8 s0
43.2 185
99.5 # o.
68.9 = 201
95.5 #447
Fig. 15
GSAT
80.6 1:10
64,5 17
50.7 9:
36.8 11
Fig. 16
MUTAG
DIR (K 156)
53.5 1:
SMGNN
77.9 24
75.2 4:99
61.9 4.
50.3 2M1
Fig. 17
GSAT
84.0 1:09
0.0 1: 0.00
0.0 0000
0.0 1:00
Fig. 18
SST2P
(K 10%)
82.5 1.09
49.5 101
37.8 :: 189
14.4 116
Fig. 19
SMGNN
83.0
4.3 d: 1.1
1.7 2.8
4.4
Fig. 20
with EST's results: when the rejection ratio is high, explanations highlight subgraphs; when rejections are near zero, explanations emphasize class-discrmminative subgraphs, often aligning with human expectations.
We train the SE-GNN architectures in Table 2 by following their original protocol and natural losses, tuning their hyperparameters to encourage explanation sparsity. For DIR, the original implementation selects explanations based relatively large top-K; train the model using a much smaller K instead, as indicated in the results table. This is useful to show that DTR can still encode label-relevant information inside small subgraph even when the subgraph has no discriminative power by itself. For each model, we report the accuracy, the AUCROC with the ground truth explanations when these are available, and compare the rejection ratios of EST with those of Fid- and RFid- (as baselines). Further details on the experimental setup are available in Appendix D.3.
Setup:
Results: As shown in Table 4, the results are largely consistent with those for naturally trained models in Table 2, with few exceptions. On RBGV and MNTSTsp, SMGNN achieves modest decrease in accuracy (5x 2%). For DIR,, instead, the small K value hinders learning on MUTAG, and the accuracy on MNISTsp ( 20%) confirms DIR's unsuitability for this task, in line with the accuracy reported in Table (+% 40 + 20%). In RBGV and SST2P, reducing DIR's K substantially (from 50% to 1% and from 60% to 10%. respectively) results in only RJ 2% drop in accuracy. This is remarkable, as DIR does not fit in Theorem 1, and yet can encode label-relevant information inside degenerate explanations, as illustrated in Fig. 12 and Fig. 19. Interestingly, the behavior of EST is contrasting: rejection ratios are high for certain models but almost zero for others, calling for a more detailed analysis, reported below. A case-by-case discussion for some selected examples is reported in the figures listed in Table 4. Our major findings are as follows:
SE-GNNs can output degenerate explanations: We provide examples of naturally occurring degenerate explanations in Fig. 12, Fig. 13, and Fig. 15, where SE-GNNs highlight green and violet nodes for RBGV, and background pixels for MNISTsp, respectively. Similar examples are also found for DIR on SST2P, where explanations highlight punctuation and stop words (Fig. 19), and for GSAT and SMGNN on MUTAG, where explanations emphasize individual weakly class-discriminatt atoms, rather than meaningful functional groups (Fig. 16, Fig. 17). In all cases, SE-GNNNs retain high predictive performance, and EST rejects a substantial fraction of explanations (2 50%)
ii) SE-GNNs can also output non-degenerate explanations: SE-GNNs do not always fail, and the low rejection ratios ( 2%) of GSAT on MNISTsp and SST2P suggest the model indeed outputs sufficient explanations. In fact, GSAT correctly extracts the digit-subgraph in MNISTsp, as indicated by the high AUCROC (cf. Fig. 14). In SST2P, however, it simply outputs the entire graph as explanation, see Fig. 18. Furthermore, on SST2P, SMGNN consistently highlights emotion- laden words and achieves around zero rejection ratios (see Fig. 20). Note that these results do not contradict Theorem 1, it provides existential conditions under which SE-GNNs can extract degenerate
8

---

Published as a conference paper at ICLR 2026
unfaithful explanations. In practice, stochastic optimization still steer the model to select other, non-degenerate explanations. Notwithstanding, this behavior remains beyond the practitioner's control, motivating further investigation into more robust SE-GNNs in future work.
iii) Faithfulness metries can fail in the wild: Fid- and RFid- achieve high rejection ratios in RBGV, but exhibit substantial seed-to-seed variability, reducing their reliabiliity. For instance, the examples reported in Fig. 12 and Fig. 13 highlight severe failure cases where these metrics mark most of the explanations composed of green and violet nodes as faithful. Similarly, Fig. 15 and Fig. 19 show that Fid- and RFid- can fail to reject explanations highlighting background pixels or punctuation for MNISTsp and SST SST2P, respectively. In contrast, EST achieves more consistent results, and it proved helpful in spotting explanations containing only irrelevant information.
In conclusion, the answer RQ3 positive: naturally trained SE-GNNs can output degenerate explanations, and popular faithfulness metrics can fail to mark them as such. Conversely, EST proved effective in distinguishing explanations containing or omitting key relevant features.
7 RELATED WORK
Popular faithfulness metrics (see Section 2 and Table for taxonomy) are typically evaluated by their correlation with i) human-defined ground-truth explanations or ti) rankings from progressively randomized explanations (Fang et al., 2023; Christiansen et al., 2023; Zheng al., 2023; 2025), but are rarely tested to flag known-unfaithful explanations as such. To address this, in Section 5.1 we in- troduce controlled benchmark where SE-GNNs are trained to output known- unfwnnnffittful explanations, and metrics are assessed by the fraction of explanations they correctly reject.
Prior work has shown that explanations can be manipulated in ways that evade detection (Dombrowski et al., 2019; Heo et al., 2019; Slack et al., 2020; 2021), with most studies focusing on post-hoc methods for tabular or image data. Furthermore, similar failure cases to the ones presented in Section can be found in rationalization methods for text (Yu et al., 2019), Neuro-Symbole (Marconato et al., 2023), and Concept Bottleneck Models (Bortolotti et al., 2025). Tai et al. (2025) has highlighted that when not regularized for sparsity, SE-GNNs extract redundant and potentially unfaithful explanations. This work is complementary to ours, in that we show that when SE-GNNs strongly regularized for sparsity, their explanations can also be unfaithful. We provide an extended discussion on some of this related work in Appendix C due to space constraints.
architectures
CONCLUSION
We outlined a critical failure case of SE-GNNs whereby they output explanations completely un- faithful to their actual inner workings. We provided a sufficient condition under which several SE-GNNs achieve optimal true risk and demonstrated that this condition met by explanations with class discrimiiiim power, which the model could not have used to achieve high accuracy (Section 3). We then showed that a malicious attacker can exploit this fallacy to deliberately conceal the features the model relies (Section 4), potentially hiding the use of protected attributes. We also observed that these degenerate explanations can emerge naturally (Section 6), underscoring the need for reliable auditing of explanations. Motivated by this, we proposed benchmark for faithfulness where faithfulness metrics are tested based on how many known-unfaithful explanations they reject, and showed that popular metrics perform poorly (Section 5.1). Finally, to address this shortcoming, we introduced a new metric that is shown to be more effective (Section 5.2).
Limitations. To highlight the counterintuitive aspect of our analysis, Theorem I is provided for a restricted but representative setting: explanations composed solely of nodes from an anchor set, which the model cannot use in isolation to achieve high accuracy. Nonetheless, shows that SE- GNNs can output explanations that do not faithfully represent what the model is actually using for inferring predictions, opening the door to several unfaithful behaviors beyond explanations composed of anchor sets. To improve on this, we provide in Appendix B.2 an extended analysis where we generalize the notion of anchor set to the case of subgraphs, showing how popular SE-GNNs can still prefer uncorrelated subgraphs over other, more informative explanations. In both analysis, assume the explanation extractor to be hard: This is a natural and commonly found desideratum for extracting explanations (Yu et al., 2020; Azzolin et al., 2025b), it represents an extractor maximally

---

Published as a conference paper at ICLR 2026
confident of what is relevant and what is irrelevant; This desideratum is already included in the design of practical SE-GNNs, which employ TopK masking (Wu et al., 2022; Deng & Shen, 2024), Gumbel-softmax trick (Miao et al., 2022a;b), entropy regularization (Lin et al., 2020; Azzolin et al., 2025b), to push the relevance scores to extremal values. While requiring access to the SE-GNN's training process is strong assumption for attack in Section 4, it naturally aligns with several practical Machine Learning-as-a-Serve model. Furthermore, despite EST effectively detecting unfaithful explanations omitting key relevant features, it cannot identify unfaithful behaviors arising from redundancy, i.e., explanations containing both truly relevant elements and irrelevant ones. Finally, although our focus is on graph classification, our findings carry over directly to node classification. For example, consider variant of RBGV in which each node must be classified based on whether has more or blue neighbors; In this case, SE-GNNs can still encode the overall count of colored neighbors within green and violet nodes, similarly to Example
scenarios, where the service provider has full control of the
ACKNOWLEDGEMENT
Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not 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 re- sponsible for them. Grant Agreement no. 101 701727363 TANGO and Grant Agreement no. 101 120237 -ELIAS. SM acknowledges the support of FWF and ANR project NanOX-ML (6728).
ETHICS STATEMENT
All authors have read and approved the ICLR Code of Ethics. As for societal consequences, the aim of this work is to shed light potential misuse of weerrretable-bydesiieee neural models, warning users from blindly trusting explanations, and providing a more reliable tool to audit explanations. can therefore contribute to the development of more trustworthy models for graph-based data and more reliable certifications of explanation validity.
REPRODUCIBILIT STATEMENT
The proofs of our theoretical results in Section 3 are provided in Appendix B. Details about the experiments, along with details about datasets and metric implementation, are available in Appendix D. Our code is available at https: /ttp://gtttttt thub. wwtpso//tttssooooooooooe http://eeeeeeoolnnnn//nnneedegee wtwgi//gggnnnnnnnneeeeeee
REFERENCES
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
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 on Graphs Conference, pp. 44-1. PMLR, 2022.
Burouj Armgaan, Manthan Dalmia. Sourav Medya, and Sayan Ranu. Graphtrail: Translating GNN predictions into human- -nterpritereee logical rules. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: / www.reveeevveooo www.ee...... forum? id= EifEzlMze 6dRZ.
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini. Global explainabil- ity of gnns via logic combination of learned concepts. In The Eleventh International Conference on Learning Representations, 2022.
Steve Azzolin, Antonio Longa, Stefano Teso, and Andrea Passerini. Reconsidering faithfulness in regular, self-explainable and domain invariant GNNs. In The Thirteenth International Confer- ence on Learning Representations, 2025a. URL https:///// /ttp:///ppeeeeeee///mm/ net forum?ii id k OxNNsrppy.
10

---

Published as a conference paper at ICLR 2026
Steve Azzolin, Sagar Malhotra, Andrea Passerini, and Stefano Teso. Beyond topological self- explainable gnns: A formal explainability perspective. In Forty-second International Conference on Machine Learning. 2025b.
Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. A gentle introduction to deep learning for graphs. Neural Networks, 2020.
Albert-Láázıó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In ICLR, 2020.
Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Matthias Althoff, and Guy Katz. Explaining. fast and slow: Abstraction and refinement of provable explanations. In Forty-second International Conference on Machine Learning, 2025a. URL https: nOfSWmPYLS.
/ wwwp//ppppeeee.eeooe/pe/e net forum?? ii
Shahaf Bassan, Ron Eliav, and Shlomit Gur. Explain yourself, briefly! self-explaining neural networks with concise sufficient reasons. In The Thirteenth International Conference on Learning Representations, 2025b. URL /otppr//ee/eerreeee.e.. net/ wttp:/.neteeeeemm//////mmmm -idiidd-nsssss fff..
Maya Bechler-Speicher, Amir Globerson, and Ran Gilad-Bachrach. The intelligible and effective graph neural additive network. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024a. URL https::tp..............tt /tttsp:s///peeeevieeeeee open net/ forum? d=sxY1 ScUTwA.
Maya Bechler-Speicher, Amir Globerson, and Ran Gilad-Bachrach. Tree-g: Decision trees contesting graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11032-11042, 2024b.
Maya Bechler-Speicher, Ben Finkelshtein, Fabrizio Frasca, Luis Müller, Jan Tönshoff, Antoine Siraudin, Viktor Zaverkin, Michael M. Bronstein, Mathias Niepert, Bryan Perozzi, Mikhail Galkin, and Christopher Morris. Position: Graph learning will lose relevance due to poor benchmarks. In Forty-second International Conference on Machine Learning Position Paper Track, 2025. URL https: http:/://///peeeeee.e... net forum? (atpummidddDDDooo didddDpp22PPhhtt
Robi Bhattacharjee and Ulrike von Luxburg. Auditing local explanations is hard. arXiv preprint arXiv:2407.13281, 2024.
Samuele Bortolotti, Emanuele Marconato, Tommaso Carraro, Paolo Morettin, Emile van Krieken, Antonio Vergari, Stefano Teso, and Andrea Passerini. A neuro-symbolic benchmark suite for concept quality and reasoning shortcuts. Advances in neural information processing systems, 37: 115861-115905, 2024.
Samuele Bortolotti, Emanuele Marconato, Paolo Morettin, Andrea Passerini, and Stefano Teso. Shortcuts and identifiability in concept-based models from neuro-symbolic lens. arXiv preprint arXiv:2502.11245, 2025.
Shiyu Chang, Yang Zhang, Mo Yu, and Tommi Jaakkola. A game theoretic approach to class-wise selective rationalization. Advances neural information processing systems, 32, 2019.
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-22148. 2022.
Yongqiang Chen, Yatao Bian, Bo Han, and James Cheng. How interpretable are interpretable graph neural networks? In Forty-first International Conference on Machine Learning, 2024.
Mare Christiansen, Lea Villadsen, Zhiqiang Zhong, Stefano Teso, and Davide Mottin. How faithful self-explainable gnns? arXiv preprint arXiv:2308. /5096, 2023.

---

Published as a conference paper at ICLR 2026
Enyan Dai and Suhang Wang. Towards self-explainable graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 302-311, 2021.
Sanjoy Dasgupta, Nave Frost, and Michal Moshkovitz. Framework for evaluating faithfulness of local explanations. In International Conference on Machine Learning, pp. 4794-4815. PMLR, 2022.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 12y776-7977, 1991.
Jiale Deng and Yanyan Shen. Self Self-interpretable graph learning with sufficient and necessary ex- planations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11749-11756, 2024.
Ann-Katinn Kathrin Dombrowski, Maximillian Alber, Christopher Anders, Marcel Ackermann, Klaus- Robert Müller, and Pan Kessel. Explanations can be manipulated and geometry is to blame. Advances in Neural Information Processing Systems, 32: 12:1399-11360, 2019.
Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. When comparing to ground truth is wrong: On evaluating gnn explanation methods. In KDD, 2021.
Junfeng Fang, Wei Liu, Yuan Gao, Zemin Liu, An Zhang, Xiang Wang, and Xiangnan He. Evalu- ating post-hoc explanations for graph neural networks via robustness analysis. In Thirty-eevnnth Conference on Neural Information Processing Systems, 2023. URL https: htap::://opeeee /ttp://voee//eeee/// net/ Eorum? i id=eD5 4mPhAg.
Farzan Farnia and Asuman Ozdaglar. Do GANs always have Nash equilibria? Proceedings of Machine Learning Research. PMLR, 2020.
Francesco Ferrini, Antonio Longa, Andrea Passerini, and Manfred Jaeger. A self-explainable heterogeneous gnn for relational deep learning. arXiv preprint arXiv:2412.0052), 2024.
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 WeRLatttts///ppreeeeeeee //oppppeeeveeeeeee www.ee/ooornininnnaabbbbaaeeeeee
:
Michele Guerra, Simone Scardapane, and Filippo Maria Bianchi, Interpreting temporal graph neural networks with koopman theory. 2024. URL https: /tte::///rrxii www.aaxiivvvi....a.a org/ abs/2410. 13469.
Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: A graph diist---itt benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Truck, 2022. URL https:: http:///ppeeeeeeeeeeeeeeeee
/ net/ forum? diggmmig-d-sssgeeeee
Peter Hase, Harry Xie, and Mohit Bansal. The out-of-distribution problem in explainability and search methods for feature importance explanations. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, 2021. ISBN 97817 13845393.
Juyeon Heo, Sunghwan Joo, and Taesup Moon. Fooling neural network interpretations via adversarial model manipulation. Advances in Neural Information Processing Systems, 32:2925-200 2936,, 2019,
Jennifer Hsia, Danish Pruthi, Aarti Singh, and Zachary C Lipton. Goodhart's 's law applies to nip's explanation benchmarks. In Findings of the Association for Computational Linguisties: EACL. 2024, pp. 1322-1335, 2024.
Shuaibo Hu and Kui Yu. Learning robust rationales for model explainability: A guidance-based approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 18243-18251, 2024.
Xinyue Hu, Zenan Sun, Yi Nian, Yichen Wang, Yifang Dang, Fang Li, Jingna Feng, Evan Yu, Cui Tao, et al. Self-explainable graph neural network for alzheimer disease and related dementias risk prediction: Algorithm development and validation study. JMIR aging, 711):554748 2024.
12

---

Published as a conference paper at ICLR 2026
Sergey loffe. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03166 2015.
Neil Jethani, Mukund Sudarshan, Yindalon Aphinyanaphongs, and Rajesh Ranganath. Have we learned to explain?: How interpretability methods can learn to encode predictions in their inter- pretations. In International Conference on Artificial Intelligence and Statistics, pp. 1459-1467.
PMLR, 2021.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks, Advances in neural information processing systems, 32, 2019.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, pp. 2278-2324, 1998.
Jiate Li, Meng Pang, Yun Dong, Jinyuan Jia, and Binghui Wang. Graph neural network explanations are fragile. In Proceedings of the 41st International Conference on Machine Learning, ICMI'24. org, 2024a.
Jiate Li, Meng Pang. Yun Dong, Jinyuan Jia, and Binghui Wang. Provably robust explainable graph neural networks against graph perturbation attacks. In The Thirleenth International Conference on Learning Representations, 2025.
Zhong Li, Simon Geisler, Yuhang Wang, Stephan Günnemann, and Matthijs van Leeuwen. Ex- plainable graph neural networks under fire, 2024b. URL https: http:/:/wwwwwwwaaateeeeeeeo abs 06417.
Chris Lin, Gerald J Sun, Krishma C Bulusu, Jonathan R Dry, and Marylens Hernandez. Graph neural networks including sparse interpretability. arXiv preprint MxXix:0077000111 2020.
Wei Liu, Haozhao Wang, Jun Wang, Ruixuan Li, Chao Yue, and YuanKai Zhang. Fr: Folded rationalization with a unified encoder. Advances in Neural Information Processing Systems, 35: 6954 6966, 2022.
Wei Liu, Zhiying Deng, Zhongyu Niu, Jun Wang. Haozhao Wang, YuanKai Zhang, and Ruixuan Li. Is the MMI criterion necessary for interpretability?? degenerating non-causal features to plain noise for self-rationalizzaion. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024a.
Wei Liu, Haozhao Wang. Jun Wang, Zhiying Deng, Yuankai Zhang, Cheng Wang, and Ruixuan Li. Enhancing the rationalc-input alignment for self-explaining rationalization. In 2024 IEEE 40th International Conference Data Engineering (ICDE), pp. 2218-2230 IEEE, 2024b.
Wei Liu, Zhongyu Niu, Lang Gao, Zhiying Deng, Jun Wang. Haozhao Wang, and Ruixuan Li. Adversarial cooperative rationalization: The risk of spurious correlations in even clean datasets, 2025. URL https:tt///...........tt / aaaiiiiiivv..////i http://wwwww..oaaaa/////aaaaaa// 2250..02188.
Antonio Longa, Steve Azzolin, Gabriele Santin, Giulia Cencetti, Pietro Liò, Bruno Lepri, and Andrea Passerini. Explaining the explainers in graph neural networks: a comparative study. ACM Computing Surveys, 2024.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang Parameterized explainer for graph neural network. Advances in neural information processing systems, 9911166661661.1,.-111111 2020.
Bin Ma, Yuyuan Feng, Minhua Lin, and Enyan Dai. How explanations leak the decision logic: Stealing graph neural networks via explanation alignment, 2025. URL http::/ h/tp::/.xxx/v/////// abs/2506. 03087.
Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts. Advances in Neural Information Processing Systems, 36:72507-72539, 2023.
Jono Marques-Sile Silva and Alexey Ignatiev. Delivering trustworthy ai through formal xai. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 12342-12350, 2022.
13

---

Published as a conference paper at ICLR 2026
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International conference on machine learning. pp. 3481-3490. PMLR, 2018.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference Machine Learning, pp. 15524-15543, PMLR, 2022a.
Siqi Miao, Yunan Luo, Mia Liu, and Pan Li. Interpretable geometric deep learning via learnable randomness injection. In The Eleventh International Conference Learning Representations, 2022b.
Peter Müller, Lukas Faber, Karolis Martinkus, and Roger Wattenhofer. Graphchef: Learning the recipe of your dataset. In JCML 3rd Workshop on Interpretable Machine Learning in Healthcare (IMLH) 2023. URL https: // /ttp////pppeeeeeeeeeeeee/eeeeeee net 21d-:211d222P.......
Alexander Pluska, Pascal Welke, Thomas Gürtner, and Sagar Malhotra. Logical distillation of graph neural networks. In ICML 2024 Workshop Mechanistic Interpretability, 2024.
Aahlad Manas Puli, Nhi Nguyen, and Rajesh Ranganath. Explanations that reveal all through the definition of encoding. In The ehirty- Annual Conference on Neural Information Processing Systems, 2024. URL https: / opwprevieweeeeeeeee/eeeee nett forum?id 6x00Exg.
Alessio Ragno, Biagio La Rosa, and Roberto Capobianco. Prototype-based interpretable graph neural networks. IEEE Transactions on Artificial Intelligence, 2022.
Agapi Rissaki, Ilias Fountalis, Wolfgang Gatterbauer, and Benny Kimelfeld. Database views as explanations for relational deep learning, 2025. URL http:////aaai.../aa/aaaa////aa// 09482.
Giuseppe Serra and Mathias Niepert. Learning to explain graph neural networks. arXiv preprint N.4Y::2209.1442., 2022.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 180-186, 2020.
Dylan Slack, Anna Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explanations can be manipulated. Advances in neural information processing systems, 34:62-75, 2021.
Indro Spinelli, Michele Guerra, Filippo Maria Bianchi, Simone Scardapane, et al. Combining stochastic explainers and subgraph neural networks can increase expressivity and interpretability. In ESANN 2023-Proceedingg European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. 2023.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal attention for interpretable and generalizable graph classification. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '22, pp. 1696-1705, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781 4503933388 doi: 10.1145/3534678.3588 355333336. URL https: /ooi wwt//0..//...oooo.ooooo 1145/ 3534678 3 3539366.
Wenxin Tai, Ting Zhong, Goce Trajcevski, and Fan Zhou. Redundancy undermines the trustworthiness of self-interpreetbble GNNs. In Foroy- International Conference Machine Learning, 2025.
net URL /attps://openreviiee http://e///foorraee/ee forum? id=hF Vp3NEEY....
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, pp. 1018-102) New York, NY, USA, 2022, Association for Computing Machinery. ISBN 9781450399965. 10.1 00.1145/3485447.311115 URL hwt.h:tt////eeet org/ 0. 141114/44855 44/34484447 3511948.
doi:
Stefano Teso, Öznur Alkan, Wolfang Stammer, and Elizabeth Daly. Leveraging explanations in interactive machine learning: An overview. Frontiers in Artificial Intelligence, 2023.
14

---

Published as a conference paper at ICLR 2026
Anna Varbella, Kenza Amara, Blazhe Gjorgiev, Mennatallah El-Assady, and Giovanni Sansavini. Powergraph: A power grid benchmark dataset for graph neural networks. Advances in Neural Information Processing Systems, 37:1 11F:110784-1100000 2024.
Felix Wong, Erica J Zheng, Jacqueline A Valeri, Nina M Donghia, Melis N Anahtar, Satotaka Omori,
Alicia Li, Andres Cubillos-Ruil Aarti Krishnan, Wengong Jin, et al. Discovery of structural class of antibiotics with explainable deep learning. Nature, 626(7997) 2024.
Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant 2022.
rationales for graph neural networks. arXiv preprint
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitmik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
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 Puttern Recognition, pp. 19396-19405, 2022.
Mo Yu, Shiyu Chang, Yang Zhang, and Tommi Jaakkola. Rethinking cooperative rationalization: Introspective extraction and complement control. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-IJCNLP), pp. 4094-4103, 2019.
Mo Yu, Yang Zhang, Shiyu Chang, and Tommi Jaakkola. Understanding interlocking dynamics of cooperative rationalization. Advances in Neural Information Processing Systems, 34: 1282222--8 2021.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International conference on machine learning, pp. 12241- 12252. PMLR, 2021.
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.
Linan Yue, Qi Liu, Yichao Du, Li Wang, Weibo Gao, and Yanqing An. Towards faithful explana- tions: Boosting rationalization with shortcuts discovery. In The Twelfth International Confer- ence on Learning Representations, 2024. URL https:/ pestts:://ppereeeee /opp/reveeeeeeeeee net. / forum?id= uGt.k22phu.
Andrea Zerio, Maya Rechler-Speicher Maor Huri, Marie Vibeke Vestergaard, Ran Gilad Baad-Bachrach, Tine Jess, Samir Bhatt, and Aleksejs Sazonovs. Interpretable graph learning over sets of temporally- sparse data. arXiv preprini arXiv:2505. 2025.
Wenbo Zhang, Tong Wu, Yunlong Wang, Yong Cai, and Hengrui Cai. Towards trustworthy expla- nation: On causal rationalization. In International Conference on Machine Learning. PMLR, 2023.
Zaixi Zhang, Qi Liu, Hao Wang. Chengqiang Lu, and Checkong Lee. Protgnn: Towards self- explaining graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9127-9135, 2022.
Xu Zheng, Farhad Shirani, Tianchun Wang, Wei Cheng, Zhuomin Chen, Haifeng Chen, Hua Wei, and Dongsheng Luo. Towards robust fidelity for evaluating explainability of graph neural networks, 2023.
Xu Zheng, Farhad Shirani, Zhuomin Chen, Chaohao Lin, Wei Cheng, Wenbo Guo, and Dongsheng Luo. F-fidelity: A robust framework for faithfulness evaluation of explainable AI. In The Thirteenth International Conference on Learning Representations, 2025. URL https: //pperrevee.. net/ forum? i 4BN50DV..
15

---

Published as a conference paper at ICLR 2026
A USE OF LLMS
LLMs were used to polish the writing, to rephrase sentences, and to debug the code. Our manuscript and our code first human-generated, and then possibly enhanced by LLMs.
B PROOFS
B.I PROOF OF THEOREM 1.
Theorem 1. Let Dexy be a data distribution with deterministic ground truth labeling function : + Y, e be a hard explanation extractor, and 2 =Zzyyyy be an anchor set. Then, there exists an explanation extractor e(G) := 2d(G) and a classifier ((Zy) == such that the SE-GNN implemented by GSAT, LRI, CAL, GMT-1in or SMGNN achieves optimal true-risk.
Proof. Recall that SE-GNN g is composed of an explanation extractor and classifier g. Also, recall that 9 is the set of graphs and y the set of labels with deterministic ground truth labeling function Ø G V/ and that Z is anchor set, i.e., set of single-node subgraphs 2 {2 hey such that 2; S G. for all instances E G and for all 2; E Z. Then, we show that selecting as the explanation extractor e(G) == Go(G) and the classifier g(zy) := y achieves optimal true-risk for GSAT, LRT, CAL, GMT 1 n, and SMGNN. At a high level, this shows that whenever e can encode the predicted label inside single node, then the classifier g implementing simple mapping from these nodes to labels achieves optimal true risk for several SE-GNNs, even when the selected nodes are uncorrelated with the ground truth task.
We restate below two assumptions relevant to our proof:
Assumption 1. is a hard explanation extractor, i.e., can only outpul relevance scores saturated in {0, for SMGNN and CAL, and {r, 1} for GSAT, LRI. and GMT-lin.
Assumption 2. The explanation R cannot be empty, i.e., |R] > In other words, and and following Assumption 1, 3u E V Pa =
Note that in Assumption 1 is the parameter controlling the degree of stochasticity in the relevance scores of each node, and it therefore acts as an uninformative baseline value. For example, a value of Pu 1 indicates no stochasticity for node u, i.c., maximally relevant, while Pu r indicates maximum stochasticity, i.c., low relevance (Miao et al., 2022a).
Without any loss of generality, we will consider binary classification setting, i.e., | two distinct nodes, 20, 21 belonging to the anchor set, that is 20, E Z. We proceed to show that, for each of the following SE-GNN, an explanation extractor selecting 2y for (GG) and 21 for ((G) 1, paired with a suitable classifier will yield optimal risk. We will analyze each SE-GNN separately, as follows.
and
GSAT & LRI (Miao et al., 2022a;b): The learning objective of both GSAT and LRI is:
Ca + A Σ Pu log( Pu (1 Pw. log( 1 Pu NEV
(6)
1-r" r
where V is the set of nodes for input graph G. Pv. is the explanation relevance score for node r E [0, 1] is the hyperparameter controlling the uninformative prior below which node is considered to be non-relevant (Miao et al., 2022a), and \ is an hyperparameter controlling the relative strength of the regularizer over the cross entropy loss Lag.
We now provide suitable pair of explanation extractor and classifier achieving optimal value for Eq. (6). For exposition convenience, instead of considering e as mapping from graph to subgraphs as described in Section we will unpack it function from graph to individual node relevance scores, as follows:
uf 20 (G) =
Pzo > Pz1 if pz, > Pzo otherwise
Pa :===e(G),
fu= (G)) =1
9(R) =
otherwise
0.5
16

---

Published as a conference paper at ICLR 2026
Since g classifies every sample correctly with maximum confidence, L(g. e, G. y) equals zero. Also, since each Pu equal to r yields zero loss and e highlights only a single node between 2g and 21 per graph, the second term in Eq. (6) boils down to -A1 log(r). By Assumption and Assumption 2, is not possible to find an assignment of explanation scores with more terms equal to r than the explanation provided by Eq. (7), hence -A1 log(r) is the minimum risk attainable.
As a remark, note that the classifier in Eq. (7) can indeed be learned by a linear layer with sigmoid output, receiving as input an embedding of the form h [Ps, {2) E R} , .Pao 1xz E RH], with weights w = [ax, -a] and b = O, for a sufficiently large o. Note that h can be recovered by classifier implementing a GNN with weighted message passing and sum global readout by simply mapping 2g and 21 to two different one-hot encodings, and multiplying this value by the weight given by the relevance scores. Hence, the classifier expressed Eq. (7) is easily realizable by practical GNNs.
GMT-lin (Chen et al., 2024) We observe that GMT-lin differs from CSAT just in the number of weighted message passing layers (see Appendix E.1 in Chen et al. (2024)). The proof above applies since the underlying training objective remains the same.
SMGNN (Azzolin et al., 2025b) The parsity-based learning objective of SMGNN is:
A
A2
La e, G.y) +
Σ
Pa
Σ Pu log(pw) + (1 Pw) log(1 - Po)
(8)
V
IV
NEV
NEV
where Lalf, V, \1, X2, and Pu are specular to those for GSAT and LRI.
We now provide suitable pair of explanation extractor and classifier achieving an optimal value for Eq. (8).
{
if =o (GG) 0 if 21 (GG) = g(R) otherwise
O
if 20 E E R
Pu p=
if E RA 20 $ R (9)
0.5 otherwise
Then, by plugging Eq. (9) inside the training objective, we get that Car(g, e,
G. C,e.e.GG. model achieves correct highly-confiden predictions, the middle term becomes V as only one between 20 and 21 gets a score above zero, and the last term becomes zero as relevance scores are binary in (0, 1). Hence, Eq. (8) boils down A1 \ /V By Assumption 1, the only possible smaller assignment of explanation scores would be giving zero score to every node, which, however, violates Assumption Hence, the explanation given by Eq. (9) is the smallest possible, and therefore \ is the smallest risk achievable.
0 since the
As remark, note that the classifier in Eq. (9) can indeed be learned by a linear layer with sigmoid output, receiving as input an embedding of the form h = [1fzo R] 1 21 E R)] similar to the one-hot encoding defined above for GSAT, with weights w [ a and b O, for sufficiently large a. Hence, the classifier expressed in Eq. (9) is easily realizable by practical GNNs.
CAL (Sui al., 2022): CAL aims at learning an explanation = e(G) containing the causal features for the prediction, while delegating spurious features to the complement C = G R, by applying causal interventions.
For doing that, it uses a shared explanation extractor that predicts node and edge explanation relevance scores, which can be stacked into a node-wise attention matrix Mx and an edge-wise attention matrix MA. The original graph G = (A, X) is therefore separated into R = (Ao MA X @ Mx) and C = (A 1 MA.X 1 Mx). Then, CAL instantiates three separate classifiers: 9R to predict the label from the causal explanation; gc to predict the label from the spurious complement; and to predict the label from the implicit intervened graph defined below. Note that, in this case, is classifier mapping from the global graph readout to labels, i.e., g Rdd + y. with d the size of the embedding. Let ly be the graph embedding computed by gR before the classification head, and he be the same graph embedding computed by go- Then, CAL generates implicit intervened graph by simulating causal interventions. In practice, this is achieved by summing the embedding of ha, for graph G, with the embedding he, of graph G, chosen at random, and by predicting the original label of sample G; (refer to Section 3.4.3 of Sui et al. (2022) for detailed description). The overall objective amounts to:
Las (gn; e, G.,ye) (U41, D'I,s.ccCC.. X hR, + hhe, Vi)
(10)
17

---

Published as a conference paper at ICLR 2026
where Linterv is the standard cross entropy loss defined for implicit intervened graphs with h the, the imput to 9. A1, A2 are hyperparameters controlling the relative strength of the regularizers, and Ut1, [}]]] is discrete uniform distribution over class labels.
Consider now the same construction as for SMGNN:
if u 2o A (GG) 0
if 20 E RA 21 R
Pu. : :G)
uf 21 A (GG) = IR
if 21 E RA 20 E R (11)
otherwise
0.5 otherwise
Also, since 9c is trained to output maximally uncertain predictions for any imput (second term in Eq. (10)), a possible trivial solution would be having he = Ö for any C, with an associated constant classifier outputting 1/| for each class, i... (C(C) := 1/|>// Note that any 9c trained with weight decay is encouraged to converge to this solution, as no term in Eq. (10) is pushing he to learn a meaningful representation. Together, these observations imply that both the first and second terms in Eq. (10) are zero. Furthermore, since we fixed ha Ô, then the last term in Eq. (10) boils down to:
Ae (g. b W/)
(12)
Therefore, the solution where the classification head equals that of gn implies that all three terms are zero.
Note that our examples are provided assuming the classification head of is a linear layer. Nonetheless, our examples generalize to the case where multi-layer perceptions are used, as commonly found in practical implementations of SE-GNNs.
Final remarks:
B.2 EXTENDED ANALYSIS OF THE ANCHOR SET
We provide generalization of the theoretical analysis Section to the case where the anchor set is defined in terms of subgraphs rather than single nodes, and where each of these subgraphs is not required to appear in all graphs. With this new setting, we will show that the risk attained by several popular SE-GNNs when selecting uninformative subgraphs can be lower than the risk attained by selecting other, more informative explanations R", To keep the discussion intuitive - and in line with previous work studying SE-GNNs from causal lens (Miao et al., 2022a; Chen al., 2022; Azzolin et al., 2025a)- - we will discuss the specific case where Ry is the ground truth explanation for class y.* Nonetheless, we will discuss, our insights will equally apply to any other notion of explanation. Let us now extend the anchor set definition provided in Section to the case of subgraphs.
lens
Definition 2 (Subgraph anchor set). Let Dexy be the data distribution, and A [G. a set of generic subgraphs G that can appear in any graph G E G, with m 2 { The partition of A into Z' ((G)) "hy "eye with Ey my = m called subgraph anchor set if:
1. (Per-label coverage) For every (G, y) in the support of Dexy there exists at least one subgraph G. E G.
2. (Disjointness of partitions) The partitions are pairwise disjoint: {G)) n 16 J = Ø for all y + y'.
Note that A constitutes an arbitrary subset of possible subgraphs appearing in the dataset, with no additional assumptions on the structure of the graphs. We will use A to represent the possible subgraph explanations that are provided by a generic e learned on Dęxy- Definition allows for A containing subgraphs G; carrying no information about class labels, meaning they are neither ground truth nor spurious correlation. In fact, anchor sets (as originally defined in Section 3) are a specific case of subgraph anchor sets, where appearing in all graphs.
[) and where each G, is single-node subgraph
Importantly, Definition 2 generalizes the original definition of node-wise anchor set (c.f. Section 3) in the following ways: First, considers subgraphs instead of single nodes. Second, relaxes the
Although Rú may depend on the specific graph instance, we consider a fixed subgraph for the ease of the argument. This remains general enough to capture most SF-GNNN use-cases commonly found in the literature, like motif-hased tasks (Miao al., 2022a; Chen et al., 2022; Azzolin al., 2025a).
18

---

Published as a conference paper at ICLR 2026
condition that anchor nodes must be present in all graphs to the case where different subgraphs appear in different graphs (see Per-label coverage in Definition 2).
We now proceed to show that many popular SE-GNNs achieve lower risk by picking explanations from the subgraph anchor set rather than the ground truth Rg. Crucially, this holds even when A contains only subgraphs with dass-discriminattv power, showing how the degenerate explanations discussed in Section 3 can emerge also the presence of subgraph explanations.
Theorem 2. Let Daxy be data distribution with deterministic ground truth labeling function Φ G + y and ground truth explanation Ry be hard explanation extractor, and Z' [[G ( J be subgraph anchor set. If [R 2 max, | for all labels y, then there exists a SE-GNN g such that the true risk of GSAT, LRI, CAL, GMT-IIE and SMGNN will be lower or equal for
e(G) = argmin ( and
g(G,) =
( EG
than
e* e'( = Ry
and
g g² y.
Proof. To keep the proof simple, will use the same setting of Theorem for a boolean classification task, and reuse some intermediate results.
GSAT, MMT--in, & LRI: Let consider the following pair of explanation extractor and classifier:
argmin G GREG
if (GG)
0
R {
R: e==
g(R)
1
if (
(13)
argmin CH|
if (G))
G|EG
0.5
otherwise
In the equation above, argmingçeG G means that will select the smallest subgraph i belonging to partition 0 that is present in the subgraph anchor set for the input sample G. The classifier instead, is just left with inferring to which partition the explanation belongs. and with outputting the corresponding partition index. In addition, to preserve the semantics of Miao et al. (2022a) and in accordance with Assumption 1, we assume that each node in given a score of while the rest given a score of r.
Since g replicates the predictions of the ground truth labeling function hence it classifies every sample correctly with maximum confidence by construction L(g, v, in Eq. (6) equals zero. Also, since each node with score equal to r yields zero loss, and each node with score equal to yields loss value of a1 log(r)-1 (see proof of Theorem 1), the true risk is bounded above follows:
D(Gy [ (e( log(r) < E(G.y)~Doxo max A CC log(r)
(14)
By repeating the same analysis for the following ground truth explanation extractor e and ground truth classifier y²:
R-
R: e (G) Ry
(R)
R Ri
(15)
0.5
otherwise
we get that the true risk when selecting the ground truth explanation RG equals:
B(G.)) [Ar | log(r)-11
(16)
It follows that, whenever [Rt 2 max, | for all labels y, the true risk of Eq. (14) will be smaller or equal to that of Eq. (16).
SMGNN: The proof works similarly to above. Let us consider the following SE-GNN:
arggmin
G
if (G)
0
if R (G
GGEG argmin G.I if (G)) GlEG
:: = c(G)=
g(R)
if (G]
(17)
0.5 otherwise
19

---

Published as a conference paper at ICLR 2026
C(g. e, G. y) in Eq. (8) is again zero for the reasons above, and since Eq. (8) penalizes the loss by factor of \1/[V] for each node in R, it reduces to A >zle(G))/ (see proof of Theorem 1). The true risk is then upper bounded as follows:
le(G) M
G
B(G.y)-Dox [A
(iG.y))-Dxx max
(18)
M
By repeating the same analysis for the same ground truth explanation extractor et and ground truth classifier 9" of Eq. (15), the true risk equals:
R
D(G [11
(19)
|V
It follows that, whenever | 2 max; |G for all labels y, the true risk of Eq. (18) will be smaller or equal to that of Eq. (19).
CAL: Exactly as in the original proof of Theorem 1, we can set he 0 and train gn and g predict the right label from the explanation only, achieving zero classification and intervention loss in Eq. (10) for both choices of explanation extractor (e or e*). Moreover, We can choose gc to output the uniform distribution on every input, making the KL term zero as well as in the proof of Theorem 1. Hence, both SE-GNNs attain the same value of the CAL objective, independently of RR]
As remark, note that Theorem 2 does not depend on the specific form of Ry. but relies only on its cardinality | Therefore, the same result applies to any other notion of explanation R. beyond ground truth explanations, like explanations highlighting spurious correlation (Wu et al., 2022), invariant subgraphs (Chen et al., 2022), or minimal aubel-preservngg subgraphs (Azzolin et al., 2025b). That is, SE-GNNs in Theorem 2 can prefer to highlight smaller uninformative explanations over other reasonable notions of explanations.
C EXTENDED RELATED WORK
Reasoning shortcuts. Concept bottleneck models (CBMs) introduce an intermediate layer of human- interpretable concepts between inputs and predictions, enabling users inspect and intervene on model's 's reasoning process. While this paradigm promises greater transparency and controllability. recent work has raised concerns about its reliability. In particular, Bortolotti al. (2024) show that CBMs are vulnerable to reasoning shoricuts: instead of leveraging the intended causal relationships between concepts and outcomes, models may create unwanted dependencies and semantic associ- ations in the concept space, thereby undermining the very interpretability of CBMs. While CBMs are expected to learn human-aligned concepts, SE-GNNs are only designed to declare which input patterns/features they are relying on, regardless of whether it is the intended pattern mere spurious correlation. Therefore, reasoning shortcuts can be seen as an issue poor alignment between humans and machines, whereas the issue highlighted in Section 3 is poor alignment between the predictive behavior of SE-GNNs and their explanations. In fact, the only fully reliable mitigation strategy outlined in Marconato al. (2023) involves dense human supervision concepts setting that does not apply to SE-GNNs, which are not defined over buman-specifen concepts.
Degenerate explanations. Jethani et al. (2021) was among the first works highlight that explanation-based architectures can learn to encode predictions in their explanations and to propose amelioration. Nonetheless, Hsia al. (2024) showed that the solution proposed by Jethani al. (2021) can be easily hijacked into considering degenerate explanations as legitimate. Then, Puli al. (2024) proposes an extension to Jethani et (2021), encompassing two surrogate models; one to approximate the true label posterior (as in Jethani et al. (2021)), and the other to estimate the Mutual Information between the selected mask and the target label. Their solution, however, does not readily apply to the graph setting. In fact, they propose to learn classifier & that respects the true data distribution by training & over any possible randomly generated explanation Rt where R is sampled IID for each input feature from a Bernoulli distribution. This is impractical for graph task like counting (cf. RBCV), as randomly removing input nodes can change the ground truth label of the graph, resulting in contradictory supervisory signal.
Other approaches to contrast degenerate explanations collect annotated explanations to teach the model to rely less on spuriously correlated ones (Yue et al., 2024). Nonetheless, as we show in
20

---

Published as a conference paper at ICLR 2026
Appendix E.I, supervising the SE-GNNs' explanations may not be enough to ensure the faithfulness of explanations.
Rationalization methods for NLP. Rationalization methods aim at extracting rationale for model prediction together with the final explanation, sharing the same spirit as SE-GNNs. They's re mostly used for NLP tasks.
Yu et al. (2019) formalized the problem of degeneracy as explanations encoding labels via trivial patterns. However, they did not provide formal analysis of which rationalization methods can learn such degenerate solutions, nor sound methodology for identifying when degenerate explanations appear in the wild. On the contrary, Theorem formally unpacks commonly found loss functions of popular SE-GNNs, showing how models are implicitly optimize for such cases. This result hold beyond models promoting conciseness via sparsity, which is instead the main focus of Yu et al. (2019). At high level, Yu et al. (2019) proposes to add complement predictor, trained adversarially to predict the correct label from information left out of the explanation. Thanks to the adversarial training, the explanation extractor is pushed to not leave any useful information in the complement, thus including all informative features in the explanation. A similar solution was also proposed by Liu et al. (2024a), where the complement predictor is shared with the final classifier. While this may effectively promote non-degenerate explanations, preliminary experiments on a SE-GNN implementing a similar type of mitigation have shown it may not be enough to guarantee non-degeneracy (see DIR in Section 6). Additionally, this mitigation promotes the explanation extractor to include potentially redundant and spuriously correlated information inside R, resulting in more complex explanations.
related solution was proposed by Chang et al. (2019), which adopts three different players for each output class trained in a zero-sum game output class-specific rationales. Nonetheless, this approach scales poorly with the number of classes, and the zero-sum game of the three players is notoriously hard to balance (Mescheder et al., 2018; Farnia & Ozdaglar. 2020).
Yu et al. (2021) investigates the problem of model interlocking, where the classifier overfits to little informative explanations early stages of training. and prevents the explanation extractor from finding more informative ones. This is, however, orthogonal to the degeneracy problem, as degenerate explanations can be optimal from a predictive accuracy perspective.
Liu et al. (2022) advocates that instead of relying on complex regularization components, employing a unified encoder for both the explanation extractor and the predictor enough to avoid degeneracy. Nonetheless, this can serve as a useful inductive bias, but it does not completely rule out the possibility of learning degenerate explanations, as shown in our experiments with GSAT of Section 6, which naturally employs shared extractor-classifier (Miao et al., 2022a).
Zhang et al. (2023) propose to optimize for causal non-spuriousness and efficiency during training, which is shown to yield less spuriously correlated explanations. However, this does not tackle degeneracy, as degeneracy is about the model outputting unfaithful explanations, and this issue is not caused by spurious correlations.
Hu & Yu (2024) proposes to employ a guidance rationalization module, trained with soft relevance scores instead of the binary scores employed by the core rationalization module. Then, the core rationalization module is trained to match the predictions and rationales of the guidance module. The idea is that if the guidance module learns non-degeee explanations thanks to its broader receptive field, then the final core rationalization module will also avoid degenerate explanations. Nonetheless, models trained with soft relevance scores can also fall into degeneracy, as we have shown in our work.
Liu et al. (2024b) proposes to use a standard black-box model as guidance. Then, the explanation extractor is trained to extract explanations for the black box's 's predictions and optimize the classifier, which receives such explanations as input only. This approach requires however to explain bloxk-box model in a post-hoc fashion similar to Luo et al. (2020). It thus deviates from our goal of devising an intrinsically ante-hoc self-explainable model.
Liu et al. (2025) proposes an adversarial training where the adversary tries to predict random class by exploiting any information the graph (thus not limited to the complement of the main explanation R). whereas the explanation extractor and the predictor are trained to make accurate predictions and to predict the adversarial explanation with maximum uncertainty. The proposed method is grounded on the assumption that ground truth rationales for a specific class y appear more
21

---

Published as a conference paper at ICLR 2026
often in samples of class y. While being reasonable for text-like input, this might not hold for graphs for RBCV you can construct an infinite number of negative graphs that contain any arbitrary number of red nodes.
In all those cases, to the best of our knowledge, robust framework to audit these explanation failures remains largely unexplored, and results highlight its highly challenging computational complexity (Bhattacharjee & von Luxburg, 2024). Furthermore, our experiments in Appendix E. I show that even when explanations are optimized to match human expectations thus avoiding degeneracy through supervision the model can still conceal its use of protected attributes, revealing a fundamental misalignment between the explanations and the model's actual decision process. This goes beyond degeneracy alone and towards the broader challenge of explanation model misalignment.
Self-explainable GNNs. In our work, we focused on Self-explainable GNNs (SE-GNNs) that have been introduced to overcome the intrinsic limits of post-hoe methods (Ying et al., 2019; Luo et al., 2020; Yuan al., 2021; Azzolin et al., 2022; Yuan al., 2022; Li et al., 2024b). Our focus is on SE-GNNs composed of an explanation extractor and a classifier, jointly trained. While being very general, alternative formulations of SE-GNNs exist, such as prototype-based models (Zhang et al., 2022; Ragno et al., 2022; Dai & Wang, 2021), meta-paths-based (Ferrini et al., 2024), Koopman theery-bbsed (Guerra et al., 2024), Decision Tree-based Secchler-Speiche et al., 2024b), or other model-specific techniques (Yu et al., 2020; 2022; Giunchiglia et al., 2022; Serra & Niepert, 2022; Spinelli et al., 2023). Furthermore, Müller et al. (2023), Bechler-Speicher et al. (2024a), and Zerio al. (2025) introduced different families of Self-explainable GNNs that avoid extracting subgraph explanation altogether, either by distilling the GNN into a Decision Tree, or by relying on learnable shape functions, respectively. Azzolin et al. (2025b), instead, proposed an hybrid approach to extract subgraph- explanations together with other forms of explanations, like rule-based explanations (Armgaan et al., 2024; Pluska et al., 2024: Rissaki et al., 2025).
Robustness of explanations. Several works have outlined that GNN explanations are fragile and can be easily broken (Li et al., 2024a;b; 2025). While their analysis mostly pertains to post-hoc explanations, a natural question is whether the problem we outlined in Section 3 can be related to lack of robustness. For instance, Li et al. (2024a;b; 2025) show that it possible to adversarially perturb the input graph to drastically change the provided explanation while leaving the prediction intact. We note, however, that this does not necessarily apply to the failure case of Section 3. To illustrate this, provide two examples of SE-GNNs that output unfaithful, degenerate explanations. One of them is also susceptible to the explanation brittleness phenomenon described in (Li et al., 2024a), whereas the other is not:
Degenerate and fragile SE-GNN: Let consider a toy binary graph-classffiction task in which each graph is composed of randomly attached nodes colored either red or blue. A graph is labeled positive if the number of blue nodes exceeds the number of red nodes. Each instance is additionally augmented with some fixed uncolored motifs (4-star, triangle, 6-clique): positive graphs contain the 6-clique and at least one between 4-star and a triangle, whereas negative graphs contain the 6-clique and may or may not contain any other motifs. We now consider the following subgraph anchor set (see the extended analysis in Definition 2):
Z' = ((G) c (G) =tar, G = triangle)')
Note that Z' contains only motifs with no label-discriminative power by construction. Therefore, any accurate SE-GNN that outputs explanations restricted to Z' produces unfaithful, degenerate explanations. Similarly to Theorem 2, we provide below a valid construction of such a case:
e(G argmin |G"|
and g(G))) = y
GREG
where y is the graph label inferred by e(). Consider now positive graph G that contains the clique and the star, so that the explanation extracted by the model highlights the star. Applying the attack in Li et al. (2024a), we aim modify the explanation while keeping the predicted label unchanged. A simple input manipulation consists of adding a single edge between any two leaves of the star, thereby creating a triangle. Because the triangle is smaller motif, the explanation extractor will now prefer selecting it, thus changing the explanation without affecting the prediction.
Degenerate and robust SE-GNN: Example 1 is already an example of a robust, degenerate SE-GNN. This is because the SE-GNN cannot change the predicted explanation unless the
22

---

Published as a conference paper at ICLR 2026
relative numerosity of red and blue is altered, which also results in change of the graph label. However, this violates the constraints of the attack proposed by Li et al. (2024a), making the attack unfeasible.
These examples together show that SE-GNNs can also be affected by fragile explanations, and it is possible to manipulate their explanations via the attack proposed in Li et al. (2024a;b; 2025). However, the failure case outlined in Section 3 is not a consequence of this brittleness.
Li et al. (2025) further considers another type of attack, designed to change the prediction itself. In this case, robustness indeed can play role in the explanation's 's faithfulness. For instance, EST (Definition 1) can be seen as measuring the robustness of the model to changes outside of the explanation, and devising an SE-GNN that is robust to such perturbations will naturally lead to non-degenerate explanations (c.f. Appendix F.3). This goal is, however, different from Li et al. (2025), which, instead of training SE-GNN to be intrinsically robust, builds wrapper around an already trained GNN to make it more robust post hoc. A validation of the most effective strategy is left as interesting future work.
D IMPLEMENTATION DETAILS
We relied the codebase provided by Gui et al. (2022), which implements GSAT and DIR. The implementation of SMCNN is derived from Azzolin et al. (2025b). Every model uses ACR (Barceló et al., 2020) backbone, where each operation is modified to incorporate the conditioning on explanation relevance scores as follows:
h COM' (Upd' (pa
1 (a(())))) Read(((poly | (VE)))
(20)
where Read and Aggr are defined as the sum, Upd' and COM' 3-layer MLP for MNISTsp and MUTAG, and as a 2-layer MLP for other datasets. This choice of model backbone was driven by the fact that ACR has precise mapping the range of tasks it can solve (Barceló al., 2020), and therefore guides the range of tasks for which the explanation extractor can meet the conditions highlighted in Theorem 1, which nonetheless remains valid for any backbone. In the SE-GNN's classifier, each MLP has the bias term deactivated, discouraging the emergence of default predictions (Faber et al., 2021). Also, the final graph global readout implements Explanation Readout (Azzolin et al., 2025a). i.e.. it weights the final node embeddings based based on their relevance score. Further details about hyperparameters and the dataset are provided below.
D.1 IMPLEMENTATION DETAILS OF SECTION
D.1.1 NATURAL TRAINING
When training models without malicious attacks, we stick to the original training procedure of each SE-GNN. In particular, we fix the hyperparameters as follows:
RBGV: Each model is trained with a batch size of 64 and for a number of epochs set 200 with learning rate of 0.0001 and without weight decay or dropout. Also, we fix the global readout to sum, and use 2 layers for both the explanation extractor and classifier. The embedding dimension is set to 100. For GSAT, we set r = 0.3 and À = 0.1. For SMGNN, we set Aspars = 0.4, Aentr = 0.1. For DIR, we set K to 0.5 and
10.
MNISTsp: Each model is trained with a batch size of 256 and for a number of epochs set to 200 with learning rate of 0.001 and without weight decay or dropout. Also, we fix the global readout to sum, and use 2 layers for both the explanation extractor and classifier. The embedding dimension is set to 300. For GSAT, we set r = 0.7 and 0.1. For SMGNN, we set Aspars = 0.01, Aentr = 0.015. For DIR, we set K to 0.8 and À 0.0001. SMGNN and DIR further adopt Batch Normalization across GNN layers (loffe, 2015).
MUTAG: Each model is trained with batch size of 64 and for number of epochs set to 100 with learning rate of 0.001 and without weight decay or dropout. Also, we fix the global readout to sum, and use 2 layers for both the explanation extractor and classifier. The embedding dimension is set to 64. For GSAT, we set r = 0.7 and > = 1. For SMGNN, we set Aspers = 0.001, Aentr = 0.008. For DTR, we set K to 0.5 and À= 0.0001.
23

---

Published as a conference paper at ICLR 2026
SST2P: Each model is trained with batch size of 256 and for number of epochs set to 100 with a learning rate of 0.001 and without weight decay. The dropout ratio is set to 0.3. Also, we fix the global readout mean, and use 2 layers for both the explanation extractor and classifier. The embedding dimension is set to 64. For GSAT, we set r = 0.7 and À = 1. For SMGNN, we set Aspars 0.1, Aentr 0.1. For DIR, we set K equals 0.6 and À 10. In this particular case, slightly changed the learning rate to 0.0002 and the training batch size to 128, which we found helped with convergence. SMGNN further employs Batch Normalization across GNN layers (loffe, 2015).
D.1.2 MALICIOUS TRAINING
Since we aim to maliciously attack the model, we assume full control over the model's training. While this is limitation of our attack, it fits the scenario in which an external service provider want to conceal the use of protected attributes, highlight a risk in the trustworthiness of the explanations they provide. Regardless, we show in Section 6 that explanations similar to those extracted in Section 4 also appear in natural scenarios, further motivating the study of this weakeness. When training models under the attack presented in Section 4, the objective becomes the one illustrated in Eq. (3). Other opplanationrreguariizali
losses are deactivated to avoid conflict with the applanation-uuprrvvsstt loss of Eq. (3). The other hyperparameters, including the training batch size, remain unchanged with respect to the ones reported above.
Since the supervision provided by Eq. (3) can be highly class-unbalanced, with many more negatives than positives, we manually reweigh by 10 the contribution from positive nodes for RBGV, and by 100 for other datasets. Then, SE-GNNs are trained for maximum of 1500 epochs, and define the stopping criterion as condition on the SE-GNN's loss and accuracy on the training set, as follows:
For DIR, we set the threshold on minimum aceuracy as for MNISTsp and CPatchMNN for MUTAG, and 99 for SST2P and RBGV. The threshold on minimum classification loss is instead set as 0.01 M STsp, CPatchMNTSS and RBGV, 0.08 for MUTAG, and 0.015 for SST2P. For GSAT and SMGNN, instead, the threshold on minimum accuracy is set to 95 for MNTSTsp. CP CPatchMTT ST, and MUTAG, 96 for SST2P, and 99 for RBGV. The threshold on minimum classification loss is instead set to 0.08 MNISTsp, Caat ChMNIST, and MUTAG, 0.015 for SST2P, and to 0.01 for RBGV.
95
Those values were manually defined after inspecting explanations on the validation set. The final model is picked as the last checkpoint when training is stopped.
D.2 IMPLEMENTATION DETAILS OF SECTION
The rejection ratio computed in Eq. (4) provides a more interpretable way to judge the faithfulness of explanations. Typical metrics, in fact, rely on the average change in class probability, which yields scores whose upper-bound depends on the underlying distance function d used, like Total variation or Kullback-Leebblr. Some metrics further non-linearly normalize those values to squash them in the fixed [0, 1] range, introducing further sources of variation (Azzolin et al., 2025a). This makes it harder to find a precise rejection criterion separating good from bad metric values, as it requires defining a threshold on the expected change. To avoid this issue, we opt for the max aggregation in Eq. (4), providing a best-case evaluation.
At a high level, Eq. (4) computes the fraction input graphs whose prediction can be changed after applying the perturbations induced by each faithfulness metric, i.c., according to I. To allow for some slack, we consider perturbation as prediction-changing if it makes the classifier's output highly uncertain, e.g., if the predicted probability lies in [0.4, 0.6] for binary classification.
D.3 IMPLEMENTATION DETAILS OF SECTION
In Section 6 provide similar natural training of SE-GNNs Section 4, with the only difference that hyperparameters are optimized to increase the sparsity of explanations, while making sure that the final accuracy is not significantly penalized. All the other aspects of model training are kept unaltered. We detail below the chosen hyperparameters for this analysis, reporting only those that differ from Appendix D.1.1.
RBGV: SMGNN is trained with Aspers 0.4 and Aentr = 1.0, and with Batch Normalization across GNN layers. GSAT is kept the same as in Appendix D.1.1, while DIR uses topK selection with K
24

---

Published as a conference paper at ICLR 2026
equals 1% as discussed in Section 6. This particularly low value is set on purpose and to verify that DIR can learn to squash all the relevant information inside a small, potentially unrelated, subgraph.
MNISTsp: SMGNN is trained with Aepare 1 and Aentr 1.5. GSAT is kept the same in Appendix D.1.I, while DIR uses a topK selection with K equals 10%. We note that DIR reportedly performs poorly the MNISTsp dataset (Wu et al., 2022), and even using larger K does not yield good results.
MUTAG: SMGNN is trained with Aspers 0.1, Aentr 0.8. GSAT is kept the same in Ap- pendix D.I.I, while DIR uses a topK selection with K equals 10%. This is the only case where setting significantly lower K alters performance compared
larger K.
SST2P: GSAT and SMGNN are kept the same as in Appendix D.1.1, while DIR uses a topk selection with K equals 10%. We noticed that SMGNN trained for random seed number 5 yields all scores squashed to 0, and we removed it from our analysis. Similarly, random seed 3 for DIR yielded significantly lower accuracy, and we also removed it.
D.4 DATASETS
We considered the following datasets in analysis:
RBGV (ours). Nodes colored with one-hot encoding of either red, blue, green, violet. The task to predict is whether the number of blue nodes is larger than the number of red ones. The topology is randomly generated from a Barabási-Albert distribution Barabási & Albert (1999), and we ensure that green and violet nodes are always disconnected. Each graph contains a total number of red and blue in the range [o, 100). plus a single green and a single violet node. The total dataset size is 5000 graphs, divided with an 80/10/10 split into train, validation, and test sets, respectively.
MUTAG (Debnath et al., 1991), abbreviation for Mutagenicity, is molecular property prediction dataset, where each molecule is annotated based on its mutagenic effect. The nodes represent atoms and the edges represent chemical bonds. The dataset is composed of 4337 graphs, where negative labels indicate mutagenic molecules and positive non- -e--aaettenccc ones.
MNISTsp (Knyazev et al., 2019) converts the popular MNIST mmage-basee digit recognition dataset (Lecun et al., 1998) into graphs by applying a super pixelation algorithm. Nodes are then composed of superpixels, while edges follow the spatial connectivity of those superpixels.
(ours) is an extension of MNISTsp where we color the top-left and bottom- right pixels with specific color that is indicative of the final label, as detailed in Table 7. This experiment is detailed in Appendix E. Visual examples are shown in Fig. 4.
SST2 is a sentiment analysis dataset, from Yuan et al. (2022). The task requires predicting the sentiment polarity of tweets, which are either labeled as negative or positive. Node features are contextual embeddings from a pretrained language model (Yuan et al., 2022).
SST2P (ours) is an extension of SST2P, where we force each input sample to contain a single "," and single in the input, such that they are not informative of the final label. To make sure that "." and "." are not correlated with the label, we add them isolated nodes in the graph. If the graph originally contained such punctuation, we first remove To further avoid the contextual embedding from carrying some information regarding amotion-ladee words, we use fixed embeddings for "," and ".". respectivvyyyy set to I and 0.
D.4.1 DESIGNATED EXPLANATIONS FOR SECTION
In our experiments, we define the following designated explanations PK: For MNISTsp, these explanations highlight background pixels, similarly to Jethani et al. (2021); For MUTAG, these highlight hydrogen (H) and carbon (C) atoms, and plot in Fig. 10 the relative frequencies of these atoms, showing they are not informative of the label; For SST2P, the designated explanations highlight "." and ".", similarly to Yu et al. (2019); For RBGV, instead, these highlight green and violet nodes, which are clearly uninformative of the underlying task to predict. We report in Table the mapping between classes and designated explanations.
25

---

Published as a conference paper at ICLR 2026
Table 5: Designated explanations are defined as nodes that are unrelated the task being solved. Yet, in Section 4 we show that SE-GNNs can extract these explanations while accurately solving the task. "H" and "C" stand for hydrogen and carbon atoms, respectively.
Dataset
Task predict
Designated Expl. pă
If blue > red nodes
Green node for y 1, violet node for = 0 Top-left and bottom- right y-th pixel H atoms for y = 0, C atoms for y
RBGV
MNISTsp
Digit number
Mutagenicity of molecules Tweet sentiment polarity
MJTAG
SST2P
" for y 0, for y
D.5 THRESHOLDING EXPLANATIONS
As discussed in Section 2, SE-GNNs output relevance scores the interval [0, 1]. Then, to extract a discrete subgraph that users consume, need to define selection criterion to decide which nodes are to be considered part of the explanation, and which are not. Following Tai et al. (2025), and in accordance with the semantics each SE-GNN gives explanation relevance scores it predicts, we define some threshold values for SMGNN and GSAT, as follows.
For naturally trained models, we fix the threshold to 0.5 for SMGNN Tai al. (2025), whereas for GSAT we set it to 0.9. This is done because GSAT's relevance scores are associated with the probability of sampling each node/edge, hence we consider as relevant only those that can be consistently sampled with high probability. The only exception is GSAT trained for RBGV, where the threshold again probability around 0.3 (by setting r = 0.3). and therefore a probability of 0.5 is already consistently higher than 0.3. Occasionally, SMGNN'S relevance scores all collapse to values around 0, or to values such that node has a value greater than 0.5. To avoid manually defining case-by-case thresholds when this happens, we apply an instance-wist wise min-max normalization while sticking to the 0.5 threshold. In particular, this happened for MNISTsp and MUTAG. For DIR, instead, we keep the topK selection used during training.
0.5. This because for RBGV, GSAT is trained to push the sampling
For attacked models, the threshold is fixed 0.5 SE-GNNs are explicitly trained to extract binary relevance scores. This also applics to DIR, for which we remove nodes inside the topK subgraph having score less than the threshold. This is because nodes with score close 0 should still be considered irrelevant, even if in the topK.
D.6 FAITHFULNESS METRICS
Each faithfulness metric defines a of allowed perturbations indicated with I. Perturbations either applied to the complement - for sufficiency or to the explanation - for necessity metrics. Below, we detail the implementation details for the metries we empirically tested in Section In all cases, the explanation selection mechanism is fixed and detailed in Appendix D.5.
Fid-: I is simply defined as the perturbation removing the complement of the explanation from the graph, and feeding the explanation alone back to the model.
Fid+: I is simply defined as the perturbation removing the explanation from the graph, and feeding the complement of the explanation alone back to the model.
RFid-: I defined random edge removals from the complement, where each edge is removed independently from the others and with a fixed probability. Following Zheng et al. (2023), we fix the probability 0.9. Nodes are left untouched.
26

---

Published as a conference paper at ICLR 2026
RFid+: I is defined random edge removals from the explanation, where each edge is removed independently from the others and with a fixed probability. Following Zheng et al. (2023), we fix the probability to 0.1. Nodes are left untouched.
Suf: defined as complement swaps. In particular, given the reference graph for which we compute the metric, we pick random sample from the same split and with the same label, and we swap their complements. The explanation is randomly attached to the new complement while preserving the total number of edges of the original graph.
Nec: I is defined as random edge removals from the explanation, where each edge is removed independently from the others, and the overall budget of removal is defined dataset-wiss wiiee and kept fixed for each sample. Following Azzolin et al. (2025a), we fix the budget as 10% of the average graph size of the split of data where the metric is computed. Nodes are left untouched.
CF: I perturbs only the relevance scores, where the perturbation is randomly sampled from Gaussian distribution with mean and variance estimated instance-wise, and applied to scores inside and outside of the explanation. Therefore, the topology of the perturbed graph is the same as the original one, with perturbed relevance scores. The perturbed graph is then fed to the SE-GNN's classifier I only. The expected semantics is that the classifier should be highly responsive to perturbations. Hence, large changes in the output should be expected for faithful explanations.
is defined as any possible supergraph of the explanation inside the input graph. Equivalently, given the input graph and its explanations, I randomly samples perturbations removing nodes and edges, jointly. This can be seen as a more general version of RFid-, where nodes can also be removed.
EST:
Algorithm Uniform Sufficiency Test (EST, Definition I)
Require: Input graph G, explanation R, budget of perturbations b, distance function
S ==
1: for i = 1 to b do
2: // Subsample nodes
3:
Sample random node weights
Unif(O, 1) ()
4: Force w|u] f for all v E V(R)
5: Define node set V; {u V(G w/[] > 0.5}
6:
Construct onde-induced subgraph G, = GVV
7:
8:
// Subsample e edges
9:
Sample random edge weights
Unif (0) 1)(E()))
10:
Force w/e] + 1 for all e E E(R)
Define edge set
fe ((G:) |we] > 0.5)
12: Construct edge-induced subgraph G = G,
Append G², to
14:
end for
15:
return maxo d(I(G),
Remark: Contrary to previous faithfulness metrics, which typically average the contribution from multiple perturbations, EST adopts worst-case evaluation by taking the maximum change in prediction across perturbations. This stops frequent but irrelevant perturbations from diluting rare but impactful perturbations.
E
ADDITIONAL EXPERIMENTS
E. PLAUSIBLE BUT UNFAITHFUL EXPLANATIONS
In this experiment, we aim to show that it is possible to induce SE-GNNs to output highly plausible but unfaithful explanations. We achieve this by attacking the model following the setting outlined in Section 4, i.c. adding an explicit supervisory signal to control the explanations provided by the explanation extractor. In this ease, supervise the SE-GNN to output only nodes belonging to
27

---

Published as a conference paper at ICLR 2026
Table 6: The Table reports the actual metric value computed with being Total variation hence computed without the proxy of RejRatio, for the same experiments as Table 3. The results confirm that EST consistently assigns worse values unfaithful explanations. Nonetheless, continuous scores make it harder to assess the overall behavior of the model, and when to consider an explanation as unfaithful. (f) stands for the lower (the higher) the better.
Dataset
Model
Fid-
Fid+
Suf
Nec
CF
RFid- J
RFid+
EST
SMGNN
16 or
44 0:
00
02
00 0
47 02
RBGV
GSAT
07
50 2
01 1
49
06
46
DIR
20
42
00
37
03
47
SMGNN
89 02
49 05
44 os
49
89 02
86 02
02 to
99
MNISTsP
GSAT
68
61
45
44
90
77
02 1:
99
01
in
52 04
88 01
86 m
03 1
98 0:01
SMGNN
33 02
69
31
13
46
43
06
95
MUTAG
GSAT
79
39
17
47
44
08
90
DIR
06
0s
02
03
SMGNN
08
41
01
21
02
52
SST2P
GSAT
25
45 04
01
31
08
58
01
+:
+:00
40
02 + 00
RHD-
SUF
FID+
rejectoon ratio
60
EST
40
20
200
400
800
800 1000
budget perturbations
Figure 2: Ablation study the budget of perturbations to estimate Eq. (4) for GSAT RBGV (cf. Section 5.2). The plot shows that EST steadily rejects more unfaithful explanations as the budget increases, while other metrics do substantially improve. Fid- (Fid+) have constant values, they do not apply any sampling but just erase the complement (the explanation) once. Note that EST samples subgraphs of the complement random, and thus, the probability of sampling duplicates increases as the budget increases. Future work can investigate more complex sampling strategies to avoid such duplicates.
Table 7: Mapping between colors applied to CPatchMNT and class label.
Color
Class label
the digit together with its 1-hop neighborhood, which typically considered to be the ground truth explanation for MNTSTsp (Miao et al., 2022a). To simulate the presence of protected attributes,
28

---

Published as a conference paper at ICLR 2026
color the top-left and bottom-right pixels with specific color that is indicative of the final label, as detailed in Table 7. The resulting dataset will be referred to as CP CPatchMN cttNMMIST Therefore, for the attack to be successful, we expect the explanation to highlight only nodes pertaining to the digit itself while concealing the use of the protected attribute.
We report in Table 8 the results of the attack, which confirm that it is possible to train SE-GNNs to output highly human-desirable explanations - in particular those matching the human expectations whilst the model is also relying crucially on other potentially protected features. We provide some visual examples of the attack in Fig. 3, and the predicted label for graphs with swapped colors Fig. 4.
Table 8: Accuracy and test accuracy after either swapping the color of the colored pixels with that of other classes (see Fig. 4), or blacking out the digit, for the experiment in Appendix E. 1. Results show that both models are highly dependent on both the digit-related superpixels and the color ones, despite only the former being declared in the explanation.
Model
Val Acc
Val Fi
Ace color swap
Acc no digit
SMGNN
100.0 1
99.3 u3
0.1 2.
9.6 i 000
GSAT
99.9 +01
99.1 t.a.
3.4 42
8.7 # 1.
Cipss-1 Prodiction-1...
Class-1 Presiction-1
Figure 3: SE-GNNs can be manipulated to output unfaithful but highly plausible explanations. We train GSAT (left) and SMGNN (right) to maximize the downstream accuracy while also optimizing for plausibility, that is, outputting the digit and its 1-hop neighbor as an explanation. Nonetheless, both models are heavily relying on the color information, shown by the severe drop in accuracy when the color information is altered (shown in Table 8), and by the arbitrary manipulation of the predicted label by swapping colors (shown in Fig. 4). The underlying dataset is an extension of MNI sp, called CPatchMN with diariiiicrim colors that are treated as protected attributes. Details about the dataset and the color coding belonging to the explanation are selected based on a threshold value on the relevance score at 0.5. Numbers above each node represent raw explanation relevance scores, Better seen in digital format.
in which we color the upper-right and bottom-left superpixels
Appendix L. The plot shows two graph examples of class 1, where nodes
Can faithfulness metrics spot plausible but unfaithful explanations? Similar to the analysis presented in Section 5.1, we investigate whether popular faithfulness metries can mark these expla- nations as unfaithful. We adopt the same setting as Section 5. and compute rejection ratios for our proposed EST, and for Fid-, and RFid- as baselines. The results in Table 9 show that RFid- can catastrophically fail to mark these explanations as unfaithful. Conversely, Fid- and EST can robustly reject a large number explanations, albeit with consistent variations across random seeds. Overall, EST achieves the highest ratios in both experiments.
E.2 EXAMPLES OF ATTACKED SE-GNNS
Taking as an example the GSAT model, we provide for each dataset in Table a few examples of graphs together with the highlighted explanations to showcase the efficacy of the attack. In particular,
29

---

Published as a conference paper at ICLR 2026
Table 9: We report the rejection ratios RejRatio, for the plausible but unfaithful explanations discussed in Appendix E. EST and Fid- robustly reject large number of explanations as unfaithful, whereas RFid- fails mark them as such.
Dataset
Model
RejRatior RFid-
Fid-
EST
SMGNN
50.7
253
0.0 0.0
50.7
CPatchMNIST
GSAT
45.3 6611
15.7 11.6
54.0
Fig. 5, Fig. 6, Fig. 7, and Fig. 8 shows such examples for RBGV, MNISTsp, MUTAG, and SST2P respectively.
E.3 FAILURES OF SE-GNN ATTACKS
Taking as an example the GSAT model on MNISTsp, which achieved slightly lower F1 score in Table 2 compared to other configurations, we provide in Fig. 9 some examples of graphs where the attacked GSAT does not provide the exact ground truth we aim for. This can emerge for several reasons, like the indistinguishabiiity of node embeddings after I. layers of message passing (i.e., oversmoothing), or because the explanation extractor failed to infer the correct graph label. Nonetheless, the examples show that even if explanations do not perfectly highlight the ground truth provided in Table 5, they are still confidently highlighting unrelated pixels while hiding the true reason behind the prediction, which is the main goal of our attack.
We further provide in Fig. 21 several examples of explanations for the test split of SMGNN on SST2P, which achieves low attack Fi score in Table 2 due to OOD samples. Also in this case, although the attack may not generalize well to OOD samples, it still consistently suppresses the relevance score of truly informative tokens, while highlighting degenerate uninformative subgraphs the most important ones.
E.4 REJECTION RATIOS FOR SUFFICIENT EXPLANATIONS
In this section, we verify that faithfulness metrics not only reject unfaithful explanations but also recognize faithful ones. Following the attack framework in Section 4, we manipulate SE-GNNs to output explanations that, by construction, include all information the model can use to solve the task. These designated explanations enforce sufficiency, though at the cost of potentially including irrelevant features. While enlarging explanations is trivial way to ensure sufficiency (Zheng et al., 2023; Azzolin et al., 2025a) and does not necessarily yield truly faithful explanations (Tai et al., 2025) this experiment serves sanity check to confirm that sufficiency metrics least recognize sufficient explanations. Accordingly, we expect rejection ratios close to zero across all configurations.
To ensure the explanation contains all the relevant information the model can use to make the final prediction, we restrict our experiments to RBCV and MNISTsp, where we have full knowledge of how to solve the task. In particular, we train each SE-GNNs with Eq. (3), where Leap is defined so to induce the following explanations: For RBGV, we extract all red nodes for the negative class, and all blue nodes for the positive class, i.e., PM. graph, pKt = 1 for any blue node in a positive graph, and pV 0 otherwise. For MNISTsp, we extract each pixel associated with the digit and its 1-hop neighborhood, i.e., pa for any node belonging to the digit itself or to its h-hop neighborhood, and pV. O otherwise. Note that these explanations are, in fact, constructed to contain all the features that are known to be related to the task at hand.
Experimental setup:
for any red node in a negative
The results are shown Table 10. The final accuracy and the explanation F, score confirm that the manipulation was successful, and that models are making accurate predictions while outputting our benignly designated explanations. Across both datasets, the only metries that consistently achieve rejection ratio around zero are Fid-, RFid-, and EST, with fluctuations in around one case each.
'For instance, given graph with three red nodes and two blue nodes, highlighting the three red nodes as the explanation ensures that perturbation on nodes of the complement can change the class of the graph. Hence, the explanation is sufficient.
30

---

Published as a conference paper at ICLR 2026
Among them, EST also the one achieving the best results in Table 3, confirming its reliability. Suf and CF, instead, reject high amount of explanations, suggesting that the high rejection ratios obtained in Table 3 were probably conflated by too aggressive metric.
Table 10: Accuracy, explanation F1 score, and rejection ratios for different metrics computed for models trained to output explanations containing all the relevant features models can use. The experimental setting is described in Appendix E.4 and constitutes sanity check verify that metrics with high rejection ratios in Table are not simply rejecting any explanation, but are indeed verifying whether the explanation does not include some relevant pattern used by the model.
Dataset
Model
Test Acc
Test Fi score
Rej rijratioo CF
Fid-
Suf
RFid-
EST
SMGNN
100 0:00
98 01
01
76
14 1 o
00 c
01 =
RBGV
GSAT
100 00
99 =11
01 01
78 oz
13 02
00 00
01 01
DIR
100
98 =01
01
93
57
01 =
01 01
SMGNN
90 01
99 201
01 01
75
93 4 0
01 o:
01 01
MNISTsp
GSAT
93
99 011
01 01
35
07 04
15
05 05
DIR
89
99 =11
22
86
93 + 0
01 =
07 0z
F ADDITIONAL DISCUSSION
F.1 EVALUATING Sufficiency AND Necessity JOINTLY
Sufficiency and necessity metrics are often evaluated in conjunction, so that an explanation consid- ered faithful only if is at the same time both sufficient and necessary (Amara et al., 2022; Longa et al., 2024). The remark on previous metrics provided in Section 5.2 generalizes to this case.
Consider the same setting as Example I for negative instance whose explanation is R Ugreen- As previously observed, R is the smallest label-preserving subgraph, as 2 0. Then, any Complement and Explanation removal metric, such Fid- and Fid+, will mark such explanation sufficient as R is subel-preserving and necessary as removing the green node will make the classifier in Eq. (2) outputting maximally uncertain predictions.
F.2 ARE NECESSITY METRICS USEFUL FOR SE-GNNS?
In this section, we aim at answering the question of whether metrics estimating the necessity of explamations are useful for finding the failure cases of SE-GNNs outlined in Section 3. Let us consider the following representative SE-GNN outputting unfaithful explanations for any arbitrary binary classification task, represented by the boolean classifier vb:
if R 40 if R = 41
e(G)
{{u = [u (G)
=
Uo if (G)
g(R)
1
(21)
0.5
otherwise
where g acts as a simple mapping from explanations to labels, and ti and #n can either be label or subgraphs of the input sample G, and are assumed to be non-representative of the true behavior of the model by construction. Note that Eq. (21) matches Example 1 whenever corresponds to Hbuue #red, un Ugreen. and ii Uniolet- Then, any necessity metric would apply perturbations to R to induce some shifts in the classifier's output. If such perturbation succeeds in changing the prediction of the model, the explanation is marked as necessary, and thus faithful. Nevertheless, Mo and are in fact relevant for the classifier which trivially maps mo and M1 to class labels. This means that removing them will always bring a change in the output class, regardless of how unfaithful wo and actually are.
F.3 THEORETICAL ANALYSIS OF EST
We aim to theoretically characterize which family of explanations EST can mark as unfaithful. We do so by relating Definition with the following three formal notions of explanations:
31

---

Published as a conference paper at ICLR 2026
Definition 3 (Prime Implicant explanation (Azzolin et al., 2025b)). Let be classifier and G be an instance with predicted label f(G), then R. is a Prime Implicant explanation f (G) if:
1. R.G.
2. For all Rt, such that R R' G. we have that f(G) - F(R).
3. No other R' C R satisfies both (1) and (2).
Prime Implicant explanations have been widely studied in the formal explainability literature, and considered of high-quality as they possess several desirable properties (Marques-Silva & Ignatiev, 2022; Azzolin al., 2025b; Bassan et al., 2025a;b). In nutshell, Prime Implicant explanations comprise minimal-sufficient explanations, which are the minimal explanations provably robust to changes in the complement. A related notion of explanations is Minimal explanation, introduced next:
Definition 4 (Minimal explanation (Azzolin et al., 2025b)). Let f be a SE-GNN and G be an instance with predicted label f(G), then R S G is Minimal explanation for f(G) if:
1. f(G) ((R)
2. There exists no R' C G such that [R|] < [R] and f(G) = f(R)).
Minimal explanations have been shown to equal Prime Implicant ones for subgraph- tasks, but in the other cases they are deemed as less informative and potentially ambiguous (see Figure 1 in Azzolin al. (2025b)). An even weaker notion of explanations introduced next:
Definition 5 Mion-label-presevviee
explanation). Let f be SE-GNN and G be instance with predicted label fG)), then R C G is a Non-tabellpreserving explanation for f(G) if f(G) + f(R).
This notion of explanation is clearly weaker than the previous two, as it embraces explanations that do not contain enough information to yield the same prediction as the original sample meaning they are omitting key relevant features- and allow any subgraph be selected as the explanation. An example of this failure case is given in Example 1: the subgraph highlighted by R = Uwintet is non-label preserving subgraph, as despite explaining the positive class, the subgraph has an equal count of reds and blues, yielding the model to predict the negative class. A similar example can also be found for Minimal explanations: the subgraph highlighted by = Ugreen is a Minimal explanation, as there exists smaller explanation, and feeding Eq. (2) with it will yield the same prediction (as 0 2 0). Yet, Uggreen is never used by e to infer the label, yielding a misleading explanation that can misguide model debugging (Teso et al., 2023) and scientific discovery (Wong al., 2024) by falsely suggesting green nodes are linked to the negative class. An additional example is also highlighted Section 3 of Azzolin et al. (2025b), where Minimal explanations are shown highlight counter-intuitive subgraphs that do not robustly indicate the model's behavior. In light of the above considerations, Minimal and Non-label prreeerrin should be regarded as notions that admit degenerate explanations.
We proceed to show how EST fares at marking the previous notions. In the following analysis, we will consider EST fully enumerating all possible extensions in Eq. (5), and consider a perturbation to yield sufficiently large prediction shift whenever it changes the predicted class.
Theorem 3. EST marks Minimal and Implicant explanations as faithful.
explanations as unfaithful and Prime-
Proof. We will analyze each explanation family of explanations separately:
Prime Implicant explanations: If the explanation R is Prime Implicant explanation, by definition, it holds that:
g(e(G)) = g(e(RR)
RR
(22)
Hence, it follows trivially that Eq. (5) will never encounter a prediction change, hence will mark the explanation as faithful.
2. Minimal explanations: We show that if an explanation R fulfills EST (i.c., Eq. (5) equals zero for any R' such that R C R C G) and is therefore considered to be faithful, then R
32

---

Published as a conference paper at ICLR 2026
be Minimal explanation only if it is also Prime Implicant. In other words, if an explanation passes the EST test, it cannot be just Minimal explanation.
Let consider explanation R. that passes the EST test and is a Minimal explanation. Then, it holds that:
1. R G.
2. g(e(G)) g(e(R)) YR R'CR
3. AR' G such that [R|| < [R and g(c(G)) g(c(RR)).
Note that condition 3 implies that no other I'' C R satisfies both conditions and 2. This is because being label-preserving is a necessary condition for condition 2 to be true. However, condition 3 ensures that there does not exist any smaller label-preserving subgraph than R. hence no smaller explanation satisfying condition 2 exists. Therefore, R is the smallest subgraph that satisfies condition 2, hence a Prime Implicant explanation.
Non-Label-preservingg explanation: Non-Label-preserving explanations are, by definition, non-label-preservee subgraphs. Since EST samples perturbed graphs R S Rt' C G uniformly, it can always sample R' = R. Hence, evaluating Eq. (5) with R' R will bring prediction change, which marks the explanation as unfaithful.
In words, this result shows that EST can flag Minimal and san-llael--reserving explanations as unfaithful. By definition, these explanations allow the model's prediction to be altered by changes outside the explanation, leaving room for unfaithful or even malicious behaviors. In contrast, Prime Implicant explanations do not permit prediction changes under complement perturbations, making them more robust. An interesting direction for future work is to investigate whether Prime Implicant explanations themselves still admit degenerate cases.
G FIGURES FROM TABLE 4
33

---

Published as a conference paper at ICLR 2026
Rredel
Prode2
Me:: 19 Cassel Rreded
Me: 15 Casse] Proded
19 Cass-] PreduS
19 Cassa] Predufi
19 Cisspeiiese
Figure 4: Despite GSAT's explanation declaring that only the digit information is used for the graph
in Fig. 3, swapping the color to that of other classes, following the schema Table 7, results in arbitrary manipulation of the final prediction.
34

---

Published as a conference paper at ICLR 2026
Classi Prediction1.0
Classid Prediction 0.005
Classe Prediction11.0
Classnd Prediction-
Figure 5: Explanations provided by the attacked GSAT on RBGV. Numbers above each node represent explanation relevance scores, and explanatory nodes selected based 0.5 threshold. Better seen in digital format.
Cloga=1 Prodiction1
Clazp-0 Prediction-O
Cipss-8 8
Prosiction-3
Figure 6: Explanations provided by the attacked GSAT on MNISTsp. Numbers above each node represent raw explanation relevance scores, and explanatory nodes selected based 0.5 threshold. Better seen in digital format.
35

---

Published as a conference paper at ICLR 2026
Closs-1 Predicton-1100
Gas--1 Predictinn10 1.0
Class-O Prediction-0.3
Class-0 Prestction-000
Figure 7: Explanations provided by the attacked GSAT on MUTAG. Numbers above each node represent raw explanation relevance scores, and explanatory nodes selected based on 0.5 threshold. Better seen in digital format.
36

---

Published as a conference paper at ICLR 2026
Prediction on=1.0
are
more deoply thought through than
most
right
thinking
fimm
Class=1 Prediction=1.0
equals the
original and
ways
betters
0.2
0.2
0.0
Class=0 0 Prediction 0.002
the
plot nothing
but
bollerplate from start
finish
Oass=0 Prediction=0.00
pleachy
poirly
04
Figure 8: Explanations provided by the attacked GSAT on SST2P. Numbers below each node represent raw explanation relevance scores, and explanatory nodes selected based 0.5 threshold. Better seen in digital format.
37

---

Published as a conference paper at ICLR 2026
Classen Prediction9
Classs Predictionn
Clasueó Predictionéé
Prediction)
Figure 9: Explanations provided by the attacked GSAT on MNISTsp. Even if explanations do not perfectly highlight the ground truth provided in Table 5, they still hide the true reason behind the prediction, i.e., the digit in the image, while confidently highlighting apparently unrelated pixels. Numbers above each node represent raw explanation relevance scores, and explanatory nodes are selected based on 0.5 threshold. Better seen in digital format.
3200
0,50
0032
2000
7250
2000
750
5.0
30.0
12.5
37.5
count of prosent the graph
Figure 10: Frequencies of appearance of carbon (C), nitrogen (N), and hydrogen (H) atoms in MUTAG, divided per class.
38

---

Published as a conference paper at ICLR 2026
GSAT
color
color
color
color
sempe avg count
80
80
80
80-
20
20
20
20
3.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
81
per-sample avg count
100
100
100
100
0.8
0.4
40
40
40-
40
20
3.0 0.5
3.0
0.0
0.5
1.0
0.0
0.5
1.0
0.6
0.5
1.0
R 6
explanation relevance
Figure 11: Diagram representing the distribution of explanation relevance score for seed of GSAT trained on RBGV according the setup described in Section 6. The four pairs plots on the left report the distribution of relevance scores, divided by class label and node color (Red, Blue, Green, and Violet), while the last pair on the right reports the boxplot (colored bars) and average count (green triangle) of each color present in the explanation of each sample. Nodes included in the explanation are chosen as those with a score greater than 0.5. Overall, GSAT roughly picks a single red node for 1, corresponding to the smallest label-preserving explanations. When computing rejection ratios for faithfulness metrics, we respectively get rejection ratio of 58.7% for EST, 0.9% for Fid-, and 0% for RFid-, Although red and blue nodes seem legitimate explanation for this task, highlighting only one them is nonetheless still concealing the fact that the model needs look at all of them to make correct prediction. Therefore, the low rejection ratios of Fid- and RFid- are considered to be failure cases, as they flagged explanations not containing every element the model is actually using infer the prediction faithful. EST, instead, correctly rejects a considerable number of explanations.
0 and a single blue node for
39

---

Published as a conference paper at ICLR 2026
DIR seed
per-sample avg
100
100
100
100
1.0
+
50
60
40
40
40
40
0.2
dersity
0.0
-2
1
-1
color
color
color
color
per per-samplc count
0.8
80
60
60
66
0.6
20
20
20
0.0
explanation relevance: scores
Diagram representing the distribution of explanation relevance score for seed DIR trained on RBGV according to the setup described in Section 6. The four pairs of plots on the left report the distribution of relevance scores, divided by class label and node color (Red, Blue, Green, and Violet), while the last pair on the right reports the boxplot (colored bars) and average count (green triangle) each color present in the explanation of each sample. Nodes included the explanation are chosen as those having the top-1% relevance scores. Nodes not belonging to the top- % are assigned a score the explanation for y 0 similarly the malicious explanations defined in Section - whereas for y = 1 the model is roughly selecting a single blue node. When computing rejection ratios for faithfulness metries, respectively get rejection ratio of 47% for EST, 0% for Fid-, and 22% for RFid-. Those values highlight catastrophic failure of Fid-, which is reflected by the high standard deviation in Table
Figure 12:
1 in the plot. Overall, even with natural training, DIR picks the violet node as
40

---

Published as a conference paper at ICLR 2026
SMGNN seed
color R
color B
color
color
per-sample count
100
80
0.8
Y-0
50
60
60
20
0.0
0.5
color R
color
color
color V
per-sample avg count
80
80
0.02
0.00
-0.03
20
20
20
1.0
0.5
0.5
V
explanation relevance scores
Diagram representing the distribution of explanation relevance score for seed of SMGNN trained on RBGV according to the setup described in Section 6. The four pairs plots on the left report the distribution of relevance scores, divided by class label and node color (Red, Blue, Green, and Violet), while the last pair on the right reports the boxplot (colored bars) and average count (green triangle) of each color present in the explanation of each sample. Nodes included in the explanation are chosen as those with score greater than 0.5. Overall, even with natural training, SMGNN picks green and violet nodes as the explanation for y 0 similarly the malicious explanations defined in Section 4 whereas for = the model is assigning zero relevance to every node. We then compute rejection ratios only for the negative class, getting value of 99% for EST, 0% for Fid-, and 98% for RFid-. Those values highlight a catastrophic failure of Fid-, which is reflected by the high standard deviation in Table 4.
Figure 13:
41

---

Published as a conference paper at ICLR 2026
Clagsud Predictionss
Predictionno
(a) EST Fid- 0, RFid- Class-? Prudiction?
(b) EST 0. Fid- 0. RFid- 0
Class-9 Presiction
(c) EST 0, Fid- 0, RFid- =
(d) EST = 1, Fid- 0, RFid- =
Presictions
EST Fid- 0, RFid-
(0 EST Fid- RFid-
Figure 14: Examples of explanations for seed 4 of GSAT trained on MNISTap according to the setup described in Section 6. Nodes included in the explanation are chosen as those with a score greater than 0.9. Overall, GSAT extracts explanations highlighting the whole digit with the addition of some background pixels. Therefore, we expect explanations to contain most of the information the model to make correct predictions. In fact, the rejection ratios reported below each example confirm that, in most cases, little to no relevant information is left in the complement. In particular, we report the value whenever each metric rejects the explanation, and 0 when not.
42

---

Published as a conference paper at ICLR 2026
Clasomd Prediction))
Class Precictionss
(a) EST Fid- 1, RFid-
(b) EST = 1, Fid- 0, RFid- 1
Claspe
cless-3 Pradictione3
EST = Fid- RFid-
(d) EST Fid- RFid
Claosud Prediction:6
Class Preciction:5
(e) EST 1, Fid- 0, RFid- =
(0 EST 1, Fid- 1. RFid- =
Figure 15: Examples explanations for seed of SMGNN trained on MNISTsp according to setup described in Section 6. Node relevance scores min-max normalized in the range [0, to ensure a meaningful thresholding across seeds, and the nodes included the explanation are chosen those with score greater than 0.5. Overall, SMGNN extracts explanations highlighting background pixels, hinting to the fact that the model could be extracting Degenerate explanations. fact, the rejection ratios computed for each example confirm that explanations cases. The only exception Fid-, which marks them as faithful in 2 cases. Recall that a rejection ratio of in the plots above means the explanation is rejected, hence considered unfaithful by the metric.
marked as unfaithful in most
43

---

Published as a conference paper at ICLR 2026
Cluss= Prediction
Class fradiciin--3322
8
(a) EST = 1, Fid- = 1, RFid- =1
(b) EST = 1, Fid- = 1, RFid- = 1
Class Prediciior0:116
Class-O Pn..
(c) EST Fid- 1, RFid-
(d) EST 1, Fid- 1, RFid- 1
Classu Fredetoo=00199
Classod Predicton:D.c35
(e) EST 1, Fid- = L, RFid- =
(1 EST = Fid- = 1, RFid- = 1
Figure 16: Examples of explanations for seed of GSAT trained on MUTAG according to the setup described in Section 6. Nodes included in the explanation are chosen as those with a score greater than 0.9. Overall, although it is hard to judge whether explanations are faithful or not by visual inspection in this case we do not have full knowledge about the task and scores not maximally sparse - we can still make the following observations: First, explanations tend to highlight atoms that are known be uninformative of the target label when taken alone, like C and N (cf. Fig. 10); Second, rejection ratios for all metrics are non-negligible (see Table 4), outlining a substantial agreement in judging these explanations as unfaithful. Recall that a rejection ratio of in the plots above means the explanation is rejected, hence considered unfaithful by the metric.
44

---

Published as a conference paper at ICLR 2026
Classe1 Predk Tondiiiionn.... 6..50 653
Class-o Pradiction 0.31
(a) EST 1, Fid- 1, RFid- =
(b) EST = 1, Fid- 1, RFid- = 1
Class- Predictor-0.112
Casz- Preditten-0:228
(c) EST = 1, Fid- = 1, RFid-
=
(d) EST = 1, Fid- = 1, RFid- = 1
Cluss= Predkcisrr-.599
Classei 2.55
(c) EST Fid- 0, RFid- =
(f) EST 1, Fid- RFid- =
Figure 17: Examples of explanations for seed 3 of SMGNN trained on MUTAG according to the setup described in Section 6. Node relevance scores are min-max normalized the range [0, 1] to ensure mcaningful thresholding across seeds, and the nodes included in the explanation are chosen as those with a score greater than 0.5. Overall, although it is hard to judge whether explanations are faithful or not by visual inspection in this case scores are not maximally sparse we can still make the following observations: First, explanations tend to highlight atoms that are known to be uninformative of the target label when taken alone, like C and H (cf. Fig. 10); Second, the same explanation can appear for different classes, like (a) and (d); Third, rejection ratios for all metrics are substantially high (see Table 4), outlining agreement in judging these explanations as unfaithful. Recall that rejection ratio of 1 in the plots above means the explanation is rejected, hence considered unfaithful by the metric.
do not have full knowledge about the task and
45

---

Published as a conference paper at ICLR 2026
GSAT seed 1
GSAT seed
592
density
200
100
explanation relevance scores
explane tion relevance scores
GSAT seed 3
GSAT seed
400
density
density
200
50
explanation scores
explanation scores
300
explanation
Figure 18: Histograms explanations scores for different random seeds GSAT trained on SST2P according to the setup described in Section 6. Overall, relevance scores are all squashed around 1, meaning the model weights equally all nodes. Therefore, by thresholding explanations at 0.9 results in explanations covering the full graph, which makes the explanation trivially sufficient. Hence, metrics achieve a rejection ratio of 0%.
46

---

Published as a conference paper at ICLR 2026
Class Prediction -.00c
filmaloss
dradge
(a) EST = 1,d 0, RFid- = 0
(b) EST = O, Fid- RFid-
Class-d Prediction-0.000
nothing but bollerplate clichés
from
start
to
finish
(c) EST Fid-
RFid-
Cass=O Prediction 002
fnd
Iittle
Interest
this
1m
which
otten
preachy
and
pooffy
acted
(d) EST 0. Fid- 0, RFid- = 0
Class=1 Prediction=1.0
young
charm generosity and diplomacy -10
3.0
3.8
-18
3.0
300
3.
aa
18
18
(c) EST = 0, Fid- 0, RFid- = 0
Class=1 Prediction=1.0
some
movies
suck
you
despite
their
flaws
:10
1.0
3.0
-3
0.5
-14
-10
-10
30 -13
(f) EST
Fid- RFid-
Figure 19; Examples of explanations for seed of DIR trained on SST2P according to the setup described in Section Nodes included in the explanation are chosen as those with the top 10% relevance scores. Nodes left out of the explanation are given the default score of -1. Overall, for y = 0 the explanations consistently highlight "." and ".", similarly to the malicious explanations of Section 4. For y 1, instead, explanations often highlight stop words. In addition, shown by the rejection ratios reported below each example, EST, Fid-, and RFid- can disagree on which explanation reject. In particular, EST correctly rejects explanations highlighting "." and " in two cases out of three, whereas the other metrics do not reject any of them. Recall that a rejection ratio of I in the plots above means the explanation is rejected, hence considered unfaithful by the metric.
47

---

Published as a conference paper at ICLR 2026
Class=0 Prediction00.08
WWUSt: Foveng:
the
nerds
dienés
the
fitmmkers coud dradgo
(a) EST 0, Fid- RFid-
Class=0 Prediction=0.0
that
5
far
t00
tragic
to
merit
such
superficiateatment
0.
3/
1.0
1.8
0.99
0.
(b) EST 0, Fid- RFid- 0
Class=1 Prodiction-D
are more deeply thought
through than
most
right
thinkng
fimms
(c) EST 0, Fid-
RFid-
Class=1 1 Prediction =
0. 0.985
equals
the
original
and
some
ways
even
betters
(d) EST = 0, Fid-
0, RFid- =
O
Dmna- Tredician--.000
ergety
vED
vtere
notteg
hapgerto
Fort
Ware songiing 2
happenna
(c) EST = 0, Fid- = 0, RFid- = 0
Class-O Prodiction-Q.0
preachy
poody.
Co
6M
(f) EST
Fid- 0, RFid-
Figure 20: Examples of explanations for seed of SMGNN trained SST2P according to the setup described in Section 6. Nodes included in the explanation are chosen as those with a score greater than 0.5. Overall, all explanations highlight words with high emotional content, hinting at the polarity of the sentence. Whilst this is not an indicator of faithful explanations, it is reasonable to at least expect that the model could have used this information infer the final prediction. Then, the fact that all the tested metrics agree that those explanations are not to be rejected hints that they can be considered as faithful. Recall that a rejection ratio of 1 in the plots above means the explanation rejected, hence considered unfaithful by the metric.
48

---

Published as a conference paper at ICLR 2026
Class=1 Prediction=1.0
Class=0 Prediction=0.0
in
world cinema
no apparent joy
Class=0 Prediction=0.0
Class 1 Prediction 1.0
skip
this
dreck
Figure 21: Explanation examples provided by the attacked SMGNN on the test set of SST2P. As described in Section 4, graphs present in the test split of SST2P are sensibly smaller than those of the train and validation splits, and are therefore OOD (Wu et al., 2022). As shown by the relevance scores below each token, the attack does not always generalize OOD: in three out of four cases, several nodes outside the designated explanation (c.f. Table 5) receive above-zero relevance, which penalizes the Fi score of Table 2. Nonetheless, "" and "" consistently receive near-maximum scores, while the true tokens used by the model are sensibly assigned lower relevance, meaning the attack still succeeded in suppressing the relevance truly important tokens.
49


Reviews:
[{"review_id": "QkUDmlZUFK", "reviewer": "Reviewer_UuzW", "summary": "This paper raise a possible explanation for self-explainable GNN(SE-GNN)'s unfaithfulness, that the explanation extractor may extract subgraphs with bijective mapping to the real groundtruth explanation to achieve well classification performance, yet only providing no-related explanation subgraphs. The author validate this view by training a group of attacked models which are humanly controlled on specific false explanation, while achieving good classification performance. Based on such insights, the author further propose a new sample-based metric namely EST on evaluating unfaithful explanations of SE-GNNs, and validate its effectiveness through experiments on both good true-negative and near-zero false-negative.", "questions": "1. Would this raised faithful problem also happens in post-hoc explainer on raw GNN? I think this shift between original important patterns and patterns used for classification may also appears in raw GNN models, e.g., for a star graph it only recognizes the most high degree node.  And could this metric be also applicable for them?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**1.** This paper is well presented, which makes me enjoy reading it. The flow of questions raised, illustration of the problem, proper designed figures and complete experiments make the motivation and findings of the paper well expressed. \n\n**2.** The raised explanation for SE-GNN's unfaithfulness in Theorem 1 is interesting and convincing. It assumes that some common anchor nodes serves as a bridge between real pattern and classification attention is novel, which also makes sense to me. The example 1 on the with figure illustrated is also well designed, which is simple and obvious for understanding.\n\n**3.** The experiments are complete and sound, which support mostly all claims in the paper. To validate the existence of such problem the author provide (1) the attacked models' performance (Table 2), (2) attacked models' rejection rate (Table 3) and (3) natural models' rejection rate (Table 4), which show that such unfaithfulness could exist in normal performing mode and may be potential reason for unfaithfulness of natural model.  To validate the effectiveness of the proposed EST, both the well rejection ratio of attacked models (Table 3) and the near zero rejection rate for designated explanations (Table 10) are provided to show this EST is a reliable metric. The provided Figure 2 also aligns with the supposed sample amount requirement of EST and also shows its effectiveness. It's also good to see every experiment column in Table 4 is assigned with a illustration figure.", "weaknesses": "**1.** The design of the new metric is somewhat limited in novelty. The difference between the proposed metric and other metrics is mainly just  enlarging the choice range of samples, i.e., including both nodes and edges for randomness. This metric is designed to approximate all the subgraphs, however, just assumed as the sample amount increases they are equivalent, which may increase high complexity. While this may not be a critic point since evaluation complexity is not a so serious problem, and explanation subgraphs are usually small. \n\n**A minor typo**: Fig.2 UST may suppose to be EST", "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": "jJZwJ6xq6V", "reviewer": "Reviewer_65XR", "summary": "This paper identifies a critical failure mode in Self-Explainable Graph Neural Networks (SE-GNNs): they can produce degenerate explanations that are completely unrelated to how the model actually makes predictions, while still achieving optimal predictive performance. The authors theoretically prove that under mild conditions, SE-GNNs can output such unfaithful explanations (e.g., highlighting non-discriminative \"anchor set\" nodes) and still achieve optimal true risk. Empirically demonstrate that these explanations can be maliciously planted to hide the use of sensitive attributes and existing faithfulness metrics often fail to detect such unfaithful explanations.  The paper then propose a new faithfulness metric, EST (Extension Sufficiency Test), which more reliably flags degenerate explanations by testing all possible supergraphs of the explanation.", "questions": "1. Given that Yu et al. (2019) formally characterized degeneration in rationalization models (where explanations encode labels via trivial patterns) and proposed complement predictors as a solution, how is your Theorem 1 different beyond adapting notation to graphs? (here my question is about motivation and your novelty). Can you explicitly show what new theoretical insight SE-GNNs provide over the rationalization literature?\n\n2. You demonstrate a serious problem (degenerate explanations) and provide a detection metric (EST), but there is no empirically validated prevention strategy. Why other existing solutions from rationalization (complement predictors and shared encoders) or neuro-symbolic systems (like reasoning shortcut mitigation) don’t work for SE-GNNs?\n\n3. Your theorem requires hard explanation extractors ({0,1} or {r,1}) and single-node anchor sets, but most practical SE-GNNs use soft scores and more complex patterns. How restrictive are these assumptions?\n\n4. On the discussions with relevant work\n\n- RQ1: On the Brittleness of Explanations & Malicious Manipulation (RQ1) \n\nConnection to Ref [A] (Li et al., ICML'24): The work shows explanations can be maliciously planted. Ref [A] demonstrates that GNN explanations are fragile, meaning small perturbations to the graph structure can drastically alter the explanation. This suggests that the problem of unreliable explanations is even more widespread: they can be not only deliberately fabricated but also easily and unintentionally broken. \n\nHow does the phenomenon of maliciously planted degenerate explanations (your work) relate to the general brittleness of explanations under minor structural perturbations (Ref [A])? Could the attack you propose be seen as a structured, large-scale exploitation of this inherent fragility?\n\n\n- RQ2: On Causal Metrics for Faithfulness\n\nConnection to Ref [B] (Behnam et al., ECCV'24): The work shows existing faithfulness metrics fail. Ref [B] proposes a causal-effect-based metric, arguing that it is less susceptible to spurious correlations and can more reliably capture the true reasoning of the model. This presents a directly relevant alternative to your proposed EST metric.\n\nHow does your proposed EST metric compare to causal-effect-based metrics like the one in Ref [B]? Could a causal framework provide a more principled foundation for defining and measuring faithfulness, potentially avoiding the need for the perturbation-based approach of EST? Please discuss the potential advantages and limitations of both perturbation-based and causal-based faithfulness metrics in the context of your findings.\n\n- RQ3: On Provably Robust Explanations\n\nConnection to Ref [C] (Li et al., ICLR'25): The work identifies a problem (degenerate explanations), and Ref [C] offers a potential solution for a related issue. Ref [C] aims to build SE-GNNs whose explanations are provably robust to graph perturbations, ensuring consistency. While their goal is robustness against adversarial graph perturbations, the underlying principle—enforcing stability in the explanation—might also prevent the model from latching onto arbitrary, degenerate subgraphs.\n\nCould the techniques for building provably robust explanations (Ref [C]) be adapted or extended to formally prevent the emergence of degenerate explanations identified in your Theorem 1? In other words, can robustness constraints guide the model toward explanations that are not only stable but also inherently faithful?\n\n[A] Li et al. Graph Neural Network Explanations are Fragile. ICML’24\n\n[B] Behnam et al. Graph Neural Network Causal Explanation via Neural Causal Models. ECCV’24\n\n[C] Li et al. PROVABLY ROBUST EXPLAINABLE GRAPH NEURAL NETWORKS AGAINST GRAPH PERTURBATION ATTACKS. ICLR’25\n\n**I would consider raising the score if the questions are sufficiently addressed during the rebuttal**", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Identifies a fundamental failure mode with serious implications for trustworthy AI in graph domains. The insight that explanations can serve as label-encoding channels is important for SE-GNN practitioners.\n\n2. Theorem 1 formalizes when optimal risk coincides with degenerate expla- nations for SE-GNNs. The proof technique (constructing explicit e and g pairs) is interesting. Extension to Theorem 2 connecting EST with formal explanation notions strengthens the contribution.\n\n3. Empirical validation on multiple datasets (synthetic RBGV, real-world MUTAG/MNISTsp/SST2P) and multiple architectures spanning different SE-GNN families in both adversarial (Section 4) and natural (Section 6) settings.", "weaknesses": "1. Theorem 1 requires hard explanation extractors, excluding soft/continuous scores common in practice, and it assumes |R| > 0, which limits generality. Also, the anchor set definition (single-node subgraphs in all graphs) is restrictive (in the discussion, it mentions generalizations but no formal treatment)\n\n2. Attack requires training access (strong assumption), though authors acknowledge this fits MLaaS scenarios. The stopping criteria (appendix D.1.2) are manually tuned per dataset which is unclear how to set these systematically. Also, tere is insufficient analysis of when/why attacks fail for Table 2.\n\n3. Fail to cite and discuss closely relevant recent works [A-C] (see questions)", "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": "U6ydyRhCHm", "reviewer": "Reviewer_BGhT", "summary": "While GNNs have received much research attentions, explanations on GNNs are becoming important. There are in general two families of studies on GNN explainations: (1) post-hoc explanations, and (2) self-explainable GNNs. This paper focuses on the latter one, and the authors made three important contributions: (1) they indicate that even self-explainable GNNs cannot be trusted. They show both therectially and empirically that the explanations (in the form of nodes, edges, attributes, or subgraphs) given by such self-explainable GNNs could be different from the real elements that lead to the prediction. In other words, this could be a misalignment between the explanations and predictions; (2) they show that such misalignments could be manipulated by attackers, and they can also arise naturally; (3) they show that existing faithfulness metrics often fail to capture such misalignments, and they propose a new metric to mitigate such issues. Overall, I think this paper is in good quality, ready for publication.", "questions": "No questions, please see the week points.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The probelm is well defined;\n\n(2) The paper is well organised;\n\n(3) Most statements/claims are supported empirically with experiments;\n\n(4) This paper provides strong insights on limitations of exitsing self-explainable GNNs;", "weaknesses": "(1) The theoretical analysis focuses on using isolation nodes as explanations, which may not be practical; as far as I know, most GNN explataions provide subgraphs (rather than isolated nodes) as explanations;\n\n(2) This paper focuses on class classification, and node classification is not discussed;", "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)