自动化知识图谱表示（从三元组到子图）自动化知识图谱表示：从三元

导读：
知识图谱是一种特殊的图结构，它包含了语义信息与图结构信息。它可以被应用在多个领域，如QA问答系统、推荐系统、新药发现、股市预测等。现在无论是学术界还是工业界都陆续提出了自己的知识图谱构建平台。第四范式也建立了低门槛、全流程的知识图谱平台Sage Knowledge Base。今天的分享旨在从三元组到子图的维度来介绍自动化知识图谱表示学习的相关技术。
今天的介绍会围绕下面四点展开：

背景介绍：什么是知识表示学习
重要方向：知识表示学习及AutoML
模型设计：从三元组到子图
总结

▌背景介绍首先和大家分享下知识表示学习的背景。

文章图片

知识图谱是一种特殊的图结构，它使用实体来表示自然界的物体或者抽象的概念，使用关系来建模实体之间的交互，其基本的存储形式是（头实体h，关系r，尾实体t）的三元组。知识图谱是一个语义图，它既包含语义信息又包含图结构信息。

文章图片

知识表示学习旨在学习将知识图谱中的符号（包括实体和关系）映射到一个低维的向量空间。其优点在于学习得到的向量是连续的，且可以发掘隐藏的性质。此外，在向量空间中计算相似度是十分高效的。
知识图谱表示学习的整体框架如上图所示。给定一个知识图谱，我们将图中所有存在的三元组作为正样本，同时我们也需要在图中采样负样本，我们需要保证负样本不存在于知识图谱中，通常的做法为将图中存在的三元组的头实体、尾实体、关系选择至少一个进行随机替换。得到正负三元组后，我们会设计一个模型对知识图谱进行建模，通过循环迭代来优化损失函数，更新embedding以及模型参数。我们的优化目标是尽可能多地保留原图中蕴含的信息。

文章图片

知识图谱表示学习有以下几个基本的任务：

知识图谱补全：这是目前业界关注最广泛的任务，其针对图谱中不存在的边进行链接预测或者在图谱中进行三元组分类任务；
实体匹配：其目标是将两个不同的知识图谱中相同实体进行匹配。例如一个中文图谱与另一英语图谱中有一些词语是同义的，那么我们可以进一步发掘两张图中其他词之间的关系来判断它们是否是同义的；
实体分类：任务目标是预测实体的类别。例如在学术图谱中判断一篇文章属于哪一个领域等。

文章图片

这里以链接预测任务为例展示知识图谱表示学习的评估指标。对于给定的三元组(h,r,t)，我们可以把头实体或者尾实体替换为图中所有的实体组成一个集合，那么评估任务就是得到模型经过打分排序后对正样本的排名。评价指标有三类：mean rank (MR)，mean reciprocal rank (MRR)以及Hit@K。三个指标的评估侧重点不一样。MR受离群值的影响较大，MRR更关注准确率，Hit@K更关注召回率。
▌重要方向：知识表示学习及AutoML

文章图片

知识图谱表示学习由五个关键模块组成。首先，我们需要定义一个打分函数对问题进行建模；然后，由于图谱中只包含正样本，那么负采样的设计也十分关键；得到正负样本之后我们需要定义一个损失函数；同时，为了避免模型过拟合，我们需要设计正则化项；最后，我们针对损失函数以及正则化项进行整体的模型优化。

文章图片

给定一系列三元组，我们需要对它们进行打分。目前有三类建模方法：基于三元组，直接对其进行打分；基于路径，我们需要找到头实体和尾实体的连接路径，通过寻找到的一系列路径进行推理；基于子图，我们需要在图谱中抽取包含头实体与尾实体的子图，然后根据子图信息进行推理。

文章图片

负采样的基本做法是对给定的正样本(h,r,t)，我们将头实体或者尾实体随机替换为图中另外一个实体，并且这个新的三元组不存在于图谱中。

文章图片

但是由于负样本集合的数量十分庞大，进行简单的随机采样会导致得到的负样本质量较差。在2018年，学术界提出了基于对抗神经网络的方法生成高质量负样本，但是这一类方法的问题在于：我们需要单独训练一个生成模型来输出负样本，而且由于样本是离散的，模型的学习过程需要基于强化学习。这两大问题会导致整体模型的学习十分不稳定。
我们针对以上问题，提出一个将高质量负样本存储在缓存中的方法。在训练过程中，负样本的生成、抽取和更新是不断进行的，保证模型能得到高质量负样本的同时大幅提升训练效率，且这一方法不需要额外训练一个样本生成模型。以上工作发表在ICDE 2019会议与VLDB-J 2021期刊上。

