# Feature-based Individual Fairness in k-clustering

Debajyoti Kar11footnotemark: 1
IIT Kharagpur, India
<EMAIL_ADDRESS>&Mert Kosan11footnotemark: 1
University of California, Santa Barbara
<EMAIL_ADDRESS>&Debmalya Mandal
MPI-SWS, Germany
<EMAIL_ADDRESS>&Sourav Medya
University of Illinois, Chicagao
<EMAIL_ADDRESS>&Arlei Silva
Rice University, USA
<EMAIL_ADDRESS>&Palash Dey
IIT Kharagpur, India
<EMAIL_ADDRESS>&Swagato Sanyal
IIT Kharagpur, India
<EMAIL_ADDRESS>
###### Abstract

Ensuring fairness in machine learning algorithms is a challenging and
essential task. We consider the problem of clustering a set of points while
satisfying fairness constraints. While there have been several attempts to
capture group fairness in the $k$-clustering problem, fairness at an
individual level is relatively less explored. We introduce a new notion of
individual fairness in $k$-clustering based on features not necessarily used
for clustering. We show that this problem is NP-hard and does not admit a
constant factor approximation. Therefore, we design a randomized algorithm
that guarantees approximation both in terms of minimizing the clustering
distance objective and individual fairness under natural restrictions on the
distance metric and fairness constraints. Finally, our experimental results
against six competing baselines validate that our algorithm produces
individually fairer clusters than the fairest baseline by 12.5% on average
while also being less costly in terms of the clustering objective than the
best baseline by 34.5% on average.

***Both authors contributed equally to this research.

##  1 Introduction

Machine learning systems are increasingly being used in various societal
decision-making, including predicting recidivism [Ang+16, Cho17], deciding
interest rates [Fus+20], and even allocating healthcare resources [Obe+19].
However, beginning with the report on bias in recidivism risk prediction
[Ang+16], it has been known that such systems are often biased against certain
groups of people. In recent years, various methods and definitions have been
proposed for ensuring fairness in supervised learning settings, with efforts
ranging from debiasing datasets [Fel+15] to explicitly encoding the fairness
constraints during the training of a classifier [Aga+18].

This paper focuses on fairness in unsupervised learning, particularly
clustering. There are two major reasons why clustering should be fair with
respect to different subgroups. First, clustering is often a pre-processing
step for generating new data representations for downstream tasks. Since we
want the downstream decisions to be fair, the clustering step needs to be
unbiased [Abb+19]. Second, clustering is also used in various resource
allocation problems, e.g. in _facility location_ [JKL19]. Since it is
desirable that no group is disproportionately affected by such decisions,
there has been an increasing interest in designing clustering algorithms that
are fair with respect to different subgroups [Chi+17, Bac+19, Ber+19, Ahm+19].
Such group-fair clustering algorithms ensure that each protected group has an
approximately equal presence in each cluster.

Compared to group fairness, individually fair clustering has received less
attention. Individually fair clustering is motivated by the _facility location
problem_ where the goal is to open $k$ facilities while minimizing the total
transportation cost between individuals and their nearest facility. If we
choose $k$ facilities (or centers) uniformly at random, then each point $x$
could expect one of its nearest $n/k$ neighbors to be one of such facilities.
This led a few studies [JKL19, MV20, CN21] to consider the following notion of
individual fairness. For a point $x$, let $r(x)$ be the radius such that the
ball of radius $r(x)$ centered at $x$ has at least $n/k$ points. An
individually fair clustering guarantees that, for every $x$, a cluster center
is chosen from the $r(x)$-neighborhood of $x$.

Although individually fair clustering [JKL19] provides guarantees for each
point, it does not exactly reflect the original premise of individual fairness
suggested by [Dwo+12], which requires that similar individuals should receive
similar decisions. In the context of clustering, this means that two points
$x$ and $y$ that are similar (in terms of features) should be clustered
similarly. However, the definition proposed by [JKL19] does not provide such a
guarantee, as points similar to a point $x$ could be different from the points
within a radius of $r(x)$ from $x$.

#### Proposed Definition of Individual Fairness.

In order to address the drawback above, we propose a new notion of individual
fairness in clustering. First, motivated by the original definition of
individual fairness in supervised learning [Dwo+12], we introduce a feature-
based notion of individual fairness. We say that two individuals are similar
if their features match significantly (parameterized by $\gamma$ in Definition
1). Now, for each individual $v$, let $C(v)$ denote the cluster $v$ is
assigned to. Then our feature-based individually fair clustering requires that
$C(v)$ also contains at least $m_{v}$ individuals that are similar to $v$. The
variable $m_{v}$ is a parameter to encode the degree of fairness. More
specifically, it encodes the amount of similarity an individual seeks inside
their own cluster. This guarantees that a point $v$ is not isolated in its own
cluster but that the cluster has a desired representation (or participation)
from points similar to it. Note that, the features that are used to compute
similarity for individual fairness might not necessarily be used for
clustering. In fact, these two sets of features might be disjoint.

Our notion of individual fairness guarantees that similar individuals (in
terms of possibly sensitive features) often share similar clusters. Consider
the following motivating example. Ad networks collect user behavior data
(e.g., browsing history, location) as well as possibly sensitive attributes
(e.g., race and gender) to cluster users into several categories [Yan+09].
These categories are directly used for targeted recommendations, including
jobs and healthcare. In this context, the cost function of the clustering
algorithm should be based on user behavior while an individual’s notion of
fairness should be based on sensitive attributes such as race and gender. In
this case, similarity in terms of sensitive features can be seen as a
relaxation of a protected group membership.

#### Contributions.

Our main contributions are as follows:

  * $\rhd$

Novel Formulation: We propose a new definition of individual fairness in
clustering based on how individuals are similar in terms of their features.
Our definition guarantees that each individual has a desired level of
representation of similar individuals in their own cluster.

  * $\rhd$

Problem Characterization: We show that minimizing the clustering cost subject
to the new notion of individual fairness is NP-hard, and also cannot be
approximated within a factor $\delta$ for any $\delta>0$.

  * $\rhd$

Algorithm: We design a randomized algorithm providing an additive
approximation cost while guaranteeing fairness within a multiplicative factor
with high probability.

  * $\rhd$

Experiments:  Our experiments on several standard datasets show that our
approach produces by $34.5\%$ less cost on average in clustering than the
best-competing method while ensuring individual fairness for more than
$95.5\%$ points on average.

#### Related Work.

[Chi+17] first introduced the problem of fair clustering with disparate impact
constraints and their goal was to ensure that all the protected groups have
approximately equal representation in every cluster. Several works [Ber+19a,
RS18] studied different generalizations of the fair clustering problem.
Furthermore, several papers [Bac+19, SSS18, HJV19] proposed procedures to
scale fair clustering to a large number of points. Although we consider
individual fairness, our work is related to [Ber+19], which shows that a
$\rho$-approximation to the vanilla clustering problem can be converted to a
$(\rho+2)$-approximate solution to fair clustering with bounded (and often
negligible) violation of fairness constraints.

Our paper is focused on individual fairness, which was first defined by
[Dwo+12] in the context classification, and requires similar individuals to be
treated similarly. For clustering problems, such a notion of individual
fairness was first defined by [JKL19]. They studied individual fairness in
terms of the guarantee a randomly chosen set of $k$ points must satisfy.
Informally, an individually fair clustering guarantees that for each point
$x$, a cluster center is chosen from a certain neighborhood of $x$. [MV20]
designed a bicriteria approximation algorithm for individually fair $k$-means
and $k$-median problems. Their algorithms guarantee that not only the fairness
constraints are approximately satisfied, but also the objective is
approximately maximized. Later, [CN21] proposed an algorithm that has
theoretical fairness guarantees comparable with [MV20], and empirically,
obtains noticeably fairer solutions. Recently, [VY21] designed improved
bicriteria algorithms for general $\ell_{p}$-norm costs. Another recent study
[Chh+22] defined a coreset for individually fair clustering problem using the
generalized fair radius notion, and [Cha+22] used per-point fairness and
aggregate fairness constraints for the k-center problem. Later they
incorporated the price of fairness notion to combine these two constraints
into one algorithm.

