面向知识图谱归纳链接预测的负采样方法

A Negative Sampling Method for Knowledge Graph Inductive Link Prediction

摘要

知识图谱归纳链接预测模型在训练过程中需要使用正例三元组和负例三元组，而当前的随机负采样方法容易产生低质量的负例三元组，影响模型的特征学习能力。针对该问题，提出一种基于相似性的负采样方法。首先，获取被替换实体周围的k跳邻居节点集合；其次，从该集合中挑选相似度高的实体替换原三元组中头实体或者尾实体，从而生成负例三元组；最后，将该方法应用在归纳链接预测模型中，并在WN18RR和FB15K-237数据集上进行归纳链接预测实验。实验结果表明，相比其他模型，该方法在MRR指标最高提升10.47个百分点，在Hits@10指标最高提升16.02个百分点。通过负样本质量分析，进一步说明该负采样方法生成高质量的负例三元组，提升模型的性能。

Abstract

The inductive link prediction model of knowledge graphs requires both positive and negative triplets during the training process. However, the current random negative sampling method tends to produce low-quality negative triplets, which affects the feature learning ability of the model. To address this problem, a similarity-based negative sampling method is proposed. Firstly, the set of k-hop neighbor nodes around the replaced entity is obtained. Secondly, the entities with high similarity are selected from the set to replace the head or tail entities in the original triplet, so as to generate a negative triplet. Finally, the negative sampling method is used in the inductive link prediction model, and the inductive link prediction experiments are carried out on the WN18RR and FB15K-237 datasets. Experimental results demonstrate that compared with other models, the MRR metric is increased by up to 10.47 percentage point, and the Hits@10 metric is increased by up to 16.02 percentage point. Furthermore, the negative sample quality analysis illustrates that high-quality negative triplets are generated by using the negative sampling method, which improves the performance of the model.

Graphical abstract

关键词

知识图谱 / 归纳链接预测 / 负采样 / k跳邻居 / 相似性计算

Key words

knowledge graph / inductive link prediction / negative sampling / k-hop neighbours / similarity calculations

知识图谱（Knowledge Graph, KG）链接预测任务分为实体预测和关系预测。实体预测为给定一个三元组（?,r,t）或者（h,r,?），目标是训练模型来预测缺失的头实体或者尾实体；关系预测为给定一个三元组(h,?,t)，目标是训练模型来预测缺失的关系^[1-2]。在传统知识图谱链接预测方法中，由于测试集中涉及的所有实体和关系均已在训练集中出现，因此模型能够在训练过程中学习到这些实体和关系的特征。随着应用业务的发展，知识图谱中会出现很多在训练集中未出现过的新实体和关系，这种场景下运用传统方法进行链接预测需要重新训练知识图谱，产生大量的开销。为了减少训练开销，同时实现对新出现实体和关系的预测，产生了归纳链接预测^[3]。在归纳链接预测中，给定两个知识图谱，分别为源KG和目标KG，目标KG中包含有源KG中不存在的实体和关系，学习目标是通过在源KG上的学习，得到一个模型，该模型可以推广应用到目标KG中，实现对未知实体和关系的预测。

为使模型充分学习到训练数据中的信息，无论是传统的链接预测还是归纳链接预测，训练过程都需要正例三元组和负例三元组，从而使模型对正负样本有较好的区分度，而现有知识图谱中存在的都是正例三元组，因此如何构建负例三元组对知识图谱归纳链接预测模型的性能具有重要影响。现有的归纳链接预测方法中模型训练时大都采用均匀随机采样方法，该方法以相同概率随机替换头尾实体生成负例三元组，由于替换是以相同概率进行的，因此很可能会选择与原实体不属于同一类型或语义无关的实体作为替换对象。这样会导致生成许多低质量的负例三元组，从而对模型的训练效果产生负面影响^[4]。

针对以上问题，提出一种面向归纳链接预测的负采样方法。假设语义相近实体替换正确三元组头或者尾实体构造的负例三元组质量更高。首先，选择要替换实体的k跳邻居构成候选集合；其次，将要替换实体和候选集合中的实体进行相似度计算，挑选出相似度较高的实体进行替换，构成高质量负例三元组；最后，在WN18RR^[5]和FB15K-237^[6]数据集上进行实验，相比其他方法，该方法在归纳链接预测性能上有显著提升。

