🤖 machine learning

The Polynomial Counting Capabilities of Message Passing Neural Networks

This paper investigates the polynomial counting capabilities of Message Passing Neural Networks (MPNNs), demonstrating that they can verify global and specific local polynomial constraints in node-labelled graphs using mean aggregation, particularly under conditions such as regular graphs, non-nested modalities, or tree-like structures.

Original authors: Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a Message Passing Neural Network (MPNN) as a team of detectives working in a city (the graph). Each detective (a node) stands at an intersection and talks to their immediate neighbors to gather clues. They also have a special radio that lets them hear a summary of what's happening across the entire city.

The goal of this paper is to figure out how good these detectives are at counting. Specifically, can they do more than just count "how many red houses are nearby?" Can they solve complex math puzzles like, "Is the number of red houses squared greater than the number of blue houses cubed?"

Here is a breakdown of what the paper discovered, using simple analogies:

1. The Problem: Linear vs. Polynomial Counting

Most previous research showed that these detectives are great at linear counting.

Example: "Are there more red houses than blue houses?" (This is like $Red > Blue$).
The Limit: They struggled with polynomial counting, where numbers are multiplied by themselves (squared, cubed, etc.).
The Paper's Goal: The authors wanted to see if the detectives could handle these harder, "polynomial" math problems.

2. The Secret Weapon: The "Mean" Aggregator

The detectives have different ways of listening to their neighbors:

Sum: They add up all the numbers they hear.
Max: They only listen to the loudest voice.
Mean (Average): They calculate the average of all voices.

The authors discovered that the Mean (average) is the secret sauce for polynomial counting. By averaging, the detectives can naturally handle the division and multiplication needed for complex math. However, to make this work perfectly, the city needs to have some specific rules.

3. The Three Rules for Success

The paper found that for the detectives to solve these hard math puzzles, the city (the graph) usually needs one of three "special conditions":

Condition A: The "Marked" Detective (The VIP)
Imagine one detective is wearing a bright, unique hat that no one else has. This is a "marked node."
- Why it helps: It gives the team a fixed reference point. Without it, the detectives get confused about which numbers belong to whom when they are doing complex division.
- Real-world analogy: It's like having a specific "Start Here" sign on a map so you know exactly where you are relative to the rest of the city.
Condition B: The "Perfectly Regular" City
Imagine a city where every single intersection has exactly the same number of roads leading out of it.
- Why it helps: If every detective has the same number of neighbors, the math stays consistent. If one detective has 3 neighbors and another has 10, the "average" gets messy and hard to compare.
- Real-world analogy: A perfectly symmetrical grid, like a chessboard, where every square has exactly 4 neighbors.
Condition C: The "Tree-Like" City
Imagine a city with no loops or circles—like a family tree or a branching river.
- Why it helps: This structure prevents information from getting stuck in circles, allowing the detectives to count things at different "distances" from the center without getting confused.

4. The Big Discoveries

Scenario 1: Looking at the Whole City (Global Counting)
If the detectives only need to count things across the entire city (ignoring specific neighborhoods), they can solve polynomial math problems if there is a Marked Detective (Condition A). They don't need the city to be perfectly regular.

Scenario 2: Looking at Neighborhoods (Local Counting)
If the detectives need to count things in specific neighborhoods (e.g., "How many red neighbors does this specific detective have?"), it gets harder.

Strict Mode: If they only use the "Mean" (average), the city must be Perfectly Regular (Condition B) AND the detective must be Marked (Condition A) AND have a Self-Loop (standing on their own street corner).
Relaxed Mode: If the detectives are allowed to use "Sum" or "Max" in addition to "Mean," they can solve these problems even if the city is not perfectly regular. They just need the Marked Detective and the Self-Loop.

Scenario 3: Deep Nesting (The Russian Dolls)
Sometimes the math gets nested: "Count the neighbors of the neighbors of the neighbors."

The paper found that if the city is Tree-Like (Condition C) and the detectives have the Marked status, they can solve these deep, nested polynomial problems.
If they are allowed to use "Sum" or "Max" helpers, they can handle even more complex tree structures.

5. The Takeaway

The paper proves that MPNNs are much more powerful than we thought, but they need a little help.

They can do complex polynomial math (like $x^2 + y^3$ ) if we give them a reference point (a marked node).
If we want them to look at specific neighborhoods, the city needs to be symmetrical (regular) or tree-shaped, unless we give them extra tools (Sum/Max).

In short: These neural networks are like brilliant mathematicians, but they need a clear starting point and a consistent environment to solve their most complex counting puzzles. Without those conditions, they get lost in the math.

Technical Summary: The Polynomial Counting Capabilities of Message Passing Neural Networks

Problem Statement
Recent research has established that Message Passing Neural Networks (MPNNs) can express logical properties involving counting up to a threshold or satisfying linear arithmetic constraints, often characterized using fragments of first-order logic with counting (FOC2) or extensions with linear integer arithmetic. However, a gap remains in understanding the expressive power of MPNNs regarding polynomial counting constraints (non-linear arithmetic), which are relevant to advanced graph classification techniques like polynomial kernels. This paper investigates the conditions under which MPNNs, specifically those utilizing mean aggregation, can recognize properties defined by Peano Modal Logic (PML). PML extends Graded Modal Logic by allowing polynomial constraints (e.g., $x_1^2 \cdot x_2 \leq x_3$ ) rather than just linear ones.

