Certified-Minimal Counterfactuals for Graph Neural Networks by Bound-and-Prune Search

A counterfactual explanation for a graph neural network (GNN, a model that predicts a node's label by repeatedly mixing information from its neighbors) answers a concrete question: what is the smallest change to the graph that would flip this prediction? Current explainers return some small set of edge deletions or additions that does flip the prediction. None of them can say whether a smaller set exists. They optimize soft, continuous edge masks with gradient descent and then round them to discrete edits, so they report "we found 2 edges" with no way to tell whether 1 would have done. This note proposes a discrete search that returns counterfactuals together with a certificate of minimality, meaning a proof that no smaller edit set within a declared candidate pool flips the prediction. The search stays tractable on graphs the size of ogbn-arxiv by pruning, which means discarding whole families of candidate edits that provably cannot succeed.

The pruning borrows the logic of anti-monotone search from data mining: if a partial candidate cannot meet a threshold, no extension of it can either. Frequent-itemset mining and community search use this to skip exponentially many candidates. GNN outputs are not monotone in the edge set, so the trick cannot be applied directly. It can be applied to an upper bound on how much any set of remaining edits could move the prediction, because that bound is monotone by construction. The two-sentence version: we bound how far a GNN's decision margin can move under any edit set drawn from a group of candidates, and we discard every group whose bound cannot reach the decision boundary. The result is a branch-and-bound counterfactual search that either finds the minimal flip or proves a lower bound on its size, and the same bounds tell us how far existing explainers are from optimal.

Core Claim

Fix a trained GNN $f$, a target node $v$ with predicted class $c$, and its margin $m(G) = f_c(G)_v - \max_{c' \neq c} f_{c'}(G)_v$, the gap between the winning logit and the runner-up. For a set $P$ of candidate edge edits (deletions and additions) and a budget $b$, define $U(P, b)$ as a computable upper bound on $\max_{S \subseteq P, |S| \le b} \big(m(G) - m(G \oplus S)\big)$, the largest margin reduction any edit set of size at most $b$ drawn from $P$ could achieve, where $G \oplus S$ is the graph with edits $S$ applied. Any sound relaxation of this maximum is non-decreasing in both $P$ and $b$. That property gives an exact pruning rule. If a search node has already committed edits $S$ and has remaining pool $R$, then

$$ U\big(R,\; b - |S|\big) < m(G \oplus S) \;\Longrightarrow\; \text{no extension of } S \text{ within } R \text{ flips } v, $$

and the whole subtree can be discarded. This is the GNN analogue of prefix pruning in itemset mining, as discussed in An Erratum on "Pushing Convertible Constraints in Frequent Itemset Mining". It is also the analogue of the recall upper bound that Web Question Answering with Neurosymbolic Program Synthesis uses to discard partial programs. The difference is that monotonicity here is a property of the bound, not of the model.

The claim is that such bounds can be made tight enough and cheap enough on message-passing GNNs to support three results. First, the search can certify minimal counterfactuals on the standard synthetic benchmarks and on a large fraction of nodes in real citation graphs. Second, it can scale additions, which have an $O(N^2)$ candidate space, by bounding groups of endpoints rather than individual edges. Third, it can measure, for the first time, the optimality gap of existing gradient-based explainers.

Relation to Prior Work

Four counterfactual explainers motivate the gap. CF-GNNExplainer learns a soft deletion mask by gradient descent and reports at least 94% accuracy with 1.47 to 2.39 removed edges on average on BA-SHAPES, TREE-CYCLES and TREE-GRID. It cannot say whether those counts are minimal, and it handles deletions only. ATEX-CF handles additions by restricting candidate endpoints with attack-derived structural orbits and optimizing a signed mask. Its pruning is a greedy pass after optimization that removes redundant edits, which halves runtime on ogbn-arxiv but certifies nothing. XPlore adds feature edits and a "role swap" trick that lets gradients reach non-existent edges, at a memory cost that grows with the number of potential edges. GNNViz uses a related $L_1$-regularized continuous perturbation. All four share the continuous-relaxation-then-round design. We replace that design with discrete search. We keep their outputs as warm starts and as the comparison targets.

Monotonicity has entered GNN explanation only once. GlobalGCE uses the monotone submodularity of a coverage objective to select dataset-wide rules greedily with a $(1-1/e)$ guarantee. Its local candidate generation relies on gSpan and a variational autoencoder, and it is evaluated only on small molecular graphs. We apply monotone bounds to the local, per-instance search that GlobalGCE leaves unguided.

Two lines of work constrain the design. An Optimal Algorithm for Certifying Monotone Functions shows that monotone functions admit size-$C(f)$ certificates in $O(C(f)\log n)$ queries. It also proves that finding the exact minimal instance-specific certificate needs $\Omega(\binom{n}{k}/k)$ queries in the worst case. We therefore do not claim worst-case efficiency. We claim that model-specific bounds make typical instances easy, and we report the instances where the search times out. Probing GNN Explainers finds that random edges often beat popular explainers on unfaithfulness. A counterfactual whose flip is verified by a forward pass is valid by construction, so the open question this proposal addresses is minimality rather than faithfulness.

Two sources supply method. Our group-level bounding over endpoints follows the interval pruning of Synthesizing Trajectory Queries from Examples, which discards whole intervals of thresholds once one fails. Our cheap per-edit bounds rest on the degree-damping argument in Fast nearest-neighbor search in disk-resident graphs. That paper shows that the effect of routing through a high-degree hub shrinks roughly inversely with its degree, which is why it can turn hubs into sinks with little error. Degree-normalized message passing has the same property, so edits incident to hubs get small bounds and are usually pruned early.

Research Program

The first component is a bound library for common architectures. It covers the simplified linear model, GCN with ReLU, and GraphSAGE with mean aggregation, all with two or three layers. The first sound pruning step is exact: edits that touch nothing within the receptive field of $v$, the set of nodes within $L$ hops for an $L$-layer model, have zero effect. Additions are subtler, because adding $u$–$w$ with $u$ in the receptive field brings $w$'s representation inside.

For edits inside the receptive field, we propagate interval bounds layer by layer through the computation graph of $v$. The intervals account for the changed degree normalization and the changed neighbor sets under any $b$ edits from a pool. For linear models the effect of a single edit is exact, and we bound interactions among edits by the second-order term that degree renormalization introduces. For ReLU models we use standard interval and linear-relaxation propagation. These are generic neural-network bounding techniques, and the file contains no GNN-specific paper on them that we can cite.

The second component is endpoint grouping for additions. We precompute each node's layer-wise embeddings once and build a hierarchical box tree over them. A single bound then covers "add an edge from $u$ to any node in this box", and a failing box removes thousands of candidate endpoints at once. This is the step that removes the $O(N^2)$ barrier without the automorphism computations ATEX-CF's orbits require.

The third component is the search itself. It runs best-first branch-and-bound over edit sets in increasing size, ordered by single-edit bound. Gradient explainers supply an incumbent: their output gives an upper bound on the minimal size, and the search tries to close the gap down to it. The search returns one of three outcomes: a certified minimal counterfactual; a counterfactual with a proven lower bound on the minimal size; or, when a time budget expires, the gap between best found and best proven. The candidate pool is always declared explicitly, for example "deletions in the receptive field plus additions from receptive-field nodes to any node". Certificates are relative to that pool, and we say so.

The analysis component asks how tight the bounds are as depth, degree and hidden width vary. We expect them to loosen with depth, because interval widths compound per layer. This is the main risk, and we plan to measure it rather than assume it away.

Baselines

The naive reference points are two. The first is random edits: sample edits uniformly from the declared pool at increasing sizes until the prediction flips. It mirrors the Random Edge baseline that Probing GNN Explainers found surprisingly strong. The second is exhaustive enumeration over the receptive-field pool with no bounds, run only where it terminates. It supplies ground-truth minima on synthetic graphs and the runtime our pruning must beat.

The strongest deletion-only competitor is CF-GNNExplainer, whose reported figures are at least 94% accuracy and 1.47 to 2.39 removed edges on average on the three synthetic benchmarks. The strongest competitor for additions and scale is ATEX-CF, run from its public code (ATEX_CF repository). It reports a per-instance runtime on ogbn-arxiv that falls from 6.12s to 3.00s with its pruning step, and the best overall rank of 2.40 against 4.67 for the runner-up. XPlore reports gains of up to +56.3% validity and +52.8% fidelity over CF-GNNExplainer. No reported result was found on Lacuna for XPlore on ogbn-arxiv specifically, so we will run it ourselves where memory allows.

All methods explain the same trained GNN checkpoints on the same sampled target nodes. Each gets the same per-instance wall-clock budget on the same single GPU, and the gradient methods get the same hyperparameter-tuning budget their papers describe. Beating them means equal or higher validity at equal or fewer edits on every benchmark. On ogbn-arxiv it also means runtime within a small constant factor of ATEX-CF's reported 3.00s, plus certificates of minimality, which no baseline provides at all.

Three ablations isolate the key ingredient, the monotone group bound. The first removes endpoint grouping. The second replaces interval bounds with the trivial receptive-field rule only. The third removes the gradient warm start. Each is measured by search nodes expanded and fraction of instances certified.

Why not just…?

Why not just run a greedy search, adding the single edit that most reduces the margin until the prediction flips? This is the strongest threat. Greedy may well find the optimum on most instances, and ATEX-CF's post-hoc greedy pass already behaves this way. Our answer is that greedy cannot tell you when it is optimal, and our search can. We will report the fraction of instances where greedy's answer equals the certified minimum. If that fraction is near 100% on every benchmark, the honest conclusion is that the method is chiefly an auditing tool that certifies cheap heuristics rather than a better explainer, and we would reframe the work that way.

Why not just brute-force the receptive field, since it is small? On BA-SHAPES it is, and there exhaustive search is our ground truth. On ogbn-arxiv, average degree times two or three hops puts thousands of edges in the receptive field, and additions bring the whole node set in as endpoints. Enumerating size-3 sets is then infeasible, and Gupta and Manoj's lower bound says no generic method avoids this in the worst case. The runtime curves comparing exhaustive search and bounded search as $b$ grows will show where enumeration stops being viable.

Why not just accept continuous explainers, since their counterfactuals are verified anyway? Validity is verified, but size is not, and the minimal size is the quantity users read as "how fragile is this prediction". If gradient explainers are routinely one or two edits above optimum, the comparative claims papers make about edit counts are unreliable. Measuring that gap is the experiment below, and a small gap would itself be a useful, publishable finding.

Proposed Experiments

The first experiment establishes ground truth. On BA-SHAPES, TREE-CYCLES and TREE-GRID, using a three-layer GCN as in CF-GNNExplainer, we compute exact minimal deletion-only and deletion-plus-addition counterfactuals for every motif node. We then report the distribution of (explainer size − certified minimum) for CF-GNNExplainer, ATEX-CF, XPlore, greedy and random. TREE-CYCLES is especially informative, because XPlore notes that some flips there require adding edges that deletion-only methods cannot find. Our search should reproduce that observation exactly and quantify it.

The second experiment tests scale. On Cora, Chameleon and ogbn-arxiv we sample a few hundred target nodes stratified by degree and margin. We report validity, mean edits, fraction certified minimal within the time budget, and mean proven lower bound on uncertified nodes. We also report wall-clock time and search nodes expanded, against the ATEX-CF figure of 3.00s per instance.

The decisive checks are three. If interval bounds are too loose beyond two layers, the certified fraction on ogbn-arxiv will collapse with depth; we will plot it against layer count and report the result whatever it shows. If degree damping matters as predicted, pruning rates for edits touching high-degree nodes should be markedly higher than for low-degree ones. If greedy matches the certified optimum nearly everywhere, the paper's contribution becomes the certification and the measured optimality gap, not a better explainer, and we will state that plainly.