Complex Query Answering with Neural Link Predictors (Extended Abstract)*

1 Introduction

Knowledge Graphs (KGs) are graph-structured knowledge bases, where knowledge about the world is stored in the form of relationship between entities. KGs are an extremely flexible and versatile knowledge representation formalism - examples include general purpose knowledge bases such as DBpedia [Auer et al., 2007] and YAGO [Suchanek et al., 2007], domain-specific ones such as Bio2RDF [Dumontier et al., 2014] and Hetionet [Himmelstein et al., 2017] for life sciences and WordNet [Miller, 1992] for linguistics, and application-driven graphs such as the Google Knowledge Graph, Microsoft's Bing Knowledge Graph, and Facebook's Social Graph [Noy et al., 2019].

∗This is an extended abstract of Arakelyan et al. [2021], published in the proceedings of the 9th International Conference on Learning Representations (ICLR 2021), where it was awarded an Outstanding Paper Award.

1 At https://github.com/uclnlp/cqd

† Equal contribution, alphabetical order.

Neural link predictors [Nickel et al., 2016] tackle the problem of identifying missing edges in large KGs. However, in many complex domains, an open challenge is developing techniques for answering complex queries involving multiple and potentially unobserved edges, entities, and variables, rather than just single edges.

In this work, we propose Complex Query Decomposition (CQD) - a framework for answering First-Order Logic Queries, where the query is compiled in an end-to-end differentiable function, modelling the interactions between its atoms. The truth value of each atom is computed by a neural link predictor [Nickel et al., 2016] - a differentiable model that, given an atomic query, returns the likelihood that the fact it represents holds true. We then propose two approaches for identifying the most likely values for the variable nodes in a query - either by continuous or by combinatorial optimisation.

Recent work on embedding logical queries on KGs [Hamilton et al., 2018; Daza and Cochez, 2020; Ren et al., 2020] has suggested that in order to go beyond link prediction, more elaborate architectures, and a large and diverse dataset with millions of queries is required. In this work, we show that this is not the case, and demonstrate that it is possible to use an efficient neural link predictor trained for 1-hop query answering, to generalise to up to 8 complex query structures. By doing so, we produce more accurate results than state-of-the-art models, while using orders of magnitude less training data.

Summarising, in comparison with other approaches in the literature such as Query2Box [Ren et al., 2020] and BetaE [Ren and Leskovec, 2020], we find that the proposed framework i) achieves significantly better or equivalent predictive accuracy on a wide range of complex queries, ii) is capable of out-of-distribution generalisation, since it is trained on simple queries only and evaluated on complex queries, and iii) is more explainable, since the intermediate results for its

"Which drugs interact with proteins associated with diseases t₁ or t₂?"

"Which directors directed actors that won either an Oscar or an Emmy?"

?D : ∃P . interacts(D, P) ∧ [assoc(P, t 1 ) ∨ assoc(P, t 2 )]

?D : ∃A . directs(D, A) ∧ [prize(A, Oscar) ∨ prize(A, Emmy)]

sub-queries and variable assignments can be used to explain any given answer.

2 Existential Positive First-Order Logical Queries

A Knowledge Graph G ⊆ E ×R×E can be defined as a set of subject-predicate-object ⟨s, p, o⟩ triples, where each triple encodes a relationship of type p ∈ R between the subject s ∈ E and the object o ∈ E of the triple, where E and R denote the set of all entities and relation types, respectively. One can think of a Knowledge Graph as a labelled multi-graph, where entities E represent nodes, and edges are labelled with relation types R. Without loss of generality, a Knowledge Graph can be represented as a First-Order Logic Knowledge Base, where each triple ⟨s, p, o⟩ denotes an atomic formula p(s, o), with p ∈ R a binary predicate and s, o ∈ E its arguments.

Conjunctive queries are a sub-class of First-Order Logical queries that use existential quantification (∃) and conjunction (∧) operations. We consider conjunctive queries Q in the following form:

In Equation (1), the variable A is the target of the query, V1, . . . , Vm denote the bound variable nodes, while c ∈ E represent the input anchor nodes. Each ei denotes a logical atom, with either one (p(c, V )) or two variables (p(V, V ′ )), and e1 ∧ . . . ∧ en denotes a conjunction between n atoms.

