# HyperAid: Denoising in hyperbolic spaces for tree-fitting and hierarchical
clustering

Eli Chien, Puoya Tabaghi, Olgica Milenkovic  University of Illinois Urbana-
Champaign<EMAIL_ADDRESS>
(2022)

###### Abstract.

The problem of fitting distances by tree-metrics has received significant
attention in the theoretical computer science and machine learning communities
alike, due to many applications in natural language processing, phylogeny,
cancer genomics and a myriad of problem areas that involve hierarchical
clustering. Despite the existence of several provably exact algorithms for
tree-metric fitting of data that inherently obeys tree-metric constraints,
much less is known about how to best fit tree-metrics for data whose structure
moderately (or substantially) differs from a tree. For such noisy data, most
available algorithms perform poorly and often produce negative edge weights in
representative trees. Furthermore, it is currently not known how to choose the
most suitable approximation objective for noisy fitting. Our contributions are
as follows. First, we propose a new approach to tree-metric denoising
(HyperAid) in hyperbolic spaces which transforms the original data into data
that is “more” tree-like, when evaluated in terms of Gromov’s $\delta$
hyperbolicity. Second, we perform an ablation study involving two choices for
the approximation objective, $\ell_{p}$ norms and the Dasgupta loss. Third, we
integrate HyperAid with schemes for enforcing nonnegative edge-weights. As a
result, the HyperAid platform outperforms all other existing methods in the
literature, including Neighbor Joining (NJ), TreeRep and T-REX, both on
synthetic and real-world data. Synthetic data is represented by edge-augmented
trees and shortest-distance metrics while the real-world datasets include Zoo,
Iris, Glass, Segmentation and SpamBase; on these datasets, the average
improvement with respect to NJ is $125.94\%$. Our code is publicly
available.111https://github.com/elichienxD/HyperAid

Hierachical Clustering, Tree-metric, Hyperbolic

††copyright: acmcopyright††journalyear: 2022††doi:
XXXXXXX.XXXXXXX††conference: August 14-18, 2022, Washington DC, USA; August
14-18, 2022; Washington DC††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Computing methodologies Machine learning††ccs: Mathematics of computing Trees
Figure 1. The HyperAid framework.

##  1\. Introduction

The problem of fitting tree-distances between data points is of great
relevance in application areas concerned with extracting and processing
hierarchical information (Saitou and Nei, 1987; Ailon and Charikar, 2005;
Macaluso et al., 2021; Coenen et al., 2019; Hewitt and Manning, 2019). A
significant body of work on the topic has focused on fitting phylogenetic
trees based on evolutionary distances (Saitou and Nei, 1987) and using fitted
tree-models for historic linguistics and natural language processing (Coenen
et al., 2019; Hewitt and Manning, 2019). Since trees are usually hard to
accurately represent in low-dimensional Euclidean spaces (Linial et al.,
1995), alternative methods have been suggested for representation learning in
hyperbolic spaces (Nickel and Kiela, 2017). For these and related approaches,
it has been observed that the quality of embedding and hence the
representation error depend on the so called Gromov $\delta$-hyperbolicity
(Gromov, 1987) of the data, which will be discussed in-depth in the following
section. For perfect trees, $\delta=0$, and the larger the value of $\delta$
the less tree-like the data structure. When $\delta$ is sufficiently large, as
is the case when dealing with noisy observations or observations with
outliers, the embedding distortion may be significant (Abraham et al., 2007).
This is a well-known fact that has limited the performance of methods such as
Neighbor Joining (NJ) and TreeRep, which come with provable reconstruction
guarantees only in the presence of small tree-metric perturbations/noise
(Saitou and Nei, 1987; Sonthalia and Gilbert, 2020) (more precisely, the
correct output tree topology is guaranteed for “nearly additive” distance
matrices, i.e., matrices in which every distance differs from the true
distance by not more than half of the shortest edge weight in the tree).
Heuristic methods for tree-metric fitting, such as NINJA (Wheeler, 2009) and
T-REX (Boc et al., 2012) have similar issues, but address the problems of
scaling, and in the latter case, the issue of negative tree-edge weights that
may arise due to large $\delta$-hyperbolicity.

In a parallel development, the theoretical computer science community has
explored the problem of fitting both general tree-metrics and ultrametrics
with specialized distortion objectives (Ailon and Charikar, 2005; Harb et al.,
2005; Cohen-Addad et al., 2021). Ultrametrics are induced by rooted trees for
which all the root-to-leaf distances are the same. Although ultrametrics do
not have the versatility to model nonlinear evolutionary phenomena, they are
of great relevance in data analysis, in particular in the context of “linkage”
clustering algorithms (single, complete or average linkage) (Ailon and
Charikar, 2005). Existing methods for ultrametric approximations scale well
and provide approximation guarantees for their general graph problem
counterparts. For both general tree-metrics and ultrametrics, two objectives
have received significant attention: The Dasgupta objective and derivatives
thereof (Dasgupta, 2016; Charikar et al., 2019) and the $\ell_{p}$ objective
(Ailon and Charikar, 2005; Harb et al., 2005). Dasgupta’s objective was
notably used for hierarchical clustering (HC) in hyperbolic spaces as a means
to mitigate the hard combinatorial optimization questions associated with this
clustering metric (Sahoo et al., 2020); see also (Macaluso et al., 2021) for
other approaches to HC in hyperbolic spaces. Neither of the aforementioned
approaches provides a solution to the problem of fitting tree-metrics for data
with moderate-to-high Gromov hyperbolicity, i.e., noisy or perturbed tree-
metric data not covered by existing performance guarantee analyses. In
addition, no previous study has compared the effectiveness of different
objectives for the measure of fit for tree-metrics on real-world datasets.

Our contributions are three-fold.

  * •

We propose the first approach to data denoising (i.e., Gromov hyperbolicty
reduction) in hyperbolic space as the first step to improving the quality of
tree-metric fits.

  * •

We combine our preprocessing method designed to fit both general trees and
ultrametrics with solutions for removing negative edge-weights in the tree-
metrics that arise due to practical deviations from tree-like structures.

  * •

We demonstrate the influence of hyperbolic denoising on the quality of tree-
metric fitting and hierachical clustering for different objectives. In
particular, we perform an ablation study that illustrates the advantages and
disadvantages of different objectives (i.e., Dasgupta (Dasgupta, 2016) and
$\ell_{2}$ (Harb et al., 2005)) when combined with denoising in hyperbolic
spaces.

The paper is organized as follows. Related works are discussed in Section 2
while the relevant terminology and mathematical background material are
presented in Section 3. Our tree-fitting, HC clustering approach and
accompanying analysis on different choices of objective functions are
described in Section 4. More details regarding the HyperAid method are
provided in Section 5, with experimental results made available in Section 6.
All proofs are relegated to the Supplement.

##  2\. Related works

The Dasgupta HC objective.  Determining the quality of trees produced by HC
algorithms is greatly aided by an adequate choice of an objective function.
Dasgupta (Dasgupta, 2016) proposed an objective and proved that an
$O(\alpha_{n}\log n)$-approximation can be obtained using specialized
$\alpha_{n}$-approximation sparsest cut procedures (Dasgupta, 2016). HC
through the lens of Dasgupta’s objective and variants thereof have been
investigated in (Charikar and Chatziafratis, 2017; Moseley and Wang, 2017;
Ahmadian et al., 2019; Alon et al., 2020). For example, the authors of
(Moseley and Wang, 2017) showed that the average linkage (UPGMA) algorithm
produces a $1/3$-approximation for a Dasgupta-type objective. It is important
to point out that the Dasgupta objective depends only on the sizes of
unweighted subtrees rooted at lowest common ancestors (LCAs) of two leaves,
the optimal trees are restricted to be binary, and that it does not produce
edge-lengths (weights) in the hierarchy. The latter two properties are
undesirable for applications such as natural language processing, phylogeny
and evolutionary biology in general (Waterman et al., 1977). As a result,
other objectives have been considered, most notably metric-tree fitting
objectives, which we show can resolve certain issues associated with the use
of the Dasgupta objective.

Tree-metric learning and HC. In comparison to the Dasgupta objective, metric-
based objective functions for HC have been mostly overlooked. One metric based
objective is the $\ell_{p}$ norm of the difference between the input metric
and the resulting (fitted) tree-metric (Waterman et al., 1977). For example,
the authors of (Farach et al., 1995) showed that an optimal ultrametric can be
found with respect to the $\ell_{\infty}$ norm loss for arbitrary input metric
in polynomial time. It is also known in the literature that finding optimal
tree-metrics with respect to the $\ell_{p}$ norm, for $p\in[1,\infty],$ is NP-
hard and finding optimal ultrametrics for $p\in[1,\infty)$ is also NP-hard. In
fact, the $\ell_{\infty}$ problem for tree-metrics and the $\ell_{1}$ problem
for tree-metrics and ultrametrics are both APX-hard (Wareham, 1993; Agarwala
et al., 1998; Ailon and Charikar, 2005). The work (Agarwala et al., 1998)
presents a $3$-approximation result for the closest tree-metric under
$\ell_{\infty}$ norm and established an important connection between the
problems of fitting an ultrametric and fitting a tree-metric. The result shows
that an $\alpha$-approximation result for the constrained ultrametric fitting
problem yields a $3\alpha$-approximation solution for tree-metric fitting
problem. The majority of the known results for tree-metric fitting depend on
this connection. The algorithm in (Ailon and Charikar, 2005) offers an
$O((\log n\log\log n)^{1/p})$ approximation for both tree-metrics fitting and
ultrametrics fitting under general $\ell_{p}$ norms. The work (Cohen-Addad et
al., 2021) improves the approximation factor to $O(1)$ for the $\ell_{1}$
norm. Unfortunately, despite having provable performance guarantees, both the
methods from (Ailon and Charikar, 2005) and (Cohen-Addad et al., 2021) are not
scalable due to the use of correlation clustering. As a result, they cannot be
executed efficiently in practice even for trees that have $\sim$50 leaves, due
to severe computational bottlenecks.

