ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs
Authors: Zhanqiu Zhang
Jie Wang
Jiajun Chen
Shuiwang Ji
Feng Wu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Query Embeddings
Knowledge Graphs
Multi-hop Reasoning
Question Answering

Abstract: Query embedding (QE)---which aims to embed entities and first-order logical (FOL) queries in low-dimensional spaces---has shown great power in multi-hop reasoning over knowledge graphs. Recently, embedding entities and queries with geometric shapes becomes a promising direction, as geometric shapes can naturally represent answer sets of queries and logical relationships among them. However, existing geometry-based models have difficulty in modeling queries with negation, which significantly limits their applicability. To address this challenge, we propose a novel query embedding model, namely \textbf{Con}e \textbf{E}mbeddings (ConE), which is the first geometry-based QE model that can handle all the FOL operations, including conjunction, disjunction, and negation. Specifically, ConE represents entities and queries as Cartesian products of two-dimensional cones, where the intersection and union of cones naturally model the conjunction and disjunction operations. By further noticing that the closure of complement of cones remains cones, we design geometric complement operators in the embedding space for the negation operations. Experiments demonstrate that ConE significantly outperforms existing state-of-the-art methods on benchmark datasets.

ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs
Zhanqiu Zhang 1.2
Jie Wangl.2 Jiajun Chen
Shuiwang Ji
Feng Wu 1.2
iCAS Key Laboratory of Technology in GIPAS
University of Science and Technology China
Institute of Artificial Intelligence
Hefei Comprehensive National Science Center
{zqzhang, , jj jjchen)@mail..... ustc. edu. cn,
edu.
Texas A&M University sj @ttau. edu
Abstract
Query embedding (QE) which aims embed entities and first-order logical (FOL) queries in low-dimensional spaces-has shown great power in multi-hop reasoning over knowledge graphs. Recently, embedding entities and queries with geometric shapes becomes a promising direction, as geometric shapes can naturally represent answer sets of queries and logical relationships among them. However, existing geometry-basee
models have difficulty in modeling queries with negation, which significantly limits their applicability. novel query embedding model, namely Cone Embeddings (ConE), which is the first geometry-based QE model that can handle all the FOL operations, including conjunction, disjunction, and negation. Specifically, ConE represents entities and queries as Cartesian products of two-dimensionall cones, where the intersection and union of cones naturally model the conjunction and disjunction operations. By further noticing that the closure of complement of cones remains cones, we design geometric complement operators in the embedding space for the negation operations. Experiments demonstrate that ConE significantly outperforms existing state-of-the-an methods on benchmark datasets.
address this challenge, we propose
Introduction
Multi-hop reasoning over knowledge graphs (KGs)-which which aims to find answer entities of given queries using knowledge from KGs has attracted great attention from both academia and industry recently [24 23 16]. In general, it involves answering first-order logic (FOL) queries over KGs using operators including existential quantification (G), conjunction (A), disjunction (V), and negation ()). A popular approach to multi-hop reasoning over KGs is to first transform FOL query to its corresponding computation graph-wher where each node represents a set of entities and each edge represents logical operation aatitiioo-nnndd then traverse the KG according identify the answer set. However, this approach confronts two major challenges. First, when some links are missing in KGs, it has difficulties in identifying the correct answers. Second, it needs to deal with all the intermediate entities on reasoning paths, which may lead to exponential computation cost.
the computation graph to
To address these challenges, researchers have paid increasing attention to the query embedding (QE) technique, which embeds entities and FOL queries in low-dimensional spaces [12 22 21 25] QE
models associate each logical operator in computation graphs with a logical operation in embedding
"Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

