Distortion-free and GPU-compatible Tree Embeddings in Hyperbolic Space

We thank the reviewer for their positive feedback on the motivation, writing, and theory. The reviewer points out three points of discussion: embeddings beyond trees, the algorithm complexity, and application to general hyperbolic networks. We provide answers to all three points below.

Embedding of trees and beyond. Indeed, our method is aimed at embedding trees into hyperbolic space. However, the approach can generalize to general graph data by first embedding the graph into a tree. This method is also used to embed graphs using the construction in (Sala et al., 2018). In Table 12 of the main paper, we provide a comparison between the embeddings of trees generated from graph data. We note that, when combining graph-to-tree and tree-to-hyperbolic algorithms, the distortion is a combination of the distortions incurred by each individual algorithm, making it difficult to assess the contribution of each separate algorithm to the overall error. Therefore, our experiments focus on the embeddings of trees to show how it performs against the baselines without clouding results.

Algorithm complexity. There are two components to discuss regarding the complexity: [1] The first is the added complexity that results from separating hyperspherical points using MHS. This is shortly discussed at the end of Section 3, but we will expand upon the subject further here. Essentially, each time that hyperspherical points have to be generated in step 6 of Algorithm 1, we check if the degree of the node has been encountered before. If not, then we have to run the optimization and cache the output. If it has been encountered before, then we simply use the cached hyperspherical points. This optimization itself is cheap to perform and the worst-case number of times that the optimization has to be performed is $\mathcal{O}(\sqrt{N})$ as shown by Theorem 1. Moreover, in practice we find that the actual number of optimizations is even lower than this as shown by the short analysis in our response to Reviewer fcXk under "How frequently are caches applied?". As a result, we find that the optimizations take a fraction of the total computation time. [2] The second is the added complexity due to the use of floating point expansion arithmetic. A complete analysis of both the accuracy and complexity of this framework and its operations is given by (Popescu, 2017) and is far too extensive to include here. To summarize their results, the complexity is similar to the complexity of mixed precision arithmetic with respect to the number of bits, while also resulting in similar accuracy. As such, the main difference between the two frameworks is the compatibility of FPEs with GPUs.

Broader applicability. Our approach has the potential for broader integration with hyperbolic networks. This does require the implementation of additional operations for FPEs, similar to the implementation of $\tanh^{-1}$. We consider this a very interesting direction of future research and we have included it in the conclusions of the paper.

We hope our answers have addressed the reviewer's concerns and, given the positive feedback, that we have convinced the reviewer to raise their rating.

We thank the reviewer for their positive feedback regarding the structure, the motivation and the performance of the method. We have performed additional experiments as discussed below, which we hope addresses the concern raised by the reviewer. Moreover, we have answered their questions below.

More comprehensive evaluations. We have performed additional experiments where we study the effect of the embedding dimension. We have added results for varying embedding dimension in our response to reviewer fcXk and find that our method outperforms the baselines for those other embedding dimensions as well. These results have also been added to the appendix. Lastly, we also want to point out the comparisons on graph data in Table 12 of the appendix.

The use of "distortion-free". We agree with the reviewer and have changed the wording to "low-distortion", akin to (Sarkar, 2011). Only in the limit $\tau \rightarrow \infty$ does this construction lead to completely distortion-free embeddings.

The relationship between low-distortion, gpu-compatible and downstream performance. The importance of low-distortion embeddings for downstream tasks depends on how the embeddings are incorporated into the downstream method. Most recent methods (Peng et al., 2021; Mettes et al., 2024; Long et al., 2020; kolyvakis et al., 2020; Tifrea et al., 2018) make use of a prototypical deep learning approach. This is still an active area of research, but what these methods typically have in common is that they require low-distortion embeddings. This is motivated by the fact that when using a tree, all of the information about how labels are related is stored in the edges (and their weights). If the embeddings suffer from high distortion, then much of this information is lost, rendering the embeddings effectively useless. The importance of GPU-compatibility stems from the use of deep learning on which all of these methods rely. When using mixed precision arithmetic for the embeddings, we end up with a representation that is incompatible with GPUs. As a result, we cannot use these directly for downstream tasks if we plan on using a deep learning method. The relation between distortion-free, gpu-compatibility and performance lies within the scaling factor $\tau$. As $\tau$ increases, the construction leads to smaller distortions, at the cost of placing embeddings further away from the origin. When we move away from the origin, we need more bits to represent points. So, to decrease the distortion of our embeddings, we need to increase $\tau$, which in turn means that we need to use more bits. Increasing the number of bits while retaining GPU-compatibility is currently only possible by using FPEs.

