Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space

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.

Relevance to the machine learning community. In our view, there are three important reasons why this paper should be published in a machine learning conference such as ICML.

1. 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.

2. 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.

3. 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.

Based 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.

[1] Mishne, Gal, et al. "The numerical stability of hyperbolic representation learning." ICML. 2023.

Corrections to Theorems 4.2 and 4.4. The 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.

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.

Runtime comparison and memory usage. Given 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.

Regarding 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.

Reference to literature on the embedding of phylogenetic trees. We thank the reviewer for pointing out the papers on the embedding of phylogenetic trees. We have added references to these papers in the manuscript.

Clarification on hyperbolic reflections. We 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.

Explanation behind elbow behaviour in Figure 1(b). This 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.

Intuitive explanation behind the difficulty of the Tammes problem. This 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].

[1] D. A. Kottwitz, The densest packing of equal circles on a sphere, Acta Cryst. Sect. A 47 (1991), 158–165.

[2] Conway, John Horton, and Neil James Alexander Sloane. Sphere packings, lattices and groups. Vol. 290. Springer Science and Business Media, 2013.

Other comments and suggestions. We have incorporated these suggestions into the manuscript. Thank you.

We hope to have adequately addressed the reviewers concerns and to have answered their questions.

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.

The importance of embedding given hierarchies in deep learning. Many 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.

Our 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.

~

[1] Stevens, Samuel, et al. "Bioclip: A vision foundation model for the tree of life." CVPR. 2024.

[2] Chen, Jingzhou, et al. "Label relation graphs enhanced hierarchical residual network for hierarchical multi-granularity classification." CVPR. 2022.

[3] Yazdani-Jahromi, Mehdi, et al. "HELM: Hierarchical Encoding for mRNA Language Modeling." ICLR. 2025.

[4] Chatterjee, Ankita, Jayanta Mukherjee, and Partha Pratim Das. "ImageNet classification using wordnet hierarchy." IEEE TAI 5.4 (2023): 1718-1727.

Fitting floating point expansions into neural networks. Integrating 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.

Additional references. We thank the reviewer for the additional references and have added these to the paper.

Theoretical comparison between our method and existing methods in terms of separation. There 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.

Other comments and suggestions. We 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.

We hope to have addressed the reviewer's concerns and that they are convinced of the potential of our method for the hyperbolic learning community.

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.

Performance of optimization-based methods. The 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.

Experimental results on real-world data and tree-like data. We 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.

Efficiency comparison. We 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).

The 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.

We 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.

Addition of a figure 1 to summarize the method. We agree with reviewer and thank them for the suggestion. We have added a Figure 1 to the manuscript.

We thank the reviewer for their helpful feedback and hope that we have addressed their concerns.