Caterpillar GNN: Replacing Message Passing with Graph-Level Aggregation
Organizations: University of Antwerp
Abstract
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 a graph-level aggregation over walk incidence-based matrices that are constructed to deliberately trade off some expressivity for stronger and more structured inductive bias. This approach allows for gradual scaling between classical message-passing and simpler methods based on walks. Drawing on weighted automata, we ensure our gradual scaling is polynomial-time and avoids the combinatorial explosion of colored walks. Our second result characterizes the expressive power at each scale using homomorphism counts over a hierarchy of generalized caterpillar graphs. Based on these foundations, we propose Caterpillar GNNs that substantially reduce the number of nodes in the hidden layers of the computational graphs on real-world datasets. This gradual reduction does not obstruct learning, enabling a systematic study of lower-order expressivity. We further describe benchmark settings where task-aligned expressivity supports learning.
Figures & tables
| Higher order b | treewidth g |
|---|---|
| -enabled c | -trees c |
| Subgraph Aggr. d,e | apex trees h |
| Spectral Invariant f | parallel trees i |
| Vanilla MPGNN a | trees g |
| Caterpillar (ours) | caterpillars |
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | Pre-comp. | Time per layer | Worst case | Equivariant |
|---|---|---|---|---|
| MPGNN [ Gilmer et al., 2017 ] | — | ✓ | ||
| CRaWL [ Tönshoff et al., 2023 ] | — | X | ||
| NeuralWalker [ Chen et al., 2024 ] | — | X | ||
| Path NN [ Michel et al., 2023 ] | ✓ | |||
| Path-based GNN [ Graziani et al., 2024 ] | ✓ | |||
| Caterpillar GNN (ours) | ✓ |
Graph Neural Networks
Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.
See all 777 papers