Tensor Decompositions for Temporal Knowledge Base Completion
Authors: Timothée Lacroix
Guillaume Obozinski
Nicolas Usunier
Venue:  (2020)
Keywords: knowledge base completion
temporal embeddings

Abstract: 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 of the form (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 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. 

Published as a conference paper at ICLR 2020
TENSOR DECOMPOSITIONS FOR TEMPORAL KNOWLEDGE BASE COMPLETION
Timothee Lacroix! Guillaume Obozinski', Nicolas Usunier' Facebook AI Research 2 ENPC Swiss Data Science Center, EPFL & ETH Zürich timothee 1ax gmw.l.gmal..... com guillaure wwozinski@epfl.ccoomm... usunier fb. com
ABSTRACT
Most algorithms for representation learning and link prediction in relational data have been designed for static data. However, the data they are applied 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 tem- poral constraints, i.e., answering queries such as (US, has president, 2, 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 Com- plEx (Tromilon et al 201G) that achieves ally, 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.
performance. Addition-
INTRODUCTION
Link prediction in relational data has been the subject of interest, given the widespread availability of such data and the breadth of its use in bioinformatics (Zitmık et all 2018). recommender systems (Koren et all, 2009) or Knowledge Base completion (Nickel et all 20)6a). Relational data is often temporal, for example, the action of buying an item or watching a movie is associated to timestamp. Some medicines might not have the same adverse side effects depending on the subject's age. The task of temporal link prediction is to find missing links in graphs at precise points time.
In this work, we study temporal link prediction through the lens of temporal knowledge base comple- tion, which provides varied benchmarks both in terms of the underlying data they represent, but also in terms of scale. A knowledge base is set of facts (subject, predicate, object) about the world that are known to be true. Link prediction in a knowledge base amounts to answer incomplete queries of accurate ranking of potential objects. In temporal
the form (subject, predicate, ?) by providing knowledge bases, these facts have some temporal metadata attached. For example, facts might only hold for certain time interval, in which case they will be annotated as such. Other facts might be event that happened at a certain point in time. Temporal link prediction amounts to answering queries of the form (subject, predicate, timestamp). For example, we expect the ranking of queries (USA, president, ?, timestamp) to vary with the timestamps.
As tensor factorization methods have proved successful for Knowledge Base Completion (Nickel at 60 [Trouilon all 2016; L Lacroix all 2018). we express our Temporal Knowledge Base Completion problem as an order tensor completion problem. That is, timestamps are discretized and used to index a 4-th mode in the binary tensor holding (subject, predicate, object, timestamps) facts.
First, we introduce a ComplEx (Irouillon et all 2016) decomposition of this order 4 tensor, and link with previous work on temporal Knowledge Base completion. This decomposition yields embeddings for each timestamps. A natural prior is for these timestamps representation to evolve slowly over time. We are able to introduce this prior as a regularizer for which the optimum is a
"Université Paris-Est, Equipe Imagine, LIGM (UMR8049) Feole des Ponts ParisTech, Mame-la-Vans Vallée

---

Published as a conference paper at ICLR 2020
variation the nuclear p-norm. In order to deal with heterogeneous temporal knowledge bases where a sigmificant amount of relations might be non-temporal, we add a non-temporal component to our decomposition.
Experiments on available benchmarks show that our method outperforms the state of the art for similar number of parameters. We additional experiments for larger, regularized models and obtain improvements of up to 0.07 absolute Mean Reciprocal Rank (MRR).
Finally, we propose dataset of 400k entities, based Wikidata, with 7M train triples, of which 10% contain temporal validity information. This dataset is larger than usual benchmarks in the Knowledge Base completion community and could help bridge the gap between the method de- signed and the envisaged web-scale applications.
2 RELATED WORK
Matrices and tensors are upper case letters. The i-th row of U denoted by u, while it's j th column is denoted by U..-. The tensor product of two vectors is written @ and the hadamard (elementwise) product C.
Static link prediction methods Standard tensor decomposition methods have lead to good results (Yang et all 2014: et 2016: Lacroix et all 2018; Balazević et all, 2019) in Knowledge Base completion. The Canonical Polyadic (CP) Decomposition (Hitchhock), (1277) is the tensor equivalent to the low-rank decomposition of a matrix. A tensor X of canonical rank R can be written as:
n x= OV. &W. = [U W. + V(i.j.)), X = Σ Us. = (uis Uy. wg) r=1
R
r=l
Setting U- W leads to the Distmult (Yang et al. 2014) model, which has been successful, despite only being able represent symmetric score functions. In order to keep the parameter sharing scheme but go beyond symmetric relations, Trouiloo et all (2016) use complex parameters and set W to the complex conjugate of U, U. Regularizing this algorithm with the variational form of the tensor nuclear norm as well as slight transformation to the learning objective (also proposed in Kazemı Poold (2018) leads to state of the results in Lacroix all (2018).
Other methods are not directly inspired from classical tensor decompositions. For example, TransE (Bordes all 2013) models the score distance of the translated subject to an object represen- tation. This method has lead to many variations (li ei all 2015: Nguyen et all 2016: Wang et all 2014), but limited in the relation systems it can model (Kazemi Poole, 2018) and does not lead to state of the art performances to generate the entity embeddings of a CP-like tensor decomposition by running forward pass of Graph Neural Network over the training Knowledge Base. The experiments included in this work did not lead to better link prediction performances than the same decomposition (Distmult) directly optimized (Kadlec all, 2017).
current benchmarks. Finally Schlichikrull et all (2018) propose
Temporal link prediction methods Sarkar & Moore (2(M)) describes a bayesian model and learn- ing method for representing temporal relations. The temporal smoothness prior used in this work is similar to the gradient penalty we describe in Section G.L However, learning one embedding matrix per timestamp is not applicable to the scales considered in this work. Bader et all (2007) uses ten- sor decomposition called ASALSAN to express temporal relations. This decomposition is related to RESCAL Nickel 2 which underperforms on recent benchmarks due to overfitting (Nickell
R
20166).
For temporal knowledge base completion, Goel (1)2)) learns entity embeddings that change over time, by masking fraction of the embedding weights with activation function of learned frequencies. Based on the Tucker decomposition, ConT aM 2013 learns one new core tensor for each timestamp. Finally, viewing the time dimension
sequence be predicted, Garcia Duran et all (20T8) use recurrent neural nets to transform the embeddings of standard models such as TransE Distmult to accomodate the temporal data.
2

---

Published as a conference paper at ICLR 2020
DE-SimplE TComplEx
2r (r3 + (1 +)) + IPD)
2r + T P))
INTComplEx
2r( + [T' Pl)
Table 1: Number of parameters for each models considered
This work follows Lacroix al (2018) by studying and extending a regularized CP decomposition of the training seen as an order tensor. We propose and study several regularizer suited to our decompositions.
MODEL
In this section, we are given facts (subject, predicate, object) annotated with timestamps, we dis- cretize the timestamp range (eg. by reducing timestamps to years) in order to obtain a training set of 4-tuple (subject, predicate, object, time) indexing an order 4 tensor. We will show in Section 5 how reduce each datasets to this setting, Following Lacroix all (2018), minimize, for each of the train tuples [i,j, k. 1), the instantaneous multiclass loss
Σ exp (Koss=)) K
(i.j..)))) = - -X.j... + log
(1)
Note that this loss is only suited to queries of the type (subject, predicate, ?, time), which is the queries that were considered in related work. We consider another auxiliary loss in Section El which (augmented with reciprocal relations (Lacroix et al, 2018, Kazemi Ponlé, 20TS),, and parametric tensor estimate X (0). minimize the following objective, with a weighted regularizer Q::
will
Wikidata dataset. For training
((( = S
(()(0): (1,J,K,1) + XΩ(O: (1.j, (i.j...))S
Σ
The ComplEx (Iromilon et al. AUG decomposition can naturally be extended this setting by adding new factor T. then have:
{U,V = Re ([U, = X(U.V,T)..A.. = Re ((us, Bj U. tt))
(2)
We call this decomposition TComplEx. Intuitively, we added timestamps embedding that modulate the multi-linear dot product. Notice that the timestamp be used to equivalently modulate the objects, predicates or subjects to obtain time-dependent representation:
(u,, U/ up. t²) = (i + ti, By wx) (u,, 2y @ tl, w.) = (u4, 2y up ② tz).
Contrary to DE-SimplE (Gioel ct all 2020), we do not learn temporal embeddings that scale with the number of entities (as frequencies and biases), but rather embeddings that scale with the number of timestamps. The number of parameters for the two models are compared in Table MI
3.1 NON-TEMPORAL PREDICATES
Some predicates might not be affected by timestamps. For example, Malia and Sasha will always be the daughters of Barack and Michelle Obama, whereas the "has occupation" predicate between two entities might very well change over time. In heterogeneous knowledge bases, where some predicates might be temporal and some might not be, propose decompose the tensor X the sum of two tensors, one temporal, and the other non-temporal:
Re
(UV = Xis.R.1 Re ((ui, @ Ug uk))
3

---

Published as a conference paper at ICLR 2020
We call this decomposition INTComplEx. Goel ee
(2020) suggests another way of introducing a non-temporal component, by only allowing a fraction y of components of the embeddings to be modulated in time. By allowing this sharing of parameters between the temporal and te-memoora part of the tensor, our model removes one hyperparameter. Moreover, preliminary experiments showed that this model outperforms without parameter sharing.
3.2 REGULARIZATION
Any order 4 tensor can be considered as an order tensor by unfolding modes together. For a tensor X R XNxxNgx,, unfolding modes 3 and together will lead to tensor X IR MRaMx.a.,,,,
(Kolda & Baden (09))
We can see both decompositions (L)) and (G)) as order tensors by unfolding the temporal and predi- cate modes together. Considering the decomposition implied by these unfoldings (see Appendix g. leads us to the following weighted regularizers (Lacroix et all 2018):
1 (I,, = 3 (1|=g]1 + Lu 11 +
110
O ttll3)
(4)
1
V,T - (2 2
1
lof
411 + 11y)
The first regularizer weights objects, predicates and pairs (predicate, timestamp) according to their respective marginal probabilities. This regularizer is variational form of the weighted nuclear 3- norm on an order tensor (see subsection [44 and Appendix 8 for details and proof). The second regularizer is the sum of the nuclear penalties on tensors [U, Vt U,7] and [U,VUU.
3.3 SMOOTIINESS OF TEMPORAL EMBEDDINGS
We have more priori structure on the temporal mode than on others. Notably, we expect smoothness of the application i + f.. In words, expect neighboring timestamps to have close representations. Thus, we penalize the norm of the discrete derivative of the temporal embeddings:
T--1
Σ (T) = [ - 2=1
|t
t.l..
(5)
We show in Appendix 8.2 that the sum of Ap and the variational form of the nuclear norm (G) lead to variational form of a new tensor atomic norm.
3.4 NUCLEAR N-ROMMS OF TENSORS AND THEIR VARIATIONAL FORMS
As was done in Lacroix et all (2018), we aim to use tensor nuclear p-norms as regularizers. The definition of the nuclear p-norm of tensor (Enedland Lim, 2018 of order D is:
R
X Ipp
inf a.R,U U(D) |alli X Σ
a. U 8 ... & ( Vr, d II b
This formulation of the nuclear p-norm writes tensor tensors of unit p-norm factors. The nuclear p-norm NP-hard to compute (Ereelladd Lam (188) Following Lacroix et all (2018), practical solution is to the equivalent formulation of nuclear p-norm using their variational form, which can conveniently written for D:
atoms which are the rank-1
|||||
1
inf ΣΣ
D x UUD] d=tr=l
For the equality above to hold, the infimum should be over all possible R. The practical solution is to fix R to the desired rank of the decomposition. Using this variational formulation regularizer leads to state of the art results for order-3 tensors (Lacroix et all 2018) and convenient a stochastic gradient setting because it separates over each model coefficient.
4

---

Published as a conference paper at ICLR 2020
In addition, this formulation makes easy introduce weighting recommended in Srehro & Salakhuddmox (20T1;; Foygel et all (20TT). In order to learn under non-uniform sampling distribu- tions, one should penalize the weighted norm I| (VMO) VM X||2>, where M and (2) are the empirical row and column marginal of the distribution. The variational form (S) makes this easy, by simply penalizing rows (:(1) ..... (:(D) for observed triple (i....,ip)) in stochastic gradient descent. More precisely for D and N(d) the vectors holding the observed count of each index over each mode d:
(2)2 |uu
N S
|uu1l +
Σ S
10y112 Σ M 11ss
Σ M, 2 1,y112 J
JS]
(1))S
In subsection we add another penalty in Equation (5) which changes the norm of our atoms. In subsection 6 we introduced another variational form in Equation (L) which allows to easily pe- nalize the nuclear 3-norm of an order 4 tensor. This regularizer leads to different weighting. By considering the unfolding of the timestamp and predicate modes, are able to weight according to
the joint marginal of timestamps and predicates, rather than by the product of the marginals. This can be an important distinction if the two are not independent.
3.5 EXPERIMENTAL IMPACT OF THE REGULARIZERS
We study the impact of regularization on the ICEWS05-15 dataset, for the TNTComplEx model. For details the experimental set-up, see Section 5. The first effect we want quantify is the effect of the regularizer Ap. We run a grid search for the strength of both Ap and Ω and plot the convex hull as function of the temporal regularization strength. As shown Figure M. imposing smoothness along the time mode brings an improvement of over 2 MRR point.
The second effect we wish quantify is the effect of the choice of regularizer Ω. A natural regular- izer for INTComplEx would be
AU V,T; k,), (2) 21| + 1o + || + 11s)1p))
We compare A A and A with 523 The comparison done with a temporal regularizer of 0 to reduce the experimental space.
A is the common weight-decay frequently used deep-learning. Such regularizers have been used in knowledge base completion (Nickel et 2о 20166: [rourlon et all 2016), however, Lacroix (2018) showed that the infimumm of this penalty is non-come non-convex over tensors.
A mmtchhes the order used in the Ω regularizer, and in previous work on knowledge base completion (Lacroix et all 2018). However, by the same arguments, its minimization does not lead to a convex
penalty over tensors.
A is the sum of the variational forms of the Nuclear 4-norm for the two tensors of order in the TNTComplEx model according to equation (k))
Detailed results of the impact of regularization on the performances of the model are given in Fig- ure M The two regularizers A and Ω are the only regularizers that can be interpreted as sums of tensor norm variational forms and perform better than their lower order counterparts.
There are two differences between A and 523. First, whereas the first is variational form of the nuclear 4-norm, the second is a variational form of the nuclear 3-norm which is closer to the nuclear 2-norm. Results for exact recovery of tensors have been generalized to the nuclear 2-norm, and to the extent of our knowledge, there has been no formal study of generalization properties or exact recovery under the nuclear p-norm for p greater than two.
Second, the weighting in A is done separately over timestamps and predicates, whereas it is done jointly for 523. This leads to using the joint empirical marginal a weighting over timestamps and predicates. The impact of weighting on the guarantees that can be obtained are described more precisely in Foygel et (2OTT).
The contribution of all these regularizers over a non-regularized model are summarized in Table Note that careful regularization leads to a 0.05 MRR increase.
5

---

Published as a conference paper at ICLR 2020
0.65
TNTComplEx
0.67
0.64
A
A
MRR
0.65
MRR
0.63
22
0.65
0.62
0.61
10
10
10
10
10-5
10-3
10
Temporal regularizer
Embedding regularizer
Figure 1: Impact of the temporal (left) regularizer and embeddings (right) regularizer on a TNT- ComplEx model trained on ICEWS05-15.
A NEW DATASET FOR TEMPORAL AND NON-TEMPORAL KNOWLEDGE BASE COMPLETION
dataset based on Wikidata was proposed by Gareia Duran al (2018). However, upon inspection, this dataset contains numerical data entities, such as ELO rankings of chess players, which not representative of practically useful link prediction problems. Also, this dataset, temporal informations is specified in the form of "OccursSince" and "OccursUnttil statements appended to triples, which becomes unwieldy when a predicate holds for several intervals in time. Moreover, this dataset contains only 11k entities and 150k which is insufficient to benchmark methods at scale.
The GDelt dataset described in Ma all (2018); Goel co (2020) holds many triples (2M), but does describe enough entities (500). In order adress these limitations, created our own dataset from Wikidata, which we make available along with the code for this paper at https:
//github. wow./aaceoookresrrccecccccceeeee
Starting from Wikidata, we removed all entities that were instance of scholarly articles, proteins and others. We also removed disambiguation, template, category and project pages from wikipedia. Then, we removed all facts for which the object was not entity. We iteratively filtered out entities that had degree at least 5 and predicates that had at least 50 occurrences. With this method, we obtained a dataset of 432715 entities, 407 predicates and 1724 timestamps (we only kept the years). Each datum is a triple (subject, predicate, object) together a timestamp range (begin, end) where begin, end or both be unspecified. Our train set contains 7M such tuples, with about 10% partially specified temporal tuples. We kept a validation and test set size 50k each.
At train and test time, for given datum (subject, predicate, object, [begin, end]), sample timestamp (appearing in the dataset) uniformly at random, in the range [begin, end]. For datum without temporal range, sample over the maximum date range. Then, rank the objects for the partial query (subject, predicate, ?, timestamp).
5 EXPERIMENTAL RESULTS
5.1 EXPERIMENTAL SET-UP
We follow the experimental set-up in Garcia- Duran from Garcia Duran et all (2018) and Goel al (2020) as baselines since they are the best performing algorithms on the datasets considered. We report the filtered Mean Reciprocal Rank (MRR) deñned in Nickel et all (20165). In order to obtaiqn comparable results, we use Table II and dataset statistics to compute the rank for each (model, dltaastt) pair that matches the number of parameters used in Goel oreletal (202I). We also report results at ranks 10 times higher. This higher rank set-up gives an estimation of the best possible performance attainable on these datasets, even though the dimension used might be impractical for applied systems. All our models optimized with Adagrad (Duchi atll 20LI). with a learning rate of 0.1, batch-size of 1000. More details on the grid search, actual given in Appendix 8
(201)
(2020). We use models
ranks used and sypeer-parameter

---

Published as a conference paper at ICLR 2020
ICEWS14
ICEWS15-05
Yago15k
Reg.
MRR
TA
0.48
0.47
0.32
No regularizer
0.62
DE-SimplE
0.53
0.51
A
0.63
ComplEx
0.47 (0.47)
0.49 (0.49)
0.35 (0.36)
A 3
0.63
TComplEx
0.56 (0.61)
0.58 (0.66)
0.35 (0.36)
A
0.64
TNTComplEx
0.56 (0.62)
0.60 (0.67)
0.35 (0.37)
Ω
0.65
Ω +A1
0.67
Table 2: Results for TA (Garefa-Durán et all 2018) and DE-SimplE (Goel et etall 2020) are the best numbers reported in the respective pa- pers. Our models have as many parameters as DE-SimplE. Numbers in parentheses for ranks multiplied by 10.
Table 3: Impact of regu- larizers on ICEWS05-15 for TNTComplEx.
We give results on 3 datasets previously used in the litterature ICEWS14, ICEWS15-05 and Yago15k. The ICEWS datasets are samplings from the Integrated Conflict Early Warning System (ICEWS) all 2015) Garcia- e (2018) introduced two subsampling of this data, ICEWS14 14 which contains all events occuring in 2014 and ICEWS05-15 which contains events occur- ing between 2005 and 2015. These datasets immediately fit in our framework, since the timestamps are already discretized.
The Y5g dataset (Garcia- Darreia-DDurncccom et al 20K) is modification of FB15k (Bordes et all 201K)
which adds "occursSince" and "occursUntil timestamps to each triples. Following the evaluation setting of Garcia-Durán all (2018), during evaluation, the incomplete triples to complete are of
the form (subject, predicate, ?, occursSince occursUntic timestamp) (with reciprocal predicates). Rather than deal with tensors of order 5, choose to unfold the (occursSince, occursUntil) and the predicate mode together, multiplying its size by two.
Some relations in Wikidata highly unbalanced (eg. (?. InstanceOf, Human)). For such relations, a ranking evaluation would not make much sense. Instead, we only compute the Mean Reciprocal Rank for missing right hand sides, since the data is such that highly unbalanced relations happen on the left-hand side. However, we follow the same training scheme as for all the other dataset, including reciprocal relations the training set. The cross-entropy loss evaluated on 400k entities puts restriction on the dimensionality of embeddings at about d 100 for batch-size of 1000. We leave sampling of this loss, which would allow for higher dimensions future work.
5.2 RESULTS
We compare ComplEx with the temporal versions described in this paper. We report results in Table 0 Note that ComplEx has performances that are stable through a tenfold increase of its number of parameters, rank of 100 is enough to capture the static information of these datasets. For temporal models however, the performance increases a lot with the number of parameters. is always beneficial to allow a separate modeling of non-temporal predicates, the performances of TNTCCmplex show. Finally, our model match or beat the state of the art on all datasets, even identical number of parameters. Since these datasets are small, we also report results for higher ranks (10 times the number of parameters used for DE-SimplE),
On Wikidata, 90% of the triples have no temporal data attached. This leads to ComplEx outper- forming all temporal models in term of average MRR, since the Non- Temporal MRR (NT-MRR) far
More information can be found at StEp:/ WWW. icews. com
MRR 0.45
NT-MRR 0.48
T-MRR
ComplEx
0.29
TComplEx
0.42
0.45
0.30
TNTComplEx
0.44
0.47
0.32
Table 4: Results wikidata for entity dimension d = 100.
7

---

Published as a conference paper at ICLR 2020
Jacques Chirac
15.0
Nicolas Sarkozy
Score
12.5
François Hollande
10.0
Emmanuel Macron
7.5
1980
1990
2000
2010
2020
Year
Figure 2: Scores for triples (President of the French republic, office holder, (Jacques Chirac Nicolas Sarkozy François Hollande Emmanuel Macron), 1980, 2020))
outweighs the Temporal MRR (T-MRR), A breakdown of the performances is available in table H. TNTComplEX obtains performances that are comparable to ComplEx on non-temporal triples, but are better temporal triples. Moreover, TNTComplEx can minimize the temporal cross-entropy (о²) and is thus more flexible on the queries can answer.
Training INTComplEx on Wikidata with rank of d 100 with the full cross-entropy Quadro GP 100, we obtain a speed 5.6% triples per second, leading to experiments time of 7.2 hours. This to be compared with 5.8k triples per second when training ComplEx for experiments time of 6.9 hours. The additional complexity of our model does not lead to any real impact on runtime, which dominated by the computation of the cross-entropy over 400k entities.
QUALITATIVE STUDY
The instantaneous loss described in equation (1), along with the timestamp sampling scheme de- scribed in the previous section only enforces correct rankings along the "object" tubes of our order-4 tensor. In order to enforce stronger temporal consistency, and be able to answer queries of the type (subject, predicate, object, ?), we propose another cross-entropy loss along the temporal tubes:
((X; (i, - log Eexp cxp (X (X....)))
We optimize the sum of defined in Equation II and defined in Equation M Doing we only lose 1 MRR point overall. However, we make our model better at answering queries along the time axis. The macro area under the precision recall curve is 0.92 for TNTComplEx model learned with é alone and 0.98 for INTComplEx model trained with & +
We plot in Figure the scores along time for train triples (president of the french republic, office holder, (Jacques Chirac Nicolas Sarkozy François Hollande Emmanuel Macron), [1980, 2020)). The periods where a score is highest matches closely the ground truth of start and end dates of these presidents mandates which is represented as colored background. This shows that models are able to learn rankings that are correct along time intervals despite our training method only ever sampling timestamps within these intervals.
CONCLUSION
Tensor methods have been successful for Knowledge Base completion. In this work, we suggest an extension of these methods Temporal Knowledge Bases. Our methodology adapts well the various form of these datasets point-in-tiin time, beginning and endings or intervals. We show that our methods reach higher performances than the state of the art for similar number of parameters. For several datasets, we also provide performances for higher dimensions. We hope that the gap between low-dimensional and high-dimensional models can motivate further research models that have increased expressivity at lower number of parameters per entity. Finally, we propose a large scale temporal dataset which we believe represents the challenges of large scale temporal completion in knowledge bases. We give performances of our methods for low-ranks on this dataset. We believe that, given its scale, this dataset could also be an interesting addition to non-temporal knowledge base completion.
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Brett W Bader, Richard A Harshman, and Tamara G Kolda. Temporal analysis of semantic graphs using asalsan, In Seventh IEEE international conference on data mining (ICDM 2007), pp- 42. IEEE, 2007.
Ivana Balažević, Carl Allen, and Timothy M Hospedales. Tucker: Tensor factorization for knowl- edge graph completion. arXiv preprint arXiv:/901.0000 2019.
Antoine Bordes, Nicolas Usunier, Alberto Gurcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating Embeddings for Modeling Multi-relational Data. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Pro- cessing Systems 26, pp. 2787-2795. Curran Associates, Inc., 2013.
Elizabeth Boschee, Jennifer Lautenschlager, Sean OBrien, Steve Shellman, James Starz, and Michael Ward. Icews coded event data. Harvard Dataverse, 12, 2015.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):2121-2159, 2011.
Rina Foygel, Ohad Shamir, Nati Srebro, and Ruslan R Salakhutdinov. Learning with the weighted trace-norm under arbitrary sampling distributions. In Advances Neural Information Processing Systems, pp- 2133-2144 2011.
Shmuel Friedland and Hen- Lim. Nuclear norm of higher-order tensors. Mathematics of Com- putation, 87(311): 2018.
Alberto García- Durán, Sebastijan Dumančić, and Mathias Niepert. Learning sequence encoders for temporal knowledge graph completion. arXiv preprint arXiv: 1809.03202, 2018.
Rishab Goel, Seyed Mehran Kazemi, Marcus Brubaker, and Pascal Poupart. Diachronic embedding for temporal knowledge graph completion. In AAAI, 2020.
Frank L. Hitchcock. The expression of tensor polyadic Applied Mathematics, 6(1-4)1164-88) 1927.
of products. Studies in
Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. Knowledge graph embedding via dynamic mapping matrix. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Pro- cessing (Volume I: Long Papers), pp. 687-696, 2015.
Rudolf Kadlec, Ondrej Bajgar, and Jan Kleindienst. Knowledge base completion: Baselines strike back. In Proceedings of the 2nd Workshop on Representation Learning for NLP, pp. 69-74, 2017.
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Advances in Neural Information Processing Systems 31, pp. 4289 4300. 2018.
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM review, 51(3): 455-500, 2009.
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8), 2009.
Timothée Lacroix. Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In Proceedings of the 35th International Conference on Machine Learning (1CML-18), pp. 2863-2872, 2018.
Yunpu Ma, Volker Tresp, and Erik A Daxberger. Embedding models for episodic knowledge graphs. Journal of Web Semantics, pp. 100490, 2018.
Dat Quoe Nguyen, Kairit Sirts, Lizhen Qu, and Mark Johnson. Stranse: a novel embedding model of entities and relationships in knowledge bases. arXiv preprint arXiv: 160vv/600008 08 /400 2016.

---

Published as a conference paper at ICLR 2020
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learn- ing on multi-relational data. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pp. 809-816, 2011.
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. Review of Relational Machine Learning for Knowledge Graphs. Proceedings of the IEEE, 104(1):11-33, 2016a.
Maximilian Nickel, Lorenzo Rosasco, Tomaso A Poggio, et al. Holographic embeddings of knowl- edge graphs. 2016b.
Purnamrita Sarkar and Andrew W Moore. Dynamic social network analysis using latent space models. In Advances in Neural Information Processing Systems, pp. 1145-1152, 2006.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Age Smilde, Rasmus Bro, and Paul Geladi. Multi-way analysis: applications the chemical sci- ences. John Wiley & Sons, 2005.
Nathan Srebro and Ruslan R Salakhutdinov. Collaborative filtering in non-uniform world: Learn- ing with the weighted trace norm. In Advances in Neural Information Processing Systems, pp. 2056-2066 2010.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In International Conference on Machine Learning, pp. 2071-2080, 2016.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by trans- lating hyperplanes. In Twenty-Eihhth AAAI conference artificial intelligence, 2014.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv: arXiv: 1412.657, 2014.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec, Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13):457466, 2018.
10

---

Published as a conference paper at ICLR 2020
8 APPENDIX
8.1 UNFOLDING AND THE CP DECOMPOSITION
Let X [0, V, W] that is X,,j, (wi, Ujs wk, tt). Then according Kolda Badei (2009).
unfolding along modes and 4 leads to an order three tensor of decomposition X [U, V. W
Tl. Where is the Khatri-Rao product (Smilde all 2005), which is the column-wise Kronecker product: W - T (W.1 @ T......, W. R @ R).
Note that for fourth mode of size L: (W T) L(K-1)+ wk t1. This justifies the regularizers used in Section G
8.2 TEMPORAL REGULARIZER AND NUCLEAR NORMS Consider the penalty:
1 + + [ + || + alI7i: T:-1l13) QUU, V. W,) 4
Let us define new norm on vectors:
||t||4 = (I[t) + allt1: - +t=1)11) 1/4
|| r4 is norm and lets us rewrite:
R Σ (11u,111 + || [|w, + [14(11)))
Q(U.VWWTT)
Following the proof in Lacroix et all (2018) which only uses homogeneity of the norms, we can show that (U, V, W, T) is variational form of an atomic norm with atoms:
A {u 6 6 [|w]|4, ||l|4, ||l]| and ||<||<4 $ 1}
8.3 NUCLEAR NORMS UNFOLDINGS
We consider the regularizer:
N (U.V (1,,,,,) (1) + || + I10% @ 4111)
Let Duubj (resp. obj, pred/time) the diagonal matrix containing the cubic-roots of the marginal prob- abilities of each subject (resp. obj, pred/time) the dataset. We denote by the Kathri-Ras product between two matrices (the columnwise Kronecker product). Summing over the entire dataset, we obtain the penalty:
Σ (...JEES
Ω N3 UUV,
1 (1)D + | + D (Vo 13))
Dropping the weightings to simplify notations, we state the equivalence between this regularizer and variational form of the nuclear 3-norm of an order 4 tensor:
R
R ΣI II
inf [U Us,
| 1
(1
& Buu 1121
inf [0. U
3
-=1d=1
The proof follows aacroox et all (2018), noting that (l) ut [13 -
|| (3) | | ls.
(4)
Note that
for Dreddtime = Dred Diiee, there would also be equality of the weighted norms. However, in the
application considered, time and predicate are most likely not independent, leading to different weightings of the norms.
11

---

Published as a conference paper at ICLR 2020
8.4
DATASET STATISTICS
Statistics of all the datasets used in this work are gathered in Table [].
ICEWS14 6869
ICEWS05-15
Yago15k
Wikidata
Entities
10094
15403
432715
Predicates
460
502
102
814
Timestamps
365
4017
170
1726
ISI
72826
368962
110441
7224361
Table 5: Dataset statistics
8.5 DETAILED RESULTS
ICEWS14
ICEWS15-05
Yago15k
MRR
H@1
H@3
H@ 10
MRR
H@@ I H@@3
H@ 10
MRR
H@@
H@@
H@ 10
TA
0.48
0.37
0.69
0.47
0.35
0.73
0.32
0.23
0.51
DE-SimplE
0.53
0.42
0.59
0.73
0.51
0.39
0.58
0.75
ComplEx
0.47
0.35
0.53
0.70
0.49
0.37
0.55
0.72
0.35
0.28
0.35
0.52
TComplEx
0.56
0.47
0.61
0.58
0.49
0.64
0.76
0.35
0.27
0.36
0.52
TNTComplEx
0.56
0.46
0.61
0.74
0.60
0.50
0.65
0.78
0.28 0.35
0.35
0.52
ComplEx (x)
0.47 0.35
0.71
0.49
0.37
0.55
0.73
0.36
0.29
0.36
0.54
TComplEx (x10)
0.61
0.53
0.66
0.77
0.66
0.59
0.71
0.80
0.36
0.28
0.38
0.54
INTComplEx (x10)
0.62
0.52 0.66
0.76
0.67
0.59
0.71
0.81
0.37
0.29
0.39
0.54
Table Results for TA Carre--Duran..e an, 2013) and DE-SimplE (Goel et all 2020) are best
numbers reported in the respective papers.
8.6 STANDARD DEVIATIONS
We give the standard deviations for the MRR computed over 5 runs of TNTComplEX on all datasets:
ICEWS14 0.0016
ICEWS15-05
Yago15k 0.00076
Wikidata (T)
Wikidata (NT)
TNTComplEx
0.0011
0.0035
0.0012
8.7
GRID SEARCH
For ICEWS14, ICEWS05-15 and Yago15k, follow the grid-search below
Using Table II to compute the number of parameters and the dataset statistics Table H. we use the following ranks match the number of parameters of DE-SimplE, in dimension 100:
ICEWS14
ICEWS05-15
Yago 5k 100
DE-SimplE
100
100
ComplEx
182
186
196
TComplEx
174
136
194
TTComplEx
156
128
189
12


Reviews:
[{"review_id": "SkeVp-x0FS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The work in this paper is focused on the task of knowledge base completion, dealing specifically with temporal relations, which is quite important in practice, and also not as well studied in literature. Specifically, the authors have 3 main contributions in this paper:\n1. They present an order 4 tensor factorization for dealing with temporal data, which is a nice extension of the work in Lacroix 2018. The authors introduce different forms of regularization to extend to the order 4 tensors. Inspired by previous work, they produce different regularization strategies for order 4 tensor by unfolding the modes to reduce it ot an order 3 formulation. They also describe a regularization term for smoothing the temporal embeddings. \n3. Finally, the authors mine wikidata for temporal relations and contribute a dataset based on wikidata that is much larger than existing datasets for this task.\n\n\nOverall, I think this paper is  interesting as it provides an incremental extension of ComplEx to the temporal case, and the experiments to support the formulation show improvements in MRR. However, the experiments around standard benchmarks as well as the data produced by the authors do not always support the hypothesis that modeling temporal dimension in the proposed formulation is a win for the KB completion task.  For example, the use of auxiliary losses  for enforcing temporal constraints makes the overall performance worse. This is mentioned in a section, but I think it deserves a more thorough explanation. Also, there is no mention about statistical significance of the results, and so it is hard to judge the claim of these being SOTA as made by the authors. For example, on the wikidata dataset produced, the ComplEx model outperforms the proposed models.\n\n\n\nStrengths:\n1. The work in this paper is quite well motivated and the modeling formulation is clear and easy to follow. The authors did a great job in citing relevant work and walking through the model formulation as well as the various regularization terms introduced.\n2. The authors compare their work to the previous SOTA - the ComplEx models for multiple datasets, including their own released datasets. They present a clear set of experiments to demonstrate the effectiveness of their approach both on non-temporal and temporal relations.\n3. There is a dataset being released and also code, which should aid in reproducibility of the results (though I have not tested the code).\n\nAreas to be addressed:\n1. The work seems to assume that the time is discretized by year. However, it is unclear how one would deal with a KB where the temporal relations can change on the order of weeks (example popular movies). For that matter, how would the model be modified to deal with heterogenous time scales in the evolution of the relations in the KB? Can the authors add some clarification as well as explanations for how this would be addressed in this formulation?\n2. While there is a section devoted to different regularization, from Table 3, the impact of choosing the right regularizer seems minimal in terms of MRR. Also, it seems that the results in Table 3 are comparable to the “ranks multiplied by 10” setting in Table 2. What is the reason for this choice? \n3. For Table 4, why is there a performance difference between static and non-static relations? It would help if the authors could provide some more error analyses to dive into this performance difference - is it just data imbalance or inherent difficulty in the task for temporal relations. \n4. Section 6 talks about enforcing another auxiliary loss, however, these results are not part of the table. I would urge the authors to add this to Table 4. Also, the loss in MRR mentioned is it the average loss or does enforcing this auxiliary loss also influence performance on T-MRR as well? If so, might it be that the auxiliary loss is too strong and might need to be penalized? Did the authors try penalizing the auxiliary loss? Finally, the graph in Figure 2 is hard to follow when printed in black and white. What would the plot look like in comparison to a model that does not enforce the auxiliary function for the same example? I would recommend re-working Section 6 to provide some more details about the performance of the models both across the various datasets as well as error analyses of a few examples compared across TNTComplex, TNTComplex + auxiliary loss + Baseline Complex. Having some representative examples would make it easy to understand where these models differ in their performance.\n5. In the results, can the authors include metrics like filtered MRR as well as Hits@10, similar to the one suggested by Bordes 2013? This would make it easier to compare against previous literature results which all seem to be reporting on these metrics.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJeB8K5AYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review:\nThis paper extends the ComplEx model (Trouillon et al., 2016) for completing temporal knowledge bases by augmenting it with timestamp embeddings. Besides, based on the assumption that these timestamp representations evolve slowly over time, the paper introduces this prior as a regularizer. Also, the paper adds a non-temporal component to the model to deal with static facts in knowledge bases. The proposed model has been evaluated using the current benchmark temporal event datasets, showing state-of-the-art performance.\nThis paper could be weakly accepted because the paper introduces new regularization schemes based on the tensor nuclear norm for tensor decomposition over temporal knowledge graphs, which could be a significant algorithmic contribution. Additionally, the submission empirically studies the impact of regularizations for the proposed model, and weight different regularizers according to the joint marginal of timestamps and predicates, which achieves good experimental results.\nFeedback to improve the paper:\n1. For novelty, the paper does not clearly point out that Ma et al. (2018) already augmented the ComplEx model with time embedding for completing temporal knowledge graphs.\n2. The paper does not point out whether the units of the timestamps affects the model and how to adjust the model accordingly. For example, the time granularity of the ICEWS dataset is 24 hours. If we switch the unit of timestamps from hours to days, do the results of the proposed model change? If yes, how to peak the best time unit for a given dataset?\n3. For the Wikidata, the author reports the filtered Mean Reciprocal Rank of the conducted experiments, where the author provides not only the overall score but also the temporal MRR. However, the paper does not provide information about error bars as well as the unfiltered version of the experiment results. Since the results of TComplEx and TNTComplEx are only slightly better than ComplexE, the reviewer doubts whether the proposed model can really beat the ComplEx model when considering the error bars. Also, NT-MRR and T-MRR are not clearly defined.\n4. The submission proposes a new large-scale temporal event dataset, and states that this dataset is more realistic than the current benchmarks. However, the reviewer does not find any argument in the paper to support this statement.\nReferences:\nThéo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In International Conference on Machine Learning, pp. 2071–2080, 2016.\nYunpu Ma, Volker Tresp, and Erik A Daxberger. Embedding models for episodic knowledge graphs. Journal of Web Semantics, pp. 100490, 2018.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJeL9wg4YB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study an important problem, i.e., time-aware link prediction in a knowledge base. Specifically, the authors focus on predicting the missing link in a quadruple, i.e., (subject, predicate, ?, timestamp). In particular, the authors design a new tensor (order 4) factorization based method with proper regularization terms shown in Eqs.(4-6).\n\nThe authors also prepare a dataset which may be helpful for further study on this topic, which is highly appreciated.\n\nEmpirical studies on three public datasets show the effectiveness of the proposed model over the state-of-the-art tensor factorization based methods that are published very recently.\n\n\nSome comments:\n\n1 The technical novelty is a bit limited in compared with those 3-order tensor factorization based methods.\n\n2 For the time-aware link prediction problem, some deep learning based methods may also perform well, especially those capturing sequential signals, e.g., RNN and their variants. The authors are encouraged to include those works in the related work and in the empirical studies.\n\nMinor:\n\nTypo: 'ICEWS05-15'\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a new algorithm based on tensor decompositions for the problem of knowledge base completion. They also introduce new regularisers to augment their method. They also propose an new dataset for temporal KB completion.  

All the reviews agreed that the paper addresses an important problem and presents interesting results. The authors diligently responded to reviewer queries and addressed most of the concerns raised by the reviewers. 

Since all the reviewers are in agreement, I recommend that this paper be accepted. 
Decision: Accept (Poster)