网络知识 娱乐 ICML 2022 | HousE: 基于Householder变换的知识图谱表示学习

ICML 2022 | HousE: 基于Householder变换的知识图谱表示学习

编者按:知识图谱(Knowledge Graph,KG)蕴含着丰富的人类知识信息,近年来在人工智能领域发挥着越来越重要的作用,已被广泛地应用于多个领域。然而,知识图谱难以避免地存在不完整的问题,这在很大程度上限制了相关应用的性能表现。作为一种有效缓解此问题的方法,知识图谱表示学习(Knowledge Graph EmbeAdding,KGE)近年来受到了学术界的关注与研究。在 ICML 2022 被接收的论文中,微软亚洲研究院与大连理工大学合作的最新研究工作《HousE: Knowledge Graph Embedding with Householder Parameterization》提出了一种具有强大且全面建模能力的KGE模型,名为HousE。


论文作者:李锐(大连理工大学),赵健安(凯斯西储大学),李朝卓(MSRA)、贺笛(MSRA)、孙浩(微软Bing)、谢幸(MSRA)、申彦明(大连理工大学)等


论文链接:https://arxiv.org/pdf/2202.07919.pdf

代码链接:https://github.com/rui9812/HousE


什么是KGE


KGE模型旨在学习KG中实体和关系的表示,并定义一个评分函数来衡量三元组的合理性,用于预测缺失的链接。这些模型的性能表现很大程度取决于对KG中关系模式(relation pattern)和关系映射属性(relation mapping property)的建模能力。


知识图谱中重要的关系模式有:(1)对称,如is_friend_of就是一种对称关系;(2)非对称,如is_father_of就是一种非对称关系;(3)互逆,如is_teacher_of和is_student_of就是一对互逆的关系;(4)组合,如is_grandmother_of就是is_father_of和is_mother_of的组合关系。而关系的映射属性则有一对一关系、一对多关系、多对一关系和多对多关系。图1展示了四种重要的关系模式和两种复杂的关系映射属性。


图1 四种重要关系模式和两种复杂映射属性


Motivation


本研究对现有代表性KGE方法的建模能力进行总结(表1),并进一步分析了其存在的局限性:(1)现有工作已经证明将关系视为实体间的旋转变换是一种可以建模多种关系模式的有效方法,然而由表1中的最后一列可以看出,现有方法中的关系旋转固定于低维空间(2、3、4维),这很大程度地限制了模型的建模能力;(2)由表1中的2-6列可以看出,现有方法无法全面地建模知识图谱中的重要关系模式与复杂映射属性。


表1 现有代表性KGE模型对重要关系模式和复杂映射属性的建模能力


以上问题促使研究员们思考:如何设计一个具有更强大、更全面建模能力的KGE模型?这其实引发了两个子问题:


(1)如何强大:现有模型的建模能力受限于低维空间的关系旋转,那么获得强大建模能力的关键则在于如何自由地扩展关系的旋转维度


(2)如何全面:已有工作希望通过设计关系投影变换来建模复杂映射属性,但将这些不可逆的关系投影与旋转变换结合会导致模型失去建模逆关系和组合关系的能力,因此获得全面建模能力的关键则在于如何设计可逆的关系投影变换来与旋转结合。


Householder框架


为解决以上两个问题,本研究引入Householder反射变换作为基本数学工具,并基于此进一步设计了两种线性变换作为KG中的关系表示:


(1) 由多个Householder反射组合而成的Householder旋转,实现了强大的建模能力;

(2) 由原始Householder反射修改而来的Householder投影,实现了全面的建模能力。


在此Householder框架下,本研究得以提出了一个更强大、更全面的KGE模型,名为HousE。如表1所示,HousE能够自然地将旋转扩展到任意的K维,并且可以全面地建模表1中所有关系模式与映射属性。与此同时,不难看出HousE是现有基于旋转的KGE模型的推广。


Householder反射

图2 二维空间中的Householder反射


Householder矩阵常用于数值代数(如正交分解等),用于描述关于一个(过原点)超平面的基本反射变换。给定一个单位向量u∈R^k,k×k的Householder矩阵H由变量U生成,定义为:


其中I为k×k的单位矩阵。从几何上来看,如图2所示,Householder矩阵能够对向量X做关于以U为单位法向量的超平面的镜面反射,即Householder反射变换:



其中⟨⋅⟩表示内积运算。需要注意的是,该变换中的矩阵和向量间乘法可以直接转化为向量间操作,这为本研究在效率上的可行性提供了保障。


Householder旋转


