Fair, Polylog-Approximate Low-Cost Hierarchical Clustering
Authors: Marina Knittel
Max Springer
John P Dickerson
MohammadTaghi Hajiaghayi
Venue: NeurIPS 2023 poster (2023)
Keywords: Fair machine learning
hierarchical clustering
clustering
TL;DR: We propose the first polylog-approximate fair hierarchical clustering algorithm optimizing for Dasgupta's cost function.

Abstract: Research in fair machine learning, and particularly clustering, has been crucial in recent years given the many ethical controversies that modern intelligent systems have posed. Ahmadian et al. [2020] established the study of fairness in hierarchical clustering, a stronger, more structured variant of its well-known flat counterpart, though their proposed algorithm that optimizes for Dasgupta's [2016] famous cost function was highly theoretical. Knittel et al. [2023] then proposed the first practical fair approximation for cost, however they were unable to break the polynomial-approximate barrier they posed as a hurdle of interest. We break this barrier, proposing the first truly polylogarithmic-approximate low-cost fair hierarchical clustering, thus greatly bridging the gap between the best fair and vanilla hierarchical clustering approximations.

Fair, Polylog-Approxmmate Low-Cost Hierarchical Clustering
Marina Knittel
Max Springer
John Dickerson MohammadTaghi Hajiaghayi
Department of Computer Science University of Maryland, College Park {mknittel, mss423)) edu {john, hojjnhajie haj iagha) @cs. umd. edu
Abstract
Research in fair machine learning, and particularly clustering, has been crucial in recent years given the many ethical controversies that modern intelligent systems have posed. Ahmadian et al. [2020] established the study of fairness in hierarchical clustering, a stronger, more structured variant of its well-known flat counterpart, though their proposed algorithm that optimizes for Dasgupta's [2016] famous cost function was highly theoretical. Knittel et al. [2023] then proposed the first practical fair approximation for cost, however they were unable to break the polynomial-approximatl barrier they posed as a hurdle of interest. We break this barrier, proposing the first truly syyllogarthmic-appooimme hierarchical clustering, thus greatly bridging the gap between the best fair and vanilla hierarchical clustering approximations.
low-cost fair
Introduction
Clustering is pervasive machine learning technique which has filled vital niche in every day computer systems. Extending upon this, a hierarchical clustering is a recursively defined clustering where each cluster is partitioned into clustering, giving an algorithm the ability to depict data similarity at different resolutions as well as ancestral relationship between data points, as in the phylogenetic tree Kraskov et al. 2003
clusters, and on. This adds structure to flat
On top of computational biology, hierarchical clustering has found various uses across computer imaging [Chen et al. 2021b, Selvan et al. 2005). computer security [Chen et al. 2020 2021a natural language processing Ramanath al. 2013] and much more. Moreover, it can be applied to any flat clustering problem where the number of desired clusters is not given. Specifically, hierarchical clustering can be viewed as a structure of clusterings at differrent resolutions that all agree with each other (i.c., two points clustered together in higher resolution clustering will also be together in lower resolution clustering). Generally, hierarchical clustering techniques are quite impactful on modern technology, and it is important guarantee they are both effective and unharmful.
Researchers have recognized the harmful biases unchecked machine learning programs pose. A few examples depicting racial discrimination include allocation of health care [Ledford 2019] presentation of ads suggestive arrest records [Sweeney] 2013), prediction hiring success Bogen and Rieke, 2018), , and estimation of recidivism risk (nngwin et al. 2016). A popular solution that has been extensively studied in the past decade is fair machine learning. Here, fairness concerns the mitigation of bias, particularly against protected classes. Most often, fairness is additional constraint on the allowed solution space; we optimize for problems in light of this constraint. For instance, the notion of individual fairness introduced by the foundational work of Dwork et al. [2012 deems that an output must guarantee that any two individuals who are similar are classified similarly.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

dloba Werning
Art DES
Glabal
Narm ag
D2
Famm
Figure I: A hierarchical clustering of news articles. Red articles are conservative, blue are liberal. On the left is the optimal unfair hierarchy. We alter the hierarchy slightly on the right to achieve fairness. Now, the user's query for global warming will yield both liberal and conservative articles.
In line with previous work in clustering and hierarchical clustering, this paper utilizes the notion of group fairness, which enforces that different protected classes receive a proportionally similar distribution of classifications (in our case, cluster placement), [Chirriceetti et al. [2017] first introduced this as a constraint for the flat clustering problem, arguing that it mitigates system 's disparate impact, or non non-propottional impact on different demographics. This notion of fair clustering has been similarly
leveraged and extended by vast range of works both flat [Ahmadian et al. 2019 Bera et al., 2019
Bercea et al. 2019] and hierarchical [Ahmadıan et al. 2020 Knittel et al.) 2023 clustering.
To illustrate fairness concept, consider the following application (Figure T news database is structured as a hierarchical clustering of search terms, where a search term is associated with a cluster of news articles output to the reader, and more specific search terms access finer-resolution clusters. When user searches for term, we simply identifyy the corresponding cluster and output the contained articles. However, as is, the system does not account for the political skew of articles. In Figure D we label conservative-leaning articles in red and liberal-leaning articles in blue. We can see that in this example, when the user searches for global warming articles, they will only see liberal articles. To resolve this, we add group fairness constraint on our cluster: for example, require at least 1/3 of the articles in each cluster to be of each political skew. This guarantees (as depicted on the right) that the outputted articles will always be at least 1/3 liberal and 1/3 conservative, thus guaranteeing the user is exposed to a range of perspectives along this political axis. This notion of fairness, which we formally define in Definition 3 has been explored in the context of hierarchical
clustering in both Ahhaddia et al. 2020 and Knittel et al. 2023
This paper is concerned with approximations for fair low-cost hierarchical clustering. Cost, first defined by Dasgupta [2016] and formally stated in Definition 2 is perhaps the most natural and optimization metric for hierarchical clustering evaluation. Effectively, every pair of points contributes an additive cost of similarity x clust size, where the latter the size of the smallest cluster in the hierarchy containing both points. Unfortunately, it is quite difficult to optimize for (the best being ((Vlog -1)-aproximmation (Charikar and Chatziafratis 2017 Dasgupta 2016); it hypothesized to not be O (aalaopproee (Charikar and Chatziafratis (017)). This appears to be even more difficult in the hierarchical clustering literature. The first work to attempt this problem, Ahmadian et al. 2220)]. achieved a highly impractical (n1 1/g n) appapooxximtaoon (not too far from the trivial O(n) upper bound). posing fair low-cost hierarchical clustering as an interesting and inherently difficult problem. Knittel et al. (2023) greatly improved this to a near-polylog approximation factor of Onn' (onpollo)g(n)) where can be arbitrarily close to 0, and parameterizes a trade-off between approximation factor and degree of fairnsss. Still, a true polylog approximation was left an open problem, one which solve in this paper.
1.1 Our Contributions
This work proposes the first polylogarithmic approximation for fair, low-cost hierarchical clustering. We leverage the work of Knittel et al. [2023] as a starting inspiration and create something much simpler, more direct, and better in both fairness and approximation. Like their algorithm, our algorithm starts with a low-cost unfair hierarchical clustering and then alters it with multiple well- defined and limited tree operators. This gives a degree of explainability, in that the user can understand exactly the steps the algorithm took to achieve its result and why. In addition, our

---

algorithm achieves both relative cluster balance (i.e., clusters who are children of the same cluster have similar size) and fairness, along with a parameterizeable trade-off between the two.
On top of the benefits of Knittel et al. [023] 's techniques, we propose a greatly simplified algorithm. They initially proposed algorithm that required four tree operators, however, only require two of the four, and we greatly simplify the more complicated operator. This makes the algorithm simpler to understand and more implementable. We show that even with this reduced functionality, we can cleverly achieve both a better approximation and degree of fairness:
Theorem 1 (High-Level), Given a n-approximation to the cost objective for a hierarchical clustering on set of n points, Algorithm 2 yields an O n) approximation to cost which relatively fair in time (n log" n). Moreover, all clusters are O log balanced, i.e., any cluster's 's children clusters within (1/ log n) size different.
To put this in perspective, previously, the best approximation for fair hierarchical clustering previously
was (n polylog(n)), whereas the best unfair approximation is O(ylog r2). Our work greatly reduces this gap by providing true (ppolylog(n)) approximation. moreover with a low degree of 2. Note that this not the most general and rigorous form of our result- that, we defer to Theorem !| as stated in the body of our paper. This simpler version is found by setting k = 0(1), h = Ollogn).
and O11 log in the more general theorem (note we assume À = O()).
2
Preliminaries
2.1 The Vanilla Problem
Fair clustering literature refers to the original problem variant, without fairness, as the "vanilla" problem. We define the vanilla problem of finding a low-cost hierarchical clustering here using our specific notation.
In this problem, we are given a complete graph G (V, E, w) with a weight function w E' R is a measure of the similarity between datapoints. Note the data is encoded as a complete tree because we require knowledge of all point-point relationships. We must construct hierarchical clustering, represented by its dendrogram, T, with root denoted root(T). T is tree with vertices corresponding all clusters of the hierarchical clustering. Leaves T, denoted (eaves(root(T) correspond the points in the dataset (i.e., singleton clusters). An internal node corresponds to the cluster containing all leaf-data of the maximal subtree (i.e., contains all its descendants) rooted at v, Tlu). In addition, we let u A v denote the lowest common ancestor of u and v in T.
In order define Dasgupta 2016 's cost function, we the same notational simplifications as Knittel et al. [2023]. For an edge = (I,y) E E, we say ne(e) = |leaves(T"[r A vl) is the size of the smallest cluster in the hierarchy containing e. Similarly, for hierarchy node v. (v,) = |leaves( (fx))] is the size of the corresponding cluster. This is sufficient to introduce the notion of cost.
Definition (Knittel et al. 2023 ). The cost of e E E in graph G (V, E, w) in hierarchy T is costr (e) w(e) 1T (e).
Dasgupta's 's cost function can then be written as a sum over the costs of all edges.
Definition (Dasgupta 2016)) ). The cost of a hierarchy T on graph G = (V, E, w) is:
cost(T) = Σ costr(e)
Our algorithm begins by assuming we have some approximate vanilla hierarchy, T. That is, if OPT is the optimal hierarchy tree, then cost(T) < a cOST(OPT) for some approximation factor a. According to Dasguupaa (016),, we can transform this hierarchy to be binary without increasing the cost. Our paper simply assumes our input is binary. We then produce a modified hierarchy T' which similar structure to T that guarantees fairness, i.e., cost(T") < a' (OP) for some approximation factor a' 2 a. Note this comparison is being made to the vanilla OPT, as we are unsure, at this time, how to classify the optimal fair hierarchy. Note that the binary assumption may not hold when consider adding faimess constraint.
3

---

2.2 Fairness and Balance Constraints
We consider the faimess constraints based off those introduced by Chierichetti et al. 2 and extended by [errea et al. [2019]. On graph G with colored vertices, let E(C') count the number of f-colored points in cluster C.
Definition 3 (Knittel et al. 2023 Consider a graph G (V, E, w) with vertices colored one of
colors, and two vectors of parameters a. 3 E (0, 1)^ with ae S Be for all E [}]. A hierarchy T on G is fair if for any non-singleton cluster C in and for every e E [A], oz|C| & E(C) S Cl Additionally, any cluster with leaf child has only leaf children.
Effectively. we are given bounds a and 3r for each color f. Every non-singleton cluster must have at least an og fraction and at most Be fraction of color E. This guarantees proportional representational fairness of each color in each cluster.
As intermediate step in achieving faimeess, we will create splits in our hierarchy that achieve relative balance in terms of subcluster size. Thus, the following definition will come in handy.
Definition 4. In a hierarchy, a vertex v (corresponding to cluster C) with e, children is e-relatively balanced if for every cluster {Ci)ie(s.) that corresponds child of v. (2) c)|CI S |C&| S +e)cc.
While this definition is quite similar to that from Knittel et al. 2023], it deviates in two ways: I)
only define it single split as opposed to the entire hierarchy and 2) we allow splits to be
non-binary. we apply it to the entire hierarchy and constrain it to be binary, it is equivalent to the former definition.
2.3 Tree Operators
9
Our work simplifies the work of Knittel et al. 2023 In doing so, we follow the same framework, using tree operators make well-defined and limited alterations to a given hierarchical clustering (Figure 2 In addition, our algorithm simplifies operator use in ways: 1) we only utilize two of their four tree operators, and 2) we greatly simplified their most complicated operator and show that it can still be used to create fair hierarchy.
First off, we utilize the same subtree deletion and insertion operator. The main difference is how we use it, which will be discussed
Figure 2: Our operators: sub- tree deletion and insertion and Section At a high level, this operator removes subtree from shallow tree folding.
part of the hierarchy and reinserts elsewhere, adding and removing parent vertices as necessary.
Definition 5 (Knittel et al. (202)). Consider a binary tree T with internal nodes u, some non- ancestor v, u sibling s. and e's parent g. Subtree deletion at removes T[u] from T and contracts s into its parent. Subtree insertion T(] at u inserts a new parent p between u and g and adds u as a second child of p. The operator del ins(u, v) deletes and inserts T(u] at
The other operator we leverage is their tree folding operator, however we greatly simplify it. In the previous work, tree folding took two or more isomorphic trees and mapped the internal nodes each other. Instead, we simply take two or more subtrees and merge their roots. The new root then directly splits into all children of the roots of all folded trees. In a way, this is an implementation of their folding operator but only at a single vertex in the tree topology. This is why we call it shallow tree fold.
Definition 6. Consider set of subtrees Ti...., Tr of T such that all root(T.) have the same parent in T. A shallow tree folding of trees Ti...., Tk (shallow follloowoold(T....... Tx)) modifies T such that all Tı,... ... Tv are replaced by a single tree Ty whose root root(T,) is made child of p. and whose root childchil are cheieeciidre
In addition, we assume the subtree Ty then arbitrarily binarized [Dasgupta 2016) after folding. Since our algorithm works top-bottom, creating balanced vertices as goes, we don't I care about the fairness of the descendants Ty. Moreover, we will then recursively call our algorithm on T to do preciscly this.

---

3 Main Algorithm
In this section, we present our fair, low-cost, hierarchical clustering algorithm along with its analysis. Ultimately, we achieve the following (for a more intuitive explanation, see Section T:
Theorem When T is a y-approximate low-cost vanilla hierarchical clustering over ((V) = con = O(n) vertices of each color E [사], MakeFair (Algorithm _ for any constants e, h, k with h >> A and n >> h, runs in (n log n( + À n)) time and yields hierarchy T" satisfying:
1. T" is an O
(ل-ا)) + +
aapppoxxmmation cost. cost.
2. T is fair for any parameters for all E [A]: as S A (1100 (1
k((tt) agh
O(loR(n))
and
B, 2 Ai Ite (1+ (1+1z)) O(log(n)) .where X c.n. (1-1)²
3. All internal nodes in T" are e-relatively balanced.
The main idea of our algorithm is to leverage similar tree operators to that Knittel et al. (2023) but greatly simplify their usage and apply them in more direct, careful manner. Specifically, the previous work processes the tree four times: once to achieve 1 1/6-relative balance everywhere, next to achieve e-relative balance, next to remove the bottom of the hierarchy, and finally to achieve fairness. The problem is that this causes proportional cost increases to grow in an exponential manner, particularly because the relative balance significantly degrades as you descend the hierarchy. Our solution is to instead do a single top to bottom pass of the tree, rebalancing and folding to achieve fairness as we go. We describe this detail now.
First, we assume our input is some given hierarchical clustering tree. Ideally, this will be a good approximation for the vanilla problem, but our results do work as black box on top of any hierarchical clustering algorithm. Second, we apply SpoitRoot in order to balance the root (Section 3. And finally, apply shallow tree folding on the children of the root to achieve fairness (Section This gives us the first layer of our output, and then we recurse.
3.1 Root Splitting and Balancing
SplitRoot is depicted in Algorithm I This fills the role of Knittel et al. [0233] 's Refine Rebalance Tree algorithm (and skips their Rebalance Tree algorithm), but it functions differently in that it only rebalances the root and it immediately splits the root into children, according to our input parameter h.
We start SplitRoot by adding dummy children to o until has h children (recall the input is binary). A dummy or null child is just a placeholder for a child to be constructed, or alternatively simply zero-sized tree (note: this does not add any leaves to the tree). None of these children will be left empty in the end. Next, we define Umaz and Umin, the maximal subtrees rooted children(root((")) which have the most and fewest leaves, respectively.
assume
As long as the root is not e-relatively balanced (which equivalent to (2 or ny (Umin) deviating from the target n/h by over ne, as they extreme points), we will attempt to rebalance. We define 6, and 52 to be the proportional deviation of (umin) and nop (Umaz) from the target size n/h respectively, and 8 to be the minimum of the two. In effect, 5 measures the maximum number of leaves we can move from the large subtree to the small subtree without causing Rer ( (Umax) to dip below n//h or TUT' (Umin) to peak above n/h. This is important to guarantee our runtime: as an accounting scheme, we show that clusters monotonically approach size n/ h, and thus we can quantify how fast our algorithm completes. We fully analyze this later, in Lemma 2
n/h,
Now we must attempt exactly this procedure: move a large subtree from Umaz to Umin though this subtree can have more than ōn leaves. To do this, simply start at Umar and traverse down its right children (recall below e Umans the tree is still binary). We halt on the first child that is of size ön or smaller. We then remove it and find place to reinsert it under Umin-
The insertion spot is found similarly by descending down Unin's left children until the right child of the current vertex has fewer leaves in its subtree than the tree we are inserting. Thus, we have
5

---

completed our insertion and deletion operations. We repeat until the tree is relatively balanced as desired.
Algorithm 1 SolitRoot
Input: A binary hierarchy tree T of size 2 1/2c over graph = (V, E, w), with smaller cluster
always on the left, and parameters E [n] and e E (0, min(1/6.11H))
Output: A hierarchical clustering T' with an e-relatively balanced root that has k children.
1: Initialize T
2: (T")
3: Add null children to until it has h children
4: Let Umin / Echildren(v)) TTT (v') pTr
5: Let Umar =
6: while NTT (Umas) > n1 (1/h-++ + c) or nor (Umin) < n(1/h - -c) do
7:
81 1/h 11T (Umin) )/n
8:
82 = nT (Umaa))))) n 1/h
9:
8 min(d1,62 82)
10:
Let V Umar
11:
12: while (v) > 8n do
13:
righty.(()) end while
14:
15:
16: u < Umin
while NTT (right:: 2 (o)(1)) do
18:
4 (eftr.(u)
end while
20:
T + T" (f.dee_inssu,.)
Reset Umaí and Umaw
22:
end while
We now analyze this part of the algorithm. The full proofs can be found in Appendix B. and we proceed to give the intuition here. To start, consider the tree we are deleting and reinserting, [v) Ideally, we want this to have many leaves, but no more than ōn. We demonstrate that:
Lemma 1. For subtree ['l that is deleted and reinserted in SplitRoot (Algorithmm we must have that en/ (2/(2(h - 1)) < nv) S ön.
The upper bound simply comes from our stopping condition in the first nested while loop: we ensure Wr (v) S ön before selecting it. The lower bound is slightly more complicated. Effectively, we start by noting that max(11, 52) > because otherwise the stopping condition for the outer loop would be met. Then, consider the total amount of "excess of large clusters", or more precisely, the sum over all deviations from n/h of clusters larger than n/h (note if all clusters were n/h, it would be perfectly balanced). This total excess must matched the "deficiency small clusters", which is the sum of deviations of clusters smaller than n n/h. Therefore, since there large clusters, the largest deviation must be at most ht times the smallest deviation, according to accounting scheme. This allows to bound 8 2 c/(h 1). The tree that is inserted and deleted must have at least half this many leaves, since it the larger child a node with over ôn leaves in its subtree. This gives lower bound, showing move at least significant number of vertices each step.
least h small or
Next, we aim to illustrate the relative balance. In addition our analysis, we also obtain the runtime, which exhibits near-linearity when the condition < n holds.
Lemma 2. SplitRoot (Algorithm 7 yields hierarchy whose root is e-relatively balanced with children. In addition, it requires Qnh) time to terminate.
The root has children by definition at the algorithm start and this remains invariant. The runtime comes from our aforementioned accounting scheme: the total excess and deficiency is reduced by the number of leaves in the subtree we move each step, which we showed in Lemma Iis ne/ ne/(2(h (2(h-1211)) 1)) at least. This gives us a convergence time of O(h), and each step can be bounded by (()) time as we search for our insertion and deletion spots. Finally, the balance comes from the fact that our stopping condition is equivalent to the root being relatively balanced.

---

All that remains is to show the negative impact on the cost of edges that are separated by the algorithm. We bound this via the following lemma.
Lemma 3. In SplitRoot (Algorithm
7. for all E E that are separated:
costr (e) S n w(ee) S 2(h 1) costr(e)/e
Lemma [ gives us that moved subtrees are at least of size en/ - 1)). which is a lower bound on the size of the smallest cluster containing any edge separated by the algorithm. This is due to the fact that separated edges must have one endpoint in the deleted subtree and one outside, so their least common ancestor is ancestor of the subtree. At worst, the final size of the smallest cluster containing such an edge is n, so the proportional increase is 2(h - 1)/c c at worst.
3.2 Fair Tree Folding
Next, we discuss how to achieve fairesss by using MakeFair, as seen in Algorithm 2 This is our final recursive algorithm which utilizes SplitRoot. Assume we are given some hierarchical clustering. We start by rumning SplitRoot, to balance the split at the root and give it h children. Next we use folding process similar to that of Knittel et al. [2023), but we use our shallow tree fold operator.
More specifically, we first sort the children of the root by the proportional representation of the first color (say, red). Then, we do a shallow fold across various k-sized sets, defined as follows: according to our ordering over the children, partition the vertices into k contiguous chunks starting from the first vertex. For each E [h/k], we find the i-th vertex in each chunk and fold them together. Notice that this is a wise fold since there are l chunks, and we end up with h/k vertices. This is repeated on each color. After this, we simply recurse on the children. If a child too small to be balanced by SplitRoot, then stop and give it trivial topology (a root with many leaf-children)..
This completes our algorithm description. We now evaluate its runtime, degree of fairness, and approximation factor. To start, we show the degree of fairness achieved at the top level of the hierarchy.
Lemma 4. MakeFair (Algorithm yields a hierarchy such that all depth I vertices satisfy fairness under a; < A 1-c
[1+2]² (1
A(I+c) and B (1-c)²
2
A ltc
(1 1-c
where X;- C.n.
c,k
This proof is quite in depth, and most details are deferred to Appendix showing that the folding process guarantees level of faimess. The parts in partition are ordered by the density of the color (say, red). Since each final vertex is made by folding across one vertex in each part, meaning that the vertices have relatively wide spread in terms of their density of red points. This means that red vertices are distributed relatively well across our final subtrees. This guarantees degree of balance.
B At a high level, we are
The problem is that the degree of fairness still exhibits a compounding affect as we recurse. More specifically, since the first children are not perfectly balanced, then in the next recursive step, the total data subset we are working on may now deviate from the true color proportions. This deviation is bounded by result in Lemma but it will increase proportionally at each step.
Lemma 5. In MakeFair (Algorithm D. let (Nibie()) be the proportion of each color and assume A << h. At any recursive call, the proportion of any color is (where X; 1/r constant cj): Ollog(n/h))
1 (1- --(0++)))
( 1+6 (1 1 1-)) (1 6]- 1 cxk ))
O(log(n/h))
X (1 e)2
< S
Moreover, the recursive depth is bounded above by Olog(n/hh).
This result derives directly from Lemma 4 Effectively, we increase the proportion of each color by the same factor each recursive step. All that is left to do is bound the recursive depth. Notice we start with n vertices. After splitting, our subtrees have size at most (1 + e)n/hh After one fold, this is increased by a factor of k, and thus 2 after all folds. Interestingly. this doesn't 't impact the final result significantly; it's fairly similar to turning an n-sized tree into an n n//l-sized tree, giving an Ollg(n//h) recursive depth. This will be sufficient to show our fairness.
Next, we evaluate the cost incurred at each stage in the hierarchy.
7

---

Lemma 6. In MakeFair (Algorithm 2. for all e E E that is separated before the recursive call:
cost (c) 00 ( 2( 1))
1 1 &+(k) k^
+ 1-
costr(e)
Algorithm 2 MakeFFir
Input: A hierarchy tree 7 of size 2 1/2c over a graph G (V, E, w) with vertices given of X colors, and parameters E [m]. k E [//(A= - 1)]. and E min 1/h)).
Output: A fair hierarchical clustering 7".
1: T =SplitRoot(1 h)
2: h
3: for each color f E [A] do
4: Order [us]e][k]] children(root((")) decreasing by ((eeaves(v.)
Pty (v.) 5: For all ė E [k). T + T'. fanalow_fold((() (T : [W/ [W/AA] /
6: N//k
7: end for
8: for each child 2 of root(T") do
9: in 2 (1ax(1/2e,) h) then
10: Replace T" [0y] +- MakePair(TT|o)),,,, k,
11: else
12: Replace T' with a tree of root uy leaves (vx))) and depth 1.
13: end if
14:
end for
As discussed before, the final cluster size should be (1 + c)nk^ /h. Any separated edge must have starting cluster size of at least (1 - c)n/h, as this the size of the smallest cluster involved in tree folding. From this, it is straightforward to compute the proportional cost increase of a single recursive level, as well as the cost increase from the initial splitting in Lemma
We additionally demonstrate that, whenever an edge is separated, its endpoints' least common ancestor will no longer be involved in any further recursive step. More formally:
Lemma 7. In MakeFair (Algorithm 2). any edge E is separated only one level of recursion.
Putting these two together pretty directly gives us our cost approximation.
Lemma 8. In MakeFair (Algorithm 2 cost(T") < (2h-1)) + 1+s
k. cost(T)
I-c
Finally, Theorem 1 comes directly from Lemmas and
4 Simulations
This section validates the theoretical guarantees of Algorithm 2 Specifically, we demonstrate that modifying an unfair hierarchical clustering using the presented procedure yields a fair hierarchy that incurs only a modest increase cost.
Datasets. We use two data sets, Census and Bank, from the UCI data repository Dua and Graff (2077) Within each, we subsample only the features with numerical values. To compute the cost of hierarchical clustering we set the similarity to be wii. I+d(1.] where d(i, j) is the Euclidean distance between points and j. We color data based on binary (represented blue and red) protected features: race for Census and marital status for Bank (both in line with the prior work of Abmmadann et al. (020)) ) As result, Census has blue to red ratio of 1:7 while Bank has 1:3. We then subsample each color in each data set such that we retain (approximately) the data's original balance. We use samples of size 512 for the balance experiments, and vary the sample sizes when assessing cost. For each experiment we conduct 10 independent replications (with different random seeds for the subsampling). and report the average results. We vary the parameters (c. h, k,
I Tro experimentally assess their theoretical impact on the approximate guarantees Section 3 Due to space constrains,
here present only the results for the Census dataset and defer the complimentary results Bank to the appendix.
Note that the parameter is used scale
8

---

15.0
75
68
1.00 1.50 2.50
1.50
0.20
0.75
0.30
6.75
6.00
Cluster Balance
subsample from the Census dataset of size n = 512. The four panels depict: (A) cluster balances after applying the (unfair) average-linkage algorithm, (B) the resultant cluster balances after running Algorithm 2 with parameters (c, h, k, E) = (8, 4, 2, 1 c/c log, n), (C) cluster balances after tuning c = 4, (D) cluster balances after further tuning 2. The vertical red line on each plot indicates the balance of the dataset itself.
Figure 3: Histogram of cluster balances after tree manipulation by Algorithm
Implementation. The Python code for the following experiments are available in the Supplementary Material. We start by running average-linkage, a popular hierarchical clustering algorithm. We then apply Algorithmp2 2 to modify this structure and induce a fair hierarchical clustering that exhibits mild increase the cost objective.
Metrics. our results we track the approximate cost objective increase as follows: Let G' be our given graph, T be average-linkaged output, and T" be Algorithm []s output. We then measure the ratio RATIO = costa (T')/cott from application of algorithm by reporting the balances of each cluster the final hierarchical clustering, where true fairness would match the color proportions of the underlying dataset.
We additionally quantify the faimesss that results
Results. We first demonstrate how our algorithm adapts an unfair hierarchy into one that achieves fair representation of the protected attributes as desired in the original problem formulation.
In Figure we depict the cluster balances of an unfair hierarchical clustering algorithm, namely eerorage-innaae" and subsequently demonstrate that our algorithm effectively concentrates all clusters around the underlying data balance. In particular, we first apply the algorithm and then show how we the balance is further refined by tuning the parameters. The application of Algorithm P dramatically improves the representation of the protected attributes in the final clustering and, as such, firmly resolves the problem of achieving fairness.
While reaching this fair partitioning of the data the overall goal, we further demonstrate that, in modifying the unfair clustering, we only increase the cost approximation by modest amount. Figure 4 fillustrates the change in rela- tive cost as we increase the sample size n, the primary influence on our theoretical cost guar- antees of Section B Specifically, we vary n in {128, 256, 512, 1024, 2048} and compute 10 replications (on different random seeds) of the fair hierarchical clustering procedure. Figure 4 depicts the mean relative cost of these replica- see
Ranatve Coot
D803
Somp
tions with standard error bars. Notably, that the cost does increase with as expected, but the increase relative to the unfair cost obtain by average linkage is only by a small multiplica- tive factor.
Figure 4: Relative of the fair hierarchical clustering resulting from Algorithm 2 compared the unfair clustering function of the sample size n.
As demonstrated through this experimentation, the simplistic procedure of Algorithm 2 not only ensures the desired fairness properties absent in conventional (unfair) clustering algorithms but accomplishes this feat with negligible rise in the overall cost. These results further highlight the immense value of our work.

---

References
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In KDD, pages 267-275, 2019.
Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang. Fair hierarchical clustering. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. 2016.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairmlbook org. 2019.
www
Omer Ben-Porat, Fedor Sandomirskiy, and Moshe Tennenholtz. Protecting the protected group: Circumventing harmful fairness. Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 5176-5184. AAAI Press, 2021.
Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In NeurlPS, pages 4955-4966, 2019.
Ioana O Bercea, Martin GroB, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In APPROX-RANDOM, pages 18:1-18:22, 2019.
M. Bogen and Ricke. Help wanted: An examination of hiring algorithms, equity, and bias. Technical report, Upturn, 2018.
Brian Brubach, Darshan Chakrabarti, John P. Dickerson, Samir Khuller, Aravind Srinivasan, and Leonidas Tsepenekas. A pairwise fair and community-preservvng approach k-center cluster- ing. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1178-1189, PMLR, 2020.
Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. In SODA, pages 841-854, 2017.
Junjie Chen, Shu Zhang, Xiaoting He, Qingwei Lin, Hongyu Zhang, Dan Hao, Yu Kang, Feng Gao, Zhangwei Xu, Yingnong Dang, and Dongmei Zhang. How incidental are the incidents? characterizing and prioritizing incidents for large-scale online service systems. Association for Computing Machinery, 2021a. ISBN 9781450367684.
Junjie Chen, Shu Zhang, Xiaoting He, Qingwei Lin, Hongyu Zhang, Dan Hao, Yu Kang, Feng Gao, Zhangwei Xu, Yingnong Dang, and Dongmei Zhang. How incidental are the incidents? characterizing and prioritizing incidents for large-scale online service systems. Association for Computing Machinery, 2021b. ISBN 9781450367684.
Yujun Chen, Xian Yang, Hang Dong, Xiaoting He, Hongyu Zhang, Qingwei Lin, Junjie Chen, Pu Zhao, Yu Kang, Feng Gao, Zhangwei Xu, and Dongmei Zhang. Identifying linked incidents in large-scale online service systems. Association for Computing Machinery, 2020. ISBN 9781450370431.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In NIPS, pages 5029-5037, 2017.
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, and Claire Mathieu. Hierarchical clustering: Objective functions and algorithms. In SODA, pages 378-397, 2018.
Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In STOC, pages 118-127, 2016.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL. http:://archive.ic.. eci/meduml
10

---

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In Shafi Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 214-226. ACM, 2012.
Marina Knittel, Max Springer, John P. Dickerson, and MohammadTaghi Hajiaghayi. Generalized reductions: Making any hierarchical clustering fair and balanced with low cost, 2023.
Alexander Kraskov, Harald Stögbauer, Ralph G. Andrzejak, and Peter Grassberger Hierarchical clustering using mutual information. CoRR, q-bio.QM/03) 1037, 2003.
Heidi Ledford. Millions of black people affected by racial bias in healthcare algorithms. Nature, 2019.
Benjamin Moseley and Joshua Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-mmans, and local search. In NIPS, pages 3094-3103, 2017.
Rohan Ramanath, Monojit Choudhury, and Kalika Bali. Entailment: An effective metric for compar- ing and evaluating hierarchical and non-hierarchical annotation schemes. In Stefanie Dipper, Maria Liakata, and Antonio Pareja-Lora, editors, Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse, 42-50. The Association for Computer Linguistics, 2013.
ACL 2013, August 8-9, 2013, Sofia, Bulgaria, pages
AN Selvan, LM Cole, Spackman. S Naylor, and Wright C. Hierarchical cluster analysis to aid diagnostic image data visualization of and other medical imaging modalities. In Molecular Biotechnology, 2005.
Latanya Sweeney. Discrimination in online ad delivery. ACM Queue, 2013.


Reviews:
[{"review_id": "ebxBfCZjfb", "reviewer": "Reviewer_gEkD", "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. \n", "questions": "- Can the authors provide experiments to compare their performance with other baselines?\n- Can the authors show that the performance of proposed algorithm is robust to the change of the originally given (unfair) hierarchical clustering?\n", "limitations": "Limitations are not well addressed by the authors. ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- Proposed an algorithm that modifies an unfair hierarchical clustering and yields a fair hierarchy with only a modest increase in cost.\n- 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. \n", "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. \n- 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.\n- 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. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*“I think the presentation of the paper needs to be largely modified…”*\n\nWe will revise the paper for the final draft per the suggestions of all reviewers. Notably, we will guarantee that all formal theorems and definitions have a high level intuitive explanation in the introduction to alleviate the mentioned confusions.\n\nWe furthermore refer the reviewer to the response of reviewer XyRG, wherein they mention that such “impenetrable” theorem statements cannot be avoided for this problem. To alleviate this, we provide some informal theorem statements and terminology definitions which will be included in the main text to improve readability (see our response to XyRG). We additionally refer to the response to reviewer qPF4’s question to better understand the results.\n\n*“What are the main changes this paper presents [as compared to Knittel 2023]...”*\n\nOur work builds upon that of Knittel 2023 in two ways. First, we reduce the number of tree operations used from 4 to 2, where the more complicated operation, tree folding, is vastly simplified. Second, in contrast to Knittel 2023 who applied one operator to the entire hierarchy at a time, we alternate applying one operator and the other. This reduces the number of top-bottom passes of the algorithm from 4 to 1 and avoids an exponential (in $O(\\delta \\log n)$) increase in the cost. This reason is somewhat complex and is a main technical contribution. Moreover, our analysis is considerably more readable and provides the much desired polylogarithmic cost approximation without the additional n^\\delta term of the former result.\n\n*“Can we call this a modest cost increase… isn’t it easier to achieve the fairness for larger $n$…?”*\n\nGiven the hardness of the vanilla problem (i.e., it’s APX-hard and the best efficient approximation is $O(\\sqrt{\\log n})$), and the increased complication posed by the fairness constraint, we would expect the cost to necessarily be increased by a large factor in the worst case (see the response to XyRG). We say “modest” because the cost increase is very small compared to $n$, which reflects the theory that it is at worst polylogarithmic in $n$. While larger n may in some ways give us more leeway to combine clusters, it is extremely difficult to characterize the most adversarial examples, which is an open question. Notice that our algorithms are agnostic to the degree of color representation imbalance in clusters - as in, the only time it considers colors at all is when it orders cluster by their relative representations of a fixed color. More involved, complicated algorithms will likely be needed to leverage the large cluster sizes to carefully handle these imbalances.\n\n*“Compare to other baselines…”*\n\nThis is a novel problem setting and the only known algorithms for such a fairness guarantee are the present work and the cited Knittel 2023 paper. Here, we provide some experimental results contrasting the two algorithms' cost returns after producing a fair clustering for full comparison.\n\nThe table below compares the relative (to unfair clustering) cost of our algorithm as compared to the baseline algorithm of Knittel 2023 (with the parameter of $\\delta$ set to ¼):\n\n| n | Baseline | Our Algorithm | \n| -- | --------- | ---------------- |\n| 128 | 3.65240727 | 1.08586718 | \n| 256 | 5.68329859 | 1.42082465 | \n| 512 | 12.30571685 | 2.5869583 | \n| 1024 | 25.17125835 | 6.6745378 | \n| 2048 | 52.93911771 | 7.86944693 | \n\nAs you can see, since our algorithm is only polylogarithmic in $n$, it naturally scales much better with the input sample size. This further highlights the impact of our work and will be included in the final version of our paper.\n\n*“Robust to changes in the original hierarchical clustering?”*\n\nWe thank the reviewer for noting that it would be interesting to study the fair clustering problem in a dynamic setting wherein an algorithm can handle updates to the underlying structure of the clustering. This is an important problem but outside the scope of the present work. Though, with some speculation, it may be possible to add a small amount of randomness to our algorithm (e.g., whenever we compare two cluster sizes) to achieve robustness to local changes while still achieving only marginally worse approximations and degrees of fairness.\n"}, {"review_id": "jSOy84iCEH", "reviewer": "Reviewer_qPF4", "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.", "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).", "limitations": "Authors have addressed limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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.\nThe 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.\nThe way the bound is written at the moment is completely impenetrable - please see the “Questions” section for advice on this.\nThere are issues with the writing of the paper which I shall now list (I include here any typos etc.):\n- The Introduction section uses a lot of notation that is not defined until later in the paper. This should definitely be fixed.\n- 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.\n- Definition 6 is ambiguous and hence is not a proper definition.\n- In line 60 I believe the authors mean “fairness literature”\n- In line 84 \\gamma must surely appear in the approximation ratio\n- Line 103 should start with “which is” instead of “is”\n- In line 103 “tree” should be replaced by “graph”\n- The use of “i.e.” in line 123 is wrong.\n- Line 161 should say “inserts a new vertex p…”\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*“The way the bound is written is completely impenetrable…”*\n\nWe emphasize, as pointed out by reviewer XyRG, that for the given problem, our results require some in depth math to be fully accurate. To alleviate these issues, we will provide informal definitions and theorem statements in the response to reviewer XyRG.\n\n*“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$?”*\n\nWe note that $b_i$ should always be $\\le 1$ since it’s the upper bound on the fractional representation of a color in a cluster (so if $b_i > 1$, it’s equivalent to $b_i = 1$, since that is the “no upper bound” case). We will answer the question assuming $0 < a < b < 1$, and all $a_i = a$ and $b_i = b$. In that case, yes you could derive a set of parameters needed to achieve this degree of fairness in terms of $a$ and $b$, and then plug them into the time complexity and approximation ratios. However, since there is a tradeoff between our parameters $\\epsilon, h$, and $k$, and how they affect the degree of fairness, there will actually be a large range of parameterizations one can work with, so we cannot pose a straightforward answer. Realistically, this might be best done programmatically with parameter tuning.\n\nWe thank the reviewer for the suggested revisions to improve readability of our main results. To more intuitively present the results, we intend to include the following informal theorem statement in the introduction (and defer the full parametrization to the analysis): \n\n*Given a $\\gamma$-approximation to the cost objective for a hierarchical clustering on set of $n$ points, Algorithm 2 yields an $O(\\log^2 n)$ approximation to cost which is relatively fair in time $O(n \\log^2 n)$. Moreover, all clusters are $O(1/\\log n)$ balanced, ie. any cluster’s children clusters are within $O(1 / \\log n)$ size different.*\n\nWhere we state that “relative fairness” simply implies looser constraints on the proportional representation of each color in each cluster. Lastly, we thank the reviewer for noting typos and grammatical errors, all of which have  now been corrected.\n"}, {"review_id": "XI0DRgNK5K", "reviewer": "Reviewer_XyRG", "summary": "  The paper addresses the problem of fair hierarchical clustering.\nGiven a hierarchical clustering with a certain cost (determined by\nDasgupta's cost function), the paper shows how the hierarchy (tree) can be\nefficiently modified so that fairness constraints are satisfied\nand the cost of the tree increases (provably) by only by a\nsmall factor. The theoretical results are validated through experiments\non two data sets.", "questions": "  (1) On lines 124--126 (page 4), it is mentioned that the approximation\n  factor is with respect to an optimal vanilla hierarchy (which doesn't\n  consider fairness).  Did the previous work also use this assumption?\n\n  (2) Are any hardness of approximation results known for the problem? (It will\n  be interesting to see how close the polylog approximation is compared to\n  what can't be achieved in polynomial time under a standard assumption\n  such as P != NP.)\n\n  (3) The statements of theorems/lemmas etc. involve many parameters. This\n  reviewer agrees that this is unavoidable for making the theorems precise.\n  Would it be possible to include informal statements of results that are easier\n  to understand (even if they are not mathematically accurate)?\n\n  Some minor typos:\n\n  (a) Line 62 (page 2): \"as a in\" ---> \"as an\"\n  (a) Line 121 (page 4): \"increasing cost\" ---> \"increasing the cost\"", "limitations": "None", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(a) The paper provides the first (provable) polylog approximation\n  for the cost of hierarchical clustering while satisfying fairness\n  requirements. This is an important advance in fair hierarchical clustering.\n\n  (b) The algorithm simplifies a previously known algorithm while\n  achieving the approximation bound.\n\n  (c) The paper is written very well.", "weaknesses": "  A (very) minor weakness is that the statements of theorems require\na good amount of effort to understand since they involve many different\nparameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*“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?”*\n\nYes, the previous work also considers an approximation to an optimal, unfair, hierarchy, since it is currently not known how much worse an optimal fair hierarchy may be. One can simply view it as a lower bound on the optimal fair cost, however we note it in the results since it is a strictly stronger statement. It is interesting to note that the best known (unfair) cost approximation is also a power of log(n), specifically ½, so our result does not deviate too considerably from this. Though it would be nice to shoot for logarithmic or possibly sublogarithmic to narrow this gap. That's a good future direction.\n\n*“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.)”*\n\nThe only known hardness results are for the cost optimization in the unfair setting (which is known to be APX hard). We acknowledge the interest in determining a lower bound on the approximation factor for fair clustering hardness. This, however, would require distinguishing the fair optimum to the unfair optimum. No previous work has managed to do that, in fact, all approximations for this problem (ours and previous) compared the output cost to the unfair optimum cost, which is a lower bound on the fair optimum cost. Differentiating between the two in any way would be a very useful result!\n\nThe 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)?”\n\nWe intend to incorporate the following theorem (sketches) in the main text to address these concerns and improve the overall readability of our results:\n\n*Given a $\\gamma$-approximation to the cost objective for a hierarchical clustering on set of $n$ points, Algorithm 2 yields an $O(\\log^2 n)$ approximation to cost which is fair in time $O(n \\log^2 n)$. Moreover, all clusters are $O(1/\\log n)$ balanced, ie. any cluster’s children clusters are within $O(1 / \\log n)$ size different.*\n\nThis result is highlighted in Corollary 1, but will be expanded upon with more intuition for the definitions before their formal definition in Section 2 to improve readability."}, {"review_id": "a0Tm5Im7E7", "reviewer": "Reviewer_BAkf", "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).", "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?\n\n(2) How do you define the cluster balance? What does $c$ mean in the simulation settings?\n\n(3) Line 171, Def. 6, do you mean root$(T_f)$, rather than root$(T)$?\n\n(4) Line 236, do you mean \"at most $h$\" rather than \"at least $h$\"?\n\n(5) A typo: Line 281, \"poitns\" should be \"points\".\n\n(6) A ref error: Line 581.\n\n(7) Please delete Line 532 that has revealed author information!", "limitations": "Yes, the authors have addressed the limitations in a specific section (Appendix A).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(1) A theoretical result of an approximation algorithm for the fair clustering problem, with great improvement in approximation factor.\n\n(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.\n\n(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.\n\n(3) There are some unclear points (refer to the questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*“This work seems to depend heavily on Knittel 2023…”*\n\nThis work does build upon the algorithm of Knittel 2023, but greatly simplifies the procedure to be more easily implemented. Moreover, our analysis removes the extra $n^\\delta$ approximation factor which allows for the first polylogarithmic approximation to cost with fairness. Since the best known unfair cost approximation is also polylogarithmic, this result is substantial in showing that a clustering can be made fair with only a modest increase in the approximation factor. In a sense the “price of fairness” is demonstrated to be low.\n\n*“Scalability of $h, k$, and $\\lambda$ is doubtful…”*\n\nWhile the runtime may not be technically scalable in terms of these parameters, these parameters are much less than $n$. In consideration of this, the runtime is certainly scalable in $n$. Since $n \\gg h \\gg \\lambda, k,$ this will certainly be $O(n^2 \\log(n))$. Notice that for our Corollary, we actually assume the largest parameter is $h = O(\\log n)$. Therefore, the runtime should be something like $O(n \\log^2(n))$. \n\n*“What is the role of $\\gamma$?”*\n\nAs correctly noted, $\\gamma$ is the approximation factor to cost incurred by the base unfair hierarchical clustering algorithm. And yes, gamma should be included in the approximation factor, we will correct this. To date, the best known such algorithm admits an $O(\\sqrt{\\log n})$ approximation factor.\n\n*“How do you define the cluster balance? What is c in the experiments?”*\n\nWe apologize for the confusion in the presentation. The parameter noted as $c$ in the experiments is used to define the $\\epsilon$ value and is not related to the notation for cluster balance in theoretical results. We will rectify this in the camera-ready version of our paper.\n\nWe lastly thank the reviewer for identifying typos and other mistakes, which have now been corrected.\n"}]

Author rebuttal:

Meta-review: The paper studies the problem of fair hierarchical clustering and improves over existing work of Knittel et al.'2023 to present the first poly-logarithmic approximation to the problem. Overall the reviewers liked the paper and agreed that it is a substantial theoretical contribution. One reviewer felt that the techniques borrowed heavily from prior work of Knittel et al.' 2023. While a lot of the machinery is built on top of prior work, there is enough technical novelty in achieving the poly-log factor via the improved algorithm. The authors are encouraged to simplify the presentation more and multiple reviewers felt that in some cases the terminology was not easy to understand without looking at prior work.
Decision: Accept (poster)