The Fairness-Quality Tradeoff in Clustering

We thank the reviewer for the comments and positive feedback!

Individual fairness definitions: To first answer the question: we think our framework is best suited for notions of group fairness, where there is some additional information about the nodes aside from their features used in the clustering objective. For individual fairness definitions, the only information available are the features themselves, making individual fairness and clustering objectives correlated (improving individual fairness in a clustering also makes the clustering cost smaller). Under some such definitions, the problem can be thought of as a single-objective optimization problem (e.g. Jung et al 2019 [37], Ghadiri et al 2019 [29]). For such problems, there is no Pareto front. For recent adaptations of individual fairness under bi-criteria optimization problems (Mahabadi and Vakilian 2020 [46]), one can apply a repeated approximation algorithm under an upper bound on one of the objectives (similar to the repeated-FCBC algorithm we proposed). In doing so, one would obtain loose approximation guarantees (see for example the $(\beta,\gamma)$-approximation guarantee for individual fairness proved by Mahabadi and Vakilian 2020 [46]). Dynamic programming approaches would not directly apply, however, we think this would be an excellent avenue for future work.

Motivation for computing the Pareto front: Computing the Pareto front would be helpful for central decision makers who are balancing different objectives: for example, in facility location problems where a central agent decides on the location of facilities (e.g. buses, hospitals, etc) based on the location of individuals within a certain region. It is well-known that people of lower socio-economic status often travel longer distances [1] and have fewer health facilities in their region [2]. A decision maker has multiple objectives to balance: minimal travel time for the entire population and equal access to facilities for different populations. The Pareto front allows the decision maker to balance these objectives in the optimal way: how much improvement can a group of people gain by moving a facility slightly away from the solution given by a single objective (e.g. by performing k-means)?

Computing the Pareto front for facility location problems with multiple objectives has a long history motivated by such questions, with real-world case studies in the Singapore road network [3] and ambulance placement in Barbados [4]. Further applications are found in extensive surveys [5]. We would be happy to include a more comprehensive motivation including real-world applications in the final version of the paper.

[1] Preston, John, and Fiona Rajé. "Accessibility, mobility and transport-related social exclusion." Journal of transport geography 15, no. 3 (2007): 151-160.

[2] Felland, Laurie E., Johanna R. Lauer, and Peter J. Cunningham. "Suburban poverty and the health care safety net." Washington (DC): Center for Studying Health System Change, 2009.

[3] Huang, Bo, P. Fery, L. Xue, and Y. Wang. "Seeking the Pareto front for multiobjective spatial optimization problems." International Journal of Geographical Information Science 22, no. 5 (2008): 507-526.

[4] Harewood, S. I. (2002). Emergency ambulance deployment in Barbados: A multi-objective approach. Journal of Operations Research Society, 53, 185–192.

[5] Farahani, Reza Zanjirani, Maryam SteadieSeifi, and Nasrin Asgari. "Multiple criteria facility location problems: A survey." Applied mathematical modelling 34, no. 7 (2010): 1689-1709.

Runtime: We think exploring faster algorithms is an excellent direction for the future. In this first analysis of the Pareto front for clustering and fairness objectives, we uncover the following complexities:

• Some objectives are more difficult than others: fairness objectives that sum over clusters do not allow a good poly-time approximation (Thm 7.1 [26]), whereas sum/max of imbalances objectives allow poly-time computation of the Pareto front through a reduction to a matching problem (Thms 3.6 and A.5 in our work).
• Overall, our main theoretical contribution gives tight approximation bounds to the true Pareto front, needing only some general conditions on the objective functions. In other words, we are agnostic to the specific objective functions used.
• We explored faster heuristics by adapting approximation algorithms that optimize fairness under a bounded clustering cost to recover the entire Pareto front; while such algorithms are polynomial, the approximation bounds are worse than what we obtain by dynamic programming; in practice, such algorithms obtain a very loose approximation of the Pareto front. We consider this a contribution of our paper: we believe that this is the first work to start exploring the tradeoff between approximation guarantees and the runtime complexity for computing the Pareto front.

We thank the reviewer for the thoughtful questions and comments!

Theoretical results: We appreciate the reviewer’s suggestions and we also think that an excellent direction would be some negative/hardness results that can decisively address what approximations can and cannot be obtained in poly-time. Currently, such results are difficult to obtain for the clustering problem for the following reasons:

1. First bottleneck: much of the literature obtains theoretical approximation bounds by solving the assignment objective as a proxy for the clustering objective. In doing so, we obtain the $(2 + \alpha)$-approximation on the clustering cost. Subject to this method, we know of theoretical results stating the we cannot get a $(2+\alpha,1)$-approximation on the Pareto front for (clustering objective, fairness objective) in poly-time for a range of fairness objectives (Thm 7.1 [26] for fairness objectives that sum across the clusters).
2. Second bottleneck: the assignment problem is also computationally hard (Thm 5.1 in [26]). This result implies that even a polynomially-sized Pareto curve is hard to compute for the (assignment, fairness) objectives. Even approximating fairness objectives with an additive approximation of $O(n^{\delta})$, $\delta \in [0,1)$ is NP-hard (Thm 7.1 [26]), therefore, an approximation of $(1, O(n^{\delta}))$ for the (assignment, fairness) objectives is hard.

In other words, all the guarantees we get are based on not relaxing the cost approximation from $(2 + \alpha)$ to something looser. Allowing a relaxation on the cost approximation may lead to theoretical guarantees on the fairness approximation (e.g. obtaining a $(c + \alpha, 1)$-approximation for $c > 2$). We think this is an excellent direction for future work, but would require fundamentally different techniques for solving the clustering objective that do not necessarily use the assignment objective as a proxy. We believe this would make for an entire paper on its own, and as such, this is beyond the scope of our paper.

Potential approximations on the fairness objective: The repeated-FCBC algorithm does indeed involve an approximation on the fairness objective as well, $(2+\alpha, c + \eta)$. Its purpose is precisely to explore the tradeoff between approximations and runtime: what we gain in runtime (FCBC is polynomial), we lose in approximation guarantees. The additive approximation eta on the fairness objective provided by FCBC has no known theoretical bound. We describe this issue further down in this response. In particular, no objectives that sum a measure of unfairness across the clusters allow a poly-time approximation of the form $O(n^{\delta})$ (Thm 7.1 [26]). Other objectives, such as sum and max of imbalances, allow even a polynomial time algorithm for computing the entire Pareto front (Thms 3.6 and A.5, our work). Such differences in the complexity of different objectives makes it difficult to have a general result that encompasses all objectives. Instead, our dynamic programming technique provides sufficient conditions on the objectives to get a good approximation guarantee of the Pareto front.

For this paper, we believe that this is the first work to start exploring the tradeoff between approximation guarantees and the runtime complexity for computing the Pareto front. We think the reviewer’s suggestion of further exploring this tradeoff is an excellent avenue for future work.

For the more minor points:

Sum of Imbalances: indeed, this objective ignores proportionality. Its purpose is to demonstrate that the complexity in computing the Pareto front comes exactly from requiring proportionality in the fairness objective. The reason for this difficulty can be explained by a reduction of fair assignment from the exact 3-cover problem [26], which shows that it is NP-hard to find an assignment of minimum cost where all clusters have red and blue points in proportion to the dataset ratio of 1:3. In contrast, simpler objectives that only compute the difference between the number of nodes in each sensitive group across clusters allow poly-time algorithms.

FCBC algorithm: described in lines 312-317, 326-328, FCBC is a polynomial-time algorithm for computing a clustering that has a cost bounded by $(2 + \alpha)U$, for an upper bound on the cost $U$ that is fixed a priori, and a fairness additive approximation, using an LP-type method, indeed proposed by [26] as the reviewer noted. This algorithm computes a single point on the approximated Pareto front. We will include a detailed description of the FCBC algorithm in the final version of the paper.

Implications for Esmaeili et al [26]: A contribution of our paper is to adapt FCBC for computing the entire Pareto front by allowing the cost upper bound $U$ to vary: in doing so, we explore the runtime-approximation tradeoff. Although FCBC has a polynomial runtime, in practice, the approximations are far from the true Pareto front. Figure 2 has the following implications: we can gain in runtime by adapting the FCBC algorithm to compute an approximated Pareto front; however, the approximation is quite loose in practice, with no guarantees on the fairness additive approximation factor. The additive approximation factor depends on a particular quantity, $L(U)$, which is the size of the smallest cluster across all clusterings of cost not exceeding $U$. This quantity has no theoretical guarantees and is computationally very expensive to compute in practice (it means iterating over all possible clusterings). In our experiments, repeated-FCBC leads to a very different approximated Pareto front than the one computed by our dynamic programming approach (Figs 2 and 7 from our paper). We consider this insight a contribution of our paper: we adapted FCBC to compute the Pareto front, and we compare it in practice with the Pareto front obtained by dynamic programming.

We thank the reviewer for the questions and positive feedback!

