Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes a method to answer complex logical queries in large incomplete knowledge bases (KB). Specifically it considers the class of existential first-order logical queries (EPFO) which includes the logical and, or and existential operator.  The key contribution of this paper is to represent sets of entities via regions, more specifically as boxes or hyper-rectangles. This is well motivated because such logical queries often involves working over sets of entities at once and involves applying set based operators. Previous work which represented queries as a point in vector space are not well suited for these queries.
Instead, this paper models sets of entities as boxes or axis-aligned hyper-rectangles which is parameterized by two vectors \in \mathbb{R}^{n] denoting the center and the offset respectively. Boxes can also be understood to represent all the points in it (measure by element-wise comparison with the min and max coordinate). Handling the queries require projection and intersection operation. They are defined by simple addition operation (which guarantees the boxes grow in size, due to positive offset values) and a shrinkage function to denote intersection that guarantees the output area is smaller and is inside the set of boxes.
For handling disjunctive queries, they make the clever trick of converting queries to DNF form so that the union operation is at the end of the computation graph which effectively reduces to taking the union of sets at the end. 
Experiments are run on standard datasets (FB15k and FB15k-237) — however, they generate their own query patterns. Specifically, they train on 5 patterns involving projection and intersection operation and test on 4 unseen ones. For baselines, they only compare to previous work of Hamilton et al., 2018 that maps queries to vectors. 

Strengths:
1. Most knowledge base comprehension benchmark tests on link prediction problems which are queries of kind (e1, r, ?). However, semantic parsers of natural language produce queries that are much richer in shape. This paper (and Hamiltion et al., 2018 before) considers answering complex logical queries (although the shape of query is pre-defined and not arbitrarily complex). 
2. Modeling logical queries into regions in vector space is an interesting idea, and it would be nice to see followup work in this direction.
3. The paper is nicely written and ablation experiments were helpful.
4. Compared to the baseline they used, the paper does a better job of modeling complex logical queries.

Weaknesses / Questions:
1. I understand that the papers have considered various pre-determined shapes of queries, but the simple 1p query is similar to the usual benchmarks, I don’t understand why results for 1p were not compared with existing benchmark results. Without that comparison, I don’t have a good sense if region-based method actually are effective for “1p” kind of queries. 
2. Even though the model was tested on two variants of freebase datasets, FB15k is well-known to have a lot of issues (Toutanova and Chen, 2015). Why weren't other standard datasets such as Nell-995, WN18RR and so many other biomedical KBs not considered for experiments, especially because the query generation process is very simple and it's easy to run experiments
3. It was not clear to me how the intersection operator would give zero offset for a set of non-overlapping boxes as input. Is the zero value coming from the deep-set model?, If so, how do you ensure that? Minor: Please include the deep-set network here instead of in Sec 4.3. I was confused about what the deepest model is until this point.
4. Regarding the results, is there any particular reason the MRR metric was pushed to the appendix and only results of Hits@3 was shown in the main section of the paper. I believe MRR is a better metric for your case because you are modeling sets of entities as answers and hence a ranking metric that ranks all entities is better, Hits@k is 1 if any of the answers in the set is present in top-k and hence quite a loose metric.
5. Why is the result of 3i is better than 2i. I am not sure why the model would do a better job in handling 3 intersections better than it does 2 intersections. 
6. How many answers are there on an average for each question. This will better help me understand how hard the dataset actually is. 
7. It is nice to see, that the model prefers boxes of different width. Do you have a sense of which type of entities (or relations) have higher offsets. This analysis would be nice to have for readers in the appendix section
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The paper studied the problem of answering complex logical queries on KGs, by proposing an embedding approach that encodes the queries into hyper-rectangles. The authors show that the proposed QUERY2BOX achieves the performance improvement in answering EPFO queries, as well as handling complex queries that is not observed in the training data. Experimental results show the efficacy of the proposed model. In general, I like the paper due to the nice presentation and promising approaches. However, I am not familiar with the context of KGs. I could not find anything wrong with this paper, but also do not have many intelligent questions to ask.  My only concern is the comparison experiments. The authors only presented the experiments using one baseline model GQE over two benchmark datasets. The authors may want to conduct more comparison experiments with the recent advances (e.g., Guu et al., 2015; Das et al., 2017) mentioned in the paper.  
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: The paper introduces an approach to answering queries on knowledge graphs, called Query2Box. The idea is to work with the embeddings of the vertices of the knowledge graph as if they were kind of sets. In this way, from a set, called box, of entities embeddings it is possible to project them to find other boxes using the relations specified by the query (these boxes contain the embeddings of the entities linked with those of the previous box by the relation specified in the query), or to intersect them to find the common entities.

Moreover, following this similarity, the approach is extended to solve queries containing disjunctions as well. The idea is to transform a query into its disjunctive normal form, solve each conjunction on its own (allowing the process to be parallelized) and finally answer with the set of entities in the boxes given by each conjunction.

A distance measure is used to check the belonging of an entity to a box.

This extension to disjunction could in principle be applied to other existing methods. In fact, the presented system is compared with GQE appropriately extended to handle disjunctions. 

The experiments show that Query2Box can achieve better results than GQE. Moreover, an ablation study was conducted.

While I am not an expert on the subject of reasoning on knowledge graph using embeddings, the proposal seems to me to achieve interesting results, and thus to be worthy of attention in the community. Comparing Query2Box with a state-of-art system like GQE positions the new approach as a good alternative to the state of the art.

The paper is well written, there are no problems in the use of English and in the organization of the paper.

The only error I have found is on page 5, equation 4, where v'_i is used while in the text below v_i is used, so I think the two notations should be aligned.

As a final score, I would not assign a high score because I am not experienced enough in the area to be sure about the validity of the approach, which, however, seems to be good and mature.
review_title: Official Blind Review #1

Meta-review: This paper proposes a new method to answering queries using incomplete knowledge bases. The approach relies on learning embeddings of the vertices of the knowledge graph. The reviewers unanimously found that the method was well motivated and found the method convincingly outperforms previous work.
Decision: Accept (Poster)