Learning-Augmented Hierarchical Clustering
Authors: Vladimir Braverman
Jon C. Ergun
Chen Wang
Samson Zhou
Venue: ICML 2025 poster (2025)
Keywords: hierarchical clustering
learning-augmented algorithms
Primary area: theory
TL;DR: We gave hierarchical clustering algorithms with learning-augmented oracles with bounds overcoming known hardness results.

Abstract: Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recursively partition a dataset into a tree-like structure while grouping together similar data points at each level of granularity. Unfortunately, for many of the proposed HC objectives, there exist strong barriers to approximation algorithms with the hardness of approximation. We consider the problem of hierarchical clustering given auxiliary information from natural oracles in the learning-augmented framework. Our main results are algorithms that, given learning-augmented oracles, compute efficient approximate HC trees for the celebrated Dasgupta's and Moseley-Wang objectives that overcome known hardness barriers.

Learning-Augmented Hierarchical Clustering
Vladimir Braverman 123 Jon C. Ergun
Chen Wang 25 Samson Zhou
Abstract
the "correct" number of clusters in flat clusterings is often difficult question that is the focus of a sequence of works dating back to the 1950s (Thorndike, 1953). In hierarchical clustering, there is no fixed number of clusters that needs to be determined in advance. Another advantage of hier- archical clustering is that the dendrogram simultancously captures structure at all levels of granularity, whereas flat clustering does not identify further structure inside each of the clusters. Hence, hierarchical clustering arises in various applications where data exhibits hierarchical structure, such as biology and phylogenetics (Sneath et al., 1973; Sotiriou et al., 2003), image and text analysis (Steinbach et al., 2000), and community detection (Leskovec et al., 2020).
Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recur- sively partition a dataset into a tree-like struc- ture while grouping together similar data points at each level of granularity. Unfortunately, for many of the proposed HC objectives, there exist strong barriers to approximation algorithms with the hardness of approximation. We consider the problem of hierarchical clustering given auxiliary information from natural oracles in the learning- augmented framework. Our main results are al- gorithms that given learning-augne augmented oracles, compute efficient approximate HC trees for the celebrated Dasgupta's and Moseley-Wang objec- tives that overcome known hardness barriers.
Despite a wealth of heuristics for both agglomerative bottom-up (Ward Jr. 1963) and divisive top-down ap- proaches (Guénoche et al., 1991), formal mathematical un- derstanding of hierarchical clustering often stagnated due to the absence of well-posed objectives until a relatively recent work by Dasgupta (Dasgupta, 2016). Subsequently, addi- tional objectives (Moseley & Wang, 2017; Cohen-Addad et al., 2019) were proposed to quantify the performance of dendrograms with n leaves, so that high-revenue similarity trees and low-cost dissimilarity trees correspond to desirable hierarchical partitions of the dataset.
1. Introduction
Hierarchical clustering (HC) a popular data analysis tech- nique that recursively partitions dataset throughout tree- like structure, that similar data points are grouped to- gether at different levels of granularity. Specifically, the input is set of n data points and a measure of similarity or dissimilarity between the points, which induces a weighted graph whose vertices represent the data points and whose edge weights represent the pairwise measure between the vertices. The output is a binary dendrogram, which is a rooted tree whose leaves represent the individual data points and whose internal nodes each represent cluster of the data points in its subtree, thus providing a hierarchical represen- tation of relationships within the dataset.
For a number of these objectives, various algorithms have been proven to achieve specific approximation guarantees. For example, a divisive clustering algorithm based on the sparsest cut subroutine was shown to give an O( n) approximation (Charikar & Chatziafratis, 201 7b; Cohen- Addad et al., 2019; Deng al., 2025) for Dasgupta's 's ob- jective (Dasgupta, 2016), while the long-used agglomer- ative heuristic was shown to give a 2-approximation for the dissimilarity objective proposed by (Cohen-Addad et al., 2019) and a a a-pproxximation for the similarity objective pro- posed by (Moseley & Wang, 2017), i.e., the Moseley- -ang (MW) objective. These objectives were further explored in the contexts of better approximation factors (Chatziafratis et al., 2020b; Alon et al., 2020), sublinear computation mod- els (Rajagopalan et al.. 2021; Assadi et al., 2022; Agarwal et al., 2022), and graphs with special properties (Charikar et al., 2019b; Manghiuc & Sun, 2021).
Hierarchical clustering has several advantages over flat clus- terings such as k-means or k-median, where the dataset is partitioned into a fixed number of clusters. For example,
Alphahetical order of author names. Johns Hopkins University 2 "Rice University 'Google Research *Carnegie Mellon University Teexs A&M University. Correspondence to: Vladimir Braverman vova @aa@@ee mova@ccsjhu.cee pe..sh..eduu... Jon C. Ergun <ergunjonO@@ gmail.com>> Chen Wang <ehen. wang.researcch @ gomi. Samson Zhou <amsonnzouuee gmail.com>.
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Unfortunately, (Charikar et al., 2019a) showed that average- linkage cannot do better than - aappproximation for the for-

---

Learning-Augmentedd Hierarchical Clustering
mer objective or better than J-approximation for the lat- ter. More general hardness of approximation results were given, showing the impossibility of achieving roughly 1.003- approximation (Chatziafratis et al., 2020a) for dissimilarity under the Unique Games Conjecture and the impossibility of achieving (1 - apprroxxxiatoonn for the Moseley-Want objective (Chatziafratis et al., 2020b) under the Small Set Expansion hypothesis, for fixed constant C > O. More- over, for the Dasgupta objective, (Charikar& & Chatziafratis, 2017a; Roy & Pokutta, 2017) showed that under the Small Set Expansion hypothesis, there is no constant approxima- tion in polynomial time for any constant. Thus, we seek new practical approaches that enable better approximation guar- antees without assumptions about the underlying dataset or weight function.
ysis. Furthermore, for graph-base problems, recent results by (Cohen-Addad et al., 2024; Braverman et al., 2024; Dong et al., 2025) have shown that natural acles could help overcome NP-hardness constraints as well. We thus ask whether machine learning models can be used to provably improve (graph-based) hierarchical clustering.
or-
1.1. Our Contributions
In this paper, we consider the problem of hierarchical clus- tering given a possibly erroneous oracle that uses auxiliary information, e.g., through clusterings of similar datasets, to provide local information about the relationship between queried data points. In particular, we consider splitting or- acle that, on an imput query of triplet (u, v, w) of vertices, outputs the vertex that is first separated away from the other two with respect to an optimal or near-optimal hierarchical clustering tree. In other words, if the oracle is consistent with some ground-truth tree, it will output the vertex that is not in the same subtree as the other two vertices, under their least common ancestor. We remark that such oracle advice is natural due to the plethora of machine learning models that are trained on related instances of graphs, where the triplet relationships are already labeled.
eearning-augmented algorithms. We draw inspiration from the recent advances in the predictive capabilities of machine learning models. On one hand, datasets often have additional auxiliary information that can be used to im- prove algorithmic performance if accurate. For example, in many applications, the input dataset can retain insight- ful patterns exhibited by similar datasets generated from previous instances. On the other hand, machine learning models lack provable guarantees and can result in wildly in- accurate predictions when generalizing to unfamiliar inputs (Szegedy et al., 2014). Nevertheless, algorithms (Mitzenmacher& & Vassilvitskii, 2020) that over- come worst-case computational limits have been designed for a number of applications, such as warm-starts for faster algorithms (Dinitz al., 2021; Chen al., 2022c; Davies et al., 2023), data structures optimized for specific query distributions (Kraska et al., 2018; Mitzenmacher, 2018; Lin et al., 2022; Fu et al., 2025), online algorithms with some "forecast" of the future (Purohit et al., 2018; Gollapudi & Panigrahi, 2019; Lattanzi et al., 2020; Wang et al., 2020; Wei & Zhang. 2020; Bamas et al., 2020; Im et al., 2021; Lykouris
Using triplet split-away information is common in the litera- ture, and there have been results explored in similar settings, e.g., tree reconstruction with accurate triplet relationships given (Aho et al., 1981), triplets are given as constraints (Chatziafratis et al., 2018), noisy triplet information with fresh randomness (Emamjomeh-Zzadeh & Kempe, 2018 8), and algorithms with quartet information (Jiang et al., 2000; Snir & Yuster, 2011; Alon et al., 2014). Furthermore, the reconstruction of phylogenetic CSPs, which provides an oracle with a similar form to ours, is an extensively studied line of work (see, e.g., (Chatziafratis & Makarychev, 2023)). From the machine learning perspective. it is possible to learn such oracles in the PAC learning framework (see Appendix J for details).
augmented
& Vassilvitskii, 2021; Aamand et al.. 2022: Anand et al., 2022; Azar et al., 2022; Grigoreseu et al., 2022; Khodak et al. 2022: Gupta et al., 2022; Jiang et al., 2022; Antoniadis et al., 2023; Shin et al., 2023; Benomar & Perchet, 2023), input-sensitive sketches for more space-efficient streaming algorithms (Hsu et al., 2019; Indyk et al., 2019; Jiang et al., 2020; Chen et al., 2022b;a; Li et al., 2023), and classical NP hard problems (Braverman et al., 2024; Cohen-Addad et al., 2024; Braverman et 2025).
In line with existing literature on Geaming--uggment al- gorithms, we investigate a stochastic and independently responding splitting oracle, where randomness is introduced only once. Specifically, this implies that the oracle correctly responds with a probability of for some constant p >>>> 1/2, independently across vertex triplets. Additionally, repeated queries of the same triplet consistently yield the same (pos- sibly erroneous) responses, which rules out basic boosting strategies such as repeatedly making the same query to the oracle. We remark this splitting oracle mirrors numerous machine learning models that are trainable with data yet exhibit inherent noise.
For clustering problems. (Frgun et al., 2022; Nguyen et al., 2023; C. S. et al., 2024) introduced flat clustering algo- rithms that use polynomial runtime and achieve approxima- tion guarantees beyond NP hardness limits. Though their techniques are specific to k-means and k-median clustering, their work nevertheless serves as an important conceptual message that demonstrates machine learning oracles can be used to improve upon traditional techniques for cluster anal-
We now present our main results for learning- augmented hierarchical clustering, We first show that for the Dasgupta objective, we can use such a splitting oracle to achieve a
2

---

Learning-Augmentte Hierarchical Clustering
constant factor approximation in polynomial time.
size as large as O(n²), the time complexity in Theorem 3 is near-linear in the worst case.
Theorem 1. There exists algorithm that, given weighted undirected graph G = (V, w) and split- ting oracle O with high probability, in polynomial time and O(n") queries computes a hierarchical clustering tree ' such that costa(T) I O(1) OPTD) (G), where OPT (G) is the cost the optimal hierarchical clustering tree T*, i.e., OPT (G) = costa((*))
Finally, we observe that our algorithms possess favorable properties that are extremely amenable to sublinear algo- rithms. As such, we can obtain the following results in the streaming and parallel computation (PRAM) settings.
Theorem 4. In the single-pass graph streaming and the PRAM settings, there exists:
By comparison, (Charikar& & Chatziafratis, 2017a; Roy & Pokutta, 2017) showed that there is no polynomial-time algorithm that could achieve any constant approximation to Dasgupta's objective, under the Small Set Expansion hypothesis. Hence, Theorem illustrates that the power of a splitting oracle can used to break complexity hardness limitations. On the other hand, we remark that the runtime of the algorithm of Theorem 1, although polynomial, is perhaps embarrassingly large. We thus give an algorithm that uses the splitting oracle and Ónn²) time to achieve approximation guarantees beyond the current state-of-the- art oblivious algorithms.
a single-pass (dynamic) streaming algorithm that, given a weighted undirected graph G (V, E, w) in a voly(n)-length dynamic stream and an offline splitting oracle O with high probability, uses On-log" n) bits of space and polynomial time computes hierarchical clus- tering tree T such that cOsta(T) S 0(1) OPT (G) (Theorem 21).
PRAM algorithm that, given a weighted undirected graph G = (V, E, w) and a splitting oracle O with high probability, in O( fin2-poly polylog n) work and log" n depth computes a hierarchical clustering tree T such that rev 2 o(1) -OTTMMPMMMMM (G) (Theorem 22).
There exists an algorithm that, given a weighted undirected graph G= (V, (V,E,w) w) and splitting oracle O. with high probability, in On log n) time and Onn)) queries computes hierarchical clustering tree T such that CTS S OVIlog log n). OPT (G), where OPT (G) the cost of the optimal hierarchical clustering free T Le., OPT (G) = (T
Theorem 2.
Our results in the sublinear settings similarly outperform the state-of-the-art in the HC algorithms without oracle advice. For instance, in the single-pass graph streaming setting, (Assadi et al., 2022; Agarwal et al., 2022) designed semi-streaming algorithms with (1) approximation but exponential time. By comparison, our algorithm only uses polynomial time, leveraging the advantage of the splitting oracle.
By comparison, the best-known polynomial-time oblivious algorithm achieves O(y (oo n) apprrxxxxaaaon (Charikar & Chatziafratis, 7b; Cohen-Addad al., 2019). Thus our algorithm that achieves O /og log n) approximation gives very competitive practical bounds- the improvement of our algorithm is approximately 2.3 times better for = 10
2. Preliminaries
We present the definition of the hierarchical clustering prob- lem, our splitting oracle model, and the HC objectives in this section.
Turning our attention to the Moseley- Wang objective, we similarly show that a splitting oracle can also be used to achieve any constant factor approximation in polynomial time.
2.1. The hierarchical clustering problem
We consider the hierarchical clustering problem with a split- ting oracle O. The hierarchical clustering problem is defined as follows. We are given n-vertex weighted undirected input graph G = (V, E, w), and our goal is to produce a binary tree TT whose root node corresponds to the vertex set V and the leaves represent the singleton vertices. The vertices set contained the internal nodes form a Laminar set family: suppose node x has children (g, it represents split S. - Sz), where S. Sy J S_. In this work, we assume without loss of generality 2 200 log n the bound holds for any 2 2500, and if n is a constant we can simply use brute-force algorithm.
Theorem 3. There exists algorithm that, given weighted undirected graph G EV,E,u) E, w) and splitting oracle O, with high probability, in O(n², polylog n) time and (n²) queries computes a hierarchical clustering tree T such that (T) 2 (1 - -o))) OPT (G), where OPTMW (G) is the revenue of the optimal hierarchical clus- tering tree T i.e., OPTMW (G) = (T*)
We note that (Chatziafratis et al., 2020b) showed the APX- hardness of the (1 C) approximation for Moseley-Want objective under the Small Set Expansion hypothesis, for a fixed constant C E (0, 1). As such, Theorem 3 again also shows the power of splitting oracles to overcome impos- sibility barriers. Since a n-vertex graph could have input
Hierarchical clustering trees only define a data structure, and there are many ways to construct "valid" HC trees.
3

---

