Robust Fair Clustering: A Novel Fairness Attack and Defense Framework
Authors: Anshuman Chhabra
Peizhao Li
Prasant Mohapatra
Hongfu Liu
Venue: ICLR 2023 poster (2023)
Keywords: Data Clustering
Fairness Attack
Fairness Defense
Consensus Clustering

Abstract: Clustering algorithms are widely used in many societal resource allocation applications, such as loan approvals and candidate recruitment, among others, and hence, biased or unfair model outputs can adversely impact individuals that rely on these applications. To this end, many $\textit{fair}$ clustering approaches have been recently proposed to counteract this issue. Due to the potential for significant harm, it is essential to ensure that fair clustering algorithms provide consistently fair outputs even under adversarial influence. However, fair clustering algorithms have not been studied from an adversarial attack perspective. In contrast to previous research, we seek to bridge this gap and conduct a robustness analysis against fair clustering by proposing a novel $\textit{black-box fairness attack}$. Through comprehensive experiments, we find that state-of-the-art models are highly susceptible to our attack as it can reduce their fairness performance significantly. Finally, we propose Consensus Fair Clustering (CFC), the first $\textit{robust fair clustering}$ approach that transforms consensus clustering into a fair graph partitioning problem, and iteratively learns to generate fair cluster outputs. Experimentally, we observe that CFC is highly robust to the proposed attack and is thus a truly robust fair clustering alternative.

Published as a conference paper at ICLR 2023
ROBUST FAIR CLUSTERING: A NOVEL FAIRNESS ATTACK AND DEFENSE FRAMEWORK
Anshuman Chhabra', Peizhao Li Prasant Mohapatral, and Hongfu Liu
f Department of Computer Science, University of California, Davis [chaaba,, pmohapat ra @ucdavis edu (ttaaaaaaaaaadddaaataaaa
8 Michtom School of Computer Science, Brandeis University [peizhaoli, hongful liu itrpruuuueubbbdeeeeeeeeee @brandeis............. edu
ABSTRACT
Clustering algorithms are widely used in many societal resource allocation ap- plications, such loan approvals and candidate recruitment, among others, and hence, biased or unfair model outputs can adversely impact individuals that rely on these applications. To this end, many fair clustering approaches have been recently proposed to counteract this issue. Due to the potential for significant harm, it is essential to ensure that fair clustering algorithms provide consistently fair outputs even under adversarial influence. However, fair clustering algorithms have not been studied from an adversarial attack perspective. In contrast to previous research, we seek to bridge this gap and conduct robustness analysis against fair clustering by proposing a novel black-box fairness attack. Through comprehensive experiments" we find that state-of-the of-te-of-the-art models are highly susceptible to our attack as it can reduce their fairness performance significantly. Finally, we propose Consensus Fair Clustering (CFC), the first robust fair clustering approach that transforms consensus clustering into a fair graph partitioning problem, and iteratively learns to generate fair cluster outputs. Experimentally, we observe that CFC is highly robust to the proposed attack and is thus truly robust fair clustering alternative.
INTRODUCTION
Machine learning models are ubiquitously utilized in many applications, including high-stakes domains such as loan disbursement (Tsai & Chen Chen)2000), recidivism prediction (Berk et al., [02T Ferguson 2014). hiring and recruitment (Roy et al. 2020 Pombo 2019), among others. For this reason, is paramount importance to ensure that decisions derived from such predictive models unbiased and fair for all individuals treated (Mehrabi al. 2021a) In particular, this is the main motivation behind group-level fair learning approaches (Celis et al. 2021a Li Liu 2022] Song al. 2021), where the goal is generate predictions that do not disparately impact individuals from minority protected groups (such as ethnicity, sex, etc.). It is also worthwhile to note that this problem technically challenging because there exists an inherent fairness- perttesssppffo tradeoff (Dutta et al.) 2020), and thus fairness needs to be improved while ensuring approximate preservation of model predictive performance. This line of research is even more pertinent for data clustering, where error rates cannot be directly assessed using class labels to measure disparate impact. Thus, many approaches have been recently proposed to make clustering models group-level fair (Chierichetti et al. 2017; Backurs al. 2019 Kleindessner et al., 2219A) Chhabra et al., 2022b). In a nutshell, these approaches seek to improve fairness of clustering outputs with respect to some fairness metrics, which ensure that each cluster contains approximately the same proportion of samples from each protected group as they appear in the dataset.
While many fair clustering approaches have been proposed, it of the utmost importance to ensure that these models provide fair outputs even in the presence of an adversary secking to degrade faimesss utility. Although there are some pioneering attempts fairness attacks against supervised learning models (Solans et al.] 2020; Mehrabi et al., 20215). unfortunately, none of these works propose defense approaches. Moreover, the unsupervised scenario, fair clustering algorithms have not yet
"Code available here: https: htttps://gtthb.... httph//..ccm.....maan///////////

---

