The Polynomial Counting Capabilities of Message Passing Neural Networks

We investigate counting in message passing neural networks beyond linear arithmetic. Using mean aggregation, these networks can check global polynomial counting constraints under mild assumptions. We also establish conditions for expressing local constraints and nested modalities, showing how aggregation choices and graph structure affect expressive power.

DOI: 10.24963/kr.2026/105