Fair clustering algorithms come with a promise: a certificate that the solution is within a constant factor of the best possible clustering that also respects demographic balance. A backdoor attack is the opposite kind of promise: a model that behaves correctly on audited data and misbehaves only when a specific trigger pattern appears. This proposal argues that these two literatures meet at an unexamined blind spot. Every approximation guarantee in fair clustering — the 3-approximation of fairlet-based fair center Fair Clustering Through Fairlets, the $(5 + O(\epsilon))$ ratio of Relax-and-Merge for fair $k$-means Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems — is stated relative to the input the algorithm receives. If an adversary adds a small fraction of trigger-carrying points to that input, the guarantee still holds trivially, because the "optimum" it is measured against is the optimum of the poisoned instance. Nothing in the theory protects the cost or the balance of the clustering computed on the clean data. We call this the poisoning gap, and we propose to characterize it, attack through it, and close it.
The empirical side of the threat is already documented. BadFair shows that a backdoor conditioned on demographic group can pass standard fairness audits while inflicting poisoned bias above 45.5% with an average targeted attack success rate over 85% and only about 1.2% accuracy loss, and that standard backdoor detectors catch it in less than 58% of cases instead of the roughly 95% they achieve on ordinary backdoors BadFair: Backdoored Fairness Attacks with Group-conditioned Triggers. Xu et al. show the complementary point on the defense side: enforcing fairness constraints shrinks the hypothesis space and makes fair classifiers more fragile under poisoning, so sanitization methods built for unconstrained models fail Towards Fair Classification against Poisoning Attacks. What is missing entirely is the algorithmic-theory view: nobody has asked what a poisoned input does to a provable fair clustering pipeline, and nobody has designed one that survives.
Core Claim
We formalize the blind spot with a poison-robust approximation ratio. Let $P$ be the clean point set with sensitive attributes, let $B$ be poisoned points with $|B| \le \epsilon |P|$ injected by the adversary, and let $\mathrm{OPT}_{\mathrm{fair}}(P)$ denote the cost of the optimal fairness-constrained clustering of the clean data. For a fair clustering algorithm $A$, define
$$ \rho_\epsilon(A) \;=\; \sup_{P,\;B:\,|B|\le\epsilon|P|} \; \frac{\mathrm{cost}\big(A(P \cup B)\big)}{\mathrm{OPT}_{\mathrm{fair}}(P)} . $$
A standard $\alpha$-approximation bounds the numerator only against $\mathrm{OPT}_{\mathrm{fair}}(P \cup B)$, which the adversary controls. Our core claim has two halves. First, an attack construction: for algorithms that enforce exact demographic balance in every cluster — the fairlet regime of Fair Clustering Through Fairlets — $\rho_\epsilon$ is unbounded. The adversary plants a tight cluster of $\epsilon$-fraction trigger points inside one demographic group, arbitrarily far from all clean data; exact balance then forces the min-cost-flow fairlet decomposition to drag nearest points of the other group across that arbitrary distance, inflating both the poisoned optimum and the algorithm's cost without limit. Second, a matching defense: if the algorithm is allowed to discard up to $O(\epsilon)$ mass per group and satisfy balance only up to slack, a trimmed version of the LP assignment step of Relax and Merge achieves a bounded $\rho_\epsilon$ — a constant-factor robust guarantee — conditional on the empirical fact, established by activation clustering Detecting Backdoor Attacks on Deep Neural Networks by Activation Clustering and by the shortcut behavior underlying cumulative-entropy filtering Anti-Backdoor Coreset Selection via Cumulative Entropy, that trigger points concentrate in tight, low-diversity pockets rather than spreading like clean data. The deeper conceptual payoff is a rebirth of the approximation-existence gap in an adversarial form: under poisoning, exact fairness exists but cannot be computed robustly at any finite ratio, while approximate fairness admits a robust constant-factor algorithm. This mirrors the structure of the classical gaps in fair division, such as the gap between the $(4+\epsilon)$-approximation algorithm and the $4/3$ lower bound for weighted chore allocation Weighted Maxmin Fair Share Allocation of Indivisible Chores and the barriers broken in MMS approximation Breaking the 3/4 Barrier for Approximate Maximin Share, but the gap here is between robustness levels rather than approximation factors.
Research Program
The program has three components. The theory component proves the two halves of the core claim: the unboundedness construction for exact-balance fairlet clustering (including the min-cost-flow and bipartite-matching variants of Fair Clustering Through Fairlets and the greedy-swap pipeline of Fair k-Center Clustering for Data Summarization), and the robust upper bound for the trimmed-LP algorithm, where the analysis must control how the discarded mass perturbs both the cost bound (via the $\epsilon$-approximate centroid set machinery of Relax and Merge) and the balance guarantee. We will also probe whether the integrality-gap phenomena that make colorful $k$-center hard Fair colorful k-center clustering sharpen the lower bound when the adversary spreads poison across many groups.
The algorithm component builds the trimmed fair clustering pipeline: an LP over the approximate centroid set in which each group's assignment mass carries a discard budget proportional to $\epsilon$, followed by center adjustment and the vanilla $k$-means merge. The discard budget is per-group, not global, which is what distinguishes this from generic outlier removal and what addresses the tension documented in Gap 4 of the literature: global clustering defenses such as activation clustering and incompatibility clustering Incompatibility Clustering as a Defense Against Backdoor Poisoning Attacks risk conflating legitimately underrepresented minority samples with poisoned pockets, because both look like small isolated clusters. A per-group budget with a balance-slack correction is designed so that trimming poison from a majority group cannot silently trim minorities.
The evaluation component adapts the empirical attack machinery of the backdoor literature to combinatorial clustering. BadFair's group-conditioned triggers BadFair were built for text classifiers; we port the construction to tabular fair-clustering benchmarks using rare-value triggers in the spirit of the Unicode-homograph approach of Hidden Backdoors in Human-Centric Language Models, and we use the placement-selection ideas of FUS++ Explore the Effect of Data Selection on Poison Efficiency in Backdoor Attacks — which achieved an attack success rate of 0.923 versus 0.871 for random placement at a 1% poisoning ratio — to build an adaptive adversary that knows our defense.
Proposed Experiments
Experiment 1 validates the attack theory. On the Adult census data (25,000 records, as used in Fair k-Center Clustering for Data Summarization), Bank, and Diabetes, we inject $\epsilon \in \{1\%, 5\%, 10\%\}$ group-conditioned trigger points at controlled distances, matching the poisoning ratios used in the poisoning literature (10% in Towards Fair Classification against Poisoning Attacks, at most 5% in Towards Poisoning Fair Representations). We measure the empirical robust ratio — achieved cost divided by clean-data fair optimum — for the fairlet pipeline and Relax-and-Merge. The prediction is that inflation grows linearly in the trigger-cluster distance for exact-balance methods, while remaining flat for our trimmed variant. We note that no reported result found on Lacuna for a numeric clustering cost of Relax-and-Merge on Adult or Bank; the paper reports only that it "consistently achieved the lowest clustering cost compared to major baselines," so we will re-run it ourselves to obtain clean-data reference costs.
Experiment 2 is the defense comparison under a fixed adaptive attack, described under Baselines below. Metrics are the empirical robust ratio, balance violation, center displacement against the clean solution, and the fraction of poisoned points surviving into the final clustering.
Experiment 3 tests the fairness tension directly: on demographically imbalanced splits, we run an adversary that camouflages poison as minority-group clusters (the FUS++-informed adaptive placement) and measure how often each defense discards legitimate minority samples. This is where we expect global defenses to fail and the per-group budget to matter.
Experiment 4 measures runtime, since LP-based fair clustering is known to scale poorly Relax and Merge; our trimming only relaxes mass constraints, so overhead should be negligible relative to the LP solve, and we will compare against the speed profile that made the greedy fair $k$-center approach attractive (under 0.01 seconds versus 230 seconds for the prior state of the art on a 250-point instance, per Fair k-Center Clustering for Data Summarization).
Baselines
The do-nothing reference is the strongest provable fair clustering pipeline run on poisoned data with no defense: the fairlet decomposition of Fair Clustering Through Fairlets and the Relax-and-Merge framework Relax and Merge, which holds the best published approximation ratio for fair $k$-means ($(5 + O(\epsilon))$ with a PTAS) and the best empirical cost on these very benchmarks. This is the strongest competitor on the theoretical question because its guarantee is exactly the one our robust ratio is defined against; we run it with identical data, identical $k$ and balance parameters, and identical compute, and beating it means holding the empirical robust ratio at a bounded constant while its ratio grows with attack distance. A naive reference point is pre-filtering by plain 2-means on raw features before fair clustering; activation clustering found this separates poison at only about 58% accuracy on MNIST raw inputs, versus nearly 100% on latent activations Detecting Backdoor Attacks on Deep Neural Networks by Activation Clustering, so we expect it to either leave trigger pockets intact or gut minority clusters. The strongest existing defenses we adapt are incompatibility clustering via Inverse Self-Paced Learning Incompatibility Clustering as a Defense Against Backdoor Poisoning Attacks, which reduced attack success rate below 1% in 134 of 165 tested scenarios with only about a 2% clean accuracy drop and beat activation clustering 22 to 5 on dirty-label attacks, and cumulative-entropy coreset selection Anti-Backdoor Coreset Selection via Cumulative Entropy, which reports a defense effectiveness rate over 95% on CIFAR-10 and 97% on Tiny-ImageNet with a coreset of roughly 55% of the data. These are the best published numbers in the field, but they were earned on neural image classifiers, not combinatorial fair clustering; we port them as pre-filters on feature representations, give them the same tuning budget and poisoned data as our method, and count ourselves as beating them only if we match their poison-suppression while additionally holding the robust ratio and per-group balance that they do not track at all. Finally, two ablations isolate the key ingredient: our trimmed LP with fairness constraints removed (pure robust clustering, testing whether robustness comes from trimming or from the fairness-aware budget structure) and fairness with trimming removed (which collapses back to Relax-and-Merge and should reproduce the unbounded inflation).
Why not just…?
Why not just remove outliers first and then cluster fairly? This is Alternative 1, and the literature gives three reasons to doubt it. Clustering raw inputs separates poisoned from clean samples at only about 58% accuracy on MNIST Detecting Backdoor Attacks on Deep Neural Networks by Activation Clustering; poisoned data is not always an outlier in feature space Incompatibility Clustering as a Defense Against Backdoor Poisoning Attacks; and sanitization designed for standard models failed badly when the downstream model was fairness-constrained Towards Fair Classification against Poisoning Attacks. Moreover, fixing fairness after unconstrained clustering fails structurally because fair clustering violates the nearest-center property Fair Clustering Through Fairlets. Still, we take the threat seriously and run this pipeline as the naive baseline in Experiment 2; if it matches our robust ratio, our contribution reduces to an outlier detector and the proposal should be judged accordingly.
Why not just apply post-hoc backdoor defenses like fine-pruning? Post-hoc model surgery targets neural weights: fine-pruning exploits dormant neurons that clean data never activates Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks. A min-cost-flow fairlet decomposition or an LP assignment has no weights to prune and no dormant neurons; the attack surface is the input combinatorics, so the defense must live there. Empirically, post-hoc defenses are also weakening: FUS++-optimized attacks are reported as more resilient against fine-pruning than random attacks Explore the Effect of Data Selection on Poison Efficiency in Backdoor Attacks, and BadFair already slips past standard backdoor detectors in more than 42% of cases BadFair. Our threat model simply does not admit these tools, and we say so in the proposal rather than arguing around it.
Why not just reduce batch size to drown poison gradients in noise? The tipping-point theory of Towards Poisoning Fair Representations shows small batches raise the poisoning ratio needed to corrupt gradient-matched representation learning, and that is a real result. But it applies to stochastic gradient training; our pipeline's decisions are made by min-cost flow and an LP, which have no batches, no learning rate, and no gradient noise to exploit. The same limitation is documented for other non-gradient attack surfaces, such as in-context-learning backdoors Universal Vulnerabilities in Large Language Models: Backdoor Attacks for In-context Learning. Where a learned surrogate does appear in our pipeline (if embeddings are used for trimming), we will include a small-batch variant as a cheap baseline so the comparison is honest rather than assumed.
Decisive Checks
The proposal stands or falls on three outcomes. First, Experiment 1 must show cost inflation for exact-balance pipelines that grows with attack distance while our trimmed variant stays flat — the empirical signature of the poisoning gap. Second, under the FUS++-informed adaptive attack, our defense must hold the robust ratio within roughly a factor of two of its clean-data cost at up to 10% poisoning while the strongest adapted defense baseline either leaks trigger pockets into the clustering or discards legitimate minority samples at a measurably higher rate. Third, the theory must deliver what the empirical defenses explicitly lack: Zhao and Wressnegger acknowledge that cumulative-entropy coreset selection has no formal foundation or approximation guarantee Anti-Backdoor Coreset Selection via Cumulative Entropy; a proved bounded $\rho_\epsilon$ for trimmed fair clustering would be the first guarantee of this kind, and would turn the approximation-existence gap from a purely theoretical fixture into a security-relevant boundary between what fair algorithms can survive and what they cannot.
References
- Fair Clustering Through Fairlets
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
- BadFair: Backdoored Fairness Attacks with Group-conditioned Triggers
- Towards Fair Classification against Poisoning Attacks
- Detecting Backdoor Attacks on Deep Neural Networks by Activation Clustering
- Anti-Backdoor Coreset Selection via Cumulative Entropy
- Weighted Maxmin Fair Share Allocation of Indivisible Chores
- Breaking the 3/4 Barrier for Approximate Maximin Share
- Fair k-Center Clustering for Data Summarization
- Fair colorful k-center clustering
- Incompatibility Clustering as a Defense Against Backdoor Poisoning Attacks
- Hidden Backdoors in Human-Centric Language Models
- Explore the Effect of Data Selection on Poison Efficiency in Backdoor Attacks
- Towards Poisoning Fair Representations
- Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks
- Universal Vulnerabilities in Large Language Models: Backdoor Attacks for In-context Learning