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

Authors: peng  zhou
rongwen  li
liang  du
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 03:52:25

Abstract: Kernel k-means has been widely studied in machine learning. However, existing kernel k-means methods often ignore the \textit{fairness} issue, which may cause discrimination. To address this issue, in this paper, we propose a novel Fair Kernel K-Means (FKKM) framework. In this framework, we first propose a new fairness regularization term that can lead to a fair partition of data. The carefully designed fairness regularization term has a similar form to the kernel k-means which can be seamlessly integrated into the kernel k-means framework. Then, we extend this method to the multiple kernel setting, leading to a Fair Multiple Kernel K-Means (FMKKM) method. We also provide some theoretical analysis of the generalization error bound, and based on this bound we give a strategy to set the hyper-parameter, which makes the proposed methods easy to use. At last, we conduct extensive experiments on both the single kernel and multiple kernel settings to compare the proposed methods with state-of-the-art methods to demonstrate their effectiveness.

Main paper: 
 introduction: 
 Clustering is a fundamental unsupervised machine learning task. In clustering, kernel methods, such as Kernel K-Means (KKM), can effectively separate nonlinear data into different clusters. Therefore, KKM has been widely studied in both the single kernel setting and multiple kernel setting [39, 50, 14, 15] . Notice that, in real-world applications, clustering is often used in some scenarios involving humans such as social networks [36] and crime analysis [32] . In these scenarios, since the humans are involved, we should guarantee the fairness of the clustering result, so that the clustering result will not cause discrimination to some specific groups. In the clustering task, we often consider the group fairness, where we have some pre-given groups that may suffer from the potential discrimination, called protected groups. Group fairness aims to partition data into some clusters and guarantee that no clusters contain a disproportionately small or large number of data in some specific protected groups [6] . Although the above-mentioned kernel k-means and multiple kernel k-means methods show promising performance in the clustering task, none of them considers the fairness issue, and thus they may obtain some clustering results which cause discrimination to some groups.To tackle this problem, in this paper, we propose a novel fair kernel k-means method and extend it from the single kernel setting to the multiple kernel setting. We follow a widely-used definition of fairness defined in [6] , which is shown as Definition 1. By analyzing this definition, we carefully design a new fairness regularization term and prove that minimizing this term can lead to the optimal fairness defined in [6] . Besides, we observe that our fairness regularization term has a similar form of the loss function of KKM, and thus can be naturally and seamlessly plugged into the KKM framework, yielding an extremely simple and elegant Fair Kernel K-Means (FKKM) framework. This framework is so concise that we do not even need to modify the loss of KKM but just adjust the input kernel to our proposed fair kernel. This framework can also be easily extended to the Multiple Kernel K-Means (MKKM) task, leading to Fair Multiple Kernel K-Means (FMKKM). We also provide some theoretical analysis of its generalization error bound. Furthermore, based on the generalization error bound, we provide a strategy to set the hyper-parameter in our framework, which makes the method easy to use. Extensive experiments on single kernel clustering and multiple kernel clustering tasks show the effectiveness of our framework w.r.t. both the clustering accuracy and fairness.The main contributions of our paper are summarized as follows:• We propose a novel fairness regularization term and prove that minimizing this term can reach the optimal fairness defined in [6] . • Our proposed regularization term has a similar form to the KKM, and thus can be seamlessly integrated into the KKM and MKKM framework. To the best of our knowledge, this is the first work for fair kernel k-means and fair multiple kernel k-means. • We provide a strategy to set the hyper-parameter based on the theoretical analysis, which makes the methods easy to use. • Extensive experiments in both single and multiple kernel clustering show the effectiveness and superiority of our proposed methods compared with the state-of-the-art methods. 
related work and preliminaries: 
 In this paper, we use a bold uppercase letter (e.g. M) and a bold lowercase letter (e.g. v) to denote a matrix and a vector, respectively. Given a matrix M, we use M ij to denote its (i, j)-th element.Given a data matrix X = [x 1 , . . . , x n ] ∈ R d×n with n instances and d features, let Φ (•) : R d → H represents a kernel mapping that maps X into a Reproducing Kernel Hilbert Space (RKHS) H. The objective function of the kernel k-means with the sum-of-squares loss can be written as [39, 24] :EQUATIONwhere Φ(X) = [Φ(x 1 ), . . . , Φ(x n )] and M = [m 1 , . . . , m c ] represents c clustering centroids in the RKHS H. Y ∈ {0, 1} n×c is an indicator matrix, which is denoted as Ind, and Y ij = 1 if x i is assigned to the j-th cluster, and otherwise Y ij = 0. Setting the derivative of Eq.( 1) w.r.t. M to zero, we can obtain the closed-form solution of M. Taking it back to Eq.( 1), it can be rewritten as [42] :EQUATIONwhere K = Φ(X) T Φ(X) ∈ R n×n is a kernel matrix with K ij = Φ(x i ) T Φ(x j ). For the convenience of optimization, we denoteEQUATION2 . Since directly solving Eq.( 2) is an NP-hard problem [16] , previous works [26, 41, 21] substituted the constraints Y ∈ Ind with H T H = I, leading to:EQUATIONThe optimal H is formed by the c eigenvectors of K corresponding to the c largest eigenvalues.After obtaining H, existing methods [54, 44, 35, 17] learn the final clustering results through some post-processing techniques such as k-means or spectral rotation on H.Multiple kernel k-means aims to fuse multiple base kernels to a consensus one for kernel k-means. Previous works assume that the ideal consensus kernel matrix is a combination of base kernel matrices i.e., K * = m p=1 γ 2 p K (p) , where K * is the consensus kernel matrix, and K (p) s are base kernels [27, 28, 19] . γ p is the weight of the p-th base kernel. Replacing K in Eq.( 3) with the consensus kernel K * , we can obtain the objective function of MKKM:EQUATIONIt can be solved by alternatively optimizing H and γ.Fair clustering considers the fairness in the clustering, which is an important problem in unsupervised machine learning. It was first introduced by Chierichetti et al., who proposed a fair decomposition method to avoid all members of a protected group being clustered into the same cluster [9] . However, this method can only handle two protected groups. To tackle this problem, Bera et al. further proposed a concept of fairness applicable to multiple protected groups in [6] , which is defined as:Definition 1 (Fairness) [6] Given a data matrix X ∈ R d×n with n instances and d features, it is par-titioned into c disjoint clusters C = {π 1 , • • • , π c }. Given t disjoint protected groups G 1 , G 2 , • • • , G t , let η i = |Gi| n and η i (k) = |π k ∩Gi| |π k |denote the proportion of group G i in the whole data and cluster π k , respectively. The fairnesss of a cluster π k is defined as:EQUATIONThe fairness of the whole clustering result C is defined as:EQUATIONRemark 1 f airness(C) ∈ [0, 1], and the larger f airness(C) is, the fairer the clustering result is.A fair clustering result requires that the proportion of G i in each cluster, which is denoted as η i (k), should be close to the proportion of G i in the whole data, which is denoted as η i . When all η i (k) = η i , the f airness will achieve its maximum value 1, which means it is perfectly fair. 3 Methodology 
