Deep Fair Discriminative Clustering
Authors: Hongjing Zhang
Ian Davidson
Venue: ICLR 2022 Submitted (2022)
Keywords: Clustering
Deep learning
Fairness

Abstract: Deep clustering has the potential to learn a strong representation and hence better clustering performance than traditional clustering methods such as $k$-means and spectral clustering. However, this strong representation learning ability may make the clustering unfair by discovering surrogates for protected information which our experiments empirically show. This work studies a general notion of group-level fairness for both binary and multi-state protected status variables (PSVs). We begin by formulating the group-level fairness problem as an integer linear programming whose totally unimodular constraint matrix means it can be efficiently solved via linear programming. We then show how to inject this solver into a discriminative deep clustering backbone and hence propose a refinement learning algorithm to combine the clustering goal with the fairness objective to learn fair clusters adaptively. Experimental results on real-world datasets demonstrate that our model consistently outperforms state-of-the-art fair clustering algorithms. Furthermore, our framework shows promising results for novel fair clustering tasks including flexible fairness constraints, multi-state PSVs, and predictive clustering.

Under review as a conference paper at ICLR 2022
DEEP FAIR DISCRIMINATIVE CLUSTERING
Anonymous authors
Paper under double-blind review
ABSTRACT
Deep clustering has the potential lear strong representation and hence better clustering performance than traditional clustering methods such as k-means and spectral clustering. However, this strong representation learning ability may make the clustering unfair by discovering surrogates for protected information which our experiments empirically show. This work studies general notion of group-level fairness for both binary and multi-state protected status variables (PSVs). We begin by formulating the group-level fairness problem as an integer linear programming whose totally unimodular constraint matrix means it can be efficiently solved via linear programming. We then show how to inject this solver into a discriminative deep clustering backbone and hence propose refinement learning algorithm to combine the clustering goal with the fairness objective to learn fair clusters adaptively. Experimental results on real-world datasets demonstrate that our model consistently outperforms state-of-the-arr fair clustering algorithms. Furthermore, our framework shows promising results for novel fair clustering tasks including flexible fairness constraints, multi-state PSVs and predictive clustering.
INTRODUCTION
Clustering is essential as it is the basis of many Al tools and has been widely used in real-world applications involving humans (Jain et al. 1999) such as market research, social network analysis, and crime analysis. However, as Al tools augment and even replace humans in decision-making, the need to ensure clustering is fair becomes paramount. Here faireess is measured using protected status variables (PSVs) such as gender, race, or education level. Fairness takes two primary forms (Binns) fairness. In this paper, we study the former
2020): i) group-level fairness and ii) individual-lewe which ensures that no one cluster contains a disproportionately small number of individuals with protected status. Motivated by this goal, our work aims to add fairness rules to deep clustering.
Recent works (Rösner& Schmidt 2018, Schmidt et al.) 2019 Kleindessner et al. 2019b Backurs et al. 2019 Bera et al.) 2019) have been proposed for non-deep fair clustering algorithms. To ensure group-level fairness, many of these works use the notion of the disparate impuct doctrine encoded constraint, that instances from different protected groups must have approximately (within tolerance) equal representation in cluster compared to the population. Different geographic regions place this tolerance at different levels (Chierichetti al., 2017). These existing algorithms optimize the clustering quality by minimizing some well-known clustering objectives while satisfying the group-level fairness constraints. Previous examples of adding fairness to clustering algorithms include
k-median based approaches (Chierichetti et al. 2017 Backurs et al. 2019 Bera et al. 2019) and spectral clustering based algorithm (Kleindessner et al. [2019)) However, all these works evaluate their performance on low- di-emnsioiinal tabular data and (Chierichetti et al. 2017: Kleindessner et al. 2019b] Backurs et al. 2019) study the problems only with binary PSV.
Deep clustering (Xie et al, 2016 Hu et al. 2017; Guo et al. 2017] Wang et al. 2019) has the ability to simultaneously cluster and learn a representation for problems with large amounts of complex data (i.e., images, texts, graphs). However, the representation learning ability sometimes makes the learner suffer from bias hidden in the data which can lead to unfair clustering results. For example, clustering of portraits may create clusters based on features which are surrogates for racial and other protected status information. One way to overcome this is by adding group-level fairness to deep clustering which is challenging and understudied problem. A significant challenge is it is hard to translate the current fair clustering algorithms into an end-to-end deep clustering setting. For example, geometric pre-processing steps such computing fairlets (Chierichetti et al. 2017) ensure fairness will not

---

