TuckER: Tensor Factorization for Knowledge Graph Completion

HypER can be understood in terms of tensor factorization up to a non-linearity.

“The authors show that convolution is a way of introducing sparsity and parameter tying and that HypER can be understood in terms of tensor factorization up to a non-linearity, thus placing HypER closer to the well established family of factorization models.”

• cites Balažević et al., 2019 sourceSupported

TransE and its variants FTransE and STransE are not fully expressive because of contradictions they impose between different relation types.

“They further prove other models are not fully expressive: DistMult, because it cannot model asymmetric relations; and transitive models such as TransE (Bordes et al., 2013) and its variants FTransE (Feng et al., 2016) and STransE (Nguyen et al., 2016), because of certain contradictions that they impose between different relation types.”

• cites Bordes et al., 2013Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Feng et al., 2016Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites Nguyen et al., 2016 sourceSupported

ComplEx-N3 is the only other linear link prediction model that benefits from multitask learning.

“To our knowledge, ComplEx-N3 (Lacroix et al., 2018) is the only other linear link prediction model that benefits from multitask learning.”

• cites Lacroix et al., 2018 sourcePartly supported

  The Experimental Setup (p. 7) identifies ComplEx-N3, and the Introduction (pp. 1–2) reports performance gains for ComplEx from modeling inverse predicates and, on harder datasets, from N3 regularization. Our copy does not establish that ComplEx-N3 benefits from multitask learning or that it is the only other linear link-prediction model to do so. (LLM, conf=0.78)

  Experimental — accuracy not yet measured

In ComplEx-N3, rank regularization of the embedding matrices is used to encourage a lowrank factorization, thus forcing parameter sharing between relations.

“There, rank regularization of the embedding matrices is used to encourage a lowrank factorization, thus forcing parameter sharing between relations.”

• cites Lacroix et al., 2018 sourcePartly supported

  Section 4 (p. 4) confirms that the paper proposes nuclear 3-norm regularization for tensor-factorization models, including ComplEx. But it does not say that this regularizer forces parameter sharing between relations; Section 2.2 (p. 2) instead describes ComplEx’s parameter sharing as occurring between the subject and object modes. (LLM, conf=0.84)

  Experimental — accuracy not yet measured

TuckER outperforms previous state-of-the-art models across standard link prediction datasets.

“TuckER outperforms previous state-of-the-art models across standard link prediction datasets, acting as a strong baseline for more elaborate models.”

• Also stated in: § 1 Introduction · plain

  “proposing TuckER, a new linear model for link prediction on knowledge graphs, that is simple, expressive and achieves state-of-theart results across all standard datasets”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

The margin by which TuckER outperforms other linear models is notably increased on datasets with a large number of relations.

“This is supported by the fact that the margin by which TuckER outperforms other linear models is notably increased on datasets with a large number of relations.”

Even with fewer parameters than ComplEx and SimplE at d_e=200 and d_r=30 on WN18RR (~9.4 vs ~16.4 million), TuckER consistently obtains better results than any of those models.

“Even with fewer parameters than ComplEx and SimplE at d e = 200 and d r = 30 on WN18RR (∼9.4 vs ∼16.4 million), TuckER consistently obtains better results than any of those models.”

The difference between the MRRs of ComplEx, SimplE and TuckER is approximately constant for embedding sizes 100 and 200.

“We can see that the difference between the MRRs of ComplEx, SimplE and TuckER is approximately constant for embedding sizes 100 and 200.”

Running ComplEx-N3 with equivalent parameter number to TuckER shows comparable performance.

“However, running their model with equivalent parameter number to TuckER shows comparable performance, supporting our belief that the two models both attain the benefits of multi-task learning, although by different means.”

At embedding dimensionalities 20, 50 and 100, TuckER has fewer parameters than ComplEx and SimplE (e.g., ComplEx and SimplE have ~3 million and TuckER has ~2.5 million parameters for embedding dimensionality 100).

“It is important to note that at embedding dimensionalities 20, 50 and 100, TuckER has fewer parameters than Com-plEx and SimplE (e.g.ComplEx and SimplE have ∼3 million and TuckER has ∼2.5 million parameters for embedding dimensionality 100).”