The definition of individual fairness in [JKL19] was mainly motivated by
fairness in the facility location problem. Recently, [KAM20] considered a
different notion of individual fairness in clustering, where the goal is to
ensure that each point, is closer to the points in its own cluster than the
points in any other cluster. Our proposed definition can be seen as a way to
capture these two notions, as we consider feature-based similarity, as well as
guaranteed representation for each point.

Here, we focus on the $\ell_{p}$-norm cost for clustering, which is just the
sum of $\ell_{p}$-distances of each point from its corresponding cluster
center. [Cha+22] also considers $\ell_{p}$-norm objectives in their individual
fairness formulation. However, several papers did consider other objectives in
the context of group-fair clustering [Ahm+19, GSV21, KAM19]. Finally, our
focus is on fair clustering algorithms, and there is extensive literature on
fair algorithms for unsupervised [Sam+18, Kle+19] and supervised learning more
broadly [Aga+18, Don+18, Cel+19] . The coverage of these algorithms is out of
the scope of the paper, and we refer the interested reader to the following
excellent surveys: [CR18, Sel+19] and [Meh+21].

##  2 Preliminaries

We first introduce some necessary notations. Let $V$ be a set of $n$ points
$V=\\{1,2,\ldots,n\\}$. We denote $\\{S_{1},S_{2},\ldots,S_{q}\\}$ as a set of
$q$ features, where $S_{i}$ is the set of values for the $i$-th feature. We
denote the tuple of $q$ features of the point $i$ by
$X_{i}=(X_{i}^{t})_{t\in[q]}$. We write $C=(C_{i})_{i\in[k]}$ to denote a
clustering (i.e. partition) of the set $V$ and $(c_{i})_{i\in[k]}$ to denote
the corresponding cluster centers. Given a clustering $C$ and a point $v$, let
$\phi(v,C)$ be the cluster center assigned to the point $v$. When the
clustering $C$ is clear from the context, we use $\phi(v)$ to denote the
cluster center assigned to the vertex $v$. We are also given a distance
function $d:V\times V\rightarrow\mathbb{R}$ that measures the distance between
any pair of points. Given a clustering $C$, we can measure its cost through
the distance metric $d$. In particular, we will be interested in measuring the
sum of the $p$-th powers of distances from each point to its cluster center
for $p\in\mathbb{N}\cup\left\\{0\right\\}$:

$\mathrm{Cost}(C)=\sum_{v\in V}d(v,\phi(C,v))^{p}.$ (1)

We assume that the distance function $d$ depends on some features of the
points but don’t assume any relationship between those features and the ones
used for fairness.

###  2.1 Similarity

In order to define the feature-based notion of individual fairness, we first
define a similarity measure based on the features. To the best of our
knowledge, all the existing notions of individual fairness in clustering only
depend on the distance-based neighborhood of each point. In contrast, our
definition of individual fairness builds upon the features of individual
points that are not necessarily used for clustering. In order to define the
feature-based notion of fairness, we first define a similarity measure based
on the features.

In real-world settings, the fairness features can be both continuous and
discrete. To handle both cases, we convert the discrete variables (features)
into one-hot encoding vectors. The continuous variables are also normalized to
be within the range $[0,1]$. After these conversions, we can now define the
distance (or similarity) between two vectors. We convert the distance to
similarity with the following where $d^{\prime}$ is a distance function on
feature space:

$s(X_{i},X_{j})=e^{-d^{\prime}(X_{i},X_{j})}$ (2)

where $s$ is the similarity between $X_{i}$ and $X_{j}$ and $d^{\prime}$ is a
distance function (e.g., Euclidean). This operation guarantees that $s$ will
always generate a value between 0 and 1. We say that $X_{i}$ and $X_{j}$ are
$gamma$ similar if $s>\gamma$.

######  Definition 1 ($\gamma$-similarity).

For a parameter $\gamma\in[0,1]$, we say two points $i,j\in V,i\neq j$ are
$\gamma$-similar if $s(X_{i},X_{j})>\gamma$ where
$s(X_{i},X_{j})=e^{-d^{\prime}(X_{i},X_{j})}$. We assume that a point is not
$\gamma$-matched with itself.

Our definition of similarity is flexible enough to support diverse
applications. For any point $v$, we use $\Gamma(v)$ to denote the set of
points in $V$ that are $\gamma$-similar to $v$. Next, we introduce our
definition of individually fair clustering.

###  2.2 Individual Fairness

######  Definition 2 (Individual Fairness in Clustering).

Given a set $V$ of $n$ points along with a $q$-length feature vector
$X_{v}=(x_{v}^{1},\ldots,x_{v}^{q})$ for every point $v\in V$, a similarity
parameter $\gamma\in[0,1]$, an integer tuple $(m_{v})_{v\in V}$, and an
integer $k$, we say that a clustering $(C_{i})_{i\in[\ell]}$ ($\ell\leqslant
k$) is $(m_{v})_{v\in V}$-individually fair if it satisfies the following
constraint for every point $v\in V$:

$\left|\left\\{u:u\in\Gamma(v)\text{ and
}\phi(u)=\phi(v)\right\\}\right|\geqslant m_{v}$ (3)

The fairness constraint (3) says that at least $m_{v}$ points that are
$\gamma$-similar to point $v$ must belong to the cluster of $v$. Our goal is
to cluster $V$ into $\ell\;(\leqslant k)$ clusters, $(C_{i})_{i\in[\ell]}$,
with corresponding centers (or facilities†††We use cluster center and facility
interchangeably.) $(c_{i})_{i\in[\ell]}$, such that clusters are individually
fair for every point and minimize the clustering cost (e.g. sum of the $p$-th
powers of distances from cluster centers for some
$p\in\mathbb{N}\cup\left\\{0\right\\}$). Formally, our Individually Fair
Clustering problem is defined as follows.

######  Definition 3 (Individually Fair Clustering (IFC)).

The input is a set $V$ of $n$ points with a $q$-length feature vector
$X_{v}=(x_{v}^{1},\ldots,x_{v}^{q})$ for each $v\in V$, a similarity parameter
$\gamma\in[0,1]$, an integer tuple $(m_{v})_{v\in V}$, a set $F$ of potential
facilities. The objective is to open a subset $S\subseteq F$ of at most $k$
facilities, and find an assignment $\phi:V\longrightarrow S$ to minimize
Cost$(C)$ satisfying the fairness constraints (eq., 3).

The classical clustering problem, which we call Vanilla Clustering, is the
same as the IFC problem except for the fairness requirements from Equation 3.

##  3 Results

We present our main technical results in two directions. First, we provide
several hardness results to show that the general Individually Fair Clustering
(IFC) problem is hard even if one considers approximation. Then we contrast
the hardness results by developing randomized approximation algorithms for
various special cases of the IFC problem.

###  3.1 Hardness Results

In order to prove hardness results, we consider the decision version of the
IFC problem, where the goal is to find a clustering whose cost is below a
certain threshold. Note that, it is always possible to find a (trivial)
individually fair clustering by one cluster containing all the points.
However, the cost of such a fair clustering could be high, and we ask whether
it is possible to beat the cost of such trivially fair clustering. As there
can be multiple trivial fair clustering (depending on the cluster center
chosen), we naturally pick the one minimizing the cost as the benchmark.

######  Definition 4 (Trivially Fair Clustering).

Given a set $V$ of $n$ points along with $q$-length feature vector
$X_{v}=(x^{1}_{v},\ldots,x^{q}_{v})$ for every point $v\in V$, the trivially
fair clustering puts all points in one cluster and picks the point as cluster
center which minimizes the cost:

$\min_{f\in F}\sum_{v\in V}d(v,f)^{p}.$

We show that it is $\mathsf{NP}$-complete to compute if there exists a
clustering better than Trivially Fair Clustering by providing a reduction from
Satisfactory-Partition, which is known to be $\mathsf{NP}$-complete [BTV06].

######  Definition 5 (Satisfactory-Partition).

Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and an integer
$\lambda_{v}$ for every vertex $v\in\mathcal{V}$, compute if there exists a
partition $(\mathcal{V}_{1},\mathcal{V}_{2})$ of $\mathcal{V}$ such that

  1. i)

$\mathcal{V}_{1},\mathcal{V}_{2}\neq\emptyset$

  2. ii)

For every $i\in[2]$ and every $v\in\mathcal{V}_{i}$, the number of neighbors
of $v$ in $\mathcal{V}_{i}$ is at least $\lambda_{v}$.

We denote an arbitrary instance of Satisfactory-Partition by
$(\mathcal{G},(\lambda_{v})_{v\in\mathcal{G}})$.

######  Theorem 1.

It is $\mathsf{NP}$-complete to decide whether an instance of Individually
Fair Clustering admits a clustering of cost less than the Trivially Fair
Clustering even when there are only 2 facilities.

Please see the proof in the Supplementary.

Given the NP-completeness result, we explore the possibility of approximation
for the Individually Fair Clustering (IFC) problem. However, the next theorem
shows that IFC is inapproximable within factor $\delta$ for any $\delta>0$.

######  Theorem 2.

Distinguishing between instances of the IFC problem having zero and non-zero
optimal costs is NP-complete even when there are 2 facilities. Hence, for any
computable function $\delta$, there does not exist a $\delta$-approximation
algorithm for IFC unless P=NP.

###### Proof.

Let $\mathcal{A}$ be a deterministic polynomial time algorithm that
distinguishes between instances of IFC with 0 and non-zero optimal costs. We
use $\mathcal{A}$ to build an algorithm for Satisfactory-Partition. Let
$(\mathcal{G}=(\mathcal{V}=\\{v_{1},v_{2},\ldots,v_{n}\\},\mathcal{E}),(\lambda_{v})_{v\in\mathcal{V}})$
be an instance of Satisfactory-Partition. We create $n-1$ instances
$I_{1},I_{2},\ldots,I_{n-1}$ of IFC as follows: the set of points is
$U=\\{u_{1},\ldots,u_{n}\\}$ and $m_{v_{i}}=\lambda_{v_{i}}$ for every
$i\in[n]$ for all the instances; for instance $I_{i},i\in[n]$, we introduce
$2$ facilities $l$ and $r$ and define distances as follows:

$d(u_{j},l)=\begin{cases}1&\text{$j=1$}\\\
0&\text{$j\in\\{2,3,\ldots,n\\}$}\end{cases}$
$d(u_{j},r)=\begin{cases}1&\text{$j=i+1$}\\\
0&\text{$j\in\\{1,2,\ldots,n\\}\setminus\\{i+1\\}$}\end{cases}$

We define feature vectors of every point similar to Theorem 1 to realize the
above distances. We now run $\mathcal{A}$ on each of these instances. If
$\mathcal{A}$ finds any instance in $\\{I_{1},\ldots,I_{n-1}\\}$ to have zero
optimal cost, then we return yes for the Satisfactory-Partition instance;
otherwise, we return no for the Satisfactory-Partition instance.

Clearly, the above algorithm runs in polynomial time. We now prove its
correctness. If $\mathcal{G}$ does not have a non-trivial satisfactory
partition, then clearly every instance in $I_{1},…,I_{n-1}$ has an optimal
cost of one. On the other hand, if $\mathcal{G}$ has a non-trivial
satisfactory partition, say $(X,\bar{X})$, then we claim that at least one of
$I_{1},…,I_{n-1}$ has optimal cost 0. Without loss of generality, we assume
that we have $v_{1}\in X$. Let $v_{j}\in\bar{X}$, for some
$j\in\\{2,3,\ldots,n\\}$. Then clearly OPT$(I_{j-1})=0$ (assigning all the
corresponding vertices in $X$ to the cluster center $r$ and all other vertices
to the cluster center $l$). Thus, the algorithm is correct. ∎

Note that the distances in the above reduction do not satisfy the triangle
inequality. If we insist that distances must satisfy the triangle inequality,
then we have the following (weaker than Theorem 2) inapproximability result.

######  Theorem 3.

There does not exist any FPTAS for the IFC problem when the distances in the
input satisfy triangle inequality unless $\mathsf{P}=\mathsf{NP}$.

Please see the proof in the Supplementary.

###  3.2 Algorithmic Results

Given the strong inapproximability results in the previous section, we aim to
develop approximation algorithms for Individually Fair Clustering under
suitable conditions. First, we develop an approximation algorithm for
Individually Fair Assignment (Theorem 4). Next, we show how to obtain an
algorithm for Individually Fair Clustering of similar guarantee (Theorem 5).
Bera et al. [Ber+19] designed an approximation algorithm for group fair
clustering from an algorithm for group fair assignment. We follow a similar
approach to individual fairness.

One of the main ingredients of our technical results is the Individually Fair
Assignment problem, which, given a set of $k$ potential cluster centers,
determines an assignment of the points i.e. which point should be assigned to
which cluster center. Formally, it is defined as follows:

######  Definition 6 (Individually Fair Assignment (IFA)).

Given a set $V$ of $n$ points along with a $q$-length feature vector
$X_{v}=(x_{v}^{1},\ldots,x_{v}^{q})$ for every point $v\in V$, a similarity
parameter $\gamma\in[0,1]$, an integer tuple $(m_{v})_{v\in V}$, and a set
$F=\\{f_{1},\ldots,f_{k}\\}$ of $k$ facilities, an $(m_{v})_{v\in V}$-fair
assignment finds the optimal cost-minimizing assignment satisfying the
fairness constraints (3).

Our Algorithm, LP-FAIR:  Algorithm 1 describes our randomized approximation
algorithm for IFA. The linear program (LP) in Inequality 4 is a relaxation of
the IFA problem. It has a variable $x_{v,f_{k}}$ for each vertex $v$ and
facility $f_{k}$. In an (integral) “solution” the variable $x_{v,f_{k}}$ takes
value $1$ if and only if the point $v$ is assigned to the facility $f_{k}$.
After solving the LP, Algorithm 1 determines the assignment $\phi$ by
assigning point $v$ to $f_{k}$ with probability $x^{*}_{v,f_{k}}$. Finally,
the above procedure is repeated $\log_{1+\delta}n$ times and the assignment
with the lowest cost is returned to boost the success probability.

Algorithm 1 LP-FAIR, Algorithm for IFA

1:$(V,(X_{v})_{v\in V},\gamma,(m_{v})_{v\in V},k)$, and $\delta$.

2:for $t=1,2,\ldots,T=\log_{1+\delta}n$ do

3: Solve the following LP to get solution $x^{\star}_{t}$.
$\displaystyle\begin{split}\min_{x}&\sum\limits_{v\in V}\sum\limits_{f_{k}\in
F}d(v,f_{k})^{p}\cdot x_{v,f_{k}}\\\
\textrm{s.t.}&\sum\limits_{u\in\Gamma(v)}x_{u,f_{k}}\geqslant m_{v}\cdot
x_{v,f_{k}}\ \forall v\in V,f_{k}\in F\\\ &\sum\limits_{f_{k}\in
F}x_{v,f_{k}}=1\ \forall v\in V\\\ &x_{v,f_{k}}\geqslant 0\ \forall v\in
V,f_{k}\in F\end{split}$ (4)

4: for each $v\in V$ do

5: Set $\phi_{t}(v)=f_{k}$ with probability $x^{\star}_{t,v,f_{k}}$.

6: end for

7:end for

8:return Assignment $\phi^{\star}$ with the minimum cost.

