论文浅尝 | 知识图谱中的链接预测:一种基于层次约束的方法

2019 年 7 月 24 日 开放知识图谱
论文浅尝 | 知识图谱中的链接预测:一种基于层次约束的方法

论文笔记整理:张良,东南大学博士生,研究方向为知识图谱,自然语言处理。


https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8450054

 

本文主要关注KG上的 Link prediction 问题,以往的方法在处理KG的时候只利用了 KG 里最一般的结构,例如将关系向量r作为头实体向量h和尾实体向量t之间的一个翻译,这种结构在KG中是最直接最普遍的。然而还有许多其它特殊的 KG Structure 可以被利用从而提升链接预测等任务的效果。一个典型的结构就是知识图谱中的层次结构(hierarchical structure),这种结构包含了丰富的推理模式,可进一步提高链接预测的效果。在文本中,作者提出了一种基于翻译模型的层次约束链接预测方法,称为hTransM。它可以通过检测单步或多步的层次结构来适应性地决定最优间隔。


背景

在一个知识图谱中,节点表示实体,边表示节点之间的关系。知识图谱上的链接预测目的是为了能够预测出一个三元组(hrt)缺失的头实体h,尾实体t或者关系r。为了处理这一问题,已经出现了许多相关方法,大致可以分为两类。第一类是基于规则和路径的方法,也就是关系通过比较明确的规则和关系路径的学习预测得来。第二类就是基于知识图谱嵌入的方法,实体之间的关系通过嵌入向量被隐式地预测出来。这些方法中比较有代表性的有基于翻译模型的TransETransA,还有利用图谱结构的PTransE等。


动机

虽然已经出现了一些利用图谱自身结构的模型,如PTransE,但仍有许多图谱自身的特殊结构没有被有效利用,一个典型的结构就是知识图谱中的层次结构(hierarchical structure)。在这种结构中,实体组织成树状结构,它们的关系也为层次关系。这种层次结构类似关系路径,能够提供丰富的模式,从而提高链接预测效果。这种层次结构其实在知识图谱中普遍存在,例如数据集WN18,有将近50%的层次关系。这种层次结构会导致实体的嵌入向量呈一个比较特殊的分布,相比于没有层次结构的方法多了一些限制,从而可以提升链接预测等任务的效果。基于以上动机,作者提出了hTransM,一种基于层次约束的链接预测方法。文中的主要贡献有如下四点:

1)本文将层次结构分为两类,一类是单步层次结构(single-step hierarchical structures),另一类是多步层次结构(multi-step hierarchical structures)。另外,文中还提供了一种通过利用层次关系的属性来检测层次结构的方法。

2)提出了一种基于层次约束的链接预测方法(hTransM),该方法在知识图谱嵌入的方法上实现。

3)通过对提供模型的均匀稳定性以及误差的上界的证明,进一步证明了了hTransM方法的收敛性。

4)通过实体预测以及关系预测等实验证明了该方法的有效性。

主要方法

首先需要对一些概念进行定义,

层次结构(Hierarchical Structure):一个层次结构是通过一个关系将若干实体组合成层级的形式。不同的层级在垂直方向上区分出来,对于某一个层级,相对于其它层级的位置有上位,下位以及相同层级等关系。例如通过关系“孩子”(child)组成的层级结构,不同的层次表示不同代的人。

一个层次结构(Ahierarchical structure):通过关系 r* 构成,定义为,其子图是一个有向无环图。其中l是节点到层次索引的映射。

1

在上图中,实体 Barack Obama SrBarack Obama 以及 Malia Sasha 通过关系 child 组成了一个三级层次结构。

层次关系(hierarchical relation):层次关系r用来使各层的实体属于同一层次。

关系路径(relation path):一条关系路径是由某个头实体出发到达某个尾实体之间所经过的所有关系组合而成。

2

上图为从图1中抽取出的多种关系路径。

