Redundancy Undermines the Trustworthiness of Self-Interpretable GNNs
Authors: Wenxin Tai
Ting Zhong
Goce Trajcevski
Fan Zhou
Venue: ICML 2025 poster (2025)
Keywords: Self-interpretble GNNs; Trustworthy; Consistency
Primary area: deep_learning->graph_neural_networks
TL;DR: We show that explanations from graph neural networks can be inconsistent and redundant, and we propose a simple ensemble method to make them more trustworthy.

Abstract: This work presents a systematic investigation into the trustworthiness of explanations generated by self-interpretable graph neural networks (GNNs), revealing why models trained with different random seeds yield inconsistent explanations. We identify redundancy—resulting from weak conciseness constraints—as the root cause of both explanation inconsistency and its associated inaccuracy, ultimately hindering user trust and limiting GNN deployment in high-stakes applications. Our analysis demonstrates that redundancy is difficult to eliminate; however, a simple ensemble strategy can mitigate its detrimental effects. We validate our findings through extensive experiments across diverse datasets, model architectures, and self-interpretable GNN frameworks, providing a benchmark to guide future research on addressing redundancy and advancing GNN deployment in critical domains. Our code is available at \url{https://github.com/ICDM-UESTC/TrustworthyExplanation}.

Redundancy Undermines the Trustworthiness of Seff-Interpretable GNNs
Wenxin Tai
Ting Zhong'
Goce Trajcevski? 2 Fan Zhou'
Abstract
This work presents systematic investigation into the trustworthiness of explanations generated by
self-interpretable graph neural networks (GNNs), revealing why models trained with different ran- dom seeds yield inconsistent explanations. We identify
Run 1: ACC 1.00 AUG 0.63
Rin AGC 1.00 0.C
Ground Truth
Figure 1: Illustration of explanation inconsistency models for molecular structure detection and impactful components. Darker colors indicate higher weights.
from weak con- ciseness constraints-an the root cause of both explanation inconsistency and associated inac- curacy, ultimately hindering user trust and limit- ing GNN deployment in high-stakes applications. Our analysis demonstrates that redundancy is dif- ficult to eliminate; however, a simple ensemble strategy can mitigate its detrimental effects. We validate our findings through extensive experi- ments across diverse datasets, model architectures, and self-interpretable GNN frameworks, provid- ing benchmark to guide future research ad- dressing redundancy and advancing GNN deploy- ment in critical domains. Our code is available at https: /ggttbb./////bt////g//pp com/ ICDM- UESTC/ TrustworthhExxpanatt..
As result, a variety of GNN explanation methods have been developed in recent years. Some researchers focus on post- hoc methods, which interpret pre-trained GNNs using auxil- iary models (Ying et al., 2019; Luo et al., 2020) or tailored strategies (Yuan et al., 2021; Chen et al., 2024b). While flexible and broadly applicable, these methods are sensitive to model initialization (Miao al., 2022) and are affected by distribution shift (Hooker et al., 2019; Zhang et al., 2023) and, some researchers argue, may not accurately represent the true decision decision-making logic of the target GNN (Rudin, 2019; Ragodos et al., 2024). Such challenges have spurred a growing interest in self-interpretabbe GNNs (Lin et al., 2020; Dai Wang, 2021; Miao et al., 2022; Sui et al., 2022; Deng & Shen, 2024) which, by design, jointly learn explanations and predictions.
1. Introduction
Graph neural networks (GNNs) have emerged powerful paradigm for learning representations on copph-srrutture data, serving plethora of applications from social network analysis (Wu et al., 2022a) to molecular structure identifi- cation (Wang et al., 2022). However, notwithstanding their remarkable success, the inner workings of GNNs remain largely inscrutable. This, in turn, presents a significant bar- rier to their widespread adoption, especially in high-stakes domains (e.g., healthcare (Pfeifer al., 2022), molecular dynamics (Quesado et al., 2024), finance (Rajput & Singh, 2022) and cybersecurity (Warmsley et al., 2022)) where explainability is not an option but a stringent requirement.
Given the critical need for explainability in high-stakes ap- plications, self- -nterrrterpeeeable GNNs appear to offer a com- pelling solution. But do they truly live up to expectations? Motivated by experiments from (Ying et al., 2019; Zhao et al., 2023b), Figure shows an example from our experi- ments from the domain of molecular chemistry. The left and middle portions illustrate the outcome of two runs of models trained in different random seeds aiming to detect benzene rings. Although both have same predictive accuracy (100% accuracy in detecting benzene rings), they show inconsistent explanations. Worse still, "Run 1" assigns higher weights (0.997-0.999) to an irrelevant three-membered ring as op- posed to the benzene ring (0.991). Such inconsistencies and explanation- -nnacucrcnis can yield misleading interpreta- tions that can have dire ramifications on decision-making and affect users' trust in the practical applicability of self- interpretable GNNs.
'Department of Software Engineering, University of Electronic Science and Technology of China, China Department of Electrical and Computer Engineering, lowa State University, United States. Correspondence to: Fan Zhou wff.n.hoouuusstc.dduu
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Through systematic investigation, we identify Redundancy as the underlying cause: self-interpretable GNNs success-

---

Redundancy Undermines the Trustworthiness of Self- Self-Interpretable GNNs
fully identify those key features but also overemphasize some irrelevant ones. We argue that hyperparameters used to enforce explanation conciseness are set overly relaxed, granting the model excessive flexibility to retain irrelevant features, thus weakening the trustworthiness of GNN ex- planations. Through theoretical analysis and experiments, we show that redundancy is inherently difficult to eliminate. Existing techniques (Madhyastha & Jain, 2019; Zhao al., 2023a; Deng & Shen, 2024), despite promising results in other related fields, fail to address this challenge.
ates the prediction Y to approximate Y.
Self- Seeff-Ittepretable GNNs. To enhance the interpretability of GNNs, current explanation methods aim to illuminate the model's decision- process by identifying a concise yet crucial set of features within the graph. Therefore, a self- interpretable GNN can be represented as f = hy o ho.. and the optimization objective is formalized as:
max G,E.JGG.IIK
T(Gs; Y)
(1)
While a complete solution to eliminating redundancy re- mains an open challenge, we find that a simple, tuning-free -ortggy--xplaatttion Ensemble (EE) can significantly mitigate its adverse effects. By aggregating explanations from multiple independently trained models, EE retains the signal of truly relevant features while suppressing the noise from irrelevant ones, leading to more consistent and accurate explanations. Extensive experiments across diverse datasets, model architectures, and self-interpretable GNN frameworks validate the effectiveness of EE.
where G, G., and Y represent the graph, its subset, and the graph label, respectively. The goal is to maximize the mutual information (MI) between the graph subset and the label while controlling the size (K) of the subset. Along the lines of prevalent graph explanation efforts (Amara et al., 2022; Chen et al., 2023), we focus on the contribution of the structural features, namely the edges.
2.2. Taxonomy of Self-Interpretable GNNs
We classify existing self-interpretable GNNs into four types based on their design principles.
In sum, we present a systematic investigation into the trust- worthiness of explanations generated by self-interpretable GNNs. Our central contribution is identifying redundancy as a fundamental cause of explanation inconsistency and inaccuracy. To address this, we introduce EE as both prac- tical mitigation strategy and a benchmark for future research.
Type I (Attention). The attention mechanism, introduced in Vaswani et al. (2017), is an early method for understand- ing how NNs make decisions. works by assigning dif- ferent levels of importance to different features. Attention- based ieferrnttrreee GNNs take advantage of this built-in ability to learn which edges are most important during train- ing. This happens without the need for any extra rules or penalties (loss constraints) to force the model to explain itself (Velickovic et al., 2018):
We hope our findings will encourage the development of more principled, theoretically grounded approaches. paving the way for the safe and effective deployment of GNNs in high-stakes applications.
2. Preliminaries
LGE = (ET,YYYIG.)
(2)
We begin by formally defining graphs and GNNs. Following this, we define self-interpretable GNNs and classify existing methods into four types based on their design principles.
where LCF is classification loss (e.g., cross-entropy loss).
Type 11 (Causal Learning). Some works approach GNN interpretability from a causal perspective, aiming at learning truly causal patterns that go beyond pure spuriosity-prone statistical correlation (Wu et al., 2022b). Techniques such as disentanglement and causal intervention are often used to optimize the learning process (Sui et al., 2022):
2.1. Basic Definitions
Graph. A graph G is a quadruplet (V, E, E,E, A). where V [e1, 02 .2.....y uy? } is the set of nodes, E S V V is the set of edges, X R.Ndd is the feature matrix where each row represents the feature vector of a node, and A E {0, 1 J]NX is the adjacency matrix, where A.j 1 if there is an edge between nodes ii and By. and 0 otherwise.
LGE LCE(YY + 8 DKL (P
+ + Lce(
(3)
where 33 and 7 are pre-defined hyperparameters, G, G G, the complement of G., and G², represents the result of intervening on G, (e.g., shuffling the edge weights of G.). Q(Y) is often set to a uniform distribution.
Graph Neural Network (GNN). GNN (Scarselli et al., 2008) is type of a neural network designed to operate on graph-structured data, making it particularly well-suited for tasks where understanding relationships between entities is crucial. Taking the graph classification task as example, we structure the GNN as combination of two modules: f == h2 o hz. In this context, the module hz (G + Rd) learns the graph representation, while by (R + R) gener-
Type III (Size Constraint). To encourage more concise and human- uaman-understandable explanations, some works ex- tend attention based methods by adding regularization terms that constrain the size of G.- A representative example is
2

---

Redundancy Undermines the Trustworthiness of Self- Self-Interpretable GNNs
20
23
8.55
645
0.5
0.23
6.85
085
05
03
0.7
025
033
0.45
635
000
0.55
305
8.6
05
(a) Important (Type I)
(b) Important (Type II)
(c) Important (Type III)
(d) Important (Type IV)
ASS 2/6 625 C41
6:5 ASS 0AS
6/6 836 036
315 125
(c) Unimportant (Type I)
(f) Unimportant (Type II)
(g) Unimportant (Type IIII
(h) Unimportant (Type IV)
Figure 2: Histograms of edge weights trained on the BA-2MOTIFS dataset. The first row shows the distribution of edge weights assigned truly important edges, while the second row shows those assigned to unimportant edges. The vertical axis represents the epoch numbers. Histograms for other datasets are provided in Appendix B.
Lin et al. (2020), which introduces a sparsity loss that nor- malizes the constraint by dividing it by the graph size:
model performance, which in turn can manifest as variation in the generated explanations. To mitigate this issue, Mad- hyastha Jain (2019) adopted Stochastic Weight Averaging (SWA) (Izmailov et al., 2018) and its variants, which stabi- lize training by averaging weights collected from different points along the optimization trajectory. This approach en- courages convergence to flatter optima, thereby improving explanation consistency.
|Gal GG]
LGE CCB Y +
(4)
Type IV (MI Constraint). Some works constrain the size of G, from an MI perspective, encouraging concise expla- nations by minimizing MI between G, and G. One work (Yu et al., 2021) uses a computationally expensive technique (Belghazi al., 2018) to estimate MI, while the other (Miao al., 2022) adopts tractable variational upper bound:
investigate whether training instability leads to expla- nation inconsistency in self-interpretable GNNs, we apply SWA four self-interpretable GNN frameworks across four datasets. Our experimental results (cf. Table 1) show that SWA improves explanation consistency in only 7 out of 16 tests. This suggests that while training instability may con- tribute to explanation inconsistency, it does not fully explain the phenomenon in self-interprettall GNNs.
LGB LY ().)) + + 3. DKL (Po(GG (5)
where Q(G,)) a Bernoulli distribution. Since the sampling process is non-differentiable, Gunbel-Softmax trick (Jang
et al., 2017) is employed for continuous relaxation.
3.2. Spurious Correlations
3. Inconsistency Investigation
Spurious correlations have been identified as a key contrib- utor to explanation inconsistency in post-hoc GNN meth- ods (Zhao et al., 2023a;b). Their works argue that when the explainer is optimized solely based on predicted out- puts-e.ge e.g., by training it to generate subgraphs whose pre- dictions align with those of raw graphs- it becomes prone to overfitting spurious patterns: features correlated with the output but not causally informative. This vulnerability stems from the two-stage pipeline, where the explainer is trained separately to mimic the behavior of a pre-trained GNN and lacks access to its training dynamics and inductive biases. Depending on initialization and optimization dynamics, the explainer may attend to different features across runs, some- times capturing truly relevant ones and other times latching onto spurious cues. Such instability results in explanation
We begin by examining two commonly presumed sources of explanations inconsistency-()) training instability (Mad- hyastha & Jain, 2019), and (2) spurious correlations (Zhao et al., 2023a;b) both of which have been studied con- tributing factors in previous literature.
3.1. Training Instability
Training instability has been identified as key contribu- tor to explanation inconsistency in attention-based NNs for NLP tasks (Madhyastha & Jain, 2019). Their work sug- gests that the inherent complexity of non-convex loss sur- faces characterized by numerous saddle points and local minima- hampers stable training, resulting inconsistent
3

---

Redundancy Undermines the Trustworthiness of Self- Self-Interpretable GNNS
inconsistency across random seeds.
GNN explanation G should satisfy: (1) Sufficiency, mean- ing the explanation must preserve all critical information required for accurate prediction; and (2) Necessity, meaning the removal of any edge in G. would impair the model's prediction due to loss of crucial information.
To examine whether spurious correlations underlic ex- planation inconsistency in self-interpretable GNNs, we conduct experiments on several benchmark datasets. As shown in Figure (a)-(d), when evaluated on synthetic datasets without deliberately introduced spurious patterns, self- -nterpetereee GNNs consistently assign high weights to truly important edges, indicating strong robustness to spuri- ous correlations. This likely stems from the nature of expla- nation generation: unlike post-hoc methods, which mimic the behavior of pre-trained GNNs and are thus susceptible to optimization bias (Miao et al., 2022) and confounding effects ( (Wu et al., 2022b), -nterpetereeeeale GNNs learn ex- planations jointly with predictions, embedding them directly into the model's decision-making process.
To enforce these properties, the authors introduced an aux- iliary contrastive loss. Given a generated explanation G2 (serving as the anchor), they constructed two variants: (1) a positive sample G obtained by adding edges to G, such that it still contains sufficient information for accurate pre- diction: and (2) negative sample G obtained by remov- ing essential edges, thereby disrupting critical substructures and causing the GNN to fail in making correct predictions. The contrastive loss is formulated as!:
exp (sim(2,, 2T)
Lcr. - -log
exp (sim(2.. 27 //T + exp (sim(2,, 25 )/T)
4. Redundancy in Explanation
where 2g 27. and 2. denote the projected representations of Gs, G and G respectively; for example, 2, is ob- tained by applying an MLP to 2., i.e., 2, - MLP(z.). The function sim(..) denotes cosine similarity, and T is tem- perature hyperparameter. This loss encourages maximizing the similarity between the representations of G2 and G while minimizing that between G, and G. As result, the model learns to generate concise and meaningful explana- tions that satisfy both sufficiency and necessity, reducing redundancy without sacrificing predictive power.
Figure 2 (e)-(h) suggests another source of explanation in- consistency in intfrinteeeeetaable GNNs: redundancy. When trained with different random seeds, models consistently identify key features but vary in their inclusion of irrelevant ones, leading inconsistent explanations. We attribute this redundancy to the limitations of global hyperparameters in enforcing conciseness. Given the varying graph sizes and explanation sizes across instances, fixed hyperparame- ter values are rarely optimal, allowing the model excessive flexibility to retain redundant edges.
However, is important to note that the efficacy of the above strategy relies on a restrictive assumption: for each graph G, the optimal explanation G should simultaneously satisfy sufficiency and necessity. In practice, this assumption is often unattainable. For instance, in datasets like BENZENE (Morris et al., 2020), where graphs are labeled to indicate the presence of one or more benzene rings, each inndpne- dent explanation (i.e., each benzene ring) constitutes a valid explanation. In such cases, sufficiency and necessity repre- sent inherently conflicting criteria: prioritizing sufficiency leads to retaining all benzene rings, whereas emphasizing necessity discards alternative valid substructures, as single benzene ring suffices to explain the graph. This conflict can be formalized as follows:
The suboptimality of global hyperparameters is further il- lustrated in Figure 3, where histograms of [Gal/|]| show that the generated explanations consistently include more edges than the ground-truth ones. This behavior is expected: in the absence of ground-truth explanations in real-world scenarios, hyperparameters are empirically tuned to balance classification accuracy and explanation conciseness. In our experiments, retaining more edges stabilizes training and improves classification performance. This also aligns with recent findings (Wu et al., 2022b; Miao et al., 2022), which recommend retaining 50%-80% of edges to achieve a favor- able trade-off. To formalize the notion of redundancy, we establish a connection to explanation budgets as follows: Proposition 4.1. Define the crucial graph subset as the optimal GNN explanation G*. When K 2 [G)), there exist 21 valid GNN explanations that can satisfy Equation (1).
Proposition 4.2. Assume that G has multiple independent explanations G² = (GG,,,, G?:"..... Gm,²t) with pairwise disjoint edge sets. Then, no single edge strictly necessary.
The proof is provided in Appendix A. As discussed above, because the true size of graph explanations is unknown in practice, designing size-specific loss objectives to directly address redundancy is challenging.
The proof is provided in Appendix A. To investigate the prac- tical implications, we conduct experiments on two datasets: BA-2MOTIFS (Luo et al., 2020) and BENZENE (Sanchez- Lengeling et al., 2020), which exemplify engle-explanattio and multi-explanation scenarios, respectively.
Instead of explicitly targeting explanation size, recent work (Deng& & Shen, 2024) adopted contrastive learning (Oord et al., 2018) as an indirect strategy to eliminate redundancy. Their method is grounded in two key properties that an ideal
Our quantitative results (see Table 2 in Appendix D) confirm
We use one positive and one negative sample for simplicity.
4

---

Redundancy Undermines the Trustworthiness of Belf-Interpretalle GNNs
45
B
==0
O
45
g ==1
45
[ = 0.01
45
B 8=1
Density
GT
Density
B 10
Density
β 0.1
Density
8=
30
30
30
30
GT
GT
15
15
15
GT
15
0
0
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
Ratio
Ratio
Ratio
Ratio
(a) Type
(h) Type
(c) Type III
(d) Type IV
Figure 3: Histograms of / on the BA-2MOTIFS dataset. GT refers Ground Truth. Only results from settings that successfully converge shown. Histograms for other datasets are provided in Appendix C.
the theoretical insights presented above. Specifically, on the BA-2MOTIFS dataset, incorporating contrastive loss re- duces explanation inconsistency and improves accuracy, the removal of necessary edges directly disrupts the unique explanation. In contrast, on the BENZENE dataset, removal of certain edges does not invalidate the remaining expla- nations. Consequently, both positive and negative samples retain sufficient information for accurate predictions, result- ing ambiguity that leads to degraded performance across all metrics due to convergence difficulties. These findings highlight the need for broadly applicable methods that do not rely on restrictive dataset-specifer assumptions.
inconsistency can viewed as the average inconsistency of its constituent edges.
To formally analyze the effectiveness of EE in improving explanation accuracy, we present the following proposition:
Proposition 5.2. Let X and W be independent random variables with X E [0, 1] and W E [8, 1], where 0 << 6 S 1. Let X be the sample mean of n independent observations of X. E[ < 6, then we have:
IP(X W)
exp(- B[())²)
(7)
The proof is provided in Appendix A. Let X and W de- note the importance scores an irrelevant and a relevant edge, respectively, where E [O, 1] and W E [8, 1] with 8 S 12. Proposition 5.2 demonstrates that aggre- gating explanations from n independently trained models, yielding the average importance score X for the irrelevant edge, increases a lower bound on the probability of cor- rectly distinguishing irrelevant edges from relevant ones (i.e., P(X < W)). This increased probability directly con- tributes to a higher ROC-AUC score, a key metric for evalu- ating explanation accuracy (Ying et al., 2019).
5. Explanation Ensemble
In this section, we demonstrate that simple Explanation En- semble (EE), which aggregates explanations from multiple independently trained models, can effectively alleviate the detrimental effects of explanation redundancy. To formally analyze the effectiveness of EE in reducing explanation inconsistency, we present the following proposition:
Proposition 5.1. Let X be a random variable with [[[] and (Xr(X) b, where X [0, [0, Let x1, 22 be in- dependent draws from X, and let X2, X2 be the sample means of two independent n-samples from X. For positive
From a more intuitive perspective, the explanation generated by self seff-interpretable GNN can be viewed as consisting of two components: (1) edges that the model genuinely deems important, and (2) edges that are assigned high importance just because sufficient budget allocation (redundancy). EE can improve explanation consistency and accuracy, as these redundant edges typically exhibit high variance and tend to receive lower average importance after aggregation.
hyperparameter l E (0, 1). we have:
2b
P(|Xi - Xx2 < kb 1|1 - x22)
(6)
nk x1
T2
The proof is provided in Appendix A. In self-interpretable GNNs, X represents the importance score (ranging from 0 to 1) assigned to an edge, reflecting its contribution to the model's prediction. The inconsistency in edge importance between two models quantified by |x] - x2). where xi and 22 are the importance scores assigned to the same edge. Proposition 5.1 shows that by aggregating explanations from independently trained models (forming two ensembles with average importance scores Xi and X2), the probability that the ensemble inconsistency |X, - X21 is less than k times the individual model inconsistency |-, - x2l has a lower bound that increases with n. Note that the above edge- level analysis readily extends to subgraphs, as graph-level
6. Experiments
Metrics. To evaluate explanation consistency, we follow Zhao et al. (2023a;b), run each method multiple times with different random seeds and report the average Structural Hamming Distance (SHD) (Tsamardinos et al., 2006) across the generated explanations. SHD quantifies the structural differences between two graphs by counting mismatched
We assume that truly important edges are assigned high impor- tance scores, an assumption supported hy our earlier investigations.
5

---

Redundancy Undermines the Trustworthiness of Self- Self-rnntepretable GNNs
Table 1: We run each method 10 times, reporting the mean and standard deviation. Results significantly outperforming the baseline x (GIN, paired t-test, p < 0.05) are underlined. Values in brackets show performance changes after Explanation Ensemble. Dark green indicates performance improvement, while dark red indicates performance degeneration.
METHOD
METRIC
STRATEGY
BA-2MOTIFS
3MR
BENZENE
MUTAGENICITY
4.75++4.68 (1.3.53)
5.59+ (L 2.68)
6.11+-4.44 3.21)
5.02+6660 (1 4.99)
SHD
+SWA
12.07:18.21 (L 1.81)
4.27+ (J 2.34)
7.42:14.61
2.55)
11.24:16.18 (1 5.64)
+EA
4.04+3380 2.49)
9.79=6.56 () 5.04)
2.01=2.63
1.96)
9.63=14.37 (1 9.10)
99.30-10344 0.31)
97.25:10.66 1.27)
83.50:12.23
7.44)
91.71=16.00 (1 6.25)
Type I (Attention)
AUC (%)
+SWA
99.03=00336 (1 0.11)
97.81+0.113 (1 0.73)
1..78 (1 4.26)
98.57=00.44 (1 0.66)
+EA
97.73.1141 (1 1.31)
97.86.10.75 (1 1.30)
88.61 13.76 (1 5.11)
97.19133.99 (1 2.23)
X
97.10+8.700 (1 2.90)
06.53-+1.445 (1 0.70)
91 60.60+0066666 (1 1.15)
92.97+00.88 (1 0.94)
ACC (%)
+SWA
98.20.11.53 (1 0.80)
95.32.10.99 (1 0.87)
89.63.12.02 (? 1.20)
89.59.11.53 (1 0.61)
+EA
100.00+00.00 (0.00)
97.99++0.70 (1 1.31)
90.71 (1 0.70)
90.33++1.13 (1 1.89)
X
7.75+5..11 11 3,51)
3.92=2,79 (L 2.98)
9.17=5.79 (L 4.07)
19,57=14.49 (1 10.44)
SHD
+SWA
11.29.17.58 (1 6.59)
4.01 22.60 (L 1.97)
9.02.15.72 (1 4.71)
12.6011.21 (L 4.88)
+EA
7.5919.63 (1 7.57)
9.2411483 (L 3.85)
4.14 () 2.49)
19.11 (1 10.45)
X
98.63-11.33 (1 0.99)
96.24:1: 1.58 (1 2.08)
77.64:1..05 (1 8,20)
96.39: 1.38 (1 2.83)
Type II (Causal Learning)
AUC (%)
+SWA
15 (1 2.72)
06.50++0.31 (1 1,48)
78.80+2.99 (* 5.66)
98.32++0.40 (1 0.98)
+FA
96.56+1.95 1.95 (1 2.68)
1.54 (1 2.08)
83.69+4.02 (.13)
3..56+ (1 3.35)
x
91.89 68 (1 6.11)
94.22:1.. 10 (1 1.97)
84.30:1:5.65 (1 3,28)
91.21 1.36 (1 1.01)
ACC
+SWA
81.30.1 10 (1 9.70)
93. 1,48 (1 1.07)
84.33.1..84 (? 2.50)
89.05 10089 (L 0.54)
+EA
99.90=10.00 (1 0.10)
97.30+1:1.35 (1 0.94)
87.83-11.18 (? 1.33)
89.93-10.92 (1 0.27)
X
11.41 (L 6.93)
3,50=22.44 (L 1.82)
6.91=4.48 () 2.47)
4.97 (L 2.40)
SHD
+SWA
11.8418.57 (L 2.85)
3,85.12,43 (L 1.90)
7.58 (1 4.59)
7.23.14.13 (L 3.78)
+EA
9.6411.66 (1 7.47)
7.1714.09 (1 3.17)
16.3419.80 (J 2.15)
15.17-1.86 (L 4.22)
99.32.10.36 (1 0.35)
96. 16.99 16.99100.76 (1 1.43)
84.38 (? 8.09)
98.11 (1 1.01)
Type III
AUC (%)
+SWA
99.19-0033 (f 0.09)
97.60++0222 (1 0.81)
85.67+22.02 5.16)
98.16:+0.43 (1 1.12)
(Size Constraint)
+EA
96.54-t4.43 1.93)
9..04++.37 (1 2.13)
85.72+5.35 (1 7.27)
97.96++0.77 (1 1.47)
95.50= (1 4.50)
97.30+ (1 0.62)
91.11=0.62 (* 1.22)
89.52:+0.99 (1 1.69)
ACC (%)
+SWA
97.10-12.66 (1 0.90)
94.25 (1 1.25)
88.2413.33 (? 1.34)
88.51111.00 (1 0.34)
+EA
99.80=0040 0.20)
97.43+0.72 (1 1.53)
1..23 (1 1,93)
89,22:10991 (1 1.32)
3.29-+2.97 97 (L 1.74)
7.71=5.51 (L 3.69)
4.13=3.15 (L 2.50)
13.30 10.29 (1 7.17)
SHD
+SWA
1.77 (1 0.65)
4.97+ (L 2.95)
3.81+3398 2.90)
0.14+0.24 (1 0.14)
+EA
0.54+1108 (1 0.54)
3.49 (L 186)
6.73=6.29 3.45)
17.02418.09 18.09 9.31)
98.44110.60 (f 0.32)
98.37.10.11 (1 0.80)
90.66 88 (1 2.00)
99.00.10.30 (1 0.39)
Type IV (MI Constraint)
AUC (%)
+SWA
98.53-1.25 (1 0.06)
98.97.00.00 10 0.29)
10.10010.30 39 (? 1.14)
99.0711031 (1 0.29)
+EA
96.89+1.67 1.54)
98.74:10.22
0.52)
92.40-10.86 (? 1.88)
99.23-1-.23 (1 0.26)
100.00+:0000 (0.00)
98.54++0.800 (1 0.76)
0..48 (1 0.85)
92.43+1.00 (f 0.13)
ACC (%)
+SWA
100.00++0.00 (0.00)
13. (1 0.83)
91.48++0.49 (? 0.93)
91.38++0.94 (1 0.84)
+EA
99.60=0.66 0.40)
97.92++0.84 (1 0.34)
88. 88.80=0.39 ( 0.05)
1. (1 1.22)
edges (either missing or extra edges). Since NNs output continuous soft edge weights, these must first be discretized
2MOTIFS (Luo et al., 2020), and three real-world dataset -MR (Rao et al., 2022), BENZENE SSanchez-Lengeling
to compute SHD. A threshold of 0.5 used in this study:
et al., 2020), and MUTAGENICITY (Debnath et al., 1991) all sourced from the graph learning community and have ground-truth explanation labels.A detailed discussion the choice of metrics and datasets is provided in Appendix E.
edges with weight greater than 0.5 are considered present,
while those below 0.5 are deemed absent?. To evaluate ex- planation accuracy, we choose datasets with ground-truth explanations, as they provide objective benchmarks for com- parison (Chen et al., 2024a). Following established practices (Wu et al., 2022b; Miao et al., 2022), we use ROC-AUC (AUC) to evaluate explanation quality and Accuracy (ACC) to evaluate predictive performance.
Baselines. To ensure fair, reliable, and comprehensive ex- periments, we evaluate two GNN backbones, GIN (Xu et al., 2019) and GCN (Kipf & Welling, 2017), alongside four types of seff-interpretable GNN methods: Type I to Type IV. Due space limitations, GIN results are presented in the main paper, with GCN results in Appendix F.
Datasets. We select four datasets: synthetic dataset, BA-
'e chose a threshold of 0.5 because determining whether an edge is important is essentially a binary classification task, and 0.5 is a standard and freer-free choice. In contrast, other threshalds or Top-K selections all require domain knowledge.
+SWA: Madhyastha & Jain (2019) introduced SWA to ad- dress attention inconsistency. To investigate whether train- ing instability contributes to explanation inconsistency of self-interpretable GNNs, we use SWA as a bascline.
6