Learning-Augmented Hierarchical Clustering
What eventually matters is to construct "good" HC trees notion that does not have a universal way to define. Popular approaches include heuristics, which work well subjectively but lack formal guarantees, and objective functions, which provide rigorous frameworks to study the optimal trees and the approximation algorithms. In recent years, the latter approach has attracted considerable attention with popular objective functions by (Dasgupta, 2016; Moseley & Wang, 2017; Cohen-Addad et al., 2019).
definition is given as follows.
Definition 6 (The splitting oracle for hierarchical clustering).
Let G = (V, F)) be a n-vertex graph, and let T be the optimal hierarchical clustering tree of G. The oracle O V x V x V - V is a function that upon being queried with a triplet of vertices (u, E w), responds as follows
with probability p. the correct answer on which vertex splits away from the two others in T
Notation. For each internal node I in T. we use leavesy[=] to denote the leaves in the induced subtree of x. Each internal node of an HC tree can be described by lowest common ancestor (LCA) of vertices. For two vertices (u, v) on the leaves of T,, we use LCAT(U, v) to denote the node that is the lowest common ancestor of u and v. We can further generalize this notion to set of vertices, i.e., for set X - V, the node LCAT (X) refers to the lowest common ancestor of all vertices in X. For a set X, we call the induced subtree Tx maximal subtree of 'T if 1eavess] [ (X)] = X, ie., the lowest common ancestor of X in Tx induces all leaves of X in T.
with probability (1 - p). arbitrary (adversarial) an- swer on which vertex splits away from the two other vertices.
The randomness is taken independently over all the queries and is fixed across different queries on the same triplet. We assume each query to the oracle takes (1) time.
Assuming the correct probability of oracle is some con- stant p > 1/2 is very common in the literature, especially for graph problem (Braverman et al., 2024; Cohen-Addad et al., 2024; Dong et al., 2025). For the convenience of presentation, we assume p = TO in this paper, and we provide a discussion about general success probabilities in Appendix I.1. Observe that by the fixed randomness for each triplet, there are at most (?) many answers that O can have. This setting rules out trivial algorithms that simply
ret r be the root of hierarchical clustering tree T, and for any internal node z, we let disty(r, x) be the number of edges on the shortest path between r and x. We say node x on level 1evely(2) (x) is a higher level node than node with level level7 (y) in T if disty (r, x) > dist (r: y)- For two internal nodes æ and y in T, we use x = pa (y) to denote the relationship of x being the parent node of
get the correct by querying multiple times and boosting the success probability.
y. Note that if r = pa (y), automatically implies that Levell(y) ( + 1.
Several hierarchical clustering objectives are proved to be hard approximate in polynomial time under very plausible complexity assumptions. As such, our goal is to explore whether can obtain better approximation guarantees with the splitting oracle.
The split-away vertex. Note that in any hierarchical clus- tering tree, if we look at triplet of vertices (u, w), there must exist a vertex that split away from the two others in the optimal tree T i.e., two vertices with a LCA that is same as the LCA of all three vertices in T* Formally, for a triplet of vertices (u, u, w), we define "w splits away from (u, r)" as follows.
2.3. Objective functions for hierarchical clustering
We introduce the objective functions for hierarchical clus- tering we are going to discuss in this paper. These in- clude the Dasgupta minimization (cost) objective (Dasgupta, 2016) and Moseley- Moseley-Wangg maximization (revenue) objective (Moseley & Wang, 2017). We start with the minimization objective as prescribed by (Dasgupta, 2016).
Definition 5 (Split-away vertex). Let G = (V,E, E, w) be n-vertex graph, and let T be the optimal HC tree for G. Given a triplet of vertices (u, u, w). we say w splits away from (u, u) (in T*) if LCAp- (w, u) (resp. LCAy- v)) is equal to LCAT (fu, 0, w)).
Problem 1 (HC under Dasgupta's s cost function). Given n-vertex weighted graph G = (V, E, w) with vertices corresponding to data points and edges measuring their similarity, create a rooted tree T whose leaf nodes are V. The goal is to minimize the cost of this tree T defined as
2.2. The splitting oracle model
We study the hierarchical clustering problem with a natural oracle advice model. In particular, we assume an oracle O: V X Vx V- + V that takes a triplet of vertices (u, v, w), probabilistically correctly returns the vertex that "split away" from the other two vertices in the optimal tree'. The formal
costa(T): = Σ
w(e) (reavesy[LCAycee u)]l,
e= (u.D)E
(1)
We provide discussion for splitting oracles with approxi- mately optimal HC tree in Appendix 1.2.
where [leaves([ICAr(u ]] is the number of leaf- nodes in the sub-tree of TT rooted at the lowest common
4

---

Learning-Augmentedd Hierarchical Clustering
ancestor of and v. We use OPT denote the cost of optimal HC tree under Dasgupta's cost for the graph G.
naturally expect different results for hierarchical clustering with the splitting oracle with the two objectives.
3. The Definitions and Results for Partial Hierarchical Clustering Trees
Roughly speaking, Dasgupta's objective accumulates the cost on an edge (u, by the number of leaves inside the subtree where and e are first split. In contrast, the Moseley- Wang objective focuses on the dual of Dastupta's 's objective: it gathers the revenue on an edge (u, v) by the number of leaves outside the subtree where u and v are first split. For- mally, the Moseley- -Wag objective can be given as follows.
A technical backhone of algorithms in this paper is the partial hierarchical clustering tree. Roughly speaking, these structures replicate the organizational framework of the optimal HC tree, exhibiting only minor "ambiguity" within small subsets of vertices. In this section, we formally define the strong and weak partial trees and give efficient construction algorithms for them. We remark that our con- structions of the partial HC trees entirely based on the vertex set V and the oracle O of the input graph, irrespective of specific objective functions. This inherent independence renders our partial HC trees highly versatile and potentially of significant interest in their own right.
Problem 2 (HC under Dossley-Wange revenue function). Given an n-vertex weighted graph G (V, E, w) with vertices corresponding to data points and edges measuring their similarity, create a rooted tree T whose leaf nodes are V. The goal is to maximize the revenue reva(T) of a tree T defined as
Σ
w(e) (n [Leavesr II)
(M.N)EE
3.1. Partial hierarchical clustering trees
=
Σ (E(u,))EE
w(e) [ea I|,
We start by showing the definition of partial hierarchical clustering trees, which are very similar to the normal HC trees: the internal nodes represent subsets of vertices, and the leaves are individual vertices. However, in partial HC trees, allow collection of vertices that not too large to have unknown local clustering, and simply represent the whole set of vertices as leaf node in the tree. The formal definition is as follows.
where [Leavesr[LCAT(u, 1) is the number of leaf- nodes in the sub-tree of T rooted at the lowest common ancestor of u and v. and Broonlleaver((CAAr(. v)ll is the number of nodes that are not among CaavesT[LCAAte
w. We use OPT (G) to de- note the revenue of an optimal HC tree under Dasgupta's cost for the graph G.
Definition 7 (Partial hierarchical clustering trees). partial hierarchical clustering tree I is a binary tree such that
1. The root represents the vertex set V.
Observe that both objectives are composeable w.r.t. edges, i.e., it is possible to divide the total objective to objectives induced by each (or each set of) edge(s). For any HC tree T and any set of edge E₁ S E, we use reva E1) and costa(T (T, E1) to denote the revenue and the cost induced by the edges in Fg.
2. For a node x with children (y, z), it represents split
S₂ + Sz), where S₂ = Sy U...
3. The leaves of I corresponds to
either a singleton vertex in V.
By straightforward calculation, one can show that for any HC tree T, there is (T) = "e=(u,)e w(e) (T). Since Σe=(u, w(e) n is a deterministic function of the graph G itself, the optimal HC tree T under the two objectives are the same. However, the two objec- tively admits vastly different approximation algorithms. In particular, for the minimization objective, (Dasgupta, 2016) and the following work (Roy& & Pokutta, 2016: Charikar & Chatziafratis, 2017b) showed that we can achieve an O n) approximation in polynomial time, and there is no O(1) approximation in polynomial time assuming Small Set Expansion (SSE) hypothesis. On the other hand, for the revenue maximization objective, (Moseley & Wang, 2017) proved that the average-linkage heuristic can achieve a 1/3 approximation in polynomial time. Therefore, we would
set of vertices S C V such that S <
50000 log n. In this case, we call the leave super- vertex.
Compared to the full hierarchical clustering tree, the partial HC tree allows the leaves to be 'contracted' vertices with size at most O(logn) We now define a partial tree that is strongly consistent with a hierarchical clustering tree T.
Definition 8 (Partial tree strongly consistent with T), Let I be a partial hierarchical clustering tree and let T be (standard) hierarchical clustering tree. We say I is strongly consistent with T if
1. (Strong contraction property) Each super-vertex in- duces a maximal subtree T.
5

---

Learning-Augmented Hierarchical Clustering
2. (Subtree preservation property) For any pair of leaves (ar, y) in I, let X and Y be the set of leaves correspond- ing to æ and in T (recall that the leaves of I can be super-vertices). The subtree induced by LCAz(a, y) con- tains the exactly the same set of vertices as induced by ICAT(XUY),
In other words, a partial tree I is strongly consistent with T if there exists a way to locally arrange tree structures for
Contains most Ofogin]jertiies
every super-vertex to exactly recover T. An illustration of the strongly consistent partial tree (w.rt. T) can be found in Figure 1.
Figure 1. An illustration of the strongly consistent partial trees as defined in Definition 8. The boxes indicate super-vertices whose clustering is unknown in the partial HC tree.
The strong partial tree is very helpful data structure for HC. Nevertheless, finding such a strong partial tree could be challenging. As such, we also define partial trees that are weakly consistent with the tree T as follows.
Definition 9 (Partial tree weakly consistent with T). Let I be partial hierarchical clustering tree and let T be (standard) hierarchical clustering tree. We say I is weakly consistent with T if
1. (Weak contraction property) Each super-vertex corre- sponds to a collection of maximal subtrees in T, i.e., U,V, such that each Vi satisfies
ntmost Ofnggn))eeriicss not necessery
(eAVes)[LCAr(V)) V,.
Furthermore, the collection U,V, is with out-degree at
An illustration of the weakly consistent partial HC trees as defined in Definition 9. The boxes indicate super-vertices whose clustering is unknown in the partial HC tree.
Figure 2.
most 2 in T such that
(a) At most one edge is connected to a node that is the parent of the LCA of U.V.
An algorithm that, with high probability, constructs partial tree strongly consistent with the optimal tree T (n logn) time and (n²)) queries to the splitting oracle. Furthermore, the algorithm uses only Ö(n)
(b) At most one edge is connected node that sibling of maximal subtree of 'T induced by (a subset of) U,V.
2. (Subtree preservation property) For any pair of leaves (xr, y) in I, let X and Y be the set of leaves correspond- ing to x and in T (recall that the leaves of can super-vertices). The subtree induced by ICAA((r, y) con- tains the exactly the same set of vertices as induced by (XCT(
space; and
An algorithm that, with high probability, constructs a partial tree weakly consistent with the optimal tree T in Ö(1²) time and queries the splitting oracle, Furthermore, the algorithm can be implemented in the PRAM model with Ón²)) work and polylog n depth.
The difference between the weak and strong consistency is that in weakly consistent partial trees, the "contraction" of vertices can happen in any consecutive region of the original tree T. An illustration of the weakly consistent partial tree (w.r.t. 7) can be found in Figure 2.
Result for strongly consistent partial HC trees. Our main theorem to construct strongly consistent partial HC trees as follows.
Theorem 10. There exists an algorithm that given splitting oracle O of weighted undirected graph G (V, F, W., with high probability, in O( logn) time and O(n²) queries computes a partial hierarchical clustering tree I that is strongly consistent with the optimal hierarchi- cal clustering tree T Furthermore, the algorithm has the following properties.
Our goal is to use oracle O, and vertex set to construct a partial HC tree I that is consistent with the optimal HC tree T
3.2. Main results of partial HC trees
We now give our main results for the strong and weak partial trees, respectively. particular, our results include
i). The runtime of the algorithm deterministic, and
6

---

Learning-Augmented Hierarchical Clustering
the high probability randomness is over the correciness
HC trees for the rest of the main paper. We defer the detailed analysis of the partial trees Appendices F to H.
guarantee.
i). The algorithm can be implemented in On log n)
4. Polynomial Time Algorithms for Dasgupta's Hierarchical Clustering Objective
space.
While the algorithm outlined in Theorem 10 necessitates (nn") queries to the oracle O rendering it less efficient, the overall running time of O(n²) is tolerable, especially considering the hardness of HC.
We introduce our polynomial time algorithms for Dasgupta's HC objective in this section. These results include an ( ((1)-aprrxiiiation algorithm in polynomial time (albeit some large constant on the exponent) and an O(ylog log n)- approximation algorithm in Ónn)) time. Our algorithms crucially rely on the strongly consistent partial tree Theo- rem 10.
Result for weakly consistent partial HC trees. We now show our algorithmic results for the weakly consistent par- tial HC trees, which enjoy much better efficiency in both the running time and the number of oracle queries.
Theorem 11.
There exists an algorithm that given a splitring oracle O of weighted undirected graph G
4.1. Polynomial- Algorithm for O apprrxxmaaton on Dasgupta's HC Objective
(V, E. w), with high probubility, in O(n² polylog n) time and O queries computes a partial hierarchical clus-
We now introduce our algorithm that finds an HC tree with ( >ppprooxxiiioonnn to Dasgupta's objective in polynomial time. One can find the formal statement of the result in Theorem 1. The algorithm of Theorem is as Algorithm 1.
tering tree I that is weakly consistent with the optimal hierarchical clustering tree T
We note that since the number of longest dependent calls for our weak partial tree is at most Oloog n). Theorem 11 implies a PRAM algorithm with O(n² polylog n) work and Olog"
Algorithm 1 A polynomial-time algorithm for the Das- gupta's HC objective
3 n) depth. The formal statement is follows.
Input: Input graph G = (V, w): Splitting oracle O Output: A hierarchical clustering tree T
Corollary 12. There exists a PRAM algorithm that given graph G = =V, E.) and a splitting oracle O with high probability, in O(n² (on2-pooylogg n) work and Ollg" n) depth computes a partial hierarchical clustering free that is weakly consistent with the optimal HC tree T*
Run the strong partial tree approximation algorithm in The- orem 10 to obtain partial tree I for each super-vertex in I do
On input vertex set S, exhaustively search the sparsest
cut (A, B) on the induced subgraph G[S]
Partition the vertices as S + (A, B), and recurse on G[A] and GIB]
We suspect that by modifying some subroutines of the algo- rithm in Theorem 11, we could possibly bring the number of time and queries to Ö()). The study of sublinear-time algorithm is an interesting future problem.
end
We now prove the efficiency and the approximation guar- antees for Dasgupta's 's objective. The following lemma pro- vides the efficiency for Algorithm 1.
A (very) high-level technical summary of the partial trees. As we will discuss in Appendix B, simply following the oracle advice does not lead to any valid outputs. The construction of the partial trees requires a careful aggrega- tion of the split-away information recover subtrees with sizes ((log n). One observation here is that if we lucky to select vertex u from the smaller side of the first binary partition, we could determine the correct "side" for each ver- tex e E V in the first partition of the optimal tree with high probability. We could then recursively recover the partition in the optimal tree T However, getting a vertex from the smaller side of the first partition is not easy, and we would need to test multiple vertices and use the size of the resulting set as the indicator for correctness. This includes careful design and analysis of different algorithmic subroutines, which is the main technical challenge. A detailed technical overview could be find in Appendix B.
Lemma 4.1. Algorithm 1 runs (deterministically) in (n55002)) time and uses Onn² queries.
Proof. By Theorem 10, the first step of the algorithm that computes the strong partial tree takes Ö(z²) time and ((z²) queries. Note that we only take queries in this step.
For the second step, when the input size is s, an exhaustive search on the sparsest cut takes O(2*) time. As such, let X be the set of induced vertices for a single super-vertex of I, since have |X] I 50000 log n, it only takes 5020000 time to find the sparsest cut. Similarly, we can show that in each recursive call, the runtime is at most (1 By Fact 1. there are at most O(log n) nodes in a binary tree with O n) leaves. As such, the recursive sparsest cut for single super-vertex in I takes On 50000 log n) time. There
We present the HC algorithms using the results for partial
7

---

Learning-Augmented Hierarchical Clustering
most O(n) super-vertices in the tree; therefore, the total runtime of the second step takes (1,50000 log n-n) ( (00000) time.
Combining Theorem 10, Lemma 4.2, and Lemma 4.1 leads to the proof of Theorem 1 (see Appendix C for more formal version).
Combining the efficiency of the two steps gives us the de- sired efficiency bound.
4.2. An Ō(na) Time Algorithm for O Vlog log aaproxxmaatooonn on Dasgupta's HC Objective
LI
The main lemma for the approximation guarantees of Algo- rithm 1 is as follows.
One drawback of the algorithm we have in Section 4.1 is that the efficiency is "theoretical only" -fter all, a runtime of (1 is nowhere near being practical. Observe that the subroutine that leads to the very large exponent the exhaustive search of the optimal sparsest cut. Therefore, we can hope to use some more efficient approximation for spars- est cuts while not sacrificing too much on the approximation guarantee. This intuition leads us to Algorithm 2.
Lemma 4.2. Conditioning the high probability guaran- tees of Theorem 10, Algorithm I outputs an HC tree TT that achieves O(1) (ppproxxxiiiioonn to the Dasgupta's 's objective.
Proof. For any partial tree I, we first partition the edges in to Eseos and Esame based on whether the edge (u, u) E E crosses different partial trees, i.e.,
1. (u, v) E Erooss iff u E X and v E Y for some super- vertices X * Y I.
Algorithm 2 An Ö(1²) time algorithm for the Dasgupta's HC objective
2. (u,v) E Esame iff u, E X for some super-vertex X in I.
Input:
Input graph G = (V, E, w); Splitting oracle O Output: A hierarchical clustering tree T
Run the strong partial tree approximation algorithm in The- orem 10 to obtain partial tree I for each super-vertex in I do On input vertex set S, find an O(v log [-])- approximation of the sparsest cut (A, on the in- duced subgraph G[S] using the algorithm of Proposi- tion 18
Since = Fermes U Fxame. by using Observation 1, we can show that OPT = (T* = costa (T*, EE) + costa(T", E2). We now analyze the costs w.r.t. to Ej and Eg, respectively.
1. For Egnos, we argue that costa (T, EECOos) costa(T" Eeross) To see this, note that if u and e are of different super-vertices, by the definition of partial HC trees that are strongly consistent with the optimal tree T", there is
Partition the vertices as S - (A, B), and recurse on G[A] and G[B]
end
(eevesy[LCAA(U u)] = leaves7. [LCAT- (u, ]-
The main lemmas for the efficiency and approximation guar- antees for Algorithm 2 are as follows.
As such, we have costa(T. Egross) (T E
by the definition of the cost function.
Lemma 4.3. With high probability, Algorithu 2 runs in (n log time and uses O(n²) queries.
For Esame: we argue that costg Exame) < 0(1)
Lemma 4.4. Conditioning on the high probability guaran- tees of Theorem 10, Algorithm outputs an HC tree T that achieves O log n) approximation to the Dasgupta's ss objective.
(T* Esane). Formally, for each super-vertex X,
Proposition 17 on G[X] to argue that the costo (T, [Esame[]] < (1) costa(T", Eeame [X]), where Exame [X] stands for the set of edges in Exame with both endpoints in X. Therefore, we can apply this calcu- lation to every super-vertex to get the desired approxima- tion factor.
The proof of Lemma 4.3 and Lemma 4.4 could be found in Appendix C.
We now use Observation 1 again on Ecoos and Esame to bound that
5. Near-linear Time Algorithms for Moseley-Wang Hierarchical Clustering Objective
(7) = costo: (T, Eeroas) + costa (T, Esame)
(7" Eeross) + 0(1) costo (T" Esame)
We introduce our algorithm for the Moseley HC ob- jective in this section. The algorithm is based on the weakly consistent trees as in Theorem 11, which could be imple- mented in near- near-linear time. The algorithm is described as Algorithm 3.
x (1) (costa (T*, EETOS)) + costo (T', Esamee)
= (1) costa(T") = 0(1) Da
as desired.
8

---

Learning-Augmentedd Hierarchical Clustering
Algorithm 3 A near-linear time algorithm for the Moseley-
gorithms that achieve Ó(n) memory usage and O(1)- approximation Dasgupta's objective, albeit in expo- nential time. By improving the time efficiency to polyno- mial time, our streaming result echoes similar narrative in the offiin setting, demonstrating significantly more efficient constructions with the splitting oracle.
Wang HC objective
Input: Input graph G = (V, E, w): Splitting oracle O
Output: A hierarchical clustering tree 'T
Run the weak partial tree approximation algorithm in Theo- rem 11 to obtain partial tree I for each super-vertex in I do
partition the leaves arbitrarily to obtain an HC tree T
2.
For the parallel setting, (Agarwal et al., 2024) (cf. (Agar- wal et al., 2022)) provided parallel algorithms (in the PRAM and the similar MPC settings, see Appendix A.3 for details of these models) for Dasgupta's objective with ((n²) work and polylog n depth that achieve polylog n approximation. Since the objectives are different, their result is not directly comparable to ours; however, the conceptual message here is still that the splitting ora- cle is able to significantly improve the approximation guarantee and the efficiency.
end
Since each super-vertex contains Ollog n) vertices, we can always partition the super-vertices in polylog time?. There are at most On// log n) such super-vertices, and the total runtime overhead is at most On polylog
Our analysis for Algorithm 3 is more involved compared to the results in Section 4 4-ix it requires careful handling of the contributions of the 'less significant edges' to the Moseley- Wang objective. In particular, we could prove the following structural result. Let Z be any partial HC tree that is weakly consistent with the optimal tree T", we show that the set of edges (u, v) such that
Due to space limits, we only give the algorithms as Al- gorithm 4 and Algorithm 5, and defer their proofs to Ap- pendix E.
Algorithm 4 A polynomial-time single-pan pass semi-streaming algorithm for the Dasgupta's 's HC objective
a). has at most Ologg" n) non-leaves in T"; and
Input: Input graph G = (V, E, w); Splitting oracle O Output: A hierarchical clustering tree
b). let X and Y be corresponding super-vertices that con- tain u and v in I; there is leavesy. LCAr- (LCAr-- (X)] n leaves7. [CAT- (Y)] ] o 0.
Before the start of the stream, run the strong partial tree approximation algorithm in Theorem 10 to obtain partial tree I
contribute to at most ((1) fraction of the optimal cost. To the best of our knowledge, the structural result was not known before.
for each edge v) with during the insertion/delltion stream do
If u, v E X for any super-vertex X in I, update (u, v) with the same insertion/delltion update Otherwise, ignore the edge end
6.
Sublinear Algorithms for Hierarchical Clustering
for each super-vertex in I after the stream, runn recursive sparsest cut as follows do On input vertex set S, exhaustively search the sparsest cut (A, B) on the induced subgraph G[S).
In this section, we explore sublinear algorithms for hierar- chical clustering with the splitting oracle. Among these is a semi-streaming algorithm, capable of computing an (11) ap- proximation of Dasgupta's HC' objective within polynomial time. Additionally, we introduce PRAM algorithm that achieves (1 o(1) approximation of the Moseley- -Wang objective, utilizing (nn)) work and polylog depth. From a technical standpoint, these algorithms represent straight- forward extensions of the results outlined in Theorems to 3. Despite their simplicity, these algorithms demonstrate the advantages of the splitting oracle in modern sublinear computation models. Specifically, we compare our sublinear algorithms with previous results as follows:
Partition the vertices as S - (A, B), and recurse on G[A] and G[B].
end
Algorithm 5 A near-linear work, poly-logarithmin depth
PRAM algorithm for the Mosg HC objective
Input: Input graph G = (V, F,, w²); Splitting oracle O Output: A hierarchical clustering tree T
Run the PRAM weak partial tree approximation algorithm in Corollary 12 to obtain partial tree I for each super-vertex in I do
1. In the streaming setting, (Assadi et al., 2022; Agar- wal et al., 2022) designed single-pass streaming al-
Partition the leaves arbitrarily to obtain an HC tree T
end
AArbitrary balanced partitions requires (log nlg logn) time

---

Learning-Augmented Hierarchical Clustering
Acknowledgements
Anthony, M. and Bartlett, P. L. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. doi: 10. 0011017/CB09988511622222
We thank anonymous ICML reviewers for the helpful com- ments and suggestions. Vladimir Braverman supported in part by the Naval Research (ONR) grant N00014-23-1-2737 and NSF 233-8333887 award. Samson Zhou is supported in part by NSF CCF-2335411. The work was conducted in part while Samson Zhou was visiting the Simons Insti- tute for the Theory of Computing as part of the Sublinear Algorithms program.
Antoniadis, A., Coester, C., Eliás, M.., Polak, A., and Simon, B. Online metric algorithms with untrusted predictions. ACM Trans. Algorithms, 19(2):1:1119:33, 2023.
Arora, S., Hazan, E.,, and Kale, S. O(sqrt (log n)) approxi- mation to SPARSEST CUT in ō(n²) time. In 45th Sym- posium on Foundations of Computer Science (FOCS), 2004.
Proceedings. pp.
Impact Statement
Assadi, S., Chatziafratis, V., Lacki, J., Mirrokni, V., and Wang, C. Hierarchical clustering in graph streams: Single- pass algorithms and space lower bounds. In Conference on Learning Theory, pp. 4643 4700, 2022.
This paper presents work that advances the Machine Learn- ing and Algorithm Design fields. Due to its theoretical nature, we do not see any immediate societal impacts, al- though there are many potential societal consequences of our work for downstream applications.
Azar, Y., Panigrahi, D., and Touitou, N. Online graph algorithms with predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 35-66, 2022.
References
Aamand, A., Chen, J. Y., and Indyk, P. (optimal) online bipartite matching with degree information. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurlPS, 2022.
Bamas, É., Maggiori, A., and Svensson, O. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
Agarwal, A., Khanna, S., Li, H., and Patil, P. Sublinear algorithms for hierarchical clustering. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), ), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurlPS, 2022.
Benomar, Z. and Perchet, V. Advice querying under budget constraint for online algorithms. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurlPS, 2023.
Agarwal, A., Khanna, S., Li, H., Patil, P., Wang, C., White, N., and Zhong, P. Parallel approximate maximum flows in near-lineal work and polylogarithmic depth. In Proceed- ings of the 2024 Annual ACM-SIAM Symposium on Dis- crete Algorithms (SODA), pp. 3997-4061 SIAM, 2024.
Braverman, V., Dharangutte, P., Shah, V., and Wang. maximum independent set. In Approximation, Randomization, and Combinato- rial Oplimization. Algorithms and Techniques, AP- PROX/ANDDM, pp. 24:1-24:18, 2024.
C.
Aho, A. V., Sagiv, Y., Szymanski, T. G., and Ullman, J. D. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing, 10(3):405 421, 1981.
Braverman, V., Dharangutte, P., Jiang, S. H.-C., Nguyen, H.- A., Wang, C., Zhang, Y., and Zhou, S. Relative error fair clustering in the weak-strong oracle model. In Proceed- ings of the 42nd International Conference Machine Learning, ICML, 2025.
Alon, N., Snir, S., and Yuster, R. On the compatibility of quartet trees. SIAM J. Discret. Math., (003)))19331507 2014.
C. S., K., Lee, E., Rabani, Y., Schwiegelshohn, C., and Zhou, S. On approximability of & min-sum clustering. CoRR, abs/2412.03332,, 2024.
Alon, N., Azar, Y., and Vainstein, D. Hierarchical cluster- ing: A 0.585 revenue approximation. In Conference on Learning Theory, COLT, pp. 153-162, 2020.
Charikar, M. and Chatziafratis, V. Approximate hierarchical clustering via sparsest cut and spreading metries. In Proceedings of the Twenty-Eights Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 841-854, 2017a.
Anand, K. Ge, R., Kumar, A., and Panigrahi, D. Online algorithms with multiple predictions. In International Conference on Machine Learning, ICML, pp. 582-598, 2022.
10

---

Learning-Augmentedd Hierarchical Clustering
Charikar, M. and Chatziafratis, V. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the Twenty-Eightl Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 841-854. SIAM, 2017b.
Cohen-Addad, V., d'Orsi, T., Gupta, A., Lee, E., and Pani- grahi, D. Beaming-augmenter approximation algorithms for maximum cut and related problems. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems, NeurIPS, 2024.
Charikar, M., Chatziafratis, V., and Niazadeh, R. Hierarchi- cal clustering better than Peerage-linkage.. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA, pp.
Dasgupta, S. A cost function for similarity- -ased hicrar- chical clustering. Wichs, D. and Mansour, Y. (eds.), Proceedings of the 48th Annual ACM SIGACT Sympo- sium Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pp- 118-127. ACM, 2016.
SIAM, 2019a.
Charikar, M., Chatziafratis, V., Niazadeh, R., and Yaroslavt- sev, G. Hierarchical clustering for euclidean data. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 2721-2730, 2019b.
Davies, S., Moseley. B., Vassilvitskii. S., and Wang, Y. Predictive flows for faster ford-fulkerson. In International Conference on Machine Learning, ICML, volume 202, pp. 7231 2023.
Chatziafratis, V. and Makarychev, K. Triplet reconstruction and all other phylogenetic esps are approximation resis- tant. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 253-284, 2023.
Deng, C., Gao, J., Upadhyay, J., Wang, C., and Zhou, S. On the price of differential privacy for hierarchical clustering. In The Thirteenth International Conference on Learning Representations, ICLR, 2025.
Chatziafratis, V., Niazadeh, R., and Charikar, M. Hierarchi- cal clustering with structural constraints. In Proceedings of the 35th International Conference on Machine Learn- ing, ICML, pp. 773-782, 2018.
Dinitz, M., Im, S., Lavastida, T., Moseley, B., and Vassilvit- skii, S. Faster matchings via learned duals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pp. 10393-10406, 2021.
Chatziafratis, V., Gupta, N., and Lee, E. Inapproximability for local correlation clustering and dissimilarity hierar- chical clustering. CoRR, abs/2010.01459, 2020a.
Dong. Y., Peng, P., and Vakilian, A. Learning seemming-augmentrr streaming algorithms for approximating MAX-CUT. In 16th Innovations in Theoretical Computer Science Con- ference, ITCS, pp. 14:1-44:24, 2025.
Chatziafratis, V.. Yaroslavtsev, G., Lee, E., Makarychev, K., Ahmadian, S., Epasto, A., and Mahdian, M. Bisect and conquer: Hierarchical clustering via max-uneu bisection. In The 23rd International Conference Artificial Intelli- gence and Statistics, AISTATS, pp. 3121-3132, 2020b.
Emamjomeh-Zaadeh, E. and Kempe, D. Adaptive hierarchi- cal clustering using ordinal queries. In Proceedings of the Twenty- Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 415-429, 2018
Chen, J. Y., Eden, T. Indyk, P., Lin, H., Narayanan, S., Rubinfeld, R., Silwal, S., Wagner, T., Woodruff, D. P., and Zhang, M. Triangle and four cycle counting with predictions in graph streams. In The Tenth International Conference on Learning Representations, ICLR, 2022a.
Ergun, J. C., Feng, Z., Silwal, S., Woodruff, D. P., and Zhou, S. Leaming--ugmmented k-means clustering. In The Tenth International Conference on Learning Representations, ICLR, 2022.
Fu, C., Nguyen, B. G., Seo, J. H., Zesch, R. S., and Zhou, S. Learning-augee augmented search data structures. In The Thirteenth International Conference on Learning Repre- sentations, ICLR, 2025.
Chen, Y., Indyk, P., and Wagner, T. Streaming algo- rithms for support-aware histograms. In International Conference Machine Learning, ICML, pp. 1184-3203, 2022b.
Gollapudi, and Panigrahi, D. Online algorithms for rent- or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, ICMI., pp. 2319-2327, 2019.
Chen, J. Y., Silwal, S., Vakilian, A., and Zhang, F. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, ICML, pp. 3583-3602. 2022c.
Grigorescu, E.,, Lin, Y., Silwal, S., Song, M., and Zhou, S. Searning-augmentt algorithms for online linear and semidefinite programming. In Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurlPS, 2022.
Cohen-Addad, V., Kanade, V., Mallmann-Trem F., and Mathieu, C. Hierarchical clustering: Objective functions and algorithms. Journal of the ACM (JACM), 66(4):1-42, 2019.

---

Learning-Augmented Hierarchical Clustering
Guénoche, A., Hansen, P., and Jaumard, B. Efficient algo- rithms for divisive hierarchical clustering with the diame- ter criterion. Journal of classification, 8:5-30, 1991.
Khodak, M., Balcan, M., Talwalkar, A., and Vassilvitskii, S. Learning predictions for algorithms with predictions. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurlPS, 2022.
Gupta, A., Panigrahi, D., Subercaseaux, B., and Sun, K. Augmenting online algorithms with S varepsilonS- accurate predictions. In Koyejo, S., Mohamed, S., Agar- wal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Ad- vances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurlPS, 2022.
Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. The case for learned index structures. Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference, pp. 489-504, 2018.
Lattanzi, S., Lavastida, T., Moseley, B., and Vassilvitskii, S. Online scheduling via learned weights. In Proceedings of the 2020 ACM- Symposium on Discrete Algorithms, SODA, pp. 1859-1877, 2020.
Høgemo, S., Bergougnoux, B., Brandes, U., Paul, C., and Telle, J. A. On dasgupta's 's hierarchical clustering ob- jective and its relation to other graph parameters. In Bampis, E. and Pagourtzis, A. (eds.). Fundamentals of Computation Theory- 23rd International Symposium, FCT, Proceedings, pp. 287-300, 2021.
Leskovec, J., Rajaraman, A., and Ullman, J. D. Mining of massive data sets. Cambridge university press, 2020.
Li, Y., Lin, H., Liu, S., Vakilian, A., and Woodruff, D. P. Learning the positions in countsketch. In The Eleventh International Conference on Learning Representations, ICLR, 2023.
Hsu, C., Indyk, P., Katabi, D., and Vakilian, A. Learning- based frequency estimation algorithms. 7th Interna- tional Conference on Learning Representations, ICLR, 2019.
Lin, H., Luo, T., and Woodruff, D. Learning augmented binary search trees. In International Conference on Ma- chine Learning, ICML, pp. 13431-13440, 2022.
Im, S., Kumar, R., Qaem, M. M., and Purohit, M. On- line knapsack with frequeney predictions. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurlPS, pp. 2733-2743, 2021.
Lucic, M., Faulkner, M., Krause, A., and Feldman, D. Train- ing gaussian mixture models at scale via coresets. J. Mach. Learn. Res., 18:16011-160:25, 2017.
Indyk, P., Vakilian, A., and Yuan, Y. Learning-based low- rank approximations. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS, pp. 7400- 7410, 2019.
Lykouris, T. and Vassilvitskii, S. Competitive caching with machine learned advice. ACM, 68(4))24 2021.
Manghiuc, B. and Sun, H. Hicrarchical clustering: O(1)- approximation for well-clustered graphs. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pp. 9278-9289, 2021.
Izzo, Z.,, Silwal, S., and Zhou, S. Dimensionality reduction for wasserstein barycenter. In Advances in Neural Infor- mation Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS, 2021.
Mitzenmacher, M. model for learned bloom filters and optimizing by sandwiching. In Advances in Neural In- formation Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurlPS, pp. 462-471, 2018
Jiang, S. H., Liu, E., Lyu, Y., Tang, Z. G., and Zhang, Y. Online facility location with predictions. The Tenth International Conference on Learning Representations, ICLR, 2022.
Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Roughgarden, T. (ed.), Beyond the Worst- Case Analysis of Algorithms, pp. 646-662. Cambridge University Press, 2020.
Jinng T., Kearney, P. F., and Li, M. polynomial time ap- proximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput., 1900:99922991. 2000.
Moseley, B. and Wang, J. R. Approximation bounds for hier- archical clustering: Average linkage, bisecting k-means, and local search. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 3094-3103, 2017.
Jiang, T., Li, Y., Lin, H., Ruan, Y., and Woodruff, D. P. data stream algorithms. In 8th Inter- national Conference on Learning Representations, ICLR, 2020.
12

---

Learning-Augmented Hierarchical Clustering
Nguyen, T. D., Chaturvedi, A., and Nguyen, H. L. Im- proved Baaning-auggmene algorithms for k-means and k-medians clustering. In The Eleventh International Con- ference on Learning Representations, ICLR, 2023.
Wang, S., Li, J., and Wang. S. Online algorithms for multi- shop ski rental with machine learned advice. In Advances in Neural Information Processing Systems 33; Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
Purohit, M., Svitkina, Z., and Kumar, R. Improving online algorithms via ML predictions. In Advances in Neural In- formation Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS, 2018.
Ward Jr, H. Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301):236-25) 244, 1963.
pp.
Wei, A. and Zhang, Optimal robustness-consiiterns trade-off' for learning-augmentee online algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurlPS, 2020.
Rajagopalan, A., Vitale, F., Vainstein, D., Citovsky, G., Pro- copiuc, C. M., and Gentile, C. Hierarchical clustering of data streams: Scalable algorithms and approximation guarantees. In Meila, M. and Zhang. T. (eds.), Proceed- ings of the 38th International Conference on Machine Learning, ICML, pp. 8799-8809, 2021.
Roy, A. and Pokutta, S. Hierarchical clustering via spread- ing metrics. In Advances in Neural Information Process- ing Systems, pp. 23 2316-2324, 2016.
Roy, A. and Pokutta, S. Hierarchical clustering via spread- ing metrics. J. Mach. Learn. Res., 18:88:1-888 18:335, 2017.
Shin, Y., Lee, C., Lee, G., and An, H. Improved learning- augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In In- ternational Conference on Machine Learning, ICML, pp. 31539-31561, 2023.
Sneath, P. H., Sokal, R. R., et Numerical taxonomy. the principles and practice of numerical classification., 1973.
Snir, S. and Yuster, R. A linear time approximation scheme for maximum quartet consistency on sparse sampled in- puts. SIAM J. Discret. Math., 1724)1172 2011.
Sotiriou, C., Neo, S.-Y., McShane, L.. M., Korn, E. L.,, Long, P. M., Jazaeri, A., Martiat, P., Fox, S. B., Harris, A. L., and Liu, E. T. Breast cancer classification and progno- sis based on gene expression profiles from a population- based study. Proceedings of the National Academy of Sciences, 100(18):00333-1033) 2003.
Steinbach, M., Karypis, G., and Kumar, V. A compari- son of document clustering techniques. Technical report, University of Minnesota, 2000.
Szegedy, C., Zaremba, W. Sutskever, I., Bruna, J., Erhan, D.. Goodfellow, I. J., and Fergus, R. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR, Conference Track Proceedingg, 2014.
Thomdike, R. L. Who belongs in the family? Psychome- trika, 18(4):267-276, 1953.
13

---

Learning-Augmented Hierarchical Clustering
A. Additional Technical Preliminaries
A.1. Concentration inequalities
We now present the standard concentration incqualities used in our proofs. We start from the following standard variant of Chernoff Chermoff-Hoefcding bound.
Proposition 13 (Chemoff-Hoeffdngg Hoeffding bound), Let XI...., a be independent random variables with support in [0, 1].
Define X = Ei= X,, Then, for every d (0, 1}, there is
R [ > 8 [X] 2 exp (- 8 B
Pr Pr
3
Furthermore, for every there is
8' [X]
> [X] 2 exp Pr
2 2+0
A.2. Standard results for trees
Fact A.1. Any binary tree T with leaves contains most internal nodes.
Proof. Consider the collection of the internal nodes that are the parents of the leaves. Since the tree is binary, there are at most n/2 such nodes. Contract all these internal nodes with the leaves, and we can obtain a new tree T such that the number of leaves is n2/2. As such, we can again count an upper bound for the number of the parents for the leaves in T' as n/4. We can continue this until we only have the root, and the number of internal nodes at most
n
n
2
$=00
as desired.
A.3. The PRAM and the Massively Parallel Computation (MPC) Models
We briefly introduce the parallel models investigate for the Moseley-Wang objective. In particular, investigated the classical PRAM model and the Massively Parallel Computation model in work.
The PRAM model. The Parallel Random Access Machine (PRAM) model is widely used theoretical framework in parallel computing. It provides a simplified abstraction of a parallel computer system, where multiple processors work simultaneously to solve a computational problem. In the PRAM model, each processor has direct access to a common memory space (RAM), and communication between processors and the RAM is instantaneous ("parallel" RAM). Processors can read from and write to any memory location parallel, hence the term "Random Access".
In the PRAM model, there are usually two objectives for algorithm designers to optimize: the total work, defined as the total number of elementary operations, and the depth, defined as the length of the longest dependent call in the algorithm. In the theoretical abstract version of PRAM, we do not care about the number of processors we use in the algorithm.
The MPC model. The Massively Parallel Computation (MPC) model is theoretical framework used to analyze algorithms designed for modern parallel computing architectures, e.g., the MapReduce framework. this model, communications are conducted synchronized rounds, and a machine can communicate with any other machine a round. Furthermore, each machine can do unlimited local computation between the rounds. Unlike traditional CONGEST models, the communication here is limited only by the memory size size s machine cannot send or receive more than bits of information.
For graph problems, suppose each machine has size typically use Ô(n² /s) machines, where O(n²) is the worst-case input size (alternatively, one can also target the more instance-optimal ((m/s) machines).
Our goal in the MPC model to minimize two objectives: i). the memory size s of each machine; and ii). the number of parallel rounds. particular, if our algorithm works with s = O(n") memory for any 6 (0, 1), we call the algorithm fully scalable in the MPC model. Typically, the best MPC algorithms would ask for fully scalable memory and polylog n rounds.
14

---

Learning-Augmented Hierarchical Clustering
A reduction between the PRAM and the MPC algorithms. The PRAM and the MPC models share great deal of similarities. And indeed, the following reduction is known.
Proposition 14. Suppose there exists a PRAM algorithm that computes a function f with w(n) work and d(n) depth. where is the input size of f. Then, there exists a fully scalable MPC algorithm that computes f with ((w(n)) total memory and (dd) rounds. The memory per machine can be made ( for any ā E (0, 1), and the number of machines is 00 (W polylog
A.4. Existing Techniques for Dasgupta's Objective
We discuss some known techniques for Dasgupta's 's minimization HC objective this section. We will use these techniques in our hierarchical clustering algorithms for Dasgupta's 's objective.
OPTIMAL HIERARCHICAL CLUSTERING TREES
We first give observation that characterizes the "composability" of HC costs with respect to the edges under Dasgupta's objective.
Observation 1 (DDaggutta, 2016)). Let G be any graph, and let E1 and Eg be two disjoint subsets of edges in G. For any HC free T, let costa (T, F1) and costa(T, F22) be the HC costs induced by edges in F and Foz, respectively. Then,
(T) (o,to(T, (T,
Observation 1 shows that to bound the total cost of the HC tree under Dasgupta's objective, it suffices to bound the edges split by the internal nodes.
APPROXIMATE HC TREES WITH RECURSIVE BALANCED MIN-CUTS AND SPARSEST CUTS
Dasgupta's 's work proved that finding the optimal trees for the hierarchical clustering function is NP-hard (Dasgupta, 2016). Consequently, significant attention has been directed towards developing approximation algorithms for efficient hierarchical clustering on the graph. A well-known approach involves obtaining an approximation of the optimal hierarchical clustering by iteratively employing sparsest cuts on the graph, e.g., (Dasgupta, 2016; Deng et al., 2025). Formally, we can define the sparsest cuts and the HC trees created by recursively applying the sparsest cuts the induced subgraphs in Definition 15 and Definition 16.
Definition 15 (Sparsest Cuts). For any parameter 3 such that B < 1. we say that cut (A'B") is sparsest cut if its sparsity (edge expansion) is minimized, i.c.
w(A", (A) min { |A min [IA, [B]]
10( A, B)
for any cut (A, B) of G.
Definition 16 (Recursive Sparsest Cut Procedure). We say an HC tree T is obtained by the recursive sparsest procedure on G if for each non-leaf node of T, the cut(T is obtained by (possibly approximate) sparsest cut (A, B) on the subgraph induced by [[.]. We call an HC tree obtained by recursively applying (approximate) sparsest cuts on induced subgraphs as a recursive sparsest cut HC tree.
Previous work (see, e.g. (Charikar& & Chatziafratis, 2017b; Assadi et al., 2022)) proved that one applies the procedure in Definition 16, we can get an (1) approximation of the optimal HC tree.
Proposition 17 (CCharikar & Chatziafratis, 2017b; Assadi et al., 2022)), For any graph G = (V, E, w), let Tsparse be an HC tree obtained by the recursive sparsest cut procedure in Definition 16, there is
costa Costa(Tsparse
Note that finding the exact sparsest cut for Proposition 17 is NP-hard. The first way to circumvent this issue to use approximation algorithms, especially for the best-known O (Vlogn) approximation for sparsest cut in polynomial time (Arora et al., 2004). The formal guarantee as follows.
15

---

Learning-Augmented Hierarchical Clustering
Proposition 18 (AArora et al., 2004)), There exists a randomized algorithm that given a graph G (V, E, w), with high probability, in Ó(IV)) time finds a partition AUB = =V such that
w(A, B) min(1A] |B]] S 5O(Vlog]V) (V)
w(A", BB) min |B1)3
where (*) is the sparsest cut of G.
We cannot immediately massage Proposition 18 with Proposition 17 since Proposition 17 does not state what will happen for approximate sparsest cuts. Fortunately, by the results in (Charikar & Chatziafratis, 2b; Assadi et al., 2022), we can indeed obtain an -appoxiiiiinnnaionn algorithm for OPT(G) by recursively applying the a-approximate sparsest cut. Proposition 19 (CCharikar& & Chatziafratis, 7b; Assadi et al., 2022)). Let T be a recursive sparsest cut tree obtained by recursively applying a-approximation sparsest cuts on the induced subgraphs (as in Definition 16). Then, we have
(TS S ( OPT(G).
There is another way to deal with the NP-hardness issue of the sparsest cut. If we can reduce the input size, we can possibly obtain the exact optimal cuts on induced subgraphs of size O(log n). This strategy allows us to leverage our strong partial tree whose 'unknown' clustering is only restricted to the induced subgraphs with O(log n) size.
B. Technical Overview
In this section, give a high-level overview of our techniques. We also provide intuition on algorithmic design choices, including number of potential pitfalls, as well number of natural other approaches and why they do not work.
B.1. Why not simply follow the oracle (or other related strategies)?
At first glance, one might wonder whether the splitting oracle trivializes the problem. A natural question is whether it is possible to simply follow the oracle to recover the optimal tree T Since the oracle only returns the relative information among triplet of vertices (u, w), it is not immediately clear how to translate the answers from the oracle to a partition of vertices. After taking a closer look at the problem, we could observe issues with a handful of straightforward approaches.
The first natural approach is to pretend the oracle is always correct and construct a tree from the ssplitting-awayy information between the triplets. Unfortunately, due the error probability and adversarial answers, there may nor exist an underlying tree consistent with the answers the queries. As such, it is unclear how the algorithm could produce a definitive answer.
The second approach could try is to frame the problem as a phylogenetic reconstruction problem, c.g., take all the "splitting away" for triplets as constraints, and try to construct an HC tree that satisfies as many constraints as possible. However, such an approach has two issues: i). by a recent result of (Chatziafratis & Makarychev, 2023), the phylogenetic reconstruction problem is itself UG-hard; and ii). the HC tree we constructed may prioritize a small number of wrong answers from the oracle that happen to induce very large additive error.
A more involved idea is to "aggregate" the oracle answers construct the HC tree's partitions. To this end, algorithm determine the partition of a vertex is to fix in the smaller subtree and look into the number of vertices t E V that split away from (u, v). More concretely, consider the split of the tree the root V + (S), S2), and suppose we know vertex that is on the smaller subtree of the root partition (this is a big "suppose" as we will see later). Then for any vertex v that is in the same subtree of u, we can get many vertices f E V from O with the answer "t split away from (u, v)". On the other hand, for a vertex u that is in the opposite subtree of u, only a few vertices t from O would answer "t E V split away from (u, v)". The gap is large enough to apply concentration inequalities and find a separation between the cases. As such, we can recursively apply the above procedure and produce the optimal tree T
Unfortunately, the above idea only works for the idealized case where we indeed know a vertex u from the smaller part of the root partition. For the general case, the algorithm requires a surprising amount of new ideas and technical work. In particular, note that the aforemennioned algorithm faces two major challenges: (1). as the partition goes deep down the HC tree, the sizes of the subtrees become too small for high-brobability guarantees; and (2). it is not clear how to find a "good" vertex u that induces the root cut. To elaborate on challenge (1), note that when the subtree induces o(log n) leaves, is generally not possible for us to guarantee correctness for the subsequent partitions. As such, we must handle some form
16

---

Learning-Augmentedd Hierarchical Clustering
of "ambiguity" when dealing with subtrees induced vertex sets with smaller sizes. Our approach this challenge is forgo the guarantees inside each leaf with ollog n) vertices and work with the respective objective functions show that the additive error is tolerable. In particular, we use the notion of partial hierarchical clustering trees that approximately capture the structure of the optimal HC tree T until the size of the induced vertex set becomes too small. In particular, we require specific structural properties of the costs of HC trees under Dasgupta's and the Moseley- Wang objectives. We provide more details about partial HC trees and how to use them to overcome challenge (1) in Appendix B.2.
Challenge (2) is even trickier and requires more care. Observe that in the example of root cut V + S2), if is in the bigger side of the partition, the argument may not work. However, since we only have access the tripler split information, retrieving whether vertex u is the smaller side of particular tree split seems to be too much to ask. In particular, consider example that the optimal tree 7 first makes two splits of small subtrees of size n n.99, as illustrated in Figure 3. Here, if we use U2 as the "baseline" vertex to perform the split, we can still get valid partition. However, the structure of the obtained tree is very different from T', and the additive error could be huge. Furthermore, since the actual tree T is hidden from us, it is not immediately clear how could we distinguish a partition obtained by using 21 vs. 1/2 The problem becomes even more intriguing when we want to obtain near-linear time efficiency. We will discuss the intuition and techniques handle challenge (2) in Appendix B.3.
Ou
Ou
142
0.99
Figure 3. An illustration of the hard example that the straightforward majority voting does not work. Left: the optimal HC tree T"; Right: the outcome of the tree if we use U2 as the baseline to perform the partition we discussed.
B.2. Partial hierarchical clustering trees and HC
We now delve into more details about the definition of partial trees and how we use them obtain low additive errors in Dasgupta's 's and the Moseley- -aag objectives.
The definition of partial hierarchical clustering trees. As discussed, a central element of our techniques is the notion of partial hierarchical clustering (HC) trees. The generic definition of the partial HC tree is similar to the normal HC tree, with the root representing the entire vertex set and the internal nodes representing the subsets of vertices. However, the leaf level, we allow the leaves of partial HC trees to contain multiple vertices, up to Ollog n) many vertices, and contract them into a single leaf, which we call "super-vertices". The partial HC tree is then allowed to be oblivious of the clustering inside each leaf node.
partial HC tree only useful it can somehow capture the optimal tree T To this end, we introduce the strongly consistent and weakly consistent partial HC trees. Roughly speaking, a partial HC tree I is said to be strongly consistent with the optimal tree T if it follows every partition of the optimal tree in top-down manner until the induced size of vertices is of size less than O(log n),, in which case we simply collapse the leaf into a super-vertex. Note that in the strongly consistent partial HC trees, every super-vertex induces a maximal tree in T - here, maximal tree means a tree where its induced vertices are exactly the leaves of their lowest common ancestor. By comparison, the weakly consistent partial HC tree allows vertices that do not necessarily form maximal trees to collapse into a single super-vertex. vertex. For instance, there are Olog n) vertices in multiple subtrees in T and suppose the LCAs of these subtrees are close the root and
17

---

Learning-Augmentedd Hierarchical Clustering
form consecutive segment in T", the weakly consistent partial HC tree can still collapse all of the vertices into a single super-vertex. We provide illustrations of the weakly and strongly consistent partial trees in Figure 1 and Figure 2, and one can refer their formal definition to Definitions 8 and 9 in Section 3.
We will eventually show that, given the splitting oracle, we can efficiently construct both the strongly and the weakly consistent partial trees regardless of the input graph and the objective functions. However, for now, we first discuss why partial HC trees are useful for our HC objectives.
Using partial HC trees for hierarchical clustering. Intuitively, if we can obtain a partial HC tree that is consistent with the optimal tree T", we can build an actual HC tree by "fixing" the clustering of the super-vertices locally to obtain good approximation. Indeed, we note that if a partial HC tree is strongly consistent with T*, we can straightforwardly obtain approximation algorithms for both Dasgupta's and the Moseley- Wang objectives. For Dasgupta's 's objective, we can run the optimal or approximate recursive sparsest cuts for the subgraphs induced by the super-vertices. Note that since the subgraphs are only of size O(log n), we can even afford to find the exact optimal recursive sparsest cuts in polynomial time. The case for the Moseley-Wang objective is even casier: since the number of leaves outside each super-vertex is at least n O(logn) n),, any arbitrary partition of the super-vertices can still give us a (1 - o()) approximation.
Unfortunately, as we will see shortly, the strongly consistent partial tree can only be implemented in Ó(n²) time - a tolerable yet far-from-optimal efficiency. As such, for the Moseley-Wand Wanl objective, we further investigate the algorithm that only uses the weakly consistent partial HC trees, which we can build in near-linear time. In this case, for two vertices that are in the same super-vertex, can replicate the argument for the strongly consistent partial HC trees again to get (1 - o( 1)) approximation. However, challenges arise when the two vertices (u, v) are in different super- super-vertices of the partial HC tree. Here, the number of induced leaves can differ by an Ollogn) additive factor, but the number of non-leaves induced by (u, v) can be very small in T (say, olog n)). As such, the (log difference on the size of non-leaves might lead to infinity multiplicative gap in the revenue, which makes controlling the overall approximation factor hard. To tackle this issue, we prove some new structural results for HC trees under the Moseley- -Wng objective: we show for all the edges (u, u) that only induce very small number of non-leaves and are "far away" from each other in the optimal tree, the contribution of such edges to the optimal objective can only be an o(1) fraction. As such, we can simply ignore the approximation guarantees on these edges and obtain an (1 - o(1) approximation of the Moseley- -ang objective.
B.3. The construction of the partial HC trees
We now come back to the efficient construction of the partial HC trees that are strongly and weakly consistent with the optimal HC tree. For simplicity, we slightly abuse the notation to let V always denote the vertex set in the high-level discussion, even if we are talking about a subset of vertices?.
B. STRONGLY CONSISTENT PARTIAL HC TREES
We first discuss the case for the strongly consistent HC tree, which only requires top-down splits. As we have discussed before, for any fixed partition, since we do not have any information about which side a vertex u is on, is generally very hard for us to know which obtained partition is actually consistent with the split in ' To address this challenge, introduce the small-tree splitting order, which, roughly speaking, is thought process that recursively draws the smaller side of the subtree in T For instance, in the tree T prescribed in Figure 3, the first n 0,99 vertices form the first small tree 1/small the second n 0.99 vertices form the second small tree V.saalll and so on.
We shall show that if u is among the first few small trees in the small-tree splitting order, we can recover the set of vertices as the sibling of the small tree*. For example, if we select ui2 in Figure 3, we can recover the subtree on the right but not the subtree that contains u1 Our strategy is as follows: for fixed vertex u and a vertex e whose split is to be determined, in addition to testing how many vertices E V such that splits away from (u, v), we also test the number of vertices E V such that splits away from (u, To see why this additional test helps, let us again look at the example in Figure 3. With the additional subroutine, if we use U22 as the fixed vertex, the vertices in yamaall will split away from many (w2, t) pairs. On the other hand, for every vertex v on the sibling subtree of V/small, it splits away from (u, f) only if E Viamall, which creates a clear signal. By careful handling of cases, we could argue that the algorithm works for general cases as long as u belongs to an "early enough" small tree.
'In the formal analysis of Appendices G and H. we use V the set of vertices of the current recursion level. + *Since "sibling" is a generic word, we call this set "counterpart" in our formal description in Appendices G and H to avoid confusion.
18

---

Learning-Augmented Hierarchical Clustering
The above strategy provides new way to identify a "good" ut it suffices only look the size of the set of vertices recover. In particular, if u is among the root cut, it surely induces the largest size on the set of the recovered vertices. As such, simple exhaustive search can find such a vertex and the corresponding set T. Since there are n vertices to be tested, and each test requires Onn²) ) time, the total time for each partition is at most (n²)). We can then recursively run this procedure, which will lead to partial tree that is strongly consistent in (n²) time. Furthermore, using a simple sampling trick, we could reduce the time for each test to (n log n) time and queries, which brings the total number of time and queries to Ó(")). Furthermore, since we only need to maintain counters for each vertex, the entire algorithm can be implemented in Ong space.
B.3.2. WEAKLY CONSISTENT PARTIAL HC TREES
The exhaustive search subroutine in the above idea inevitably leads to Ō(²²) time and queries the splitting oracle. This gives us new, and perhaps more intriguing challenge: if we only want to get partial trees that are weakly consistent with the optimal tree, can we improve the efficiency? Note that if we target a near-linear running time, we cannot always hope to get a u from the smaller side of the root partition. For a concrete example, let us look at the tree T in Figure 3 again. Here, before we "hit" a vertex in the first small tree of size 02.00, we will not be able to produce root cut. However, by the size of the first small tree, we will need test at least n0.01 vertices if we sample vertices uniformly at random. The overhead vertices and single vertex, and suppose this
can be further enlarged: suppose the root cut splits the vertices into process continues for n 0.99 levels; then, it is entirely unclear how to avoid the n n.99 overhead.
The vertical split idea. The above hard instance inspires us to resort to "vertical" splits of the tree that is, instead of finding a vertex u on the split of the roo,, we use a vertex u that is "sufficiently early" in the small-tree split order. To claborate, we can efficiently find a vertex u that is among the union of smaller subtrees that collectively induced at least n/polylog n leaves. In this way. we can still recover a maximal subtree whose induced leaves T of size least (n (n-n/ m/poyloo n)) -a size reduction that is significant enough for the entire algorithm to converge in polylog n iterations. Finally, our algorithm will guarantee that V is a composable set from single maximal tree, which implies that T and V T are composable sets, which allow us to recurse on both sides.
The use of "horizon sets". There is yet another subtle issue in the above idea: we have to ensure both parts of the split always maintain the weak consistency property. Specifically, it is crucial to maintain super-vertices with an out-degree of at most 2. where each is linked to at most one parent node in T and one sibling node in T Within our vertical split concept, as T invariably forms a single composable set, achieving this is straightforward. However, in the residual part of the split algorithm- V \ T-sustaninng weak consistency becomes notably more complex. There can be two cases for such guarantee to hold: either a). V \ T itself is a single composable set, which happens when V is a split on the root vertex, or b). V \ T has some "'rphhnned" vertices - the sibling vertices of the subtree induced by T in V (see Definition 28 for the formal definition).
Our approach to handle both the a) and b) cases is to use a semi-invariant horizon set Vn 2 V. The idea here is that instead of finding T on V. we find it on VH, which is roughly defined as the set of vertices for us to find the partition T on before a split on the root node. In particular, suppose the set of orphaned vertices is of relatively small size in V. We can always find vertex E V such that is split earlier than the orphaned vertex set in the small-tree split order of Vi. Therefore, we can make sure that the set T to be found in the new iteration will include the orphaned vertices in V. In this way, we always keep at most one edge connecting to the sibling of the orphaned vertices in the current iteration. An illustration of the role of the horizon set can be shown as Figure 9 in Appendix H.
The candidate vertex and root test. The above analysis assumed the size of orphaned vertices is relatively small in V. However, what if the size of orphaned vertices becomes large in V In this scenario, one of two sub-cases must happen: either we run into root split, or we have large set of vertices which is not on the root of VHH but occupies a large fraction among the remaining V. (Note that in case of root split, the entire set of V \ T is an orphaned set.) The challenge here is that we should update Vn in the former case while keep using the same Vn in the latter case, which requires us to distinguish the cases.
To this end, we employ a new idea to select a "candidate vertex" that splits away from the orphaned set to address this challenge. Concretely, since the set of orphaned vertices is sufficiently large, when doing random sampling, we can get a vertex u' from the orphaned set. Then, we use Vn to test whether there exist vertices that split away from (u', t) for
19

