Projected Canonical Decomposition for Knowledge Base Completion
Authors: Timothée Lacroix
Guillaume Obozinski
Joan Bruna
Nicolas Usunier
Venue:  (2020)
Keywords: knowledge base completion
adagrad

Abstract: The leading approaches to tensor completion and link prediction are based on the canonical polyadic (CP) decomposition of tensors. While these approaches were originally motivated by low rank approximations, the best performances are usually obtained for ranks as high as permitted by computation constraints. For large scale factorization problems where the factor dimensions have to be kept small, the performances of these approaches tend to drop drastically. The other main tensor factorization model, Tucker decomposition, is more flexible than CP for fixed factor dimensions, so we expect Tucker-based approaches to yield better performance under strong constraints on the number of parameters. However, as we show in this paper through experiments on standard benchmarks of link prediction in knowledge bases, ComplEx, a variant of CP, achieves similar performances to recent approaches based on Tucker decomposition on all operating points in terms of number of parameters. In a control experiment, we show that one problem in the practical application of Tucker decomposition to large-scale tensor completion comes from the adaptive optimization algorithms based on diagonal rescaling, such as Adagrad. We present a new algorithm for a constrained version of Tucker which implicitly applies Adagrad to a CP-based model with an additional projection of the embeddings onto a fixed lower dimensional subspace. The resulting Tucker-style extension of ComplEx obtains similar best performances as ComplEx, with substantial gains on some datasets under constraints on the number of parameters.