fairness regularization term: 
 We first introduce our fairness regularization term. To control the fairness, according to Definition EQUATIONNotice that G is a constant matrix because the protected groups are often pre-given, while Y is a variable that needs to learn for clustering. Based on Eq.( 7), we define a fair regularization term Tr Y T GG T Y Y T Y -1 and provide the following Theorem, which shows that minimizing this regularization term leads to the maximum of the fairness defined in Definition 1.Theorem 1 Given G and Y defined as mentioned before, we can obtain the maximum of fairness by optimizing the following objective function:EQUATION)Proof 1 We first have:Tr Y T GG T Y Y T Y -1 = Tr Y T Y -1 2 Y T GG T Y Y T Y -1 2 = G T Y Y T Y -1 2 2 F .According to Eq,( 7), we haveEQUATIONTherefore, minimizing Eq.( 8) is equivalent to minimizing the following formula:EQUATION)According to Cauchy-Schwarz Inequality, we have:EQUATIONSumming Eq.( 11) w.r.t. i, we haveEQUATION)The equation in Eq.( 12) holds if and only if|π1∩Gi| |π1| = |π2∩Gi| |π2| = • • • = |πc∩Gi| |πc| for any i. It is easy to verify that |π1∩Gi| |π1| = • • • = |πc∩Gi| |πc| = k |π k ∩Gi| k |π k | .Notice that π k is a disjoint partition of all data, and thus we have(π 1 ∩ G i ) ∪ • • • ∪ (π c ∩ G i ) = G i and (π p ∩ G i ) ∩ (π q ∩ G i ) = ∅ for any p, q. Therefore, we have k |π k ∩ G i | = |G i |. Similarly, we have k |π k | = n.Taking them back to the condition of the equation holding, we have that the equation holds if and only if|π1∩Gi| |π1| = |π2∩Gi| |π2| = • • • = |πc∩Gi| |πc| = |Gi| n . Notice that |π k ∩Gi| |π k | = η i (k) and |Gi| n = η i .Therefore, when we minimize Eq.( 8), we have η i (k) = η i . According to Definition 1, it will lead to maximum fairness. This concludes the proof.According to Theorem 1, we provide a simple yet effective fair regularization term Eq.( 8), and can easily plug it into the KKM and MKKM framework.Notice that the fairness regularization term Tr Y T GG T Y Y T Y -1 has a similar form to KKM (i.e., Eq.( 2)). Therefore, we can seamlessly integrate this term into the KKM framework, leading to a fair kernel k-means (FKKM):EQUATION)where λ is a hyper-parameter to balance the trade-off between the clustering performance and the fairness. Larger λ will lead to a fairer clustering result. Of course, λ should not be too large, or it will dominate the loss function and the kernel k-means may not work. Comparing Eq.( 13) with Eq.( 2), we observe that if λ is small enough to make K -λGG T positive semi-definite (p.s.d.), we can regard K -λGG T as a new kernel matrix and Eq.( 13) becomes a standard kernel k-means. In this case, we call K -λGG T a fair kernel.However, in practice, to make K-λGG T be a valid kernel matrix, which means to make K-λGG T p.s.d., we should set a very small λ, which cannot guarantee the fairness. To address this issue, we find that we can add a large enough constant term α Tr(I) to Eq.( 13), to obtain a valid fair kernel matrix. In more detail, we have:EQUATIONIt shows that optimizing Eq.( 14) is always exactly equivalent to optimizing Eq.( 13), no matter how we set α. With a large enough α, we can easily set an appropriate λ to make K = K + αI -λGG T be p.s.d., and thus be a valid kernel matrix. We will discuss how to set λ and α later.In this way, we obtain an extremely simple yet elegant FKKM method. In this method, we do not even need to modify the loss of standard KKM. All we need is to modify the kernel by replacing K to a fair kernel K = K + αI -λGG T . It means that we realize the fairness on the data level rather than the model level.Eq.( 14) can be naturally extended to a multiple kernel setting. Given a base kernel K (p) , we first construct its fair kernel K(p) = K (p) + αI -λGG T . Then similar to Eq.( 4), we define the fair consensus kernel K * = m p=1 γ 2 p K(p) and take it into Eq.( 2) to obtain FMKKM:EQUATIONNotice that since our fairness regularization term Tr Y T GG T Y Y T Y -1 requires that Y should be a discrete indicator matrix, our FKKM (i.e., Eq.( 14)) and FMKKM (i.e., Eq.( 15)) directly solve the discrete Y instead of the conventional two-step methods which learn an orthogonal embedding H first and then obtain the discrete clustering result. As we know, 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. Different from the two-step methods, we can directly learn the final clustering result Y by fully considering the clustering accuracy and fairness.When minimizing Eq.( 14), we only need to solve one variable Y. Notice that there is only one 1 in each row of Y. Therefore, we can solve Y row by row. When solving the i-th row, we replace the i-th row with[1, 0, • • • , 0], [0, 1, 0, • • • , 0], ..., [0, • • • , 0, 1]respectively, and compute the values of the corresponding objective function to find the one which leads to the maximum. Then we set the i-th row as this row vector. Wang et al. propose an efficient method to compute these objective functions by reducing the computation redundancy [43] .In Eq.( 15), there are two groups of variables, i.e., Y and γ. We solve them by a block coordinate descent method, which optimizes one variable when fixing the other.When fixing γ to solve Y, we have the following subproblem w.r.t Y:EQUATIONwhereK * = m p=1 γ 2 p K(p). It is the same as the optimization of FKKM.When fixing Y to solve γ, we have following subproblem w.r.t γ:EQUATIONwhereh p = Tr K(p) I -Y Y T Y -1 Y T .According to Cauchy-Schwarz Inequality, the closed-form solution of γ p is:EQUATION)Appendix A shows the pseudo-codes of FKKM and FMKKM, respectively. When updating each row of Y, the objective function of FKKM decreases and has a lower bound. Therefore, FKKM can always converge. Similarly, the convergence of FMKKM can also be guaranteed. Now, we analyze the time complexity. According to [43] , optimizing the i-th row of Y has a time complexity of O (nc).FKKM has a time complexity of O n 2 c . Calculating γ has a time complexity of O (n). Therefore, FMKKM also has a time complexity of O n 2 c . According to [43] , although the time complexity is square in the number of instances, it can be computed very efficiently in practice. Therefore, the time complexity of our method is comparable with the mainstream KKM and MKKM methods. 
