acceptodds
Under review as a conference paper at ICLR 2027

What Does It Mean to Remove an Edge? Intervention-Aware Fidelity for Graph Neural Network Explanations

Abstract

Graph neural network explanations are often evaluated via deletion fidelity, i.e., by deleting their top-ranked edges and measuring the resulting change in model output. Yet, in a message-passing GNN, "deleting an edge" does not specify a unique intervention. Structural deletion removes the edge from the graph and recomputes quantities such as degree normalization and attention, whereas message suppression leaves this structural context intact while blocking the message carried by the edge. The meaning of deletion fidelity therefore depends on what the intervention targets in the model computation. We formalize this distinction and derive sufficient conditions for exact equivalence. The two interventions coincide for additive message passing with edge-set-independent coefficients, but can diverge when aggregation depends on the presence of zero messages or when removing an edge changes the coefficients applied to surviving messages. We then construct intervention-specific edge attributions and evaluate each resulting ranking under both interventions, testing whether their relative fidelity changes with the evaluation intervention. Across nine datasets and a panel of GIN, GCN, and GATv2 models at depths 2-5, all nine GIN controls satisfy the equivalence predicted by the theory. On the target logit, the relative fidelity of the two rankings depends on the evaluation intervention in 10 of 11 reportable GCN and GATv2 cells, and in nine of them each ranking has the larger deletion area under the intervention it was built with. Deletion fidelity is thus not a property of an edge ranking alone. Evaluation protocols should explicitly report the intervention, output functional, target, and perturbation unit, and test alternative intervention semantics when the scientific question does not uniquely determine one.

Primary area:
interpretability and explainable AI
Keywords:
Graph Neural Networks, GNN Explainability, Deletion Faithfulness, Intervention Semantics, Edge Attribution, Causal Interventions, Message Passing, Evaluation Protocols

Reviews

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

The paper observed that "removing an edge" in a message-passing GNN is ambiguous: structural deletion (T_S) removes the edge and recomputes every edge-set-dependent quantity (degree normalization in GCN, attention softmax in GAT), whereas message-channel suppression (T_M) keeps the edge and only zeros the transmitted message. The authors 1) formalized the two interventions in one message-passing template and gave a sufficient condition for their equivalence, 2) pointed out that the choice enters twice, once when an explainer perturbs the model to build an edge ranking and once when the evaluator perturbs it to compute deletion fidelity, 3) cross the two choices in a 2x2 construction-by-evaluation design with contrasts C_S=F_SS-F_MS,C_M=F_MM-F_SM and interaction D=C_S+C_M.

Critical strengths

The motivation is clear, and the paper pined down an ambiguity that prior work left unresolved. Deletion fidelity was reported throughout the GNN-explanation literature with the word "removed" and nothing more, and the paper showed that this hides two different interventions, structural deletion and message-channel suppression, which produce different input to the model whenever the architecture uses degree normalization or attention. This paper was the first to make the choice itself explicit and to note that it is made twice, once by the explainer and once by the evaluator.

Critical weaknesses

W1) The headline "home advantage" claim was supported only for edge IG and may be a property of IG's construction rather than of fidelity. Signed IG along the T_S gate path attributed f_S (1)-f_S (0); evaluating with T_S retraces that same path, thus yielding that r_S scoring higher under T_S is close to what the completeness identity already guarantees. The paper did not test an explainer without a path identity. When it switches to GNNExplainer, matched superiority drops from 9/11 to 4/11 and the signs of C_S,C_M scatter across all four quadrants (BA-2Motifs: +1.38/-0.32; BA-MultiShapes: -0.14/-0.71); however, the abstract and conclusion lead with the 9/11 figure. The authors attributed the GNNExplainer result to restart instability, but no experiment separated "noise" from "IG-specific effect". Without a perturbation-free or converged explainer in the crossing, the strong claim should be stated as IG-specific; as written, it overreaches. This is my main reason for not recommending acceptance.

W2) The empirical panel is narrow and the main text carried little of the evidence; combined with a near-trivial Proposition 1, the contribution rests on a thin base. Proposition 1 followed in a few lines from the definitions (adding zero to a sum, coefficients that do not depend on E); it is necessary to justify the GIN control but does not carry novelty on its own. The paper's weight therefore falls on the empirical finding, and that finding was established on 8 GCN cells and 3 GATv2 cells, the latter all molecular; thus, architecture and domain cannot be separated (acknowledged in Section 8). Mean aggregation, which violates the other condition, had no trained-model cell. More broadly, three backbones are too few for a claim about message-passing GNNs in general: GraphSAGE with mean aggregation (the paper’s own witness for the zero-absorption failure), the original GAT, and attention-based or transformer-style architectures (e.g. GraphGPS, Graphormer) were all absent, and GATv2 itself appears in only three cells. Since Proposition 1 predicted that any architecture failing either condition can diverge, the natural test of the paper’s generality is to run the same crossing on several such architectures; as it stands, the empirical claim was established on one degree-normalized model and one attention model.