---

Learning-Augmented Hierarchical Clustering
sufficiently many L E VH. The idea here is that if u' is in the orphaned set, and there still exists a vertex that splits earlier than u' in (the small-tree split order of) Vn, then u should split away from many (u',t) (t) pairs. On the other hand, if u' is on the smaller side of the root cut of VH. there is only small number of t that any u E V can split away from. As such, we can make progress by either identifying the "right" candidate vertex that splits earlier than u', or by switching the horizon Vi and recurse on the cut.
Merging of two weakly consistent partial trees. In the case of strongly consistent partial trees, the merging of subtrees very straightforward: since the splits always follow the top-down order of internal nodes, we can easily merge the two subtrees with common parent node. In the case of weakly consistent partial trees, the story is much more complicated. For the merge to be correct, we have to correctly identify the "'orhhaned" subtree in the previous recursion; however, since we only have access to the splitting oracle, and the actual optimal tree structure is hidden from us, it is not immediately clear how could we identify the "correct" internal node to merge the trees.
Fortunately, we could utilize the "good vertex" from the previous recursion to identify the "orphamed" set of vertices Verphun In particular, let u be the "good vertex" we used split the tree; since u also belongs to Verphan, for each vertex v, we can test how many times v splits away from (u, t) for E T, where T is the single maximal tree to be merged in the level of recursion. If Vorphan such vertex should not split away from (u, f); otherwise, if e & Vorphan, v should split away from (u,t), f). Since the size of T is large enough, we could identify Viephan correctly with high probability, and perform the merge correctly. An illustration for this idea to identify Vorphan is in Figure 10 in Appendix H.
The complexity of the algorithm for weakly consistent frees. Similar to the case for the strongly consistent trees, the subroutine that gives the sibling of a small tree for fixed vertex u takes ( time. However, in the new algorithm, we only need sample and test Ollg n) vertices u for each iteration. Similarly, the root test and the tree merging subroutines both use Olog n) vertices and Ó(n²) time. Furthermore, since we can roughly reduce the instance size by (1 1 1/polylog n) factor every iteration, the entire process converges in polylog iterations. As such, we could argue that the total running time is Ö(n²), ), and the longest chain of dependent calls is polylog n. This would imply near-linear time offline algorithm and a parallel algorithm with near-lineat work and poly-logarithmic depth.
C. Missing Proof' of Section 4 (Dasgupta's 's Objective)
We give the proof' we skipped in Section 4 in this section.
C.1. Missing proofs of Section 4.1
Formal proof of Theorem 1. With Algorithm 1, we can obtain the poly-time efficiency from Lemma 4.1. Furthermore, since the strong partial tree algorithm of Theorem 10 succeeds with high probability, the approximation guarantee of Lemma 4.2 holds with high probability as well. This concludes the proof.
C.2. Missing proofs of Section 4.2
Proof of Lemma 4.3. The first step of the algorithm that computes the strong partial tree takes O(n log time and O(n²) queries by Theorem 10. We need to argue that the second step takes most O(n' log time as well. Note that by Proposition 18, the algorithm, with high probability, runs in Ö(s²) time and finds an O( O(Vlog >)approximattinn of the sparsest cut (A, B), where is the input size. In our case, for a single super-vertex of I with |X| < 50000 log n, the running time is therefore O(log" n) only. By Fact A, there are at most Ollog n) nodes in a binary tree with O(log n) leaves, which implies Olog" n) running time for a single super-vertex. Finally, with at most (n) super-vertices in the tree, the second 3 n) = Ore² log time, as desired. step only takes (n log
Proof of Lemma 4.4. Similar to the proof of Lemma 4.2, for any partial tree I, we first partition the edges in to Eemos and Esae based on whether the edge (u, v) E E crosses different partial trees, i.c.,
1. (u, u) E Eccoss iff u E X and u E Y for some super-vertices X + Y in I.
2. (u,,) v) E Fsame iff u, V. E X for some super-vertex X in I.
20

---

Learning-Augmented Hierarchical Clustering
Again, by using Observation 1, we can show that OPT cost costo(T", E1) costa(T" E2). The costs to Ej and Eg therefore as follows.
1. For Ecross, we have that costa (T, Ecross) = costa (T", E by using the same argument of Lemma 4.2.
2. For Esame: we argue that costa ) I O l) costa(T", E Formally, since algorithm in Proposi- tion 18 finds an O( log spappoooxmtaiion for each super-vertex X, we can use Proposition 17 on G[X] to argue that the cOsta((T Fasaee x & OVolo n)) costa(T", Fsame| (X]) since 8 = O(logn). Therefore, we can apply the same argument to every super-vertex to get the desired approximation factor.
We now Observation 1 again Exross and Exame to bound that
costr;(7) = costa (T, Eemos) + costa: Esame)
I costo (T" Eaoos) O log log n) costa (T .Eaame)
I 0 O(vloo log (costa F + costa (T*, -Esame)
OVVooglloo logn) CTs - 0 /og logn). OPT Das
as desired.
D. Missing Details of Section (Moseley-Wang Objective)
We now prove the approximation guarantee of Theorem 3. To this end, we will show the following technical lemma that lower bounds the number of non-leaves between T and T
Lemma D.I. Let T be a hierarchical clustering free obtained by Algorithm 3, and let u, v E V be any two vertices. Then, conditioning on the high probability event that I is a partial tree that weakly consistent with T*, there is
If u and in the same super-vertex X of then, there is
v)]l 2 n 50000 log n.
u and are in different super-vertices X and Y of then, there is
moonlleavesyLLC.. r) |oon-eavesr u)]l 50000 log
Furthermore, if
(X))
=0,
then, we additionally have
Mon-leavesy(ICAA/y w)] |non- -onn-eevess-ll (onn-Lavesr-LLCArrie LCAT- v]]l
Proof.
We prove the two cases separately as follows.
u and v are in the same super-vertex X of I. By our construction, every leaf that is outside the subtree induced by (LCA))) counts non-leave of (u, As such, since |X| s 50000 log it is straightforward to get that
Ionn (T. (U, w) 2 n 50000 log n.
u and e are in different super-vertices X,Y of Suppose w.log. that u E X and v E Y. By the subtree preserving We now discuss further two sub-cases:
property, we have L LCA7 (u, v) leavesy [LCA
a). If (1CVe (X)] and leaves (Y) disjoint. In this case, have exactly leaves7 [LCA7 (u, v) which implies Leavesr[LCAr(1, v)]
Leaves7 (X UY)] (1CAT (u, v) Therefore, we have
Sonn-Leveey/LCAr/e v) l (LCY [CCA- v)
This proves the "furthermore" part of the second case.
21

---

Learning-Auggentted Hierarchical Clustering
b). If [LCA))) and (eAVes)-(ICAT--O)) have intersections. In this case, that by
the weak contraction property; and (ECAT-)-(CCAT--)) Leavest-[LCAr] (Y)), the differences between (LCess--LCAA-(AA is at most the set of X. Since | < 50000 log n, we have
must have inclusion relationship between leavest: [LCAT- Suppose without loss of generality, that leavesT-[ICAT] and leavesr-[LCA,, (u, v)
(LCAT- (X)
2
(u, w)]l
(u, e) 50000 50000 log
as desired.
This concludes the proof of Lemma D.I.
To prove the approximation guarantee of Theorem 3, will need handful of structural observations for the optimal HC trees in the Moseley- Wand objective. We first observe that for any optimal HC tree T necessarily has "monotone edge weight" property between an internal node and its descendants.
W1
103
Other leaves
A
D
B
C
Figure 4. An illustration of the edge weights and leaves described in Claim D.2.
Claim D.2. Let 21 and 22 be any internal nodes of the optimal HC tree T under the Moseley- Wang objective, and let 22 be descendant node of 21. We use wi and w2 denote the total weights of the edges induced by 21 and 22, respectively. Furthermore, let wa be the total weights of the edges induced on the internal nodes between 21 and
Suppose the partition induced by 21 is S SA, A), and let B and C. be the set of vertices induced by 22 such that JUCSS) A. Furthermore, let = (S) A) \ (B U.,, and suppose max{[B], 2 |A]. Then, there
w1 (
[A]
+ 1) -33
W2
[ + D
max ( [B
An illustration of the edges and leaves used in the statement can be found in Figure 4.
Proof. The claim is similar in spirit to the "switching lemma" under Dasgupta's 's objective as proved in (Høgemo et al., 2021). Suppose w.log. that B |C]. For the purpose of this proof (and also that of Claim D.3), reve (T, F1) be the revenue
22

---

Learning-Augmented Hierarchical Clustering
induced by subset of edges Ej with T being the HC tree of G. We further observe some useful relationships between the weights W1, W2, tg and the weights v( (A, B), wo (A, C)2 w(A, D), wBB, C), u/ B, D), and w((C, D) follows.
W1 w D) + w (A, B) (A, C)
w C) W2
w3 2 w(B, D) + w(C, D).
We first prove self-contained structural claim that the edge weights between A and B cannot be too much bigger than wa. More formally, the claim is as follows.
Claim D.3. Let A. B, C, and D be the set of vertices and w1, w2, and Wa be the edge weights as prescribed in Claim D.2. Furthermore, let (AA, B) be the edges between A and B, and w(A, B) be the weights of (A,, B). Then, there is
A D
w( (A, B)
W3-
[C]. Let us construct a tree T()) based on T by switching the subtrees induced by A and D. Note that in such change of HC tree, the only edges that will have changed revenue are ((A, B), E(A, C), E(A, D), EBB, C), and edges accounted by wa, which we call E3 (including but not limited EBB, D) and ECC, D)). and edges in. We list these changes follows.
Proof. As consistent with the proof of Claim D.2, we assume w.log. that |B| 2
1. E(A, B): we have that rev (T EA.B) reva(T EA,B) 2 |D| w(A, B). 2. E)A,)): we have that rev. (T)),, ( EA.c) reva(T" EA,c) 2 DD| w(A, C).
3. E(A, D): we have that reva (T()) (A.D) reva ,T,,,A, = =0
F(B, C): we have that ( FBBC)) reva(T" F.B.C) = O.
5. Eg: we have that reva(7 (T 2 W'3 |A].
To maintain the optimality of T there should be reva(T()) reva(T") S 0. As such, we have
0 2 reva(T(2) (2)) reva(TT)
(revc(T()) (1, EA,B) reva EA..) (reva(T(),
EAAc) ((Cc(T((E,A,.)))) - revo(T', ,E,,))
+ (revG(T(W,, EADD) revo EA.D)) (revo(T()), revo (ev,((".BB,C)
+ reva(T E3) (TV 2 (w, + C)) |D| w's |A|.
As such, we can move the terms around, and obtain that
|A| D
(A ( < W33
desired.
Claim D.3 P
We now Claim D.3 to prove Claim D.2. We again construct a tree (22) based on T by switching the subtrees induced by A and B (note that this is different from the proof of Claim D.3). Observe again that only the edges that have different revenue contribution in (2) vs. T are E(A, B), E(A, C), E(A, D), E(B, C"), and edges accounted by W3. We again list all the changes of revenue induced on these edges.
1. E(A, B): we have that rev. (T EA.B) reva(T* EA,B) 0.
2. E(ACC) we have that rev. (2))), EA.C) reva EA,C) Z ([B) + [D]) w(A, C).
3. E(A, D): we have that rev (2)), (AAD) reva .A,)) Z B ww w.A D):
F(B, C): we have that (T) FBBC)) revo FB,C) 2 -[4 + DI) w B, C).
23

---

Learning-Augmented Hierarchical Clustering
5. Eg: we have that rev Eg) reva(T", EB3 - -Al wg- w3-
Therefore, by the optimally of T there should be reva(T(2)) reva(TT) 0. As such, have
z (T reva(T))
= (revo(T FA,B) - reva(T" FA.B)) - (revc(T(2) (((G(((()FF,,)) - revalT", FA,C))
+ (reva(T(2) ((evG(((),EA,,)) - reva (T", ..A.)) (TeVv(("EE..)) + (reva(T(3),
EB,C) - EB,O))
+ (reva(T()) Es) - reva(T" Ess)
2 (BB) + [D]) (A, C) + B w D) (14) + IDI) w(B,C) w/ |A|.
As such, by moving the terms around, we can get that
[] (w(A C) w(A, D)) s (I + [P]) w/ (A,C) [B] w(A, D)
{ + PI) C) |A] w3-
We can use the observation that w1 = w(A, B) + w/ A, C) + w(A,,,,, D) to obtain that
B = (w(A, C) + w A, B) + (A,
$ [1A| + DI) w B, C) + | Wy + B w(A, B)
by adding B w(, B) both sides. Now, we can apply Claim D.3 to obtain that
A
|B| wi < (IA) + DI) w (BC)) + |A|
W3 [B]
W3
D
|
S (I4) + DI) w B, C) + B W3 +
[B]
W/3
(using |A| $ BB)
D
Note that wBBC) W2. As such, the above implies that
A Ww's S (IA)
[B]
W1 (1 +
DI) w2
Moving the turns around in the above inequality gives us the desired bound.
Claim D.2
We now use Claim D.2 to show that the set of edges (u, v) such that
a). has at most (log² n) non-leaves T and
b). let and Y be corresponding super-vertices that contain u and in a weakly consistent partial tree I; there is leavest- (ICAT 0.
leaves7: [LCAT-
can contribute to at most an o(1) fraction of the optimal cost. This means that our estimation with non-leaves using Lemma D.1 would lead to a good approximation. The formal statement as follows.
Lemma D.4. Let I be an arbitrary partial HC tree that is weakly consistent with the optimal HC tree T under the Moseley-Wal Wang objective. Define Erow C V x V as the edges such that for any (u, v) E Erow (I), there is
a). |nov-leavesy- (iaoveess-LLAA(( [LCAT-(u, v) < 50000 log" n.
b). Let X and Y be corresponding super-vertices that contain and in I; there is
LeavesT-[ICAAT O leavest. [LCAT (V) + 6.
24

---

Learning-Augmentee Hierarchical Clustering
Then, for sufficientll large n, the total contribution of revenue from the edges Flow (I) is at most 50000 log fraction of OPTMW i.e.
log* n (LCAT- (u, w) S 0
E
w(e)
OPTMW
e (W
Proof. For any two super-vertices X and Y in the partial HC tree I, by the weak contraction property, if Leavesy- (ICAA-(() n Leavest- (LCAT- (EEAA-()) (Y) is not empty, the only possible case is to have inclusion relation- ships between the two sets of leaves, Suppose w.log. that leaves7- [CAA leaves7- (LCA)-(Y)] Let Ý be the set of vertices induced by the sibling node of in I, and it is straightforward to see that C Y. We further let y' be the larger immediate child of the tree induced by Y.
By the conditions of t). nno leavesr LCAT (u, v)] S 50000 log" n, ii). |X| 5000 log n. and iii). the inclusion relationship between the leaves, there is
50000 (log* 2 + logn)
50000 (log² n + logn):
Y
2
We now use Claim D.2 inductively to bound the weights of wo E(E for the sets edges Ej S Enow that are split by some internal nodes of X. Let Eg be the of edges that is split the subtree induced by Y', and let X be vertices that are split by Eg and as the sibling of Y. Our induction hypothesis is that
C logn n w( (E2)
w (o) <
50000 (log" 2
log
for some absolute constant C.
To prove this statement, we first look at the base case. By the size bound on X, it is straightforward to see that
x
50000 log
In the base case, we pick edges En C Flow such that Fg is split immediately after Ej, i.e., Ej the edges between X and Y. Now, we can use Claim D.2 with A + X, B +- Y', and D 0 (wz 0) to argue that
w E X
E
w E2) |Y
By the size upper bound of X and the size lower bound of Y", the above inequality implies that w (2))
C log w(Eb) (b)) 50000 log n n 50000 (log" n + logn) 50000 (log" 2 n + log
w wE)
for any C > 2, which proves the base case.
For the inductive step, let us suppose the statement holds until some internal node z, and we look into Ei C Ejow that is induced on pa (z). We again use Claim D.2 by letting A + X, < Y', and D + \ X. Define E3 as the set of edges that are split between z and LCAT- (Y). By the induction hypothesis, for every node between and LCAT- (Y), the total induced weights is most
C log ni w(E2)
50000 (log* logn)
Furthermore, since [X|
X
< 50000 log n, and 2 and pa (C)AT-(P)) are in the same X of I, we can bound the total
X
weights in E3 as follows
C. logn w(E2)
w (Ea) < 50000 log n 50000 (log* n + log
25

---

Learning-Augmented Hierarchical Clustering
Furthermore, by the size upper bound of X, have AA| us that for sufficiently large n, we have
[D]
< 50000 log n in Claim D.2. Combining the above gives
X w(Ei)
1) ((EB))
1 ((E)) E1) 2 X
wn (( (50000 log 1) w(Es)
w( E2)
[X]
X
Y
where the first inequality follows from the fact that w(Ea) 0 ( w (E2).. the second incquality follows from that x
/
= |||
I 50000 log n, and the last inequality follows from Claim D.2. Therefore, we can again obtain that
w(E))
4 w(E2)
100000 log n
50000 (log* 2 + l)
which means w(E)) <
n n 50000-(1og" llog" notlog n) for a sufficiently large constant (C 400000 suffices). This concludes our inductive proof for the weight bound of any E1 C Ejow in any X.
C-log R-wnl Ex)
Using w(E)) S a 50000-(log' #+logn) revenue is
C-log n
(((Ee)) for any (u, v) E Ejow. we note that a trivial lower bound of the optimal
OPT = 22llog n (x)))),
since this is the revenue induced the edge set Eg only. On the other hand, since we need the inclusion relationship between the leaves, and by the fact that the number of non-leaves is at most log" there are at most 50000(1og* n log n) edges in Eoo,, i.c.
Ejow| I 50000 n + log n.)
Therefore, the total contribution of revenue by Flow most
Σ
w(e)
v)]l
= (u,D)E Fam (I)
Σ
w(e) log*
(by the number of non-leaves)
Fo. (Z)
< max (1))
E1 E 50000 log 12) -log* n
(uniform upper bound)
C log n
ww Fez) 50000 + logn) log"
n 50000 (log* n + logn)
(by the relationship between wr (Fe) and w (FFE) for Eg S Elow)
log* 4
< 0
OPTMW,
(by the lower bound of OPT
as desired.
Finalizing the proof of Theorem 3. We have discussed that the algorithm enjoys Ó(1²² running time and O(n²) query efficiency. For the approximation guarantee, note that each edge (u,v) gains a revenue of wa, nno - wew.eleeeeeeeee [ ]] in the optimal tree T For edges (u, v) & Eiow, let Li be the set of edges where and are in the same super-vertex, and Ediff' be the of edges where u and in different super- We now have
For edges in Esame we have hon-le (IC.veess[CAAAAC (CAT(U, v)]l 2 n 50000 that by Lemma D.I. On the other ligh
26

---

Learning-Augmented Hierarchical Clustering
hand, any vertex pair has at most n non-leaves in the graph. Therefore, we have that
rev Fagg
(T)
Σ E B Ligh
w(e) [non-leavesy/LCArrr
v)
Σ
w(e) n 50000 log n
eE Ligh
w(e) n (1 50000 log
cE high
50000 log n
IV
rev GOVGnE Ligh
(T*).
For edges in high we have
Inon Lea-Lsevves/LCAAr b) nno moon-leaves7 [LCAT- (u, v) 50000 log
1 Lhon-leavesr- (u, v)l1,
(1 0 log
where the first inequality follows from Lemma D.I, and the second inequality from the fact that Inon-leavest- LCAT- (u, e) 2 50000 log" for every (u, & Eaow As such, have that
rev one (T) = Σ w(e) | (LCA7(u, w)
E&a
Σ
wle) wwl. (LCCT (u, u)
log
eE Eug
0 rev
GrEai (T*).
logn'
Therefore, by additionally using Lemma D.4, we have that
(T) 2 rev Greune (7) + rev Gridi (T)
2 (1 - O
rev Engg (T*) + rev on
GnEar par (T*)
log n
2 (1 O
rev GeVGreeus (T*) + rev On EoUIT (T bash
log
log* 1 (1-0( 0 (oog""))) ) (T)
> 0 log n
(using Lemma D.4)
n
M (1 o(1) revo(T"),
desired.
Remark 20. We can observe that if we run Algorithm 3 with the strongly consistent partial HC tree, we can get a similar (and even stronger) approximation guarantee, albeit with worse efficiency (O(n²) time). Concretely, note that if we use the strongly consistent partial HC tree, the additive error again only happens Esame, and we do not need Lemma D.4 to further decrease the o( term to O log However, the sacrifice of the running time is too significant, and we skip the details of this algorithm.
bound the contributions of the edges in Enow (I) (since 0). In this way,
E. Missing Details of Section 6 (Sublinear Algorithms)
We discuss the analysis of the algorithms and their analysis for the rest of this section.
E. A single-pass semi-streaming HC algorithm for Dasgupta's objective
We present our algorithm for the semi-streaming algorithm this part. To begin with, we need to define the model for streaming hierarchical clustering with the splitting oracle.
27

---

Lcarning-Augmentedd Hierarchical Clustering
Graph streaming with offline splitting oracle. We focus on the (dynamic) graph streaming model with the offline splitting oracle. In this model, the edges of the graph are inserted and deleted (together with their edge weights), and the algorithm is asked to output an HC tree by the end of the stream. Additionally, the algorithm is given an offline splitting oracle O before the graph stream, and the algorithm is allowed to make unlimited computations before the stream starts. The total memory cost is the total number of bits the algorithm maintains at any point, including those dedicated to edge representation and those generated through offline computations.
For polynomial -immm time efficiency, we assume that the stream itself of poly(n) length since otherwise, the stream itself will take super-polynomin time to complete. Under the above model and setting, the formal statement of our result is as follows.
Theorem 21. There exists a single-pass (dynamic) streaming algorithm that given a weighted undirected graph G (V, E. w) in a poly(w) (n) -lengh dynamic stream and an offline splitting oracle O with high probability, in O(n log n) (bits) space and polynomial time computes a hierarchical clustering tree T such that (TS - 0(1) OPT (G), where OPT (G) is the cost of the optimal hierarchical clustering free T i.e., OPT (G) = (T
Proof. The algorithm is to simply first construct a strong partial tree I with the algorithm of Definition 8 before the stream starts, and store edges only inside the same super-vertices during the stream. By the end of the stream, we compute recursive sparsest cuts the vertices induced on super-vertices of I, and output in the same manner of Algorithm 1. The formal description is as Algorithm 4.
We first prove the time and space efficiency. Essentially, Algorithm 4 computes a strong partial tree I before the stream starts, and only main edges inside each super-vertex of (log size. By Theorem 10, the pre-processing part takes polynomial (O(n2 log 12)) time and On log n) space. Furthermore, for each super-vertex, we maintain most (log² n) edges; each edge could have at most poly(n) updates, which means an additive space of Oloog n) bits suffices for each edge. Therefore, most super-vertices, which means the algorithm maintains the 2 n) edges, which takes (n log" n) bits. After the stream, we partition the super-vertices with the edges stored, and write down the rest of the HC tree, The time efficiency of the post-processing part is exactly as Lemma 1.
we record at most Ollog n) bits for each edge. There
information of (n log"
For the approximation guarantee, note that we are essentially simulating Algorithm 1 with the same input and output guarantees. As such, we can simply use Lemma 4.2 to argue the approximation guarantee.
E.2. Parallel HC algorithms for Moseley-Wang Objective
We now move the PRAM hierarchical clustering algorithm for the Moseley- objective with near-linear Ö(n²) work and polylog (n) depth. The formal statement of the algorithm is as follows.
Theorem 22. There exists a PRAM algorithu that given a weighted undirected graph G = (V,E,w) and a splitting oracle O, with high probability, in Onn².. polylog n) work and polylog n depth computes a hierarchical clustering tree T such that rev (T) 2 (1 - o(1)) - OPTMW (G), where OPTMW (G) is the revenue of the optimal hierarchical clustering tree T*, i.e., OPTMW MW (G) = (T*)
Proof. The algorithm is to run the PRAM weak partial tree algorithm in Corollary 12 to obtain I, and arbitrarily partition the vertices in the super-vertices of I. The formal description of the algorithm is as Algorithm 5.
By Corollary 12, the first step that computes the weak partial tree I only takes Ö(n²) work and polylog depth. For the second step, since the partition is arbitrary, can simply perform arbitrary balanced cuts on the vertices for each super-vertex X. For an individual X, this procedure can be done in O(logn log log n) work and O(log logn) depth. By accounting for all the super- vertieeer we blow up the work by at most an ((n) factor and the depth remains the same since we can partition super-vertices in parallel. Therefore, the second step takes O(n log? n) work and Olog log n) depth. Therefore, the entire procedure takes Ónn²) work and polylog n depth.
The output of Theorem 22 follows exactly the same rules of Algorithm 3; therefore, the approximation guarantee follows from Theorem 3.
Remark 23. By the reduction of Proposition 14, the result of Theorem 22 also implies fully-scalable Massively Parallel Computation (MPC) algorithm that computes the HC tree T with (1 - o(1)) OPT (G) revenue in Ó(n²) total memory and polylog n depth. The memory on each machine here is allowed to be O(z²) for any a E (0, 1), and we use Ō(n²~9) total machines in the MPC algorithm.
28

---

Learning-Augmented Hierarchical Clustering
F. Preliminaries for Partial HC Tree Algorithms
will discuss the construction partial HC trees for rest of this paper (Appendices F to H). In this section, we first introduce the several notions that are essential in the analysis of the partial HC tree algorithms. We use these notions extensively in the analysis of both Theorem 10 (Appendix G) and Theorem 11 (Appendix H).
In the high-level overview, slightly abused the notation use V to denote the subset of vertices, In our formal description
of the algorithms, we will use V S V as the set of vertices of the current recursion step, and use ñ V as the size of the set.
F.1. Composable vertex sets and restricted subtrees
To continue, we first introduce the notions of composable vertex sets for graph and the HC tree restricted the sets. Definition 24 (Composable vertex sets). Let G (V, be n-vertex graph and T be hierarchical clustering of G. For subset V V, we say V is a composable (vertex) ser of (G, if V be written in disjoint union of the leaves of maximal trees, i.e., union vertices V = U,V. such that all V; satisfies that
Teaves7[ICA77A/ V,
In the special case, we say V is single composable (vertex) set if there only one such maximal tree, i.e., [LVV
In other words, if vertex V composable, it means we only look the leaves of V, they still form subtrees of T. illustration of composable sets be found in Figure 5.
Single C Composable Sets (Vertices of M Maximal Subtrees)
General C able Sels Nota Maximal
Figure 5, An illustration of the composable vertex sets and maximal trees in Definition 24.
We can define the HC tree restricted to composable subsets of vertices as follows.
Definition 25 (Hierarchical clustering tree restricted to subset). Let G (V, F) be a n-vertex graph and be a hierarchical clustering G. For any composable subset S C V such that |S|] 2 2, call T(S) as restricted to if T(S) is new binary tree constructed with the following process
29

---

Learning-Augmented Hierarchical Clustering
1. Extract T' from T by taking the induced subtree of the internal node LCAr(S).
2. Remove all subtrees whose leaves contain only vertices not in S from T'.
3. there exists an internal node a that only has a single child, contract x and its child to one node. Repeat until all internal node has two children nodes.
Note that the algorithm in Definition 25 is a thought process, and it only serves the purpose of analysis. The third line eventually terminates since there exists least subtree with leaves for any composable set S with least two vertices. An illustration of HC trees restricted to subsets can be shown in Figure 6.
T
T(S)
8
Sa
S6
S3
85
S4
5
Figure 6. An illustration of the HC tree T to he restricted on a subset of vertices S.
We now provide the following observation that the tree T(S) preserves the relative order of split away vertices of T. Observation 2. For any triplet of vertices (u, v, w), the orders of split-away for (u, v, w) are the same T(S) and T, i.e. w splits away from (u, v) in T(S) if and only if w splits away from (u, v) in T.
Proof. We first observe that the orders of split away for any triplet (u, v, w) are the same in T and T' since T is subtree of T. Furthermore, since S is conposeable set, every subtree remove from T' is necessarily maximal subtree, i.e., fix the removed vertex set S. the leaves of LCAT (S) is S itself.
Let x be the lowest common ancestor of (u, v) in T', and x' be the lowest common ancestor of (u, U, w) in T'. By our definition, we have level (1')) > level (x:). In TSS), if none of x and xf is contracted line 3, then the order of splits away trivially remains the same as T'.
On the other hand, if at least one of and x' is contracted, and let the new internal nodes be y and y', we claim that there > level (v)) This is simply because every removed tree is maximal tree, and the only case that
still 1 level l y and y are merged is that the induced vertices of y become empty, which contradicts the fact that (u, v) is not removed. Therefore, the split order between (w. u, v) is the same as in T', which in turn is the same in T.
F2. Small-tree splitting order
We now introduce the following notion of small-tree split order, which frequently use in analysis.
Definition 26 (Small-tree split order). Consider any subset C V and the hierarchical clustering tree (*(S) restricted to S, and consider the following process that divides leaves S:
30

---

Learning-Augmented Hierarchical Clustering
1. Starting from the root let the split be S + (S), St), and assume w.log. [S] (leaves) induced by the "smaller subtree" s/
<
|
Let Vismall be the vertices
2. Starting from the lowest common ancestor of S7. recursively define Vi as the vertices contained in the "smaller subtree" of level & (by splitting from the "larger subtree" of level 8 1).
For the convenience of notation, we define Vi = 0 when is larger than the depth the tree. For any integer E [0, norrs we can define the first N vertices the small-tree split order by taking the first N vertices in the order of V V etc.. Inside each set V V.small pick vertices an arbitrarily fixed order. We use the notation //saal (s. .N denote the first N vertices in the small-tree split order, and we use //small (2 N) denote the last N vertices in the small-tree split order.
Intuitively, we can think of the small-tree split order we always write the "smaller" tree on the left-hand side, and recurse on the "larger" tree for this procedure, then take leaves from the left-most vertices. Note that every vertex has to belong to V.small for some i. An illustration can be found in Appendix F.2.
Based on the notion of small-tree split order, we can define the notion induced leaves of the first or last N vertices the small-tree split order as follows.
Definition 27 (Induced leaves of the first split vertices). Let (S) and be the hierarchical clustering tree and the set of leaves. For any integers N [0, nH], we define the induced leaves of /small I N) as the union of the U V V.sall where É is the maximum level such that 1/amali contains at least one vertex in / (< N).
An illustration of the induced leaves in Definition 27 can be found in Appendix F.2.
S) <
1 (15))
N) PIN
Figure 7. An illustration of the notion of small- tree split order Definition 26 and the Induced leaves of the first split vertices Definition 27,
G. The Algorithm for the Strongly Consistent Partial HC Tree: Proof of Theorem 10
We now give an algorithm for partial trees that are strongly consistent with the optimal HC tree T We first remind the readers of our main result on the algorithm for strongly consistent partial HC trees as follows.
Theorem 10. There exists an algorithm that given a splitting oracle O of a weighted undirected graph G = (V, E, w), with high probability, in 3 log n) time and O queries computes a partial hierarchical clustering tree I that is strongly consistent with the optimal hierarchical clustering T". Furthermore, the algorithm has the following properties.
The runtime of the algorithm is deterministic, and the high probability randomness is over the correctness guarantee.
ii. The algorithm can implemented in On log space.
We refer the readers to Appendix for a high-level overview of the algorithm. We directly give the algorithm and the analysis in this section.

---

Learning-Augmented Hierarchical Clustering
The algorithm. We introduce our main algorithm for the construction of strongly consistent partial HC trees. To begin with, give 'helper function' counterpart- weerrttttteereee trng follows. As have discussed in the high-level overview, this function tests the 'sibling vertices' of small tree that is 'early enough' in the small-tree splitting order.
strongl(O.vin Vanu) (u, 6, threshold1, thresholdg): an algorithm to test whether / Algorithm counterpart tetttterrrrrtttttteeeeee tester--e--ee -ester-sttooggO
among the "counterpart" of
Input: Vertex set Vinpar' the splitting oracle O; baseline vertex test vertex threshold, E (0, n). threshold2 E (0, n)
Output: Whether e is "counterpart" of u
Initialize counters C1 <- 0, C2 t O for Every vertex & E Vinput do If e splits away from (u, t), increase ej by If splits away from (u, v), increase og by end
if < threshold, and S threshold, then
Return "v is counterpart of u".
end
Our main algorithm for the strongly consistent partial HC tree construction is as follows.
algorithm for strongly consistent partial tree Input: Vertex set V size ñi; the splitting oracle O; parameter E < a sufficiently small constant Output: partial tree Ty that is strongly consistent with T (V)
Algorithm 7 strrong-arrtill-t:en
S 50000 log then
Return super-vertex
end
for Each V do
Initialize T + 9 Sample a set of 20 log n/E2 vertices from V for u V do Run counterpart song (0.5) (u, v, =) (1/6- Add v to T' is "counterpart" u
end
Record the size (T) for this choice of
end
Pick (T (T) such that T +- T is with the largest size (breaking ties arbitrarily) Recursively call
Tra-- strong- partsn---atttataeeeaae
(*)) Tr- strong strong- partial-tressee (T*).
Connect the two trees with common ancestor as the root
We first observe that the algorithm takes mnstō(n²) queries to and O(n2/e² time. The formal statement and analysis follows.
Lemma G.1. The algorithm strong sarong-partial-tteed takes at most O(n²) queries O and Ó(n log n/ n/e²) running time.
Proof. The On query upper bound is trivial since there most (*) such comparisons, and the algorithm store the answers for reuse. For the running time, we claim that each recursive call on
partaaataaaa -teetree o (V) with vertices takes at most ( log ï) time. To see this, note that each call Line 7 takes at most (logn//s) time, and there are at most (nz²) calls the counterpart teweett-ttttteessttttete function, By Fact A.I, there are at most (n) such recursion calls induced on internal nodes, which results at most On log n/=²) running time.
We now prove the correctness of the algorithm. To this end, first establish the split-away relationships between the vertex set V. and the sampled set S.
Lemma G.2. Consider quantities Cy, 022 Et and &2 obtained by the following processes of running Algorithm 6:
32

---

Learning-Augmentedd Hierarchical Clustering
Let ej and og be the counter returned by comterpaart-esterrssttoogg v, (3/5 8). (1/6 -))
(i.e., by running line 7).
Let ε and 02 be the counter obtained by running
3d/5, n/6).
Then, with high probability, the following statements are true.
Ifā: 2 and 02 2 n/6, then 61 2 (3/5 -) and c2 2 (1/6 E)
Ifa < (3/5 - 2e) and 02 < (1/6 - 2-))- nt then ei (3/5- 8 and c2 < (1/6 -)
The lemma is a direct application of Chernoff bound, and we prove the quantities for ei and č₁ only since the relationships between 0g and 82 follow from the same argument. For each fixed pair of (u, 2) as the inputs to Algorithm let T C V be the set of vertices in V reporting "v splits away from (u, ()". It is clear that [ č₁ Furthermore, define X,
Proof.
as the indicator random variable for the sampled vertex E T S and X as the total number of answers reporting "V splits away from (u, t)" S. We have E
[X] Eves Pr(X,, = 1) = s-ē1
a
If 35/5, have that E [X] 5, and X is summation of independent indicator random variables. Therefore, by Chernoff bound we have
3 Pr x ( -5555-)00 8).8)
1
< Pr [[X] < < S exp -2
exp (040log
10 n²
where the third inequality is by the choice that 20 n/e2. : On the other hand, if (3/5 2s) n. we have that E [ < (3/5- 2z). Therefore, by Chernoff bound, we have
38 X Z
< Pr - E X 2 e 8) S exp (-2. =²0²² (-2.--))
1
Pr
< exp (-40 lognl <
5
10 n²
where the third inequality is by the choice that s 20 20logg// n/e2.
Using Lemma G.2, we now present the following key lemma for the behavior of the "counterpart-tess" of Algorithm 7.
Lemma G.3. For any composable V such that V 2 50000 log n, let E be the maximal level that Vi contains a vertex in /mmall (< i/5). With high probability, Line in Algorithm 7 satisfies the following properties.
a). For any vertex u E E V.saall there is
No vertex u E - V.small can be added to T by Line 7 of Algorithm 7.
No vertex - can be added to T by Line 7 of Algorithm 7.
b). For every level S E" and vertices Viamall, with high probability, there
No vertex Viumall can be added to I by Line 7 of Algorithm 7.
No vertex u E Viimall for can be added to T by Line of Algorithm
c). There exists a i S E such that | V.small >
25. and for any S i and any vertex E Vamall, with high probability, all vertices v E Vamall for k > are added to T by Line 7 of Algorithm 7.
Proof. By Lemma G.2, we only need to prove the split-away properties on V, and the split-away properties on S follows. Let h be the maximal level that the / /zmmali contains a vertex /ssall/ (S n/55), and suppose the split on this level results in (Sf". ) We assume wllog. that s I | so that Sf becomes Vismal), We first observe structural property.
Observation 3. The size of the vertices in VH \ /small (< n/5) (and equivalently U +1 V,sual) satisfies
2n
4ñ
< | Lamall
<
5
5
33

---

Learning-Augmeented Hierarchical Clustering
Proof. The upper bound follows from V (< R/55] n/5, as otherwise Vsmall n/5) will not have enough vertices. For the lower bound, note that by level - 1, the size there are still more than 5 that U V.small collectively forms the 'larger subtree' w.r.t. Va As such, its size has to be more than 1
48 vertices remain to be decided. Also, note
4n
26
2 5
5
for any We now proceed one-by-one to the proofs of Note that by the definition of small trees, we also have [Vamall| S 2 Item a)., Item b)., and Item c)..
Proof of Item a). Fix any vertex - 1 V.sall For the first statement, note that for every e E - V/smali, all the vertices in Uf_11 V.small are splitting away from (u, v). Define Xun,, as the indicator random variable answered by O as "t splits away from (u,u)" and define X., = =EIE Xu,r,t as the total number of vertex split away from (u, v). By Observation 3, the expected number of split away reported by oracle is at least
9 n2
9
E X
7.
10
5
50
Note also that Xu,v is summation of 0/1 independent random variables. As such, can apply Chernoff bound to get that
fi
25
Pr
Xu,v
= Pr
X
E [uu,e]
27
(2/27)²
< exp
E [x
3
1
9 ñ 2 9000 log using the lower bound on the size of V) 50
10
n²"
For the second statement, note that for any E - V.nalll v actually splits away from (u, t). As such, there is least d8 vertices such that "v splits away from (u, t)" this is because the LCA between (u, v) has to be higher than the LCA between (u, 1) for any E U V.small. As such, define Yu, as the number of total answers of "v splits away from (u, t)* by O, we again have
9
4m
18
E YY w
n.
10
25
As such, we again have
3m Pr
15
Pr
Yu,o -
Yu,o S
IE [Xu.v]
18
$ 10 n
9
á 2 9000 log using the lower bound on the size of V)
50
By union bound over at most n vertices, no vertex v E - umaall or - +- smmall can pass the test and be recorded 'counterpart'. Furthermore, by Lemma G.2, if X., n/6 and Yu,r > 3n/5, then such cannot pass the test on the sampled set S, which is as desired. This part of the proof can be visualized as in Figure 8(a).
I=1
Proof of Item b).. We now show that vertices we claim that there are too many vertices & that split away from (u, v). To see this, let us define Au, as the total number of
V cannot pass the "counterpart" test. For vertices in Visail
answers of "t splits away from (u, v)" answered by O. Note that for any vertex & E U ( V/amall, the answer is always
"yes" since *" > /2 E. Therefore, we can lower bound the expectation of Au, with IE [Au,v] > 2 g 2 -. Therefore. can apply Chernoff bound to get
To
Pr An, S h
< exp (1122) LE [AA...]]
1 1
10 n3
We now turn to the vertices that are in uf=1 Vamall Note that by definition, there is V
2 | V/small 2 2 i..
For any E u /amall v splits away from (u, t). As such, define BuG as the number of answers by O with "v splits away
34

