Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings
Authors: Hongyu Ren*
Weihua Hu*
Jure Leskovec
Venue:  (2020)
Keywords: knowledge graph embeddings
logical reasoning
query answering

Abstract: 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 ($\wedge$) and existential quantifiers ($\exists$). Handling queries with logical disjunctions ($\vee$) remains an open problem. Here we propose query2box, an embedding-based framework for reasoning over arbitrary queries with $\wedge$, $\vee$, and $\exists$ 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 $\wedge$, $\vee$, $\exists$ 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.


Published as a conference paper at ICLR 2020
QUERY2BOX: REASONING OVER KNOWLEDGE GRAPHS IN VECTOR SPACE USING Box EMBEDDINGS
Hongyu Ren", Weihua Hu', Jure Leskovee Department of Computer Science, Stanford University (hyren, we huahu, jure) @cs. stanford. edu
ABSTRACT
Answering complex logical queries on large-scale incomplete knowledge graphs (KGs) is fundamental yet challenging task. Recently, promising approach 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 the query. However, prior work models queries as single points in the vector space, which is problematic because complex query represents 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 only handle queries that use conjunctions (A) and existential quantifiers ()). Handling queries with logical disjunctions (V) remains an open problem. Here we propose QUERY2BOX, an embedding-bassee framework for reasoning over arbitrary queries with A, V, and 3 operators in massive and incomplete KGs. Our main insight is that queries can be embedded as boxes (i.c., hyper-rectangles) where set of points inside the box corresponds to set of answer entities of the query. We show that conjunctions can be naturally represented as intersections of boxes and also prove negative result that handling disjunctions would require embedding with dimension proportional 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 A, V, 3 in a scalable manner. We demonstrate the effectiveness of QUERY BOX on three large KGs and show that QUERY2BOX achieves up to 25% relative improvement over the state of the art.
INTRODUCTION
Knowledge graphs (KGs) capture different types of relationships between entities, e.g., Canada citizen Hinton. Answering arbitrary logical queries, such as "where did Canadian citizens with Turing Award graduate?", over such KGs a fundamental task in question answering, knowledge base reasoning, well as Al more broadly.
First-order logical queries can be represented as Directed Acyelic Graphs (DAGs) (Fig. A)) and be reasoned according to the DAGs to obtain a set of answers (Fig. CC). While simple and intuitive, such approach has many drawbacks: (1) Computational complexity of subgraph matching exponential in the query size, and thus cannot scale to modern KGs; (2) Subgraph matching is very sensitive as cannot correctly answer queries with missing relations. To remedy (2) one could impute missing
relations (Koller et al.) 2007 Džeroski 2009 De Raedi, 2008 Nickel et al.] 2016) but that would
only make the KG denser, which would further exacerbate issue (1) Dalvi Sueiu 2007 Krompaß
et al. 2014).
Recently, a promising alternative approach has emerged, where logical queries as well as KG entities are embedded into now-dimensional vector space such that entities that answer the query are embedded close to the query (Guu al., [015: [ammllton al.) 2018 Das et al.) (017)). Such approach robustly handles missing relations (Hamilton et al.) 22018) and is also orders of magnitude faster, as answering an arbitrary logical query is reduced to simply identifying entities nearest the embedding of the query in the vector space.
'Equal contributions. query2box
Project website with data and code: hts::///naa.sttafford.eee stanford.edu

---

