Query2box: Reasoning over Knowledge
Graphs in Vector Space using Box Embeddings
Query2box：使用盒子嵌入在向量空间中对知识图谱进行推理

We denote a KG as $\mathcal{G}=(\mathcal{V},\mathcal{R})$, where $v\in\mathcal{V}$ represents an entity, and $r\in\mathcal{R}$ is a binary function $r:\mathcal{V}\times\mathcal{V}\to\{\text{True},\text{False}\}$, indicating whether the relation $r$ holds between a pair of entities or not. In the KG, such binary output indicates the existence of the directed edge between a pair of entities, i.e., $v\xrightarrow{r}v^{\prime}$ iff $r(v,v^{\prime})=$ True.
我们将知识图谱表示为 $\mathcal{G}=(\mathcal{V},\mathcal{R})$ ，其中 $v\in\mathcal{V}$ 表示一个实体， $r\in\mathcal{R}$ 是一个二元函数 $r:\mathcal{V}\times\mathcal{V}\to\{\text{True},\text{False}\}$ ，表示关系 $r$ 是否在一对实体之间存在。在知识图谱中，这样的二元输出表示一对实体之间的有向边的存在，即当且仅当 $v\xrightarrow{r}v^{\prime}$ 为真时。

Conjunctive queries are a subclass of the first-order logical queries that use existential ($\exists$) and conjunction ($\wedge$) operations. They are formally defined as follows.
合取查询是一类使用存在量词（ $\exists$ ）和合取（ $\wedge$ ）操作的一阶逻辑查询的子类。它们的形式定义如下。

		$\displaystyle q[V_{?}]=V_{?}\>.\>\exists V_{1},\ldots,V_{k}:e_{1}\land e_{2}\land...\land e_{n},$		(1)
		$\displaystyle\textrm{where }\textrm{$e_{i}=r(v_{a},V)$},V\in\{V_{?},V_{1},\ldots,V_{k}\},v_{a}\in\mathcal{V},r\in\mathcal{R},$
		$\displaystyle\qquad\ \ \textrm{or }\textrm{$e_{i}=r(V,V^{\prime})$},V,V^{\prime}\in\{V_{?},V_{1},\ldots,V_{k}\},V\neq V^{\prime},r\in\mathcal{R},$

where $v_{a}$ represents non-variable anchor entity, $V_{1},\ldots,V_{k}$ are existentially quantified bound variables, $V_{?}$ is the target variable. The goal of answering the logical query $q$ is to find a set of entities $\llbracket q\rrbracket\subseteq\mathcal{V}$ such that $v\in\llbracket q\rrbracket$ iff $q[v]=$ True. We call $\llbracket q\rrbracket$ the denotation set (i.e., answer set) of query $q$.
其中 $v_{a}$ 表示非变量锚定实体， $V_{1},\ldots,V_{k}$ 是存在量化的绑定变量， $V_{?}$ 是目标变量。回答逻辑查询 $q$ 的目标是找到一组实体 $\llbracket q\rrbracket\subseteq\mathcal{V}$ ，使得 $v\in\llbracket q\rrbracket$ 当且仅当 $q[v]=$ 为真。我们称 $\llbracket q\rrbracket$ 为查询 $q$ 的指示集（即答案集）。

As shown in Fig. 1(A), the dependency graph is a graphical representation of conjunctive query $q$, where nodes correspond to variable or non-variable entities in $q$ and edges correspond to relations in $q$. In order for the query to be valid, the corresponding dependency graph needs to be a Directed Acyclic Graph (DAG), with the anchor entities as the source nodes of the DAG and the query target $V_{?}$ as the unique sink node (Hamilton et al., 2018).
如图 1（A）所示，依赖图是对连词查询 $q$ 的图形表示，其中节点对应于 $q$ 中的变量或非变量实体，边对应于 $q$ 中的关系。为了使查询有效，相应的依赖图需要是一个有向无环图（DAG），其中锚定实体作为 DAG 的源节点，查询目标 $V_{?}$ 作为唯一的汇节点（Hamilton 等，2018）。

From the dependency graph of query $q$, one can also derive the computation graph, which consists of two types of directed edges that represent operators over sets of entities:
从查询 $q$ 的依赖图中，还可以推导出计算图，它由两种类型的有向边组成，表示对实体集合的运算符：

• •

  Projection: Given a set of entities $S\subseteq\mathcal{V}$, and relation $r\in\mathcal{R}$, this operator obtains $\cup_{v\in S}A_{r}(v)$, where $A_{r}(v)\equiv\{v^{\prime}\in\mathcal{V}:\ r(v,v^{\prime})=\text{True}\}$.

  
  • 投影：给定实体集合 $S\subseteq\mathcal{V}$ 和关系 $r\in\mathcal{R}$ ，此运算符获得 $\cup_{v\in S}A_{r}(v)$ ，其中 $A_{r}(v)\equiv\{v^{\prime}\in\mathcal{V}:\ r(v,v^{\prime})=\text{True}\}$ 。
• •

  Intersection: Given a set of entity sets $\{S_{1},S_{2},\ldots,S_{n}\}$, this operator obtains $\cap_{i=1}^{n}S_{i}.$

  
  • 交集：给定一组实体集合 $\{S_{1},S_{2},\ldots,S_{n}\}$ ，此运算符获取 $\cap_{i=1}^{n}S_{i}.$

