Fair Minimum Representation Clustering via Integer Programming
Connor Lawless Oktay Gunluk

	
        1]Connor Lawless
        2]Oktay Günlük
        [1]Management Science and Engineering, Stanford University
        [2]Industrial and Systems Engineering, Georgia Institute of
Technology

	
	Fair Minimum Representation Clustering via Integer Programming A preliminary version of this paper appeared in CPAIOR 2024.
    [
    
===========================================================================================================================



	§ ABSTRACT 
        Clustering is an unsupervised learning task that aims to partition data into a set of clusters. In many applications, these clusters correspond to real-world constructs (e.g., electoral districts, playlists, TV channels) whose benefit can only be attained by groups when they reach a minimum level of representation (e.g., 50% to elect their desired candidate). In this paper, we study the k-means and k-medians clustering problems with the additional constraint that each group (e.g., demographic group) must have a minimum level of representation in at least a given number of clusters. We formulate the problem through a mixed-integer optimization framework and present an alternating minimization algorithm, called MiniReL, that directly incorporates the fairness constraints. While incorporating the fairness criteria leads to an NP-Hard assignment problem within the algorithm, we provide computational approaches that make the algorithm practical even for large datasets. Numerical results show that the approach is able to create fairer clusters with practically no increase in the clustering cost across standard benchmark datasets. 

	
	


§ INTRODUCTION


Clustering is an unsupervised learning task that aims to partition data points into sets of similar data points called clusters <cit.>. Clustering is widely used due to its broad applicability in domains such as customer segmentation <cit.>, grouping content together for entertainment platforms <cit.>, and identifying subgroups within a clinical study <cit.> amongst others. However the wide-spread application of clustering, and machine learning broadly, to human-centric applications has raised concerns about its disparate impact on minority groups and other vulnerable demographics. Motivated by a flurry of recent results highlighting bias in many automated decision making tasks such as facial recognition <cit.> and criminal justice <cit.>, researchers have begun focusing on mechanisms to ensure machine learning algorithms are fair to all those affected. One of the challenges of fairness in an unsupervised learning context, compared to the supervised setting, is the lack of ground truth labels. 
Consequently, instead of enforcing approximately equal error rates across groups, fair clustering generally aims to ensure that composition of the clusters or their centers  (for settings like k-means and k-medians clustering)  represent all groups fairly.





A common approach to fair clustering is to require each cluster to have a fair proportion of itself represented by each group
(i.e., via balance <cit.> or bounded representation <cit.>). This approach aims to balance the presence of each group in each cluster and therefore tries to spread each group uniformly across the clusters.
Notice that this approach might not be desirable in settings where a group only gains a significant benefit from the cluster when they reach a minimum level of representation in that cluster. Consider the problem of clustering a set of media (e.g., songs, tv shows) into cohesive segments (e.g., playlists, channels). A natural fairness consideration in designing these segments would be to ensure that there is sufficient representation for different demographic groups. In these settings the benefit of the representation is only realized when a large percentage of the segment is associated with a demographic group (i.e., so that listeners can consistently watch or hear programming that speaks to them). This is even legislated in some countries, for example Canadian television channels are required to have at least 50% Canadian programming <cit.>. Note that, in this setting, spreading a minority demographic group across all clusters ensures that the demographic group will never have majority representation in any segment.

As another example, consider a simple voting system for a committee where the goal is to first cluster voters (e.g., employees, faculty) into different constituencies that can then elect a committee representative. Here, a proportionally fair clustering would assign a minority group that represents 30% of the vote equally among each cluster. However, the minority group only gets a benefit (i.e., the ability to elect a candidate of their choice) if they have at least 50% representation in the cluster. In this paper we introduce a new notion of fairness in clustering that addresses this issue. Specifically, we introduce minimum representation fairness (MR-fairness) which requires each group to have a certain number of clusters where they cross a given minimum representation threshold (i.e., 50% in the voting example).




Arguably the most popular algorithms for clustering is Lloyd's algorithm for k-means clustering <cit.>, and the associated alternating minimization approach for k-medians <cit.>. 
These iterative algorithms alternate between fixing cluster centers and assigning each point to the closest cluster center.
Both algorithms are guaranteed to return a locally optimal
solution (i.e., no perturbation of the cluster centers around the solution leads to a better clustering cost). However, using these algorithms can lead to clusters that violate MR-fairness. As an example, consider the Adult dataset which contains census data for 48842 individuals in 1994 <cit.>. Suppose we wanted to cluster these individuals into groups that represent different stakeholder groups for a local committee and geographic contiguity was not a concern. A natural fairness criteria in this setting would be to ensure that there are a sufficient number of groups where minority groups (i.e., non-white in this dataset) have majority voting power. Despite the fact that only approximately 85% of the dataset is white, every cluster produced by Lloyd's algorithm is dominated by white members even when the number of clusters is as high as twenty. This highlights the need for a new approach to address fair minority representation.






In this paper we introduce a modified version of Lloyd's algorithm for k-means and k-medians that ensures minimum representation fairness, henceforth referred to as MINIimum REpresentation fair Lloyd's algorithm (MiniReL for short). The key modification behind our approach is to replace the original greedy assignment step with a new optimization problem that finds the minimum cost assignment while ensuring fairness. In contrast to the standard clustering setting, we show that finding a minimum cost clustering that respects MR-fairness is NP-Hard even when the cluster centers are already fixed. We show that this optimization problem can be solved via integer programming (IP) in practice and introduce a number of computational approaches to improve the run-time. We empirically show that our approach is able to construct fair clusters which have nearly the same clustering cost as those produced by Lloyd's algorithm.




 §.§ Minimum Representation Fair Clustering Problem



The input to the standard clustering problem is a set of n m-dimensional data points 𝒳 = {x^i ∈R^m}_i=1^n. Note that assuming the data points to have real-valued features is not a restrictive assumption as categorical features can be converted to real-valued features through the one-hot encoding scheme. The goal of the clustering problem is to partition the data points into a set of K clusters 𝒞 = {C_1, …, C_K } in such a way that some measure of clustering cost is minimized.
Let K = {1, …, K} be the set of clusters. 







In the fair clustering setting, each data point x^i  has a (small) number of sensitive features such as gender and race associated with it. Each sensitive feature can take a finite number of possible values (e.g., male, female, or non-binary for gender).
We denote the set of sensitive features with F and possible values of a feature f ∈ F with the set G_f.
We use G = ∪_f ∈ F G_f to be the set of all possible values of all features, and call each g∈ G a group.
With this notation, each data point x^i is associated with | F| many groups, one for each f∈ℱ (i.e., gender, race).
Let X_g be the set of data points associated with group g∈𝒢 and note that unlike other fair machine learning work, we do not assume that {X_g}_g∈ G form a partition of 𝒳 when | F|>1. 
Instead, {X_g}_g∈ G_f forms a partition of 𝒳 for each sensitive feature  f ∈ F. 

The key intuition behind MR-fair clustering is that individuals belonging to a group gain material benefit only when they have a minimum level of representation in their cluster. We denote this minimum representation threshold α∈ (0,1], and define the associated notion of an α-representation as follows:


   A group g∈𝒢  is said to be α-represented in a cluster C_k if 
    
    | C_k ∩ X_g | ≥α |C_k|

    
    
Note that α represents the minimum threshold needed for a given group to receive benefit from a cluster and thus depends on the application. For instance, most voting systems require majority representation (i.e., α = 0.5). Our framework also allows for α to be group-dependent (i.e., α_g for each group g), however in most applications of interest α is a fixed threshold regardless of group. 
For a given clustering 𝒞, group g∈ G, and α∈ (0,1], let Λ(𝒞, X_g, α) be the number of clusters where group g has α-represention. In MR-fairness, each group g has a parameter β_g that specifies a minimum number of clusters where that group should have α-represention.



A given clustering 𝒞 = {C_1, …, C_K} is said to be an (α,β)-minimum representation fair clustering if for every group g ∈𝒢:

    Λ(𝒞, X_g, α) ≥β_g

for a given β = {β_g ∈ℤ^+}_g ∈𝒢.





The definition of MR-fairness is flexible enough that the choice of  β can (and should) be specialized to each application as well as the choice of α. Also note that up to ⌊ 1/α⌋ groups corresponding to a single feature f can be α-represented in a cluster.
In the remainder of the paper we explore two different natural choices for β that mirror fairness definitions in the fair classification literature. The first sets β_g to be equal for all groups corresponding to the same feature:

    β_g = ⌊1/|𝒢_f|⌊α^-1⌋ K ⌋  ∀ g ∈𝒢, f ∈ F

which we denote cluster statistical parity. The second set choice sets β_g to be proportional to the size of the group: 

    β_g = ⌊|X_g|/n⌊α^-1⌋ K ⌋  ∀ g ∈𝒢
 
which we denote cluster equality of opportunity. Note that in both cases, β_g should be at most K (i.e., if α is very small, we set β_g = K).
 
























For a given α∈ (0,1] and β = {β_g ∈ℤ^+}_g ∈𝒢, the minimum representation fair k-means and k-medians problems are:

    min_𝒞, c_1,…,c_K ∈ L∑_k ∈𝒦∑_x^i ∈ C_k D(x^i, c_k)
      s.t.  Λ(𝒞, X_g, α) ≥β_g  ∀ g ∈𝒢

where L = R^m, D(x^i, c) = x^i - c_2^2  for k-means, and L =  X, D(x^i, c) is a distance function for  k-medians problem. can the center not belong to the cluster? In the unfair formulation it never wouldn't, not sure what's meaningful in our setting (I think our implementation requires it).



For a given α∈ (0,1] and β = {β_g ∈ℤ^+}_g ∈𝒢, the minimum representation fair k-means problem is:

    min_𝒞, c_1,…,c_K∑_k ∈𝒦∑_x^i ∈ C_kx^i - c_k^2
      s.t.  Λ(𝒞, X_g, α) ≥β_g  ∀ g ∈𝒢




The main difference between the  fair  and the standard versions of the k-means clustering problem is that greedily assigning data points to their closest cluster center may no longer be feasible for the fair version (i.e., assigning a data point to a farther cluster center may be necessary to meet the fairness criteria). Thus the problem can no longer be viewed simply as an optimization problem over cluster centers.

We integrate MR-fairness into two popular clustering paradigms: k-means and k-medians. In both settings the aim is to find a clustering together with a set of cluster centers {c_k ∈ L_k }_k=1^K. In the k-means setting the center of a cluster can be located anywhere in the feature space (i.e., L_k = R^m   ∀ k), whereas in k-medians it must be at one of the data points assigned to the cluster (i.e., L_k = C_k). Note that in the standard k-medians setting it is not necessary to explicitly require c_k∈ C_k as any (local) optimal solution would  satisfy this. However, this is no longer true in the MR-fairness setting and thus we explicitly constraint the center to belong to the cluster. We denote the cost of assigning a data point x^i to a cluster with center c with D(x^i, c) and the objective of the problem is to minimize the total cost of the clustering over all data points.
In the k-means setting the cost is equal to the squared distance between the data point and the center (i.e., D(x^i, c) = x^i - c^2), whereas in k-medians one can use any distance function. 
Combining the standard clustering problem with MR-fairness requirement leads to the following optimization problem:


For a given α∈ (0,1] and β = {β_g ∈ℤ^+}_g ∈𝒢, the minimum representation fair k-means and k-medians problems are:

    min_𝒞, c_1,…,c_K∑_k ∈𝒦∑_x^i ∈ C_k D(x^i, c_k)
      s.t.  Λ(𝒞, X_g, α) ≥β_g  ∀ g ∈𝒢,
    c_k ∈ L_k   ∀ k ∈ K

where L_k = R^m   ∀ k, D(x^i, c) = x^i - c_2^2  for k-means, and L_k = C_k, D(x^i, c) is any given distance function for  k-medians problem.


The main difference between the  fair  and the standard versions of the k-means and k-medians clustering problem is that greedily assigning data points to their closest cluster center may no longer be feasible for the fair version (i.e., assigning some data points to farther cluster centers may be necessary to meet the fairness criteria). Thus the problem can no longer be viewed as an optimization problem over cluster centers.




 §.§ Related Work


A recent flurry of work in fair clustering has given rise to a number of different notions of fairness. One broad line of research, started by the seminal work of <cit.>, puts constraints on the proportion of each cluster that comes from different groups. This can be in the form of balance <cit.> which ensures each group has relatively equal representation, or a group specific proportion such as the bounded representation criteria <cit.> or maximum fairness cost <cit.>. MR-fairness bares a resemblance to this line of work as it puts a constraint on the proportion of a group in a cluster, however instead of constraining a fixed proportion across all clusters it looks holistically across all clusters and ensures that threshold is met in a baseline number of clusters. Another line of work tries to minimize the worst case average clustering cost (i.e., k-means cost) over all the groups, called social fairness <cit.>. 
Most similar to our algorithmic approach is the Fair Lloyd algorithm introduced in <cit.> which studies social fairness. They also present a modified version of Lloyd's algorithm that converges to a local optimum. As a consequence of the social fairness criterion their approach requires a modified center computation step that can be done in polynomial time. MR-fairness, however, requires a modified cluster assignment step that is NP-hard which we solve via integer programming.

Most similar to MR-fairness is diversity-aware fairness introduced in <cit.> and the related notion of fair summarization <cit.>. These notions of fairness require that amongst all the cluster centers selected, a minimum number comes from each group. MR-fairness differs in that our criteria is not tied to the group membership of the cluster center selected but the proportion of each group in a given cluster. Our notion of fairness 
is more relevant in settings where the center cannot be prescribed directly, but is only a function of its composition (i.e., in voting where members of a `cluster' elect an official).    

There is also a long line of research that looks at fairness in the context of gerrymandering <cit.>. While our notion of fairness shares some similarity with different notions of fairness in gerrymandering, the gerrymandering problem places different constraints on the construction of the clusters such as contiguity. Consequently the algorithmic approaches to tackle gerrymandering generally require more computationally intensive optimization procedures that do not readily transfer to the machine learning setting.




 §.§ Main Contributions



We summarize our main contributions as follows:


  * We introduce a novel definition of fairness for clustering of practical importance called MR-fairness, which requires that a specified number of clusters should have at least α percent members from a given group.



  * We formulate the problem of finding a MR-fair k-means or k-medians clustering in a mixed integer optimization framework, and introduce a new heuristic algorithm MiniReL, based on Lloyd's algorithm for clustering, to find a local optimum.


  * We show that unlike other notions of proportional fairness,  this problem can not be approximated by  adjusting unfair cluster centers.


  * We show that incorporating MR-fairness into Lloyd's algorithm leads to a NP-Hard sub-problem to assign data points to fixed cluster centers, which we call the Fair Minimum Representation Assignment (FMRA) Problem. 


  * We introduce a two-stage decomposition approach to solving the FMRA problem that includes a polynomial time bi-criteria approximation algorithm based on a network flow formulation. We also introduce a polynomial time heuristic for setting the first-stage variables.


  * We present numerical results to demonstrate that MiniReL is able to construct MR-fair clusterings with only a modest increase in run-time and with little to no increase in clustering cost compared to the standard k-means or k -medians clustering algorithm.  


An initial version of this paper was published in a conference publication <cit.> which introduced MR-fairness and a basic version of the MiniReL algorithm with pre-fixing. In this work we extend MiniReL to the k-medians setting and present new computational studies to show its efficacy. In addition, we build upon MiniReL's algorithmic framework and introduce a two-stage decomposition framework to solve the FMRA including a polynomial time heuristic for solving the FMRA under pre-fixing built around a network flow model. We also provide additional theoretic results on the total unimodularity of the heuristic pre-fixing IP presented in the conference version, and additional NP-hardness results on variants of the FMRA problem. 

The remainder of the paper is organized as follows. In Section <ref> we present a mixed integer optimization formulation for the MR-fair clustering problem and introduce MiniReL. In Section <ref> we introduce computational approaches to help our algorithm scale to large datasets. Finally Section <ref> presents a numerical study of MiniReL compared to the standard Lloyd's algorithm.		


§ MIXED INTEGER OPTIMIZATION FRAMEWORK
 

We start by formulating the MR-fair k-means clustering problem as a mixed-integer program with a non-linear objective. We use binary variable z_ik to denote if data point x^i is assigned to cluster k, and variable c_k ∈ℝ^d to denote the center of cluster k. The binary variable y_gk indicates whether group g is α-represented in cluster k. Let L_k(z) be the set of allowable cluster center locations for cluster k as a function of the current cluster assignments, (i.e., L_k(𝐳) = R^m for k-means). To represent L_k in the k-medians case, we introduce additional binary decision variables d_ik to denote if data point i is selected as the center for cluster k. The set L_k(𝐳) is the set defined by the following constraints:

    L_k(𝐳) = {c_k∈ℛ^m : c_k = ∑_x^i ∈ X d_ik x^i,  
        d_ik≤ z_ik  ∀ x^i ∈ X ,  ∑_x^i ∈ X d_ik = 1,  
        d_ik∈{0,1}  ∀ x^i ∈ X}

 



We can now formulate the MR-fair clustering problem as follows:


    min        ∑_x^i ∈𝒳∑_k ∈𝒦 D(x^i,c_k) z_ik
    s.t.        ∑_k ∈𝒦  z_ik   = 1         ∀ x^i ∈𝒳
          ∑_x^i ∈ X_g z_ik +  M (1 - y_gk)   ≥α∑_x^i ∈𝒳 z_ik        ∀ g ∈𝒢, k ∈𝒦
          ∑_k ∈𝒦 y_gk   ≥β_g       ∀ g ∈𝒢
           u≥∑_x^i ∈𝒳 z_ik   ≥ l       ∀ k ∈𝒦
          z_ik   ∈{0,1}      ∀ x^i ∈𝒳, k ∈𝒦
          y_gk   ∈{0,1}      ∀ g ∈𝒢, k ∈𝒦
          c_k    ∈ L_k(z)       ∀ k ∈𝒦


The objective (<ref>) is to minimize the cost of the clustering. Constraint (<ref>) ensures that each data point is assigned to exactly one cluster. Constraint (<ref>) tracks whether a cluster k is α-represented by a group g, and includes a big-M which can be set to α n. Finally, constraint (<ref>) tracks that each group g is α-represented  in at least β_g clusters. In many applications of interest, it might also be worthwhile to add a constraint on the size of the clusters to ensure that each cluster has a  minimum/maximum number of data points. Constraint (<ref>) captures this notion of a cardinality constraint where l and u represent the lower and upper bound for the cardinality of each cluster respectively. Note that in cases where the cardinality constraint is used, the big-M in constraint (<ref>) can be reduced to α u. In all our experiments we make sure that l ≥ 1 so that exactly k clusters are returned by the algorithm. This ensures that each group is α-represented in non-trivial clusters. Note that every group would be trivially α-represented in an empty cluster according to Definition <ref> but would provide little practical use.



We can now formulate the MR-fair clustering problem as follows:

    min        ∑_x^i ∈𝒳∑_k ∈𝒦x^i - c_k_2^2 z_ik
    s.t.        ∑_k ∈𝒦  z_ik   = 1         ∀ x^i ∈𝒳
          ∑_x^i ∈ X_g z_ik +  M (1 - y_gk)   ≥α∑_x^i ∈𝒳 z_ik        ∀ g ∈𝒢, k ∈𝒦
          ∑_k ∈𝒦 y_gk   ≥β_g       ∀ g ∈𝒢
           u≥∑_x^i ∈𝒳 z_ik   ≥ l       ∀ k ∈𝒦
          z_ik, y_gk   ∈{0,1}      ∀ x^i ∈𝒳, g ∈𝒢, k ∈𝒦
          c_k    ∈R^m      ∀ k ∈𝒦


The objective (<ref>) is to minimize the sum of the squared distances between the data points and the centers of the clusters they are assigned to. Constraint (<ref>) ensures that each data point is assigned to exactly one cluster. Constraint (<ref>) tracks whether a group g is α-represented in cluster k, and includes a big-M which can be set to α n. Finally, constraint (<ref>) enforces that each group g is α-represented  in at least β_g clusters. In many applications of interest, it might also be necessary to add a constraint on the size of the clusters. Constraint (<ref>) captures this notion where l and u represent the lower and upper bounds on the cardinality of each cluster respectively. Note that in cases where the cardinality constraint is used, the big-M in constraint (<ref>) can be reduced to α u. For all our experiments we set l = 1 to ensure that exactly k clusters are returned by the algorithm. Adding a lower bound also ensures that each group is α-represented in non-trivial clusters. Note that without this lower bound every group would be trivially α-represented in an empty cluster according to Definition <ref>.


To solve problem (<ref>)-(<ref>) in practice, we introduce a modified version of Lloyd's algorithm called MiniReL, which requires solving a fair assignment problem, in Section <ref>. In Section <ref> we show that, 
unlike other notions of fairness in clustering, first solving the clustering problem without fairness constraints and then finding a fair assignment of the data points to these centers can lead to arbitrarily poor results under MR-fairness which further justifies the use of an iterative approach such as MiniReL.






 §.§ MiniReL Algorithm for Fair Clustering
 

Solving the optimization problem outlined in the preceding section to optimality is computationally challenging as it is a large scale integer optimization problem with a non-convex objective function. To solve the problem in practice, we introduce a modified version of Lloyd's algorithm which we call the Minimum Representation Fair Lloyd's Algorithm (MiniReL) that alternates between adjusting cluster centers and fairly assigning data points to clusters to converge to a local optimum, see Algorithm <ref>. 



Note that the only difference between Lloyd's algorithm for k-means and k-medians is how centers are computed. Given a fixed set of cluster assignments (i.e., when variables z are fixed in (<ref>)-(<ref>)) the optimal choice of c_k is the mean value of data points assigned to C_k for k-means whereas it is found by searching across all data points in the cluster for k-medians <cit.>. In the case of multiple centers with the same cost in the k-medians setting we use deterministic tie-breaking and chose the center corresponding to the data point that comes first in the lexicographic ordering of the dataset which we set-up at the beginning of the algorithm. For simplicity, we will refer to both algorithms (with separate center computation approaches) as Lloyd's algorithm for the remainder of the paper. 

For a given (fixed) set of cluster centers c_k we denote the problem (<ref>)-(<ref>) the fair minimum representation assignment (FMRA) problem which is a linear integer program. While the optimal assignment step in Lloyd's algorithm can be done in polynomial time, the following result shows that the FMRA problem is NP-Hard.

 
The fair minimum representation assignment problem is NP-Hard.


See Appendix <ref> for proof. Note that if the FMRA problem is infeasible (for any given collection of cluster centers), it provides a certificate that no MR-fair clustering with the given α, β exists. While integer programs do not always scale well to large datasets, in our computational experiments we observed that FMRA can be solved to optimality in a reasonable amount of time even for datasets with tens of thousands of data points. In Section <ref> we describe the computational techniques that help scale our algorithm. 

A natural question is whether MiniReL converges to a locally optimal solution as Lloyd's algorithm does. When discussing local optimality, it is important to formally define the local neighborhood of a solution. In the absence of fairness constraints, data points must be assigned to the closest centers to minimize cost. Consequently, a clustering is locally optimal if perturbing the centers does not improve the clustering cost.


In our setting, we define a local change as any perturbation to a cluster center, or an individual change to cluster assignment (i.e., moving a data point from one cluster to another). With this notion of a local neighborhood, the following result shows that the MiniReL converges to a local optimum in finite time. Note that while MiniReL converges to a local optimum, the solution may be arbitrarily worse than the global optimum as is the case for Lloyd's algorithm.

  
MiniReL converges to a local optimum in finite time.


For proof please see Appendix <ref>.





 §.§ A Natural Solution Approach and an Inapproximability Result
 

One natural approach <cit.> used for other notions of fairness in clustering is to first obtain cluster centers by solving the clustering problem without fairness constraints and then find a fair assignment of the data points to these centers. This has been shown to provide an overall approximation guarantee for the full optimization problem in some settings even when the centers are only approximately optimal for the clustering problem without fairness constraints <cit.>. 
Unfortunately, we show that in our MR-fairness setting this approach, which we call one-shot fair adjustment, can lead to arbitrarily bad solutions. Let z^*, c^* be the optimal solution to the MR-fair clustering problem. Let c^*_UF be the optimal centers for the clustering problem without fairness constraints and z^*_FA be the optimal (fair) assignment of data points to centers c^*_UF. Note both z^* and z^*_FA are feasible fair assignments. Let COST(z, c) = ∑_x^i ∈𝒳∑_k ∈𝒦 D(x^i, c_k) z_ik be the objective for the clustering problem. 


 
There does not exist a constant M > 0 such that:

    COST(z^*_FA, c^*_UF) ≤ M ·  COST(z^*, c^*)

In other words, fairly assigning data points to (approximately) optimal unfair centers can lead to arbitrarily bad performance relative to the optimal solution of the MR-fair clustering problem.





Proof of Theorem <ref>
To prove the claim we will construct an instance of the MR-fair k-means problem in two dimensions with four data points and three groups (Red, Blue, and Yellow). The first two points are located at (0,0) and belong to the red and blue groups, respectively. The next two data points belong to the yellow group and are located at (γ,0) and (γ,ϵ) for some γ,ϵ>0. For the fair clustering problem, we set K=3, α > 0.5, and β_R=β_Y=β_B=1. 

Note that any optimal solution to the clustering problem without fairness constraints will place the cluster centers c^*_UF  at (0,0), (γ,0), (γ,ϵ) with cost 0. It is straightforward to see that fairly assigning points to these fixed centers requires assigning either the red or blue data point to the center at (γ, 0) and assigning the yellow data point at (γ, 0) to the center at (γ, ϵ) yielding a cost of γ^2 + ϵ^2. Now consider the optimal solution to the fair clustering problem which selects centers at (0,0), (0,0), (γ,ϵ/2). It assigns the red data point to the first center at (0,0), the blue data point to the second center at (0,0), and both yellow data points to the center at (γ,ϵ/2) which satisfies the fairness constraints and gives a total cost of ϵ^2/2. The ratio of the costs of the two solutions is γ^2 + ϵ^2/ϵ^2/2 which can be made arbitrarily large by increasing γ, completing the proof. Note that the same construction, with the same unfair centers and optimal fair centers at (0,0), (0,0), (γ,0) proves the same result in the k-medians setting. Figure <ref> shows both the bad instance and the optimal centers for the fair and unfair problems. 


Note that using the simple example constructed above,  one can argue that the cost of the optimal fair clustering can be arbitrarily larger than the cost of the optimal clustering without fairness. Also note that the above proof also shows that one can get an arbitrarily bad solution when the (unfair) cluster centers are chosen using a constant factor approximation algorithm.



		



§ SCALING MINIREL: TWO-STAGE DECOMPOSITION
 





The main computational bottleneck of the MiniReL algorithm is solving the FMRA problem, which simultaneously selects which groups are α-represented in which clusters (i.e., set y_gk variables) and assigns data points to clusters in a way that satisfies said constraints  (i.e. sets z_ik variables). It is a computationally demanding problem to solve in practice both due to its scale (i.e., as the number of binary variables scales with the number of data points), symmetry, and its use of big-M constraints (i.e., that lead to weak linear relaxations <cit.>). To alleviate these computational challenges, we introduce a heuristic two-stage decomposition scheme that separates setting the y variables and z variables into two sequential problems. 

The first stage problem, which we call the  (), sets the y_gk variables. 
The second stage problem, which we call the (), sets the z_ik variables.  One approach to solve the first-stage problem is to solve the FMRA problem with relaxed z variables (i.e., problem (<ref>)-(<ref>) with fixed centers, y_gk binary and z_ik∈ [0,1]). This dramatically reduces the number of binary variables (relaxing nK binary variables), making the problem much faster to solve than FMRA in practice. While this approach does not guarantee the feasibility of an integral second-stage solution, in Section <ref> we show that this fractional assignment can be rounded to an integer assignment with only small violation to the fairness constraints. In Section <ref> we present an alternative heuristic approach to find a solution to the first-stage problem in polynomial time without the accompanying feasible fractional assignment of data points. 

The second stage problem () is akin to solving the FMRA problem with a fixed set of y_gk variables.
This removes the need for the y variables and the associated big-M constraints in the model formulation and breaks symmetry in the IP (i.e., removes permutations of feasible cluster assignments), dramatically improving the computation time. However, despite this simplification, the following result shows that the second-stage problem is still NP-Hard.

 
The Problem () is NP-Hard.



See Appendix <ref> for proof. Despite this negative result, in Section <ref> we present a polynomial time algorithm that solves with a small additive fairness violation. We emphasize that this two-stage decomposition scheme is a heuristic which is not guaranteed to solve the FMRA problem to optimality. However, we found in practice this two-stage approach is able to find solutions that have similar objectives in a fraction of the time of solving the full IP (see Section <ref> for an empirical evaluation). While both stages of the two-stage decomposition scheme can be solved sequentially at every iteration of the MiniReL algorithm, we found in practice the first stage solution changed infrequently during the execution of the algorithm. To further improve the computation time, we also present a pre-fixed version of the algorithm where we only set the y_gk variables once at the beginning of the algorithm. In problems where only a single group can have α-represention in a cluster (i.e., a data point can only be part of one group and α > 0.5), pre-fixing preserves an optimal solution to the full problem. However, in more complicated settings pre-fixing may remove all optimal solutions and becomes a heuristic for improving run-time. It is worth noting that the MiniReL algorithm is itself a heuristic, and thus the pre-fixing scheme has ambiguous effects on the cost of the solution as it may cause the algorithm to converge to a better local optimum. Figure <ref> presents a visual summary of the three different control flows for the MiniReL algorithm. 











 §.§ Solving via Polynomial Time Heuristic




Recall that the goal of the first stage problem is to find an assignment of groups to be α-represented in clusters to meet the MR-fairness constraints. In this section we present a polynomial time heuristic to find good performing settings of the y_gk variables. 


To find a good pre-fixing of the y variables, we use a fixed set of cluster centers and formulate a small integer program to find the lowest cost way to greedily meet the MR-fairenss constraints. There are multiple ways to formulate the cost of setting the y variables - we look at the myopic increase in clustering cost needed to meet the constraints (see Appendix <ref> for a computational comparison of different objectives). For a given cluster k and group g, let q_kg≥0 be the additional number of points from group g needed to make this group α-represented in cluster k (i.e., smallest integer q_kg≥0 that satisfies q_kg + |C_k∩ X_g| ≥α(q_kg + |C_k|)). Let c_(x) = _ c ∈{c_1, …, c_K}{x - c_2^2} denote the closest center for point x ∈ X. 
To find a good pre-fixing, we estimate the (myopic) increase in cost m_gk to make group g α-represented in cluster k as follows:


    m_gk = min_X ⊂ X_g ∖ C_K: |X| = q_kg∑_x ∈ X(D(x^i, c_k) - D(x^i, c_(x))))


 Note that this objective is a heuristic that does not take into account the impact of moving data points on the satisfaction of α-representation constraints from the cluster in which it is being moved from. We can now formulate the problem of performing the pre-fix assignment as follows: 

    1.5cmmin        ∑_(g,k) ∈𝒲 m_gk y_gk
    s.t.        ∑_k ∈𝒦:(g,k) ∈𝒲  y_gk   ≥β_g         ∀ g ∈𝒢
          ∑_g ∈𝒢_fy_gk   ≤⌊1/α⌋        ∀ k ∈𝒦, f ∈ F
           y_gk   ∈{0,1}        ∀ g ∈𝒢,k ∈𝒦

where  y_g,k is a binary variable indicating whether group g will be α-represented in cluster k.
The objective (<ref>) is a proxy for the cost of pre-fixing. Constraint (<ref>) ensures enough clusters are allocated to each group to meet the MR-fairness constraint. Finally constraint (<ref>) ensures no cluster is assigned more groups corresponding to the same feature than can simultaneously have α-representation.



Note that the size of this formulation does not depend on the size of the dataset and it has only |𝒦| × |𝒢| variables. As mentioned earlier, when α > 0.5 and the groups are disjoint (i.e., no group can be in multiple groups) then this pre-fixing scheme simply removes symmetry. In other cases, this operation is a heuristic that leads to substantial speedups to the overall solution time. We now show that the constraint matrix for the pre-fixing problem (<ref>)-(<ref>) is totally unimodular, and thus can be solved in polynomial time.

 
The constraint matrix for the pre-fixing problem is totally unimodular.

Proof of Theorem <ref>
Note that every variable y_gk only appear in exactly two constraints - one constraint <ref> for g and one constraint <ref> for k. Thus it suffices to show that there exists an equitable row bi-coloring for the full constraint matrix <cit.>. Set all constraints <ref> to one color, and all constraints <ref> to another color. Note that this is an equitable bi-coloring as the difference in row sums between the two colors will all be 0, completing the proof.




 §.§ Solving via Network Flow Rounding
 
In this section, we introduce a polynomial time algorithm to solve the second-stage problem while approximately meeting the fairness constraints. The key intuition behind our approach is that we take the fractional assignment of data points coming from the first stage problem (or from solving the linear relaxation of the second stage problem) and round it to an integer assignment using a min-cost network flow model. Recall that in the problem, clusters have already been assigned groups that must be α-represented in them (i.e., the y_gk variables are fixed). 

Given a fractional solution z^LP, we construct a graph G=(V,E) as follows. V consists of three sets of vertices V_x, V_HK, V_K which we define below. For every data point x^i ∈ X we construct a vertex v_i ∈ V_X with a supply of 1. For every cluster k we create a set of vertices V_HK that partition the dataset (i.e., every data point can be mapped to exactly one vertex) and allow us to track how many data points of each group with y_gk=1 are assigned to cluster k. Let G_k be the set of groups g such that y_gk=1. We create one vertex for every possible combination of attributes in the dataset such that the attribute corresponds to a group g ∈ G_k plus one `remainder' vertex that corresponds to any other data point. For instance, consider a dataset with two sensitive features : Gender (Male, Female, Non-binary) and Age (Youth, Adult, Senior), and a cluster k that was pre-fixed to have the Female, Youth, and Adult groups α-represented. A set of combinations for the cluster are (Female, Youth), (Female, Adult), (Female, NOT {Youth or Adult}), (NOT Female, Youth), (NOT Female, Adult), and (NOT Female, NOT {Youth or Adult}). Let H_k be the set of such combinations for a cluster k. For each combination of groups c ∈ H_k we create create one node v_ck∈ V_HK with demand d_ck = ⌊∑_x^i ∈⋂_g ∈ c X_g z_ik^LP⌋. We create an edge with capacity one between data point x^i and every node v_ck if x^i ∈∩_g ∈ c X_g. The cost for these edges is equal to the clustering cost of assigning x^i to the fixed center c_k (i.e., D(x^i, c_k)). The costs of all other edges in this graph are 0.





For every cluster k we also create a node v_k ∈ V_K with demand d_k = ⌊∑_x^i ∈ X z_ik^LP⌋ - ∑_c ∈ H_k d_ck. We create an edge with capacity one between every node v_k and every node v_ck corresponding to the same cluster. Finally, we add a sink note v_t with demand d= | X| - ∑_k (d_k + ∑_c ∈ H_k d_ck) to capture any residual supply. For every node v_k ∈ V_k with fractional weight assigned to it in the LP solution (i.e., ∑_x^i ∈ Xz^LP_ik∉ℤ) we create an edge with capacity one between it and the node v_t. Figure <ref> shows a sample network flow formulation. Note that this min-cost flow problem can be solved in polynomial time via standard min-cost flow algorithms <cit.>. We denote the minimum cost flow problem associated with this graph the Flow- problem. We now show that by solving the Flow- problem we can generate a good assignment of data points to clusters:

 

Solving the Flow- problem yields a binary assignment of data points to clusters that respects the cardinality constraints and has a cost that does not exceed the cost of the LP relaxation of the  problem.



Proof Recall z^LP is the optimal fractional assignment of the  problem (found by solving the LP relaxation or as the output of the  problem). We now construct an integer solution z̅ via solving the Flow- problem. Note that since all capacities and demands in the Flow- problem are integer, the optimal solution to the FMRA-problem is an integer flow. We can interpret this flow as a binary assignment of data points to clusters by setting z̅_ik = 1 if there is a unit of flow between vertex v_i ∈ V_ X and any vertex v ∈ V_Hk, and 0 otherwise. By construction of the Flow- problem and the integrality of the optimal flow, we know every data point will be assigned to exactly one cluster. Since the LP solution is feasible for the network flow problem, we know that the cost of the solution z̅ is lower or equal to the cost of the LP solution.

Note that at least ⌊∑_x^i ∈ X z_ik⌋ and at most ⌈∑_x^i ∈ X z_ik⌉ data points are assigned to cluster k. This follows from the fact that a total of d_k + ∑_c ∈ H_k d_ck = ⌊∑_x^i ∈ X z_ik⌋ demand is consumed in nodes corresponding to cluster k and the edge capacity of the edge of 1 between v_k and v_t ensures at most one additional point is allotted to cluster k. We now claim that the solution to the FMRA-flow problem satisfies the cardinality constraints. Suppose it did not, then ⌊∑_x^i ∈ X z_ik⌋ < l or ⌈∑_x^i ∈ X z_ik⌉ > u. This implies that ∑_x^i ∈ X z_ik < l or ∑_x^i ∈ X z_ik > u, which would violate constraints (<ref>) and contradicts z^LP being a solution to the LP relaxation of the FMRA problem. 


It remains to show the impact of this rounding scheme on the fairness of the final solution. Specifically, we look at the impact of this network flow rounding procedure on the satisfaction of the α-representation fairness constraints (i.e., constraints (<ref>) for group g and cluster k where y_gk=1). Recall the following definition for an additive constraint violation:






For a given constraint g(x) ≤ 0, a solution x̅ is said to have an additive constraint violation of δ for δ≥ 0 such that
g(x̅) ≤δ.


We now show that the assignment produced by the Flow- problem has a small additive violation of the MR-fairness constraints. 

 
Let γ = min(⌈α^-1⌉, max_f ∈ F| G_f|). The binary assignment from the Flow- problem has at most an additive fairness violation of:

    γ^| F| - 1 + α𝕀(γ > 2)



Proof 
Let δ≥ 0 be the additive fairness violation of the constraint for group g in cluster k by binary assignment z̅. We can re-write this violation as:

    δ = α∑_x^i ∈ Xz̅_ik - ∑_x^i ∈ X_gz̅_ik  =α∑_x^i ∉ X_gz̅_ik  - (1-α)∑_x^i ∈ X_gz̅_ik

The worst-case scenario when rounding the LP solution, with respect to the fairness constraint, is to round down the number of data points in g assigned to the cluster and to round up the number of data points outside g assigned to the cluster. Let f_g, f_g'≥ 0 be the difference between the fractional and integer assignment for the group g and data points outside g respectively:

    f_g = ∑_x^i ∈ X_g z_ik^LP - ∑_x^i ∈ X_gz̅_ik    
        f_g' = ∑_x^i ∉ X_gz̅_ik  - ∑_x^i ∉ X_g z_ik^LP


Rewriting the fairness constraint we get:
    δ    = α∑_x^i ∉ X_g z_ik^LP + α f_g' -
    (1-α)∑_x^i ∈ X_g z_ik^LP - (1-α)f_g  
       = (1-α)f_g + α f_g' + ( α∑_x^i ∉ X_g z_ik^LP -  (1- α)∑_x^i ∈ X_g z_ik^LP) 
       ≤ (1-α)f_g + α f_g'

with the final inequality coming from the feasibility of the LP solution for the fairness constraint. Let F_k be the set of sensitive features f with at least one group g ∈ G_f α-represented in cluster k, and let η_fk = max(1+∑_g ∈ G_f y_gk, | G_f|). Note that there are a total of ∏_f ∈ F_kη_fk vertices for each cluster k. Let V_gk⊂ V_HK be the set of nodes v_ck such that g ∈ c, and note |V_gk| = ∏_f ∈ F_k: 
 g ∉ G_fη_fk. Note that the V_gk sets do not for a partition of V_HK as a node v_ck can correspond to multiple groups. Similarly let V_g'k be the set of nodes v_ck such that g ∉ c. Note that V_gk≤ V_g'k, with the comparison being strict only when | G_f| > 2. By construction we know that for every node v_ck∈ V_gk at least d_ck = ⌊∑_x^i ∈∩_g ∈ c X_g z_ik^LP⌋ units of flow are routed to it. Thus f_g ≤∑_v_ck∈ V_gk∑_x^i ∈∩_g ∈ c X_g z_ik^LP - d_ck≤ |V_gk|. By a similar argument we also have f_g'≤ |V_g'k|. By construction the total number of data points assigned to cluster k is at most ⌈∑_x^i ∈ X z_ik^LP⌉, which means f_g' - f_g≤ 1. Therefore the worst-case fairness violation from rounding can be seen as the following optimization problem:

    max_f_g, f_g'≥ 0 (1-α)f_g + α f_g'  s.t.     f_g' - f_g≤ 1,    f_g'≤ |V_g'k|,   f_g≤ |V_gk|

Recall that V_gk≤ V_g'k and thus by inspection, the optimal solution is (1-α)|V_gk| + αmin(1+|V_gk|, |V_g'k|). Note that |V_g'k| > |V_gk| only if max_f ∈ F | G_f| > 2 AND ⌈α^-1⌉ > 2 (i.e., there can be ≥ 3 nodes corresponding to the same sensitive feature). This condition is equivalent to saying γ > 2. Finally, we complete the proof by bounding |V_gk|. Recall that by construction: 
    |V_gk|  = ∏_f ∈ F_k: g ∉ G_fη_fk ≤∏_f ∈ F_k: g ∉ G_fγ ≤ γ^| F|-1












We now show that this result generalizes the earlier result of <cit.> and gives an additive fairness violation of 1 in the special case of two disjoint groups.

 
    In the special case when | G| = 2 and | F|= 1, the FMRA-flow problem guarantees of an additive fairness violation of at most 1.


Proof of Corollary <ref>
Follows from the fact that in the two group case | F| = 1 and γ = 2.

One limitation of Theorem <ref> is the the worst-case fairness violation scales exponentially in the number of sensitive features | F|. In the following result, we show that the fairness violation is also upper bounded by K and the number of α-representation constraints and thus scales linearly with | F|:


The binary assignment from the Flow- problem has at most an additive fairness violation of:

    K + ∑_g ∈ Gβ_g  
    ≤ K + K γ | F|
	


Proof We prove this result via a counting argument based on the linear relaxation of the  problem. Start by solving this linear relaxation to generate z^LP. Take all z_ik variables with values in {0,1} and fix them, then re-solve the LP. We now have a LP where all basic z_ik variables are fractional. We now bound the number of data points with fractional variables, denoted X̂. Let n_frac be the number of fractional basic z_ik variables. Note that for every data point x^i ∈ X there must be at least two basic fractional variables z_ik associated with it, implying 2 |X̂| ≤ n_frac. 

Also note that the LP has at most the following tight constraints:


  * |X̂| constraints corresponding to constraint (<ref>).

  * ∑_g ∈ Gβ_g ≤ K γ | F| constraints of type (<ref>) corresponding to the pre-fixed α-representation constraints.

  * K active upper or lower bound constraints of type (<ref>).

In total there are at most K + K γ_MAX + X̂ tight constraints, implying n_frac≤  K + K γ_MAX + X̂.
Combining both the upper and lower bound for n_frac and re-arranging terms we get that X̂≤ K + ∑_g ∈ Gβ_g. The worst-case fairness violation is upper-bounded by the number of fractional variables, completing the result. 

		


§ NUMERICAL RESULTS
 






To benchmark our approach, we evaluate it on three datasets that have been used in recent work in fair clustering: adult (n=48842, m=14) <cit.>, default (n=30000, m=24) <cit.>, and Brunswick County voting data (n=49190, m=2) <cit.> where n denotes the number of data points and m denotes the initial number of features. We pre-process the Brunswick County voting data by geocoding the raw addresses to latitude and longitude using the US census bureau geocoding tool and retain all data with a successful geocoding that belong to white and Black voters. For each dataset we use one sensitive feature to represent group membership - namely gender for both adult (67% Male, 33% Female) and default (60% Male, 40% Female), and race for voting (92% white, 8% Black). We also report results for the Adult dataset with two sensitive features (Adult-2F) where the second sensitive feature is marital status (47% married, 33% never married, 20% divorced or widowed). For all datasets we normalize all real-valued features to be between [0,1] and convert all categorical features to be real-valued via the one-hot encoding scheme. For datasets that were originally used for supervised learning, we remove the target variable and do not use the sensitive attribute as a feature for the clustering itself. The k-medians algorithms require computing a distance matrix between all pairs of points leading to a large memory requirement (O(n^2)). To circumvent memory issues for large datasets, we sub-sample all datasets to have 10,000 data points. We use the same random sub-sample for all algorithms to provide a fair comparison. 

We implemented MiniReL in Python with Gurobi 10.0 <cit.> for solving all IPs. We warm-start MiniReL with the output from the baseline version of Lloyd's algorithm (details and evaluation of this warm-starting is included in Appendix <ref>). All experiments were run on a computing environment with 16 GB of RAM and 2.7 GHz Quad-Core Intel Core i7 processor. For the following experiments we set α = 0.51 to represent majority representation in a cluster. We experiment with different settings of α in Appendix <ref>. We also set  ℓ = 1, u = n to provide a fair comparison to Lloyd's algorithm with no cardinality constraints. We provide some additional experiments with balanced clusters (i.e., l ≈n/k) in Appendix <ref>. 

We benchmark MiniReL against Lloyd's algorithm for k-means and its associated alternating minimization algorithm for k-medians <cit.>. For the k-means setting we use the implementation available in scikit-learn <cit.> with a k-means++ initialization. For the k-medians setting we compare MiniReL against the alternating minimization approach for k-medians using the implementation available in scikit-learn extra package <cit.> with a k-mediods++ initialization. We use euclidean distance to compute distances between points. For both settings, we run the algorithm with 100 different random seeds. We report the clustering with the lowest clustering cost, which we denote k-means/k-medians respectively, and the fairest clustering with respect clustering statistical parity (k-means-SP/k-medians-SP) and cluster equality of opportunity( k-means-EqOp/ k-medians-EqOp).





 §.§ Comparing different variants of the MiniReL 
 


We evaluate the following 5 different variants of the MiniReL algorithm to show the impact of different algorithmic components on its performance:

    
  * MiniReL: The baseline algorithm that solves the full FMRA at each iteration.
    
  * MiniReL-TwoStage: Decomposes the FMRA by sequentially solving the , by relaxing the z variables and solving the problem via IP, and , using IP.
    
  * MiniReL-TwoStageFlow: Uses the two-stage decomposition and solves the second stage using the network flow approach introduced in section <ref>.
    
  * MiniReL-PrefixFlow: Uses the two-stage decomposition with pre-fixing (i.e., solves the via IP once) and solves the second stage using the network flow approach introduced in section <ref>.
    
  * MiniReL-PrefixHeurFlow: Uses the two-stage decomposition with pre-fixing with the polynomial time heuristic introduced in section <ref> and solves the second stage using the network flow approach introduced in section.



For the sake of brevity we report results for this ablation study in the k-means setting, but the results were similar in the k-medians setting. Figure <ref> shows the performance of these five different variants with respect to cluster quality, computation time, and average time to solve the assignment stage of the algorithm. All the amounts presented are normalized to show the percent change with respect to the base MiniReL algorithm, and averaged over k ∈ [2,14]. Negative values indicate an improvement over the baseline algorithm. Overall, the results show that the two-stage decomposition (MiniReL-TwoStage) approach leads to a decrease in computation time over the baseline algorithm leading to as much as a 20% percentage reduction in computation time on the Adult data set with two sensitive features. Solving the second stage problem via network flow (MiniReL-TwoStageFlow) also gives a small additional reduction in computation time over the the two-stage decomposition alone. Both approaches have no large impact on the objective (i.e., clustering cost) of the final solutions). Adding pre-fixing (Minirel-PrefixFlow) while still solving the problem via IP yields an additional reduction in computation time in most of the datasets - the exception being the Default that had on average only 1.2 iterations that needed to use IP. Solving the problem via the polynomial time heuristic led to a large additional reduction in computation time (an additional 30% in the adult dataset) but comes with a slight reduction to the quality of the clusters found. In most datasets this increase in cluster cost is small (under 1% on average) but in the voting dataset this led to a 7% point increase. 








 §.§ k-means results
 