theoretical analysis: 
 The generalization error bound of the k-means evaluates the expectation of distance between an unseen data and the clustering center it belongs to [30, 22, 21] . Since FKKM is a special case of FMKKM when m = 1, in this section, we derive the generalization error bound of our FMKKM.Before the derivation, we need the following two mild assumptions:Assumption 1 Each K(p) = K (p) + αI -λGG T is a valid kernel matrix, i.e., K(p) is symmetric and p.s.d.Remark 2 This assumption is easy to satisfy. If K(p) is not p.s.d., we can enlarge α to make the assumption hold.Assumption 2 All K (p) are upper bounded. We denote b as the maximum of elements in all K (p) .According to assumption 1, since all K(p) are valid kernel matrices, K * is also a valid kernel matrix. We define the corresponding kernel function of K * as K * (•, •), and its kernel mapping function isΦ γ (x i ) = [γ 1 Φ 1 (x i ) T , . . . , γ m Φ m (x i ) T ] T : R d → H, where Φ 1 (x i ), . . . , Φ m (x i ) are the induced kernel mapping function of K(1) , . . . , K(m) , respectively. Let M = [m 1 , . . . , m c] denote the learned centroids matrix in the RKHS H, where m i is the center of the i-th cluster in H. FMKKM aims to minimize the error: E min y∈{e1,...,ec} ∥Φ γ (x) -My∥ 2 H , where [e 1 , . . . , e c ] are the standard orthonormal basis of R c space, i.e., e i is an all-zero vectors except that the i-th element is 1.Then, we define a function class as our hypothesis space:EQUATION)Similar to [21] , we have the following Theorem to provide the generalization error bound:Theorem 2 Under Assumptions 1 and 2, given training data X = [x 1 , . . . , x n ], function class F defined in Eq.( 19), and any δ ≥ 0, with probability at least 1 -δ, the following inequality holds for all f ∈ F:EQUATION)where t and c are the number of protected groups and clusters, respectively.Proof 2 See Appendix B.The first term in Eq.( 20) is the empirical error. Notice that, we haven i=1 f (x i ) = Tr K * I -Y Y T Y -1 Y T ,which means our loss function is to minimize exactly this empirical error. However, in the two-step methods, which applyH T H = I where H = Y Y T Y -12 to replace Y ∈ Ind, they only optimize a continual approximation of the empirical error.Besides, the second and third terms represent the gap between the generalization and empirical errors. Intuitively, the gap is the smaller the better. To decrease the gap, we wish α to be as small as possible. However, Assumption 1 prevents α being too small because K(p) should be p.s.d., or Theorem 2 will not hold anymore. Now we can derive the lower bound of α according to Assumption 1. Suppose σ min as the smallest eigenvalue of K (1) , . . . , K (p) . Then, the smallest eigenvalue of K (p) + αI should be no smaller than σ min + α. Notice that we have the following Lemma:Lemma 1 Given two real symmetric matrices A and B with the same size, where the smallest eigenvalue of A is σ A and the largest eigenvalue ofB is σ B . If σ A ≥ σ B , then A -B is p.s.d. Proof 3 See Appendix C.Denoting σ max as the largest eigenvalue of GG T , it is easy to verify that σ max = |G max |, where G max is the protected group with the largest number of instances. According to Lemma 1, we have that if σ min + α -λ * |G max | ≥ 0, K(p) will be p.s.d. Therefore, α has a lower bound λ * |G max | -σ min . In practice, σ min is often very small and close to 0. To avoid the time consuming to compute the eigenvalues of the kernels, we can approximately set α = λ * |G max |.Take α = λ * |G max | back into the generalization error bound Eq. (20) . We consider the gap between the generalization and empirical errors, i.e., the second and third terms:EQUATIONNotice that |G max | -1 ≥ 0 and |G max |t -1 ≥ 0, and thus we have that the gap decreases with λ decreases. It means that smaller λ leads to a lower gap. Therefore, λ is a trade-off between the clustering performance and fairness. Increasing λ may enlarge the error bound, but obtain a fairer result. Based on this theoretical analysis, we provide a strategy to set λ by observing a fairness metric, which can be computed without the ground truth. In more detail, we gradually enlarge λ from 0, set α = λ * |G max |, and observe the fairness metric. If it gets stable good fairness, we stop enlarging λ and set λ 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 λ to achieve a good fairness result. 