1 相关工作

1.1 归纳链接预测

归纳链接预测强调链接预测的泛化性，主要是通过对知识图谱中已知实体和关系的学习来对未知实体和关系进行预测。Geng等^[7]从测试集中是否包含未知实体和关系的角度出发，将归纳链接预测分为部分归纳链接预测和全归纳链接预测。测试集中只有不可见实体的情况称为部分归纳链接预测，测试集中既有不可见实体又有不可见关系的更现实、更具有挑战性的情况称为完全归纳链接预测。本文的归纳链接预测主要指对测试集中包含未知实体的部分归纳链接预测。

针对未知实体的部分归纳链接预测工作主要分为两类。1）借助图神经网络方法将邻居节点信息聚合来获取未知节点信息，比如Graph-NN^[8]和局域网（（Local Area Network, LAN））^[9]，但该类方法需要借助未知节点周围的已知节点信息对该节点进行预测，无法应用在全部由未知节点组成的全新图中。2）从知识图谱中采样目标关系周围子图，通过对子图拓扑结构和节点特征信息的学习来实现对未知实体的预测，比如GraiL^[10]、拓扑感知关联（Topology-Aware Correlations, TACT）^[11]、面向归纳关系推理的交际信息传递（Communicative Message Passing for Inductive Relation Reasoning, CoMPILE）^[12]、子图相邻关系信息（Subgraph Neighboring Relations Infomax, SNRI）^[13]，这类方法着重对子图抽取方式、包含信息和训练方式进行优化和改进。以上方法在归纳链接预测方面取得一定的效果，但都忽略负例三元组构建策略对模型效果的影响。本文主要通过改进负例三元组的构建策略，提高负采样的质量，进而提升模型链接预测性能。

1.2 负采样方法

知识图谱中存储的三元组均为正例三元组，不存在负例三元组，因此训练过程中需要自行构建负例三元组，不同的构建方式对于表示学习的效果有重要影响。目前知识图谱中常用的负采样方法有均匀随机负采样^[14]、伯努利负采样^[15]、对抗样本负采样^[16]等。

1.2.1 均匀随机负采样

随机负采样是通过随机破坏正例三元组来生成负例三元组的方法，包括随机替换实体和随机替换关系，Uniform方法以平等的概率随机替换正确三元组中的头实体或尾实体来构造负例三元组，其中替换的实体从实体集中随机抽样得到。Random Corrupt^[17]对上面方法进行扩展，除了将正三元组的头或尾实体替换外，还将正例三元组的关系替换为关系集合中的随机关系，以增强关系信息的表示。随机采样方法实现简单，但所获得的负例三元组有可能是低质量的三元组，例如对于三元组（Steve Jobs, FounderOf, AppleInc.），替换头实体后可能得到负例三元组（Baseball, FounderOf, AppleInc.）和（Bill Gates, FounderOf, Apple Inc.），显然前者为低质量三元组，后者为高质量三元组。低质量三元组会使知识图谱嵌入模型收敛速度减缓，导致模型无法学习到有效特征，从而无法提升模型性能。

1.2.2 伯努利负采样

知识图谱中的关系具有一对多、多对一和多对多的特性，基于这一特点，伯努利负采样方法根据头实体和尾实体在特定关系三元组中的数量差异，采用概率机制来选择替换实体。对于给定的关系r，如果头实体关联的尾实体数量为N_tph，尾实体关联的头实体数量为N_hpt，则替换头实体的概率为P_{\mathrm{h}}=N_{\mathrm{t}\mathrm{p}\mathrm{h}}/(N_{\mathrm{t}\mathrm{p}\mathrm{h}}+N_{\mathrm{h}\mathrm{p}\mathrm{t}})。同样，替换尾部实体的概率计算为P_{\mathrm{t}}=N_{\mathrm{h}\mathrm{p}\mathrm{t}}/(N_{\mathrm{t}\mathrm{p}\mathrm{h}}+N_{\mathrm{h}\mathrm{p}\mathrm{t}})。My-X是对伯努利负采样的扩展，关系替换概率由知识图谱中实体和关系数量决定。基于概率的方法较好地平衡了知识图谱嵌入模型的复杂度和替换准确率，但是替换的实体仍然是随机产生的，同样存在产生低质量负样本问题。

