# Tight and fast generalization error bound of graph embedding in metric space

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 63 references that are in the map.
- First posted on arXiv 13 May 2023.

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

- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Enriching Word Vectors with Subword Information](https://mlsanity.com/paper/1607.04606/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Hyperbolic Neural Networks](https://mlsanity.com/paper/1805.09112/) (2018)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [Holographic Embeddings of Knowledge Graphs](https://mlsanity.com/paper/1510.04935/) (2015)
- [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)
- [Multi-relational Poincar'e Graph Embeddings](https://mlsanity.com/paper/1905.09791/) (2019)
- [Hyperbolic Attention Networks](https://mlsanity.com/paper/1805.09786/) (2018)
- [PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks](https://mlsanity.com/paper/1508.00200/) (2015)
- [TorusE: Knowledge Graph Embedding on a Lie Group](https://mlsanity.com/paper/1711.05435/) (2017)
- [Finite Sample Prediction and Recovery Bounds for Ordinal Embedding](https://mlsanity.com/paper/1606.07081/) (2016)
- [Generalization Error Bound for Hyperbolic Ordinal Embedding](https://mlsanity.com/paper/2105.10475/) (2021)
- [On the ERM Principle with Networked Data](https://mlsanity.com/paper/1711.04297/) (2017)
- [The Importance of Norm Regularization in Linear Graph Embedding: Theoretical Analysis and Empirical Demonstration](https://mlsanity.com/paper/1802.03560/) (2018)

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

- [Towards Non-Euclidean Foundation Models: Advancing AI Beyond Euclidean Frameworks](https://mlsanity.com/paper/2505.14417/) (2025)

## Abstract (arXiv)

Recent studies have experimentally shown that we can achieve in non-Euclidean metric space effective and efficient graph embedding, which aims to obtain the vertices' representations reflecting the graph's structure in the metric space. Specifically, graph embedding in hyperbolic space has experimentally succeeded in embedding graphs with hierarchical-tree structure, e.g., data in natural languages, social networks, and knowledge bases. However, recent theoretical analyses have shown a much higher upper bound on non-Euclidean graph embedding's generalization error than Euclidean one's, where a high generalization error indicates that the incompleteness and noise in the data can significantly damage learning performance. It implies that the existing bound cannot guarantee the success of graph embedding in non-Euclidean metric space in a practical training data size, which can prevent non-Euclidean graph embedding's application in real problems. This paper provides a novel upper bound of graph embedding's generalization error by evaluating the local Rademacher complexity of the model as a function set of the distances of representation couples. Our bound clarifies that the performance of graph embedding in non-Euclidean metric space, including hyperbolic space, is better than the existing upper bounds suggest. Specifically, our new upper bound is polynomial in the metric space's geometric radius R and can be O(frac1S) at the fastest, where S is the training data size. Our bound is significantly tighter and faster than the existing one, which can be exponential to R and O(frac1√S) at the fastest. Specific calculations on example cases show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much smaller training data than the existing bound has suggested.