Source-linked AI summary
SimplE Embedding for Link Prediction in Knowledge Graphs
Seyed Mehran Kazemi, David Poole
TL;DR
Knowledge graphs are incomplete, so link prediction must infer new triples from existing ones; CP is limited because it learns independent head and tail embeddings. The paper introduces SimplE, which uses inverse relations to couple those embeddings, and reports full expressivity, useful empirical performance, interpretability, and weight-tying support.
Problem
Knowledge graph completion needs to predict missing triples, but CP independently learns an entity’s head and tail embeddings, limiting its performance.
Method
SimplE enhances CP by using inverse relations and averaging the original and inverse CP scores to couple each entity’s two vectors.
Results
SimplE is fully expressive and performs well empirically, matching ComplEx on WN18 and achieving state-of-the-art tensor-factorization results on FB15k.
Takeaways & Limitations
SimplE offers an interpretable bilinear model whose embeddings can incorporate three types of background knowledge through weight tying.
Takeaways & Limitations
Raw MRR can give equal scores to models despite differences in whether their top-ranked alternatives are correct, motivating filtered MRR.
Abstract
from arXiv · showhide
Knowledge graphs contain knowledge about the world and provide a structured representation of this knowledge. Current knowledge graphs contain only a small subset of what is true in the world. Link prediction approaches aim at predicting new links for a knowledge graph given the existing links among the entities. Tensor factorization approaches have proved promising for such link prediction problems. Proposed in 1927, Canonical Polyadic (CP) decomposition is among the first tensor factorization approaches. CP generally performs poorly for link prediction as it learns two independent embedding vectors for each entity, whereas they are really tied. We present a simple enhancement of CP (which we call SimplE) to allow the two embeddings of each entity to be learned dependently. The complexity of SimplE grows linearly with the size of embeddings. The embeddings learned through SimplE are interpretable, and certain types of background knowledge can be incorporated into these embeddings through weight tying. We prove SimplE is fully expressive and derive a bound on the size of its embeddings for full expressivity. We show empirically that, despite its simplicity, SimplE outperforms several state-of-the-art tensor factorization techniques. SimplE's code is available on GitHub at https://github.com/Mehran-k/SimplE.
1 Introduction
Knowledge graphs are incomplete, motivating link prediction from existing triples. SimplE addresses a key CP limitation by tying entity representations while retaining a simple tensor-factorization design.
- Knowledge graph completion predicts new triples from existing links in incomplete knowledge graphs.
- Tensor factorization models score triples using embeddings for the head entity, relation, and tail entity.
- CP learns independent head and tail vectors for each entity, which has caused poor knowledge-graph-completion performance.
- SimplE enhances CP to address the independence between an entity’s two embedding vectors.
- SimplE is presented as bilinear, fully expressive, capable of weight tying, and empirically strong despite its simplicity.
2 Background and Notation
This section establishes notation for vectors, matrices, triples, truth assignments, relations, and tensor-factorization models. It also defines full expressivity as the ability to represent any ground-truth assignment over triples.
- Vectors use lowercase letters, matrices use uppercase letters, and concatenation is written with semicolon-separated vectors.
- A triple is represented as (h, r, t), with a head entity, relation, and tail entity.
- A knowledge graph is a subset of the triples that are true in a world, while ζ′ denotes false triples.
- A tensor-factorization model learns entity and relation embeddings plus a prediction function for triple truth.
- Full expressivity requires embedding values that realize any assignment of truth values to all triples.
3 Related Work
Related work groups knowledge-graph models into translational, multiplicative, and deep-learning approaches. These families differ in how entity and relation embeddings interact and in which relation patterns they can represent.
- Translational Approaches: Translational approaches define additive functions over entity and relation embeddings.
- Multiplicative Approaches: Multiplicative approaches define product-based functions over embeddings.
- Multiplicative Approaches: DistMult cannot distinguish head from tail entities and therefore models only symmetric relations.
- Multiplicative Approaches: ComplEx extends DistMult with complex-valued entity and relation vectors and expands into four trilinear terms.
- Deep Learning Approaches: Deep-learning approaches use neural networks to learn interactions among head, relation, and tail embeddings.
4 SimplE: A Simple Yet Fully Expressive Model
CP independently learns each entity’s head and tail behavior, preventing information from one relation context from affecting the other. SimplE uses inverse relations to couple these vectors through averaged CP scores and is trained with minibatch stochastic gradient descent.
- CP assigns each entity separate head and tail vectors, updating only the role-specific vectors observed in each triple.
- In CP, movie information learned from acted observations does not affect predictions for likes observations.
- SimplE uses inverse relations to address the independence between an entity’s two CP vectors.
- SimplE represents each entity with two vectors and each relation with vectors for the relation and its inverse.
- SimplE scores a triple by averaging the CP scores of the triple and its inverse-relation counterpart.
- Training uses minibatch stochastic gradient descent with generated negative triples and L2-regularized optimization.
5 Theoretical Analyses
Theoretical analysis establishes SimplE’s full expressivity, interpretable parameter sharing, and linear computational complexity, while identifying representational restrictions in several translational models.
- 5.1 Fully Expressiveness: SimplE represents any ground truth over entities E and relations R with embedding size min(|E| · |R|, γ + 1), where γ is the number of true facts.This provides an explicit upper bound for full expressivity.
- 5.1 Fully Expressiveness: FSTransE is not fully expressive: reflexive relations must also be symmetric and transitive, with an additional restriction on entities related to subsets.The corollary extends these restrictions to TransE, FTransE, STransE, TransH, and TransR.
- 5.2 Incorporating Background Knowledge into the Embeddings: SimplE embeddings support interpretation by treating entity-vector elements as features and relation-vector elements as feature importance measures.The paper connects this representation to incorporating observed entity features and transferring embeddings to other domains.
- 5.2 Incorporating Background Knowledge into the Embeddings: SimplE can encode symmetric, antisymmetric, and inverse relations by tying relation parameters to one another or to their negatives.These constraints can be applied selectively to relations rather than enforced globally.
- 5.3 Time Complexity and Parameter Growth: O(d) is the time complexity of SimplE and SimplE-ignr; with equal parameter counts, they require respectively 2× and 4× fewer computations than ComplEx.SimplE uses two three-vector multiplications per triple, compared with four for ComplEx.
- 5.4 Family of Bilinear Models: SimplE is a bilinear model whose constrained relation matrices add parameters corresponding to inverse relations compared with CP.This places SimplE within the bilinear-model family while modifying CP’s matrix constraints.
6 Experiments and Results
The experiments evaluate SimplE against tensor-factorization and other baselines on WN18 and FB15k, using filtered ranking metrics and background-knowledge variants. SimplE performs competitively on both benchmarks and benefits substantially from incorporating background knowledge through tied parameters.
- Datasets and baselines: Experiments use WN18 and FB15k, comparing SimplE with CP, TransE, TransR, DistMult, NTN, STransE, ER-MLP, and ComplEx.The study uses the same train/validation/test splits as prior work.
- Evaluation metrics: Filtered MRR excludes known true triples from train, validation, and test when ranking candidate entities, while hit@k measures the percentage ranked within k.The filtered procedure addresses cases where multiple candidate triples are correct.
- Entity prediction results: On WN18, SimplE-ignr and SimplE perform as well as ComplEx, while on FB15k SimplE outperforms existing baselines and achieves state-of-the-art results among tensor-factorization approaches.SimplE performs especially well on FB15k in filtered MRR and hit@1.
- Entity prediction results: Bilinear approaches generally outperform translational and deep-learning approaches, while highly parameterized models such as NTN and STransE perform poorly, likely because of overfitting.The authors also relate translational limitations to restrictions on representable relations.
- Incorporating background knowledge: With background knowledge encoded through parameter tying, filtered MRR rises from 0.384 to 0.776 for SimplE and from 0.221 to 0.772 for SimplE-ignr.The corresponding hit@1, hit@3, and hit@10 values also increase substantially for both tied-parameter variants.
7 Conclusion
The paper concludes that SimplE is a simple, interpretable, fully expressive bilinear model for knowledge graph completion. It also identifies parameter tying as a way to incorporate several types of background knowledge into its embeddings.
- Conclusion: SimplE is presented as a simple, interpretable, fully expressive bilinear model for knowledge graph completion.The conclusion describes these as central properties of the proposed model.
- Conclusion: Three types of background knowledge can be incorporated into SimplE by tying embeddings.The conclusion lists combining SimplE with other relational-learning and logic-based techniques as future directions.