The Polynomial Counting Capabilities of Message Passing Neural Networks
This work provides theoretical insights into the expressive power of MPNNs for counting, which is important for understanding their limitations and capabilities in graph learning tasks.
The paper studies the counting capabilities of Message Passing Neural Networks (MPNN) beyond linear arithmetic, focusing on polynomial counting constraints. It shows that global polynomial counting constraints can be checked using mean MPNN under mild assumptions, and local constraints can be checked under specific conditions, such as using sum/max aggregations or restricting to regular graphs.
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.