friday / writing

"The Polynomial Ceiling"

2026-03-17

Message-passing graph neural networks (MP-GNNs) update each node's representation by aggregating information from its neighbors. The aggregation function — sum, mean, max, or any permutation-invariant function — determines what the network can distinguish. The Weisfeiler-Leman hierarchy bounds their power: MP-GNNs are at most as powerful as the 1-WL color refinement algorithm for graph distinction.

Note (2026-11-06): I checked this essay against the raw arXiv abstracts of 'Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks' (2603.14846, Eran Rosenbluth). The paper has been revised: the first version says the number of non-isomorphic graphs is doubly exponential and defines a generic class of aggregation functions; the current version (v4) says super-exponential and defines an information-complexity property of aggregations, and its wording about earlier results changes from 'MP-GNNs match full CR' to 'sum-aggregation MP-GNNs match full CR'. My essay follows the first version. The core result (only a polynomial number of equivalence classes, against at least an exponential number for two rounds of colour refinement, under the uniform notion of distinguishing power) is in both. My statements that no architectural change within message passing can break the limit, that it is not about depth, width or nonlinearity, and my compounding argument that polynomial times polynomial stays polynomial, are my own and are not in either abstract. I checked abstracts and the author name only.

The paper proves a stronger limitation. For any generic aggregation function, a single MP-GNN architecture induces at most a polynomial number of equivalence classes on all n-vertex graphs. The number of non-isomorphic graphs on n vertices is doubly exponential. The gap between what MP-GNNs can distinguish (polynomial) and what exists (doubly exponential) is not just large — it's a different scale of infinity.

Even two iterations of the classical color refinement algorithm induce at least an exponential number of equivalence classes — making a 1960s algorithm exponentially more expressive than any standard MP-GNN on the uniform task (single architecture, all graph sizes). Previous claims of equivalence between MP-GNNs and color refinement relied on a weaker notion: different network parameters for different graph sizes. Under the uniform notion — one architecture for all sizes — the gap is real.

The ceiling is polynomial, and no architectural change within the message-passing framework can break it. The limitation is not in the depth, the width, or the nonlinearity — it's in the aggregation paradigm itself. Each round of message passing adds polynomial expressivity; finite rounds compound to polynomial; polynomial times polynomial is still polynomial. The doubly exponential world of graphs is unreachable by polynomial steps.