Source-linked AI summary
Compositional Vector Space Models for Knowledge Base Completion
Arvind Neelakantan, Benjamin Roth, Andrew McCallum
TL;DR
KB completion seeks to infer missing facts, but existing methods struggle with the growth of distinct multi-hop path features. The paper composes relation embeddings recursively with RNNs, achieving stronger baseline comparisons and zero-shot inference on a large dataset. Its longer-memory limitation motivates future compositional models that better capture local structure.
Problem
Existing symbolic methods treat millions of distinct paths as separate features, limiting scalability as knowledge bases add relation types.
Method
The paper uses RNNs to compose relation embeddings recursively along arbitrary-length paths for knowledge-base completion.
Results
11% and 7%: the compositional method outperforms PRA and Cluster PRA, respectively, while the combined model improves 15% over Gardner et al. (2013).
Takeaways & Limitations
The model generalizes to paths unseen during training and can perform zero-shot inference for new relation types.
Takeaways & Limitations
The RNN may not capture important local structure as well as a classifier using bigram features, motivating longer-memory models.
Abstract
from arXiv · showhide
Knowledge base (KB) completion adds new facts to a KB by making inferences from existing facts, for example by inferring with high likelihood nationality(X,Y) from bornIn(X,Y). Most previous methods infer simple one-hop relational synonyms like this, or use as evidence a multi-hop relational path treated as an atomic feature, like bornIn(X,Z) -> containedIn(Z,Y). This paper presents an approach that reasons about conjunctions of multi-hop relations non-atomically, composing the implications of a path using a recursive neural network (RNN) that takes as inputs vector embeddings of the binary relation in the path. Not only does this allow us to generalize to paths unseen at training time, but also, with a single high-capacity RNN, to predict new relation types not seen when the compositional model was trained (zero-shot learning). We assemble a new dataset of over 52M relational triples, and show that our method improves over a traditional classifier by 11%, and a method leveraging pre-trained embeddings by 7%.
1 Introduction
Knowledge bases support reasoning but remain incomplete, motivating KB completion methods that can generalize beyond atomic path features. This paper composes relation embeddings with an RNN to reason over multi-hop paths, enabling unseen-path and zero-shot inference.
- Knowledge bases contain millions of relational triples that support reasoning about resolved entities and their relations.
- KB completion adds missing triples by inferring facts from existing knowledge-base facts.
- Symbolic path methods treat each distinct path as a separate feature, causing rapid feature growth as relation types increase.
- The paper combines path-based conjunctions, vector-embedding generalization, and non-atomic composition to improve multi-hop reasoning.
- An RNN recursively composes relation vectors along arbitrary-length paths and outputs a vector near the path’s endpoint relation.
- The work contributes over 52 million triples and supports unseen-path prediction and zero-shot prediction of relation types.
- 11% and 7%: the compositional method outperforms PRA and Cluster PRA, respectively, on the new large-scale dataset.
2 Background
The paper uses PRA to collect paths connecting entity pairs and represents variable-length sequences with recursively composed vectors.
- PRA obtains paths connecting entity pairs through heuristic random walks that retain the most common paths.
- The method uses PRA to find millions of distinct paths per relation type without using PRA’s random-walk probabilities.
- An RNN constructs vector representations for sequences of arbitrary length by repeatedly applying a composition function.
3 Recurrent Neural Networks for KB Completion
The model represents relations and paths as vectors, recursively composing relation embeddings with an RNN to predict missing relations in a knowledge base. Training uses observed facts, unobserved negatives, and latent selection of the most predictive path.
- 3 Recurrent Neural Networks for KB Completion: For a path, the RNN recursively combines the accumulated left-to-right path representation with the next relation vector and outputs a new composed vector.The resulting vector is intended to lie near the relation connecting the path’s first and last entities.
- 3 Recurrent Neural Networks for KB Completion: The model represents each binary relation and path as a d-dimensional vector, using an RNN to compose relations along arbitrary-length paths.At each step, the RNN combines the next relation vector with the accumulated path vector.
- 3 Recurrent Neural Networks for KB Completion: The model predicts a target relation by comparing the composed path vector with the target relation vector using a sigmoid function.The worked example predicts CountryOfHeadquarters from the path IsBasedIn → StateLocatedIn → CountryLocatedIn.
- 3.1 Model Training: Training uses observed facts as positives and unobserved instances as negatives, while treating the predictive path for each fact as a latent variable.The latent path is assigned by selecting the path whose representation has the maximum dot product with the target relation vector.
- 3.1 Model Training: More sophisticated path-ordering schemes did not produce significant improvements over the model’s left-to-right traversal.The paper reports this result as a training-related limitation.
- 3.1 Model Training: The parameters are trained by maximizing regularized log likelihood, with gradients accumulated through the selected paths and optimization performed by backpropagation through structure.Relation vectors and the composition matrix are randomly initialized in the standard model.
4 Zero-shot KB Completion
The zero-shot model is designed to predict relation types absent from training by sharing one composition matrix and fixing relation vectors to pretrained representations. It therefore extends path-based inference to unseen target relations using their pretrained vectors at prediction time.
- 4 Zero-shot KB Completion: Zero-shot KB completion targets relation types that are unavailable during training but have vector representations available at prediction time.The paper frames this capability as important because KB completion involves thousands of relation types.
- 4 Zero-shot KB Completion: The zero-shot variant learns one general composition matrix for all relations instead of a separate matrix for each predicted relation.For example, a two-relation path is composed with f(W[vr(IsBasedIn); vr(StateLocatedIn)]).
- 4 Zero-shot KB Completion: Relation vectors are initialized from pretrained representations and kept fixed so unseen target relations retain usable vectors at prediction time.Only the general composition matrix is learned in this model.
- 4 Zero-shot KB Completion: At prediction time, the model compares a path representation computed with the general composition matrix against pretrained relation vectors to score unseen relations.This permits prediction for relations regardless of whether they appeared during training.
5 Experiments
Experiments evaluate the compositional RNN on a large Freebase–ClueWeb dataset, comparing it with path-based classifiers and testing unseen paths and zero-shot relation prediction.
- 5.1 Data: The dataset combines Freebase with ClueWeb and contains over 52 million triples for path-based knowledge base completion.ClueWeb sentences containing two Freebase-linked entities provide additional relation types.
- 5.3 Results: RNN predictions include high-quality paths unseen during training, indicating generalization beyond observed path types.Table 2 reports predictive paths for four target relations, including seen and unseen examples.
- 5.3 Results: Training with all path types improves every method over training with only the top 1,000 paths, while RNN significantly outperforms PRA Classifier and Cluster PRA Classifier.The RNN’s performance is similar with randomly initialized and pre-trained relation vectors.
- 5.3 Results: The bigram-feature baseline performs comparably to RNN, with differences from RNN not statistically significant.Bigram features extend the classifier approach and make naive PRA as effective as Cluster PRA.
- 5.3.2 Discussion: Combining RNN and PRA Classifier-b predictions yields a statistically significant gain over PRA Classifier-b.The two models have different strengths: the classifier memorizes local structure, whereas RNN generalizes better to substantially different unseen paths.
- 5.3.1 Zero-shot: The zero-shot model performs significantly better than a random baseline without direct supervision for the target relation types.Fully supervised RNN remains substantially stronger than the zero-shot model.
- 5.3.2 Discussion: The authors suspect RNN does not capture some important local structure as well as the bigram-feature classifier.They propose longer-memory compositional models as future work.
6 Related Work
Related work spans symbolic inference rules, path-based classifiers, vector embeddings, attention-like path selection, and zero-shot learning across other domains.
- 6 Related Work: Early KB-completion methods learn one-hop rules or select accurate paths, but exhaustive path exploration does not scale well to modern knowledge bases.PRA improves efficiency and robustness by replacing exhaustive search with random walks and using unique paths as features.
- 6 Related Work: Prior PRA extensions use relation embeddings to cluster paths or map unseen paths to nearby observed paths, but neither performs zero-shot learning.These methods retain an atomic-path classifier as their core mechanism.
7 Conclusion
The paper develops a compositional RNN-based vector-space model for large-scale KB completion, outperforming two baselines and enabling zero-shot inference.
- 7 Conclusion: The compositional RNN model outperforms two baseline methods and performs competitively with a modified stronger baseline on a challenging large-scale dataset.Combining the model with the modified baseline achieves a 15% improvement over Gardner et al. (2013).
- 7 Conclusion: The model can perform zero-shot inference for relation types without direct training on those target types.This capability follows from the paper’s compositional vector-space approach.