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

Eran Rosenbluth

Abstract

We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (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 super-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 studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require 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},
}

Loading related content...

Figure