The next theorem presents probabilistic approximation guarantees provided by
Algorithm 1.

######  Theorem 4.

For any $\varepsilon,\delta>0$, there exists a randomized algorithm for IFA
running in time polynomial in $n$ and $\frac{1}{\delta}$, that outputs a
solution of cost at most $(1+\delta)$OPT where each vertex $v$ has at least
$\frac{m_{v}}{k}(1-\varepsilon)$ $\gamma$-similar points assigned to the same
facility with high probability if $m_{v}=\Omega(\frac{k\log
n}{\varepsilon^{2}})$, $\forall v\in V$.

###### Proof.

Let $x^{\star}$ be a solution to the linear program 4. Algorithm 1 assigns
point $v$ to $f_{k}$ with probability $x^{*}_{v,f_{k}}$. We now prove the
quality of this solution. Let $X$ be the random variable denoting the number
of points in $\Gamma(v)$ that are assigned to the same facility as a given
point $v$. For every $u\in\Gamma(v)$, let $X_{u}$ be the indicator random
variable indicating whether $u$ and $v$ are assigned to the same facility.
Thus,

$E[X_{u}]=\sum\limits_{f_{k}\in F}x^{*}_{v,f_{k}}x^{*}_{u,f_{k}}$

So we have,

$\displaystyle E[X]$ $\displaystyle=\sum\limits_{u\in\Gamma(v)}E[X_{u}]$
$\displaystyle=\sum\limits_{f_{k}\in
F}(x^{*}_{v,f_{k}}\sum\limits_{u\in\Gamma(v)}x^{*}_{u,f_{k}})$
$\displaystyle\geqslant m_{v}\sum\limits_{f_{k}\in
F}x^{*^{2}}_{v,f_{k}}\geqslant m_{v}/k$

Now using Chernoff bound,

$\text{Pr}[v\text{ has at most }\frac{m_{v}}{k}(1-\varepsilon)\text{
$\gamma$-similar points}]\leqslant
e^{-\frac{\varepsilon^{2}}{2}\frac{m_{v}}{k}}\leqslant\frac{1}{n^{2}}$

And using union bound,

$\text{Pr}[\exists\text{ a vertex that has at most
}\frac{m_{v}}{k}(1-\varepsilon)\text{ $\gamma$-similar
points}]\leqslant\frac{1}{n}$

Also, clearly, the expected cost of the computed solution is at most OPT.
Hence, using Markov’s inequality, $\text{Pr[cost of computed solution is
}\geqslant(1+\delta)\text{OPT}]\leqslant\frac{1}{1+\delta}$

As we repeat the above algorithm $T=\frac{\log n}{\log(1+\delta)}$ times and
output the solution with minimum cost, we have

$\text{Pr[cost of the computed solution is
}\geqslant(1+\delta)\text{OPT}]\leqslant\frac{1}{n}$

Also, by union bound, the probability that there exist a vertex having at most
$\frac{m_{v}}{k}(1-\varepsilon)$ $\gamma$-similar points in one of the $T$
solutions is at most $\frac{T}{n}$. ∎

Algorithm 2 Algorithm for Individually Fair Clustering

1:$(V,(X_{v})_{v\in V},\gamma,(m_{v})_{v\in V},k)$

2:Solve clustering problem $(V,(X_{v})_{v\in V},\gamma,(m_{v})_{v\in V},k)$
using any vanilla algorithm ignoring fairness constraints. Let
$\left(\left(C_{i}\right)_{i\in[\ell]},\left(c_{i}\right)_{i\in[\ell]}\right)$
be the output of the clustering algorithm.

3:$F\leftarrow\\{c_{1},\ldots,c_{\ell}\\}$

4:Run algorithm for Individually Fair Assignment on $(V,(X_{v})_{v\in
V},\gamma,(m_{v})_{v\in V},F)$. Let $\phi$ be the output.

