Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the computational challenges of achieving subgroup-fair clustering in the presence of multiple sensitive attributes by introducing a covariance-based surrogate for the subgroup-fairness gap. The proposed algorithm, COVA-FC, leverages a continuous relaxation of this surrogate to enable efficient gradient-based optimization, significantly improving computational efficiency while maintaining competitive cost-fairness trade-offs. Experimental results demonstrate that COVA-FC not only achieves better performance in subgroup fairness but also extends to higher-order marginal fairness settings, highlighting the nuanced relationship between subgroup and marginal fairness.
Subgroup fairness in clustering can be achieved efficiently without sacrificing performance, thanks to a novel covariance-based approach that reveals the hidden complexities of fairness gaps.
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.