Complex Query Answering with Neural Link Predictors
Authors: Erik Arakelyan
Daniel Daza
Pasquale Minervini
Michael Cochez
Venue: ICLR 2021 Oral (2021)
Keywords: neural link prediction
complex query answering

Abstract: Neural link predictors are immensely useful for identifying missing edges in large scale Knowledge Graphs. However, it is still not clear how to use these models for answering more complex queries that arise in a number of domains, such as queries using logical conjunctions ($\land$), disjunctions ($\lor$) and existential quantifiers ($\exists$), while accounting for missing edges. In this work, we propose a framework for efficiently answering complex queries on incomplete Knowledge Graphs. We translate each query into an end-to-end differentiable objective, where the truth value of each atom is computed by a pre-trained neural link predictor. We then analyse two solutions to the optimisation problem, including gradient-based and combinatorial search. In our experiments, the proposed approach produces more accurate results than state-of-the-art methods --- black-box neural models trained on millions of generated queries --- without the need of training on a large and diverse set of complex queries. Using orders of magnitude less training data, we obtain relative improvements ranging from 8% up to 40% in Hits@3 across different knowledge graphs containing factual information. Finally, we demonstrate that it is possible to explain the outcome of our model in terms of the intermediate solutions identified for each of the complex query atoms. All our source code and datasets are available online, at https://github.com/uclnlp/cqd.

Published as a conference paper at ICLR 2021
COMPLEX QUERY ANSWERING WITH NEURAL LINK PREDICTORS
Erik Arakelyan's Daniel Daza Pasquale Minervini', & Michael Cochez
UCL Centre for Artificial Intelligence. University College London, United Kingdom Vrije Universiteit Amsterdam, The Netherlands
University of Amsterdam, The Netherlands
Discovery Lab, Elsevier, The Netherlands
(erik. aarkkarrke yan. 8, mi nervini h juucl.acc. (d. dazacruz, m. cochez (vu.n. @vu.nn
ABSTRACT
Neural link predictors are immensely useful for identifying missing edges large scale Knowledge Graphs. However, it is still not clear how to use these models for answering more complex queries that arise in a number of domains, such as queries using logical conjunctions (A), disjunctions (V) and existential quantifiers (3), while accounting for missing edges. In this work, we propose a framework for efficiently answering complex queries incomplete Knowledge Graphs. We translate each query into an end-to-end differentiable objective, where the truth value of each atom is computed by a pre-trained neural link predictor. We then analyse two solutions to the optimisation problem, including gradient-based and combinatorial search. our experiments, the proposed approach produces more accurate results than state-of-the-an methods - black-box neural models trained on millions of generated queries - without the need of training on a large and diverse set of complex queries. Using orders of magnitude less training data, we obtain relative improvements ranging from 8% up 40% in Hits across dif- ferent knowledge graphs containing factual information. Finally, we demonstrate that is possible to explain the outcome our model in terms of the intermediate solutions identified for each of the complex query atoms. All our source code and datasets are available online
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 al., 2007). domain-specific ones such as Bio2RDF (Dumontier et al.) 2014) and Hetionet (Himmelstein et al.] (017) 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 's Social Graph (Noy et al.) 2019).
Neural link predictors (Nickel al. 2016) tackle the problem of identifying missing edges in large KGs. However, in many complex domains, an open challenge is developing techniques for answer- ing complex queries involving multiple and potentially unobserved edges, entities, and variables, rather than just single edges.
We focus on First-Order Logical Queries that conjunctions (A), disjunctions (V), and existential quantifiers ()). A multitude of queries can be expressed by using such operators - for instance, the query "Which drugs D interact with proteins associated with diseases t1 or t2? can be rewritten as ?D 3P.interacts(D, D. P) A aassoc(P,t, t1) V assoc( t2)]. which can be answered via sub-graph matching.
At https://githuh.coo http:///ggtuuu.coo///clllppgpp
Equal contribution, alphahetical order.

---

