Fitting trees to $\ell_1$-hyperbolic distances
Authors: Joon-Hyeok Yim
Anna Gilbert
Venue: NeurIPS 2023 poster (2023)
Keywords: tree metric fitting
ultrametric fitting
$\ell_1$-hyperbolicity

Abstract: Building trees to represent or to fit distances is a critical component of phylogenetic analysis, metric embeddings, approximation algorithms, geometric graph neural nets, and the analysis of hierarchical data. Much of the previous algorithmic work, however, has focused on generic metric spaces (i.e., those with no \emph{a priori} constraints). Leveraging several ideas from the mathematical analysis of hyperbolic geometry and geometric group theory, we study the tree fitting problem as finding the relation between the hyperbolicity (ultrametricity) vector and the error of tree (ultrametric) embedding. That is, we define a vector of hyperbolicity (ultrametric) values over all triples of points and compare the $\ell_p$ norms of this vector with the $\ell_q$ norm of the distortion of the best tree fit to the distances. This formulation allows us to define the average hyperbolicity (ultrametricity) in terms of a normalized $\ell_1$ norm of the hyperbolicity vector. Furthermore, we can interpret the classical tree fitting result of Gromov as a $p = q = \infty$ result. We present an algorithm \textsc{HCCRootedTreeFit} such that the $\ell_1$ error of the output embedding is analytically bounded in terms of the $\ell_1$-norm of the hyperbolicity vector (i.e., $p = q = 1$) and that this result is tight. Furthermore, this algorithm has significantly different theoretical and empirical performance as compared to Gromov's result and related algorithms. Finally, we show using \textsc{HCCRootedTreeFit} and related tree fitting algorithms, that supposedly standard data sets for hierarchical data analysis and geometric graph neural networks have radically different tree fits than those of synthetic, truly tree-like data sets, suggesting that a much more refined analysis of these standard data sets is called for.

