Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces a new algorithm for fair k-clustering problem(specifically when cost is measure with l_p norm for different p values) based on LP rounding. It provides a bi-criteria approximation guarantee for the clustering objective and experiments are provided to validate the theoretical properties. It is also shown how the runtime of the algorithm can be improved using sparsification with minimal effects on the objective.
main_review: # Originality

Although LP formulations have been studied for various clustering settings under different constraints, this paper introduces a nice formulation that handles fairness constraints and I believe that the rounding procedure and the analysis contain a decent amount of original work. 

# Quality

The quality of the writing and the presentation are good. This result has been placed among the relevant prior work well. The experiment complements the theoretical guarantees provided.

# Clarity

The clarity of the paper for the most part is good. However, I believe the following places need more clarification.
- In the experiments, when looking at the violations, what is considered the ground truth clustering? Do the datasets have cluster labels and if so do they adhere to the k-means(or k-median) optimal clustering? or output from some standard algorithm(eg: k-mean++) is considered the ground truth?
- It is not clear why Fact 4. in line 186 hold. Don't the updates in Algorithm 2, line 13 or line 19 affect that condition on y?

# SIgnificance

Fair k-clustering is an important problem for the NeurIPS community in my opinion and the improvements on the running time and the approximation guarantees simultaneously for the clustering objective and fairness (where prior works are lacking) carries a substantial significance.

Overall, I believe this paper adds decent contributions.

limitations_and_societal_impact: Some limitations are discussed regarding the theoretical analysis of violation vectors.
It may be worthwhile comparing this work with other notions of fair clustering, for example when the objective is maintaining similar cost for every cluster (see "Fair Clustering via Equitable Group Representations" by Abbassi, Bhaskara, and Venkatasubramanian).
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the problem of \ell_p norm and center-based clustering with a
fairness consistent. The fairness constraint roughly says that no point should
be further from its assigned center than it is from its (n/k)-th furthest
neighbor. The authors consider a Linear Programming based (approximation)
algorithm for this problem.

main_review: Center based clustering is widely studied problem where the basic problem of
clustering, i.e. partitioning data is framed as a combinatorial optimization
problem of picking k centers such that some combination of the distance of the
points from their nearest center (typically the sum -- though can be max in the
case of k-center) is minimized. These problems are well-studied -- most of them
are NP-hard, and in several cases approximation algorithms to some factors are
known. There are also hardness of approximation results known for several
settings -- though some gaps in our understanding remain. Since the main
purpose of the paper is not to discuss these problems per se, this should
suffice for the purpose of this review.

The goal in this paper is to have an additional "fairness" constraint -- where
for each point v in the dataset, there is a quantity r(v) and the requirement
(hard constraint) is that the center assigned to v should not be at a distance
of more than r(v) from this point. Of course, in some cases this may be
impossible and relaxations can be considered. There is also the standard k-*
objective, where * can be median, mean, center etc. Let me call these
objectives A (radius r(v)) and B cost of the k-* value. Then an (\alpha, \beta)
bi-criteria approximation algorithm guarantees that the distance of v from its
assigned center is no more than \alpha r(v) and also that the overall cost of
the objective B for the k-* value is no more than \beta OPT. 

The authors design LP-based algorithms that can achieve "better" bi-criteria optimization algorithms that were available in prior work. 

The main shortcoming I see in this work is that this particular criterion has been proposed very recently, as recent as 2020, and in particular the authors don't explain very well why this is an interesting objective to consider. In fairness, the authors do say that their focus is on the "algorithmic" rather than the fairness part of the work, but it is not clear to me that this is necessarily an interesting algorithmic problem to solve if the fairness objective is not well-motivated enough, and the authors do little to motivate it. Furthermore, the actual algorithmic techniques are not particularly novel or impressive, though it does improve on the current state of affairs. Thus, I am relatively lukewarm about this paper.

limitations_and_societal_impact: See above for limitations. 

