MPNN能用均值聚合实现多项式计数，扩展了图神经网络的逻辑表达能力。
The Polynomial Counting Capabilities of Message Passing Neural Networks
- 利用全局与局部均值聚合，突破线性计数限制
- 在满足条件下可验证节点标签图的多项式计数约束
- 适用于树状结构或规则图，适合图逻辑推理研究者
消息传递神经网络（MPNN）的计数能力近年来备受关注，已有研究表明其可表达涉及计数阈值或线性算术约束的逻辑。本文研究了MPNN在超越线性算术之外的计数能力，主要采用局部和全局均值聚合。我们证明，在温和假设下，均值型MPNN可检查节点标记图中的全局多项式计数约束。对于局部约束，若公式无嵌套模态，并满足：(i) 允许求和/最大值聚合，或 (ii) 仅限于规则图，则同样可实现。此外，对于具有嵌套模态的公式，均值型MPNN可在树状结构图上实现表达，前提条件类似。
原文摘要 · Abstract (English)
The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshold or more generally satisfy a linear arithmetic constraint. In this paper, we study the counting capabilities of MPNN beyond linear arithmetic, primarily utilising local and global mean aggregations. In particular, our goal is to tease out conditions required to express extensions of graded modal logic with polynomial counting constraints. We show that global polynomial counting constraints in node-labelled graphs can be checked using mean MPNN under mild assumptions. Checking local constraints is also possible, if we consider formulas with no nested modalities and additionally either (i) permit sum/max aggregations, or (ii) only restrict to regular graphs. We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures and similar assumptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。