1.2.3 对抗式负采样

对抗式负采样方法包含一个生成器（generator）和一个判别器（discriminator）。生成器负责生成负例三元组，并将之混入正例中迷惑判别器；判别器负责区分出正例和生成器混入的负例，并反馈给生成器。随着模型的迭代，负样本生成器和判别器通过对抗式训练同时提高性能。

1.2.4 NSCaching

针对对抗式负采样模型复杂，训练时间长的问题，Zhang等^[18]提出基于对抗式方法的“蒸馏”版本NSCaching，该方法将高质量的负例三元组存储在缓存中，然后根据重要性采样策略来更新缓存。

综上所述，随机负采样和伯努利负采样简单方便，但可能产生无意义的三元组，导致零损失问题，模型不仅学习不到特征，甚至减慢收敛速度。对抗式负采样方法基于生成对抗网络（Generative Adversarial Network, GAN）来选择负例，一定程度上提高了负例三元组的质量，但是该方法存在训练结果不稳定、采样成本较高等问题。NSCaching方法随着知识图谱规模的增加，内存需求呈指数级增长，并且缓存的定期更新增加计算时间。

2 基于相似性的负采样方法

2.1 定义

知识图谱G={E,R,T}，其中：E表示实体集合；R表示关系集合；T表示三元组集合。对于T中一个给定的三元组（h,r,t），h表示头实体，r表示关系，t表示尾实体。负采样就是从实体集合E中选择实体e来对h或者t进行替换，构造一个集合T_n，使得T_n中三元组均未在当前KG中出现过，可表示为

T_{\mathrm{n}}=\underset{(h,r,t)\in T,e\in E}{\cup }\{(e,r,t)\notin T\}\bigcup \{(h,r,e)\notin T\}（1）

2.2 负采样方法

Yang等^[19]从理论上证明在优化目标函数和减小方差时负采样与正采样同等重要，因此构建高质量负例三元组对提升知识图谱归纳链接预测的性能具有重要作用。本文方法假设语义相近实体替换正确三元组头或者尾实体构造的负例三元组质量更高。寻找语义相近实体的最简单方法是在每个训练步骤中计算特定实体与实体集合中所有实体之间的相似度。然而，这种方法消耗大量的计算资源，并且成本会随着实体集合的大小成比例增加。

知识图谱中具有相同关系的实体之间有某种相似性，同时距离相近的实体之间语义关系也更为近似。基于该思想，对候选集合的生成过程进行改进，提出基于相似性的负采样算法（Similarity-Based Negative Sampling, SNS），如算法1所示。

算法1 面向归纳链接预测的负采样算法

输入：训练三元组集合T_train={(h, r, t)},实体集合E，关系集合R，嵌入表示维度d，相似度计算函数sim(·)，每个正例三元组对应的负例三元组数量n，训练轮数大小m

输出：实体和关系的嵌入表示

1. 初始化训练集中实体e∈E和关系r∈R的嵌入表示

2. while 训练轮数＜m do

3. 采样 mini-batch T_batch∈T_train

4. while (h,r,t)∈T_batch do

5. 计算实体t的k跳邻接矩阵集合S_k

6. 使用相似度公式计算实体t和集合S_k 中实体的相似度

7. if \left|S_k\right|<n