For a given query $q$, the computation graph specifies the procedure of reasoning to obtain a set of answer entities, i.e., starting from a set of anchor nodes, the above two operators are applied iteratively until the unique sink target node is reached. The entire procedure is analogous to traversing KGs following the computation graph (Guu et al., 2015).
对于给定的查询 $q$ ，计算图指定了推理过程，以获取一组答案实体，即从一组锚节点开始，以上两个运算符被迭代应用，直到达到唯一的目标节点。整个过程类似于按照计算图遍历知识图谱（Guu 等，2015）。

So far we have defined conjunctive queries as computation graphs that can be executed directly over the nodes and edges in the KG. Now, we define logical reasoning in the vector space. Our intuition follows Fig. 1: Given a complex query, we shall decompose it into a sequence of logical operations, and then execute these operations in the vector space. This way we will obtain the embedding of the query, and answers to the query will be entities that are enclosed in the final query embedding box.
迄今为止，我们已经将连词查询定义为可以直接在知识图谱中的节点和边上执行的计算图。现在，我们在向量空间中定义逻辑推理。我们的直觉遵循图 1：给定一个复杂的查询，我们将把它分解成一系列逻辑操作，然后在向量空间中执行这些操作。这样，我们将获得查询的嵌入，查询的答案将是包含在最终查询嵌入框中的实体。

In the following, we detail our two methodological advances: (1) the use of box embeddings to efficiently model and reason over sets of entities in the vector space, and (2) how to tractably handle disjunction operator ($\vee$), expanding the class of first-order logic that can be modeled in the vector space (Section 3.3).
在接下来的内容中，我们详细介绍了我们的两个方法论进展：（1）使用盒子嵌入来高效地对向量空间中的实体集进行建模和推理，以及（2）如何可行地处理析取运算符（ $\vee$ ），扩展了可以在向量空间中建模的一阶逻辑类别（第 3.3 节）。

Box embeddings. To efficiently model a set of entities in the vector space, we use boxes (i.e., axis-aligned hyper-rectangles). The benefit is that unlike a single point, the box has the interior; thus, if an entity is in a set, it is natural to model the entity embedding to be a point inside the box. Formally, we operate on $\mathbb{R}^{d}$, and define a box in $\mathbb{R}^{d}$ by $\mathbf{p}=(\text{Cen}(\mathbf{p}),\text{Off}(\mathbf{p}))\in\mathbb{R}^{2d}$ as:
盒子嵌入。为了在向量空间中高效地建模一组实体，我们使用盒子（即轴对齐的超矩形）。好处是，与单个点不同，盒子具有内部；因此，如果一个实体在一个集合中，将实体嵌入建模为盒子内的一个点是自然的。形式上，我们在 $\mathbb{R}^{d}$ 上操作，并将一个盒子定义为 $\mathbb{R}^{d}$ 乘以 $\mathbf{p}=(\text{Cen}(\mathbf{p}),\text{Off}(\mathbf{p}))\in\mathbb{R}^{2d}$ 。

$\displaystyle{\rm Box}_{\mathbf{p}}\equiv\{\mathbf{v}\in\mathbb{R}^{d}:\ \text{Cen}(\mathbf{p})-\text{Off}(\mathbf{p})\preceq\mathbf{v}\preceq\text{Cen}(\mathbf{p})+\text{Off}(\mathbf{p})\},$

(2)

where $\preceq$ is element-wise inequality, $\text{Cen}(\mathbf{p})\in\mathbb{R}^{d}$ is the center of the box, and $\text{Off}(\mathbf{p})\in\mathbb{R}^{d}_{\geq 0}$ is the positive offset of the box, modeling the size of the box. Each entity $v\in\mathcal{V}$ in KG is assigned a single vector $\mathbf{v}\in\mathbb{R}^{d}$ (i.e., a zero-size box), and the box embedding $\mathbf{p}$ models $\{v\in\mathcal{V}:\mathbf{v}\in{\rm Box}_{\mathbf{p}}\}$, i.e., a set of entities whose vectors are inside the box. For the rest of the paper, we use the bold face to denote the embedding, e.g., embedding of $v$ is denoted by $\mathbf{v}$.
其中 $\preceq$ 是逐元素不等式， $\text{Cen}(\mathbf{p})\in\mathbb{R}^{d}$ 是盒子的中心， $\text{Off}(\mathbf{p})\in\mathbb{R}^{d}_{\geq 0}$ 是盒子的正偏移量，模拟盒子的大小。KG 中的每个实体 $v\in\mathcal{V}$ 都被分配一个单一的向量 $\mathbf{v}\in\mathbb{R}^{d}$ （即零大小的盒子），盒子嵌入 $\mathbf{p}$ 模拟 $\{v\in\mathcal{V}:\mathbf{v}\in{\rm Box}_{\mathbf{p}}\}$ ，即一组向量在盒子内的实体。在本文的其余部分，我们使用粗体表示嵌入，例如 $v$ 的嵌入用 $\mathbf{v}$ 表示。

Our framework reasons over KGs in the vector space following the computation graph of the query, as shown in Fig. 1(D): we start from the initial box embeddings of the source nodes (anchor entities) and sequentially update the embeddings according to the logical operators. Below, we describe how we set initial box embeddings for the source nodes, as well as how we model projection and intersection operators (defined in Sec. 3.1) as geometric operators that operate over boxes. After that, we describe our entity-to-box distance function and the overall objective that learns embeddings as well as the geometric operators.
我们的框架在向量空间中通过查询的计算图推理知识图谱，如图 1(D) 所示：我们从源节点（锚定实体）的初始方框嵌入开始，根据逻辑运算符顺序更新嵌入。下面，我们描述了如何为源节点设置初始方框嵌入，以及我们如何将投影和交集运算符（在第 3.1 节中定义）作为在方框上操作的几何运算符进行建模。之后，我们描述了我们的实体到方框的距离函数和总体目标，该目标学习嵌入以及几何运算符。

