Source-linked AI summary
Tensor Decompositions for temporal knowledge base completion
Timothée Lacroix, Guillaume Obozinski, Nicolas Usunier
TL;DR
Temporal link prediction requires completing knowledge-base queries whose answers depend on time, but most relational representation-learning methods were designed for static data. The paper formulates the task as order-4 tensor completion, adds regularization and a ComplEx extension, and reports state-of-the-art performance alongside a large Wikidata benchmark. The benchmark contains 400k entities and 7M training triples, with 10% carrying temporal validity information.
Problem
Temporal link prediction asks which facts hold at a specific time, extending knowledge-base completion beyond static queries.
Method
The paper models temporal knowledge bases with an order-4 tensor, timestamp embeddings, temporal regularization, and separate non-temporal structure within a ComplEx-based decomposition.
Results
The method outperforms the state of the art at similar parameter counts, with larger regularized models improving absolute Mean Reciprocal Rank (MRR) by up to 0.07.
Takeaways & Limitations
The paper provides tensor-based temporal-completion methods and a large Wikidata dataset for evaluating temporal and non-temporal knowledge-base completion.
Takeaways & Limitations
The cross-entropy loss restricts embedding dimensionality to about d = 100 for batch-size 1000, while sampled-loss training for higher dimensions is left for future work.
Abstract
from arXiv · showhide
Most algorithms for representation learning and link prediction in relational data have been designed for static data. However, the data they are applied to usually evolves with time, such as friend graphs in social networks or user interactions with items in recommender systems. This is also the case for knowledge bases, which contain facts such as (US, has president, B. Obama, [2009-2017]) that are valid only at certain points in time. For the problem of link prediction under temporal constraints, i.e., answering queries such as (US, has president, ?, 2012), we propose a solution inspired by the canonical decomposition of tensors of order 4. We introduce new regularization schemes and present an extension of ComplEx (Trouillon et al., 2016) that achieves state-of-the-art performance. Additionally, we propose a new dataset for knowledge base completion constructed from Wikidata, larger than previous benchmarks by an order of magnitude, as a new reference for evaluating temporal and non-temporal link prediction methods.
1 INTRODUCTION
The paper frames temporal link prediction as completing time-indexed knowledge-base facts and develops tensor-based models with regularization for evolving and non-temporal relations. It also evaluates these models against prior work and introduces a substantially larger Wikidata dataset.
- Motivation: Temporal link prediction finds missing graph links at precise points in time, including queries whose correct object ranking changes with the timestamp.Temporal knowledge bases attach intervals or event timestamps to facts.
- Tensor formulation: The problem is represented as completion of a binary order-4 tensor indexed by subject, predicate, object, and discretized timestamp.Timestamps form the tensor's fourth mode.
- Model: The proposed ComplEx decomposition produces timestamp embeddings and regularizes them with a prior favoring slow temporal evolution.The regularizer is described as a variation on the nuclear p-norm.
- Model: A non-temporal component is added to handle heterogeneous knowledge bases containing many relations without temporal information.
- Results: The method outperforms the state of the art with similar parameter counts, while larger regularized models improve absolute Mean Reciprocal Rank (MRR) by up to 0.07.The reported improvement is on additional experiments with larger, regularized models.
- Dataset: The proposed Wikidata dataset contains 400k entities and 7M training triples, with 10% containing temporal validity information.It is presented as larger than usual knowledge-base-completion benchmarks.
2 RELATED WORK
Related work covers tensor decompositions and alternative temporal models for knowledge-base completion. The paper positions its contribution as a regularized CP decomposition extended to temporal data.
- Static link prediction methods: Standard tensor decompositions, including CP, have produced strong results for static knowledge-base completion.CP is presented as the tensor analogue of low-rank matrix decomposition.
- Static link prediction methods: DistMult uses shared factors but represents only symmetric score functions, while ComplEx uses complex parameters to model beyond-symmetric relations.
- Static link prediction methods: Variational tensor nuclear-norm regularization and a transformed learning objective led to state-of-the-art results for a prior tensor model.
- Static link prediction methods: Alternative methods such as TransE use translated embeddings but are limited in the relation systems they can model and do not achieve state-of-the-art benchmark performance.
- Temporal link prediction methods: Prior temporal approaches include Bayesian models, tensor decompositions, frequency-modulated embeddings, timestamp-specific Tucker cores, and recurrent transformations of standard-model embeddings.The paper notes that one-embedding-matrix-per-timestamp learning is unsuitable for its considered scales.
- This work: This work extends regularized CP decomposition to an order-4 tensor and studies several regularizers suited to the resulting temporal decompositions.
3 MODEL
The model represents temporal knowledge-base completion as an order-4 tensor problem, extending ComplEx with timestamp embeddings and a non-temporal component. It combines tensor-norm-based regularization with temporal smoothness penalties and evaluates their effects on TNTComplEx.
- Temporal tensor formulation: Timestamped facts are discretized into 4-tuples indexing an order-4 tensor, and training uses an instantaneous multiclass loss for (subject, predicate, ?, time) queries.The loss is specifically suited to queries that predict the object at a given time.
- Temporal decomposition: TComplEx extends ComplEx with timestamp embeddings that modulate the multilinear product, with parameters scaling by the number of timestamps rather than entities.The timestamp can equivalently modulate object, predicate, or subject representations.
- Non-temporal predicates: TNTComplEx adds a non-temporal tensor component for heterogeneous knowledge bases containing both time-varying and time-invariant predicates.Parameter sharing between temporal and non-temporal parts removes one hyperparameter, and preliminary experiments favored sharing.
- Regularization: The regularization design combines weighted nuclear 3-norm variational forms with a temporal penalty that encourages neighboring timestamp embeddings to remain close.Unfolding predicate and timestamp modes permits weighting by their joint marginal, while the temporal penalty acts on discrete embedding differences.
- Regularization: A new tensor atomic norm arises from combining the temporal smoothness penalty with the variational nuclear p-norm formulation.The paper notes that nuclear p-norm computation is NP-hard and therefore uses a fixed-rank variational form as a practical regularizer.
- Experimental impact: 0.05 MRR increase is obtained from careful regularization, while ∆4 and Ω3 outperform lower-order counterparts and smoothness improves MRR by over 2 points on ICEWS05-15.The comparisons concern TNTComplEx regularization experiments on ICEWS05-15.
4 A NEW DATASET FOR TEMPORAL AND NON-TEMPORAL KNOWLEDGE BASE COMPLETION
The paper introduces a large Wikidata-based benchmark addressing limitations in prior temporal knowledge-base datasets. It retains entity-valued facts with timestamp ranges for scalable temporal and non-temporal completion.
- The prior Wikidata-based dataset contained numerical entities, unwieldy interval encoding, and only 11k entities and 150k facts.
- The authors created a Wikidata dataset to address these limitations and released it with the paper’s code.
- Filtering produced 432715 entities, 407 predicates, and 1724 timestamps, retaining only years.
- For each datum, training and evaluation sample a timestamp uniformly within its validity range before ranking objects for the temporal query.
5 EXPERIMENTAL RESULTS
Experiments compare the proposed temporal models with ComplEx and established temporal baselines across existing benchmarks and Wikidata. Results show strong performance, benefits from modeling non-temporal relations, and modest runtime overhead.
- Experimental setup: The experiments evaluate filtered MRR on ICEWS14, ICEWS05-15, and Yago15k against baselines selected for their reported performance.
- Existing benchmarks: The proposed model matches or beats the state of the art on all datasets at identical parameter counts.
- Wikidata: ComplEx remains strongest on Wikidata’s average MRR because 90% of triples lack temporal data, while TNTComplEx improves on temporal triples.
- Runtime: TNTComplEx trains at 5.6k triples per second versus 5.8k for ComplEx, with experiment times of 7.2 and 6.9 hours, respectively.
6 QUALITATIVE STUDY
The qualitative study adds temporal-tube supervision and examines whether scores track facts across time. The combined loss improves temporal-query performance while preserving most overall MRR.
- The instantaneous loss ranks objects at sampled timestamps, so an auxiliary temporal-tube loss is introduced for queries of the form (subject, predicate, object, ?).
- Optimizing both losses loses only 1 MRR point overall while improving the model’s ability to answer queries along the time axis.
- The macro area under the precision recall curve rises from 0.92 with ℓ alone to 0.98 with ℓ+ ˜ℓ.
- For French presidents, score peaks closely match the ground-truth start and end dates despite training that samples timestamps only within valid intervals.
7 CONCLUSION
The paper extends tensor methods to temporal knowledge-base completion and reports higher performance than the state of the art at similar parameter counts. It also contributes a large-scale temporal dataset for evaluating temporal and non-temporal completion.
- The proposed tensor methods handle point-in-time, beginning-and-ending, and interval temporal datasets.
- The methods achieve higher performance than the state of the art with similar numbers of parameters.
- Higher-dimensional results are provided for several datasets to motivate models with greater expressivity at lower parameters per entity.
- A large-scale temporal dataset is proposed to represent challenges in large-scale temporal completion.
- The dataset may also support evaluation of non-temporal knowledge-base completion methods.
8 APPENDIX
The appendix details the order-4 tensor formulation, its regularization interpretation, dataset statistics, and parameter-matched experimental procedures. It also reports uncertainty estimates and rank settings used for comparisons.
- Tensor decomposition: Unfolding the order-4 decomposition along modes 3 and 4 produces an order-three tensor with W ◦ T as its factor.The Khatri-Rao product is the column-wise Kronecker product.
- Tensor decomposition: For a fourth mode of size L, the Khatri-Rao factor has entries wk ⊙ tl, motivating the regularizers used in Section 3.2.
- Regularization: The regularizer Ω(U, V, W, T) has a variational form involving an atomic norm whose atoms are four-way outer products.The atom constraints use fourth norms for u, v, and w, and the τ4 norm for t.
- Regularization: The appendix relates the stated regularizer to a variational form of the nuclear 3-norm for an order-4 tensor.
- Regularization: Weighted norms coincide when Dpred/time = DpredDtime, but the application allows different weightings because time and predicate are likely dependent.
- Experiments: Standard deviations for TNTComplEx MRR are reported over five runs across ICEWS14, ICEWS15-05, Yago15k, Wikidata (T), and Wikidata (NT).The reported standard deviations are 0.0016, 0.0011, 0.00076, 0.0035, and 0.0012, respectively.
- Experiments: Ranks are selected to match DE-SimplE in dimension 100 using parameter counts and dataset statistics.