Gradient-based HC. The authors of (Chierchia and Perret, 2020) proposed an
ultrametric fitting framework (Ufit) for HC based on gradient descent methods
that minimize the $\ell_{2}$ loss between the resulting ultrametric and input
metric. There, a subdifferentiable min-max operation is integrated into the
cost optimization framework to guarantee ultrametricity. Since an ultrametric
is a special case of a tree-metric, Ufit can be used in place of general tree-
metric fitting methods. The gHHC method (Monath et al., 2019) represents the
first HC approach based on hyperbolic embeddings. The authors assume that the
hyperbolic embeddings of leaves are given and describe how to learn the
internal vertex embeddings by optimizing a specialized objective function. The
HypHC approach (Chami et al., 2020) disposes of the requirement to have the
leaf embeddings. It directly learns a hyperbolic embedding by optimizing a
relaxation of Dasgupta’s objective (Dasgupta, 2016) and reconstructs the
discrete binary tree from the learned hyperbolic embeddings of leaves using
the distance of their hyperbolic lowest common ancestors to the root. Compared
to gHHC, our framework also does not require input hyperbolic embeddings of
leaves. We learn the hyperbolic embeddings of leaves by directly minimizing
the $\ell_{2}$ loss (rather than the Dasgupta objective) between the
hyperbolic distances and the input metric of pairs of points, which
substantially differs from HypHC and has the goal to preprocess (denoise) the
data for downstream tree-metric fitting. Furthermore, it will be shown in the
subsequent exposition that metric based losses are preferable to the Dasgupta
objective for the new task of hyperbolic denoising and consequent HC.

Learning in hyperbolic spaces. Representation learning in hyperbolic spaces
has received significant interest due to its effectiveness in capturing latent
hierarchical structures (Krioukov et al., 2010; Nickel and Kiela, 2017;
Papadopoulos et al., 2015; Tifrea et al., 2019). Several learning methods for
Euclidean spaces have been generalized to hyperbolic spaces, including
perceptrons and SVMs (Cho et al., 2019; Chien et al., 2021; Tabaghi et al.,
2021), neural networks (Ganea et al., 2018; Shimizu et al., 2021) and graph
neural networks (Chami et al., 2019; Liu et al., 2019). In the context of
learning hyperbolic embeddings, the author of (Sarkar, 2011) proposed a
combinatorial approach for embedding trees with low distortion in just two
dimensions. The work (Sala et al., 2018) extended this idea to higher
dimensions. Learning methods for hyperbolic embeddings via gradient-based
techniques were discussed in (Nickel and Kiela, 2017, 2018). None of these
methods currently provides quality clustering results for practical data whose
distances do not “closely” match those induced by a tree-metric. Furthermore,
the main focus of (Nickel and Kiela, 2017, 2018) is to learn hyperbolic
embeddings that represent the input graphs and trees as accurately as
possible. In contrast, our goal is to learn hyperbolic metrics that
effectively “denoise” parts of the input metric to better conform tree
structures, in order to improve the performance of arbitrary metric-tree
fitting and HC downstream methods.

##  3\. Preliminaries

Figure 2. Left: Illustration of the generative tree for an ultrametric and a
tree-metric. Note that all the weighted distances of leaves to the root are
equal for an ultrametric, while general tree-metrics do not have to satisfy
this constraint. Right: Detailed block diagram of our HyperAid framework.
Detailed explanations of the encoder and decoder modules are available in
Section 5.

Notation and terminology. Let $T=(V,E,w)$ be a tree with vertex set $V$, edge
set $E$ and nonnegative edge weights $w:E\rightarrow\mathbb{R}_{+}$. Let
$\mathcal{L}(T)\subseteq V$ denote the set of leaf vertices in $T$. The
shortest length path between any two vertices $v_{1},v_{2}\in V$ is given by
the metric $d_{T}:V\times V\rightarrow\mathbb{R}_{+}$. The metric $d_{T}$ is
called a tree-metric induced by the (weighted) tree $T$. In binary trees,
there is only one internal (nonleaf) vertex of degree two, the root vertex
$v_{r}$; all other internal vertices are of degree three. Since our edge
weights are allowed to be zero, nonbinary trees can be obtained by adding
edges of zero weight. The pairwise distances of leaves in this case remain
unchanged. A vertex $v_{2}$ is said to be a descendant of vertex $v_{1}$ if
$v_{1}$ belongs to the directed path from the root $v_{r}$ to $v_{2}$. Also,
with this definition, the vertex $v_{1}$ is an ancestor of the vertex $v_{2}$.
For any two vertices $v_{1},v_{2}\in\mathcal{L}(T)$, we let $v_{1}\land v_{2}$
denote their lowest common ancestor (LCA), i.e., the common ancestor that is
the farthest from the root vertex. We define a clan in $T$ as a subset of leaf
vertices that can be separated from the rest of the tree by removing a single
edge. Furthermore, we let $\mathcal{T}_{n}$ be the set of binary trees with
$n$ leaves. For any internal vertex $v$ of $T\in\mathcal{T}_{n}$, we let
$T(v)$ be a binary subtree of $T$ rooted at $v$.

$\delta$-hyperbolic metrics. Gromov introduced the notion of
$\delta$-hyperbolic metrics as a generalization of the type of metric obtained
from manifolds with constant negative curvature (Gromov, 1987; Sonthalia and
Gilbert, 2020), as described below.

###### Definition 3.1.

Given a metric space $(V,d)$, the Gromov product of $x,y\in V$ with respect to
a base point $r\in V$ is

(1) $\displaystyle(x,y)_{r}=\frac{1}{2}\left(d(r,x)+d(r,y)-d(x,y)\right).$

Note that the Gromov product measures how close $r$ is to the geodesic
connecting $x$ and $y$ (Sonthalia and Gilbert, 2020).

###### Definition 3.2.

A metric $d$ on a space $V$ is a $\delta$-hyperbolic metric for $\delta\geq 0$
if

(2) $\displaystyle\forall r,x,y,z\in
V\quad(x,y)_{r}\geq\min\left((x,z)_{r},(y,z)_{r}\right)-\delta.$

Usually, when stating that $d$ is $\delta$-hyperbolic we mean that $\delta$ is
the smallest possible value that satisfies the condition (2). An ultrametric
is a special case of a tree-metric (Ailon and Charikar, 2005), and is formally
defined as follows.

###### Definition 3.3.

A metric $d_{U}$ on a space $V$ is called an ultrametric if it satisfies the
strong triangle inequality property

(3) $\displaystyle\forall x,y,z\in V,\quad
d_{U}(x,y)\leq\max\left\\{d_{U}(x,z),d_{U}(y,z)\right\\}.$

Note that the generating tree of an ultrametric $d_{U}$ on $V$ has a special
structure: All element in $V$ are leaves of the tree and all leaves are at the
same distance from the root (Ailon and Charikar, 2005). An illustration of an
ultrametric can be found at Figure 2.

Hyperbolic geometry. A hyperbolic space is a nonEuclidean space with a
constant negative curvature. Despite the existence of various equivalent
models for hyperbolic spaces, Poincaré ball models have received the broadest
attention in the machine learning and data mining communities. Although our
hyperbolic denoising framework can be extended to work for any hyperbolic
model, we choose to work with Poincaré ball models with negative curvature
$-c,c>0$: $\mathbb{B}^{d}_{c}=\\{x\in\mathbb{R}^{d}:\sqrt{c}\,\|x\|<1\\}$. For
any two points $x,y\in\mathbb{B}^{d}_{c}$, their hyperbolic distance equals

(4) $\displaystyle
d_{\mathbb{B}^{d}_{c}}(x,y)=\frac{1}{\sqrt{c}}\cosh^{-1}\left(1+\frac{2c\|x-y\|^{2}}{(1-c\|x\|^{2})(1-c\|y\|^{2})}\right).$

Furthermore, for a reference point $r\in\mathbb{B}^{d}_{c}$, we denote its
tangent space, the first order linear approximation of $\mathbb{B}^{d}_{c}$
around $r$, by $T_{b}\mathbb{B}^{d}_{c}$. Möbius addition and scalar
multiplication — two basic operators on the Poincaré ball (Ungar, 2008) – may
be defined as follows. The Möbius sum of $x,y\in\mathbb{B}^{d}_{c}$ equals

(5) $\displaystyle x\oplus_{c}y=\frac{(1+2c\left\langle
x,y\right\rangle+c\|y\|^{2})x+(1-c\|x\|^{2})y}{1+2c\left\langle
x,y\right\rangle+c^{2}\|x\|^{2}\|y\|^{2}}.$

Unlike its vector-space counterpart, this addition is noncommutative and
nonassociative. The Möbius version of multiplication of
$x\in\mathbb{B}^{d}_{c}\setminus\\{0\\}$ by a scalar $t\in\mathbb{R}$ is
defined according to

(6) $\displaystyle
r\otimes_{c}x=\tanh(t\tanh^{-1}(\sqrt{c}\|x\|))\frac{x}{\sqrt{c}\|x\|}\text{
and }r\otimes_{c}0=0.$

