Fair Kernel K-Means: from Single Kernel to Multiple Kernel
Authors: Peng Zhou
Rongwen Li
Liang Du
Venue: NeurIPS 2024 poster (2024)
Keywords: kernel k-means
multiple kernel k-means
fair clustering
Primary area: fairness
TL;DR: This paper proposes a new fairness regularization term and plug it into kernel k-means framework, leading to novel fair kernel k-means and fair multiple kernel k-means.

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.

Fair Kernel K-Means: from Single Kernel to Multiple Kernel
Peng Zhou
Rongwen Li
School of Computer Science and Technology Anhui University Hefei, 230601
School of Computer Science and Technology Anhui University
Hefei, 230601
zhoupeng@ahu.ede edu. en
e223012848stu. ahu edu.
Liang Du
School of Computer and Information Technology Shanxi University
Taiyuan, 237016 dul buliangen auliang edu, cn
Abstract
Kernel k-means has been widely studied in machine learning. However, existing kernel k-means methods often ignore the fairness issue, which may cause dis- crimination. To address this issue, in this paper, we propose a novel Fair Kernel K-Means (FKKM) framework. In this framework, we first propose new fairesss regularization term that can lead to fair partition of data. The carefully designed fairness regularization term has 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 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-paramettr, which makes the proposed methods easy to use. At last, we conduct extensive ex- periments on both the single kernel and multiple kernel settings to compare the pro- posed methods with state-of-the-ar methods to demonstrate their effectiveness. Our code is available at https:://// //github. com hoom//ooggeelll/lerriP22222 FMKKM
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 50
13
14 15).
Notice that, in real-world applications, clustering is often used in 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 faimess 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
Peng Zhou is the corresponding author. Peng Zhou and Rongwen Li are also with Anhui Provincial International Joint Research Center for Advanced Technology in Medical Imaging.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

