Elamur Research⌕
☰
home / papers / 2020 / Complex Query Answering with Neural Link Predictors

Complex Query Answering with Neural Link Predictors

Paper · 2020 · Erik Arakelyan, Daniel Daza, Pasquale Minervini et al.

Summary

The paper addresses answering complex logical queries over incomplete knowledge graphs (KGs). Such queries combine conjunction, disjunction and the existential quantifier, and some of the required links may be missing from the graph. Earlier methods, such as GQE and Query2Box, encoded the whole query as a vector. Training them required millions of generated complex queries. The authors propose the CQD framework, which turns a query into a differentiable objective function. A pre-trained link predictor, ComplEx, scores the plausibility of each atom, and the atom scores are combined through t-norms and t-conorms. CQD searches for the best variable assignments in two ways: gradient-based optimization of embeddings (CQD-CO) or combinatorial beam search over entities (CQD-Beam). The model is trained only on one-hop queries, yet it also works on more complex structures not seen during training. On FB15k, FB15k-237 and NELL995 the method outperforms the state of the art, with relative Hits@3 gains from 8 to 40%. It also needs orders of magnitude less training data. The intermediate variable assignments explain how the model arrived at its answer. Thus, complex reasoning over KGs does not necessarily require building large specialized architectures.

Key points

  • The method is evaluated on three knowledge graphs: FB15k, FB15k-237 and NELL995. Nine query types are tested (1p, 2p, 3p, 2i, 3i, ip, pi, 2u, up), eight of which have a complex structure. The baselines for comparison are GQE and Query2Box.
  • On FB15k with embedding dimension 1000, CQD-Beam reaches Hits@3 0.779 on 2p queries, whereas Query2Box has 0.413. On 3p queries the result is 0.584 versus 0.303, and on 1p it is 0.918 versus 0.786.
  • On chain queries CQD-Beam is markedly more accurate than CQD-CO: on FB15k for 2p it is 0.779 versus 0.454. High accuracy is retained even with embedding dimension 100.
  • The predictor used is ComplEx with N3 regularization (Lacroix et al., 2018). Replacing it with DistMult lowers accuracy slightly, but it remains higher than GQE and Query2Box.
  • The code and data are open: github.com/uclnlp/cqd. CQD-Beam spends the most time on multi-hop chain queries, because the predictor is called at every step of the chain.

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 Kingdom119 works · 23,545 citations🎓Vrije Universiteit AmsterdamAmsterdam · Netherlands45 works · 3,544 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

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

Cite

Cite as Erik Arakelyan, Daniel Daza, Pasquale Minervini and Michael Cochez. 2020. Complex Query Answering with Neural Link Predictors. arXiv:2011.03459.

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

@misc{arakelyan2020complex,
  title = {{Complex Query Answering with Neural Link Predictors}},
  author = {Erik Arakelyan, Daniel Daza, Pasquale Minervini and Michael Cochez},
  year = {2020},
  doi = {10.48550/arxiv.2011.03459},
  eprint = {2011.03459},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2011.03459}
}