Regarding societal impact, while I think there is inadequate discussion about it in the paper, I don't hold this against the authors. It's not clear what is to be expected from a paper like this.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This submission proposes an approximation algorithm for individual fair k-clustering in a metric space. Here, individual fairness means that each point v has an individual radius $r(v)$ and we require an open facility within radius $r(v)$ of $v$. We may use the radius $r(v)$ to provide each point $v$ with a "fair share" of its assigned facility by, for instance, choosing $r(v)$ as the smallest radius such that $n/k$ points lie within radius $r(v)$ of $v$; as originally proposed by Jung, Kannan, and Lutz. 

The approximation algorithm is the main contribution of the submission. It works for any p-norm objective and is bi-criterial, guaranteeing an $2^{1+2/p}$-approximation of the  objective while ensuring an open facility within radius $8r(v)$ of each point $v$. However, it requires a metric space which means, in particular, that all facilities/centers have to be chosen from the point set.

The algorithm roughly works in the following way: First, the authors compute an optimum solution to a linear programming relaxation of the problem. The solution is turned into an input for a filter function by Plesnik/Rita, Moro and Cortez; this function replaces the original point set by a smaller set of representatives. In the original version of the filter, the function may be run until only $k$ representatives remain (a point may represent another if it can serve as the point's facility; hence, in the original filter, the representatives are then chosen as the facilities to open). In this case, however, it may be that the filter stops early as the fairness restriction on the connection radius may make it impossible to cover all points with $k$ representatives. Hence, a final step is required to reduce the set of representatives down to $k$ points. This is done via an LP-rounding algorithm and turns out to be a substantial amount of work. Finally, in order to improve the running time of the algorithm, the authors propose a sparsification technique for the LP-relaxation (whose size is otherwise quadratic in the number of points and could be prohibitive for larger point sets).

An empirical part shows improvements over the previous approach.
main_review: The paper is exceptionally well written and I found it good to follow even through the substantial technical parts. The authors state that their work is mostly a combination of existing ideas. I feel this is a rather modest description and found the work to be quite non-incremental. I particularly like how the existing approach is extended to the individual fairness model in a non-trivial way. The experimental part is extensive; certainly larger than I would have expected for a paper with a sizeable theoretical contribution. The sparsification shows that clearly practicability was a priority for the authors.

As the weaker sides of the submission, I only see the assumption that all facilities must be chosen from the input points; the  approximation results for k-means (l2-objective, in language of the paper) from the literature generally assume a Euclidean space and permit the use of non-input points as facilities. The cited reference [1] considers Euclidean k-median. The assumption may be removed, but only at the loss of a factor of 2 in the approximation guarantee. 

This is not so much of a limitation, but the distinction could be more explicit in the paper. In particular, having a decent LP-rounding and sparsification for Euclidean k-means without having to invest a factor of 2 would be a big result.
limitations_and_societal_impact: See above; it would like the submission to be more explicit about having to choose the centers/facilities from the input points.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors of this paper consider the individual fair k-clustering problem, as introduced by Jung et al. [FORC 19]. In this model, for every point $j$ there is a given radius $r_j$, and the goal is to choose a set of centers such that each point has an open center within distance $r_j$ from it, and also one of the standard clustering objective functions is minimized.

Specifically, under the k-median and k-means objectives, the authors provide improved guarantees compared to the state of the art results (Mahabadi and Vakilian [ICML 2020]). For the k-median objective, they give an $(8,8)$-bicriteria algorithm, while the best known result was an $(84,7)$ one. For k-means their result is an $(4,8)$-bicriteria algorithm, while the result of Mahabadi and Vakilian was a $(\gamma,7)$ one, with $\gamma$ being a very large constant. (an $(a,b)$-bicriteria solution has objective cost at most $a$ times the optimal, and for every $j$ it has an open center within distance at most $b \cdot r_j$ from it).

The authors achieve their results via standard LP-rounding techniques.
main_review: A COMMENT ON A PREVIOUSLY OVERLOOKED TRIVIAL SOLUTION:

Before I proceed with my actual review, I would like to make an observation regarding this particular fair clustering problem.

I remember after reading the Mahabadi and Vakillian paper, it was obvious to me that their local-search approach (although technically sound and very impressive) was unnecessarily complicated and far from efficient (in terms of the approximations achieved). Specifically, there is a trivial LP-based approach that can immediately give refined results. Focus on k-median for instance, and consider the standard LP for it with the additional constraint that $D_j = \sum_{i}x_{i,j} \cdot d(i,j) \leq r_j$, where $D_j$ is basically the fractional assignment of point $j$. Then any deterministic LP rounding approach that satisfies $\sum_{i}\hat{x}_{i,j} \cdot d(i,j) \leq \rho D_j$, would immediately yield results for the fair problem as well (here $\hat{x}$ is the integral assignment after the rounding). For instance, the rounding from "A Dependent LP-rounding Approach for the k-Median Problem" by Charikar and Li would give $\rho = 9$ and subsequently an $(9,9)$-bicriteria algorithm (I'm actually referring to the bundling process they use to solve matroid-median). In case I'm missing something (though I have discussed this with a couple fellow researchers), it's surprising how such a trivial solution was overlooked by Mahabadi and Vakillian.

CLARITY OF THE PAPER:

The paper is very easy to follow and the authors have done a great job with regards to writing. I really enjoyed reading this work.

CORRECTNESS:

I went though all the arguments as carefully as I could, and I believe that all the theoretical claims are sound.

SIGNIFICANCE - ORIGINALITY:

The main contribution of this work is improved results compared to the Mahabadi and Vakillian paper. However, I think that a more accurate comparison is with the trivial solution I mentioned earlier. Compared to that, the authors employ their own rounding approach, instead of just using another one as a black-box. This gives indeed an improvement, but under this comparison the refinement is not that substantial. Moreover, I don't think that the details of their technique are very novel, since similar rounding ideas have appeared before. 

Overall, we have a problem that has a trivial solution which was overlooked by the previous "state-of-the-art" results. Compared to the trivial solution, the authors indeed provide refined results, yet 1) the improvement is not that substantial and 2) the techniques used are not really original. Nonetheless, it would be beneficial (to the research community) if the results of this paper are published, since they show a much more accurate algorithmic understanding of the problem (compared to the Mahabadi and Vakillian paper). My concern is that they might not be novel enough technique-wise to meet the high NeurIPS threshold.

