Neighborhood Fidelity Curves for Detecting Fairwashed Explanations

A company can defend a biased model by publishing a simple "explanation": a short rule list or logistic regression that agrees with the model on most people but never mentions race or sex. This practice is called fairwashing. Existing detectors check that explanation only at the data points the auditor holds. They ask how often the explanation and the model agree on those points, and whether the disagreements pile up in one demographic group. An informed adversary can tune the explanation to pass exactly those checks. Adversarial robustness research went through the same failure. Reporting accuracy at one attack strength hid defenses that collapsed just past that point, and the field moved to full curves of performance versus attack strength.

This note proposes to audit explanations the same way. For each audited person, we search for the smallest plausible change to their record that makes the explanation and the model disagree. We then compare, group by group, the curve of how fast agreement breaks down as the allowed change grows. The intuition is simple. A rationalizing explanation matches the model at the audit points, but the model's hidden dependence on a protected attribute or its proxies must show up somewhere in the neighborhood. It should show up sooner for members of the affected group.

Core Claim

An honest surrogate explanation (one fit only for fidelity) and a fairwashed one can have the same agreement rate with the model on audit data. They should differ sharply in the geometry of their disagreement. A fairwashed surrogate must place its decision boundary away from the model's boundary along proxy directions, and for the disadvantaged group more than the other. The minimum distance to disagreement should therefore be systematically shorter for that group.

We claim that a group-stratified curve of this distance has two properties. First, it separates honest from fairwashed explanations at least as well as the current strongest pointwise test. Second, and this is the part that matters, it raises the price an adaptive adversary pays to evade detection, measured as the parity gap that leaks back into the surrogate.

The new element is not "plot fairwashing metrics against a budget." It is a specific audit statistic: a per-group margin curve on the explanation–model disagreement region, computed by a minimum-norm search. It is tested against adversaries who know the statistic.

Where this sits in prior work

The fairwashing papers motivate the gap. Fairwashing: the risk of rationalization builds rule-list surrogates (LaundryML) that trade fidelity against demographic parity. On Adult it reports a surrogate with 90.8% fidelity and unfairness of only 0.058. Characterizing the risk of fairwashing shows logistic-regression explainers that are 50% less unfair than the black box at 90–96% fidelity. These deceptions generalize from the audited group to held-out data with a fidelity drop under 1–2%, and transfer across architectures. Both papers draw fidelity–unfairness trade-off curves, but every evaluation is at static data points. Neither asks what happens a small step away from them.

The strongest detector is the constraint we must beat. Washing The Unwashable proves that a high-fidelity surrogate of an unfair model must distort fidelity unevenly across subgroups. Its detector, FRAUD-Detect, measures this as the KL divergence between per-group confusion matrices of surrogate versus model. The divergence rises by a factor of 4 or more, by more than 0.6 on COMPAS, and evading it forces parity gaps above 10% back into the surrogate. Our statistic is a direct extension of that idea from points to neighborhoods. The hypothesis is that the neighborhood version tightens the dilemma.

Evaluating Model Explanations without Ground Truth shows the other side. Its AXE test fits a k-NN predictor on an explanation's top features and reports 100% detection of adversarial fairwashing, versus 50% for sensitivity metrics. It is also a static, clean-data test. Robust ML Auditing using Prior Knowledge shows why static audit sets are exploitable. Platforms conceal 10–20 demographic-parity points before triggering detection, and public audit data offers no protection. Its curves are over audit sample size, not over perturbations, and it addresses a different attack: model swapping rather than explanation rationalization.

Security-curve work supplies the method. On Evaluating Adversarial Robustness argues for full accuracy-versus-budget curves and for treating anomalous curves as evidence of a weak attack rather than a secure model. Adversarial Robustness Curves defines margin curves: the distribution of the minimum perturbation that flips each correctly classified point. It also shows that non-linear models behave very differently under different distance measures. Benchmarking Adversarial Robustness on Image Classification documents rankings that flip as budget grows, for example TRADES versus PGD adversarial training on CIFAR-10. We borrow the margin-curve object and the warning about single operating points.

Fast Minimum-norm Adversarial Attacks (FMN) finds the smallest misclassifying perturbation in one pass by adaptively growing and shrinking a norm ball. It supports $L_0$ through $L_\infty$ (code). HO-FMN shows that default attack settings give overly optimistic results and that tuning loss, optimizer and step schedule matters. We adapt FMN from "flip the model" to "make surrogate and model disagree," and we tune it following HO-FMN.