Published as a conference paper at ICLR 2021
"Which drugs interact with proteins associated with diseases i, or tg?"
"Which directors directed actors that
won either an Oscar Emmy?"
ND: 3P. Interacts(D. P) (assoc 4) assoc(P, e)]
?D 3A. directs((), |prize(A, Oscar) prizerA, Emmy)
Interacts
88800
directs
prize
Oscar
Emmy
A
Figure I:
Examples of First-Order Logical Queries using existential quantification (3), conjunction
(A), and disjunction (V) operators their dependency graphs D < P + ((1,42) and D <-
A + [Oscar, Emmty), respectively.
However, plain sub-graph matching cannot capture semantic similarities between entities and rela- tions, and cannot deal with missing facts in the KG. One possible solution consists computing all missing entries via KG completion methods (Getoor & Taskar 2007 De Raedt 2008 Nickel et al. 2016), but that would materialise significantly denser KG and would have intractable space and time complexity requirements (Krompaß et al., 2014).
In this work, we propose a framework for answering First-Order Logic Queries, where the query is compiled in an end-to to-eto-- differentiable function, modelling the interactions between its atoms. The truth value of each atom is computed by neural link predictor (Nickel et al., 2016) model that, given atomic query. returns the likelihood that the fact it represents holds true. We then propose two approaches identifying the most likely values for the variable nodes in query either by continuous or by combinatorial optimisation.
differentiable
Recent work on embedding logical queries on KGs (Hamilton al. 2018 Daza Cochez, 2020) Ren et al. 2020) has suggested that in order to go beyond link prediction, more elaborate architec- tures, and a large and diverse dataset with millions of queries required. In this work, we show efficient neural link predictor
that this is not the case, and demonstrate that it is possible to trained for I-hop query answering, to generalise to up to complex query structures. By doing so, produce more accurate results than state-of-the-ar models, while using orders of magnitude less training data.
Summarising, in comparison with other approaches in the literature such Query2Box (Ren al., 2020), we find that the proposed framework i) achieves significantly better or equivalent predictive accuracy 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 ex- plainable, since the intermediate results for its sub-queries and variable assignments can be used to explain any given answer.
2 EXISTENTIAL POSITIVE FIRST-ORDER LOGICAL QUERIES
Knowledge Graph G C & x triples. where each triple encodes relationship of type R between the subject & and the object the triple, where E and R denote the set all entities and relation types, respectively. One can think of Knowledge Graph as labelled multi-graph. where entities & represent nodes, and edges are labelled with relation types R. Without loss of generality, a Knowledge Graph can be represented First-Order Logic Knowledge Base, where each triple (s, p, o) denotes atomic formula p(s, o), with p E R a binary predicate and 8, 0 E & its arguments.
x E can be defined as set of pubject-predicate-ojjee (s,p, o)
Conjunctive queries are sub-class of First-Order Logical queries that existential quantification ( and conjunction (A) operations. We consider conjunctive queries Q in the following form:
C(4) A?A: AV, Vm-ei A... Aen e; = p(c, V), with (A,V,,.... 6; = P.V((V.V)) with V, V' (A, Vi...., V. +V'
where
(I)
In Eq. (I). the variable A is the target of the query, Vi,..., .,....,,,, Vm denote the bound variable nodes, while E represent the input anchor nodes. Each e; denotes a logical atom, with either one (p(c, V)) two variables (p(V, V')), and en A...A en denotes conjunction between n atoms.
2

---

Published as a conference paper at ICLR 2021
The goal of answering the logical query Q consists in finding set of entities [Q] C & such that a E [Q] iff Q[a] holds true, where [Q] is the answer set of the query Q.
As illustrated in Fig. the dependency graph of 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 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.
Example 2.1 (Conjunctive Query). Consider the query "Which drugs interact with proteins as- sociated with the disease !?". This query can be formalised as a conjunctive query Q such as ?D P..tteeactts( D, P) A assoc((; (P,)) [), where I is an input anchor node, the variable D is the target of the query, P is a bound variable node, and the dependency graph is D + P + t. The answer set [2] of Q corresponds to the set of all drugs in E interacting with proteins associated with t.
Handling Disjunctions So far we focused on conjunctive queries defined using the existential quantification (3) and conjunction (A) logical operators. Our aim is answering a wider class of logical queries, namely Existential Positive First-Order (EPFO) queries (Dalvi & Suciu (004) that in addition to existential quantification and conjunction, also involve disjunction (V). We follow
Ren et al. (020) and, without loss of generality, we transform a given EPFO query into Disjunctive Normal Form (DNF, Davey & Priestley 2002), i.e. disjunction of conjunctive queries.
Example 2.2 (Disjunctive Normal Form). Consider the following variant of query in Ex- ample 2.7 "Which drugs interact with proteins associated with the diseases t or tz?", be formalised
This query
EPFO query Q such ?D EP.interacts( D, P) A [assoc(P. P. f1) V assoc(P, (tt)) We can transform Q in the following, equivalent DNF query: ?D :
3P. [interacts(D) D, P) A assoc(P, (P,4)) V [interacts(]) D, P) A assoc(P,12).
In our framework, given DNF query Q. for each of its conjunctive sub-queries produce score for all the entities representing the likelihood that they answer that sub-query. Finally, such scores aggregated using t-conorm continuous relaxation of the logical disjunction.
3 COMPLEX QUERY ANSWERING VIA OPTIMISATION
We propose a framework for answering EPFO logical queries in the presence of missing edges. Given a query Q. we define the score of target node E & as candidate answer for query as a function of the score of all atomic queries in º. 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 E & or to virtual entity. The score of each of the query atoms is determined individually using neural link predictor (Nickel et al.) 2016). Then, the score of the query with respect to 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 query atom p(s, o), where p E R and 8,0 E E, the score for p(8, o) is computed as (p(e,,e)), where e,, e, E R are the embedding vectors of s and o, and 6p : IR* x * + [o, 1] is 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 ComplEx (Trouillon et al. 2016) regularised using a variational approximation of the tensor nuclear p-norm proposed by Lacroix al. (018).
T-Norms A I-norm T 10. 1| x [0, 1] [o, 1] is generalisation of conjunction in logic (Klement et al. 2000 2004). Some examples include the Gödel t-norm min (z, y) = min (z., y), the product r- nomm prod [r, y) x y, and the Lukasiewicz t-norm T (z. y) max z+y-1). Analogously, r-conorms are dual to t-norms for disjunctions - given a t-norm T, the complementary t-conorm is
defined by 1 (I. y) 1 T(1 xx v).
3

---

Published as a conference paper at ICLR 2021
Continuous Reformulation of Complex Queries Let Q denote the following DNF query:
2[1] : "V,...., Vm- (e) A... A em) v (et A ....A....C. A where e. = p(c, V), with V E (1.V..... ...., V & or - pV, with V.V' {A, Vi,... Vn + PER.
(2)
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 mapping from variables to entities that maximises the score of Q:
(c) T T Teh I..1 (cT Teaa
arg max A. V.V. VE
where
= Sp(e,, with E (A, V.,... P PEE Sp ev:); with V' E (A, Y FV,,ER
where and 1. denote t-norm and t-conorm continuous generalisation of the logical con- junction and disjunction, respectively - and (,, e,) E [0, 1] denotes the neural link prediction score for the atom o)s,o). We write t-norms and I-conorms as infix operators since they are both associative.
Note that, Eq. (3). the bound variable nodes V,,,.., Vn are only used through their embedding vector: compute 6p(e.. ev) we only use the embedding representation ey E R$ 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 ey E R with V {A, Vi,..., Vn) for maximising the objective in Eq. (3). namely continuous optimisation, where we optimise ey 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 Eq. (3) is by finding the variable embeddings that maximise the score of complex query. This can be formalised as the following continuous optimisation problem:
T ... Teh,) T..1 ( T
arg max
CA ey ER
(4)
where
c óy(cc. ev), with V {A, Vi..... .,. E. or e oplev, with V, v'
Vn V # P.R
In Eq. (4p we directly optimise the embedding representations e ......., ev., R of variables A, Vi...., Vm. rather than exploring the combinatorial space of variable-to-entie mappings. In this way, we can tackle the maximisation problem in Eq. 4 using gradient- based optimisation methods, such Adam (Kingma & Ba 2015). Then, after identified the optimal representation for vari- ables A, Vi,...,Ve V., we replace the query target embedding e with the embedding representations e, R of all entities E E, and the resulting complex query score compute the likelihood that such entities answer the query.
3.2 COMPLEX QUERY ANSWERING VIA COMBINATORIAL OPTIMISATION
Another way we tackle the optimisation problem in Eq. (3) is by greedily searching for a set of variable substitutions S {A + a, V1 < .1,.... Vm )m). with a, vi,-.., E E, that maximises the complex query score, in a procedure akin beam search. We do so by traversing the dependency graph of query Q and, whenever we find an atom in the form p(c. V), where p R, e is either an entity or a variable for which we already have a substitution, and is a variable for which we do not have substitution yet, we replace V with all entities in & and retain the top-k entities t E that maximise &p (C,, e₂) ie. 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.
4

---

Published as a conference paper at ICLR 2021
Example 3.1 (Combinatorial Optimisation). Consider the query "Which drugs D interact with proteins associated with disease t?" can be rewritten as: ?D: "P..ineerccs((D P) A assoc t). In order answer this query via combinatorial optimisation, we first find the top-k proteins p that are most likely to substitute the variable P in assoc( (P, 1). Then, we search for the top-k drugs d that are most likely substitute D in interacts( D. P), ending up with most k2 candidate drugs. Finally, we rank the candidate drugs d by using the query score produced by the t-norm.
Note that scoring all possible entities can be done efficiently and in single step on a GPU by replac- ing V with the entity embedding matrix. In our experiments we did not notice any computational bottlenecks due to the branching factors of longer queries. However, that could be handled by using alternate graph exploration strategies.
4 RELATED WORK
This work is closely related to approaches for learning to traverse Knowledge Graphs (Guu et al.)
2015 Das et al. 2017 2018), and more recent works on answering conjunctive queries via black- box neural models trained on generated queries (Hamilton et al. 2018 Daza & Cochez [2020] Kotnis
ct al. 2020). The main difference is that propose tractable framework for handling a substan- tally larger subset of First-Order Logic queries.
More recently, Ren et al. (222)) proposed Query2Box, neural model for Existential Positive First- Order logical queries, where queries are represented via box embeddings (Li et al. 2019). Such approaches for query answering require dataset with millions of generated queries to generalise well instance, on the FB15k-237 dataset, approx. 15 x 10a training queries for each query type used, resulting in approx. 1.2 x 10 training queries. Our framework, on the other hand, only uses a simple, state-of-the the-----ttt--tttt neural link predictor (Lacroix et al. 2018) trained on a set of 1-hop queries that is orders of magnitude smaller.
There is large body of work on neural link predictors, that learn embeddings of entities and rela- tions in KGs via simple link prediction training objective (Bordes et al. 2013 Yang et al., 2015] Trouillon et al. 2016 Lacroix et al. 2018). Due to their design, they are often evaluated for answer- ing 1-hop queries only, as their application more complex queries does not derive directly from their formulation.
Previous work has considered using such embeddings for complex query answering. by partitioning the query graph and using an ad-hoc aggregation function to score candidate answers (Wang et al. 2018), or by using a probabilistic mixture model similar to DistMult (Friedman & den Broeck 2020). In contrast, steps are implemented with t-norms and t-conorms, which are continuous relaxations of conjunc- tions and disjunctions. Such t-norms have been proposed as differentiable formulations of logical operators suitable for gradient-based learning (Serafini & d' A'Ailla Garcez 2016: Guo et al. 2016
proposed method answers query by using a single pass where aggregation
Minervini al. 2017 van Krieken et al. 2020).
Further alternatives for using embeddings from neural link predictors, such as combinatorial op- timisation, have been ruled out unfeasible (Hamilton et 2018 Daza & Cochez 2020). We show that this approach can scale well by reducing the set of possible intermediate answers, while outperforming the state-of-the-art in query answering.
The framework proposed in this paper is related to neural theorem provers (Rocktäschel & Riedel 2017 Weber al., 2019 Minervini et al., 2020a b). a differentiable relaxation of the backward- chaining reasoning algorithm where comparison between symbols is replaced by differentiable similarity function between their embedding vectors. During the reasoning process, neural theorem provers check which rules can be used for proving given atomic query. Then it is checked whether the premise of such rules is satisfied, where the premise is a conjunctive query. The procedure they use for answering conjunctions is akin to the combinatorial optimisation procedure we propose in Section 3.2 The main source of difference is how atomic queries are answered - we use the Com- plEx neural link predictor (Trouillon et al.) 2016), while neural theorem provers the maximum similarity value between a given atomic query and all facts in the Knowledge Graph, which has linear complexity in the number of triples in the graph.
5

---

Published as a conference paper at ICLR 2021
0-000
1p
2p
3p
pi ip up
2u
Anchor node
Variable node
Query target node
Disjunction
Query structures considered our experiments, as proposed by Ren et al. (0220) the naming of each query structure corresponds to projection (p), intersection (i), and union (u), and reflects how they were implemented in the Query2Box model (Ren et al.) 2020). An example of pi query is ?T 3V-((a, V), (V, T), where and b are anchor nodes, V is variable node, and I' is the query target node.
Figure 2:
Table I: Number of queries in the datasets used for evaluation of query answering performance. Others indicates the number of queries for each of the remaining types.
Training
Validation
Test
Dataset
1p
Others
1p
Others
1p
Others
FB 15k
273,710
273,710
59,097
8,000
67,016
8,000
FB15K-237
149,689
149,689
20,101
5,000
22,812
5,000
NELL995
107,982
107,982
16,927
4,000
17,034
4,000
EXPERIMENTS
We described method to answer a query by decomposing it into a continuous formulation, which refer to as Continuous Query Decomposition (CQD). In this section demonstrate the effective- ness of CQD on the task of answering complex queries that cannot be answered using the incomplete KG, and report experimental results for continuous optimisation (CQD-CO, Section 3.1 and beam search (CQD-Beam, Section 3.2). We also provide qualitative analysis of how our method can be used obtain explanations a given complex query answer. For the sake of comparison, we use the same datasets and evaluation metrics as Ren et al. (2020).
DATASETS
Following Ren et al. 2020). evaluate our approach on FB15k (Bordes al.) 2013) and FB 7B15k-237 Touutanova & Chen 2015) two subset of the Freebase knowledge graph and NELL995 Xiong et al. 2017). KG generated by the NELL system (Mitchell et al. 2015). In order to compare with previous work query answering, we use the queries generated by Ren al. (2020) from these datasets. Dataset statisties are detailed in Table We consider total of 9 query types, including atomic queries, and 2 query types that contain disjunctions the different query types are shown in Fig. 2 Note that in our framework,
neural link predictor is only trained on atomic queries, while the evaluation is carried out on the complete set of query types in Fig. 2
Note that each query in Table I can have multiple answers, therefore the total number of training instances can be higher. For atomic queries (of type 1p), this number is equal the number of edges in the training graph. Other methods like GQE (Hamilton et al., 2018) and Q2B (Ren et al. 2020) require dataset with more query types. As example, the FB15k dataset contains approximately 960k instances for 1p queries. When adding 2p. 3p, 2i, and queries employed by GQE and Q2B during training, this number increases 65 million instances.
5.2 MODEL DETAILS
To obtain embeddings for the query answering task, we use ComplEx (Trouiloon et al. 2016) a variational approximation of the nuclear tensor p-norm for regularisation (Lacroix al. 2018). We fix a learning rate of 0.1 and use the Adagrad optimiser. We then tune the hyperparameters of ComplEx on the validation set for each dataset, via grid search. We consider ranks (size of the

---

Published as a conference paper at ICLR 2021
Table 2: Complex query answering results (H@3) across all query types; results for Graph Query
Embedding (GQE, Hamilton et al. 2018) and Query2Box (Ren et al. 2020) are from Ren et al. 2020
Method
Avg
1p
2p
3p
2i
3i
ip
pi
2u
up
FB15k
GQE
0.384
0.630
0.346
0.250
0.515
0.611
0.153
0.320
0.362
0.271
Qucry2Box
0,484
0.786
0,413
0.303
0.593
0.712
0.211
0.397
0.608
0.330
CQD-CO
0.576
0.918
0.454
0.191
0.796
0.837
0.336
0.513
0.816
0.319
CQD-Beam
0.680
0.918
0.779
0.577
0.796
0.837
0.375
0.658
0.839
0.345
FB15k-237
GQE 0.230
0,405
0.213
0.153
0.298
0.411
0.085
0.182
0.167
0.160
Query2Box
0.268
0.467
0.240
0.186
0.324
0.453
0.108
0.205
0.239
0.193
CQD-CO
0.272
0.512
0.213
0.131
0.352
0.457
0.146
0.222
0.281
0.132
CQD-Beam
0.290
0.512
0.288
0.221
0.352
0.457
0.129
0.249
0.284
0.121
NELL995
GQE 0.248
0.417
0.231
0.203
0.318
0.454
0.081
0.188
0.200
0.139
Query2Box
0.306
0.555
0.266
0.233
0.343
0.480
0.132
0.212
0.369
0.163
CQD-CO 0.368
0.667
0.265
0.220
0.410
0.529
0.196
0.302
0.531
0.194
CQD-Beam
0.375
0.667
0.350
0.288
0.410
0.529
0.171
0.277
0.531
0.156
embedding) in (100, 200, 500, 1000), batch size in (100, 1000). and regularisation coefficients
in the interval [10-4, 0.5].
For query answering we experimented with the Gödel and product t-norms select the best t-norm for each query type according to the best validation accuracy. For CQD-CO, we optimise variable and target embeddings with Adam, using the same initialisation scheme Lacroix et al. (018)), with an initial learning rate of 0.1 and a maximum of 1,000 iterations. In practice, we observed that the procedure usually converges in less than 300 iterations. For CQD-Beam, the beam size & E (2 23,,.... 28] } is found held-out validation set.
5.3 EVALUATION
As in Ren al. 2020), for each test query, assign such score for ranking such entities. We then compute the Hits at (H ())3) metric, which measures the frequency with which the correct answer is contained in the top three answers in the ranking. Since a query can have multiple answers, we use the filtered setting (Bordes et al. 2013), where we filter other correct answers from the ranking before calculating the H@3. As baselines we use two recent state-of-the-art models for complex query answering, namely Graph Query Embedding (GQE, Hamilton al. 2018) and Query2Box (Q2B, Ren al. 2020).
every entity in the graph, and use
5.4 RESULTS
detail the results of H@3 for different query types in Table We observe that, on average, CQD produces more accurate results than GQE and Q2B, while using orders of magnitude less training data. In particular, combinatorial optimisation in CQD-Beam consistently outperforms the baselines across all datasets.
The results for chained queries (2p and 3p) show that CQD- is effective, even when increasing the length of the chain. The most difficult case corresponds 3p queries, where the number of candidate variable substitutions increases due to the branching factor of the search procedure.
We also note that having more variables does not always translate into performance for CQD- CO: it yields the best ranking scores for ip queries on FB15k-237, and for ip and pi queries for NEL.1995, and both such query types contain two variables.

