COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

Source: arXiv:2607.18119 · Published 2026-07-20 · By Kyungseon Lee, Hankyo Jeong, Kunwoong Kim, Kwanho Lee, Yongdai Kim

TL;DR

This paper addresses the problem of subgroup fairness in clustering when multiple sensitive attributes induce an exponential number of subgroups, many of which may be very small. Existing fair clustering methods struggle computationally and numerically in this scenario due to scaling issues and instability from small subgroup sizes. To overcome these challenges, the authors propose a subgroup-fairness gap metric based on the difference between cluster assignment probabilities overall and within each subgroup. They then derive an exact covariance-based surrogate of this gap, which they relax continuously for efficient gradient-based optimization, enabling scalable training with parallel assignment updates. The proposed algorithm, COVA-FC, simultaneously achieves fairness across many subgroups under multiple sensitive attributes. Furthermore, they extend the framework to also control marginal fairness (fairness on individual sensitive attributes) and higher-order marginal combinations via an augmented gap metric. Experiments on seven benchmark datasets spanning tabular, text, and image domains demonstrate that COVA-FC attains competitive clustering cost–fairness trade-offs with improved computational efficiency, numerical stability, and scalability compared to state-of-the-art baselines such as VFC, FCBC, FCA, and FairKM. The results support COVA-FC as a practical method for fair clustering under complex multi-attribute fairness constraints.

Key findings

• The covariance-based surrogate CR(A) exactly equals the subgroup fairness gap Δ(A) for any hard cluster assignment (Theorem 2.1).
• Relaxing cluster assignments to soft assignments and optimizing a continuous relaxation of CR(A) enables efficient gradient-based optimization with instance-wise decomposability.
• COVA-FC runs 3.2× faster than VFC on a large dataset with over 1.6 million samples while achieving lower subgroup fairness gaps.
• COVA-FC avoids numerical instability seen in VFC that arises from inverse subgroup-cluster masses in sparse subgroup settings.
• On benchmark datasets (Adult, Dutch, Bank, Civilcomments), COVA-FC achieves substantially lower subgroup fairness gaps at similar or slightly increased clustering costs compared to baselines (e.g., Adult: SP 0.0002 vs 0.0158 for VFC).
• Incorporating marginal fairness constraints (1st and 2nd order) into COVA-FC significantly reduces marginal fairness gaps MP(1) and MP(2) with only mild trade-offs in subgroup fairness.
• COVA-FC's per-iteration assignment update parallelizes efficiently on GPU, with matrix updates scaling sub-linearly with dataset size compared to a linear-scaling loop baseline.
• LP-based methods (FCA, FCBC, FRA) and FairKM scale poorly with subgroup count and fail computationally on large or high-dimensional datasets; COVA-FC avoids these issues.

Threat model

Non-adversarial fairness setting, where the goal is to reduce statistical dependence between cluster assignments and sensitive subgroups defined by multiple sensitive attributes. The adversary is not explicitly modeled — the problem focuses on algorithmic fairness as an optimization constraint rather than robustness to malicious manipulation.

Methodology — deep read

The paper tackles subgroup-fair clustering under multiple binary sensitive attributes, resulting in 2^q intersecting subgroups. The threat model is not adversarial but focuses on achieving statistical independence of cluster assignments from sensitive subgroups, ensuring fairness. Data includes seven benchmark datasets across tabular, text, and image modalities. Each dataset is split into train/test sets; detailed preprocessing is in Appendix D.1 but involves standard feature extraction including pretrained ResNet features for images.

The fairness objective defines the subgroup-fairness gap Δ(A) as the maximum over subgroups of weighted total variation differences between overall cluster assignment probabilities and subgroup-conditional assignment probabilities. Direct optimization is difficult because Δ(A) depends on sums over assignments, making parallel updates impossible.

To overcome this, they show Δ(A) = CR(A), a covariance-based surrogate that measures maximum empirical covariance between cluster assignment scores and subgroup membership indicators. CR(A) is still discrete and non-differentiable due to hard assignments and max over subgroups.

They introduce two continuous relaxations: 1) soft cluster assignment vectors A_i in the simplex replacing hard assignments, making objectives differentiable in A; 2) a convex combination of subgroup indicators weighted by vector v over observed subgroups, softening the max over subgroups and stabilizing optimization. Together these yield a differentiable surrogate CR(A) amenable to gradient-based optimization.

They extend the subgroup-fairness gap to incorporate marginal fairness, defining separate marginal fairness gaps on individual sensitive attributes and higher-order subsets. The subgroup-marginal gap includes all these constraints simultaneously in a unified framework.

The COVA-FC algorithm optimizes clustering cost plus λ times the smooth CR(A) fairness penalty by alternating steps: fixing cluster assignments to optimize adversarial variables (β,v) identifying worst-case subgroup dependence direction, then updating soft cluster assignments A and cluster centroids μ by gradient descent. The soft assignment update decomposes over instances and supports parallel GPU implementation.

