【图机器学习论文】图神经网络的逻辑表达性（Logical Expressiveness of Graph Neural Networks）

题目： Logical Expressiveness of Graph Neural Networks

摘要：

图神经网络(Graph Neural Networks, GNNs)是近年来在分子分类、知识图谱补全等结构化数据处理领域中流行起来的一类机器学习体系结构。最近关于GNNs表达能力的研究已经建立了它们对图中节点进行分类的能力与用于检查图同构的WeisfeilerLehman (WL)测试之间的紧密联系。具体来说，这两篇论文的作者分别观察到，WL测试产生的节点分类总是细化了任何GNN产生的分类，而且有GNN可以重现WL测试。这些结果表明，GNNs在节点分类方面与WL测试一样强大。然而，这并不意味着GNNs可以表达任何通过WL测试改进的分类器。我们的工作旨在回答以下问题:什么是可以用GNNs捕获的节点分类器?在本文中，我们从逻辑的角度来看待这个问题，将其限制在FOC2中可表达的属性上，即具有计数能力的一阶逻辑的两变量片段进行研究。

作者：

Pablo Barceló是智利天主教大学工程学院和数学学院数学与计算工程研究所所长，研究领域为数据库理论、计算机科学中的逻辑、自动机理论。