---

Published as a conference paper at ICLR 2021
Query: 2G BM perform; M) genrel,, G)
"In what genres of movies did Martin Lawrence appear?"
G
Rank
Correctness
Druma
Do the Right Thing
Comedy
4
?G BM www.ppeffomMM..... M) genre(M, ()
Crime Fiction
7
Action
2
National Security
Thriller
Crime Fiction
perform
genre
ML
M
G
Comedy
Nutty
Romantic Com.
Romance Film
Query: 30 3C nationaaliyy C) memberOf(C, 0)
"What international organisations contain the country of nationality of Thomas Aquinas?"
Rank
Correctness
NATO
United States
OECD
2
?0: DC. www..nniioiiltyta........ C) member(,,
NATO
3
United Kingdom
OFCD
4
EU
5
nationality
member
OECD
6
Germany
EU
7
WTO
Figure 3: Intermediate variable assignments and ranks for two example queries, obtained with CQD- Beam. Correctness indicates whether the answer belongs to the ground-truth set answers.
The results presented in Table 2 were obtained with a rank of 1,000, as they produced the best performance in the validation set. We present results for other values of the rank in Appendix [A] where we observe that even with a rank of 100, CQD still outperforms baselines with a larger embedding size. Furthermore, Appendix B we report the number of seconds required to answer each query type, showing that CQD-Beam requires less than 50ms for all considered queries.
We also experimented with a variant of CQD- -OD-Beam that uses DistMult (Yang et al. (015)) as the link predictor results are reported in Appendix C As expected, results when using DistMult are slightly less accurate than when using ComplEx, while still being more accurate than those produced by GQE and Q2B.
5.5 EXPLAINING ANSWERS TO COMPLEX QUERIES
useful property of our framework is its transparency when computing scores for distinct atoms in query. Unlike GQE and Q2B two neural models that encode query into vector via set of non-linear transformations our framework is able to produce an explanation for given answer in terms of intermediate variable assignments.
Consider the following test query from the FB15k-237 knowledge graph: "In what genres of movies did Martin Lawrence appear?" This query be formalised as ?G 3M. htlffppefrmmm/mmmmm (MI,, M) A genre M,, G), where MI. is an anchor node representing Martin Lawrence. The ground truth answers to this query are 7 genres, including Drama, Comedy, and Crime Fiction. In Fig, 3 we show the intermediate assignments obtained when using CQD-Beam, to the variable M in the query, and the rank for each combination of movie M and genre G. We note that the assignments the variable M are correct, as these are movies where Martin Lawrence appeared. Furthermore, these intermediate assignments lead to correct answers in the first seven positions of the ranking, which correctly belong to the ground-truth set of answers.
In a second example, consider the following query: "What international organisations contain the country of nationality of Thomas Aquinas?" Its conjunctive form is ?0 IC..naiinaaiityTT C) A memberOf(C. O), where TA an anchor node representing Thomas Aquinas. The ground-truth answers to this query are the Organisation for Economic Co-operation and Development (OECD), the European Union (EU), the North Atlantic Treaty Organisation (NATO), and the World Trade Organisation (WTO). As shown in Fig. 3 CQD-Beam yields the correct answers in the first four positions in the rank. However, by inspecting the intermediate assignments, we note that such correct answers produced by incorrect (although related) intermediate assignment, since the country
8

