C yl E : Cylinder Embeddings for Multi-hop Reasoning over Knowledge Graphs (2023)

Abstract: Recent geometric-based approaches have been shown to efficiently model complex logical queries (including the intersection operation) over Knowledge Graphs based on the natural representation of Venn diagram. Existing geometric-based models (using points, boxes embeddings), however, cannot handle the logical negation operation. Further, those using cones embeddings are limited to representing queries by two-dimensional shapes, which reduced their effectiveness in capturing entities query relations for correct answers. To overcome this challenge, we propose unbounded cylinder embeddings (namely CylE), which is a novel geometric-based model based on three-dimensional shapes. Our approach can handle a complete set of basic first-order logic operations (conjunctions, disjunctions and negations). CylE considers queries as Cartesian products of unbounded sector-cylinders and consider a set of nearest boxes corresponds to the set of answer entities. Precisely, the conjunctions can be represented via the intersections of unbounded sector-cylinders. Transforming queries to Disjunctive Normal Form can handle queries with disjunctions. The negations can be represented by considering the closure of complement for an arbitrary unbounded sector-cylinder. Empirical results show that the performance of multi-hop reasoning task using CylE significantly increases over state-of-the-art geometric-based query embedding models for queries without negation. For queries with negation operations, though the performance is on a par with the best performing geometric-based model, CylE significantly outperforms a recent distribution-based model.

## introduction multi-hop reasoning (mhr) on knowledge graphs (kgs) is a primary task in answering queries over large-scale knowledge graphs. queries can be represented using first-order-logic (fol) connectives @xcite , involving these operations: existential quantification (∃), conjunction (∧), disjunction (∨) and negation (¬). mhr involves learning to answer these fol queries, which has recently received attention from several studies @xcite @xcite . a common approach is to first transform the fol query into a computation graph (see figure 1 ), where nodes represent entity constants or variables and edges map to predicates and logical operations. representing queries in this way enables the learning process to traverse paths of kgs via the computation graph, so as to find a set of answers for a given query. however, large-scale kgs @xcite @xcite @xcite are often incomplete and noisy, which makes explicit query mechanism, such as graph traversal incapable of returning correct answers to a query. motivated by the challenge above, we aim to reason about incomplete kgs using mhr @xcite . to achieve mhr, recent studies have proposed several query embedding (qe) methods based on geometry @xcite @xcite and probability distribution representations @xcite . a common approach of qe in the literature is to project the fol queries into an embedding space, allowing a model to learn the embeddings of queries and entities. answering these queries is equivalent to finding the similarity between the embedded queries and the embedded entities. geometric-based models using cone embeddings cone @xcite are shown to be superior over the others, especially the ability of handling negations. cone represents queries as cartesian product of sector-cones in an embedding space. cone projects target entities as lines and queries as areas of sector-cones. intuitively, if the line is inside the area, the corresponding entity is considered as a match to the query. nevertheless, cone embeddings are limited to the 2d space in a flat plane, to represent the query and entity embeddings. for example, one entity in a cluster of the sub-topic /movie/action and one in another /movie/documentary can be in the sectorcone region for those labels in the topic /movie (see figure 2(a) ). answering a query regarding the /movie/action can return irrelevant entities from the /movie/documentary. in multi-dimensional space, entities assigned to multiple labels can be achieved using multi-dimensional classification @xcite . in the 3d space, for instance, apart from the xy-plane, semantics of entities can be additionally classified by different levels of degree in the height segment (along the z-axis). in this paper, we propose to expand the two dimension sector-cone embeddings into the three dimension coordinate system. we represent queries by augmenting the shape of the sector-cones to be similar as unbounded sector-cylinders (shortly called sector-cylinders) in an embedding space, compared to closed sector-cylinders in a normal situation (see examples of unbounded sectorcylinders, their intersection or union in figure 2 and further definitions in section 4.1). in short, we name this approach cylinder embeddings (cyle). answering a query is similar to finding entities that are subsets of the sector-cylinders representing queries. we investigate whether there is any improvement in answering correctly any query structures, using cyle over other approaches. our approach can handle the conjunction as we notice that the intersection of sector-cylinders (along the z-axis) can be a sector-cylinder. since the union of sector-cylinders is no longer a sector-cylinder, we first transform queries to disjunctive normal form (dnf), which enables cyle to handle disjunction. with regard to the negation operation, we consider the closure-complement of sector-cylinders to model this operation. our contributions are: (1) introducing the first 3d geometric-based approach to model the qe for mhr to the best of our knowledge, (2) enabling the model to handle a complete set of the basic fol queries (existential quantification, conjunction, disjunction and negation) and (3) demonstrating that cyle significantly outperforms state-of-the-art (sota) geometric-based models for non-negation queries and is on par for queries with negations by empirical results. ## related works multi-hop reasoning for logical query studies in mhr employed approaches such as (distributions @xcite @xcite , geometric shapes @xcite @xcite , fuzzy logic @xcite ), others using count-min sketch @xcite and neural-symbolic approach @xcite , to achieve the common goal of learning representation of queries, i.e. query embeddings. the primary difference in these approaches is based on how queries are represented. for example, distribution-based models use beta distributions @xcite or multivariate gaussian distributions @xcite . in geometric shapes, @xcite represented queries as point embeddings, @xcite then furthered this using box embeddings, and @xcite made an improvement by introducing 'particle' embeddings (a set of points using multiple vectors). @xcite have made the geometric approach more expressive using cone embeddings. another difference is the ability to model a complete set of logical operations @xcite (conjunction, disjunction and negation). several methods @xcite @xcite have achieved a coverage of all operations including the negation, compared to others @xcite @xcite without negation. reasoning about kgs using geometric shapes historically, these approaches received attention since the introduction of translation-based methods @xcite , rotation @xcite and 3d-rotation @xcite for learning knowledge graph embeddings. inspired by a poincaré ball, other studies @xcite proposed hyperbolic space (non-euclidean geometry). a common task of these studies is kgs completion. however, furthering it to mhr task poses a challenge because of the complex structures of queries (see figure 3 ). using geometric shapes for the mhr task (point @xcite ; bai et al. (2022), box ren et al. (2020), hyperbolic choudhary et al. (2021b) and cone embeddings zhang et al. (2021b) ) have increasingly gained popularity. cone embeddings were also mentioned in @xcite , but not for the mhr task. since existing geometric-based methods of cone embeddings rely on 2d shapes, we extend the representation learning for this geometric family to 3d shapes for the mhr task. other studies (e.g. spherical text embeddings @xcite ) learned word embeddings for document clustering and classification tasks, but still not for the mhr task. ## cylinder embeddings we first provide a background of parameterizing cylinder (section 4.1) and modeling cylinder embeddings for conjunctive queries (section 4.2). next, we show the cylinder embeddings process with logical operators (section 4.3), then provide an optimization method (section 4.4). ## conclusion we have presented a novel query embeddings (qe) model using cylinder embeddings (cyle), which can handle a complete set of arbitrary fol queries, to perform the multi-hop reasoning (mhr) task. to the best of our knowledge, cyle is the first 3d geometric-based qe model for mhr. experiments show significant performance gain over previous approaches for non-negation queries. for queries with negation operations, we face a similar challenge to previous models i.e. low mhr performance. this is a future direction to improve cyle on these queries. this work paves the way for opening the geometric-based qe method using three dimensional shapes.