文章图片

模型需要平衡表达能力和复杂度。在知识图谱中，由于embedding的参数十分庞大，我们必须考虑对模型进行正则化。正则化的通用方法有：将embedding的范数限制在小于1的范围内；加入一个p范数的regularizer；增加针对embedding的dropout。

文章图片

模型参数可以通过随机梯度下降的方法来进行优化。整个算法流程如上图所示，我们首先在图谱上抽取正样本，并通过负采样得到负样本，随后使用模型得到三元组的打分，最后基于包含正则化项的损失函数来更新embedding。模型优化过程中包含很多超参数，如学习率、初始化、batch size、dimension size、early stop等。

文章图片

超参数优化是我们一个重点研究的方向。大部分超参数优化算法每次迭代时在搜索空间中选取一组参数，在整个知识图谱上评估模型效果，但这一算法费时费力。在今年的ACL会议中，我们提出了KGTuner。这是一个两阶段的超参数搜索优化算法。在第一阶段，我们大幅减少了参数搜索空间，并且使得算法在一个采样得到的子图上评估模型效果。通过这一方法，我们可以在第一阶段搜索中探索大量优质的超参数样本，选取模型效果最好的top10超参数，作为第二阶段fine-tune的候选集合。第二阶段搜索优化的过程中我们会增加样本的batch size和dimension size，并基于完整的图谱来评估模型效果，最终确定最优的超参数。

文章图片

下面简单介绍一下自动化机器学习AutoML。AutoML将搜索空间和搜索目标包装成一个上层的优化问题，从而使得整个超参数优化问题可以转化为一个Bi-level的优化过程。具体地，搜索空间定义了我们需要搜索的对象（如超参数、模型结构等），训练目标位于优化问题的内层，搜索目标位于优化问题的外层，同时在搜索的过程中存在一些限制条件。

文章图片

不同知识图谱的数据集数据分布差异较大，它们包含的关系种类也各不相同，例如关系种类可以分为：对称性、反对称性、相反性、非对称性、组合性等。另外，知识图谱的下游任务多种多样，如边预测、实体匹配、节点分类等。面对如此复杂的数据以及多样的任务，如果我们想要进行统一的建模则需要丰富的专家知识才能完成，而AutoML可以帮助我们有效地降低建模的门槛。

文章图片

AutoML搜索优化的定义也可以一一对应于超参数优化的四个组成模块：

搜索空间：包含搜索超参数以及打分模型；
搜索目标：基于排序的评价指标；
训练目标：损失函数；
搜索限制条件：搜索的总时长。

AutoML也有很多待选择的搜索算法。传统的搜索算法有grid search, random search, 贪心算法，遗传算法等。此外，我们还有一些基于模型的优化算法，如贝叶斯优化、强化学习、梯度下降算法等。
▌模型设计：从三元组到子图下面我来重点分享针对知识图谱表示学习的模型设计。
1. 基于三元组的模型
在过去的十年间，业界提出了大量的打分函数来建模三元组，它们对三元组中存在的关系的捕捉侧重点各有不同。我们先来介绍基于三元组的模型。

文章图片

首先是基于平移距离的模型。例如TransE以及它的衍生模型TransH和RotatE将三元组建模为头实体经过关系r在一个向量空间中进行平移后得到尾实体，通过向量的距离差来设计模型的打分函数。TransH和RotatE解决了TransE在一对多与对称关系中建模能力不足的问题。但是总体来说，基于平移距离的模型表达能力不足，导致其在边预测任务中效果不尽如人意。

文章图片

随着神经网络的发展，如基于多层感知器（MLP）的模型、基于卷积神经网络的模型（ConvE）以及基于递归神经网络的模型（RSN）被业界提出，用来建模三元组的知识表示学习。但是，基于神经网络的模型通常较为复杂并且难以被训练。

文章图片