Questions for authors
  1. State explicitly which datasets GATv2 was run on and reconcile "22 cells" with nine datasets x three backbones. Were the nine GIN controls run including Tox21-GIN, which Appendix B says was excluded by the health check?

  2. Can the crossing be extended to additional backbones that violate Proposition 1’s conditions, in particular GraphSAGE-mean (zero-absorption failure) and at least one more attention or transformer-style model, and can GATv2 be run on the synthetic datasets as well? The current panel of 8 GCN + 3 molecular GATv2 cells cannot distinguish an architecture effect from a dataset effect.

  3. Can you run the construction-by-evaluation crossing with an explainer that does not perturb the model while constructing its ranking (e.g. attention weights, gradient x input, GNN-LRP), or with a mask-based explainer run to a certified convergence budget? If matched superiority persists there, the strong claim is general; if not, it is an IG property and should be stated as such.

  4. Report depth-level (K = 2, …, 5) C_S,C_M and D for all 11 edge-IG cells, as done for BA-2Motifs-GCN. How many other cells change sign across depth?

  5. Figure 1 used c_uv=1/|N(v)| and called it degree-normalized; GCN uses symmetric normalization with self-loops. Is the toy meant as a mean-aggregation example? If so, label it that way.

  6. How does the framework relate to the removal-semantics axis of Covert, Lundberg and Lee (2021) and to GraphFramEx's hard/soft masking? A sentence positioning T_S/T_M against these would clarify what is new.

7 comments
AuthorsOpenReview ↗

Response to M8Cq (1/2): evidence beyond IG

Please also see our two-part “General response” for the motivation, new results and changes to the revised PDF.

The new experiments show matched superiority beyond IG and beyond GCN and molecular GATv2, with failures that delimit its scope. The revised abstract states this dependence.

W1 and Q3: completeness and evidence beyond IG. IG varies all gates together; deletion visits binary masks selected by a ranking. Completeness constrains the sum of attributions, not the ordering of deletion effects. For f(g1,g2)=g1+2g2+6g12g2f(g_1,g_2)=g_1+2g_2+6g_1^2g_2, straight-line IG assigns scores 5 and 4 with exact completeness, but deleting the corresponding gates decreases the output by 7 and 8. Even the first deletion need not follow the IG ordering.

We tested finite occlusion and signed gate saliency on the same 11 cells. Saliency is gradient × input with respect to the edge gates, evaluated with all gates at one. It uses no integration path or finite perturbation, but remains specific to each gate parameterization.

We also ran GNNExplainer with two objectives. Its default objective, which we call sufficiency, optimizes a mask whose retained edges preserve the prediction. The necessity objective optimizes a small mask whose soft removal lowers the probability of the predicted class, so it is aligned with deletion. This variant tests the role of the objective within GNNExplainer and does not add an independent explainer.

ConstructionDeletion, 11 core cellsRetention, 11 core cells
Signed edge IG9/117/11
Single-edge occlusion9/119/11
Signed gate saliency5/116/11
GNNExplainer, sufficiency objective, lr 0.01 / 0.14/11 / 0/118/11 / 7/11
GNNExplainer, necessity objective, lr 0.01 / 0.19/11 / 9/116/11 / 5/11

The outcome is fidelity on the target logit, read by deletion or by retention, which perturbs the complement of the selected edges. A cell is counted when both CSC_S and CMC_M have positive one-sided 95% lower bounds, clustering by training seed. These are nominal cell-level results, not a simultaneous guarantee across cells. Table 8 reports a sensitivity analysis with seed-level sign-flip tests and Benjamini–Yekutieli correction across 154 comparisons.

Occlusion is optimal for its own single-edge deletion by construction, but not for joint deletions. It still gives 9/11 from 10% deletion onward. Thus matched superiority is not exclusive to IG, but is not universal across explainers.

For the sufficiency objective at learning rate 0.1, the 0/11 result concerns deletion. Matched superiority requires both within-intervention advantages to be positive. Their sum, D=CS+CMD=C_S+C_M, has a nominal 95% interval above zero in 5/11 core cells and in 26/29 additional configurations evaluated with this GNNExplainer setting (Table 7). Thus, an overall matching interaction can remain even when one construction does not win under its own intervention. Under retention, which perturbs the complement of the selected edges, the same masks meet the nominal criterion in 7/11 cells, and 2/11 remain supported in the sensitivity analysis. This sensitivity analysis uses discrete seed-level tests and corrects across 154 comparisons, which limits its power. However, a comparison that does not pass is inconclusive under that rule, rather than evidence of no effect. The gate-saliency experiment addresses the gradient × input alternative in Q3. These are fixed-budget mask results. For the sufficiency objective at learning rate 0.1, the median shares of loss decrease occurring in the last fifth of the 100 epochs are 0.9% under suppression and 1.3% under removal. Yet the median Spearman correlation between two restarts on the same graph is 0.35 and 0.52 (median over graphs within each cell, then over the 11 cells), and at most 0.62 in every cell except Reddit-Binary–GCN. Limited late-stage loss decrease therefore does not establish ranking convergence. Changing the objective nevertheless changes matched superiority from 0/11 to 9/11 under deletion at the same learning rate and budget. We do not attribute this difference to restart instability alone. The independent evidence beyond IG comes from occlusion and gate saliency.

The second part of this reply addresses architectures and domains (W2, Q2), depth (Q4), and accounting and positioning (Q1, Q5, Q6).

AuthorsOpenReview ↗

Response to M8Cq (2/2): architectures, depth and positioning

This comment continues our reply.

W2 and Q2: architectures and domains. Occlusion now covers GCN, GATv2, GAT, GraphSAGE-mean and TransformerConv on the same five datasets: BACE, MUTAG, Mutagenicity, PROTEINS and Graph-Twitter. Matched superiority occurs in 20/25 combinations, respectively 4/5, 5/5, 5/5, 3/5 and 3/5. This tests mean aggregation and additional attention layers, although not GraphGPS or Graphormer.

