Certified Evaluation of Model-Level Explanations for Graph Neural Networks

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 distributionfree 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 with 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 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 metric for comparing explanations and the methods that generate them. However, class score alone is insufficient to distinguish between explanations. Since every explainer explicitly optimizes a loss term that rewards high target class scores, the resulting motifs often become pathological: they achieve high scores but stray far from the data distribution and may bear little resemblance to meaningful 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 measures 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 motifs 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 metrics 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 a set of explanations generated by a model-level explainer can be said to sufficiently capture the classifier's decision process, formalizing sufficiency through a risk functional and deriving distribution-free 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 sufficiency 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, we also derive uncertainty bounds that yield confidence intervals, ensuring that comparisons between methods remain statistically reliable. Through extensive experiments, we demonstrate that our metrics reliably complement the class score, enabling meaningful distinctions between explanations that would otherwis