5:return $(\phi^{-1}(c_{i}))_{i\in[\ell]}$ (ignore $\phi^{-1}(c_{j})$ if
$\phi^{-1}(c_{j})$ is the empty set for some $j\in[\ell$)

We next show a method to obtain an approximation algorithm for Individually
Fair Clustering from an approximation algorithm for Individually Fair
Assignment in a black box fashion.

######  Theorem 5.

If the distances satisfy the triangle inequality, then the existence of an
$\rho$-approximation algorithm for Vanilla Clustering and an
$\alpha$-approximation algorithm for Individually Fair Assignment with
$\lambda$-multiplicative violations for some $\lambda\geqslant 1$ implies the
existence of an $\alpha(\rho+2)$-approximation algorithm for Individually Fair
Clustering with $\lambda$-multiplicative violation.

###### Proof.

Let $S^{*}$ be the optimal set of facilities opened and $\phi^{*}$ be the
optimal assignment in the input Individually Fair Clustering instance. Let $S$
be the set of facilities returned by the vanilla $k$-clustering problem and
$\phi$ the assignment. For each $f^{*}\in S^{*}$, let us define
$\text{nrst}(f^{*})=\arg\min_{f\in S}d(f,f^{*})$. Consider the assignment
$\phi^{\prime}$ over the set of facilities $S$ that assigns each vertex $v$ to
$\text{nrst}(\phi^{*}(v))$. We claim that $\phi^{\prime}$ is a fair assignment
(please see Claim 1).

For any vertex $v$, let $\phi(v)=f$, $\phi^{\prime}(v)=f^{\prime}$ and
$\phi^{*}(v)=f^{*}$. Thus $d(v,f^{\prime})\leqslant
d(v,f^{*})+d(f^{*},\text{nrst}(f^{*}))\leqslant d(v,f^{*})+d(f^{*},f)\leqslant
2d(v,f^{*})+d(v,f)$. Since $l_{p}$ is a monotone norm,
$l_{p}(S,\phi^{\prime})\leqslant
2l_{p}(S^{*},\phi^{*})+l_{p}(S,\phi)\leqslant(\rho+2)OPT$. Now, since we have
an $\alpha$-approximation algorithm for Individually Fair Assignment, the
solution returned by the algorithm will have cost at most $\alpha\cdot
l_{p}(S,\phi^{\prime})\leqslant\alpha(\rho+2)\text{OPT}$. ∎

Note that the proof requires that $\phi^{\prime}$ is an individually fair
assignment. Next, we prove the following claim:

######  Claim 1.

$\phi^{\prime}$ is an individually fair assignment.

###### Proof.

For $v\in V$, let $T_{v}$ denote the set of vertices assigned to
$\phi^{*}(v)$. Since $\phi^{*}$ is an individually fair assignment, the number
of $\gamma$-similar points of $v$ in $T_{v}$ is at least $m_{v}$. Now all
vertices in $T_{v}$ are assigned to the facility $\text{nrst}(\phi^{*}(v))$.
Thus, the number of $\gamma$-similar points of $v$ in the assignment
$\phi^{\prime}$ is at least $m_{v}$. Hence, $\phi^{\prime}$ is an individually
fair assignment. ∎

##  4 Experiments

| Normalized Cost | Fairness | Macro Fairness
---|---|---|---
| Adult | Bank | Diabetes | Adult | Bank | Diabetes | Adult | Bank | Diabetes
FairCenter | $0.544\pm 0.107$ | $0.528\pm 0.134$ | $0.341\pm 0.029$ | $90.0\pm 5.5$ | $96.0\pm 2.0$ | $94.1\pm 5.0$ | $64.0\pm 15.0$ | $76.0\pm 8.0$ | $64.0\pm 8.0$
Alg-PP | $0.625\pm 0.098$ | $0.516\pm 0.053$ | $0.422\pm 0.089$ | $86.8\pm 10.9$ | $91.3\pm 7.4$ | $88.1\pm 7.0$ | $70.0\pm 24.5$ | $72.9\pm 16.3$ | $60.0\pm 20.0$
Alg-AG | $0.617\pm 0.114$ | $0.563\pm 0.178$ | $0.649\pm 0.268$ | $86.8\pm 10.9$ | $83.4\pm 5.5$ | $87.2\pm 7.9$ | $70.0\pm 24.5$ | $56.9\pm 13.2$ | $60.0\pm 20.0$
P-PoF-Alg | $0.592\pm 0.084$ | $0.586\pm 0.136$ | $0.528\pm 0.150$ | $86.8\pm 10.9$ | $87.6\pm 7.7$ | $92.8\pm 9.1$ | $70.0\pm 24.5$ | $66.9\pm 18.0$ | $80.0\pm 24.5$
H-S | $0.267\pm 0.053$ | $0.251\pm 0.022$ | $0.107\pm 0.033$ | $90.8\pm 4.3$ | $\textbf{97.7}\pm\textbf{1.8}$ | $91.1\pm 7.1$ | $53.0\pm 13.3$ | $70.0\pm 8.4$ | $66.0\pm 21.5$
Gonzalez | $0.331\pm 0.084$ | $0.327\pm 0.022$ | $0.088\pm 0.029$ | $88.6\pm 3.5$ | $90.4\pm 3.9$ | $89.9\pm 4.0$ | $56.0\pm 15.0$ | $60.0\pm 0.0$ | $56.0\pm 15.0$
LP-FAIR | $\textbf{0.194}\pm\textbf{0.034}$ | $\textbf{0.176}\pm\textbf{0.016}$ | $\textbf{0.057}\pm\textbf{0.026}$ | $\textbf{92.3}\pm\textbf{0.7}$ | $96.3\pm 4.6$ | $\textbf{97.9}\pm\textbf{2.8}$ | $\textbf{80.0}\pm\textbf{0.0}$ | $\textbf{92.0}\pm\textbf{9.8}$ | $\textbf{92.0}\pm\textbf{9.8}$

Table 1: Normalized cost and fairness comparison between LP-FAIR (ours) and
competing baselines. The best and second-best values for each column are in
bold and underlined, respectively. Our method outperforms or has performance
comparable to the baselines in terms of the three evaluation metrics. LP-FAIR
is able to increase the clustering fairness while keeping the distance between
individuals smaller. For Normalized Cost, LP-FAIR is 34.5% better than the
best cost baseline, H-S, on average. For fairness, the best baselines are
FairCenter and P-PoF-Alg, which are outperformed by our method by 12.5% on
average.

In this section, we provide an experimental evaluation of our proposed LP-
based algorithm along with six baselines using the cost function from K-means
(unless specified otherwise) on three different datasets. Our evaluation
consists of performance on different metrics (Sec. 4.1), the cluster quality
(Sec. 4.2), and the effect of varying the number of clusters (Sec. 4.3). We
also provide the running time (Supp. C) and additional experiments (Supp. D)
in the Supplementary. Our
implementation‡‡‡https://anonymous.4open.science/r/lp-fair is available online
anonymously.

#### Datasets:

We use three datasets from the UCI repository in our
experiments.§§§https://archive.ics.uci.edu/ml/datasets These datasets have
also been used by previous work [Ber+19, MV20, Chi+17]. We consider the
following attributes for distance and $\gamma$-similarity (fairness):

  * $\rhd$

Adult [Koh+96]: Cluster labels determine whether a person makes over 50K a
year. Distance features are “educationnum” and “age”. The $\gamma$-similarity
features are “salary” and “hoursperweek”.

  * $\rhd$

Bank [MCR14]:  Data from customers of a bank. Distance features are
“duration”, and “age”, $\gamma$-similarity features are “education” and
“balance”.

  * $\rhd$

Diabetes:  Data from diabetes patients from 130 hospitals in the USA from 1999
to 2008. The distance features are “age” and “number-emergency”. The
$\gamma$-similarity features are “time_in_hospital”, “num_lab_procedures”.

We also provide experiments with randomly selected features in the
Supplementary.

#### Algorithms:

We evaluate the following seven algorithms.

  * $\rhd$

Our LP-based approach (LP-FAIR):  Provides probabilistic approximation
guarantees (Algorithm 1). Our implementation is based on Algorithm 2 (Section
3.2).

  * $\rhd$

FairCenter [JKL19]: Ensures fairness based on the existence of a cluster
center nearby. Notice that this algorithm has different fairness criteria than
ours.

  * $\rhd$

Alg-PP [Cha+22]: Optimizes the clusters based on a per-point fairness metric.

  * $\rhd$

Alg-AG [Cha+22]: Optimizes the clusters based on an aggregate fairness metric.

  * $\rhd$

P-PoF-Alg [Cha+22]: Incorporates the Price of Fairness notion and combines the
constraints from Alg-PP and Alg-AG.

  * $\rhd$

Hochbaum-Shmoys (H-S) [HS85]: Uses the triangle inequality to solve a k-center
problem with a 2-approximation algorithm.

  * $\rhd$

Gonzalez [Gon85]: Minimizes the maximum intercluster distance. H-S and
Gonzalez are used as baselines in [Cha+22] for comparison.

#### Performance measures:

We evaluate the algorithms described above using the following metrics:

  * $\rhd$

Normalized Cost: Clustering cost (Equation 1) normalized by the cost of
trivially fair clustering (Definition 4). The normalization removes the effect
of dataset-dependent feature distributions and makes it easier to compare the
results across datasets: $\text{Normalized
Cost}(A)=\frac{Cost(A)}{Cost(\text{{\sc Trivially Fair Clustering}})}$.

  * $\rhd$

Fairness: This denotes the fraction of points that satisfy individual
fairness.

  * $\rhd$

Macro Fairness: This denotes the average of the Fairness metric for each
cluster.

  * $\rhd$

Cluster Imbalance: This measures the imbalance of the found clusters in terms
of their sizes. It is a standard deviation of cluster sizes (i.e., the number
of elements in the cluster). The lower value of imbalance means the clusters
are more balanced.

#### Other settings:

We choose 200 points from each dataset randomly for all the experiments. The
experiments are run five times, and averages and standard deviations are
reported based on these repetitions. Let $\Gamma_{v}$ denote the number of
$\gamma$-matched points of $v$ in the entire dataset and $k^{\prime}$ be the
number of clusters found by the algorithm. The initial $m_{v}$ for each node
$v$ is set as $\frac{\theta}{k}*|\Gamma_{v}|$, then scaled by
$\frac{k}{k^{\prime}}$ (after $k^{\prime}$ is decided) to make the fairness
metric cluster balanced. Unless specified otherwise, we set $\theta$ as $0.5$
in all experiments.

Figure 1: Cost and fairness results, varying the number of clusters ($k$) for
$30k$ random data points using all datasets and methods (better seen in
color). LP-FAIR outperforms or achieves results comparable to the baselines
for all $k$. While increasing $k$ decreases the cost, it is less correlated
with the fairness metric.

###  4.1 Performance

We present the results for our method LP-FAIR and competing baselines using
the normalized cost (the lower the better) and fairness metrics (the higher
the better). Table 1 shows the results produced by all algorithms. LP-FAIR has
a significantly lower cost than the baselines, with a 34.5% lower cost than
the best baseline (H-S) on average. Moreover, LP-FAIR consistently clusters
points fairer. The best baselines for the fairness metric are FairCenter and
P-PoF-Alg, which have consistent performances overall. However, LP-FAIR
outperforms them by 12.5% on average. Furthermore, our method generates
results with less variance compared to the baselines, which shows the
stability of our algorithm.

| Adult | Bank | Diabetes
---|---|---|---
FairCenter | $5.0\pm 0.0$ | $5.0\pm 0.0$ | $4.0\pm 0.63$
Alg-PP | $2.0\pm 0.0$ | $3.2\pm 0.98$ | $2.0\pm 0.0$
Alg-AG | $2.0\pm 0.0$ | $2.8\pm 0.4$ | $1.8\pm 0.4$
P-PoF-Alg | $2.0\pm 0.0$ | $4.0\pm 1.67$ | $2.0\pm 0.0$
H-S | $4.6\pm 0.49$ | $4.6\pm 0.49$ | $4.6\pm 0.49$
Gonzalez | $5.0\pm 0.0$ | $5.0\pm 0.0$ | $5.0\pm 0.0$
LP-FAIR | $5.0\pm 0.0$ | $5.0\pm 0.0$ | $4.8\pm 0.4$
Table 2: The mean and standard deviation of the number of clusters generated by the methods (with $k=5$). Generating fewer clusters generally leads to higher costs (see Table 1). | Adult | Bank | Diabetes
---|---|---|---
FairCenter | $28.4\pm 5.8$ | $30.3\pm 5.2$ | $35.1\pm 6.3$
Alg-PP | $51.4\pm 6.5$ | $37.1\pm 13.6$ | $63.8\pm 14.8$
Alg-AG | $51.4\pm 6.5$ | $42.7\pm 13.8$ | $54.4\pm 28.7$
P-PoF-Alg | $51.4\pm 6.5$ | $29.1\pm 15.5$ | $37.6\pm 23.0$
H-S | $44.5\pm 9.5$ | $34.9\pm 6.2$ | $40.9\pm 13.4$
Gonzalez | $40.9\pm 10.0$ | $33.3\pm 5.7$ | $37.1\pm 10.0$
LP-FAIR | $17.9\pm 2.8$ | $17.6\pm 2.1$ | $15.8\pm 4.8$
Table 3: The mean and standard deviation of cluster imbalance. Imbalanced
clusters result in small clusters where the members might not be individually
fair. LP-FAIR generates clusters with lower imbalance compared to the
baselines.

###  4.2 Quality of Clusters

Cluster quality is also a crucial metric to be considered. Table 2 and Table 3
show generated cluster counts and imbalance, respectively, for all methods and
datasets. Some algorithms use less number of clusters even though the expected
number is $k=5$, which makes their cost higher compared to the one generating
close to $5$. Cluster imbalance is also critical as imbalanced clusters would
result in clusters with a small number of elements in them. The elements in
those clusters are unlikely to be fair, and this will affect individual
fairness as well as macro fairness. LP-FAIR generates more balanced clusters
(low imbalance) compared to the baselines resulting in better fairness.

###  4.3 Varying Number of Clusters

Here, we evaluate the impact of the number of clusters ($k$) on cost and
fairness. We vary the value of $k$ from 3 to 10 and choose $30k$ random points
from each dataset. Figure 1 shows the results. LP-FAIR achieves the best
results for most values of $k$. In general, the cost decreases as the number
of clusters increases. The exceptions are for the cases where the number of
clusters generated is lower than expected. For fairness metrics, LP-FAIR
outperforms or achieves comparable results to all baselines for all datasets.
The values for Fairness do not present a clear trend based on $k$. We provide
results on Macro Fairness in Supplementary D.3.

#### Summary.

A few key observations from the above experiments are as follows: (1) Our
method (LP-FAIR) produces clusters that are individually fair to more than
95.5% points and achieves 88% Macro Fairness on average, outperforming the
baselines in most of the settings; (2) LP-FAIR also produces lower cost or
distance than competing baselines in all settings; (3) LP-FAIR generates
better clusters in terms of numbers and imbalance. This makes LP-FAIR clusters
less costly and more fair compared to the existing competitors.

##  5 Conclusion

We have studied the $k$-clustering problem with individual fairness
constraints. Our notion of fairness is defined in terms of a feature-based
similarity among points and guarantees that each point will have a pre-defined
number of similar points in their cluster. We have provided an algorithm with
probabilistic approximation guarantees for optimizing the cluster distance as
well as ensuring fairness. Finally, the experimental results have shown that
our proposed algorithm can produce $34.5\%$ lower clustering cost and $12.5\%$
higher individual fairness than previous works on average.

truemoreauthor truemorelabelname

## References

  * [Abb+19] Mohsen Abbasi, Sorelle A Friedler, Carlos Scheidegger and Suresh Venkatasubramanian  “Fairness in representation: quantifying stereotyping as a representational harm”  In _Proceedings of the 2019 SIAM International Conference on Data Mining_ , 2019, pp. 801–809
  * [Aga+18] Alekh Agarwal et al.  “A reductions approach to fair classification”  In _International Conference on Machine Learning_ , 2018, pp. 60–69  PMLR
  * [Ahm+19] Sara Ahmadian, Alessandro Epasto, Ravi Kumar and Mohammad Mahdian  “Clustering without over-representation”  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2019, pp. 267–275
  * [Ang+16] Julia Angwin, Jeff Larson, Surya Mattu and Lauren Kirchner  “Machine bias”  In _ProPublica, May_ 23.2016, 2016, pp. 139–159
  * [Bac+19] Arturs Backurs et al.  “Scalable fair clustering”  In _International Conference on Machine Learning_ , 2019, pp. 405–413  PMLR
  * [BTV06] Cristina Bazgan, Zsolt Tuza and Daniel Vanderpooten  “The satisfactory partition problem”  In _Discrete applied mathematics_ 154.8 Elsevier, 2006, pp. 1236–1245
  * [Ber+19] Suman Bera, Deeparnab Chakrabarty, Nicolas Flores and Maryam Negahbani  “Fair algorithms for clustering”  In _Advances in Neural Information Processing Systems_ , 2019, pp. 4955–4966
  * [Ber+19a] Ioana Oriana Bercea et al.  “On the Cost of Essentially Fair Clusterings.”  In _APPROX-RANDOM_ , 2019
  * [Cel+19] L Elisa Celis, Lingxiao Huang, Vijay Keswani and Nisheeth K Vishnoi  “Classification with fairness constraints: A meta-algorithm with provable guarantees”  In _Proceedings of the conference on fairness, accountability, and transparency_ , 2019, pp. 319–328
  * [Cha+22] Darshan Chakrabarti et al.  “A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center”  In _International Conference on Artificial Intelligence and Statistics_ , 2022, pp. 6387–6408  PMLR
  * [CN21] Deeparnab Chakrabarty and Maryam Negahbani  “Better Algorithms for Individually Fair $k$-Clustering”  In _NeurIPS_ , 2021
  * [Chh+22] Rachit Chhaya, Anirban Dasgupta, Jayesh Choudhari and Supratim Shit  “On Coresets for Fair Regression and Individually Fair Clustering.”  In _AISTATS_ , 2022, pp. 9603–9625
  * [Chi+17] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi and Sergei Vassilvitskii  “Fair clustering through fairlets”  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , 2017, pp. 5036–5044
  * [Cho17] Alexandra Chouldechova  “Fair prediction with disparate impact: A study of bias in recidivism prediction instruments”  In _Big data_ 5.2 Mary Ann Liebert, Inc. 140 Huguenot Street, 3rd Floor New Rochelle, NY 10801 USA, 2017, pp. 153–163
  * [CR18] Alexandra Chouldechova and Aaron Roth  “The frontiers of fairness in machine learning”  In _arXiv preprint arXiv:1810.08810_ , 2018
  * [Don+18] Michele Donini et al.  “Empirical risk minimization under fairness constraints”  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , 2018, pp. 2796–2806
  * [Dwo+12] Cynthia Dwork et al.  “Fairness through awareness”  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , 2012, pp. 214–226
  * [Fel+15] Michael Feldman et al.  “Certifying and removing disparate impact”  In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , 2015, pp. 259–268
  * [Fus+20] Andreas Fuster, Paul Goldsmith-Pinkham, Tarun Ramadorai and Ansgar Walther  “Predictably unequal? the effects of machine learning on credit markets”  In _The Effects of Machine Learning on Credit Markets (October 1, 2020)_ , 2020
  * [GSV21] Mehrdad Ghadiri, Samira Samadi and Santosh Vempala  “Socially fair k-means clustering”  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , 2021, pp. 438–448
  * [Gon85] Teofilo F Gonzalez  “Clustering to minimize the maximum intercluster distance”  In _Theoretical computer science_ 38 Elsevier, 1985, pp. 293–306
  * [HS85] Dorit S Hochbaum and David B Shmoys  “A best possible heuristic for the k-center problem”  In _Mathematics of operations research_ 10.2 INFORMS, 1985, pp. 180–184
  * [HJV19] Lingxiao Huang, Shaofeng Jiang and Nisheeth Vishnoi  “Coresets for Clustering with Fairness Constraints”  In _Advances in Neural Information Processing Systems_ 32, 2019, pp. 7589–7600
  * [JKL19] Christopher Jung, Sampath Kannan and Neil Lutz  “A center in your neighborhood: Fairness in facility location”  In _arXiv preprint arXiv:1908.09041_ , 2019
  * [KAM20] Matthäus Kleindessner, Pranjal Awasthi and Jamie Morgenstern  “A notion of individual fairness for clustering”  In _arXiv preprint arXiv:2006.04960_ , 2020
  * [KAM19] Matthäus Kleindessner, Pranjal Awasthi and Jamie Morgenstern  “Fair k-center clustering for data summarization”  In _International Conference on Machine Learning_ , 2019, pp. 3448–3457
  * [Kle+19] Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi and Jamie Morgenstern  “Guarantees for spectral clustering with fairness constraints”  In _International Conference on Machine Learning_ , 2019, pp. 3458–3467
  * [Koh+96] Ron Kohavi  “Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid.”  In _Kdd_ 96, 1996, pp. 202–207
  * [MV20] Sepideh Mahabadi and Ali Vakilian  “Individual fairness for k-clustering”  In _International Conference on Machine Learning_ , 2020, pp. 6586–6596  PMLR
  * [Meh+21] Ninareh Mehrabi et al.  “A survey on bias and fairness in machine learning”  In _ACM Computing Surveys (CSUR)_ 54.6 ACM New York, NY, USA, 2021, pp. 1–35
  * [MCR14] Sérgio Moro, Paulo Cortez and Paulo Rita  “A data-driven approach to predict the success of bank telemarketing”  In _Decision Support Systems_ 62 Elsevier, 2014, pp. 22–31
  * [Obe+19] Ziad Obermeyer, Brian Powers, Christine Vogeli and Sendhil Mullainathan  “Dissecting racial bias in an algorithm used to manage the health of populations”  In _Science_ 366.6464 American Association for the Advancement of Science, 2019, pp. 447–453
  * [RS18] Clemens Rösner and Melanie Schmidt  “Privacy Preserving Clustering with Constraints”  In _45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)_ , 2018  Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
  * [Sam+18] Samira Samadi et al.  “The price of fair PCA: one extra dimension”  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , 2018, pp. 10999–11010
  * [SSS18] Melanie Schmidt, Chris Schwiegelshohn and Christian Sohler  “Fair coresets and streaming algorithms for fair k-means clustering”  In _arXiv preprint arXiv:1812.10854_ , 2018
  * [Sel+19] Andrew D Selbst et al.  “Fairness and abstraction in sociotechnical systems”  In _Proceedings of the conference on fairness, accountability, and transparency_ , 2019, pp. 59–68
  * [VY21] Ali Vakilian and Mustafa Yalçıner  “Improved Approximation Algorithms for Individually Fair Clustering”  In _arXiv preprint arXiv:2106.14043_ , 2021
  * [Yan+09] Jun Yan et al.  “How much can behavioral targeting help online advertising?”  In _Proceedings of the 18th international conference on World wide web_ , 2009, pp. 261–270