We also tested GCN, GATv2, GAT and TransformerConv on all four synthetic datasets with degree features. Occlusion gives 7/16, including failures on all four TransformerConv cells. On the twelve GCN/GATv2/GAT cells, signed edge IG gives 12/12. Matched superiority therefore extends to additional architectures, but does not hold for every explainer on those architectures: on the same synthetic tasks, occlusion fails in cells where edge IG succeeds. The complete grids, including negative and inconclusive contrasts, are in Tables 13 and 14.

On the 28 additional configurations evaluated with both edge IG and occlusion, matched superiority occurs in 28/28 and 22/28, respectively, including two Tox21 retrains with class-weighted loss. In two of these cells, some trained models fail the IG completeness check, which requires an aggregate relative error below 5% on eight validation graphs: 9 of 40 in D&D–GATv2 and 2 of 40 in the Tox21–GATv2 retrain. Our protocol certifies an edge-IG cell only when every one of its models passes this check, so these two cells, counted on the remaining models, are not certified. On the other 26 cells, edge IG gives 26/26 (Appendix D.3). Edge IG has no result on Reddit-Binary–GAT, where the attributions are not finite at the required quadrature power. GraphSAGE on the four synthetic datasets fails the model-health check, because, with constant node features, mean aggregation cannot distinguish graphs without isolated nodes that have the same number of nodes. Table 7 lists every cell, with the reason whenever a cell is not counted.

On GraphSAGE and TransformerConv, we report the crossed comparison using occlusion, which applies removal and suppression directly. Edge IG and GNNExplainer approximate structural removal with a continuous gate on each edge. On these backbones, scaling down all incoming gates together leaves the normalized aggregate unchanged until the gates reach zero, where it can jump. Gradients along the continuous part do not capture that jump, so this relaxation can miss the effect of actually removing the selected edges, and we do not use edge IG or GNNExplainer on these backbones.

Q4: depth. For K=2,…,5K=2,\ldots,5, original BA-2Motifs–GCN changes sign in CSC_S and DD, and Synth-Dist–GCN in CSC_S only. The other nine edge-IG cells retain positive contrast estimates at every depth; eight retain positive lower bounds throughout. We distinguish sign changes from loss of support (Table 15).

Q1, Q5 and Q6: accounting and positioning. The original design contains 22 dataset–architecture configurations: nine with GIN, nine with GCN and four with GATv2. The 11 core cells are eight GCN and three GATv2. GATv2 covers BACE, MUTAG, Mutagenicity and Tox21. We corrected the account of the original Tox21 models in Appendix B: they predominantly predict the majority class and were not all excluded before attribution. The extension includes separately retrained GCN and GATv2 models with class-weighted loss. The original Tox21–GIN remains an algebraic control regardless of predictive accuracy.

We have corrected the Figure 1 caption to identify a mean-style coefficient without self-loops, rather than GCN normalization. Covert, Lundberg and Lee already identify removal semantics as a dimension of explanation methods. GraphFramEx organizes evaluation around user needs and necessity versus sufficiency. Our distinction specifies the computation performed when a mask is applied: even a binary mask can remove edges and recompute context, or suppress messages while retaining that context. The contribution is the equivalence criterion and the construction-by-evaluation experiment for these two interventions.

Reviewer_M8CqOpenReview ↗

Additional unresolved points

Thank you for the response and the additional experiments. However, several major points remain unresolved yet.

W1 / Q3. My concern was not that completeness guarantees the deletion ordering, but that constructing and evaluating along the same path makes matched superiority close to mechanical; the counterexample does not address this. The revision partly concedes the point: Section 7 states that matched superiority is more frequent when the explainer’s objective and the evaluator’s reading ask the same question, and Appendix D.3 notes that occlusion’s single-arc advantage holds by construction. The only construction without such alignment, gate saliency, gives 5/11. I therefore read the evidence as narrowing the claim from “IG-specific” to “specific to deletion-aligned constructions”. The abstract, however, still says that the advantage “also occurs with occlusion and signed gate saliency” without the 5/11 count or this qualification. Please state it there and in the conclusion. In addition, the convergence I asked for remains uncertified, as Section 8 acknowledges, and the 0/11 case is defended in the reply with D > 0, a weaker criterion.

W2 / Q2. I appreciate the added backbones, which I had proposed as a test of generality. The results, however, point the other way: the backbones that most clearly violate the conditions of Proposition 1 show the weakest matched superiority (GraphSAGE 3/5; TransformerConv 3/5 and 0/4 in Tables 13 and 14). The conditions therefore indicate when the two interventions differ, but not when the home advantage appears, which the conclusion now calls an open question. These backbones are also evaluated only with occlusion, which inherits the concern in W1. Finally, degree features are held fixed under structural removal (Section 3), so the input no longer matches the perturbed graph in the Reddit-Binary and degree-feature synthetic cells; and GraphSAGE was not run on the synthetic datasets with degree features, without a stated reason.

Reviewer_mssxOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the intervention semantics of deletion fidelity for GNN explanations. The authors distinguish structural deletion from message-channel suppression: the former removes edges and recomputes degree normalization or attention, while the latter retains the corresponding structural context and blocks selected messages. The paper provides sufficient conditions for the two interventions to be equivalent, constructs intervention-specific IG rankings, and uses a construction-by-evaluation crossing to examine the interaction between attribution construction and evaluation intervention. The authors consequently argue that deletion fidelity depends on the intervention definition and that evaluation protocols should explicitly report the relevant choices.

Critical strengths

The paper addresses a practically meaningful problem that reflects the computational characteristics of GNNs. Structural deletion can change the normalization coefficients of surviving messages, so removing an edge and blocking its message do correspond to different model interventions. Clarifying this distinction helps improve the transparency of explanation experiments and avoids implicitly treating implementation details as evaluation standards.

