summaries: 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. 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.  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).  - 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. - The choice of using cones facilitates complement operation. - Authors demonstrate empirical improvements over past work in FOL query embedding. - 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. 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. 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.   Overall 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?  
abstractText: 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 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-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.
authors.name: Zhanqiu Zhang
authors.name: Jie Wang
authors.name: Jiajun Chen
authors.name: Shuiwang Ji
authors.name: Feng Wu
references.authors: I. Balazevic C. Allen T. Hospedales
references.title: Multi-relational poincaré graph embeddings
references.venue: In Advances in Neural Information Processing Systems,
references.authors: K. Bollacker C. Evans P. Paritosh T. Sturge J. Taylor
references.title: Freebase: A collaboratively created graph database for structuring human knowledge
references.venue: In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data,
references.authors: A. Bordes N. Usunier A. Garcia-Duran J. Weston O. Yakhnenko
references.title: Translating embeddings for modeling multi-relational data
references.venue: In Advances in Neural Information Processing Systems
references.authors: S. Boyd L. Vandenberghe
references.title: Convex Optimization
references.authors: R. Das A. Neelakantan D. Belanger A. McCallum
references.title: Chains of reasoning over entities, relations, and text using recurrent neural networks
references.venue: In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers,
references.authors: S. Dasgupta M. Boratko D. Zhang L. Vilnis X. Li A. McCallum
references.title: Improving local identifiability in probabilistic box embeddings
references.venue: In Advances in Neural Information Processing Systems,
references.authors: B.A. Davey H.A. Priestley
references.title: Introduction to lattices and order
references.venue: Cambridge university press,
references.authors: O. Ganea G. Becigneul T. Hofmann
references.title: Hyperbolic entailment cones for learning hierarchical embeddings
references.venue: In Proceedings of the 35th International Conference on Machine Learning,
references.authors: D. Garg S. Ikbal S.K. Srivastava H. Vishwakarma H. Karanam L.V. Subramaniam
references.title: Quantum embedding of knowledge for reasoning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: S. Guo Q. Wang L. Wang B. Wang L. Guo
references.title: Knowledge graph embedding with iterative guidance from soft rules
references.venue: In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence,
references.authors: K. Guu J. Miller P. Liang
references.title: Traversing knowledge graphs in vector space
references.venue: In Proceedings of the Conference on Empirical Methods in Natural Language Processing,
references.authors: W.L. Hamilton P. Bajaj M. Zitnik D. Jurafsky J. Leskovec
references.title: Embedding logical queries on knowledge graphs
references.venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,
references.authors: D.P. Kingma J. Ba
references.title: Adam: A method for stochastic optimization
references.venue: In Proceedings of the International Conference on Learning Representations (ICLR),
references.authors: T. Lacroix N. Usunier G. Obozinski
references.title: Canonical tensor decomposition for knowledge base completion
references.venue: In Proceedings of the 35th International Conference on Machine Learning,
references.authors: A. Lai J. Hockenmaier
references.title: Learning to predict denotational probabilities for modeling entailment
references.venue: In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers,
references.authors: Li F.-L M. Qiu H. Chen X. Wang X. Gao J. Huang J. Ren Z. Zhao W. Zhao L. Wang G. Jin Chu W. Alime
references.title: assist: An intelligent assistant for creating an innovative e-commerce experience
references.venue: In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management,
references.authors: X.V. Lin R. Socher C. Xiong
references.title: Multi-hop knowledge graph reasoning with reward shaping
references.venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,
references.authors: Y. Lin Z. Liu M. Sun Y. Liu X. Zhu
references.title: Learning entity and relation embeddings for knowledge graph completion
references.venue: In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence,
references.authors: M. Nickel D. Kiela
references.title: Poincaré embeddings for learning hierarchical representations
references.venue: In Advances in Neural Information Processing Systems,
references.authors: H. Ren J. Leskovec
references.title: Beta embeddings for multi-hop logical reasoning in knowledge graphs
references.venue: In Neural Information Processing Systems,
references.authors: H. Ren W. Hu J. Leskovec
references.title: Query2box: Reasoning over knowledge graphs in vector space using box embeddings
references.venue: In International Conference on Learning Representations,
references.authors: A. Saxena A. Tripathi P. Talukdar
references.title: Improving multi-hop question answering over knowledge graphs using knowledge base embeddings
references.venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,
references.authors: H. Sun T. Bedrax-Weiss W. Cohen
references.title: PullNet: Open domain question answering with iterative retrieval on knowledge bases and text
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),
references.authors: H. Sun A.O. Arnold T. Bedrax-Weiss F. Pereira W.W. Cohen
references.title: Faithful embeddings for knowledge base queries
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Z. Sun Deng Z.-H Nie J.-Y J. Tang
references.title: Rotate: Knowledge graph embedding by relational rotation in complex space
references.venue: In International Conference on Learning Representations,
references.authors: K. Toutanova D. Chen
references.title: Observed versus latent features for knowledge base and text inference
references.venue: In 3rd Workshop on Continuous Vector Space Models and Their Compositionality,
references.authors: T. Trouillon J. Welbl S. Riedel E. Gaussier G. Bouchard
references.title: Complex embeddings for simple link prediction
references.venue: In Proceedings of The 33rd International Conference on Machine Learning,
references.authors: I. Vendrov R. Kiros S. Fidler R. Urtasun
references.title: Order-embeddings of images and language
references.venue: In 4th International Conference on Learning Representations,
references.authors: W. Xiong T. Hoang W.Y. Wang
references.title: DeepPath: A reinforcement learning method for knowledge graph reasoning
references.venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,
references.authors: Z. Zhang J. Cai J. Wang
references.title: Duality-induced regularizer for tensor factorization based knowledge graph completion
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Z. Zhang J. Cai Y. Zhang J. Wang
references.title: Learning hierarchy-aware knowledge graph embeddings for link prediction
references.venue: In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence,
sections.heading: 1 Introduction
sections.text: Multi-hop reasoning over knowledge graphs (KGs)—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 (∃), conjunction (∧), disjunction (∨), and negation (¬). A popular approach to multi-hop reasoning over KGs is to first transform a FOL query to its corresponding computation graph—where each node represents a set of entities and each edge represents a logical operation—and then traverse the KG according to the computation graph to 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.
  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 (NeurIPS 2021).
  spaces. Given a query, QE models generate query embeddings following the corresponding computation 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, 11, 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, Query2Box [22] represents entities as points and queries as boxes. If a point is inside a box, then the corresponding entity is the answer to the query. Compared with non-geometric 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—cannot handle queries with negation, as the complement of a point/box is no longer a point/box. To tackle this problem, Ren & Leskovec [21] propose a probabilistic QE model using Beta distributions. However, it does not have some advantages of geometric models. For example, using Beta distributions, it is unclear how to determine whether an entity is an answer to a query as that in the box case [22]. 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—namely, Cone Embeddings (ConE)—which represents entities and queries as 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 is the first geometry-based QE model that can handle all the FOL operations, including conjunction, disjunction, and negation. Experiments demonstrate that ConE significantly outperforms existing state-of-the-art methods on benchmark datasets.