MINOR COMMENT REGARDING THE EXPERIMENTS:

To test the scalability of the sparsification process it would have been better to run for a larger sample of points (1000 points seem already too few).

MOTIVATION:

When this model was first introduced I was skeptical about it, in the sense of believing that it doesn't actually capture any notion of fairness. It felt more like a robust version of k-median/k-means, where you want to give an additional covering guarantee to each client. From my perspective, Jung et al. did not do a good job justifying the fairness aspect of the problem (same thing with Mahabadi and Vakillian, although this was justified in the sense of them studying an already established model). 

My issue stems from the fact that this notion of individual fairness diverges from the definition given by Dwork et al. in their seminal work "Fairness through Awareness" [ITCS 2012] (a solution is individually fair iff it treats similar points similarly).

I understand that the authors did not have to justify the model from a fairness perspective, since it is an already established one, and hence I reviewed their paper based only on its own merit without letting doubts of the model affect my judgement. However, because previous work lacks a convincing discussion on why this particular constraint captures fairness, it would be beneficial to the community if someone does this. Therefore, I recommend that the authors add a detailed discussion about this in their paper.


limitations_and_societal_impact: Yes
review_title: null

Meta-review: The authors consider the problem of \ell-p objective (e.g. k-median, k-means) centre based clustering with fairness constraints. The notion of fairness is that no point v should be at a distance of more than r(v) from its respective centre (where there are some conditions on r(v) to ensure feasibility). This notion of fairness was introduced in prior work and the authors main contribution is algorithmic. The algorithmic techniques while standard do improve on the (very recent) state of the art; thus the paper could be of interest to the NeurIPS community. There was a lot of discussion about the notion of fairness as well. It is suggested that the authors critique the notion (from all angles) more effectively, given how new this notion is, in order for the paper to have the most influence.
Decision: Accept (Poster)