arXiv:2405.14606v4 宣告类型: replace-cross 摘要: 在2019年的开创性工作中，Barceló及其合作者确定了与一阶逻辑可定义的性质相比，精确匹配常数迭代深度图神经网络（GNNs）表达能力的形式化逻辑。在这篇文章中，我们给出了两种情况下递归图神经网络的精确逻辑特征刻画：（1）在带有浮点数的设定中，（2）在带有实数的设定中。对于浮点数，匹配递归GNN的形式化逻辑是一种带计数的规则基模态逻辑，而对于实数，我们使用一种合适的无穷模态逻辑，同样带计数。这些结果显示，在不涉及背景逻辑的前提下，递归GNN在浮点数和实数两种情况下均与逻辑具有精确匹配的关系，但利用一些自然的浮点算术假设。应用我们的特征刻画，我们还证明了，相对于由单调第二阶逻辑（MSO）可定义的图性质，我们的无穷模态逻辑和规则基模态逻辑具有相同的表达能力。这意味着带有实数和浮点数的递归GNN在MSO可定义的性质上具有相同的表达能力，并且还表明，对于此类性质，也存在一种（有限的）规则基模态逻辑来刻画递归GNN，而不像一般情况，这两种数值下递归GNN的表达能力不同。除了逻辑导向的结果外，我们还通过分布式自动机来特征刻画了具有浮点数和实数的递归GNN，这与分布式计算模型建立了联系。