The Key Blind Spot in GNN Explanation Evaluation: What Does Deleting an Edge Really Mean?

Graph neural network (GNN) interpretability research has long relied on a seemingly intuitive evaluation approach: delete the top-ranked edges from an explanation method and observe how much the model output changes—the larger the change, the more faithful the explanation. But a new paper points out a neglected semantic ambiguity in this pipeline: under the message-passing framework, "deleting an edge" does not correspond to a unique intervention operation, and deletion fidelity can change depending on the intervention.

Two Kinds of "Deletion": Structural Deletion and Message Suppression

The paper first clarifies a distinction that is implicitly glossed over. Structural deletion actually removes an edge from the graph structure and recomputes quantities that depend on the graph structure, such as degree normalization and attention coefficients; message suppression preserves the full structural context and merely blocks the message transmitted along that edge.

Both operations are intuitively called "edge deletion," but they intervene on different objects: one changes the input graph the model computes on, the other changes the information flow during computation. The meaning of deletion fidelity therefore depends on which part of the computation the intervention targets—if the evaluation protocol does not specify this, the conclusions drawn are ambiguous.

The message-passing framework is the fundamental computational paradigm underlying most GNNs: each node updates its representation by aggregating messages from neighboring nodes (typically scaled by edge weights or attention coefficients), and after multiple layers of iteration obtains its final embedding. Edge coefficients (such as the degree-normalized coefficients in GCN or the attention weights in GAT) determine the contribution magnitude of each message. The key point of this framework is that message passing is tightly coupled with graph structure—coefficients are often derived from structure, so any intervention on structure may in turn change how messages are aggregated. Only by understanding this can one see why structural deletion and message suppression diverge under certain architectures.

When Are the Two Interventions Equivalent? Sufficient Conditions from Theory

The paper formalizes this distinction and derives sufficient conditions under which the two interventions are exactly equivalent. The conclusion is: for additive message passing where edge coefficients are independent of the edge set, structural deletion and message suppression yield identical results.

Divergence arises in two scenarios: when the aggregation process is sensitive to the presence of zero messages (e.g., using max aggregation or special handling of empty neighborhoods), or when deleting an edge changes the coefficients applied to surviving messages (e.g., attention weight reallocation). In these cases, the two interventions produce different changes in model output, thereby altering the fidelity evaluation of the same edge ranking.

The value of this analysis is that it transforms "is edge-deletion evaluation reliable?" from an empirical debate into a decidable condition question: given a model architecture and aggregation method, one can determine whether the evaluation conclusions are sensitive to intervention semantics.

Additive message passing means that node updates aggregate neighbor messages by summation (or weighted summation), rather than by max, min, or other nonlinear pooling. Under additive aggregation, blocking a message along an edge is equivalent to setting its weight to zero, and if structural deletion merely removes that edge without changing the coefficients of other edges, the two yield the same result. Edge coefficients independent of the edge set requires that each edge's weight does not change with the presence or absence of other edges—for example, degree-normalized coefficients in GCN depend on node degree, and deleting an edge changes the degree, thereby affecting the coefficients of surviving edges, so GCN does not satisfy this condition; some models using fixed weights may satisfy it. Together these two conditions delineate the scope of applicability of the equivalence.

Experiments: Systematic Testing on Nine Datasets

The authors construct edge attribution methods tailored to specific interventions and evaluate each ranking under both interventions, testing whether its relative fidelity changes with the evaluation intervention. The experiments cover nine datasets, with a model panel including GIN, GCN, and GATv2, at depths ranging from 2 to 5 layers.

The results show a clear stratification: all nine GIN control groups satisfy the theoretically predicted equivalence, validating the correctness of the sufficient conditions. On the target logit, however, 10 of the 11 reportable GCN and GATv2 units exhibit relative fidelity that depends on the evaluation intervention; in 9 of these units, each ranking achieves a larger deletion area under "the intervention it was constructed against."

In other words, rankings constructed with message suppression evaluate better under message suppression, and rankings constructed with structural deletion evaluate better under structural deletion—the "quality" of a ranking is not an intrinsic property but is bound to the evaluation intervention.

Deletion area (deletion AUC) is a quantification of deletion fidelity: edges are ranked by the importance assigned by the explanation method, the top-ranked edges are deleted sequentially, and the area under the curve of model output (e.g., the logit of the target class) versus deletion ratio is recorded. A larger area indicates that the deleted edges are indeed crucial to the model output and the explanation is more faithful. The paper compares "relative fidelity"—the relative magnitude of deletion areas of the same ranking under different interventions, rather than absolute values. This makes the conclusions independent of specific datasets or model scales and instead focuses on the impact of intervention semantics itself on evaluation conclusions.

Implications for Evaluation Protocols

The paper's conclusions point directly to practice: deletion fidelity is not a property of an edge ranking alone. Evaluation protocols should explicitly report four elements—the intervention method, the output functional, the target quantity, and the perturbation unit; when the scientific question itself does not uniquely determine the intervention semantics, one should also test whether results are robust under alternative interventions.

For researchers of GNN explanation methods, this means that when comparing different methods, if each uses a different edge-deletion semantics, the comparison may not be on the same baseline. For downstream users, before deploying an explanation tool, confirming whether the intervention used in its evaluation is consistent with the computational path they care about is a necessary step to avoid misinterpretation.

The significance of this work is not to negate deletion fidelity but to decompose it from a broad metric into an experimental design choice that must be explicitly declared. The rigor of interpretability evaluation often lies in these details that are taken for granted.

Output functional refers to the model output quantity observed during evaluation, such as the logit of the target class, predicted probability, or the entire output vector; target quantity refers to the object being explained, which may be a single node's prediction, a whole graph's class, or the existence of an edge. The perturbation unit is the smallest unit of the intervention operation, which can be an edge, a node feature, or a subgraph. Together these four elements determine the specific meaning of deletion fidelity: changing any one of them may yield different fidelity values. The paper emphasizes explicitly reporting these elements precisely to put comparisons between different studies on the same baseline and avoid spurious judgments of superiority or inferiority arising from different default assumptions.