Fair Polylog-Approximate Low-Cost Hierarchical Clustering

Summary

This paper studies the clustering problem in a fair setting. It proposes an approximation algorithm that achieves polylogarithmic factors for fair and cost while also keep relative balance. This work has greatly improved the result of Knittel et al. [2023] that has an approximation factor of $O(n^\delta\text{polylog}(n))$. The simulation results on two datasets verifies the effectiveness of their algorithm (replacing the binary clustering algorithm that theoretically achieves a factor of $O(\sqrt{\log n})$ with average-linkage).

Strengths

(1) A theoretical result of an approximation algorithm for the fair clustering problem, with great improvement in approximation factor. (2) Simple and intuitive tree operations in clustering adjustment that can be theoretically analysed.

Weaknesses

(1) This work seems to heavily depend on Knittel et al. [2023], although the authors are probably overlapping heavily. (2) Scalability of $h$, $k$ and $\lambda$ is doubtful. According to Theorem 1, $h$ should be much larger than $k^\lambda$, but in the experiments, $h=4$, $k=\lambda=2$ such that $h=k^\lambda$, which seems to be a violation of the settings. (3) There are some unclear points (refer to the questions).

Questions

(1) What is the role of $\gamma$ in Theorem 1? Do you mean an approximation algorithm for the cost of the input binary clustering tree (as described in Lemma 8) rather than the optimal cost of the original problem? So, for the latter, $\gamma$ needs to be multiplied outside the approximation factor, right? (2) How do you define the cluster balance? What does $c$ mean in the simulation settings? (3) Line 171, Def. 6, do you mean root$(T_f)$, rather than root$(T)$? (4) Line 236, do you mean "at most $h$" rather than "at least $h$"? (5) A typo: Line 281, "poitns" should be "points". (6) A ref error: Line 581. (7) Please delete Line 532 that has revealed author information!

Rating

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

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes, the authors have addressed the limitations in a specific section (Appendix A).

Summary

The paper addresses the problem of fair hierarchical clustering. Given a hierarchical clustering with a certain cost (determined by Dasgupta's cost function), the paper shows how the hierarchy (tree) can be efficiently modified so that fairness constraints are satisfied and the cost of the tree increases (provably) by only by a small factor. The theoretical results are validated through experiments on two data sets.

Strengths

(a) The paper provides the first (provable) polylog approximation for the cost of hierarchical clustering while satisfying fairness requirements. This is an important advance in fair hierarchical clustering. (b) The algorithm simplifies a previously known algorithm while achieving the approximation bound. (c) The paper is written very well.

Weaknesses

A (very) minor weakness is that the statements of theorems require a good amount of effort to understand since they involve many different parameters.

Questions

(1) On lines 124--126 (page 4), it is mentioned that the approximation factor is with respect to an optimal vanilla hierarchy (which doesn't consider fairness). Did the previous work also use this assumption? (2) Are any hardness of approximation results known for the problem? (It will be interesting to see how close the polylog approximation is compared to what can't be achieved in polynomial time under a standard assumption such as P != NP.) (3) The statements of theorems/lemmas etc. involve many parameters. This reviewer agrees that this is unavoidable for making the theorems precise. Would it be possible to include informal statements of results that are easier to understand (even if they are not mathematically accurate)? Some minor typos: (a) Line 62 (page 2): "as a in" ---> "as an" (a) Line 121 (page 4): "increasing cost" ---> "increasing the cost"

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

None

Summary

The paper considers finding a hierarchical clustering of (approximately) minimum Dasgupta cost under fairness and balance constraints. It appears that for any constant fairness range (i.e. the quantities a_i and b_i) they have a quasi-linear time algorithm which has a polylogarithmic approximation ratio. In fact - their algorithm takes any (unfair) hierarchical clustering and converts it into a fair one.

Strengths

The best previous polynomial-time algorithm for approximately minimising the Dasgupta cost under fairness constriants had a polynomial approximation ratio (with exponent dependent on the fairness range). I think that going from a polynomial to polylogarithmic approximation ratio is a big step. The authors have conducted experiments on their algorithm - showing empirically that the cost of the fair clustering produced is not much greater than the cost of the original (unfair) clustering. However, there are no experiments comparing to other algorithms.

Weaknesses

The algorithm is tailored to the Dasgupta cost which is only one measure of goodness of a hierarchical clustering and in itself can be seen as a heuristic. However - I believe this cost to be very famous so the result is significant. The way the bound is written at the moment is completely impenetrable - please see the “Questions” section for advice on this. There are issues with the writing of the paper which I shall now list (I include here any typos etc.): - The Introduction section uses a lot of notation that is not defined until later in the paper. This should definitely be fixed. - The authors state that the cost is hypothesised not to be O(1) approximatable. What they mean is not O(1) approximatable by a polynomial-time algorithm. - Definition 6 is ambiguous and hence is not a proper definition. - In line 60 I believe the authors mean “fairness literature” - In line 84 \gamma must surely appear in the approximation ratio - Line 103 should start with “which is” instead of “is” - In line 103 “tree” should be replaced by “graph” - The use of “i.e.” in line 123 is wrong. - Line 161 should say “inserts a new vertex p…” - In line 133 \ell(C) (which I assume is the number of elements of C of colour \ell) is not defined. This notation also overloads \ell - it is both a colour and a function (corresponding to the colour). I recommend something like N_{\ell}(C).

Questions

Suppose I give you a<1 and b>1 and I enforce you to create a fair hierarchical clustering with a_i=a and b_i=b for all colours i (where a_i and b_i are as in line 95). Can you write the parameters, the time complexity and the approximation ratio in terms of a and b? This is not just a question - doing this will vastly improve the presentation of the result since this is the logical way round (I give you the fairness constraints and you give me the (approximately) best hierarchical clustering satisfying those constraints).

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

2 fair

Contribution

2 fair

Limitations

Authors have addressed limitations

Summary

This paper considers fairness in hierarchical clustering and proposes an approximation algorithm that modifies a given unfair approximate vanilla hierarchy $T$, of which the cost is bounded by $\alpha$-factor of the optimal (OPT) hierarchy tree, i.e., $cost(T)\leq \alpha \cdot cost(OPT)$, to a polylogarithmic-approximate fair hierarchical clustering. This work is developed based on the ideas by Knittel et al. [2023] but simplifies some of the key operators, e.g., tree holding operator, and achieves the polylogarithmic approximation for cost for the first time.

Strengths

- Proposed an algorithm that modifies an unfair hierarchical clustering and yields a fair hierarchy with only a modest increase in cost. - Provided real dataset experiments showing that their proposed algorithm improves the fairness in clustering (i.e., balances the portion of nodes from different parties) with a modest cost ratio increase.

Weaknesses

- I think the presentation of this paper needs to be largely modified. First, this paper addresses some technical terminologies before there are defined, which makes it hard to understand what the statements mean before reading until the end of the paper. For example, in Introduction the last paragraph, “O(function(N)))-approximation”is used to compare previous methodologies. But, neither the definition of the cost in hierarchical clustering nor what this approximation means was provided. Theorem 1 in page 3 is an exact same copy of the same theorem in page 5. But just presenting the same theorem without even defining what approximation means and how $\alpha_i$ and $\beta_i$ are related to the quantification of fairness makes it very hard to understand the meaning of the paper in introduction. If the authors want to summarize the key contributions in introduction, they need to properly define the terminologies and important parameters to make it self-contained. - Another issue is related to the reference. The techniques in this paper is highly dependent on the previous techniques by Knittel et al [2023] and the authors refer the paper many times. Especially in Sec. 2.3 when tree operators are introduced, they refer the same operators introduced in Knittel. But it is hard to see what was the original way these operators were defined, what are the main changes this paper addresses, and why this change generates a better approximation. - In experiment Fig.4, the ratio of cost increase due to fair clustering is about 8x when n is about 10^3. Can we call this a modest cost increase? Intuitively, isn't it relatively easier to achieve the fairness for larger $n$ since there are many nodes and balancing those nodes without hurting the cost can be easier due to much more ways to modify the tree? Can the authors compare their result with other algorithms in terms of achievable fairness and cost increase? There is no baseline comparison in the experiment. Also, it is not clear whether the performance of the proposed algorithm is robust to the change of the original hierarchical clustering algorithm. In the experiment, only the average-linkage was considered as an initial algorithm.

Questions

- Can the authors provide experiments to compare their performance with other baselines? - Can the authors show that the performance of proposed algorithm is robust to the change of the originally given (unfair) hierarchical clustering?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed 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

2 fair

Presentation

1 poor

Contribution

2 fair

Limitations

Limitations are not well addressed by the authors.