The crossed experimental design is valuable. By separately controlling attribution construction and evaluation intervention, the authors can distinguish evaluator differences for a fixed ranking from construction-by-evaluation matching effects. The GIN equivalence controls, multiple training seeds and depths, and sensitivity analyses concerning the output functional and perturbation unit provide fairly comprehensive support for the main observations.

Critical weaknesses

The mechanistic explanation of the main empirical findings remains limited. The theoretical analysis explains why structural deletion can change the contributions of surviving messages through normalization, but it does not sufficiently explain when these computational differences change explanation rankings or why matched superiority frequently occurs. The experiments contain several exceptions that merit further analysis: the interaction estimate for BA-2Motifs–GCN changes sign with depth; on Synth-Dist–GCN, the message-channel ranking performs better under both evaluators; These findings are primarily reported as heterogeneity or sensitivity, without developing further understanding of how graph structure, propagation depth, or task mechanisms determine the phenomenon. Thus, the paper provides substantial evidence that the phenomenon exists, but insufficient explanation of the conditions and boundaries under which it arises.

The paper identifies ambiguity in evaluation but provides limited practical guidance for choosing an intervention. Section 8 explains that structural deletion concerns removing a relation, whereas message-channel suppression concerns blocking a message while retaining the structural context. This semantic distinction is reasonable, but it is still insufficient to guide researchers in specific explanation tasks. In particular, the paper does not provide sufficient case studies or independent grounds for interpreting conflicting evaluation results in light of the research objective. The current recommendations mainly concern explicitly reporting the intervention and performing crossed evaluation. These improve transparency but do not sufficiently address how to choose and interpret an evaluation. Given that evaluation methodology is a principal contribution of the paper, this gap limits its practical value and the depth of its contribution.

Questions for authors

Which identifiable conditions related to the model, graph structure, or task cause differences in model outputs under the two interventions to translate into ranking differences and matched superiority? Could the authors provide controlled experiments or mechanistic analyses of the depth dependence, the Synth-Dist exception, beyond reporting cell-level results?

Could the authors provide concrete explanation scenarios that specify the research question, the counterfactual assumptions corresponding to each intervention, and principles for interpreting conflicting evaluation conclusions? The choice should be grounded in the explanation objective, rather than solely in which evaluator gives a particular ranking a higher score.

3 comments
AuthorsOpenReview ↗

Response to mssx (1/2): mechanism, joint deletion, features and depth

Please also see our two-part “General response” for the motivation, new results and changes to the revised PDF.

The new analyses provide a concrete attention mechanism on MUTAG and locate where single-edge rankings fail under joint deletion. They also test whether prediction-changing edge sets transfer between interventions. The original depth mechanism in BA-2Motifs and the Synth-Dist exception remain unresolved.

A concrete mechanism. On MUTAG–GATv2 we identify a case in which an edge transmits a message but removing it has no effect. When all messages entering a node are identical, their attention-weighted average is unchanged if one edge is removed and the remaining weights are renormalized. Suppressing that edge's message instead subtracts its weighted contribution without redistributing the weight. If the identical-message condition holds at the receiving node in every layer, single-edge removal leaves the network output unchanged. In the trained MUTAG–GATv2 models, the corresponding diagnostic identifies almost all edges with near-zero structural IG scores (Appendix A, "Attention renormalization in trained GATv2 models"). This explains why a zero removal effect need not mean that an edge was unused. It does not explain the general occurrence of matched superiority.

When the ranking of individual effects fails for sets. Occlusion ranks edges by the effect of removing each one separately. The effect of removing several together need not equal the sum of those individual effects. We measured where this difference overturns the advantage of the ranking built under the evaluating intervention. We decompose the top-kk contrast into the difference of summed single-edge effects and a non-additive remainder difference. The first term is nonnegative by construction, so a reversal requires the second to outweigh it (Appendix D.3).

On BA-2Motifs–GCN with degree features, CMC_M becomes negative at three edges: −0.34-0.34, with pointwise 90% seed-clustered interval [−0.53,−0.13][-0.53,-0.13]. The structural estimate turns negative at twelve edges and its interval is below zero at thirteen. For TransformerConv it reverses at four, while the message-channel contrast stays positive through thirteen (Figure 8).

Correct single-edge ordering therefore need not survive joint deletion. The decomposition localizes the failure of additivity; it does not identify redundancy or a specific layer mechanism. The exploratory intervals are pointwise.

For GNNExplainer on BA-2Motifs–GCN, we also compare the necessity and sufficiency objectives while keeping structural removal fixed. On the target logit, the advantage observed with continuous masks reverses in the integrated comparison of equal-size edge sets at both learning rates (Figure 6). On the probability scale, the integrated contrasts are small (Figure 7). These observations do not separate discretization from incomplete optimization.

Features and depth. The prediction that degree features would remove the failures was not supported. GCN with degree features gives matched superiority on all four synthetic tasks with IG, but occlusion still fails on BA-2Motifs and SPMotif. On original Synth-Dist, CSC_S remains negative at depths 2–4 and is only +0.008 at depth 5, while CMC_M stays positive (Table 15).

The second part of this reply covers the choice of intervention and the transfer of prediction-changing edge sets between interventions.

AuthorsOpenReview ↗

Response to mssx (2/2): choosing the intervention and transfer

This comment continues our reply.

Choosing the intervention from the question. The two interventions answer different questions. The choice should follow from the question and be made before seeing which explainer scores higher.

