Year: 2021

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.

heading: 1 INTRODUCTION
text: Clustering is essential as it is the basis of many AI 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 AI tools augment and even replace humans in decision-making, the need to ensure clustering is fair becomes paramount. Here fairness is measured using protected status variables (PSVs) such as gender, race, or education level. Fairness takes two primary forms (Binns, 2020): i) group-level fairness and ii) individual-level fairness. In this paper, we study the former 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 (Rö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 impact doctrine encoded as a constraint, that instances from different protected groups must have approximately (within a tolerance) equal representation in a cluster compared to the population. Different geographic regions place this tolerance at different levels (Chierichetti et 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., 2019b). However, all these works evaluate their performance on low-dimensional 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 a 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 as computing fairlets (Chierichetti et al., 2017) to ensure fairness will not
work as 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 as these constraints are at the instance level, whereas we require to apply fairness rules at a cluster level.
The work on 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 a fair representation with multi-state PSV. The most recent work (Li et al., 2020) proposes a 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 1), 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 a 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 our fairness objective as an integer linear programming (ILP) problem that guarantees group-level fairness. This ILP is efficient to solve as its constraint matrix is totally unimodular. Further, we propose a refinement learning algorithm to combine the solved fair assignments and the clustering objective. Experimental results on real-world 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 PSVs. The major contributions of this paper are summarized as follows:
• We optimize a general notion of fairness 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 an end-to-end refinement learning algorithm that combines deep learning and discrete optimization to learn fair representation for clustering. (See Algorithm 1).
• 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 fairness rules. (See Section 5.2).
In the next section 2 we discuss the related work. Then we outline our measure of fairness and how it 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. A 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 6.

