Noise-Robust Counterfactual Explanations under the Rashomon Effect via Homotopy Path-Following

Although there has been extensive research on robust counterfactual explanations (RCEs) addressing the Rashomon Effect, when training data contains noisy labels, the Hessian matrix — which characterises the geometry of the ellipsoid — becomes corrupted under label noise for RCE methods based on Rashomon uncertainty sets. This corruption distorts the geometry of the uncertainty set, causing robust optimisation to yield unreliable RCEs. We find that the perturbation $\Delta H$ introduced by noisy labels to the Hessian matrix exhibits a low-rank structure, leading to a deflection of the principal directions of the Rashomon ellipsoid defined by the Hessian; this phenomenon is observable across different noise rates, regardless of whether the label noise is random flipping or systematic flipping. Our theoretical analysis further establishes that this conclusion generalises to model uncertainty sets defined by general quadratic forms. To mitigate the impact of noisy labels on RCE, we propose a path-following strategy based on homotopy: starting from a conservative uncertainty set that is independent of labels, label information is gradually incorporated along a continuously deformed path, with the homotopy parameter controlling the degree of trust placed in the training labels. We prove that the robust CE solution is continuously differentiable along the homotopy path, enabling stable path-following and principled selection of the homotopy parameter. Experimental results on five diverse datasets demonstrate that this new framework produces counterfactual explanations that are both robust and computationally efficient across model uncertainty sets defined by different quadratic forms.