Elamur Research⌕
☰
home / papers / 2016 / Complex Embeddings for Simple Link Prediction

Complex Embeddings for Simple Link Prediction

Paper · 2016 · Théo Trouillon, Johannes Welbl, Sebastian Riedel et al.

Summary

The paper addresses link prediction, that is, automatically completing missing facts in large knowledge bases such as Freebase or DBPedia. The authors represent each fact as a "subject–relation–object" triple and complete a three-dimensional tensor via latent factorization. The novelty of the ComplEx model is that entity and relation vectors take complex values, and the score of a fact is computed as the real part of the Hermitian product. Because one of the vectors is conjugated, the score depends on the order of the arguments. The model therefore captures both symmetric and antisymmetric relations, while memory and computation time grow linearly with the dimensionality. Theoretically, the approach rests on the spectral decomposition of normal matrices, and for practical implementation an equivalent formulation using only real numbers is given. On standard benchmarks, ComplEx consistently outperforms stronger and more complex models such as NTN and HolE. Thus, making a model capture more types of relations does not necessarily require inflating the number of parameters: it is enough to change the numerical space of the embeddings.

Key points

  • The ComplEx scoring function is Re(<w_r, e_s, ē_o>) with e_s, e_o, w_r ∈ C^K. The complexity is O(K) in both time and memory. For comparison, RESCAL requires O(K²), and HolE requires O(K log K) in time due to circular correlation.
  • DistMult is symmetric in subject and object by construction. ComplEx removes this limitation without additional parameters.
  • For FB15K, the authors separately studied the effect of the number of negative examples per positive one (from 1 to 200). The best result was obtained with 100 negatives: filtered MRR 0.737 and Hits@1 64.8%. With 200 negatives, accuracy drops again. As a trade-off between accuracy and training time, the authors recommend 50.
  • The code is open on GitHub: ttrouill/complex. The paper was published at ICML 2016.
  • Among future directions, the authors name smarter generation of negative examples and complex embeddings in other dot-product-based models, in particular in deep neural networks.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University College LondonLondon · United Kingdom88 works · 19,432 citations🎓Université Grenoble AlpesSaint-Martin-d'Hères · France20 works · 8,059 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksInformation Systems · 1,437 works

🧭 Topics 1Research subjects and languages the work is about.Knowledge graphs & ontologies · 192 works

💡 Concepts 1Key ideas and methods explained on our concept pages.Knowledge graph · 49 works

Cite

Cite as Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier and Guillaume Bouchard. 2016. Complex Embeddings for Simple Link Prediction. arXiv:1606.06357.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1606.06357 · arXiv 1606.06357

@misc{trouillon2016complex,
  title = {{Complex Embeddings for Simple Link Prediction}},
  author = {Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier and Guillaume Bouchard},
  year = {2016},
  doi = {10.48550/arxiv.1606.06357},
  eprint = {1606.06357},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1606.06357}
}

References

