Certified Evaluation of Model-Level Explanations for Graph Neural Networks
Authors: Sayan Saha
Sanghamitra Bandyopadhyay
Venue: ICLR 2026 Poster (2026)
Keywords: Model-Level Explanations for GNNs
Theory of XAI
Evaluation of GNN Explainablity
Primary area: interpretability and explainable AI
TL;DR: This paper proposes a suite of measures for evaluating model-level explanations of GNNs which complement class score and provide a principled basis for comparing model-level explainers.

Abstract: Model-level explanations for Graph Neural Networks (GNNs) aim to identify class-discriminative motifs that capture how a classifier recognizes a target class. Because the true motifs relied on by the classifier are unobservable, most approaches evaluate explanations by their target class score. However, class score alone is not sufficient as high-scoring explanations may be pathological or may fail to reflect the full range of motifs recognized by the classifier. To bridge this gap, this work introduces sufficiency risk as a formal criterion for whether explanations adequately represent the classifier’s reasoning, and derives distribution-free certificates that upper-bound this risk. Building on this foundation, three metrics are introduced: Coverage, Greedy Gain Area (GGA), and Overlap which operationalize the certificates to assess sufficiency, efficiency, and redundancy in explanations. To ensure practical utility, finite-sample concentration bounds are developed for these metrics, providing confidence intervals that enable statistically reliable comparison between explainers. Experiments on synthetic data and with three state-of-the-art explainers on four real-world datasets demonstrate that these metrics reveal differences in explanation quality hidden by class scores alone. Designed to complement class score, they constitute the first theoretically certified framework for evaluating model-level explanations of GNNs.

Published as a conference paper at ICLR 2026
CERTIFIED EVALUATION OF MODEL-LEVEL EXPLANATIONS FOR GRAPH NEURAL NETWORKS
Sayan Saha
Sanghamitra Bandyopadhyay
Machine Intelligence Unit Indian Statistical Institute, Kolkata sayansahal 1 81 111996 96 gma i1 com
Machine Intelligence Unit Indian Statistical Institute, Kolkata sanghami @ Rist dical... ac.in
ABSTRACT
Model-level explanations for Graph Neural Networks (GNNs) aim to identify class-discimiinatie motifs that capture how classifier recognizes a target class. Because the true motifs relied on by the classifier are unobservable, most ap- proaches evaluate explanations by their target class score. However, class score alone is not sufficient as high-scoring explanations may be pathological or may fail to reflect the full range of motifs recognized by the classifier. To bridge this gap, this work introduces sufficiency risk as a formal criterion for whether expla- nations adequately represent the classifier's reasoning, and derives distribution- free certificates that upper-bound this risk. Building on this foundation, three metries introduced: Coverage, Greedy Gain Area (GGA), and Overlap which operationalize the certificates to assess sufficiency, efficiency, and redundancy in finite-sample sample concentration bounds are developed for these metrics, providing confidence intervals that enable statisti- cally reliable comparison between explainers. Experiments with synthetic data and with three state-of-the-an explainers on four real-world datasets demonstrate that these metrics reveal differences in explanation quality hidden by class scores alone. Designed to complement class score, they constitute the first theoretically certified framework for evaluating model-level explanations of GNNs.
explanations. To ensure practical utility, finite-
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as powerful models for learning from graph- structured data, achieving state-of-the-art performance in diverse domains such as drug discovery (Merchant et al., (023), weather forecasting (Lam et al., 2023) and social network analysis (Wul et al.))2222) Despite these successes, the opaque nature of GNNs pose significant challenges in high-stakes applications, where understanding why a prediction is made is as important as the pre- diction itself. This has driven rapid progress in research post-hoc explainability methods for GNNs. Broadly, post-hoc GNN explainability approaches fall into two categories (Kakkad et al.)
2023): 1: instance-level and model-level methods. Instance-level methods (Pope et al. 2019 Feng
et al.
2023 Baldassarre & Azizpour, 2019 HHuang et al.] [002]] Schlichtkrull et al. 2020 Yuan
al. 2021 Lucic al. [2022] Lin al., [2022] Zhang et al. 2021]
; Vu Thai 2020 are devised
to explain the prediction on a single instance by highlighting salient nodes and edges that most in- fluenced the outcome. However, such explanations lack generalizability, since insights drawn from one instance may not extend to others. Hence, achieving a global understanding of model behaviour requires inspecting instance- levell explanations across numerous instances, which is costly and un- reliable. In contrast, model-level explanations( Yuan et al. 2020 Wang & Shen 2023; Shin et al.) 2024) aim to provide a global view of the classifier's behavior. Given target class, they seek to identify key discriminative motifs that the model consistently relies to recognize instances of the class. These motifs provide a high level view of the classifier's 's behavior, reducing the need for exhaustive inspection and offering more coherent picture of what the model has learned.
Model-level explainers typically work by either discovering or generating key class discriminative motifs. While each approach differs in their mechanism, uniform objective all of them share is to generate motifs that attain high target class scores. Since the true patterns that a classifier relies on to identify class unobservable, motifs which the classifier assigns high class scores are in-

---

Published as a conference paper at ICLR 2026
terpreted as representative of the discriminative information using which the model has learned to recognize instances of the class. Consequently, the quality of a model-level explanation is typically judged by the score it receives from the classifier, making the target class score the primary met- ric for comparing explanations and the methods that generate them. However, class score alone is insufficient to distinguish between explanations. Since every explainer explicitly optimizes loss term that rewards high target class scores, the resulting motif's often become pathological: they achieve high scores but stray far from the data distribution and may bear little resemblance mean- ingful graph structures. In the absence of more principled metrics, researchers frequently resort to qualitative inspection where consensus is elusive and comparisons are vulnerable to cherry-picking Other than qualitative comparison between explanations, researchers also rely on auxilliary mea- sures such as time required to generate explanations, sparsity of the explanations and comparison between graph statistics of real graphs and the generated explanations. While useful, these auxiliary measures do not directly assess explanation quality, since they ignore the relationship between the motif's and the classifier's decision process. It should also be noted here that common measures of explanation quality for instance-level explanations such as fidelity and accuracy style metrics are not directly applicable in this setting. Fidelity style metries typically involve operations like removing the explanation subgraph or corrupting input features while preserving the explanation. However, model-level explanations, especially those produced by generative methods rarely appear as exact subgraphs of any graph in the class, making such operations infeasible. Accuracy. on the other hand, requires ground-truth explanation subgraphs for comparison. Yet in the model-level setting, the true motif relied upon by the classifier is unknown, rendering this measure inapplicable as well. This leaves a fundamental gap in principled evaluation of model-level explanations.
This work closes this gap by introducing a principled and computable suite of metrics for evaluating model-level explanations. We begin by characterizing when set of explanations generated by a model-level explainer can be said to sufficiently capture the classifier's ss decision process, formaliz- ing sufficiency through a risk functional and deriving distribution-fret certificates that upper-bound this risk. The first metric, Coverage, measures how much of the class manifold in the classifier's embedding space is accounted for by the explanations, thereby providing a certified bound on suf- ficiency risk. To assess how efficiently coverage is accumulated, we propose the Greedy Gain Area (GGA), which connects to guarantees on prefix coverage, motif budgets, and certified sufficiency under motif constraints, while also diagnosing when coverage has stagnated. We further introduce Overlap, which captures redundancy between motifs that explain the same regions. Since these quantities are estimated from finite samples, also derive uncertainty bounds that yield confidence intervals, ensuring that comparisons between methods remain statistically reliable. Through exten- sive experiments, we demonstrate that our metries reliably complement the class score, enabling meaningful distinctions between explanations that would otherwise appear equivalent. Moreover, we show that they can diagnose common pitfalls, such as pathological motifs that drift away from the data distribution and cases of mode collapse where explanations fail to capture the full diversity of patterns learnt by the classifier. To the best of our knowledge, this constitutes the first principled framework with theoretical certificates for evaluating model-level explanations of GNNs.
2 RELATED WORK
Model-Level Explanations. Compared to instance-level explanations, model-level explanations for GNNs remain relatively underexplored. Existing approaches can be broadly categorized into generation-based and discovery-based methods. Generation-based methods employ graph gener- ative models to synthesize dlas-discriminntive motifs. Representative examples include XGNN Yuaan et al., 2022)). which uses reinforcement learning to construct motifs node by node; GNNInter- preter (Wang& & Shen (023). which leverages a probabilistic generative model;
(Saha & Bandyopadhyay), D4Explainer (Chen et al., 2023), and MAGE (Yu & Gao 2025). which employ graphon- based, ciffiusionbbasedd and masif-based generation strategies respectively. While such methods optimize for high class scores and incorporate distributional constraints, they still yield pathological motifs not representative of the underlying data distribution. Discovery- methods, such as PAGE and GLGExplainer (Shin et al. 2024 Azzolin et al., 2023), argue that gen- erative explainers are inherently prone to such pathologies and instead identify motifs directly from the dataset, either by selecting discriminative subgraphs already present in instances or by aggre- gating instance-level explanations. While this avoids unrealistic motifs, there still remains the need
2

---

Published as a conference paper at ICLR 2026
to evaluate whether the extracted patterns generalize across instances in the class, underscoring the need for principled metrics to assess explanation quality.
Metrics for Evaluating GNN Explanations. Existing evaluation of GNN explanations combines domain-specific criteria with quantitative metrics such as accuracy, fidelity, faithfulness, sparsity, and consistency. Considerable theoretical analysis has highlighted their limitations and proposed refinements, but all such work remains confined to instance-level explanations. Examples include upper bounds on worst-case performance (Agarwal al. 2022), robust fidelity under distribution shifts (Zheng et al., 2024), characterization scores combining fidelity measures (Amara et al., 2022). and robustness- bases metries (Fang et al.) 2023). Complementary benchmarking efforts (Kosan iet al. [2024; AAgawaa et al. 2023) systematically compare instance-level explainers across diverse datasets and highlight which metrics are reliable in different settings.
Despite this progress, no principled evaluation framework exists for model-level explanations. A few works have highlighted the pitfalls of relying solely on class score: [Wang Shen (2023) and Chen al. (2023) observe that high-scoring explanations may be pathological and drift from the data distribution, while |aha & Bandyopadhyay identify mode collapse, where explainers generate only variations of single motif despite the classifier relying on diverse patterns. These approaches attempt to mitigate such issues by adding training constraints, but they stop short of introducing metrics that can directly diagnose the issues they highlight.
PRELIMINARIES
We begin by formalizing when a model-level explainer can be considered to sufficiently capture how a classifier f()) identifies instances of a target class Given a target class a model-level explainer outputs an explanation set E. = (,M1...,,M ). where each motif M, E. is intended to represent a discriminative substructure that the classifier relies on to recognize graphs of class c.
Scope of explanation objects. In this work we use the term motif in broad sense to denote any explanation object that can be mapped to the embedding space of the classifier. This includes extracted subgraphs, prototype instances, generated graphs, or rule instantiated examples produced by model level explainers. The proposed metries operate only the embeddings of these objects. Therefore the framework applies uniformly all model -level explainers, as long as their outputs can be embedded by the underlying GNN.
Denote by G. the set of input graphs that the classifier has identified as belonging class Then, the premise of model-level explanation is that for each graph G Se, there exists membership function (G, Ee) that specifies how motifs in Eg are internally associated by the classifier to G when assigning class c. In the simplest case, M (G, Ee) may be binary vector in {0, 13K, where the i-th entry indicates whether motif M, is used in the classifier's 's reasoning for G. More generally, M (G, may encode soft or probabilistic associations. If E. truly captures the reasoning of the classifier, then the membership codes {M*(G, Ee): G G.J should contain sufficient information } for graphs in G.. Note that the true membership function M* is not observable, hence in practice computable surrogate M must be used as an approximation of M
to reconstruct the classifier's 's output scores {fa(G)}
Notational Simplification: Since, the explanation set Eg remains fixed throughout our analysis, whenever we denote the input for membership function M, we write M (G) in place of M (G. E.).
Sufficiency risk. is defined as
Given a membership function M and an explanation set E,, the sufficiency risk
SR,M,, B B - |M(G))
2(G)))² G Ge].
where fG) is the classifier's 's score for class e and (G) | MG)] its conditional expectation given the membership code. This risk quantifies the predictive information lost when G is replaced by its membership representation under M. Low values of (M E.) indicate that motifs faith- fully capture the classifier's reasoning, with (R F..) = 0 denoting an optimal explanation.
3

