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.
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.