FairDen: Fair Density-Based Clustering

Dear Reviewer,

thank you for your insightful feedback and time!

• W1: We would like to emphasize that fairness in density-based clustering has not been explored before. One of the key innovations in our work is the observation that dc-distance allows us to incorporate fairness into density-based clustering by using spectral clustering, though this is just one of the novel elements of our approach. In particular, FairDen is designed to handle non-binary sensitive groups, multiple sensitive attributes, and categorical data features— ignored by existing fair methods, despite their relevance in real-world scenarios. We are pleased that, despite the simplicity and clarity of our method, it effectively addresses several important issues and introduces unique contributions that differentiate it from competing approaches (see Table 1 for a summary).

  1. To the best of our knowledge, no other fair clustering method inherently includes handling categorical attributes, even though it is very typical for data with sensitive attributes (which are categorical) to also include other categorical attributes. While we include the similarity measure based on Goodall1 (Boriah et al., 2008), this approach cannot be used for center-based approaches.
  2. Multiple and non-binary sensitive attributes: Many fair methods, do not work for non-binary sensitive attributes, as it is a more complex problem – that, however, FairDen solves successfully. While two of the works referenced by you ([2] and [3]) also take into account non-binary sensitive attributes, integrating multiple sensitive attributes still poses a difficult problem they do not achieve.

• W2: We appreciate the suggestions for additional related work. In the interest of space, we originally limited the discussion to the core scope of the paper: group-level fair clustering optimizing the balance of sensitive attributes in combination with arbitrarily shaped clusters. Following your suggestion, in the revised version, lines 479-503, we added more details to clarify further this emerging research into a broader context to help to delineate our work more clearly. However, note that the suggested methods, in contrast to FairDen, do not aim at density-based clusters. Additionally, they solve different objectives than FairDen, thus, we did not include them in the comparative experiments: [1] is based on proportional fairness and not on balance, [2] assumes the sensitive group (color) is assigned probabilistically rather than deterministically, and [3] optimizes fairness as an objective function up to a determined upper bound of clustering cost. As [4] also includes group-level fairness, we are interested in further investigating it for its usage as a post-processing step for achieving fairness in density-based clustering - however, this is future work and out of the scope of this paper.

• W3: Thank you for the note, we fixed this typo in the revision and added some more details on the exact shape of the output of Algorithm 1.

• W4: As there are no fair density-based clustering algorithms besides FairDen yet, we compare FairDen to other group-level fair algorithms that can potentially find arbitrary-shaped clusters, as they bear some relationship to density-based clusters. We furthermore included the conventional clustering DBSCAN only as a baseline of which FairDen is the fair version, similar to related work (e.g., Kleindessner et al.) where fair spectral clustering is compared to its vanilla version (conventional spectral clustering). Since our focus is on density-based clustering we do not include centroid-based conventional clustering methods.

In the following, we answer the questions (Q1-Q3):

• Q1: This experiment assesses the inclusion of categorical data into FairDen vs excluding categorical data. As our competitors cannot handle categorical data, and also the evaluation measure DCSI cannot be applied to categorical attributes, we show the results of the datasets without the categorical attributes in Table 2. Thus, Table 3 contains only the additional results from methods that are capable of handling categorical attributes, i.e., DBSCAN and FairDen.

• Q2: While we automatically computed our only hyperparameter $\mu$ based on the data for all experiments, we had tested its influence on the clustering results. Because of space limitations, the results were included in the paper only in the appendix (A.2), but we refer to them more prominently in the revised version (l.302).

• Q3: A sensitive group can also be a combination like black women. Thus, for example, in Equation 7 there are two ways to compute the balance of a cluster. First, one could be interested in the balance regarding the individual sensitive attributes, i.e., "is the cluster balanced regarding gender?" And "is the cluster balanced regarding race?" In this case, both balance values are handled separately. The other option, which also corresponds to the solutions FairDen is finding, is to regard both sensitive attributes at once, i.e., combining them. Thus, for $a$ many sensitive groups for a sensitive attribute $A$ and $b$ many sensitive groups for another sensitive attribute $B$, we have up to $a$ times $b$ many combined sensitive groups (or fewer, as not every value combination might occur in the data).

Dear Reviewer,

Thank you for your time and your detailed review, especially the minor comments for improving our paper are much appreciated! We follow many of your suggestions for the revision and highlight changes in the revised PDF version in blue color. In the following, we address your questions:

• W1: We would like to point out that the integration of fairness into density-based clustering has not been studied before. Leveraging the dc-distance to incorporate fairness into density-based clustering is neither incremental nor our only contribution: Concretely, FairDen admits non-binary sensitive groups, multiple sensitive attributes, and categorical data aspects that other fair methods neglect despite their relevance for real-world data. We appreciate that our approach is still perceived as simple and coherent, even though it addresses several important aspects and novel contributions that our competitors do not (see Table 1 for an overview).

• W2 / Q1: Approximating fairness instead of optimizing it is an interesting idea for future work! As we note in the conclusion of the paper, also extending the approach to different notions of fairness, or investigation of related constrained problems are interesting open questions. However, in this paper, our goal is to optimize the fairness/balance.

• W3: We conducted some runtime experiments that we include in the revised version of the pdf, to set the computational complexity into context. Thank you for bringing up combinatorial or sketching algorithms, we see this as a promising direction for future work. However, as FairDen is the first fair density-based approach, our focus was on the conceptual contribution and quality, but not yet on runtime optimization.

