Representation Tradeoffs for Hyperbolic Embeddings

By Frederic Sala, Christopher De Sa, Albert Gu, Christopher R'e. International Conference on Machine Learning, 2018

508 citations recorded by the source corpus.

Hyperbolic embeddings offer excellent quality with few dimensions when embedding hierarchical data structures like synonym or type hierarchies. Given a tree, we give a combinatorial construction that embeds the tree in hyperbolic space with arbitrarily low distortion without using optimization. On WordNet, our combinatorial embedding obtains a mean-average-precision of 0.989 with only two dimensions, while Nickel et al.’s recent construction obtains 0.87 using 200 dimensions. We provide upper and lower bounds that allow us to characterize the precision-dimensionality tradeoff inherent in any hyperbolic embedding. To embed general metric spaces, we propose a hyperbolic generalization of multidimensional scaling (h-MDS). We show how to perform exact recovery of hyperbolic points from distances, provide a perturbation analysis, and give a recovery result that allows us to reduce dimensionality. The h-MDS approach offers consistently low distortion even with few dimensions across several datasets. Finally, we extract lessons from the algorithms and theory above to design a PyTorch-based implementation that can handle incomplete information and is scalable.

View Paper: https://www.semanticscholar.org/paper/33618275fcb19b0535d1b25d02b1d3f3d058de04

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Hyperbolic Neural Networks (2018, background): “For example, [10] shows that arbitrary tree structures cannot be embedded with arbitrary low distortion (i.e. almost preserving their metric) in the Euclidean space with unbounded number of dimensions, but this task becomes surprisingly easy in the hyperbolic space with only 2 dimensions where the…”
Hyperbolic Graph Neural Networks (2019, methodology): “The representation trade-offs for hyperbolic embeddings were analyzed in [12], which also proposed a combinatorial algorithm to compute embeddings.”
Hyperbolic Image Embeddings (2019, unknown): “tree graphs) with low distortion [39, 40].”
Low-Dimensional Hyperbolic Knowledge Graph Embeddings (2020, background): “In contrast, fixed curvature degrades performance in high dimensions (Figure 5a), confirming the importance of trainable curvatures and its impact on precision and capacity (previously studied by (Sala et al., 2018)).”
Hyperbolic Entailment Cones for Learning Hierarchical Embeddings (2018, background): “…embedding f : T → X such that for all i, j , Conversely, any tree can be embedded with arbitrary low distortion into the Poincar´e disk (with only 2 dimensions), whereas this is not true for Euclidean spaces even when an unbounded number of dimensions is allowed (Sarkar, 2011; De Sa et al., 2018).”
Multi-relational Poincaré Graph Embeddings (2019, background): “Hyperbolic space can be thought of as a continuous analogue of discrete trees, making it suitable for modelling hierarchical data structures [26, 8].”
GEMSEC: Graph Embedding with Self Clustering (2018, unknown): “Representations in hyperbolic spaces have emerged as a technique to preserve richer network structures [22], [23], [24].”
Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry (2018, methodology): “Simultaneously to the present work, De Sa et al. (2018) analyzed the representation trade-offs for hyperbolic embeddings and proposed a new combinatorial embedding approach as well as a new approach to Multi-Dimensional Scaling (MDS) in hyperbolic space.”
Riemannian Adaptive Optimization Methods (2018, background): “…equations (Vander-eycken & Vandewalle, 2010), matrix factorization (Tan et al., 2014), geometric programming (Sra & Hosseini, 2015), dictionary learning (Cherian & Sra, 2017) or hyperbolic taxonomy embedding (Nickel & Kiela, 2017; Ganea et al., 2018a; De Sa et al., 2018; Nickel & Kiela, 2018).”
Hyperbolic Graph Convolutional Neural Networks (2019, background): “However, the volume of balls in Euclidean space only grows polynomially with respect to the radius, which leads to high distortion embeddings [34, 35], while in hyperbolic space, this volume grows exponentially.”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, background): “Two common challenges that arise with non-Euclidean embeddings are the limited machine precision [98] and challenging Riemannian optimization [12].”
Poincaré GloVe: Hyperbolic Word Embeddings (2018, methodology): “Note that De Sa et al. (2018) also apply cosh to their distance matrix for hyperbolic MDS before applying PCA.”