CoChat
Sign Up
PreprintCited by 247Tensor decomposition and applicationsAdvanced Graph Neural NetworksTopic Modeling

Canonical Tensor Decomposition for Knowledge Base Completion

Open access
Lacroix, Timothée, Usunier, Nicolas, Obozinski, Guillaume·2018·arXiv
DOI 10.48550/arxiv.1806.07297arXiv 1806.07297
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1806.07297

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • 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.”

    From TuckER: Tensor Factorization for Knowledge Graph Completion (2019) · cites this paper as Lacroix et al., 2018

    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.”

    From TuckER: Tensor Factorization for Knowledge Graph Completion (2019) · cites this paper as Lacroix et al., 2018

    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

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 34

  1. Bordes, A., Weston, J., Collobert, R., and Bengio, Y. Learning structured embeddings of knowledge bases. In Conference on artificial intelligence , 2011.
  2. Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O. Translating Embeddings for Modeling Multi-relational Data. In Burges, C. J. C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 26 , pp. 2787-2795. Curran Associates, Inc., 2013.
  3. Bordes, A., Glorot, X., Weston, J., and Bengio, Y. A semantic matching energy function for learning with multirelational data. Machine Learning , 94(2):233-259, 2014.
  4. Cai, J.-F., Candès, E. J., and Shen, Z. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization , 20(4):1956-1982, 2010.
  5. Candès, E. J. and Recht, B. Exact matrix completion via convex optimization. Foundations of Computational mathematics , 9(6):717, 2009.
  6. Cheng, H., Yu, Y., Zhang, X., Xing, E., and Schuurmans, D. Scalable and sound low-rank tensor learning. In Artificial Intelligence and Statistics , pp. 1114-1123, 2016.
  7. Dettmers, T., Minervini, P., Stenetorp, P., and Riedel, S. Convolutional 2d knowledge graph embeddings. arXiv preprint arXiv:1707.01476 , 2017. · arXiv
  8. Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research , 12(Jul):21212159, 2011.
  9. Foygel, R., Shamir, O., Srebro, N., and Salakhutdinov, R. R. Learning with the weighted trace-norm under arbitrary sampling distributions. In Advances in Neural Information Processing Systems , pp. 2133-2141, 2011.
  10. Friedland, S. and Lim, L.-H. Nuclear norm of higher-order tensors. Mathematics of Computation , 87(311):12551281, 2018.
  11. Garcia-Duran, A., Bordes, A., Usunier, N., and Grandvalet, Y. Combining two and three-way embedding models for link prediction in knowledge bases. Journal of Artificial Intelligence Research , 55:715-742, 2016.
  12. Guu, K., Miller, J., and Liang, P. Traversing knowledge graphs in vector space. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing , pp. 318-327, 2015.
  13. Hitchcock, F. L. The expression of a tensor or a polyadic as a sum of products. Studies in Applied Mathematics , 6 (1-4):164-189, 1927.
  14. Jaggi, M., Sulovsk, M., and others. A simple algorithm for nuclear norm regularized problems. In Proceedings of the 27th international conference on machine learning (ICML-10) , pp. 471-478, 2010.
  15. Joulin, A., Grave, E., Bojanowski, P., Nickel, M., and Mikolov, T. Fast linear model for knowledge graph embeddings. arXiv preprint arXiv:1710.10881 , 2017. · arXiv
  16. Kadlec, R., Bajgar, O., and Kleindienst, J. Knowledge Base Completion: Baselines Strike Back. In Proceedings of the 2nd Workshop on Representation Learning for NLP , pp. 69-74, 2017.
  17. Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 , 2014. · arXiv
  18. Kolda, T. G. and Bader, B. W. Tensor decompositions and applications. SIAM review , 51(3):455-500, 2009.
  19. Koren, Y., Bell, R., and Volinsky, C. Matrix factorization techniques for recommender systems. Computer , 42(8), 2009.
  20. Krompass, D., Baier, S., and Tresp, V. Type-constrained representation learning in knowledge graphs. In International Semantic Web Conference , pp. 640-655. Springer, 2015.
  21. Lao, N., Mitchell, T., and Cohen, W. W. Random walk inference and learning in a large scale knowledge base. In Proceedings of the Conference on Empirical Methods in Natural Language Processing , pp. 529-539. Association for Computational Linguistics, 2011.
  22. Ma, S., Ding, J., Jia, W., Wang, K., and Guo, M. Transt: Type-based multiple embedding representations for knowledge graph completion. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases , pp. 717-733. Springer, 2017.
  23. Negahban, S. and Wainwright, M. J. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Journal of Machine Learning Research , 13 (May):1665-1697, 2012.
  24. Nguyen, D. Q. An overview of embedding models of entities and relationships for knowledge base completion. arXiv preprint arXiv:1703.08098 , 2017. · arXiv
  25. Nickel, M., Tresp, V., and Kriegel, H.-P. A three-way model for collective learning on multi-relational data. In Proceedings of the 28th international conference on machine learning (ICML-11) , pp. 809-816, 2011.
  26. Nickel, M., Murphy, K., Tresp, V., and Gabrilovich, E. A Review of Relational Machine Learning for Knowledge Graphs. Proceedings of the IEEE , 104(1):11-33, 2016a.
  27. Rennie, J. D. and Srebro, N. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference on Machine learning , pp. 713-719. ACM, 2005.
  28. Srebro, N. and Salakhutdinov, R. R. Collaborative filtering in a non-uniform world: Learning with the weighted trace norm. In Advances in Neural Information Processing Systems , pp. 2056-2064, 2010.
  29. Srebro, N., Rennie, J., and Jaakkola, T. S. Maximum-margin matrix factorization. In Advances in neural information processing systems , pp. 1329-1336, 2005.
  30. Tomioka, R., Hayashi, K., and Kashima, H. Estimation of low-rank tensors via convex optimization. arXiv preprint arXiv:1010.0789 , 2010. · arXiv
  31. Toutanova, K. and Chen, D. 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.
  32. Wimalawarne, K., Sugiyama, M., and Tomioka, R. Multitask learning meets tensor factorization: task imputation via convex optimization. In Advances in neural information processing systems , pp. 2825-2833, 2014.
  33. Yang, B., Yih, W.-t., He, X., Gao, J., and Deng, L. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575 , 2014. · arXiv
  34. Yuan, M. and Zhang, C.-H. On tensor completion via nuclear norm minimization. Foundations of Computational Mathematics , 16(4):1031-1068, 2016.

Cited by

Sorted by citations

Authors
Lacroix, T., Usunier, N., & Obozinski, G.
Affiliations
  • Meta (United States) (US)
  • Laboratoire d'Informatique Gaspard-Monge (FR)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2018
Volume
80
Pages
2863-2872
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1806.07297
arXiv
1806.07297
OpenAlex
W2803992439
Cited by
247
References
1
Citations by year
2025: 13 · 2024: 20 · 2023: 24 · 2022: 41 · 2021: 61 · 2020: 49 · 2019: 36 · 2018: 2 · 2017: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • HAL (submittedVersion, other-oa)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Mathematics › Computational Mathematics › Tensor decomposition and applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
Keywords
knowledge base completion, CP decomposition, complexes, third-order tensors

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review