sections.heading: 2 Related Work
sections.text: 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-based models are another line of works, which embed FOL queries into low-dimensional spaces. For example, existing works embed queries to geometric shapes [12, 22, 11, 5], probability distributions [21], and complex objects [9, 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, 18], rotation [28, 26, 14, 32], and complex geometric operations [1, 33] 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 in the ALC description logic, and use polars of cones to model negation operators. Recent years have also witnessed the development of embeddings in non-Euclidean geometry, such as Poincaré embeddings [1, 20] and hyperbolic entailment cones [8]. Notably, although there exist works that also use cone embeddings [15, 29, 8, 19], they are not designed for the multi-hop reasoning task and their definition of cones are different from that in our work.
sections.heading: 3 Preliminaries
sections.text: 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.
sections.heading: 3.1 Backgrounds
sections.text: Knowledge Graphs (KGs). Given a set V of entities (vertices) and a set E of relations (edges), a knowledge graph G = {(si, pj , ok)} ⊂ V × E × V is a set of factual triple, where pj ∈ E is a predicate, and si, ok ∈ V are subject and object, respectively. Suppose that rj(·, ·) ∈ R is a binary function rj : V × V → {True,False} corresponding to pj , where rj(si, ok) = True if and only if (si, pj , ok) is a factual triples. Then, for all (si, pj , ok) ∈ G, we have rj(si, ok) = True. Note that both E and R are involved with relations, while E is a set of relation instances and R is a set of relational functions.
  First-Order Logic (FOL). FOL queries in the query embedding literature involve logical operations including existential quantification (∃), conjunction (∧), disjunction (∨), and negation (¬). Universal quantification (∀) is not included, as no entity connects with all other entities in real-world KGs [21]. We use FOL queries in its Disjunctive Normal Form (DNF) [7], which represents FOL queries as a disjunction of conjunctions. To formulate FOL queries, we assume that Va ⊂ V is the non-variable anchor entity set, V1, . . . , Vk are existentially quantified bound variables, and V? is the target variable, i.e., the answers to a certain query. Then, a FOL query q in the disjunctive normal form is:
  q[V?] = V?. ∃V1, . . . , Vk : c1 ∨ c2 ∨ · · · ∨ cn.
  Specifically, ci are conjunctions, i.e., ci = ei1 ∧ · · · ∧ eim, where eij = r(va, V ) or ¬r(va, V ) or r(V ′, V ) or ¬r(V ′, V ), va ∈ Va, V ∈ {V?, V1, . . . , Vk}, V ′ ∈ {V1, . . . , Vk}, and V ̸= V ′. Using the aforementioned notations, answering a query q is equivalent to finding the set of entities JqK ⊂ V , where v ∈ JqK if and only if q[v] is True. Computation Graphs. Given a query, we represent the reasoning procedure as a computation graph (see Figure 1a for an example), of which nodes represent entity sets and edges represent logical operations over entity sets. We map edges to logical operators according to the following rules.
  • Relation Traversal→Projection Operator P . Given a set of entities S ⊂ V and a relational function r ∈ R, the projection operator P outputs all the adjacent entities ∪v∈SN(v, r), where N(v, r) is the set of entities such that r(v, v′) = True for all v′ ∈ N(v, r).
  • Conjunction→Intersection Operator I. Given n sets of entities {S1, S2, . . . , Sn}, the intersection operator I performs set intersection to obtain ∩ni=1Sn.
  • Disjunction→Union Operator U . Given n sets of entities {S1, S2, . . . , Sn}, the union operator U performs set union to obtain ∪ni=1Sn.
  • Negation→Complement Operator C. Given an entity set S ⊂ V , C gives S̄ = V\S.
  Query Embeddings (QE). QE models generate 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 a set with a single element and each query q is corresponding to a unique answer set JqK, the aim of QE models is equivalent to embedding entity sets that can be answers to some queries.
