将图神经网络与一阶逻辑片段精确对应，揭示其表达能力边界。
The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic
- 用有限模型论方法建立GNN与一阶逻辑片段的严格对应关系
- 证明特定GNN架构恰好能表达特定逻辑片段的查询能力
- 为理解GNN表达力提供统一逻辑框架，适合理论研究者
图神经网络（GNN）解决了深度学习应用于图结构数据时输入图大小不一和图同构不变性两大挑战。尽管GNN应用广泛，其表达能力仍缺乏清晰理解。本文提出与一阶逻辑（FO）中多个重要片段（包括各类模态逻辑及更丰富的二元变量片段）精确对应的GNN架构。通过将一阶逻辑与模态逻辑的有限模型论方法引入图表示学习领域，建立了这些对应关系。研究结果为理解GNN在一类逻辑中的表达能力提供了统一框架。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph isomorphism. While GNNs have demonstrated broad applicability, understanding their expressive power remains an important question. In this paper, we propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO), including various modal logics as well as more expressive two-variable fragments. To establish these results, we apply methods from finite model theory of first-order and modal logics to the domain of graph representation learning. Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。