ICLR 2024 | 理解图神经网络在规则学习中的表达能力

©PaperWeekly 原创 · 作者 | 卡梅

单位 | 清华大学

引言

规则有着逻辑清晰和高度可解释的推理过程，在确保模型决策的可靠性和可信度方面发挥着至关重要的作用。尽管在过去两年内，大语言模型在许多任务上表现出了强大的推理能力，但它们在处理图数据时的理解深度和决策可靠性仍然有待提升。因此，深入研究并理解图神经网络的规则学习能力对于确保图数据处理的可信性和可靠性具有重要意义。

本文旨在填补当前对于 GNN 在规则学习中的表达能力缺乏理论认识的空白。通过对 GNN 的表达能力进行深入分析，从理论上阐述它们能够学习的规则结构，并在此基础上提出了一种新的标记策略，通过优化 GNN 的输入，使得它们可以学习更广泛的规则结构，从而提高了知识图谱推理的准确性。

▲ 图1. 知识图谱中三元组的存在取决于相应的规则结构

我们研究了用于知识图谱推理的 GNN（即 QL-GNN）可以学习哪种规则结构，并提出了 EL-GNN，它可以比 QL-GNN 学习更多的规则结构。

收录会议：

UNDERSTANDING EXPRESSIVITY OF GNN IN RULE LEARNING, ICLR 2024

论文链接：

https://openreview.net/pdf?id=43cYe4oogi

代码链接：

https: //github.com/LARS-research/Rule-learning-expressivity

核心思想

本文的核心思想是通过对采用尾实体评分的图神经网络（GNN）在规则学习中的表达能力进行深入分析，揭示其理论基础，并提出新的标注策略以提高推理性能。这一研究丰富了对于 GNN 在规则学习中的理论理解，为知识图谱推理的进一步发展提供了新的思路和方法。

2.1 QL-GNN的逻辑表达能力

我们首先将这些 GNN 统一到一个通用的框架中，命名为 QL-GNN。QL-GNN 的特点是使用尾实体评分来对三元组进行打分，并从具有相同模式的子图中提取规则结构，QL-GNN 包含了 SOTA 的知识图谱推理算法，例如 RED-GNN 和 NBFNet 等。