Initial boxes for source nodes. Each source node represents an anchor entity $v\in\mathcal{V}$, which we can regard as a set that only contains the single entity. Such a single-element set can be naturally modeled by a box of size/offset zero centered at $\mathbf{v}$. Formally, we set the initial box embedding as $(\mathbf{v},\mathbf{0})$, where $\mathbf{v}\in\mathbb{R}^{d}$ is the anchor entity vector and $\mathbf{0}$ is a $d$-dimensional all-zero vector.
源节点的初始框。每个源节点代表一个锚定实体 $v\in\mathcal{V}$ ，我们可以将其视为仅包含单个实体的集合。这样的单元素集合可以通过一个大小/偏移为零且以 $\mathbf{v}$ 为中心的框来自然建模。形式上，我们将初始框嵌入设置为 $(\mathbf{v},\mathbf{0})$ ，其中 $\mathbf{v}\in\mathbb{R}^{d}$ 是锚定实体向量， $\mathbf{0}$ 是一个 $d$ 维全零向量。

Geometric projection operator. We associate each relation $r\in\mathcal{R}$ with relation embedding $\mathbf{r}=(\text{Cen}(\mathbf{r}),\text{Off}(\mathbf{r}))\in\mathbb{R}^{2d}$ with $\text{Off}(\mathbf{r})\succeq\mathbf{0}$. Given an input box embedding $\mathbf{p}$, we model the projection by $\mathbf{p}+\mathbf{r}$, where we sum the centers and sum the offsets. This gives us a new box with the translated center and larger offset because $\text{Off}(\mathbf{r})\succeq\mathbf{0}$, as illustrated in Fig. 2(A). The adaptive box size effectively models a different number of entities/vectors in the set.
几何投影运算符。我们将每个关系 $r\in\mathcal{R}$ 与关系嵌入 $\mathbf{r}=(\text{Cen}(\mathbf{r}),\text{Off}(\mathbf{r}))\in\mathbb{R}^{2d}$ 和 $\text{Off}(\mathbf{r})\succeq\mathbf{0}$ 相关联。给定一个输入框嵌入 $\mathbf{p}$ ，我们通过 $\mathbf{p}+\mathbf{r}$ 来建模投影，其中我们对中心点和偏移量进行求和。这样我们就得到一个新的框，其具有平移后的中心和更大的偏移量，因为 $\text{Off}(\mathbf{r})\succeq\mathbf{0}$ ，如图 2(A)所示。自适应框大小有效地模拟了集合中不同数量的实体/向量。

Geometric intersection operator. We model the intersection of a set of box embeddings $\{\mathbf{p_{1}},\ldots,\mathbf{p_{n}}\}$ as $\mathbf{p}_{{\rm inter}}=(\text{Cen}(\mathbf{p_{{\rm inter}}}),\text{Off}(\mathbf{p_{{\rm inter}}}))$, which is calculated by performing attention over the box centers (Bahdanau et al., 2015) and shrinking the box offset using the sigmoid function:
几何交集运算符。我们将一组盒子嵌入的交集建模为 $\mathbf{p}_{{\rm inter}}=(\text{Cen}(\mathbf{p_{{\rm inter}}}),\text{Off}(\mathbf{p_{{\rm inter}}}))$ ，通过对盒子中心进行注意力计算（Bahdanau 等人，2015），并使用 sigmoid 函数缩小盒子偏移量来计算。

	$\displaystyle\text{Cen}(\mathbf{p_{{\rm inter}}})=\sum_{i}\mathbf{a}_{i}\odot\text{Cen}(\mathbf{p_{i}}),\ \ \mathbf{a}_{i}=\frac{\exp(\textsc{MLP}(\mathbf{p_{i}}))}{\sum_{j}{\exp(\textsc{MLP}(\mathbf{p_{j}}))}},$
	$\displaystyle\text{Off}(\mathbf{p_{{\rm inter}}})={\rm Min}(\{\text{Off}(\mathbf{p_{1}}),\dots,\text{Off}(\mathbf{p_{n}})\})\odot\sigma({\rm DeepSets}(\{\mathbf{p_{1}},\dots,\mathbf{p_{n}}\})),$