QuestionInterventionWhat the answer covers
How does the model respond if the selected directed edges are absent from the input graph?Structural removalNode features fixed, normalization and attention recomputed on the remaining edges
Which transmitted messages does this prediction rely on?Message-channel suppressionThe selected messages are suppressed without removing their edges, and the following layers process the resulting states
Which of two explainers is better?Both, reported separatelyIf their order reverses, the preferred explainer depends on the intended intervention. Neither order establishes a quality that is independent of the intervention

Reading a disagreement. When the same edge set has different effects under the two interventions, the discrepancy shows that the conclusion depends on how the intervention is implemented. It does not by itself identify the cause. A user who asks which messages carry the signal should read the suppression result. A user who asks how the model reacts to an edited input graph should read the removal result, knowing that a zero there does not mean that the edge was unused. Evaluating an existing ranking under the second intervention costs one additional deletion sweep.

For transfer between interventions, a MUTAG–GCN example shows the effect on one graph (Figure 9, whose caption states how the graph was selected). Suppressing five directed edges changes the class, but removing them does not: the target logit minus the best rival logit is −1.78 versus +0.19, from +3.89 intact (Figure 9).

Across that cell, 46% of graphs admit a prediction-changing prefix under suppression up to 50% of edges. At the first tested budget where suppression changes the class, removing exactly the same edges leaves the class unchanged in 49% of those graphs. At a fixed 10% budget across all graphs, disagreement is 17%, versus 11% for random rankings. These are directed computational edges with fixed node features, not chemical counterfactuals.

The practical recommendation is to test a proposed perturbation under the intervention that will actually be executed. An undirected relation edit additionally requires both directions and a policy for derived features.

The disagreements are not uniformly small threshold crossings. For structural IG on BA-2Motifs–GCN at a 20% budget, the median distance to the decision boundary, taking the closer of the two outputs, is 0.95 and 0.89 times the checkpoint's typical intact target–best-rival gap in the two discordant groups. These are descriptive medians, not probabilities. Other cells have smaller gaps. As predicted by the equivalence result, the GIN control has no disagreement (Figure 10, Tables 16 and 17).

On the conditions under which output differences become ranking differences: Proposition 1 says when the outputs of the two interventions coincide, and beyond it we do not have a general condition. Our results indicate that it cannot be read off the explainer or the architecture alone. On the same 12 synthetic cells of the extension block, the interval of D excludes zero in 12 with edge IG and in 11 with gate saliency, but matched superiority holds in 12 and in 3. What we can show are worked examples, in the second of today's general comments. Removing one bond of the BA-2Motifs house changes the class under one intervention and not under the other, two cuts of the same size in Synth-Dist lead to different diagnoses under the two interventions, and in both cases, for the GCNs trained on constant features, the difference arises at the first layer. On the depth dependence on BA-2Motifs, the same comment shows that a group of motif arcs has opposite effects when suppressed alone and after the arcs ranked before it. This shows that the effect of a group of arcs depends on which arcs were removed before it, but it does not explain in general how the effect changes with depth. As a practical consequence for evaluation, attention coefficients, a ranking built under neither intervention, receive a different advantage over chance from the two interventions in most cells (third of today's comments).

Reviewer_9o2wOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

GNN explanation quality is routinely measured by deletion fidelity — remove an explanation's top-ranked edges and watch the model output change. But "removing an edge" is not a well-defined intervention. The paper distinguishes two: Structural deletion (TS):​ physically remove the edge and recompute everything derived from graph structure (degrees, GCN normalization, GAT attention). Message-channel suppression (TM):​ keep the edge but zero out the message it carries, leaving all structural context intact.

Critical strengths
  • Exposes a real, overlooked ambiguity. The structural-vs-message distinction is subtle and has been implicitly collapsed by nearly all prior GNN-faithfulness work.

  • Rigorous theory with a built-in control. Proposition 1 + a clean induction proof, and the elegant use of GIN as a predicted equivalence control that validates the whole pipeline end-to-end.

Critical weaknesses
  • The divergence is partly intuitive. That GCN degree-renorm and GAT attention shift when edges disappear is somewhat expected; the surprise is modest, and the theoretical conditions are only sufficient (not necessary), limiting their prescriptive reach.

  • Confounded empirical scope. Only graph classification, frozen trained models, and just 3 GATv2 cells, all molecular — architecture and domain are entangled and can't be separated in that stratum.

Questions for authors

The GNNExplainer analysis is explicitly exploratory: restarts disagree, convergence wasn't certified, and matched superiority "carries no across-cell error guarantee." How does it support the thesis?

5 comments
AuthorsOpenReview ↗

Response to 9o2w (1/2): GNNExplainer and statistical scope

Please also see our two-part “General response” for the motivation, new results and changes to the revised PDF.

The additional experiments separate two claims that the original GNNExplainer discussion did not distinguish sufficiently. A fixed explanation can receive different fidelity scores under the two interventions. Matched superiority further requires each intervention-specific ranking to outperform the other under its own evaluator. GNNExplainer supports the first claim more broadly than the second.

GNNExplainer and statistical scope. The result depends on both the optimization objective and the evaluation question. Sufficiency is GNNExplainer's default objective, which optimizes a mask whose retained edges preserve the prediction. The necessity objective optimizes a small mask whose soft removal lowers the probability of the predicted class. Deletion perturbs the selected edges, and retention perturbs their complement. Each entry counts matched superiority on the target logit, which requires both CSC_S and CMC_M to have positive one-sided 95% lower bounds, clustering by training seed. In each column, the extension evaluates all four rows on the same 29 additional dataset–architecture configurations, including two Tox21 retrains with class-weighted loss.