References

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

  1. Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary G. Ives. DBpedia: A nucleus for a web of open data. In ISWC/ASWC, volume 4825 of Lecture Notes in Computer Science, pp. 722–735. Springer, 2007. find
  2. Antoine Bordes, Nicolas Usunier, Alberto Garcı́a-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pp. 2787–2795, 2013.
  3. Nilesh N. Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. In VLDB, pp. 864–875. Morgan Kaufmann, 2004. find
  4. Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In EACL (1), pp. 132–141. Association for Computational Linguistics, 2017. find
  5. Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In ICLR (Poster). OpenReview.net, 2018. find
  6. Brian A. Davey and Hilary A. Priestley. Introduction to Lattices and Order, Second Edition. Cambridge University Press, 2002. find
  7. Daniel Daza and Michael Cochez. Message passing query embedding. In ICML Workshop - Graph Representation Learning and Beyond, 2020. URL https://arxiv.org/abs/2002.02406. — [arXiv:2002.02406](https://arxiv.org/abs/2002.02406) ↗
  8. Luc De Raedt. Logical and relational learning. Cognitive Technologies. Springer, 2008. find
  9. Michel Dumontier, Alison Callahan, Jose Cruz-Toledo, Peter Ansell, Vincent Emonet, François Belleau, and Arnaud Droit. Bio2RDF release 3: A larger, more connected network of linked data for the life sciences. In International Semantic Web Conference (Posters & Demos), volume 1272 of CEUR Workshop P… find
  10. Tal Friedman and Guy Van den Broeck. Symbolic querying of vector spaces: Probabilistic databases meets relational embeddings. In UAI, volume 124 of Proceedings of Machine Learning Research, pp. 1268–1277. AUAI Press, 2020. find
  11. Lise Getoor and Ben Taskar. Introduction to statistical relational learning. The MIT Press, 2007. find
  12. Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Jointly embedding knowledge graphs and logical rules. In EMNLP, pp. 192–202. The Association for Computational Linguistics, 2016. find
  13. Kelvin Guu, John Miller, and Percy Liang. Traversing knowledge graphs in vector space. In EMNLP, pp. 318–327. The Association for Computational Linguistics, 2015. find
  14. William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In NeurIPS, pp. 2030–2041, 2018. find
  15. Daniel S. Himmelstein, Antoine Lizee, Christine Hessler, Leo Brueggeman, Sabrina L. Chen, Dexter Hadley, Ari Green, Pouya Khankhanian, and Sergio E. Baranzini. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. bioRxiv, 2017. doi: 10.1101/087619. URL https://www.biorxi… — [doi:10.1101/087619](https://doi.org/10.1101/087619) ↗
  16. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
  17. Erich-Peter Klement, Radko Mesiar, and Endre Pap. Triangular Norms, volume 8 of Trends in Logic. Springer, 2000. find
  18. Erich-Peter Klement, Radko Mesiar, and Endre Pap. Triangular norms. position paper I: basic analytical and algebraic properties. Fuzzy Sets Syst., 143(1):5–26, 2004. find
  19. Bhushan Kotnis, Carolin Lawrence, and Mathias Niepert. Answering complex queries in knowledge graphs with bidirectional sequence encoders. CoRR, abs/2004.02596, 2020. — [arXiv:2004.02596](https://arxiv.org/abs/2004.02596) find
  20. Denis Krompaß, Maximilian Nickel, and Volker Tresp. Querying factorized probabilistic triple databases. In International Semantic Web Conference (2), volume 8797 of Lecture Notes in Computer Science, pp. 114–129. Springer, 2014. find
  21. Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 2869–2878. PMLR, 2018. find
  22. Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smoothing the geometry of probabilistic box embeddings. In ICLR. OpenReview.net, 2019. find
  23. George A. Miller. WORDNET: a lexical database for english. In HLT. Morgan Kaufmann, 1992.
  24. Pasquale Minervini, Thomas Demeester, Tim Rocktäschel, and Sebastian Riedel. Adversarial sets for regularising neural link predictors. In UAI. AUAI Press, 2017. find
  25. Pasquale Minervini, Matko Bosnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. In AAAI, pp. 5182–5190. AAAI Press, 2020a. find
  26. Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies in end-to-end differentiable proving. In ICML, Proceedings of Machine Learning Research. PMLR, 2020b. find
  27. Tom M. Mitchell, William W. Cohen, Estevam R. Hruschka Jr., Partha Pratim Talukdar, Justin Betteridge, Andrew Carlson, Bhavana Dalvi Mishra, Matthew Gardner, Bryan Kisiel, Jayant Krishnamurthy, Ni Lao, Kathryn Mazaitis, Thahir Mohamed, Ndapandula Nakashole, Emmanouil A. Platanios, Alan Ritter, Mehdi… find
  28. Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11–33, 2016. find
  29. Natalya Fridman Noy, Yuqing Gao, Anshu Jain, Anant Narayanan, Alan Patterson, and Jamie Taylor. Industry-scale knowledge graphs: lessons and challenges. Commun. ACM, 62(8):36–43, 2019. find
  30. Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. find
  31. OpenReview.net, 2020. URL https://openreview.net/forum?id=BJgr4kSFDS. ↗
  32. Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In NIPS, pp. 3788–3800, 2017.
  33. Luciano Serafini and Artur S. d’Avila Garcez. Logic tensor networks: Deep learning and logical reasoning from data and knowledge. CoRR, abs/1606.04422, 2016. URL http://arxiv.org/abs/1606.04422. — [arXiv:1606.04422](https://arxiv.org/abs/1606.04422) ↗
  34. Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: a core of semantic knowledge. In WWW, pp. 697–706. ACM, 2007. find
  35. 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, Beijing, China, July 2015. Association for Computational Linguistics. doi: 10.18653/v1…
  36. Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pp. 2071–2080. JMLR.org, 2016.
  37. Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing Differentiable Fuzzy Implications. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, pp. 893–903, 9 2020. doi: 10.24963/kr.2020/92. URL https://doi.org/10.24963/kr.2020/92. — [doi:10.24963/kr.2020/92](https://doi.org/10.24963/kr.2020/92) ↗
  38. Meng Wang, Ruijie Wang, Jun Liu, Yihe Chen, Lei Zhang, and Guilin Qi. Towards empty answers in SPARQL: approximating querying with RDF embedding. In International Semantic Web Conference (1), volume 11136 of Lecture Notes in Computer Science, pp. 513–529. Springer, 2018. find
  39. Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel. Nlprolog: Reasoning with weak unification for question answering in natural language. In ACL (1), pp. 6151–6161. Association for Computational Linguistics, 2019. find
  40. Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, pp. 564–573. Association for Computational Linguistics, 2017. find
  41. Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/arakelyan-2020-complex-query-answering-neural-link/