where $\odot$ is the dimension-wise product, ${\rm MLP}(\cdot):\mathbb{R}^{2d}\to\mathbb{R}^{d}$ is the Multi-Layer Perceptron, $\sigma(\cdot)$ is the sigmoid function, ${\rm DeepSets}(\cdot)$ is the permutation-invariant deep architecture (Zaheer et al., 2017), and both ${\rm Min}(\cdot)$ and ${\exp}(\cdot)$ are applied in a dimension-wise manner. Following Hamilton et al. (2018), we model all the deep sets by ${\rm DeepSets}(\{\mathbf{x_{1}},\ldots,\mathbf{x_{N}}\})={\rm MLP}((1/N)\cdot\sum_{i=1}^{N}{\rm MLP}(\mathbf{x_{i}}))$, where all the hidden dimensionalities of the two MLPs are the same as the input dimensionality. The intuition behind our geometric intersection is to generate a smaller box that lies inside a set of boxes, as illustrated in Fig. 2(B).¹¹1One possible choice here would be to directly use raw box intersection, however, we find that our richer learnable parameterization is more expressive and robust
在这里，一个可能的选择是直接使用原始的框交集，然而，我们发现我们更丰富的可学习参数化更具表达能力和鲁棒性。
其中 $\odot$ 是按维度求积， ${\rm MLP}(\cdot):\mathbb{R}^{2d}\to\mathbb{R}^{d}$ 是多层感知机， $\sigma(\cdot)$ 是 sigmoid 函数， ${\rm DeepSets}(\cdot)$ 是排列不变的深度架构（Zaheer 等人，2017），而 ${\rm Min}(\cdot)$ 和 ${\exp}(\cdot)$ 都以按维度的方式应用。根据 Hamilton 等人（2018）的方法，我们通过 ${\rm DeepSets}(\{\mathbf{x_{1}},\ldots,\mathbf{x_{N}}\})={\rm MLP}((1/N)\cdot\sum_{i=1}^{N}{\rm MLP}(\mathbf{x_{i}}))$ 对所有深度集进行建模，其中两个 MLP 的隐藏维度与输入维度相同。我们几何交集背后的直觉是生成一个位于一组盒子内部的较小盒子，如图 2(B)所示。 ¹ Different from the generic deep sets to model the intersection (Hamilton et al., 2018), our geometric intersection operator effectively constrains the center position and models the shrinking set size.
与通用的深度集合不同，用于模拟交集的几何交集运算符有效地约束了中心位置并模拟了收缩的集合大小。

Entity-to-box distance. Given a query box $\mathbf{q}\in\mathbb{R}^{2d}$ and an entity vector $\mathbf{v}\in\mathbb{R}^{d}$, we define their distance as
实体到框的距离。给定一个查询框 $\mathbf{q}\in\mathbb{R}^{2d}$ 和一个实体向量 $\mathbf{v}\in\mathbb{R}^{d}$ ，我们将它们的距离定义为

$\displaystyle{\rm dist}_{\rm box}(\mathbf{v};\mathbf{q})={\rm dist}_{\rm outside}(\mathbf{v};\mathbf{q})+\alpha\cdot{\rm dist}_{\rm inside}(\mathbf{v};\mathbf{q}),$

(3)

where $\mathbf{q_{\rm max}}=\text{Cen}(\mathbf{q})+\text{Off}(\mathbf{q})\in\mathbb{R}^{d}$, $\mathbf{q_{\rm min}}=\text{Cen}(\mathbf{q})-\text{Off}(\mathbf{q})\in\mathbb{R}^{d}$ and $0<\alpha<1$ is a fixed scalar, and
其中 $\mathbf{q_{\rm max}}=\text{Cen}(\mathbf{q})+\text{Off}(\mathbf{q})\in\mathbb{R}^{d}$ ， $\mathbf{q_{\rm min}}=\text{Cen}(\mathbf{q})-\text{Off}(\mathbf{q})\in\mathbb{R}^{d}$ 和 $0<\alpha<1$ 是固定标量，而

	$\displaystyle{\rm dist}_{\rm outside}(\mathbf{v};\mathbf{q})=\|{\rm Max}(\mathbf{v}-\mathbf{q_{\rm max}},\mathbf{0})+{\rm Max}(\mathbf{q_{\rm min}}-\mathbf{v},\mathbf{0})\|_{1},$
	$\displaystyle{\rm dist}_{\rm inside}(\mathbf{v};\mathbf{q})=\|\text{Cen}(\mathbf{q})-{\rm Min}(\mathbf{q_{\rm max}},{\rm Max}(\mathbf{q_{\rm min}},\mathbf{v}))\|_{1}.$

As illustrated in Fig. 2(C), ${\rm dist}_{\rm outside}$ corresponds to the distance between the entity and closest corner/side of the box. Analogously, ${\rm dist}_{\rm inside}$ corresponds to the distance between the center of the box and its side/corner (or the entity itself if the entity is inside the box).
如图 2（C）所示， ${\rm dist}_{\rm outside}$ 对应于实体与盒子最近的角/边之间的距离。类似地， ${\rm dist}_{\rm inside}$ 对应于盒子的中心与其边/角之间的距离（或者如果实体在盒子内，则对应于实体本身）。

The key here is to downweight the distance inside the box by using $0<\alpha<1$. This means that as long as entity vectors are inside the box, we regard them as “close enough” to the query center (i.e., ${\rm dist}_{\rm outside}$ is 0, and ${\rm dist}_{\rm inside}$ is scaled by $\alpha$). When $\alpha=1$, ${\rm dist}_{\rm box}$ reduces to the ordinary $L_{1}$ distance, i.e., $\|\text{Cen}(\mathbf{q})-\mathbf{v}\|_{1}$, which is used by the conventional TransE (Bordes et al., 2013) as well as prior query embedding methods (Guu et al., 2015; Hamilton et al., 2018).
关键在于使用 $0<\alpha<1$ 对盒子内部的距离进行降权。这意味着只要实体向量在盒子内部，我们将其视为与查询中心“足够接近”（即 ${\rm dist}_{\rm outside}$ 为 0， ${\rm dist}_{\rm inside}$ 按 $\alpha$ 进行缩放）。当 $\alpha=1$ 时， ${\rm dist}_{\rm box}$ 变为普通的 $L_{1}$ 距离，即 $\|\text{Cen}(\mathbf{q})-\mathbf{v}\|_{1}$ ，这是传统的 TransE（Bordes 等人，2013）以及先前的查询嵌入方法（Guu 等人，2015；Hamilton 等人，2018）所使用的。