层次关系路径(hierarchical relation path):一个层次关系路径是一种多步关系路径,可以定义为。也就是说至少有一种关系出现在不同的层次中。

有两种推理类型的层次结构可以被用到链接预测任务中,分别是单步层次结构和多步层次结构。

单步层次结构(Single-stephierarchical structure):一个单步层次结构是一个层次结构的子图,可以定义为 ,单步层次结构中的实体分布在两个不同的层次上,并通过单步关系(single-steprelation)进行链接,其尾实体有着共同的父节点。图3a)表示一个单步层次结构。

多步层次结构(Multi-step hierarchicalstructure):与单步层次结构对应,多步层次结构中的实体分布在不同的层次上,通过关系路径链接,这些路径有着相同的头实体和尾实体,可以定义为 ,图3b)表示一个单步层次结构。

3

 

和一般的关系相比较,通过层次关系组合在一起的实体在其嵌入空间中的分布会有着比较明显的区分,这种限制可以很好地被用到链接预测任务中。首先,在单步层次结构中,兄弟节点所对应的实体所对应的向量会在向量空间中比较相近,因为它们有共同的父节点,语义相似。在传统的学习方法中,大多只对头实体和尾实体进行约束,使它们尽可能靠近,而忽略了兄弟尾实体之间的语义相似。而这些相似性可以很好地作为推理信息被用到链接预测中。另外,这种层次结构已经大量地出现在知识图谱中,例如FB15KWN18K,都有将近50%的层次关系。

虽然知识图谱中已有许多层次结构,但还需要将其抽取出来。

层次结构的发现(Hierarchical Structure Discovery):以往的文献表明,DAG(有向无环图)有着独特的层次结构,从而可以利用许多算法进行发掘。由于许多DAG的子图并非具有层次结构,所以问题的关键在于检测其子图是否进一步具有层次结构,进而将问题聚焦到层次关系的发现(discoveryof hierarchical relations)。层次关系由于层次结构的原因是不能形成环状的,所以文中采用拓扑排序算法(topological sorting algorithm)来检测环状结构:

除了不能形成环状,层次关系也应该是不自反的(irreflexive),例如BarackObama Sasha 之间的关系child。另外,层次关系与不平衡映射性质密切相关(一对一,一对多等映射)。

 

预测方法hTransM的提出:有文献表明,适当值(appropriate value)对于链接预测的提升非常重要。所以hTransM通过检测知识图谱中的层次结构和一般结构定义了一个层次约束的margin ,其中 被用来区分正确三元组和错误三元组。实体和关系的嵌入过程通过最小化带有的损失函数实现:

这里的评分函数采用TransE里的形式。

由于层次结构是通过单步层次结构和多步层次结构组成的,所以也会有两方面组成。这里很自然地用线性组合的方式将两部分进行组合:

其中α,β都是参数,用来发现单步结构所对应的最佳间隔, 则用来发现多步结构所对应的最佳间隔。

单步特定间隔Single-step Specific Margin):单步特定间隔是由对应的单步特定结构而产生的。对于一个给定的实体h和对应的关系r,正确实体的集合 Pr 由表示,集合中包含的实体都与h有关系r。错误实体的集合由 Nr 表示,集合中的实体与h有其它关系 r'。假如单步结构(single-step structure)具有层次性,那么正确实体就会分布地比较紧凑,即图4中的扇形区域。

4

在这种情况下,把一个正例和一个负例区分开来不仅需要考虑与实体h的虽短距离d,还需要考虑与扇形区域的相近程度。对于一个给定的三元组(hrt),可以表示为: 。其中 为 Pr 和 Nr 之间的间隔, 通过来 给出。

多步特定间隔Multi-step Specific Margin):与单步特定间隔类似,多步特定间隔可以表示为。参数 给出。m_p 定义了 Pp 和 Np 之间的间隔。Pp 包含了正确的关系,Np 包含了错误的关系。其中 m_p 可以由图5进行表示。

