{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:52:25Z","timestamp":1743105145479,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030723071"},{"type":"electronic","value":"9783030723088"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T00:00:00Z","timestamp":1615852800000},"content-version":"vor","delay-in-days":74,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Large, heterogeneous datasets are characterized by missing or even erroneous information. This is more evident when they are the product of community effort or automatic fact extraction methods from external sources, such as text. A special case of the aforementioned phenomenon can be seen in knowledge graphs, where this mostly appears in the form of missing or incorrect edges and nodes.<\/jats:p><jats:p>Structured querying on such incomplete graphs will result in incomplete sets of answers, even if the correct entities exist in the graph, since one or more edges needed to match the pattern are missing. To overcome this problem, several algorithms for approximate structured query answering have been proposed. Inspired by modern Information Retrieval metrics, these algorithms produce a ranking of all entities in the graph, and their performance is further evaluated based on how high in this ranking the correct answers appear.<\/jats:p><jats:p>In this work we take a critical look at this way of evaluation. We argue that performing a ranking-based evaluation is not sufficient to assess methods for complex query answering. To solve this, we introduce Message Passing Query Boxes (MPQB), which takes binary classification metrics back into use and shows the effect this has on the recently proposed query embedding method MPQE.<\/jats:p>","DOI":"10.1007\/978-3-030-72308-8_8","type":"book-chapter","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T18:03:07Z","timestamp":1615831387000},"page":"107-124","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6891-5237","authenticated-orcid":false,"given":"Ruud","family":"van Bakel","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6567-5960","authenticated-orcid":false,"given":"Teodor","family":"Aleksiev","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5357-3705","authenticated-orcid":false,"given":"Daniel","family":"Daza","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0090-2069","authenticated-orcid":false,"given":"Dimitrios","family":"Alivanistos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5726-4638","authenticated-orcid":false,"given":"Michael","family":"Cochez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,16]]},"reference":[{"key":"8_CR1","unstructured":"Aleksiev, T.: Answering approximated graph queries, embedding the queries and entities as boxes. BSc. thesis, Computer Science, Vrije Universiteit Amsterdam, Supervised by Cochez, M. (2020)"},{"key":"8_CR2","unstructured":"Arakelyan, E., Daza, D., Minervini, P., Cochez, M.: Complex query answering with neural link predictors. In: International Conference on Learning Representations (2021). https:\/\/openreview.net\/forum?id=Mos9F9kDwkz"},{"key":"8_CR3","unstructured":"van Bakel, R.: Box R-GCN: Structured query answering using box embeddings for entities and queries. BSc. thesis, Computer Science, Vrije Universiteit Amsterdam, Supervised by Cochez, M. (2020)"},{"key":"8_CR4","unstructured":"Daza, D., Cochez, M.: Message passing query embedding. In: ICML Workshop - Graph Representation Learning and Beyond (2020). https:\/\/arxiv.org\/abs\/2002.02406"},{"key":"8_CR5","unstructured":"Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in Neural Information Processing Systems, pp. 3844\u20133852 (2016)"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Dong, T., Wang, Z., Li, J., Bauckhage, C., Cremers, A.B.: Triple classification using regions and fine-grained entity typing. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 77\u201385 (2019)","DOI":"10.1609\/aaai.v33i01.330177"},{"key":"8_CR7","unstructured":"Fey, M., Lenssen, J.E.: Fast graph representation learning with PyTorch Geometric. arXiv preprint arXiv:1903.02428 (2019)"},{"key":"8_CR8","unstructured":"Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6\u201311 August 2017, pp. 1263\u20131272 (2017)"},{"key":"8_CR9","unstructured":"Hamilton, W., Bajaj, P., Zitnik, M., Jurafsky, D., Leskovec, J.: Embedding logical queries on knowledge graphs. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 31, pp. 2026\u20132037. Curran Associates, Inc. (2018). https:\/\/proceedings.neurips.cc\/paper\/2018\/file\/ef50c335cca9f340bde656363ebd02fd-Paper.pdf"},{"key":"8_CR10","unstructured":"Hogan, A., et al.: Knowledge graphs. arXiv preprint arXiv:2003.02320 (2020)"},{"key":"8_CR11","unstructured":"Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)"},{"key":"8_CR12","doi-asserted-by":"publisher","unstructured":"van Krieken, E., Acar, E., van Harmelen, F.: Analyzing differentiable fuzzy implications. In: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, pp. 893\u2013903 (2020). https:\/\/doi.org\/10.24963\/kr.2020\/92","DOI":"10.24963\/kr.2020\/92"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Minervini, P., Demeester, T., Rockt\u00e4schel, T., Riedel, S.: Adversarial sets for regularising neural link predictors. In: UAI. AUAI Press (2017)","DOI":"10.18653\/v1\/K18-1007"},{"issue":"8","key":"8_CR14","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/3331166","volume":"62","author":"N Noy","year":"2019","unstructured":"Noy, N., Gao, Y., Jain, A., Narayanan, A., Patterson, A., Taylor, J.: Industry-scale knowledge graphs: lessons and challenges. Commun. ACM 62(8), 36\u201343 (2019)","journal-title":"Commun. ACM"},{"key":"8_CR15","unstructured":"Ren, H., Hu, W., Leskovec, J.: Query2box: reasoning over knowledge graphs in vector space using box embeddings (2020)"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Safavi, T., Koutra, D., Meij, E.: Evaluating the calibration of knowledge graph embeddings for trustworthy link prediction (2020)","DOI":"10.18653\/v1\/2020.emnlp-main.667"},{"key":"8_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/978-3-319-93417-4_38","volume-title":"The Semantic Web","author":"M Schlichtkrull","year":"2018","unstructured":"Schlichtkrull, M., Kipf, T.N., Bloem, P., van\u00a0den Berg, R., Titov, I., Welling, M.: Modeling relational data with graph convolutional networks. In: Gangemi, A., et al. (eds.) ESWC 2018. LNCS, vol. 10843, pp. 593\u2013607. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-93417-4_38"},{"key":"8_CR18","unstructured":"Serafini, L., d\u2019Avila Garcez, A.S.: Logic tensor networks: Deep learning and logical reasoning from data and knowledge. CoRR abs\/1606.04422 (2016). http:\/\/arxiv.org\/abs\/1606.04422"},{"key":"8_CR19","unstructured":"Socher, R., Chen, D., Manning, C.D., Ng, A.: Reasoning with neural tensor networks for knowledge base completion. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 26, pp. 926\u2013934. Curran Associates, Inc. (2013). https:\/\/proceedings.neurips.cc\/paper\/2013\/file\/b337e84de8752b27eda3a12363109e80-Paper.pdf"},{"key":"8_CR20","unstructured":"Trouillon, T., Welbl, J., Riedel, S., Gaussier, \u00c9., Bouchard, G.: Complex embeddings for simple link prediction. In: ICML, JMLR Workshop and Conference Proceedings, vol. 48, pp. 2071\u20132080. JMLR.org (2016)"},{"key":"8_CR21","unstructured":"Yang, B., Yih, W., He, X., Gao, J., Deng, L.: Embedding entities and relations for learning and inference in knowledge bases. In: Proceedings of the 3rd International Conference on Learning Representations, ICLR 2015, Conference Track Proceedings, San Diego, CA, USA, 7\u20139 May 2015 (2015)"},{"key":"8_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-030-49461-2_33","volume-title":"The Semantic Web","author":"MA Pellegrino","year":"2020","unstructured":"Pellegrino, M.A., Altabba, A., Garofalo, M., Ristoski, P., Cochez, M.: GEval: a modular and extensible evaluation framework for graph embedding techniques. In: Harth, A., et al. (eds.) ESWC 2020. LNCS, vol. 12123, pp. 565\u2013582. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-49461-2_33"}],"container-title":["Lecture Notes in Computer Science","Graph Structures for Knowledge Representation and Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-72308-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T18:15:04Z","timestamp":1615832104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-72308-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030723071","9783030723088"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-72308-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"16 March 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GKR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph Structures for Knowledge Representation and Reasoning","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwgskrr2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/graphkr.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"78% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2 invited contributions are also included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}