FairDen: Fair Density-Based Clustering
Authors: Lena Krieger
Anna Beer
Pernille Matthews
Anneka Myrup Thiesson
Ira Assent
Venue: ICLR 2025 Poster (2025)
Keywords: Fair Clustering
Density-based Clustering
Density-Connectivity
Fairness
Unsupervised Learning
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We developed the first density-based fair clustering method - it finds density-based clusters that have balanced ratios of sensitive groups, accounting for multiple non-binary sensitive attributes.

Abstract: Fairness in data mining tasks like clustering has recently become an increasingly important aspect. 
However, few clustering algorithms exist that focus on fair groupings of data with sensitive attributes. 
Including fairness in the clustering objective is especially hard for density-based clustering, as it does not directly optimize a closed form objective like centroid-based or spectral methods.  

This paper introduces FairDen, the first fair, density-based clustering algorithm.
We capture the dataset's density-connectivity structure in a similarity matrix that we manipulate to encourage a balanced clustering. 
In contrast to state-of-the-art, FairDen inherently handles categorical attributes, noise, and data with several sensitive attributes or groups.
We show that FairDen finds meaningful and fair clusters in extensive experiments.

Published as a conference paper at ICLR 2025
FAIRDEN: FAIR DENSITY-BASED CLUSTERING
Lena Krieger".,, Anna Beer".?, 2 Pernille Matthews', Anneka Myrup Thiesson', & Ira Assent 1.3 IAS-8: Data Analytics and Machine Learning, Forschungszentruum Jülich, Jülich, Germany 2 Faculty of Computer Science University of Vienna, Vienna, Austria
3 Department of Computer Science Aarhus University, Aarhus, Denmark
ABSTRACT
Fairness in data mining tasks like clustering has recently become an increasingly important aspect. However, few clustering algorithms exist that focus on fair groupings of data with sensitive attributes. Including fairness in the clustering objective is especially hard for density-based clustering, as does not directly optimize a closed form objective like centroid-based or spectral methods.
This paper introduces FairDen, the first fair, density-based -ased clustering algorithm. We capture the dataset's density-connectivity structure in a similarity matrix that we manipulate to encourage balanced clustering. In contrast state-of-the- art, FairDen inherently handles categorical attributes, noise, and data with several sensitive attributes or groups. We show that FairDen finds meaningful and fair clusters in extensive experiments.
INTRODUCTION
Applying machine learning critical situations, such as medical diagnostics or recidivism, requires fair and reliable models. It is crucial to ensure that minorities are not disadvantaged in the decision- making process based on machine learning models. This paper focuses on group-level fairness, i.c., treating different groups equally (Chhabra al. 2021). These groups usually arise from sensitive attributes such as gender, race, or age.
Clustering is the task of grouping data objects based on similarity and is widely used in various domains. Recently, issues with fairness data-driven models, particularly, machine learning. have been discussed, e.g., in connection with new legislation and laws regarding disparate impact (Dressel & Farid 2018). Without adequately addressing sensitive attributes, most state-of-the-art clustering algorithms may produce unfair clusters: minorities might be disproportionately assigned the same cluster, and people may suffer from biases in downstream tasks. For clustering, group-level fairness means avoiding favoring or discriminating against any sensitive group within each cluster (Chhabra et al. ). e.g., by making sure that the distribution of sensitive groups within each cluster is as close as possible their overall distribution the dataset (Chierichetti et al., 2017). The toy dataset in Figure three spatial groups with sensitive attribute denoted by the shape of the objects. fair clustering consists of clusters with as many circles as triangles, corresponding to their overall distribution in the dataset. Clustering methods like k-Means (Lloyd) 1982) or k k-Center (Har-Peled 2008) can be adapted to a fair version (Bera et 2019 Bercea et al. 2018). However, incorporating fairness into
-based clustering is difficult, as this clustering notion does not directly optimize a closed form objective function like centroid-based or spectral methods.
Especially for real-world applications, faimess in density-based clustering methods is crucial as centroid-based methods have several shortcomings: 1) In contrast to density-based methods, centroid-basee based methods typically cannot handle categorical data, rendering them suboptimal for data with the most common sensitive attributes like 'gender', 'race', or 'marital status': these attributes usually have categorical values. 2) Density- methods inherently manage noise, which is com- mon in real-world applications, whereas partitioning- based clusterings may be more susceptible to the impact of noise. 3) For geographic data, travel distance along streets or railroads is often more expressive than the Euclidean distance, making For example, an important task for city planning is to find school districts where the socio-economic
connected clusters an inherently better fit.
Both authors contributed equally this work and ordered randomly.

---

Published as a conference paper at ICLR 2025
Denstybaaeed
-Covvenionaa-
-Fair Clustering
DBSCAN
FairDen
Clustering
Balance: 0.33, DCSI: 0.98
Balance: 1.0. DCSI: 0.43
Balance: 0.4, DCSI, 0.0
Balange: 1.0, DCSI:
Balance: 0.36, DCSI: 0.01
Labels:
Cluster 0
Cluster
Cluster
Sensitive groups:
S.
Figure 1: Different methods, balance, and clustering quality measured by DCSI (higher is better). A balanced density-based clustering has for each cluster the same ratio of circles to triangles as in the overall dataset, yielding a balance value of 1.0. Shapes indicate membership to of two sensitive groups: the first moon has 50% triangles and 50% circles, the second moon has only triangles, the third moon has only circles, and all moons have the same number of data points. In contrast to our competitors, FairDen achieves a perfect balance and well-separated density-based clusters, indicated with higher DCSI value. Colors indicate the clusters found by FairDen and its competitors FairSC, clustering with Fairlets, Scalable Fair Clustering, respectively, the three density- based clusters found by DBSCAN.
distribution of schools is similar ensure fair education for all pupils. Density-based clusters offer good routes for school buses picking up the children and ensuring socio-economic fairness. However, there is method yet that finds fair density-connected clusters.
In this work, we propose FairDen, a novel method that integrates fairness into density-based clus- tering. For this, we first capture the data's density-based -based structure, which may include categorical attributes. Capturing the structure allows us to flexibly manipulate the resulting similarity matrix based on fairness constraints. Our code is available at GitHut
Our main contributions are as follows:
We introduce FairDen, the first fair density-based clustering algorithm which successfully detects fair clusters of arbitrary shapes while enforcing a balance with respect to all sensitive attributes.
FairDen is the first fair clustering algorithm that can handle mixed-type data and multiple sensitive attributes at once. Furthermore, it automatically detects noise points.
Our experiments show that FairDen determines more balanced clusterings with respect sensitive attributes than other density-based methods and detects density- based clusters better than other fair methods.
2 FAIRDEN: FAIR DENSITY-BASER CLUSTERING
In the following, we describe novel density-based fair clustering method in detail. Including fairness constraint into density-based clustering is challenging due to the characteristics of density- connectivity. At the heart of density-based clustering (e.g., DBSCAN (Ester et al.) 1996)), it is defined as a binary property for each pair of points: Given a data set X' -II,..., In) comprised of points, two points are density-connected if and only if there is a chain of core points connecting them. Core points lie in dense areas and are defined points with at least minPts points in their e-radius for given min N>1. E R>o. Points form chain if the (usually Euclidean) distance d(p, s) between any two consecutive points is not larger than A cluster is then maxi- mal set of density-connected points. This definition does not allow for an easy adaption of clusters to fulfill fairness criteria like balance between groups (Chierichetti et al.) 2017 Bera et al.) 2019) (cf. Section 2.2 Group-level fairness aims to achieve a ratio between sensitive groups within each cluster that corresponds to their ratio in the full dataset. However, the two most prominent exist- ing approaches for including group-level fairness into clustering are not applicable to density-based clustering: Density- based methods usually do not have differentiable clustering objective, thus, approaches like Bera et al. (0119) or Bercea et al. (2018) are not applicable. Other approaches use fairlets, i.e., minimal satisfying fairness that approximately preserve the k-clustering objective.
https://jugit.
2

---

