知识图谱系统的建设需要工程和算法的紧密配合,在工程层面,去年蚂蚁集团联合OpenKG开放知识图谱社区,共同发布了工业级知识图谱语义标准OpenSPG并开源;算法层面,蚂蚁从知识融合,知识推理,图谱应用等维度不断推进。
OpenSPG GitHub,欢迎大家Star关注~:https://github.com/OpenSPG/openspg
本文将梳理知识图谱常用的推理算法,并讨论各个算法之间的差异、联系、应用范围和优缺点,为建设知识图谱的图谱计算和推理能力理清思路,为希望了解或者工作中需要用到知识图谱推理算法的同学提供概述和引导。
在知识图谱推理算法综述(上):基于距离和图传播的模型,我们了解到“基于距离的翻译模型”,“基于图传播的模型”的详细知识图谱算法梳理。本文为下篇,重点从基于语义的匹配模型:张量分解模型与神经网络类型进行介绍。
本章将对常用的图谱推理算法做一个概括的梳理。业界算法很多,一篇文章难以做到全面覆盖,因此我们这里挑选了与图谱推理强相关的算法进行讲解,部分类似的算法挑选了其典型代表进行讨论,算法能力范围尽量覆盖:
知识融合,包括:实体对齐、属性融合、关系发掘、相似性属性补全;
知识推理,包括:链接预测、属性值预测、事件分析、连通性分析、相似性分析。
首先,通过一张思维导图对这些图推理算法进行汇总:
概率软逻辑(Probabilistic Soft Logic)[5]。是马尔可夫逻辑网的升级版本,最大的不同是事实的真值可以在[0,1]区间任意取值。进一步增强了马尔可夫逻辑网的不确定性处理能力,能够同时建模不确定性的规则和事实。并且连续真值的引入使得推理从原本的离散优化问题简化为连续优化问题,大大提升了推理效率。因为是连续值,所以其“与、或、非”规则专门定义了一套公式。
图表示学习(Knowledge Graph Embedding)是知识图谱中的实体和关系通过学习得到一个低维向量,同时保持图中原有的结构或语义信息。所以一组好的实体向量可以充分、完全地表示实体之间的相互关系,因为绝大部分机器学习算法都可以很方便地处理低维向量输入,可以应用于链接预测、分类任务、属性值计算、相似度计算等大多数常见任务。其包含基于距离的翻译模型,基于图传播的模型,基于语义的匹配模型等板块。本文围绕基于语义的匹配模型展开讨论。
基于语义的匹配模型
这类模型使用基于相似度的评分函数评估三元组的概率,将实体和关系映射到隐语义空间中进行相似度度量。这类方法分为两种:一类是简单匹配模型:RESCAL张量分解模型及其变种。二类是深度神经网络SME、NTN(Neural Tensor Networks)神经张量模型、MLP、NAM等等。
Trans系列算法是利用求和来表达关系对头结点的影响,而RESCAL[14]是利用旋转、拉伸来表达关系对头结点的影响。旋转、拉伸操作在数学上就是乘以矩阵Mr。RESCAL张量分解算法是将整个知识图谱看作一个大的张量,通过张量分解技术分解为多个小的张量片,即将高维的知识图谱进行降维处理,大幅减少计算时的数据规模。张量构建的基本方法是,如果实体i和实体j存在关系k,则否则为0。
其目标函数如下(一种向量内积):
DistMult[15]是为了减少RESCAL的参数空间,而采用了一个对角矩阵diag(r)来代替矩阵Mr。这一点与TransH和TransE之间的关系有异曲同工之妙。其目标函数如下:
需要留意的是,因为采用了对角矩阵diag(r),而h、t互换后是相等的,见下式,导致DistMult只能处理对称关系。比如"A-同学-B",而不能处理非对称关系,比如"A-父亲-B"。
HolE[16]是为了在缩小RESCAL的参数空间前提下,依然能够处理非对称关系而开发的。方法就是每次先利用快速傅里叶变换对头向量和尾向量做一个shift i 位,然后再做内积运算。因为头向量和尾向量shift的位数不一样,就打破了对称性,就可以处理非对称关系了。其目标函数如下:
ComplEx[17]和HolE目的相同,为了能够缩小RESCAL的参数空间,同时依然能够处理非对称关系。ComplEx采用了复数的方式,扩充到实部和虚部以增加自由度的方式来解决非对称关系。其目标函数如下:
ANALOGY[18]融合了DistMult、HolE、ComplEx这三类模型,以期待得到更好的效果。
SME[19]利用深度神经网络构造一个二分类模型,将h、r和t输入到网络中。先经过隐藏层gu和gv分别将h、r以及t、r结合,然后将这两个结果在输出层做内积作为得分。如果(h,r,t)在知识图谱中真实存在,则应该得到接近1的概率,如果不存在,应该得到接近0的概率。得分函数如下:
隐藏层gu和gv分别将h、r以及t、r结合。有两个版本,其中一个是线性版本:
另外一个是双线性版本:
NTN[20]是另外一种神经网络结构。与SME打平的结构不同,NTN先用隐藏层将h、t结合起来,经过一个激活函数tanh以后,在输出层与关系向量r相结合。得分函数如下:
MLP[21]模型更简单一些,h、r、t经过输入层结合在一起,通过激活函数tanh后得到非线性的隐藏层,权重为M1、M2、M3,最后再经过一个线性的输出层,权重为w。得分函数如下:
NAM[22]先将h和r经过输入层后结合在一起,然后使用多层DNN作为隐藏层,第层为z()。
得分函数如下:
Logistic loss适合RESCAL系列模型。是基于Close World假设,即将未观察到的三元组视为不成立。对正确的三元组进行奖励,对错误的三元组进行惩罚。
Pairwise ranking loss更适合Trans系列模型。是基于Open World假设,将未观察到的三元组视为不一定成立。将事实三元组和未观测到三元组从距离上尽量分开。
这里是给定常数margin,用于将正、负三元组分开。是正样本的打分,是负样本的打分。
上面这些算法默认都是随机初始化的。初始化这里也有发挥的空间,比如可以利用外部知识源做一些预训练等。
给定三元组(h, r, t)中任意两个预测第三个。
评估指标有:
对给定三元组(h, r, t)判定成立还是不成立。
这里用了一个技巧,即将实体分类转化为求 “Is A” 关系。
若两个实体的向量相等,就判定为同一个实体
Trans系列、RESCAL系列、SME系列这三类模型的参数数量与节点数量成正比,面对大规模图谱时往往捉襟见肘。为了克服这个困难,人们引入了图神经网络模型GNN,图神经网络后来发展成为了一个体系,本文后面会介绍到包括GCN、GAT、Structure2vec、GeniePath等等图神经网络算法。图神经网络算法通过共享参数的方式降低了参数空间,就能适用于大规模图推理了。
文献已经下表将上述各类算法做了一个汇总,将上述算法的实体、关系嵌入向量,打分函数,约束信息的表达式做了整理如下:
从算法分类角度
无监督:Deepwalk、Node2Vec、Metapath2vec、LINE、Louvain
有监督:GCN(半监督)、GraphSAGE、SDNE(半监督)、GeniePath、GAT、Structure2Vec、HeGNN
从应用角度
链接预测:所有的embedding算法都支持链接预测。有一个区别是同质图模型支持一种关系预测,而异质图模型支持多种关系预测。(另外加上ALPS平台尚未包括的trans系列也可以做链接预测)。
实体归一(相似度计算):所有的embedding算法都支持相似度计算。相似度是由具体的任务目标来定义并体现在loss中,一般的任务目标有距离相似性(两个节点有几度相连)、结构相似性、节点类型相似性(label预测)。
属性值预测(label预测):GCN、GraphSAGE、GeniePath、GAT、Structure2Vec、HeGNN等。
支持异质图:HeGNN、metaPath2vec、KGNN
支持同质图:Deepwalk、Node2Vec、LINE、SDNE、GCN、GraphSAGE、GeniePath、GAT、Structure2Vec
|