ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs

Introduction

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 . In general, it involves answering first-order logic (FOL) queries over KGs using operators including existential quantification ($\exists$), conjunction ($\land$), disjunction ($\lor$), and negation ($\neg$). 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 . QE models associate each logical operator in computation graphs with a logical operation in embedding 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 . 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 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 and Query2Box —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 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 . 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.

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 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 , probability distributions , and complex objects . 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 , rotation , and complex geometric operations have been widely used in knowledge graph embeddings. Other geometric embedding methods also manage to use boxes , convex cones , etc. For example, Lütfü Özçep et al. 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 and hyperbolic entailment cones . Notably, although there exist works that also use cone embeddings , they are not designed for the multi-hop reasoning task and their definition of cones are different from that in our work.

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.

Knowledge Graphs (KGs). Given a set $\mathcal{V}$ of entities (vertices) and a set $\mathcal{E}$ of relations (edges), a knowledge graph $\mathcal{G}=\{(s_{i},p_{j},o_{k})\}\subset\mathcal{V}\times\mathcal{E}\times\mathcal{V}$ is a set of factual triple, where $p_{j}\in\mathcal{E}$ is a predicate, and $s_{i},o_{k}\in\mathcal{V}$ are subject and object, respectively. Suppose that $r_{j}(\cdot,\cdot)\in\mathcal{R}$ is a binary function $r_{j}:\mathcal{V}\times\mathcal{V}\rightarrow\{\text{True},\text{False}\}$ corresponding to $p_{j}$, where $r_{j}(s_{i},o_{k})=\text{True}$ if and only if $(s_{i},p_{j},o_{k})$ is a factual triples. Then, for all $(s_{i},p_{j},o_{k})\in\mathcal{G}$, we have $r_{j}(s_{i},o_{k})=\text{True}$. Note that both $\mathcal{E}$ and $\mathcal{R}$ are involved with relations, while $\mathcal{E}$ is a set of relation instances and $\mathcal{R}$ is a set of relational functions.

First-Order Logic (FOL). FOL queries in the query embedding literature involve logical operations including existential quantification ($\exists$), conjunction ($\land$), disjunction ($\lor$), and negation ($\neg$). Universal quantification ($\forall$) is not included, as no entity connects with all other entities in real-world KGs .

We use FOL queries in its Disjunctive Normal Form (DNF) , which represents FOL queries as a disjunction of conjunctions. To formulate FOL queries, we assume that $\mathcal{V}_{a}\subset\mathcal{V}$ is the non-variable anchor entity set, $V_{1},\dots,V_{k}$ 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:

Specifically, $c_{i}$ are conjunctions, i.e., $c_{i}=e_{i1}\land\cdots\land e_{im}$, where $e_{ij}=r(v_{a},V)$ or $\neg r(v_{a},V)$ or $r(V^{\prime},V)$ or $\neg r(V^{\prime},V)$, $v_{a}\in\mathcal{V}_{a},V\in\{V_{?},V_{1},\dots,V_{k}\}$, $V^{\prime}\in\{V_{1},\dots,V_{k}\}$, and $V\neq V^{\prime}.$

Using the aforementioned notations, answering a query $q$ is equivalent to finding the set of entities $\llbracket q\rrbracket\subset\mathcal{V}$, where $v\in\llbracket q\rrbracket$ if and only if $q[v]$ is True.

