Representing Hyperbolic Space Accurately using Multi-Component Floats
Authors: Tao Yu
Christopher De Sa
Venue: NeurIPS 2021 Poster (2021)
Keywords: Hyperbolic Embedding
Multi-component floating-point
Representation learning

Abstract: Hyperbolic space is particularly useful for embedding data with hierarchical structure; however, representing hyperbolic space with ordinary floating-point numbers greatly affects the performance due to its \emph{ineluctable} numerical errors. Simply increasing the precision of floats fails to solve the problem and incurs a high computation cost for simulating greater-than-double-precision floats on hardware such as GPUs, which does not support them. In this paper, we propose a simple, feasible-on-GPUs, and easy-to-understand solution for numerically accurate learning on hyperbolic space. We do this with a new approach to represent hyperbolic space using multi-component floating-point (MCF) in the Poincar{\'e} upper-half space model. Theoretically and experimentally we show our model has small numerical error, and on embedding tasks across various datasets, models represented by multi-component floating-points gain more capacity and run significantly faster on GPUs than prior work. 

Representing Hyperbolic Space Accurately using Multi-Component Floats
Tao Yu
Christopher De Sa Department of Computer Science Cornell University ceesa@cs.cornell..
Department of Computer Science Cornell University tyu@cs.cornell. cornell. edu
Abstract
Hyperbolic space is particularly useful for embedding data with hierarchical struc- ture; however, representing hyperbolic space with ordinary floating -oint numbers greatly affects the performance due its ineluctable numerical errors. Simply increasing the precision of floats fails to solve the problem and incurs a high com- putation cost for simulating as GPUs, which does not support them. In this paper, we propose a simple, feasible- on-GPUs, and easy-to-understand solution for numerically accurate learning on hyperbolic space. We do this with a new approach to represent hyperbolic space using multi-component flotingg-poin (MCF) the Poincaré upper-half' space model. Theoretically and experimentally we show our model has small numerical error, and on embedding tasks across various datasets, models represented by multi-component floating- pointss gain more capacity and run significantly faster on GPUs than prior work.
floats hardware such
Introduction
Representation learning of particular interest nowadays in machine learning. Real-world data is often discrete--suhe as natural language sentences in the form of syntax trees and graphs [2] which makes critical to do good job of representing and storing them as numbers which can better understand and deal with. Perhaps the most common way of doing this representation with embedding, which discrete objects are assigned points in some continuous (typically high-dimensional Euclidean) space. Standard embeddings in NLP include Word2 [24] and GloVe [30 However, many kinds of real-world data are hierarchical or graph-like 255. in which case embedding into non-Euclidean space can outperform the standard Euclidean embedding. Hyperbolic spuce such an embedding target of particular interest, showing impressive performance on many tasks such as taxonomies, link prediction and inferring concept hierarchies [27 28 15).
Hyperbolic space is helpful for many types of embeddings because of its constant negative curvature, as distinguished from Euclidean space with zero curvature. This negative-curvatue geometry endows hyperbolic space with many useful properties not present Euclidean space. For example, the volume of ball in even two-dimensional hyperbolic space increases exponentially with respect to the radius, as shown in [9, Euclidean space. This makes it possible to embed more instances in the hyperbolic ball than Euclidean ball with the same radius, making it ideal for structures like trees where the number of objects at distance d from any given object can grow exponentially with d. Reasoning from this intuition, the hyperbolic space "looks like" finite-degree tree and can be regarded as a continuous version of trees (6). The combination of low dimension (which facilitates learning) with high volume (which increases representational capacity) makes hyperbolic space inherently well-suited for embedding hierarchical structures data like trees and graphs.
contrast to the polynomial rate at which balls grow in
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, the advantages of hyperbolic space do not come for free. The large volumes that are so beneficial from a saabedding-appcciii perspective create unavoidable numerical problems. Informally called "the NaN problem" [37 34], representing hyperbolic space with ordinary floating-poin point num- bers can cause significant errors and lead to severe numerical instability that compounds throughout training, causing NaNs to pop out everywhere in the computations. Common models of hyperbolic space used to learn hyperbolic embeddings using floating-per -oaiing-poitt&o arithmetic, such as the Poincaré ball model [27 15| and the Lorentz hyperboloid model [28]. all suffer from significant numerical errors. These errors originate in the ordinary Moating-point representation, and are further amplified in subse- quent computations by the very ill-conditioned Riemannian metrics involved in their construction. Yu and De Sa (37] show that in the Lorentz hyperboloid model, the error of representing an exact point with ordinary floating prating-point numbers becomes unbounded as the point moves away from the origin, which is what will happen in most embedding tasks: points unavoidably move far away from the origin as more and more data instances crowd in.
Many efforts and compromises have been made so as to solve or alleviate the 'NaN' problem. One commonly adopted technical solution firstly exploited in (35] is using an appropriate scaling factor, i.e., scale down all the distances by the scaling factor before embedding. then recover the original distances by dividing to the scaling factor. However, this scaling will increase the distortion of the embedding, and the distortion gets worse as the scale factor increases. Sala et al. [4]] show that this sort of tradcoff is unavoidable when embedding in hyperbolic space: one either choose to increase the number of bits used for the floating point numbers or increase the dimension of the space, and this is independent of the underlying models. However, increasing the dimension is not panacea, as the 'NaN' problem still exists in high dimensional space (albeit to a lesser degree).
A straightforward solution to the 'NaN' problem would be to compute with high precision floating- point numbers, such as BigFloats (specially designed with a large quantity of bits), as adopted in the combinatorial construction of hyperbolic embedings in (34], where floating-poit ppont numbers with thousands of bits are used with the support of Julia 44. However, there are two evident problems with representing hyperbolic space using BigFloats. Firstly, BigFloats are not supported on ML accelerator hardware like GPUs: computations using BigFloats on CPUs will be slow and hence not realistic for many meaningful tasks. Secondly, BigFloats currently not supported in most deep learning frameworks even on CPUs, so one would need to develop the algorithms from scratch so as to learn over hyperbolic space, which is tedious and fraught with the danger of numerical mistakes.
hybrid solution to the 'NaN' problem proposed by Yu and De Sa (37 is to avoid footing-point arithmetic much possible by using integer arithmetic instead-as integer arithmetic can be done exactly. Their tiling-based model works by decomposing hyperbolic space into a tiling: the product of a compact fundamental region (which can be represented in floating-point with bounded error) and a discrete group (which supports integer computation). We can also interpret their approach as decomposing large floating -pont number into a multiply of small floating-point number with large integer number using some group actions [3] 33). This allows for a guarantced bound on the numerical error of learning in hyperbolic space. However, their approach is limited somewhat in that its guarantees apply to loss functions that depend only the hyperbolic distance between points, and their best pest-performing model (their L-tiling model) is limited to 2-dimensional space. A bigger issue with this type of approach is computational: the big-integer matrix multiplication involved in the model is not supported on GPUs and not yet implemented in many deep learning frameworks such as Py PyTocc (29] and TensorFlow (I. This effectively prevents the method from being used in training of complex models that depend on GPU acceleration, such hyperbolic neural networks 14
10 23
In this paper, we propose a more direct way represent and learn in hyperbolic space without sac- rificing either accuracy guarantees or GPU acceleration. To achieve high precision computations and controllable numerical errors, we choose represent hyperbolic space with nompoete floating- booating-point numbers (MCF) [1 32 19 36), an alternative approach different from BigFloats where number is expressed as unevaluated sum of multiple ordinary foating-poine numbers. We make the following contributions:
We propose representing hyperbolic space with the Poincaré upper-half space model for opti- mization in section 3, and show how to represent it with MCF secttiion 41oo eliminate the 'NaN' problem.
2

---

We provide algorithms for computing with these MCF that are adapted to hyperbolic space in /ssectonn and |section 6 where we prove numerical errors can be reduced to any degree by simply increasing the number of components of the MCF.
We experimentally measure our model on embedding tasks across several datasets, and show that one can gain more learning capacity (compared to models that use ordinary floating- point numbers) with only a mild computational slowdown on GPUs in sessecttio 7, meanwhile significantly faster than prior high precision hyperbolic models.
2 Related Work
The non- Euclidenn geometry of hyperbolic space offers many distinctive properties useful in machine learning. It is well-suited to model hierarchical structures such as trees and more complex graphs: for instance, Sala et al. (34) show that tree can be embedded into a 2-dimensional hyperbolie space with arbitrarily low distortion, and Gromov [16] shows that any finite tree can be embedded into a finite hyperbolic space such that distances are preserved approximately.
propose to embed symbolic data into the Poincaré ball model of hyperbolic space for learning the hierarchical representations, where the Poincaré ball embeddings outperform Euclidean embeddings significantly on hierarchical data in terms of both representation capacity and generalization ability. Subsequently, Ganea et al. [15] further improve the empirical results of Poincaré ball embeddings on directed acyclic graphs by theoretically grounding entailment using the hierarchical relations. Later work uses other models of hyperbolic space (28 17 besides the Poincaré ball model for various purposes. For example, the Lorentz hyperboloid model used in Nickel and Kiela (28 to learn continuous hierarchies from large-scale unstruetured data, was observed to be substantially more efficient and numerically stable. Along a different direction, hyperbolic embeddings can be used in many down-streaming tasks, by simply treating the hyperbolic embedding as a layer to form neural networks, such as the hyperbolic neural networks [4] for textual entailment
Nickel and Kiela [77]
and noisy-prefix recogmition tasks, hyperbolic attention networks [18] for neural machine translation
and visual question answering tasks, and hyperbolic graph networks 110 23 for link prediction and node classification tasks.
Although widely adopted in many applications, the 'NaN' problem in hyperbolic representations can be observed easily in practice and generally remains unsolved. Sala et al. (34 suggests that hyperbolic embeddings can have high quality on hierarchies but require large dimensions or high precision for graphs with long chains: they suggest alleviating the 'NaN' problem by using scaling factors together with BigFloats. Yu and De Sa [37 introduced tiling-based models, the first theoretical solution to the numerical error. The tiling-based models enable deriving high-precision embeddings without using high precision floating- boini point numbers.
'NaN' problem with bounded-every
In the literature of arbitrary precision algorithms, there are two different ways to achieve high precision computations, and BigFloat is not the only option. The first one is straightforward: the muitiple-digit format, which consists of sequence of digits coupled with single exponent. Examples in this category include the computation package Mathematica [20). the BigFloats format in Julia [4], and the Fortran muntiple-precisioo arithmetic packages []. The other option is the multiple-component format, in which an exact number is written as an unevaluated sum of ordinary floating-poit numbers,
each with its own significand and exponent [1] 31 32 13
3 The 'NaN' Problem
Hyperbolic space can be modelled with several well-known isomorphic models. Previous works have proposed to optimize over the hyperbolic space with the Poincaré ball model [27] and Lorentz hyperboloid model (28). In this paper, we propose to optimize within the Poincaré upper-hall half space model instead, because its properties allow for localization of potential sources of numerical error.
The Poincaré upper-half space model is the manifold (21", ,gu). where 4 {ar IR I,, > 0} the upper half space of n-dimensional Euclidean space. The metric and corresponding distance function are
du(x, y) = arcosh (1+
x y112
9e x²
9u (x)
2x U/o
3

---

Averaged Representation Error
Numerical Error of RSGD
16'
10
2MCs-Hlllspaaee
Haltspace
10:9
10
3MC Half-aafeeace
10
10a
2MCs-Hellspece
Halfspace
10-19
10-11
10
10t4
50
100
150
200
20
40
60
300 120
distance-to-arigin
distance-to-origin
Averaged representation error d(æ,, ((())) as æ moves away from the origin in halfspace models.
Figure 1:
Figure 2: Numerical error d(y, y') of the RSGD algorithm as moves away from the origin in halfspace models.
where ge is the Euclidean metric. Notably, the tangent space of the upper-half space model is the same as the ambient vector space, which makes it easier and numerically stable to derive Riemannian gradients without projection the tangent space. In the two dimensional case, the Poincaré upper-half space model can be interpreted as mapping on the complex plane (the "half-plane model").
Numerical error analysis. Yu and Sa 37 shows that in the Lorentz hyperboloid model of the hyperbolic space, the error of representing an exact point with ordinary floating-point fi(x) is unbounded and proportional to the distance to the origin d(æ:, O). Here, as baseline to compare MCF methods to, show that the same sort of representation error d(x, fl(x)) happens when representing points in the Poincaré upper-half space model with ordinary floating-pol point numbers.
Theorem The representation error of storing a particular point x E U using floating- ppintss fl is on(2) (x) = (xx fl(z)), and the worst case representation error defined a function of the distance-to-owe toiiinn in the Poincaré upper-half space model is
max ó =El du (s,
5n(2) = arcosh(1 + 2nachhine cosh (ds))
where Cmachiie is the machine epsilon of the underlying floating-point arithmetic. This be- comes 5g machiiee + olc machine) if log(1/ and 8a 2d + o( cx)(-2d)) if d 2 (mmohin/))))))
We plot the averaged representation error and the 'NaN' problem practically in Figure I the distance error d(x fl(x)) when a is represented as fz(x)) using floating-poin point. The enror explodes at at distance of around 55 from the origin, which will then potentially cause NaNs subsequent computations.
Identify potential numerical errors. Optimizing in the Poincaré upper-half space model will typically push æ away from the origin, with Z; * n being large floating- point numbers and x, being floating-point numbers close to 0. Hence, the subtraction of two big floating-point numbers in ||æ - 22 of the distance calculation leads to catastrophic cancellation and accounts for a large part of the numerical errors. We can localize this part of the numerical errors easily in simple subtractions in the Poincaré upper-half space model. (For comparison, in the Lorentz model (28). the multiplication Lorentzian scalar product accounts for the major numerical errors in distance computations.)
RSGD in the Poincaré upper-half space model. We are interested in gradient-based optimizations within the Poincaré upper-half space model, hence we provide Riemannian stochastic gradient descent (RSGD) algorithm for different learning algorithms in the hyperbolic space. For each E 4tth in the Poincaré upper-half space model, let f : 2tt + I be a smooth real-valued loss function over the manifold, denote Vzf to be the Euclidean gradient of w.r.t. In order to do RSGD in the Poincare haper-half space model, we firstly derive the Riemannian gradient the tangent space from the Euclidean gradient using the pull-back metric computed as:
grad f 2n V f

---

then we take the learning rate 7) into consideration, denote ー grad f. Next, we will need the exponential map Exp in the Poincaré upper-hall half space model, which takes tangent vector in the tangent space to z' on the manifold 21th via the following arithmetic:
in
2
+
Us.
< m
tanh
Un
Zn
(2)
cosh
sinh
where 8 VoTu. We also provide a more numerically stable form of this exponential map in the Appendix. As an example, assume exact point æ is given, we do RSGD following the above arithmetic and get the accurate y as:
y = Exp,,-7) gradg..).
We derive a y using ordinary floating-point arithmetic and compute the distance error between the exact and y'. In Figure 2| we show how this error (y. y') varies as the starting point æ gradually moves away from the origin. At a distance of around 60, the halfspace RSGD algorithm will be numerically unstable with numerical errors large enough to cause NaNs.
In the Poincaré upper-half space model, the major part of the numerical errors in the exponential map happens in [Equation| I] when a big floating- point number added to a small floating point gradient number. This lets us localize the numerical errors within simple addition operation in the Poincaré upper-half space model; in comparison, for the exponential map in the Lorentz model (8). multiple operations cause numerical errors. Hence, we propose use multiple-compneent floating-poii poatin numbers in the Poincaré upper-half space model to avoid the numerical errors in addition and subtraction, rather than base our methodology in other models like the Lorentz model.
4 Hultiple-Componee Floating-point (MCF)
Currently, most high precision algorithms are developed with one of two approaches: (1) the standard multiple-digit "BigFloat" approach, involving a sequence of digits coupled with single exponent and (2) the multiplc-componeet
format (MCF), which uses unevaluated sums of multiple ordinary floating- point numbers. The multiple-digii approach can represent compactly a much larger range of numbers, whereas the multiple-component approach has an advantage in speed, as it better takes advantage of existing doating-poim accelerators. Since speed and scalability is critical for MI. applications, MCF is to be preferred here. In this section, we will detail how MCF works.
For machine which supports p-bit Moating-point number arithmetic, exact arithmetic often produces values that require more than p-bits to express and store. In the multi-component floating-point format, each arbitrary precision value is expressed as expansion 36
x Fn
32 + 21
where each v; is called component of and is represented by floating- ppint number with a p-bit significand. As the structure requirements of this expansion definition, all components are ordered by magnitude (from largest x,, smallest æ1). What's more, every two different components 24, 4 required to be non non-overlapping: the least significant nonzero bit of x; is more significant than the most significant nonzero bit of 2; or vice versa.
Multiple-component floating- point format allows roundoff error to occur when performing exact arithmetic, then accounts for it afterwards by adding more components. To measure roundoff quickly poating-point and correctly, the algorithms presented herein rely on the assumption that ordinary floating point ops performed with standard to-nearest rounding. MCF allows the boundaries between components to wander freely, and boundaries are still enforced but can fall at any bit position. For example, the floating-poinn
sum of 2300 + 2- 2-300 will be represented by (2300 2 2-300) in the multiple-componet componeet approach may store numbers with fewer bits, stored as two words of memory, whereas the multiple-dije digit approach will at least 601 bits store the sum 36..
format. In this sense, the
we see that the 'NaN' problem occurs at distance around 50 to the origin, thus for the representation of hyperbolic space, the range of distances not the main concern, rather, the issue is that when points are far from the origin, small error in magnitude causes high numerical
From Figure
5

---

Algorithm 1: Two-Sum
Algorithm 2: Grow-Expansion
Input: p-bit floats a, b, where p
Input: p-bits expansion e, p-bit float b initialize Qo < for to do
I f- flaa + b)
Ovirtual fl(r a)
Ovirtual f- fl(x bvirual)
(Qi, h.) t Two-Sum(Qi-L,ee)
Droundoff fl(b Ovirtal)
end for
Groundoff f fl(a Ovirtual)
1m++1 < Qm Return: h
y Aroundoll + broundot)
Return: (r. y)
error in subsequent computations. Multiple-component floats, which can have very small numerical errors, will thus be better-suited to represent hyperbolic space compared the multiple format.
Multiple Multiple-componett floating-polt point arithmetic can be faster than multiple-digit arithmetic because the latter requires expensive normalization of results to fixed digit positions. MCF can also be implemented to run efficiently on GPUs because their unevaluated-sum structure is amenable to parallelism. This allows learning applications that use MCF to enjoy not only accurate results but also benefit from the hardware acceleration of GPUs.
Computing with MCF
We provide some basic numerical operations for computing with multppl--componett floating-point numbers. To start with, we consider the sum of two p-bit floating-pon point numbers to form a non- overlapping expansion.
Theorem (27 36y. For floating point numbers a, b, Alg. produces a non-overlapping expansion (z, v) such that + 6 + y, where is an approximation to a + and y is the roundoff error. Particularly, when exact rounding is adopted, the roundoff error is bounded as
1ul S ulpp(A(a + b)), lyl S min([a],1b])
2
where ulp(x) is the unit of the least precision of x.
This theoretical bound on the roundoff enror y serves an important role in computations involving Alg. (most MCF algorithms). Now we can derive an expansion by adding two p-bit floating-pois values with this algorithm, next, need to add single Doating-poine number to an expansion. Alg. shows how to add a single p-bit value to any arbitrary precision value expressed as an expansion.
Em es be a non-overlupping m p(Z 3)-bit components expansion, soried in increasing order, except that any of the e; may be zero. Let b be p(23)-bit value, then Alg. 2 produces non-overlapping + emponents expansion h Dm+1 h e + b, where the components are also in increasing order, except that any of them may be zero. Notably, Q; in Alg. P can serve as an approximate sum and the first components of
Theorem 33 Let e
As result of Alg. 2 addition of a value to mn-components expansion will grow the expansion and outputs an expansion with mn + 1 components. However, there are no constraints on the number of components, then different values will be highly irregular and vary a lot, which will slow down the computations and make the algorithms much more complicated. Hence, in our implementation, rather to grow the number of components without any constraints, would like to fix the number of components for all expansions we may use. With Alg. 3 we can renormalize an m + expansion back to an components expansion.
Priest proves that if the input expansion of Alg. 3 does not overlap by more than 51 bits, then the algorithm works correctly. This condition holds when ordinary boating-point numbers are used. Table summarizee MCF algorithms used in this paper, some them detailed in the Appendix. Note that firstly these MCF algorithms can be easily vectorized to apply on high dimensional vectors, secondly, they are linear in the number of components (quadratic for Scale-Expane (cale-Expansion) and dimension, hence enjoy great speedup.

---

Table 1: MCF algorithms used in the paper
Operation
Function
Example Usage
Two-Sum
sum of two floats
MCF algorithms RSGD, update parameters distance calculation gradient calculation, RSGD RSGD, reduce # components
Grow-Expansion
add float to an expansion
Add-Expansion
sum of two expansions multiply a float to an expansion reduce # components of an expansion
Scale-Expansiog
Renormalize
6 Learning using MCF
We solve the 'NaN' problem in the Poincaré upper-half half space model using multippe-compoon arithmetic in the addition & subtraction computations. As analyzed in Sec. we only need to use m-multiple- component floating-point numbers for the first ordinates of the model, denoted as m--MM-Halfspace.. We will mostly compute with MCF arithmetic (in Table D for the addition & subtraction involved in the compu- tations, and leave the rest of computations ordinary Boating-poing arithmetic.
floating point
Algorithm 3: Renormalize [32]
Input: (m + 1 1)-oopponents expansion
(ag: 01," (0m) in decreasing order.
initialize $ + am k +
for i to do
(s, (.) < Two-Sum(a;-1,
end for
for i = to m do
(s, e) Two-Sum (s),)
For example, compute the distance between æ, y Ln as:
if e * 0 then
by f
(x. y) = arcosh 1+ Add-E Add--xppassion(z; -
8 x-
k t 1:
2x,
end if end for Return: (bo, bi, ... bm-1)
where we add two expansions æ, - y to get the summed expansion and then take the first, largest component as an approximation of the scalar ||æ: y||- Further
more, in Appendix show how do RSGD using the multi-component floating-poin numbers in the m- XMC-Halfspace model.
When we compute with the introduced multi-components floating-poine poonn numbers in the model, we show theoretically the worse numerical representation error Theorem 4
Theorem 4 The worst case representation error of storing an exact point æ E U with m-multi- component Hoating-point expansion (x (m) origin d is
x (2) x())) defined as function of the distance-to.
8 arcosh (1+ emachine machine (1 Cmachine) cosh?(d)) (d))
22m
where Cmachine is the machine epsilon. This becomes 5, 2c machine + ole machine) if d < m log(1/1 moachine) and 5,- = 2d 2m bog(Cmachine/" 2)) + olc machine exp( 2d)) if d 2 m (mamkine))
Table 2: Datasets Information
Table Embedding performances on Mammals
Datasets
Nodes
Edges
Model
MAP
MR
WordNet [2
74374
75834
Halfspace
92.07%++1..00 % 93.55%
1.600-t0.79
2-xMC-Halfspac
1.430
I, Nouns
82115
769130
4, Verbs
13542
35079
Lorentz
85.75%++2.30%
1.857=4.78
L Mammals
1181
6541
L-Tiling
91.49%
1.645
Gr- Q2-]
4158
13422
H-Tiling
91.60%
1.559-10.44
7

---

WORDNET NOUNS
WORDNET VERDS
GR-QC
DIMENSION MODBLS
MAP
MR
MAP
MR
MAP
MR
LORENTZ
15.6110.37%
0..5
56.76:1.5229
4.1820.07
55.934103225
718111124
L-TILING
23.
34.22=1103
63.08-0.311
3.28+0.03
56.0740.21%
72.5342.08
2
II-TILING
23.34.1..19%
34.30-0.49
64.26110.00%
3.2311.05
35.95110300
71.78.1.02
HALFSPACE
23.31=0.17%
34.81=0.26
63.65=0.329
3.3620.07
55.60:2035%
74.29:1132
2-XMC-HALISPACE
24.42:+0.11%
34.01=0.17
64.88=0.22 25%
3.18=0.05 05
36.35++0.38%
11.81+1.12
LORENTZ
34.8210.388
0.528=0.23
89.72:00,00 0.4%
1.5210.00
71.16:10.33%
33.66.11.23
H-TILING
04.90=0.088%
7.529=0.12
00.133:0000 08%
1.4620.00 00
70.89:10.15%
32.99:+0.52
5
HALISPACE
74,89=00,14 14%
7.388=0.08
89 00.9900.211 21%
1.51+0.01
71.10++0.119
32. 09:
H-XMC-HALFSPACE
75.05=0.12%%
7.377=0.12
90.2550.088
1.4100001
71.2110.24%
31.89:0.71
LORENTZ
78.43=+0.42%%
6.148=0.15
90.71 13%
1.4100.00
72.84=0.13%
28.53=0027
H-TILING
78 18.40+00.22 22%
6.229=0.13
62:022000 02%
I 1.40=00
72.57-00.00 09%
28.50+0.31
10
HALPSPACE
78.39:10. 12%
6.227-0.21
90.71 1%%
1.39
72.66-40..1
28.56-10.24
2-XMC-HALISPACE
78.46:20.08%
6.136=0.14
90.71=0.04%%
1.39
72.69+400099
28.57:0.32
Table 4: Learning experiments different datasets. Results averaged over 5 runs and reported in mean+std style. Bold numbers show the best performance among all models.
Hence, there's 's region around the origin whose radius is proportional to the number of components m, where we can confident there are no numerical issues. This is the scaling we' d expect, and is in line with the results from B4. In Figure I we plot the averaged representation error d( MCF(x)) when æ is represented using 2-component floating-point The error will not explode until distance of 125 from the origin simply by using 2 components, compared to the distance of 55 for vanilla halfspace.
Particularly, we also show the numerical errors of the adapted RSGD algorithm in the 2-xMC- Halfspace model in Figure 2| with way smaller error compared the increasing numerical errors in Poincaré upper-half space model using ordinary floating numbers. Practitioners can choose the number of components according to the desired precision requirements, yet many applications would get full benefits from using merely small multiple of (such as two or three) components.
As matter of fact, MCF can be more generally adopted in many operations, in all hyperbolic models and different generic loss functions for better performance. Hence we also implement the model with all coordinates represented with MCF, denoted M-MM--Halspace. We defer the discussion of this model to Appendix since it is more sophisticated by making use of the Scale- Exaee-Expansion algorithm.
7 Experiments
Firstly proposed in Nickel and Kiela 27 hierarchical structure such as taxonomies, producing results that outperform Fuclidean embeddings. Motivated by this, conduct embedding experiments on datasets including the Gr-Qc and commonly used WordNet Nouns, Verbs and Mammals dataset whose statistics are shown in Table 2] We are interested in two aspects of the proposed MCF-based models in practice: firstly the capacity of the models, and secondly the running speed of model training and optimization.
hyperbolic embedding used to embed data with
Reconstruction. We focus the tasks which can show the capacity of the models. Given an observed transitive closure D = {u, v)} } of all objects, we embed all objects into hyperbolic space and then reconstruct it from the embedding. Hence, the error from the reconstructed embedding to the ground truth will be reasonable measure for the capacity of the model and reflect how the underlying seatiing-poin arithmetic may affect the performance. Specifically, we learn embeddings of the transitive closure D such that related objects are close in the embedding space. To do this, we aim minimize the loss introduced in [27]
d(u,.)
(())= = Σ log
EV'NNW) c(u((o"")
(M,N)D
where (uu) { v) D) U {u} is the set of negative examples for (including u). We do negative sampling randomly per positive example during training for different datasets.
We implemented the upper-half space model and xMC-Halfspace models trained with RSGD in our experiments, as for baselines, we consider the current state-of-the-art L-tiling models, H-tiling models (37) trained with RSGD and the Lorentz model (28). Models were trained using ordinary
8