5

5中的环状代表正确关系,周围的长方体代表错误的关系。

 

论文还对hTransM方法的收敛性进行了证明。

 

实验结果

实验在FB15KWN18K以及FAMILY三个数据集上进行。FAMILY是一个人工构建的包含五个家庭总共六代人的层次知识图谱。三个数据集所包含的数据分布如下:

实体预测实验结果:

关系预测实验结果:

实验结果表明 hTransM 在链接预测任务上的效果相比其它传统方法有一定的提升。

总结与展望

本文比较细致地从 KG embedding 模型损失函数中的间隔入手,充分考虑层次结构信息,对损失函数中的间隔项进行优化,并在此基础上提出了比较有效的链接预测方法。以往的 KG Embedding 方法在一定程度上忽视了知识图谱本身的结构化信息,最近一段时间相继出现了一些加入KG结构信息的论文,比如加路径,加节点的邻居信息,加三元组等等,但知识图谱中所包含的结构可能远不止于此,实现Link prediction的方法也不是必须要通过 KG embedding,在网络科学里(复杂网络)也有许多关于Link prediction的研究,大多都是从图论的角度,充分利用图谱自身结构(当然很少考虑语义),本文也是一种初步尝试,所以结合网络学科里的一些方法,可能会找到新的研究途径。

 



OpenKG


开放知识图谱(简称 OpenKG)旨在促进中文知识图谱数据的开放与互联,促进知识图谱和语义技术的普及和广泛应用。

点击阅读原文,进入 OpenKG 博客。

登录查看更多
15

相关内容

知识图谱(Knowledge Graph),在图书情报界称为知识域可视化或知识领域映射地图,是显示知识发展进程与结构关系的一系列各种不同的图形,用可视化技术描述知识资源及其载体,挖掘、分析、构建、绘制和显示知识及它们之间的相互联系。 知识图谱是通过将应用数学、图形学、信息可视化技术、信息科学等学科的理论与方法与计量学引文分析、共现分析等方法结合,并利用可视化的图谱形象地展示学科的核心结构、发展历史、前沿领域以及整体知识架构达到多学科融合目的的现代理论。它能为学科研究提供切实的、有价值的参考。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等

摘要

知识图谱(KGs)在工业和学术领域有很多应用,这反过来又推动了朝着大规模地从各种来源提取信息大量的研究工作。尽管付出了这些努力,但众所周知,即使是最先进的KGs也是不完整的。链路预测(Link Prediction, LP)是一种根据KG中已存在的实体去预测缺失事实的任务,是一种有前途的、广泛研究的、旨在解决KG的不完整的任务。在最近的LP技术中,基于KG嵌入的LP技术在一些基准测试中取得了很好的性能。尽管这方面的文献在迅速增加,但对这些方法中各种设计选择的影响却没有引起足够的注意。此外,这一领域的标准做法是通过测试大量的事实来报告准确性,其中一些实体被过度表示;这允许LP方法通过只修改包含这些实体的结构属性来展示良好的性能,而忽略KG的主要部分。本篇综述分析提供了基于嵌入的LP方法的全面比较,将分析的维度扩展到常见的文献范围之外。我们通过实验比较了16种最先进的方法的有效性和效率,考虑了一个基于规则的基准,并报告了文献中最流行的基准的详细分析。

介绍

知识图谱(KGs)是真实世界信息的结构化表示。在一个KG中,节点表示实体,例如人和地点;标签是连接它们的关系类型;边是用关系连接两个实体的特定事实。由于KGs能够以机器可读的方式对结构化、复杂的数据进行建模,因此它被广泛应用于各个领域,从问答到信息检索和基于内容的推荐系统,并且对于任何语义web项目都非常重要。常见的KG有FreeBase、WikiData、DBPedia、Yago和行业KG有谷歌KG、Satori和Facebook Graph Search。这些巨大的KG可以包含数百万个实体和数十亿个事实。

