Fair Kernel K-Means: from Single Kernel to Multiple Kernel

W1. We will revise the related work to introduce the fair clustering methods in more detail.

W2. Since our method has the same form as the standard kernel k-means, we do not increase much overhead. In contrast, in our method, instead of using the eigenvalue decomposition which is used in conventional KKM and MKKM methods, we directly learn the discrete clustering result $Y$. This optimization only involves matrix multiplication, which is faster than conventional eigenvalue decomposition. We also conduct comparison experiments w.r.t. the running time. The results are shown in Figures 5 and 6 in the Appendix. The results show that our methods are faster than or at least comparable with other kernel methods.

W3. We will discuss it in more detail in the revised version. The methods should be used in some applications involving humans which need fairness. For example, in the clustering of the customers of the banks, we wish to partition the customers into several groups to make the decisions for each individual. However, when doing the partition or making the decision, we should not consider gender, or it will cause sexism. In these scenarios considering the fairness when doing the partition, we can use the fair kernel k-means. Otherwise, in the cases that do not need fairness or without humans, we can use the standard clustering methods instead of the fair methods. If the accuracy contradicts to the fairness seriously, we should consider the fairness first or it may cause some bad social impact, such as sexism or other discriminations. Therefore, we should first guarantee fairness and select a relatively good clustering result in the fair results. Our strategy to choose $\lambda$ to make a trade-off between accuracy and fairness in Section 4 is also based on this rule.

W1. Bal is a very strict evaluation metric that considers the worst case. Notice that $\mathrm{Bal}\left(\mathcal{C}\right)=\min_{k} \left(\frac{N_{k}^{\min}}{N_{k}^{\max}} \right)\in[0,1]$. As long as in one cluster, there are no instances of one protected group, according to its definition, Bal will be zero. That’s why there are many 0s in other methods. Therefore, the results are normal.

W2. Sorry to cause you confusion. Fairness considers the balance of protected groups in each cluster instead of the balance of clusters. That means we should check the distribution along the protected group axis instead of the cluster axis. For example, although the instances in the cluster with axis 1 are much more than the cluster with axis 20, the 8 protected groups in the cluster with axis 1 or 20 are both balanced, which means the results are fair.

W3. Thanks. We will revise these notations.

Q1. As you suggested, we tried to take $K+\alpha I-\lambda GG^T$ into standard KKM, denoted as KKM-fair. The results are shown as follows:

It shows that this kernel can indeed improve the fairness of standard KKM. Notice that the fairness of KKM-fair may be lower than our proposed FKKM. It is because that according to Theorem 1, the regularized term achieves fairness when we find a discrete $Y$ to minimize $tr(Y^TGG^TY(Y^TY)^{-1})$. If we use the traditional two-step method, even though we obtain an optimal embedding $H$, we cannot guarantee there exists a discrete $Y$ to make $H=Y(Y^TY)^{-1/2}$ in the second step. That’s why we propose a one-step method instead of the two-step method.

W1. The methods can be used in some applications involving humans which need fairness. For example, in the clustering of the customers of the banks, we wish to partition the customers into several groups to make the decisions for each individual. However, when doing the partition or making the decision, we should not consider gender, or it will cause sexism. In these scenarios considering the fairness when doing the partition, we can use the fair kernel k-means. Or otherwise, in the cases that do not need fairness or without humans, we can use the standard clustering methods instead of the fair methods. We will add more detailed discussion in the revised version.

W2. In Tables 1 and 2, we compare with other methods w.r.t. ACC, NMI, Bal, and MNCE. The Bal and MNCE are for fairness, and the ACC and NMI are for clustering performance. As you said, incorporating fairness may cause the degeneration of the original clustering performance, which is also discussed in Section 4 and can be observed in our experiments of Parameter Study (i.e., Figure 2). To address this problem, we design a parameter selection method to choose the appropriate $\lambda$ for the regularized term in Section 4. We gradually enlarge $\lambda$ from 0, set $\alpha = \lambda ∗ |G_{max}|$, and observe the fairness metric. If it gets stable good fairness, we stop enlarging $\lambda$ and set $\lambda$ as the current value. This strategy does not need the ground truth, which is appropriate for unsupervised learning, and can obtain an as small as possible $\lambda$ to achieve a good fairness result. The comparison results also demonstrate this. Besides, another difference between our FKKM-f, FKKM and the conventional KKM is that our method is a one-step method that directly learns the final discrete clustering result $Y$ and other KKM methods are two-step methods that need to learn an embedding first, and then discretize the embedding to obtain the discrete result. In the two-step methods, the kernel k-means and the discretization post-processing are separated and when doing the discretization it cannot guarantee the clustering accuracy or fairness. We think this may be the other reason why our methods can outperform other methods w.r.t. the clustering accuracy.