Training objective. Our next goal is to learn entity embeddings as well as geometric projection and intersection operators.
训练目标。我们的下一个目标是学习实体嵌入以及几何投影和交集运算符。

Given a training set of queries and their answers, we optimize a negative sampling loss (Mikolov et al., 2013) to effectively optimize our distance-based model (Sun et al., 2019):
鉴于一组查询及其答案的训练集，我们优化负采样损失（Mikolov 等人，2013）以有效优化我们的基于距离的模型（Sun 等人，2019）：

$\displaystyle L$

$\displaystyle=-\log\sigma\left(\gamma-{\rm dist}_{\rm box}(\mathbf{v};\mathbf{q})\right)-\sum_{i=1}^{k}\frac{1}{k}\log\sigma\left({\rm dist}_{\rm box}(\mathbf{v_{i}^{\prime}};\mathbf{q})-\gamma\right),$

(4)

where $\gamma$ represents a fixed scalar margin, $v\in\llbracket q\rrbracket$ is a positive entity (i.e., answer to the query $q$), and $v_{i}^{\prime}\notin\llbracket q\rrbracket$ is the $i$-th negative entity (non-answer to the query $q$) and $k$ is the number of negative entities.
其中 $\gamma$ 代表固定的标量边界， $v\in\llbracket q\rrbracket$ 是一个正实体（即，回答查询 $q$ 的答案）， $v_{i}^{\prime}\notin\llbracket q\rrbracket$ 是第 $i$ 个负实体（非查询 $q$ 的答案）， $k$ 是负实体的数量。

So far we have focused on conjunctive queries, and our aim here is to tractably handle in the vector space a wider class of logical queries, called Existential Positive First-order (EPFO) queries (Dalvi & Suciu, 2012) that involve $\vee$ in addition to $\exists$ and $\wedge$. We specifically focus on EPFO queries whose computation graphs are a DAG, same as that of conjunctive queries (Section 3.1), except that we now have an additional type of directed edge, called union defined as follows:
到目前为止，我们专注于合取查询，并且我们的目标是在向量空间中可解地处理更广泛的逻辑查询，称为存在性正一阶（EPFO）查询（Dalvi＆Suciu，2012），其中除了 $\exists$ 和 $\wedge$ 之外还涉及 $\vee$ 。我们特别关注 EPFO 查询的计算图是一个 DAG，与合取查询的计算图相同（第 3.1 节），只是现在我们有了一种额外类型的有向边，称为并集，定义如下：

• •

  Union: Given a set of entity sets $\{S_{1},S_{2},\ldots,S_{n}\}$, this operator obtains $\cup_{i=1}^{n}S_{i}.$

  
  • 联合：给定一组实体集合 $\{S_{1},S_{2},\ldots,S_{n}\}$ ，此运算符获取 $\cup_{i=1}^{n}S_{i}.$

A straightforward approach here would be to define another geometric operator for union and embed the query as we did in the previous sections. An immediate challenge for our box embeddings is that boxes can be located anywhere in the vector space, so their union would no longer be a simple box. In other words, union operation over boxes is not closed.
这里的一个直接方法是为并集定义另一个几何运算符，并像我们在前面的部分中所做的那样嵌入查询。我们的盒子嵌入面临的一个直接挑战是盒子可以位于向量空间的任何位置，因此它们的并集将不再是一个简单的盒子。换句话说，盒子的并集运算不是封闭的。

Theoretically, we prove a general negative result that holds for any embedding-based method that embeds query $q$ into $\mathbf{q}$ and uses some distance function to retrieve entities, i.e., ${\rm dist}(\mathbf{v};\mathbf{q})\leq\beta$ iff $v\in\llbracket q\rrbracket$. Here, ${\rm dist}(\mathbf{v};\mathbf{q})$ is the distance between entity and query embeddings, e.g., ${\rm dist}_{\rm box}(\mathbf{v};\mathbf{q})$ or $\|\mathbf{v}-\mathbf{q}\|_{1}$, and $\beta$ is a fixed threshold.
从理论上讲，我们证明了一个普遍的负面结果，适用于任何将查询 $q$ 嵌入到 $\mathbf{q}$ 并使用某种距离函数来检索实体的基于嵌入的方法，即当且仅当 $v\in\llbracket q\rrbracket$ 时 ${\rm dist}(\mathbf{v};\mathbf{q})\leq\beta$ 。这里， ${\rm dist}(\mathbf{v};\mathbf{q})$ 是实体和查询嵌入之间的距离，例如 ${\rm dist}_{\rm box}(\mathbf{v};\mathbf{q})$ 或 $\|\mathbf{v}-\mathbf{q}\|_{1}$ ，而 $\beta$ 是一个固定的阈值。

The proof is provided in Appendix A, where the key is that with the introduction of the union operation any subset of denotation sets can be the answer, which forces us to model the powerset $\{\cup_{{}_{q_{i}\in S}}\llbracket q_{i}\rrbracket:S\subseteq\{q_{1},\ldots,q_{M}\}\}$ in a vector space.
证明在附录 A 中提供，关键在于引入并操作后，任何指示集的子集都可以成为答案，这迫使我们在一个向量空间中建模幂集 $\{\cup_{{}_{q_{i}\in S}}\llbracket q_{i}\rrbracket:S\subseteq\{q_{1},\ldots,q_{M}\}\}$ 。

