Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912977212407808 |
|---|---|
| author | Rosenbluth, Eran |
| author_facet | Rosenbluth, Eran |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_14846 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks Rosenbluth, Eran Machine Learning Computational Complexity 68T05, 68T07 I.2.6 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. |
| title | Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks |
| topic | Machine Learning Computational Complexity 68T05, 68T07 I.2.6 |
| url | https://arxiv.org/abs/2603.14846 |