QL-GNN 可以学习的规则结构由一种称为分级模态逻辑 (CML) 的逻辑语言描述 (De Rijke, 2000; Otto，2019）。CML 通过递归定义，基本元素包括常数、变量、一元谓词 Pi(x) 以及递归规则：如果是 CML 中的公式，则也是 CML 中的公式。

由于 QL-GNN 将常数引入查询实体 , 我们使用 CML[G, h] 表示从中的基本元素和常数（等价于常数谓词）递归构建的 CML。以下定理和推论展示了 QL-GNN 的逻辑表达能力：

定理：对于知识图谱推理, 给定查询 (, ?), 如果 QL-GNN 学习到规则公式，那么是 CML[G, h] 中的公式。

推论：OL-GNN 学习到的规则结构可以由以下递归构造：

基本规则：所有一元谓词可以被 QL-GNN 学习；常数谓词可以被 QL-GNN 学习；
递归规则：如果规则结构被 QL-GNN 学习，那么也可以被 QL-GNN 学习。

与以往基于图同构测试的分析方法不同，本文采用了对图中规则结构进行形式化描述的方法。这种新的分析工具能够更好地理解 QL-GNN 所学习到的规则，并揭示 QL-GNN 在训练中可以泛化的最大表达能力。图 2 展示了 QL-GNN 可以学习的规则结构。

基于逻辑工具，本文得到了传统的知识图谱推理 GNN，例如 CompGCN 的规则学习能力：

定理：对于知识图谱推理，CompGCN 能够学习到规则公式，其中是一个包含来自子公式和的公式。

▲ 图2. QL-GNN可以学习的规则结构及其对应的规则公式示例

2.2 基于规则公式转换的实体标注EL-GNN

QL-GNN 在学习规则结构方面还是存在一些不足之处，为了改进其学习能力，我们提出了一种新的标注策略 EL-GNN，以在知识图谱推理中学习更多的规则。这种标注策略通过优化 GNN 的输入，使得它们可以学习更广泛的规则结构，从而提高了知识图谱推理的准确性。以下命题和推论展示了如何向规则结构添加常数，使其可以用 CML 中的公式描述，以及如何应用标注技巧使其可被 QL-GNN 学习。

命题：假设描述了一个在中单连通的规则结构。如果我们将常数分配给 G 中所有出度大于 1 的个实体，那么规则结构可以用一个新的规则公式在中描述。

推论：在上述命题中，对于被分配了常数的实体应用带有唯一初始表示的标注技巧，规则结构可以被 QL-GNN 学习到。

实体标注 EL-GNN 算法表示如下，它为所有出度大于 d 的实体分配常数，度阈值 d 根据 GNN 的表达能力和泛化能力进行调整。EL-GNN 选择度阈值 d 作为超参数，因为较小的 d（如 1）会向图中引入过多的常数，从而阻碍了 GNN 的泛化能力。

实验结果

本文基于合成数据集和真实数据集，对各种 GNN 的表达能力进行实验评估，验证了相关理论的正确性。同时，针对真实数据集，提出的 EL-GNN 方法也取得了显著的性能提升。这些实验结果进一步证明了本文所提出方法的有效性。

3.1 合成数据集上的实验

该数据集包含了不同模式的规则结构以及相应的三元组。我们评估不同方法在学习规则结构方面的能力。如表 1，与传统方法相比，QL-GNN 在学习规则结构方面表现出显著优势，能够更准确地提取和表示规则。在数据集 U 上，EL-GNN 又比 QL-GNN 进一步提供更准确的推理结果。

▲ 表1. 不同方法在合成数据集上的准确性

图 3 展示了在数据集 U 上，出度阈值 d 对 EL-GNN 的影响，过大过小的出度阈值都会影响 EL-GNN 的性能。

▲ 图3. EL-GNN在数据集U上的准确率与出度阈值d的关系

3.2 真实数据集上的实验

在四个实际数据集上测试 EL-GNN 的有效性：Family (Kok & Domingos, 2007)，Kinship (Hinton et al., 1986)，UMLS (Kok & Domingos, 2007)，WN18RR (Dettmers et al., 2017)，和 FB15k-237 (Toutanova & Chen, 2015)。表 2 展示了实验结果，EL 算法提高了 RED-GNN 和 NBFNet 在实际数据集上的准确性。

▲ 表2. 实际数据集上的准确性和标准差，最好的（和相对最好） “粗体”，第二（和相对第二）是下划线。

总体而言，实验结果与我们的理论分析一致，证明了我们提出的方法在规则学习和知识图谱推理任务中的有效性。实验结果进一步支持了我们对于采用尾实体评分的 GNN 在规则学习中的表达能力的理论理解。

未来工作

本文分析了 GNN 在知识图谱推理中学习规则的表达能力，给出了 GNN 可以学习的规则结构，并提出一种有效的标注方法来提高 GNN 的表达能力。未来，我们将扩展我们的分析到使用一般标注技巧的 GNN，以研究它们在学习更复杂规则结构方面的表现。此外，还将尝试从训练好的 GNN 中提取可解释的规则结构，以提高模型的可解释性。

参考文献

[1] Yongqi Zhang and Quanming Yao. Knowledge graph reasoning with relational digraph. In Interna- tional World Wide Web Conference, 2022.

[2] Yongqi Zhang, Zhanke Zhou, Quanming Yao, Xiaowen Chu, and Bo Han. Adaprop: Learning adaptive propagation for graph neural network based knowledge graph reasoning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3446–3457, 2023.

[3] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 2021.

[4] Zhaocheng Zhu, Xinyu Yuan, Mikhail Galkin, Sophie Xhonneux, Ming Zhang, Maxime Gazeau, and Jian Tang. A*net: A scalable path-based reasoning approach for knowledge graphs. arXiv preprint arXiv:2206.04798, 2022.

更多阅读