- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies fair clustering under the k-median objective, following the fairness notion suggested in [CKLV17] (balanced representation of classes in the clusters). The authors propose a framework that converts any polynomial-time fairlet decomposition into an almost-linear time algorithm with a constant-factor loss in approximation, for points in low-dimensional Euclidean spaces (Theorem 1.1). This framework uses nested grids, where the points of each cell are represented by the centers of their sub-cells. The fairlets spanning sub-cells are finalized immediately on real points, and the rest are pushed down and handled recursively. Using this with a weighted version of [CKLV17]'s flow-based algorithm gives a constant-factor fair k-median static algorithm in almost-linear time (Corollary 1.3). Then, they extend it to the dynamic setting, and they obtain a fair k-median dynamic algorithm with sublinear update time (Corollary 1.3). Experiments show ~10x speedup over static baselines recomputed after each update, at comparable cost.
Critical strengths
-
The paper's originality lies in being the first attempt to tackle the fair-median problem under the dynamic setting.
-
Some technical contributions of the paper are strong. The central technical idea behind the dynamic result (one-sided monotonicity idea), introducing a small metric perturbation so that a single update deletes only fairlets when propagating downward, is an elegant and non-obvious idea. So is the acceleration framework that proves collapsing points to sub-cell centers incurs only a constant-factor approximation loss per level.
Critical weaknesses
- The high-dimensional limitation is not properly discussed. Theorems 3.1 and 4.1 state that the running time is and the approximation is . However, these two bounds are coupled through . For the running time to be almost-linear, needs to be small, i.e. , which makes the approximation , i.e. exponential in . Similar for the dynamic result (Theorem 4.1). This is something that needs to be clearly stated in the paper.
- Moreover, Theorems 1.1, 1.2 and Corollary 1.3 are stated only for , without a pointer to the general versions.
- I understand that for the specific application (tabular) and the datasets used, constant is a fully justifiable assumption. However, if is dependent on or just very large (e.g. in graph clustering), then it falls out of paper's reach - something that can be handled by the Backurs et al. baseline.
Questions for authors
- A proper conclusion section is missing, and there is no place where the limitations of the work are discussed, especially the restriction to constant (as discussed in the weaknesses). I suggest adding a short conclusion that also clearly mentiones the limiations of the work. Space could be freed by making Figure 1 more compact.
2 comments
I would like to thank the authors for their response. The restriction to constant dimension is ineed reasonable given that no dynamic algorithm was previously known even in this setting, and I appreciate the planned pointers to the general theorems and the new conclusion discussing limitations. However, I think that the trade-off between and should be explicitly stated next to the main theorems or in the introduction - not only in the conclusion. I will keep my positive score.
Response to Comments
We thank the reviewer for insightful comments.
Our main focus is on low (constant) dimensional spaces. Even in this restricted setting, no dynamic algorithm was previously known in the literature. As for the static setting, our aim was designing a fast, almost-linear constant-approximate algorithm. For this reason, we chose to present the main result in two dimensions for clarity, while providing the generalization to arbitrary dimension d in the technical sections for completeness.
Designing static and dynamic algorithms for high-dimensional spaces was not the goal of this paper, but we believe it is a natural and interesting direction for future research.
We will add the corresponding pointers to the general versions of the theorems.
We thank the reviewer for this suggestion. We will add a Conclusion section discussing the limitations of our approach, in particular the algorithms' exponential dependence on d, and outlining possible directions for future research in this area.