groups [6]. Although the above-mention 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 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 [ 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-pane pyper-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 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.
2 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 vector, respectively. Given matrix M, we use Mij to denote its (i. j-th element.
2.1 Kernel K-means and Multiple Kernel K-means
Given a data matrix X x...... X.] E dx with n instances and features, let 1 (-) Rd + H
represents a kernel mapping that maps X into 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
(1) where (XX) = [0(x))...... (xx.)) and M = [m.,..., m. represents e clustering centroids in the RKHS H. Y E {0, 1]axee is an indicator matrix, which denoted as Ind, and Y,, = if x, is assigned to the j-th cluster, and otherwise Yy = O. Setting the derivative of (q. w.r.t. M to zero, we can obtain the closed-form solution of M. Taking it back to Eq. it can be rewritten as [4]
min M. Yndd
( MY 1
min Tr (K) - Tr ((r') Y' YY"))* Yeind
where K K ( E Raxa is a kernel matrix with K.₃ = (xx)) (xx)). For the convenience
of optimization, we denote H = Y (Y" - Since directly solving Eq. 2 is an NP-hard problem [6], previous works 26
21
substituted the constraints Y E Ind with H H = I, leading to:
min Tr K (1 (.-HHHH)
(3)
H'H=I The optimal H is formed by the eigenvectors of K corresponding to the largest eigenvalues. After obtaining H, existing methods 44 post-processing techniques such as k-means spectral rotation on H.
35 17 learn the final clustering results through some

---

Multiple kernel k-means aims to fuse multiple base kemells to consensus one for kernel k- k-means. Previous works assume that the ideal consensus kernel matrix is combination of base kernel matrices
ie..
K
p=1 Tz Kg (P), where K' the consensus kernel matrix, and K(Pss are base kernels
27
28
Tp the weight of the p-th base kernel. Replacing K in 3q. with the consensus we can obtain the objective function of MKKM:
kernel
K
min Tr (K' (T-(1-HH)
H' 1 7o K"
(4)
H
It can be solved by alternatively optimizing H and
2.2 Fair Clustering
Fair clustering considers the fairness the clustering, which an important problem in unsupervised machine learning. It was first introduced by Chierichetti et al., who proposed fair decomposition method to avoid all members 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 defined as:
Definition (Fairness) [6] Given data matrix X Rdx= with instances and d features, it is par- ritioned into с disjoint clusters {-1,-... Teh. Given t disjoint protected groups G1, 92, ... -9.. let = 19il and (=(k) |TTGi denote the proportion of group Gi in the whole data and cluster Tke [xel
respectively. The faimesss of a cluster Ti is defined as:
Thi Ti(kk) ()(k)) n/
fairness (mx) min
ViE (1.
(5)
The fairness of the whole clustering result C. is defined as:
min fairness(()) xE(1,--)
suirness(TR)
(6)
Remark foirness(C) E [0, 1), and the larger fairness(C) is, the faiver the clustering result is. A fair clustering result requires that the proportion of in each cluster, which denoted as ())))). should be close to the proportion of G; in the whole data, which is denoted as When all ny (k) Th the fairness will achieve its maximum value I, which means is perfectly fair.
For example, Ziko et al. proposed a variational fair clustering framework by integrating fairness term with clustering objective [57]; Kleindessner et al. embedded fairness as a linear constraint into spectral clustering obtaining fair spectral clustering [18]; Ghadiri et al. introduced a fair k-means method that ensures all protected groups have equal cluster costs [12]: Li et al. proposed deep fair clustering method 220) Wang et al. embedded this fairness into deep clustering by learning differentiated and fair clustering allocation function [40] Chhabra et al. provided a robust deep fair clustering method
Based on Definition T many fair clustering methods have been proposed
by considering the fairness attack g
3 Methodology
3.1 Fairness Regularization Term
We first introduce our fairness regularization term. To control the fairness, according to Definition 1 need compute [T& n ni and [T in ())).. To this end, we introduce two indicator matrices
G E (0. 1 and Y E {0. 1 jxxe__ G is protected group indicator matrix, where G.j- = 1 if the i-th instance belongs to the j-th protected group, and G.j, otherwise. Y is cluster indicator
matrix, where Yú 1 if the i-th instance belongs the j-th cluster, and Yo 0 otherwise. It is
easy to verify that
mi ng
ma O Gil ma O Gal
Ta n
M 0
0 0
m n
GTY
and YTY=
[ 0 Gel
Im. [
3

---

Notice that G is a constant matrix because the protected groups are often pre-given, while Y is variable that needs learn for clustering. Based on Eq. 7. we define fair regularization term Tr YYTGGYY (Y"Y)* ) and provide the following Theorem, which shows that minimizing this regularization term leads to the maximum of the fairness defined in Definition I
Theorem Given G and Y defined as mentioned before, we can obtain the maximum of fairness by optimizing the following objective function:
min Tr (Y"GGYY
(8)
Yelnd
Proof We first have:
Ir YFGG"Y (XTx) = Ir ((xT)) - Y= (x" +)= = G (X"'))
(xTx)++}
According Eq. 7 we have
Vin byg m2
Vimal lagn
m n
GO (x"x)++=
Vini
viza
(9)
Irange
Remge
Vim
Vival
Vinel
Therefore, minimizing Eq. 8 is equivalent to minimizing the following formula:
G² (Y (Y'
(10)
[T
km
According to Cauchy-Schwerd Inequality, we have:
mh
G.l
Th n gil
b& 9.
19.1
(11)
[T
Summing Eq. w.r.t. i, we have
T 2.l
19.12
(12)
[T
1=1
The equation in Eq. 12 holds if and only if |angaa
Imangal Le Imngel [aal
mang for any i. It is
[511
Stel
easy verify that [ mll
Notice that Th is disjoint partition
2n
of all data, and thus we have (m1 n u.).U .......
(Te n G.) -=)= = G, and (Tp n G.) n (Tg n G.) = 19.) Similarly,
have Σx T ngl for any p. q. Therefore,
have Ex [k
Taking
them back to the condition of the equation holding, we have that the equation holds if and only if laLngll 19.1
mang. [ra
[k2n9,1
mal
Notice that Iang (k) and | nR Therefore, when we minimize Eq. (8, we have m)s (k) T)-
aa According Definition 7 it will lead maximum fairness. This concludes the proof.
According to Theorem we provide a simple yet effective fair regularization term Eq. 8 and can easily plug it into the KKM and MKKM framework.
3.2 Fair Kernel K-means
Notice that the fairness regularization term Tr YTTGGY (YTC)YYYYY))))))) (YTY)-) has a similar form to KKM (i.e.. ()). Therefore, we can seamlessly integrate this term into the KKM framework, leading to fair kernel k-means (FKKM):
min Tr (K) -rr ((r")) - Y'KY (x-x)=+) + +AT (y"cG"x(Y"x)) Yelnd
max Tr (YT (K- ("-KKGG')) XGG") Y (x' - Yehud
(13)

---

where À is hyper-pape parameter to balance the trade-off between the clustering performance and the fairness. Larger À will lead to 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 Eg. T3) with Eq. (2) we observe that if À is small enough to make regard K XGG T as a new kernel matrix and Eq. 13 becomes standard kernel k-means. In this case, we call K XGG' a fair kernel.
AGG positive semi-definite (p.s.d.,, we can
However, in practice, to make K K-AGG" be valid kernel matrix, which means make K - -GG p.s.d., we should set very small X, which cannot guarantee the fairness. To address this issue, find that we can add a large enough constant term a (r(I) to (3). to obtain a valid fair kernel matrix. In more detail, we have:
'Ir Y "K"(K-AGG)) Y Y (xx)) +
+ Tr(I)
'Ir (xt(x" (K*(ktl-XXGG)) Y Y (x"x) )))
(14)
It shows that optimizing Eq.(14) is always exactly equivalent to optimizing Eq [3) no matter how we set a. With large enough we can easily set appropriate À to make K = K + aI - TGG
be p.s.d., and thus be a valid kernel matrix. We will discuss how to set and a later.
In this way, we obtain an extremely simple yet elegant FKKM method. In this method, we do not even need modify the loss of standard KKM. All need is to modify the kernel by replacing K to fair kernel K = K + aI XGGT. It means that we realize the fairness on the data level rather than the model level.
3.3 Fair Multiple Kernel K-means
Eq.414 can be naturally extended to a multiple kernel setting. Given a base kernel K(P), first construct its fair kernel K(p) K(r) + aI XGG". Then similar to Eq. we define the fair
consensus kernel K Ep=1 7p
k()) and take into e to obtain FMKKM:
min Tr K (R- (Y" )²)) s.t. Y e Ind, T" 11 7o 20, K
Σ
1 K
(15)
Notice that since our fairness regularization term Tr YYT (X"X) requires that Y should
be a discrete indicator matrix, our FKKM (i.e., Eq, (4)) and FMKKM (i.c., Eq. (T5) 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.
3.4
Optimization
3.4.1
Optimization of FKKM
When minimizing 14), only need 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........000 0). [0, 0, 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 al. propose an efficient method to compute these objective
functions by reducing the computation redundancy 43
3.4.2 Optimization of FMKKM
In Eq. 15). there are two groups of variables, i.e., Y and y. We solve them by block coordinate descent method, which optimizes one variable when fixing the other.
When fixing 7 to solve Y, we have the following subproblem w.r.t Y:
max Tr (Y" (Y (Y'x)
(16)
Yefnd
where K"
Em 3o
1K)) It the same as the optimization of FKKM.
5

---

When fixing Y to solve 7, we have following subproblem w.r.t 7:
min
ppp
8.1.
7 1, 7p 2 0, Σ
(17)
where hy Tr (K(() I- Y (YTY) -1 -rr))--r))))))
According Cauchy-Sehwarz Inequality, the
closed-form solution of Yp is:
hpp
7/p Σj= h
(18)
Appendix A shows the pseudo-codes of FKKM and FMKKM, respectively. When updating each row Y. the objective function of FKKM decreases and has lower bound. Therefore, FKKM can always converge. Similarly, the convergence of FMKKM can also be guaranteed. Now, analyze the time complexity. According to 43], optimizing the i-th row of has a time complexity of (nc). FKKM has a time complexity of O (n=c). Calculating 7 has time complexity of (n). Therefore, FMKKM also has a time complexity of (n²c). According to 44 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 21] Since FKKM is special case of FMKKM when m in this section, derive the generalization error bound of our FMKKM. Before the derivation, we need the following two mild assumptions:
K(p) + al - XGGT is a valid kernel matrix, i.e. K(P) is symmetric Assumption Each k(p) and p.s.d.
Remark This assumption is easy to satisfy. K(() is not p.s.d., we can enlarge a to make the assumption hold.
Assumption All (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 valid kernel matrix. We define the corresponding kernel function of K as (+,,,,), and its kernel mapping function is (x,) = [m 4 (x:)" ....)..... .i T,, (TIT d + H. where 4 (x;),.... T (xx) are the induced
kernel mapping function of (1) ..... (mm), respectively. Let M [m, m.] denote the learned centroids matrix in the RKHS H. where m; is the center of the i-th cluster in H. FMKKM aims to minimize the error: E [minye (eI.......) [| My [ where [e....., e.] are the standard orthonormal basis of R space, i.e., e; is an all-zero vectors except that the i-th element 1.
Then, we define function class as our hypothesis space:
F-
F 5-f1ix0 xi
1| (x) Myll 1-1= 1,7p 2 O, m E n
min oe)
(19)
Similar to we have the following Theorem to provide the generalization error bound:
Theorem Under Assumptions and and given training data X [xi...., Xa), function class F defined in Eq. 19.. and any ê 2 0, with probability at least 1 6, the following inequality holds for all f T F:
2m B(((x) -- Σ (xx)
(1 (1+t))bbal (1+ 2 (0(aa>)))
2(b
Vri
1=1
{A((b+a) -
1 (1=1) (==))))
(og(1/8)
(20)
2n
where and 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 have Σ (x:) = Tr K II-Y( (x)) which means our loss function is to minimize exactly this empir-
ical error. However, in the two-step methods, which apply H"H = I where H H (YTY) 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 However, Assumption 1 prevents a being too small because (P) should be p.s.d., or Theorem 2 will not hold anymore. Now we can derive the lower bound of a according to Assumption | Suppose min as the smallest eigenvalue of K K K(r), Then, the smallest eigenvalue of K(p) + al
be small as possible.
should be smaller than mmin + Notice that we have the following Lemma:
Lemma Given two real symmetric matrices and B with the same size, where the smallest eigenvalue of A is a A and the largest eigenvalue B is on a A an, then A B is p.s.al
Proof 3 See Appendix C
Denoting maz as the largest eigenvalue of GGT, it is easy to verify that maz = 19 where Imaz is the protected group with the largest number of instances. According to Lemmal I we have that if min + a
1mazz O, K(() will be p.s.d. Therefore, has lower bound A * Gmazl - min-- In practice, Tmin is often very small and close to 0. To avoid the time consuming to compute the eigenvalues of the kernels, we can approximately set a À |9masl-
Take a * [mmaz back into the generalization error bound Eq.2 We consider the gap between the generalization and empirical errors, i.e., the second and third terms:
2
(1 (1 (1+ a) -1+ ) 210t A) (b+a-
;) + (2
log(1/6)
vn
2n
2/2x
+ 23 + (19mar) 2llSmaolt -11) A + q 20 (19marl - 1)1) (b+ |meaa |t
-1)1)
Vn
(4b + 4(19mazl 1)A) 1))) log(1/8)
(21)
2n
Notice that [9mazl 1 1 and 19mazlt - 2 O, and thus we have that the gap decreases with A decreases. It means that smaller À leads to a lower gap. Therefore, À is trade-off between the clustering performance and fairness. Increasing À may enlarge the error bound, but obtain a fairer result. Based on this theoretical analysis, which can be computed without the ground truth. In more detail, we gradually entarge À from 0, set À |9maz 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 faimess result.
provide a strategy set by observing a fairness metric,
5
Experiments
5.1 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 Klb [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 a face image data set. Following [20], the face images with the same expressions are put into 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 data set that describes the customers' default payments and the data of males and females form two protected groups respectively. Klb is
7

---

text data set. Following [48] we randomly assign each text to protected group with a Bernoulli distribution whose p 0.5 form two protected groups. The statistical information of these data sets is shown in Appendix D
Contenr of momtrrreee
Table 1: Comparison results on the single kernel setting, The best and second best results are denoted in bold and underlined, respectively.
Data sets
m-mann
KKM
FairSC
VFC
FFC
F
FKKM
ACC
0.555
0.552
0.558
0.435
0.539
0.521
0.648
0.636
D&S
NMI
Bal
0.650
0
0.602
0.652
0.575
0.186
0.617
0.100
0,583
0.724
0.559
0.683
Chrster Rt
group
MNCE
0.156
0.531
0.023
0.923
0.712
0.477
0.991
(a) FMKKM-F
ACC
0.524
0.620
0.680
0.742
0.600
0,602
0.689
0.771
HAR
NMI
Bal
0.596
0
0.609
0
0.618
7.7
0.654
0.200
0.490
0.007
0.625
0
0.250
0.710
Number of intarness
MNCE
0.933
0.930
0.914
0.983
0.953
0.920
0.989
vo.
ACC
0.363
0.396
0.406
0.458
0.560
0.437
0.403
0.432
MNIST-USPS
NMT
0.423
0.421
0.435 0
0.306
0.412
0.426
0.380
Bal
0.142
0.217
0
0.847
MNCE
0
0.003
0.544
0.684
0.997
ACC
0.927
0.948
0.901
0.901
0,954
Jaffe
NMI
0.914
0.922
0.889
0.943
0.969
0.918
0,930
0.400
0.250
0.500
Cluste
MNCE
0.808
0.900
0.765
0.827
0.983
0.924
0.897
0.989
Piskecied growp 9.
ACC
0.362
0.381
0.311
0.351
0.381
0,364
0.400
0.404
(b) FMKKM
Credit Card
0.139
0.140
0.139
0.145
Bal
0.510
0.550
0.567
0.603
0.586
0,550
0.536
0.624
MNCE
0.953
0.961
0.967
0.975
0.970
0.969
0.956
0.985
Figure I: Fairness visual-
ACC
0.742
0.669
0.667
0.853
0.778
0.663
0.826
0.809
ization results of FMKKM-F
Klb
NMT
0.589
0.537
0.536
0.666
0.553
0,503
0.628
0.591
and FMKKM D&S.
0.666
0.775
0.763
0.667
0.794
0.773
0.703
0.800
MNCE
0.971
0.989
0.987
0.971
0.990
0.989
0.978
0.991
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-an MKKM methods, including ONKC (25), MKCSS (55) DPMKKM 42), LFLKA [51), EMKC (38) OSLR [47], ASLR [46). CSAMKC [56]. FAMKKM 4T. 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 [1. we construct 12 kernels, including seven Gaus- sian kernels K x,) = exp (-1|x; Xy 2 with = v8 * D, where s varies in the range of (1. 2: 1,4 1, 8, and D is the average distance between samples; four polyno- mial kernels K xx)
{0, and 6 {2, 4); and a cosine ker- (x7 x1) / [[|x:|| ||x;]|). Finally, all kernels have been normalized through K (x,, xx) S/VKKK K (x,, x,) K (x,. x,) and then rescaled to [0, 1]. We use Accuracy (ACC) and Nor- malized Mutual Information (NMI) evaluate the clustering performance. Besides, we also use balance (Bal) (20 and Minimal Normalized Conditional Entropy (MNCE)
(a + xxxx,)) with
nel K (Xi, x,)
49 to evaluate fairness.
Specifically, Bal is defined as
min
Bal (C) = min
E [0. 1].
(22)
Niaa
where Numn and Nmar represent the number of instances in the smallest and the largest (in size) protected groups in cluster kk. respectively. MNCE is defined as
mine (-Σ,
log [Sankel
Imal
MNCE-
E(0.1].
(23)
C.
log
All metrics are the larger the better. Based on previous analysis of hyper-parameter setting, we search X as = 1, 2.... by observing the corresponding MNCE When the MNCE gets stable, i... the change of MNCE is smaller than 0.005, we stop the searching and use the current X. For
8

---

Table 2: Comparison results the multiple kernel setting. denoted in bold and underlined, respectively.
The best and second best results
Data sets
ONKC MKCSS
DPMKKM
LFLKA
EMKC
OSLR
ASLR
CSAMKC
FAMKKM
FMKKM-1
FMKKM
ACC
0.505
0.543
0.614
0.646
0.491
0.590
0.508
0.598
0.501
0.645
0.616
NMI
0.644
0.665
0.697
0.717
0.602
0.677
0.591
0.668
0.678
0.718
0.661
D&S
0.471
MNCE
0.333
0
0.333
0.622
0.501
0.649
0.598
0.476
0.585
0.985
ACC
0.526
0.646
0.692
0.695
0.732
0.717
0.574
0.668
0.705
0.697
0.791
NMI
0.557
0.670
0.622
0.622
0.656
0,650
0.549
0.558
0.642
0.655
0.752
HAR
Bal
0
0
0
0
0.263
MNCE
0.933
0.920
0.914
0,917
0.520
0.928
0.888
0.990
ACC
0.397
0.457
0.391
0.412
0.415
0.406
0,436
0.398
0.445
0.412
0.495
MNIST-USPS
NMI
0.400
0.442
0.359
0.407
0.406
0.406
0.449
0.382
0.402
0.416
0.454
Bal
0.024
0.808
MINCE
0
0.161
0
0.993
ACC
0,840
0.956
0.911
0.934
0,948
0.939
0.995
Jaffe
NMI
0,848
0.958
0,924
0.887
0.964
0,903
0.936
0.925
0.971
0.914
0.991
Bal
0,200
0
0
0.250
0
0,540
MNCE
0.542
0,880
0.826
0.964
0.923
0.686
0.917
0.970
0.895
0,989
ACC
0.402
0.333
0.363
0.360
0.337
0.370
0.321
0.327
0.355
0.378
0.375
Credit Card
NMI
0.141
0.139
0.126
0.135
0.119
0.138
0.103
0.091
0.123
0.148
0.147
Bal
0,547
0.558
0,523
0.590
0.557
0.599
0.587
0.497
0.571
0.559
0.641
MNCE
0,960
0.964
0,950
0.975
0.963
0.977
0.973
0.938
0.969
0.964
0.989
0.749
Klb
NMI
0.435
0.535
0,286
0.545
0.436
0.523
0.652
0.554
0.581
0.632
0.601
Bal 0.428
0,794
0.545
0.818
0.881
0.854
0.714
0.892
0.849
0.757
0.935
MICE
0.881
0.991
0.937
0.993
0,997
0.994
0.980
0.9518
0,995
0.986
other comparison methods, we follow their recommended parameter configurations and search methodologies. All experiments are conducted on the 12th Gen InterI(R) Core(TM) i7-12700 with 32 GB RAM. All experiments are repeated 10 times and the average results are reported.
5.2 Experimental Results
Table 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 presents the comparison results in the multiple kernel setting. FMKKM easily achieves the best fairness, due to the effectiveness of our faimesss 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 achieve competitive clustering performance, demonstrating that our method is simple yet effective.
Figure I shows the visualization results. It shows the number of instances of each protected group Gj in each cluster 'T in the D&S data set obtained by FMKKM-f and FMKKM, respectively. As shown in Figure
I [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 [ (b) shows that the distribution of protected group in each cluster more balanced, which means the result obtained by FMKKM is much fairer than FMKKM-F. It demonstrates the effectiveness of our fair regularization term.
5.3 Efficiency Results
The convergence curves of our methods are shown in Appendix 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
5.4 Parameter Study
Figure 2aaree 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

---

145
015
0.4
MNCE
NMI
(a) NMI on USPS (FKKM)
Mb MNCE on MNIST-(O) NMI on Credit Card (d) MNCE on
Credit
USPS (FKKM)
(FKKM)
Card (FKKM)
MNCE
MNCE 808
N0N1
NOM
NMI on (f MNCE on MNIST-(g) NMT on Credit Card (h) USPS (FMKKM)
MNCE on Credit
USPS (FMKKM)
(FMKKM)
Card (FMKKM)
Figure 2: NMI and MNCE our methods on MNIST-USPS and Credit Card data sets w.r.t different values of X. The red points represent the lambda that algorithm automatically searches for.
with the increase of X, the fairness grows and the clustering performance may decrease, which is consistent with our previous discussion. We can often achieve good trade-off between fairness and performance at the red point, which shows the effectiveness of our hyper- syper-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 novel FKKM and FMKKM method. We also provided hyper-parament methods easy to use. Extensive experiments demonstrated the effectiveness and superiority of our proposed FKKM and FMKKM methods.
setting strategy based on the theoretical analysis to make the
Although the proposed methods achieve promising performance on fairness, they still have some limitations. For example, in methods, the protected groups must be pre-given 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.
Acknowledgments
This work is supported by the National Natural Science Foundation of China grants 62176001 and 62376146, and Natural Science Project of Anhui Provincial Education Department grants 2023AH030004.
References
[1] M. Abbasi, A. Bhaskara, and S. Venkatasubramannin. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pages 504-514, 2021.
[2] K. Altun, B. Barshan, and O. Tunçel. Comparative study on elassifying human activities with miniature inertial and magnetic sensors. Pattern Recognition, page 3605-3620, Oct 2010.
[3] D. Anguita, A. Ghio, L. Oneto, X. Parra, and J. Reyes-Ortiz. A public domain dataset for human activity recognition using smartphones. The European Symposium Artificial Neural Networks, The European Symposium on Artificial Neural Networks, Jan 2013.
[4] A. Backurs, Indyk, Onak, B. Schieber, A. Vakilian, and Wagner. Scalable fair clustering. In International Conference Machine Learning, pages 405-413. PMLR, 2019.
10

---

[5] P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 2002.
[6] Bera, D. Chakrabarty, N. Flores, and M. Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32, 2019.
[7] I. O. Bercea, M. GroB, S. Khuller, A. Kumar, C. Rösner, D. R. Schmidt, and M. Schmidt, On the cost of essentially fair clusterings. arXiv preprint 1eXiv:8111.133111 2018.
[8] A. Chhabra, P. Li, P. Mohapatra, and H. Liu. Robust fair clustering: A novel fairness attack and defense framework. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023,
[9] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5029-5037, 2017.
[10] I. S. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 551-556, 2004.
[11] L.. Du, P. Zhou, I. Shi, H. Wang. M. Fan, W. Wang, and Shen. Robust multiple kernel k- means using 121-norm. In Twenty-fourth international joint conference artificial intelligence, 2015.
[12] M. Ghadiri, S. Samadi, and S. Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, Mar 2021.
[13] G. Hamerly and Elkan. Learning the k k-means. Advances in neural information processing systems, 16, 2003.
[14] T. Handhayani and L. Hiryanto. Intelligent kernel k-means for clustering gene expression. Procedia Computer Science, 59:171-177, 2015.
[15] L. He and H. Zhang. Kernel k-means sampling for nyström approximation. IEEE Transactions on Image Processing, 27(5):2108- 2120, 2018.
[16] D. S. Hochba. Approximation algorithms for np-hard problems. ACM Sigact News, 28(2))40-52, 1997.
[17] Huang, F. Nic, and H. Huang. Spectral rotation versus k-means in spectral clustering. Proceedings of the AAAI Conference on Artificial Intelligence, page 431 Jun 2022.
[18] M. Kleindessner, S. Samadi, P. Awasthi, and J. Morgenstem. Guarantees for spectral clustering with fairness constraints. In International conference on machine learning, pages 3458-3467. PMLR, 2019.
[19] M. Li, Y. Zhang, S. Liu, Z. Liu, and X. Zhu. Simple multiple kernel k-means with kernel weight regularization. Information Fusion, 100: 101902, 2023.
[20] P. Li, H. Zhao, and H. Liu. Deep fair clustering for visual learning. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9067-9076, June 2020.
[21] J. Liu, X. Liu, J. Xiong, Q Liao, S. Zhou, S. Wang, and Y. Yang. Optimal neighborhood multiple kernel clustering with adaptive local kernels. IEEE Transactions Knowledge and Data Engineering. 34(6)) 2020.
[22] Liu, D. Tao, and D. Xu. Dimensionaliiy-ddeeneerr generalization bounds for k-dimensional coding schemes. Neural computation, 28(10):2213-2444 2016.
[23] X. Liu. Simplemkkm: Simple multiple kernel k-means. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):5174-5186, 2022.

---

[24] X. Liu, S. Zhou, L. Liu, C. Tang, S. Wang, J. Liu, and Y. Zhang. Localized simple multiple kernel k-means. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2021.
[25] X. Liu, S. Zhou, Y. Wang, M. Li, Y. Dou, E. Zhu, and J. Yin. Optimal neighborhood kernel clustering with multiple kernlss. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
[26] X. Liu, X. Zhu, M. Li, L. Wang, E. Zhu, T. Liu, M. Kloft, D. Shen, J. Yin, and W. Gao. Multiple kernel & k-means with incomplete kernels. IEEE transactions on pattern analysis and machine intelligence, 12(5):119--1044 2019.
[27] L. L.. Wang, J. Lu, J. Yang, and C. Shen. Multiple kernel clustering based on centered kernel alignment. Pattern Recognition, 47(11):3656-3664 2014.
[28] Y. Lu, X. Zheng, J. Lu, R. Wang. F. Nie, and Li. Self-paced and discrete multiple kernel means. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 4284 4288, 2022.
[29] M. J. Lyons, S. Akamatsu, M. Kamachi, Gyoba, and J. Budynek. The japanese female facial expression (jaffe) database. In Proceedings of third international conference on automatic face and gesture recognition, pages 14-16, 1998.
[30] A. Maurer and M. Pontil. k-dimensional coding schemes in hilbert spaces. IEEE Transactions on Information Theory, 56 56(11):5839-5846 2010.
[31] A. Maurer and M. Pontil. K -dimensional coding schemes in hilbert spaces. IEEE Trans. Inf. Theory, 56(11) 1):58)9--5845 2010.
[32] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan. A survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 1-(6) 2021.
[33] A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
[34] R. Pan and Zhong. Fairness first clustering: multi-stage approach for mitigating bias. Electronics, page 2969, Jul 2023.
[35] Y. Pang. J. Xie, F. Nie, and X. Li. Spectral clustering by joint spectral embedding and spectral rotation. JEEE Transactions on Cybernetics, page 247-258, Jan 2020.
[36] A. Saxena, G. Fletcher, and M. Pechenizkiy. Fairsna: Algorithmic fairness in social network analysis. ACM Computing Surveys, 2022.
[37] M. Schmidt, C. Schwiegelshohn, and C. Sohler. Fair coresets and streaming algorithms for fair k-means. In Approximation and Online Algorithms: 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers 17, pages 232-251. Springer, 2020.
[38] C. Tang, Z. Li, W. Yan, G. Yue, and W. Zhang. Efficient multiple kernel clustering via spectral perturbation. In Proceedings of the 30th ACM International Conference on Multimedia, pages 1603-1611, 2022.
[39] G. Tzortzis and A. Likas. The global kernel k-means clustering algorithm. In 2008 IEEE International Joint Conference Neural Networks (IEEE World Congress Computational Intelligence), pages 1977-1984. JEEE, 2008
[40] B. Wang and Davidson. Towards fair deep clustering with multi-state protected variables. arXiv preprini arXiv: 1901:1901..0033 2019.
[41] J. Wang, C. Tang, X. Zheng, X. Liu, W. Zhang, E. Zhu, and X. Zhu. Fast approximated multiple kernel k-means. IEEE Transactions on Knowledge and Data Engineering, 2023.
[42] R. Wang, J. Lu, Lu, F. Nie, and X. Li. Discrete and parameter- free multiple kernel k-means. IEEE Transactions on Image Processing, 31:2796-2803 2022.
12

---

[43] R. Wang, J. Lu, Y. Lu, F. Nie, and X. Li. Discrete and parameter- free multiple kernel k k-means. IEEE Transactions on Image Processing, page 2796-2808, Jan 2022.
[44] D. Yan, L. Huang, and M. Jordan. Fast approximate spectral clustering. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 907-916, 2009.
[45] D. Yin, R. Kannan, and P. Bartlett. Rademacher complexity for adversarially robust generaliza- tion. In International conference on machine learning, pages 7085-7094. PMLR, 2019.
[46] You, Z. Ren, Q. Sun, Y. Sun, and X. Li. Approximate shifted laplacian reconstruction for multiple kernel clustering. In Proceedings of the 30th ACM International Conference on Multimedia, pages 2862-2870, 2022.
[47] J. You, Z. Ren, F. R. Yu, and X. You. One-stage shifted laplacian refining for multiple kernel clustering. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[48] M. B. Zafar, I. Valera, M. Gomez-Rodrriguzz, and K. P. Gummadi. Fairness constraints: A mechanism for fair classification. CoRR, abs/1507.05259, 2015.
[49] Zeng, Li, Hu, D. Peng, Lv, and X. Peng. Deep fair clustering via maximizing and minimizing mutual information: Theory, algorithm and metric. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023, pages 23986-23999 IEEE, 2023.
[50] R. Zhang and A. I. Rudnicky. A large scale clustering scheme for kernel k-means. 2002 International Conference Pattern Recognition, volume 4, pages 289-292. IEEE, 2002.
[51] T. Zhang, X. Liu, L. Gong. S. Wang, X. Niu, and L. Shen. Late fusion multiple kernel clustering with local kernel alignment maximization. IEEE Transactions on Multimedia, 25:993-1007, 2021.
[52] L. Zheng, Y. Zhu, and J. He. Fairees-awware multi-view clustering. In Proceedings of the 2023 SIAM International Conference Data Mining (SDM), pages 856-864. SIAM, 2023.
[53] S. Zhong and J. Ghosh. Generative model-based document clustering: comparative study. Knowl. Inf. Syst., 8(3):374-384, 2005.
[54] P. Zhou, L. Du, L. Shi, H. Wang, and Y. Shen. Recovery of corrupted multiple kernels for clustering. In Q. Yang and M. J. Wooldridge, editors, Proceedings of the Swenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 4105-4111. AAAI Press, 2015.
[55] Zhou, X. Liu, M. Li, E. Zhu, Liu, C. Zhang, and J. Yin. Multiple kernel clustering with neighbor-kernel subspace segmentation. IEEE transactions neural networks and learning systems, 3154):135- 2019.
[56] S. Zhou, Q Ou, X. Liu, S. Wang, I.. Liu, S. Wang, E. Zhu, J. Yin, and X. Xu. Multiple kernel clustering with compressed subspace alignment. IEEE Transactions on Neural Networks and Learning Systems, 34(1):252-263, 2021.
[57] I. M. Ziko, J. Yuan, E. Granger, and I. B. Ayed. Variational fair clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11202-11209, 2021.
[58] I. M. Ziko, J. Yuan, E. Granger, and Ben Ayed. Variational fair clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):1 1202-11209, Sep 2022.
13

---

A Pseudo-codes of FKKM and FMKKM
Algorithms
1 and
show the pseudo-codes of our FKKM and FMKKM, respectively.
Algorithm Fair Kernel K-means
Input: Kernel matrix K, protected groups 91, ... , fairness hyper-parameter X.
1: Construct protected group indicator matrix G and calculate
[9maa A.
2: Construct the fair kernel by K K + al XGG""
3: Initialize Y by rumning standard kernel k k-means on K.
4: repeat
5: Update Y row by row by maximize Tr (Y"KY (Y"
6: until Converges
Output: The final partition matrix Y.
Algorithm Fair Multiple Kernel K-means
Input: Kernel matrices (K(p) pp=1 protected groups 91, 9t. fairnsss hyper-parameter X.
1: Construct protected group indicator matrix G and calculate
19maa A.
2: Construct the corresponding fair kernel by K K(r) + oI XGGT for each base kernel
matrix K(P).
3: Initialize 7 and Y by running standard kernel k-means on Σp= 7pp (2(())
4: repeat
5: Update row by row by solving 16.
6: Update 7 by (q.
7: until Converges
Output: The final partition matrix Y.
B Proof of Theorem 2
Denote R (M, 7) Ei= minye (c.......) 1 (xx) My Our goal is to bound:
[X[(x) - 1 Σ (xx) (x))
sup fEF
(24)
According Assumption 2 have the largest value of elements in K(p) is b. Now, consider
((r) (p) + al XGG T Since the diagonal elements of GG" are 1, given any x;, have
that T (x,) 2y (x.) = p= 7/2 " (xx) 2 (x+) S b + a X. Given two different instances X; and Xj. if they belong the same protected group, we have that the (i.j)-th element in GG" is and thus &L (x:) B (x,) = Ep= >p 22 (x,) o (x,) < b X. If x; and x, belong to different protected groups, we have that the 1-th element in GGT O, and thus & (x,) 2, (x₂) = Ep 22 (x;) p (x,) < b. Then, notice that
b (xx) My 1 min {llee (xx) ye(ei....e.)
min
my 11.122 ... 1 (xx) mell?]
(25)
where m. denotes the k-th cluster centroid. Next, we denote a, = TH 0 n to represent the number of instances in all protected groups in cluster mT. We have:
14

---

2
1 (x.) m mx112
$ (x:)
|Tb Σ By (x,)
jENU
2
(x, (x;)
Σ
pxp) "T (xa)
7
TT
EPETN X,, ET
(|+x) (b +b+a- - 2) + EE as - -\
2) + (ITE|
Ei=
2
a 1)
|TT
= 2 bb 1) |x/0 A Ei= i== a? + b/TT/l?
TT
2 0 - A+b b
+
TT
<4(b+a) - 2 (1+ 7)
(26)
Eia 0s
The second last inequality holds due to the Cauchy-Schwarz inequality E ay and Σ a; = | Therefore, we have:
>
0 $ ( - 2111
(27)
According the Theorem 3.1 in 30), by utilizing McDiarmid's inequality, have that for any 5 2 0, with probability at least
6, for all f E F, the following inequality holds:
B[f(x)] - 1 Σ (xx) s 2F) + 44 + a) - -2(1+1) (1)
log((10)
V
(28)
2n
where:
R. (F) = E
sup
orf (x:)
(29)
fer
represents the Rademacher complexity of F uniformly distributed on 1}. Next, introduce the Gaussian complexity provide upper bound for (FF 5
01.... Tn are Rademacher random variables
G, (F)
E
sup JEF
Bif (x,)
(30)
where BI,..., 3n are Gaussian random variables with zero mean and unit standard deviation. To bound the Rademacher complexity, we need the following two lemmas:
Lemma
123 Ri,
Lemma 3 123 Let G = = 3.G (x,, f) and H Σ 3.H (xi, f) be two zero-mean sepa-
rable Gaussian processes. for all f1, F.
E [G G1,)21
S (H,, H1,)
(31)
then we have:
E
sup G₁ feF
< E
sup H3
(32)
SEF
15

---

In our setting, we define:
n
(xx; = GM. -
Σ 3 i=1
min (ese.....e
1 (x,) Myll3
(33)
Next, we aim to find y (i.c., HNI,) such that:
Es (GMII. GManss) )²]
s Eg (HMMm HMMan)) )
(34)
Specifically, for any f1, f2 E F, we have:
min [| (xx) - M min 12 (x:) - May l2x )²
y
max (1)07, (xi) Miy l2u - 1| (xi) - Mayl
M3) max {2 ( (x,) M2 -0, (x,) (x.) y + (MF TTTM.-M3j (MFM)-MM(M)) xr) ) ?
(1077 (xs) ||07 (xx) 11x))
y
(1(7) (xs)]l || (xx)) max 2 T (x,) M2 22 (x,) (x)) y + maxy" (MMM Mb)
(l (xx)ll T2 (x) max Σ 2/ (0 (x.) M2 D2 (x.) Mi) o
2
+ max Σ yr
- My (MMM es
<1 01 (xx) 11 - -1 (xx))l?²) + max 2
E
(TT (x:: M2 - -02, (xx) M,) er
y
2
+ 4 max Σ V.yue (MMM. -M)MM)
r===
<4 P1 )x - -2 (xx))1+)* +8 Σ (( (oTs (x:) Mr - -07, (xx) (xx) e.)²
+ 4 Σ (e. (M.M, - M²M,) ex) 2
(35)
The final two inequalities hold due to (a + b + c)² < 4a² + 26 + 4c², Ei= Vr = 1, and En Drys = 1. Therefore, combining Eq. (3) and Eq.(35). we have:
Ep [(GMm =G
Σ min 1r (x:) - Myyl min 18 (xx) Maylla 1)
=Ba
n
min || (xx:) Miyll min 1|0r (xx) May )
Σ
4 (1 (x:))l 11 (xx)) +8 Σ ((0% (xx) M2 -0, (xx) (x:)MM) ).)))
c (MF - MOMs) e.) 2
1,am1
-Eg [HM HManz)
(36)
Then, we obtain HM,y as follows:
HM, =2 3z T (x:) 2 + 2/2
= i=1
Σ
3rr
T (x:) Me, + 2 2 Σ
B T R Me.-
1=1==
r,s=1
(37)
16

---

To bound the expectation of HM,Y, we introduce the following Lemma from [1
Lemma 4 (37 Suppose that
1) (e, : Sr c) is orthonormal busis of ;
2) M the class of linear operators M : R + H with ||Mer S
3) (x: S S n) is sequence in H. H.||x p
4) (3,, isis n, and (Birs 1 S i S n, T, S, r) orthogaussian (independent
and N (0, 1) sequences.
Then the following three inequalities hold:
Es sup MEM
Bir (ct, Me.) S wuevn,
(38)
Es sup MEM
Bir |M Sw²cnn
(39)
i=1 rm
ES sup MEM
S u Pirs (Me, Me.)
(40)
r,a=1
where (.-)) denotes the inner production.
In method, given instance x,, we have that || (x+) 2/ (x:) (xx) S b a X.
Moreover, we also have ||Mrllæ S /b b + a À according to Eq.(26) As result, according to Lemma 4 the expectation of HM,y can be be bounded as follows,
Es
sup HM, FEF
n B t y (x,) Mc, +
-Eg
sup 2 SEF
8/ T (x:)
+222 Σ>
Σ
Pire Mc,
r,0=1
<2EB
sup
8: 17 (x:)]l
+ 22/2EB
sup
Bir T (xi) Me,
+ 21E,
sup Birs e M Me, |EF
FEF i=1
/EF
1=1 1=1
<2 A) V + +201/00 a(b+a-11 1) (b+a - 7 n2 + 20
b (b+a - 2) vn
=2/7 (1
(1+ c² ) G 2(b 2 -
-1 (b+a- à)
(41)
Last, we can bound R,, (F) with Lemma
Lemma
Eq. 29
Eq.
30
and Eq. 41
R, (F) < -V T/2 Eg
sup GM,Y FEF
-- 7/2 Egg
sup HM, FEF
2m
(1 (1+ (b - (1+ -(1) = a 2(b+a A)
2
b (b+a-
Vn
(42)
17

---

Substituting Eq. 42 into Eq 28 all F, the following holds:
we finally obtain for any 8 2 0, with probability at least 1 - 6, for
[x](
Σ 1=1
f (x.)
+
2 2T
(1+ (b+
- (1+ 7 + o 2 2(b+a (b+a-
Vn
1 + 1 8
log(1/0)
+ - 2
(43)
2n
This concludes the proof.
C Proof of Lemma 1
Since a is the smallest eigenvalue of A, and σ is the largest eigenvalue of B, we have:
A 0 -
(44)
Ø B
(45)
Summing up Eq. and Eq. 45. we have:
B (aΛ oB) 120. 0.
(46)
Considering the smallest eigenvalue of A B, denoting as Oa-Bs Bs and its corresponding eigenvector
VA-B. we have (A B) VABB = OA-BVA-B. Multiplying the left-hand side of Eq.446 with
A-B and VA-B Bs have
v B (A - B (01-
=V A- (OA-B
OBB)
= (αΛ - -n)) 1/
(47)
Notice that (A- B (a σB) 1) is positive semi-definite according to Eq. (4).. which means V (A (σ σB) V--B 2 0. Therefore, JA-B ( σB) 2 0, and thus O BB3 2
σΛ 0g 0. This means that A B positive semi-definite, which concludes the proof.
D Statistical Information of Data Sets
We conduct experiments on benchmark data sets which are widely used in fair clustering, including D&S 22, HAR 3 Jaffe [29], MNIST-USPS 220, Credit Card [52] and Klb [53]. D&S human daily and sports activities data set including 8 participants. HAR is human action recognition data set including 30 participants.
both D&S and HAR data sets, the data of each participant form protected group. Jaffe is face image data set. Following [20], the face images with the same expressions are put into protected group. MNIST-USPS 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 data set that describes the customers' default payments and the data males and females form two protected groups respectively. K.lb is a text data set. Following [48]. randomly assign each text to protected group with Bernoulli distribution whose = 0.5 to form two protected groups. Details of the data sets are shown in Table
E
Introduction of Compared Methods
To show the effectiveness of our method on clustering performance and fairness, we compare our method with some oftteoof-the-ar fair clustering and multiple kernel k-means methods, including:
SpFC 18
which integrates faimess constraints into the Laplacian matrix of graph.
VFC
58
which is universal variational fair clustering framework.
18

---

Table 3: Description of the data sets.
Data sets
# of Instances
# of Features
# of Cluster
Protected Groups
D&S
9120
5625
19
Person Identity (8)
HAR
10299
561
Person Identity (30)
MNIST-USPS
3800
256
10
Source of images (2)
Jaffe
213
676
10
Expression (7)
Credit Card
5000
22
Gender (2)
Klb
2340
21839
Synthetic Binary (2)
FFC
34
which is three-stage fair clustering method based on k-means method.
which is an optimal neighborhood kernel clustering algorithm to enhance the representability of the optimal kernel.
ONKC 25
MKCSS [5 which is simple yet effective
MKC algorithm to consider the intrinsic neighborhood structure among base kernels.
DPMKKM 42), which is novel discrete multiple kernel k-means by directly solving the clustering indicator matrix.
LFLKA 51. whihe is simple late fusion multiple kernel clustering with local kernel aligmment maximisation approach.
EMKC [38] which is effective multiple kernnel k-means by introducing spectral perturba- tion theory to laplacian matrix.
OSLR [47
which one stage multiple kernel k-means by refining shifted laplacian
matrix.
ASLR
46 which a effective multiple kernel k-means by reconstructing the laplacian
matrix.
CSAMKC [6 which is a fast multiple kernel k-means by adopting novel sampling strategy to improve the performance of MKC.
FAMKKM 4 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.
F Efficiency Results
Figures and show the convergence curves of FKKM and FMKKM, respectively, We can see that our methods converge very fast and they often converge within iterations.
and show the running time of all methods on single kernel setting and multiple kernel setting, respectively. For better comparison, we report the logarithm the time (in seconds). From Figures 55 6) we can see that our FKKM and FMKKM are faster than or at least comparable with many state-of-the-ar methods, which well demonstrates the efficiency of our methods.
19

---

x10
5750.00
2.38
5740.00
5730.00
0
obi
2.36
5720.00
5710.00
2.34
5700.00
10
15
20
10
20
#iterations
#iterations
D&S
(b) HAR
x10
391.50
1.85
391.00
Obj
O
1.80
390.50
1.75
390.00
10
15
20
0
10
15
20
#iterations
#iterations
(c) MNIST-USPS
(d) Jaffe
x10
6398.00
1.35
6396.00
1.35
Obj
1.35
O
6394.00
1.34
6392.00
1.34
6390.00
10
15
20
10
20
#iterations
#tterations (f) klb
(c) Credit Card
Figure 3: Convergence curves of all data sets on single kernel setting.
20

---

10
x10
8.64
3.50
8.64
Obj
obi
3.50
8.64
8.64
3.50
10
15
20
0
5
10
15
20
#iterations
#iterations
D&S
(b) HAR
472.6
6.32
6.32
472.5
Obj
6.32
Obj
6.32
472.4
6.32
6.32
472.3
10
15
20
5
10
15
20
#iterations
#iterations
(c) MNIST-USPS
(d) Jaffe
x 6
x10
1.23
2.34
1.23
Obj
2.34
1.23
1.23
2.34
10
15
20
5
15
20
diterations
#iterations
(c) Credit Card
(f) klb
Figure 4: Convergence curves of all data sets on multiple kernel setting.
21

---

Logarithm of the running Lime (in Sec.)
Logarithm the running time (In Sec.)
K-monns
KKM
KKM
SC
FairSC
FabrC
VFC
3
FFC
FFC
FXKM
FKXM
Methods (a) D&S
Methods (b) HAR
Logarithm of the running time (In Sec.)
L Logarithm of the time (in Sec.)
K-moons
K-maoas
KKM
KKM
SC
FwirSC
vFC
VFC
-1
FFC
BFC
-2
FKKM
FKKM
3
Methods (c) MNIST-USPS
Methods (d) Jaffe
Logarithm of the running time (in Sec.)
Logarithm the running time (in Sec.)
K-msons
K-msons
KJM
KKM
3
Fairsc
Pakrc
VFC
VFC
FFC
FFC
-1
22
Methods (c) Credit Card
Methods
Klb
Figure Running time of all methods on the single kernel setting.
22

---

Logarithm the running time Sec.)
Logarithm of the running time (in Sec.)
ONKC
ONKC
MICSS
MKCSS
FFLKA
ITLKA
FMKC
FMKC
ASLR
ASLR
4
CSAMKC
CSAMKC
FMKKN
FXIKKN
Methods (a) D&S
2
Methods (b) HAR
8
10
Logarithm of the running time (In Sec.)
Logarithm the running time (in Sec.)
MKCSS
MKCS8
-05
DPMKKM
OPMKKM
FMKC
-1.5
FMKC
OSLR
CSAMKC
(2
CSAMKC
FANKKM
FANKKN
-35
Methods (c) MNIST-USE
Methods (d) Jaffe
10
Logarithm the running time (in Sec.)
Logarithm of the running time (in Sec.)
ONKC
ONKC
ПPMKKM
5
OPMKKM
LFLKA
LILKA
OSLR
DSLR
ASL.R
2.
FAMKKM
FAMKKM
FMKKM
FMKKM
M Methods (c) Credit Card
MMethods
Klb
Figure 6: Running time of all methods on the multiple kernel setting.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section Conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
We provide the proofs of all theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the detailed experimental settings and the codes.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer: [Yes]
Justification:
We provide the codes.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeee //nips.com / cassiicnncccyyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We provide the detailed experimental setting.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have computed the standard deviation but due to the space limit, do not report this in the manuscript. We can provide it requested.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
26

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the detailed experimental setting.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://urrrpppccppoo......aaaaaa
Answer: [Yes]
Justification:
We conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact 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.
27

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [Yes]
Justification: All used assets are cited.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "JI7CUED8XZ", "reviewer": "Reviewer_dRCy", "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.", "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?\n2.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?\n3.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?\n4.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?\n5.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?\n6.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?\n7.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?\n8.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?\n9.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?\n10.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": "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.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.The introduction of a fairness regularization term is a significant innovation that addresses the often overlooked issue of fairness in kernel K-means clustering.\n2.Expanding the method to a multi-kernel setting (FMKKM) adds versatility and applicability to a broader range of clustering tasks.\n3.The paper provides theoretical analysis, including a generalization error bound, and offers a strategy for hyperparameter settings, adding rigor to the proposed methods.\n4.The methods are validated through experiments, showing their effectiveness in achieving fair clustering results.", "weaknesses": "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.\n2.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.\n3.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.\n4.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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.  \n\nW2. 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.\n\nThe 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.\n\nW3 & 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. \n\nW4 & 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.\n\t\nQ1.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. \n\nQ2. 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.\n\nQ3. 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$.\n\nQ4 & 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.\n\nQ6. 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. \n\nQ9 & 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].\n[1] On the Consistency and Large-Scale Extension of Multiple Kernel Clustering. In TPAMI 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5d2xsPxcX7", "reviewer": "Reviewer_GAQw", "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.", "questions": "1. How does the proposed method perform on very large-scale datasets? Are there any scalability issues?\n2. Have the authors considered extending the fairness concept to other clustering algorithms beyond kernel k-means?\n3. How sensitive are the proposed methods to the choice of initial kernels in the multiple kernel setting?\n4. Can the proposed fairness regularization term be adapted to other machine learning tasks beyond clustering?", "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.\n2. While the method often achieves good performance on both metrics, there might be cases where improving fairness significantly impacts clustering quality.\n3. The approach is specifically designed for kernel-based clustering, which may limit its applicability to non-kernel-based clustering algorithms.\n4. The paper focuses on a specific definition of fairness, and it's unclear how the method would perform under alternative fairness criteria.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces a new fairness regularization term that can be easily integrated into kernel k-means frameworks.\n2. The authors provide thorough theoretical analysis, including proofs of the fairness optimization and generalization error bounds.\n3. The method is extended from single kernel to multiple kernel settings, showing its adaptability.\n4. The paper offers a strategy for setting hyperparameters based on theoretical analysis, making the method more accessible for practical use.\n5. The authors conduct extensive experiments on multiple datasets, comparing their methods against various state-of-the-art approaches in both single and multiple kernel settings.\n6. The proposed methods demonstrate fast convergence and competitive running times compared to existing methods.", "weaknesses": "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?\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nW2. 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.\n\nQ1. 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. \n[1] On the Consistency and Large-Scale Extension of Multiple Kernel Clustering. In IEEE TPAMI 2023.\n\nQ2. 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.\n\nQ3. 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. \n\nQ4. 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.\n\nL2. 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.\n\nL3. 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.\n\nL4. 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "adrkSjUxZv", "reviewer": "Reviewer_t6xq", "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.", "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": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.The fairness is an important issue in machine learning. Although kernel k-means have been widely studied in recent decades, fairness is seldom considered in these kernel methods. The paper considers the fairness for kernel methods, which can make contributions to the community.\n2.The proposed methods are simple, elegant, and effective. After integrating the proposed fairness regularization term into kernel k-means, it is still a kernel k-means formula. The method only modifies the input kernel, but can achieve the fairness. This idea is interesting and novel.\n3.The paper is well-motivated and solid. To my knowledge, the derivations are reasonable. \n4.The paper is well-organized and easy to follow.\n5.The experiments are sufficient and convincing. The ablation study of comparing with FKKM-f and FMKKM-f reveals the superiority of the fairness regularization term.", "weaknesses": "1.In Tables 1 and 2, there are many “0”s in the results of Bal. Is that normal? If so, why?\n2.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.\n3.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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nW2. 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. \n\nW3. Thanks. We will revise these notations.\n\nQ1. 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:\n|          | |    K1b       |      |      |    |   Jaffe          |      |      |  \n|----------|--------|-------|------|------|------------|-------|------|------|\n|          | ACC    | NMI   | Bal  | MNCE |ACC        | NMI   | Bal  | MNCE |\n| KKM      | 0.669  | 0.537 | 0.775| 0.989| 0.948      | 0.922 | 0    | 0.900|\n| KKM-fair | 0.573  | 0.444 | 0.818| 0.993| 0.985      | 0.974 | 0.333| 0.978|\n\n|          |  |   Credit|      |      |         |    D&S   |      |      |\n|----------|-------------|-------|------|------|------------|-------|------|------|\n|          | ACC         | NMI   | Bal  | MNCE | ACC        | NMI   | Bal  | MNCE |\n| KKM      | 0.381       | 0.140 | 0.550| 0.961| 0.552      | 0.602 | 0    | 0.530|\n| KKM-fair | 0.403       | 0.145 | 0.570| 0.968| 0.643      | 0.735 | 0    | 0.640|\n\n|          |   |    M-U|      |      |        |  HAR      |      |      |\n|----------|-------------|-------|------|------|------------|-------|------|------|\n|          | ACC         | NMI   | Bal  | MNCE | ACC        | NMI   | Bal  | MNCE |\n| KKM      | 0.396       | 0.421 | 0    | 0.003| 0.620      | 0.609 | 0    | 0.930|\n| KKM-fair | 0.401       | 0.358 | 0.045| 0.257| 0.765      | 0.691 | 0.009| 0.971|\n\nIt 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "515ZVcIc9h", "reviewer": "Reviewer_px1V", "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.", "questions": "Please see the Weaknesses.", "limitations": "The paper has analyzed the limitations.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. A novel fairness regularized term is proposed. It has the same form as the kernel k-means and can be seamlessly plugged into the kernel k-means framework.\n2. Some theoretical analyses are provided. The paper is technically sound.\n3. The paper also provides a strategy to tune the trade-off hyper-parameter $\\lambda$ based on the generalization error bound. This makes the proposed method easily applicable to new data.\n4. The experimental results on both the single kernel and multiple kernel settings are good, especially when comparing w.r.t. the fairness. It well demonstrates the effectiveness of the fairness regularized term.", "weaknesses": "1. The related work of fair clustering can be introduced in more detail.\n2. 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?\n3.  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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "W1. We will revise the related work to introduce the fair clustering methods in more detail.\n\nW2. 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. \n\nW3. 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)