For more details, see (Vermeer, 2005; Ganea et al., 2018; Chien et al., 2021;
Tabaghi et al., 2021). With the same operators, one can also define geodesics
– analogues of straight lines in Euclidean spaces and shortest path in graphs
– in $\mathbb{B}^{d}_{c}$. The geodesics connecting two points
$x,y\in\mathbb{B}^{d}_{c}$ is given by

(7) $\displaystyle\gamma_{x\rightarrow
y}(t)=x\oplus_{c}(t\otimes_{c}((-x)\oplus_{c}y)).$

Note that $t\in[0,1]$ and $\gamma_{x\rightarrow y}(0)=x$ and
$\gamma_{x\rightarrow y}(1)=y$. An illustration of the Poincare model is given
in Figure 3.

Figure 3. The two-dimensional Poincaré disk. (Right) a set of geodesics.
(Left) vectors in the tangent space at $r\in\mathbb{B}_{1}^{2}$.

##  4\. Hierarchical Clustering: A Tree Learning Problem

As previously explained, tree-metric fitting is closely related to
hierarchical clustering, and both methods are expected to greatly benefit from
data denoising. It is nevertheless unclear for which tree-metric fitting
algorithms and objectives used in hierarchical clustering does one see the
most significant benefits (if any) from denoising. To this end, we describe
two objectives that are commonly used for the aforementioned tasks in order to
determine their strengths and weaknesses and potential performance benefits.

Let $\\{d_{i,j}\\}_{i,j\in[n]}$ be a set of nonnegative dissimilarity scores
between a set of $n$ entities. In HC problems, the goal is to find a tree $T$
that best represents a set of gradually finer hierarchical partitions of the
entities. In this representation, the entities are placed at the leaves of the
tree $T$, i.e., $|\mathcal{L}(T)|=n$. Each internal vertex $v$ of $T$ is
representative of its clan, i.e., the leaves of $T(v)$ or the hierarchical
cluster at the level of $v$. We find the following particular HC problem
definition useful in our analysis.

###### Problem 4.1.

Let $\\{d_{i,j}\\}_{i,j\in[n]}$ be a set of pairwise dissimilarities between
$n$ entities. The optimal hierarchical clusters are equivalent to a binary
tree $T^{*}$ that is a solution to the following problem:

$T^{*}=\operatorname*{argmin}_{T\in\mathcal{T}_{n}}\sum_{i,j\in[n]}L(f(v_{i},v_{j}),d_{i,j}),$

where $f:\mathcal{L}(T)\times\mathcal{L}(T)\rightarrow\mathbb{R}_{+}$ is a
(known) function of pairwise dissimilarities of the leaves in $T$, and
$L(\cdot,\cdot)$ is a given loss function.

###  4.1. The Dasgupta objective

Dasgupta (Dasgupta, 2016) introduced the following cost function for HC:

(8) $\mathrm{cost}(T)=\sum_{i,j\in[n]}|\mathcal{L}(T(v_{i}\land
v_{j}))|d_{i,j}.$

The optimal HC solution is a binary tree that maximizes (8). In the formalism
of Problem 4.1, this approach assumes that the pairwise dissimilarity between
leaf vertices $v_{i}$ and $v_{j}$ equals the number of leaves of the tree
rooted at their LCA, i.e.,

$f(v_{i},v_{j})=|\mathcal{L}(T(v_{i}\land v_{j}))|.$

In words, two dissimilar leaves $v_{i}$ and $v_{j}$ should have an LCA
$v_{i}\land v_{j}$ that is close to the root. This ensures that the size of
$|\mathcal{L}(T(v_{i}\land v_{j}))|$ is proportional to $d_{i,j}$. It is also
important to note that this method is sensitive to the absolute value of the
input dissimilarities, since the loss function is the inner product between
measurements and tree leaf dissimilarities, i.e., $L(|\mathcal{L}(T(v_{i}\land
v_{j}))|,d_{i,j})=-|\mathcal{L}(T(v_{i}\land v_{j}))|d_{i,j}$.

###  4.2. The $\ell_{p}$ loss objective

Figure 4. Hierarchical clusters learned by different objectives.
Figure-$(a_{1})$ Dissimilarity measurements are pairwise leaf distances on the
weighted tree $T$ (optimal tree in $\ell_{2}$ sense). Figure-$(a_{2})$: The
tree $T_{\mathrm{dasg.}}$ optimizes Dasgupta’s objective for measurements
$\\{d_{T}(v_{i},v_{j})\\}_{i,j\in[4]}$. Figure-$(b_{1})$: Dissimilarity
measurements are pairwise distances of points on a line in $\mathbb{R}$, i.e.,
$\mathcal{D}=\\{d_{i,j}:d_{i,j}=|x_{i}-x_{j}|,i,j\in[6]\\},$ where
$x_{i}=10^{i}$ for all $i\in[6]$. Figure-$(b_{2})$: The Dasgupta-optimal tree
for $\mathcal{D}$. Figure-$(b_{3})$: Both trees $T_{1}$ and $T_{2}$ optimize
the $\ell_{p}$ cost function ($\varepsilon\rightarrow 0^{+}$).

Instead of using the Dasgupta objective, one can choose to work with a leaf
dissimilarity metric that is provided by the tree distance function, $d_{T}$.
This way, one can learn a _weighted tree_ that best represents the input
dissimilarity measurements. This is formally described as follows.

###### Problem 4.2.

Let $\\{d_{i,j}\\}_{i,j\in[n]}$ be a set of pairwise dissimilarities of $n$
entities. The optimal hierarchical clusters in the $\ell_{p}$ norm sense are
equivalent to a tree $T^{*}$ that minimizes the objective

(9)
$\mathrm{cost}_{p}(T)=\Big{(}\sum_{v_{i},v_{j}\in\mathcal{L}(T)}|d_{T}(v_{i},v_{j})-d_{i,j}|^{p}\Big{)}^{\frac{1}{p}},\text{
where $p\geq 1$.}$

According to our general formalism, Problem 4.2 uses the natural tree-distance
function to compute the leaf dissimilarities, i.e.,
$f(v_{i},v_{j})=d_{T}(v_{i},v_{j})$, and the $\ell_{p}$ loss to measure the
quality of the learned trees, i.e.,
$L(d_{T}(v_{i},v_{j}),d_{i,j})=|d_{T}(v_{i},v_{j})-d_{i,j}|^{p}$. The
objective function in Problem 4.2 aims to jointly find a topology (adjacency
matrix) and edge weights for a tree that best approximates a set of
dissimilarity measurements. This problem can be interpreted as approximating
the measurement with an additive distance matrix (i.e., distances induced by
trees). This is a significantly stronger constraint than the one induced by
the requirement that two entities that are similar to one another should be
placed (as leaves) as close as possible in the tree. We illustrate this
distinction in Figure 4 $(a_{1}),(a_{2})$: The dissimilarity measurements are
generated according to the tree $T$ and the vertices $v_{2}$ and $v_{3}$ can
be arbitrarily close to each other ($\varepsilon\rightarrow 0$)— see Figure
4-$(a_{1})$. The optimal tree in the $\ell_{p}$ sense does not place these
vertices close to each other since the objective is to approximate all
dissimilarity measurements with a set of additive distances. This is therefore
in contrast to Dasgupta’s objective where, for a small enough $\varepsilon$,
it favors placing the vertices $v_{2}$ and $v_{3}$ closest to each other (see
Figure 4-$(a_{2})$). In Figures 4 $(b_{1}-b_{3})$, we provide another example
to illustrate the distinction between optimal clusters according to the
$\ell_{2}$ and Dasgupta’s criteria.

Remark 1. We can interpret Problem 4.2 as two independent problems: (1)
Learning edge-weights, and (2) Learning the topology. A binary tree $T$ with
$n$ leaves has a total of $2n-1$ vertices and $2n-2$ edges. Let
$w=(w_{1},\ldots,w_{2n-2})^{T}\in\mathbb{R}^{2n-2}_{+}$ be the vector of the
edge weights. Any distance between pairs of vertices in
$v_{1},\ldots,v_{n}\in\mathcal{L}(T)$ can be expressed as a linear combination
of the edge weights. We can hence write
$d_{T}\in\mathbb{R}^{\frac{n\times(n-1)}{2}}$ for the vector of all pairwise
distances of leaves, so that $d_{T}=A_{T}w$. Given a fixed topology (adjacency
matrix of the tree $T$), we can compute the edges weight of $T$ that minimize
the objective function in Problem 4.2

(10) $\min_{w:E\rightarrow\mathbb{R}_{+}}\mathrm{cost}_{p}(T).$

There always exists at least one solution to the optimization problem 4.2.
This is the result of the following proposition.

###### Proposition 4.1.

The objective in Problem 4.2 is a convex function of the edge weights of the
tree $T$.

Remark 2. Let $e_{1}$ and $e_{2}$ be two edges, with weights $w_{1}$ and
$w_{2}$, incident to the root of a binary tree $T\in\mathcal{T}_{n}$. We can
delete the root along with the edges $e_{1}$ and $e_{2}$, and place an edge of
weight $w_{1}+w_{2}$ between its children. This process trims the binary tree
$T$ while preserving all pairwise distances between its leaf vertices. Hence,
we can also work with trimmed nonbinary trees. Furthermore, in this formalism,
the root vertex does not carry any hierarchy-related information about the
entities (leaves), although it is important for “anchoring” the tree in HC. We
discuss how to select a root vertex upon tree reconstruction in our subsequent
exposition.

###  4.3. Hierarchical objectives: $\ell_{p}$ vs. Dasgupta

