# The Polynomial Counting Capabilities of Message Passing Neural Networks

arXiv: https://arxiv.org/abs/2605.10393 · HTML: https://mlsanity.com/paper/2605.10393/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 24 references that are in the map.
- First posted on arXiv 11 May 2026.

## Builds on (most cited first, 13 of 13)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Molecular graph generation with Graph Neural Networks](https://mlsanity.com/paper/2012.07397/) (2020)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats](https://mlsanity.com/paper/2405.14606/) (2024)
- [Logical Characterizations of GNNs with Mean Aggregation](https://mlsanity.com/paper/2507.18145/) (2025)

## Abstract (arXiv)

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.