arXiv:2505.07816cs.LOcs.AI2025-05
证明了图神经网络在树上的表达能力等价于特定逻辑系统。
Graph neural networks and MSO
- 通过构建分布式自动机捕捉树上所有可定义的节点性质
- 揭示了递归图神经网络与广义模态代换演算在表达力上一致
- 适合研究图神经网络理论基础的学者阅读
我们给出了一个替代证明，表明使用实数的循环图神经网络在限制于一阶单峰二阶逻辑（MSO）时，其表达能力与广义模态代换演算相同。该证明基于构造能捕获树上所有MSO可定义节点性质的分布式自动机。此外，我们还探讨了接受条件的一些变体。
原文摘要 · Abstract (English)
We give an alternative proof for the existing result that recurrent graph neural networks working with reals have the same expressive power in restriction to monadic second-order logic MSO as the graded modal substitution calculus. The proof is based on constructing distributed automata that capture all MSO-definable node properties over trees. We also consider some variants of the acceptance conditions.
图神经网络逻辑表达力自动机
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。