---

Learning-Augmented Hierarchical Clustering
from (u, ()", there is E [Bu,e]
n. Once again, by applying Chernoff bound, there is
25
3n
(1/5)²
1 1
Pr Bu.e I
< exp
3
10 n
Applying a union bound over the cases and all n Σ n vertices and using Lemma G.2 would lead to the desired statements. This part of the proof can be visualized as in Figure 8(b).
Proof of Item c).. We fix é as the minimum level such that the union of Uf V.small has at least h/25 vertices. Let & S é, and for any vertex v in Vigmali for k > f, define the following two random variables: Xu. as the number of answers that "/ splits away from (u, v)", and y,, as the number of answers that "v splits away from (u, t)". We shall show that both terms are not large and can always pass the test. (Note that X and Y are overloaded and are not related to their meaning in the proof of Line b)..)
Note that by definition, we have V
Since l S é, for any vertex E U/=1 V.smalll only vertices E 25
V are actually splitting away from (u, v) for v E V As such, we have EE ,., S ( + 1 ñ 7 by the correct probability of O. For Xu,r, also note that if the answer is at most (30000 100000s) log n, then by Lemma G.2, the vertex passes the test with high probability. Therefore, we assume Xu," 2 E [X,,e] 2 (8000- 100000s) log n, and we again apply Chernoff for the tail bound:
50
(2/75- -
Pr (Xu,v 2 (L/6- - 22). .n) S exp
E [Xue]]
7-3
1
(using E [Y,,]] 2 (8000- 100000s) llog n and pick sufficiently small)
10
n
For Yu,,, note that only E V.small can report "v splits away from (u, t)" since the LCA between (u, t) at least i for any other v. Therefore, the number of signals we can possibly get is n/2 plus the noise induced by the oracle O. As such, we again have E [Ya.e]= I 11 Also, note that if Y. less than (30000 - 100000e) log n, the vertex e would always pass the test, which allows us to assume w.log. that [Yu,e] 2 (30000- 100000s) log n. Therefore, we can again apply Chernoff bound to show
3 Pr Yu,v
(-
20 (1/20 2=)²
(5 - 25) -20)
á
cxp
E [Yu..]]
3
1
(using E [Z 2 (30000 - 100000s) log and pick e sufficiently small)
10
n
Therefore, we could apply Lemma G.2 to argue that with high probability, the vertex e would pass the test. This part of the proof can be visualized in Figure 8(c).
Combining the analysis of Item a)., Item b)., and Item c). gives us the desired proof of Lemma G.3.
Using Lemma G.3, we can now argue that with high probability, the algorithm always correctly identifies the vertex split from the root as long as the size is at least 50000 log More formally, we have
Lemma G.4. For any composable V such that [ Z 50000 log n, let (V) be the optimal HC tree restricted to V, and suppose the root split of (V) is (5,S) Then, the outpul (T V (ATT) of Line is exactly (St,S;)
Proof. Assume without the loss the generality that S S Sy. Note that for any vertex u St it is also among the vertex of y (I ñ 22) As such, by Lemma G.3, the entire vertex set of St is returne. On the other hand, for any vertex S7, we claim the induced set 7 is necessarily smaller than S To see this, note that by Lemma G.3, the only possible case for Line 7 to not return a subset of S is if u E V. such that é > l and t = 1. However, in such case, the algorithm can at most return the set St, which is necessarily smaller than the size of S; As such, the maximum size of the set is attained by picking the vertex from Sj, which implies that the return rule of Line gives the partition (S;
In essence, Lemma G.4 is the very natural consequence of Lemma G.3. This can be visualized in Figure 8(d) of Figure 8 the T with the largest size is always the set of vertices induced by u1, which is exactly what we want.
35

---

Learning-Augmentt Hierarchical Clustering
tway (0.9))
isplls BAIS PU
ml (r g//
V/ 5875
(5519)
(((8))
amury Furm
TEEES anay from D6 P.).
9:50 l5 from (4.0
Illustration of Item of Lemma G.3 with U E U V.
(b) Illustration of Item of Lemma G.3 with Viuaal for some S E..
Vimall
T(6)
(onty) tsuch thtt uspliz away from (a.
(ankk) tuuch hut its sway from 19
T(2))
T(s))
(15))
(d) The "counterpart" trees generated by vertices u2, and (c) Illustration of Item c). of Lemma G.3 with u E Vimmall for us. We can simply take the largest partition guarantee the root cut.
< & as prescribed in Lemma G.3.
Figure 8. An illustration of the analysis used in the proof of Lemma G.3.
36

---

Learning-Augmented Hierarchical Clustering
Conditioning on the high probability event, any super-vertex has induce a maximal subtree in T", which satisfies the requirement for the tree be strong consistent with T. By Lemma G.I, Algorithm deterministically takes most (nn)) queries and O log n/=²)= Onn logn) time by the choice of (1).
Finally, we observe that Algorithm 7 only takes On logn) memory to implement. To see this, observe that for any recursive call of Algorithm 7, for any fixed u and v, the subroutine count e srpartttestersst.eee. On log bits of space; furthermore, the space can be re-used for different u and v vertices. As such, we only need to maintain the set T and its size for every u, which takes (n n) space. In fact, we can maintain this in (n n) space by keeping the I with the largest size and re-using the space on the fly. After each recursive call, we can free up the space of V to store V \ T and T instead. On separate (n log sized space, can keep writing down the HC tree with
can be implemented in
i). A name of the node that takes Ollog n.) bits of memory;
ii).
The set of vertices induced by this node.
In each recursion, we re-use the space of ti) by crasing the set of vertices induced by an internal node z once the children of a are written down, In the end, the sets of vertices are only written on the super-vertices. As such, the entire partial HC tree can be stored in (n lo memory as well.
H. The Algorithm for the Weakly Consistent Partial HC Tree: Proof of Theorem 11
We present the considerably more involved algorithm for the weakly consistent partial tree construction in near-linear time. We first remind the readers of the main theorem of this result.
There exists an algorithm that given splitting oracle O of weighted undirected graph G (V, E, w). with high probability, in On polylog n) time and (n²) queries computes partial hierarchical clustering tree I that is weakly consistent with the optimal hierarchical clustering tree T
Theorem 11.
Our main effort is to show the algorithm that satisfies the guarantee of Theorem 11. As we have discussed in the high-level overview, the algorithm divided into the "split" and the "merging" parts. We first show an algorithm that given a composable subset of vertices V C V such that V 12 return set '" that induces a maximal subtree in T(V). As
such, we can recurse on T and V T to gradually reduce the sizes to at most O(logn) Then, in the second part, we show how to 'glue' the subtrees together to eventually form partial tree that is consistent with T The overall structure of the algorithm can be shown as Algorithm 8.
Algorithm 8 weak weak-partial-trer "
(V, Vıi): an algorithm for partial tree construction
Input: Input vertex set V; input horizon vertex set VH; splitting oracle O as prescribed in Definition 6 Output: A partial hierarchical clustering tree for V. Initialize V -ー= V. 1/4 V.
If V < 50000 log n. return a super-vertex (defined in Definition 7). Get the partition of T such that Tr is a complete subtree, i.c. (T, V \ T, u,u" V4A) + vertex-split V4)) (Algorithm 12) Recurse on T and V \\ T. T.i.e.
Tr +- wewweeappate beak-partiall-tre ((T,T)
Tayr t weak-partial- T, Vi)
for the respective HC trees Run the merging algorithm To + tree- (Tr, Tyyrs u²) (Algorithm 13).
We will introduce and analyze the splitting and the merging algorithms in the subsequent sections.
H. An algorithm to split the vertices
We first discuss algorithm that produces complete subtrees for given set of vertices V. For the clarity of presentation, we use ñ to denote the size of V. i.e., á V..
37

---

Learning-Augmented Hierarchical Clustering
H.1.1. THE ALGORITHM
We now present the actual algorithm. We first give "tester" subroutines that serves more general version of the counterpart-teetee--ttroo algorithm used in Algorithm 7.
Algorithm peantterpart-tester/ee
4, threshold,, thresholds): an algorithm to test whether is among
"counterpart" of
Input: Vertex set VH; a splitting oracle O; baseline vertex u; test vertex e; threshold, E (0, n), thresholdy E (0, i)) Output: Whether v is "counterpart" of u
Initialize counters 61 t- 0, C2 f- O for Every vertex t E Vi do If e splits away from (u, t), increase e₁ by If't splits away from (u, v), increase Cg by end
if < threshold, and S threshold, then Return is counterpart of u".
end
Algorithm 9 is very similar to Algorithm 6, and the difference is that instead of testing V set, query on the Vи set instead. This is more than simple notation change: it allows us to separate the vertices "to be tested" (e.g., vertices in V) vs. the set we "used in the tests" (e.g., vertices in VH))
Next, we introduce the tester that given vertices E Vismlll and E Veruill returns whether le i.e., whether "split earlier" in the small-tree split order of
Algorithm 10 ppedecessor-tester""
(u, t, threshold): an algorithm to test whether t is among the "predecessor"
of u
Input: Vertex set VH: a splitting oracle O; baseline vertex u; test vertex t; threshold E (0, ñ.) Output: Whether i a "predecessor" of u
Initialize counters
for Every vertex V# do If f splits away from (u, s), increase by 1 end
c 2 threshold then Return "t is a predecessor of u²"
end
Note that unlike Algorithm 9, the vertex / passes the test in Algorithm 10 if the number of "split away" is lower-bounded.
With the predecesscr-test.. (O..a) (u, t, threshold) algorithm, we can now define the following algorithm that tests whether a root split has happened the previous iteration.
We now continue the presentation our tree-split algorithm. The full algorithm as Algorithm 12.
38