For a real-world KG, there are $M\approx|\mathcal{V}|$ conjunctive queries with non-overlapping answers. For example, in the commonly-used FB15k dataset (Bordes et al., 2013), derived from the Freebase (Bollacker et al., 2008), we find $M$ = 13,365, while $|\mathcal{V}|$ is 14,951 (see Appendix B for the details).
对于一个真实世界的知识图谱，存在 $M\approx|\mathcal{V}|$ 个具有非重叠答案的连结查询。例如，在常用的 FB15k 数据集（Bordes 等人，2013）中，源自 Freebase（Bollacker 等人，2008），我们发现 $M$ = 13,365，而 $|\mathcal{V}|$ 为 14,951（详见附录 B）。

Theorem 1 shows that in order to accurately model any EPFO query with the existing framework, the complexity of the distance function measured by the VC dimension needs to be as large as the number of KG entities. This implies that if we use common distance functions based on hyper-plane, Euclidean sphere, or axis-aligned rectangle,²²2For the detailed VC dimensions of these function classes, see Vapnik (2013). Crucially, their VC dimensions are all linear with respect to the number of parameters $d$.
对于这些函数类的详细 VC 维度，请参阅 Vapnik（2013）。关键是，它们的 VC 维度都与参数数量成线性关系 $d$ 。
定理 1 表明，为了准确地模拟任何现有框架中的 EPFO 查询，距离函数的复杂度（由 VC 维度度量）需要与知识图谱实体的数量一样大。这意味着，如果我们使用基于超平面、欧几里得球体或轴对齐矩形的常见距离函数， ² their parameter dimensionality needs to be $\Theta(M)$, which is $\Theta(|\mathcal{V}|)$ for real KGs we are interested in. In other words, the dimensionality of the logical query embeddings needs to be $\Theta(|\mathcal{V}|)$, which is not low-dimensional; thus not scalable to large KGs and not generalizable in the presence of unobserved KG edges.
它们的参数维度需要是 $\Theta(M)$ ，对于我们感兴趣的真实知识图谱来说，这是 $\Theta(|\mathcal{V}|)$ 。换句话说，逻辑查询嵌入的维度需要是 $\Theta(|\mathcal{V}|)$ ，这并不是低维的；因此在大型知识图谱中不具有可扩展性，并且在存在未观察到的知识图谱边缘时不具有泛化能力。

To rectify this issue, our key idea is to transform a given EPFO query into a Disjunctive Normal Form (DNF) (Davey & Priestley, 2002), i.e., disjunction of conjunctive queries, so that union operation only appears in the last step. Each of the conjunctive queries can then be reasoned in the low-dimensional space, after which we can aggregate the results by a simple and intuitive procedure. In the following, we describe the transformation to DNF and the aggregation procedure.
为了纠正这个问题，我们的关键思想是将给定的 EPFO 查询转化为析取范式（DNF）（Davey＆Priestley，2002），即合取查询的析取，以便联合操作仅出现在最后一步。然后，可以在低维空间中推理每个合取查询，然后通过简单直观的过程聚合结果。接下来，我们将描述转换为 DNF 和聚合过程。

Transformation to DNF. Any first-order logic can be transformed into the equivalent DNF (Davey & Priestley, 2002). We perform such transformation directly in the space of computation graph, i.e., moving all the edges of type “union” to the last step of the computation graph. Let $G_{q}=(V_{q},E_{q})$ be the computation graph for a given EPFO query $q$, and let $V_{\rm union}\subset V_{q}$ be a set of nodes whose in-coming edges are of type “union”. For each $v\in V_{\rm union}$, define $P_{v}\subset V_{q}$ as a set of its parent nodes. We first generate $N=\prod_{v\in V_{\rm union}}|P_{v}|$ different computation graphs $G_{q^{(1)}},\ldots,G_{q^{(N)}}$ as follows, each with different choices of $v_{\rm parent}$ in the first step.
将逻辑转换为 DNF 形式。任何一阶逻辑都可以转换为等价的 DNF 形式（Davey＆Priestley，2002）。我们直接在计算图空间中进行这种转换，即将所有类型为“union”的边移动到计算图的最后一步。设 $G_{q}=(V_{q},E_{q})$ 为给定 EPFO 查询 $q$ 的计算图，设 $V_{\rm union}\subset V_{q}$ 为一组入边类型为“union”的节点。对于每个 $v\in V_{\rm union}$ ，将 $P_{v}\subset V_{q}$ 定义为其父节点的集合。我们首先生成 $N=\prod_{v\in V_{\rm union}}|P_{v}|$ 个不同的计算图 $G_{q^{(1)}},\ldots,G_{q^{(N)}}$ ，如下所示，每个计算图在第一步中选择不同的 $v_{\rm parent}$ 。

1. 1.

   For every $v\in V_{\rm union}$, select one parent node $v_{\rm parent}\in P_{v}$.

   
   1. 对于每个 $v\in V_{\rm union}$ ，选择一个父节点 $v_{\rm parent}\in P_{v}$ 。
2. 2.

   Remove all the edges of type ‘union.’

   
   删除所有类型为“union”的边缘。
3. 3.

   Merge $v$ and $v_{\rm parent}$, while retaining all other edge connections.

   
   3. 合并 $v$ 和 $v_{\rm parent}$ ，同时保留所有其他边连接。

We then combine the obtained computation graphs $G_{q^{(1)}},\ldots,G_{q^{(N)}}$ as follows to give the final equivalent computation graph.
然后，我们按照以下方式组合所得到的计算图 $G_{q^{(1)}},\ldots,G_{q^{(N)}}$ ，以得到最终等效的计算图。

1. 1.

   Convert the target sink nodes of all the obtained computation graphs into the existentially quantified bound variables nodes.

   
   1. 将所有所得计算图的目标汇节点转换为存在量化的绑定变量节点。