Computation Graphs. Given a query, we represent the reasoning procedure as a computation graph (see Figure 1(a) 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$\rightarrow$Projection Operator $\mathcal{P}$. Given a set of entities $S\subset\mathcal{V}$ and a relational function $r\in\mathcal{R}$, the projection operator $\mathcal{P}$ outputs all the adjacent entities $\cup_{v\in S}N(v,r)$, where $N(v,r)$ is the set of entities such that $r(v,v^{\prime})=\text{True}$ for all $v^{\prime}\in N(v,r)$.

Conjunction$\rightarrow$Intersection Operator $\mathcal{I}$. Given $n$ sets of entities $\{S_{1},S_{2},\dots,S_{n}\}$, the intersection operator $\mathcal{I}$ performs set intersection to obtain $\cap_{i=1}^{n}S_{n}$.

Disjunction$\rightarrow$Union Operator $\mathcal{U}$. Given $n$ sets of entities $\{S_{1},S_{2},\dots,S_{n}\}$, the union operator $\mathcal{U}$ performs set union to obtain $\cup_{i=1}^{n}S_{n}$.

Negation$\rightarrow$Complement Operator $\mathcal{C}$. Given an entity set $S\subset\mathcal{V}$, $\mathcal{C}$ gives $\bar{S}=\mathcal{V}\backslash 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 $\llbracket q\rrbracket$, the aim of QE models is equivalent to embedding entity sets that can be answers to some queries.

2 Cones in Two-Dimensional Spaces

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.

By letting $\lambda=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.

Next, we introduce a class of cones that can be parameterized in a scalable way.

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.

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:

Specifically, $\theta_{\text{ax}}$ represents the angle between the symmetry axis of the sector-cone and the positive $x$ axis. $\theta_{\text{ap}}$ represents the aperture of the sector-cone. For any points in the cone, its phase will be in $[\theta_{\text{ax}}-\theta_{\text{ap}}/2,\theta_{\text{ax}}+\theta_{\text{ap}}/2]$. Figure 1(b) 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.

where $\theta_{\text{ax}}^{i}\in[-\pi,\pi),\ \theta_{\text{ap}}^{i}\in[0,2\pi]$, for $i=1,\dots,d$. Or equivalently, $C=(\bm{\theta}_{\text{ax}},\bm{\theta}_{\text{ap}})$, where $\bm{\theta}_{\text{ax}}=(\theta_{\text{ax}}^{1},\dots,\theta_{\text{ax}}^{d})\in[-\pi,\pi)^{d}$ and $\bm{\theta}_{\text{ap}}=(\theta_{\text{ap}}^{1},\dots,\theta_{\text{ap}}^{d})\in[0,2\pi]^{d}$.

Cone Embeddings

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.

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 $\mathcal{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 $\llbracket q\rrbracket$ into an embedding space, we expect entities in $\llbracket q\rrbracket$ 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 $\llbracket q\rrbracket$ and the boundary designates how many entities are in $\llbracket q\rrbracket$.

To model the embedding region of $\llbracket q\rrbracket$, we propose to embed it to a Cartesian product of sector-cones. Specifically, we use the parameter $\theta_{\text{ax}}^{i}$ to represent the semantic center, and the parameter $\theta_{\text{ap}}^{i}$ to determine the boundary of $\llbracket q\rrbracket$. If we use a $d$-ary Cartesian product, i.e., the embedding dimension is $d$, we define the embedding of $\llbracket q\rrbracket$ as

where $\bm{\theta}_{\text{ax}}\in[-\pi,\pi)^{d}$ are axes and $\bm{\theta}_{\text{ap}}\in[0,2\pi]^{d}$ are apertures.

An entity $v\in\mathcal{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 , where the axes indicates the semantics of the entity. Formally, if the embedding dimension is $d$, the cone embedding of $v$ is $\textbf{v}=(\bm{\theta}_{\text{ax}},\textbf{0})$, where $\bm{\theta}_{\text{ax}}\in[-\pi,\pi)^{d}$ is the axis embedding and 0 is a $d$-dimensional vector with all elements being .

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.

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 .

Projection Operator $\mathcal{P}$. The goal of $\mathcal{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 2(a)). Thus, we define a relation-dependent function in the embedding space for $\mathcal{P}$:

We implement $f_{r}$ in a neural way. First, we represent relations as relational translations of query embeddings and assign each relation with an embedding $\textbf{r}=(\bm{\theta}_{\text{ax},r},\bm{\theta}_{\text{ap},r})$. Then, we define $f_{r}$ as

where $[g(\textbf{x})]_{i}$ denotes the $i$-th element of $g(\textbf{x})$, $\lambda_{1}$ and $\lambda_{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 $\theta^{\prime i}_{\text{ax}}=-\pi$ and $\theta^{\prime i}_{\text{ap}}=0,2\pi$. However, when we implement $g$ in experiments, the value of $g$ can be very close to 0 and 2$\pi$, which is equivalent to the closed set numerically.

Intersection Operator $\mathcal{I}$. Given a query $q$ that is the conjunction of conjunctive queries $q_{i}$, the goal of $\mathcal{I}$ is to represent $\llbracket q\rrbracket=\cap_{i=1}^{n}\llbracket q_{i}\rrbracket$. Since the conjunction of conjunctive queries are still conjunctive queries, the entities in $\llbracket q\rrbracket$ 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 $\llbracket q\rrbracket$ (see Figure 2(b)). Suppose that $\textbf{V}_{q}^{c}=(\bm{\theta}_{\text{ax}},\bm{\theta}_{\text{ap}})$ and $\textbf{V}_{q_{i}}^{c}=(\bm{\theta}_{i,\text{ax}},\bm{\theta}_{i,\text{ap}})$ are cone embeddings for $\llbracket q\rrbracket$ and $\llbracket q_{i}\rrbracket$, respectively. We define the intersection operator as follows:

where $\textbf{SemanticAverage}(\cdot)$ and $\textbf{CardMin}(\cdot)$ generates semantic centers and apertures, respectively. In the following, we introduce these two functions in detail.

SemanticAverage. As the semantic center of $\textbf{V}_{q}^{c}$, $\bm{\theta}_{\text{ax}}$ should be close to all the semantic centers $\bm{\theta}_{i,\text{ax}}$. Thus, we propose to represent $\bm{\theta}_{\text{ax}}$ as a semantic average of $\bm{\theta}_{i,\text{ax}}$. We note that the ordinary weighted average may lead to inconsistent semantics. For example, when $d=1$, if $\bm{\theta}_{1,\text{ax}}=\pi-\epsilon$ and $\bm{\theta}_{2,\text{ax}}=-\pi+\epsilon$ ($0<\epsilon<\pi/4$), then we expect $\bm{\theta}_{\text{ax}}$ to be around $\pi$. However, if we use the ordinary weighted sum, $\bm{\theta}_{\text{ax}}$ will be around 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 $[\bm{\theta}_{i,\text{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

We use $\textbf{Arg}(\cdot)$ to recover angles of 2D points. Suppose that $\beta_{i}=\arctan([\textbf{y}]_{i}/[\textbf{x}]_{i})$, then

Note that $[\textbf{x}]_{i}=0$ will lead to an illegal division. In experiments, we manually set $[\textbf{x}]_{i}$ to be a small number (e.g., $10^{-3}$) when $[\textbf{x}]_{i}=0$.

CardMin. Since $\llbracket q\rrbracket$ is the subset of all $\llbracket q_{i}\rrbracket$, $\theta_{\text{ap}}^{i}$ should be no larger than any apertures $\theta_{j,\text{ap}}^{i}$. Therefore, we implement CardMin by a minimum mechanism with cardinality constraints:

where $\sigma(\cdot)$ is the element-wise sigmoid function, ${\theta}_{j,\text{ap}}^{i}$ is the $i$-th element of $\bm{\theta}_{j,\text{ap}}$, $\textbf{DeepSets}(\cdot)$ is a permutation-invariant function . Specifically, $\textbf{DeepSets}(\{\textbf{V}_{q_{j}}\}_{j=1}^{n})$ is computed by

Union Operator $\mathcal{U}$. Given a query $q$ that is the disjunction of conjunctive queries $q_{i}$, the goal of the union operator $\mathcal{U}$ is to represent $\llbracket q\rrbracket=\cup_{i=1}^{n}\llbracket q_{i}\rrbracket$. As noted by Ren et al. , directly modeling the disjunction leads to unscalable models. Thus, we adopt the DNF technique , in which the union operation only appears in the last step in computation graphs.

Suppose that $\textbf{V}_{q_{i}}^{c}=(\bm{\theta}_{i,\text{ax}},\bm{\theta}_{i,\text{ap}})$ are cone embeddings for $\llbracket q_{i}\rrbracket$. To represent the union of several cones (see Figure 2(c)), we represent $\llbracket q\rrbracket$ as a set of $\textbf{V}_{q_{i}}^{c}$:

where $n$ may be various in different queries. Equivalently, $\textbf{V}_{q}^{d}$ can be written as

As $\{({\theta}_{1,\text{ax}}^{i},{\theta}_{1,\text{ap}}^{i}),\dots,({\theta}_{n,\text{ax}}^{i},{\theta}_{n,\text{ap}}^{i})\}$ 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 $\mathcal{C}$. Given an conjunctive query $q$ and the corresponding entity set $\llbracket q\rrbracket$, the aim of $\mathcal{C}$ is to identify the set $\llbracket\neg q\rrbracket$, which is the complementary of $\llbracket q\rrbracket$, i.e., $\mathcal{V}\backslash\llbracket q\rrbracket$. Since the set of sector-cones is closed under closure-complement, we define $\mathcal{C}$ using the closure-complement. Thus, the apertures of $\textbf{V}_{q}$ plus the apertures of $\textbf{V}_{\neg q}$ should be a vector with all elements being $2\pi$. Moreover, to represent the semantic difference between $\llbracket q\rrbracket$ and $\llbracket\neg q\rrbracket$, we assume that their semantic centers to be opposite. Please refer to Figure 2(d) for a figure illustration.

Suppose that $\textbf{V}_{q}=(\bm{\theta}_{\text{ax}},\bm{\theta}_{\text{ap}})$ and $\textbf{V}_{\neg q}=(\bm{\theta}^{\prime}_{\text{ax}},\bm{\theta}^{\prime}_{\text{ap}})$. We define the complement operator $\mathcal{C}$ as:

3 Learning Cone Embeddings

To learn cone embeddings, we expect that the cone embeddings of entities $v\in\llbracket q\rrbracket$ are inside the cone embeddings of $q$, and the cone embeddings of entities $v^{\prime}\notin\llbracket q\rrbracket$ 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. , we divide the distance $d$ into two parts—the outside distance $d_{o}$ and the inside distance $d_{i}$. Figure 2(e) gives an illustration of the distance function $d$. Suppose that $\textbf{v}=(\bm{\theta}^{v}_{\text{ax}},\textbf{0})$, $\textbf{V}_{q}^{c}=(\bm{\theta}_{\text{ax}},\bm{\theta}_{\text{ap}})$, $\bm{\theta}_{L}=\bm{\theta}_{\text{ax}}-\bm{\theta}_{\text{ap}}/2$ and $\bm{\theta}_{U}=\bm{\theta}_{\text{ax}}+\bm{\theta}_{\text{ap}}/2$. We define the distance as

The outside distance and the inside distance are

where $\|\cdot\|_{1}$is the $L_{1}$ norm, $\sin(\cdot)$ and $\min(\cdot)$ 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 $\lambda\in(0,1)$ is fixed during training, so that v is encouraged to be inside the cones represented by $\textbf{V}_{q}^{c}$, but not necessarily be equal to the semantic center of $\textbf{V}_{q}^{c}$.

Since we represent the disjunctive queries as a set of embeddings, we cannot use $d_{con}$ 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=q_{1}\lor\dots\lor q_{n}$ in the Disjunctive Normal Form, the distance between $q$ and an entity is

If we use $\textbf{V}_{q}$ to represent embeddings of both kinds of queries, the unified distance function $d$ is

Training Objective. Given a training set of queries, we optimize a negative sampling loss

where $\gamma>0$ is a fixed margin, $v\in\llbracket q\rrbracket$ is a positive entity, $v_{i}^{\prime}\notin\llbracket q\rrbracket$ is the $i$-th negative entity, $k$ is the number of negative entities, and $\sigma(\cdot)$ is the sigmoid function.

Experiments

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.

We adopt the commonly used experimental settings for query embeddings .

Datasets and Queries. We use three datasets: FB15k , FB15k-237 (FB237) , and NELL995 (NELL) . 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 . 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 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 . We first build three KGs: the training KG $\mathcal{G}_{\text{train}}$, the validation KG $\mathcal{G}_{\text{valid}}$, and the test KG $\mathcal{G}_{\text{test}}$ using training edges, training+validation edges, training+validation+test edges, respectively. Given a test (validation) query $q$, we aim to discover non-trivial answers $\llbracket q\rrbracket_{\text{test}}\backslash\llbracket q\rrbracket_{\text{valid}}$ ($\llbracket q\rrbracket_{\text{valid}}\backslash\llbracket q\rrbracket_{\text{train}})$. 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 $\mathcal{V}\backslash\llbracket q\rrbracket_{\text{test}}$. 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 , Query2Box (Q2B) , and BETAE . 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 , 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.

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 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.

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 $\llbracket q\rrbracket$. 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 $\textbf{V}_{q}=(\bm{\theta}_{\text{ax}},\bm{\theta}_{\text{ap}})$ of a given query $q$, we use the $L_{1}$ norm of $\bm{\theta}_{\text{ap}}$ to represent the learned cardinality of $\llbracket q\rrbracket$. 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 .

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.

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 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 $(A_{i},B_{i})$, where $A_{i}\subset B_{i}$. Then, for each $i$, we randomly select a relation $r_{i}$ and calculate the projections $P_{r_{i}}(A_{i})$ and $P_{r_{i}}(B_{i})$. Ideally, the projected cones should satisfy $P_{r_{i}}(A_{i})\subset P_{r_{i}}(B_{i})$. We calculate the ratio $r_{i}=|P_{r_{i}}(A_{i})\cap P_{r_{i}}(B_{i})|/|P_{r_{i}}(A_{i})|$ to measure how many elements in $P_{r_{i}}(A_{i})$ are included in $P_{r_{i}}(A_{i})\cap P_{r_{i}}(B_{i})$. Finally, we get an average ratio $r=0.8113$. That is to say, the learned $P_{r_{i}}(A_{i})$ are included in $P_{r_{i}}(A_{i})$ 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 $(C_{i},D_{i})$, where $C_{i}\cap D_{i}$ is not guaranteed to be a sector-cone. Then, we generate embeddings $I(C_{i},D_{i})$ for the intersection $C_{i}\cap D_{i}$. Ideally, the learned cones $I(C_{i},D_{i})$ should be the same as the real cones $C_{i}\cap D_{i}$. We calculate the ratio $r_{i}=|I(C_{i},D_{i})\cap(C_{i}\cap D_{i})|/|I(C_{i},D_{i})\cup(C_{i}\cap D_{i})|$ to measure the overlap between $I(C_{i},D_{i})$ and $C_{i}\cap D_{i}$, 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. , 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.

Conclusion

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.

References

Appendix A Proof for Proposition 1

To show Proposition 1, we need the following defition and lemma.

$C$ is solid, which means it has nonempty interior,

$C$ is pointed, which means that it contains no line (or equivalently, $x\in C,-x\in C\Rightarrow x=0$).

where $\text{as}(K)$ is the axial symmetry degree of $K$. The upper bound becomes an equality if and only if $K$ is axially symmetric.

A sector-cone is always axially symmetric.

We further assume that $C$ is convex, contains no line, and has nonempty interior, i.e., it is a proper cone. By Lemma 1, we know that $C$ is axially symmetric. If $C$ is convex but contains a line, i.e., it is the half space, then it is axially symmetric. If $C$ has empty interior, i.e., it is a ray, then it is axially symmetric. Therefore, when $C$ is convex, it is axially symmetric.

Therefore, a sector-cone is always axially symmetric. ∎

Appendix B More Details about Experiments

In this section, we show more details about experiments that are not included in the main text due to the limited space.

For a fair comparison, we use the same datasets and query structures as those in Ren & Leskovec . The datasets is created by Ren & Leskovec based on two well-known knowledge graphs Freebase and NELL . They do not contain personally identifiable information or offensive content. Table 4 summarizes the number of different queries in different datasets. Figure 3 shows all the query structures used in the experiments.

B.2 Training Protocal

We run all the experiments on a single Nvidia Geforce RTX 3090 GPU card. All the models are implemented in Pytorch and based on the official implementation of BETAE Link: https://github.com/snap-stanford/KGReasoning, licensed under the MIT License. for a fair comparison. We search the learning rates in $\{5\times 10^{-5},10^{-4},5\times 10^{-4}\}$, the batch size in $\{128,256,512\}$, the embedding size in $\{200,400,800\}$, the negative sample sizes in $\{32,64,128\}$, and the margin $\gamma$ in $\{20,30,40,50,60\}$. For all the modules using multi-layer perceptron (MLP), we use a three-layer MLP with 1600 hidden neurons and ReLU activation. We apply dropout to the $\min$ function in CardMin and search the dropout rate in $\{0.05,0.10,0.15,0.20\}$. The best hyperparameters are shown in Table 5.

B.3 Evaluation Metrics

We choose Mean Reciprocal Rank (MRR) as the evaluation metric. Higher MRR indicates better performance. Definitions are as follows. The mean reciprocal rank is the average of the reciprocal ranks of results for a sample of queries Q:

Appendix C More Experimental Results

In this section, we give more experimental results that are not included in the main text due to the limited space.

Tables 6 and 7 show the results of BETAE with embedding dimensions 400 (B-400) and 800 (B-800). The results of B-400 is slightly better than that of B-800. Therefore, we report the results of B-400 in the main text.

C.2 Results on Disjunctive Queries

Since ConE is capable of modeling complement, we can also implement disjunctive queries using De Morgan’s law, i.e., $\cup_{i=1}^{n}S_{i}=\overline{\cap_{i=1}^{n}\overline{S}_{i}}$. Table 8 shows the results of $2u$ and $up$ queries that are implemented using both DNF (-N) and De Morgan’s law (-M). The results show that results of $\text{2u-M}/\text{up-M}$ are competitive compared with those of $\text{2u-N}/\text{up-N}$, which all outperform BETAE .

We can also see that ConE using De Morgan’s law perform worse than ConE using DNF. The results is reasonable and expectable. If we use the complement to handle queries with unions, their representations will always be sector-cones. However, not all such queries can be well represented by sector-cones (see Figure 3c in the main text).

C.3 Correlation Results

Tables 9 and 10 show the results of Spearman’s rank correlation between learned embeddings and the number of queries on FB15k-237 and NELL, respectively. The results of Query2Box (Q2B) and BETAE are taken from Ren & Leskovec . The symbol “$*$" indicates that the average performance is computed only using results of queries without negation.

Tables 11, 12 and 13 show the results of Pearson correlation between learned embeddings and the number of queries on FB15k, FB15k-237, and NELL, respectively. The results of Query2Box (Q2B) and BETAE are taken from Ren & Leskovec . The symbol “$*$" indicates that the average performance is computed only using results of queries without negation.

All the results show that ConE is effective in modeling the cardinality of queries’ answer sets.

C.4 Comparison with EmQL

We compare ConE with EmQL on FB15k that is from Query2Box . The dataset is the same as that in EmQL. Table 14 shows that ConE significantly outperforms EmQL and other baselines.

C.5 Error Bars of Main Results

To evaluate the multi-hop reasoning performance of ConE, we run the model five times with random seeds $\{0,10,100,1000,10000\}$. In this section, we report the error bars of these results. Table 15 shows the error bar of ConE’s MRR results on EPFO queries, i.e., queries without negation. Table 16 shows the error bar of ConE’s MRR results on queries with negation. Overall, the standard variances are small, which demonstrate that the performence of ConE is stable.

C.6 Union using De Morgan’s Law and the Real Union.

When we use De Morgan’s law to approximate the union, the resulted cones are always sector-cones, which may be inconsistent with the real union. We conduct experiments to compare the learned embeddings for $\neg(\neg A\land\neg B)$ and $A\lor B$. Specifically, we randomly generate $8000$ pairs of sector-cones $(A_{i},B_{i})$ and generate embeddings for $\neg(\neg A_{i}\cap\neg B_{i})$ and $A_{i}\cup B_{i}$. Then, to measure the overlap between $\neg(\neg A_{i}\cap\neg B_{i})$ and $A_{i}\cup B_{i}$ , we calculate the ratio $r_{i}=|(\neg(\neg A_{i}\cap\neg B_{i}))\cap(A_{i}\cup B_{i})|/|(\neg(\neg A_{i}\cap\neg B_{i}))\cup(A_{i}\cup B_{i})|$ , and obtain an average ratio of $r=0.4618$ . The results show a relatively high discrepancy between $\neg(\neg A_{i}\cap\neg B_{i})$ and $A_{i}\cup B_{i}$, which again validates the results that ConE with DNF technique can outperform ConE with De Morgan’s law.

C.7 Modeling the Variability of Answer Sets

It is possible that an answer set to a query has a large number of entities but small apertures. When it happens, there are two possible cases.

The semantic variability of the entities in this set is low. That is to say, entities in the set closely locate in a cone with a small aperture.

Some of the entities are outside the cone. The learned cone embeddings of a query may not include all its answer entities, especially for queries in the validation/test sets. This phenomenon also partly accounts for imperfect performance.

We conduct experiments on FB15k to demonstrate that the learned apertures are correlated with the similarity measures over answer sets. The results are shown in Table 17. In this experiment, suppose that we have an entity set $[[q]]=\{v_{1}^{q},\dots,v_{n_{q}}^{q}\}$ that is the answer set to a query $q$, and its corresponding embeddings $\{\textbf{v}_{1}^{q},\dots,\textbf{v}_{n_{q}}^{q}\}$ (note that their apertures are zero). First, we compute the average embeddings of $\{\textbf{v}_{1}^{q},\dots,\textbf{v}_{n_{q}}^{q}\}$ using SemanticAverage (all weights are set to be equal) introduced in Section 5.2. Then, we calculate the maximum squared distance from the entity embeddings to the average embeddings and let $\delta_{q}$ denote the result. That is, $\delta_{q}$ measures the overall variation of entities in $[[q]]$. Finally, we calculate the Spearman’s rank correlation and Pearson’s correlation between $\delta_{q}$ and the learned apertures of $q$.

Appendix D Semantic Average and Ordinary Average

We give a figure illustration of the difference between the ordinary and semantic average. When $d=1$, if $\bm{\theta}_{1,\text{ax}}=\pi-\epsilon$ and $\bm{\theta}_{2,\text{ax}}=-\pi+\epsilon$ ($0<\epsilon<\pi/4$), then we expect $\bm{\theta}_{\text{ax}}$ to be around $\pi$. However, if we use the ordinary weighted sum, $\bm{\theta}_{\text{ax}}$ will be around with a high probability.

Appendix E Determining Whether an Entity Belonging to an Answer Set

Whether an entity $v$ belongs to the answer set $[[q]]$ is determined by the outside distance $d_{o}(\textbf{V},\textbf{V}_{q})$, where V and $\textbf{V}_{q}$ are the cone embeddings for the entity $v$ and query $q$, respectively. Ideally, the entity $v$ belongs to the answer set $[[q]]$ when $d_{o}(\textbf{V},\textbf{V}_{q})=0$, i.e., the entity embedding V intersects all of the cones in the query embedding $\textbf{V}_{q}$. Accordingly, in the ideal case, an entity belongs to the complement if it intersects all of the cones in the negation query embedding. However, we allow some components of V outside the corresponding components of $\textbf{V}_{q}$ in practice. If $d_{o}(\textbf{V},\textbf{V}_{q})$ is small enough (e.g., smaller than a threshold), we can recognize the entity $v$ as an answer to the query $q$. Moreover, in this way, even if we have two entities that both have mismatched cones, we can say that one entity is more likely to be the answer than the other one by comparing their distances to the query embeddings.

We claim that geometry-based models can determine an entity as an answer to a given query if the cones/boxes represented the entity are inside the cones/boxes represented the query. We conduct experiments to validate the above claim. Specifically, we use trained models ConE/Query2Box with embedding dimensions $d=800$. That is, each entity and query is represented by a Cartesian product of $800$ cones/boxes. Given an entity embedding v and a query embedding $\textbf{V}_{q}$, if a majority (we use a threshold of $500$ in the experiments) of the $800$ cones/boxes of v are inside the cones/boxes of $\textbf{V}_{q}$, we regard the entity $v$ as an answer to the query $q$. Given a query in the validation/test set, we see its answer entities as positive samples and all the other entities in the KG as negative samples.

Table 18 shows the precision/recall results of the validation/test queries. Note that Query2Box does not apply to queries with negation, so we do not include the corresponding results. The results demonstrate that, using geometry-based models, we can determine whether an entity is an answer to a query by the inclusion relation between entity embeddings and query embeddings. Moreover, ConE outperforms Query2Box on the queries without negation, which is consistent with the results in Table 1 in the main text.

Appendix F Qualitative Analysis Between ConE and Query2Box

The embedding space and the operators are two key parts of a query embedding model. Therefore, we introduce the superiority of ConE over Query2Box in these two aspects.

Cones can naturally represent a finite universal set and its subset, while Query2Box cannot. The universal set in a knowledge graph corresponds to the set consisting of all the entities, which is finite. As the apertures of cones are bounded (between and $2\pi$), we can use the cones with apertures $2\pi$ to represent the universal set and find cones with proper apertures to represent any subsets of the universal set. However, since the offsets of boxes in Query2Box are unbounded, how to find boxes to represent the universal set is unclear. It is worth noting that we cannot constrain the offsets of boxes in Query2Box to be bounded, since the composition of its projection operator can generate boxes with arbitrarily large offsets.

The axes of cones are periodic while the centers of boxes are not. It is an important property to model symmetric relations. We will discuss it in detail in the next part.

F.2 Operators

The operators in query embedding models usually contain projection, intersection, union, and complement. The superiority of ConE over Query2Box mainly comes from the projection and complement operator.

The projection operator of ConE can generate cones with larger or smaller apertures depending on the relation. However, the projection operator of Query2Box always generates a larger box with a translated center, no matter what the relation is. In fact, not all the relation projections should result in larger boxes. For example, if an entity set contains all the countries in the world, and the relation is contain_cities, the set of adjacent entities will be larger. If the given entity set contains all cities in the world and the relation is locate_in_country, the set of adjacent entities will be smaller. Therefore, the projection operator of ConE is more expressive than that of Query2Box. An expressive projection operator can improve the performance on all the queries as projection appears in all query structures.

The projection operator of ConE can well deal with symmetric relations, while the translation-based projection operator of Query2Box cannot. Suppose that $r$ is a symmetric relation. That is, if $r(h,t)$ is true, then $r(t,h)$ will also be true (e.g., married_with). Suppose that the embedding dimension $d=1$ , the axis of $h$ is $\theta_{h}$, the axis of $t$ is $\theta_{t}$, and the apertures of $h$ and $t$ are . Then, ConE can model the symmetric relation by learning a neural operator that rotates some axes by an angle $\pi$ and keeps the apertures unchanged. That is, ConE can model the relation $r$ between $h$ and $t$ as $r(\theta_{h})=\theta_{h}+\pi=\theta_{t}$ and $r(\theta_{t})=\theta_{t}+\pi=\theta_{h}$, which is benefited from the periodicity. A similar case can be found in RotatE. RotatE can deal with symmetric relations since the phases in complex spaces are periodic.

Since the complements of boxes are no longer boxes, it is still unclear how to use boxes to model the complement operation.

Appendix G Computational Complexity

The computational complexity of ConE is similar to that of Query2Box . Given a query in Disjunctive Normal Form $q=q_{1}\lor\dots\lor q_{n}$, where $q_{i}$ are conjunctive queries, the computational complexity of ConE to answer $q$ is equal to that of answering the $n$ conjunctive queries $q_{i}$. Answering $q_{i}$ requires to execute a sequence of simple geometric cone operations, each of which takes constant time. Then, we perform a fast search using techniques such as Locality Sensitive Hashing to get the final answer.

To evaluate the training speed of ConE and all the baselines, we report the average time spent to run 100 training steps. We run all the models with the same number of embedding parameters using a single RTX 3090 GPU card. Table 20 demonstrates that the simplest model GQE is the most time-efficient. The training speed of ConE is close to that of Query2Box (Q2B) and faster than BetaE.

Appendix H Potential Societal Impacts

ConE is a method that performs automatic reasoning over knowledge graphs. One potential negative societal impacts when using automatic reasoning methods (including ConE) is privacy disclosure. If we use public data on the Internet or somewhere else to construct a knowledge graph, and then perform multi-hop reasoning over it, personal information that one does not want to make public may be exposed.