They evaluate on seven datasets, comparing against baselines FCBC, VFC, FCA, FairKM, and FRA using metrics K-means cost, subgroup fairness gap (SP), and marginal fairness gaps (MP). They run extensive ablations on the continuous relaxations and hardness of different subproblems. Runtime, scalability, and stability measures are included. Several experiments test scaling to millions of samples and high-dimensional image features.

The codebase and detailed hyperparameter settings are discussed in appendices, but no public code release is mentioned. Datasets are public or well-known benchmarks.

Technical innovations

• An exact covariance-based surrogate CR(A) that precisely equals the subgroup fairness gap Δ(A), enabling principled optimization.
• Continuous relaxation of both cluster assignments (to soft cluster membership) and subgroup max operator (to a convex combination) for stable gradient-based fairness optimization.
• Extension of subgroup-fairness gap to joint subgroup and marginal fairness via a unified subgroup-marginal-fairness gap metric.
• A scalable alternating optimization algorithm (COVA-FC) with parallelizable per-instance assignment updates, improving computational efficiency over LP-based and penalty-based baselines.

Datasets

• Adult — ∼48,842 samples — UCI repository
• Dutch — not specified — benchmark tabular
• Bank — not specified — benchmark tabular
• Civilcomments — not specified — text dataset
• Communities — not specified with q =18 sensitive attributes, 1,180 subgroups — public benchmark
• ACSIncome — 1,664,500 samples — public census-derived dataset
• CelebA — not specified number of images — public image recognition dataset

Baselines vs proposed

• VFC: lowest SP = 0.0158 (Adult) vs COVA-FC: 0.0002
• VFC: runtime 48.25s (Dutch) vs COVA-FC 30.24s
• FairKM: runtime 292.26s (Dutch) vs COVA-FC 30.24s
• FCA: runtime 226.42s (Dutch) vs COVA-FC 30.24s
• FCBC: runtime 179.26s (Dutch) vs COVA-FC 30.24s
• FRA: runtime 64.29s (Dutch) vs COVA-FC 30.24s
• COVA-FC achieves 3.2× speedup over VFC on ACSIncome dataset with over 1.6 million samples
• Subgroup-marginal variant reduces MP(1) and MP(2) significantly compared to subgroup-only variant with small SP trade-offs

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.18119.

Fig 1: Comparison of trade-offs between subgroup-fairness gap (SP) and cost on (left to right)

Fig 2: Per-iteration runtime of the

Fig 3: Comparison on Communities between subgroup-only COVA-FC and subgroup-marginal

Fig 4: Trade-offs between MP(1) and cost on (left to right) Adult, Dutch, Civilcomments, and

Fig 5 (page 8).

Fig 6 (page 8).

Fig 7 (page 8).

Fig 8 (page 8).

Limitations

• The method assumes binary sensitive attributes; extension to multi-valued attributes is mentioned but not experimentally validated.
• No adversarial robustness evaluation against strategic subgroup manipulation or poisoning attacks.
• The quality of fairness depends on choice of λ and W subsets, which may require manual tuning.
• The algorithm is developed for K-means clustering; extension to other clustering paradigms is left as future work.
• Code release and full reproducibility details are not provided, limiting immediate practical adoption.
• Evaluation mainly focuses on subgroup fairness metrics; downstream task impact or user-centric fairness evaluations are not studied.

Open questions / follow-ons

• Can the covariance-based surrogate framework be adapted to other clustering methods such as hierarchical or mixture models?
• How can this approach handle multi-valued or continuous sensitive attributes more naturally?
• What are the implications of subgroup fairness constraints on downstream supervised learning tasks or causal inference?
• Can the method be extended or combined with adversarial robustness techniques to handle strategic data manipulation?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, this work highlights how to enforce nuanced fairness constraints in unsupervised user or behavior clustering when multiple sensitive attributes define numerous small subgroups. The exact covariance-based surrogate enables scalable fairness-aware clustering applicable even when the subgroup space grows exponentially, a setting common when profiling users or detecting fraud across multiple demographic or behavioral signals. Efficient parallel updates and stability in sparse subgroup contexts are critical when working on large-scale real-world bot datasets with imbalanced protected groups. The extension to jointly control marginal fairness addresses practical fairness concerns beyond fine-grained subgroup definitions. While not directly a CAPTCHA evasion defense, the algorithmic techniques for scalable subgroup fairness could inspire methodologies to cluster or segment user sessions while avoiding bias — a relevant issue in ensuring equitable bot detection models. The covariance surrogate concept may also help design auxiliary fairness regularizers in learnable detection or challenge-response systems.

Cite

@article{arxiv2607_18119,
  title={ COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering },
  author={ Kyungseon Lee and Hankyo Jeong and Kunwoong Kim and Kwanho Lee and Yongdai Kim },
  journal={arXiv preprint arXiv:2607.18119},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.18119}
}

Read the full paper

• arXiv:2607.18119 (abstract)
• arXiv:2607.18119 (PDF)