最后一类是双线性模型，它们也是基于三元组的知识表示学习中效果最好的一类。双线性模型的表达能力强且模型复杂度不高。2011年被提出的RESCAL便是一个典型的双线性模型。通俗来说，线性模型是一个矩阵乘以一个向量，而双线性模型则是则一个矩阵两侧分别左乘和右乘一个向量（头实体向量和尾实体向量），最后得到一个标量来作为三元组的得分。RESCAL的relation矩阵的维度是D×D，其包含的参数过多，从而导致模型的过拟合。

文章图片

为了解决过拟合问题，DistMult将relation矩阵限制为一个对角矩阵。但是DistMult的打分函数满足交换律，导致其不能建模一些非对称的关系。

文章图片

为了方便统一建模双线性模型，DistMult可以拆分为上图所示的表达形式。例如，我们将头实体和尾实体向量都分为四份，那么DistMult可以被分解为四组内积相加的形式。

文章图片

为了解决DistMult不能建模非对称关系的问题，ComplEx将实体向量与关系矩阵所在空间从实数空间转换为复数空间。那么由于复数乘法的不对称性，ComplEx可以建模非对称的关系。

文章图片

同理，我们也可以对ComplEx进行类似于DistMult的拆分，写成四组实部内积之和和四组虚部内积之和的形式。事实上，对于所有基于双线性建模的模型，我们都可以将其拆分为类似的表达形式，具体细节这里就不再展开，感兴趣的同学可以通过查看对于论文来进行了解。

文章图片

以上所有双线性模型的不同之处在于对于relation矩阵的建模方式各有差异。虽然每一个模型都具有很好的表达能力，但是针对多种多样的下游任务，它们每一个都无法在所有任务中优于其他同类型方法，导致其泛化能力不足。基于双线性模型的表达形式以及之前方法存在的问题，我们提出了AutoSF，旨在自动化搜索relation矩阵的建模方法，从而达到统一建模的目标。

文章图片

对搜索问题的定义如上图所示。考虑到双线性模型的差异在于relation矩阵的不同形式，所以我们把问题抽象为：对于一个K×K的relation矩阵，每一个元素我们可以在-K,…0,…K这（2K+1）个数字中选择一个来进行填充。给定搜索空间，我们每次在搜索空间中选取一个结构（即一个relation矩阵），它对应于一个打分函数；基于这个打分函数我们可以训练一个模型，并在验证集中使用评估函数衡量模型效果；得到的结果传递至优化器，旨在在搜索空间中选取在验证集中能得到更好的效果的结构。通过循环迭代，最终得到最优的打分函数。搜索空间十分庞大，大小为

文章图片

如果我们对每一个候选元素进行训练与评估，那么其开销是不可接受的，所以AutoSF及其改进版本AutoSF+分别设计了两种算法来优化搜索效率。

文章图片

在AutoSF中我们提出了渐进式的搜索算法。以上图为例，首先我们搜索在测试集中表现最好的relation矩阵，且限制其仅含有四个非零元素；在此基础上，每次迭代我们进一步增加非零元素的个数，并搜索对应条件下评价指标最好的relation矩阵。渐进式算法的灵感来源于我们希望保证每次对效果最好的relation矩阵进行微调，从而使其逐渐地找到最优结构。但是，渐进式搜索算法属于贪心算法，容易得到局部最优解。为了解决这个问题，我们在AutoSF+中提出了基于遗传算法的搜索模式。具体地，我们可以在每次迭代时使用变异和交叉操作对矩阵进行修改，然后在所有修改的矩阵中保留一部分性能较好的矩阵，最终找到更好的relation矩阵。一般来说，这一算法相较于渐进式算法会更加灵活。

文章图片

同时，在选取矩阵的过程中我们会考虑领域的性质。我们设计一个过滤器来减少冗余评估。比如，包含全零行或者全零列的矩阵不需要被评估；某些矩阵之间是等价的，我们仅需保留其中一个矩阵进行评估即可。此外，在文章中我们证明了矩阵的对称性是模型是否可以全面表达知识图谱的重要性质。所以，我们定义了一个基于relation矩阵的对称性来进行模型性能预测的预测器，它通过矩阵中包含的对称性相关特征，使用两层MLP对模型性能进行打分。

文章图片

