ILP-SAGE：一种用于可扩展归纳链接预测的基于采样的框架

《Neurocomputing》：ILP-SAGE: A Sampling-Based Framework for Scalable Inductive Link Prediction

　　穆罕默德·拉希米|阿夫萨内·法特米|艾哈迈德·巴拉尼
伊朗伊斯法罕大学计算机工程系，伊斯法罕

摘要
链接预测是推断知识图中缺失事实的一项基础技术。在归纳框架下，它旨在预测训练过程中未出现节点之间的关系，因此对于动态和大规模应用尤为有用。尽管基于图神经网络的方法是一种常见途径，但它们往往存在两个主要缺陷：过度平滑问题，以及随着邻域深度增加而带来的高计算成本，这限制了它们的可扩展性；此外，针对非英语数据集的严格评估不足，使得其跨语言泛化能力存疑。为解决这些挑战，我们提出了ILP-SAGE这一用于归纳链接预测的新框架。ILP-SAGE采用列式数据存储方案，以便图网络快速进行子图采样和高效处理。通过可控的随机采样机制筛选出相关子图，再利用基于GraphSAGE的模型将其编码为节点嵌入。这种设计有助于控制图结构的扩展，并生成能够有效结合结构信息和特征信息的嵌入，从而在保证准确性的同时提升计算效率。我们使用来自知名英语数据集WN18RR、FB15K-237和NELL-995，以及波斯语数据集PersianILP的27个基准测试（13个演绎型，14个归纳型）对ILP-SAGE进行了全面评估。实验结果表明，ILP-SAGE在显著降低运行时间的同时，仍能保持较强的预测性能。例如，在NELL-995数据集的第4版本上，该框架的AUC-PR值比现有最先进方法高出3.52点，且与GraIL相比，训练时间从1705.5分钟缩短至2.28分钟。这些结果证明了该框架适用于大型、异构且多语言的知识图谱中的精确且可扩展的链接预测。完整源代码和文档可通过以下地址获取：https://github.com/mohammadRahimi1993/ILP_SAGE

引言
在现代信息技术中，如何高效处理结构化、半结构化和非结构化的大规模数据是一项关键挑战。在此背景下，知识图谱日益被视为组织、存储和推理复杂数据的强大工具。通过建模实体及其之间的关系，知识图谱能够实现对信息的有意义分析。它们已被广泛应用于智能系统，包括问答系统[1]、信息检索系统[2]以及推荐系统[3]。

知识图谱面临诸多重大挑战，其中包括实体的语义模糊性[4]、处理和存储方面的动态性与可扩展性问题[5]，以及图的稀疏性[6]。此外，数据不平衡、固有偏见、异构数据源的整合以及信息质量的一致性评估也是亟待解决的问题。其中一个核心问题在于多义词的语义模糊性——Weiss等人曾运用基于知识图谱的方法来解决短文本中的这一问题[4]。此外，为了使知识图谱与不断变化的数据保持一致，还需要具备检测和解决语义及结构冲突的机制。数据偏差也可能导致不准确的推理，因此维护数据集的多样性和平衡性至关重要。随着知识图谱规模的扩大，可扩展性和计算资源消耗问题愈发突出。在这方面，Tang等人提出了一种用于知识图谱智能同步和更新的模型[5]。最后，实体间关系的不完整性会降低推理算法的性能。为解决这一问题，人们引入了链接预测等方法来辅助完成知识图谱的构建。本研究探讨了该领域的一个关键挑战，并提出了针对性的解决方案。

近年来，知识图谱中的链接预测在提升智能系统性能方面发挥了重要作用。这项技术已被广泛应用于搜索引擎、推荐系统、自然语言处理、社交网络分析以及知识发现等领域。例如，在搜索引擎中，链接预测通过揭示数据实体间的隐含关系，有助于提高页面排名和内容推荐效果；在推荐系统中，它能实现更精准、个性化的建议；在社交网络中，则有助于识别用户互动模式并发现具有影响力的社群。