2. 2.

   Create a new target sink node $V_{?}$, and draw directed edges of type “union” from all the above variable nodes to the new target node.

   
   2. 创建一个新的目标接收节点 $V_{?}$ ，并从所有上述变量节点绘制类型为“union”的有向边指向新的目标节点。

An example of the entire transformation procedure is illustrated in Fig. 3. By the definition of the union operation, our procedure gives the equivalent computation graph as the original one. Furthermore, as all the union operators are removed from $G_{q^{(1)}},\ldots,G_{q^{(N)}}$, all of these computation graphs represent conjunctive queries, which we denote as $q^{(1)},\ldots,q^{(N)}$. We can then apply existing framework to obtain a set of embeddings for these conjunctive queries as $\mathbf{q^{(1)}},\ldots,\mathbf{q^{(N)}}$.
整个转换过程的示例如图 3 所示。根据并集操作的定义，我们的过程给出了与原始计算图等效的计算图。此外，由于所有的并集运算符都从 $G_{q^{(1)}},\ldots,G_{q^{(N)}}$ 中移除了，所有这些计算图都表示合取查询，我们将其表示为 $q^{(1)},\ldots,q^{(N)}$ 。然后，我们可以应用现有的框架为这些合取查询获取一组嵌入，如 $\mathbf{q^{(1)}},\ldots,\mathbf{q^{(N)}}$ 所示。

Aggregation. Next we define the distance function between the given EPFO query $q$ and an entity $v\in\mathcal{V}$. Since $q$ is logically equivalent to $q^{(1)}\vee\cdots\vee q^{(N)}$, we can naturally define the aggregated distance function using the box distance ${\rm dist}_{\rm box}$:
聚合。接下来，我们定义给定的 EPFO 查询 $q$ 与实体 $v\in\mathcal{V}$ 之间的距离函数。由于 $q$ 在逻辑上等价于 $q^{(1)}\vee\cdots\vee q^{(N)}$ ，我们可以自然地使用盒子距离 ${\rm dist}_{\rm box}$ 定义聚合距离函数：

$\displaystyle{\rm dist}_{\rm agg}(\mathbf{v};q)={\rm Min}(\{{\rm dist}_{\rm box}(\mathbf{v};\mathbf{q^{(1)}}),\ldots,{\rm dist}_{\rm box}(\mathbf{v};\mathbf{q^{(N)}})\}),$

(5)

where ${\rm dist}_{\rm agg}$ is parameterized by the EPFO query $q$. When $q$ is a conjunctive query, i.e., $N=1$, ${\rm dist}_{\rm agg}(\mathbf{v};q)={\rm dist}_{\rm box}(\mathbf{v};\mathbf{q})$. For $N>1$, ${\rm dist}_{\rm agg}$ takes the minimum distance to the closest box as the distance to an entity. This modeling aligns well with the union operation; an entity is inside the union of sets as long as the entity is in one of the sets. Note that our DNF-query rewriting scheme is general and is able to extend any method that works for conjunctive queries (e.g., (Hamilton et al., 2018)) to handle more general class of EPFO queries.
其中 ${\rm dist}_{\rm agg}$ 由 EPFO 查询 $q$ 参数化。当 $q$ 是一个合取查询，即 $N=1$ ， ${\rm dist}_{\rm agg}(\mathbf{v};q)={\rm dist}_{\rm box}(\mathbf{v};\mathbf{q})$ 。对于 $N>1$ ， ${\rm dist}_{\rm agg}$ 将最小距离取为到最近盒子的距离作为实体的距离。这种建模与并集操作很好地对齐；只要实体在其中一个集合中，实体就在集合的并集中。请注意，我们的 DNF 查询重写方案是通用的，并且能够扩展任何适用于合取查询的方法（例如（Hamilton 等，2018））以处理更一般的 EPFO 查询类别。

Computational complexity. The computational complexity of answering an EPFO query with our framework is equal to that of answering the $N$ conjunctive queries. In practice, $N$ might not be so large, and all the $N$ computations can be parallelized. Furthermore, answering each conjunctive query is very fast as it requires us to execute a sequence of simple box operations (each of which takes constant time) and then perform a range search (Bentley & Friedman, 1979) in the embedding space, which can also be done in constant time using techniques based on Locality Sensitive Hashing (Indyk & Motwani, 1998).
计算复杂性。使用我们的框架回答 EPFO 查询的计算复杂性等于回答 $N$ 个合取查询的复杂性。在实践中， $N$ 可能不会很大，并且所有的 $N$ 计算可以并行化。此外，回答每个合取查询非常快速，因为它要求我们执行一系列简单的盒子操作（每个操作都需要恒定时间），然后在嵌入空间中执行范围搜索（Bentley＆Friedman，1979），这也可以使用基于局部敏感哈希（Indyk＆Motwani，1998）的技术在恒定时间内完成。

We perform experiments on three standard KG benchmarks, FB15k (Bordes et al., 2013), FB15k-237 (Toutanova & Chen, 2015), and NELL995 (Xiong et al., 2017) (see Appendix E for NELL995 pre-processing details). Dataset statistics are summarized in Table 5 in Appendix F.
我们在三个标准 KG 基准测试上进行实验，分别是 FB15k（Bordes 等，2013）、FB15k-237（Toutanova 和 Chen，2015）和 NELL995（Xiong 等，2017）（NELL995 预处理详细信息请参见附录 E）。数据集统计信息总结在附录 F 的表 5 中。

