Random Laplacian Features for Learning with Hyperbolic Space

Tao Yu, Christopher De Sa

Hyperbolic geometry has emerged as a powerful "secret sauce" for representing hierarchical and graph-structured data. Because hyperbolic space expands exponentially, it can embed complex trees and taxonomies with almost no distortion—a feat that flat, Euclidean space simply cannot match. However, building neural networks that actually operate natively within this curved space has historically been a numerical and computational nightmare.

A recent paper, "Random Laplacian Features for Learning with Hyperbolic Space" (HyLa), proposes a clever and highly effective workaround. Instead of forcing a neural network to perform complex math inside the hyperbolic domain at every single layer, the authors suggest translating the data into a flat Euclidean language just once, using a mapping that strictly respects the original hyperbolic geometry.

The Bottleneck of Hyperbolic Neural Networks

Deep learning traditionally takes place in Euclidean space. When researchers try to force hierarchical data—like citation networks, biological structures, or flight paths—into this flat world, vital structural information is lost.

To address this, Hyperbolic Neural Networks (HNNs) were developed. Unfortunately, HNNs are notoriously difficult to implement and train. They require "gyro-vector" operations (non-associative, non-commutative versions of standard addition and multiplication) at every layer. This architectural requirement leads to two major bottlenecks:

  1. Computational Overhead: Gyro-vector operations are mathematically expensive and struggle to scale to large graphs.
  2. Numerical Instability: Points in hyperbolic space can quickly "explode" toward the boundary of the space (infinity), leading to catastrophic "NaN" (Not a Number) errors during training.

The authors of HyLa asked a fundamental question: Can we achieve the representational power of hyperbolic space without the computational pain of hyperbolic layers?

The HyLa Method: A "Once and Done" Pipeline

To bypass the limitations of HNNs, the authors introduce HyLa (Hyperbolic Laplacian features). Their approach follows a streamlined pipeline:

  1. Embed: Map the input data into a low-dimensional hyperbolic space to capture the hierarchy.
  2. Translate (The HyLa Step): Use a novel random feature mapping to project these hyperbolic points into a high-dimensional Euclidean space.
  3. Process: Feed these Euclidean features into a standard, highly optimized model, such as a Simplifying Graph Convolutional (SGC) network.
Hyperbolic geometry in the Poincaré disk

HyLa acts as the hyperbolic equivalent of the famous "Random Fourier Features" (RFF) used in Euclidean kernel methods. While RFF relies on sine and cosine waves (the eigenfunctions of the Euclidean Laplacian), HyLa utilizes "hyperbolic plane waves." These are the eigenfunctions of the Laplace-Beltrami operator on hyperbolic space.

By leveraging these specific waves, the authors mathematically prove that the resulting Euclidean inner product approximates an isometry-invariant kernel in hyperbolic space. In simpler terms, the newly "flat" features still perfectly remember how far apart they were in the "curved" world, preserving the geometric prior without the ongoing computational cost.

Approximating the hyperbolic heat kernel with random features

Empirical Triumphs: Speed, Stability, and Scale

The researchers evaluated HyLa across a diverse range of benchmarks, including standard citation networks (Cora, Citeseer, Pubmed), a tree-structured Disease propagation network, an Airport flight path dataset, and several text classification tasks. The results demonstrate significant improvements over existing methods:

  • Superior Accuracy: On the highly hierarchical Disease dataset, HyLa outperformed the previous state-of-the-art Hyperbolic Graph Convolutional Network (HGCN) by a massive 12.3%.
  • Blazing Speed: By offloading the heavy lifting to standard Euclidean operations, the HyLa-SGC model was 4.4x faster to train than HGCN on the Pubmed dataset.
  • Unprecedented Scalability: HyLa successfully processed the massive Reddit dataset (over 233,000 nodes). In contrast, several existing hyperbolic baselines crashed entirely due to "Out of Memory" (OOM) errors.
  • Robust Text Performance: In inductive text classification—where the model encounters unseen words at test time—HyLa-based models consistently beat standard Euclidean GCNs, proving that word hierarchies are vastly better captured using this curved-to-flat translation.

Crucially, because the hyperbolic mathematics only occur once at the beginning of the pipeline, errors do not compound layer-by-layer. This effectively neutralizes the "NaN problem" that has long plagued deep hyperbolic networks.

Future Directions

While HyLa represents a major leap forward for geometric deep learning, the authors note a few exciting areas for future research. The current implementation primarily uses a linear Euclidean model (SGC) as the backend; exploring how HyLa interacts with deeper, non-linear Euclidean architectures could yield even richer representations. Additionally, the current method uses a Gaussian distribution for the random features to approximate a heat kernel. Future work could explore different distributions to approximate other types of hyperbolic kernels, further expanding the toolkit for hierarchical data analysis.

Summary updated

Abstract

Due to its geometric properties, hyperbolic space can support high-fidelity embeddings of tree- and graph-structured data, upon which various hyperbolic networks have been developed. Existing hyperbolic networks encode geometric priors not only for the input, but also at every layer of the network. This approach involves repeatedly mapping to and from hyperbolic space, which makes these networks complicated to implement, computationally expensive to scale, and numerically unstable to train. In this paper, we propose a simpler approach: learn a hyperbolic embedding of the input, then map once from it to Euclidean space using a mapping that encodes geometric priors by respecting the isometries of hyperbolic space, and finish with a standard Euclidean network. The key insight is to use a random feature mapping via the eigenfunctions of the Laplace operator, which we show can approximate any isometry-invariant kernel on hyperbolic space. Our method can be used together with any graph neural networks: using even a linear graph model yields significant improvements in both efficiency and performance over other hyperbolic baselines in both transductive and inductive tasks.
BibTeX
@inproceedings{yu2023random,
  author = {Tao Yu and Christopher De Sa},
  title = {{Random Laplacian Features for Learning with Hyperbolic Space}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=3pfNb4pZBNp},
}
Figure