Figure 5. The reconstruction error for the trees
$T_{\mathrm{dasg.}}(\mathcal{D}^{n}_{\mathrm{dasg.}})$,
$T_{\mathrm{dasg.}}(\mathcal{D}^{n}_{\ell_{2}})$,
$T_{\ell_{2}}(\mathcal{D}^{n}_{\ell_{2}})$, and
$T_{\ell_{2}}(\mathcal{D}^{n}_{\mathrm{dasg.}})$. We have
$d(T_{1},T_{2}):=\frac{2}{n(n-1)}\|d_{T_{1}}-d_{T_{2}}\|_{2},$ where $d_{T}$
is the pairwise leaf distances in the tree $T\in\mathcal{T}_{n}$, assuming
unit length edges.

Here we discuss _which objective function produces more “acceptable” trees and
hierarchical clusters, $\ell_{p}$ or Dasgupta?_ In clustering problems for
which we do not have the ground truth clusters, it is hard to quantify the
quality of the solution. This is especially the case when using different
objectives, as in this case comparisons may be meaningless. To address this
issue, we performed an experiment in which ground-truth synthetic data is
modeled in a way that reflect the properties of the objectives used in
optimization. Then, the quality of the objective is measured with respect to
its performance on both model-matched and model-unmatched data.

Let us start by generating a ground truth random (weighted) tree
$T\in\mathcal{T}_{n}$ with edge weights distributed uniformly and
independently in $[0,1]$. Measurements are subsequently generated by computing
the dissimilarities of leaves in $T$. According to the Dasgupta objective, the
dissimilarity between $v_{i},v_{j}\in\mathcal{L}(T)$ is given by
$|\mathcal{L}(T(v_{i}\land v_{j})|$, whereas according to the $\ell_{2}$
objective, it is given by $d_{T}(v_{i},v_{j})$ (all distances are computed wrt
the weighted tree $T$). We postulate that _if the measurements are generated
according to the Dasgupta notion of dissimilarities, then his objective should
perform better in terms of recovering the original tree than the $\ell_{2}$
objective; and vice versa_.

In this experiment, we generate $100$ random ground truth trees with i.i.d.
edge weights from $\mathrm{Unif.}[0,1]$; and produce measurements according to
both objectives, denoted by $\mathcal{D}_{\mathrm{dasg.}}$ and
$\mathcal{D}_{\ell_{2}}$. Then, we generate a fixed set of $10^{5}$ random
trees and find the tree that minimizes the cost function of each of the
problems. Let $\mathcal{D}^{n}_{\mathrm{dasg.}}$ be the measurements of the
form $\\{|\mathcal{L}(T(v_{i}\land v_{j})|\\}_{i,j\in[n]}$ and
$\mathcal{D}^{n}_{\ell_{2}}$ be the measurements of the form
$\\{d_{T}(v_{i},v_{j})\\}_{i,j\in[n]}$ for the randomly generated tree
$T\in\mathcal{T}_{n}$. We let $T_{\ell_{2}}(\mathcal{D}^{n}_{\mathrm{dasg.}})$
be the binary tree with the minimum $\ell_{2}$ cost on dissimilarity
measurements $\mathcal{D}^{n}_{\mathrm{dasg.}}$. We define
$T_{\ell_{2}}(\mathcal{D}^{n}_{\ell_{2}})$,
$T_{\mathrm{dasg.}}(\mathcal{D}^{n}_{\mathrm{\ell_{2}}})$, and
$T_{\mathrm{dasg.}}(\mathcal{D}^{n}_{\mathrm{dasg.}})$ similarly. The goal is
to compare the deviation of $T_{\ell_{2}}(\mathcal{D}^{n}_{\mathrm{dasg.}})$
and $T_{\mathrm{dasg.}}(\mathcal{D}^{n}_{\mathrm{dasg.}})$ from the ground
truth tree $T$, i.e., $d(T,T_{\ell_{2}}(\mathcal{D}^{n}_{\mathrm{dasg.}}))$
vs. $d(T,T_{\mathrm{dasg.}}(\mathcal{D}^{n}_{\mathrm{dasg.}}))$. We ask the
same question for $T_{\ell_{2}}(\mathcal{D}^{n}_{\ell_{2}})$ and
$T_{\mathrm{dasg.}}(\mathcal{D}^{n}_{\ell_{2}})$.

In Figure 5, we show the scatter plot of the results for each of the $100$
random trials, pertaining to trees with $n$ leaves. If the measurements are
generated according to the $\ell_{2}$ objective, then $T_{\ell_{2}}$ recovers
the underlying tree with higher accuracy compared to $T_{\mathrm{dasg.}}$, as
desired. On the other hand, for dissimilarities generated according to
Dasgupta’s objective, $T_{\ell_{2}}$ still manages to recover the underlying
tree better than $T_{\mathrm{dasg.}}$ for larger trees ($n=10,11,12)$. This
suggests that the $\ell_{2}$ objective could be more useful in recovering the
underlying tree for more versatile types of dissimilarity measurements and
larger datasets.

##  5\. Hyperbolic tree-denoising

We describe next how to solve the constrained optimization Problem 4.2 in a
hyperbolic space, and explain why our approach has the effect of data
denoising for tree-metric learning. The HyperAid framework is depicted in
Figure 2. In particular, the HyperAid encoder is described in Section 5.1,
while the decoder is described in Section 5.2.

###  5.1. A $\delta$-hyperbolic metric as a soft tree-metric

The first key idea is to exploit the fact that a tree-metric $d_{T}$ is
$0$-hyperbolic. This can be deduced from the following theorem.

###### Theorem 5.1 (Theorem 1 in (Buneman, 1974)).

A graph $G(V,E,w)$ is a tree if and only if it is connected, contains no loops
and has shortest path distance $d$ satisfying the four-point condition:

$\displaystyle\forall x,y,z,r\in V,\quad d(x,y)+d(z,r)$ (11)
$\displaystyle\leq\max\left\\{d(x,z)+d(r,y),d(r,x)+d(y,z)\right\\}.$

Note that through some simple algebra, one can rewrite condition (2) for
$\delta$-hyperbolicity as

$\displaystyle\forall x,y,z,r\in V,\quad d(x,y)+d(z,r)-2\delta$ (12)
$\displaystyle\leq\max\left\\{d(x,z)+d(r,y),d(r,x)+d(y,z)\right\\}.$

It is also known that any $0$-hyperbolic metric space embeds isometrically
into a metric-tree (Dress, 1984).

The second key idea is that condition (2) with a value of $\delta>0$ may be
viewed as a relaxation of the tree-metric constraint. The parameter $\delta$
can be viewed as the slackness variable, while a $\delta$-hyperbolic metric
can be viewed as a “soft” tree-metric. Hence, the smaller the value of
$\delta$, the closer the output metric to a tree-metric. Denoising therefore
refers to the process of reducing $\delta$.

Note that direct testing of the condition (2) takes $O(n^{4})$ time, which is
prohibitively complex in practice. Checking the soft tree-metric constraint
directly also takes $O(n^{4})$ time, but to avoid this problem we exploit the
connection between $\delta$-hyperbolic metric spaces and negative curvature
spaces. This is our third key idea, which allows us to optimize the Problem
4.2 satisfying the soft tree-metric constraint efficiently. More precisely,
$\delta\times\sqrt{c}=\mathrm{const}$ (see Appendix B). Hence, a distance
metric induced by a hyperbolic space of negative curvature $-c$ will satisfy
the soft tree-metric constraint with slackness at most
$\delta=\mathrm{const.}\times\frac{1}{\sqrt{c}}$. Therefore, using recent
results pertaining to optimization in hyperbolic spaces (i.e., Riemannian SGD
and Riemannian Adam (Bonnabel, 2013; Kochurov et al., 2020)), we can
efficiently solve the Problem 4.2 with a soft tree-metric constraint in a
hyperbolic space. Combined with our previous argument, we demonstrate that
finding the closest $\delta$-hyperbolic metric with $\delta$ small enough may
be viewed as tree-metric denoising.

Based on $\delta\times\sqrt{c}=\mathrm{const}$, one many want to let
$c\rightarrow\infty$. Unfortunately, optimization in hyperbolic spaces is
known to have precision-quality tradeoff problems (Sala et al., 2018; Nickel
and Kiela, 2018), and some recent works has attempted to address this issue
(Yu and De Sa, 2019, 2021). In practice, one should choose $c$ at a moderate
scale ($\sim 100$ in our experiment). The loss optimized by the encoder in
HyperAid equals

(13)
$\displaystyle\min_{x_{1},\ldots,x_{n}\in\mathbb{B}_{c}^{d}}\Big{(}\sum_{i,j\in[n]}|d_{\mathbb{B}_{c}^{d}}(x_{i},x_{j})-d_{i,j}|^{p}\Big{)}^{\frac{1}{p}},$

where $p\geq 1$, and $d_{i,j}$ are dissimilarities between $n$ entities.

A comparison between HyperAid and HypHC is once more in place. The purpose of
using hyperbolic optimization in HypHC and our HyperAid is very different.
HypHC aims to optimize the Dasgupta objective and introduces a continuous
relaxation of this cost in hyperbolic space, based on continuous versions of
lowest common ancestors (See Equation (9) in (Chami et al., 2020)). In
contrast, we leverage hyperbolic geometry for learning soft tree-metrics under
$\ell_{p}$ loss, which denoises the input metrics to better fit “tree-like”
measurements. The resulting hyperbolic metric can then be further used with
any downstream tree-metric learning and inference method, and has therefore a
level of universality not matched by HypHC whose goal is to perform HC. Our
ablation study to follow shows that HypHC cannot offer performance
improvements like our approach when combined with downstream tree-metric
learners.

###  5.2. Decoding the tree-metric

Tree-metric fitting methods produce trees based on arbitrary input metrics. In
this context, the NJ (Saitou and Nei, 1987) algorithm is probably the most
frequently used algorithm, especially in the context of reconstructing
phylogenetic trees. TreeRep (Sonthalia and Gilbert, 2020), a divide-and-
conquer method, was also recently proposed in the machine learning literature.
In contrast to linkage base methods that restrict their output to be
ultrametrics, both NJ and TreeRep can output a general tree-metric. When the
input metric is a tree-metric, TreeRep is guaranteed to recover it correctly
in the absence of noise. It is also known that the local distortion of TreeRep
is at most $\delta>0$ when the input metric is not a tree-metric but a
$\delta$-hyperbolic metric. NJ can recover the ground truth tree-metric when
input metric is a “slightly” perturbed tree-metric (Atteson, 1997). Note that
methods that generate ultrametrics such as linkage-based methods and Ufit do
not have similar accompanying theoretical results.

The key idea of HyperAid is that if we are able to reduce $\delta$ for the
input metric, both NJ, TreeRep (as well as other methods) should offer better
performance and avoid pitfalls such as negative tree edge-weights. Since an
ultrametric is a special case of a tree-metric, we also expect that our
denoising process will offer empirically better performance for ultrametrics
as well, which is confirmed by the results presented in the Experiments
Section.

Rooting the tree.  The NJ and TreeRep methods produce unrooted trees, which
may be seen as a drawback for HC applications. This property of the resulting
tree is a consequence of the fact that NJ does not assume constant rates of
changes in the generative phenomena. The rooting issue may be resolved in
practice through the use of outgroups, or the following simple solution known
as _mid-point rooting_. In mid-point rooting, the root is assumed to be the
midpoint of the longest distance path between a pair of leaves; additional
constraints may be used to ensure stability under limited leaf-removal.
Rooting may also be performed based on priors, as is the case for outgroup
rooting (Hess and De Moraes Russo, 2007).

Complexity analysis.  We focus on the time complexity of our encoder module.
Note that for the exact computation of the (Dasgupta) loss, HypHC takes
$O(n^{3})$ time, while our $\ell_{p}$ norm loss only takes $O(n^{2})$ time.
Nevertheless, as pointed out by the authors of HypHC, one can reduce the time
complexity to $O(n^{2})$ by sampling only one triplet per leaf. A similar
approach can be applied in our encoder, resulting in a $O(n)$ time complexity.
Hence, the time complexity of our HyperAid encoder is significantly lower than
that of HypHC, as we focus on a different objective function. With respect to
tree-metric and ultrametric fitting methods, we still have low-order
polynomial time complexities. For example, NJ runs in $O(n^{3})$ time, while
an advanced implementation of UPGMA requires $O(n^{2})$ time (Murtagh, 1984).

##  6\. Experiments

To demonstrate the effectiveness of our HyperAid framework, we conduct
extensive experiments on both synthetic and real-world datasets. We mainly
focus on determining if denoised data leads to decoded trees that have a
smaller losses compared to those generated by decoders that operate on the
input metrics directly (Direct). Due to space limitations, we only examine the
$\ell_{2}$ norm loss, as this is the most common choice of objective in
practice; HyperAid easily generalizes to arbitrary $p\in[1,\infty)$. An in-
depth description of experiments is deferred to the Supplement.

Tree-metric methods. We test both NJ and TreeRep methods as decoders. Note
that TreeRep is a randomized algorithm so we repeat it $20$ times and pick the
tree with lowest $\ell_{2}$ loss, as suggested in the original paper
(Sonthalia and Gilbert, 2020). We also test the T-REX (Boc et al., 2012)
version of NJ and Unweighted NJ (UNJ) (Gascuel et al., 1997), both of which
outperform NJ due to their sophisticated post-processing step. T-REX is not an
open-source toolkit and we can only use it by interfacing with its website
manually, which limits the size of the trees that can be tested; this is the
current reason for reporting the performance of T-REX only for small-size
real-world datasets.

Ultrametric methods. We also test if our framework can help ultrametric
fitting methods, including linkage-based methods (single, complete, average,
weight) and gradient-based ultrametric methods such as Ufit. For Ufit, we use
the default hyperparameters provided by the authors (Chierchia and Perret,
2020), akin to (Chami et al., 2020).

###  6.1. Synthetic datasets

Figure 6. Visualization of the resulting trees for zoo (left) and iris (right). Vertex colors indicate the ground truth labels. Table 1. The $\ell_{2}$ norm loss of the resulting trees, averaged over three independent runs; $n$, $R$, and EL stand for the number of leaves, edge-noise ratio and the $\ell_{2}$ loss of the hyperbolic distances that we learned, respectively (listed for each dataset). Bold values indicate the best results among tree-metric methods and ultrametric methods. If additionally depicted in red, the values pertain to the best achievable performance. Grey shaded boxes indicate the better of the two results for Direct and HyperAid, for the same decoder. We also report the $\delta$ hyperbolicity of the raw input metric and our learned hyperbolic metric, as well as the values of Gain$=$ (Direct/HyperAid -1). Note that the first two decoders produce tree-metrics while the remaining ones result in ultrametrics. |  $n=64,R=0.1$, EL$=32.93$ |  $n=64,R=0.3$, EL$=37.75$ |  $n=64,R=0.5$, EL$=31.36$
---|---|---|---
|  | Direct
---
($\delta:4.67$)
| HyperAid
---
($\delta:3.14$)
Gain (%) |  | Direct
---
($\delta:4.33$)
| HyperAid
---
($\delta:2.60$)
Gain (%) |  | Direct
---
($\delta:3.50$)
| HyperAid
---
($\delta:2.05$)
Gain (%)
NJ | 139.57 |  [HTML]EFEFEF 117.19 | 19.09 | 97.14 |  [HTML]EFEFEF 93.14 | 4.29 | 80.92 |  [HTML]EFEFEF 72.36 | 11.82
TreeRep | 167.59 |  [HTML]EFEFEF150.37 | 11.45 | 169.06 |  [HTML]EFEFEF138.28 | 22.26 | 131.52 |  [HTML]EFEFEF97.15 | 35.37
single | 379.14 |  [HTML]EFEFEF370.55 | 2.31 | 290.11 |  [HTML]EFEFEF254.77 | 13.87 | 236.10 |  [HTML]EFEFEF196.38 | 20.22
complete | 376.24 |  [HTML]EFEFEF355.54 | 5.82 | 293.06 |  [HTML]EFEFEF279.55 | 4.83 | 281.92 |  [HTML]EFEFEF231.41 | 21.82
average |  [HTML]EFEFEF148.68 | 149.83 | -0.77 | 108.05 |  [HTML]EFEFEF106.64 | 1.32 | 85.22 |  [HTML]EFEFEF83.63 | 1.89
weighted | 162.35 |  [HTML]EFEFEF150.86 | 7.61 | 132.96 |  [HTML]EFEFEF130.85 | 1.61 | 111.55 |  [HTML]EFEFEF104.41 | 6.84
Ufit | 228.21 |  [HTML]EFEFEF227.25 | 0.42 | 131.97 |  [HTML]EFEFEF124.78 | 5.76 | 90.20 |  [HTML]EFEFEF85.45 | 5.56
|  $n=128,R=0.1$, EL$=172.45$ |  $n=128,R=0.3$, EL$=122.12$ |  $n=128,R=0.5$, EL$=94.26$
|  | Direct
---
($\delta:6.67$)
| HyperAid
---
($\delta:1.36$)
Gain (%) |  | Direct
---
($\delta:4.83$)
| HyperAid
---
($\delta:1.31$)
Gain (%) |  | Direct
---
($\delta:4.00$)
| HyperAid
---
($\delta:1.23$)
Gain (%)
NJ | 283.73 |  [HTML]EFEFEF 259.38 | 9.38 | 201.71 |  [HTML]EFEFEF 181.52 | 11.12 | 151.58 |  [HTML]EFEFEF 142.86 | 6.09
TreeRep | 505.03 |  [HTML]EFEFEF318.62 | 58.50 | 383.12 |  [HTML]EFEFEF228.30 | 67.81 | 343.21 |  [HTML]EFEFEF192.57 | 78.22
single | 936.98 |  [HTML]EFEFEF767.25 | 22.12 | 688.52 |  [HTML]EFEFEF519.70 | 32.48 | 563.58 |  [HTML]EFEFEF431.50 | 30.61
complete | 826.73 |  [HTML]EFEFEF698.71 | 18.32 | 738.98 |  [HTML]EFEFEF583.67 | 26.60 | 619.42 |  [HTML]EFEFEF454.95 | 36.14
average |  [HTML]EFEFEF323.58 | 326.26 | -0.82 | 236.29 |  [HTML]EFEFEF234.92 | 0.58 | 182.29 |  [HTML]EFEFEF178.40 | 2.18
weighted | 340.93 |  [HTML]EFEFEF340.30 | 0.18 |  [HTML]EFEFEF301.30 | 316.85 | -4.90 |  [HTML]EFEFEF262.61 | 273.47 | -3.97
Ufit | 681.52 |  [HTML]EFEFEF556.37 | 22.49 | 388.47 |  [HTML]EFEFEF303.14 | 28.15 | 231.69 |  [HTML]EFEFEF198.29 | 16.84
|  $n=256,R=0.1$, EL$=248.89$ |  $n=256,R=0.3$, EL$=219.41$ |  $n=256,R=0.5$, EL$=172.52$
|  | Direct
---
($\delta:7.33$)
| HyperAid
---
($\delta:4.24$)
Gain (%) |  | Direct
---
($\delta:5.83$)
| HyperAid
---
($\delta:3.10$)
Gain (%) |  | Direct
---
($\delta:4.33$)
| HyperAid
---
($\delta:2.38$)
Gain (%)
NJ | 910.31 |  [HTML]EFEFEF 642.68 | 41.64 | 450.57 |  [HTML]EFEFEF 420.97 | 7.03 | 320.29 |  [HTML]EFEFEF 312.83 | 2.38
TreeRep | 1484.36 |  [HTML]EFEFEF1078.49 | 37.63 | 1125.81 |  [HTML]EFEFEF751.72 | 49.76 | 925.65 |  [HTML]EFEFEF551.10 | 67.96
single | 2343.78 |  [HTML]EFEFEF2277.91 | 2.89 | 1666.06 |  [HTML]EFEFEF1397.08 | 19.25 | 1313.64 |  [HTML]EFEFEF1066.32 | 23.19
complete | 2186.13 |  [HTML]EFEFEF2024.22 | 7.99 | 1786.13 |  [HTML]EFEFEF1532.99 | 16.51 | 1565.70 |  [HTML]EFEFEF1390.28 | 12.61
average | 758.35 |  [HTML]EFEFEF756.91 | 0.18 |  [HTML]EFEFEF521.83 | 521.91 | -0.01 | 392.09 |  [HTML]EFEFEF386.87 | 1.35
weighted | 794.90 |  [HTML]EFEFEF776.84 | 2.32 |  [HTML]EFEFEF681.73 | 683.01 | -0.18 | 626.06 |  [HTML]EFEFEF600.36 | 4.27
Ufit | 2026.42 |  [HTML]EFEFEF1974.59 | 2.62 | 1206.72 |  [HTML]EFEFEF1008.93 | 19.60 | 774.92 |  [HTML]EFEFEF641.07 | 20.88

Let $R\in\\{0.1,0.3,0.5\\}$ be what we refer to the _edge-noise rate_ , which
controls the number of random edges added to a tree as a means of introducing
perturbations. We generate a random binary tree and then add $R\times(2n-2)$
random edges between vertices, including both leaves and internal vertices.
The input metric to our encoder is the collection of shortest path distances
between leaves. We generate such corrupted random binary trees with
$n\in\\{64,128,256\\}$. All the results are averages over three independent
runs with the same set of input metrics. Note that this edge-noise model
results in graph-generated similarities which may not have full generality but
are amenable to simple evaluations of HyperAid in terms of detecting spurious
noisy edges and removing their effect from the resulting tree-fits or
hierarchies.

It is easy to see that our framework consistently improves the performance of
tree-metric learning methods, with gains as large as $41\%$ for NJ and $78\%$
for TreeRep (and $12.54\%$ and $47.66\%$ on average, respectively).
Furthermore, one can see that the hyperbolic metric learned by HyperAid indeed
results in smaller $\delta$-hyperbolicity values compared to the input. For
ultrametric methods, our framework frequently leads to improvements but not of
the same order as those seen for general tree-metrics. We also test the
centroid, median and ward linkage methods for raw input metric data, but given
that these methods requires the input metric to be Euclidean we could not
combine them with HyperAid. Nevertheless, their results are significantly
worse than those offered by our framework and thus not included in Table 1.

###  6.2. Real-world datasets

We examine the effectiveness of our HyperAid framework on five standard
datasets from the UIC Machine Learning repository (Dua and Graff, 2017). We
use $1-$cosine similarities as the raw input metrics. The results are listed
in Table 2.

One can see that the HyperAid framework again consistently and significantly
improves the performance of all downstream methods (reaching gains in excess
of $120\%$). Surprisingly, we find that average linkage, the best ultrametric
fitting method, achieves smaller $\ell_{2}$ norm losses on the Spambase
dataset when compared to tree-metric methods like NJ. We conjecture two
possible explanations: 1) We have not explored more powerful tree-metric
reconstruction methods like T-REX. Again, the reason for not being able to
make full use of T-REX is the fact that the software requires interactive data
loading and processing; 2) The optimal tree-metric is very close to an
ultrametric. It is still worth pointing out that despite the fact that the
ultrametric fits have smaller loss than tree-metric fits, even in the former
case HyperAid consistently improved all tested algorithms on real-world
datasets.