---

abs/ Published as a conference paper at ICLR 2021
of nationality of Thomas Aquinas is Italy. By inspecting these decisions thus identify failure modes of our framework, even when it produces seemingly correct answers. This in contrast with other neural black-box models for complex query answering outlined in Section 4 where such an analysis is not possible.
6 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 framework, answering a complex query is reduced to answering each of its sub-queries, and aggre- gating the resulting scores via t-norms. The benefit of the method is that we only need train 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 state-of-the-art complex query answering methods incomplete Knowledge Graphs.
ACKNOWLEDGEMENTS
This research was supported by the European Union's Horizon 2020 research and innovation pro- gramme under grant agreement no. 875160. This project was partially funded by Elsevier's Discov- ery Lab, Finally, we thank NVIDIA for GPU donations.
REFERENCES
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.
Antoine Bordes, Nicolas Usumier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, pp. 2787-2795, 2013.
Nilesh N. Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. In VLDB, pp- 864-875. Morgan Kaufmann, 2004.
Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. EACL (l), pp. 132-141. Association for Computational Linguistics, 2017.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, 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.
Brian A. Davey and Hilary A. Priestley. Introduction to Lattices and Order, Second Edition. Cam- bridge University Press, 2002.
Daniel Daza and Michael Cochez. Message passing query embedding. In ICML Workshop Graph Representation Learning and Beyond, 2020. URL
2002. 02406
Lue De Raedt. Logical and relational learning. Cognitive Technologies. Springer, 2008
Michel Dumontier, Alison Callahan, Jose Cruz-Toledo, Peter Ansell, Vincent Emonet, François Belleau, and Arnaud Droit. Bio2RDE 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 Proceedings, pp. 401-404. CEUR-WS.org 2014.