Fairwashing explanations with off-manifold detergent constrains the design. It shows that model behavior off the data manifold can be manipulated almost freely, so honest models can disagree arbitrarily far from real data. Our probes must stay near the data's support. Otherwise the curve measures off-manifold noise rather than rationalization.

The Audit Statistic

The auditor holds a claimed-faithful surrogate $e$, query access to the black box $f$, and an audit set of records partitioned into protected groups $g$. For each audit point $x$ we compute

$$ r(x) = \min_{\delta \in C(x)} \|\delta\| \quad \text{subject to} \quad e(x+\delta) \neq f(x+\delta). $$

Here $C(x)$ is the set of plausible edits to record $x$: ranges respected, one-hot categories valid, and edits confined to a support region estimated from data. The norm mixes $L_2$ over standardized continuous features with an $L_0$ count of categorical changes. The sensitive attribute itself is excluded from $C(x)$ in the main statistic, so disagreement must be found through proxies.

The group disagreement curve $D_g(\epsilon)$ is the fraction of group-$g$ audit points with $r(x) \le \epsilon$. It is Göpfert et al.'s margin curve applied to the disagreement region. At $\epsilon = 0$ it equals one minus pointwise fidelity, so it contains the information global fidelity and FRAUD-Detect use and adds everything beyond it.

Simple surrogates of complex models disagree near boundaries even when honest. For that reason the auditor also trains a reference surrogate $e_0$ of the same class for fidelity alone, which is possible with query access. The test statistic is the excess group asymmetry over a radius range $[0, \bar\epsilon]$:

$$ S(e) = \int_0^{\bar\epsilon} \big|D_{a}^{e}(\epsilon) - D_{b}^{e}(\epsilon)\big| - \big|D_{a}^{e_0}(\epsilon) - D_{b}^{e_0}(\epsilon)\big| \, d\epsilon. $$

In this expression $a$ and $b$ are the two groups and superscripts indicate which surrogate is compared to $f$. The integral follows the expected-robustness summary of Ngnawe et al.. Integrating over radii rather than picking one prevents the adversary from tuning to a single known radius. That is the lesson of Dong et al.'s ranking inversions carried over to auditing.

For rule-list surrogates, $e$ is constant on axis-aligned boxes. The search runs FMN on $f$, pushing $f$ toward the label opposite to $e$'s current label while the edit stays inside the box. Separately, it enumerates the nearest box crossings exactly. The final radius is the smaller of the two. For logistic-regression surrogates, both models are differentiable and FMN applies directly with a disagreement loss. For non-differentiable black boxes (random forests, AdaBoost), we substitute a query-based boundary search. We report its sub-optimality separately rather than hiding it.

Research Program

The work has three parts.

Build the attack and validate its strength. We first implement the disagreement-seeking minimum-norm search and verify it as security evaluations require. Its radii should match or undercut a fixed-budget iterative search run on a grid of $\epsilon$ values. Its curves should be monotone and consistent across random restarts. Its hyperparameters are tuned under the HO-FMN protocol, and we measure how much the curves shift between default and tuned settings.

Characterize honest versus fairwashed curves. We then compare the curves of honest and fairwashed surrogates across datasets, black-box families and fairwashing strengths. We ask whether the protected group's curve rises faster and at which radii the separation is largest. We also ask whether the search recovers the proxy features that LaundryML-style surrogates shift attribution onto.

Attack the audit. Finally we play the adversary. The LaundryML and FaiRS objectives get an added penalty for neighborhood disagreement asymmetry, computed with the same search on the adversary's copy of the audit set. We trace how much apparent unfairness reduction the adversary can keep at each detection threshold.

The main output is an evasion frontier: hidden parity gap versus detector false-alarm rate on honest surrogates. It is directly comparable to the frontier implied by FRAUD-Detect.

Baselines

The naive reference is global fidelity with a fixed pass threshold. It declares an explanation acceptable if it agrees with the model on, say, 90% of audit points. The reported 90–96% fidelity of fairwashed explainers in Characterizing the risk of fairwashing predicts that this baseline fails. Including it anchors the scale of the problem. It is computed on the identical audit sets, and any method must beat its detection rate at matched false alarms.

The strongest existing competitor is FRAUD-Detect from Washing The Unwashable. It targets exactly this threat and is the only method with an evasion-cost guarantee. The reported figures to beat are divergence gaps of a factor of 4 or more, above 0.6 on COMPAS, and a forced parity gap above 10% for evading adversaries. We rerun it ourselves on the same black boxes, surrogates, audit splits and random seeds, and calibrate both detectors' thresholds on the same honest-surrogate pool. Beating it means one of two results. Either higher detection at equal false-alarm rate against the non-adaptive attacks, or, more importantly, a lower hidden parity gap on the adaptive-adversary frontier at every false-alarm level.