###  6.3. Ablation study

While minimizing the $\ell_{2}$ loss in the encoding process of the HyperAid
framework is an intuitively good choice given that our final tree-metric fit
is evaluated based on the $\ell_{2}$ loss, it is still possible to choose
other objective functions (such as the Dasguptas loss) for the encoder module.
We therefore compare the performance of the hyperbolic metric learned using
HypHC, centered on the Dasgupta objective, with the performance of our
HyperAid encoder coupled with several possible decoding methods. For HypHC, we
used the official implementation and hyperparameters provided by the authors
(Chami et al., 2020). The results are listed in Table 3 in the Supplement. The
results reveal that minimizing the $\ell_{2}$ loss during hyperbolic embedding
indeed offers better results than those obtained by using the Dasgupta loss
when our ultimate performance criterion is the $\ell_{2}$ loss. Note that the
default decoding rule of HypHC produces unweighted trees and hence offers
worse performance than the tested mode (and the results are therefore omitted
from the table).

###  6.4. Tree visualization and analysis

One conceptually straightforward method for evaluating the quality of the
hierarchical clustering is to use the ground truth labels of object classes
available for real-world datasets such as Zoo and Iris.

The Zoo dataset comprises $7$ classes of the animal kingdom, including
insects, cartilaginous and bony fish, amphibians, reptiles, birds and mammals.
The hierarchical clusterings based on NJ, HyperAid+NJ and HypHC reveal that
the first and last method tend to misplace amphibians and bony fish as well as
insects and cartilaginous fish by placing them in the same subtrees. The NJ
method also shows a propensity to create “path-like trees” which do not
adequately capture known phylogenetic information (e.g., for mammals in
particular). On the other hand, HyperAid combined with NJ discriminates
accurately between all seven classes with the exception of two branches of
amphibian species.