Q1. Yes. There is a scalability issue. The issue exists in the conventional KKM and MKKM methods, not only in our methods. We also have made some attempts to tackle the issue. For example, instead of using the eigenvalue decomposition used in conventional KKM and MKKM, we directly learn the discrete clustering result $Y$, which only involves matrix multiplication. It’s faster than conventional eigenvalue decomposition. We also conduct comparison experiments w.r.t. the running time. The results are shown in Figures 5 and 6 in Appendix. The results show that our methods are faster than or at least comparable with other kernel methods. Of course, some techniques for large scale kernel methods, such as [1], can be used to further improve the scalability and efficiency. [1] On the Consistency and Large-Scale Extension of Multiple Kernel Clustering. In IEEE TPAMI 2023.

Q2. From the proof of Theorem 1, the proposed regularized term can achieve the fairness defined in Def. 1. Therefore, this term can be used in any clustering loss function involving the clustering indicator matrix $Y$. We use it in KKM and MKKM tasks because this term has the same form as KKM, and thus can be seamlessly integrated into these frameworks. We can also integrate it into other loss functions, such as kmeans and spectral clustering, but the formula may not be as elegant as that in KKM and MKKM.

Q3. One main motivation of multiple kernel methods is that with different kernels which may have very different performance, the multiple kernel methods can provide a stable and robust result. Therefore, most MKC methods are insensitive to the choice of initial kernels. Since our method is a variation of standard MKKM, intuitively, it is also insensitive to the choice of the initial kernels.

Q4. As explained in the response to your Q2, the proof of Theorem 1 doesn’t involve kernels or clustering. It means that Theorem 1 holds for any machine learning tasks. Therefore, the regularized term can be used in the tasks involving the learnable class indicator matrix $Y$, such as the classification, clustering, and some embedded feature selection methods using classification or clustering results.

L2. Yes. As discussed in Section 4, too large weight for the regularized term may deteriorate the clustering accuracy. It can also be observed from our experiments of Parameter Study (i.e., Figure 2). To address this problem, we design a parameter selection method to choose the appropriate $\lambda$ for the regularized term in Section 4. The comparison results in Tables 1 and 2 with four metrics including the clustering performance and fairness also demonstrate this. Detailed explanation can be found in the answer to W2.

L3. From the proof of Theorem 1, the proposed regularized term can achieve the fairness defined in Definition 1. Therefore, this term can be used in any clustering loss function involving the clustering indicator matrix $Y$. We use it in the KKM and MKKM tasks because this term has the same form as KKM and MKKM, and thus can be seamlessly integrated into these frameworks. We can also integrate it into other loss functions, such as kmeans and spectral clustering, but the formula may not be as elegant as that in KKM and MKKM.

L4. Yes. Our regularized term is designed based on Definition 1, which is a widely used definition of fairness. Whether this term is effect under other definitions of fairness needs a more careful theoretical analysis.

W1. Our methods can be used in applications involving humans which need fairness. For example, in bank system, we make decisions without considering the gender of customers to avoid sexism. In experiments, we use Credit Card data in this scenario. The data is to predict whether a customer will face default. It collects customers' information and partition the customers into 5 clusters: timely repayment, delayed repayment for 1, 2, 3, and 4 months, respectively. In this task, gender is the protected attribute to avoid sexism. We also use some other real-world data such as D&S and HAR. We’ll add more discussion in the revised version.

W2. We’ll revise it to introduce the experimental setup and results further. We use the widely-used data in real-world fair clustering tasks, including D&S, HAR, Credit Card. Following previous work, we also use some synthetic data such as JAFFE, K1b, MNIST-USPS. The details are introduced in the paper. In single kernel setting, we compare some classical clustering methods, such as kmeans, KKM; and SOTA fair clustering methods, such as FairSC, VFC. In the multi-kernel setting, we compare some SOTA multi-kernel methods, such as ONKC, ASLR. We’ll further introduce them in the revised version.