26 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Alon, Noga, Moran, Shay, and Yehudayoff, Amir. Sign rank versus vc dimension. arXiv preprint arXiv:1503.07648, 2015. — [arXiv:1503.07648](https://arxiv.org/abs/1503.07648) find
  2. Auer, Sren, Bizer, Christian, Kobilarov, Georgi, Lehmann, Jens, and Ives, Zachary. Dbpedia: A nucleus for a web of open data. In In 6th Intl Semantic Web Conference, Busan, Korea, pp. 11–15. Springer, 2007. find
  3. Autonne, L. Sur les matrices hypohermitiennes et sur les matrices unitaires. Ann. Univ. Lyons, Nouvelle Srie I, 38: 1–77, 1915. find
  4. Beltrami, Eugenio. Sulle funzioni bilineari. Giornale di Matematiche ad Uso degli Studenti Delle Universita, 11 (2):98–106, 1873. find
  5. Bergstra, James, Breuleux, Olivier, Bastien, Frédéric, Lamblin, Pascal, Pascanu, Razvan, Desjardins, Guillaume, Turian, Joseph, Warde-Farley, David, and Bengio, Yoshua. Theano: a CPU and GPU math expression compiler. In Proceedings of the Python for Scientific Computing Conference (SciPy), June 20… find
  6. Bollacker, Kurt, Evans, Colin, Paritosh, Praveen, Sturge, Tim, and Taylor, Jamie. Freebase: a collaboratively created graph database for structuring human knowledge. In SIGMOD 08 Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247–1250, 2008. find
  7. Bordes, Antoine, Usunier, Nicolas, Garcia-Duran, Alberto, Weston, Jason, and Yakhnenko, Oksana. Irreflexive and Hierarchical Relations as Translations. In CoRR, 2013a. find
  8. Bordes, Antoine, Usunier, Nicolas, Garcia-Duran, Alberto, Weston, Jason, and Yakhnenko, Oksana. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems, pp. 2787–2795, 2013b.
  9. Bouchard, Guillaume, Singh, Sameer, and Trouillon, Théo. On approximate reasoning capabilities of low-rank vector spaces. In AAAI Spring Syposium on Knowledge Representation and Reasoning (KRR): Integrating Symbolic and Neural Approaches, 2015. find
  10. Dong, Xin, Gabrilovich, Evgeniy, Heitz, Geremy, Horn, Wilko, Lao, Ni, Murphy, Kevin, Strohmann, Thomas, Sun, Shaohua, and Zhang, Wei. Knowledge vault: A web-scale approach to probabilistic knowledge fusion. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Dat… find
  11. Duchi, John, Hazan, Elad, and Singer, Yoram. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121–2159, 2011. find
  12. Getoor, Lise and Taskar, Ben. Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning). The MIT Press, 2007. ISBN 0262072882. find
  13. Hitchcock, F. L. The expression of a tensor or a polyadic as a sum of products. J. Math. Phys, 6(1):164–189, 1927. find
  14. Jenatton, Rodolphe, Bordes, Antoine, Le Roux, Nicolas, and Obozinski, Guillaume. A Latent Factor Model for Highly Multi-relational Data. In Advances in Neural Information Processing Systems 25, pp. 3167–3175, 2012. find
  15. Koren, Yehuda, Bell, Robert, and Volinsky, Chris. Matrix factorization techniques for recommender systems. Computer, 42(8):30–37, 2009. find
  16. Linial, Nati, Mendelson, Shahar, Schechtman, Gideon, and Shraibman, Adi. Complexity measures of sign matrices. Combinatorica, 27(4):439–463, 2007. find
  17. Nickel, Maximilian, Tresp, Volker, and Kriegel, Hans-Peter. A Three-Way Model for Collective Learning on Multi-Relational Data. In 28th International Conference on Machine Learning, pp. 809—-816, 2011. find
  18. Nickel, Maximilian, Jiang, Xueyan, and Tresp, Volker. Reducing the rank in relational factorization models by including observable patterns. In Advances in Neural Information Processing Systems, pp. 1179–1187, 2014. find
  19. Nickel, Maximilian, Murphy, Kevin, Tresp, Volker, and Gabrilovich, Evgeniy. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11–33, 2016a. find
  20. Nickel, Maximilian, Rosasco, Lorenzo, and Poggio, Tomaso A. Holographic embeddings of knowledge graphs. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 1955–1961, 2016b. find
  21. Riedel, Sebastian, Yao, Limin, McCallum, Andrew, and Marlin, Benjamin M. Relation extraction with matrix factorization and universal schemas. In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, pp. 74–84, 2013. find
  22. Socher, Richard, Chen, Danqi, Manning, Christopher D, and Ng, Andrew. Reasoning with neural tensor networks for knowledge base completion. In Advances in Neural Information Processing Systems, pp. 926–934, 2013.
  23. Sutskever, Ilya. Modelling Relational Data using Bayesian Clustered Tensor Factorization. In Advances in Neural Information Processing Systems, volume 22, pp. 1–8, 2009. find
  24. Trouillon, Théo, Dance, Christopher R., Gaussier, Éric, and Bouchard, Guillaume. Decomposing real square matrices via unitary diagonalization. arXiv:1605.07103, 2016. — [arXiv:1605.07103](https://arxiv.org/abs/1605.07103) find
  25. Welbl, Johannes, Bouchard, Guillaume, and Riedel, Sebastian. A factorization machine framework for testing bigram embeddings in knowledgebase completion. arXiv:1604.05878, 2016. find
  26. Yang, Bishan, Yih, Wen-tau, He, Xiaodong, Gao, Jianfeng, and Deng, Li. Embedding entities and relations for learning and inference in knowledge bases. In International Conference on Learning Representations, 2015.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/trouillon-2016-complex-embeddings-simple-link-prediction/