data sets and experimental setup: 
 We conduct experiments on benchmark data sets which are widely used in fair clustering, including D&S [2] , HAR [3] , Jaffe [29] , MNIST-USPS [20] , Credit Card [52] and K1b [53] . D&S is a human daily and sports activities data set including 8 participants. HAR is a human action recognition data set including 30 participants. In both D&S and HAR data sets, the data of each participant form a protected group. Jaffe is a face image data set. Following [20] , the face images with the same expressions are put into a protected group. MNIST-USPS is an image data set containing images of handwritten digits from the subsets of MNIST and USPS data sets. Following [20] , we randomly sample 2000 images from MNIST to form one protected group and randomly sample 1800 images from USPS to form the other protected group. Credit card is a data set that describes the customers' default payments and the data of males and females form two protected groups respectively. K1b is a text data set. Following [48] , we randomly assign each text to a protected group with a Bernoulli distribution whose p = 0.5 to form two protected groups. The statistical information of these data sets is shown in Appendix D. In the single kernel setting, we compare our FKKM with K-means [13] , Kernel K-means (KKM) [10] , Spectral Clustering (SC) [33] , and three state-of-the-art fair clustering methods, including SpFC [18] , VFC [58] , and FFC [34] . For the kernel methods (i.e., our FKKM and KKM), we use a Gaussian kernel with a bandwidth parameter fixing to √ 0.5 * D, where D is the average distance between samples. In the multiple kernel setting, we compare our FMKKM with 9 state-of-the-art MKKM methods, including ONKC [25] , MKCSS [55] , DPMKKM [42] , LFLKA [51] , EMKC [38] , OSLR [47] , ASLR [46] , CSAMKC [56] , FAMKKM [41] . Detailed information of these compared methods is shown in Appendix E. Besides, for an ablation study, we also compare with the degeneration version of our method, which is without the fairness regularization term, denoted as FKKM-f (for single kernel version) and FMKKM-f (for multiple kernel version).In the multiple kernel setting, following [11] , we construct 12 kernels, including seven Gaussian kernels K (x i , x j ) = exp -∥x i -x j ∥ 2 2 /2ϵ 2 with ϵ = √ s * D, where s varies in the range of { 1 8 , 1 4 , 1 2 , 1, 2, 4, 8} and D is the average distance between samples; four polynomial kernels K (x i , x j ) = a + x T i x j b with a = {0, 1} and b = {2, 4}; and a cosine ker-nel K (x i , x j ) = x T i x j / (∥x i ∥ • ∥x j ∥).Finally, all kernels have been normalized through K (x i , x j ) / K (x i , x i ) K (x j , x j ) and then rescaled to [0, 1]. We use Accuracy (ACC) and Normalized Mutual Information (NMI) to evaluate the clustering performance. Besides, we also use balance (Bal) [20] and Minimal Normalized Conditional Entropy (MNCE) [49] to evaluate fairness. Specifically, Bal is defined asEQUATIONwhere N min k and N max k represent the number of instances in the smallest and the largest (in size) protected groups in cluster π k , respectively. MNCE is defined asEQUATIONAll metrics are the larger the better. Based on previous analysis of hyper-parameter setting, we search λ as λ = 1, 2, . . . , by observing the corresponding MNCE. When the MNCE gets stable, i.e., the change of MNCE is smaller than 0.005, we stop the searching and use the current λ. For other comparison methods, we follow their recommended parameter configurations and search methodologies. All experiments are conducted on the 12th Gen Interl(R) Core(TM) i7-12700 with 32 GB RAM. All experiments are repeated 10 times and the average results are reported.Table 1 shows the comparison results in the single kernel setting, where the best and second best results are denoted in bold and underlined, respectively. It can be seen that FKKM exhibits better fairness compared to K-means, KKM, SC, our ablation version (i.e., FKKM-f), and even the fair clustering methods, indicating the effectiveness of our fairness regularization term. When comparing w.r.t. clustering performance (i.e., ACC and NMI), FKKM still often achieves the best or the second-best results.Table 2 presents the comparison results in the multiple kernel setting. FMKKM easily achieves the best fairness, due to the effectiveness of our fairness regularization term. Moreover, FMKKM often achieves better or at least comparable ACC and NMI. Notice that our method just simply modifies the original MKKM and can achieve competitive clustering performance, demonstrating that our method is simple yet effective.Figure 1 shows the visualization results. It shows the number of instances of each protected group G j in each cluster π i in the D&S data set obtained by FMKKM-f and FMKKM, respectively. As shown in Figure 1 (a), in FMKKM-f, without the fairness regularization term, the numbers of data of each protected group in each cluster have a great difference, which means the result is unfair. Figure 1 (b) shows that the distribution of protected group in each cluster is more balanced, which means the result obtained by FMKKM is much fairer than FMKKM-f. It demonstrates the effectiveness of our fair regularization term.The convergence curves of our methods are shown in Appendix F. The results show that our methods often converge very fast. We also conduct experiments to compare the running time of our methods with other compared methods. Our method is faster than or at least comparable with other methods on many data sets. The detailed results are shown in Appendix F.Figure 2 shows the effects of λ of FKKM and FMKKM on MNIST-USPS and Credit Cards data sets. The other results are similar. The red points denote the λ selected by our strategy. We can see that with the increase of λ, the fairness grows and the clustering performance may decrease, which is consistent with our previous discussion. We can often achieve a good trade-off between fairness and performance at the red point, which shows the effectiveness of our hyper-parameter setting strategy. 
