A Revenue Function for Comparison-Based Hierarchical Clustering
Authors: Aishik Mandal
Michaël Perrot
Debarghya Ghoshdastidar
Venue: Accepted by TMLR ()

Abstract: Comparison-based learning addresses the problem of learning when, instead of explicit features or pairwise similarities, one only has access to comparisons of the form: \emph{Object $A$ is more similar to $B$ than to $C$.}  Recently, it has been shown that, in Hierarchical Clustering, single and complete linkage can be directly implemented using only such comparisons while several algorithms have been proposed to emulate the behaviour of average linkage. Hence, finding hierarchies (or dendrograms) using only comparisons is a well understood problem. However, evaluating their meaningfulness when no ground-truth nor explicit similarities are available remains an open question.

In this paper, we bridge this gap by proposing a new revenue function that allows one to measure the goodness of dendrograms using only comparisons. We show that this function is closely related to Dasgupta's cost for hierarchical clustering that uses pairwise similarities.
On the theoretical side, we use the proposed revenue function to resolve the open problem of whether one can approximately recover a latent hierarchy using few triplet comparisons. On the practical side, we present principled algorithms for comparison-based hierarchical clustering based on the maximisation of the revenue and we empirically compare them with existing methods.

Published in Transactions on Machine Learning Research (03/2023)
A Revenue Function for Comparison-Basete Hierarchical Clustering
Aishik Mandal
Rttishik@titkgp..oo..
Centre of Excellence in Artificial Intelligence Indian Institute of Technology Kharugpur
Michaël Perrot"
pichuee..errootiariia..
Unio. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRISIAL, F-59000 Lille, France
Debarghya Ghoshdastidar"
ghoshdas@cit. tum..
Technical University of Munich
School of Computation, Information and Technology Munich Data Science Institute.
Reviewed on OpenReview: https: oppere/e/penrevieuu. net/ forum? Q2Wr4u8PXa
Abstract
Comparison-based learning addresses the problem of learning when, instead of explicit fea- tures or pairwise similarities, one only has access to comparisons of the form: Object A is more similar to B than to C. Recently, it has been shown that, in Hicrarchical Clustering, single and complete linkage can be directly implemented using only such comparisons while several algorithms have been proposed to emulate the behaviour of average linkage. Hence, finding hierarchies (or dendrograms) using only comparisons is well understood problem. However, evaluating their meaningfulness when no ground-truth explicit similarities are available remains an open question.
In this paper, we bridge this gap by proposing new revenuc function that allows one to measure the goodness of dendrograms using only comparisons. We show that this function is closely related to Dasgupta's cost for hierarchical clustering that uses pairwise similaritie On the theoretical side, we use the proposed revenue function to resolve the open problem of whether one can approximately recover a latent hicrarchy using few triplct comparisons. On the practical side, we present. principled algorithus for comparison- clustering based on the maximisation of the revenue and we empirically compare them with existing methods.
hierarchical
1 Introduction
In the past decade, there has been an exponential growth in the scope of data science and machine learning in domains such as psycho-physics (Shepard 1962 Stewart et. al. 2005
Haghiri el. al.] 2020) cultural
psychology (Berenhaut
al. 2022 evolutionary biology (Foulds al. 1979 Semple and Steel 2003
Catanzaro 2009), or crowd-sourcing (Hikinheemmo and Ukkonen
2013
Ukkonen 2017) among others.
type of data that has recently gained some traction in these contexts is comparisons (Stewart et al. 2005
Agarwal et al. 2007), particularly in the form of:
Triplet comparison: Binary response to the query is object more similar to object j than to object A:?
Quadruplet comparison: Binary response the query are objects i and j more similar to each other than objects & and !?
All authors contributed equally.

---

Published in Transactions on Machine Learning Research (03/2023)
Comparisons have been used in the psycho-physies literature for more than 50 years since it is known that
humans can provide relative measurements better than absolute ones [hheaadd 1962 Stewart et al. 2005
It led to a surge of popularity of comparisons in the context of crowdsourced data about objects that cannot be represented by Euclidean features, such as food (Wilber et al.; 2014) or musical artists (Ellis et al. 2002) or objects for which humans cannot robustly estimate a pairwise similarity, for instance cars (Kleindessner
and von Luxburg, 2017) or natural scenes (Heikinheimo and Ukkonen, 2013). The purpose of collecting comparisons is often to learn patterns in the objects, such as latent clusters, or use them for prediction, as
in classification. Hence, there has been significant development of algorithms for comparison-based learning
AAgawal et al. 2007 Heikinheimo and Ukkonen, 2013 Haghiri et al. 2017 Kazemi et al. 2018 Perrot and
von Luxburg 2019).
The present paper focuses on comparison based hierarchical clustering. Clustering refers to partitioning a dataset into groups of similar objects, while hierarchical clustering is the problem of finding partitions of the data at different levels of granularity. It is natural to wonder how one can group similar objects or find hierarchy of groups when neither features nor pairwise similarities are available, and one only has access to triplet or quadruplet comparisons. For instance, the objects in the food dataset (Wilber et al.) 2014] can be broadly categorised into 'sweets or desserts' and 'main or savoury dishes', but the latter can be further sub-divided into meat dishes, soups and others. Surprisingly, interest in comparison- based (hierarchical) clustering stemmed in 1970s when single linkage clustering gained popularity, and researchers realised that the method uses only ordinal informal instead of absolute values of pairwise similarities (Janowitz 1971 Sibson 1972, Janowitz 1979). Around the same time, works also started on the consensus tree problem, that is, constructing trees (hierarchies) from given sub-trees or ordinal relations (Adams IIT 1972 Aho
ct al. 1981) The problem has since evolved an important topic in both computational biology and computer science, most notably addressing the question of phylogenetic tree reconstruction under triplet or other ordinal constraints SSmple and Steel (2003); Wul (2004); Snir and Yuster (2011). More recently, Ghoshdastidar et al. (2019) re-discovered that single and complete linkage can be computed using only few actively chosen quadruplet comparisons. There are, however, limited practical settings where the learning algorithm can actively decide which comparisons should be queried, and the most. relevant case that of learning from a set of passively collected comparisons. This is certainly true in the known practical applications of comparison-baser hicrarchical clustering, such as (hicrarchical) clustering of objects from crowd-sourced comparisons [Ukkonen 2017 Kleindessner and von Luxburg 2017), , finding communities in languages or in cultural psychology (Berenhaut et al. 2022), and constructing relational database queries Aho et al. (981] or phylogenetic trees (Semple and Steel 2003).
One of the fundamental problems in hierarchical clustering is to evaluate the goodness of a hierarchy. This issue is obviously inherent to identifying better hierarchical clustering algorithms. In the phylogencties literature, the optimal hierarchy problem typically corresponds to the minimum evolution problem, where, given set of species and pairwise distance matrix (representing evolutionary distance between species), the goal is to find a. weighted tree with minimal total edge weights that preserve the evolutionary distances (Foulds) ct al.) 1979 Catanzaro 2009). A similar philosophy exists in the carly works on hicrarchical clustering, where an algorithm is judged to better if the ultrametric induced by the output tree is closer to the specified pairwise dissimilarities among the given objects (Janowitz) 1979). More recently, there has been efforts to mathematically quantify the goodness of a hicrarchy in terms of certain cost or revenue functions (Dasguptal 2016 Moseley and Wang] 2017 Wang and Wang (020)). Such formulations have led to a plethora of new methods for hierarchical clustering that also come with worst-case approximation guarantees (Cohen-Addad)
et al. 2019 Charikar et al. 2019 Chatziafratis et al. 2021).
The main motivation for this work stems from the lack of cost revenue functions that can be used in the comparison-based framework. Available goodness measures for trees can only be defined using pairwise (dis)similarities (Dasgupta 2016 Moscley and Wang 2017 Wang and Wang 2020). Hence, existing works on comparison--aased hierarchical clustering either demonstrate the meaningfulness of the computed hierarchies visually or in artificial settings, where compar- isons are derived from pairwiso similarities (Kleindessner and von Luxburg 2017 Ghoshdastidar et al. 2019). Neither solution is useful in practice, where one only has access to comparisons. In this paper, we propose new revenue functions for dendrograms that are only based on triplet or quadruplet comparisons (Section
Motivation for this work and our contributions.
2

---

Published in Transactions on Machine Learning Research (03/2023)
We show that the proposed comparison-basee revenues are equivalent to Dasgupta's cost revenue Dasgupta 2016 Moseley and Wang 2017) applied to particular pairwise similarities that can be computed from comparisons, Interestingly, the pairwise similarities that arise from this equivalence are known in the comparison-based based clustering literature (Perrot et al. 2020
Section 5 demonstrates that the proposed revenue function meaningfully captures the goodness of hier- archical tree. For this purpose, we consider the problem of reconstructing a latent hierarchy (for example, phylogeny tree) from ordinal constraints (Emamjomch-Zadee Zadeh and Kempel 2018). In particular, we show that, when all possible triplets among the objects are available, the dendrogram corresponding to the latent hicrarchy maximises the proposed revenue function. This, in turn, implies that one can mathematically formulate the triplet-based hierarchical clustering problem as a mazimum triplel comperison revenue prob- lem. We further address the question of whether one can approximately recover the latent hierarchy using fewer than ( triplets. This problem has not been directly addressed in previous works (see Section 2 We show that only On logn/c?) passive triplcts suffice to obtain (1 - -appoooiiimiiiioo of the optimal revenue.
Finally, Sections 6 use the connection of the proposed revenue functions to the additive similarities in Perrot et al. (2020 to present two variants of average linkage hicrarchical clustering based on passive triplet or quadruplet comparisons. The performance of these approaches is empirically compared with state of the art baselines using synthetic and real datasets.
2 Related Work
In this section, we briefly review the algorithmic developments of comparison-based hierarchical clustering, as well as existing theoretical results related to this problem. As noted earlier, interest in comparison- based hierarchical clustering stemmed from different applications. The current literature consists of two lines of research- works related reconstruction of phylogenetic trees (Wul 2004] Snir and Yuster 2011: Chatziafratis et al. 2021 and those focusing on ordinal data analysis from crowd-sourced data (Kleindessner
and von Luxburg 2017
Ghoshdastidar et al. 2019).
In ordinal data analysis literature, the most widely used principle is that of ordinal embedding, where the underlying idea is to retrieve Euclidean representations of the objects that respect the available comparisons as well as possible (see the review in Vankadara et al. (2019) for more details). The embedded data can be subscquently used for (hicrarchical) clustcring. While this principle provides flcxibility in the choice of clustering methods, the Euclidean restriction of the underlying data often leads to inaccurate representa- tions, and hence, poor performance in the context. of hierarchical clustering (Ghoshdastidar et al.] 2019). The restrictive assumption of Euclidean embedding is avoided by computing pairwise similarities from avail- able comparisons (Kleindessner and von Luxburg 2017 Ghoshdastidar et al. 2019). Standard hierarchical clustering algorithms, such as average linkage, can then be applied using the pairwise similarities.
An alternative approach for baseed (hierarchical) clustering is to define an appropriate cost or objective based on comparison and directly optimise it. [kkkonen (2017) employs such a technique for clus- tering using crowd-sourced data, while this principle underlies most techniques in consensus tree problems or phylogenctic tree reconstruction. In the latter context, two well-studied optimisation problems are marimum rooled triplel consislency (Wu) 2004 Byrka et al.) 2010) finding a hierarchy that satisfies most, if not all, given triplets- and marimum quartet consistency Snir and Yuster 2011 Jiang et al. 2000)-where where one has access to quartets (sub-trees with four leaves indicating which pairs should be merged first) and the problem is to find a tree that satisfies most given quartets Other related optimisation problems as well as various constraints other than triplets or quartets have been studied (Snir and Rao 2010 Chatziafratis et al. 2021) Since the focus of the present paper is to define revenue for trees (see Section I our work naturally belongs to this broad class of hierarchical clustering algorithms based on revenue maximisation. However, in Theorem I we relate the proposed revenues to pairwise similarities computed from comparisons. Hence,
"Note that quartets are different from quadruplets though both are defined on four objects. More preciscly, quartet i,j,k, & correspouds information that i,j and & should be merged in the tree before all four are merged. Using the notation from Section 3 quadruplet (1, only implies siz > 8ui whereas a quartet on i,j, 8, implies min(sij, su3 > max Sak Sa1, 8jks Syt)-
3

---

Published in Transactions on Machine Learning Research (03/2023)
the present paper connects the optimisation principle to the aforementioned approach of defining pairwise similarities from comparisons.
Prior works on comparison-based hierarchical clustering provide a range of computational and statistical results. On the computational side, it is known that both the problems of maximum rooted triplet consis- tency and maximum quartet consistency are NP-hard (Byrka et al. 2010 Snir and Yuster 2011]. However, polynomial-time constant factor approximation algorithms are known in both cases, assuming that uni- formly random subset of triplets/quartett is available. For triplets, Wu (004)) provides 3-approximation algorithm- fraction at least 3 of the given triplets are satisfied which slightly improved in Byrka et al. (2010). For quartets, polynomial-time algorithms that satisfy at least (1 (1-c) (1-c)-fractinn of the given quartets are known (Jiang et al. 2000 Snir and Yuster, 2011). While the above results focus on finding hierarchies that only match the given triplets/quarte quartets, Emamjomeh- Zadeee Zadeh and Kempe) (2018) show that the true (la- tent) hierarchy can be recovered only if (2(n²) passive (uniformly sampled) triplcts are available. In contrast, only (n logn) triplets suffice they are actively queried. In Scction 5 we show that only On log n/(²)
uniformly sampled triplets suffice to obtain (1 e)-approximation of the optimal triplel. revenue.
A different latent model is considered in Ghoshdastidar et al. (019)) and Perrot et al. 2020 where the objects have latent (noisy) pairwise similarities that have a (hicrarchical) cluster structure. Noisy triplet- s/quadrupless are uniformly sampled following the noisy latent similarities. focus on quadruplet- based hierarchical clustering and show that O log log n) suffice to recover the latent hierarchy, Perrot et al. (2020) show that flat latent clusters can be exactly recovered using only O(n² log n) uniformly sampled triplets/quadrupps quadruplets. Although our model is different from Perrot et al. (2020), , we obtain similar (n log n) upper bound sample complexity- even when the triplets are noisy.
Chilsshhhsaaattdarr et al. (2019)
3 Preliminaries
n). We consider the problem of hierarchical clustering of a set of n objects, denoted by [n] = {1,2, .I, In this paper, we assume that a hierarchy dendrogram
[n] is binary tree H whose root node is the set In], each leaf node is a singleton containing one of the n objects, and each internal node represents a set C C [n]] with its two children, Ci and C22 denoting a partition of C, that is min(ICi), > 0, C = CCC and C n C22 = O. In the following, we use binary tree or tree to designate hierarchy. For node C, we use HC) to denote the subtree rooted at C and [H)] represents the number of leaves in the subtree, or equivalently, the number of objects in the set C. For objects i,j E [n], let V denote the smallest node in the tree containing both and j, and V j) denote the smallest subtree containing both and j. The goal of hierarchical clustering is to find dendrogram H that is optimal, or at least good, in some sense. In the next subsections, we recall Dasgupta's cost for hierarchical clustering that allows one to measure the goodness of a dendrogram given full access to pairwise similarities, and then describe the comparison- based learning framework, where only triplct or quadruplct comparisons are available. In the paper, we use the standard Landau notations O(),, 2()), o(-), where the asymptotics are defined with respect to n.
3.1 Dasgupta's Cost for Hierarchical Clustering
Suppose one has access to function s: [n] x [n] + R, symmetric, such that 8ij s(i,j) denotes the pairwise similarity between objects i,j E [n]. Dasgupta's cost function (Dsgupla 2016 for dendrogram H on [r], with respect to the pairwise similarity 8, is defined as
Doost HH
Σ (.ENR, KJ
Sig H(V)))
(1)
An equivalent definition of the above cost can be found in Wang and Wang (020), where the cost is expressed in terms of triplets of objects instead of pairs. To find a good dendrogram, Dasgupta (2016) proposed to minimize this cost over all trees. While is NP-hard to find the optimal solution, several relaxations are known to have constant factor approximation guarantees for Dasgupta's cost or related quantities. Tn
4

