Generalization Error Bound for Hyperbolic Ordinal Embedding

Atsushi Suzuki, Atsushi Nitanda, Jing Wang, Linchuan Xu, Kenji Yamanishi, Marc Cavazza

Introduction

Ordinal embedding is the task of representing entities as points in a metric space based on relative similarity constraints (e.g., "entity $i$ is more similar to $j$ than to $k$"). Traditionally, this is performed in Euclidean space (Euclidean Ordinal Embedding, or EOE). However, Euclidean space exhibits polynomial volume growth, making it fundamentally ill-suited for representing hierarchical data like knowledge bases or citation networks, which grow exponentially.

Hyperbolic space offers a natural alternative. Its volume grows exponentially, allowing tree-like structures to be embedded with minimal distortion. While Hyperbolic Ordinal Embedding (HOE) has demonstrated strong empirical performance, it has historically lacked a theoretical guarantee of its generalization error—how well an embedding learned from a small sample of constraints performs on unseen data. Because hyperbolic space is not an inner-product space, standard proofs relying on the Gramian matrix do not apply, leaving a significant theoretical gap in understanding HOE's performance in noisy, real-world settings.

Methodology: Bridging the Theoretical Gap

To establish generalization bounds for HOE, the authors introduce a novel mathematical characterization. Instead of the standard Gramian matrix, they utilize the Lorentz Gramian matrix by viewing hyperbolic space as a submanifold of Minkowski space (the hyperboloid model).

They decompose this Lorentz Gramian into two positive semi-definite matrices ($L^+$ and $L^-$), which allows the HOE objective to be reformulated as a linear prediction problem. By framing HOE in this manner, the authors calculate its Rademacher complexity—a measure of a model's capacity to fit random noise. Combining this with standard statistical learning frameworks yields a generalization error bound dependent on the number of entities ($N$), the number of constraints ($S$), and the radius of the embedding space ($R$).

Key Insights and Results

The paper provides the first formal generalization error bound for HOE, proving it to be $O(\exp(R)^2 \cdot \sqrt{N \ln N / S})$. This bound matches the EOE bound in its dependency on $N$ and $S$, differing primarily in how it scales with the radius $R$.

  • The Exponential Trade-off: The bound reveals that HOE carries an error bound that is exponential with respect to the embedding radius ($R$), whereas EOE's bound is polynomial ($R^2$). This formalizes the "price" HOE pays in variance for its massive representational capacity.
  • Bias-Variance Trade-off: Despite the looser generalization bound (higher variance), HOE exhibits significantly lower bias for hierarchical data. For tree structures, EOE often fails to find a good fit (high bias), whereas HOE fits easily. Consequently, the total error for HOE is lower on hierarchical data despite its higher variance.
  • Sample Efficiency: The theoretical results suggest that a robust embedding requires roughly $O(N \ln N)$ ordinal constraints, vastly fewer than the $O(N^3)$ total possible triplets.

Empirical Validation

The authors validated their theory using simulated triplet comparisons across varying sample sizes ($S = 100$ to $1600$) on two distinct datasets:

  1. R2: A dataset of 20 points in a 2D Euclidean plane, representing data that naturally fits Euclidean space.
  2. Star: A 20-node star graph with random weights, representing hierarchical data where hyperbolic space should excel.

As expected, EOE performed better on the Euclidean R2 dataset due to its lower variance. Conversely, HOE outperformed EOE on the Star dataset as sample size increased, successfully capturing the tree structure (low bias) where EOE hit a strict performance ceiling.

Limitations and Future Directions

A primary limitation of the current bound is that it does not explicitly depend on the dimensionality ($D$) of the embedding space. Intuitively, lower-dimensional embeddings should generalize better, but the current mathematical framework (following previous work in EOE) does not yet capture this "low-dimensional advantage." Deriving a tighter bound that incorporates $D$ remains an important next step for the field.

Additionally, because the bound is highly sensitive to the radius $R$, practitioners face the practical challenge of keeping the embedding radius small while maintaining representation accuracy.

Summary updated

Abstract

Hyperbolic ordinal embedding (HOE) represents entities as points in hyperbolic space so that they agree as well as possible with given constraints in the form of entity $i$ is more similar to entit...
BibTeX
@inproceedings{suzuki2021generalization,
  author = {Atsushi Suzuki and Atsushi Nitanda and Jing Wang and Linchuan Xu and Kenji Yamanishi and Marc Cavazza},
  title = {{Generalization Error Bound for Hyperbolic Ordinal Embedding}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=AEm_9Kq97E},
}
Figure