Source-linked AI summary
Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry
Maximilian Nickel, Douwe Kiela
TL;DR
The paper studies how to discover concept hierarchies from large-scale, unstructured pairwise similarities when explicit ordering information is unavailable. It learns continuous hyperbolic embeddings using a Lorentz-model optimization approach and reports substantially better taxonomy embeddings than Poincaré embeddings, especially in low dimensions. The method is also applied to organizational and linguistic hierarchy discovery.
Problem
The paper addresses recovering unobserved concept hierarchies from pairwise similarity measurements when explicit hierarchical relationships are unavailable.
Method
The method separates relatedness from generality and learns continuous hyperbolic embeddings with an efficient Lorentz-model Riemannian optimizer.
Results
The Lorentz model produces substantially improved embedding quality over Poincaré embeddings, especially in low dimensions, while scaling to large datasets.
Takeaways & Limitations
Hyperbolic embeddings can discover hierarchies from pairwise similarity scores, including meaningful structure in real-world organizational and language datasets.
Takeaways & Limitations
The approach assumes concepts in the same ground-truth subtree are more similar than concepts in different subtrees and relies on observed superior-subordinate concepts.
Abstract
from arXiv · showhide
We are concerned with the discovery of hierarchical relationships from large-scale unstructured similarity scores. For this purpose, we study different models of hyperbolic space and find that learning embeddings in the Lorentz model is substantially more efficient than in the Poincaré-ball model. We show that the proposed approach allows us to learn high-quality embeddings of large taxonomies which yield improvements over Poincaré embeddings, especially in low dimensions. Lastly, we apply our model to discover hierarchies in two real-world datasets: we show that an embedding in hyperbolic space can reveal important aspects of a company's organizational structure as well as reveal historical relationships between language families.
1. Introduction
The paper addresses discovering concept hierarchies from pairwise similarity measurements when explicit hierarchical relationships are unavailable. It separates relatedness from generality and uses hyperbolic embeddings, with a Lorentz-based optimizer that improves embedding quality, especially in low dimensions.
- Explicit hierarchical relationships are unavailable in many domains, motivating hierarchy discovery from unstructured observations.
- The setting assumes pairwise hierarchical relations among observed superior and subordinate concepts, inferred only from pairwise similarity measurements.
- The method separates relatedness and generality, representing them through embedding distance and embedding norm, respectively.
- Hyperbolic embeddings provide continuous representations of hierarchies because hyperbolic space has geometric properties analogous to discrete trees.
- The Lorentz model enables closed-form geodesics and an optimizer that follows them directly, avoiding first-order approximation and numerical instabilities from the Poincaré distance.
- The resulting method substantially improves embedding quality, especially in low dimensions, while retaining gradient-based learning and scalability to large datasets.
2. Related Work
The work extends hyperbolic and ordered embedding research by introducing Lorentz-model optimization, learning from real-valued similarities, and recovering hierarchical relationships. It differs from prior approaches that primarily model symbolic links or use directly ordered input pairs.
- Related work also includes hyperbolic network models, geodesic-cone extensions, combinatorial embeddings, hyperbolic multidimensional scaling, and probabilistic or density-based hierarchy models.
- Poincaré embeddings learn low-dimensional hierarchical representations of symbolic data by exploiting the structure of hyperbolic space.
- The paper introduces Lorentz-model hyperbolic embeddings with efficient Riemannian optimization that scales to large datasets and improves embeddings, especially in low dimensions.
- Unlike Poincaré embeddings based on binary adjacency matrices, the approach infers hierarchies from real-valued similarity scores.
- The method focuses not only on preserving similarity and local link structure but also on recovering correct hierarchical relationships.
- Order Embeddings learn hierarchies from ordered input pairs, whereas this work uses unordered symmetric pairs without direct partial-order information.
3. Methods
The method learns continuous hierarchies from pairwise similarities by separating comparability from generality and embedding concepts in hyperbolic space. It uses Lorentz-model Riemannian optimization to preserve local similarity orderings efficiently while retaining hyperbolic representations of hierarchy.
- Lorentz optimization: The Lorentz model supports efficient Riemannian optimization through closed-form geodesics and avoids numerical instabilities associated with the Poincaré distance.Updates use Riemannian stochastic gradient descent, including tangent-space projection and the exponential map.
- Model connection: Embeddings are learned in the Lorentz model and mapped to the Poincaré ball for visualization, exploiting the equivalence of the two models.The Lorentz representation is used for optimization, while the Poincaré disk provides an intuitive visualization.
- Problem setting: The approach extends hyperbolic graph embeddings to infer continuous hierarchies from pairwise similarity measurements.It targets settings where hierarchical relations are unobserved but similarity scores are available.
- Hierarchy representation: The model represents a superior concept as both related to and more general than its subordinate.Comparability and generality are treated as separate aspects of hierarchical relations.
- Structural assumptions: Comparable concepts are assumed more similar than incomparable concepts, while general concepts are assumed similar to more concepts.These structural assumptions connect pairwise similarities to latent partial-order relations.
- Similarity objective: The embedding objective preserves local similarity orderings so the most likely comparable concept can be identified among less-similar candidates.For each pair, candidate concepts are ranked using distances in the embedding space.
4. Evaluation
The evaluation compares Lorentz and Poincaré embeddings on large taxonomies and applies the Lorentz model to organizational and historical-linguistic data. Lorentz embeddings consistently achieve higher quality, particularly in low dimensions, while revealing meaningful real-world hierarchies.
- 4.1. Embedding Taxonomies: The evaluation embeds WordNet, EuroVoc, ACM, and MeSH taxonomies and compares Lorentz optimization with Poincaré embeddings.The methods use undirected transitive closures, rank observed edges against unobserved edges, and evaluate generality through embedding norms.
- 4.1. Embedding Taxonomies: 74.8% relative improvement on WORDNET noun hierarchy and 42.4% on EUROVOC were achieved by two-dimensional Lorentz embeddings over Poincaré embeddings.Similar improvements occurred across all evaluated taxonomies.
- 4.1. Embedding Taxonomies: 10-dimensional Lorentz embeddings on WORDNET nouns outperformed the best reported Poincaré results, which used up to 200 dimensions.The authors attribute the advantage to full Riemannian optimization, especially where low-dimensional optimization faces local minima.
- 4.2. Enron Email Corpus: The Enron embedding places executives near the origin and traders and analysts nearer the boundary, approximately reflecting organizational hierarchy.Embedding norms correlate with organizational rank, while node clusters capture similarity within the hierarchy.
- 4.3. Historical Linguistics Data: The IELex embedding recovers clusters of major Indo-European language families and meaningful internal hierarchies among related languages.Examples include Gothic → Old High German → German, Latin → Italian, and Ancient Greek → Greek.
5. Conclusion
The paper introduces a method for learning continuous concept hierarchies from pairwise similarity observations using hyperbolic geometry. Lorentz-based Riemannian optimization improves embedding quality over Poincaré embeddings, especially in low dimensions, and reveals meaningful hierarchies in two real-world datasets.
- 5. Conclusion: The method discovers continuous concept hierarchies from pairwise similarity scores under an assumption about within-subtree similarity.It uses hyperbolic embeddings and Lorentz-model Riemannian optimization.
- 5. Conclusion: Lorentz optimization substantially improves embedding quality over the method of Nickel and Kiela, especially in low dimensions.The approach retains continuous, gradient-based hierarchy representations that scale to large datasets.
- 5. Conclusion: The method discovers meaningful hierarchies from pairwise similarity information in two real-world datasets.The conclusion summarizes the Enron organizational and language-family applications.