---

Published in Transactions on Machine Learning Research (03/2023)
particular, Moseley and Wang 2017 defined Dasgupta's revenue function,
Drev(H, = n
E
Sij - Dcost H, s).
(2)
(.jE[n), Ksj
Note that since Esj 8ij is fixed, maximising Drev(H, over all binary trees is equivalent to minimising (eost(H,s) s). It can then be shown that the revenue of the tree H obtained from average linkage achieves revenue Drev(H, s) that is at least of the revenue of the optimal tree that would achieve the best revenue, provided that the similarity function is non-negative.
3.2 Comparison-based Learning
In the present paper, we assume that the pairwise similarities (sy))) are not available. Instead the algorithm has access to either set of triplets T, which is a subset of
Tau ((.,,,) E [m] 8ij su, ijjk distinct),
or set of quadruplets Q C Qalt, where
Call =
siy suat < k < (i,5) # (k,,1))
Since the pairwise similarities are assumed symmetric, we set j and A < to avoid cousidering the same comparison multiple times. We note that the number possible comparisons high-IQaul = O(n)) and (Tall = but,)bbut, in practice, the observed comparisons, T or Q may be fewer than that, about O(n²) comparisons, can be seen from Table 3 Note that whenever triple (i.j.k) is considered, T contains either (i,j, k) or (i, k,j), depending on whether 8ij S Sik- The same holds for quadruplets. We further assume that the observed set of comparisons T, or 2, is passively collected, that is the algorithm cannot decide which comparisons should be present in it as opposed to the active sctting where the algorithm can choose which comparisons should be observed (Ghoshdastidar al. 2019
4 Comparison-based Revenue
We present two comparison-based revenue functions for hierarchical clustering, one in the triplets framework and the other for quadruplet comparisons.
Triplet comparisons. We first consider the case of triplets and assume that the algorithm has access to a passively collected set of triplets T. We define the triplet comparison revenue binary troe (dendrogram) H on [n], using triplets T,
Tree H,T)=
Σ ( (H(V))) (K..A)ET
For every (i,j,k) k) E T, we know that i is more similar to j than to k, and hence, we prefer to merge i.j before merging and k. It means the idcal tree should have [H v k)] > [i) for every (i.j. k) E T. Hence, it is desirable to maximise (i v k)] - (i V Á)l for every observed triplet (i.j, ET. We then propose formulate triplets comparison- based hierarchical clustering the problem of maximizing Trev(H, over all binary trees.
Remark 1. We nole that the proposed triplet revenue is significantly different from the triplet based cost presented in Wang and Wang (2020). The most important distinction is that the triplet cost in Wang and Wang (2020) a reformulation of Dasgupta's cost, and requires knowledge of pairwise similarities. In contrast, the revence in equation is computed only from triplet comparisons without access to pairwise similarities.
5

---

Published in Transactions on Machine Learning Research (03/2023)
Quadruplet comparisons. The above formulation be similarly stated in the quadruplets setting. Assuming that the algorithm has access to passively collected set of quadruplets Q, we define the quadruplet comparison revenue of a binary tree H on [n] as
Qrev(H, ②) 2)= =
E
(4)
Similar the triplet setting, every ki,j,k.1) E Q indicates that i,j should be merged earlier than k, in H, and we prefer trees such that [H VI) 2 [))- We propose to achieve this by finding tree that maximises Qreo( H, Q).
Connection with Dasgupta's cost. While one may try to directly maximise the above comparison- based revenue functions, the following equivalence to Dasgupta's cost and revenue allows us to employ existing methods for hierarchical clustering that require pairwise similarities. In the following, let 4g denote the indicator of event E, that is, Ig if happens, and otherwisc.
Theorem 1. For any given set of triplets T and any dendrogram on [m],
Treu(H, -Deost H, AAdS3) = Dree((HH AAdsa)
where 8 AddS3 refers to the addilive simmllariy from triplets (AddS3) defined by Perrol el al. 2020
Adds's
(LOSMET MAAJET + LURANET - I(AA.NTT) kiij
Σ
Similarly, for any set of quadruplets Q and dendrogram H,
Qrev H, Q) - Deoos AdaSA) = Drev H, Adasa).
where s Add54 is the additive similarity from quadruplets (AddS4) defined by Perrot et al. (2020)
Adds4
E
Sij
Right, (R.1)
Proof idea (details in appendix). Proving Treu(H,T) = -Deost( H, Add53) involves a rearrangement of terms, with the observation that, for every i,J, the term (H v j)l appears in the summation in equa- tion 3 with coefficient -1 when ki.j.k) E T or (j,i,k) T and with coefficient +1 when (i, ki,k, E or (j,,,) 2) T. Adding these coofficients for all is & i,j gives us - Addss and proves the equality. The second equality - -Dcost(Hl H, s Adas3) = Drev( (H, Adds3) simply follows from the observation that Eie, %1) The proof for quadruplets similar.
AddS3 = 0.
5 Recovering a Latent Hierarchy by Triplet Revenue Maximisation
In this section, we consider the problem of recovering a latent hierarchy from triplet comparisons, earlier studied in Emaaammmm----aane Zadeh and Kempel 2018). Let Ho be hierarchy on [n], from which we derive a set of triplets
To
(j,i,)) Hoo j)l < (o(( v A)), [ol k)D).
(5)
One can show that any rooted tree H' that satisfies all triplets in To is equivalent to Ho. up to isomorphic transformations, and hence, one can exactly recover Ho given To- Note that |Tal = (²)) It is natural to ask whether, Hy can be recovered if a significantly smaller number of triplets are observed. To this end, Famamjoneh-7adeeh and Kempe (20T8) show that if the algorithm can choose the triplets to be queried (active setting), then a deterministic algorithm can recover Ho using only n logz n queries. However, the authors also construct (randomised) Ho show that for any fixed sct T To with fewer than n² 22/48 triplets, the
Emamjomeh-Zadel and Kempe (2018) consider triples the form (i that imply i,J closer each other than k
respect Ho. Each such triple (L.,k) correspond two triplets (1. k) and (j,ik) k) our setting.

---