We compare the full version of MiniReL with heuristic pre-fixing and network flow assignment in the k-means setting with the standard Lloyd's algorithm for k-means. We evaluate both algorithms with respect to cluster statistical parity (i.e., every group must be α-represented in the same number of clusters), and cluster equality of opportunity (i.e., every every group must be α-represented in a number of clusters proportional to the size of the group).  






Figure <ref> (top 2 rows) shows the maximum deviation  from the fairness parameters β_g (i.e., max_g max(β_g - Λ (C, X_g, α), 0)) for the k-means algorithms and the variants of MiniReL that use IP to strictly enforce fairness.  Figure <ref> (bottom 2 rows) shows the total additive fairness violation normalized by the size of the dataset for the k-means algorithms and the variant of MiniReL that uses network flow to approximately enforce fairness. 
Across all three datasets we can see that k-means can lead to outcomes that violate MR-fairness constraints significantly, and that selecting the fairest clustering has only marginal improvement. This is most stark in the default dataset where there is as much as an 11 cluster gap (6 cluster fairness violation) between the two groups despite having similar proportions in the dataset. In contrast, the MiniReL algorithm is able to generate fair clusters under both notions of fairness and for all three datasets. This result also applies in the additive fairness violation setting, where the k-means algorithms generate large constraint violations (as much as 20% of the dataset size for the voting dataset) whereas the MiniReL algorithms with flow assignment have normalized additive fairness violations close to 0%. 