The impact of maximally separated points on downstream tasks. In the original 2-dimensional construction (Sarkar, 2011), Sarkar has shown the relationship between several important variables such as the scaling factor $\tau$, the degree of nodes and the minimal separation between points in the hypersphere step. Those results are further generalized to higher dimensions by (Sala et al., 2018). A rigorous exposition of these results is perhaps a bit excessive for this discussion, but the complete results can be found in Theorem 6 and Algorithm 1 of (Sarkar, 2011) and Appendix D of (Sala et al., 2018). In short, these state that the distortion can be decreased by increasing $\tau$ or by increasing the separation between hypersphere points in step 6 of Algorithm 1 as given in our paper. Therefore, if we achieve better hyperspherical separation, then the distortion will go down.

MHS optimization details. The experimental details that we use for optimization with MHS are given towards the end of Section 3. We have added a header to this paragraph to indicate that it describes the implementation details for optimizing MHS.

We thank the reviewer for their positive comments on the theory and writing of the paper and for spotting some improvements that can be made. Below, we have answered the questions posed by the reviewer and we have made the proposed changes in the manuscript.

Typo in line 855. There was indeed a typo. We thank the reviewer for catching the mistake and we have updated the sentence.

On Theorems 3 and 5. We agree with the reviewer that these statements would be more appropriate in the form of a proposition and we have changed this in the manuscript accordingly.

Elaboration on third limitation of baseline (line 236). When placing a point on the vertex of an $n$-dimensional hypercube, there are $2^n$ options, so we can represent each option by a binary sequence of length $n$. For example, on a hypercube where each vertex $v$ has $||v||_\infty = 1$, each vertex is of the form $(\pm 1, \ldots, \pm 1)^T$, so we can represent $v$ as some binary sequence $s$. The distance between two such vertices can then be expressed in terms of the Hamming distance between the corresponding sequences as $d(v\_1, v\_2) = \sqrt{4d\_{\text{Hamming}} (s\_1, s\_2)},$ 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 $k$ binary sequences of length $n$ which have maximal pairwise Hamming distances. There are some specific combinations of $n$ and $k$ for which optimal solutions are known, such as the Hadamard code. However, for most combinations of $n$ and $k$, the solution is still an open problem (MacWilliams and Sloane, 1977). Therefore, properly placing points on the vertices of a hypercube currently relies on the solution to an unsolved problem, making it difficult to do in practice. We have added this discussion to the appendix.

MacWilliams, F. J., and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company, 1977.

Generalizing to other manifolds. Yes, it is certainly possible to use isometries between hyperbolic spaces to study other manifolds. Our method operates in the Poincaré ball model of hyperbolic space and the resulting embeddings can be mapped to any other model of hyperbolic space through the usual isometries. This maintains the pairwise distances of the embeddings, meaning that the quality of the embedding is preserved. Therefore, our approach can be used to generate embeddings for any model of hyperbolic space by simply applying an isometry at the end. However, it should be noted that some isometries may rely on operations for which new FPE routines need to be implemented. Therefore, we focus on the Poincaré ball throughout the paper.

Extension of Theorem 1. We can indeed extend Theorem 1 by changing MHS. In fact, the proof is independent of the optimization objective that is being used. The statement of the theorem would have been more appropriate without the mention of MHS. We have changed this accordingly. Thank you for pointing this out.

We again thank the reviewer for their feedback and we hope to have addressed their questions.

Additional questions

$s$ in Eq. 13. Thank you for pointing this out. The value $s$ is a nonnegative integer introduced in (Liu et al., 2018) which parameterizes the hyperspherical energy functions, so each $E_0, E_1, \ldots$ forms a different hyperspherical energy function. Higher values of $s$ lead to higher penalties on highly similar points akin to how the mean squared error and the mean absolute error relate to one another. We have added this information below the equation.