---

Published as a conference paper at ICLR 2021
Tal Friedman and Guy Van den Broeck. Symbolic querying of vector spaces: Probabilistic databases meets relational embeddings. UAI, volume 124 Proceedings of Machine Learning Research, pp. 1268-1277. AUAI Press, 2020.
Lise Getoor and Ben Taskar. Introduction statistical relational learning. The MIT Press, 2007.
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.
Kelvin Guu, John Miller, and Percy Liang. Traversing knowledge graphs vector space. In EMNLP. pp. 318-3118-2033 327. The Association for Computational Linguistics, 2015.
William L. Hamilton, Payal Bajaj. Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In NewrIPS, pp. 2030-2041, 2018.
Daniel S. Himmelstein, Antoine Lizee, Christine Hessler, Leo Brueggeman, Sabrina Chen, Dex- ter Hadley, Ari Green, Pouya Khankhanian, and Sergio E. Baranzini. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. bioRxiv, 2017. doi: 10. 101/0/9/9. URL ht http://wwwwwwww.x...c////oo
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
Erich-Peter Klement, Radko Mesiar, and Endre Pap. Triangular Norms, volume 8 Trends in Logic. Springer, 2000.
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.
Bhushan Kotnis, Carolin Lawrence, and Mathias Niepert. Answering complex queries in knowledge graphs with bidirectional sequence encoders. CoRR, abs/2004.02556. 2020.
Denis KrompaB, Maximilian Nickel, and Volker Tresp. Querying factorized probabilistic triple databases. In International Semantic Web Conference (2), volume 8797 Lecture Notes in Com- puter Science, pp. 114-129. Springer, 2014.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. /CML, volume 80 Proceedings of Machine Learning Research, pp. 2869 2878. PMLR, 2018.
Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smoothing the geometry of probabilistic box embeddings. ICLR. OpenReview.net, 2019.
George A. Miller. WORDNET: a lexical database for english. HLT. Morgan Kaufmann, 1992.
Pasquale Minervini, Thomas Demeester, Tim Rocktäschel, and Sebastian Riedel. Adversarial sets for regularising neural link predictors. In UAI. AUAI Press, 2017.
Pasquale Minervini, Matko Bosnjak, Tim Rocktäschel, Sehastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. In AAAI, pp. 5182-5190. AAAI Press, 2020a.
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies in end-to-end differentiable proving. In ICML, Proccedings of Ma- chine Learning Research. PMLR, 2020b.
Tom M. Mitchell, William W. Cohen, Estevam R. Hruschka Jr., Partha Pratim Talukdar, Justin Bet- teridge, Andrew Carlson, Bhavana Dalvi Mishra, Matthew Gardner, Bryan Kisiel, Jayant Krish- namurthy, Ni Lao, Kathryn Mazaitis, Thahir Mohamed, Ndapandula Nakashole. Emmanouil A. Platanios. Alan Ritter, Mehdi Samadi, Burr Settles, Richard Wang, Derry Wijaya, Abhinav Gupta, Xinlei Chen, Abulhair Saparov, Malcolm Greaves, and Joel Welling. Never-ending learn- ing. In AAAI, pp. 2302-2310. AAAI Press, 2015.
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.
10

