Answering complex logical queries on large-scale incomplete knowledge graphs (KGs) is a fundamental yet challenging task. Recently, a promising approach to this problem has been to embed KG entities as well as the query into a vector space such that entities that answer the query are embedded close to the query. However, prior work models queries as single points in the vector space, which is problematic because a complex query represents a potentially large set of its answer entities, but it is unclear how such a set can be represented as a single point. Furthermore, prior work can only handle queries that use conjunctions (∧) and existential quantifiers (∃). Handling queries with logical disjunctions (∨) remains an open problem. Here we propose QUERY2BOX, an embedding-based framework for reasoning over arbitrary queries with ∧, ∨, and ∃ operators in massive and incomplete KGs. Our main insight is that queries can be embedded as boxes (i.e., hyper-rectangles), where a set of points inside the box corresponds to a set of answer entities of the query. We show that conjunctions can be naturally represented as intersections of boxes and also prove a negative result that handling disjunctions would require embedding with dimension proportional to the number of KG entities. However, we show that by transforming queries into a Disjunctive Normal Form, QUERY2BOX is capable of handling arbitrary logical queries with ∧, ∨, ∃ in a scalable manner. We demonstrate the effectiveness of QUERY2BOX on two large KGs and show that QUERY2BOX achieves up to 25% relative improvement over the state of the art.
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