Limitations of Eq. 13. The statements on lines 250-254 are based on the results in Figure 1a and Table 1, where we see that the objectives in Equation 13 lead to lower minimum pairwise angles and that these objectives lead to higher distortion when compared to MHS. We have added a mention of the experiment to this discussion in the paper.

Minimizing cosine similarity between points instead of maximizing absolute angles. Based on the suggestion by the reviewer, we have recreated Figure 1b where we have added the proposed objective, where we minimize the maximum value of the cosine similarity instead of maximizing the minimum angle. This leads to mostly similar results, although we find that MHS is slightly more stable and, on average, leads to slightly better separation, compared to the cosine-based approach. Moreover, as can be seen in the table for the binary tree above, the two objectives lead to similar distortions, with MHS leading to slightly lower worst-case distortion in two cases. We have included the ablation study in the appendix of the paper. Thank you for the suggestion.

How frequently are caches applied? We can use a cached result each time we run into a node with a degree that we have encountered before. Therefore, the number of times that we cannot use a cached result and have to perform the optimization is equal to the number of unique degrees occuring in the tree (ignoring the leaf nodes). In the table below you can see this number of optimizations for each of the trees that is used in the experiments compared to the theoretical worst-case number of optimizations given by Theorem 1, alongside some other statistics. As can be seen, the number of optimizations that we perform is generally quite a bit lower than this upper bound. We have included this analysis in the appendix of the paper.

Utility of the embeddings. The use of tree embeddings for downstream tasks is an active area of research, with most methods taking a deep learning approach using prototype learning (Peng et al., 2021; Mettes et al., 2024; Long et al., 2020; Kolyvakis et al., 2020; Tifrea et al., 2018). In order to apply our method, with FPEs, in such a setting, we need additional routines, similar to the $\tanh^{-1}$ routine, and an altered neural network architecture that allows for predicting FPEs. We consider this a very interesting research direction, but due to the additional theory required, we deem it outside the scope of the current paper. Experiments, such as the link prediction experiment by (Nickel and Kiela, 2017), are aimed at graphs and are inappropriate for trees, since predicting an additional edge in a tree would break the tree structure.

WordNet. WordNet is not a tree, so in order to embed it using our approach, it must first be embedded into a tree, similar to (Sala et al., 2018). We attempted this first step using the approach by (Abraham et al., 2007) which led to a tree which was already heavily distorted from the original WordNet graph. In other words, WordNet does not let itself be described by a tree very well. Moreover, the method of graph-to-tree embedding and the choice of root node for the tree heavily influence the distortion of the embedding. As such, it is difficult to compare our approach to for example (Sala et al., 2018) without having access to the exact graph-to-tree embedding configuration, since any difference in distortion is a combination of both embedding steps. We, therefore, focus on tree-like data in our experiments.

We hope to have addressed the reviewer's primary concern and to have answered their questions. If there are any additional experiments of interest or if there are any further questions or concerns, please let us know.

The fifth and sixth tables contain the results for the phylogenetic trees for the methods using FPEs, akin to the last 3 rows of Table 3 in the paper. Here, we again observe that HypFPE + MS-DTE outperforms each method in nearly every setting. Moreover, we observe that for the carnivora and for the lichen, the results with the precomputed points (HypFPE + Sala et al. (2018)*) become worse as the dimension increases. This can be explained by the fact that these trees have a low $\text{deg}_{\max}$ (shown in the table corresponding to the answer to question 4), meaning that an increase in dimension is not as beneficial for embedding these trees, while this increase in dimension does make the task of separating points on a hypersphere more difficult. It seems that the precomputed points are not as well separated for increasing dimension. On the other hand, MHS still leads to proper separation, even for higher dimension, as evidenced by the results.

We conclude that our approach provides the best hyperbolic embeddings across all dimensionalities.

We thank the reviewer for their feedback. Below we show how our approach handles varying dimensionalities and answer the individual questions. We agree with the reviewer on the need for additional ablations on the embedding dimensionality and we believe this analysis further strengthens our contributions.

