揭示图神经网络全局读取机制如何突破逻辑表达极限
Towards Understanding the Expressive Power of GNNs with Global Readout
- 用求和聚合与全局读取实现对更复杂图性质的捕捉
- 在有向与无向图上超越经典逻辑C2的表达能力
- 为理解图神经网络逻辑上限提供新视角，适合理论研究者
本文研究消息传递型图神经网络（ACR-GNNs）的表达能力，聚焦其对一阶（FO）性质的刻画能力。尽管严格逻辑表征仍是开放难题，本文提出两项贡献：首先，证明在有向和无向图上，仅需求和聚合与全局读取即可捕获无法被逻辑语言C2表达的FO性质，优于此前需特殊设计函数的结果；其次，识别出两种恢复可表征性（相对于C2）的自然方式：限制局部聚合或限定图的有界度（不限制大小）。在两种情形下，GNN能表达的FO性质恰好对应带全局计数模态的分级模态逻辑公式。结果确立了GNN表达力在C2片段下的天然上下界，表明正是聚合与读取间无约束交互使其超出C2表达能力。
原文摘要 · Abstract (English)
We study the expressive power of message-passing aggregate-combine-readout graph neural networks (ACR-GNNs). Particularly, we focus on the first-order (FO) properties expressible by this formalism. While a tight logical characterisation remains a difficult open question, we make two contributions towards answering it. First, we show that sum aggregation and readout suffice for GNNs to capture FO properties that cannot be expressed in the logic C2 on both directed and undirected graphs. This strengthens known results by Hauke and Wał{\k e}ga (2026) where aggregation and readout functions are specially crafted for the task. Second, we identify two natural ways of restoring characterisability (with regard to C2) for ACR-GNNs. One option is to limit local aggregation (without imposing restrictions on global readout), whilst the second is to run ACR-GNNs over graphs of bounded degree (but unbounded size). In both cases, the FO properties captured by GNNs are exactly those definable by a formula in graded modal logic with global counting modalities. Our results thus establish an innate lower- and upper-bound in terms of how far (fragments of) C2 can be taken to characterise GNNs, and imply that is indeed the unbounded interaction of aggregation and readout that pushes the logical expressive power of GNNs above C2.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。