Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

Authors: raffaele  paolino
sohir  maskey
pascal  welke
gitta  kutyniok
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:14:25

Abstract: We introduce $r$-loopy Weisfeiler-Leman ($r$-$\ell$WL), a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, $r$-$\ell$MPNN, that can count cycles up to length $r{+}2$. Most notably, we show that $r$-$\ell$WL can count homomorphisms of cactus graphs. This extends 1-WL, which can only count homomorphisms of trees and, in fact, is incomparable to $k$-WL for any fixed $k$. We empirically validate the expressive and counting power of $r$-$\ell$MPNN on several synthetic datasets and demonstrate the scalability and strong performance on various real-world datasets, particularly on sparse graphs.

Main paper: 
 introduction: 
 Graph Neural Networks (GNNs) (Scarselli et al., 2009; Bronstein et al., 2017) have become a prevalent architecture for processing graph-structured data, contributing significantly to various applied sciences, such as drug discovery (Stokes et al., 2020) , recommender systems (Fan et al., 2019) , and fake news detection (Monti et al., 2019) .Among various architectures, Message Passing Neural Networks (MPNNs) (Gilmer et al., 2017) are widely used in practice, as they encompass only local computation, leading to fast and scalable models. Despite their success, the representational power of MPNNs is bounded by the Weisfeiler-Leman (WL) test, a classical algorithm for graph isomorphism testing (Xu et al., 2019; Morris et al., 2019) . This limitation hinders MPNNs from recognizing basic substructures like cycles (Chen et al., 2020) . However, specific substructures can be crucial in many applications. For example, in organic chemistry, the presence of cycles can impact various chemical properties of the underlying molecules (Deshpande et al., 2002; Koyutürk et al., 2004) . Therefore, it is crucial to investigate whether GNNs can count certain substructures and to design architectures that surpass the limited power of MPNNs.Several models have been proposed to surpass the limitations of WL. Many of these models draw inspiration from higher-order WL variants (Morris et al., 2019) , enabling them to count a broader range of substructures. For instance, GNNs emulating 3-WL can count cycles up to length 7. However, this increased expressivity comes at a high computational cost, as 3-WL does not respect the sparsity of real-world graphs, posing serious scalability issues. Hence, there is a critical need to design expressive GNNs that respect the inherent sparsity of real-world graphs (Morris et al., 2023) .Figure 1 : Visual depiction of r-GIN: During preprocessing, we calculate the path neighborhoods N r (v) for each node v in the graph G. Paths of varying lengths are processed separately using simple GINs, and their embeddings are pooled to obtain the final graph embedding. The forward complexity scales linearly with the sizes of N r (v), enabling efficient computation on sparse graphs.Main Contributions. We introduce a novel class of color refinement algorithms called r-loopy Weisfeiler-Leman test (r-WL) and a corresponding class of GNNs named r-loopy Graph Isomorphism Networks (r-GIN). The key idea is to collect messages not only from neighboring nodes but also from the paths connecting any two distinct neighboring nodes, as illustrated in Figure 1 . This approach enhances the resulting GNNs' expressivity beyond 1-WL. In particular, r-WL can count cycles up to length r+2, even surpassing the k-WL hierarchy.Furthermore, we prove that r-WL can homomorphism-count any cactus graph with cycles up to length r+2. Cactus graphs are valuable due to their structural properties and simplicity, making them useful for modeling in areas such as electrical engineering (Nishi et al., 1986 ) and computational biology (Paten et al., 2011) . For instance, aromatic compounds often form cactus graphs, where the molecular core, usually a cycle, is coonected to functional groups (e.g., carboxyl groups) that can significantly impact the properties of the molecule. Thus, the ability to homomorphism-count cactus graphs can enhance model performance, and it allows us to compare the expressive power of r-WL with other popular GNNs in a quantitative manner (Barceló et al., 2021; B. Zhang et al., 2024) . Specifically, we show that r-WL is more expressive than GNNs that include explicit homomorphism counts of cycle graphs, known as F-Hom-GNNs (Barceló et al., 2021) . Additionally, 1-WL can already separate infinitely many graphs that Subgraph k-GNNs (Frasca et al., 2022; Qian et al., 2022) cannot (see, e.g., Figure 7 ). The higher expressivity, paired with the local computations, highlights the enhanced potential of r-GIN, showing its competitive performance and the efficiency of its forward pass on real-world datasets, see Section 7. 
related work: 
 The notion of expressivity in standard neural networks is linked to the ability to approximate any continuous function (Cybenko, 1989; Hornik et al., 1989) . In contrast, GNN expressivity is measured by the ability to distinguish non-isomorphic graphs. According to the Stone-Weierstrass theorem, these criteria are equivalent (Chen et al., 2019; Dasoulas et al., 2021) : a network that can distinguish all graphs can approximate any continuous function. Therefore, research often focuses on determining which graphs a GNN can distinguish (Morris et al., 2023) . Xu et al. (2019) and Morris et al. (2019) proved that the expressive power of MPNNs is bounded by 1-WL. Subsequent works (Maron et al., 2018; Morris et al., 2019 Morris et al., , 2020) ) introduced higher-order GNNs that have the same expressive power as k-WL or its local variants (Geerts et al., 2022) . Although these networks are universal (Maron et al., 2019b; Keriven et al., 2019) , their exponential time and space complexity in k renders them impractical. Abboud et al. (2022) proposed k-hop GNNs which aggregate information from k-hop neighbors, thus, enhancing expressivity beyond 1-WL but within 3-WL (Feng et al., 2022) . Michel et al. (2023) and Graziani et al. (2024) construct GNNs that process paths emanating from each node to overcome 1-WL. Subgraph GNNs (Bevilacqua et al., 2021; You et al., 2021; Frasca et al., 2022; Huang et al., 2022) surpass 1-WL by decomposing the initial input Intuitively, a homomorphism from F to G is an edge-preserving map. A subgraph isomorphism ensures that F actually occurs as a subgraph of G. Consequently, it also maps distinct edges to distinct edges. A visual explanation can be found in Figure 5 . We denote by Hom(F, G) the set of homomorphisms from F to G and by hom(F, G) its cardinality. Similarly, we denote by Sub(F, G) the set of subgraph isomorphisms from F to G and by and sub(F, G) its cardinality. 
graph invariants: 
 In order to unify different expressivity measures, we recall the definition of graph invariants. Definition 2. Let P be a designated set, referred to as the palette. A graph invariant is a functionζ : G → P such that ζ(G) = ζ(H) for all isomorphic pairs G, H ∈ G. ζ is a complete graph invariant if ζ(G) = ζ(F ) for all non-isomorphic pairs G, F ∈ G.Complete graph invariants have maximal expressive power. However, no polynomial-time algorithm to compute a complete graph invariant is known. To compare the expressive power of different graph invariants, such as graph colorings and GNN architectures, we introduce the following definition. Definition 3. Let γ, ζ be two graph invariants. We say that γ is more powerful than ζ (γ ζ) if for every pair G, H ∈ G, γ(G) = γ(H) implies ζ(G) = ζ(H). We say that γ is strictly more powerful than ζ if γ ζ and there exists a pair F, G ∈ G such that γ(G) = γ(H) and ζ(G) = ζ(H).Message passing is an iterative algorithm that updates the colors of each node v ∈ V (G) asEQUATIONThe graph output after t iterations is given byc (t) (G) := h c (t) (v) | v ∈ V (G) .Here, g (t) , h are functions on the domain of multisets and f (t) is a function on the domain of tuples. For each t, the colorings c (t) are graph invariants. When the subsets of nodes with the same colors cannot be further split into different color groups, the algorithm terminates; the stable coloring after convergence is denoted by c(G).Choosing injective functions for all f (t) and setting g (t) and h as the identity function results in 1-WL (Weisfeiler et al., 1968) . If f (t) , g (t) , h are chosen as suitable neural networks, one obtains a Message Passing Neural Network (MPNN). Xu et al. (2019) proved that MPNNs are as powerful as 1-WL if the functions f (t) , g (t) , and h are injective on their respective domains. The k-WL algorithms uplift the expressive power of 1-WL by considering interactions between k-tuples of nodes. This results in a hierarchy of strictly more powerful graph invariants (see Appendix B.1 for a formal definition).A more nuanced graph invariant can be built by considering the occurrences of a motif F .Definition 4. Let F ∈ G. A graph invariant ζ can homomorphism-count F if for all pairs G, H ∈ G ζ(G) = ζ(H) implies hom(F, G) = hom(F, H). By analogy, ζ can subgraph-count F if for all pairs G, H ∈ G, ζ(G) = ζ(H) implies sub(F, G) = sub(F, H).If F is a family of graphs, we say that (Lovász, 1967) . Additionally, homomorphism-counting serves as a quantitative expressivity measure to compare different WL variants and GNNs, such as k-WL, Subgraph GNNs, and other methods (Lanzinger et al., 2024; B. Zhang et al., 2024) , and allows for relating them to our proposed r-WL variant, as detailed in Corollary 2. 
loopy weisfeiler-leman algorithm: 
 In this section, we introduce a new graph invariant by enhancing the direct neighborhood of nodes with simple paths between neighbors. Definition 5. Let G ∈ G. A simple path of length r is a collection p = {p i } r+1 i=1 of r+1 nodes such that {p i , p i+1 } ∈ E(G) and i = j =⇒ p i = p j for every i, j ∈ {1, . . . , r},.Simple paths are the building blocks of r-neighborhoods, which in turn are the backbone of our r-WL algorithm. The following definition is inspired by (Cantwell et al., 2019; Kirkley et al., 2021) . For consistency, we set N 0 (v) := N (v). An example of the construction of r-neighborhood is shown in Figure 2 , where different rneighborhoods of node v are represented with different colors.Definition 6. Let G ∈ G and r ∈ N \ {0}, we define the r-neighborhood N r (v) of v ∈ V (G) as N r (v) := {p | p simple path of length r, p 1 , p r+1 ∈ N (v), v / ∈ p} . v N 0 (v) N 1 (v) N 2 (v)We generalize 1-WL in (1) as follows.Definition 7. We define the r-loopy Weisfeiler-Leman (r-WL) test by the following color update:EQUATIONwhere cEQUATIONr (p r+1 ) is the sequence of colors of nodes in the path.We denote by c (t) r (G) the final graph output after t iterations of r-WL, i.e.,c (t) r (G) = HASH r c (t) r (v) | v ∈ V (G) ,and by c r (G) the stable coloring after convergence. The stable coloring c r serves as graph invariant and will be referred to as r-WL. 
