acceptodds
Under review as a conference paper at ICLR 2027

Auditing Explanation Preservation in Sparsified GNN Pipelines

Abstract

We study explanation auditability of graph sparsifiers for graph neural networks (GNNs). Existing sparsifiers preserve structural properties or predictive accuracy, but in deployment workflows where predictions are inspected or audited, do the explanations produced on the sparsified graph remain consistent with the full-graph reference explanations? We introduce an audit framework built around a node-level outcome that permits controlled explanation change and identifies four failure modes: prediction flip, excessive explanation drift, top- structural rearrangement, and top- mass erosion. The framework evaluates preservation at marginal, conditional, and worst-case levels and provides exact finite-sample confidence bounds for the complete test-node population and its structural subgroups. We audit thirteen sparsifiers, four post-hoc explainers, and five node-classification benchmarks spanning homophilic and heterophilic graphs. Experiments spanning 280 main audit runs indicate that (i) prediction-preserving sparsification does not imply explanation-preserving sparsification, (ii) distinct sparsifier families exhibit signature failure modes, (iii) preservation rates vary systematically with local graph structure, with high-degree nodes substantially less likely to satisfy the audit outcome, and (iv) overall preservation rates do not establish that the same preservation target holds across all structural groups. We argue that explanation preservation is a measurable property of deployed GNN pipelines, distinct from accuracy, and one that should be reported alongside it.