---

Redundancy Undermines the Trustworthiness of Self- Beff-Interpretable GNNS
Case
ADD 1:22 AUG
Grsund
AUC (%)
Case
Riso ADD CO AUCCIO4
PuiTt: ADD 1/3 0.2
Pun.7 AOC LO AUD
RaKi ACD 1:0 AUGIO
Puxn:: ADC 1O0 AUG
.FP AGG 1:: AUGOS
Ground
AUC (%): 78.46 94.87
B.nS ACC 25 C30
P: ADC LOS RUC
R. ACC 1.0 AUC Cuta
RaRE: ACC L:S AUC 0.22
Pu ADC 1O0 AUI 0:94
Figure 4: Illustration of Explanation Ensemble. Darker colors indicate higher weights. Only edges with weights greater than 0.5 are highlighted, they collectively form the explanations.
+EA: Zhao et al. (2023a;b) argued that optimization solely based on predicted labels can casily lead to overfitting to spurious correlations. To address this, they proposed several alignment-based loss objectives enhance semantic consis- tency between graphs and identified subgraphs in the embedding space. An example implementation employs the Euclidean absolute distance to align graph representations. Formally, let z and n, denote the pooled embeddings of the raw graph and the identified key graph subset, respectively. The embedding alignment (EA) loss is defined as:
tions. For example, on the BA-2MOTIFS dataset, it causes an AUC drop of up to 3% across all self-interpretable GNN frameworks. We attribute this to the difference in how the alignment loss operates in different settings. In post-hoc methods, the alignment loss is applied solely to the ex- plainer, which learns match the representation of a fixed, pre-trained GNN. Since the target representation remains unchanged across runs, this alignment directly promotes ex- planation consistency. contrast, self-interpretable GNNs train both explainer and the GNN jointly, and the loss influences both. As result, the explainer is constantly align- ing to moving target-itss its own co-evolving GNN- weakens the intended effect of enforcing consistency. (03): EE is the only approach that consistently improves explanation quality across all evaluated settings, reducing SHD and improving AUC in all 48 cases. Moreover, EE also improves downstream classification accuracy (ACC) in 46 out of 48 cases. The simplicity of EE and its indepen- dence from specific training procedures (unlike EA, which requires additional loss term, and SWA, which necessi- tates changes to the training regime) make it highly suitable for real-world applications.
LEA ||z 22112-
(8)
We use EA bascline. Additional details about experi- mental setup provided in Appendix G.
6.1. Overall Performance
Table reports the overall performance and we have the following observations:
(01): SWA does not consistently improve the quality of GNN explanations: it decreases SHD in approximately 44% of cases and increases AUC in around 63%. This result can be attributed to two factors. First, self-interpretable GNNs often train stably and converge to near-optimal solutions, leaving limited room for further gains. Second, averaging weights may pull the model away from sharp yet accurate optimum toward flatter but suboptimal region in the loss landscape. While flatter minima can sometimes improve generalization, they may also lead to less precise explana- tions, thereby reducing performance in some cases.
6.2. Case Study
While Table I provides a quantitative overview of EE's per- formance, we now present two case studies to qualitatively illustrate how EE impacts explanation accuracy (Figure 4).
In the first case, the average AUC of the initial explanations is 88.6 88.60%. After applying EE, the weights of irrelevant edges are effectively reduced, leading to perfect AUC of
(O2): EA also fails to improve the quality of GNN explana-

