Fair Clustering via Alignment

To reviewer Nujs: We sincerely appreciate your review and thank you for the opportunity to improve our work. Please refer to our point-by-point responses below.

Claims And Evidence

1: However, in the experiments, the authors do not compare the results of proposed method with the method of Chietichetti et al. (2017).

• In the current version, instead of directly comparing with Chietichetti et al. (2017), we compared FCA with SFC (Backurs et al., 2019), which developed a more scalable fairlet-based method. Notably, Backurs et al., (2019) reported SFC's competitive/better performance when compared to Chietichetti et al. (2017) across three real datasets.

• However, in light of your suggestion, we have newly conducted experiments comparing FCA and Chietichetti et al. (2017). The results are provided below, showing ourperformance of FCA, which we will add to Appendix C.3.1 in the camera-ready version.

  Dataset / Bal*	Adult / 0.494		Bank / 0.649		Census / 0.969
  	Cost (↓)	Bal (↑)	Cost (↓)	Bal (↑)	Cost (↓)	Bal (↑)
  Chietichetti et al. (2017)	0.507	0.488	0.378	0.639	1.124	0.941
  SFC	0.534	0.489	0.410	0.632	1.015	0.937
  FCA ✓	0.328	0.493	0.264	0.645	0.477	0.962

Methods And Evaluation Criteria

1: However, the authors do not use the well-known measures to evaluate the clustering quality.

• The reason why we consider the `cost' for measuring clustering quality is because it is the clustering objective function to be minimized.

• (Comparison in terms of the silhouette score) However, as you suggested, measuring the cost alone may not fully capture the clustering quality, we additionally consider another measure, called the silhouette score. The silhouette score is computed as the average of $(d_{\text{near}} - d_{\text{intra}}) / \max(d_{\text{intra}}, d_{\text{near}})$ over all data points, where $d_{\text{intra}}$ denotes the intra-cluster distance and $d_{\text{near}}$ represents the average distance to the nearest neighboring cluster.

  Surprisingly, the results in the following table show that FCA is also superior or competitive to baselines in terms of the silhouette score. We will add it to Appendix C.3.1 of the camera-ready version.

  Adult / Bal* = 0.494	Silhouette (↑)	Bal (↑)
  Standard (fair-unaware)	0.227	0.223
  FCBC	0.173	0.443
  SFC	0.071	0.489
  FRAC	0.156	0.490
  FCA ✓	0.176	0.493

Experimental Designs Or Analyses

1: However, 3 datasets are not yet appropriate ... Besides, the selection of features (on each dataset) is not yet well explained...

• (The number of datasets) Please note that we analyzed 6 datasets in total. That is, not only the three tabular datasets, but we also analyzed on two image datasets (Section 5.3 and Appendix C.3.2) and a large synthetic dataset (Appendix C.3.7).

• (Analysis on an additional dataset) However, in light of your comment, we additionally conducted an analysis on Credit Card dataset from Yeh and Lien (2009), which was also used in Bera et al., (2019) and Harb & Lam, (2020). We used gender as the sensitive attribute and set $K = 10.$ The results are provided in the table below (to be added to Appendix in the camera-ready version), showing the outperformance of FCA.

  CreditCard / Bal* = 0.656	Cost (↓)	Bal (↑)
  Standard (fair-unaware)	0.392	0.506
  FCBC	0.492	0.629
  SFC	0.682	0.653
  FRAC	0.510	0.649
  FCA ✓	0.402	0.653

  (References) Yeh and Lien (2019): The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 2009.

• (About the feature selection) Existing fair clustering works use continuous variables as features (Backurs et al. 2019; Bera et al., 2019; Esmaeili et al., 2021; Ziko et al., 2021), so we have made the same choice. For reference, the features we consider in this paper are the same as VFC (Ziko et al., (2021)). Furthermore, please note that the feature `final weight (fnlwgt)' has also been selected in the prior works (Esmaeili et al., 2021; Ziko et al., 2021).

  We will add the above detailed explanation to Appendix C.1 in the camera-ready version.

To reviewer 4J8b: We sincerely appreciate your review and the opportunity to improve our work. Please refer to our point-by-point responses below.

Weaknesses

1: The computational complexity ...

• Section 4.3 introduces a partitioning technique to reduce the computational complexity. Our experiments (Figures 6–7 and Table 9 in Appendix C.3.3) demonstrate that it yields reasonable results and significant runtime reduction. To evaluate scalability, we already conducted experiments on a dataset of one million data points, showing that FCA outperforms VFC (Appendix C.3.7).