Primary area:
interpretability and explainable AI
Keywords:
GNN explanation, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_fQKsOpenReview ↗
Rating
2(−1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

he paper audits whether inference-time graph sparsification preserves a frozen GNN pipeline's predictions and reference explanations. A node passes when the class prediction is unchanged and normalized L1 drift, top-k overlap, and reference top-k mass retention meet prespecified tolerances. The framework reports overall, structural-stratum, and worst-stratum preservation, with exact finite-population lower confidence bounds obtained by hypergeometric inversion. A 280-run main matrix covers five datasets, thirteen sparsifier implementations and four explainers plus identity controls. Appendices examine reference fidelity, co-training, a GraphSAGE slice, tolerance sensitivity, seed variation, and an ogbn-arxiv pilot.

Critical strengths
  1. The deployment question is concrete and distinct from ordinary predictive accuracy. Reproducing a documented explanation is a legitimate reference-relative requirement, and the paper explicitly avoids claiming that the full-graph explanation is ground truth.
  2. The audit outcome, finite-population estimand, and statistical assumptions are clearly specified. Conditioning on fixed pipelines/outcomes makes uniform sampling without replacement hypergeometric; graph dependence between node outcomes does not invalidate this design-based argument. Bonferroni addresses simultaneous structural-group claims without assuming independent groups.
  3. The main evidence shows a substantial empirical gap: non-identity pipelines have mean prediction preservation .904 versus joint preservation .438, with considerable dataset/sparsifier heterogeneity. The audit is useful even though these metrics need not agree by construction; the measured size and structural distribution are the contribution.
  4. The supplementary controls materially strengthen the paper. Appendix E finds the gap among references passing sufficiency/necessity checks; Appendix F repeats a node-matched slice with GraphSAGE; Appendix D distinguishes co-trained matched-model and cross-model comparisons; Appendix G evaluates all 125 tolerance settings; Appendix H reports seed variability. These should be credited rather than requested as absent.
  5. The all-strata example responsibly separates lack of certification from actual poor preservation: a census follow-up can resolve uncertainty in a weakly sampled group. The scalable pilot and audit-time reporting help connect the framework to practical use.
Critical weaknesses
  1. Several named sparsifiers are adapted proxies, limiting method/family-level conclusions (Appendix I). The “Spectral” implementation uses resistance-based deterministic top-k ranking rather than stochastic reweighted spectral sampling, and “t-spanner” is a sampled shortest-path-tree ranker without a guaranteed stretch property. Learned methods are mostly frozen off-design preprocessors. These are disclosed, but the main text and result labels should distinguish the evaluated adaptations from the original methods and their guarantees. The NeuralSparse companion is useful but cannot validate every learned/proxy implementation. The audit framework survives this issue; conclusions about canonical sparsifier families require narrower wording.

  2. Drift should be decomposed into unavoidable pruned mass and changes on retained edges (Secs. 3, 5.2). In original edge coordinates, pruned edges contribute their full reference mass to L1 drift regardless of how retained-edge scores behave. This is relevant to preservation, not an error in the definition, but it can mechanically explain part of the failures. Reporting removed reference mass and retained-edge score movement separately would show what the additional audit reveals beyond pruning important edges. Degree associations may likewise reflect neighborhood size, support, or attribution concentration rather than a new structural causal effect.

  3. Failure-mode “signatures” depend on priorities and tolerances (Sec. 5.2, Appendix G). A single dominant label is assigned in the order prediction, drift, overlap, mass. Consequently, 71% drift and near-zero mass erosion are priority-conditioned shares, not independent violation frequencies. Appendix G shows at least one mode ordering changes as tolerance changes. Include the marginal/co-occurring violation rates or state the priority explicitly beside every family-level interpretation.

  4. Stochastic-explainer robustness and operating-point breadth remain limited. Fixed seeds define a valid reproducible pipeline and make identity tests meaningful, but Appendix H varies backbone and audit-node seeds, not independent explainer randomness. A cross-seed identity comparison would contextualize whether ordinary explainer instability is of similar magnitude; it is a robustness study rather than a prerequisite for the fixed-seed guarantee. The main pruning ratio is .5 and also sets k_i, so sparsity and top-k evaluation budget are coupled. The 125-setting tolerance sweep does not vary that retention ratio.

  5. Reference preservation and deployment quality should remain separate throughout . A failed preservation audit can represent either a faithful changed explanation or degraded explanation quality. Appendix E appropriately studies reference fidelity but does not fully assess the sparsified explanation's fidelity to its own deployed model. The paper should present the audit as measuring change under a chosen behavioral contract rather than treating every failure as harmful explanation degradation. The exact confidence machinery is standard; the strongest novelty is its integration with a broad, interpretable empirical audit.

Questions for authors
  1. Can the main tables explicitly rename the resistance-ranking and sampled-tree adaptations and summarize how each differs from the original method? What actual retained edge ratios and weight conventions were achieved?
  2. From existing explanation vectors, how much L1 drift is contributed by reference mass on pruned edges versus retained-edge changes, and how does that decomposition vary by degree?
  3. Please report independent failure-indicator frequencies or their overlaps, alongside the priority-ordered shares. Are family signatures robust to changing that order?
  4. Are independent-explainer-seed identity results or retention-ratio sweeps already available? If not, please delimit the fixed-seed, rho=.5 claim rather than treating the tolerance sweep as a substitute.
  5. Is the targeted all-strata follow-up intended as descriptive evidence for selected pipelines, with confidence claims only within each fixed pipeline, rather than simultaneous post-selection inference across all 260? Please clarify the stated scope.
5 comments
Reviewer_fQKsOpenReview ↗

follow-up and reconsideration

My concern that the evaluated spectral and t-spanner methods do not implement the original algorithms or preserve their guarantees remains unaddressed. This makes the conclusions about sparsifier families less convincing, so I am revising my rating from 3 to 2.

Dear Reviewer,

We are still preparing the response and will submit it as soon as it is ready. Thanks!

AuthorsOpenReview ↗

W1/Q1,W3/Q3

Thank you for your suggestions and comments.

W1

We will distinguish the evaluated adaptations from the original methods in the main text and result labels.

For learned/proxy methods, we will state more clearly that the main experiments apply fixed edge scores to a separately trained full-graph GNN. Conclusions about individual methods and families will be limited to the implementations and deployment settings evaluated. We will clarify that the NeuralSparse companion experiment evaluates joint training only for NeuralSparse; it does not validate the other learned/proxy implementations or support family-wide conclusions.

Q1

We agree that the method names should make these adaptations clear. We will revise the names throughout the paper as follows:

  • "Spectral" becomes "Resistance-ranked pruning." It keeps edges with the highest approximate effective-resistance scores instead of sampling and reweighting edges as in the original spectral method. The original spectral guarantee therefore does not apply.
  • "tt-spanner" becomes "Sampled-tree pruning." It counts how often each edge appears in shortest-path trees rooted at sampled nodes and keeps the edges with the highest counts. It does not enforce the original method's stretch bound.

Weight conventions. Both adaptations assign weight 1 to retained edges. Resistance scores determine edge selection only; no inverse-probability reweighting is applied.

Across four explainers, preservation rates changed by at most 1.5 percentage points on Chameleon and 2 percentage points on Squirrel.

Actual retention. At the nominal budget ρ=0.5\rho=0.5, both methods retain the following numbers of edges.

DatasetRetained / original entriesEntry retentionResistance-ranked: node pairsSampled-tree: node pairs
Cora5,278 / 10,55650.0%50.0%50.4547%
CiteSeer4,552 / 9,10450.0%50.0%50.2636%
PubMed44,324 / 88,64850.0%50.0%50.0857%
Chameleon18,050 / 36,10149.9986%54.1615%52.5453%
Squirrel108,536 / 217,07349.9998%52.6511%51.3952%

W3 / Q3

We examine twelve evaluated implementations: Random, degree-distribution pruning, DSpar, Resistance-ranked pruning, Sampled-tree pruning, GraphPRI, NeuralSparse, SparseGAT, SGS-GNN, SGCN, GraphUltra, and MoG. These span five datasets and four explainers (240 configurations), using the resistance-ranked results for Chameleon and Squirrel. We retain ρ=0.5\rho=0.5 and (ϵ,β,μ)=(0.5,0.5,0.5)(\epsilon,\beta,\mu)=(0.5,0.5,0.5) and average percentages equally across configurations, as in the original failure-share table.

We measured how often each condition fails and how often multiple conditions fail on the same node. We also recomputed the assigned failure shares under all 24 priority orders to test whether the family differences persist. Changing the labeling order does not change joint pass/fail outcomes or preservation rates. For the 240 configurations specified above, the table compares individual failure frequencies with the shares assigned under the original priority:

Violated conditionAmong all audited nodes (%)Among failing nodes (%)Assigned share under the original priority (%)
Prediction preservation9.3420.3820.38
Explanation drift49.6290.9371.78
Top-kk overlap43.5965.777.83
Retained mass45.4982.780.010

The original priority is prediction flip, drift, top-kk rearrangement, then mass erosion. On average, 89.06% of failing nodes violate multiple conditions; 80.83% violate both drift and retained mass. Mass erosion is therefore common, but rarely receives the assigned label because another condition fails earlier in the order. We will correct the statement that mass erosion itself is rare and include individual and overlapping frequencies alongside the assigned shares.

Across all 24 priority orders, drift's assigned share ranges from 4.13% to 90.93%, and mass erosion's from 0.010% to 82.78%. Two aggregate contrasts retain their direction across all orders: the evaluated learned/proxy implementations have more prediction-flip labels, and the structural implementations have more top-kk rearrangement labels. However, the differences range from 0.024 to 6.93 percentage points and from 1.44 to 5.10 points, respectively, and do not hold uniformly within every dataset or explainer. We will describe these as aggregate differences at the stated tolerances, rather than universal family signatures, and state the labeling order beside the corresponding interpretations.

Reviewer_BLpwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether graph sparsification preserves GNN explanations when predictions remain unchanged. It proposes an audit framework to measure prediction and explanation preservation. Experiments show that high prediction preservation does not necessarily imply high explanation preservation, and high-degree nodes are generally less likely to pass the audit.

Critical strengths

The paper is well written and easy to follow. I enjoyed reading it. The framework is clearly formalized, with precise definitions of the audit outcomes, evaluation metrics, and levels of auditability. The empirical evaluation is extensive, covering 13 sparsifiers, 4 post-hoc explainers, and 5 node-classification benchmarks; The appendix provides substantial additional experiments.

Critical weaknesses

My first concern is that, after reading the paper, I am still not fully convinced why preserving the reference explanation within prespecified tolerances is a practically important requirement. Sparsifiers may aim to preserve different properties, such as graph structure or predictive performance, whereas explanations concern the evidence behind a specific prediction. Multiple distinct sets of evidence may support the same prediction, so sparsification could change the explanation without degrading its quality or downstream utility.

My second concern is that, I am still unsure what a practitioner should do with the audit results. If explanations are inconsistent, should practitioners choose another sparsifier, improve the explainer, or accept the change?

My third concern is that, the analysis of the experimental findings remains mostly descriptive. A deeper analysis of the underlying causes would help turn these observations into more useful insights.

Questions for authors

Please see my concerns above.

4 comments

Dear Reviewer,

We are still preparing the response and will submit it as soon as it is ready. Thanks!

Thank you for your comments.

W1

The motivating example in the Introduction clearly articulates a scenario where preserving the reference explanation is a practically important requirement. In this example, a lender uses a full-graph GNN's explanations to support communicated credit decisions. When a sparsified GNN replaces that system, revisiting the same cases may produce the same decisions but highlight different relationships. If the replacement is expected to reproduce the explanation behavior previously reviewed, these changes matter even when the new explanations are faithful. The lender needs to know whether the replacement remains consistent with the documented explanations or requires renewed review. Prediction preservation alone does not answer that question. In this setting, our audit framework checks whether the replacement preserves the previously reviewed prediction and explanation behavior within prespecified tolerances.

W2

Practitioners first specify the explanation tolerances, required preservation rate, and confidence level. The audit then guides the following actions:

  • Accept on preservation grounds or collect more evidence. Consider a hypothetical DSpar--GNNExplainer candidate retaining 75% of edges and a fixed 1,000-node population. Two alternative, prespecified audits sample uniformly without replacement and yield 190/200 or 19/20 passes. Both observed rates are 95%, but their exact 95% lower confidence bounds are 92.1% and 78.6%. Only the first supports a 90% preservation requirement. The second motivates a larger confirmatory audit, not immediate replacement of the sparsifier.
  • Evaluate another sparsifier. In our checked ten-node Cora pilot at 50% retention, Random with GNNExplainer preserves 8/10 predictions but passes joint preservation on only 1/10 nodes. The audit exposes explanation changes missed by prediction checks. If these changes are unacceptable and the reference is suitable, inspect the failed nodes and conditions, then compare another sparsifier under the same requirements.
  • Improve or replace the explainer. If separate fidelity checks or unchanged-graph repeats reveal a weak or unstable reference, review the explainer's settings or choice before changing the sparsifier.
  • Accept a different explanation after validation. If different explanations are permissible, assess their faithfulness and usefulness directly. That evidence can justify accepting a change that the audit identifies as outside the chosen preservation tolerances.

Note that any revised pipeline should be audited again against the same preservation requirements.

W3

We have examined the sources of explanation drift and degree-preservation associations in Appendix L, and the effects of the retention budget in Appendix K. Summary:

Sources of drift. Across ten configurations at ϵ=0.5\epsilon=0.5, removed reference mass alone exceeds the tolerance in 159 of 269 drift failures. The remaining 110 cross it only when we include score changes on retained edges (Appendix L, Table 19 and accompanying text). This suggests that sparsification affects explanations through both edge removal and changes in how the explainer scores the retained edges.

Degree-preservation associations. We find weaker absolute degree-preservation correlations in eight of ten configurations after accounting for two-hop edge count, the number of positive reference scores, reference-score concentration, and local edge retention (Appendix L, Table 20). This suggests that the observed degree association partly reflects other graph and explanation characteristics.

Retention budget. Increasing ρ\rho from 0.250.25 to 0.900.90 improves preservation in all four configurations of Random and DSpar with GNNExplainer on Cora and PubMed, with the top-kk comparison size fixed (Appendix K, Figure 9). This suggests that less aggressive sparsification can improve preservation under unchanged evaluation criteria.

I have read your reply, thank you.

I understand the motivation from the lending example, but I feel that my original concern is not addressed.

As far as I know, some GNN sparsification methods focus on preserving properties such as graph structure or predictive performance, which may be quite different from how explanations are generated and what explanations focus on. Therefore, I would not be surprised if the explanations change after sparsification, and I don't think we should necessarily expect them to remain the same, especially when preserving explanations is not an objective of the sparsification method.

Also, multiple different sets of evidence may support the same prediction, so a change in explanation does not necessarily mean that the new explanation is worse or less useful. I understand that explanation changes may require additional review in your lending example, but I am not convinced why preserving the original explanation should be an important requirement for sparsified GNNs in general.

Reviewer_UY5VOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper audits whether explanations derived from a sparsified graph remain consistent with those of the original graph using four criteria: label consistency, small drift, large overlap, and large representation overlap. They try to audit a sampled set such that a fraction of $ 1 - \delta$ of the complete test-node population passes the audit with a confidence of 1−α1 - \alpha. Their main experiments show that preserving label predictions after sparsification does not necessarily preserve explanation quality, as most nodes fail the audit, with explanation drift emerging as a major contributing factor.

Critical strengths
  • The paper conducts a diverse set of experiments across multiple sparsifiers, explainers, and datasets, complemented by extensive robustness checks and additional analyses. These experiments provide convincing empirical evidence and strengthen the reliability of the findings.

  • The paper clearly distinguishes prediction preservation from explanation preservation and evaluates explanation changes relative to a designated reference without assuming access to ground-truth explanations.

Critical weaknesses

The audit is presented as a deployment tool, but the scope of its guarantee and several design choices limit its practical use. First, the finite-population bound covers only the fixed test split, with the trained model, explainer seeds, and sparsifier held fixed, as the Limitations section acknowledges. It says nothing about future query nodes, retrained models, or the same pipeline run with different explainer seeds. Second, the paper gives no guidance on choosing the tolerances (ε, β, µ) or the target 1−δ, although the conclusions depend heavily on them. The only target used, 1−δ = 0.5, accepts that half of all explanations may fail, which is far below what the motivating credit-notice example would plausibly require. Finally, the main setting does not match how sparsifiers are typically deployed. It uses a model trained on the full graph and sparsified only at inference, on small graphs such as Cora and CiteSeer. In practice, sparsification is usually applied during training as well and is motivated by scale. The only large-scale experiment (ogbn-arxiv) uses unspecified “reduced budgets” and gives very different numbers (Random 0.78 vs. about 0.07 on Cora), so practitioners can take little from it.

Furthermore, the central finding that preserving predictions does not imply preserving explanations is consistent with the well-known fragility of post-hoc explanations under input perturbations.

Questions for authors
  1. Is δ\delta fixed at 0.5 across all settings, as in the all-strata audit? This threshold seems relatively permissive, as it allows up to half of the explanations to fail the audit, which may be insufficient to establish that the sparsifier preserves explanation quality.

  2. The four failure criteria may be correlated. Rather than basing overall failure solely on the most severe criterion, could a weighted evaluation better capture overall explanation quality?

  3. For measuring D, should the difference between the reference explanation graph and the sparsified graph also be considered? If these graphs differ substantially, it seems difficult for D to remain small.

  4. Explaining heterophilous graphs is known to be challenging for the explainer adopted in this paper. Although the resulting explanations serve as reference points rather than ground truth, how reliable is this evaluation when the reference explanations themselves may have limited quality?

4 comments

Dear Reviewer,

We are still preparing the response and will submit it as soon as it is ready. Thanks!

Thank you for your comments.

W1

The proposed audit framework evaluates whether a specified sparsified deployment meets a required prediction-and-explanation preservation rate across the full test population, using only a sample of nodes. We explain why this population-level claim is useful, provide evidence on explainer-seed robustness, and describe how to audit changed models or query populations.

  • Auditing a specified test population. In the introduction we provided a motivating scenario regarding replacing a full-graph system whose explanations have already been documented or communicated. Our framework determines whether sampled evidence supports the required preservation rate over those cases, without recomputing every explanation. This is the practical role of the fixed-population guarantee.

  • Explainer-seed variation. Appendix H examines variation across backbone and audit-node sampling seeds. In our additional explainer-seed study, we use 50 fixed nodes per dataset and compare GNNExplainer seeds 1--4 with seed 0 on the unchanged graph and model. Mean preservation is 99.5% on Cora and 100% on PubMed. On the same nodes, Random and DSpar at 50% retention give 2--54% preservation with seed 0 fixed. All comparisons use (ϵ,β,μ)=(0.5,0.5,0.5)(\epsilon,\beta,\mu)=(0.5,0.5,0.5). In these settings, sparsification changes exceed the measured seed variability. This is empirical robustness evidence, separate from the fixed-seed guarantee.

  • Changed models and new query populations can be audited separately. Appendix D already compares a jointly trained NeuralSparse--GCN deployment with an independently trained full-graph reference. If the GNN is retrained or we want to assess a different set of nodes, we apply the same audit procedure to that setting and compute a new confidence bound.

W2

Section 4.2 defines the parameters, and Appendix G examines how tolerance choices affect the audit results. For deployment, we recommend the following selection procedure.

Choosing the tolerances. Practitioners can review examples of acceptable and unacceptable explanation changes separately from the audit. These judgments inform the maximum normalized score change ϵ\epsilon, minimum top-kk Jaccard overlap β\beta, and minimum retained reference top-kk mass ratio μ\mu. For example, when both top-kk sets contain ten edges, β=2/3\beta=2/3 requires at least eight shared edges. The tolerances should be fixed before auditing, rather than adjusted afterward to obtain a favorable result.

Choosing the preservation target. The target 1−δ1-\delta specifies the minimum fraction of nodes that must satisfy all preservation conditions. It should reflect the deployment's acceptable frequency of violations. The corresponding lower confidence bound must meet this target, including within every designated group when that is the requirement.

We use 1−δ=0.501-\delta=0.50 to illustrate the all-strata procedure. A credit deployment would be audited against its required preservation target using the same confidence-bound criterion.

W3

  • Training-time relevance. We hold the trained GNN fixed to isolate sparsification's effect when replacing an existing full-graph deployment. Appendix D (Table 9) also evaluates NeuralSparse jointly trained with a GCN on Cora and Chameleon, using either that GCN or an independently trained GCN as the full-graph reference.

  • Large-graph evidence. In a separate ogbn-arxiv study (Appendix B, Table 6), we evaluate Random pruning with GNNExplainer across three backbone seeds. We represent edges in both directions and retain both directions of each selected edge at 50% retention. We train GCNs separately on the full and pruned graphs for 200 epochs, selecting checkpoints by validation accuracy. The 50 audit nodes, pruning mask, explainer seed, and preservation tolerances remain fixed.

    ComparisonMean pred. preservation ±\pm SD (%)Mean joint preservation ±\pm SD (%)
    Full-trained GCN on full versus pruned graph88.0±3.588.0\pm3.52.0±0.02.0\pm0.0
    Full-trained/full reference versus sparse-trained/pruned deployment86.7±4.286.7\pm4.22.0±0.02.0\pm0.0
    Same sparse-trained GCN on full versus pruned graph88.0±0.088.0\pm0.02.0±0.02.0\pm0.0

    We observe that prediction--explanation gap persists with training-time sparsification, including when the same trained GNN is evaluated on both graphs.

  • Reduced budgets and the ogbn-arxiv - Cora rate difference.. With Random and GNNExplainer, the directed ogbn-arxiv experiment used a 20-epoch GCN training cap and 50 audit nodes, vs. 200 epochs and 200 nodes on Cora. Both used 100 explainer optimization epochs, 50% retention, and the same tolerances. On ogbn-arxiv, 39 of the 50 audited nodes pass the audit (preservation rate 0.780.78), including 32 nodes with zero reference explanations. Cora records 15/200 passes (0.0750.075), with no zero references.

W4

Fragility of post-hoc explanations under input perturbations: This is related, but our paper is about the auditability of a specified sparsified deployment. We assess whether sampled evidence supports a required rate of prediction-and-explanation preservation over a fixed test population and its structural groups.

Central Finding: The prediction/explanation preservation gap is one empirical finding (RQ1). The paper's central contribution is a framework and empirical study of explanation auditability under graph sparsification. It integrates established finite-population confidence bounds with the preservation criteria, structural analysis, and empirical evaluation, as also noted by reviewer fQKs. Our framework addresses three connected questions:

  • How much of the reference behavior is preserved? It measures the fraction of nodes satisfying a joint prediction-and-explanation preservation requirement, allowing changes within prespecified tolerances.
  • Where does preservation fail? It identifies the violated requirements and examines preservation within structural node groups. This distinguishes overall preservation from preservation within each designated group.
  • What claim does the audit support? It applies established finite-population bounds to determine whether sampled outcomes support a required preservation rate over the fixed test population, or simultaneously across its prespecified structural groups.

The empirical study evaluates these questions across sparsifiers, explainers, and graph datasets, and examines how audit size affects the strength of the supported claims.

Q1

We set δ=0.5\delta = 0.5, corresponding to a preservation target of 1−δ=0.501-\delta=0.50, for the all-strata audit. The other experiments report preservation rates and confidence bounds without applying a population-level target. In deployment, this target should be specified a priori based on application-specific reliability requirements. Our framework does not prescribe a universal value.

Q2

The labeling order does not affect which nodes pass the audit or the resulting preservation rates. Under Definition 1 (Section 4.2), a node passes only when all four conditions hold. The priority order selects one descriptive label for a node that already fails. It is not the rule used to determine failure. We will make this distinction explicit in the paper.

Our objective is to evaluate prediction and explanation preservation after sparsification, rather than overall explanation quality. We require every preservation condition to hold, so that satisfying one condition cannot compensate for violating another. A weighted score allowing such compensation would not enforce these individual requirements. To examine overlapping failures, we computed how often each condition fails and how often multiple conditions fail on the same node.

Q3

Yes. Graph differences should enter the drift measure. Since our objective is to measure preservation of the full-graph reference explanation, removing edges that carry reference attribution constitutes explanation change. Our definition includes this loss by assigning zero scores to removed edges. We therefore retain both removed reference mass and retained-edge score changes in DD. To make their contributions explicit, we now quantify them separately in Appendix L. This decomposition shows how much drift follows directly from pruning and how much arises from changes on retained edges.

Q4

  • What evidence supports reference quality? Appendix E, Table 9 in the submitted manuscript already evaluates reference fidelity on 100 nodes each from Cora and Chameleon with all four explainers. The tests select the highest-scoring 50% of local edges: sufficiency checks whether keeping those edges preserves the prediction; necessity checks whether removing them changes it. Appendix E also examines preservation among references passing both tests. This assesses fidelity to the model without assuming that every reference is reliable.

  • How does limited reference quality affect the evaluation? We checked whether preservation failures persist within the subset passing both fidelity tests. In our additional GNNExplainer evaluation on 50 Chameleon nodes with Random sparsification at 50% edge retention, 15 references pass both tests. 9 out of 15 nodes preserve prediction, but only 1 meets all preservation requirements. Thus, preservation failures also occur among references passing these fidelity tests. As Appendix E explains, preservation measures agreement with the reference; failure does not by itself establish degraded explanation quality.

I appreciate the authors' detailed response and the additional clarifications. Their explanations regarding the pass/fail criterion (Q2), the interpretation of (1-\delta), and the budget settings for ogbn-arxiv have addressed my questions, and I acknowledge that my earlier understanding of these aspects was not entirely accurate. Nevertheless, my primary concern remains unresolved: the guarantee is still established under the assumption of a fixed test pool and fixed explainer seeds, which limits the scope of the claim. Therefore, I will maintain my original rating.

Comments on the paper

1 comment

Dear reviewers,

As the rebuttal period is coming to an end, I kindly remind you to check the authors' responses. If you have not yet responded, please indicate whether your concerns have been adequately addressed. Many thanks!

Best,

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.