Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

Eran Rosenbluth

This paper, "Lost in Aggregation," provides a rigorous theoretical reality check for the Graph Neural Network (GNN) community. It reveals a fundamental bottleneck in how standard Message-Passing GNNs (MP-GNNs) process information, proving they are significantly less expressive than previously thought when applied to graphs of varying sizes.

TL;DR

The paper proves that MP-GNNs using standard aggregation functions (like sum, mean, or max) can only distinguish a polynomial number of graph structures, even though the number of possible graphs grows doubly-exponentially. This makes these models "infinitely weaker" than even two iterations of the classic Color Refinement (Weisfeiler-Lehman) algorithm in a practical, size-independent setting.

What Problem Does This Paper Address?

In the world of Graph Machine Learning, we often measure a model's power by its ability to distinguish non-isomorphic graphs—essentially, can the model tell two different graphs apart? Previous research suggested that MP-GNNs are as powerful as the 1-dimensional Weisfeiler-Lehman (1-WL) test, also known as Color Refinement (CR).

However, those "equivalence" results often relied on a non-uniform assumption: that you can pick a different GNN for every possible graph size. In the real world, we want a single, uniform model that works on graphs of any size. This paper tackles the "uniform" expressivity of MP-GNNs, specifically looking at how the choice of aggregation function (the part that merges neighbor information) limits the model's ability to distinguish complex structures as the number of vertices ($n$) grows.

Methods

The author introduces a framework based on Information Complexity. The core idea is to track the "bit-length" of the values produced by a GNN's layers.

  1. Aggregation Classes: The paper defines two broad classes of aggregation functions:
  2. Logarithmic: The output bit-length grows logarithmically with the number of input nodes (e.g., sum, mean, max).
  3. Sublinear: A more general class where bit-length grows slower than the number of nodes.
  4. Complexity Analysis: By bounding the bit-length of intermediate computations (MLP outputs and aggregations), the author calculates the maximum number of distinct "equivalence classes" (unique output values) a GNN can produce for a given graph size $n$.
  5. Comparison to CR: The paper compares these bounds to the number of equivalence classes induced by just two iterations of the Color Refinement algorithm ($CR^{(2)}$).

Datasets

Not discussed in the paper. This is a purely theoretical work focused on mathematical proofs and complexity analysis.

Key Insights and Ideas

  • The "Uniform" Bottleneck: While a GNN could theoretically distinguish many graphs if allowed to have infinite precision or size-specific parameters, a fixed, computable GNN with standard aggregators acts as a massive information bottleneck.
  • Logarithmic Aggregators are Weak: Most aggregators used in practice (like sum) are "logarithmic." The paper proves that any MP-GNN using only these can only distinguish a polynomial number of vertices or graphs.
  • The Doubly-Exponential Gap: There are $2^{2^{O(n)}}$ non-isomorphic graphs of size $n$. Distinguishing only a polynomial number of them ($n^k$) means the model is missing almost everything as $n$ increases.
  • Infinitely Weaker than $CR^{(2)}$: Perhaps the most striking insight is that even though MP-GNNs are often compared to "full" CR, they are actually "infinitely weaker" than just two rounds of CR. As the graph size $n$ goes to infinity, the fraction of $CR^{(2)}$-distinguishable structures that a standard GNN can catch drops to zero.

Key Results

  • Theorem 3.7: For any MP-GNN with logarithmic aggregations, the number of induced equivalence classes $N_{dp}(n)$ is $poly(n)$. For sublinear aggregations, it is sub-exponential ($2^{o(n)}$).
  • Corollary 3.9: Formally establishes the "infinitely weaker" claim. Specifically: $$\lim_{n\to\infty} \frac{N_{dp}(n)}{CR^{(2)}_{dp}(n)} = 0$$ This means that as graphs get larger, the gap between what a simple local algorithm (CR) can see and what a GNN can see becomes an unbridgeable chasm.

Limitations and Future Work

  • Softmax and Attention: The paper does not fully analyze "softmax" aggregation (common in GATs and Graph Transformers). Because softmax involves exponentiation, it might have higher output-size complexity (potentially linear or exponential), which could bypass some of these limits.
  • Non-ReLU Activations: The proofs focus on ReLU-activated, rationally-weighted MLPs. Functions like sigmoid or tanh involve exponentiation and require further study to see if they offer more "distinguishing bits."
  • High-Precision Aggregators: The author notes that one could design an aggregator that packs all CR information into a single rational number, but this would likely lead to astronomical runtime complexities or require infinite precision, making it impractical for real-world hardware.
  • Expressivity vs. Distinguishing Power: While the paper focuses on distinguishing graphs, the author notes that if a model can't even distinguish two inputs, it certainly can't approximate a function that treats them differently. This sets a hard upper bound on what GNNs can learn to compute.

Summary updated

Abstract

We define a generic class of functions that captures most conceivable aggregations for Message-Passing Graph Neural Networks (MP-GNNs), and prove that any MP-GNN model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is doubly-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2-iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous results state that MP-GNNs match full CR, however they concern a weak, 'non-uniform', notion of distinguishing-power where each graph size may required a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.
BibTeX
@misc{rosenbluth2026lost,
  author = {Eran Rosenbluth},
  title = {{Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks}},
  year = {2026},
  eprint = {2603.14846},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.14846},
}
Figure