Table <ref> shows the average computation time in seconds for Lloyd's algorithm and MiniReL-PrefixHeurFlow under cluster statistical parity. We display results for the cluster statistical parity as it was the more computationally demanding setting requiring more MiniReL iterations than cluster equality of opportunity. As expected, the harder assignment problem in MiniReL leads to higher overall computation times when compared to the standard Lloyd's algorithm. However, MiniReL is still able to solve large problems in under 200 seconds demonstrating that the approach is of practical use. 





 One remaining question is whether fairness comes at the expense of the cost of the clustering. Figure <ref> shows the k-means clustering cost for Lloyd's algorithm and MiniReL under both definitions of fairness. Although there is a small increase in the cost when using MiniReL the overall cost closely matches that of the standard k-means algorithm in 5 out of 6 instances, with the sole exception being the voting dataset under statistical parity, showing that we can gain fairness at practically no additional increase to clustering cost. 

    





 §.§ k-medians results
 


In this section we benchmark MiniReL against the Lloyd-style k-medians algorithm <cit.>. The results closely parallel those in the k-means section and thus in the interest of brevity we present a subset of results for the algorithm under statistical parity and include the extended results in Appendix <ref>. Figure <ref> shows the maximum fairness violation and normalized additive fairness violation for MiniReL and the baseline k-medians algorithm. Similar to the k-means setting, the k-medians algorithm without fairness constraints can lead to unfair outcomes across all datasets, whereas MiniReL constructs fair clusters by design. Figure <ref> shows the cluster cost for both algorithms in the same setting. Adding fairness in these settings again leads to only moderate increase in cluster cost, with the only notable increase coming on the voting dataset under statistical parity. Table <ref> shows the runtime of both algorithms under statistical parity. MiniReL still leads to a modest increase in runtime compared to the baseline algorithm but is able to solve all datasets (10,000 data points after sub-sampling) in under 60 seconds in most instances.











		


