Fair Clustering via Alignment
Authors: Kunwoong Kim
Jihu Lee
Sangchul Park
Yongdai Kim
Venue: ICML 2025 poster (2025)
Keywords: Clustering
Fairness
Trustworthy AI
Primary area: social_aspects->fairness
TL;DR: This paper proposes a new algorithm for fair clustering based on a novel decomposition of the fair clustering objective, achieving an approximately optimal trade-off between fairness level and clustering utility for any given fairness level.

Abstract: Algorithmic fairness in clustering aims to balance the proportions of instances assigned to each cluster with respect to a given sensitive attribute.
While recently developed fair clustering algorithms optimize clustering objectives under specific fairness constraints, their inherent complexity or approximation often results in suboptimal clustering utility or numerical instability in practice.
To resolve these limitations, we propose a new fair clustering algorithm based on a novel decomposition of the fair $K$-means clustering objective function.
The proposed algorithm, called Fair Clustering via Alignment (FCA), operates by alternately (i) finding a joint probability distribution to align the data from different protected groups, and (ii) optimizing cluster centers in the aligned space.
A key advantage of FCA is that it theoretically guarantees approximately optimal clustering utility for any given fairness level without complex constraints, thereby enabling high-utility fair clustering in practice.
Experiments show that FCA outperforms existing methods by (i) attaining a superior trade-off between fairness level and clustering utility, and (ii) achieving near-perfect fairness without numerical instability.

Fair Clustering via Alignment
Kunwoong Kim
Jihu Lee"
Sangchul Park Yongdai Kim
Abstract
Ingold & Soper, 2016; Damodaran al., 2018; Mehrabi et al., 2019). Moreover, non-discrimination laws are also increasingly emphasizing the importance of fair decision making based on Al systems (Hellman, 2019). Specifically, group fairness is a category within algorithmic fairness that ensures models do not discriminate against certain protected groups, which are defined by specific sensitive attributes race). In response, large amount of research has been conducted to develop algorithms for mitigating such biases in various supervised learning tasks such as classification (Zafar et al., 2017: Donini et al., 2018; Agarwal et al.. 2018; Quadrianto et al., 2019; Jiang et al., 2020) and regression (Agarwal et al., 2019; Chzhen et al., 2020).
Algorithmic fairness in clustering aims bal- ance the proportions of instances assigned to each cluster with respect to given sensitive at- tribute. While recently developed fair clustering algorithms optimize clustering objectives under specific fairness constraints, their inherent com- plexity or approximation often results subopti- mal clustering utility or numerical instability in practice. To resolve these limitations, we propose new fair clustering algorithm based on novel decomposition of the fair K-means clustering ob- jective function. The proposed algorithm, called Fair Clustering via Alignment (FCA), operates by alternately (i) finding a joint probability distri- bution to align the data from different protected groups, and (ii) optimizing cluster centers in the aligned space. A key advantage of FCA is that it theoretically guarantees approximately optimal clustering utility for any given faimess level with- out complex constraints, thereby enabling high- utility fair clustering in practice. Experiments show that FCA outperforms existing methods by (i) attaining superior trade-off between fairness level and clustering utilityy, and (ii) achieving near- perfect fairness without numerical instability.
Along with supervised learning, algorithmic fairness for unsupervised learning tasks, such as clustering, has also gathered significant interest. Clustering algorithms have long been employed as fundamental unsupervised learning methods for machine learning, such as recommendation systems (Widiyaningtyas et al., 2021), image processing (Le, 2013; Guo et al., 2020; Mittal et al., 2022), and language modeling (Butnaru & lonescu, 2017; Zhang et al., 2023).
Related works for Fair Clustering (FC) Combining al- gorithmic fairness and clustering, the notion of Fair Clus- tering (FC) was initially introduced in Chierichetti al. (2017). FC operates under the goal that the proportion of each protected group within each cluster should be simi- lar to that in the population. To achieve this goal, various algorithms have been developed to minimize a given cluster- ing objective under pre- specified faimess constraints (Bera et al., 2019; Kleindessner al., 2019; Backurs et al., 2019; Li et al., 2020; Esmaeili et al., 2021; Ziko al., 2021; Zeng et al., 2023), to name few.
1. Introduction
As artificial intelligence (AI) technology has advanced and been successfully applied to diverse domains and tasks, the requirement for Al systems to make fair decisions (i.e., al- gorithmic fairness) has emerged as important societal issue. This requirement is particularly necessary when ob- served data possess historical biases with respect to specific sensitive attributes, leading to unfair outcomes of learned models based on such biased data (Angwin et al., 2016;
We can roughly categorize the existing FC algorithms into three: (i) pre-processing, (ii) in- in-processing, and (iii) post- processing. Pre-processing methods (Chierichetti et al., 2017: Backurs et al., 2019) involve transforming instances into fair space based on the concept of fairlets. Fairlets are small subsets that satisfy (perfect) faimess, and thus performing standard clustering on the fairlet space yields a fair clustering. In- pnocrscssing methods (Kleindessner et al., 2019; Ziko et al., 2021; Li et al., 2020; Zeng et al., 2023) aim to simultancously find both the cluster centers and as- signments of the fair clustering by solving constrained op-
'Department of Statistics, Seoul National University, Re- public of Korea "School of Law, Scoul National University, Republic of Korea. Correspondence to: Yongdai Kim <yd- kim0903 @ @ma.emmmmaaa........
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Fair Clustering via Alignment
timization problems. Post-processing methods (Bera al., 2019; Harb & Lam, 2020) focus on finding fair assignments given fixed cluster centers. The fixed cluster centers are typically predetermined by a standard clustering algorithm.
tected groups, and (ii) the clustering cost with respect cluster centers in the aligned space.
Building on this decomposition, we develop novel FC algorithm called FCA (Fair Clustering via Alignment), which is stable and guarantees convergence.
Theoretically, we prove that FCA achieves an approx- imately optimal trade-off between fairness level and clustering utility, for any given fairness level.
Our contributions In this paper, we focus on the trade-off between faimess level and clustering utility: our goal is to maximize clustering utility while satisfying a given fairness level. While the trade-off between the fairness and utility is inevitable (Bertsimas et al., 2011; Chhabra et al., 2021), achieving the optimal trade-off with existing FC algorithms remains challenging. For example, pre- or post-processe processiig algorithms usually result in suboptimal clustering utility due to indirect maximization of clustering utility (e.g., Backurs et al. (2019); Esmaeili et al. (2021)). Even when designed for achieving reasonable trade-off, in in-precessing algorithms may have trouble due to numerical instability, particularly when a given fairness level is high (c.g., Ziko et al. (2021)).
Experimentally, show that FCA (i) outperforms existing baseline FC algorithms in terms of the trade- off and numerical stability, and (ii) effectively controls the trade-off across various fairesss levels.
2. Preliminaries
Notations Let D - (xx,,))) s;)
be a given dataset (i.e.. set of observed instances), where X, R and s; {0, 1} are ddddimensional data and binary variable for the sensitive attribute, respectively. We denote (X, S) as the random vector whose joint distribution denoted as IP is the empirical distribution on D. Let P. represents the conditional distribu- tion of X given S = s. In this paper, we specifically define these distributions to discuss the (probabilistic) matching between two protected groups of different sizes. We denote E and E,, as the expectation operators of IP and IP,, respec- tively. Let X' = }x, X. = fxx E X ny == [2,] for s E 10. Denote || - -12 as the L2 norm.
This paper aims to address these challenges by developing new in- in-processing algorithm that can practically achieve superior trade-off between fairnsss level and clustering utility without numerical instability. The primary idea of our proposed algorithm is to optimally align data from differ- ent protected groups by transforming them into a common space (called the aligned space), and then applying a stan- dard clustering algorithm in the aligned space. We prove that the optimal fair clustering, i.e., the clustering with min- imal clustering cost under given fairness constraint, is equivalent to the optimal clustering in the aligned space.
= $). and
We assume that the number of clusters, represented by K E N, is given a priori. The K K-many cluster centers are denoted as μ == (,I....,, "ii.....,,,,,, } where 1* Rd, Vk e X x {0, 1] - SK be as-
[K] = (1,.... ..... K). signment function that takes as input (x,s) E X' x (0, 1} and returns the assignment probabilities over clusters for the data point x, where S is the (K - 1)-dimensional simplex. We consider this probabilistic assignment function to ensure the existence of perfectly fair clustering.
Let Let
Based on the theoretical result, we devise a new FC algo- rithm, called Fair Clustering via Alignment (FCA)'. FCA alternately finds the aligned space and the (approximately) optimal clustering in the aligned space until convergence. To find the aligned space, we develop a modified version of algorithm for finding the optimal transport map (Kan- torovich, 2006), while standard clustering algorithm (e.g..
the K-means++ algorithm (Arthur& & Vassilvitskii, 2007))
Clustering objective function We first present the math- ematical formulation of the clustering objective function. The objective of the standard (i.e., fair-unaware) K-means clustering is to minimize the clustering cost C(H, := 1 In= E(x,))ED A(x, s)x M 1l2 with respect to J and A. Note that C(u, A) can be equivalently re-written as E Σx= A(X, 5)x{|( - 1xl Furthermore, the opti- mal assignment function is deterministic, i.e., A(x, s)& = 1 (arg ming ||x - # 2|2 = k) for a given (x, X (0, 13, where pi...., u& are the centers of the opti- mal clustering. Thus, C(u, A) becomes E min& || 12, and the optimal clustering is obtained by finding μ minimiz- ing E ming ||X - 14 1
is applied to find the (approximately) optimal clustering in
the aligned space. It is worth noting that FCA can be partic- ularly compared to the fairlet-based methods (e.g.. Backurs et al. (2019)). While existing fairlet-based methods first find fairlets and then perform clustering sequentially, FCA simultaneously builds the aligned space and performs clus- tering to obtain an approximately optimal fair clustering. A detailed comparison is provided in Remark 3.2.
The main contributions of this paper can be summarized as:
We provide novel decomposition of the fair cluster- ing cost into two components: (i) the transport cost with respect to joint distribution between two pro-
Immleemenation code is available at https: //tp:///gttt///// com/kwkin mon1 FFA.
Definition of fair clustering An assignment function A is said to be fair in view of group (or proportional) fairness
2

---

Fair Clustering via Alignment
(Chierichetti al., 2017), if it satisfies for all & E [K],
3.1. Case of equal sample sizes: no 11
Ex,xxo A(x,, Ex,ex, A(x,: 1) (1)
Assume that the sizes of two protected groups are equal (i.e., no n1). We consider deterministic assignment func- tions, i.e.,,,.,.... Ax(x)x E {0,1); since the optimal perfectly fair assignment function is deterministic when fo = nn (see Remark 3.4 in Section 3.2). The case of probabilistic assign- ment functions when no # n2 is discussed in Section 3.2.
Rg
n1
This constraint ensures the proportion of data belonging to cluster be balanced, resulting in fair clustering. That is, we find the cluster center μ and the assignment function A that minimize C(p,A) A) among all f and fair assignment functions A satisfying eq. (1).
The core idea of FCA to match two instances from differ- ent protected groups and assign them the same cluster. By doing matching all instances from Xg to 21 in a one- to-one fashion and assigning each pair to the same cluster- the resulting clustering becomes perfectly fair.
To assess the fairness level in clustering, Balance measure widely used (Chierichetti et al., 2017: Bera et al., 2019; Backurs et al., 2019; Esmaeili et al., 2021; Ziko al., 2021;
Zeng et al., 2023), which is defined as
Conversely, suppose we are given a perfectly fair clustering constructed by a deterministic assignment function A. Since no = n1 and AA is deterministic, there exists a one-to-one matching between X, and X1 such that two matched in- stances belong to the same cluster. Thus, we decompose the clustering cost in terms of the one-to-one matching, as presented in Theorem 3.1.
EnnEx A(x, 0)k Ex,ex, A(x,, 1)6 Exyex A(x;, 1)k ExExx A(x;; 0),}
min min kE[K]
Note that the higher balance is, the fairer the clustering is. Furthermore, the balance of any given perfectly fair cluster- ing min (Mo/n,, n,, nn/no). The objective of FC to mini- mize C(,,,, A) with respect to f E IK and A, under the fair- ness constraint (e.g., balance Re min (no/ /11, m2/no))) We abbreviate s() = A.(+) and A), = C(u,, A1) when their meanings are clear.
Theorem 3.1. For any given perfectly fair deterministic assignment function A and cluster centers p. there exists a one-to-one matching map T X, + Xyx such that, for any E (0, 1}. C(H,A A1)
For the case of perfect fairness, in Section 3, we prove that the FC objective can be decomposed into the sum of (i) the cost of transporting data from different protected groups to a common space (called the aligned space), and (ii) the clus- tering cost in the aligned space built by the transported data. Building on the decomposition, in Section 4.1, we intro- duce our proposed algorithm for perfect fairness. Then, in Section 4.2, we extend the algorithm to control the fairness level by relaxing the perfect fairness constraint.
E. Σ A.(X)
- -T(XII +
X + X
pkke
4
2
Transport cost WILL T
Clustering cost W.t. μs and
(2)
The assignment function A that minimizes eq. (2) given l and T assigns both x and T(x) to cluster k, where h = arg mingge(k] || x 1=l Hence, the optimal perfectly fair clustering can be found by minimizing E. [|[x-([X]]3] with respect to μ and T, instead of finding the opti- mal μ and A minimizing Al, We update μ for given T by applying standard clustering algorithm to px+T(x) x E X.). which is called the aligned space. To update T, any algorithm for finding the optimal matching can be used, where the cost be- tween two instances Xo E Xo and x1 E X1 is given by |xx-xx1' 2 / (1xx xx))/xx///11 mx2l (see Section 4.1 for the specific algorithm we use). Note that there are no complex constraints in updating μ and T. Finally, we define A corresponding to T, which assigns both x and T(x) to the same cluster on the aligned space { x++T(x) x E X.). See Appendix A.4 for a similar decomposition that extends to other general distance metrics (e.g., the Lp norm for p 2 1).
mink ll(x + T(X))/2 - mull")
3. Reformulation of fair clustering objective
This section presents our main theoretical contribution: we derive a novel decomposition of the perfectly fair (i.e., ExExx Ao(x;)&/ Exye, Ax(x)) = no/n2 for all & E [K)) clustering objective, which motivates our proposed algorithms in Section 4.
In Section 3.1, we introduce our idea through discussing the simplest case where the two protected groups are of equal size (ni- = n1). Then, in Section 3.2, we generalize to the unequal case (no * n1) by constructing the aligned space defined by given joint distribution on Xy Xi. We prove that there exists joint distribution such that the objective function of perfectly fair clustering can be decomposed into the sum of the transport cost with respect to the joint distribution and the clustering cost with respect to the cluster centers on the aligned space. Full proofs of all the theoretical findings in this section are given in Appendix B.
Remark 3.2 (Comparison to the baislet-based methods). Although our idea of matching data from different pro- tected groups may seem similar to the fairlet-based methods
3

---

