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.
Two notions of deletion
- Structural deletion removes the edge from the graph and recomputes quantities such as degree normalization and attention.
- 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.
Equivalence conditions
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.
Intervention-specific attributions and evaluation
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.
Empirical results
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.
Implications
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.
- Output functional: the function of the model output used to compute change (e.g., target logit).
- Target: the model output element under study.
- Perturbation unit: the graph element altered by the intervention (e.g., edge).