§ CONCLUSION


In this this paper we introduce a novel definition of group fairness for clustering that requires each group to have a minimum level of representation in a specified number of clusters. This definition is a natural fit for a number of real world examples, such as voting and entertainment segmentation. To create fair clusters we introduce a modified version of Lloyd's algorithm called MiniReL that solves an assignment problem in each iteration via integer programming. While solving the integer program remains a computational bottleneck, we note that our approach is able to solve problems of practical interest, including datasets with tens of thousands of data points, and provides a mechanism to design fair clusters when Lloyd's algorithm fails. 



		

    
apalike
    
    
    

§ PROOF OF THEOREM <REF>
 


Proof
The reduction is from the exact cover by 3 sets  (X3C) problem, 
with 3q elements U = {u_1, …, u_3q} and t = q + r subsets W = {W_1, …, W_t} where each subset W_i ⊆ U and |W_i| = 3. 
Recall that X3C is one of Karps 21 NP-Complete problems and its goal  is to select a collection of subsets W^* ⊆ W such that all elements of U are covered exactly once.

Given an instance of the X3C problem, we first construct an undirected bipartite graph G = (∪, E) which we then convert into a FMRA instance following a similar construction as <cit.>. 
Graph G has a node for each u_i∈ and a node w_j for each  W_j∈. There is an edge {u_i,w_j} between nodes
u_i and w_j provided that u_i ∈ W_j. Note that with slight abuse of notation, we use  both for the subsets in the X3C instance and the nodes corresponding to them in the graph G.


