cs.LGNov 3, 2026

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

Authors: Rocco Mattia Di Mauro, Marco Grassia, Giuseppe Mangioni

Organizations: Department of Electrical, Electronic and Computer Engineering (DIEEI), University of Catania, Italy

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.

Figures & tables

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Generating Intervention Hypotheses using Explainable Explanations on Graphs: G2I, a Two-Stage Greedy Framework

    Aug 24, 2026Mulin Tian, Ajitesh SrivastavaGNN ExplainabilityGraph Counterfactual Explanations

  2. Towards Faithful Graph Explanations with Synergistic Edge Effects via Granular Balls

    Jul 23, 2026Jiancu Chen, Shuyin Xia, Guan Wang +2Graph Neural NetworksGNN Explainability

  3. RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks

    Sep 29, 2026Yuxiang Yao, Zijun ZhaoGraph Counterfactual ExplanationsGNN Explainability