Caterpillar GNN: Replacing Message Passing with Efficient Aggregation

2025/06/07 by Marek Černý, Černý, Marek
Computer Science · #05C60 #05C85 (Secondary) #68T07 (Primary) #Advanced Graph Neural Networks #FOS: Computer and information sciences #G.2.2 #Graph Theory and Algorithms #I.2.6 #Machine Learning (cs.LG) #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2506.06784

openalex publication_date 2025/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 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.

Citations

• Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
• What makes a good feedforward computational graph?
• NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
• On the Expressive Power of Spectral Invariant Graph Neural Networks
• Learning Long Range Dependencies on Graphs via Random Walks
• Reconstructing the evolution history of networked complex systems
• An Algorithmic Meta Theorem for Homomorphism Indistinguishability
• Homomorphism Counts for Graph Neural Networks: All About That Basis
• Path Neural Networks: Expressive and Accurate Graph Neural Networks
• A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests
• On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race
• Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
• Ordered Subgraph Aggregation Networks
• Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree
• Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
• Understanding over-squashing and bottlenecks on graphs via curvature
• Cycle Representation Learning for Inductive Relation Prediction
• Weisfeiler and Lehman Go Cellular: CW Networks
• Graph Neural Networks with Local Graph Parameters
• Rethinking Graph Transformers with Spectral Attention
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial\n Networks
• Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
• Notes on Equivalence and Minimization of Weighted Automata
• TUDataset: A collection of benchmark datasets for learning with graphs
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• Deep Double Descent: Where Bigger Models and More Data Hurt
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Quantum isomorphism is equivalent to equality of homomorphism counts\n from planar graphs
• Walk refinement, walk logic, and the iteration number of the\n Weisfeiler-Leman algorithm
• Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
• How Powerful are Graph Neural Networks?
• Graph Coarsening with Preserved Spectral Properties
• Lovász Meets Weisfeiler and Leman
• Neural Message Passing for Quantum Chemistry
• MoleculeNet: A Benchmark for Molecular Machine Learning
• Semi-Supervised Classification with Graph Convolutional Networks
• On recognizing graphs by numbers of homomorphisms
• Contractors and connectors of graph algebras

Related

• Aggregation-aware MLP: An Unsupervised Approach for Graph Message-passing
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Demystifying MPNNs: Message Passing as Merely Efficient Matrix Multiplication
• Generalizing Aggregation Functions in GNNs:High-Capacity GNNs via Nonlinear Neighborhood Aggregators
• Covered Forest: Fine-grained generalization analysis of graph neural networks