论文:Query2Box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings
ICLR 2020的一篇论文,和论文Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs是相关的文章,有完整代码
作者:Hongyu Ren, Weihua Hu, Jure Leskovec
pdf:https://arxiv.org/abs/2002.05969
github:https://github.com/snap-stanford/KGReasoning(包含三种模型,BetaE
,Query2box
,GQE
)
0. Abstract
本文是BetaE
的前身,仅提供了EPFO
查询,没有提供否定
查询。本文提出的Query2Box
框架,比[上一篇文章]()增加了析取(也就是或)查询
Query2Box
框架,将查询嵌入为框(即超矩形),框内的实体为答案实体。在此设定下,连接就是框的交叉部分。但经过证明发现,框嵌入需要与实体数量成正比的维度才能进行有效表示。本文将给定的EPFO查询
转换为析取正常形式 Disjunctive Normal Form,DNF
,最后解决了这一问题
在三个大型知识图谱数据集上,实现了25%的提升,取得了SOTA
1. Introduction
本文认为,过去工作将查询嵌入到向量空间中的单点,这样无法很好地实现活动实体建模(如图一C),也无法较好地在向量空间中定义两点的逻辑运算符
本文的Query2Box
框架使用一个框表示查询,好处如下:
- 框自然对所包围的实体建模
- 逻辑运算符可以自然地在框中定义,类似维恩图的框
- 对框进行一阶逻辑运算会产生新的框,说明是闭运算。迭代进行运算更新框,可以进行逻辑推理(如图一B、D)
框嵌入需要与实体数量成正比的维度进行表示。为解决这一问题,本文将给定的EPFO查询
转换为析取正常形式 Disjunctive Normal Form,DNF
,即连接查询的分离,也就是,先处理单个框嵌入问题,最后取答案实体的连接。
最后的实验证明:
Query2Box
泛化能力很强,可以回答复杂查询Query2Box
可以泛化出训练期间未出现的逻辑查询结构(也就是能正常运算)Query2Box
能隐式填补缺失关系Query2Box
比此前的SOTA提高25%的效果
- 图一:
Query2Box
框架过程图。图一构建一阶逻辑查询DAG图
;图二构建计算图;图三在知识图谱空间遍历知识图谱,活动实体建模;图四在向量空间嵌入查询,获取答案实体
2. Further Related Work
- 知识图谱多跳推理的嵌入方法:本文与此前工作的区别是,本文实现了更丰富的一阶逻辑推理,同时将查询嵌入为框,实现了更好的效果
- 结构化嵌入方法:本文与此前工作的区别是,本文的框嵌入与实体嵌入是共同学习的,从而允许推理不完整的知识图谱
3. Query2Box: Logical Reasoning Over KGs in Vector Space
3.1 知识图谱和连接查询
3.2 框嵌入的实体推理
如图1所示,推理过程是,给定一个复杂查询,将其分解为一系列逻辑运算,然后在向量空间中执行这些运算,获得查询嵌入,查询答案是最终嵌入框中的实体
框嵌入(Box Embedding
)
框嵌入有点类似张量运算,视每个实体嵌入为一个0维框,而框嵌入是一个p
维框
源节点的初始框
每个源节点视为一个锚定节点,是只含1个元素的、大小和偏移量都为0的框,框嵌入表示为:(v, 0),v是锚定实体向量,0是0维。
几何投影算子
令关系嵌入为(Cen(r), Off(r))。对于给定框嵌入p,投影算子被定义为:
几何连接算子
连接算子采用了注意力机制,计算公式:
- 公式:
o
是维度乘积,σ
是激活函数,DeepSets
是排列不变的深度架构
实体与框的距离
给定实体嵌入和查询框,计算距离公式:
- (3):计算实体嵌入与查询框的距离,包括外部距离和内部距离。可以看到,在框内则外部距离为0,内部距离为1。当
α = 1
时,公式(3)退化成一阶范数距离
训练目标
3.3 采用析取正常形式的析取算子
定义了一种叫联合 union
的新算子,用于最后合并连接查询答案
定理一证明了,为了用现有框架对EPFO
查询进行准确建模,VC维测量的距离函数的复杂度要和知识图谱的数量一样大。这意味着用超平面、欧几里得球体或轴对齐矩形表示与计算距离函数,维度要和实体维度成正比
为了解决这个问题,关键思想是,将给定EPFO
查询转换为析取正常形式 Disjunctive Normal Form, DNF
,这样就可以只在最后一步执行union
算子
通过将查询转换为DNF
形式,就可以在低维空间中对每个子查询进行推理,最后再通过union
算子进行答案聚合
- 总的来说,就是用
DNF
表示拆开一阶逻辑查询,分开运算,再用union
把答案合起来。这个过程可以递归执行
转换为DNF
任何一阶逻辑查询都可以转换为等效的DNF
。步骤如下:
- 取所有
union
算子的一端,作为父节点
- 把所有
union
算子删除,保留父节点 - 拆开各个计算图的目标
下沉节点 sink node
,也就是汇聚计算结果的节点,各个计算图进行联合计算 - 生成新的下沉节点,各个计算图结果取
union
,结果汇聚到下沉节点
聚合
定义了EPFO
查询中,查询q
和实体v
之间的距离函数。由于q
可以拆分为q1..qn
取union
,因此距离表示可以采用框距离的形式
- (5):
EPFO
中查询嵌入和实体嵌入的距离函数,采用了框距离的形式
计算复杂性
EPFO
的计算复杂性与计算拆开的N
个连接查询
复杂性相同。同时,可以采用并发运算加速
回答每个连接查询速度也很快,可以通过在嵌入空间中进行范围搜索,或使用基于局部敏感哈希 Locality Sensitive Hashing
的方法,实现查询
4. Experiments
4.1 知识图谱和查询生成
- 数据集:FB15k、FB15k-237、NELL995
- 表1:9种查询结构类型,其中,选择5种用于训练,9种用于测试
- 构建缺失关系知识图谱用于实验
4.2 评价方案
平均倒数排序 Mean Reciprocal Rank, MRR
Hits at K, H@K
4.3 基线和模型变形
- GQE
- GQE-DOUBLE
- Q2B(实验模型)
- Q2B-AVG:连接算子的注意力机制改为求平均值
- Q2B-DEEPSETS:连接算子的注意力机制改为DEEPSETS
- Q2B-AVG-1P:仅用
查询结构1p
进行训练 - Q2B-SHAREDOFFSET:所有查询结构共享一样大的查询框
4.4 结果
与GQE的试验,显示了模型的改善
消融实验,结果证明了:
- 注意力机制的重要性:
Q2B
优于Q2B-AVG
和Q2B-DEEPSETS
- 复杂查询训练的重要性:
Q2B-AVG
优于Q2B-AVG-1p
- 查询框大小应该自适应调整:
Q2B
优于Q2B-SHAREDOFFSET
5. Conclusion
本文提出了Query2Box
框架,可以有效对实体进行建模和推理,并处理向量空间中的EPFO
查询。给定一个逻辑查询,先转化为DNF
,将每个连接查询嵌入到一个框中,并输出距离最近的框内实体。Query2Box
框架可以处理所有的EPFO
查询。
Comments | NOTHING