Objective, learning rateCore: deletionCore: retentionExtension: deletionExtension: retention
Sufficiency, 0.014/118/119/2918/29
Necessity, 0.019/116/1117/2914/29
Sufficiency, 0.10/117/117/2913/29
Necessity, 0.19/115/1117/298/29

Thus the 0/11 deletion result does not describe the same masks under retention.

The revised Figure 2 shows GNNExplainer at learning rate 0.1. At 0.01 and 100 epochs, the PyTorch Geometric default used in the submission, a validation diagnostic of the sufficiency objective places a median 24% of the loss decrease in the last fifth of the epochs for the message-channel construction and 17% for the structural one. At 0.1 both shares are close to 1%. Table 1 reports both rates. The smaller late-stage loss decrease motivates this comparison, but does not establish that the resulting edge rankings would remain unchanged with further optimization.

A separate comparison holds the intervention fixed and compares, across edge budgets, the target-logit changes produced by equal-size edge sets selected by the two objectives. On the core cells, deleting necessity-selected edges produces a larger target-logit drop in 10/11 cells under each intervention at both learning rates. Under retention, the direction depends on learning rate and on whether logit or probability is measured (Table 12, Figures 3–5).

The necessity variant tests the role of the objective within GNNExplainer. We do not attribute the failures to restart instability alone.

The counts are exploratory, without error control across cells. We report individual contrasts and intervals, not a population-wide success rate. Table 8 adds a multiplicity sensitivity analysis with seed-level sign-flip tests and Benjamini–Yekutieli correction across 154 comparisons. Under deletion, 8/11 and 7/11 necessity-objective cells remain supported at learning rates 0.01 and 0.1. Under retention, 2/11 sufficiency-objective cells at learning rate 0.1 remain supported after correction, compared with 7/11 under the nominal criterion. The remaining cells are inconclusive under the corrected test.

The evidence beyond IG also includes single-edge occlusion and signed gate saliency. Occlusion achieves matched superiority in 9/11 cells, eight of which also satisfy the criterion with edge IG. Signed gate saliency does so in 5/11 and uses no integration path or finite perturbation. Under retention, occlusion gives 9/11, gate saliency 6/11 and edge IG 7/11 (Table 1).

The second part of this reply addresses architecture–domain confounding and the role of the sufficient conditions.

AuthorsOpenReview ↗

Response to 9o2w (2/2): architectures, domains and sufficient conditions

This comment continues our reply.

Architecture–domain confounding. On real datasets, the common grid crosses BACE, MUTAG, Mutagenicity, PROTEINS and Graph-Twitter with GCN, GATv2, GAT, GraphSAGE-mean and TransformerConv. Occlusion reaches matched superiority in 20/25 combinations, including all five GATv2 cells. GATv2 is also evaluated on Graph-SST2 outside this common grid.

On the four synthetic datasets with degree features, occlusion reaches matched superiority in 7/16 combinations across GCN, GATv2, GAT and TransformerConv. For GATv2 specifically, occlusion gives 2/4 and edge IG 4/4. The expanded panel therefore contains both successes and failures outside molecular datasets (Tables 13 and 14).

Intuitive divergence and sufficient conditions. We agree that a difference between the two computations is expected under degree normalization and attention. Its consequences are less obvious. The general comment shows that current libraries mix the two interventions, and that selecting an explainer under one and evaluating under the other reduces how often the selected explainer outperforms the alternative on graphs not used for selection, in 8 of 11 cells. We retain Proposition 1 as a sufficient equivalence criterion and as the basis of the GIN control; violating its assumptions permits divergence but does not guarantee it, nor does it predict matched superiority. We withdrew the unsupported non-necessity claim and clarified the role of the layer representation.

We hold the trained model fixed because the question is how its explanations are constructed and evaluated. The expanded experiments address the architecture–domain confounding, but remain limited to graph classification.

Thank you for your reply. However, after considering new results and other reviews, I have decided to maintain my score.

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

The authors address the issue of fidelity evaluation for GNN explanations, highlighting that evaluation results may differ depending on how edge removal is implemented.

Critical strengths
  • How to evaluate the found GNN explanations has been studied as an important research question.
Critical weaknesses
  • While the authors study an important issue about the evaluation of GNN explanations, the observation that how edge removal impacts fidelity scores is not novel.
  • The paper lacks deeper insights into the implications of different evaluation protocols. Furthermore, the authors did not provide enough experimental analysis of edge removal or a comparison with existing studies on the evaluation of explanations.
  • Despite the wide range of GNN explanation methods, the experiments are limited to only two methods with SubgraphX in the appendix.
Questions for authors
  1. Have the authors examined the rank correlation (e.g., Spearman's ρ or Kendall's τ) between edge attribution rankings generated using structural deletion and message suppression?
  2. Although the paper demonstrates that matching the construction and evaluation interventions often yields higher fidelity, it remains unclear whether this corresponds to better explanation quality. Could the authors evaluate both interventions against ground-truth explanatory structures on synthetic datasets (e.g., BA-2Motifs and SPMotif) to investigate whether either intervention provides a more reliable assessment of explanation quality?
  3. How do the proposed findings relate to existing fidelity evaluation frameworks, such as GInX-Eval, Robust Fidelity, and F-Fidelity?
2 comments
AuthorsOpenReview ↗

Response to kqFp: novelty, ground truth and explainer selection

Please also see our two-part “General response” for the motivation, new results and changes to the revised PDF.

The new experiments test both the matching effect beyond IG and its practical consequences. In particular, the evaluation intervention can change which explainer is selected, with a measurable cost on graphs not used for selection.