Using graph G, we construct an instance of the FMRA problem with two groups by interpreting each vertex in the graph as a data point where points corresponding to vertices in U and W belong to separate groups.
We set  K = t (i.e., one cluster for each subset), α = 0.75,  β_W = t - q  and β_U = q (minimum number of α-represented clusters for each group). 
We place the (fixed) K centers at the data points associated with W. 
The distances between pairs of data points are set to be the length of the shortest path distances between the corresponding vertices in the graph.

We now argue that the optimal solution to the FMRA instance has a cost of 3q if and only if there exists a feasible solution to the X3C instance. 
First note that any feasible solution  to the FMRA instance has a cost of at least 3q as each point u_i∈ incurs a cost of at least 1 and there are 3q such points. Next, note that given a feasible solution ^*⊆  to the X3C instance, we can construct a solution to the corresponding FMRA instance with cost 3q by creating one cluster for each W_j∈^* in the solution.
These q clusters contain w_j together with the 3 elements u_i∈ W_j. The remaining t-q clusters contain a single point w_j, one for for each W_j∈∖^*. Note that these clusters satisfy the fairness constraints. Furthermore, letting the  center of each cluster to be the w_j that it contains gives a cost of 3q.

Finally we argue that if the FMRA instance has a cost of 3q, then the X3C instance is feasible. If the solution to the FMRA has cost 3q, then (i) each point u_i∈ must be assigned to a center w_j∈ such that u_i∈ W_j, and, (ii) each point w_j∈ must be assigned to the center w_j and consequently, each cluster must contain exactly one w_j∈.
In addition, the fairness constraint for the  group requires that at least t-q clusters must have 75% of its points belonging to the  group. As there is exactly one w_j∈ in each cluster, this can only happen if at least t-q clusters have no points from  group in them.
Consequently all 3q points form the  group are assigned to at most q clusters. As all u_i∈ must be assigned to a center w_j∈ such that u_i∈ W_j, and |W_j|=3, the solution to the FMRA instance must have exactly t-q clusters with no points from  group and q clusters with one w_j and three u_i∈ W_j, which gives a feasible solution to the X3C instance. 