##  Appendix A Proof of Theorem 1

###### Proof.

The problem clearly belongs to $\mathsf{NP}$. We now exhibit a reduction from
Satisfactory-Partition. Let
$(\mathcal{G}=(\mathcal{V}=\\{v_{1},v_{2},\ldots,v_{n}\\},\mathcal{E}),(\lambda_{v})_{v\in\mathcal{V}})$
be an arbitrary instance of Satisfactory-Partition. In our Individually Fair
Clustering instance, we have two facilities $l$ and $r$ and the set of points
$U=\\{u_{1},u_{2},\ldots,u_{n}\\}$. We define the distances as

$d(u_{i},l)=\begin{cases}(\lceil\frac{n}{2}\rceil+\beta)^{1/p}&\text{$1\leqslant
i\leqslant\lceil\frac{n}{2}\rceil+1$}\\\
\beta^{1/p}&\text{$\lceil\frac{n}{2}\rceil+2\leqslant i\leqslant
n$}\end{cases}$ $d(u_{i},r)=\begin{cases}\beta^{1/p}&\text{$1\leqslant
i\leqslant\lfloor\frac{n}{2}\rfloor$}\\\
(\lceil\frac{n}{2}\rceil+\beta+1)^{1/p}&\text{$\lfloor\frac{n}{2}\rfloor+1\leqslant
i\leqslant n$}\end{cases}$