conclusion: 
 In this paper, we focused on the fairness issue in KKM and MKKM. We carefully designed a novel fairness regularization term, which can be seamlessly plugged into the KKM and MKKM framework. Equipped with this fairness regularization term, we proposed a novel FKKM and FMKKM method. We also provided a hyper-parameter setting strategy based on the theoretical analysis to make the methods easy to use. Extensive experiments demonstrated the effectiveness and superiority of our proposed FKKM and FMKKM methods.Although the proposed methods achieve promising performance on fairness, they still have some limitations. For example, in our methods, the protected groups must be pre-given or decided by humans. An interesting question is how to automatically decide the protected groups without human intervention. In the future, we will focus on this problem.A Pseudo-codes of FKKM and FMKKM Algorithms 1 and 2 show the pseudo-codes of our FKKM and FMKKM, respectively.Algorithm 1 Fair Kernel K-means Update Y row by row by solving Eq.( 16). Input: Kernel matrix K, protected groups G 1 , • • • , G t , 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: We do not find any societal impact of this work.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All used assets are cited.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Denote R (M, γ) = 1 n n i=1 min y∈{e1,...,ec} ∥Φ γ (x i ) -My∥ 2 H . Our goal is to bound:EQUATION)According to Assumption 2, we have the largest value of elements in K (p) is b. Now, we consider K(p) = K (p) + αI -λGG T . Since the diagonal elements of GG T are 1, given any x i , we have thatΦ T γ (x i ) Φ γ (x i ) = m p=1 γ 2 p Φ T p (x i ) Φ p (x i ) ≤ b + α -λ.Given two different instances x i and x j , if they belong to the same protected group, we have that the (i, j)-th element in GG T is 1, and thusΦ T γ (x i ) Φ γ (x j ) = m p=1 γ 2 p Φ T p (x i ) Φ p (x j ) ≤ b -λ.If x i and x j belong to different protected groups, we have that the (i, j)-th element in GG T is 0, and thus (25) where m k denotes the k-th cluster centroid. Next, we denote a i = |π k ∩ G i | to represent the number of instances in all protected groups in cluster π k . We have:Φ T γ (x i ) Φ γ (x j ) = m p=1 γ 2 p Φ T p (x i ) Φ p (x j ) ≤ b. Then, notice that min y∈{e1,...,ec} ∥Φ γ (x i ) -My∥ 2 H = min ∥Φ γ (x i ) -m 1 ∥ 2 H , • • • , ∥Φ γ (x i ) -m c ∥ 2 H ,EQUATIONThe second to last inequality holds due to the Cauchy-Schwarz inequalityt i=1 a 2 i ≥ ( t i=1 ai) 2 t and t i=1 a i = |π k |.Therefore, we have:EQUATIONAccording to the Theorem 3.1 in [30] , by utilizing McDiarmid's inequality, we have that for any δ ≥ 0, with probability at least 1 -δ, for all f ∈ F, the following inequality holds:EQUATIONwhere:EQUATIONrepresents the Rademacher complexity of F [45] . σ 1 , . . . , σ n are Rademacher random variables uniformly distributed on {-1, 1}.Next, we introduce the Gaussian complexity to provide an upper bound for R n (F) [5] :EQUATIONwhere β 1 , . . . , β n are Gaussian random variables with zero mean and unit standard deviation. To bound the Rademacher complexity, we need the following two lemmas:EQUATION)then we have:EQUATIONIn our setting, we define:EQUATIONNext, we aim to find H f (i.e., H M,γ ) such that:EQUATIONSpecifically, for any f 1 , f 2 ∈ F, we have:EQUATIONThe final two inequalities hold due to (a + b + c) 2 ≤ 4a 2 + 2b 2 + 4c 2 , c r=1 y r = 1, and c r,s=1 y r y s = 1. Therefore, combining Eq.( 33) and Eq.( 35), we have:EQUATIONThen, we obtain H M,γ as follows:H M,γ = 2 n i=1 β i Φ T γ (x i ) 2 H + 2 √ 2 n i=1 c r=1 β ir Φ T γ (x i ) Me r + 2 n i=1 c r,s=1β irs e T r M T Me s .To bound the expectation of H M,γ , we introduce the following Lemma from [31] :Lemma 4 [31] Suppose that 1) (e r : 1 ≤ r ≤ c) is an orthonormal basis of R c ; 2) M is the class of linear operators M : R c → H with ∥Me r ∥ H ≤ ω 3) (x i : 1 ≤ i ≤ n) is a sequence in H,∥x i ∥ H ≤ µ ; 4) (β ir : 1 ≤ i ≤ n, 1 ≤ r ≤ c) and (β irs : 1 ≤ i ≤ n, 1 ≤ r, s ≤ r) are orthogaussian (independent and N (0, 1) ) sequences.Then the following three inequalities hold:EQUATIONEQUATIONEQUATIONwhere ⟨•, •⟩ denotes the inner production.In our method, given an instance x i , we have that∥Φ γ (x i )∥ H = Φ T γ (x i ) Φ γ (x i ) ≤ b + α -λ. Moreover, we also have ∥Me r ∥ H ≤ b + α -λt according to Eq.( 26). As a result, according to Lemma 4, the expectation of H M,γ can be be bounded as follows,EQUATIONLast, we can bound ℜ n (F) with Lemma 2, Lemma 3, Eq.( 29), Eq.( 30), and Eq.( 41):EQUATIONSubstituting Eq.( 42) into Eq.( 28), we finally obtain for any δ ≥ 0, with probability at least 1 -δ, for all f ∈ F, the following holds:EQUATIONThis concludes the proof.Since σ A is the smallest eigenvalue of A, and σ B is the largest eigenvalue of B, we have:EQUATIONEQUATIONSumming up Eq.( 44) and Eq.( 45), we have:EQUATIONConsidering the smallest eigenvalue of A -B, denoting as σ A-B , and its corresponding eigenvectorv A-B , we have (A -B) v A-B = σ A-B v A-B .Multiplying the left-hand side of Eq.( 46) with v T A-B and v A-B , we haveEQUATIONNotice that (A -B -(σ A -σ B ) I) is positive semi-definite according to Eq.( 46), which meansv T A-B (A -B -(σ A -σ B ) I) v A-B ≥ 0. Therefore, σ A-B -(σ A -σ B )≥ 0, and thus σ A-B ≥ σ A -σ B ≥ 0. This means that A -B is positive semi-definite, which concludes the proof.We conduct experiments on benchmark data sets which are widely used in fair clustering, including D&S [2] , HAR [3] , Jaffe [29] , MNIST-USPS [20] , Credit Card [52] and K1b [53] . D&S is a human daily and sports activities data set including 8 participants. HAR is a human action recognition data set including 30 participants. In both D&S and HAR data sets, the data of each participant form a protected group. Jaffe is a face image data set. Following [20] , the face images with the same expressions are put into a protected group. MNIST-USPS is an image data set containing images of handwritten digits from the subsets of MNIST and USPS data sets. Following [20] , we randomly sample 2000 images from MNIST to form one protected group and randomly sample 1800 images from USPS to form the other protected group. Credit card is a data set that describes the customers' default payments and the data of males and females form two protected groups respectively. K1b is a text data set. Following [48] , we randomly assign each text to a protected group with a Bernoulli distribution whose p = 0.5 to form two protected groups. Details of the data sets are shown in Table 3 .To show the effectiveness of our method on clustering performance and fairness, we compare our method with some state-of-the-art fair clustering and multiple kernel k-means methods, including:• SpFC [18] , which integrates fairness constraints into the Laplacian matrix of a graph.• VFC [58] , which is a universal variational fair clustering framework. • FFC [34] , which is a three-stage fair clustering method based on k-means method.• ONKC [25] , which is an optimal neighborhood kernel clustering algorithm to enhance the representability of the optimal kernel. • MKCSS [55] , which is a simple yet effective neighbor-kernel-based MKC algorithm to consider the intrinsic neighborhood structure among base kernels. • DPMKKM [42] , which is a novel discrete multiple kernel k-means by directly solving the clustering indicator matrix. • LFLKA [51] , whihc is a simple late fusion multiple kernel clustering with local kernel alignment maximisation approach. • EMKC [38] , which is effective multiple kernnel k-means by introducing spectral perturbation theory to laplacian matrix. • OSLR [47] , which is a one stage multiple kernel k-means by refining shifted laplacian matrix.• ASLR [46] , which is a effective multiple kernel k-means by reconstructing the laplacian matrix.• CSAMKC [56] , which is a fast multiple kernel k-means by adopting a novel sampling strategy to improve the performance of MKC. • FAMKKM [41] , which is fast and innovative multiple kernel k-means by incorporating two approximated partition matrices instead of the original individual partition matric for each base kernel.Figures 3 and 4 show the convergence curves of FKKM and FMKKM, respectively. We can see that our methods converge very fast and they often converge within 5 iterations.Figures 5 and 6 show the running time of all methods on single kernel setting and multiple kernel setting, respectively. For better comparison, we report the logarithm of the time (in seconds). From Figures 5 and 6 , we can see that our FKKM and FMKKM are faster than or at least comparable with many state-of-the-art methods, which well demonstrates the efficiency of our methods. #iterations #iterations Justification: We conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: This paper incorporates fairness into kernel K-means clustering, by designing a novel regularization term for clustering and proving it leads to fair clustering results based an existing fairness definition. A generalization error bound of the regularized clustering algorithm is derived and discussed, and experimental results on six data sets show the algorithm strikes a better fairness-accuracy balance than existing K-means clustering algorithms, their fair variants and kernel K-means clustering algorithms. 