---

Published as a conference paper at ICLR 2021
Natalya Fridman Noy, Yuqing Gao, Anshu Jain, Anant Narayanan, Alan Patterson, and Jamie Taylor. Industry-scake knowledge graphs: lessons and challenges. Commun. ACM, 62(8):36 43, 2019.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In 8th International Conference Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
https://openreview net Beee:/oooummmidBBg44k3s.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In NIPS, pp. 2017.
Luciano Serafini and Artur S. Avili Garcez. Logic tensor networks: Deep learning and logical reasoning from data and knowledge. CoRR, abs/1606.04422, 2016. URL http://arxiv.
arg/abs/De 1606 04422
Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: a core of semantic knowledge. In WWW, pp. 697-706. ACM, 2007.
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 Compositionaliit, pp. 57-66, Beijing, China, July 2015. Association for Computational Lin- guistics. doi: 10.1663/111115-40077 URL httpps://wwtt hwtp://wwwwwwwww......... wwg..tthoooattyyy.
W15- 4007
Théo Trouillon, Johannes Welbl, Sehastian Riedel, féric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In ICML, volume 48 of JMLR Workshop and Con- ference Proceedings, pp. 207 2071-2080. JMLR.org, 2016.
Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing Differentiable Fuzzy Implications. In Proceedings of the 17th International Conference on Principles of Knowl- edge Representation and Reasoning, pp. 893-903, 9 2020. doi: 10.24963/lr.2220/92 URL
2...1....93366 2020/92
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 Con- ference (1), volume 11136 of Lecture Notes in Computer Science, pp. 513-529. Springer, 2018.
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 ACI. (1), pp- 6151-6161. Association for Computational Linguistics, 2019.
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 Linguis- tics, 2017.
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.

---

