Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.10393 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914553593331712 |
|---|---|
| author | Sälzer, Marco Bergsträßer, Pascal Lin, Anthony W. |
| author_facet | Sälzer, Marco Bergsträßer, Pascal Lin, Anthony W. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10393 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Polynomial Counting Capabilities of Message Passing Neural Networks Sälzer, Marco Bergsträßer, Pascal Lin, Anthony W. Machine Learning Logic in Computer Science 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. |
| title | The Polynomial Counting Capabilities of Message Passing Neural Networks |
| topic | Machine Learning Logic in Computer Science |
| url | https://arxiv.org/abs/2605.10393 |