Methodology
The authors employ a formal framework to analyze the expressive capabilities of MPNNs by comparing them against fragments of PML.

Model Definition: The study focuses on MPNNs ( $M_{mean}$ ) that use mean aggregation for both local (neighborhood) and global (entire graph) information. The authors also consider variants ( $M_{mean, x}$ ) that permit additional sum or max aggregations.
Logic Definition: They define PML, where modal formulas $\langle \pi_1, \dots, \pi_m \rangle \psi(x_1, \dots, x_m)(\phi_1, \dots, \phi_m)$ count nodes satisfying subformulas $\phi_i$ within specific neighborhoods (defined by modalities $\pi \in \{id, E_{in}, E_{out}, \top\}$ ) and check if the counts satisfy a Peano arithmetic constraint $\psi$ .
Recognition Framework: An MPNN is said to "recognize" a formula $\phi$ over a class of pointed graphs if the network's output state for the focus node $v$ is non-zero (specifically $\geq c(|V|)$ ) if the graph satisfies $\phi$ , and zero otherwise. The certainty $c(|V|)$ is allowed to depend on the graph size.
Construction Strategy: The proofs involve constructing specific MPNN architectures layer-by-layer. These constructions utilize "gadgets" (combinations of ReLU neurons) to perform arithmetic operations (multiplication, addition, comparison) on aggregated values. A key technical challenge addressed is the handling of denominators introduced by mean aggregation (e.g., $1/|V|$ or $1/|neigh(v)|$) when evaluating polynomial terms of varying degrees.

Key Contributions and Results
The paper identifies specific structural assumptions on input graphs that enable mean MPNNs to capture polynomial counting properties. The results are categorized by the depth of modalities (shallow vs. nested) and the type of modalities used (global vs. local).

Global Modalities (Shallow Depth):
- Homogeneous Constraints: For formulas using only global modality ( $\top$ ) and homogeneous Peano terms (no constant terms, same degree for all monomials), mean MPNNs can recognize the logic without additional graph assumptions (Lemma 1).
- General Polynomial Constraints: To recognize arbitrary global polynomial constraints (including non-homogeneous terms and constants), the input graphs must contain a marked node (a node with a unique color). Under this assumption, mean MPNNs can align denominators to $|V|^k$ and recognize the logic (Theorem 1).
Local Modalities (Shallow Depth):
- Regularity Requirement: For formulas using only local modalities ( $E_{in}, E_{out}$ ), mean MPNNs require the input graphs to be regular (all nodes have the same in/out-degree) and the focus node to be strongly marked (marked and having a self-loop). This allows the network to normalize local neighborhood sizes (Theorem 2).
- Relaxing Regularity: If the MPNN is allowed to use sum or max aggregation in addition to mean, the regularity assumption can be dropped. The network can then recognize local polynomial constraints on any graph where the focus is strongly marked (Theorem 3).
Mixed Modalities (Shallow Depth):
- When combining global and local modalities, the results from the previous sections can be combined. Mean MPNNs recognize these formulas on regular, strongly marked graphs (Theorem 4).
- With the addition of sum/max aggregations, the regularity assumption is again removable (Theorem 5).
Nested Modalities (Arbitrary Depth):
- Global Nesting: Nesting global modalities does not increase expressive power beyond depth 1; they can be flattened (Proposition 1).
- Local Nesting: For formulas with nested local modalities, the paper introduces a class of graphs called $(T \circlearrowleft_\phi)^p_\bullet$ . These are "tree-like" structures where the focus is marked, and the graph structure ensures unique traces for nodes at specific distances (avoiding ambiguity in neighborhood counts).
- Results: Mean MPNNs can recognize nested local PML on these tree-like, regular, strongly marked graphs (Theorem 6). If sum/max aggregations are permitted, the regularity constraint is removed, allowing recognition on general tree-like, strongly marked graphs (Theorem 7).

Significance and Claims
The paper claims to identify the minimal conditions required for MPNNs to generalize beyond linear arithmetic to polynomial counting.

Theoretical Generalization: The results suggest that MPNNs with mean aggregation can generalize techniques used in graph classification that rely on polynomial kernels (e.g., SVMs with polynomial kernels), provided the input data satisfies specific structural properties (marked nodes, regularity, or tree-likeness).
Role of Aggregation: The study highlights that while mean aggregation is sufficient for polynomial counting under strict structural assumptions, the inclusion of sum or max aggregations significantly relaxes these requirements (specifically removing the need for graph regularity).
Limitations: The authors explicitly state that without these structural assumptions (marked nodes, regularity, or tree-like structures), mean MPNNs cannot express all polynomial constraints. For instance, Lemma 2 demonstrates that mean MPNNs cannot distinguish between certain non-regular graphs satisfying a simple polynomial constraint.

The paper concludes that while MPNNs possess polynomial counting capabilities, realizing them requires either specific architectural choices (adding sum/max) or specific data preprocessing/structural assumptions (marking nodes, ensuring regularity or tree-like structures). Future work is suggested to explore arbitrary Boolean combinations of modalities and comparing counts at different distances, which are not currently covered by the PML framework used.