Novelty and relation to prior evaluation frameworks. GInX-Eval already reports that changing the edge-removal strategy can change the ordering of explainers on a trained model. The revised text makes that relationship explicit. Holding the model fixed does not by itself distinguish our study. We define the two interventions through their computation and distinguish two questions: does changing the evaluation intervention change the score of a fixed explanation, and does it change which of two intervention-specific rankings performs better? Our crossed design measures these separately. The theory specifies sufficient conditions under which neither difference can occur, and the experiments test their consequences for explainer selection and prediction-changing edge sets.

GInX-Eval also introduces fine-tuning on degraded graphs. Robust Fidelity develops an information-theoretic formulation and measures addressing distribution shift, while F-Fidelity uses explanation-agnostic fine-tuning and random masking. Our experiments do not establish whether those alternative measures remove or retain the effects reported here. We therefore distinguish the computational intervention from the further question of how evaluation handles distribution shift.

Methods. On the 11 core cells, matched superiority on deletion fidelity occurs in 9/11 with signed edge IG, 9/11 with single-edge occlusion and 5/11 with signed gate saliency. GNNExplainer gives 4/11 and 0/11 with its sufficiency objective at learning rates 0.01 and 0.1. A necessity variant gives 9/11 at both rates. This last result is an objective control within the mask family, not an independent explainer. All counts use nominal seed-clustered bounds and are reported with the individual contrasts. The evidence supports a matching effect beyond IG, with clear dependence on the method and objective (Table 1, per cell in Table 7).

Q1: agreement between the rankings. We measured Spearman correlation between the structural and message-channel rankings within each graph. For edge IG, the cell estimates range from +0.043 to +0.452 on ten cells and are −0.209 on BA-MultiShapes–GCN. The GIN controls are between 0.999 and 1.000. Thus the intervention changes the ranking itself, not just its fidelity score. Table 9 also reports the correlations for occlusion and saliency.

Q2: explanatory ground truth. We compared fidelity with recovery of the motifs supplied as ground-truth explanations by the synthetic benchmarks, and examined motif ablations against size-matched random ablations. These comparisons do not identify a uniformly preferable evaluator. On BA-2Motifs–GCN, the fidelity–recovery correlations depend strongly on class composition. For example, structural occlusion evaluated by removal has correlation −0.435 when classes are pooled, but +0.030 and +0.296 within the two classes (Table 20). We therefore do not interpret the pooled correlation as evidence that an evaluator measures explanation quality reliably.

Motif ablation also depends on the intervention. On BA-MultiShapes–GCN, its target-logit drop relative to size-matched random ablation is −6.57 under removal and +1.05 under suppression, with seed-clustered 90% intervals [−6.91,−6.22][-6.91,-6.22] and [0.58,1.56][0.58,1.56]. On SPMotif–GCN the same quantity is positive under both interventions, +3.30 under removal and +0.73 under suppression (Table 19). This diagnostic cannot serve as an independent ground truth for choosing between the interventions. The annotation describes the dataset's motif; establishing what the trained model relies on requires additional evidence. We keep that distinction explicit rather than equating higher deletion fidelity with better motif recovery.

Practical consequence: selecting an explainer. We compare message-channel Input × Gradient and structural edge occlusion. For each trained model, we select the more frequent winner in target-logit deletion area on half of its test graphs and evaluate on the other half, then swap the halves. Selecting under a different intervention from the final evaluation reduces how often the selected method outperforms the alternative on graphs not used for selection, in 8/11 cells after Benjamini–Yekutieli correction, by up to 27 percentage points. The statistic averages the two final evaluation interventions. The two GIN controls give zero. This establishes a consequence for the tested pair, not a general ranking of explainer quality (Table 11).

In the third of today's general comments we report two results on the alternative measures you raised. The reference implementation of Robust Fidelity contains both structural removal and message-channel suppression, selected by its code path, and when our reimplementation evaluates the same random draws under both interventions, a fixed ranking receives different scores and matched superiority depends on the explainer ("Robust Fidelity under both interventions"). F-Fidelity fine-tunes the model under random masking, and its published experiments and released code do not provide a graph evaluation: the paper evaluates it on images, time series and natural language, and the code covers images. The F-Fidelity paper cites Robust Fidelity, evaluated above, as a partial solution to the same out-of-distribution problem in the graph domain. To check the point beyond fidelity curves, the revised manuscript also evaluates an edge-restricted form of the extension-sufficiency test (EST) of Azzolin et al. (ICLR 2026), with the same sampled perturbations under both interventions (Table 10, our general comment of November 12, and "Beyond fidelity curves" in the third of today's comments), where the extent of matched superiority also depends on the output measure. On the implications of the protocol and the number of methods, the first two comments report four explainers on the extension block and a single bond whose removal changes the class under one intervention and not under the other, and the third reports attention as a fixed ranking on 36 cells.

Comments on the paper

6 comments
AuthorsOpenReview ↗

General response (1/2): why the choice of intervention matters

We thank the reviewers for their careful reading. Several comments ask, in different forms, why a reader should care which of the two edge interventions is used. We answer that question in this comment. A second comment summarizes the new evidence on matched superiority and the changes to the PDF, and the individual replies address each point.

Structural removal deletes an edge from the graph and recomputes the normalization or attention that depends on it. Message-channel suppression keeps the edge and blocks the message it transmits.

Both interventions are already in use, usually without being named. We read the current code of three libraries. In PyTorch Geometric, the masking paths we verified, listed in Appendix D.5 and Table 18, scale messages and pass the original edge index. The built-in fidelity metrics apply the mask in the same way, although the documentation describes this evaluation as removing edges. GraphXAI builds explanations with message masks and evaluates them by removing edges. GraphFramEx evaluates by removing edges by default. Fidelity numbers produced with different tools can therefore refer to different interventions, and a mask can be built under one intervention and scored under the other. We read this as an unstated convention, not as a defect of any library.

