从单调图神经网络到数据图,再回到单调图神经网络:表达能力与实际应用
《Artificial Intelligence》:From Monotonic Graph Neural Networks to Datalog and Back: Expressive Power and Practical Applications
【字体:
大
中
小
】
时间:2026年04月27日
来源:Artificial Intelligence 4.6
编辑推荐:
大卫·特纳·库卡拉|贝尔纳多·库恩卡·格劳|鲍里斯·莫蒂克|埃戈尔·V·科斯提列夫
英国牛津大学计算机科学系
**摘要**
许多在知识图谱上的任务,如链接预测,可以被概念化为学习关系事实集合的转换问题。机器学习模型(如图神经网络GNN)可以用来实现这种转换,从而从示
大卫·特纳·库卡拉|贝尔纳多·库恩卡·格劳|鲍里斯·莫蒂克|埃戈尔·V·科斯提列夫
英国牛津大学计算机科学系
**摘要**
许多在知识图谱上的任务,如链接预测,可以被概念化为学习关系事实集合的转换问题。机器学习模型(如图神经网络GNN)可以用来实现这种转换,从而从示例中学习转换规则。然而,通常很难正式验证这种转换的性质,或者理解为什么它能得出特定的事实。或者,这种转换可以使用如Datalog这样的知识表示语言来表达的一组规则来实现。这种转换的形式性质可以通过符号手段进行验证,每个推导出的事实都可以通过规则来证明;然而,编写和整理这些规则既费时又需要应用领域和形式语言的专业知识。为了弥合这两种方法之间的差距,本文研究了由单调最大-和GNN实现的转换与由Datalog规则实现的转换之间的关系。首先,我们提供了一个算法,可以验证给定的Datalog规则对于一个网络来说是否是合理的,即GNN总是能从任何输入数据集中推导出规则的所有结果。其次,我们提供了一个算法,可以通过计算一个对GNN合理的规则来证明GNN推导出的任何事实。第三,我们研究了单调最大-和GNN的表达能力,并表明对于每个这样的GNN,都可以计算出一个Datalog程序,该程序将GNN应用于任何数据集时产生的结果与程序规则单轮应用的结果相同;我们还将结果具体化到仅使用最大聚合函数的单调最大GNN子类,并确定了一个相应的Datalog程序类。最后,我们进行了实际评估,表明单调最大-和GNN可以在常见的知识图谱任务上成功训练,从最大-和GNN中提取规则在实践中是可行的。
**引言**
许多在知识图谱(KG)上的任务,如KG完成[1]、节点分类[2]、问题回答[3]和推荐[4],可以被概念化为对包含关系事实的数据集的转换。例如,在推荐系统中,我们可以将用户-项目交互和相关背景知识表示为一组事实[5],然后系统可以将这个数据集转换为另一个包含推荐用户-项目交互的数据集。机器学习(ML)模型越来越多地被用来从示例中诱导这些转换:这样做比手动指定转换更经济高效,并且不需要领域专业知识。为此目的已经提出了许多类型的模型,如循环网络[6]、纤维网络[7]和前馈网络[8]、模拟前向[9]、[10]和后向链式[11]的架构,以及用于规则学习的架构[12]、[13]。最近,图神经网络(GNN)[14]作为处理图数据的ML模型被开发出来。GNN的推理是排列不变的(对于图级输出)和排列等变的(对于节点级输出):将GNN应用于两个同构图总是产生相同的输出,无论顶点如何标记。当目标是独立于图顶点的身份分析图结构时,这些属性是非常理想的。数据集转换通常也期望具有类似的属性。例如,如果两个不同的用户以完全相同的方式与不同的项目集互动,可以合理地期望使用相同的一般规则来生成推荐。因此,基于GNN的数据集转换最近受到了相当多的关注[15]、[16]、[17]、[18]、[19]、[20]、[21]、[22]、[23]。
在这种应用中的一个关键问题是理解所使用的ML模型的表达能力——即描述模型可以计算的数据集转换类别。在传统的任务管理任务中,如查询回答和逻辑推理中,表达能力通常是通过识别实现与正在研究的任务相同转换类别的基于逻辑的语言来确定的。例如,关系和图查询语言的核心方面已经使用一阶逻辑的片段进行了表征[5]、[24],并且已经使用基于规则的Datalog语言描述了RDF数据集上的逻辑演绎[25]。这种对应关系使得不同数据管理语言的严格理解和比较成为可能。因此,描述ML模型用于数据管理的表达能力越来越重要,计算逻辑提供了一种成熟的方法论:可以描述在什么条件下,基于ML的数据集转换等同于某种逻辑形式主义,即将基于ML的转换应用于任意数据集产生的结果与应用该形式主义的特定公式产生的结果相同。在一项开创性的研究中[26]表明,每个可以用一阶逻辑表达的GNN诱导的转换都等同于ALCQ描述逻辑[27]的概念查询——这是一种流行的KR形式主义。[28]为具有专用顶点和颜色的GNN类证明了类似的结果,[29]通过展示在非常温和的限制下,GNN诱导的转换可以被带有计数项的受保护的一阶逻辑片段GFO+C捕获而推广了这些结果。[30]和[31]表明GNN可以表达某些类型的图同构测试,例如一维Weisfeiler–Leman测试。[32]使用一种混合语言描述了GNN的表达能力,其中每个逻辑公式都附带了一个张量。最后,[33]使用带有Presburger量词的各种逻辑描述了几类具有有理系数的GNN的表达能力。
使用基于逻辑的形式主义来描述ML模型类别还有潜力解决解释模型预测的关键实际挑战。Datalog似乎特别适合这一目的。在Datalog中,可以使用“如果-那么”规则来捕获特定领域的知识,这些规则可以应用于一组事实以推导出新结论。此外,任何Datalog推理都可以使用描述从输入数据集推导出事实所需的所有步骤的证明来解释。这种严格但人类可读的解释有助于建立对系统预测的信任,确保符合规范,并能够验证公平标准。例如,在推荐应用中,可以使用事实Author(Dostoevsky,Crime_and_Punishment) 和 Author(Dostoevsky,The_Idiot)来捕获关于文学的领域知识,然后可以使用事实Likes(Crime_and_Punishment)来表示用户与系统的过去交互。系统随后可以学习一个ML模型,将该事实转换为使用事实Recommend(The_Idiot)表示的推荐。解释这些推荐的一种可能方法是提取与模型相对应的Datalog规则。例如,如果可以证明模型产生的结论与规则(1)相同,那么可以通过显示它是通过将规则(1)应用于背景知识和过去交互来得出的事实来解释推荐:Author(x,y1)∧Author(x,y2)∧Likes(y1)→Recommend(y2)。
在本文中,我们介绍了一类新的基于GNN的数据集转换,这些转换可以像通常一样从示例中训练得到,但其表达能力可以使用Datalog来表征。此外,我们提出了实用的算法,可以从任何这样的转换中提取一组等效的规则。GNN通常分三个阶段应用于数据集。首先,输入数据集被编码成一个图,其顶点用数字特征向量标记。其次,这个图由具有多个层的GNN处理;在每一层中,特征向量根据模型参数和前一层的特征向量进行更新。最后,输出层的向量被解码为输出数据集。我们的转换类似,但这些阶段经过精心设计,以确保整个转换总是可以使用规则来符号化描述。
为了实现这一目标,我们遇到了两个关键障碍。首先,整个转换的表达能力显然取决于编码和解码步骤,这可能会使得隔离ML模型的贡献变得困难。作为解决方案,在第3节中,我们采用了一种对转换的表达能力影响最小的规范编码:规范编码产生的图的结构紧密反映了输入数据集的结构。规范编码的变体已经由[15]、[26]和[16]考虑过。我们还引入了合理性和完整性的自然概念:如果对于每个数据集,将程序应用于数据集一次(即不需要固定点迭代)分别产生使用规范编码的GNN获得的事实的子集或超集,则Datalog程序(即一组规则)对于GNN来说是合理的或完整的。我们还说,如果一个程序对于GNN来说既是合理的也是完整的,那么它就等同于GNN。最后,我们观察到文献中提出的非规范编码(如[30]或[17]的编码)可以使用Datalog的扩展来描述,因此可以组合相关的Datalog程序来表征基于这些编码的转换的表达能力。
其次,GNN和Datalog的表达能力似乎存在根本差异。与GNN不同,Datalog只能实现单调转换,这意味着向输入中添加事实总是会在输出中产生额外的事实——也就是说,添加事实不能使现有规则的结论无效。此外,GNN通常使用求和来聚合输入图中给定顶点所有相邻顶点的特征向量。输入中相邻顶点的数量是无限的(即,顶点可以拥有的邻居数量没有先验限制),因此求和结果也是无限的;因此,任意多的顶点都可能影响是否推导出事实。这似乎与Datalog的根本原则相矛盾:在应用Datalog规则时需要共同考虑的常量数量由规则变量的数量决定,而不是由输入数据集的结构决定。因此,乍一看,人们可能会认为使用求和的GNN与Datalog规则根本不同。作为解决方案,在第4节中,我们引入了一类单调最大-和GNN,它们允许在每一层中使用最大或求和聚合函数;然而,矩阵权重必须是非负的,激活和分类函数需要满足某些限制(允许ReLU和阈值函数,但不允许sigmoid和ELU)。最大-和GNN的设计确保了结果转换在单射同态下是单调的,并且我们能够证明可以用只对有限数量元素求和的聚合函数替换每个求和聚合函数,而不影响模型在任何数据集上的输出。这些观察足以使基于最大-和GNN的数据集转换的表达能力与Datalog的表达能力一致。我们还引入了只允许在所有层中使用最大聚合的单调最大GNN。
在第5节中,我们表征了单调最大-和GNN的Datalog规则的合理性——即,我们给出了Datalog规则对于单调最大-和GNN来说合理的必要和充分条件。此外,我们还为单调最大GNN提供了类似的具体表征,这些表征后来被用于开发实际的合理性检查。在第6节中,我们证明了对于单调最大-和GNN在输入数据集上推导出的每个事实,我们可以通过计算一个特定树状形状的Datalog规则来解释其推导过程,该规则可能包含不等式,并且对于GNN是合理的,并且可以在一轮规则应用中从数据集中推导出该事实。此外,我们提出了一个实用算法,可以从输入数据集和GNN在这个数据集上产生的事实中计算出这样的规则。在第7节中,我们展示了每个单调最大-和GNN等同于一个可以从GNN本身算法计算的Datalog程序。这样的程序可以是递归的,因为相同的谓词可以出现在规则体和头部;然而,我们的等价概念不涉及固定点迭代(即,程序的规则只应用一次)。这个结果很有趣,因为它需要以一种能保证终止的方式,枚举来自可能无限的实数值候选特征值集合的元素。我们还展示了对于单调最大GNN来说,考虑没有不等式的Datalog树状程序就足够了,这反过来可以简化规则提取过程。在第8节中,我们提出了几种从单调最大GNN中提取等价Datalog程序的算法优化方法。这些优化方法有效减少了相关规则的搜索空间,同时它们倾向于产生更简洁的规则——也就是说,规则中的主体原子更少。在第9节中,我们证明了单调最大GNN可以通过树状Datalog程序来精确描述:不仅每个这样的GNN都等同于第7节中的树状Datalog程序,而且反过来也成立,即对于每个树状Datalog程序,都存在一个等价的单调最大GNN。在第10节中,我们展示了在多个知识图谱补全基准测试上评估单调最大和GNN的结果。我们的结果表明,最大和GNN在这项任务上的性能与最先进的方法相当或更优越。此外,我们还展示了第6节中的算法可以快速提取出解释模型推导出的事实的简短而简单的规则。最后,对于我们的某些模型,我们展示了第8节中的优化算法可以提取出一个与GNN等价的程序。因此,单调最大和GNN与现有的归纳式知识图谱补全技术具有竞争力,但额外的好处是模型的预测可以使用逻辑规则来完全解释。
本文扩展了我们在KR 2023会议上发布的早期工作[34]。新结果包括用于提取解释单个事实推理规则的算法、用于提取等价Datalog程序的优化算法、对几种非标准编码方案的讨论、对最大和GNN及其规则提取算法的经验评估,以及所有技术结果的详细和修订后的证明。
**初步内容**
在本节中,我们回顾了本文所基于的一阶规则、Datalog和图神经网络(GNN)的基本定义。
**编码/解码方案**
为了使用GNN实现数据集转换,我们首先必须将输入数据集编码成GNN可以直接处理的图,然后再次将GNN的输出解码回数据集。文献中提出了几种编码/解码方案,它们的细节差异很大。因此,在使用逻辑描述基于GNN的数据集转换时,很难理解哪些属性是由于所选择的编码方案引起的。
**具有最大和聚合的单调GNN**
在本节中,我们介绍了单调最大和GNN。我们定义的一个关键特点是使用了最大-k和聚合函数,该函数概括了最大和聚合。
**定义5**
对于每个k∈N0∪{∞},每个非负实数的有限多重集S∈F(R0+),以及?=min(k,|S|),定义max-k-sum(S)为:
- 如果?=0,则max-k-sum(S)={0};
- 否则,max-k-sum(S)={∑i=1? si | si是S中第?大的元素}。
在这个定义中,每个数字的出现都被单独计数;例如,max-3-sum({0,1,1,2,2,2,5})=9,因为S中最大的三个数字是2、2和5。
**检查规则的正确性**
在本节中,我们提出了一种方法来检查一个不含常量的Datalog规则是否对于单调最大和GNN是正确的。例如,我们可以验证第1节中的推荐系统是否推荐用户喜欢其其他书籍的作者所写的书籍——这一属性由规则(1)表达。我们的方法适用于实际应用。此外,在接下来的几节中,我们将介绍几种从单调最大和GNN中提取等价程序的算法。
**解释特定推理**
为了计算一个与单调最大和GNN等价的Datalog程序,在本节中,我们专注于解释GNN在特定数据集上的推理过程——即,给定一个单调最大和(Col,δ)-GNN N、一个(Col,δ)-数据集D以及一个事实Ui(a)∈TN(D),我们展示了如何构造一个对N来说正确的Datalog规则r,并确保Ui(a)属于Tr(D)。
除非我们限制r的句法结构,否则这个问题可以很容易地解决:我们让D′是通过替换D得到的合取。
**单调最大和GNN与Datalog程序的等价性**
在本节中,我们展示了每个单调最大和GNN都等同于一个由树状Datalog程序组成的程序。为此,在第7.1节中,我们展示了对于每个具有无界聚合函数的单调最大和GNN,都存在一个仅使用有界聚合函数的等价GNN。接下来,在第7.2节中,我们展示了这些聚合界限可以从GNN的参数中计算得出。最后,在第7.3节中,我们展示了如何从GNN中提取一个等价的Datalog程序。
**从单调最大GNN中提取等价Datalog程序的实用方法**
在本节中,我们提出了一种从单调最大GNN中提取等价Datalog程序的优化实用算法。这些基本原则也可以扩展到单调最大和GNN,但由于命题2中的正确性检查必须考虑大量的替换,因此得到的方法可能仍然不切实际。
设N是一个具有L层(维度分别为δ0,?,δL)的单调最大(Col,δ)-GNN,且δN=max(δ0,?,δL)。我们的优化算法遵循基本原则。
**单调最大GNN的完整表征**
现在我们补充了第7节的结果,并展示了对于单调最大GNN也是如此:对于每个没有不等式的树状Datalog程序,如果该程序由一元谓词U1,?,Uδ和二元谓词Ec组成(c∈Col),我们可以构造一个等价的单调最大GNN。为此,在本节的其余部分,我们固定了一个由(d, f)-树状规则组成的程序,其中不包含不等式。为了确保该程序可以与GNN等价,
**评估**
我们使用Python 3.8.5和Pytorch Geometric v1.7.1实现了我们的单调最大和GNN模型。我们的实现支持第3.1节中的标准编码/解码方案,以及第3.3.1节中的[35]提出的编码/解码方案。我们还实现了用于规则提取的算法1和6。接下来,我们描述了我们的经验评估结果,其中我们将我们模型的分类性能与几种最先进的方法进行了比较。
**相关工作**
从神经网络中提取规则的方法通常是通过首先在数据上训练神经模型,然后从训练好的模型中提取规则来进行的。早期这类系统专注于从前馈神经网络中提取命题(即不含变量的)规则[41]。Neural-LP [12]是这类现代系统的一个著名例子,它是DRUM [13]的前身。在Neural-LP、DRUM以及
**结论和未来工作**
我们介绍了一类基于GNN的数据集转换方法,这些方法模仿了带有不等式的Datalog规则的应用过程。我们转换产生的预测可以用符号来解释,并且我们已经证明它们在实践中可以成功训练。我们看到了许多未来工作的方向。在理论方面,我们将开发单调最大和GNN的完整表征。我们还将开发能够捕获更复杂规则(例如传递性)的扩展。
**作者贡献声明**
David Tena Cucala:撰写 – 审稿与编辑,撰写 – 初始草稿,软件,项目管理,方法论,调查,形式化分析,数据 curate,概念化。
Bernardo Cuenca Grau:撰写 – 审稿与编辑,监督,方法论,调查,资金获取,形式化分析,概念化。
Boris Motik:撰写 – 审稿与编辑,监督,方法论,调查,资金获取,形式化分析,概念化。
Egor V. Kostylev:撰写
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号