COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering

• URL: http://arxiv.org/abs/2607.18119v1
• Date: Mon, 20 Jul 2026 16:14:13 GMT
• Title: COVAriance-Induced Fairness Gap Penalty for Subgroup-Fair Clustering
• Abstract summary: We propose a new fair clustering algorithm, COVA-FC.<n>We show that COVA-FC achieves competitive cost-fairness trade-offs and improves computational efficiency over existing baselines in both subgroup and higher-order marginal settings.<n> Experiments on benchmark datasets show that COVA-FC achieves competitive cost-fairness trade-offs and improves computational efficiency over existing baselines in both subgroup and higher-order marginal settings.
• Score: 9.978074549317652
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fair clustering aims to make cluster assignments independent of sensitive attributes, but this goal becomes challenging when multiple sensitive attributes jointly define many subgroups. In such settings, directly extending existing fair clustering algorithms is computationally expensive or numerically unstable, especially when the number of subgroups grows exponentially and some subgroups contain only a few instances. To address these challenges, we define a subgroup-fairness gap for clustering and derive a covariance-based surrogate that exactly matches this gap. We then introduce a continuous relaxation of the surrogate, enabling efficient gradient-based optimization and yielding our proposed algorithm, COVA-FC. We also show that subgroup fairness alone does not imply marginal fairness, and extend our framework to capture a subgroup-marginal-fairness gap. Experiments on benchmark datasets show that COVA-FC achieves competitive cost-fairness trade-offs and improves computational efficiency over existing baselines in both subgroup and higher-order marginal settings.

Related papers

• Imputation Meets Clustering: Exploiting Latent Subgroup Structure for Missing Data Recovery [52.29866804948133]
  We propose CAGI (Cluster-Aware Generative Imputation), a framework that reformulates clustering and imputation as a mutually reinforcing co-optimization process.<n>Experiments on 14 benchmark datasets with 15 representative baselines demonstrate the superiority of CAGI.
  arXiv  Detail & Related papers  (2026-07-08T02:50:02Z)
• UniFair: A unified fair clustering approach based on separation and compactness [1.918113642696782]
  We propose UniFair, a unified framework that jointly optimize separation fairness and social fairness.<n>We develop gradient-based optimization procedures for separation-fair and unified k-means objectives.<n>Experiments show that UniFair reduces both boundary-related and cost-based group disparities with only a modest increase in clustering loss.
  arXiv  Detail & Related papers  (2026-06-03T12:00:22Z)
• Doubly-Regressing Approach for Subgroup Fairness [14.327714719028924]
  As the number of sensitive attributes grows, the number of subgroups increases.<n>This creates heavy computational burdens and data sparsity problem.<n>We develop a novel learning algorithm for subgroup fairness.
  arXiv  Detail & Related papers  (2025-10-24T02:04:44Z)
• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• Fair Clustering via Alignment [12.12426896501947]
  Algorithmic fairness in clustering aims to balance proportions of instances assigned to each cluster with respect to a given sensitive attribute.<n>We propose a new fair clustering algorithm based on a novel decomposition of the fair $K$-means clustering objective function.
  arXiv  Detail & Related papers  (2025-05-14T04:29:09Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Outlier-Robust Group Inference via Gradient Space Clustering [50.87474101594732]
  Existing methods can improve the worst-group performance, but they require group annotations, which are often expensive and sometimes infeasible to obtain. We address the problem of learning group annotations in the presence of outliers by clustering the data in the space of gradients of the model parameters. We show that data in the gradient space has a simpler structure while preserving information about minority groups and outliers, making it suitable for standard clustering methods like DBSCAN.
  arXiv  Detail & Related papers  (2022-10-13T06:04:43Z)
• Fair Labeled Clustering [28.297893914525517]
  We consider the downstream application of clustering and how group fairness should be ensured for such a setting. We provide algorithms for such problems and show that in contrast to their NP-hard counterparts in group fair clustering, they permit efficient solutions. We also consider a well-motivated alternative setting where the decision-maker is free to assign labels to the clusters regardless of the centers' positions in the metric space.
  arXiv  Detail & Related papers  (2022-05-28T07:07:12Z)
• Focus on the Common Good: Group Distributional Robustness Follows [47.62596240492509]
  This paper proposes a new and simple algorithm that explicitly encourages learning of features that are shared across various groups. While Group-DRO focuses on groups with worst regularized loss, focusing instead, on groups that enable better performance even on other groups, could lead to learning of shared/common features.
  arXiv  Detail & Related papers  (2021-10-06T09:47:41Z)
• Feature-based Individual Fairness in k-Clustering [14.847868952138795]
  We consider the problem of clustering a set of points while ensuring fairness constraints. We introduce a new notion of individual fairness in k-clustering based on features that are not necessarily used for clustering.
  arXiv  Detail & Related papers  (2021-09-09T20:42:02Z)
• You Never Cluster Alone [150.94921340034688]
  We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation. We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one. By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
  arXiv  Detail & Related papers  (2021-06-03T14:59:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.