---

Redundancy Undermines the Trustworthiness of Self- Self-Inttepretable GNNs
99.50
99.30
92.00
99.80
AUC (%)
99.00
(%)
98.20
AUC (%)
89.00
LUC 990
96.80
Type
98.50
Type II
97.10
86.00
93.80
Type
Type IV
98.00
5.00
10.00
96.00
2.00
4.00
6.00
83.00
2X
1.00
4x
2.00
3.00
90.80
2.00
5.00
7.50
SHD
SHD
SHD
SHD
(a) BA-2MOTIFS
(b) 3MR
(c) BENZENE
(d) MUTAGENICITY
Figure 5: Trustworthiness (SHD and AUC) vs. Efficiency (1x, 2x, 3x, 4x, 5x) on four datasets.
100%. This demonstrates EE's ability to retain the signal of truly relevant features while suppressing the noise from irrelevant ones. In the second case, the average AUC of the initial explanations 78.46%. Applying EE substantially improves the AUC to 87%, with the weights most irrele- vant edges significantly reduced. However, a few irrelevant edges still retain relatively high weights because these edges consistently identified as important across all 10 models. This observation also aligns with our theoretical analysis in Proposition 5.2, which suggests that EE's effectiveness diminished when the weights of certain irrelevant edges remain consistently high.
(Luo et al., 2020; Lu et al., 2024; Luo et al., 2024). However, as GNNs are increasingly deployed in high-stakes domains, other critical properties such as robustness (Bajaj et al., 2021; Li et al., 2024; Fang et al., 2024), generalizability (Wu et al., 2022b; Miao et al., 2022; Azzolin et al., 2025), and fairness (Medda et al., 2024; Dong et al., 2022) have gained growing attention (Dai al., 2024).
Zhao et al. (2023a:b) took pivotal step in investigating the consistency of GNN explanations. They concluded that spu- rious correlations are the core reason behind inconsistency in post-hoc GNN explanation methods (Ying et al., 2019; 9;; Luo et al., 2020). Inspired by their work, we conduct an ex- tended investigation on celf-interpretable GNNs (Velickovic et al., 2018; Sui al., 2022; Miao et al., 2022; Deng & Shen, 2024), and find that explanation inconsistency persists even in the absence of spurious correlations. This observation motivates us to look beyond existing hypotheses, ultimately leading to the identification of redundancy soaundaacy--temminng stemming from the weak conciseness constraints as a core and previously underexplored reason for inconsistency.
Together, these two cases demonstrate EE's capability to improve explanation accuracy. Given its simplicity, empir- ical effectiveness, and theoretical foundation, we believe that EE can serve as a strong baseline for future research on trustworthy self-interpretable GNNs and may inspire the development of more principled solutions.
6.3. Efficiency-TTuustorthin Tradc-off
Although EE consistently improves explanation quality, its ensemble nature requires training multiple models, increas- ing training and deployment costs linearly with n. To investi- gate the relationship between trustworthiness and efficiency, we vary and plot the resulting SHD and AUC values. As shown in Figure 5, have the following two key ob- servations: (1) Increasing generally leads to improved performance across all metrics and datasets. (2) Most sig- nificant performance gain is observed when nt is increased from to 2. These findings suggest n = 2 as a practical choice in balaneing trustworthiness and efficiency. Another limitation of EE-it incompatibility with faithfulness met- rics-is discussed in Appendix H.
8. Conclusion & Future Work
In this work, we identify redundancy as a root cause of explanation inconsistency and its associated inaccuracy in self-interpretable GNNs. While existing methods struggle to eliminate this redundancy, we demonstrate that a simple, tuning- free ensemble strategy EE can substantially mitigate its negative effects, leading to more consistent and accu- rate explanations. Extensive experiments across diverse datasets, model architectures, and self- reff-interpretable GNN frameworks validate the effectiveness of EE.
We hope this work, which also serves as an evaluation study, will inspire researchers and practitioners to recognize ex- planation consistency as an indispensable criterion in the design and evaluation of self-interprettalee GNNs. Future research efforts involve moving beyond reactive strategies (such as EE) and prioritizing the development of proactive strategies that directly address redundancy during model training, enabling highly trustworthy GNN systems.
7. Related Work
A variety of methods have been proposed to explain GNN predictions, with most efforts focusing on improving expla- nation accuracy (Ying et al., 2019; Yuan et al.. 2021; Wang al., 2021; Dai & Wang, 2021) or computational efficiency
8

---

Redundancy Undermines the Trustworthiness of Self- Beff-Inttrpretable GNNS
Acknowledgements
Dai, E. and Wang. S. Towards self-explainable graph neural network. In Proceedings of the 30th ACM International Conference Information & Knowledge Management, pp. 302-311, 2021.
We thank Dr. Zeng Wang for her constructive discussions and valuable feedback. We also thank the anonymous re- viewers for their comments and suggestions. This work was supported in part by National Natural Science Foundation of China (Grant No.62176043 and No.62072077).
Dai, E., Zhao, T., Zhu, H., Xu, J., Guo, Z., Liu, H., Tang, J., and Wang. S. A comprehensive survey trustworthy graph neural networks: Privacy, robustness, fairesss, and explainability. Machine Intelligence Research, pp. 1-51, 2024.
Impact Statement
This work aims to enhance the trustworthiness of explana- tions produced by self-interpretable GNNs, aligning with the goals of responsible AI. We do not foresee any direct negative societal consequences and expect that work will support the safe deployment of GNNs in high-stakes domains such as healthcare and scientific discovery.
Debnath, A. K., Lopez de Compadre, R. L.., Debnath, G., Shusterman, A. J., and Hansch, C. Structure- activity rela- tionship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
References
Deng. J. and Shen, Y. Self-interpretable graph learning with sufficient and necessary explanations. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11749-11756, 2024.
Amara, K., Ying, Z., Zhang, Z., Han, Z., Zhao, Y., Shan, Y., Brandes, U., Schemm, S., and Zhang, C. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. Learning on Graphs Con- ference, pp. 44-1. PMLR, 2022.
Dong, Y., Wang, S., Wang, Y., Derr, T., and Li, J. On structural explanation of bias in graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 316-326, 2022.
Azzolin, S., Longa, A., Teso, S., Passerini, A., et al. Re- considering faithfulness in regular, self-explainable and domain invariant gnns. In Proceedings of ICLR 2025. Curran Associates, Inc., 2025.
Faber, L.., K. Moghaddam, A., and Wattenhofer, R. When comparing to ground truth is wrong: On evaluating gnn explanation methods. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data min- ing. pp. 332-341, 2021.
Bajaj, M., Chu, L., Xue, Z. Y., Pei, J.. Wang, L., Lam, P. C.- H., and Zhang, Y. Robust counterfactual explanations graph neural networks. Advances in Neural Information Processing Systems, 34:5644-5655. 2021.
Belghazi, M. I., Baratin, A., Rajeshwar, S., Ozair, S., Ben- gio, Y., Courville, A., and Hjelm, D. Mutual information neural estimation. In International conference ma- chine learning, pp. 531-540. PMLR, 2018.
Fang, J., Liu, W., Gao, Y., Liu, Z., Zhang, A.. Wang, X., and He, X. Evaluating post-hoe explanations for graph neural networks via robustness analysis. Advances in Neural Information Processing Systems, 36, 2024.
Chen, J., Amara, K., Yu, and Ying, R. Generative explana- tions for graph neural network: Methods and evaluations. arXiv preprint arXiv:2311.05766 2023.
Hooker, S., Erhan, D., Kindermans, P.-.., and Kim, B. A benchmark for interpretability methods in deep neural networks. Advances in neural information processing systems, 32, 2019.
Chen, V., Yang, M., Cui, W., Kim, J. S., Talwalkar, A., and Ma, J. Applying interpretable machine learning in computational biology pitfalls, recommendations and opportunities for new developments. Nature methods, (8):1454-1461, 2024a.
Izmailoy, P., Podoprikhin, D., Garipov, T., Vetrov, D., and Wilson, A. G. Averaging weights leads to wider optima and better generalization. In 34th Conference on Un- certainty in Artificial Intelligence 2018, UAI 2018, pp. 876 885.885,44 Association For Uncertainty in Artificial Intel- ligence (AUAI), 2018.
Chen, X., Cai, R., Zhu, Y., Horwood, J., Hao, Z., Li, Z Hernández-Lobato,, J. M., et al. Feature attribution with necessity and sufficiency via dual-stage perturbation test for causal explanation. In International Conference on Machine Learning. PMLR, 2024b.
Jang, E., Gu, S., and Poole, B. Categorical reparametrization with gumble-softman sofumax. In International Conference on Learning Representations, 2017.

---

