Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Authors: Max van Spengler
Pascal Mettes
Venue: ICML 2025 poster (2025)
Keywords: Hyperbolic Geometry
Hyperbolic Tree Embeddings
Representation Learning
Hierarchical Learning
Primary area: general_machine_learning->representation_learning
TL;DR: In this paper we propose a method for embedding trees in hyperbolic space by optimizing hyperspherical point separation and using floating point expansion arithmetic for maintaining GPU-compatibility.

Abstract: Embedding tree-like data, from hierarchies to ontologies and taxonomies, forms a well-studied problem for representing knowledge across many domains. Hyperbolic geometry provides a natural solution for embedding trees, with vastly superior performance over Euclidean embeddings. Recent literature has shown that hyperbolic tree embeddings can even be placed on top of neural networks for hierarchical knowledge integration in deep learning settings. For all applications, a faithful embedding of trees is needed, with combinatorial constructions emerging as the most effective direction. This paper identifies and solves two key limitations of existing works. First, the combinatorial construction hinges on finding highly separated points on a hypersphere, a notoriously difficult problem. Current approaches achieve poor separation, degrading the quality of the corresponding hyperbolic embedding. We propose highly separated Delaunay tree embeddings (HS-DTE), which integrates angular separation in a generalized formulation of Delaunay embeddings, leading to lower embedding distortion. Second, low-distortion requires additional precision. The current approach for increasing precision is to use multiple precision arithmetic, which renders the embeddings useless on GPUs in deep learning settings. We reformulate the combinatorial construction using floating point expansion arithmetic, leading to superior embedding quality while retaining utility on accelerated hardware.

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Max van Spengler'
Pascal Mettes
Abstract
ral language (Miller, 1995; Tifrea et al., 2018; Yang et al., 2016), social networks (Freeman, 2004), visual understand- ing (Desai et al., 2023; Van Spengler et al., 2023; Pal et al., 2025) and more. To obtain faithful embeddings, Euclidean space is ill-equiped; even simple trees lead to high distor- tion (Sonthalia & Gilbert, 2020). On the other hand, the exponential nature of hyperbolic space makes it a natural geometry for embedding trees (Nickel & Kiela, 2018). This insight has led to rapid advances in hyperbolic learning, with superior embedding (Sala et al., 2018) and clustering (Chami et al., 2020) of tree-like data.
Embedding tree-like data, from hierarchies to on- tologies and taxonomies, forms a well-studied problem for representing knowledge across many domains. Hyperbolic geometry provides a natu- ral solution for embedding trees, with vastly su- perior performance over Euclidean embeddings. Recent literature has shown that hyperbolic tree embeddings can even be placed on top of neu- ral networks for hicrarchical knowledge integra- tion in deep learning settings. For all applica- tions, a faithful embedding of trees needed, with combinatorial constructions emerging the most effective direction. This paper identifies and solves two key limitations of existing works. First, the combinatorial construction hinges on finding highly separated points on a hypersphere, a no- toriously difficult problem. Current approaches achieve poor separation, degrading the quality of the corresponding hyperbolic embedding. We pro- pose highly separated Delaunay tree embeddings (HS-DTE), which integrates angular separation in a generalized formulation of Delaunay embed- dings, leading to lower embedding distortion. Sec- ond, low-distortion requires additional precision. The current approach for increasing precision is to use multiple precision arithmetic, which ren- ders the embeddings useless on GPUs in deep learning settings. We reformulate the combinato- rial construction using floating point expansion arithmetic, leading to superior embedding quality while retaining utility on accelerated hardware.
Recent literature has shown that hyperbolic tree embeddings are not only useful on their own, they also form powerful tar- get embeddings on top of deep networks to unlock hierarchi- cal representation learning (Peng et al., 2021; Mettes et al., 2024). Deep learning with hyperbolic tree embeddings has made it possible to effectively perform action recognition (Long et al., 2020), knowledge graph completion (Kolyvakis et al., 2020), hypernymy detection (Tifrea et al., 2018) and many other tasks in hyperbolic space. These early adop- tions of hyperbolic embeddings have shown a glimpse of the powerful improvements that hierarchically aligned rep- resentations can bring to deep learning.
The rapid advances in hyperbolic deep learning under- line the need for hyperbolic tree embeddings compati- ble with GPU accelerated software. Current tree em- bedding algorithms can roughly be divided in two cate- gories; optimization-basel and constructive methods. The optimization-basel methods, e.g. Poincaré embeddings (Nickel & Kiela, 2017), hyperbolic entailment cones (Ganea et al., 2018), and distortion optimization (Yu et al., 2022b), train embeddings using some objective function based on the tree. While these approaches are flexible due to minimal assumptions, the optimization can be unstable, slow and result heavily distorted embeddings. Conversely, con- structive methods traverse a tree once, placing the children of each node on a hypersphere around the node's 's embedding (Sarkar, 2011; Sala et al., 2018). These methods are fast, require no hyperparameter tuning and have great error guar- antees. However, they rely on hyperspherical separation, a notoriously difficult problem (Saff & Kuijlaars, 1997), and on multiple precision floating point arithmetic, which incompatible with GPUs and other accelerated hardware.
1. Introduction
Tree-like structures such as hierarchies are key for knowl- edge representation, from biological taxonomies (Padial al., 2010) and phylogenetics (Kapli al., 2020) to natu-
'VIS Lab, University of Amsterdam, The Netherlands. Corre- spondence to: Max van Spengler <m. www.w.vanssengler@uw..... @u....
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Our goal is embed trees in hyperbolic space with mini- mal distortion yet with the ability operate on accelerated GPU hardware even when using higher precision. We do so in two steps. First, we outline HS-DTE, a new gen- eralization of Delaunay tree embeddings (Sarkar, 2011) to arbitrary dimensionality through hyperspherical separa- tion. Second, we propose HypFPE, a floating point ex- pansion arithmetic approach enhance our constructive hyperbolic tree embeddings. We develop new routines for computing hyperbolic distances on floating point expan- sions and outline how to use these on hyperbolic embed- dings. Furthermore, we provide theoretical results demon- strating the effectiveness of these floating point expansion routines. Floating point expansions allow for higher preci- sion similar to multiple precision arithmetic. However, our routines can be implemented using standard floating point operations, making these compatible with GPUs. Experi- ments demonstrate that HS-DTE generates higher fidelity embeddings than other hyperbolic tree embeddings and that HypFPE further increases the embedding quality for HS- DTE and other methods. The code will be made avail- able at sttps://git:nn com/ maxvanspenglerr/ saarrbolicctrreeeebbeeee
errors. This distance represents the length of the straight line or geodesic between and y with respect to the Rie- mannian metric g". Geodesics of the Poincaré ball are Euclidean straight lines through the origin and circular ares perpendicular to the boundary of the ball.
We will use some isometries of hyperbolic space, as these conveniently allow for moving embeddings around with- out changing pairwise distances, keeping the distortion unaffected. More specifically, we will use reflections in geodesic hyperplanes. A geodesic hyperplane is an (n 1)- dimensional manifold consisting of all geodesics through some point x E D which are orthogonal to a normal geodesic through x or, equivalenty, orthogonal to some normal tangent vector v E Tx For the Poincaré ball these are the Euclidean hyperplanes through the origin and the (n diddmeensional hyperspherical caps which are per- pendicular to the boundary of the ball. We will denote geodesic hyperplane by H Reflection in geodesic hyperplane Ho,v through the origin can be defined as in Euclidean space, so as a Householder transformation
RH (y) = (In - --2v2 Jy,
(5)
where ||vl| = 1. Reflection in the other type of geodesic hyperplane is a spherical inversion:
2. Preliminaries and Related Work
2.1. Hyperbolic Geometry Preliminaries
,2
RH (y) = m +
m);
(6)
yy
m
To help explain existing constructive hyperbolic embedding algorithms and our proposed approach, we outline the most important hyperbolic functions here. For a more thorough overview, we refer to (Cannon al., 1997; Anderson, 2005). Akin (Nickel & Kiela, 2017; Ganea al., 2018; Sala et al., 2018), we focus on the Poincaré ball model of hyperbolic space. For n-dimensional hyperbolic space, the Poincaré ball model is defined as the Riemannian manifold (ID", s²), where the manifold and Riemannian metric are defined as
with m E RR, 0 the center and radius of the hyper- sphere containing the geodesic hyperplane. We will denote reflection mapping some point x E ID" to another point y E DD by Rx-y-- The specific formulations and deriva- tions of the reflections that we use are in Appendix A.
2.2. Related Work
Hyperbolic tree embedding algorithms. Existing em- bedding methods can be divided into two categories: optimization- methods and constructive methods. The optimization methods typically use the tree to define some loss function and use a stochastic optimization method such as SGD to directly optimize the embedding of each node, e.g. Poincaré embeddings (Nickel & Kiela, 2017), hyper- bolic entailment cones (Ganea et al., 2018) and distortion optimization (Sala et al., 2018; Yu et al., 2022b). Poincaré embeddings use a contrastive loss where related nodes are pulled together and unrelated nodes are pushed apart. Hyper- bolic entailment cones attach an outwards radiating cone to each node embedding and define loss that forces children of nodes into the cone of their parent. Distortion optimiza- tion directly optimizes for distortion loss to embed node pairs. Such approaches are flexible, but do not lead to arbi- trarily low distortion and optimization is slow. Constructive methods are either combinatorial methods (Sarkar, 2011;
||x|| < 1}. 11 fx E R"
2
(1)
g" Axdn:
I- ||=||
Using this model of hyperbolic space, we can compute distances between x, E D either as
||x 1
dx -cosh- -1 (1+2 (1 [1 - 111)2)
(2)
or as
yx = 2tanh -1 ((l x|
(3)
where
(1 + 2(x, y) + |y 12 x (1
| 2 y
x ① y
(4)
y(x + | P 2
is the Möbius addition operation. These formulations are theoretically equivalent, but suffer from different numerical
2

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Sala et al., 2018) or eigendecomposition methods (Sala et al., 2018). Combinatorial methods first place the root of tree at the origin of the hyperbolic space and then traverse down the tree, iteratively placing nodes as uniformly as possible on a hypersphere around their parent. (Sarkar, 2011) 1) pro- poses a 2-dimensional approach, where the points have to be separated on a circle; trivial task. For higher dimensions, (Sala et al., 2018) place points on a hypereube inscribed within hypersphere, which leads to suboptimal distribu- tion. We also follow constructive approach, where we use an optimization method for the hyperspherical separa- tion, leading to significantly higher quality embeddings. The cigendecomposition method h-MDS (Sala et al., 2018) takes a graph or tree metric and uses an eigendecomposition of the corresponding distance matrix to generate low-distortion embeddings. However, it collapses nodes within some sub- trees to single point, leading to massive local distortion.
proposed over the years with improved error guarantees (Joldes et al., 2014; 2015; Muller et al., 2016). In this pa- per, we build upon the most recent arithmetic framework detailed in (Popescu, 2017). We have implemented this framework for PyTorch and extend its functionality to work with hyperbolic embeddings.
3. HS-DTE
Setting and objective. We are given (possibly weighted) tree T = (V, E), where the nodes in V contain the concepts of our hierarchy and the edges in E' represent parent-child connections. The goal is to find an embedding Φ : V + Th' that accurately captures the semantics of the tree T, so where T can be accurately reconstructed from (VV). An embedding is evaluated by first defining the graph metric dr, v) on the tree as the length of the shortest path between the nodes u and v and then checking how much & distorts this metric. More specifically, for evaluation we use the average relative distortion (Sala et al., 2018), the worst-case distortion (Sarkar, 2011) and the mean average precision (Nickel & Kiela, 2017). Further details on these metrics can be found in Appendix B.
Deep learning with hyperbolic tree embeddings. In computer vision, a wide range of works have recently shown the potential and effectiveness of using a hyperbolic em- bedding space (Khrulkov et al., 2020). Specifically, hier- archical prior knowledge can be embedded in hyperbolic space, after which visual representations can be mapped to the same space and optimized to match this hierarchical organization. (Long et al., 2020) show that such a setup improves hierarchical action recognition, while (Liu al., 2020) use hierarchies with hyperbolic embeddings for zero- shot learning. Deep visual learning with hyperbolic tree embeddings has furthermore shown to improve image seg- mentation (Ghadimi Atigh et al., 2022), skin lesion recogni- tion (Yu et al., 2022b), video understanding (Li et al., 2024), hicrarchical visual recognition (Ghadimi Atigh et al., 2021: Dhall et al., 2020), hierarchical model interpretation (Gul- shad et al., 2023), open set recognition (Dengxiong & Kong, 2023), continual learning (Gao et al., 2023), few-shot learn- ing (Zhang et al., 2022), and more. Since such approaches require freedom in terms of embedding dimensionality, they commonly rely on optimization- based approaches to embed the prior tree-like knowledge. Similar approaches have also been investigated other domains, from audio (Petermann et al., 2023) and text (Dhingra et al., 2018; Le et al., 2019) to multimodal settings (Hong et al., 2023). In this work, we provide a general- purpose and unconstrained approach for low-distortion embeddings with the option to scale to higher precisions without losing GPU-compatiiility
Constructive solution for hyperbolic embeddings. The starting point of our method is the Poincaré ball implementa- tion of Sarkar's 's combinatorial construction (Sarkar, 201 1) as outlined by (Sala et al., 2018). A generalized formulation of this approach is outlined in Algorithm 1. The scaling factor T >> 0 used to scale the tree metric dy. larger allows for a better use of the curvature of hyperbolic space, theo- retically making it easier find low-distortion embeddings. Lower values can help avoid numerical issues that arise near the boundary of the Poincaré ball. When the dimension of the embedding space satisfies n S log(A + 1 and the scaling factor is set to
1 + C log (4)(T)=+t).
T
with A(T') the maximal degree of T', then the construction leads to a worst-case distortion bounded by 1 + c, given that the points on the hypersphere are sufficiently uniformly distributed (Sala et al., 2018). When the dimension is n > log( ((T)) + 1, the scaling factor should be T 2(1) to achieve this bound on the distortion, so it can no longer be reduced by choosing a higher dimensional embedding space (Sala et al., 2018). The number of bits required for the construction is O 1 & log(A(T)) when n S ()T()()T)) +1 and O when > log ((()) + 1, where is the longest path in the tree.
Floating point expansions. Floating point expansions (FPEs) to increase precision in hyperbolic space was pro- posed by (Yu & De Sa, 2021) and implemented in a PyTorel library (Yu et al., 2022a). However, their methodology is based on older FPE arithmetic definitions and routines by (Priest, 1991; 1992; Richard Shewchuk, 1997). In the field of FPEs, more efficient and stable formulations have been
The difficulty of distributing points on a hypersphere. The construction in Algorithm 1 provides a nice way of con- structing embeddings in n-dimensional hyperbolic space
3

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Algorithm 1 Generalized Sarkar's Delaunay tree embedding
Delaunay tree embeddings with separation. We propose to improve the construction by distributing the points on the hypersphere in step 6 of Algorithm 1 through optimiza- tion. Specifically, we use projected gradient descent to find E 5 such that
1: Input: Tree T (V, and scaling factor T >> O.
2: for V do
3: p p-rent((())
4: cI,..., Gdeg(e)-1 + children(v)
X1, x1,-..;Xp
5: Reflect (p) with R
X1 X = arg min L(WI..... W&), W1 Wi. E Sa-1
6: Generate X1,... ())g(v) uniformly distributed points
on a hypersphere with radius 1
7: Get rotation matrix A such that (o()))((((p))) is
1) + E is some objective function. Com- mon choices for this objective are the hyperspherical energy functions (Liu et al., 2018), given by
where L: (S
aligned with Axdeg(u) and rotate
8: Scale points by e*+1
=--1
9: Reflect rotated and scaled points back: o(c)) +
(7xxxx)))) i i= -....... deg(v)
W. wyll
>>> 0,
10:
end for
E, (W1...... Wx) =
k Σ f
log
8 = 0,
with arbitrarily low distortion. However, the bound the distortion for the in Equation 7 is dependent on our ability to generate uniformly distributed points on the n- dimensional hypersphere. More specifically, given gener- ated points xI....,XA XA(T), the error bound relies on the assumption that
(10)
where is nonnegative integer parameterizing this set of functions. Minimizing these objective functions pushes the hyperspherical points apart, leading to a more uniform dis- tribution. However, these objectives are aimed at finding a large mean pairwise angle, allowing for the possibility of having small minimum pairwise angle. Having small minimum pairwise angle leads to the corresponding nodes and their descendants being placed too close together, lead- ing to large distortion, as shown in the experiments. There- fore, we advocate the minimal angle maximization (MAM) objective, aimed at maximizing this minimal angle
min sin (xx, 2 A(T)- (S)
(8)
While this assumption can theoretically always be achieved (Sala et al., 2018), generating points that actually satisfy it is not straightforward. In practice it is important to keep the scaling factor 7 as small as possible, since the required number of bits increases linearly with т. Increasing the minimal angle beyond the condition in Equation 8 allows for a smaller T. This problem of maximizing the minimal pairwise angle is commonly known the Tammes problem (Tammes, 1930; Mettes et al., 2019) and it has been studied extensively, with many analytical and approximate solutions given for various specific combinations of dimensions n and number of points that have to be placed (Cohn, 2024). However, there exists no general closed-fome solution that encompasses all possible combinations.
k
E(W1..... W&)
Σ
min <(w, W2); (11) sf1
which pushes each wt away from its nearest neighbour and essentially optimizes directly for the objective of the Tammes problem. We find that this method results in strong separation in terms of the minimal pairwise angle when compared to highly specialized existing methods used for specific cases of the Tammes problem (Cohn, 2024). More importantly, it leads to better separation than the method used in current hyperbolic embeddings (Sala al., 2018), allowing for the use of smaller т. Moreover, this opti- mization method places no requirements on the dimension, making it a suitable choice for downstream tasks. We refer to the resulting construction as the highly separated Delau- nay tree embedding (HS-DTE).
(Sala et al., 2018) propose to generate points by placing them on the vertices of an inscribed hypercube. This ap- proach comes with three limitations. First, the maximum number of points that can be generated with this method is 2n, which is limited for small n. Second, for most config- urations this method results in a sub-optimal distribution, leading to an unnecessarily high requirement on r. Third, this method depends finding binary sequences of length n with maximal Hamming distances (see Appendix C), which is in general not an easy problem to solve. Their solution is to use the Hadamard code. This can only be used when the dimension is a power of 2 and at least A(T): a severe restriction, often incompatible with downstream tasks.
When performing the construction using MAM, the output of the optimization can be cached and reused each time node with the same degree is encountered. Using this approach, the worst-case number of times that a solution to equation 9 has to be found is O (VNN) as shown by Theorem 3.
Theorem 3.1. The worst-case number of optimizations p that has to be performed when embedding a tree with the
4

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
combinatorial construction in Algorithm I with any objec- tive using caching is
point expansion f consists of. Each term f4 is in the form of GPU supported float format, such as float16, float32 or float64, Moreover, to ensure that this representation is unique and uses bits efficiently. it is constrained to be ulp- nonoverlapping (Popescu, 2017).
p 2 + VI6N -15)
(12)
Proof. See Appendix D.
Definition 4.1. A floating point expansion f fo is ulp-nonoverlapping if for all 2 < i S t, [il S (up(Si-1)) where ulp(fi-1) is the unit in the last place of fi-1-
In practice we find the number of optimizations to be lower due to frequent occurrence of low degree nodes for which cached points can be used, as shown in Appendix L.
A ulp-nonoverlapping FPE consisting of terms each with b bits precision has at worst ((b 1) + 1 bits of precision, since exactly - overlapping bits can occur. The corre- sponding arithmetic requires completely different routines for computing basic operations, many of which have been introduced by (Joldes et al., 2014; 2015; Muller et al., 2016; Popescu, 2017). An overview of these routines can be found in Appendix N. For an overview of the error guarantees we refer to (Popescu, 2017). Each of these routines can be de- fined using ordinary floating point operations that exist for tensors in standard tensor libraries such as PyTorch, which are completely GPU compatible. Here, we have general- ized all routines to tensor operations and implemented them in PyTorch by adding an extra dimension to each tensor containing the terms of the floating point expansion.
MAM optimization details. MAM is an easily optimizable objective, that we train using projected gradient descent for 450 iterations with learning rate of 0.01, reduced by a factor of 10 every 150 steps, for every configuration. This optimization can generally be performed in mere seconds which, if necessary, could be further optimized through hy- perparameter configurations, early stopping, parallelization or hardware acceleration. As a result, the increase in com- putation time of our method compared to (Sala et al., 2018) minimal. Moreover, when compared to methods such as Poincaré embeddings (Nickel & Kiela, 2017) which use stochastic gradient descent to directly optimize the embed- dings, we find that our method is orders of magnitude faster, while avoiding the need for costly hyperparameter tuning.
Applying FPEs to the construction. In the constructive method the added precision is warranted whenever numer- ical errors lead to large deviations with respect to the hy- perbolic metric. In other words, if we have some x D and its floating point representation X. then it makes sense to increase the precision if
4. HypFPE: High-precision GPU-compatible Hyperbolic Embeddings
While hyperbolic space enjoys numerous potential bene- fits, it is prone to numerical error when using floating point arithmetic. Especially as points move away from the origin, floating point arithmetic struggles to accurately represent or perform computations with these points. For larger values of 7 or maximal path lengths f, the embeddings generated by the construction often end up in this problematic region of the Poincaré ball. As such, the precision required for hyperbolic embeddings is often larger than the precision provided by the floating point formats supported on GPUs Increased precision can be attained by switching to arbi- trary precision arithmetic. However, this makes the result incompatible with existing deep learning libraries.
dx x) >> O.
(14)
For the Poincaré ball, this is the case whenever x lies some- where close to the boundary of the ball. In our construction, this means that generation and rotation of points on the unit hypersphere can be performed in normal floating point arithmetic, since the representation error in terms of de will be negligible. However, for large т, the scaling of the hy- persphere points and the hyperspherical inversion require increased precision as these map points close to the bound- ary of ID". Specifically, steps 5, 8 and 9 of Algorithm may require increased precision. Note that these operations can be performed using the basic operation routines shown in Appendix N. From the basic operations, more complicated nonlinear operations can be defined through the Taylor se- ries approximations that are typically used for floating point arithmetic. To compute the distortion of the resulting em- beddings, the distances between the embedded nodes must be computed either through the inverse hyperbolic cosine formulation of Equation or through the inverse hyper- bolic tangent formulation of Equation 3. We show how to accurately compute distances using either formulation.
Here, we propose HypFPE, method to increase the preci- sion of constructive hyperbolic approaches through floating point expansion (FPE) arithmetic. In this framework, num- bers are represented as unevaluated sums of floating point numbers, typically of a fixed number of bits In other words, a number f IR is represented by a floating point expansion f as
(13)
where the f are floating point numbers with a fixed number of bits and where is the number of terms that the floating
5

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
4.1. The Inverse Hyperbolic Cosine Formulation
Theorem 4.4. Given a udp-nonoverlapping FPE x
Ei=1 zi E [-1 + d cd-1] consisting of floating point numbers with precision b > t, Algorithm 13 leads to an approximation y of the inverse hyperbolic tangent of
For Equation 2, normal floating point arithmetic may cause the denominator inside the argument of cosh to become O due to rounding. To solve this, we can use FPE arithmetic to compute the argument of cosh 1 and then approximate the distance by applying cosh to the largest magnitude term of the FPE. This allows accurate computation of distances even for points near the boundary of the Poincaré ball, as shown by Theorem 4.2 and Proposition 4.3.
that, for small e" > 0, satisfies
1 - -annh (x))
(16)
Proof. See Appendix G.
Theorem 4.2. Given x, Y E DD with |x|| <1-<'~ and ||yll < 1 - E an approximation d to equation 2 can be computed with FPE representations with terms and with a largest magnitude approximation to cosh such that, for some small E² > O,
Proposition 4.5. The range of algorithm 13 increases lin- early in the number of terms t.
Proof. See Appendix H.
Based on these results, either formulation could be good choice for computing distances with FPEs. In practice, we find that the tanh -1 formulation leads to larger numerical errors, which is likely due to catastrophic cancellation errors in the dot product that is performed in Equation 4. Therefore, we use the cosh formulation in our experiments.
||x y
)
d dochsh-1 -1 1+2 (1 X 11 1113))
<< (15)
Proof. See Appendix E.
Proposition 4.3. The range of the inverse hyperbolic tan- gent formulation increases linearly in the number of terms of the FPEs being used.
5. Experiments
5.1. Ablations
Proof. See Appendix F.
Minimal angle maximization. To test how well the pro- posed methods for hyperspherical separation perform, generate points wi...., W on an 8-dimensional hyper- sphere for various numbers of points k and compute the minimal pairwise angle min;y, <(w;, wj). We compare to the Hadamard generation method from (Sala et al., 2018) and the method that is used in their implementation, which precomputes 1000 points using the method from (Lovisolo & Da Silva, 2001) and samples from these precomputed points. Note that a power of 2 is chosen for the dimension to be able to make a fair comparison to the Hadamard con- struction, since this method cannot be used otherwise. The results are shown in Figure la. These results show that our MAM indeed leads to high separation in terms of the min- imal pairwise angle, that the precomputed approach leads to poor separation and that the Hadamard method only per- forms moderately well when the number of points required is close to the dimension of the space.
Theorem 4.2 shows that we can accurately compute dis- tances on larger domain than with normal floating point arithmetic. Proposition 4.3 shows that the effective radius of the Poincaré ball in which we can represent points and compute distances increases linearly in the number of terms of our FPE expansions. Therefore, this effective radius in- creases linearly with the number of bits. The same holds for arbitrary precision floating point arithmetic, so FPE ex- pansions require similar number of bits for constructive methods arbitrary precision floating point arithmetic.
4.2. The Inverse Hyperbolic Tangent Formulation
For Equation 3, the difficulty lies in the computation of tanh -1 With normal floating point arithmetic, due to rounding errors, this function can only be evaluated on [-1 + e, - e]. where e is the machine precision. This severely limits the range of values, i.e., distances, that we can compute. Therefore, we need to be able to compute the inverse hyperbolic tangent with FPEs. Inspired by (Felker & musl Contributors, 2024), we propose new routine for this computation, given in Algorithm 13 of Appendix N. Here, we approximate the logarithm in steps 7 and 9 as log(f) s log(fi). which is accurate enough for our pur- poses. This algorithm can be used to accurately approximate tanh 1 while extending the range linearly in the number of terms i as shown by Theorem 4.4 and Proposition 4.5.
To verify that this minimal pairwise angle is important for the quality of the construction, we perform the construc- tion on a binary tree with a depth of 8 edges using each of the hypersphere generation methods. The construction is performed in 10 dimensions except for the Hadamard method, since this cannot generate 10 dimensional points, Additional results for dimensions 4, 7 and 20 are shown in Appendix I. Each method is applied using float32 represen- tations and a scaling factor of = 1.33. The results are shown in Table These findings support our hypothesis
6

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
2018) and the combinatorial method with Hadamard (Sala et al., 2018) or precomputed hyperspherical points (Lovi- solo & Da Silva, 2001). For the constructive methods and for h-MDS, a larger scaling factor improves performance, so we use T = 5. For DO we find that increasing the scaling factor does not improve performance, so we use t = 1.0. PE and HEC are independent of the scaling factor.
Table Comparing hyperspherical separation methods for the constructive hyperbolic embedding of binary tree with a depth of edges when using float32 representations (24 bits precision) in 10 dimensions. Note that the Hadamard method (1) cannot be applied in 10 dimensions, so there is used instead.
Method
dim
Dave
D uce
MAP
(Sala et al., 2018)
8
0.734
1143
0.154
The results on the various trees in 10 dimensions are shown in table 2 and additional results for dimensions 4, 7 and 20 are shown in Appendix J. These illustrate the strength of the combinatorial constructions. The optimization methods PE, HEC and DO perform relatively poor for all evalua- tion metrics. This performance could be increased through hyperparameter tuning and longer training. However, the results will not come close to those of the other methods. The h-MDS method performs well in terms of Dave. but very poorly on Dwc and MAP. This is because h-MDS col- lapses leaf nodes, leading to massive local distortion within the affected subtrees. However, between subtrees this dis- tortion is much smaller, explaining the low Dave. Figure illustrates the issue with h-MDS and the superiority of our approach. Each of the white squares in the h-MDS plot corresponds to a collapsed subtree, which renders the em- beddings unusable for downstream tasks since nearby leaf nodes cannot be distinguished. We conclude that HS-DTE obtains the strongest embeddings overall.
(Sala et al., 2018)
10
0.361
18.42
0.998
Eo
10
0.219
1.670
1.000
Ei
10
0.204
1.686
1.000
Es
0.190
1.642
1.000
MAM
10
0.188
1.635
1.000
that the minimal pairwise angle is important for generating high quality embeddings and that the MAM is an excellent objective function for performing the separation.
FPEs versus standard floating points. To demonstrate the importance of using FPEs for increasing precision, perform the construction on phylogenetic tree pressing the genetic heritage of mosses in urban envi- ronments (Hofbauer et al., 2016), made available by (Sanderson et al., 1994), using various precisions. This tree has a maximum path length = 30, which imposes sharp restrictions on the value of r that we can choose before encountering numerical errors. We perform the construction either with normal floating point arithmetic using the usual GPU-supported float formats or with FPEs, using multiple float64 terms. The scaling factor is chosen to be close to the threshold where numerical problems appear in order to obtain optimal results for the given precision. The results in terms of Dine are shown in Figure 1b. As can be seen from these results, around 100 bits of precision are needed to obtain decent results, which can be achieved using FPEs with 2 float64 terms. Without FPE expansions, the largest GPU-compatible precision is 53 bits, obtained by using float64. This precision yields a Dwe of 9.42, which is quite poor. These results illustrate the importance of FPEs for high quality GPU-compatible embeddings.
5.3. Embedding Phylogenetic Trees
Lastly, we compare hyperbolic embeddings on phyloge- netic trees. Moreover, we show how adding HypFPE to our method and the other combinatorial methods increases the embedding quality when requiring GPU-compatibility. The phylogenetic trees describe mosses (Hofbauer et al., 2016), weevils (Marvaldi et al., 2002), the European car- nivora (Roquet et al., 2014), and lichen (Zhao et al., 2016), obtained from (McTavish et al., 2015). The latter two trees are weighted trees which can be embedded by adjusting the scaling in step 8 of Algorithm 1. Fach of the embeddings is performed in 10-dimensional space. Other dimensions are given in Appendix K. The h-MDS method and the combina- torial constructions are performed with the largest r that can be used with the given precision. The results are shown in Table 3. When using float64, HS-DTE outperforms each of the optimization-bate approaches from (Sala et al., 2018). While h-MDS obtains high average distortion, it collapses entire subtrees, leading to massive local distortion. Therefore, the HS-DTE embed- dings are of the highest quality. When adding HypFPE on top of the combinatorial approaches, all performances go up, with the combination of HS-DTE and HypFPE leading to the best performance on both Dave and D Additional results on graph-like data are shown in Appendix M.
5.2. Embedding Complete m-ary Trees
To demonstrate the strong performance of the combinato- rial constructions compared to other methods, we perform embeddings on several complete m-ary trees with a max path length of f 8 and branching factors m 3,5, 7. Due to the small f, each experiment can be performed with normal floating point arithmetic using float64 representa- tions. We compare our method with Poincaré embeddings (PE) (Nickel & Kiela, 2017), hyperbolic entailment cones (HEC) (Ganea et al., 2018), distortion optimization (DO) (Sala et al., 2018; Yu et al., 2022b), h-MDS (Sala et al.,
methods and the other combinatorial
7

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
bltaktts Roatle
Minimal painwise angle (rad)
Hadamard Precomputed
Worst-case distortion D
3.0
Roat32
2.5
E2
MAM
foaas4
1.5
0.5
Flosttl
4 Flcass
15
18
21
50
100
300
350
400
Number points
Precision (bits)
(a) Minimal hyperspherical energy ablation.
(b) Floating point expansion ablation.
construction and floating point expansion. (a) Minimal pairwise angle (f) of the hyperspherical points generated in step of Algorithm using various generation methods. dimension the space set to 8, so the Hadamard method cannot generate distortion (L. Dw.) of the constructed embedding the phylogenetic tree with the maximal admissable given the number of bits. The vertical dashed line shows the limit with standard GPU floating point formats (float64). The horizontal dashed line the best possible result wwc
Figure 1. Ablation studies
than 8 points. The MAM objective consistently leads higher separation angle. (b) The worst-case
1. FPE representations are required to get high quality embeddings without losing GPU-compatibllit..
Acknowledgements
Max van Spengler gratefully acknowledges the University of Amsterdam Data Science Centre for financial support.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
0.0
0.2
0.4
0.6
0.8
1.0
References
Figure 2. Pairwise relative distortions of h-MDS (left) and HS- DIE (right) applied to the 5-ary tree with a scaling factor r = 5.0. Axes are ordered using breadth-first search of the tree. Embeddings ohtained with h-MDS suffer from leaf node collapse.
Abraham, Balakrishnan, M., Kuhn, F,, Malkhi, D., Rama- subramanian, V., and Talwar, K. Reconstructing approx- imate tree metrics. In Proceedings of the twenty-sixth anmual ACM symposium on Principles of distributed com- puting, pp. 43-52, 2007.
6. Conclusion
In this paper introduce HS-DTE, novel way of construc- tively embedding trees in hyperbolic space, which uses optimization approach to effectively separate points on a hy- persphere. Empirically, we show that HS-DTE outperforms existing methods, while maintaining the computational effi ciency of the combinatorial approaches. We also introduce HypFPE, framework for floating point expansion arith- metic on tensors, which is adapted to extend the effective be used
Anderson, J. W. Hyperbolic Geometry. Springer Undergrad- uate Mathematics Series. Springer, London, 2nd edition, 2005. ISBN 978-1-85233-934440
Cannon, W., Floyd, W. J., Kenyon, R., Parry, W. R., et al. Hyperbolic geometry. Flavors of geometry, 31(59-115): 2, 1997.
Chami, Gu, A., Chatziafratis, V., and Ré, C. From trees continuous embeddings and back: Hyperbolic hierar- chical clustering. Advances Neural Information Pro- cessing Systems, 33:15065-15076 2020.
radius of the Poincaré ball. This framework to increase the precision of computations, while benefiting from hardware acceleration, paving the way for highly accu- rate hyperbolic neural networks. It can be added on top of any of the combinatorial methods, leading to distoortoion and GPU-compatible hyperbolic tree embeddings.
Cohn, Table spherical codes, 2024. URL https: / //hal handle net. 1/153543.
8

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Table Comparison hyperbolic embedding algorithms on m-ary frees with a maximum path length l' The h-MDS method is represented by i. The $ method is the combinatorial construction with the hyperspherical points being generated using the Hadamard construction, whereas the x method samples hyperspherical points from the precomputed points generated with the hyperspherical separation method from (Lovisolo & Da Silva, 2001). The h-MDS method outperforms the other methods in terms of Dove, but collapses nodes, leading to NaN values of the Dwe and making the embeddings unusable. AS-DTE has the second best Dave and outperforms all methods in terms of Dwe. Each combinatorial construction has perfect MAP.
3-tree
5-tree
7-tree
Dave
D
MAP
Dave
Dwe
MAP
D aav
Dwe
MAP
(Nickel & Kiela, 2017)
0.17
169
0.8
0.31
NaN
0.58
0.84
NaN
0.24
(Ganea et al., 2018)
0.51
184
0.27
0.81
604
0.24
0.96
788
0.15
(Yu et al., 2022b)
0.16
31.9
0.57
0.52
545
0.30
0.93
3230
0.05
(Sala et al., 2018) f
0.03
NaN
0.52
0.04
NaN
0.1
0.03
NaN
0.05
(Sala et al., 2018) $
0.11
1.14
1.00
0.12
1.14
1.00
0.12
1.14
1.00
(Sala et al., 2018) *
0.09
1.18
1.00
0.13
1.30
1.00
0.13
1.31
1.00
HS-DTE
0.06
1.07
1.00
0.09
1.09
1.00
0.10
1.12
1.00
Table Comparison hyperbolic embedding algorithms on various trees. f represents h-MDS, & the construction with Hadamard hyperspherical points and * the construction with points sampled from a set precomputed with (Lovisolo & Da Silva, 2001). The best float64 performance is underlined and the best FPE performance is in bold. All embeddings are performed in a 10-dimensional space. Hadamard generation cannot be used for the mosses tree, since it has A(T) greater than 8. Distortion optimization (Yu et al., 2022b) does not converge for the lichen tree due to large variation in edge weights. Overall, combining HypFPE and HS-DTE works best.
Precision bits
Mosses
Weevils
Carnivora
Lichen
Dane
me
Dane
Dee
Dace
Dwc
Dane
Dae
(Nickel & Kiela, 2017)
53
0.68
44350
0.45
NaN
0.96
NaN
151
NaN
(Ganea el al., 2018)
53
0.90
1687
0.77
566
0.99
NaN
162
NaN
(Yu al., 2022b)
53
0.83
163
0.57
79.8
0.99
NaN
(Sala al., 2018)
53
0.04
NaN
0.06
NaN
0.11
NaN
0.13
NaN
(Sala al., 2018)
53
0.79
330
0.26
35.2
0.49
79.6
(Sala al., 2018)
0.78
122
0.54
34.3
0.23
0.55
HS-DTE
53
0.40
9.42
0.27
2.03
0.12
11.7
0.30
23.5
HypFPE + (Sala et al., 2018)
417
0.07
1.09
0.05
6.76
0.12
43.4
HypFPE (Sala al., 2018)*
417
0.08
1.14
0.05
1.11
0.03
4.87
0.11
6.42
HypFPE + HS-DTE
417
0.04
1.06
0.03
1.04
0.03
2.03
0.05
3,30
De Nooy, W., Mrvar, A., and Batagelj, V. Exploratory so- cial network analysis with Pajek: Revised and expanded edition for updated software, volume 46. Cambridge university press, 2018
M., and Krause, A. Hierarchical image classification using entailment cone embeddings. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pp. 836 837, 2020.
Dengxiong, X. and Kong, Y. Ancestor search: General- ized open set recognition via hyperbolic side information learning. In Proceedings of the IEEE/CVF Winter Confer- ence on Applications of Computer Vision, pp. 4012-4012, 2023.
Dhingra, B., Shallue, C., Norouzi, M., Dai, A., and Dahl, G. Embedding text hyperbolic spaces. Proceedings of the Twelfth Workshop on Graph- Based Methods for Natural Language Processing, pp. 59 69, 2018.
Felker, R. and musl Contributors. musl libe: A lightweight implementation of the standard library for linux systems, 2024. URL https: /wwsl.u.....mmm////mmmmmmmmm.m.m iatuusl.iiii lib...bc.... org. Version 1.2.5, retrieved on September 30, 2024.
Desai, K., Nickel, M., Rajpurohit, T., Johnson, J., and Vedantam, S. R. Hyperbolic image-text representations. In International Conference on Machine Learning, pp- 7694 7731. PMLR, 2023.
Freeman, L. The development of social network analysis. Study in the Sociology of Science, 1(687):159-161) 2004.
Dhall, A., Makarova, A., Ganea, O., Pavllo, D., Greeff,

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Ganea, O., Bécigneul, G., and Hofmann, T. Hyperbolic entailment cones for learning hierarchical embeddings. In International conference machine learning, pp. 1646- 1655. PMLR, 2018.
Khrulkov, V., Mirvakhabova, L.,, Ustinova, E., Oseledets, I., and Lempitsky, V. Hyperbolic image embeddings. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 6418-646666 18886,,,,888 2020.
Gao, 7., Xu, C.,, Li, F., Jia, Y., Harandi, M., and Wu, Y. Exploring data geometry for continual learning. In Pro- ceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 24325- 24334, 2023.
Kolyvakis, P., Kalousis, A., and Kiritsis, D. Hyperbolic knowledge graph embeddings for knowledge base com- pletion. In The Semantic Web: 17th International Con- ference, ESWC 2020, Heraklion, Crete. Greece, May 31-June 4, 2020, Proceedings 17, pp. 199- 219. Springer, 2020.
Ghadimi Atigh, M., Kelser-Ressel, M., and Mettes, P. Hyper- bolic busemann learning with ideal prototypes. Advances in neural information processing systems, 34:103-115, 2021.
Le, M., Roller, S., Papaxanthos, L.,, Kiela, D., and Nickel, M. Inferring concept hierarchies from text corpora via hy- perbolic embeddings. arXiv preprint 102.01192..00113 2019.
Ghadimi Atigh, M., Schoep, J., Acar, E., Van Noord, N., and Mettes, P. Hyperbolic image segmentation. In Pro- ceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 4453 4462,446,,222 2022.
Li, Y.-L.., Wu, X., Liu, X., Wang. Z., Dou, Y., Ji, Y., Zhang, J., Li, Y., Lu, X., Tan, J., et al. From isolated islands to pangea: Unifying semantic space for human action understanding. Proceedings of the IEEF/CVF Confer- ence on Computer Vision and Pattern Recognition, pp. 16582-16592, 2024.
Goh, K.-I., Cusick, M. E., Valle, D., Childs, B., Vidal, M.. and Barabási, A.-L. The human disease network. Proceedings of the National Academy of Sciences, 104 (21):685586690 2007.
Liu, S., Chen, J., Pan, L.,, Ngo, C.-W., Chua, T.-S., and Jiang, Y.-G. Hyperbolic visual embedding learning for zero-shot recognition. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 9273-9281, 2020.
Gulshad, S., Long, T., and van Noord, N. Hierarchical explanations for video action recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3703-3708, 2023.
Hofbauer, W. K., Forrest, L. L., Hollingsworth, P. M., and Hart, M. L. Preliminary insights from dna barcoding into the diversity of mosses colonising modern building surfaces. Bryophyte Diversity and Evolution, 38(1):1-22, 2016.
Liu, W., Lin, R., Liu, Z., Liu, L., Yu, Z., Dai, B., and Song, L. Learning towards minimum hyperspherical energy. Advances in neural information processing systems, 31, 2018.
Long, T., Mettes, P., Shen, H. T., and Snock, G. Search- ing for actions on the hyperbole. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 1141-1150, 2020.
Hong, J.. Hayder, Z., Han, J., Fang, P., Harandi, M., and Petersson, L. Hyperbolic audio-visual zero-shot learning. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 7873-7883, 2023.
Lovisolo, L. and Da Silva, F. Uniform distribution of points on a hyper-sphere with applications to vector bit bit-plane encoding. IEE Proceedings- Vision, Image and Signal Processing, 148(3):187-19) 2001.
Joldes, M., Muller, J.-M., and Popescu, V. On the computa- tion of the reciprocal of floating point expansions using an adapted NewtonnRRahhee iteration. In 2014 IEEE 25th International Conference Application-Sppe -Seecffic Systems, Architectures and Processors, pp. 63-67. IEEE, 2014.
Mac Williamms and Sloane. The theory of error-correcting codes. Elsevier Science Publishers BV google schola, 2: 47, 1977.
Joldes, M., Marty, O., Muller, J.-M., and Popescu, V. Arith- metic algorithms for extended precision using floating- point expansions. IEEE Transactions on Computers, 65 14):1197-1210, 2015.
Marvaldi, A. E., Sequeira, A. S., O'Brien, C. W., and Far- rell, B. D. Molecular and morphological phylogenetics of weevils (coleoptera, cureulionoidaa): do niche shifts accompany diversification? Systematic biology, 51(5): 761-785, 2002.
Kapli, P., Yang, Z., and Telford, M. J. Phylogenetic tree building in the genomic age. Nature Reviews Genetics, 21 (7))222 444, 2020.
McTavish, E. J., Hinchliff, C. E., Allman, J. F., Brown, J. W., Cranston, K. A., Holder, M. T., Rees, A., and Smith,
10

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
S. A. Phylesystem: git-based data store for community- curated phylogenetic estimates. Bioinformatics, 317)) 2794-2800, 2015.
Priest, D. M. On properties of floating point arithmetics: numerical stability and the cost of accurate computations. University of California, Berkeley, 1992.
Mettes, P., Van der Pol, E., and Snoek, C. Hyperspherical prototype networks. Advances in neural information processing systems, 32, 2019.
Richard Shewchuk, J. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry, 18:305-200 1997.
Mettes, P. Ghadimi Atigh, M., Keller-Ressel, M., Gu, J., and Yeung, S. Hyperbolic deep learning in computer vision: A survey. International Journal of Computer Vision, pp. 1-25, 2024.
Roquet, C.,, Lavergne, S., and Thuille,, W. One tree to link them all: phylogenetic dataset for the european tetrapoda. PLoS currents, 6, 2014.
Saff, E. B. and Kuijlaars, A. B. Distributing many points on sphere. The mathematical intelligencer, 19:5-11, 1997.
Miller, G. A. Wordnet: lexical database for english. Com- munications of the ACM, 38(11):39-41) 1995.
Sala, F., De Sa, C., Gu, A., and Ré, C. Representation trade- offs for hyperbolic embeddings. In International Con- ference on Machine Learning. pp. 4460-4469, PMLR, 2018.
Muller, J.-M., Popescu, V., and Tang, T. P. A new multi- plication algorithm for extended precision using floating- point expansions. 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH), pp. 39-46. IEEE, 2016.
Sanderson, M. J.. Donoghue, M. J., Piel, W., and Eriksson, T. Treebase: a prototype database of phylogenetic analyses and an interactive tool for browsing the phylogeny of life. American Journal of Botany, 8 81(6):183, 1994.
Nickel, M. and Kiela, D. Poincaré embeddings for learning hierarchical representations. Advances in neural informa- tion processing systems, 30, 2017.
Nickel, M. and Kiela, D. Learning continuous hierarchies in the Lorentz model of hyperbolic geometry. In Interna- tional conference on machine learning, pp. 3779-3788. PMLR, 2018.
Sarkar, R. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, pp. 355-366 Springer, 2011.
Sonthalia, R. and Gilbert, A. Tree! am no tree! am a low
Padial, M., Miralles, A., Riva, I., and Vences, M. The integrative future of taxonomy. Frontiers in zoology, 7:1-14, 2010.
dimensional hyperbolic embedding. Advances Neural Information Processing Systems, 33:845-856, 2020.
Tammes, P. M. L. On the origin of number and arrange- ment of the places of exit on the surface of pollen-graing grains. Recueil des travaux botaniques néerlandais, 27(1):1-84, 1930.
Pal, A., van Spengler, M.. di Melendugno, G. M. D., Fla- borea, A., Galasso, F., and Mettes, P. Compositional en- tailment learning for hyperbolic vision-language models. International Conference on Learning Representations, 2025.
Tifrea, A., Bécigneul, G., and Ganea, O.-E. Poincaré glove: Hyperbolic word embeddings. arXiv preprint 1rX1v:1810.06546. 2018.
Peng, W., Varanka, T., Mostafa, A., Shi, H., and Zhao, G. Hyperbolic deep neural networks: A survey. IEEE Trans- actions on pattern analysis and machine intelligence, 44 100033002310044,, 2021.
Van Spengler, M., Berkhout, E., and Mettes, P. Poincaré resnet. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5419-5428, 2023.
Petermann, D., Wichern, G., Subramanian, A., and Le Roux, J. Hyperbolic audio source separation. In ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp- 1-5. IEEE, 2023.
Yang. Z., Yang, D., Dyer, C., He, X., Smola, A., and Hovy, E. Hierarchical attention networks for document classi- fication. In Proceedings of the 2016 conference of the North American chapter of the association for compu- tational linguistics: human language technologies, pp. 1480-1489, 2016.
Popescu, Towards fast and certified multiple-precision librairies. PhD thesis, Université de Lyon, 2017.
Yu, T. and De Sa, C. M. Representing hyperbolic space accu- rately using multi caatiicomponent floats. Advances in Neural Information Processing Systems, 14:15570-15533 2021.
Priest, D. M. Algorithms for arbitrary precision floating point arithmetic, University of California, Berkeley, 1991.

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Yu, T, Guo, W., Li, J. C., Yuan, T,, and De Sa, C. Mctensor: high-precision deep learning library with multi-component foating-point. arXiv preprint arXiv:2207.08867, 2022a.
Yu, Z., Nguyen, T., Gal, Y., Ju, L., Chandra, S. S., Zhang, L., Bonnington, P., Mar, V., Wang, Z., and Ge, Z. Skin lesion recognition with class-hierarchy regularized hyperbolic embeddings. In International conference on medical image computing and computer-assisted intervention, pp- 594-603. Springer, 2022b.
Zhang, B., Jiang, H., Feng, S., Li, X., Ye, Y., and Ye, R. Hyperbolic knowledge transfer with class hierarchy for few-shot learning. In IJCAI, pp. 3723-3729, 2022.
Zhao, X., Leavitt, S. D., Zhao, Z. T., Zhang, L. L., Arup, U., Grube, M., Pérez-Ortege S., Printzen, C., Sliwa, L., Kraichak, E., et al. Towards revised generic classifi- cation of lecanoroid lichens (lecanoraceae, ascomycota) based on molecular, morphological and chemical evi- dence. Fungal Diversity, 78:293-304, 2016.
12

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
A. Geodesic hyperplane reflections
In this paper we will make use reflections in geodesic hyperplanes through the origin to align points on a hypersphere centered the origin with some existing point on the hypersphere. More specifically, if we have points w, z D with |||] = ||/|| and we want to reflect w to 2, then we can use a Householder reflection with v = w[] so
Rw Rw) = In- 2(z w w) w)²
2 -11-2601
y.
(17)
w |
To see that this maps to z, we can simply enter w into this map to see that
Rw-sz(W) = 1, 2(z - w) - w)
w
(18)
Iz - w|1 wa/2
2((2, w) ||
w
||||| 2(z, w) + |w| 2 Zz w
(19)
| 2(z, w) + |w| 2 + W 112
||/112
w
||z|| 2(z, w) |w| 1
(z w)
(20)
|w|| ||z||
w +
1
(z w)
(21)
|
2(z, w)
w + z
(22)
We make use of reflections in geodesic hyperplanes not through the origin that reflect some given point w E ID' to the origin. This can be done through reflection in the hyperplane contained in the hypersphere with center m ||
w and
radius r
w|| We easily verify that this hyperspherical inversion maps w to the origin.
w
1w
2
(w)
|w|
1
||
W TW]p
W
|w] 11
(23)
W
|w|]
(1
||w/
|/w||
2
///ll
+
//w/
w
(24)
w
[w]
2
||
1
|w|
1
[w]] ||
w
(25)
W
(26)
| 2 [
To show that this is reflection in a geodesic hyperplane and, therefore, an isometry, we need to show that the hypersphere defined by m and r is orthogonal to the boundary of DD", This is the case when all the triangles formed by the line segments between O, m and any point v in the intersection of the hypersphere and the boundary of D are right triangles. This is exactly the case when the Pythagorean theorem holds for each of these triangles. For each v we have that ||v/| = 1 and ||v m||- r, so
V 0 + 1/v
m
1 1+ 2
(27)
(28)
|w| 1
(29)
| 4 [
0/1
(30)
which shows that the Pythagorean theorem holds and, thus, that this hyperspherical inversion is a geodesic hyperplane reflection. The fact that such a hyperspherical inversion in a geodesic hyperplane is an isometry is shown in, for example, (Anderson, 2005).
13

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
B. Evaluation metrics
The first one is the average relative distortion (Sala et al., 2018), given We will use two distortion based evaluation metrics. as
Σ (()((u),(())))) - dr (u, v)
D Dave( (Ø) NNN 1)
(31)
dr(u,2) v)
where N = |V| is the number of nodes. A low value for this metric is a necessary, but not sufficient condition for a high quality embedding, as it still allows for large local distortion. Therefore, we use second distortion based metric, the worst-case distortion (Sarkar, 201 1), given by
do dr(o(u).
do(o(u), ((1))) dr(u,e)
Due max uşo
min usfi
(32)
dr (u, v)
Dave ranges from 0 to infinity and Dwo ranges from to infinity, with smaller values indicating strong embeddings. A large Dave indicates a generally poor embedding, while a large Dw indicates that at least some part of the tree is poorly embedded. Both values should be close to their minimum if an embedding be used for a downstream task. Lastly, another commonly used evaluation metric for unweighted trees the mean average precision (Nickel & Kiela, 2017), given by
(v) ( (V(()no-(BBluu) (Bo(u,)))
M)
1 N
Σ WEV
Σ
(33)
deg(u)
0 (-((BB))))))
(a)
where deg(u) denotes the degree of u in T. (u) denotes the nodes adjacent to u in V and where Bb(u, v) C D denotes the closed ball centered at (uu) with hyperbolic radius ( ((v)), so which contains itself. The MAP reflects how well we can reconstruct neighborhoods of nodes while ignoring edge weights, making less appropriate for various downstream tasks.
C. Placing points on the vertices of hypercube
The discussion here is heavily based on (Sala et al., 2). We include it here for completeness. When placing a point on the vertex of an n-dimensional hypercube, there are 2n options, so each option can be represented by a binary sequence of length n. For example, on a hypercube where each vertex v has ||o|| 1. each vertex is of the form (#1..... +1)", so can represent as some binary sequence s. The distance between such vertices can then be expressed in terms of the Hamming distance between the corresponding sequences as
d(vi, 02) AdHamming (51, 82),
which shows that points placed on vertices of a hypercube are maximally separated if this Hamming distance is maximized. This forms an interesting and well studied problem in coding theory where the objective is to find & binary sequences of length which have maximal pairwise Hamming distances. There are some specific combinations of n and k for which optimal solutions are known, such the Hadamard code. However, for most combinations of n and the solution is still an open problem (Mac Williams & Sloane, 1977). Therefore, properly placing points on the vertices of hypereube currently relies on the solution to an unsolved problem, making it difficult in practice.
D. Proof of Theorem 3.1
Proof. For a tree T (V, F) with N [V. we know that the degrees of the vertices satisfy
Σ deg(v) 2| 2(N 1).
(34)
VEV
Suppose Wi.... Wp C Sn are the sets of points on the hypersphere generated by the p optimizations that need be to perform the construction, then W.| * [W,l, since we use the cached result whenever nodes have the same degree. Moreover, [W] is equal to the degree of the node for which the points are generated,
W S
Σ deg(v) = 2(N - 1).
(35)
VEV
14

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Given this constraint, the largest possible value of p is when fit many [Wl'ss I' in this sum possible, which is when [Wi.....: [Wpl 1, - p. In that case
P
p(p+1) 1)
W
Σ
S 2 1).
(36)
2
Solving for integer p yields
1 S (VI6N- - 15 1)}
(37)
Note that this bound can be sharpened slightly by observing that each node e with deg(v) > forces the existence of deg(v) 1 leaf nodes with degree However, the asymptotic behaviour remains (VNN).
E. Proof of Theorem 4.2
Theorem. Given x, DD with ||||| < 1 - e and ||y|| < 1 e approximation d to equation 2 can be computed with FPE representations with terms and with a largest magnitude approximation to cosh -1 such that
||x - yl?
d cosh -1
<c',
(38)
(1-1 (1-
for small
Proof. We begin by noting that the accuracy of the largest magnitude approximation to cosh depends on the underlying floating point algorithm used for computing the inverse hyperbolic cosine. While this function cannot be computed up to machine precision on its entire domain due to the large derivative near the lower end its domain, can still be computed quite accurately, i.e. there exists some small e > 0 such that
cosh (xx) - cosh (+) cosh-
< <ti,
(39)
where E RR, where R is the greatest representable number and T is the floating point approximation to so for which we have
T
<C
(40)
x
For example, in PyTorch when using float64, we have of 2.107 * 10-8, If we can approximate the argument inside cosh sufficiently accurately, then the largest magnitude approximation will be close enough guarantee small error. More specifically, let
x 1
2
(41)
x (1
13)
and let 3 3 + ... 2, with
[ for each ل j be the approximation to obtained through FPE arithmetic.
2c,
(42)
where e is the machine precision of the corresponding floating point format, then
1z 2115 21 +
(43)
< Dc + 2c/211
(44)
< 4<|2 2E/ 2/1b
(45)
15

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
where we that A ulp(21) e |.
that Σ
2e/2z]
Now, can rewrite that
2 ž1
4
8c.
(46)
2c
Therefore, by repeatedly using equation 39, we see that the largest magnitude approximation error is bounded by 16e Our ability to approximate the argument as precisely as in equation 42 using FPEs follows from the error bounds of the FPE arithmetic routines from (Popescu, 2017). This shows that the statement holds for =16ej.
F. Proof of Proposition 4.3
Proposition. The range of the inverse hyperbolic tangent formulation increases linearly in the number of terms of the FPEs being used.
Proof. When we use FPEs with t terms, we can represent points x, y E D such that ||x| = 1 - c- and ||yl| = c-
If we set -y- = x (1 - (1-e!_1 1,, O,.... 0)², then
x yll
(1- 6--
cosh -1 (1+ X 31 13)
cosh -1
(1 4 (1 (1 - 21-1)332
(47)
2 cosh -1
(48)
1e21-2
46 31-3 10-1
cosh -1
1
(49)
221-2
)
log
1 1+
2c2
+
2021
-
(50)
2 log
(51)
f-I
(1 t) log(e)
(52)
(t - 1)) log(e)),
(53)
which shows that we can compute a distance that is bounded from below by O(). Similar steps can be used to show that the distance is also bounded from above by (t) term
G. Proof of Theorem 4.4
Theorem. Given a ulp-nonoverlapping FPE = Ei x 11-1+ consisting of floating point numbers with precision > Algorithm 13 leads to approximation of the inverse hyperbolic tangent of that satisfies
yy - tanh -x)) E
(54)
for some small c* > 0.
Proof. The accuracy of the (-0.5, 0.5) branch of the algorithm follows easily from the accuracy of the algorithm for normal floating point numbers and the error bounds of the FPE routines from (Popescu, 2017). similar to the proof in Appendix E. The other branch can be a bit more problematic, due to the large derivatives near the boundary of the domain. For 0.5 < |x| < 1 1-1 we use
tanh (x) 0.5 sign(x) log (1
2|x|| [
(55)
Let denote the argument of the logarithm, so
2|Ø0
1 +
(56)
16

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
and let 2 + +... + & denote that approximation of obtained through FPE operations. Due to the error bounds given in 1 c²-1 we can assume that
(Popescu, 2017), for FPEs with / terms on the domain 0.5 I
|x]
<
2
< 2e,
(57)
|=|
where is the machine precision the floating point terms. Now, since |ž2| S ulp( = = we can write
2
31 S
+
(58)
S 2c/2| + 22
(59)
$ 26/2
2
(60)
$ 4
+ +2e/21 - 2//
(61)
which can be rewritten as
4e
2z - E1| S
|2| S 8e|=|
(62)
2
This shows that we can write žΙ = (1 5)2, with |6| Now, the error of the largest magnitude term approximation of the logarithm
0.5 sign(z) log(z)
0.5
(i) log((i) - 0.5 sign(x)) log(z)
(63)
0.5
log
(64)
21
0.5
log
(65)
[[+)]2)
8)2
0.5
log
(66)
0.5
log(1 5)]
(67)
S 0.5 [8]
(68)
< 4e.
(69)
Lastly, we introduce some error through the approximation of the natural logarithm. However, as long as no overflow occurs, this error is typically bounded by the machine precision. Therefore, if we can approximate well enough, then we can guarantee an accurate computation of tanh So combining this result with the error bounds from (Popescu, 2017) concludes the proof.
H. Proof of Proposition 4.5
Proposition. The range of algorithm 13 increases linearly in the number of terms t.
Proof. The maximal values that we can encounter occur near the boundary of the domain, so set r. = 1 - c-1 Then,
0.5 sign(x) log (1
2/x] 1 - |x|
0.5 log
1+
2 -1
(70)
ct-1
d-1 +2
< 0.5 log
(71)
c--
< 0.5 - log
(72)
c--
0.5 (1 (1-- 1) log(s))
(73)
= 0.5 (1 + (1 ( 1)] log ())
(74)
which shows that the range is bounded from above by O(t). A similar argument leads to a O(t) lower bound, showing that the range indeed increases linearly in the number of terms
17

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
I. Binary tree embedding results for varying dimensions
Table 4 shows results of the embedding of a binary tree with float32 representations 4, 7, 10 or 20 dimensions. Here, we have also tested an additional objective similar MAM, where we use the cosines of the angles instead of the angles. We find that MAM generally leads the best or close the best results for each choice of dimensions.
Table Comparing hyperspherical separation methods for the constructive hyperbolic embedding of binary with depth of 8 edges using float32 representations 4, 7, 10 or 20 dimensions. & uses Hadamard generated hypersphere points and uses precomputed points from (Lovisolo & Da Silva, 2001).
D Dave
D Dwo
10
20
10
20
(Sala et al., 2018)
0.734
0.734
0.734
0.734
1143
1143
1143
1143
Sala et al. (2018) *
0.235
0.502
0.361
0.726
10.51
132
18.42
280.5
Eo
0.192
0.188
0,219
0.189
1.655
1.625
1.670
1.640
Ei
0.190
0.196
0.204
0.190
1.619
1.664
1.686
1.698
E2
0.194
0.198
0.190
0.198
1.666
1.687
1.642
1.680
Cosine similarity
0.189
0.189
0.188
0.188
1.636
1.637
1.635
1.633
MAM
0.188
0.188
0.188
0.189
1.632
1.623
1.635
1.631
J. Embedding m-ary trees in varying dimensions
Tables 5 and 6 show results of the embedding of various m-ary trees in dimensions 4, 7, 10 and 20, similar to Table 2. We find that MS-DTE gives the best results overall.
Table Comparison of average distortion of hyperbolic embedding algorithms on m--ary trees with a maximum path length of t= 8. The h-MDS method is represented by The method the combinatorial construction with the hyperspherical points being generated using the Hadamard construction, whereas the method samples hyperspherical points from the precomputed points generated with the hyperspherical separation method from (Lovisolo higher dimensions, but collapses nodes, making the embeddings unusable. HS-DTE has the best performance for smaller dimensions and second best performance for larger dimensions.
Silva, 2001). The h- h-MDS method outperforms the other methods for
3-tree
5-tree
7-tree
D ave
4
10
20
7
10
20
4
7
10
20
(Sala al., 2018)
0.09
0.07
0.03
0.01
0.18
0.05
0.04
0.03
0.16
0.13
0.03
0.02
(Sala et al., 2018) $
0.11
0.11
0.11
0.11
0.12
0.12
0.12
0.12
(Sala al., 2018)
0.08
0.08
0.09
0.14
0.10
0.12
0.13
0.18
0.12
0.12
0.13
0.17
HS-DTE
0.06
0.06
0.06
0.06
0.09
0.09
0.09
0.09
0.10
0.10
0.10
0.10
K. Embedding phylogenetic trees in varying dimensions
Additional experiments involving the phylogenetic trees with embedding dimensions 4, 7, 10 and 20 shown in Tables 7, 8, 9 and 10. We observe that the precomputed points method struggles to separate points for higher dimensions, leading to higher distortion. Moreover, we find that HS-DTE gives the best results overall in every setting.
18

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Table Comparison worst-case distortion hyperbolic embedding algorithms on m--ary trees maximum path length l' = 8. The h h-MDS method is represented by The $ method is the combinatorial construction with the hyperspherical points being generated using the Hadamard construction, whereas method samples hyperspherical points from precomputed points generated with the hyperspherical separation method from (Lovisolo & Da Silva, 2001). HS-DTE has the best performance in all settings.
3-tree
5-rree
7-tree
Das
4
10
20
4
7
10
20
7
(Sala et al., 2018)
NaN
NaN
NaN
NaN
NaN
NaN
NaN
NaN
NaN
NaN
NaN
NaN
(Sala et al., 2018) $
1.14
1.14
1.14
1.14
1.14
1.14
1.14
1.14
(Sala et al., 2018)
1.32
1.22
1.18
1.23
1.28
1.30
1.30
1.34
1.53
1.25
1.31
1.26
HS-DTF
1.07
1.07
1.07
1.07
1.14
1.10
1.10
1.10
1.14
1.13
1.12
1.12
Table Comparison of average distortion of hyperbolic embedding algorithms the mosses and weevils trees. t represents the construction with Hadamard hyperspherical points and * the construction with points sampled from a set precomputed with (Lovisolo Da Silva, 2001). The hest performance is in hold. The embeddings are performed in 4, 10 20-dimensional space. Overall, find that HS-DTE works best.
Mosses
Weevils
D
4
7
10
20
4
7
10
20
HypFPE + (Sala et al., 2018)* $
0.09
0.07
0.07
HypFPE (Sala et al., 2018)> *
0.06
0.10
0.08
0.10
0.03
0.05
0.05
0.10
HypFPE HS-DTE
0.04
0.04
0.04
0.04
0.03
0.03
0.03
0.03
Table Comparison of average distortion of hyperbolic embedding algorithms the carnivora and lichen trees. represents the construction with Hadamard hyperspherical points and * the construction with points sampled from set precomputed with (Lovisolo & Da Silva, 2001). The best performance is bold. The embeddings are performed in 4, 7, 10 20-dimensional space. Overall, we find that HS-DTE works best.
Carnivora
Lichen
Dave
4
7
10
20
4
7
10
20
HypFPE + (Sala et al., 2018) $
0.04
0.04
0.04
0.04
0.12
0.12
0.12
0.12
HypFPE + (Sala et al., 2018)
0.01
0.03
0.03
0.06
0.05
0.10
0.11
0.19
HypFPE + HS-DTE
0.02
0.02
0.03
0.02
0.06
0.06
0.05
0.05
L. Statistics of the trees used in the experiments
Some statistics of the trees that are used in the experiments are shown in Table 11. Most notably, these statistics show that the true number of optimizations that has to be performed is significantly lower than the worst-case number of optimizations given by Theorem 3.1. To see this, note that an optimization step using MAM has to be performed each time node encountered with a degree that did not appear before. The result this optimization step can then cached and used for each node with the same degree.
M. Graph and tree-like graph embedding results
The graphs that we test our method on are graph detailing relations between diseases (Goh et al., 2007) and graph describing PhD advisor-advisee relations (De Nooy et al., 2018). In order to embed graphs with the combinatorial constructions, the graphs need to be embedded into trees first. Following (Sala et al., 2018), we use (Abraham et al., 2007) for the graph-to-tree embedding. The results of the subsequent tree embeddings are shown Table 12. These distortions are with respect to the tree metric of the embedded tree instead of with respect to the original graph. This is to avoid mixing the
19

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Table Comparison worst-case distortion hyperbolic embedding algorithms on the mosses and weevils trees. represents the construction with Hadamard hyperspherical points and * the construction with points sampled from set precomputed with (Lovisolo & Da Silva, 2001). best performance bold. The embeddings are performed in 4, 7, 20-dimensional space. Overall, we find that HS-DTE works best.
Mosses
Weevils
Dwe
4
10
20
4
7
10
20
HypFPE+ + (Sala el al., 2018) $
1.10
1.09
1.09
HypFPE + (Sala et al., 2018)
1.36
1.21
1.14
1.16
1.25
1.12
1.11
1.13
HypFPE + HS-DTE
1.09
1.07
1.06
1.07
1.05
1.05
1.04
1.04
Table 10. Comparison of worst-case distortion of hyperbolic embedding algorithms the carnivora and lichen trees. represents the construction with Hadamard hyperspherical points and the construction with points sampled from a set precomputed with (Lovisolo Da Silva, 2001). The best performance in bold. The embeddings performed in 4, 7, 10 20-dimensional space. Overall,
find that HS-DTE works best.
Carnivora
Lichen
Dwe
4
10
20
4
7
10
20
HypFPE+ + (Sala et al., 2018) $
6,76
6.76
6.76
6.76
43.4
43.4
43.4
43.4
HypFPE + (Sala et al., 2018) *
3.50
4.06
4.87
13.0
4.73
5.44
6.43
36.0
HypFPE+ + HS-DTE
2.46
2.45
2.03
2.35
4.07
4.63
3.30
7.17
influence the tree-to-hyperbolic space embedding method with that the graph-to-trec embedding.
From these results again that HypFPE + HS-DTE outperforms all other methods. However, it should be noted that graphs cannot generally be embedded with arbitrarily low distortion in hyperbolic space and that the graph to tree embedding method will introduce significant distortion. Hyperbolic space is not a suitable target for embedding a graph that is not tree-like. Therefore, we define our method as a tree embedding method and not as graph embedding method.
N. FPE arithmetic
Algorithm IPEAddition
Input: FPEs x 21 ... Fn y 1/1 ... + Um and number of output terms
2: f MergeFPPEs(x::)
3: + FPERenormalizo(f1
4: return = +
20

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Algorithm 3 MergeFPEs
1: Input: FPEs 21 + Zn. 21 + 3mm
2: 2 f Concatenate(I:.)
3: Sort terms in z in ascending order with respect to absolute value.
4: return Sorted (z1, 2n }-
Algorithm FPERenormaaize
Input: List of floating point numbers x 21...., In
and number of output terms
2: VecSum(x)
3: y +- VecSummEmBranch(e...
4: return y1 +... +
Algorithm VecSum
Input: List of floating point numbers 21,...; Zn.
2: +- In
3: io (.......... do
4: (s,e441) + 2Sum(I;; 8)
5: end for
6: 61 f-8
7: return EI,...,
Algorithm 6 VecSumEErBBracc
1: Input: List of floating point numbers e En and number of output terms
2: j 1+1
3: e 6
4: for [1,n-1) 1} do
5:
(r,,e) f- 2Summe, e++1
6:
e then
7: j 2 then
8:
return T1 Tm end if
9:
10:
j + +++1
11: else
12: e et
end if end for
15: if c 0 and
m then
16: t-
17: end if
18: return To.
Algorithm 2Sum
1: Input: floating point numbers and y-
2: + RN(x + y)
where RN is rounding nearest
3: x +- RN(s 8 7)
4: g' < RN(s s x¹)
5: 5 < RN(I x¹)
6: by + RN(V v/)
RN + +,,)
8: return (s,e)
21

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Algorithm 8 Fast2Sum
1: Input: Floating point numbers and with [log2 [e]] 2
[log2 [v]]
2: + RN(r + y)
3: z < ( x)
4: e + RN - 2)
5: return ())
Algorithm 9 IPEMultiplication
1: Input: FPEs x = r1 +... + Fn. y = + + ymu number of output terms r, bin size and precision p (for float64:
45, = 53).
2: tz llog2 _m|l
3: In [log2 [11l]
4: t tz + ty
[r- p/bl 6: Bi + 1.5 1- pb-ibbp-1
5: for (I,...,
2} do
7: end for
8: foríe {1,.... min(n, r + 1)} do
9: for E (l...., (ni, i)} do
(T')e) e) + 2Prod 8;) {t tz. ty:
11:
12:
sh + [e/b]
13:
l +-& - sh b
14:
B + Accumulate(x', e, B, sh,
15:
end for
j < m then
n' I; Yj
ftt Lzz by
19:
sh < [l/b]
20:
f - - sh b
21:
B + Accumulate(2/ B, sh, E)
22:
end if
23: end for
for
E (1...., (r..,,rpp//)) 2} do
25: B; + B, 2-b---
26: end for
27: π + VecSumEmnBranch( B, r)
28: return T1 +... Tr
22

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Algorithm 10 Accumulate
Input: Floating point numbers x', e, list of floating point numbers and integers sh, L.
2: c < p b-1
3: if < 2-c6-220 2c then
4: (Bah, x') t- Fast2Sum (Bsh: x²)
5: Bah+1 t Bsh+1 n'
6:
(Bsh+1, e] t- Fast2Sum(
7:
Bah+2 f Bah+2 t
8:
else if < then
9:
(Bah, T') f- (Bst T²)
10:
Bah+1 Bsh+1 n²
11:
(Bah+1, Fast2Sum( e,
12:
(Beh+2, t- Fast2Sum (anDSummBsh222 es)
13:
Bon+3 < Bah43 +e
14:
else
(Bah,P) - Fast2Suml (Bsh, m²)
(Bah+1, T') t Fast2Sum (Bah11,
17:
Bah+2 Bah+2 + x²
18:
(Bah+2, e) Fast2Sum BBhh+,
19:
Bah+3 < Bah+3 +e
20:
end if
21: return B
Algorithm 11 FPEReciprocal
1: Input: FPE x = + + 22+ an number of output terms 29,
2: ri RN(=) )
3: for E {1.....q) . do
4: v f- FPFMultiplicaaionn(:... 2(+1)
5: < FPERenormalize( (U) ..,.... - U2i 1, 2.0,0 21+1) FPEMultiplicatioon(f w. 1
6:
7: end for
8: return 71 + + 129
Algorithm 12 FPEDivision
1: Input: FPEs a = I1 +... In. = 111 +... + 3m and number output terms r.
2: z < FPEReciprocal(y, m)
3: IFPEMuliplicationn;,.,
4: return
Algorithm 13 FPEtanh -1
1: Input: FPE f = 8 +...... + fc.
2: if [ff] > then
3: return NaN
4: else if [f] then
5: return
6: else if [f] 0.5 then
7: return 0.5 sign(f) log(1 21 + 21/111/1
1-1f
8: else
9: return 0.5 sign(f f). log(1
21 1-1
10: end if
23

---

Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space
Table 11. Statistics for the trees used in the experiments. The number of unique degrees is excluding nodes with degree of 1. This number is equal to the total number of optimizations that has to be performed when embedding the tree using HS-DTE. The theoretical worst-case shows the worst-case number of optimizations that has be performed according Thcorem 3.1. Note that the number of optimizations is often significantly lower than this worst-case number.
Tree
Nodes
Unique degrees
Theoretical worst-case
A(T)
Longest path length
m-ary trees
Varying
Varying
m +
varying
Mosses
344
51
Weevils
195
29
29
Carnivora
548
3
45
4
192.4
Lichen
481
48
0.972
Table Comparison hyperbolic embedding algorithms graphs. represents the h-MDS method, the construction with Hadamard hyperspherical points and the construction with points sampled from set precomputed with (Lovisolo & Da Silva, 2001). The best float64 performance is underlined and best FPE performance is in bold. embeddings are performed 10-dimensional space. Hadamard generation cannot be used, since each embedded graph has A(T) greater than 8. HypFPE HS-DTE outperforms all methods.
Precision
Diseases
CS PhDs
D Dave
Dwc
D Dave
D Dwc
(Nickel & Kiela, 2017)
53
0.40
NaN
0.72
NaN
(Ganea al., 2018)
53
0.85
4831
0.94
803
(Yu al., 2022b)
53
0.72
1014
0.91
1220
(Sala et al., 2018) }
53
0.06
NaN
0.08
NaN
(Sala et al., 2018) $
53
(Sala et al., 2018) *
53
0.364
5.07
0.33
3.84
HS-DTE
53
0.28
2.28
0.29
2.76
HypFPE + (Sala et al., 2018) |
417
HypFPE + (Sala et al., 2018)
417
0.05
1.16
0.04
1.14
HypFPE + HS-DTE
417
0.04
1.14
0.04
1.09
24


Reviews:
[{"review_id": "Mu72lIwwY8", "reviewer": "Reviewer_bqVV", "summary": "This paper proposes a construction based tree embedding method in hyperbolic space.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback on the writing and clarity, and we are glad to hear that they like the paper. The reviewer points out four points of discussion and suggestions: the performance of optimization-based methods, experimental results on real-world data, comparison w.r.t. efficiency and a figure 1 for summarizing the approach. We address each of these below.\n\n**Performance of optimization-based methods.**\nThe approaches we mention regarding distorted embeddings are about the optimization-based approaches Poincaré Embeddings and Hyperbolic Entailment Cones specifically. We will clarify our statement to avoid any confusion with hyperbolic embeddings in general. There are several ways of measuring the quality of embeddings. For some of these, such as the MAP and F1 score, the optimization-based methods indeed perform well. This is in line with their intended downstream tasks which often involve link prediction. However, on distance-based metrics, these methods tend to perform significantly worse, as shown for instance by (Sala et al., 2018) and by our results. On the other hand, the constructive based approaches perform well on both types of metrics, while being significantly faster and without requiring hyperparameter tuning. We will add the point on quality with respect to metrics to the discussion.\n\n**Experimental results on real-world data and tree-like data.**\nWe fully agree with the reviewer, which is why we have included results on the embedding of real-world phylogenetic trees in Subsection 5.3 and tree-like graphs in Appendix M of the manuscript. Even on such real-world data, we find that our method has the strongest performance. Our method can be used to embed graphs in the same manner employed by (Sala et al., 2018). We hope the reviewer will find these results as convincing as we do.\n\n**Efficiency comparison.**\nWe believe comparisons can be made at two levels. The first is a comparison in efficiency between HS-DTE and the constructive approaches by (Sala et al., 2018). Here, the difference in efficiency comes from the difference in generating points on the hypersphere in step 6 of Algorithm 1. This generation for our method takes mere seconds and, according to Theorem 3.1, only has to be performed $\\mathcal{O}(\\sqrt{N})$ times in the worst-case (much less in practice). So, in our experiments we find a minimal increase (only seconds) in computation time with respect to (Sala et al., 2018).\n\nThe second is the efficiency of floating point expansion arithmetic compared to arbitrary precision arithmetic. Here, we have referred to the theoretical guarantees described for instance in (Popescu, 2017), which tell us that the complexities between the two types of arithmetic are similar. Testing this in practice is an important future direction. Currently, this cannot be done fairly as we would be comparing our first version Python implementation of FPE arithmetic against the heavily optimized arbitrary precision arithmetic that is used by Julia. More specifically, Julia uses the heavily optimized GNU MPA and GNU MPFR libraries, written in C, which have been in development for well over two decades with the sole purpose of building highly optimized and easily applicable arbitrary precision arithmetic. To compare fairly against such libraries, an optimized CUDA version of our library should be developed. We believe this is an exciting future research direction.\n\nWe expect that an optimized version for FPE arithmetic will significantly outperform arbitrary precision arithmetic libraries, especially for large tensors, as our approach can rely on accelerated hardware. We believe more attention should be brought to FPEs through papers such as this, as that will hopefuly help speed up the development of such libraries. We will include the discussion on efficiency and open research opportunities to the paper.\n\n**Addition of a figure 1 to summarize the method.**\nWe agree with reviewer and thank them for the suggestion. We have added a Figure 1 to the manuscript.\n\nWe thank the reviewer for their helpful feedback and hope that we have addressed their concerns.", "claims_and_evidence": "\"While these approaches are flexible due to minimal assumptions, the optimization can be unstable, slow and result in heavily distorted embeddings\"\n\nThis is not true, many hyperbolic embeddings achive great results, e.g., in  NLP, knowledge graphs, GNNs. It would be great to show more evidences for the claim \"...result in heavily distorted embeddings\".", "methods_and_evaluation_criteria": "This paper focus on tree embeddings, and only evaluate the model on small and synthetic tree data. \n\nTo demonstrate its applications to real-world cases, it should also be evaluated on real tree-like (but not eactly tree) datasets, such as on tasks of hierarchical graph (WordNet) embeddings, knowledge graphs, etc. Another reasoning to consider real data is to compare with learning based hyperbolic embeddings used in KG embeddings, GNNs, etc.", "theoretical_claims": "I read the theorem, but not check the proof.", "experimental_designs_or_analyses": "The experimental designs on synthetic datasets make senses, but should also be evaluated on real tree-like datasets. Otherwise, it is not convincing to claim that construction based methods are better than learning based methods.", "relation_to_broader_scientific_literature": "This work might be related to many applications involving hierarchical data.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n\n1) I like the paper, the writing of the paper is great. Motivation is also clear.\n2) The theorems provide some nice guarantees that are useful for real applciations (and the other methods do not have). \n3) Ilustration of the results and findings (figures and tables) are also clear. \n\nWeaknesses:\n\n1) Comparision w.r.t efficiency is missing\n2) Lack of evaluation on real-world datasets and ML tasks\n3) Lack of conceptual description of the proposed idea. I suggest to add a figure 1 in the intro, to summerize the main idea of the paper.", "other_comments_or_suggestions": "See Weaknesses", "questions_for_authors": "Does the proposed method only work for trees? or it can be extended to DAG, or any tree-like data like hierarchies but with a few cycles?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U939ti6eoB", "reviewer": "Reviewer_xLwr", "summary": "This paper takes on the task of transforming into an algorithm some mathematical results about low-distortion embeddability of any metric tree into hyperbolic space, whose existence and non-quantitative construction was known by work of Sarkar.\n\nThis endeavor leads to two new challenges.\n(1) the tree embeddings can become very large (unbounded diameter). Since the Poincare disk model sends the infinite hyperbolic space to a bounded chart, this means that unbounded numerical precision has to be used. Thus the authors present encodings via floating-point formal sums, that fit well with GPU processing and allow arbitrary precision\n(2) at vertices at which the metric tree has high degree N, for good efficiency (i.e. to get low distortion) we would impose that the N branches have to go in as well separated as possible directions, as measured in the tangent space to hyperbolic space at that point.. thus since in the tangent space is euclidean, we get the problem of distributing N points on a sphere, as uniformly as possible. This is in itself a well studied problem with many possible versions, but (a) one version has to be chosen and (b) it needs to be fit within the framework of hyperbolic space embeddings of trees. Here for (a) the authors choose to implement an energy depending on angle separations, and they proceed to do (b) in the natural way one would expect.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful and constructive feedback. Below, we describe how the feedback has been incorporated into the paper and address the reviewer's concerns.\n\n**The importance of embedding given hierarchies in deep learning.**\nMany works have shown the strong potential of deep learning with hyperbolic embeddings. All these works assume that hierarchical information is known *a priori*. Such knowledge is important for deep learning and can be incorporated into the model (as prototypes for example), the loss function, or several other means. The most intuitive examples of such hierarchies can be found in biology, where tasks such as classification can greatly benefit from knowledge regarding the evolution of species, typically given through animal taxonomies or phylogenetic trees [1, 2]. Other examples can be found in many different areas, such as biochemistry [3], medicine (Yu et al., 2022b), action recognition (Long et al., 2020), commonly used classification datasets such as ImageNet [4] and many more. In general, these works show that hierarchical information benefits deep learning, especially for hierarchical classification. There are various ways in which such a hierarchy can be leveraged to improve performance, such as through prototype learning.\n\nOur embedding approach can be directly used in deep learning in the same way. For all deep learning approaches, the better the embedding, the better the corresponding prototype distribution, benefitting deep learning. This is shown in (Liu et al., 2020; Long et al., 2020; Yu et al., 2022b). We apologize for not making this case clear enough and we will update the discussion in the introduction accordingly.\n\n~\n\n[1] Stevens, Samuel, et al. \"Bioclip: A vision foundation model for the tree of life.\" CVPR. 2024.\n\n[2] Chen, Jingzhou, et al. \"Label relation graphs enhanced hierarchical residual network for hierarchical multi-granularity classification.\" CVPR. 2022.\n\n[3] Yazdani-Jahromi, Mehdi, et al. \"HELM: Hierarchical Encoding for mRNA Language Modeling.\" ICLR. 2025.\n\n[4] Chatterjee, Ankita, Jayanta Mukherjee, and Partha Pratim Das. \"ImageNet classification using wordnet hierarchy.\" IEEE TAI 5.4 (2023): 1718-1727.\n\n\n**Fitting floating point expansions into neural networks.**\nIntegrating floating point expansions into existing deep learning libraries is an exciting next step, although it is indeed not completely trivial. Our statement in lines 247-248 is about the incompatibility of arbitrary precision arithmetic, since this incompatibility is at the hardware level. On the other hand, FPE arithmetic does allow for the use of GPUs, but requires new routines for additional functions and, often, for their derivatives in order to work with the usual deep learning pipelines. More specifically, to incorporate FPE arithmetic into existing hyperbolic learning methodology, we would have to implement the forward and backward passes of each operation involving the hyperbolic space (where the added precision is warranted) in FPE arithmetic, similar to what we did with the computation of the distance function in this work. On top of the additional required theory, the new architectures that incorporate these embeddings would have to be designed, optimized and tested. Because of this, we consider this to be outside the scope of the current paper, but a very interesting and necessary direction that we intend to explore in future work.\n\n**Additional references.**\nWe thank the reviewer for the additional references and have added these to the paper.\n\n**Theoretical comparison between our method and existing methods in terms of separation.**\nThere are a few specific settings in which optimal solutions are known. In some of those cases we have compared the optimal result to ours and found very similar separation. However, ours has the benefit of being always applicable, whereas the table of best known solutions (Cohn, 2024) has many missing entries. Combining both could lead to a small improvement, but due to the marginal increase in separation between our results and the best known results, the decrease in distortion will also be marginal.\n\n**Other comments and suggestions.**\nWe have incorporated each of the reviewer's comments and suggestions into the text. Due to the character limit we cannot address each point individually here. If the reviewer would like further clarification on any point in particular, then we would be happy to address these in the next response.\n\nWe hope to have addressed the reviewer's concerns and that they are convinced of the potential of our method for the hyperbolic learning community.", "claims_and_evidence": "I think that the claims about the algorithm working better for tree embeddings is warranted, both by the theoretical and by the quantitative comparison with other embeddings, so I don't have much to say on that.\n\nHowever I don't follow the reasoning about this embedding being useful for deep learning frameworks, as hinted at by the passages in the introduction in the first page of the paper. \n(In fact the authors mention this limitation explicitly in lines 247-248, first column, but they don't propose any solution.)\nSo I don't see how the floating point expansion from Def. 4.1 can be easily fit into a neural network processing. If the whole goal is just to embed a known tree into hyperbolic space, OK. But in practice for HNN applications one does not know the correct tree, and that has to be learned by a neural network or some other mechanism. The compatibility of the floating point expansion with Deep Learning frameworks has not been discussed nor tested. So the claims about usefulness in machine learning remain dubious to me.", "methods_and_evaluation_criteria": "I think that yes, they do.", "theoretical_claims": "Yes, I checked all the details and didn't find anything wrong.", "experimental_designs_or_analyses": "I think that the analyses match closely the theoretical part, and are not the most important part of the paper.\nHowever, they are sound for me.", "relation_to_broader_scientific_literature": "As said before, I think that this paper relates as a practical counterpart to the mathematical theory of embedding trees into hyperbolic space, however it does not connect with the most influential part of Hyperbolic Machine Learning, due to the presence of floating point expansions and due to not proposing a way to include this into hyperbolic machine learning pipelines.", "essential_references_not_discussed": "I think that some reference to the book of Borodachov-Hardin-Saff would be useful. \nAlso work by Carlos Beltran and collaborators on energy minimization over spheres can be interesting to mention. https://arxiv.org/abs/1703.00416. Perhaps taking points randomly from a determinantal point process can be another way to build good enough embeddings for other choices of energies?", "other_strengths_and_weaknesses": "I covered all the important points in other sections.", "other_comments_or_suggestions": "Line 133-134 second column: \"strong embeddings\" means what precisely? do you mean less distorted? And \"numerical issues\" means precisely what? It'd be good to be specific about what you refer to.\n\nLine 136 second column: I think that \"deg_{max}\" would be better as \"maxdeg\", if the underlying language of reference is English. If you follow French or Italian then go with \"deg_max\" but that seems odd.\n\nLine 145 second column: \"should be \\tau= \\Omega(1)\" what do you mean by \"should\" exactly? should be that in order to do what?\n\nLine 154 firlst column \"However\" means what, i.e. what's the problem with the methodology of that library? Be precise please.\n\nIn step 5 of Algorithm 1, what is R_{\\phi(v)\\to 0} ? this notation is not introduced before.\n\nLine 189-190 second column: \"We find that this method results in strong separation when compared to highly specialized existing methods [..]\" can you explain how you measured that? What's the comparison and to what do you compare it?\n\nIn the statement of Thm. 3.1 you talk about \"number of optimizations\" what does that mean? how is that defined from eq. (9) exactly?\n\nAt the end of page 4, you say \"MAM is easily optimizable\", what does that mean? Does it have no local minima? Or what does it mean \"easily\" and what would \"hardly\" mean?\n\nLine 223 first column: \"can be further optimized\", so why was it not optimized? maybe write \"could be optimized\"?\n\nAbout the description of formula (13), in the preceding paragraph: \"unevaluated sums\" does that mean \"collections of terms\" or what does it mean exactly? maybe represent that as tuples of floating point numbers, and then use formula (13) just for the interpretation. This is because \"unevaluated sums\" seems odd and to me unnecessarily hard to imagine.", "questions_for_authors": "1) Do you know of actual separation guarantees that allow to compare the theoretical results of separation obtained from your algorithm for mininmizing (13) vs the previous works? In other words, in theory, what's the improvement, how can that be measured?\n\n2) I reiterate on the question of NN processing compatibility of your floating point expansions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YlrmhgZhrO", "reviewer": "Reviewer_gaL1", "summary": "Existing combinatorial approaches to embedding trees in hyperbolic space suffer from issues stemming from (1) the difficulty of spreading out points on a hypersphere, and (2) floating-point precision issues. To address issue (1), the authors propose highly-separated Delauney tree embeddings (HS-DTE), which maximize the minimal angle between two leaves, unlike previous approaches which optimize the mean pairwise angles. To address (2), the authors present HypFPE, a modernized approach to floating point expansion with special attention paid to the hyperbolic distance function. The authors demonstrate the superiority of their methods against comparable approaches for a variety of real and empirical trees.\n\n## Update after rebuttal\nI maintain my recommendation to accept this paper. A common theme among other reviews is that, while the paper itself is of high quality, its relevance to the ICML readership is limited. I would like to offer a dissenting opinion: as the authors themselves argue better than I could in their rebuttal to Reviewer uxsR, there is substantial precedent for machine learning venues publishing work pertaining to tree embeddings. More speculatively, I also believe it is valuable to expose ML venue audiences to more nuts-and-bolts hyperbolic work, given the extensive history of cross-pollination between these fields.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback regarding the writing, motivation and results. Below we address the points and questions raised by the reviewer.\n\n**Runtime comparison and memory usage.**\nGiven the similar theoretical complexities, we consider benchmarking this to be an interesting and important direction for future work. However, currently, such a runtime comparison cannot be performed fairly, since (Sala et al., 2018) perform arbitrary precision (AP) arithmetic in Julia, which uses the heavily optimized GNU MPA and GNU MPFR libraries, written in C, which are the result of well over two decades of development. Our FPE library is a first version Python library, that still requires extensive optimization. So, before we can make a fair comparison, an optimized CUDA version of our library should first be developed. We expect that, once such a library exists, the runtime of AP arithmetic versus FPE arithmetic will be similar for small tensors, while for large tensors the FPE arithmetic will likely be significantly faster due to its ability to leverage the benefits of accelerated hardware. \n\nRegarding the memory usage, the main difference between FPE arithmetic and AP arithmetic is that each term of an FPE contains its own exponent (11 bits per float64), whereas an AP floating point number has a single exponent (64 bits in Julia). Therefore, adding bits of precision is slightly less efficient for FPEs than for AP arithmetic. However, this difference is marginal.\n\n**Reference to literature on the embedding of phylogenetic trees.**\nWe thank the reviewer for pointing out the papers on the embedding of phylogenetic trees. We have added references to these papers in the manuscript. \n\n**Clarification on hyperbolic reflections.**\nWe thank the reviewer for their suggestions for further clarification on hyperbolic reflections. Each of these will be incorporated into the manuscript, including a figure to show some simple examples of such reflections in $\\mathbb{D}^2$. The motivation for reflections lies within the fact that these are isometries of hyperbolic space, which means that we can safely use these to move our embeddings around without changing the distortion. This fact is not trivial and is a result that is sometimes proved in books on hyperbolic geometry such as in (Anderson, 2005). A reference to this result should have been in the manuscript and we have since added this to Appendix A alongside a clear explanation of the motivation and interpretation.\n\n**Explanation behind elbow behaviour in Figure 1(b).**\nThis is interesting behaviour that results from increasing the scaling factor $\\tau$ within the construction itself. Note that, as we increase the precision, we increase the scaling factor $\\tau$, since a greater $\\tau$ is always beneficial as long as it does not lead to numerical problems. For smaller values of $\\tau$, the method cannot make good use of the curvature and, as a result, subtrees will tend to overlap as we iteratively embed a tree, leading to massive distortion. As we increase the scaling factor $\\tau$, there comes a point where the subtrees stop overlapping, causing the worst-case distortion to quickly drop to near 1. Past this threshold, increasing $\\tau$ will only marginally decrease distortion compared to the initial drop, as the distortion will already be very low. We will include this explanation to the paper.\n\n**Intuitive explanation behind the difficulty of the Tammes problem.**\nThis is a very surprising problem as the problem statement itself is deceptively simple. Giving an intuitive explanation of why exactly this problem is so difficult is not particularly easy itself. Probably, the most straightforward way of getting a feeling for the difficulty of this problem is by manually attempting to place points on the sphere $S^2$. Placing a small number of points remains fairly simple (for example through the use of regular polyhedra), but as the number of points increases, this quickly becomes very difficult. In fact, for 15 points, there is already no known optimal solution [1]. This problem has sparked enormous amounts of research and has been found to have applications in many different areas of physics, computer science, and other scientific fields. For further information we refer the reviewer to a book on spherical coding such as [2].\n\n[1] D. A. Kottwitz, The densest packing of equal circles on a sphere, Acta Cryst. Sect. A 47 (1991), 158–165.\n\n[2] Conway, John Horton, and Neil James Alexander Sloane. Sphere packings, lattices and groups. Vol. 290. Springer Science and Business Media, 2013.\n\n**Other comments and suggestions.**\nWe have incorporated these suggestions into the manuscript. Thank you.\n\nWe hope to have adequately addressed the reviewers concerns and to have answered their questions.", "claims_and_evidence": "The authors do an excellent job situating their work within the rich literature on embedding trees in hyperbolic space, motivating their approach in terms of empirical issues and theoretical problems (the Tammes problem), proving bounds on all of their formulas, and devising careful experiments that demonstrate their improvement over other methods. All in all, each part of their paper is clearly isolated, well-argued, and relevant to the central argument.", "methods_and_evaluation_criteria": "The authors devise fair and minimal evaluations for demonstrating the value of their method. Their extension to phylogenetic trees is also reasonable. Given the emphasis on GPU optimization and several allusions to runtime improvements throughout the paper, I am confused by the absence of a runtime analysis in the paper.", "theoretical_claims": "I skimmed the proofs in Appendices D–H, but I did not scrutinize them closely.", "experimental_designs_or_analyses": "I closely read the description of the experiments and Appendix B and verified they are reasonable.", "relation_to_broader_scientific_literature": "The authors situate themselves in the context of tree embedding literature, which they subdivide into optimization-based and constructive methods; this method belongs to the latter, but quite reasonably the authors benchmark against all methods of both categories. They discuss the relationship of HS-DTE to Delauney tree embeddings, as well as explain how their work on HypFPE differs from other work on floating-point expansion. All in all, the authors are quite clear about where their work fits in to the existing literature.", "essential_references_not_discussed": "The authors perform extensive benchmarking on phylogenetic trees, but neglect to cite any of the literature concerning embedding phylogenetic trees in hyperbolic space [1, 2, 3, 4]. These tend to be much more Bayesian in flavor, as is typical of the phylogenetics literature more broadly; I acknowledge that this would be difficult to do explicit comparisons with, but I think acknowledging the existence of this literature is necessary.\n\n**References**\n\n[1] Macaulay et al (2023). Fidelity of hyperbolic space for Bayesian phylogenetic inference. https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1011084. \n\n[2] Jian et al (2022). Learning Hyperbolic Embedding for Phylogenetic Tree Placement and Updates. https://pmc.ncbi.nlm.nih.gov/articles/PMC9495508/.\n\n[3] Matsumoto et al (2021). Novel metric for hyperbolic phylogenetic tree embeddings. https://pmc.ncbi.nlm.nih.gov/articles/PMC8058397/.\n\n[4] Wilson (2021). Learning phylogenetic trees as hyperbolic point configurations. https://arxiv.org/pdf/2104.11430.\n\n[5] Chen et al (2025). Variational Combinatorial Sequential Monte Carlo for Bayesian Phylogenetics in Hyperbolic Space. https://arxiv.org/abs/2501.17965.", "other_strengths_and_weaknesses": "**Strengths:**\n* The paper is very coherently written, and the experiments are minimal and convincing.\n* The authors promise to provide Pytorch-compatible libraries for both HS-DTE and HypFPE, which will be a boon to the hyperbolic deep learning community.\n\n**Weaknesses:**\n* The novelty of this paper is somewhat limited: as I understand it, HS-DTE is a simple substitution of one loss function for another relative to the previous Delauney embeddings work; similarly, floating point expansion has been done in hyperbolic space previously, and the authors simply modernize it and give a more careful gloss of its role in the hyperbolic distance function. That said, this is a well-studied problem, so I expect most papers in this field to be somewhat incremental. Given the clear improvements the authors demonstrate, I am less concerned about this weakness.\n* The phylogenetics benchmarks are not situated in the context of other hyperbolic methods for embedding/inferring phylogenetic trees.\n* The authors talk about runtime, but do not provide actual benchmarks for this. Memory usage would also be interesting to look at, especially as a function of the number of FPE terms.", "other_comments_or_suggestions": "* The discussion of hyperbolic reflections is somewhat confusing, and I found the transition into reflections in subsection 2.1 quite abrupt. For context, I am quite familiar with the preceding math, and not at all familiar with reflections. To this end, I have three concrete suggestions:\n  * Add a paragraph break prior to starting this discussion\n  * Explaning the motivation for the reflections more clearly would motivate this math better.\n  * A figure demonstrating a hyperbolic reflection in $\\mathbb{P}^2$ could be helpful\n* Per the ICML style guide, table captions should appear above the tables.\n* It is unclear what the horizontal lines in Tables 2 and 3 mean\n* The running title of the paper still reads \"Submission and Formatting Instructions for ICML 2025\"", "questions_for_authors": "* Can you explain the \"elbow\" in Figure 1(b)? Is this surprising, or is it explained by some theoretical aspect of FPE?\n* I found it very surprising that it is a difficult problem to distribute $n$ points nicely on $\\mathbb{S}^d$. Can you provide an intuitive explanation for why this is the case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OjGeLKxHpu", "reviewer": "Reviewer_uxsR", "summary": "The Authors propose a pipeline to embed trees in hyperbolic space with minimal distortion yet with the ability to operate on accelerated GPU by the generalised Dalaunay embedding algorithm with minimal angle maximization and providing a solid framework to essentially increase the precision by using multiple float data even when the precision of each variable is limited.\n\n## update after rebuttal.\n\nThe authors have provided acceptable evidence that embedding pure trees can contribute to the ICML community, e.g., through action search. It should be included in the manuscript, but it can be easily done in the camera-ready version. I have raised the score to Weak Accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind remarks regarding the contribution of our paper and their recognition of the convincing nature of our method. Below we address the main concern of the reviewer, namely the potential and relevance to the machine learning community.\n\n**Relevance to the machine learning community.**\nIn our view, there are three important reasons why this paper should be published in a machine learning conference such as ICML.\n\n1. This paper follows a long tradition of hyperbolic embedding papers published in machine learning conferences. As mentioned by the reviewer, (Sala et al., 2018) is closest to our work and was previously published in ICML. Their h-MDS performs an eigenvalue decomposition on the pairwise distance matrix and projects the resulting eigenvectors to the hyperboloid to obtain embeddings, hence also not making use of any learning algorithms. The high impact of (Sala et al., 2018) serves as an indication of the potential of hyperbolic tree embeddings within our field. Other hyperbolic embedding papers in machine learning conferences include (Nickel and Kiela, 2017; Ganea et al., 2018; Yu et al., 2022b), each of which uses a learning approach to obtain embeddings. Although these methods all employ some type of learning, they achieve considerably worse results than the constructive approaches. Therefore, we think it is important that our constructive approach is published within the machine learning community.\n\n2. We believe that the primary relevance of hyperbolic embeddings to the machine learning community lies in their potential for downstream deep learning applications. In recent years, a common approach for incorporating hierarchical knowledge into deep learning models is by placing the hyperbolic embeddings of the hierarchies on top of neural networks. Then, the node embeddings serve as prototypes for learning. See for example (Liu et al., 2020; Long et al., 2020; Yu et al., 2022b). In other words, hyperbolic embeddings are already an active part of the deep learning pipeline. Lower distortion means better embeddings which leads to better results in hierarchical deep learning. Hence it is important for us to share our findings in a machine learning venue to maximize impact.\n\n3. We believe FPEs to be an important direction for the field of hyperbolic machine learning. Nearly every paper on hyperbolic learning mentions the numerical problems that arise from attempting to do computation in hyperbolic space, with a particularly compelling analysis of the numerical stability by [1], also published at ICML. They show that the maximally representable subset of hyperbolic space in the commonly used models is severely limited in its radius. FPEs alleviate these problems, significantly increasing this radius. We think our work will be impactful to hyperbolic machine learning by shining a light on the potential of FPEs while also providing an implementation of the current state-of-the-art routines on this type of arithmetic that is compatible with the most commonly used deep learning framework, i.e., PyTorch. This provides a starting point for exciting future work on hyperbolic machine learning with higher precision, while mantaining GPU-compatibility.\n\nBased on these, we believe our work will be most impactful if it is published at ICML where it can reach its intended target audience: the hyperbolic machine learning community. We hope that the reviewer will appreciate and agree with our motivations. We will make sure to better clarify these important points in the paper.\n\n[1] Mishne, Gal, et al. \"The numerical stability of hyperbolic representation learning.\" ICML. 2023.\n\n**Corrections to Theorems 4.2 and 4.4.**\nThe reviewer is correct in that we intend $\\epsilon^*$ to be in the order of the machine epsilon. We apologize for the lack of clarity and have changed the text accordingly.", "claims_and_evidence": "The goal of the paper (low-distortion with fixed length float numbers, exploiting hyperbolic space with a general dimensionality) itself is simple, and the proposed method is designed to directly solve the issue. Algorithm 1 is a natural generalisation of Sarker's embedding in high-dimensional hyperbolic space. Applying the minimal angle maximization is a natural and direct idea to put the children of a node uniformly. Using multiple fixed precision float numbers also directly solves the issue of the lack of precision required by hyperbolic embedding. They are both convincing.", "methods_and_evaluation_criteria": "As discussed above, the proposed method succeeds in solving existing issues of hyperbolic embedding of a tree.", "theoretical_claims": "The statement of Theorem 4.2. must be rewritten. \"Some $\\\\epsilon^*$\" makes no sense mathematically. If some argued $\\\\epsilon^*=10^{300}$ is still small, there would be no practical implication of Theorem 4.2. If it were a function of $\\\\epsilon$, $t$, or machine epsilon, it might have some practical implication. \nPerhaps, the Authors wanted to say that we can let $\\\\epsilon^*$ be 16 times the machine epsilon, according to the proof? Theorem 4.4. has the same issue.", "experimental_designs_or_analyses": "The experiments are designed soundly so that they can directly evaluate how well the proposed method achieved the initial goal of the paper.", "relation_to_broader_scientific_literature": "The paper might have more contributions to the data compression or data structure contexts.", "essential_references_not_discussed": "Nothing.", "other_strengths_and_weaknesses": "As a computer science paper, the paper's contribution is solid and almost complete. Having said that, regrettably, I need to flag that the current manuscript of the paper does not clarify the contribution to the ICML community, where the main focus is on machine learning, as its name suggests. Many hyperbolic representation learning methods, represented by (Nickel and Kiela 2017), the motivation was in learning some representations of a graph, typically not a tree strictly but approximated by a tree, and those obtained representations could be used for link prediction. This is a procedure of retrieving some initially unknown information from data, which can be called \"learning.\" However, the proposed method only considers where **the complete information of a pure tree** is available. Where we have the complete information of a pure tree and obtain perfect representations in hyperbolic space that can recover the original distance structure, what do we \"learn\" by that? In other words, why are we not satisfied with the original tree? Actually, I do not see any information that we can obtain from the Authors' method, compared to the original tree. Hence, I do not dare to call the Authors' method \"machine learning.\" Recall that (Sarker 2011) was presented in the graph drawing context, and (Sala et al., 2018) included hyperbolic MDS, which has room for being called \"machine learning.\"\n\nObviously, even if some work is not directly related to machine learning, provided that it has the potential to contribute to the machine learning community, ICML must be capable of accepting it as long as the potential is clarified in the paper. However, the Authors' current manuscript does not clarify how it can contribute to the community.\n\nIn fact, the Authors' work has the potential to contribute to the machine-learning community. The perfect representations can provide the distance between two nodes at almost constant time (though it depends on the precision of float and dimension, strictly speaking) while the space complexity is almost linear to the number of nodes (again, it depends on the precision of float and dimension). This is in contrast to the naive distance matrix implementation needing computational costs quadratic to the number of nodes. This must be an attractive *data structure*, if not machine learning itself, for machine learning on tree data. Nevertheless, the current manuscript does not stress such perspectives. It requires rewriting from scratch, which is not what the rebuttal period aims at.", "other_comments_or_suggestions": "Considering the solid contribution of the Authors' work to computer science, I humbly suggest the following:\n- The most straightforward way is to submit the manuscript to another venue (it requires withdrawal from ICML), which can appreciate the Authors' contribution better. In any case, I encourage the Authors to upload the work to some online repositories to secure the priority right if they have not done so.\n- If the Authors want to present their work on machine learning venues, rewrite it from scratch so that the contribution to the community is clear.\nIn any case, the competitors would be data structures, like the distance matrix, naive implementation of a tree as a graph, etc., rather than existing hyperbolic representations.", "questions_for_authors": "Could you formalize the statements of Theorems 4.2. and 4.4?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The submitted manuscript introduces a novel tree embedding method in hyperbolic space. After reading the initial reviews, the rebuttal and following the discussion, my summary is that all reviewers agree that the paper presents an interesting novel idea and is technically strong. Maybe some claims and assertions should be toned down a bit, especially regarding the a-priori use of hierarchical information. Also, the authors provided a convincing rebuttal, clarifying most concerns raised by the reviewers. From that perspective, I think there are no substantial changes to the manuscript required and all concerns can be addressed in a camera-ready version without an additional round of review. Hence, I am recommending acceptance. Please incorporate all (reasonable) changes requested when preparing the final manuscript.
Decision: Accept (poster)