The experimental results show that our method outperforms others in fairness. It is often better or comparable on ACC and NMI. It obtains good trade-off between accuracy and fairness due to our strategy of choosing an appropriate $\lambda$ for the regularized term in Section 4. We gradually enlarge $\lambda$ from 0 and set $\alpha = \lambda |G_{max}|$. When getting stable good fairness, we stop enlarging it. The strategy can obtain as small as possible $\lambda$ for good fairness. Besides, ours is a one-step method that directly learns the final discrete result and other KKM methods are two-step methods that learn an embedding first and then discretize it. In two-step methods, the two steps are separated. When discretization, it cannot guarantee accuracy or fairness. This is the reason why it outperforms other methods in accuracy.

W3 & Q5. All experiments are conducted on a PC with an i7-12700 CPU and 32G RAM and repeated 10 times to report the average result. We’ve analyzed the time complexity in the last paragraph in Section 3.4.2, which is $O(n^2c)$. Other kernel methods need the time-consuming eigenvalue decomposition. Our method directly learns the discrete clustering result without eigenvalue decomposition. It only uses matrix multiplication, which is faster in practice. We’ve reported the execution time in Fig. 5 and 6 in Appendix. It shows that ours are often faster than or comparable with other SOTA methods.

W4 & Q7. We use some real datasets such as Credit Card to show the application of the proposed method, showing its superiority. We will try more real-world data including noisy and inconsistent data in the future. Section 4 shows that in the worst case the generalization error is upper bounded, providing a guarantee of the method used on new datasets theoretically.

Q1.Our main contribution is to propose a new fairness regularized term, and thus we focus on fairness instead of robustness or balance. Since our method has the same form as standard KKM, any robust or balanced techniques that can be used in KKM, can also be easily used in our method. Our term can also be plugged into other methods that can handle noisy or unbalanced data, to further improve fairness.

Q2. We can easily plug the regularized term into KKM because it has the same form as KKM, showing its elegant structure. It’s one of our contributions. Our ablation study (in Tab. 1 and 2) by comparing with the versions without the term, denoted as FKKM-f and FMKKM-f, show that without this term the fairness is poor, demonstrating this combination outperforms individual techniques.

Q3. In Section 4, we provide theoretical analysis of the generalization error bound. On any untested data, in the worst case, the generalization error of the proposed FMKKM is upper bounded. It provides a theoretical guarantee on unseen data. According to Theorem 1, the proposed term can be used in any applications involving class indicator $Y$.

Q4 & Q8. According to Theorem 1, larger $\lambda$ causes fairer results. According to the generalization error bound in Eq.(21), large $\lambda$ increases the error bound, i.e., it may decrease the accuracy on unseen data. This is how the regularized term compromises accuracy and fairness theoretically. In practice, we show the sensitive curves of hyperparameter $\lambda$ in Fig. 2. Large $\lambda$ causes better fairness but worse accuracy, being consistent with theoretical analysis. We provide a strategy to select $\lambda$ without accessing the ground truth labels. We also mark the selected $\lambda$ in the curves, showing that our strategy often achieves good trade-off between accuracy and fairness.

Q6. No matter in single or multiple kernel methods, there is always trade-off between the clustering performance and fairness, controlled by $\lambda$. In Section 4 we theoretically discuss the trade-off in multi-kernel setting. Based on the discussion, we provide a strategy to select $\lambda$. Since the main contribution is about fairness, we don’t control the diversity. Intuitively, considering diversity may improve performance. Since ours has the same form as KKM, any diversity term for KKM can also be used in our methods.

Q9 & Q10. Kernel methods often have scalable issue. So our current version may also be hard to handle extremely large data or real-time applications. However, our implementation only uses matrix multiplication instead of eigenvalue decomposition. It can be easily parallelized for scalability. Moreover, since our formula has the same form as KKM, any scalable or speedup methods for KKM can also be used in ours to tackle the scalable issue, such as [1]. [1] On the Consistency and Large-Scale Extension of Multiple Kernel Clustering. In TPAMI 2023.