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

Abstract Graph counterfactual explainability (GCE) addresses the interpretability limitations of opaque machine learning models on graph-structured data by producing graph counterfactuals (GCs): alternative graphs that remain maximally similar to a given instance while inducing a different model prediction. State-of-the-art GCE methods usually follow a generate-and-minimize pipeline: first, generate a valid counterfactual, then refine it to be closer to the original graph. While generation is well-studied, minimization still lacks a formal definition, complexity analysis, and general-purpose algorithms; existing solutions are either simple random edge-swap heuristics or tightly coupled to specific generators, limiting effectiveness and generality. In this work, we address a key gap in GCE by providing the first principled study of minimizing a given valid graph counterfactual. We formalize the task as an optimization problem and prove it is NP-hard. We then propose a decoupled generate-and-minimize framework and introduce Local Bounded Search (LBS), a model-agnostic heuristic that refines any valid counterfactual via constrained structural and attribute edits to reduce dissimilarity while preserving validity. Across nine synthetic and real-world datasets (molecular, biomedical, social), LBS reduces structural edit distance by up to 98% from the initial counterfactual and consistently outperforms existing refinement heuristics.