sections.heading: 3.2 Cones in Two-Dimensional Spaces
sections.text: To represent FOL queries as Cartesian products of two-dimensional cones, we introduce some definitions about cones and the parameterization method of a special class of cones. Definition 1 (Boyd & Vandenberghe [4]). A set C ⊂ R2 is called a cone, if for every x ∈ C and λ ≥ 0, we have λx ∈ C . A set is a convex cone if it is convex and a cone, which means that for any x1, x2 ∈ C and λ1, λ2 ≥ 0, we have λ1x1 + λ2x2 ∈ C.
  By letting λ = 0 in Definition 1, we know that a cone must contain the origin. In view of this property, we define a new operation called closure-complement for cones. Definition 2. Suppose that C ⊂ R2 is a cone. Then, the closure-complement of C is defined by C̃ = cl(R2\C), where cl(·) is the closure of a set.
  Next, we introduce a class of cones that can be parameterized in a scalable way. Definition 3. A 2D closed cone is called a sector-cone, if its closure-complement or itself is convex.
  The set of sector-cones is closed under closure-complement and their union and intersection are still cones. Besides, we have the following proposition, whose proof is provided in Appendix A. Proposition 1. A sector-cone is always axially symmetric.
  Parameterization of 2D Sector-Cones. Proposition 1 suggests that we can use a pair of parameters to represent a two-dimensional sector-cone:
  (θax, θap),where θax ∈ [−π, π), θap ∈ [0, 2π].
  Specifically, θax represents the angle between the symmetry axis of the sector-cone and the positive x axis. θap represents the aperture of the sector-cone. For any points in the cone, its phase will be in [θax − θap/2, θax + θap/2]. Figure 1b 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 (θax, θap). We can represent an arbitrary sector-cone C0 as C0 = (θax, θap) ∈ K. Then, for a d-ary Cartesian product of sector-cones
  C = C1 × C2 × . . .× Cd, (1)
  we represent it via a d-dimensional vector in Kd: C = ( (θ1ax, θ 1 ap), . . . , (θ d ax, θ d ap) ) ⊂ Kd. (2)
  where θiax ∈ [−π, π), θiap ∈ [0, 2π], for i = 1, . . . , d. Or equivalently, C = (θax,θap), where θax = (θ 1 ax, . . . , θ d ax) ∈ [−π, π)d and θap = (θ1ap, . . . , θdap) ∈ [0, 2π]d.
