Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: Summary: 
This 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.
Evaluating 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. 

Strong points
Elegant, efficient solution.
SOTA results.
Provides aspects of explainability, although this could be discussed and illustrated better.

Detailed comments
- 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.
- Could you talk more, give more insights about the 8 complex queries types? Why are they important?
- 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?
- Could you say a bit more with respect to how the KG incompleteness is accounted for in the evaluation?
- 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.


review_title: Complex logical query evaluation with link predictors

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

I 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.
For 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?

Additional questions:
1. 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. 
2. Some ablation studies that use different t-norm and t-conorm other than the Godel and product may make the argument stronger.
3. 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?
4. For 1p performance, it is equivalent to the performance of ComplEx on link prediction right?
5. 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]?
6. 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.

Minor points to fix:
1. 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.
2. 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.

review_title: A new method on reasoning on KG, nice empirical results

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: 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.

Here are some comments 
* I think the authors cover the relevant work sufficiently 
* The idea is very simple and builds upon other work that is well studied and well understood by the community
* 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.
* 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
* 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
* 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.

In general, I think it is a very practical paper

review_title: Surprisingly simple idea that seems to work

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: The paper proposes Continuous Query Decomposition (CQD), an approach for answering Existential Positive First-Order (EPFO)
queries over incomplete knowledge graphs exploiting a neural link predictor for 1-hop-only queries.
Entities are embedded in a low dimensional space and entity vectors are used to compute the score of query atoms that
are then combined using a t-norm for conjunction and t-conorm for disjunction.
Answers to queries are found either with continuous optimisation by gradient descent to find embeddings for query variables
or combinatorial optimisation where top-k entities for query variables are looked for yielding a beam search.
CQD is compared with Graph Query Embedding (GQE) and Query2Box over three datasets on a large number of queries.
The result show that CQD outperforms the baselines on Hit@3 on average.
CQD also offers the possibility of explaining the results of queries by showing the top scoring entities for query variables and the score of atoms.

CQD tackles the difficult problem of answering queries that are beyond simple 1-hop completion queries. It improves
over previous work which need to train the model over a large number of queries (Hamilton et al., 2018;Daza & Cochez, 2020;
Ren et al., 2020) and do not consider disjunctive queries (Hamilton et al., 2018; Daza & Cochez, 2020).
These advantages are obtained by not embedding the query into a low dimensional space but using continuous or combinatorial
optimization to answer queries, considering the query as a formula in fuzzy logic and applying t-norms and t-conorms.
While the use of fuzzy logic in query answering is not new, they way in which it is combined with entity embeddings and
neural link predictors is original to the best of my knowledge.

The fact that queries are not embedded (and so learning does not need large numbers of queries) is a strong point of CQD,
with competing methods (Hamilton et al., 2018;Daza & Cochez, 2020; Ren et al., 2020) requiring many queries for tuning the query embeddings.
Since queries are not embedded, the results of CQD are also easier to explain. 

The experiments are sufficiently extensive to support the claim of the paper that CQD is also outperforming competitors in 
terms of the quality of solutions. However, the authors should justify why they used embedding size 500 for their methods
and 400 for the baselines.

From a technical point of view the article seems sound but the authors say that "Then, after we identified the optimal 
representation for variables $A, V_1, \ldots  V_m$, we replace the query target embedding $e_A$ with the embedding 
representations $e_c \in R^k$ of all entities $c \in E$, and use the resulting complex query score to compute the 
likelihood that such entities answer the query."
In this way the authors throw away vector $e_A$ that may have information about the problems, isn't there a method to
exploit the information in $e_A$?

I have a few remarks about the presentation:
Citation Raedt, 2008 should be De Raedt, 2008.
In Figure 1 the edges of the graphs have the opposite direction with respect to the caption and main text.
Page 6: "we only make use of type 1-chain queries to train the neural link
predictor": do the authors mean 1-hop queries? 1-chain appears here for the first time.
"In all cases, we use a rank of 500.": for rank do the authors mean the embedding size? This should be clarified
Page 7: "Since
a query can have multiple answers, we implement a filtered setting, whereby for a given answer, we
filter out other correct answers from the ranking before computing H@3.": this sentence is not clear. Does it mean
that answers that follow from the KG without completion are removed from the ranking?

----After reading the other reviews and the authors' comments, I still think the paper is excellent and should be accepted.
review_title: nice improvement of the SOTA

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)