All reviewers commended the proposed regularization term, the theoretical analysis and convincing experimental results. I agree and think the regularization term is smartly designed and has a non-obvious connection to fair clustering (as stated in Theorem 1). The paper definitely carries a fair amount of merits. 

On the other hand, reviewers suggest adding discussions on several things, including practical implications of fair kernel clustering (e.g. use cases), computational cost and related work. I agree and encourage authors to properly address them in revision or future studies. 
Nevetheless, I judge these deficiencies do not outweigh the merits of the work.

Reviews: review: paper_summary: paper_summary: The paper introduces a new framework called Fair Kernel K-Means (FKKM) aimed at addressing fairness issues in kernel K-means clustering. By incorporating a fairness regularization term, the method ensures fair data partitioning and avoids discrimination against specific groups. Additionally, the paper extends this method to a multi-kernel setting, proposing the Fair Multiple Kernel K-Means (FMKKM) method. Theoretical analyses and experimental validations demonstrate the effectiveness and superiority of the proposed methods in both single and multiple kernel clustering tasks.
strength_weakness: strength_weakness: 1.While the paper introduces FKKM and FMKKM, it lacks a detailed discussion on their practical application and limitations. Real-world effectiveness and constraints are not thoroughly explored.
2.The experimental setup, including data selection and comparison with other methods, is not comprehensively described. There is a lack of in-depth analysis of the experimental results.
3.The paper does not detail the computational resources required for the experiments, such as CPU/GPU types, memory, and execution time, which are essential for ensuring reproducibility.
4.Although the paper proposes methods to address fairness, it does not thoroughly discuss how these methods perform in practical applications, especially in scenarios with noisy or inconsistent data.
questions: questions: 1.Are there specific technical challenges or deficiencies in the proposed fairness regularization term when applied to real-world, noisy, or unbalanced datasets? How does the method address these issues, and what are the potential impacts on its performance?
2.The paper combines fairness regularization with kernel K-means. How do these combinations offer substantial innovations beyond the sum of their parts? Are there specific examples where this combination significantly outperforms individual techniques?
3.Beyond the specific datasets tested, how does the proposed method generalize to other applications or domains? Can the authors provide examples or theoretical justifications for its broader applicability?
4.How does the new fairness regularization term quantify and balance the trade-off between clustering performance and fairness? Can the authors provide more detailed insights or metrics used to achieve this balance?
5.Given the computational complexity associated with fairness in clustering, how scalable is the proposed method for large-scale datasets? Can the authors provide a thorough analysis of the computational complexity and runtime performance compared to other state-of-the-art methods?
6.The paper mentions using multiple kernels. How does the proposed method ensure that the selected kernels contribute to fairness without compromising clustering performance? Are there specific strategies or metrics used to evaluate and enhance kernel diversity?
7.The experiments were conducted on specific benchmark datasets. How does the proposed method perform on diverse real-world datasets not included in the benchmark? Are there plans to validate the algorithm on more varied and complex datasets?
8.How sensitive is the proposed method to the choice of hyperparameters? Can the authors provide a sensitivity analysis to demonstrate the robustness of the method under different hyperparameter settings?
9.While the theoretical foundations are sound, how does the proposed method scale with extremely large datasets? Are there any practical implementations or optimizations that address the potential computational bottlenecks in real-world scenarios?
10.Given the complexity of fairness in clustering, how feasible is the method for real-time or near-real-time applications? Are there any real-world use cases where the proposed method has been successfully implemented and tested?
limitations: limitations: In the "Conclusion" section, the authors discuss the limitations of the work, including strong assumptions, the robustness of the results to the assumptions, the scope of the experiments, and factors that may affect the performance of the method. In addition, the authors discuss computational efficiency and scale issues.
paper_summary: paper_summary: This paper proposes a novel Fair Kernel K-Means (FKKM) framework to address the fairness issue in kernel k-means clustering. The authors introduce a fairness regularization term that can be seamlessly integrated into the kernel k-means objective function. They extend this approach to multiple kernel k-means, resulting in Fair Multiple Kernel K-Means (FMKKM). The paper provides theoretical analysis of the generalization error bound and a strategy for setting hyperparameters. Extensive experiments on both single kernel and multiple kernel settings demonstrate the effectiveness of the proposed methods in achieving fair clustering results while maintaining competitive clustering performance.
strength_weakness: strength_weakness: 1. The main weakness is that this paper does not discuss the use case extensively. In what cases people would use this kind of fair kernel based clustering method?
2. The evaluation is mainly about fairness and it is more convincing if the authors could compare the clustering performance. Usually incorporating fairness would cause the degeneration on the original clustering performance. A significant improvement on fairness and a small degeneration on clustering can better validate the effectiveness of the proposed method.
questions: questions: 1. How does the proposed method perform on very large-scale datasets? Are there any scalability issues?
2. Have the authors considered extending the fairness concept to other clustering algorithms beyond kernel k-means?
3. How sensitive are the proposed methods to the choice of initial kernels in the multiple kernel setting?
4. Can the proposed fairness regularization term be adapted to other machine learning tasks beyond clustering?
limitations: limitations: 1.  As mentioned in the conclusion, the method requires pre-defined protected groups, which may not always be available or appropriate in all scenarios.
2. While the method often achieves good performance on both metrics, there might be cases where improving fairness significantly impacts clustering quality.
3. The approach is specifically designed for kernel-based clustering, which may limit its applicability to non-kernel-based clustering algorithms.
4. The paper focuses on a specific definition of fairness, and it's unclear how the method would perform under alternative fairness criteria.
paper_summary: paper_summary: The authors design a novel fair kernel k-means method and a fair multiple kernel k-means method. The main part is the fairness regularization term. By minimizing this term, the optimal fairness, which is defined in Definition 1, can be achieved. The authors also derive the generalization error bound and discuss how to select $\lambda$ to decrease the bound. At last, the authors conduct the experiments by comparing with some state-of-the-art single kernel methods, fair clustering methods, and multiple kernel k-means methods. The results show that the proposed methods can achieve better fairness.
strength_weakness: strength_weakness: 1.In Tables 1 and 2, there are many “0”s in the results of Bal. Is that normal? If so, why?
2.Figure 1 is a little confusing. Figure 1(b) is the result of FMKKM and should be fair. However, Figure 1(b) still seems not balanced enough. For example, when the cluster axis is 1, the instances is much more than the instances whose cluster axis is  20. More explanation should be provided.
3.Some symbols or notations e.g. $delta$ and $b$, are reused in different places for different purposes (see Section 4 and Section 5.1), which should be corrected.
questions: questions: The paper calls $K+\alpha I-\lambda GG^T$ a fair kernel and claims that the methods only replace the traditional kernel with this fair kernel. However, traditional kernel k-means often needs the eigenvalue decomposition to learn a continual embedding and then discretize it to the final clustering results. The proposed methods directly learn the discrete results. My question is that, what about directly take the fair kernel $K+\alpha I-\lambda GG^T$ into the standard kernel k-means, instead of directly solving the new discrete problem? Can this still achieve the fairness?
limitations: limitations: N/A
paper_summary: paper_summary: This paper focuses on the fairness in the kernel k-means. It designs a new fairness regularized term, which has the same form as the kernel k-means. Then it plugs this term into the kernel k-means and extends it to the multiple kernel k-means. Some theoretical analyses are provided to help to tune the hyper-parameters. The experimental results show the effectiveness of the proposed methods.
strength_weakness: strength_weakness: 1. The related work of fair clustering can be introduced in more detail.
2. As we know, time-consuming is one of the biggest problems in kernel methods. The proposed methods add a regularized term on the conventional kernel k-means and directly solve the discrete optimization problem. Will they increase time overhead?
3.  Although the paper discusses the trade-off between accuracy and fairness, I think more about the usage scenarios should be discussed, since the proposed methods are not as universal as conventional kernel k-means after all. For example, how about the scenarios that the accuracy contradicts to the fairness seriously? When should we use the proposed methods, and when should we use the conventional kernel k-means?
questions: questions: Please see the Weaknesses.
limitations: limitations: The paper has analyzed the limitations.