实验结果表明双线性模型比基于平移距离的模型与基于神经网络的模型效果更好。此外，对于每一组双线性模型，在不同数据集下的表现均有所差异，不存在绝对的胜者。而AutoSF通过搜索算法在不同数据集中都可以得到最优的效果。我们对搜索到的结构进行了可视化，如上图所示。可以观察到，AutoSF搜索到的最优关系结构在不同数据集下各不相同，这证明了我们的方法达到了data dependent的目标。
最后对基于三元组的知识图谱表示学习进行简单的总结。双线性模型是基于三元组的建模方法中效果最好的。AutoSF(+)是一个基于AutoML的双线性打分模型，其搜索空间是统一表达形式下的双线性模型，它们可以保证模型拥有出色的表达能力。AutoSF(+)使用了渐进式以及基于遗传算法的搜索算法，并设计了过滤器和预测器来引入领域属性特征，进一步提升模型结构搜索性能。相关文章发表在了ICDE 2020会议以及TPAMI 2022期刊中。
2.基于关系路径的模型
下面来介绍一下基于关系路径的模型。

文章图片

三元组的表达能力有限，如果我们可以将三元组中的头实体和尾实体通过图中一条路径进行连接，那么我们就可以得到更加丰富的信息。首先，三元组本身会被保留在路径之中；其次，路径可以表达更复杂的关系；此外，路径中还包含了多个三元组之间的长链信息。

文章图片

PTransE基于TransE做了拓展，将三元组改造为一系列由多个关系组合而成的路径。类似于TransE，头实体和尾实体之间的关系可以使用平移向量之和来表达。具体公式如上图所示。但是，与TransE存在的问题一样，它无法解决一对多与对称关系，所以PTransE的建模效果一般。

文章图片

RSN（Recurrent Skipping Network）使用RNN来建模路径，其中实体节点加入了skip connection结构，最终输出对应的实体与关系embedding。RSN可以很好地建模长期信息，但它很难有效地捕捉三元组内部的语义信息。

文章图片

为了解决前述方法的缺陷，我们提出了Interstellar模型。我们以每个三元组为单位将路径进行切分。针对每个三元组，我们可以对模型的建模结构进行搜索。如果我们将三元组之间的路径断开，那么模型就可以退化为基于三元组的建模方式；如果我们将路径中间每个三元组的尾实体去除（输入0向量），那么模型就退化为PTransE（只建模关系向量表达）。通过这一策略，我们可以使得模型自动化地捕捉路径中包含的不同语义信息与性质。

文章图片

与AutoSF相同，我们需要对模型的搜索算法进行设计。若我们直接采用AutoSF的搜索算法，将每一组新的结构配置对应的模型进行一次完整的训练（stand-alone）则会有很高的代价，但是这一做法的好处是可以得到精准的模型评估结果。相对地，基于one-shot的方法会共享已经训练好的模型参数，使得这一类型的搜索算法十分高效，但是代价是只能得到不可靠的模型评估结果。我们的算法吸收了这两类算法的优点，在宏观层面（connection、combinators）使用stand-alone的方法得到对模型结构配置的准确效果评估，而在微观层面（activation、weight matrix）使用one-shot的方法得到高效的模型评估结果。

文章图片

文章图片

在实体匹配任务中，经过对比实验我们可以发现Interstellar相较于其他基础模型都有很大的性能提升；在不同的数据集上，我们的模型也对三元组建模了完全不同的结构配置。在链接预测任务中，我们观察到WN18-RR数据集中一跳的关系较多，而相对的在FB15k-237数据集中两跳关系的占比较高。Interstellar最终给出的三元组结构搜索结果也很好地体现了这一特点，可视化图示如上所示。以上结果佐证了我们所提出的模型的建模结果与数据具有强相关性，且模型针对结构搜索的设计对最终性能的提升有着关键作用。
在这里，我对基于关系路径的建模方法做一个总结。首先，基于关系路径的方法与基于三元组的方法相比蕴含了更多的信息。我们提出了Interstellar，它是一个基于神经网络结构搜索的算法，可以递归地处理路径中实体之间的关系。搜索空间分为宏观搜索空间（connections以及combinators算子）与微观搜索空间（activations以及weighting matrices）；搜索算法利用了stand alone与one-shot方法中各自的优点，设计了一种混合式的搜索算法。以上工作发表在了NeurIPS 2020会议中。
3.基于图神经网络的模型

文章图片