Additional ablations on dimensionality. In our submission, we chose 10 dimensions since the Hadamard baseline of (Sala et al., 2018) is often too restricted on smaller dimensions. Our approach can handle any choice of dimensionality. As pointed out by the reviewer, hyperbolic embeddings are well-suited in low-dimensional settings. To showcase our robustness, we replicated our experiments in Tables 1, 2 and 3 with 4, 7 and 20 embedding dimensions. The results are shown in the tables below, which have also been added to the appendix of the paper.

The first two tables show the average distortion and worst-case distortion, respectively, of the embedding of a binary tree of depth 8, akin to Table 1 of the paper. The cosine similarity method that has been added to the tables is in response to question 3 regarding the objective function, which will be addressed below. We note that MHS has the best performance on both metrics for all configurations except for the $D_{wc}$ with embedding dimension 4, where $E_1$ achieves slightly better performance, and for $D_{ave}$ with embedding dimension 20, where the cosine similarity achieves a slightly better result. For lower embedding dimensions, the hyperspherical separation is slightly easier to perform, meaning that MHS's benefits compared to the hyperspherical energy objectives ($E_s$) are slightly less important. However, overall we find MHS to lead to the best results. The MAP metric has not been reported because $E_0$, $E_1$, $E_2$ and MHS already lead to a perfect MAP for each dimension.

In the third and fourth tables, we present the average distortion and the worst-case distortion, respectively, of the embedding of a 3-tree, 5-tree and 7-tree, akin to Table 2 of the paper. Here, we see that MS-DTE outperforms all methods on $D_{ave}$. The only exception is h-MDS. This approach is however not useful, as it leads to infinite worst-case distortion due to leaf node collapse and, therefore, also to low MAP scores, as highlighted in Figure 2 of the main paper. The Hadamard code (Sala et al. (2018)\ddagger) can only generate 4 points for dimensions 4 and 7, due to which it cannot be used to embed the 5-tree and 7-tree in those dimensions. The MAP metric is again not reported because all methods except h-MDS achieve a perfect MAP in all settings.

We thank the reviewer for their positive comments on the method, its implementation and its efficacy. Below we have addressed the questions and concerns posed in the review.

Down-stream tasks. Indeed, our empirical evaluation focuses on the tree embeddings themselves, not on down-stream tasks. Works that focus on down-stream tasks build hyperbolic embeddings on top of deep networks and have shown that better tree embeddings lead to better (hierarchical) classification (Peng et al., 2021; Mettes et al., 2024; Long et al., 2020; Kolyvakis et al., 2020; Tifrea et al., 2018). Our approach leads to lower distortion, while our floating point expansion (FPE) ensures that we can still use standard floating point operators required by modern deep learning libraries. Making the step towards down-stream tasks does require further study however, as current solutions do not use FPEs. We consider this step a fruitful direction for future research. To avoid confusion about our claims, we have made changes to the introduction and conclusions accordingly.

Code will be made public. All code will be made available. We will release two software libraries, one for arbitrarily-dimensional hyperbolic tree embeddings (where all current embedding algorithms are implemented under one umbrella for direct comparisons) and one for GPU-compatible floating point expansions. The code will be released on GitHub with the links shared in the final manuscript.

Figure 1(b). As we increase the number of bits that we use for our representation, we increase the effective radius of the Poincaré ball, i.e. the distance from the origin up to which we can represent points in hyperbolic space without numerical problems. In fact, this radius in terms of the hyperbolic distance of points to the origin grows linearly in the number of bits. The scaling factor $\tau$ that we use stretches the edges, which leads to lower distortion of the embeddings as discussed by (Sarkar, 2011; Sala et al., 2018), while also causing the embeddings to end up further and further from the origin as $\tau$ grows. This means that we need to use more bits if we want to use larger values of $\tau$ and this relationship is linear. In Figure 1(b) we simply set $\tau$ to a value for which the embeddings end up close to this effective radius, so we could have also used $\tau$ on the x-axis here. As expected, as the number of bits, and therefore $\tau$, increase, the distortion decreases. The elbow type graph that we see is due to the fact that subtree embeddings can overlap for smaller values of $\tau$, which leads to very large distortion. Once the scaling factor becomes large enough, these subtrees get disentangled, after which the distortion decreases more slowly.

We hope to have addessed the questions raised by reviewer and we thank you for the feedback.