Comments: title: Response
Response 2
Respond
comment: Thanks for your approval and the clarification of the AC's questions.

For the Question 1, i.e., the correctness of Theorem 1. As said by AC, the equation in Row116 is a sufficient condition for the equality to hold. Therefore, we just show that it is also a necessary condition. To show it's a necessary condition, we need to show that if the equality in Eq.(11) holds, we can derive the equality in Row116. As discussed in above comments, the equality in Cauchy-Schwarz Inequality can result in  $\frac{|\pi_1\cap\mathcal{G}_i|}{|\pi_1|}=\cdots=\frac{|\pi_c\cap\mathcal{G}_i|}{|\pi_c|}$. So, we just need to show that this ratio can only be $\frac{|\mathcal{G}_i|}{n}$. Notice that if $\frac{a}{b}=\frac{c}{d}$, we have $\frac{a}{b}=\frac{c}{d}=\frac{a+c}{b+d}$. According to this, we have $\frac{|\pi_1\cap\mathcal{G}_i|}{|\pi_1|}=\cdots=\frac{|\pi_c\cap\mathcal{G}_i|}{|\pi_c|}=\frac{\sum_k{|\pi_k\cap\mathcal{G}_i|}}{\sum_k{|\pi_k|}}$. Since $\pi_k$ is a disjoint partition of all data, we have $(\pi_1\cap\mathcal{G}_i)\cup\cdots\cup(\pi_c\cap\mathcal{G}_i)=\mathcal{G}_i$ and $(\pi_p\cap\mathcal{G}_i)\cap(\pi_q\cap\mathcal{G}_i)=\emptyset$ for any $p,q$. Therefore, we have $\sum_k|\pi_k\cap\mathcal{G}_i|=|\mathcal{G}_i|$. Similarly, we have $\pi_1\cup\cdots\cup\pi_c=X$ and $\pi_p\cap \pi_q=\emptyset$, where $X$ is the set of all data, leading to $\sum_k|\pi_k|=n$. Therefore, we have  $\frac{|\pi_1\cap\mathcal{G}_i|}{|\pi_1|}=\cdots=\frac{|\pi_c\cap\mathcal{G}_i|}{|\pi_c|}=\frac{\sum_k{|\pi_k\cap\mathcal{G}_i|}}{\sum_k{|\pi_k|}}=\frac{|\mathcal{G}_i|}{n}$, which is the equation in Row116.