Published in Transactions on Machine Learning Research (03/2023)
latent hierarchy Ho cannot be recovered with probability at least 1/2. This raises the question approximately recover Ho from smaller set of triplets T?
We use the proposed triplets-based revenue to answer this question in the affirmative. Before providing an approximation guarantee, we first show the significance of our formulation in this context by proving that one can recover Ho from To by maximising Tree.
Proposition 2. Consider the aforementioned setting, where Ho is a hierarchy on [n]] objects, and To is the corresponding set of triplets as defined above. Then
Hu = arg max Trev(H, To),
H
where the marimisation is over all binary trees H on [n].
Proof idea (details in appendix). One can show that if To is a set of triplets corresponding to hierarchy Ho according to equation and (sty)ssissn denote the AddS3 similarity derived from To (cf. Theorem [], then $iy = 2n + 2 3 Hi v. that is, one can recursively construct Hg from the AddS3 similaritics. We further use this representation to show that To, Ti are respectively derived from two hierarchies Ho, H, according equation [ then there is a symmetry in the triplet revenue of the form Trev(Ho, Ti) = Trev(HH, To).
The above symmetry implies that proving Ho uniquely maximises Treu H, To) is equivalent to showing that Tree( (Ho To) > Tree(Fi Ho, Ti) for every triplet set Ti that correspond to a binary tree H1 on [n] that is not isomorphic to Ho. This last claim can be proved by showing that every j, k for which the ordering of merger is changed between Hg and Ha a positive contribution in Trev(H (o, To) - Trev(Ho, Ti). ]
KimamjomchZZadee Zadch and Kempe 2018 prove the uniqueness of the hicrarchy that satisfies all the triplets
in To, that is, Ho maximises the function S(H, To) = E(,,,,)TT, [[(())))) (((())))- While maximising Trev(H, To) seems to be a relaxation of maximising I(H, To) in this context, Proposition both problems have the same optimal solution Ho-
2 shows that
5.1 Approximate Recovery of Ho Using Passive Triplets
We consider the setting, where To is not completely available but one has access to uniformly sampled subset T = To- We show that [T| = Onn n/?) triplets suffice to obtain tree H such that Trev To) 2 (--c)-Tre(HH,, To), that is, we get good approximation of Ho with much fewer than n² samples, although we may not exactly recover Ho. We consider the following uniform sampling to obtain T. Let Pa E (0, 1] denote a sampling probability, depending on n. For every pair triplets (i.j, k), (,i,k) E To. we add the pair to T with probability Pn. We state the following approximation guarantce for trees derived using T.
Theorem 3. For a triplet set T obtained from the above sampling procedure, consider the hierarchy
u = arg max Tree (H,)
For any constants a > 0 and 0 < 1/2, if n > 8/c and Pa > 212. (a + 2) log n/nc,, then with probability at least 1 - 2n-
0. < ST S 0.5p.n3
and
Trev H, To) 2 (1-6) Tree (Ho To).
(6)
Proof idea (details in appendiz). We need to relate Trev(H, T) with Trev(H, To) for every tree H. Since, the revenue function is linear with respect to the observed triplets, E[Trev(H, T)] Ps Trev(H, To), where the expectation is with respect random observation of cach triplet pair in To. We use concentration inequalities to bound deviation from expectation, max [Trev H, T) - E(Trev(HHHT)
Although there are exponentially many H, one can note that, due to Theorem [ the deviation can be controlled by bounding the maximum deviation of the (?) AddS3 similaritics, max,<) (iij - B[ss]]]- For this we use, Bernstein inequality (for each sty) followed by union bound (over all i, Thus, we show that for any constant a > 0,
if Pn (a + 2) log n/n, then max Freu(H,T) Treu To) O VPPnn logn) with probability
7

---