expressivity of r-wl: 
 We analyze the expressivity of r-WL in terms of its ability to distinguish non-isomorphic graphs, subgraph-count, and homomorphism-count motifs. The proofs for all statements are in Appendix D.It is straightforward to check that 0-WL corresponds to 1-WL, since N 0 (v) = N (v) for all nodes v. However, increasing r leads to a strict increase in expressivity.Proposition 1. Let 0 ≤ q < r. Then, r-WL is strictly more powerful than q-WL. In particular, every r-WL is strictly more powerful than 1-WL.This shows that the number of graphs we can distinguish monotonically increases with r. We empirically verify this fact on several synthetic datasets in Section 7.Recent studies highlight limitations in the ability of certain graph invariants to subgraph-count cycles.For instance, 1-WL cannot subgraph-count cycles (Chen et al., 2020, Theorem 3.3) , while 3-WL can only subgraph-count cycles of length up to 7 (Arvind et al., 2020, Theorem 3.5) . Similarly, Subgraph GNNs have limited cycle-counting ability (Huang et al., 2022, Proposition 3.1) . In contrast, r-WL can count cycles of arbitrary length, as shown in the following statement.Theorem 1. For any r ≥ 1, r-WL can subgraph-count all cycles with at most r + 2 nodes.Since 3-WL cannot subgraph-count any cycle with more than 7 nodes, Theorem 1 implies that 6-WL is not less powerful than 3-WL. This observation generalizes to any k-WL, as shown next.Corollary 1. Let k ∈ N. There exists r ∈ N, such that r-WL is not less powerful than k-WL. Specifically, r ∈ O(k 2 ), with r ≤ k(k+1)-2 for even k and r ≤ (k+1) 2-2 for odd k.The r-WL color refinement algorithm surpasses the limits of the k-WL hierarchy while only using local computation. This is particularly important since already 3-WL is computationally infeasible, whereas our method can scale efficiently to higher orders if the graphs are sparse, which is commonly the case in real-world applications.The following section unveils a close connection between the expressivity of r-WL and cactus graphs (Harary et al., 1953) , a significant class between trees and graphs with tree-width 2.Definition 8. A cactus graph is a graph where every edge lies on at most one simple cycle. For r ≥ 2, an r-cactus graph is a cactus where every simple cycle has at most r vertices. We denote by M the set of all cactus graphs, and by M r the set of all q-cactus graphs for q ≤ r.Figure 6 shows two examples of cactus graphs. From the expressivity perspective, the ability to homomorphism-count cactus graphs establishes a lower bound strictly between the homomorphismcounting capabilities of 1-WL and 3-WL (Neuen, 2024) , as cactus graphs are a strict superset of all trees and a strict subset of all graphs of treewidth two. With this in mind, we are now ready to present our significant result on the homomorphism expressivity of our r-WL algorithm.Theorem 2. Let r ≥ 0. Then, r-WL can homomorphism-count M r+2 .We refer to Appendix G for a detailed proof of Theorem 2, which is fairly involved and requires defining canonical tree decompositions of cactus graphs and unfolding trees of r-WL. Demonstrating their strong connection, we then follow the approach in (Dell et al., 2018; B. Zhang et al., 2024) to decompose homomorphism counts of cactus graphs. In fact, we prove a more general result, showing that r-WL can count all fan-cactus graphs, see Appendix G for more details.The class M 2 contains only forests; hence, Theorem 2 implies the standard results on the ability of 1-WL to count forests. Since forests are the only class of graphs 1-WL can count, Theorem 2 implies that r-WL is always strictly more powerful than 1-WL, corroborating the claim in Proposition 1.The implications of Theorem 2 are profound: it establishes that r-WL can homomorphism-count a large class of graphs. Specifically, Theorem 2 provides a quantitative expressivity measure that enables comparison of r-WL's expressivity with other WL variants and GNNs. This comparison is achieved by examining the range of graphs that r-WL can homomorphism-count against those countable by other models, as detailed in works by Barceló et al. (2021) and B. Zhang et al. (2024) .For instance, B. Zhang et al. (2024) showed that Subgraph GNNs (Bevilacqua et al., 2021; You et al., 2021; Frasca et al., 2022; Huang et al., 2022) are limited to homomorphism-count graphs with end-point shared NED. Hence, Subgraph GNNs can not homomorphism-count F = , while 1-WL can. Based on this, we can identify pairs of graphs that 1-WL can distinguish but Subgraph GNNs cannot. We summarize these and other implications of Theorem 2 in the following corollary. Corollary 2. Let r ∈ N \ {0}. Then, i) r-WL is more powerful than F-Hom-GNNs, where F = {C 3 , . . . , C r+2 }.ii) 1-WL is not less powerful than Subgraph GNNs. In particular, any r-WL can separate infinitely many graphs that Subgraph GNNs fail to distinguish.iii) For any k > 0, 1-WL is not less powerful than Subgraph k-GNNs. In particular, any r-WL can separate infinitely many graphs that Subgraph k-GNNs fail to distinguish. iv) r-WL can subgraph-count all graphs F such that spasm(F ) ⊂ M r+2 , where spasm(F ) := {H ∈ G | ∃ surjective h ∈ Hom(F, H)}. In particular, if 1 ≤ r ≤ 4, then r-WL can subgraph-count all paths up to length r + 3.A detailed explanation of Subgraph (k-)GNNs, F-Hom-GNNs, along with the proofs of Corollary 2, can be found in Appendix H. Finally, we note that Theorem 2 states a loose lower bound on the homomorphism expressivity of r-WL. This observation opens the avenue for future research to explore tight lower bounds, or upper bounds, on the homomorphism expressivity of r-WL. 
loopy message passing: 
 In this section, we build a GNN emulating r-WL. Definition 9. For t ∈ {0, . . . , T -1} and k ∈ {0, . . . , r}, r-MPNN applies the following message, update and readout functions:EQUATIONand final readout layer c(T ) r (G) = h c (T ) r (v) | v ∈ V (G) .In the following statement, we link the expressive power of r-MPNN and r-WL. Theorem 3. For fixed t, r ≥ 0, t iterations of r-WL are more powerful than r-MPNN with t layers. Conversely, r-MPNN is more powerful than r-WL if the functions f (t) , g (t) in (3) are injective.The previous result derives conditions under which r-MPNN is as expressive as r-WL. To implement r-MPNN in practice, we choose suitable neural layers for f(t)k , g (t) , and h in Definition 9. As a consequence of (Xu et al., 2019, Lemma 5) , the aggregation function in (3) can be written asf (t+1) k c (t) k (p) | p ∈ N k (v) := f   p∈N k (v) g(p)   ,for suitable functions f, g. Since 1-WL is injective on forests (Arvind et al., 2015) , hence on paths, and since GIN can approximate 1-WL (Xu et al., 2019) , we choose f = MLP and g = GIN. Hence, r-GIN is defined as an r-MPNN that updates node features viax (t+1) r (v) := MLP   x (t) r (v) + (1 + ε 0 ) u∈N0(v) x (t) r (u) + r k=1 (1 + ε k ) p∈N k (v) GIN k (p)   . (4)To reduce the number of learnable parameters in (4), the GIN k can be shared among all k. Nothing prevents from choosing a different path-processing layer; we opted for GIN because it is simple yet maximally expressive on paths. We refer to Figure 1 for a visual depiction of r-GIN.The complexity of r-GIN is O(|E| + v∈V (G) r k=1 2k|N k (v)|).The former addend is the standard message complexity, while the latter arises from applying GIN to paths of length k ≤ r. This implies that our model's complexity scales linearly with the number of edges, and with the number of paths within N k (v). The number of such paths is typically less than the number of edges. For example, ZINC12K has overall 598K edges while only containing 374K paths in N r (v) for 1 ≤ r ≤ 5. Hence, the runtime overhead is small in practice. Compared to 3-WLGNN (Dwivedi et al., 2022a) , which has the same cycle-counting expressivity, our model requires ca. 10 seconds/epoch while 3-WLGNN takes ca. 329.49 seconds/epoch on ZINC12K. Our runtime is comparable to that of GAT, MoNet, or GatedGCN (see Table 10 for a thorough comparison).Comparison with (Michel et al., 2023) PathNN updates node features by computing all possible paths starting from each node. In contrast, our approach selects paths between distinct neighbors, potentially resulting in fewer paths. For instance, a tree's r-neighborhoods (r ≥ 1) are empty, while counts of paths between nodes are quadratic. Notably, Michel et al. (2023) do not explore the impact of increasing the path length on architecture expressiveness, a consideration we address (see, e.g., Proposition 1 and Corollary 1). Another significant contribution of our work, which we assert does not hold (at least not trivially) for PathNN, is the provable ability to subgraph-count cycle graphs (see, e.g., Theorem 1) and homomorphism-count cactus graphs (see, e.g., Theorem 2). 
experiments: 
 All instructions to reproduce the experiments are available on GitHub (MIT license). Additional information on the training and test details can be found in Appendix C.Expressive Power. We showcase the expressive power of r-GIN on synthetic datasets:• GRAPH8C (Balcilar et al., 2021) comprises 11 117 connected non-isomorphic simple graphs on 8 nodes; 312 pairs are 1-WL equivalent but none is 3-WL equivalent.• EXP_ISO (Abboud et al., 2022) comprises 600 pairs of 1-WL equivalent graphs. Figure 3 : Indistinguishable pairs at initialization, symlog scale. For GRAPH8C and EXP_ISO, we report the proportion of indistinguished pairs: 2 graphs are deemed indistinguishable if the L 1 distance of their embeddings is less than 10 -3 . For COSPECTRAL10 and SR16622, we report the L 1 distance between graph embeddings. We report the mean and standard deviation over 100 seeds. • COSPECTRAL10 (van Dam et al., 2003) : the dataset comprises two cospectral 4-regular non-isomorphic graphs on 10 nodes which are 1-WL equivalent (see, e.g., Figure 8a ).• SR16622 (Michel et al., 2023) comprises two strongly regular graphs on 16 nodes, namely the Shrikhande and the 4×4 rook graph, which are 3-WL equivalent (see, e.g., Figure 8b ).The goal is to check whether the model can distinguish non-isomorphic pairs at initialization. The results are shown in Figure 3 .Additionally, Table 1 shows the performance on BREC (Wang et al., 2024) , which includes 400 pairs of non-isomorphic graphs ranging from 1-WL to 4-WL equivalent. The baselines include PPGN, which is 3-WL equivalent and can count up to 7-cycles and homomorphism-count all graphs of tree-width 2; NestedGNN which is between 1-WL and 3-WL; GSN which is more powerful than 1-WL but whose expressive power depends on the chosen pattern.Finally, Figure 4 reports the performance on synthetic classification tasks:• EXP, CEXP (Abboud et al., 2021) require expressive power beyond 1-WL.• CSL (Murphy et al., 2019) comprises 150 cycle graphs with skip links (see, e.g., Figure 8c ). The task is to predict the length of the skip link.Counting Power. Following (B. Zhang et al., 2024) , we use the SUBGRAPHCOUNT dataset (Chen et al., 2020) to test the ability to homomorphism-and subgraphs-count exemplary motifs. There is a strict hierarchy in the expressive power of the baselines: MPNN Subgraph GNN local 2-GNN local 2-FGNN. These variants, apart from MPNNs, are more expressive than 1-WL and can subgraph-count up to 7-cycles.Real-World Datasets. We experimented with three benchmark datasets: ZINC250K (Irwin et al., 2012) , ZINC12K (Dwivedi et al., 2022a) , and QM9 (Wu et al., 2018) which consist of 250 000, 12 000, and 130 831 molecular graphs, respectively. We report the mean and standard deviation over 4 random seeds. For ZINC250K and ZINC12K, we selected as baseline models standard MPNNs (GIN, GCN, GAT), Subgraph GNNs (NestedGNN, GNNAK+, SUN), domain-agnostic GNNs fed with substructure counts (GSN, CIN), a GNN processing paths (PathNN), and expressive GNNs with provable cycle counting power (HIMP, SignNet, I2-GNN, DRFWL). Following the standard procedure, we kept the number of parameters under 500K (Dwivedi et al., 2022a) for ZINC12K.The results are detailed in Table 3 .For the QM9 dataset, we followed the setup of (Huang et al., 2022; Zhou et al., 2023) . Specifically, the test MAE is multiplied by the standard deviation of the target and divided by the corresponding conversion unit. The baseline results and models were obtained from (Zhou et al., 2023) , including expressive GNNs with provable cycle counting power. We omit methods that use additional geometric features to focus on the model's expressive power. The results are presented in Table 4 . The results in Figures 3 and 4 and Table 1 constitute a strong empirical validation of our theory: increasing r leads to more expressive r-MPNN. Albeit 6-WL is not less powerful than 3-WL (see, e.g., Section 5.2), in practice, smaller values of r can already distinguish pair of graphs that are 3-WL equivalent, such as the Shrikhande and the (4×4) rook graphs. In the BREC dataset, 4-GIN distinguishes all pairs of strongly regular graphs, significantly outperforming 3-WL (0/50 graphs). Notably, 4-GIN can already distinguish 257 out of 400 total pairs of graphs, surpassing other expressive GNNs like PPGN (233/400), theoretically equivalent to 3-WL, and NestedGNN (166/400). Refer to (Wang et al., 2024, Table 2) for detailed baseline results.The results in Table 2 further substantiate our theory, as r-WL can effectively count cycles of length r+2 (see, e.g., Theorem 1).On molecular datasets, we observe that r-GIN, although designed for subgraph-counting cycles and homomorphism-counting cactus graphs, is highly competitive. Notably, we outperform the baseline 0-GIN by 226% on ZINC12K and 400% on ZINC250K and surpass domain-agnostic methods such as CIN or GSN. We conjecture that this is attributed to straightforward optimization, driven by the simplicity of the architecture (see, e.g., Figure 1 ) and its inductive bias towards counting cycles.Limitations Path calculations can become infeasible for dense graphs due to O(N d r ) complexity, where N is the number of nodes and d is the average degree. However, for sparse graphs, the runtime remains reasonably low. For instance, preprocessing ZINC12K for r = 5 takes just over a minute. 