§ PROOF OF THEOREM <REF>
 
Proof.
We start by noting that given an assignment of data points to clusters, the optimal cluster centers for this assignment are precisely the ones computed as in Step <ref> (<ref>).
Consequently, if improved_cost = current_cost in Step <ref>, then the cluster centers used in Step <ref> and the ones computed in Step <ref> or <ref> (in the last iteration) must be identical. This follows from the uniqueness of the optimal centers in the k-means setting and the deterministic tie-breaking in the k-medians setting. Therefore, if Algorithm 1 terminates, then the current assignment of the data points to the current cluster centers is optimal and the cost cannot improve by changing their assignment due to Step <ref>.
In addition, Steps <ref> and <ref> guarantees that perturbing cluster centers cannot not improve the cost for the current assignment.


It remains to show that the algorithm will terminate after a finite number of iterations. 
Similar to the proof for Lloyd's algorithm, we leverage the fact that there are only a finite number of partitions of the data points. By construction, the objective value decreases in each iteration of the algorithm, and thus can never cycle through any partition multiple times as for a given partition we use the optimal cluster centers when computing improved_cost in Step <ref>. Thus the algorithm can visit each partition at most once and thus must terminate in finite time.




§ PROOF OF THEOREM <REF>



Proof Given an instance of a 3-SAT problem, one of Karp's 21 NP-Complete problems, we construct an instance of the  problem as follows. We start with a 3-SAT problem with n variables and m clauses K_1, …, K_m. Each clause K_i takes the form v_i1∨ v_i2∨ v_i3 where v_ij is either one of the original variables or its negation. 

