【论文解读 ICLR 2020 | Jure Leskovec组】Query2box: Reasoning over KGs in Vector Space using Box Embedding
论文题目:Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings
论文来源:ICLR 2020 斯坦福大学 Jure Leskovec组
论文链接:https://arxiv.org/abs/2002.05969
代码链接:http://snap.stanford.edu/query2box
关键词:知识图谱,知识推理,逻辑推理,注意力机制
推荐阅读Aminer的简要解读:ICLR 2020 | 知识图谱推理框架:基于向量空间的推理和数值逻辑推理
文章目录
1 摘要
本文解决的是回答大规模不完全的知识图谱(KG)上的复杂逻辑查询(EPFO query)。
现有方法的思路是将KG中的实体以及查询的query编码到一个向量空间中,能够回答这一query的实体在这一空间中和query的距离较近。
但是,先前的方法都将query建模成向量空间中的一个点(single point),这是有问题的,因为一个复杂的query可能代表着一个很大的答案实体集合,直接将这样的一个集合表示为空间中的一个点也许是不合理的。
而且,现有的方法只能处理合取关系和存在关系,处理带有析取关系的有逻辑的query仍是一个问题。
本文提出Query2Box,是一个基于嵌入(embedding-based)的框架,可用于推理任何使用操作符的query,并且可用于任意大规模的不完全的KG中。
作者的主要观点是:query可以被编码成box(例如hyper-rectangles),box内的一组点对应于query中的一组答案实体(answer entities)。
作者证明了合取可以天然地表示为boxes间的交集。同时还证明了一个负面的结果,即处理析取需要embedding的维度和KG实体数成比例。但是,通过将query转换为析取范式(Disjunctive Normal Form),Query2Box能够以可扩展的方式处理带有的任意逻辑查询。
作者在3个大规模的KG上进行了实验,展示了Query2Box的有效性,并实现了state-of-the-art。
2 引言
本文面对的任务是基于KG的问答推理。
(1)最直接的想法和其局限性
一阶的逻辑查询可以表示成图1 A所示的有向无环图(DAG),根据DAG进行推理得到一组答案,如图1 C所示。
这样的方法有一些缺点:(1)子图匹配的计算复杂度和query size成指数关系,这会影响到向大规模KG的扩展;(2)子图匹配非常敏感,因为它不能正确地回答缺少关系的查询。为了解决第二个问题,可以对KG中缺失的关系进行补全,但是这样会使得KG更加稠密,这就加剧了第一个问题。
(2)近期的基于表示学习的方法
将逻辑查询和KG中的实体编码到低维向量空间中,可以回答这一查询的实体和该查询在空间中的位置接近。这样的方法可以鲁棒地处理关系缺失问题,并且速度也快几个量级,因为回答任意的逻辑查询被简化为了识别在向量空间中最接近于query嵌入向量的实体。
但是这一方法有许多不足:
1)先前的工作将query编码成了向量空间中的一个单点。这是有问题的,因为回答一个逻辑查询需要建模KG中的一组实体,如图1 C所示,如何有效地将一个集合建模成一个单点还是有待研究的。
2)此外,在向量空间中定义两个点的逻辑操作符(例如 集合交集)也是不自然的。
3)只能处理conjuctive queries,是一阶逻辑中的子集,包含合取和存在,但不包括析取。在向量空间有效地处理析取逻辑还是一个有待解决的问题。
(3)作者提出
作者提出Query2Box模型用于处理基于KG的推理问题,并且可以解决任意的EPFO(Existential Positive First-order)逻辑查询(含有任意子集的查询),还有着可扩展性。
首先,为了准确地建模一组实体,作者的主要思想是使用一个关系紧密的范围(closed region)而不使用向量空间中的一个单点。我们使用box(axis-aligned hyper-rectangle)来表示一个query,如图1 D所示,这就带来了以下3个好处:
1)Boxes可以自然地对其封装的实体进行建模;
2)逻辑运算符(例如 集合交集)可以自然地在box上定义,就像维恩图一样;
3)在box上执行逻辑运算符就会产生新的box,这意味着操作符已关闭。
因此,根据图1 B, D所示的query计算图迭代地更新boxes,就可以有效地进行逻辑推理。
作者证明了Query2Box可以天然地处理conjunctive queries,还第一个证明了将EPFO query编码成单点是很难处理的,因为这需要embedding的维度和KG中实体数量成比例。
因此,作者提供了一个优雅(elegant这个词用得真好)的解决方法,将给定的EPFO逻辑查询转换成Disjunctive Normal Form(DNF)。给定任何的EPFO query,Query2Box将其表示成一组boxes,每个box对应DNF中的一个conjunctive query。然后,将最近邻的邻居实体作为查询的答案返回。也就是说,回答任何的EPFO query时,我们首先回答单个的conjunctive query,然后再将回答实体联合起来。
(4)实验证明
作者在3个KG benchmarks上使用Query2Box方法进行了实验,证明了:
1)Query2Box有很强的泛化能力,可以回答复杂的查询;
2)Query2Box可以泛化到训练中没有见过的新的逻辑查询结构;
3)当和query相关联的关系在KG中缺失时,Query2Box可以回单任意的EPFO query,并且有较高的准确率;
4)Query2Box在回答EPFO queries方面实现了state-of-the-art。
3 进一步的相关工作
和文本工作最相关的是处理KG上多跳推理的嵌入学习方法。主要的区别在于,本文提供的方法可以处理一阶逻辑的较大的一个子集(EPFO queries vs. conjunctive queries),而且本文的方法将query编码成box,实现了更高的准确率和泛化能力。
本文的方法和维恩图相关,box可以看成是向量空间中的维恩图。联合学习boxes和实体的嵌入,实现了在不完全的KG上进行推理。
4 Query2Box: Logical Reasoning Over KGs In Vector Space
作者提出Query2Box,定义一个目标函数以学习到KG中实体的嵌入,同时基于boxes学习到参数化的逻辑操作。给定任意的一个EPFO query (如图1 A所示),对其定义一个计算图(图1 B),然后在boxes上通过执行一组几何运算符(geometric operators)对query进行嵌入(图1 D)。最终封装到一个box中的实体就是query的答案(图1 D)。
为了训练模型,在训练阶段使用一组queries和它们的答案,然后学习到实体的嵌入以及几何操作符,以对queries进行正确的回答。
4.1 KGs and Conjunctive Queries
将KG定义为,代表实体集合,代表一个二元函数,表示一对实体间是否有关系(有向边)。
Conjunctive Queries是一阶逻辑查询的一个子集,使用到了操作符。形式化定义如下:
其中表示非变量的锚实体(non-variable anchor entity),是量化的边界变量(quantified bound variables),是目标变量。回答逻辑查询的目的是找到一组实体使 iff 。称是query 的符号集(例如 答案集)。
如图1 A所示,依赖图是conjunctive query 的图表示形式,其中节点对应于中变量或非变量的实体,边对应于中的关系。
为了使得query有效,相应的依赖图应该是有向无环图(DAG),锚实体是DAG的源节点,query目标是唯一的汇聚节点(unique sink node)。
根据query 的依赖图,我们可以得到计算图,其中包含了两种类型的有向边代表了在实体集合上的操作:
(1)Projection:给定实体集合和关系,这一操作得到,其中。
(2)Intersection:给定实体集合,这一操作得到。
给定一个query ,计算图将推理过程转变为得到答案的实体集合的过程,即从锚节点集合出发,递归地应用上面两个操作符,直到到达唯一的汇聚节点。
4.2 使用box embedding在实体集合上进行推理
到目前为止我们将conjunctive queries定义成了计算图,并且可以直接在KG的节点和边上执行。接下来我们定义在向量空间中的逻辑推理。给定一个复杂的query,需要将其分解成一个逻辑操作序列,然后在向量空间中执行这些操作。这样就获得了query的嵌入,针对此query的答案就是在封装在最终的query embedding box中的实体。
接下来详细介绍以下两个方法:(1)如何使用box embedding有效地建模并且在向量空间中的实体集合上进行推理;(2)如何处理析取操作符,从而扩大可以被建模到向量空间中的一阶逻辑集合。(4.3节)
Box embeddings
为了在向量空间中有效地建模实体集合,作者使用了boxes(例如axis-aligned hyper-rectangles)。如果集合中有某个实体,就可以很自然地将这个实体的嵌入建模成box内的一个点。在空间中的一个box定义如下:
其中;是元素级别的不等关系;是box的中心;是box的正偏移,建模了box的大小。
KG中的每个实体都分配了一个向量(例如 a zero-size box),box嵌入建模了(例如 向量在box内的实体的集合)。
接下来都用加粗的字母表示嵌入,例如的嵌入表示为。
在KG上进行推理是基于query的计算图的,如图1 D所示:从源节点(锚节点)初始的box嵌入出发,根据逻辑操作符序列对嵌入进行更新。接下来描述如何为源节点设置初始的box嵌入,以及如何建模projection和intersection操作符。之后将描述entity-to-box距离函数以及为了学习到嵌入和几何操作符(geometric operators)的整体目标函数。
(1)源节点的初始boxes
每个源节点都表示一个锚节点,可视为单个实体组成的集合。这样的single-element set可以天然地使用偏移量为0、中心为的box进行建模。我们将初始的box嵌入设为,其中是锚实体向量,是一个维的全0向量。
(2)几何投影操作符
将每个关系和关系嵌入关联起来。给定一个输入的box嵌入,使用建模投影(projection),对中心(centers)和偏移量(offsets)进行求和。
这就得到一个有转换后的中心和更大的偏移量的新的box,如图2 A所示。有适应能力的box size有效地建模了集合中不同数量的实体/向量。
(3)几何交集操作符
对box的中心使用注意力机制,并使用sigmoid函数缩小box的偏移量,将box embeddings集合 的交集建模成:
其中表示dimension-wise乘积;是多层感知机;表示sigmoid函数;表示排列不变的(permutation-invariant)深层架构;都是在dimension-wise进行操作。
根据前人的工作,作者使用建模所有的deep sets,其中所有的两个MLPs间的隐层维度都和输入维度相同。
几何交集背后的想法是生成一个位于一组boxes内的更小的box,如图2 B所示。和一般的建模交集的deep sets不同,我们的几何交集操作有效地限制了中心的位置并且建模了shrinking set size。
(4)Entity-to-box distance
给定一个query box 和实体向量,将它们间的距离定义如下:
其中,。
如图2 C所示,对应于实体和其在box内最接近的边/角的距离;对应于box的中心和它的边/角的距离(如果实体在box内则为实体自身)。
这里的关键在于使用减小box内部距离的权重,这就意味着只要实体向量在box内部,则认为该实体距离query的中心足够近(例如,使用进行缩放)。当时,变成原始的距离,例如
(5)训练目标
接下来的目标是学习到实体嵌入以及几何映射和交集操作符。
给定训练使用的query集合以及它们的答案,优化一个负采样损失以有效地优化本文的基于距离的模型:
其中表示margin;是正实体(query 的答案);是第个负实体(不是query 的答案);是负实体的数目。
4.3 使用disjuctive normal form处理disjunction
目前为止我们聚焦于conjuntive queries,我们这里的目标是在向量空间中处理更广泛的逻辑查询,称为EPFO(Existential Positive First-order)查询,包括。我们特别地关注于计算图为DAG的EPFO queries,和第4.1节中的conjunctive queries相同,只是我们现在有了一种额外类型的有向边,称为,定义如下:
一个最直接的想法就是为union定义一个几何操作符,就像前面的操作一样。但是对于box embedding有一个挑战:boxes可以位于向量空间中的任意位置,它们的union可以不再是一个简单的box。
作者在理论上证明了一个普遍的负面结果,适用于任何的将query 嵌入到并使用距离函数来检索实体的embedding-based方法(例如 当且仅当)。这里的是实体嵌入和query嵌入间的距离,例如或。
定理 1:
证明见附录A,关键是随着union操作的引入,denotation sets的任何子集都可以作为答案,这强迫我们在向量空间中建模powerset 。
对于真实世界中的KG,有个conjunctive queries,它们的答案不重叠。例如,在从Freebase中获取的常用数据集FB15k中,我们找到,。
细节见附录 B
定理 1证明了为了使用现有的框架准确地建模任意的EPFO query,使用VC维度衡量的距离函数的复杂度需要和KG中实体的数量一样大。这就表示着,如果我们使用普通的基于超平面(hyper-plane)、欧几里得球体(Euclidean sphere)或者axis-aligned rectangle的距离函数,它们的参数维度需要是,对于我们感兴趣的真实的KG来说就是。
换句话说,逻辑查询的嵌入维度需要是,维度太大了,不利于扩展到大规模的KG,并且无法推广到未见过的KG边。
为了解决这一问题,作者的主要思想是:将给定的EPFO query转换成Disjunctive Normal Form(DNF),因此union操作仅在最后一步出现。每个conjunctive query都能在低维空间进行推理,之后使用简单的过程对结果进行聚合。
接下来将描述向DNF的转换,以及聚合的过程。
(1)向DNF的转换
任意的一阶逻辑可以被转换成等价的DNF。我们直接在计算图的空间进行转换,例如 将所有类型为“union”的边移动到计算图的最后一步。
令表示给定EPFO query 的计算图,表示入边的类型为“union”的节点集合。对于每个,定义为其父节点的集合。
我们首先生成个不同的计算图(步骤如下所示)每个在第一步都有不同的选择:
1)对于每个,选择一个父节点;
2)去除所有的类型为“union”的边;
3)合并和,同时保留其他的所有的边。
然后组合获得的计算图,以得到最终的等价的计算图:
1)将所有得到的计算图的目标汇聚节点转换成量化边界的变量节点(the existentially quantified bound variables nodes);
2)创建一个新的目标汇聚节点,将类型为“union”的有向边从上述所有的变量节点绘制到新的目标节点。
整个转换过程如图3所示:
通过union操作的定义,我们给出了与原始计算图等价的计算图。由于所有的union操作符从中移除了,所有的这些计算图表示的conjunctive queries定义成。接着使用现有的框架得到这些conjunctive queries的嵌入集合。
(2)聚合
接下来定义给定的EPFO query 和实体间的距离函数。
由于在逻辑上等价于,我们可以使用box距离定义聚合的距离函数:
其中是使用EPFO query 进行参数化的。当是一个conjunctive query时,例如 。对于,取到最近的box的最小距离作为到实体的距离。该模型和union操作一致,只要实体在一个集合中,该实体就在集合的并集中。
注意,我们的DNF-query重写模式是通用的,能够扩展到任何适用于conjunctive queries的方法以处理更一般的EPFO queries。
(3)计算复杂度
使用本文的框架回答EPFO queries的计算复杂度和回答个conjunctive queries的相等。所有的个计算可以并行进行。回答每个conjunctive query的速度很快,因为它要求我们执行一个简单的box操作序列,然后在嵌入空间中执行一系列搜索,搜索可以基于局部敏感哈希(LSH)技术在固定时间内完成。
5 实验
实验部分的目的是评估Query2Box在发现复杂逻辑查询的答案时的性能,并且这些问题是不能通过遍历不完全的KG来获得的。这就意味着,我们重点回答KG中需要成功预测出一个或多个缺失边的query。
1、数据集
FB15k、FB15k-237、NELL995
考虑9种不同的query结构,如图4所示。使用5种query结构用于训练,在9种query结构上进行评估。
表1显示了不同的query结构答案实体的平均数。可以看出复杂的逻辑查询(例如 2p, 3p, ip, pi, up)缺失需要建模更多的答案实体。
2、评估方法
给定一个测试query ,使用式(3)中的对$v \in \mathcal{V} $ \ 进行排序,定义为,然后使用如下的度量进行评估:
对于MRR(Mean Reciprocal Rank),;对于[email protected](Hits at K),。
然后基于式(6)对所有的有相同query结构的queries取平均,分别得到针对不同query结构的评估结果。
3、对比方法
(1)baselines
- GQE:state-of-the-art,将query编码成一个向量,将projection和intersection操作符分别建模成translation和deep sets。使用距离衡量query和实体向量间的距离。
- GQE-DOUBLE:在GQE的基础上使用双倍的嵌入维度,使得Query2Box和GQE-DOUBLE的参数量一样。
尽管原始的GQE不能处理EPFO queries,我们使用了本文提出的DNF-query重写策略使得GQE也可以处理EPFO queries。
(2)Query2Box的变形
- Q2B:使用box嵌入建模queries,并且使用注意力机制用于intersection操作;
- Q2B-AVG:使用平均操作替换intersection中的注意力机制;
- Q2B-DEEPSETS:使用deep sets替换intersection中的注意力机制;
- Q2B-AVG-1P:Q2B-AVG的变形,仅仅使用1p queries训练,因此逻辑运算符没有经过显示的训练;
- Q2B-SHAREDOFFSET:box的偏移量在所有的queries间共享(每个query都表示成了相同大小的box)。
4、实验结果
和baseline进行对比的实验结果:
消融实验的实验结果:
6 总结
本文提出了一个推理框架Query2Box,可以有效地建模实体集合,并基于其进行推理,同时还可以处理EPFO queries。
给定一个逻辑查询,首先将其转换成DNF,将每个conjunctive query嵌入到一个box中,并输出最接近boxes的实体。
本文的方法可以处理所有类型的EPFO queries,并且具有较好的可扩展性和准确率。
在KG上进行了实验,证明了Query2Box在回答多样的逻辑查询方面,显著优于现有的方法。
本文的思路非常新颖,作者将query建模成了一个box,而不是向量空间中的a single point。
这篇文章大致领会了思想,具体细节没有太读懂,日后有需要再仔细阅读文章及附录。