---

Learning-Augmented Hierarchical Clustering
Algorithm 11 test -rpphnn predecessor(0....)) (O.V.V algorithm to obtain any vertex that is split earlier than the orphaned vertex set in the small-tree split order
Input: Vertex set V of size ñi; the horizon set Vи of size nı: splitting oracle O
Output: Vertex X that is either empty contain "predecessor" of orphaned sets Sample set U² of 100 log vertices from V using randomness for u' E U do
for v E V/ do
n S 3m then threshold-pred 3n/2 end
else
threshold-pred +- 2n
end
Add x to X terredecsssoo-ttstee of u²
threshold-pres pred) (Algorithm 10) reports "v is predecessor
end
Record the size | for this choice of u'
end
Return X the largest size of
Algorithm 12 vertex-spl (V, Vn):
an algorithm that splits V to T and V
Input: Vertex set V of size ñi; the horizon set VH of size nH; splitting oracle O Output: Vertex sets T, V T; new horizon set Vi
Sample set U of 500 50g vertices from V for E U do
Initialize T 0 for e Vi do
Run counterpart-
(u, 3n nz/6) Add to T is "counterpart" of u.
end
Record the size [T'l for this choice of end
Pick (T V \ T") such that T T is with the largest size if 7 nv= 0 then
// Test whether a root split happened in the last iteration X +- -testt-oppha-pppeeeeess=000000 (using Algorithm 11) if X" * then
// The case non-root split Pick an arbitrary w² E X* Initialize T +- 0 for E Vn do Run sauutteraatttestee//e
(u", v, 3n nz/6) Add v to T if is "counterpart" of ut
end
Output with the same rules of the T n V * 0 case
end
else
// Case for root split Let Vi +- V, run and output with vertex-split Enforce single level of
recursion call (return "FAIL" if V Vi and the algorithm enters the above line again with V = Vi²)
end
end
else
I/ Keep the current horizon Output (T* V, V ('* as the partition and keep the same u E U corresponding the output T
Output of the vertex
end
39

---

Learning-Augmented Hierarchical Clustering
Note that in Line 12, we sample 500 log opposed 500 log vertices (this is purpose as opposed to being a typo). The formal guarantee of the tree split algorithm is follows.
Lemma H.1. Suppose V is composable with size i that satisfies the weak contraction property prescribed in Definition 9, and suppose ñ 2 50000 1ogo0logn. n. Furthermore, let Vu be single composable (e.g., Vu induces maximal free in T*) of on vertices, and suppose
V = 2.
for some E in the small-tree split order of Vy. Then, given splitting oracle O with correct probability at least 9/10, Algorithm 12 with high probability outputs composable sets T n N.V and V T and a vertex u' such that
1. T induces a single maximal subtree T (V).
2. V T" satisfies the weak contraction property as prescribed in Definition and in particular, the subtrees induced by
T have
(a) one edge connected to the node pa (VCAT-(V)) (ifit exist).
(b) one edge connected to the node that induces T in T
3. The lowest common ancestor between the nodes in T is an (immediate) child node of the lowest common ancestor between T {u²) in T (V), i.e., LCAT.(V) (TU = pa (LCAT-(M(T))) =
4. Size properties: at least one of the following guarantees hold.
(a) The new V T has least of at least 99 fraction of vertices in V T 100
T00 fraction of vertices that are orphaned verfices, i.e., the new Vorphan set accounts
99
(b) The size T satisfies the following properties:
i. The size T r V. is at least 200 n, i.e.,
1
2
7.
200
VH V, the size T n V is most (1 10000lo"" i.e.
< (1 10000 ñ.
n.
Furthermore, case Item 4b always happens Vf =V,
=V, and the algorithm runs in time O( n).
We now proceed to the analysis to prove Lemma H.1.
THE ANALYSIS
To begin with, we define the notion of orphaned vertices from our split procedure. Definition 28 (Orphaned vertices). Let V be a composable set of vertices, and let T - //saall We call V/small C V the set of orphaned vertices in V. with respect to T'. We denote the orphaned set of vertices Verphum and we write yoophan as the simplified notation when the context clear.
One can refer to Figure 9 for a visualization of the orphaned vertices (we used V as opposed to V in the figure). When the context is clear, we ignore the dependence on /amaal and T when talking about orphaned vertices, and simply denote the orphaned vertices as /rrphun In our proof of correctness, we will show "inductively" that the set only has a single orphaned set poorhhn key to guarantee property Item 2 of Lemma H.1.
We now proceed with the relatively straightforward analysis of the running time single level of recursion.
40

---

Learning-Augmentee Hierarchical Clustering
T
More than one edge connect to sibling
plits with recursive
subsets of V
Ampton
T
T2
T
Exactly one edge connect to sibling
T2
S plits with semi-invariate H
T1
Figure 9. An illustration of how horizon sets help maintain weak consistency. With the same the reason for the different outcomes is on the top, the small-tree split order restricted on has changed compared to the last iteration. The use of horizon set helps keep the small-tree tree split order invariant before root cut happens.
Lemma H.2. The algorithm vertex-split (V, VH) runs in time O log n.)
Proof. Each run of the counterrpar--tester takes ((nr) time. As such, the procedure that finds takes O log n) time since it involves On logn) calls of counterpart-testee: Similarly, the procedure that finds X takes most (n log n) calls of predecessor only make nH number of counterpart-teste
which again result in On log ń) time. Furthermore, if X / calls, which takes (m time. On the other hand, if X = 0. since we insist a single level of recursion call, the runtime overhead is at most O(n) log n). Adding up the time complexity of the above two procedures gives us the desired bound.
We proceed with the proof of correctness for the algorithm. To this end, we first observe that by Observation and since Vi is composable, the answers for the splitting oracle O on (u, v, w) Vn is fully preserved in TV(Vi). We now give technical lemma that characterizes the return T by running counterpart-teste this is essentially the same argument used in Lemma G.3, albeit switched V to Vn. We provide the lemma and the analysis for the purpose of completeness.
on different sets of vertices
Lemma H.3 (Cf. Lemma G.3). For any composable Vn such that [Vrl 2 50000 log n, let E be the maximal level that ssmall contains a in / (Sn n5/ With high probability, Line 12 in Algorithm 12 satisfies the following properties.
a). For any vertex U V.
V/saall there
No vertex U U 1. Vemall can be added to T by Line 12 of Algorithum 12.
No vertex u E Uft1 Vysmall can be added to T by Line 12 of Algorithu 12.
b). For every level ( E and vertices Vimaall with high probability, there are
No vertex U E Vamall can be added to T by Line 12 of Algorithum 12. vertex Vsmall for can added to T by Line 12 of Algorithm 12.

---

Learning-Augmented Hierarchical Clustering
c). There exists l such that | V. 2 25 and for any & S and any vertex u E V. with high probability, all vertices u E Vi for l >> are added to T by Line 12 of Algorithm 12.
Proof. Let l" be the maximal level that the Vismall contains a vertex in Vsmall /5), and suppose the split on this level results in (Sf -x ). We again assume w.log. that |S - $ which means S becomes Vi The bounds in Observation still hold with parameter nH, i.e., 2n Item b)., and Item c)., respectively.
U 1-(+++ V.mail inz We now proceed to the proofs of Item a).,
Proof of Item a). Fix any vertex U V.small For the first statement, note that for every v E + Viamall, all the vertices in Uf_1 V.small are splitting away from (u, v). Define Xu.r, as the indicator random variable answered by O as "t splits away from (u, u)". and define X,, = EiED Xu,,, as the total number of vertex split away from (u, v). By Observation 3, the expected number of split away reported by oracle is at least
9
nH
E E[Xueel
50 nH.
10
5
Note also that a, is summation of 0/1 independent random variables. As such, can apply Chernoff bound to get that
Pr (Nu,0 I
12
= Pr
Xu,v S
25
E [Xa,z]
6
27
(2/27)²
I exp
E [Xu,e]
3
60 nM 2 9000 log using the lower bound on the size of Vii)
10 n
For the second statement, note that for any t E U V.smal, v actually splits away from (u, t). As such, there is at least 4n vertices such that "v splits away from (u, 1)" this is because the LCA between (u, e) has to be higher than the LCA between (u, t) for any e U V.small, As such. define Yu,u as the number of total answers of "v splits away from (u, t)
5
by O, again have
9
4nH
18
E 0.00
1HH
10
25
As such, we again have
31H
15
Pr
Yu
Pr
Yu,
E
[X,,r]
5
18
1
nM 2 9000 log using the lower bound on the size of Vi1)
10
n
50
By union bound over at most vertices, vertex v E U Vamall - V. as 'counterpart'.
V/small can pass the test and be recorded
Proof of Item b).. We now show that vertices U E Uf_ Vomall cannot pass the "counterpart" test. For vertices in v E Viaall we claim that there are too many vertices that split away from (u, v). To see this, let us define An, as the total number of answers of "t splits away from v)" answered by O. Note that for any vertex E - + //small the answer always
"yes" since e* 2 2 e. Therefore, we can lower bound the expectation of Ay, with E [A,,v] Therefore, we can apply Chernoff bound to get
5
2 nn
10
2 9 nH.
25
Pr (Au.
TA S exp
(1/2)2 3
E [[
1
10 n
We now turn to the vertices that are in Uf-1 V. Note that by definition, there | V.mall For any E U Vamalll v splits away from (u, As such, define Bu,v as the number of answers by O with "v splits away from (u, t)", there is E [Bu,el
| V.small 2 + ny-
18 nH. Once again, by applying Chernoff bound, there is
3n
(1/5)² E (
1
Pr Bu, S
< exp
10 n
Applying a union bound over the cases and all nH S n vertices gives us the desired statements.
42

---

Learning-Augmented Hierarchical Clustering
Proof of Item c)., We fix l as the minimum level such that the union of Uf=1 V/ has at least n n /5 vertices. Let l S E and for any vertex in k for k > define the following two random variables: Xu, as the number of answers that "t splits away from (u, v)", and Yu, v as the number of answers that "v splits away from (u,t)" We shall show that both terms are not large and can always pass the test. (Note that X and Y are overloaded and are not related to their meaning in the proof of Line a)..
Since S ?, for any vertex u E U/=11 V.small, only vertices E - V.suall are actually splitting away from (u, u) for v E V As such, we have E' [Xu,
Note that by definition, we have |
az 25
] S ( + )) n 50 NH by the correct probability of O. For Xa,v, we also note that if the answer is at most 3000 log n, then the vertex
7
trivially passes the test. Therefore, we assume Nu,v 2 E [X,,] 2 3000 log n, and we again apply Chernoff for the tail
bound:
(4/21)²
Pr
Xu,v 2
nH
S exp
E [Yuu]]
6
3
1
(using the condition E [Ya,e) o] 3000 n)
10
n²
For Yu,v, note that only t E Vimall report "y splits away from (u, since the LCA between (u, t) is least é for any other v. Therefore, the number of signals we can possibly get is /2r/2 plus the noise induced by the oracle O. As such, we again have EE o) < 11n /20, Also, note that Yu,. is less than 30000 log n, the vertex would always pass the test, again apply Chernoff bound to show
which allows to assume w.log. that E yY, 2 30000 log n. Therefore,
3nH
(-
(1/11)²
Yu z
I exp
E [Y,,]
5
3
1
(using the condition E Zu,ool 2 30000 log n)
10
n3
Lemma H.3 D
A direct corollary of Lemma H.3 is that the set T induced by any u V. is larger than the T induced by u E 1 V.mall, and the "higher level" vertices in 1 Vamall induces larger sets. More formally, we can summarize this observation as follows.
Lemma H.4. Conditioning the high-probability event of Lemma H.3, the following statements are true:
Let Ti be the vertex set induced by un E V from Line 12 in Algorithm 12, and let T2 be the vertex set induced V.small from Line 12 in Algorithu 12. We have [Ti] 2 [T2).
by u2 E U i=8+1
Let l S < l. Let Ti be the vertex set induced by i1 E Vamall from Line 12 in Algorithm 12, and let T2 be the vertex set induced by U2 E Vismall from Line 12 in Algorithm 12. We have [Til 2 [T2]
Proof. We prove the second bullet first since the conclusion can be used to prove the first bullet. Note that conditioning on the nigh-probability event of Lemma H.3, if L < lz, we have T2 S Ti by Item c).. Therefore, we have [ 2 [Tal-
For the first bullet, note that conditioning on the figh-probability event of Lemma H.3, the set T2 can either be V. (by Item a).) or U (=ē+1 V. //small (by Item b).). In either case, the size of such set is at most U 1=2+1 V-small which is the set Ti generated by u E V.small Furthermore, by the result in the second bullet, if u V.small for some i < غ, the induced set T can only be larger. This proves the first bullet.
We now show that conditioning Lemma H.3 (resp. Lemma H.4), if the size of the orphaned set is relatively small, we will not need the subroutine in Line 12, and all the guarantees in Lemma H.1 will be satisfied.
n. i.e. Vorpun| < 99 n. Then, with high probability, we have T O V # 0, and the resulting T and V \ TT satisfy the properties of Lemma H. I.
Lemma H.5. Let V and Vn be as prescribed by Lemma H. I, and suppose the size of the orphaned set is at most
99
100
100
43

---

Learning-Augmented Hierarchical Clustering
Proof. We discuss the cases based whether VH V and whether there exists Vismali such that [
100
1. Vn = V. In this case, we show that with high probability, the guarantees in Item 1, Item 2, and Item 3 of Lemma H.1 always hold, and the Item 4b case of Lemma H.1 is going to happen. To see this, note that with high probability, we will sample a vertex that is among the first & vertices in the small-tree split order: the probability for us to not sample a vertex from /small
25
< f is at most 25
24 25
1 10 n²
500 log
As such, we condition vertex v' among V (S 23 is sampled. By Lemma H.3 and Lemma H.4, the counterpart set induced by v' /ssmall (s á is among Uf V.small, which necessarily induces larger set than any other 25
E U Vsmall Therefore, the induced set 7 must be from the vertex v'.
i=8+1
We now use this to verify the desired properties. The proofs of Item I, Item 2, and Item are straightforward as follows.
For Item 1, note that by Lemma H.3, the induced 7"" is always V V induces a maximal subtree in (V))..
V.,mmlll which forms a maximal subtree in
T (VH). Similarly,
For Item 2, note that as long as T includes the orphaned set Vrorhhan there will be only one edge connecting the node induces 7 in T In this case, there is orphaned set, and Item 2 holds trivially.
Item 3 directly follows from Lemma H.3 since T is induced by u².
For the size upper and lower bounds (Item 4), we verify that the guarantees for case 4b always holds. Note that conditioning on the high-probability event of Lemma H.3, the size is least 2nx (Observation 3). Therefore, the set T n = T has size at least 28
5
2 1 n. which proves the lower bound (Item 4(b)i). For the upper bound (Item 4(b)i), we note that for the size of T VV to be more than (1 1oo00 n, a necessary condition sample vertex / (S h 1/0000 log" r). Since we sample 500 log vertices, define X the random variable for the number of vertices sampled from | (S ñ/ 1010000 log" î), we have
5 200
E [X]+
20
Since X is a summation independent random variables supported on [0, 1}. we can apply Chernoff bound to show that
Pr 2 Pr 2 50 n [X])
2500 log² n 20 log
S exp
+ 20
<
10
n²
Therefore, we apply a union bound to show that with high probability, the size of T n V will not be larger than 10000 log 7, desired.
If Vn * V. We need to handle this case with more care. We first show that at least one vertex that V Vorphan can be sampled with high probability. To see this, note that by the size bound on |orphan the probability for vertex in V porphan to not be sampled is most 99/100. 100. Therefore, the probability for no vertices in V \ prophan to be sampled is at most
1
(99/ (10) 500 log
n²
We condition on the high- probability event that at least one vertex from V yorhhn is sampled for the rest of the proof. We now discuss two sub-cases.
44

---

Learning-Augmented Hierarchical Clustering
a). If there exists a V. such that [Vamall 99 and no vertex from U Vasaall is sampled. In this case, we show that with high probability, Item 1, Item 2, and Item 3 of Lemma H.1 always hold, and Item 4a in Lemma H.1 is going to happen. Note that in this case, there exist vertices of V. that are among V (I / 1/)00), and it is of the size at least 10000 As such, the probability for us to sample at least one vertex from V/mmall is at least
100
1
- 1-(100
500 log n 2
100
10 n2
Let E Vaamall be the sampled vertex. Note that since V + V. the vertex sample from V. is among the vertices of -f_ V.smal in Lemma H.3. Therefore, by the same argument of the Ví V case, if we pick T with the largest size, the entire set of e V. is going to included T"* Therefore, the properties of Item 1, Item 2,
and Item 3 follow from the same argument of the Vn V case.
Furthermore, by the condition that no vertex from V is sampled, we cannot have larger such T sets (see Lemma H.4). As such, the set will pick is necessarily the set T corresponds to v E V. and V.small becomes the new /oorhhn set of the next iteration.
Finally, note that have |V..mall| 2
99 n. And after remove T* from V, we have (V t V T*) which
100
means (ñ - C) for some C > 0. As such, for the next iteration, we must have /urphan 2 100
b). If there exists a V/small such that | 2 99 á and vertex from | is sampled. In this case, show that Item 1, Item 2, and Item 3 of Lemma H.1 always hold, and Item 4b of Lemma H.1 is going to happen with high probability. Note that since vertex v' e |
sampled, and since v' is among U V/ in Lemma H.3, the entire set of V.small is going to be included in T* The properties as prescribed by Item 1, Item 2,
and Item follow from the argument in the V = VH case, and the size lower bound becomes
99
200 n.
100
as desired. Finally, note that we do not need to guarantee the size upper bound (Item 4(b)ii) since we will not be able to meet the ViH V condition.
c). If |/amall <
100 ń for all l among V. In this case, we show that Item 1, Item 2, and Item 3 of Lemma H.1 always hold, and Item 4b case of Lemma H.1 1 will happen. We first show the size lower bound of Item 4b: note that with high probability, we can sample one vertex that is among the first 1/200 vertices to be split in V the small-tree split order: the probability for us to not sample any vertex among the first n/2200 vertices in the small-tree split order most
99
500 log n
199
1 3 n
200
Therefore, condition on the event that vertex o' in V (S f/220) is sampled. Since we have the condition that |/small| < TOo ñ for all & among V, vertex among /small 7/200) can induce at most 100 vertices. As such, let ll be the level in the small-tree split order of v', we have
+ 200
200
199
- V/maal|
200 n.
Furthermore, as the case analysis of Vn A V. which means v' is among the vertices of Uf_ V/amall in Lemma H.3. Therefore, the properties of Item 1, Item 2, and Item 3 follow from the same argument as in the VHH V case. For the size bounds of T n V. by Lemma H.4, if we pick the largest T by the subroutine of line Line 12, at least the entire set of U Vamall is going to be included, which means the size of T n is of size at least 200 ñ. This gives us the size lower bound.
Finally, we again note that we do not need to guarantee the size upper bound (Item 4(b)ii) since we will not be able to meet the Vi4 V condition.
We now handle the case when prorhhan becomes large. We first note that if we happen to sample vertex u V Torphan can still guarantee T n V A and obtain the properties as prescribed by Lemma H.I.
45

---

Learning-Augmented Hierarchical Clustering
Lemma H.6. Let V and Vy be prescribed by Lemma H.I, and suppose the size of the orphaned set is more than
.9
100
i.e., |Vorhan| >
99 n. Furthermore, suppose U Un( (V \ Vorphun + V. Then, with high probability, we have T n V + 0. 100
and the resulting T and V T satisfy the properties of Lemma H.I.
Proof. In the lemma statement, we have already conditioned on a vertex sampled from V \ Varphun Furthermore, we can again show that the probability for us to sample a vertex among the first n /25 in the small-tree split order is at least
24 500 log 21
1
1 - 25
10 n²
The events of U n (V) Vorphun) * 9 and V (S nH n2/25) * 0 are not independent. Nevertheless, we can still apply a union bound and argue that both events happen with high probability.
Conditioning on the high-probability events as above, we can argue by Lemma H.3 and Lemma H.4 that the entire set of Vorphan is going to be included by the subroutine as defined in line Line 12 of Algorithm 12, which gives us the size lower bound. We do not need to guarantee the size upper bound since we cannot meet the condition of V/4 = V.
Finally, for properties of Item I, Item 2, and Item 3, we can repeat our proof' Lemma H.5. We provide the analysis again for the purpose of self-contained proof.
For Item 1, note that by Lemma H.3, the induced set T is always - V.small Therefore, T V induces maximal subtree in T (V).
For Item 2, note that as long as T includes the orphaned set Vorphan there will be only one edge connecting to the node induces T in T This is exactly what we proved in the lemma.
Item 3 directly follows from Lemma H.3 since T is induced by u".
This concludes the proof of Lemma H.6.
By Lemma H.6, the only case of concern now is when T n n = 0, i.e., |rophun >
.99 ñ and U does not contain 100
samples from V \ Vorphan We now show that our procedure Line can effectively distinguish between the cases of V.P /orphan = 0 (root cut) and Vorphan being small.
99 Lemma H.7. Let V and VH be as prescribed by Lemma H.1, and suppose the size of the orphaned set is more than 100
i.e.,
Vorphun
99 Tt Furthermore, suppose T n nV- = =0 in Line 12 of Algorithm 12. Then, the following statements
true.
(i). If VVV Vorphan + O. with high probability, we have X + 0 and X C (V) Vorphan), iee, X only contains vertices in V but not in Vrophhn.
(ii). V \ Vorphan = 0. with high probability, we have X = Ø.
Proof. Consider the small-tree splitting order of VH. and let E V.small for some é < غ, where V = /orphan We prove that with high probability, i). no vertices u E V n ( can be added to by Line 11; and ii) all vertices in E V n (uf= Vamall) are added to X by Line 11. (Note that this is why name the subroutine as a "predecessor" test.)
We first observe that by our definition, there is Voophan C V n Luuelllmall Too see i), note that any E V n VZ can only split away from (u,t) t) for t E V/amall, this is true since for every &f Vamall the lowest common ancestor between (u, t) induces a subtree in VH that contains e. Moreover, since V/small _ V, we have |Vamall| < n. Define X,, as the number of answers "v splits away from (u, t)" for t E VH from O. By our choice of the parameter phreshold-pred we assume w.log. ng 13 in expectation. Since
X, 2 7 since otherwise will not join X anyway. nH S 3Ā, we have [X,) S +
10 To
46

---

Learning-Augmenttr Hierarchical Clustering
X is summation of independent random variables supported on {0, 1}, we can apply Chernoff bound to obtain that
15
Pr x 2 2
Pr
x 2
EE (
13
(2/13)2
$ exp
E [X.]
3
1 1
(using the condition on the lower bound of X,)
10
na"
On the other hand, if nH > 3r, we have E [X,]] apply Chernoff bound to obtain that
-
3
+
1H
10
30
13
11
We again assume w.log. that X, 2 n, and we can
20
Pr X 2 3
n1
= Pr
X 2
E [X,]]
13
(8/13)2
$ exp
E [X,)
3
1
(using the condition on the lower bound of X,))
10
n
Therefore, we can apply a union bound and argue that with high probability, no vertices v E V n (U Vmmall) can be added to X by Line 11 1, as desired by i).
We now proceed to show vi). all vertices in E Vn(u are added to by Line 11. Note that v E V implies E V Vorphan, Therefore, splits from (u,t) for every t in the orphaned set and for every t as the sibling of /rophan i.e., / E U 1=8+1 V.small Define Y, as the number of answers "v splits away from (u, 1)" for 1 E Vn from O. By our
V
choice of the parameter threshold-pred, if HH S 3n, since we have |/orphn| 2
99 á and | (
V.small >
|oorphnn, we
100
have E [Y=] 2 9 199
n in expectation. Since Yu is a summation of independent random variables supported on {0, 1}.
1O Ton
we can apply Chernoff bound to obtain that
3 = Pr
17
Pr
Yu S
7
Yo <
E [Y,]
2
15
(2/15)²
< exp
E [Y,)
3
< 10
(using E [Y,]
2
10 n)
17
n3
On the other hand, if ng Therefore, we have E [Y,]
3n, we have at least nH T00
209 nHr vertices such that v splits away from (u, t).
300
g
299
nh N 1 nH in expectation. Therefore, can again apply Chernoff bound to obtain
300
that
2 nH
5 Yo
Pr
Yu
Pr
E [Y.) 6
(1/6)²
S exp
E. [V.)
1
(using E [Y)) > nH 2 1 n)
10 n
Therefore, we can apply a union bound to obtain the desired statement on it).
By our statements in i) and di) as above, we can already conclude that X C (V Vorpun). Therefore, Item (ii) of Lemma H.7 follows straightforwardly since if V \ purphan = 0. any of its subset can only be empty as well. For Item (i)., what remains to show is that with high probability, there is X * 0. Note that if Vorphan and V \ prrphun * 0, then by
our statements in i) and ii) above, the set X will not be empty. Since we assume Vorphan
>
.9
the probability for
100
47