sections.heading: 4 Cone Embeddings
sections.text: In this section, we 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 to learn ConE in Sections 4.2 and 4.3.
sections.heading: 4.1 Cone Embeddings for Conjunctive Queries and Entities
sections.text: As introduced in 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 U 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 be places. If we embed an entity set JqK into an embedding space, we expect entities in JqK to have similar embeddings. Thus,
  we expect their embeddings to form a "region" in the embedding space. If the embedding of an entity is inside the region, then the entity is likely to be an answer. Further, we can find a semantic center and a boundary for the region, where the semantic center represents the semantics of JqK and the boundary designates how many entities are in JqK. To model the embedding region of JqK, we propose to embed it to a Cartesian product of sector-cones. Specifically, we use the parameter θiax to represent the semantic center, and the parameter θ i ap to determine the boundary of JqK. If we use a d-ary Cartesian product, i.e., the embedding dimension is d, we define the embedding of JqK as
  Vcq = (θax,θap),
  where θax ∈ [−π, π)d are axes and θap ∈ [0, 2π]d are apertures. An entity v ∈ V is equivalent to an entity set with a single element, i.e., {v}. We propose to represent an entity as a Cartesian product of cones with apertures 0, where the axes indicates the semantics of the entity. Formally, if the embedding dimension is d, the cone embedding of v is v = (θax, 0), where θax ∈ [−π, π)d is the axis embedding and 0 is a d-dimensional vector with all elements being 0.