根据其在新环境中的泛化能力，链接预测模型可分为两类：演绎型和归纳型。在演绎型链接预测中，模型能够推断训练过程中已观察到的节点之间的关系；而归纳型链接预测则能够估算涉及此前未见过节点的链接[7]。这一特性使得归纳型模型特别适合于数据持续更新的动态环境。根据现有研究在链接预测领域所采用的演绎或归纳框架，链接预测方法通常可分为三类：基于规则的方法、基于子图提取的方法以及基于嵌入的方法。在基于嵌入的方法中，知识图谱中编码的信息会被映射为低维向量表示；基于规则的方法则通过利用从训练图中提取的规则来推断新关系；而基于子图提取的方法则侧重于目标节点周围的局部邻域，提取相关子图，然后基于这些子图进行归纳型链接预测。为阐明二者差异，文中通过一个示例展示了基于规则的方法与基于子图提取的方法之间的区别。图1展示了通过子图提取来预测David和Robert之间链接的示例，同时也展示了基于规则的方法用于预测Alic和David之间链接的情况。

像GraIL[7]这类基于子图提取的方法，或是那些利用线图的方法（如GRelGT[6]），在归纳型链接预测方面存在局限性。首先，在基于子图的方法中，随着邻域深度的增加，过度平滑问题会愈发严重，从而导致特征嵌入的质量下降。其次，构建线图或提取子图的过程往往会导致子图规模呈指数级增长，这就带来了巨大的计算和内存开销。在处理大规模图谱时，这一问题更为突出。一些关于归纳型链接预测的研究[8]、[9]、[10]试图降低计算复杂度，但由于这些方法仅适用于时间序列知识图谱或药物发现等特定领域，其在静态知识图谱上的泛化能力仍需验证。此外，像LCILP[11]这样的方法试图通过选择信息含量最高的节点来提取更为紧凑高效的子图，但这些方法并未显著降低运行时间。另一方面，尽管GRelGT[6]等新兴方法在预测精度方面表现良好，但其较高的计算复杂度使其不适合需要高效处理和持续更新的大型动态知识图谱。另外，大多数现有方法仅在英语数据集上进行了评估，它们在其他语言数据集上的表现，包括波斯语数据集，仍不清楚。因此，开发一种能够在保持准确性的同时降低计算成本，并且能够处理如PersianILP[12]这类波斯语数据集的高效框架，是该领域亟需解决的研究课题。

在本研究中，我们提出了一种名为ILP-SAGE的新框架，旨在提升归纳型链接预测的采样效率。该框架通过可控的随机采样来选择目标子图，这样随着图深度的增加，样本数量会逐渐减少，从而有效避免子图规模的指数级增长。在图数据存储方面，该框架采用了优化的列式数据结构，大大加快了采样速度并降低了内存开销。在嵌入阶段，该框架采用了GraphSAGE架构，包括两个用于特征提取的图卷积层1和一个用于最终输出预测的多层感知器2。模型输入包括节点特征向量以及一组采样得到的子图。在每一层中，节点特征都会通过均值聚合器利用邻域信息进行更新。最终，每个节点在经过两个SAGEConv层处理并应用ReLU激活函数后，其嵌入向量会被输入到多层感知器中，从而生成最终预测结果。

实验结果表明，ILP-SAGE框架在保持较高预测准确性的同时，显著降低了计算运行时间，实现了预测性能与效率的平衡。它能够以低于传统方法的成本实现高效的归纳型链接预测。ILP-SAGE的一个显著优势在于它支持多语言数据，包括波斯语，因此非常适合用于大型动态知识图谱。本研究旨在提升在不断变化的数据环境中的链接预测能力，帮助发现潜在关系，从而为搜索引擎和推荐系统等下游应用带来益处。ILP-SAGE具有三大优势：（1）与呈指数增长的K跳采样相比，它的内存和计算复杂度更低；（2）通过可控采样避免了过度平滑问题；（3）具备多语言处理能力，尤其适用于波斯语。在WN18RR、Freebase、NELL以及PersianILP数据集上的评估表明，ILP-SAGE在保持准确性的同时，提升了归纳型和演绎型预测的处理速度和效率。这些结果证明了该框架适用于频繁更新的多语言知识图谱。

本研究的主要创新点如下：
1. 我们开发了一种名为ILP-SAGE的新型多语言归纳框架，用于解决归纳型链接预测问题。该框架将可控随机采样机制与GraphSAGE架构相结合，使得能够在围绕目标节点的较少样本中提取局部子图。这种设计有助于通过GraphSAGE生成更丰富的嵌入，进而提升分类准确率和链接排序质量。
2. 该框架采用了高性能的列式数据结构，用于图数据的存储和压缩。这种结构显著降低了图访问时间和遍历延迟，从而提升了整体系统效率。
3. 我们通过对各种归纳型和演绎型基准数据集进行大量实验，对所提出的框架进行了评估。实验结果表明，随着节点平均度数的增加，该模型在AUC-PR和Hits@10指标上的性能都会提升。该框架在PersianILP数据集的演绎型和半归纳型版本上也能取得优异成绩。此外，与GraIL和GRelGT等现有方法相比，ILP-SAGE在运行效率和计算开销方面具有明显优势。例如，在归纳型WN18RR数据集的第3版本中，其训练时间从652.8分钟降至2.66分钟，推理时间从200.2分钟降至0.01分钟，显示出极大的计算效率提升。

本文的结构如下：第2节对相关研究和先前工作进行了全面综述；第3节给出了正式定义并阐述了问题背景，为后续研究奠定概念基础；第4节介绍了为弥补现有研究缺口而提出的方法，并对其各组成部分进行了深入分析；第5节详细阐述了本文提出的算法及其分析复杂性；第6节介绍了评估标准以及实验中使用的基准数据集，随后对实验结果进行了详细讨论和解读；最后，第7节总结了全文，并探讨了未来研究的方向。

相关文献
链接预测主要应用于两种类型的知识图谱补全任务：文本型和多模态型。在文本型知识图谱中，所有实体仅以文本形式表示；而在多模态知识图谱中，节点可能包含文本和视觉数据。APKGC[13]和AdaMKGC[14]是最近提出的两种用于多模态知识图谱补全的方法。在APKGC中，Jian等人通过可控的噪声注入和注意力机制来处理多模态数据中的噪声。

理论背景与问题阐述
本节首先介绍与归纳型链接预测相关的基本概念和定义，随后阐述研究问题。

框架结构
图4展示了ILP-SAGE框架用于归纳型链接预测的各个模块。在第一个模块中，知识图谱的三元组被转换为DGL3格式，以便图神经网络进行处理。同时，这些三元组也以列式格式存储，便于高效采样。在第二个模块中，根据正样本的结构特征生成负样本，从而使模型能够区分有效关系与……

ILP-SAGE的算法设计
本节介绍了支撑ILP-SAGE框架用于知识图谱归纳型链接预测的算法。算法1（见图5）展示了ILP-SAGE框架的工作流程。第一步是将数据集中的三元组转换为与DGL库兼容的结构；第二步是将数据以列式格式存储，以便高效采样；第三步是为采样选择种子节点。

数据集描述与探索性分析
为评估链接预测模型的归纳预测能力，我们使用了来自四个知识图谱的数据集——Freebase、WordNet、NELL和FarsBase。前三个知识图谱为英语格式，而FarsBase知识图谱则为波斯语格式。WN18RR数据集取自WordNet词汇数据库，该数据库是一个结构化的存储系统，它将英语词汇按同义词集合进行组织，并通过各种语义关系相互关联[40]。FB15k-237则是……结论与未来工作近年来，已有诸如LCILP[24]和GRelGT[6]等方法被提出用于知识图谱中的归纳链接预测。尽管这些方法具有较高的准确性，但在大规模应用时因其高昂的计算成本而存在局限性。本研究引入了一种名为ILP-SAGE的新框架，它在显著减少训练和推理时间的同时，相较于以往方法在传递式和归纳式任务上实现了更高的准确性。CRediT作者贡献声明穆罕默德·拉希米：撰写初稿。阿夫萨内·法特米：指导。艾哈迈德·巴拉尼：指导。利益冲突声明作者声明不存在任何可能影响本文所述工作的已知财务利益或个人关系。穆罕默德·拉希米目前是伊朗伊斯法罕大学计算机工程学院的软件工程专业博士候选人。他于2021年获得伊朗科学技术大学努尔校区的硕士学位，2016年则从伊朗沙赫雷科尔德的帕亚梅努尔大学获得学士学位。他的研究兴趣集中在语义网、深度学习、自然语言处理、数据挖掘以及软件建模领域。