New query embedding method with increased expressiveness to be presented at the Web conference

January 26, 2025

Researchers from the Institute for Artificial Intelligence will present their work at the Web Conference 2025, in Sidney, Australia, from April 28 to May 2.

Query embedding methods are used to predict the answers to queries by embedding entities and queries. They decompose queries into subqueries, and perform complex reasoning since tasks are divided into subtasks. However, existing query embedding methods were limited to tree-form queries. In the paper "DAGE: DAG Query Answering via Relational Combinator with Logical Constraints," the researchers Yunjie He, Bo Xiong, Daniel Hernández, Yuquicheng Zhu, Evgeny Kharlamov, and Steffen Staab, developed a method to extend the capacity of existing query embedding methods for queries whose is structure can be seen as a DAG, and answer queries like "give all works x edited by an Oscar winner y and produced by an Oscar winner y." This query is not tree-form because it cannot be equivalent divided. Indeed, if we divide it into the queries "give all works x edited by an Oscar winner y" and "give all works produced by an Oscar winner y," then we lose the requirement of that y must refer to the same values in both subqueries.

Abstract

Predicting answers to queries over knowledge graphs is called a complex reasoning task because answering a query requires subdividing it into subqueries. Existing query embedding methods use this decomposition to compute the embedding of a query as the combination of the embedding of the subqueries. This requirement limits the answerable queries to queries having a single free variable and being decomposable, which are called tree-form queries and correspond to the SROI⁻ description logic. In this paper, we define a more general set of queries, called DAG queries and formulated in the ALCOIR description logic, propose a query embedding method for them, called DAGE, and a new benchmark to evaluate query embeddings on them. Given the computational graph of a DAG query, DAGE combines the possibly multiple paths between two nodes into a single path with a trainable operator that represents the intersection of relations and learns DAG-DL concepts from tautologies. We show that it is possible to implement DAGE on top of existing query embedding methods, and we empirically measure the improvement of our method over the results of vanilla methods evaluated in tree-form queries that approximate the DAG queries of our proposed benchmark.

Preprint: https://doi.org/10.48550/arXiv.2410.22105

To the top of the page