Redundancy Undermines the Trustworthiness of Self- Intfrrrteeeectable GNNs
Kingma, D. P. and Ba, J. Adam: A method for stochas- tic optimization. In Bengio, Y. and LeCun, Y. (eds.), 3rd International Conference
Workshop Graph Representation Learning and Beyond, 2020.
Learning Represen- tations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: //arxiv. org/ abs / 1412. 6980.
Oord, v. d., Li, Y., and Vinyals, O. Representation learn- ing with contrastive predictive coding. arXiv preprint arXiv.1807.037485 2018.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017.
Pfeifer, B., Saranti, A., and Holzinger, A. Gnn-subnet: dis- ease subnetwork detection with explainable graph neural networks. Bioinformatics,
1iiii12--i1220 2022.
Li, J., Pang, M., Dong, Y., Jía, J., and Wang. B. Graph neural network explanations fragile. In International Conference on Machine Learning. PMLR, 2024.
Quesado, P., Torres, L. H. M., Ribeiro, B., and Arrais, J. P.
A hybrid GNN approach for improved molecular property prediction. J. Comput. Biol., 31 1):1 146-1157, 2024. doi: 10. (089/CMBB.223.0000
URL https::///// /oii org / 10. 1089 cmb. 2023 0452.
Lin, C., Sun, G. J., Bulusu, C.,, Dry, R., and Hernande7, M. Graph neural networks including sparse interpretabil- ity. arXiv preprint arXiv:2007.00 0000 19, 2020.
Ragodos, R., Wang. T., Feng, L., et al. From model explana- tion to data misinterpretation: Uncovering the pitfalls of post hoc explainers in business research. arXiv preprint arXiv:2408. 16987, 2024.
Liu, W., Wang, H., Wang. J., Li, R., Li, X., Zhang, Y., and Qiu, Y. Mgr: Multi genertee based rationalization. In The 6lst Annual Meeting Of The Association For Compu- tational Linguistics, 2023.
Rajput, N. and Singh, K. Temporal graph learning for financial world: Algorithms, scalability, explainability & fairness. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4818 9818-4819) 2022.
Lu, S., Liu, B., Mills, K. G., He, J., and Niu, D. Eig-search: Generating edge-induced subgraphs for gnn explanation in linear time. In International Conference on Machine Learning. PMLR, 2024.
Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H., and Zhang, X. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33: 33:19620-19631, 2020.
Rao, J., Zheng, S., Lu, Y., and Yang, Y. Quantitative evalua- tion of explainable graph neural networks for molecular property prediction. Patterns, 3(12), 2022.
Rudin, C. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206- 215, 2019.
Luo, D., Zhao, T., Cheng, W., Xu, D., Han, F., Yu, W., Liu, X., Chen, H., and Zhang, X. Towards inductive and efficient explanations for graph neural networks. IEEE Transactions Paltern Analysis and Machine Intelli- gence, 2024.
Sanchez-Lengeling B., Wei, J., Lee, B., Reif, E., Wang, P., Qian, W., McCloskey, K., Colwell, L.,, and Wiltschko, A. Evaluating attribution for graph neural networks. Ad- vances in neural information processing systems, 33: 5898-5910, 2020.
Madhyastha, P. S. and Jain, R. On model stability as a function of random seed. Proceedings of the 23rd Con- ference on Computational Natural Language Learning (CoNLI.), pp. 929-939, 2019.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008
Medda, G., Fabbri, F., Marras, M., Boratto, L., and Fenu, G. Gnnuers: Fairness explanation in gnns for recommenda- tion via counterfactual reasoning. ACM Transactions on Intelligent Systems and Technology, 16(1):1-125) 2024.
Sui, Y., Wang, X., Wu, J.. Lin, M., He, X., and Chua, T.-S. Causal attention for interpretable and generalizable graph classification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1696-1705, 2022.
Miao, S., Liu, M., and Li, P. Interpretable and generaliz- able graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pp- 15524-15543, PMLR, 2022.
Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection bench- mark datasets for learning with graphs. In ICML. 2020
Tsamardinos, I., Brown, L. E., and Aliferis, C. F. The max- min hill-climbing bayesian network structure learning algorithm. Machine learning, 65:31-78. 2006.
10

---

Redundancy Undermines the Trustworthiness of Self- Seff-Interpretable GNNS
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.,, Gomez, A. N., Kaiser, I.., and Polosukhin, I. Atten- tion is all you need. Advances in Neural Information Processing Systems, 2017.
Zhang, Z., Liu, Q. Wang, H., Lu, C., and Lee, C. Prot- gnn: Towards self-explaining graph neural networks. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 36, pp. 9127-9135, 2022.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A.,
Zhao, T., Luo, D., Zhang, X., and Wang, S. Faithful and consistent graph neural network explanations with ratio- nale alignment. ACM Transactions Intelligent Systems and Technology, 14(5):1-22 2023a.
Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Wang, X., Wu, Y., Zhang, A., He, X., and Chua, T.-S. Towards multi-grained explainability for graph neural networks. Advances in Neural Information Processing Systems, 14:1844--1855 2021.
Zhao, T., Luo, D., Zhang, X., and Wang, Towards faithful and consistent explanations for graph neural networks. In International Conference on Web Search and Data Mining, pp. 634 642, 2023b.
Wang, Y., Wang. J., Cao, Z., and Barati Farimani, A. Molec- ular contrastive learning of representations via graph neu- ral networks. Nature Machine Intelligence, 4(3):279-287, 2022.
Zheng, X., Shirani, F., Wang, T., Cheng, W., Chen, Z., Chen, H., Wei, H., and Luo, D. Towards robust fidelity for evaluating explainability of graph neural networks. In International Conference on Learning Representations, 2024.
Warmsley, D., Waagen, A., Xu, J., Liu, Z., and Tong, H. A survey of explainable graph neural networks for cy- ber malware analysis. In 2022 IEEE International Con- ference on Big Data (Big Data), pp. 2932-2939. IEEE, 2022.
Wu, S., Sun, F., Zhang, W. Xie, X., and Cui, B. Graph neural networks in recommender systems: survey, ACM Computing Surveys, 55(5):1-37, 2022a.
Wu, Y., Wang. X., Zhang, A., He, X., and Chua, T.-S. Dis- covering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022b.
Xu, K., Hu, W., Leskovee, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Ying, Z., Bourgeois, D., You, J., Zitnik, M., and Leskovec, J. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Yu, J., Xu, T., Rong, Y., Bian, Y., Huang, J., and He, R. Graph information bottleneck for subgraph recognition. In International Conference on Learning Representations, 2021.
Yuan, H., Yu, H., Wang, J., Li, K., and Ji, On explainabil- ity of graph neural networks via subgraph explorations. In International conference on machine learning, pp. 12241- 12252. PMLR, 2021.
Zhang, J., Luo, D.,, and Wei, H. Mixupexplainer: General- izing explanations for graph neural networks with data augmentation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3286-3296, 2023.

---