Published as a conference paper at ICLR 2021
A INFLUENCE OF THE EMBEDDING SIZE ON THE RESULTS
Table 3: Complex query answering results (H@3) across all query types, for different rank (em-
bedding size) values results for Graph Query Embedding (GQE, Hamilton et al. 2018) and Query2Box (Ren et al. 2020) are from Ren et al. (202)).
Method
Rank
1p
2p
3p
2i
ip
pi
2u
up
FB15k
GQE
800
0.630
0.346
0.250
0.515
0.611
0.153
0.320
0.362
0.271
Query2Box
400
0.786
0.413
0.303
0.593
0.712
0.211
0.397
0.608
0.330
100
0.893
0.162
0.076
0.773
0,818
0.118
0.344
0.493
0.073
0.906
0.257
0.092
0.785
0.828
0.210
0.426
0.753
0.110
CQD-CO
500
0.912
0.345
0.123
0.772
0.817
0.257
0.454
0.795
0.206
1000
0.918
0.454
0.191
0.796
0.837
0.336
0.513
0.816
0.319
100
0.893
0.746
0.557
0.773
0,818
0.357
0.669
0.689
0.313
200
0.906
0.770
0.585
0.785
0,828
0.373
0.679
0.815
0.357
CQD-Beam
500
0.912
0.759
0.580
0.772
0.817
0.372
0.650
0.831
0.351
1000
0.918
0.779
0.584
0.796
0.837
0.377
0.658
0.839
0.355
FB15K-237
GQE
800
0.405
0.213
0.153
0.298
0,411
0.085
0.182
0.167
0.160
Query2Box
400
0.467
0.240
0.186
0.324
0.453
0.108
0.205
0.239
0.193
100
0.493
0.162
0.076
0.311
0,415
0.118
0.199
0.238
0.073
200
0.500
0.187
0.092
0.329
0.439
0.128
0.204
0.254
0.103
CQD-CO
500
0.508
0.210
0.123
0.346
0.454
0.142
0.216
0.273
0.119
1000
0,512
0,213
0.131
0.352
0.457
0.146
0.222
0.281
0.132
100
0.493
0,256
0.207
0.311
0.415
0.119
0,234
0.254
0.121
200
0.500
0.272
0.216
0.329
0.439
0.122
0.244
0.264
0.127
CQD-Beam
500
0.508
0.280
0.216
0.346
0.454
0.127
0.257
0.280
0.128
1000
0.512
0.279
0.219
0.352
0.457
0.129
0.249
0.284
0.128
NELL995
GQB
800
0.417
0.231
0.203
0.318
0.454
0.081
0.188
0.200
0.139
Query2Box
400
0.555
0.266
0.233
0.343
0.480
0.132
0.212
0.369
0.163
100
0.647
0.234
0.145
0.389
0.508
0.165
0.283
0.465
0.126
200
0.658
0.238
0.164
0.401
0.524
0.172
0.282
0.502
0.148
CQD-CO
500
0.665
0.261
0.208
0.406
0.525
0.187
0.293
0.523
0.171
1000
0.667
0.265
0.220
0.410
0.529
0.196
0.302
0.531
0.194
100
0.647
0.333
0.296
0.389
0,508
0.160
0.293
0.469
0.150
200
0.658
0.335
0.292
0.401
0.524
0.162
0.290
0.508
0.146
CQD-Beam
500
0.665
0.348
0.296
0.406
0,525
0.166
0.291
0.527
0.149
1000
0.667
0.343
0.297
0.410
0.529
0.168
0.283
0.536
0.157
In Table B we report results for CQD-CO (Section 3.1 and CQD-Beam (Section 3.2 for different
rank (embedding size) values. We can see that the model produces very accurate results even with significantly fewer parameters.
12

---

Published as a conference paper at ICLR 2021
B TIMING EXPERIMENTS
Time (seconds) required for answering each query type FB15k
Method
(seconds queryy
0.08
-25
COD-Beam
0.07
0.02
0.01
0.00
2u
Types of queries
Figure 4: Number of seconds required by Q2B (Ren et al. 2020) and CQD-Beam (Section 3.2 for answering each query type in FB
(seconds) required for answering each query type FB15k-237
0.012
Method
Time (seconds) per query
028
0.010
CQD-Beam
0.008
0.004
0.002
2p 3p
21
ip
pi
Types queries
Figure 5: Number of seconds required by Q2B (Ren et al. 2020) and CQD-Beam (Section 3.2 for answering each query type in FB15K-237.
In Fig. and Fig. we report the time (seconds) required by Q2B Ren et al. 2020) and CQD-Beam (Section for for answering each query type, aggregated over FB15k, FB15k-237, and NELL. We can see that, in CQD-Beam, the main computation bottleneck are multi-hop queries, since the model is required invoke the neural link prediction model for each step of the chain to obtain the top-k candidates for the next step in the chain.
13

---

Published as a conference paper at ICLR 2021
C
DISTMULT EXPERIMENTS
Table 4: Complex query answering results (H@3) across all query types, for two different neural
link prediction models, namely ComplEx (Truillonn al. 2016) and DistMult Yang et al. 2015).
Method
Model
1p
2p
3p
2i
3i
ip
pi
2u
up
FB15k
ComplEx
0.918
0.779
0.584
0.796
0.837
0.377
0.658
0.839
0.355 0.355
CQD-Beam
DistMult
0.869
0.761
0.581
0.778
0.824
0.369
0.608
0.822
FB15K-237
ComplEx 0.512
0.279
0.219
0.352
0.457
0.129
0.249
0.284
0.128
CQD-Beam
DistMult
0.485
0.277
0.210
0.332
0.443
0.117
0.224
0.281
0.123
NELL995
ComplEx 0.667
0.343
0.297
0.410
0.529
0.168
0.283
0.536
0.157
CQD-Beam
DistMult
0.642
0.348
0.297
0.392
0.517
0.
0.260
0.502
0. 169
In Table 4 we report the results for CQD-Beam with two different neural link prediction models, namely ComplEx (Trouillon et al. 2016) and DistMult (Yang et al.) 2013). Both models were trained using the loss and regulariser proposed by Lacroix et al. (2018), and their hyperparameters were tuned according to their performance in the validation set; in both cases, the embedding size set to 1, 1,000. As expected, CQD-Beam with DistMult produces slightly less accurate results than with ComplEx, while still yielding more accurate results than the Q2B and GQE baselines.
14


Reviews:
[{"review_id": "w_unFNZGW2i", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes Continuous Query Decomposition (CQD), an approach for answering Existential Positive First-Order (EPFO)\nqueries over incomplete knowledge graphs exploiting a neural link predictor for 1-hop-only queries.\nEntities are embedded in a low dimensional space and entity vectors are used to compute the score of query atoms that\nare then combined using a t-norm for conjunction and t-conorm for disjunction.\nAnswers to queries are found either with continuous optimisation by gradient descent to find embeddings for query variables\nor combinatorial optimisation where top-k entities for query variables are looked for yielding a beam search.\nCQD is compared with Graph Query Embedding (GQE) and Query2Box over three datasets on a large number of queries.\nThe result show that CQD outperforms the baselines on Hit@3 on average.\nCQD also offers the possibility of explaining the results of queries by showing the top scoring entities for query variables and the score of atoms.\n\nCQD tackles the difficult problem of answering queries that are beyond simple 1-hop completion queries. It improves\nover previous work which need to train the model over a large number of queries (Hamilton et al., 2018;Daza & Cochez, 2020;\nRen et al., 2020) and do not consider disjunctive queries (Hamilton et al., 2018; Daza & Cochez, 2020).\nThese advantages are obtained by not embedding the query into a low dimensional space but using continuous or combinatorial\noptimization to answer queries, considering the query as a formula in fuzzy logic and applying t-norms and t-conorms.\nWhile the use of fuzzy logic in query answering is not new, they way in which it is combined with entity embeddings and\nneural link predictors is original to the best of my knowledge.\n\nThe fact that queries are not embedded (and so learning does not need large numbers of queries) is a strong point of CQD,\nwith competing methods (Hamilton et al., 2018;Daza & Cochez, 2020; Ren et al., 2020) requiring many queries for tuning the query embeddings.\nSince queries are not embedded, the results of CQD are also easier to explain. \n\nThe experiments are sufficiently extensive to support the claim of the paper that CQD is also outperforming competitors in \nterms of the quality of solutions. However, the authors should justify why they used embedding size 500 for their methods\nand 400 for the baselines.\n\nFrom a technical point of view the article seems sound but the authors say that \"Then, after we identified the optimal \nrepresentation for variables $A, V_1, \\ldots  V_m$, we replace the query target embedding $e_A$ with the embedding \nrepresentations $e_c \\in R^k$ of all entities $c \\in E$, and use the resulting complex query score to compute the \nlikelihood that such entities answer the query.\"\nIn this way the authors throw away vector $e_A$ that may have information about the problems, isn't there a method to\nexploit the information in $e_A$?\n\nI have a few remarks about the presentation:\nCitation Raedt, 2008 should be De Raedt, 2008.\nIn Figure 1 the edges of the graphs have the opposite direction with respect to the caption and main text.\nPage 6: \"we only make use of type 1-chain queries to train the neural link\npredictor\": do the authors mean 1-hop queries? 1-chain appears here for the first time.\n\"In all cases, we use a rank of 500.\": for rank do the authors mean the embedding size? This should be clarified\nPage 7: \"Since\na query can have multiple answers, we implement a filtered setting, whereby for a given answer, we\nfilter out other correct answers from the ranking before computing H@3.\": this sentence is not clear. Does it mean\nthat answers that follow from the KG without completion are removed from the ranking?\n\n----After reading the other reviews and the authors' comments, I still think the paper is excellent and should be accepted.", "extra_scores": {}, "extra_text": {}}, {"review_id": "KimDoIp84Rp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThis paper proposes Continuous Query Decomposition (CQD) a novel method for evaluating complex queries over incomplete KGs. Each variable of a logical query (involving existential quantifiers, conjunctions and disjunctions) is mapped to an embedding. A link predictor, trained on single edge prediction, is used to score the atomic query involving the variable. The full query is evaluated using continuous versions of the logical operators and gradient-based or combinatorial optimization.\nEvaluating complex logical queries on (necessarily incomplete) KGs and other graph-structured data is an important problem for data mining purposes. The paper proposes an elegant and effective method. \n\nStrong points\nElegant, efficient solution.\nSOTA results.\nProvides aspects of explainability, although this could be discussed and illustrated better.\n\nDetailed comments\n- What is particularly important/challenging about EPFO queries, beyond existential and conjunctive ones? Obviously it is an extension that covers more FOL, but a qualitative discussion would help the reader, particularly with respect to applications to KGs.\n- Could you talk more, give more insights about the 8 complex queries types? Why are they important?\n- The query “What international organisations contain the country of nationality of Thomas Aquinas?” sounds really artificial. Maybe there is a better example involving entities and relations, similar to the drugs one?\n- Could you say a bit more with respect to how the KG incompleteness is accounted for in the evaluation?\n- The paper mentions “.. 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.” It would be great to articulate this more for sake of providing context and motivation.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Fm1mCn1WNX4", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper aims to answer complex queries on knowledge graphs. Different from previous methods that aim to embed the queries, the method views the query answering problem as an optimization / search problem where the goal is to find the most plausible entities on the reasoning path. The merits are that the method only needs to train on 1 hop path queries (link prediction), saving the effort of training on complex queries as in previous work, and proposes two solutions, which both achieve nice results on standard multi-hop reasoning benchmarks. It also demonstrates interpretability of the model by showing some examples of the intermediate entities found in the reasoning path when answering a complex multi-hop query.\n\nI think the paper is clear and easy to follow. I have some questions regarding the two methods. For the first method, continuous optimization in sec 3.1, what is the difference between this method and the previous works GQE, Q2B, etc. apart from different neural link predictors? Especially for path queries, e.g., given a two hop query, $(\\text{Obama}, \\text{BornIn}, V_1)\\wedge(V_1, \\text{CapitalOf}, V_2)$, then the optimal $e_{V_1}$ will be $e_{Obama}+e_{BornIn}$, because the distance will be 0, and $\\phi_p$ will be 1 (here it assumes TransE model, and of course it can be generalized to DisMult, ComplEx, etc.). Then the first formulation is in essence very much similar to GQE, because GQE/Q2B also models $\\mathbf{e}_{V_1}$ in the exact same way and the difference only lies in (1) you use ComplEx (2) t-norm modeling of conjunction? However, it seems that t-norm demonstrates less expressiveness for modeling conjunction because both GQE/Q2B models conjunction using a MLP with additional learnable parameters, which can also approximate t-norm and even be more adaptive depending on the training queries/KG.\nFor the second method, the time complexity seems exponential with respect to the number of hops. For a m hop query, and each step you keep the top-k, then do you end up with $k^m$ entities?\n\nAdditional questions:\n1. How did you calibrate the output of ComplEx so that $\\phi_p(e_s, e_o)$ is in [0,1]? Better to add more details on neural link predictors. \n2. Some ablation studies that use different t-norm and t-conorm other than the Godel and product may make the argument stronger.\n3. There exists a tradeoff between the inference time and training queries. For GQE/Q2B, they can leverage complex queries to train the conjunction operator (MLP), so that during inference, there is no need to do any optimization. But for the proposed method, it saves the effort of training on complex queries, however, during inference, the method needs an online optimization process to instantiate the variables on the path. Especially for CQD-CO, the authors mention that they need to optimize online for 1000 iterations, which is too expensive for answering a query. Can you list the inference time of both models (continuous, combinatorial) and compare it with GQE/Query2box?\n4. For 1p performance, it is equivalent to the performance of ComplEx on link prediction right?\n5. The table 3 is confusing, why are the numbers (e.g., 5.5, 46.76) larger than 1, I think the model normalized the output of $\\phi$ to [0,1]?\n6. The proposed two optimization methods are independent of neural link predictors. Can you use the same neural link predictor for your models and GQE for fair comparison? You can train a TransE model for the neural link predictor, and accordingly define $\\phi_p$, then it will be clear to show whether the gain comes from a different neural link predictor (TransE vs ComplEx), or comes from the t-norm and the two optimization methods. And of course another choice is the other way around, e.g., use the ComplEx version of GQE and make the same comparison.\n\nMinor points to fix:\n1. In the method section, bold $\\mathbf{e}$ denotes vector embedding while normal $e$ denotes a logic formula, which is subtle and confusing. Authors can change the notation of one of them.\n2. Also, the notation $e_i^j$ is abused, in Eq. 2, it represents a logic formula, however, in Eq. 3, it represents the output of $\\phi_p$, which is a scalar.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CGldkk2zr0f", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper attempt to answer conjunctive queries that are in the form of a chain of facts bound together with unobserved variables. The authors suggest that you can use any relational learning method to embed entities and relations in a k-dimensional space and then use the t-norm in order to create a loss function that will be used in order to find the result of the query.  The paper investigates continuous optimization through stochastic gradient descent and a greedy method for combinatorial optimization. The results demonstrate that the greedy optimization method performs better. In addition, they claim that their method outperforms other methods with the advantage of using less training data.\n\nHere are some comments \n* I think the authors cover the relevant work sufficiently \n* The idea is very simple and builds upon other work that is well studied and well understood by the community\n* I think that there is an excessive mathematical formalism that is a bit unnecessary. There is no reason for that, the fact that the idea is very simple does not mean that we have to add extra formalism.\n* In terms of generalization, I think it is very interesting that the users train only on 1-hop  queries and evaluate up to 5-hop. In the introduction, the authors claim they use less data than the other methods, but they don’t make it very clear in the experimental section. I think they need to be more explicit about that. They need to clarify that less data means just the 1-hop queries\n* I have two reservations about the paper. I suspect that part of the success of their approach is the ComplEx embeddings. I would appreciate an ablation study with at least one more method for relational learning, let’s say TransE to see how sensitive it is on the embeddings. To be fair the authors study in depth the performance of their algorithm in other variations, such as the length of the chain\n* The other concern is about timing results. It would help to know how the whole algorithm compares in terms of time to answer the query compared to the others. I think it is of particular interest the difference between the two optimization techniques. I suspect that the greedy one might be two slow for longer chains. From the preliminary analysis, it seems to grow as k^d where k is the width of the beam per relation and d is the length of the chain.\n\nIn general, I think it is a very practical paper\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously agree that this paper is a strong accept; it makes important progress in developing our ability to query relational embedding  models.
Decision: Accept (Oral)