At embedding size 20 (~300k parameters), the performance of TuckER is almost as good as the performance of ComplEx and SimplE at embedding size 200 (~6 million parameters).

“At embedding size 20 (∼300k parameters), the performance of TuckER is almost as good as the performance of ComplEx and SimplE at embedding size 200 (∼6 million parameters), which supports our initial assumption.”

TuckER is fully expressive.

“We show that TuckER is a fully expressive model, derive sufficient bounds on its embedding dimensionalities and demonstrate that several previously introduced linear models can be viewed as special cases of TuckER.”

• Also stated in: § 1 Introduction · boosted

  “We thus show that TuckER is fully expressive, i.e. given any ground truth over the triples, there exists an assignment of values to the entity and relation embeddings that accurately separates the true triples from false ones.”

• Also stated in: § 1 Introduction · plain

  “proving that TuckER is fully expressive and deriving a bound on the embedding dimensionality for full expressiveness”

• Also stated in: § 7 Conclusion · plain

  “Whilst being fully expressive, TuckER's number of parameters grows linearly with respect to the number of entities or relations in the knowledge graph.”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

The SimplE scoring function is equivalent to that of TuckER with core tensor Z ∈ R^{P×Q×R}, P=Q=R=2d_e, where 2d_e elements on two tensor diagonals are set to 1/2 and all other elements are set to 0.

“The SimplE scoring function (see Table 1) is therefore equivalent to that of TuckER (see Equation 1), with core tensor Z ∈ R P ×Q×R , P = Q = R = 2d e , where 2d e elements on two tensor diagonals are set to 1 2 and all other elements are set to 0 (see Figure 2c).”

The scoring function of ComplEx is equivalent to the scoring function of TuckER with core tensor Z ∈ R^{P×Q×R}, P=Q=R=2d_e, where 3d_e elements on different tensor diagonals are set to 1, d_e elements on one tensor diagonal are set to -1 and all other elements are set to 0.

“Similarly to DistMult, we can regard the scoring function of ComplEx (see Table 1) as equivalent to the scoring function of TuckER (see Equation 1), with core tensor Z ∈ R P ×Q×R , P = Q = R = 2d e , where 3d e elements on different tensor diagonals are set to 1, d e elements on one tensor diagonal are set to -1 and all other elements are set to 0 (see Figure 2b).”

RESCAL is prone to overfitting due to its large number of parameters, which increases quadratically in the embedding dimension with the number of relations.

“Although a very expressive and powerful model, RESCAL is prone to overfitting due to its large number of parameters, which increases quadratically in the embedding dimension with the number of relations in a knowledge graph.”

• cites Nickel et al., 2011Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

The core tensor of TuckER can be viewed as containing a shared pool of prototype relation matrices, which are linearly combined according to the parameters in each relation embedding.

“Rather than learning distinct relation-specific matrices, the core tensor of TuckER can be viewed as containing a shared pool of”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

SimplE belongs to the family of bilinear models by concatenating embeddings for head and tail entities for both subject and object and constraining the relation matrix so that it contains the relation embedding vector 1/2 w_r on its d_e-diagonal and the inverse relation embedding vector 1/2 w_r^{-1} on its -d_e-diagonal and 0s elsewhere.

“The authors show that SimplE belongs to the family of bilinear models by concatenating embeddings for head and tail entities for both subject and object into vectors [h es ; t es ] ∈ R 2de and [h eo ; t eo ] ∈ R 2de and constraining the relation matrix W r ∈ R 2de×2de so that it contains the relation embedding vector 1 2 w r on its d e -diagonal and the inverse relation embedding vectorfoot_0 2 w”

• cites Kazemi and Poole (2018)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

TuckER is capable of potentially capturing all information (and noise) in the data.

“The purpose of Theorem 1 is to prove that TuckER is capable of potentially capturing all information (and noise) in the data.”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

DistMult is not fully expressive because it cannot model asymmetric relations.

“They further prove other models are not fully expressive: DistMult, because it cannot model asymmetric relations; and transitive models such as TransE (Bordes et al., 2013) and its variants FTransE (Feng et al., 2016) and STransE (Nguyen et al., 2016), because of certain contradictions that they impose between different relation types.”

• cites Kazemi and Poole (2018)Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

Given any ground truth over a set of entities E and relations R, there exists a TuckER model with entity embeddings of dimensionality d_e = n_e and relation embeddings of dimensionality d_r = n_r that accurately represents that ground truth.

“Theorem 1.Given any ground truth over a set of entities E and relations R, there exists a TuckER model with entity embeddings of dimensionality d e = n e and relation embeddings of dimensionality d r = n r , where n e = |E| is the number of entities and n r = |R| the number of relations, that accurately represents that ground truth.”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

DistMult cannot model asymmetric relations.

“The binary tensor learned by DistMult is symmetric in the subject and object entity mode and thus Dist-Mult cannot model asymmetric relations.”

• cites Yang et al., 2015Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

TuckER's number of parameters increases linearly with respect to entity and relation embedding dimensionality d_e and d_r as the number of entities and relations increases.

“Further, its number of parameters increases linearly with respect to entity and relation embedding dimensionality d e and d r , as the number of entities and relations increases, since the number of parameters of W depends only on the entity and relation embedding dimensionality and not on the number of entities or relations.”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

TuckER does not encode all learned knowledge into the embeddings; some is stored in the core tensor and shared between all entities and relations through multi-task learning.

“By having the core tensor W, unlike simpler models such as DistMult, Com-plEx and SimplE, TuckER does not encode all the learned knowledge into the embeddings; some is stored in the core tensor and shared between all entities and relations through multi-task learning.”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

TuckER benefits from multi-task learning by parameter sharing across relations due to the low rank of the core tensor.

“Due to the low rank of the core tensor, TuckER benefits from multi-task learning by parameter sharing across relations.”

• AssumptionThe authors state this as an assumption: Subject and object entity embedding matrices are equivalent, i.e. no distinction is made between the embeddings of an entity depending on whether it appears as a subject or as an object.

The scoring function of ComplEx is equivalent to a hard regularization of the core tensor of TuckER in the real domain.

“This shows that the scoring function of ComplEx, which computes a bilinear product with complex entity and relation embeddings and disregards the imaginary part of the obtained result, is equivalent to a hard regularization of the core tensor of TuckER in the real domain.”

The results demonstrate the expressive power of linear models.

“demonstrating the expressive power of linear models”

TuckER exploits knowledge sharing between relations through the core tensor, i.e. multi-task learning.

“We believe this is because TuckER exploits knowledge sharing between relations through the core tensor, i.e. multi-task learning.”

TuckER allows relations to be asymmetric.

“while still keeping the desirable property of allowing relations to be asymmetric”

The full rank matrix approach for relations has quadratic growth of parameter number with the number of relations.

“However, the drawback of the latter approach is quadratic growth of parameter number with the number of relations”

ComplEx-N3's published results are not included in Tables 3 and 4 because they use d_e=d_r=2000 and a far larger parameter number (18x more than TuckER on WN18RR; 5.5x on FB15k-237), making their results incomparable to those typically reported.

“We do not include their published results in Tables 3 and 4, since they use the highly non-standard d e = d r = 2000 and thus a far larger parameter number (18x more parameters than TuckER on WN18RR; 5.5x on FB15k-237), making their results incomparable to those typically reported, including our own.”

TuckER's number of parameters grows linearly with respect to the number of entities or relations in the knowledge graph.

“Whilst being fully expressive, TuckER's number of parameters grows linearly with respect to the number of entities or relations in the knowledge graph.”

TuckER and ComplEx-N3 both attain the benefits of multi-task learning, although by different means.

“supporting our belief that the two models both attain the benefits of multi-task learning, although by different means.”

Previous linear state-of-the-art models, RESCAL, DistMult, ComplEx and SimplE, can be interpreted as special cases of TuckER.

“We further show that previous linear state-of-the-art models, RESCAL, DistMult, ComplEx and Sim-plE, can be interpreted as special cases of our model.”