Published as a conference paper at ICLR 2025
However, those may destroy the points, as shown in Figure Il Thus, to achieve fair connstt-conneettvvtty proach this problem from novel perspective: capture the conneeitcone between points in continuous representation that admits group balancing, thereby presenting the first fair density- based clustering method. We describe how capture the density-connectivity in Section 2.1 in- troduce fairness constraints in Section [.2] and how to combine both in Section 2.3 In Section 2.4 explain clustering with categorical data. A complexity analysis, limitations, and interpretation are in Section 2.5 The pseudo-code is in Appendix A.1 and our implementation is available online.
structure of the dataset when locally merging
clustering, we ap-
2.1 TRANSFORMING THE DENSITY-BASHD OBJECTIVE
As outlined above, the major challenge in fair density- density-based clustering lies in the discrete nature of Our idea is thus to transform the original problem into a continuous one that admits faimess balancing. Concretely, capture the density-coonecttiity constraint by leveraging the density-connectivv est such that two points density- P. E X' is still a discrete property. the dc-distance gives mapping from the continuous space of possible e-values onto the binary property by checking ddc(p, q) S S. The dc-distance represents pairwise distances between objects in a tree structure with objects as leaves and distances in the nodes. The hierarchy defined by the de-distance works analogously to the well-known clustering hi- erarchy defined by the single-link distance in agglomerative single-linkage clustering. While usually the single link distance based on the Euclidean distance, the dc-distance builds upon the mutual reachability distance used by DBSCAN, ef. Appendix [.2 Consequently, any partitioning based on the hierarchy defined by the dc-distance will give density-connected clusters. In FairDen, we observe that by casting the density-based clustering problem one of the partitionings, optimizing a cut criterion on this hierarchy admits using spectral clustering methods (Beer et al., 2023). For this, regard the following affinity matrix and its Laplacian (line 3 of Alg 1
distance (de-distance) (Beer et al. 2023). which intuitively gives the small-
While the density-connectivtty between points
Aij max,, (i,
L=D-A
(2)
where 'D the degree matrix. Minimizing the minCut as described in Beer al. (2023) with ultra- metric spectral clustering yields DBSCAN-like clusters. However, as we want to capture density- based clusters of potentially different densities, we cut the hierarchy given by the ultrametric at different levels instead of thresholding at specific value for e. This leads to more prevalent ver- sions of spectral clustering that detect the normalized cut (Hess et al. 2019) instead of the minCut. Thus, we apply k-means on the spectral embedding given by the first & eigenvectors of our Laplacian L (see Von Luxburg (2007) that we will adopt as shown in the following. Note that any clusters FairDen finds in the hierarchy given by the de-distance follow the connety-comnecttvitty notion.
To find the normalized cut we solve for
Tr(HT LH) HER
min
(3)
Where H encodes our clustering:
1/ [//vvll(C (Ci) 10
p E Ci p $ Ci
Hpt
(4)
And vol(C;) is the volume of the cluster C₁ i.e., (C) E 9E Apg. Similar to Klein-
dessner et al. (2019b), and common in spectral clustering, we relax Eq. to only requiring the following equality where 15 E & is the & x & identity matrix:
H DH
(5)
Adopting the de-distance as the basis for similarity matrix in FairDen, now incorporate the fairness constraint in the form of a balancing matrix for density- based clustering, similar to the approach taken for spectral clustering in Kleindessner et al. (019a)..
3

---

Published as a conference paper at ICLR 2025
2.2 FAIRNESS CONSTRAINT
As in recent work on fair clustering, our goal is to balance clusters regarding membership in sensi- tive groups (Kleindessner et al. 2019b; Chierichetti al., 2017). where for each cluster, the ratio between different groups of specific sensitive attributes is as similar as possible to the ratio in the entire dataset. Where, c.g., FairSC (Kleindessner al., 2019b) only considers individual sensitive attributes, FairDen handles also combinations of several sensitive attributes (c.g., gender and race simultaneously). Known as intersectional fairness (Gohar & Cheng 2023), it has been shown that the combination of sensitive values (e.g., black woman) can lead to unique discrimination issues.
Our multi sensitive notion takes into account membership in each sensitive group: Assume that each data object E X belongs to precisely one of di many sensitive groups Siy of size |Stg] 2 k with j = 0, ..,, Di for each of its sensitive attributes S, with O,..., and & being the number of clusters: VS: X' = U,
We want to maximize the group-level balance (Chierichetti et al. 2017 Bera et al. 2019) that assesses the ratio (c) of all sensitive groups S.y within each cluster Tay, the distribution of the sensitive groups within the whole dataset.
We define Fay |5:, and ray (Ci) |s,ncy [C, where (Siy n Cil is the number of samples belonging group Si, within cluster Ct. The balance for cluster Cj (see Eq. (6) is the minimum balance value for each sensitive group Sij within the cluster, see Eq.
balance(Ci) = min balance,y (Ci) VSi,
(6)
balance,, (Cin) = min
Tsj
Tiy(Ci)
(Ci(
Ti
To handle several sensitive attributes simultaneously, we introduce combined group membership vector f where S2 denotes membership in some combination of sensitive groups across sensitive attributes. Thus, instead of gs groups for every of the a attributes, we consider up to Σi= 9: combined sensitive groups S, (e.g., Asian + female, Asian + male). Due to this representation, FairDen has the advantage of different sensitive attributes combined being weighed equally, and attributes with fewer groups (e.g., gender) do not impact the clustering more than attributes with more groups (c.g., race), as would be the case for simple concatenation of sensitive attributes.
For balanced clustering. the ratio of each combined sensitive group S₂ within each cluster C should be as similar as possible to its ratio in the overall dataset:
S2 n
|
S.
(8)
|Ci
n
Thus, our FairDen objective for a perfect balance is
Sz S2 n C.
SSall
[G]
n
With that and Eq. we reformulate Eq.
[S
VC1, Sn
S.
Hpt =
(10)
n
PEA
To solve this equation, we use fairness matrix F R with vectors f ([S2I/n) 1, as
columns for the first [S,| combined sensitive groups (Alg. Iline 4). The fairness matrix captures the term in brackets in Eq. T0 thereby balancing the clustering regarding the sensitive groups. Then, we include Eq. TO as a constraint into our overall clustering objective from Eq. 3
f
FTH
(11)
By enforcing this constraint make sure that any cluster assignment H. yields balanced clustering with respect to any sensitive group as mandated by the fairness matrix F.
omit membership vector for the last combined sensitive group s.t. the matrix is over-determined
4

---

Published as a conference paper at ICLR 2025
2.3 INTEGRATING DENSSTY-CONNECTIVTY AND FAIRNESS
FairDen integrates the density--onneetiitty objective (Eq. 3 with the faimess constraint (Bq.
min Tr(H. CH) subject to H DH I& and F
(12)
HER
While this objective bears superficial similarity with the one for spectral clustering in Kleindess- ner et al. (2019b), there are fundamental differences the two approaches: Most importantly, our Laplacian 2 in FairDen captures censity-connecttiity and is unrelated to the Laplacian of [leii- dessner et al. (2019b). Furthermore, our fairness constraints handle multiple sensitive attributes. We now reshape Eq. 12] |2|so so that it can be solved by spectral clustering, i.e., by eigendecomposition and subsequent application of k-means on the first &o eigenvectors. For this, we ensure the condition in Eq. 11 is met (Alg. | line 5): we compute the orthonormal basis of the nullspace of F as the columns of matrix Z [=*(((.)-1)), so that can replace H. zy for y p(n=15sl+1)x,,
min Tr(y 2 LZY) subject to y" D = Ig
(13)
We want to express the condition in the shape VT = It. We make use of the fact that DDZ is positive definite and square (as it comes from a fully connected graph given by de-distances that calculated for all pairs): This means, there is Q (1 (s.-sS.++1)((( (1-,+()) so that: Q Z T DZ
(Alg. lines 6 and 7). With this, we can replace y - for some V E ((==(S_|+1)xx in Eq. 13
min Tr(V* e IT Z cTczz-11 V) subject to VTv= = Is
(14)
Now our solution V to Eq. 14 can be found by computing the eigenvalue decomposition of Q Q-1 _ LZQ-1 and the k eigenvectors belonging to the k smallest eigenvalues become the columns of (Alg. D line 8). We obtain fair density-based clustering by applying k-means on
H = VV- (Alg- line 9). Note that subdividing the hierarchy given by the dc-distance automat-
ically detects noise points as subtrees that are smaller than the given μ.. Our algorithm thus returns a k-means clustering that gives k non-noise clusters (Alg. Blg..Dine lines 10-18).
2.4 CATEGORICAL ATTRIBUTES AND MULTIPLE SENSITIVE ATTRIBUTES
While most fair clustering methods (cf. Section 3.4) target numerical data or assume a given sim- ilarity matrix (Kleindessner et al., 2019b), this is strong contrast their real-world use cases: Most data for which fairness is fundamental contains categorical attributes, especially considering sensitive attributes are usually categorical. Thus, handling categorical data, while preserving the underlying information, in fair clustering is of utmost importance.
In FairDen, we provide full inclusion of categorical attributes and mixed-type data. For this, we com- pute similarity matrix SG based on Goodalll (Boriah et al. 2008). We extend Eq. [ to a weighted average of de-distance and categorical similarity measure. Consider data set X (#1..... Zn, with dl d-dimensional points where the d dimensions consist of d,, numerical and de categorical features. Instead of using Eq. [ we can then compute our affinity matrix as follows:
dp (1- (1- Ar = d
dac(i,
de
maxi, (i, ++
Sa(i.))
(15)
Like this, we combine both types of data weighted proportionally to the number of numerical and categorical features within the dataset. Note that this approach not suitable for k-means-like algorithms, as they need a metric space where centroids can be computed: Clustering methods solving k-oojjective would require an embedding of the categorical data first. In contrast, density- based methods only require a distance or similarity matrix. FairDen captures arbitrarily shaped clusters with the de-distance. Since the de-distance defined on numerical data, the input data has to feature some numerical attributes. With the above extension, we allow for the inclusion of categorical attributes in a mixed data type approach.
When including multiple sensitive attributes, we combine those sensitive attributes into one meta- sensitive attribute, such that FairDen balances the combined groups. For example, for sensitive attributes race and gender the combinations might include groups like 'Female-Asian'. Clearly, multiple sensitive attributes are highly complex to handle, and achieving balance also requires a sufficient amount of data for each subgroup, for fair clustering to be attainable.
5

---

Published as a conference paper at ICLR 2025
2.5 ANALYSIS
General Interpretation FairDen aims for optimal balance (see Eq. and following). By working on the hierarchy of density-based clusterings given by the dc-distance, all clusterings by spectral cuts are density-based. However, we relax DBSCAN's clustering criterion by allowing clusters of dif- ferent densities, and by prioritizing balance. Thus, as Section 3.5 shows, FairDen finds clusterings with high balance values. Their cennity-connectivity is of course slightly lower than the non-fair coniecivtn of DBSCAN clusterings. However, FairDen captures arbitrarily-shape clus- ters better than any other fair clustering algorithm, see e.g. Figure [| quality regarding density-based clusters throughout our experiments in Section 3.5
leading to higher clustering
Complexity Analysis The complexity of FairDen in the number of data points is dominated by the cigenvector decomposition in O As we need only up to k (number of clusters) eigenvectors, this step be accelerated significantly by, e.g., using power iterations. After computing the de- distance matrix, the runtime is independent of the dimensionality, yielding linear dependency in dimensionality d. Thus, the complexity is in O(n d), comparable other fair clustering methods.
Limitations Note that a balanced clustering with & clusters is only possible if every sensitive group has at least members. In extreme cases with insufficient data for particular subgroups, these individuals are considered here, manual check regarding minorities with very few members is advisable. For several sensitive attributes, FairDen optimizes the balance of their combination, and not of the individual sensitive attributes, which may or may not be adequate depending on the application goal.
EXPERIMENTAL EVALUATION
We measure cluster quality with DCSI Gauss et al. 2024) and group-level fairness with general- ized balance Bera et al.] (2019) (Sect. 3.1. We study real-world benchmarks (Sect. 3.3 and compare to of fair clustering methods FairSC (Kleindessner al. 2019b). normalized FairSC (Kleindessner et al. 2019b), Fairlets (Chierichetti et al.]| (011)). ). and Scalable Fair Cluster- ing (Backurs al., 2019) (Section 3.4). Following SSchubert al. (2017). we fix the parameter 2d - 1 for FairDen and show an ablation in App. A.2 Further technical details in App. C.I
3.1 EVALUATING CLUSTERING QUALITY
Note that ground truth labels of benchmark data are not typically balanced, but rather potentially include bias. Crucially, these labels cannot serve external measures for fairness, but only for (biased) group assignments. Thus, an optimal correspondence the ground truth clustering is not necessarily desirable. We aim to find fair, balanced clustering, ruther than replicating the biases in original labels. To evaluate the clustering quality, we compare standard clustering with DBSCAN to that of our fair results using normalized mutual information (NMI) (Danon et al. 2005) and ad- justed rand index (ARI) (Hubert & Arabie 1985) where higher values indicate better results. When assessing NMI and ARI regarding DBSCAN results (denoted as NMI ARI exclude data points marked as noise by DBSCAN in both solutions when computing these measures. DBSCAN's We additionally include DCSI (Gauss) et al. 2024) as an internal evaluation measure to assess quality of density- clusters of arbitrary shape. DCSI evaluates the separation and connectivity of a cluster based on the density-connectio in DBSCAN (Ester et al. (996) (details in App. C22 We follow good evaluation practices as rec- ommended in Ullmann et al. (2023). Thus we not use other internal measures like Silhouette Coefficient (Rousseeuw 1987) or Dunn Index as they are not suitable for clusters with non-convex shapes (Gauss et al.] 2024). For clusterings C" that include noise labels, we compute NMI, ARI, and DCSI values based on all non-noise labeled points and multiply the results with the percentage of non-noise points. This accounts for the extent of data that is actually assigned to clusters. Note that detecting any noise prevents optimal score, introducing bias against noise-detecting methods like FairDen. However, detecting noise is essential for real-world use cases where the percentage of noise is unknown beforehand.
hyperparameters are optimized as described in Appendix C.I C.

---

Published as a conference paper at ICLR 2025
Table 1: Properties of our group-level fair competitors.
Algorithm
Fairlcts
Scalable Fair Clustering
Fair SC
FairDEN(ours)
Density-busee
X
x
x
Multiple sensitive attributes
X
x
Multiple (> 2) sensitive groups
Categorical features
3.2 EVALUATING FAIRNESS
Building on Equations and we report the balance (Chierichetti et al. 2017 Bera et al. 2019) for a clustering C. with & clusters the average balance over the individual clusters, with values between 0 and where higher values imply fairer results. Note that, while balance is one of the most common measures in the area of fairness in clustering, it has some limitations to be considered during evaluation and analysis:
If sensitive group is smaller than the number of clusters, at least one cluster has balance of O, significantly reducing the overall balance.
As the balances computed per cluster, higher balance does not necessarily mean that the majority of points are fair clusters, as cluster sizes might vary heavily. Some existing works only report the balance of the largest clusters (e.g., Bera et al. 2019 making a direct comparison difficult.
In order ensure fair evaluation in the presence of noise, adjust the balance calculation by excluding noise-labeled points for the calculation and multiplying the result by the percentage of non-noise points, similar the evaluation of clustering quality.
3.3 REAL WORLD DATA
We use the common benchmark datasets for fair clustering (Chhabra et al. 2021 Le Quy et al.
2022], details shown in Table The datasets Adult (Kohavi et al.] 1996). Bank (Moro et al. [014). Communities and Crime (Asuncion & Newman 2007), and Diabetes (Strack et al. (014)) provide different scenarios in terms of dimensionality and number of sensitive groups. Achieving a balanced
clustering for sensitive groups with fewer members than the number of clusters (k) is not feasible
(e.g., if a minority encloses only 2 members, they cannot be distributed across 5 clusters). Thus, we
include all data objects belonging sensitive groups of sufficient size: |Si k.
3.4 COMPETITORS
We compare FairDen with state-of-the-ar fair clustering methods aiming group-level faimesss. Tsooes important properties of FairDen and its competitors: FairDen closes several important gaps, as most state-of-the-art fair clustering methods handle neither categorical features nor multiple sensitive attributes. We compare to the following methods that we discuss more detail in Section
FairSC and normalized FairSC KKeindessner et al. 2019b) need weighted adjacency matrix as input. Thus, as common in spectral clustering, we employ kNN graph with & = 15 based on the numerical features and sensitive attributes to apply those methods also tabular data. Fairlet and Fairlet MCF (Chierichetti et al.) 2017) as well as Sealable Fair Clustering (Backurs et al. 2019) follow two-stage approach based on identifying fairlets. Since the construction fairlets is an N P-hhard problem both researchers present an approximative method, which are included in our experiments. The fairlet approach limits the methods one binary sensitive attribute. Thus, they cannot be used in all our experiments.
3.5 EXPERIMENTS
Fair Clustering of Real-World Benchmark Data Figure 2 shows that FairDen consistently reaches the highest competitive balance values for the real-world datasets when regarding only one sensitive attribute. Note that Fairlet and Scalable Fair Clustering cannot be applied to datasets with non-binary sensitive attributes. Table shows (along the balance values) also the evaluation of

---

Published as a conference paper at ICLR 2025
Balance
(gender)
(race)
Bank
Communties
DBSCAN
FairDn
Fairsc
Farsc (N)
Falrflt (MCF)
GroundTruth
Scalable
Figure 2: Balances for all competitors and benchmark datasets. Fairlet (MCF) and Scalable Fair Clustering are not included for settings including non-binary sensitive groups.
Table 2: Number of clusters k. Balance, DCSL, for real-world benchmark data. Diabetes dataset
for 2=2 (Ground truth) and k=44 (DBSCAN clusters) respectively.
Algorithm
Balance
DCSI
ARI
Algorithm
Balance
DCSI
DBSCAN
0.01
0.97
0.00
DBSCAN
0.01
0.65
-0.03
Adult (gender)
FairDen
0.86
0.04
0.05
Communitios
FairDen
0.92
0.15
0.09
FairSC
0.40
0.00
0.23
FairC
0.82
0.13
0.03
FairSC (N)
0.49
0.00
0.27
FairCC (N)
0.86
0.13
0.03
Fairlet (MCF)
0.94
Fairlet (MCF)
0.99
0.05
0.16
GroundTruth
0.66
0.00
1.00
Scalable
0.75
0,08
-0.03
Scalable
0.95
0.01
-0.01
GroundTruth
0.52
0.07
1.00
DBSCAN
0.50
0.02
DBSCAN
Adult (race)
FairDen
0.83
0.09
0.05
FairDen
0.96
0.08
0.01
FairSC
0.34
0.00
.0.03
FairSC
0.89
0.00
-0.01
1210 19 1 130N0
FairSC (N)
0.32
0.00
0.16
FairSC (N)
0.96
0.00
0.01
Fairlet (MCF)
Fairler (MCF)
0.97
0.00
0.00
Scalable
Diabetes
Scalable
0.99
0.01
0.00
GroundTruth
0,52
0.00
1.00
GroundTruth
0.96
0,00
1.00
DBSCAN
0.79
0.99
0.01
DBSCAN
0.01
0.88
FairDen
0,98
0.14
0.21
FairDen
0.95
0.24
Bank
FairSC
0.42
0.00
-0.06
FairSC
0.23
0.01
FairSC (N)
0.88
0.00
-0.04
FairSC (N)
0.61
0.19
Fairlet (MCF)
Fairlet (MCF)
0.95
0.00
Scalable
Scalable
0.96
0.07
GroundTruth
0.86
0.00
1.00
GroundTruth
clusterings, i.e., DCST and ARI. Density-comnected structures become more significant for higher numbers of clusters, while most benchmark datasets have binary classification as ground truth. Con- sequently, the DCSI values are very low as soon as few points are assigned differently than their density-conmectivity suggests. Nevertheless, FairDen achieves the highest DCSI besides DBSCAN for almost all datasets while improving the balance by large amount.
Multiple sensitive attributes While our competitors (Chierichetti et al. 2017 Backurs et al. 2019 Kleindessner et al.) (019b) cannot balance clustering with respect several sensitive at- tributes at once, FairDen can include an arbitrary number of sensitive attributes, successfully bal- ancing the sensitive attributes as Figure
We regard fairness with respect to all three sensi- tive attributes of the Adult dataset and study various combinations of sensitive attributes in FairDen. Each heat map shows the balance regarding the individual sensitive attributes. Note that this is different from balancing the combined groups. In the first heat map, each row represents the out- comes when labeling exactly one of the attributes as sensitive, while the remaining are included as non-sensitive categorical attributes. As expected, the balance for any sensitive attribute is highest in the row where it was included as sensitive in FairDen: each column's highest value lies on the diagonal. The second heat map shows results when including two sensitive attributes simultaneously indicated by the row description), yielding Pareto-optimal balance values for the respective at- tributes. The third heat map reveals an interesting effect: although all balance values are notably high (surpassing any combination for single sensitive attribute), it seems like we could achieve a better-balande of second heat map "M&R"). However, when inspecting the results and the underlying clustering, it is apparent that combining all three attributes results in more combinations of sensitive groups, consequently rendering the fairness constraint more complex than for just two sensitive attributes. When evaluating the balance across the combined sensitive groups, three sensitive attributes results in a higher balance (0.32) regarding the combination than "M&R" (0.25). Thus, the consideration of combined sensitive groups may not always yield the optimal solu-
cluster when using only marital status and race as sensitive attributes (row three
observe that including
8

---

Published as a conference paper at ICLR 2025
Sensilive attributess
0.96
0.86
0.73
GBR G&M
0.97
0.74
0.82
CBMBR
0.94
0.76
0.79
0.5
0.82
0.87
0.83
0.78
0.9
0.6
0.91
0.93
0.9
0.85
Balance
Balance
Balance
Figure 3: Columns show balance with respect to sensitive attributes gender (G), marital status (M) and race (R) in FairDen clusterings of the Adult dataset. Left: results for clustering when including only of the sensitive attributes, highest column-wise values/balance for the attribute labeled as sensitive is framed green. Middle: results for clusterings when including two of the sensitive attributes indicated by the description. Lowest column-wise values/ balance of attribute that not labeled as sensitive is framed in red. Right: results for including all three sensitive attributes.
tion in terms of proportionally distributing individual sensitive attributes, but it does ensure the most balanced distribution across all combinations.
Categorical data In contrast to our competitors, FairDen inherently includes categorical attributes. We conducted comparison results, excluding (FairDen-) and including (FairDen) categorical at- tributes in Table 3 with sensitive attributes as indi- cated, As the DCSI is not defined for data with cate- gorical attributes, we only report the correspondence DBSCAN results (columns ARI g and NM) The results, see Table show that both versions usu- ally improve the balance with respect the ground truth. When incorporating categorical attributes, the balance increases. The correspondence to original DBSCAN clusters stays approximately the same for both versions, i.e., the density-conneectvity aspect not negatively influenced by including categorical attributes. Lastly, noise levels consistently remained low for the three datasets.
Table 3: Comparison of results when exclud- ing/including (FairDen-/ FairDen) categori- cal attributes for datasets Adult (sensitive tribute: gender/ race) and Bank. Note that
none of our fair competitors is able work
with categorical attributes.
Algorithm
Balance
ARlos
NMD
Noise
DBSCAN
FairDen
0.96
0.00
0.00
0.00
Adult
FairDen-
0.86
0.00
0.00
Ground Truth
0.66
-0.04
0.01
(r)
DBSCAN
0.50
1.00
FairDen
0.86
0.01
0.01
0.00
FairDen-
0.83
0.01
0.02
0.00
Ground Truth
0.52
0.01
0.01
DBSCAN
0.79
1.00
1.00
FairDen
0.99
0.01
0.01
0.00
Bank
FairDen-
0,98
0.01
0.01
0.00
Ground Truth
0.86
0.00
0.00
Robustness with respect to number of clusters In all previous experiments, the number of clusters (k:) was determined based on the ground truth of the dataset or DBSCAN clustering (cf. Appendix C. In Figure 4 we assess the performance and balance all algorithms under consideration for various numbers of clusters. Note that the Fairlet (MCF) and Scalable Fair Clustering approaches cannot handle data with non-binary sensitive attributes. As a result, for the sensitive attribute race (depicted on the left), comparisons can only be made with FairSC versions. In this context, FairDen constantly receives the highest balance (top left) while achieving comparable quality measured by DCSI. When gender is considered as the sen- sitive attribute (on the right), FairDen exhibits the highest DCSI up to k 4, and is only surpassed by Scalable and the FairSC variants for larger number of clusters. Notably, all methods except FairSC versions yield relatively high balance values.
RELATED WORK: GROUP-LEVEL FAIR CLUSTERING USING BALANCE
Several fair clustering methods have been developed to ensure geoup-level fair clustering. We refer to the notion of group-level fairness as introduced by Chierichetti al. (2017), which aims to ensure that each group is represented in each cluster in proportions similar to the overall dataset. Other def- initions such proportional faimess (Chen al. 2019) also exist. Many works have approached this problem from different angles, e.g., including probabilistically defined croup-memberskee (Es- maeili et al. 2020), treating it constrained optimization problem (Esmaeili et al. 2021) and

---

Published as a conference paper at ICLR 2025
Adult (race)
Adult (gender)
Balance
Balance
0.5
0.5
0.0
0.0
10
10
Adult (race)
Adult (gender)
D090
0.0
0.0
10
FairDen
FairSC
FairSC (N)
Fairlet (MCF)
Scalable
Figure 4: Balance (top) and DCSI (bottom) depending on number of clusters k. Gender has only
two sensitive groups, race has five sensitive groups, which some competitors cannot handle.
integrating different notions of group-level fairness (Dickerson et al. 2024). Our focus is on work that optimizes balance.
Chierichetti et al. (2017) and Bereea et al. (2018) proposed two-stage approaches. Chierichetti et al. (2017) introduced the concept of fairlets, which are minimal sets of points with a balanced distribution. These fairlets are then used as input for subsequent clustering method, achieving a balanced clustering that can approximately preserve clustering objectives for k-center or k-means. Bercea et al. (2018) solve a fair reassignment problem with a linear program (LP) based on weakly supervised rounding. However, these methods are more suitable for cantrod-bbase approaches and are not appropriate for density-connected clusters: These minimal subsets can influence the density- connectivity between clusters significantly, leading to potentially very poor approximation. This where clustering a three moons toy dataset with a binary sensitive attribute using fairlets in density-connected structures consisting of only one sensitive group (e.g.. the middle cluster) leads to an undesirable patchwork of points in the left and middle cluster. Similar to Bercea et al. (2018). Bera et al. (2019) and Ahhmadian et al. (2019) present LP-based algorithms. Bera et al. (2019) aims for a balance within bounds depending on a user-input a and B, which differs from the focus of this paper, where we optimize the balance objective. Based on the solution returned by clustering algorithm, they solve fair assignment problem with an LP. Note that, while this approach allows non-binary sensitive attributes, is still only defined for k-center, k-median, and k- means objective. [Ahmadian al. (2019) solve the k-center objective with bicriteria approximation guarantee, bounding the additive violation. Scalable Fair Clustering (Backurs al.) 2019) partitions the dataset into fairlets that are merged into k clusters. The merging alleviates problems caused by fairlets in similar approaches (see Figure T so that clusters are more contiguous. Fair Spectral Clustering (FairSC) (Kleindessner et al. 2019h) is group-level fair spectral clustering algorithm that builds on an affinity graph. It comes in two versions: unnormalized FairSC, which is based on ratio cuts, and normalized FairSC, which is based normalized cuts. However, FairSC can handle only one sensitive attribute and lacks details on how to obtain the affinity graph from tabular data.
effect is evident in Figure [
Note that all these approaches do not consider density or density-comnectivity, have limitations in handling noise, and do not accommodate categorical data in the clustering process. Additionally, methods based on fairlets struggle with multiple sensitive attributes or more than two sensitive groups. These limitations are summarized in Table
5 CONCLUSION
We introduced FairDen, the first density-based fair clustering algorithm. By imposing faimess to the density-connectivity distance we transformed the problem to graph cut solvable with spectral clustering. FairDen is, to the best of our knowledge, the first group-level fair clustering algorithm that incorporates categorical data, multiple sensitive attributes, and non- non-binary sensitive attributes at once. Extensive experiments show that FairDen indeed finds fair and density-based clusters. Future work includes investigating different fairness notions, handling micro-clusters, and exploiting GPU parallelism and Nyström approximation (Hohma et al. 2022) for runtime improvement.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work was partially funded by project W2/W3-108 Initiative and Networking Fund of the Helmholtz Association and partially supported by the Pioneer Centre for AI, DNRF grant number Pl.
REFERENCES
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 267-275, 2019.
Mihael Ankerst, Markus M Breunig, Hans-Peter Kriegel, and Jörg Sander. OPTICS: Ordering points to identify the clustering structure. ACM Sigmod record, 28(2):49-60, 1999.
Arthur Asuncion and David Newman. UCI machine learning repository, 2007.
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scal- able fair clustering. In International Conference Machine Learning, pp. 405-413. PMLR, 2019.
Anna Beer, Andrew Draganov, Ellen Hohma, Philipp Jahn, Christian MM Frey, and Ira Assent. Con- necting the poss-Densty-Coomeetvvi Distance unifies DBSCAN, k-Center and Spectral Clus- tering. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 80-92, 2023.
Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32, 2019.
Ioana Bercea, Martin GroB, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. arXiv preprint arXiv:1811.10311 2018.
Shyam Boriah, Varun Chandola, and Vipin Kumar. Similarity measures for categorical data: A comparative evaluation. In Proceedings of the 2008 SIAM International Conference on Data Mining, pp. 243-254. SIAM, 2008.
Ricardo G. B. Campello, Davoud Moulavi, and Joerg Sander. Density- clustering based on hierarchical density estimates. In Jian Pei, Vincent S. Tseng, Longbing Cao, Hiroshi Motoda, and Guandong Xu (eds.), Advances in Knowledge Discovery and Data Mining, pp. 160-172, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. ISBN 978-3-642-37456-2. doi: https: //doi.org/ 1ttp////...0000/0--0101 (007997--3--42-37556-222---
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering, In International Conference on Machine Learning, pp. 1032-1041. PMLR, 2019.
Anshuman Chhabra, Karina Masalkovaité, and Prasant Mohapatra. Overview of Fairness in Clustering. IEEE Access, 9:130698-130729 2021. doi: 10.1109/ACCES. 1LL10//ACCESS2222111110099
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in Neural Information Processing Systems, 30, 2017.
Leon Danon, Albert Diaz-Guilera, Jordi Duch, and Alex Arenas. Comparing community structure identification. Journal of statistical mechanics: Theory and experiment, (005(09): 2005.
John Dickerson, Seyed Esmaeili, Jamie Morgenstern, and Claire Jie Zhang. Doubly constrained fair clustering. Advances in Neural Information Processing Systems, 36, 2024.
Julia Dressel and Hany Farid. The accuracy, faimess, and limits of predicting recidivism. Science advances, 4( (()acaa05588 2018.
Seyed Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John Dickerson, Probabilistic fair clus- tering. Advances in Neural Information Processing Systems, 33:12743-12753 2020.

---

Published as a conference paper at ICLR 2025
Seyed Esmaeili, Brian Brubach, Aravind Srinivasan, and John Dickerson. Fair clustering under bounded cost, Advances in Neural Information Processing Systems, 34:14345-14357 2021.
Martin Ester, Hans- Kriegel, Jörg Sander, Xiaowei Xu, al. A Density- Bastdd Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD, volume 96, pp. 226-231, 1996.
Jana Gauss, Fabian Scheipl, and Moritz Herrmann. DCSI-An improved measure cluster separa- bility based on separation and connectedness. arXiv preprint arXiv:23 12.0000 2024.
Usman Gohar and Lu Cheng. A survey on intersectional faimesss in machine learning: Notions, mitigation, and challenges. arXiv preprint arXiv:2305.0696) 2023.
Sariel Har-Peled. Geometric approximation algorithms. Lecture Notes for CS598, UIUC, 14, 2008.
Sibylle Hess, Wouter Duivesteijn, Philipp
Honysz, and Katharina Morik. The SpectACI of non- convex clustering: spectral approach to density-based clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3788-3795, 2019. doi: https://doi.org// org///0.
1609/aaai
Ellen Hohma, Christian MM Frey, Anna Beer, and Thomas Seidl. SCAR: spectral clustering accel- crated and robustified. Proceedings of the VLDB Endowment, 15(11):3031-3444 2022.
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2:193-218, 1985.
Philipp Jahn, Christian MM Frey, Anna Beer, Collin Leiber, and Thomas Seidl. Data with Density- Based Clusters: A Generator for Systematic Evaluation of Clustering Algorithms. In Joint Eu- ropean Conference on Machine Learning and Knowledge Discovery Databases, pp. 3-21. Springer, 2024.
Faisal Kamiran, Indrè Zliobaité, and Toon Calders. Quantifying explainable discrimination and removing illegal discrimination in automated decision making. Knowledge and Information Sys- tems, 35:613 154411664,,0 2013.
Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness- classifier with prejudice remover regularizer. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II 23, pp. 35-50. Springer, 2012.
Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In International Conference on Machine Learning, pp. 3448-3457. PMLR, 2019a.
Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstem. Guarantees for spectral clustering with fairness constraints. International Conference on Machine Learning, pp. 3458-34677 PMLR, 2019b.
Ron Kohavi et al. Scaling up the accuracy of naive-bayes classifiers: decision-tre -tee hybrid. In Kdd, volume 96, pp. 202-207. 1996.
Tai Le Quy, Arjun Roy, Vasileios losifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning. Wiley Interdisciplinary Reviews: Data Mining and Knowl- edge Discovery, 1252,, 2022.
Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2):129-136, 1982.
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
Peter Rousseeuw, Silhouettes: a graphical aid to the interpretation and validation of cluster analy- sis. Journal of Computational and Applied Mathematics, 20:53-65, 1987.
12

---

Published as a conference paper at ICLR 2025
Erich Schubert, Jörg Sander, Martin Ester, Hans Peter Kriegel, and Xiaowei Xu. DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems (TODS), 42(3):1-21, 2017. doi: https://doi.org/10.. http://...orrr11..1117335333333 145/3068335.
Beata Strack, Jonathan P DeShazo, Chris Gennings, Juan L Olmo, Sebastian Ventura, Krzysztof Cios, John N Clore, et al. Impact of НbAlc measurement on hospital readmission rates: analysis of 70,000 clinical database patient records. BioMed Research International, 2014, 2014.
Theresa Ullmann, Anna Beer, Maximilian Hünemörder, Thomas Seidl, and Anne-Laure Boulesteix. Over-optimistic evaluation and reporting of novel cluster algorithms: An illustrative study, Ad- vances Data Analysis and Classification, 17(1):211-22) 2023.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17:395 416,,441666000 2007.
13

---

Published as a conference paper at ICLR 2025
A FAIRDEN
A. PSEUDO-CODE
The pseudo-code for novel fair benssttybasee clustering method FairDen is given in Algorithm
Algorithm FairDen
Input: X' E R dataset, G E R group-membership vectors for each of the a sensitive at-
tributes, pl,
Output: assignment of point in X' to one of cluster indices or to index -1 for noise
1: Dde dc-distance(2)) pairwise dc-distances in X'
2: A - 1- - Dae/ mar(Dde) get affinity matrix (Eq. I A get Laplacian (Eq.
3: L
4: f +- combined membership(C (G) membership vector to combined sensitive group S, for each
point p E X
5: F + f [8.l I, get Fairnsss matrix
6: Z + orth_base (aais(nullspace(F)) get orthonormal basis for the nullspace of FFT (Eq. 11
7: Q VETDZ
8: V + k smallest eigenvectors of ( CBQ-
9: + zQ-11
10: Clustering C t k-mmans(H)) compute clustering
while [Ci] < μ (for any cluster Ci) do
12: CN C₁, for [r] <
13: ir \ Cxl
then
14: repeat step 10 for k: = k 1
15: else
16: return C
17: end if
18:
end while
14

---

Published as a conference paper at ICLR 2025
A.2 MIN POINTS ABLATION
Table gives a small ablation study for the hyperparameter that we set, according to Schubert al. (2077), μ 2d for all experiments in the main part of the paper. According rows marked in bold. While there is no free lunch, the heuristic yields a good trade-off between clustering quality measured by DCSI and balance for all data sets.
Table 4: Overview of DCSI, balance and noise (in %) results regarding different values for μ..
Data
DCSI
Balance
Noise
0,9867
0,4983
4
Adult (g)
0,9867
0.4983
0,0880
0.8142
10
0.0005
0.0878
0.8343
0.0005
0.0091
0,8630
15
0.0005
0,0000
0.4990
Adult (r)
0.0989
0,8480
0.0005
0.0677
0.8499
0.0005
0.0599
0.8603
11
0.0005
0.0436
0.8633
0.0005
0.0706
0,9603
0.0910
0.9649
Bank
0.1357
0.9795
0.1613
0.9942
10
0.0567
0.9887
15
0.2028
0.8533
0.0005
Communities
0.1325
0.8408
0.0005
0,0963
0.8536
10
0.0005
0.1461
0.8620
0.0005
0.1533
0.9199
135
0.0005
0.0744
0.9606
0.0002
Diabetes
0,1193
0.9691
10
0.0002
0.0756
0.9622
0.0002
A.3 RUNTIME EXPERIMENTS
In this section, we investigate FairDen's runtime in comparison to our competitors.
Experiment design We perform three experiments regarding the runtime of FairDen. We examine three scenarios: (a) increasing the number of data points (b) increasing the number of numerical features (dimension of the dataset), and (c) increasing the number of ground truth clusters. We generate datasets with the data generator DENSIRED (DENSIty-based Reproducible Experimental Data) (Jahn et al., (024)) for these experiments. The parameters used for the generation of the datasets are shown in Table [5] Note that the data generator generates entirely new datasets for each configuration. Consequently, not only do the parameters we intend to adjust vary, but underlying structures do as well. We randomly assign a binary, sensitive attribute (by permuting an array composed of 50% ones and 50% zeros). The random assignment entails that we cannot guarantee the distribution within the clusters. As a result, the different datasets may not be directly comparable. However, this approach ensures equal conditions for all of the algorithms.
Experiment setup We perform five runs for each generated dataset. The runtime experiments performed on workstation with an AMD Ryzen Threadripper PRO 3955W, 250 GB RAM, and an RTX 3090. We set the cutoff time for each individual run to two hours.
15

---

Published as a conference paper at ICLR 2025
Table 5: DENSIRED parameters for runtime experiments.
Scenario
Number of data points
Dimensionality
Number of clusters
(a) 100, 200, 500, 1000, 2,000, 5,000, 10,000
10
2
(b)
2,000
10, 50, 100, 1,000
2
(c)
2,000
10
2,3,4,5.6,7,8,99
Results
Figures show runtime in seconds for the previously defined scenarios.
In the first scenario, we increase the number of data points in the dataset. The results are shown in Figure 5 We observe that our runtime increase is similar normalized FairSC, with FairDen demonstrating slightly faster performance across the five runs. Both FairSC and Scalable Fair Clus- tering are faster. Fairlets, in contrast, has a significantly higher runtime that exceeds our cutoff of 120 minutes for datasets with more than 2000 data points.
2000
Time
1000
500
0
2000
4000
6000
8000
10000
n
FairDen
Fairsc
FairSC (N)
Fairist (MCF)
Scalable
Figure 5: Runtime experiments for increasing numbers of data points n, with ranging from 100 10,000. Fairlet exceeds the time cutoff for more than 2,000 data points.
In the second scenario, increase the dimensionality of the dataset. Since proposed selection for depends on the dimensionality we regard two versions of FairDen in Figure 6 The bright pink color shows FairDen used throughout the paper with the automatically computed μr, the dark green denotes FairDen with fixed 5=5. The runtimes of both versions are very similar, ranging in difference of around 0.1 seconds.
After introducing the comparison of the two FairDen versions we want to include comparison across different methods, see the top of Figure 7 The left plot illustrates that the Fairlet approach does not yield comparable runtimes. We include second version of the plot excluding Fairlets to show the differences between the remaining approaches better. Although all of the algorithms can calculate the result in less than 18 seconds we observe some variations in runtime. While FairSC and Scalable not even need 2.5 seconds, normalized FairSC needs around FairDen requires more time; the difference observed here between the various dimensions of the dataset partly due to the fact that calculating the de-distance takes little longer. The calculations after determining the de-distance independent of the dimensions of the dataset.
In the third scenario, we increase the number of ground truth clusters in the dataset. The runtime results for this experiment illustrated in the bottom of Figure 7 Note that the distribution of sen- sitive attributes or the underlying clustering structures or noise points, might vary heavily between the different datasets. We observe that especially in the bottom right part of Figure 7 for k 5.
16

---

Published as a conference paper at ICLR 2025
Algorithm
FairDen (adjusted)
FairDen (fixed)
4.8
4.4
4.2
40
100
Dim
Figure 6: Runtime in seconds for FairDen with fixed μ= and y automatically computed based the dimensionality the data as used throughout the paper.
Runtime among all methods (up to 41 min)
Runtime among fastest methods (up to 18 sec)
2500
2000
1500
Time
10
1000
500
0
200
400
600
800
1000
0
200
400
600
800
1000
Number of features
Number of features
(up to min)
(up to sec)
2500
2000
Time
Time
1000
500
0
6
2
Number of clusters
Number of clusters
FairDen
FairSC
FairSC (N)
Fairlet (MCF)
Scalable
Figure 7: Runtime in seconds for experiments regarding (top) increasing numbers of features and (bottom) increasing numbers of clusters (k), for & ranging from 2 to 9. Left: includes all of the algorithms. Right: algorithms excluding the slowest method, Fairlet MCF, For the experiments with increasing number of features, used FairDen with fixed value of 5=5,
where FairDen has peak the runtime. Note that also the curves of FairSC and FairSC(N) have small bumps here. This effect might be due to an unfortunate positioning of noise points in this specific dataset. Except for this outlier, FairDen performs very similar normalized FairSC. While FairSC and especially Scalable are significantly faster. The Fairlet approach needs again more time than any of the competitors with around 40 minutes per run.
17

---

Published as a conference paper at ICLR 2025
B TECHNICAL BACKGROUND
The following section includes technical details regarding the de-distance and DBSCAN.
B. DBSCAN
DBSCAN ODensity-Based Spatial Clustering of Applications with Noise) (Ester al.) 1996) one of the most prominent clustering algorithms regarding the notion of density-based clustering. The algorithm differentiates between core points, border points, and noise points. The process DB- SCAN clustering is illustrated for minPts=5 in Fig. g The minPtss parameter denotes the mini- mum number of points required within a point's e-radius for it to be regarded as a core point. Points with less than minPts neighbors in their e-neighborhood are considered border points if and only they have at least one core point in their e-meighborhood, otherwise the point is considered a noise point. DBSCAN implementations label noise points with -1.
Noise points
Border points
3
Core points
Figure 8: Illustration of DBSCAN clustering with minPts=:
B.2 DENSITY-CONNECTIVTY DISTANCE
The censity-comnectivigg distance (dc-distance) is defined in Beer et al. (2023). It is based on
the mutual reachability distance dm (1, y) max (x), deone denec x., y)) which known from works as, e.g., DBSCAN (Ester et al., 1996). OPTICS (Ankerst et al. 1999), or HDB- SCAN (Campello et al. 2013). The dc-distance represents the minimax (path) distance on the graph given by the mutual reachability distance dm, see Eq. 16
ddc( v) = min max |el.
(16)
PEP eEp(2.y)
where the length |el of edge e a path p(ar, y) that connects points æ and y is given by the de-distance between the nodes that are connected by e. Intuitively, the de-distance provides the smallest so that two points are density-comnected. As the de-distance is based on the minimax distance, it inherits relevant properties that make it well-defined (ultra-)metric (also known as rooted tree metric (Beer et al. 2023), which allows the representation of its distance matrix as tree or hierarchy). The hierarchy established by the dc-distance works analogously to how the single link distance defines the traditional clustering hierarchy given by agglomerative single-linkage clustering. For more details, we refer the reader to the original paper by Beer al. (2023).
18

---

Published as a conference paper at ICLR 2025
Table 6: Properties Real-Worke datasets. Sensitive attributes a, number of sensitive groups g(a) for attribute number of numerical features dn, number of categorical features de, DBSCAN parameters minPts and E.
Dataset
Sens. Attr. (g(a))
dn de)
minPts
race (5)
5 (+2)
4
2.1
Adult (Kohavi et al.
1996)
gender (2)
5 (+2)
9
0.15
marital status (7)
5 (+2)
1.2
Bank (Moro et al.
2014
marital (3)
3 (+2)
Communities (Asuncion & Newman 2007)
black (2)
67
10
3.25
diabetes (Strack et al.
2014)
gender (2)
7
10
0.45
C EXPERIMENT DETAILS
In the following, we give all experimental details and parameter settings, the definition of the used evaluation measure DCSI, and details of the real-world benchmark datasets.
C.I EXPERIMENT SETTINGS
The experiments are performed on a MacBook Pro, with an M2 Pro, and 16 GB of RAM using Python 3.9. Where possible, we integrated the author implementations for our competitors and the code reproducing every experiment for every competitor is included in our our git
The parameters of Scalable Fair Clustering are set according to the implementation 2019) that the maximum desirable balance is set, p and
(Backurs al,
Sxx
with SS.
< S
The parameters for DBSCAN, min and E, were determined with a hyperparameter optimiza- tion. The criterion for the optimization is the DCSI score with a constant setting minPtspcsi 5. The parameter space for mainPtspBSCAN comprises (4, 10, 15, 2d - 1}. with d being the dimen- sion of the dataset, and for & E {0.01, 0.05, 0.1, 0.5, 0.6, 2.5, 2.6, 2.8, 3.25, 3.7,3.75). The final parameter settings are given in Table
C.2 DCSI
DCSI (Gauss et al. 2024) is an internal clustering validity index, that assesses the quality of a clustering regarding the connectedness and separability of the assigned clusters. The score relies on the notion core points defined similarly to DBSCAN. The definition differs in terms of the parameters minPtss and c, instead of defining them globally for all clusters, the approach of DCSI regards them as parameters that should be set individually for each cluster. The score includes only core points in its calculation. Core points are defined points & with least minPlss data points from the same cluster having distance d(x,x²) < E;, note that E; and minPts; are defined separately for each cluster i. The distance employed here is the mutual reachability distance.
2
DCSI(C) K(K
DCSI(G, Cj)
(17)
DCSI(C, C3) = 1 9 where = Sepposi (C, C2)
(18)
Comn (C,, C₁)
Separation is defined as the minimum distance between the core points of two clusters, C, and C₁+ denoting how well the classes are separated. Connectedness is defined as the maximum distance between core points within one cluster. The choice core points depends on minPts and denotes the influence of noise/outliers. The proposed values min.tts = 5 for all clusters and e, set to the median distance between all points x within the cluster and their 2- -inniis nearest neighbor in cluster i. The score, Eq. 17 is accumulation of DCSI scores calculated for each pair of clusters
19

---

Published as a conference paper at ICLR 2025
(ef. Eq. 18 Higher scoring denotes better clustering. Note that the score drops significantly when a certain number of points is assigned to another cluster than the optimal density-based based clustering.
C.3 REAL WORLD DATA
This section includes overview of the included real-world datasets and our corresponding prepro- cessing.
Adult. The Adult dataset (Kohavi et al. 1996) includes 15 demographic features and categorizes 48,842 people based on their annual incom (above or below 50,000 US-dollars). The sensitive attributes are gender, race and marital starus. Depending on the setting. it has five numerical and up to two categorical features. Note that the distribution of groups within the individual sensitive attributes can vary largely, e.g., more than 70% of the data points belong to one protected race- group. We sampled 2000 data points from the dataset and removed duplicate entries based on the remaining features.
b) Bank. The bank marketing dataset (Moro et al. 2014 includes seventeen features that have been collected during marketing campaigns in Portugal between 2008 and 2013, The sensitive attribute marital includes three sensitive groups married, divorced, and single. The dataset includes binary categorization whether a person subscribed to term deposit or not. We include three numerical and two categorical variables. We sample the dataset to 5000 data points and remove duplicate entries based on the remaining features.
c) Communities and Crime Communities and Crime (Asuncion & Newman, 2007 includes data from the 1990 US census, law enforcement data from the 1990 LEMAS survey and crime data from the 1995 FBI's Uniform Crime Reporting (UCR). We use sensitive attributes as described in Kamiran et al. (2013) and Kamishima et al. (0012), yielding 67 numerical features. We exclude duplicate data points.
d) Diabetes The diabetes dataset (Strack et al. 2014) includes medical records regarding diabetes from 130 US hospitals. is labeled according whether patient is readmitted within 30 days. We include seven numerical features and sample the number of data points to 5000, removing duplicates. The sensitive attribute is gender, divided into female and male.
20


Reviews:
[{"review_id": "MpjPf5Kxc5", "reviewer": "Reviewer_ygXB", "summary": "The paper proposes a method for fair density-based clustering, whereby the discovered groupings satisfy certain fairness criteria in the context of sensitive attributes.  Whilst fairness criteria have been explored  for other clustering methods, this appears to be the first work that addresses it for density based clustering.  The key insight of the paper is to model density connectivity between points using a continuous representation, that facilitates a so-called fairness-balancing procedure.  The proposed method is distinguished in its ability to handle aspects such as categorical attributes, noise and mixed data.", "questions": "Figure 1 – it is hard to visually distinguish which methods are producing better clusters.  They all look rather similar.  It’s also hard to visually match the balance and dcsi values to the clusters.  DCSI is mentioned in the caption before it has been defined in the paper.\n\nIn Table 2 and Table 3, the ARI/NMI seem very low (close to zero).  Earlier it is mentioned that higher is preferable.  How is one supposed to interpret such low values – is it a drawback of the clustering method?\n\nTo what extent would be the approach for the fairness constraint described in 2.2, be extendible to different or multiple fairness constraints?   Does feasibility need to be worked through on a case by case basis?\n\nCan scalability and noise be examined further, as described above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-fills a gap in the fair clustering literature through its focus on density based clustering.  Density based methods can be particularly attractive through their ability to handle scenarios with categorical data and noise\n\n-proposed method is able to handle scenarios with categorical attributes and mixed type data, in contrast to some baselines.  It can also handle scenarios with multiple sensitive attributes.  It is thus quite “expressive” in terms of fair clustering approaches.\n\n-its formulation leverages well known and principled approaches through spectral clustering\n\n-solid experimental performance in terms of balance for a single sensitive attribute.  Some exploration of the benefits of multiple sensitive attributes.", "weaknesses": "-approach is potentially expensive computationally being O(d*n^3).  The experiments don’t explore runtime of the method, particularly for larger datasets.  The selected real world datasets appear to be of smaller size.\n  Can this aspect be explored further to provide more insight?\n\n-The proposed method allows inclusion of noise points, which is a strength.  However, it is not so clear from the experiments what can be the advantages of handling noise.  Indeed noise points are specifically excluded in some of the evaluations.  Could a specific experiment be designed to evaluate the role of noise for fair clustering?", "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": "", "extra_scores": {}}, {"review_id": "rh97G7jubk", "reviewer": "Reviewer_Jc4S", "summary": "The paper introduces a new density-based clustering method called FairDen - it is designed to incorporate fairness without compromising the density-based structure of the data.  Fairness has been studied in clusterings, but density-based clustering algorithms have not been studied through the fairness lens.\n\nDensity-based clustering methods come with their own merits - eg, they can handle categorical data (or in general, mixed data types) and can handle noise.  FariDen inherits these nice properties.  In addition, it can handle mutiple sensitive attributes simultaneously.  Experiments on real-world datasets show that FairDen produces fairer and more balanced clusters compared to other density-based algorithms and better captures density-based clusters than existing fairness-oriented algorithms - thus achieving the better of both worlds. \n\nTechnically, the key idea is based on Eqn (11) - how to incorporate the fairness constraint into the normalized cut objective.  Eqn (12) essentially summarizes the paper's contribution.  The task then is show how to solve (12) via spectral clustering.  Luckily, the fairness constraint is (rigid and) easy enough to be able to reshape the constrained problem into an unconstrained spectral clustering problem.", "questions": "The constraint in (11) is very rigid.  Could you methods be adopted to relax it to say an approximation of it?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* DBScan is widely used and practical clustering algorithm and a fair version of it is a natural question\n\n* The ability to handle categorical data, which is more of a property of DBScan.\n\n* The proposed method can handle several sensitive attributes.\n\n* The paper has good experimental results, showing good outcomes on both the balance aspect as well the density aspect", "weaknesses": "* The ideas are incremental and largely based on based on existing work.  The dc distance (continuous) formulation is from the KDD paper of Beer et al and solving such problems with spectral methods is quite standard, even in the fairness literature.\n\n* The fairness constraint it treated in a very rigid way, which makes the problem way too simple.  (Eqn (12)).  A more relaxed accommodation of fairness (instead of equality, an approximation in some matrix-norm sense) would be more meaningful here.  \n\n* The scalability of the algorithm is also unclear for large datasets (complexity=O(n^3)), given its reliance on spectral methods.  (This criticism is applicable to some other but not all work on fair clustering).  Combinatorial or sketching algorithms might have better running times.  \n\n* The writing is extremely poor.  It assumes that the reader has a lot of background on the KDD 2023 paper and even about DBScan.  The paper is hardly self-contained - the authors could have written more clearly or provided missing details in the Appendix.  For example, they assume the reader knows what an ultrametric is or an ultrametric leads to a hierarchy ... there are many such instances.  See minor comments below.\n\nMinor comments:\n\n93: not sure e-range is standard -> use eps-radius?\n\n89-93: sloppily written - hard to parse\n\n116: the ddc distance is taken from Beer et al - not even defined in the text\n\n119: what is the hierarchy you are talking about?\n\n127-134: hard to parse\n\n145: state I_k is the kxk identity matrix\n\n161: The model itself is not clear here: what does single index S_i mean?  Is the setting as simple as a bipartite graph of X times S, where edges from X to S denote membership of a user in a sensitive group?  At the end of the sentence, i is used to index attributes where in the beginning, it is used to index the user (data). In fact, for S_{ij} what does i and j stand for?\n\n162: what is k? (i assume # clusters)\n\n167: r_ij is not the whole dataset (as written it reads that way)\n\n176: it might be enough to index balance_{ij} instead of balance_{S_{ij}}\n\n197: what is the quantifier for l in (10)\n\n219: why does the inverse ultrametric even matter?\n\n305: Aren't there are scenarios where heavy bias is inevitable and hence replicating the biases in the clusterng is also inevitable?  \n\n357: again, what is k?", "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": "", "extra_scores": {}}, {"review_id": "FqIYX2VRzs", "reviewer": "Reviewer_DheD", "summary": "The paper presents FairDen, a density based clustering algorithm with group fairness considerations. As it is written in the paper, it is a novel approach, forming fair clusters that supports mixed-type data types, and multiple sensitive attributes, with a weighting mechanism. The contributions include the formulation of the algorithm in an analytical way, and a standard set of experimentation.", "questions": "Is there minimum number on the count of data types for the algorithm to be effective? In another words, how many numerical features are needed, relatively to be able to form fair clusters given various number of sensitive attributes? Has there been any more studies done on the algorithm that could be included to give more insights on this aspect of the algorithm?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this is a solid work, but to name a few strengths, I can mention these:\n1- The method is clearly described with some sound step by step derivation of the last optimization objective.\n2- The implementation is submitted as well.\n3- The experiments section cover a good set of algorithms and datasets.", "weaknesses": "There are a few things that could be better about this paper. Given these are addressed, I am willing to increase my scores:\n\n1- The limitations, such as the reduced performance on very small sensitive minority groups, are scattered throughout the text. A dedicated limitations section before the conclusion that consolidates these points would be beneficial.\n2- Figure 1 is a canonical figure, but could be more clear. Mainly because it is too visually dense and the description of it is broken down into pieces being in introduction section in the beginning and the related works towards the end. As an option, breaking it up into multiple figures with more information rich descriptions, especially, on the third colour used for the DBSCAN sub-figure would be beneficial.\n3- In the complexity analysis section, it is mentioned \"Note that runtime can be reduced significantly, e.g., by using the GPU for matrix computations.\". Although it is becoming a common knowledge that using parallel approaches can decrease practical runtime, this claim does not seem to be supported by an experiment. If there is explicit evidence to support it, it should be added. Otherwise, removal is advised.\n4- There are some writing issues that could be fixed:\n 4.1- Setting the most common abbreviations such as i.e., and e.g. aside, the paper has numerous abbreviations that is best to be omitted. \n Here are the list I found: \"iff\" on line 92, s.t. on lines 117, 221,523,... w.r.t on lines 416, 418 ... \n A full review of the paper and spelling out the non-standard abbreviations is advised.\n 4.2- The line numbers of Algorithm 1 are not appropriately referenced in the text. For example: on line 201, it is ambiguous that (line 4) is \n mentioning Algorithm 1 in the appendix. Making the reference explicit make the paper more readable.\n\nHere is a suggestions rather than stating weaknesses:\nThe authors did a great job with \"Multiple sensitive attributes\"and the following figure 3. It could be great to have a general interpretation section on the clusters that this algorithm forms.", "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": "", "extra_scores": {}}, {"review_id": "fV5FzKMzhF", "reviewer": "Reviewer_xP7u", "summary": "This paper proposes a density clustering method based on fair learning. The authors claim that it is the first fair clustering algorithm capable of handling mixed-type data and multiple sensitive attributes simultaneously. The algorithm also includes the ability to detect noise.", "questions": "1. Why does Table 3 not include results from other fair comparison methods?\n2. Do the experimental results depend on the parameters? The authors did not conduct experiments on this aspect.\n3. How does the proposed method address the issue of sensitive attribute combinations (e.g., Black women), particularly regarding the physical meaning of Equation 7? Could the authors provide a detailed explanation?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method successfully detects fair clusters of arbitrary shapes while achieving balance.\n2. The proposed density-based fair clustering method sounds interesting, and research in the field of fair machine learning also enhances contributions to the community.", "weaknesses": "1. The proposed method involves two existing ways to compute similarity matrices, and the form of the objective function is fundamentally consistent with spectral clustering. Although the authors emphasize that the distinction between their method and spectral clustering lies in the Laplacian matrix, this level of innovation is insufficient for ICLR.\n\n2. The discussion on existing fair clustering methods is insufficient and should include the following relevant literature:\n\n[1] Chen X, Fain B, Lyu L, et al. Proportionally fair clustering[C]//International conference on machine learning. PMLR, 2019: 1032-1041.\n[2] Esmaeili S, Brubach B, Tsepenekas L, et al. Probabilistic fair clustering[J]. Advances in Neural Information Processing Systems, 2020, 33: 12743-12755. \n[3] Esmaeili S, Brubach B, Srinivasan A, et al. Fair clustering under a bounded cost[J]. Advances in Neural Information Processing Systems, 2021, 34: 14345-14357.\n[4]Dickerson J, Esmaeili S, Morgenstern J H, et al. Doubly constrained fair clustering[J]. Advances in Neural Information Processing Systems, 2024, 36.\n\n3. There are several omissions in the paper. For instance, vol(c) should be vol(c_l),  and the output of Algorithm 1 is also unclear.\n4. The latest comparison method is from five years ago, which raises questions about the algorithm's effectiveness. Even without involving the most recent fair clustering methods, the referenced conventional clustering methods should not be limited to only DBSCAN.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)