spaces, Given query, QE models generate query embeddings following the corresponding computa- tion graph. Then, they determine whether an entity is a correct answer based on similarities between the query embeddings and entity embeddings.
Among the existing QE models, geometry- based models that embed entities and queries into geometric shapes have shown promising performance [12
I 5 22]. Geometry-based models usually represent entity sets as "regions" (e.g.. points and boxes) in Euclidean spaces and then design set operations upon them. For example, Quxxy2BBox [2 represents entities as points and queries as boxes, If a point is inside box, then the corresponding entity the answer to the query. Compared with non-geod ren-eemmetric methods. geometric shapes provide a natural and easily interpretable way to represent sets and logical relationships among them.
However, existing geometry-based models have difficulty in modeling queries with negations, which significantly limits their applicability. For example, GQE [12 and Query2Box [22 -which embed queries to points and boxes, respectively-canne handle queries with negation, as the complement of a point/box is no longer a point/box. To tackle this problem, Ren & Leskovee [21] propose probabilistic QE model using Beta distributions. However, it does not have some advantages of geometric models. For example, using Beta distributions, is unclear how determine whether an entity is an answer to query as that in the box case 12). Therefore, proposing a geometric QE model that can model all the FOL queries is still challenging but promising.
In this paper, we propose a novel geometry-based query embedding model-namelyy Cone Embeddings (ConF))which represents entities and queries Cartesian products of two-dimensional cones. Specifically, if the cones representing entities are subsets of the cones representing queries, then these entities are the answers to the query. To perform multi-hop reasoning in the embedding space, we define the conjunction and disjunction operations that correspond to the intersection and union of cones. Further, by noticing that the closure of complement of cones are still cones, we correspondingly design geometric complement operators in the embedding space for the negation operations. To the best of our knowledge, ConE the first geometry-basee QE model that can handle all the FOL operations, including conjunction, disjunction. and negation. Experiments demonstrate that ConE significantly outperforms existing state-of-the thrtt methods on benchmark datasets.
2 Related Work
Our work is related to answering multi-hop logical queries over KGs and geometric embeddings.
Answering multi-hop logical queries over KGs. To answer multi-hop FOL queries, path-based methods [30, 17 10 start from anchor entities and require traversing the intermediate entities on the path, which leads to exponential computation cost. Embedding-basee based models are another line of works, which embed FOL queries into low-dimensional spaces. For example, existing works embed queries geometric shapes 12 22 IT [5), probability distributions (21). and complex objects 25).
Our work also embeds queries to geometric shapes. The main difference is that our work can handle all the FOL operations, while existing works cannot.
Other Geometric embeddings. Geometric embeddings are popular in recent years. For example,
geometric operations including translation [3 [8]. rotation [28 26 14 [3], and complex geomet-
ric operations [ [3) have been widely used in knowledge graph embeddings. Other geometric embedding methods also manage to use boxes (6) convex cones [15] 29 19], etc. For example, Lütfüü Özęep et al. [19] use axis-aligned cones to embed ontologies expressed the ALC description logic, and use polars of cones to model negation operators. Recent years have also witnessed the development of embeddings in non- non-Euclice Euclidean geometry, such as Poincaré embeddings [I (0) and hyperbolic entailment cones [8]. Notably, although there exist works that also use cone embeddings [15 29 g 19. they are not designed for the multi-hop reasoning task and their definition of cones different from that in our work.
3 Preliminaries
In this section, we review the background of query embeddings in Section 3.1 and introduce some basic concepts of two-dimensional cones in Section 3.2

---

4
= V, V: AwardW inner (Academy Awards, V)
A wwwootsrrouuueeeeeee (USuced((UAAAA V) Director
Academy
Anaadd Winner
Morter Producd
Complement
Internaction
Anower Frehher
(a) Computation Graph
(b) Cones
Figure I: Examples of computation graph and several cones. In Figure la the natural language interpretation of the query "List all the directors of Ameerccaa movies that win the Academy Awards". In Figure Tb the four cones are: cone with aperture O, sector-cone with aperture on < n, sector-cone with aperture ag = 2x, and cone that the union of two sector-cones.
3.1 Backgrounds
Knowledge Graphs (KGs), Given set of entities (vertices) and set of relations (edges), a knowledge graph 9 = [(s.P), Ps, o²}} V x & V is set of factual triple, where pj E & is predicate, and Si, 0g E V are subject and object, respectively. Suppose that (y( R is binary function r3 V x V + (True, False) corresponding to Pj. where ry 0x) ) = True if and only (s:, Pj, ok) is factual triples. Then, for all (s., Pj. 0k) E G. have ry oR) = True. Note that both & and R are involved with relations, while & is a set of relation instances and R is a set of relational functions.
Logic (FOL). FOL queries in the query embedding literature involve logical operations including existential quantification (3), conjunction (A), disjunction (V), and negation (-). Universal quantification (A) is not included, as no entity connects with all other entities in real-worke KGs [2]]
First-Order
We use FOL queries in its Disjunctive Normal Form (DNF) 77, which represents FOL queries disjunction of conjunctions. To formulate FOL. queries, we assume that Va C anchor entity set, Vi,..., Vi existentially quantified bound variables, and V, is the target variable, ie., the answers to a certain query. Then, a FOL query q in the disjunctive normal form is:
the non-variable
[V3] = V/. 3V,..... V& 61 V...... V
Specifically, e, are conjunctions, i.e., C; = 4: A -... A eim, where eij r V) or -r(vas V) or r(V',V) or -r(V (VV,VVV, V), va E V., V E (V,, V,,..., VaJ, V' (Vi...., VvJ, and V + V".
Using the aforementioned notations, answering query q is equivalent to finding the set of entities [q]l C V, where v E [[q] if and only if q[o] is True.
Computation Graphs. Given query, we represent the reasoning procedure computation graph (see Figure Ta for an example), of which nodes represent entity sets and edges represent logical operations entity sets. We map edges logical operators according to the following rules.
Relation Traversal
Operator P. Given set of entities S V and relational function r E R. the projection operator P outputs all the adjacent entities Uoes (v, r), where (u,rr) ) is the set of entities such that r(v, v') True for all v' Nuu,r).
Operator I. Given sets of entities {S1, S2,..., S,), the intersec- tion operator I performs set intersection to obtain n S..
Disjunction Union Operator U. Given n sets of entities {S1, S2,..., Sn), the union operator U performs set union to obtain S
Negution Operator C. Given an entity S V. C gives $ VASS.
Query Embeddings (QE). QE models generate low low-dimensional continuous embeddings for queries and entities, and associate each logical operator for entity sets with an operation in embedding spaces. Since an entity is equivalent to set with single element and each query g is corresponding to a unique answer set [Ą]], the aim of QE models equivalent to embedding entity sets that can be answers to some queries.
3

---

3.2 Cones in
Spaces
To represent FOL queries as Cartesian products of wwo-dimensional cones, we introduce some definitions about cones and the parameterization method of special class of cones.
Definition 1 (Boyd & Vandenberghe Al). A set C' C I2² is called a cone, if for every x E C and O. have xæ C. A set is convex cone if is convex and a cone, which means that for any D1, D2 E C and A1, X2 2 O, we have 11 + X2 E C.
By letting À 0 in Definition II know that must contain the origin. In view of this property, we define a new operation called poosure-compemenn for cones.
Definition Suppose that C IK² a cone. Then, the closure-complement of C is defined by Ö = cl( 2 (C), where el(.) is the closure of sel.
Next, we introduce a class of cones that can be parameterized in scalable way.
Definition 3. 2D closed cone is called sector-cone, if its flosrre-copplenn or itself convex.
The set of sector-cones is closed under closure complemett and their union and intersection are still cones. Besides, we have the following proposition, whose proof provided in Appendix A.
Proposition 1. A sector-cone is always axially symmetric.
Parameterization of 2D Sector-Cones. Proposition suggests that we can use a pair of parameters to represent two-dimensional sector-cone:
(fax: app) where 6xx E [- Oap E [0,2m]
Specifically, Onx represents the angle between the symmetry axis of the sector-cone and the positive axis. Oap represents the aperture of the sector-cone. For any points in the cone, its phase will in (0.x 0pp/ /2, fax /p// 2 Figure gives examples of several (sector-)cones, One may notice that sector-cones share some similarities with boxes defined in Query2Box, which also involves region representations. However, we argue that sector-cones are more expressive than boxes, of which the details are provided in Appendix F.
Let K be the space consisting of all (fax. 0up) We represent arbitrary sector-cone Co as Co = (fax, 0ap) E K. Then, for a d-ary Cartesian product of sector-cones
C= x C2 x Ca.
represent via d-dimensional vector in Kd.
C= ((0) 01 ( .... (0d 0g)) c CK..
where Bi E [- R), 6 [0, 2T). for i 1.... d. Or equivalently, C (0ax, Oxp), where
am = (f)....., (d)) E [-T,, T. )²d and 0ap = (B....... ap E [0, 2mT²
Cone Embeddings
In this section, propose Cone Embeddings (ConE) for multi-hop reasoning over KGs. We first introduce cone embeddings for conjunctive queries and entities in Section 4.1 Afterwards, we introduce the logical operators and the methods learn ConE in Sections
and
4.1 Cone Embeddings for Conjunctive Queries and Entities
As introduced Section 3.1. conjunctive queries constitute the basis of all queries in the DNF form. Embeddings of all queries can be generated by applying logical operators to conjunctive queries' embeddings. Thus, we design embeddings for conjunctive queries in this section. We model queries with disjunction using the Union Operator 24 in Section 4.2
In general, the answer entities to a conjunctive query q have similar semantics. For example, answers to the query that "List all the directors of American movies" should all be persons; answers to the query that "List all the Asian cities that ever held Olympic Games" should all places. If we embed an entity set [q]] into embedding space, expect entities [g] to have similar embeddings. Thus,

---

W
K
%
(a) Projection
(b) Intersection
(c) Union
(d) Complement
(c) Distance
Figure 2: ConE's logical operators and distance function, of which the embedding dimension d 1.
we expect their embeddings to form a "region" the embedding space. If the embedding of an entity inside the region, then the entity is likely to be answer. Further, we can find semantic center and a boundary for the region, where the semantic center represents the semantics of [q] and the boundary designates how many entities are in [4]
To model the embedding region of [y]; we propose to embed to Cartesian product of sector-cones. Specifically, we use the parameter 0ix to represent the semantic center, and the parameter 0% to determine the boundary of [9]] If we use a d-ary Cartesian product, i.e., the embedding dimension is d, we define the embedding of [[]] as
V = (0ax, ap.)
where Pm E [--,, 1T axes and aap E 00, 2m]d apertures.
equivalent an entity set with single element, i.e., fo}. We propose to represent an entity Cartesian product of cones with apertures 0, where the axes indicates the semantics of the entity. Formally, the embedding dimension d, the cone embedding of v is v (0xx, 0), where ax
An entity
[-T,, n. x)d is the axis embedding and 0 a d-dimensional vector with all elements being
4.2 Logical Operators for Cone Embeddings
In this section, we introduce our designed logical operators of ConE in the embedding space, including projection, intersection, union, and complement.
worth noting that, the composition logical operators may lead non-sense queries. For example, the queries "List the intersection/union of American movies and non-American movies" and "List the intersection of American movies and Asian movies" make no sense real-world applications. However, the main aim of a query embedding model is to represent all entity sets that can be answer to some real-world query. Therefore, we do not need to model the entity sets that only correspond to theoretically possible queries (21].
Projection Operator The goal of to represent an entity's s adjacent entities that are linked by given relation. It maps an entity set to another entity set (see Figure 2a). Thus, we define relation-dependent function in the embedding space for P:
Jr
We implement fr in neural way. First, represent relations relational translations of query embeddings and assign each relation with an embedding r (6mrr, Oap.r). Then, we define f, as
fr(V)) g(MLP(( m Oup 0ap.rl)
where MLP 2d 2d is multi-layer perceptron network, [: is the concatenation of two vectors, and is function that generates 0'2 [- rdd and O' [0, 2nrdd. We define
f = x tanh(A)æ;), [g(x)); - -000 x tanh()22:)) +
if d, if > d.
-
where (x)); denotes the i-th element of (x), A and xy are two fixed parameters to control the scale. Note that the range of the hyperbolic tangent function (tanh) open sets. Thus, cannot indeed get the boundary value gii π and g 0, 2n. However, when we implement g in experiments, up the value of y can be very close to 0 and 2T,, which is equivalent to the closed set numerically.
Intersection Operator Given a query y that the conjunction conjunctive queries yis the goal of I is to represent [q] ni [[]]]] Since the conjunction of conjunctive queries still conjunctive
5

---

queries, the entities in [q] should have similar semantics. Recall that we only need to model entity sets that can be answers. We still use Cartesian product of sector-cones to represent [9] (see Figure 2b). Suppose that V = (0.x, Oap) and V. (ax.. (s.sp) are cone embeddings for [[q] and [%1 respectively. We define the intersection operator as follows:
2x SemanticAverager V Ve
On
0g CardMin(V; g1:-.13 V
where SemanticAveragee/ and CardMin(-)) generates semantic centers and apertures, respectively. In the following, we introduce these two functions in detail.
SemanticAverage. As the semantic center of VGg. 0xx should be close to all the semantic centers 0a.x. Thus, we propose to represent 0ax as a semantic average of 0a,xx. We note that the ordinary weighted average may lead to inconsistent semantics. For example, when d = if 01.ax π and 22.0x = -T + (0 < é < TT /4,, then we expect 9x to be around я. However, we use the ordinary weighted sum, Oax will be around 0 with high probability. To tackle this issue, propose a semantic average scheme, which takes periodicity of axes into account. For a figure illustration of the difference between the ordinary and semantic average, please refer to Appendix D.
Specifically, we first map ا to points on the unit circle. Then, compute the weighted average of the points using attention mechanism. Finally, map the points back to angles that represent axes. Formally, the computation process is
y
Σ a, cos(Or,.v) sin sin(O,,, (0,,,)), 1=1
O2x Arg(x.y),
where cos and sin clement-wise cosine and sine functions; a, E Rd are positive weights vectors the element-wise multiplication; Arg(-) is the function that computes arguments of (a Cartesian of) 2D points. Noticing that the weights a, relevant to both axes and apertures, we compute [a:l; via the following attention mechanism:
that satisfy Σ [a:li = for all j = ......de
(Mp((MMP(O.) (0..x Oz 0s.x + 0 /2)l)
[
1= cxp( MLP(( 0 Ox.ap/ 2; OR... O ak.pp/21 21)))
where MIP: 2dd + Rd is multi-layer perceptron network, [:: is the concatenation of two vectors. can see 0 0/.p/2 and 0 + 0ump/ 2 as the lower and upper bound of sector-cones.
We use Arg(.) to recover angles of 2D points. Suppose that B3 = arctan((y): ([)):)((())))))))))))))))))>))) [[))). then
B3 + n. if [x];
0, [y], 0,
[0x)
B: n, if [x), 0, [y]s 0, otherwise.
B,,
Note that [x); = 0 will lead to an illegal division. In experiments, we manually set [x]; to be a small number (e.g., 10-3) when [x): 0.
CardMin. Since [q] is the subset all [q.]. di should be no larger than any apertures 0j Therefore, we implement CardMin by a minimum mechanism with cardinality constraints:
g min (ei 8"... ((DeepSets((V) ))=)),
where (-)) is the element-wise sigmoid function, 0j.pp is the i-th element Oj.aps DeepSets(-) is permutation-invant function [3]] Specifically, DeepSets( (V,, } is computed by
MIP Σ
MIP (0 02 2 0jap/ /2)
Union Operator 44 Given query y that is the disjunction of conjunctive queries yi the goal the union operator 2/ is to represent [g] U As noted by Ren et al. [22), directly modeling the
disjunction leads to unscalable models. Thus, we adopt the DNF technique 22 which the union operation only appears in the last step in computation graphs.

---

Suppose that V. aax app are cone embeddings for [qll- To represent the union of several cones (see Figure 2cb, we represent [4] as set of V g.
4 h
where n may be various in different queries. Equivalently, V can be written as Vil (4(0),xx (.pp)..... (0), a.x 0p.ap) ).. ...,, .........ffff.. of i.p....... (Oh,ax 0 (..p)))
As {(0 ii l..p)..... (0) ax. 0 ap)) are the union sector-cones, it is also a cone. Thus, the cone embedding of q also Cartesian product of woodimensional cones.
Complement Operator C. Given an conjunctive query q and the corresponding entity set [9]] the aim of C is to identify the set [~g]] which is the complementary of [g]. i.e., VVllg- Since the set of sector-cones closed under closure-complee compllme, we define C using the complemnt Thus, the apertures of V, q plus the apertures of V should be vector with all elements being 2T.
Moreover, to represent the semantic difference between [q] and [[<]]] we assume that their semantic centers to be opposite. Please refer to Figure 2d for a figure illustration.
Suppose that V, (0ax: Qap) and V Y-4 (0 ). We define the complement operator as:
10 n,
if [ax]i 0, if [0x]: 0,
0
axx] + n,
(0 2T (0pp)-
4.3 Learning Cone Embeddings
To learn cone embeddings, we expect that the cone embeddings of entities E [v] are inside the cone embeddings of g. and the cone embeddings of entities v' [g] are far from the cone embedding of q. This motivates us to define distance functiin to measure the distance between a given query embedding and an entity embedding, and a training objective with negative sampling.
Distance Function. We first define the distance function for conjunctive queries. Inspired by Ren al. 22 divide the distance d into two parts- outside distance d, and the inside distance d,. Figure 2e gives an illustration of the distance function d. Suppose that v = (0" 0), V. = (6xx. amp)
0
aap! 2 and Oy = 0ax + aap/ 2. We define the distance as deon (v: V.) = dv; Vgy) + Ad;(v; V..).
The outside distance and the inside distance are
d, = min {|sin (0", 0,.) /2|, Isin (0 0v) /21H d; = min {[sin (0% 6.x) /2| |sin (0mp) /21
where || Ilis the L, norm, sin(-) and min(-) (-) are element-wise sine and minimization functions. Note that as axes and apertures are periodic, we use the sine function to enforce two close angles have small distance. The parameter À E (0, 1) is fixed during training, so that v is encouraged to be inside the cones represented by VG. but not necessarily be equal to the semantic center of V
Since we represent the disjunetive queries as a set of embeddings, we cannot use deon to directly compute the distance. Nonetheless, the distance between a point and the union of several sets is equal to the minimum distance between the point and each of those sets. Therefore, for query q 41 V ... V In in the Disjunctive Normal Form, the distance between q and an entity is
disso (v; vz)) = min (v; ) (v; )=. }}-
If we use V, to represent embeddings of both kinds of queries, the unified distance function d is d(v: Vg) = [conn() (v; Vg), if is conjunctive queries,
ddis (v; Va), if q is disjunctive queries.
Training Objective. Given training set of queries, we optimize negative sampling loss
1 ' - log logo(d(v Vg) 7),
L = log a d(v V.))
where y > 0 is a fixed margin, v E [[q] is a positive entity, 2f & [9] is the i-th negative entity, & is the number of negative entities, and a is the sigmoid function.
7

---

Table MRR results for answering queries without negation (2, A, V) on FB15k, FB237, and NELL.
The results of BETAE are taken from Ren & Leskovec [21]
Dataset
Model
1p
2p
3p
2i
pi
ip
2u
up
AVG
GQE
53,9
15.5
11.1
40.2
52.4
27.5
19.4
22.3
11.7
28.2
Q2B
70.5
23.0
15.1
61.2
71.8
41.8
28.7
37.7
19.0
40.1
FB15k
BETAΣ
65.1
25.7
24.7
55.8
66.5
43,9
28.1
40.1
25.2
41.6
ConE
73.3
33.8
29.2
64.4
73.7
50.9
35.7
55.7
31.4
49.8
GQE
35.2
7.4
5.5
23.6
35.7
16.7
10.9
5.8
16.6
Q2B
41.3
9.9
7.2
31.1
45.4
21.9
13.3
11.9
8.1
21.1
FB237
BEТАΣ
39.0
10.9
10.0
28.8
42.5
22.4
12.6
12.4
9.7
20.9
ConE
41.8
12.8
11.0
32.6
47.3
25.5
14.0
14.5
10.8
23.4
GQE
33.1
12.1
9.9
27.3
35.1
18.5
14.5
8.5
9.0
18.7
Q2B
42.7
14.5
11.7
34.7
45.8
23.2
17.4
12.0
10.7
23.6
NELL
BЕTАE
53.0
13.0
11.4
37.6
47.5
24.1
14.3
12.2
8.5
24.6
ConE
53.1
16.1
13.9
40.0
50.8
26.3
17.5
15.3
11.3
27.2
5
Experiments
In this section, we conduct experiments to demonstrate that: 1) ConE is powerful model for the multi-hop reasoning over knowledge graphs; 2) the aperture embeddings of ConE are effective in modeling cardinality (i.e., the number of elements) of answer sets. We first introduce experimental settings in Section S. ConE is available GitHub hattps://gitonn wwt.://AAALaaa---SS////////
[3.] and then present the experimental results and and
The code of
5.1 Experimental Settings
We adopt the commonly used experimental settings for query embeddings 12 22 21
Datasets and Queries. We three datasets: FB15k 2), FBI FB-5k-237 (FB237) 277 and NELL995 (NELL) 30 QE models focus on answering queries involved with incomplete KGs. Thus, we aim find non-trivial answers to FOL queries that cannot be discovered by traversing KGs. For fair comparison, we use the same query structures as those in Ren & Leskovee (21]. The training and validation queries consist of five conjunctive structures (lp/2p/3p/ 3tpp/3p22/33 and five structures with negation (2in / impp/ fipp/mi/in pin). We also evaluate models' generalization ability, i.e., answering queries with structures that models have never seen during training. The extra query structures include ip/ /2//up Please refer to Appendix B.1 for more details about datasets and query structures.
mmipinn.
Training Protocol.
Adam [3 the optimizer, and use grid search to find the best hyperparameters based on the performance on the validation datasets. For the search range and best hyperparameters, please refer Appendix B.2.
We
Evaluation Protocol. We use the same evaluation protocol as that in Ren & Leskovec (1]. We first build three KGs: the training KG Grain- the validation KG Gvalid, and the test KG Geest using training edges, training+validation edges, training-validation--oo. edges, respectively. Given a test (validation) query q, we aim discover non-trivial answers [4] lea \g]] valid ([9] Iran) In other
words, to answer an entity, we need to impute at least one edge to create an answer path to it. For each non-trivial answer of a test query the rank as r and calculate the Mean Reciprocal Rank (MRR), of which the definition is provided in Appendix B.3. Higher MRR indicates better performance.
rank it against non-answer entities V V'I[glees-- We denote
Baselines. We compare ConE against three state-of satte-of-the-e the-art models, including GQE [2], Query2Box (Q2B) (22). and BETAE (21). GQE and Q2B are trained only five conjunctive structures they cannot model the queries with negation. Since the best embedding dimension d for ConE is 800, we retrain all the baselines with d 800. The results of GQE and Q2B are better than those reported in Ren Leskovec (21) while the results of BETAE become slightly worse. Therefore, we reported the results of GQE and Q2B with 1600 and BETAE with d = 400. For the results of BETAE with = 800, please refer to Appendix C.I.