尽管有这样的努力,但众所周知,即使是最先进的KGs也存在不完整性问题。例如,据观察FreeBase是用于研究目的的最大和最广泛使用的KGs之一,但是在FreeBase中超过70%的个体没有出生地点,超过99%的个体没有民族。这使得研究人员提出了各种各样的技术来纠正错误,并将缺失的事实添加到KGs中,通常称为知识图谱补全或知识图谱增强任务。可以通过从外部源(如Web语料库)提取新的事实,或者从KG中已经存在的事实推断缺失的事实,来增长现有的KG。后来的方法,称为链接预测(LP),是我们分析的重点。

LP一直是一个日益活跃的研究领域,最近受益于机器学习和深度学习技术的爆炸式增长。目前绝大多数LP模型使用原始的KG元素来学习低维表示,称为知识图谱嵌入,然后利用它们来推断新的事实。在短短几年的时间里,研究人员受到RESCAL和TransE等一些开创性工作的启发,开发了几十种基于不同的架构的新模型。这一领域的绝大多数论文都有一个共同点,但也存在问题,那就是它们报告的结果汇总在大量的测试事实之上,其中很少有实体被过度表示。因此,LP方法可以在这些基准上表现出良好的性能,只对这些实体进行访问,而忽略其他实体。此外,当前最佳实践的局限性可能使人们难以理解这一文献中的论文是如何结合在一起的,以及如何描述出值得追求的研究方向。除此之外,目前技术的优点、缺点和局限性仍然是未知的,也就是说,几乎没有研究过允许模型更好地执行的情况。粗略地说,我们仍然不知道是什么可以让一个事实变得容易还是难以学习和预测。

为了缓解上述问题,我们对一组有代表性的基于KG嵌入的LP模型进行了广泛的比较分析。我们优先考虑最先进的系统,并考虑属于广泛的体系结构的工作。我们从零开始对这些系统进行训练和调整,并通过提出新的、信息丰富的评估实践,提供超出原始论文的实验结果。具体是:

我们考虑了16个模型,属于不同的机器学习和深度学习架构;我们还采用了一个基于规则挖掘的附加的最先进的LP模型作为基线。我们提供了实验比较考虑的方法的详细描述和相关文献的总结,以及知识图谱嵌入技术的教育分类。 我们考虑了5个最常用的数据集,以及目前用于基准测试的最流行的指标;我们详细分析了它们的特点和特性。 对于每个模型,我们为每个数据集提供了效率和有效性的定量结果。 我们在训练数据中提出一组结构特征,并测量它们如何影响每个模型对每个测试事实的预测性能。

方法概述

在本节中,我们描述并讨论了基于潜在特征的知识管理的主要方法。正如在第2节中所描述的,LP模型可以利用各种各样的方法和架构,这取决于它们如何对优化问题进行建模,以及它们实现来处理优化问题的技术。

为了概述它们高度不同的特征,我们提出了一种新的分类法,如图1所示。我们列出了三个主要的系列模型,并进一步将它们划分为更小的组,以独特的颜色标识。对于每个组,我们都包括最有效的代表性模型,优先考虑那些达到最先进性能的模型,并且在任何可能的情况下,优先考虑那些具有公开可用实现的模型。结果是一组16个模型,基于极其多样化的架构;这些是我们随后在比较分析的实验部分所使用的模型。对于每个模型,我们还报告了发表的年份以及从其他模型得到的信息。我们认为,这种分类有助于理解这些模型和在我们的工作中进行的实验。表1报告了关于所包括的模型的进一步信息,例如它们的损失函数和空间复杂性。我们确定了三大类模型:1)张量分解模型;2)几何模型;3)深度学习模型。

张量分解模型