Published in Transactions on Machine Learning Research (03/2023)
1--7 n Using concentration for both Hu, H, and noting that Treo(H, T) 2 Trev(Ho, T), we have that For stated condition on Pn: the second term is at least en 21 2(n"~=²-n) which is at least (1 e1 for 8/c. This follows since AddS3 similarities computed from To are of the form 8ij 2n + 2 3 Ho ( V j)l, and hence, we rewrite T Trev(Ho, To) in terms sizes of internal nodes. The lower bound follows from inductive arguments. Combining the lower bound with the deviation bound results in the theorem. The claim |T] = (p..n)) with probability 1 - n follows from E| Pal = ((p,n") and multiplicative Chernoff inequality.
Tre 2 Tre To) - -0 n log
Next, show that Trev To) 2 Pr
3
With Ps. fixed at the stated threshold, Theorem shows that, with probability 2n we can achieve (1 - -ppappooxiintoonn of triplet revenue using [T| = O(n logn/<²) triplets. The result Emamjomeh- Zadch and Kempe (2018) Proposition 2.2)-that that (2(n)) triplets are necessary to exactly recover Ho hinges on the fact that it is impossible to correctly guess the hierarchy the lowest level of the tree Ho using fewer comparisons. Since errors in the lowest level do not significantly affect Tree, can achieve the (1- approxiiooiinnnnnnnn in Theorem 3 However, note that H may not be efficiently computable as it requires exhaustive scarch over all trees. We discuss practical algorithms in the next section.
Theorem 3 is stated in the noiseless setting, where it is assumed that every observed triplet in T is correct. It natural to ask if Theorem 3 still holds under a noisy setting, where some triplets may be flipped with some probability. To formalise this, let T C To be a set of triplets obtained from the sampling procodure in Theorem 3 Let T' be construcled such that, for every (i, E T, T' contains (4.j, k) with probability 1 1- 6, (i, j) with probability 5. The random flipping of labels is independent for all (i. E T. We obtain the following corollary from minor modification of the above proof (details in appendix).
Corollary For any floed Ripping probability 5 E (0, 2) and for any a > and < e < 1/2,
max Trev(H,T) 2 (1 (1-c) Trev( To) with probability n na if n > 8/E and Pa > 222 logn H
(1-20-
6 Comparison-bast Algorithms for Hierarchical Clustering
The equivalence between comparison- baased revenues and Dasgupta's revenue, stated in Theorem ! implies that one may simply employ standard hicrarchical clustering algorithms using the pairwisc similarities AddS3 or AddS4, depending on whether one has access to triplets or quadruplets. This makes it possible to use the well-established literature on hierarchical clustering with pairwise similarities. In fact, mentioned before, previous works on passive comparison-baset hicrarchical clustering also follow this philosophy using other kind of pairwise similarities obtained from the comparisons (Kleindessner and von Luxburg 2017 Ghoshdastidar et al. 2019).. Unlike previons works, our use of AddS3 or AddS4 stems from a revenue maximisation formulation that allows us to consider an approach based on the average linkage (AL) clustering algorithm, that is, the following procedure:
AddS3-AL (or AddS4-AL)
Given. A set of triplets T (or quadruplets Q) on [r]]
Step 1.
Compute the pairwise similarity function AdaS3 (or AddS4) for every pair of objects
Step 2.
Run average linkage algorithm with AdAS3 (or s AdaS4)
Output. The tree dendrogram H the objects
Remark approximation guarantee. Average linkage enjoys theoretical guarantees under the as- sumption that the similarities are always positive. Moseley and Wang (211)) show that average linkage achieves a worst-case t-approximation for revenue maximisation. Unfortunately, this result does not readily extend to AddS3-AL and AddS4-AL, as these similarities may be negative in some cases. possible approach could be to add a positive constant to all the similaritics to ensure that they are positive. Although this does not change the optimal tree or the one obtained from average linkage, a 1 apappoxiiattion for the modified revenues (considering revised similarities) does not imply j-approximation for the original revenues.
8

---

Published in Transactions on Machine Learning Research (03/2023)
Based on the proof of Moseley and Wang (2017), one can show that AddS3-AL (or AddS4-AL) returns tree with non-negative triplet (or quadruplet) comparison revenue. Whether approximation guarantees may also be derived for AddS3-AL and AddS4-AL remains open.
7 Experiments
In this section, we propose two sets of experiments to demonstrate the practical relevance of our new revenue function and the corresponding algorithm. In our first set of experiments, our goal is to show the usefulness of revenue maximisation as a solution to find hierarchies that are closer to the ground truth, We consider planted model and demonstrate the alignment between AARI scores, supervised metric of goodness for clustering, and our proposed revenue function. In our second set of experiments, we aim to show that the heuristic proposed in Section 6 to maximize the revenue performs well in practice. On real datasets, we compare our approach to two different state of the art approaches in comparison- hicrarchical clustering.
7.1 Planted Model
In this first set of experiments, we study the behaviour of the proposed revenucs in a controllod sctting. Hence, we generate data using a planted model for comparison-based hierarchical clustering (Goshhdastidar ct al. 2019 and we use 3 triplets-based and 2 quadruplets-based based methods to learn dendrograms.
Data. To generate the data in this first set of experiments, use a standard planted model in comparison- based hierarchical clustering (Balakrishnan et al. 2011 Ghoshdastidar et al. 2019). Given n objects, we create a real similarity matrix S = (siy) Jig.jsnn such that 85 O and 8:y 8yz correspond to the similarity between objects i and j. We assume that (sij)iey are independent. Gaussians with 8ij ~ NNuuj, o²). The choice of μaj defines a planted hierarchy, a complete binary tree of height L, built on top of 2 ground clusters, that sets of no objects denoted as C2.,,...,Cczu The total number of points (leaves) in the complete hierarchy is thus n n²24, For every pair of objects i, that belong to the same ground cluster, a constant. On the other hand, for objects i, from two distinct clusters, if H(i j) is rooted at level L, we define pij μ (L 6)o. We observe that the tree is rooted at level-0 and the constants separation 8 and noise level conorlr the hardness of the problem. In particular, smaller values of 5 make the similarities between examples that belong to the same cluster more difficult. to distinguish from similarities between examples that belong to different clusters. The signal-to-non
Pij =
ratio thus A. In all the experiments, we set μ = 0.8, a = 0.1, 70- = 30, L and we vary E (0.02, 0.04, 0.2}. Since we are in a comparison-baseer based setting, we do not directly use the similarities of the planted model to learn dendrograms but instead generate comparisons. Given Talt and Qail the sets containing all possible triplets and quadruplets (see preliminaries), obtain T Ç Tall and Q C Qall by uniformly sampling kn² comparisons with k >>> 0.
Evaluation Function. To measure the closeness between the dendrograms obtained by the different ap- proaches and the ground truth trees, we use the Averaged Adjusted Rand Index (Ghoshdastidar et al. 2019). The AARI an extension to hierarchies of well-kuown measure in standard clustering called Adjusted Rand Index (ARI; see Hubert and Arabie 1985). The underlying idea to average the ARI obtained over the top L levels of the tree, This measure takes values in [0, 1] with higher values for more similar hierarchies, AARI of 1 implying identical trees. Our goal is to empirically verify that the hierarchics with higher revenues are the ones closest to the ground truths as indicated by a higher ARRI Indeed, this would show that our revenue function is appropriate to evaluate the goodness of a dendrogram and that maximizing the revenue is indoed a good unsupervisod way to seloct hierarchics. The results reported are averaged over 10 independent trials. We defer the standard deviations to the appendix for the sake readability.
Methods. We compare AddS3-AL and AddS4-AL, the two methods proposed in this work, to various comparison-based algorithms for learning dendrograms, such as 4K-AL (Ghoshdastidar et al.) 2019
"The code is available at https://github. http://sstubb..coo/ataaattt///// comm/jitaashii//keeeeee cwwprsanwe__oppaasnnnn...ee
"The randomness stems from three sources: the noise in the similarities, triplets selection, and the optimization procedure in 1.T.. We fix the seeds 0-9 the 10 runs.
9

---

Published in Transactions on Machine Learning Research (03/2023)
1eb
Comparison Revenue
AddS3-AL tSTE-AL
Add53-AL tSTE-AL MulK3-AL
MulK3-AL
0.6
AARI
0.4
1
0.2
0.0
0.2 0.4
0.6
0.8
1.0
1.2 1.4
1.8
2.0
0.2
0.4
0.6
0.8
1.2
1.4 1.6
1.8 2.0
Signal to Noise Ratio
Signal to Noise Ratio
Figure 1: Revenue and AARI (higher is better) of several triplets-based methods using n² comparisons. Given various signal to noise ratios, a higher revenue implies higher AARI values (better dendrograms).
Table 1: Revenue and AARI of various methods for fixed signal to noise ratio = 1.5 and varying number of triplets (decreased by factor of 2). The planted setting consists of total of n = 240 objects. In each line the highest revenue and AARI are underlined, taking into account standard deviation (see appendix). This shows that the two measures are well aligned.
Number of triplets
AddS3-AL
(STE-L
MulK3-AL
Revenue
AARI
Revenue
AARI
Revenue
AARI
16n.
7.347 x 10
0.937
7.300 x 107
0.877
7.315 x 107
0.861
8n
3.667 x 107
0.905
3.656 x 107
0.877
3.636 x 106
0.855
4n²
1.823 10?
0.862
1.825 x 107
0.874
1.795 x 107
0.830
2n²
8.962 x 106
0.782
9.130 x 106
0.867
8.444 x 106
0.677
n²
4.315 x 106
0.682
4.559 X 106
0.868
3.728 x 106
0.540
n²
2.038 x 106
0.593
2.277 X 106
0.860
1.220 x 106
0.347
12/44
9.268 x 10$ 0.498
1.137 X 106
0.851
1.531 x 10a
0.077
n2
4.261 x 105
0.396
5.728 x 105
0.840
1.856 x 104
0.011
n2 /6
2.015 x 105
0.295
2.858 x 105
0.720
4.026 x 103
0.005
n 1//
1.096 10a
0.192
1.450 X 10
0.549
2.015
103
0.003
snadrrpplessbbsse method, along with two triplets-based approaches MulK3-AL (KeeeKKlenee Kleindessner and von Luxburg. 2017 Perrot et al.] 2020) and uSTE-AL (Van Der Maaten and Weinberger 2012). The former two are similarity- based approaches where the idea is use the comparisons to learn a similarity. The latter is an ordinal embedding approach where the idea to recover a representation the data that respects the
(e;,,y) comparisons well possible, and then use the cosine similarity Sıy = ||>,|a|||>_||a to compare the examples. To learn the dendrograms then apply standard average linkage to the various similarities.
Results. In Figure 1 we present the AARI and Revenue of different triplet-based methods for several signal to noise ratios using n² comparisons We observe that, given set signal to noise ratio, the ordering between the methods remains the same for the revenue and the AARI, that is the method with the highest revenue is also the one with the highest AARI. In other words, a higher revenue indicates that the corresponding dendrogram is better. In Table [ we verify that this remains true for a constant signal to noise ratio of 1.5 and various number of observed comparisons. In particular, we notice that when revenue of AddS3-AL becomes higher than the revenue of tSTE-AL, that is using more than 4n² triplets, the AARI also follows the same trend, thus confirming that selecting the dendrogram with the highest revenue is indeed good
Note that we also considered other amounts of comparisons. However, the trends similar the ones observed here and thus chose defer these results the appendix.
10

---

Published in Transactions on Machine Learning Research (03/2023)
Table 2: Experiments on real datasets. For the triplets-based methods, AddS3-AL tends to obtain the dendrograms with the best revenues. For the quadruplets- approaches, AddS4-AL and 4K-AL obtain comparable results. Using the original Cosine similarities only yields slightly better hierarchies than the comparison-based methods. For first 3 datascts, multiple runs are used and standard deviation (sce appendix) is considered for highlighting the best method(s).
Triplet
Quadruplet
Dataset
AddS3-AL
tSTE-AL
MulK3-AL
Cosine-AL
AddS4-AL
4K-AL
Cosine-AL
Zoo
2.771x 105
2.144110'
2.041x10*
2.824x100 10
2.828 10a
2.866 x 10
2.945x 10a
Glass
2.161x 106
1.93x 10
1.412 106
2.110x 106
2.429 10
2.425 10
2.494 10
MNIST
1.893 10
2.061x109
1.724x109
2.064x 10
1.905 10
1.884x10 109
2.075x109
Car
1.521 x 10
1.562x10
1.264x10
1.521 x 10
1.125x 105
Food
6.137x100
5.993x10
6.096x10*
6.137 10
6.137x10
Vogue
2.7
2.104x10*
3.022x10*
2.722 10
2.549x
Nature
2.650x10a
2.056x105
1.231x10'
2.650 10
2.228x
Imagenet
7.179x107
6.571x10"
3.440x10*
7.179x10*
6.994x10*
way to select meaningful hierarchies. the appendix, we show that the same behaviour can be observed for various signal to noise ratios well as in the quadruplet case.
We further investigate the dependence between AARI and the triplet revenue in Figure] 2 where plot the AARI and the corresponding triplet revenue (in log scale) for different runs and number of triplets, considered in Table D1 Although the variation of the revenue for increasing AARI seems to depend on the mothod under consideration, all plots show a monotonic trend. To validate this we use two measures of rank correlation Kendall's-r and Spearman'st ssp that capture how well the dependence captured as monotonic function. For both AddS3-AL and MulK3-AL, the rank correlations are greater than 0.9, indicating a highly monotonic trend. Although the rank correlations are smaller for tSTE-AL, but still large enough and corresponding p-value is about 10-17, indicating rank correlation.
7.2
Real Data
The previous experiments establish that our revenue functions are good at identifying meaningful dendro- grais in an unsupervised way. In the following experiments, we investigate the behaviour of the proposed approaches on real data. In particular, show that they competitive with standard comparison-base hicrarchical clustering approaches on various datasets.
18
26-
15
12
13-
13
12
12
6.2
0.4
2.6
0.8
10
0.50
0.55 0.60
3.65 0.70 0.75 0.80
0.85
0.50
0.0
0.2
0.4
0.6
0.8
AAR
AARI
AARI
(a) AddS3-AL
(b) tSTE-AL
(c) MulK3-AN
(T 0.933, 0 0.992)
(T 0.583, p 0.764)
0.926, p 0.988)
Figure 2: Scatter plots for the AARI and triplet revenue from different runs and varying number of triplets in the setting of T The three methods (AddS3, (STE and MulK3) show different trends. However, in each case, the triplet revenue and AARI have high Kendall-r and Spearman-p correlation.
11

---

Published in Transactions on Machine Learning Research (03/2023)
Data. We consider 8 different datasets. On the one hand, we consider 3 stan- dard clustering datasets: Zoo, Glass, and MNIST (Heller and Ghahramani 2005 Le- Cun et al. 2010 Vikram and Dasgupla 2016). The Zoo dataset originally consisted of 101 animals each with 16 features. But we choose to remove the entry with class "girl' since we do not feel it belongs to the zoo dataset. The Glass dataset has 9 features for 214 examples. For the MNIST dataset we consider two subsets of the MNIST test dataset that originally contains 10000 exam- ples distributed among the len digits. A 2- dimensional embedding of the entire MNIST test data constructed with t-SNE (van der Maaten 2014 From this we randomly sampled 200 examples for each digit to form dataset of 2000 entries and normalized the embeddings so that each example lies in [-1, 1]. Since we are in comparison-bart based setting, we generate n² comparisons using the cosine similarity. To model mistakes from human annotators, we randomly and uniformly flip 5% of the comparisons (Emamjomeh- Zadeh Zadeh and Kempe 2018), where by flipping [t, k) we mean replacing with (i, j).). On the other hand, we consider 5 comparison- Vogue Cover, Nature Scene and ImageNet Images v0.1, from the cblearn repository The number of ob- jects and the kind of query used to obtain comparisons are summarized in Table 3 The comparisons are transformed into triplets (final number of triplets noted in Table 3), which are also used in the quadruplet setting. In Table 8 central triplet is query of the form-whit of the three objects (i.j.k) is most central. Provided that the answer is i, this implies object is more similar to both and k than they are to each other. Two standard triplets (j.i.k) and (k,i.j) are thus obtained. An Odd-out triplct is a query of the form-whidh of the three objects (i.j,k) is the odd one out. If i is picked as the odd one, gives two standard triplets of the form (j.k.i) and (kj..). A rank 2 from query of the form among objects (io...., rank the 2 that appear to be most similar to the reference object to- If i, and are ranked the most similar to in in this order, then 11 standard triplets of the form (io, &1 2 and (iu, b2 4x)2mm are obtained.
Table 3: Description of datasets used in the experiments.
Dataset
Query
# Objects
#Triplets
Zooo
Cosine Similarity
100
100000
Glass
Cosine Similarity
214
45796
MNIST
Cosine Similarity
2000
4000000
Car
Most Central Triplet
60
14194
Food
Standard Triplet
100
190376
Vogue
Odd-out Triplet.
60
2214
Nature Imagenct
Odd-out Triplet Rank 2 from 8
120
6710
1000
328549
datasets, Car, Food,
Evaluation Function. Since the datasots considered here do not come with ground truth hicrarchy, we cannot compute the AARI. Hence, we only report the revenue. The results reported are averaged over 10 independent trials"
p and defer the standard deviations to the appendix.
Methods. Besides the methods already used in the planted setting, we also consider the Cosine bascline where it is assumed that the pairwise cosine similarities are available, and apply average linkage directly the similaritics used to generate the comparisons. This bascline not applicable to the comparison- datasets where we only have access to the comparisons and not to the similarities.
Results. The results are reported in Table 2 We can notice that AddS3-AL tends to be better than tSTE-AL and MulK3-AL while AddS4-AL and 4K-AL are comparable. As is expected, the Cosine baseline based on the original similarities obtains the best performances in most cases, but it only seems to yield slightly better hicrarchies than the comparison-based methods. This would tend to confirm that hicrarchical clustering with average linkage is indeed a problem that can be solved using only limited number of comparisons, instead using all similarities.
https://github.com wtt.ssuuw..commeekeeaaaao wom.//okuunstee/ccleee.e
"The randomness from main sources: the triplets generation (in the Zoo, Glass, and MNIST datasct), the optimization procedure in 1STE (Initialization, batch selection). We fix the seeds for the runs. For all the other datasets and methods, every step deterministic and, thus, we only need report the results single run.
12

---

Published in Transactions on Machine Learning Research (03/2023)
8 Conclusion
In this paper, we proposed novel revenue functions that allow to measure the goodness of dendrogram in an unsupervised way using only triplet or quadruplet comparisons. This suggest natural algorithms for hierarchical clustering based on the maximization of such revenues. Drawing theoretical connections with existing work on cost and revenuc functions in standard hicrarchical clustering, we propose two algorithms based on average linkage for hierarchical clustering using only comparisons. We empirically show that our revenue functions successfully identify the dendrograms that are closest the ground truth. We also show that the proposed approaches to learn hierarchics perform well on real datasets and competitive with state of the art methods.
We further used the proposed revenue function to resolve an open theoretical problem of recovering a latent hicrarchy using fewer than ((n²)) passive triplcts. We showed that O(n log n/c²) passive triplets suffice to obtain a (1 -approoppooiiitoooon of the optimal triplet revenue. We conclude with the following open questions: (i) Are Q2n2 log n) passive triplets necessary for a (1 - <-aapproximation?
(it) At this point, we are unable to obtain a polynomial-time approximation scheme (PTAS) for the revenue maximisation problem, but we believe this should be possible. It may also be possible to obtain more efficient algorithms that are linear in time with respect to the number of triplets. A linear-time method exists for maximum quartet consistency (Snir and Yuster 2011
Acknowledgments
The work of A. Mandal was supported by the German Academic Exchange Service (DAAD) through the Working Internships in Science and Engincering (WISE) scholarship The work of D. Ghoshdastidar is partly supported by the German Research Foundation through the DFG-ANR PRCT "ASCAT" (GH 257/3-1).
References
E. N. Adams I11. Consensus techniques and the comparison of taxonomic trees. Systematic Biology, 21(4): 390 397, 1972.
S. Agarwal, J. Wills, L. Cayton, G. Lanckrict, D. Kriegman, and S. Belongic. Generalized non-metric multidimensional scaling. In Arlificial Intelligence and Statistics, pages 11-18. PMLR, 2007.
V. Aho, Y. Sagiv, G. Szymanski, and D. Ullman. Inferring a tree from lowest common ancestors with an application the optimization of relational expressions. SIAM J. Comput., 10(3))405-44) 421, 1981, doi: 10.1137/021000
S. Balakrishnan, M. Xu, A. Krishnamurthy, and A. Singh. Noisc thresholds for spectral clustering. Advances in Neural Information Processing Systems, 24:954 962, 2011.
K. S. Berenhaut, K. E. Moore, and R. L. Melvin. A social perspective on perceived distances reveals deep community structure. Proceedings of the National Academy of Sciences, 119(4))e0003631119, 2022.
J. Byrka, S. Guillemot, and J. Jansson. New results optimizing rooted triplets consistency. Discret. Appl. Math., 158(11):1136 1147, 2010. doi: 10.1016/j. 0at.m.20000..000
Catanzaro. The minimum evolution problem: Overview and classification. Networks, 53(2):112 125, 2009. doi: 10.1002/net. 200800.
M. Charikar, V. Chatziafratis, and R. Niazadeh. Hierarchical clustering better than average-linkage. In T. M. Chan, editor, Proceedings of the Thirtieth Annual ACM-STAM M Symposium Discrete Algorithmms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2291 2304. SIAM, 2019. doi: 10. 1197/1.9781611195549..919
V. Chatziafratis, M. Mahdian, and S. Ahmadian. Maximizing agreements for ranking, clustering and hi- erarchical clustering via. MAX-CUT. Tn A. Banerjee and K. Fukumizu, editors, The 24th International
13

---

Published in Transactions on Machine Learning Research (03/2023)
Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Re- search, pages 1657-1665. PMT.R, 2021.
V. Cohen-Addad, V. Kanade, F. Mallmann- Frenma, and C. Mathieu. Hierarchical clustering: Objective functions and algorithms. Journal of the ACM (JACM), 66(4):1-42, 2019.
S. Dasgupta. cost function for similarity- based hierarchical clustering. In Proceedings of the Annual CM Symposium on Theory of Computing, STOC '16, page 118-127, New York, NY, USA, 2016. Association for Computing Machinery. doi: 10. 1115////87111117777555 URL httpp:://dii.org////// 11445 0197518.2897522
Ellis, B. Whitman, A. Berenzweig, and Lawrence. The quest for ground truth musical artist similarity. In Proceedings of ISMIR, 2002.
E. Emamjomeh--Zadeh and D. Kempe. Adaplive hierarchical clustering using ordinal queries. In Proceedings SIAM, 2018.
of the Twenty-Nine Anmual ACM- SMMM Symposium on Discrete Algorithms,, pages
L. Foulds, M. Hendy, and D. Penny. A graph theoretic approach to the development of minimal phylogenetic trees. J. Mol. Evol, 13:149, 1979.
D. Ghoshdastidar, M. Perrot, and U. Luxburg. Foundations of comparison-based hierarchical clustering. Advances in Newral Information Processing Systems, 32:7456 7466, 2019.
S. Haghiri, Ghoshdastidar, and U. von Luxburg. Comparison-based nearest neighbor search. In Artificial Intelligence and Statistics, pages 851 859. PMLR, 2017.
S. Haghiri, F. A. Wichmann, and U. von Luxburg. Estimation of perceptual scales using ordinal embedding. Journal of vision, 20(9):14 14, 2020.
H. Heikinheimo and A. Ukkonen. The crowd-median algorithm. In First AAAI Conference on Human Computation and Croudsourcing, 2013.
K. A. Heller and Z. Ghahramani. Bayesian hicrarchical clustering. In Proccedings of the 22nd international conference Machine learning, pages 297-304, 2005.
L. Hubert and Arabie. Comparing partitions. Journal of classification, 2(1):193-218, 1985.
M. Janowitz. Monotone equivariant cluster methods. SIAM Journal on Applied Mathematics, 37(1):148 165, 1979.
M. F. Janowitz. Mathematical Taronomy. Wiley Series in Probability and Mathematical Statistics. Wiley, 1971. ISBN 978-0471440505,
T. Jiang, P. E. Kearney, and M. Li. A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. STAM J. Comput., 30(6):1942-190))))) 2000. doi: 10.1137/ $0097539799361683,
E. Kazomi, L. Chen, S. Dasgupta, and A. Karbasi. Comparison based learning from weak oracles. In International Conference on Artificiol Intelligence and Statistics, pages 1849 1858, 2018.
M. Kleindessner and U. von Luxburg. Kernel functions based on triplet similarity comparisons. In Advances in Neural Information Processing Systems, pages 6807 6817, 2017.
Y. LeCun, C. Cortes, and C. Burges. Mnist handwritten digit database, 2010.
B. Moseley and J. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-
means, and local search. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnelt, editors, Aduances in Newral Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017.
M. Perrot and U. von Luxburg. Boosting for comparison-based learning. In IJCAT, 2019.
14

