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
Figure 1: Counting over either of the two depicted notions is exactly as expressive on graphs. Left: A graph homomorphism {\color[rgb]{0.8633,0.1367,0}\varphi}\colon F{\color[rgb]{0.8633,0.1367,0}\to}\,G , where F is a caterpillar graph. Right: An occurrence of a colored walk {\color[rgb]{0,0.1367,0.8633}{\bm{w}}}=\mathsf{brbg} in the same graph G colored by χdeg according to vertex degrees.
Higher order b
treewidth g
P -enabled c
P -trees c
Subgraph Aggr. d,e
apex trees h
Spectral Invariant f
parallel trees i
Vanilla MPGNN a
trees g
Caterpillar (ours)
caterpillars
Table 1: MPGNNs and corresp. expressivity bounds using class F . a Gilmer et al. (2017) , b Morris et al. (2019) , c Barceló et al. (2021) , d Qian et al. (2022) e Frasca et al. (2022) , f Zhang et al. (2024) , g Dvořák (2010) , h Rattan and Seppelt (2021) , i Gai et al. (2025) .
Figure 2: Top: Graph G with vertices colored by χdeg . Colors red, green and blue depict degrees 1, 2 and 3, respectively. Bottom: Walk incidence matrix W of shape V×Σ∗ . The entry W[3,gb] equals 2 , since vertex 3 terminates two occurrences of the colored walk gb in G .
Figure 3: Locking the adjacency matrix A of the graph G as in Figure 2 . Matrix B3 of shape V×S3 is a submatrix of W3 (of shape V×Σ3 ) induced by highlighted columns, similarly, B2⊤ and W2⊤ .
Figure 4: Comparison of computational graphs (without self-loops): (GLA) graph-level aggregation (ours), and (MP) message-passing for the graph G and coloring χdeg as given in Figure 2 (left). Connections between layers are given by (GLA) t -th reduced graph matrices; (MP) copies of the adjacency matrix and the global readout. For unit weights, we omit labels.
Figure 5: Strictly separated lower-order expressivity hierarchy of graph-level aggregations IR along the height parameter h related to caterpillar graph classes P=C0⊂C1⊂⋯⊂Ch⊂⋯⊂T .
Figure 6: Caterpillar graphs with highlighted (possible) spine (green). Graph F0 is a path of length 6 and hence a (0,6) -caterpillar. Graph F1 is a (1,6) -caterpillar, and F3 is a (3,6) -caterpillar.
Figure 7: nStepAddition : Trading off expressivity for a suitably structured task-aligned inductive bias. Ch denotes a model of Caterpillar GNN with height h (ours), while MP refers to a model of MPGNN. The y -axis shows validation accuracy.
Figure 8: (a) An example graph G on vertices {1,2,3,4,5} with a Σ -coloring χ , where Σ={r,b,g,y} . (b) The weighted automaton A(G,χ) that accepts a weighted language of words corresponding to colored walks in G ( Lemma A.5 ). The weights of the language represent the number of occurrences of each walk in G . Transitions corresponding to directed edges uv in E(G) are represented by matrices {\bm{M}}(\chi(u)\!\rotatebox[origin={c}]{90.0}{-}\!\chi(v))={\bm{P}}_{\chi(u)}{\bm{A}}{\bm{P}}_{\chi(v)} , while transitions corresponding to loops at vertex u in V(G) are given by matrices M(χ(u))=Pχ(u)IPχ(u) .
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: Sections A.1 and A.3 establish the result of Theorem 4.2 for a coloring χ by relating the following three functions on graphs: Colored walk refinement wr(−,χ) , semantics of graph walk automaton [[A(−,χ)]] , and the matrices of graph-level aggregation IR(−,χ) .
Figure 10: Section 4 establishes the equivalence between homomorphism counts over caterpillars and colored walk refinement with respect to (specific) colorings. First, we focus on folklore caterpillars (left), and then we generalize to (h,t) -caterpillars (right) in Section B.1 . For every h,t≥0 , we relate the following two functions on graphs: homomorphism counts over (h,t) -caterpillars hom(Ch,t,−) , and colored walk refinement wr(t)(−,χcr(h)) .
Figure 11: An example of a pair of graphs G and H that strictly separates the graph functions hom(C1,−) and hom(C0,−) . Note that the graph H can be derived from G by removing the edges {0,8} and {1,9} , and then adding the edges {0,1} and {8,9} .
Figure 12: An example graph representation of a protein structure, colored by (χF,χdeg) . The shown datapoint is taken from the Proteins dataset [ Morris et al., 2020 ] .
Figure 13: Left: Computational graph (ours) of Caterpillar GCN with h=1 that uses CtℓA~ matrix at ℓ -th layer. This diagram is analogous to Figure 4 . Right: Computational graph (message-passing) of GCN that uses copies of matrix A~ for its layers. Weights are represented by line width, and signs by arrow direction. The input graph is shown in Figure 12 .
Table 2: Density of computational graphs across datasets. By Ch is denoted the (caterpillar height) parameter h in N of graph-level aggregation (ours), while MP denotes the full message-passing GCN. The subcolumns correspond to δh,L (lower is better) and relative_density (higher is better once δh,L is bounded) for L=5 layers. We report absolute density in % .
Method
Pre-comp.
Time per layer
Worst case
Equivariant
MPGNN [ Gilmer et al., 2017 ]
—
∣E∣
n2
✓
CRaWL [ Tönshoff et al., 2023 ]
—
n⋅fG(ΔT)⋅T
nfG((n−1)T)T
X
NeuralWalker [ Chen et al., 2024 ]
—
n⋅fG(ΔT)⋅T
nfG((n−1)T)T
X
Path NN [ Michel et al., 2023 ]
n⋅ΔT
n⋅ΔT⋅T
nT+1T
✓
Path-based GNN [ Graziani et al., 2024 ]
n⋅ΔT
n⋅ΔT⋅T
nT+1T
✓
Caterpillar GNN (ours)
T⋅n2.372
∣E∣⋅δh,L
n2
✓
Appendix
Table 3: Asymptotic comparison of methods processing sequential patterns of length T. The function fG gives the number of sampled walks on G=(V,E) from the given upper bound. Symbol Δ stands for the maximal degree and δh,L is the relative density on G (see Equation 30 ).
Table 4: Density and nodal efficiency of computational graphs across large datasets. By Ch is denoted the (caterpillar height) parameter h in N of graph-level aggregation (ours), while MP denotes the full message-passing GCN + [ Luo et al., 2025 ] . The subcolumns correspond to δh,L (lower is better) and relative_density (higher is better once δh,L is bounded) for L=5 layers. We report absolute density in % . Columns “ # n.” denote the number of nodes of the computation graph, and columns “ % s.” percentage of nodes of the computation graph saved compared with message-passing ( MP ).
Figure 14: nStepAddition : An example of a graph G (a). The graph G encodes two 5 -bit numbers (b), namely 11 (top) and 22 (bottom). If N=33 for a classification dataset then G is a positive example, as 11+22=33 .
Table 5: Results for the nStepAddition dataset. By Ch is denoted the (caterpillar height) parameter h in N of graph-level aggregation (ours), while MP denotes the full message-passing GCN. We report mean validation accuracy with standard deviation across 10 different splits. The 18-layer model was trained for 10 and 50 epochs. The best results are highlighted in bold. The columns “ # n.” denote the number of nodes of the computation graph, and columns “ % s.” the percentage of nodes of the computation graph saved compared with message-passing (MP).
Figure 15: Computational nodes vs. accuracy. Solid segments connect models of Caterpillar GNN, with height h=0 ( C0 , circle) up to h=10 ( C10 , circle), the final dashed segment connects to MPGNN (square).
Table 6: Results for graph-level classification datasets. By Ch is denoted the (caterpillar height) parameter h in N of graph-level aggregation (ours), while MP denotes the full message-passing GCN. We report mean validation accuracy with standard deviation across 10 different splits. Columns “ # n.” denote the number of nodes of the computation graph, and columns “ % s.” the percentage of nodes of the computation graph saved compared with message-passing ( MP ).
Table 7: Running times across datasets. By Ch is denoted the (caterpillar height) parameter h in N of graph-level aggregation (ours), while MP denotes the full message-passing GCN. Columns “precomp" report the preprocessing time for the computation of graph-level aggregation matrices, and columns “avg. training" report the average training time across multiple runs.
Table 8: Results for graph-level regression datasets. By Ch is denoted the (caterpillar height) parameter h in N of graph-level aggregation (ours), while MP denotes the full message-passing GCN. We report validation mean absolute error (MAE) with standard deviation across 10 different splits and random seeds, with five repetitions using different random seeds for ZINC. Columns “ # n.” denote the number of nodes of the computation graph, and columns “ % s.” the percentage of nodes of the computation graph saved compared with message-passing ( MP ).
We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (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 super-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 studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require 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.
Message-passing graph neural networks (GNNs) are limited in expressive power by the one-dimensional Weisfeiler-Leman test. Persistent homology (PH) provides topological descriptors that can complement GNN representations, but existing approaches typically compute persistence separately from the representation learning process. In this paper, we introduce Message-Passing Graph Persistence (MGP), a family of topological descriptors that incorporates message passing into graph filtrations. At each filtration step, node embeddings are updated using the current subgraph and associated with persistence events. These embeddings also determine the representatives of connected components during persistence computation. We prove that MGP is invariant under graph isomorphism and that it is strictly more expressive than the PH-based descriptors it extends. We evaluate MGP on an expressivity benchmark and on several graph classification and regression datasets. Experiments show that MGP outperforms other PH-based descriptors on most of these datasets.
Jorge Luiz Franco, Arthur Queiroz Moura, Moacir Ponti +1
Institute of Mathematics and Computer Sciences (ICMC), University of S˜ao Paulo, S˜ao Carlos, Brazil · Avra · Mercado Libre +1
It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored in their lack of universality for higher-order signals. To go beyond this bound, we propose the Full-Spectrum GNNs (FSpecGNNs), a second-order generalization of classical spectral GNNs. FSpecGNN advances spectral filtering from two perspectives: (1) it lifts signals from the node domain to the node-pair domain; and (2) it extends the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. We show that classical spectral GNNs arise as a diagonal special case of FSpecGNNs, and prove that FSpecGNNs can be at most as expressive as Local 2-GNN while universally approximating node-pair signals, the latter being particularly beneficial for heterophilic graph learning. Moreover, FSpecGNN admits scalable implementations that avoid explicit node-pair-level computations; combined with a low-rank approximation that reduces full-spectrum convolution to a combination of polynomial spectral filters, it enables learning on large graphs. Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.
Xiaohan Wang, Deyu Bo, Longlong Li +1
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.