conclusion: 
 In this paper,we introduce a novel hierarchy of color refinement algorithms, denoted as r-WL, which incorporates an augmented neighborhood mechanism accounting for nearby paths. We establish connections between r-WL and the classical k-WL. We construct a GNN (r-MPNN) designed to emulate and match the expressive powerof r-WL. Theoretical and empirical evidence support the claim that r-MPNN can effectively subgraph-count cycles and homomorphism-count cactus graphs.Future research could focus on precisely characterizing the expressivity of r-WL tests by identifying the maximal class of graphs that r-WL can homomorphism-count. This would facilitate comparisons by constructing pairs of graphs that r-WL cannot separate, but other WL variants can.Another promising direction involves exploring the generalization capabilities of GNNs with provable homomorphism-counting properties. The ability to homomorphism-count certain motifs could provide a mathematical framework to support the intuitive notion that the capacity to count relevant features may improve generalization. We observed this improved generalization experimentally in our ablation study on ZINC12K (see, e.g., Table 8 ).Zhang, B., Gai, J., Du, Y., Ye, Q., He, D., and Wang, L. (2024) . "Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness". In: International Conference on Learning Representations (ICLR). Zhang, M. and Li, P. (2021). "Nested Graph Neural Networks". In: Advances in Neural Information Processing Systems (NeurIPS), pp. 15734-15747. Zhao, L., Jin, W., Akoglu, L., and Shah, N. (2022) . "From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness". In: International Conference on Learning Representations (ICLR). Zhou, J., Feng, J., Wang, X., and Zhang, M. (2023) . "Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power". In: Advances in Neural Information Processing Systems (NeurIPS). 
 
 Appendix: Bijective Homomorphism Isomorphism Figure 5 : Examples of non-injective homomorphism (row 1), subgraph isomorphism (row 2), bijective homomorphism with non-homomorphic inverse (row 3), and isomorphism (row 4). For better clarity, the mappings h : V (F ) → V (G) are visually represented with colors, where F is consistently on the left, and G is on the right in each row.v v N 0 (v) N 1 (v) (a) r = 0 v v N 0 (v) N 2 (v) (b) r = 1Figure 6: Example of two non-isomorphic graphs that are r-WL equivalent but not (r+1)-WL equivalent: a chordal cycle (left) and a cactus graph (right). 5 6 4 3 2 1 (a) Input graph F . 6, {4, 5} 4, {6, 3} 3, {2, 4} 2, {1, 3} 1, {2, 3} 3, {1, 4} 4, {5, 3} 5, {4, 6} 3, {1, 2} 4, ∅ 3, ∅ 4, {5, 6} 6, ∅ 5, ∅ 1, ∅ 2, ∅ (b) Fürer graph G(F ): hom(F, G(F )) = 68. 6, {4, 5} 4, {6, 3} 3, {2, 4} 2, {1, 3} 1, {2, 3} 3, {1, 4} 4, {5, 3} 5, {4, 6} 3, {1, 2} 4, ∅ 3, ∅ 4, {5, 6} 6, ∅ 5, ∅ 1, ∅ 2, ∅ (c) Twisted Fürer graph H(F ): hom(F, H(F )) = 34.It is possible to uplift the expressive power of WL by considering higher-order interactions. The simplest higher-order variant of WL is the k-dimensional Weisfeiler-Leman test, denoted by k-WL.Given a graph G with nodes V (G) and edges E(G), the algorithm generates a new graph H where each node is a k-tuple of elements of V (G)V (H) = v = {v i } k i=1 | v i ∈ V (G) = V (G) k ,and edges E(H) are built among those k-tuples that differ in one entry onlyE(H) = {{v, u} | d H (v, u) = 1 , u, v ∈ V (H)}where d H is the Hamming distance. The algorithm assigns to each node v ∈ V (H) an initial color depending on the isomorphic type of the induced subgraph G[v]. The color refinements scheme is exactly (1) applied to H. While H can be generated by a simple algorithm, the approach quickly becomes impractical as the number of nodes and edges grows exponentially in k.(a) Input graphs.(b) 1-WL after one iteration.(c) 3-WL at initialization.(d) 1-WL after one iteration.Figure 9 : The input graphs cannot be distinguished by 1-WL, since the color distribution after convergence of the algorithm is equal. 3-WL can distinguish them at the cost of creating new dense graphs. Our proposed 1-WL can distinguish the two graphs heeding the original graph sparsity.Our model is implemented in PyTorch (BSD-3 license) (Paszke et al., 2019) , using PyTorch Geometric (MIT license) (Fey et al., 2019) . The r-neighborhoods are computed with NetworkX (Creative Commons Zero v1.0 Universal) (Hagberg et al., 2008) as preprocessing. Hyperparameters on real-world datasets were tuned using grid search; for synthetic experiments, we fixed one configuration of hyperparameters. All experiments were run on an internal cluster with Intel Xeon CPUs (28 cores, 192GB RAM) and GeForce RTX 3090 Ti GPUs (4 units, 24GB memory each), as well as Intel Xeon CPUs (32 cores, 192GB RAM) and NVIDIA RTX A6000 GPUs (3 units, 48GB memory each).All models are trained with Adam optimizer (Kingma et al., 2015) .The SR16622 dataset is retrieved from the official PATHNN repository (MIT license) (Michel et al., 2023) . The GRAPH8C dataset is downloaded from Australian National University webpage (Creative Commons Attribution 4.0 International (CC BY 4.0) license). The EXP, EXP_ISO, and CEXP datasets are downloaded from GNN-RNI official repository (GPL-3.0 license) (Abboud et al., 2021) , while the corresponding splits are generated via Stratified 5-fold cross-validation. The CSL dataset is provided by torch_geometric, while the corresponding splits are taken from PathNN official repository. The SUBGRAPHCOUNT dataset is taken from the official repository (MIT license) of (Zhao et al., 2022) . The BREC dataset is downloaded from its official repository (MIT license) (Wang et al., 2024) . The configuration of hyperparameters can be found in Table 5 . For the synthetic datasets, we fixed one configuration and studied the effect of increasing r on the expressive and counting power of the architecture.For the SR16622, GRAPH8C, EXP_ISO, and COSPECTRAL10 datasets, we report the mean and standard deviation over 100 random seeds. For the EXP, CEXP, and CSL datasets, we report the mean and standard deviation of 5-fold cross-validation. For BREC, we follow the original setup and perform an α-level Hotellings T-square test; see (Wang et al., 2024) for more details. For the SUBGRAPHCOUNT dataset, we report the mean and standard deviation over 4 random seeds, using the original splits from (Zhao et al., 2022) . All real-world datasets come with edge features. We use an encoder layer, followed by a linear layer to encode node, edge features, and atomic types before passing them to the r-GIN. Within the r-GIN layers, we process the edge features via a 2-layered learnable MLP, and replace the GIN in (4) by GINE layers (Hu* et al., 2020a) . After t rounds of r-GIN layer, we apply a two-layered MLP as decoder layer. In all experiments, BatchNorm1D (Ioffe et al., 2015) is used in the MLP layers. We refer to Figure 1 for a depiction of the architecture. We begin by recalling some core concepts that are relevant for Section 5 and the proofs therein.Definition 10. A node invariant ζ (•) is a mapping that assigns to each graph G ∈ G a function ζ G : V (G) → P , which satisfies ∀v ∈ V (G), ζ G (v) = ζ H (h(v)),where H is any graph isomorphic to G and h is the corresponding isomorphism from H to G.The following definition enables us to compare the expressive power of different node invariants.Definition 11 (Node Invariant Refinement). Given two node invariants γ and ζ. We say that ζ refines γ if for every fixed graph G and nodesu, v ∈ V (G), it holds ζ G (u) = ζ G (v) ⇒ γ G (u) = γ G (v).We write ζ γ.We emphasize that every node invariant ζ induces a graph invariant A[γ] by collecting the multiset, i.e., G → {{ζ G (v)}} v∈V (G) . We denote the induced graph invariant of a node invariant γ as A[γ].The following lemma establishes a connection between the expressive power of two node invariants (see Definition 11) and that of their induced graph invariants (see Definition 3).Lemma 1. Let ζ, γ be node invariant. If ζ γ, then A[ζ] is more powerful than A[γ].Proof. Let G, H be two graphs, and let P be the underlying palette of ζ, γ. Consider the functionφ : P -→ P, ζ(u) → γ(u) ∀u ∈ V (G) ∪ V (H).As a consequence of ζ γ, φ is well-defined, sinceζ(u) = ζ(v) =⇒ (φ • ζ) (u) = γ(u) = γ(v) = (φ • ζ) (v). Assume that A[ζ](G) = A[ζ](H), i.e, {{ζ(u) | u ∈ V (G)}} = {{ζ(v) | v ∈ V (H)}} .As φ is well-defined, we have{{φ • ζ(u) | u ∈ V (G)}} = {{φ • ζ(x) | v ∈ V (H)}} , which leads to A[γ](G) = A[γ](H).E Appendix for Section 5.1In this section, we provide the proof of Proposition 1 from the main paper. Proposition 1. Let 0 ≤ q < r. Then, r-WL is strictly more powerful than q-WL. In particular, every r-WL is strictly more powerful than 1-WL.Proof of Proposition 1. Let r ≥ 0. We aim to prove that (r + 1)-WL is strictly more powerful than r-WL. We begin by demonstrating that (r + 1)-WL is more powerful than r-WL.To establish this, we rely on Lemma 1. Specifically, we demonstrate that the underlying (r + 1)-WL node invariant c r+1 refines c r . Moreover, we go beyond and show that the node invariant c(t) r+1 refines c (t)r at every iteration t ≥ 0, which shows that t iterations of (r + 1)-WL are more powerful than t iterations of r-WL.For this purpose, let G be a graph with node set V (G). For t = 0, c(0) r+1 c (0)r since both algorithms start with the same labels. By induction, we assume thatEQUATIONholds; we need to prove that (5) impliesEQUATIONSince HASH in Definition 7 is injective, c(t) r+1 (u) = c (t) r+1 (v) in (5) leads to c (t) r+1 (p) | p ∈ N q (u) = c (t) r+1 (p) | p ∈ N q (v)for all q ∈ {0, . . . , r}. The assumption c(t) r (u q l,k ) = c (t)r (v q l,k ) in ( 5) is satisfied for every path u q l = u q l,k ∈ N q (u) and v q l = v q l,k ∈ N q (v) for q = 0, . . . , r, l = 1, . . . , |N v | and k = 1, . . . , q + 1. Hence,c (t) r (p) | p ∈ N k (u) = c (t) r (p) | p ∈ N k (v)Inputting this into Definition 7, we get (6), i.e, c(t+1) r.The "strictly" can be deduced as follows. The cycle graph on (2r + 6) nodes equipped with a chord between nodes 1 and r + 4 is r-WL equivalent to the graph consisting of two (r + 3)-cycles connected by one edge; however, they are not (r + 1)-WL equivalent (see, e.g., Figure 6 ).F Appendix for Section 5.2The goal of this subsection is to provide a proof for Theorem 1 and Corollary 1. In fact, we present and prove a more general statement. Specifically, for a graph G and v ∈ V (G), we introduce the node invariant sub(F x , G v ), defined as the count of subgraph isomorphisms from F to G that are rooted, meaning that x is mapped to v. Let us denote this node invariant as sub(F x , •). Our result establishes that c(1) r (•) refines sub(C x , •) for every cycle graph C with at most r nodes. In simpler terms, c(1) r can determine how often node v appears in a cycle C. Lemma 2. Let r ≥ 1. For every cycle graph C with at most r + 2 nodes and x ∈ V (C), it holds c(1)r (•) sub(C x , •).Proof of Lemma 2. Let G be any graph, u, v ∈ V (G), and q = 1, . . . , r + 2. Let C be a cycle graph with q nodes. It is important to note that for every x 1 , x 2 ∈ C, we have sub(C x1 , G v ) = sub(C x2 , G v ) since every node in C is automorphic to each other. Therefore, we can arbitrarily choose any x ∈ V (C).sub (C x , G u ) = sub (C x , G v ) =⇒ c (1) r (u) = c (1) r (v)The number of injective homomorphisms from the q-long cycles C x to G v , i.e., sub(C a q , G v ), is equal to the number of paths of length (q -2) between distinct neighbors of v.The neighborhood N (q-2) (v) comprises exactly all paths of length (q -2) between any two distinct neighbors of v. Therefore,sub (C x , G v ) = N (q-2) (v) . Thus sub (C x , G u ) = sub (C x , G v ) =⇒ N (q-2) (u) = N (q-2) (v) , which implies c (0) q-2 (p) : p ∈ N (q-2) (u) = c (0) q-2 (p) : p ∈ N (q-2) (v) .Finally, as HASH in Definition 7 is injective, we get the thesis c(1)q-2 (u) = c (1) q-2 (v).Now, Theorem 1 from the main paper is a simple corollary of Lemma 2. Theorem 1. For any r ≥ 1, r-WL can subgraph-count all cycles with at most r + 2 nodes.Proof of Theorem 1. Combining Lemma 2 and Lemma 1, we get that c (1)r (G) = c (1) r (H), we have A [sub(C x , •)] (G) = A [sub(C x , •)] (H). Hence, by definition of induced graph invariants, {{sub(C x , G v ) | v ∈ V (G)}} = {{sub(C x , H w ) | w ∈ V (H)}} . Hence, 1 n v∈V (G) sub(C x , G v ) = 1 n w∈V (H) sub(C x , H w ),which is equivalent to sub(C, G) = sub(C, H).We proceed to restate Corollary 1 and provide its proof.Corollary 1. Let k ∈ N. There exists r ∈ N, such that r-WL is not less powerful than k-WL.Specifically, r ∈ O(k 2 ), with r ≤ k(k+1)-2 for even k and r ≤ (k+1) 2-2 for odd k.Proof of Corollary 1. Let k > 0. We need to show that there exist r k ∈ N and a pair of graphs G, H,such that k-WL(G) = k-WL(H) and r k -WL(G) = r k -WL(H).The hereditary treewidth hdtw(F ) of a graph F is the maximum treewidth of ϕ(F ) where ϕ is an edge surjective homomorphism. Neuen (2024) has shown that k-WL can subgraph-count a graph F if and only if hdtw(F ) ≤ k. This directly implies that for F with hereditary treewidth larger than k, there exist graphsG F , H F with k-WL(G F ) = k-WL(H F ) and sub(F, G) = sub(F, H).Since the hereditary tree-width of cycle graphs is not uniformly bounded (Arvind et al., 2020) , for every k > 0 there exists a cycle C c k of length c k ∈ N with hereditary treewidth larger than k. SettingF = C c k concludes the existence proof with r k = c k -2.To see that r k ∈ O(k 2 ), note that the complete graph K n on n vertices has treewidth n -1 and exactly n 2 edges. For odd n, K n is Eulerian, i.e., there exists an edge surjective homomorphism from a cycle to K n which uses each edge exactly once, i.e., from C ( n 2 ) . If n is odd, the minimum T -join which makes K n Eulerian contains exactly n 2 edges (see, e.g., Korte et al., 2018) . As a result, there exists an edge surjective homomorphism from C ( n 2 ) to K n if n is odd, and an edge surjective homomorphism from C ( n 2 )+ n 2 to K n if n is even. This implies that hdtw(C c k ) > k forc k = k+1 2 + k+1 2 . Hence, r k := c k -2 ∈ O(k 2 ).G Appendix on Homomorphism Counting and Section 5.3In this section, we provide background information and all proofs related to homomorphism counts. We begin by introducing additional definitions and notation. Definition 12 (Induced Subgraph).Let G = (V (G), E(G)) and S ⊂ V (G). The induced subgraph G[S] of G over S is defined as the graph G[S] with vertices V (G[S]) = S and edges E(G[S]) = {{u, v} ∈ E(G) | u, v ∈ S}.The following definition indicates whether a pair of nodes is connected by an edge or not. Definition 13 (Atomic Type). For a tuple of nodes (u 1 , u 2 ), the atomic type atpG ((u 1 , u 2 )) of G over (u 1 , u 2 ) indicates where {u 1 , u 2 } ∈ E(G), i.e., atp G ((u 1 , u 2 )) = 1 if {u 1 , u 2 } ∈ E(G) and zero otherwise.We continue by defining tree graphs, an important class of graphs closely related to the 1-WL test. Definition 14 (Tree Graph). A graph T is called a tree (graph) if it is connected and does not contain cycles. A rooted tree T s = (V (T s ), E(T s )) is a tree in which a node s ∈ V (T s ) is singled out. This node is called the root of the tree. For each vertex t ∈ V (T s ), we define its depth dep T s (t) := dist T s (t, s), where dist denotes the shortest path distance between t and s.The depth of T s is then the maximum depth among all nodes t ∈ V (T ). We define Desc The remainder of this section is structured as follows. Appendix G.1 introduces the basics of tree decompositions. In Appendix G.2, we present the class of fan cactus graphs, encompassing all cactus graphs, and develop its canonical tree decomposition. We present an alternative formulation of r-WL in Appendix G.3 for technical reasons. Subsequently, in Appendix G.4, we define the unfolding tree of r-WL and illustrate its relation to the r-WL colors and canonical tree decompositions of fan cactus graphs. Finally, in Appendix G.4.1, we establish the groundwork to conclude the proof of Theorem 2, a simple corollary of all the results in this section.Along with its notation, this subsection closely adheres to the conventions outlined by B. Zhang et al.(2024, Section C). We start with a formal definition of a tree decomposition for a graph. Definition 15 (Tree Decomposition). G) satisfying the following conditions:Let G = (V (G), E(G)). A tree decomposition of G is a tree T = (V (T ), E(T )) together with a function β T : V (T ) → 2 V (1. Each tree node t ∈ V (T ) is mapped to a non-empty subset of vertices β T (t) ⊂ V (G) in G, referred to as a bag. We say tree node t contains vertex u if u ∈ β T (t).2. For each edge {u, v} ∈ E(G), there exists at least one tree node t ∈ V (T ) such that {u, v} ⊂ β T (t).3. For each vertex u ∈ V (G), all tree nodes t containing u form a connected subtree, i.e., the induced subgraphT [{t ∈ V (T ) : u ∈ β T (t)}] is connected.If (T, β T ) is a tree decomposition of G, we refer to the tuple (G, T, β T ) as a tree-decomposed graph.The width of the tree decomposition T of G is defined asmax t∈V (T ) |β T (t)| -1.If T has root s, we also denote it as (G, T s , β T ). Definition 16 (Treewidth). The treewidth of a graph G, denoted as tw(G), is the minimum positive integer k such that there exists a tree decomposition of width k.Cactus graphs play a crucial role in graph theory due to their unique structural properties. Before delving into their canonical tree decomposition, we define the concept of a rooted r-cactus graph. To simplify the notation, we assume that graphs in this section are connected and that V (G) ⊆ N for all graphs G. Further, we assume that r ∈ N throughout this section. Definition 17 (Rooted r-Cactus Graph). A cactus graph is a graph where every edge lies on at most one simple cycle. An r-cactus graph is a cactus graph where every simple cycle has at most r vertices.A rooted cactus (graph) G s is a cactus graph G with a root node s ∈ V (G).Now, we introduce the notion of a fan cactus, which is an essential concept for our subsequent discussions on the canonical tree decomposition of these graphs. Definition 18 (Fan Cactus). Let G s be a rooted r-cactus. For every simple cycle C in G let v C be the unique vertex in C that is closest to s. We obtain a fan r-cactus F s from a rooted r-cactus G s by adding an arbitrary number of edges {v C , w} to any cycle C with w ∈ V (C). Let M r+2 be the class of graphs F with s ∈ V (F ) such that F s is a fan r-cactus. Remark 1. Every r-cactus is a fan r-cactus. Every fan r-cactus is outerplanar. Every outerplanar graph has tree-width at most 2.Figure 10 shows an example of a fan 6-cactus. As fan cacti are outerplanar, graph isomorphism can be decided in linear time. One way to do so is to use a canonicalization function, that maps graphs to a unique representative of each set of isomorphic graphs. We denote the set of all such representatives as M r+2 / ∼ = ⊆ M r+2 . Lemma 3 (Colbourn et al. (1981) ). There exists a function canon :M r+2 → M r+2 / ∼ = such that 1. G ∼ = canon(G) 2. G ∼ = H ⇐⇒ V (canon(G)) = V (canon(H)) ∧ E(canon(G)) = E(canon(H)).Moreover, given G ∈ M r+2 , canon(G) can be computed in linear time.For each G ∈ M r+2 we denote the isomorphism between G and canon(G) as canon G . Colbourn et al. (1981) describe a bottom-up algorithm to obtain canon(G) of a fan r-cactus G. We will implicitly use the results of this canonicalization to define a canonical tree decomposition of fan r-cacti. The crucial point in the algorithm is a simple way to decide which "direction" to use when dealing with a cycle in the underlying cactus graph. Each undirected, rooted cycle allows for a choice between two directions when building a tree decomposition. We will first define a tree decomposition for a rooted cycle which depends on a choice of direction and then define a canonical direction of cycles in G based on canon G . Definition 19 (Tree Decomposition of Rooted Cycle). Let C n be a cycle graph on n nodes v 0 to v n-1 . The path T on nodes w 1 , . . . , w 2n-3 with bags β(w 1 ) = {v 0 , v 1 } and for i ≥ 2β(w i ) = β(w i-1 ) ∪ v i/2+1 if i is even β(w i-1 ) \ v (i-1)/2 if i is oddis a tree decomposition of C n . We say that v 0 and v 1 correspond to w 1 and v i corresponds to w 2i-1 for i ≥ 2.A depiction of the tree decomposition T 0 (right) of C 6 (left) is shown below. Note that we have to choose one of two possible orientations of the undirected cycle to construct T 0 . We address this choice in the next definition.0 1 2 3 4 5 {0, 1} {0, 1, 2} {0, 2} {5, 0} {0, 4, 5} {0, 2, 3} {0, 3} {0, 3, 4} {0, 4}Definition 20 (Canonical Tree Decomposition of Undirected Rooted Cycle). Let F s be a fan r-cactus and C be a simple cycle in the underlying cactus G. Let v C , v 1 , . . . , v n-1 and v C , v n-1 , . . . , v 1 be the two directions of C rooted at v C . We define the canonical tree decomposition of C in G as the tree decomposition of the smaller of the two orientations canon F (v C ), canon F (v 1 ), . . . , canon F (v n-1 ) and canon F (v C ), canon F (v n-1 ), . . . , canon F (v 1 ).The choice of "smaller" does not matter as long as it defines a total order. One can, for example, use a lexicographical order. Based on Definition 20, we now define a canonical tree decomposition of fan cactus graphs, in the sense that any two isomorphic fan cactus graphs will have isomorphic tree decompositions. Definition 21 (Canonical Tree Decomposition of Fan r-Cactus Graphs). Let F s be a fan r-cactus and G s its underlying r-cactus. We define the canonical tree decomposition T s of F rooted at s as follows 1. Node Gadget: For all v ∈ V (F ) add a node t to V (T ) and set β(t) = {v}. We choose s such that β(s) = {s}.2. Tree Edge Gadget: For all {v, w} ∈ E(G) that are not on a simple cycle in F add a nodex {v,w} to V (T ) with β(x {v,w} ) = {v, w} and edges v, x {v,w} and w, x {v,w} to E(T )3. Cycle Gadget: For each (undirected) cycle C in the underlying cactus G, add a copy of its canonical tree decomposition T v C C of C rooted at v C to T and connect nodes in it to the corresponding node gadgets.See Figure 10 for an illustration. For the discussions in subsequent sections, we introduce the following definition. C 2 v C 1 v C 2 v C 3 {7, 12} {12} {7} {7, 8} {8} {7, 8, 9} {7, 9} {9} {7, 9, 10} {7, 10} {10} {7, 10, 11} {7, 11} {11} {7, 11, 12} {13} {12, 13} {4} {1} {2} {1, 4, 3} {1, 4} {1, 2} {1, 3, 2} {1, 3} {3} {4, 7} {2, 5} {2, 6} {2, 5, 6} {6} {5}Figure 10 : Example of a fan 6-cactus F 1 (left) and its canonical tree decomposition (T, 1). The underlying rooted 6-cactus G 1 (on colored, thick edges) of F 1 contains three simple cycles C 1 , C 2 , C 3 . Additional diagonal edges must have v Ci as one endpoint.Definition 22 (Depth in the Canonical Tree Decomposition of Fan r-Cactus Graphs). Let (F, T s ) be a canonical tree decomposition of a fan r-cactus. We define the depth dep(t) of t ∈ V (T ) recursively as follows:1. dep(s) = 0 2. For v ∈ V (T ) with parent node p: dep(v) = dep(p) + 1 if |β(v)| = 1 or |β(p)| = 1 dep(p) otherwiseThe depth of (F, T s ) is then the maximum depth of any node t ∈ V (T s ).Intuitively, for a given fan r-cactus graph F with its canonical tree decomposition T s , Definition 22 captures the depth (see Definition 15) of the tree T s , if cycles in F and the corresponding bags in T s were replaced by single edges.Lemma 4. Let F s be a fan r-cactus. The canonical tree decomposition (F, T s) is a tree decomposition of F s .Proof. We need to show that (1) T is a tree, (2) for every edge e ∈ E(F ) there exists some bag β(v) with e ⊆ β(v), and (3)T [{t ∈ V (T ) : u ∈ β(t)}] is connected.To see that T does not contain cycles, note that we replace each cycle with its cycle gadget, which is a path. It is easy to see that T is connected as G is connected.For (2), note that tree edges e ∈ V (F ) have their own gadget node in x e with β(x e ) = e. Similarly, each edge e on a simple cycle C of the underlying cactus F of G is contained in some bag within the cycle gadget of C. Finally, for diagonal edges {v C , w} ∈ E(F ) \ E(G), v C is contained in any bag of the cycle gadget of C. As a result, {v C , v} is contained in the bag of the corresponding node of v.For (3), note that in the tree edge gadget, nodes t with v ∈ β(t) are connected to the node gadget of v. In the cycle gadget, any node t with w ∈ β(t) is either directly or via its neighbor connected to the node gadget of w if w = v C . As the cycle gadget is connected and v C is in any bag of the gadget, a path to the node gadget of v C exists where every bag contains v C .We conclude this subsection with a formal definition of when two canonical tree decompositions are isomorphic and prove the main result of this section, i.e., that canonical tree decompositions of fan r-cacti G s , H t are isomorphic whenever G s , H t are isomorphic. Definition 23 (Isomorphism between canonical tree-decomposed graphs). Given two canonical tree-decomposed graphs (G, T s ) and ( G, T s), a pair of mappings (ρ, τ ) is called an isomorphism between (G, T s ) and ( G, T s), denoted by (G, T s ) ∼ = ( G, T s), if the following holds:• ρ is an isomorphism between G and G,• τ is an isomorphism between T s and T s,• For any t ∈ T s , we have ρ(βT (t)) = β T (τ (t)). Lemma 5. Let G s ∼ = H t be rooted r-fan cacti. Then (G s , T [G s ]) ∼ = (H t , T [H t ]).Proof. Let ρ be a root preserving isomorphism between G s and H t . According to Lemma 3 then there exist isomorphisms canon G and canonH with ρ = canon G • canon -1 H . We construct τ : V (T [G s ]) → V (T [H t ]) from ρ as follows: It is easy to see that ρ induces a bijective mapping τ between the nodes of T [G s ] andT [H t ] that assigns each gadget node v ∈ V (T [G s ]) to the unique gadget node τ (v) ∈ V (T [H t ]) with β(τ (v)) = ρ(β(v)). By the same argument, τ maps the root of T [G s ] to the root of T [H t ].τ is not an isomorphism between T [G s ] and T [H t ]. That means that w.l.o.g. there exists {v, w} ∈ E(T [G s ]) with {τ (v), τ (w)} / ∈ E(T [H t ]). However, for the bags of v, w it holds canon G (β(v)) = canon H (β(τ (v))) and canon G (β(w)) = canon H (β(τ (w))).This cannot happen, as the addition of edges in Definition 21 depends only on the images of the bags under canon.In this subsection, we define slightly modified versions of 1-WL and r-WL that we consider in the subsequent sections. Definition 24 (Alternative 1-WL and r-WL). The alternative 1-WL test refines vertices' colors asc (t+1) (v) ← HASH c (t) (v), atp(v, u), c (t) (u) | u ∈ V (G) .Equivalently, we define the alternative r-WL viac (t+1) r (v) ← HASH r c (t) r (v), atp(v, u), c (t) (u) | u ∈ V (G) , c (t) r (p) | p ∈ N 1 (v) , . . . c (t) r (p) | p ∈ N r (v) ,It is well-known that both the alternative 1-WL test and the standard 1-WL test are equally powerful (in terms of their expressive power). Similarly, the alternative k-WL test and the standard k-WL test are equally powerful. For the sake of simplicity in the subsequent discussion, we will refer to both the alternative 1-WL and k-WL tests simply as the 1-WL and k-WL tests, respectively. Although this practice may seem like a slight abuse of notation, it is justified because the expressive power of these tests remains unaffected.Finally, as noted in Section 6, we alter the r-WL algorithm slightly by incorporating atomic types into the path representation. Hence, we update node features according toEQUATIONwhere atp(v, p), c(t) r (p) := atp(v, p 1 ), c (t) r (p 1 ) , . . . , atp(v, p q+1 ), c (t) r (p q+1 ) for p = {p i } q+1 i=1 ∈ N q (v).The definition of atomic types atp(•, •) is given in Definition 13. Clearly this version of r-WL is more powerful than the standard version, according to Definition 3. However, it is unclear whether r-WL with atomic types is strictly more powerful than standard r-WL.Given Definition 20, we assume, for the remainder of this appendix, that every fan cactus graph has a unique labeling function, allowing us to select a unique orientation for every cycle in the graph. We call this orientation the canonical orientation. If not otherwise mentioned, we consider the canonical orientation of cycle graphs.We begin this section by introducing a critical concept known as bag isomorphism (Dell et al., 2018; B. Zhang et al., 2024) . Definition 25 (Bag Isomorphism). Let (F, T s ) be a tree-decomposed graph, and G be a graph.A homomorphism f from F to G is called a bag isomorphism from (F, T s ) to G if, for all t ∈ V (T s ), the mapping f is an isomorphism from F [β T s (t)] to G[f (β T s (t))].We denote by BIso((F, T s ), G) the set of all bag isomorphisms from (F, T s ) to G, and set bIso((F, T s ), G) = |BIso((F, T s ), G)|.Moving forward, we proceed to define r-WL unfolding trees, which intuitively construct, for a given graph and a node in the graph, the computational graph of the r-WL algorithm and its canonical tree decomposition. Definition 26 (Unfolding tree of r-WL). Given a graph G, vertex v ∈ V (G) and a non-negative D ∈ Z, the depth-2D r-WL unfolding tree of a graph G ∈ M r+2 at node v, denoted asF (D) (v), T (D) (v), is a tree-decomposition (F, T s ) constructed in the following way:1. Initialization: V (F ) = {v} without edges, and T s only has a root node s withβ T s (s) = {v}. Define a mapping V (F ) → V (G) as π(v) = v.2. Introduce nodes: For each leaf node t with |β T s (t)| = 1 in T s , do the following procedure:Let β T (t) = {g}. For each w ∈ V (G) do the following: a) Add a fresh child t w to t in T s . b) Add a fresh vertex f to F and extend π with [f → w]. c) Define the bag of t w by β T s (t w ) = β T s (t) ∪ {f }. d) Add an edge between f and g if {π(f ), π(g)} ∈ E(G).3. Introduce paths: For each q = 1, . . . , r, do: For each length q path with canonical orientation p = {p i } q+1 i=1 ∈ N q (g), do the following: a) Add a fresh path t p = t {p1} , t {p1,p2} , t {p2} , . . . , t {pq} , t {pq,pq+1} , t {pq+1} to t in T s . b) Add q + 1 fresh vertices f 1 , . . . , f q+1 to F and extend π with [f i → p i ] for every i = 1, . . . , q + 1.EQUATION. . . c) For i = 1, . . . , q, let the bag of t {pi,pi+1} be defined viaβ T s (t {pi,pi+1} ) = β T s (t) ∪ {f i , f i+1 }. d) For i = 1, . . . , q + 1, let the bag of t {pi} be defined via β T s (t {pi} ) = β T s (t) ∪ {f i }.e) For i = 1, . . . , q + 1, add edges between f i and f i+1 . f) Add edges between g and f 1 , . . . , f q+1 such that for every i = 1, . . . , q, we haveF [β T s (t {pi,pi+1} )] = F [{f i , f i+1 , g}] ∼ = G[π(β T s (t {pi,pi+1}))], i.e., add edges between g and f i if and only if there is an edge between {π(g), π(f i )} ∈ E(G).4. Forget nodes: If t is a leaf node of T s with |β T s (t)| = 2 and parent t with |β T s (t)| = 1, do the following: a) Add a fresh child t 1 of t to T s . b) Let f be that vertex introduced at t, that is, we haveβ T s (t) \ β T s (t ) = {f }. c) We set β T s (t 1 ) = {f }.5. Forget paths: If t p = t {p1} , t {p1,p2} , t {p2} , . . . , t {pq} , t {pq,pq+1} , t {pq+1} is a leaf path of T s with parent t of t {p1} , do the following: a) For i = 2, . . . , q + 1, add a fresh child t{pi} to t {pi} . b) Let f 2 , . . . , f q+1 be the vertices introduced at t p , that is, we have β T s (t {pi} ) \ β T s (t ) = {f i }. c) For i = 2, . . . , q + 1, we set β T s ( t{pi} ) = {f i }.We refer to Figure 11 for the depth-2 2-WL unfolding tree of an example graph. Theorem 4. Let r ≥ 1. For any graph G, any vertex v ∈ V (G), and any non-negative integer D, let F (D) (v), T (D) (v) be its depth-2D r-WL unfolding tree at node v. Then, F (D) (v) is a fan r-cactus graph, and T (D) (v) is an r-canonical tree decomposition of F (D) (v). Moreover, the constructed mapping π in Definition 26 is a bag isomorphism from F (D) (v), T (D) (v) to the graph G.Proof. Clear by the definition of the depth-2D unfolding tree of r-WL.We present the following results that fully characterize when two graphs and their respective nodes have the same r-WL colors in terms of their r-WL unfolding trees. Theorem 5. Let r ∈ N. For any two connected graphs G, H, any vertices v ∈ V (G) and x ∈ V (H) and any D ∈ N, it holds: c(D) r (v) = c (D)r (x) if and only if there exists a root preserving isomorphism betweenF (D) (v), T (D) (v) and F (D) (x), T (D) (x) .Proof of "=⇒". The proof is based on induction over D. When D = 0, the theorem obviously holds. Assume that the theorem holds for D ≤ d, and considerEQUATIONfor all i = 1, . . . , n. Also, again since c(d+1) r (v) = c (d+1) r(x), we have for every q = 1, . . . , r,atp(v, u 1 ), c (d) r (u 1 ) , . . . , atp(v, u q+1 ), c (d) r (u q+1 ) | {u 1 , . . . , u q+1 } = u ∈ N q (v) = atp(x, y 1 ), c (d) r (y 1 ) , . . . , atp(x, y q+1 ), c (d) r (y q+1 ) | {y 1 , . . . , y q+1 } = y ∈ N q (x) .In particular, |N q (v)| = |N q (x)| and we can enumerate the paths in N q (v) and N q (x) such thatEQUATIONfor every l = 1, . . . , |N q (v)|.Now, by definition of the r-WL unfolding tree, the graph F (d+1) (v) is isomorphic to the union of: a) all graphs F (d) (w i ) for i = 1, . . . , n, plus additional edges between w i to v if {w i , v} ∈ E(G), and b) all graphs F (d) (p q l,k ) for q = 1, . . . , r, l = 1, . . . , |N q (v)| for any path p q l = p q l,1 , . . . , p q l,q+1 ∈ N q (v). And adding, for k = 1, . . . q, edges between p q l,k and p q l,k+1 . And adding, for k = 1, . . . q + 1, edges p q l,k and v if there is one in G, i.e., if p q l,k , v ∈ E(G).Similarly, the tree T (d+1) (v) is isomorphic to the disjoint union of all trees T (d) (w i ) (for i = 1, . . . , n) and T (d) (p q l,k ) (for q = 1, . . . , r, k = 1, . . . , q + 1 and l = 1, . . . , |N (v)|). Plus adding the following fresh tree nodes and edges: a root node s, nodes t wi (for i = 1, . . . , n) that connects to s and the root of T (d) (w i ). And for q = 1, . . . , r, l = 1, . . . , |N q (v)| for any path p q l ∈ N q (v) a path of length 2q, given by t p q l = t p q l,1, t p q l,1 ,p q l,2 , . . . , t p q l,q ,p q l,q+1, t p q l,q+1, where s is attached to t p q l,1.And finally, connecting the trees T (d) (p q l,k ) at root node p q l,k to t p q l,k.By (8) and induction, there exist isomorphisms(ρ i , τ i ) from (F (d) (w i ), T (d) (w i )) to (F (d) (z i ), T (d) (z i ))such that ρ i (w i ) = z i for i = 1, . . . , n. By (9) and induction, there exist isomorphisms (ρ q l,k , τ q l,k ) from (F (d) (u q l,k ), T (d) (u q l,k )) to (F (d) (y q l,k ), T (d) (y q l,k )) such ρ i (u q l,k ) = y q l,k for q = 1, . . . , r, k = 1, . . . , q + 1 and l = 1, . . . , |N q (v)|.We now construct ρ by merging all ρ i and ρ q l,k , and construct τ by merging all τ i and τ q l,k . We finally specify an appropriate mapping for the tree root, its direct children and the paths attached to the tree root. Then, it is easy to see that (ρ, τ ) is well-defined and an isomorphism betweenF (d+1) (v), T (d+1) (v) and F (d+1) (x), T (d+1) (x) such that ρ(v) = x.Proof of "⇐=". We now prove the other direction, again via induction over D. When D = 0 the assertion obviously holds. Assume that the assertion holds for D ≤ d. Now, assume that there exists an isomorphism (ρ, τ ) betweenF (d+1) (v), T (d+1) (v) and F (d+1) (x), T (d+1) (x) such that ρ(v) = x. We show that c (d+1) r (v) = c (d+1) r (x).We begin our proof by establishing the equality of two multisets: (c(d) r (w), atp(v, w))|w ∈ V (G) and (c (d) r (z), atp(v, z))|z ∈ V (H) .The proof of this equivalence closely mirrors the argument presented in the proof of B. Zhang et al. (2024, Lemma C.14) . Since τ is an isomorphism it maps all tree nodes T (d+1) (v) of depth 2 with 1 element in their bag to the corresponding tree nodes in T (d+1) (x). Let s 1 , . . . , s n and t 1 , . . . , t n be the nodes in T (d+1) (v) and T (d+1) (x) of depth 2 with 1 element in their bag, respectively. For i = 1, . . . , n, let s i and t i the parents of s i and t i , respectively. We then choose the order such that the following holds for all i = 1, . . . , n1. Let β T (d+1) (v) (s i ) = {v, wi } and β T (d+1) (x) (t i ) = {x, zi }. Then, ρ(v) = x and ρ( wi ) = ziand thus, per assumption, {v, wi } ∈ E(F (d+1) (v)) if and only if {x, zi } ∈ E(F (d+1) (x)).2. τ is an isomorphism from the subtree rooted at s i in T (d+1) (v), i.e., T (d+1) (v)[s i ], the subtree rooted at t i in T (d+1) (x), i.e., T (d+1) (v)[t i ].3. For all s ∈ Desc T(d+1) (v) (s i ), it holds ρ(β T (d+1) (v) (s)) = β T (d+1) (x) (τ (s)).4. By the definition of the unfolding tree, ρ is an isomorphism from the induced subgraphF (d+1) (v) T (d+1) (v)[s i ] and the induced subgraph F (d+1) (x) T (d+1) (x)[t i ] .By the last three items, we get thatF (d+1) (v) T (d+1) (v)[s i ] , T (d+1) (v)[s i ] and F (d+1) (x) T (d+1) (x)[t i ] , T (d+1) (x)[t i ] are isomorphic. By definition of the r-WL unfold- ing tree, F (d+1) (v) T (d+1) (v)[s i ] , T (d+1) (v)[s i ] is isomorphic to (F (d) (w i ), T (d) (w i )) for some w i ∈ V (G) that satisfies { wi , v} ∈ E F (d+1) (v) if and only if {w i , v} ∈ E(G). And F (d+1) (x) T (d+1) (x)[t i ] , T (d+1) (x)[t i ] is isomorphic to (F (d) (z i ), F (d) (z i )) for some z i ∈ V (H) that satisfies {z i , x} ∈ E(F (d+1) (x)) if and only if {z i , x} ∈ E(G).Hence, by induction, we have atp (v, w i ) = atp (x, z i ) and c(d) r (w i ) = c (d)r (z i ) for all i = 1, . . . , n. It remains to show that, for every q = 1, . . . , r, atp(v, u 1 ), c (d) r (u 1 ) , . . . , atp(v, u q+1 ),c (d) r (u q+1 ) | {u 1 , . . . , u q+1 } = u ∈ N q (v) = atp(x, y 1 ), c (d)r (y 1 ) , . . . , atp(x, y q+1 ), c (d) r (y q+1 ) | {y 1 , . . . , y q+1 } = y ∈ N q (x) .Fix q = 1, . . . , r. Since τ is an isomorphism it maps all paths of length q in T (d+1) (v) connected to v to paths of length q in T (d+1) (x) connected to x.By construction of the r-WL unfolding tree and since (ρ, τ ) is an isomorphism, it holds |N q (v)| = |N q (x)|. Denote the relevant bags at depth 2 by s q l,k for l = 1, . . . , |N q (v)| and k = 1, . . . , q + 1. Denote by s q l,k and t q l,k the parents of s q l,k and t q l,k , respectively. We then choose the order l = 1, . . . , |N q (v)| and k = 1, . . . , q + 1 such that it holds 1. Let β T (d+1) (s q l,k ) = v, wq l,k and β T (d+1) (t q l,k ) = x, zq l,k . Then, ρ( wq l,k ) = zq l,k and thus, per assumption, v, wq l,k ∈ E(F (d+1) (v)) if and only if x, zq l,k ∈ E(F (d+1) (x))2. τ is an isomorphism from the subtree rooted at s q l,k in T (d+1) (v), i.e., T (d+1) (v)[s q l,k ], to the subtree rooted at t q l,k in T (d+1) (x), i.e., T (d+1) (x)[t q l,k ].3. For all s ∈ Desc T (d+1) (v) (s q l,k ), it holds ρ(βT (d+1) (v) (s)) = β T (d+1) (x) (τ (s)).4. By the definition of the unfolding tree, ρ is an isomorphism from the induced subgraphF (d+1) (v) T (d+1) (v)[s q l,k ] and the induced subgraph F (d+1) (x) T (d+1) (x)[t q l,k ] .By the last three items, we get thatF (d+1) (v) T (d+1) (v)[s q l,k ] , T (d+1) (v)[s q l,k ] and F (d+1) (x) T (d+1) (x)[t q l,k ] , T (d+1) (x)[t q l,k ] are isomorphic. By definition of the r-WL unfold- ing tree, F (d+1) (v) T (d+1) (v)[s q l,k ] , T (d+1) (v)[s q l,k ] is isomorphic to (F (d) (w q l,k ), T (d) (w q l,k )) for w q l,k ∈ V (G) that satisfies wq l,k , v ∈ E F (d+1) (v) if and only if w q l,k , v ∈ E(G).AndF (d+1) (x) T (d+1) (x)[t q l,k ] , T (d+1) (x)[t q l,k ] is isomorphic to (F (d) (z q l,k ), T (d) (z q l,k )) for z q l,k ∈ V (G) that satisfies zq l,k , v ∈ E(F (d+1) (v)) if and only if z q l,k , v ∈ E(G).Hence, by induction, we have c(d) r (w q l,k ) = c (d)r (z q l,k ) for all indices. By Item 1, we then have c(d) r (w q l ) = c (d)r (z q l ) and atp(v, w q l ) = atp(v, z q l ) for every q = 1, . . . , r and l = 1, . . . , |N q (v)|.We introduce the following definition that provides a similarity measure between a graph and a tree-decomposed graph. Definition 27. Given a graph G and a tree-decomposed graph (F, T s ), definecnt ((F, T s ), G) = v ∈ V | ∃D ∈ N s.t. (F (D) (v), T (D) (v)) ∼ = (F, T s ) ,where (F (D) (v), T (D) (v)) is the depth-2D r-WL unfolding tree of G at v.The counting function cnt ((F, T s ), G) serves as a key metric, allowing us to draw connections between r-WL colorings of two different graphs. Corollary 3. Let r ∈ N. Let G and H be two graphs. Then, c r (G) = c r (H) if and only if cnt ((F, T s ), G) = cnt ((F, T s ), H) holds for all graphs (F, T s ) ∈ M r+2 .Proof of "=⇒". Let c r (G) = c r (H), i.e.,{{c r (v) | v ∈ V (G)}} = {{c r (x) | x ∈ V (H)}} .Assume, by contradiction, that there exists a tuple (F, T s ) ∈ M r+2 such that cnt ((F, T s ), G) = cnt ((F, T s ), H). Let c 1 , . . . , c k be the final colors of nodes in V (G) and V (H). Then, define for i = 1, . . . , kcnt ((F, T s ), G[c i ]) := v ∈ V (G) | c r (v) = c i and ∃D ∈ N s.t. (F (D) (v), T (D) (v)) ∼ = (F, T s ) .We haveEQUATIONcnt ((F, T s ), H) = k i=1 cnt ((F, T s ), H[c i ]) .Since cnt ((F, T s ), G) = cnt ((F, T s ), H), there exist an index i = 1, . . . , k such thatEQUATIONFurthermore, there exists i n ∈ N such that there are exactly n nodes v 1 , . . . , v n and x 1 , . . . , x n such that c r (v 1 ) = . . . = c r (v in ) = c i and c r (x 1 ) = . . . = c r (x in ) = c i .Hence, as c r refines c(D)r , we have c (D) r (v 1 ) = . . . = c (D) r (v in ) = c (D) r (x 1 ) = . . . = c (D) r (x in ). By (10), there exists some D ∈ N such that (without loss of generality) (F (D) (v 1 ), T (D) (v 1 )) ∼ = (F, T s ). Then, by Theorem 5, we have(F (D) (v 1 ), T (D) (v 1 )) ∼ = . . . ∼ = (F (D) (v in ), T (D) (v in )) ∼ = (F (D) (x in ), T (D) (x in )) ∼ = . . . ∼ = (F (D) (x 1 ), T (D) (x 1 )).There does not exist any other node w with c r (w) = c 1 such that the corresponding unfolding tree is isomorphic to (F (D) (v 1 ),T (D) (v 1 )). Hence, cnt((F, T s ), G[c i ]) = cnt((F, T s ), H[c i ]), which is a contradiction.Proof of "⇐=". Suppose that cnt((F, T s ), G) = cnt((F, T s ), H) for all (F, T s ) ∈ M r+2 . Let c 1 , . . . , c k G with multiplicities m 1 , . . . , m k G and c1 , . . . , ck H with multiplicities m1 , . . . , mk G be the final colors of r-WL applied to G and H, respectively. Consider some v ∈ V (G) such that c r (v) = c 1 . Let D be sufficiently large (any D after convergence of r-WL), then cnt((F (D) (v), T (D) (v)), G) = cnt((F (D) (v), T (D) (v)), H) since (F (D) (v), T (D) (v)) ∈ M r+2 .Hence, without loss of generality, c 1 = c1 and m 1 = m1 . Repeating this argument for all colors finishes the proof.In this section, we employ techniques adapted from the works of Dell et al. (2018) and B. Zhang et al. (2024) to derive a proof for Theorem 2 from the established result in Corollary 3. Definition 28 (Definition 20 in (Dell et al., 2018) ). Let (F, T t ) and ( F, T s ) be two tree-decomposed graphs. A pair of mappings (ρ, τ ) is said to be a bag isomorphism homomorphism from (F, T t ) to ( F, T s ) if it satisfies the following conditions 1. ρ is a homomorphism from F to F .2. τ is a homomorphism from T t to T s .3. τ is depth-surjective, i.e., the image of T t under τ contains vertices at every depth present in T s .4. For all t ∈ T t , we havedep T t (t ) = dep T s (τ (t )) and F [β T t (t )] ∼ = F [β T s (τ (t ))].5. For all t ∈ T t , the set equality ρ(β T t (t )) = β T s (τ (t )) holds.6. The depth of T t and T s is equal.We denote the set of bag isomorphism homomorphisms from (F, T t ) to ( F, T s ) by BIsoHom (F, T t ), ( F, T s ) and set bIsoHom (F, T t ), ( F, T s ) = |BIsoHom (F, T t ), ( F, T s ) |.We continue with the following lemma that shows a linear relation between the number of bag isomorphisms and the output of the counting function in Definition 27. Lemma 6. Let r ∈ N. For any tree-decomposed graph (F, T s ) ∈ M r+2 and any graph G, it holds bIsoEQUATIONProof. Let (F, T s ) be a tree-decomposed graph such that T s has depth 2D. The sum is over all isomorphism types ( F, T t ) of tree-decomposed graphs. This sum is finite and thus well-defined as bIsoHom (F, T s ), F, T t = 0 holds if T t has depth unequal to 2D or nodes with at least(r + 1) • (|V (G)| -1) children.Assume that for the root bag of (F, T s ) it holds β T s (s) = {v}. Let x ∈ V (G) be any vertex in G, and denote by (F (D) (x), T (D) (x)) the depth-2D r-WL-unfolding tree at node x. Define the following two sets,S 1 (x) = {h ∈ BIso((F, T s ), G) | h(v) = x} , S 2 (x) = (ρ, τ ) ∈ BIsoHom (F, T s ) , F (D) (x), T (D) (x) | ρ(v) = x .We prove that |S 1 (x)| = |S 2 (x)| for every x ∈ V (G), which is equivalent to (11). For this, we show for any bag isomorphism h from (F, T s ) to G with h(v) = x, there exists a unique bag isomorphism homomorphism σ from (F, T s ) to (F (D) (x), T (D) (x)) with σ(v) = x such that h = π • σ, where π is the bag isomorphism from (F (D) (x), T (D) (x)) to G, defined in Definition 26 and Theorem 4, respectively. To visualize this proof idea, see Figure 12 .First, define ρ(v) := x. Let v 1 , . . . , v n ∈ V (F ) be nodes that correspond to bags in T s of depth 2 with one element inside the bag and their parents having two elements in their bag, i.e., {v i } are the corresponding bags. Similarly, set x 1 , . . . , x m ∈ V (F (D) (x)) nodes that correspond to bags of depth 2 in T (D) (x), with one element inside the bag and their parents having two elements in their bag. Since h is a bag isomorphism and π as well, for every i = 1, . . . , n there exists a j i such that h(v i ) = xji = π(x ji ), where xji ∈ V (G) and x ji ∈ V F (D) (x) . Since π and h are bag isomorphisms, we haveEQUATIONNow, set ρ(v i ) = x ji for every i = 1, . . . , n. Based on (12), we can easily define τ such that τ satisfies Definition 28 with respect to bags that are of depth 1 and 2.For q = 1, . . . , r and l = 1, . . . , |N q (v)|, let p q l be a path of length 2q starting from the root node s in T s . Every such path p q l in T s corresponds to unique path v q l , that is in N q (x), of length q in F . We represent the path by v q l,1 , v q l,2 , . . . , v q l,q+1 , where every consecutive node is connected to each other and for k = 1, . . . q + 1, we have v, v q l,k ∈ E(F ) iff h(v), h(v q l,k ) ∈ E(G) as h is a bag isomorphism. Further for every node k = 1, . . . , q + 1 there exists a j q l,k such that h(v q l,k ) = xj q l,k = π(x j q l,k ), where xj q l,k ∈ V (G), xj q l,1 , . . . , xj q l,q+1∈ N q (x) and x j q l,1 , . . . , x j q l,q+1∈ N q (x). We set σ(v q l,k ) = x j q l,k for every k = 1, . . . , q + 1. Clearly, we haveF [{{v, v i , v i+1 }}] ∼ = G x, xji , xji+1 ∼ = F (D) (x)x, x ji , x ji+1 .(13) Now, based on (13), we can easily define τ such that τ satisfies Definition 28 with respect to bags that correspond to paths in N q (v) for q = 1, . . . , r. Now, following this construction recursively leads to a bag isomorphism ρ such that h = π • ρ.It remains to show that (ρ, τ ) is unique (up to isomorphism). For this, let (ρ 1 , τ 1 ) be another bag isomorphism homomorphism between (F, T s ) and (F (D) (x), T (D) (x)) such that ρ 1 (v) = x and h = π • ρ 1 . We show that ρ = ρ 1 .We begin by showing that ρ(v) = ρ 1 (v) for every v that is not in a cycle. Adopting the previous notations, consider v 1 , . . . , v n ∈ V (F ) and x 1 , . . . , x m ∈ V (F (D) (x)). For each i = 1, . . . , n, let k i and l i be the indices such that ρ(v i ) = x ki and ρ 1 (v i ) = x li . Consequently, π(x ki ) = π(x li ). We note that the image of h(v i ) is not contained in a cycle in G, as otherwise, h would not be a bag isomorphism. Similarly, x ki and x li are not contained in a cycle; otherwise, ρ and ρ 1 would not be bag isomorphisms. Now, π is an injective mapping if the domain is restricted to nodes that are of depth 1 and 2, and not contained in a cycle. Hence, x ki = x li .We continue by showing that for every w ∈ V (F ), that is contained in a cycle, we have ρ(w) = ρ 1 (w). This follows a similar argument as the nodes that are not included in any cycle. We summarize the argument shortly: It must hold that ρ(w) and ρ 1 (w) are contained in a cycle, and π(ρ(w)) and π(ρ 1 (w)) as well. Now, π is injective if the domain is restricted to nodes that are only contained in cycles. Hence, ρ 1 = ρ.We continue this subsection by introducing the concept of a bag extension in the context of treedecomposed graphs. This definition formalizes the notion of one tree-decomposed graph being an extension of another. Definition 29 (Definition 20 in (Dell et al., 2018) ). Let (F, T t ) be a tree-decomposed graph. A bag extension of (F,T t ) is a graph (H, T t ) with V (H) = V (F ) such that for every t ∈ V (T t ) the induced subgraph H[β T t (t)] is an extension of F [β T t (T )], i.e., if e ∈ E (F [β T t (T )]), then e ∈ E (H[β T t (T )]). We define bExt (F, T t ), ( F, T s ) as the number of bag extensions of (F, T t ) that are isomorphic to ( F, T s ).Intuitively, a bag extension of a tree-decomposed graph (F, T s ) can be achieved by adding an arbitrary number of edges to F . Each added edge must be contained within a bag that corresponds to a node in the tree T s . Definition 30 (Definition C.28 in (B. Zhang et al., 2024) ). Given a tree-decomposed graph (F, T r ) and a graph G, a bag-strong homomorphism from(F, T s ) to G is a homomorphism f from F to G such that, for all t ∈ V (T r ), f is a strong homomorphism from F [β T s (t)] to G[f (β T s (t))], i.e., {u, v} ∈ E (F [β T s (t)]) iff {f (u), f (v)} ∈ E (G[f (β T s (t))]). Denote BStrHom((F, T s ), G) to be the set of all bag-strong homomorphisms from (F, T s ) to G, and denote bStrHom((F, T s ), G) = |BStrHom((F, T s ), G)|.We continue with decomposing the number of homomorphism from a fan cactus graph to any graph. Lemma 7. Let r ∈ N. For any tree-decomposed graph (F, T s ) ∈ M r+2 and any graph G, it holds Proof. The proof follows the lines of Lemma C.29. in (B. Zhang et al., 2024) . First, ( 14) is well-defined as T s is finite, hence, there can only be finitely many bag extensions of (F, T s ).EQUATIONFurther, consider the setS = F, T t , (ρ, τ ) , g | F, T t ∈ M r+2 , (ρ, τ ) ∈ BExt (F, T s ) , F, T t , g ∈ BstrHom F, T t , G .We consider the mapping σ from S to hom(F, G) via ((ρ, τ ) , g) → g • ρ. We show that for every homomorphism h there exists a unique, up to automorphisms, F, T t ∈ M r+2 , (ρ, τ ) and g such that h = g • ρ.We begin with the existence part. For h ∈ hom(F, G), we define F, T t ∈ M r+2 , (ρ, τ ) and g as follows.• We define F by adding the edges given byEQUATIONWe define T t := T s . Clearly, F, T t ∈ M r+2 and it is a bag extension as only edges are added that are contained within a bag that corresponds to a node in T s .• We define ρ and τ as the identity mappings on their respective domain, leading to (ρ, τ ) ∈ BExt (F, T s ) , F, T t .• We define g = h. For x ∈ T t , we show that g is a strong homomorphism fromF [β T t (x)] to G[g (β T t (x))]. Let {u, v} ∈ E F [β T t (x)] , then {g(u), g(v)} ∈ E (G[g (β T t (x))]) as his a homomorphism with respect to the edges E(F ) and in (15) only edge {u, v} were added that satisfy {h(u), h(v)} ∈ E(G). On the other hand {g(u), g(v)} ∈ E (G[g (β T t (x))]),but {u, v} ∈ E F [β T t (x)] would contradict (15) as u, v are contained in the same bag β T t (x). Hence, g ∈ BstrHom F, T t , G .We finally prove the uniqueness part, i.e., that σ ( F1 , T t1 1 ), (ρ 1 , τ 1 ), g 1 = h implies that there exists an isomorphism (ρ, τ ) from F1 , T t1 1 to F, T t such that ρ • ρ 1 = ρ, τ • τ 1 = τ . We first prove that F1 ∼ = F and T t1 1 ∼ = T t .1. For any u, v ∈ V (F ), we obviously have ρ(u) = ρ(v) iff u = v iff ρ 1 (u) = ρ 1 (v) as ρ and ρ 1 are injective mappings.2. Let u, v ∈ V (F ). Consider {ρ 1 (u), ρ 1 (v)} ∈ E( F1 ), we show that {ρ(u), ρ(v)} ∈ E( F ).If {u, v} ∈ E(F ), then clearly {ρ(u), ρ(v)} ∈ E( F ) as ρ is a homomorphism. Hence, assume that {u, v} ∈ E(F ). Then, u, v must be contained in the same bag of T s as ρ 1 is a bag extension and only node pairs are added if they are in the same bag. Hence, ρ(u) and ρ(v) are contained in the same bag. As g 1 is a homomorphism, we have {g 1 (ρ 1 (u)), g 1 (ρ 1 (v))} ∈ E(G). But, then also {g(ρ(u)), g(ρ(v))} ∈ E(G), and as g is a strong homomorphism (with respect to the bag in which ρ(u) and ρ(v) are contained), we have {ρ(u), ρ(v)} ∈ E( F ).By symmetry of the argument, we have {ρ 1 (u), ρ 1 (v)} ∈ E( F1 ) iff {ρ(u), ρ(v)} ∈ E( F ).3. Since ρ 1 and ρ are bag extension, they are bijective on their respective domain. Hence, ρ = ρ • ρ -1 1 defines an isomorphism from F1 to F . On the other hand, T t1 1 ∼ = T t trivially holds, again with τ = τ • τ -1 1 .We have ρ • ρ 1 = ρ, τ • τ 1 = τ . We show that the tuple (ρ, τ ) is an isomorphism, i.e., it remains to show that for any b ∈ T t1 1 , we have ρ(β The first and third equalities hold since (ρ 1 , τ 1 ) and (ρ, τ ) are bag extensions.Definition 31 (Definition 30 in (B. Zhang et al., 2024) ). Given two tree-decomposed graphs (F, T s ) and ( F, T t ), a homomorphism (ρ, τ ) from (F, T s ) to ( F, T t ) is called bag-strong surjective if ρ is a bag-strong homomorphism from (F, T s ) to F and is surjective on both vertices and edges, and τ is an isomorphism from T s to T t such that for all x ∈ V (T s ), we have ρ(β T s (x)) = β T t (τ (x)). Denote BStrSurj((F, T s ), ( F, T t )) to be the set of all bag-strong subjective homomorphisms from (F, T s ) to ( F, T t ), and denote bStrSurj((F, T s ), ( F, T t )) = |BStrSurj((F, T s ), ( F, T t ))|. Lemma 8. Let r ∈ N. For any tree-decomposed graph (F, T s ) ∈ M r+2 and any graph G, it holds bStrHom ((F, T s ) , G) = ( F, T t )∈M r+2 bStrSurj (F, T s ) , F, T t bIso F, T t , G aut F, T t , (16) where aut( F, T t ) counts the number of automorphisms of ( F, T t ).Theorem 7 (B. Zhang et al., 2024) . The homomorphism-expressivity of Subgraph k-GNN is given by F sub(k) = {F : ∃U ⊂ V F s.t. |U | ≤ k and F \ U is a forest }.Since the set F sub(k) is the maximal set of graphs that Subgraph k-GNNs can homomorphism-count, we can derive the following corollary, which restates Corollary 2 iii) and provides a proof. Corollary 6. For any k ≥ 1, 1-WL is not less powerful than Subgraph k-GNNs. In particular, any r-WL can separate infinitely many graphs that Subgraph k-GNNs fail to distinguish.Proof. The proof parallels the proof of Corollary 2. We present it here for completeness.Let k ≥ 1. We will show that there exists a pair of graphs that 1-GIN can distinguish, but Subgraph k-GNNs cannot. Consider the graph F , defined as the unique graph with k triangle graphs, all connected by an edge to a single node.It holds that F ∈ M 3 \ F sub (k) , where F sub(k) is the maximal set that Subgraph k-GNNs can homomorphism-count. Then, by (B. Zhang et al., 2024, Theorem 3.8) , there exists a pair of graphs G(F ) and H(F ) such that hom(F, G(F )) = hom(F, H(F )) and hom (F sub(k) , G(F )) = hom (F sub(k) , H(F )). Hence, Subgraph k-GNNs cannot separate G(F ) and H(F ). Since F ∈ M 3 , by hom(F, G(F )) = hom(F, H(F )) and Theorem 2, 1-WL can separate G(F ) and H(F ).This argument can be repeated for every F ∈ M 3 \ F sub (k) . Since there are infinitely many non-isomorphic graphs in M 3 \ F sub(k) , the corollary follows.Proof of Corollary 2 iv). Given graphs F and G, it is well-known (see, e.g., (Neuen, 2024; Curticapean et al., 2017) ) that sub(F, G) can be decomposed as:EQUATIONHere, the sum ranges over all non-isomorphic graphs in spasm(F ). The sum in (20) is finite since the homomorphic image of F has at most |V (F )| nodes. Per assumption, we have spasm(F ) ⊂ M r+2 , i.e., by Theorem 2, r-WL can homomorphism-count spasm(F ). In particular, if r-WL cannot separate two graphs G and H, we have hom(spasm(F ), G) = hom(spasm(F ), H), and hence, sub(F, G) = sub(F, H).The result on subgraph-counting paths follows directly as the homomorphic image of a path P r+3 of length r + 3 lies in M r .Theorem 3. For fixed t, r ≥ 0, t iterations of r-WL are more powerful than r-MPNN with t layers. Conversely, r-MPNN is more powerful than r-WL if the functions f (t) , g (t) in (3) are injective.Proof of Theorem 3. We begin by proving that c(t) r h (t)r . We argue by induction over t for any fixed r ≥ 0. countable and hence a proper subset of R. It follows that there exists ε r+1 ∈ R with ε r+1 / ∈ Q[ε]. Note that 0 ∈ Q and hence ε r+1 = 0. We now prove our claim by contradiction.Assume there exist x = x ∈ Q r+1 with r+1 k=0 ε k x k = r+1 k=0 ε k x k . We distinguish two cases: x i = x i for all i ≤ r and x r+1 = x r+1 : Then immediatelyx r+1 = x r+1 ⇒ ε r+1 x r+1 = ε r+1 x r+1 ⇒ r k=0 ε k x k + ε r+1 x r+1 = r k=0 ε k x k + ε r+1 x r+1 ⇒ r+1 k=0 ε k x k = r+1 k=0 ε k x k . r k=0 ε k x k = r k=0 ε k x k : But then r k=0 ε k x k + ε r+1 x r+1 = r k=0 ε k x k + ε r+1 x r+1 ⇔ r k=0 ε k x k - r k=0 ε k x k = ε r+1 (x r+1 -x r+1 )The left hand side is an element of Q[ε 1 , . . . , ε r ]. However, ε r+1 (x r+1 -x r+1 ) / ∈ Q[ε 1 , . . . , ε r ] by choice of ε r+1 , leading to a contradiction. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: Our paper does not involve crowdsourcing or research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.lr < 10 -5 lr < 10 -5 lr < 10 -5 


Decision: This paper suggests a new hierarchy of graph isomorphism tests, alternative to the standard kWL heirarchy. This is done by appending information on paths between neighborhing nodes the the standard MPNN procedure. The paper shows strong theoretical results, and in practice good separation abilities and competitive performance on standard benchmarks. The reviewers all recommended acceptance.

Reviews: review: paper_summary: paper_summary: This introduce $r$-loopy Weisfeiler-Leman, a new hierarchy of graph isomorphism test and a corresponding GNN framework. It achieves good cycle counting power and surpuss $k$-WL in some cases. The power of r-lWL is examined in various synthetic and real-world datasets.
strength_weakness: strength_weakness: 1. More datasets [1, 2] can be included to evaluate expressivity, especially long range expressivity. 


[1] Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, Dominique Beaini: Long Range Graph Benchmark. NeurIPS 2022.
[2] Yanbo Wang, Muhan Zhang. Towards Better Evaluation of GNN Expressiveness with BREC Dataset. arxiv/abs/2304.07702
questions: questions: 1. For any pair of non-isomorphic graph, can $r$-lwl differentiate them with large enough $r$? (similar that $k$-WL can solve graph isomorphism problem for graph of node less than $k$).
limitations: limitations: Yes
paper_summary: paper_summary: In this paper, the authors propose a loopy version of the Weisfeiler-Lehman (WL) algorithm. This version utilizes an extended notion of neighborhood, incorporating paths between standard neighboring vertices to update vertex coloring. By parameterizing the length $r$ of these paths, we obtain $r$-$l$WL. The results include a hierarchy for $r$-$l$WL based on $r$ and a comparison with $k$-WL. The most technical result is that $r$-$l$WL is expressive enough to determine homomorphism counts of $(r+2)$-cactus graphs. Experiments show that $r$-$l$WL is competitive in detecting substructures.
strength_weakness: strength_weakness: **W1 Capturing Cacti:** 
The motivation for focusing on cactus graphs is unclear. The authors should better justify why this class of graphs is interesting and relevant, and provide examples in the main paper.

**W2 Insufficient Comparison with Subgraph GNNs:** 
The paper mentions that subgraph GNNs are bounded by $3$-WL, but there are subgraph GNNs beyond $3$-WL, such as $k$-OSAN s (ordered subgraph aggregation networks, Qian et al.), which can capture features that $k$-WL cannot and are bounded by $(k+1)$-WL. The paper overlooks this line of work and lacks comparison with $k$-OSANs, both empirically and theoretically. For example, specifying paths of length $r$ and a central node requires special subgraphs of size $r+1$ (the path plus central node), suggesting that $r$-$l$WL may be included in $(r+1)$-OSAN? This could imply that some results stem from $k$-OSAN properties. A more detailed comparison is needed.

**W3 Experimental Comparison:**
The experiments do not seem to include any subgraph GNNs that capture properties beyond 3-WL. The authors should make more clear what are the capabilities of the methods with which they compare.

**W4 Unlabeled Graphs:**
The paper does not address vertex labels. Can the approach be generalized to vertex labels? Additionally, $c^{(0)}$ in section 3.2 is undefined.

Minor Comments: The authors sometimes use obscure references. For instance:
- line 71: Do you mean Tinhofer or Dvorak?
- line 96: Why refer to Dimitrov 2023 for the notion of graph invariant, which has existed for ages?
questions: questions: Please comment on **W1**, **W2** and **W3**.
limitations: limitations: This has been addressed in a satisfactory way by the authors.
paper_summary: paper_summary: The paper proposed a hierarchy of graph isomorphism tests and a corresponding GNN framework, $r$-$\ell$-MPNN while showing the ability to count homomorphisms of cactus graphs.
strength_weakness: strength_weakness: The weaknesses of the paper is that while the paper is well written, there are some terms undefined, or unexplained such as HASH; see the first question in the following section.
questions: questions: 1) What is the HASH function? do you have an example of such a function?
2) Can you add tables concerning the times of your method compared to other methods?
3)  What is the motivation behind using $r=5$ in the experiments? would any $r>5$ result in worse results or simply better results by small significance on the expense of might higher time?
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_summary: The paper introduces the $r$-loopy Weisfeiler-Leman ($r$-$l$WL) test, an innovative hierarchy of graph isomorphism tests, and the corresponding GNN framework, $r$-$l$MPNN. This new approach extends the counting capabilities of previous algorithms, specifically allowing the counting of cycles up to length $r+2$ and homomorphisms of cactus graphs. Empirical validation demonstrates the expressiveness and performance of $r$-$l$MPNN on both synthetic and real-world datasets.
strength_weakness: strength_weakness: Some of the mathematical proofs are complex and may be difficult for readers without a strong background in graph theory and GNNs. Providing additional intuitive explanations or examples could improve accessibility. While the empirical validation is strong, it could be expanded to include a broader range of real-world datasets to further demonstrate the robustness and generalizability of the approach.
questions: questions: The paper is generally well-written and clear, although some sections could benefit from additional explanations or examples to aid understanding. I have a few questions:

1. How does the computational complexity of $r$-$l$WL compared to existing higher-order WL variants like $3$-WL in practice, especially when dealing with large and dense graphs?

2. What are the limitations of $r$-$l$WL in terms of scalability and memory usage, particularly when applied to real-world datasets with varying degrees of sparsity?

3. In Table 1, why didn't your method perform well on the Extension (100) and CFI (100) datasets compared to 3-WL and PPGN?
limitations: limitations: The authors have addressed the limitations related to the complexity of higher-order GNNs and the scalability issues associated with $k$-WL. However, a more detailed discussion on the limitations of $r$-$l$WL in terms of computational overhead and potential impact on large-scale applications would be beneficial.

Comments: title: Satisfied with the answers
Good rebuttal
Good rebuttal
comment: Thank you to the authors for addressing my comments and for their thoughtful responses to the other reviewers' feedback. I continue to believe this is a good paper and will maintain my score.
The authors satisfactorily addressed my questions. However, I have kept my score, increasing my confidence to 4 in light of the authors' answers.
I have read the rebuttal and I am pleased with the responses. I would indeed appreciate if the case for cactus graphs is made stronger in the paper, as is explained here in the rebuttal. Moreover, the connection with subgraph GNNs, whether OSANs or other, should be explored or at least discussed briefly in related work. Based on the rebuttal and I am happy to accept the paper and to raise my score. The paper I referred to is "On recognizing graphs by numbers of homomorphisms by Zdeněk Dvořák.