2: The method requires ...

• We think that $\epsilon$ is not a tuning parameter, but $\epsilon$ itself serves as a fairness level in FCA-C. In particular, on Page 5 we define $\mathbf{A}\_{\epsilon}$ as the set of assignment functions where the sum of unfairness across clusters is bounded by $\epsilon.$ FCA-C always converges to a local minimum for any given $\epsilon.$
• On the other hand, Proposition 3.2 implies that we can control balance by controlling $\epsilon.$

3: The paper primarily addresses ...

• We have already discussed extending FCA to handle multiple groups (see Appendix A.3). To numerically validate this extension, we newly conducted an analysis using Bank dataset with 3 groups single/married/divorced (following VFC (Ziko et al., 2021)). The results are in the table below (to be added to Appendix A.3): FCA can practically handle multiple groups and outperforms VFC (a lower cost $0.222 < 0.228$ with a higher balance $0.182 > 0.172$).

Other Comments Or Suggestions

1: It is better ...

• Please see our response to 'Weaknesses' above.

2: Consider discussing ...

• (Sinkhorn algorithm) We also applied the Sinkhorn algorithm and compared with solving the Kantorovich problem using the linear programming. The Sinkhorn algorithm of Cuturi et al., (2013) optimizes $\mathbf{C} + \lambda \cdot ent(\Gamma),$ where $\mathbf{C}$ is the cost matrix defined in Section 4.1, $\lambda$ is a regularization parameter, and $ent(\Gamma)$ denotes the entropy of the coupling matrix $\Gamma.$

  The result table below suggests that: careful tuning of $\lambda$ is crucial, while the runtime reduction may not be significant in practice ($\lambda = 0.01$) and a large regularization ($\lambda = 1.0$) significantly degrades performance while reducing runtime (10% decrease). This experiment also suggests that reducing computational cost (beyond the partitioning technique) for solving the Kantorovich problem would be difficult but is a promising future study. We will include this discussion in Appendix.

  Adult / Bal* = 0.494	Cost (↓)	Bal (↑)	Runtime / iteration (sec)
  FCA (Sinkhorn, λ = 1.0)	0.350	0.271	4.98
  FCA (Sinkhorn, λ = 0.1)	0.315	0.463	5.12
  FCA (Sinkhorn, λ = 0.01)	0.330	0.491	5.55
  FCA (Linear program)	0.328	0.493	5.67

  (References)
  Cuturi et al., (2013): Sinkhorn Distances: Lightspeed Computation of Optimal Transport

3: Expanding ...

• In Appendix A.4, we already showed that FCA can be similarly applied to $L_{p}$ norms for all $p \ge 1.$ Experimentally, Appendix C.3.9 (Table 17) shows that under the $K$-median ($L_{1}$ norm) setting, FCA outperforms the fairlet-based method SFC.
• During the rebuttal, we realized that the argument for the extension to $L_{p}$ norm in Appendix A.4 can be applied to any distance satisfying the triangle inequality. We will add this comment in the camera-ready version.

Ethical Review Concerns

1: This paper may need an ethics review ...

• Our paper primarily aims to achieve proportional (group) fairness in clustering, in line with many existing works. We acknowledge that focusing solely on proportional fairness may overlook other fairness notions. In light of your feedback, we will add the following paragraph to our Impact Statement in the camera-ready version:

• (A paragraph to be added to `Impact Statement')

  While this work focuses on proportional (group) fairness, we acknowledge that such an approach may overlook other fairness notions, such as individual fairness or social fairness (e.g., balancing clustering costs across groups), which are not explicitly addressed within the proportional fairness framework. We therefore encourage readers to interpret our results with this scope in mind: our goal is to improve the trade-off between clustering cost and proportional fairness level, but care must be taken when considering the broader implications for other fairness notions. In conclusion, we anticipate future studies that integrate fair clustering research with various notions of fairness.

To reviewer AM68: We sincerely appreciate your review and thank you for the opportunity to improve our work. Please refer to our point-by-point responses below.

Weaknesses

1: Extremely notationally dense ...

• Answer:
  • When preparing this work, we initially considered summation-based notations for expressions such as $\frac{1}{n\_{s}} \sum\_{i=1}\^{n\_{s}} \sum\_{k=1}\^{K} \mathcal{A}\_{s}(\mathbf{x}\_{i})\_{k} \bigg( \frac{\Vert\mathbf{x}\_{i}-\mathbf{T}(\mathbf{x}\_{i})\Vert^2}{4} + \left\Vert \frac{\mathbf{x}\_{i} + \mathbf{T}(\mathbf{x}\_{i})}{2}-\mu\_k \right\Vert\^2 \bigg),$ for eq. (2) in Theorem 3.1. However, we decided to use the probability-based notations instead, since the readability of the proofs is much improved.
  • We were also concerned about this and made efforts to explain the probability-based formulations by use of summation-based notation in several instances (e.g., the clustering cost $C(\mu, \mathcal{A})$ in Section 2, the definition of balance in lines 119-120, and assignment functions of FCA in Section 4).

2: New methods aren't entirely novel ...

• Answer:
  • We agree that FCA is similar to the fairlet-based methods in the sense that the idea of matching is used. In this sense, FCA can be viewed as a novel extension of the fairlet-based methods.
  • Although the fairlet-based methods also rely on matching, it would be not optimal in view of fair clustering. In contrast, our method guarantees to find a matching map, which provides a (local) optimal fair clustering, by Theorems 3.1 and 3.3. Also, please see Remark 3.2 for further discussion.
  • It would be hard to modify the fairlet-based methods to control fairness level (for non-perfect fairness). FCA can be modified to find an (local) optimal solution to control fairness level (i.e., FCA-C algorithm).
  • This novel extension is made possible by the novel reformulation of the fair clustering objective function using the matching map (or alignment), as presented in Section 3.

Questions

1: Would you say ...

• Answer:
  • We thank you for the insightful question. Yes, you are right. However, in fact, the 'before' step of our approach (i.e., finding matchings) is not solely for achieving fairness, but also simultaneously for minimizing the clustering cost. Specifically, it solves a modified Kantorovich problem, where the modification is aimed at minimizing the clustering cost.
  • Furthermore, the proposed algorithm can be extended to control the fairness level (e.g., non-perfect fairness), while other pre-processing algorithms such as fairlet-based methods are not designed for it.

2: Can you clarify ...

• Answer:
  • Numerical stability means that FCA does not suffer from numerical instability compared to VFC. The main reason for this stability is that FCA does not have any regularization parameters while VFC requires to choose a fairness regularization parameter, which can make the algorithm numerically unstable.
  • Specifically, (i) FCA is more robust to dataset pre-processing, while VFC operates reliably when data points are $L_{2}$-normalized. (ii) FCA can achieve near-perfect fairness, whereas VFC may fail to do so. In detail, without $L_{2}$-normalization - especially in high-dimensional settings - VFC can become numerically unstable due to overflow. See Appendix C.3.1 for details.

3: How does the epsilon ...

• Answer:
  • (Fairness bound by $\epsilon$) Please refer to Proposition 4.2, which shows that the fairness level (balance) is bounded by $\epsilon.$
  • (The trade-off) The clustering cost for a larger $\epsilon$ is always lower than that for a smaller $\epsilon.$ That is, the optimal fair clustering with $\epsilon$ is included in $\mathbf{A}_{\epsilon'}$ for $\epsilon'>\epsilon.$
  • (Note: definition of $\epsilon$) $\epsilon \in [0, 1]$ represents the size of the set $\mathcal{W}$ (i.e., $\mathbb{Q}((\mathbf{X}\_{0}, \mathbf{X}\_{1}) \in \mathcal{W}) \le \epsilon$), as defined below eq. (5). The set $\mathcal{W}$ consists of the aligned data points to which the standard $K$-means clustering cost is applied. That is, $\epsilon$ used in the FCA-C algorithm is the fairness level: as $\epsilon$ decreases, the resulting clustering of FCA-C becomes fairer.

4: Are the benchmark ...

• Answer:
  • Yes, you are right. Among the four baseline methods we consider in our study (FCBC, SFC, FRAC, and VFC), three methods have been developed for $K$-means (as well as other $K$-clustering), while SFC is originally designed for $K$-median.
  • Please also note that, in Appendix C.3.9 we already discussed how to modify FCA for the $K$-median clustering setting. As shown in Table 17, FCA outperforms SFC under the $K$-median clustering setting.

To reviewer 1gG2: We sincerely appreciate your review and the opportunity to improve our work. Please refer to our point-by-point responses below.

Claims And Evidence

1: I don't find ...

• First, we would like to highlight our main contributions:
  • A novel reformulation of the fair clustering objective function using the matching map (Section 3).
  • Our method guarantees finding a matching map that provides a (local) optimal fair clustering (Theorems 3.1 and 3.3).
• For the theoretical aspect, please see our response to 'Weaknesses' below, where we suggest that our proposed algorithm is competitive with existing methods in terms of approximation rate.
• For discussion on the experimental aspect, please see our response to 'Experimental Designs Or Analyses' below, which emphasizes the empirical superiority of our proposed algorithm.

Experimental Designs Or Analyses

1: The authors can clarify this ...

• The main contribution of our work is the development of a numerically stable in-processing fair clustering algorithm. While in-processing algorithms such as VFC require difficult regularization parameter tuning, FCA does not have any regularization, guaranteeing a (local) optimal solution without tuning (Theorems 3.1 and 3.3). For example, FCA achieves near-perfect fairness and is more robust to data pre-processing than VFC (Section 5.2 and Appendix C.3.1).
• As expected, FCA significantly outperforms the fairlet-based pre-processing algorithm SFC: achieving nearly 40% lower cost on average and higher fairness (Table 1 in Section 5.2).
• Surprisingly, FCA performs even better on visual clustering tasks, competing with two image-specific algorithms and dominating SFC and VFC (Table 3 in Section 5.3).

2: Further, some ...

• Please see our response to 'Weaknesses-3' below.

3: Also, in Table 1 ...

• Although FCBC achieves a lower cost than FCA, it is less fair (i.e., lower balance). Table 1 compares the costs at the highest fairness levels each algorithm can achieve. FCBC achieves a lower cost because the highest fairness level it can achieve is lower than that of FCA.

• To compare fairly, we obtained a fair clustering using FCA-C with a cost of 0.313 (similar to the cost of FCBC, 0.314). The table below shows FCA-C achieves a higher balance (0.473 vs. 0.443), suggesting FCA offers a better trade-off than FCBC. This result will be added to Appendix C.3.1.

  Bal* = 0.494	Cost (↓)	Bal (↑)
  FCBC	0.314	0.443
  FCA-C ✓	0.313	0.473

Relation To Broader Scientific Literature

1: Although greater connection ...

• We appreciate the suggestion. In fact, we already mentioned the two methods in Section 1 and Appendix C.2.3. Experimentally, FCA outperforms VFC and FCBC (Tables 1, 2, 5, and 6; Figures 4 and 5).

Weaknesses

1: the main issue ...

• Our theoretical bound in Theorem 4.3 is not claimed to be the sharpest one, but is to claim that FCA is not much worse than the global optimal fair clustering. The main advantages of FCA include (i) greater numerical stability than an in-processing method VFC (Tables 2 and 6; Figures 3–5) and (ii) empirical superiority over post-processing methods (Tables 1 and 5).
• A detailed version of Theorem 4.3 is in Theorem B.3: FCA-C provides a $(\tau+2)$-approximate solution with a violation $3R\epsilon$, where $R$ is a bound on the data norm ($\sup_{\mathbf{x} \in \mathcal{X}} \Vert \mathbf{x} \Vert^{2} \le R$).
• A comparison of the detailed approximation rate with several existing methods:
  • Bera et al. (2019) achieved a $(\tau + 2)$-approximation and a violation $3.$ FCA-C provides the same approximation rate of $\tau + 2,$ but can attain a smaller violation when $R = 1,$ as $\epsilon \in [0, 1].$
  • Schmidt et al. (2018) provided a $(5.5\tau + 1)$-approximation, which is worse than $\tau + 2$ for $\tau > 2/9,$ e.g., $\tau = 8(\log K) + 2$ for the K-means++ algorithm.
  • We will include this discussion following Theorem 4.3 in the camera-ready version.
  • (References) Schmidt et al. (2018): Fair Coresets and Streaming Algorithms for Fair k-means.
• (Definition of $\epsilon$) Please see our response to 'Questions'-3 for Reviewer AM68 due to space limitation.

2: lines (184-187) ...

• The term 'suboptimal' in Remark 3.2 is used not because the clustering problem is NP-hard, but because our method guarantees finding a matching map providing a (local) optimal fair clustering (Theorems 3.1 and 3.3), whereas the matching map of the fairlet-based methods do not offer this guarantee.

3: the paper assumes that ...

• Please see our response to 'Weaknesses'-3 for Reviewer 4J8b due to space limitation.

4: (Minor) presentation ...

• Thank you for your careful review. (1) Remark B.1 will be moved to Section 3.1 and (2) the boxes will be replaced by algorithm expressions, in the camera-ready version.