这个家族的模型将LP解释为一个张量分解的任务。这些模型隐式地将KG考虑为一个三维邻接矩阵(即一个3维张量),由于KG的不完整性,这个邻接矩阵只有部分可观测。张量被分解成低维向量的组合(比如一个多线性乘积):这些向量被用作实体和关系的嵌入表示。张量分解的核心思想是,只要训练集训练不过拟合,则学习到的嵌入应该能够泛化,并将高值与图邻接矩阵中不可观测的真实事实相关联。在实践中,每个事实的得分都是通过对事实中涉及的特定嵌入进行组合计算得出的;通过优化所有训练事实的评分函数,可以像往常一样进行学习嵌入。这些模型倾向于使用很少或根本没有共享参数;这使得它们特别容易训练。

几何模型

几何模型将关系解释为潜在空间的几何变换。对于给定的事实,头实体嵌入进行空间转换τ,使用嵌入的关系作为参数的值。对事实评分的值是结果向量和尾向量之间的距离;这样则可以使用距离函数计算δ(例如L1和L2范数)。

深度学习模型

深度学习模型使用深度神经网络来执行LP任务。神经网络学习参数,如权重和偏差,它们结合输入数据,以识别显著模式。深度神经网络通常将参数组织成独立的层,通常穿插非线性激活函数。

随着时间的推移,人们开发了许多不同类型的层,对输入数据应用不同的操作。例如,全连接层将把输入数据X与权重W结合起来,并添加一个偏差B: W X + B。为了简单起见,在下面的公式中我们将不提及偏差的使用,使其保持隐式。更高级的层执行更复杂的操作,如卷积层(它学习卷积内核以应用于输入数据)或递归层(以递归方式处理顺序输入)。

在LP任务中,通常结合各层的权重和偏差来学习KG嵌入;这些共享的参数使这些模型更有表现力,但可能导致参数更多,更难训练,更容易过拟合。

成为VIP会员查看完整内容
0
105
小贴士
相关资讯
论文浅尝 | 用于知识图中链接预测的嵌入方法 SimplE
开放知识图谱
19+阅读 · 2019年4月3日
论文浅尝 | 基于属性嵌入的知识图谱间实体对齐方法
开放知识图谱
23+阅读 · 2019年3月26日
论文浅尝 | Knowledge Vault: 全网规模的知识概率融合方法
开放知识图谱
7+阅读 · 2019年3月11日
论文浅尝 | 基于知识库的自然语言理解 02#
开放知识图谱
6+阅读 · 2019年2月24日
论文浅尝 | 基于置信度的知识图谱表示学习框架
开放知识图谱
20+阅读 · 2018年2月27日
相关论文
Zhanqiu Zhang,Jianyu Cai,Yongdong Zhang,Jie Wang
15+阅读 · 2019年12月25日
Zhen Zhang,Jiajun Bu,Martin Ester,Jianfeng Zhang,Chengwei Yao,Zhi Yu,Can Wang
6+阅读 · 2019年11月14日
Efficiently Embedding Dynamic Knowledge Graphs
Tianxing Wu,Arijit Khan,Huan Gao,Cheng Li
9+阅读 · 2019年10月15日
Liang Yao,Chengsheng Mao,Yuan Luo
12+阅读 · 2019年9月7日
Afshin Sadeghi,Damien Graux,Jens Lehmann
4+阅读 · 2019年5月29日
Ye Liu,Hui Li,Alberto Garcia-Duran,Mathias Niepert,Daniel Onoro-Rubio,David S. Rosenblum
15+阅读 · 2019年3月13日
Ivana Balazevic,Carl Allen,Timothy M. Hospedales
5+阅读 · 2018年8月28日
Eliyahu Kiperwasser,Miguel Ballesteros
5+阅读 · 2018年4月24日
Tim Dettmers,Pasquale Minervini,Pontus Stenetorp,Sebastian Riedel
27+阅读 · 2018年4月6日
Liwei Cai,William Yang Wang
5+阅读 · 2018年2月20日
Top