When Features Don't Move Alone: Relational Constraint Satisfaction for Counterfactual Explanations

Counterfactual explanations (CEs) explain model predictions by identifying input changes that alter the predicted outcome. CE quality spans multiple properties, including validity, proximity, confidence, sparsity, and constraints on feature changes. While boundary and immutability constraints have received considerable attention, relational constraints encoding dependencies among features remain largely unaddressed. We introduce relational constraints as a third constraint type and propose MARBLE, a gray-box method that assembles candidates from observed nearest unlike neighbors values, deterministically repairs constraints, and refines them through an $\epsilon$-constrained multi-objective evolutionary search, returning only CEs satisfying all stated constraints and abstaining otherwise. We evaluate MARBLE on four high-stakes real-world use cases: URL phishing detection, credit scoring, ICU survival prediction, and botnet attack detection. On the hardest dataset, MARBLE returns a valid CE satisfying all stated constraints for 91% of queries, compared with at most 4% for five state-of-the-art methods. Across the benchmark, MARBLE outperforms these methods in validity and constraint satisfaction while remaining competitive in confidence, sparsity, and proximity.