heading: 2 RELATED WORK
text: Fair clustering has received much attention recently (Schmidt et al., 2019; Kleindessner et al., 2019a; Ahmadian et al., 2019; Chen et al., 2019; Davidson & Ravi, 2020; Mahabadi & Vakilian, 2020; Brubach et al., 2020). Chierichetti et al. (2017) 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 a constant factor approximation with respect to cluster quality. Backurs et al. (2019) improves the fair decomposition algorithm to linear run-time. Later on, Bera et al. (2019) propose a 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 `p norms such as k-median, k-means, and k-center. Besides the centroid-based method, Kleindessner et al. (2019b) extends the fairness notion to graph spectral clustering problems. Ziko et al. (2021) propose a general, variational and bound-optimization framework of fair clustering.
Previous fair clustering approaches mainly focus on adding fairness 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 et 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 is to learn a fair and clustering-favored representation. We illustrate the basic intuitions behind traditional fair clustering methods and deep fair clustering approaches in Figure 1.
One of the earliest works (Wang & Davidson, 2019) to address the deep fair clustering problem learns a 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 fairness constraints as an adversarial loss and concatenates the fairness loss to a centroid-based deep clustering objective as a unified model. Unlike previous deep fair clustering works, we translate the fairness requirements into an ILP problem that generates guaranteed fair solutions given the PSVs. Meanwhile, our formulation allows for a 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 simultaneous clustering and fitting the self-generated fairness signals.

heading: 3 DEFINITIONS OF GROUP-LEVEL FAIRNESS
text: We begin this section by overviewing the seminal definition of group-level fairness in clustering (see equation 1) and then its extension to multi-state PSVs (see equation 2). We then go onto show a new measure that our deep clustering framework will optimize (see equation 3) and equation 2 have the same optimal condition as shown in Theorem 3.2.

heading: 3.1 NOTION OF FAIRNESS
text: Let X ∈ RN×D denote N data points with D dimension features. The prediction function φ assigns each instance to one unique cluster, φ : x→ {1, ...K}, which forms K disjoint clusters {C1, ...CK}. Given the protected status variable (denoted as PSV) A with T states, X can be partitioned into T demographic groups as {G1, G2, ...GT }. Definition 1. The seminal proposed measure of fairness for clustering with binary PSV (Chierichetti et al., 2017) encoded disparate impact as follows:
balance(Ck) = min( N1k N2k , N2k N1k ) ∈ [0, 1] (1)
Here N1k and N 2 k represent the populations of the first and second demographic groups in cluster Ck. Such a measure of fairness only works for binary PSV. To allow for multi-state PSVs, let Nmink = min(N 1 k . . . N T k ) denotes the smallest (in size) protected group in cluster k and Nmaxk = max(N 1 k . . . N T k ) denotes the largest group. We extend the balance measure for multistate PSV as:
balance(Ck) = Nmink Nmaxk ∈ [0, 1] (2)
Recent works (Rösner & Schmidt, 2018; Bera et al., 2019) also propose a new fairness measure to allow for fair clustering problems with multi-state PSVs.
Definition 2. Let ρi be the representation of group Gi in the dataset as ρi = |Gi|/N , and ρi(k) be the representation of group Gi in the cluster Ck: ρi(k) = |Ck ∩Gi|/|Ck|. Using these two values, the fairness value for cluster Ck is:
fairness(Ck) = min( ρi ρi(k) , ρi(k) ρi ) ∈ [0, 1] ∀i ∈ {1, . . . T} (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.

heading: 3.2 EQUIVALENCE OF OPTIMIZING FAIRNESS AND BALANCE MEASURES
text: Here we show that optimizing equation 3 is equivalent to optimizing our extended definition of balance in equation 2. We see that equation 3 achieves maximal fairness when P (x ∈ Gt|x ∈ Ck) = ρt. Our balance measure in equation 2 achieves optimal balance when P (x ∈ Gt|x ∈ Ck) = 1T for any protected group Gt in cluster Ck. However, this is an ideal case as protected groups may be imbalanced. Denote the size of each protected group as |Gi| and the size of the data set as N , we now show that the optimal balance is achieved if and only if P (x ∈ Gt|x ∈ Ck) = ρt. This result indicates the equivalence of optimizing fairness (equation 3) and generalized balance (equation 2).
Lemma 3.1. The optimal balance can be achieved only when all the clusters have the same balance. Formally, ∀i, j ∈ {1, 2, ...,K}: balance(Ci) = balance(Cj). Theorem 3.2. To achieve optimal balance value for multi-state protected variables, we must satisfy the condition: P (x ∈ Gt|x ∈ Ck) = ρt which is precisely the optimal fairness value for equation 2.

heading: 4 DEEP FAIR CLUSTERING ALGORITHM
text: We introduce our framework in this section. Our approach can be viewed as learning fair clustering under a discriminative clustering loss objective and a fairness objective with self-generated signals.

heading: 4.1 REVIEW OF BASE CLUSTERING MODEL
text: For base clustering model, we directly apply the previous work (Hu et al., 2017) and overview it here. We learn a neural network fθ as a discriminative function to predict the clustering assignments Y = σ(fθ(X)) ∈ RN×K based on input X ∈ RN×D and softmax function σ. The mutual information I(X;Y ) between X and Y is calculated as the difference between marginal entropy H(Y ) and conditional entropy H(Y |X):
I(X;Y ) = H(Y )−H(Y |X) = h( 1 N N∑ i=1 σ(fθ(xi)))− 1 N N∑ i=1 h(σ(fθ(xi))) (4)
where h is the entropy function. With weight decay term the clustering objective `C is as follows:
`C = 1
N N∑ i=1 h(σ(fθ(xi)))− h( 1 N N∑ i=1 σ(fθ(xi))) + α L∑ l=1 ‖θl‖2 (5)
where α denotes the hyper-parameter for network parameters {θ1 . . . θL}. Maximizing H(Y ) will punish imbalanced cluster size and prevent trivial solutions where all the instances are clustered into one cluster while minimizing H(Y |X) will map similar instances x to have similar labels y. Further, self-augmented training is applied to encourage the representations to be locally invariant. Here we add a local perturbation of instance x 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 t. Denote the current model’s parameters θ to help estimate the true clustering indicator vector for instance x as σ(fθ(x)), the formulation to compute the adversarial perturbation tadv is as follows:
tadv = argmax t;||t||2≤ KL(σ(fθ(x)), σ(fθ(x+ t))) (6)
With the generated tadv, we have the augmentation loss `Aug which minimizes the KL divergence between clustering assignment σ(fθ(xi)) and its augmented version’s assignment σ(fθ(xi ′ )):
`Aug = N∑ i=1 KL(σ(fθ(xi)), σ(fθ(xi ′ ))) (7)
Finally, the base clustering model optimizes the clustering loss `C and `Aug 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 are made and fits our fairness objective which requires fractional clustering assignments as inputs to indicate the degree of cluster assignment belief.

heading: 4.2 GENERATING FAIR ASSIGNMENTS UNDER GROUP-LEVEL FAIRNESS CONSTRAINTS
text: Let the fractional clustering assignments from the current learned model be Y = {y1, . . . yN} ∈ RN×K . To use these to form fair clustering assignments, we solve a fairer assignment matrix Ŷ = {ŷ1, . . . ŷN} ∈ ZN×K that satisfy the fair optimal condition: P (x ∈ Gt|x ∈ Ck) = ρt. 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:
Objective: argmin Ŷ N∑ i=1 [1− yi × ŷiT ] (8)
Recall yi is a row vector which represents the probability distribution over the cluster assignments for instance i and ŷi chooses exactly one cluster to assign instance i to. Naturally the objective is maximized when yi is assigned to its most probable cluster but this may cause an unfair clustering.
We denote ρi = |Gi|/N as the fraction of the protected group Gi in the data set and our aim is for each cluster to have the same density. Let M ∈ ZN×T encode the sensitive attributes for the entire population such that Mit ∈ {0, 1} indicates whether an instance xi belongs to a protected group Gt. To satisfy optimal fair condition P (x ∈ Gt|x ∈ Ck) = ρt we have the following constraints:
N∑ i=1 Mitŷij = N∑ i=1 ŷijρt ∀j ∈ {1 . . .K}, t ∈ {1 . . . T} (9)
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 assignment Y as hard assignments Y ′ by assigning the
cluster with largest probability. Then the size of cluster Cj is |Cj | = ∑N i=1 y ′
ij . The constraints for new clusters’ size are:
N∑ i=1 ŷij = |Cj | ∀j ∈ {1 . . .K} (10)
Lastly we add constraints for Ŷ to ensure each instance is assigned to one cluster:
K∑ j=1 ŷij = 1 ∀i ∈ {1 . . . N} (11)
Note this ILP formulation also supports user-defined ρt which can be seen as a flexible fairness rule. Next we show the constraint matrix of our ILP problem is totally unimodular so that we can efficiently solve it with a LP solver and still return integral solutions.
We know that if a 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 (Vaidya, 1989) has shown that the running 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 9, 10 and 11, we will use NK regular variables. Matrix C has T + 1 rows (the first T rows correspond to the fairness constraints in equation 9 and last row corresponds to
Algorithm 1 Main learning algorithm for deep fair discriminative clustering.
Input: Input {xk}Nk=1, sensitive attributes M , cluster size K, network structure f , hyper-parameters α, β, γ. Output: Clustering network fθ , predictions {yk}Nk=1 . 1: for each pre-trained epoch do 2: for sampled mini-batch {xk}nk=1 do 3: Calculate `C = 1n ∑n i=1 h(σ(fθ(xi)))− h( 1 n ∑n i=1 σ(fθ(xi))) + α ∑L l=1 ‖θ l‖2
4: Generate x ′ k = xk + t via solving t from eq 6. 5: Calculate `Aug = ∑n i=1 KL(σ(fθ(xi)), σ(fθ(x ′ i))) 6: Update network fθ via minimizing `C + γ`Aug . 7: end for 8: end for 9: repeat
10: Generate predictions {yk}Nk=1 based on fθ . 11: Construct a fair assignment problem via objective 8 and constraints defined in eq 9, 10 and 11. 12: Solve fair assignments {ŷk}Nk=1 via LP solver. 13: for sampled mini-batch {xk}nk=1 do 14: Calculate `Fair = 1n ∑n i=1 ŷilog(σ(fθ(xi)))
15: Calculate `C = 1n ∑n i=1 h(σ(fθ(xi)))− h( 1 n ∑n i=1 σ(fθ(xi))) + α ∑L l=1 ‖θ l‖2 16: Generate x ′ k = xk + t via solving t from eq 6.
17: Calculate `Aug = ∑n i=1 KL(σ(fθ(xi)), σ(fθ(x ′ i))) 18: Calculate ` = `C + β`Fair + γ`Aug 19: Update network fθ via minimizing `. 20: end for 21: until {yk}Nk=1 satisfy optimal fairness rules
constraints in equation 11) 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 are 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 9, each instance only belongs to one protected group, (2) for constraints set in equation 11, there is only one row vector with K elements as 1 to ensure the valid assignment. Lemma 4.1. TU Identity (Schrijver, 1998). Let C be a matrix such that all its entries are from {0, 1,−1}. Then C is totally unimodular, i.e., each square submatrix of C has determinant 0, 1, or −1 if every 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, 1,−1}. Theorem 4.2. The matrix C formed by the coefficients of the constraints used to encode our proposed constraints from equation 9, 10 and equation 11 is totally unimodular.

heading: 4.3 LEARNING TO BE FAIRER
text: To learn a fair clustering model we aim to exploit the fairness assignments Ŷ to reshape the features learned via clustering networks fθ. We treat Ŷ as “pseudo-labels” to optimize the following cross entropy loss `Fair for fairer results:
`Fair = 1
N N∑ i=1 K∑ j=1 ŷij logyij = 1 N N∑ i=1 ŷilog(σ(fθ(xi))) (12)
Simply optimizing the fairness loss `Fair will dramatically change the current clustering representations to fit an approximated fair assignment Ŷ which harms the clustering properties. Instead, we propose to learn a fairer and clustering-friendly representation simultaneously by combining the clustering loss `C , augmentation loss `Aug and fairness loss `Fair. 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 f(θ) via optimizing the clustering loss `C and augmentation loss `Aug to ensure the data are separated into different meaningful clusters; as clustering model converges we generate fair assignments after each training epoch based on the objective in equation 8 and optimize the overall loss function ` by concatenating the fairness loss `Fair to clustering objectives as ` = `C + β`Fair + γ`Aug where β, γ are positive weight hyper-parameters. Algorithm 1 summarizes the proposed learning method.

heading: 5 EXPERIMENTS
text: We conduct experiments1 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 a latent space useful for fair clustering quickly and also provides insights on tuning hyper-parameter β in unsupervised way to achieve our fairness goal with a minimum loss on clustering performance.

heading: 5.1 EXPERIMENTAL SETUP
text: 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 3 attributes (“age”, “balance”, “duration-of-account”) and binary PSV marital, we set whether a client 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 a payment as the label.
To measure the clustering quality for deep fair clustering and other baselines, we use both clustering accuracy (ACC) (Xu et al., 2003; Yang et 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, we use DEC (Xie et al., 2016) as a representative method for centroid-based clustering and IMSAT (Hu et al., 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 et al., 2019). For deep fair clustering baselines, we compare our work with the latest work (Li et al., 2020) and the geometric-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 features like (Li et al., 2020). For the LP solver we use the Gurobi optimizer. More details about datasets and experimental setup are given in Appendix.

heading: 5.2 EVALUATION
text: Fair clustering results on high dimensional data: as shown in the Table 1, traditional fair clustering algorithms achieve good fairness results especially ScFC 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 fairness 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 ILP’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 1
1In our experimental work we use the fair clustering data sets used by earlier work for comparison.
we can see the fairness rules can be seen as positive guidance to improve the clustering performance, our approach is shown to be able to learn from this guidance and improve fairness 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 a 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 in Figure 2. 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 1 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 2 (c). We find that our model achieves similar clustering results as k-Means on tabular data with human-defined semantic features. Meanwhile, we notice that k-Means algorithm achieves good fairness results when the number of clusters is correctly set as the ground truth number of classes. Finally, our model can achieve optimal balance with a slight loss in terms of clustering accuracy.

heading: 5.3 FURTHER ANALYSIS ON OUR MODEL
text: Here we explore our model’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 a 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 fairness signals the red instances start to move to different clusters. Meanwhile, we observe our learned representations maintain good clustering properties.
Tuning the weight of fairness objective: we experiment on the choices of hyper-parameter β 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 as β increases, the training balance increases. Meanwhile,
based on (b) and (d) we can find the ACC goes up and down as β 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 β from 0. But we also observe that with a very large β the clustering accuracy will drop. We hypothesize this is because the fairness objective dominates the overall objective so that the impact of clustering objective is hindered. As balance can be tracked during the training process for free, our insight for selecting hyper-parameter β is to pick the smallest β that achieves satisfying balance results.
Results on flexible fairness constraints with MNIST-USPS: here we explore how relaxing the optimal fair condition defined as ρt in equation 9 produces flexible constraints. We now require the fairness requirement to be in the interval [ρt ∗ (1 − ), ρt ∗ (1 + )]. In Figure 5 (a), we can see a larger relaxation degree leads to a lower balance which as expected; since the fairness signals can serve as positive guidance for clustering in MNIST-USPS, we observe the ACC and NMI are decreasing with larger . 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 of overall training loss and the balance results in Figure 5 (b) and (c). We can see 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.

heading: 6 CONCLUSION
text: In this paper, we explore the novel direction of adding fairness into deep clustering. This is a challenging 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 a 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 a deep learner and show that our formulation works with multi-state sensitive attributes as well as flexible fairness constraints that can occur in real-life applications. Extensive experiments demonstrate the strong performance of our approach and an in-depth analysis including feature space visualization, hyper-parameter tuning, model convergence analysis, and investigating flexible fair constraints shows its versatility.
ETHICS STATEMENT
Our work is proposed to ensure the fairness of deep clustering algorithms. One advantage of our work is 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 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 hyper-parameters in the Appendix.

heading: A THEOREMS AND PROOFS
text: Lemma A.1. (Lemma 3.1). The optimal balance can be achieved only when all the clusters have the same balance. Formally, ∀i, j ∈ {1, 2, ...,K}: balance(Ci) = balance(Cj).
Proof. The proof is by contradiction, we assume the optimal balance can be achieved when not all clusters have the same balance. Let cluster Ci have the largest balance as bmax and cluster Cj has the smallest balance as bmin. Denote the number of T different groups’ instances in Ci as {Ci1, Ci2, . . . , CiT }, similarly the composition for Cj as {Cj1, Cj2, . . . , CjT }. Assume the balance for Ci is achieved by bmax = CiαCiβ , the balance for Cj is achieved by bmin = Cjγ Cjθ
. Now we discuss two possible cases:
Case 1: If α = γ and β = θ. Based on our definition we have CiαCiβ > Cjα Cjβ . Let r = 12 ( Ciα Ciβ + Cjα Cjβ ), we can move instances which belong to group α from Ci to Cj to achieve the higher balance r. This can be done by setting Ciα− Ciβ = Cjα+ Cjβ = r.
Case 2: If α 6= γ or β 6= θ. Based on the balance definition we have CiγCiθ ≥ Ciα Ciβ . Based on our definition we have CiαCiβ > Cjγ Cjθ . Thus we have CiγCiθ ≥ Ciα Ciβ > Cjγ Cjθ . Similar as in case 1 we can move
′
instances which belong to group γ from Ci to Cj to achieve higher balance r′ = 12 ( Ciγ Ciθ + Cjγ Cjθ ).
In both cases, we can swap some instances between clusters to increase the final balance. This contradicts our assumption and completes our proof.
Theorem A.2. (Theorem 3.2). To achieve optimal balance value for multi-state protected variables, we must satisfy the condition: P (x ∈ Gt|x ∈ Ck) = ρt which is precisely the optimal fairness value for equation2 2.
Proof. Given the condition P (x ∈ Gt|x ∈ Ck) = ρt, let Gmin be the smallest protected group and Gmax be the largest protected group, the largest balance we can achieve is |Gmin|/|Gmax|. The proof by contradiction assumes these exists a solution where all the clusters have the same balance (based on lemma A.1) and have balance α > |Gmin|/|Gmax|. For each cluster we sort each protected group based on their size in an increasing order. We use C∗i1, C ∗ i2 . . . C ∗ iT to denote the size of the sorted groups in cluster i. Obviously we have α = C ∗ i1
C∗iT for any cluster i. Now we sum up the smallest group among all the K clusters as S: S = ∑K i=1 C ∗ i1. Similarly we can calculate the sum of the
largest group among all the clusters as: ∑K i=1 C ∗ iT = 1 α ∑K i=1 C ∗ i1 = S α . Consider the allocation of
the smallest group Gmin we have the following inequality: |Gmin| ≥ ∑K i=1 C ∗ i1 = S. Similarly we
have |Gmax| ≤ ∑K i=1 C ∗ iT = S α . By combining previous two inequalities we have α|Gmax| ≤ S ≤ |Gmin| which means |Gmin|/|Gmax| ≥ α. This contradicts with our initial assumption that there exists a α which is larger than |Gmin|/|Gmax|. Thus we complete the proof.
Proof Total Unimodularity of Constraint Matrix We know that if a 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 Vaidya (1989) has shown that the running 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 7, constraint 8 and constraint 9, we will use NK regular variables. Matrix C has T +1 rows (the first T rows correspond to the fairness 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 are 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 to 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.
2All the equations referenced in appendix are in the main paper.
Lemma A.3. (Lemma 4.1). TU Identity (Schrijver, 1998). Let C be a matrix such that all its entries are from {0, 1,−1}. Then C is totally unimodular, i.e., each square submatrix of C has determinant 0, 1, or −1 if every 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, 1,−1}. Theorem A.4. (Theorem 4.2). The matrix C formed by the coefficients of the constraints used to encode our 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 A and B 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 rows are put into B. Let row vectors SA and SB denote the sums of the rows within A and B respectively. It is clear that elements in SA and SB are from {1, 0,−1} because each column only has one non-zero element. Now we show all the elements in SA−SB are from {1, 0,−1}. Firstly there will be only one non-zero element in SA, and we denote the column which has a non-zero element as r. If column r belongs to the fairness constraints (from column 1 to column N in C), then the column r within SB will be 0 since one instance only belongs to one protected group. If the column r belongs to the valid assignment constraints (from column N + 1 to N +K in C) then column r within SB will be 0 since those elements are filled with 0. Thus column r of SA − SB is still from {1, 0,−1}. The non-zero elements in other columns will change their sign but still from {1, 0,−1}. This completes the proof.

heading: B BASELINES IMPLEMENTATIONS
text: For the k-means baseline, we choose to use the k-means++ implementation from scikit-learn library. For scalable fair clustering work (Backurs et al., 2019), we use the code from their author’s github repository (https://github.com/talwagner/fair_clustering). For deep embedding clustering (Xie et al., 2016) we use the implementations from the public github repositories (https: //github.com/vlukiyanov/pt-dec) and for IMSAT (Hu et al., 2017) we use the code from their author’s github repository (https://github.com/weihua916/imsat). For Wang and Davidson’s deep fair clustering work (Wang & Davidson, 2019), we have contacted the author to 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.

heading: C HYPER-PARAMETERS AND ARCHITECTURES OF OUR APPROACH
text: For the digit datasets like reverse-MNIST and MNIST-USPS, we use a 2-block convolutional architecture with first block consisting of a convolutional layer with 8 (5 × 5) filters and second block consisting of 4 (5 × 5) filters. Each block is followed with BatchNorm, ReLU activation and max pooling layers. The second block is finally connected to a fully connected layer with 10 units. For the HAR data we use a stacked fully connected neural network with intermediate layers as d − 1200 − 1200 − k, note d = 561 is the total number of features in HAR and k = 6 is the number of clusters. Moreover, we have listed the hyper-parameters that we used for these three data sets in Table 2. In unsupervised learning, it is not straightforward to determine hyper-parameters by cross-validation. Hence, we fixed the hyper-parameters (weight decay α and augmentation term γ) across all the datasets; we tuned the hyper-parameter β based on the training set’s balance value as mentioned in the main paper to achieve satisfying fair results.
For the traditional fair clustering data sets, we use a stacked fully connected neural network with intermediate layers as d− 50− 50− k, note the total number of features d for Census, Credit and Bank are 5, 3, 14 and k = 2 is the number of clusters. Moreover, we have listed the hyperparameters that we used for these three data sets in Table 3. We set the same values for hyper-parameters α and γ. Since these tabular data sets only have limited features we observe that fewer training epochs are needed to train our model.

heading: D EXTRA EXPERIMENTAL RESULTS
text: 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 our algorithm in Python 3.6 and run our experiments on a PC with a 3.3 GHz Intel Core i9 Processor and 1 GeForce RTX 2080 TI graphic card. We use Gurobi 3 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.
CLUSTERING RESULTS VISUALIZATION
Figure 6 and 7 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 to 0 balance. Instead, our approach successfully separated them into different clusters to achieve fairness goals.
3https://www.gurobi.com/

Review summaries:
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. 

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:  1) find fair assignments $\hat y$ based on $y$; 2) tune the latent representations and $y$ according to the pseudo-label $\hat y$.