Redundancy Undermines the Trustworthiness of Self- Beff-Interpretable GNNs
A. Proofs
Proposition 4.1. Define the crucial graph subset as the optimal GNN explanation G When K 2 |Gg there exist 2 1
valid GNN explanations that can satisfy Equation (1).
Proof. Based on Lagrangian, adjusting actually corresponds to setting different budget values K (Zhang et al., 2022).
In our experiments, K 2 [G'] generally holds true in existing self- eeff-rnterree GNNs. By definition of MI, optimizing Equation (1) equals:
max G.
(
(9)
Since HY) a constant once the dataset given, maximizing the above equals:
max
-Y)G)).
(10)
G.C.C.C.IKK
20
where HY)).,) O means the graph subset G, contains enough information to predict the label Y, i.e., G S G, K larger than the size of the optimal GNN explanation, i.c., K 2 | we have Σ (IG-G:l) different explanations that can satisfy Equation (1). This completes the proof.
Proposition 4.2. Assume that G has multiple independent explanations G = {G G G...,, with pairwise disjoint edge sets. Then, no single edge is strictly necessary.
Proof. An edge E E is strictly necessary if removing e from G, causes I(G;; Y) to decrease, i.e., e is indispensable for any valid explanation of Y. By definition, each explanation G in the set G = {G.,"" G.* ...., G } is sufficient to fully explain Y. Therefore:
()) ((; Vi
(11)
Suppose e E is considered strictly necessary. Then, its removal must render all valid explanations of Y invalid. Formally, we have:
T(, (e): < V(G,Y) VG, E G and [., < K
(12)
However, by the independence property of the explanations, each explanation G = EVi,&)) satisfies the following condition:
83g 0, Vi i.j E
(13)
Therefore, for any G that contains e, there exist at least one Gi (j * i) that does not rely on e. Thus, the removal of e does not invalidate all explanations, and I(G, \ {e);Y) = I(G,; Y) still holds for at least one G, E (G! GZ...... .... G "}. Since this reasoning holds for any edge e E E, we conclude that no single edge is strictly necessary when has multiple independent explanations. This completes the proof.
Propusition 5.1. Let X be a random variable with [[ = a and Var(X) where X E [0, 1]. Let 21, 22 be independent draws from X, and let X1, X₂ be the sample means of two independent n-samples X. For positive hyperparameter k (0, 11, we have:
2b
P([x:
X21 < k/21 x22) 2 1
(14)
nk. x1
2212
Proof. We aim to derive a lower bound for the probability P([X1 using the complement rule:
Xz1 k|21 x2l). First, we rewrite the probability
P X2l k| 222)
P(|X,
X21 2 K/21 x2l)-
(15)
12

---

Var(X) b Redundancy Undermines the Trustworthiness of Self- Interrprrrre GNNS
Next, apply Chebyshev's inequality'. Chebyshev's inequality states that for any random variable Z with finite mean E [[z] and variance Var(Z), and any positive value
Var(Z)
P(IZ E|Z]
(16)
Now, we let == X1 X2 and k1/21 F2l. Applying Chebyshev's inequality, we get:
Var(X, X2)
P(| - X2 - E E[x1 X2] 2
k/ x2)) 5
(17)
(k:211 - x22 )2
Since E[X,] = [[X] = a and E[X,) = E = a, we have:
E X = E[X,] -
E[22] = -
(18)
Substituting Equation (18) into Equation (17), we obtain:
Var( X1 X2) P( - X2 2 k/ - x21) S
(19)
k2 x11 222
Now, we calculate the variance of X1 X2. Since X1 and X2 are the sample means of two independent samples of size from X, we have:
Var(X) n n
b
Var(X,)
(20)
Var(X2)
(21)
7 ni
Because X, and X2 are independent, the variance of their difference is the sum of their variances:
b
b 26
Var(X; -x2)= Var(X,) Var(X2)
(22)
n n
Substituting Equation (22) into Equation (19), get:
2h
P([x - X21 2 ki/00 x22) 5
(23)
nk.
.1
x2 1
Finally, substituting Equation (23) back into Equation (15), we obtain the desired lower bound:
26
P([x: X21 < k| x2l)
(24)
nk- 41 x2 2
This completes the proof.
Proposition 5.2. Let X and W be independent random variables with X E [0, 1] and W E [8, 11. where 0 < 8 S 1. Let X be the sample mean of n independent observations of X. E[ < 6, then we have:
P(X < W) 2 1 expl (6 E{X])²).
(25)
Proof. Since W E 16, if X < 6, then it must also be true that X < W. Therefore:
P(X 2 P(X < W).
(26)
We can calculate P(X < o) as follows:
P(X < 8) = 1 P > 8).
(27)
_ ity
13

---

Redundancy Undermines the Trustworthiness of Self- Beffrrrttepretable GNNs
Next, we apply Hoeffding's inequality². Hoeffding's 's inequality states that for several independent random variables 7....., Zn with Zi (a, for all where 20 S +00, have:
2 EJ Z.) 21) S exp (-70- 2nt²
P
(28)
[b a)2
-=1
In our case, X E [0, so (b a) = 1. Applying Hoeffding's inequality with / = -
[x[]] (since [R[X] < <,,6> 0), we
have:
2m(6 E[X])²
P(X 2 6) B[X] 2 d E[X]) - exp
exp(p22n(( =
(29)
12
Thus,
P(X < 8) 2 1 1x1-epp(-10) exp(-2n(6 B[
(30)
Combining Equation (30) with Equation (26), we obtain:
P(X W) 2 1 exp(- {[
(31)
This completes the proof.
B. Spurious Correlations Are Not the Primary Drivers of Inconsistency
(a) Important (Type I)
(b) Important (Type II)
(c) Important (Type III)
(d) Important (Type IV)
015 222
3/D
306 625 645
03s 6.0 825 635 a/d cds aid 635 a.d
615
025 8rd
ai 075
036
025
025
072 6.00
(c) Unimportant (Type I)
(f) Unimportant (Type II)
(g) Unimportant (Type III)
(h) Unimportant (Type IV)
Figure 6: Histograms of edge weights trained on the 3MR dataset.
In this section, we present histograms of edge weights for the 3MR, BENZENE, and MUTAGENICITY datasets (see Figure 6, Figure 7, and Figure 8). The results indicate that, when evaluated on datasets without deliberately introduced spurious patterns, all self-interprettable GNNs are able to identify truly important edges. However, explanation inconsistency still persists. This suggests that spurious correlations are not the root cause of explanation inconsistency in self-interpretable GNNs. Instead, we attribute this inconsistency redundancy: different irrelevant edges are identified as important across training runs, leading to variations in explanations.
C. Hyperparameter Tuning Fails to Address Redundancy
To quantify the impact of hyperparameter tuning, we present histograms of |G.I/|G| for the 3MR, BENZENE, and MUTAGENICITY datasets, shown in Figure 9, Figure 10, and Figure 11, respectively. The results show that redundancy cannot be addressed by hyperparameter tuning. Increasing the value of generally leads decrease in the model's prediction accuracy. For instance, on the Type III framework, setting to results in an accuracy reduction of 5%-20%
"https://cs22 (tttt::://s222.staaffrrr sww.norrd.....o..o wewdd.dduexxtteee hto.ro/dddd//eeeeeeoooooeee//oee fnng:rrrrnnottee/eeeifnnnn.ggng
14

---

Redundancy Undermines the Trustworthiness of Self- Beff-Interpretable GNNs
1.0
0.15
1.25
0.33
2:4
055
205 075 100 6.55
0.5
1:10
0.2
1.35
344
0.5
345
0.55 0.00
0.55
0.0 6:15
8:25
0:35
844
0.5
8.08
0.75
0.00
0d0
0.55
0.3
0.45
0.55
0.5
1.75
1.5
(a) Important (Type I)
(b) Important (Type II)
(c) Important (Type III)
(d) Important (Type IV)
2/6
625
005
635 3.0 0.5 6-d
325
(c) Unimportant (Type I)
(f) Unimportant (Type II)
(g) Unimportant (Type III)
(h) Unimportant (Type IV)
Figure 7: Histograms of edge weights trained on the BENZENE dataset.
(a) Important (Type I)
(b) Important (Type II)
(c) Important (Type III)
(d) Important (Type IV)
ois aie oas ard 366 025 645
on 6.6 a25 c35 axd cds aid 635 aid
330 ois a. 025 8/d ads
s ois a 036
aid
125 a3 (h) Unimportant (Type IV)
122 64G 675
(c) Unimportant (Type I)
(f) Unimportant (Type II)
(g) Unimportant (Type III)
Figure 8: Histograms of edge weights trained on the MUTAGENICITY dataset.
D. Contrastive Learning Fails to Address Redundancy
When it comes to incorporating contrastive loss into existing self-interpretable GNNs, present our results in Table 2. "+CL (c)" means positive and negative samples were created by adding/removing c edges from G,, On the BA-2MOTIFS dataset, incorporating contrastive loss reduces explanation inconsistency and improves accuracy. However, on the BENZENE dataset, incorporating contrastive loss leads to performance degradation across all metrics.
E. Rationale for Metrics and Datasets Selection
E. Metrics Selection
To evaluate explanation quality, two types of metries are commonly used in the community: those that rely on ground-truth truth metrics, such ROC-AUC, offer unbiased evaluation standards, as
explanations and those that do not. Ground-truie they directly measure how well the explanation aligns with predefined important substructures. However, their applicability is limited by the scarcity of high-quality annotated datasets. Moreover, even when such annotations exist, they may not fully reflect the internal reasoning of the model-they can rely on alternative, equally valid but human- iamaa-iiccoppehennibbee patterns to make correct predictions. As a result, agreement with ground-trutt does not always guarantee that an explanation truly captures the model's behavior.
15

---

Redundancy Undermines the Trustworthiness of Self- Interpretable GNNS
0
g =
_ 0.01
B 8=1
7.5
7.5
7.5
7.5
Density
GT
Density
8 3 10
Density
B 0.1
8= 10
5.0
5.0
GT
5.0
B B=1
5.0
GT
2.5
2.5
2.5
GT
2.5
0.0
0.25
0.50
0.75
1.00
0.0
0.25
0.50 Ratio
0.75
1.00
0.0
0.25
0.50 Ratio
0.75
1.00
0.0
0.25
0.50
0.75
1.00
Ratio
Ratio
(a) Type
(h) Type
(c) Type III
(d) Type IV
Figure 9: Histograms of [Gal/|G| on the 3MR dataset.
4.5
4.5
4.5
4.5
B = 0
A =
B= 0.01
B=
Density
3.00
GT
Density
3.0
8 = 10
Density
3.0
8 0.1
Density
3.0
B = 10
GT
GT
GT
1.5
1.5
1.5
1.5
0.0
0.50
0.75
1.00
0.0
0.25
0.50 Ratio
0.75
1.00
0.0
0.25
0.50 Ratio
0.75
1.00
0.0
0.25
0.75
1.00
Ratio
Ratio
(a) Type
(b) Type I1
(c) Type III
(d) Type IV
Figure 10: Histograms of |G,//||| on the BENZENE dataset.
12
12
12
12
B=
8 1
0.01
B=
Density
8-
GT
Density
8
8= 10
Density
8
B= 0.1
Density
8
GT
GT
GT
0.5
1.0
0.25
0.50 Ratio
0.75
1.00
0.25
0.50 Ratio
0.75
1.00
0.25
0.50
0.75
1.00
Ratio
Ratio
(a) Type
(b) Type
(c) Type III
(d) Type IV
Figure 11: Histograms of |Gal/G|| on the MUTAGENICITY dataset.
In contrast, metrics that do not require ground-truth labels aim to assess faithfulness (Amara et al., 2022), i.e., how well the explanation aligns with the model's own decision preiiion-making process. A widely used class of such metrics is the family of Fidelity (FID) metrics (A (Amara et al., 2022), which quantify the change in the model's prediction when the identified important subgraph is either removed or retained. These metrics are more broadly applicable and, in theory, enable explanation quality to be assessed any scenario. However, their reliability remains an active topic of debate (Faber et al., 2021), particularly due to distribution shifts introduced by imput perturbations (Zheng et al., 2024). As long as OOD exists, FID-based metrics assess not only explanation quality but also the model's generalization ability (Azzolin et al., 2025), introducing confounding factors that weaken the objectivity of the evaluation.
AUC vs. FID has long been debated, and neither is perfect. The key contribution of our work is to raise awareness in the community that redundancy in explanations weakens explanation quality. Given (1) the specific nature of our task (we need ground-truth to assess redundancy), (2) that AUC's limitations can be fully addressed certain cases, and (3) that the FID's limitations can't be fully addressed (to date), we ultimately chose AUC and just feel that SHD and AUC are enough to support our findings.
As discussed above, ground-truth explanations can sometimes be misleading, they may not accurately reflect the reasoning process of the trained model. To avoid this risk, we were highly selective in choosing datasets and only included four well-established benchmarks that have been extensively validated by the community. Specifically, BA-2MOTIFS and MUTAGENICITY have been adopted in prior works such as GNNExplainer (Ying et al., 2019), PGExplainer (Luo et al., 2020), DIR (Wu et al., 2022b), and GSAT (Miao et al., 2022), all of which use AUC for evaluation. For 3MR and BENZENE, AUC was also employed by Rao et al. (2022). To further ensure that ground-truth explanations align with the model's
16

---

Redundancy Undermines the Trustworthiness of Self- Beff-Interrretable GNNS
Table 2: We run each method 10 times, reporting the mean and standard deviation. Results significantly outperforming the baseline X (GIN, paired t-test, p < 0.05) are underlined. Type I is selected for our case study.
DATASET
STRATEGY
SHD
AUC
ACC
4.75=4.68
99.30=0.34
97.10
+CL
4.27=3.90
99.67=0.10
100.00:10.00
BA-2MOTIFS
+CL. (3)
4.77=4.38
99.35-0.57
100.00=100.00
+CI. (5)
4.71=5.36
99.29-0.28
99.69+0.90
x
6.11=4.34
83.50-2.23
91 91.60+-0.66
+CI. (1)
10.89+6.57
81.97-2.68
90.49+1.64
BENZENE
+CL.
13.05-8.36
79.47=3.46
88.37+4.44
+CL (5)
5.14
81.77=3.77
87.92
Table 3: Statisties of the datasets.
BA-2MOTIFF
3MR
BENZENE
MUTAGENICITY
Graphs
1000
2877
12000
2951
# Nodes / Graph
25.00
20.31
20.58
30.13
Edges / Graph
25.48
22.27
21.82
30.45
Node Features
10
14
Multiple Types of Rationales? Multiple Identical Explanations?
No
No
No
-NO2 and -NH2
No
Three-membered Rings
1 Benzene Rings 33.64%
1 Explanations
# Ratio of Multiple Explanations
0.00%
8.21%
32.01%
learned knowledge, we manually inspected the outputs of trained models. Specifically, we validated dataset reliability by checking: (I) whether, in correctly classified cases, the model assigns high importance to truly relevant edges; and (2) whether the model relies on any unintended shortcuts. While such manual inspection cannot guarantee absolute reliability, provides a reasonable safeguard against misleading explanations.
We acknowledge that verifying the absolute faithfulness of ground-truth explanations remains fundamental challenge. Designing more principled and robust evaluation protocols is an important direction for future work.
E.2. Datasets Selection
We select four datasets:
synthetic dataset, BA-2MOTIFS (Luo et al., 2020), and three real-world dataset 3MR (Rao et al., 2022), BENZENE (Morris et al., 2020), and MUTAGENICITY (Morris et al., 2020) all sourced from the graph learning community and have ground-truth explanation labels.
BA-2MOTIFS: synthetic dataset with binary graph labels created by Luo al. (2020). Class labels are determined by house motifs and cycle motifs, which serve as the ground-truth explanations for the two classes. Each graph has only one explanation.
3MR: A real-world molecular property prediction dataset where nodes represent atoms and edges represent chemical bonds (Rao et al., 2022). Each graph is labeled binary to indicate the presence of one more three-membered rings. Multiple explanations may exist for each graph.
BENZENE: real-world molecular property prediction dataset where nodes represent atoms and edges represent chemical bonds (Sanchez-Lengeling et al., 2020). Each graph labeled binary to indicate the presence one or more benzene rings. Multiple explanations may exist for each graph.
MUTAGENICITY: A real-world molecular property prediction dataset where nodes represent atoms and edges represent chemical bonds (Debnath et al., 1991). Each graph is labeled binary to indicate its mutagenic effect, with -NO2 and -NH2 considered ground-truth explanations (Luo et al., 2020). Multiple explanations may exist for each graph.
These datasets are selected to represent a variety of characteristics commonly encountered graph explanation tasks. BA-2MO,IFS, a synthetic dataset, has a single, unambiguous ground-trut -tunt explanation for each instance. 3MR, a real-world dataset, while having multiple possible explanations for each instance, has relatively low proportion (8%) of instances with
17

---

Redundancy Undermines the Trustworthiness of Self- Self-rnntepretable GNNs
Table 4: We run each method 10 times, reporting the mean and standard deviation. Results significantly outperforming the baseline x (GIN, paired t-test, p < 0.05) are underlined. Values in brackets show performance changes after Explanation Ensemble. Dark green indicates performance improvement, while dark red indicates performance degeneration.
METHOD
METRIC
STRATEGY
BA-2MOTIFS
3MR
BENZENE
MUTAGENICITY
2.74 (L 1.37)
6.44.13.85 (L 2.91)
0.00=00.00 (0.00)
2.90=5.880 (1 2.90)
SHD
+SWA
3.89+ (1 2.70)
3.06+-2.15 (1 1.77)
0.00=00.00 (0.00)
7.79+5535 (1 4.38)
+EA
3.80.13.84 2.01)
4.82 (L 2.67)
0.00.00.00 (0.00)
0.12.10.25 (1 0.12)
19.12:10.17 (1 0.14)
98.89:10.20 (1 0.56)
83.63.1.334 (1 6.59)
97.22-10.9 ( 1.56)
Type I (Attention)
AUC (%)
+SWA
99.06.+0.13 (1 0.08)
98.56++0.12 (1 0.31)
2.6933+2.68 (1 2.38)
08.83+0.28 (1 0.37)
+EA
98.95=0.228 (1 0.17)
98.78=0.15 (1 0.56)
82.33+ .66 (1 8.30)
1. (1 2.06)
100.00++0.00 (0.00)
99.13++0.41 (1 0.17)
91.17++0.36 (t 0.41)
92.22+ 1.2221100 (1 0.34)
ACC(%)
+SWA
70.301:5000 (L 2.00)
94.15=10.58 (L 0.04)
87.724:0.26 (1 0.36)
07 (1 0.41)
+EA
100.00++0000 (0.00)
99.37=00333 (1 0.28)
91.36+0.33 (1 0.14)
92.22=0.95 (1 0.78)
x
1 (4 0.66)
3.66:12.51 (L 2.00)
0.00 (0.00)
0.15 (J 0.15)
SHD
+SWA
3.54 (1 2.20)
4.22-42.88 (L 2.14)
0.00=0.00 (0.00)
7.15=4.82 () 3.95)
+EA
2. (1 1.76)
1. (L 2.75)
0.00 (0.00)
0.01 (1 0.01)
x
97.80.10,42 (f 1.08)
98, 10 (1 0.70)
73.6616.03 (t 8.72)
96.8710.80 (1 1.59)
Type II
AUC (%)
+SWA
96.96- (f 1.67)
97.23++0.49 (1 0.99)
66.65+44.43 (f 8.25)
97.83+0..43 (1 1.22)
(Causal Learning)
+EA
97.53=0.59 (1 1.33)
98.36=10.30 (1 0.85)
75.25+6.92 (1 7.14)
95.27=1.51 (1 2.38)
x
78.59=44005 6.4,1)
98.30+00.66 (1 1.00)
84.20+ (1 3.21)
89.66+ (t 0.88)
ACC (%)
+SWA
65.50-+6.77 (1 0.50)
88.75+ (1 0.52)
82.79+ 1.02 (f 2.62)
90.03++0.48 (1 0.17)
+EA
80.19=6.70 (1 7.81)
99.03-+0.43 (1 0.62)
43.15+4.89 (1 3.76)
89.72=0.83 (1 0.48)
x
2.77.12.57 (1 1.68)
3.5112.377 (L 1.62)
0.00 (0.00)
18.74 (4) 9.91)
SHD
+SWA
4. (1 3.10)
2,8942222 (L 1.52)
0.00=0000 (0.00)
11.4916.87 (L 6.13)
+EA
3.15 (1 1.67)
3.53 (L 1.69)
7.00 (0.00)
11.07 (L 6.74)
x
99.11100116 (1 0.11)
98.44.10.19 (1 0.72)
85.7511.006 (1 5,83)
97. 97.4910.88 (1 1.57)
Type III (Size Constraint)
AUC (%)
+SWA
98.94+0..18 18 (1 0.09)
98.37++0.09 (1 0.42)
89. 1.02 (1 1.73)
98.67+00228 (1 0.48)
+EA
99.10=10.12 (1 0.09)
98.35::0.23 (1 0.75)
4..31 (1 7.82)
97.00=1 46 (1 1.91)
X
100.00++0.00 (0.00)
98.85=00.46 (1 0.45)
90.67+00299 (1 0.58)
91.35+ 1.22 (1 0.87)
ACC (%)
+SWA
68.80+5.111 (1 0.20)
03.04++1.08 (1 0.73)
87.83++0.33 (1 0.25)
09.66+0.40 (1 0.14)
+EA
100.00+10.00 (0.00)
99.30=20:40 (1 0.35)
91.37+:0.26 (1 0.13)
91.95=1.04 1.04 (T 0.95)
x
3.72.13.54 2.25)
S.75 (L 2.25)
3.78 (1 2.11)
13.53 10331110.00 10.86 (1 5,98)
SHD
+SWA +FAA
3.13 (1 2.73)
3,8913,51 (L 2,86)
0,48 (L 0.48)
0.00 (0.00)
2.33 (1 1.51)
6.64 () 2,49)
2.78 () 2.76)
11.91 8.38 (L 5.13)
x
98.73.10.14 (1 0.20)
99.31110.15 (1 0.19)
88.1511.22 (1 1.01)
99. 99.1510.119 (1 0.17)
Type IV (MI Constraint)
AUC (%)
+SWA
99.21+00116 (1 0.13)
98.40++0.23 (1 0.24)
89.09++0.5 (t 0.87)
99. 14.0770.07 ( 0.13)
+EA
98.16=#0.33 (1 0.29)
99.14=0.118 (1 0.24)
86.6911.18 (1 1.14)
99.19 (1 0.21)
X
100.0011..00 (0.00)
99.51110.16 (1 0.21)
88.83110.46 (f 0.35)
51.58 (1 0.64)
ACC (%)
+SWA
87.30+88003 (1 6.70)
93.07-+0.99 (1 0.27)
86.96+00.68 (t 0.79)
89.86+0.72 (1 0.68)
+EA
100.00+10.00 (0.00)
99.27= (1 0.38)
87.62++0.47 (1 0.46)
91.85=1.22 (1 0.71)
multiple explanations. BENZENE, in contrast, exhibits higher degree of multi-explanattons, with 33% of its instances having multiple valid explanations. Finally, MUTAGENICITY also features instances with multiple explanations, and these explanations can be of varying types. This diverse selection of datasets ensures comprehensive evaluation of our proposed method. Statistics of the datasets are provided in Table 3.
F. More Quantitative Results
In this section, we present the results of using GCN as the model architecture (see Table 4). Some self-interpretable GNNs achieve zero SHD (indicating no inconsistency) on certain datasets, but this result is misleading. It does not imply that they produce meaningful explanations. Instead, the zero SHD is often an artifact of the model assigning weights above 0.5 to all edges. In experiments, we used 3-layer GCN and 2-layer GIN, as a 2-layer GCN failed to achieve satisfactory classification performance. However, we observe that even with improved accuracy, the explanations produced by GCN remain much less meaningful compared to GIN. This may be because GCN's aggregation mechanism (i.c., neighborhood averaging) tends to dilute node-specific signals, especially as the number of layers increases. As a result, the model may become less sensitive to specific substructures and assign uniformly high attention to all edges, leading to deceptively low SHD scores. In contrast, GIN, which is more expressive and theoretically as powerful as the Deisfeiler-Lehmar test, appears
18

---

Redundancy Undermines the Trustworthiness of Self- Self-Interpretable GNNs
Table 5: Datasets and their URLs
DATASET
URL
BA-2MOTIFS
3MR
https: http:///oiiiaanssss....oaaaaeaee
BENZENE
MUTAGENICITY
to better preserve local discriminative structures and yields more valuable explanations.
G. Experimental Settings
Considering that some of the datasets selected were not used in the original papers of certain methods, and to ensure (relatively) fair comparison, we built our backbone entirely upon the official GSAT (Type IV) implementation and then reimplemented ATT (Type 1), GISST (Type III), and CAL (Type III) on top of this backbone. Specifically:
ATT (Velickovic et al., 2018); This only required modifying the loss function (classification loss).
GISST (Lin et al., 2020): This only required modifying the loss function (classification loss + L.1 loss entropy loss). In practice, we observed that due to the use of Gumbel sampling during training, the model naturally tends to produce hear-binary outputs. As result, the entropy loss became unnecessary and was ultimately omitted in our final implementation.
CAL (Sui et al., 2022): We reimplemented CAL within the GSAT framework based on its original implementation. Besides modifying the loss function, CAL requires three classifiers, each taking different inputs, described in Equation (3). In the original GSAT (Miao et al., 2022), the final classifier is a single linear layer. However, during our experiments, we found that 1 l-layer classifier(s) led to convergence issues for CAL. Therefore, we changed it to 3-layer classifier(s). For consistency, we also applied this modification to ATT, GISST, and GSAT.
SHD Calculation. We run each method 10 times with different random seeds. To evaluate stability. we randomly divide the 10 models into two disjoint groups and compute the SHD) between their corresponding EE-generated explanations. For Table and Table 4, we consider all possible 5-vs-5 splits and report the average SHD across all such pairs. For Figure 5, and sample all possible disjoint n-vs-n pairs from the 10 models, reporting the
we vary the ensemble size v from average SHD for each n.
To compute the standard deviation of SHD, take sample-level approach: for each individual graph, calculate the SHD scores across all valid disjoint model groupings, then compute the standard deviation of these scores for that graph. The final reported value is the average of these per-sample standard deviations across the dataset. This reflects sample-level variability, rather than population-level variance over the whole dataset.
Model Architectures. GIN consists of layers with hidden size of 64, while GCN has layers with the same hidden size. Following Miao al. (2022), we employ a 3-layer Multi-Layer Perceptron (MLP) to predict edge weights, with hidden selected based on validation set performance: the learning rate is chosen
sizes set to 256, 64, 1. Model hyperparameters from (0.01, 0.005, 0.001, 0.0005. 0.0001} to maximize classification accuracy, and for SWA, learning rate or half of it, whichever yields better validation accuracy. The coefficient for EA is selected from {0.01, 0.1, 1, 10, 100} based on classification performance on the validation set. We start using SWA from the 10-th epoch, and at the end of every optimization step, a snapshot of the weights will be added to the SWA running average.
either the optimal
Self-Interpretable GNN frameworks. The workflow of the self-interpretablle GNNs is described follows (we use GIN as study case). First, 2-layer GIN is used update node representations:
H GIN(G).
(32)
Next, a 3-layer MLP (explainer) with hidden size (256, 64, 1} is used to predict edge weights. For certain edge (i. its edge weight is calculated as:
mi = (MLP h,)),
(33)
19

---

Redundancy Undermines the Trustworthiness of Self- Self-Inttepretable GNNs
where a is the sigmoid function, h2 and hy represent the representation of the i-th node and j-th node in H, respectively, and is the sigmoid function. Then, Gy is factorized as:
P(G.) - II P(wa))
(34)
LJEE
where is the set of edges in the raw graph G, and P((y,) is the Bernuuli distribution Bern(w;y), representing the probability of edge (i,j) being included in G.- Following existing works (Miao al., 2022; Deng & Shen, 2024; Luo et al., 2024), we employ the Gumbel Softmax technique (Jang et al., 2017) for generating GNN explanations during training, The edge weight eij is calculated by:
(niform(O,). 1),
c = ((loge log(1 -)) + wiy)/r)
(35)
where a is the sigmoid function, and is the temperature parameter. Finally, G, is fed to the above GIN;
2 (OOL)G
(36)
where POOL is a pooling operation RI + TR. (e.g., sum, mean, max). The other 3-layer MLP with hidden size {64, 64, 13 is used to make final predictions:
y = ML.(2.).
(37)
The optimization objectives defined in Section 2.2 are used during training. The hyperparameters (e.g.. B, 7) are selected from {0.01, 0.05, 0.1, 0.5, 5, 10, 50, 100), primarily based on classification accuracy on the validation set. In practice, we also heuristically consider explanation conciseness during selection, and discard configurations that yield uninformative explanations. Detailed hyperparameter settings can be found in our code.
Computing resources. All experiments 2015), and executed on one NVIDIA RTX 4090 GPU with Intel Core i7- 17-13700KF CPU. Running all our experiments single GPU took approximately 3 days.
conducted using Py PoTocch, trained with the Adam optimizer (Kingma & Ba,
Open Access to Data and Code. All datasets are published and can be downloaded from the Internet (see Table 5).
H. Limitations
While EE is effective in improving explanation consistency and its associated accuracy through ensemble averaging, it is inherently incompatible with commonly used faithfulness metrics. These metrics typically rely on perturbing or masking parts of the input based on a single model's 's explanation and observing the change in its prediction (Amara et al., 2022). However, EE produces explanations by aggregating multiple models' outputs, making it unclear which model should be evaluated under perturbation. Nonetheless, EE is just a first step toward more trustworthy explanations. We envision that future solutions may achieve similar or even better results without relying on ensembling.
Other Related Work
As suggested by one of the reviewers, we reviewed a set of recent works on self-interpretable methods in NLP. While these studies primarily focus on rationalization in language models, one of the Muutrs--Muli--Geeerttoo Based Rationalization (MGR) (Liu et al., 2023) certain similarities with our work. Specifically, MGR introduces multiple independently trained rationale generators to produce diverse explanations, which are then used to train a more robust predictor. Both MGR and our proposed EE adopt ensembling strategies, but they address different issues and operate in different ways: MGR targets spurious correlations and degeneration in text-based tasks and applies ensembling only during training, whereas EE, developed in the context of self-interpretablle GNNs, aggregates explanations inference time to mitigate the negative impact of redundancy. We plan to investigate whether redundancy also exists in self-interpretabble language models.
20


Reviews:
[{"review_id": "AhR06CsMg7", "reviewer": "Reviewer_K3Wx", "summary": "This paper investigates the inconsistency in explanations generated by self-interpretable GNNs. It identifies redundancy—caused by weak conciseness constraints—as the root cause of explanation inconsistency, which in turn reduces trustworthiness. The paper argues that redundancy is difficult to eliminate completely but suggests a simple ensemble strategy to mitigate its effects. Extensive experiments across multiple datasets and models validate the claim that EE improves explanation consistency and accuracy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our work. We appreciate the references you suggested and will discuss them in the revised manuscript. Your recognition of our work truly means a lot to us.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed method makes sense.", "theoretical_claims": "The paper makes two major theoretical claims:\n\n- Redundancy is the primary cause of explanation inconsistency. The paper provides empirical evidence, showing that training instability and spurious correlations are not the main causes of inconsistency. Appendix A supports the argument that redundancy naturally arises due to weak conciseness constraints.\n\n- Explanation Ensemble effectively mitigates redundancy. Empirical results consistently show EE improves explanation consistency and accuracy.", "experimental_designs_or_analyses": "I am not familiar with GNNs, so I can not judge it.", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "S:\n- The paper systematically examines why explanations of self-interpretable GNNs vary across runs with different random seeds. The investigation is thorough, combining theoretical analysis, extensive experiments, and case studies.\n\n- The proposed Explanation Ensemble is a simple yet effective solution that requires no hyperparameter tuning and consistently improves explanation quality across various datasets and models.\n\nW:\n- The EE method requires training multiple models to aggregate explanations, which increases computational cost linearly. While it significantly improves consistency, this approach may not be feasible in resource-constrained settings.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "There are some other papers studying self-interpretable methods (although belong to NLP), would it be possible to discuss them in the related work?\n\n[1] D-Separation for Causal Self-Explanation [2] Is the MMI Criterion Necessary for Interpretability? Degenerating Non-causal Features to Plain Noise for Self-Rationalization [3] Breaking Free from MMI: A New Frontier in Rationalization by Probing Input Utilization [4] MGR: Multi-generator Based Rationalization.", "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": "OEfJYk0Obe", "reviewer": "Reviewer_6xUG", "summary": "The authors study the (lack of) reliability of GNN explanations, focusing on self-explainable architectures, which promise precisely to output more reliable explanations.  They notice that these models however produce unstable explanations, or more specifically that their explanations vary even substantially between seeds, even when achieving high task accuracy.  Then, they propose and evaluate a simple mitigation strategy based on averaging explanations obtained from multiple seeds.\n\n**Post-rebuttal update**: the authors promised to clarify several rather central issues, which is enough for me to be weakly positive about the contribution.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. Below we address your concerns. \n\n**Constructive Feedback We Appreciate and Will Revise:**\n\n(1) Overstatement of the First Systematic Investigation\n\nOur intent was to emphasize that we are the first to investigate the inconsistency and its associated inaccuracy -- two key aspects of trustworthiness -- in SI-GNNs. We acknowledge that our current wording has overstated this claim, and we will revise our description accordingly. \n\n(2) Robustness of Self-Interpretable GNNs to Spurious Correlations\n\nOur intent was to highlight that the inconsistency observed in post-hoc GNN explanations, which has been attributed to spurious correlations, does not apply to SI-GNNs. Yes, you are absolutely right. We appreciate your insightful comment and will revise our description accordingly.\n\n**Points We Would Like to Clarify:**\n\nBased on your comments, we realized that clarifying the notions of $G_s$, $G_s^*$, optimal explanations, and truly important edges is crucial for you to reassess our work. $G_s^*$ is the ground-truth explanation (also referred to as the optimal explanation) available in our datasets. $G_s$ is the explanation generated by SI-GNNs. Edges that belong to $G_s^*$ are what we refer to as truly important edges. Since the definition of \"plausibility\" varies slightly across different papers, if it is understood as \"how closely $G_s$ matches $G_s^*$\", then it is correct to say that we aim for $G_s$ to be plausible. \n\n(1) Clarification on Related Concerns\n\n- Evidence for Redundancy, Identification of Truly Important Edges in Figure 2, and Support for Prop. 5.2: Because $G_s^*$ is available in our datasets, we can directly evaluate whether the model assigns high weights to these truly important edges. Fig. 2(a–d) show that SI-GNNs successfully identify these edges, and Fig. 2(e–h) show that they also assign high weights to some irrelevant edges. Reasons are detailed in Lines 198–219.\n- Redundancy is Difficult to Eliminate: Figure 3 and Prop. 4.1 illustrate why tuning hyperparameters cannot eliminate redundancy; (2) Figure 4, Prop. 4.2, and Table 2 show the limitations of the +CL. Note that while EE helps mitigate its negative impact, it does not eliminate redundancy. Eliminating redundancy remains an open challenge.\n- Questions on Prop. 4.1: By definition, $H(Y|G_s^*)=0$. If $G_s^* \\subseteq G_s$, we have $H(Y|G_s) = 0$. We cite Zhang et al. (2022) just to show that constraining the subgraph size (in theory) can be implemented via an additional loss term (in practice) -- please see Eqs. 12–14 in their paper.\n\n(2) Relationship Between SHD and AUC\n\nSHD and AUC evaluate different properties of explanations: SHD evaluates explanation inconsistency, while AUC evaluates explanation accuracy. There is no inherent relationship between the two metrics. Figure 6 just illustrates that the effectiveness of EE improves as $n$ increases.\n\n(3) Threshold Choice & Impact of Discretization on Redundancy\n\nWe chose a threshold of 0.5 because determining whether an edge is important is essentially a binary classification task, and 0.5 is a standard and prior-free choice. In contrast, other thresholds or Top-K selections all require domain knowledge. Regarding redundancy, the choice of discretization method does have an effect, as it directly influences the number of retained edges, which in turn affects metric value such as SHD. But this does not change the core conclusion of our paper. This is because irrelevant edges might receive higher scores than truly important ones, which means that no matter how the threshold is set (as long as it ensures relevant edges are included), these irrelevant edges will always be retained. That said, we believe HS and ER, proposed in the ICLR 25 paper you suggested, are very important for the future design of SI-GNNs.\n\n(4) Empirical Evaluation of Deng & Shen’s Approach\n\nTable 2 in Appendix D provides empirical evidence that applying CL to Type I reduces both AUC and ACC. Other types yield similar results, which we can provide in the revised version if needed.\n\n(5) Relation to ICLR 25 paper\n\nSorry, but we could not find the exact claim about ‘insufficient explanations’ in this paper. After reading it, we found that the most relevant aspect to our work is its discussion on the unreliability of existing FID metrics when redundancy exists (as they acknowledge redundancy might occur). This paper does not analyze why redundancy happens, nor does it provide clear evidence that the proposed strategies for improving faithfulness can address it. Given this, we believe our contributions remain distinct.\n\nWe appreciate your time and feedback, and we hope our rebuttal addresses your concerns. We look forward to any further discussions if needed. Thank you!", "claims_and_evidence": "Main claims:\n\n- Claim: This is the first systematic investigation of explanation reliability of GNNs\n    - Evidence: There is at least one other systematic investigation in the literature, see below.\n\n- Claim: SI-GNN explanations are \"redundant\".\n    - Evidence: SHD values in Table 1 + convincing examples.\n\n- Claim: SI-GNN explanations \"successfully identify key features but also overemphasize some irrelevant ones\" (p 1)\n    - Evidence: only empirical.  They authors measure the structural similarity between ground-truth explanations and produced explanations in Table 1 for four architectures and on four data sets.  Theoretical guarantees are not provided, and I have strong doubts that any could be given in general, see my example below.\n\n- Claim: Redundancy is difficult to eliminate\n    - Evidence: none of the strategies really help in Table 1.  It is unclear to me whether averaging constitutes a \"difficult strategy\" (it probably does not: it is easy to set up and use.)  Other evidence includes presumably Proposition 4.2, although I do not find the link obvious. [**Q**] Is there any link between Prop 4.2 and the claim?  Could you please explain it clearly?\n\n- Claim: Existing techniques fail to address this challenge\n    - Evidence: +SWA, +EA rows in Table 1.\n\n- Claim: Aggregating explanations from multiple seeds helps\n    - Evidence: ideally, Prop 5.1 and 5.2.  However, the link to the averaging technique makes an (I think) unfounded assumption that members of the ensemble will assign higher score to truly relevant (i.e., plausible) subgraphs, and I could not find evidence for this.", "methods_and_evaluation_criteria": "The choice of data sets, architectures and metrics is appropriate.", "theoretical_claims": "I did look at the proofs in the appendix.\n\n- One issue is that the propositions in the appendix are misnumbered.\n\n- Prop 1: the first two sentences of the proof of Prop 1 do not belong to the proof and should be moved elsewhere (e.g. after the proof).  Also, it seems that the proof assumes that the optimal SI-GNN explanation attains $H(Y|G_s) = 0$, which may not be the case.  If it does, then all supegraphs of $G_s$ (of size up to $K$) will also have zero conditional entropy, but if it does not, they may have *lower* entropy, and therefore $G_s$ is not even an optimum.  [**Q**] What happens in this case?  Why doesn't this assumption appear in the statement of the proposition?  I am confused by what is meant by $G_s$ and what properties it should have.  What does it mean that it is \"optimal\"? According to what criterion?  I also skimmed through (Zhang et al., 2022), but I couldn't find the result you are referencing in p 12.  [**Q**] Could you please provide more precise coordinates?\n\n- Prop 2: the definitions of sufficiency and necessity used here differ from others in the literature (see the openreview link below), but are intuitively sensible.  The claim is otherwise quite intuitive.\n\n- Prop 3 and 4: appear to be correct.", "experimental_designs_or_analyses": "The experimental setup is mostly good.  Table 1 is difficult to read.  The main take-away is clear enough: averaging generally helps (see the sea of green numbers).  But the relative performance of different models and competitors is very difficult to read.\n\nPerhaps I missed it, but I was expecting to see a table or plot showcasing the correlation between reduction in SHD (explanation stability) on one side and improvement in AUC (plausibility) on the other.  Figure 6 seems to indicate that they may be anti-correlated.  [**Q**] Could you please elaborate on this?\n\nI also have a couple of other issues with the experiments, which I'll turn into questions.\n\n- [**Q**] Why did you choose a threshold of $0.5$ for the relevance discretization step?  Does a single constant threshold make sense across models?\n\n- [**Q**] Why did you not evaluate the approach of Deng & Shen empirically? Given that it is supposed to underperform, numerical evidence would have provided further support for your claims. (Note that Proposition 4.2 does not say anything specific about the performance of their method.)", "relation_to_broader_scientific_literature": "The related work does an overall reasonable job at positioning the paper within the context of the broader literature, with out exception, see below.", "essential_references_not_discussed": "The quality of explanations produced by SI-GNNs was also systematically analyzed in a recent paper:\n\n  https://openreview.net/forum?id=kiOxNsrpQy\n\nThere, the authors found that SI-GNN explanations can be \"insufficient\" (which is, to the best of my understanding, equivalent to what the authors call \"redundancy\").  So, this issue was already pointed out.  The paper also proposes several potential solutions, which may be worth mentioning.", "other_strengths_and_weaknesses": "#Strengths\n\n- Clarity: the paper is mostly nicely written and well structured.\n- Significance: it is generally assumed that explanations output by SE-GNNs -- an increasingly popular class of models -- are high-quality, while in practice this may not be the case; this paper tackles this very issue, and as such it is definitely significant.\n- Originality: to the best of my knowledge, the issue identified by the authors is novel.\n- Quality: I appreciated the experiments in 3.1 and 3.2.\n- Quality: standard deviations over 10 seeds.\n\n#Weaknesses\n\n- Clarity: The authors use terms without describing them properly.  For instance, what is an \"optimal\" explanation?  What is the difference between $G_s$ and $G_s^*$?  Moreover, I find it difficult to understand when the authors refer to explanations being high-quality because they are *plausible* (they capture the variables that have a causal role in the data generation process) vs because they are *faithful* (they capture the variables that are causal for the learned model).  Is an optimal explanation faithful? plausible? sufficient?  Also, necessity is only defined in enough detail in the proof of Prop 2.\n- Clarity: [**Q**] How did you determine the truly important edges in Fig 2? At this stage in the paper, this is not clear.  Also, are these edges \"truly important\" for the model or for the data generating process?\n- Quality: The proposed solution is very simple (not an issue), but I think that it fails to really address the core issue.  On the other hand, I see it more as a starting point than as a key contribution, so I am not too concerned about this limitation.", "other_comments_or_suggestions": "- The notion of \"truly relevant edges\" should be introduced in Sec 2 or 3, and it should be clearly linked to plausibility and/or faithfulness, for ease of understanding. (I would expect GNN researchers to be familiar with these notions.)", "questions_for_authors": "Please see my questions above, I marked them with [**Q**].\n\nIn addition:\n\n- p 4: \"In contrast, self-interpreable GNNs [...] and thus more robust to spurious features.\"  I tend to disagree with this statement:  I don't see why SI-GNNs trained on biased data would output explanations that contain no bias.  Imagine that I manipulate the data such that a given subgraph S (say, a star) is strongly discriminative for class 0 (i.e., has ~1.0 correlation with the ground-truth label) in the training set but not in the test set (where I can simply delete it).  In turn, subgraph S would very likely be highlighted by the model's explanations.  Simply \"simultaneously learning explanations and predictions\" (p 4) does not prevent SI-GNNs from picking up subgraph S as relevant.  In fact, concept-bottleneck models -- which are architecturally similar to SI-GNNs, except for image inputs -- are known to suffer from shortcut learning:\n\n  Bahadori and David Heckerman. \"Debiasing Concept-based Explanations with Causal Analysis.\"  ICLR.\n\nand I don't see what would give SI-GNNs an advantage over them.  To me, this sentence seems clearly wrong and I think it should be dropped.  Moreover, I don't see how the mechanisms listed in Sec 2 could fix the issue: finding coincise explanations does not help if the confound is small.  I am very skeptical that SI-GNNs (or any GNN, really) can attain high plausibility -- with guarantees -- unless strongly nudged through supervision or architectural bias.  I would appreciate a clarification.\n\n- The manuscript relies on $G_s$ being a subgraph of $G$, but in practice -- as readily admitted by the authors -- SI-GNNs output continuous per-edge relevance scores, which need to be somehow converted into a subgraph $G_s$.  Does the construction of the discretization step somehow affect the issue of redundancy?\n\nI am willing to **increase my score** provided the authors clarify my doubts during the rebuttal period.", "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": "TMTD8nIzYF", "reviewer": "Reviewer_DDzK", "summary": "The paper aims to systematically investigate trustworthiness of explanations provided by self-Interpretable GNNs. That is, GNNs that simultaneously act as classifiers and explainers. Such GNNs highlight a subgraph as an explanation for a given graph. They provide a brief taxonomy of different  self-Interpretable GNNs. They identify the fact that different GNNs provide inconsistent explanations and not completely trustworthy explanations. \nFor inconsistency, they identify two reasons: (1) training instability and (2) spurious correlations. They show that conventional methods to overcome training instability do not consistently work for GNNs. While they argue that self-interpretable GNNs are better protected against spurious correlations.\nThey also identify redundancy as a key factor for inconsistent explanations in self-interpretable GNNs. \nThey show that the recently introduced criterions for necessity and sufficiency are often not simultaneously achievable. \n\nFinally, they propose an ensemble based aggregation method to get explanations. And formally show that these explanations are more consistent with high probability compared to model level consistency.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. Below we address your concerns.\n\n(1) Robustness of Self-Interpretable GNNs to Spurious Correlations\n\nWe have addressed this in our response to Reviewer 6xUG, where we acknowledge the mistake and clarify our point.\n\n(2) Graph-Level Analysis of EE (Theoretical)\n\nThe graph-level inconsistency is the average of edge-level inconsistencies, which means that **we do not require each edge to independently satisfy the bound in Eq. 6. Instead, the key idea is to show that the average inconsistency decreases, which is sufficient to guarantee overall improvement.**\n\nFor an edge $i$, let $A_i^n \\in [0, 1]$ denote the inconsistency score under EE (with $n$ samples ensemble), and $B_i$ denote the inconsistency score of two individual models (independent of $n$). At the graph level, we aim to bound:\n$$\n\\mathbb{P}\\left(\\frac{1}{|G_s|} \\sum_{i=1}^{|G_s|} A_i^n < B \\right),\n$$\nwhere $B = \\frac{1}{|G_s|} \\sum_{i=1}^{|G_s|} B_i$. Using Hoeffding’s inequality (Eq. 28), we have:\n$$\n\\mathbb{P}\\left(\\frac{1}{|G_s|} \\sum_{i=1}^{|G_s|} (A_i^n - \\mathbb{E}[A_i^n]) \\geq B\\right) \\leq \\exp(-2nB^2).\n$$\nSince $\\mathbb{E}[A_i^n] = 0$ (Eq. 18), we get: \n$$\n\\mathbb{P}\\left(\\frac{1}{|G_s|} \\sum_{i=1}^{|G_s|} A_i^n < B\\right) \\geq 1 - \\exp(-2nB^2).\n$$\nThus, we have established a lower bound on the probability that EE outperforms the vanilla version, and this bound increases with $n$.\n\nUnlike Prop. 5.1, Prop. 5.2 already reflects the graph-level behavior of EE. By setting different definitions for $X$ and $W$, Prop. 5.2 serves different purposes. For instance, we can let $X$ denote the most important irrelevant edge (i.e., the one with the highest score in irrelevant edges) and $W$ denote the least important relevant edge (i.e., the one with the lowest score in relevant edges). Under this setting, Eq. 7 essentially computes the probability that the AUC reaches 100%. \n\n(3) Why EE Works (Empirical)\n\nYou raised a concern that EE might lead to “strange semantics” in explanations, such as highlighting all benzene rings instead of just one. We'd like to clarify that **our goal is to identify all label-relevant structures in the graph. If a molecule contains two benzene rings, both sets of edges should be considered relevant -- this is determined by the dataset’s ground-truth explanations.**\n\nMoreover, the concern that EE might merge overlapping subgraphs into their union is also unlikely in practice. **Same structures tend to receive similar importance scores due to their structural and attribute similarity.** This means that if multiple benzene rings exist, their scores will generally be close (see Figure 5). Similar cases can be observed in GSAT’s results (e.g., Figure 3 and Figure 10 in their paper).\n\nThe key reason why EE is effective is that truly important edges consistently receive high weights, so their average remains high. In contrast, irrelevant edges exhibit variance and tend to have lower average importance after EE. In other words, EE does not simply merge explanations -- it refines them by leveraging ensemble averaging to filter out noise.\n\n(4) Evidence that Conciseness Constraints are Overly Relaxed\n\nAs mentioned in Line 178, classic self-interpretable methods like DIR and GSAT recommend retaining 50%-80% of edges to achieve a desirable trade-off between training stability and explanation conciseness. Additionally, our experimental results provide strong evidence of this issue (see Figure 2 and Figure 3).\n\nWe appreciate your time and feedback, and we hope our rebuttal addresses your concerns. We look forward to any further discussions if needed. Thank you!", "claims_and_evidence": "Claim 1: GNN extracted explanations not trustworthy due to inconsistencies emerging from:\n- C1.1 Training instability \n- C1.2 Spurious correlations: \n- C1.3 Redundancy \n\nEvidence: The paper provides strong empirical evidence for C1.1 and C1.3. About claim C1.3 --- I agree with the larger message that spurious correlations can lead to misleading explanations. \nBut I do not see why authors claim \"In contrast, self-interpretable GNNs simultaneously learn explanations and predictions, naturally embedding explanations into the model’s decision-making process and thus more robust to spurious features.\" I think if the point is that Self-interpretable explanations are more faithful to how the model works, then this statement is true. However, I believe SE-GNNs are not less likely to learn a model (and hence explanations) based on spurious correlations.  \n\nClaim 2: Ensemble of explanations  lead to lesser inconsistency than normal explanations. \n\nEvidence: The authors show this result theoretically by bounding the inconsistence in the ensemble explanations wrt the conventional explanations (Prop 5.1). And they also show that with high probability relevant edges will be distinguished from irrelevant edges. \n\nI do not think that the proof/claim are wrong. But I am not sure the results really reflect the true picture, my main concern is that the amount of samples required to make sure that Prop 5.1 and Prop 5.2 on graph level (i.e. for all edges w.h.p) will be quite high (one will additionally need a union bound to show this), and this analysis should be done and presented.", "methods_and_evaluation_criteria": "The paper is a relatively easy read. Theoretical claims are clearly presented and experimental results are well-explained.", "theoretical_claims": "Theoretical claims are clearly presented in the paper. Although the proofs are in the appendix the statements are clear, plausible and relatively clear to see given the larger context of the paper.\n\nMy main theoretical concern is regarding Prop 5.2 and Prop 5.1, and are explained above.", "experimental_designs_or_analyses": "- The paper empirically evaluates the inconsistency between explanations over different random seeds. And compares consistency of  ensemble based explanations to other explanation methods using Structural Hamming Distance (SHD) \n\n- They also compare their approach against other methods wrt accuracy of the explanation.", "relation_to_broader_scientific_literature": "The paper is quite relevant to the larger GNN explainability literature.", "essential_references_not_discussed": "I think all the reasonably relevant paper are cited.", "other_strengths_and_weaknesses": "Strengths:\n- The paper is quite clearly written and makes some pertinent observations regarding self-interpretable GNNs.\n\nWeakness:\n\n- I see two main weakness: \n(1) (Minor) The theoretical results (Prop 5.1 and Prop 5.2) are quite remote from actually supporting  the experiments. I think the number of samples required wrt these results would not justify your experimental observation of requiring only 2 runs. I believe the real reason for superior results wrt accuracy is that you potentially capture a large sufficient explanation, by aggregating many of them.\n\n(2) (Major) I think aggregating over explanations could potentially lead to strange semantics for explanation, so lets say one benzene ring suffices to classify a molecule into a positive, with the EE, one will highlight all possible benzene rings in a positive molecule and not just one. But stranger things may happen when you have over-lapping subgraphs as potentially different explanations, your method may highlight their union.", "other_comments_or_suggestions": "-- Implications of Prop 5.1 and Prop 5.2 should be given a more nuanced analysis\n-- The formal notion of explanations captured by EE should be discussed, if not completely formalized. I think having a better understanding of what these explanations represent is fundamental to the quality of this paper.", "questions_for_authors": "-- I may have missed this, but I did not understand where you show that conciseness constraints are set overly relaxed in other explainability methods?", "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": "f3bDIaG5JQ", "reviewer": "Reviewer_CmNK", "summary": "The paper tackles the fundamental challenge of verifying whether explanations extracted by self-interpretable models, which are considered to be more trustworthy by design, are so.\nThe authors highlight an issue with current approaches by providing the intuitive example (Fig. 1) of how simply changing the random seed of the model results in quite inconsistent explanations, raising concerns about their utility for model understanding. The authors identify redundancy as the root cause of this problem and test three different mitigation strategies. Among the three, only one achieves consistently good results, which involves an ensemble of explanations. The rationale of this idea is that averaging multiple explanations from diverse models can filter out noise/spurious correlation, yielding better explanations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. Below we address your concerns.\n\n(1) Overstatement of the First Systematic Investigation\n\nWe have addressed this in our response to Reviewer 6xUG, where we acknowledge the mistake and clarify our intent.\n\n(2) About Evaluation Metrics\n\nFaber et al. (2021) argue against removing-based evaluation and support ground-truth explanations. They suggest using datasets with reliable ground truth (please see Sec 2.2 and Sec 7 in their paper). **We acknowledge that ground-truth explanations can sometimes be misleading, so we were highly selective in choosing datasets and only included four well-established benchmarks that have been extensively validated in the community:** BA-2MOTIFS and MUTAGENICITY have been used in GNNExplainer, PGExplainer, DIR, and GSAT, and they use AUC for evaluation. For 3MR and BENZENE, Rao et al. (2022) -- the creators of the 3MR dataset -- also use AUC. We also manually inspected models' outputs to ensure that the ground-truth explanations reflect the knowledge encoded in model and that no shortcuts is learned (some works questioned the validity of the MUTAGENICITY, e.g., Both NO2 and NH2 are important, but explainer may detect only one of them, we have verified that such issues never occur in our experiments).\n\n**EE is indeed not compatible with FID, but this was not the reason we opted against FID. EE is just a first step, and future solutions may not require ensembling.** While RFID mitigates OOD, it does not fully eliminate it and compromises evaluation effectiveness (i.e., no OOD = invalid evaluation). As long as OOD exists, FID-based metrics assess not only explanation quality but also the model’s generalization ability [3], introducing confounding factors that weaken the objectivity of the evaluation. AUC vs. FID has long been debated, and neither is perfect. The key contribution of our work is to raise awareness in the community that redundancy in explanations weakens explanation quality. Given (1) the specific nature of our task (we need ground-truth to assess redundancy -- Figures 2, 3), (2) that AUC’s limitations can be fully addressed in certain cases [5], and (3) that the FID's limitations can't be fully addressed (to date), we ultimately chose AUC and just feel that SHD and AUC are enough to support our findings.\n\nPS: Beyond OOD, redundancy also weakens the validity of FID-based metrics -- in the most redundant case (i.e., $G_s = G$), FID metrics achieve trivially optimal scores (see Sec. 5.1 in [5]). Some alternatives, such as H-FID in GStarX and advanced Nec in [3], could potentially be used to evaluate redundancy but require careful design. We prepare to include a more detailed discussion in the revised version.\n\n(3) Unavoidable Redundancy\n\nWe understand your concern. Our work investigates all relevant techniques to date and, through a combination of theoretical and empirical analysis, demonstrates that redundancy is challenging to eliminate (via existing techniques). Specifically: (1) Figure 3 and Prop. 4.1 illustrate why tuning hyperparameters cannot eliminate redundancy; (2) Figure 4, Prop. 4.2, and Table 2 show the limitations of the +CL. We will revise the subsection title to “On the Difficulty of Eliminating Redundancy” and hope this addresses your concern.\n\n(4) Responses to Other Concerns\n\n- Causal Learning for Interpretable GNNs: Thank you for your comment. We will revise it accordingly.\n- Equation 1: The goal of GNN explanation is to identify subgraphs that are both informative and concise. You are correct that some methods optimize for different objectives, but some papers define the GNN explanation task more generally (see Definition 2 in [5]). Even GSAT, though it constrains subgraphs from an MI perspective, still imposes a size constraint in a broader sense (see discussion in https://github.com/Graph-COM/GSAT/issues/2). We are open to revising the paper based on your suggestion.\n- Definition in Prop. 1: The crucial subgraph is the ground-truth explanation $G_s^*$, and a valid explanation must include $G_s^*$ while also satisfying the size constraint (i.e., $G_s^* \\subseteq G_s$ and $|G_s| \\leq K$).\n- Definition of strictly necessary: An edge is strictly necessary if its removal alone significantly impacts the prediction.\n- Model Types and Figure 4: Type I is Attention, Type II is GISST, Type III is CAL, and Type IV is GSAT. The underlying backbone is implemented using GSAT, with slight modifications to accommodate others. In Figure 4, we use Type I for evaluation (other types yield similar results, which we can provide in the revised version if needed). We plot the contrastive loss during training. \n- $h_{G_s}$ generates $G_s$, uses it as input, and outputs a graph representation.\n- Run 1 in Figure 1: The three-membered ring is also present in the other class. \n\nWe appreciate your time and feedback, and we hope our rebuttal addresses your concerns. We look forward to any further discussions if needed. Thank you!", "claims_and_evidence": "The claims of the paper are generally fairly well supported by arguments and experiments, except for the following cases:\n\n- While I agree that the analysis on the redundancy and inconsistency issue of explanations is novel, the first sentence in the abstract sounds a bit of an overstatement. In fact, this is not the first work studying the trustworthiness of explanations extracted by self-interpretable GNNs [1,2,3]. I have a similar concern in line 74 of the Introduction.\n\n- In the Type II paragraph of Section 2.2, the authors say that Causal Learning for interpretable GNNs aims at identifying\nthe essential parts that are responsible for the classification while ensuring that the remaining parts have no influence on the model’s output. This is, however, a shared design principle of self-interpretable models which all try to highlight the relevant portions for predictions. I would rather stress the fact that Causality-based approaches aim at learning truly causal patterns that go beyond pure spuriosity-prone statistical correlation.\n\n- The authors claim that redundancy is somewhat unavoidable. However, they seem to be testing only a limited set of mitigation strategies, and they do not provide strong theoretical results to support this statement, making this claim not well supported in my opinion.", "methods_and_evaluation_criteria": "Authors claim that \"datasets with ground-truth explanations provide a reliable benchmark for comparison\". However, ground truth explanations are reportedly found to be potentially misleading, as pointed out in (Faber et al. 2021) and [4]. In general, when comparing against an explanation ground truth, it is required to ensure that the model actually learned the expected ground truth, but this issue seems not to be addressed in the paper.\n\nPerhaps more importantly, the paper does not provide any analysis on the faithfulness of the resulting explanation, constituting a major lack in the experimental investigation of the trustworthiness of explanations.", "theoretical_claims": "I did not find major issues in the theoretical claims. Below are some on-point comments:\n\n- Equation 1 formalizes only self-interpretable models with explicit size constraints (<=K), but there exist models that optimize for other objectives, like GSAT (Miao et al., 2022). In fact, in Section 2.2 the authors correctly distinguish between different training methodologies, making Equation 1 not very precise.\n\n- In the statement of Prop. 1, the meaning of \"crucial subgraph\" and \"valid explanations\" should be clarified. Albeit intuitive, the formality of the statement would benefit.\n\n- Similarly to above, the notion of \"strictly necessary\" is not defined.", "experimental_designs_or_analyses": "In \"Run 1\" of Figure 1, the authors point out that the triangle is erroneously highlighted as important by the model, and they claim that this proves the inconsistency issue outlined in the paper. However, it remains unclear whether such a three-membered ring is indeed not correlated with the label and whether it is in fact a portion of the input that the model is *not* using. In fact, if the dataset presents some biases, such a triangle might be spuriously correlated with the label, and the model might be *authorized* to exploit it, resulting in the explanation for \"Run 1\" as a faithful explanation for a model affected by spurious correlation.\n\nOther than that, I found the experimental results hard to follow and to contextualize, in the sense that it is not clear which is the model under investigation. In Tables and Figures, in fact, authors refer to the tested models as Type I/II/III/IV. However, it is not clear which is the underlying model implementation being in use (GSAT vs DIR vs ...). It would be beneficial to refer to the individual architectures with their name to improve clarity.", "relation_to_broader_scientific_literature": "To the best of my knowledge, there is no prior work studying explanations of self-interpretable GNNs under this lens. However, the paper fails in contextualizing it with some recent findings in the literature of analyzing the trustworthiness of explanations of those models, like [1,2,3,5].", "essential_references_not_discussed": "In line 35 of the Introduction, the authors ask whether Self-interpretable GNNs \"truly live up to expectations?\". While this is an interesting question, it should be noted that this work is not the first to pose this problem, as investigated in [1].\n\nList of missing key references:\n\n[1] How Faithful are Self-Explainable GNNs?\n\n[2] How Interpretable Are Interpretable Graph Neural Networks?\n\n[3] Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs\n\n[4] XAI and Bias of Deep Graph Networks\n\n[5] Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks", "other_strengths_and_weaknesses": "The paper is well-written and clear. Also, figures are curated and well presented, albeit captions are often not self-explanatory.\n\nThe mitigations implemented in this work are relatively new in the context of GNN explanations, but they seem not to bring solid empirical evidence, leaving open the question of whether redundancy is really unavoidable. On the same vein, the proposed solution of averaging explanations from multiple models is very easy, and albeit working well in practice, little is discussed about the limitations in terms of faithfulness of the resulting explanation and the utility of this ensable in debugging model behaviour. Therefore, to me, the practical benefits of the proposed solution for an end user remain unclear.", "other_comments_or_suggestions": "- The caption of Figure 4 should be self-contained: (i) Which is the model under investigation? (ii) Is the loss referred to train or validation split? (iii) Is the entire loss plotted or only the explanation regularization loss? If the entire loss is plotted, are you sure that the instability is caused by the difficulty in differentiating positive vs negative samples and not by BENZENE being more difficult to fit?\n\n- $h_{G_{s}}$ is not defined in Equation 1", "questions_for_authors": "1. How does the Explanation Ensamble solution affect the computation of other metrics for explanation quality, such as Faithfulness/Fidelity? My feeling is that since the explanation is aggregated over different models, it is no longer possible to evaluate how faithful the explanation is wrt a single model.\n\n2. Regarding the experiments with known ground truth, do the authors check that the ground truth is actually the knowledge encoded in the model being explained and that no shortcuts have been learned? Can you please argue about the impact that this may have on your evaluation?\n\n3. Regarding Run 1 in Figure 1, can you please argue or provide evidence regarding the fact that the model is indeed not using the triangle to predict the class? For example, an argument would be to show that such a three-membered ring is in fact present also in the other class.\n\nI updated my score from 1 to 3 after the rebuttal by the authors that addressed most of my concerns.", "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:

Meta-review: This paper presents the first systematic investigation into the trustworthiness of explanations generated by self-interpretable graph neural networks. It demonstrates that models trained with different initialization still recover the same meaningful features, while introducing some spurious ones. By aggregating, it is posible to improve the detection of relevant features. 

The reviewers are all in agreement that this is valuable work, supported by solid evidence.
Decision: Accept (poster)