Fair Clustering via Alignment
Method (Cost & Bal)
Standard (8.50 & 0.33). Fairlet-based (10.22 & 1.0)
Ours (9.82 & 1.0)
x0
*
Cluster center Hiz
Cluster center
Matched
Figure 1. Comparison between the fairlet-based method and our approach with no = n1 = 4 and K 2. The representative of each fairlet is set as the mean vector of the data within that fairlet, and the standard K-means algorithm is then applicd to this set of representatives. The clustering results are visualized using contours. While both the fairlet-based method and ours result in perfectly fair clustering, i.c., min(na/ /1, 0u /no). our approach yields lower cost (9.82 10.22). due more efficient matchings.
balance (Bal)=
(Chierichetti et al., 2017; Backurs et al., 2019), they funda- mentally differ:
Let Te nn/(nn de//nntna +ny) for s f s' {0,1). We then define
(xxx. == Toxo + π
Our method is an in-processing approach that directly mini- mizes the clustering cost with respect to both the matching map and cluster centers simultaneously. In contrast, the fairlet-based method a two-step pre-processing approach, which does not directly minimize the clustering cost; in- stead, it first searches for fairlets and then attempts to find the optimal cluster centers on the set of representatives for
as the alignment map.
Theorem 3.3. Let μ E TR and Q" E Q be the cluster centers and joint distribution minimizing
Ee 2 -X,11
2 min I (Xo, X1) 1 -meel?
each fairlet. See Appendix A. for details about fairlets. As a result, in the fairlet-based method, the matchings and cluster centers are not jointly optimized, which may lead to suboptimal clustering utility.
Then, AA; is the solution of the per- fectly fair K-means clustering, where A5(x)) Q" (arg ming (1) p=ll2 Xx x x) and Ai (x) is defined similarly.
Figure 1 illustrates how the faideet-based method can pro- duce suboptimal clustering, when compared to our approach. It implies that, more efficient matchings exist that yield higher clustering utility than the matchings of fairlets, and our approach is specifically designed to find these efficient matchings. We confirm this claim more comprehensively using real benchmark datasets in Section 5.2.
This result implies that, by simultancously minimizing the transport cost I|x,, X2 and finding the cluster cen- ters in the aligned space (Xo, X1) (Xo, Xi) ~ Q), obtain the optimal perfectly fair clustering. A notable observation is here that there is no explicit constraint in eq. (3). In fact, the constraint for perfect fairness (i.e., Σ Ex A(x,, 0)2/ Ex A(x;, 1)k = no/n1 for all k E [K]) is implicitly satisfied through the use of the align- ment map TA together with the assignment functions Aj and Ai. In conclusion, solving eq. (3) with respect to μ and Q yields the optimal perfectly fair clustering. The algorithm for solving eq. (3) is detailed in Section 4.
3.2. Case of unequal sample sizes: no f m
To handle the case no A n1, we follow a similar strat- egy to that for no = n1, but replace the matching map T with the joint distribution Q over X = 0 and X 1. For each {0, 1), let X, denote the random variable following the conditional distribution of X|S = 8, i.e., IP.. We reformulate the perfectly fair clustering cost in terms of cluster centers μl and joint distribution Q whose marginal distributions are 8 E {0, 1). Note that Q serves as a smooth and stochastic version of T.
Remark 3.4 (AA" becomes deterministic when no = n1). Assume that no M1. Then, for a given E Ng. note that %i is positive for a unique j E [m1), meaning that Q in Theorem 3.3 corresponds to the one-to-one matching map in Theorem 3.1. In other words, finding Q becomes equivalent optimizing the optimal permutation between [ng] and [n1]. See Remark 2.4 in Peyré & Cuturi (2020) for the theoretical evidence. Then, we have A5(x;)s :=
Let Q {all joint distributions Q on X, X1 with Q. P., s E {0. 1)), where @. is the marginal distribution of Q on X,. Theorem 3.3 below, which is the main theoretical result and motivation of our proposed algorithm, proves that the optimal perfectly fair clustering can be found by optimizing the joint distribution Q and cluster centers μ..
Q (arg ming (x;, X1) M 1|2 k|X,- = =x)
1 [arg ming || +xx+T(x=) - =1x112 = k), which is determinis- tic, provided that mg = mi = =1/2.
2

---

Fair Clustering via Alignment
4. Proposed algorithms
Algorithm 1 FCA algorithm
input (i) Dataset Xg U X, (ii) The number of clusters K.
4.1. FCA: Fair Clustering via Alignment
1: Initialize cluster centers μ =mux J kk=1
Based on Theorem 3.3, we propose an algorithm for finding the (approximately) optimal perfectly fair clustering, called
2: while μ has not converged do
3: Update r = [7%,5] E R by solving eq. (4) // Phase 1: update T
Fair Clustering via Alignment (FCA). FCA consists of TWO phases. Phase 1 finds the joint distribution Q with the cluster centers μa being fixed. Phase 2 updates the cluster centers μ with the joint distribution Q being fixed. Then, FCA iterates these two phases until cluster centers converge.
for a fixed μ..
4: Update fa by solving
min Σ Σド= Mi ming (x,, x,) - px l| for a fixed
(x,, // Phase 2: update μ
5: end while
6: Build fair assignments: for X; E Xx, define
Phase I: Finding the joint distribution Phase I finds the optimal Q that minimizes the cost in eq. (3) given μs. For this goal, we modify the Kantorovich problem (Kantorovich, 2006; Villani, 2008), which finds the optimal coupling be- tween two measures for given cost matrix. Appendix A.2 covers details regarding the Kantorovich problem along with the optimal transport problem.
Ax(x;) == Σx,ex, ToT I1 (arg ming ||,,X + T - - = k), k E [K].
output (i) Cluster centers sa [ (ii) Assignments Ao (x,), X E No and A1 E N..
In Appendix A.3, we introduce practical extension of FCA to scenarios involving multiple protected groups and present experimental results on real dataset that validate this extension (see Table 4).
First, the transport cost matrix between the two (the first term of eq. (3)) is defined by C = [ر,ي] E [R where I12. The clustering cost matrix between the aligned data and their assigned centers (the second term R= where d,, = [ [x;; xj) mall2 Then, we find the
C.j = ||X;
of eq. (3)) is defined by D [db.]] E
4.2. FCA-C: control of fairness level
It is also important to find the optimal non-perfectly fair clustering. For this purpose, we introduce a feasible relax- ation of FCA called FCA-Control (FCA-C), a variant of FCA specifically designed for controlling the fairness level.
optimal coupling I' [T,,]] E 1 solving
min |I(C + +D) @ 1 = min(cs.s + di.s)Taa
7h.3
1
1
(4)
Let W C Xo x X, be a given subset. The idea of our relax- ation is to apply FCA algorithm only to instances in W Xo X2 W and apply the standard K-means algorithm to those in W. Note that W = 0 becomes FCA, while W Xn x X, results in standard (fair-unaware) clustering. For given μ and W, we define CFCA W) ;= (2mo Xoo
subject to
nJ no
2.
J=1
Note that this problem becomes the original Kantorovich problem when D O. Hence, this objective can be also efficiently solved using linear programming, similar to the Kantorovich problem (Villani, 2008).
X, 12 + mink || X, -
- 13) ((Xo, X1) E W
and CK me-aa (14, W) = (ming (No [X μ |x l|2) +
Based on the optimal coupling that solves eq. (4), we define the joint distribution as (((xx,x;)) = Ni-- That is, we have the measures (weights) (7AJhefmoiseeln for the aligned points in (x;,,)) iiteol As a sult, we define the corresponding aligned space as the no X n2 many pairs of the weight and the aligned points: [(H,, TM (x;; xy)), Je(m))
ming (TI|X, - mxll)) ((x,, X1) E W). Denote E > O hyper-parameter that controls the fairness level. For
given E, FCA-C algorithm minimizes
Ex,.xi~ Danxxme(CCraall (Crca(H, W) + CK- (M, W))
(5)
with respect to μ. Q and W satisfying Q((X,,)) E W) S e. Figure visualizes an example of W and Q.
Phase 2: Optimizing cluster centers Phase op- timizes the cluster centers μ on the aligned space [(H,j (x,,, (xxx,x;)]< [x))oe(nolll obtained from Phase 1, by solving min, Ei D Va. ming T (x,, xy) - pul? Standard clustering algorithms, such the K-means++ al- gorithm (Arthur& & Vassilvitskii, 2007) or gradient descent- based algorithm, can be used to update μ. Note that in Section 5.4, we empirically show that FCA is stable regard- less of the algorithm used to optimize μ. See Algorithm for the overall algorithm of FCA.
Then, we construct A as follows. For xo E Xo, we define
Ao (xx)x
Fi (arg min ||T (Xo, X1) - p 112 k, (Xo+ X1) E Wo)
+ 1 (arg min [Xx - M = k) PI P1 X1) E W),
1
and the assignment function Ai can be defined similarly.
(6)
5

---

ne Fair Clustering via Alignment
Theorem 4.1 (Equivalence between C and constrained C),, Minimizing FCA-C objective Č(Q, W, pt) with the corre- sponding assignment function defined in eq. (6), is equiva- lent to minimizing Cp,,A.. A1) subject to A1) E A..
X1
E W FCA cost applied
X
%
Ml
W: K-means cost applied
Mass
Note that A. is based on the sum of unfaimesss for k [K], whereas several previous works (e.g., Bera et al. (2019); Backurs et al. (2019)) focus on the proportions for all k E [K], which is more directly related to bal- ance. However, As is also closely connected to bal- ance: (i) E = 0 ensures perfect faimess (i.e., balance min(no/n1, mn//nn and (ii) for all k E [K], the gap be- tween Σx, Ex,ex, Ao(xx)a/ Exex, A (xx)x and no/ni is bounded by E, as shown in Proposition 4.2. Its proof is provided in Appendix B.4.
Figure 2. Example illustration of W and I (or equivalently Q) when (no, m1) = (2 and e = 71.4 72.2 + 72.5-
In summary, FCA-C comprises three phases: the first two mirror the Phases 1 and 2 of FCA, and the third updates W. The overall algorithm for FCA-C is in Algorithm 2.
Algorithm 2 FCA-C algorithm
input (i) Dataset X, U X1 (ii) The number of clusters K.
(iii) Fairness level e E [0, 1].
Proposition 4.2 (Relationship between balance and =). For any assignment function (AD,A1) E Ac, we have
1: Initialize cluster centers j = {uR 1K and a subset
W C X such that RoR1 - Ej x(xx,,x,) e
W) S.
Ex An(x:)a
no
2: while μa has not converged do
max kE(K] Ex,ex Al Ax(x))a
3: Calculate the costs CK mens for (x;, Xj) E W and
OPcA for (x,, (x,,x,) E WS
where c ni
max (X)=
4: Update I by minimizing eq. (5) for fixed μ and W.
Phase I: update r
Section 5.2 empirically validates Theorem 4.1 and Propo-
5: Update u by minimizing eq. (5) for fixed I' and W.
sition 4.2, by showing that the trade-off between fairness (balance) and utility (cost) is effectively controlled by s.
// Phase 2: update μ
6: For all (x) Xo x X, caleulate xx) == 2momi ||x; [x,xx xj|| + (x, - [t.l|lLLer Let be the eth upper quantile. Update W = (xx,, x,) E
Lastly, we establish the approximation guarantee of FCA-C in Theorem 4.3, similar to Bera et al. (2019). The approx- imation error of given algorithm is defined by an upper bound on the ratio by which the cost of the solution of the algorithm can exceed the optimal cost. Let be the ap- proximation error of standard clustering algorithm used to find initial cluster centers without the fairness constraint. Suppose that supxex ||x|² <
No x X, : xx) > nel.
// Phase 3: update W
7: end while
8: Build fair assignment functions Ao and A₁ following Equation (6).
K output (i) Cluster centers μ {pu R==1. (ii Assignments
R for some R >>0. O.
Ao(x;), x; E Ao and (xx)) X, E &..
Theorem 4.3 (Approximation guarantee of FCA-C). For any given E, FCA-C algorithun returns an (T + 2) -approoxmeet solution with a violation 3Rs for the optimal fair clustering, which the solution of min Ao, subject to A1) E Ac.
Theoretical validity of FCA-C Notably, FCA-C algo- rithm achieves a solid theoretical guarantee for the (ap- proximately) optimal trade-off between fairness level and clustering utility, for any given fairness level to be satisfied.
A more formal statement is provided in Theorem B.2, with the proof in Appendix B.5. For example, if we use K- means++ + initialization (Arthur & Vassilvitskii, 2007), then we have O(log K). The violation term 3Rs suggests that FCA-C would be more efficient when e is small.
First, Theorem 4.1 shows that solving the objective of FCA-C algorithm in eq. (5) is equivalent to solve the clustering cost C(u, A) under a given fairesss constraint, whose proof is given in Appendix B.3. For technical sim- plicity, assume that the densities of Po and P1 exist (i.e., we consider the population version). See Remark B.1 in Appendix B when the densities do not exist. Recall that (X)())) ((Ab. A1): ΣK (X)()a)) - E,, (X)al S e) represent a set of fair assignment functions. Let C W. be the objective of FCA-C in eq. (5).
Remark 4.4 (Comparison of the approximation rate with existing approaches). The approximation rate t + of FCA- C is comparable to that of existing approaches. For example, Bera et al. (2019) proposed an algorithm that achieves a (r+ 2) -ppprpooeea solution with violation of 3. FCA-C and the algorithm of Bera et al. (2019) provide the same rate of T + but FCA-C can attain a smaller violation when R = 1, since & E [0, 1). Furthermore, Schmidt et al. (2019) provided
n, Exlex, (x(x)) Let A. :=
6

---

Fair Clustering via Alignment
(5.5r ipaapoooinntiion algorithm, which exceeds 7 + 2 for r > 2/9.
rithms. For given x, let k(x, s) be the index k such that (x(x) 1. Then, for given μ
K Cost and Bal on D are defined as: Cost = 2 ||x M and Bal = ming min (Fx, 1/kx), where Fx ΣxEx, An(x)) (a))//xxxx (x(x) Let Bal" == min / n1/no) be the balance of perfectly fair clus- tering for given D.
4.3. Reducing computational complexity
As discussed in Section 4.1, finding the joint distribution Q technically equivalent solving the Kantorovich problem, which can be done by linear programming (Villani, 2008). Its computational complexity is approximately O(z²) when no 11 = (Bonneel et al., 2011), indicating high computational cost when n is large. To address this is- sue in practice, we randomly split each group into L par- titions of (approximately) same sizes: (x(") ) of X and fx M= of X4. We then calculate the optimal cou- pling (11) between 26 and x;",, by solving eq. (4). The (full) optimal coupling between Xo and X, is estimated by f= diag( L. (Tr)),..... ,..;; (.)) Let m = |,260 | |2 be the partition size. This technique can theoretically reduce complexity by (n/m) x O(m²)
Baseline algorithms and implementation details For the baseline algorithms compared with FCA, we consider four methods: a pre- pre-processing (fairlet- method SFC from Backurs et al. (2019), two post-processing methods FCBC from Esmaeili et al. (2021) and FRAC from Gupta et al. (2023), and an in-processing method VFC from Ziko et al. (2021), which differs from the other baselines as it is specifically designed to control the trade-off between fairness level Bal and clustering utility Cost. For details of these baselines, refer to Appendix C.2.
O In our periments, we apply this technique with = 1024, which is significantly faster than using full datasets, while yielding similar performance (see Section 5.4 for the results).
When solving the linear program (i.e., finding the coupling matrix I'), we use the POT library (Flamary et al., 2021). For finding cluster centers, we adopt the scikit-leam library (Pedregosa et al., 2011) to run the K K-means algo- rithm. We specifically choose the K-means++ initializa- tion (Arthur & Vassilvitskii, 2007) with Lloyd's algorithm (Lloyd, 1982). An ablation study comparing the Lloyd's al- gorithm and a gradient descent-based algorithm (i.c., Adam (Kingma & Ba, 2014)) for finding cluster centers is pro- vided in Section 5.4. The maximum number of iterations is set to 100, and we select the best iteration when Cost is minimized.
5. Experiments
This section presents experiments showing that (i) FCA out- performs baseline methods in terms of the trade-off between fairness and utility; (ii) FCA-C effectively controls the fair- ness level; and (iii) FCA is numerically stable, efficient, and scalable. We further illustrate the applicability of FCA to visual clustering.
5.2. Performance comparison results
5.1. Settings
Trade-off: fairness level vs. clustering utility First, we compare FC algorithms in terms of their ability to achieve reasonable trade-off between faimess level (Bal) and clus- tering utility (Cost). Specifically, we compare FCA with three baselines: SFC, FCBC, and FRAC, all of which are designed achieve perfect fairness. Table presents Bal and Cost of the four methods, where FCA consistently attains the lowest Cost (i.e., the highest utility).
Datasets and performance measures We use three benchmark tabular datasets, ADULT (Becker & Kohavi, 1996), BANK (Moro et al., 2012), and CENSUS (Meek et al.), from the UCI Machine Learning Repository² (Dua & Graff, 2017). The sensitive attribute is defined by gender, marital status, and gender for ADULT, BANK, and CENSUS, respec- tively. The number of clusters K is set to 10 for ADULT and BANK, and 20 for CANSUS, following Ziko et al. (2021). ) The features of data are scaled to have zero mean and unit variance. We then optionally apply L2 normalization, as used in Ziko et al. (2021). Further details are given in Ap- pendix C.I.
Notably, FCA outperforms SFC by achieving higher Bal and lower Cost, highlighting the effectiveness of in- processing approach for finding better matchings. While FCA requires slightly more iterations until convergence (see Table 21 in Appendix C.3.8), it remains superior even with a smaller number of iterations similar SFC (see Table 22 in Appendix C.3.8). Moreover, FCA also outper- forms SFC in K-median clustering (see Table 23 in Ap- pendix C.3.9), which is the original clustering objective of SFC. Table 8 in Appendix C.3.1 additionally shows that FCA also outperforms the first fairlet- method intro- duced by Chierichetti et al. (2017). Furthermore, FCBC and
We consider two performance measures, Cost and Ba 1. The former assesses clustering utility, while the latter mea- sures fairness level. For a given assignment function A, let (x(x) := 1 (arg max, A, (x)x² = k) be a determin- istic version of A. Note that we use this deterministic Á
instead of A itself for fair comparison with existing algo-
hhttps://archiwr ve. iss, uci edu/ dataeaatsssssss
7

---

Fair Clustering via Alignment
Table Comparison of the trade-off between Hal 1 and Cost on ADULT, BaNK, and CENSUS datascts. We underline Hal values for the cases of near perfect fairness (i.e., Bal R Bail) ") and use bold face for the lowest Cost value among those cases. Similar results when data are not L2 normalized are presented in Table in Appendix C.3.1.
Dataset Bal*
ADULT / 0.494
BANK 0.669
CENSUS / 0.969
With L2 normalization
Cost (()
Bal (t)
Cost (4)
Bal (1)
Cost ())
Bal (1)
Standard (fair-unaware)
0.295
0.223
0.208
0.325
0,403
0.024
FCBC (Esmacili ct al., 2021)
0.314
0.443
0.685
0.615
1.006
0,926
SFC (Backurs al., 2019)
0.534
0.489
0,410
0,632
1.015
0.937
FRAC (Gupta al., 2023)
0.340
0.490
0.307
0.642
0.537
0.954
FCA V
0.328
0.493
0.264
0.645
0.477
0.962
FRAC offer lower Bal 1 and higher Cost than FCA in most cases. Specifically for fixed Cost 0.314, FCA achieves higher Bal than FCBC (see Table 7 in Appendix C.3.1). These results suggest that FCA is the most effective algo- rithm for maximizing utility under perfect fairness.
achieve reasonable Cost while controlling Bal.
Adult
Standard
0.32
FCA-C
Cost
0.32
Bal"
Table 2. Comparison of the two in in-processing algorithms, VFC and FCA, in terms of numerical stability when achieving the max- imum Bal, , on ADULT, BANK, and CENSUS datasets with L2 normalization. Bold-faced results are the highest Bal. Similar re- sults without L2 normalization are in Table 9 in Appendix C.3.I.
0.31
0.50
0.25
0.50
0.3h
0.40
0.65
Bal
Figure 3. Bal vs. Cost trade-offs on ADULT dataset. Black square (m) is from the standard clustering, orange circle (+) is from VFC, green star (+) is from FCA-C, C, orange dashed line (--) is the maximum of Bal that VFC achieve, and blue line (-) is the maximum achievable balance Bal*.
Bal (Cost)
Dataset / Ba1*
VFC (Ziko et al., 2021)
FCA V
ADULT / 0.494
0.437 (0.310)
0.493 (0.328)
BANK 0.649
0.568 (0.221)
0.645 (0.264)
CENSUS / 0.969
0.749 (0.432)
0.962 (0.477)
Figure 3 displays the performance of FCA-C and VFC across various fairness levels, on ADULT dataset. It shows that FCA-C achieves favorable trade-off for many values of Bal (by controlling E), with Cost similar to that of VFC. Similar results on other datasets or without L2 nor- malization are given in Figures 4 and Appendix C. Furthermore, FCA-C can attain Bal beyond the orange dashed vertical line, which is the maximum achievable Bal by VFC. Refer to Appendix C.2 for details on selecting for FCA and the hyper-parameteer used in VFC.
Numerical stability Second, we compare the two in- processing algorithms, FCA and VFC, in terms of their ability to achieve a high (near-perfect) fairness level (i.e., Bal s0 Bal') without numerical instability. To do so, we obtain the maximum Bal 1 that each algorithm can attain. We also evaluate robustness to data pre-processing, i.e., the impact of L2 normalization to numerical stability.
The results presented in Table 2 show that VFC achieves Bal values no higher than 90% of Bal*. While FCA is explicitly designed to achieve perfect fairness, VFC is de- signed to control Bal using a hyper-parameter However, even with a large syper-parameter (see Appendix C.2 for the chosen hyper- parameerreeeerr VFC fails to achieve perfect fairness (i.e., Bal remains significantly lower than Bal*). Moreover, the performance gap between FCA and VFC be- comes greater without L2 normalization than with it, and VFC further fails on CENSUS dataset due to an overflow (see Appendix C.3.1 for details on this issue).
Furthermore, the computation times of FCA-C (when E > 0) and FCA (i.e., FCA-C with = 0) are compared in Table 20 in Appendix C.3.8, indicating that finding W in FCA-C does not require significant additional time.
5.3. Applicability to visual clustering
We further evaluate the applicability of FCA to visual clus- tering using two image datasets, which are commonly used in recent visual clustering algorithms (Li et al., 2020; Zeng et al., 2023): (i) RMNIST, mixture of the original MNIST and a color-reversed version, and (ii) OFFICE-31, consisting of images from two domains.
Control of fairness level In addition to the previous analy- sis for the scenario of perfect fairness (where Bal x Bal*), we also compare FCA-C and VFC in terms of controlling 1 lower than Ba To this end, we assess the ability to
We compare FCA with SFC, VFC and two visual FC base- lines: DFC (Li et al., 2020) and FCMI (Zeng et al., 2023).
8

---

Fair Clustering via Alignment
Note that DFC and FCMI are end-to-end algorithms that simultaneously perform clustering and learn latent space us- ing autoencoder with faimess constraints. In contrast, FCA, SFC, and VFC are applied to a latent space pre-trained by autoencoder without any fairness constraints. The clustering utility is evaluated using ACC (accuracy based on assign- ment indices and ground-truth labels) and NMI (normalized mutual information between assigned cluster distribution and ground-truth label distribution), as in Zeng al. (2023).
the initialization of cluster centers. Appendix C.3.4 shows that FCA is robust both factors.
(3) Consistent outperformance across various K; We confirm that FCA consistently outperforms baseline meth- ods for various values of K. That is, as shown in Figure 8 in Appendix C.3.5, FCA outperforms the baseline methods across all K E {5, 10, 403.
(4) Scalability for large-scale data: We further inves- tigate the adaptivity of FCA to large-scale data. To do so, we compare FCA and VFC using a large-scale dataset (n 10%), and observe that FCA still outperforms VFC (see Appendix C.3.6).
Table 3. Comparison of clustering utility (ACC) and fairness level (Ba1) on two image datasets. 'Standard (fair-unaware) indicates autoencoder K means. The first-place values bold, and second place values are underlined.
Dataset Bal*
RMNIST 1.000
OFFICE-31 0.282
(5) Linear program vs. Sinkhorn for optimizing Q In our main experiments, we solve the objective in eq. (4) with the linear programming. To explore alternative approaches,
A ACC, B = Bal
A (t)
B (t)
A (T)
(1)
Standard (fair-unat) (
41.0
0.000
63.8
0.192
we compare (i) FCA with the linear programming and (ii) FCA with the Sinkhorn algorithm, in terms of Cost, Bal, and runtime. Table 19 in Appendix C.3.7 shows that their performances are comparable; however, the Sinkhorn algo- rithm requires tuning a regularization parameter, suggesting that solving the linear program remains a practical and reli- able option.
SFC (Backurs al. 2019)
51.3
1.000
61.6
0.267
VFC (Ziko et al., 2021)
38.1
0.000
64.8
0,212
DFC (Li ct al., 2020)
49.9
0.800
69.0
0.165
FCMI (Zeng et al., 2023)
88.4
0.995
70.0
0.226
FCA V
89.0
1.000
67.6
0.270
Table 3 compares FCA with the baseline methods, showing its performance is comparable to the state-of-the-art FCMI and generally better than SFC, VFC, and DFC. While DFC achieves slightly higher ACC on the OFFICE-31 dataset, its Bal is significantly lower (0. 165 vs. 0.270 of FCA). No- tably, while FCA operates as a two-step approach leveraging the pre-trained latent space, while DFC and FCMI are end- to-end methods. Moreover, FCA offers practical benefits: (i) requiring fewer hyper-parameter parameters, reducing burden of hyper- parameter tuning in the absence of ground-truth labels, and (ii) adaptability with any pre-trained latent space.
6. Conclusion and discussion
This paper has proposed FCA, an in-processing algorithm for fair clustering, inspired by the theoretical equivalence between optimal perfectly fair clustering and finding cluster centers in the aligned space. FCA algorithm is based on well-known algorithms, the K-means algorithm and linear programming, making it transparent and stable. Further- more, we have developed FCA-C (a variant of FCA) to control faimess level, and established its approximation guarantee. Experimental results show FCA achieves near- perfect fairness, superior clustering utility, and robustness to data pre-processing, optimization methods, and initializa- tion.
Further details are provided in Appendix C.3.2, where Ta- ble 12 presents the full results of Table 3, which includes the similar superiority of FCA in terms of NMI values. More- over, Table 13 highlights FCA's additional benefits over the bairlet-based method (SFC), in terms of matching efficiency.
A promising direction for future work is to apply FCA to other clustering algorithms such as model-based clustering,
5.4. Ablation studies
e.g., Gaussian mixture, which we will pursue in near future.
(1) Selection of the partition size m We empirically confirm the efficiency of the partitioning technique in Sec- tion 4.3, by investigating the convergence of Bal and Cost with respect to the partition size m. In Appendix C.3.3, Figure suggests that m = 1024 yields reasonable results, while Table 14 shows a significant reduction in computation time.
(2) Optimization and initialization of cluster centers μı: We also analyze the stability with respect to (i) the choice of optimization algorithm for finding cluster centers, and (ii)
9

---

Fair Clustering via Alignment
Acknowledgements
URL htlphttt////rooeeedeiie iggs ml mrl.. wwt.mml............. / agarwal18a.htar
This work was partly supported by the National Research Foundation of Korea(NRF) grant funded by the Korea governmen((MSIT) (No. A022RA557708390 tional Research Foundation of Korea(NRFF) grant funded by the Korea governmen((MSIT) (RS-2025-00556079, Next-generation Intelligence semiconductor R&D Pro- gram through the National Research Foundation of Ko- rea(NRF) funded by the Korea govemmenn(MSSTTRRS 2024-00431718) and by Institute of Information & commu- nications Technology Planning& & Evaluation (IITP) grant funded by the Korea goVSrM INO.RS-2021- II21 1343, Artificial Intelligence Graduate School Program (Seoul National University)).
Agarwal, A., Dudík, M., and Wu, Z. S. Fair regres- sion: Quantitative definitions and reduction-based al- gorithms. In Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9- 15 June 2019, Long Beach, Califormia, USA, 2019. URL http:/ htppppooodnnnggee ml www..prrrss///. agarwall9d. html.
the Na-
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine bias. ProPublica, May, 23:2016, 2016.
Arthur, D. and Vassilvitskii, S. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA '07, pp. 1027-1035, USA, 2007. Society for Indus- trial and Applied Mathematics. ISBN 9780898716245..
Impact Statement
This study aims to advance the field of algorithmic fairness in machine learning. In particular, given the growing ap- plication of clustering algorithms across diverse domains, we believe the proposed framework offers promising ap- proach to fair clustering. For example, it can ensure that privileged and unprivileged groups are clustered fairly, lead- ing to unbiased downstream Decision-making Thus, this study is expected to yield potentially positive impact rather rather than significant negative socictal consequences.
Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., and Wagner, T. Scalable fair clustering. In International Conference on Machine Learning, pp. 405-413, PMI.R, 2019.
Becker, B. and Kohavi, R. Adult. chine Learning Repository, 1996.
UCI Ma-
DOI:
https///bb.ogg//2223333XXXX
Furthermore, incorporating the joint distribution in the pro- posed algorithm enables the identification of specific data that are matched and assigned together. This feature can enhance interpretability of fair clustering through the lens of implicit matching.
Bera, S., Chakrabarty, D., Flores, N., and Negahbani, M. Fair algorithms for clustering. Advances in Neural Infor- mation Processing Systems, 32, 2019.
Bertsimas, D., Farias, V. and Trichakis, N. The price of fairness. Oper. Res., 59(1):17-31, January 2011. ISSN 0030-364X. doi: 10. 10.11877opre.11000000 //doi. //doi.org/100 /10o///g/.00/.. 10. 1127/2/7pre./ 1100. 0865.
While this work focuses on proportional (group) fairness, we acknowledge that such approach may overlook other fairness notions, such as individual fairness or social fair- ness (e.g., balancing clustering costs across groups), which are not explicitly addressed within the proportional fairness framework. We therefore encourage readers to interpret our results with this scope in mind: our goal is to improve the trade-off between proportional fairness level and clustering cost, but care must be taken when considering the broader implications for other fairness notions. In conclusion, we ticipate future studies that integrate fair clustering research with these additional notions of fairness.
1100.086.. URL https:
Bonneel, N., van de Panne, M., Paris, S., and Hei- drich, W. Displacement interpolation using lagrangian mass transport. ACM Trans. Graph., 30(6):1-12, dec 2011. ISSN 0730-0301. doi: 10.1145/2070781. 2024192. URL https: /ttp://........11/1/// 2070781.2024192.
Butnaru, A. M. and Ionescu, R. T. From image to text classification: A novel approach based on clustering word embeddings. Procedia Computer Science, 112:1783-1792, 2017. ISSN 1877-0509. doi: http://00..ogg/ll.....//pppssp22 URL sicteene//rrtiiell///////////0// Knowledge-Basee and Intelligent Information & Engi- neering Systems: Proceedings of the 21st International
References
Agarwal, A., Beygelzimer, A., Dudik, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In Dy. J. and Krause, A. (eds.), Pro- ceedings of the 35th International Conference on Ma- chine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 60-69. PMLR, 10-15 Jul 2018.
Conference, KES-20176-8 September 2017, Marseille, France.
10

---

Fair Clustering via Alignment
Chen, L., Kyng, R., Liu, Y. P., Peng, R., Gutenberg, M. P., and Sachdeva, S. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Sympo- sium on Foundations of Computer Science (FOCS), pp. 612-623, 2022. doi: 10. 1009///05554572222.00000
Donini, M., Oneto, L.,, Ben-David, S., Shawe-Taylee S., and Pontil, M. Empirical risk minimization under fairness constraints. In Advances in Neural Information Process- ing Systems, pp. 2791-2801,
Dua, D. and Graff, C. UCI machine learning repository, 2017. URL http: / arhive icss uci www..euuuuee.e edd/ml.
Chhabra, A., Masalkovaité, K., and Mohapatra, P. An overview of fairness in clustering. IEEE Access, 9: 130698-130720, 2021. doi: 10.1109/ACCESS.202.. 3114099.
Esmaeili, S., Brubach, B., Srinivasan, A., and Dickerson, J. Fair clustering under a bounded cost. Advances Neural Information Processing Systems, 34: 101144444435555 2021.
Chiappori, P., McCann, R., and Nesheim, L. Hedo- nic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness. Economic Theory, 42(2):11-354, 2010. URL attpp::/EconPapees.eeeeee ott.:apppee..eree....ooooo//eeee spr: joecth:v::::::: 42::::tth...222:::::::::::::::::
Flamary, R., Courty, N., Gramfort, A., Alaya, M. Z., Bois- bumon, A., Chambon, S., Chapel, L.., Corenflos, A., Fatras, K., Fournier, N., Gautheron, L., Gayraud, N. T., Janati, H., Rakotomamonjy. A., Redko, I., Rolet, A., Schutz, A., Seguy, V., Sutherland, D. J., Tavenard, R., Tong, A., and Vayer. T. Pot: Python optimal transport. Journal of Ma- chine Learning Research, 22(78):1-8, 2021. URL http:
Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. Fair clustering through fairlets. Advances in neural information processing systems, 30, 2017.
//jmlr watggpapperse http//22222222222 21222005551.h.. html.
Forrow, A., Hütter, J.-C., Nitzan, M., Rigollet, P. Schiebinger, G., and Weed, J. Statistical optimal trans- port via factored couplings. In Chaudhuri, K. and Sugiyama, M. (eds.), Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 Proceedings of Machine Learn- ing Research, pp. 1454-2465 PMLR, 16-18 Apr 2019. URL https: httpp//ooceennnn.eeee/ mlr. wwl.r.press/vve forrowl 9a html.
Chzhen. E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M. Fair regression with wasserstein barycenters. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances Neural Information Pro- cessing Systems, volume 33, pp. 7321-7331. Curran As- sociates, Inc., 2020. URL https: httptssss///rrrceednggg... cc/ httpippppcccppppeeeeeeee pdf.
Galichon, A. Optimal Transport Methods in Economics.
Princeton University Press, 2016. URL httht/tp/// /ttt:://ww.. jstor. .rgg wwt.oorgg//saaaeee stts//aalle///// cttlglxshh.
Cuturi, M. Sinkhom distances: Lightspeed compu- tation of optimal transport. In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), Advances in Neural Information Pro- cessing Systems, volume 26. Curran Associates, Inc., 2013. URL https: httpp:s:///cccednng..... neurips.com hctps/ppppppp/11///i.eee// af22 pdf.
Genevay, A., Cuturi, M., Peyré, G., and Bach, F. Stochastic optimization for large-scale optimal transport. In Proceed- ings of the 30th International Conference on Neural In- formation Processing Systems, NIPS' 16, pp. 4440-3448, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Gordaliza, P., Barrio, E. D., Fabrice, G., and Loubes, J.- M. Obtaining fairness using optimal transport theory, In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 2357-2365 PMLR, 09-15 Jun 2019, URL httpt::///// WRRhhtts:://poceeee http://pooceeeennnee/ee/ mll press/997/ gordalizal html.
Damodaran, B., Kellenberger, B., Flamary, R., Tuia, D., and Courty, N. Deepjdot: Deep joint distribu- tion optimal transport for unsupervised domain adapta- tion. In Computer Vision ECCV 2018: 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part IV, pp. 467-483, Berlin, Heidelberg, 2018. Springer Verlag. ISBN 378-3-030-012224-3 doi: 10. 10.100779788-3-000-012223 28. URL https://ps/d htg/10.1007/990 3-008-3--330---- 01225-0_28..
Guo, J., Zhu, X., Zhao, C., Cao, D., Lei, Z., and Li, S. Z. Learning meta face recognition in unseen domains. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6162-6171, Los Alamitos, CA, USA, jun 2020. IEEE Computer Society. doi: 10. D0I.11//VVP2220000.O2 200.222200000000000 URL
Deb, N., Ghosal, P., and Sen, B. Rates of estimation of opti- mal transport maps using plug-in in estimators via barycen- tric projections. NewrIPS, 2021.

---

Fair Clustering via Alignment
http:://boi..eeeccmpttrrrccc org/ 10. 10.1109/CVPR42600.00 00620.
Le, Q. V. Building high-level features using large scale unsupervised learning. In 2013 IEEE international con- ference acoustics, speech and signal processing, pp. IEEE, 2013.
Gupta, S., Ghalme, G., Krishnan, N. C., and Jain, S. Ef- ficient algorithms for fair clustering with a new no- tion of fairness. Data Min. Knowl. Discov, 37(5): 1959-1997, mar 2023. ISSN 1384-5810. doi: 10.1007/ 1007/s1061 000-1100611002-09222200
Li, P. Zhao, H., and Liu, H. Deep fair clustering for visual learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9070- 9079, 2020.
https: //tp://.o./o/goo////////
Harb, E. and Lam, H. S. Kfe: A scalable approximation algorithm for k-center fair clustering. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 14509-14519, Curran Associates, Inc., 2020. URL htt.tppss/pprccceen....eeeeeeee cc cc/pppperfflllesspeer///////////
Lloyd, S. Least squares quantization in pem. IEEE Transac- tions on Information Theory, 2892):129-137, 1982. doi: 10. 1999/TTT.982.105644459
Meek, C., Thiesson, B., and Heckerman, D. US Census Data (1990). UCI Machine Learning Repository. DOI: https//doo.org/0022444///33
(dd2999ff42200888355eeeeeleeeee2 pdf.
Mehrabi, N., Morstatter, F,, Saxena, N., Lerman, K., and Galstyan, A. A survey on bias and fairness in machine 2019.
Hellman, D. Measuring algorithmic faireess. Crim-
inal Procedure eJournal, 2019. URL https:
learning. arXiv preprint
//api. www.sttesaannnooo.e..e org/CorpusID; 199002104.
Mittal, H., Pandey, A. C., Saraswat, M., Kumar, S., Pal, R., and Modwel, G. A comprehensive survey of image segmentation: clustering methods, performance param- eters, and benchmark datasets. Multimedia Tools and Applications, pp. 1-26, 2022.
Hütter, J.-C. and Rigollet, P. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 49(2): 1166 - 1194, 2021. doi: 10. 20114/00-AOSSSS https: //coi///oiii www/oogg./ooooooooo 1214 2202144/00-009999777
URL
Ingold, D. and Soper, S. Amazon doesn't 't consider the race of its customers. should it. Bloomberg, April, 1, 2016.
Moro, S., Rita, P., and Cortez, P. Bank Market- ing. UCI Machine Learning Repository, 2012. DOI:
Jiang, R., Pacchiano, A., Stepleton, T., Jiang, H., and Chiappa, S. Wasserstein fair classification. In Adams, R. P. and Gogate, V. (eds.), Proceedings of The 35th Uncertainty in Artificial Intelligence Con- ference, volume 115 of Proceedings of Machine Learning Research, pp. 862-872. PMLR, 22-25 Jul 2020. URL httptttss://rrrceeeeeeeee pttp///pcceeeen..ce/eep//pc mlr press// v115/jiang20a.ntt html.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
Kantorovich, L. On the translocation of masses. Journal of Mathematical Sciences, 133:1381-1384 2006.
Peyré, G. and Cuturi, M. Computational optimal trans- port, 2020. URL httpttt/://ee pettttss//arxivii wwt.iii..rrabb////ee/ 00567.
Kim, K., Kong, I., Lee, J., Chae, M., Park, S., and Kim, Y. Fairness through matching. Transactions on Machine Learning Research, 2025. ISSN 2835- 8856. URL
Quadrianto. N.. Sharmanska, V., and Thomas, O. Discover- ing fair representations in the data domain. In Proceed- ings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 8227-8236, 2019.
net/forum?
id=dHljjaNHh1.
Kingma, D. P. and Ba, J. Adam: A method for stochastic op- timization, 2014. URL 2012.6980.
Salimans, T., Zhang, H., Radford, A., and Metaxas, Im- proving gans using optimal transport, 2018.
org./ / abs/
Kleindessner, M., Samadi, S., Awasthi, P., and Morgenstern, Guarantees for spectral clustering with fairness con- straints. In International conference on machine learning, pp. 3458 -367. PMLR, 2019.
Schmidt, M., Schwiegelshohn. C., and Sohler, C. Fair coresets and streaming algorithms for fair k-means. In WAOA, pp. 232-251, 2019. URL httpp:://ddoo //tp:::///..../// org/ 10. 3- -007788---000----80
12

---

Fair Clustering via Alignment
Seguy, V., Damodaran, B. B., Flamary, R., Courty, N., Rolet, A., and Blondel, M. Large scale optimal trans- port and mapping estimation. In International Confer- ence on Learning Representations, 2018. URL https: //openreview ewwew.wwww........ net/ forum? dd z. 1p1bw.
Ziko, I. M., Yuan, J., Granger, E., and Ayed, I. B. Variational fair clustering. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 1 1202-112009 2021.
Su. Z., Wang, Y., Shi, R., Zeng, W., Sun, Luo, F., and Gu, X. Optimal mass transport for shape matching and comparison. IEEE Transactions on Pattern Analysis and Machine Intelligence, (7(1 37211))2246-2255, 2015. doi: 10.
11097PPAM12011.24008544 244044446..
Villani, C. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008. ISBN 9783540710509. URL
httts:://bokk goo.lss..ooolooooooooo..oo google.ooo.oooooooooooooooooooo. co. ceo.kr/boocke kr/booksiid- hV8o5R7_5tkc.
Vincent, P., Larochelle, H., Lajoie, I., Bengio, Y., and Man- zagol, P.-.. Stacked denoising autoencoders: Learn- ing useful representations in deep network with local denoising criterion. Journal of Machine Learn- ing Research, 111110)3331-3408, 2010. URL http: //jmlr. org. wwtpa//rr.rrgpppp////lleo/ http://pppre///i//cennnntt 0a htmll
Widiyaningtyas, T., Hidayah, I,, and Adji, T. B. Recom- mendation algorithm using clustering-basse upesim (ch- upcsim). Computers, 10(10):123, 2021.
Yang, K. D. and Uhler, C. Scalable unbalanced opti- mal transport using generative adversarial networks. International Conference on Learning Representations, 2019. URL https: id=HyexAiASEM.
wttpttttttt///eeeeeeeeeeeeeee http:////pppeeeeeeeooomemmm/ forum?
Yeh, I. and Lien, C. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2, Part 1):2473-2480, 2009. ISSN 0957-4174. doi: https://oo.ooog///000l..sss..2. com/ 020. URL
Zafar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. Fairness constraints: Mechanisms for fair classifica- tion. In Artificial Intelligence and Statisties, pp. 962-970, 2017.
Zeng, P., Li, Y., Hu, P., Peng, D., Lv, J., and Peng, X. Deep fair clustering via maximizing and minimizing mutual in- formation: Theory, algorithm and metric. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 23986-23999 2023.
Zhang, Y., Wang, Z., and Shang. J. Clusterllm: Large language models as a guide for text clustering. arXiv preprint ar Xiv:2205. 14871, 2023.
13

---

Fair Clustering via Alignment
A. Supplementary discussion
A.1. Fairlet-based methods
Fairlet decomposition was first introduced in Chierichetti et al. (2017), providing a pre-processing method for fair clustering. fairlet is defined as a subset (as small as possible) of data in which the proportion of the sensitive attribute is balanced. The dataset is then partitioned into disjoint fairlets. It is important to note that the fairlets are not built arbitrarily; instead, the sum of distances among instances within each fairlet is minimized (i.e., each fairlet consists of similar instances). Finding such fairlets can be done by solving the minimum cost flow problem.
Notably, when no = ni, building fairlets is equivalent to finding the optimal coupling I' in the Kantorovich problem, which can be understood as special case of minimum cost problem (Peyré & Cuturi, 2020; Chen et al., 2022). Hence, we can say that the fairlet-based methods find the coupling only once, then apply the standard clustering algorithm.
After building the fairlets, each fairlet then deterministically assigned to a cluster. Since fairness is implicitly guaranteed within each fairlet, the resulting clustering directly becomes also fair. The representatives of each fairlet can be arbitrarily chosen when nu R1, chosen by the medoids (or possibly the centroids) when no & f1,, as suggested by Chierichetti et al. (2017). Then, a standard clustering algorithm is applied to the set of these chosen representatives.
On the other hand, the computational cost is high, with most of the time spent finding the fairlets due to the quadratic complexity of the minimum cost flow problem. To address this issue, SFC (Backurs et al., 2019) proposed a scalable algorithm for fairlet decomposition by using a reduction approach using metric embedding and trees. See Appendix C.2.3 for details on the SFC algorithm.
A.2. Optimal transport problem
The notion of Optimal Transport (OT) provides a geometrie view of the discrepancy between two probability measures. For two given probability measures P1 and P2,, map T Supp(P1) + Supp(P2) is defined as 'transport map' if TT = P2, where T + (AA) Pi PT (A)). AA, is the fush-forward measure. The OT map is the minimizer of transport cost among all transport maps. That is, the OT map from Pi to P2 is the solution of minT Pi Pi-Pa Pa Ex-p, (c (X, T(X))) for pre-specified cost function e (e.g., L2 distance). which is so-called the Monge problem.
Kantorovich relaxed the Monge problem by seeking the optimal coupling (joint distribution) between two distributions. The Kantorovich problem is mathematically formulated as x Ex (c(X, Y)) where II P2) is the set of all joint measures of Pi and P2. For two empirical measures, this problem can be solved by the use of linear programming as follows. For given two empirical distributions on X,- = { J and X1 { the cost matrix between the two is defined by C: = [ct_] E IR where 4, = ||x; x, 11 Then, the optimal coupling (joint distribution) is defined by the matrix I = [ E Reax that solves the following objective:
1 11
min |CoT min R. s.t. %5.
n. 2 0.
1=1 n10
This problem can be solved by the use of linear programming. For the case of large n with no # n1, various feasible estimators have been developed (Cuturi, 2013; Genevay et al., 2016), e.g., the Sinkhorn algorithm (Cuturi, 2013). Note only practical implementations, but theoretical aspects such as minimax estimation have also discussed deeply (Seguy et al., 2018; Yang & Uhler, 2019; Deb et al., 2021; Hütter & Rigollet, 2021). Recently, the OT map is utilized in diverse domains, for example, economics (Galichon, 2016; Chiappori et al., 2010), domain adaptation (Damodaran et al., 2018; Forrow et al., 2019), and computer vision (Su et al., 2015; Salimans et al., 2018). Several studies, including Jiang et al. (2020); Chzhen et al. (2020); Gordaliza et al. (2019); Kim et al. (2025), also employed the OT map in the field of algorithmic fairness for supervised learning.
A.3. Extension to multiple protected groups
In this paper, we mainly focus on the case of two protected groups, for ease of discussion. However, it is possible to extend FCA to handle multiple (more than two) protected groups. The idea is equivalent to the case of two protected groups: matching multiple individuals from different protected groups
14

---

Fair Clustering via Alignment
The of equal sample sizes Let G be the number of protected groups, and denote 8 E {o,.... G 13 fixed sensitive attribute anchor reference) attribute. For the case of no nG-1; similarly decompose the objective function in terms of matching map, follows. First, we decompose the clustering objective similar the proof of Theorem 3.1:
K
= R
As
[X]
- 1A
k=1
K
= a B.
Σ k=1
A.
(X)x
| +
Σ 8'
T
where T is the one-to-one matching map from X'. N2 for s' {o,..... G 11. Note that T then becomes the identity map from Xx- to X, for s' = TThen for any given x and MA, we can decompose |xx M4 by
1x (x -xx((x))
x Es Tx((x)
G
(x-
x Eejor Tx((x)
+2
p1
G
G
We also similarly decompose (T,(()) 11:112
E ""r4 (T.((xx
x Ex' Tx
14h
G
(Tx (x)( x + Ev Txr(x)
+2
pk
G
By summing up the above G many terms, we have the final result that
Exyo (T, (T, (X))
X E.E
(X)(X)
pik 1).
(2)
E. A.
Σ
G
G
Note that this result holds for any anchor s" E GO,...,G-111
The case of unequal sample sizes For the case of unequal sample sizes, we also derive a similar decomposition (i.e., eq. (8)). We first define the alignment map as: T T (xa..... .., xG-1) == ToXu +... xG-1XG-1, where म, ng/n for E (O....,Ge G Then, find the joint distribution and cluster centers by minimizing the following objective:
G-1
|| + min (X (X...... .....) -xx11
E E Xa-1
Σ ==
G
Σx, xx))
(8)
s'
where N I1--1 Tg.
The proof idea is similar the case of two protected groups, in Theorem 3.3. We first recall the original K-means objective:
Co,, AG-1) == E > As Ax(X)al |) X nu GG T. Ek
km A. Ax(X))ul) (X.)a||X, - -Mul12 Consider set of joint
distributions of X given μ Q := (Q( (xo, ... x H1) x, Xs. (O...., G 1}). Then, we can
show that there exists Q = Q( XG x Q satisfying
K Clp.An..., = Σ T Eg Σ Ax - 1
G-1
kml
G-1
EXo....... 1)m8
Σ 1=0
X, mall 1
15

---

Fair Clustering via Alignment
by using the same logic in the proof of Theorem 3.3. Furthermore, we reformulate
G-1
||
E [o.... Xo-1
Σ
G
Σx,
Xx,)
min T (Xo. ... Xo-1) mxll?
s'
with the assignment functions for fair clustering given as
( min
Ax(x,)& = Q
arg min |T, +
Σ a'
k x, xs
V (o....,G-11}
Furthermore, since finding the joint distribution for multiple protected groups is technically similar to the case of two protected groups, the optimization of the objective in eq. (8) can be solved using linear program.
Experiments To empirically confirm the validity of the extension, defined by dividing marital status angll/married/divoreedd (directly following the approach of VFC (Ziko et al., 2021)). We then compare the performance of FCA with VFC, which also can handle multiple protected groups The result is presented in Table 4 below, showing the superior performance of FCA: achieving lower cost (0.222 < 0.228) along with higher balance (0. 082 > 0.172).
BANK dataset with three protected groups
Table Comparison VFC and FCA in terms the trade-off between Bal and Cost, on BANK dataset with three protected groups.
BaNk
groups (single/marriedd/iivoreee
Bal* 0.185
Cost (4)
Bal (t)
VFC
0.228
0.172
FCA V
0.222
0.182
A.4. Extension to K-clustering for general distance metrics
Let D IRd x x + R_ be a given distance satisfying (i) D(v, w) S. u) w), (ii) D(v.w) u,, +u), and (iii) D(vv, Aw) | D(v, w), for all v, w, u E Rd and E IR. For example, D can be the Lp norm on Rd for any p 2 1. Then, for the balanced case no nı, we can replicate the argument of Theorem 3.1 as follows:
K E A(X SE, Σ As())a 1=1
K
D
T(X) 2
X T(X)
(4k ))
E
+
2
2
Minimizing this upper bound yields a fair K K-clustering procedure for any distance satisfying the above conditions. Note that using the L1 norm for corresponds to the K-median clustering.
See Appendix C.3.9 for experiments based on this approach, showing the outperformance FCA over SFC in view of the K-median clustering.
16

---

Fair Clustering via Alignment
B. Proofs of the theorems
B.1. Proof Theorem 3.1
Theorem 3.1. For any given perfectly fair deterministic assignment finction and cluster centers μ., there exists a one-to-one matching map T X, + R2 such that, for any {0, {0, 1}.
K
X
T(
X
X +
2
AI, = E.
(x)))
+
p/6
(9)
4
2
Proof of Theorem 3.1. Without loss of generality,
0. First, it clear that we can construct one-to-one map T that
maps each x {x E Xa An(x) 1} to a unique x' x = {x' Xi A1 1} for all k [K].
That is, (T(x): x E x x Ak [K] and (T(x) x E No} X1.
Then, for the given T, we can rewrite the clustering cost as
K As X
K
Ao, E
X
1
Eo
Ax(x): (IXX - m=l (T(() - -1x113).
(10)
2
k=1
k=1
For any given x and (4k: decompose
1 as:
x T(x)
x + T(x)
||x
1xxl1
x
1.
2
x
T(
x T(x)
+ T(x)
T(x)
2
x
p16
4
2
2
2
We similarly decompose [ 1 as:
x+ T(x)
T(x)
2
[((x) 1x
T(x)
2
[2
x + T(x)
x T(x)
x + T(x)
pk
+2 T(x)
p1
Adding the two terms, we have
x - [2
x T(x)
2
11x
4
2
Finally, we conclude that
K
R
Ao (X)x (1IX -
- 13
A=1
(11)
K
XX-T(X)1
X+ X T(X)
12)
Ao(X);
-2
+
14
4
2
Am
B.2. Proof of Theorem 3.3
Theorem 3.3. Let μ* and Q* be the cluster centers and joint distribution minimizing
2TTTTI|XX 22 + min T X1) pall?))
min E(x..x,)~0 RRe
(12)
= Then, (μ*, AG, is the solution of the perfectly fair K-means clustering, where Aj(x); Q" (arg ming T (x, X1) - p 112 X xx) and (T(x)) defined similarly.
17

---

Fair Clustering via Alignment
Proof of Theorem 3.3. Let X X 8, (0, 1]. For given (1t, Ao, Ao; recall the original K-means objective:
C(u,, A1) = E Ass As(X)x X -- u TolBo Ex=1 Ao(Xo)) Xo - uell + Σx=1 ( - u
Consider set of joint distributions Xo. X1 given μ as Q = {Q[ (x). (x) x1)( x X,, E X13. We show that there exists Q [((xx, x1 1114) E satisfying
K
K Au Ao(k XD - -1:1 + 11 Σ
Ao; A1) = ToBU Σ
(1(G))& - Mell
(13)
k=1
- -o 1 + Tı T j4k 13)
Let
Q(1x0, [M<xoxxHHuu x1)) K (xxx)) Po
(14)
Cx.
where C₁ = EA)(()) = Ao (Xo) = EEAAI Then,
B B(x,,X (Tol 116l1 TI | 11x112)
-x -M Σ (A(T)))TI - P1
(15)
(BoTO Xo uull BITT - mull?) Ao,
which concludes eq. (13). Our original aim is find (H, A1) minimizing C(p,, Au,AA) Let ju(x) pkg where = arg ming || Mxll Let jx(xo, x1) pas, where k = arg mink || TIXi -u -x For given Q defined in eq. (14), similar to Theorem 3.1, we can reformulate
E xxx,))) ( (TolXx (XX))l + 3x()))13)
(16)
-x (2 X. X,112 NT + Tx, x(xo, 13)
In turn the assignment functions given
Ao(xo)x = Q arg min Toxo TIX1 px Xo xo
(17)
and
Ai(x))a = 2 arg min Io + xixi - 11 X, = x1
(18)
Hence, C(p, A1) (xxo,x))<4 (2TOTI||X, 11 ming Io + TT 12
B.3. Proof of Theorem 4.1
Theorem 4.1. Minimizing FCA-C objective Č(Q, W, p)) with the corresponding assignment function defined in eq. (6), equivalent to minimizing An; A1) subject (Ao.Ar A..
Proof of Theorem 4.1. It suffices to show the followings: A and B.
A. For given Q, W.p. let Ao and Ai be the constructed assignment functions, defined in eq. (6). Then, we have Č(Q, W. μ) = Ao, A1) and (Ag, e A.
B. (i) For given a and (Ap, E Ac, there exist Q and W s.t. ((Q,W, Ao,)..
18

---

Fair Clustering via Alignment
Proof A.A. For given Q W. ,e, construct the assignment functions in eq. (6). In other words, we define
Ao(xn): IPi (farg ming (xo; X1) ue 1|2 = k. (xo. X1) W())
+1 (argming: ming |xxo - per 1|2 k) (f X1) E WJ),
and the assignment function Ai defined similarly. Then, we have Č(Q, (1 C(u, Ao, A1) by its definition.
Furthermore,
EoAo(X): (X))
C1 arg min T (Xo, X1) - -u-112 = X1) we)
E, arg min | (Xo. (Xo. X1) 1x: k. (Xo, X1) ) E We)
+ Eo ((X,, x1) E W) (arg min |X 1x:111 = k))
- EE ((X,, X1) E W) (arg min [X u = k))
K
EI ((x,,)) E W) ((rg min
[Xo 1ww k))
(19)
k
R.Q0 ((x,: 1)) W) 1 (arg min
|X1 11x.11 = k)
k'
Ex. x, 1( X,) W) (arg
IXo 112 = k-) 1 (arg min |X Mw 1w =k)
k'
K
[[arg min Xo - -xx = k:) I(rgg [X - 1 = k) X1) E ww)
Ex
k'
1(Xx,, x1) em)
Xx
Sea
which implies (An, A1) E Ag.
Proof of B.
For each & E [K], let 6e (X)) 6. (1. (X)))) Then, ExAo(X); = (X)x for all & e [K]. Define A,(X) = I A5(X)x Note that
We decompose A.(.). -o(-)x AA()),, where Ās(-)x
E.A,()) K+1 E.
Now, for given μu, we define a probability measure on No x X1 by
Ao (x (x1)a po(())p) (xi) +
(x()))<4414 (1
Qidxo: dxi (po)
po (x(x)) (xi),
5x
8k+1
where 5K+1 = 1x-m 5g and Po: Pı the densities of Po. P,, respectively.
Note that 6K+1 = x+++ and thus 8k+1 S c. In addition, for given (Xo, x1) Xo x X1, we define binary random variable R(xo, x1) such that
Åo(xo) (x1x))))) (x1))++))++))) (x (x1)
Pr(R(xx, x1)= =1)
Axi1
Q(dxo, dxl/p1) 11)
19

---

Fair Clustering via Alignment
For given X,, let pxx)= pk-, where k* arginin,||x
||x - mu|l². For given (Xo, x1) E Xo X1, let (xx x1) = M
where k' arg mink To + T1X1 1sx 2 Then, it holds that C(Q, R4 S C(U,, A1) where
ČQQ, R) = Eq.a [ X1 2| m + Ti x1 (x x1) R(X,,
+ E
[{ To Xo - (xXo)) |1 + n1 X1 1 (Xx)) | R(Xo: X1)]
= The final mission is to find W C No x di such that R(x,, x1) = [((x)) E W). For this, define (1x,,x1) 2T Xx0 x1ll + ming (xo, x1) - u 1 Let T7 be the sth upper quantile of 17(Xo, X1) and let
W = {(x0, x1) (xx x1) > n-
(20)
Then, we can find W S V such that Č(Q n) - Č(Q, R. 14) and Q(W) = E (see Remark B.I below), which completes the proof.
Remark B.1 (The case when the densities do not exist). When the distribution of (Xo, X1) is strictly increasing, we have ((W) = If not, we can find W such that W 3 X1) nxxx, x1) 2 c} with Q(W) when Q has its density.
When Q is discrete, the situation is tricky. When no = n1, the measure Q minimizing C(Q, W. (1) has masses 1 1/mo on no many pairs of (xo, X1) among Ng x Xi. In this case, whenever noe is an integer, we can find W such that ((W) = E.
Otherwise, we could consider a random assignment. Let F,, be the distribution of (X., X1). Suppose that F, has a jump at Me- In that case, Q(W) < 8. Let (x]:>f) be the element such that v((x;; xi) = T)- Then, we can let R(x xi) 1 with probability (s Q(W)) / (xjjxi]] R[x,,,)) = for (Xp,Xi E W and [(xx,,x)) 0 for (Xo: X1) (WU (x6 x The current FCA-C algorithm can be modified easily for this random assignment.
B.4. Proof of Proposition 4.2
Proposition 4.2. For any assignment function (Ao, E Ags, we have
Σ Ex,ex, Ao(xi)
no
max kE[K]
S
(21)
Ex,ex, Ex Al (x;))
n1
where c no maX (xA,
Proof of Proposition 4.2. On the other hand, by the definition of A any (Ap, A1) A satisfies
1 Σ Ai(x))a Se,
Ao(x;)
no
ni
1=
x.ENo
X,EXi
which implies
1 Σ
- 1 Σ A1(x))
Ao(xi)
=IEoAo - (X)x Se
11 X
n1
EyEdi
for all & E [K]. Then, we have
Exer Ao(xi)
n00
Σx Ao(x;)a/mm
710
(x))
ExEx, Ax(x))
11
11
Ex,exi (x;))a²/11
11
E (X)x
(22)
110
110
Io (X);
E,Ai
c, ni (X)x
n1 E, (X)x
for all le E [K]. Letting c:= no maX (X),
concludes the proof.
20