---

Published in Transactions on Machine Learning Research (03/2023)
M. Perrot, P. Esser, and D. Ghoshdastidar. Near-optimal comparison based clustering. In Advances in
Newral Information Processing Systems, volume 33, pages 19388-19399) Curran Associates, Inc., 2020.
C. Semple and M. A. Steel. Phylogenetics, volume 24. Oxford University Press Demand, 2003.
R. N. Shepard. The analysis of proximities: Multidimensional scaling with an unknown distance function. i.
Psychometrika, 27(2):125 140, 1962.
Sibson. Order invariant methods for data analysis. Journal of the Royal Statistical Society: Series B (Methodological), 34(3):311-333 338, 1972.
S. Snir and Rao. Quartets maxcut: divide and conquer quartets algorithm. IEEE ACM Trans. Comput. Biol. Bioinform., 7(4):704-718, 2010. doi: M.1109/TCBB.2008
S. Snir and R. Yuster. A linear time approximation scheme for maximum quartet consistency on sparse sampled imputs. STAM J. Discret. Malh., 25(4):1722 1736, 2011. doi: 10.1137/110820555. URL https: 7/doi 1ttp:/or//11..117111188..
Stewart, G. D. Brown, and N. Chater. Absolute identification by relative judgment. Psychological review, 112(4):881, 2005.
Ukkonen. Crowdsourced correlation clustcring with relative distance comparisons. 2017 IEEE Inter- national Conference on Data Mining (ICDM), pages 1117-1129 TEEE, 2017.
L. van der Maaten. Accelerating t-sme using tree-based algorithms. Journal of Machine Learning Research, 15(93):3221 3245, 2014. URL http://jmlr. http:://ju....oorpppperrrrrreee http:////aaaee//////////aaaaaaaa
html html
L. Van Der Maaten and K. Weinberger. Stochastic triplet embedding. In 2012 IEEE International Workshop on Machine Learning for Signal Processing, pages 1 1-6. IEEE, 2012.
L. C. Vankadara, S. Haghiri, F. U. Wahab, and U. von Luxburg. Large scale ordinal embedding: training neural networks with structure-free inputs. arXio preprint, arXiv:1912.01663 2019.
S. Vikram and S. Dasgupta. Interactive bayesian hicrarchical clustoring. In International Conference Machine Learning, pages 2081 2090. PMLR, 2016.
D. Wang and Y. Wang. An improved cost function for hierarchical cluster trees. Journal of Compulational Geometry, 11(1):283-33) 331, 2020. doi: 10.20382/jocg..1iin vl
M. Wilber, S. Kwak, and S. Belongie. Cost-effective hits for relative similarity comparisons. In Human Computation and Crowdsourcing (HCOMP), Pittsburgh, 2014.
B. Y. Wu. Constructing the maximum consensus tree from rooted triples. J. Comb. Optim., 8(1):29-39, 2004. doi: (0002///BJCC00.00000113333 04215.66..........
15

---

Published in Transactions on Machine Learning Research (03/2023)
A Proof of Theorem
Recall the formulation of Trev for tree H and set of triplets T:
Tree(H, H, T)
Σ
HoSMET
-
(sum over all distinct i, k.)
i.j.k
Σ
(H 5)l
Σ
AGA.ner
Σ ((iV
(by change of variable between j and k in the first term.)
[((AJ))TT ((. (((v
Σ
E
TRLKJETT ((.AA)TT + TUAAEET - TUARETT
Ki
(by change of variable between i and j when > j.)
Adds3
H(V
by definition of AddS3 This concludes the proof for the triplets-based revenue. Using similar approach, recall the formulation of Qree for tree H and quadruplet set Q:
Qreu H, Q)
Σ IG i
(H(KVII)- (H(V))))
[e Σ [(
(sum over all i j. < 1, (1,5) # (k:)).)
Σ (auu)eelH(ii))) H(V - Σ ((JADE
(by swapping the role of i, and k, in the first term.)
TaNissEe TUSANEE) HH(
st
Adds H(v
by definition of s Adds4, This concludes the proof for the quadruplets-based revenue.
Proof of Proposition
The proposition follows immediately from the following two lemmas. Lemma 5. Let Ho be binary tree on [n] and To be the set of triplets induced by Ho. Then
To mag T),
(7)
where the marimum is unique over all triplet sets that induced by some binary tree on [n]. Lemma Let Ho, H2 be two binary trees on [n] and To, Tr be the set of triplets induced by Ho and H1, respectively- Then Treu(Ho, (Ho, Ti) Treu( (H1, To)-
16

---

Published in Transactions on Machine Learning Research (03/2023)
Combining the above two lemmas, obtain that
Trev Ho; To) > Trev Ti) Trew (i,To) To)
for any tree H1 and corresponding set of triplets Ti. This directly implics the Proposition 2 complete the proof by proving Lemmas and G
We now
Proof of Lemma 5 Recall that
Hoo To)
E (6...JTT
[Ho((V - Hol v 5)
Do(....)
is a sum of positive terms. For convenience, we denote each difference by Do(i, 00
Let Ti be the set triplets generated by another tree H1. Note that at least one pair of triplets Ti has to be different from To, otherwise H1 and Hg would be isomorphic transformations of one another. Without loss of generality, assume that the pair (i,j, k), (f.i, k) has been replaced by the pair (i, j),, (k, i, that is, k merged in H1 before they are merged to j. Observe that can write
Tree Ho, To) Trev Ho. TT) =
E Do(i,j,)) Dolí,i,)) Do(i,k,j) Du(k, 2,5)
(....),
(1,k.)
TTaTT
where cach term in the summation can be computed
Do(i.j,b) + ko Do(i, k,j) Do(k,i,j)
|Holi V +)]+ Hol v A)] 2l -H i)l [o)( 2( -2(6(0)))
=)D,
which is strictly positive for every (i,j, k) E To- Summing over all Trev(H, (Ho, To) > Trev(Ho, T1) for any Ti generated by another tree H1.
E ToXTi, we have that
Proof of Lemma D Let {sok) Jig be the pairwise AddS3 similarity induced by To, and fsigths be the AddS3 similarity from TI. Due the definition of To, we note that, for any & + i,j, the term (T(a, I(A.)) + TG,,)))TT ((..)))) either takes the value 2 if k & (IV that is, i.j is merged in Ho before k-or the value -1 if & is merged to either i before (i V j). Summing over all k i,j gives
806j 2(n Hol v 2iI (1 v f)l - 2) 2n + - Ho v)
for every i.j. Using the same arguments Stij can be expressed as Sıúj = 2n + 3| (iV 5))- We can now use the equivalence in Theorem D
to write
Trev( (o, Ti) - Trev(H, Ta) = Σ
11y Ho(i Ho
i
=- Σ(
2
(2n (2m+2 + 3|Ho( =3
-2n + 2)
Σ
((6 -
i<j
which is zero, since Σ Ho(i Σ
Hivi = (n² nn) is Dasgupta's cost for any tree on [n] when
all pairwise similarities
Dasgupta
2016
Theorem 3). Hence, the claim.
17

---

Published in Transactions on Machine Learning Research (03/2023)
C Proof of Theorem 3 and Corollary 4
We first state and prove two lemmas that are essential for the proof of Theorem The first lemma shows that Trev( (Ho To) ((n*). The second lemma derives concentration inequalities for the AddS3 similarities Sij, which is then used in the proof of Theorem 3 to derive bound on [Trev(HH, T) - Trev(H, To)l for all H, and subsequently arrive at the claim.
Lemma 7. Given (0,1) 1) and n 2 8/e, the following holds. If Ho is a hierarchy on [n]] and To is the sel of triplets induced by Ho:
Trev (rev(Ho To) 2 (1 (1-s)m²
12
Proof. We start with the equivalence in Theorem 1 to write the revenue as Trev Ho. 10j--Eie 800 (oV j)l, where Soij is the pairwise AddS3 similarity induced by To- Due the definition of To, we note that, for any l # i, the term (T(.,,,)TT (a..TTTTT -'...,))TTT (IAA)))))))) either takes the value 2 if k & (iV that is, i is merged in Hg before or the value -1 if k is merged to either or j before (iV Summing over all k + i gives
806 = 2(n - (Ho(i - (I v f)i - 2) = 2n + HoH v)
for every i,j. Let N ()V denote the least common ancestor of j in Ho, and N1, N2 be the two children of N. Note that |Ni] [N2] pairs of j.j are merged at N. Hence,
rewrite the revenue
Trev(Ho: To)
Σ s2g
soij Ho(i
Σ
Holi v (3 (3 j)l 2n 2)
Kj
Σ
[N [22 |N] (3)N1 - -2n 2
NeHo
Σ
N N2 - -(2 + 2)
Σ NEHo
|2
=
NeHo
where the summations are over all internal nodes the tree Ho, with N1, N2 deenoting the two children of N. The second summation is Dasgupta's cost. for any tree on [n] with all pairwise similarities 1, and evaluates to x² x²-n Dasgupta, 2016 Theorem 3). On the other hand, we claim that the first sum has lower 3
bound Σ |N NEHa
We prove this claim through induction on n. The claim is easy to verify for n 2,3. For 4, we assume that claim holds for any Ho with & leaves, when & < (oquivalently, Ho on [K]). Consider the tree Ho in] such that the root node is split into two nodes of size nı, n2 (note nı + n2 n)). From our inductive hypotsesis,
+ nt + n1
Σ |N
2 ningn
4
4
NEH Hd
1
4 (4nimny 8nin2 + 444nnnn n + nt + n²)
1
n
2 (n) + +22)a=
4
4
which proves the claim for any Combining all terms, we have
3n (2m + 2)( n)
n 2
Treu(Ho, To) 2
(n3 n² - n))
4
3
12 3
Now, given 6 (0, 1), notice that (n² n n)
c for any 2 which proves the lemma. T2
18

---

Published in Transactions on Machine Learning Research (03/2023)
We now state and prove the concentration results for the AddS3 similarity computed from the sampled triplet set T. We first recall the sampling and introduce some notations. For any with probability Pn. E (0, 1), a pair of triplets (i, (i,, E To is included in T, independent of other pairs. To formalise this, we define the random variable Xijk = Xjik ~ Bernoullipp.) such that the collection {Xiik : & i,j) are mutually independent. If Sy denotes the pairwise AddS3 similarily, computed using T, then observe that
8ij = Σ
XisaHHosAAeTT - (o....TT + UUAAE 4g...TT)) K
(8)
Hence, for fixed Ho- and To- the similaritiy Siz is weighted sum of independent Bernoullis, with weights either 2 -1 (ef. proof of Lemma 7 As consequence, E[sty] Pnosoij, where the expectation is with respect to sampling, and furthermore we can state the following concentration for all pairwise similarities.
Lemma 8. Assume n 2 8. Let T denote a random subset of To (obtained from the aforementioned sam- pling), and (ssties, {suis hies denote the pairwise AddS3 similarities computed using triplets in T and To. respectively. For any a > 0, Pn > (a + 2) log n/n, then with probability 2n 2n
Pan
nn
S T
<
and max sy Sos 54v + n) log iej
10
2
Proof. We first derive the bound on max |iy Pnigl From the expression of 8ij, mentioned above, we note zcj that 8t Susy is sum of 2) independent mean zero random variables, with each term in [-2, 2] and variance bounded by 4pn- By Bernstein's 's inequality,
P([sij Pnsoiil 5) S 2 exp (- 8pn (n - 22)
8²
For any 0, if Pv. (a + lognn/ and setting 8 4V(la + 2)p,, n, we have Sijj Pv Pn.j
4 4v(a (a + 2)p,n n with probability I 2n 2n-(2, Using union bound over all < n²/2 pairs of i,j. we have that max [s;) Suij exceeds the claim bound with probability S n no
To derive the bound on [T), we first bound [Tl. From definition of To, every internal node N Ho contributes WM/IN22((1)) 2) triplets to To since merger of every i,j contributes to |N 2 triplets, one for each k that is either merged with or j at a lower level. Hence,
n1. - Σ IN 2 Σ |N
2. n2
n1
3n2²
Too = Σ |N - 2) NEHL
3
2
3
NEH.
NEHo
The first summation follows from Dasgupta 2016 induction with hypothesis that the sum evaluates to n² 22/2. We now note that [[[T]] = Pol and apply
Theorem 3), whereas the second sum follows from
multiplicative Chernoff bound get that 2 < IT| S 3pulTol with probability 1 2c P., Tol/12 To simplify the terms, use TTol to the bounds on [T], whereas for the probability, note that 2e --.17ol/122 < 2n (a+2) < n -", where the first inequality follows using [To| 2 n² n2/5.pm (a + 2) log n/n and 2 8.
3nn [5 7 where the lower bound holds for 2 8. This leads
Below, we prove Theorem 3 using Lemmas
7
Proof of Theorem We first derive bounds on the deviation of the revenue Tree of any tree H due sampling. The concentration of (sijiicj ensures that we state deviation bound that uniformly holds
19

---

Published in Transactions on Machine Learning Research (03/2023)
for all H, shown below. From the equivalence in Theorem
we write for any H,
[Tee(H, T) P. Prevre,H, To)l =
Σ
8ig Pn
( 5)
i<j
8ij - Snijl | 3)1
< 4 (a + 2m log n
Hiv
where the last bound holds with probability 1-n due to Lemma 8
Note that Σ ((v is Dasgupta's
cost of tree H on [n] if all pairwise similarities are 1, and hence the summation is n'-n n 3.
We conclude
that, with probability n na
max
(T) - P.TrreuH,,T)) (4/3) (a 2)pmn logn.
We now write
4
(a + 2)m² log
Trev(H, To)
2 Treu H,T)
Pn
3
Pn
1 Trev Ho, T) (a + 2)n² logn
8
(a + 2)n² log
2
2 Tree Ho, To)
3
Pn
Pn
Pn
where the first and third inequalities follow from the deviation bound stated above, and the second inequality
holds since H maximises Trev(H,T) T). For Pn > 2a + 2) log n/ne?, the second term is smaller than
en /24 & <(1 e)n²/11 < TTrev Ho, To), where the first inequality uses the fact S 1/2 and the second inequality is due to Lemma 7 Hence the claim.
Proof of Corollary 4 In the noisy setting, the random flipping be modelled through the independent variables {G} i,j < k} where Sj ~ Bernoull(d) is the indicator for triplet (i.j, to be flipped with
triplet (i, j)- Using the notation of equation 8 the variable EogCEx indicates (i, (. T (noisy triplet)
whereas Eifk (1 - (ik) indicates correct triplet (1, ET. Hence,
Sij = Σ (1 2TA [(AJ))T) + Xijx(1 - 2CHh) Tg...))T.)
(9)
Kit
and [[s;y] = (1 - Sn. Following the arguments of Lemma
we can that, with probability 1 - n
max Si - (1 22))) < 4/ (a + nogn KJ
where the deviation bound same as in Lemma since the same variance bound holds for the independent random terms in the summation in equation Subsequently, following the proof of Theorem have with probability n
max Trev (1 (1-25)p. Treu H, To) (4/3) (a 2) logn.
and so
1 Treu H, T)
4
(a + 2)n² log
Hr, H, To) 2
(1 26)pm
3(1 (()) |
Pn
1 Trev(Ho: T)
4
(a 2)n logn
(a + 2)n² log
3(1 - 26) V
Trev(Ho, To)
(1 26)pn
Pn
3(1 28)
Pr
Following the proof of Theorem 3 second term is ent/ /24 for pn,
2 222 logn
ne (1-28)
20

---

Aosine-AL Published in Transactions on Machine Learning Research (03/2023)
D Standard Deviation on Real Data
In Table we provide the standard deviations for the real data experiments that were omitted in the main paper.
Table 4: Experiments on real datasets. For the triplets- based methods, AddS3-AL typically obtains den- drograms with the best revenues. For the quadruplets- based methods, AddS4-AL and 4K-AL show similar results. Using Cosine similarities yields slightly better hierarchies than comparison- methods.
Triplet
Datasct
Ad
tSTE-AL
MulK3-AL
Cosine-AL
Zoo
2.77 108 = x 10a
2.16 10a 8 10a
2.04 10a = 10
2.82 10th = x 10
Glass
2.16 10 + x 101
1.97 x 10 +3 10a
1.41 10t + 5 10
2.11
10
+2 10
MNIST
1.89 10 # x 107
2.06 x +40 10?
1.72 10" = 107
2.06 10
22 106
Car
1.52 x 10a
1.56 x 10 10
1.26 x 10
Food
6.14 x 106
5.99 x 12 104
6.10 x 106
Vogue
2.72 x 104
2.10 x 10 +1x 10
3.02 x 103
Nature
2.65 x 10a
2.06 x 10 1 10a
1.23 X 105
Imagenet
7.18 x 107
6.57 x 10 + 10
3.44 107
Quadruplet
Datasel
AddS4-AL
4K-AL
Zoo
2.83 x 106 1 X 10a
2.87 x 109 + x 10
2.95 x 10 + x 10
Glass
2.43 X 10
3 x 104
2.43 x 10 +
10a
2.49
10 + 1 10t
MNIST
1.91 x 10
x 107
1.88
10
+ 3 107
2.08 10 # 10
Car
1.52 105
1.13 105
Food
6.14 x 106
6.14 106
Vogue
2.72 X 104
2.55 X 10a
Nature
2.65 x 105
2.23 x 105
Imagenet
7.18 x 107
6.99 x 107
E
Additional Results on the Planted Model
In this section, we provide additional results on the Planted Model presented Section 7.1 of the main paper. In Figure 3 we present the results obtained n²/2, n² and 2n² triplet comparisons respectively. Similarly, Figure 4 displays the results obtained using n²? n2/2, n² and 2n² quadruplet comparisons respectively. In all these figures, notice that, given set signal to noise ratio, the ordering between the methods remains the same for the revenue and the AART, that is the method with the highest revenue also has the highest. AARI. In other words, a higher revenue indicates a better dendrogram!
In Table 5 we verify that this remains true for constant signal to noise ratios of 1.5, and halving mumber of comparisons (Table 1 an abbrieved version of Table 5). The highest revenue and AART are underlined. We can notice that, when the revenue of AL becomes higher than the revenue of uSTE-AL, the AARI also follows the same trend, thus confirming that selecting the dendrogram with the highest revenue is indeed good way to select meaningful hierarchies.
F Results on the Planted Model with Noisy Comparisons
In the main paper, we only used the planted model to generate comparisons with no noise. In this section, we show that our findings remain true even when some of the comparisons are noisy, that is randomly
Tn Figures current time seeds for random numbers for each run.
21

---

Published in Transactions on Machine Learning Research (03/2023)
flipped with probability of 5%. In Figure present the results obtained using n²/2, n² and 2n noisy triplet comparisons respectively. In Figure 6 present the results obtained using n² n² and 2n noisy quadruplet comparisons respectively. We notice that, given a set signal to noise ratio, the ordering between the methods remains the same for the revenue and the AARI, that is the method with the highest revenue is also the one with the highest AARI In other words, a higher revenue indicates a better dendrogram.
Table 5: Revenue and AARI of various methods for a signal to noise ratio of 1.5 and halving of comparisons. each line the highest revenue and the highest AARI are underlined, showing that the two measures are well aligned.
Number of triplets
Ad
tSTE-AL
Revenue
AARI
Revenue
AARI
16n
7.347 x 10 + 1.3 x 10
0.937 + 0.024
7.300 x 10 8.7 x 10a
0.877 0.007
Sn
3.667 10" 105
0.905 = 0.020
3.656 x 10 8.8 10*
0.877 0.007
4n²
1.823 1.0 105
0.862 0.023
1.825
10 7.0 104
0.874 = 0.012
2n
8.962 x 10 +.8 x 104
0.782 0.042
9.130 x 10 +.0 104
0.867 0.014
n²
4.315 x 10 19.77 X 10a
0.682 : 0.047
4.559 x 10t +.0 104
0.868 + 0.012
n²
2.038 x 10t 6.8 x 10*
0.593 + 0.087
2.277 X 10t 1.4 x 104
0.860 = 0.014
n²
9.268 x 109 +.2
104
0.498 + 0.035
1.137 X 10 + 1.0 x 104
0.851 0.065
18/8
4.261 x 10 + 2.5
104
0.396 + 0.033
5.728 x 10 6.2 x 10
0.840 0.010
n 2/616
2.015 x 10 + 1.2
104
0.295 + 0.041
2.858 x 10 3.3 10a
0.720 0.057
n² n2/32
1.096 10S + 8.5 103
0.192 0.057
1,450 10 + 2.2 10a
0.549 0.025
Number of triplets
MulK3-AL
Revenue
AARI
16n
7.315 x 107 1.3 10a
0.861 + 0.005
8n?
3.636
10 9.7
104
0.855 + 0.003
4n²
1.795
107
104
0.830 + 0.009
2n²
8.444
106 1.3
105
0.677 + 0.041
n²
3.728 x 106 + 1.4
10a
0.540 0.016
n n//2
1.220 x 10
103
0 0.050
n
1.531 x 1.9 1
0.077 0.047
n n²/8
1.856 x 10' x 104
0.011 1011000 0.011
1² 1/
4.026 x 10 +.0 10a
0.005 0.004
n²
222
2.015
10a 3.5
103
0.0003 0.001
22

---

Published in Transactions on Machine Learning Research (03/2023)
1e6
Comparison Revenue
AddS3-AL LSTE-AL
0.8
AddS3-AL tSTE-AL
2.0
MulK3-AL
MulK3-AL
0.6
1.5
AARI
1.0
0.4
0.5
0.2
0.0
0.0
0.2
0.6
0.8
1.0
1.2
144 1.6
1.8
2.0
0.2
0.6
0.8
1.0
1.2 1.4
1.6
1.8
2.0
Signal to Noise Ratio
Signal to Noise Ratio
(a) Revenue (x2/2)
(b) AARI (n²/2)
1e6
Comparison Revenue
AddS3-AL AL tSTE-AL Mulk3-AL
0.8
AddS3-AL
tSTE-AL
Mulk3-AL
0.6
AARI
0.4
1
0.2
0.0
0.2
0.4
1.0 1.2 1.4 1.6
1.8
0.2
0.6
0.8
1.2 1.4 1.6
2.0
Signal to Noise Ratio
Signal to Noise Ratio
(c) Revenue (n²)
(d) AARI (n²)
166
Comparison Revenue
Add53-AL tSTE-AL MulK3-AL
0.8
Add53-AL tSTE-AL
8-
Mulk3-AL
0.6
AARI
2
0.2
0.0
0.4
0.6
1.0 1.2 1.4 1.6 1.8
2.0
0.6
0.8
1.4
Signal to Noise Ratio
Signal to Noise Ratio
(e) Revenue (2n²)
(f) AARI (2ne²)
Figure 3: Reverne and AARI (higher is botter) of several triplets- based methods using respectively n²/2 comparisons (a-b), n² comparisons (c-d), and 2nd comparisons (e-f). Given various signal to noise ratios, a higher revenue implies higher AARI values, that is better dendrograms.
23

---

Published in Transactions on Machine Learning Research (03/2023)
1eb
Comparison Revenue
AddS4-AL 4K-AL
2.00
AddS4-AL
0.6
1.75
4K-AL
0.5
1.50
AARI
0.4
1.25
1.00
0.3
0.75
0.2
0.50
0.1
0.00
0.0
0.2
0.4
0.8
1.0
1.2
1.4
1.6
1.8
2.0
0.2
0.4
0.8
1.0
1.2
1.4
1.6
1.8
2.0
Signal to Noise Ratio
Signal to Noise Ratio
(a) Revenue (x22/)
(b) AARI (2²)2)
166
Comparison Revenue
0.7
Add54-AL 4K-AL
4.0
AddS4-AL
4K-AL
3.5
3.0
0.5
AARI
2.5
0.4
2.0
0.3
1.5
0.2
1.0
0.5
0.1
0.0
0.0
0.4
0.8
1.2
1.4
1.8
0.2
0.8
1.2
1.4
1.8
Signal to Noise Ratio
Signal to Noise Ratio
(c) Revenue (n
(d) AARI (n²)
1c6
Comparison Revenue
Add54-AL 4K-AL
0.8
Add54-AL 4K-AL
8-
0.7
0.6
6-
AARI
0.5
0.4
4
0.3
0.2
0.1
0.0
0.2
1.6 Signal to Noise Ratio
0.6
1.0 1.2
2.0
0.2
0.4
0.8
1.2
1.4
1.8
2.0
Signal to Noise Ratio
(e) Revenue (2n²)
(f) AARI (2re²)
Figure 4: Revenue and AARI (higher is better) of several quadruplets-based methods using respectively n²/2 comparisons (a-b), n² comparisons (c-d), and 2nd comparisons (e-f). Given various signal to noise ratios, a higher revenue implies higher AARI values, that is better dendrograms.
24

---

Published in Transactions on Machine Learning Research (03/2023)
Comparison Revenue
AddS3-AL tSTE-AL
0.8
AddS3-AL tSTE-AL
2.0
MulK3-AL
MulK3-AL
0.6
1.5
AARI
1.0
0.4
0.5
0.2
0.0
0.0
1.0
1.6
2.0
0.6
1.2 1.4
1.8
2.0
Signal Noise Ratio
Signal to Noise Ratio
(a) Revenue (n² (2)
(b) AARI (n²
0.8
AddS3-AL
tSTE-AL
Comparison Revenue
4-
AddS3 AL
(STE-AL Mulk3-AL
0.6
MulK3-AL
AARI
0.2
0.0
0.2
0.6
0.8 1.0 1.2 144
2.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
1.6
1.8
2.0
Signal to Noise Ratio
Signal to Noise Ratio
(c) Revenue (n²²
(d) AART (m²)
Comparison Revenue
Adds3-AL
8
AddS3-AL -LL tSTE-AL
0.8
tSTE-AL
MuIK3-AL
MuiK3-AL
0.6
6-
AARI
4-
0.4
2
0.2
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4 1.6 1.8
2.0
0.2
0.4
1.4 1.6 Signal to Noise Ratio
0.6
0.8
1.0
1.2
1.8 2.0
Signal to Noise Ratio
(e) Revenue (2n²)
(I) AARI (2re*)
Figure 5: Revenue and AARI (higher is better) of several triplets- based methods using respectively n²/2 comparisons (a-b), n² comparisons (c-d), and 2n² comparisons (e-f) with 5% noise. Given various signal to noise ratios, higher revenue implies higher AARI values, that is better dendrograms.
25

---

Published in Transactions on Machine Learning Research (03/2023)
1eb
Comparison Revenue
AddS4-AL 4K-AL
2.00
AddS4-AL
0.6
1.75
4K-AL
0.5
1.50
AARI
0.4
1.25
1.00
0.3
0.75
0.2
0.50
0.1
0.00
0.0
0.2
0.4
0.8
1.0
1.2
1.4
1.6
1.8
2.0
0.2
0.4
0.8
1.0
1.2
1.4
1.6
1.8
2.0
Signal to Noise Ratio
Signal to Noise Ratio
(a) Revenue (x22/)
(b) AARI (2²)2)
166
Comparison Revenue
0.7
Add54-AL 4K-AL
4.0
AddS4-AL
4K-AL
3.5
3.0
0.5
AARI
2.5
0.4
2.0
0.3
1.5
0.2
1.0
0.5
0.1
0.0
0.0
0.4
0.8
1.2
1.4
1.8
0.2
0.8
1.2
1.4
1.8
Signal to Noise Ratio
Signal to Noise Ratio
(c) Revenue (n
(d) AARI (n²)
1c6
Comparison Revenue
Add54-AL 4K-AL
0.8
Add54-AL 4K-AL
8-
0.7
0.6
6-
AARI
0.5
0.4
4
0.3
0.2
0.1
0.0
0.2
1.6 Signal to Noise Ratio
0.6
1.0 1.2
2.0
0.2
0.4
0.8
1.4
1.8
2.0
Signal to Noise Ratio
(e) Revenue (2n²)
(f) AARI (2n²²)
Figure 6: Revenue and AARI (higher is better) of several quadruplets-based methods using respectively n²/2 comparisons (a-b), n² comparisons (c-d), and 2n² comparisons (e-f) with 5% noise. Given various signal noise ratios, higher revenue implies higher AARI values, that is better dendrograms.
26


Reviews:
[{"review_id": "wob1WuyEkl", "reviewer": "Reviewer_Te1E", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is generally well-written. The idea is very clear. The authors also do a good job to position this work in the context of related works, so the contributions are also presented clearly. \n2. The notations and derivations are good and rigorous. I have roughly gone through the proof. \n3. The experiments are extensive including synthetic datasets and real datasets, which demonstrates the effectiveness of the proposed revenue function. \n\nWeaknesses:\n1. The biggest weakness is the theoretical side of the algorithm for this revenue function. Although the sample complexity O(n^2 log n) has been proved to achieve good approximation, no poly-time approximation algorithm is provided for this revenue function.\n2. There are some typos. Some parts of the paper are not self-contained. I will list some of them in \"Requested Changes\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new revenue function for comparison-based hierarchical clustering. There are many good theoretical contributions including the equivalence between the proposed function and Dasgupta's cost function, and provably approximate recovery of the hierarchy based on O(n^2 log n) sampled comparisons based on the proposed function. Evaluation on real datasets also reveals the effectiveness of the proposed function. Overall, I think this work makes valid contributions to the research on hierarchical clustering. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In sec 5, when T0 is defined, it is unclear \"i,j are merged before k\". \"merged\" is not defined. Suggest using a more formal way to define this. \n\n2. Typo in the last line of the proof sketch for Prop.2: H! should be H1. \n\n3. Real data experiments: To make the paper self-contained, I suggest adding descriptions of how the hierarchical structure is formulated rather than \"use the same pre-processing...\". \n\n4. Please explain why the proposed algorithm is worse than tSTE-AL when the number of comparisons is less than 6n^2. ", "broader_impact_concerns": "I see no ethical concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8hRi016Qn7", "reviewer": "Reviewer_EQsT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* This is a very clearly written paper that provides an accessible and seemingly comprehensive description of the landscape of related work and where the proposed objective and algorithms fit in. \n* The algorithms, while simple, are clearly motivated by the setting and serve for an empirical comparison to validate the algorithms and proposed objective. \n* The authors provide connections between related algorithms, objectives and settings that are nice and could help inspire future work connecting these related areas. \n\n**Weaknesses**\n* I think the paper could benefit from a bit more discussion of: how comparison-based data comes to be and further discussion of considerations for such data. What is the scale of such datasets? What is the purpose of clustering in the example datasets (e.g., data exploration, some end-task, etc)? What are the characteristics of the clusterings desired for such data? Speed, accuracy, guarantees about the solution? The paper does a nice job placing itself in the related literature, I think it would benefit from this further discussion of the data.\n* Similarly, I think it would be good to discuss the use of agglomerative clustering further, especially in relation to highly scalable variants such as those that operate on sparse graphs, e.g., [1,2] among others.\n\n[1] Sumengen, Baris, et al. \"Scaling hierarchical agglomerative clustering to billion-sized datasets.\" arXiv preprint arXiv:2105.11653 (2021).\n\n[2] Dhulipala, Laxman, et al. \"Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth.\" arXiv preprint arXiv:2206.11654 (2022).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies hierarchical clustering in the comparison-based setting. That is rather than have direct access to pairwise similarities, we only have triplet (i more similar to j than k) or quadruplet comparisons (i and j more similar to each other than to k and l). The paper introduces an objective for comparison-based hierarchical clustering that is closely related to Dasgupta's cost. Furthermore, it presents principled algorithms along with an empirical comparison of these methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I only have a few minor writing comments:\n\nMinor:\n* \"In the past decade, there has been an exponential growth in the scope of data science and machine learning.\" -> Personally, I think this reads as too broad a statement. I think that stronger engagement from the reader would be to lead with the \"crowdsourcing and psychometrics\" use case and give both applications of these and impacts of those applications as you do in the following paragraph.\n* \"those focusing on ordinal data analysis from crowd-sourced data Kleindessner and von Luxburg (2017); Ghoshdastidar et al. (2019).\" -> citation parens\n* \" we believe that our revenue maximisation formulation can recover the latent hierarchy using only O(n^2 log n) comparisons under their latent model.\" -> would be nice to say a bit more here, perhaps turning it into a proper result (or describing more for future work).", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4weRazNk5C", "reviewer": "Reviewer_etdf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS\n\n1) The problem is well-motivated. Several works exist that study comparison-based clustering, yet I am not aware of a measure of cluster quality that is defined in terms of comparisons.\n2) The contributions are mostly clear and understandable.\n3) The results and definitions are nicely connected to their related counterparts (e.g., Dasgupta's cost function for hierarchical clusterings).\n\nWEAKNESSES\n\n1) The work suffers from lack of formality and rigor in several points. This includes some sloppy or incomplete definitions, some slightly wrong formulation of hypotheses, and some slightly wrong formulation of bounds and results.\n2) The sketches of the proofs are really too short, to the point that they do not manage to convey the idea, and therefore in the end they become quite useless.\n3) The experimental part can be improved. On the one hand, there is no clear statement of what the whole experimental part is supposed to assess (the individual experiments are described, but here I'm talking about the general goal of the experiments). On the other hand, some experiments are not very solid and seem almost anecdotal (more about this below).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces a measure of quality for hierarchical clusterings on a set of objects. The novelty of this measure is that, instead of being based on pairwise similarities $s(A,B)$ between objects, it is based on comparisons of the kind \"is $s(A,B)>s(A,C)$?\". This is interesting since several clustering algorithms that are based on comparisons rather than similarities have been proposed; human themselves are often better at performing comparisons rather than providing similarities. After defining such a measure of quality, called revenue, the work relates it to other known cost functions and proves some interesting results. For instance, they prove that one can compute a hierarchy that has revenue within constant factors from the optimum if one samples roughly $O(n^2)$ of the $\\Omega(n^3)$ possible triplets comparisons. The work is completed by some experiments that assess the effectiveness of the proposed measure in capturing the quality of a hierarchical clustering.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "CRITICAL CHANGES\n\nPage 5: \"We propose to achieve this by finding a tree that maximises $Qrev(H, Q)$\", how do you guarantee that in such a tree $|H(k \\vee l)| > |H(i \\vee j)|$? for all $(i,j,k,l) \\in Q$? Moreover, the inequality could be loose (i.e., $|H(k \\vee l)| = |H(i \\vee j)|$).\n\nPage 6: \"one cannot exactly recover $H_0$ from any passively obtained $T \\subseteq T_0$ if $|T| = o(n^3)$\", this sentence is vague and unclear. \n\nPage 6: \"$i,j$ are merged before $k$\", although I understand what is meant, there is no formal definition of what \"merged before\" means; and I do not think one can say \"$i,j$ are merged before $k$\" but rather \"$i,j$ are merged before $i,k$ and $j,k$\"\n\nPage 6: \"we obtain that $Trev(H_0, T_0) > Trev(H_0, T_1)$\", couldn't this be an equality?\n\nPage 7: \"One can use standard concentration inequalities to show that, with high probability, $|T| = O(p_n n^3)$\". This is true only if $p_n$ is large enough. In particular it is false if $p_n = n^{-3}$, since in that case $E[|T|]$ is too small to yield concentration.\n\nPage 7, Theorem 3: \"Given access to $T$\", this has no meaning here.\n\nPage 7, Theorem 3: \"with probability at least $1-n^{-O(1)}$\", probably you want to say $1-n^{-a}$ where $a>0$ can be made arbitrarily large by adjusting the constants. Otherwise that $O(1)$ could be $0$, in which case you get the trivial lower bound of $0$. In fact I would suggest defining formally what you mean by \"high probability\".\n\nPage 7, Theorem 3: \"Setting $p_n$ at its smallest allowable value, equation 5 holds for $|T| = O(n^2 \\log n / \\epsilon^2)$\". Do you mean that, for that value of $p_n$, with high probability we have simultaneously $|T| = O(n^2 \\log n / \\epsilon^2)$ and equation (5)? I guess this is the intended meaning, but one could interpret that sentence differently -- for instance, that conditioned on the event $|T| = O(n^2 \\log n / \\epsilon^2)$ we have (5) with high probability. In any case, the sentence is missing some quantifiers and/or some probability.\n\nPage 8: what do you mean by \"ideal\" matrix? I have not heard this before.\n\nPage 8: so what objects are R,M precisely? Real symmetric matrices? This should be stated clearly and formally.\n\nPage 8: \"there are $2^L$ pure clusters\", what is a cluster, and what is a pure cluster?\n\nPage 9, Table 1: this experiment does not tell much. First, the range of values for the number of comparisons is rather small. I guess it would be better to test, say, from k=n/2^c to k=n in doubling steps. This would support the claim that your revenue is correlated with the AARI. Second, this test is basically anecdotal evidence. Better evidence would be given by computing some standard measure of correlation between revenue and AARI such as Pearson's correlation between the revenue and AARI sequences, or Spearman's rank correlation between the rankings of the hierarchies given by the revenue and the AARI for the various methods.\n\nPage 10: the results are not easily repeatable since the authors used the current time to seed the random number generator (why not use just 0 as the seed?). \n\nPage 10: the denominator of the cosine similarity should have the norms, and not the squared norms\n\nPage 11: as before, these experiments are not repeatable since the authors used the current time to seed the random number generator.\n\nLemma 6: the statement is problematic as it first chooses $n, H_0, T_0$ and then makes a \"universal\" claim about all such choices. Consider rewriting it like this: \"For every $\\epsilon \\in (0,1)$ there exists $n_0 > 0$ such that what follows holds for all $n \\ge n_0$. If $H_0$ is a hierarchy on $[n]$ and $T_0$ is the set of triplets induced by $H_0$, then ...$\"\n\nLemma 7: first, the $O(1)$ at the exponent of $n$ is not what you want, as I remarked above. Second, if you aim at $1-n^{-a}$ for arbitrarily large $a > 0$, then the hypothesis $p_n = \\Omega(\\log n / n)$ is not sufficient; you need the stronger hypothesis $p_n > c \\log n / n$ for sufficiently large $c > 0$.\n\n\n\n\nORDINARY CHANGES\n\nPage 3: \"optimmisation\" --> \"optimisation\"\n\nPage 3: \"an uniformly\" --> \"a uniformly\",  \"are\" --> \"is\"\n\nPage 3: \"at least $\\frac{1}{3}$-fraction of given triplets\" --> \"a fraction at least $\\frac{1}{3}$ of the given triplets\"\n\nPage 3: \"that satisfy at least $(1-\\epsilon)$-fraction\" --> \"that satisfy at least a $(1-\\epsilon)$-fraction\"\n\nPage 3: \"given quartets\" --> \"the given quartets\"\n\nPage 4: \"Since, we show that\" --> \"Since we show that\"\n\nPage 4: \"we believe that ...\": I do not understand this sentence; do you prove this is true, or what?\n\nPage 4: \"$C_1$ and $C_2$, denoting a split of $C$ such that ...\" Why not just say that $\\{C_1,C_2\\}$ is a partition of $C$? Moreover, shouldn't the partition be nontrivial, i.e., $\\min(|C_1|,|C_2|) > 0$ ?\n\nPage 4: \"..., or equivalently, the number of objects in the set $C$\". I see no constraint in the definition that ensures that $|H(C)|=|C|$.\n\nPage 4: \"the number of objects in the set $C$\", why not just $|C|$?\n\nPage 4: \"the smallest node in the tree and the smallest subtree containing both i and j\" --> \"the smallest node in the tree containing both i and j, and the smallest subtree containing both i and j\"; otherwise it's ambiguous.\n\nPage 4: \"that allows ones\" --> \"that allows one\"\n\nPage 4: \"o(n)\" --> \"o(\\cdot)\"\n\nPage 4: \"achieves $Drev(H, s) \\ge \\frac{1}{3}$-optimal revenue\", what does this mean?\n\nPage 5: \"avoids counting the same comparison multiple times\", what does this mean? I see no \"counting\" problem here.\n\nPage 5: \"in practice, the observed comparisons are fewer\", in practice where? Moreover, this claim does not seem to be supported (there is no justification or citation).\n\nPage 5: \"We further assume that $T$, or $Q$, is passively collected -- the algorithm cannot decide which comparisons should be queried.\", I am confused. What can the algorithm do? Query any triplet from $T$ where $T$ is an arbitrary subset of $T_{all}$?\n\nPage 5: \"which leads to $|H(i \\vee k)| > |H(i \\vee j)|$\", you mean that you would like this to hold for every $(i,j,k) \\in T$?\n\nPage 5, Theorem 1: perhaps highlight in the notation that $s^{AddS3}$ is a function of the set of triplets $T$. Otherwise the right-hand side of the first equation looks independent of $T$, which is weird.\n\nPage 5, Theorem 1: need brackets in the right-hand side of the equation of $s_{ij}^{AddS3}$ \n\nPage 6, Theorem 1: need brackets in the right-hand side of the equation of $s_{ij}^{AddS4}$ \n\nPage 6: \"$Trev(H!,T_0)$\"\n\nPage 7: \"that $\\Omega(n^3)$ is necessary\" --> \"that $|T| \\in \\Omega(n^3)$ is necessary\"\n\nPage 8: \"experimentsto\"\n\nPage 8: \"triplets based\" --> \"triplets-based\",  \"quadruplets based\" --> \"quadruplets-based\"\n\nPage 8: \"$M+R$ where,\" --> \"$M+R$, where\"\n\nPage 8: \"to be more difficult\" --> \"more difficult\"\n\nPage 8: \"comparison based setting\" --> \"comparison-based setting\"\n\nPage 8: \"well known measure\" --> \"well-known measure\"\n\nPage 8: \"higher revenues imply higher AARI\", you mean AARI against the optimal hierarchy?\n\nPage 9: \"several triplets (a-b) and quadruplets (c-d) based\" --> \"several triplet-based methods (a-b) and quadruplet-based methods (c-d)\"\n\nPage 10, Table 2: \"triplets based\" --> \"triplet-based\",  \"quadruplets based\" --> \"quadruplet-based\"\n\nPage 10: \"in this work to various\" --> \"in this work, to various\"\n\nPage 10: \"quadruplets based\" --> \"quadruplet-based\",  \"triplets based\" --> \"triplet-based\",  \"similarity based\" --> \"similarity-based\"\n\nPage 10: \"we can then use\" --> \"and then use\"\n\nPage 11: \"comparison based\" --> \"comparison-based\"\n\nPage 11: \"we randomly and uniformly flip 5% of the comparisons (Emamjomeh-Zadeh and Kempe, 2018), for example if one should observe the triple $(i, j, k)$ that is object $x_i$ is closer to $x_j$ than to $x_k$ then one observes $(i, k, j)$ instead\", perhaps I would say \"we randomly and uniformly flip 5% of the comparisons (Emamjomeh-Zadeh and Kempe, 2018), where by flipping $(i, j, k)$ we mean replacing it with $(i, k, j)$.\"\n\nPage 11: \"The number of objects, the kind of query\" --> \"The number of objects and the kind of query\"\n\nPage 11: it is not clear what kind of comparisons the real-data datasets contain, and how they are converted into triplets/quadruplets. For instance I wonder what the \"most central triplet\" is. I believe this should be explained in the main body of the manuscript.\n\nPage 12: \"two average linkage based algorithms\" --> \"two algorithms based on average linkage\"\nProof of Theorem 1, Lemma 4, Lemma 5, Lemma 6, ... : the hierarchies $H$ are sometimes called \"hierarchies\", sometimes \"binary trees\", sometimes \"trees\".\n\nLemma 6: what is a \"latent\" hierarchy? It seems to me that it has no mathematical meaning.\n\n", "broader_impact_concerns": "I see no concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After some revisions during the review process, the paper is now clearly written and would be a valid contribution to TMLR.
Decision: Accept (poster)