最后一类方法是基于子图的图神经网络（GNN）模型。图神经网络近些年在包含图结构的数据中展现了强大的表达能力。在知识图谱表示学习领域，最近也有不少模型尝试将GNN运用至图谱的子图中。
R-GCN、CompGCN、KE-GCN三种方法都是以浅层的embedding作为模型输入，使用关系型GNN进行节点聚合得到高层embedding，再通过TransE、ConvE等打分函数来得到最终得分。但是这类型方法需要加载完整的知识图谱，导致其可扩展性较差；另外，这类模型依赖于打分函数，且使用GNN后对模型最终效果的提升有限。

文章图片

2020年业界提出了GraIL模型，它基于给定的头实体与尾实体将包含它们的子图从原图谱中抽取出来，随后基于节点与头尾实体的距离进行entity labeling，最后使用GNN对子图进行消息传递与更新。最终我们可以得到以头实体与尾实体组成的三元组的打分。GraIL不需要经过训练的embedding就可以做归纳式推理，这就使得其对于未知节点也可以使用图结构进行打分，但是子图的抽取与子图中节点标签的生成的时间复杂度较高。

文章图片

基于前述模型的缺点，我们提出了RED-GNN的模型。首先，我们利用关系路径，将图中得到的路径增强至同一长度，具体做法是引入了identity关系；随后，我们将所有路径进行堆叠，得到一个关系子图（有向图，保留了信息的传播方向）。

文章图片

由于关系子图中层与层之间的路径存在overlapping，我们可以利用动态规划的方式来一次性建模所有共有相同头实体的关系子图。如上图所示，左侧是传统的GNN计算方法，我们需要对每一个关系子图进行单独的计算，而右侧展现了RED-GNN的计算方法，我们可以使用递归计算与并行计算，使得GNN一次性建模多个关系子图。GNN的信息聚合是基于实体之间的关系信息，并且采用了attention机制进行自适应融合。

文章图片

上图展示了对比实验的结果。RED-GNN是一个纯粹使用子图结构的模型，并没有使用实体embedding，所以它同时适用于transductive以及inductive的推理。从实验结果中我们可以发现，即使模型没有使用任何embedding信息，它的效果依然优于绝大部分方法。由于模型的参数量较少，且设计了基于动态规划的算法，RED-GNN的计算效率相较于GraIL有了很明显的提升。
现在我来对基于GNN的方法进行总结。首先，单纯将GNN经过少量修改使用到知识图谱表示学习中的效果并不理想。我们提出了RED-GNN模型，通过对于子图结构进行基于GNN的学习，在transductive与inductive推断中均取得了SOTA的效果。我认为知识图谱中的子图学习是一个很有潜力的研究方向，目前该方法面临着计算效率的挑战。
▌总结今天我们针对知识图谱表示学习领域介绍了三类模型：

基于三元组的模型：侧重于建模具有对称性或相反性的语义，但它无法建模结构信息且可解释性较差。其优势在于计算效率高，在实际落地中应用较为广泛；
基于关系路径的模型：侧重于建模复合语义，可以建模序列型结构信息，使用简单逻辑规则来达到可解释性的效果。这一类模型的计算复杂度依赖于路径的数量；
基于子图的模型：侧重于建模高阶语义，可以建模拓扑结构信息，使用复杂逻辑规则来达到可解释性的目标。这一类模型的计算复杂度由抽取的子图决定。

使用AutoML设计模型结构可以大幅提升知识图谱表示学习的性能，但是在使用这一方法时，我们需要针对搜索空间与搜索算法考虑领域的先验知识与性质。
未来我们可以从以下四个方面来继续探索知识图谱表示学习：
将GNN的结构设计转变为一个自动化的流程；

在超大规模知识图谱中达到高效的推理；
在动态或者事例（event）知识图谱中完成推理；
将知识图谱表示学习运用至更广泛的领域，例如生物、金融等。

▌Q&A

知识图谱中存在一些长尾的关系，针对这些关系我们应该如何设计算法来更好地学习它们？

【自动化知识图谱表示（从三元组到子图）】我们在实践中发现通过AutoML可以缓解长尾关系欠学习的问题。因为AutoML的评估方式可以间接地增加那些学习得不好的关系样本的权重，从而使得优化模型结构设计时考虑到这些长尾关系的学习效果。事实上，这就类似于upsampling的方式。此外，可考虑通过小样本学习的方式更有针对性地去学习长尾关系。