TL;DR
Researchers from Cornell have developed a way to train hyperbolic embeddings with high numerical precision without sacrificing the speed of GPU acceleration. By representing coordinates as "Multi-Component Floats" (MCF)—sums of standard floating-point numbers—they eliminate the notorious "NaN problem" that plagues hierarchical data models, achieving state-of-the-art accuracy significantly faster than previous high-precision methods.
The Challenge: The NaN Problem in Hyperbolic Space
Hyperbolic space is the "gold standard" for embedding hierarchical data like taxonomies, syntax trees, and complex networks. Unlike Euclidean space, where volume grows polynomially with radius, hyperbolic volume grows exponentially. This makes it a perfect fit for trees, where the number of nodes also grows exponentially with depth.
However, there is a major catch: The NaN Problem. As points move further from the origin to accommodate more data, the numerical precision required to represent them and calculate distances between them explodes. Standard 32-bit or 64-bit floats eventually run out of precision, leading to "Not-a-Number" (NaN) errors and training collapses.
Previous solutions were lackluster: you could either use "BigFloats" (which are painfully slow and don't work on GPUs) or "tiling" methods (which are mathematically complex and often limited to low dimensions).
Methods: Multi-Component Floats
The authors propose a two-pronged solution to tackle this precision bottleneck:
- The Poincaré Upper-Half Space Model: While most researchers use the Poincaré Ball or Lorentz models, this paper utilizes the upper-half space model. They found that in this specific geometry, the primary sources of numerical error are localized to simple additions and subtractions.
- Multi-Component Floats (MCF): Instead of using a single high-precision number (like a 128-bit float), they represent a value as an unevaluated sum of multiple standard floats (e.g., $x = x_1 + x_2 + ...
- x_n$).
This approach is "GPU-friendly" because it relies on standard floating-point hardware. The authors adapted Riemannian Stochastic Gradient Descent (RSGD) to work with these MCF expansions, providing specific algorithms to maintain precision during gradient updates without the overhead of arbitrary-precision libraries.
Key Insights
- Localization of Error: The "aha moment" is realizing that numerical instability in hyperbolic space isn't just about the range of numbers, but the precision lost during the subtraction of two very large, nearly equal numbers. By choosing the upper-half space model, the authors could pinpoint exactly where these "catastrophic cancellations" happen and apply MCF only where needed.
- The "Sweet Spot" of Precision: You don't need infinite precision. The paper shows that using just two components (2-xMC) extends the stable distance from the origin from ~55 to ~125, which is more than enough for most massive real-world hierarchies.
- Hardware Alignment: Because MCF uses standard floats under the hood, it can be vectorized. This allows the model to run on modern GPUs, which are designed for massive parallel float operations but usually choke on custom high-precision types.
Key Results
The model was evaluated on several standard hierarchical and graph-based datasets, including WordNet (Nouns, Verbs, Mammals) and Gr-QC (a co-authorship graph).
- Improved Capacity: On the Mammals dataset, the 2-component MCF model achieved a 93.85% Mean Average Precision (MAP), outperforming standard halfspace models (92.07%) and Lorentz models (85.75%).
- Massive Speedups: Compared to previous high-precision "tiling" models that only run on CPUs, the MCF approach is a speed demon. On the WordNet Nouns dataset, it saved over 30 hours of training time for 1,000 epochs, running roughly 3x faster while maintaining better accuracy.
- Stability: The authors theoretically and experimentally proved that numerical errors can be reduced to any desired degree simply by increasing the number of components in the MCF.
Limitations and Future Work
- Extreme Distances: While MCF significantly pushes the boundaries, the model will eventually fail if points move so far that they cause an overflow or underflow of the underlying floating-point exponents.
- Origin-Centric Problems: If a specific embedding task doesn't push points far from the origin, MCF provides no benefit over standard floats and adds a small computational overhead.
- Future Directions: The authors suggest that MCF could be generalized to other hyperbolic models or even other areas of deep learning where numerical stability is a bottleneck, such as training very deep or recurrent neural networks.
Summary updated