---

Table 2: MRR results for answering queries with negation on FB15k, FB237, and NELL. The results of BETAE are taken from Ren & Leskovec [2]]
Dataset
Model
2in
3in
inp
pin
pni
AVG
BETAE
14.3
14.7
11.5
6.5
12.4
11.8
FB15k
ConE
17.9
18.7
12.5
9.8
15.1
14.8
BETAE
5.1
7.9
7.4
3.6
3,4
5.4
FB237
ConE
5.4
8.6
7.8
4.0
3.6
5.9
BETAE
5.1
7.8
10.0
3.1
3.5
5.9
NELL
ConE
5.7
8.1
10.8
3.5
3.9
6.4
5.2
Main Results
We compare ConE against baseline models on queries with and without negation. We run our model five times with different random seeds and report the average performance. For the error bars of the performance, please refer to Appendix C.5.
Queries without Negation. Table shows the experimental results on queries without negation, i.e., existentially positive first-order (EPFO) queries, where AVG denotes average performance. Overall, ConE significantly outperforms compared models. ConE achieves on average 19.7%, 12.0%, and 10.6% relative improvement MRR over previous state-of-the-art BETAE on the three datasets, which demonstrates the superiority of geometry-based models. Compared with Q2B, which uses Query2Box to embed queries, ConE gains up to 24.2% relative improvements. ConE also gains an impressive improvement on queries ip/ ip/pi/ /u/ 2u/up, which are not in the training graph. For example, ConE outperforms BETAE by 38.9% for 2u query on FB15k. The results show the superior generality ability of ConE. Since ConE is capable of modeling complement, we can also implement disjunctive queries using De Morgan's 's law. However, using De Morgan's 's law always results in sector-cones, which may be inconsistent with the real set union. Thus, the models with DNF outperforms those with De Morgan's 's law. We include the detailed results in Appendix C.2 due to the space limit.
Queries with Negation. Table shows the results of ConE against BETAE on modeling FOL queries with negation. Since GQE and Q2B are not capable of handling the negation operator, we do not include their results in the experiments. Overall, ConE outperforms BETAE by large margin. Specifically, ConE achieves on average 25 25.4%, 9.3%, and 8.5% relative improvement MRR over BETAE on FB15k, FB237, and NELL, respectively.
Table 3: Spearman's is rank correlation between learned aperture embeddings and the number of queries' answers on FB15k. The results of Q2B and BETAE are taken from Ren & Leskovec (2
Model
1p
2p
3p
2i
3i
pi
ip
2in
3in
inp
pin
pni
Q2B
0.30
0.22
0.26
0.33
0.27
0.30
0.14
BETAR
0.37
0.48
0.47
0.57
0.40
0.52
0.42
0.62
0.55
0.46
0.47
0.61
ConE
0.60
0.68
0.70
0.68
0.52
0.59
0.56
0.84
0.75
0.61
0.58
0.80
5.3 Modeling the Cardinality of Answer Sets
As introduced in Section 4.1 the aperture embeddings can designate the cardinality (i.e., the number of elements) of [q]. In this experiment, we demonstrate that although we do not explicitly enforce ConE to learn cardinality during training, the learned aperture embeddings effecttve in modeling the cardinality of answer sets. The property partly accounts for the empirical improvements of ConE.
We compute the correlations between learned aperture embeddings and the cardinality of answer sets. Specifically, for the cone embedding V. (0ax, 0ap) of given query 9. we use the L₁ norm of 0up to represent the learned cardinality of [q]. Then, we compute the Spearman's 's rank correlation (SRC) between the learned cardinality and the real cardinality, which measures the statistical dependence between the ranking of two variables. Higher correlation indicates that the embeddings can better model the cardinality of answer sets. As we model queries with disjunction using the DNF technique, we do not include the results of disjunctive queries following Ren & Leskovee [1].

---

Table Bl shows the results of SRC for ConE, Query2Box (Q2B), and BETAE on FB15k. For the results on FB237 and NELL, please refer to Appendix C.3. As Query2Box cannot handle queries with negation, we do not include its results on these queries. On all query structures, ConE outperforms the previous state-of-the-an method BETAF. Note that BETAF is a probabilistic model, of which the authors claim that it can well handle the uncertainty of queries, i.e., the cardinality of answer set. Nonetheless, ConE still outperforms BETAE by a large margin, which demonstrates the expressiveness of cone embeddings. We also conduct experiments using Pearson's 's correlation, which measures the linear correlation between two variables. Please refer to Appendix C.3 for the results.
5.4 The Designed Operators and the Real Set Operations
As introduced in Section 4.2 the designed union (using DNF technique) and complement operators for ConE are non-parametric. They correspond to exact set union and complement. Meanwhile, we define neural operators to approximate the projection and intersection operators to achieve a tractable training process and better performance. Notably, the designed neural operators may not exactly match the real set operations. However, experiments some example cases demonstrate that these neural operators provide good approximations for real set operations. In the following, we show the experimental results for the operators including projection and intersection. In all experiments, the ConE embeddings are trained on FB15k.
Projection. Suppose that a set A is included by set B, then we expect the projection of A is also included by the projection of B. We randomly generate 8000 pairs of sector-cones (A,, B.). where A; C B,, Then, for each i, we randomly select relation ri and calculate the projections Pr. (A,) and Pr. (B.). Ideally, the projected cones should satisfy Pr: (A:) C Pr. (B,). We calculate the ratio T2- IPr, (A,) (B,)l/
(A,)l to measure how many elements in Pr, (A,) are included in P., (4)) (B.). Finally, we get an average ratio r = 0.8113. That is to say, the learned Pr, (A.)
included in Pr. (A.) with high probability. The learned projection operators approximate the real set projection well.
To validate that the learned intersection can well approximate real set intersection, we randomly generate 8000 pairs of sector-cones (C,, D:). where C, n D; is not guaranteed to be sector-cone. Then, we generate embeddings I(C,, D:) for the intersection C; n D; Ideally, the learned cones I(C,, D.) should be the same as the real cones C, n D; We calculate the ratio [[(C,, D:) n (C, n D.), D,) U (C. n D:) to measure the overlap between I(C,, D:) and C, n D,, and obtain an average ratio of 0.6134. Note that the experiments are conducted on the test set, and did not explicitly train our model on these queries. The relatively high overlap ratio r demonstrates that the learned intersection is a good approximation of the real set intersection.
Intersection.
We further conduct experiments to demonstrate that the learned intersection operators can well handle empty intersections. Following Ren et [22, on FB15k, we randomly generate 10k queries of two types: (a) intersection queries with more than five answers, and (b) intersection queries with empty answer sets. We found that the average aperture 2.495 for type (a) queries, while 1.737 for type (b) queries. The results demonstrate that although we have never trained ConE on the type (b) queries, the empty intersection sets are much more likely to have smaller apertures than queries with non-zero answers (with a 0.9632 ROC-AUC score). In other words, though we did not train ConE on datasets with empty intersection sets, we can distinguish empty answer sets by the learned apertures.
We also conduct experiments to demonstrate the difference between the learned union operator with De Morgan's 'ss law and the real set union. Please refer to Appendix C.6 for details.
6 Conclusion
In this paper, we propose novel query embedding model, namely Cone Embeddings (ConE), to answer multi-hop first-order logical (FOL) queries over knowledge graphs. We represent entity sets as Cartesian products of cones and design corresponding logical operations. To the best of our knowledge, ConE the first geometric query embedding models that can model all the FOL operations. Experiments demonstrate that ConE significantly outperforms previous state-of-the-art models on benchmark datasets. One future direction to adapt ConE to queries in the natural language, which will further improve ConE's 's applicability.
10

---

Acknowledgments and Disclosure of Funding
We would like thank all the anonymous reviewers for their insightful comments. This work was supported in part by National Science Foundations of China grants 61822604, U19B2026, 61836006, and 62021001, and the Fundamental Research Funds for the Central Universities grant WK3399000004.
References
[1] Balazevic, I., Allen, C., and Hospedales, T. Multi-relational poincaré graph embeddings. In Advances in Neural Information Processing Systems, 2019.
[2] Bollacker, K., Evans, C., Paritosh, P., Sturge, T., and Taylor, J. Freebase: A collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 1247-1250, 2008.
[3] Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O. Translating em- beddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26, pp. 2787-2795, 2013.
[4] Boyd, S. and Vandenberghe, L. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
[5] Das, R., Neelakantan, A., Belanger, D., and McCallum, A. Chains of reasoning over entities, relations, and text using recurrent neural networks. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume Long Papers, pp. 132-141, 2017.
[6] Dasgupta, S., Boratko, M., Zhang, D., Vilnis, L., Li, X., and McCallum, A. Improving local identifiability in probabilistic box embeddings. In Advances in Neural Information Processing Systems, 2020.
[7] Davey, B. A. and Priestley, H. A. Introduction lattices and order. Cambridge university press, 2002.
[8] Ganea, O., Becigneul, G., and Hofmann, T. Hyperbolic entailment cones for learning hierarchi- cal embeddings. In Proceedings of the 35th International Conference Machine Learning. volume 80, pp. 1646-1655, 2018.
[9] Garg, D., Ikbal, S., Srivastava, S. K., Vishwakarma. H., Karanam, H., and Subramaniam, L. V. Quantum embedding of knowledge for reasoning. In Advances in Neural Information Processing Systems, 2019.
[10] Guo, S., Wang, Q. Wang, L., Wang, B., and Guo, L. Knowledge graph embedding with iterative guidance from soft rules. In Proceedings of the Thirty-Second AAAI Conference Artificial Intelligence, 2018
[11] Guu, K., Miller, J., and Liang, Traversing knowledge graphs vector space. Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 318-327, 2015.
[12] Hamilton, W. L., Bajaj, P., Zitnik, M., Jurafsky, D., and Leskovec, J. Embedding logical queries on knowledge graphs. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 2030-2041, 2018.
[13] Kingma, P. and Ba, J. Adam: method for stochastic optimization. In Proceedings of the International Conference on Learning Representations (ICLR), 2015.
[14] Lacroix. T.. Usunier, N., and Obozinski, G. Canonical tensor decomposition for knowledge base completion. In Proceedings of the 35th International Conference on Machine Learning, pp. 2863 2872. PMLR, 2018
[15] Lai, A. and Hockenmaier, J. Learning to predict denotational probabilities for modeling entailment. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pp. 721-730, 2017.
11

---

[16] Li, F.-L., Qiu, M.. Chen, H.. Wang, X., Gao, X., Huang, J., Ren, J., Zhao, Z.. Zhao, W., Wang, L., Jin, G., and Chu, W. Alime assist: An intelligent assistant for creating an innovative e-commerce experience. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 2495 -498- 2017.
[17] Lin, X. V., Socher, R., and Xiong, C. Multi-hop knowledge graph reasoning with reward shaping. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 3243-3253, 2018.
[18] Lin, Y., Liu, Z., Sun, M., Liu, Y., and Zhu, X. Learning entity and relation embeddings for knowledge graph completion. In Proceedings of the Twenty-Ninhh AAAI Conference on Artificial Intelligence, pp. 2181-2187, 2015.
[19] Lütfü Özgep. O., Leemhuis, M., and Wolter, D. Cone semantics for logics with negation. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence.
[20] Nickel, M. and Kiela, Poincaré embeddings for learning hierarchical representations. In Advances in Neural Information Processing Systems, 2017.
[21] Ren, H. and Leskovec, J. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In Neural Information Processing Systems, 2020.
[22] Ren, H., Hu, W., and Leskovec, J. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference Learning Representations, 2020.
[23] Saxena, A., Tripathi, A., and Talukdar, P. Improving multi-hop question answering over knowledge graphs using knowledge base embeddings. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 4498 4508,, 2020.
[24] Sun, H., Bedrax- Weiss, T., and Cohen, W. PullNet: Open domain question answering with iterative retrieval knowledge bases and text. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp.
2019.
[25] Sun, H., Arold, A. O., Bedrax-Weiss T., Pereira, F., and Cohen, W. W. Faithful embeddings for knowledge base queries. In Advances in Neural Information Processing Systems, 2020.
[26] Sun, Z., Deng, Z.-H., Nie, J.-Y.. and Tang, J. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representattinss 2019.
[27] Toutanova, K. and Chen, D. Observed versus latent features for knowledge base and text inference. In 3rd Workshop Continuous Vector Space Models and Their Compositionality, 2015.
[28] Trouillon, T., Welbl, J., Riedel, S., Gaussier, E., and Bouchard, G. Complex embeddings for simple link prediction. In Proceedings of The 33rd International Conference Machine Learning, volume 48, pp. 2071-2080, 2016.
[29]
Vendrov, I., Kiros, R., Fidler, S., and Urtasun, R. Order-embeddings of images and language. In 4th International Conference on Learning Representutions, 2016.
[30] Xiong, W., Hoang, T., and Wang, W. Y. DeepPath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 564 573, 2017.
[31] Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J. Deep sets. In Advances in Neural Information Processing Systems, 2017.
[32] Zhang, Z., Cai. J., and Wang, J. Duality-induced regularizer for tensor factorization based knowledge graph completion. In Advances in Neural Information Processing Systems, 2020.
[33] Zhang, Z. Cai, J., Zhang, Y., and Wang, J. Learning hierarchy-aware knowledge graph embeddings for link prediction. In Proceedingy of the Fourth AAAI Conference on Artificial Intelligence, 2020.
12


Reviews:
[{"review_id": "wd2VpHY96i", "reviewer": "Reviewer_65PB", "summary": "A recent line of knowledge graph (KG) query systems \"compiles\" the query into an embedded representation, which is interpreted as a geometric region and then used to find response entities whose embedding representations are contained within the region.  Query2box is an early example, where the regions are multidimensional boxes or rectangles.  To be useful, the regions have to be simple, closed under query operators, and capable of being characterized using a few parameters.  Union (disjunction) and negation have therefore created problem for boxes.  This paper replaces boxes with a Cartesian space of cones in 2d.  By restricting the family of permitted cones and disjunction to the last step of any query, the authors argue that their cone family is closed under query operators.  Experiments with benchmarks that have a good diversity of query graph structures show promising results.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Motivation and novelty of problem statement:\n\nThe problem statement was established in Query2box.\nIt is well-motivated, although the claimed \"exponential\" complexity of discrete graph alignments vs. efficiency of query embedding methods is somewhat debatable.  Plenty of SPARQL implementations do fine on these query classes by clever indexing and pruning.\n\nMoreover, even from the ML perspective, generating a region of embedding space with various assumptions about the compactness of and distances in the region seems more fraught with difficulties than testing a candidate entity against a query, in a discriminative manner.  This also depends on the fanout of a query operator.  See further discussion on table 1 later.  However, the current authors do not really own that debate.\n\n\nClarity of presentation:\n\nThe paper is quite well written. However, there is one high level issue.  It could well be a limitation in my understanding.\n\nTo discuss it, we first need a mild definition.  Let's say a cone in 2d is simple if it has only one contiguous region, i.e., is defined by exactly two rays from the origin.  A simple cone may be convex (if the aperture is at most $\\pi$) or non-convex.  A convex cone is always simple.  The complement of a simple cone is also simple.\n\nThere is a 1-1 mapping between the Cartesian space of $K$ simple cones and $K$-dimensional boxes.  So, in principle, ConE goes beyond query2box only because they allow a larger family of cones.\n\nThe authors define \"sector-cones\" (definition 3).  A sector-cone or its closure-complement is convex.  If a sector-cone is convex, it is simple.  Otherwise its complement is simple and therefore so is it.  So it seems a sector-cone is always simple.\n\nNow even if there is a bijection between $K$ simple cones and $K$-dimensional boxes, non-convex loss optimization can behave  differently, but it seems to be important to understand the core reason behind the superiority of ConE over Query2box.\n\nQuality and depth of technical proposal/\nDetailed comments:\n\nL81 Careful about terminology here: relation instance from $\\mathcal{E}$ vs. relation type from $\\mathcal{R}$.\n\nL85 triples -> triple\n\nL124 near Defn 3 --- give more examples to clarify the expressiveness boundaries of sector-cones, particularly concerning the discussion about simple cones above.\n\nL150 \"should have similar embeddings\" --- this is actually quite questionable, and there is some anecdotal evidence (sorry, word of mouth) that even entity sets belonging to what look like coherent types to humans do not occupy tight or compact regions in typical embedding spaces.\n\nL159 remove the two occurrences of \"embeddings\"\n\nL190 After staying with the paper reasonably well up to this point, and noting the visual definition of intersection in Fig 2(b), SemanticAverage and CardMin come as surprises.  Why should we define the intersection axis as any kind of average?  Aren't the bounding rays of the intersection cone defined in terms of a bunch of min and max operators?\n\nL213 ... and if you are using DeepSets to define the intersection aperture, small wonder about the numbers in Table 3; section 5.3.  I was hoping this would arise naturally out of ConE magic.\n\nL223 \"is also a cone\" ... but is it a sector-cone?\n\nTable 1 is intuitive.  The trend 1p > 2p > 3p is generally sustained from prior work.  3i gets a large boost, but that is the case even for Q2B --- basically, chaining out is progressively harder with chain length, but intersections are easy (which has been the experience with indexed/combinatorial graph traversal approaches as well).\n\nOn negation queries the gains are modest, again raising the question about fundamental model capacity over boxes.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact: N/A\n\nLimitations: Please provide clarification for the questions raised in the main review field.\n\nTo a first order, the appeal of this paper is in improved accuracy, not a new modeling or representation insight.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5 hours"}, "extra_text": {}}, {"review_id": "v9scu0wLAGD", "reviewer": "Reviewer_Zjbx", "summary": "The paper proposes a new framework for embedding first-order logic (FOL) queries over knowledge bases using region-based embeddings. The embedding space is a Cartesian product of 2D cones. Entities are embedded in the same space with 0-aperture cones (ray starting at origin).\n\n- Authors provide the relevant foundation to cones in 2D space, the final Cartesian product space, and suggest parameterizations of projection, intersection, union, and complement operations.\n- The choice of using cones facilitates complement operation.\n- Authors demonstrate empirical improvements over past work in FOL query embedding.\n- While the proposed cone-based region embeddings allow for clear descriptions for intersection, union, and complement, the implementation does not strictly enforce these geometric concepts.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality\n\n- The work builds on past work on FOL query embedding and suggests new parameterization using cones. Set complements of cones are also cones and lie in the same embedding space. This was a limitation of past work that relied on geometrical embeddings (e.g. complement of box embeddings is no longer a box). This choice allows the representation to model all FOL operations.\n- It has appropriately cited past related work and placed itself with respect to it.\n\n### Quality\n\n- The representation capacity of the proposed method is demonstrated with empirical results. The baselines are fairly compared. The ability to tackle set complement is also compared with relevant baselines.\n- **(1) Minor clarification**: ConE embeddings are trained with *d*=800. Is this space the Cartesian product of 800 cones (so a total of 1600 parameters) or 400 cones (800 parameters)? If is it the former, then shouldn't the baselines also have 1600 dimensional embeddings?\n- **(2) Strong claim**: Line 297 claims that cone embeddings are better geometric representations than box embeddings. I believe this is a very strong claim since it only compares against specific parameterizations of box embeddings. In particular, the notion of intersection and union of box embeddings is still an active area of research and there isn't a universally accepted parameterization.\n\n### Clarity\n\n- The paper provides the necessary mathematical background to understand the proposed approach of conical embeddings.\n- Hyperparameters are reported in sufficient detail to recreate the experimental results.\n\n### Significance\n\n- The work improves the state of the art in a demonstrable way.\n- There is scope to experiment with other parameterizations of the same underlying conical embeddings space for marginal improvements.\n- There is also scope to view the apertures in a probabilistic framework (the fraction of the entire space covered by a cone can be interpreted as likelihood similar to probabilistic box embeddings)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "### Limitations\n\n(1)\n\nThe set of sector cones (used to represent the query) is not closed under union and intersection.\n\n(2)\n\nThe proposed parameterization of the intersection operation does not correspond exactly to set intersection.\n\nAs a concrete example, consider a space of a single 2D cone (i.e. *d*=1). The intersection of two sector cones with $C_1$ = ($\\theta_{ax} = 0$, $\\theta_{ap} = \\pi / 2$) and $C_2$ = ($\\theta_{ax} = \\pi / 4$, $\\theta_{ap} = \\pi / 2$), have an intersection of $C_I$ = ($\\theta_{ax} = \\pi / 8$, $\\theta_{ap} = \\pi / 4$). This is not guaranteed by the parameterization i.e. an entity can belong to $C_1$ and $C_2$ but not to $I(C_1, C_2)$ as defined in sec 4.2.\n\n(3)\n\nThe definition of an entity belonging to the answer set is not clear. This is especially confusing when using $d > 1$. The use of both *inside* and *outside* distance in the scoring seems to convey that an entity can belong to the answer set as long as it intersects any of the *d* cones in the query embedding. In this case, an entity can have some overlapping components with both the query and the complement of the query.\n\nAlternatively, we can define that an entity belongs to the answer set only if it intersects all of the *d* cones in the query embedding. Under this definition, the proposed complement operation is too restrictive since an entity with just one mismatched cone dimension should belong to the complement.\n\n- - -\n\nThe geometric embeddings help build intuitions/mental pictures when *d*=1 but the geometry isn't strictly imposed always. It would be useful to explicitly discuss this along with barriers to implementing fully geometric operations. \n\n### Societal Impact\n\nThe work does not pose issues in terms of negative societal impacts besides concerns noted in the supplementary materials.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PnhAmy389J", "reviewer": "Reviewer_jq2v", "summary": "This paper represents a novel approach to learning embeddings for entities and relations from a knowledge base that are capable of directly encoding *reasoning* (i.e. FOL). The principal representation proposed for this representation is a *cone* (i.e. a set which is closed under multiplication by a positive scalar) which is motivated by the fact that cones are closed under intersection and complements. In practice, the authors use *sector cones*, which leads to some incongruity between the original motivation and the model in practice (eg. sector cones are not closed under intersection or union). Even so, the authors apply this embedding method to several standard logic embedding tasks and demonstrate significant performance improvements.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Update after Rebuttal\nThe authors have performed extensive experiments to aid in understanding how the neural operators approximate their geometric analogs as well as various potential logical discrepancies that exist between the interaction of negation and union / intersection. I appreciate the time and effort which went into these additional experiments, and feel they add significant value to the paper. I would strongly encourage the authors to include this level of detailed analysis in a polished way in the final submission.\n\n### Overview\n\n**Originality:** The approach of using this form of cones is significantly novel, and the approaches to representing relations, intersections, and unions combine well-known techniques in a reasonable way.\n\n**Quality:** The most concerning aspect from the perspective of quality is the distinction between motivation and practice, as mentioned in the summary. Not only is the set of sector cones not closed under intersection or union, the actual operations used for projection, intersection, and union are not necessarily self-consistent (see below). That being said, the empirical evidence in support of the resulting model, regardless of it's departure from the initial motivations, is quite strong.\n\n**Clarity:** The submission is reasonably clear, and gives enough mathematical detail to reproduce the results.\n\n**Significance:** The authors report strong results on the task of logic embeddings, which is of significant interest to the community.\n\n---\n\n### Specific Comments / Concerns\n\nThe fundamental question which remains in my mind is whether the original motivation of using *cones* is responsible for the improved performance, particularly when considering the fact that many of the original motivating principles to suggest their use are not applicable to the model which was employed in practice. For example:\n\n1. The authors claim that the aperture of a cone should represent the number of entities it contains, however this aperture must also somehow depend on the variety of answers. For example, consider a query that represents a very specific set of things that (from the KB's perspective) are all very similar vs. a very general query with a wide variety of answers. Here is an approach to test this: pick an arbitrary entity $x$ from the KB, and artificially augment the training data by creating many new entities $\\{\\tilde x_i\\}$ which have identical relations to $x$. Then, any query which contains $x$ suddenly contains many more entities, but this does not actually require that it have a larger aperture - indeed, the exact same model should work if the $\\tilde x_i$ entities simply have the same embedding as $x$.\n2. As mentioned in the summary, the use of cones is motivated by their closure under intersection and union, however the actual model uses sector cones which are not closed under intersection and union. Still, it seems the model performs very well. The authors mention that they have resubmitted this paper to NeurIPS with additional motivation and evaluation along these lines, however I actually feel it is simply less emphasized in the beginning and has not been fully explored. For example, the representations could be assessed as to how well they approximate the actual intersection and union operator - if it is close, then perhaps the original motivation is justified; if it is not, then the next question on my mind would be to explore the actual model and try to identify which properties are contributing to the increased performance.\n3. Apart from the difference between cones and sector cones, the operations themselves are all learned and do not necessarily obey reasonable compositional semantics. For example, if cone A is inside cone B (indicating that it contains elements which are, themselves, a subset of those in B) then the projection of A should be inside the projection of B, but this is not guaranteed by the current model. Composing operations lead to additional issues, for example, the complement of intersections may be far from the union of their complements. This can be assessed in much the same way as proposed above - compare the learned operators with geometrically accurate versions; if it is close, then perhaps it is learning to approximate the geometric idealized model, if it is not close then I would argue that it is not, fundamentally, embedding the logical operations it claims to.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The questions I raised above could be viewed as a limitation of the work, particularly if it turns out that the proposed operators are not actually learning the intersection / union / complement operations they claim to represent.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "H_bPyTp7qbd", "reviewer": "Reviewer_uQKs", "summary": "The paper presents a novel geometric embeddings called cone embeddings for solving query answering. Query answering requires embeddings of queries that are represented using first order logic. This includes conjunction, disjunction, negation but excluding Universal Quantification. Given this as basis, the related work until now has focused on two different types of embeddings (1) Geometric; and (2) probabilistic query based model. The progression from Geometric based embeddings to probabilistic models was primarily due to the fact that geometric embeddings cannot handle negation.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work differentiates itself from the other related works in the geometric query embeddings space by handling negation in first order logic queries for knowledge graphs. They propose cone embeddings (in comparison to Box Embeddings). Cone embeddings can handle negation because complement of a cone is also a cone, whereas this is the primary limitation for box embeddings. The approach also proposes four operators (a) Projection, (b) Intersection, (c) Union, and (d) Complement. The experiments on three different datasets and 9 different patterns of queries shows that Cone embeddings outperform the other approaches including BetaE, Query2Box, and GQE. This also includes its performance gain in predicting the cardinality of the answers. \n\nThe paper is written well and the overall evaluation shows significant performance gain in comparison to other approaches. \n\nMy main concerns with the paper are as follows:\n1. Comparison to faithful embeddings: The primary drawbacks of query embeddings approach is that they focus on incomplete knowledge bases. In pursuit of this -- they lose significant performance on complete knowledge bases. This is an important feature that is required for all embeddings. This work does not compare itself on the setting and also does not provide any reasons why they did not attempt comparing. \n2. Qualitative analysis between Box Embeddings and Cone Embeddings: While Cone Embeddings makes sense for negation, it is unclear why they perform significantly better than Box Embeddings. This is also the case in comparison to BetaE for negation. The authors primarily drive the work as having a geometric embeddings for negation but do not motivate/justify why Cone embeddings performs better than Box Embeddings for this work. Particularly, seems like Box Embeddings can handle most of the conjunctive queries without negation and is probably more easily interpretable than cone embeddings. \n\nOverall -- its hard for me to understand why ConeEmbeddings performs well on all aspects since it is not clearly explained in the paper. Further, it is important to have the time taken for training both ConeEmbeddings, BetA, and BoxEmbeddings. This is primarily because of the effect of multiple operators including the negation in Cone embeddings. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hrs"}, "extra_text": {}}, {"review_id": "064GeyC8nG_", "reviewer": "Reviewer_NFbk", "summary": "The paper proposes a new embedding model for multi-hop reasoning over knowledge graphs. The idea is to embed a complex query as n arc segments each on a 1-sphere. The paper designs several neural logic operators including the intersection, projection and complement operators. For union, the model uses the DNF technique to reorder the operators so that the union operators always appear in the last step. The authors evaluate the model on standard benchmarks and achieve better results than prior methods. \n\nOverall the paper is clean and easy to follow. A general question I have is that the current modeling is to embed the query into several independent arc segments. Have you tried to embed the query into the surface (sphere cap) of a n-sphere? \n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Here are some additional questions.\n1. line 46-47, it seems a little inaccurate. The beta QE model uses the KL divergence to determine whether an entity is an answer to the query. Can you clarify this point?\n2. For the SemanticAverage operation, what if the weighted sum of the points is a whole-zero vector? E.g., what is the intersection between $\\theta$ and $\\theta+\\pi$?\n3. Can you also report the performance of converting union queries into queries with only intersection and complement operations? How does it compare with the DNF modeling?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please check the questions in the section above. I do not see any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper attempts to improve reasoning over knowledge bases. In this regard, the authors introduces a novel query representation using cones. As the set of cones is closed under intersection, union, and complement, it is claimed that such representation can be very expressive. Empirical performance of the proposed method is very good. We thank the reviewers and authors for engaging in an active discussion, which resulted in clearing a lot of the concerns (e.g. mismatch between motivation and method) and a lot of constructive feedback were provided to improve the paper. The authors provided extensive empirical results as part of the discussion, please include them in the final version of the paper as they add great value and understanding to the model as a whole.
Decision: Accept (Poster)