AXE from Evaluating Model Explanations without Ground Truth is the second strong competitor, with a reported 100% detection versus 50% for sensitivity metrics. It is applied to the feature importances each surrogate implies, with its k-NN size and top-$n$ choice tuned on the honest pool under the same budget as our radius range. Because its reported success is against non-adaptive attacks, the informative comparison is again under adaptive adversaries.

Two ablations isolate the key ingredient, the adversarial minimum-norm search. The first replaces the search with random plausible perturbations drawn at matched radii ("noisy FRAUD-Detect"). The second restricts the search to flipping only the sensitive attribute. A third ablation evaluates the curve at a single radius instead of the integral.

Why not just…?

Why not just measure the black box's demographic parity directly? Given query access and representative data, the auditor can see that outcomes are unequal. But unequal outcomes can be defended as driven by legitimate features, and the published explanation is exactly the artifact that makes that defense. The question FRAUD-Detect and this proposal answer is different: is the claimed mechanism a rationalization? Direct parity measurement cannot distinguish an honest explanation of a legitimately disparate model from a lying explanation of a discriminatory one. Our experiments include both cases.

Why not just run FRAUD-Detect on the audit points? It already works well against unaware adversaries, and we expect our statistic to roughly tie it there. Its weakness is that the adversary can concentrate fitting effort on known audit points. Its own paper shows evasion is costly but possible, at a parity gap above 10% on Adult and COMPAS. Whether moving to neighborhoods raises that cost is an empirical question, and the adaptive-adversary frontier settles it. If our frontier is not lower, the neighborhood statistic adds nothing and we will say so.

Why not just add random noise around each audit point? This is the real threat to the proposal. It is cheaper, needs no gradients, and may capture much of the effect if disagreement regions are large. Our argument is that an adversary who knows the noise distribution can train the surrogate to agree on noisy neighbors. An adaptive search picks directions at audit time along the specific proxies where the model's boundary bends, which the adversary cannot pre-cover without matching the model's mechanism. The random-perturbation ablation runs under both non-adaptive and adaptive adversaries. If it matches the minimum-norm statistic under adaptive attack, we will adopt the simpler test and report the search as unnecessary.

Why not just flip the sensitive attribute and check whether surrogate and model still agree? This single-direction counterfactual test misses the documented mechanism of fairwashing. Fairwashing: the risk of rationalization shows that attribution moves onto correlated neutral features, so the model can be insensitive to the attribute itself while depending on its proxies. The attribute-only ablation measures how much of the signal comes from proxies found by the search.

Why not just evaluate at one standard radius? Security evaluation shows that single operating points hide collapses (Adversarial Robustness Curves) and invert rankings (Dong et al.). In auditing, a known radius is also a target the adversary can optimize against. We test this directly with adversaries tuned to one radius, scored both at that radius and by the integral.

Proposed Experiments

Data and models. The datasets are Adult Income, COMPAS, Bank Marketing and Default Credit, following Characterizing the risk of fairwashing, with ACSEmployment added to test scale. Black boxes are deep networks, random forests and AdaBoost. Surrogates are CORELS rule lists via LaundryML and logistic regressions via FaiRS, each at several fidelity–fairness trade-off weights, plus honest fidelity-only surrogates over many seeds to form the null pool. To separate the legitimate-disparity case, we include black boxes trained without the sensitive attribute or its strongest proxies, whose honest explanations should pass.

Attack validity. Before any detection result is trusted, the disagreement search must produce radii no larger than a grid-based fixed-budget search at every $\epsilon$. It must also produce monotone curves and stay stable across restarts. For tree ensembles, where only query-based search is possible, we report the gap to a gradient-based search on a differentiable distilled copy.

Metrics. We report detection AUC over honest versus fairwashed surrogates, detection rate at 5% false alarm, and the adaptive evasion frontier of retained parity reduction versus false-alarm rate. We also report the overlap between features the search moves along and the proxies identified by attribution analysis, plus wall-clock cost per audited point.

Decisive checks. The proposal succeeds only if two conditions hold. The adaptive-adversary frontier of $S$ must lie below FRAUD-Detect's on at least Adult and COMPAS. The random-perturbation ablation must lie measurably above $S$ under the same adaptive attack.

Named failure modes. It fails, and we will report it as a negative result, in any of three cases. Honest surrogates show group asymmetry comparable to fairwashed ones even after the reference correction. Asymmetry appears only in off-support probes that the support constraint removes. Or cheap random neighbors match the search.