arXiv:2505.08021v1 声明类型: 新 摘要: 图 neural 网络(GNNs)解决了将深度学习应用于图结构数据时的两个关键挑战: 他们可以处理大小各异的输入图,并且确保在图形同构下的不变性。尽管 GNNs 已展现出广泛的应用性,但对其表达能力的理解仍是一个重要的问题。在本文中,我们证明了有界 GNN 架构对应于特定的一阶逻辑(FO)片段,包括模态逻辑(ML)、量词化模态逻辑(GML)、带普遍量词的模态逻辑(ML(A))、两个变量片段(FO2)及其扩展的计数量词(C2)。为了建立这些结果,我们使用了一阶逻辑和模态逻辑的一致模型理论的方法和工具,在图表示学习领域进行应用。这为在 FO 内理解 GNN 的逻辑表达能力提供了一个统一的框架。