Source-linked AI summary
TorusE: Knowledge Graph Embedding on a Lie Group
Takuma Ebisu, Ryutaro Ichise
TL;DR
Knowledge graphs can be incomplete, while TransE’s normalization prevents divergence at the cost of warping embeddings and conflicting with its translation principle. TorusE moves that principle to a torus, avoiding regularization; it outperforms alternatives and is scalable and faster than TransE. Its scope remains limited to information available in training triples.
Problem
Knowledge graphs contain missing facts, and TransE’s sphere normalization conflicts with its translation principle, adversely affecting link-prediction accuracy.
Method
TorusE embeds entities and relations on a torus, a compact Lie group where embeddings remain bounded, so TransE’s principle can be used without regularization.
Results
TorusE outperforms other models on all link-prediction metrics except HITS@10 on FB15K, where it ranks second and trails ComplEx by 0.8%.
Takeaways & Limitations
TorusE is scalable to large knowledge graphs and is empirically faster than TransE because it avoids regularization calculations.
Takeaways & Limitations
TorusE uses only triples, so broader knowledge-graph completion may require information extracted from other materials such as text.
Abstract
from arXiv · showhide
Knowledge graphs are useful for many artificial intelligence (AI) tasks. However, knowledge graphs often have missing facts. To populate the graphs, knowledge graph embedding models have been developed. Knowledge graph embedding models map entities and relations in a knowledge graph to a vector space and predict unknown triples by scoring candidate triples. TransE is the first translation-based method and it is well known because of its simplicity and efficiency for knowledge graph completion. It employs the principle that the differences between entity embeddings represent their relations. The principle seems very simple, but it can effectively capture the rules of a knowledge graph. However, TransE has a problem with its regularization. TransE forces entity embeddings to be on a sphere in the embedding vector space. This regularization warps the embeddings and makes it difficult for them to fulfill the abovementioned principle. The regularization also affects adversely the accuracies of the link predictions. On the other hand, regularization is important because entity embeddings diverge by negative sampling without it. This paper proposes a novel embedding model, TorusE, to solve the regularization problem. The principle of TransE can be defined on any Lie group. A torus, which is one of the compact Lie groups, can be chosen for the embedding space to avoid regularization. To the best of our knowledge, TorusE is the first model that embeds objects on other than a real or complex vector space, and this paper is the first to formally discuss the problem of regularization of TransE. Our approach outperforms other state-of-the-art approaches such as TransE, DistMult and ComplEx on a standard link prediction task. We show that TorusE is scalable to large-size knowledge graphs and is faster than the original TransE.
1 Introduction
Knowledge graphs support many AI tasks but can contain missing facts, motivating automatic completion through link prediction. The paper introduces TorusE, which preserves TransE’s translation principle on a torus to avoid regularization conflicts.
- Knowledge graphs represent real-world facts for tasks including question answering, content tagging, fact checking, and knowledge inference.
- Missing facts in large knowledge graphs motivate systems that automatically complete graphs.
- Link prediction models estimate missing heads or tails in triples to complete knowledge graphs.
- TransE embeds triples in a real vector space using the principle h + r = t and is known for effectiveness and simplicity.
- TorusE applies the TransE principle on a torus, a compact Lie group, eliminating regularization and outperforming alternative link-prediction approaches.
2 Related Work
Related work includes translation-based, bilinear, and neural network-based models for knowledge graph completion. These families trade off simplicity, expressive power, redundancy, dimensionality, and susceptibility to overfitting.
- Knowledge graph completion models are broadly classified as translation-based, bilinear, or neural network-based.
- Translation-based Models: TransE uses h + r = t to capture several first-order relation rules, but the principle is unsuitable for 1-N, N-1, and N-N relations.
- Translation-based Models: TransH, TransR, TransG, and pTransE extend translation-based models through projection, relation-specific transformations, multiple relation vectors, or relation paths.
- Bilinear Models: RESCAL represents each relation with an n-by-n matrix and scores triples using a bilinear map.
- Bilinear Models: DistMult simplifies bilinear models with diagonal relation matrices, while ComplEx uses complex numbers to address symmetric scoring of reversed triples.
- Bilinear Models: Bilinear models can overfit because of redundancy and may require low-dimensional spaces that inadequately distinguish entities in huge graphs.
- Neural Network-based Models: Neural network-based models are highly expressive because they use many parameters, but they tend to overfit training data most easily.
3 TransE and Its Flaw
TransE combines translation-based scoring, negative sampling, and normalization on a real vector space. Normalization prevents divergence but can warp embeddings and conflict with the principle h + r = t.
- TransE’s algorithm has three parts: the translation principle, negative sampling, and regularization.
- Principle: For true triples, TransE learns embeddings satisfying h + r = t and scores deviations with an L1 or squared L2 norm.
- Negative Sampling: Negative sampling prevents the trivial solution of identical entity embeddings and zero relation embeddings by training against corrupted triples.
- Regularization: TransE normalizes entity embeddings to magnitude 1 on the sphere S^(n−1) to prevent unlimited divergence.
- TransE uses a margin-loss objective with margin hyperparameter γ > 0 and trains it using stochastic gradient descent.
- Regularization flaw: Normalization conflicts with h + r = t because translated embeddings often leave the sphere, so projection back onto it warps embeddings and can reduce prediction accuracy.
4 TorusE
TorusE preserves TransE’s translation principle by moving embeddings from a real vector space to a torus, a compact Abelian Lie group. The compact space bounds embeddings and removes the need for regularization while supporting torus-based scoring functions.
- Motivation and model: TorusE changes TransE’s embedding space from R^n to a torus while retaining the translation principle.Entities and relations are represented as points on the torus, with translation expressed through the group operation.
- Motivation and model: Compactness prevents unlimited embedding divergence, resolving the conflict between TransE’s translation principle and regularization during training.The scoring function is bounded on the compact space, so regularization is unnecessary.
- Embedding space: Any Abelian Lie group can support the translation-based strategy, and TorusE selects the torus as a compact Abelian Lie group.The group operation on the torus is inherited from vector addition through equivalence classes.
- Scoring functions: TorusE defines three normalized scoring functions from torus distances: fL1, fL2, and feL2.The distances derive respectively from the L1 norm on R^n, the L2 norm on R^n, and the L2 norm after mapping the torus into C^n.
- Scoring functions: The three scoring-function derivatives differ: f′L1 is constant, f′L2 vanishes at x = 0, and f′eL2 vanishes at x = 0 and x = 0.5.These derivative properties affect embeddings obtained through gradient descent.
- Training and implementation: TorusE minimizes a margin-based objective over true and negatively sampled triples without regularization, reducing regularization-related calculation time.The objective uses positive-part loss with margin γ > 0 and one of the three scoring functions.
- Interpretation and extensions: TorusE embeddings represent similar relation translations on the torus, and some TransE extensions can be transferred by changing the embedding space.The paper also relates feL2 to a restricted, less redundant version of ComplEx on the torus.
5 Experiments
Experiments evaluate TorusE’s scalability and link-prediction accuracy on WN18 and FB15K. TorusE is substantially faster than TransE and generally achieves stronger prediction results, including on difficult HITS@1 evaluations.
- Scalability of TorusE: TorusE and TransE have the same theoretical O(n) complexity, but TorusE’s empirical calculation time is substantially lower.Both calculation times scale approximately linearly with embedding dimension; the measured gap is attributed mainly to TransE’s regularization overhead.
- Scalability of TorusE: 11 times faster: on WN18 at dimension 10,000, TorusE completes one epoch in 4.0 seconds versus 55.6 seconds for TransE.The paper attributes this difference mainly to the time-consuming normalization of all TransE entity embeddings.
- Scalability of TorusE: On FB15K at dimension 10,000, TorusE completes one epoch in 16.8 seconds versus 29.4 seconds for TransE.Across 500 epochs, TorusE takes about 2 hours 30 minutes on FB15K; it is also faster than ComplEx in the reported comparisons.
- Accuracies of the Link Prediction Tasks: TorusE outperforms all other models on every reported metric except HITS@10 on FB15K, where it ranks second.On FB15K, its difference from the best model, ComplEx, is 0.8%.
- Accuracies of the Link Prediction Tasks: TorusE improves HITS@1 over TransE by 90.3% on WN18 and 42.7% on FB15K.The paper links this result to changing the embedding space to avoid TransE’s regularization.
- Accuracies of the Link Prediction Tasks: On WN18, TorusE performs equal to or better than ComplEx for many relations and appears able to handle 1-N, N-1, and N-N relations.The paper argues that ranking correct entities above incorrect ones can suffice even when h + r = t cannot be followed completely.
6 Conclusions and Future Work
TorusE addresses TransE’s regularization problem by embedding entities and relations on a torus, while the paper identifies broader directions for embedding spaces and knowledge-graph completion.
- TorusE embeds entities and relations on a torus without regularization and outperformed state-of-the-art models on WN18 and FB15K.The paper also experimentally showed that TorusE is faster than TransE.
- Future work will consider other embedding spaces and combine TorusE with extended TransE models.The authors note that all Lie groups can serve as embedding spaces and that some TransE extensions may transfer directly by changing the space to a torus.
- More general completion models are needed to retrieve information beyond training triples, including triples extracted from text and word-embedding-based models.The paper motivates this direction because required information may not be included in the training triples.