A neuro-symbolic framework for answering conjunctive queries
Pablo Barceló Tamara Cucumides Floris Geerts Juan Reutter Miguel Romero
The problem of answering logical queries over incomplete knowledge graphs is
receiving significant attention in the machine learning community.
Neuro-symbolic models are a promising recent approach, showing good performance
and allowing for good interpretability properties. These models rely on trained
architectures to execute atomic queries, combining them with modules that
simulate the symbolic operators in queries. Unfortunately, most neuro-symbolic
query processors are limited to the so-called tree-like logical queries that
admit a bottom-up execution, where the leaves are constant values or anchors,
and the root is the target variable. Tree-like queries, while expressive, fail
short to express properties in knowledge graphs that are important in practice,
such as the existence of multiple edges between entities or the presence of
triangles.
  We propose a framework for answering arbitrary conjunctive queries over
incomplete knowledge graphs. The main idea of our method is to approximate a
cyclic query by an infinite family of tree-like queries, and then leverage
existing models for the latter. Our approximations achieve strong guarantees:
they are complete, i.e. there are no false negatives, and optimal, i.e. they
provide the best possible approximation using tree-like queries. Our method
requires the approximations to be tree-like queries where the leaves are
anchors or existentially quantified variables. Hence, we also show how some of
the existing neuro-symbolic models can handle these queries, which is of
independent interest. Experiments show that our approximation strategy achieves
competitive results, and that including queries with existentially quantified
variables tends to improve the general performance of these models, both on
tree-like queries and on our approximation strategy.