---

Fair Clustering via Alignment
B.5. Proof of Theorem 4.3
We establish the approximation guarantee of our proposed algorithm: The cost of the solution obtained by our FCA-C algorithm in Section 4.2 is at most T + 2 times of the cost of the global optimal fair clustering solution (where is the approximation error of the algorithm used for finding initial cluster centers without the fairness constraint), with additional violation of O(e). In other words, for a given fairness level e, FCA-C has an approximation error of r + 2 with an additional violation of (ss).
First, for a given fairness level e, we define several notations to be used as follows.
1 A .
A the solution of FCA-C algorithm for faimess level E, given initial cluster centers obtained by т- approximation algorithm for K-means clustering.
j.. Ao Å₁: the optimal fair clustering solution of Al. C(u,, Ao: A1) subject to (A) E Ac, for given fairness level
nr, Ag: Af: the (approximated) clustering solution, given a r-approximation algorithm for (standard) K-means clustering.
Then, can prove Theorem B.2 below, which is formal version of Theorem 4.3, showing the approximation error of FCA-C algorithm.
Theorem B.2 (A formal version of Theorem 4.3). Suppose that supxex ||x| S for some R > O. Given initial cluster centers obtained by a a--approximation algorithm, FCA-C returns a (T + 2) apprrxximtte solution with a violation 3Re for optimal fair clustering, i.e., C(uA,A AA - ( 2)C Ao, Ai) + 3Rs.
Proof of Theorem B.2. Let Q W" arg ming,w Č(Q, C M)), and Ai are the assignment functions corresponding to Q and W
suffices to show the following two claims:
1. (Claim A): Given initial cluster centers obtained by a r-approximation algorithm for K-means clustering, we have Cuu², Ab, Ab) S (r + (j, Ai).
2. (Claim By: There exist Q', W such that C(, s (6, 3Rs, where Aò and Ai are the fair assignment functions corresponding Q* and W
Then, by combining Claim A and B, we have that C(u AA, Ai) S (r (), + 3Re. Note that Ai and Ai are the feasible solution of FCA-C, while A', and A₁ are the global optimal fair assignment function given μº, Consequently, can clearly get the same approximation error for (MA AA), by iterating the process (finding new cluster centers minimizing the cost and updating the assignment functions), which completes the proof. See Remark B.3 for details.
Proof of Claim A: Let C* = min Ao C(u,, A1) represent the global optimal clustering cost without fairness constraint. Then, we have C(u², Ag, Ai) I TC*
We show that for given initial cluster centers nº, there exist A and At that satisfy the following conditions: (i) (At, .T) E Ag, (ii) C(p,, A AA) S ( + ( Ao A,). and (iii) C(pe, .6. A,,A1) < C(p², A .A), where Ab, Ai are the fair assignment functions corresponding to Q W = arg minq.w w C(Q, W.
(i) Recall that j { and f { For all 1 E [K], define the set of nearest neighbors of ng as
N ((p)) == (āx E jı arg aagginngge en 1|ã - 11 ml). For x E X, we define A (x)x := Emer A. (x))..
Then, A also becomes an assignment function since Σ AJ (x) = for all x E X.
Since A1) E Ae, we have the fact that Σk obtain
1 Σ An(x;) 1 A < s. Therefore, we
-k=1
ng
K
(x:)a
1 n1
Σ
AF
(x))
=
Σ
Σ
L An
1 1
A (x))
no ==1
ni 1=1
k=1
((())
21

---

Fair Clustering via Alignment
K
K Σ
1 no
Ao(x))
1 (x(x)
Σ
=
Ax(x))
R1 Σ A (x;))
Se.
n1 j=1
1=1 Kepp (N(
k==1
where the last equality holds because U (N(A)) {K' = {KT -
Thus, the condition (i) is satisfied.
iii For given x X, let px(x)= arg mgea ||x - be the initial cluster center closest to x. We then have:
K
K
- 1211= = (x)x
Σ
Σ
1x 2
k= Mi EN(g)
(x)x) (1|x- - pox + 11 12ll?)
Jm ke EN(
(x)x (1|x- ix 112 11pp (x(3)11
(23)
K
E
Ax(x) (2/ mw 11? + ||x - 1x(x))11)
k=
M EN(E)
K
K
2
1 Σ Ax(x)
k=11
km 1 k km (N()
2
((xx))x|1-xx-111 1x(2)
k=1
Summing over all x and dividing by n, we obtain:
ChH At) 5 Ao A.. Σ
Cle A0 AP) min mxin/x - = An, Ai)
XEX
< 200 + T 2C Ad) + TC
which concludes (ii).
Ao. (ii) is clear that C(H², A/: S C(p2, At,AA since Ao and Ai are the minimizers of Co,, A1) subject to (Ao, A1) E Ag given μ 1º (by Theorem 4.1). Thus, the condition (iii) is satisfied.
Let p/g == Σ.= A / Ei= (x;xx:) which is the minimizer of mina Ah, given Ah and A₁. Then, it clear that C(p', Ab, Ai) < C(u Ab Ai) s (r () Au, A1).
Proof of Claim B: Note that we can rewrite
C(Q.W. Ex.. 8 (FCA cost(Xo, X1,H1) Ex. 2 (FCA cost (Xo, X1, ()) K K-means cost(Xo, X1, 1)) ((xo, X1) W),
(24)
where FCA cos X1, 11) = (2 Xo= - x1 + ming [X,, X1) u 112) and K-means cost(Xo, X1,14) = ming Xxo - m=ll2) + min: (m X, - m)))?)) which are defined in eq. (5).
(i): For given o define Q* as the solution of mingeg Ex.,x.-O(FE cost(Xo, X1, (1,,))), which can be found by solving the Kantorovich problem. Then, we have Ex.xx. (FCA cost(Xo, X,, vT)) S Ex.xx-~ (FCA cost(Xo. cost(Xo.X.,,I))
(ii): Let (Xo, x1) = FCA co, x1, - K-means cost(xo Xo, x1, 11) and ne be the eth upper quantile. Define
22

---

Fair Clustering via Alignment
W (1x 2o x 21 (x0x x1) > )e Then, using (i), We have
C(Q', "M H9) - C(Q" 0, u² = Ex..X (FCA-cost(Xo, X1,
= =Bx,x,00 (FCA-Cost(X,, no X1, 14))
sup a.W.
E (FCA cost X X1, 1I)
K-means cost(Xo: X1, (I) ((X,, X1) E W)
+ sup Q.W:J(W)
Ex. (FCA cost(X,, Xo, X1, 11) K-means cost(Xo. X1, 11)1 ((oo, X1) E W)
I XI FCA-cost(X., X1, (4)
ExoXXI (FCA cost X1, 1)) K-means (ost X1, U)) ((Xo; X1) E EW)
+ sup Q.W:
ExoXXI (FCA cost(Xo, X1, K-means cost(X,, XI) ((Xo, (X),XX)) E W)
-CC' W4
+ sup Q.W:QWWSEC
Exo.Xin (FCA (FCA cost(Xu, X1, 14) - K-means cost(X., 11. ((Xo, (X),XI) E W).
(25)
(iii) The last term of the right-hand-side can be bounded as follows:
First, let p (x) == arg min ggep ||x - mlll for x E X' and μ xI) == arg min mgems (xo, - uell for
(xo, x1) E No x X1. Then, V(xo, x1) E Xo x Xi, it holds that
FCA cost(xo, x1, 11 K-means cost (xo, X1, )4)
2 ||x0 - X1 112 + (xu, x1) - (xx: x1 )11 (Tollxx - (xx0)1) (TT1|X² - 1² (x1))11)
S 2 ||x0 - x1|2 1| + | x1) - 1² x((x))]² - (Tolix - 11 (xx))l²) - (xı - (x11)1)
I 2 ||x0 - -x1| Too|x 11 (x0))11 + T πi||x1 - 14 (xx))l
(Tolixo- xxxx))1 (A1 [x] 1 (x1)
(26)
2 ||x0 - x1||" Tı (1|x1 - ~x((xo)) )² ||x| - 1² (x1)11
S 2 ||x0 - x1||² 2| + Tı||i|- - ->x(x))11
-x1ll
1 1 |x0 11 ||x v (xo)1l s 2 2 2R 3R
Hence, we conclude that
sup (:Q(())
Ex, a (FCA cost(Xo, X1, - K-means cost(Xo, X1, 1)) ((X,, X1) E W)
S3R sup Q.w:Q(W)=
Ex,.XI<a(1 ((Xo, X1) E W)) = 3RQ(W) 3Re.
Finally, combining (ii) and (iii), we have Č(Q', W S Č(Q', ,', + 3Re, which implies C(u Ai) S C(u², Abe AD) 3R, where Až and Aj are the fair assignment functions corresponding to Q* and W
Remark B.3. Finally, FCA-C algorithm iterates the above process. Using FCA-C, we find Aا and Af. which minimizes the cost given μı, where 1// AG. Again, let 14 n (x Ei A (x)+.. which is the minimizer of min, Crr,, AH, A() given A" and AV.
:= 1 (xxx))xx;/ En A'xx,),, i.e., the minimizer of min, C(u,, Ai) given Ab and
This iteration process results in the following inequality: C(u", "Ta""A""AA" Al)) I C(p', AT) < C(r', A1) S (r + (), Ao, A,) + 3Re. Hence, iterating this process until convergence guarantees the approximation error + 2 with additional violation of 3Rs, which concludes that C , A S (T + 2) Ao, + 3Re.
23

---

Fair Clustering via Alignment
C. Experiments
C.1. Datasets
The three datasets used in our experiments can be found the UCI Machine Learning Repository".
ADULT dataset (Becker Kohavi, 1996) can be downloaded from
adult. We use continuous variables (age, Enlwgt. educat in sapital-gain and hours hours-per-week)
The total sample size is 32,561. The sample size for S and S (resp. female and male) are 10,771 and 21,790, respectively.
BANK dataset (Moro et al., 2012) can be downloaded from https: /ttp:a/ai.ee..........eaaaaaaaaa
Markttarnnnngggg We use 6 continuous variables (age, duration, euribar3m, nr nr. employed, cons. pesss.rii...... idxx and campaign). The total sample size is 41,108. The sample size for S = 0 and $ = (resp. not married and married) are 16,180 and 24,928, respectively.
CeNSUS dataset (Meek et al.) can be downloaded from
US+Gensus+Datat (1990). We use 66 continuous variables (dAncstryl,, diaas iclass, dDepart, iDisabll, iDisabl2, iEnglish, iFeb55, iFertil, dHispanic, dHour89, dHours, iImmigr, dIncomel, dIncome2, dIncome3, dIncome4, dIncome5, dIncome6, dIncome7, dIncome8, dIndustry, iKorean, iLangl. iLocking, iKarital, iMay75880, iMeans, iMilitary, iMobility, iMobillim, dCccup, i0thrserv, iPerscare, dPOB, dPoverty, dPwgt1, iRagechld, dRearning, iRelat1, iRelat2, iRemplpar, iRiders, iRlabor, iRownchld, dRpincome, iRPOB, iRrelchid, iRspouse, iRvetserv, iSchool, iSept80, iSubfami, iSubfam2, iImpabent, dTravtime, iVietnam, dWeek89, iWork89, iWorklwk, I, iYearsch, iYearwrk, and dYrsserv). We subsample 20,000 instances, as done in Chierichetti al. (2017); Bera et (2019); Esmaeili et (2021). The sample size for S and S (not married and married, respectively) 9,844 and 10,156 respectively.
Note that, for each dataset, studies, e.g., Backurs al. (2019); Bera et al. (2019); Esmaeili et al. (2021); Ziko et al. (2021), to name few. Particularly, the features we consider in this paper are the same those selected in a baseline method VFC (Ziko et al., 2021). The variables of all datasets are scaled with zero mean and unit variance.
only the continuous (numerical) variables introduced above, consistent with previous
C.2. Implementation details
C.2.1. COMPUTING RESOURCES
The computation is performed on several Intel Xeon Silver CPU cores and an additional RTX 4090 GPU processor.
C.2.2. PROPOSED ALGORITHMS
We use the POT library (Flamary et al., 2021) to find the optimal joint distribution Q (i.e., I). For updating the cluster centers, we adopt the K-means++ algorithm (Arthur & Vassilvitskii, 2007) from the implementation of scikit teiittleaamn package Pedregosa al. (2011). The iterative process of updating the cluster centers and the joint distribution is run for 100 iterations, with the result where Cost minimized being selected.
FCA
FCA-C To control Bal, we vary e, i.c., the size of W. The value of s sweeped in increments of 0.05, ranging from 0.1 0.9. We also use similar partitioning technique in Section 4.3 for FCA-C with m 2048. For stability, the first iteration step, find W based fixed cluster centers μ., initialized using the K-means++ algorithm.
C.2.3. BASELINE ALGORITHMS
Scalable Fair Clustering (SFC) (Backurs et al., 2019) We directly use the official source code of SFC, available on the authors' GitHub SFC provides a fast and scalable algorithm for fairlet decomposition, which builds the fairlets in nearly
hhttps://archiv ve. iis..uu auci.edu/datasee hhttps://gi thub. com/tataaaaooooo htmm//tlwagger/aaaaa fttts//rrrrroottringnggoo
24

---

Fair Clustering via Alignment
linear time. The given data are first embedded a tree structure (hierarchically well-separated tree; HST) using probabilistic metric embedding, where seek for optimal edges (as well as their nodes) to be activated that satisfy Bal Ra Then, the linked nodes are then aggregated as fairlet. This process can build fairlets in nearly linear time while minimizing the cost of building them. After building these fairlets using SFC, we apply the standard K K-means algorithm on the fairlet space (i.e., the set of representatives of the obtained fairlets).
Fair Clustering under a Bounded Cost (FCBC) (Esmacili et al., 2021) We use the official source code of FCBC, available on the authors' GitHub". FCBC maximizes Bal under a cost constraint, where the cost constraint is defined by the Price of Fairness (PoF) "cost of fair clustering (the solution) / cost of standard clustering'. However, since the authors mentioned the constrained optimization problem is NP-hard, they reduced the problem to a post-processing approach (i.e.. fairly assigning data under the cost constraint, with pre-specified centers opened by standard clustering algorithm). We set the value of PoF to 1.2 to achieve Bal ~ Bal".
Fair Round-Robin Algorithm for Clustering (FRAC) (Gupta et al., 2023) We directly follow the official source code of FRAC, available on the authors' GitHub FRAC provides an lo-loop post-processing approach to fairly assign data from each protected group to given cluster centers found by a standard clustering algorithm. In other words, the fair assignment problem is solved at each iteration of standard clustering algorithm.
Variational Fair Clustering (VFC) (Ziko et al., 2021) We use the official source code of VFC, available on the authors'
GitHub". The overall objective of VFC is E Ein, || pa |x2 + X Σ KL ([TO, Ti Ti]l (x)),A((X),, A, (X), where Ả is hyper-parameter to control Bal. A higher À results in higher Bal, with KL - + Bal = 1. We run the code with multiple trials, by varying the values of X. For Table 2, we select the best that achieves the highest Bal and report the corresponding performance for the chosen hyper-parameter, as the authors have done. For Figure 3, we present all the results obtained using the various values of A. Table below provides the values of VFC's hyper-parametert used in our experiments.
[X=(X)= EXx((X)+
Table 5. The hyper- parameters used in VFC for searching clustering with maximum achievable Bal for each dataset. The bold faces are the recommended ones by the authors. The underlined values are the ones we use for maximum achievable Bal.
Datasct
La normalization
||
Hyper parameters
O
{5000, 7000, 9000, 10000. 1 11000, 12000, 13000, 13600, 14200) (5000, 7000, 9000, 10000, 11000, 12000, 1.3000, 15000, 20000, 22000, 23000)
ADULT
X
O
(5000, 6000, 7000, 9000, 10000, 11000, 12000, 12300)
BANK
X
{10000, 12000, 13000, 15000, 17000, 19000, 25200, 26000)
O
{100, 200, 500, 700, 1000, 1500, 2000)
CENSUS
X
Failed
Note that VFC's superior performance over other two well-known FC algorithms from Bera et al. (2019); Kleindessner et al. (2019) was already shown in Ziko et al. (2021), which is why we omit these two methods as baselines in our experiments.
httpss//.ttt.o........r////eaaat gwwo-AAloorrrrgaaaaaaaaaa rness htte::///sttaaal..ooom/////aaa//
25

---

Fair Clustering via Alignment
C.3. Omitted experimental results
C.3.1. PERFORMANCE COMPARISON RESULTS (SECTION 5.2)
Trade-off:: fairness level vs. clustering utility Table 6 presents the comparison results for the trade-off between Bal and Cost without L2 normalization, which is similar to Table 1.
Table Comparison of the trade-off between Hal 1 and Cost on ADULT, BANK, and CENSUS datasets, when data are not T--normalized. We underline Bal values for cases of near pear-perfect fairmess (i.e., Bal Bal") use bold face the lowest Cost value among those cases.
Dataset / Ball
ADuLT / 0.494
BaNK /06649
CeNSUS / 0.969
Without Le normalization
Cost ())
Bal (t)
Cost (4)
Bal (1)
Cost (U)
Bal (1)
Standard (fair-unaware)
1.620
0.206
1.510
0.391
28.809
0.030
FCBC (Esmaeili et al., 2021)
1,851
0.460
2.013
0.610
59.988
0.925
SFC (Backurs al., 2019)
3.399
0.471
3.236
0.622
69.437
0,940
FRAC (Gupta al., 2023)
2.900
0.488
2.716
0.646
38,430
0.962
FCA V
1.875
0.492
1.859
0.647
33,472
0.959
On the other hand, shown in Table 1, FCBC attains slightly lower Cost (0.314) than FCA, whereas FCA yields higher fairness level. To fairly compare the two methods equal Cost, we run FCA-C targeting Cost R 0.314, i.e., the Cost of FCBC. Under this constraint, FCA-C achieves a Balance of 0.473, compared to 0.443 of FCBC, demonstrating that FCA offers a superior trade-off between Bal and Cost.
Table Comparison of FCBC and FCA-C terms trade-off between Bal and Cost on ADULT dataset, when are Lg- normalized, Cost is fixed near 0.314 for fair comparison.
ADULT
Bal 0.494
Cost (4)
Bal (f)
FCBC (Esmaeili al., 2021)
0.314
0.443
FCA-C
0.313
0.473
For our main experiments in Section 5, mainly compare FCA with the scalable fairlet-based method of Backurs et al. (2019). Here, we additionally compare FCA with the original fairlet-based approach introduced by Chierichetti et al. (2017). Table 8 shows that FCA outperforms the fairlet-based method of Chierichetti et al. (2017) as well as SFC.
Table Comparison of Chierichetti et al. (2017), SFC and FCA terms of the trade-off between Bal 1 and Cost on ADULT, BANK, and CENSUS datasets, when data are Lo-ooaaalzed. The bold-faced results indicate the bests.
Dataset / Bal*
ADULT 0.494
BaNk / 0.649
CENSUS 0.969
With La normalization
Cost ())
Bal (f)
Cost (4)
Ba1 (f)
Cost (4)
Bal (t)
Chietichetti al. (2017)
0.507
0.488
0.378
0.639
1.124
0.941
SFC
0.534
0.489
0.410
0.632
1.015
0.937
FCA V
0.328
0.493
0.264
0.645
0.477
0.962
26

---

Fair Clustering via Alignment
Numerical stability Table presents the comparison results of FCA and VFC in terms of numerical stability without La normalization, which is similar to Table 2. In specific, CENSUS dataset without T22 normalization, VFC fails, i.e., it does not achieve higher Bal than the standard clustering for any X. We find that the failure of VFC on CENSUS dataset (without L2 normalization) is due to explosion of an exponential term calculated in its algorithm. There exists an exponential term with respect to the clustering cost in the calculation of the optimal assignment vector in the VFC algorithm, and thus when the clustering cost becomes too large, VFC fails due to an overflow. Note that the input dimension of CENSUS dataset is 66, while those of ADULT and BANK are 5 and 6, respectively. While the clustering cost with L2 normalization is bounded regardless of the dimension, the clustering cost without La normalization proportional to the input dimension. This is why VFC fails only for CENSUS dataset without L2 normalization. In contrast, FCA does not fail at all regardless of the L2 normalization because there is no exponential term in the algorithm, meaning that it is numerically more stable than VFC.
Table Comparison of the two in- processing algorithms, VFC (Ziko et al., 2021) and FCA, in terms of numerical stability when achieving the maximum Bal, ADULT, BANK, and CENSUS datasets without normalization. Bold-faced results the highest values of Ba 1.
Bal (Cost)
Dataset / Bal*
VFC (Ziko et al., 2021)
FCA
ADULT 0..94
0.310 (1.688)
0.493 (1.875)
BANK / 0.649
0.505 (1.549)
0.647 (1.859)
CENSUS / 0.969
Failed
0.959 (33.472)
Control of fairness level We also provide the full results (i.e., Figures and where the data are Tzg-normaiizdd and not Lg-normalized, respectively) showing the trade-off of VFC and FCA-C for various fairness levels, on ADULT, BANK and CENSUS datasets. FCA and VFC show similar trade-offs, while VFC cannot achieve sufficiently high values of Bal (the orange dashed lines are the limit values of balance that VFC can achieve).
Adult
Bank
Census
Standard
Standard
2.10
Standard
0.33
FCA-C
0:5
FCA-C
FCA.C
Cost
0.32
Hol"
Cost
Hail
0:44
0.31
0.43
0.38
*/"
840
3.25
0.30
0.31
0.40
0.90
5.35
5.40
6.55
0353
535
6.00
0.0
0.2
64
6.1
Bal
Bal
Bal
Figure Ball vs. Cost trade-off's on (left) ADULT, (center) BANK and (right) CENSUS datasets. Black square from the standard clustering, orange circle (+) is from VFC, green star (+) is from FCA-C, orange dashed line (--) is the maximum of Bal that VFC can achieve, and blue (-) the maximum achievable balance Ba
Adult (without L2)
Bank (without L2)
Census (without L2)
Standard
Standard
3,00
VFC
110
VFC (failed)
2.05
Cost
1,00
Bai"
Cost
3.55
Cost
22
Bal"
1.75
Standard
30
VFC
155-
HCAE
Bal"
0.3
645
046
0.5
Bal
Bal
Bal
Figure 5, Ba.1 Cost trade-off's (left) ADULT, (center) BANK and (right) CENSUS datasets. Black square is from the standard clustering, orange circle (+) is from VFC, green star (*) is from FCA-C, orange dashed line (- is the maximum of Bal that VFC can achieve, and blue line (-) the maximum achievable halance Bal*. The data T norroaiale
27

---

Fair Clustering via Alignment
Comparison in terms of the silhouette score As measuring Cost alone may fully capture the clustering quality, additionally consider another measure, called the silhouette score. The silhouette score (we abbreviate by Si 1 lhouette) is computed the average of (chear / max dintras dnear) over all data points, where dian denotes the intra-cluster distance and dnear represents the average distance to the nearest neighboring cluster. Notably, the results in Table 10 show that FCA is also superior or competitive to baselines in terms of the silhouette score.
Table 10. Comparison the si hhouette and Bal on ADULT dataset, when the data are Ig-normalized.
Dataset Bal*
ADULT 0.494
With La normalization
Silhouctte (t)
Bal (t)
Standard (fair-unaware)
0.227
0.223
FCBC
0.173
0.443
SFC
0,071
0.489
FRAC
0.156
0.490
FCA v
0.176
0.493
Analysis on an additional dataset We additionally conduct an analysis on CREDITCARD dataset (n 30000) from Yeh Lien (2009), which was also used in Bera et al. (2019): Harb Lam (2020). We directly follow the data preprocessing of Bera et al. (2019). We use gender the sensitive attribute and set K 10. The results provided in Table 11 below, where we can observe that FCA outperforms the baseline methods on CREDITCARD dataset well.
Table 11. Comparison of the Cost and Bal on CREDITCARD dataset, when the data are Lz-nommalized.
Dataset / Ball
CREDITCARD 0.656
With La normalization
Cost ())
Bal (t)
Standard (fair-unaware)
0.392
0.506
FCBC
0,492
0.629
SFC
0.682
0.653
FRAC
0.510
0.649
FCA V
0.402
0.653
28

---

Fair Clustering via Alignment
C.3.2. APPLICABILITY TO VISUAL CLUSTERING (SECTION 5.3)
Settings: datasets, baselines, and measures RMNIST is a mixture of two image digit datasets: the original MNIST and color-reversed version (where black and white are swapped). OFFICE-31 I is mixture of two datasets from two domains (amazon and webcam) with 31 classes. Both datasets are used in state-of-the-art visual FC methods (Li et al., 2020; Zeng et al., 2023).
For the baseline, we consider a state-of-the-art FC method in vision domain called FCMI from Zeng et al. (2023). FCMI learns a fair autoencoder with two additional loss terms: (i) clustering loss on the latent space and (ii) mutual information between latent vector and color. While FCMI is an end-to-end method that learns the fair latent vector and perform clustering on the fair latent space simultaneously, FCA is applied to a pre-trained latent space obtained by learning an autoencoder with the reconstruction loss only. We also report the performances of DFC (Li al., 2020) which the main baseline in the FCMI paper, along with SFC (Backurs et al., 2019) and VFC (Ziko al., 2021), even though these two methods are not specifically designed for the vision domain.
The clustering performance for the two image datasets is evaluated by two classification measures ACC (accuracy calculated based on assigned cluster indices and ground-truth classification labels) and NMI (normalized mutual information between ground-truth label distribution and assigned cluster distribution). which are consistently used in Li et al. (2020); Zeng al. (2023), as datasets involve ground-truth classification labels (e.g.. {0, .,...,9) 9) for RMNIST and the 31 classes for OFFICE-31). The fairnsss level is also evaluated by Bal.
Results Table 12 shows that FCA performs similar to FCMI, which is the state-of-the-art, while outperforming the other baselines with large margins in terms of Bal. Note that SFC, VFC, and FCA are two-step methods, i.e., they find fair clustering on the pre-trained (fair-unaware) latent space, and FCA is the best among those. Furthermore, on the other hand, DFC and FCMI are end-to-end methods so is noteworthy that FCA outperforms DFC and performs similarly to FCMI.
Table 12. Comparison of clustering utility (ACC and NMI) and faimess level (Bal) on two image datascts. 'Standard (fair-umaware) indicates autoencoder + K K-means (Vincent et al., 2010). First-place values are bold, and second-place values are underlined. The performances of the baselines reflects the better results between our re-implementation and the one reported by Zeng et al. (2023).
Dataset / Ba1"
RMNIST / 1.000
||
OFFICE-31 31 0.282
Performance
ACC (t)
NMI (*)
Bai (t)
ACC (f)
NMI (1)
Bal (f)
Standard (fair-unaware)
41.0
52.8
0.000
63.8
66.8
0.192
SFC (Backurs et al., 2019)
51.3
49.1
1.000
61.6
61.2
0.267
VFC (Ziko et al., 2021)
38.1
42.7
0.000
64.8
70.4
0,212
DFC (Li et al., 2020)
49.9
68.9
0.800
69.0
70.9
0.165
FCMI (Zeng al., 2023)
88.4
86.4
0.995
70.0
71.2
0.226
FCA
89.0
79.0
1.000
67.6
70.5
0.270
Further comparison between the fairlet-based method and FCA in visual clustering We compare the fairlet-based method and FCA using OFFICE-31 I dataset, considering (i) not only the overall clustering utility, (ii) but also the similarity of matched features. For clear comparison, from the original dataset, which is imbalanced. That is, we ensure that the number of samples with the same label is equal across the two protected groups (i.e., the two domains). As result, we obtain 795 images from both the amazon and webcam domains. We then find fairlets or apply FCA on this balanced dataset. Note that finding fairlets when ni = nı is equivalent to finding the optimal transport map (Villani, 2008; Chierichetti et al., 2017; Peyré & Cuturi, 2020).
sample balanced subset (with respect to the label and sensitive attribute)
Table 13. Comparison of the fairlet-bases method and FCA. 'Matching cost' is defined by the average distance between two matched features. 'Matching= Label' is defined by average ratio images with the same label being matched. Bold faced values indicate the best performance.
Matching performance
Clustering performance
Matching method
Matching cost
Matching = Label (t)
Cost (L)
ACC (1) | NM (1)
Fairlet-based
0.211 0.241
0.595 0.631
0.278
65.8
71.0
FCA V
0.269
69.3
72.2
29

---

Fair Clustering via Alignment
Table 13 presents the comparison results using various measures, including performance measures with respect matching (the matching cost and how much images with the same label are matched) and clustering (Cost, ACC, and NMT). While the fairlets tend to match more similar features (i.e., the matching cost is lower) expected by the definition of fairlets, FCA exhibits better ability to collect images with same labels into clusters (i.e., lower Cost, higher ACC, and higher NMT). Moreover, visual clustering, matching similar features in the pre-trained latent space does not always guarantee that images with the same label are matched (FCA achieves a higher proportion of matchings where images share the same label compared to fairlets). These results suggest that while fairlets provide optimal matchings in terms feature similarity, however, they may be suboptimal in terms of label similarity and overall clustering utility.
30

---

Fair Clustering via Alignment
C.3.3. ABLATION STUDY: (1) SELECTION THE PARTITION SIZE m (SECTION 5.4)
This section provided empirical evidence for the partitioning technique introduced in Section 4.3. First, Figure indicates that using partition size of around 1000 yields reasonable results. Specifically, using values greater than 1000 shows similar performance compared to those obtained with 1024.
Adult
Bank
Census
6.0
Bal Cost
Bal
Dal Cost
Cost
6464
c.
030
040
03:00 303 be Lue 0g.00 ogann
2c our Loeiing roeznng Hiw
00.09 K031x
no one Ro
log (Partition size)
log (Partition size)
log (Partition size)
Adult (without L2)
Bank (without L2)
Census (without L2)
6.07
Bal Cast
Bal
Bal Cost
Cost
6164
042
295 Me117 105 les
bolne (roting Taaking wil
N9 517
181
Iog 2045
log (Partition size)
log (Partition size)
log (Partition size)
Figure 6. Variations of Cost and Ba with respect to the partition size. (Left, Center, Right) = (ADULT, BANK, CENSUS). (Top, Bottom)
-With La normalization, Without Le normalization.
We further provide the elapsed computation time for various partition sizes, up to using the full dataset. Using m 1024 as the baseline, we calculate the relative computation time (%) for other partition sizes. The comparison, presented in Table 14 below, shows that using m 1024 leads to significant reduction in computation time.
Table 14. Comparison of computation time with different partition sizes, up to using the full dataset. For each partition size and dataset, we provide the averaged relative elapsed time per iteration, when compared to computation time for m 1024.
Partition size m
(Relative) elapsed time per iteration
256
512
1024 v 2048
4096
Full
ADULT (n 32561, d 5)
17%
58%
100%
140%
344%
3,184%
BaNK (n = 41108, d 6)
14%
43%
100%
161 %
288%
3,308%
CENSUS 20000, = 66)
23%
52%
100%
176%
375%
1,064%
Additionally. we observe that computation time is linear in m², as shown in Figure 7 below. This numerical result can support the theoretical computational complexity Onn?² described in Section 4.3. See Table 18 in Appendix C.3.6 for another result showing that the computation time also linear n.
Adult
Bank
Census
Computation time 1.
computaton time
computation time 22
300
Jeer
Squared partition size (m?)
Squared partitio size (m²)
Squared partiion size Im?)
Figure Squared partition size m² vs. Relative computation time. (Left, Center, Right) (ADULT, BANK, CENSUS).
31

---

Fair Clustering via Alignment
C.3.4. ABLATION STUDY: (2) OPTIMIZATION INITIALIZATION CLUSTER CENTERS (SECTION 5.4)
Optimization algorithm of cluster centers algorithm for finding cluster centers.
We analyze how the performance FCA varies depending on the optimization
(i) For the K-means algorithm whose results are reported in the main body, we use the K-means++ initialization (Arthur & Vassilvitskii, 2007) from the implementation of scikit -earn package (Pedregosa et al., 20.1). Note that we use the algorithm of Lloyd (1982) for the K-means algorithm.
(ii) We additionally consider random initialization of cluster centers with Lloyd's algorithm.
(iii) For the gradient-based algorithm, we use Adam optimizer (Kingma Ba, 2014). We a learning rate of 0.005 for CENSUS dataset with 122 normalization, and 0.05 for all other cases. To accelerate convergence, 20 gradient steps of updating the centers are performed per iteration.
Table 15 presents the results comparing these three approaches, showing that FCA is robust to the choice of the optimization algorithm for finding cluster centers. Note that, while the gradient-based algorithm also effective and accurate, requires additional practical considerations such as selections of the learning rate and optimizer. Furthermore, the slight outperformance of K + initialization over random initialization suggests that an efficient initialization algorithm can enhance the final performance of FCA. This is also theoretically examined through the approximation error in Appendix B.5, which depends the approximation error of the standard algorithm for finding cluster centers without fairness constraints. However, since the margins are small, FCA can be considered empirically robust to the initialization.
Table 15. Comparison of performance with respect optimization algorithms for finding cluster centers with L2 normalization (top) and without La normalization (bottom). 'K-mean++*' indicates that the initial centers are set according the K K-means++ initialization the first iteration, then apply the algorithm of Lloyd (1982). "K-means random' indicates that the initial centers are set randomly at the first iteration. then apply the algorithm from Lloyd (1982). 'Gradient-based indicates that the initial centers are set randomly, and the centers are subsequently updated using the Adam optimizer.
Dataset Bal"
ADULT / /0.94
BANK 0.649
CENSUS / /0.969
With La normalization
Cost
Bal
Cost
Bal
Cost
Bal
FCA (K --mans+))
0.328
0.493
0.264
0,645
0.477
0.962
FCA meaas random)
0.331
0.490
0.275
0.646
0.477
0.955
FCA (Gradient-based)
0.339
0.492
0.254
0.640
0.478
0.957
Dataset Bal*
ADULT 0.494
BaNk 0.649
CENSUS 0.969
Without La normalization
Cost
Ba1
Cost
Bal
Cost
Bal
FCA (K (K-means++)
1.875
0.492
1.859
0,647
33.472
0.959
FCA (K (K-means random)
1.882
0.489
1.864
0.644
32.913
0.960
FCA (Gradient-based)
1.943
0.490
1.967
0.646
34.121
0.962
32

---

Fair Clustering via Alignment
Initialization of cluster centers Moreover, we empirically assess the stability of FCA and FCA-C with respect the different initial cluster centers (while keeping the initialization algorithm fixed K K-means++), and compare them with the run each algorithm five times with
standard K K-means++ algorithm. For FCA and the standard K-means++ algorithm, five different random initial centers. For FCA-C, we use five random initial centers for each E E {0.1, 0.15.......... 0.85, 0.9} and compute the averages as well as standard deviations. Then, we divide the standard deviation by average 17 times (corresponding to 17 ES), and take average.
Table 16 below reports the coefficient of variation (= standard deviation + average) of Cost and Bal. The results show that the variations of all the three algorithms are similar, indicating that FCA and FCA-C are stable as the standard K-means++ with respect the choice of initial cluster centers. That is, aligning data (i.e., finding the optimal coupling matrix I' to build fair clustering does not affect the stability of the overall algorithm.
Table 16. Standard deviations divided by averages (i.c., coefficient of variation) with respect to five random different choices of initial centers.
ADULT
BANK
CENSUS Cost
FCA
Cost
Bal
Cost
Bal
Bal
with L2
0.012 0.010
0.001 0.001
0.093 0.081
0.006 0.003
0.004
0.001
without L2
0.006
0.003
ADULT
BaNK
CENSUS
FCA-C
Cost
Bal
Cost
Bal
Cost
Bal
with L2
0.015 0.011
0,001 0.001
0.083 0.088
0.007 0.002
0.011 0.010
0.004
without L2
0.002
ADULT
BANK
CENSUS
K-means++
Cost
Bal
Cost
Bal
Cost
Bal
with L2
0.009 0.011
0.001 0.000
0.078 0.090
0.005
0.008
0.002
without L2
0.004
0.010
0.002
C.3.5. ABLATION STUDY: (3) CONSISTENT OUTPERFORMANCE ACROSS VARIOUS K (SECTION 5.4)
We analyze the impact of K the performance of four FC algorithms (FCBC, SFC. FRAC, and FCA). On ADULT dataset, evaluate the FC algorithms with K (5, 10, 20, 40]. The results presented in Figure 8 below, which show that FCA outperforms existing FC algorithms across all values of K. Specifically, FCA achieves lower values of Cost than baselines for most values of K, while maintaining the highest faimess level: Bal ~ Bal*.
With normalization
Without Lg normalization
FCBC
FCBC
SFC
CA4
SFC
FRAC
FRAC
FCA
FCA
Dal
Dal"
8/2
Figure 8. Performance comparison of FC algorithms in terms of Cost and Bal for K E (5, 20,10000000000 40). (Left two, Right two) = (With La normalization, Without La normalization).
33

---

Fair Clustering via Alignment
C.3.6. ABLATION STUDY: (4) SCALABILITY LARGE-SCALE DATA (SECTION 5.4)
In this section, evaluate the scalability of FCA for larger datasets, while the main experiments in Section are conducted on real datasets with sample sizes of around 20, 000 40, 000. In specifie, apply FCA synthetic dataset with an extremely large sample size (around million).
Large-scale dataset generation We generate a large (n = 10%) synthetic dataset in I&d using J J-component Gaussian mixture, as follows:
1. (Mean vectors) We sample J many d-dimensional vectors mj.j (1,...,JJ) from uniform distribution Uni 20). To ensure diversity, the distance between any two vectors is constrained to be at least 1. These vectors are used as the mean vectors for the Gaussian components.
2. (Covariance matrices) Each jth Gaussian component is assigned a covariance matrix Σ, = =o]I. where oj 3n)
3. (Weights) Component weights, denoted as Φj.j E {I....,J}, are sampled from Dirichlet distribution Dirichlet(a1,......0 for given parameters (1,-..,00 O.J-
4. (Completion) The Gaussian mixture model is completed as Σ/=1 o,N(m.. Σ,). We set J as an even number, and sample data for S from J/2 components and for S 1 from the remaining J/2 components.
J.. The resulting generated dataset contains 320,988 samples for = and 679,012 samples for S 1. The features are then scaled to have zero mean and unit variance. Figure provides a visualization of this synthetically generated dataset.
Using this procedure, we construct a dataset with n = 10 = 2, = 20, and a, = 1, E (J}
= 10
Feature
S
S S-1
Feature 1
Figure 9. The large synthetic dataset generated with n 10,,d= 2, J 20, and a, = 1,V (I.
34

---

Fair Clustering via Alignment
Results We fix the number of clusters K 10. In this analysis, we compare only FCA and VFC, other baselines incur extremely high computational costs for this dataset. Table 17 presents the results, demonstrating that FCA is easily scaled-up and remains favorable FC algorithm for this large-scale dataset. That is, FCA successfully achieves near-perfect fairness (i.e., Bal 0.472 x 0.473). In contrast, VFC fails to achieve pear-perfect faimess, with a limit of Ba 0.1 14. Meanwhile, FCA-C achieves a lower Cost than VFC (0.107 < 0.111), while attaining the maximum achievable Ba l for VFC (~ 0.114).
Table 17. Comparison of Cost and Bal between FCA (or FCA-C) and VFC the large synthetic datasct in Figure 9.
Bal* = 0.473
Cost ())
Bal (f)
Standard (fair-unaware) VFC (Ziko et al., 2021) (A = 51000)
0.058
0.000
0.111
0.114
FCA-C (e 0.65) v
0.107
0.115
FCA V
0.669
0.472
We further analyze the computation times of FCA on four datasets with different ns, including this large-scale dataset. Table 18 shows that the computation time scales linearly with n (i.e., Average time / r is nearly constant). This observation aligns with our discussion on the computational complexity of ((mm²) when applying the partitioning technique with a fixed m = 1024 (see Section 4.3). These results can further highlight the empirical efficiency of the partitioning technique.
Table 18. Comparison of total computation times (scconds) of FCA, on four different datasets with different ns. The reported results are averages and standard deviations, based on five runs.
ADULT
BANK
CENSUS
Large synthetic (Figure 9)
Partition size
1024
1024
1024
1024
32,561
41,108
20,000
1,000,000
Average time (Standard deviation)
56.7 (3.9)
73.1 (7.8)
32.2 (5.4)
1410.1 (115.8)
Average time / n
1.7 x 10-3 3
1.8 x 10
1.6 x 10-3
1.4 x 10-3
C.3.7. ABLATION STUDY: (5) LINEAR PROGRAM VS. SINKHORN FOR OPTIMIZING Q (SECTION 5.4)
We evaluate an alternative algorithm for finding the coupling matrix I. Specifically, the Sinkhorn algorithm of Cuturi (2013) optimizes C + ent where C is the cost matrix defined in Phase 1 of Section 4.1, À is regularization parameter, and en) denotes the entropy of T. Note that, as À increases, I approaches a uniform matrix. It is well-known that the Sinkhorn algorithm generally yields a more relaxed solution with reduced runtime compared to solving the Kantorovich problem via linear programming.
We compare (i) the original FCA (using linear programming) and (ii) FCA with the Sinkhorn algorithm for (0.01, 0.1, 1.0). Table 19 shows the results, suggesting: (i) A small regularization (A = 0.01) achieves performance comparable to linear programming with a slight runtime reduction (= 2%). (ii) A large regularization (A = 1.0) significantly degrades performance while reducing runtime (= 10%). Overall, careful tuning of À is critical when using the Sinkhorn algorithm, while the runtime reduction may not be significant in practice. Therefore, we recommend solving the linear program for FCA.
Table 19, Comparison of using the Sinkhorn algorithm and solving the linear program, terms of Cost, Bal, and runtime per iteration.
ADULT
Bal 0.494
Cost (L)
Bal (1)
Runtime / iteration (sec)
FCA (Sinkhorn, À 1.0)
0,350
0.271
4.98
FCA (Sinkhorn, 0.11)
0.315
0.463
5.12
FCA (Sinkhorn. À = 0.01)
0.330
0.491
5.55
FCA (Linear program)
0.328
0.493
5.67
35

---

Fair Clustering via Alignment
C.3.8. COMPARISONS OF COMPUTATION TIME
FCA versus FCA-C We compare the computation times of FCA and FCA-C, as FCA-C technically involves additional step of optimizing W. Table 20 below shows that while FCA-C requires slightly more computation time than FCA, the increase is not substantial (a maximum of 3.7%).
Table 20. Comparison of computation times (seconds) FCA and FCA-C per each iteration. The averages and standard deviations are calculated based on five runs. The data are Iz-normalized and the hatch size is fixed as 1024.
Average (Standard deviation)
ADULT
BANK
CENSUS
FCA
5.67 (0.39)
7.31 (0.78)
16.10 (2.70)
FCA-C
5.72 (0.47)
7.58 (0.32)
16.46 (1.23)
Increase (FCA-C/RCA)
0.5%
3.7% 1
2.2% f
FCA versus SFC We here additionally consider two more scenarios to compare FCA and SFC. In this analysis, the data are Ln-normalized and the batch size is fixed as 1024 for FCA. Note that FCA consists of an outer iteration (updating the cluster centers and joint distribution alternately), and an inner iteration when applying the K-means algorithm the aligned space.
1. We compare the number of iterations until convergence. For SFC, we calculate the number of iterations in the K-means algorithm (after finding fairlets). For FCA, we calculate the sum of the number of iterations (inner iteration) in the K -means algorithm for each outer iteration (updating the cluster centers and joint distribution). In this analysis, note that report the elapsed time for FCA with 10 iterations of the outer iteration, because the performance of FCA with 10 iterations of the outer iteration is not significantly different from FCA with 100 iterations of the outer iteration.
As result, SFC requires smaller number of iterations, compared to FCA (see Table 21), primarily because FCA involves the outer iterations. On the other hand, in FCA, the number of total iterations is almost linear with respect to the number of iterations in each inner loop.
Table 21. Comparison of computational costs between FCA and SFC: the total number of iterations the standard K K-means algorithm in SFC and FCA.
Total number of iterations
ADULT
BaNK
CENSUS
SFC (Backurs et al., 2019)
15
10
32
FCA
57
110
93
2. further analyze whether applying an early-stopping to FCA can maintain reasonable performance, we conduct an additional experiment: we fix the number of K K-means iterations to I per outer iteration of FCA, then perform a total of 10 outer iterations. With this setup, the total number of iterations for FCA becomes 10, which is comparable to smaller than that of SFC (15 for Adult, 10 for Bank, and 32 for Census dataset, as shown in Table 21). We observe that the performance of FCA with this early-stopping is slightly worse than the original FCA (where the K-means algorithm runs until convergence), but it still outperforms SFC (see Table 22). However, this carly-stopping approach would be not recommended, at least for the datasets used in our experiments. This is because running the K K-means algorithm takes less than a second or a few seconds, while the computation of finding the joint distribution dominates the overall runtime. Additionally, the original FCA slightly outperforms the early-stopped version with only 10 iterations.
Table 22, Performance comparison of SFC, FCA with a total of 10 iterations, and the original FCA (updating until convergence). The data are not noromazll.
Dataset / Bal*
ADULT / 0.494
BaNk / 0.649
CENSUS / 0.969
Performance
|| Cost (L)
Bal (t)
Cost (4)
Bal (t)
Cost (L)
Bal (1)
SFC (Backurs et al., 2019)
3.399
0.471
3.236
0.622
69.437
0.940
FCA (total 10 iterations)
1.923
0.489
1.992
0.644
33.967
0.955
PCA (original)
1.875
0.492
1.859
0.647
33.472
0.959
36

---

Fair Clustering via Alignment
C.3.9. COMPARISON OF FCA AND SFC BASED K-MEDIAN CLUSTERING COST
As SFC originally designed for the K-median clustering objective, we compare FCA and SFC based the K-median clustering cost (i.e., L, cost) for more fair comparison. In specific, FCA for K K-median clustering cost is modified as follows: (i) The Lg norm in eq. (3) is replaced by the L1 norm. (ii) The cluster centers are found by minimizing the L1 distance, as we discuss in Appendix A.4.
The results are presented in Table 23, which shows that FCA still outperforms SFC. It implies that the fairlet-based method still may not always find the most effective matching in view of clustering utility (cost), even when the given clustering objective more suited to fairlet-based approaches (e.g., L1 norm) is considered.
Let Costi (x.))D (*((x,)]l be the K-median clustering cost.
Table 23, Comparison of Costi and Bal of FCA and SFC. The data are not Lz-normalized.
Dataset Bal*
||
ADULT 0.494
BaNk 0.649
CENSUS 0.969
Performance
|| Cost1 (4)
Bal (1)
Costi (1)
Bal (1)
Costi (4)
Bal (1)
Standard (fair-unaware)
1.788
0.206
1.989
0.391
21.402
0.030
SFC (Backurs et al., 2019)
2.979
0.471
3.056
0.622
29.597
0.940
FCA
2.032
0.492
2.383
0.647
22.927
0.959
37


Reviews:
[{"review_id": "7oBaENMlpP", "reviewer": "Reviewer_1gG2", "summary": "The paper is focused on fair clustering. In particular, it suggests a new method based on decomposing the clustering cost which claims to have higher flexibility than prior methods in trading the clustering cost and fairness violations. Theoretical analysis and experiments comparing to baselines are conducted to prove these claims.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*To reviewer 1gG2: We sincerely appreciate your review and the opportunity to improve our work. Please refer to our point-by-point responses below.*\n\n------\n### Claims And Evidence\n> 1: I don't find ...\n- First, we would like to highlight our main contributions:\n    - A novel reformulation of the fair clustering objective function using the matching map (Section 3).\n    - Our method guarantees finding a matching map that provides a (local) optimal fair clustering (Theorems 3.1 and 3.3).\n- For the theoretical aspect, please see our response to 'Weaknesses' below, where we suggest that **our proposed algorithm is competitive with existing methods in terms of approximation rate**.\n- For discussion on the experimental aspect, please see our response to 'Experimental Designs Or Analyses' below, which emphasizes **the empirical superiority of our proposed algorithm**.\n\n------\n### Experimental Designs Or Analyses\n> 1: The authors can clarify this ...\n- The main contribution of our work is the development of **a numerically stable in-processing fair clustering algorithm**.\nWhile in-processing algorithms such as VFC require difficult regularization parameter tuning,\n**FCA does not have any regularization, guaranteeing a (local) optimal solution without tuning** (Theorems 3.1 and 3.3).\nFor example, FCA achieves near-perfect fairness and is more robust to data pre-processing than VFC (Section 5.2 and Appendix C.3.1).\n- As expected, FCA significantly outperforms the fairlet-based pre-processing algorithm SFC: achieving nearly 40% lower cost on average and higher fairness (Table 1 in Section 5.2).\n- Surprisingly, FCA performs even better on visual clustering tasks, competing with two image-specific algorithms and dominating SFC and VFC (Table 3 in Section 5.3).\n\n> 2: Further, some ...\n- Please see our response to 'Weaknesses-3' below.\n\n> 3: Also, in Table 1 ...\n- Although FCBC achieves a lower cost than FCA, it is less fair (i.e., lower balance).\n**Table 1 compares the costs at the highest fairness levels each algorithm can achieve**.\nFCBC achieves a lower cost because the highest fairness level it can achieve is lower than that of FCA.\n- To compare fairly, we obtained a fair clustering using FCA-C with a cost of 0.313 (similar to the cost of FCBC, 0.314).\nThe table below shows FCA-C achieves a higher balance (0.473 vs. 0.443), suggesting FCA offers a better trade-off than FCBC.\nThis result will be added to Appendix C.3.1.\n\n    | Bal* = 0.494 | Cost (↓) | Bal (↑) |\n    |:-:|:----:|:---:|\n    | FCBC| 0.314  | 0.443 |\n    | FCA-C ✓  | 0.313  | **0.473** |\n\n------\n### Relation To Broader Scientific Literature\n> 1: Although greater connection ...\n- We appreciate the suggestion.\nIn fact, we already mentioned the two methods in Section 1 and Appendix C.2.3.\nExperimentally, FCA outperforms VFC and FCBC (Tables 1, 2, 5, and 6; Figures 4 and 5).\n\n------\n### Weaknesses\n> 1: the main issue ...\n- Our theoretical bound in Theorem 4.3 is not claimed to be the sharpest one, but is to claim that FCA is not much worse than the global optimal fair clustering.\nThe main advantages of FCA include (i) greater numerical stability than an in-processing method VFC (Tables 2 and 6; Figures 3–5) and (ii) empirical superiority over post-processing methods (Tables 1 and 5).\n- A detailed version of Theorem 4.3 is in **Theorem B.3**:\n**FCA-C provides a $(\\tau+2)$-approximate solution with a violation $3R\\epsilon$, where $R$ is a bound on the data norm ($\\sup_{\\mathbf{x} \\in \\mathcal{X}} \\Vert \\mathbf{x} \\Vert^{2} \\le R$).**\n- **A comparison of the detailed approximation rate** with several existing methods:\n    - Bera et al. (2019) achieved a $(\\tau + 2)$-approximation and a violation $3.$\n    **FCA-C provides the same approximation rate of $\\tau + 2,$ but can attain a smaller violation** when $R = 1,$ as $\\epsilon \\in [0, 1].$\n    - Schmidt et al. (2018) provided a **$(5.5\\tau + 1)$-approximation, which is worse than $\\tau + 2$** for $\\tau > 2/9,$ e.g., $\\tau = 8(\\log K) + 2$ for the K-means++ algorithm.\n    - We will include this discussion following Theorem 4.3 in the camera-ready version.\n    - (References) Schmidt et al. (2018): Fair Coresets and Streaming Algorithms for Fair k-means.\n- (Definition of $\\epsilon$)\n**Please see our response to 'Questions'-3 for Reviewer AM68 due to space limitation.**\n\n> 2: lines (184-187) ...\n- The term 'suboptimal' in Remark 3.2 is used **not because the clustering problem is NP-hard**, but because our method guarantees finding a matching map providing a (local) optimal fair clustering (Theorems 3.1 and 3.3), whereas the matching map of the fairlet-based methods do not offer this guarantee.\n\n> 3: the paper assumes that ...\n- **Please see our response to 'Weaknesses'-3 for Reviewer 4J8b due to space limitation.**\n\n> 4: (Minor) presentation ...\n- Thank you for your careful review.\n(1) Remark B.1 will be moved to Section 3.1 and (2) the boxes will be replaced by algorithm expressions, in the camera-ready version.", "claims_and_evidence": "I don't find the claims convincing. Convincing evidence would be through a theorem with superior guarantees in comparison to prior work. Or experiments where the results are much better.", "methods_and_evaluation_criteria": "Yes. Theorems and experiments are valid ways to establish guarantees. The issue is that the arguments in both are not strong.", "theoretical_claims": "I did not verify the correctness of any proofs", "experimental_designs_or_analyses": "-The authors can clarify this, but it does not seem that the performance of the algorithm is really much better than existing baselines. Further, some the baselines work for many groups instead of just two as done in this paper. Also, in Table 1 for Adult doesn't FCBC have a smaller cost?", "relation_to_broader_scientific_literature": "Prior work is well-cited. Although greater connection to Ziko et al and Esmaeili at al would be good since both trade-off clustering cost and fairness.", "essential_references_not_discussed": "Essential References are discussed.", "other_strengths_and_weaknesses": "### Strengths:\n\n-the objective of the paper is interesting. \n\n### Weaknesses:\n\n-the main issue I think is that this is not the first paper to trade-off the clustering cost and fairness. While some claims are made that prior work follows an \"in-processing\" or \"post-processing\" approach. The issue is that the paper does not directly establish superior performance.  For example, in Theorem 4.3 what is \\epsilon? Further O(\\tau) is not sufficient, what is the exact constants hidden in the O(.) notion. Prior work was specific in including the factors. How can we be convinced that this is a better algorithm if the approximation factors are not better, based on the current presentation since they are not given they may even be worse. For the experiments, please my points above on experiments above.  \n\nMore points on weaknesses:\n\n-lines (184-187) claim that previous methods are sub-optimal, but that has to be the case since the problem is NP-hard. Even this method is sub-optimal as otherwise it would be solving an NP-hard problem exactly.  \n\n-the paper assumes that there are only two groups which is a weakness in comparison to prior algorithms that can handle an arbitrary number of groups.\n\n### Minor Points:\n\n-presentation can be improved by:\n     1-not referring to Remark B.1 on the appendix and maybe including the main intuition in the text.  \n     2-finding another way instead of the boxes on page 5 which are very heavy in text", "other_comments_or_suggestions": "See weaknesses above.", "questions_for_authors": "See weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1tDBc1mLyd", "reviewer": "Reviewer_AM68", "summary": "In group fair clustering, a clustering objective is optimized in light of a group fairness constraint. If each data point is assigned some class, we require the proportions of these classes in each cluster to be the same as, or close to, their proportions out of the total dataset.\n\nThis work considers the problem of group fair clustering using in-processing algorithms to simultaneously find a fair alignment between points and a good k-means clustering. They propose an algorithm which uses an alignment, or a joint probability distribution over points of two different classes, together with a select set of centers to design an objective that optimizes both at the same time. While either the alignment or the set of centers is fixed, the other is optimized. The algorithm iterates, alternating between the two, to find a solution.\n\nAlignment is found using optimal transport methods from Kantorovich. The center selection is performed via one of many clustering techniques, including K-means and gradient descent. A variant of this algorithm that allows for non-perfect fairness is also introduced as a paramterized option.\n\nOn the theory side, they show that their designed combined objective is equivalent to optimizing for the clustering objective in light of the fairness constraint. This can then be used to show their parameterized algorithm approximates the clustering objective with small violation to the fairness constraint. The approximation factor is within a constant factor of the vanilla clustering algorithm used, and the violation is linearly dependent on an error constraint epsilon.\n\nThis paper also validates their findings with experiments. They select a handful of baseline fair clustering algorithms that represent in-processing, pre-processing, and post-processing fairness techniques. These experiments show that, on tested cases, their algorithm provides the best fairness-cost tradeoff. It is also numerically stable and does not require too much additional computation time.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*To reviewer AM68: We sincerely appreciate your review and thank you for the opportunity to improve our work. Please refer to our point-by-point responses below.*\n\n------\n\n### Weaknesses\n\n\n> 1: Extremely notationally dense ...\n\n- Answer:\n    - When preparing this work, we initially considered summation-based notations for expressions such as\n        $ \\frac{1}{n\\_{s}} \\sum\\_{i=1}\\^{n\\_{s}} \\sum\\_{k=1}\\^{K} \\mathcal{A}\\_{s}(\\mathbf{x}\\_{i})\\_{k} \\bigg( \\frac{\\Vert\\mathbf{x}\\_{i}-\\mathbf{T}(\\mathbf{x}\\_{i})\\Vert^2}{4} + \\left\\Vert \\frac{\\mathbf{x}\\_{i} + \\mathbf{T}(\\mathbf{x}\\_{i})}{2}-\\mu\\_k \\right\\Vert\\^2 \\bigg), $\n        for eq. (2) in Theorem 3.1.\n        However, we decided to use the probability-based notations instead, since the readability of the proofs is much improved.\n    - We were also concerned about this and **made efforts to explain the probability-based formulations by use of summation-based notation in several instances (e.g., the clustering cost $C(\\mu, \\mathcal{A})$ in Section 2, the definition of balance in lines 119-120, and assignment functions of FCA in Section 4)**.\n\n> 2: New methods aren't entirely novel ...\n\n- Answer: \n    - We agree that FCA is similar to the fairlet-based methods in the sense that the idea of matching is used.\n    In this sense, FCA can be viewed as a novel extension of the fairlet-based methods.\n    - Although the fairlet-based methods also rely on matching, it would be not optimal in view of fair clustering. In contrast, **our method guarantees to find a matching map, which provides a (local) optimal fair clustering, by Theorems 3.1 and 3.3.**\n    Also, please see Remark 3.2 for further discussion.\n    - It would be hard to modify the fairlet-based methods to control fairness level (for non-perfect fairness).\n    FCA can be modified to find an (local) optimal solution to control fairness level (i.e., FCA-C algorithm).\n    - This novel extension is made possible by **the novel reformulation of the fair clustering objective function using the matching map (or alignment)**, as presented in Section 3.\n\n------\n\n### Questions\n\n> 1: Would you say ...\n\n- Answer:\n    - We thank you for the insightful question.\n    Yes, you are right.\n    However, in fact, **the 'before' step of our approach (i.e., finding matchings) is not solely for achieving fairness, but also simultaneously for minimizing the clustering cost**.\n    Specifically, it solves a modified Kantorovich problem, where the modification is aimed at minimizing the clustering cost.\n    - Furthermore, the proposed algorithm can be extended to control the fairness level (e.g., non-perfect fairness), while other pre-processing algorithms such as fairlet-based methods are not designed for it.\n\n> 2: Can you clarify ...\n\n- Answer: \n    - Numerical stability means that **FCA does not suffer from numerical instability compared to VFC**.\n    The main reason for this stability is that FCA does not have any regularization parameters while VFC requires to choose a fairness regularization parameter, which can make the algorithm numerically unstable.\n    - Specifically,\n    (i) FCA is more robust to dataset pre-processing, while VFC operates reliably when data points are $L_{2}$-normalized.\n    (ii) FCA can achieve near-perfect fairness, whereas VFC may fail to do so.\n    In detail, without $L_{2}$-normalization - especially in high-dimensional settings - VFC can become numerically unstable due to overflow.\n    See Appendix C.3.1 for details.\n\n\n> 3: How does the epsilon ...\n\n- Answer: \n    - **(Fairness bound by $\\epsilon$)**\n    **Please refer to Proposition 4.2, which shows that the fairness level (balance) is bounded by $\\epsilon.$**\n    - **(The trade-off)** The clustering cost for a larger $\\epsilon$ is always lower than that for a smaller $\\epsilon.$\n    That is, the optimal fair clustering with $\\epsilon$ is included in $\\mathbf{A}_{\\epsilon'}$ for $\\epsilon'>\\epsilon.$ \n    - **(Note: definition of $\\epsilon$)**\n    $\\epsilon \\in [0, 1]$ represents the size of the set $\\mathcal{W}$ (i.e., $\\mathbb{Q}((\\mathbf{X}\\_{0}, \\mathbf{X}\\_{1}) \\in \\mathcal{W}) \\le \\epsilon$), as defined below eq. (5).\n    The set $\\mathcal{W}$ consists of the aligned data points to which the standard $K$-means clustering cost is applied.\n    That is, $\\epsilon$ used in the FCA-C algorithm is the fairness level: as $\\epsilon$ decreases, the resulting clustering of FCA-C becomes fairer.\n\n\n\n> 4: Are the benchmark ...\n\n- Answer: \n    - Yes, you are right.\n    Among the four baseline methods we consider in our study (FCBC, SFC, FRAC, and VFC), three methods have been developed for $K$-means (as well as other $K$-clustering), while SFC is originally designed for $K$-median.\n    - **Please also note that, in Appendix C.3.9 we already discussed how to modify FCA for the $K$-median clustering setting**.\n    As shown in Table 17, FCA outperforms SFC under the $K$-median clustering setting.", "claims_and_evidence": "Their claims are supported by theoretical and empirical evidence. Theoretical evidence comes as proofs deferred to the appendix. Experiments are partially in the appendix but the major results are shown in the paper to support their findings.", "methods_and_evaluation_criteria": "The methods seemed to have no issues.", "theoretical_claims": "Theoretical claims were believable, but for the most part, proved in the appendix. I did not check the appendix.", "experimental_designs_or_analyses": "I did not find any issues", "relation_to_broader_scientific_literature": "Fair clustering is a relatively new yet also pretty extensively studied area of research. Many methods have been proposed, particularly for group fair clustering. To my knowledge, less has been done regarding group fair k-means, which is the problem this paper approaches. This paper additionally proposes a new way to combine the fairness constraint and clustering objective into a single objective that turns out to be equivalent to the given problem. This allows them to iteratively optimize the two terms of the combined objective to arrive on a solution. This is somewhat like a repeated pre-processing method, which is interesting in its own right. Combined objectives have also been studied before, but in the context of a different formulated problem, where fairness is not a constraint but given to be part of the objective.", "essential_references_not_discussed": "None that I am aware of", "other_strengths_and_weaknesses": "Strengths\n- New methods\n- Formulations very nicely represent the original problem\n- Technically involved\n- Experimentally verified\n\nWeaknesses\n- Extremely notationally dense, with a fair amount of notation that is not introduced properly (it generally assumes a pretty strong understanding of advanced probability and its notation)\n- New methods aren't entirely novel, they bear some similarities to existing methods", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Would you say your techniques are sort of like iterated preprocessing? You do have a kind of \"before\" and \"after\" part of the algorithm, where before attempts to achieve fairness and after then selects centers accordingly.\n\n2. Can you clarify what you mean by numeric stability?\n\n3. How does the epsilon parameter control a tradeoff? In theorem 4.3, I only see it affecting the fairness violation.\n\n4. Are the benchmark clustering methods designed for K-means? I know much of fair clustering literature has looked at k-center and k-median instead of k-means.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rw4yXqlT4P", "reviewer": "Reviewer_4J8b", "summary": "This paper introduces a fair clustering method called Fair Clustering via Alignment (FCA), which aims to balance the trade-off between fairness and clustering utility. The authors propose a decomposition of the fair k-means clustering objective into two components: the transport cost and the clustering cost. The key idea is to alternately align data from different protected groups into a common space and optimize cluster centers in this aligned space. The authors claim that FCA theoretically guarantees approximately optimal clustering utility for any given fairness level without complex constraints. Empirical results demonstrate the effectiveness of FCA in terms of both fairness and clustering utility.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*To reviewer 4J8b: We sincerely appreciate your review and the opportunity to improve our work. Please refer to our point-by-point responses below.*\n\n------\n### Weaknesses\n\n> 1: The computational complexity ...\n- **Section 4.3 introduces a partitioning technique to reduce the computational complexity.**\nOur experiments (Figures 6–7 and Table 9 in Appendix C.3.3) demonstrate that it yields reasonable results and significant runtime reduction.\nTo evaluate scalability, **we already conducted experiments on a dataset of one million data points, showing that FCA outperforms VFC (Appendix C.3.7).**\n\n> 2: The method requires ...\n- We think that $\\epsilon$ is not a tuning parameter, but $\\epsilon$ itself serves as a fairness level in FCA-C.\nIn particular, on Page 5 we define $\\mathbf{A}\\_{\\epsilon}$ as the set of assignment functions where the sum of unfairness across clusters is bounded by $\\epsilon.$\nFCA-C always converges to a local minimum for any given $\\epsilon.$\n- On the other hand, Proposition 3.2 implies that we can control balance by controlling $\\epsilon.$\n\n> 3: The paper primarily addresses ...\n- We have already discussed extending FCA to handle multiple groups (see Appendix A.3).\nTo numerically validate this extension, we newly conducted an analysis using Bank dataset with 3 groups single/married/divorced (following VFC (Ziko et al., 2021)).\nThe results are in the table below (to be added to Appendix A.3): **FCA can practically handle multiple groups and outperforms VFC** (a lower cost $0.222 < 0.228$ with a higher balance $0.182 > 0.172$).\n\n| Bank | 3 groups (single/married/divorced)| |\n|:---:|:---:|:--:|\n| Bal* = 0.185  | Cost (↓)| Bal (↑)|\n| VFC   | 0.228  | 0.172|\n| FCA ✓ | **0.222**   | **0.182** |\n\n------\n### Other Comments Or Suggestions\n> 1: It is better ...\n- Please see our response to 'Weaknesses' above.\n\n> 2: Consider discussing ...\n- **(Sinkhorn algorithm)**\n    We also applied the Sinkhorn algorithm and compared with solving the Kantorovich problem using the linear programming.\n    The Sinkhorn algorithm of Cuturi et al., (2013) optimizes  $\\mathbf{C} + \\lambda \\cdot ent(\\Gamma),$ where $\\mathbf{C}$ is the cost matrix defined in Section 4.1, $\\lambda$ is a regularization parameter, and $ent(\\Gamma)$ denotes the entropy of the coupling matrix $\\Gamma.$\n\n    The result table below suggests that:\n    careful tuning of $\\lambda$ is crucial, while the runtime reduction may not be significant in practice ($\\lambda = 0.01$) and a large regularization ($\\lambda = 1.0$) significantly degrades performance while reducing runtime (10\\% decrease).\n    This experiment also suggests that reducing computational cost (beyond the partitioning technique) for solving the Kantorovich problem would be difficult but is a promising future study.\n    We will include this discussion in Appendix.        \n    | Adult / Bal* = 0.494 | Cost (↓) | Bal (↑) | Runtime / iteration (sec) |\n    |:---:|:---:|:---:|:---:|\n    | FCA (Sinkhorn, λ = 1.0) | 0.350 | 0.271 | 4.98|\n    | FCA (Sinkhorn, λ = 0.1) | 0.315 | 0.463 | 5.12|\n    | FCA (Sinkhorn, λ = 0.01) | 0.330 | 0.491 | 5.55|\n    | FCA (Linear program) | 0.328 | 0.493 | 5.67|\n\n    (References)        \n    Cuturi et al., (2013): Sinkhorn Distances: Lightspeed Computation of Optimal Transport\n\n> 3: Expanding ...\n- In Appendix A.4, we already showed that FCA can be similarly applied to $L_{p}$ norms for all $p \\ge 1.$\nExperimentally, Appendix C.3.9 (Table 17) shows that under the $K$-median ($L_{1}$ norm) setting, FCA outperforms the fairlet-based method SFC.\n- During the rebuttal, **we realized that the argument for the extension to $L_{p}$ norm in Appendix A.4 can be applied to any distance satisfying the triangle inequality**.\nWe will add this comment in the camera-ready version.\n\n------\n\n### Ethical Review Concerns\n> 1: This paper may need an ethics review ...\n- Our paper primarily aims to **achieve proportional (group) fairness in clustering, in line with many existing works**.\nWe acknowledge that focusing solely on proportional fairness may overlook other fairness notions.\nIn light of your feedback, **we will add the following paragraph to our Impact Statement in the camera-ready version**:\n- **(A paragraph to be added to `Impact Statement')**\n\n    *While this work focuses on proportional (group) fairness, we acknowledge that such an approach may overlook other fairness notions, such as individual fairness or social fairness (e.g., balancing clustering costs across groups), which are not explicitly addressed within the proportional fairness framework.\n    We therefore encourage readers to interpret our results with this scope in mind: our goal is to improve the trade-off between clustering cost and proportional fairness level, but care must be taken when considering the broader implications for other fairness notions.\n    In conclusion, we anticipate future studies that integrate fair clustering research with various notions of fairness*.", "claims_and_evidence": "The claims made in the paper are generally well-supported by both theoretical analysis and empirical results. The authors provide a clear theoretical foundation for their decomposition of the fair clustering objective, and they validate their claims through extensive experiments on benchmark datasets.", "methods_and_evaluation_criteria": "The proposed method, FCA, is well-motivated and makes sense for the problem of fair clustering. The authors use a combination of optimal transport theory and standard clustering algorithms to align data from different protected groups and optimize cluster centers. The evaluation criteria (Cost and Balance) and the benchmark datasets are widely used.", "theoretical_claims": "The theoretical claims are supported by rigorous proofs, which are provided in the supplementary material. The key theoretical contribution is the decomposition of the fair clustering objective into transport and clustering costs, which is proven in Theorem 3.3. The authors also provide an approximation guarantee for their algorithm in Theorem 4.3.", "experimental_designs_or_analyses": "The experimental design is sound and comprehensive. The authors compare FCA against several baseline methods across multiple datasets, including pre-processing, in-processing, and post-processing approaches.", "relation_to_broader_scientific_literature": "The paper builds on established research in fair clustering, particularly extending fairlet-based methods and in-processing approaches.", "essential_references_not_discussed": "There are no critical references missed.", "other_strengths_and_weaknesses": "Strengths:\n1. The alignment-based approach introduces a novel and effective method for enforcing fairness in clustering.\n2. FCA provides both theoretical guarantees and practical improvements over existing clustering methods.\n3. FCA-C enhances the method's flexibility by enabling fairness–utility trade-offs.\nThe empirical evaluation is thorough, covering diverse datasets and baseline methods.\n\nWeaknesses:\n1. The computational complexity of solving the Kantorovich problem may hinder scalability to very large datasets.\n2. The method requires careful tuning of the fairness control parameter in FCA-C for optimal performance.\n3. The paper primarily addresses binary sensitive attributes, with limited exploration of extending FCA to multiple protected groups.", "other_comments_or_suggestions": "1. It is better to include a more detailed discussion on the limitations of the approach, particularly in terms of scalability and applicability to non-binary sensitive attributes.\n2. Consider discussing potential strategies to further reduce the computational cost of solving the Kantorovich problem. \n3. Expanding the approach to clustering with non-Euclidean distance metrics is better.", "questions_for_authors": "Please refer to the weakness and the other comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Discrimination / Bias / Fairness Concerns"]}}, {"review_id": "SDoXeARaqQ", "reviewer": "Reviewer_Nujs", "summary": "The paper introduces an in-processing fair clustering approach that matches two instances from different protected groups and assigns them to the same cluster. The approach directly minimizes the clustering cost with respect to both the matching map and cluster centers simultaneously. The proposed method is theoretically proven and evaluated on three datasets and four baselines/competitors. The experimental results show that the proposed method outperforms the baselines and effectively controls the trade-off at multiple fairness levels.\n## update after rebuttal", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*To reviewer Nujs: We sincerely appreciate your review and thank you for the opportunity to improve our work. Please refer to our point-by-point responses below.*\n\n------\n\n### Claims And Evidence\n\n> 1: However, in the experiments, the authors do not compare the results of proposed method with the method of Chietichetti et al. (2017).\n\n- In the current version, instead of directly comparing with Chietichetti et al. (2017), we compared FCA with SFC (Backurs et al., 2019), which developed a more scalable fairlet-based method.\n    Notably, Backurs et al., (2019) reported SFC's competitive/better performance when compared to Chietichetti et al. (2017) across three real datasets.\n- However, in light of your suggestion, we have newly conducted experiments comparing FCA and Chietichetti et al. (2017).\n    The results are provided below, showing ourperformance of FCA, which we will add to Appendix C.3.1 in the camera-ready version.\n\n    | Dataset / Bal*  | Adult / 0.494   |  | Bank / 0.649    |  | Census / 0.969  |  |\n    |:-------|:---:|:---:|:---:|:---:|:---:|:---:|\n    |           | Cost (↓)       | Bal (↑)      | Cost (↓)       | Bal (↑)      | Cost (↓)       | Bal (↑)      |\n    | Chietichetti et al. (2017)  | 0.507           | 0.488        | 0.378           | 0.639        | 1.124           | 0.941        |\n    | SFC        | 0.534           | 0.489        | 0.410           | 0.632        | 1.015           | 0.937        |\n    | FCA ✓      | **0.328**           | **0.493**        | **0.264**           | **0.645**        | **0.477**           | **0.962**        |\n\n------\n\n### Methods And Evaluation Criteria\n\n> 1:  However, the authors do not use the well-known measures to evaluate the clustering quality.\n\n- The reason why we consider the `cost' for measuring clustering quality is because it is the clustering objective function to be minimized.\n- **(Comparison in terms of the silhouette score)**\n    However, as you suggested, measuring the cost alone may not fully capture the clustering quality, we additionally consider another measure, called the silhouette score.\n    The silhouette score is computed as the average of $ (d_{\\text{near}} - d_{\\text{intra}}) / \\max(d_{\\text{intra}}, d_{\\text{near}})$ over all data points, where $d_{\\text{intra}}$ denotes the intra-cluster distance and $d_{\\text{near}}$ represents the average distance to the nearest neighboring cluster.\n\n    Surprisingly, the results in the following table show that **FCA is also superior or competitive to baselines in terms of the silhouette score**.\n    We will add it to Appendix C.3.1 of the camera-ready version.\n\n    | Adult / Bal* = 0.494 | Silhouette (↑) | Bal (↑)      |    \n    |:---:|:-----:|:---:|\n    | Standard (fair-unaware) | 0.227          | 0.223        |\n    | FCBC  | 0.173          | 0.443        |\n    | SFC   | 0.071          | 0.489        |\n    | FRAC  | 0.156          | 0.490        |\n    | FCA ✓ | **0.176**          | **0.493**        |\n\n\n------\n\n### Experimental Designs Or Analyses\n\n\n> 1: However, 3 datasets are not yet appropriate ... Besides, the selection of features (on each dataset) is not yet well explained...\n\n- **(The number of datasets)**\n    Please note that **we analyzed 6 datasets in total**.\n    That is, not only the three tabular datasets, but we also analyzed on two image datasets (Section 5.3 and Appendix C.3.2) and a large synthetic dataset (Appendix C.3.7).\n- **(Analysis on an additional dataset)**\n    However, in light of your comment, we additionally conducted an analysis on Credit Card dataset from Yeh and Lien (2009), which was also used in Bera et al., (2019) and Harb \\& Lam, (2020).\n    We used gender as the sensitive attribute and set $K = 10.$\n    The results are provided in the table below (to be added to Appendix in the camera-ready version), showing the outperformance of FCA.\n\n    |  CreditCard / Bal* = 0.656   | Cost (↓)           | Bal (↑)         |\n    |:---:|:------:|:---:|\n    | Standard (fair-unaware) | 0.392  | 0.506           |\n    | FCBC  | 0.492  | 0.629           |\n    | SFC   | 0.682  | **0.653**           |\n    | FRAC  | 0.510  | 0.649           |\n    | FCA ✓ | **0.402**  | **0.653**           |\n\n    (References)\n    Yeh and Lien (2019): The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 2009.\n\n- **(About the feature selection)**\n    Existing fair clustering works use **continuous variables** as features (Backurs et al. 2019; Bera et al., 2019; Esmaeili et al., 2021; Ziko et al., 2021), so we have made the same choice.\n    For reference, the features we consider in this paper are the same as VFC (Ziko et al., (2021)).\n    Furthermore, please note that the feature `final weight (fnlwgt)' has also been selected in the prior works (Esmaeili et al., 2021; Ziko et al., 2021).\n\n    We will add the above detailed explanation to Appendix C.1 in the camera-ready version.", "claims_and_evidence": "The decomposition process is proved theoretically, and the experimental results support their claim. However, in the experiments, the authors do not compare the results of proposed method with the method of Chietichetti et al. (2017).", "methods_and_evaluation_criteria": "The proposed approach is technically sound. However, the authors do not use the well-known measures to evaluate the clustering quality.", "theoretical_claims": "I have checked the proofs of theoretical claims and they are sound.", "experimental_designs_or_analyses": "In general, the experimental results are promising. However, 3 datasets are not yet appropriate  to make a comprehensive assessment. Besides, the selection of features (on each dataset) is not yet well explained. For example, the feature “fnlwgt” (Adult dataset) is usually ignored in many relevant works.", "relation_to_broader_scientific_literature": "The paper introduces a new in-processing fair clustering method which outperforms the baselines in terms of performance and complexity.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "The idea of matching data from different protected groups is similar to the fairlet-based method, but the authors clarified their contrast and superiority.", "other_comments_or_suggestions": "None", "questions_for_authors": "Please refer to my comments above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes fair clustering with alignment (FCA), part of a family of approaches that seek to balance some form of minimization of fairness constraint or cost while also minimizing overall clustering cost (e.g., traditional k-means objective, traditional k-center objective, and so on).  That general body of work has been quite active for over ten years, so the problem fits within scope and within a greater research community in AI/ML as well as OR/MS.  Reviewers broadly appreciated the paper, both from a theory and an experimental results/comparison point of view.  The one weakly negative reviewer, 1gG2, brings up some good points about the theoretical analysis - this AC appreciates the authors' detailed rebuttal to these points, and (i) encourages the authors to update their working draft with these changes/comments and (ii) note that this AC is relatively down-weighted the weakly negative score because of that rebuttal.  All other reviewers were weakly positive.  Would also encourage the authors to consider expanding to other standard settings in fair clustering (e.g., non-Euclidean metrics, multi-group membership, etc), either in this or future work.
Decision: Accept (poster)