8. 对S_k 中实体按照相似度进行降序排列，选取前n个构成负例三元组{(h,r,t_i^{\text{'}}),i=1,2,…,n}

9. else

10. 从实体集合E中随机选择\left(\left|S_k\right|-n\right)个实体构成负例三元组

11. 使用公式计算损失，更新实体和关系的表示

12. end while

13. end while

该方法由两部分组成，分别是候选集合生成和相似度计算。候选集合是指从实体集合E中选择出可以构成负例三元组的e，构成候选集合E_c。以生成三元组（h,r,t）对应的负例三元组为例，首先，将KG中三元组按照不同关系进行划分，得到关系r相关的所有三元组集合；其次，构建关系r对应的邻接矩阵 A_r，其中A_r [i][j]表示实体i和实体j之间存在关系r；最后，对于给定三元组（h,r,t），从邻接矩阵 A_r 中获取与头实体h或者尾实体t相关的k跳邻居集合 M =A_r^{k-\mathrm{1}}+A_r^k。

KG中包含大量实体，因此生成的k跳邻居集合 M 中实体数量也很多。为了进一步挑选出高质量的实体进行替换，将 M 中实体与原正例三元组中要替换实体进行相似度计算，并按照相似度得分进行降序排列，从中选取前m个实体进行替换形成高质量负例三元组。相似度采用余弦相似度，可表示为

\mathrm{s}\mathrm{i}\mathrm{m}(\mathit{e},\mathit{t})=\frac{\mathit{e}\times \mathit{t}}{\left|\mathit{e}\right|\times \left|\mathit{t}\right|}（2）

式中： e 表示实体e的嵌入表示； t 表示实体t的嵌入表示； e × t 表示两个向量的点积。

对于某些度很小的节点，存在候选集合中实体数量无法满足负例三元组的数量要求的情况，对于不足部分仍然采用随机采样方法进行补充。

2.3 损失函数

根据获取的正例三元组和负例三元组，采用知识图谱表示学习中常用的损失函数Hinge Loss进行模型训练，损失函数可表示为

L_{\mathrm{L}\mathrm{o}\mathrm{s}\mathrm{s}}={\displaystyle \sum _{i=\mathrm{1}}^{\left|N_{\mathrm{t}\mathrm{r}\mathrm{i}}\right|}}max\left(\mathrm{0},score\left(n_i\right)-score\left(p_i\right)+\gamma \right)（3）

式中：\left|N_{\mathrm{t}\mathrm{r}\mathrm{i}}\right|表示训练图中三元组数量；n_i 表示负例三元组；p_i 表示正例三元组；\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\left(n_i\right)和\mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}\left(p_i\right)分别表示负例三元组和正例三元组的得分；\gamma表示正则化参数。

该方法虽然避免了和实体集合中所有实体进行相似度计算，但k跳邻居候选集合的生成过程中需要进行矩阵的幂运算，时间复杂度为O(|v|³)log₂k，空间复杂度为O(|v|²)，与均匀随机采样算法相比，构建成本仍然较高。

3 实验

3.1 数据集

WN18数据集来源于大型的英语词汇数据库WordNet。该数据库同样包含大量的可逆关系，为了提高链接预测任务的准确度，删除WN18中的可逆关系，得到包含11种关系的WN18RR数据集。

FB15K数据集来源于FreeBase知识库，该数据库是一个包含关于世界一般事实的大型数据库，具有许多不同的关系类型。FB15K-237是FB15K的一个子集，通过删除FB15K中大量可逆关系数据创建。其中，15K表示数据集中有15 000个主题词，237表示共有237种关系。

为验证所提模型在全新图上的链接预测性能，采用GraiL中的数据集划分方法，对WN18RR和FB15K-237数据集进行划分。首先，从FB15K-237数据集中随机选取4个实体作为根节点；其次，对根节点周围k跳邻域节点合并来获得训练数据集；最后，从整个图中移除训练图中包含节点和边，在剩余图中使用相同的方法获取测试图。调整上述过程的参数，以获得一系列大小不断增加的图。将FB15K-237数据集按照数量递增的方式分为4份，训练集分别用V1、V2、V3、V4表示。对WN18RR数据集应用同样的方法获取训练集和测试集。数据集统计情况如表1所示，其中N_R、N_E、N_T分别表示数据集中关系、实体和三元组的数量。

3.2 评价指标

采用常用性能指标平均倒数排名（Mean Reciprocal Ranking, MRR）和命中率Hits@n对模型进行性能评估。MRR是指将测试集中所有三元组排名的倒数求平均，该指标越大越好，可表示为

R_{\mathrm{M}\mathrm{R}\mathrm{R}}=\frac{\mathrm{1}}{\left|S\right|}{\displaystyle \sum _{i=\mathrm{1}}^{\left|S\right|}}\frac{\mathrm{1}}{R_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\_i}}（4）

式中：S表示三元组集合；\left|S\right|表示三元组个数；R_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\_i}指第i个三元组的链接预测排名。Hits@n指的是在前n个结果中命中的概率，该指标越大越好，可表示为

P_{\mathrm{H}\mathrm{i}\mathrm{t}\mathrm{s}@n}=\frac{\mathrm{1}}{\left|S\right|}{\displaystyle \sum _{i=\mathrm{1}}^{\left|S\right|}}I(R_{rank\_i}\le n)（5）

式中，I(·)表示indicator函数，若条件为真则函数值为1，否则为0。一般n取1、3、5或者10。

3.3 实验设置

为验证SNS方法在归纳链接预测中的有效性，在归纳链接预测模型SNRI中采用SNS方法进行实验，并将随机负采样方法（SNRI模型）、NSCaching方法（SNRI_NSCaching模型）这两种负采样方法作为基线模型进行对比。实验代码使用Python实现，在配置GNU/Linux操作系统的服务器上完成，CPU配置为Intel Core i7-7700 3.60 GHz，128 GB内存，GPU为单个GeForce RTX 2080 Ti。模型基于PyTorch^[20]进行训练，采用Adam^[21]优化器进行优化，学习率初始值设置为0.001，训练轮次为10，批量大小为16。

3.4 实验结果分析

表2和表3分别为SNRI引入不同负采样方法在WN18RR和FB15K-237数据集上的实验结果。

1）与随机负采样方法相比，在FB15K-237的4个数据子集上，SNS模型均取得最优的MRR和Hits@1，MRR分别最高取得9.19、2.07、2.36、4.76个百分点的性能提升，Hits@1分别最高取得6.59、1.78、3.02、6.08个百分点的性能提升。在WN18RR的4个数据子集上，SNS模型均取得最优Hits@10，分别提升7.51、0.80、13.31、0.21个百分点。

2）与NSCaching方法相比，在FB15K-237的4个数据子集上，SNS模型均取得了最优的MRR和Hits@1，MRR分别取得了0.18、1.42、2.24、0.04个百分点的性能提升，Hits@1取得了0.25、2.61、3.30、0.22个百分点的性能提升。在WN18RR的4个数据子集上，SNS模型在其中3个子集上取得了最优MRR和Hits@1，MRR分别取得了2.80、9.19、1.47个百分点的提升，Hits@1分别取得3.20、8.35、2.35个百分点的提升。

3）在数据集WN18RR中，SNS模型在子集V1、V3上提高幅度较大，V2、V4提升幅度较小。在数据集FB15K-237中，4个子集中的提升幅度都较小，原因可能是这些提升较小的数据集中，SNS方法产生的候选实体数量不足，无法满足负样本数量需求，使用随机采样方法进行了补充。

总体来说，基于相似性的负采样方法提高了负样本的质量，显著提升了知识图谱中归纳链接预测的准确率。

3.5 参数敏感性分析

为分析获取候选集合时k跳半径对性能的影响，在WN18RR_V3数据集上，分别选择k为2、3、4和5来进行实验，如图1所示。

从图1可以看出，当k≤4时，随着k值增大，性能逐渐提高，k为5时性能开始下降。当k较小时，有可能获取到的负例三元组有限，因此模型中更多的是随机采样的负例三元组。当k≥5时，距离较远的实体语义相差较大，因此5跳以外实体构建的负例三元组可能为低质量负例三元组，从而降低链接预测的性能。

3.6 负样本质量分析

为验证SNS方法能生成高质量的负样本，在WN18RR数据集上进行案例分析。对于数据集中实体wheat，如果按照均匀随机采样方法，可替换实体集合为（lend, align, doodad, mismanage, semiconductor device）。如果按照SNS方法，更倾向于选择同一类型的实体进行替换，可替换实体集合为（wild rice, tabbouleh, barely, Bulgur, buckwheat）。

可以看出，本文提出的负采样方法在选择实体进行替换时，考虑了实体的类型和语义相似性，优先选择同类型或是在语义上相似、具有内在联系的实体作为替换对象，以生成高质量负样本。而传统的均匀随机采样方法大概率会采样到不属于同一类型或几乎完全不相关的实体作为替换对象，从而可能使模型在训练阶段面临零损失问题。

4 结束语

现有知识图谱中的归纳链接预测方法更多强调对知识图谱中目标关系周围子图的不同获取方法以及如何更加充分地利用子图信息和全局信息，未考虑负采样对归纳链接预测性能的影响。针对该问题，从邻近实体语义更相近，语义相近实体替换可以得到高质量负例三元组角度出发，首先获取每个实体的k跳邻居节点集合，然后从该集合中选取相似度高的实体进行负例三元组构建，解决了传统方法中负采样效果不理想的问题。尽管该方法筛选出了高质量负例三元组，一定程度上提高了归纳链接预测的性能，但是也存在某些负例三元组是伪负例的情况。这些伪负例的引入，削弱了模型的性能。如何从生成的负例三元组中自动识别出这些伪负例，是后续研究中需要关注的问题。

参考文献

[1] JI S X， PAN S R， CAMBRIA E， et al. A survey on knowledge graphs： representation， acquisition， and applications［J］. IEEE Transactions on Neural Networks and Learning Systems， 2021，33（2）：494-514.

[2] 杨大伟，周刚，卢记仓，基于知识表示学习的知识图谱补全研究综述［J］.信息工程大学学报，2021，22（5）：558-565.

[3] 梁新雨，司冠南，李建辛，面向知识图谱补全的归纳学习研究综述［J］.计算机科学与探索，2023，17（11）：2580-2604.

[4] 郭正山，左劼，段磊，面向知识超图链接预测的生成对抗负采样方法［J］.计算机研究与发展，2022，59（8）：1742-1756.

[5] DETTMERS T， MINERVINI P， STENETORP P， et al. Convolutional 2D knowledge graph embeddings［C］∥Proceedings of the 32nd AAAI Conference on Artificial Intelligence. Washington， USA： AAAI Press， 2018：1811-1818.

[6] TOUTANOVA K， CHEN D Q. Observed versus latent features for knowledge base and text inference［C］∥Proceedings of the 3rd Workshop on Continuous Vector Space Models and Their Compositionality. Stroudsburg， USA： ACL， 2015：57-66.

[7] GENG Y X， CHEN J Y， PAN J Z， et al. Relational message passing for fully inductive knowledge graph completion［C］∥Proceedings of the IEEE International Conference on Data Engineering. Piscataway， USA： IEEE， 2023：1221-1233.

[8] HAMAGUCHI T， OIWA H， SHIMBO M， et al. Knowledge transfer for out-of-knowledge-base entities： a graph neural network approach［C］∥Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. Washington， USA： AAAI Press， 2017：1802-1808.

[9] WANG P F， HAN J L， LI C L . et al . Logic attention based neighborhood aggregation for inductive knowledge graph embedding［C］∥Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. Washington， USA： AAAI Press， 2019：7152-7159.

[10] TERU K， DENIS E G， HAMILTON W L. Inductive relation prediction by subgraph reasoning［C］∥Proceedings of the 37th International Conference on Machine Learning. Red Hook， USA： Curran Associates Inc.， 2020：9448-9457.

[11] CHEN J J， HE H， WU F， et al. Topology-aware correlations between relations for inductive link prediction in knowledge graphs［C］∥Proceedings of the AAAI Conference on Artificial Intelligence. Washington， USA： AAAI Press， 2021：6271-6278.

[12] MAI S J， ZHENG S J， YANG Y D， et al. Communicative message passing for inductive relation reasoning［C］∥Proceedings of the AAAI Conference on Artificial Intelligence. Washington， USA： AAAI Press， 2021：4294-4302.

[13] XU X H， ZHANG P， HE Y Q， et al. Subgraph neighboring relations infomax for inductive link prediction on knowledge graphs［DB/OL］. （2022-08-26）［2024-05-13］.

[14] BORDES A， USUNIER N， GARCIA DURAN， et al. Translating embeddings for modeling multi-relational data［C］∥Proceedings of the 26th International Conference on Neural Information Processing Systems. Red Hook， USA： Curran Associates Inc.， 2013：2787-2795.

基金资助

国家自然科学基金(62172433)