---

Published as a conference paper at ICLR 2026
4 METRICS FOR EVALUATING MODEL-LEVEL EXPLANATIONS
As noted earlier, the true membership M unobservable, so the true sufficiency risk S SR. Fic) cannot be computed directly (see Appendix P for why we chose this formulation of sufficiency). We therefore consider proxy memberships .M induced from the explainer's motifs Es, which ap- proximate M but are inherently noisy. One might ask why we do not simply compute the surrogate (R, Ec). since both M() and fe(G) are observable. This is feasible in princi- ple as (M, Ea) is the mean squared error between fe(G) and its prediction from M(G) us- ing E[L(G) MG)] However estimating the conditional expectation term requires a high- dimensional regression, which is statistically unstable, sensitive finite samples, and yields no certified guarantees. A low empirical risk may reflect estimation error rather than genuine suf- ficiency. For these reasons, we propose computable metrics that serve as distribution- upper bounds on sufficiency risk, thereby providing reliable certificates of explanatory adequacy.
At this point, it important to emphasize that, a priori, there no guarantee that the sufficiency risk under proxy membership M has any meaningful relation to the risk under the true membership M Without such a connection, bounding SR,(M, Ee) would say nothing about the unobservable quantity SR.(M* Ee). The following theorem establishes precisely this link: it shows that the sufficiency risk with any proxy membership is always greater than or equal to that with the true membership. Hence, the risk under M is always upper bounded by the risk under any proxy M.
Theorem 1. Fix Er. Let Y = Se(G). Let (G) be the (unobservable) true membership relative to Ee, and let M(G)= = h(M*, :) be any proxy membership with 1 Y M Then SR,(M, Ee) S
SR,MM, Ee), with equality if and only if Var(E [M]] M) = 0 almost surely.
The proof is deferred to Appendix B.1 Theorem I establishes the ground for introducing proxy membership function and the first metric Coverage using which the sufficiency risk under the proxy membership be upper bounded.
4.1 COVERAGE
To make sufficiency risk estimable, we introduce a structured proxy membership M, based on the graph embeddings of the target class and the embeddings of the explanation set E, (MM....,Mxk Let f = H o e where o : G + Hd is the classifier's embedding function, and write my == ((M²) for the embedding of each motif. For graph G, define its nearest-motif distance D(G, Ex) == min; [Iő(G) m& mll12.
The proxy membership is then the function M,: 14 x E. + {I,.... [}
arg mine (l) - mella, Df E.) Sr,
M, G,
otherwise,
where the null code 1 indicates that G is not assigned any motif. For clarity, we will simply write M, (G) and DGG) in the remainder of the paper, with the dependence on E, left implicit.
Intuitively, GG) attaches each graph to its closest motif within radius r, and leaves it uncovered otherwise. Note that M, is constructed solely from embeddings and does not use any information beyond what is available to the true membership M Hence, conditioned on the true membership M the residual noise in M, is independent of Y satisfying the assumption in Theorem !| Definition (Coverage). Coverage is the conditional probability that class-c instance covered by some motif.
Covo(r) = (::)::==PPD)) S GE {
High coverage means most positive instances for class c are explained by motifs in Ec, whereas low coverage indicates explanatory insufficiency.
Theorem 2 (Bounding Sufficiency Risk with Coverage). Assume the classifier head H in the factorization f = H o à is L-Lipschitz on ((G). Then for any r > 0, the sufficiency risk under the proxy membership M, satisfies SRe,M,, Ec) S L' 1(G)) <r) G + (1 Covvlr)) Moreover, since D(G)² < x² whenever D(G) S r, obtain the coarser bound (R,, Fe) T Cove(r) (1 Cova(r)).
4

---

Published as a conference paper at ICLR 2026
The proof is deferred to Appendix B.2 Theorem 2 establishes computable coverage- basead cer- tificate for the sufficiency risk of explanations. A natural question is: for which choice of radius r does this bound become tightest? The following result shows that the optimal choice is the universal radius r* = 1/L2,, independent the distribution of D(G).
Theorem (Optimal radius for the coverage certificate). Under the setting of Theorem con- sider the coverage-bast based bound
B(r) = 1. I'E (((G) Gr) + (oC-Cvr(r)).
Then Brr) is minimized at r*
1
2L'
The proof is deferred to Appendix B33 The result of Theorem extends verbatim to a scale- invariant, angular formulation on normalized embeddings (Appendix A which is used in practice compute the Coverage. Together, these results imply that evaluating explanations at radius r* yields the tightest certified guarantec sufficiency risk, regardless of the underlying distribution of dis- tances. The Lipschitz condition required for Theorem 2 is mild, since classifier heads such as linear layers shallow MLPs with standard activations are Lipschitz and admit efficient spectral-norm based estimates (Xu & Sivaranjani 2024). While the existence of such an L. suffices for the cover- age bound, its explicit value becomes relevant only in Theorem where determines r*.
4.2 GREEDY GAIN AREA: MEASURING DISTRIBUTION OF COVERAGE
Coverage at the optimal radius r' provides certified upper bound sufficiency risk, but it does not reveal how this coverage is distributed across motifs. An explainer may achieve its coverage by relying almost entirely on single motif, leaving others redundant, it may distribute coverage more evenly across motifs. To capture this, we introduce the Greedy Gain Area (GGA).
Formally, given Eg (M1..... MM }. ((M)) [[x(G) - m S r*) as the of class-c graphs covered by motif Mj. We construct greedy set cover by iteratively selecting motifs: at step j. the motif that yields the largest marginal increase in coverage is chosen. Let I S (l...., K} denote the set of selected motif indices after j steps. The cumulative coverage fraction after j motifs then aj
and radius r*, define Se(r*) = {G go:
UREI, Se((*)/ j= K.
Definition (Greedy Gain Area). The Greedy Gain Area (GGA) of E, at radius r* the normal- ized area under the greedy coverage curve:
1
GGA(E,.
K
GGA measures how efficiently motifs contribute to coverage: is high when a few motifs account for most of the explanatory power and low when many motifs are required. Its maximum value equals the coverage attained by the explainer. When coverage high, a GGA value close to cov- erage indicates parsimonious explanations where few motifs suffice, whereas a low GGA reflects diversity with many motifs contributing. When coverage is low, a GGA value close to coverage signals mode collapse, with one motif dominating, while low GGA denotes poor explanations that are neither sufficient nor diverse.
GGA also admits formal guarantees: it certifies how much coverage is retained when only fixed budget of motifs is used, and it bounds the resulting sufficiency risk. These guarantees, together with full statements and proofs, are presented in Appendix C
different question concerns whether generating additional motifs beyond the given set could still improve explanatory sufficiency. To address this, examine the greedy coverage curve: once its marginal gains stagnate, further motifs cannot significantly reduce the certified sufficiency risk. In such cases, the explainer can be considered to have already reached its maximal achievable coverage, and producing further motifs yields only marginal benefits. The next theorem formalizes this idea.
Theorem 4 (Diagnostic stopping criterion from stagnation). Let {ay be the greedy coverage curve at Y" with marginal gains A = aj - aj-1 and final coverage a = Cov,(r*). Fix t e (1. (1...., K} and suppose the curve stagnates after motifs in the sense that A; S for all j > L. Let
5

---

Published as a conference paper at ICLR 2026
Ec be the first l motifs under greedy selection and E,, the full of molifs. Then, under the setting of Theorem? 2 SR.,Mr E (Mr,
(aa-aap Σ 1/2 (K - -. In particular, once the marginal gains flatten below the certified benefit of adding the remaining motifs is at most [ - t)c. Thus stagnation serves as a diagnostic that the explainer has already achieved essentially all of the coverage can provide.
In practice, after generating K motifs, one may inspect the greedy coverage curve. If the curve has already stagnated, Theorem guaranteess that producing further motifs cannot yield a meaningful reduction in sufficiency risk. Hence, the curve itself provides diagnostic criterion for deciding when explanation generation can be safely terminated.
4.3 OVERLAP
Even when an explanation set achieves high coverage, different motifs may end up covering largely the same subset of graphs. Such redundancy inflates apparent explanatory capacity without actually broadening the scope what is explained. To make this effect explicit, we introduce the Overlap metric, which measures the degree to which motifs provide duplicated rather than complementary coverage.
Definition (Overlap). At radius r", define
Σ -1(())) U(r*) Sa("". max max(1,||((r*))
K
Overlap =
k=1
The numerator measures redundant coverage across motifs, while the denominator normalizes by the effective domain size. Overlap takes values in [0, K 11, with 0 indicating no redundancy and K - 1 indicating complete redundancy.
Taken together, the three metrics provide a holistic evaluation of model-level explanations: coverage certifies sufficiency, GGA characterizes how coverage is accumulated across motifs, and overlap explicitly quantifies redundancy. An analysis of the computational cost of these metrics can be found in Appendix FF) We now turn their empirical estimation, analyzing how reliably these population metrics can be approximated from finite samples.
4.4 FINITE-SAMPLE CONCENTRATION OF THE METRICS
The metrics of coverage and greedy gain area are defined as population quantities, i.e., expectations with respect to the distribution of class-c graphs. In practice, however, only observe finite sample G. = (G....., G,) of size n. To make reliable use of such finite data, we derive concen- tration bounds that quantify the estimation error of the empirical metrics Cov, and GGA. These bounds quantify the maximum deviation from the population values at any chosen confidence level 5, effectively yielding confidence intervals whose width shrinks with Equivalently, they pro- vide confidence intervals that support principled comparison between explainers. Non-overlapping intervals imply statistically distinguishable performance the population level.
probability statements below are with respect to the randomness of drawing these graphs i.i.d.
from the conditional distribution given G E go.
Concentration Bounds for Coverage: Let, X, 1(D(G,) < r} be random variable. At the population level, the true coverage is the expectation Cov.(r) = E[X,] However, at the empirical level, with observed graphs, coverage is estimated by the sample average Cova(r) / Σm E X;. The next result quantifies how close this empirical estimate to its population counterpart.
Proposition (Concentration of coverage). For any 8 (0, 1), with probability least 5, (ovv(r) Cov.(r))
log 2
2n
Concentration Bounds for GGA: As with coverage, GGA can be defined at both the population and empirical levels. At the population level, let a denote the expected coverage after selecting motifs according the greedy procedure. Then the true GGA is GGA R Ey=

---

Published as a conference paper at ICLR 2026
At the empirical level, with n observed graphs, the coverage after motifs is given by āy. and the corresponding estimate of GGA is GGA = K Σド= Cz.
Proposition 2 (Concentration of GGA). For any ò E (0, 1), with probability at least 1 -, |GGA-
GGA|
<
2m log
2K
The proofs of Propositions a deferred to Appendix B.5 B.6
Together, Propositions I
2 eestablish bounds which translate directly into meaningful confidence intervals. When is small the intervals are wider, so only coarse distinctions between methods are certified; however, clear performance gaps remain statistically significant. As n increases, the intervals shrink at the rate Onn11,2), enabling progressively finer comparisons between explainers while preserving the same theoretical control. The time complexity bounds for computing the metries on finite samples data is shown in Appendix [F
EXPERIMENT
We validate the proposed metrics through controlled experiments designed to highlight key proper- ties of explanations. In all our experiments, the classifier comprises an embedding function followed by linear classification head, allowing exact computation of its Lipschitz constant and the radius r via the spectral norm. Also note that, Coverage and GGA values in Figs. | and 2 and Table [ are presented with Hoeffding bounds at significance level p = 0.05. The datasets and classifiers are discussed in detail in Appendix D
5.1 EXPERIMENTS ON SYNTHETIC DATASET
Complementing Class Score: We begin by showing a scenario where the proposed metrics both agree with and differ from class score. We synthetically construct the 4Shapes dataset illustrated in Fig for this purpose. Each class in this dataset corresponds to one of four motifs: Star, Lollipop, Grid Tree. An instance graph in a class is random Airabasi-Albert (BA) graph to which a motif of the corresponding shape is attached. While graphs in the same class are attached with motifs of the same shape, the number of nodes in the motif and the number of motif attachments vary within a set range. Each class is assigned two explanation sets on which the metrics are computed: good set containing instances of the class-specift motif without the BA backbone, and a bad set containing 5 random BA graphs. The classifier attains 0.93 test accuracy on this dataset. As shown in Figs. lb except for Class 2, good explanation sets always receive both higher class scores and higher coverage. Fig. Tc confirms that good motifs consistently lie closer to the graph embeddings. For Class 2, random BA graphs attain higher class scores but much lower coverage than the good explanation set. This discrepancy indicates that the trigger for Class-2 predictions does not lie near the embedding distribution of Class-2 instance graphs and suggests that the classifier has learned to predict Class 2 whenever it does not see convincing evidence for any of the other three motifs. To confirm this, we input Erdōs-Résss Rényi random graphs to the classifier and found that they are also labelled as Class 2 with high confidence. This confirms that absence of the other class-specific motifs is the effective decision rule for Class 2. Considered in isolation, class score makes it appear as though the classifier has learned BA graphs themselves as typical representatives of Class and does not reveal that absence of the other three motifs is driving the prediction. In contrast, the low Coverage of these high-score BA graphs shows that they are off-manifold indicating that the effective decision rule is negative evidence.
Diagnosing Redundancy and Partial Explanations: We test whether the metries capture redun- dancy in overly similar explanation sets and diagnose when they only partially reflect the motifs rec- ognized by the classifier. We create a synthetic MixedShapes dataset by merging pairs of 4Shapes classes. One MixedShapes class contains BA graphs with either Lollipop or Star motif attached (never both in the same graph). The other MixedShapes class is defined similarly using Grid and Tree motifs. Thus, each class has two possible motif types, but each graph only has motifs of single shape. For each MixedShapes class, we build two explanation sets: a unimodal set, where all explanations use the same motif type from that class(Star for one class and Grid for another), and a bimodal set, where explanations include both motif types. As shown in Fig. 2 while both sets attain similar mean class scores, bimodal sets achieve much higher coverage explaining broader
7

---

Published as a conference paper at ICLR 2026
Covaroge
Flecx
Class
Class 1
Cass 2
Cless 3
Casa
Class
Class
Clsc
Class
(a) Coverage
(b) Class Scores
(c) Embedding-Motif Distances
Figure I: a) Coverage b) Class Scores and e) Distance of Embeddings from Nearest Motif's for Good (Blue) and Bad (Orange) explanation sets on 4Shapes.
Coverage Soth
Both wt Score Singe
Clss Eem
salu (Coverage Score
Coverage Stnge
9mch
Cass Eeth
Dlos begee
0.6
Ove Overtp
0.6
0:2
10
Class 0
Class
Cless
Class
mobifs selected
(a) Class Scores and Coverage
(b) Overlap
(c) GGA Curve
Figure 2: Plots of a) Coverage (Solid Bars) and Class Scores (Dashed Bars) b) Overlap and c) GGA Curve for MixedShapes for Bimodal (Blue) and Unimodal (Orange) sets.
range of instances, while unimodal sets show high overlap as motifs cover largely the same subset of instances. The GGA curves also show that bimodal motifs steadily expand coverage, whereas uni- modal coverage quickly saturates. Thus, the metrics expose sufficiency and redundancy properties invisible class scores. Additional analysis in Appendix G shows how explanation embeddings align with graph embeddings.
5.2 EXPERIMENTS USING STANDARD MODEL-LEVEL EXPLAINERS
We conducted experiments with three standard model-level explainers XGNN Yuaan et al. 2020
GNNInterpreter (Wang & Shen 2023) and PAGE (Shin et al. 2024) across four diverse real- world datasets: MUTAG (Debnath et al. 1991). IMDB-Multi Yanardaag & Vishwanathan 2015
REDDIT-Binan (Yanardag & Vishwanathan 2015), and the OOB-MOLHIV (Hu et al. 2020 dataset.
For each target class, an explanation set of ten motifs is generated by each explainer. The qualitative (Fig. 3 and quantitative (Table results reveal distinct behaviors, On MUTAG, XGNN and PAGE achieve higher Coverage than GNNInterpreter due to their design choices: XGNN enforces valency constraints, and PAGE discovers connected motifs, yielding explanations aligned with molecular structures. GNNInterpreter, lacking such domain-aware constraints, generates disconnected and chemically invalid graphs that attain high class scores but low Coverage. On REDDIT and IMDB, XGNN completely fails(scores reported in Appendix [], producing trivial structures (single nodes or lines Fig. 3) with zero Coverage, GGA, Overlap, and low class scores. XGNN also cannot be run on OGB-MOLHIV, since it only supports graphs with discrete node features.
On REDDIT- Binnrr, where graphs represent large user interaction networks, GNNInterpreter sur- passes PAGE in both Coverage and class score, likely because PAGE's subgraph search fails large graphs. On IMDB-Multi, both methods achieve high Coverage, GGA, and overlap, indicating that few motifs suffice explain class identity, though PAGE attains significantly higher class scores.
8

---

Published as a conference paper at ICLR 2026
Dataset
Class
XGNN
GNNInterpreter
PAGE
Example
Mutagenic
MUTAG
Non-
mutagenic
Class
Reddit-B
Class
Class
IMDB- Multi
Class
Class
Figure 3: Explanations and Examples MUTAG, REDDIT-B and IMDB-Multi datasets
Table I: Quantitative Results on All Real Datasets
Methods
Dataset
Class
Coverage
GGA
Overlap
Class Score
Mutagenic
0.77310.117
0.71010.150
7.314
0.96610.005
XGNN
MUTAG
Non-mutugenic
0.88540. 185
0.829#0.235
8,400
1.00000.000
Mutagenic
0.411=0.117
0.344+0.150
6,573
0.987+0.002
MUTAG
Non-mutagenic
0.599
0.514+0.235
4.674
1.00000.000
Class
0.86440.051
0.62940.065
0.84440.069
Reddit-B
TableClass
0.77240.038
0.529 40.048
5.361
0.975+40.004
GNN-
OGB-
HIV
0.81240. 117
1411
7.781
0.449+0.004
Interpreter
MolHIV
non-HIV
0.431
0.36240.016
7.944
0.929*0.021
Class O
0.911+0.018
0.893+0.061
8.599
0.650+0:004
IMDB-
Class
0.956t0.077
0.95620.092
9.000
0.75420.000
Multi
Class 2
0.97610.064
0.97610.074
9.000
0.71110.003
Mutagenic
0.77840. 117
0.72110.150
5.611
0.99240.003
MUTAG
Non-mutugenic
0.823+0. 185
0.639*0.235
7.682
0.926#0.003
Reddit-B
Class 0
0.799+0.051
0.681#0.065
8.694
0.776+0.010
Class
0.57540.038
0.32340.048
0.74510.009
PAGE
0.737+0.11
0.713+0.141
8.944
0.578+0.008
MolHIV
non-HIV
0.31140.013
0.215+0.016
3.872
0.937+0.008 004
Class O
0.94740.018
0.947+0.061
9.000
0,955+0.001
IMDB- Mulli
Class
0.996+0.077
0.99640.092
9.000
0.85640.005
Class 2
0.96640.061
0.96620.074
0.85520.004
On the large-scale OGB-MOLHIV dataset, none of the methods achieve more than 0.5 Coverage on the majority non-HIV class, and GGA values remain close Coverage, suggesting stagnation where adding more explanations would not improve coverage. For the minority HIV class, Coverage values are higher but class scores remain low. This stems from the severe class imbalance (~4%), where the classifier memorizes specific minority molecules rather than learning robust discriminative pat- terns, leaving the explainers unable to extract motifs that trigger confident predictions. Appendix H supports this interpretation: even removing single random node from a minority molecule flips its label, indicating that the classifier has memorized examples rather than generalizing.
5.3 META-MEASURE ANALYSIS AND GUIDANCE ON PRACTICAL USAGE
Correlation Analysis and Geometry of Optimality: To examine whether the proposed metrics be- have redundantly, we perform a meta measure analysis by sampling explanation embeddings directly from the classifier latent space. We construct 1000 explanation sets, each containing 10 points drawn

---

Published as a conference paper at ICLR 2026
uniformly at random from the normalized embedding space of the trained GNN on the MixedShapes dataset, and treat these points as hypothetical motif embeddings. We compute Coverage, GGA and Overlap for each set using the class specific radius r". The scatter plots in Fig. show that the three metrics explore a broad feasible region and do not collapse to a single deterministic relationship. By definition, GGA cannot exceed Coverage, and this constraint appears Coverage-GGA plane, but within this envelope the values vary widely, Explanation sets with iden- tical Coverage often exhibit very different GGA values depending on how the gains are distributed across motifs. Overlap behaves almost independently of the other two metrics and increases mainly when motifs influence the same neighbourhoods in the embedding space. These results indicate that the metrics measure distinct geometric properties of explanation sets and are not redundant. The scatter plots further show that there no inherent tradeoff between the three objectives: explanation sets can simultaneously achieve high Coverage, high GGA and low Overlap, and the feasible region contains many such jointly favourable configurations. This has direct implications for explainer de- sign. Methods that discover in distribution motifs are naturally encouraged toward higher Coverage as seen in Figure 6 while explainers that recover multiple distinct reasoning patterns rather than repeated variants tend to achieve lower Overlap.
upper envelope in the
GGA
Overiao
GGA Overiap
234 Duemag apt rqum boant
04-
0.
0.
0.6
0.6
0.6
3.0
0.0
62
666
0.4
00
02
0.4
0.6
0.R
Coverage
Covarage
Figure 4: Scatter Plots of Coverage, GGA and Overlap across 1000 explanation sets on the Mixed- Shapes dataset.
Robustness and Invariance Properties: The metric system is designed remain stable under common geometric transformations of the embedding space. Because Coverage, GGA and Over- lap are defined entirely through neighborhood relations the classifier embedding space, they are invariant to uniform feature rescaling, affine gain and other transformations that preserve relative distances. The angular formulation in Appendix A provides an explicit scale-invariant analogue of the Euclidean coverage-risk certificate, and Theorem 5 shows that the optimal angular radius ră yields the same ordering of explanation sets as any monotone transformation of the underlying dis- tance. Consequently, replacing Euclidean distance by angular distance or normalizing embeddings does not alter the qualitative conclusions about explanation sufficiency, efficiency or redundancy. Empirically, as shown in Appendix E, the ordering between explanation sets is preserved across small perturbations of the radius, and the metrics vary smoothly under shifts in the embedding ge- ometry. Further, when exact calculation of the Lipschitz constant T. is not possible such as for an MLP, it can be upper bounded by multiplying the spectral norms of all weight matrices in the MLP. This provides computable estimate Î 2 L and the sufficiency bounds remain valid for the radius estimated from L. Only the tightness of the bound may vary under varying radius.
6 CONCLUSION
In this paper, we have examined the limitations of prevailing practices for evaluating model-Ievel explanations in GNNs, highlighting the inadequacy of solely using class score. Motivated by the goal of upper bounding sufficiency risk, we introduced three complementary metrics-Coverage,, GGA and Overlap that capture essential properties of explanation sets and are supported by strong theoretical guarantees. Through extensive experiments, we demonstrated that these metrics reliably diagnose unfaithfulness, redundancy, and mode collapse, which remain hidden when evaluation relies only on class score. Our contributions advance the foundations of explainable graph learning by providing the first rigorous theoretically grounded evaluation protocol for model-level explanations.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
The authors were supported in part through the J.C. Bose Grant JBR/2021/000036 from ANRF, Government of India.
Reproducibility Statement The code of our project for comput- ing the metrics can be found Metrics -ee--foor--eeeeeee Model Level-Eaee LE----Eaaaiionni of GN-Ns The proofs of all proposed theorems in Appendix B XGNN, GNNInterpreter and PAGE run using their official implementations which are publicly available. The datasets and the classifiers used on each dataset detailed in Appendix D
https://gitt htt//gttuuub..../ com/ ami sayan/
REFERENCES
Chirag Agarwal, Marinka Zitnik, and Himabindu Lakkaraju. Probing gnn explainers: rigorous theoretical and empirical analysis of gmn explanation methods. In International conference on artificial intelligence and statistics, pp. 8969-89996. PMIR, 2022.
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating expiaanabli for graph neural networks. Scientific Data, 10(1) 1444, 2023.
Kenza Amara, Rex Ying. Zitao Zhang, Zhihao Han, Yinan Shan, Ulrik Brandes, Sebastian Schemm, and Ce Zhang, Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. arXiv preprint arXiv:2206. 09677, 2022.
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini. Global explain- ability of GNNs via logic combination of learned concepts. In The Eleventh International Confer-
ence on Learning Representations, 2023. URL hnttps://openreviit wttp://wwwweeeeettuteemmma
OTBRTIY4YS
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works. arXiv preprint arXiv: 13686, 2019.
Jialin Chen, Shirley Wu, Abhijit Gupta, and Rex Ying. D4explainer: In-distribution explanations of graph neural network via discrete denoising diffusion. Advances in Neural Information Process- ing Systems, 36, 2023.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-799 1991.
Junfeng Fang, Wei Liu, Yuan Gao, Zemin Liu, An Zhang, Xiang Wang, and Xiangnan He. Evaluat- ing post-hoc explanations for graph neural networks via robustness analysis. Advances in neural information processing systems, 36:72446-72444 -24633, 2023.
Qizhang Feng, Ninghao Liu, Fan Yang, Ruixiang Tang, Mengnan Du, and Xia Hu. Degree: Decom- position based explanation for graph neural networks. arXiv preprint wrXiv:2305.12855 2023.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: /903.0090030223 2019.
Aric Hagberg, Pieter Swart, and Daniel A Schult. Exploring network structure. dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), 2007.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18 222133, 2020.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local inter- pretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
11

---

Published as a conference paper at ICLR 2026
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. A survey on explainability graph neural networks. arXiv preprint (.XXii:30660195.8, 2023.
Mert Kosan, Samidha Verma, Burouj Armgaan, Khushbu Pahwa, Ambuj Singh, Sourav Medya, and Sayan Ranu. GNNX- BENXHB Unravelling the utility of braurbaation-basedd GNN explainers through in-depth benchmarking. In The Twelfth International Conference on Learning Represen- tations, 2024. URL.https::/openneeee
net/ t
Remi Lam, Alvaro Sanchez-Gonzalez, Matthew Willson, Peter Wirnsberger, Meire Fortunato, Fer- ran Alet, Suman Ravuri, Timo Ewalds, Zach Eaton-Rosen, Weihua Hu, et al. Learning skillful medium-ranne Bendumm-range global weather forecasting. Science, 382(6677):1416- 1421, 2023.
Wanyu Lin, Hao Lan, Hao Wang, and Baochun Li. Orphicx: causality-inspired latent variable model for interpreting graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13729-13738, 2022.
Ana Lucie, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. Cl-gnnexplainer: Counterfactual explanations for graph neural networks. In International Con- ference on Artificial Intelligence and Statistics, pp. 4499-4511. PMLR, 2022.
Amil Merchant, Simon Batzner, Samuel Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk. Scaling deep learning for materials discovery. Nature, 624(7990):80-85, 2023.
Phillip E Pope. Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 10772-10781, 2019.
Sayan Saha and Sanghamitra Bandyopadhyay. Graphon-explainer Generating model-level expla- nations for graph neural networks using graphons. Transactions on Machine Learning Research.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for nlp with differentiable edge masking. arXiv preprint arXiv:2010.00577 2020.
Yong-Min Shin, Won Kim, and Won-Yong Shin. Page: Prototype-based model-level explana- tions for graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(10))6559-6533 6576, 2024. doi: 10.1 (0.1109/PPAM12222.333772
Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33:12225-12233 2020.
Xiaoqi Wang and Han-We Ken Shen. Gnninterpreter: A probabilistic generative model-level ex-
planation for graph neural networks. In The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https://opennevii/
net htttppddF..ddrrg00hh33.4
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: survey. ACM Computing Surveys, 55(5):1-37, 2022.
Yuezhu Xu and S Sivaranjani. Eclipse: Efficient compositional lipschitz constant estimation for deep neural networks. Advances Neural Information Processing Systems, 37:10414-10441, 2024.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Zhaoning Yu and Hongyang Gao. MAGE: Model-level graph neural networks explanations via basef-based graph generation. In The Thirteenth International Conference on Learning Repre- sentations, 2025. URL https:/ openreview .nt// forum? wtw.iiiduueeeypueeeee
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 430 438, 2020.
12

---

Published as a conference paper at ICLR 2026
Hao Yuan, Haiyang Yu, Jie Wang. Kang Li, and Shuiwang Ji. On explainability of graph neu- ral networks via subgraph explorations. In International Conference on Machine Learning, pp- 12241-12252. PMLR. 2021.
Yue Zhang, David Defazio, and Arti Ramesh. Relex: A model-agnostic relational model explainer. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Society, pp. 1042-1049, 2021.
Xu Zheng, Farhad Shirani, Tianchun Wang, Wei Cheng, Zhuomin Chen, Haifeng Chen, Hua Wei, and Dongsheng Luo. Towards robust fidelity for evaluating explainability of graph neural net- works. In The Twelfth International Conference on Learning Representations, 2024. URL https:/ Dttps:://pperevz/ .ne. nowt://orrummm2uuurrrrrm
A COVERAGE IN ANGULAR DISTANCE
Why angular distances? In practice, the Euclidean geometry underlying r 2I, can be fragile to arbitrary rescalings of the embedding space or the classifier head (e.g., layerwise gain, feature nor- malization choices), which stretch or shrink [[x(G) - m& ll without altering the decision boundary. As result, the Euclidean coverage at r may saturate to 0 or and become uninformative, de- spite the validity of the thcoretical guarantee. To obtain a scale-invariant notion of proximity while retaining distribution-free upper bound sufficiency risk, evaluate coverage normalized embeddings using angular distance. The next result provides the exact analogue of the Euclidean bound and its optimizer in this scale-invariant geometry.
Theorem 5 (Coverage-risk bound and optimal radius in angular geometry). Let f = H o o and assume the head H is L-Lipschitz w.rt. the Euclidean norm on @()): (H(a)) - H(22) S L| zalla for all 21, 22 E (g)). Define normalized embeddings ō(G) = ([))/] and m. = m&/ /a///mmllz and the angular distance
Do(G) = min ((o(G),mz), 0(u, == arccos n)).
Let Cov2 Pr(Do S G E 9r). Then for any re E (0,
SRa(Mro, Ex) S L' (2 D Dx) ((Dx(G) S Ge G + (1- (ov (1)
and the right-hand side minimized
r 2 aresin min 11
When L 2 1. this simplifies to ră arrssin(.).)
Proof. Define the proxy Mr, E fl..... K, 1} by assigning G' to the index of its nearest motif in angle if Do(G) S To, and to 1 otherwise. Let Y := fc) E [0, 1]. By variance decomposition,
K
SR. E.)
Σ Pr(Mrr = k) Var(Y Mr k) + Pr(Mr, =1) Var(Y Mro =1). k=1
For covered bin (Mr k), Var(Y Mr, = k) s B((y fc(M))) M, k).. On the unit sphere, the chord angle identity yields ||ž ml12 = 2 sin (2, ( m)). Using Lipschitzness of H in Euclidean norm,
(c(E)))) fe(ma)) S I(((()) mx lll = 21 sin (i m.))
Averaging over covered bins gives the expectation term in equation T For the uncovered bin, since Y E [0, 1], Var(Y M,, =1) 1. giving the second term.
For optimality, let Fo(r) == Pr(Do( < G E 9 and write the bound as
Br(re) L? foOm 4sin dFo(t) + (1-Fo(ro)).
13

---

Published as a conference paper at ICLR 2026
For 0 12 m.
Bø(r2) - Br(r1) -(orrs) (4L" sin
11) d(F(tt).
Hence Bg decreases while 41, sin (ra/2) S 1/ and increases afterwards. The minimizer solves 2 (in(rg/2) = 21.
1 If L 2 4- this yields rg = arcsin( 4r.): otherwise the inequality holds for all t E [0, T] and the minimizer is the maximal feasible radius. Compactly, rb = 2 arcsin(ming }).
B PROOFS
B.1 PROOF OF THEOREM 1
Proof. First note that for any M, SR, = Var(Y M)]. Set Z == B[y M* By the tower property of expectation.
E|y M] = E M*] M] = E|Z M..
By the law of total variance applied inside M,
Var(Y M) E| Var(Y M*) M] + Var(Z M) 2 EE Var(Y M²) M).
Taking expectations yields
SR,(M,,,) = E
M)] E Var(Y M*) SRoMM Var(Y [[r(
as claimed.
B.2 PROOF THEOREM 2
Proof. Let Y = fc(G). By variance decomposition,
K
SR,,M, Ee) = Va MM(G)) Σ Pr(M, = k) Var(Y M, = k) + Pr(M, =1) Var(Y | M,, =1).
We show the total bound by bounding the covered and uncovered parts.
Covered Part (M, = k). For each k, let M₁ E E. denote the k-th motif with embedding ((M2). For any random variable Z and constant a. Var(Z) S E Z a) Apply this with Z Y and = fa(M)) under the conditional distribution given M, = k:
Var(Y | k) S (I((G)- M,, = k
By L-Lipschitzness of H ((G).
(G) - sc(Mw) & Il(((G) m l12.
hence
Var(Y Mr = k) < L²E - mx M, k..
Averaging over k with weights Pr(M, k) yields
Pr(M, k) Var(Y M, k) 1(E)) r)].
Uncovered Part (M, =)). Here M, takes a single value, so
Pr(M, 1) Var(Y M, 1) (1 Cova(r)) Var(Y M, = Since = fa(G) E [0, 1], any conditional variance satisfies Var(Y |)) S 1/4. Thus
Pr(M, =1) Var(Y M, =1) < (1 - Cr).
Combining the covered and uncovered parts establishes the claim.
14

---

Published as a conference paper at ICLR 2026
B.3 PROOF OF THEOREM 3
Proof. Let F(r) - Pr(D(G) r G 99) denote the cumulative distribution function of D For two radii 0 m < 12, the change in the bound is
- Brr) L [ (m1.ra)
ddF(t) -FF(2))-((1))
This expression rewrites as
B(r2) - B(r1) = I (M.raa)
1 22) dF()).
We now analyze the sign of the integrand: If r2 I 1/(2L), then for all t E [r1,72] we have L < 1. Henee each term inside the integral is nonpositive, so Brr2) - B(r)) S 0. Therefore B(r) is nonincreasing on 00, 1/L)]. If m 2 1/(2L), then for all (ri, r2] we have 1,2 2 1 Hence each term inside the integral is nonnegative, B(r2) - B(r1) 2 0. Therefore B(r) is nondecreasing on [1/(2L), oo).
Combining these two facts, the function Brr) decreases up to 1/(2L) and increases thereafter. Thus (rr) achieves its global minimum at
2L
B.4 PROOF OF THEOREM 4
Proof. All expectations/proabblliiess are with respect to E 9o By Theorem 2 for any explanation
set E at r",
SRe(M,,, E) s ('E ((D))))))(((G)) r*1] + (1
where (G) is the nearest-moti distance to E and ag its coverage fraction. For the greedy prefix El( and the full set E.,, enlarging the motif cannot increase the distance term, i.e., DE. (G) S
D Pro (G) and hence
E E[DE, (DE, S S E D E (G) 1(D E! (G) sm
Therefore
SMr, E( - SR. (M,,, Ee) < (a - at).
A S e for all j > f, then a² 04 = 1== A S (K - t)c, yielding the stated bound.
B.5 PROOF OF PROPOSITION
Proof. By Hoeffding's s inequality for bounded independent variables in [0, 1]. for any > O, Pr Pr([Cove(r) - (rv 2 t) v 2 exp( 2n
Set the rinht-hand side to and solve for eexp(-2nf'' = 5 + t = V 2n log 2
8. Equivalently,
Pr([Cov - (rv) <
2n log 2) 2 1 1- 5.
B.6 PROOF OF PROPOSITION 2
Proof. Fix j. Write āj n X with indicators X [0, 1]. Hoeffding gives Pr([a,
a;1 2 1) 2exp( 2nt2) for any > 0. Apply union bound over j 1,..., K:
Pr max |ā, - -ay 2 t) < 2K exp( exp(-2nt²) ISiŠK
Set the RHS to and solve for t: 2K exp( - 2nt = - t= V In
log 2K
8- Finally,
GGA GGA|
k ( 6a ag)l s max jā a,1
j=1
which yields the stated bound with probability at least 8.
15

---

Published as a conference paper at ICLR 2026
C ADDITIONAL GUARANTEES USING GGA
When only a budget of t < motifs are retained for interpretability. can we certify how much cov- erage is still guaranteed? The following theorem shows that GGA provides exactly such guarantee: it lower bounds the prefix coverage ae at every step t, using only the achievable coverage Cove(r*) and the average area summarized by GGA.
Theorem 6 (Prefix coverage guarantee from GGA). Let a = Cova(r") be the total achievable coverage at r². Then for every E [I,...,K) K) the coverage obtained by the first greedy motifs certified to satisfy
at 2 KGGA (K a''
Thus GGA provides distribution-free lower bound on prefix coverage, linking overall efficiency to budgeted motif selection.
Proof. We have
K
K Σ J= 1=1
Σ
0
A
=
Σ
-K-1+1)
(K
F=1
111
Split the sum at t:
K
Σ aj Σ
K (K-i+1AA + Σ (K (K-i+) 1)4,. i=t-1
For S t, -i++ 2 (K - t 1), and for t, (K i + 1) s (K t). Hence
K
KGGA
Σ
aj S (K - 1) + (K - +)(a" - a4))
j=1
Rearranging gives a, 2 GGA - (K 1)a*
Its immediate consequences: bounding the number of motifs required reach target coverage fraction and the corresponding sufficiency risk such prefixes are presented next.
Corollary (Motif budget for target fraction of coverage). Fix p E (0, and let Tp min 04 2 pa' } be the number of motifs required to reach fraction of the achievable coverage oz.. Then
Tp S
KKP K
GGA GGA a*
Proof. By Theorem 6 for any t we have
ay > KGGA - (K- -t)a".
If K GGA (K l)x pa', then aa 2 pa and hence Tp t. Rearranging yields / K + K(GGA/a"). Taking the smallest integer f. that satisfies this gives the bound.
Corollary (Risk bound under motif budget). Let Fi!!) denote the greedy prefix of size at r*, with coverage at. Then by Theorem 2 the sufficiency risk satisfies
SRoM,,, E( < L'EED(G) ((D()) ST*H +
- 4(1-aa))
Using Theorem 6 this implies the certified bound
SR,, S (ED(G)) s - (1- maxf0, K GGA (K (K-t)oo -t)a")).
D DETAILED EXPERIMENTAL SETUP
All experiments were conducted using the PyTorch Geometric library (Fey & Lenssen 2019) for implementing and training the graph neural networks, and the NetworkX library (Hagberg et al. 2007) for synthetic graph generation and visualization. The experiments were performed on a high- performance workstation equipped with an Intel Xeon Processor with 40 cores, 256 GB RAM, and an NVIDIA Quadro RTX 6000 GPU (24 GB).
16

---

Published as a conference paper at ICLR 2026
Algorithm 4Shapes Dataset Generation
Require: Number of classes C 4, number of graphs per class N, range of motifs per graph
[min (max] number of nodes each motif [Tmmnn; Rmaz]
Ensure: Synthetic graph dataset !
1: for each class E 3 do
2: for = 1 to N do
3: Generate Barabásii-Alboc (BA) graph as the backbone
4: Select motif type based class
Class 0: Star
Class 1: Grid
Class 2: Lollipop
Class 3: Balanced
5:
Sample m ~ ~ Maax
6:
Sample n ~ 21 (nimmin 7
7:
for j 1 to m do
8:
Generate motif of the chosen type with n nodes
Attach the motif to the backbone by connecting random node in the backbone with random node the motif 10: end for
9:
11: Add the resulting graph with label c to D
end for
13:
end for
14: return D
D.1 DATASETS
4Shapes. We construct this synthetic dataset which consists of 4000 graphs divided into four classes with 1000 graphs each. Each graph is generated by first constructing a Barabási- (BA) backbone. Depending on the class label, one of four motif types (star, grid, lollipop, balanced tree) selected. A random number of motifs is sampled and attached to the backbone by connect- ing random node from the motif to random node in the backbone. Algorithm demonstrates the generation algorithm of the dataset and Figure shows representative examples of instances in the dataset and good and bad explanation sets.
MixedShapes. This synthetic dataset is built from 4Shapes by merging pairs of classes. The first MixedShapes class combines the Star and Lollipop classes: each graph a BA graph with either a Star or Lollipop motif attached (never both in the same graph). The second MixedShapes class is defined similarly by merging the Grid and Tree classes, so each graph has either a Grid or a Tree motif. Thus, each class has two possible motif types, but every graph contains exactly one motif of a single shape.
MUTAG. MUTAG (Debnath et al., 1991] a benchmark dataset of 188 molecular graphs, each labeled according to the mutagenic effect of the compound on Salmonella typhinurium. In these graphs, nodes denote atoms (e.g., e. C, O, N) and edges represent chemical bonds. Node features typically encode atom types, while edge features capture bond types. Although relatively small, MUTAG is widely used for evaluating graph classification methods and explanation approaches, as models often highlight substructures such as functional groups that influence mutagenicity.
REDDIT-B. REDDIT-B (Yanardag & Vishwanathan 2015) is a large-scale social network dataset containing 2,000 graphs constructed from Reddit discussion threads. Each graph corresponds to thread, with nodes representing users and edges indicating reply interactions. The task is binary classification: Q&A communities, which yield tree-like structures, versus discussion communities, which form denser interaction patterns. With graphs often containing hundreds of nodes and no node features, REDDIT-B is commonly used to benchmark GNN scalability and their ability to capture structural information from purely relational data.
17

---

Published as a conference paper at ICLR 2026
Examples
Good explanation set
Class
Class
Class
Class
explanation
Class
Claos
Closs
Class
Figure 5: Representative Examples of Instance Graphs in the 4Shapes dataset with Examples in the Good and Bad Explanation Sets. The Good explanation sets shows examples of the motifs contained in each class while the bad explanation sets are random BA graphs.
IMDB-MULTI. IMDB-MULTI YYnnardag & Vishwanathan 2015 consists of 1,500 ego- networks extracted from the Internet Movie Database. Each graph corresponds to an actor/actress, with nodes actors and edges connecting pairs who co-appear in movies. Graphs labeled into three classes based on the predominant genre of the target actor's movies: Action, Comedy, or Drama. These graphs are sparse and lack node features, making the dataset standard benchmark for evaluating GNN performance social networks with limited attribute information.
OGBG-MOLHIV. OGBG-MOLHIV, part of the Open Graph Benchmark (OGB) et al., 2020). contains 41,127 molecular graphs with the binary prediction task of determining whether molecule inhibits HIV replication. Rich atom-level (type, chirality, valence) and bond-level features are pro- vided. Dataset splits are defined using scaffold splitting, ensuring structurally distinct molecules across train, validation, and test sets. As a large-scale and chemically meaningful benchmark, ogbg- molhiv is widely adopted for testing the generalization ability of GNNs in molecular property pre- diction and drug discovery applications.
D.2 CLASSIFIER DETAILS
Model architecture and Training For the IMDB-MULTI. REDDIT-B and OGB datasets, we em- ploy Graph Isomorphism Network (GIN) architecture. The encoder consists of five stacked GIN- Conv layers, each parameterized by a two-layer MLL with ReLU activation. Batch normalization and dropout (p = 0.5) are applied after each layer to improve stability and prevent overfitting. The final node embeddings are aggregated using global mean pooling to obtain a fixed-size graph-level representation. This pooled representation is passed through fully connected layer with ReLU activation, followed by a linear classifier that outputs logits over the class labels. The model is trained using the Adam optimizer with learning rate of 10-3 and cross-entropy loss function. A StepLR scheduler with decay factor = 0.5 is applied every 20 epochs to reduce the learning rate adaptively.
18

---

Published as a conference paper at ICLR 2026
On the MUTAG dataset the general architecture and the training paradigm remains the same with the only modification being the use of two stacked GINConv layers.
On the 4Shapes and MixedShapes datasets, Conv layers with 64 hidden units and ReLU activations, followed by global sum pooling and a final fully connected linear layer that outputs the class logits.
simple GNN classifier consisting of two GCN-
Table 2: Dataset Properties and Classifier Accuracy
Dataset
#Classes
#Graphs
Average #Nodes
Average #Edges
Classifier Accuracy
IMDB-Multi
3
1500
19.77
96.53
0.835
Reddit-Binary
2
2000
429.63 63
497.75
0.871
MUTAG
2
188
17.93
19.79
0.8723
OGB-MOLHIV
2
117
25.51
54.94
0.9701
4Shapes
4
2000
41.53
103.20
0.9320
MixedShapes
2 2000
41.53
103.20
0.9563
E BEHAVIOUR OF COVERAGE: ALIGNMENT WITH DISTRIBUTIONAL. DISTANCE AND ROBUSTNESS TO RADIUS CHANGES
Relationship with Wasserstein Distance: To verify that coverage reflects distributional fidelity, we compare it against the Wasserstein (W1) distance between explanation sets and the target class distribution. We generate 1000 explanation sets on the 4Shapes dataset for each class and group them into quantiles based on coverage. Figure violin plots of WI distances for each quantile. The pattern is clear: sets with higher coverage exhibit substantially lower and more concentrated W1 values, while low-coverage sets show large and dispersed distances. This confirms that coverage is not only a sufficiency certificate but also correlates with being in-distribution: explanations that align more closely with the class distribution naturally achieve higher coverage.
2.00
W1 Distance
1.25
0.75
0.00
(.0.001, 0.024)
02024, 0.048)
10048, 0.072)
(0.02, 3.26
362 0.71
10.67. 0.778|
00.77. 0,908)
10 0.95)
Coverage Quantile
Figure 6: Distribution of WI distances across coverage quantiles (1,000 explanation sets). Higher coverage corresponds to lower and less variable W1, indicating stronger alignment with the class distribution.
Robustness to Radií Changes: further test robustness to the choice of radius r on which the coverage is evaluated. For this coverage is evaluated over sweep of radii around r*, comparing good and random motif sets on the 4Shapes dataset. As shown in Figure Jarrss all radii, the ordering remains invariant: good motifs consistently achieve higher coverage than random ones, with no reversals observed. This stability shows that coverage- based comparisons are robust to radius selection.
19

---

Published as a conference paper at ICLR 2026
1.0
Good
Class Rand
Class Rand
Class Rand
Class Rand
0.8
Coverage
0.6
0.4
0.2
0.0
3
Figure 7: Coverage variance with r*
F COMPUTATIONAL COMPLEXITY OF METRICS
We analyze the computational cost of computing the proposed metrics. Let N denote the number of positive embeddings and M the number of motif embeddings considered for class.
Metric
Complexity
Notes
Coverage
O(NM)
Distance matrix + minimum operation
GGA
O(NM²)
Greedy selection of motifs
Overlap
O(NM)
Computed from coverage sets
Table 3: Computational complexity the proposed metrics.
Coverage. Coverage requires computing the minimum distance from each of the N embeddings to the M motifs. This involves constructing an N x M distance matrix and minimum operation, leading to complexity of
O(NM).
GGA (Greedy Gain Area). The GGA curve is obtained by iteratively adding motifs that maxi- mize marginal coverage. At each iteration, coverage gains for all remaining motifs are evaluated, costing O M) per iteration. Over up to K iterations (with K < M), this yields a worst-case complexity of
O(NM²).
Overlap. Overlap is computed from the coverage sets constructed during GGA. Since these sets are already available, the additional computation is linear in the number of memberships, giving
O(NM).
Summary. The complexities of the three metrics are summarized in Table 3
In practice, the number of motifs M small (5-10), so the quadratic dependence in GGA remains computationally feasible.
G FURTHER ANALYSIS ON THE MIXEDSHAPES DATASET
We compare the explanation sets constructed from Both-shapes motifs (bimodal, containing both motif types per class) and Single-shope motifs (unimodal, containing only motif type per class).
20

---

Published as a conference paper at ICLR 2026
The t-SNE visualization in Figure 8 shows that the bimodal explanation set achieves broader and more even coverage of the embedding space, with motifs distributed across diverse regions. In contrast, the unimodal set concentrates motifs in fewer regions, leaving large portions of the emhedding space underrepresented.
The nearest-distance distributions in Figure g b confirm this observation. Embeddings tend to lie closer to their nearest motifs under the bimodal set, whereas the unimodal set results in larger dis- tances, indicating poorer representational coverage. Together, these results highlight that explana- tion sets combining multiple motif types provide better alignment with the embedding distribution and are thus more representative.
L-SNE embeddinngs with motils
Nath-shapse Singes
Neurest muei distances
12-
(a) I-SNE of embeddings with motifs.
(b) Nearest motif distance distributions.
Figure 8: Comparison of bimodal (Both-shapes) vs unimodal (Single-shape) explanation sets on MixedShapes dataset.
H
ANALYSIS ON THE OGB DATASET
Confussion Mabrik
Poportan Lobel with Rode Nemovel
25000
Cloa
37521
163
20000
23
The
15000
Pegeten
1123
70700
Redicied
(a) Confusion Matrix of the Classifier.
(b) Proportion of label flipping minority- graphs
Figure 9: Classifier Analysis on the OGB-Molhiv Dataset
Figure Da shows the confusion matrix of the classifier trained on the OGB dataset. It can be observed that the classifier has a high rate of misclassification on the minority class. We saw that the explainers on the minority class struggled to achieve high class score this dataset even though they attained relatively high Coverage scores. Our hypothesis for this phenomenon was that the classifier has memorized instances it has classified the minority class rather than learning general pattern.
21

---

Published as a conference paper at ICLR 2026
This is why the discriminative motif that the explainers came up with attained high class score. We verify our hypothesis using a controlled experiment. We randomly choose 50 graphs that the classifier has classified to the minority class and progressively delete 1-3 randomly chosen nodes from each graph. Figure 99 shows the proportion of graphs whose labels flip upon deletion of nodes. It can be that after deletion of one node 67% of the graphs flip labels to the majority class while after deletion of three nodes 94% of the graphs flip their labels, This shows the strong bias of the classifier to the majority class. Since, the node deletion is done in random and the chosen graphs were also random, it shows that the classifier's 's decision is not robust to minor perturbation. In other words, the classifier has not learnt a general pattern for the minority class. It has only memorized certain instances that it has rightly or wrongly classified to the minority class.
I RESULTS ON IMDB-MULTI AND REDDIT-B FOR XGNN
Table shows the quantitative results of XGNN on the IMDB-Multi and the REDDIT-Binary datasets.
Table 4
Methods
Dataset
Class
Coverage
GGA
Overlap
Class Score
Class 0
0.000=0.051
0.000
0.000
0.003+000000
Reddit-B
Class
0.000 0.038
0.000 0.048
0.000
0.35740.000
XGNN
Class 0
0.000=0.018
0.000+000061
0.000
0.499* 0.000
IMDB- Multi
Class
0.000=0.077
0.000100009
0.000
0.54440.000
Class 2
0,000#0.062
0.000*0.074
0.000
0,508+0.000
J MOTIVATION FOR THE SUFFICIENCY RISK FORMULATION
Sufficiency as a sufficient statistic. Our notion of sufficiency is grounded in the classical concept of sufficient statistic. A statistic T(X) is sufficient for predicting target quantity if, once T(X) known, the original variable X contains no additional predictive information about that target. In setting, the graph G is random variable and the membership code M (G') is statistic of G. The goal is to quantify how far (G) is from being sufficient for predicting the classifier score fe(
Why the conditional expectation is the canonical predictor under squared loss. Consider pre- dicting fe(G)) using only the information in (G), i... predictors of the form (G). A stan- dard projection (orthogonality) result states that the conditional expectation [[[c(G) M()) is the unique minimizer of mean squared error over this function class:
[G) | M(G) = arg min [[[[c(G) - 1000-gg(((0 (M(())
(2)
Equivalently, for any measurable
[[[f((G) - ((M(G))) = (E((.(() -(((G)))(((()) M(G))) +E (B[(B(((GG M(G) - ([G))))(MM())) (G))))
sufficiency risk
(3)
Thus, any squared-loss notion of "how sufficient is (() for predicting Je(G)" must be measured relative to this optimal predictor.
Interpretation via law of total variance. By the law of total variance, the sufficiency risk admits the equivalent form
Reuf M) [[(.(G))- BG) [ = [[Var(J((()) M(G)))
(4)
Hence Rent (M) = 0 if and only if (G) is (almost surely) a deterministic function of MG), i.e.,
(G) is sufficient for predicting [c) in the standard statistical sense.
22

---

Published as a conference paper at ICLR 2026
Relation to certificates. While could consider information iifommation-theoretic theoretic alternatives (e.g., mutual information between G and (G)), our goal is to relate an ideal membership M to proxy membership M, and derive distribution-frre guarantees. The conditional-cxpectatee formulation in equation 2 4 connects directly to our I Lipschitz-based bounds, enabling certificates for the gap in sufficiency risk between M and the proxy.
LLM USAGE K
We used GPT-5 to polish the writing and grammar of the paper.
23


Reviews:
[{"review_id": "trTUU6PR3E", "reviewer": "Reviewer_qamU", "summary": "This paper introduces three metrics, coverage, greedy gain area (GCA), and Overlap, to characterize the quality of the model-level explanations for GNNs. Coverage quantifies the likelihood a class is covered by a motif, determined by a threshold r and a distance measure (nearest motif). A tightness analysis verifies a suggested universal radius r for the sufficiency risk estimation.  GCA, based on coverage analysis, gives an area under the coverage curve. Overlap measures the possible redundancy of the motifs.", "questions": "D1. It is not yet clear how the proposed metrics may encourage existing methods to seek computable optimal explanations under such measures, or whether they are conflicting or highly correlated, thereby indicating suboptimal yet Pareto-optimal solutions. An in-depth meta-measure analysis to verify potential trade-offs is needed. Other properties of metric systems, such as their susceptibility to scaling factors and user-defined preferences, and their invariance properties (will the value change significantly, suggesting different quality simply because a different distance function is used?) under the replacement of task-driven distance measures, deserve in-depth discussion. \n\nD2. How the bound analysis helps in practice should be elaborated. It may suggest proper normalized measures—and indicate a fair assessment? The advantages of the proposed metrics, compared with other commonly adopted ones, should be discussed. \n\nD3. How easy is it to compute such measures? What's the time cost? This needs further analysis. \n\nD4. More insightful results could be summarized from Table 1. As is, only the results are shown, with little further analysis of how these measures help recommend or suggest promising solutions. \n\nD5. More state-of-the-art GNN explainers should be compared and experimentally tested to show the benefit of the proposed measures.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1. Principled metric system and efficient assessment are important topics for graph learning. \nS2. The paper provides an optimality analysis of parameter choices, such as r, and provides proper upper and lower bounds. \nS3. The metrics are simple and generally applicable.", "weaknesses": "W1. There is a lack of time-cost analysis for the assessment process. \nW2. Only the proposed metrics are measured; the methods lack more insightful justification from third-party measurements regarding consistency or any contradictory observations.  \nW3. It seems all or some of these measures are highly correlated. A necessary correlation or orthogonality analysis is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tnnHuztRDX", "reviewer": "Reviewer_jLqD", "summary": "This paper tackles the long-standing problem of evaluating model-level explanations for Graph Neural Networks (GNNs). Unlike instance-level explainers, which clarify decisions for individual samples, they focus on the explainers that aim to uncover class-discriminative motifs or graph patterns that the classifier consistently relies on. Current evaluation practices hinge almost entirely on target class scores, assuming high-scoring motifs faithfully represent the model’s reasoning. The authors argue this is flawed: high scores can result from pathological motifs detached from the true data distribution. To address this, they propose a theoretically grounded evaluation framework supported by distribution-free certificates that upper-bound an explanation’s insufficiency, or sufficiency risk.", "questions": "N/A", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper tackles a very important and long standing problem, namely, evaluating model-level GNN explanations. \n2. The paper proposed three reasonable metrics.\n3. The paper presented time analysis of the metrics.", "weaknesses": "1. The usage of the term \"model-level\" in this paper is not accurate. They develop metrics (Coverage, Greedy Gain Area, Overlap) that assume the explanation set is a collection of motifs (subgraphs) that represent class-discriminative patterns. However, many so-called “model-level explainer” methods do not output exactly “motifs” in this sense (i.e., compact sub-graph patterns extracted from or representative of the dataset). For example: XGNN generates class-specific instances (i.e. synthetic graphs) rather than mining motifs present in the training set. GCNeuron may produce Boolean rules or logic combinations rather than explicit graph motifs. The claim that their evaluation metrics are “for model-level explanations” is true only if the explainer produces motif-style explanations. If an explainer produces rules, logic formulas, or generated graphs that don’t align with “motifs from data”, then the metrics may not apply cleanly. The story told by the paper implies the metrics apply to all model‐level explainers, but they in fact only apply to motif‐extraction style ones. This needs to be clarified in the title, abstract, introduction, etc., instead of keeping it vague or overclaim. \n2. Presentation needs improvement. Citation style needs to be corrected.\n3. The three metrics, Coverage, GGA, and Overlap, are intuitive and could be justified directly from geometric reasoning. The introduction of sufficiency risk and distriThere is a fundamental mismatch between the proposed metrics and the explainers evaluated. \n4. The metrics are designed for motif-extraction-based model-level explanations, where each explanation represents a class-discriminative subgraph sampled from or near the data distribution. However, the tested methods (XGNN, GNNInterpreter, PAGE) are generation-based and produce synthetic or prototype instances rather than extracted motifs. As a result, the evaluation does not truly measure what the proposed metrics are meant to assess. The reported results cannot substantiate the claimed effectiveness of the framework, since the metrics and the explainers operate on fundamentally different types of outputs.bution-free certificates adds complexity without offering real insight or practical necessity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SAHOiIysca", "reviewer": "Reviewer_JtxQ", "summary": "This paper presents a principled evaluation framework for model-level explanations on graph neural networks (GNNs), introducing\ntheoretical guarantees via sufficiency risk and three novel metrics: Coverage, Greedy Gain Area (GGA), and Overlap. The work\naddresses a critical gap in evaluating model-level explanations beyond classification scores, with rigorous theoretical foundations\nand extensive experiments.", "questions": "See the questions associated with Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The formalization of sufficiency risk provides a rigorous foundation for evaluating explanation quality. Theorems 1-3 and Proposition 1-2 establish certified bounds linking the proposed metrics to sufficiency risk, ensuring reliablity of metric even in a finite sample scenario.\n\nS2. The three metrics offer complementary views of explanation quality (sufficiency, efficiency, non-redundancy), which reveals unfaithfulness, redundancy and mode collapse in the methods relying only on class score through extensive experiments.\n\nS3. Experiments on 2 synthetic and 4 real-world datasets convincingly demonstrate the metrics' ability to expose limitations of class-score-based evaluation on model-level GNN explanations, such as pathological explanations and pattern collapse.", "weaknesses": "W1. The proxy function $M_r$ relies on nearest-neighbor distance in the embedding space. While simple and computationally efficient,\nthe paper doesn’t give the reason of choice and whether the measure is optimal for all GNN architectures or datasets or not.\n\nW2. The description of “For each target class, an explanation set of ten motifs is generated by each explainer.” on page 8 indicates that\nthe current approach considers model-level explanations typically using small M(~10 motifs) in practice, as observed in the experiments. However, the computational complexity of GGA is related to O(NM^2) in Appendix F. A large explanation sets may lead to low scalability. Why does the paper define a ten motifs scenario in practice?\n\nW3. Experiments only use GIN architectures (In Appendix D.2). The theoretical bounds depend on the Lipschitz constant of the\nclassifier head (In Theorem 2), which may vary with architecture (e.g., GAT or GCN), affecting metric stability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3lUkm99bBz", "reviewer": "Reviewer_GqAd", "summary": "In short, the paper proposes a new way of evaluating model-level explanations.\n\nMore in detail, the paper introduces sufficiency risk as a metric that equals zero for optimal explanations. Then, since the metric is difficult to compute, the paper introduces practical metrics, like Coverage, Greedy Gain Area, and Overlap. Coverage, in particular, is shown to upper-bound sufficiency risk, making it a principled way to estimate the risk. Convergence and approximation bounds from finite samples are further discussed, showing how the metrics can be efficiently and reliably estimated from limited data.", "questions": "- Q1: I'm expecting that $SR_c(M*, E_c)$ to be always zero, as $M^*$ is the true membership function. Is this correct? \n\n- Q2: How is the membership function $M$ defined for disconnected motifs appearing in the same sample for a certain class, like *square AND lollipop*? And how does the proposed proxy membership function $M_r$ cope with that situation? Examples of such explanations can be found in Azzolin et al. 2023 and [1].\n\n- Q3: Fig 1c shows that the embedding-motif distances separate quite well good from bad explanations. Hence, why not use that as a metric by itself, by setting a threshold on the distance to separate good from bad explanations?\n\n- Q4: Do the authors think that evaluating a model-level explanation by feeding the classifier with only the individual motif may cause some OOD issues in the evaluation, so that model's prediction changes not because the motif is not representative of what the model is doing, but just because the input sample is OOD?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "- I agree that there is a fundamental lack in evaluation metrics for model-level explainers, and the paper proposes to fill the gap with an interesting suite of metrics. I think this contribution fills a big gap in the current literature.\n\n- I also agree that the usual approach of evaluating the classifier score metric cannot capture all the nuances of the explanation. The paper describes this issue in detail and motivates well why the literature should move beyond that.\n\n- The proposed metrics are principled, and the authors show how to reliably estimate their values, and also show how metrics complement each other.\n\n\nThis paper **has the potential to be a cornerstone paper** in the context of model-level explainer, and I liked a lot the motivation part. Nonetheless, **when it comes to the results and implementation side, I'm left with some concerns**, detailed below.", "weaknesses": "- **W0**: The authors say that estimating sufficiency risk is particularly challenging, as it involves a conditional expectation. However, I struggle to understand why the provided formulation is the only possible way to define the sufficiency risk. Do you really need to formulate it as a conditional expectation? I think more details should be provided about the rationale of this formulation. Also, the authors write:\n\n> Low values of $SR_c(.)$ indicate that motifs faithfully capture the classifier’s reasoning.\n\nHowever, the authors claim that class core alone is not sufficient to distinguish good from bad explanations; therefore, **how can sufficiency risk alone be indicative of an explanation's faithfulness, given that it is an MSE between class scores?**\n\n\n- **W1**: Authors define the proxy membership function $M_r$ as a proximity-based check detailed in lines 188-191. However, I feel that a natural baseline for this would be to run some subgraph isomorphism check, which, albeit more computationally expensive, does not require defining a hyperparameter $r^*$ and is not approximated. I was expecting the authors to at least compare their proposed methodology with that simple baseline, to show it is actually better/more efficient than such a baseline. \n\n- **W2**: Line 196 says *the residual noise in $M_r$ is independent of $Y$ satisfying the assumption in Theorem 1*. However, I believe that considering the embeddings given by $\\phi$ does not make $M_r$ independent of $Y$, as $Y$ is still predicted from $\\phi$. So, I believe there is still a correlation between embeddings and classifier scores. Actually, embeddings contain all the information needed by the classifier to predict $Y$, making it clearly non-uncorrelated with $Y$.\n\n- **W3:** In lines 105-106, the authors write: \"*While this avoids unrealistic motifs, extracted patterns often cover only a limited subset of instances and may fail to generalize across the class*\". Since this is a strong statement showing key limitations of discovery-based approaches, some evidence or literature in support of the claim should be provided.\n\n- **W4:** Greedy Gain Area seems to favor explanations where few motifs cover a large portion of the input graphs (*it is high when a few motifs account for most of the explanatory power and low when many motifs are required*). Nonetheless, I believe that the opposite should be actually preferred: If only a few motifs cover the majority of graphs, then the other motifs present in the explanation are redundant, therefore indicating an explanation with useless motifs.\n\n- **W5:** The authors consider only a very simple model with a linear classification head in the experiments, allowing exact computation of $r*$. It is not clear how these results generalize when the exact computation of $r*$ is not possible, and how the approximation of $r*$ for more complex models will impact the metric values. \n\n- **W6:** It is unclear from the text that the 4Shapes dataset is actually proposed by the authors. Also, several implementational details are missing in the main text, like a proposed description of how motifs look like (their name is not very indicative), the test accuracy reached by the trained GNN, and the specific architecture of that GNN. Some of these details are reported in the Appendix, but no explicit link to that is presented in the main text, making it hard to parse the details coherently. \n\n- **W7:** The sentence in line 349: \n\n> For evaluation, each class is assigned two explanation sets: a good set containing 5 instances of the class-specific motif without the BA backbone and a bad set containing 5 random BA graphs.\n\nis not clear. What do you mean by evaluation here? Also, why does the good set of explanations contain 5 instances of the class-specific motif instead of just 1? Aren't these motifs always the same for a fixed class?\n\n- **W8:** In line 354, the authors say:\n\n> As shown in Figs. 1a–1b, good sets achieve both high class scores and coverage, while random BA graphs may reach high class scores but always yield zero coverage.\n\nis not true. In fact, Fig. 1a shows indeed very low coverage results, but for Class 2, the score is greater than zero.\n\n\n- **W9:** In line 353, the authors claim that \n\n>  random BA graphs may reach high class scores\n\nas in Fig. 1b class scores for Class 2 are considerably high, and this is presented as a weakness of the class score metric previously adopted by other papers. Nonetheless, **I feel this does not necessarily show the intended failure case**. In fact, a valid strategy for the GNN to solve the 4Shapes task is to recognize three out of four motifs, and predict the fourth class when such three motifs are not there in the graph. I suspect this is what is happening in Class 2 in the figure. Therefore, an explanation highlighting a random BA graph is actually a good explanation for Class 2, as it indeed does not contain any of the three other motifs, and this would invalidate your claim that the Class Score can be erroneously high for *bad* explanations. \n\n\n- **W10:** In line 377, the authors write:\n\n> For each class, we compare a unimodal explanation set (containing a single motif)\n\nbut it is unclear which single motif they are referring to, as classes have 2 possible motifs appearing together. In general, this experimental part should be better described and formalized more clearly.\n\n\n- **W11:** Authors provide a link to an anonymous GitHub repo, but the link is provided as a hyperref, which stops people reading the paper on paper from actually seeing the link. Also, I checked the repo, and **the files *metrics.py* and *requirements.txt* are empty**.\n\n**Minors**\n\n- **M1:** In line 51, the authors write that a uniform objective of model-level explainers is to generate motifs attaining a high target class score. Nonetheless, alternative formulations exist, like Azzolin et al. 2023 (already cited), and [1] which I think should be added to the discussion.\n\n- **M2:** Citation format is not consistent across the paper. I would suggest sticking to *\\citep{}* for non-in-text citations.\n\n- **M3:** Some theoretical results, like Theorem 2, are introduced abruptly. A more gentle and intuitive description would be better.\n\n- **M4:** Line 228, in particular the statement *admit efficient spectral-norm based estimates*, needs some references in support.\n\n- **M5:** Authors use the word *classifier score* and *class score* interchangably, which creates confusion. I would suggest sticking to only one way of referring to that concept.\n\n\n\n\n\n[1] GraphTrail: Translating {GNN} Predictions into Human-Interpretable Logical Rules. NeurIPS 2024.\n\n\n\n**In summary**, I believe the paper in the current format is not solid enough for acceptance, but I remain open to reconsidering the score if the authors improve it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)