for any $\beta\geqslant\frac{\lceil\frac{n}{2}\rceil+1}{2}$. We can easily
verify that the following properties are satisfied:

  1. i)

The distances satisfy the triangle inequality.

  2. ii)

$\sum\limits_{v\in V}d(v,l)^{p}=\sum\limits_{v\in V}d(v,r)^{p}=A$ (say).

  3. iii)

For any $X\subset V,X\neq\emptyset,X\neq V,$ we have $\sum\limits_{v\in
X}d(v,l)^{p}\neq\sum\limits_{v\in X}d(v,r)^{p}$. To see this, let
$s=|X\cap\\{u_{1},u_{2},\ldots,u_{\lceil\frac{n}{2}\rceil+1}\\}|$ and
$t=|X\cap\\{u_{\lfloor\frac{n}{2}\rfloor+1},u_{\lfloor\frac{n}{2}\rfloor+2},\ldots,u_{n}\\}|$
so that $s\leqslant\lceil\frac{n}{2}\rceil+1$ and
$t\leqslant\lceil\frac{n}{2}\rceil$. Then $\sum\limits_{v\in
X}d(v,l)^{p}=s\lceil\frac{n}{2}\rceil+\beta|X|$ and $\sum\limits_{v\in
X}d(v,r)^{p}=t(\lceil\frac{n}{2}\rceil+1)+\beta|X|$. Thus $\sum\limits_{v\in
X}d(v,l)^{p}=\sum\limits_{v\in X}d(v,r)^{p}$ would imply
$s\lceil\frac{n}{2}\rceil=t(\lceil\frac{n}{2}\rceil+1)$ and therefore either
$s=t=0$ or $s=\lceil\frac{n}{2}\rceil+1$ and $t=\lceil\frac{n}{2}\rceil$. In
the former case $X=\emptyset$ while in the latter case $X=V$, a contradiction.

We now describe the feature vector. For every edge $e\in\mathcal{E}$, we have
a feature $\theta_{e}$. A point $u_{i},i\in[n]$ has value $1$ for $\theta_{e}$
if the edge $e$ is incident on the vertex $v_{i}$ in $\mathcal{G}$; otherwise
has value $0$ for $\theta_{e}$. We define the distance function $d^{\prime}$
on feature space as the number of features that two points differ. Finally, we
set the similarity parameter $\gamma=\frac{e^{-m}+e^{-(m-1)}}{2}$. We observe
that two points $u_{i},u_{j},i,j\in[n]$ are $\gamma$-similar if and only if
there is an edge between $v_{i}$ and $v_{j}$ in $\mathcal{G}$. Finally, we
define $m_{v_{i}}=\lambda_{v_{i}}$ for every $i\in[n]$.

We claim that the Satisfactory-Partition instance is a yes instance if and
only if there exists a fair clustering of $U$ with cost $<A$. The “if” part
follows directly, since any fair clustering of $U$ with cost $<A$ must be non-
trivial and fairness ensures that the corresponding partition of $\mathcal{G}$
is satisfactory.

