- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes CertCF, a counterfactual explanation method for neural network classifiers. Offline, it uses a verification tool to build small regions around reference points that are guaranteed to be classified as the target class. Online, it answers a query by finding the closest point within the nearest regions, without calling the model again. Experiments on seven tabular datasets show 100% validity and strong robustness and plausibility, while proximity and sparsity remain behind model-based methods.
Critical strengths
1.Validity by construction. Every returned counterfactual lies inside a verified region, so it is guaranteed to reach the target class, and the method achieves 100% validity.
2.Reusable verification. The costly verification is done once offline and reused across queries, so query time does not depend on model size.
3.Each design choice is tested. Removing verification, adaptive shrinking, or top-k retrieval leads to lower validity, poorer coverage, or much slower queries, showing that each component is useful.
Critical weaknesses
1.Poor proximity. Counterfactual explanations aim for minimal changes, but certified regions are small balls around reference points, so CertCF requires large changes, with an L1 distance even larger than simply returning the nearest reference point.
2.Certified robustness is not evaluated. Certified robustness to input perturbations is claimed in the abstract and contributions, but this option is never enabled in the experiments, which report only empirical robustness, so its cost on proximity and success rate remains unknown.
3.Actionability is not evaluated. Restricting changes to selected features is claimed in the abstract and contributions, yet the Limitations section states that quality evaluation is limited to unconstrained tasks.
4.Missing comparison with verification-based methods. The paper motivates CertCF as a faster alternative to verification-based methods such as MACE and Maragno et al., but includes none of them in the experiments, so neither its speed advantage nor its quality relative to these methods is shown.
Questions for authors
(1)Quality is evaluated only on a two-layer network with 64 and 32 hidden units. How does proximity change as the network becomes deeper or wider?
(2)The paper only compares variants within the LiRPA family on regions of the same size. Since certification is done once offline, could more precise methods, such as PREMAP’s region splitting, certify larger regions and improve proximity?
Weakness 1
We agree that CertCF does not have the best proximity. It is designed as a trade-off between data-based and model-based methods (Figure 3a), and optimizing proximity alone yields points that barely cross the decision boundary.
The gap to NN is not caused by the sparsity penalty (without it, L1 is 7.54), and we attribute it to certification and to the finite atlas. In return, CertCF changes fewer features, has a larger post-hoc certified neighborhood and higher robustness, with similar plausibility, and never returns real records. GS and DiCE are closer but much less supported by the data. More anchors improve proximity. On synthetic data, going from 10 to 500 anchors lowers the mean L1 from 28.64 to 23.75 (still decreasing).
Weakness 2
The guarantee follows from the closed form of the eroded region (Eq. 11), and we will state it as a theorem with full proof. We measured its cost on the synthetic benchmark of Appendix F.2 (1,000 queries), and attacked the counterfactuals found without erosion at the same L1 radius (three seeds).
Success stays at 100%, at a cost of +1% L1 at δ = 0.2 and +23.7% at δ = 2 (23.75 without erosion), while without erosion attacks flip up to 31.5% of counterfactuals.
Weakness 3
We ran two experiments with the main-benchmark classifiers, queries and hyperparameters. In CertCF, constraints are hard constraints in the projection and hold by construction. With immutable features (sex and race on Adult and COMPAS, age on German Credit and Give Me Some Credit, 2,717 queries), CertCF loses one query (0.04 points of validity, paired L1 +0.73) and NN and FACE lose 0.44 and 0.55 points, with no constraint violations. Adding directional constraints on Give Me Some Credit (DebtRatio and credit utilization may only decrease, 1,000 queries), CertCF keeps 100% success (L1 +24.9%), NN and FACE drop to 89.0% and 88.0%, and GS and DiCE stay at 100% and 99.7%. We will add these results and update the Limitations section.
Weakness 4
We excluded verification-based methods because they cannot answer queries at interactive latency, which we consider essential in practice. MACE and Maragno et al. (2024) solve a new problem over the encoded network for every query. We ran the official MACE implementation on our benchmark classifiers (20 random queries per dataset). With a 10-second budget, all 140 attempts timed out in the first SMT call, so no quality comparison is possible, while CertCF answers every query in 0.35 s on average without model access. This reflects our setup, not MACE's general infeasibility. CertCF's median latency stays near 87.5 ms from 562 to 272,130 parameters and near 0.44 s on CIFAR-10 ResNets up to 532,480 ReLUs (Appendix F). The certified radius in our answer on proximity shows that pointwise validity does not imply a certified neighborhood.
Question 1
We analyzed the 25 networks of Appendix F.2 (depth 1 to 5, width 16 to 256, 1,000 queries each). From depth 1 to 5, mean L1 grows by only 5% (23.04 to 24.19) although the median region radius roughly halves (2.53 to 1.28). Width matters even less (+2% from 16 to 256). Success stays at 100%, and the trend holds without sparsity refinement. We will add these results to the appendix.
Question 2
We tested PREMAP2, which splits on ReLU states. Its branch conditions must be exported as input-space polytopes, which we did under a fixed budget (seven datasets, three repetitions). We compare it with the standard CROWN atlas (all anchors) and, to separate certification precision from anchor loss, with CROWN restricted to the anchors PREMAP2 retains (box domains, mean L1).
At equal atlas size (same anchors), PREMAP2 improves proximity on all datasets (0.5% to 13%), but the export budget loses many anchors, so it remains worse than the full CROWN atlas. On WBC a single anchor survives, so queries to the other class fail (PREMAP2 success 28.6%, 100% elsewhere).