Under review as a conference paper at ICLR 2022
work the end-to-end learning of deep learners means the underlying features that clustering is performed on are unknown apriori. Similarly, another line of work that adds constraints into deep learning models such as (Xu et al.. 2018: Zhang et al. 2019) are not appropriate either these constraints are at the instance level, whereas we require to apply fairness rules at a cluster level.
The work fair deep clustering is relatively new. The first work on fair deep clustering (Wang & Davidson 2019) studies deep fair clustering problem from a geometric perspective which aims to learn fair representation with multi-state PSV. The most recent work (Li et al., (020) proposes deep fair visual clustering model with adversarial learning to encourage the clustering partition to be statistically independent of each sensitive attribute (PSV). Although these deep clustering approaches demonstrate better clustering performance compared to the traditional fair clustering algorithms (Table D their fairness results are relatively poor compared to those fair clusterings with fairness guarantees (Chierichetti et al., 2017 Backurs et al. 2019). Our work can be seen as combining the benefits of deep learning and discrete optimization to produce guaranteed fair predictions on clustered data with PSVs while making out-of-sample fair predictions for data without PSVs.
In this paper, we propose a novel deep fair clustering framework to address the above issues. We adopt probabilistic discriminative clustering network and learn a representation that naturally yields compact clusters. To incorporate the group-level fairness rules in the deep learner, we first formulate faimess objective as integer linear programming (ILP) problem that guarantees group-level fairness. This II.P is efficient to solve as its constraint matrix is totally unimodular. Further, we propose refinement learning algorithm combine the solved fair assignments and the clustering objective. Experimental results on real woold datasets demonstrate that our model achieves guaranteed fair results with competitive clustering performance. We also examine the novel uses of our framework in predictive clustering, flexible fair clustering, and challenging tasks with multi-state Vs.s. The major contributions of this paper are summarized as follows:
We optimize general notion of fairesss for multi-state PSVs which we prove is equivalent to optimize the general balance measure (Chierichetti et al. 2017) for disparate impact.
We formulate our fairness assignment sub-problem as an ILP which is NP-hard. We show that by relaxing our constraint matrix to be totally unimodular our sub-problem can be efficiently solved by an LP solver (but still generate integer solutions). (See Theorem 4.2)
We propose end-to-end refinement learning algorithm that combines deep learning and discrete optimization to learn fair representation for clustering. (See Algorithm
Extensive experimental results show that our work can achieve guaranteed fairness with competitive clustering performance. We demonstrate our novel extensions for fair clustering tasks in predictive clustering, multi-state PSVs and flexible faimess rules. (See Section 5.2)
In the next section 2 we discuss the related work. Then we outline our measure of fairness and how relates to classic measures of disparate impact in section 3 In our approach section 4 we introduce our clustering framework and encode our fairness objective as an ILP which can be efficiently solved via our relaxation. refinement learning algorithm is proposed for end-to-end fair clustering. Finally we empirically evaluate the effectiveness of our approach in section 5 and conclude in section
2 RELATED WORK
Fair clustering has received much attention recently (Schmidt al. 2019 Kleindessner al. 201 2a
Ahmadian et al., 2019: Chen et al., 2019 Davidson & Ravi] 2020 Mahabadi & Vakilian 2020
Brubach al. 2020). Chierichetti et al. (211)) first addressed the disparate impact for clustering problems in the presence of binary PSVs. Their work apriori groups instances into many fairlets which are used as input into standard k-medians style algorithms. Their work is guaranteed to produce a specified level of fairness and achieve constant factor approximation with respect to cluster quality. Backurs et al. (019) improves the fair decomposition algorithm to linear run-time. Later on, Bera et al. (2019) propose general fair clustering algorithm that allows human-specified upper and lower bounds on any protected group in any cluster. Their work can be applied to any clustering problems under l norms such as k-median, k-means, and k-center. Besides the centroid- based Kleindesse et al. (2019b) extends the fairness notion to graph spectral clustering problems. Ziko al. (2021) propose general, variational and bound-optimizztionn framework of fair clustering.
2

---

Under review as a conference paper at ICLR 2022
(a) Traditional Fair Clustering
(b) Deep Fair Clustering
Figure 1: Note the red and blue points instances with different PSV values. Traditional fair clustering (left) aims to find a fair partition of the data while minimizing some classic clustering objectives. Deep fair clustering (right) aims to learn general fair representation to cluster the data.
Previous fair clustering approaches mainly focus on adding faimess constraints into traditional clustering algorithms. In our work, we aim to study the fairness problem for recently proposed deep clustering algorithms (Xie et al. 2016 Yang et al. 2017 Hu et al. 2017; Caron al. 2018
Shaham et al. 2018 Tzoreff et al. [2018] Shah & Koltun 2018). Deep clustering algorithms connect
representation learning and clustering together and have demonstrated their advantages over the two-phase clustering algorithms which use feature transformation first and then clustering. The goal of deep fair clustering to learn fair and clustering-fate favored representation. We illustrate the basic intuitions behind traditional fair clustering methods and deep fair clustering approaches in Figure [
One of the carliest works (Wang & Davidson 2019) to address the deep fair clustering problem learns latent representation such that the cluster centroids are equidistant from every "fairoid" (the centroid of all the data belonging to the same protected group). Recently, Li et al. (2020) encodes the faireess constraints as adversarial loss and concatenates the faimess loss centroid-based deep clustering objective as a unified model. Unlike previous deep fair clustering works, we translate the fairness requirements into ILP problem that generates guaranteed fair solutions given the PSVs. Meanwhile, our formulation allows for general notion of fairness that supports flexible fairness constraints and multi-state PSVs. Moreover, we propose a novel learning framework to train fair clustering models via simultancous clustering and fitting the self- self-generated fairness signals.
3 DEFINITIONS OF GROUP-LEVEL FAIRNESS
We begin this section by overviewing the seminal definition of group-level fairness in clustering (see equation [ and then its extension multi-state PSVs (see equation 2). We then go onto show new measure that our deep clustering framework will optimize (see equation 3) and equation 2 havve the same optimal condition shown in Theorem 3.2
3.1 NOTION OF FAIRNESS
Let X E NxD denote N data points with D dimension features. The prediction function á assigns each instance to one unique cluster, Φ - {1, ...K). which forms K disjoint clusters [CI,,..Ck] Given the protected status variable (denoted as PSV) A with T states, X can be partitioned into T demographic groups as {G1, G2....Gr.
Definition 1.
The seminal proposed measure of fairness for clustering with binary PSV (Chierichetti et al. 2017 encoded disparate impact as follows:
N
N2
balance (CanneeeCC))CC))) = min(
[0,
Here No and N2 represent the populations of the first and second demographic groups in clus- ter Ck. Such a measure of fairness only works for binary PSV. To allow for multi-state PSVs, let Nrmán min(NL ... NT') denotes the smallest (in size) protected group in cluster and Nmaa max(NV ... NT) denotes the largest group. We extend the balance measure for multi- state PSV as:
Nyan Niaa
balance
[0,
Recent works (Rösner& Schmidt, 2018 Bera et al. 2019) also propose a new fairness measure to allow for fair clustering problems with multi-state PSVs.
3

---

Under review as a conference paper at ICLR 2022
Definition 2. Let pt be the representation of group G; in the dataset as p. |G,|/N, and pi(k) be the representation of group G₃ in the cluster Cs: Pı(k) = |C n.l//G/ Using these two values, the faimess value for cluster Cg is:
fairness(Cs) = min( P
p.(k) ) pi(k)' E [0,1]
Vi (1....
(3)
The overall fairness of a clustering is defined as the minimum fairness value over all the clusters. Similarly, the overall balance is the minimum balance value of all the clusters.
3.2 EQUIVALENCE OF OPTIMIZING FAIRNESS AND BALANCE MEASURES
Here we show that optimizing equation 3 is equivalent to optimizing our extended definition of balance
in cquation 2 We see that equation 3 achieves maximal fairness when P(æ E G, E C²) = Pt- for any protected group G; in cluster Cs. However, this is an ideal case as protected groups may be imbalanced. Denote the size of each protected group as |G, and the size the data set as N, we now show that the optimal balance is achieved if and only if P(x E G.|æ E C²) Pr. This result indicates the equivalence of optimizing fairness (equation 3) and generalized balance (equation 2
Our balance measure in equation 2 achieves optimal balance when P(x E G,Iæ E C+)
Lemma 3.1. The optimal balance can be achieved only when all the clusters have the same balance. Formally, Vi,j E 11., K]: balance(C:) = balance(())
Theorem 3.2. To achieve optimal balance value for multi-stat state protected variables, we must satisfy the condition: P( E G,,læ C2) = Pt which is precisely the optimal fairness value for equation
DEEP FAIR CLUSTERING ALGORITHM
We introduce our framework this section. Our approach can be viewed as learning fair clustering under discriminative clustering loss objective and a fairness objective with self-generated signals.
4.1 REVIEW OF BASE CLUSTERING MODEL
For base clustering model, we directly apply the previous work (Hu et al. 2017) and overview it here. We learn neural network fo as a discriminative function to predict the clustering assignments == (fx(x) E Nx based on input X E NDD and softmax function a. The mutual information 1(X; Y between X and is calculated as the difference between marginal entropy HY) and conditional entropy (Y)x):
1 N I(x;))= H - hi Eo(f(())) - N
Σ h(o(fo(z)))
(4)
where h is the entropy function. With weight decay term the clustering objective &g is as follows:
1 N N M(o(f((=))) - h( N Σ (ff(())))) + a 10912
N
lo =
(5)
where a denotes the hyper-parameter for network parameters (0r 04), Maximizing HY) will punish imbalanced cluster size and prevent trivial solutions where all the instances are clustered into one cluster while minimizing H (X) will map similar instances x to have similar labels y.
Further, segm-nugeetted training applied to encourage the representations to be locally invariant. Here we add local perturbation of instance æ such that x x + t and hope to maximize the perturbation t subject to the constraint that the clustering assignments for x and x' are the same. Virtual adversarial training (Miyato et al. 2018) is applied to generate adversarial direction for I. Denote the current model's s parameters / to help estimate the true clustering indicator vector for instance as a (z)())) the formulation to compute the adversarial perturbation tadv is as follows:
tade
arg max (L(a(fo(z)), (fo(x +)))
(6)
&:|ddI,5
4

---

Under review as a conference paper at ICLR 2022
With the generated fadu, we have the augmentation loss Eaug which minimizes the KL divergence between clustering assignment o ((f(xz)) and its augmented version's assignment (z)( )):
N
LAng Σ o
Finally, the base clustering model optimizes the clustering loss & and Laug simultaneously. Note that we favor this probabilistic discriminative clustering model (Hu et al.) 2017) since it has fewer assumptions about the natures of categories that made and fits fairness objective which requires fractional clustering assignments as inputs to indicate the degree of cluster assignment belief.
4.2 GENERATING FAIR ASSIGNMENTS UNDER GROUP-LEVEL FAIRNESS CONSTRAINTS
Let the fractional clustering assignments from the current learned model be Y (vi.... yN RNKK To use these to form fair clustering assignments, we solve fairer assignment matrix = .N E zN*X that satisfy the fair optimal condition: P(ar E G.lz E C³)) Pe- To address the fair assignment problem we formulate it as an integer linear programming where we aim to minimize the changes to the current assignment Y to obtain a fairer assignment Y as follows:
N ys x D
Objective: arg min Σ
Recall y/4 is a row vector which represents the probability distribution over the cluster assignments for instance and vi chooses exactly one cluster to assign instance to. Naturally the objective is maximized when Yi is assigned to most probable cluster but this may cause an unfair clustering.
We denote A: //N as the fraction of the protected group G; in the data set and our aim is for each cluster to have the same density. Let M NxT encode the sensitive attributes for the entire population such that M,. {0, l} indicates whether an instance æ; belongs to a protected group G.. To satisfy optimal fair condition P(r E G.|æ Ck) = Pt we have the following constraints:
N
N
Σ
Mady = Eeppe (je,L...KK,. (1...T)
Now we relax the problem by fixing the size of each new cluster to make the constraint matrix totally unimodular. We round the soft probabilistic assigmment Y hard assignments Y by assigning the cluster with largest probability. Then the size of cluster C, is |C₁l = - May The constraints for new clusters' size are:
N
Dig = CH
Vj e (1...K)
(10)
Lastly we add constraints for y to ensure each instance is assigned to one cluster:
K
Σ bし =1 Vie (1....
(11)
Note this ILP formulation also supports user-defined Ps which can be seen flexible fairness rule. Next we show the constraint matrix of our II. problem is totally unimodular so that we can efficiently solve it with I.P solver and still return integral solutions.
We know that if constraint matrix of an ILP is totally unimodular (TU) then we can solve the problem using an LP (linear program) solver and the solution will still be integral (Schrijver) 1998). Using an LP solver will largely reduce the running time and (Vaidyal 1989 has shown that the rumning time for LP is polynomial in the input size. In the above proposed constraints, there are NK unique regular variables (N instances and K categories). To construct the constraint matrix C' which encodes constraint | IC and [T] we will use N K regular variables. Matrix has T + 1 (the first T rows correspond to the fairness constraints in equation I and last corresponds to
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Main learning algorithm for deep fair discriminative clustering.
Input: Input {ar X
sensitive attributes M, cluster size K, network structure hyper-parameters o, 8. Output: Clustering network fe. predictions [y=) I: for each pre-trained epoch do
2: for sampled mini-batch { 1 do
Calculate to 1 -i=1 (o((foxx))))- M - (fo(())))) + a 11011
4: Generate 24 = z4 + solving from c
Calculate laug = Di= (o.(o(f(oz))), ( (fo(z)))
6:
Update network fo via minimizing to + AlAug-
7: end for
8:
end for
repeat
10:
Generate predictions fn = based on fo.
11:
Construct fair assignment problem via objective and constraints defined in oq 9 T0 and 11
12:
Solve fair assignments {úx Tk=1 via LP solver.
13:
for sampled mini-batch k== do
Calculate Eaair = >
(elog(a(fo(=:)))
15:
Calculate &c = 1 Eim ((o((f()))))) h( E offo(z))) + EtEn 10'1
16:
Generate 24 Th via solving t from eq
17:
Calculate Exug Σn (
18:
Calculate f == + Blpair + +llAug
19:
Update network fo via minimizing l. end for
20:
21:
until {ux 1 satisfy optimal fairness rules
constraints in equation T1 and N + K columns. Note the first K columns of the last row are set to and the last N columns of first T rows are set to O. In matrix C, each entry of C is from (-1,0, 0,10 1). Moreover, each column only has one non-zero element. This because: (1) for constraints set in 2 each instance only belongs to protected group, (2) for constraints set in equation there is only one row vector with K elements as I to ensure the valid assignment.
equation
Lemma 4.1. TU Identity (Schrijver 1998). Let C be matrix such that all its entries are from 1.). Then C totally unimodular, ie., each square submatrix of C has determinant O, 1, or -1 ifeer subset of rows of C can be split into two parts A and B so that the sum of the rows in A minus the sum of the rows in B produces a vector all of whose entries are from {0, 1111.
Theorem 4.2. The matrix C formed by the coefficients of the constraints used to encode our proposed
constraints from equation 9 10 (0ddd equation 77 is totally unimodular.
4.3 LEARNING TO BE FAIRER
To learn a fair clustering model we aim to exploit the fairness assignments Ý to reshape the features learned via clustering networks fe. We treat Y as "pseudo-labels" to optimize the following cross entropy loss Fair for fairer results:
Faar
Dtylogyij Σ (
(12)
Simply optimizing the fairness loss Faair will dramatically change the current clustering representa- tions to fit an approximated fair assignment Y which harms the clustering properties. Instead, we propose to learn fairer and clustering friendll representation simultaneously by combining the clustering loss lc, augmentation loss Aug and faireess loss F Note the fair assignments Y are updated after each training epoch as the "nearest" fair assignments for current clustering predictions.
To train our proposed framework, we start with the training on base clustering network (() via optimizing the clustering loss to and augmentation loss Laug to ensure the data are separated into different meaningful clusters; as clustering model converges we generate fair assignments after each training epoch based the objective in equation and optimize the overall loss function é by concatenating the fairness loss Faär to clustering objectives as lg + .l AAAg where (3, y positive weight hyper-parameters. Algorithm summarizes the proposed learning method.

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTS
We conduct experiments to evaluate our approach empirically and report the following key results:
Our proposed approach achieves better clustering performance and guaranteed fairness results compared against both traditional fair clustering and deep fair clustering baselines.
Our proposed approach is effective in novel fair clustering settings such as supporting flexible fairness constraints, clustering with multi-state PSVs, and predictive clustering.
We show how our learned embedding converges to latent space useful for fair clustering quickly and also provides insights on tuning hyper-paramee /3 in unsupervised way to achieve our fairness goal with a minimum loss on clustering performance.
5.1 EXPERIMENTAL SETUP
We first evaluate our work on two visual data sets with binary PSV that has been used in recent deep fair clustering work (Li et al. 2020): 1) MNIST-USPS consists of 67291 training images of hand-written digits. We use the image source (MNIST or USPS) as a binary PSV and cluster the data into 10 classes representing 10 digits. 2) Reverse-MNIST takes the 60000 training images from MNIST and creates an inverted duplicate to build this dataset. The binary PSV is then original or inverted and the total number of classes is 10. Moreover, we evaluate one challenging fair clustering task with multi-state PSV on the HAR dataset used in (Wang & Davidson 2019): 3) HAR contains 10299 instances in total with captured action features for 30 participants. There are 6 actions in total which serve as labels for clustering. The identity of each person is used as the PSV value.
Following Bera et al.] (2019) we choose three tabular datasets for complete comparison: 1) Census data with 5 attributes ("age", "fnlwgt", 'education-num" "'capitalgain.. "hours-per-week") and binary PSV gender, we set whether income exceeds 50K as the clustering label; 2) Bank data with attributes ("age", "balance", "durattonnoff-accouu will subscribe a term deposit as the label: 3) Credit data with 14 features and binary PSV marital, we set whether the cardholder will make payment the label.
and binary PSV marital, we set whether a client
To measure the clustering quality for deep fair clustering and other baselines, we use both clustering accuracy (ACC) (Xu et al.] 2003] Yang al. 2010) and normalized mutual information (NMI) metrics. To evaluate the fairness, we use the balance measure defined in equation 2 For all those three measures, higher values indicate better performance. For the deep clustering baselines,
DEC (Xie et al.) 2016) as a representative method for centroid- based clustering and IMSAT (Hu) 2017) for discriminative clustering approach. For fair clustering algorithms, we choose the scalable fair clustering algorithm (Backurs et al. 2019) and the fair algorithms for clustering (Bera) al.
al.
2019). For deep fair clustering baselines, we compare our work with the latest work (Li et al., 2020) and the crometric-based fair clustering (Wang & Davidson 2019). For our own approach, we use two convolutional layers followed by batch normalization and pooling for visual data and fully connected layers for tabular data. For a fair comparison with non-deep baselines, we use pre-trained auto-encoder's 's features like (Li et al.] 2020). For the I.P solver we use the Gurobi optimizer. More details about datasets and experimental setup are given in Appendix.
5.2 EVALUATION
Fair clustering results on high dimensional data: shown in the Table traditional fair clustering algorithms achieve good fairness results especially ScPC which returns guaranteed fair clusters. However the clustering performance is not good as deep clustering methods due to the lack of representation learning. Both DEC and IMSAT achieve reasonable clustering results but poor balance, this shows the unfairness of existing deep clustering models which motivates our adding fairesss rules. Comparing our results with the recent deep fair clustering works (Wang & Davidson 2019 Li et al. 2020) we can see that our approach consistently outperforms these two in terms of both clustering performance and fairness. Note we report both the deep model's results and the II.P's output in the last iteration. We observe that our deep clustering model's predictions almost converge to the final assignments solved from our ILP module. Observing the ground truth results in Table
In our experimental work use the fair clustering data sets used by earlier work for comparison.
7

---

Under review as a conference paper at ICLR 2022
Table I: Comparison of clustering and fairness performance on MNIST-USPS, Reverse-MNIST and HAR. HAR consists of multi-state PSV that baselines with dashes are not applicable. Bold results are the best results among all the baselines except the guaranteed fairness results which are marked with
blue. Note we report our average performance results after 10 trials and the term optimal refers the clustering giving the ground truth labels and the corresponding balance.
MNIST-USPS
Geverss--NNIS
HAR
Methods
ACC
NMI
Balance
ACC
NMI
Balance
ACC
NMI
Balance
Ground Truth (Optimal)
1.000
1.000
0.120
1,000
1.000
1.000
1.000
1.000
0.458
DEC Xie ct al. [016
0.586
0.686
0,000
0.401
0.480
0.000
0.571
0.662
0.000
IMSAT Hu et al. 2017
0.804
0.787
0.000
0.525
0.630
0.000
0.812
0.803
0.000
ScFC Backurs et al 2019
0.176
0.053
0.120
0.268
0.105
1.000
FAlg Bera of al. 2019)
0.621
0.496
0.093
0.295
0.206
0.667
0.642
0.618
0,420
Wang & Davidsón (2019)
0.725
0.716
0.039
0,425
0,506
0.430
0.607
0.661
0.166
DFCV Li ct al. 2020
0.825
0.789
0.067
0.577
0.679
0.763
Fair-DEC (Deep Model)
0.783
0.752
0.118
0.539
0.614
0.937
0.680
0.725
0.458
FaCr-DEC (ILP)
0.774
0.746
0.120
0.509
0.590
1.000
0.668
0.705
0.653
Ours Result (Deep Model)
0.939
0.876
0.119
0,589
0.690
0.946
0.862
0.845
0.468
Ours Result (ILP)
0.936
0.867
0.120
0.583
0.680
1.000
0.842
0.827
0,653
(a) Predictive Clustering Results
(b) Predictive Clustering Fairness
(c) Tabular Datasets Results
Figure 2: Experimental results on novel predictive clustering settings and classic tabular datasets.
we can see the fairness rules can be seen as positive guidance improve the clustering performance, our approach is shown to be able to learn from this guidance and improve faireess as well as accuracy.
Predictive clustering results: here we evaluate our method's ability to make predictions on test data without PSV information which is new setting in the fair clustering literature. That is we have already clustered a data set with PSV values and are now making predictions using the model learnt. This is particularly important for practitioners who are, for instance, deploying models on the web (where individuals are reluctant to share PSV information) and we see our results Figure Our approach performs consistently in both train and test sets. One exception is that the test balance in HAR is much lower than the training balance, we hypothesize this is due to different distributions between training and test set, the optimal test balance is while the optimal training balance is 0.653.
Classic tabular datasets: we evaluate our approach on tabular data sets and present the results in Figure (c). We find that model achieves similar clustering results k-Means tabular data with human-defined semantic features. Mcanwhile, we notice that k-Means algorithm achieves good fairness results when the number of clusters is correctly as the ground truth number of classes. Finally, our model can achieve optimal balance with a slight loss in terms of clustering accuracy.
5.3 FURTHER ANALYSIS ON OUR MODEL
Here we explore our model's 's flexibility in satisfying fairness requirements and better understand its performance by feature space visualization, parameter sensitivity and empirical convergence study.
Feature space visualizing: to understand how our model learns fair representation, we have applied t-SNE (Van der Maaten & Hinton 2008) to visualize the feature space of MNIST-USPS during different training epochs in Figure 3 The initial model is trained with clustering objectives which yield unfair results, once we introduce faimess signals the red instances start move to different clusters. Meanwhile, we observe our learned representations maintain good clustering properties.
Tuning the weight of fairness objective: we experiment the choices of hyper-paramedt 3 which controls the weight of the fairness objective and report the clustering results in Figure 4 It is straightforward to see from (a) and (c) that 33 increases, the training balance increases. Meanwhile,
8

---

Under review as a conference paper at ICLR 2022
(a) epoch 0
(b) epoch 15
(c) epoch 30
(d) epoch 45
(e) epoch 60
Figure 3: t-SNE visualization of learned embedding, color red and blue indicate different PSV values.
(a) MNIST-USPS (Balance)
MNIST-USPS (ACC)
(c) HAR (Balance)
(d) HAR (ACC)
Figure 4: Sensitivity analysis of thper-paramette 3 which serves as the weights for faimness objective.
based (b) and (d) can find the ACC goes up and down 3 increases. Our previous result shows that the fairness constraints can serve as positive guidance for both MNIST-USPS and HAR. That is why the clustering accuracy goes up when we increase 3 from O. But we also observe that with a very large 3 the clustering accuracy will drop. We hypothesize this is because the fairness objective dominates the overall objective so that the impact of clustering objective hindered. As balance can be tracked during the training process for free, our insight for selecting to pick the smallest 33 that achieves satisfying balance results.
Results on flexible fairness constraints with MNIST-USPS: here we explore how relaxing the optimal fair condition defined as Pt in equation / produces flexible constraints. We now require the fairness requirement to be in the interval [Pt [1 <), Ps * (1 <)]- In Figure 5 (a), we can see a larger relaxation degree e leads to lower balance which as expected; since the fairness signals can serve as positive guidance for clustering MNIST-USPS, we observe the ACC and NMI are decreasing with larger c. Allowing flexible constraints are important as the fairness rules vary across regions.
Empirical convergence analysis: to investigate the smoothness of learning with clustering and fairness objectives together, we present the learning curves overall training loss and the balance results in Figure 5 (b) and (c). We can from the plots that our model's overall training loss drops quickly and converges after 50 epochs. Meanwhile, our model's balance result also converges after 50 epochs.
42
4.5
420
12/1
20%
1244
080
Degres
(a) Flexible Fairness Constraints
(b) Convergence Study (Train Loss) (c) Convergence Study (Balance)
Figure 5: Flexible fairness constraints experiments on MNIST-USPS in (a); visualizing the learning curves of training loss and fairness measured by the balance on HAR and MNIST-USPS in (b, c).
CONCLUSION
In this paper, we explore the novel direction of adding fairness into deep clustering, This is a chal- lenging problem given the end-to-end deep learning setting which does not facilitate pre-processing into fairlets and the need for scalability to large data sets. We formulate group level measure of fairness as an integer linear programming problem and show the problem can be solved efficiently due to total unimodularity (Theorem 4.2). We then add this solver into deep learner and show that our formulation works with multi-state sensitive attributes as well as flexible fairness constraints that occur in real-life applications. Extensive experiments demonstrate the strong performance of our approach and an in-depth analysis including feature space visualization, dyper-paramett tuning, model convergence analysis, and investigating flexible fair constraints shows its versatility.
9

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work is proposed to ensure the fairness of deep clustering algorithms. One advantage of our work that users can define their own group-level fairness criterion, as shown in the flexible fairness rules experiments. Another advantage is that the learned model can be used for out-of-sample predictions of new instances which may not have sensitive attributes (PSVs) available. However, our flexible design will also allow malicious users to pass the "unfair constraints" into our ILP fairness objective, which leads to artificially unfair results. Therefore, we recommend that the users output both the fairness requirements within the ILP objective and the deep clustering model's s results to ensure the correct use of our algorithm.
REPRODUCIBILITY STATEMENT
After the reviewing process, our work will be open-sourced, allowing researchers to conduct deep clustering tasks on both tabular and image datasets with group-level fairness rules. Moreover, we have included our source code in the supplementary package and also added two extra sections about baselines implementations and our model's selected seperpparameters the Appendix.
REFERENCES
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 267-275, 2019.
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In International Conference on Machine Learning, pp. 405-413, 2019.
Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Advances in Neural Information Processing Systems, pp. 4955-4966, 2019.
Reuben Binns. On the apparent conflict between individual and group fairness. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 514-524, 2020.
Brian Brubach, Darshan Chakrabarti, John Dickerson, Samir Khuller, Aravind Srinivasan, and Leonidas Tsepenekas. A pairwise fair and cranuuunit--preeevviin approach to k-center clustering. In International Conference on Machine Learning, pp. 1178-1189. PMLR, 2020.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsuper- vised learning of visual features. In Proceedings of the European Conference Computer Vision (ECCV), pp. 132-149, 2018
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering, In International Conference on Machine Learning, pp. 1032-1041. PMIR, 2019.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances Neural Information Processing Systems, pp. 5029-5037, 2017.
Ian Davidson and SS Ravi, Making existing clusterings fairer: Algorithms, complexity results and insights. In Thirty-Fourth AAAI Conference on Artificial Intelligence. 2020.
Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin. Improved deep embedded clustering with local structure preservation. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 1753-1759, 2017.
Weihua Hu, Takeru Miyato, Seiya Tokui, Eiichi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. In International Conference on Machine Learning, pp. 1558-1567, 2017.
Anil K Jain. M Narasimha Murty, and Patrick Flynn. Data clustering; a review. ACM computing surveys (CSUR), 31(3):264-323, 1999.
10

---

Under review as a conference paper at ICLR 2022
Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In International Conference on Machine Learning, pp.
2019a.
Matthaus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. Guarantees for spectral clustering with fairness constraints. In International Conference on Machine Learning, pp. 3458-3467, 2019b.
Peizhao Li, Han Zhao, and Hongfu Liu. Deep fair clustering for visual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9070-9079, 2020.
Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering. In International Conference Machine Learning, pp. 6586-6596. PMLR, 2020.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: regularization method for supervised and supervisd learning. IEEE transactions on pattern analysis and machine intelligence, 11(8):1979-199 2018.
Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. In 45th International Colloquium Automata, Languages, and Programming (ICALP 2018). Schloss Dagstubl-Laibbni--ZZntuu fuer Informatik, 2018.
Melanie Schmidt, Chris Schwiegelshonn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means. In International Workshop on Approximation and Online Algorithms, pp. 232-251. Springer, 2019.
Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
Sohil Atul Shah and Vladlen Koltun. Deep continuous clustering. arXiv preprint arXiv: 1803.01449, 2018.
Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectralnet: Spec- tral clustering using deep neural networks. International Conference on Learning Representations, 2018.
Elad Tzoreff, Olga Kogan, and Yoni Choukroun. Deep discriminative latent space for clustering. arXiv preprint arXiv: 1805. 2018.
Pravin M Vaidya. Speeding-up linear programming using fast matrix multiplication. In 30th annual symposium on foundations of computer science, pp. 332-337. IEEE, 1989.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Bokun Wang and Ian Davidson. Towards fair deep clustering with multi-state protected variables. arXiv preprint 1901 2019.
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang, Attributed graph clustering: A deep attentional embedding approach. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 3670-3676, 2019.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference on machine learning, pp. 478-487, 2016.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. semantic loss function for deep learning with symbolic knowledge. In International Conference Machine Learning, pp- 5502-5511, 2018
Wei Xu, Xin Liu, and Yihong Gong. Document clustering based on non nog-nvgative matrix factoriza- tion. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion reirieval, pp. 267-273, 2003.
Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. Towards k-means-frient friendly spaces: Simultancous deep learning and clustering. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 3861-38777 JMLR. org, 2017.
11

---

Under review as a conference paper at ICLR 2022
Yi Yang, Dong Xu, Feiping Nie, Shuicheng Yan, and Yueting Zhuang. Image clustering using local discriminant models and global integration. IEEE Transactions on Image Processing, 19(10): 2761-2773, 2010.
Hongjing Zhang, Sugato Basu, and Ian Davidson. Deep constrained clustering-algoritmms and advances. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 57-72, 2019.
Imtiaz Masud Ziko, Jing Yuan, Eric Granger, and Ismail Ben Ayed. Variational fair clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11202-1 1209,, 2021.
12

---

Under review as a conference paper at ICLR 2022
A THEOREMS AND PROOFS
Lemma A.1. (Lemma 3.1). The optimal balance can be achieved only when all the clusters have the same balance. Formally, V j E {1, K.). balance(C.)) = balance(C,).
Proof. The proof is by contradiction, we assume the optimal balance can be achieved when not all clusters have the same balance. Let cluster C, have the largest balance as 6maz and cluster C has the smallest balance as bmin- Denote the number of 'T different groups' instances in C₁ as {C11, Cr2..... ) similarly the composition for Cj as {C21, Cj2.... f2...... C5z }. Assume the balance
for C, is achieved by bmaz two possible cases:
Now we discuss Cia the balance for C3 is achieved by bmin Cja" Cia
Cia.
Case 1: If a " and B = 0. Based on our definition we have Cia
C.. Letr = ( Cas o
C.e move instances which belong to group from C₁ Cj This can be done by setting CLo-
achieve the higher balance
Cj
C.a
r.
Case 2: If a # Y or 3 # 0. Based on the balance definition we have C... definition we have Caa C2.
2
C... C2a
Based on our
C2
Ca., Thus we have
Cz.
C.a.
Ciz,
Similar as in case 1 we can move
OSe"
Cse
C.a
Cje*
instances which belong to group y from C, to C, to achieve higher balance r' 1/4
Cin Cie
+ Cir).
Cje
In both cases, we can swap some instances between clusters to increase the final balance. This contradicts assumption and completes our proof.
Theorem A.2. (Theorem 3.2). To achieve optimal balance value for multi-state state protected variables, we must satisfy the condition: P(r E Gilæ E Ck) Ps which is precisely the optimal fairness value for equation
Proof. Given the condition P(r E Ge|z E C*) = Ps.. let Gmán be the smallest protected group and Gmaz be the largest protected group, the largest balance we can achieve is /Gminl// mazzl I. The proof by contradiction assumes these exists a solution where all the clusters have the same balance (based on lemma and have balance a > |Gmial/IG
For each cluster sort each protected group based on their size in an increasing order. We use C. Cß Ci to denote the size of the Ci. for any cluster Now we sum up the smallest sorted groups cluster Obviously we have a CTr
group among all the K clusters as S: 5 = >K C.-- Similarly we can calculate the sum of the Consider the allocation of the smallest group Gmin we have the following inequality: |Gmin| 2 E C₁ = S. Similarly we have |Gmazl I Ek Cir-Cr- |mmin which means |Gmin l/ G 2 a. This contradicts with our initial assumption that there exists a which is larger than [mmin/ Saaaml//Garr //maall Thus complete the proof.
largest group among all the clusters Ei= Cj Σ Că
By combining previous two inequalities have a/Gmazl S S <
Proof Total Unimodularity of Constraint Matrix We know that if constraint matrix of an ILP totally unimodular (TU) then we can solve the problem using an LP (linear program) solver and the solution will still be integral [Schrijver (9988. Using an LP solver will largely reduce the running time and Vaidya (1989) has shown that the running time for IP is polynomial in the input size.
In the above proposed constraints, there are NK unique regular variables (N instances and K categories). To construct the constraint matrix C' which encodes constraint 7, constraint 8 and constraint 9, we will use N K regular variables. Matrix has + 1 rows (the first rows correspond to the faimess constraints in equation 7 and last row corresponds to constraints in equation 9) and N + K columns. Note the first K columns of the last row are set to 0 and the last n columns of first T rows set to 0. In matrix C, each entry of C' is from {-1, 0, 1}. Moreover, each column only has one non-zero element. This is because: (1) for constraints set in equation 7, each instance only belongs one protected group, (2) for constraints set in equation 9, there is only one row vector with K elements as 1 to ensure the valid assignment.
2 All the equations referenced in appendix are in the main paper.
13

---

Under review as a conference paper at ICLR 2022
Lemma A.3. (Lemma 4.1). TU Identity (Schrijver 1998). Let C be matrix such that all its entries
are from {0, 10.). Then C is totally unimodular, ie.. each square submatrix of C has determinant 0, 1, -1 if every subset of rows of C can be split into two parts A and B that the rows A minus the sum of the rows in B produces a vector all of whose entries are from {0, 1, -1).
of the
Theorem A.. (Theorem 4.2). The matrix C formed by the coefficients of the constraints used to encode proposed constraints from equation 7, 8 and equation 9 is totally unimodular.
Proof. We consider any subset F of rows in C. We will show that F can be partitioned into two sets and to satisfy the condition in lemma A..3 Our partitioning scheme is as follows: the first row of F is put into A and the remaining of the rows within A and respectively. It is clear that elements in S A and SB are from (1,0, -11 because each column only has one non-zero element. Now we show all the elements in SA SB from {1, 0, -1 -1 Firstly there will be only one non-zero element in SA, and we denote the column which has a non-zero element r. If column belongs the fairness constraints (from column 1 to column N in C), then the column within SB will be since one instance only belongs to one protected group. the column r belongs the valid assignment constraints (from column N to N + K in C') then column within S B will be 0 since those elements are filled with O. Thus column r of SA SB is still from {1, 0, -1}. The non-zero elements other columns will change their
are put into B. Let vectors SA and SB denote the sums
sign but still from {1, 0, 1}. This completes the proof.
B BASELINES IMPLEMENTATIONS
For the k-means baseline, choose For scalable fair clustering work (Backurs et al. 2019), we use the code from their author's github repository (ht tps: /gi //gittutuuuu..g thub. com/ www.wr/g/weeao cesirrrcuusterree
the k-means++ implementation from scikit-leamn library.
For deep embedding clustering Xie et al.] 2016) we use the implementations from the public github repositories (https //github. com/ wil.vvluiiyy/ www.ukiynnv/ptttoo dec) and for IMSAT (Hu et al., (017)) we use the code from their author's github repository (https: gi witthub.... com we hua 9166 6 imsat), ). For Wang and Davidson's 's deep fair clustering work (Wang Davidson 2019), we have contacted the author get their code re-run the experiments under our setting. For the DFCV (Li et al.) 2020) approach, we directly excerpt the experimental results from their original paper.
C HYPER-PARAMETEE AND ARCHITECTURES OF OUR APPROACH
For the digit datasets like reverse-MNIST and MNIST-USPS, we use a 2-block convolutional ar- chitecture with first block consisting of convolutional layer with 8 (5 5) filters and second 4 (5 x 5) filters. Each block is followed with BatchNorm, ReLU activation and max pooling layers. The second block is finally connected units. For the HAR data we use a stacked fully connected neural network with intermediate layers as d 1200 1200 number of clusters. Moreover, we have listed the hyper-parameters that we used for these three data sets in Table In unsupervised learning. it is not straightforward determine cross-validation. Hence, we fixed the hyper-pan parameters (weight decay a and augmentation term 7) across all the datasets; we tuned the hyper-paramen / based on the training set's balance value as mentioned in the main paper to achieve satisfying fair results.
block consisting
fully connected layer with 10
note 561 is the total number of features in HAR and k is the
sapee-pprraeterss by
Table 2: Deep-clustering data: hyperparameter summary
HAR
reverse-MNIST
MNIST-USPS
Learning rate
0.0002
0.0005
0.0005
Batch size
256
256
256
Train epochs
60
80
50
Weight decay
0.0001
0.0001
0.0001
Parameter 3
4.00
6.00
4.00
Parameter y
1.00
1.00
1.00
14

---

Under review as a conference paper at ICLR 2022
Table Traditional tabular data: hyperparameler summary
Census
Credit
Bank
Learning rate
0.0002
0.0002
0.0005
Batch size
256
256
256
Training epochs
30
50
30
Weight decay a
0.0001
0.0001
0.0001
Parameter /
4.00
5.00
4.00
Parameter 1.00
1.00
1.00
For the traditional fair clustering data sets, intermediate layers as d 50 50 - k; note the total number of features for Census, Credit and Bank are 5, 14 and k: 2 is the number of clusters. Moreover,
stacked fully connected neural network with
have listed the hyperparameters that we used for these three data sets 3 We set the same values for hyper-parameters a and y. Since these tabular data sets only have limited features we observe that fewer training epochs are needed to train our model.
D EXTRA EXPERIMENTAL RESULTS
In this section we first report the run time results in Table 4 Our codes will be available on GitHub for public use after the reviewing process.
RUNTIME ANALYSIS
We implement algorithm in Python 3.6 and run experiments a PC with 3.3 GHz Intel Core 19 Processor and GeForce RTX 2080 TI graphic card. We use Gurobi for solving all the ILP problems. We report the runtime results in Table|4 We can observe that solving the ILP via LP is not very time-consuming, the introduction of our fairness objective does add more computations compared with the non-fair version but the overall time cost is still acceptable.
Table 4: We report the average running time (second) over 10 trials.
ILP solver
Train with fair-
Train w/o fair- objective
objective
HAR
87.20
130.81
12.49
reverse- twerse-MNIST MNIST
389.71
813.26
218.90
MNIST-USPS
201.56
434.18
127.76
Census
32.65
96.13
22.54
Credit
53.82
151.13
34.28
Bank
5.12
12.49
3.57
CLUSTERING RESULTS VISUALIZATION
TigureGanne shows randomly selected instances of the MNIST-USPS that clustered via our proposed fair clustering approach and the deep clustering approach (IMSAT). We observe that in the IMSAT's results most of the instances from USPS are grouped to one cluster which lead balance. Instead, our approach successfully separated them into different clusters to achieve fairness goals.
httpp:/wwww.gurob.com
15

---

Under review as a conference paper at ICLR 2022
2
2
33330
3
33
3
2-
2
3
3
2
9
9
2
0
2
3
3
7 7
7
8
3
7
9
7
9
7
6
5
5
5
6
6
7
7
5
V
8
9
9
5 5 5
8 8
8
$
9 9
9
9
S 5 5
39666666
7
9 56556955
66
9
8
q
7
5
66600
7
2
7
8
9
9
Q
8 8
6666666
7
7
7
8
7 4
5
Figure 6: Sampled instances of MNIST-USPS discovered using fair clustering approach.
2
2 2
5
2
2
33555
5
3
3
2
2
2
3
5
1603
2
2 T
5
0
208
D 14000
7
5
9
9
8 D 3033
7
4
8
9
9
5
D
70
&
7
9
102 102317 1
6
7
4 24
1 1
6
7 7
7
7
8
8
4 9
9
0 2
3
7 2
7
7
7 7
5
9
9
9
G
9
Figure 7: Sampled instances of MNIST-USPS discovered using IMSAT.
16


Reviews:
[{"review_id": "_oushF68EO", "reviewer": "Reviewer_5Bwe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is generally clear and well written, and the empirical results are impressive.\n\nThe paper could do a better job distinguishing itself from existing work in deep fair clustering, which also supports multiple-state PSVs (this point seems muddied at times, e.g., the second to last sentence of section two and bullet 2 in section 5 both seem to imply otherwise).  It seems the main advantage of the proposed method over existing methods (beyond better observed performance in experiments, which is motivating in itself) is that the method guarantees a fair clustering.  Unfortunately, it is not very clear how this method is able to guarantee a fair clustering, since fairness is a weighted term in the loss function, and the authors don’t seem to prove (or argue) that the method will converge to a fair clustering (I can certainly believe that it would, but perhaps it would be useful to help the reader see that this is the case), and the authors also do not address what happens when a fair clustering is not possible.  I suppose the fairness guarantee involves using the output from the ILP in the last iteration as the output, but this doesn’t seem clearly specified.\n\nOne limitation of this work seems to be that each person can only belong to one protected class, which doesn’t seem to be the case for (Bera et al., 19).\n\nThe importance of Theorem 3.2 (one of the stated contributions of the paper) is not very clear and could be emphasized.\n\nI found the description of the constraint matrix a little confusing and would imagine a little more clarification could be helpful.  For example, why are 2NK variables used (rather than NK), and doesn’t the number of variables typically equal the number of columns in the constraint matrix?\n\nThe empirical results are impressive, though counter intuitive at times and could benefit from a little additional explanation (perhaps as the result of a bit more exploration).  For example, it would seem intuitive that taking a loss function and adding a term for fairness would cause the result to be worse w.r.t. the original loss function.  While neither accuracy nor NMI are the original loss function, they (especially NMI) seem more closely related than to the fairness term.  The authors note this and claim that fairness provides “positive guidance” for clustering performance, but this does not seem to be an explanation as much as a hypothesis (or, less generously, a re-statement of the observation).  A second example that could probably benefit from slightly more explanation is the observed results when setting the beta hyper parameter.  Why does beta=4 seem to be the sweet spot for all datasets and metrics?  Any intuition for this (if any could be gained) would be interesting to report.  A third example, “we observe the ACC and NMI are decreasing with larger ε”, seems very counter intuitive  (similar to the first example, but perhaps more so) and some explanation beyond “positive guidance” would be encouraging.\n\nMinor comments:\n\n“Fairness takes two primary forms: i) group-level fairness and ii) individual-level fairness.” Please consider citing, I have seen other characterizations of fairness.\n\n“Different geographic regions place this tolerance at different levels.” Consider adding a citation.\n\n“most of these algorithms evaluate their performance on low-dimensional tabular data and mainly study the problems with binary PSV.”  Most of and mainly seem like unfortunate hedges here.  Perhaps its worth pointing out which work evaluate their performance on low-dimensional tabular data and study the problems with binary PSV, and which do not.\n\n“Finally, the base clustering model optimizes the clustering loss lC and lAug simultaneously” Doesn’t (Hu et al., 2017) optimize lC subject to constraints on lAug? (And isn’t this slightly different?)\n \n“Let the rounded version of current assignment Y as Y’ ” I’m not sure I understand what is meant here (perhaps due to a typo resulting in a grammatical error).\n\nThe choice of datasets makes sense (in that they were used in prior work).  Nevertheless, using MNIST for fairness seems somewhat contrived and the results would seem more motivating on more reasonable data.\n\nWhat is ““fnlwgt”?  It might be worth spelling out what the attributes mean/their possible values.\n\nIt seems like an overstatement to claim that by evaluating both accuracy and NMI the study is comprehensive (which means  including all or nearly all elements or aspects of something).\n\n“Note we report both the deep model’s results and the final ILP’s results.”  What is meant here does not seem to be specified anywhere and was confusing to me (and I think resulted in my confusion elsewhere).  I think a sentence or two explanation could go a long way.\n\n“ground-truth and the guaranteed fairness results which are marked with blue”. I guess I know what is meant here, but there is a whole row labeled ground truth and only some of the cells in that row are blue. \n\n“This is particularly important for practitioners who are, for instance, deploying models on the web (where individuals are reluctant to share PSV information)”. If the train data came from a source where PSV information is available and the test data came from a source where it is not (e.g., the web, as described), is it reasonable to assume other changes in the population/resultant distribution are present as well?\n \n“We hypothesize this is because the fairness objective dominates the overall objective so that the impact of clustering objective is hindered” What is meant here?  That training solely on the fairness objective does not lead to good clustering results?  Something else?\n", "summary_of_the_paper": "This paper proposes a method for fair clustering (where a clustering is considered fair when each protected group is present in every cluster in the same proportion as in the population) using deep neural networks.  The method works by training a neural network for clustering using the deep clustering with virtual adversarial training approach proposed by (Hu et al., 2017) and then refining (retraining) the network by adding a fairness term to the loss function (where the fairness term is the cross entropy loss between the current networks prediction and the fair assignments obtained using an LP solver on a constraint matrix that enforces the group fairness/balance constraints).  It also presents some experiments that demonstrate the method is more effective at finding high quality fair clusterings than existing deep clustering, fair clustering, and deep fair clustering methods. ", "summary_of_the_review": "The paper is generally clear and well written, and the empirical results are impressive.  Still, there are several opportunities to clarify the details of the approach as well as its advantages, to note its limitations, and to provide intuition for the empirical results (that may be surprising to some readers).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "X133EsWHBz", "reviewer": "Reviewer_tDB1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "## Pros\n1) The proposed fair clustering algorithm shows the equivalence between the fairness measure defined in eqn 3 and the balance measure. \n2) The experimental results seem satisfactory, especially the balance measure. \n3) This paper is well-organized and easy to follow. \n \n## Cons\n1)  As Section 4.1 is simply the introduction of the backbone network, maybe it should be an individual section. In my opinion, the major contribution is to use the fair approximation as pseudo-labels. It will be more convincing to conduct experiments on various backbone networks. \n2) In P5, the authors claim that \"Let the rounded version of current assignment $Y$ as $Y'$ then the size of cluster $C_j$ ... \". But what is the *rounded version* (formally)? Does it mean the hard version of $Y$ as $Y$ is a continuous variable?\n3) In Table 1, the balance scores of DEC and IMSAT are 0. It means that some samples from USUS are not assigned to a certain cluster (on MNIST-USPS). It is abnormal since ACC and NMI are still high. Although these two models are non-fair clustering methods, it might be inappropriate to mark the balance score as 0 simply. \n4) There are some typos and inappropriate formulation:\n- P5: \"that *satisfy* our optimal fairness condition\"\n- P5, eqn 8: $*$ -> $\\times$ or $\\cdot$. What's more, the authors should emphasize that $y_i$ is a row vector. \n- P5, eqn 11: the superscript is missing. \n ", "summary_of_the_paper": "This paper proposes a fair clustering algorithm that uses DL models to map the data into deep representations. The authors also show the equivalence between the practical fairness measure and the balance measure. The algorithms can be concluded as two steps: \n1) find fair assignments $\\hat y$ based on $y$;\n2) tune the latent representations and $y$ according to the pseudo-label $\\hat y$. ", "summary_of_the_review": "Please see above. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WKp-U6lwST5", "reviewer": "Reviewer_py3W", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The own contributions of this paper are unclear. The introduced fairness notion is simply a generalization of the previous proposed measure of fairness allowing for protected status variable (PSV) with multi-state instead of binary-state. The integer linear programming formulation is then plug into a probabilistic discriminative clustering model proposed in 2017 for deep fair discriminative clustering. The own contributions therefore remain unknown. It is a stretch to argue that the authors should not use \"we\" as the subjects when describing the base clustering model and others' methods which mystify their own contributions. \n\nRelevantly, multi-state PSV is stated as their learning target while 2/3 datasets are binary PSV. In addition, the improvements over baselines are marginal or no improvement and flexible fairness constraint is not completely supported by the experimental results notably the ACC part. The authors should consider tone down relevant claims.   \n\nThis study is not well motivated either. The drawbacks of existing studies and how these limitations are addressed by this work should have discussed to justify the necessary of this work. The rationals of selecting the base clustering model and evaluation metrics also lack of more detailed discussion. ", "summary_of_the_paper": "The authors propose to combine deep learning and discrete optimization to learn fair representation for clustering. To this end, a generalized notion based on the previous defined balance measure is introduced, based on which an integer linear programming problem is defined and is further added into an existing deep learner for fair deep clustering. ", "summary_of_the_review": "Lack of own contribution, proper motivation and sufficient justification of the proposed method. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2eXdECsOq5k", "reviewer": "Reviewer_Um5H", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths:\n1. This paper explores the fairness problem in deep clustering, and presents a general notion of fairness for both binary and multi-state protected status variables, which is proved to be equivalent to optimize the general balance measure for disparate impact.\n\nWeaknesses: \n1. The paper said that it can be fairer in clustering without the sensitive attributes. However, what is sensitive attributes in a data set? The definition is not clear. How do we judge whether attribute is sensitive? The authors think the clustering result is not fair, if the sensitive attributes are used in clustering process. Why do we delete these sensitive attributes and cluster the data set without sensitive attributes? Why doe we need the fairness constraints for clustering task? The authors should provide the clear explanation.\n2. In the proposed algorithm, the authors first get pseudo labels y on a data set with sensitive attributes by a deep clustering model. Furthermore, they use fairness constraints to refine the pseudo labels to get \\hat{y}. Finally, they use \\hat{y} as supervised information to train a deep model. That make me confuse: why do the authors directly add the fair constraints to the objective function or problem of the deep model? Why are the fairness constraints only used as a preprocess of pseudo labels?\n3. In the experiments, these tested datasets do not include sensitive attributes. The authors should provide an application scenario to prove the performance of the proposed algorithm.\n", "summary_of_the_paper": "This paper proposes a novel deep fair clustering framework which addresses the problem about producing guaranteed fair predictions on clustered data with PSVs and making out-of-sample fair predictions for data without PSV. ", "summary_of_the_review": "The present paper presents a framework to ensure the fairness of deep clustering algorithms. The paper is well organized and the motivation of this paper is clear. However, some definitions and roles about sensitive attributes are not clear. Besides, these tested datasets do not include sensitive attributes. The experiments are not enough. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper received a majority voting of rejection. In the internal discussion, no reviewer would like to change the score according to the author response. I have read all the materials of this paper including manuscript, appendix, comments and response. Based on collected information from all reviewers and my personal judgement, I can make the recommendation on this paper, *rejection*. Here are the comments that I summarized, which include my opinion and evidence.

**Motivation**

The motivation of this paper is not strong. In this paper, the authors claimed that the fairness level of deep clustering methods is relatively poorly compared with the traditional fair clustering methods. The traditional fair clustering methods employ the hard constraints to achieve fairness by scarifying the cluster utility. Instead, deep fair clustering methods seek the trade-off balance between fairness level and cluster utility; therefore, the deep fair clustering can be regarded to use the soft constraints. There is no necessary to compare two different fairness constraints. Even the proposed method is a trade-off balance between fairness level and cluster utility.

**Self-augmented Training**

The relationship between self-augmented learning and fairness learning is unclear. I guess that the authors added this modular simply to enhance the cluster utility. However, such a loss or an operator can be also applied to other (fair) clustering algorithms. The experimental comparisons in Section 5 is unfair. No ablation study on this is provided.

**Novelty**

One reviewer pointed out there existed some work that plugs integer linear programming into a probabilistic discriminative clustering model proposed in 2017. 

**Experiments**

(1) ScFC and DFCV release their codes; no results of these two methods were reported on HAR. (2) No standard deviation. (3) The Initial ILP Results (Ours) and Ours Result in Table 1 on HAR dataset is 0.653 and 0.468, both higher than the Ground Truth (Optimal) 0.458.

**Presentation**

 A few statements are not well-supported, or require small changes to be made correct.

No objection from reviewers was raised to again this recommendation.
Decision: Reject