The goal of answering the logical query Q consists in finding a set of entities �Q� ⊆ E such that a ∈ �Q� iff Q[a] holds true, where �Q� is the answer set of the query Q.

As illustrated in Figure 1, the dependency graph of a conjunctive query Q is a graph representation of Q where nodes correspond to variable or non-variable atom arguments in Q and edges correspond to atom predicates. We follow Hamilton et al. [2018] and focus on valid conjunctive queries - i.e. the dependency graph needs to be a directed acyclic graph, where anchor entities correspond to source nodes, and the query target A is the unique sink node.

Handling Disjunctions Our aim is answering a wider class of logical queries, namely Existential Positive First-Order (EPFO) queries [Dalvi and Suciu, 2004] that in addition to existential quantification and conjunction, also involve disjunction (∨). We follow Ren et al. [2020] by transforming a given EPFO query into Disjunctive Normal Form [DNF, Davey and Priestley, 2002], i.e. a disjunction of conjunctive queries. See Figure 1 for an example.

3 Complex Query Answering via Optimisation

We propose Complex Query Decomposition (CQD) as a framework for answering EPFO logical queries in the presence of missing edges. Given a query Q, we define the score of a target node a ∈ E as a candidate answer for a query as a function of the score of all atomic queries in Q, given a variable-to-entity substitution for all variables in Q.

Each variable is mapped to an embedding vector, that can either correspond to an entity c ∈ E or to a virtual entity. The score of each of the query atoms is determined individually using a neural link predictor [Nickel et al., 2016]. Then, the score of the query with respect to a given candidate answer Q[a] is computed by aggregating all atom scores using t-norms and t-conorms - continuous relaxations of the logical conjunction and disjunction operators.

Neural Link Prediction A neural link predictor is a differentiable model where atom arguments are first mapped into a k-dimensional embedding space, and then used for producing a score for the atom. More formally, given a query atom p(s, o), where p ∈ R and s, o ∈ E, the score for p(s, o) is computed as ϕp(es, eo), where es, eo ∈ Rk are the embedding vectors of s and o, and ϕp : Rk × Rk ↦→ [0, 1] is a scoring function computing the likelihood that entities s and o are related by the relationship p.

In our experiments, as neural link predictor, we use a regularised variant of ComplEx [Trouillon et al., 2016; Lacroix et al., 2018].

T-Norms A t-norm⊤ : [0, 1]×[0, 1] ↦→ [0, 1] is a generalisation of conjunction in logic [Klement et al., 2000, 2004]. Some examples include the G¨odel t-norm ⊤min(x, y) = min{x, y}, the product t-norm ⊤prod(x, y) = x · y, and the Łukasiewicz t-norm ⊤Luk(x, y) = max{0, x + y - 1}. Analogously, t-conorms are dual to t-norms for disjunctions given a t-norm ⊤, the complementary t-conorm is defined by ⊥(x, y) = 1 - ⊤(1 - x, 1 - y).

Continuous Reformulation of Complex Queries Let Q denote the following DNF query:

We want to know the variable assignments that render Q true. To achieve this, we can cast this as an optimisation problem, where the aim is finding a mapping from variables to entities that maximises the score of Q:

where ⊤ and ⊥ denote a t-norm and a t-conorm - a continuous generalisation of the logical conjunction and disjunction, respectively - and ϕp(es, eo) ∈ [0, 1] denotes the neural link prediction score for the atom p(s, o). We write t-norms and t-conorms as infix operators since they are both associative.

Note that, in Equation (2), the bound variable nodes V1, . . . , Vm are only used through their embedding vector: to compute ϕp(ec, eV ) we only use the embedding representation eV ∈ Rk of V , and do not need to know which entity the variable V corresponds to. This means that we have two possible strategies for finding the optimal variable embeddings eV ∈ Rk with V ∈ {A, V1, . . . , Vm} for maximising the objective in Equation (2), namely continuous optimisation, where we optimise eV using gradient-based optimisation, and combinatorial optimisation, where we search for the optimal variable-to-entity assignment.

3.1 Complex Query Answering via Continuous Optimisation

One way we can solve the optimisation problem in Equation (2) is by finding the variable embeddings that maximise the score of a complex query. Equation (2) is modified into the following continuous optimisation problem:

