- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper introduces COVA-FC, a surrogate-based approach to subgroup fair centroid-based clustering with multiple sensitive attributes. The authors define a subgroup-fairness gap and optimize a continuous relaxation of it together with the clustering cost in a covariance-based surrogate. COVA-FC is extended to account for subgroup and margin fairness simultaneously.
Critical strengths
S1: The paper proposes a covariance-based surrogate that they show exactly realizes the subgroup-fairness gap for any hard cluster assignment.
S2: The paper provides a detailed complexity analysis and runtime experiments.
Critical weaknesses
W1 (Context): Although the paper’s introduction discusses LP-based methods, VFC, and FairKM briefly, it lacks positioning within the broader context of related works. This includes the relation to other notions of fairness, e.g., group-level fair clustering methods, other clustering paradigms, or other works that target subgroup fairness. This makes it difficult to assess novelty.
W2 (Experiments / Rare Subgroups):
- The paper identifies rare subgroups as one of the main limitations of current works. However, the experiments do not sufficiently isolate or test the algorithm on these specific scenarios, and it is not clear to me how the metric reflects that, since it is weighted by the size of the subgroup . Comparisons for the Communities dataset, which is the most interesting for the rare subgroups claim, are limited to the Appendix.
- The reported metric in the main paper (supgroup fairness gap) is the quantity that COVA-FC optimizes, while the competitors optimize other objectives, which makes it difficult to separate algorithmic improvement from the experimental design. The gaps between the algorithms are often very small (0.0001 in Table 6), and it remains unclear to me how these differences relate to practical examples.
- Table 2 compares only one competitor, excludes Communities, and uses L_2-normalized data. This raises the question of how other competitors perform in this setting and how much the preprocessing affects the results of the method.
Minor Comments:
- Figure 2 is very small, making it difficult to read. Since there is enough space, I suggest adding the legend once at the top across all subplots and providing more space for the actual content.
Questions for authors
Q1: How can we interpret the very small differences, sometimes 0.0001, in the fairness metric (Table 6)? What difference would this make in practice?
Q2: How do the baselines compare regarding the subgroup-marginal fairness gap as they are?
Q3: How is the unfair clustering in the results determined? Is it a vanilla k-means clustering?
Q4: How do the results change across different values for K? The appendix includes results for K=5 and K=20, but only for COVA-FC and not for competitors, and are thus difficult to set into context.
4 comments
Questions
[Q1] Practical meaning of a 0.0001 difference.
See Weakness 2-2.
[Q2] Baselines on marginal fairness gaps.
- Section 5.3 now includes all baselines on
Communities(Figure 4): our subgroup-only variant attains lower SP in most cases and the subgroup-marginal variant lower and , while VFC and FRA fail at strict levels and FCBC needs much higher cost. Appendix D.2 (Figure 5) covers the other datasets.
[Q3] What is the Unfair baseline?
- The Unfair baseline is standard -means, as stated in Section 5.1 and Appendix D.1.
[Q4] Results for other with competitors.
- We added all baselines on
Adultat (Appendix E.5, Figure 23); Cova-FC remains competitive for all three , with lower cost than FRA and FCBC at comparable SP.
Thank you for the rebuttal and the additional experiments, which resolved some of my concerns. However, some points remain.
(W2-2) SP is the quantity COVA-FC optimizes, while the baselines optimize different proxies. The Balance results are mixed: COVA-FC has the highest SB on three of four datasets and the highest whole-data ratio only on Adult. Since Figure 2 shows that COVA-FC needs higher cost than VFC, FRA, and FCBC at the same SB, I share VFmB's concern that part of the benefit comes from the aligned evaluation.
(Q1) My question about practical implications remains unanswered. I agree the standard deviations show the gaps are not noise, but it is still unclear what these gaps mean in practice when cost is taken into account, and what trade-off would be acceptable.
I will keep my scores.
Thank you very much for carefully reviewing our rebuttal and additional experiments, and for providing further feedback despite the short discussion period. Below, we provide clarifications on your remaining concerns.
(Reply - W2-2) SP is the quantity COVA-FC optimizes, while the baselines optimize different proxies. The Balance results are mixed: COVA-FC has the highest SB on three of four datasets and the highest whole-data ratio only on Adult. Since Figure 2 shows that COVA-FC needs higher cost than VFC, FRA, and FCBC at the same SB, I share VFmB's concern that part of the benefit comes from the aligned evaluation.
-
Shared concern with Reviewer VFmB. Since this concern is shared with Reviewer VFmB, we answer it in detail in our follow-up response to Reviewer VFmB (Reply - Q1). In short, the main benefit of Cova-FC is efficient optimization with many subgroups; the gap-based baselines optimize gaps of the same kind, and all these measures, including Balance, share the same fully fair solutions (Table R8); and most baselines are designed for one multi-category attribute, so we run them with each subgroup as a category, where they often reduce SP less.
-
Balance results. We agree that Cova-FC does not always achieve the best cost–Balance trade-off. In particular, FRA and FCBC can achieve the same SB at lower clustering cost in some settings (Figure 2), and slightly better trade-offs on datasets other than
Adult(Figure 8). With many small subgroups, Balance is unstable: a subgroup with fewer than members must miss some cluster and sets it to zero, and FRA, which imposes it, fails to solve its LP under strict constraints onCommunities(Section 5.3); this is why SP is our main metric. Even so, Cova-FC achieves the highest subgroup Balance onAdult,Civilcomments, andBank, despite not directly optimizing Balance.
(Reply - Q1) My question about practical implications remains unanswered. I agree the standard deviations show the gaps are not noise, but it is still unclear what these gaps mean in practice when cost is taken into account, and what trade-off would be acceptable.
-
Practical benefits of ours in presence of many subgroups. One of our main motivations and goals is to achieve high level of subgroup fairness more efficiently and stably, especially when the number of subgroups is large. On datasets with few subgroups, such as
DutchandBank, the differences between Cova-FC and baselines can be small. However, these differences become more pronounced onCommunitieswith 1,180 subgroups, where Cova-FC achieves SP , for FairKM, for VFC, for FCBC, and for FRA (Table R6). The advantage is thus largest with many subgroups: LP-based methods can take hours or fail under strict fairness (our follow-up response to Reviewer VFmB, Reply - Q1), whereas the runtime of Cova-FC onFairFacegrows by only 3.5% from 8 to 126 subgroups (Reviewer Ewqn, Table R4). -
Why the difference in SP is important in practice. SP measures how much the subgroup counts in each cluster differ from the expected counts: . For example, when , SP values of and correspond to total count discrepancies of 6 and 12, respectively, for the worst subgroup. Consider two clusters with equal expected proportions, i.e., . For a subgroup of 20 individuals, assignments of and yield discrepancies of 6 and 12. In contrast, for a subgroup of 1,000 individuals, assignments of and yield the same discrepancies. Thus, even a small difference in SP can be practically significant for rare subgroups.
-
Main aim of fair clustering: achieving a good trade-off between clustering cost and fairness. Fair clustering aims to achieve fairness while preserving clustering quality (Chierichetti et al., 2017; Bera et al., 2019; Ziko et al., 2021; Esmaeili et al., 2021). For example, with , randomly assigning every instance the same soft assignment achieves perfect fairness, but ignores the underlying data structure and does not guarantee meaningful clusters. In practice, users can fix a required fairness violation and select the lowest-cost solution satisfying the threshold. For example, on
Adult, Cova-FC and FRA both reach SP , at cost and (Table 6). For , both qualify, but Cova-FC has 12.8% lower clustering cost, indicating that it produces substantially better clustering. Thus, the practical benefit is not merely achieving a slightly lower SP, but attaining the desired fairness level while better preserving clustering quality.
Weaknesses
Why size weighting is the default. Size weighting gives rare subgroups less weight, but a subgroup smaller than K cannot appear in every cluster, so no method can close its gap (Gs≳2(K−ns)/K). A smaller α in the weight πsα gives rare subgroups more weight (results in Ewqn W1 above).
Rare-subgroup datasets. We test rare subgroups on
Communities, where 886 of 1,180 subgroups have one instance and all baselines are now in the main text (Table 2, Figure 4), and on the addedFairFace, whose smallest subgroup is 0.03% of the data. On both, Cova-FC keeps rare-subgroup gaps small, and a smaller α lowers them further; Reviewer Ewqn W1 above gives the table and results.Other fairness metrics. Cova-FC also does well on Balance, which it does not optimize, attaining the highest SB on three of four datasets (VFmB W2 above).
Size of the differences. SP values are means over five random seeds with standard deviations of at most 0.0001 (Table 6), so these differences are not noise. They appear on
BankandDutch, which have only three and four subgroups, where all methods do similarly. Cova-FC is designed for many subgroups, and there it leads clearly:Communities(1,180 subgroups; SP 0.0060 vs. at least 0.0094, Table R6),FairFace(126; 0.0017 vs. 0.0023), andCelebA(94; SP 0.1141 vs. 0.1299 among methods within the 2% cost budget; Table R1).Table R6: Comparison of clustering cost and SP on
Communities. Mean ± s.d.CommunitiesAdditional baselines. Table R7 (now Table 2) adds FRA, FairKM, FCBC, and
Communities; Cova-FC attains the lowest SP on all five datasets.Effect of normalization. Without it (Figure 3, Table 6), Cova-FC also attains the lowest SP on
Adult(tied with FRA),Dutch,Civilcomments, andBank.Table R7: Comparison of SP and clustering cost on L2-normalized data.
SP (Cost)
AdultDutchCivilcommentsBankCommunities