The Iris dataset includes three groups of iris flowers, Iris-setosa, Iris-
versicolor and Iris-virginica. All three methods perfectly identify the
subtrees of Iris-setosa species, but once again the NJ method produces a
“path-like tree” for all three groups which does not conform to nonlinear
models of evolution. It is well-known that it is hard to distinguish Iris
versicolor and Iris virginica flowers as both have similar flower color and
growth/bloom times. As a result, all three methods result in subtrees
containing intertwined clusters of flowers from both groups.

Table 2. The $\ell_{2}$ norm loss of the resulting trees (see the caption of Table 1 for the format description). In addition, we use $\delta^{\star}$ to indicate that the $\delta$ value is approximated by random sampling of one million quadruples of leaves. NA refers to “not applicable”. Note that the first four decoders produce tree-metrics while the remaining produce ultrametrics. |  Zoo, $n=101$, EL$=7.85$ |  Iris, $n=150$, EL$=15.64$ |  Glass, $n=214$, EL$=27.58$ |  Segmentation, $n=2310$, EL$=248.40$ |  Spambase, $n=4601$, EL$=255.22$ | Average Gain (%)
---|---|---|---|---|---|---
|  | Direct
---
($\delta=0.349$)
| HyperAid
---
($\delta=0.048$)
Gain (%) |  | Direct
---
($\delta=0.489$)
| HyperAid
---
($\delta=0.062$)
Gain (%) |  | Direct
---
($\delta=0.453$)
| HyperAid
---
($\delta=0.044$)
Gain (%) |  | Direct
---
($\delta^{\star}=0.389$)
| HyperAid
---
($\delta^{\star}=0.133$)
Gain (%) |  | Direct
---
($\delta^{\star}=0.234$)
| HyperAid
---
($\delta^{\star}=0.065$)
Gain (%) |
NJ | 11.77 |  [HTML]EFEFEF8.99 | 30.94 | 43.85 |  [HTML]EFEFEF18.17 | 141.22 | 60.96 |  [HTML]EFEFEF30.76 | 98.15 | 856.47 |  [HTML]EFEFEF 292.78 | 192.53 | 1008.6 |  [HTML]EFEFEF377.93 | 166.87 | 125.94
TreeRep | 14.65 |  [HTML]EFEFEF9.32 | 57.12 | 22.59 |  [HTML]EFEFEF19.00 | 18.89 | 71.81 |  [HTML]EFEFEF32.00 | 124.41 | 1357.28 |  [HTML]EFEFEF1038.98 | 30.64 | 2279.31 |  [HTML]EFEFEF927.02 | 145.87 | 75.38
NJ(T-REX) | 8.85 |  [HTML]EFEFEF8.59 | 3.09 | 26.38 |  [HTML]EFEFEF16.96 | 55.51 | 37.61 |  [HTML]EFEFEF29.58 | 27.11 | NA | NA | NA | NA | NA | NA | 28.57
UNJ(T-REX) | 8.60 |  [HTML]EFEFEF 8.57 | 0.31 | 17.47 |  [HTML]EFEFEF 16.86 | 3.58 | 29.41 |  [HTML]EFEFEF 29.38 | 0.09 | NA | NA | NA | NA | NA | NA | 1.33
single | 34.53 |  [HTML]EFEFEF17.17 | 101.11 | 84.66 |  [HTML]EFEFEF65.97 | 28.33 | 95.91 |  [HTML]EFEFEF52.82 | 81.55 | 1174.95 |  [HTML]EFEFEF924.76 | 27.06 | 1809.83 |  [HTML]EFEFEF1109.75 | 63.08 | 60.23
complete | 20.78 |  [HTML]EFEFEF10.64 | 95.27 | 58.13 |  [HTML]EFEFEF30.95 | 87.80 | 88.19 |  [HTML]EFEFEF37.75 | 133.61 | 928.63 |  [HTML]EFEFEF486.31 | 90.96 | 1248.15 |  [HTML]EFEFEF633.70 | 96.96 | 100.92
average | 10.04 |  [HTML]EFEFEF 9.17 | 9.47 | 23.38 |  [HTML]EFEFEF 22.99 | 1.68 | 31.94 |  [HTML]EFEFEF 30.79 | 3.73 | 339.41 |  [HTML]EFEFEF 300.07 | 13.11 | 365.78 |  [HTML]EFEFEF 350.68 | 4.31 | 6.46
weighted | 12.08 |  [HTML]EFEFEF11.05 | 9.33 |  [HTML]EFEFEF27.20 | 29.07 | -6.42 | 34.75 |  [HTML]EFEFEF34.16 | 1.74 | 458.17 |  [HTML]EFEFEF337.75 | 35.66 | 385.37 |  [HTML]EFEFEF382.13 | 0.84 | 8.22
Ufit | 10.53 |  [HTML]EFEFEF9.35 | 12.70 | 26.02 |  [HTML]EFEFEF23.02 | 13.03 | 33.21 |  [HTML]EFEFEF31.04 | 6.98 | 354.66 |  [HTML]EFEFEF314.08 | 12.92 | 381.68 |  [HTML]EFEFEF377.67 | 1.06 | 9.34

