Doubly Constrained Fair Clustering

Summary

The paper investigates the fair $k$-center problem and considers the combination of two fairness notions: Group Fairness (GF) and Diversity in Center Selection (DS). The authors show that a constant approximation algorithm for one constraint (GF or DS only) can be extended to a constant approximation algorithm for both constraints simultaneously. Moreover, the authors show that both GF and DS are incompatible with a collection of other distance-based fairness notions.

Strengths

- Due to the importance of fair clustering and multiple fairness notions, it is interesting to study the relationship between different fairness notions. - The theoretical results show a separation between DP notions (GF and DS), and distance-based notions, which look interesting to me.

Weaknesses

- The studied objective is fair $k$-center, which is less used in machine learning. The extension of the paper to fair $k$-median and fair $k$-means would be more interesting. - It lacks a discussion of the limitations and future works.

Questions

Could you say anything about fair $k$-median/means?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No, the authors should include a discussion on limitations and societal impact.

Summary

This paper studies how to combine several notions of fairness together in one clustering. Fairness is a popular notion in the context of clustering, however most of previous works had focused on a single notion of fairness at once. This paper studies two specific notions of fairness which are called group fair clustering (GF), and diverse center selection (DF). They give various algorithms that give a constant factor approximation to the k-center problem under the GF+DS constraints (i.e. the clustering has to satisfy both DS and GF constraints). They also study the relationship of these two notions of fairness to other notions that also appear in the literature. More precisely, they show the following. 1) From a GF fair solution which is a constant factor to the GF problem, one can obtain a constant factor approximation to the GF+DS objective (in polynomial time), assuming a slight violation of the GF constraints. 2) Similarly, from a DS fair solution which is a constant factor to the DS problem, one can obtain a constant factor approximation to the GF+DS objective (in polynomial time), assuming a slight violation of the GF constraints. 3) It is also shown that the DS and GF objectives are both incompatible with several other notions of fairness. 4) They validate their algorithms with experiments.

Strengths

I think this is a conceptually interesting paper. To the best of my knowledge, this is the first paper that combines different fairness criteria together.

Weaknesses

Althought the results are nice, the techniques do not seem very novel.

Questions

Line 2 in pseudocode page 6: the output is stated to satisfy the GF fairness constraint but in fact there is an additive violation. This happens in several other places where the reader first thinks that GF constraint are satisfied exactly without violation. I would encourage to rephrase a little bit. Typos/minor comments: Line 138: extra k in equation Line 211: guarantees

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

yes

Summary

The paper investigates the relationship and intersection between two constraints for fairness clustering: Group Fair, in which populations should be fairly represented in each cluster, and Diversity Selection, in which centers should be fairly selected. It is shown that a solution for one of the constraints can be post-processed into a solution for the other with a constant degradation in results, but also that both constraints are incompatible with other, distance-based fairness constraints introduced in the literature.

Strengths

The theoretical results are very interesting, in terms of showing how it is possible to achieve (with some degradation) both kinds of fairness in clustering but also, and perhaps even more interestingly, when showing how these constraints are incompatible with other fairness settings.

Weaknesses

Experimental results are somewhat weak, with a single dataset being analyzed in the main text and an additional one presented in the supplementary material. The running time of the post-processing method to adapt a DS-compliant solution into a GF+DS-compliant one is very high when compared to the running time of the DS algorithm, but this is only mentioned in the supplementary material as well.

Questions

- Do you believe the same results would be replicated for other datasets? - What would happen (in terms of guarantees, results, running times) if the constraints must be guaranteed for more than two groups? - Were you able to verify the claim in the supplementary material that the overhead in the DS to GF+DS algorithm is due to the necessity of solving an LP?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

I believe the running time issues should be discussed in the main body of the paper. If there is space for it, it would be interesting to also expand on the consequences of these constraints not being compatible with distance-based ones.

Summary

This paper considers two common notions of fairness in clustering: (I) Group Fairness (GF) and, (II) Diversity in Data Selection (DS). The authors show how to boost an approximate algorithm that satisfies only GF/DF to an approximate algorithm that satisfies them both (with constant violations and constant times cost enlargement). Experiments also support the main claims of the paper. GF and DF are two popular notions to capture group fairness, I am happy to see that actually they can mostly be satisfied simultaneously without paying much effort. I think the results are an interesting addition to the study of fair clustering.

Strengths

1. The first results link different notions of group fairness constraint in clustering. 2. Algorithms are easy to follow.

Weaknesses

1. The algorithms heavily depend on existing approximate algorithms for clustering with GF or DF. So the result should mostly be regarded as an enhancement of the existing algorithms. 2. The simultaneous guarantees may violate some group constraints. I am worried that in some cases this feature actually contradicts fairness.

Questions

1. What is your running time of algorithms in Theorem 4.1 and 4.2?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The algorithms may violate some groups' fairness constraints in the worst case. Will it be an issue in some cases?