---

Learning-Augmented Hierarchical Clustering
U" to not have any vertex a E Vorphan is most
1 100 log _
1 1
100
10 n²'
as desired. Thus, with high probability, X* is not empty, which proves Item (i). and concludes the proof of Lemma H.7.
Finalizing the proof of Lemma H.I. By Lemma
H.2, the algorithm runs in ni log n time. For the set of vertices V, we
either have /orphan
99
n or |/rpban|
Z
99 n. In the former case, we apply Lemma H.5, and all guarantees in 100
100
Lemma H.1 1 are satisfied. Otherwise, if |orphan
IV
99 n and U n (V) \ Vorphan) + 0. by Lemma H.6, we can still satisfy
100
the properties as prescribed by Lemma H.1.
The only remaining case is Vorphan 2
99 á and U n (V \ Vorplin) = In such a case, the algorithm will enter TOO
Line 12. If V \ Vorphan 0, then by Item (ï). of Lemma H.7, the algorithm uses Vn V for single level of recursion call, and the properties of Lemma H.1 are satisfied by the guarantees of Lemma H.5 (since now Vorphan = 0). Otherwise, if V Vorphan # 0. note that by Item (i). of Lemma H.7, any arbitrary vertex u E U belongs to V. for some < É, such that V.amall = /orphan Since |vorphan| 2
99 n and n. 2 ñi the vertex u is among / (S nz /z/ /10). As such, by 100
Lemma H.3, with high probability, the vertex set T contains all vertices in Vorphan and the size is sufficiently large to guarantee Item 4(b)i of Lemma H.1. We do not need to guarantee Item 4(b)i since V * 0, and we will not meet the V = Vi condition. The guarantees of Item 1 and Item 2 are similarly satisfied since we remove a set U2 V.salll that contains Vorphan Finally, by similar argument as we used in Lemma H.5 and Lemma H.6, Item 3 is satisfied as desired.
H.2. An algorithm to merge two subtrees
We now move to the algorithm that merges two partial trees. Note that this task is not trivial: we use the thought process of small-tree split order in the proof of Lemma H.I, but the algorithm vertex saxtex--ppit"" split does not immediately tell us which node did we "extract" the set T. As such, it still takes considerable work to merge the two trees on the "right" internal node.
Exactly here is why we need the split algorithm vertex- vertex-spliee split return the vertex w". Note that our goal is essentially to find the lowest common ancestor between u² and T, and "stitch" the tree TT to the node. As such, natural strategy is to ask whether in T (resp. (V))), whether vertex v E V splits away from (u",x) .) for
T. If O is to answer the queries correctly, all vertices that are "outside" (CA (T {u') })) would answer yes, and all vertices that are among the leaves of LCAr-(V) (T {u²) would answer no. We then use the fact that I' is always large enough beat the noise from O.
The formal description of the algorithm is as Algorithm 13.
Algorithm 13 tree-merge (Tr, Tiirs u²): an algorithm to merge partial trees Tr and TexT-
Input: Vertex set V of size ñ; a splitting oracle O; Partial trees Tr and Tivy constructed by vertex vertex-spli: split VH)); vertex u² by vertex-split (V, Vn))
Output: A partial tree on Ty Initialize S' + for s e V \ do
Initialize counter C, + 0 for Every vertex l T do
If 8 splits away from (u", (), increase c2 by end
if < 2 [T] then Add to
end
end
Take the lowest common ancestor æ = LCAT, (S') If S' does not induces a maximal tree in Taxe i.c. 1e [S'] + S', abort the algorithm and report "fail" If the algorithm does not fail, split node into two nodes: the left node induces the subtree of x, and the right node induces the subtree Tr.
We now present the guarantees of the tree-merging algorithm.
48

---

Learning-Augmentle Hierarchical Clustering
Lemma H.8. Given any composable vertex set V S V such that V = = 50000 n, a splitring oracle O with correct
probability 9/ 10, and suppose Tv Tr, and u' are obtained by Algorithm 12. Furthermore, assume that
i). The high probability events of Lemma H.I happens:
ii). The partial tree Tixr is (weakly) consistent with T T.(V \T), Tr is (weakly) consistent with T*
Then, with high probability, Algorithm 13 runs in time O and outputs a partial tree Ty that weakly consistent with (V).
Proof. We first remind the readers of the definition of a partial tree I weakly consistent with another tree T. For I to be consistent with T, there should be
a). each super-vertex of I corresponding to a connected subtree in T with out-degree at most 2, and each of the edge connects to either parent sibling node; and
b). for leaves (x,y) y) in I, let X and Y be the corresponding leaves in T, the subtrees induced by LCAr(*, y) and LCA7(X U Y) contain exactly the same set of leaves.
We now show that with high probability, the algorithm tree tree-merge" (Tr, Tvirs u²) outputs partial tree that satisfies a) and b) w.r.t. (V).. For a), we note that the super-vertices in T (V) and (T T), T (T)) are exactly the same. Furthermore, by the high probability event of Lemma H.1, both (V) and (T (V) \ (T) satisfy the weakly consistent property. As such, the guarantee of u) follows.
The main work here to prove the guarantee prescribed by b). To this end, we first observe that for any set of vertices X and Y, if LCAT-(V) (X U only contain vertices in (resp. V T), then the assumptions of Tiyp being consistent with (V \ T) and Tr being consistent with (T) is sufficient to prove the leaves induced by LCAT, (X YU is the same as the leaves of LCAT((V) (X UY). This is evident by using the procedure that constructs T (V) as in Definition 25.
The final missing piece the vertex sets X and Y that induce vertices both and V \ T, which the place where we need show that the merging algorithm finds the "correct" node to merge. Let /urphan be the orphaned vertices by removing T from V. Since condition the high probability event of Lemma H.1, there must be an internal vertex 2, such that = (CAT-(V)(T U {u() }), and nodes rT and such that i). 2 pa (rr) and = pa (rs) in (V) and ii). the induced leaves of rr is T and the induced leaves of rs is S such that n" S. Furthermore, have [T] 2 50000 log n 200 2 200 log by Lemma H.I. We now claim that by rumning tree-merge O (Tr, Tv u²), the set 5" we recover is exactly the leaves of S (the /orphan set of vertices). The detailed analysis is as follows.
For each E S, observe that in T (and T (V)), s does not split away from (u", .t) for t E T. Therefore, define C. as the random variable that records "s split away from (u", .t) for t E T" from O, we have in expectation E [C.]] S 10 (TT). If C2 < 20 log n, trivially fails the test. Otherwise, if C. 2 20 log n, we can apply Chernoff bound to get that
1 [T) Pr C. 2 2
= Pr (C, 2 E(C.)
52
< exp
E [C.]
3
1
<
(using C, 2 100logg)
n
For each d & S, observe that in T (and T(V)), does split away from (u' t) for t E T. Therefore, define Cy as the random variable that records "d split away from (u", 1) for t E T from O we have in expectation E C.) 2 10 [T].
49

---

Learning-Augmentel Hierarchical Clustering
Therefore, we can apply Chernoff bound get that
1 = Pr
Pr
Ca S 2 [7]
Ca S IR [Ca)
(4/9)²
exp
E [[Ca]
(using Ca 2 200 1100-oog10 n))
n²
We can then apply a union bound over at most ń Σ n vertices V \ T to get the desired statement.
Observe that any internal node that induces leaves in both I" and V \ ''' has to at least include the whole set of S and T. For any leaves and y in Tp. let the induced set of vertices in the leaves of T (V) be Z S SUTUA P. By the above argument, ST should be returned the set of vertices. Furthermore, by the consistency between Tpir and T (V \ (T), the set should also be returned. This concludes the proof.
The merging algorithm in Lemma H.8 could be visualized as in Figure 10.
T V
TT
X
1
T
S V Vorphan
S V orphan
a). Merging algorithm's view
b). The actual T
Figure 10. An illustration of the algorithm that merges (V \ TT) and (T) The shaded internal node is the "actual" node to split and T in T the oracle is correct, does not split away from (u", 4). but does split away from (u",t). (). The size of I" is large enough to overcome the adversarial noise.
H.3. Finalizing the proof of Theorem 11
We now move to prove Theorem 11 for our partial tree construction. We first bound the number of possible internal nodes as n by Fact A. Therefore, we can apply a union bound on all splits for Lemma H. and argue that with high probability, the events of Lemma H.1 hold for every partition. Furthermore, conditioning on Lemma H. I always holds across the splits, we can again apply a union bound to show that Lemma H.8 holds across all internal nodes in the partial tree construction with high probability. We condition on the high probability events of Lemma H.1 and Lemma H.8 across the internal nodes for the rest of the proof.
Proof of efficiency. We show that the depth of recursive calls Lemma H.1 is Olog² n), i.e., the longest sequence of recursive calls induced by any fixed V is at most Ollog n) in Algorithm 8. To see this, consider any set of vertices V
50

---

Learning-Augmented Hierarchical Clustering
with size ñi, and look into three levels of splits on V. Suppose the vertices sets are V (V1, V2 Vss V1, V3 Vo V7, V/). We claim that there is
max (( == <1
10000 log n.
We prove the above statement by using Lemma H.I. Conditioning on the high probability event of Lemma H.I, if the first split of V falls into the condition of V = VH, then by Item 4(b)i and Item 4(b)ii of Lemma H.1, the balanceness of sizes already follows. Otherwise, we can have the following cases
If we enter the case of Item 4b, note that we have (T) 2 1o000log*%)
A As such, in the first split V + (V T,T), we already
200
n. The size of T might be large; however, it must have V = Vn for the first split T (by Algorithm 8). Therefore, in the next iteration, the maximum size is at most (1 10000 logo R) n as well.
have V\T <
199 200
n - (1
If we enter the case of Item 4a, note that the set T of the current iteration is of size at most 8 S1 10000 n.
TOO Furthermore, in the next iteration, the Vorphan set accounts for at least 99 fraction of vertices. Hence, we can apply 100
Lemmas H.6 and H.7 and argue that the split will be in the case of Item 4b with T3 as the new set T Now, we have A
V \ (T (b) with size at most
TOO I (1 Ing? n. The new set T2 n (V \ ()) might be large, but since it
forms a single maximal subtree in T(T n (V) \. T)), there is Ví = V. and in the third iteration, the maximum size is going be to at most (1 10000 log" ) - ni, as desired.
Since the size reduces by (1 10000 10000log* factor for every three level of splits, after 60000 log n recursive calls, we have
remaining size S ñ (1 10000 log 7
20000 log"
I ń exp (-2 n) s O(),
to which point the remaining vertices will be collapsed to a super-vertex by our algorithm. Therefore, since ñ n, the longest sequence of dependent calls is most Ollg"* n).
Finally, to complete the proof of efficiency, note that by Lemma H.I, the runtime for each call of Algorithm 12 is Onl log nt. The tree has depth at most log" nı; and at each level, the total number of runtime is at most Onn² -log n) since we have Σ n S n. Similarly, each call of the merging algorithm will happen only after the split algorithm, which causes an overall (n²) runtime overhead on any level. Therefore, the total runtime is bounded by O(n² -log n) = O(n polylog m), as desired.
Proof of correctness. We inductively prove the correctness of Theorem 11. On the level of the leaves in Algorithm 8, by Lemma H.1, if the leave contains more than one vertex, it must be composable set with out-degree at most 2 in T*, and exactly one of them connecting to a parent node, and the other connecting to the sibling of the orphaned vertex. As such, when we merge two components X, Y in which at least one of them is a super-vertex, we can guarantee the out-degree is still at most 2, and the LCA of X and Y induces the same vertices as on T (LCAy. (X UY)), which implies the partial tree is weakly consistent with TX UY). On the other hand, when merging two components who are both not super-vertices, we can use Lemma H.8, and the assumptions of weak consistency come from the guarantees on previous partitions. Therefore, the weak consistency inductively applies to every level of the merging process, which gives the desired correctness guarantee.
I. Discussions about Additional Settings for Our Algorithms
We discuss our algorithms in additional settings, which include general success probability (other than 9/10) and splitting oracle for approximately optimal HC trees.
L.I. General success probabilities
We use a success probability of 9/10 in our algorithms for technical convenience. Here, we discuss algorithms with more general success probabilities. We remark that due to adversarial incorrect answers, our algorithm cannot work with 2 + 8
51

---

Learning-Augmenttr Hierarchical Clustering
success probability for arbitrary e. In fact, it is unclear whether any algorithm would work with 1 + success probability and adversarial incorrect answers. Concretely, suppose that in the optimal HC tree, the first cut is balanced with size (n/2, n n/2). This appears to be a quite easy example. Now, let us fix a vertex u and determine whether a vertex is on the same side of u. If v is on the same side of u, there are n n/2 vertices w E V such that w splits away from (u, v); conversely, if v is on the opposite side, there is no such w vertex. However, due to adversarial incorrect answers, we can report (n/2 - nn/3 = n/6) such w vertices in the former case, and n1/ such w vertices in the latter case. As such, in the above example, the correct probability for the oracle must be at least 3/4 to get anything meaningful. Finally, we remark our algorithm would work for any success probability 1/ + C' for sufficiently large = Q(1): all the analysis will go through with changes in the constants. Furthermore, if we deal with random incorrect answers instead, we will be able work with 2 + E success probability for any e (2(/n)).
Finally, we give a remark on the discrepancy between success probabilities between learning- -augmented HC and other deaming-augmenter graph algorithms. In some graph algorithm, e.g., in (Braverman et al., 2024; Cohen-Addad et al., 2024; Dong et al., 2025), the leariig--augmenter augmented oracle could work with 1/2 + C probability for any C = 2(1). The reason our algorithm should work with a sufficiently high success probability is due to the hierarchical structure. For instance, in the paper that studied However, in the HC problem, if the construction of the partial tree is wrong at any level, the error will propagate to all subsequent nodes, and it is not clear how to control the error if this happens. Therefore, a constant success probability sufficiently larger than 1/2 is necessary.
max-cut (e.g. (Dong et al., 2025)), the errors in the algorithm are "one shot",
1.2. Splitting oracle with approximately optimal HC trees
A natural extension of our algorithms is to explore HC algorithms with splitting oracles from an approximately optimal HC tree. In other words, for triplet of vertices (u, u w), the oracle O answers the "splitting away" query based on an HC tree T that achieves a-approximation of the optimal tree T We remark that our algorithms based on the strongly consistent partial HC trees (i.e., the algorithms of Theorems 1, 2 and 21) could work with approximation HC trees. In particular, if the splitting oracle is constructed from an a-approximation HC tree T, our algorithm will produce HC trees with an extra ((a) factor on the approximation guarantees.
On the other hand, however, it is not immediately clear whether our algorithms based weakly consistent partial HC trees could work for oracles from approximate HC trees. The main difficulty here is that to analyze the revenue decrement induced by the weakly consistent partial HC tree, we need to prove Lemma D.4 that characterizes the revenue structure of the optimal tree. We proved the statement by showing that if the statement is not true, we can increase the revenue, which forms a contradiction with the optimal HC tree (see Claim D.2 for details). We cannot casily argue that the same structural statement with an approximately optimal HC tree. This could be an interesting problem to resolve for future work.
J. Splitting Oracle and Learning Theory
In this section, we offer formal learning theory analysis for learning a splitting oracle for the Bouriigg-augmenn hierarchical clustering problem. In particular, we utilize the PAC learning framework to show that a high-quality predictor can be efficiently learned, provided that the input instances are drawn from a specific distribution. We remark that similar results have been shown in other settings by (Izzo et al., 2021; Chen et al., 2022c; Ergun et al., 2022; Grigorescu et al., 2022). Thus although the results of this section are by now standard techniques, they still provide an end-to-ent framework for designing leaming-augmented algorithms.
First, we suppose that there exists underlying distribution D, from which our input is drawn. In particular, D generates independent instances for hierarchical clustering, corresponding to the setting where similar instances of hierarchical clustering are being solved. Note that this is exactly the setting where we would like to apply If there is instead generalization failure or distribution-shiff then inherently machine learning models will perform poorly.
algorithms.
Then our goal is to efficiently learn a predictor f from a family F of possible functions, where the input to each predictor f a weighted undirected graph G = (V, E, w) and three specific nodes, and the output is a feature vector. We remark that each input instance G' can be encoded as a vector in = by first considering the weighted n x n adjacency matrix of the graph. We can then flatten the matrix into a vector of dimension n² and then append 3-sparse binary vector of length n, corresponding to the three vertices in the input. We also assume that the output of has most dimension, indicating a binary vector for which vertex should be split from the other two vertices.
52

---

Learning-Augmented Hierarchical Clustering
We define a loss function L f + R, which intuitively defines how accurate predictor / performs on each input instance G. For example, can represent the splitting oracle on G and I. can denote the number of inaccurate responses compared to the best hierarchical clustering on G.
Now our goal is to learn the function f E F, which minimizes the following objective:
G- G.D.(s...eevva [[,f((z,,2))]
(3)
Let f* be an optimal function in F., so that f argmin G-D, (A [ifc 2))] is minimizer of the above objective. Assuming that for each graph instance G. triplet (x, y,, E V, and each ʃ F, we can efficiently compute fa(2, y, 2) as well as [(fa(z, y, 2)2, say in polynomial time [mn), then have:
E
Proposition 29. There exists an algorithu that uses poly (T(n), :) samples and returns a function f. such that with probability least To
E G-D. G-D((agg,eevs [ min E (a.,()
((fo(Z,,,2))) +e.
In particular, Proposition 29 is a PAC-style result that bounds the number of samples necessary to achieve a good probability of learning an approximately-opiinn
function f. The algorithm corresponding to Proposition 29 is straightforward; is simply the empirical minimizer after a sufficient number of samples are drawn. To prove correctness, we first require the following definition of sseudo-dimension for a function class, which a generalization VC dimension veal-valued functions.
Definition 30 (Pseudo-dimension, e.g., Definition 9 in (Lucic et al., 2017)). Let X' denote ground set, and let F be collection of functions mapping elements from X' to the interval [0, 1]. Consider fixed set 5 {211-..,25,, C X, set of real numbers R = {ri,.... ....., where each E [0, 1J. and function f E F. The subset S {az S f(x;) 2 ri) is referred to as the induced subset of S determined by the function f and the real values R. We say that the set S with associated values R is shattered by F the number of distinct induced subsets is 1[S, f E FH = 2 Then the pseudo-dimension of F is defined as the size of the largest subset X' that can be shattered by F (or it is infinite if no such maximum exists).
Using pseudo-dimension we can now present an accuracy-sample complexity trade-off for empirical risk minimization with and the number of necessary samples. First, we define H be the class of functions in F composed with L, i.c.. H = (Lo f f F). Moreover, by normalization, can assume the range of L is contained within [0, 1]. Then we have the following generalization bounds:
Theorem 31. (Anthony & Bartleu, 1999) Lei D be distribution over problem instances in G, and let H be class of functions h G - [0, 1] with dsmudo-dimension dg. Consider ii.d samples G1, G2...., Gt drawn from D. There exists universal constant co such that for any e > 0, ift 2 co du then for all h E H. we have the following with probability at
least 9 10'
h(G.)
E G
(G) SE.
We have the following immediate corollary by applying the triangle inequality. Corollary 32. Let GI,..., G. be of independent samples from 'D and let h H. be a function that minimizes 7 E h(G.). If the number of samples is chosen as in Theorem 31, then with probability at least 9
To.
[(C]) I min E GoD GDD
E
1h~ (G)) + 2s.
Thus, the main question is to analyze the pseudo-dimension of our function class H. To that end, we first relate the seeudo-dimessonn to the VC dimension of a related class of threshold functions.
Lemma J.1
to VC dimension, Lemma 10 in (Lucic et al., 2017)). For any E H. let B,, denote the i.e., B (z, y) = sgn(h(z) - y). Then the pseudo-dinen dimension of H equals the VC-dimension of the subgraph class By = (B, h E H).
indicator function of the threshold function, functiion,
53

---

Learning-Augmented Hierarchical Clustering
What remains is to bound the VC dimension of the function to compute in the class, which follows from the following standard result. Lemma J.2 (Theorem 8.14 in (Anthony & Bartlett, 1999)). Let R RR {0, 1}, defining the class
== =(0,)) R*).
Assume that any function T can computed by an algorithm that takes as input the pair (0,z) E IR Re and produces the value z) after performing no more than of the following operations:
arithmetic operations
- x./ on real numbers,
comparisons involving
-.= and outputting the result of such comparisons,
outputring 0 or 1.
Then, the VC dimension T is bounded by Oaa2t² + lalogg).
We can now apply these results to prove Proposition 29 by instantiating Lemma J.2 with the computational complexity of evaluating any function in the class H.
Proof of Proposition 29. From Lemma J.1, we know that the pseudo-dimension of H. is equivalent to the VC dimension of the threshold functions defined by H. Next, from Lemma J.2, we observe that the VC dimension of the relevant class of threshold functions is polynomial in the computational complexity evaluating a function from the class. other words, Lemma J.2 implies that VC dimension of By (as defined Lemma J.1) polynomial the number of arithmetic operations required to compute the threshold function corresponding some H. According to our definition, this quantity is polynomial in T(n). Thus, the pseudo-dimension of H. is also polynomial in T(n), and the desired result follows.
Note that we initialize Proposition 29 with various oracles, in terms of the input and output predictions. Indeed, if each function in the family of oracles we are considering can be computed efficiently, then Proposition 29 guarantees that polynomial number of samples is sufficient to learn a nearly optimal oracle.
54


Reviews:
[{"review_id": "4i5ZMJGG7T", "reviewer": "Reviewer_HUGU", "summary": "Brief Summary of the Paper:\n\nThe paper introduces and studies learning-augmented algorithms for hierarchical clustering (HC) where the type of advice given comes in the form of a splitting oracle. This continues a long line of research on algorithms with ML predictions (or augmented with ML advice) and extends ideas to the context of hierarchical clustering. \n\nThe problem itself is Hierarchical Clustering where the output of the algo is a tree whose leaves are the given datapoints, and the input is a collections of points with pairwise similarities. The formal framework studied here is under the two objectives for Dasgupta's cost and Moseley-Wang reward objective. These two are complementary objectives (they add up to sth constant based on the input graph) and they try to encode the fact that similar points should be split as late in the hierarchy as possible.\n\nThe main contributions are 5 algorithms that leverage this abovementioned ML splitting oracle to achieve improved approximation guarantees for Dasgupta’s and Moseley-Wang’s objectives. Importantly, all the algorithms construct partial HC trees (strongly or weakly consistent with the optimal tree) using the oracle, then refine them using techniques like sparsest cut. Sparsest Cut was one of the first methods to be used for obtaining good approximation algorithms for Dasgupta's cost and here the authors show how to exploit it for the framework of advice.\n\nA meta-comment here, is that the authors, through this ML oracle splitting aadvice, they are able to go beyond hardness results that hold for the HC objectives in the standard worst-case input (i.e. without the advice).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review and positive evaluation. Our responses are as follows.\n\n> Additional References\n\nWe agree with the reviewer that discussing the related papers and in particular the role of adversarial noise will help demonstrate the challenges with constructing a near-optimal tree. We thank the reviewer for pointing out the additional references; we have added these discussions to the new version. \n\n> O(n^2) time vs. ‘near-linear’.\n\nDue to the construction of weak partial trees, the run time of the algorithm is $\\tilde{O}(n^2)$ even if the input graph has $m=o(n^2)$ edges. However, since the similarity graph on $n$ vertices has $\\Omega(n^2)$ edges, our algorithm is still near-linear time. We have clarified this point in the updated version. \n\nFurthermore, we believe it is possible to revise our weakly consistent partial tree algorithm to input sparsity runtime, i.e., $o(n^2)$ runtime when the similarity graph is sparse. This could be an interesting direction to pursue as a future step.\n\n> Other Comments or Suggestions.\n\nWe have addressed these points – thanks for the suggestions!", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The paper assumes we have access to a splitting oracle; all algorithms are based on this assumption. Appendix J shows that it is possible to learn such an oracle efficiently. Overall, this setting is reasonable for a theory paper, and it is interesting from a practical perspective as well.", "theoretical_claims": "This is a proof-heavy paper. I checked the main body and proofs from Appendix B (Technical Overview), and overall I believe it is solid.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper is studying HC which is at the heart of many different applications. So as such, it presents interesting results to many other papers from the litearture.", "essential_references_not_discussed": "I believe that it's better to point out why adversarial noise is important: constructing the optimal tree is easy if the oracle always gives the correct triplet. (check Aho et al. \"Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions.\", 1981). Studying models where triplets (or even quartets info is given, has been studied in other works listed below, and it would be good to provide some comparison with your setting) Other related works not cited:\n\n\n1. Chatziafratis, Vaggos, Rad Niazadeh, and Moses Charikar. \"Hierarchical clustering with structural constraints.\" International conference on machine learning. PMLR, 2018.\n\n2. Ghoshdastidar, Debarghya, Michaël Perrot, and Ulrike von Luxburg. \"Foundations of comparison-based hierarchical clustering.\" Advances in neural information processing systems 32 (2019).\n\n3. Alon, Noga, Yossi Azar, and Danny Vainstein. \"Hierarchical clustering: A 0.585 revenue approximation.\" Conference on Learning Theory. PMLR, 2020.\n\n4. Vaggos Chatziafratis, Mohammad Mahdian, Sara Ahmadian. \"Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT.\", AISTATS 2021\n\n5. Jiang, Tao, Paul Kearney, and Ming Li. \"A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application.\" SIAM Journal on Computing 30.6 (2001): 1942-1961.\n\n6. Snir, Sagi, and Raphael Yuster. \"A linear time approximation scheme for maximum quartet consistency on sparse sampled inputs.\" SIAM Journal on Discrete Mathematics 25.4 (2011): 1722-1736.\n\n7. Alon, Noga, Sagi Snir, and Raphael Yuster. \"On the compatibility of quartet trees.\" SIAM Journal on Discrete Mathematics 28.3 (2014): 1493-1507.\n\nIncluding these would better capture the background for introducing your problem.", "other_strengths_and_weaknesses": "Strengths: \n\n-This work is the first time that combines Learning-Augmented algorithms with HC, which is creative. The paper is well-written.\n\n-The reviewer thinks this is a very natural setting, and the authors do a good job motivating and explaining overall their approach.\n\n-The algorithms and proofs are very interesting and constitute solid contributions.\n\n-All results are interesting in their own right but also when comparing with some expected hardness of the problems studied and how the authors bypass it.\n\nWeakness:\n\n-I couldn't find serious weaknesses (other than some minor literature omissions). Overall, this is a nice theoretical contribution that could benefit from a discussion about the lower bounds (samples, runtime etc.) and/or some experimental section, though I don't think this reduces the value of the contribution as is.", "other_comments_or_suggestions": "-It seems that (1/2 + ε) should be (1/2 - ε) in the context of discussing success probabilities (Appendix I.1, lines 2803-2806). PLease check.\n\n\n-It would be better to include some overview or intuition of the proofs in the main text!", "questions_for_authors": "For constructing weakly consistent trees: if the input has m edges, what would be the runtime of your algo? why is ~O(n^2) is considered near-linear? Do you assume that all edges are present or sth like this? I think you should clarify that.", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "XGPSvVg95J", "reviewer": "Reviewer_xyMS", "summary": "This paper explores hierarchical clustering in a learning-augmented framework. Unlike other clustering methods such as $k$-means or $k$-medians, hierarchical clustering constructs a clustering tree $\\mathcal{T}$ to represent similarity across all item pairs, and does not have a predetermined target number of clusters. The quality of $\\mathcal{T}$ can be assessed using various metrics; this work focuses on the Dasgupta and Moseley-Wang objectives.\n\nThe study assumes access to a splitting oracle that, given any triplet of items $(u,v,w)$, predicts which one should split away first in the optimal clustering tree $\\mathcal{T}^*$. The oracle’s predictions are assumed to be correct with probability $9/10$ and arbitrary otherwise. The paper investigates how leveraging these predictions enables the design of efficient polynomial-time approximation algorithms.\n\nFor the Dasgupta objective, the best-known polynomial-time algorithm achieves an $O(\\sqrt{\\log n})$-approximation, and no polynomial-time algorithm can guarantee a constant approximation. The authors overcome these limitations by utilizing the splitting oracle. They show that with $O(n^3)$ oracle queries, it is possible to achieve with high probability the following\n- A constant-factor approximation in $O(n^{50002})$ time, instead of exponential time in the setting without predictions. While this result is not practical because of the extremely high polynomial degree, it is interesting from a theoretical point of view as it shows that using an oracle allows breaking classical impossibility results.\n- An $O(\\sqrt{\\log \\log n})$-approximation in $O(n^4)$ time.\n\nFor the Moseley-Wang objective, the authors propose a $(1-o(1))$-approximation algorithm that requires $O(n^2)$ oracle queries and runs in $O(n^2 \\text{poly} \\log n)$ time. This surpasses the impossibility result of Chatziafratis et al. (2020) for the setting without predictions.\n\n## Update after rebuttal\nMy primary concern with this paper is in the assumption that the oracle is correct with a fixed, known probability of 0.9. This assumption weakens the results, as it is unclear how the algorithm's performance scales with varying oracle accuracy. Moreover, the assumption that the success probability is known contradicts the core motivation behind learning-augmented algorithms, which is to design algorithms having a good performance without any knowledge of the oracle accuracy.\n\nIn their rebuttal, the authors state that their algorithms still work when the oracle is correct with probability $1/2 + \\epsilon$, and gives uniformly random predictions with the remaining probability. They refer to this as \"the standard model,\" but this is not correct. The standard model in algorithms with $\\epsilon$-accurate predictions assumes that the oracle is correct with probability $\\epsilon$ and adversarial otherwise, which is the model studied in the paper, and which requires $p=0.9$.\n\nThe authors also claim that the algorithm does not require precise knowledge of $p$, but only that $p \\geq 1/2 + \\Omega(1)$ for some sufficiently large $\\Omega(1)$. However, without specifying the constant hidden in the $\\Omega(1)$, this claim is trivial and uninformative, as the algorithm already works for $p \\geq 0.9$. Thus it does not address my concern.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and insightful questions. Our responses and clarification are as below.\n\n> The paper deviates from the standard setting of learning-augmented algorithms, which assumes no guarantees on the quality of predictions.\n\nAlthough there is a body of literature that assumes no guarantees on the quality of predictions, we believe the setting with performance guarantees for the predictions is also quite standard, especially for graph-related problems. To that end, we have expanded the discussion on the “algorithms with $\\epsilon$-accurate predictions”, including “Learning-Augmented Streaming Algorithms for Approximating Max-Cut” (DVP [ITCS’25]), “Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems” (COGLP [NeurIPS’24]), and “Learning-augmented Maximum Independent Set” (DBSW [APPROX’24]). \n\nWe want to emphasize that since we study an *offline* problem (as opposed to an online one), we could always guarantee *robustness* studied in the online learning-augmented algorithm literature by running a separate algorithm without prediction. In the end, we could evaluate the costs of the two HC trees (with and without predictions) and output the one with the lower cost.\n\n> Discussions about “algorithm actively decides when to query predictions, rather than receiving them as a fixed input”\n\nWe agree that our algorithm requires adaptivity, and we can add more discussion about this in future versions. Thanks for providing the related literature. \n\n> Assuming an oracle with p=0.9 accuracy is quite restrictive.\n\nFirst, we want to clarify that our discussion did not mention the error probability of $1+\\varepsilon$ but rather $1/2+\\varepsilon$ and $1/2+\\Omega(1)$. Due to the offline nature of our problem, indeed, we could recover the best result for hierarchical clustering when the prediction is bad by simply running a separate algorithm without using any prediction. We also discussed a simple example (in I.1) that requires the correct probability to be at least 3/4. This is due to the combinatorial subroutines used in our algorithm\n\n> Accessibility.\n\nWe thank the reviewer for the comments on readability. We have strived to make the paper readable by inserting multiple figures and explaining things in detail as much as possible, e.g., by providing intuition for both our algorithm and our analysis in the technical overview that is Appendix B. Although elements of our results have multiple moving parts and are complex to describe, we completely agree that accessibility is an important part of the paper. Thus, we will continue to make editorial passes over the document to improve presentation. \n\n> The accuracy of the oracle is denoted $1-\\delta$ vs. $p$\n\nWe thank the reviewer for pointing this out, and we have made changes accordingly.\n\n> In Section 5, the complexity of Algorithm 3 seems quadratic and not near linear.\n\nWe view the input as the similarity graph with $\\Omega(n^2)$ edges on $n$ vertices, so that the input size is $\\Omega(n^2)$ and thus our algorithm that has runtime roughly quadratic in the number of vertices actually has runtime near-linear in the input size. We have clarified this point. \n\n> The bound in Proposition 13.\n\nWe only deal with *discrete* random variables in this paper, and for all the applications of Proposition 13, we only used supports on $\\{0,1\\}$. For discrete random variables with supports as a (finite) set of value between $[0,1]$, the bound should be true also. We agree that Chernoff bounds on *continuous* random variables might be different, and we will make Proposition 13 more precise in later versions.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "All the proofs are in the appendices. I skimmed through some proofs to grasp the main ideas and overall logic but did not examine any in detail.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper studies the problem of hierarchical clustering augmented with a splitting oracle. \nTo my knowledge, this is the first paper studying this problem. Therefore, there are no prior works proving results in the same setting.\n\nThe authors show that using the oracle allows significant improvement upon previous algorithms and results for the problem of hierarchical clustering, and even break impossibility results. The improvements are cited in my summary of the paper.", "essential_references_not_discussed": "The paper gives a very good overview of state-of-the-art results of hierarchical clustering without predictions, which allows a good understanding of the proposed results and their relevance.\n\nThe paper deviates from the standard setting of learning-augmented algorithms, which assumes no guarantees on the quality of predictions. Instead, it considers a specific scenario where predictions are independently accurate with a certain probability, which is referred to in the literature as \"algorithms with $\\epsilon$-accurate predictions\". While some prior works on similar settings (for other problems) are cited, there is no discussion on the model. Maybe this should be made more explicit in the introduction.\n\nA very interesting aspect of the paper is that the algorithm actively decides when to query predictions, rather than receiving them as a fixed input as the standard setting in learning-augmented algorithms, and an objective is to have a small number of queries. The authors should emphasize this feature more and consider citing relevant works that explore similar settings. Such works include for example\n- \"Parsimonious Learning-Augmented Caching\", Im et al. 2022\n- \"Algorithms for Caching and MTS with reduced number of predictions\", Sadek et al. 2024\n- \"Learning-Augmented Priority Queues\", Benomar et al. 2024", "other_strengths_and_weaknesses": "**Strengths**.  \n- The setting is very interesting, and the oracle model makes sense\n- The authors consider different objective functions and improve upon standard results for all of them\n- The problem is technically challenging, yet the paper provides many strong results.\n\nWeaknesses:\n- Assuming an oracle with accuracy $p = 0.9$ is quite restrictive. The authors mention in the appendix that their results can be generalized for $p = 1 + \\epsilon$ with $\\epsilon$ above some unknown constant—though this is trivial, as the results already hold for $p = 0.9$. However, I find their arguments unconvincing. Understanding the dependency on $p$ is crucial for quantifying the impact of oracle accuracy. Additionally, for $p = 0.5$, the algorithm should be able to perform as good as standard hierarchical clustering methods without predictions (e.g., for the Dasgupta objective). This suggests the possibility of designing an algorithm that interpolates between the performance of the best algorithm without predictions, when $p$ is close to 1/2, and the optimal algorithm when the oracle is perfectly accurate. Moreover, the choice of $p=0.9$ is extremely arbitrary if the precise value $0.9$ is used nowhere in the proofs.\n- The paper is difficult to read: Some sections/paragraphs are extremely wordy (Section B.1 for example), notations are used before being introduced, some paragraphs are very poorly written (for eg. L 403-412 (left column)), some sentences are very informal (L 813: 'this is a big “suppose” as we will see later'), ...", "other_comments_or_suggestions": "The accuracy of the oracle is denoted $1-\\delta$ in Lign 72 (right column), while it is denoted $p$ in the rest of the paper", "questions_for_authors": "1/ In Section 5, the complexity of Algorithm 3 seems quadratic and not near linear: the algorithm uses the construction of Theorem 11, which requires O(n^2) queries and $\\Omega(n^2)$ time, then another sublinear operation. The overall complexity is near-quadratic, and not near-linear as the section title suggests. Can the authors clarify this?\n\n2/ Can the authors give a reference or proof for the concentration bound of Proposition 13?   \nThe bound they state is known to be true for Bernoulli random variables, i.e. taking values in the set {0,1}, and not for any random variables bounded in $[0,1]$ a.s.", "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": "", "extra_scores": {}}, {"review_id": "IcoM3hXKWk", "reviewer": "Reviewer_vBZ1", "summary": "The paper studies learning-augmented algorithms for hierarchical clustering (HC). In this problem, a set of data points is given along with a similarity measure, which induces a weighted undirected graph $G=(V,E,w)$. The goal is to partition the points/vertices into a binary tree that captures the hierarchical relationships within the data. The paper considers two objective functions: the Dasgupta cost minimization objective (Dasgupta, 2016) and the Moseley-Wang revenue maximization objective (Moseley & Wang, 2017). For Dasgupta’s objective, prior work (Charikar & Chatziafratis, 2017a; Roy & Pokutta, 2017) showed that there is no polynomial-time algorithm that could achieve any constant-factor approximation under the Small Set Expansion hypothesis. The best-known algorithm achieves an $O(\\sqrt{\\log n})$-approximation (Charikar & Chatziafratis, 2017b; Cohen-Addad et al., 2019). For the Moseley-Wang objective, (Chatziafratis et al., 2020b) showed that achieving a $(1 − C)$-approximation is impossible under the Small Set Expansion hypothesis for some fixed constant $C \\in (0, 1)$.\n\nMotivated by the practical aspect of the problem, the paper considers HC with learning-augmented oracles. Specifically, it introduces a splitting oracle that, when queried for a triplet of vertices, outputs the vertex that is first separated away from the other two with respect to an optimal HC tree. The oracle returns the correct answer with probability $p$ and returns arbitrarily with the remaining probability. Using such a predictor, for Dasgupta’s objective, the paper achieves a constant-factor approximation in polynomial time (albeit with a large exponent), and a more practical $O(\\sqrt{\\log \\log n})$-approximation that improves upon the state-of-the-art. For the Moseley-Wang objective, the paper achieves any constant factor approximation in polynomial time, which overcomes prior impossibility barriers. The key technical contribution of the paper is the introduction of partial HC trees, which capture structural properties of optimal HC trees. The paper shows that these partial HC trees can be efficiently constructed given access to the splitting oracle, independent of the specific objective function.\n\nThe paper further explores sublinear algorithms for HC with splitting oracles (in the streaming and PRAM model), and obtains results that outperform their non-learning counterparts.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful questions and positive evaluation. Our responses to the questions are as follows.\n\n> The error probability of the splitting oracle cannot be too large\n\nWe agree with the reviewer that this is a limitation of our algorithm, and due to the combinatorial nature of many subroutines, it’s unclear exactly what minimal error can be tolerated on this front. However, we hope that modern ML models can achieve decent accuracy across the entirety of the similarity graph, which may consist of a number of dissimilar items. \n\nWe agree that additional experiments could add value to the paper. We have conducted preliminary experiments on social network-like graphs and plan to expand the discussion accordingly.\n\n> Typos \n\nThanks for pointing these out. We will make changes accordingly.\n\n> Implementing the oracle in small space\n\nThis is a great question. We are not exactly sure how the oracle could be implemented in small space. However, since the input of the oracle is only triplets of vertices, and the output is essentially an ordering, the model size could be very small (say, for a 3-layer neural network, we could implement with 3xNx1 with one N-node hidden layer). Of course, to ensure good performances, the actual model might need to be bigger. We could also use cloud-based services, and the aim is to reduce the memory cost on local machines. For instance, we could query the triplets to LLMs and implement the streaming algorithm on our local machine. Exploring whether these ideas work is an interesting direction to pursue. \n\n> Potential sublinear time algorithms\n\nWe believe it is possible to revise our weakly consistent partial tree algorithm to achieve *sublinear* (i.e., $o(n^2)$) time. The `counterpart testing’ subroutine, as we could see in the construction of the strongly consistent partial tree, could be made $O(n \\log{n})$ time. Due to the balanced partition, this part should take $\\tilde{O}(n)$ time across the algorithm. However, the ‘root test’, which is crucial to the correctness of our algorithm, still requires $O(n^2)$ time. Making this part sublinear time appears to require more work, and is an interesting direction to explore as future research.\n\n> Performance of the algorithm with random noise\n\nDue to the persistent noise and the combinatorial nature of our algorithm, it is difficult to get something in the form of query-quality trade-offs. If the noises are random, for the adversarial example we mentioned in appendix I.1, as long as $\\varepsilon=\\Omega(1/n)$, we should be able to obtain enough signals to distinguish the cases for the two sides. We also realize that the way it is currently written is not precise, and we meant to say that if the noise is random, we could guarantee correctness for any *constant* $\\varepsilon$ (as opposed to some fixed $C\\geq 1/4$). We will make changes about this in future versions.", "claims_and_evidence": "This paper is purely theoretical. All claims are formally stated as theorems or lemmas and are supported by rigorous proofs.", "methods_and_evaluation_criteria": "This paper is purely theoretical, and the proposed methods are analyzed through rigorous mathematical proofs. The evaluation is based on formal theoretical criteria, which are appropriate for the problem at hand.", "theoretical_claims": "I have checked all the content in the main text (i.e., the first 8 pages). However, I did not thoroughly verify all the proofs in the appendix. I reviewed the technical overview and sketched the proofs, and they appear to be correct.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper studies learning-augmented algorithms for hierarchical clustering. Hierarchical clustering is a well-studied problem. There are two main objective functions considered in prior work: the Dasgupta cost minimization objective (Dasgupta, 2016) and the Moseley-Wang revenue maximization objective (Moseley & Wang, 2017). The paper provides improved algorithms with respect to these two objectives in the learning-augmented framework, showing the power of machine learning oracles. Therefore, the paper is a good addition to the literature on learning-augmented algorithms.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n\n- Hierarchical clustering is a fundamental and extensively studied problem. The paper is well-motivated to study this problem in the learning-augmented setting with recent advances in machine learning. The paper is a good addition to the literature on learning-augmented algorithms.\n\n- The technical contributions are solid. The theoretical results outperform prior state-of-the-art and even impossibility barriers.\n\n- The paper is extremely well-written. The technical sections are clearly structured and easy to follow.\n\nWeaknesses:\n\n- the error probability of the splitting oracle cannot be too large, i.e., the success probability of the oracle is assumed to be at least 1/2+C, for sufficiently large $C=\\Omega(1)$. \n\n- Since the paper is motivated by the recent advances in machine learning, I think some empirical results for the proposed algorithms would strengthen the evaluation.", "other_comments_or_suggestions": "Typos:\n\n- Page 1, Line 49, right column: $1+C$ -> $1-C$\n- Page 3, Line 149, right column: deonte -> denote\n- Page 4, Line 168, left column: I think $level_\\mathcal{T}(\\cdot)$ is not formally defined.\n- Page 4, Definition 5: Should $\\mathcal{T}$ be $\\mathcal{T}^*$?\n- Page 5, Definition 8: ‘the same set of vertex’ -> ‘the same set of vertices’; also applies to Definition 9.\n- Page 7, Line 356, left column: I think a period is missing.", "questions_for_authors": "Q1: I am curious about the practical aspects of the splitting oracle in the streaming setting. While the paper assumes that the oracle is given offline and queried as a black box, is there any possibility that the oracle can be implemented using small space?\n\nQ2: Do you see any chance for your algorithms to be made sublinear time?\n\nQ3: In line 2813, you mentioned that for *random* incorrect answers, you will be able to work with $1/2+\\epsilon$ success probability for any $\\epsilon>0$. Could you give more details on that? Specifically, how does the resulting approximation ratio depend on  $\\epsilon$?", "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": "", "extra_scores": {}}, {"review_id": "Aj3OiAoZZO", "reviewer": "Reviewer_Q4HP", "summary": "Hierarchical clustering, wherein vertices (representing items in a dataset) are grouped into clusters of increasing refinement following a tree structure, is a well-motivated procedure of interest to practitioners and gives rise to interesting theoretical problems. In particular, several of the most prominent objectives in hierarchical clustering admit impossibility results. In this work, the authors show that having even only marginally informative predictions allows one to overcome these impossibility results. They consider a “splitting oracle,” which given an input triple of three vertices outputs a single vertex. With probability $p$, this output vertex is the first vertex that would be separated from the other two in some (near-)optimal hierarchical clustering tree. With probability $1-p$, the oracle outputs an arbitrary vertex. For small constant values of $p$, e.g. $p= ½ + \\varepsilon$ for $\\varepsilon > 0$ fixed, this oracle gives only a small amount of additional information to the algorithm. Yet the authors show that this is enough to drastically reduce the hardness of the problem.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review, positive evaluation, and helpful questions. Our responses and clarifications are as follows.\n\n> Relation To Broader Scientific Literature\n\nThanks for pointing out the additional papers related to our work. We will add them and some discussions about the connections.\n\n>  I do think the assumption of large probability of success (p=9/10) was surprising to me, as in other works (e.g. max-cut and max IS with predictions) the emphasis is on overcoming barriers using arbitrarily small probability of success. I would suggest that an abridged discussion of this assumption be presented closer to the statements of the main theorems, as currently it could be overlooked in the main body of the paper.\n\n> After reading Appendix I.1, it is now my understanding that for arbitrary (adversarial) incorrect responses, a significantly large probability of success is necessary (see Questions below), while for randomly-chosen incorrect responses, probability $½+\\varepsilon$ does suffice. Is this understanding correct?\n\n> (Q2) In Appendix I.1, I am confused about some of the remarks about general success probabilities. The penultimate line states “...we remark our algorithm would work for any success probability ½ + C for sufficiently large C.\n\nWe answer these concerns and questions together here since all of them are related to the success probability of the learning-augmented oracle. We first want to say that the reviewer’s understanding of our algorithm is correct: in the setting of adversarial noise, the success probability should be at least $1/2+C\\geq 3/4$, and $9/10$ suffices. On the other hand, if the errors of the oracle are random, we should be able to ensure correctness with $1/2+\\varepsilon$ for any constant $\\varepsilon>0$ (we forgot to mention “constant” in the current Appendix I.1 and will add that in the final version).\n\nThe reason our algorithm should work with a sufficiently high success probability is exactly due to the hierarchical structure of the problem. In both max-cut and MIS papers (which we are sufficiently familiar with), the errors in the algorithm are ‘one-shot’. However, in the HC problem, if the construction of the partial tree is wrong at any level, the error will propagate to all subsequent nodes, and it is not clear how one could control the error if this happens. Furthermore, the oracles in the max-cut and MIS papers are about ‘memberships’, while the oracle in our setting is about ‘relationships’. The latter type of oracle does not give *any* trivial solution or even a ‘partial solution to be fixed’ (like the case in the MIS paper). Therefore, a constant success probability much larger than $1/2$ is necessary.\n\n> In the exposition, $\\delta$ is used to denote success probability, while later $p$ is used.\n\nThanks for the catch! We will unify this and use $p$ as the success probability.\n\n> Is there an intuitive reason why the results established in this work only apply to the Mosely-Wang (MW) and Dasgupta (Das) objectives, as opposed to the Cohen-Adad (CA) objective? In particular, it is striking that the impossibility results for oblivious algorithms for both MW and Das stem from the Small Set Expansion hypothesis, whereas impossibility results for the CAobjective stem from UCG. Is the fact that your results focus on MW and Das implicitly connected to this divide?\n\nWe do not believe our results are connected to the division between the UGC vs. small set expansion. The reason is that our constructions for the weakly and strongly consistent partial trees are objective-oblivious, and we can also construct these partial trees w.r.t. the Cohen-Addad objective. The reason for us not getting results for the Cohen-Addad objective is due to the limited bandwidth, we are not sure how the error would propagate in the CA objective. It will be an interesting direction to explore as a future step.", "claims_and_evidence": "Claim: Learning-augmented algorithms can efficiently approximate optimal HC trees for prominent HC objectives, breaking impossibility barriers.\n\nEvidence: \n- In Thm 1, they show that for $p=9/10$, there exists a polynomial-time algorithm that makes $O(n^3)$ queries and produces a constant approximation to the Dasgupta (Das) optimal HC tree.\n- In Thm 2 they improve the running time, showing that an $\\tilde{O}(n^3)$ time algorithm that makes $O(n^3)$ queries produces an $O(\\sqrt{\\log\\log(n)}$ approximation to the Das optimal HC tree.\n- In Thm 3 they show an $\\tilde{O}(n^2)$ time algorithm that makes $O(n^2)$ queries produces a constant approximation to the Moseley-Wang (MW) optimal HC tree.", "methods_and_evaluation_criteria": "Not applicable; this is a theoretical work and does not include experiments.", "theoretical_claims": "I did not check any of the proofs in the supplementary material.", "experimental_designs_or_analyses": "Not applicable; this is a theoretical work and does not include experiments.", "relation_to_broader_scientific_literature": "Learning-augmented algorithms/algorithms with predictions have been an area of expanding recent study. Several works in this area have focused on showing that even marginally-informative predictions (i.e. those whose probability of giving a correct response is arbitrarily close to ½) can break hardness barriers for classical well-studied problems, such as max-cut, independent set.\n\nCohen-Addad, Vincent, et al. \"Max-Cut with $\\epsilon $-Accurate Predictions.\" arXiv preprint arXiv:2402.18263 (2024).\n\nBraverman, Vladimir, et al. \"Learning-augmented maximum independent set.\" arXiv preprint arXiv:2407.11364 (2024).\n\nThis work similarly studies how predictions can break impossibility results for hierarchical clustering.", "essential_references_not_discussed": "I do not know of any essential references that are not discussed.", "other_strengths_and_weaknesses": "Strengths:\n- This work clearly establishes that predictions fundamentally decrease the hardness of well-motivated hierarchical clustering problems.\n- Several of the algorithms proposed (esp. Algo. 2 and 3) seem like they could be implemented in practice. It would be interesting to compare the performance of these theoretically-grounded algorithms with heuristics used for HC in practice.\n- The partial HC trees introduced could be objects of further study. They seem well-motivated for practitioners, who may be content to learn a hierarchical clustering that encompasses only the majority of vertices, and leaves some reasonably-sized sub-population ambiguous.\n\nI find no major weaknesses in the work, but I did not check the proofs included in the supplementary material. I do think the assumption of large probability of success (p=9/10) was surprising to me, as in other works (e.g. max-cut and max IS with predictions) the emphasis is on overcoming barriers using arbitrarily small probability of success. I would suggest that an abridged discussion of this assumption be presented closer to the statements of the main theorems, as currently it could be overlooked in the main body of the paper.", "other_comments_or_suggestions": "The assumption of large success probability p=9/10 and highlights from the Discussion of general success probabilities (Appendix I.1) should be emphasized earlier in the text. When I first read Thms. 1-3, I assumed based on the exposition that they held for any arbitrarily small yet constant probability of success (e.g. ½ + \\varepsilon). After reading Appendix I.1, it is now my understanding that for arbitrary (adversarial) incorrect responses, a significantly large probability of success is necessary (see Questions below), while for randomly-chosen incorrect responses probability $½ + \\varepsilon$ does suffice. Is this understanding correct?\n\nIn the exposition, $\\delta$ is used to denote success probability, while later $p$ is used. I would suggest picking one of the two and using it consistently, as there's already several symbols floating around that describe success probabilities (e.g. $\\varepsilon$ and $C$). If I am confused and actually $\\delta$ and $p$ have different meanings, please correct me.", "questions_for_authors": "I already feel the paper is compelling. These questions are mostly for my own understanding.\n\n1. Is there an intuitive reason why the results established in this work only apply to the Mosely-Wang (MW) and Dasgupta (Das) objectives, as opposed to the Cohen-Adad  (CA) objective? In particular, it is striking that the impossibility results for oblivious algorithms for both MW and Das stem from the Small Set Expansion hypothesis, whereas impossibility results for the CAobjective stem from UCG. Is the fact that your results focus on MW and Das implicitly connected to this divide?\n\n2. In Appendix I.1, I am confused about some of the remarks about general success probabilities. The penultimate line states “...we remark our algorithm would work for any success probability ½ + C for sufficiently large $C=\\Omega(1)$.” I am confused by the meaning of $C=\\Omega(1)$ when discussing success probabilities, as this does not seem to imply any nontrivial lower bound on C. Do the authors have a more specific lower bound on ½ + C in mind? The main results of the paper imply that ½ + C = 9/10 suffices, while the counter-example in Appendix I.1 implies that ½ + C must be at least ¾.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The submission studies learning-augmented algorithms for hierarchical clustering. Most reviewers are very positive about the submission, and I think that the weakness pointed out by the reviewers can be easily addressed. Hence, I recommend to accept the paper.
Decision: Accept (poster)