###### Acknowledgements.

The work was supported by the NSF CIF program under grant number 19566384.

## References

  * (1)
  * Abraham et al. (2007) Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Venugopalan Ramasubramanian, and Kunal Talwar. 2007.  Reconstructing approximate tree metrics. In _Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing_. 43–52.
  * Agarwala et al. (1998) Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup. 1998.  On the approximability of numerical taxonomy (fitting distances by tree metrics).  _SIAM J. Comput._ 28, 3 (1998), 1073–1085.
  * Ahmadian et al. (2019) Sara Ahmadian, Vaggos Chatziafratis, Alessandro Epasto, Euiwoong Lee, Mohammad Mahdian, Konstantin Makarychev, and Grigory Yaroslavtsev. 2019.  Bisect and conquer: Hierarchical clustering via max-uncut bisection.  _arXiv preprint arXiv:1912.06983_ (2019).
  * Ailon and Charikar (2005) Nir Ailon and Moses Charikar. 2005.  Fitting tree metrics: Hierarchical clustering and phylogeny. In _46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05)_. IEEE, 73–82.
  * Alon et al. (2020) Noga Alon, Yossi Azar, and Danny Vainstein. 2020.  Hierarchical clustering: a 0.585 revenue approximation. In _Conference on Learning Theory_. PMLR, 153–162.
  * Atteson (1997) Kevin Atteson. 1997\.  The performance of neighbor-joining algorithms of phylogeny reconstruction. In _International Computing and Combinatorics Conference_. Springer, 101–110.
  * Boc et al. (2012) Alix Boc, Alpha Boubacar Diallo, and Vladimir Makarenkov. 2012\.  T-REX: a web server for inferring, validating and visualizing phylogenetic trees and networks.  _Nucleic acids research_ 40, W1 (2012), W573–W579.
  * Bonnabel (2013) Silvere Bonnabel. 2013\.  Stochastic gradient descent on Riemannian manifolds.  _IEEE Trans. Automat. Control_ 58, 9 (2013), 2217–2229.
  * Buneman (1974) Peter Buneman. 1974\.  A note on the metric properties of trees.  _Journal of combinatorial theory, series B_ 17, 1 (1974), 48–50.
  * Chami et al. (2020) Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. 2020.  From trees to continuous embeddings and back: Hyperbolic hierarchical clustering.  _arXiv preprint arXiv:2010.00402_ (2020).
  * Chami et al. (2019) Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. 2019\.  Hyperbolic graph convolutional neural networks. In _Advances in Neural Information Processing Systems_. 4868–4879.
  * Charikar and Chatziafratis (2017) Moses Charikar and Vaggos Chatziafratis. 2017.  Approximate hierarchical clustering via sparsest cut and spreading metrics. In _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 841–854.
  * Charikar et al. (2019) Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh. 2019\.  Hierarchical clustering better than average-linkage. In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 2291–2304.
  * Chien et al. (2021) Eli Chien, Chao Pan, Puoya Tabaghi, and Olgica Milenkovic. 2021\.  Highly Scalable and Provably Accurate Classification in Poincaré Balls. In _2021 IEEE International Conference on Data Mining (ICDM)_. IEEE, 61–70.
  * Chierchia and Perret (2020) Giovanni Chierchia and Benjamin Perret. 2020.  Ultrametric fitting by gradient descent.  _Journal of Statistical Mechanics: Theory and Experiment_ 2020, 12 (2020), 124004.
  * Cho et al. (2019) Hyunghoon Cho, Benjamin DeMeo, Jian Peng, and Bonnie Berger. 2019\.  Large-margin classification in hyperbolic space. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 1832–1840.
  * Coenen et al. (2019) Andy Coenen, Emily Reif, Ann Yuan, Been Kim, Adam Pearce, Fernanda Viégas, and Martin Wattenberg. 2019.  Visualizing and measuring the geometry of BERT.  _arXiv preprint arXiv:1906.02715_ (2019).
  * Cohen-Addad et al. (2021) Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, and Mikkel Thorup. 2021\.  Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor.  _arXiv preprint arXiv:2110.02807_ (2021).
  * Dasgupta (2016) Sanjoy Dasgupta. 2016\.  A cost function for similarity-based hierarchical clustering. In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_. 118–127.
  * Dress (1984) Andreas WM Dress. 1984\.  Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces.  _Advances in Mathematics_ 53, 3 (1984), 321–402.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Farach et al. (1995) Martin Farach, Sampath Kannan, and Tandy Warnow. 1995\.  A robust model for finding optimal evolutionary trees.  _Algorithmica_ 13, 1 (1995), 155–179.
  * Ganea et al. (2018) Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. 2018\.  Hyperbolic neural networks. In _Advances in Neural Information Processing Systems_. 5345–5355.
  * Gascuel et al. (1997) Olivier Gascuel et al. 1997\.  Concerning the NJ algorithm and its unweighted version, UNJ.  (1997).
  * Gromov (1987) Mikhael Gromov. 1987\.  Hyperbolic groups.  In _Essays in group theory_. Springer, 75–263.
  * Harb et al. (2005) Boulos Harb, Sampath Kannan, and Andrew McGregor. 2005\.  Approximating the best-fit tree under l p norms.  In _Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques_. Springer, 123–133.
  * Hess and De Moraes Russo (2007) Pablo N Hess and Claudia A De Moraes Russo. 2007\.  An empirical test of the midpoint rooting method.  _Biological Journal of the Linnean society_ 92, 4 (2007), 669–674.
  * Hewitt and Manning (2019) John Hewitt and Christopher D Manning. 2019.  A structural probe for finding syntax in word representations. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. 4129–4138.
  * Kochurov et al. (2020) Max Kochurov, Rasul Karimov, and Serge Kozlukov. 2020\.  Geoopt: Riemannian Optimization in PyTorch.  arXiv:2005.02819 [cs.CG]
  * Krioukov et al. (2010) Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. 2010.  Hyperbolic geometry of complex networks.  _Physical Review E_ 82, 3 (2010).
  * Linial et al. (1995) Nathan Linial, Eran London, and Yuri Rabinovich. 1995\.  The geometry of graphs and some of its algorithmic applications.  _Combinatorica_ 15, 2 (1995), 215–245.
  * Liu et al. (2019) Qi Liu, Maximilian Nickel, and Douwe Kiela. 2019\.  Hyperbolic graph neural networks. In _Advances in Neural Information Processing Systems_. 8230–8241.
  * Macaluso et al. (2021) Sebastian Macaluso, Craig Greenberg, Nicholas Monath, Ji Ah Lee, Patrick Flaherty, Kyle Cranmer, Andrew McGregor, and Andrew McCallum. 2021\.  Cluster Trellis: Data Structures & Algorithms for Exact Inference in Hierarchical Clustering. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 2467–2475.
  * Monath et al. (2019) Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. 2019.  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_. 714–722.
  * Moseley and Wang (2017) Benjamin Moseley and Joshua R Wang. 2017.  Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_.
  * Murtagh (1984) Fionn Murtagh. 1984\.  Complexities of hierarchic clustering algorithms: state of the art.  _Computational Statistics Quarterly_ 1, 2 (1984), 101–113.
  * Nickel and Kiela (2017) Maximillian Nickel and Douwe Kiela. 2017.  Poincaré embeddings for learning hierarchical representations.  _Advances in neural information processing systems_ 30 (2017), 6338–6347.
  * Nickel and Kiela (2018) Maximillian Nickel and Douwe Kiela. 2018.  Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In _International Conference on Machine Learning_. PMLR, 3779–3788.
  * Papadopoulos et al. (2015) Fragkiskos Papadopoulos, Rodrigo Aldecoa, and Dmitri Krioukov. 2015\.  Network geometry inference using common neighbors.  _Physical Review E_ 92, 2 (2015).
  * Sahoo et al. (2020) Roshni Sahoo, Ines Chami, and Christopher Ré. 2020.  Tree Covers: An Alternative to Metric Embeddings. In _Differential Geometry for Machine Learning Workshop at NeurIPS_.
  * Saitou and Nei (1987) Naruya Saitou and Masatoshi Nei. 1987.  The neighbor-joining method: a new method for reconstructing phylogenetic trees.  _Molecular biology and evolution_ 4, 4 (1987), 406–425.
  * Sala et al. (2018) Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. 2018\.  Representation tradeoffs for hyperbolic embeddings. In _International Conference on Machine Learning_ , Vol. 80. PMLR, 4460–4469.
  * Sarkar (2011) Rik Sarkar. 2011\.  Low distortion delaunay embedding of trees in hyperbolic plane. In _International Symposium on Graph Drawing_. Springer, 355–366.
  * Shimizu et al. (2021) Ryohei Shimizu, YUSUKE Mukuta, and Tatsuya Harada. 2021\.  Hyperbolic Neural Networks++. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=Ec85b0tUwbA
  * Sonthalia and Gilbert (2020) Rishi Sonthalia and Anna C Gilbert. 2020.  Tree! i am no tree! i am a low dimensional hyperbolic embedding.  _arXiv preprint arXiv:2005.03847_ (2020).
  * Tabaghi et al. (2021) Puoya Tabaghi, Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenković. 2021.  Linear Classifiers in Product Space Forms.  _arXiv preprint arXiv:2102.10204_ (2021).
  * Tifrea et al. (2019) Alexandru Tifrea, Gary Becigneul, and Octavian-Eugen Ganea. 2019\.  Poincaré GloVe: hyperbolic word embeddings. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=Ske5r3AqK7
  * Ungar (2008) Abraham A Ungar. 2008\.  _Analytic hyperbolic geometry and Albert Einstein’s special theory of relativity_.  World Scientific.
  * Väisälä (2005) Jussi Väisälä. 2005\.  Gromov hyperbolic spaces.  _Expositiones Mathematicae_ 23, 3 (2005), 187–231.
  * Vermeer (2005) J Vermeer. 2005\.  A geometric interpretation of Ungar’s addition and of gyration in the hyperbolic plane.  _Topology and its Applications_ 152, 3 (2005), 226–242.
  * Wareham (1993) HT Wareham. 1993\.  On the complexity of inferring evolutionary trees.  _Technical Report Technical Report_ 9301 (1993).
  * Waterman et al. (1977) Michael S Waterman, Temple F Smith, Mona Singh, and William A Beyer. 1977.  Additive evolutionary trees.  _Journal of theoretical Biology_ 64, 2 (1977), 199–213.
  * Wheeler (2009) Travis J Wheeler. 2009\.  Large-scale neighbor-joining with NINJA. In _International Workshop on Algorithms in Bioinformatics_. Springer, 375–389.
  * Yu and De Sa (2019) Tao Yu and Christopher M De Sa. 2019.  Numerically accurate hyperbolic embeddings using tiling-based models.  _Advances in Neural Information Processing Systems_ 32 (2019).
  * Yu and De Sa (2021) Tao Yu and Christopher M De Sa. 2021.  Representing Hyperbolic Space Accurately using Multi-Component Floats.  _Advances in Neural Information Processing Systems_ 34 (2021).