Published as a conference paper at ICLR 2023
been explored from an adversarial attack perspective, which leaves the whole area of unsupervised fair clustering in potential danger. This leads us to our fundamental research questions in this paper:
Are fair clustering algorithms vulnerable to adversarial attacks that seek to decrease fairness utility, and if such attacks exist, how do we develop an adversarially robust fair clustering model?
Contributions. In this paper, answer both these questions in the affirmative by making the following contributions:
We propose novel black-box adversarial attack against clustering models where the attacker can perturb a small percentage of protected group memberships and yet is able to degrade the fairness performance of state-of-the-a art fair clustering models significantly (Section 2. We also discuss how our attack is critically different from existing adversarial attacks against clustering performance and why they cannot be used for the proposed threat model.
Through extensive experiments using our attack approach, we find that existing fair clustering algorithms are not robust to adversarial influence, and are extremely volatile with regards to fairness utility (Section 2.2). We conduct this analysis on a number of real-world datasets, and for a variety of clustering performance and fairness utility metrics.
To achieve truly robust fair clustering, we propose the Consensus Fair Clustering (CFC) model (Section 3) which is highly resilient to the proposed fairness attack. To the best of our knowledge, CFC is the first defense approach for fairness attacks, which makes it an important contribution to the unsupervised ML community.
Preliminaries and Notation. Given tabular dataset ]={aa)<RRxx with n samples and d fea- tures, each sample z; is associated with a protected group membership g (<x)){[L), where L is the total number of protected groups, and we denote group memberships for the entire dataset as (= N We also have H = [H1, H2, .... H2} and H; is the set of samples that belong to 1-th protected group. A clustering algorithm C(X, K) takes as input the dataset X and a parameter K, and outputs labeling where each sample belongs to one of K clusters (Xu & Wunsch 2005). That is, each point is clustered in one of the sets {C1. C2. .... Ck} with - Cs = X. Based on the above, a group-level fair clustering algorithm F(X, K, G) (Chierichetti al. 2017) can be defined similarly to C, where F takes as input the protected group membership G along with and K, and outputs fair labeling that is expected to be more fair than the clustering obtained via the original unfair/vanilla clustering algorithm with respect to a given fairness utility function é. That is, 6F((, K, G), G) S (CC(X, G). Note that á can be defined to be any fairness utility metric, such as Balance and Entropy (Chhabra et al. 2021a Mchrabi et al. 202
2 FAIRNESS ATTACK
In this section, we study the attack problem on fair clustering. Specifically, we propose a novel attack that aims to reduce the fairness utility of fair clustering algorithms, as opposed to traditional adversarial attacks that seek to decrease clustering performance Cinà et al.] (2022). To our best knowledge, although there are few pioneering attempts toward fairness attack (Mehrabi al. 202Tb; (Solans et al., 2020), all of them consider the supervised setting. Our proposed attack exposes a novel problem prevalent with fair clustering approaches that has not been given considerable attention yet- as the protected group memberships are input to the fair clustering optimization problem, they can be used to disrupt the fairness utility. We study attacks under the black-box setting, where the attacker has no knowledge of the fair clustering algorithm being used. Before formulating the problem in detail, we first define the threat model as the adversary and then elaborate on our proposed attack.
2.1 THREAT MODEL TO ATTACK FAIRNESS
Threat Model. Take the customer segmentation (Liu & Zhou 2017 Nazari & Sheikholeslami 2021 as an example and assume that the sensitive attribute considered is age with 3 protected groups: {youth, adult, senior). Now, we can motivate our threat model as follows: the adversary can control a small portion of individuals' protected group memberships (either through social engineering, exploiting security flaw in the system, etc.); by changing their protected group memberships, the adversary aims to disrupt the faimess utility of the fair algorithm on other uncontrolled groups. That is, there would be overwhelming majority of some protected group samples over others in clusters.
2

---

Published as a conference paper at ICLR 2023
This would adversely affect the youth and senior groups, as they are more vulnerable and less capable of enforcing self preventeon... The attacker could carry out this attack for profit or anarchistic reasons.
Our adversary has partial knowledge of the dataset X but not the fair clustering algorithm F. However, they can query F and observe cluster outputs. This assumption has been used in previous adversarial attack research against clustering (Cinà et al.. 2022 Chhabra et al. 2020a Biggio al. 2013). ). They
can access and switch/change the protected group memberships for a small subset of samples in G, denoted as G GGCG. Our goal of the fairness attack is to change the protected group memberships of samples in G A such that the fairness utility value decreases for the remaining samples in GD GD=GGy G GA. As clustering algorithms (Von Luxburg, 2007) and their fair variants (Kleindessner et al., 2019b) are trained on the input data to generate labeling, this attack is a traiiin-fiime attack. Our attack can also be motivated by considering that fair clustering outputs change with any changes made to protected group memberships G' or the input dataset X. We can formally define the fairness attack as follows:
Definition 2.1 (Faireess Attack), Given a fair clustering algorithm F that can be queried for cluster outputs, dataset X, samples' protected groups G, and GA C G is a small portion of protected groups that an adversary can control, the fairness attack is that the adversary aims to reduce the fairness of clusters outputted via F for samples in GD G GA S G by perturbing G
Attack Optimization Problem. Based the above threat model, the attack optimization problem can be defined analytically. For ease of notation, we define two mapping functions:
n) Takes GA and GD inputs and gives output G ( GD) which is the combined group memberships for the entire dataset. Note that G and GD are interspersed in the entire dataset in an unordered fashion, which motivates the need for this mapping.
0: 0: Takes GD and output cluster labeling from clustering algorithm for the entire dataset as input, returns the cluster labels for only the subset of samples that have group memberships in GD. That is, if the clustering output is C(X, K), we can obtain cluster labels for samples in GDD as (X,, K), GD).
Based on the above notations, we have the following optimization problem for the attacker:
min ((B(O,Gp),Gp) s.t. O FOF((XX,,)) K,X,K,n(GAA Gp)). GA
(I)
The above problem is a two-level hierarchical optimization problem (Anandalingam & Friesz 1992) with optimization variable GA where the lower-level problem is the fair clustering problem F(X, K, (G GD)), and the upper-level problem aims to reduce the fairness utility é of the clustering obtained on the set of samples in GD. Due to the black-box nature of our attack, both the upper- and lower-level problems are highly non-convex and closed-form solutions to the hicrarchical optimization cannot be obtained. In particular, hierarchical optimization even with linear upper- and lower-level problems has been shown to be HP-Hard (Ben-Ayed & Blair 1990), indicating that such problems cannot be solved by exact algorithms. We will thus resort to generally well cell-performin heuristic algorithms for obtaining solutions to the problem in Eq. ①
Solving the Attack Problem. The aforementioned attack problem in Eq. ①T is non-trivial opti- mization problem, where the adversary has to optimize G such that overall clustering fairness for the remaining samples in GD decreases. Since F a black-box and unknown to the attacker, first- or second-order approaches (such as gradient descent) cannot be used to solve the problem. Instead, we utilize zeroth-order optimization algorithms to solve the attack problem. In particular, we use RACOS (Yu et al., 2016) due to its known theoretical guarantees on discrete optimization problems. Moreover, our problem belongs to the same class as protected group memberships are discrete labels.
Discussion. Note that (Cahabra et al. (2021b) propose a theoretically motivated fairness disrupting attack for k-median clustering: however, this cannot be utilized to tackle our research problem for the following reasons: (1) their attack only works for k-median vanilla clustering, thus not constituting a black-box attack on fair algorithms, (2) their attack aims to poison a subset of the input data and not the protected group memberships thus leading to more common threat model different from us. We also cannot use existing adversarial attacks against clustering algorithms (Cinà et al. 2022 Chhabra et al. 2020a) as they aim to reduce clustering performance and do not optimize for a reduction in fairness utility. Thus, these attacks might not always lead to a reduction in fairness utility. Hence, these threat models are considerably different from our case.
3

---

Published as a conference paper at ICLR 2023
0.3
0.3
0.18
0.2
0.38
-0.3
-0.35
0.58
hrsoout Oven
-0.38
Protacee monectedorag
5 Resseae Greus
0.3
4.0
Pre-attack
(b) Post-attack
Figure 1: Pre-attack and post-attack clusters of the SFD fair clustering algorithm on the synthetic toy data. The labels of Cluster A and Cluster B are shown in green and blue, and these samples in two clusters belong to GD. The and A markers represent the two protected groups, and points in red are the attack points that belong to GA. Observe that before the attack, the SFD algorithm obtains a perfect Balance of 1.0. However, after the attack, once the attacker has optimized the protected group memberships for the attack points, the SFD clustering has become less fair with Balance = 0.5.
2.2 RESULTS FOR THE ATTACK
Datasets. We utilize one synthetic and four real-world datasets in our experiments. The details of our synthetic dataset will be illustrated in the below paragraph of Performance on the Toy Dataset. MNIST- USPS: Similar to previous work in deep fair clustering (Li et al. 2020), we construct MNIST-USPS dataset using all the training digital samples from MNIST Lm 1998) and USPS dataset (LeCun 1990), and set the sample source as the protected attribute (MNSST/USPS)) Office-31: The Office-31 dataset (Saenko et al. 2010) was originally used for domain adaptation and contains images from 31 different categories with three distinct source domains: Amazon, Webcam, and DSLR. Each domain contains all the categories but with different shooting angles, lighting conditions, etc. We use DSLR and Webcam for our experiments and let the domain source be the protected attribute for this dataset. Note that we also conduct experiments on the Inverted UCI DIGITS dataset (Xu et al 1992) and Extended Yale Face dataset (Lee et al. 2005), and provide results for these in the appendix.
Fair Clustering Algorithms. We include three state-of-the-an fair clustering algorithms: Fair K-Center (KFC) (Harb& & Lam| 2020)) Fair Spectral Clustering (FSC) (Kleindessner et al.. (2019b) and Scalable Fairlet Decomposition (SFD) (Backurs et al.) 2019) for fairness attack, and these methods employ different traditional clustering algorithms on the backend: KFC uses k-center, SFD uses k-median, and FSC uses spectral clustering. Implementation details and hyperparameter values for these algorithms are provided in Appendix A
Protocol. Fair clustering algorithms, much like their traditional counterparts, are extremely sensitive to initialization (Celebi et al.] 2013). Differences the chosen random seed can lead to widely different fair clustering outputs. Thus. FSC, and KFC fair algorithms and obtain results. We also uniformly randomly sampled G and GD initially select these sets such that the fairness utility (i.e. Balance) before the attack is reasonably high enough value to attack. The size of G is varied from 0% to 30% to see how this affects the attack trends. Furthermore, for the zeroth-order attack optimization, we always attack the Balance metric (unless the fair algorithm always achieves 0 Balance in which case we attack Entropy). Note that Balance is harsher fairness metric than Entropy and hence should lead to a more successful attack. As performance baseline, we also compare with random attack where instead of optimizing G to reduce fairness utility on GD. we uniformly randomly pick group memberships G
10 different random seeds when running the SFD,
Evaluation Metrics. We use four metrics along two dimensions: fairness utility and clustering utility for performance evaluation. For clustering utility, we consider Unsupervised Accuracy (ACC) (Li Ding 2006). and Normalized Mutual Information (NMI) (Strehl & Ghosh] 2002). For fairness utility we consider Balance (Chierichetti et al. 2017) and Entropy (Li et al., (020). The definitions for these metrics are provided in Appendix B These four metrics are commonly used in the fair clustering literature. Note that for each of these metrics, the higher the value obtained, the better the utility. For faireess, Balance is better metric to attack, because value of 0 means that there is a cluster that has 0 samples from one or more protected groups Finally, the attacker does not care about the clustering utility as long changes in utility do not reveal that an attack has occurred.
4

---

Published as a conference paper at ICLR 2023
Entropy
0.400
1000
9.433
Su5h SSSNN
SED Algortti
2000
0,000
20
20
25
30
32
20
25
33
38
11
25
2
38
15
25
2
10,000
5.800
TERNIOO
0.400
9,800
5.000
0,200
0.002
5-200
20
25
30
22
20
25
39
2
35
30
10
15
Susn ISINA
2.55
0.800
2.500
FSC Algorthm
0.400
9,432
TE T7910
0.480
5.230
3000
Susin 1500
0.300
2302
0,250
2.000
0.162
30,000
0.303
KFC
9,100
TE 1700000
8.200
0.200
6.300
0.300
0.242
Rlaaklack
Our allack
Randorn allack
Figure 2: Attack results for MNIST-USPS & Office-31 (x-axis: % of samples attacker can poison).
Performance on the Toy Dataset. To demonstrate the effectiveness the poisoning attack, we also generate a 2-dimensional 20-sample synthetic toy dataset using isotropic Gaussian distribution, with standard deviation 0.12, and centers located at (4,0) and (4.5, 0). Out of these 20 points, we designate 14 to belong GD and the remaining 6 belong G The number of clusters is set to 2. These are visualized in Figure [ We generate cluster outputs using the SFD fair clustering algorithm before the attack (Figure Ta). and after the attack (Figure lb). Before the attack, SFD achieves perfect fairness with Balance of 1.0 as for each protected group and both Cluster A and
1.0, respectively. Moreover, performance utility also high with NMI = 0.695 and ACC 0.928. However, after the attack, fairness utility decreases significantly. The attacker changes protected group memberships of the attack points, and this Ieads the SFD algorithm trying to find a more optimal global solution, but in that, reduces fairness for the points belonging to Gp. Balance drops to 0.5 as for Cluster A and Protected Group 0 we have Balance 1/4 0.5, leading to 50% decrease. Entropy also drops down 0.617 from 0.693. Performance utility decreases this case, but is still satisfactory with NMI 0.397 and ACC 0.785. Thus, it can be seen that our attack can disrupt the fairness of fair clustering algorithms significantly.
4/8 Cluster B. we have Balance 7/14 1.0 and 3/6
7/14
7/14
Performance on Real-World Datasets. We show the pre-ate pre-attack and post-attack results MNIST-USPE and Office-31 by our attack and random attack in Figure 2 It can be observed that our fairness attack consistently outperforms the random attack baseline in terms both fairness metrics: Balance and Entropy. Further, our attack always leads to lower fairness metric values than the pre-attack values obtained, while this is often not the case for the random attack, Balance and Entropy increase for the random attack on the FSC algorithm on Office-31 dataset. Interestingly, even though do not optimize for this, clustering performance utility (NMI and ACC) do not drop significantly and even increase frequently. For example, NMI/ACC for FSC Office-31 (Figure 2 Row 4, Column 3-4) and NMI/ACC for KFC on MNIST-USEE (Figure 2 Row 5, Column 3-4). Thus, the attacker can easily subvert the defense as the clustering performance before and after the attack does not decrease drastically and at times even increases. We also conduct the Dolmogorov-Sminge statistical test
5

---

Published as a conference paper at ICLR 2023
Table Results for our attack and random attack when 15% group membership labels are switched.
MNIST- USPS
Algorithms
Metries
Pre-Attack
Our Attack
Change (%)
Random Attack
Change (%)
Balance
0.286 +: 0.065
0.000 = 0.000
(-)100.0
0.000 = 0.000
(-)100.0
Entropy
3.070 +: 0.155
1.621 + 0.108
(-)47.12
1.743 0.156
(-)43.23
SFD
NMI
0.320 + 0.033
0.302 = 0.007
(-)5.488
0.301 = 0.011
(-15,847
ACC
0.427 + 0.040
0.378 + 0.015
(-111554
0.374 0.026
(-112.35
Balance
0.000 + 0.000
0.000 0.000
(-100.0
0.000 = 0.000
(-1000.0
Entropy
0.275 + 0.077
0.251 0.041
(-18.576
0.295 0.036
(+)7.598
FSC
NMI
0.549 + 0.011
0.544 = 0.007
(-00,00
0.552 0.006
(+)0.491
ACC
0.448 +: 0.012
0.457 = 0.002
(+)1.911
0.455 = 0.002
(+)1.50
Balance
0.730 +: 0.250
0.332 + 0.307
(-)51.87
0.608 = 0.237
(-16.72
KFC
Entropy
2.607 + 0.607
2.343 = 0.444
(-)10.12
2.383 = 0,490
(-18,595
NMI
0.072 + 0.024
0.076 0.029
(+)5.812
0.076 0.027
(+)5.330
ACC
0.168 + 0.026
0.176 = 0.034
(+)4,581
0.174 = 0.031
(+33,419
Office-3
Algorithms
Metrics
Pre-Attack
Our Attack
Change (%)
Random Attack
Change (%)
Balance
0.484 +: 0.129
0.062 + 0.080
(-187.21
0.212 = 0.188
(-)56,34
Entropy
10.01 + 0.098
9.675 - 0.187
(-13.309
9.745 = 0.181
(-12.581
SFD
NMI
0.801 + 0.050
0.768 0.058
(-)4.110
U.795 0.053
(-)0.726
ACC
0.088 + 0.082
0.624 = 0.098
(-19.397
0.668 = 0.091
(-)2,908
Balance
0.041 + 0.122
0,000 = 0.000
(-)100.0
0.086 = 0.172
(+)110.8
Entropy
9.538 + 0.113
9.443 = 0.178
(-)0.997
9.558 = 0.226
(+)0.207
FSC
NMI
0.669 + 0.014
0.693 0.014
(+)3.659
0,693 0.022
(+)3.711
ACC
0.411 + 0.014
0.432 = 0.027
(+19.904
0.417 0.030
(+)8.817
Balance
0.250 + 0.310
0.037 = 0.172
(-)77.07
0,191 = 0.301
(-122.55
Entropy
9.997 +: 0.315
9.919 + 0.189
(-)0.786
9.992 0.250
(-)0.051
KFC
NMI
0.064
0.391
(-)0.483
0.393 0.067
(-)0.160
ACC
0.265 + 0.048
0.266 0.049
(+)0.032
U.265 0.051
(-)0.162
Massey Jr 1951) between our attack and the random attack result distribution for the fairness utility metrics (Balance and Entropy) to see if the mean distributions are significantly different. We find that for the Office-31 dataset our attack is statistically significant in terms of fairness values and obtains p-values of less than 0.01. For MNIST- USS, the results are also statistically significant except for the cases when the utility reduces quickly to the same value. For example, it can be seen that Balance goes to for SFD on MNIST-USPS in Figure 2 (Row 1, Column 1) fairly quickly. For these distributions, it is intuitive why we cannot obtain statistically significant results, as the two attack distributions become identical. We provide detailed test statisties in Appendix C We also provide the attack performance Inverted UCI DIGITS dataset (Xu et al. 1992) and Extended Yale Face B dataset (Lee et al. 2005) in Appendix
Furthermore, to better compare attack with the random attack, we present the results when 15% group memberships are switched in Table As can be seen, for all fair clustering algorithms and datasets, our attack leads to a more significant reduction in faimess utility for both the MNIST-USPS and Office-31 datasets. In fact, as mentioned before, the random attack at times leads to an increase in fairness utility compared to before the attack (refer to FSC Balance/Entropy on Office-31). In contrast, our attack always leads to reduction in fairness performance. For example, for the KFC algorithm and Office-31 dataset, our attack achieves reduction in Balance of 77.07% whereas the random attack reduces Balance by only 22.52%. However, it is important to note here that existing fair clustering algorithms are very volatile in terms of performance, as the random attack can also lead to fairness performance drops, especially for the SFD algorithm (refer to Figure 2 for visual analysis). This further motivates the need for a more robust fair clustering algorithm.
3 FAIRNESS DEFENSE: CONSENSUS FAIR CLUSTERING
Beyond proposing a fairness attack, we also provide our defense against the proposed attack. Accord- ing to the faimess attack in Definition 2.1] we also provide a definition of robust fair clustering to defend against the fairness attack, followed by our proposed defense algorithm.
Definition 3.1 (Robust Fair Clustering). Given the dataset X, samples' protected groups G, and GA C G is small portion of protected groups that an adversary can control, fair clustering

---

Published as a conference paper at ICLR 2023
algoritlum F is considered to be robust to the fairness attack if the change in fairesss utility GD= =G= GA S G before the attack and after the attack is by a marginal amount, or if the fairness utility G increases after the attack.
3.1 DEFENSE ALGORITHM TO FAIRNESS ATTACK
To achieve robust fair clustering, our defense utilizes consensus cluster- ing (Liu et al. 2019; Fred & Jain 2005 Lourenço al., 2015, Fern & Brod-
SinstStage
Second Stage
ML Network
lcy 2004) combined with fairness con-
Cluster Assignment
straints to ensure that cluster outputs are robust to the above attack. Consensus clustering has been widely renowned for its robustness and consistency prop- erties but to the best of our knowledge, no other work has utilized consensus clustering concepts in the fair clustering scenario. Specifically, we propose Con- sensus Fair Clustering (CFC) shown in Figure which first transforms the consensus clustering problem into a graph partitioning problem, and then utilizes a novel graph-based neural network architecture to learn representations for fair clustering. CFC has two stages to tackle the attack challenge at the data and algorithm level. The first stage is to sample subset of training data and run cluster analysis to obtain the basic partition and the co-association matrix. Since poisoned samples are a tiny portion the whole training data, the probability these being selected into the subset is also small, which decreases their negative impact. In the second stage, CFC fuses the basic partitions with a fairness constraint and further enhances the algorithmic robustness.
Activatoo
Loyel
Dropout
Unear
Loss
L,
Genear Covasorr ahoo
Commerthe
Mano
C S)
Figure 3: Our proposed CFC framework.
First Stage: Generating Co-Association Matrix. In this first stage of CFC, we will generate basic partitions II = {T1, T22 ..., }. For each basic partition T;, we first get sub dataset X, by random sample/feature selection and run K-means (Lloyd 1982) obtain a basic partition ,,. Such process is repeated r times such that X X. Given that u and u are two samples and π. TT( is the label category of u in basic partition म,. and following the procedure of consensus clustering, we summarize the basic partitions into a co-association matrix S E R=x" as Sae = Ei= T (u). (u)). where 5(a, 6) if a = b; otherwise. d(a,b) b) 0. The co-association matrix not only summarizes the categorical information of basic partitions into pair-wise relationship, but also provides an opportunity to transform consensus clustering into a graph partitioning problem, where we can learn a fair graph embedding that is resilient to the protected group membership poisoning attack.
Second Stage: Learning Graph Embeddings for Fair Clustering. In the second stage of CFC, we aim to find an optimal consensus and fair partition based on the feature matrix X, basic partitions II, and sample sensitive attributes G. The objective function of our CFC consists of a self-supervised contrastive loss. fair clustering loss, and structural preservation loss.
Self-supervised Contrastive Loss. To learn a fair graph embedding using X, S, and G, we use a few components inspired by recently proposed simple graph classification framework called Graph- MLP (Hu et al. 2021), which does not require message- message-passing between nodes and outperforms the classical message- saaaggeepasiigggggo GNN methods in various tasks (Wang et al. [202]] Yin et al., 2022). Specifically, it employs the neighboring contrastiveness and considers the Rt-hop neighbors to each node as the positive samples, and the remaining nodes as negative samples. The loss ensures that positive samples remain closer to the node, and negative samples remain farther away based on feature distance. Let Tuv Stft and the co-association matrix, sim denote cosine similarity. and r be the temperature parameter, then we can write the loss as follows:
n
Σd [a Tia exp(sim (2, Za)/T) Σ
Lc(Z.S)
n log
1 byyq exp( (xp(sim( Zz, Z,)T))
Fair Clustering Loss. Similar other deep clustering approaches (Xie et al. 2016 Li et al. 2020). we employ a clustering assignment layer based on Student t-distribution and obtain soft cluster assignments P. We also include fairnsss regularization term using auxiliary target distribution Q
7

---

Published as a conference paper at ICLR 2023
Table 2: Pre/post-attack performance when 15% group membership labels are switched.
Office-31
MNIST-USPS
Algoritums
Metrics
Pre-Attack
Post Attack
Change (%)
Pre-Attack
Post Attack
Change (%)
Balance
0.609 + 0.081
0.606 0.047
(-)0.466
0.442 + 0.002
0.373 0.090
(-)15,54
Entropy
5.995 + 0.325
6.009 0.270
(+)0.229
2.576 + 0.088
2.626 0.136
(+)19522
CFC
NMI
0.690 + 0.019
0.698 0.013
(+)1.236
0.209 + 0.007
0.287 + 0.008
(+)6.749
ACC
0.508 + 0.021
0.511 + 0.018
(+)0.643
0.385 + 0.002
0.405 + 0.015
(+)5,343
Balance
0.484 + 0.129
0.062 + 0.080
(-)87,21
0.286 + 0.0G5
0.000 + 0.000
(-)100.0
Entropy
10.01 + 0.098
9.675 0.187
(-33.309
3.070 + 0.155
1.621 0.108
(-)47.19
SFD
NMI
0.801 + 0.050
0.768 0.058
(-)4.110
0.320 + 0.033
0.302 0.007
(-)5,488
ACC
0.688 + 0.082
0.624 + 0.098
(-)9.397
0.427 + 0.040
0.378 + 0.015
(-)11.54
Balance
0.041 + 0.122
0.000 0.000
6-100.0
0.000 + 0.000
0.000 0.000
C-100.0
Entropy
9.538 + 0.113
9.443 + 0.178
(-)0.997
0.275 + 0.077
0.251 + 0.041
(-)8,576
FSC
NMI
0.669 + 0.014
0.693
0.014
(+)3.659
0.549 + 0.011
0.544 0.007
(-)0.007
ACC
+: 0.014
0.452 0.027
(+)9,904
+ 0.012
0.457
0.002
(+)1997
Balance
0.250 +: 0.310
0.057 0.172
(-777.07
0.730 +: 0.250
0.352
0.307
(-551.87
KFC
Entropy
9.997 + 0.315
9.919 + 0.189
(-)0.786
2.607 + 0.607
2.343 0.444
()10.1
NMI
0.393 +: 0.064
0.391 + 0.063
(-)0.483
0.072 + 0.024
0.076 + 0.029
(+)5.812
ACC 0.265 + 0.048
0.266 0.049
(+)0.082
0.168 + 0.026
0.176 0.034
(+)4.581
to ensure that the cluster assignments obtained from the learned embeddings = E Z are fair. We abuse notation slightly and denote the corresponding learned representation of sample x E X as 2n E Z. Also let P represent the probability of sample X being assigned to the k-th cluster, Yk [K]. More precisely, y represents the assigned confidence hetween representation 2n and cluster centroid Ck in the embedding space. The fair clustering loss term then be written
Gz (L(])K)))P))) = Σ Σ
Pk log
PE
(3)
9
9E[1.] H K]
(xE) Eo' (M
[1+1|=,-01100- LEE (++ -ppا)p- and oh EveLK (pt)) E PT
where pK
Structural Preservation Loss. Since optimizing the fair clustering loss Cy can lead to a degenerate solution where the learned representation reduces to constant function (Li et al. 2020), a well-known structural preservation loss term for each protected group. Since this loss is applied to the final partitions obtained we omit it for clarity from Figure 3 which shows the internal CFC architecture. Let Po be the obtained soft cluster assignments for protected group using CFC, and Jg be the cluster assignments for group g obtained using any other well-performing fair clustering algorithm. We can then define this loss as originally proposed in Li et al. (2020):
employ
Cp = Σ P.p J 11.
BE[L]
The overall objective for CFC algorithm can be written as L. +atta+++Bpppp where a, 3 are parameters used to control trade-off between individual losses. CFC can then be used to generate hard cluster label predictions using the soft cluster assignments P E Roxk
3.2 RESULTS FOR THE DEFENSE
To showease the efficacy of our CFC defense algorithm, we utilize the same datasets and fair clustering algorithms considered in the experiments for the attack section. Specifically, we show results when 15% of protected group membership labels can be switched for the adversary Table (over 10 individual runs). Here, present pre-attack and post-attack fairness utility (Balance, Entropy) and clustering utility (NMI, ACC) values. We also denote the percent change in these evaluation metrics before the attack and after the attack for further analysis. The detailed implementation and hyperparameter choices for CFC can be found in Appendix [F] The results for Inverted UCI DIGITS and Extended Yale Face B datasets
provided in Appendix G
As can be seen in Table 6 our CFC clustering algorithm achieves fairness utility and clustering performance utility superlative the other state-of-the-at fair clustering algorithms. In particular,
8

---

Published as a conference paper at ICLR 2023
CFC does not optimize for only fairness utility over clustering performance utility but for both of these jointly, which is not the case for the other fair clustering algorithmms. Post-attack performance of CFC on all datasets is also always better compared to the other fair algorithms where Balance often drops close to O. This indicates that fairness utility has completely been disrupted for these algorithms and the adversary is successful. For CFC, post-attack fairesss and performance values are at par with their pre-attack values, and at times even better than before the attack. For example, for Entropy, NMI, and ACC metrics, CFC has even better fairness and clustering performance after the attack than before it is undertaken on both the Office-3/ / and SANIST-USP? datasets. Balance also decreases only by a marginal amount. Whereas for the other fair clustering algorithms SFD, FSC, and KFC. faimess has been completely disrupted through the poisoning attack. For all the other algorithms, Entropy and Balance decrease significantly with more than 10% and 85% decrease on average, respectively. Moreover, we provide more in-depth analysis of CFC performance in Appendix H
4 RELATED WORKS
Fair Clustering. Fair clustering aims to conduct unsupervised cluster analysis without encoding any bias into the instance assignments. Cluster fairness is evaluated using Balance, i.e,, to ensure that the size of sensitive demographic subgroups in any cluster follows the overall demographic ratio (Chierichetti et al. 2017). Some approaches use fairlets, where they decompose original data into multiple small and balanced partitions first, and use k-center or k-means clustering to get fair clusters (Schmidt et al. 2018 Backurs et al., 2019). There are also works that extend fair clustering into other clustering paradigms like spectral clustering (Kleindessner al.] (009b),, hierarchical clustering (Chhabra et al. 2020b), and deep clustering (Li et al.) [0200] Waag & Davidson 2011)). In this work, beyond solutions fair clustering, we investigate the vulnerabilities of fair clustering and corresponding defense algorithms.
Adversarial Attacks on Clustering. Recently, white-box and black-box adversarial attacks have been proposed against a number of different clustering algorithms (Chhabra et al. [2022a). For single- linkage hierarchical clustering, (Biggio et al. 2013) first proposed the poisoning and obfuscation attack settings, and provided algorithms that aimed to reduce clustering performance. In (Biggio et al. 2014) the authors extended this work to complete-linkage hierarchical clustering and (Crussell & Kegelmeyer| 2015) proposed a white-box poisoning attack for DBSCAN (Ester et al.) 1996) clustering. On the other hand, (Chhabra et al.) 2020a Cinà et al. 2022) proposed black-box adversarial attacks that poison a small number of samples in the input data, so that when clustering is undertaken on the poisoned dataset, other unperturbed samples change cluster memberships, leading to a drop in overall clustering utility. As mentioned before, our attack is significantly different from these approaches, as it attacks the fairness utility of fair clustering algorithms instead of their clustering performance.
Robustness of Fairness. The robustness of fairness is the study of how algorithmic fairness could be violated or preserved under adversarial attacks or random perturbations. [Solans et al. (2020) and Mehrabi al. (2021b) propose poisoning attack frameworks trying to violate the predictive parity among subgroups in classification. Celis et al.] (2021a) and Celis et al. (2021b) also work on classification and study fairness under perturbations on protected attributes. Differently, we turn our sights into an unsupervised scenario and study how attacks could degrade the fairness in clustering.
CONCLUSION
In this paper, we studied the fairness attack and defense problem. In particular, we proposed a novel black-box attack against fair clustering algorithms that works by perturbing a small percentage of samples' protected group memberships. For self-completennsss, we also proposed a defense algorithm, named Consensus Fair Clustering (CFC), a novel fair clustering approach that utilizes consensus clustering along with fairness constraints to output robust and fair clusters. Conceptually, CFC combines consensus clustering with fair graph representation learning, which ensures that clusters are resilient to the fairness attack at both data and algorithm levels while possessing high clustering and fairness utility. Through extensive experiments on several real-world datasets using this fairness attack, we found that existing state-of-the- fair clustering algorithms are highly susceptible to adversarial influence and their faimness utility can be reduced significantly. On the contrary, our proposed CFC algorithm is highly effective and robust it resists the proposed fairness attack well.
9

---

Published as a conference paper at ICLR 2023
6 ETHICS STATEMENT
In this paper, we have proposed a novel adversarial attack that aims to reduce the fairness utility of fair clustering models. Furthermore, we also propose defense model based on consensus clustering and fair graph representation learning that is robust to the aforementioned attack. Both the proposed attack and the defense are important contributions that help facilitate ethics in ML research, due to a number of key reasons. First, there are very few studies that investigate the influence of adversaries on the fairness of unsupervised models (such as clustering). and hence, our work paves the way for future work that can study the effect of such attacks in other different learning models. Understanding the security vulnerabilities of models, especially with regard to fairness is the first step to developing models that are more robust to such attacks. Second, even though our attack approach can have negative societal impact in the wrong hands, we propose a defense approach that can be used as a deterrent against such attacks. Third, we believe our defense approach can serve starting point for the development of more robust and fair ML models. Through this work, we seek to underscore the need for making fair clustering models robust adversarial influence, and hence, drive the development of truly fair robust clustering models.
REFERENCES
G Anandalingam and Terry L Friesz. Hierarchical optimization: An introduction. Annals of Operations Research, 34(1):1-11, 1992.
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In Proceedings of the International Conference on Machine Learning, 2019.
Omar Ben-Ayed and Charles E Blair. Computational difficulties of bilevel linear programming. Operations Research, 38())556--66,, 1990.
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3 44, 2021.
Battista Biggio, Ignazio Pillai, Samuel Rota Bulò, Davide Ariu, Marcello Pelillo, and Fabio Roli. Is data clustering in adversarial settings secure? In Proceedings of ACM Workshop Artificial Intelligence and Security, 2013.
Battista Biggio, Samuel Rota Buld, Ignazio Pillai, Michele Mura, Eyasu Zemene Mequanint, Marcello Pelillo, and Fabio Roli. Poisoning complete-lintee linkae hierarchical clustering. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition and Structural and Syntactic Puttern Recognition, 2014.
M Emre Celebi, Hassan A Kingravi, and Patricio A Vela. A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Systems with Applications, 40(1):200-210 2013.
L Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K Vishnoi. Fair classification with noisy protected attributes: A framework with provable guarantees. In Proceedings of International Conference on Machine Learning, 2021a.
L Elisa Celis, Anay Mehrotra, and Nisheeth Vishnoi. Fair classification with adversarial perturbations. Advances in Neural Information Processing Systems, 2021b.
Anshuman Chhabra, Abhishek Roy, and Prasant Mohapatra. Suspicion-free adversarial attacks on clustering algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020a.
Anshuman Chhabra, Vidushi Vashishth, and Prasant Mohapatra. Fair algorithms for hicrarchical agglomerative clustering, arXiv preprint arXiv:2005.03197 20200
Anshuman Chhabra, Karina Masalkovaité, and Prasant Mohapatra. An overview of fairness in clustering. IEEE Access, 2021a.
Anshuman Chhabra, Adish Singla, and Prasant Mohapatra. Faimess degrading adversarial attacks against clustering algorithms. arXiv preprint arXiv:21 12020, 2021b.
10

---

Published as a conference paper at ICLR 2023
Anshuman Chhabra, Ashwin Sekhari, and Prasant Mohapatra. On the robustness of deep clustering models: Adversarial attacks and defenses. arXiv preprint arXiv:2210001940, 2022a.
Anshuman Chhabra, Adish Singla, and Prasant Mohapatra, Fair clustering using antidote data. In Algorithmic Fairness through the Lens of Causality and Robustness workshop, pp. 19-39. PMLR, 2022b.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in Neural Information Processing Systems, 2017.
Antonio Emanuele Cinà, Alessandro Torcinovich, and Marcello Pelillo. A black-box adversarial attack for poisoning clustering. Puttern Recognition, 122:108306, 2022.
Jonathan Crussell and Philip Kegelmeyer. Attacking dbscan for fun and profit. Proceedings of
SIAM International Conference Data Mining, 2015.
Sanghamitra Dutta, Dennis Wei, Hazar Yueksel, Pin- Pin-Yu Chen, Sijia Liu, and Kush Varshney. Is there trade-off between fairness and accuracy? a perspective using mismatched hypothesis testing, In Proceedings of the International Conference on Machine Learning. 2020.
Martin Ester, Hans-Peter Peter Kriegel, Jörg Sander, Xiaowei Xu, et A density- based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 1996.
Andrew Guthrie Ferguson, Big data and predictive reasonable suspicion. University of Pennsylvania Law Review, 163:327, 2014.
Xiaoli Zhang Fern and Carla Brodley. Solving cluster ensemble problems by bipartite graph partitioning, In Proceedings of the International Conference Machine Learning, 2004.
Ana LN Fred and Anil K Jain. Combining multiple clusterings using evidence accumulation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(6)):35-850, 2005.
Elfarouk Harb and Ho Shan Lam. Kfc: A scalable approximation algorithm for k- center fair clustering. Advances in Neural Information Processing Systems, 2020.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint
SEfi:1600608415, 2016.
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: node classification without message passing in graph. arXiv preprint arXiv: 106.000.0000 106.04051, 2021.
Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data
summarization. In Proceedings of the International Conference on Machine Learning, 2019a.
Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstem. Guarantees for spectral clustering with fairness constraints. Proceedings of the International Conference on Machine Learning, 2019b.
Harold W Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 2(1-2):83-97, 1955.
Yann LeCun. USPS Dataset. https://wwwt http:s/www..aaaoooooo///////aaa/ 1990. [Online; accessed June 30th 2022].
Yann LeCun. MNIST Dataset. http:://aan. http://aw....cc.c.co////////////
1998. [Online;
accessed June 30th 2022].
Kuang-Chih Lee, Jeffrey Ho, and David Kriegman. Acquiring linear subspaces for face recognition under variable lighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(5): 684-698, 2005.
Peizhao Li and Hongfu Liu. Achieving faimess at no utility cost via data reweighing with influence. In Proceedings of the 39th International Conference Machine Learning, 2022.
11

---

Published as a conference paper at ICLR 2023
Peizhao Li, Han Zhao, and Hongfu Liu. Deep fair clustering for visual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.
Tao Li and Chris Ding. The Relationships Among Various Nonnegative Matrix Factorization Methods for Clustering. In Proceedings of the International Conference on Data Mining, 2006.
Hongfu Liu, Zhiqiang Tao, and Zhengming Ding. Consensus clustering: an embedding perspective, extension and beyond. arXiv preprint arXiv: 190.0990000000, 2019.
Jian Liu and Y Zhou. Customer segmentation and fairness: A queueing perspective. Technical report, Working paper, University of Washington, Seattle, 2017.
Stuart Lloyd. Least squares quantization in pem. IEEE Transactions Information Theory, 28(2):
129-137, 1982.
André Lourenço, Samuel Rota Bulò, Nicola Rebagliati, Ana LN Fred, Mário AT Figueiredo, and Marcello Pelillo. Probabilistic consensus clustering using evidence accumulation. Machine Learning, 98(1): 98(1):331-357,201
Frank J Massey Jr. The kolmogorov-smmrrov test for goodness of fit. Journal of the American statistical Association, 46(253):68-78, 1951.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galsryan. A survey on bias and fairness in machine learning. ACM Computing Surveys, 54(6):1-35, 2021a.
Ninareh Mehrabi, Muhammad Naveed, Fred Morstatter, and Aram Galstyan. Exacerbating algorith- mic bias through fairness attacks. In Proceedings of the AAAI Conference Artificial Intelligence, 2021b.
Mohsen Nazari and Seyed Parham Sheikholeslami. The impact of price segmentation based on customer characteristics, product bundle or product features on price fairness perceptions. Journal of International Marketing Modeling, 2(2):104-11 101-1144,,, 114, 2021.
José Luís Fava de Matos Pombo. Landing the right machine learning approach match candidates with jobs applying semantic embeddings. PhD thesis, 2019.
Pradeep Kumar Roy, Sarabjeet Singh Chowdhary, and Rocky Bhatia. machine learning approach for automation of resume recommendation system. Procedia Computer Science, 167:2318-2322 2020.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In Proceedings of the European Conference on Computer Vision, 2010.
Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means clustering. arXiv preprint arXiv: 10854, 2018
Claude Elwood Shannon. A Mathematical Theory of Communication. The Bell System Technical Journal, 27(3):379 423, 1948.
David Solans, Battista Biggio, and Carlos Castillo. Poisoning attacks algorithmic fairness. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2020.
Hanyu Song, Peizhao Li, and Hongfu Liu. Deep clustering based fair outlier detection. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, 2021.
Alexander Strehl and Joydeep Ghosh. Cluster Ensembles-a Knowledge Reuse Framework for Combining Multiple Partitions. Journal of Machine Learning Research, 3:583-617, 2002.
Chih-Fong Tsai and Ming-Lun Chen. Credit rating by hybrid machine learning techniques. Applied Soft Computing, 10(2):374-380, 2010.
Ulikee Von Luxburg. tutorial on spectral clustering. Statistics and Computing, 17(4):395-44 416, 2007.
12

---

Published as a conference paper at ICLR 2023
Bokun Wang and lan Davidson. Towards fair deep clustering with multi-state protected variables. 2019.
arXiv preprint
Hao Wang, Defu Lian, Hanghang Tong, Qi Liu, Zhenya Huang, and Enhong Chen. Decoupled representation learning for attributed networks. IEEE Transactions on Knowledge and Data Engineering, 2021.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In Proceedings of the International Conference on Machine Learning. 2016.
Lei Xu, Adam Krzyzak, and Ching Y Suen. Methods of combining multiple classifiers and their applications to handwriting recognition. IEEE Transactions Systems, Man, and Cybernetics, 22 13::488435, 1992.
Rui Xu and Donald Wunsch. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3):645-61) 678, 2005.
Nan Yin, Fuli Feng, Zhigang Luo, Xiang Zhang, Wenjie Wang, Xiao Luo, Chong Chen, and Xian- Sheng Hua. Dynamic hypergraph convolutional network. In Proceedings of the IEEE International Conference on Data Engineering, 2022.
Yang Yu, Hong Qian, and Yi-Qi Hu. Derivative-free optimization via classification. In Proceedings of the AAAI Conference Artificial Intelligence, 2016.
Hongjing Zhang and Ian Davidson. Deep fair discriminative clustering. arXiv:2105.144 144,,,,,,,,,,,6, 2021.
arXiv preprint
13

---

Published as a conference paper at ICLR 2023
A IMPLEMENTATION OF KFC, FSC, SFD ALGORITHMS
We implemented the FSC, SFD, and KFC fair algorithms in Python, using the authors' implementa- tions reference in case they were not written Python. To this end, we generally default using the hyperparameters for these algorithms as provided in the original implementations. However, if needed, we also tuned the hyperparameter values as maximize performance on the unsupervised faireess metrics (such as Balance) as this allows us to attack fairness better. Note that this is still an unsupervised parameter selection strategy as Balance is fully unsupervised metric, as takes only the clustering outputs and protected group memberships as input, which are also provided input to the fair clustering algorithms, Such parameter tuning has also been done previous fair clustering work (Kleindessner al. 2019b Zhang & Davidson, 2021).
For SFD, we set the parameters p 2, q = 5 for all datasets except DIGITS for which we set g,g 5. For FSC we use the default parameters and use the nearest neighbors approach Von Luxburg (207)) for creating the input graph for which we set the number of neighbors = 3 for all datasets. For KFC use the default parameter value of 0.1.
B DEFINITIONS FOR METRICS
NMI. Normalized Mutual Information is essentially normalized version of the widely used mutual information metric. Let denote the mutual information metric Shamnon (1948), E denote Shannon's entropy Shannon (1948), L denote the cluster assignment labels, and Y denote the ground truth labels. Then we can define NMI as:
I(Y,L) NMI (1/2) (E(Y) + E(L)
ACC. This is the unsupervised equivalent of the traditional classification accuracy. Let there be mapping function y that computes all possible mappings between ground truth labels and possible cluster assignments for some samples. Also, let Y, L, denote the ground truth label and cluster assignment label for the i-th sample, respectively. Then we can define ACC as:
ACC max i= D p(L.)
Balance. Balance is fairness metric proposed by (Chierichetti al. 2017) which lies between (least fair) and 1 (most fair). Let there be m protected groups for given dataset X. Then, define r% and r be the proportion of samples of the dataset belonging to protected group g and the proportion of samples in cluster & E [K] belonging to protected group g. The Balance fairness notion then defined over all clusters and protected groups as:
Balance
min min
kE[K].,E[m]
Entropy. Entropy is a fairness metric proposed by (Li et al. 2020) and similar to Balance, higher values of Entropy, mean that clusters have more fairness. Let No.g be the containing the samples of the dataset X that belong to both the cluster A E [K] and the protected group g. Further, let n& be the number of samples in cluster Then Entropy for group g is defined as follows:
NK.gl
[N
Entropy(g) (g)
Σ KE[K]
log
7kk
Note that in the paper, we take the average Entropy over all groups.
TTuning hyperparameters using NMI/ACC or other performance metrics that take the ground truth cluster labels as input, would violate the unsupervised nature of the clustering problem. Such mapping function be computed optimally using the Hungarian assignment Kuhn 1955
14

---

Published as a conference paper at ICLR 2023
C STATISTICAL SIGNIFICANCE RESULTS
Table 3: KS test statistic values comparing our attack distribution with the random attack distribution for the Balance and Entropy metries (** indicates statistical significance i.e., p-value 0.01).
Dataset
Algorithm
Balance
Entropy
Office-31
SFD
0.889
0.889**
Office-31
FSC
0,889**
0.778**
Office-31
KFC
0.889**
0.778*
MNIST-USPS
SFD
0.222
0.222
MNIST-USPS
FSC
0.000
0.778**
MNIST-USPS
KFC
0.333
0.333
We present the KS test statistic values in Table 3 for the SFD, FSC, and KFC fair clustering algorithms on the Office-31 and MNIST-USPS datasets. The Balance and Entropy distributions obtained are largely significantly different except for the scenario when fairness utility for both our attack and the random attack quickly tends to O. This leads to both distributions becoming identical, and no statistical test can be undertaken in that case. Moreover, it is important to note that such volatile performance is an artefact of the fair clustering algorithm, and does not relate to the attack approach.
D THEORETICAL RESULT FOR ATTACK
We present simple result that demonstrates that attacker solving our attack optimization can be successful at reducing fairness utility for a k-center or k-median fairlet decomposition based fair clustering model described in (Chierichetti et al. 2017). We introduce notation used for this section independently below.
We will use instance of well-separated ground-truth clusters defined in (Chhabra et al. 202 with slight modification allowing samples to possess protected group memberships, thus making possible to study our attack. The original definition for well well-separated clusters is as follows:
Definition D.1 (Well-Separated Clusters (Chhabra et al. 2021b)). These defined for a given K and dataset X E Raxd as a set of cluster partitions {Pi, Pe...., P on the dataset, s.t. |P:] = n/K
and points belonging to each P. C X are closer to each other than any points belonging to P3 C where: + j. Vi.j E []].
We now provide definition for well-separated ground-truie -ruth clusters with equitably distributed protected groups:
Definition D.2 (Well-Separated Clusters with Equitable Group Distribution). These are defined for given K, dataset X E Raxd, and protected group memberships G E [L]" E N", as a set of cluster partitions (P,,P2,... P on the dataset, s.t. |P,| = n// K and points belonging to each P. C X are closer each other than any points belonging to Pj C X and P, contains an equal number of protected group members of G as P, without overlap, where + Vi. E [K].
Using the Definition D.2 provided above for well-separated clusters with equitable protected groups, will now provide result that proves the success of our attack for the specific case when K and L 2 (i.e. we have two protected groups)
Theorem D.1. Given a ground- truth instance as defined in Definition D.2 for = 2, Fairler Decomposition (Chierichetti al. (017]] as the clustering model, and attacker that satisfies the following conditions: (i) controls equal number of sumples from each protected group in each ground-truth cluster, and (ii) has selected these points they are clustered similarly before and after the attack; then our altack optimization will always be successful at reducing the Balance of the benign samples after the attack.
Proof. Based Definition D.2 we know that we have two ground truth clusters P1 and P2 each containing n/2 samples. Following Definition D.2 let the two protected groups be denoted as gi and 92 and then know there are n// samples of 9i and n/4 samples of g2 in both P. and Pz.
15

---

Published as a conference paper at ICLR 2023
individually. The attacker controls a total of A points and if the first condition of the theorem is met, they control A/2 points in each ground-trute cluster comprising of A/4 points from each of the two protected groups.
First note that the Balance of the overall dataset including the adversary's points is clearly 1.0. The defender will use this value for the fair clustering model since they do not know the attacker's points from benign points. Hence, the Fairlet Decomposition algorithm is invoked with = 1.0, specifying requirement of having Balance in each cluster 1.0. For this case the Bipartite Graph Matching approach is used for fairlet decomposition (refer to (Chierichetti et al. 2017) for more details).
Note that when Fairlet Decomposition is run before the attacker switches memberships and carries out the attack. the ground truth clusters are also the optimal fair clustering solution. We can then calculate the Balance for just the benign points, denoted as Opre. Due to symmetry will be the same for each protected group in each cluster:
n/4
A/4
12
Ope
X
1.
n1/2
n/2
A/2
Thus, Opre is the maximum possible value of Balance possible, and if we can show that an attack solution exists that switches group memberships such that post-attack Balance for the benign samples @post pre the theorem statement will hold true.
Consider the following feasible attack policy: the attacker switches membership of each of the A/4 points of group 91 in P1 to group 92 and switches membership of each of the A/4 4 points of group 92 in P2 to group 91- Now; note that after carrying out the attack Balance of the overall dataset is still 1.0 and hence, the same algorithm is going be invoked for fair clustering. After the attack, however, Pi and P2 are no longer the optimal clusters as they violate the Balance constraint. Hence, the optimal clusters will be P` and P/d where |/4| = IPI n/2. P` has obtained A/4 group 9i points from P2 to accommodate the Balance constraint. Similarly, P1 has obtained A/4 group 92 points from Pj.
Now, if the second condition of the theorem holds, without loss of generality, the original A/2 adversarial points of P1 are still present in Py and similarly the original A/2 adversarial points of P2 are present in P2 Again, note that the attack policy was such that the A/2 points of P1 now all belong to protected group B2 and the A/2 points of P2 now all belong to protected group 91- Therefore, we can calculate the Balance for the benign samples post the attack:
n/4
A/2
past
1122
X
n/2
A/2
n1 - 2A
A
11 - A
A
A
A
1 A
A
Opre
Thus, we have proved that épost < Opre for all A > 0.
E ATTACK RESULTS ON DIGITS AND YALE DATASETS
We present results obtained upon carrying out our attack and the random attack on the SFD, FSC, and KFC fair algorithms and two additional datasets: Extended Yale Face B (Lee et al. 2005) (abbreviated as Yale) and Inverted UCT DIGITS (Xu et al.) 1992) (abbreviated as DIGITS). For Yale, we consider lighting and elevation as the two sensitive attributes, and for DIGITS, we essentially color invert all the images in the original DIGITS dataset and then consider the sensitive attribute to be the source of the image (inverted or original). The attack analysis that follows in Figure 4 exactly similar to the results Office-31 and MNIST-USPS in the main paper. We can that our attack is significantly more detrimental than the random attack, and reduces fairness utility by a large margin compared to the pre-attack values.
16

---

Published as a conference paper at ICLR 2023
Bolance
Entropy
NYI1
ACC
0.003
0,180
SFD Algorithm
3,500
0.200
3.000
4.080
35
15
25
25
30
38
35
20
25
30
30
33
25
2.000
0.350
SIIS 100
1.000
0.350
0.002
0.380
4.000
0.000
3,000
0.375
0210
rSc Algorithm
4.000
0.375
0.000
0.430
0.310
0.003
0.900
0.320
$40
0.093
0.300
0.509
30
15
20
23
30
35
20
25
30
21
20
25
22
25
11
KFC Algorithm
0.002
0.130
4.602
0.000
0.120
0.055
0.752
1.400
0.070
0.500
0.502
0.25
3.000
0.170
8.000
0.200
0,200
Algorithim
0.00
0.000
28
25
2,000
0.225
0.300
SI/91O
0.175
0.20
0.002
attack
Figure 4: Attack results for the Extended Yale Face B and Inverted UCI DIGITS datasets (x-axis denotes % of samples attacker can poison).
F IMPLEMENTATION OF CFC
Here present parameter values and implementation details regarding CFC. The hyperparameters such as number of basic partitions r, temperature parameter in the contrastive loss L., dropout in hidden layers, number of training epochs, the activation function, and fair clustering algorithm used to generate J for structural preservation loss Lp are set to be the same across all datasets. These dropout
r 100, T & Gimpel 2016) is used as the activation function, and we use SFD with default parameters for generating since runs faster than other fair clustering algorithms. Moreover, the dimension the hidden layer is set to 256 for all datasets except for DIGITS since DIGITS has only 64 features and hence we use the hidden layer dimension as 36 for
0.6. epochs 3000, Gaussian Error Linear Unit (Hendrycks)
As mentioned in Appendix A we tune the other hyperparameters for the different datasets to optimize for fairness performance. Using grid based search we set the following parameters for the given datasets: for Office-31 we have R 1, 1,3 100: for MNIST-USPS we have
R = 2, = 100, = 25; for Yale we have R 2, a = 50, 3 10; and for DIGITS we have R = 2, 10, 3 50.
17

---

Published as a conference paper at ICLR 2023
Table 4: Pre/post-attack performance when 15% group membership labels are switched.
DIGITS
Yale
Algorithms
Metries
Pre-Attack
Post Attack
Change (%)
Pre-Attack
Post Attack
Change (%)
Balance
0.145 + 0.002
0.266 0.189
(+)83.62
0.176 + 0.027
0.047 0.067
(-)73.22
Entropy
1.903 + 0.022
2.096 0.153
(+)6.758
5.472 + 0.069
6.196 + 0.441
(+)13.22
CFC
NMI
0.225 + 0.004
0.187 + 0.013
(-)16.72
0.142 + 0.004
0.170 + 0.013
(+)20,16
ACC
0.287 + 0.006
0.270 + 0.008
(-)6.132
0.099 + 0.003
0.108 + 0.007
(+)9,381
Balance
0.021 # 0.002
0.000 + 0.000
(-)100.0
0.000 + 0.000
0.000 + 0.000
(-)100.0
Entropy
2.781 + 0.286
0.000 0.000
(-1100.0
3.757 +: 0.358
3.351 0.277
(-100.8
SFD
NMI
0,281 + 0.005
0.371
0.032
(+)32.21
0.159 + 0.009
0.170 0.007
(+)7.206
ACC
0.395 + 0.014
0.417 0.038
(+)5.440
0.095 + 0.004
0.101 0.005
(+)6.733
Balance
0.000 + 0.000
0.000 0.000
G-100.0
0.000 + 0.000
0.000 0.000
(-1000.0
Entropy
0.345 +: 0.000
0.345 + 0.000
(-)0,000
3.907 + 0.137
3.793 + 0.0G0
(-)2,912
FSC
NMI
0.571 + 0.004
0.571 0.004
(-00,000
0.375 + 0.004
0.373 0.005
(-)0,530
ACC
+: 0.003
0.317 0.003
(-00.000
+ 0.004
0.277
(-00.171
Balance
0.653 + 0.290
0.188
(-771.14
0.000
0.000
(-)100.0
KPC
Entropy
3.356 + 0.138
3.128 0.193
(-)6.815
10.92 + 0.744
10.19 + 0.742
(-)6,730
NMI
0.009 +: 0.012
0.062 + 0.010
(-99.184
0.122 + 0.006
0.138 + 0.006
(+)13.08
ACC
0.182 + 0.020
0.179 0.017
(-)1,333
0.080 +: 0.006
0.088 0.004
(+)10.50
1.0
Pre-attack
20
Post Post-attack
0.8
Count
15
0.6
10
0.4
A
0.2
C
0.0
0.0
0.2
0.4
0.6
Pre-attack
Post-attack
Figure 5: (A) Histogram representing the distribution of Balance of the Basic Partitions (BPs) before the attack and after the attack. (B) Visualization of the consensus matrix before the attack. (C) Visualization the conensus matrix after the attack.
G DEFENSE RESULTS ON DIGITS AND YALE DATASETS
Table 4 shows the pre/post-attack performance of CFC and other fair clustering algorithms on DIGITS and Yale when 15% group membership labels are switched. As can be seen, CFC is superlative in terms of both pre-attack and post-attack fairness utility and clustering performance compared the SFD. FSC, and KFC algorithms. More importantly, note that for the Yale dataset, the Balance is consistently 0.0 for all three competitive algorithms, leading to a 100% decrease in fairness (both pre-attack and post-attack Balance is 0). However, CFC is able to find clustering solution that has non-zero pre-attack Balance and even though there is a drop in Balance after the attack, never reaches 0. In fact, Entropy increases by 13.22%. For DIGITS, its results are even better, and CFC has a good trade-off between both clustering utility and fairness utility. Specifically, after the attack, Balance for CFC increases by 83.62% and Entropy by 6. 6.758%. For all other state-of-the tte--art algorithms, performance decreases significantly for both Balance and Entropy.
H IN-DEPTH EXPLORATION OF CFC
H.1 ANALYZING THE CONSENSUS CLUSTERING STAGE OF CFC
We undertake some additional analysis that sheds light why the performance of CFC remains largely unaffected by the proposed faimess attack. We begin by analyzing the first stage the CFC pipeline, i.e., the consensus matrix generation stage. In Figure SJA), we plot the distribution of basic partitions' (BPs) Balance values before our faimess attack and after our faimess attack on Office-31, histogram. Note that 100, which means that have 100 basic partitions. It be seen
18

---

Published as a conference paper at ICLR 2023
Balance
Entropy
NM
ACC
1.40
0.90
190
1.00
MN55T
0.40
0.40
1.00
140
0.80
0.90
-.20
0304
1.00
1.00
1.06
1.04
Office-31
0.80
3.24
2.0
1.92
2.00
11500
0.56
0.90
0.94
0.96
0.65
0.00
0.34
10
20
25
10
15
20
30
30
15
30
10
20
25
1.50
1.20
1.00
1.30
1.20
0.90
1.20
1.20
0.60
0.30
110
0.50
1.00
0.00
10
20
10
20
30
15
15
15
30
10
26
25
4.00
1.00
1.00
135
0.80
220
0.60
-30
1.50
1.00
0,40
1.00
0.0
0.50
8:20
0.50
0.00
0.00
10
20
25
5
15
15
20
25
30
13
20
10
25
20
75
CFC
FSC
KFC
SFD
Figure 6: Post/Pre attack ratio trends for CFC and other fair clustering algorithms (we do plot curves for which pre-attack values are 0). X-axis denotes the % of samples attacker can poison.
that before the attack there actually decrease. Specifically, the mean Balance of the BPs shifts from 0.3 before the attack to 0.35 after the attack. Moreover, the partition the 20th percentile has Balance 0 before the attack, but 20th percentile BP improves to a Balance of 0.14 after the attack. This indicates that the simple basic partition generation strategy will alleviate the negative impact of a fairness attack.
BPs with 0 Balance values, and after the attack these partitions
Moreover, is beneficial to use consensus between BPs as a means of ensuring robustness, i.e, our model is able generalize from the performance of number of different clustering results obtain more robust results. This can also be observed through Figures 5 B) and where we plot the pre-attack and post-attack consensus matrices obtained for Office-11, respectively. Visually, both these matrices look similar, indicating that the consensus matrix is largely unaffected by the attack. Note that for the size these matrices (n n, where n = 1, 293 is the number of samples in the Office-31 dataset), the norm of their difference equals 19.335, which is relatively small comparing the number samples. This indicates that consensus clustering results as part of the first stage are independent of the attack, and hence, can be used to ensure highly resilient and robust performance on the dataset before and after the attack.
19

---

Published as a conference paper at ICLR 2023
H.2 ANALYZING OVERALL ADVERSARIAL ROBUSTNESS OF CFC
Next, we conduct experiments on comparing the performance of CFC with the other state-of-the-arr fair clustering algorithms. For ease of understanding, we plot the ratio between the mean post-attack and pre-attack values as a function the percentage of protected group membership labels switched by the attacker. Thus, the ratio is mathematically defined as Mean Post-Atlack Value Then, note that higher values the ratio, indicate more robust performance with regards to faimess metrics such as Balance or Entropy.
We present these results in Figure 6 As can be observed, the CFC ratio values are always much higher than the other algorithms for all the attack percentages and for the faimess metrics Balance and Entropy. This especially observable for certain datasets (such as Yale), where Balance for all other fair algorithms is consistently but CFC is still able obtain clustering solutions with desirable fairness utility before and after the attack. It is also worthwhile to note that for Office-31 and MNIST-USP? fairness performance highly robust the ratio trends tend to be approximately 1.0, or > 1.0, with little to no decrease in utilityy after the attack. For the NMI and ACC metries, we find that the ratio is generally distributed very close 1.0, indicating that clustering performance is very similar before and after the attack. This means that in general, it is hard to tell whether or not a fairness attack has occurred based on clustering performance. This makes it challenging for the defender to defend against such an attack, further mandating the need for robust fair clustering algorithms like CFC. Also note that for some algorithms, pre-attack and/or post-attack values are consistently O, and we omit their trends from the figure since they indeterminate.
I MISCELLANEOUS EXPERIMENTS AND RESULTS
I.1 RESULTS WHEN ATTACKER CAN SWITCH TO 3.75% GROUP MEMBERSHIPS
Table 5: Results for our attack and random attack when 3. 75% group membership labels are switched.
Algorithms
Metrics
Office-31
Pre-Attack
Our Attack
Change (%)
Random Attack
Change (%)
Balance
0.4841 0.129
0.068 0.089
(-)85,95
0.250 0.1138
(-)48.37
Entropy
10.01 1 0.098
9.681 0.161
(-)3.243
9.798 1 0.146
(-12.082
SFD
NMI
0.801 + 0.050
0.809 + 0.040
(+)0.956
0.802 + 0.060
(+)0.173
ACC
0.688 + 0.082
0.681 = 0.066
(-)1.066
0.673 = 0.101
(-)2,196
Balance
0.011 0.122
0.000 = 0.000
(-100.0
0.032 = 0.097
(-)20,95
Entropy
9.538 1 0.113
9.228 1 0.191
(-33.257
9.322 1 0.176
(-)2.268
FSC
NMI
0.669 + 0.014
0.688 + 0.028
(+)2,920
0.687 + 0.021
(+)2.714
ACC
0.411 + 0.014
0.446 = 0.034
(+)8,525
0.446 + 0.030
(+)8.420
Balance
0.250 + 0.310
0.052 = 0.155
(-779,66
0.170 = 0.267
(-332,08
Entropy
9.997 + 0.315
9.947 0.146
(-)0.500
9.966 0.251
(-)0.313
KFC
NMI
0.393 1 0.064
0.392 0.063
(-)0,272
0.393 0.064
(-)0.149
ACC
0.265 0.048
0.265 0.050
(-)0.227
0.266 0.048
(+)0.065
Algorithms
Metries
MNIST-USPS
Pre-Attack
Attack
Change (%)
Random Attack
Change (%)
Balance
0.286 + 0.065
0.252 0.015
(-)12.05
0.42% + 0.146
(+148.45
Entropy
3.070 + 0.155
3.101 + 0.073
(+)1.012
3.206 + 0.090
(+)4.432
SFD
NMI
0.320 1: 0.033
0.358 0.025
(+)11.73
0.328 1 0.030
(+)2.503
ACC
0.427 1 0.040
0.475 1 0.025
(+)11.15
0.444 1 0.033
(+)4.112
Balance
0.000 1 0.000
0.000 - 0.000
()100.0
0.000 + 0.000
(-1000.0
Entropy
0.275 + 0.077
0.230 + 0.067
(-)16.17
0.276 + 0.063
(+)0.564
FSC
NMI
0.549 + 0.011
0.010
()1.144
0.549 + 0.009
(-10.022
ACC
0.448 1 0.012
0.450
0.011
(+X0.461
0.452 1 0.000
(+)0.847
Balance
0.730 1 0.250
0.225
1 0.298
(-169.14
0.414 0.359
(-)43.77
Entropy
2.607 + 0.607
2.502 0.466
(-)4.221
2.710 0.464
(+)3.978
KFC
NMI
0.072 + 0.024
0.072
0.024 0.024
(+)0.110
0.073 0.023
(+)0.948
ACC
0.168 1 0.026
0.171 0.025
(+)1.453
0.169 0.028
(+)0.715
20

---

Published as a conference paper at ICLR 2023
1.2
UPDATED TABLES WITH RANDOM ATTACK
Table 6: Pre/post-attack performance when 15% group membership labels are switched for Office-31 and MNIST-USPS.
Alaseihua
0,00
C30405
[:3224]
3,073
631534
1:215-0011 2:126
CCC
NMI
0,600
3:500
0.015
0.525
6.009
0.008
0.015
01.270
(+)0.229
(+11.256
0.715 0.007
5.009 0.115
(-35601
[-9-416
2,508
0.299
0.00%
2,636
0.287
8.000
00.36
(+)1.953
(+16-709
2.59P 0.135
0.280 0.03
(+>4,00
(-20-90
ACC
0,508
0.021
0.011
(130.633
0,227
0.013
(-33.655
0,385
0.000
B1-00 =0005
(K15.343
0.214 = 0.05
(12.439
Balinss
0.4611
0.135
C38721
C212
C35874
0.298
00000 0,000
C20000
00001
Emeogy
0.005
0.500
0.000
555448
0.09
ACC
6,688
2 0U082
0.621
0.015
--99,903
0 0.00
(-2.006
0.427 4 0.000
0.378
0.016
6-11.54
0.574 4 0.026
+-12.35
0/201
11177
0100
7 01070
0100 1117
0163 1- 070000
11000 17300
0-30700
FSC
Ensopy
0.400
9,588
+ 0.113
0.014
0.003
9:643
0L178
(+)1.999
C30,907
5,864 0.225
(-35-711
1-00.00
0.545
0,273 0.677
0.253 0.041
0.541
0.007
6-8.576
6-00
0.212 0.036
0.006
(477.588
0.411
00014
6-477
(131.973
0000
11250
033521033
KFC
XMI
9:807
6,800
+ 0.064
0.515
0.919
0.201
1L053
0.189
630.796
$.500 0.29)
0.201 0.007
(-901600
1-00051
0.072 0.824
2,077 0.007
2.545
0.070- : 0.029
0.445
(1)5,812
6-00.12
2,583
0.0.50
(+15,33
(-18.595
ACC
0,266
8 0,045
0.205
(+10,00
0.065 0.06
1-8-183
A.165 0.625
0.126-2
0.084
(434-501
0.104 0.001
(+0.419
Table Pre/post-attack performance when 15% group membership labels are switched for DIGITS
and Yale.
Alareshm
Mosic
ANGITS
Pre- Att-A
Our Atack
Change (%)
Runsoo Altack
Chanse (15
Pre-Attck
Our Attack
Change (%)
Random Attak
Chasge (S)
Balasce
Tuiter 113922
2 21111
(7155322
C:202 11:111
(374222
Easeopy
2.005: 0.155
1.195 0:114
[-38.44
0:0000
(4115:23
0.8.99
[315.14
(1/28:16
0,287
0L005
0.274
0.007
0.056
0,021
111072
0000
030000
10C0
SED
Ernooyy
NM
2.781 + 0.296
0.281
3. 0.005
0.000
0.511
0.822
1.030
(4132.21
63100.
0.57 0.00
01000 0,000
03030.0
0.188 0.000
3,707
0.355
0,353
0.120
0.000
0.277
(437.205
(-0081
8773
0.120 0.055
(+77.53
(30430
ACC
0,300
#: 0.004
0.417
(+15.400
0.421 0.00
(-22240
0.005 000
01000
-0000
(+30.733
51000 0100
(+34.300
Balanoe
0,000
C-100.0
ESC
VMI
0:571
+ 0.001
0.571
0.001
(3000000
0.509 0.003
(-6.25%
0.355
0.375 0.005
6-0-530
0.375 0.055
(+90532
ACC
6,317
= 2.003
0.317
= 8.035
--0,000
0.315 0.003
(-90.3)
0 0.004
0.277
0.0004
6-0.17]
0.264-2000 0.06
(6023006
Retenst
1.800
10200
[1165 D1T0
0:00 1120
0100
T 1100
01F00 11300 17300
01001 11:0
KFC
Ensogy
0.000
1,366 + 0.135
0.013
3.125 0119
C16815
3,215
0.10
(-9.240
134.216
10.02 5 0.744
00.19=0..24
0.006
(+113.08
6-67730
10:54:2
0.066
CJ0785
I.3 CFC PERFORMANCE WHEN J IS GENERATED USING DIFFERENT FAIR ALGORITHMS
Table 8: CFC performance on Office-31 for generated by different algorithms.
Algorithm used for J
Metrics
Pre-Attack
Post-Attack
Change (%)
Balance
0.609
0.081
0.606 = 0.047
(-J0.466
Entropy
5.995
0.325
6.009 0..270
(+)0.229
SFD
NMI
0.690
0.019
0.698
+ 0.013
(+)1.236
ACC
0.508
0.021
0.511 = 0.018
(+10.643
Balance
0.650
0.069
0.653
0.064
(+)0,404
Entropy
4.027
0.273
4.485 = 0.677
(+)11.38
FSC
NMI
0.610
0.008
0.610 = 0.017
(-)0.011
ACC
0.361
0.015
0.358 0.015
(-1.7114
Balance
0.414
0.31S
0.385 - 0.310
(-66.815
Entropy
4.830
0.174
4.382 0.298
(-)9,260
KFC
NMT
0.409
0.003
0.426 0.004
(+)4.218
ACC
0,252 0.001
0.265 0.002
(+)5.108
21


Reviews:
[{"review_id": "rQfkacL_-8", "reviewer": "Reviewer_EUnH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies robust fair clustering and motivates the issue of robustness under attack. The authors conduct numerical experiments to show that state-of-the-art models are highly susceptible to the attack they design. The authors then propose a Consensus Fair Clustering and numerically show its robustness.", "summary_of_the_review": "The issue of robustness under attack is well-motivated, and I believe this could be an important property for any robust fair clustering. \n2. The designed attack is quite novel. The designed attack is quite novel.", "strength_and_weaknesses": "Strength: \n1. The issue of robustness under attack is well-motivated. I believe this could be an important property for any robust fair clustering. \n2. The designed attack is quite novel.\n\nMy major concern is the following:\nThe proposed Consensus Fair Clustering appears to respond well to the designed attack. Is there any guarantee that it remains robust under ANY attack that the adversary would choose?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "D9UD_pOHodu", "reviewer": "Reviewer_XY3W", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies adversarial attacks on fair clustering. The authors demonstrate simple adversarial attacks on existing fair clustering approaches and propose an algorithm that is robust to the attack.", "summary_of_the_review": "Overall, I think this is interesting work, though I am not an expert in the area.\n\n-------------------------\nPost Rebuttal:\n-------------------------\nI thank the authors for their response. After reading all the reviews and responses, I have increased my score from borderline accept to accept.", "strength_and_weaknesses": "------------------------\nStrengths:\n------------------------\n-- The paper is mainly well written (except section 3.1) and easy to follow.\n\n-- The idea of adversarial attacks on fair clustering is natural and worth exploring. \n\n------------------------\nWeaknesses:\n------------------------\n-- The paper would be strengthened if the authors provide a clear motivating example.\n\n-- The size of $G_A$ in all the experiments is rather large. In all the definitions, it is assumed that this proportion is small but all of the experiments focus on 15% which is rather large. How do the results change for proportions much smaller than 15%?\n\n------------------------\nMinor Comments:\n------------------------\n-- What is the axis in Figure 2? It would be nice to have labels for graphs.\n\n-- Can you elaborate on why the fairness violation can decrease after accounting for attacks? This intuitively does not make sense as the approach which only optimizes for the fairness violation should achieve a smaller loss.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CvuAcHXW2Ek", "reviewer": "Reviewer_UuYT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the fairness attack and defense problem. The authors propose a black-box attack against fair clustering algorithms that works by perturbing a small percentage of samples’ protected group memberships. They also proposed a defense algorithm, named Consensus Fair Clustering (CFC), that utilizes consensus clustering along with fairness constraints to output robust and fair clusters. Empirically, existing fair clustering algorithms are highly susceptible to adversarial influence, while the proposed CFC algorithm is highly effective and robust as it resists the proposed fairness attack well.", "summary_of_the_review": "The paper studies the fairness attack and defense problem and proposes a novel black-box attack. The empirical results that existing fair clustering algorithms are highly susceptible to adversarial influence are convincing. The major concern is the lack of theoretical analysis on both the influence of black-box attacks and the proposed CFC approach.\n\nOverall, I tend to accept the paper. I think the paper can be further improved by providing some theoretical analysis. ", "strength_and_weaknesses": "Strength: \n- The proposed problem of robust fair clustering is interesting and novel.\n- The proposed black-box attack is natural in robust clustering literature.\n- The empirical results that existing fair clustering algorithms are highly susceptible to adversarial influence are convincing.\n\nWeaknesses:\n- The proposed approach CFC does not have any provable guarantees, both in fairness and in accuracy. I expect to see at least some performance analysis for CFC.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5SNRDERMpA", "reviewer": "Reviewer_HmWf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tackles **unsupervised fair clustering**. The authors first propose **a black-box adversarial attack** on state-of-the-art fair clustering algorithms, effective on a toy dataset they propose as well as real datasets (MNIST, USPS, Office-31). In their threat model, an adversary can modify *the protected attribute* of a subset of the dataset. Its goal is to minimize a fairness utility function while trying not to degrade the performances. Success of the attack is evaluated on the remaining untouched datapoints.\nIn a second time, the authors propose **a defense against that attack**, an unsupervised fair clustering algorithm which is robust to the attack.", "summary_of_the_review": "The novelty and relevance of this work make it interesting for the scientific community in both Robust Machine Learning and Fairness-related Machine Learning research. Although I pointed a few (alleged) weaknesses, the paper should have tackled, they nonetheless exhibited a relevant attack and experimentally demonstrated a defense to that attack. Further work on this topic will be of great value for the community.", "strength_and_weaknesses": "### Strengths\n\n- Being *black-box* and exploring a wide range of ratio of poisoned data, the threat model seems highly relevant;\n- Brings neural network in the field of fair machine learning, which seems to still be understudied (as showed by the state-of-the-art algorithms used to compare to in the paper);\n- The paper is well written and easy to read.\n\n### Weaknesses\n\n- Some comparisons would have benefited being more thorough:\n    - Figure 2 and 4 would have benefited showing results on CFC;\n    - Table 2 and 4 would have benefited comparing with random attacks;\n    - Figure 6 experiments would have benefited from a confidence interval;\n    - Comparing different fair algorithms that could be used to generate the $J$ parameter in equation $(4)$.\n- Even though an in-depth exploration of CFC is proposed in appendix, an ablation study would have been relevant, especially on the different losses being used.\n- Studying the robustness of CFC against other known attacks on clustering (relaxing some of the problem constraints if necessary) would have been highly appreciated.\n- Is the ratio of poisoned samples reasonable? 15% seems like a lot, it would be interesting to see how CFC compare with a low number of adversarial samples (1%?)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster