Source-linked AI summary
Canonical Tensor Decomposition for Knowledge Base Completion
Timothée Lacroix, Nicolas Usunier, Guillaume Obozinski
TL;DR
Knowledge base completion can be viewed as binary third-order tensor completion, yet standard CP implementations lag behind competing models. The paper evaluates optimization, tensor nuclear p-norm regularization, and reciprocal-predicate reformulation, finding that inverse predicates raise CP to state-of-the-art performance and improve ComplEx further.
Problem
CP performs poorly against specialized knowledge-base completion methods, motivating a study of which optimization, regularization, and formulation choices determine its performance.
Method
The paper re-evaluates CP with broader optimization searches and multiclass log-loss, tests tensor nuclear p-norm regularizers, and models predicates together with explicitly constructed inverses.
Results
0.86 mean reciprocal rank is reached by both CP and ComplEx on FB15K with inverse predicates, compared with 0.40 for vanilla CP and 0.80 for vanilla ComplEx.
Takeaways & Limitations
CP performs nearly as well as competing models when each model is evaluated in its optimal configuration, while reciprocal predicates are the key formulation effect identified in the study.
Takeaways & Limitations
The paper provides definite evidence that correctly formulated CP performs extremely well but lacks a strong theoretical justification for the large performance differences.
Abstract
from arXiv · showhide
The problem of Knowledge Base Completion can be framed as a 3rd-order binary tensor completion problem. In this light, the Canonical Tensor Decomposition (CP) (Hitchcock, 1927) seems like a natural solution; however, current implementations of CP on standard Knowledge Base Completion benchmarks are lagging behind their competitors. In this work, we attempt to understand the limits of CP for knowledge base completion. First, we motivate and test a novel regularizer, based on tensor nuclear $p$-norms. Then, we present a reformulation of the problem that makes it invariant to arbitrary choices in the inclusion of predicates or their reciprocals in the dataset. These two methods combined allow us to beat the current state of the art on several datasets with a CP decomposition, and obtain even better results using the more advanced ComplEx model.
1. Introduction
The paper studies why CP performs poorly for knowledge base completion and evaluates optimization, regularization, and reciprocal-predicate reformulations. Modeling inverse predicates substantially improves both CP and ComplEx, bringing CP to state-of-the-art performance on the reported benchmarks.
- Knowledge base completion infers likely unknown facts from subject–predicate–object triples and serves as both a tensor-factorization application and a relational-representation benchmark.
- CP is known to perform poorly against specialized methods, despite DistMult—a constrained CP model—achieving state-of-the-art results.DistMult shares subject and object factors, producing a symmetric tensor even though many benchmark predicates are non-symmetric.
- The study evaluates broader optimization searches, tensor nuclear p-norm regularization, and a formulation that models predicates separately from their inverses.The reciprocal formulation creates inverse predicates and reverses subject and object positions for training and query answering.
- Systematic parameter searches improve ComplEx beyond prior reports, while inverse predicates produce state-of-the-art CP results matching ComplEx across the evaluated datasets.The experiments compare CP and ComplEx on five common link-prediction benchmarks.
- 0.86 MRR is achieved by both CP and ComplEx on FB15K with inverse predicates, versus 0.40 for vanilla CP and 0.80 for vanilla ComplEx.
- The nuclear 3-norm regularizer does not dramatically help CP, although it yields small but significant gains for inverse-predicate CP and ComplEx on more difficult datasets.
2. Tensor Factorization of Knowledge Bases
The paper represents relational knowledge bases as third-order binary tensors and studies tensor-factorization models, losses, and regularization for link prediction. CP is general, while DistMult and ComplEx impose different parameter-sharing structures; training uses multiclass log-loss and data-dependent regularization weights.
- Tensor representation: Relational facts form a {0, 1}-valued tensor Y ∈ {0, 1}^N×P×N, with subject, predicate, and object modes.Known triples set tensor entries to one, and predicted tensor values rank candidate entities for held-out queries.
- Tensor models: CP represents a tensor as a sum of R rank-one tensors, with the smallest valid R defining its canonical rank.The score of a triple is linked to the corresponding entry in the tensor estimated by CP.
- Tensor models: DistMult constrains CP by sharing the subject and object factors, whereas ComplEx uses complex-conjugate factors for those modes.DistMult therefore produces a symmetric tensor, while ComplEx can represent any real tensor.
- Training: The training objective uses full multiclass log-loss, selected for satisfactory speed and motivated by prior results and the authors’ experiments.The instantaneous loss is defined for each training triple and predicted tensor.
- Training: CP minimizes a regularized empirical risk in which factor weights depend on the data and can reflect uneven sampling across tensor modes.For DistMult and ComplEx, the objective is analogous apart from parameter sharing and tensor computation.
3. Related Work
Related work frames link prediction as representation learning and tensor factorization, while highlighting parameter sharing, tensor norms, and computational constraints in large-scale knowledge bases.
- Link prediction models score relational triples using either two-way interactions or three-way multiplicative interactions.Two-way approaches include translation and bag-of-words models; three-way multiplicative methods report the strongest performances.
- Many competitive models share parameters between subject and object modes, with DistMult imposing the strongest sharing through subject-object symmetry.DistMult is described as the extreme case of this parameter-sharing strategy.
- Matrix trace-norm regularization motivates tensor norm approaches, including matricization-based penalties and tensor nuclear 2-norms.These tensor methods extend matrix-completion ideas but can be difficult to apply at large scale.
- CP is a closely related low-rank tensor decomposition that typically uses square loss and no regularization.The related-work discussion positions CP alongside other low-rank tensor methods.
- Generalized conditional-gradient optimization for tensor trace norms becomes too costly with binary or multiclass log-loss because the gradient lacks suitable structure.The approach is efficient in the described setup only with square error loss.
4. Nuclear p-Norm Regularization
The paper replaces conventional factor regularization with tensor nuclear p-norm formulations and analyzes their mathematical properties, implementation, and computational trade-offs.
- The proposed nuclear p-norm regularizers are derived variationally over bounded-rank CP decompositions.The formulation introduces p-norm-normalized decompositions and connects the penalty to the CP spectrum.
- The nuclear 3-norm admits a variational form that can replace usual regularization without additional computational cost under SGD.A weighted version regularizes only parameters involved in sampled triples, matching the complexity of the weighted Frobenius regularizer.
- For tensors of order D, the resulting penalty behaves as an ℓα/D penalty over the CP spectrum and recovers the matrix nuclear norm when α = p = 2.The p = α = 2 setting also recovers the familiar squared Frobenius regularizer.
- The usual squared Frobenius regularizer is not a tensor norm and is not the tensor analogue of the matrix trace norm.The paper shows its sub-level sets are non-convex, and a stronger result remains true after homogeneous rescaling.
- The weighting scheme is justified by analogy with matrix weighted trace norms to make the all-1 tensor’s nuclear 3-norm dimension-independent under uniform sampling.The authors explicitly present this as an analogy-based justification.
- On FB15K, nuclear 3-norm updates are about 1.5× faster than nuclear 2-norm updates in the authors’ implementation.The speed difference arises because minibatch SGD updates every coefficient for the weighted nuclear 2-norm formulation.
5. A New CP Objective
The new objective explicitly models predicates and their inverses, making the method invariant to dataset choices about predicate direction and improving benchmark performance.
- The reformulation appends inverse predicates by adding (obj, pred−1, sub) for every training triple (sub, pred, obj).At test time, left-hand-side queries are answered through the corresponding inverse predicate.
- The reformulation factorizes a tensor containing original and inverse predicates, then models the object fibers of this expanded tensor.This construction is motivated by evaluating both right-hand-side and left-hand-side rankings.
- The method is invariant to the arbitrary choice of including a predicate or its reciprocal in the dataset.The paper identifies this property as semantic invariance.
- At test time, right-hand-side queries use X̂_i,j,: while left-hand-side queries use X̂_k,j+P,: to rank candidate entities.These fibers correspond to the original and inverse-predicate portions of the expanded tensor.
- CP beats the previous state of the art on many benchmarks after applying the reformulated objective.The reformulation also appears to help ComplEx despite its shared entity-embedding parameters.
6. Experiments
Experiments show that CP and ComplEx are highly sensitive to optimization choices, while reciprocal reformulation produces major gains, especially for CP. Nuclear 3-norm regularization provides smaller, consistent improvements on harder datasets.
- Datasets and Experimental Setup: The experiments evaluate CP and ComplEx across five knowledge-base completion benchmarks using Standard and Reciprocal settings, filtered MRR and Hits@10, and grid-searched optimization parameters.The grid varies learning rate, batch size, rank, and regularization coefficients; results are compared with published baselines including ConvE and DistMult.
- Reimplementation of the Baselines: 0.33 to 0.46 filtered MRR on FB15K for CP and 0.70 to 0.80 for ComplEx mark improvements over their published Standard-setting results.The authors attribute the gains partly to multiclass log-loss, broader optimization and regularization searches, and nuclear 3-norm regularization.
- Standard vs Reciprocal: CP improves from 0.2 to 0.95 filtered MRR on WN18 and from 0.46 to 0.86 on FB15K under the Reciprocal reformulation.ComplEx also improves consistently, with the largest gains on FB15K and YAGO3-10; most improvements for both models occur in 1-m and m-m relation categories.
- Frobenius vs Nuclear 3: The nuclear 3-norm yields a small but consistent performance gain over Frobenius regularization, with the largest improvements on WN18RR, FB15K-237, and YAGO3-10.The authors checked the significance of the gain for CP on WN18RR using a signed-rank test.
- Effect of Optimization Parameters: Optimization hyperparameters can change filtered MRR by as much as 0.1, and batch-size effects remain large after 100 epochs while reversing between Standard and Reciprocal settings.This makes batch-size difficult to choose a priori.
7. Conclusion and Discussion
The paper concludes that CP can perform nearly as well as competing models when evaluated with an optimal formulation and configuration. It also identifies nuclear p-norm regularization as broadly interesting while leaving the causes of large performance differences theoretically unresolved.
- Conclusion: Systematic evaluation isolates optimization, formulation, and regularization effects, concluding that CP performs nearly as well as competitors in its optimal configuration.The authors present this comparison as relevant for prioritizing future knowledge-base-completion research.
- Conclusion: Nuclear p-norm regularizers with p ≠ 2 are proposed as independently interesting for tensor factorization beyond knowledge base completion.
- Open Questions: The paper lacks a strong theoretical justification for why correct problem formulation produces such large performance differences.The authors identify this explanation as an open question despite evidence that CP can perform extremely well on the evaluated datasets.
8. Appendix
The appendix analyzes why DistMult can achieve high filtered MRR on hierarchical predicates despite its symmetricity assumption, and develops supporting norm-based arguments. It also shows that the associated tensor quasi-norm is nonconvex for rank-2 tensors.
- 8.1. DistMult on hierarchical predicates: A hierarchical predicate is modeled as an n-ary tree of depth d, with nd leaves, one root, and approximately nd−1 internal nodes.The analysis focuses on how query counts differ across leaves, the root, and internal nodes.
- 8.1. DistMult on hierarchical predicates: For an internal node, n child queries can receive filtered rank 1 while its ancestor query receives rank n + 1.This ranking pattern is evaluated under n > 2.
- 8.1. DistMult on hierarchical predicates: The rank-1 queries outnumber the rank-(n + 1) queries, so hierarchical structure can yield high filtered MRR under DistMult.The count includes n rank-1 queries per internal node, n for the root, and nd for the leaves.
- 8.2. Proofs Lemma 2.: The appendix characterizes minimizers of the displayed norm expression using constrained optimization.The proof proceeds by first characterizing the minima and then studying a summand for positive parameters.
- 8.2. Proofs Lemma 2.: For a rank-2 tensor identified with a 2 × 2 matrix, the tensor quasi-norm exceeds 1, contradicting convexity.The argument uses the trace bound, the relation between ℓ_2/3 and ℓ_1 norms, and the need for at least two nonzero coordinates.