Fitting trees to l1-hyperbolic distances
Joon-Hyeok Yim
Anna C. Gilbert
Abstract
Building trees represent fit distances is critical component of phylogenetic analysis, metric embeddings, approximation algorithms, geometric graph neural nets, and the analysis of hierarchical data. Much of the previous algorithmic work, however, has focused on generic metric spaces (i.e., those with no a priori con- straints). Leveraging several ideas from the mathematical analysis of hyperbolic geometry and geometric group theory, we study the tree fitting problem as finding the relation between the hyperbolicity (ultrametricity) vector and the error of tree (ultrametric) embedding. That is. we define a vector of hyperbolicity (ultrametric) values over all triples of points and compare the l norms of this vector with the by norm of the distortion of the best tree fit to the distances. This formulation allows to define the average hyperbolicity (ultrametricity) in terms of normalized & norm of the hyperbolicity vector. Furthermore, tree fitting result Gromov as a p = = oo result. We present an algorithm HCCROOTED
can interpret the classical
such that the ε error of the output embedding is analyti- cally bounded in terms of the & norm of the hyperbolicity vector (i.e., q 1) and that this result is tight. Furthermore, this algorithm has significantly different theoretical and empirical performance as compared to Gromov's result and related algorithms. Finally, show using HCCROOTED algorithms, that supposedly standard data sets for hierarchical data analysis and geometric graph neural networks have radically different tree fits than those of synthetic, truly tree-like data sets, suggesting that a much more refined analysis these standard data sets is called for.
and related tree fitting
Introduction
Constructing trees or ultrametrics to fit given data are both problems of great interest in scientific applications (e.g., phylogeny), algorithmic applications (optimal transport and Wasserstein distances are easier, for example, to compute quickly on trees), data visualization and analysis, and geometric machine learning. An ultrametric space is in which the usual triangle inequality has been strengthened to d(z, y) S max max(d(<, 2), d(y, 2)}. A hyperbolic metric space is one in which the metric relations amongst any four points are the same they would be in tree, up to the additive constant Ó. More generally, any finite subset of a hyperbolic space "looks like" a finite tree.
There has been a concerted effort to solve both of these problems in the algorithmic and machine learning communities, including (1(55 among many others. Indeed, the motivation for embedding into hyperbolic space or into trees was the heart of the recent explosion in geometric graph neural networks (6).
As an optimization problem, finding the tree metric that minimizes the f, norm of the difference between the original distances and those on the tree (i.e., the distortion) known to be NP-hard for most formulations. [7] showed that it is -ard under the lo norm. The first positive result also came from [7], which provided 3-approximation algorithm and introduced a reduction technique from a tree metric an ultrametric (a now widely used technique). The current best known result is an ((log n log log 1/)) approximation for 1 < oo (2) and O(1) approximation for p = 1,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Hyperbolicity measure
Value
Distortion
Gromov's 6-hyperbolicity
||d - drl 00 = log log = O[1 A 21100 logn)
Average hyperbolicity
||d dr 0(ôn") O A>llI)
Table 1:
Connection between 6-hyperbolicity and average hyperbolicity and how these quantities determine the distortion of the resulting tree metric.
recently shown by D. Both papers exploit the hierarchical correlation clustering reduction method and its LP relaxation to derive an approximation algorithm.
While these approximation results fruitful, they not practical (the LP result uses enormous number of variables and constraints). On the more practical side, (8] provided a robust method, commonly known Neighbor Join (which can be computed in O(n") time), for constructing tree. Recently, 99) proposed an (n?²) method known as TreeRep for constructing a tree. Unfortunately, neither algorithm provides guaranteed bound on the distortion.
The main drawback with discrete point set, when, in fact, many real application data sets are close to hierarchical nearly so. After all, why tree to generic data only to get a bad approximation? geometric assumptions on our data set, we can fit better tree metric or ultrametric, perhaps even more efficiently than for a general data set.
these results is that they assume almost nothing about the underlying
fact, perhaps with some
Motivated by both Gromov's ' d-hyperbolicity and the work of Chatterjee and Slonam 10 on average hyperbolicityy we define proxy measures of how tree-like a data set is. We note that 11 provide simple algorithm and analysis to find tree approximation for which the maximum distortion (E norm) is bounded by ( log n),, where 8 the hyperbolicity constant. Moreover, this bound turns out to be the best order we can have. In this paper, we go beyond the simple notion of 6-hyperbolicity to define vector hyperbolicity values (dd) for a set of distance values. The various Ep norms of this vector capture how tree-like data set is. Then, we show that the by norm of the distortion of the best tree and ultrametrics can bounded in terms of this tree proxy. Thus, give a new perspective on the tree fitting problem, use the geometric nature of the data set, and arrive at, hopefully, better and more efficient tree representations. The table below captures the relationship between the different hyperbolicity measures and the tree fit distortion. We note the striking symmetry in the tradeoffs.
Our main theoretical result can be summarized as
There an algorithm which runs in time On logn) n) which returns a tree metric dy with distortion bounded by the average (or f1) hyperbolicity of the distances; i...
10-1 AvgHyp(d)). ld drl11 S (d)l 58 (
Additionally, the performance of HCCROTTED TREEFIT and other standard tree fitting algorithms on commonly used data sets (especially in geometric graph neural nets) shows that they are quite far from tree-like and not well-represented by trees, especially when compared with synthetic data sets. This suggests that we need considerably more refined geometric notions for learning tasks with these data sets.
2 Preliminaries
2.1 Basic definitions
To set the stage, we work with finite metric space (X, d) and we set [X] = n. the number of triples in X as (?) = E, and (?) the number quadruples of points in X. In somewhat an abuse of notation, we let (3) denote the set of all triples chosen from X (and, similarly, for all quadruples of
points). Next, we recall the notion of hyperbolicity, which defined via the Gromov product (4).
Given metric space (X, d), the Gromov product of two points I, y E X with respect to a base point

---

X is defined as
1 = (d(x, w) + d(y, w) d(æ, y))
9Pw (z. v)
2
We use the definition of the Gromov product on two points with respect third to establish the four point condition and define
P x. y, =) max [min(gp.o m=), PPw (Ty, m²)) (TT Ty)] perm
where the maximum is taken over all permutations π the labels of the four points. Since Pw (d; y, 2) fp=(d; y, 2, w) fPy (P; w) = (d; z, y, w), sometimes denote the four point condition as fp(d: v. y, 2, w). Similarly, we define the three point condition as
tp(d; 2. y, 2) = max [TT, T2) max(d( my). (()))==))
perm
which we use to define ultrametricity.
Following standard definition of Gromov, metric space (X, d) is said to be 8-hyperbolic with respect to the base point w E X, if for any z, y, 2 E X, the following holds:
(P v) min(gp (P,(,, =)) -
We denote Hyp(d) 5, the usual hyperbolicity constant (similarly, UM(d), is the usual ultrametricity constant). We note that this measure hyperbolicity is worst case measure and, as such, it may give distorted sense of the geometry of the space. A graph which consists of tree and a single cycle, instance, is quite different from single cycle alone but with a worst case measure, we will not be able to distinguish between those two spaces.
In order to disambiguate different spaces, we define the hyperbolicity vector as the f-dimensional vector of all four point conditions with respect to d:
X 3
A (d) = [fp(d: x, U. 2, w)] for all x, y, E
Similarly, we define the ultrametricity vector as the Ê-dimensional vector of all three point conditions with respect to d:
A (d) = [tp[d; x, y, =)] for all r, y. E
We use the hyperbolicity and ultrametricity vectors to express more refined geometric notions. We define p-average hyperbolicity and p-average ultrametricity.
1/p
AvgHyp,
Σ
x, U,,
and
1/p
AvgUM,(d)
Σ (3)
tp(d; =)
pf 1, then the notions are simply the average (and we will call them so). Also, for clarity, note the usual hyperbolicity and ultrametricity constants Hyp(d) and UM(d) are the p Proposition 2.1. We have the simple relations:
(a) Hyp(d) = max,ex Ax (e) 2 (d)l()) for any x E X.
(b) UM(d)= = A (d)l
In the discussion of heirarchical correlation clustering in Section 2.4 and in the analysis of our algorithms in Section 3] we construct multiple graphs using the points of X vertices and derived edges, Of importance to our analysis is the following combinatorial object which consists of the set of bad triangles in graph (i.e., those triples of vertices in the graph for which exactly two edges, rather than three, are in the edge set). Given a graph G = (V, E), denote B(G), the set of bad triangles in G. as
B(G) == (x. y. E (y) (( v). (v. E = =2
3

---

2.2 Problem formulation
First, we formulate the tree fitting problem. Given a finite, discrete metric space (X, d) and the distance (() between any two points Ii, T. X, find tree metric (T, dr) in which the points in X are among the nodes of the tree and the tree distance dr(a;, 23y) is "close" to the original distance d(z;; F.)).
While there are many choices to measure how close dr and are, in this paper, we focus on the 4 error; i.e., ||d d| for 1 S S oo. This definition is itself shorthand notation for the following. Order the pairs of points (2,, . < lexicographically and write d (overloading the symbol d) for the vector of pairwise distances d(r;; F.). Then, seek tree distance function dr whose vector of pairwise tree distances is close in lp norm to the original vector of distances. For example, if p = oc, wish to bound the maximum distortion between any pairs X. If p 1, wish to bound the total error over all pairs. Similarly, we define the ultrametric fitting problem.
We also introduce the moted tree fitting problem. Given a finite, discrete metric space (X, d) and the distance d(x,, 21) between any two points Z;, Tjj E X, and a distinguished point w E X, find a tree metric (I', dr) such that ||d - drllp ll is small and dr(w, x) d(w, 2) for all x E X. Although the rooted tree fitting problem has more constraints, previous work (such as (7) shows that by choosing the base point appropriately, the optimal error of the rooted tree embedding is bounded by constant times the optimal error of the tree embedding. Also, the rooted tree fitting problem is closely
connected to the ultrametric fitting problem.
Putting these pieces together, we observe that while considerable attention has been paid to the by tree fitting problem for generic distances with only mild attention paid to the assumptions on the input distances. No one has considered both restrictions on the distances and more sophisticated measures of distortion. We define the fp/e, tree (ultrametric) fitting problem as follows.
Definition 2.2 (Cp/ /e tree (ultrametric) fitting problem). Given (X, d) with hyperbolicity vector (d) and A Ayg (d) (ultrametricity vector (d) and AvgUM, (d)), find the tree metrie (T; dr) (ultrametric (X, dy)) with distortion
|| drllp S AvgHyp, s(n) or Iddddyll llp S AvgUM, ((x)
for a growth function f(n) that as small as possible. (Indeed, f(n) might be simply a constant.)
2.3 Previous results
Next, we detail Gromov's classic theorem tree fitting. using our notation above. Theorem 2.3. (4) Given a 6-hyperbolic metric space (X, d) and a reference point x E X, there exists a tree structare T and its metric dr such that
1. T is w-restricted, ie., d(x, u) = dr(x, 4) for all E X.
2. ||d dr s 2 (1))l= - 2)1-
In other words, constant Hyp(d)= = 5 and the size of our input space X.
bound the maximum distortion of tree metric in terms of the hyperbolicity
2.4 (Hierarchical) Correlation clustering and ultrametric fitting
Several earlier works (2). (12) connected the correlation clustering problem to that of tree and ultrametric fitting and, in order to achieve our results, we do the same. In the correlation clustering problem, we given a graph G (V, E) whose edges are labeled "+" (similar) "_" (different) and we seek a clustering of the vertices into two clusters so as to minimize the number of pairs incorrectly classified with respect to the input labeling. In other words, minimize the number of "'" edges within clusters plus the number of "+" edges between clusters. When the graph G is complete, correlation clustering is equivalent the problem of finding an optimal ultrametric fit under the E and 2.
norm when the input distances are restricted to the values
Hierarchical correlation clustering is a generalization of correlation clustering that is also implicitly connected to ultrametric and tree fitting (see (T). (2. [12], (T3). In this problem, we are given a set of non-negativewwcihtt and set of edge sets. We seek partition of vertices that is both hicrarchical and

---

minimizes the weighted sum of incorrectly classified pairs of vertices. It is (weighted) combination of correlation clustering problems.
G = =V, with & 1 edge sets G; (V, E,), and k + weights & 2 0 for O < & < k, we seek a hierarchical partition Pt that minimizes the & objective function, E ( It is hierarchical in that for each t, Pt subdivides P
More precisely, given graph
Chowdury, et al. [3] observed that the Single Linkage Hierarchical Clustering algorithm (SLHC) whose output can be modified to produce an ultrametric that is designed to fit given metric satisfies a similar property to that of Gromov's 's tree fitting result. this case, the distortion bound between the ultrametric and the input distances is a function of the ultrametricity of the metric space.
Theorem 2.4. Given (X, d) and the output of SLHC in the form of an ultrametric dy, we have
|| - 1-ddlli ~o V (d) [logg 1}].
2.5 Reductions and equivalent bounds
Finally, we articulate precisely how the tree and ultrametric fitting problems are related through the following reductions. We note that the proof of this theorem uses known techniques from [2] and M although the specific results are novel. First, ultrametric fitting algorithm yields tree fitting algorithm.
Theorem 2.5. Given 1 S p < oo and S S OC. Suppose we have an ultrametric fitting algorithm such that for any distance function d on X (with [X| = n), the output dy satisfies
||d - du S AvgUM,(d) f(n) for some growth function f(n).
Then there exists a tree fitting algorithm (using the above) such that given an input d on X (with [X] n), the output dr satisfies
1/9
[dd-d1y dl 2
12
3
Avgllyp,(d) f(n) for same growth function f(n).
Conversely, a tree fitting algorithm yields an ultrametric fitting algorithm. From which we conclude that both problems should have the same asymptotic bound, which justifies our problem formulation.
Theorem 2.6. Given 1 S p and such that for any distance function d on X (with [X| = n.) the output dr satisfies
D0. Suppose that have tree fitting algorithm
||d - dr S AvgHyp, (d) [n) some growth function [(n).
Then there exists an ultrametric fitting algorithm (using the above) such that given an input d on X (with [X] n.), the output dr satisfies
||d dullz 3 (1
1/4
AvgUM, f(2n) for same growth function f()).
Proofs of both theorems can be found in the Appendix 6.2
Tree and ultrametric fitting: Algorithm and analysis
In this section, we present an algorithm for the p q ultrametric fitting problem. We also present the proof of upper bound and present an example that shows this bound is asymptotically tight (despite empirical evidence the contrary). Then, using our reduction from Section 2 produce a tree fitting result.
3.1 HCC Problem
As we detailed in Section correlation clustering is connected with tree and ultrametric fitting and in this section, we present a hierarchical correlation clustering (HCC) algorithm which bounds the number of disagreement edges by constant factor of number of bad triangles. We follow with a proposition that shows the connection between bad triangle objectives and the l ultrametricity vector.
5

---

Definition 3.1 (HCC with triangle objectives). Given vertex V and k edge sets, G. = (V, Fx)) for 0 S f S k. The edge sets are hierarchical so that F S Re+1 for each We seek hierarchical partition Pt so that for each f. Pt subdivides P++1 and the number of disagreement edges (P)) is bounded by C. [B() (where B denotes the set of bad triangles) for some constant C 0.
Note that this problem does not include the weight sequence {6,], as the desired output will also guarantee upper bound on Σ 5e ((P))))) the usual & objective.
This proposition relates the é vector norm A (d), the average ultrametricity of the distances, and the bad triangles in the derived graph. This result is why we adapt the hierarchical correlation clustering problem to include triangle objectives.
Proposition 3.2. Given distance function d on (2) (with
X = n) and s > 0, consider the (X)
s-neighbor graph G. (X, where Eg denotes {xx, v) E
2 (d(x, S 8). Then we have
(dd) = = AvgUM(() = [o |B(G.)lds.
3.2
Main results
Our main contribution is that the HCCTRIANGLE algorithm detailed in Section 3.3 solves our modified HCC problem and its output partition behaves "reasonably" on every level. From this partition, we can construct good ultrametric fit which we then leverage for a good (rooted) tree fit (using the reduction from Section 2
Theorem 3.3. HCCTRIANGLE oulputs hierarchical partition P. where |E,AE(P)) S 4- 4-|B()))) holds for every 0 v S ( = k. Furthermore, the algorithm runs in time (
By Proposition 3.2 and Theorem 3.3 we find ultrametric fit using the HCCTRIANGLE
subroutine to cluster our points. This algorithm we refer to as HCCULTRAFIT. Using Theorem 3.3 we have following L bound.
Theorem 3.4. Given d, HCCULTRAFIT outputs an ultrametric dy with ||d 22-dyl dulli S 4 A|1 48 AvgUM, (d). The algorithm runs in time O(n² logn).
In other words, HCCULTRAFTT solves the HCC Problem proof shows why adapting HCCTRIANGLE as a subroutine is successful.
3. with constant C = 4. The following
Proof of Theorem 3.4 from Theorem 3.3; Suppose the outputs of HCCTRIANGLE and
HCCULTRAFIT are (P) and dy, respectively. Denote d; == d(e;) (do = 0, d oc) and, for any & > 0, set
G, (X,,X, P. P. for de Ss d1+1-
Then, for any x. y (2),
see that (x, v) E E.AE(P))
d(æ, v) 8 dr v) or dr( S < d(z, 1)- Again, we use the integral notion from Proposition 3.2 Every edge (x, v) will contribute |E.AE(P.) with amount exactly |dy (x. y) d(x,, y)1. Then, by Theorem 3.3
||d - du
E,AE((P))ds
$ 4
|B = (d)]l,
desired. Assuming that HCCTRIANGLE (n² n) as the initial step of sorting over all pairs is needed. Thus ends the proof.
in time On,)). HCCULTRAFIT runs in time
By the reduction argument we discussed in Section 2 conclude the following:
put all of these pieces together to
Theorem 3.5. Given (X, d), can find two tree fits with the following guarantees:
Given base point point x E X, HCCRoOTEdT outputs a tree fit dr with ||d drll1 < A (d))l. The algoritium runs in O logn).

---

AvgHyp (d). Therefore, given (X, d) There exists & X where [|x,( S ("3²) one can find (rooted) tree metric dr with ||d - drili S 8("5') Avgllypi(d) in time On n).
3.3
Algorithm and analysis
Algorithm 1 ISHIGHLYYCONEECTED tests if two clusters highly connected.
function ISHIGILLYCONNEETED
Input: vertex set X, Y and edge set E
For I E X:
If Ky (1, v) E) M 2
return False
For Y:
!X If He E (1 y) E E}]
return False
return True
X
Y
X
Y
3
3
deg
deg
deg
deg
False
True
Figure 1: Illustration of highly connectedness condition
Algorithm 2 HCCTRIANGLE: Find HCC which respects triangle objectives
function HCCTRIANGLE
Input: V [11. . and an ordering of all pairs fe1,e2." "...e........................... ((3)) on V so that E,
{E1, ".,, (e).
Desired Output: hierarchical partition (Pt} for < t < le so that [EAE(P)) S B(G)) holds for every 1.
Init: P = ((r1), (v2).... [2n}}
Po -
Fort E (1,2,...,
J: Take e -z, v) with E C2 and E Cg (Cz, Cy P)
If Cr # Cy;
If IFiHHGHHCCCNNNNCTDEDCC Cy. F.) is true: add C C₂ U,, and remove Cas Cy P.
P. x P return (Pc}
In the rest of this subsection, we provide a sketch of the proof that HCCTRIANGLE provides the desired correlation clustering (the detailed proof can be found in Appendix 6.4). We denote the output of HCCTRIANGLE by (Pt} and also assume = E, and P: (Ci, C2 ... Cx). The algorithm HCCTRIANGLE agglomerates two clusters if they are highly connected, adds the cluster to the partition, and iterates. The key to the ordering of the edges input to HCCTRIANGI.E that they are ordered by increasing distance that the number of edges that are in "disagreement" in
7

---

Algorithm 3 HCCULTRAFIT: Ultrametric fitting algorithm, uses HCCTRIANGLE function HCCULTRAFIT(d)
Sort as fer.... (z)) } so that d(ei) S d(e2) S ... ........ssee ()))
[Pt} HCCTRIANGLE(X,, {e+))
dy (z. v) < d(ey) where j = argmin, (z, are in same cluster in Pt)
return du
the correlation clustering is upper bounded by the number of edges whose distances "violate" triangle relationship. The proof proceeds in bottom up fashion. (It is clear that the output partition is naturally hierarchical.) We count the number of bad triangles "within" and "between" clusters, which are lower bounded by the number of disagreement edges "within" and "between" clusters, respectively. The proof uses several combinatorial properties which follow from the highly connected condition. This is the key point of our proof.
From an ultrametricity fit to a rooted tree fit: Following procedure from Cohen-Addad et al. (T]. we can also obtain tree fit with the f objective. Note that the algorithm HCCROOTEDTREIIE takes the generic reduction method from ultrametric fitting algorithm but we have instantiated it with HCCULTRAFIT. For self-contained proof, see the Appendix 6.3
Proof of Theorem 3.5; This proof can be easily shown simply by applying Theorem 2.5 with p= 9 = 1 and f(n) (*))
Algorithm 4 Find tree fitting given an ultrametric fitting procedure
1: procedure HCCROOTEDTREEFTI
2: Input: distance function d on (²) and base point X
3: Output: (rooted) tree metric dr which fits d and d(x, w) dr (2, w) for X
4: < m d(z, w)
5: (o y) + 2M - d(x, w) d(y, w) for all æ. E (2)
6: dy + HCCULTRAFIT(d + cw)
7: dr t- du Cw
8: return dr
is seemingly expensive, there is way to implement HCCTRIANGLE so that all procedures run in ((n²) time. Thus, HCCULTRAFIT can be implemented so as to run in On2 log n) time. The detailed algorithm can be found in Appendix 6.5
Running Time Although
Asymptotic Tightness Consider (d, X) with X = ",,,", and d(z1,42) = d((1, 23)) = and 2 otherwise. Then we see that tp(d: #1, I2 n3) 1 and otherwise, so that ||
One 2z)) (x(2 2 2'-p for : dr d. When 1, ||d - derl || > || (d)l (G) AvgUM(() holds for any ultrametric du- While HCCULTRAFIT guarantees ||d do 1l s A ((d) = (()) AvgUM(d); this shows that
can easily check that for any ultrametric de, |c(z1, x22)
theoretical bound is asymptotically tight.
Examples demonstrating how HCCULTRAFiT works and related discussion can be found in Ap- pendix 6.7.1
4 Experiments
In this section, we run HCCROOTEDTREEFFT on several different type of data sets, those that are standard for geometric graph neural nets and those that are synthetic. We also compare our results with other known algorithms. We conclude that HCCROOTEDTREEFIT (HCC) is optimal when the data sets are close to tree-like and when we measure with respect to distortion in the & sense and running time. is, however, suboptimal terms of the lox measure of distortion (as to expected). We also conclude that purportedly hierarchical data sets do not, in fact, embed into trees with low distortion, suggesting that geometric graph neural nets should be configured with different geometric considerations. Appendix 6.9 contains further details regarding the experiments.

---

Data set
C-ELEGAN
CS PHD
CORA
AIRPORT
n
452
1025
2485
3158
Hyp(d)
1.5
6.5
11
1
AvgHly((d)
0.13
0.51
0.36
0.18
Bound
158.0
1384.5
2376.2
1547.1
HCC
0,90:1.19
2.60
2.4210.44
1.09
Gromov
+..4
4.79
1.
1.56+0.08
TR
0.83
2.55
2.91 +0.63
1.28
NJ
0.30
1.35
1.06
0.49
Table 2: Connection between hyperbolicity and average hyperbolicity and how these quantities
determine the average distortion (ld - drll1/ (²)) of the resulting tree metric.
Data set C-ELEGAN
CS PHD
CORA
AIRPORT
HCC
4.340.64
23.37=3.20
19.30
7.63+0.54
Gromov
3.32
13.24
9.23
4.04
TR
5.90=0.72
21.01#a.34
16.86-211
10.00
NJ
2.97
16.81
13.42
4.18
Table 3: f. error (i.e., max distortion)
4.1 Common data sets
We used common unweighted graph data sets which are known to he hyperbolic or close to tree-like and often used in graph neural nets, especially those with geometric considerations. The data sets we used are C-ELEGAN, CS PHD from (14). and CORA, AIRPORT from [5].. (For those which contain multiple components, chose the largest connected component.) Given unweighted graph, we computed its shortest-path distance matrix and used that input to obtain a tree metric. We compared these results with the following other tree fitting algorithms TREEREP (TR) (9), VEIGHBORJJOT (NJ) (8. and the classical Gromov algorithm. As TREEREP is a randomized algorithm and HCCROOTED
and Gromov's 's algorithm depends on the choice of a pivot vertex. we run all of these algorithms 100 times and report the average еπто with standard deviation. All edges with negative weights have been modified with weight O, TREEREP and NEIGHBORJOIN both occasionally produce edges with negative weights. Recall, both TREEREP and NEIGHBORJOIN enjoy no theoretical guarantees on distortion.
First, we examine the results Table 2 We note that although the guaranteed bound (of average distortion), ((==) AvgHyp(d) ( is asymptotically tight even in worst case analysis, this bound is quite loose in practice; most fitting algorithms perform much better than that. We also that the & error of HCCROOTED FIF is comparable to that of TREEREP, while NEIGHBOR.JOIN performs much better than those. It tends perform better when the graph data set known to be more hyperbolic (or tree-like), despite no theoretical guarantees. It is, however, quite slow.
Also, note from Table that Gromov's 's algorithm, which solves our / loo hyperbolicity problem tends to return better output in terms of lo error. the other hand, its result on é error is not as good as the other algorithms. In contrast, our HCCROOTED objective, which suggests that our approach to this problem is on target.
performs better the E
Data set
C-ELEGAN
CS PHD
CORA
AIRPORT
logn)
HCC
0.648+0.018
3.11420.020
18. a.0
28.821+0.88
O(s?)
Gromov
0.055+0.005
0.296+n.004
2.063+0.00s
3,25 0.251 +o.ass
TR
0.068 so.aco
0.223
0.610
0.764
06*)
NJ
0.336
4.659
268.45
804.67
Table 4: Running Time(s). For NJ, we implemented the naive algorithm, which is On²3). We note that TREEREP produces a tree and not set of distances; its running times excluded step which computes the distance matrix, which takes O(n?) time.

---

Initial Tree
[T 3)
BT 4)
BT(3, 5)
BT(22 8)
DISEASE
585
776
364
511
2665
0.01887
0.0187620.0075
0.001501n.0006
0.00098
0.000131a000
0.00443 cooes
0.01538
0.04153
0.07426=a 02027
0.00061 =0 00058
Gromov
0.18225-0.0om
0.44015
0.17085+0.0a9rt
0.16898=0.ooo
0.18977
TR
0.01360 -0
0.01103 +0.005s
0.06080+n.ms77
0.09550+0.aaat
0.0008
=0.00559
NJ
0.03180 c07o7
0.0609220.0188
0,043092n.00aa
0.04360 0054s
0.00601
=0 0028
Table 5: Average { сπтог when R2
500
In analyzing the running times in Table 4
we notice that HCCROOTED runs in truly (n n) time. Also, its dominant part the subroutine HCCTRIANGLE, which runs in (n?))
4.2 Synthetic data sets
In order to analyze the performance our algorithm a more thorough and rigorous fashion, we generate random synthetic distances with low hyperbolicity. More precisely, construct synthetic weighted graph from fixed balanced trees. We use (T h) to indicate a balanced tree with branching factor and height h and DISEASE from [6]. an unweighted tree data set. For each tree, add edges randomly, until we reach 500 additional edges. Each added edge is given a distance designed empirically to keep the 5-hyperbolicity bounded by value of 0.2.
Then we measured the & error of each tree fitting algorithm (and averaged over 50 trials). Note that all rooted tree fitting algorithms use root node (for balanced trees, we used the apex; for DISEASE, we used node 0).
For these experiments, we see quite different results in Table 5 All of these data sets are truly tree-like. Clearly, NEIGHBORJOIN performs considerably worse on these data than on the common data sets above, especially when the input comes from a tree with high branching factor (note that the branching factor of DISEASE is recorded as 6.224, which is also high). We also note that Gromov's method behaves much worse than all the other algorithms. This is possibly because Gromov's 's method known to produce a non-stretching tree fit, while it better idea to stretch the metrie in this case. The theoretical bound is still quite loose, but not as much as with the common data sets.
5 Discussion
All of our experiments show that it is critical to quantify how "tree-like" a data set in order to understand how well different tree fitting algorithms will perform that data set. In other words, we cannot simply assume that a data set is generic when fitting a tree to Furthermore, we develop both measure of how like data set is and an algorithm HCCROOTED'TREES leverages this behavior so as to minimize the appropriate distortion of this fit. The performance of DiCCROTEETRREFI and other standard tree fitting algorithms shows that commonly used data sets (especially in geometric graph neural nets) are quite far from tree-like and are not well-represented by trees, especially when compared with synthetic data sets. This suggests that we need considerably more refined geometric notions for learning tasks with these data sets.
that
10

---

References
[1] V. Cohen-Addad, D. Das, E. Kipouridis, N. Parotsidis, and M. Thorup, "Fitting distances by tree metrics minimizing the total error within constant factor," in 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), IEEE, 2022, pp. 468-479.
[2] N. Ailon and M. Charikar, "Fitting tree metrics: Hicrarchical clustering and phylogeny." in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS '05) IEEF, 2005,
pp. 73-82.
[3] M. Farach, S. Kannan, and Warnow, "A robust model for finding optimal evolutionary trees," Algorithmica, vol. 13, no. 1. pp. 155-179, 1995.
[4] M. Gromov, "Hyperbolic groups," in Essays in group theory, Springer, 1987, pp. 75-263.
[5] I.. L. Cavalli-Sforza and A. W. Edwards, "Phylogenetic analysis. models and estimation procedures." American journal of human genetics, vol. 19, no. 3 Pt 1, 233, 1967.
[6] I. Chami, Z. Ying, C. Ré, and J. Leskovec, "Hyperbolic graph convolutional neural networks," Advances neural information processing systems, vol. 32, 2019.
[7] R. Agarwala, V. Bafna, M. Farach, M. Paterson, and M. Thorup, "On the approximability of numerical taxonomy (fitting distances by tree metrics)," SIAM Journal on Computing, vol. 28, no. 3. pp. 1073-1085, 1998.
[8] N. Saitou and M. Nei. "The neighbor-joining method: A new method for reconstructing phylogenetic trees.," " Molecular biology and evolution, vol. 4, no. 4, pp. 406-425, 1987.
[9] R. Sonthalia and A. C. Gilbert, "Tree! i am no tree! am a low dimensional hyperbolic embedding," arXiv preprint 2005.0000 2020.
[10] S. Chatterjee and L.. Sloman, "Average gromov hyperbolicity and the parisi ansatz," Advances in Mathematics, vol. 376, p. 107 417, 2021.
[11] É. Ghys and P. De La Harpe, "Espaces métriques hyperboliques." in Sur les groupes hyper- boliques d' après Mikhael Gromov, Springer, 1990, pp. 27-45.
[12] B. Harb, S. Kannan, and A. McGregor, "Approximating the best-fit tree under norms," in Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques: 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computa- tion, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005. Proceedings, Springer, 2005, pp. 123-133.
[13] S. Chowdhury, F. Mémoli, and Z. T. Smith, "Improved error bounds for tree representations of metric spaces," " Advances in Neural Information Processing Systems, vol. 29, 2016.
[14] R. Rossi and N. K. Ahmed, "The network data repository with interactive graph analytics and visualization," "" in AAAI, 2015. [Online]. Available: htat::s://netwwrrrppossos
com
[15] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective classifi- cation in network data," Al magazine, vol. 29, no. 3. pp. 93-93, 2008.
[16] W. H. Day. "Computational complexity of inferring phylogenies from dissimilarity matrices," Bulletin of mathematical biology, vol. 49, no. pp. 461-467, 1987.
[17] B. H. Bowditch, A course on geometric group theory.." " 2006.
[18] H. Samet, "The quadtree and related hierarchical data structures," ACM Computing Surveys (CSUR), vol. 16, 2. pp. 187-260, 1984.
[19] M. Elkin, Y. Emek, D. A. Spielman, and S.-H. Teng, "Lower-stretch spanning trees," SIAM Journal on Computing, vol. 38, no. 2, pp. 608-628 2008.
[20] N. Ailon, M. Charikar, and A. Newman, "Aggregating inconsistent information: Ranking and clustering," Journal of the ACM (JACM), vol. 55, no. 5, pp. 1-27, 2008
[21] V. Chepoi, F. Dragan, B. Estellon, M. Habib, and Y. Vaxès, "Diameters, centers, and ap- proximating trees of delta-hyperbolieecodesii spaces and graphs," in Proceedings of the twenty-fourth annual symposium on Computational geometry, 2008, pp. 59-68.
[22] W. Chen, W. Fang, G. Hu, and M. W. Mahoney, "On the hyperbolicity of small-world and treelike random graphs," Internet Mathematics, vol. 9, no. 4, pp. 434-491, 2013.
[23] D. Coudert, A. Nusser, and L. Viennot, "Computing graph hyperbolicity using dominating *ets*" in 2022 Proceedings of the Symposium Algorithm Engineering and Experiments (ALENEX), SIAM, 2022, pp. 78-90.

---

[24] R. Sarkar, "Low distortion delaunay embedding of trees in hyperbolic plane," in International Symposium on Graph Drawing, Springer, 2011, pp- 355-366.
[25] F. Sala, C. De Sa, A. Gu, and C. Ré, "Representation tradeoffs for hyperbolic embeddings." in International conference on machine learning. PMLR, 2018, pp.
[26] I. Chami, A. Gu, V. Chatziafratis, and C. Ré, "From trees to continuous embeddings and back: Hyperbolic hierarchical clustering," Advances in Neural Information Processing Systems, vol. 33, Pp. 15 065-15 076, 2020.
[27] N. Monath, M. Zaheer, D. Silva, A. McCallum, and A. Ahmed, "Gradient-based hierarchical clustering using continuous representations of trees in hyperbolic space," in Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 714-722.
[28] M. Nickel and D. Kiela, "Poincaré embeddings for learning hierarchical representations." Advances in neural information processing systems, vol. 30, 2017.
[29] N. Linial, London, and Y. Rabinovich, "The geometry of graphs and some of its algorithmic applications," " Combinatorica, vol. 15, no. 2, pp. 215-245, 1995.
[30] M. Nickel and D. Kiela, "LLearning continuous hierarchies in the lorentz model of hyperbolic geometry," International Conference on Machine Learning, PMIR, 2018, pp. 3779-3788. [31] H. Fournier, A. Ismail, and A. Vigneron, "Computing the gromov hyperbolicity of a discrete metric space," Information Processing Letters, vol. 115, no. 6-8, pp. 576-579, 2015.
[32] P. K. Agarwal, K. Fox, Nath, A. Sidiropoulos, and Wang. "Computing the gromov- hausdorff distance for metric trees," ACM Transactions on Algorithms (TALG), vol. 14, no. 2,
pp. 1-20, 2018
[33] B. Nica and J. Spakula, "Strong hyperbolicity," Groups, Geometry, and Dynamics, vol. 10,
no. 3. pp. 951-964, 2016.
[34] T. Das, D. Simmons, and M. Urbański, Geometry and dynamics in Gromov hyperbolic metric spaces. American Mathematical Soc., 2017, vol. 218.
[35] I. Abraham, M. Balakrishnan, Kuhn, D. Malkhi, V. Ramasubramanian, and K. Talwar, "Reconstructing approximate tree metrics," in Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, 2007, pp. 43 43.52.
12

---

6 Appendix
6.1 Proof of Theorem 2.5
We will follow the details from (and T to address minor issues). This is, in fact, the generic reduction method from ultrametric fitting.
Algorithm 5 Find a tree fitting given an ultrametric fitting procedure
1: procedure ULTRAFIT
2: Input: distance function d
3: Output: ultrametric dy which fits d
4: procedure ROOTEDTREEFIT
5: Input: distance function d on (²) and base point X
6: Output: (rooted) tree metrie dr which fits d and d(w, x)) dr(w for all X
7:
Define m = max.ex d(w,,)) x), (w y) = 2m d(w, x) d(w, v), and Br = 2(m
d(w,x))( E X)
8:
du ULTRAFIT(d c.c))
9:
Restrict dr v) min(max((B,, By, duy (2,, w)) 2m)
10: dr dy Cw
return dr
For any I, U E X, (dg - (d + (w) v) & (x. - (d + Gw) v) holds. In other words, the restriction will reduce the error.
Claim:
Proof: It is enough to check the two cases when dy differs.
Case I: max(32, By) (x, > (x,(x))): without loss of generality, we assume that di (x, 3z By. We have (d + cw ) y) d(x, y) + cw (x, v) > (d(w, v) d(w, x)) (2m- (il-dd(waa -ddw(w, y)) = 2m 2on-22((u)
2d( x)) = 3n, which shows (d+ (w+ (r, 2
du (x,3) 3) > drr (v. v). Therefore the claim holds.
Case 2: 2m dy (z. y) < (2, v): since (d + (x) = 2m - (x, v) S 2m, have
(d cw (2x y) s dy (z. y) do y). Again, the claim holds.
This completes the proof.
Claim: The restriction dy is also an ultrametric.
We need to prove (z, y) I max(de (z, z), du ()) for all 0, E X. As U' is ultrametric by assumption, is enough to check only if
Proof:
dy (2. > der (z. y) max(de 2), du (y. 2)) max(d (2, de (g, 2)) holds.
Case 1: du (z, y) > du (z, y): we have max(3 (3., By) dy (z, v) du (2,z). Without loss of generality, we assume that dy (z, y) = Br 2 By. Then we have du (z, 2) 2 max(3e, 3x) 2
3. (x, y), which shows do (I, max(du (Ic 2) (v.2)). 2)).
Case 2: max(dy (xr, 2), du (y, 2)) max(de (ar, 2), der (v. 2)): we have du (x, 2) dur 2) dy (y, 2) < de (y. 2) holds. In either case, we have the value is clipped by the maximum value 2m so that dy (x, v) max(du (x, z), de =)) 2m.
Therefore, we conclude that the stronger triangle inequality still holds, which completes the proof.
Claim: By the restriction, dr satisfies tree metric.
Proof: First, we need to verify that dr is metric. First, we have
dr dr y) = dr 4) - C.n (2, v) 2 max(3n, 3g)) - Co, 4) = max(32, Byy (Bp Br + 3yy)
2
1,3, - Byy
2 = |d(w, x) d(w, y) 2 0,

---

that dr is non-negative. Next, will prove the triangle inequality: dr(x; S (x, 23. Without loss of generality, we assume that (x, y) 2 du (v. z). Then we have
dr(x,2) 2) = (x( z) Car (2, =) & (x, dv =)) - cw
dy(a, v) (w,( y) + C. (2,
dr(x,y) + (d(we,2) z) d(w,y))
dr( y) + (d(w, d(w, v) S dr v) + dr (y, z).
Therefore, dr is (non-negative) metric. To show it is metrie, examine the four point condition of dr- For any z, y, E X,
dr( v) + dr(2,() = (du v) - (o( y)) + (dv(221) - Ca (2, 1))
(d y) + (z,)))) (cn( + Car(z, (z,
= (2, v) + du (2,t)) -4m - d(w, x) - d( y) d(w, 2) - d(w. t)),
so that any pair sum of dr differs from dy by 4m - d(wr x)) d(w, y) - d(w, =) - d(wc 1). As dy is ultrametric and thus O-hyperbolic, dr is also O-hyperbolic, desired. Thus, dr is tree metric.
Finally, we prove that lp error of dr is bounded as desired. This can be done by
||d - drllp = [I(d c..) (dr + llp = lldr (d + Cun clr
S |ldb (d + ew)ll S AvgUM, (d+uMM((+cci +ww) f(n),
by assumption. For 1 S < oo, we have
Σ (AvgUM, cw))
Σ
1p(d+ Cwjs,
71
WEX
WEX
2.N.
(((N))
n1
29 29 y, 2)
n
WEX
29
3
Σ
fp 2,,d;,,,,,,0
29 n
(AvgHyyp(d))) (d)).
Therefore, there exists E X so that AvgUM, c..) 2 ( 1/4 AvgHyp, The q = case can be separately checked.
Hence, there exists E X where such reduction yields tree fitting with lp error bounded by
2 (m=3) 1/4 AvgHyp,,dd) f(n), desired.
Note that when we use HCCULTRAFIT, then max(32, B,) s der (z, y) S 2m always hold so that the clipping is not necessary.
6.2 Proof of Theorem 2.6
Our reduction is based on the technique from [16] construct distance d' Z XUY such that X
and Section 9 of (T.. Given d on X, we will
[Y] and
d(2, w) M
if 2, X
d' d'(z, w)
if X,w Y or e for all + Z,
if w Y
for M large enough and e small enough. Then first we have
Claim: I S q < then AvgHyp,(d") ( + 25- 1/8 AvgUM,(d). For we have
Hyp(d') 2 (MM()..

---

Proof: It can be checked that if at least of 2; 2, is from Y, then immediately have fp(d';;; I, Us 2, w) = O. Therefore, we get
Σ
fp(d': 2,
Σ
Σ
Σ
fp(d";
(.
WEY 2.21PE (3)
E
Σ
tp(d; 2dd; z)
a.M.Z,WE( (1)
T. (5)
(") 1
(d) + mm(r))
Ad)
To bound Avgllypg. we will use the fact that
fp(d; w) - [tp(d; tp(d; t, w) tp(d: y, 2, w)]
Therefore,
(dg
1
Σ
fp(d; 2,)
w.N.A.EE (*)
29-2
tp(d: add;v.14. 2, + w. + (,dd;,,,,w)) +
29-2
(n ()=3))p(d;,
29
Σ
2,(d; = 29 AvgUM,(d).
2.8.2E(2))
2.9.
To sum up, we get
Avgllyp,(d'
1
Σ
2,
2n
2. (3)
n(3)
AvgHyp, (d)" +
AvgUM,(d))
2n
2m
1
Avgldyp,(d (d) + AvgUM,
16
4
24
(1 + 20--)) AvgHyp,(d).
Adg
Adg
16
The y case can be checked separately.
Therefore, by the claim above and the assumption, we have a tree fitting dr which fits d' with |dd - d') Ipp < Avgllyp, ((2m). Our goal is to construct a reduction to deduce an ultrametric fit du on X, by utilizing dr. First,
Claim: M and e were large and small enough respectively, then dr v) + dx v) (2), 2 2c holds for every 21, 22 E X and y Y.
Proof: Suppose the claim fails. As d(x11 y) + d(x2, y) d(ri, = M + d(z), x2). suggests that one of three pair distances should have distortion at least 3 (2M - 2c- d(x1, This should not happen if M - c > AvgHyyp,(d") f22n).
We will interpret the above claim as a structural property. Given tree T'' which realizes the tree metric dr, one can find a Steiner node w on T1, 22, y. Then we have dr(w,y) y) = (x1 y) + dy (12, v) dy (2(11, x22) 2 Since it holds for any 21, 22 E X, it suggests that every geodesic segment [æ. y] for fixed E Y should share their paths at least c. This observation allows a following uniformization Y.
Claim: One can refine tree metric so that dr v2) for all yı y22 E Y with &p error non- increasing.
3

---

Algorithm 6 Refine a tree fit on Z = XUY
procedure UNIFORMIZATION ON Y
2: Input: tree fit (T,dr) on
X
Output: refined tree (T', ,dr)) on Z
4: (1r(21, F2) + dr (21, F2) Vx1 # 22 E X
(y V2) c Ayι F 82 EY
6: Find yo argmin Lxex |d(a,, y) MP
(x, y) < dr(x, yo)
da E Y.yYY EY
8: return dr
Pick argmingey ΣzEx |dr (z, y) - d(z,,) y)1". Then we will keep X U {yo} with its tree structure and relocate all other y & yo Y. As every geodesic segments will share their paths at least we will pick point with dr( 2) = c/22 on the segment, and draw edge (z, y) for all y E Y with length c/2. Then dr y2) = as desired. Furthermore, as dr (z. y) dr (2. yo) for any E X and Y.
Proof:
ld
d|B
Σ
ldr w) d(2,w))
(.)
Σ
(dr x¹) - x(x,x'))
Σ MEXWNY
[dr((z,)) - -MP+ Σ
(v. cP.
DE
s Σ
Idr(x, x²) -dxxxx ((x,x))1
Σ
|dr(2, yo) MP
Σ 0
a.))((3)
.EXWEY
E.D'((")
Σ
(dT(x,, x²) - 2(x,x')1
Σ
Σ
(x, vo) MP
VEY FE
S Σ
(dr(x, d(xx,'))
Σ
Σ
(d. v) MP S | dlp
VEY #EX
as desired.
Algorithm 7 Construction of restricted tree with respect to given root r
procedure RESTRICTTREE
2: Input: Tree fitting (T, on Z
Output: Tree fitting dr such that dy (x. v) = M for all x E X and Y
4: for each æ E X:
if dr(x,, Mo) > M:
Relocate x to point on geodesic [z, yol so that dz yo) M else if d1, yu) M: 8: Add edge (x, with length M dr yo) and relocate x to return (T, dT)
6:
One can refine a tree metric so that dr, y) = M for all x E X and y E with lp error not greater than 3(p-1)/p times the original error. Furthermore, we restrict dy on X, then an ultrametric.
Claim:
We will use the algorithm RESTRICTTREE to obtain the restricted tree as described. that such procedure will successfully return tree metric dr with dr (I. y) = M for all x E X and y E Y. Furthermore, as Denote e == dr d. Then for any pair 21, 22 X, distortion does not increase greater than (e(z1, (e)) + |e(x2, vo)l, which is the amount of relocation. We can utilize this
Proof:
clear

---

dr(a, va) > M
dr(2', vo) < M
Figure 2: This figure depicts how RESTRICTTREE works. The idea is we can relocate every vertices
so that d(x, wo) dr yo) holds for every x X.
fact by
||dr
ddb
Σ
(d w) - d(z, w)l
2.wE(3)
Σ
(x,,') d(x,21))
Σ =EX.
(dr((,)) - MP+ Σ
(d. - cp
z,x' 2,))
Σ
(x, -(xx
2x)
< Σ
(1e(2, + (e(x, 2')1 + |e(z'.80)))
<30-1
Σ
+c(2, + |c(2', vo)
-30-1
le(x, 2(), (n-1) Σ
le(x, y0)l
zex
<3p-1
Σ
|e(x, x)) + n
Σ
= =30-11/dr d|p le(x, 30)l
(
xeX
as desired. Then by the restriction, dr (x. yo) M holds for all x E X. Therefore, tp(dr;; Fı, F1, x2) xz) = f drr; 21, 02, T3, yo)
holds for all 21, T3 which shows that dr X is an ultrametric.
Denote the restricted metric de (on (²))) )). Then we have
Ildy dlpp || d'Ipp - 3 = |rr - d'Ilp - 33 v1 l| - d''pp
33 p=1 ( + (+ AvgUM, (d) f(2n),
1/9
as desired.
6.3 Self-contained proof of ultrametric fit to rooted tree fit
Choose any base point w e X and run HCCROOTEDTRESFIT. Note that + cw = 2(M -gpw). Then by 3.4 we see that the output dy satisfies
||d - drll1 < Al|A cw)ll 8 A gpw) (l)
5

---

Although (d)(1) itself does not satisfy the guaranteed bound, know that
Σ ll
E Σ
PP (d; v,,
wEX a.
(1))
2, (() AvglHyp(d)
4
N.M.P.MEE
so there exists an output dr (with appropriately chosen w) with its & error bounded by 8 1 (a) AvgHlyp(d) 8( 8("=)) AvgHyp((d). As we need to check every base point w E X, this
procedure runs in time nog
6.4 Proof of Theorem 33
We begin by recalling the definition highly connectedness.
Definition 6.1. Given graph = (V, E) and two disjoint vertex sets X and Y, the pair (X, Y) is said to be highly connected if both
Y
for all x E X, (V E (Z) RJ
2
and
2
X
for all E H E x)
E E} 2
2
hold.
Our first lemma shows that every clusters should contain reasonably many edges "within", so that the number of "false positive" edges can be bounded. Because highly connectedness determines whether at least half of the edges have been connected, we can expect that the degree of every node should be least half of the size clusters.
Lemma 6.2. For any C P. with |C| > 2 and C, H( C1(,, F.J
I
Proof. We use induction on The lemma obviously true when 0. Next, suppose we pick C' E Pt with |C] 2 2 and the cluster C' is formed at step to S I. If to < f,, since P. is increasing, it is clear that
|C| 2
Ha E C((x, E. 1a E C((x,²)) E E
for all x E C.
Therefore, it is enough to check when to I,, i.e., C' is the newly added cluster at step L.
Suppose C is achieved by merging C C. U Cb. We then have two cases check, depending on the sizes of C2 and Co.
Case 1:
1 or |C&l = 1: Without loss of generality, assume that |Cal = and let C. {a}. C also a singleton, then there is nothing to prove. If not, then, must have (a, y) E E, for all E C₁ in order to be highly connected. And by the induction hypothesis,
Cal= -
Cob 2
lt E CallAn') E E.J 2 Hal E Colliny)) E Em
for all E Ca.
Hence, we have
|C|
11 E E 10
2
and for all y E C2
CCb
C
Hy's E Cl(.v)) E,Hl Hy' e C.((.v)) E EHH+1> which completes the proof of Case 1.
+ >
2

---

As version of the HCC problem bounds the number of edges in disagreement in terms of the bad triangles, with the next lemmas, we count the number of bad triangles [B(G)) and bound the number of edges in disagreement. Recall that bad triangle is defined as triplet of edges in which only two Case 2: Cal
and [Ch] 1: By the induction hypothesis, have
Ca 2
|a E C. (z, x') E E,H 2 1[ E (Cll(,,x') E E 2
for all x E Cas
and similarly for Co. As C. and C. both highly connected, we have
Ho E Col(z,)) E EiH
for all x E Ca.
2
Cal
Ke' E Col(y,, E E:Hl 2
for all y E Ca-
2
Therefore, for any x E Ca. |= E CI((x))) E.ll
1/22 E Col(E, x') E E.J++ HW E C,l(a,))) E E.H
Cal
C. CCI
2
2 2
while each inequality comes from the induction hypothesis and the connectivity condition. We can similarly show the property for any y E C., which completes the proof of Case 2.
This completes the proof.
Next, we prove the following isoperimetric property: Lemma 6.3. For C' Pt denote ax == {(x,0) E Esjx X. for X C C. Then for any proper X,
|0x| 2 |||
Then for any x E X, by 6.2 there are least CC 2 ||x + edges which connects æ and other vertices in X. Therefore, we have
Proof. Without loss of generality, assume that 1 <
|
<
[Cl
Cl
|ax N |
| +1+1
2
of the three possible edges belong to E,, For each cluster C E Pt, denote the number of bad triangles inside C Tc. And for each cluster pair C, C' E Pr, count some of the bad triangles between C and C" as To.c, More precisely,
Definition 6.4. Given partition Pt. denote
Te = [1x y, 2), v, E C and (x, E B(G.)) for C'
Tic.y (1x, x' ,), C.yec C and (z, x'), (z.v) E E,, (z' v) & Ed}
Pt
U((,,../) C.D.V e C' and (v. (1,1) E E., (x.11) & F.). for (C,C')
Note that To,c" does not count every bad triangle between C and C², there might be bad triangles in which the missing edge is inside the cluster. With these definitions, we have
Σ
Tol
Σ
ITcc,y < [B(G.))
CEP.
(C)
Proposition 6.5. For any cluster
Pt, the number of edges not in C' is bounded by [Tel. That is.
1((x.)) v) & E/a, E CCH [Tcl-
(In fact, it is bounded by (Tc)

---

Proof. We will prove that for any (2r E2 with x. C, there exist at least elements
in To that contain e, which implies our result. |C] = 1, then there is nothing to prove. For any
|C| 2 2 and (z, y) & E,, by Lemma 6.2 there are at least [Cl neighbors of and y (we will denote each as N₂ and Ny. respectively). Since Na, Ny C CC fæ, y). we have
C
N N + 1 IN U
(1C) 2
For any N₂ Ng, (z, To by definition, which proves the assertion.
Lemma 6.6. For G E) and two disjoint subsets X, Y C V, suppose
|X|
Y
(x' E (') E E)
2
2 for all x E and Kv E (l E EH
for all E Y.
We will further assume that X and Y are not highly connected. Then we have
H(x,)) E E| X, r 4- (1((z,')))) E xxyy E Y and (z, (z,,)) E (, .v) $ E}
+ [(((,,,,))) X.u. E Y and (.,'), E E, (z, & E))
Proof. The key argument here is to use Lemma 6.3 and count the boundary sets. Define Ny {y E (I, y) E E3} for E X (and Nx (y) for E Y respectively.) Then for any (y, y') E (x), (x, vy, v.y')) a bad triangle and contributes the right hand side. In other words, the right hand side of the above equation is upper bounded by
Σ [ONy(z)1+ + Σ (1Nx(W01) DEY
(+) 4
By6.3 6.3 we know that for Ny + or (NN M We will count such x E X and y E Y which neighbor set is proper, in order make lower bound. We divide the rest of the analysis into three cases:
Case 1:
There exists zo E X such that Ny = 0: then for any E Y, zo & Nx Nx(y) so that (y) cannot be X. Thus, (x 0 immediately leads that JaNx (y) > 2
[X] We have
H(x,0) E E|r e H1
YINx (V) # 0}
<
Σ
[
D yEY,Nx
(
< 2
Σ
[Nx(2))
y NEY,Nx(u)>
< (+) < RHS,
which proves the lemma.
Case 2: There exists Yo Y such that Nx (vo) = 0: this case is proven as we did in Case 1.
Case 3: For any x E X and y E Y, (2) * and (v) * 0 we will use the assumption that X and Y are not highly connected. With this assumption, can also assume without loss of generality that there an Fi E such that Ny (αp) < 2- Wx(y) 0 and Nx (v) * X (as zo Nx(y)) Thus, the boundary set exists and has at
[Y] Then for any y g Ny (aro),

---

least 2
[X]
elements. Therefore,
RHS Z Σ
2+)
xaNx (y)
yEY
Σ
1aN (v)
yc yЕ UEY (zo)
X
24
Σ
yE VEY,vEN (zo)
X|
4
((Y)
(2o))
X|
Y
4
--XI- LHS.
2
This completes the proof.
Proposition 6.7. For any cluster pair (C, E Ps, the number of edges between and C" is bounded by 4[Tic,e)) (i.e., ((x,)) y) E Elæ E C, E C"ll s 4(T(c,,)))
Proof. Here, we will use an induction on t. When t 0, then there is nothing to prove. Suppose the induction hypothesis holds for < t.
Case 1: does not connect two vertices between C' and C" and C, C" are not added at step t: then by induction hypothesis, the proposition holds at step which is also at step (As the left hand side is invariant and (T(c,o") is increasing).
Case 2: et (ar, v) for C and y E C²: then it follows that algorithm decided not merge two clusters, which means C' and C" are not highly connected. Then by Lemma 6.6 the number of edges is bounded by ((T() as desired.
Case 3: 6 does not connect two vertices between C and C', but C' or C' is newly formed at step t: note that both clusters cannot be generated at the same time, assume without loss of generality that C' is the new cluster and assume is generated by C = Ca Cb- Then by the induction hypothesis, we have
{(.,v) E E|r C,y C'Hl
((,,y) E Elx Ca.yE C'Jl ((x, E E C.,y C'Hl I 44[Tic..o]+ + (by the induction hypothesis)
< Tic.ol
This completes the proof.
We are now ready prove Theorem 3.3
Proof Theorem 3.3 For Pt (C1, C2, .. ,C&), denote
e; : 1((x, $ Ela, Ci)),
6. : (((,,)) E E|x C.ye C,Hl
Then by the above propositions, we have
[EAE(())) Ea+ Σ
cij
icj
$ Σ To, + 4T(c.o))
<4 ETe, Tc, + > Tccooo <4-1B(G,)).
K

---

6.5 Implementation details
To detail our implementation, we will introduce the following variables.
For x X and cluster C, denote D(x,C) = (y E (l E B.). We further denote the connectivity condition (x, C*) as (F( () ) Also for given two clusters Ca and Cg. we will denote M(C,. Cb) = π E (a, Cb) = 1H-- We can easily check that two disjoint clusters C. and C. are highly connected if and only
M M(a, Ci) M(C,, C.) |Cal + |Cal.
Algorithm 8 HCCTRIANGLE: Actual Implementation
function HCCTRIANGLE
Input: X= {x1, " Inn.
{er}
Initialize D, H, .M as 0 for vertex X
Initialize p = [(r1] {x2). ... {
For E (1, (2)
Take 6, = (x, y) with a E C. and y E Cb (Ca, Co EP)
Add (iz, Cb), Dly, C.) by
Update (x, C₂) and Hy, If H has been updated, update MiC,; Cb) and M(C,, Ca) accordingly
If Ca + Co and (C Cb) M(C Ca) = C |C/|:
Remove Ca, Cs and add Cnew == Co U. in
D(: Cnew)) < D(;, C.) + D(: Gb) Compute H(:, Cnew) and M(: Cnew) (by using D(: Cnew))
M(Cnew::)) +- M(Ca,:) + M(C..:)
Pt P return [P]}
One observe that iteration only takes O(1) when C2 and C. not merged. When merge Cnems we need time (n) to compute new information of Cnew- Since such events occur exactly 1 times, we can conclude that HCCTRIANGLE overall runs in time O(n²).
6.6 Asymptotic tightness of Gromov's distortion bound
While it well-known that Gromov's result is asymptotically tight, we give self-contained sketch of the proof and provide an example that witnesses the bound. We detail the construction given by [17). Consider the Poincaré disk H2 and its hyperbolic n 4m-gon H,r as a set of equally spaced n points around the circle of radius r in H22 Label all the points as Ø T2,,.... , Fimm in the counterclockwise order, and define = Z3m Suppose dr is tree metric fit to d and denote the Gromov product with respect to y as gpy. Then
JPy 22m) 2 min(gp, x1) gy (x1, F2m))
min(gr x1), min( (2)) 9p (22, 22m))
Al
min
gPy 2141)
10
Therefore there exists an such that
dr(2; u) + dr (2:41111)) 8) dr x1+1) S (20, 4) + dr v) - dr (2o, x2m). On the other hand, for r, n large enough,
[d(a,, y)+ +d y) (.o.))d(,,)) d(x,, x1+1)) [ddro y) +d( 4) d(rro x2m)) R 2 shows one of six pair distances should have distortion least 1/3 log O(logn).
ss 2 2log
6.7 Examples
6.7.1
Example for HCCULTRAFIT
For the following distances on X = {a, b, c, d, e, f}, we will compute the ultrametric fit using HCC. We first sort all the pairs in increasing distance order. We merge {a} and (b) first; this edge
10

---

mm2m
H12
Figure 3: This figure depicts the example that proves Gromov's distortion bound is asymptotically tight. By symmetry. we can conclude that Gromov's algorithm will always return the same foe error regardless of the choice of base point
corresponds e1 = (a, Then we merge {d} and {e} for 62 (d, e). Next, when we explore (e, f) (regardless of whether (a, d) comes first not), merge {d, e} and {f] with corresponding distance 6. Then we merge {a, b} and {e} when we explore (b, c). Finally, we merge {a, b, cf and {d, f) when both clusters are highly connected, and we check its corresponding fit is 8
d
b
d
dy
b
d
a
3
5
a
3
8
8
b
3
0
7
8
7
10
b
3
0
7
8
8
c
7
0
9
5
+
c
7
8
8
d
6
8
9
0
4
d
8
0
4
6
e
7
5
e
8
4
6
f
10
7
5
8
6
0
Figure 4: This figure depicts the example output de by drawing dendrogram.
6.7.2 Example for HCCROOTED
Next, given d, we want to find tree fitting dy which restricts E X. We first compute c, and run HCCULTRAFIt on d + cy, denote the output dg. Then our tree fit dr is obtained by dr == dy Cr. which is tree metric. Furthermore, it restricts X, that dr (z, r) d(x,r) for all x E X.
d
b
d
f
a
b
d
r
9
10
8
7
r
11
11
12
10
12
13
9
0
1
2
5
5
4
11
0
2
3
1
3
4
b
0
7
4
6
b
11
2
0
3
1
3
2
4
0
7
1
2
C
12
3
3
0
2
4
5
d
10
7
0
2
2
d
10
1
1
2
0
2
3
4
2
0
1
12
3
3
4
2
0
5
f
7
4
6
2
2
1
0
f
13
4
4
5
3
5
0
11

---

d +
CT
d
f
du
d
0
20
20
20
20
20
20
r
20
20
20
20
20
20
20
8
8
a
20
8
8
20
3
7
8
7
10
b
20
7
8
8
8
20
20
8
8
d
20
8
0
4
5
d
20
8
0
4
6
20
e
f
20
8
10
7
6
0
f
20
8
6
6
0
r
b
e
0
10
8
a
9
1
5
9
0
4
5
dp
8
4
4
6
4
10
7
2
8
5
5
4
2
0
f
7
1
0.5
Figure 5: This figure depicts how the output dr looks like. This tree structure fact can easily be obtained by utilizing the structure of dendrogram computed.
6.8 Rooted tree structure
We discuss how the tree structure of dr, the output of HCCROOTEDTREEFIT, is related to that of dy. As fitting dy is an agglomerative clustering procedure. one may consider its linkage matrix with specified format in seipy library (See http://dos..cciy...oo
wtwperraeedscccyycccssseeeeeeeee www.sste...irrrccyyliii www.ae...iinnae..h.. htmml... At each wwtp:///w//soyy/efeeeee///eeeere
step, we utilize the data to construct desired rooted tree by adding Steiner node. Detailed algorithm is follows (For the simplicity, will describe the procedure when X [n] {0, 1, .n 1}).
6.9 Experiment details
6.9.1 TREEREP
We adapted code from TREEREP, which is available removed its dependency upon PyTorch and used the numpy library for two reasons. First, we have found that using the PyTorch library makes the implementation unnecessarily slower (especially for small input). Second, to achieve fair comparison, we fixed the randomized seed using numpy. All edges with negative weight have been set 0 after have outputted the tree.
http:/hhwwh...oooooo/a//erreeeer We
6.9.2 GROMOY
We used the duality of Gromov's algorithm and SLHC (observed by (13) and simply used reduction method (from ultrametric fitting to rooted tree fitting). scipy library was used to run SLHC. This procedure only takes ( time to compute.
12

---

Algorithm 9 Construct rooted tree from linkage matrix
1: procedure ULTRALINKAGEFIT
2: Input: distance function d
3: Output: linkage matrix Z which depicts ultrametric fit de
4: procedure CONSTRUCTROOTEDDREE
5: Input: distance function d on ((2) and base point S r
6: Output: Rooted tree (T, dr) which fits d and d(r, x) dr(r, x) for all 0 و n-1
7:
Define m = maNge=sn-1 d(r,z), (x(2,)) = 2m d(r,x) d(r,y), and 3g = 2(m
d(r, (0), < x
8:
Define (x) <- d(r,x) for 0 & w S n- c,)
9:
Z ULTRALINKAGFFTI(
10:
Fort 1.... 2):
11:
I, F.y. d f 0), [t, 11, t 2|
12:
Add node + in with d, m
d/2
13:
Add edge (x, +1) in T with weight (x)
d, (n +
14:
Add edge (y. n in T with weight (v) (n +t)
15:
(Collapse node 2n and the root node r)
16:
return (T,dr)
6.9.3
NEIGHBORJOIN
For NEIGHBORJOIN, we implemented simple code. Note that does not contain any heuristics on faster implementation. All edges with negative weight have been set to O after have outputted the tree.
6.9.4 Hardware setup
All experiments have used shared-use computing resource. There are CPU cores each with SGiB memory. We executed all the code using a Jupyter notebook interface running Python 3.11.0 with numpy 1.24.2, scipy 1.10.0, and networkx 3.0. The operating system we used Red Hat Enterprise Linux Server 7.9.
6.9.5 Common data set
For C-ELEGAN and CS PHD, we used pre-computed distance matrix from http://github.oom/ssnntaaa
For CORA, AIRPORT, and DISEASE, used https://github.com com/ Hazy Research/hgen and computed the shortest-path distance matrix of its largest connected component. The supplementary material includes the data input that utilized.
6.9.6 Synthetic data set
To produce random synthetic tree-like hyperbolic metric from given tree, we do the following.
1. Pick two random vertices v, w with (v, w) > 2 (If not, then run again.)
2. Add edge (v, w) with weight ( w) - (for 8 = 0.1).
3. We repeat until new n. = 500 edges have been added.
4. We compute shortest-path metric of the outputted sparse graph.
We excluded pair with dv,v, w) < 2 because: if it is 1, then the procedure simply shrinks the edge. if it is 2, then one can consider the procedure as just adding an Steiner node (of v, w and their common neighbor), which does not pose hyperbolicity.
6.9.7 Comparison
For the comparison, we have fixed the randomized seed using numpy library (from 0 to Rsseed 1). For common data set experiments, we run Rsseed 100 times. For synthetic data set experiments, we Rseed 50 times.
13

---

Error
Average & error
Max Loo error
HCC
0.26020.0ss 25.
1..78
Gromov
0.255 10.041
1.071
TR
0.282.1..00 087
10.48
NJ
0.224
1,430
QT
1.123
1.943
Table Experiments on unit cube in I2a The data set does not have some hyperbolicity feature so that the result kind may be different from the main experiments.
6.10 Detailed Comparisons
In comparison with [1] As presented an O(1) approximation that minimizes the & error, can be deduced that the total error of its output is also bounded by O(AvgHyp(d)n") while the leading coefficient is not known. It would be interesting to analyze the performance of LP based algorithms including [ if we have some tree-like assumptions on input, such as AvgHyp(d) or the
o-hyperbolicity.
In comparison with [10] We bounded the total error of the tree metric in terms of the average hyperbolicity AvgHyp(d) and the size of our input space X. As the growth function we found is O(n"), it can be seen that the average error bound would be O(AvgHyp(d) X|), which is asymptotically tight (In other words, the dependency on X is necessary).
While the setup 10) used is quite different, the result can be interpreted as follows: they bounded the expectation of the distortion in terms of the average hyperbolicity AvgHyp and the maximum bound on the Gromov product (or the diameter D). The specific growth function in terms of AvgHyp and b is not known, is hard track. By slightly tweaking our asymptotic tightness example, can also be seen that the dependency on b should be necessary. It would also be interesting to find how tight the dependency in terms of b is.
In comparison with QUADTREE There are a number tree fitting algorithms in many applications, with various kinds of inputs and outputs. One notable method is QUADTREE (referred in, for example, (18) which outputs a tree structure where each node reperesents rectangular area of the domain. There major differences between QUADTREE and ours: first, QUADTREE needs to input data points (Euclidean), while ours only requires a distance matrix. Also, the main output of QUADTREE an utilized tree data structure, while ours (and other comparisons) focus on fitting the metric.
We conducted a simple experiment on comparing QUADTREE and others including ours. First, we uniformly sampled 500 points in [0, 1)2 C IR² and ran QUADTREE algorithm as baseline algorithm. While defining edge weights on the output of QUADTREE is not clear, we used 2- for depth d edges. Note that the input we sampled is nowhere hyperbolic so that may not enjoy the advantages of fitting algorithms which use such geometric assumptions.
There is simple reason why QUADTREE behaves worse when it comes to the metric fitting problem. QUADTREE may distinguish two very close points across borders. Then its fitting distance between such points is very large; it in fact can be the diameter of the output tree, which is nearly in this experiment. That kind of pairs pose a huge error.
14


Reviews:
[{"review_id": "3qXb0Hncup", "reviewer": "Reviewer_Fg5u", "summary": "This paper introduces a novel tree fitting algorithm named HCCRootedTreeFit. First, the authors motivate the need for a better tree fitting algorithm by stating that current methods \"assume almost nothing about the underlying discrete point set, when, in fact, many real application data sets are close to hierarchical or nearly so\".\n\nBefore introducing their new method, the authors introduce new proxy measures of how tree-like a dataset is. These proxy measures are used later on in several bounds, including in their main theoretical result which guarantees the existence of a tree fitting method with some nice bound on the distortion.\n\nIn their theoretical analysis, the authors mention a connection between the tree fitting problem and hierarchical correlation clustering (HCC), along with an equivalence result between tree fitting algorithms and ultrametric fitting algorithms. Then, they introduce an adapted HCC problem formulation and three algorithms named HCCTriangle, HCCUltraFit and HCCRootedTreeFit. The first algorithm solves the adapted HCC problem. The second algorithm uses HCCTriangle to solve the ultrametric fitting problem. The last algorithm uses HCCUltraFit to solve the rooted tree fitting problem.\n\nIn the experiments, the HCCRootedTreeFit algorithm is tested versus various other methods from the literature. For these experiments the authors have used both common and synthetic datasets. They observe that their method underperforms on common datasets, but performs well on synthetic datasets with respect to the $\\ell_1$ norm. They attribute this observation to a lack of tree-like structure in the common datasets. They furthermore observe that their method underperforms with respect to the $\\ell_\\infty$ norm.", "questions": "1. What is the exact connection between the tree fitting problem and the HCC problem?\n2. How is the term $|E_t \\Delta E(P_t)|$ defined precisely?", "limitations": "Mostly yes. They do not really address the fact that their method does not seem to have a proper use case, but they do point out its weaknesses in the experiments.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The paper introduces interesting new notions of hyperbolicity and ultrametricity through their hyperbolicity and ultrametricity vectors. \n2. The authors derive an interesting connection between the distortion bounds for tree fitting and ultrametric fitting algorithms.\n3. The new notion of hyperbolicity is used to show that, contrary to common belief, the common datasets are not very tree-like.", "weaknesses": "The paper is very difficult to read. Due to the very large number of definitions and technical results, the paper reads more like a collection of statements than a paper. Much of the actual content seems to be put in the appendix, adding to the feeling that the paper is not at all self-contained. Moreover, the paper appears to use many tricks from different papers without any description of these tricks. For example, in line 233, the authors refer to some paper to obtain a tree fit without actually explaining the actual procedure. \n\nThe structure of the paper also makes it rather difficult to follow, with several forward- and backward references spread throughout the paper. As an example, Subsection 3.2 appears to state several results regarding algorithms that have not yet been introduced. Then, in the next subsection, these algorithms are introduced and following these algorithms, the authors quickly throw in a proof of a result from the previous Subsection. \n\nAnother issue with the paper is that they first formulate the tree (ultrametric) fitting problem, but then, after quickly mentioning a connection to hierarchical correlation clustering, seem to actually solve an adapted version of this HCC problem. However, the introduction of their adapted HCC problem is rather unclear and uses, for example, a 'number of disagreement edges' term that is not properly defined in the paper. Also, it is not really clear to me what the connection with this problem and the original problem is.\n\nDue to these issues I cannot adequately judge the validity of the many technical results of this paper.\n\nThere is also an issue regarding the newly proposed algorithm within the context of the experimental results. The authors show that their method underperforms on common datasets with respect to both the $\\ell_1$ norm and the $\\ell_\\infty$ norm. Moreover, the method is quite slow compared to two of the other methods. It therefore appears that this method is only useful in synthetic settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Thank all the reviewers for their comments and fruitful feedback. Below each review, we have posted a rebuttal that directly addresses concerns and clarifies any misunderstandings. If you wish to obtain further clarification, please reply in the relevant thread, and we will get back to you as soon as possible.\n* Thank you for the review and the constructive comments. We appreciate that you note our paper “derive an interesting connection” between the distortion bounds. We address your concerns from the “Weaknesses” and “Questions” section below.\n* The paper is very difficult to read. Due to the very large number of definitions and technical results, the paper reads more like a collection of statements than a paper. Much of the actual content seems to be put in the appendix, adding to the feeling that the paper is not at all self-contained. Moreover, the paper appears to use many tricks from different papers without any description of these tricks. For example, in line 233, the authors refer to some paper to obtain a tree fit without actually explaining the actual procedure.\n  * It was hard to contain every detail for the algorithms and proofs within a certain page limit so we put the most technical proofs in supplementary materials. However, we will absolutely work on improving its readability. For example, as you noted, line 233 -- 236 should clearly refer to Algorithm 4 in order to make the procedure more clear. Thank you for this constructive feedback!\n* The structure of the paper also makes it rather difficult to follow, with several forward- and backward references spread throughout the paper. As an example, Subsection 3.2 appears to state several results regarding algorithms that have not yet been introduced. Then, in the next subsection, these algorithms are introduced and following these algorithms, the authors quickly throw in a proof of a result from the previous Subsection.\n  * Again, the structure was not optimal as many technical proof details need to go in the Appendix due to space constraints initially. We will work on improving the structure.\n* Another issue with the paper is that they first formulate the tree (ultrametric) fitting problem, but then, after quickly mentioning a connection to hierarchical correlation clustering, seem to actually solve an adapted version of this HCC problem. However, the introduction of their adapted HCC problem is rather unclear and uses, for example, a 'number of disagreement edges' term that is not properly defined in the paper. Also, it is not really clear to me what the connection with this problem and the original problem is.\n  * There are a number of references which make a connection between the tree (ultrametric) fitting problem and the HCC problem: we addressed this question below. The connection to “adapted” HCC problem is that the quantity of `a number of disagreement edges’ (which should be properly defined using the symmetric difference notion; thanks for pointing this out) is related to $\\ell_1$-notion of hyperbolicity vector, so that we made a statement using $\\ell_1 / \\ell_1$ tree fitting problem (Definition 2.2). This work potentially develops and broadens the notion of such known “tree-likeness”.\n* There is also an issue regarding the newly proposed algorithm within the context of the experimental results. The authors show that their method underperforms on common datasets with respect to both the $\\ell_1$ norm and the $\\ell_\\infty$ norm. Moreover, the method is quite slow compared to two of the other methods. It therefore appears that this method is only useful in synthetic settings.\n  * We understand the point that our algorithm does not practically outperform currently known methods. As we illustrated in the synthetic experiments, we want to highlight that the current widely accepted concepts on hyperbolicity and tree-likeness of certain data sets may be imperfect, which can be observed in some synthetic examples and experiments. We suggest that future works on achieving more theoretically sound bounds will be interesting: it could also work well on common data sets?\n* What is the exact connection between the tree fitting problem and the HCC problem?\n  * The technical connection between ultrametric fitting problem and tree fitting problem can be described as the reduction from tree metric to ultrametric. In other words, if we have an adequate ultrametric fitting algorithm, then we can use it as the subroutine to develop a tree fitting algorithm. This connection was first developed by [7], which is already known. The connection between the HCC problem and the ultrametric fitting problem is also a “reduction”: there is a reduction from ultrametric to HCC. While there are a number of references describing this connection (including [2]), the connection we explored and utilized is similar to the work on [1].\n    * We included these technical details in the Appendix in order to be self-contained.\n* How is the term $|E_t \\Delta E(P_t)|$ defined precisely?\n  * Given a partition $P$ over $X$, we define $E(P) := \\cup_{C \\in P} \\binom{C}{2}$. In other words, $E(P)$ is the collection of *every* edge in the clusters of $P$. $\\Delta$ denotes the symmetric difference of two sets, namely $A \\Delta B := (A \\setminus B) \\cup (B \\setminus A)$. We will add these descriptions to make the statement precise; thank you for your feedback!\n"}, {"review_id": "lznel4SKCG", "reviewer": "Reviewer_x4xj", "summary": "The paper formulate the $l_p$ tree fitting problem introduces a new algorithm, HCCROOTEDTREEFIT, for building trees in hyperbolic space by investigating the relationship between hyperbolicity (ultrametricity) vectors and the error of tree (ultrametric) embedding, which outperforms previous methods both theoretically and empirically.,\n\n", "questions": "As described in the abstract, the proposed method is inspired by geometric group theory, can the authors be more specific on what is inspired the novel approach to the tree-fitting problem using which part of geometric group theory? \n\nWhat does the notation in equation between line 82 and 83 mean? $\\begin{pmatrix} X \\\\\\\\ 3 \\end{pmatrix}$ seems to mean combinatoric number in convention but $X$ here is a set.\n\n", "limitations": " The authors does not discussed about limitations, but this method is quite theoretical and is very unlikely to have potential negative societal impact", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) The authors have developed a novel approach to the tree-fitting problem that applies hyperbolic geometry and geometric group theory.\n2) The developed algorithm, HCCROOTEDTREEFIT, delivers a tree metric with $l_1$ distortion bounded by polynomial function of the average hyperbolicity, while previous research delivers a tree metric with $l_{\\infty}$ distortion only.\n3) Comparison not only on performance but also on speed are explored, which makes a more computational sense.\n4) Repeated experiments are conducted and standard deviation was analyzed. ", "weaknesses": "The paper is not well self-contained, needing additional supplementary materials to be complete.\n\nTable captions are not very comprehensive, e.g., Table 3 and Table 5, which increase the difficulty to understand the major experimental results.\n\nThe results lack qualitative examples to show 1) how different the proposed tree-fitting method is compared with previous tree-fitting methods. 2) how different the synthetic datasets is to real datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Thank all the reviewers for their comments and fruitful feedback. Below each review, we have posted a rebuttal that directly addresses concerns and clarifies any misunderstandings. If you wish to obtain further clarification, please reply in the relevant thread, and we will get back to you as soon as possible.\n* The paper is not well self-contained, needing additional supplementary materials to be complete.\n  * It was hard to contain every detail for the algorithms and proofs within a certain page limit so we put the most technical proofs in supplementary materials.\n* Table captions are not very comprehensive, e.g., Table 3 and Table 5, which increase the difficulty to understand the major experimental results.\n  * We will include more details on table captions; thank you for your feedback! For example, the caption of Table 3 could be “$\\ell_\\infty$ error (i.e.,$||d - d_T||_\\infty$, max distortion) over each methods and data sets.”\n* The results lack qualitative examples to show 1) how different the proposed tree-fitting method is compared with previous tree-fitting methods. 2) how different the synthetic datasets is to real datasets.\n  * Many of the existing tree fitting methods suffer from a lack of analysis (e.g., TreeRep, NeighborJoin). Even Gromov's original work, while mathematical, isn't presented as an algorithm. It's only a few recent papers  that have begun to do this analysis.\n  * The synthetic data sets are designed to emphasize and to provide specific control on the proxy measures of  “tree-likeness”. These examples show that 1) the current widely accepted notions of hyperbolicity and tree-likeness of certain data sets may be imperfect. Also, we would argue that the quantitative analysis on such common data sets is absent as well.\n* As described in the abstract, the proposed method is inspired by geometric group theory, can the authors be more specific on what is inspired the novel approach to the tree-fitting problem using which part of geometric group theory?\n  * Gromov's original work was in Geometric Group Theory; he was a pioneer of the field. We refer to his “algorithm” which is a very small part of the original work. And $\\delta$-hyperbolicity also came from his work.\n* What does the notation in equation between line 82 and 83 mean? $\\binom{X}{3}$ seems to mean combinatoric number in convention but $X$ here is a set.\n  * There is also a convention for defining $\\binom{X}{k}$($X$ choose $k$) for a set $X$, as the set of all $k$-element subsets of $X$ in a very similar fashion. See, for example, chapter 1.2 of Stanley’s Enumerative Combinatorics."}, {"review_id": "tzjbVZkmll", "reviewer": "Reviewer_uKfW", "summary": "The authors consider the tree fitting problem for a given distance. The authors cast the tree fitting problem as finding the relation between the hyperbolicity vector and the error of tree embedding. The authors propose an algorithmic approach with provably tight $\\ell_1$ error. The authors also illustrate the advantage of the proposed approach on some “tree-like” datasets.", "questions": "+ Could the authors elaborate the main ideas of the proposed algorithmic approach in Section 3.3? (although some algorithms are given to summarize the ideas, it is better to discuss about it, e.g., how the tree is constructed to fit a given distance, besides the analysis)?\n+ Could the authors discuss how the proposed algorithmic approach improves over some simple approach, such as the QuadTree approach (which is popularly used in the context of optimal transport)?\n+ If possible, please consider the QuadTree approach as a baseline for tree fitting in the experiments.\n+ In Algorithm 1, could the authors explain the “highlyconnected” concept? How is it defined as in the Algorithm 1?\n+ In line 269, why do the negative weights appear? (for tree metric, should the weights be nonnegative?) It seems unclear whether these approaches try to find a closest tree metric for a given distance?\n\nSome minor points:\n+ In line 58, “the table below”? which table is mentioned? It is better to have a reference for the mentioned table.\n+ In Theorem 3.4, could the authors comment on the constant $C=4$? Is it a tight result or is there any chance to improve it?\n\n---\n\nThank you for the rebuttal.", "limitations": "There are no discussions about the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ By casting the fitting tree problem as finding the relation between the hyperbolicity vector and the error of tree embedding, the authors propose provably tight $\\ell_1$ error algorithmic approach.\n+ The authors illustrate the advantage of the proposed approach on some “tree-like” datasets.\n+ Overall, the presentation is good. (It may be better to elaborate more details on the proposed algorithmic approach in Section 3.3)", "weaknesses": "+ At the heart of the proposed algorithmic approach (Section 3.3), although the authors summarize their proposed approach in several Algorithms, it is hard to get the ideas how the tree is constructed. It seems the authors focus more on analysis for the proposed algorithm.\n+ It seems better to include discussions about other existing approaches of tree fitting for a given distance. Besides the provable analysis of the proposed algorithmic approach, it is not clear how the proposed approach addresses some limits of existing approaches on tree fitting for a given distance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Thank all the reviewers for their comments and fruitful feedback. Below each review, we have posted a rebuttal that directly addresses concerns and clarifies any misunderstandings. If you wish to obtain further clarification, please reply in the relevant thread, and we will get back to you as soon as possible.\n\n* Thank you for your review and the constructive comments. We appreciate that you note our paper has a good presentation. We address your comments from the \"Weaknesses\" and \"Questions\" section below.\n\n* At the heart of the proposed algorithmic approach (Section 3.3), although the authors summarize their proposed approach in several Algorithms, it is hard to get the ideas how the tree is constructed. It seems the authors focus more on analysis for the proposed algorithm.\n  * We will add more sentences about the intuition behind the algorithm in order to elucidate the idea. Our tree construction is a bottom-up approach using the sorted order of \"Gromov product\" over all pairs. Then we sequentially add Steiner nodes to \"fit\" those products.\n  * Many of the existing tree fitting methods suffer from a lack of analysis (e.g., TreeRep, NeighborJoin). Even Gromov's original work, while mathematical, isn't presented as an algorithm. It's only a few recent papers that have begun to do this analysis, including ours.\n* It seems better to include discussions about other existing approaches of tree fitting for a given distance. Besides the provable analysis of the proposed algorithmic approach, it is not clear how the proposed approach addresses some limits of existing approaches on tree fitting for a given distance.\n  * As we illustrated in the synthetic experiments, ours and other empirical algorithms behave quite differently on the synthetic data sets. This suggests that existing approaches may underperform on certain “tree-like” inputs, and that common data sets are not nearly as tree-like as researchers thing. Also, as far as we know, both the $\\ell_1$ distortion bound and our approach is novel: there are some theoretical works which seek to minimize the $\\ell_1$ distortion (including the recent result [1], which is actually an O(1) approximation), but they cannot be implemented practically.\n* Could the authors elaborate the main ideas of the proposed algorithmic approach in Section 3.3? (although some algorithms are given to summarize the ideas, it is better to discuss about it, e.g., how the tree is constructed to fit a given distance, besides the analysis)?\n  * The intuition behind IsHighlyConnected is that if every node in both clusters is reasonably connected with those in the other cluster, then the number of bad triangles can be favorably controlled.\n* Could the authors discuss how the proposed algorithmic approach improves over some simple approach, such as the QuadTree approach (which is popularly used in the context of optimal transport)? If possible, please consider the QuadTree approach as a baseline for tree fitting in the experiments.\n  * QuadTree needs to input data points (Euclidean), while ours only requires a distance matrix. Therefore ours works on a more generic setup. We will conduct extra experiments on the Euclidean dataset in order to 1) compare with QuadTree (and other popular) algorithms as a baseline and 2) make an evaluation on a broader range of datasets, which are NOT tree-like at all.\n* In Algorithm 1, could the authors explain the “highlyconnected” concept? How is it defined as in the Algorithm 1?\n  * The intuition behind IsHighlyConnected is that if every node in both clusters is reasonably connected with those in the other cluster, then the number of bad triangles can be favorably controlled.\n  * We will add a figure which helps to describe the concept like https://i.imgur.com/u5uyw68.jpg.\n* In line 269, why do the negative weights appear? (for tree metric, should the weights be nonnegative?) It seems unclear whether these approaches try to find a closest tree metric for a given distance?\n  * For a set of distances to satisfy a (tree) metric, all edge weights should be nonnegative. It has been shown, however, empirically that negative weights can appear in other algorithms, such as NeighborJoin or TreeRep. If the input distances satisfy a metric, then our algorithm is guaranteed to output a proper tree fitting with all non-negative weights. (This cannot be guaranteed for other tree fitting algorithms.)\n* In line 58, “the table below”? which table is mentioned? It is better to have a reference for the mentioned table.\n  * Should be labeled as \"Table 1\". Thanks for pointing this out!\n* In Theorem 3.4, could the authors comment on the constant $C = 4$? Is it a tight result or is there any chance to improve it?\n  * We do not think that $C = 4$ is tight but we couldn't show it. That improvement seems difficult. We also did not yet find an example which forces $C > 1$.\n  * The reason we emphasized such constant $C$ is that the usual (unweighted) CC problem can be simply solved with $C = 1$, which is actually tight. To get more detailed, if we have an unweighted graph, we are able to find a clustering that the number of disagreement edges is bounded by the number of bad triangles (with the same definition). For example, an algorithm presented at ``Aggregating Inconsistent Information: Ranking and Clustering`` (Ailon et al., 2008) achieves this bound. Also, when analyzing this problem, considering such triangles plays an important role. That is why we are somewhat optimistic that $C = 4$ can be improved with, possibly tight results on $C = 1$. "}, {"review_id": "p2fDIX4ekq", "reviewer": "Reviewer_xUok", "summary": "The paper introduces a new algorithm, HCCRootedTreeFit, for fitting tree metrics to a given distance matrix. The algorithm is designed to minimize the ℓ1 distortion of the fit. The authors provide a detailed explanation of the algorithm, its theoretical properties, and an extensive experimental evaluation. The results show that the algorithm performs optimally when datasets are close to tree-like and when distortion is measured in the ℓ1 sense. The paper suggests that commonly used datasets, especially in geometric graph neural nets, are not well-represented by trees, indicating the need for more refined geometric notions for learning tasks with these datasets.", "questions": "Please solve the weakness above", "limitations": "NA", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": " The algorithm is theoretically sound, thoroughly evaluated, and performs optimally on tree-like datasets. The work provides valuable insights into dataset characteristics and has significant potential for practical applications, particularly in machine learning and data analysis.", "weaknesses": "The evaluation of the proposed algorithm is primarily focused on its performance on tree-like datasets. While this is certainly important, it would be beneficial to see how the algorithm performs on a broader range of datasets, particularly those that are not tree-like. This would provide a more comprehensive understanding of the algorithm's performance and its applicability to real-world problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Thank all the reviewers for their comments and fruitful feedback. Below each review, we have posted a rebuttal that directly addresses concerns and clarifies any misunderstandings. If you wish to obtain further clarification, please reply in the relevant thread, and we will get back to you as soon as possible.\n\n* Thank you for your review and the constructive comments. We appreciate that you note our paper \"provides valuable insights\" into dataset characteristics. We address your comment from the \"Weaknesses\" section below.\n\n* The evaluation of the proposed algorithm is primarily focused on its performance on tree-like datasets. While this is certainly important, it would be beneficial to see how the algorithm performs on a broader range of datasets, particularly those that are not tree-like. This would provide a more comprehensive understanding of the algorithm's performance and its applicability to real-world problems.\n  * We understand the point that more results on a broader range of data sets would make our discussion more fruitful and comprehensive. We will conduct extra experiments on the Euclidean dataset in order to 1) compare with other popular tree fitting algorithms works on Euclidean points (such as QuadTree) as a baseline and 2) make an evaluation on a broader range of datasets, which are NOT tree-like at all."}]

Author rebuttal:

Meta-review: This paper received 4 reviews, all above the acceptance threshold. The rebuttal period resulted in active discussions between authors and reviewers to clear up remaining concerns. The AC follows the consensus of the reviewers and suggests that the authors use the discussion outcomes to update the paper accordingly.
Decision: Accept (poster)