Under review as a conference paper at ICLR 2020
PROJECTED CANONICAL DECOMPOSITION FOR KNOWLEDGE BASE COMPLETION
Anonymous authors Paper under double-blind review
ABSTRACT
The leading approaches to tensor completion and link prediction are based on the canonical polyadic (CP) decomposition of tensors. While these approaches were originally motivated by low rank approximations, the best performances are usu- ally obtained for ranks as high as permitted by computation constraints. For large scale factorization problems where the factor dimensions have to be kept small, the performances of these approaches tend to drop drastically. The other main tensor factorization model, Tucker decomposition, is more flexible than CP for fixed factor dimensions, so we expect tucker-based approaches to yield better per- formance under strong constraints the number of parameters. However, we show in this paper through experiments on standard benchmarks of link prediction in knowledge bases, ComplEx, (Tromillon all 2016), variant of CP, achieves similar performances to recent approaches based on Tucker decomposition on all operating points in terms of number of parameters. In a control experiment, we show that one problem in the practical application of Tucker decomposition to large-scale tensor completion comes from the adaptive optimization algorithms based on diagonal rescaling, such as Adagrad. We present new algorithm for a constrained version of Tucker which implicitly applies Adagrad to a CP-based model with an additional projection of the embeddings onto fixed lower dimen- sional subspace. The resulting Tucker-style extension of ComplEx obtains similar best performances ComplEx, with substantial gains some datasets under constraints on the number of parameters.
INTRODUCTION
The problems of representation learning and link prediction in multi-relational data can formu- lated as binary tensor completion problem, where the tensor is obtained by stacking the adjacency matrices of every relations between entities. This tensor can then be intrepreted as a "knowledge base". and contains triples (subject, predicate, object) representing facts about the world. Link pre- diction in knowledge bases aims at automatically discovering missing facts (Bordes et all, 2011 Nickel et all 201; Bordes et all 20L3; Nickeletall, 2016a; Nguyen. 2017).
State of the art methods use the canonical polyadic (CP) decomposition of tensors (Hitcheock), 1927) or variants of it (Troullon all 2016 Kazemi & Poold, 2018 Lacroix al 2018). While initially motivated by low-rank assumptions on the underlying ground-truth tensor, the best performances are obtained by setting the rank high as permitted by computational constraints, using tensor norms for regularization (Lacroix et all, 2018). However, for large scale data where computational or memory constraints require ranks to be low (Lerer 2019), performances drop drastically.
Tucker decomposition is another multilinear model which allows richer interactions between entities and predicate vectors. A special case of Tucker decomposition is RESCAL (Nickel all Nt 201T), in which the relations are represented by matrices and entities factors are shared for subjects and ob- jects. However, an evaluation of this model Nickel all (20))6)) shows that RESCAL lags behind other methods several benchmarks of interest. Recent work have obtained more competitive re- sults with similar models (Balazevic all 20199: Wang et all 2019)) using different regularizers or deep learning heuristics such as dropout and label smoothing. Despite these recent efforts, learning Tucker decompositions remains mostly unresolved. |Wang et all (201%) does not achieve state of the art results standard benchmarks, and we show (see Figure 8 that the performances reported by

---

Under review as a conference paper at ICLR 2020
Balazević et all (20199)) are actually matched by ComplEx (Tromllon all 2016 aarrox all 2018) optimized with Adam, which has less hyperparameters.
In this work, overcome some of the difficulties associated with learning Tucker model for knowledge base completion. Balazevie el all (20195) use deep-lcarning mechanisms such as batch normalization (lotte & Szegedy, 2015), dropout (Srivastaya all, 2014) learning-rate annealing to address both regularization and optimization issues. Our approach is different: We factorize the core tensor of the Tucker decomposition with CP to obtain formulation which is closer to CP and better understand what difficulties appear. This yields a simple approach, which has a single regularization hyperparameter to tune for a fixed model specification.
The main novelty of our approach is more careful application of adaptive gradient techniques. State-of-the- methods for tensor completion use optimization algorithms with adaptive diagonal rescaling such as Adagrad (Duchi et all 20MI or Adam (Kingma & Ba, 2014). Through control experiments in which our model is equivalent to CP up fixed rotation of the embeddings, we show that one of the difficulties in training Tucker-style decompositions can be attributed to the lack of invariance to rotation of the diagonal rescaling. Focusing on Adagrad, we propose different update rule that is equivalent to implicitely applying Adagrad to CP model with a projection of the embedding to a lower dimensional subspace.
Combining the Tucker formulation and the implicit Adagrad update, we obtain performances that match state-of-the-arr methods on the standard benchmarks and achieve significanly better results for small embedding sizes several datasets. Compared to the best current algorithm for Tucker decomposition of Balazevic et all (2019)), our approach has less hyperparameters, and we effec- tively report better performances than the implementation of ComplEx of Lacroix et (2018) in the regime of small embedding dimension.
We discuss the related work in the next section. In Section B. we present variant of the Tucker decomposition which allows to interpolate between Tucker and CP. The extreme case of this vari- ant, which is equivalent to CP up highlight the deficiency of the diagonal rescaling of Adagrad for Tucker-style decompositions in experiments reported in Section g We present the modified version of Adagrad in Section B and present experimental results on standard benchmarks of knowledge base completion in Section M
fixed rotation of the embedding, serves control model to
LINK PREDICTION IN KNOWLEDGE BASES
Notation Tensors and matrices are denoted by uppercase letters. For matrix U, u, is the vector corresponding to the i-th row of U. The tensor product is written @ and the Hadamard product (i.c., elementwise product) is written
2.1 LEARNING SETUP
knowledge base consists of set S of triples (subject, predicate, object) that represent (true) known facts. The goal of link prediction is to recover facts that are true but not in the database. The data is represented as a tensor X E {0, 1 for N the number of entities and T. the number of predicates. Given a training set of triples, the goal is to provide a ranking of entities for queries of the type (subject, predicate, ?) and (?, predicate, object). Following Lacroix at (20T8), we use the cross-entropy as a surrogate of the ranking loss. As proposed by Lacroix el al (2018) and Kazemi Poole (2018, we include reciprocal predicates: for each predicate P in the original dataset, and given an item o, each query of the form (?, P. o) is reformulated as a query (o, p-1 ?), where o is now the subject of P-I. This doubles the effective number of predicates but reduces the problem to queries of the type (subject, predicate, ?) only.
For given triple (i,j, k)) E S. the training loss function for tensor X is then
(x)x(() -Nij,k log
exp( exp(Xx...))) k
Σ
2

---

Under review as a conference paper at ICLR 2020
For tensor decomposition model (0) parameterized by 8, the parameters 1 are found by minimiz- ing the regularized empirical risk with regularizer A:
i argmin (()) argmin
Σ
RAsiA (X()) +O))).
(2)
S
8
0
(A..A)ES
This work studies specific models for (0), inspired by CP and Tucker decomposition. We discuss the related work on tensor decompositions and link prediction in knowledge bases below.
2.2
RELATED WORK
2.2.1
CANONICAL. DECOMPOSITION AND ITS VARIANTS
The canonical polyadic (CP) decomposition of a tensor X is defined entrywise by
d
ji X.... = U,, wy) = Σ
Uer Ur Wkr-
Wyr
The smallest value of for which this decomposition exists is the rank of X. Each element X.,.k ls is thus represented as a multi-linent product of the embeddings in Fd associated respectively to the ith subject, the jth predictate and the kth object.
CP currently achieves near state-ol of the-art art performances on standard benchmarks of knowledge base completion (Kazemi & Poole, 2018: Lacroix et all 2018). Nonetheless, the best reported results are with the ComplEx model (Irouillon all 2016), which learns complex valued embeddings and sets the embeddings of the objects to be the complex conjugate of the embeddings of subjects, i.e., we = ui. Prior to ComplEx, Dismult was proposed (Yang et al3. 201E) as a variant of CP with wgg ug. While this model obtained good performances (Kadlec et all 20T.)), it can only model symmetric relations and does not perform as well as ComplEx. CP-based models are optimized with vanilla Adam or Adagrad and a single regularization parameter (Tromllon et all, 2016: Kadlec et all
2017: Lacroix et all, 2018) and do not require additional heuristics for training.
2.2.2 TUCKER DECOMPOSITION AND ITS VARIANTS
Given a tensor X of size LxN, the Tucker decomposition X is defined entrywise by
di
de
ds
Vi,j,k; Nij.k = (us 3 & Wk. C) =
Crisass Uir, Ujra Wkrs-
11=1r3=1r3=
The triple (di, d2, da) are the rank parameters of the decomposition. We also use multilinear product notation X [C; V, W]. where U, V, W are the matrices whose rows are respectively Uj Uke wi and C' the three dimensional d₃ x d2 x dy core tensor. Note that the CP decomposition is Tucker decomposition in which d1 = d2 = d3 = and C is the identity, which we write tensor, Tucker decomposition is thus more flexible than CP for
[U, V, WJ. With non-trivial fixed embedding size. In knowledge base applications, we typically have d < I. < N, so the vast majority of the model parameters are in the embedding matrices of the entities and W. When constraints on the number of model parameters arise (e.g., memory constraints), Tucker models appear as natural candidates increase the expressivity of the decomposition compared to CP with limited impact on the total number of parameters.
While many variants of the Tucker decomposition have been proposed in the literature on tensor factorization (see e.g., Kolda & Badert 2009), the first approach based on Tucker for link prediction in knowledge bases is RESCAL (Nickel et all, 20LI). RESCAL uses a special form of Tucker decomposition in which the object and subject embeddings are shared, i.e., U W. and it does not compress the relation matrices. In the multilinear product notation above, a RESCAL model is thus written as X IC]. Despite some success on few smaller datasets, RESCAL performances drop on larger datasets (Nickel et all 20166). This decrease in performances has been attributed either improper regularization (Nickel all (XLT optimization issues (Xue et al. 2018). Baakzeyie et all (2019) revisits Tucker decomposition in the context of large-scale knowledge bases and resolves some of the optimization and regularization issues using learning rate
3

---

Under review as a conference paper at ICLR 2020
annealing, aatch-normalization and dropout. It comes at the price of more hyperparameters to tune for each dataset (label smoothing, three different dropouts and a learning rate decay), and as we discuss in our experiments, the results they report not better than ComplEx for the same number of parameters.
Two methods
previously proposed interpolate between the expressivity of RESCAL and CP. Xue et all (2018) expands the HolE model (Nickel et all (0(6G) (and thus the ComplEx model (Hayashı & Shimbo, 2)) based on cross-correlation of embeddings to close the gap in expressivity with the Tucker decomposition for a fixed embedding size. lenatton et all (2012) express the relation matrices in RESCAL low-rank combination of family of matrices. We describe the link between these approaches and ours in Appendix D None of these approach however studied the effect of their formulation on optimization, and reported results inferior to ours.
2.2.3 OTHER APPROACIIES
(Graph) neural networks for link prediction Several methods have introduced models that go beyond the form of Tucker and canonical decompositions. ConvE (Dettmers et al, M uses convolution on 2D tiling of the subject and relation embeddings as input 2-layer neural net that produces new embedding for the pair, then compares to the object embedding. Graph neural networks (Scarselli atll 200% Niepert et al, 2016 ell 2016; Bruna all 201 have recently gained popularity and have been applied to link prediction in knowledge bases by Schlichtkrul all (2018). This model uses a graph convolutional architecture to generate a variant of CP.
Poincaré embeddings Poincaré embeddings have been proposed an alternative to usual tensor decomposition approaches to learn smaller embeddings when the relations are hierarchical (Nickel Kiela. 2017). The method has recently been extended to link prediction in relational data with very good performance trade-offs for small dimensional embeddings on the benchmark using WordNet (Balazević all, (2)14)), which contains relationships such as hypemyys and hyponyms which purely hicrarchical. However, such good results do not extend to other benchmarks.
3 INTERPOLATING BETWEEN CP AND TUCKER
In order to better understand the underlying difficulties in learning (variants of) Tucker decompo- sitions compared to CP, our analysis starts from a Tucker model in which the core tensor is itself decomposed with CP. Given N x L x N tensor, a fixed d and assuming (d, d, d) Tucker de- composition simplify notation, a Tucker model where the core tensor itself decomposed with rank- D CP can be written as (details are given in Appendix 933):
Xijk = (u, & Uj & WK, C* (Piu,, P2tlj, PaWx) or equivalently X [UP] VPJ. 1
where P1, P2, P3 are all D x d matrices. Since most knowledge bases have much fewer predicates than entities (L & N), the dimension the predictate factors has little impact on the overall number of model parameters. So in the remainder of the paper, we always consider P2 I. Learning matrices U, V, PrP PI of this decomposition simultancously leads to the following model, which call Tucker (CPT):
(CPT) Xijk = (Plus, us Uy Pawx), wy E Rdd ey E
The CPT model is similar to CP model except that the embedding matrices U and W have an additional low-rank constraint (d instead of D). We say that the model interpolates between CP and Tucker because for D d it is equivalent to CP (as long P1 and P3 are full rank), whereas for D d2 we recover full Tucker model because the matrices Pi and P3 can be chosen such that (Pius, Py Pswa) u,Mat(u,)uf where Mat is the operator that maps a dl vector to d d matrix (see Appendix )
CPT is similar to CANDELINC (Crrroll all 198)), except that in CANDELINC the factors U, V and W are fixed and used to compress the data in order to efficiently learn the P. Closer to CPT, Bro & Andersson (199%) first leam a Tucker3 decomposition of X before applying CANDELINC using the learned factors. These methods are only applicable to least-square estimation, and for tensors of smaller scale than knowledge bases.
4

---

Under review as a conference paper at ICLR 2020
0.350
MRR (higher is better)
0.325
Value (log scale)
10-9
0.300
CP (Adagrad)
CPT (Adagrad)
0.275
PCP (Adagrad)
PCP Adagrad
0.250
PCP (Ada"))
10
10a
10a
200
400
Parameters entities
Sorted Adagrad coefficients
(a) Performances on FB 19155K22 237 in the control exper- iments for D = d, ie., when PCP is reparameteriza- tion of CP. We observe that PCP and CPT with vanilla Adagrad, which
(b) Adagrad coefficients for subject/object embedding matrices in the control experiments (D = d) for CP and PCP, averaged by columns (i.e.. embedding di- mension) and sorted by values. Adagrad coefficients decay exponentially for CP, but the values are similar across most dimensions in PCP: the fixed unitary trans- form in PCP removes the benefit of Adagrad.
variants of Tucker, underperform compared to CP. As expected in this case D) = d, our modification of the Adagrad update leads to the same performances for PCP as for CP.
Figure Results the control experiment of Section
Fixed projection matrices: The Projected Canonical Polyadic (PCP) Decomposition In order to clarify the difficulty that arise when learning CPT model compared to a CP model, we study a simpler model in which the matrices P1 and P3 are not learned but rather fixed during training and taken as random matrices with orthonormal columns. We call the resulting model the Projected Canonical Polyadic (PCP) decomposition, since P1, P3 project the embeddings dimension into higher dimension D:
(PCP) Xijk = (Pru,, Uy: PawE), u, we Rd RR,,y ERD, fixed Pi, E Dxd
When the matrices P; are then fixed unitary transformations. The PCP (or CPT) model in this case D d is then equivalent to CP model, up to a fixed invertible transformation of the embeddings. The capacity the model grows beyond that of CP as D increases up to d².
4 MOTIVATION: OPTIMIZATION ISSUES WITH CPT AND PCP
As discussed in the related works, previous results suggest that Tucker models are more difficult to train than CP models. The goal of this section is isolate issue faced with CPT/PCP models when trained with vanilla adaptive gradient methods such as Adagrad or Adam.
4.1 CONTROL EXPERIMENT: UNITARY P1 AND P3 IN PCP
When D d in PCP, the model becomes equivalent to CP. Indeed, the matrices Pi and P3 are and [(UP) PT V. (WPs)PJ] [U, V, W]. There no practical interest in considering this degenerate case of PCP, we only use it in the following toy experiment exhibit one of the difficulties encountered when training PCP.
unitary (P P3P3
We perform simple control experiment in which we take one of the standard benchmarks of link prediction in knowledge bases, called FB15K-237, and train a CP model for different values of the rank D and PCP model with D d with vanilla Adagrad. The full experimental protocol, including hyperparameter tuning, similar to our main experiments and described Section [2.2 Figure LE plots the performances in terms of the standard metric mean reciprocal rank (higher is better) as a function of D of CP (blue curve) and PCP (red curve, called PCP (Adagrad)).
We observe that CP obtains significantly better performances than CPT for larger embedding dimen- sion D. Since in this toy experiment CP and PCP can represent exactly the same tensors and have equivalent regularizations. the only difference between the algorithms that explain the difference in performances is how the optimization is carried out, namely the diagonal rescaling performed by Adagrad: Adagrad adapts the learning rate per-parameter basis, depending previous and
5

---

Under review as a conference paper at ICLR 2020
current gradients, and is therefore not invariant by the addition of the matrices P1 and Pa even if these are unitary (we provide the formal justification in the next section). This is shown experimen- tally in Figure IRR where (i.e., adagrad coefficients of subject/object embedding matrices averaged by column). The addition of the random Pi and P2 flattens the Adagrad weights, which in turn removes all the benefit of the adaptive rescaling of the algorithm.
plot the average Adagrad coefficients for each embedding dimensions
For reference, we also tried directly learn all parameters including Pi and Ps (i.e., learn a CPT model) with vanilla Adagrad. The performances obtained are also lower than those of CP, as shown in Figure (orange curve).
A ROTATION INVARIANT ADAGRAD: ADA imp
In this section, we study the optimization problem in more details, and more precisely the effect of the diagonal rescaling performed by Adagrad. As a remainder, given sequence of stochastic gradients (0) of L and denoting ((t) = el و the (practical) AdaGrad update is:
0(++1) = g(0) - (g (
(+tt) pp
or equivalently g((+1) = g(t) Diag (
where Dia is the diagonal matrix obtained by extracting the diagonal elements of G.
5.1 TWO EQUIVALENT PARAMETRIZATION OF PCP
The following decomposition is equivalent to PCP, but its embeddings are expressed in R.::
FPCP Xi.j.k (P) PI ue, M/z PaP3 wa): with ug By wh E R.P, fixed P1, Pa E Dxd
Note that with U1 = P. U; and wa P3 Wk, go from PCP to PCP. The practical differences between PCP and PCP full are that PCP learn embeddings in the high-dimensional space, main- taining the low-rank structure of the overall entity embeddings through the orthogonal projections P.P and P.P.. The practical interest of PCP is not in terms modeling but rather from the optimization perspective with Adagrad because it has structure that is closer that of CP.
Indeed, for d = D, Pi and P3 disappear in PCP so that optimizing a PCP model with Adagrad is equivalent to optimizing CP model with Adagrad. This property suggests alternative the vanilla PCP + Adagrad algorithm, which we call implicit Adagrad:
Implicit Adagrad: imp The approach we propose is to effectively optimize PCP with Ada- grad. However, when d < D, which is the interesting case for PCP, we notice that we do not need maintain embeddings in RR." Our approach, called Amp computes the gradients and Adagrad coefficients with respect to ug wi E RR,,, but the full dimension factor matrices U and W are never explicitly stored memory. Rather, we store u, = P. u, and Wi P3 w4 E Rdd, which all that is required for any model computation in PCP since Pi and P3 are fixed. Overall, the effective model parameters are exactly the same as in PCP, and we call this approach PCP +md
An Ada update is described in Algorithm ! While PCP +Adagrad and PCP +Adaimp work with the same number of model parameters, the fundamental difference the computation of Adagrad coefficients. Since Ama effectively applies Adagrad to PCP need maintain the Adagrad coefficients in IRD even when d < D: the overall update is first computed in IR and projected back to Rdd after the application of Adagrad rescaling. In constrat, in vanilla PCP +Adagrad, the gradient is projected to R2d before Adagrad rescaling.
5.2 IMPLICIT OPTIMIZATION OF PCPFULL: ADA 6mp
In this section, we discuss more formally the Ama updates, and how they compare to PCP +Ada- grad. In the following, Ú, W are in R Nxd whereas U, V and W are in NND, Using d < D, Pi, Pa E Dxd and the notation IT, P.P.T and Π P3 PyP..

---

Under review as a conference paper at ICLR 2020
The empirical risk L can be expressed function of three matrices M M and M corre- sponding to factors of a CP decomposition. We focus on the following problems:
(PCP) argmin L(UP, K, (PCP argmin L(UIT .V,TT, U.V.W
U.V.W
We focus on a step at time (t) on vectors ū, and Up. We assume that at this time t, the tensor iterates are the same, that is U = UPP (resp. W WPP so that [ŪP], V, W P [UT V, W In this case, the gradient V va & is the same in both optimization problems, we denote it by 9i
Let G: =ela + Et=
9; (r)
9; The updates for (PCP) are:
ú = ut nDiag(P, G. PT)
(3)
Note that due to the presence of P1 inside the Diag operator, the update (8) is not rotation invariant. Moreover, for random P1. the matrix PJ PTT.(O P1 will be far from diagonal with high probability, making its diagonal meaningless. This is visualized in Figure lIil
Similar updates can be derived for (PCP)un):
a ut "IDiag(II] G. 11)-1/11111 g.
(4)
As a sanity check, clearly, for d = D and II, = I, the update (E) is equivalent to the Adagrad update for the CP model. In the general case d D, in order to avoid storing U RND,, we apply these updates implicitly with Ada by storing w;
(t) P3 uj in Rdd Let us compare the updates:
Adagrad in R
projection to Rd
(ADAGRAD) -++1 17
17
Pi G P1)
P 9
(ADA hmp)
11
1+1
= 3.
X
X Diag (TI, G 1
X projection to Im(I))ER
projection Rd
Adagrad in I
Going back to our control experiment, we note on Figure In that PCP +Ada imp matches the perfor- mances of CP+Adagrad for all D, indicating that we fixed this optimization issue.
5.3 ALTERNATIVES TO ADA imp
Another solution would be to Adagrad projected on the column space of II. but we show in Appendix H.] that even with the diagonal approximation, this is impractical. Note that the version of Adagrad which uses the full matrix (+)) is rotation invariant (see Appendix M. for details), but cannot be used the scale of our problems.
could be argued that the strength of the AdaGrad algorithm in our context mostly comes from its adaptation to the different frequencies of updates of each embedding. In fact, this is of the examples chosen in Duchi et all (201T) to display the advantages of AdaGrad compared to stochastic gradient descent. A version of AdaGrad that would only keep coefficient per embedding (we call this version Adarow) would be invariant to unitary transforms by design and would adapt to the various update frequencies of different embeddings. In fact, this version of AdaGrad is used to save memory in Lerer el all (2019). We test this algorithm in Appendix E.B. The difference in performances shows that this adaptation not sufficient to recover the performances of the finer diagonal AdaGrad in our setting. The claim that the approximations made in Ada are indeed better further backed by the experiments the next section.
5.4 COMPLEXITY
The time complexity of our Ada update for batch of size B is O(D d B) which is similar, up to constants, to the complexity of updates for the AdaGrad algorithm. We do not notice any runtime differences between dimension D (see Section M. The runtime for large enough is dominated by the matrix product (O(D2. B)) required compute the cross-entropy in Equation (l))
algorithm applied in dimensions (d, D) and a CP decomposition of
7

---

Under review as a conference paper at ICLR 2020
Algorithm Step of PComplEx training
Algorithm Ada
ji, k) sample from S
Input: 7) x() (0)) G(t-1), ,
g(t) t P(P P(PTg()) g())
Pis Ij. + gradients in (Pui, Puj, wk)
G: - Ada (1) Iu: Gi, P)
G t G(t-1) + g o g())
Uj Gj + Ad (1), Ug 93. Gj, P)
x(++1) t x(t) nP Diag(G(t))1122
Wk: GR AdaGrad(n, Wk: 9k G1.)
return g((+1), 7(0)
Figure 2: The algorithms used in the training of PComplEX
6 PROJECTED COMPLEX
As the state-of-the-art variant of CP is ComplEx (Irowiloo et all 2016 Lacroix et all 2018), propose the following alternative to PCP base on ComplEx with Ada in practice. Given the ComplEx decomposition X Re((U, V, U], low-rank decomposition of the entity factor U as PŪ leads to the model PComplEx
in the experiments of Section
(PCOMPLEX) X.jk (Pui, U/, Pus)
= (u,, P P. ug), wk E C.. E CD, fixed P E Pxd
PComplEx is similar to ComplEx but with interactions described by full matrices rank D that share basis. We learn this decomposition with Algorithms W and g
7 EXPERIMENTS
In this section, we compare ComplEx optimized with AdaGrad and PComplEx optimized with Ada imp We optimize the regularized empirical risk of Equation (.). Following Lacroix all (2018), we regularize ComplEx with the weighted nuclear-3 norm, which is equivalent to regulariz- ing |4 13 + Mu + || 13 for each training example (i. For PComplEx based models, we regularize Pu 1 + [|uy | by analogy.
We conduct all experiments available the supplementary materials, experiments on ComplEx use the code from (Lacroix atall 201)). We include results from TuckER (Balazević et all, 201H),, DRT and SRT which are the two models considered in Wang et all (2019), ConvE (Dettmers el all 2018), HolEx (Xue et all 2018), LFM (Jenatron all 2012) and MurP (Balazevic all 2019)) without re-implementation on our parts. All the parameters for the experiments in this section are reported in Appendix 1.1
Quadro GP 100 GPU. The code for PComplEx and Ada is
7.1 DATASETS
WN18 (ordes et all 2013) is taken from the Wordnet database which contains words and relations between them. WN18RR (Dettmers all 2018) is filtering of this dataset which removes train/test. leakage. YAGO3-10 10 (Detimers el all 2018) is taken from the eponymous knowledge base. Finally, SVO (Jenatton et all 2012) contains observations of Subject, Verb, Object triples. All statistics for these datasets can be found in Appendix 3. Experiments on the FB15K and FB15K-237 datasets are deferred to Appendix 5.10
7.2 RESULTS
We report the filtered Mean Reciprocal Rank (N 2016)) on Figure EL For SVO, we report the only figure available in previous work which is the filtered hits 5% (lenatton all 2012). These measures are detailed in Appendix I.I. Only the grid-search parameters were given for LFM, so we were not able to obtain a precise number of parameters for the number they report.
8

---

Under review as a conference paper at ICLR 2020
SVO
YAGO3-10
0.82
0.60
0.80
0.50
Hits 5%
0.78
0.40
MRR
0.76
0.30
0.74
0.20
0.72
0.10
10a
10
10a
WN18
WN18RR
1.0
0.50
ComplEx
0.45
0.8-
X
PComplEx
MRR
TuckER
MRR
0.40
MurP
0.35
X
0.6
LFM
0.30
D/SRT
0.4
0.25
10a
10a
10a
10
10a
109
Parameters per entities
Parameters per entities
Figure 3: MRR function of #floats/ entities (see Appendix [. four knowledge bases. We plot the convex envelope of various operating points we tested, varying for several values of For some datasets (WN18, WN18RR), Adam (Kingma & Ba, 2014)) is beneficial, in which case use the implicit adaptation of Adam detailed in Appendix 9
On WN18. SVO and YAGO3-10 we observe sizable performance gains for low embedding sizes up to 0.14 MRR points WN18, 0.05 MRR points on YAGO and 0.03 H@5% points SVO.
The TuckER (Balazević all. 2019)) model performs similarly PComplEx and ComplEx except on FB15K and WN18 where it underperforms (see Appendix 9.10) We expect this discrepancy to come from a less extensive grid-search rather than any intrinsic differences in the models that are both based on the Tucker decomposition. The consistency all operating points of method with ComplEx shows an advantage our method, which enjoys the same learning rate robustness AdaGrad, and does not require choosing learning-rate decay, leading easier experiments with only the regularization strength to tune. The MurP model (Balazevic et all 2019a) provides good performances for low embedding sizes WN18RR, but underperforms FB15K-237 (see Appendix I. All other models fail to match the performances of ComplEx and PComplEx with equivalent number of parameters.
Variance of performances in PComplEx due to random choice of P is similar to the variance of ComplEx. We present experiments the WN18 dataset for different seeds in Appendix 3A.
CONCLUSION
By observing that the tensor of the Tucker decomposition can itself be decomposed, obtain new models that are reminiscent of the canonical decomposition with low-rank factors. We provide experimental evidence that naive application of AdaGrad on this decomposition fails, due to in- dividual coordinates losing their meaning. We propose a new algorithm. Ada which fixes this issue. Our model, when optimized with imp provides better performances than ComplEx in the low-rank regime, and matches its performances in the other regimes.
9

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ivana Balažević, Carl Allen, and Timothy Hospedales. Multi-relational poincar 'e graph embed- dings, arXiv preprint arXiv:1905.0979,, 2019a.
Ivana Balažević, Carl Allen, and Timothy M Hospedales. Tucker: Tensor factorization for knowl- edge graph completion. arXiv preprint arXiv: 1901. 0090009990 2019b.
Antoine Bordes, Jason Weston, Ronan Collobert, and Yoshua Bengio. Learning structured embed- dings of knowledge bases. In Conference on artificial intelligence, 2011.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-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.
Rasmus Bro and Claus A Andersson. Improving the speed of multiway algorithms: Part ii: Com- pression. Chemometrics and intelligent laboratory systems, 42(1-2):105-113,, 1998.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and lo- cally connected networks graphs. In International Conference Learning Representations (ICLR20014, 2014.
J Douglas Carroll, Sandra Pruzansky, and Joseph B Kruskal. Candelinc: A general approach to mul- tidimensional analysis of many-way arrays with linear constraints parameters. Psychomelrika, 45(1):3-24, 1980.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2D knowledge graph embeddings. In Shirty-Second AÅAI Conference on Artificial Intelligence, 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(uu))2121-2153) 2011.
Katsuhiko Hayashi and Masashi Shimbo. On the equivalence of holographic and complex embed- dings for link prediction. arXiv preprint arXiv:1702.05563, 2017.
Frank Hitchcock. The expression of a tensor or polyadic as a sum of products. Studies in Applied Mathematics, 6(1-4):164-189, 1927.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 1rXiv:1502.03167, 2015.
Rodolphe Jenatton, Nicolas L Roux, Antoine Bordes, and Guillaume R Obozinski. A latent factor model for highly multi-relational data. In Advances in Neural Information Processing Systems, pp. 3167-3175, 2012.
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 43000 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.694 22800, 2014.
Tamara G. Kolda and Brett Bader. Tensor decompositions and applications. SIAM review, 51(3): 455-500, 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 (ICML-18), pp. 2863-2872, 2018.
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. Pytorch-biggraph: A large-scale graph embedding system. arXiv preprint arXiv: /903. /2287, 2019.
10

---

Under review as a conference paper at ICLR 2020
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016.
Dat Quoc Nguyen. An overview of embedding models of entities and relationships for knowledge base completion. arXiv preprint arXiv: 1:::: mee.::003.00000 08008, 2017.
Maximilian Nickel, Volker Tresp. and Hans-Peter Kriegel. A three-way model for collective learn- ing 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, al. Holographic embeddings of knowl- edge graphs. 2016b.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representa- tions. In Advances in Neural Information Processing Systems, pp. 6338-6347, 2017.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International Conference Machine Learning, pp. 2014-2023, 2016.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61 2009.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdi- nov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Ma- chine Learning Research, 15:1929-1958, 2014. URL http:// mmlr. wwtppppppp//....aooaappp..
vastava 4a ht.mm..11....
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, pp. 57-66, 2015.
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.
2016.
Yanjie Wang. Samuel Broscheit, and Rainer Gemulla. A relational tucker decomposition for multi- relational link prediction. arXiv preprint wwXf::1922000890 2019.
Yexiang Xue, Yang Yuan, Zhitian Xu, and Ashish Sabharwal. Expanding holographic embeddings for knowledge completion. In Advances in Neural Information Processing Systems, pp. 4496- 4506. 2018.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv: MxXiv:1412.66755 2014.

---

Under review as a conference paper at ICLR 2020
9 APPENDIX
I and where we discuss the Adagrad algorithm, we do so in a general setting, where we study, for fixed P with orthonormal columns, the problem
In subsections
min f (PO).
9.1 PROJECTED ADAGRAD UPDATE
Let D denote Diag(G)!/ for the classical version of Adagrad and G1/² itself for the "full" version of the update. When the parameter 0 constrained to a set θ, the update proposed in Eq.(1) in Duchi etal (20IIT) the one obtained by solving
min 2) D(Ø - 2) with 2 = -(t) nD gg(0
lEB
To enforce the constraint that A P8,
consider the Lagrangian
C(0, 0; A) = (0 2) T D 2) - A (0 P9)
whose stationary points satisfy D 2) = X and P X 0. So this entails PT D(0 (())
nPT g(t) and finally using 0 P0 we obtain an update in 0 as follows
((t-1) = g( - TPP (9
Clearly, PDPT is in general non non-diagonal whether D is diagonal not, and so this approach does not provide computationally efficient update.
If D G1/2, then since PG1/2p" pT (PGPT)4/ the update is the same as the full Adagrad update (5l) that derive in the following section and replacing (PGPT)1/2 by its diagonal approx- imation recovers update (B).
9.2 THE TWO FULL ADAGRAD AD UPDATES AND THE QUALITY OF APPROXIMATIONS OF THE DIAG VERSIONS
If we consider the full versions of the Adagrad updates then (letting again 11 = PPT) its application to 0 + f(P0) and 0 + fIII)) yield respectively
g(t+1) g(t) n P(P (()) P) 1 1/2 (Tg))
and
(5)
g((+1) ((t) IT (II (()) m) -/2 g1
(6)
where M notes the pseudo-inverse of a matrix M. As it turns out, the two updates are equivalent: Indeed, first (I2 = P(PTGP))
because PT P implies that
P(P 12 P(P P(P /2 /2 pT T IIGI1,
and the p.s.d. squareroot is unique. Second, taking the pseudo-inverse of this identity, we have (IGII)t/2 (P(PT /2 PPP
because, if H (PT 1/2 is invertible matrix, then (PHPT)L PH-IPT given that PHPT PH-IPT=PP PPT Finally multiplying both sides of Eq. ( by II shows that
(I P(PT (()) pT
This shows that although Adagrad is not invariant for any invertible P, it is invariant for any P such that PT T. Fq.(5) seems in general simpler than (R), but note that if D = d, then TI is the identity and (K) shows that both full updates are in that case actually equivalent to the full update of Adagrad applied to plain CP.
Finally, the equivalence of the full updates discussed above strongly suggests that if our pro- posed update performs better than the naive application of Adagrad to PCP, it is because PDiag(IIG*)))) -12 1 is a better approximation of (G(9)-1/2 than D while not being much computationally expensive.
12

---

Under review as a conference paper at ICLR 2020
9.3 CP-TUCKER
We have X [C;U,V, W] and C P2, For all i, we have:
d Σ
X1J.==
Oreman Unn Vara Wars
d
Σ
EiP ( PPlrain
Unn Vera Wk.sa
D
)
d
d Σ WWrrsPPalss
Σ Up.r (Pilrss))
E EVsralPalras
(Pi ug P20j. P3ws)
9.4
HOLEX AND LATENT FACTOR MODEL
9.4.1 HOLEX
The HolEx model all 2018) writes Xi,,A Ex= ((c, u.)) uU, w(), where denotes the circular correlation Exploiting the equivalence between HolE and ComplEx (Hayashi & Shimbo 2017),, denoting by FF the discrete Fourier transform (with values in C), we can write for embeddings of size d:
R Σ
R
1
(crr u:) * Ug. wf)
Re
Σ
F(c o F()).
d
Re
d
For all vectors, we write ú, = F(u,) E Cd. We can re-write the circular correlation F(c) * F(u)) as C, where C, E Cdxd is the circulant matrix associated with e, E Rdd. We have
Σ (c, u.) uy wf) wf) Re (Cr 8y ot)
Finally, with C [CI,.... CRl E Rdxd the vertical stacking of all C,,, C2 [Tas..., Ta] and
úb = [10] k: .., ";
R Σ
O() d Re ((C* Citj, wxx)
HolEx with embeddings of size d is close to the CPT with D = Rd, allowing for two different complex matrices act on left and right hand side embeddings.
9.4.2 LATENT FACTOR MODEL.
The latent factor model defines the score for triple (i,j, k) as:
X...A = ((5: + 2), Ry (ox + 2²)), with R2 Σ of
Removing the bias terms and z' and gathering u, and v, into matrices P1 and Ps leads to the model CPT. In the PCP model, we fix P1 and P3 instead of learning them. We do not use a sparsity inducing penalty on a but rather variational form of the nuclear norm on the whole tensor.
3/0 b)s dd-1 a.bee4k)modd ded
13

---

Under review as a conference paper at ICLR 2020
9.5 TUCKER2 WITH CU-TUCKER
Let for all Sr d, M be matrix of zeros except its r- column which is all Let P1 be the vertical concatenation of all (M and P2 the vertical concatenation of d identity matrix in Rd. Remember that for all wp is element of RR For all 0 S r < d, let w be the restriction of we to its (rd, (r + 1)d] coordinates.
Then P1 and P2 are elements of RR xd and we have for all i,
PPu4 Pauj, wx)
Σ (M Lavy, w
Σ dirr (ug, wit)
by definition of M M())
d
Σ ugr
Σ 12=1
Usrr Wk.rirz
by definition w
n=
u Mat(wx)u
9.6 COMPLETE PCOMPLEX ALGORITIIM
Let U E Nxx the the entity embedding matrix and V E C2Ix matrix. Let P Nxd + R x such that P(U)) PU, Let G and G be the stochastic gradients with respect to U and V at time L.
D. be the predicate embedding
Algorithm 3 PComplEx optimized with Ada
Input: learning rate 7/, (random) matrix with orthogonal columns, e Co, Gy 0 while U, V not converged do
G + P(G
Cy + Cu + G @ G
Cv t Cv + O
U--
/V(CCC+++)
V V- V GỤ (VCCVv
end while
return U
9.7 ADAM IMPLICIT
For WNISRR, we used the ideas presented in this paper, but adapted to the Adam Kingma & BR ROIE) optimization algorithm. Similar to md, first and second moment estimates are ac- cumulated in R and we project back to Rd only for the parameter update. For simplicity, we present here the dense version of the algorithm applied to the entity embeddings U R Nxd. Let P N + D such that P(U)) PU,, Let G, be the stochastic gradient with respect to U time f.
9.8
ADA row
For the same control experiment as in Section E,, we observe the performances Ada which is rotation invariant by design.
14

---

Under review as a conference paper at ICLR 2020
Algorithm 4 Adam applied U
Input: 7), 12, P.E mo. to. 4- 0
while U not converged do
t ++1
G. + P(G,)
my + 81 10-m--1- + (1 B1) (1 Gt
8. + 82 . 111 + (1 82) G. o G2
my m. [1 Bi)
â - 1-00111 82)
U U- - (m// 0v
Or + +c)
end while
return
0.350
0.325
MRR
0.300
0.275
CP Adagrad
CP Ada row
0.250
10a
102
10a
Parameters per entities
Figure 4: r vs AdaGrad on FB15K-237.
9.9 VARIANCE PCOMPLEX
We run grid search and plot the associated convex-hulls on the WN18 dataset optimized with Ady, Note that despite the added randomness of the choice of there not more variance in PComplEx than in ComplEx.
Variance of PComplEx on WN18
0.8
MRR
01.6
0.4
ComplEx
PComplEx
0.2
40
60
80
100
params per entities
9.10
FB 15K5K DATASETS
We use two subsets of the Freebase knowledge base FB15K (orrdes et all 2013) and FB15K- 237 (ooutanova & Chen, 2015). FB15K-237 is harder version of FB FB15K, where some triples have been removed to avoid leakage between the train and test set. There is no difference of performances between PComplEx and ComplEx on these datasets.
15

---

Under review as a conference paper at ICLR 2020
FB15K
FB15K-237
0.8
0.350
X
0.6
0.325
MBR
ComplEx
MRR
X
TuckER
PComplEx
0.300
D/SRT
0.4
TuckER
MurP
HolEx
0.275
ConvE
10
10a
103
10
10a
Params per entities
Params per entities
9.11 EXPERIMENTAL DETAILS
Metries Let rank & / k) the rank of XIJ.K in the sorted list values of Xij..- We report the MRR for most datasets:
MRR(X)=
1
Σ rank(X..r
SS]
(K.jA)EES
For SVO, the task is slightly different as the ranking happens on the predicate mode. The metric reported in Jenatton et all (2012) is 55% defined as:
H05%(X)
Σ
((ran)(X..x:.)) S 227).
S
(KJ.E)ES
The metrics we report are filtered by ignoring other true positives when computing the ranks, as done in Bordes et all (2013).
Number of parameters per entities We count the number of floats in the model, and divide by the number of entities in the dataset. For different methods, the number of parameters are
ComplEx: 2-d (N 2L)
PComplEx: 2-d +2 D. d D
TuckEr: N -d, L d, dz dp
MurP: N (d + 1) + 2- L-d
ConvE: taken from Detimers et al (011))
D/SRT: taken from Wang et all (2019)
HolEx: (N L)
Grid Search
For SVO:
For Complex vary d in [5, 25, 50, 100, 500, 1000, 2000). For PComplFEx, we vary d in 5, 50, 100, 500].
The strength the regularizer, varies in [5e 4, 3,5c 5e vary
3, le dimension D
2,5e 2,
le 1].
Finally, for PComplEx,
the
in
[5, 25, 50, 100, 500, 1000, 2000, 4000, 8000).
For all other datasets, we run 500 epochs
For FB15K and FB15K-233
vary d in [5, 25, 50, 100, 500, 1000, 2000). For YAGO3-10, WN18 and WNISRR, we add ranks 8 and 16 to that list.
The strength of the regularizer, varies in [5e 4, 3, 3, 2.5c 2, 1e 1].
Finally, for PComplEx, vary the dimension D in [5,
25, 25, 50, 100, 500, 1000, 2000).
16

---

Under review as a conference paper at ICLR 2020
For TuckEr, the hyperparameters deseribed in Balazević et all (2019h) for each dataset. We apply a multiplicative factor to the dropout rates and run a grid-search over this parameter.
For WN18RR, we vary de in [12, 15, 18, 20, 40, 100, 200). For FB15K-237, we vary de in [10, 20, 30, 40, 50, 80, 100, 200]. For WN18, de varies in [5, 8, 16, 25, 50, 100]. For FB15K varies in.
For WN18RR, WN18 we search 7 over [0, 0.5, 1]. For FB15K-233 where this lead non increasing performances as a function of number of parameters. we refined this grid to [0, 00,0.1,00 0.2, .... 0.7] for de I 80. For FBI5K, we use grid of [0, 0.2, 0.4,
For MurP, the hyperparameters described in Balazevic all (2019 for each dataset and vary d [10, 12, 15, 18, 20, 40, 100, 200] on WN18RR and [10, 20, 40, 100, 200) for FB15K-237.
Other details Batch-size fixed 1000, the learning-rate is le both for Adagrad and for Adaump we run 100 epochs to ensure convergence. The best model based on validation MRR is selected and we report the corresponding test MRR.
9.12 RUNNING TIMES
We give here the rumning times of each method per epoch, on the WNI8RR dataset for comparable dimensionalitics and run on a P100 GPU. We use the original implementation for MurP (Balazevid all 2019a and TuckEr (Balazevic all 20T95). For ComplEx, the implementation from
Lacroix et (2018).
ComplEx (d 200) 4s/epoch.
PComplEx (d 200, Ada"mp): 5s/epoch.
MurP (d 200): 38s/epoch.
TuckEr (d.- 200, d, 200): 24s/epoch
Note that these running times are implementation dependent. In the figure below, we give the learning-curves MurP, TuckEr, ComplEx and PComplEx for one operating point the WNI8RR dataset. The convergence speed of these methods is given in the figure below at an operating point on WN1SRR where all methods close in final performances.
Convergence on WN18RR
0.50
0.45
MRR
MurP
TuckEr
0.40
ComplEx
PComplES
0.35
100
200
300
400
500
Epoch
17

---

Under review as a conference paper at ICLR 2020
9.13 DATASET STATISTICS
Dataset
N
Train
FB15K
15k
1k
500k
FB15K-237
15k
237
272k
WN18
41k
18
141k
WN18
41k
11
141k
YAGO3-10
123k
37
1M
SVO
30k
4.5k
1M
Table 1: Dataset statistics.
18


Reviews:
[{"review_id": "rkl0nrbb5S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 authors present a new way of decomposing 3-order tensors which uses interpolation\nbetween the Tucker and CP decompositions, called CPT. The main idea is to present the components of the CP model\nwith an additional low-rank structure.\nThe authors also provide a new optimization algorithm called ADA-imp, for learning this decomposition,\nwhich is a variant of Adagrad adapted to their settings. \nThe paper is overall interesting, clearly written and well-motivated. \nThe mathematical derivations are, as far as I could follow, correct and non-trivial.  (I did not read all the details in the Appendix). \nThe authors also show favorable experimental results on two knowledge-base datasets, with improved loss vs. #parameter used tradeoff.\nA few unclear issues and suggestions for improvements are below.\n\nThe authors present the problem as completion of a binary 3-order tensor, i.e. predicting for triplets (subject, predicate, ?) if '?' refers to 0 or 1.\nBut they also write 'we formulate this problem as a multi-class classification problem, where the classes are the entities of the knowledge base'  - so this is not a binary problem? does this mean there is some structure that must be present in the tensor? (e.g. there is exactly one '1' in each column of length N? This should be clarified. \n\nIt would be good to make the description of Algorithms 1 and 2 more precise and detailed. \nFor example, the operation/algorithm AdaGrad(\\eta;w_k; g_k;G_k) is not defined. AdaGrad is described in the Appendix but it is hard to match it to get the precise operation used in Algorithm 1. \nAlgorithm 1 shows one step of PComplEx, and it would be good to add the entire PComplEx algorithm, with input,output&parameters. \n\nThe authors present their method in the context of knowledge base completion, thus for tensors of order 3, but it is not clear if any of the components they proposed indeed specialized for this problem, or is it a contribution to general tensor decomposition. Some remarks regarding the (in?)applicability of the method more generally would be helpful. \n\nFigure 3 describing the experimental results should be explained better. There are few methods shown only in some of the graphs and only for some parameter values - why?\nThe complexity measure 'parameters-per-entity' should be clearly defined (I didn't find it in the text). Similarly, the performance measures 'mean reciprocal rank' and 'hits at 5%' \nshould be defined in terms of the tensor. \nThe authors should also add running times of the different experiments and methods. \n\n\nMinor:\n--------\nIn the main paper, the authors define an (N,L,N) tensor, but in the appendix Section 9.9 they list N and P. Does P refer to L here? \n\nThe authors mention a few times usage of 'deep-learning techniques' - but I believe that in at least some of the contexts, they refer to optimization methods which are typically used in deep learning, and  are applied here to train other models presented in the text, and not to the usage of actual deep learning architectures - this is confusing and should be clarified. \n\nPage 7, top: what are the matrices M^(1), M^(2), M^(3)? they seem to be different for different decompositions  \n\n", "extra_scores": {"experience_assessment": "I have read many 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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJeYwE_VqB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "* Summary:\nThe paper introduces a novel tensor decomposition that is reminiscent of canonical decomposition (CP) with low-rank factors, based on the observation that the core tensor in Tucker decomposition can be decomposed, resulting in a model interpolating between CP and Tucker. The authors argue that a straight application of AdaGrad on this decomposition is inadequate, and propose Ada^{imp} algorithm that enforces rotation invariance of the gradient update. The new decomposition is applied to ComplEx model (called PComplEx) that demonstrates better performance than the baseline.\n\n* Comments:\nAlthough the approach is well motivated, the paper has many ambiguities that need to better clarification.\n1. Tucker decomposition results in lower dimension factors, \"d\" in the paper. So the resulting core tensor is of size (d \\times d \\times d). However, this core tensor is further decomposed with a rank-D CP as shown in Section 3, where D >= d. Basically, first the original tensor is factored into lower rank d, and the core tensor is then expanded into rank D >= d. The reader did not understand what is the justification for this approach? Please provide further explanation on this part.\n2. The confusion of P_2 and P_3 terms in the paper. At the beginning of Section 3, P_2 is assumed to be identity through out the paper. But P_2 is mentioned to have specific attributes in other parts of the paper, such as in the second paragraph from the bottom of page 4, the first paragraph and first equation on page 5. And P_2 does not appear in AdaGrad algorithm.\n3. The experiment is lacking. First, the paper does not explain the meaning of evaluation metrics. Second, the authors do not provide an insight, why PComplEx is better than the ComplEx baseline on SVO dataset, but performs similarly on other datasets. Which factors lead to such improvement?\n4. The comparison to other state-of-the-arts is inadequate, each compared method only has one or few configurations in terms of number of parameters.\n\nOverall the proposed decomposition method might have significant contribution to research progress in this field, but the paper fails to convince the reader of its significance. I feel the paper should be overhauled.", "extra_scores": {"experience_assessment": "I have read many 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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gTZuqaKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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, a tensor decomposition method is studied for link prediction problems. The model is based on Tucker decomposition but the core tensor is decomposed as CP decomposition so that it can be seen as an interpolation between Tucker and CP. The performance is evaluated with several NLP data sets (e.g., subject-verb-object triplets). \n\nAlthough the entire idea is interesting, the current form of the paper is not sufficient for acceptance. The main reasons are (A) the proposed model is not completely novel and (B) the empirical results are not significant. \n\n(A) The idea of combining CP and Tucker is not new. For example, Tomioka et al. (2010; Section 3.4) considered the Tucker-CP patterns (CP decomposition of the Tucker core). Although they used the Tucker-CP model to improve the interpretability rather than link prediction, the paper needs to make some attribution to the prior work. \n\n(B) By looking Figure 3, the proposed method, PComplEx, is not significantly better than the existing methods such as ComplEx. Except SVO data, PComplEx and ComplEx share almost the same performance curve. Also, other existing methods such as TuckER and MurP are evaluated only in a few points while (P)ComplEx is evaluated in many points. I feel this is unfair.\n\nTomioka, R., Hayashi, K., & Kashima, H. (2010). Estimation of low-rank tensors via convex optimization. arXiv preprint arXiv:1010.0789.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a tensor decomposition method that interpolates between Tucker and CP decompositions. The authors also propose an optimization algorithms (AdaImp) and argue that it has superior performance against AdaGrad in this tesnor decomposition task. The approach is evaluated on some NLP tasks.
The reviewers raised some concerns related to clarity, novelty, and strength of experiments. As part of addressing reviewers concerns, the authors reported their own results on MurP and Tucker (instead of quoting results from reference papers). While the reviewers greatly appreciated these experiments as well as authors' response to their questions and feedback, the concerns largely remained unresolved. In particular, R2 found the gain achieved by AdaImp not significantly large compared to Adagrad. In addition, R2 found very limited evaluation on how AdaImp outperforms Adagrad (thus little evidence to support that claim). Finally, AdaImp lacks any theoretical analysis (unlike Adagrad).
Decision: Reject