The distinction also applies across evaluation metrics. PyG's built-in fidelity metrics use message-channel suppression in the paths we audited. By contrast, the Extension Sufficiency Test (EST) of Azzolin et al. evaluates subgraphs that contain the explanation, removing nodes and edges structurally. Moving from fidelity to EST therefore changes both the evaluation question and, in this comparison, the intervention. To separate these choices, we also evaluated an edge-restricted EST under both interventions, keeping nodes, features and sampled edge sets fixed (Table 10).

The choice changes conclusions. We report results by experimental configuration, or “cell”: a dataset and architecture with specified input features and training setup. We measured three consequences.

  1. Which explainer a user would select. We compare Input × Gradient on the edge mask with single-edge occlusion. For each trained model, we select the method that more often achieves higher deletion fidelity on half of the graphs. Changing the evaluation intervention changes that selection in 21% to 79% of cases, depending on the cell. We then compare the methods on the remaining graphs. Selecting with a different intervention from the one used for this final evaluation reduces how often the selected method outperforms its competitor, by 6 to 27 percentage points in 8/11 cells after Benjamini–Yekutieli correction. We repeat the comparison with the two graph halves exchanged.
  2. Whether a set of edges changes the prediction. We select the top 10% of edges using message-channel edge IG and apply both interventions to that same set. The interventions disagree on whether the predicted class changes in 8% to 91% of graphs across cells, with a median of 31%. Random edge sets of the same size give a median of 23%, so substantial disagreement is not specific to the explainer.
  3. Whether the motif supplied as ground truth by the benchmark appears important. On BA-MultiShapes–GCN, ablating this motif lowers the target logit by 6.57 less than a random ablation of the same size under removal, and by 1.05 more under suppression. The seed-clustered 90% intervals are [−6.91,−6.22][-6.91,-6.22] and [0.58,1.56][0.58,1.56] (Table 19). The same annotation looks less important than random edges under one intervention and more important under the other.

When the distinction can be ignored. Proposition 1 gives sufficient conditions under which the two interventions coincide. GIN satisfies them, and on the GIN controls both the selection statistics and the transfer disagreement are zero. A user can therefore check the message aggregation and edge-dependent coefficients of their architecture before deciding whether the distinction matters.

The second part of this general response reports the new results on matched superiority, the changes to the PDF and our recommendations.

AuthorsOpenReview ↗

General response (2/2): explainer results, changes to the PDF and recommendations

This comment continues the general response.

What the new experiments say about matched superiority. Matched superiority means that each intervention-specific ranking outperforms the other when evaluated under its own intervention. It is not exclusive to Integrated Gradients, and it is not universal. Under deletion, on the 11 core cells of the submitted study, it occurs in 9 with edge IG, in 9 with single-edge occlusion and in 5 with signed gate saliency, the gradient of the target logit with respect to the edge gates at the intact graph, which uses no integration path. For GNNExplainer it depends on the objective: 4 and 0 cells with the sufficiency objective at learning rates 0.01 and 0.1, and 9 cells at both rates with a necessity objective. Under retention, which perturbs the complement of the selected edges, edge IG, occlusion and gate saliency give 7, 9 and 6 cells (Table 1). We also expanded the experiments to additional datasets and architectures. On the 28 additional configurations evaluated with both edge IG and occlusion, matched superiority occurs in 28/28 and 22/28 under deletion, respectively, and in 27/28 and 19/28 under retention.

The dependence is not confined to deletion and retention curves. In the edge-restricted EST, matched superiority occurs in 7/11 cells for edge IG, 8/11 for occlusion and 5/11 for signed gate saliency when the output change is measured by total variation. With the maximum absolute target-logit change, the counts are 1/11, 2/11 and 2/11. These nominal results show that the intervention remains relevant under a different evaluation test, while the matching advantage depends on the measured quantity (Table 10).

We do not have a rule that predicts when matched superiority occurs. We report one verified mechanism, on MUTAG–GATv2, and we state which exceptions remain unexplained. All results obtained after submission are exploratory. The matched-superiority counts use nominal seed-clustered intervals without error control across cells, and Table 8 reports a sensitivity analysis with Benjamini–Yekutieli correction.

Changes in the revised PDF, marked in red.

  • The abstract and the contributions state that the 9 of 11 result concerns edge IG, and report the dependence on the explainer and on the objective.
  • The main text gains a table with all explainers (Table 1) and paragraphs on explainer selection, on the attention mechanism and on an edge-restricted extension-sufficiency test. Figure 2 now shows GNNExplainer with both objectives at learning rate 0.1.
  • The limitations say how to choose the intervention from the question.
  • We corrected the Tox21 statement in Appendix B, the Figure 1 caption and the relationship to GInX-Eval, and we withdrew the unsupported non-necessity claim and clarified the role of the layer representation.
  • Appendix D adds the per-cell tables, the multiplicity sensitivity analysis, the depth contrasts, the transfer analysis, the library reading and the sensitivity to benchmark motifs.

What we recommend. State the intervention next to every fidelity number. Fix it from the question before comparing explainers. Check a proposed edge set under the intervention that will actually be executed. Evaluating an existing ranking under the second intervention costs one additional deletion sweep.

Dear reviewers,

The rebuttal period is ending soon. Please read the authors rebuttal and check if they addressed your concerns. Please acknowledge the rebuttal and adjust your scores accordingly.

Thanks.

-AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.