Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embedding

Rishi Sonthalia, Anna C. Gilbert

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, or used as a tree approximation of the original metric. To this end, we present a novel fast algorithm 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 TREEREP exactly recovers the original tree structure. We show empirically that 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.

Introduction

Extracting hierarchical structure from data is crucial in fields ranging from single-cell genomics to natural language processing and social network analysis. Because trees cannot be faithfully represented in standard, flat Euclidean space without massive distortion, researchers have turned to hyperbolic space, which expands exponentially and naturally accommodates tree-like hierarchies. However, current methods for learning these hyperbolic embeddings (like Poincaré Maps or Lorentz Maps) try to learn the continuous coordinates of the data points directly. This requires solving complex, non-convex optimization problems that are computationally expensive, slow on large datasets, and prone to local minima.

The TREEREP Algorithm

We propose a "metric-first" approach. Instead of trying to embed data directly into a continuous hyperbolic space, we first learn a discrete tree metric—a tree structure that approximates the distances between data points—and then embed that tree into hyperbolic space using existing, fast mathematical constructions. To do this, we introduce TREEREP, a recursive, divide-and-conquer algorithm:

  1. Universal Trees & Steiner Nodes: TREEREP picks three random data points and builds a "universal tree" connecting them. Crucially, it introduces a Steiner node—a new, latent central hub that wasn't in the original dataset—to correctly capture the underlying hierarchy.
  2. Zone Sorting: Using a geometric measure called the Gromov product, the algorithm sorts all remaining data points into seven distinct "zones" relative to this initial 3-point tree.
  3. Recursion: The algorithm recursively repeats this process within each zone, building out the full tree in $O(n^2)$ time.
Figure 1: Illustration of the tree construction cases and the universal tree structure used in the TREEREP algorithm.

Experimental Evaluation

The authors evaluated TREEREP across a variety of synthetic and real-world datasets, including random points sampled from continuous hyperbolic manifolds, immunological distances for phylogenetic reconstruction, and single-cell RNA sequencing (scRNA-seq) data.

Key Results

  • Massive Speedups: TREEREP is 10,000 to 40,000 times faster than optimization-based methods. For example, on the CBMC single-cell dataset, TREEREP took 2.8 seconds, while Poincaré Maps took over 3.4 hours.
  • Higher Quality: Despite the speedup, TREEREP generally yields higher Mean Average Precision (MAP) and lower average distortion than direct embedding methods, especially for low-dimensional representations.
  • Theoretical Guarantees: If the input data perfectly forms a tree (a 0-hyperbolic metric), TREEREP is mathematically guaranteed to exactly recover the original tree using the absolute minimum number of nodes.

Discussion and Insights

Hyperbolic space is essentially a tree at scale. The authors justify their approach using the concept of asymptotic cones: if you "zoom out" infinitely far on a hyperbolic space, its large-scale structure is equivalent to a continuous tree. Thus, learning a tree first is geometrically the "correct" way to learn large-scale hyperbolic representations. Furthermore, the necessity of Steiner nodes is non-negotiable; spanning trees that only use existing data points fundamentally fail to capture the true geometry. The fact that TREEREP outperforms continuous gradient descent methods suggests that existing hyperbolic embedding models frequently get trapped in local minima.

Limitations and Future Work

While TREEREP guarantees exact recovery for perfect trees, it lacks a global mathematical bound on distortion for general, noisy $\delta$-hyperbolic metrics. Additionally, the algorithm can occasionally calculate negative edge weights during construction, currently handled by setting them to zero. Future work may involve more sophisticated handling of these weights or establishing tighter global bounds.

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