Published as a conference paper at ICLR 2020
(A) Query and Its Dependency Graph
(B) C Computation Graph
V. 3.V. Win(TuringAwarrd A Citizen A Graduate(V.V))
Turing Award
Turing Award
Projection
Intersection
Win
V
Graduate
V
Projection
Projection
Canada
Citizen
Canada
Intersection
(C) Knowledge Graph Space
(D) Vector Space
Pearl
Win
Turing Award
McGill Cambridge
Hinton
Edinburgh
Turing
Edinburgh
Pearl
Graduate
Bengio
Graduate
B Bengia
Hinton
Cambridge
Canada
Bieber
Canada
Citizen
Bieber
Trudeau
McGill
Trudeau
Citizen
Query2Box reasoning framework. (A) A given conjunctive query "Where did Canadian citizens with Turing Award graduate?" can be represented with a dependency graph. (B) Computation graph specifies the reasoning procedure to obtain set of answers for the query in (A). (C) Example knowledge graph, where green nodes/entities denote answers to the query. Bold arrows indicate subgraphs that match the query graph in (A). (D) In QUERY2BOX, nodes of the KG are embedded as points in the vector space. We then obtain query embedding according to the computation graph (B) as sequence of box operations: start with two nodes TuringAward and Canada and apply Win and Citizen projection operators, followed by an intersection operator (denoted as a shaded intersection of yellow and orange boxes) and another projection operator. The final embedding of the query is green box and query's answers are the entities inside the box.
Figure 1:
However, prior work embeds query into single point in the vector space. This is problematic because answering a logical query requires modeling a set of active entities while traversing the KG (Fig. [C), and how effectively model set with a single point is unclear. Furthermore, is also unnatural to define logical operators (e.g., set intersection) of two points in the vector space. Another fundamental limitation of prior work is that it can only handle conjunctive queries, a subset of first-order logic that only involves conjunction (A) and existential quantifier (3), but not disjunction (V). It remains an open question how handle disjunction effectively in the vector space.
Here we present QUERY2BOX, an embedding-based framework for reasoning over KGs that is capable of handling arbitrary Existential Positive First-order (EPFO) logical queries (i.e., queries that include any set of A, V, and F) in a scalable manner. First, to accurately model a set of entities, our key idea is to closed region rather than single point in the vector space. Specifically, we use box (axis-aligned hyper-rectangle) to represent a query (Fig. [D). This provides three important benefits: (I) Boxes naturally model sets of entities they enclose; (2) Logical operators (e.g.. set intersection) can naturally be defined over boxes similarly as in Venn diagrams (Venn) 1880); (3) Executing logical operators over boxes results in new boxes, which means that the operations are closed; thus, logical reasoning can be efficiently performed in QUERY2BOX by iteratively updating boxes according to the query computation graph (Fig. (DD)).
We show that QUERY2BOX can naturally handle conjunctive queries. We first prove a negative result that embedding EPFO queries to only single points boxes is intractable it would require embed- ding dimension proportional to the number KG entities. However, we provide an elegant solution, where transform given EPFO logical query into Disjunctive Normal Form (DNF) (Davey & Priestley| 2002), i.e., disjunction of conjunctive queries. Given any EPFO query, QUERY BBOX represents
set of individual boxes, where each box is obtained for each conjunctive query in the DNF. We then return nearest neighbor entities to any of the boxes as the answers to the query. This means that to answer any EPFO query we first answer individual conjunctive queries and then take the union of the answer entities.
We evaluate QUERY2BOX three standard KG benchmarks and show: (1) QUERY2BOX provides strong generalization as it can answer complex queries; (2) QUERY2BOX can generalize to new

---

Published as a conference paper at ICLR 2020
logical query structures that it has never seen during training; (3) QUERY2BOX is able to implicitly impute missing relations as can answer any EPFO query with high accuracy even when relations involving answering the query missing in the KG; (4) QUERY2BOX provides up to 25% relative improvement in accuracy of answering EPFO queries over state-of-the tarth-r baselines.
2 FURTHER RELATED WORK
Most related to work embedding approaches for multi-hop reasoning over KGs (Bordes et al., 2013 Das et al. 2017 Guu et al. 2015; Hamilton et al., 2018). Crucial difference is that we provide way tractably handle larger subset of the first-order logic (EPFO queries vs. conjunctive queries) and that we embed queries as boxes, which provides better accuracy and generalization.
Second line of related work is on structured embeddings, which associate images, words, sentences, or knowledge base concepts with geometric objects such as regions (Erk) 22099 Vilnis et al. 2018 Li
ett al.) 2019), densities (Vilnis & McCallum 20144 [He et al., [2055] Athiwaratkun & Wilssn 2018). and orderings (Vendrov et al., 2016; Lai Hockenmaier 2017 Li et | (017). While the above work uses geometric objects to model individual entities and their pairwise relations,
the geometric objects to model sets of entities and reason over those sets. In this sense our work is also related to classical Venn Diagrams (Venn (880), where boxes are essentially the Venn Diagrams in vector space, but our boxes and entity embeddings are jointly learned, which allows us to reason over incomplete KGs.
Box embeddings have also been used to model hierarchical nature of concepts in an ontology with uncertainty (Vilnis et al. 2018 Li et al. 2019). While our work is also based on box embeddings we employ them for logical reasoning in massive heterogeneous knowledge graphs
3 QUERY2BOX: LOGICAL REASONING OVER KGs IN VECTOR SPACE
Here present the QUERY2BOX, where will define objective function that allows to learn embeddings of entities in the KG, and at the same time also learn parameterized geometric logical operators over boxes. Then given an arbitrary EPFO query 9 (Fig. [[A),, we will identify its computation graph (Fig. B)), and embed the query by executing a set of geometric operators over boxes (Fig. (D). Entities that are enclosed in the final box embedding are returned as answers the query (Fig. D)).
In order to train our system, we generate a set of queries together with their answers at training time and then learn entity embeddings and geometric operators such that queries can be accurately answered. We show in the following sections that our approach is able to generalize to queries and logical structures never seen during training. Furthermore, as we show experiments, our approach is able to implicitly impute missing relations and answer queries that would be impossible to answer with traditional graph traversal methods.
In the following we first only consider conjunctive queries (conjunction and existential operator) and then we extend our method also include disjunction.
3.1 KNOWLEDGE GRAPHS AND CONJUNCTIVE QUERIES
We denote a KG as = (V, where v E V represents an entity, and E R is binary function r: V x V + (True, False). indicating whether the relation r holds between pair of entities or not. In the KG, such binary output indicates the existence of the directed edge between a pair of entities, ie., v In vf iff r(e, True.
Conjunctive queries are a subclass of the first-order logical queries that use existential (3) and conjunction (A) operations. They are formally defined as follows.
[[>] V/. ...V...... ... VA : e, A ... Cn. where e; = r(v,, V), V E (V2, Vi...., VaJ v. E VVrEE
ore; = rV, V"), V, V E (V,, V,,.. VJJV +V',E
where e. represents non-variable anchor entity, V/,...,
.....,,e Va are existentially quantified bound variables, V is the target variable. The goal of answering the logical query q is to find set of entities [4]] C V such that u E [q] iff qlu] = True. We call [g] the denotation set (i.e., answer set) of query q.

---

Published as a conference paper at ICLR 2020
As shown in Fig. TA), the dependency graph is graphical representation of conjunctive query q. where nodes correspond to variable or non-variable entities in q and edges correspond to relations in q. In order for the query to be valid, the corresponding dependency graph needs to be Directed Acyclic Graph (DAG), with the anchor entities as the source nodes the DAG and the query target Vj as the unique sink node (Hamilton et al. 2018).
From the dependency graph of query q, one can also derive the computation graph, which consists of two types of directed edges that represent operators over sets of entities:
Projection: Given a set of entities 5 C V. and relation r R. this operator obtains
Ar))) where (v) = {o' E V: r(e, v²) True}.
Intersection: Given a set of entity sets (S1, S2, ....................... S,), this operator obtains 1
For given query q, the computation graph specifies the procedure of reasoning to obtain set of answer entities, i.e., starting from a set of anchor nodes, the above two operators are applied iteratively until the unique sink target node is reached. The entire procedure is analogous traversing KGs following the computation graph Guu et al. 2015).
3.2 REASONING OVER SETS OF ENTITIES USING BOX EMBEDDINGS
So far we have defined conjunctive queries as computation graphs that can be executed directly over the nodes and edges in the KG. Now, we define logical reasoning in the vector space. Our intuition follows Fig. T Given a complex query, we shall decompose into sequence of logical operations, and then execute these operations in the vector space. This way we will obtain the embedding of the query, and answers to the query will be entities that are enclosed the final query embedding box.
In the following, we detail our two methodological advances: (1) the use of box embeddings to efficiently model and reason over sets of entities in the vector space, and (2) how to tractably handle disjunction operator (V), expanding the class of first-order logic that can be modeled in the vector space (Section 3.3).
Box embeddings. To efficiently model a set of entities in the vector space, we use boxes (i.e., axis-aligned hyper-rectangles). The benefit that unlike single point, the box has the interior; thus, if an entity is in set, it is natural to model the entity embedding to be point inside the box. Formally, we operate on Ed and define a box in Rd by p = (Cen(p), (ff(p)))ff( E 28 as:
(2) where = is element- inequality, Cen(p) E TRd is the center of the box, and Off(p) E RR is the V in KG is assigned single
Boxp (v E Rd Cen(p) Off(p) = Cen(p) Off(p)),
positive offset of the box, modeling the size of the box. Each entity vector V E IRd (i.e., a zero-size box), and the box embedding p models {u E V : v E Boxp). ). i.e. set of entities whose vectors are inside the box. For the rest of the paper, we use the bold face to denote the embedding, e.g., embedding of v is denoted by v.
Our framework reasons over KGs in the vector space following the computation graph of the query, as shown in Fig. DD) we start from the initial box embeddings of the source nodes (anchor entities) and sequentially update the embeddings according to the logical operators. Below, we describe how we set initial box embeddings for the source nodes, as well as how we model projection and intersection operators (defined in Sec. 3.1 as geometric operators that operate over boxes. After that, we describe our entity-to-box distance function and the overall objective that learns embeddings as well as the geometric operators.
Initial boxes for source nodes. Each source node represents an anchor entity v E V, which we can regard as set that only contains the single entity. Such a single-element set can be naturally modeled by a box of size/offset zero centered at v. Formally, we set the initial box embedding as (v, 0), where IRd is the anchor entity vector and is a d-dimensional all-zero vector.
Geometric projection operator. We associate each relation r E R with relation embedding r (Cen(r), (r) 2d with Off(r) > O. Given an input box embedding p. we model the projection by + r, where we sum the centers and sum the offsets. This gives us new box with the translated center and larger offset because Off(r) > 0, as illustrated in Fig. A.. The adaptive box size effectively models a different number of entities/vectors in the set.
Geometric intersection operator. We model the intersection of a set of box embeddings (Pi,..., .p))...,P.) as Pinter = (Cen(Pinter). (ft which is calculated by performing attention

---

Published as a conference paper at ICLR 2020
(A) Projection
(B) Intersection
(C) Distance
4aax
Cen
dist (q.V v)
mmi
dist outside (q.
Figure 2: The geometric intuition of the two operations and distance function in QUERY2BOX (A) Projection generates larger box with a translated center. (B) Intersection generates smaller box lying inside the given set of boxes. (C) Distance distbox is the weighted sum of distoutside and distinside. where the latter is weighted less.
over the box centers (Bahdanau al. 2013) and shrinking the box offset using the sigmoid function:
Cen(Pinter) a, ② Cen(pi), exp(MLP(pi))
Σj exp(MML((p))
Off(Piiter) Min((Off(p1)..... Off((n))) } @ o (DeepSets((pi.... .P)))
where the dimension-wise product, MLP(.) : 12 F.d is the Multi-Layer Perceptron, (-) is the sigmoid function, DeepSets(-) is the permutation-invarial deep architecture (Zaheer et al. 2017), and both Min(-) and exp(-) are applied in dimension-wise manner. Following Hamilton et al. (2018), we model all the deep sets by DeepSets( [xi..... xN)) = MLP((L/N) E'= (x,(xx)). where all the hidden dimensionalities of the two MLPs the same the imput dimensionality. The intuition behind our geometric intersection to generate a smaller box that lies inside a set boxes, illustrated in Fig. B Different Differrent from the generic deep sets to model the intersection (Hamilton jet al. 2018), our geometric intersection operator effectively constrains the center position and models the shrinking set size.
Entity-to-box distance. Given query box q E Id2d and an entity vector v E Rd, we define their distance as
distbox (v:q) q) = distoutside (v; q) + a dist (v;g),
(3)
where qmax Cen(q) Off(g) Rd Qmin Cen(q) Off(g) Rdd and 0 < is fixed scalar, and
distoutside (v; q) |Max(v Qmax, 0) Max(qmin v. 0)]],
distinside (v:q)= [[Cen()) Min(qmax: Max (axin v))ll
As illustrated in Fig. [CC), distoutside corresponds to the distance between the entity and closest corner/side of the box. Analogously, distinside corresponds the distance between the center of the box and its side/corner (or the entity itself if the entity is inside the box).
The key here is to downweight the distance inside the box by using < 1. This means that as long as entity vectors are inside the box, we regard them as "close enough" to the query center (i.e., dist.utsidee is 0, and distinside scaled by a). When distance, i.e., |[Cen(q) - v/I1. which is used by the conventional TransE (Bordes et al. 2013) as well prior query embedding methods (Guu al. 2015 Hamilton al., 2018).
1, dist reduces the ordinary L
Training objective. Our next goal to learn entity embeddings as well as geometric projection and intersection operators.
Given a training set of queries and their answers, we optimize a negative sampling loss (Mikolov' et al. 2013) to effectively optimize distance-based model (Sun et al.) 2019):
log (? distbox (v: q))
log (distbox (V/::) - -Y),
'ne possible choice here would to directly use raw intersection, however, we find that our richer learnable parameterization is more expressive and robust

---

Published as a conference paper at ICLR 2020
where Y represents a fixed scalar margin, [[9] is positive entity (i.e., answer to the query g). and 2 & [g] is the i-th negative entity (non-ansser to the query q) and k is the number of negative entities.
3.3 TRACTABLE HANDLING OF DISJUNCTION USING DISJUNCTIVE NORMAL FORM
So far we have focused on conjunctive queries, and our aim here is to tractably handle in the vector space a wider class of logical queries, called Existential Positive First-order (EPFO) queries (Dalvi & Suciu 2012) that involve V in addition to 3 and A. We specifically focus on EPFO queries whose computation graphs are DAG, same as that of conjunctive queries (Section 3.I. except that now have an additional type of directed edge, called union defined as follows:
Union: Given set of entity sets (Si, S....., } this operator obtains 1
straightforward approach here would be to define another geometric operator for union and embed the query as did in the previous sections. An immediate challenge for our box embeddings is that boxes can be located anywhere in the vector space, so their union would no longer be a simple box. In other words, union operation over boxes is not closed.
Theoretically, we prove a general negative result that holds for any embedding-basee method that embeds query q into q and uses some distance function retrieve entities, i.e., dist(v; q) S iff v E [q]. Here, (v; q) is the distance between entity and query embeddings, e.g., distbbo (v; q) or 1|v 9ll2. and 33 is fixed threshold.
Theorem 1. Consider any M conjunctive queries Q1,....9 ..M whose denotation sets [qi]....., [[
are disjoint with each other, V i + j, [9.1 I = Ø. Let D be the VC dimension of the function class {sign(B 8 - dist(;; Q) q E }. where E represents the query embedding space and sign(-) is
the sign function. Then, we need D 2 M to model any EPFO query, i.e., dist d 3 + [q]
is satisfied for every EPFO query q-
The proof is provided in Appendix A where the key is that with the introduction of the union operation any subset of denotation sets can be the answer, which forces us to model the powerset .MM } in vector space.
{U,ccs [9:1 Vv.csl9:1= : S
For real-world KG, there are M Rs |V] conjunctive queries with non-overlapping answers. For example, in the commonly-used FB 15k5 dataset (Bordes et al. 2013), derived from the Freebase (Bollacker et al. 2008). we find M 13,365, while |V] is 14,951 (see Appendix B for the details).
Theorem shows that in order to accurately model any EPFO query with the existing framework, the complexity of the distance function measured by the VC dimension needs to be large as the number of KG entities. This implies that if we use common distance functions based on hyper-plane, Euclidean sphere, axis-aligned rectangle? their parameter dimensionality needs to be ((M), which is @(Vl) for real KGs we are interested in. In other words, the dimensionality of the logical query embeddings needs to be O(D)). which is not low-dimensional; thus not scalable large KGs and not generalizable in the presence of unobserved KG edges.
To rectify this issue, our key idea is to transform given EPFO query into Disjunctive Normal Form (DNF) (Davey & Priestley] 2002). i.e., disjunction of conjunctive queries, so that union operation only appears in the last step. Each of the conjunctive queries can then be reasoned in the low-dimensional space, after which we can aggregate the results by a simple and intuitive procedure. In the following, we describe the transformation to DNF and the aggregation procedure.
Transformation to DNE. Any first-order logic can be transformed into the equivalent DNF Davey & Priestley 2002). We perform such transformation directly in the space of computation graph, Le., moving all the edges of type "union" to the last step of the computation graph. Let G = (V, Egy) be the computation graph for given EPFO query q. and let Vunion Vg be set of nodes whose in-coming edges are of type "union". For each E Vunion- define Pa C Vg as set of its parent nodes. We first generate N IIvevmnu |Pol different computation graphs G (g)),..... G...,) as follows, each with different choices of Uparent in the first step.
1. For every U E V Vunion, select one parent node Uparent E Pa-
2 For the detailed VC dimensions these function classes, see Vapnik 2013 Crucially, their VC dimensions are all linear with respect to the number of parameters d.

---

Published as a conference paper at ICLR 2020
(A) O Orgginal Computation Graph
(B) Converted Computation Graph
Projection Projection
Intersection
P
P Projection
Union
Pojection
Union
Intersection
Projecton
Intersection
Projection
Union
P2 Projection rojection
Intersection
P2
Union
Projection
Intersection
rojection
Intersection
Figure 3: Illustration of converting a computation graph of an EPFO query into an equivalent computation graph of the Disjunctive Normal Form.
2. Remove all the edges of type 'union.'
3. Merge v and parente while retaining all other edge connections.
We then combine the obtained computation graphs Ggo))...., Gyiny as follows to give the final equivalent computation graph.
1. Convert the target sink nodes of all the obtained computation graphs into the existentially quantified bound variables nodes.
2. Create new target sink node V,, and draw directed edges of type "union" from all the above variable nodes to the new target node.
An example of the entire transformation procedure is illustrated in Fig. 3 By the definition of the union operation, our procedure gives the equivalent computation graph as the original one. Furthermore, as all the union operators are removed from Gg(t),.... G ((,, all of these computation graphs represent conjunctive queries, which we denote as q()), ,...., g (N)) We can then apply existing framework obtain a set of embeddings for these conjunctive queries as ((),....,q()),
Aggregation. Next we define the distance function between the given EPFO query q and an entity v E V. Since q is logically equivalent to q v... V (NV), we can naturally define the aggregated distance function using the box distance dist
distags (v: q) Min (fdist ()),,.. dist.ox d
(5)
where distagg is parameterized by the EPFO query When is conjunctive query, i.e., N = 1. distagg (v: distbox (V: For N 1, distagg takes the minimum distance to the closest box as the distance to an entity. This modeling aligns well with the union operation; an entity is inside the union of sets as long as the entity is in one of the sets. Note that our DNF-query rewriting scheme is general and is able to extend any method that works for conjunctive queries (e.g.. (Hamilton et al. 2018)) to handle more general class of EPFO queries.
Computational complexity. The computational complexity of answering an EPFO query with our framework equal that of answering the conjunctive queries. In practice, N might not be so large, and all the N computations can be parallelized. Furthermore, answering each conjunctive query is very fast takes constant time) and then perform range search (Bentley & Friedman 1979) in the embedding space, which can also be done constant time using techniques based on Locality Sensitive Hashing (Inyyk & Motwani] 1998).
requires us to execute sequence of simple box operations (each of which
4 EXPERIMENTS
Our goal in the experiment section is to evaluate the performance of QUERY on discovering answers to complex logical queries that cannot be obtained by traversing the incomplete KG. This means, we will focus on answering queries where one or more missing edges in the KG have to be successfully predicted in order to obtain the additional answers.
4.1 KNOWLEDGE GRAPHS AND QUERY GENERATION
We perform experiments on three standard KG benchmarks, FB15k (Bordes et al. (Toutanova & Chen 2015), and NELL9995 (Xiong al. 2017) Appendix E for NELL1995
2013) FB15k-22 137
pre-processing details). Dataset statistics are summarized in Table in Appendix

---

Published as a conference paper at ICLR 2020
Training Conjunctive Querles
Unseen Conjunctive Queries
Union Querles
O+0+
O
u
1p
2p
3p 2i
3i
ip pi 2u
up
Figure 4: Query structures considered in the experiments, where anchor entities and relations to be specified to instantiate logical queries. Naming for each query structure is provided under each subfigure, where 'p', 'i', and 'u' stand for 'projection', 'intersection', and 'union', respectively, Models are trained on the first query structures, and evaluated on all 9 query structures. For example, "3p" is path query of length three, and "2i" is an intersection of cardinality two.
Dataset FB15k
1p
2p
3p
2i
3i
ip
pi
2u
up
10.8
255.6
250.0
90.3
64.1
593.8
190.1
27.8
227.0
FB15K-237
13.3
131.4
215.3
69.0
48.9
593.8
257.7
35.6
127.7
NELL995
8.5
56.6
65.3
30.3
15.9
310.0
144.9
14.4
62.5
Table I: Average number of answer entities of test queries with missing edges grouped by different query structures (for a KG with 10% edges missing).
We follow the standard evaluation protocol in KG literture: Given the standard split of edges into training, test, and validation sets, we first augment the KG also include inverse relations and effectively double the number of edges in the graph. We then create three graphs: Guain. which only contains training edges and we use this graph train node embeddings well as box operators. We then also generate two bigger graphs: Gvalid, which contains Guaai plus the validation edges, and Gres. which includes Gvali well as the test edges.
We consider kinds of diverse query structures shown and named in Fig. We use 5 query structures for training and then evaluate all the 9 query structures. We refer the reader Appendix D for full details on query generation and Table i Appendix for statistics of the generated logical queries. Given query q, let [q]]miin [9llaat, and [ les denote set of answer entities obtained by running subgraph matching of on Gmnin Gvalid, and Gees. respectively. At the training time, we use [q]leain as positive examples for the query and other random entities as negative examples. However, at the test/validation time we proceed differently. Note that we focus on answering queries where generalization performance is crucial and at least edge needs to be imputed in order to answer the queries. Thus, rather than evaluating a given query on the full validation (or test) set [q] (Tll of answers, validate the method only on answers that include missing relations. Given how we constructed Gmii S Gvalid S Frest- we have [q] Irann S [g] val S [q] and thus we evaluate the method on [4]]val Mg] main to tune hyper-parameters and then report results identifying answer entities in [q]]ess [g]] This means we always evaluate on queries/entities that were not part of the training and the method has not seen them before. Furthermore, for these queries, traditional graph traversal techniques would not be able to find the answers (due to missing relations).
Table 1 shows the average number of answer entities for different query structures. We observe that complex logical queries (especially 2p, 3p, ip, pi, up) indeed require modeling a much larger number of answer entities (often more than 10 times) than the simple 1p queries do. Therefore, expect box embeddings to work particularly well in handling complex queries with many answer entities]
4.2 EVALUATION PROTOCOL
Given test query g, for each of its non-trivial answers [[] lea Millvat, we use dist in Eq. 3 rank v among V VVTTleest Denoting the rank of o by Rank(u), we then calculate evaluation metrics for answering query q, such as Mean Reciprocal Rank (MRR) and Hits K (H@@ K):
Metrics(g) I[ [glval HE[1] wn Vol
Σ
fmearies (Rankei))) (u)),
'On the simple link prediction (Ip query) task, box embeddings provide minor empirical performance improvement over TransE, possibly because simple link prediction does not require modeling large sets of entities, as shown in Table See Appendix C [or for full experimental results on link prediction.

---

Published as a conference paper at ICLR 2020
Method
Avg
1p
2p
3p
2i
31
ip
pi
2u
up
FB15k
Q2B
0.484
0.786
0.413
0.303
0.593
0.712
0.211
0.397
0.608
0.33
GQE
0.386
0.636
0.345
0.248
0.515
0.624
0.151
0.310
0.376
0.273
GQE-DOUBLE
0.384
0.630
0.346
0,250
0.515
0.611
0.153
0.320
0.362
0.271
FB15k-237
Q2B
0.268
0,467
0.24
0.186
0.324
0,453
0.108
0.205
0.239
0.193
GQE
0.228
0.402
0.213
0.155
0.292
0.406
0.083
0.17
0.169
0.163
GQE-DOUBLE
0.23
0.405
0.213
0.153
0.298
0.411
0.085
0.182
0.167
0.16
NELL995
Q2B
0.306
0.555
0.266
0.233
0.343
0.48
0.132
0.212
0.369
0.163
GQE
0.247
0,418
0.228
0.205
0.316
0,447
0.081
0.186
0.199
0.139
GQE-DOUBLE
0.248
0.417
0.231
0.203
0.318
0.454
0.081
0.188
0.2
0.139
Table 2: H@3 results of QUERY2BOX vs. GQE on FB15k FB15k-237 and NELL995.
where metricc (z) 3 for MRR, and (z) 1[2 s K] for H@ K.
x2
We then average Eq. 6 over all the queries within the same query structure and report the results separately for different query structures. The same evaluation protocol is applied to the validation stage except that we evaluate on [4] val [[]]min rather than [q][ess /41]vat.
4.3 BASELINE AND MODEL VARIANTS
We compare our framework QUERY2BOX against the state-of-the-art GQE (Hamilton al. 2018). GQE embeds a query to a single vector, and models projection and intersection operators as trans and deep sets (Zaheer al. 2017), respectively. The Lı distance is used the distance between query and entity vectors. For a fair comparison, we also compare with GQE-DOUBLE (GQE with doubled embedding dimensionality) so that QUERY2BOx and NQE-DOUBLE have the same amount of parameters. Refer to Appendix for the model hyper-paramen parameters used in our experiments. Although the original GQE cannot handle EPFO queries. we apply our DNF-query rewriting strategy and in our evaluation extend GQE to handle general EPFO queries well. Furthermore, we perform extensive ablation study by considering several variants of QUERY2BOX (abbreviated Q2B). We list our method as well as its variants below.
Q2B (our method):
The box embeddings are used to model queries, and the attention mechanism is used for the intersection operator.
Q2B-AVG: The attention mechanism for intersection is replaced with averaging.
Q2R-DEEPSETS: The attention mechanism for intersection is replaced with the deep sets.
Q2B-AVG-IP The variant of Q2B-AVG that is trained with only 1p queries (see Fig. 4 thus,
logical operators not explicitly trained.
Q2D-SIIAREDOFFSET The box offset is shared across all queries (every query is represented by box with the same trainable size).
4.4
MAIN RESULTT
We start by comparing our Q2B with state-of-the-art query embedding method GQE (Hamilton et al. 2018) FB15k, FB 15k-237, and NELL995. As listed in Tables 2 our method significantly and consistently outperforms the state-of-the-ard baseline across all the query structures, including those not seen during training well as those with union operations. On average, we obtain 9.8% (25% relative), 3,8% (15% relative), and 5.9% (24% relative) higher H@3 than the best baselines on 15K,, FB15k-237, and NELL995, respectively. Notice that naively increasing embedding dimensionality in GQE yields limited performance improvement. Our Q2B is able to effectively model a large set of entities by using the box embedding. and achieves significant performance gain compared with GQE-DOUSE (with same number of parameters) that represents queries as point vectors. Also notice
*Note that our evaluation metric is slightly different from conventional metric Nickel et al. 2016 Hamilton
2018, Guu al. 2015), where average taken over query-answer pairs. The conventional metric problematic can be significantly biased toward correctly answering generic queries with huge number of answers, while dismissing fine-grained queries with a few answers. Here, treat queries equally regardless of the number of answers they have, we take average over queries.

---

Published as a conference paper at ICLR 2020
Method
Avg
1p
2p
21
3i
ip
pi
2u
up
FB15k
Q2B
0.484
0.786
0,413
0.303
0.593
0.712
0.211
0.397
0.608
0.330
Q2B-AVG
0.468
0.779
0.407
0.300
0.577
0.673
0.199
0.345
0.607
0.326
Q2B-DEEPSETS
0.467
0.755
0.407
0.294
0.588
0.699
0.197
0.378
0.562
0.324
Q2B-AVG-IP
0.385
0.812
0.262
0.173
0.463
0.529
0.126
0.263
0.653
0.187
QBB-SHAREDOFFSET
0.372
0.684
0.335
0,232
0.442
0.559
0.144
0.282
0.417
0.252
FB15k-2.3
Q2B
0.268
0.467
0.24
0,186
0.324
0,453
0.108
0.205
0.239
0.193
Q2B-AVG
0.249
0.462
0.242
0.182
0.278
0.391
0.101
0.158
0.236
0.189
Q2R-DEEPSETS
0.259
0.458
0.243
0,186
0.303
0.432
0.104
0.187
0.231
0.190
Q2B-AVG-IP
0.219
0.457
0.193
0.132
0.251
0.319
0.083
0.142
0.241
0.152
0.207
0.391
0.199
0.139
0.251
0.354
0.082
0.154
0.15
0.142
NELL995
Q2B
0.306
0.535
0.266
0.233
0.343
0,480
0.132
0.212
0,369
0.163
Q2B-AVG
0.283
0.543
0.250
0.228
0.300
0.403
0.116
0.188
0.36
0.161
Q2B-DEEPSETS
0.293
0.539
0.26
0.231
0.317
0.467
0.11
0.202
0.349
0.16
Q2B-AVG-IP
0.274
0.607
0.229
0.182
0.277
0.315
0.097
0.18
0.443
0.133
0.237
0.436
0.219
0.201
0.278
0.379
0.096
0.174
0.217
0.137
Table 3: H@3 3 results of QUERY2BOX vs. several variants on FB15k, FB FB15k-237 and NELL995.
that Q2B performs well on new queries with the same structure the training queries well as on new query structures never seen during training, which demonstrates that Q2B generalizes well within and beyond query structures.
We also conduct extensive ablation studies (Tables)
3) We summarize the results as follows:
Importance of attention mechanism. First, we show that our modeling of intersection using the
attention mechanism is important. Given a set of box embeddings (P1,.... .P........p.. ). Q2B-AVG AVG is the most naïve way to calculate the center of the resulting box embedding Pinter while -2---EEESSEEEE flexible and neglects the fact that the center should be a weighted average of Cen(P1) (p)...... Cen(pa), Compared with the two methods, Q2B achieves better performance in answering queries that involve intersection operation, e.g., 2i, 3i, pi, ip. Specifically, on FB15k-237, Q2B obtains more than 4% and 2% absolute gain in H@3 compared to Q2B-AVG and Q2B-DEEPSETS, respectively.
is too
Necessity of training on complex queries. Second, we observe that explicitly training on complex logical queries beyond one-hop path queries (Ip in Fig. 4 improves the reasoning performance. Although Q2B-AVG- 1P able to achieve strong performance on Ip and 2u, where answering 2u essentially answering two 1p queries with an additional minimum operation (see Eq. 5 Section 3.3). Q2B-AVG-11 1P fails miserably in answering other types of queries involving logical operators. On the other hand, other methods (Q2B, Q2B-AVG, and BEB-DEEPSTTS that are explicitly trained on the logical queries achieve much higher accuracy, with up to 10% absolute average improvement of H@3 3 on FB15k.
Adaptive box size for difffernt queries. Third, we investigate the importance of learning adaptive offsets (box size) for different queries. Q2B-SHAREDOFFSS is a variant of our Q2B where all the box embeddings share the same learnable offset. Q2B-SHAREDOPFSET does not work well on all types of queries. This is most likely because different queries have different numbers of answer entities, and the adaptive box size enables us to better model it. In fact, we find that box offset varies significantly across different relations, and one-to-many relations tend to have larger offset embeddings (see Appendix for the details).
5 CONCLUSION
In this paper we proposed reasoning framework called QUERY2BOX that can effectively model and reason over sets of entities as well as handle EPFO queries in vector space. Given a logical query, we first transform it into DNF, embed each conjunctive query into box, and output entities closest to their nearest boxes. Our approach is capable of handling all types of EPFO queries scalably and accurately. Experimental results on standard KGs demonstrate that QUERY2BOX significantly outperforms the existing work in answering diverse logical queries.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We thank William Hamilton, Rex Ying, and Jiaxuan You for their helpful discussion. W.H is supported by Funai Overseas Scholarship and Masason Foundation Fellowship. J.L. is Chan Zuckerberg Biohub investigator. We gratefully acknowledge the support of DARPA under Nos. TA865018C7880 (ASED), N66001 (MCS); ARO under Nos. W91 19F--166-1-034 (MURI, W91 1911NF-16-1-017 (DURIP); NSF under Nos. OAC-1835598 (CINES), OAC-1934578 (HDR); Stanford Data Science Initiative, Wu Tsai Neurosciences Institute, Chan Zuckerberg Biohub, JD.com, Amazon, Boeing, Docomo, Huawei, Hitachi, Observe, Siemens, UST Global.
The U.S. Government is authorized reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings, and conclusions or rec- ommendations expressed in this material those of the authors and do not necessarily reflect the views, policies, or endorsements, either expressed or implied, of DARPA, NIH, ARO, or the U.S. Government.
REFERENCES
Carl Allen, Ivana Balazevic, and Timothy M Hospedales. On understanding knowledge graph representation. arXiv preprint arXiv:1909. 1611,, 2019.
Ben Athiwaratkun and Andrew Gordon Wilson. Hierarchical density order embeddings. In Interna- tional Conference on Learning Representations (ICLR), 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference Learning Representations (ICLR), 2015.
Jon Louis Bentley and Jerome H Friedman. Data structures for range searching. ACM Computing Surveys (CSUR), 11(4):397-409 1979.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collabora- tively created graph database for structuring human knowledge. In ACM SIGMOD international conference on Management of data (SIGMOD), pp. 1247-1250. AcM, 2008
Antoine Bordes, Nicolas Usunier, Alberto Marcia-Duran Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2787-2795, 2013.
Nilesh Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. VLDB, 16(4): 523-544 2007.
Nilesh Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. Journal of the ACM (JACM), 59(6):30, 2012.
Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In European Chapter of the Association for Computational Linguistics (EACL), pp. 132-141, 2017.
Brian Davey and Hilary Priestley. Introduction lattices and order. Cambridge university press, 2002.
Lue De Raedt. Logical and relational learning. Springer Science & Business Media, 2008
Sašo Džeroski. Relational data mining. In Data Mining and Knowledge Discovery Handbook, pp. 887-911. Springer, 2009.
Katrin Erk. Representing words as regions in vector space. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning, pp. 57-65. Annual Meeting of the Association for Computational Linguistics (ACL), 2009.
Kelvin Guu, John Miller, and Percy Liang. Traversing knowledge graphs in vector space. In Empirical Methods in Natural Language Processing (EMNLP), pp. 318-327, 2015.

---

Published as a conference paper at ICLR 2020
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2027-2038, 2018.
Shizhu He, Kang Liu, Guoliang Ji, and Jun Zhao. Learning to represent knowledge graphs with gaussian embedding. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 623-632. ACM, 2015.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. pp. 604-613. ACM, 1998.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Daphne Koller, Nir Friedman, Sašo Džeroski, Charles Sutton, Andrew McCallum, Avi Pfeffer, Pieter Abbeel, Ming-Fai Wong. David Heckerman, Chris Meek, et al. Introduction to statistical relational learning. MIT press, 2007.
Denis KrompaB, Maximilian Nickel, and Volker Tresp. Querying factorized probabilistic triple databases. In International Semantic Web Conference, pp. 114-129. Springer, 2014.
Alice Lai and Julia Hockenmaier. Learning to predict denotational probabilities for modeling entailment. In Annual Meeting of the Association for Computational Linguistics (ACL), pp. 721-730, 2017.
Xiang Li, Luke Vilnis, and Andrew McCallum. Improved representation learning for predicting commonsense ontologies. arXiv preprint arXiv: 00549, 2017.
Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smoothing the ge-
ometry of probabilistic box embeddings. In International Conference Learning Representations (ICLR), 2019.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word repre- sentations in vector space. In International Conference on Learning Representations (ICLR), 2013.
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.
Zhiqing Sun, Zhi-Hong Deng, Tan Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations (ICLR), 2019.
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 Compositionalllt, pp. 57-66, 2015.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddings of images and language. In International Conference Learning Representations (ICLR), 2016.
John Venn. I. on the diagrammatic and mechanical representation of propositions and reasonings.
The London, Edinburgh, and Dublin philosophical magazine and journal of science, 10(59): 1880.
Luke Vilnis and Andrew McCallum. Word representations via gaussian embedding. In International Conference on Learning Representations (ICLR), 2014.
Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Prohabilistic embedding of knowledge graphs with box lattice measures. In Annual Meeting of the Association for Computational Linguistics (ACL), 2018.
12

---

Published as a conference paper at ICLR 2020
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Empirical Methods in Natural Language Processing (EMNLP), 2017.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), pp. -3401, 2017.
13

---

Published as a conference paper at ICLR 2020
A PROOF OF THEOREM
Proof. To model any EPFO query, we need to at least model a subset EPFO queries Q = {Va,e S (q...... ..r.......)) h, where the corresponding denotation sets are (U.esIIa)) S (g...... qas }}- For the sake of modeling Q, without loss of generality, we consider assigning a single entity embedding qq: to all E [a:] so there are M kinds of entity vectors, V.u.... Vam To model all queries in Q, it is necessary to satisfy the following.
ees
{ if 1> if $
3V Vg.. 3vqu AS S (91..... qm 3qs such that dist(Vq 9s)
(7)
where qs is the embedding of query c. Eq. means that we can learn the M kinds of entity vectors such that for every query in Q, we obtain its embedding to model the corresponding set using the distance function. Notice that this is agnostic to the specific algorithm to embed query Vees into qs: thus, our result is generally applicable to any method that embeds the query into single vector.
3} being able to shutter (Vq..... VqM i.e., any binary labeling of the points can be perfectly fit by some classifier in the function class. To up, in order model any EPFO query, need to at least model any query in Q, which requires the VC dimension of the distance function to be larger than or equal to M.
Crucially, satisfying Eq- equivalent {sign(B dist(:: ::)
B DETAILS ABOUT COMPUTING M IN THEOREM
Given the full KG Giea for the FB dataset, our goal is find conjunctive queries .1..... - such that [m]].... [[aar] are disjoint with each other. For conjunctive queries, we use two types of queries: '1p' and '2i' whose query structures
shown in Figure 4 On the FB FB15k, we instantiate 308,006 queries of type 'Ip', which we denote by Sip- Out of all the queries in Sip. 129,717 queries have more than one answer entities, and we denote such set of the queries by St We then generate set of queries of type '2i' by first randomly sampling two queries from Sip and then taking conjunction; we denote the resulting set of queries by S2i
Now, we use Sip and Sz to generate set of conjunctive queries whose denotation sets are disjoint with each other. First, we prepare two empty sets Vseen = Ø and Q = Ø. Then, for every E Sip. Vseen 0 [[]] = Ø holds, we let Q QU {q) and Vseen seen U [q] This procedure already gives us Q. where we have 10, 812 conjunctive queries whose denotation sets are disjoint with each other. We can further apply the analogous procedure for Szi, which gives us a further increased Q, where we have 13, 365 conjunctive queries whose denotation sets are disjoint with each other. Therefore,
get M 13, 365.
C EXPERIMENTS ON LINK PREDICTION
FB15k
FB15k
2277
NEL1995
Method
H@3
MRR
H@3
MRR
H@3
MRR
query2box
0.613
0,516
0.331
0.295
0.382
0.303
query2box- 1p
0.633
0.531
0.323
0.292
0.415
0.320
TransE 0.611
0.522
0.318
0.289
0.413
0.320
Table 4: Performance comparison on the simple link prediction task on the three datasets.
In Table we report the link prediction performance (no multi-hop logical reasoning required) following the conventional metrics (taking average over the triples of head, relation, and tail). Here query2box trained on all five query structures as shown in Figure g and query2box-Ip is only trained simple Ip queries. We found that query2box is comparable TransE on simple link prediction. Note that in the case of simple link prediction, we do not expect a huge performance gain by using box embeddings link prediction does not involve logical reasoning nor handling a large set of answer entities. Also, we see that even if we train query2hox over diverse link prediction is still comparable to TransE and query2box-Ip which
slightly better than
queries, its performance are trained solely on the link prediction task.
14

---

Published as a conference paper at ICLR 2020
V
a
r
O
r-1
r
Va
V
V/
V
r
Va
Figure 5: Example the degenerated queries, including (1) r and y-1 appear along one path and (2)
same anchor node and relation in intersections.
D DETAILS ON QUERY GENERATION
Given Grainn Gvalid, and Grest as defined Section 4.1 we generate training, validation and test queries of different query structures. During training, we consider the first 5 kinds of query structures. For evaluation, consider all the 9 query structures in Fig- 4 containing query structures that are both seen and unseen during training time. We instantiate queries in the following way.
Given KG and query structure (which is DAG), we use pre-order traversal to assign entity and a relation to each node and edge in the DAG of query structure to instantiate a query. Namely, start from the root of the DAG (which is the target node),
sample entity uniformly from the KG to be the root, then for every node connected to the root the DAG, we choose a relation r uniformly from the in-coming relations of in the KG, and new entity e' from the set of entities that reaches by r in the KG. Then we assign the relation r to the edge and e' to the node, and move on the process based on the pre-order traversal. This iterative process stops after assign entity and relation to every node and edge in DAG. The leaf nodes in the DAG serve as the anchor nodes. Note that during the entity and relation assignment, we specifically filter out all the degenerated queries, as shown in Fig. D Then we perform post-order traversal of the DAG on the KG, starting from the anchor nodes, obtain set of answer entities this query.
When generating validation/test queries, we explicitly filter out trivial queries that can be fully answered by subgraph matching Grain/
E DETAILS NELL995 DATASET
Here detail pre-processing of the NELL995 dataset, which is originally presented by Xiong et al. (2017). Following Allen et al. 2019). we first combine the validation and test sets with the training set to create the whole know ledge graph for NELL995. Then create validation and test set splits by randomly selecting 20,000 triples each from the whole knowledge graph. Note that we filter out all the entities that only appear in the validation and test sets but not in the training set.
15

---

Published as a conference paper at ICLR 2020
Dataset
Entities
Relations
Training Edges
Validation Edges
Test Edges
Total Edges
FBT5k
14,951
1,345
483,142
50,000
59.071
592,213
FB15K-237
14,505
237
272,115
17,526
20,433
310,079
NEL.9995
63,361
200
114,213
14,324
14,267
142,804
Table 5: Knowledge graph dataset statistics as well as the split into training, validation, and test sets.
Queries
Training
Validation
Test
Dataset
others
1p
others
1p
others
FB15k
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
Table 6: Number of training, validation, and test queries generated for different query structures,
F DATASET STATISTICS
Table summarizes the basic statistics of the three datasets used in our experiments. Table summarizes the basic statistics of the generated logical queries.
G HYPER-PARAMETERS
We embedding dimensionality of d 400 and s 24, a 0.2 for the loss in Eq. 4 We train all types of training queries jointly. In every iteration, we sample a minibatch size of 512 queries for each query structure (details in Appendix D). and sample answer entity and 128 negative entities for each query. We optimize the loss in Eq. 4 [uuiing& Adam Optimizer (Kingma & Ba 2015) with learning rate 0.0001. We train all models for 250 epochs, monitor the performance the validation set, and report the test performance.
H ANALYSIS OF LEARNED BOX OFFSET SIZE
Here we study the correlation between the box size (measured by the L1 norm of the box offset) and the average number of entities that are contained in Ip queries using the corresponding relation. Table T shows the top 10 relations with smallest/largest box sizes. We observe a clear trend that the size of the box has strong correlation with the number of entities the box encloses. Specifically, see that one-to-many relations tend to have larger offset embeddings, which demonstrates that larger boxes are indeed used to model sets of more points (entities).
Top 10 relations with smallest box size
#Ent
Box size
Top relations with largest box size
WEnt
Box size
/architecturel...oo Jowner
1.0
2.3
fcommony .topic
3616.0
147.0
/base/_./dog broods
2.0
4.0
tuseo/...uxooomy
1.0
137.2
leducation.. Campuses
fcommoon/ /Calegooyy
125.6
leducation/ /education institution
1.0
4.6
/basel. /admmmmttamittt area Type
1.0
123.6
loolect/oo
medicinell... Jegal status
114.9
/base/../membee.
1.0
5.1
/pcople/ .poopll....sppuuse /spouse
889.8
114.3
pecople/.../pppoiin by
1.0
Isports/.
113.9
models with this bair color
2.0
5.2
ppcopte/ Srooplo.../ocaatoooo /location of ceremony
132.0
108.4
Meciioall universel....paaeee
1.0
53
Isports/..
83.1
104.5
Jamerican lostball....een
200
6.7
/ushe/...saajjet
495.0
104.2
Table 7: Top 10 relations with smallest/largest box size in FB15k.
16

---

Published as a conference paper at ICLR 2020
I
MRR RESULTS
Method
Avg
1p
2p
3p
3i
ip
pi
2u
up
FB15k
Q2B
0.41
0.654
0.373
0.274
0.488
0.602
0.194
0.339
0.468
0.301
GQE
0.328
0.505
0.320
0.218
0.4.9
0.536
0.139
0.272
0.3
0.244
GQE-DOUBLEE
0.326
0.49
0.3
0.222
0.438
0.532
0.142
0.28
0.285
0.242
FB15k-233
Q2B
0.235
0.4
0.225
0.173
0.275
0.378
0.105
0.18
0.198
0.178
GQE
0.203
0.346
0.193
0.145
0.25
0.355
0.086
0.156
0.145
0.151
GQE-DOUBLE
0.205
0.346
0.191
0.144
0.258
0.361
0.087
0.164
0.144
0.149
NELL995
Q2B
0.254
0,413
0.227
0.208
0.288
0.414
0.125
0.193
0.266
0.155
GQE
0.21
0.311
0.193
0.175
0.273
0.399
0.078
0.168
0.159
0.13
GQE-DOUBLE
0.211
0.309
0.192
0.174
0.275
0.408
0.08
0.17
0.156
0.129
Table MRR results of QUERY2BOX vs. GQE on FB15k, FB15k-22 237 and NELL995.
Method
Avg
1p
2p
3p
2i
pi
2u
up
FB15k
Q2B
0.654
0.373
0.274
0.488
0.602
0.194
0.339
0.468
0.301
Q2B-AVG
0.396
0.648
0.368
0.27
0.476
0.564
0.182
0.295
0.465
0.3
O2N-DEEPSETS
0.402
0.631
0.371
0.269
0.499
0.605
0.181
0.325
0.437
0.298
Q2B-AVG-12 1P
0.324
0.688
0.236
0.159
0.378
0.435
0.122
0.225
0.498
0.178
Q2B- O2BSHAREDOPPSET
0.296
0.511
0.273
0.199
0.351
0.444
0.132
0.233
0.311
0.213
FB15K-237
Q2B
0.235
0.225
0.173
0.275
0.105
0.18
0.198
0.178
02B-AVG
0.219
0.398
0.222
0.171
0.236
0.328
0.1
0.145
0.193
0.177
Q2B-DEEPSETS
0.23
0.395
0.224
0.172
0.264
0.372
0.101
0.168
0.194
0.176
Q2n-AVG-IP
0.196
0.41
0.18
0.122
0.217
0.274
0.085
0.127
0.209
0.145
Q2B TB-SSHREDDOFFET
0.18
0.328
0.18
0.131
0.207
0.289
0.083
0.136
0.135
0.132
NELL995
Q2R
0.254
0.413
0.227
0.208
0.288
0.414
0.125
0.193
0.266
0.155
Q2R-AVG
0.235
0.406
0.219
0.2
0.251
0.342
0.114
0.174
0.259
0.149
Q2E-DEEPSETS
0.246
0.405
0.226
0.207
0.275
0.403
0.107
0.182
0.256
0.153
Q2B-AVG-IP
0.227
0.468
0.191
0.16
0.234
0.275
0.094
0.162
0.332
0.125
Q2B-
S0--SHRRDDFFFETT
0.196
0.318
0.187
0.172
0.228
0.312
0.098
0.156
0.169
0.127
Table MRR results of QUERY2BOX vs. several variants on 15k, FB 15k-237 and NELL995.


Reviews:
[{"review_id": "rJxqx3Fy9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "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.\nInstead, 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.\nFor 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. \nExperiments 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. \n\nStrengths:\n1. 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). \n2. Modeling logical queries into regions in vector space is an interesting idea, and it would be nice to see followup work in this direction.\n3. The paper is nicely written and ablation experiments were helpful.\n4. Compared to the baseline they used, the paper does a better job of modeling complex logical queries.\n\nWeaknesses / Questions:\n1. 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. \n2. 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\n3. 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.\n4. 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.\n5. 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. \n6. How many answers are there on an average for each question. This will better help me understand how hard the dataset actually is. \n7. 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", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1geJGyitH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 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.\n\nMoreover, 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.\n\nA distance measure is used to check the belonging of an entity to a box.\n\nThis 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. \n\nThe experiments show that Query2Box can achieve better results than GQE. Moreover, an ablation study was conducted.\n\nWhile 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.\n\nThe paper is well written, there are no problems in the use of English and in the organization of the paper.\n\nThe 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.\n\nAs 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.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Hklbu1aRKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 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.  ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)