We follow the standard evaluation protocol in KG literture: Given the standard split of edges into training, test, and validation sets, we first augment the KG to also include inverse relations and effectively double the number of edges in the graph. We then create three graphs: $\mathcal{G}_{\text{train}}$, which only contains training edges and we use this graph to train node embeddings as well as box operators. We then also generate two bigger graphs: $\mathcal{G}_{\text{valid}}$, which contains $\mathcal{G}_{\text{train}}$ plus the validation edges, and $\mathcal{G}_{\text{test}}$, which includes $\mathcal{G}_{\text{valid}}$ as well as the test edges.
我们遵循 KG 文献中的标准评估协议：根据将边缘分为训练、测试和验证集的标准拆分，我们首先扩充 KG，使其包括逆关系，并有效地将图中的边缘数量加倍。然后我们创建三个图： $\mathcal{G}_{\text{train}}$ ，仅包含训练边缘，我们使用该图来训练节点嵌入以及盒子操作符。然后我们还生成两个更大的图： $\mathcal{G}_{\text{valid}}$ ，包含 $\mathcal{G}_{\text{train}}$ 以及验证边缘，以及 $\mathcal{G}_{\text{test}}$ ，包括 $\mathcal{G}_{\text{valid}}$ 以及测试边缘。

We consider 9 kinds of diverse query structures shown and named in Fig. 4. We use 5 query structures for training and then evaluate on all the 9 query structures. We refer the reader to Appendix D for full details on query generation and Table 6 in Appendix F for statistics of the generated logical queries. Given a query $q$, let $\llbracket q\rrbracket_{\text{train}}$, $\llbracket q\rrbracket_{\text{val}}$, and $\llbracket q\rrbracket_{\text{test}}$ denote a set of answer entities obtained by running subgraph matching of $q$ on $\mathcal{G}_{\text{train}}$, $\mathcal{G}_{\text{valid}}$, and $\mathcal{G}_{\text{test}}$, respectively. At the training time, we use $\llbracket q\rrbracket_{\text{train}}$ as positive examples for the query and other random entities as negative examples. However, at the test/validation time we proceed differently. Note that we focus on answering queries where generalization performance is crucial and at least one edge needs to be imputed in order to answer the queries. Thus, rather than evaluating a given query on the full validation (or test) set $\llbracket q\rrbracket_{\text{val}}$ ($\llbracket q\rrbracket_{\text{test}}$) of answers, we validate the method only on answers that include missing relations. Given how we constructed $\mathcal{G}_{\text{train}}\subseteq\mathcal{G}_{\text{valid}}\subseteq\mathcal{G}_{\text{test}}$, we have $\llbracket q\rrbracket_{\text{train}}\subseteq\llbracket q\rrbracket_{\text{val}}\subseteq\llbracket q\rrbracket_{\text{test}}$ and thus we evaluate the method on $\llbracket q\rrbracket_{\text{val}}\backslash\llbracket q\rrbracket_{\text{train}}$ to tune hyper-parameters and then report results identifying answer entities in $\llbracket q\rrbracket_{\text{test}}\backslash\llbracket q\rrbracket_{\text{val}}$. This means we always evaluate on queries/entities that were not part of the training set and the method has not seen them before. Furthermore, for these queries, traditional graph traversal techniques would not be able to find the answers (due to missing relations).
我们考虑了图 4 中展示和命名的 9 种不同的查询结构。我们使用 5 种查询结构进行训练，然后在所有 9 种查询结构上进行评估。有关查询生成的详细信息，请参见附录 D；生成的逻辑查询的统计信息，请参见附录 F 中的表 6。给定一个查询 $q$ ，让 $\llbracket q\rrbracket_{\text{train}}$ ， $\llbracket q\rrbracket_{\text{val}}$ 和 $\llbracket q\rrbracket_{\text{test}}$ 分别表示通过在 $\mathcal{G}_{\text{train}}$ ， $\mathcal{G}_{\text{valid}}$ 和 $\mathcal{G}_{\text{test}}$ 上运行子图匹配 $q$ 获得的一组答案实体。在训练时，我们使用 $\llbracket q\rrbracket_{\text{train}}$ 作为查询的正例，其他随机实体作为负例。然而，在测试/验证时，我们采取不同的方法。请注意，我们专注于回答在泛化性能至关重要且至少需要填充一个边以回答查询的查询。因此，我们不会在完整的验证（或测试）答案集 $\llbracket q\rrbracket_{\text{val}}$ （ $\llbracket q\rrbracket_{\text{test}}$ ）上评估给定的查询，而是仅在包含缺失关系的答案上验证该方法。鉴于我们构建了 $\mathcal{G}_{\text{train}}\subseteq\mathcal{G}_{\text{valid}}\subseteq\mathcal{G}_{\text{test}}$ ，我们有 $\llbracket q\rrbracket_{\text{train}}\subseteq\llbracket q\rrbracket_{\text{val}}\subseteq\llbracket q\rrbracket_{\text{test}}$ ，因此我们在 $\llbracket q\rrbracket_{\text{val}}\backslash\llbracket q\rrbracket_{\text{train}}$ 上评估该方法以调整超参数，然后报告在 $\llbracket q\rrbracket_{\text{test}}\backslash\llbracket q\rrbracket_{\text{val}}$ 中识别答案实体的结果。 这意味着我们始终对不在训练集中的查询/实体进行评估，而且该方法以前从未见过它们。此外，对于这些查询，传统的图遍历技术将无法找到答案（因为缺少关系）。