##  Appendix A Proof of Proposition 4.1

###### Proposition A.1.

The objective in Problem 4.2 is a convex function of the edge weights of the
tree $T$.

###### Proof.

The objective in Problem 4.2 can be written as

$\min_{A_{T}\in\mathcal{A},w\in\mathbb{R}^{2n-2}_{+}}\|A_{T}w-d\|_{p}$

where $\mathcal{A}$ is the set of admissible linear operators that map edge
weights to additive pairwise distances on a binary tree with $N$ leaves. Let
$f(w)=\|A_{T}w-d\|_{p}$. For a $\lambda\in[0,1]$, we have

$\displaystyle f(\lambda w+(1-\lambda)v)$ $\displaystyle=\|\lambda
A_{T}w+(1-\lambda)A_{T}v-d\|_{p}$
$\displaystyle=\|\lambda(A_{T}w-d)+(1-\lambda)(A_{T}v-d)\|_{p}$
$\displaystyle\leq\lambda\|A_{T}w-d\|_{p}+(1-\lambda)\|A_{T}v-d\|_{p}$
$\displaystyle\leq\lambda f(w)+(1-\lambda)f(v).$

This result follows from the convexity of the $\ell_{p}$ norm for $p\geq 1$. ∎

##  Appendix B Proof of $\delta\times\sqrt{c}=\mathrm{const}$

###### Theorem B.1.

$\delta\times\sqrt{c}=\mathrm{const}$.

###### Proof.

Let us define a one-to-one map
$\phi:\mathbb{B}_{1}^{d}\rightarrow\mathbb{B}_{c}^{d}$, where
$\phi(x)=\frac{1}{\sqrt{c}}x$. The Gromov hyperbolicity of the Poincaré ball
is finite (Väisälä, 2005) and it scales linearly with the pairwise distances;
see Definition 3.2. Since
$d\big{(}\phi(x),\phi(y)\big{)}=\frac{1}{\sqrt{c}}d(x,y)$ for all
$x,y\in\mathbb{B}_{1}^{d}$, the Gromov hyperbolicity of $\mathbb{B}_{c}^{d}$
equals $\mathrm{const.}\times\frac{1}{\sqrt{c}}$. ∎

##  Appendix C Additional experiment details

###  C.1. Detailed description of the encoder

We implemented our framework in Python. The encoder part is developed in
Pytorch, and is a modification based on the official implementation of
HypHC222https://github.com/HazyResearch/HypHC.

Training details.  Note that all hyperparameters of each dataset are described
in our implementation. Here, we briefly describe the most important ones. All
the hyperparameters are tuned based on the loss of Hyp+NJ. Note that since we
are solving a search problem, this is a standard approach – for combinatorial
search algorithms, one usually reports the best loss for different random
seeds. HypHC also report the best loss results over several random seeds
(Chami et al., 2020).

When training hyperbolic embeddings in the Poincaré model, we follow the
suggestion stated in (Nickel and Kiela, 2017). We initialize the embeddings
within a small radius `1e-6` with small learning rate for a few (`burnin`)
epochs, then increase the learning rate by a `burnin_factor`. We also tune the
negative curvature `c` for different datasets. As mentioned in the main text,
although choosing larger `c` makes the resulting hyperbolic metric more
similar to the tree-metric (i.e. $\delta$ becomes smaller based on the
relation $\delta\times\sqrt{c}=\mathrm{const}$), it can make the optimization
process harder and can potentially cause numerical issues. For synthetic
datasets, we find that scaling the input metric by a factor `scaling_factor`
during training (and scale it back before decoding) can help with improving
the final results. We conjecture that this is due to the numerical precision
issues associated with hyperbolic embeddings approaches for which the
resulting points are close to the boundary of Poincaré ball. We use Riemannian
Adam implemented by the authors of HypHC as our optimizer.

###  C.2. Detailed description of the decoder

For NJ and TreeRep, we use the implementation from the TreeRep
paper333https://github.com/rsonthal/TreeRep. We manually interact with the
T-REX website444www.trex.uqam.ca for NJ-TREX and UNJ-TREX. For linkage-based
methods, we use the scipy
library555https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html.
For UFit, we use the official
implementation666https://github.com/PerretB/ultrametric-fitting along with
default hyperparameters.

Remarks. The NJ implementation, which is based on the PhyloNetworks
library777http://crsl4.github.io/PhyloNetworks.jl/latest in Julia, is a naive
version of the method. It is known from the literature that such versions of
NJ can potentially produce negative edge
weights888https://en.wikipedia.org/wiki/Neighbor_joining/#Advantages_and_disadvantages.
In the naive version of NJ, one simply replaces the negative edge-weights by
$0$. On the other hand, a more sophisticated cleaning approach is implemented
in T-REX, which is the reason why the T-REX version offers better performance.
Note that TreeRep is also known to have the negative edge-weights problem,
where the naive correction (replacing them with $0$) was adopted by the
authors (Sonthalia and Gilbert, 2020).

###  C.3. Additional results

Figure 7. Visualization of resulting trees for Glass. Vertex colors indicate the ground truth labels. Table 3. The $\ell_{2}$ losses of resulting trees generated as part of the ablation study pertaining to methods for generating hyperbolic embeddings. | Zoo | Iris | Glass
---|---|---|---
| HyperAid | HypHC | HyperAid | HypHC | HyperAid | HypHC
NJ |  [HTML]EFEFEF11.77 | 31.55 |  [HTML]EFEFEF18.18 | 70.43 |  [HTML]EFEFEF30.76 | 87.75
TreeRep |  [HTML]EFEFEF14.65 | 28.51 |  [HTML]EFEFEF19.00 | 64.61 |  [HTML]EFEFEF32.00 | 80.31
single |  [HTML]EFEFEF34.53 | 45.01 |  [HTML]EFEFEF65.97 | 85.40 |  [HTML]EFEFEF52.83 | 108.44
complete |  [HTML]EFEFEF20.78 | 24.01 |  [HTML]EFEFEF30.96 | 59.60 |  [HTML]EFEFEF37.75 | 69.54
average |  [HTML]EFEFEF10.05 | 33.31 |  [HTML]EFEFEF23.00 | 72.36 |  [HTML]EFEFEF30.79 | 90.58
weighted |  [HTML]EFEFEF12.09 | 32.97 |  [HTML]EFEFEF29.07 | 71.00 |  [HTML]EFEFEF34.16 | 87.15
Ufit |  [HTML]EFEFEF10.54 | 33.07 |  [HTML]EFEFEF23.03 | 73.19 |  [HTML]EFEFEF31.04 | 90.34

Tree visualization for the Glass dataset. Clustering results obtained for the
Glass dataset comprising seven classes of material are hardest to interpret,
as all three methods only accurately cluster tableware glass. HypAid appears
to better delineate between building-windows glass that is float-processed
from building-windows glass that is nonfloat-processed.