# Generalization Error Bound for Hyperbolic Ordinal Embedding

arXiv: https://arxiv.org/abs/2105.10475 · HTML: https://mlsanity.com/paper/2105.10475/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 21 May 2021.

## Builds on (most cited first, 18 of 18)

- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Hyperbolic Neural Networks](https://mlsanity.com/paper/1805.09112/) (2018)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [Hyperbolic Entailment Cones for Learning Hierarchical Embeddings](https://mlsanity.com/paper/1804.01882/) (2018)
- [Poincar'e GloVe: Hyperbolic Word Embeddings](https://mlsanity.com/paper/1810.06546/) (2018)
- [Hyperbolic Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.04562/) (2021)
- [Multi-relational Poincar'e Graph Embeddings](https://mlsanity.com/paper/1905.09791/) (2019)
- [Hyperbolic Attention Networks](https://mlsanity.com/paper/1805.09786/) (2018)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [Large-Margin Classification in Hyperbolic Space](https://mlsanity.com/paper/1806.00437/) (2018)
- [Finite Sample Prediction and Recovery Bounds for Ordinal Embedding](https://mlsanity.com/paper/1606.07081/) (2016)
- [Hyperbolic Distance Matrices](https://mlsanity.com/paper/2005.08672/) (2020)
- [Metric recovery from directed unweighted graphs](https://mlsanity.com/paper/1411.5720/) (2014)
- [Stochastic Non-convex Ordinal Embedding with Stabilized Barzilai-Borwein Step Size](https://mlsanity.com/paper/1711.06446/) (2017)
- [Robust Ordinal Embedding from Contaminated Relative Comparisons](https://mlsanity.com/paper/1812.01945/) (2018)

## Built on by (most cited first, 12 of 12)

- [A Comprehensive Survey of Few-shot Learning: Evolution, Applications, Challenges, and Opportunities](https://mlsanity.com/paper/2205.06743/) (2022)
- [Hyperbolic Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/2202.13852/) (2022)
- [Hyperbolic Fine-Tuning for Large Language Models](https://mlsanity.com/paper/2410.04010/) (2024)
- [Hyperbolic Representation Learning: Revisiting and Advancing](https://mlsanity.com/paper/2306.09118/) (2023)
- [Learning Structured Representations with Hyperbolic Embeddings](https://mlsanity.com/paper/2412.01023/) (2024)
- [kHGCN: Tree-likeness Modeling via Continuous and Discrete Curvature Learning](https://mlsanity.com/paper/2212.01793/) (2022)
- [HoPE: Hyperbolic Rotary Positional Encoding for Stable Long-Range Dependency Modeling in Large Language Models](https://mlsanity.com/paper/2509.05218/) (2025)
- [HyperbolicRAG: Enhancing Retrieval-Augmented Generation with Hyperbolic Representations](https://mlsanity.com/paper/2511.18808/) (2025)
- [Emotion Collider: Dual Hyperbolic Mirror Manifolds for Sentiment Recovery via Anti Emotion Reflection](https://mlsanity.com/paper/2602.16161/) (2026)
- [Tight and fast generalization error bound of graph embedding in metric space](https://mlsanity.com/paper/2305.07971/) (2023)
- [Towards Ordinal Data Science](https://mlsanity.com/paper/2307.09477/) (2023)
- [Towards Non-Euclidean Foundation Models: Advancing AI Beyond Euclidean Frameworks](https://mlsanity.com/paper/2505.14417/) (2025)

## Abstract (arXiv)

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 entity j than to entity k. It has been experimentally shown that HOE can obtain representations of hierarchical data such as a knowledge base and a citation network effectively, owing to hyperbolic space's exponential growth property. However, its theoretical analysis has been limited to ideal noiseless settings, and its generalization error in compensation for hyperbolic space's exponential representation ability has not been guaranteed. The difficulty is that existing generalization error bound derivations for ordinal embedding based on the Gramian matrix do not work in HOE, since hyperbolic space is not inner-product space. In this paper, through our novel characterization of HOE with decomposed Lorentz Gramian matrices, we provide a generalization error bound of HOE for the first time, which is at most exponential with respect to the embedding space's radius. Our comparison between the bounds of HOE and Euclidean ordinal embedding shows that HOE's generalization error is reasonable as a cost for its exponential representation ability.