To construct the instance of the  problem, start by creating two new data points x_v_i, x_v̅_i, corresponding to each original variable v_i and its negation respectively. We construct two clusters C_1 and C_2 that each variable can be assigned to. Let W represent the set of allowable group-cluster assignments (i.e., (g, k) ∈ W if y_gk = 1). For each original variable v_i we create one group g_i = {x_v_i, x_v̅_i} that can be α-represented in either cluster (i.e. (g_i, 1), (g_i,2) ∈𝒲). For each group g_i we set β_g_i = 2 - ensuring that both clusters must be α-represented by the group. We also create one group for each clause K_i corresponding to its three conditions g_K_i = {x_v_i1, x_v_i2, x_v_i3} that must be α-represented in cluster 1 (i.e. (g_K_i,1) ∈𝒲, (g_K_i,2) ∉𝒲). For these groups we set β_K_i = 1. Finally, we set α = 1/2n - this ensures that any assignment of a group's data point to a cluster will satisfy the α-representation constraint (as there are 2n data points and thus at most 2n data points in a cluster). We also add a cardinality lower bound on both clusters of 1. Clearly the above scheme can be set-up in polynomial time.

We now claim that a feasible solution to the aforementioned  problem corresponds to a solution to the original 3-SAT instance. We start by taking the variable settings by looking at C_1. We start by claiming that for each variable exactly one of x_v_i, x_v̅_i are included in C_1. Suppose this weren't true, either both variables were included in C_1 or C_2. However, whichever cluster has neither of the variables would not be α-represented by group g_i, thereby contradicting the fairness constraints. Since C_1 contains either x_v_i or x_v̅_i we set v_i = T if x_v_i is included and v_i = F otherwise. We now claim that such a setting of the variables satisfies all the clauses. Assume it did not, then there exists a clause K_i such that none of x_v_i1, x_v_i2, x_v_i3 are included in C_1. However, this violates the α-representation constraint for g_K_i providing a contradiction to the feasibility of the fair assignment problem. Note that since the feasibility problem does not consider the objective or the location of the centers the proof applies for both the k-means and k-medians setting. 