In Equation (3) we directly optimise the embedding representations eA, eV1 , . . . , eVm ∈ Rk of variables A, V1, . . . , Vm, rather than exploring the combinatorial space of variable-toentity mappings. In this way, we can tackle the maximisation problem in Equation (3) using gradient-based optimisation methods, such as Adam [Kingma and Ba, 2015]. Then, after we identified the optimal representation for variables A, V1, . . . , Vm, we replace the query target embedding eA with the embedding representations ec ∈ Rk of all entities c ∈ E, and use the resulting complex query score to compute the likelihood that such entities answer the query. We denote this variant of CQD as CQD-CO.

3.2 Complex Query Answering via Combinatorial Optimisation

Another way we tackle the optimisation problem in Equation (2) is by greedily searching for a set of variable substitutions S = {A ← a, V1 ← v1, . . . , Vm ← vm}, with a, v1, . . . , vm ∈ E, that maximises the complex query score, in a procedure akin to beam search. We do so by traversing the dependency graph of a query Q and, whenever we find an atom in the form p(c, V ), where p ∈ R, c is either an entity or a variable for which we already have a substitution, and V is a variable for which we do not have a substitution yet, we replace V with all entities in E and retain the top-k entities t ∈ E that maximise ϕp(ec, et) - i.e. the most likely entities to appear as a substitution of V according to the neural link predictor.

Our procedure is akin to beam search: as we traverse the dependency graph of a query, we keep a beam with the most promising variable-to-entity substitutions identified so far. We thus denote this variant as CDQ-Beam. Note that scoring all possible entities can be done efficiently and in a single step on a GPU by replacing V with the entity embedding matrix.

4 Experiments

Datasets Following Ren et al. [2020], we evaluate our approach on FB15k [Bordes et al., 2013] and FB15k237 [Toutanova and Chen, 2015] - two subset of the Freebase knowledge graph - and NELL995 [Xiong et al., 2017], a KG generated by the NELL system [Mitchell et al., 2015]. We use the datasets generated by Ren and Leskovec [2020], who notice that in previous benchmarks, test queries may have more than 5,000 answers. To make the task more challenging, they regenerate the same number of validation and test queries for each of the 9 query structures, keeping only those with a number of answer smaller than a threshold. We consider a total of 9 query types, including atomic queries, and 2 query types that contain disjunctions - the different query types are shown in Figure 2. In our framework, the neural link predictor is only trained on atomic queries, while the evaluation is carried out on the complete set of query types in Figure 2.

4.1 Results

We detail the results of H@3 for all different query types in Table 1. We observe that, on average, both CQD-CO and CQD-Beam produce more accurate results than GQE and Q2B, while using orders of magnitude less training data. In particular, combinatorial optimisation in CQD-Beam outperforms the baselines across all datasets.

The results for chained queries (2p and 3p) show that CQDBeam is effective, even when increasing the length of the chain. The most difficult case corresponds to 3p queries, where the number of candidate variable substitutions increases due to the branching factor of the search procedure.

Explaining Answers to Complex Queries A useful property of our framework is its transparency when computing scores for distinct atoms in a query. Unlike GQE and Q2B - two neural models that encode a query into a vector via a set of non-linear transformations - CQD-Beam is able to produce an explanation for a given answer in terms of intermediate variable assignments as it selects a top-k list of candidates for each atom. By inspecting these decisions we can thus identify failure modes of our framework, even when it produces seemingly correct answers. This is in contrast with previously proposed black-box models for query answering, where such an analysis is not possible.

5 Conclusions

We proposed a framework - Complex Query Decomposition (CQD) - for answering Existential Positive First-Order logical queries by reasoning over sets of entities in embedding space. In our framework, answering a complex query is reduced to answering each of its sub-queries, and aggregating the resulting scores via t-norms. The benefit of the method is that we only need to train a neural link prediction model on atomic queries to use our framework for answering a given complex query, without the need of training on millions of generated complex queries. This comes with the added value that we are able to explain each step of the query answering process regardless of query complexity, instead of using a black-box neural query embedding model.

The proposed method is agnostic to the type of query, and is able to generalise without explicitly training on a specific variety of queries. Experimental results show that CQD produces significantly more accurate results than current stateof-the-art complex query answering methods on incomplete Knowledge Graphs.