Caterpillar GNN: Replacing Message Passing with Efficient Aggregation
Marek Černý · 2025
Read Caterpillar GNN: Replacing Message Passing with Efficient Aggregation by Marek Černý (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06784.txt.
Introduction
Marek Černý rethinks how graph neural networks gather information from a graph. Standard message passing shuttles data along edges, round after round. His 2025 paper replaces that shuffle with aggregation over walk-based matrices, deliberately trading some expressive power for a stronger, cleaner bias.
The trade is not a leap but a dial: settings slide between plain walk methods and full message passing. At each step, expressive power is pinned down exactly by counting graph homomorphisms into a family of caterpillar-shaped graphs. The resulting Caterpillar GNNs beat a benchmark built to embarrass message passing. On real data they matched it, with far fewer hidden nodes. Graph learning readers get efficiency bought with theory, not luck.
Catalog record
| CREATOR | Marek Černý |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06784
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Caterpillar GNN: Replacing Message Passing with Efficient Aggregation Marek Černý Abstract Message-passing graph neural networks (MPGNNs) dominate modern graph learning, typically prioritizing maximal expressive power. In contrast, we introduce an efficient aggregation mechanism, deliberately trading off some expressivity for stronger and more structured aggregation capabilities. Our approach allows seamless scaling between classical message-passing and simpler methods based on colored or plain walks. We rigorously characterize the expressive power at each intermediate step using homomorphism counts from a hierarchy of generalized caterpillar graphs . Based on this foundation, we propose the Caterpillar GNN , whose robust graph-level aggregation enables it to successfully tackle synthetic graph-level task specifically designed to be challenging for classical MPGNNs. Moreover, we demonstrate that, on real-world datasets, the Caterpillar GNN achieves comparable predictive performance while significantly reducing the number of nodes in the hidden layers of the computational graph. 1 Introduction Graphs are a powerful and expressive structure, capable of representing complex relational information across various domains such as biology, chemistry, databases or social sciences. Unlike data with a given finite-dimensional structure such as text and images, graph structured data brings into a consideration the additional variability of its relations. To let deep learning methods process a signal represented as graph, Message-Passing Graph Neural Networks (MPGNNs) have emerged as a default approach. MPGNN iteratively aggregates information from a tree structure of node neighborhoods in a graph. However, in scenarios where strict invariance to vertex ordering is not required, alternative aggregation schemes based on applying deep learning to sequences of nodes visited by random walks have emerged. Recently, these two schemes combined Chen et al. 2024 ; Tönshoff et al. 2023 shown significant improvements. Deep neural networks rely on stacking multiple feedforward layers, progressively abstracting information. For instance, convolutional neural networks for images downscale after every given block of layers, gradually reducing the spatial dimension to accommodate for higher-level compact representations. In contrast, MPGNNs traditionally copy the input graph structure across all layers to perform repetitive message-passing . As a consequence, the structure and complexity of their computational graphs vary significantly depending on the properties of the input graph, some of which negatively influence the performance Vitvitskyi et al. 2025 . Meanwhile, random walk-based processing typically abandons explicit replication of node neighborhoods altogether, as shown Chen et al. 2024 . In this work, we simultaneously challenge and exploit both paradigms above by introducing a novel, parametric and vertex ordering invariant aggregation scheme that enables controlled, gradual reduction of the structure of the tree of neighborhoods in the feedforward computational graph at each parameter step. Our approach, efficient aggregation explicitly bridges the classical message-passing and the expressive power of plain walk counting, thereby achieving a structured and efficient option for “downscaling” within graph neural networks—an innovation we found previously absent in graph learning. Our main contributions to graph learning in Sections 3 , 5 , and 6 , are summarized as follows: • We introduce efficient aggregation downscaling from classical message-passing to walk counting. • We propose Caterpillar GNN , a new architecture directly based on efficient aggregation. • We demonstrate that Caterpillar GNN effectively tackles graph-level task specifically designed to be challenging for MPGNNs. • We conduct an empirical evaluation on real-word datasets, systematically investigating the trade-off between scaled computational graph complexity (the number of nodes) and predictive performance. We explicitly compare Caterpillar GNN and GCN-based MPGNN Kipf and Welling 2017 . Our core theoretical contributions in graph theory , given in Section 4 , are summarized as follows: • We give a combinatorial explanation of the expressive power of efficient aggregation using homomorphism counts form generalized caterpillar graphs. • We characterize the problem of homomorphism indistinguishability of two graphs for the hierarchy of caterpillar graph classes in terms of colored walks in those graphs. • We show the homomorphism counts from folklore caterpillar graphs, also known as the graphs of pathwidth at most one, are strictly more expressive than those of plain paths. 1.1 Related Work Methods alternative to MPGNNs leveraging random walk-based kernels Kriege 2022 ; Borgwardt et al. 2005 and dedicated neural architectures Chen et al. 2024 ; Tönshoff et al. 2023 ; Zeng et al. 2023 have recently emerged. Recently, structural aspects of MPGNN feedforward computation graph have been brought to attention Vitvitskyi et al. 2025 . Another line of work aims at enhancing MPGNN expressivity, e.g., Morris et al. 2019 ; Bodnar et al. 2021b ; Bodnar et al. 2021a ; Qian et al. 2022 ; Frasca et al. 2022 . Many of these enhancements are closely connected to graph homomorphisms Nguyen and Maehara 2020 ; Zhang et al. 2023 ; Jin et al. 2024 ; Paolino et al. 2024 ; Gai et al. 2025 . Purely theoretical studies on graph homomorphism counting, underpinning these recent practical advances, have a longstanding history dating back to foundational work by Lovász Lovász 1967 , and subsequently expanded through algebraic, combinatorial, and quantum approaches Dell et al. 2018 ; Grohe et al. 2022 ; Rattan and Seppelt 2021 ; Mančinska and Roberson 2020 , motivating our work. 2 Preliminaries Figure 1: Caterpillar graphs. (a) (1,4) -caterpillar with leg sequence (S_{1},S_{3},S_{0},S_{4}) , where S_{i} is, a star graph . a root with i leaves as children. (b) (3,4) -caterpillar. In both cases vertices 1,2,3,4 are the spine. Let G=(V,E) be a simple graph with vertex set V and edge set E\subseteq V^{2} . We assume no loops and the edges to be undirected. An edge between vertices u and v is denoted by uv . The neighborhood of a vertex u\in V is the set of vertices N(u):=\{v\mid uv{\text{ in }}E\} . We denote by A{\text{ in }}\mathbb{R}^{V\times V} the adjacency matrix of G , The identity and all-ones matrices by I and J , respectively, and the all-ones vector by \mathbf{1} . Multisets are prepresented using symbols \{\!\!\{\, , and \,\}\!\!\} , their union by \uplus . Multiset comprehention accounts for element multiplicities, so that M=\big\{\kern-3.99994pt\big\{m\mid m{\text{ in }}M\big\}\kern-3.99994pt\big\} . The set of all multisets of elements from X is denoted by \mathbb{N}^{X} . For M{\text{ in }}\mathbb{N}^{X} , we use notation M(x) for multiplicity of x in M . Finally, the notation [n] stand for the set \{1,2,\ldots,n\} . Caterpillar graphs. Let F be a tree graph, i.e., connected and without a cycle, and h,t{\text{ in }}\mathbb{N} , then F is a (h,t) - caterpillar if there is a path S of length t^{\prime}\leq t in F on vertices s_{1},s_{2},\dots s_{t^{\prime}} , with the following property: Let F^{\prime}=(V(F),E(F)\setminus E(S)) be a graph obtained from F by deleting edges of S . Then, for every vertex s_{i}{\text{ in }}S , there is a connected component F_{i} of F^{\prime} such that the distance from s_{i} to any other vertex in F_{i} is at most h . We call the path S a spine of F , and for such spine, we call the connected component F_{i} the i -th leg of F , and (F_{1},F_{2},\dots,F_{t^{\prime}}) the leg sequence of F . We denote the class of all (h,t) -caterpillars by \mathcal{C}_{h,t} , and all lengths by \mathcal{C}_{h}=\bigcup_{t\geq 0}\mathcal{C}_{h,t} . For example, every caterpillar in \mathcal{C}_{0} is exactly its spine, and thus \mathcal{P}_{t}=\mathcal{C}_{0,t} are the path graphs of