Source-linked AI summary
Multi-relational Poincaré Graph Embeddings
Ivana Balažević, Carl Allen, Timothy Hospedales
TL;DR
Multi-relational knowledge graphs contain simultaneous hierarchies that existing hyperbolic models do not adequately capture. MuRP embeds them in the Poincaré ball with relation-specific Möbius transformations, outperforming Euclidean and existing models on WN18RR link prediction while using fewer dimensions for comparable performance.
Problem
Existing hyperbolic approaches do not adequately represent knowledge graphs whose shared entities participate in multiple relation-specific hierarchies.
Method
MuRP embeds multi-relational graph data in the Poincaré ball using relation-specific Möbius matrix-vector multiplication and Möbius addition.
Results
MuRP outperforms its Euclidean counterpart and existing models on WN18RR link prediction, requiring far lower dimensionality for comparable performance.
Takeaways & Limitations
Hyperbolic embeddings can succinctly represent multiple hierarchies in WN18RR, including at relatively low embedding dimensionality.
Takeaways & Limitations
Evaluation may be unreliable because some predicted false positives are facts missing from the dataset, and not all relations are hierarchical.
Abstract
from arXiv · showhide
Hyperbolic embeddings have recently gained attention in machine learning due to their ability to represent hierarchical data more accurately and succinctly than their Euclidean analogues. However, multi-relational knowledge graphs often exhibit multiple simultaneous hierarchies, which current hyperbolic models do not capture. To address this, we propose a model that embeds multi-relational graph data in the Poincaré ball model of hyperbolic space. Our Multi-Relational Poincaré model (MuRP) learns relation-specific parameters to transform entity embeddings by Möbius matrix-vector multiplication and Möbius addition. Experiments on the hierarchical WN18RR knowledge graph show that our Poincaré embeddings outperform their Euclidean counterpart and existing embedding methods on the link prediction task, particularly at lower dimensionality.
1 Introduction
Hyperbolic space efficiently represents hierarchical data, but existing hyperbolic models struggle with knowledge graphs containing multiple simultaneous hierarchies. MuRP addresses this gap with relation-specific transformations and improves link prediction, especially at lower dimensionality.
- Motivation: Hyperbolic space models tree-like structures more efficiently than Euclidean space for hierarchical data.Its capacity grows exponentially with radius, providing more room to separate nodes farther from a tree root.
- Problem: Knowledge graphs can impose different hierarchies on the same entities, creating a challenge for shared entity embeddings.For example, an entity may occupy different hierarchical positions under different relations.
- Approach: MuRP learns relation-specific parameters that transform entity embeddings through Möbius matrix-vector multiplication and Möbius addition.The model embeds multi-relational graph data in the Poincaré ball.
- Results: MuRP outperforms its Euclidean counterpart and existing models on WN18RR link prediction while requiring fewer dimensions for comparable performance.The paper also analyzes convergence, relation-level performance, and embedding dimensionality.
2 Background and preliminaries
Knowledge graphs represent typed relations between entities, and link prediction infers missing facts from learned scores. The section introduces Poincaré geometry, where geodesic distance and Möbius operations support hyperbolic representations.
- Multi-relational link prediction: A knowledge graph stores facts as triples (es, r, eo), with entities connected by typed directed relations.Link prediction learns a score for each triple and converts it into a predicted truth probability.
- Motivation: Hyperbolic space is motivated for relations such as hypernym and has_part because they induce hierarchical structures over entities.The paper focuses on embedding such multi-relational knowledge-graph data hyperbolically.
- Geometric intuition: Figure 1 illustrates geodesics, triple predictions, and entity-specific spheres of influence in the model.The figure connects shortest-path geometry with decision regions for predicted relations.
- Poincaré geometry: The Poincaré ball represents hyperbolic space using a conformal Riemannian metric on a bounded d-dimensional manifold.Distances are measured along geodesics, the shortest paths between points.
- Hyperbolic operations: Möbius matrix-vector multiplication is obtained by mapping a point to the tangent space, applying matrix multiplication, and mapping it back.The exponential and logarithmic maps provide the projections between the Poincaré ball and tangent space.
3 Related work
Related work spans hyperbolic embeddings for hierarchical data and Euclidean multi-relational models based on bilinear or translational scoring. These approaches differ in how they represent hierarchy, relation structure, asymmetry, and parameter sharing.
- Hyperbolic embeddings: Poincaré and Lorentz embeddings represent hierarchical data in low dimensions, with Poincaré embeddings outperforming higher-dimensional Euclidean embeddings on representation capacity and generalization.Hyperbolic neural networks extend these operations to linear layers, translations, and nonlinearities.
- Bilinear models: Bilinear models represent relations as transformations of entity vectors, ranging from full-rank RESCAL matrices to parameter-controlled variants.RESCAL can overfit, while DistMult reduces parameters but cannot model asymmetric relations.
- Bilinear models: ComplEx enables asymmetry through complex-valued embeddings, while TuckER supports multi-task learning across relations through a shared core tensor.The cited linear models are described as special cases of TuckER.
- Translational models: Translational models treat relations as vector offsets and typically score triples using Euclidean distance between transformed subject and object embeddings.TransE and later variants follow this translational formulation.
4 Multi-relational Poincaré embeddings
MuRP extends translational multi-relational embeddings to the Poincaré ball, using relation-specific hyperbolic transformations and entity-specific biases. It is trained by negative sampling with Bernoulli loss and Riemannian optimization.
- 4 Multi-relational Poincaré embeddings: Entities can occupy different hierarchical positions under different relations, so an ideal embedding should capture multiple hierarchies simultaneously.WordNet relations such as hypernym, has_part, and member_meronym induce distinct hierarchies over shared entities.
- Motivation: The model is motivated by linear relation offsets in word embeddings, which support treating graph relations as transformations between entity pairs.This connection provides intuition for the translational basis score.
- Hyperbolic model: MuRP scores a triple by the negative squared Poincaré distance between relation-adjusted embeddings plus subject and object biases.Its Euclidean analogue MuRE replaces the hyperbolic distance with Euclidean distance.
- Hyperbolic model: MuRP transforms the subject with Möbius matrix-vector multiplication and transforms the object with Möbius addition of a relation vector.The relation matrix is diagonal, keeping parameter growth linear in the numbers of entities and relations.
- Geometric intuition: Entity-specific biases define sphere-of-influence radii, while relation-specific parameters determine the positions of transformed embeddings.The decision-boundary radius is independent of the relation, although each subject-object pair has its own boundary.
- Training and optimization: Training adds reciprocal relations, corrupts subjects or objects for negative samples, and minimizes Bernoulli negative log-likelihood.The predicted probability is obtained by applying a logistic sigmoid to the score.
- Training and optimization: Riemannian stochastic gradient descent updates hyperbolic parameters using gradients adjusted by the inverse Poincaré metric tensor and exponential-map updates.The Euclidean counterpart is optimized with ordinary stochastic gradient descent.
5 Experiments
Experiments evaluate MuRE and MuRP on standard knowledge-graph benchmarks, showing that MuRP is particularly effective for hierarchical relations and at lower dimensionality.
- Link prediction results: MuRE performs slightly better on non-hierarchical FB15k-237, whereas MuRP outperforms on hierarchical WN18RR.
- Link prediction results: Both models outperform previous state-of-the-art methods on WN18RR across metrics except hits@1, where MuRP ranks second overall.
- MuRE vs MuRP: The performance difference between MuRP and MuRE on WN18RR is greatest at lower embedding dimensionality.
- MuRE vs MuRP: MuRP converges faster than MuRE on WN18RR training and validation sets.
- MuRE vs MuRP: Ablating relation-specific transformations or changing bias choices reduces performance for both models.
- MuRE vs MuRP: MuRP generally outperforms MuRE on hierarchical relations, while both models are comparable on non-hierarchical symmetric relations.
- MuRE vs MuRP: Embedding-vector norms and entity biases are correlated for both MuRP and MuRE.
6 Conclusion and future work
MuRP is a translational Poincaré-ball method for multi-relational graph data that outperforms Euclidean and existing models on hierarchical WN18RR while requiring fewer dimensions for comparable performance. Future work includes comparing Riemannian adaptive optimization with Riemannian SGD and combining Euclidean and hyperbolic models for mixed-curvature embeddings.
- Conclusion: MuRP embeds multi-relational graph data in the Poincaré ball using relation-specific Möbius transformations.The transformations use Möbius matrix-vector multiplication and Möbius addition.
- Conclusion: MuRP outperforms MuRE and existing models on link prediction for the hierarchical WN18RR knowledge graph.
- Conclusion: MuRP requires far lower dimensionality than MuRE to achieve comparable performance.
- Future work: Future work may compare recently introduced Riemannian adaptive optimization methods with Riemannian SGD.
- Future work: Future work may combine Euclidean and hyperbolic models because knowledge graphs do not contain only hierarchical relations.The proposed direction is to produce mixed-curvature embeddings suited to the data's curvature.
A Poincaré ball model of hyperbolic geometry
The Poincaré ball is one of five isometric hyperbolic-geometry models, with a d-dimensional Euclidean tangent space providing a local approximation of the manifold. Exponential and logarithmic maps support movement between tangent-space vectors and the manifold.
- Model: The Poincaré ball is one of five isometric models of hyperbolic geometry.Isometry provides a one-to-one distance-preserving mapping between model metric spaces.
- Tangent space: At a point x, the Poincaré ball has a d-dimensional Euclidean tangent space that locally approximates the manifold.
- Maps: The exponential map moves from x on the manifold in the direction of a vector v in the tangent space.
- Maps: The logarithmic map is the inverse of the exponential map.For the Poincaré ball, these maps are defined mathematically in the model.
B NELL-995-h{100, 75, 50, 25} dataset splits
The authors revise NELL-995 validation and test splits to represent all training relations, then construct four subsets with varying proportions of hierarchical and non-hierarchical relations.
- Dataset splits: The commonly used NELL-995 test set contains 12 of 200 training relations, none hierarchical.
- Dataset splits: New validation and test splits combine the initial splits with training data and randomly select 10,000 triples for each.
- Dataset splits: The four subsets contain 100%, 75%, 50%, or 25% hierarchical relations, with 43 hierarchical relations and respectively 0, 14, 43, or 129 non-hierarchical relations.
C NELL-995-h{100, 75, 50, 25} experiments
Across NELL-995 subsets, MuRP's advantage over MuRE is strongest when relations are hierarchical and embeddings are low-dimensional; increasing non-hierarchical relations narrows or reverses the difference at d=200.
- Experiments: At d=40, MuRP consistently outperforms MuRE on all four NELL-995 subsets.
- Experiments: As non-hierarchical relations increase, the performance difference between MuRP and MuRE becomes smaller.The difference is smallest on NELL-995-h25.
- Interpretation: The results support hyperbolic embeddings' advantage for hierarchical data, particularly when low embedding dimensionality is required.
- Experiments: On purely hierarchical NELL-995-h100, MuRP outperforms MuRE at both lower and higher dimensionality.NELL-995-h100 contains 43 hierarchical and 0 non-hierarchical relations.
- Experiments: On mostly non-hierarchical NELL-995-h25, MuRP is only slightly better at d=40, while MuRE outperforms at d=200.NELL-995-h25 contains 43 hierarchical and 129 non-hierarchical relations.
D Krackhardt hierarchy score
The Krackhardt hierarchy score measures hierarchy in a directed graph using directed reachability between node pairs.
- The Krackhardt hierarchy score is defined for directed networks.
- It uses a binary reachability matrix R for a directed graph G with n nodes.R_i,j records whether a directed path exists from node i to node j.
- The score is based on directed paths between node pairs in the graph.
E Dimensionality reduction method
The visualization method projects high-dimensional entity embeddings into two dimensions by aligning the subject embedding with the x-axis and positioning objects relative to it.
- The method computes two-dimensional projection coordinates x and y for each entity embedding.
- The original subject embedding defines the reference direction for projecting the embeddings.The subject embedding is used as the reference vector in the projection.
- The subject embedding is placed on the x-axis, with its projected x-coordinate set to zero.
- Object embeddings are positioned relative to the subject using aligned and remaining projection components.The aligned component is e′_i^x, while the remaining component is e′_i^y.