Caterpillar GNN: Replacing Message Passing with Efficient Aggregation
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914057817161728 |
|---|---|
| author | Černý, Marek |
| author_facet | Černý, Marek |
| contents | Message-passing graph neural networks (MPGNNs) dominate modern graph learning. Typical efforts enhance MPGNN's expressive power by enriching the adjacency-based aggregation. In contrast, we introduce an efficient aggregation over walk incidence-based matrices that are constructed to deliberately trade off some expressivity for stronger and more structured inductive bias. Our approach allows for seamless scaling between classical message-passing and simpler methods based on walks. We rigorously characterize the expressive power at each intermediate step using homomorphism counts over a hierarchy of generalized caterpillar graphs. Based on this foundation, we propose Caterpillar GNNs, whose robust graph-level aggregation successfully tackles a benchmark specifically designed to challenge MPGNNs. Moreover, we demonstrate that, on real-world datasets, Caterpillar GNNs achieve comparable predictive performance while significantly reducing the number of nodes in the hidden layers of the computational graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06784 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Caterpillar GNN: Replacing Message Passing with Efficient Aggregation Černý, Marek Machine Learning 68T07 (Primary), 05C60, 05C85 (Secondary) I.2.6; G.2.2 Message-passing graph neural networks (MPGNNs) dominate modern graph learning. Typical efforts enhance MPGNN's expressive power by enriching the adjacency-based aggregation. In contrast, we introduce an efficient aggregation over walk incidence-based matrices that are constructed to deliberately trade off some expressivity for stronger and more structured inductive bias. Our approach allows for seamless scaling between classical message-passing and simpler methods based on walks. We rigorously characterize the expressive power at each intermediate step using homomorphism counts over a hierarchy of generalized caterpillar graphs. Based on this foundation, we propose Caterpillar GNNs, whose robust graph-level aggregation successfully tackles a benchmark specifically designed to challenge MPGNNs. Moreover, we demonstrate that, on real-world datasets, Caterpillar GNNs achieve comparable predictive performance while significantly reducing the number of nodes in the hidden layers of the computational graph. |
| title | Caterpillar GNN: Replacing Message Passing with Efficient Aggregation |
| topic | Machine Learning 68T07 (Primary), 05C60, 05C85 (Secondary) I.2.6; G.2.2 |
| url | https://arxiv.org/abs/2506.06784 |