§ EXPERIMENTS WITH DIFFERENT OBJECTIVES FOR  HEURISTIC
 


To test the efficacy of the myopic cost for pre-fixing we perform a computational study. We experiment with three different choices of cost function:

    
  * Proportion: Set the cost to the proportion of the cluster that needs to be changed for g to be α-represented in cluster k: 
    c_gk = max(α - p_gk,0)
 where p_gk is the current proportion of cluster k that belongs to group g.
    
  * Weighted Proportion: Set the cost to the proportion weighted by the size of the cluster: 
    c_gk = |C_k|max(α - p_gk,0).

    
  * Local Cost: The myopic (i.e. one-shot) increase in cost of moving additional data points to cluster k to meet the fairness constraints. Let q be the additional number of points from group g needed for g to be α-represented in this cluster (i.e. q + p_gk|C_k| ≥α(q + |C_k|)). Let c_(x) = _ c ∈{c_1, …, c_K}{D(x, c)} be the closest center for x ∈ X. The myopic cost c_gk associated with α-representing group g in cluster k then becomes: 
    
    c_gk = min_X ⊂ X_g ∖ C_K: |X| = q∑_x ∈ X(D(x,c_k) - D(x, c_(x)))



Figure <ref> shows the impact of different choices of the objective in IP model (8)-(11) on run-time for MiniReL on three different datasets. For these experiments we focused on the k-means setting (though k-medians showed a similar result) and ran 10 trials with different random initial seeds, and warm-start the algorithm with the standard Lloyd's algorithm. We benchmark using the IP model to perform pre-fixing with naively pre-fixing the group cluster assignments (i.e. random assignment). In the small 150 data point iris dataset, the pre-fixing scheme has little impact on the total run-time of the algorithm as the overhead of running the IP model outweighs any time savings from a reduced number of iterations. However, for larger datasets (i.e. adult and default which both have over 30K data points), using the IP model to perform pre-fixing outperforms the naive approach - leading to as large as a 3x speed-up. However, there is a relatively small difference in performance between the three choices for the objective, with the local cost objective reducing the speed by approximately 0.1% compared to the other two when averaged across all three datasets. 



Figure <ref> shows the impact of pre-fixing strategy on the number of iterations needed for MiniReL to converge. For iris, pre-fixing has practically no impact on on the number of iterations, however for larger datasets like adult and default using the pre-fix IP model with any objective leads to substantially fewer iterations. The same holds for cluster cost as shown in Figure <ref> where the IP model leads to solutions with slightly better clustering cost in both adult and default. Both results show that the choice of objective function has relatively little impact on the performance of pre-fixing, but outperform random assignment. 




		


§ WARM-STARTING MINIREL
 

To reduce the number of iterations needed to converge in MiniReL, we warm-start the initial cluster centers with the final centers of the unfair variants of Lloyd's algorithm. The key intuition behind this approach is that it allows us to leverage the polynomial time assignment problem for the majority of iterations, and only requires solving the fair assignment problem to adjust the locally optimal unfair solution to a fair one. To incorporate warm-starting into MiniReL, we replace step 1 in Algorithm (<ref>) with centers generated from running Lloyd's algorithm. For the sake of brevity, we report results in the k-means setting. We benchmark this approach against two baselines: (i) randomly sampling the center points, and (ii) using the k-means++ initialization scheme without running Lloyd's algorithm afterwards. We also compare using the k-means warm-start with 1 initialization and 100 initializations. Figure <ref> shows the impact of these initialization schemes on the total computation time including time to perform the initialization. Each initialization scheme was tested on three datasets. For each dataset we  randomly sub-sample 2000 data points (if n > 2000), and re-run MiniReL with 10 random seeds. The results show that using Lloyd's algorithm to warm-start MiniReL can lead to a large reduction in computation time, even taking into account the cost of running the initialization. However, there are diminishing returns. Namely running 100 different initialization for k-means and selecting the best leads to slightly larger overall run-times. 

		


§ EXPERIMENTS WITH DIFFERENT VALUES OF Α
 

In this section we explore the impact of α on the fairness and runtime of the different algorithms. For these experiments we replicate the experimental set-up of Section <ref> but vary α. For brevity we focus on the k-means setting, but k-medians showed similar results. Figures <ref> and <ref> show the normalized fairness violation (the number of α-represented clusters away from meeting the required amount β_g normalized by K) and normalized additive fairness violation (the number of data points away from meeting the fairness constraints normalized by n). In both cases, lower value of α lead to much laxer fairness requirements that are easier to meet. Both the standard k-means and the heuristic fair k-means algorithms are able to generate fair clusters for α≤ 0.3 for both statistical parity and equality of opportunity settings of β_g. However for larger values of α both struggle to generate fair clusters having normalized (additive) violations close to 100% (25%). In constrast, by design MiniReL with IP-based assignment (MiniRel-Prefix) is able to generate fair clusters at all levels of α. While the version of MiniReL with network flow rounding (MiniReL-PrefixFlow) can lead to fairness violations, the size of the violations are consistently small (in line with our theoretical results) - violating the constraints by close to 0% of the size of the dataset. Figure <ref> shows the impact of α and K on the computation time of all algorithms. As expected, both k-means and fair k-means run very quickly regardless of K (and α evidently has no impact on the runtime). In contrast, the runtime of MiniReL increases with both K and α showing that harder assignment problems lead to larger runtimes overall.






		


§ EXPERIMENTS WITH BALANCED CLUSTERS
 

In this section we explore the impact of constructing balanced clusters (i.e., clusters with approximately equal size) on the objective and computation time of MiniReL. For these experiments we require each cluster to have at least 80% of the balanced allocation of data points to clusters (i.e., ℓ = 0.8*n/K. Figure <ref> shows the k-means clustering cost of both Lloyd's algorithm (with no cardinality constraints) and the cost of MiniReL with balanced clusters. The first thing to note is that under balanced clusters, not every dataset and setting for α, β remains feasible. For the voting dataset under statistical parity, MiniReL certifies that no fair clustering exists (and thus has no associated objective or runtime). Overall, requiring balance leads to a modest increase in cluster cost across all instances - exceeding the deviation that occurs from enforcing fairness alone. Table <ref> shows the average runtime over 10 random seeds for K-Means and MiniReL-HeurFlow under balanced clusters for statistical parity. Adding the requirement that clusters are balanced leads to a small increase in runtime for MiniReL on all datasets. The one exception is the voting dataset, which is an infeasible problem, where MiniReL can certify infeasibility in under 30 seconds for all settings of K.














		


§ FULL K-MEDIANS RESULTS
 
The following section includes the extended empirical results for MiniReL in the k-medians section. Figure <ref> shows both the maximum fairness violation and normalized additive fairness violation of both algorithms under both notions of fairness. Regardless of the setting, the baseline k-medians algorithm and its fair heuristic analog are unable to generate fair clusters - whereas MiniReL can construct fair clusters or clusters with negligible additive fairness violations by design. Figure <ref> shows the clustering objective of both sets of algorithms. With the exception of the voting dataset under statistical parity, MiniReL is able to generate fair clusters with practically no increase in the cluster cost - showing that in practical settings achieving minimum representation fairness comes at little cost over Lloyd's algorithm.



		


	



