AI RESEARCH
The Polynomial Counting Capabilities of Message Passing Neural Networks
arXiv CS.LG
•
ArXi:2605.10393v1 Announce Type: new 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 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.