Tree! I am no Tree! I am a low dimensional Hyperbolic Embedding

Rishi Sonthalia, Anna C. Gilbert

Introduction

Hierarchical data—such as evolutionary lineages, linguistic structures, or social networks—does not map well into standard Euclidean space. Forcing a tree structure into a flat 2D plane inevitably warps the distances between nodes. Hyperbolic space, however, is the natural geometric home for trees because its volume grows exponentially, mirroring the exponential growth of leaves in a hierarchical tree.

Despite this natural fit, current methods for "Hyperbolic Representation Learning" typically rely on heavy-duty, non-convex optimization. They treat the problem like a physics simulation, iteratively nudging points around until the distances look correct. This approach is computationally expensive, slow, and prone to getting stuck in local minima.

In this paper, the authors ask a fundamental question: Why not just build the tree first? Instead of using slow optimization to force data into hyperbolic space, they propose a "metric-first" approach. By learning a discrete tree structure that preserves data distances and then embedding that tree, their new algorithm, TREEREP, achieves up to a 10,000x speedup over previous methods while providing better representation quality and rigorous geometric insights.

The TREEREP Algorithm

The authors introduce TREEREP, a recursive, divide-and-conquer algorithm that takes a distance metric as input and outputs a representative tree. The algorithm operates on several key principles:

  1. The Metric-First Approach: Rather than embedding points directly into a manifold, TREEREP focuses on the underlying metric. If the data is inherently "tree-like" (quantified mathematically by Gromov’s $\delta$-hyperbolicity), the algorithm can reconstruct the tree structure that best represents those distances.
  2. Universal Trees and Seven Zones: The algorithm begins by selecting three points and building a "universal tree" (a simple star graph with a central node). For every other point in the dataset, TREEREP determines which of "seven zones" it belongs to relative to the initial three points. This acts as a highly efficient geometric sorting mechanism.
Universal Tree and Node Placement
  1. Steiner Nodes: Crucially, the algorithm introduces "Steiner nodes"—extra junctions that were not present in the original data. These hidden nodes (like a "common ancestor" in a phylogenetic tree) are essential for maintaining correct distances and reducing distortion.
  2. Sarkar’s Construction: Once the discrete tree is built, the authors utilize a known mathematical technique called Sarkar’s construction. This allows them to snap the tree into hyperbolic space in linear time with near-zero additional distortion.

Evaluation and Key Results

The researchers evaluated TREEREP across three distinct categories of data: synthetic data sampled from hyperbolic manifolds, biological data (phylogenetic distances and single-cell RNA sequencing), and unweighted graphs (such as C. elegans neural networks and Wordnet).

The results demonstrate significant improvements over existing state-of-the-art methods:

  • Massive Speedups: By using geometric properties (Gromov products) to sort points into tree branches, TREEREP bypasses iterative optimization entirely. This makes the algorithm embarrassingly parallelizable. In practice, TREEREP is over 10,000 times faster than popular optimization methods like Poincaré Maps or Lorentz Maps. Datasets that previously took hours to embed are processed in seconds.
  • Lower Distortion and Higher Precision: Despite its speed, TREEREP produced embeddings with lower average distortion and higher Mean Average Precision (MAP) than direct optimization methods in most test cases.
  • Exact Recovery: The authors proved analytically that if the input data is a perfect tree metric (where $\delta = 0$), TREEREP will recover the original tree exactly.
  • Biological Accuracy: On real-world phylogenetic data, TREEREP correctly clustered related species far more effectively than standard spanning tree methods, proving the practical value of its Steiner node insertions.

Limitations and Future Work

While TREEREP represents a massive leap forward in hyperbolic embedding, there are still hurdles to overcome. Embedding deep trees into hyperbolic space can sometimes require high-precision floating-point numbers to avoid "collapsing" nodes that are very close together. While recent work has begun to address this, it remains a technical challenge for extremely large hierarchies.

Furthermore, while the algorithm performs excellently in practice for general $\delta$-hyperbolic metrics, the authors note they do not yet have a theoretical global bound on distortion for metrics that are far from being trees. Finally, the current iteration of TREEREP is designed for static datasets; adapting the algorithm for streaming data or dynamically evolving networks presents an exciting avenue for future research.

Summary updated

Abstract

Given data, finding a faithful low-dimensional hyperbolic embedding of the data is a key method by which we can extract hierarchical information or learn representative geometric features of the data. In this paper, we explore a new method for learning hyperbolic representations by taking a metric-first approach. Rather than determining the low-dimensional hyperbolic embedding directly, we learn a tree structure on the data. This tree structure can then be used directly to extract hierarchical information, embedded into a hyperbolic manifold using Sarkar's construction \cite{sarkar}, or used as a tree approximation of the original metric. To this end, we present a novel fast algorithm \textsc{TreeRep} such that, given a $\delta$-hyperbolic metric (for any $\delta \geq 0$), the algorithm learns a tree structure that approximates the original metric. In the case when $\delta = 0$, we show analytically that \textsc{TreeRep} exactly recovers the original tree structure. We show empirically that \textsc{TreeRep} is not only many orders of magnitude faster than previously known algorithms, but also produces metrics with lower average distortion and higher mean average precision than most previous algorithms for learning hyperbolic embeddings, extracting hierarchical information, and approximating metrics via tree metrics.
BibTeX
@inproceedings{sonthalia2020tree,
  author = {Rishi Sonthalia and Anna C. Gilbert},
  title = {{Tree! I am no Tree! I am a low dimensional Hyperbolic Embedding}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=-xxKEyzaqLm},
}
Figure