For the second Question. Since our method is based on standard KKM, the clustering objective and kernelization have been done by standard KKM. In more detail, Eq.(1) in Section 2.1 is the clustering objective of standard KKM. It is kernelized in Eq.(2). Our contribution is to design a new fairness regularization term, which is shown in Eq.(8). Therefore, our final objective is to combine Eq.(2) and Eq.(8), which is shown in Eq.(14). Then we design Algorithm 1 to optimize Eq.(14), which first constructs the fair kernel $\tilde{\mathbf{K}}=\mathbf{K}+\alpha\mathbf{I}-\lambda\mathbf{G}\mathbf{G}^T$, and then optimize $\mathbf{Y}$ row by row. For the FMKKM, the original clustering objective is Eq.(4) in Section 2.1. We plug our regularized term (Eq.(8)) into it, leading to our final objective function Eq.(15). Then we design Algorithm 2 to optimize Eq.(15). We first construct fair kernels for each base kernel, and then iteratively optimizing $\mathbf{Y}$ and weight $\gamma_p$. I'm sorry to cause any confusion and will try to improve the presentation.
With the clarification of case study and experiments, all my questions are mostly solved so I will improve my score.
Here is the questions:

The concern about the correctness of Theorem 1. Its proof argues the equality in (12) holds when equlity in Row116, which implies minimizing the left-hand-side of (12) always results in  equlity in Row116. However, this equality comes from Cauchy-Schwarz in (11), which seems to hold under a broader condition (as long as the two vectors of added items are orthogonal). In other words,  equlity in Row116 may only be a sufficient but not necessary condition for the equality to hold, which means minimizing the left-hand-side of (12) does not always results in  equlity in Row116.

Why authors present the designed algorithm (18) in a seemingly unconventional way. If the goal is to incorporate an existing fairness constraint, isn't it more common to first design a clear clustering objective (btw, what is the clustering objective of this algorithm?) with the fairness constraint, then kernelize it and finally optimize it or its proxy?
Thanks for your responses. Our experiment follows previous works of fair clustering, and we use some public real-world data, such as Credit Card. Our reply just means that we tried some real-world data but not means we intend to use the noisy and inconsistent data. We admit that we do not consider the noisy and inconsistent data specifically. We appreciate your constructive suggestions and agree that using more noisy and inconsistent data would be better. We will try more data, especially noisy and inconsistent data.

Sorry. We can not see AC's questions now. The following is the answers to the AC's two questions you mentioned.
1. The Cauchy-Schwarz Inequality is that for two vectors $\mathbf{a}$ and $\mathbf{b}$, we have $||\mathbf{a}||_2^2*||\mathbf{b}||_2^2\ge\<\mathbf{a},\mathbf{b}\>^2$, where $\<,.,\>$ denotes the inner production. The equation holds if and only if $\mathbf{a}=c\mathbf{b}$ for some $c$, which means $\frac{a_1}{b_1}=\frac{a_2}{b_2}=\cdots=\frac{a_n}{b_n}$. In our Theorem 1, $\mathbf{a}=[\frac{|\pi_1\cap\mathcal{G}_i|}{\sqrt{|\pi_1|}},\cdots,\frac{|\pi_c\cap\mathcal{G}_i|}{\sqrt{|\pi_c|}}]$ and $\mathbf{b}=[\sqrt{|\pi_1|},\cdots,\sqrt{|\pi_c|}]$. The equation in Eq.(11) holds, when $\frac{\frac{|\pi_1\cap\mathcal{G}_i|}{\sqrt{|\pi_1|}}}{\sqrt{|\pi_1|}}=\cdots=\frac{\frac{|\pi_c\cap\mathcal{G}_i|}{\sqrt{|\pi_c|}}}{\sqrt{|\pi_c|}}$, i.e., $\frac{|\pi_1\cap\mathcal{G}_i|}{|\pi_1|}=\cdots=\frac{|\pi_c\cap\mathcal{G}_i|}{|\pi_c|}$. Notice that, if $\frac{|\pi_1\cap\mathcal{G}_i|}{|\pi_1|}=\cdots=\frac{|\pi_c\cap\mathcal{G}_i|}{|\pi_c|}$, we have $\frac{|\pi_1\cap\mathcal{G}_i|}{|\pi_1|}=\cdots=\frac{|\pi_c\cap\mathcal{G}_i|}{|\pi_c|}=\frac{\sum_k{|\pi_k\cap\mathcal{G}_i|}}{\sum_k{|\pi_k|}}=\frac{|\mathcal{G}_i|}{n}$, which is shown in the paper. Therefore, the conditions shown in the proof of Theorem 1 are exactly the necessary and sufficient conditions of the equation holding.

2. Eq.(18) is the closed-form solution of $\gamma_p$ rather than our proposed algorithms. Due to the limited space, we do not show the algorithms in the main body of the paper, but we show the algorithms in the Appendix. The algorithms of FKKM and FMKKM are shown in Algorithms 1 and 2 in the Appendix. The differences between our algorithms and the standard KKM and MKKM are that 1) we need construction of fair kernel $\tilde{\mathbf{K}}=\mathbf{K}+\alpha\mathbf{I}-\lambda\mathbf{G}\mathbf{G}^T$, and 2) we optimize discrete $\mathbf{Y}$ row by row.
Thank you for your answer which partly solve my problem.

Regarding W4 & Q7, I want to know why you didn't try more real data, including noisy and inconsistent data, to verify the effectiveness of the algorithm in the experiments of this paper. Your reply told me that you originally intended to do so, but it was not shown in the paper. Why? I still have doubts about the case study.

As you can see in AC's comment, I would be also interested to AC's question: 
1.about the correctness of Theorem 1. That mentioned equality comes from Cauchy-Schwarz in (11), which seems to hold under a broader condition (as long as the two vectors of added items are orthogonal). 
2. Why authors present the designed algorithm (18) in a seemingly unconventional way.
Dear reviewer GAQw, Thank you for reviewing our paper. We hope our previous responses and revisions will meet your requirements. We are looking forward to your reply on the discussion stage. Thank you very much.
Dear reviewer  dRCy,
Thank you for reviewing our paper. We hope our previous responses and revisions will meet your requirements. We are looking forward to your reply on the discussion stage.
Thank you very much.
Thanks for the author's response, which has effectively addressed my concerns. I will keep my score on the paper.