For the “only if” part, let $(X,\bar{X})$ be a non-trivial satisfactory
partition of $\mathcal{G}$. Let $\phi_{1}$ denote the assignment that assigns
all corresponding vertices in $X$ to $l$ and all corresponding vertices in
$\bar{X}$ to $r$, and $\phi_{2}$ denote the assignment that assigns all
vertices in $X$ to $r$ and all vertices in $\bar{X}$ to $l$. Thus,

$\mathrm{Cost}(\phi_{1})=\sum\limits_{v\in
X}d(v,l)^{p}+\sum\limits_{v\in\bar{X}}d(v,r)^{p}$
$\mathrm{Cost}(\phi_{2})=\sum\limits_{v\in
X}d(v,r)^{p}+\sum\limits_{v\in\bar{X}}d(v,l)^{p}$

Thus, $\mathrm{Cost}(\phi_{1})+\mathrm{Cost}(\phi_{2})=2A$. Now, it cannot be
the case that $\mathrm{Cost}(\phi_{1})=\mathrm{Cost}(\phi_{2})=A$, which would
imply that one of the assignments $\phi_{1}$ or $\phi_{2}$ must have cost
$<A$. Suppose to the contrary that $\mathrm{Cost}(\phi_{1})=A$. Thus,
$\sum\limits_{v\in
X}d(v,l)^{p}+\sum\limits_{v\in\bar{X}}d(v,r)^{p}=\sum\limits_{v\in
X}d(v,r)^{p}+\sum\limits_{v\in\bar{X}}d(v,r)^{p}$ and therefore
$\sum\limits_{v\in X}d(v,l)^{p}=\sum\limits_{v\in X}d(v,r)^{p}$, a
contradiction. ∎

##  Appendix B Proof of Theorem 3

###### Proof.

Let $\mathcal{A}$ be an FPTAS for IFC. Similar to the proof of Theorem 2, we
create $n-1$ instances of Satisfactory-Partition where instance $I_{i}$ is as
follows: the set of points is $U=\\{u_{1},\ldots,u_{n}\\}$ and
$m_{v_{i}}=\lambda_{v_{i}}$ for every $i\in[n]$ for all the instances; for
instance $I_{i},i\in[n]$, we introduce $2$ facilities $l$ and $r$ and define
distances as follows:

$d(u_{j},l)=\begin{cases}(1+\beta)^{1/p}&\text{$j=1$}\\\
\beta^{1/p}&\text{$j\in\\{2,3,\ldots,n\\}$}\end{cases}$
$d(u_{j},r)=\begin{cases}(1+\beta)^{1/p}&\text{$j=i+1$}\\\
\beta^{1/p}&\text{$j\in\\{1,2,\ldots,n\\}\setminus\\{i+1\\}$}\end{cases}$

where $\beta$ is any constant $\geqslant 1/2$. The algorithm runs
$\mathcal{B}$ on each of the above instances with approximation parameter
$\varepsilon=\frac{1}{2n\beta}$. If $\mathcal{B}$ returns a solution of cost
less than $1+n\beta$ on any instance, return yes for the Satisfactory-
Partition instance; otherwise, we return no for the Satisfactory-Partition
instance.

Clearly, the cost of the trivial partition is $1+n\beta$. Thus, if
$\mathcal{G}$ does not have a non-trivial satisfactory partition, then
$\mathcal{B}$ must always return the trivial assignment of cost $1+n\beta$ for
all instances. If $\mathcal{G}$ has a satisfactory partition $(X,\bar{X})$,
then as in Theorem 2, there exists an instance with optimal cost $n\beta$.
Thus, the solution returned by $\mathcal{B}$ will have cost at most
$n\beta(1+\frac{1}{2n\beta})<1+n\beta$. Hence, the algorithm is correct. ∎

##  Appendix C Running Time

The most expensive part of our algorithm is the linear programming part where
we use scipy.optimize.linprog Python module. Since our algorithm is
randomized, we run 10 trials, but the best performance is achieved in at most
4 trials. One trial of our algorithm takes 36.7 seconds to finish on the Adult
dataset. Table 4 shows the running time of LP-FAIR and the baselines on the
Adult dataset.

| Adult
---|---
FairCenter |  $16.5$s
Alg-PP |  $11.8$s
Alg-AG |  $9.68$s
P-PoF-Alg |  $9.55$s
H-S |  $7.92$s
Gonzalez |  $7.91$s
LP-FAIR (10 trials) |  $367.5$s
LP-FAIR (4 trials) |  $147$s
LP-FAIR (1 trial) |  $36.7$s
Table 4: The running times of LP-FAIR and baselines on the Adult dataset. We
run our randomized algorithm 10 times, but the best performance is achieved
with at most 4 trials. Figure 2: Macro Fairness results, varying the number of
clusters ($k$) for $30k$ random data points using all datasets and methods
(better seen in color). LP-FAIR outperforms or achieves results comparable to
the baselines for all $k$. Increasing $k$ decreases the macro fairness.

##  Appendix D Additional Experiments

###  D.1 Random Features

We randomly select two distance and two fairness attributes, with five
different random selections, and run each experiment five times. Table 5 shows
that selecting random features does not alter the performance of our method
compared to Table 1, and LP-FAIR is the best performing or has comparable
results to the baselines.

| Normalized Cost | Fairness
---|---|---
| Adult | Bank | Diabetes | Adult | Bank | Diabetes
FairCenter | $0.783$ | $0.535$ | $0.874$ | $91.93$ | $90.90$ | $92.43$
Alg-PP | $0.632$ | $0.415$ | $0.852$ | $76.60$ | $77.38$ | $91.00$
Alg-AG | $0.643$ | $0.432$ | $0.953$ | $78.55$ | $77.75$ | $91.30$
P-PoF-Alg | $0.525$ | $0.382$ | $0.856$ | $76.60$ | $75.15$ | $94.20$
H-S | $0.415$ | $0.526$ | $0.773$ | $92.55$ | 93.60 | $94.90$
Gonzalez | $0.472$ | $0.359$ | $0.548$ | $88.50$ | $91.20$ | $90.50$
LP-FAIR | 0.302 | 0.232 | 0.189 | 93.48 | $92.18$ | 96.43

Table 5: Normalized cost and fairness comparison between LP-FAIR (ours) and
competing baselines with random feature selections. The best and second-best
values for each column are in bold and underlined, respectively. Our method
outperforms or has performance comparable to the baselines in terms of
fairness and cost.

###  D.2 Neglecting Fairness Constraint

We run experiments by setting $m_{v}=0$ in Equation 3 to see the effect of our
fairness constraint. Setting $m_{v}=0$ essentially makes all points fair after
the first cluster assignments, so the cost will be minimized with K-means.
Table 6 shows that setting $m_{v}=0$, as expected, decreases the normalized
cost, whereas the fairness performance becomes much worse.

| Normalized Cost | Fairness
---|---|---
| Adult | Bank | Diabetes | Adult | Bank | Diabetes
LP-FAIR ($m_{v}=0$) | 0.182 | 0.159 | 0.047 | ${89.3}$ | $92.2$ | ${93.4}$
LP-FAIR | $0.194$ | $0.176$ | $0.057$ | 92.3 | 96.3 | 97.9

Table 6: The effect of removing fairness constraint from LP-FAIR. The better
performances are in bold. As expected, our algorithm makes the clusters more
costly while having more individually fair clusters.

###  D.3 Macro Fairness on Varying Number of Clusters

We also evaluate the impact of the number of clusters on the macro fairness
metric. Figure 2 shows that LP-FAIR performs better or has comparable results
to the baselines. Macro Fairness tends to decrease as the number of clusters
increases. That is because $k$ affects the cluster imbalance. Eventually, this
makes some clusters less fair and decreases the average score.

##  Appendix E Reproducibility

The code and datasets are available anonymously here:
https://anonymous.4open.science/r/lp-fair