sections.heading: 4.2 Logical Operators for Cone Embeddings
sections.text: In this section, we introduce our designed logical operators of ConE in the embedding space, including projection, intersection, union, and complement.
  It is worth noting that, the composition of logical operators may lead to 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 in 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 P . The goal of P is to represent an entity’s adjacent entities that are linked by a given relation. It maps an entity set to another entity set (see Figure 2a). Thus, we define a relation-dependent function in the embedding space for P:
  fr : Kd → Kd, Vcq 7→ V c′ q .
  We implement fr in a neural way. First, we represent relations as relational translations of query embeddings and assign each relation with an embedding r = (θax,r,θap,r). Then, we define fr as
  fr(Vq) = g(MLP([θax + θax,r;θap + θap,r])) (3)
  where MLP : R2d → R2d is a multi-layer perceptron network, [·; ·] is the concatenation of two vectors, and g is a function that generates θ′ax ∈ [−π, π)d and θ′ap ∈ [0, 2π]d. We define g as:
  [g(x)]i = { θ′iax = π tanh(λ1xi), if i ≤ d, θ′i−dap = π tanh(λ2xi) + π, if i > d.
  where [g(x)]i denotes the i-th element of g(x), λ1 and λ2 are two fixed parameters to control the scale. Note that the range of the hyperbolic tangent function (tanh) are open sets. Thus, we cannot indeed get the boundary value θ′iax = −π and θ′iap = 0, 2π. However, when we implement g in experiments, the value of g can be very close to 0 and 2π, which is equivalent to the closed set numerically.
  Intersection Operator I. Given a query q that is the conjunction of conjunctive queries qi, the goal of I is to represent JqK = ∩ni=1JqiK. Since the conjunction of conjunctive queries are still conjunctive
  queries, the entities in JqK should have similar semantics. Recall that we only need to model entity sets that can be answers. We still use a Cartesian product of sector-cones to represent JqK (see Figure 2b). Suppose that Vcq = (θax,θap) and V c qi = (θi,ax,θi,ap) are cone embeddings for JqK and JqiK, respectively. We define the intersection operator as follows:
  θax = SemanticAverage(Vcq1 , . . . ,V c qn), θap = CardMin(Vcq1 , . . . ,V c qn),
  where SemanticAverage(·) and CardMin(·) generates semantic centers and apertures, respectively. In the following, we introduce these two functions in detail.
  SemanticAverage. As the semantic center of Vcq, θax should be close to all the semantic centers θi,ax. Thus, we propose to represent θax as a semantic average of θi,ax. We note that the ordinary weighted average may lead to inconsistent semantics. For example, when d = 1, if θ1,ax = π − ϵ and θ2,ax = −π + ϵ (0 < ϵ < π/4), then we expect θax to be around π. However, if we use the ordinary weighted sum, θax will be around 0 with a high probability. To tackle this issue, we 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 [θi,ax]j to points on the unit circle. Then, compute the weighted average of the points using an attention mechanism. Finally, map the points back to angles that represent axes. Formally, the computation process is
  [x;y] = n∑ i=1 [ai ◦ cos(θi,ax); ai ◦ sin(θi,ax)],
  θax = Arg(x,y),
  where cos and sin are element-wise cosine and sine functions; ai ∈ Rd are positive weights vectors that satisfy ∑n i=1[ai]j = 1 for all j = 1, . . . , d; ◦ is the element-wise multiplication; Arg(·) is the function that computes arguments of (a Cartesian of) 2D points. Noticing that the weights ai are relevant to both axes and apertures, we compute [ai]j via the following attention mechanism:
  [ai]j = exp([MLP([θi,ax − θi,ap/2;θi,ax + θi,ap/2])]j)∑n
  k=1 exp([MLP([θk,ax − θk,ap/2;θk,ax + θk,ap/2])]j) ,
  where MLP : R2d → Rd is a multi-layer perceptron network, [·; ·] is the concatenation of two vectors. We can see θi,ax − θi,ap/2 and θi,ax + θi,ap/2 as the lower and upper bound of sector-cones. We use Arg(·) to recover angles of 2D points. Suppose that βi = arctan([y]i/[x]i), then
  [θax]i =  βi + π, if [x]i < 0, [y]i > 0, βi − π, if [x]i < 0, [y]i < 0,
  βi, otherwise.
  Note that [x]i = 0 will lead to an illegal division. In experiments, we manually set [x]i to be a small number (e.g., 10−3) when [x]i = 0.
  CardMin. Since JqK is the subset of all JqiK, θiap should be no larger than any apertures θij,ap. Therefore, we implement CardMin by a minimum mechanism with cardinality constraints:
  θiap = min{θi1,ap, . . . , θin,ap} · σ([DeepSets({Vqj}nj=1)]i),
  where σ(·) is the element-wise sigmoid function, θij,ap is the i-th element of θj,ap, DeepSets(·) is a permutation-invariant function [31]. Specifically, DeepSets({Vqj}nj=1) is computed by
  MLP ( 1
  n ∑n j=1 MLP ([θj,ax − θj,ap/2;θj,ax + θj,ap/2]) ) .
  Union Operator U . Given a query q that is the disjunction of conjunctive queries qi, the goal of the union operator U is to represent JqK = ∪ni=1JqiK. As noted by Ren et al. [22], directly modeling the disjunction leads to unscalable models. Thus, we adopt the DNF technique [22], in which the union operation only appears in the last step in computation graphs.
  Suppose that Vcqi = (θi,ax,θi,ap) are cone embeddings for JqiK. To represent the union of several cones (see Figure 2c), we represent JqK as a set of Vcqi :
  Vdq = {V c q1 , . . . ,V c qn},
  where n may be various in different queries. Equivalently, Vdq can be written as Vdq = ( {(θ11,ax, θ11,ap), . . . , (θ1n,ax, θ1n,ap)}, . . . , {(θd1,ax, θd1,ap), . . . , (θdn,ax, θdn,ap)} ) .
  As {(θi1,ax, θi1,ap), . . . , (θin,ax, θin,ap)} are the union of d sector-cones, it is also a cone. Thus, the cone embedding of q is also a Cartesian product of two-dimensional cones.
  Complement Operator C. Given an conjunctive query q and the corresponding entity set JqK, the aim of C is to identify the set J¬qK, which is the complementary of JqK, i.e., V\JqK. Since the set of sector-cones is closed under closure-complement, we define C using the closure-complement. Thus, the apertures of Vq plus the apertures of V¬q should be a vector with all elements being 2π. Moreover, to represent the semantic difference between JqK and J¬qK, we assume that their semantic centers to be opposite. Please refer to Figure 2d for a figure illustration.
  Suppose that Vq = (θax,θap) and V¬q = (θ′ax,θ′ap). We define the complement operator C as:
  [θ′ax]i = { [θax]i − π, if [θax]i ≥ 0, [θax]i + π, if [θax]i < 0,
  [θ′ap]i = 2π − [θap]i.
sections.heading: 4.3 Learning Cone Embeddings
sections.text: To learn cone embeddings, we expect that the cone embeddings of entities v ∈ JqK are inside the cone embeddings of q, and the cone embeddings of entities v′ /∈ JqK are far from the cone embedding of q. This motivates us to define a distance function 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 et al. [22], we divide the distance d into two parts—the outside distance do and the inside distance di. Figure 2e gives an illustration of the distance function d. Suppose that v = (θvax, 0), V c q = (θax,θap), θL = θax − θap/2 and θU = θax + θap/2. We define the distance as dcon(v;V c q) = do(v;V c q) + λdi(v;V c q).
  The outside distance and the inside distance are do = ∥min {|sin (θvax − θL) /2| , |sin (θvax − θU ) /2|}∥1 , di = ∥min {|sin (θvax − θax) /2| , |sin (θap) /2|}∥1 ,
  where ∥ · ∥1is the L1 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 λ ∈ (0, 1) is fixed during training, so that v is encouraged to be inside the cones represented by Vcq , but not necessarily be equal to the semantic center of V c q .
  Since we represent the disjunctive queries as a set of embeddings, we cannot use dcon 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 a query q = q1 ∨ · · · ∨ qn in the Disjunctive Normal Form, the distance between q and an entity is
  ddis(v;Vdq) = min{dcon(v;V c q1), . . . , dcon(v;V c qn)}.
  If we use Vq to represent embeddings of both kinds of queries, the unified distance function d is
  d(v;Vq) = { dcon(v;Vq), if q is conjunctive queries, ddis(v;Vq), if q is disjunctive queries.
  Training Objective. Given a training set of queries, we optimize a negative sampling loss
  L = − log σ(γ − d(v;Vq))− 1
  k ∑k i=1 log σ(d(v′i;Vq)− γ),
  where γ > 0 is a fixed margin, v ∈ JqK is a positive entity, v′i /∈ JqK is the i-th negative entity, k is the number of negative entities, and σ(·) is the sigmoid function.
sections.heading: 5 Experiments
sections.text: In this section, we conduct experiments to demonstrate that: 1) ConE is a 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 5.1 and then present the experimental results in Sections 5.2 and 5.3. The code of ConE is available on GitHub at https://github.com/MIRALab-USTC/QE-ConE.
sections.heading: 5.1 Experimental Settings
sections.text: We adopt the commonly used experimental settings for query embeddings [12, 22, 21].
  Datasets and Queries. We use three datasets: FB15k [2], FB15k-237 (FB237) [27], and NELL995 (NELL) [30]. QE models focus on answering queries involved with incomplete KGs. Thus, we aim to find non-trivial answers to FOL queries that cannot be discovered by traversing KGs. For a fair comparison, we use the same query structures as those in Ren & Leskovec [21]. The training and validation queries consist of five conjunctive structures (1p/2p/3p/2i/3i) and five structures with negation (2in/3in/inp/pni/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/pi/2u/up. Please refer to Appendix B.1 for more details about datasets and query structures.
  Training Protocol. We use Adam [13] as 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 to Appendix B.2.
  Evaluation Protocol. We use the same evaluation protocol as that in Ren & Leskovec [21]. We first build three KGs: the training KG Gtrain, the validation KG Gvalid, and the test KG Gtest using training edges, training+validation edges, training+validation+test edges, respectively. Given a test (validation) query q, we aim to discover non-trivial answers JqKtest\JqKvalid (JqKvalid\JqKtrain). 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 v of a test query q, we rank it against non-answer entities V\JqKtest. We denote 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.
  Baselines. We compare ConE against three state-of-the-art models, including GQE [12], Query2Box (Q2B) [22], and BETAE [21]. GQE and Q2B are trained only on five conjunctive structures as 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 d = 1600 and BETAE with d = 400. For the results of BETAE with d = 800, please refer to Appendix C.1.
sections.heading: 5.2 Main Results
sections.text: 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 1 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/pi/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 law. However, using De Morgan’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 law. We include the detailed results in Appendix C.2 due to the space limit.
  Queries with Negation. Table 2 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 a large margin. Specifically, ConE achieves on average 25.4%, 9.3%, and 8.5% relative improvement MRR over BETAE on FB15k, FB237, and NELL, respectively.
sections.heading: 5.3 Modeling the Cardinality of Answer Sets
sections.text: As introduced in Section 4.1, the aperture embeddings can designate the cardinality (i.e., the number of elements) of JqK. In this experiment, we demonstrate that although we do not explicitly enforce ConE to learn cardinality during training, the learned aperture embeddings are effective 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 Vq = (θax,θap) of a given query q, we use the L1 norm of θap to represent the learned cardinality of JqK. Then, we compute the Spearman’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 & Leskovec [21].
  Table 3 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-art method BETAE. Note that BETAE 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 correlation, which measures the linear correlation between two variables. Please refer to Appendix C.3 for the results.
sections.heading: 5.4 The Designed Operators and the Real Set Operations
sections.text: 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 on 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 a 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 (Ai, Bi), where Ai ⊂ Bi. Then, for each i, we randomly select a relation ri and calculate the projections Pri(Ai) and Pri(Bi). Ideally, the projected cones should satisfy Pri(Ai) ⊂ Pri(Bi). We calculate the ratio ri = |Pri(Ai)∩Pri(Bi)|/|Pri(Ai)| to measure how many elements in Pri(Ai) are included in Pri(Ai)∩Pri(Bi). Finally, we get an average ratio r = 0.8113. That is to say, the learned Pri(Ai) are included in Pri(Ai) with a high probability. The learned projection operators approximate the real set projection well.
  Intersection. To validate that the learned intersection can well approximate real set intersection, we randomly generate 8000 pairs of sector-cones (Ci, Di), where Ci ∩ Di is not guaranteed to be a sector-cone. Then, we generate embeddings I(Ci, Di) for the intersection Ci ∩ Di. Ideally, the learned cones I(Ci, Di) should be the same as the real cones Ci ∩Di. We calculate the ratio ri = |I(Ci, Di) ∩ (Ci ∩Di)|/|I(Ci, Di) ∪ (Ci ∩Di)| to measure the overlap between I(Ci, Di) and Ci ∩Di, and obtain an average ratio of r = 0.6134. Note that the experiments are conducted on the test set, and we 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.
  We further conduct experiments to demonstrate that the learned intersection operators can well handle empty intersections. Following Ren et al. [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 is 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 law and the real set union. Please refer to Appendix C.6 for details.
sections.heading: 6 Conclusion
sections.text: In this paper, we propose a 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 is 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 is to adapt ConE to queries in the natural language, which will further improve ConE’s applicability.
  Acknowledgments and Disclosure of Funding
  We would like to 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 WK3490000004.
title: ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs