证明了带读出层的GNN比完整C2逻辑更强大
Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2
- 通过逻辑对比方法，分析GNN与逻辑语言的表达能力关系
- 发现带读出层的GNN严格超越完整C2逻辑的表达能力
- 对GNN理论和无穷逻辑研究均有重要意义
近年来，人们通过将图神经网络（GNN）与逻辑语言关联来理解其表达能力。Barceló 等人（2020）首次表明，加权模态逻辑（或逻辑 C2 的受控片段）刻画了聚合-组合型 GNN 的逻辑表达能力。他们提出一个‘具有挑战性的开放问题’：完整 C2 是否能刻画聚合-组合-读出型 GNN 的表达能力？该问题至今未解。本文通过证明，聚合-组合-读出型 GNN 的逻辑表达能力严格强于 C2，从而解决了这一开放问题。该结论在无向图和有向图上均成立。除对 GNN 的理论意义外，本工作还为无穷逻辑的表达能力提供了纯逻辑视角的新见解。
原文摘要 · Abstract (English)
In recent years, there has been growing interest in understanding the expressive power of graph neural networks (GNNs) by relating them to logical languages. This research has been been initialised by an influential result of Barceló et al. (2020), who showed that the graded modal logic (or a guarded fragment of the logic C2), characterises the logical expressiveness of aggregate-combine GNNs. As a ``challenging open problem'' they left the question whether full C2 characterises the logical expressiveness of aggregate-combine-readout GNNs. This question has remained unresolved despite several attempts. In this paper, we solve the above open problem by proving that the logical expressiveness of aggregate-combine-readout GNNs strictly exceeds that of C2. This result holds over both undirected and directed graphs. Beyond its implications for GNNs, our work also leads to purely logical insights on the expressive power of infinitary logics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。