---

BATCHSIZE=32
BATCHSIZE=64
BATCHSIZE=12 128
DATASET
MODELS
2D
5D
10p
2D
5D
10p
2D
10p
LORENTZ
57.37
60.00
53.42
27.38
27.28
74
9.37
9.14
HALFSPACE
118.7
119,9
119.7
40.2
40.3
39.3
17.4
17.4
20.4
WORDNET NOUNS
L-TIINNG (CPU)
205
203
203
185
185
182
161
158
158
H-TILING (CPU)
146
188
238
107
156
212
93
129
177
X-MC-HALSSRCC
272
284
296
118
136
121
54
58
68
LORENTZ
3.21
3.19
3.25
0.93
0.93
0.96
0.42
0.41
0.41
HALPSPACE
5.65
5.68
5.71
1.69
1.66
1.66
0.78
0.75
0.77
WORDNET VERBS
(CPU)
7.46
8.87
10.76
5.56
7.85
8.54
5.06
8.59
RRMC-HALPSPACE
12.38
12.14
12.83
6.19
5.86
6.42
1.80
1.84
2.09
HALESPACE
4.29
4.36
4.31
2.13
1.91
1.88
0.559
0.63
0.67
LORENTZ
2.45
2.61
2.44
0.67
0.76
0.67
0.36
0.36
0.36
GR-QC
H-TILING (CPU)
5.99
7.22
10.12
4.39
6.45
8.12
4.16
7.32
2-XMC- HALPSPACE
9.52
9.96
10.41
5.42
5.57
5.94
1.46
1.63
1.79
Table 5: Training time (seconds per epoch) for different models on different datasets. Results are averaged over 10 epochs. Performances of low precision models L are separated from that of high precision models in the table.
float64 with the same hyper-parameters starting from same initializations of parameters, see Appendix for more implementation details. To evaluate the quality of the embeddings, we make use of the standard graph embedding metrics in [6, For an observed relationship (u, v), we rank the distance d(u, v) among the set {d(u, ('), r²) E D)}, then we evaluate the ranking on all objects in the dataset and record the mean rank (MR, smaller=betteer) well as the mean average precision (MAP, larger=bbetter) of the ranking.
We firstly evaluate different 2-dimensional embeddings on the light-scale Mammals dataset. As shown 3 we choose 2 components for the MCF-based models. The proposed upper-half space model already outperforms all previously proposed baseline models. In particular, the xMC-Hallspacc model further improves the embedding performance and achieves a 2.25% MAP improvement on Mammals compared to the best baseline models.
We present the large scale experiments other three datasets in Table 4 These results show that MCF-based models generally perform better than baseline models in various dimensions with respect MAP and MR, particularly in 2 dimensional hyperbolic space, since higher dimension can alleviate the 'NaN' problem to some degree. On 2 dimensional embeddings of the largest WordNet Nouns dataset, MCF-based models gain large 1.03% MAP improvement compared to the L-tiling model and 1.1 11% % MAP improvement compared to the upper-half space model.
The limitation of the work is that in some cases of embedding problems that stay close the origin, MCF will give no improvement over plain half space because it was already numerically accurate enough, also method will eventually break down at very large distances due to overflow or underflow of the floating point exponent.
Training time cost. Running the model on GPUs confers important training advantage for modern machine learning tasks. In order to provide comprehensive comparison result, train most models in our experiments on GPUs including MCF-based half space models, upper-half space model and the Lorentz model. As for the L-tiling and H-tiling model, since big-integer matrix multiplications are not supported in GPUs, we train both models with CPUs. For all timing results within this section, we use GPU: GeForee RTX 2080 Ti and CPU: Intel(R) Xcon(R) Gold 6240 @2.60GH2
Note that negative sampling size and batch size can make a great difference to the timing performance over CPUs and GPUs Herein, we fix the negative sampling size to be 50 and only vary the batchsize in 32, 64, 128. Readers may question the performances of the model as the batchsize changes, we note that with simple scale of the learning rate, can achieve comparable results for different batchsize, detailed in the Appendix. We report the training time (seconds per epoch) for different models on three different datasets in Table 5 We can conclude that:
On large-scale datasets or large batchsize (e.g. 128) training, MCF-based models (high precision) can be trained efficiently, with timing close to that of models using ordinary floating-point.

---

MCF-based models (high precision) can run on GPUs, enjoying great training speedup compared to other high precision models such as the L-tiling and H-tiling models which can only run over CPUs. As matter of fact, on WordNet Nouns, relatively it takes MCF-based models around 2/3 less time and saves 30.27 hours finish 1000 epochs training (batchsize 128), compared to the H-Tiling model with best MAP performance.
More experiment details are in the Appendix. We will release our code in PyTorch publicly for reproducibility, and in hopes that practitioners can use MCF to reliably compute in hyperbolic space.
8 Conclusion
In this work, we proposed upper-half space model of hyperbolic space and presented new multi- component floating- point representations. Our approach avoids the numerical errors inherent to popular models of hyperbolic space, such as the Lorentz model, while supporting efficient compu- tations on GPUs. This allows our MCF approach to effectively trade off computational cost and numerical accuracy for learning over hyperbolic space.
Acknowledgments and Disclosure of Funding
This work is supported by NSF IIS-2008102 This work was supported in part by gift from SambaNova Systems, Inc. The authors would like to thank Aaron Lou and anonymous reviewers from NeurlPS 2021 for providing valuable feedbacks earlier versions of this paper.
References
[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp. Geoffrey Irving, Michael Isard. Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore. Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens. Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg. Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large- scale machine learning on heterogeneous systems, 2015. https://////e tensorflow org/ Software available from tensorflow.org.
[2] David H Bailey, A fortran 90-based multiprecision system. ACM Transactions Mathematical Software (TOMS), (1(4)3379-3 1995.
[3] Alan F Beardon. The geometry of discrete groups, volume 91. Springer Science & Business Media, 2012.
[4] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. Julia: A fresh approach to numerical computing. SIAM review, 59(1):65 98, 2017. URL /ttptttt////oooog/g///// 141000671
[5] Antoine Bordes, Nicolas Usunier, A Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pages 2787-2795 2013.
[6] Brian Bowditch. A course on geometric group theory. Mathematical Society of Japan, of MSJ Memoirs, 2006.
[7] Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher Manning. A large annotated corpus for learning natural language inference. In Proceedings of the 2015 Con- ference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, 2015.
[8] Richard P Brent. fortran multiple-precisenn arithmetic package. ACM Transactions on Mathematical Software (TOMS), 4(1):57-70, 1978.
10

---

[9] James W. Cannon, William J. Floyd, Richard Kenyon, Walter, and R. Parry. Hyperbolic geometry. In In Flavors of geometry, pages 59-115. University Press, 1997.
[10] Ines Chami, Rex Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances neural information processing systems, 32:4869, 2019.
[11] Theodorus Jozef Dekker. A floating Mooainng-point technique for extending the available precision. Numerische Mathematik, 18(3)224-22) 2422 1971.
[12] Christiane Fellbaum. WordNet: An Electronic Lexical Database. Bradford Books, 1998.
[13] Steven Fortune. Progress in computational geometry. Directions in Geometric Computing, 3: 81-128, 1993.
[14] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. In Advances neural information processing systems, pages 5345-5355, 2018.
[15] Octavian-Euue Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In Proceedings of the 35th International Conference on Machine Learning, 2018.
[16] Mikhael Gromov. Hyperbolic groups. Essays in group theory, page 75-263, 1987.
[17] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature repre- sentations in product spaces. In International Conference on Learning Representations, 2019.
URL http:::///ppeeeeereeee wwt.:eetteetooorrrddddddeeeeeeee
[18] Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, et al. Hyperbolic attention networks. International Conference on Learning Representations, 2018.
[19] Yozo Hida, Xiaoye S Li, and David H Bailey. Library for double-double and quad-double arithmetic. 2007.
[20] Wolfram Research, Inc. Mathematica, Version 12.2. URL wwtp:://wwwwolffr..m com/ mathematica Champaign, IL, 2020.
[21] Donald Ervin Knuth. The art of computer programming Seminumerical algorithmm, volume Addison-Wesley, 1971.
[22] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions Knowledge Discovery from Data (TKDD), 1(1):2, 2007.
[23] Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. arXiv preprint 1910 / 2892, 2019.
[24] Tomáš Mikolov, Wen-tau Yih, and Geoffrey Zweig. Linguistic regularities in continuous space word representations. Proceedings of the 2013 conference of the north american chapter of the association for computational linguistics: Human language technologies, pages 746-751, 2013.
[25] Shigeru Miyagawa, Robert C Berwick, and Kazuo Okanoya. The emergence of hierarchical structure in human language. Frontiers in psychology, 1,71,2013
[26] Maximilian Nickel, Lorenzo Rosasco, and Tomaso Poggio. Holographic embeddings of knowledge graphs. In Thirtieth Aaai conference on artificial intelligence. 2016.
[27] Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6338-6345 6344- Curran Associates, Inc., 2017.

---

[28] Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the Lorentz model of hyperbolic geometry. In Jennifer Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 3779-3788. PMLR, 2018.
[29]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vitioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8035. Curran Associates, Inc., 2019.
[30] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532-1543, 2014.
[31] Douglas Priest. Algorithms for arbitrary precision floating point arithmetic. University of California, Berkeley, 1991.
[32] Douglas M Priest. On properties of floating point arithmetics: numerical stability and the cost of accurate computations. PhD thesis, Citeseer, 1992.
[33] Godement R. Fuchsian groups Analysis IV. Universitext. 2015.
[34] Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoffs for hyperbolic embeddings. Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 4460-4469, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
[35] Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, pages 355-366. Springer, 2011.
[36] Jonathan Richard Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry, 18(3):305-365 1997.
[37] Tao Yu and Christopher M De Sa. Numerically accurate hyperbolic embeddings using tiling- based models. In Advances in Neural Information Processing Systems, volume 32, pages 2023-2033. Curran Associates, Inc., 2019.
12


Reviews:
[{"review_id": "yKMAf6eM58o", "reviewer": "Reviewer_gMed", "summary": "To solve the 'NaN' problem in hyperbolic embeddings, the paper proposes to learn the hyperbolic embeddings in the Poincare upper-half space model using multi-component floating-point (MCF). Theoretically, the paper proves that numerical errors can be reduced to any degree by simply increasing the number of components of MCF. In experiments, it shows the proposed MCF can have better results while not compromising much on efficiency.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The paper focuses on the numerical issues in the hyperbolic embeddings. The task and experimental settings closely follow the previous work on tiling-based models, but the proposed method is novel since it uses the Poincare upper-half space to learn the hyperbolic embeddings and it utilizes MCF to alleviate the numerical errors. The theoretical contribution is solid and clearly presented. However, the improvements in empirical evaluation is very small. The proposed method is quite close with H-Tiling. The gap is smaller than std sometimes.\n\n*Post-rebuttal*: I appreciate the response of the authors. I am keeping my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors addressed the limitations. The potential negative societal impact is not discussed since they thought there are none, which I agree.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "nhdih9BkMJ9", "reviewer": "Reviewer_FLfq", "summary": "Solving \"the NaN problem\" in the Poincaré upper-half space model using multiple-component floating-point arithmetic.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "In this paper, the authors propose a simple, feasible-on-GPUs, and easy-to-understand solution for numerically accurate learning on Poincaré upper-half space model using multiple-component floating-point arithmetic in the addition & subtraction computations.\n\nThe work is technically sound and well organized. \nBut (1) Poincar\\'e Ball model and Lorentz model are more popular in hyperbolic embedding, how about using MCF on these models? (2) Many works use SGD or Adam for optimization, how about using these optimizers?\n\nTotally, the work is new and important to the research community.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 Hours"}, "extra_text": {}}, {"review_id": "H2lLN_HoEgc", "reviewer": "Reviewer_72MY", "summary": "This paper proposes a model for hyperbolic space using multi-component floating point in the Poincare upper-half space model which can be supported on GPU and with small numerical error. Experimental results show good training time performance. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This paper offers a new model to support hyperbolic space multi-component floating-point representations. The proposed method offers good trade-off between numerical error magnitude and hardware cost. This paper is well organised for readers to comprehend the problems and the proposed solution. The authors provide enough background discussing the related models and their limitations in computational precision and existing framework support.  The proposed algorithms is clearly demonstrated with sound mathematical analysis and supported with experimental results comparing training time on several graph-related data sets. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author does mention that one of the limitation is that some  embeddings problems may not benefit from the proposed method.\n\nSome questions and suggestions:\n1. Can the proposed method be possibly benchmarked for its performance on model trained using it? Such as model accuracy. \n2. While the authors does provide a thorough introduction on multi-component fp representations, a figure illustrating it directly would be better.\n3. I would suggest to summarise or have a table for training time also in relative improvements. As it seems the saving time in training time can be huge compared to 3% improvements in MAP, which is also presented in relative comparison. \n4. Can we also have some experiments on how does the proposed method perform on problems that it may not benefit from? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new approach to numerically represent hyperbolic space with high precision using multi-component floats. Insufficient precision is known to cause problems for hyperbolic representation learning and this paper proposes an interesting method to alleviate this issue. The contributions are somewhat incremental as there exists closely related prior work (also in terms of organization of the paper) on improving numerical accuracy for hyperbolic embeddings by Yu and De Sa (2019). However, an important advantage of the proposed method is that it allows for easy GPU-training what significantly expands it applicability compared to prior work. Reviewers highlighted also the sound mathematical analysis and empirical evaluation in the manuscript. After rebuttal, all reviewers supported therefore acceptance of the paper. When preparing the camera ready version of the manuscript, please take the feedback and comment from the reviewers into account to improve the paper.
Decision: Accept (Poster)