• W4: We follow your suggestion and added more details in the revised version accordingly and added corresponding sections in the appendix (Appendix B “Technical Background“ ). Furthermore, we removed interesting, but not necessary parts (like the dc-distance being an ultrametric) from the paper and added details in the Appendix instead, see also our explanation regarding minor comment for l.119 at the end.

Regarding the minor comments: Thank you for your very detailed feedback! We addressed most of them directly, for those with a question, we provide some comments:

• “161: 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?”

  • We had omitted the index $i$ in $x_i \in X$ for simplicity, as it is not required in the rest of the paper, but we can see now that it might indeed be confusing regarding its later use in combination with $S$.
  • $S_i$ refers to any of the sensitive attributes (see line 162), where the number of different sensitive attributes is given by $a$, which we introduce earlier and more explicitly in the revised paper (than in the current line 179).
  • Each sensitive attribute (e.g., gender, race, age, …) can have several, usually categorical values. E.g., for gender, “male”, “female”, “diverse”. Those define three sensitive groups with regard to the sensitive attribute. We refer to the sensitive attribute with the first index, $i$, and to each of the groups for this attribute, using a second index, $j$.
  • One could model the membership of an object $x$ in a sensitive group $S_{ij}$ with an edge in a bipartite graph of $X \times |S_{ij}|$ . Every object $x$ has then exactly $a$ many edges (one for every sensitive attribute).

• “305: Aren't there are scenarios where heavy bias is inevitable and hence replicating the biases in the clusterng is also inevitable?”

  • Yes if the dataset only consists of data points that cannot be separated into fair clusters, i.e., the sensitive groups across different sensitive attributes are non-separable (intersection discrimination) there exists no fair solution. This observation is true for any fair clustering notion.

• “119: what is the hierarchy you are talking about?“

  • The hierarchy is defined by the dc-distance and works analogously to how the single link distance defines the standard clustering hierarchy given by agglomerative single-linkage clustering. We have tried to clarify this in the revised paper.

Dear Reviewer,

Thank you for your time and the helpful feedback! We address each of the weaknesses and questions individually. We highlight changes in the revised pdf version in blue color.

• W1: Thank you for the suggestion of adding a limitations section! We added the section in the revised version, see lines 288-292.

• W2: We have simplified Figure 1 based on your comment, and enhanced it with a legend, along with an updated caption to improve clarity.

• W3: We believe that GPU parallelization is a promising direction for future work, especially considering the complexity of the problem that other reviewers also noted. Thus, we would like to keep mentioning this idea in the paper, despite no experimental backup. Thus, in the revised version, we clarified it is future work and accordingly moved it to the conclusion (line 540) – is this an appropriate solution to your concern?

• W4: Thank you for the detailed remarks, we directly followed them and improved the paper accordingly.

• Regarding your last paragraph with the suggestion: Thank you! We added a paragraph regarding the interpretation of clusters in the analysis section, lines 274-281.

• Q1: This is a very interesting point of discussion, the number of numerical features or sensitive attributes do not play as important a role as the distributions they represent. In the extreme case, it might be that there is only one sensitive attribute with feature values distributed such that fairness is in direct contradiction to density-based clustering using numerical features. On the other extreme, even for few numerical features and many sensitive attributes, if the values in sensitive attributes are evenly distributed among the numerical feature clusters, the problem is solved effortlessly. Still, we would expect that fewer sensitive attributes, more numerical features, as well as a large size of the data set, might be favorable to fair density-based clustering. In sum, we consider it a highly data-dependent question, which could be interesting for case-based studies in fairness applications.

Dear Reviewer,

We sincerely appreciate your feedback and time, thank you! We highlight changes in the revised pdf version in blue color.

• Q1: We changed Figure 1 to be more clear and added a legend which shows that the clusters are given by the colors and the sensitive attributes are given by the shapes of the objects. Thus, continuous areas of the same color represent ‘good’, density-based clusters. We furthermore include a short description of DCSI and balance in the caption.

• Q2: Both ARI and NMI evaluate the clustering result regarding the ground truth labels. However, since we aim at finding group-level fair density-based clusterings rather than clusterings reflecting the possibly unfair ground truth labels, the external evaluation metrics do not offer much insight into quality of fair clustering. We included them merely to provide some background information about the contrast between ground-truth labels, and also density-based clustering (DBSCAN), and fair clustering alternatives.

• Q3: Thank you for this question, this is an interesting idea and a promising direction for future work. Some constraints like individual-level fairness could most probably be included, however, there would be a trade-off between the different fairness notions (and also, the clustering quality) if their optimal solutions are not equal. In the extreme case, the combination of constraints may not admit a solution. Indeed, the feasibility largely depends on the data distribution, in particular in regards to the sensitive attribute value combinations, and would require a case-based analysis for a given dataset.

• Q4 + W1: We conducted some runtime experiments which we added to the appendix of the revision (Appendix A.3). FairDen had comparable runtimes to the normalized spectral-based competitor. Scalable Fair Clustering and Fair SC are faster. In contrast, the Fairlet-based approaches had significantly higher runtimes.

• W2: Generally, the ability to detect noise is a favorable property of clustering algorithms, as it avoids degenerate clusters affected by noise - in fact, it is arguably one of the reasons for the popularity of DBSCAN. In our case, noise indicates individuals that should be investigated manually since they might differ from the population considerably. Note that including noise points as singleton clusters in the computation of the balance would cause the full clustering to have a balance score of 0, which is why we included them only indirectly for the respective experiments as described in Sections 3.1 and 3.2. Detecting noise points in a fairness setting improves the handling of intersectional fairness, especially for very small minorities, as it points to special cases, that may benefit from including the user in the loop.