Optimized Instance Alteration for Explaining and Assessing Robustness of Classifiers

# Optimized Instance Alteration for Explaining and Assessing Robustness of Classifiers
Source: [https://arxiv.org/html/2607.06637](https://arxiv.org/html/2607.06637)
Evgenii Kuriabov, David Miller, and Jia LiE\. Kuriabov and J\. Li are with the Department of Statistics, The Pennsylvania State University, University Park, PA 16802, USA\. Emails:eak5582@psu\.edu,jiali@psu\.eduD\. Miller is with the Department of Electrical Engineering, The Pennsylvania State University, University Park, PA 16802, USA\. Email:djm25@psu\.eduThe research of E\. Kuriabov and J\. Li has been supported by the NSF under Award No\. 2205004\.Correspondence: Evgenii Kuriabov\.

###### Abstract

In this work, we propose a unified approach for diagnosing misclassification and assessing the robustness of black\-box classifiers\. Central to our method is an optimization framework that modifies an instance so that the classifier predicts a specified target label, while ensuring that the modification remains easily explainable\. The objective function contains two components: an explainability\-awareL0L\_\{0\}\(XA\-L0L\_\{0\}\) penalty that promotes sparse and interpretable modifications, and a classifier loss objective that steers the perturbed instance toward the desired output\. This integrated optimization formulation is used both to identify the underlying causes of misclassification and to evaluate robustness by determining how an instance can change within a tolerance region before being reassigned to another class\. To quantify robustness, we introduce the Tolerance Region Confusion Matrix \(TOR\-Confusion Matrix\), which measures a classifier’s susceptibility by modeling the class\-to\-class transition probabilities induced by tolerance\-bounded perturbations\. We validate the proposed method on both image and tabular datasets, demonstrating its ability to jointly deliver interpretability and robustness assessment\.

## IIntroduction

Interpretable machine learning has become essential for understanding and validating model decisions in domains such as healthcare, finance, and autonomous systems\. Despite impressive predictive performance, modern deep models often act as opaque black boxes, offering little insight into why a specific prediction was made or how a misclassification could be corrected\. This opacity limits trust, accountability, and deployment in high\-stakes environments where the reasoning behind predictions must be transparent\. A principled interpretability framework should therefore not only explain a model’s decision but also suggest how the decision could be altered through minimal, meaningful changes to the input\. For example, in credit or insurance approval, a counterfactual explanation can indicate that only a modest increase in credit score or reported income would flip a rejection to an approval, providing actionable feedback to an applicant\. As another example, in scientific or clinical settings where features are measured with finite precision, an explanation may reveal that the predicted label changes under a perturbation smaller than the typical measurement resolution of a key feature, suggesting that this feature should be measured more precisely in practice or that the decision is unstable to measurement noise\.

Counterfactual explanations offer a natural and intuitive mechanism for achieving this goal\. Given a misclassified instance, the objective is to identify the smallest modification that would change the model’s output to the desired label\. Likewise, given a correctly classified instance, the objective is to identify how close the instance is to being misclassified\. Existing approaches typically encourage sparsity usingL0L\_\{0\}\-style penalties or their relaxations\[[20](https://arxiv.org/html/2607.06637#bib.bib22),[4](https://arxiv.org/html/2607.06637#bib.bib36),[3](https://arxiv.org/html/2607.06637#bib.bib23)\], seeking to minimize the number of altered features\. However, sparsity alone does not guarantee interpretability\. AnL0L\_\{0\}penalty constrains the number of modified features, but not the nature or coherence of those changes\. In image domains, enforcing sparsity may result in isolated pixels whose alteration creates implausible visual artifacts\. In tabular settings, sparsity that ignores inherent feature relationships produces edits that are numerically small but conceptually nonsensical\. Thus, whileL0L\_\{0\}promotes minimality, it falls short of ensuring that the resulting counterfactuals are actually interpretable, a gap we directly address in our formulation\. Sampling\-based inverse classification methods, such as Growing Spheres\[[10](https://arxiv.org/html/2607.06637#bib.bib45)\], further struggle with scalability and often neglect dependencies among variables, resulting in disjoint or unstable counterfactuals\.

Counterfactual generation is also closely related to methods for constructing adversarial examples and test\-time evasion attacks, which similarly search for input modifications that induce a change in a model’s prediction\[[6](https://arxiv.org/html/2607.06637#bib.bib40),[11](https://arxiv.org/html/2607.06637#bib.bib41),[2](https://arxiv.org/html/2607.06637#bib.bib42)\]\. The key distinction lies in intent and structure: adversarial methods typically aim to produce imperceptible or noise\-like perturbations that change the decision while remaining difficult to detect, whereas counterfactual explanations seek coherent, semantically meaningful modifications that reveal how and why a decision could change\. This contrast motivates our emphasis on structured, interpretable perturbations—changes that are aligned with domain structure rather than optimized solely for minimal norm or visual imperceptibility\.

To address these limitations, we propose a unified optimization framework that generates*interpretable corrections*by jointly enforcing correctness, parsimony, and semantic coherence\. The approach integrates three complementary components: a classification term that enforces the desired label, a proximity regularizer that maintains realism, and a novel*Explainability\-AwareL0L\_\{0\}\(XA\-L0L\_\{0\}\)*penalty that promotes structured sparsity by coupling related features\. For tabular data, this coupling captures meaningful feature dependencies, such as correlations or learned communities in a feature graph, while for image data, an edge\-aware spatial regularizer favors clustered modifications near object boundaries, where changes are most visually salient, avoiding the scattered or visually implausible pixel changes produced by standard sparsity penalties\. Together, these components yield compact and semantically consistent corrections that respect both statistical relationships and perceptual structure, providing interpretable pathways for refining model predictions\.

Beyond generating individual corrections, we introduce the*Tolerance\-Region Confusion Matrix \(TOR\-CM\)*to quantify model robustness under interpretable perturbations\. Unlike conventional adversarial or certified robustness measures\[[6](https://arxiv.org/html/2607.06637#bib.bib40),[11](https://arxiv.org/html/2607.06637#bib.bib41),[2](https://arxiv.org/html/2607.06637#bib.bib42)\], which evaluate sensitivity to infinitesimal or norm\-bounded noise, TOR\-CM characterizes how predictions change within bounded, semantically meaningful tolerance regions defined by the XA\-L0L\_\{0\}geometry\. This perspective links interpretability and robustness within a single optimization\-based framework, enabling a unified analysis of both model behavior and its stability under human\-understandable modifications\.

The proposed framework thus unifies counterfactual interpretability and robustness assessment through a structured optimization objective\. Extensive experiments on image and tabular datasets show that XA\-L0L\_\{0\}generates coherent, domain\-aligned corrections while providing faithful, interpretable explanations of the classifier’s decisions\. Moreover, the TOR\-CM analysis reveals that models differ not only in accuracy but also in their intrinsic stability under interpretable perturbations, providing a more complete characterization of model reliability in real\-world settings\.

## IIPreliminaries and Related Work

Counterfactual explanations have emerged as one of the most intuitive forms of post\-hoc interpretability, aiming to explain or correct a model’s decision by identifying minimal input changes that would alter its predicted class\. Given an instance𝐱\(o\)∈ℝd\\mathbf\{x\}^\{\(o\)\}\\in\\mathbb\{R\}^\{d\}and a trained classifierf​\(𝐱\)f\(\\mathbf\{x\}\), the objective is to find a perturbed point𝐱∗\\mathbf\{x\}^\{\*\}such thatf​\(𝐱∗\)≠f​\(𝐱\(o\)\)f\(\\mathbf\{x\}^\{\*\}\)\\neq f\(\\mathbf\{x\}^\{\(o\)\}\)while keeping𝐱∗\\mathbf\{x\}^\{\*\}as similar and plausible as possible\. This formulation offers a human\-aligned explanation by revealing “what needs to change” to achieve a desired outcome and, correspondingly, “which features contribute to the misclassification\.” Likewise, it can identify how close a correctly classified instance is to being misclassified, and which feature changes would result in such misclassification\.

Recent surveys\[[17](https://arxiv.org/html/2607.06637#bib.bib2),[8](https://arxiv.org/html/2607.06637#bib.bib43),[16](https://arxiv.org/html/2607.06637#bib.bib44)\]highlight that counterfactual frameworks differ not only in their technical formulation but also in their underlying goals\. Some prioritizeclassification fidelity, ensuring that the modified instance reliably flips the prediction\[[20](https://arxiv.org/html/2607.06637#bib.bib22),[4](https://arxiv.org/html/2607.06637#bib.bib36)\]; others emphasizeproximity and feasibility, constraining changes to remain close to the original input\. Sparsity\-based methods focus onparsimony, seeking to alter as few features as possible\[[3](https://arxiv.org/html/2607.06637#bib.bib23),[12](https://arxiv.org/html/2607.06637#bib.bib5)\], while generative and manifold\-based approaches\[[1](https://arxiv.org/html/2607.06637#bib.bib48),[7](https://arxiv.org/html/2607.06637#bib.bib49),[15](https://arxiv.org/html/2607.06637#bib.bib50)\]aim forplausibility, producing counterfactuals that remain within the natural data distribution\. More recent causal formulations\[[8](https://arxiv.org/html/2607.06637#bib.bib43)\]extend these objectives to ensure that counterfactuals correspond to meaningful, achievable interventions\. These diverse objectives—correctness, proximity, sparsity, plausibility, and causality—define complementary yet often competing aspects of interpretability\.

Despite their conceptual richness, most counterfactual formulations can be expressed within a common optimization framework:

𝐱∗=arg⁡min𝐱⁡\[ℒcls​\(f​\(𝐱\),y∗\)\+λ​d​\(𝐱,𝐱\(o\)\)\+Ω​\(𝐱,𝐱\(o\)\)\],\\mathbf\{x\}^\{\*\}=\\arg\\min\_\{\\mathbf\{x\}\}\\Big\[\\mathcal\{L\}\_\{\\text\{cls\}\}\(f\(\\mathbf\{x\}\),y^\{\*\}\)\+\\lambda\\,d\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)\+\\Omega\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)\\Big\],whereℒcls\\mathcal\{L\}\_\{\\text\{cls\}\}enforces classification consistency,d​\(⋅,⋅\)d\(\\cdot,\\cdot\)penalizes deviation from the original input, andΩ​\(𝐱,𝐱\(o\)\)\\Omega\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)regularizes the structure of the modification\. In classical works such as Wachteret al\.\[[20](https://arxiv.org/html/2607.06637#bib.bib22)\]and Dhurandharet al\.\[[4](https://arxiv.org/html/2607.06637#bib.bib36)\], the regularizerΩ\\Omegais instantiated as a simple norm, typicallyL1L\_\{1\}orL2L\_\{2\}\. Dandlet al\.\[[3](https://arxiv.org/html/2607.06637#bib.bib23)\]later extended this paradigm to a multi\-objective formulation that jointly optimizes fidelity, proximity, and sparsity, yielding a Pareto set of counterfactuals with varying trade\-offs\. Although effective, such methods generally assume feature independence and therefore tend to produce counterfactuals that modify isolated coordinates, ignoring correlations or spatial relations among features\. This independence assumption often leads to fragmented or implausible explanations—small in magnitude but not necessarily interpretable to humans\.

A parallel line of work in statistical learning has demonstrated that interpretability often improves when sparsity is replaced withstructured sparsity\. Regularizers such as the group lasso\[[22](https://arxiv.org/html/2607.06637#bib.bib26)\], fused lasso\[[14](https://arxiv.org/html/2607.06637#bib.bib37)\], and graph\-guided penalties\[[9](https://arxiv.org/html/2607.06637#bib.bib38)\]encourage coordinated changes among related variables, yielding solutions that align with meaningful feature groups or spatial neighborhoods\. These approaches reflect an important principle: real\-world data exhibit dependencies, in particular, features in tabular domains are correlated, and pixels in images form spatially coherent regions\.

However, despite the maturity of structured\-sparsity methods in predictive modeling, they have not been adequately exploited in counterfactual explanation frameworks\. Most counterfactual methods still treat features as independent dimensions, optimizing forL0L\_\{0\}\-style sparsity without regard for how meaningful or coherent the resulting changes appear\. Moreover, existing structured\-sparsity penalties were not designed with counterfactual interpretability in mind\. They promote grouped activation patterns for predictive accuracy, but they do not incorporate the semantic or domain\-specific considerations required for generating human\-interpretable instance\-level modifications\. Consequently, they cannot directly ensure that counterfactual changes are realistic and interpretable\.

Beyond interpretability, robustness is a core requirement for reliable prediction systems\. Classical robustness research, most notably adversarial defenses\[[6](https://arxiv.org/html/2607.06637#bib.bib40),[11](https://arxiv.org/html/2607.06637#bib.bib41)\]and certified smoothing\[[2](https://arxiv.org/html/2607.06637#bib.bib42)\], focuses on the model’s sensitivity to small, unstructured perturbations such asℓp\\ell\_\{p\}\-bounded noise or Gaussian randomized smoothing\. These approaches are designed to capture worst\-case or distributional stability, but the perturbations they consider are typically imperceptible, lack semantic meaning, and do not reflect the kinds of structured changes humans naturally interpret as meaningful modifications to the input\. Moreover, they evaluate robustness only in terms of preserving the predicted label, without characterizing how predictions shift among classes or whether alternative outputs become reachable under non\-adversarial but interpretable changes\. Consequently, robustness with respect to human\-understandable, structured perturbations, and the corresponding class\-to\-class transition behavior, remains largely unaddressed in existing robustness frameworks\.

In summary, prior work has established strong foundations for counterfactual reasoning but typically optimizes for sparsity and correctness in isolation, overlooking the structural and semantic coherence of feature changes\. Likewise, robustness analysis has focused on worst\-case sensitivity rather than interpretable variability\. Our approach aims at bridging these perspectives via an optimization framework that respects both the internal structure of the data and the external behavior of the model\.

## IIIMethod

We propose a unified optimization framework for identifyingminimal, interpretable, and structured modificationsthat correct a misclassification while remaining close to the original instance\. The framework jointly enforces correctness, parsimony, and realism through three complementary loss terms\.

### III\-AProblem Formulation

Let𝐱∈ℝd\\mathbf\{x\}\\\!\\in\\\!\\mathbb\{R\}^\{d\},𝐱=\(x1,…,xd\)t\\mathbf\{x\}=\(x\_\{1\},\\dots,x\_\{d\}\)^\{t\}denote an input instance, and letf:ℝd→\{1,…,K\}f:\\mathbb\{R\}^\{d\}\\\!\\rightarrow\\\!\\\{1,\\dots,K\\\}, whereKKis the number of classes, denote a trained classifier that estimates posterior probabilitiespj​\(𝐱\)=P​\(y=j∣𝐱\)p\_\{j\}\(\\mathbf\{x\}\)=P\(y\\\!=\\\!j\\mid\\mathbf\{x\}\)\. Given a misclassified sample𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}with true labely∗y^\{\*\}, we aim to find a corrected input𝐱∗\\mathbf\{x\}^\{\*\}satisfying

𝐱∗=arg⁡min𝐱⁡ℒcomp​\(𝐱,𝐱\(o\),y∗\),\\mathbf\{x\}^\{\*\}=\\arg\\min\_\{\\mathbf\{x\}\}\\mathcal\{L\}\_\{\\mathrm\{comp\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\},y^\{\*\}\)\\;,\(1\)where the*composite penalty/loss*ℒcomp\\mathcal\{L\}\_\{\\mathrm\{comp\}\}is defined as

ℒcomp​\(𝐱,𝐱\(o\),y∗\)\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{comp\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\},y^\{\*\}\)=\\displaystyle=ℒcls​\(𝐱,y∗\)\+λ1​ℒXA​\-​L0​\(𝐱,𝐱\(o\)\)\+λ2​ℒprox​\(𝐱,𝐱\(o\)\)\.\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{cls\}\}\(\\mathbf\{x\},y^\{\*\}\)\+\\lambda\_\{1\}\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)\+\\lambda\_\{2\}\\mathcal\{L\}\_\{\\mathrm\{prox\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)\\,\.The three components of the composite loss are given by

ℒcls​\(𝐱,y∗\)\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{cls\}\}\(\\mathbf\{x\},y^\{\*\}\)=max⁡\(0,maxj≠y∗⁡\(pj​\(𝐱\)−py∗​\(𝐱\)\)\),\\displaystyle=\\max\\\!\\big\(0,\\,\\max\_\{j\\neq y^\{\*\}\}\(p\_\{j\}\(\\mathbf\{x\}\)\-p\_\{y^\{\*\}\}\(\\mathbf\{x\}\)\)\\big\)\\,,\(3\)ℒprox​\(𝐱,𝐱\(o\)\)\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{prox\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)=‖𝐱−𝐱\(o\)‖22,\\displaystyle=\\\|\\mathbf\{x\}\-\\mathbf\{x\}^\{\(o\)\}\\\|\_\{2\}^\{2\}\\,,\(4\)ℒXA​\-​L0​\(𝐱,𝐱\(o\)\)\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\):structured explainability term\.\\displaystyle:\\text\{structured explainability term\}\\,\.\(5\)
Here,ℒcls\\mathcal\{L\}\_\{\\mathrm\{cls\}\}enforces the correct classification label\. If we additionally require that the posterior of the true class exceed that of all other classes by a marginθ\\theta, its definition becomes

ℒcls​\(𝐱,y∗\)=max⁡\(0,maxj≠y∗⁡\(pj​\(𝐱\)−py∗​\(𝐱\)\)\+θ\),\\mathcal\{L\}\_\{\\mathrm\{cls\}\}\(\\mathbf\{x\},y^\{\*\}\)=\\max\\\!\\big\(0,\\,\\max\_\{j\\neq y^\{\*\}\}\(p\_\{j\}\(\\mathbf\{x\}\)\-p\_\{y^\{\*\}\}\(\\mathbf\{x\}\)\)\+\\theta\\big\),where the marginθ\>0\\theta\>0ensures that the corrected counterfactual lies safely within the true\-class region, away from the decision boundary\. The lossℒprox\\mathcal\{L\}\_\{\\mathrm\{prox\}\}constrains the magnitude of deviation from the original sample𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}, whereasℒXA​\-​L0\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}encourages coherent and interpretable sparsity, as elaborated below\.

### III\-BExplainability\-AwareL0L\_\{0\}Loss \(XA\-L0L\_\{0\}\)

Although theL0L\_\{0\}norm is commonly used to enforce sparsity, it ignores dependencies among features and is not differentiable, making it difficult to optimize\. To capture domain\-specific structure, we introduce a differentiable penalty that promotes structured activation, encouraging related features to change jointly rather than in isolation\.

Define a soft activation function

σ​\(x\)=21\+exp⁡\(−ξ​x\)−1,ξ\>0\.\\sigma\(x\)=\\frac\{2\}\{1\+\\exp\(\-\\xi x\)\}\-1,\\qquad\\xi\>0\.In our experiments, we setξ=10\\xi=10\. Then define

ℒXA​\-​L0​\(𝐱,𝐱\(o\)\)\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)\(6\)=\\displaystyle=∑\(i,j\)∈ℐWi,j​σ​\(\|xi−xi\(o\)\|\)​σ​\(\|xj−xj\(o\)\|\),\\displaystyle\\sum\_\{\(i,j\)\\in\\mathcal\{I\}\}W\_\{i,j\}\\,\\sigma\(\|x\_\{i\}\-x\_\{i\}^\{\(o\)\}\|\)\\,\\sigma\(\|x\_\{j\}\-x\_\{j\}^\{\(o\)\}\|\)\\,,whereℐ\\mathcal\{I\}denotes a set of index pairs\(i,j\)\(i,j\)withi≠ji\\neq j,i,j=1,…,di,j=1,\.\.\.,d, andWi,j≥0W\_\{i,j\}\\geq 0specifies the degree of incoherence between featuresiiandjj, \(i\.e\., a penalty weight that discourages their joint activation; smallerWi,jW\_\{i,j\}indicates stronger affinity and makes it less costly for the two features to change together\)\. This construction yields a differentiable surrogate that preserves the interpretive sparsity characteristics of anL0L\_\{0\}penalty while enabling gradient\-based optimization\. We also introduce several candidate formulations forWi,jW\_\{i,j\}tailored to both tabular and image data\.

#### \(a\) Tabular Data: Correlation and Network\-Based Grouping

For tabular data, interpretability improves when correlated or semantically related features vary together\. We first introduce a simple correlation\-based incoherence measure:

Wi,j=1−\|ρi,j\|max\(i′,j′\)∈ℐ⁡\|ρi′,j′\|,W\_\{i,j\}=1\-\\frac\{\|\\rho\_\{i,j\}\|\}\{\\max\_\{\(i^\{\\prime\},j^\{\\prime\}\)\\in\\mathcal\{I\}\}\|\\rho\_\{i^\{\\prime\},j^\{\\prime\}\}\|\},whereρi,j\\rho\_\{i,j\}denotes the Pearson correlation between featuresiiandjj\. This construction assigns larger penalties to weakly correlated pairs and smaller penalties to strongly correlated pairs \(e\.g\., income and credit limit, or systolic–diastolic pressure\) to co\-vary\. When domain knowledge is available,Wi,jW\_\{i,j\}may also encode expert\-specified relationships or hierarchical groupings, offering a flexible mechanism for representing application\-specific dependencies\.

To capture nonlinear or higher\-order relationships among features, we construct a feature networkG=\(V,E,A\)G=\(V,E,A\), where each feature corresponds to a node and edge weights encode pairwise affinities\. An edge weight is defined asAi​j=g​\(xi,xj\)∈\[0,1\]\\displaystyle A\_\{ij\}=g\(x\_\{i\},x\_\{j\}\)\\in\[0,1\], whereg​\(⋅,⋅\)g\(\\cdot,\\cdot\)may represent correlation, mutual information, geometric proximity, or any other symmetric dependence measure\.

We then apply community detection \(e\.g\., spectral clustering\[[19](https://arxiv.org/html/2607.06637#bib.bib52)\]or modularity maximization\[[13](https://arxiv.org/html/2607.06637#bib.bib39)\]\) to partition the nodes intoKcK\_\{c\}groups, and letci∈\{1,…,Kc\}c\_\{i\}\\in\\\{1,\\dots,K\_\{c\}\\\}denote the community label of featureii\. Based on this partition, we define a pairwise incoherence penaltyWWthat controls how strongly pairs of features are encouraged to activate together:

Wi,j=\{ωin,if​ci=cj,ωout,if​ci≠cj,0≤ωin<ωout≤1\.W\_\{i,j\}=\\begin\{cases\}\\omega\_\{\\mathrm\{in\}\},&\\text\{if \}c\_\{i\}=c\_\{j\},\\\\\[4\.0pt\] \\omega\_\{\\mathrm\{out\}\},&\\text\{if \}c\_\{i\}\\neq c\_\{j\},\\end\{cases\}\\qquad 0\\leq\\omega\_\{\\mathrm\{in\}\}<\\omega\_\{\\mathrm\{out\}\}\\leq 1\.Within\-community pairs receive the lower penaltyωin\\omega\_\{\\mathrm\{in\}\}, encouraging coherent changes among related features, whereas cross\-community pairs incur the higher penaltyωout\\omega\_\{\\mathrm\{out\}\}, discouraging dispersed or semantically unrelated edits\.

As a continuous alternative that does not rely on discrete communities, the incoherence measure may be defined directly from the affinity structure:

Wi,j=1−η​Ai​j,η∈\[0,1\],W\_\{i,j\}=1\-\\eta A\_\{ij\},\\qquad\\eta\\in\[0,1\],so that strongly related features \(largeAi​jA\_\{ij\}\) receive a smaller incoherence penalty\. This formulation unifies the similarity functiong​\(⋅,⋅\)g\(\\cdot,\\cdot\), the graphGG, and the coupling weightsWi,jW\_\{i,j\}within a single coherent framework, ensuring that XA\-L0L\_\{0\}respects the underlying feature\-network geometry\.

#### \(b\) Image Data: Distance\- and Boundary\-Based Coherence

For images, we consider two schemes designed to encourage more interpretable modifications\. The first favors changes in spatially proximate pixels over dispersed alterations across the image\. The second emphasizes changes on or near edges, reflecting the intuition that edges attract greater perceptual attention and that modifying them is more likely to alter object shapes and thus influence classification outcomes\. Correspondingly, we propose two spatial coupling strategies for defining XA\-L0L\_\{0\}: a pixel\-distance\-based scheme and an edge\-focused scheme\.

##### Distance\-Based Spatial Coupling

To promote spatially localized and contiguous corrections, we couple pixels according to their spatial distance\. Let the 2D coordinate of pixelii,i=1,…,Ni=1,\\dots,N\(withNNthe total number of pixels\), be denoted by𝐮i=\(ui,1,ui,2\)\\mathbf\{u\}\_\{i\}=\(u\_\{i,1\},u\_\{i,2\}\), whereui,1u\_\{i,1\}andui,2u\_\{i,2\}represent the horizontal and vertical coordinates, respectively\. We assign each pixel pair\(i,j\)\(i,j\)the weight

Wi,j=1−exp⁡\(−‖𝐮i−𝐮j‖222​ζ2\),W\_\{i,j\}=1\-\\exp\\Bigl\(\-\\tfrac\{\\\|\\mathbf\{u\}\_\{i\}\-\\mathbf\{u\}\_\{j\}\\\|\_\{2\}^\{2\}\}\{2\\zeta^\{2\}\}\\Bigr\),so that nearby pixels \(small spatial separation\) receive*smaller*weights and distant pixels receive*larger*ones\. The hyperparameterζ\\zetais set to 2\. Under the definition ofℒXA​\-​L0\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}in Eq\. \([6](https://arxiv.org/html/2607.06637#S3.E6)\), this design makes it inexpensive to activate neighboring pixels jointly and costly to activate distant pixels, thereby encouraging compact, spatially coherent perturbation regions rather than isolated pixel\-level changes\.

##### Edge\-Focused Coherence

For image data, a counterfactual correction should identify*where*and*how*the model’s perception must change in order to alter its prediction\. Unconstrained pixel\-wise optimization often produces scattered, noise\-like perturbations that lack semantic structure\. In contrast, human perception is strongly guided by*edges*and*object boundaries*, where salient visual changes occur—such as shifts in shape, texture transitions, or part delineations\. Encouraging modifications to concentrate near these boundaries therefore leads to counterfactuals that are more interpretable and visually coherent\.

To implement this principle, we introduce an*edge\-aware weighting*into the XA\-L0L\_\{0\}penalty\. LetMi∈\[0,1\]M\_\{i\}\\in\[0,1\]denote the probability that pixelii,i=1,…,Ni=1,\\dots,N, lies on an edge, obtained from the original image𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}using an edge detector, in particular, Holistically\- Nested Edge Detection \(HED\)\[[21](https://arxiv.org/html/2607.06637#bib.bib46)\]in our experiments\. IfMi=0M\_\{i\}=0, pixeliiis treated as a non\-edge pixel; otherwise, it is regarded as lying on an edge\. LetDM​\(i\)D\_\{M\}\(i\)denote the Euclidean distance from pixeliito the nearest detected edge\. Pixels located on or near edges should be favored for modification, whereas pixels far inside homogeneous regions should be discouraged\.

We encode this preference using the edge\-aware function

αedge​\(i\)=αmin\+\(1−αmin\)​exp⁡\(−DM​\(i\)22​τ2\),\\alpha\_\{\\mathrm\{edge\}\}\(i\)=\\alpha\_\{\\min\}\+\(1\-\\alpha\_\{\\min\}\)\\exp\\\!\\Biggl\(\-\\frac\{D\_\{M\}\(i\)^\{2\}\}\{2\\tau^\{2\}\}\\Biggr\),whereαmin∈\(0,1\)\\alpha\_\{\\min\}\\in\(0,1\)adjusts the minimum value forαedge​\(i\)\\alpha\_\{\\mathrm\{edge\}\}\(i\), which decreases monotonically withDM​\(i\)D\_\{M\}\(i\)\. Hyperparameterτ\\taudetermines how fastαedge​\(i\)\\alpha\_\{\\mathrm\{edge\}\}\(i\)reduces whenDM​\(i\)D\_\{M\}\(i\)increases\.

We also take into account the probability of pixeliilying on an edge and further define

α~edge​\(i\)=\(1−κ\+κ​Mi\)​αedge​\(i\),\\tilde\{\\alpha\}\_\{\\mathrm\{edge\}\}\(i\)=\\bigl\(1\-\\kappa\+\\kappa\\,M\_\{i\}\\bigr\)\\,\\alpha\_\{\\mathrm\{edge\}\}\(i\),where0<κ<10<\\kappa<1controls the influence ofMiM\_\{i\}\.

Since the XA\-L0L\_\{0\}penalty operates on per\-pixel activations, we convert this preference into a penalty weight:

Wied=ε\+\(1−ε\)​\(1−α~edge​\(i\)\),W^\{\\mathrm\{ed\}\}\_\{i\}=\\varepsilon\+\(1\-\\varepsilon\)\\,\\bigl\(1\-\\tilde\{\\alpha\}\_\{\\mathrm\{edge\}\}\(i\)\\bigr\),with a small constantε\>0\\varepsilon\>0ensuring nonzero gradients\.

The resulting edge\-aware penalty is

ℒXA​\-​L0ed​\(𝐱,𝐱\(o\)\)=∑i=1NWied​σ​\(\|xi−xi\(o\)\|\),\\mathcal\{L\}^\{\\mathrm\{ed\}\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)=\\sum\_\{i=1\}^\{N\}W^\{\\mathrm\{ed\}\}\_\{i\}\\,\\sigma\(\|x\_\{i\}\-x\_\{i\}^\{\(o\)\}\|\)\\,,which encourages smooth, spatially coherent adjustments along boundaries rather than diffuse, noise\-like pixel\-level perturbations\.

### III\-COptimization and Thresholding

The composite lossℒcomp​\(𝐱,𝐱\(o\),y∗\)\\mathcal\{L\}\_\{\\mathrm\{comp\}\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\},y^\{\*\}\)is minimized with respect to𝐱\\mathbf\{x\}, while the classifierf​\(⋅\)f\(\\cdot\)remains fixed\. The optimization procedure consists of two steps:

1. 1\.Initialize𝐱\\mathbf\{x\}with the original instance𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}, and apply ADAM to solve optimization problem \([1](https://arxiv.org/html/2607.06637#S3.E1)\)\. Denote the resulting counterfactual sample by𝐱∗\\mathbf\{x\}^\{\*\}\.
2. 2\.Apply hard thresholding \(zero\-clipping\) to set near\-zero changes to zero, thereby removing residual numerical artifacts from the optimization\. In particular, supposettis the threshold and apply thresholding individually to the value at each pixelxi∗x^\{\*\}\_\{i\}: x^i∗=\{xi∗,\|xi∗−xi\(o\)\|\>t,xi\(o\),otherwise\.\\hat\{x\}^\{\*\}\_\{i\}=\\begin\{cases\}x^\{\*\}\_\{i\},&\|x^\{\*\}\_\{i\}\-x^\{\(o\)\}\_\{i\}\|\>t,\\\\ x^\{\(o\)\}\_\{i\},&\\text\{otherwise\}\\,\.\\end\{cases\}For tabular data, since the inputs are standardized, we set the threshold tot=0\.05t=0\.05\. For image data with pixel values in the range\[0,255\]\[0,255\], we selectt∈\[1,10\]t\\in\[1,10\]dynamically\. This choice is motivated by the fact that a modification smaller than 10 intensity levels \(under the standard one\-byte\-per\-channel representation\) is typically imperceptible to the human eye\. Fort=1,2,…,10t=1,2,\\dots,10, we apply each threshold successively and validate the resulting𝐱^∗\\hat\{\\mathbf\{x\}\}^\{\*\}to ensure that the corrected sample still yields the desired classification label\. We then setttto the largest value that preserves the correct label\. For image datasets in which pixel values are normalized to\[0,1\]\[0,1\], the thresholds are adjusted tot=j/255t=j/255,j=1,…,10j=1,\\dots,10\.

The resulting𝐱^∗\\hat\{\\mathbf\{x\}\}^\{\*\}constitutes aminimal sufficient correction, namely the smallest set of changes \(after zero\-clipping\) required to flip the classification outcome to the true class\. Its binary maskZi=I​\(\|x^i∗−xi\(o\)\|\>0\)Z\_\{i\}=I\\\!\\left\(\|\\hat\{x\}^\{\*\}\_\{i\}\-x^\{\(o\)\}\_\{i\}\|\>0\\right\), whereI​\(⋅\)I\(\\cdot\)is the indicator function that equals 1 when the argument is true, provides key information for explaining the misclassification of the original sample\.

### III\-DQuantifying Structural Coherence

To assess the interpretability of tabular counterfactual edits, we evaluate how well the modified features form a compact and internally coherent group within the feature–affinity network\. Let𝒮=\{i:x^i∗≠xi\(o\),1≤i≤d\}\\mathcal\{S\}=\\\{\\,i:\\hat\{x\}^\{\*\}\_\{i\}\\neq x^\{\(o\)\}\_\{i\},\\;1\\leq i\\leq d\\,\\\}denote the set of changed features \(withddthe input dimension\), and letW∈ℝd×dW\\in\\mathbb\{R\}^\{d\\times d\}be the pairwise incoherence penalty matrix used in the XA\-L0L\_\{0\}regularizer, where smallerWi,jW\_\{i,j\}indicates stronger feature affinity and largerWi,jW\_\{i,j\}indicates weaker relation between featuresiiandjj\(andWi,iW\_\{i,i\}takes its minimum value\)\.

We define the*structural incoherence score*:

ϕ​\(𝒮\)=1d​\|𝒮\|​∑i∈𝒮∑j∈𝒮exp⁡\(ψ​Wi,j\),\\phi\(\\mathcal\{S\}\)=\\frac\{1\}\{d\\,\|\\mathcal\{S\}\|\}\\sum\_\{i\\in\\mathcal\{S\}\}\\sum\_\{j\\in\\mathcal\{S\}\}\\exp\\bigl\(\\psi\\,W\_\{i,j\}\\bigr\),\(7\)whereψ\>0\\psi\>0controls the sensitivity to pairwise affinity\.

SinceWi,jW\_\{i,j\}is small for closely related features, the termexp⁡\(ψ​Wi,j\)\\exp\(\\psi W\_\{i,j\}\)becomes small for coherent pairs and larger for weakly related or independent pairs\. Consequently,ϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)remains small when𝒮\\mathcal\{S\}forms a compact cluster of mutually similar features and increases when the modified features are weakly related\. Normalization byd​\|𝒮\|d\|\\mathcal\{S\}\|ensures comparability across datasets and prevents systematic favoring of counterfactuals that modify many features\. Low values ofϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)therefore indicate that the counterfactual corresponds to a compact, semantically meaningful edit aligned with the underlying structural dependencies of the dataset\.

### III\-ERobustness via Tolerance\-Region Confusion Matrix

To complement counterfactual explanations with a quantitative assessment of model stability, we evaluate how predictions behave under*interpretable*perturbations rather than adversarial or norm\-bounded noise\. The key idea is to use the same penalty that governs counterfactual modifications, whether based on proximity, structured sparsity, or any domain\-specific interpretability cost, to define a tolerance region around each instance\. Within this region, we examine which classes become reachable and summarize the resulting transitions in a matrix\-level representation\.

The*Tolerance\-Region Confusion Matrix \(TOR\-CM\)*formalizes this idea\. For each original input𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}, we define a tolerance region containing all inputs that differ from𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}by at mostτ\\tauwith respect to a chosen loss function\. TOR\-CM summarizes, for each true classii, the empirical transition probabilities to predicted classesjjinduced by tolerance\-bounded perturbations\. This yields a class\-by\-class characterization of prediction stability under structured, interpretable perturbations, rather than arbitrary norm\-bounded noise\.

For each sample𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}, letℒ​\(𝐱,𝐱\(o\)\)\\mathcal\{L\}\(\\mathbf\{x\},\\mathbf\{x\}^\{\(o\)\}\)denote a general loss between𝐱\\mathbf\{x\}and𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}\. The*tolerance region*is defined as:

𝒯τ​\(𝐱\(o\)\)=\{𝐱′:ℒ​\(𝐱′,𝐱\(o\)\)≤τ\},\\mathcal\{T\}\_\{\\tau\}\(\\mathbf\{x\}^\{\(o\)\}\)=\\big\\\{\\mathbf\{x\}^\{\\prime\}:\\mathcal\{L\}\(\\mathbf\{x\}^\{\\prime\},\\mathbf\{x\}^\{\(o\)\}\)\\leq\\tau\\big\\\},\(8\)whereℒ​\(⋅,⋅\)\\mathcal\{L\}\(\\cdot,\\cdot\)may take various forms—for example‖𝐱′−𝐱\(o\)‖22\\\|\\mathbf\{x\}^\{\\prime\}\-\\mathbf\{x\}^\{\(o\)\}\\\|\_\{2\}^\{2\}or, in our setting, the combined lossℒXA​\-​L0\+ℒprox\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\+\\mathcal\{L\}\_\{\\mathrm\{prox\}\}\.

A*reachable class set*at𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}is defined as

ℛ​\(𝐱\(o\)\)=\{j:∃𝐱′∈𝒯τ​\(𝐱\(o\)\),f​\(𝐱′\)=j\}\.\\mathcal\{R\}\(\\mathbf\{x\}^\{\(o\)\}\)=\\big\\\{j:\\exists\\,\\mathbf\{x\}^\{\\prime\}\\\!\\in\\\!\\mathcal\{T\}\_\{\\tau\}\(\\mathbf\{x\}^\{\(o\)\}\),f\(\\mathbf\{x\}^\{\\prime\}\)=j\\big\\\}\.Suppose the dataset is partitioned into𝒟i\\mathcal\{D\}\_\{i\},i=1,…,Ki=1,\\dots,K, where𝒟i\\mathcal\{D\}\_\{i\}contains all samples with true class labelii\. The TOR\-CMC=\(Ci,j\)i,j=1,…,KC=\(C\_\{i,j\}\)\_\{i,j=1,\\dots,K\}is then defined by

Ci,j=∑𝐱\(o\)∈𝒟iI​\(j∈ℛ​\(𝐱\(o\)\)\),i,j=1,…,K\.C\_\{i,j\}=\\\!\\\!\\sum\_\{\\mathbf\{x\}^\{\(o\)\}\\in\\mathcal\{D\}\_\{i\}\}I\(j\\in\\mathcal\{R\}\(\\mathbf\{x\}^\{\(o\)\}\)\)\\,,\\;\\;i,j=1,\.\.\.,K\\;\.\(9\)Row\-normalizing by\|𝒟i\|\|\\mathcal\{D\}\_\{i\}\|yieldsC~i,j=Ci,j/\|𝒟i\|\\tilde\{C\}\_\{i,j\}=C\_\{i,j\}/\|\\mathcal\{D\}\_\{i\}\|, which can be interpreted as an empirical estimate of the probability that a class\-iiinstance can be perturbed into classjjwithin toleranceτ\\tau\. The diagonal elementsC~i,i\\tilde\{C\}\_\{i,i\}reflect classifier robustness, while the off\-diagonal entries quantify feasible class transitions under structured perturbations\.

Finally, we define two summary metrics, capturing robust accuracy and vulnerability respectively\. LetN=∑i=1K\|𝒟i\|N=\\sum\_\{i=1\}^\{K\}\|\\mathcal\{D\}\_\{i\}\|denote the total number of samples\. We define

γa=1N​∑i=1KCi,i\\gamma\_\{\\mathrm\{a\}\}=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{K\}C\_\{i,i\}\(10\)
γv=1K​N​∑i=1K∑j:j≠iCi,j\.\\gamma\_\{\\mathrm\{v\}\}=\\frac\{1\}\{KN\}\\sum\_\{i=1\}^\{K\}\\sum\_\{j:j\\neq i\}C\_\{i,j\}\\;\\;\.\(11\)

## IVExperiments

In this section, we evaluate our method on both tabular and image data and conduct a robustness analysis using the proposed TOR\-CM\. A central goal of the evaluation is to determine whether XA\-L0L\_\{0\}produces compact, structurally coherent modifications\. Through TOR\-CM, we further investigate how such human\-interpretable perturbations reveal aspects of model robustness that remain invisible under conventional adversarial or norm\-bounded evaluations\. Across all experiments comparing XA\-L0L\_\{0\}with existing methods, we keep the classifier architecture, optimization budget, thresholding rules, and training procedures fixed to ensure that any observed differences in sparsity, coherence, or robustness stem from the loss formulations themselves rather than implementation details\.

### IV\-ATabular Data

![Refer to caption](https://arxiv.org/html/2607.06637v1/x1.png)\(a\)Breast Cancer: incoherenceϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)
![Refer to caption](https://arxiv.org/html/2607.06637v1/x2.png)\(b\)Breast Cancer: sparsitynn
![Refer to caption](https://arxiv.org/html/2607.06637v1/x3.png)\(c\)Coil2000: incoherenceϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)
![Refer to caption](https://arxiv.org/html/2607.06637v1/x4.png)\(d\)Coil2000: sparsitynn

Figure 1:Trade\-offs between proximity \(L2L\_\{2\}\), structural incoherence \(ϕ\\phi\), and sparsity \(nn\) for the Breast Cancer and Coil2000 datasets\. Left: structural incoherence versusL2L\_\{2\}\. Right: sparsity versusL2L\_\{2\}\. For clarity of visualization, instances are binned according to theirL2L\_\{2\}values, and the average of each metric within each bin is reported\. Solid lines denote the mean value in each bin, while shaded bands indicate one standard deviation\.We evaluate XA\-L0L\_\{0\}on a diverse collection of seven tabular datasets spanning binary and multiclass classification\. Table[I](https://arxiv.org/html/2607.06637#S4.T1)provides the basic information about the datasets\. For each dataset, we standardize the features, create training–test partitions, and train a two\-layer MLP classifier to obtain consistently strong predictive performance\. Counterfactuals are generated only for misclassified test samples, and all methods use identical optimization budgets, step sizes, and post\-hoc zero\-clipping rules to ensure a fair comparison\.

TABLE I:Datasets used in the tabular experiments\. All features are numeric and standardized per dataset\.To isolate the role of structured explainability, we compare against several baselines:

1. 1\.*XA\-L0L\_\{0\}*: Our proposed method, using the complete loss functionℒcomp\\mathcal\{L\}\_\{\\mathrm\{comp\}\}in Eq\.[III\-A](https://arxiv.org/html/2607.06637#S3.Ex2)\. Furthermore, we experiment with two schemes for XA\-L0L\_\{0\}using correlation and feature community detection respectively \(see Section[III\-B](https://arxiv.org/html/2607.06637#S3.SS2)\), which we refer to as XA\-L0L\_\{0\}\-corr and XA\-L0L\_\{0\}\-comm\.
2. 2\.*StandardL0L\_\{0\}*: Modifyℒcomp\\mathcal\{L\}\_\{\\mathrm\{comp\}\}by replacingℒXA​\-​L0\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}with the smoothL0L\_\{0\}surrogate\. This method is referred to asL0\+L2\+LclsL\_\{0\}\+L\_\{2\}\+L\_\{\\mathrm\{cls\}\}\.
3. 3\.*BaselineL2L\_\{2\}*: Modifyℒcomp\\mathcal\{L\}\_\{\\mathrm\{comp\}\}by removing the termℒXA​\-​L0\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\. This method is referred to asL2\+LclsL\_\{2\}\+L\_\{\\mathrm\{cls\}\}\.
4. 4\.*BaselineL0L\_\{0\}*: Modifyℒcomp\\mathcal\{L\}\_\{\\mathrm\{comp\}\}by removing the termℒprox\\mathcal\{L\}\_\{\\mathrm\{prox\}\}and replacingℒXA​\-​L0\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}with the plainL0L\_\{0\}norm\. This method is referred to asL0\+LclsL\_\{0\}\+L\_\{\\mathrm\{cls\}\}\.
5. 5\.*Dandl\-inspired scalarization sweep*: A baseline inspired by Dandl et al\.\[[3](https://arxiv.org/html/2607.06637#bib.bib23)\]and their trade\-off view of counterfactual generation\. We obtain multiple candidate counterfactuals by sweeping scalarization weights in a gradient\-based objective that combines classification, sparsity, and proximity terms\.

For the XA\-L0L\_\{0\}\-comm variant, we construct a feature–feature affinity matrix from the training set using the absolute Pearson correlation matrix, normalized to\[0,1\]\[0,1\]\. We then apply spectral clustering with this precomputed affinity to partition theddfeatures intoKcK\_\{c\}communities, whereKc=max⁡\{2,min⁡\(d−1,round​\(d\)\)\}K\_\{c\}=\\max\\\{2,\\min\(d\-1,\\ \\mathrm\{round\}\(\\sqrt\{d\}\)\)\\\}\. The resulting discrete community labelsci∈\{1,…,Kc\}c\_\{i\}\\in\\\{1,\\ldots,K\_\{c\}\\\}define a block\-structured penalty matrixWW, assigning a smaller within\-community penaltyωin\\omega\_\{\\mathrm\{in\}\}and a larger cross\-community penaltyωout\\omega\_\{\\mathrm\{out\}\}\(withWi​i=0W\_\{ii\}=0\), encouraging coordinated edits within coherent feature groups\. Across all methods we report proximity \(L2L\_\{2\}\), sparsity \(that is, the number of changed features after thresholding, denoted bynn\), and the structural incoherence scoreϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)computed on the same dataset\-level computed using the same pairwise incoherence matrixWW\. To sweep out the trade\-offs in Figure[1](https://arxiv.org/html/2607.06637#S4.F1), we generate multiple counterfactual solutions per test instance by varying the regularization weights in the optimization objective\. For XA\-L0L\_\{0\}\(both corr and comm variants\), we evaluate a grid over \(λ1\\lambda\_\{\\mathrm\{1\}\},λ2\\lambda\_\{\\mathrm\{2\}\}\); for the baselines we sweep the corresponding penalty weights \(onlyλ2\\lambda\_\{\\mathrm\{2\}\}forL2\+LclsL\_\{2\}\+L\_\{\\mathrm\{cls\}\}, onlyλ1\\lambda\_\{1\}forL0\+LclsL\_\{0\}\+L\_\{\\mathrm\{cls\}\}, and \(λ1\\lambda\_\{1\},λ2\\lambda\_\{\\mathrm\{2\}\}\) forL0\+L2\+LclsL\_\{0\}\+L\_\{2\}\+L\_\{\\mathrm\{cls\}\}\)\. The resulting runs are binned by their achievedL2L\_\{2\}, and we report the mean and one\-standard\-deviation bands ofϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)\(ornn\) within each bin\.

Figure[1](https://arxiv.org/html/2607.06637#S4.F1)visualizes trade\-offs between proximity \(measured byL2L\_\{2\}norm\) and interpretability measures, specifically, the structural incoherence and sparsity based on two datasets \(Breast Cancer and Coil2000\)\. The instances are binned based on theirL2L\_\{2\}values\. Then the averageϕ\\phi,nn, andL2L\_\{2\}are computed for instances in each bin\. The left column reports the average structural incoherenceϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)and the right column reports the average sparsitynn, both versus the average binnedL2L\_\{2\}values\. Across bins and across both datasets, XA\-L0L\_\{0\}\(correlation\- and community\-based variants\) consistently yields substantially smallerϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)than theL2\+LclsL\_\{2\}\+L\_\{\\mathrm\{cls\}\}baseline, indicating that the modified features form a more compact and internally consistent group under the feature\-dependence structure\. This advantage is especially pronounced on Coil2000, where theL2\+LclsL\_\{2\}\+L\_\{\\mathrm\{cls\}\}baseline exhibits high incoherence penalties and large numbers of changed features, whereas XA\-L0L\_\{0\}maintains lowϕ​\(𝒮\)\\phi\(\\mathcal\{S\}\)while keepingnnsmall\. Furthermore, XA\-L0L\_\{0\}\-corr achieves the lowest values of bothϕ\\phiand sparsitynnacross allL2L\_\{2\}values, outperforming all other methods\. XA\-L0L\_\{0\}\-comm exhibits similar performance\.

TABLE II:Median\-bin summary: for each dataset, the averageϕ\\phiandnncomputed over instances in the bin corresponding to the medianL2L\_\{2\}value\.Results for all seven datasets are summarized in Table[II](https://arxiv.org/html/2607.06637#S4.T2)\. For each dataset and method, we focus on instances that belong to the bin with the medianL2L\_\{2\}value\. We then compute the average structural incoherenceϕ\\phiand sparsitynnover these instances\. Two consistent trends emerge\. First, theL2\+LclsL\_\{2\}\+L\_\{\\mathrm\{cls\}\}baseline typically achieves class flips by spreading small adjustments across many features, resulting in both high incoherence and large support sizes \(e\.g\., Digits:ϕ=75\.868\\phi=75\.868,n=55\.3n=55\.3; Breast Cancer:ϕ=33\.887\\phi=33\.887,n=28\.2n=28\.2\)\. Second, introducing sparsity via theL0\+L2\+LclsL\_\{0\}\+L\_\{2\}\+L\_\{\\mathrm\{cls\}\}baseline improves sparsity but does not guarantee better structural incoherence, indicating that the selected features are not necessarily affinity\-consistent\.

XA\-L0L\_\{0\}addresses this gap by explicitly coupling feature activations\. On datasets with clear dependency structure, most notably Breast Cancer and Digits, XA\-L0L\_\{0\}\-corr/comm achieves very small incoherence penalties while keepingnnin the single digits, demonstrating that the correction can be both compact and structurally aligned\. On simpler problems such as Iris, many methods already admit near\-minimal edits; accordingly, XA\-L0L\_\{0\}\-comm and Dandl reachϕ≈0\.250\\phi\\approx 0\.250withn≈1n\\approx 1, and the difference between methods is negligible\. On Wine, XA\-L0L\_\{0\}\-corr and Dandl again provide low\-ϕ\\phisolutions with smallnn, while theL2\+LclsL\_\{2\}\+L\_\{\\mathrm\{cls\}\}baseline remains substantially more diffuse\.

The advantage of XA\-L0L\_\{0\}over other methods is less pronounced on datasets with weak or relatively uniform correlations between features, such as Wine Quality Red and Phoneme\. For these datasets, structural incoherence values are higher across all methods, suggesting that correlation\-derived affinity is less informative or that meaningful dependencies are distributed across multiple predictors\. Even in this regime, XA\-L0L\_\{0\}remains competitive in terms of sparsity \(with single\-digitnn\) and avoids the extreme diffuseness exhibited by theL2\+LclsL\_\{2\}\+L\_\{\\mathrm\{cls\}\}baseline\. Overall, the table supports the central claim: whenever the data exhibit an interpretable dependency structure, incorporating this structure into the sparsity regularizer yields counterfactual corrections that are simultaneously more coherent and more parsimonious than proximity\-only or unstructured\-sparsity alternatives\.

To illustrate how the method quantifies a decision’s proximity to changing, we consider a test applicant from the COIL2000 insurance dataset who is predicted as not likely to purchase \(class 0\) with purchase probability0\.4300\.430\. Using the training\-set correlation structure, we partition thed=85d=85features intoKc=9K\_\{c\}=9communities and then compute targeted counterfactuals under the prescribed tolerance and thresholding rule\. For XA\-L0L\_\{0\}\-comm, the purchase probability increases from0\.4300\.430to0\.5000\.500with only\|S\|=3\|S\|=3meaningful feature edits, touching 3 communities \(one feature each from communities 0, 2, and 6\)\. The dominant change is in the relationship\-status indicator \(MRELOV\), accompanied by smaller shifts in a brand\-related insurance attribute \(ABRAND\) and the trailer\-policy contribution variable \(PAANHANG\)\. In comparison, a Dandl baseline reaches a similar probability threshold \(0\.5000\.500\) but requires a less compact change:\|S\|=8\|S\|=8feature edits spanning 5 communities, with prominent adjustments including social\-class indicators \(e\.g\., MOPLHOOG, MAUT0\), relationship status \(MRELOV\), and several insurance product variables \(ABRAND, PBYSTAND, PAANHANG\), along with additional attributes \(AWERKT, AZEILPL\)\. From an application perspective, such results provide actionable insight into decision sensitivity: they reveal whether a borderline “not likely to purchase” prediction is driven by a small set of coherent factors \(as in the XA\-L0L\_\{0\}\-comm explanation\) or whether crossing the decision boundary would require broader, multi\-factor shifts\. This distinction can support model debugging and policy design, for example, by flagging cases where the decision hinges on a single sensitive attribute, or by identifying which groups of features most strongly control the transition from non\-purchase to purchase predictions\.

### IV\-BImage Data

We evaluate XA\-L0L\_\{0\}on two image benchmarks with different levels of visual complexity\. MNIST offers a controlled grayscale setting where counterfactual corrections often correspond to small, spatially localized stroke edits\. We use penaltyℒXA​\-​L0\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}on MNIST\. Flowers\-102 consists of natural RGB photographs, where successful corrections can involve more complex appearance changes\. On this dataset, we experiment with the edge\-aware penaltyℒXA​\-​L0ed\\mathcal\{L\}^\{\\mathrm\{ed\}\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}and test whether it encourages modifications to concentrate near edges, which are more visually salient than smooth regions\. In both experiments we start from misclassified test instances and generate*targeted*counterfactuals toward the ground\-truth label while keeping the classifier fixed\. After optimization, we apply zero\-clipping as described in Sec\.[III](https://arxiv.org/html/2607.06637#S3)to remove small\-magnitude artifacts\.

![Refer to caption](https://arxiv.org/html/2607.06637v1/MNIST/mnist_summary_plot.png)\(a\)XA\-L0L\_\{0\}
![Refer to caption](https://arxiv.org/html/2607.06637v1/MNIST/mnist_summary_l0pgd.png)\(b\)L0L\_\{0\}
![Refer to caption](https://arxiv.org/html/2607.06637v1/MNIST/mnist_summary_cemae.png)\(c\)CEMAE

Figure 2:Targeted MNIST corrections on five misclassified test images\. Red overlay indicates pixels that changed\. XA\-L0L\_\{0\}produces compact, stroke\-aligned edits across a range of\(λ1,t\)\(\\lambda\_\{1\},t\)settings, whileL0L\_\{0\}and CEMAE tend to yield less coherent or more diffuse changes\.#### \(a\) MNIST: distance\-based incoherence and sparsity control

A pretrained CNN classifier \(two3×33\\times 3convolution blocks with ReLU and2×22\\times 2max pooling, followed by two fully connected layers\) is used and kept fixed during counterfactual generation\. We show results for five misclassified test images and compare three methods: XA\-L0L\_\{0\}, a generic sparsity\-drivenL0L\_\{0\}baseline \(referred to asL0L\_\{0\}\), and*CEMAE*\[[5](https://arxiv.org/html/2607.06637#bib.bib3)\]\(a contrastive explanation method with an autoencoder prior\)\. For XA\-L0L\_\{0\}, we fixλ2=0\.1\\lambda\_\{2\}=0\.1and vary the sparsity weightλ1\\lambda\_\{1\}and clipping thresholdttover

\(λ1,t\)∈\{\(10−4,1255\),\(5×10−4,1255\),\(10−3,1255\),\(5×10−4,10255\),\(5×10−4,15255\)\}\.\(\\lambda\_\{1\},t\)\\in\\Bigl\\\{\\begin\{aligned\} &\(10^\{\-4\},\\tfrac\{1\}\{255\}\),\\,\(5\\times 10^\{\-4\},\\tfrac\{1\}\{255\}\),\\,\(10^\{\-3\},\\tfrac\{1\}\{255\}\),\\\\ &\(5\\times 10^\{\-4\},\\tfrac\{10\}\{255\}\),\\,\(5\\times 10^\{\-4\},\\tfrac\{15\}\{255\}\)\\end\{aligned\}\\Bigr\\\}\.Figure[2](https://arxiv.org/html/2607.06637#S4.F2)presents the resulting counterfactual images\. The red overlay marks the set of pixels changed from the original image, directly visualizing the number of modifications required to reach correct classification\. Two consistent trends appear\. First, as shown by columns 1–3 with a fixedt=1255t=\\tfrac\{1\}\{255\}, increasingλ1\\lambda\_\{1\}produces progressively sparser solutions: the red overlay shrinks to a smaller number of pixels\. Second, for fixedλ1=5×10−4\\lambda\_\{1\}=5\\times 10^\{\-4\}\(shown by columns 1,4,5\), increasingttremoves speckles caused by low\-magnitude changes and preserves only the dominant contiguous changes that drive the correction\. As expected,λ1\\lambda\_\{1\}plays the primary role of controlling how many pixels are changed, while thresholding atttcan further reduce the number of pixel changes required to steer the classification to the target class\. Compared to the two baseline methods, XA\-L0L\_\{0\}consistently produces spatially compact edits concentrated on or near digit strokes rather than in the black background, whereasL0L\_\{0\}and CEMAE tend to yield less coherent selections or more extensive modifications\. Overall, the distance\-based coupling produces minimal corrections that are both sparse and visually meaningful\.

#### \(b\) Flowers\-102: edge\-focused incoherence on natural images

Next, we evaluate XA\-L0L\_\{0\}in a natural\-image setting using Flowers\-102 dataset\. We fine\-tune a ResNet\-18 classifier for 102\-way classification and keep it fixed during counterfactual generation\. Here we use the edge\-focused coherence penaltyℒXA​\-​L0ed\\mathcal\{L\}^\{\\mathrm\{ed\}\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}, which favors changing pixels near detected edges and discourages edits deep inside homogeneous regions\. To threshold pixel changes after minimizing the penalty function, we normalize pixel values to\[0,1\]\[0,1\]and select the largestt⋆t^\{\\star\}from the set\{1,…,10\}/255\\\{1,\\ldots,10\\\}/255such that the target label is still obtained after zero\-clipping\.

![Refer to caption](https://arxiv.org/html/2607.06637v1/x5.png)Figure 3:Flowers\-102 targeted corrections on five misclassified test images\. Rows show the original image and counterfactuals for XA\-L0L\_\{0\}\(edge\-focused\), CEM, and SEDC\.We compare against two representative baseline counterfactual methods for images:*CEM*\[[5](https://arxiv.org/html/2607.06637#bib.bib3)\], an optimization\-based method with elastic\-net regularization but no explicit spatial or edge coherence, and*SEDC*\[[18](https://arxiv.org/html/2607.06637#bib.bib51)\], a superpixel\-based evidence counterfactual method that achieves the target by replacing selected segments\.

Example counterfactual images for five misclassified images are shown in Figure[3](https://arxiv.org/html/2607.06637#S4.F3), with the true class as the target\. Again, the red overlays indicate the set of pixels whose values are changed\. XA\-L0L\_\{0\}typically produces a small number of visually coherent modifications concentrated near object boundaries and salient contours, whereas CEM often requires more dispersed pixel changes and SEDC produces larger region\-level edits that reflect its segment\-replacement mechanism\. These qualitative observations are consistent with the quantitative comparison in Figure[4](https://arxiv.org/html/2607.06637#S4.F4)over 50 images\. The figure shows boxplots of theL0L\_\{0\}mask count \(i\.e\., the number of changed pixels after zero\-clipping\), theL2L\_\{2\}penalty \(the totalL2L\_\{2\}distance over all changed pixels\), and the mean distance from each changed pixel to its nearest edge pixel in the image plane\. XA\-L0L\_\{0\}achieves substantially smallerL0L\_\{0\}values \(i\.e\., fewer changed pixels\) and smallerL2L\_\{2\}values than SEDC\. Compared with CEM, XA\-L0L\_\{0\}attains similarL2L\_\{2\}values but considerably smallerL0L\_\{0\}values\. Moreover, XA\-L0L\_\{0\}yields a significantly smaller mean distance to edges than the other methods\. Overall, results on Flowers\-102 demonstrate that incorporating edge\-aware coherence produces counterfactual corrections that are both parsimonious and aligned with human\-perceptual structure\.

![Refer to caption](https://arxiv.org/html/2607.06637v1/x6.png)Figure 4:Comparison of three methods, XA\-L0L\_\{0\}, CEM, and SEDC, based on 50 misclassified Flowers\-102 images using boxplots\. \(a\) Number of changed pixels \(L0L\_\{0\}mask count\), \(b\) The totalL2L\_\{2\}distance, \(c\) The mean distance of changed pixels to the nearest detected edge\.

### IV\-CRobustness Assessment with TOR\-Confusion Matrix

To assess robustness under bounded, interpretable modifications, we use the Tolerance\-Region Confusion Matrix \(TOR\-CM\)\. Whereas a standard confusion matrix evaluates predictions only at the original inputs, TOR\-CM characterizes the probability of class\-to\-class transitions when inputs are allowed to vary within a prescribed tolerance region\.

Figure[5](https://arxiv.org/html/2607.06637#S4.F5)illustrates the idea on a toy problem with four classes in a two\-dimensional feature space\. The left panel shows the decision regions of a nearest\-centroid classifier\. For a point𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}and tolerance radiusτ\\tau\(as an example,L2L\_\{2\}distance is used\), we define a tolerance region𝒯τ​\(𝐱\(o\)\)\\mathcal\{T\}\_\{\\tau\}\(\\mathbf\{x\}^\{\(o\)\}\)\(dashed circle\)\. For each target classjj, we search within𝒯τ​\(𝐱\(o\)\)\\mathcal\{T\}\_\{\\tau\}\(\\mathbf\{x\}^\{\(o\)\}\)for a*feasible point*𝐱∗\\mathbf\{x\}^\{\*\}such thatf​\(𝐱∗\)=jf\(\\mathbf\{x\}^\{\*\}\)=j\. When such a point exists, we mark it by a cross in the left panel and connect it to𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}, indicating that classjjis reachable from𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}under the tolerance budget\.

The right panel shows the TOR\-CM at a fixed shared tolerance radiusτ=0\.30\\tau=0\.30, computed by repeating the same reachability check over a collection of points from each true class\. Each entry reports the fraction of class\-iipoints for which classjjis reachable within𝒯τ​\(𝐱\(o\)\)\\mathcal\{T\}\_\{\\tau\}\(\\mathbf\{x\}^\{\(o\)\}\)\. For example, for true class0, class11is reachable for about74%74\\%of points and class22for about14%14\\%, while class33is not reachable at this budget \(entry0\.000\.00\)\. Similarly, for true class11, classes0and33are frequently reachable \(approximately66%66\\%and29%29\\%\)\. The inset shows the standard confusion matrix on the unperturbed points, which is perfectly diagonal in this toy setup\. TOR\-CM therefore complements standard evaluation by summarizing prediction stability in terms of feasible class transitions under bounded perturbations\.

![Refer to caption](https://arxiv.org/html/2607.06637v1/x7.png)Figure 5:Illustration of TOR\-CM on a 2D four\-class toy problem\. Left: tolerance regions \(dashed circles\) and examples of feasible points \(crosses\) inside the region that achieve specified target classes\. Right: TOR\-CM at shared radiusτ=0\.30\\tau=0\.30, where each entry is the fraction of class\-iipoints from which classjjis reachable; inset: standard confusion matrix on unperturbed inputs\.
### IV\-DTOR\-CM for MNIST via distilled surrogates

To illustrate TOR\-CM in an image setting, we evaluate four classifiers on MNIST and compute a TOR\-CM for each: Logistic Regression \(LogReg\), Decision Tree \(CART\), Random Forest \(RF\), and a CNN\. TOR\-CM requires repeated counterfactual searches toward specified target classes\. To enable a unified gradient\-based search for the non\-differentiable classical models, we train smooth MLP*surrogates*for LogReg, CART, and RF via knowledge distillation: each surrogate minimizes the KL\-divergence to the teacher model’s predicted class\-probability vector\. The CNN is inherently differentiable and is used directly for computing counterfactuals\. All neural models \(surrogates and CNN\) are implemented in PyTorch\.

##### Counterfactual search and tolerance region

For each test image𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}and each target classjj, we run XA\-L0L\_\{0\}to obtain an optimized image𝐱∗\\mathbf\{x\}^\{\*\}\. For the classical models \(LogReg, CART, RF\), although the counterfactual is searched by XA\-L0L\_\{0\}using a differentiable surrogate model, the target reachability is always confirmed using the original teacher classifier\. We declare classjjreachable from𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}only if the prediction by the teacher model satisfiesf​\(𝐱∗\)=jf\(\\mathbf\{x\}^\{\*\}\)=j\.

The tolerance region is defined using the same interpretable penalty that governs XA\-L0L\_\{0\}modifications, excluding the classification hinge term\. We measure the tolerance loss by

ℒ​\(𝐱′,𝐱\(o\)\)=ℒXA​\-​L0​\(𝐱′,𝐱\(o\)\)\+ℒprox​\(𝐱′,𝐱\(o\)\),\\displaystyle\\mathcal\{L\}\(\\mathbf\{x\}^\{\\prime\},\\mathbf\{x\}^\{\(o\)\}\)=\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\(\\mathbf\{x\}^\{\\prime\},\\mathbf\{x\}^\{\(o\)\}\)\+\\mathcal\{L\}\_\{\\mathrm\{prox\}\}\(\\mathbf\{x\}^\{\\prime\},\\mathbf\{x\}^\{\(o\)\}\),\(12\)whereℒXA​\-​L0\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}is the structured XA\-L0L\_\{0\}penalty andℒprox\\mathcal\{L\}\_\{\\mathrm\{prox\}\}is the proximity \(magnitude\) penalty used by XA\-L0L\_\{0\}\.

##### Fromλ\\lambda\-sweeps to reachability under a fixed budgetτ\\tau

We adjust the objective function used by XA\-L0L\_\{0\}in Eq\.[III\-A](https://arxiv.org/html/2607.06637#S3.Ex2)slightly:

ℒcomp​\(𝐱′,𝐱\(o\)\)\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{comp\}\}\(\\mathbf\{x\}^\{\\prime\},\\mathbf\{x\}^\{\(o\)\}\)=\\displaystyle=ℒcls​\(𝐱′\)\+λ​\(ℒXA​\-​L0​\(𝐱′,𝐱\(o\)\)\+ℒprox​\(𝐱′,𝐱\(o\)\)\),\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{cls\}\}\(\\mathbf\{x\}^\{\\prime\}\)\+\\lambda\\big\(\\mathcal\{L\}\_\{\\mathrm\{XA\\text\{\-\}L\_\{0\}\}\}\(\\mathbf\{x\}^\{\\prime\},\\mathbf\{x\}^\{\(o\)\}\)\+\\mathcal\{L\}\_\{\\mathrm\{prox\}\}\(\\mathbf\{x\}^\{\\prime\},\\mathbf\{x\}^\{\(o\)\}\)\\big\),where we use a single penalty weightλ\\lambdato be consistent with the tolerance loss in Eq\.[12](https://arxiv.org/html/2607.06637#S4.E12)\. Since the tolerance loss is not directly set in optimization, we experiment with a set ofλ\\lambdavalues taken from a predefined grid\. For each pair\(𝐱\(o\),j\)\(\\mathbf\{x\}^\{\(o\)\},j\)and eachλ\\lambda, we obtain an output𝐱∗​\(λ\)\\mathbf\{x\}^\{\*\}\(\\lambda\)and record the achieved tolerance lossℒ​\(𝐱∗​\(λ\),𝐱\(o\)\)\\mathcal\{L\}\(\\mathbf\{x\}^\{\*\}\(\\lambda\),\\mathbf\{x\}^\{\(o\)\}\)together with a binary success indicatorB​\(λ\)=𝕀​\{f​\(𝐱∗​\(λ\)\)=j\}B\(\\lambda\)=\\mathbb\{I\}\\\{f\(\\mathbf\{x\}^\{\*\}\(\\lambda\)\)=j\\\}\. We then define the cutoff value

ℒ∗​\(𝐱\(o\),j\)=minλ:B​\(λ\)=1⁡ℒ​\(𝐱∗​\(λ\),𝐱\(o\)\),\\mathcal\{L\}^\{\*\}\(\\mathbf\{x\}^\{\(o\)\},j\)=\\min\_\{\\lambda:\\,B\(\\lambda\)=1\}\\mathcal\{L\}\(\\mathbf\{x\}^\{\*\}\(\\lambda\),\\mathbf\{x\}^\{\(o\)\}\),with the conventions that ifB​\(λ\)=0B\(\\lambda\)=0for allλ\\lambdawe setℒ∗\\mathcal\{L\}^\{\*\}to a value larger than all achieved losses, and ifB​\(λ\)=1B\(\\lambda\)=1for allλ\\lambdawe setℒ∗=ε\\mathcal\{L\}^\{\*\}=\\varepsilon, whereε\\varepsilonis below all the values ofτ\\tauexamined in the experiments\. For any fixed tolerance budgetτ\\tau, we declare classjjreachable from𝐱\(o\)\\mathbf\{x\}^\{\(o\)\}iffτ≥ℒ∗​\(𝐱\(o\),j\)\\tau\\geq\\mathcal\{L\}^\{\*\}\(\\mathbf\{x\}^\{\(o\)\},j\)\. Aggregating these reachability indicators yields TOR\-CMCi,jC\_\{i,j\}as in \([9](https://arxiv.org/html/2607.06637#S3.E9)\)\. For visualization, we report the per\-class normalized matrixC~i,j=Ci,j/\|𝒟i\|\\tilde\{C\}\_\{i,j\}=C\_\{i,j\}/\|\\mathcal\{D\}\_\{i\}\|\.

##### Choice of tolerance budgets

To assess robustness across classifiers over a meaningful range of interpretable modification budgets, we report TOR\-CM at three fixed tolerances,τ∈\{120,350,700\}\\tau\\in\\\{120,350,700\\\}\. These values are chosen to span three qualitatively distinct regimes of the counterfactual search: a*low\-budget*regime where only the easiest class transitions are feasible and TOR\-CM remains close to diagonal; an*intermediate*regime where off\-diagonal reachability begins to appear for a subset of class pairs, exposing early differences in robustness across models; and a*high\-budget*regime where many more transitions become feasible, revealing how quickly each classifier’s reachable set expands under interpretable perturbations\. Using a shared set ofτ\\tauvalues across all methods enables direct comparison of robustness at the same absolute tolerance, while still capturing how stability degrades as the tolerance is relaxed\.

##### Results

We evaluate on a balanced subset of100100MNIST test images \(10 per class\)\. For each model and each tolerance budgetτ∈\{120,350,700\}\\tau\\in\\\{120,350,700\\\}, we compute TOR\-CM and summarize robustness usingγa\\gamma\_\{\\mathrm\{a\}\}andγv\\gamma\_\{\\mathrm\{v\}\}defined by \([10](https://arxiv.org/html/2607.06637#S3.E10)\)–\([11](https://arxiv.org/html/2607.06637#S3.E11)\)\. Figure[6](https://arxiv.org/html/2607.06637#S4.F6)shows that TOR\-CM reveals robustness differences that are largely invisible in the standard confusion matrices \(top row\)\. An interesting observation from this figure is that although the CNN achieves the highest accuracy on original instances, it is clearly less robust than the other methods\. While achieving competitive accuracy on the original instances, RF and CART are the most robust across all tolerance levels, with RF outperforming CART\.

![Refer to caption](https://arxiv.org/html/2607.06637v1/x8.png)Figure 6:MNIST TOR\-CM \(per\-class normalized\) based on distilled surrogate models\. The four columns of the plots correspond to the classification methods: LogReg, CART, RF, CNN\. Top row: standard confusion matrices\. Rows 2–4: TOR\-CM atτ=120,350,700\\tau=120,350,700respectively\. Beneath each panel, the values ofγa\\gamma\_\{\\mathrm\{a\}\}andγv\\gamma\_\{\\mathrm\{v\}\}are presented\.At the smallest budgetτ=110\\tau=110, LogReg already exhibits noticeable off\-diagonal reachabilityγv=0\.106\\gamma\_\{v\}=0\.106, whereas CART remains comparatively stableγv=0\.045\\gamma\_\{v\}=0\.045and RF is the most stableγv=0\.006\\gamma\_\{v\}=0\.006\. In contrast, the CNN shows substantially higher reachability even at this low budget withγv=0\.280\\gamma\_\{v\}=0\.280, indicating that many target classes can be achieved within the tolerance region\. As the budget increases toτ=350\\tau=350, the difference between the models becomes much more pronounced\. LogReg’s off\-diagonal mass grows furtherγv=0\.206\\gamma\_\{v\}=0\.206, and CART increases modestlyγv=0\.073\\gamma\_\{v\}=0\.073, while RF remains close to diagonalγv=0\.016\\gamma\_\{v\}=0\.016\. The CNN, however, undergoes a sharp expansion in reachability, with a large fraction of class transitions becoming feasible, yieldingγv=0\.737\\gamma\_\{v\}=0\.737, as shown by a substantially denser TOR\-CM than all other methods\. At the largest budgetτ=700\\tau=700, LogReg continues to broaden its reachability \(γv=0\.278\\gamma\_\{v\}=0\.278\) and CART increasesγv\\gamma\_\{v\}slightly to0\.0980\.098, while RF remains the most stable overall withγv=0\.027\\gamma\_\{v\}=0\.027\. The CNN nearly saturates TOR\-CM: any class becomes almost always reachable from any data point with the vulnerability indicator rising toγv=0\.900\\gamma\_\{v\}=0\.900\. Across all methods,γa\\gamma\_\{a\}is near 1 at moderate and large budgets, indicating that the true class is typically reachable within the tolerance region; the key differences are therefore driven by how rapidly the off\-diagonal reachability grows asτ\\tauincreases\.

## VConclusions & Discussion

We have presented a unified framework for generating interpretable counterfactuals and assessing the robustness of black\-box classifiers\. Central to our approach is the explainability\-awareL0L\_\{0\}\(XA\-L0L\_\{0\}\) penalty, which encourages sparse and structurally coherent modifications, combined with a misclassification\-driven loss that steers perturbed instances toward specified target labels\. Our experiments on both tabular and image datasets demonstrate that XA\-L0L\_\{0\}consistently produces compact, interpretable corrections while avoiding the diffuseness typical of proximity\-only or unstructured\-sparsity baselines\. Furthermore, the Tolerance\-Region Confusion Matrix \(TOR\-CM\) provides a complementary tool for assessing robustness under interpretable modifications, revealing vulnerabilities that standard evaluation may miss\.

A natural direction for future work is to extend the method to datasets with categorical or mixed\-type features\. In this setting, performing counterfactual optimization is challenging, and determining which feature changes are interpretable is highly data\-dependent\. Another promising avenue is to tailor the explainability\-aware sparsity penalty to specific application domains, allowing it to encode practically motivated constraints or preferences\. Furthermore, counterfactuals produced by the framework could inform improvements to the underlying classifier or guide targeted data collection, by revealing systematic patterns in misclassification\. More broadly, it would be interesting to integrate this approach with active learning or model debugging pipelines, where interpretable counterfactuals not only explain errors but also suggest actionable interventions to enhance model robustness and fairness\.

## References

- \[1\]\(2020\)Getting a clue: a method for explaining uncertainty estimates\.arXiv preprint arXiv:2006\.06848\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p2.1)\.
- \[2\]J\. Cohen, E\. Rosenfeld, and J\. Z\. Kolter\(2019\)Certified adversarial robustness via randomized smoothing\.InInternational Conference on Machine Learning \(ICML\),pp\. 1310–1320\.Cited by:[§I](https://arxiv.org/html/2607.06637#S1.p3.1),[§I](https://arxiv.org/html/2607.06637#S1.p5.1),[§II](https://arxiv.org/html/2607.06637#S2.p6.1)\.
- \[3\]S\. Dandl, C\. Molnar, M\. Binder, and B\. Bischl\(2021\)Multi\-objective counterfactual explanations\.Machine Learning110\(3\),pp\. 495–507\.Cited by:[§I](https://arxiv.org/html/2607.06637#S1.p2.3),[§II](https://arxiv.org/html/2607.06637#S2.p2.1),[§II](https://arxiv.org/html/2607.06637#S2.p3.6),[item 5](https://arxiv.org/html/2607.06637#S4.I1.i5.p1.1)\.
- \[4\]A\. Dhurandhar, P\. Chen, R\. Luss, C\. Tu, P\. Ting, K\. Shanmugam, and P\. Das\(2018\)Desiderata for interpretable explanations: quantifying interpretability of explanations\.InProceedings of the 2018 IEEE International Conference on Data Mining \(ICDM\),pp\. 1103–1108\.Cited by:[§I](https://arxiv.org/html/2607.06637#S1.p2.3),[§II](https://arxiv.org/html/2607.06637#S2.p2.1),[§II](https://arxiv.org/html/2607.06637#S2.p3.6)\.
- \[5\]A\. Dhurandhar, P\. Chen, R\. Luss, C\. Tu, P\. Ting, K\. Shanmugam, and P\. Das\(2018\)Explanations based on the missing: towards contrastive explanations with pertinent negatives\.Advances in neural information processing systems31\.Cited by:[§IV\-B](https://arxiv.org/html/2607.06637#S4.SS2.SSSx1.p1.9),[§IV\-B](https://arxiv.org/html/2607.06637#S4.SS2.SSSx2.p2.1)\.
- \[6\]I\. J\. Goodfellow, J\. Shlens, and C\. Szegedy\(2015\)Explaining and harnessing adversarial examples\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§I](https://arxiv.org/html/2607.06637#S1.p3.1),[§I](https://arxiv.org/html/2607.06637#S1.p5.1),[§II](https://arxiv.org/html/2607.06637#S2.p6.1)\.
- \[7\]S\. Joshi, O\. Koyejo, W\. Vijitbenjaronk, B\. Kim, and J\. Ghosh\(2019\)Towards realistic individual recourse and actionable explanations in black\-box decision making systems\.arXiv preprint arXiv:1907\.09615\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p2.1)\.
- \[8\]A\. Karimi, B\. Schölkopf, and I\. Valera\(2021\)Algorithmic recourse: from counterfactual explanations to interventions\.InProceedings of the 2021 ACM conference on fairness, accountability, and transparency,pp\. 353–362\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p2.1)\.
- \[9\]S\. Kim, K\. Sohn, and E\. P\. Xing\(2009\)Multivariate regression with grouped variables: modeling and estimation via sparse graphical models\.Journal of Machine Learning Research10,pp\. 513–546\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p4.1)\.
- \[10\]T\. Laugel, M\. Lesot, C\. Marsala, X\. Renard, and M\. Detyniecki\(2017\)Inverse classification for comparison\-based interpretability in machine learning\.arXiv preprint arXiv:1712\.08443\.Cited by:[§I](https://arxiv.org/html/2607.06637#S1.p2.3)\.
- \[11\]A\. Madry, A\. Makelov, L\. Schmidt, D\. Tsipras, and A\. Vladu\(2018\)Towards deep learning models resistant to adversarial attacks\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§I](https://arxiv.org/html/2607.06637#S1.p3.1),[§I](https://arxiv.org/html/2607.06637#S1.p5.1),[§II](https://arxiv.org/html/2607.06637#S2.p6.1)\.
- \[12\]R\. K\. Mothilal, A\. Sharma, and C\. Tan\(2020\)Explaining machine learning classifiers through diverse counterfactual explanations\.InProceedings of the 2020 conference on fairness, accountability, and transparency,pp\. 607–617\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p2.1)\.
- \[13\]M\. E\. J\. Newman\(2006\)Modularity and community structure in networks\.Proceedings of the National Academy of Sciences103\(23\),pp\. 8577–8582\.Cited by:[§III\-B](https://arxiv.org/html/2607.06637#S3.SS2.SSSx1.p3.4)\.
- \[14\]R\. Tibshirani, M\. Saunders, S\. Rosset, J\. Zhu, and K\. Knight\(2005\)Sparsity and smoothness via the fused lasso\.Journal of the Royal Statistical Society: Series B \(Statistical Methodology\)67\(1\),pp\. 91–108\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p4.1)\.
- \[15\]A\. Van Looveren and J\. Klaise\(2021\)Interpretable counterfactual explanations guided by prototypes\.InJoint European Conference on Machine Learning and Knowledge Discovery in Databases,pp\. 650–665\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p2.1)\.
- \[16\]S\. Verma, V\. Boonsanong, M\. Hoang, K\. Hines, J\. Dickerson, and C\. Shah\(2024\-10\)Counterfactual explanations and algorithmic recourses for machine learning: a review\.ACM Comput\. Surv\.56\(12\)\.External Links:ISSN 0360\-0300,[Link](https://doi.org/10.1145/3677119),[Document](https://dx.doi.org/10.1145/3677119)Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p2.1)\.
- \[17\]S\. Verma, V\. Boonsanong, M\. Hoang, K\. Hines, J\. Dickerson, and C\. Shah\(2024\)Counterfactual explanations and algorithmic recourses for machine learning: a review\.ACM Computing Surveys56\(12\),pp\. 1–42\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p2.1)\.
- \[18\]T\. Vermeire, D\. Brughmans, S\. Goethals, R\. M\. B\. De Oliveira, and D\. Martens\(2022\)Explainable image classification with evidence counterfactual\.Pattern Analysis and Applications25\(2\),pp\. 315–335\.Cited by:[§IV\-B](https://arxiv.org/html/2607.06637#S4.SS2.SSSx2.p2.1)\.
- \[19\]U\. Von Luxburg\(2007\)A tutorial on spectral clustering\.Statistics and computing17\(4\),pp\. 395–416\.Cited by:[§III\-B](https://arxiv.org/html/2607.06637#S3.SS2.SSSx1.p3.4)\.
- \[20\]S\. Wachter, B\. Mittelstadt, and C\. Russell\(2017\)Counterfactual explanations without opening the black box: automated decisions and the gdpr\.Harvard Journal of Law & Technology31\(2\),pp\. 841–887\.Cited by:[§I](https://arxiv.org/html/2607.06637#S1.p2.3),[§II](https://arxiv.org/html/2607.06637#S2.p2.1),[§II](https://arxiv.org/html/2607.06637#S2.p3.6)\.
- \[21\]S\. Xie and Z\. Tu\(2015\)Holistically\-nested edge detection\.InProceedings of the IEEE international conference on computer vision,pp\. 1395–1403\.Cited by:[§III\-B](https://arxiv.org/html/2607.06637#S3.SS2.SSSx2.Px2.p2.9)\.
- \[22\]M\. Yuan and Y\. Lin\(2006\)Model selection and estimation in regression with grouped variables\.Journal of the Royal Statistical Society: Series B \(Statistical Methodology\)68\(1\),pp\. 49–67\.Cited by:[§II](https://arxiv.org/html/2607.06637#S2.p4.1)\.

![[Uncaptioned image]](https://arxiv.org/html/2607.06637v1/x9.jpg)Evgenii Kuriabovis a Ph\.D\. candidate in the Department of Statistics at The Pennsylvania State University\. His research interests include interpretable machine learning, counterfactual explanations, and optimization\-based methods for diagnosing model errors and assessing robustness\.![[Uncaptioned image]](https://arxiv.org/html/2607.06637v1/x10.jpg)David MillerDavid J\. Miller received his Bachelor’s from Princeton University in 1987, his M\.S\. from University of Pennsylvania, and his Ph\.D\. from UC Santa Barbara, all in electrical engineering\. Dr\. Miller joined Penn State’s EE Department in 1995\. He is a longtime researcher in machine learning, data compression, and statistical estimation\. He is an author of the 2023 Cambridge University Press book “Adversarial Learning and Secure AI”\. He received an NSF CAREER Award in 1996\. He was on the IEEE SP Society Conference Board from 2019\-2022 and is currently on the Management Board for IEEE Transactions on Artificial Intelligence\. He was Chair of the Machine Learning for Signal Processing Technical Committee, within the IEEE Signal Processing Society from 2007\-2009\. He was an Associate Editor for IEEE Transactions on Signal Processing from 2004\-2007\. He was General Chair for the 2001 IEEE Workshop on Neural Networks for Signal Processing\.![[Uncaptioned image]](https://arxiv.org/html/2607.06637v1/x11.png)Jia Li\(Fellow, IEEE\) is a Professor of Statistics and \(by courtesy\) Computer Science and Engineering at The Pennsylvania State University\. Her research interests include machine learning, artificial intelligence, probabilistic graph models, and image analysis\. She worked as a Program Director at the NSF from 2011 to 2013, a Visiting Scientist at Google Labs in Pittsburgh from 2007 to 2008, a researcher at the Xerox Palo Alto Research Center from 1999 to 2000, and a Research Associate in the Computer Science Department at Stanford University in 1999\. She received the MS degree in Electrical Engineering \(1995\), the MS degree in Statistics \(1998\), and the PhD degree in Electrical Engineering \(1999\), from Stanford University\. She was Editor\-in\-Chief for Statistical Analysis and Data Mining: The ASA Data Science Journal from 2018 to 2020\. She is a Fellow of the Institute of Electrical and Electronics Engineers and a Fellow of the American Statistical Association\.