Graph Counterfactual Explanations Made Minimal: NP-Hard Problem Tamed by Local Bounded Search

Machine learning models built on graph-structured data now sit at the heart of decisions that touch molecular design, brain imaging, fraud detection, and drug discovery. Yet when these black-box models classify a molecule as toxic or a brain network as autistic, researchers and clinicians often have little insight into why. A powerful remedy comes from counterfactual explanations: a slightly modified version of the input that flips the model’s prediction. In graph land, that means a graph counterfactual, a graph as close as possible to the original that nevertheless pushes the model to a different answer. The smaller and sparser this counterfactual, the more useful it is as an explanation, because it points directly at the structural or attribute changes that actually matter for the decision.

A new study published in the journal Machine Learning by Rodrigo García, Mario Alfonso Prado-Romero, Francesco Gullo, and Giovanni Stilo delivers the first principled treatment of the step that most graph counterfactual explainability methods have quietly neglected: minimization. State-of-the-art approaches typically follow a generate-and-minimize pipeline. A generator first produces a valid counterfactual that crosses the model’s decision boundary, then a refinement step trims it down to something closer to the original graph. Generation has been studied extensively; minimization has not. Existing refinement strategies are either crude random edge-swap heuristics or tightly coupled to a specific generator, leaving the field without a formal understanding of how hard trimming a counterfactual actually is.

The authors close that gap by formalizing the task as an optimization problem they call GC-min. Given a black-box machine learning model, an original graph, and a valid graph counterfactual, GC-min asks for the counterfactual with the smallest possible set of edits — edge additions, edge removals, or node attribute changes — that still flips the model’s prediction. The result of their theoretical analysis is stark: GC-min is NP-hard. The proof reduces from Karp’s classic Feedback Arc Set problem in the general directed case, and from the Edge Bipartization problem for undirected graphs. Assuming only that model inference is computable in polynomial time, the hardness holds regardless of the underlying machine learning task or the model architecture. In plain terms, finding the truly minimal counterfactual is computationally intractable in general, which explains why practical systems have settled for heuristic refinement and why a principled approximation algorithm is needed.

That algorithm is Local Bounded Search, or LBS, a model-agnostic heuristic grounded in the classical local search tradition for NP-hard combinatorial problems. LBS takes any valid counterfactual as a seed and explores a bounded neighborhood of graph edits, aiming to reduce the count of edits separating the counterfactual from the original graph while preserving validity — the requirement that the refined graph still triggers a different prediction. Once a valid solution with a given number of edits is found, no solution larger than that bound can improve the objective, so LBS never needs to explore beyond it. The authors prove that this cardinality bound never excludes an optimal solution, since any smaller valid counterfactual can be reached without ever exceeding the current size.

Within each iteration, LBS executes exactly one of four priority-ordered strategies under a first-improvement acceptance policy. The highest-priority move is single-edit removal: deleting one edit at a time and checking whether validity survives. When no single removal works, the edits are likely mutually supportive, each necessary on its own but jointly redundant with others. Here the algorithm’s distinctive overshooting move kicks in, removing multiple edits simultaneously, with the removal size drawn from a truncated exponential distribution biased toward larger deletions. This escape from local minima is what distinguishes LBS from naive greedy pruning. The third strategy replaces one edit with another, preserving cardinality while restructuring the solution to unlock further deletions. The fourth, lowest-priority move adds an edit back as compensatory backtracking when the current size has dipped below a previously recorded bound.

Because the black-box oracle consumes the full attributed graph, each structural candidate must also be paired with a node-attribute modification strategy. LBS offers a sequence of eight, ranging from leaving features untouched, through average and degree-weighted neighborhood smoothing, to Laplacian regularization, feature aggregation from new neighbors, heat-kernel diffusion, and random-walk diffusion. These strategies are tried in a cheapest-to-richest order under a first-accept policy, so the algorithm spends oracle calls frugally. The authors stress that these are optimization operators for finding attribute configurations that preserve validity, not claims of semantically interpretable edits, and that domain constraints such as chemical validity of molecules can be enforced by folding additional checks into the oracle itself.

The paper is also careful to distinguish counterfactuals from adversarial examples, a distinction that has generated debate in the explainable AI literature. Both involve finding small input perturbations that flip a model’s output, but the defining difference lies in the ground-truth label: an adversarial example is by definition misclassified, whereas a counterfactual need not be. LBS optimizes validity and minimality; plausibility, meaning closeness to the real data manifold, is not part of its objective. Instead, the study shows that starting from real, in-distribution seeds — as the DCE generator does — anchors the search to genuine class changes rather than perturbations that merely fool the model, effectively keeping the output on the counterfactual side of the divide.

Empirically, the authors paired LBS with three generators spanning the main paradigms of graph counterfactual explainability — the search-based DCE, the heuristic-based OFS, and the generative RSGG — across nine datasets spanning synthetic motifs, molecular graphs such as BBBP, BZR, and AIDS, protein benchmarks like ENZYMES and PROTEINS, and fMRI-derived brain networks from the ASD dataset. The results are striking. LBS reduces the graph edit distance between the original graph and its counterfactual by up to 98 percent relative to the initial counterfactual, consistently outperforming the random edge-swap baseline obs, the data-driven backward search DBS, and a matched-budget hill-climbing control. On the Synthie benchmark, for instance, graph edit distance fell from 189.71 to 2.17. Even when LBS and obs were given the same oracle-call budget, LBS achieved dramatically lower edit counts, demonstrating that its advantage comes from the search strategy rather than extra model access.

Ablation studies confirm the importance of each design choice. Enabling attribute manipulation significantly improves structural minimality on attributed datasets, trading a modest increase in feature edit distance for large structural gains. Combining removal and swap/addition strategies proves essential: removal-only variants fail on attributed graphs while swap-only variants degrade catastrophically on attribute-free ones. The priority ordering matters too — checking small removals first proves the most robust configuration across both attributed and attribute-free data. On the scalability side, the study introduces DCEM, a medoid-based variant of DCE whose generator-side oracle cost is constant regardless of dataset size; paired with LBS, it achieves minimality comparable to the best variable-cost generator.

The broader implication is a shift in emphasis for the field: once minimization is explicitly optimized in a generator-agnostic way, even a simple valid seed can yield highly minimal, inspectable explanations. The authors point to future work on adaptive strategy selection, comparisons with metaheuristics such as simulated annealing and tabu search, and integration of domain-specific plausibility constraints. For now, the study gives the graph explainability community something it has lacked — a formal understanding of what minimization costs, and a practical algorithm that delivers on it.

Subject of Research: Theory and algorithms for minimizing graph counterfactual explanations in explainable machine learning.

Article Title: On the Minimization of Graph Counterfactual Explanations: Theory and a Local Bounded Search Algorithm

Article References: On the Minimization of Graph Counterfactual Explanations: Theory and a Local Bounded Search Algorithm. (n.d.). https://doi.org/10.1007/s10994-026-07157-0

Image Credits: AI Generated

DOI: 10.1007/s10994-026-07157-0

Keywords: graph counterfactual explanations, explainable AI, machine learning, graph neural networks, NP-hardness, local search, graph edit distance, counterfactual minimization, black-box models, combinatorial optimization, Minimization, Graph