Definitions of fairness: The notions of fairness we discuss cover a range of fairness definitions used in a significant part of the literature, focused on group fairness notions. We would be glad to include a discussion on additional definitions in the final version of our paper. For some definitions, the notion of a Pareto front does not apply: for example, the socially fair k-means clustering notion proposed by Ghadiri et al 2021 [29] defines a single optimization objective that already incorporates fairness (by minimizing the max distance between points in each group and their cluster centers). With this definition, the fairness objective and the clustering objective are not separated in a multi-objective optimization problem, but rather combined in a single objective. Therefore, there is no Pareto front, since this notion applies to a multi-objective optimization problem. For Ghadiri et al, the problem is about how close an algorithm can approximate the optimal solution. For other definitions of individual fairness, such as recent adaptations of individual fairness under bi-criteria optimization problems (Mahabadi and Vakilian 2020 [46]), one can apply a repeated approximation algorithm under an upper bound on one of the objectives (similar to the repeated-FCBC algorithm we proposed). In doing so, one would obtain loose approximation guarantees (see for example the $(\beta, \gamma)$-approximation guarantee for individual fairness proved by Mahabadi and Vakilian 2020 [46]). Dynamic programming approaches would not directly apply, however, we think this would be an excellent avenue for future work.

Sum/max of imbalances: The sum of imbalances and max of imbalances objectives are indeed not previously defined in the literature: we introduce them as simple examples of objectives for which the Pareto front can be computed in polynomial time using a novel approach that adapts a graph matching argument to our clustering setting. We denoted them as natural due to their simplicity and we use them to exemplify that not all fairness objectives render the Pareto front problem difficult. We are happy to clarify this point in the final version of the paper.

US Census datasets: We appreciate the reviewer’s suggestion of using newer versions of the Census data — we would be glad to include an empirical analysis on the data obtained from the folktables package in the final version of the paper.

We thank the reviewer for the comments and question!

Question about FCBC: we’re not sure why a lower bound on the clustering cost would be desirable, since the clustering cost objective is a minimization objective (hence, lower cost is better). To modify FCBC with a lower bound on the cost guarantee, one can turn the cost minimization objective into a cost maximization objective by switching the sign of the objective and solving k-means clustering by gradient ascent methods; with the inverted objective, FCBC should follow a similar analysis. We note that the focus of our paper is not the FCBC algorithm per se, rather, we adapt it to explore the approximated Pareto front that it can obtain.

Runtime: while previous work provides approximation algorithms for optimization clustering under a fairness constraint, none offers a method for computing the Pareto front. We show in Section 4.2 that we can adapt such polynomial-time methods to compute an approximation of the Pareto front; however, what we gain in runtime, we lose in approximation bounds: the repeated FCBC algorithm has an additive approximation on the fairness objective that can get large in practice (we get a different Pareto front, with points quite far away in the objective cost, compared to the dynamic programming approach), and with no theoretical bounds on the additive approximation.

Our main theoretical contribution gives tight approximation bounds to the true Pareto front, needing only some general conditions on the objective functions. In other words, we are agnostic to the specific objective functions used. Furthermore, for some fairness objectives, prior work has shown that there is no polynomial-time algorithm that can offer a $O(n^{\delta})$-approximation: Thm 7.1 [26] for fairness across clusters objectives.

While prior work provides approximation algorithms for clustering objectives with fairness constraints, these methods do not all readily extend to computing the Pareto front. A contribution of our paper is to adapt one such method for computing the entire Pareto front: we adapted the FCBC algorithm [26] that optimizes fairness under a bounded clustering cost by varying the bound on the clustering cost. In doing so, we explore the runtime-approximation tradeoff. We consider this a contribution of our paper: we adapted FCBC to compute the Pareto front, and we compare it in practice with the Pareto front obtained by dynamic programming. Although FCBC has a polynomial runtime, in practice, the approximations are far from the true Pareto front.

Sum/max of imbalances: We agree with the reviewer that the sum of imbalances and max imbalances objectives are quite restrictive; in fact, we only give them as examples of objectives for which there are poly-time algorithms for computing the Pareto front. These objectives exemplify where the difficulty of computing the Pareto front arises from: fairness objectives that require clusters to match the group proportions present in the general population are difficult to optimize for even with approximation algorithms (Esmaeili et al [26] and our work). The reason for this difficulty can be explained by a reduction of our problem from the exact 3-cover problem, detailed by Esmaili et al [26] which shows that it is NP-hard to find an assignment of minimum cost where all clusters have red and blue points which match a dataset ratio of 1:3. In contrast, simpler objectives that only compute the difference between the number of nodes in each sensitive group across clusters allow poly time algorithms. We would be glad to clarify this point in the final version of the paper.

Minor comments: we thank the reviewer for noticing these minor issues, we will fix them in the final version of the paper.