基于Householder矩阵,本研究定义一个映射来表示旋转。给定2n个单位向量{u_c }_(c=1)^2n,其中u_c∈R^k,n为正整数,定义如下映射:


针对此映射,本研究从理论上证明了当n=⌊k/2⌋时,任意k×k的旋转矩阵都可以通过映射Rot-H计算得到。这意味着任意的k维旋转都可以表示为2⌊k/2⌋个Householder反射的组合,比如任意二维空间中的旋转都可以分解为两个基本反射。本研究将这种由2⌊k/2⌋个Householder反射组合而成的旋转称为Householder旋转,进而以此方式自然地将知识图谱中的关系表示为K维空间中的旋转变换,从而获得更为强大的建模能力。


Householder投影


旋转变换被证明能够有效建模表1中的四种关系模式,然而,由于其严格的保距性质,单纯的关系旋转无法有效地处理知识图谱中复杂的关系映射属性(一对多、多对一和多对多)。本研究注意到前人的方法(TransH、TransR等)希望引入关系投影变换来建模映射属性,然而这些模型中的投影变换均是不可逆的,这会导致模型失去对逆关系和组合关系的建模能力。为了解决这一问题,本研究通过对原始的Householder矩阵进行修改,提出了一种新的可逆投影,称为Householder投影。


更具体地说,给定一个单位向量p∈R^k和一个实数标量τ,对原始Householder矩阵的定义稍作修改,得到k×k的矩阵M,M由变量P和τ生成,定义为:



数学上可以算出,M(p,τ)有(k-1)个特征值为1,1个特征值为(1-τ),因此当τ≠1时,M(p,τ)总是可逆的。从几何上来看,M(p,τ)能够对向量X做沿着P轴的基本投影变换:


其中标量τ决定了投影后x ̂的位置,该变换中的矩阵和向量间乘法也可以直接转化为向量间乘法。图3展示了二维空间中,不同τ值下投影后x ̂的不同位置。


图3 二维空间中M(p,τ)在不同τ值下对应的投影变换


基于以上的基本投影矩阵M,本研究定义一个映射来表示投影。给定一组标量T={τ_c }_(c=1)^m和单位向量P={p_c }_(c=1)^m,其中p_c∈R^k,m为正整数,定义如下映射:



由于可逆矩阵的乘积仍然是可逆矩阵,因此上述映射的输出也是一个可逆矩阵,对应的投影变换同样是可逆的。本研究将这种由m个修改后的Householder反射组合而成的可逆投影称为Householder投影。不同于前文中严格保距的关系旋转变换,Householder关系投影可以在保证可逆性的同时改变实体之间的相对距离,故能够在不损失对关系模式建模能力的同时有效地处理复杂的关系映射属性(一对多、多对一和多对多)。


HousE

图4 HousE图示


结合所设计的Householder旋转与Householder投影,本研究将这两种变换纳入一个统一的框架,提出了一种全新的KGE模型,称为HousE。如图4所示,对于给定三元组(h,r,t),S_h,S_t∈R^(d×k) 分别的头实体h和尾实体t表示,其中d为实体嵌入表示大小,k为行向量维度,即S_h [i],S_t [i]∈R^k,i∈{1,…,d}。。HousE首先通过Householder投影得到关系r特定的头尾实体表示S_(h,r)和S_(t,r),然后对投影后的头实体表示S_(h,r)进行Householder旋转,希望旋转后的结果与S_(t,r)尽可能相近。也就是说,HousE将关系r建模为实体间行级的两阶段变换:


关系投影阶段:HousE首先利用Householder关系投影将实体h和t表示映射为关系r特定的表示S_(h,r)和S_(t,r)。详细来说,HousE为关系r定义参数P_(r,1),P_(r,2)∈R^(d×m×k)和T_(r,1),T_(r,2)∈R^(d×m),利用Pro-H映射对头尾实体的行级表示进行投影:



关系旋转阶段:在完成对头尾实体的投影变换后,HousE在投影后的头实体表示S_(h,r)和尾实体表示S_(t,r)之间建模Householder关系旋转变换。详细来说,HousE为关系r定义参数U_r∈R^(d×2⌊k/2⌋×k),利用Rot-H映射对投影后的头实体表示S_(h,r)做行级的Householder关系旋转,希望旋转后的表示与投影后的尾实体表示S_(h,r)尽可能相近:



这意味着HousE的评分函数为:



在以上投影和旋转的变换过程中,所有的矩阵和向量间乘法都可以替换为向量间乘法,以保证高效的计算。得益于投影的可逆性和旋转的可扩展性,HousE能够全面有效地建模表1中所有的关系模式和映射属性,并且可以视为现有旋转模型的推广。


实验分析


主实验


在实验阶段,该研究在五个公开知识图谱基准数据集上验证所提方法的有效性,分别为WN18、FB15k、WN18RR、FB15k-237和YAGO3-10。HousE在这五个数据集的知识图谱补全任务上的实验结果如表2和表3所示,其中HousE-r为仅使用Householder关系旋转(无Householder关系投影)的基础模型。为了保证比较的公平性,本研究限制了HousE和HousE-r的参数量,使得总参数量与基线模型相近,甚至是远少于基线方法。


表2 在WN18和FB15k数据集上的实验结果

表3 在WN18和FB15k数据集上的实体预测结果


从实验结果可以观察到,相对于现有的KGE模型,HousE-r和HousE在限制了模型参数的情况下仍然表现出了更加优越的性能,这证明了本研究所设计的Householder框架的有效性。HousE-r相对于的基准模型的性能提升来源于Householder旋转带来的强大建模能力。值得注意的是,HousE-r超越了几乎所有的基准模型,唯一的例外是在FB15k-237数据集上与Rotate3D的性能表现是相近的,然而HousE-r使用了远少于Rotate3D的参数(后者的参数量约为HousE-r的3.67倍),这也反映了Householder关系旋转的有效性。进一步来说,HousE在所有指标上都一致超越了HousE-r,这得益于HousE中的Householder关系投影所带来的对复杂关系映射属性的建模能力。


细粒度性能分析



表4 WN18RR数据集中各个关系下的性能对比


为了从细粒度角度进一步验证模型性能,本研究展示了模型在各个关系下的性能表现,如表4所示。可以观察到,相对于现有的两种代表性旋转模型RotatE和QuatE,HousE-r在所有关系下都表现出更好的性能,验证了Householder旋转优越的建模能力。通过结合Householder投影,HousE进一步取得了更好的性能,尤其是在一对多和多对一关系上的性能提升更为显著,比如在一对多关系member_of_domain_region和多对一关系instance_hypernym上,HousE相对于RotatE分别有62.55%和21.55%的显著提升,这得益于HousE对复杂映射属性的有效建模。


对复杂映射属性的建模能力分析


表5 FB15k-237数据集中在不同映射属性下的性能对比


为了进一步验证HousE对关系映射属性的有效建模,本研究对比了HousE和RotatE在不同关系映射属性下的性能,如表5所示。可以观察到,HousE在所有映射属性下的性能一致优于RotatE,特别是在复杂的一对多关系(预测尾实体)、多对一关系(预测头实体)和多对多关系下,HousE相对于RotatE的性能提升更加显著。HousE的这种优越性能得益于Householder投影对关系映射属性的有效建模。


旋转维度的影响分析


图5 WN18RR和FB15k-237数据集中旋转维度对性能的影响


为了验证高维旋转的有效性,本研究在WN18RR和FB15k-237数据集上探究旋转维度对性能的影响,结果如图5所示。可以观察到,正如所期望的那样,在这两个数据集中,更高维旋转变换下的HousE和HousE-r相比于其在低维旋转下时都取得了更优越的性能,因为高维旋转能够带来更为强大的建模能力。与此同时,在所有旋转维度下,HousE都一致且显著地超越了HousE-r,证明了HousE中Householder关系投影的有效性。例如,在4维旋转变换下的HousE就已经优于12维旋转变换下的HousE-r了。 模型变体与潜力


表6 不同模型变体的性能


为了验证所提出Householder投影的有效性,本研究设计了HousE的两个变体模型HousH和HousR,分别是将HousE中的Householder投影替换为了TransH和TransR中的不可逆投影。从表6可以观察到,相比于没有投影变换的基础模型HousE-r,HousH和HousR在FB15k-237数据集上的性能仅有略微提升,在WN18RR数据集上的性能甚至会更差一些,这反映了不可逆的投影变换可能会损害模型的建模能力。进一步来说,HousE在两个数据集上都显著地优于HousH和HousR,证明了Householder可逆投影的优越性。


为了进一步探究模型的潜力,本研究也尝试向HousE和HousE-r中引入了关系平移变换,分别得到HousE+和HousE-r+。从表6中可以看出,这两种变体在两个数据集上的性能都要优于它们的原始版本,这是因为平移变换能够反映KG的层次属性,因而也可以一定程度地增强HousE和HousE-r的表达能力。