Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
Authors: Raffaele Paolino
Sohir Maskey
Pascal Welke
Gitta Kutyniok
Venue: NeurIPS 2024 oral (2024)
Keywords: Graph Neural Networks
Weisfeiler-Leman (WL) Test
Homomorphism Counting
Theory and Expressivity in GNNs
Cactus Graphs
Primary area: graph_neural_networks
TL;DR: We introduce GNNs that can count cycles and homomorphisms of cactus graphs, surpassing the limitations of existing GNNs while being scalable on real-world graphs.

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.

Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
Raffaele Paolino":la .22 11,2 Sohir Maskey* Pascal Welke
Gitta Kutyniok 12,4,5
Deparrment of Mathematics, LMU Munich
Munich Center for Machine Learning (MCML)
Faculty of Computer Science, TU Wien
Institute for Robotics and Mechatronics, DLR-German Aerospace Center
Department of Physics and Technology, University of Tromsø
Abstract
We introduce r-loopy Weisfeiler-Leman (r-(WL), novel hierarchy of graph isomorphism tests and a corresponding GNN framework, r-ÊMPNN, that can count cycles up to length r+2. Most notably, we show that r-LWL can count homomorphisms of cactus graphs. This extends 1-WL., which can only count homomorphisms of trees and, in fact, we prove that r-LWL. is incomparable to k-WL for any fixed k. We empirically validate the expressive and counting power of r-MMPNN on several synthetic datasets and demonstrate the scalability and strong performance on various real-world datasets, particularly on sparse graphs. Our code is available on GitHub.
1 Introduction
Graph Neural Networks (GNNs) (Scarselli al., 2009; Bronstein et al., 2017) have become 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 al., 2019; Morris et al., 2019). This limitation hinders MPNNs from recognizing basic substructures like cycles (Chen et al., 2020). However, specific substructures can crucial in many applications. For example, in organic chemistry, the presence of cycles can impact various chemical properties of the underlying molecules (Deshpande al., 2002; Koyutürk et al., 2004). Therefore, is crucial to investigate whether GNNs count certain substructures and to design architectures that surpass the limited power of MPNNs.
Several models have been proposed 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 substructures. For instance, GNNs emulating 3-WL. can count cycles up to length However, this increased expressivity comes at 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 design expressive GNNs that respect the inherent sparsity of real-world graphs (Morris et al., 2023).
*Equal contribution.
Corresponding authors: paolino @ math. Imu.de, maskey @ math.lmu.de
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Input graph
Preprocessing; extracting (v)
Training: paths-lo-grane embedding
Pooling direct neighbors
Path-wise GNN
Pooling path
embeddings
Graph Pooling
Graph Embedding
Path-wise GNN
Pooling path
embeddings
Figure 1: Visual depiction of r-EGIN: During preprocessing, we calculate the path neighborhoods (u) for each node u 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 (v), enabling efficient computation on sparse graphs.
Main Contributions. We introduce novel class of color refinement algorithms called r-loopy Weisfeiler-Leman test (r-EWL) and a corresponding class of GNNs named r-loopy Graph Isomorphism Networks (r-IGIN). The key idea 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-LWL can count cycles up to length r+2, even surpassing the 6-WL hierarchy.
Furthermore, prove that r-LWL can homomorphism-comm 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 electrical engineering (Nishi al., 1986) and computational biology (Paten et al., 2011). ). For instance, aromatic compounds often form cactus graphs, where the molecular core, usually cycle, is coonected functional groups (e.g., carboxyl groups) that can significantly impact the properties of the molecule. Thus, the ability to homomorphism-coum cactus graphs can enhance model performance, and allows to compare the expressive power of r-LWL with other popular GNNs in quantitative manner (Barceló et al., 2021: B. Zhang et al., 2024). Specifically, we show that r-EWL more expressive than GNNs that include explicit homomorphism counts of cycle graphs known as F-Hom-Gre GNNNs (Barceló et al., 2021). Additionally, 1-LWL can already separate infinitely many graphs that Subgraph k-GNNs (Frasca et al., 2022; Qian al., 2022) cannot (see, e.g., Figure 7). The higher expressivity, paired with the local computations, highlights the enhanced potential of r-EGIN, showing its competitive performance and the efficiency of its forward pass on real-world datasets, see Section 7.
2 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 measured by the ability to distinguish non-isomorphic graphs. According to the 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 (Moriis et al., 2023).
theorem,
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, 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 al., 2019b; Keriven al., 2019), their exponential time and space complexity in & 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-WI.. Subgraph GNNs (Bevilacqua al., 2021; You et al., 2021; Frasca et al., 2022; Huang al., 2022) surpass 1-WL by decomposing the initial input

---

graph into a bag of subgraphs. However, subgraph GNNs are upper-bounded by 3- 3-WL (Frasca et al., 2022). A different line of work leverages positional encoding through unique node identifiers (Vignac et al. 2020), random features (Abboud et al., 2021; Sato et al., 2021) eigenvectors (Lim et al., 2022; Maskey et al., 2022) to augment the expressive power of MPNNs.
While the predominant approach for gauging the expressive power of GNNs is within the k-WL hierarchy, such a measure inherently qualitative, as it cannot shed light on substructures a particular GNN can encode. Lovász (1967) showed that homomorphism counts is a complete graph invariant, meaning two graphs are isomorphic and only if their homomorphism counts are identical. Building on this result, B. Zhang et al. (2024) advocate for homomorphism-comm count as a quantitative measure of expressivity, as GNN architectures can homomorphism-com count particular families of motifs. Tinhofer (1986, 1991) established that 1-WL is equivalent to counting homomorphisms from graphs with tree-width one, while Dell al. (2018) proved the equivalence between k-WI. and the ability to count homomorphisms from graphs with tree-width k: Nguyen et al. (2020), Barceló et al. (2021), Welke al. (2023), and Jin et al. (2024) used homomorphism counts to develop expressive GNNs.
Manually augmenting node features with homomorphism counts can be disadvantageous as perfor- mance depends on the chosen substructures. This can be alleviated by designing domain-agnostic GNNs that can learn structural information suitable for the task at hand. For instance, higher-order GNNs can count a large class of substructures as homomorphisms (B. Zhang et al., 2024), but they suffer from scalability issues. We propose r-L'L and r-LGIN, which can count homomorphisms of cactus graphs without adding explicit substructure counts. Our method is scalable large datasets, particularly when the graphs in these datasets are sparse.
3
Preliminaries
Let G be the set of all simple and undirected graphs, and let G' E G. We denote the set of nodes by V(G) and the set of edges by EGG). The direct neighborhood N(v)= == {u E (G) {u, u) E B(G)).
node v E V(G) is defined as
Definition 1. Let F, G E G. A homomorphism from F to G is map h. V(F) + V(G) such that {u, v} E E(F) implies hh()) E E(G). A subgraph isomorphism is an injective homomor- phism.
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, also maps distinct edges to distinct edges. A visual explanation can be found in Figure 5. We denote by Hom G)) the set of homomorphisms from F to G and by hom(F, Gi) 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.
3.1 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 5: + P such that <(G) {(H) for all isomorphic pairs G, H G. Ç is a complete graph invariant ((G) + ((F) for all non-isomorphic pairs G, F E.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 Y be two graph invariants. We say that ry is more powerful than Ç (y 5 Ç) for every pair G, H E G, (G) = (H) implies ((G) = ((H). We say that ry is strictly more powerful than C i E and there exists a pair F.G G E G such that (G) # (H) and ((G) = ((H).
3.2 Message Passing Neural Networks and Weisfeiler-Leman
Message passing is iterative algorithm that updates the colors of each node E V(G) as
(t) + s(++1] (cd) (t+1) (t+)) (((c((()) (uEN(o)))))
(1)
3

---

The graph output after iterations is given by
(G) =
Here, g(), h are functions on the domain of multisets and f(t) is function on the domain of tuples. For each f, 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 e(G).
Choosing injective functions for all f() and setting g and as the identity function results in 1-WL (Weisfeiler et al., 1968). If f(t), o g(t), 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(), g()) 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. for a formal definition).
3.3 Homomorphism and Subgraph Counting Expressivity
A more nuanced graph invariant can be built by considering the occurrences of motif F. Definition 4. Let F E G. graph invariant ( can homomorphism-ccum
F ffr all pairs G, H E S(G) ((H) implies hom F, G) = hom F, H). By analogy, Ç can subgraph-count F if for all pairs G, E g, ((G) = ((H) implies sub(F, G) = sub(F, (F, H)-
If is family of graphs, we say that Ç can homomorphism-come every F E F; we denote the vector of homomorphism-coum by hom G) (hom F, F)) Interpreting hom(F, :) graph invariant, given by G + hom(F, G), another graph invariant can homomorphism-coumt
FF if ( can homomorphism-comm count
if and only if Ç = (J,
The ability of graph invariant to count homomorphisms is highly relevant because hom(C, -) is complete graph invariant. Conversely, if Ç is complete graph invariant, then C can homomorphism- count all graphs (Lovász, 1967). Additionally, homomorphism-counteee 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-L variant, as detailed in Corollary
serves as quantitative
4 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 E G. A simple path of length r is collection p (p:) r+1 ofr+ nodes such that {p. P E(G) and i i = P: * Pj for every i,j E [1......)].
Simple paths are the building blocks of r-neighborhoods, which in turn are the backbone of our r-LWL algorithm. The following definition is inspired by (Cantwell et al., 2019; Kirkley et al., 2021).
Definition 6. Let G E G and r E N \ [0}, we define the r-neighborhood (v) of E V(G) as Nr(v) = {pl simple path of length r, P1.Pr+1 E N(u), p).
For consistency, we set No(v) = Nvv). An ex- ample of the construction of r-neighborhood is shown in Figure 2, where different neighborhoods of node u are represented with different colors.
No(v)
-N)
....a())
Figure 2: Example of r-neighborhoods.
We generalize 1-WL in (1) as follows.
Definition 7. We define the r-loopy Weisfeiler- (r-&WL) test by the following color update:
& (1+1(()) < HASH, (() (0) (p) lelppe p (f....((( (pe
(2)
(p2)...., ...., (ert1)) is the sequence of colors of nodes in the puth. where (p) 10:00( (p)( (p2)

---

We denote by 6 (G) the final graph output after / iterations of r- i.e.
c (G) = HASH, ([(:%))levia))
and by (G) the stable coloring after convergence. The stable coloring e serves as graph invariant and will be referred to as r-LWI..
Expressivity of r-LWL
We analyze the expressivity of r-LWL in terms of its ability distinguish non-isomorphic graphs, subgraph-count, and homomorphism-come count motifs. The proofs for all statements are in Appendix D.
5.1 Isomorphism Expressivity
It is straightforward to check that O-LWL corresponds to 1-WL, since No(v) -N(v) for all nodes However, increasing r leads strict increase expressivity.
Proposition 1. Let S q < r. Then, r-LWL is strictly more powerful than q-EWL. In particular, every r-LWL 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
5.2 Subgraph Expressivity
Recent studies highlight limitations in the ability of certain graph invariants to subgraph-count cycles. For instance, 1-WL cannot subgraph-count cycles (Chen 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). contrast, r-LLL can count cycles of arbitrary length, as shown in the following statement.
Theorem 1. For any r 2 1, r-LWL can subgraph-come all cycles with at most + 2 nodes.
Since WL cannot subgraph-count any cycle with more than 7 nodes, Theorem implies that 6-LWL not less powerful than 3-WI.. This observation generalizes any k--WL, as shown
Corollary 1. Let l E N. There exists E N, such that r-EWL. is not less powerful than k-WL. Specifically, r E O(k2), with r 1(k++) 2 for even k and S (k+1)2 2 for odd k.
The r-LWL color refinement algorithm surpasses the limits the k- 6- hierarchy while only using local computation. This is particularly important since already 3- 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.
5.3 Homomorphism Expressivity
The following section unveils close connection between the expressivity of r-LWL and cactus graphs (Harary et al., 1953), significant class between trees and graphs with tree-width 2.
Definition 8. A cactus graph is graph where every edge lies at most one simple cycle. For r 2 2, an r-cactus graph a cactus where every simple cycle has at most T vertices. We denote by M the set of all cactus graphs, and by M the set of all q-cactus graphs for q Sr.
Figure 6 shows two examples of cactus graphs. From the expressivity perspective, the ability to homomorphism-com countt cactus graphs establishes lower bound strictly between the homomorphism- counting capabilities of 1-WL and 3- WL (Neuen, 2024), as cactus graphs are strict superset of all trees and strict subset of graphs of treewidth two. With this in mind, we are now ready to present our significant result on the homomorphism expressivity of our r-EWI. algorithm.
Theorem 2. Letr 2 0. Then, r-LWL can homomorphism-coumt M
5

---

We refer to Appendix G for a detailed proof of Theorem 2, which is fairly involved and requires defining canonical tree decompositions cactus graphs and unfolding trees of r-LWL. 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 more general result, showing that r-LWL. can count all fan-cactus graphs, see Appendix G for more details.
The class M² 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 implies that r-L is always strictly more powerful than 1-WL, corroborating the claim in Proposition 1.
The implications of Theorem 2 are profound: establishes that r-LWL can homomorphism-coum large class of graphs. Specifically. Theorem provides quantitative expressivity measure that enables comparison of r-LWI'ss expressivity with other WL variants and GNNs. This comparison is achieved by examining the range of graphs that r-
homomorphism-coum 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 (Bevilaequa et al., 2021; You et al., 2021; Frasca et al., 2022; Huang et al., 2022) are limited to homomorphisn-coum graphs with end-point shared NED. Hence, Subgraph GNNs can not homomorphism-coun I -== [+<4], 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 in the following corollary. Corollary 2. Let E N \ {0}. Then,
i) r-LWL is more powerful than F-Hom- where F = [Ca,..... ,,C2,..,,C+2hh
ii 1-EWL not less powerful than Subgraph GNNs. In particular, any r-EWL can separate infinitely many graphs that Subgraph GNNs fail to distinguish.
ii)) For any k > 0, 1-LWL is not less powerful than Subgraph k-GNNs. In particular, any r-LWL can separate infinitely many graphs that Subgraph k-GNNs fail to distinguish.
iv) r-LWL can subgraph-count all graphs F such that spasm(() C M where (F)sm(F) = (H e 9 surjective h E Hom(F, F, H)}. In particular, ff I 4. then r-LWL subgraph-coune all paths up to length 3.
A detailed explanation of Subgraph (k-)GNNs, J-Hom--HNIT 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-LWL. This observation opens the avenue for future research to explore tight lower bounds, or upper bounds, on the homomorphism expressivity of r-WLL.
Loopy Message Passing
In this section, we build GNN emulating r-LWL.
Definition 9. For fO...., 1} and le E {O....,. (-..)rr.EEMMM r-EMPNN applies the following message, update and readout functions:
(u) (++)(2)
(1+1)
(1 10 (p) (
(ff
m
(3)
(1) = (1+ (c) me a (o) ( (0)0m,..,....
(0) (OllEv))))) and final readout layer ( (G) (ff
In the following statement, we link the expressive power of r-MMPNN and r-EWI. Theorem For fixed frr 2 0, iterations of r-LWL are more powerful than r-MMPNN with t layers.
Conversely, r-MMPNN is more powerfual than r-LWL if the functions f(0, (())) in (3) are injective.
The previous result derives conditions under which r-MMPNN is expressive r-L To imple- ment r-MMPNN in practice, we choose suitable neural layers for p(t)) ("), and in Definition As consequence of (Xu et al.. 2019, Lemma 5), the aggregation function in (3) can be written
{(t 1(++1) (1fo (((((())
(p) Ipl (a(o))))) =
g(p) (v)
Σ

---

for suitable functions g.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 = MLP and g GIN. Hence, r-EGIN is defined as an r-MMPNN that updates node features via
2 (v) MLP
Jy (v) (1+ 60)
Σ wENo(v)
(1) E(+
CIN&(P) Σ DEN((()
To reduce the number of learnable parameters (4), the GIN, can be shared among all Nothing prevents from choosing different path-processing layer; we opted for GIN because it is simple yet maximally expressive on paths. We refer to Figure for a visual depiction of r-EGIN.
Computational Complexity The complexity of r-EGIN is O( EVEVIC) Σi=1 2b]N&( The former addend is the standard message complexity, while the latter arises from applying GIN to paths of length k S This implies that our model's is complexity scales linearly with the number of edges, and with the number of paths within (v). The number such paths typically less than the number of edges. For example, ZINC12K has overall 598K edges while only containing 374K paths in (v) for < 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 that of GAT, MoNet, GatedGCN (see Table 10 for 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 architecture expressiveness, consideration we address (see, e.g.. Proposition and Corollary 1). Another significant contribution our work, which we assert does not hold (at least not trivially) for PathNN, is the provable ability subgraph-count cycle graphs (see, e.g., Theorem 1) and homomorphism-coum cactus graphs (see, e.g., Theorem 2).
7 Experiments
All instructions to reproduce the experiments available GitHub (MIT license). Additional information on the training and test details can be found in Appendix C.
Expressive Power. We showcase the expressive power r-IGIN on synthetic datasets:
GRAPHSC (Balcilar al., 2021) comprises 11 117 connected non-isomorphic simple graphs on 8 nodes; 312 pairs are 1-WL equivalent but none is 3- 3-WL equivalent.
EXP _SO (Abboud al., 2022) comprises 600 pairs of 1-WL equivalent graphs.
GRAPHSC
EXP_ EXP_ISO
COSPECTRALIO
SR16622
3
3
3
H
4
2
2
+f
1
2
0
0
0
6.4 10
10-
10
10-1
010
1 10a
Proportion of indistinguishable pairs (t)
L distance (+))
Figure Indistinguishable pairs initialization, symlog scale. For GRAPHSC and EXP ISO. we report the proportion of indistinguished pairs: 2 graphs are deemed indistinguishable if the L distance of their embeddings less than 10-3, 3 For COSPECTRALIO and SR 3616622, we report the I distance between graph embeddings. We report the mean and standard deviation over 100 seeds.
7

---

Table 1: Num. of distinguished pairs (t). Results from (Wang al., 2024).
Model
Basic (60)
Regular (140)
Extension (100)
(100)
3-WL
60
50
100
60
PPGN
60
50
100
23
NestedGNN
59
48
59
0
GSN
60
99
0
OSAN
52
41
2
4-2GIN
60
100
95
2
EXP
EXP
CEXP
CEXP
aCC.
CSL
acc.
CSL
0
2
3
5
2
4 5
6
Figure 4: Test accuracy on synthetic classification task: (left) shared and (right) non-shared weights.
COSPECTRALIO (van Dam et al., 2003): the dataset comprises two cospectral 4-regular non-isomorphic graphs 10 nodes which 1-WL equivalent (see, e.g., Figure 8a).
SRI6622 (Michel al., 2023) comprises two strongly regular graphs 16 nodes, namely the Shrikhande and the 4x4 rook graph, which are 3-WL equivalent (see, e.g., Figure 8b).
The goal is to check whether the model can distinguish -on-isomorphic pairs at initialization. The results are shown in Figure 3.
Additionally, Table shows the performance 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 3-WL equivalent and can count up 7-cycles and homomorphism-coum 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 al., 2021) require expressive power beyond 1-WL.
CSL (Murphy 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) test the ability to homomorphism- and subgraphs-count exemplary motifs.
Table 2: Test MAE for homomorphism- and subgraph-counts. Results from (B. Zhang et al., 2024).
(F, G)
sub(F, G)
Model
MPNN
0.300
0.233
0.254
0.358
0.208
0.188
0.146
0.261
0.205
Subgraph GNN
0.011
0.015
0.012
0.010
0.020
0.024
0.046
0.007
0.027
Local 2-GNN
0.008
0.008
0.010
0.008
0.011
0.017
0.034
0.007
0.016
Local 2-FGNN
0.003
0.005
0.004
0.003
0.004
0.010
0.020
0.003
0.010
0.001
0.006
0.009
0.0005
0.0005 (r=2)
0.0003
0.0003 (r=4)
0.001
0.0004
r-AGIN
(r=2)
(r=3)
(r=3)
(r=1)
(r=3)
(r=2)
(r=3)

---

There is a strict hierarchy in the expressive power of the baselines: MPNN _ Subgraph GNN C/r 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.
Weal-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 ZINCI2K, we selected as base- line 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, 12-GNN, DRFWL). Following the standard procedure, we kept the number of parame- ters under 500K (Dwivedi et al., 2022a) for ZINC12K. The results are detailed in Table 3.
Table 3: Test MAE (L) on ZINC dataset.
Model
ZINC12K
ZINC250K
GIN
0.163 + 0.001
0.088 = 0.002
GCN
0.321 + 0.009
GAT
0.384 + 0.007
GSN
0.115 = 0.012
CIN
0.079 + 0.006
0.022 0.002
NestedGNN
0.111 + 0.003
0.029 = 0.001
For the QM9 dataset, we followed the setup of (Huang et al., 2022; Zhou et al., 2023). Specifically, the test MAE multiplied by the standard deviation of the target and divided by the corresponding con- version unit. The baseline results and models were obtained from (Zhou et al., 2023), including expres- sive GNNs with provable cycle counting power. We omit methods that use additional geometric features to focus on the model's s expressive power. The results
SUN
0.083 + 0.003
GNNAK+
0.080 = 0.001
12-GNN
0.083 = 0.001
0.023 = 0.001
DRFWL
0.077 0.002
0.025 = 0.003
SignNet
0.084 = 0.004
0.024 0.003
HIMP
0.151 = 0.006
0.036 = 0.002
PathNN
0.090 = 0.004
3-EGIN
0.072 0.002
0.022 = 0.001
are presented in Table 4.
Table 4: Normalized test MAE (L) on QM9 dataset. Top three models as
2nd 3rd
Model
Target
I-GNN
1-2-3-GNN
DTNN
Deep LRP NestedGNN
12-GNN DRFWL
5-EGIN
0.493
0.476
0.244
0.364
0.428
0.428
0.346
0.350
#0.011
0.78
0.27
0.95
0.298
0.290
0.230
0.222
0.21
#0.025
Ehomo
0,00321
0.00337
0.00388
0.00254
0.00265
0.00261
0.00226
0.00 0.00205
10,000
Ehamo
0.00355
0.00351
0.00512
0.00277
0.00297
0.00267
0.00225
0.00216
+0.00004
(ee)
0,0049
0.0048
0.0112
0.00353
0,0038
0.0038
0.00324
0.00321
0.0000
R²
34.1
22.9
17.0
19.3
20.5
18.64
15.04
13.21
=0.19
ZVPE
0.00124
0.00019
0.00172
0.00055
0.0002
0.00014
0.00011
0.000127
10 0000000003
Up
2.32
0.0427
2.43
0.413
0.295
0.211
0.156
0.0418
U
2.08
10.111
2.43
0.413
0.361
0.206
0.153
0.023
+0.023
H 2.23
0.0419
2.43
0.413
0.305
0.269
0.145
0.0352
+0.0004
G 1.94
0..0499
2.43
0,413
0.489
0,261
0.156
0.01 18
10.0015
C. 0.27
0.0944
2.43
0.129
0.174
0.0730
0.0901
0.0702
10.0024
Discussion of Results The results in Figures 3 and 4 and Table 1 constitute a strong empirical validation of our theory: increasing leads to more expressive r-LMPNN. Albeit 6-LWL is not less powerful than 3-W LL (see, e.g., Section 5.2), in practice, smaller values of r can already distinguish pair of graphs that are 3-WL equivalent, such the Shrikhande and the (4x4) rook graphs. In the BREC dataset, 4-&GIN distinguishes all pairs of strongly regular graphs, significantly outperforming 3-WL (0/50 graphs). Notably, 4-EGIN can already distinguish 257 out of 400 total pairs of graphs, surpassing other expressive GNNs like PPGN (233/400), theoretically equivalent to 3- 3-WL, and NestedGNN (166/400). Refer to (Wang al., 2024, Table 2) for detailed baseline results.
The results in Table 2 further substantiate our theory, as r-W.. can effectively count cycles of length r+2 (sec, e.g., Theorem 1).

---

On molecular datasets, we observe that r-EGIN, although designed for subgraph- subgraph-counting cycles and homomorphism-cooee -ountinng cactus graphs, is highly competitive. Notably, we outperform the baseline O-EGIN by 226% on ZINC12K and 400% on ZINC250K and surpass domain-agnoste 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')) 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 takes just over a minute.
Conclusion
In this paper, introduce novel hierarchy of color refinement algorithms, denoted r-LWL, which incorporates an augmented neighhorhood mechanism accounting for nearby paths. We establish connections between r-L and the classical k-WL. We construct a GNN (r-(MPNN) designed to emulate and match the expressive powerof r-L Theoretical and empirical evidence support the claim that r-MMPNN can effectively subgraph-count eycles and homomorphism-coum cactus graphs.
Future research could focus on precisely characterizing the expressivity r-&WL tests by iden- tifying the maximal class of graphs that r-LWL can tomomorphism-count, This would facilitate comparisons by constructing pairs of graphs that r-LWL cannot separate, but other WL variants can. Another promising direction involves exploring the generalization capabilities of GNNs with prov- able nomomorphism-couniie
properties. The ability to homomorphism count count certain motifs could provide mathematical framework support the intuitive notion that the capacity count relevant features may improve generalization. We observed this improved generalization experimentally in ablation study on ZINC12K (see, e.g., Table 8).
Acknowledgements
R.P. is funded by the Munich Center for Machine Learning (MCML).
S.M. is funded by the NSF-Simons Research Collaboration the Mathematical and Scientific Foundations Deep Learning (MoDL) (NSF DMS 2031985) and DFG SPP 1798, KU 1446/27-2.
P.W. is funded by the Vienna Science and Technology Fund (WWTF) project StruDL (ICT22-059).
G.K. acknowledges partial support by the Konrad Zuse School of Excellence in Reliable Al (DAAD), the Munich Center for Machine Learning (BMBF) as well as the German Research Foundation under Grants DFG-SPP-2298. KU 1446/31-1 and KU 1446/32-1, Furthermore, G.K. acknowledges support from the Bavarian State Ministry for Science and the Arts as well as by the Hightech Agenda Bavaria.
References
Abboud, R., Ceylan, I. I., Grohe, M., and Lukasiewicz, T. (2021). "The Surprising Power of Graph Neural Networks with Random Node Initialization". In: International Joint Conference on Artificial Intelligence (IJCAI), pp. 2112-2118.
Abboud, R., Dimitrov, R., and Ceylan, I. I. (2022). "Shortest Path Networks for Graph Property Prediction". In: Learning Graphs Conference (LoG), 5:1-5:25.
Arvind, V., Fuhlbrück, F., Köbler, J., and Verbitsky, O. (2020). "On Weisfeiler-Leman Invariance:
Subgraph Counts and Related Graph Properties" In: Journal of Computer and System Sciences
113, pp. 42-59.
Arvind, V., Köbler, J., Rattan, G., and Verbitsky, O. (2015). "On the Power of Color Refinement". In: International Symposium Fundamentals of Computation Theory (FCT). Vol. 9210. Lecture Notes in Computer Science, pp. 339-350.
Balcilar, M., Heroux. P., Gauzere, B., Vasseur, P., Adam, S., and Honeine, P. (2021). "Breaking the Limits of Message Passing Graph Neural Networks". In: International Conference on Machine Learning (ICML), pp. 599-608.
10

---

Barceló, P.. Geerts, F., Reutter, J., and Ryschkov, M. (2021). "Graph neural networks with local graph parameters". In: Advances in Neural Information Processing Systems (NeurIPS), pp. 25280-225 252933. Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C.,, Balamurugan, G., Bronstein, M. M., and Maron, H. (2021). "Fquivariant Subgraph Aggregation Networks". In: International Conference on Learning Representations (ICIR).
Bodnar, C., Frasca, F., Otter, N., Wang, Y., Liò, P., Montufar, G. F., and Bronstein, M. (2021). "Weis-
feiler and Lehman Go Cellular: CW Networks". In: Advances in Neural Information Processing
Systems (NeurIPS), pp. 2623-2640.
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. (2023). "Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting". In: IEEE Transactions on Pattern
Analysis and Machine Intelligence 1,. pp. 657-668.
Bresson, X. and Laurent, T. (2017). "Residual gated graph convnets". In: arXiv preprint
17X
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., and Vandergheynst, P. (2017). "Geometric Deep Learning: Going beyond Euclidean Data". In: IEEE Signal Processing Magazine 34.4, pp. 18 42. Cantwell, G. T. and Newman, M. E. J. (2019). "Message Passing on Networks with Loops". In: Proceedings of the National Academy of Sciences 116.47, pp. 23398-23403.
Chen, Z. Chen, L., Villar, S., and Bruna, J. (2020). "Can Graph Neural Networks Count Substruc- tures?" In: Advances in Neural Information Processing Systems (NeurIPS), pp. 10383-10395. Chen, Z., Villar, S., Chen, L., and Bruna, J. (2019). "On the equivalence between graph isomorphism testing and function approximation with guns". In: Advances in Neural Information Processing Systems (NeurIPS), pp. 15868-15888 15876.
Colbourn, J. and Booth, K. S. (1981). "Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs". In: SIAM Journal on Computing 10.1, pp. 203-225.
Curticapean, R., Dell, H., and Marx, D. (2017). "Homomorphisms are good basis for counting small subgraphs". In: ACM SIGACT Symposium on Theory of Computing (STOC), pp. 210-223. Cybenko, G. (1989). "Approximation by superpositions of a sigmoidal function"" In: Mathematics of control, signals and systems 2.4, pp. 303-314.
Dasoulas, G., Santos, L. D., Scaman, K., and Virmaux, A. (Jan. 7, 2021). "Coloring Graph Neural Networks for Node Disambiguation" In: International Joint Conference Artificial Intelligence (IJCAJ). pp. 2126-2132.
Dell, H., Grohe, M., and Rattan, G. (2018). "Lovász Meets Weisfeiler and Leman". In: International Colloquium on Automata, Languages, and Programming (ICALP). Vol. 107. LIPIcs, 40:1-40: 14. Deshpande, M., Kuramochi, M., and Karypis, G. (2002). "Autoomted Approaches for Classifying Structures". In: ACM SIGKDD Workshop on Data Mining in Bioinformatics (BIOKDD), pp. 11-18. Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. (2022a). "Bench- marking Graph Neural Networks". In: Journal of Machine Learning Research 24.43, pp. 1-48. Dwivedi, V. P.. Rampáek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. (2022b). "Long Range Graph Benchmark". In: Advances in Neural Information Processing Systems. Ed. by S. KKoyeoo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh. Vol. 35. Curran Associates.
Inc., pp. 22326-22340.
Fan, W., Ma, Y., Li, Q.. He, Y., Zhao Y. E., Tang. J., and Yin, D. (2019). "Graph Neural Networks for Social Recommendation". In: The World Wide Weh Conference ( (WWW), pp. 417-426.
Feng, J., Chen, Y., Li, Sarkar, A., and Zhang, M. (2022). "How Powerful are K-hop Message Pass- ing Graph Neural Networks". In: Advances in Neural Information Processing Systems (NeurIPS). Fey, M., Yuen, J. G., and Weichert, F. (2020). "Hierarchical Inter-Message Passing for Learning on Molecular Graphs". In: ICML Graph Representation Learning and Beyond (GRL+) Workhop. Fey, M. and Lenssen, J. E. (2019). "Fast Graph Representation Learning with PyTorch Geometrie".
In: ICLR Workshop on Representation Learning on Graphs and Manifolds.
Frasca, F., Bevilacqua, B., Bronstein, M., and Maron, H. (2022). "Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries". In: Advances in Neural Information Processing
Systems (NeurIPS). pp. 31376-313999
Fürer, M. (2001). "Weisfeiler-Lemmar Refinement Requires at Least Linear Number of Iterations".
In: Automata, Languages and Programming. Ed. by F. Orejas, P. G. Spirakis, and J. van Leeuwen,
pp. 322-333.
Geerts, F. and Reutter, J. L. (2022). "Expressiveness and Approximation Properties of Graph Neural Networks". In: International Conference on Learning Representations (ICLR).

---

Gilmer, J.. Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. (2017). "Neural Message Passing for Quantum Chemistry". In: International Conference on Machine Learning (ICML), pp. 1263-1272.
Graziani, C.,, Drucks, T., Jogl, F., Bianchini, M., scarselli, franco, and Gärtner, T. (2024). "The Expressive Power of Path- Fath-Based Graph Neural Networks". In: Forty-first International Conference on Machine Learning.
Hagberg, A. A., Schult, D. A., Swart, P., and Hagberg. J. (2008). "Exploring Network Structure, Dynamics, and Function using NetworkX", In: Python in Science Conference (SciPy),
Harary, F. and Uhlenbeck, G. E. (1953). "On the Number of Husimi Trees, I". In: Proceedings of the National Academy of Sciences of the United States of America 39.4, pp. 315-322.
Hornik, K., Stinchcombe, M., and White, H. (1989). "Multilayer feedforward networks are universal approximators". In: Neural networks 2.5, pp. 359-366.
Hu*, W., Liu*, B., Gomes, J., Zitnik, M.,, Liang, P., Pande, and Leskovec, J. (2020a). "Strategies for Pre-training Graph Neural Networks". In: International Conference on Learning Representations (ICLR).
(2020b). "Strategies for Pre-training Graph Neural Networks". In: International Conference on Learning Representations.
Huang, Y., Peng, X., Ma, J., and Zhang, M. (2022). "Boosting the Cycle Counting Power of Graph Neural Networks with 12 I²-GNNs". In: International Conference on Learning Representations (ICLR).
loffe. S. and Szegedy, C. (2015). "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift". In: International Conference on Machine Learning, (ICMI...
Vol. 37, pp. 448 4566.
Irwin, J.. Sterling, T., Mysinger, M. M., Bolstad, E. S., and Coleman, R. G. (2012). "ZINC: A Free
Tool to Discover Chemistry for Biology". In: Journal of Chemical Information and Modeling 52,
pp. 1757-1768.
Jin, E., Bronstein, M., Ceylan, I., and Lanzinger. M. (2024). "Homomorphism Counts for Graph Neural Networks: All About That Basis", In: International Conference on Machine Learning (ICML).
Keriven, N. and Peyré, G. (2019). "Universal invariant and equivariant graph neural networks". In: Advances in Neural Information Processing Systems (NeurIPS), pp. 7090-7099.
Kingma, D. P. and Ba, J. (2015). " "Adam: A Method for Stochastic Optimization". In: International Conference on Learning Representations (ICLR).
Kipf, T. N. and Welling, M. (2017). "Semi-SSuerriie"
Classification with Graph Convolutional Networks". In: International Conference on Learning Representations (ICLR).
Kirkley, A., Cantwell, G. T., and Newman, M. E. J. (2021). "Belief Propagation for Networks with Loops". In: Science Advances 7.17, eabf1
Korte, B. and Vygen, J. (2018). Combinatorial Optimization. Springer.
Koyutürk, M., Grama, A. Y., and Szpankowski, W. (2004). "An efficient algorithm for detecting frequent subgraphs in biological networks". In: Bioinformatics 20 Suppl 1, pp. i200-7. Lanzinger, M. and Barcelo, P. (2024). "On the Power of the Weisfeiler- Parameters". In: International Conference on Learning Representations (ICLR).
Test for Graph Motif
Lim, D., Robinson, J. D., Zhao, L., Smidt, T., Sra, S., Maron, H., and Jegelka, S. (2022). "Sign and Basis Invariant Networks for Spectral Graph Representation Learning". In: International Conference on Learning Representations (ICLR). Lovász, L. M. (1967). "Operations with structures". In: Acta Mathematica Academiae Scientiarum Hungarica 18, pp. 321-328.
Maron, H., Han-Hamu, H., Serviansky, H., and Lipman, Y. (2019a). "Provably Powerful Graph Networks". In: Advances in Neural Information Processing Systems (NeurIPS), pp. 2153-2164. Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. (2018). "Invariant and Equivariant Graph Networks". In: International Conference
Learning Representations (ICLR).
Maron, H., Fetaya, E., Segol, N., and Lipman, Y. (2019b). "On the Universality of Invariant Networks... In: International Conference on Machine Learning (ICML). pp. 4363-4371.
Maskey, S., Parviz, A., Thiessen, M., Stärk, H., Sadikaj, Y., and Maron, H. (2022). "Generalized Laplacian Positional Encoddin for Graph Representation Learning.. In: NeurIPS 2022 Workshop on Symmetry and Geometry in Neural Representations.
Michel, G., Nikolentzos, G., Lutzeyer, J. F., and Vazirgiannis, M. (2023). "Path Neural Networks: Expressive and Accurate Graph Neural Networks". In: International Conference on Machine Learning (ICML), pp. 24737-24755
12

---

Monti, F., Boscaini, D., Masci, J.. Rodola, E., Svoboda, J., and Bronstein, M. M. (2017). "Geometric deep learning on graphs and manifolds using mixture model enns". In: IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pp. 5115-5124.
Monti, F., Frasca, F., Eynard, D., Mannion, D., and Bronstein, M. M. (2019). Fake News Detection on Social Media using Geometric Deep Learning. arXiv: 1902. 1902.06673. 06673.
Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. (2023). "Weisfeiler and Leman Go Machine Learning: The Story so Far". In: Journal of Machine Learning Research 24, 333:1-333 133:3-333
Morris, C., Rattan, G., and Mutzel, P. (2020). "Weisfeiler and Leman go sparse: Towards scal- able higher-order graph embeddings". In: Advances in Neural Information Processing Systems
(NeurIPS). pp. 21824-218848
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. (2019). "Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks". In: AAAI Conference on Artificial Intelligence (AAAI), pp. 4602-4609.
Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. (2019). "Relational Pooling for Graph Represen- tations". In: International Conference on Machine Learning (ICML), pp. 4663-4673. Neuen, D. (2024). "Homomorphism- hetttoorrhisn--iiiiiuuiiiisii Distinguishing Closedness for Graphs of Bounded Tree-Width". In: International Symposium on Theoretical Aspects of Computer Science (STACS), 53:1 Nguyen. H. and Machara, T. (2020). "Graph Homomorphism Convolution". In: International Confer- ence on Machine Learning (ICML), pp. 906-7316.
Nishi, T. and Chua, L. (1986). "Uniqueness of solution for nonlinear resistive circuits containing CCCS's s or VCVS's whose controlling coefficients are finite". In: IEEE Transactions on Circuits and Systems 33.4, pp. 381-397.
Paszke, A. et al. (2019). "Py'Torch: An Imperative Style, High-Performance Deep Learning Library".
In: Advances Neural Information Processing Systems (NeurIPS), pp. 8024-8028 8035.
Paten, B., Diekhans, M., Earl, D., John, J. S., Ma, J., Suh, B., and Haussler, D. (2011). "Cactus graphs for genome comparisons". In: Journal of Computational Biology 18.3, pp. 469-481.
Qian, C., Rataann G., Geerts, F., Niepert, M., and Morris. C. (2022). "Ordered subgraph aggregation
networks". In: Advances in Neural Information Processing Systems (NeurIPS), pp. 21030-21044
Sato, R., Yamada, M., and Kashima, H. (2021). "Random Features Strengthen Graph Neural Net- works". In: SIAM International Conference on Data Mining (SDM), pp. 333-341.
Scarselli, F., Gori, M., Tsoi, A. C.,, Hagenbuchner, M., and Monfardini, G. (2009). "The Graph Neural Network Model". In: IEEE Transactions on Neural Networks 20.1, pp. 61-80.
Stokes, J. M. et al. (2020). "A deep learning approach to antibiotic discovery". In: Cell 180.4, 688-
102.e13.
Tinhofer, G. (1986). "Graph isomorphism and theorems of Birkhoff type". In: Computing 36, pp. 285- 300.
(1991). "A note on compact graphs". In: Discrete Applied Mathematics 30, pp. 253-264, van Dam. E. R. and Haemers, W. H. (2003). "Which Graphs Are Determined by Their Spectrum?" In: Linear Algebra and its Applications. Vol. 373. Combinatorial Matrix Theory Conference. pp. 241-272.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. (2018). "Graph Attention Networks". In: International Conference on Learning Representations (ICLR). Vignae, C., Loukas, A., and Frossard, P. (2020). "Building powerful and equivariant graph neural networks with structural message-passing" In: Advances in Neural Information Processing Systems (NeurIPS), pp. 14143-14155.
Wang. Y. and Zhang, M. (2024). "An Empirical Study of Realized GNN Expressiveness". In: International Conference on Machine Learning (ICML).
Weisfeiler, B. and Lehman., A. (1968). "The reduction of graph canonical form and the algebra which appears therein". In: Nauchno- Terichne-Tcchiicheskkaya Informatsia 9. Welke, P., Thiessen, M., Jogl. F., and Gärtner, T. (2023). Eiapectation-Complee Graph Repre- sentations with Homomorphisms". In: International Conference on Machine Learning (ICML),
pp. 00.33-69339222
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. (2018). MoleculeNet: A Benchmark for Molecular Machine Learning. arXiv: 1703. 00564. Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2019). "How Powerful Are Graph Neural Networks?"
In: International Conference on Learning Representations (ICLR).
You, J., Gomes-Selman, J. M., Ying, R., and Leskovec, J. (2021). "Identity-Aware Graph Neural
Networks". In: AAAI Conference on Artificial Intelligence (AAAI), pp. 10737-10745.
13

---

Zhang, B., Gai, J., Du, Y., Ye, Q., He, D., and Wang, L. (2024). "Beyond Ceisfeiler-Lehman, A Quantitative Framework for GNN Expressiveness". In: International Conference on Learning Representations (ICIRR).
Zhang, M. and Li, (2021). "Nested Graph Neural Networks". In: Advances 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 Learning Representations (ICLR).
Zhou, J., Feng. J., Wang, X., and Zhang, M. (2023). DDistnce-RResrictter Folklore Weisfeiler-Lent GNNs with Provable Cycle Counting Power". In: Advances in Neural Information Processing Systems (NeurIPS).
14

---

Appendix
Table of Contents
Additional Figures
16
B Additional Notions
18
Higher-Order Weisfeiler-Leman Tests
C Experimental Details
19
C.I Synthetic Datasets
20
C.2 Real-World Datasets
20
D Preparation for Proofs
23
E Appendix for Scction 5.1
23
F Appendix for Scction 5.2
24
G Appendix on Homomorphism Counting and Section 5.3
25
G.1 Tree Decomposition Preliminaries.
26
G.2 Cactus Graphs and their Canonical Tree Decomposition
26
G.3 Altemative r-LWL ............
29
G.4 The Unfolding Tree r-WWL
H Implications of Theorem
40
H.1 Appendix on F-Hom-GNNs and Proof of Corollary 2
40
H.2 Appendix on Subgraph GNNs and Proof of Corollary ii)
41
H.3 Appendix on Subgraph k-GNNs and Proof of Corollary 2 iii)
42
H.4 Proof of Corollary 2 iv)
43
Appendix for Section
15

---

A
Additional Figures
Homomorphism
Subgraph Isomorphism
Bijective Homomorphism
Isomorphism
Figure 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, mappings h V(F) - VGG are visually represented with colors, where F' is consistently on the left, and G is on the right in each row.
No(u)
-- Ni
mh No
(2
(b)
Figure 6: Example of two non-isomorphic graphs that are r-LWL equivalent but not (r+1)- equivalent: chordal cycle (left) and cactus graph (right).
16

---

6
3
(a) Input graph F.
3, (2, 4]
4, {6,3)
1,
2, (1,3)
6, (4,5)
3, (1, 2}
4,
3,0 0
(5,6)
1, (2,3)
5, {4,
6, 0
2, 0
3, (1,4)
4, [5
(b) Fürer graph G(F): hom F, G(F))
68.
3, (2, 4)
4, {6,3)
1, 0
2, (1
6, (4,5)
3, (1,2}
4,
3, 0
4, (5.6)
(2,3)
5, {4,
6, 0
2,
3, (1,4)
4, (5,3)
(c) Twisted Fürer graph H (F): hom H(F)) 34.
Figure 7: Example of graphs that Subgraph GNNs cannot separate but 1-tWL can: Subgraph GNNs cannot separate G(F) and (FF). However, since hom (F, G(F) * hom(F, H(F)) and is cactus graph, 1- can separate G(F) and H (F) by Theorem 2.
17

---

(a) COSPECTRAL10.
SR16622.
(c) CSL example, skip length (left) and 3 (right).
Figure 8: Some synthetic datasets. The dotted lines are the common edges. The orange edges identifies (i))).
Additional Notions
B.1 Higher-Order Weisfeiler-Leman Tests
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 k-tuple of elements of V(G)
V(G)*, V(H) = {v (ui) l v(()) -VG)),
and edges E(H) are built among those k-tuples that differ one entry only
E(H) [[v.u] u} dv u) u e.ve
where de is the Hamming distance. The algorithm assigns to each node v E V(H) an initial color depending the isomorphic type of the induced subgraph G[v]. The color refinements scheme is
18

---

exactly (1) applied to H. While H can be generated by simple algorithm, the approach quickly
becomes impractical as the number of nodes and edges grows exponentially in
(a) Input graphs.
(b) 1-WL after one iteration.
(c) 3-WL initialization.
(d) 1- 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 graphs heeding the original graph sparsity.
C Experimental Details
Our model is implemented in PyTorch (BSD-3 license) (Paszke et al., 2019), using PyTorch Geometric (MIT license) (Fey al., 2019). The r-neighhorhoods are computed with NetworkX (Creative Commons Zero v1.0 Universal) (Hagberg et al., 2008) preprocessing. Hyperparameters
19

---

on real-world datasets were tuned using grid search; for synthetic experiments, we fixed one configu- ration 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).
C.1 Synthetic Datasets
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 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 vosssvvlidation.. The CSL dataset is provided by torch gew.etriccccco..... 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 hyperparameters can be found in Table 5. For the synthetic datasets, fixed one configuration and studied the effect of increasing counting power of the architecture.
the expressive and
For the SR16622, GRAPH&C, EXP_ISO, and COSPECTRALII datasets, 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 a-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).
Table 5: Hyperparameter configuration for synthetic experiments.
SUBGRAPHCOUNE
COSPECTRA10
GRAPHEC
SR16622
EXP ISO
CEXP
BREC
EXP
CSL.
Epochs
10a
10a
10a
1.210
40
Learning Rate
10-3
10-3
10-3
10-3
10-4
Early Stopping
Ir < 10-5
Ir < 10-3
Ir < 10-5
Ir < 10-5
Scheduler
(50, 0.5)
{50, 0.5)
{50, 0.5)
(10,0.9)
(50, 0.5)
Hidden Size
64
64
64
64
64
64
64
64
32
Num. Layers
3
Num. Encoder Layers
2
2
2
2
2
Num. Decoder Layers
2
Batch Size
64
64
64
64
64
64
64
128
64
Dropout
Readout
sum
C.2 Real-Worke Datasets
All real-world datasets are provided by torch _eohbggeomerccc The splits for both ZINC datasets are also provided by borch_geometric. For QM9, we follow the set-up of (Zhou et al., 2023) and use random 80/ 80/10/10 100 splits. Details for the datasets are provided in Table 6.
Hyperparameters were tuned using grid search. For ZINCI2K, the grid was defined by Hidden Size (64, 128) and Num. Layers E {3, 4, 5). For ZINC250K, the grid was defined by Hidden Size E (128, 256} and Num. Layers {4]. For the QM9 tasks, the grid was defined by Hidden Size (64, 128) and Num. Layers {3, 4, 4,5). For the QM9 tasks, we followed the training set-up of scheduler, reducing the learning rate by a factor of 0.9 if the validation metric did not decrease for 10 epochs. The exact hyperparameters given in Table 7.
(Zhou et al., 2023), training for 400 epochs with ReduceeLROnPlttenn
20

---

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-LGIN. Within the r-EGIN layers, we process the edge features via 2-layered learnable MLP, and replace the GIN in (4) by GINE layers (Hu* et al., 2020a). After rounds of r-LGIN layer, we apply two-layered MLP as decoder layer. In all experiments, BatchNormiD (loffe et al., 2015) is used in the MLP layers. We refer to Figure for depiction of the architecture.
Table 6: Statistics of real-world datasets.
Dataset
Number of graphs
Average number of nodes
Average number of edges
QM9
130 831
18.0
18.7
ZINC12K
12 000
23.2
24.9
ZINC250K
249 456
23.2
24.9
Table 7: Hyperparameters configuration for real-world experiments.
ZINCI2K
ZINC250K
QM9 (1)
QM9 (a)
QM9 (Chomo)
Epochs
1000
2000
400
400
400
Learning Rate
0.001
0.001
0.001
0.001
0.001
Early Stopping
Ir 10-5
Ir < 10
Ir < 10
Ir < 10
Ir 10
Scheduler
{50, 0.5)
0.53
f10, 0.9)
f10, 0.9}
{10,0.4 0.9)
I
5
5
5
Hidden Size
64
256
64
64
64
Depth
3
4
4
5
Batch Size
64
128
64
64
64
Dropout
0
Readout
sum
sum
sum
sum
sum
# Parameters
452 633
2379 041
418481
519
519 677
Preprocessing Time [sec]
77.4
1278.5
427.5
425.9
517.4
Run Time per Seed [h]
2.8
45.6
13.6
15.9
21.1
Table 8:
Ablation study on the effect of in r-EGIN, ZINC12K.
MAE (1)
Model
Train
Test
O-EGIN
0.060 + 0.009
0.209 + 0.007
1-8GIN
0.060 = 0.012
0.201 + 0.004
2-EGIN
0.068 + 0.011
0.198 + 0.008
3-EGIN
0.056 + 0.013
0.184 + 0.007
4-EGIN
0.0203 + 0.0002
0.077 + 0.001
5-6GIN
0.022 + 0.004
0.072 + 0.002
6-EGIN
0.028 + 0.000
0.077 + 0.000
21

---

Table Test metrics on long-range graph benchmark datasets (Dwivedi al., 2022b). The baseline results are obtained from (Dwivedi et al., 2022b, Table 4), Our method is able enhance performance over standard baselines.
PEPTIDES
Model
STRUCT (MAE L)
FUNC (AP 1)
GCN
0.3496 + 0.0013
59.30 0.23
GINE
0.3496 + 0.0013
59.30 + 0.23
GatedGCN
0.3420 + 0.0013
58.64 + 0.77
7-EGIN
0.2513 + 0.0021
65.70 + 0.60
Table 10: Empirical time complexity for QM9 dataset; results from (Zhou et al., 2023). the size of the dataset after the computation of r-neighborhoods.
In parenthesis
Model
Memory usage [GB]
Preprocessing [sec]
Training [sec/epoch]
MPNN
2.28
64
45.3
NestedGNN
13.72
2354
107.8
I2-GNN
19.69
287
209.9
2-DRFWL
2.31
430
141.9
0-EGIN
0.02 (0.39)
191
44.7
1-EGIN
0.03 (0.48)
370
66.4
2-EGIN
0.05 (0.57)
388
84.0
3-EGIN
0.07 (0.66)
408
85.2
4-EGIN
0.10 (0.82)
427
96.9
5-EGIN
0.12 (0.91)
444
130.6
22

---

D Preparation for Proofs
We begin by recalling some core concepts that are relevant for Section and the proofs therein.
Definition 10. A node invariant {() is mapping that assigns to each graph G 9 function
Sa (G) + P, which satisfies
Vo ((C))) C (n((()))
where is any graph isomorphic to and h is the corresponding isomorphism from H to G.
The following definition enables to compare the expressive power of different node invariants. Definition 11 (Node Invariant Refinement). Given two node invariants y and Ç. We say that refines y if for every fixed graph G and nodes u, v V ((),, it holds Ça(u) <a(v) Ta(u) (c(v). We write Ç 7
We emphasize that every node invariant Ç induces graph invariant A[r by collecting the multiset, i.e. G G ((Ga())))vevcc)) We denote the induced graph invariant of node invariant y as A(r))-
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 Y be node invariant. If C % then A(c] is more powerful than A(7]].
Proof. Let G, be two graphs, and let P be the underlying palette of S, Consider the function
6: P, ((w) + 7(u) Vu U(G)
As consequence of [ 7, á is well-defined, since
((u) = ((u) = (60 = = r()) = (6 ( (v).
Assume that A[) A[(](H),,,,
{{((u) UE V(G)] (((()) UUE v(H)))
As ø is well-defined, we have
(()) | qe [VV)) ( vEV()))
which leads to Ah) (H).
E Appendix for Section 5.1
In this section, we provide the proof of Proposition from the main paper.
Proposition 1. Let < q < r. Then, r-LWL is strictly more powerful than q-LWL. In particular, every r-LWL is strictly more powerful than 1-WL.
Proof of Proposition 1. Let r 2 O. We aim to prove that (r + 1)-LWL is strictly more powerful than r-LWL. We begin by demonstrating that (r + 1)-(WL is more powerful than r-LWL.
To establish this, we rely on Lemma 1. Specifically, we demonstrate that the underlying (r 1)-CWL node invariant 4 refines cy. Moreover, we beyond and show that the node invariant c,41 refines
(t)
& at every iteration / 2 0, which shows that / iterations of (r + 1)-CWL are more powerful than I iterations of r-LWL.
For this purpose, let G be graph with node set (G). For t = 0, c C Cr start with the same labels. By induction, we assume that
(0)
since both algorithms
(w) = ( = (0 (1) = c1)
(5)
holds; we need to prove that (5) implies
(++1) (w) (t+1) (c) - ((+ -c+ ((+1)(v). 441
(6)
23

---

Since HASH in Definition is injective, (0) (u) = (0 (v) in (5) leads to
N (
{{ ((2i(() (D)
{[
( (()4(()) (p) | p.N
for all & E (o,...,,).. r). The assumption o (u( = 4 (v in (5) is satisfied for every path u = Juixx] E (N)(u) and vf = {oLA)] E NG)(v) for q 0. o,...,,,, I,....IW.. and le , -9 1.
Hence,
(p) (D) Nului) {{ c (p) |p N
Inputting this into Definition 7, we get (6), i.e (1+1) _ (++1)
The "strictly" can be deduced as follows. The cycle graph (2r + 6) nodes equipped with chord between nodes 1 and r + is r-WWL equivalent to the graph consisting of two (r + -yycclss connected by one edge; however, they are not (r + 1)-EWL equivalent (see, e.g., Figure 6).
F
Appendix for Section 5.2
The goal of this subsection is provide proof for Theorem and Corollary 1. In fact, present and prove a more general statement, Specifically, for a graph G' and v E VG),, we introduce the node invariant sub(F", G"), defined the count of subgraph isomorphisms from F to G that rooted, meaning that æ is mapped to v. Let us denote this node invariant as sub(F",,)) -). Our result establishes that af (.) refines sub(C",") :) for every cycle graph C with at most nodes. In simpler terms, (2) can determine how often node appears in cycle C.
Lemma 2. Let r 2 1. For every cycle graph C' with at most r + 2 nodes and x E V(C), holds Sub(C
Proof of Lemmaa 2. Let G' be any graph, u E V(G), and g 1, I,...,7-- 2. Let C be cycle graph with nodes. is important to note that for every Iı, 02 E C, we have sub(C G*) ) Sub(C"a, G*) since every node in C is automorphic to each other. Therefore, we can arbitrarily choose any x E VCC).
We show that
sub
& sub (C*, (
The number of injective homomorphisms from the g-long cycles C to G", i.e., sub(Ca G"), is equal to the number of paths of length (g- - 2) between distinct neighbors u.
The neighborhood (v) comprises exactly all paths of length (g 2) between any two distinct neighbors of v. Therefore,
sub (C" (Nio-
Thus
sub # sub G") - [NG + (N)-
which implies
{{ ((0220)) De Mor2((u13} # ((-2)
p - : N10
Finally, as HASH Definition 7 is injective, we get the thesis 2 # (0)2
(1)
Now, Theorem from the main paper is simple corollary of Lemma 2.
Theorem 1. For any 2 r-LWL can subgraph-count all cycles with most + 2 nodes.
Proof of Theorem 1. Combining Lemma 2 and Lemma 1, we get that (()) (as a graph invariant) is stronger than the induced graph invariant A [sub( (abb((,))) .)]. Now, consider graphs G. H, and assume without loss of generality that [V(G) [VH)
24

---

If c (G) (H). we have A [sub((", (G) A [sub(C : (H). Hence, by definition of induced graph invariants,
w ((I))).
Hence,
sub(C*, G*) Σ sub(C", H)), .EV(G)
Σ
wEV(I)
which is equivalent to sub(C, G) sub(C, H).
We proceed restate Corollary 1 and provide its proof. Corollary 1. Let E N. There exists E N, such that r-EWL is not less powerful than k- B-WL. Specifically, r E O(k2), with r S k(k+1) for even and r S (k+1)²
2 - for odd k.
Proof of Corollary 1. Let & >> O. We need show that there exist rиk N and pair of graphs G, H. such that k- (LW = k- (H) and ry-(WL(G) + rg-(WL((H).
The hereditary treewidth hdtw(F') of graph F is the maximum treewidth of (FF) where is an edge surjective homomorphism. Neuen (2024) has shown that k-WL can subgraph-cov coouph a graph F if and only if hdtw(FF (F) S k. This directly implies that for F with hereditary treewidth larger than there exist graphs Gr, HE with k: pL = k (-WL((H (Hr) and sub(F, G) 7 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 Co, of length Cg E N with hereditary treewidth larger than k. Setting F Co., concludes the existence proof with rι Ca 2.
To see that rы E O(k)), note that the complete graph Kn n vertices has treewidth n 1 and exactly (H) edges. For odd n, K,, is Fulerian, i.e., there exists edge surjective homomorphism from a cycle to K,, which uses each edge exactly once, i.e., from C(z). n is odd, the minimum T-join which makes Kn Eulerian contains exactly z edges (see, e.g., Korte al., 2018). As result, there exists an edge surjective homomorphism from C(z) to K, if n is odd, and an edge surjective homomorphism from C(:)+ to K,, if is even. This implies that hddw((Ce) > & for Cx ((+) 1. Hence, T& == Ck O(
G Appendix on Homomorphism Counting and Section 5.3
In 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) E(G)) and S C VGG.. The induced subgraph G[S] of over defined as the graph G[S] with vertices (GGS)) = and edges E(G[S]) = Hu, v) E E(G) u. 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 (u1, U2), the atomic type atpp ((1), uz) of G over (u1, U2) indicates where (u1, E E()), ie., atpo((u1, u2)) = 1 if (u1, U2) E E(G) and zero otherwise.
We continue by defining tree graphs, important class of graphs closely related to the 1-WL test.
Definition 14 (Tree Graph). A graph T is called tree (graph) if it is connected and does not contain cycles.
rooted tree 7 (V E(T))) is a tree which node s V(T") is singled out. This node is called the root of the tree. For each vertex t E V(T*), we define its depth depr= (t) := distr- (t, s). where dist denotes the shortest path distance between t and s. The depth T is then the maximum depth among all nodes t E VT).. We define Descr= (t) the set of descendants of I,, i.e. Desor= (1) = (L' E T depr- (t') = depr- + dist (')) For each E V(T*) \ {s}. we define the parent node pa (l) of 1 as the unique node L E N()) such that depy- (1) = deppr-(1)) + We define the subtree of T rooted at node & by T [*],,, ie.
[* := T [Descrr- (t)).
25

---

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-/WI. Appendix G.3 for technical reasons. Subsequently, in Appendix G.4, we define the unfolding tree of r- and illustrate its relation to the r-LWL. colors and canonical tree decompositions of fan cactus graphs. Finally, Appendix G.4.I, we establish the groundwork to conclude the proof of Theorem 2, simple corollary of all the results in this section.
G.1 Tree Decomposition Preliminaries
Along with its notation, this subsection closely adheres to the conventions outlined by Zhang et al. (2024, Section C). We start with formal definition of tree decomposition for graph.
Definition 15 (Tree Decomposition). Let G = (VGG),E(G) A tree decomposition of G is free T (V(T), E(T) together with function 3r : V(T)) - 2V( satisfying the following conditions:
1. Each tree node E (T)) is mapped to non-empty subset of vertices 3r(1) C CVGG) in G. referred to as a bag. We say tree node contains vertex u if E (r(().
2. For each edge {u,u} E E(G), there exists at least one tree node t E (TT such that {u, o} C (t).))
3. For each vertex E V(G), all tree nodes containing u form connected subtree, i.e., the induced subgraph T (t V(T): uu (t)} is connected.
If (T, (T)) is tree decomposition of G, we refer the upple (G,T, The width of the tree decomposition ofG is defined as
(G,T,8r) (TT tree-decomposed graph.
max KEV(T)
(3((1)-11
T has root 8, we also denote it as (G, Definition (Treewidth). The treewidth of a graph G, denoted as tw(G), is the minimum positive integer k such that there exists tree decomposition of width k.
G.2 Cactus Graphs and their Canonical Tree Decomposition
Cactus graphs play a crucial role in graph theory due to their unique structural properties. Before delving into their canonical tree decomposition, simplify the notation, we assume that graphs in this section are connected and that V(G) C N for all graphs G. Further, we assume that E N throughout this section.
define the concept of rooted r-cactus graph. To
Definition 17 (Rooted r-Cactus Graph). A cactus graph is graph where every edge lies at most one simple cycle. An r-cactus graph a cactus graph where every simple cycle has at most r vertices. A rooted cactus (graph) G is cactus graph G with root node E (G').
Now, we introduce the notion of a fan cactus, which is an essential concept for our subsequent discussions the canonical tree decomposition of these graphs.
Definition 18 (Fan Cactus). Let G be rooted r-cactus. For every simple cycle C in G let be the unique vertex in that is closest to 8. We obtain a fan r-cactus F from a rooted r-cactus G by adding arbitrary number of edges {vc, w) to any cycle C with E (CC.. Let M be the class of graphs F with s E (FF) such that FS a fan r-cactus.
Every r-cactus is a fan r-cuctus. Every fan r-cuctus is outerplanar Every outerplanar graph has tree-width at most 2.
Remark 1.
Figure 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 canonicalization function, that maps graphs to a unique representative each set of isomorphic graphs. We denote the set of all such representatives M / 2 C Mr+2
Lemma 3 (Colbourn et al. (1981)), There exists function canon - M such that
26

---

1. G = canon(G)
2. G H + V(canon(G)) = V (c)non((H)) A E(canon(GG) = E (Ccano((H))
Moreover, given G E M canon G) can be computed in linear time.
For each G E MM+ we denote the isomorphism between and canon (G) as canong. Colbourn et al. (1981) describe a bottom-up algorithm to obtain canon(G) of fan r-cactus G. We will implicitly use the results of this canonicalization to define a canonical free decomposition of fan r-cacti. The crucial point in the algorithm is simple way to decide which "direction" to when dealing with 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 tree decomposition for a rooted cycle which depends on a choice of direction and then define a canonical direction of eycles in G based canong.
Definition 19 (Tree Decomposition of Rooted Cycle), Let Cn be a cycle graph on n nodes to to 2n The path T nodes w W2n-3 with bags B(w1) {vo, vi and for
(3(m--1) (1/2+1] B(w,) (3(w,-1)\ 1)/22)
if is even if is odd
a tree decomposition of Cn. We say that Un and tn correspond to wi and v, corresponds to W2i-1 for 2 2.
depiction of the tree decomposition 7 (right) of Ca (left) is shown below. Note that we have to choose one of two possible orientations of the undirected cycle to construct 7 We address this choice in the next definition.
[0,2,3]
{0, 2]
{0. 1,2]
{0.3}
3
{0, 13
(0, 3, 4]
{0, 4]
[0, (,,4,5)
{5,0}
Definition 20 (Canonical Tree Decomposition of Undirected Rooted Cycle). Let F be a a r-cactus and be a simple cycle in the underlying cactus G. Let ec, UI,..., Un-1 and ve, Un-1,... U1 be the two directions of C' rooted at UC. We define the canonical tree decomposition of C' in G as the tree decomposition of the smaller of the two orientations canon canonp(ri)..... canon (Un-1) and (ac) canon (V..))...
canon (v1).
The choice of "smaller" does not matter as long as defines a total order. One can, for example, use a lexicographical order. Based on Definition 20, we now define a canonical tree decomposition of cactus graphs, 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 be a fan r-cactus and G its underlying r-cactus. We define the canonical tree decomposition T of F rooted at é as follows
1. Node Gadget: For all u E ((F) add a node to V(T) and set 3(t) {v}. We choose š such that ((3) = {s}.
2. Tree Edge Gadget: For all w E E(G) that are not on simple cycle in F add node x (y VTT) with ((I(v.))) {w, w) and edges {u, {u, } and { (w. (v,u)) E(T)
3. Cycle Gadget: For each (undirected) cycle C' in the underlying cactus G. add a copy of its canonical tree decomposition Tiee of C rooted at vc to and connect nodes in to the corresponding node gadgets.
See Figure 10 for an illustration. For the discussions in subsequent sections, we introduce the following definition.
27

---

[4)
C2
12
f1, 43
f4}
{1. 4,34
{4.
[1.2]
(1,3)
(7)
(2)
31 2)
(7.8)
{12}
{ 93
{7, 12)
(12, 13)
(2
[2,6]
[9]
(7.9)
[7. 11, 12)
(13)
(6)
10}
{7, 11)
10, 11)
{11)
{10}
Figure 10: Example of fan 6-cactus Fl (left) and its canonical tree decomposition (T, The underlying rooted 6-cactus GD (on colored, thick edges) of 1* contains three simple cycles C₁, C22 Cg. Additional diagonal edges must have Vc, as one endpoint.
Definition 22 (Depth in the Canonical Tree Decomposition of Fan r-Cactus Graphs). Let (F, (") ) be a canonical tree decomposition of a fan r-cactus. We define the depth dep(t) oft V(T) recursively as follows:
1. dep(s) =
2. For u E VTT) with parent node dep(c) (dep(p) + depp(p)
i/](()] =
or 13(p) =
otherwise
The depth of (F,T") is then the maximum depth of any node E V(T").
Intuitively, for given fan r-cactus graph F with its canonical tree decomposition 7 Definition 22 captures the depth (see Definition 15) of the tree T if cycles in F and the corresponding bags in T were replaced by single edges.
Lemma 4. Let F be a fan r-cactus. The canonical tree decomposition (F,T²) is a tree decomposi- tion of Fs
Proof. We need to show that (1) is a tree, (2) for every edge E E(F) there exists some bag ((v)
with ((v), and (3) Ti(t V(T) B(t)}] is connected.
To see that T does not contain cycles, note that we replace each cycle with its cycle gadget, which is that T is connected G is connected.
path. It is easy
For (2), note that tree edges e V(F) have their own gadget node in &e with (xx.) = e. Similarly, each edge
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 (MC, w) E F.(F) F(G),, ve is contained in any bag of the cycle gadget of C. As result, {ue, oa is contained in the bag of the corresponding node of
28

---

For (3), note that in the tree edge gadget, nodes t with E B(t) are connected to the node gadget of v. In the cycle gadget, any node with w E B(t) either directly or via its neighbor connected the node gadget of w if w & ui.. As the cycle gadget is connected and ve is in any bag of the gadget, path to the node gadget of ve exists where every bag contains rc-
We conclude this subsection with 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 H' are isomorphic whenever G H'' are isomorphic.
Definition 23 (Isomorphism between canonical tree- decomposeddd graphs). Given two canonical tree-decomposed graphs (G,T") and (G, (5, a pair of mappings (p.T) is called an isomorphism between (G, T and (G, T.), denoted by (G, T*) = (G,T*), if the following holds:
p is an isomorphism between G and G.
T is an isomorphism between T and T
For any T we have ((3r(t)) = (T((())).
Lemma Let G = H' be rooted r-fan cacti. Then (G*, T(G*) (H', ((H)).
Proof. Let be root preserving isomorphism between G and H According to Lemma 3 then there exist isomorphisms canong and canon with canong canon We construct T: VVT[G*)) - ((T from p as follows: easy to see that p induces bijective mapping between the nodes of G and T[H that assigns each gadget node VTT(G*)) to the unique gadget node T(U) E ()THH)) with ((T()) = p(B(u)). By the same argument, maps the root of T[G*] to the root of T[
Now assume by contradiction that is not an isomorphism between T and T T[H). That means that w.l.o.g. there exists {u,w} E G(] with (7(U), [(w)} & H"). However, for the bags of v, w holds (a = canon (3(T())) and canong (Bw)) canony (B(r(w))) This cannot happen, as the addition of edges in Defimition 21 depends only on the images of the bags under canon.
w
G.3 Alternative r-WL
In this subsection, we define slightly modified versions of 1-WL and r-LWL that we consider in the subsequent sections.
Definition 24 (Alternative 1-WL and r-LW)). The alternative 1-WL test refines vertices' colors
(++) + HASH (
(v), (o),, {{
[uEV(C))))
Equivalently, we define the alternative r-LWL via
e (0)) {{ (at((t,,),, ( (+)1)()= + HASH,
{f ( (PMD)))N))))
{{ ( (p) ( (EN)())))
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- &- test and the standard k- WL test are equally powerful. For the sake of simplicity the subsequent discussion, we will refer 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, justified because the expressive power of these tests remains unaffected.
29

---

Finally, as noted in Section 6, we alter the r-LWL algorithm slightly by incorporating atomic types into the path representation. Hence, we update node features according to
(1) HASH, (2)(0) {{( at)((, |nEV(C))}.
(aap((e.)) |PENii)))
: {{ p). |PEA.(l)))
p).
where (atp(1,)) cf = ((atp((rr,))) (p1)))))))))))))))) ..... (atp(u. po+1), o0 (Pr-1)) for p =
{ E (v). The definition of atomic types atp(:.)) is given in Definition 13. Clearly this version of r-LWL is more powerful than the standard version, according to Definition However, is unclear whether r-LWL with atomic types is strictly more powerful than standard r-LWL.
G.4 The Unfolding Tree of r--WL
Given Definition 20, we assume, for the remainder of this appendix, that every fan cactus graph has unique labeling function, allowing us to select 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 critical concept known as bag isomorphism (Dell et al., 2018; B. Zhang et al., 2024).
Definition 25 (Bag Isomorphis)). Let (F, T*) be a rreemdecomposed graph, and be a graph. A homomorphism from F to G is called bag isomorphism from (F, (5) G if. for all t (T*),
the mapping f is an isomorphism from F F[3r- (t) to G[f (t)). We denote by BIso( (F.T", G") the set of all bag isomorphisms from (F, T8) to G, and set blso (F, T*), G) [Bsso
(F)))) G))
Moving forward, we proceed to define r-W unfolding trees, which intuitively construct, for a given graph and node in the graph, the computational graph of the r-LWL. algorithm and its canonical tree decomposition.
Definition 26 (Unfolding tree of r-EWL). Given a graph G. vertex U E (G) and a non-negative D E E, the depth-2D r-LWL unfolding tree of graph G E M node v. denoted as (F) (1D)), is a tree-decomposition (F,T*) constructed in the following way:
1. Initialization: VFF) = [u} without edges, and T only has a root node s with 3T (s)
{v}. Define a mapping VFF) V(G) as (V)) V.
2. Introduce nodes: For each leaf node t with | (t)
in T do the following procedure:
Let (1(() = [g). For each E V(G) do the following:
a) Add a fresh child tw to f. in T
b) Add a fresh vertex to F and extend with [f + w).
c) Define the bag of the by ST (tw) = Br- (t)
d) Add an edge between f and g if (x(f), (g)) E E(G).
3. Introduce paths: For each L,..., do: For each length path with canonical orientation p 18t E Nggg),, do the following:
a) Add fresh path tp = {t<pr by (prp Upsh Apob tppport b (ppt1) } to t in T
b) Add q + fresh vertices f1...., satz to and extend n with [ss + pt) for every i == I, I..... L.
30

---

(1)(1)
1.2
1.3
1.8"
1,2
8
1,8"
Figure 11: The depth-2 unfolding tree of graph vertex 1 for 2-EWL.
c) For i = 1,...,.. let the bag of (poppe1) be defined via 3T- (1pp.).e1)) - (1)
(Ji, J.
d) For == I,..., q 1, let the bag of (pr) be defined via BT (t(p:)) =
e) For i = lii==...., q 1, add edges between f: and fit1.
f) Add edges between 9 and f1..... J9t1 such that for every i i= 1,..., we have (tr tween and fi if and only if there is an edge between (o(9), (f.)) E E(G)).
F(
Plffifttu 9
ie., add edges be-
T 4. Forget nodes: If a leaf node T with [tr and parent if with (8T-(())
do the following:
a) Add a fresh child ti oft to T
b) Let f be that vertex introduced at t, that is, we have ST (t) Br (t') [f}.
c) We set 3r (t1) = {f).
5. Forget paths: If tp = (t
I. (pr pat (pat: .., (ppl P (pgest) is a leaf path
T T with parent l' of Kgr do the following:
a) For = 2....,q +++ 1, add a fresh child [(m)) to (p:))-
b) Let f2.... fa+t be the vertices introduced at tp. that is, we have BT (t(pa) 37 {fil-
For ......... we set BT (f(p)) (f.).
We refer to Figure 11 for the depth-2 2 2-LWL unfolding tree of an example graph.
For any graph G, any vertex V and any non-negative integer D. let (u)) (()) be depth-2D r-LWL unfolding tree at node v. Then, F(D)(v) fan r-cactus graph, and ((D) an r-canonical tree decomposition of ((D) Moreover the constructed mapping n in Definition 26 a bag isomorphism from (F(D) (v), ((D) to the graph G.
Theorem 4. Let
Proof. Clear by the definition of the depth-2D unfolding tree of r-WWL
We present the following results that fully characterize when two graphs and their respective nodes have the same r-LWL colors in terms their r-LLL unfolding trees.
Theorem Letr N. For any two connected graphs G, H, any vertices E V and x V
and any D E N. it holds: er (p) = of (P) ( if and only if there exists root preserving isomorphism
(x)
between (v), (())))))(())()))) and (x)
Proof "=" The proof is based on induction over D. When D the theorem obviously holds. Assume that the theorem holds for D < d, and consider D = d + 1. We show that if Cr (d+1) (v) e (x)), then there exists an isomorphism (p,7) from ((44))) to (F(++) ((dt)))))) such that p(u)
If or (1) = of (d+1) (d)))(z),, then
{((a w), w), Ie VEV(G)]] = -((=))))(((((=))))0000000 (oo)))leev(e wev(m)))
31

---

i... |V(G] = [V(H),, and we set n IV(G)). We enumerate V(G) = {wi..... w/ and
V(H) ..,..... 2n such that
(wx) = of (2:)
(8)
for all i = ,,....,,. n. Also, again since of (a+1) (v) = 6x ((+1)(x)) (xt). we have for every q = -=,...... .,
{[( atpp( un). o (uz)) (atp(u, Up+1), (d) (Mg+1)) {ui, Uy+1) = E NG (G)
=[(( ((atp(z,, (1), (v1))
[atp(z, Mo+ Mo+
1), ct) (yp+1) (y1,.... ". M. = E No
In partieular, [Vg(v)] = Ng(x)] and can enumerate the paths in Ny and (g(2)) such that (d)l (u (y?) and alp(e, uft alp(
for every -= I, (v).
Now, by definition of the r-LWI. unfolding tree, the graph (w)+))()) is isomorphic to the union of: a)
all graphs (w;, for = 1,... n. plus additional edges between wi to if [w;, v} E E(G), and b) all graphs F(4) (p%,,) for q = ...... r, (y).). And adding, for l = 1...... ......g q. edges between pÊ, and Pi, And adding, for l: = 1, .....99 -
1..... (N)(t)) for any path pÊ ={ př, -.. pl. 11
edges Pl, and if there is one in G, i.e. if {pi,.= o) E(G).
Similarly. the tree ((++1) (v) is isomorphic to the disjoint union of all trees ((d) (w;) (for 1..... and (p) (for q = i,...,r,, .r, k = ......g and / = .,..., [N()) Plus adding the following fresh tree nodes and edges: a root node s, nodes tw. (for i = 1,... n) that connects to s and the root I,..., (.G.)) for any path pp E (N) a path of length 2g.
r,, l of (T()) (ws). And for g = 1,....,,,
given by 'pp = (1t,)) (pl:-13)) "
(n "Mt.. (lot) '' "(rlott) H where s is attached to t {M
And finally, connecting the trees (vf,) at root node pi,e to b (mix)]
By (8) and induction, there exist isomorphisms (ps.T:) from (F;)) T(4) (wx)) to (P(d())) (z)), (x)) such that p:(wx) = 2, for i = L..... n. By (9) and induction, there exist isomor- phisms (0f,e The)) from (Fid) (ul,,) ", (Mf,,) to (F1 T(d) (vi,)) such (((u(,)) = vf, for 1,
11 1...., .2
and 1 = 1,..., (NG()))
We now construct p by merging all a and Pl. and construct T by merging all TV and Th We finally specify appropriate mapping for the tree root, its direct children and the paths attached to the tree root. Then, it is easy to see that (p, T) is well-defined and an isomorphism between (F(d+1)()) ((d+)())) and (x), ((d+))()))) such that p(v) = x.
Proof of "s" We now prove the other direction, again via induction over D. When D = the assertion obviously holds. Assume that the assertion holds for D S d. Now, assume that there exists an isomorphism (p,T) between (Fr(+1)(1) (v), (w)))(()) and (F(d+) (()+ such
that p(u) = x. We show that (d-1) (w) cr (d+11
We begin our proof by establishing the equality of two multisets: (f(c) (w), atp(e, w))lw ){ and (s) z))lz e v(H) of this equivalence closely mirrors the argument presented in the proof of B. Zhang et al. (2024, Lemma C.14). Since is isomorphism it maps all tree nodes 1(d+1) (v) of depth 2 with 1 element in their bag to the corresponding tree nodes in (x)+1) Let s 8, and t,. be the nodes in (1++ 1)) and (d++ 1) (z) of depth 2 with element in their bag, respectively. For i = 1..... let s/ and E the parents of s, and t,, respectively. We then choose the order such that the following holds for all i = 1,
The proof
1. Let ST (5)) = {u, w and (rea+s) = (2, ē.). Then, p(u) = x and p(ūū;) = Eo and thus, per assumption, (u, w.) e E(F(d+1) (v)) if and only if (x, 2, E ((F(d+t)(r)..
32

---

2. T is an isomorphism from the subtree rooted at in (v)+ i.., T D (v)[s:) the subtree rooted at & in (r)+ (v)
3. For all 8 E (es (8)),, it holds pl (( = (o
4. By the definition of the unfolding tree, P is an isomorphism from the induced subgraph (v)+ [r(++)(v)]ss]] and the induced subgraph (x)+)(()) (=)(])
By the last three items, we get that (F)++)() [u)ss] (v))s( and (F( (x)][] (x)ls) are isomorphic. By definition of the r-LWI. unfold- ing tree, (F) [T (v)ss) is isomorphic to (F( (w:), ((4) (w:)) for some E V(G) that satisfies {w), 2) E Ep(ti(()) if and only if {wg, o} E E(G). And isomorphic to (F(d) F(d) (2:)) for some 2;
(F) (x)(a] (x)(a)) V(H) that satisfies (2 E (x)) if and only if {zi,z) E F(G). Hence, by induction, we have atp (v, w;) atp (z, 2i) and ol (w)) of (2) for all = I.....n.
remains to show that, for every 8 ,....,r.
(l( atp(v, u1). df) (uz)
atp(( up+1), (d) (ug+1)) Hui,....,ut11" = E Ngg(o)} alp((2, Mo+ 1), (2 (wp+1) (2), ................................ Me+1 E [g
[1(
11 aapppl, v1), 4d) (v1)
Fix qg Since T is an isomorphism it maps all paths of length q in (v) connected to e to paths of length 9 in ((d-1) (z) connected to r.
By construction of the r-L unfolding tree and since (p, r) is an isomorphism, it holds (Ng(r) (2)). Denote the relevant bags depth by s for l = (...,,,,(())) and .,...,,000 , 1. 1q Denote by of, and fl the parents of $1,K and t respectively. We then choose the order I = 1. (N)] and k = =,..... 1.....9t such that it holds
1. Let Braan ($1 (u, Wff } and B 3r (t(h)) = =sz, 21x) Then, p(w)(k) 29, and thus, per assumption, { v, wif, j E E(F(+1((e)) if and only if { 1, E E E(F(++))
2. 7 is an isomorphism from the subtree rooted at oi, in T(d+1) (v), i.e., (w) the subtree rooted at G, (x)+ i.e., 7(d+1) (x)14,)))
3. For all s E (esc (s ). it holds p( (s)) = Br (T(s))
4. By the definition of the unfolding tree, is an isomorphism from the induced subgraph (1) (T(++(())ss) and the induced subgraph (x) [x)+t)
By the last three items, we get that (pl)tt)() (w)(t) (1) and
(z)) ( (()( are isomorphic. By definition of the r-LWI unfold- ing tree, (p) (rrat) ((d+)) is isomorphic to (Li(4) (w))), (, (wf,))
for wi, V(G) that satisfies ( w) (pp if and only if { (w F(G)..
And (x)
[TiC+1 (x)
T ((dt)) is isomorphic to (F(d)) (=i,N); (()))) (=I,)) for
=i, V(G) that satisfies { ( v E((((+1(()) if and only if { u) E(G). Hence, by induction, we have of (1( = oit (=(,e) for all indices. By Item 1, we then have c:a0 (w/))
(i (z1)) and atp(v, w/) atp(v, 2,) for every I,..., and ( = L,, (WG()).
33

---

We introduce the following definition that provides similarity measure between graph and tree-decomposed graph.
Definition 27. Civen graph G and rre-ddecomposed graph (F.T*), define
cnt ((F.T"), { s.t. (F(D) (v), = (F
where (o) is the depth-2D 2D r-LWL unfolding tree o at v.
The counting function cnt ((F, T,) G) serves as a key metric, allowing us to draw connections between r-LWL colorings of two different graphs.
Corollary Let E N. Let G and H be two graphs. Then, GG( (H(H) if and only if ent ((F, )), G) cnt ((F, T"), H) holds for all graphs (F,T)) E M
Proof of " Let e, (G) = e, (H), {()((v) u {
Assume, by contradiction, that there exists a tuple (F,T*) E M such that ent ((F, G) + ent ((F, "), H). Let cl.....Ck be the final colors of nodes in V(G) and V(H). Then, define for i I....,k
{ V(G))c(()) c, and 3D E s.t. (p), = (F.T9)
ent
We have
ent () Σ (F.TT),
and
ent ((F,T", H) = Σ ent ((F,T*), H [c]).
Since ent (), + cut ((F,7", H). there exist an index = 1..... & such that ent ((F, G[c])) ent ((F,"", 11 [c:]).
(10)
Furthermore, there exists in E N such that there are exactly n nodes u vi,..., Un and ai.... such that
(v1) =... o (vi,.) and er (x1) =... =G((i, =c.
Hence, as e, refines or (D) we have
( (u1) =
By (10), there exists some E such that (without loss of generality) (o1))
(F, T"). Then, by Theorem 5, we have
(F(P) ((P) = ..... (v,,) (vt.)) = (TD),, _... (FID) (x1). (T()) (m1)).
There does not exist any other node with (ww) = ci such that the corresponding unfolding tree is isomorphic to (F(D) (v1), (1z)). Hence, contradiction.
Gic.)) (FF.(FTT). H(c;)), which is
Proof of Suppose that cnt((F,TT),, C1,..., Cko with multiplicities mi...., Mag and čI,..., Ct,, with multiplicities mi.... fika be the final colors of r-LWL, applied to G and H. respectively. Consider some u E V(G)
cnt(( H) for (F,T*) Mr+2 Let
such that (v(U) Ci. Let D be sufficiently large (any D after convergence of r-LWL), then (FL((F(D)()) (v). (w)). = cnt((F(D)(v)) (v)), H) since (F(P)(v), (()) E Mr+2 Hence, without loss of generality, e₁ = and my my. Repeating this argument for all colors finishes the proof.
34

---

G.4.1 Proof of Theorem 2
In this section, we employ techniques adapted from the works of Dell et al. (2018) and B. Zhang et al. (2024) to derive proof for Theorem from the established result in Corollary
Definition 28 (Definition 20 (Dell et al., 2018)). Let (F, and (F, T*) be two tree-decomposed graphs. A pair of mappings (p. r) is said to be bag isomorphism homomorphism from (F, T*) to (F,T*) ) if satisfies the following conditions
1. p is a homomorphism from F to F.
2. is homomorphism from T to T
T under contains vertices at every depth present 3. T is depth-surjecttve, i.e., the image Tf in T
4. For all t' ET, we have depr. (t') = depp-(((t")) and F(BT((1)) (T (1))
5. For all t' E T", the set equality p(3re(t')) (q. (T((') holds.
6. The depth T and To is equal.
We denote the set of bag isomorphism homomorphisms from (F,T*) to (F,1") by BlsoHom ((F,T),, BIsoHHmm (F,TT),
and set blsoHom (IF,T),, =
We continue with the following lemma that shows a linear relation between the number of bag isomorphisms and the output of the counting function Definition 27.
Lemma 6. Let E N. For any tree-decomposed graph (F,T*) E M2+ and any graph G, it holds
blso ((FTT),G))
Σ (P:7))MM+
bTsoHom (F,,T%, (F:T*)) ent ((F:T))
(11)
Proof. Let (F,T*) be a tree-decomposed graph such that 7 has depth 2D. The sum is over all isomorphism types (fr, T of tree-decomposed graphs. This sum is finite and thus well-defined as blsoHom (F,T (F:T*) 0 holds if I has depth unequal to 2D or nodes with at least 11) ((V(G)) 1) children.
Assume that for the root bag of (F,T)) it holds (s) {u). Let E V(G) be any vertex in G, and denote by (F(P)x)) ((P) the depth-2D r-LWL-unfolding at node æ. Define the following two sets,
S1(x) = {h E Blso(( h(v) = =x} S2(2) = ((1.T) E BlsoHom (IFTT", ( (t), p(u) =]]
We prove that [x)] [82(z) for every a E VG),, which is equivalent to (11). For this, we show for any bag isomorphism h from (F, T*) G with h(v)) = x, there exists unique bag isomrrphism homomorphism a from (F, T*) ( to (F(D) (x), (z), (z)) with (v)) x such that
a, where is the bag isomorphism from (F(D) (I), (()) to G. defined in Definition 26 and Theorem respectively. To visualize this proof idea, see Figure 12.
First, define p(v) Let 01,..., Un V(F) be nodes that correspond to bags in T of depth 2 with one element inside the bag and their parents having two elements in their bag, i.e., {wy] are the corresponding bags. Similarly, set .1...., Fm E V(F(D) (x)) nodes that correspond to bags of depth 2 in (x)) with one element inside the bag and their parents having two elements in their bag. Since h is bag isomorphism and well, for every = 1,..., there exists j: such that h(())) J = TTr,)). ). where ū5 E V(G) and Jy E V (z)). Since a and h are bag isomorphisms, we have
Fllle, Gl 2
(12)
35

---

Now, set p(e;)) = 23, for every i = I.....n. n. Based on (12). we can easily define T such that satisfies Definition 28 with respect to bags that are of depth and 2.
For q 1,,.....? r and / = l...= (. (v)] let pf be a path of length 2q starting from the root node s in T Every such path př in T corresponds unique path vy. that is in (x), of length g in F.
We represent the path by ff ff22 ................................ " 10,+1 f
}. where every consecutive node is connected each
1. we have { {u, of E E(F) iff h((w), E E(G) as h is a bag
other and for k= I..... q isomorphism. Further for every node h ,,...9 there exists a fi such that h( = $zp.a
(IxH)) ). where Zz E EVGG), 2,,, ................................ Ss j E (2) and "g,,.. ,3 52
E (N) We
set a (v) = 33, for every k- = =1, ...... .9+ 1. Clearly, we have
F Fiee Us 1 = G [[(,,ūz; -5 = (x)) [[ ( 2n []]]
(13)
Now, based on (13), we can easily define such that T satisfies Definition 28 with respect to bags that correspond to paths in (v) for q = I. r. Now, following this construction recursively leads to a bag isomorphism P such that
π o p.
It remains to show that (p. T) is unique (up to isomorphism). For this, let (pi, Ti) be another bag isomorphism homomorphism between (F, T and (F(P)()) ((D))) such that pi (v) = x and h o P1- We show that p P1.
We begin by showing that p(v) = (v) for every v that is not in a cycle. Adopting the previous
notations, consider .i..... Un E (F) and æi,...,, Im E (z)() For each i = 1,..., n, let k; and I; be the indices such that p(v:) Us; and (1 Ii.,- Consequently, x (Ix,,) = . (1 ). We note that the image of ((,))) not contained in a cycle isomorphism. Similarly, Tk, and Tı, are not contained in 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 cycle. Hence, Zk. -t,,
G, as otherwise, h would not be a bag
We continue by showing that for every w E (F), that contained a cycle, we have p(w) = P1 (w). This follows a similar argument as the nodes that are not included in any cycle. We summarize the argument shortly: must hold that p(w) and pi (w) are contained in a cycle, and r(((w)) and T (pi (w)) as well. Now, π is injective if the domain is restricted to nodes that are only contained in cycles. Hence, P1 = p.
We continue this subsection by introducing the concept of a bag extension in the context of tree- decomposed graphs. This definition formalizes the notion of one recompoo graph being an extension of another.
Definition 29 (Definition 20 in (Dell et al., 2018)). Let (F, Tt) be a decompecoppoeed graph. A bag extension of (F. T') is a graph T*) with V(H) = V(F) such that for every t E V (T") the induced subgraph 11 (3r (t) is an extension of FlBT (T)), i.e if E E (F(3T. then E E (H( We define bExt (IF."), as the number of bag extensions of (F,T*)
that are isomorphic to (F,T*).
Intuitively, bag extension of a decoopcoppo graph (F, T*) can be achieved by adding an arbitrary number of edges to F. Each added edge must be contained within a bag that corresponds to node in the tree T
Definition 30 (Definition C.28 in (B. Zhang et al., 2024)). Given a tree-decomposed graph (F, T") and a graph G. bag-strong homomorphism from (F,T*) to G is a homomorphism f from F to G such that, for all t E (IT)). ff is a strong homomorphism from Fl (t)) to G (t))), i.e. {u, v} E (F13T- [t)) iff (f)), f(w)) E (
Denote BStrHomm(F* (F,T"), G) to be the set of all bag-strong homomorphisms from (F, (" to G. and denote bStrHom (F,T") [BStrHom( ((F (FF,T*)G) G)L.
We continue with decomposing the number of homomorphism from a fan cactus graph to any graph.
Lemma 7. Let r E N. For any tree-decomposed graph (*) E M2+ and any graph G, it holds
hom (F.G)= Σ (MM1)
bExt (F. (F (F.T*)) bStrHom (F.T*).G)
(14)
36

---

F
n
G
Figure 12: Visualization of proof idea of Lemma 6
Proof. The proof follows the lines of Lemma C.29. in (B. Zhang et al., 2024). First, (14) is well-defined T is finite, hence, there can only be finitely many bag extensions of (F,T").
Further, consider the set
| (F.T*) M (p, BExt (IFTT)) (F.T+) $ = (((F..T)
E BstrHom ( (F. G)}
We consider the mapping from S to hom(F, G) via ((p,7) 7) .g) + -gopp We show that for every homomorphism h there exists unique, up to automorphisms, (F, TM Mr+ (p,T) and g such that / = g p.
We begin with the existence part. For hommF, G), define (F:T*) MM+ (p,T) and g as follows.
We define F by adding the edges given by
{u u V(F), T s.t. {u (t), (M(1), A(0)) E(G)). (15)
37

---

We define 7 := T Clearly, (F:T*) MM+ and it is bag extension as only edges are added that are contained within a bag that corresponds to a node in T
We define and 7 as the identity mappings on their respective domain, leading to (p, 7) E BExt ((F,T*) [ )-
We define g = For x E T we show that g a strong homomorphism from F1 (x)] to Gig (8p. (z))). Let {u,
(1)) then g())) E (Glg (5yz (z)))) as is homomorphism with respect to the edges E(F) and in (15) only edge {u, 2} were added that satisfy {h(u), h(w)) E E(G). On the other hand
E E (Glg (3x(())))
but {u, o) & E [ (x)) would contradict (15) as u, u are contained in the same bag B (z)) Hence, g BstrHom ((F.T)).G)
We finally prove the uniqueness part, i.e., that a (FFi. TY1), (01, ())9)) = h implies that there exists an isomorphism (p,5) from (F) to (F.T*) such that рo p. Po =. We first prove that Fi = F and T/ = Tt.
1. For any u, V(F), we obviously have p(u) = p(u) iff = p1()) (u)= = pi()) as and Pi are injective mappings.
2. Let V(F). Consider p())) E E(Fi),
we show that {p(u), p(v)} E(F).
If vu, E E(F), then clearly {p(u). p(u)) E E(F) as p a homomorphism. Hence, assume that {u, v) & E(F). Then, u, e must be contained in the same bag of T as is bag extension and only node pairs are added if they are in the same bag. Hence, p(u) and p(v) are contained in the same bag. As 91 is a homomopphism, we have (91 (91(p1 (u)), @1 (p (v))) E EG)) But, then also (g((w)), (((()))) E E(G), and as g is a strong homomorphism (with respect to the bag in which p(u) and p(v) are contained), we have ((v)) B(F). By symmetry of the argument, we have (u)( (v)) E E(Fi) iff (p(u), E E(F).
3. Since #I and p are bag extension, they are bijective on their respective domain. Hence, I p= ==po o PT defines an isomrrphism from Fi to F. On the other hand, Th = f trivially holds, again with F = TOT
We have 7o PI = 7. =. We show that the tuple (ő, F) is an isomorphism, i.e., it remains to show that for any 6 E T we have p(373 (b)) = B7. (F(b). Since is surjective, we can choose such that Ti (a) = b. Then.
7(3g5 (a))) = (Br- (a))) p(Br (a)) = (T(a)) = 3 (f (
The first and third equalities hold since (p1, 72) and (p. T) are bag extensions.
Definition 31 (Definition 30 in (B. Zhang et al., 2024)). Given two tree-decomposed graphs (F,T*) and ).) a homomorphism (p. T) from (F,T") T*) to F.T") is called bag-strong surjective if p is a bag-strong homomorphism from (F, T)) to F. and is surjective on both vertices and edges, and T is an isomorphism from T to I such that for all x E V(T"), we have p(3r- (x)) = (T())), to be the set of all bag-strong subjective homomorphisms from (F, (", to F,, and denote bStrSurj( T*), (F, T)) [BStrSurj(FF,TT (F) T.
Denote (StrSurj((E,TT)) (F,
Lemma 8. Let E N. For any decomooop graph (F, T*) E M*+ and any graph G, it holds
blso (( (F, .G)
bStrHom ())
bStrSurj (IF,T"), (F, )+) (F:T+)EM+
Σ
aut (,T
(16)
where out(F,TT) counts the number of automorphisms of (F, F
38

---

Proof. The proof follows the lines of Lemma C.31. in (B. Zhang et al., 2024).
Consider the set
S s ((((((T))
(F:T*) E M e BStrSurj (IF,T%) (F,T*)
g E Blso
)
We consider the mapping o from S to BStrHom ((F,T)) G) via (9) + goo p. We show that for every bag-strong homomorphism h there exists a unique, up to automorphisms, (F.T)) E MM+2
bag-strong surjective homomorphism (p, and g such that = g
We begin with the existence part. For h E BStrHlom ((F,7*) G), we define (F.T) E
M (p, and g as follows.
We define F by defining an equívalence relation ~ on V(F): u h(u) h(v) and there exists a path P in T with endpoints 4, l2 E V(T*) such that u E (4), E 3r (12). and all nodes t on the path P satisfies that h(u)= = h(t) (t)r We then define p the quotient map with respect to ~ and set F F/ ~ ie..
v(F) {p(u) u (VF)), = ((p(u), {u, E E(F))
which is well-defined as (u, v) E E(F) imples p(u) F p(v) since h is a homomorphism. Then, p is surjective per construction.
We define the mapping g VV()) - V(G) such that g(((u)) = h(w) for all u E (FF). This mapping g is well-defined since p(u) = p(u) implies h(u) = h(v), and p (FF) - V is surjective. This leads to the equality h = go p. To demonstrate that g is a homomorphism, consider any edge (xr, E(F). There exists an edge (u.v) E(F) such that p(u) x and p(v) y. which implies (M(w),(u)) E F[G)), since h is a homomorphism. Consequently, this means (g()).9()) E E(G).
We continue by defining the tree T = (V(T), E(T), Sp.) We set t = s, and define 7 to be the identity. Furthermore, we have (x)
((31(22) for all E V(T). It remains to prove that (F, T') E M is a valid tree decomposition. For this, it suffices to prove that for any vertex I E V(²) the subgraph By. is connected. For this, let x E (f) and 42 E B (x). Then, there exists E (4)),, u E BT= (12) such that p(u) x. p(v) = Therefore, u v. As such, there exists a path P E T such that all nodes on satisfy h(u) E h(3r-(b)) Hence, for every b E P there exists some wa 3r- such that h(w)) = h(u), and consequently wh ~ Finally, p(u)= = p(wb) E p(3r (b)) = ())()) for all b in the path P. Hence, (F.T*) MM42
It remains to prove that p is a bag-strong surjective homomorphism and g is bag isomorphism. We begin by showing that is a bag-strong surjective homomorphism. For this, let L E V(T*) and u, E (t). If {u,e) & E(F). then (h(u), & E(G) (since h is bag-strong homomorphism). Therefore, ((()),p(u)) & E(F) since g is a homomorphism. Hence, p is a bag-strong surjective homomorphism.
We show that g is a bag isomorphism. Let a E VT*),, and consider ū, E (x). Since is surjective, there exist u, E (2r) such that p(u) ū and p(v) = We have (o(u),((v) & EFF) iff {h(u), h(v)) & E(G), since both p and are bag-strong homomorphisms, Therefore, g a bag isomorphism.
We finally prove that (1F1, (pI, (pI.T))91) - ( (p. implies there exists an isomorphism (p,7) from T+t) to (F,T") TT) such that po PI = =. TT = T, T, = g p. Let h 91 o P1 = g p. We will only show that F; x F since the remaining procedure is almost the same as previous proofs. suffices to prove that, for all u, u.v. E V(F), (u() = pi (v) iff
a) h(u)= = 110)), and
b) There exists a path P T with endpoints 4, /2 E VTT) such that u E (r- v 3T (tz), and all node path P satisfies that h(u)) h(3r=(x))
39

---

We begin by showing the first direction, i.., (i( P1 (v) implies Items a) and b). If pr = pi().
we clearly have h(u) h(v) as 9i is well-defined. Also, there exists 21 E Br (u), E (v)
i.e., E AT (x1) and v E Br (12). Hence, p(u) E ((3r=(x1) C Aqp (m(()) and p1(w) = pi(u) E (i (x2)) C Bpge (Ti (I2)) since Ti) is homomorphism. Hence, ni (Ti), (x2) E
Byp (pI(u)) Since Tft [By, (pi (u)) is connected, there is path P in T (Bp (p (u)) with endpoints Ti (21), TI (222 such that all nodes on P satisfies pi(u) E Bap (2) = Sgpi (TOT (2))
Pi (T- We conclude h(u)= = (p)()) E (1
(( (z))).
(v) if Items a) and b). We prove this by contradiction, i.c., assume (u) * pı (v) but the above items (a) and (b) hold. We consider two cases.First, assume that u and are in the same bag of T'. Then, as (11,T)) TI) is homomorphism, the nodes Pi (u) and Pi (u) are in the same bag of T Since 91 is a bag isomorphism, have 9i (pi (u)) # 9i (Pi (u)). This contradicts Item (a) above.
We continue by showing the second direction, i.., Pı(u)
Now, consider the second case. For this, assume that u and are not in the same bag of T Then, there exist two adjacent nodes æ1, 22 on path P such that u E (21( u & have (T- C. Br= (z1) as for every pair of nodes f to in canonical tree decomposition with (t1, E =((T)) we have either 3T- (f1) C 3T (t2) or BT (f2) C (t). Now, item (b) implies that there exists w (x22 such that w * and h(w) h(u). Then, Pi (w) E Pr (3r (22)) C PI (x1) C 3pn (f1(z1) Therefore, (u) and p1(w) are two different nodes in 874 (T1( with 91 (p (u)) = h()) h(w) 9n (pr (w)). This contradicts the condition that 91 is bag isomorphism. This yields the desired result that F = F..
(22). We
Finally, we restate Theorem 2, with its proof now being a straightforward corollary of the preceding results in this section.
Theorem 2. Let r 2 O. Then, r-LWL can homomorphismn-cout M
Proof. According to Corollary 3, if (G) (H,)), then Cnt(F, = cnt(F, H) for every F
M Utilizing Lemma 6, we extend this result to bag isomorphism counts: blso F, G) blso F, H) holds for every F M Finally, invoking Lemma 7 and Lemma 8, we conclude that hom F, G) (FmmF, H) for all F E E
H Implications of Theorem 2
In this section, we discuss important implications of Theorem 2 and provide proofs for the results in Corollary 2.
H.1 Appendix on F-Hom-GNNs and Proof of Corollary 2 i)
Recent work in the domain of MPNNs has explored enhancing the initial node features by incorporat- ing homomorphism counts (Barceló et al., 2021). We summarize this approach in this section and compare it to our r-LLL algorithm.
Define F = [Pf, .... ... Pf] as collection of rooted graphs, termed as patterns. In J---o---PPaa MPNNs. the initial feature vector of vertex a graph G combines a one-hot encoding of the label Xa (v) with homomorphism counts corresponding to each pattern in F. The feature vector for each vertex is recursively defined over rounds of message passing as follows:
FFG,,v = (xo(v), hom(pf G")... hom( G"))
(0)
(17)
F.G. = ((+11)
((+1)
(x (1)
(x p(++2) p(+1))
10) (x
lue lue Na(v)))
Here, ( and f()) represent the update and aggregation functions at depth t, respectively.
40

---

H.1.1 Expressivity of J-Hom-MPNNS
In this section, we summarize known results about the expressivity of F-Hom-MPNNS. The main result from Barceló et al., 2021 can be summarized as follows.
Theorem 6. For any two graphs and H, holds J-Hom-MPNNN can separate and H if and only if homm(, G) = hom H), for every F-pattern tree.
To understand the above theorem, we need to define the concept of F-pattern trees. For this, we define the graph join operator
follows. Given two rooted graphs G and H the join graph (G * H)" obtained by taking the disjoint union of G and H", followed by identifying w with v. The root of the join graph is Further, if G' is graph and Pr is rooted graph, then joining vertex v in with P results in the disjoint union of and Pr, where r identified with v.
An F-pattern tree T is constructed from standard rooted tree S (V, E, x), which serves as the core structure, or the "backbone", of 7". To form T", each vertex & E V of the backbone may be joined to any number of duplicates of any patterns from F. Conceptually, an F-pattern tree a tree graph enhanced by attaching multiple instances of any pattern from F to the nodes of the backbone tree. However, it is important to note that additional patterns may not be attached to any node that already derives from pattern in F. Our method can homonorphism-coum graphs where this is allowed, see Appendix H.1.2.
Let F (Pi...., Pt).
Examples of F-pattern trees for F { are
where grey vertices are part of the backbones of the F-pattern trees, black vertices are the joined node and white vertices are part of the attached patterns. We define the set of F-pattern trees by J=
H.1.2 Comparison with r-L
We compare our proposed r-GGIN against FT--HomMPNNN where F== = ........ Cr+2} consists of cycle graphs up to length r + 2. Both MPNN variants exhibit equivalent preprocessing complexity. However, after the initial layer, the computational complexity of our method is marginally higher, yet it increases linearly with the number of cycles present in the underlying graph.
According to Theorem 2, our method r-IGIN can homomorphism-comm all fan (r 2)-cactus graphs. In particular, r-EGIN can homomorphism-come all F -r-pattem trees. For example, there are infinitely many fan r-cactus graphs that cannot be represented as FP" -paatterrn trees, e.g., for r
We restate Corollary ii) and give short proof.
Corollary 4. Let r N \ {0). Then, r-LWL is more powerful than F-Hom-MPNNN where F= == (C3,...,Cr42.!
Proof. The proof of Corollary 2 can be stated summary of all finding of the previous subsection: By Theorem 2, we have r- r-LWL C hom(M*+2 -). By Theorem 6, we have F-Hom-MPNNY
C hom((")) and hom (FD) C J-Hom-MPNNs. Clearly, FIrr C M Hence, r--WL
[ hoo( M222, E hom FT)
Hence, r-LWL is more powerful than F-Hom-MPNNs.
Li
H.2 Appendix on Subgraph GNNs and Proof of Corollary ii)
Subgraph GNNs treat a graph as a collection of graphs (G" | w E N(v)), where G is a graph obtained by marking the corresponding node u. For every graph G it runs an independent WL-
41

---

algorithm, i.e.,
Sub,ar (v) (xa(v); (v=(
(U)
(18)
1++1) Sub,Gr (v) = g(t+t)
Gu (v), f((+1)
(x (ub..o w E No(w)))
Here, gl and f(() represent the update and aggregation functions at depth i, respectively. The final node representations after rounds are then calculated by
L Suub. (u)) h Sub G- (v) U EV())
H.2.1 Expressivity of Subgraph GNNs and Comparison with r-LWL
The expressivity of subgraph GNNs fully characterized by the class
Jsub == {F Eu E (FF) s.t. F \ {u} is a forest].
ie., Subgraph GNNs can separate pair of graphs G, H if and only if hom(Feub, G) * hom(J H). Furthermore, the Jrub the maximal that satisfies this property (B. Zhang et al., 2024, Theorem 3.4). We restate Corollary 2 ii) and provide a proof.
Corollary 5. 1-tWL is not less powerful than Subgraph GNNs. In particular, any r-LWL can separate infinitely many graphs that Subgraph GNNs fail to distinguish.
Proof. We show that already 1-LWL can separate infinitely many graphs that Subgraph GNNs fail to distinguish. The other statements then follow as a simple corollary of Proposition
For clarity, we begin by demonstrating that there exists pair of graphs that 1-EGIN can separate, but Subgraph GNNs cannot distinguish. Consider the graph F defined as follows: F { [o-o{]]
holds that F E _M3 FFsu,, where Frab is the maximal set that Subgraph GNNs can homomorphism- count. Then, by (B. Zhang et al., 2024, Theorem 3.4), there exists pair of graphs G(F) and
H(F) such that hom(F, G(F)) * (Fom H(F)) and hom[FFub, G(F)) = hom[[Fub, (F))). Hence, Subgraph GNNs cannot separate G(F) and (FF). Since M3, by hom G(F)) #
hom(H FF H (F)) and Theorem 2, 1-tWL can separate G(F) and (FF).
This argument can be repeated for every E M3 AFaub, Since there are infinitely many graphs in M Jsub the corollary follows.
We mention that the construction of the pair of graphs G(F) and H(F) in the previous proof is based on (twisted) Fürer graphs and largely motivated by the constructions by Fürer (2001) and B. Zhang et al. (2024). More precisely, we can define G(F)) as the Fürer graph of F and (FF) the corresponding twisted Fürer graph. See Figure 7c for visualization of F, G(F),, and (FF).
H.3 Appendix Subgraph k:-NNNs and Proof of Corollary 2 fii)
Qian et al. (2022) introduced a higher-order version of Subgraph GNNs that compute representations for subgraphs made of tuples of nodes. Specifically, Subgraph k-GNNs referred vertex- subgraph A--OANs in the original work (Qian et al., 2022) - treat a graph as a collection of graphs {G" VGG)*), where G" a graph obtained by marking the corresponding nodes u. For every graph G" it runs an independent WL-algorithm, i.c.,
Su (v) (xo(v), atp(u), lu=u, ........ (v)) (t+1) Sub(k), (v) ((+11)
(0)
(19)
(t) (x (ub(()) ((+))
(x)) (xbbbt)) (w) w e No(v)))
Here, (9) and f(() represent the update and aggregation functions at depth respectively. For every k-tuple u, the final representations after t rounds are then calculated by
(x Su B l V()).
The final graph representation is then given by
Sub(R) (G) = j (ub()) u V())*)
The ceannoophhss-exppesssiiii of these GNNs is characterized as follows:
42

---

Theorem 7 (B. Zhang et al., 2024). The domoomrphism--epprssii of Subgraph k-GNN is given by jzab(k) = {F=: 30 C. VF s.t. |U| S k and F U is forest }.
Since the set FFub(k) is the maximal set of graphs that Subgraph k- k-GNNs can homomorphism-coun, we can derive the following corollary, which restates Corollary 2 iii) and provides a proof.
Corollary 6. For any k 2 1-EWL is not less powerful than Subgraph k-GNNs. In particular, any r-EWL 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 2 I. We will show that there exists 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 edge a single node.
It holds that F E M F=su((k), where F.ub((k) is the maximal set that Subgraph k-GNNs can homomorphism-count Then, by (B. Zhang et al., 2024, Theorem 3.8), there exists pair of graphs G(F) and (F)) such that hom(F, G(F)) A hom(F, ((F)) and hom(FFsu(()) G(F)) (ssb)))b(k) H(F)). Hence, Subgraph k-GNNs cannot separate G(F) and HFF). Since F E M', by hom F, G(F)) & hom F, (F)) and Theorem 2, 1-CWL can separate G(F) and H(F).
This argument can be repeated for every F E M \ F=mu((k), Since there are infinitely many non-isomorphic graphs in M jrau((k), the corollary follows.
H.4 Proof of Corollary iv)
Proof of Corollary 2 iv). Given graphs F and G, it is well-known (see, e.g., (Neuen, 2024; Curtica- pean et al., 2017)) that sub(F, F, G) can be decomposed as:
Sub(F,G)=
E
a(F")hom( (F'
(20)
F'Espasm(F)/~
Here, the sum ranges over all non- non-isomorphic graphs in spasm (F). The sum in (20) is finite since the homomorphic image of F has at most (F) nodes. Per assumption, we have spasm(() C -M*+2 ie.. by Theorem r-LWL can homomorphism-ccunt (pasm(F). In particular, if r-LWL cannot separate two graphs G and H, we have hom(spasm(F) (F), G) = hom(spasm( (F), H), and hence, sub(F, F, G) = sub(F. H).
The result on subgraph-counting paths follows directly as the homomorphic image of path Pr+3 of length r + lies in M
I Appendix for Section
Theorem 3. For fixed r 0, iterationn of r-LWL are more powerful than r-MMPNN with t layers. Conversely, r-LMPNN is more powerful than r-LWL if the functions f(0,g(() in (3) are injective.
Proof of Theorem 3. We begin by proving that & fixed 2 0.
E h We argue by induction over for any
Initially, (0) 16p both labeling functions start with the same base labels. Now assume
((+1) Cr ((+))()) for some u, E V(G.. By definition.
HASH (1), {f
(P) (p) T No(u
HASH (40) (p) (PPD)
This implies of (u) (c) and
{1 (e) [(<W))/NNN))) Ak (0. (O.....r),
as HASH is an injective function.
43

---

By induction hypothesis, we hence have 11, (u) (
(v) and
{ (D)
{{ (p) Na(t)) A4 E (o.....
which implies that any function, in particular f((+1) and g(++1) have to return the same result. Therefore, have bf b(++1) (w) (v).
We proceed to prove hr _ or if all message, update, and readout functions are injective in Definition 9. For this, show that for each 0 there exists an injective function such that 1, Φ o of For /. = O, we can choose Φ to be the identity function. Assume that for / there exists an injective function ø such that h ( (v) doc or (v). Then, we can write
(v) = g (1)
hh (t- (v). m (v), ..., mf (()(
= g ④ cf (v),
(1) (v), 2 (o)....,.mm.. (. (v))
where for every = .,. we set Φ o my (v) = {f(0 1f 11"1) (p)) |p NGG()))) and (o Cf ( (p)) = (Ø o or 1 (p.),.... o of (p++1)) for p= = {pr 19t1 (N))). By assumption, all message, update, and readout functions injective in Definition 9. Since the concatenation of injective functions is injective, there exists an injective function &o such that
( + (C-1((),,
(p) (pENNN)))
(p) (p
{{ (--)(()) lelll DeMW))))
As HASH in Definition is injective, the inverse HASH-1 exists and is also injective. Hence,
A (v) = 1b o HASH HASH (o)) {{ { (p) Ipe e No(u))
{{ (d NEN(
{ (c) (eN((o))))
1b o HASH
(v))
Choosing Φ = v HASH
finishes the proof.
We conclude this section with the following lemma that justifies our architectural choice in (4).
Lemma 9. Let x Q.. Then there exist E H such that
((x)
EKTT
(21)
is an injective function.
Proof. We prove this claim by induction. For r = 0, any x * R fulfills the claim. Now, let
E I²" such that vpxx) Q" - 1R is injective. The set QUei...., -E Ex24 x Q") is
44

---

countable and hence a proper subset of R. It follows that there exists Ey+1 E R with E,-1 $ Q(a.. Note that 0 Q and hence E # We now prove our claim by contradiction.
Ex=0 Exat We distinguish two cases: Assume there exist x' ++ with Ek= EaTA Σ
I; = x for all S r and 1r+1 # 2/41: Then immediately
Ir+1 * x4yt1
1r+12r-1 # 1r-12
Ek + 1r+18 #
Ex + E4414/41
k=0
k=
r+l
r+l
Σ
TR +
Σ
EKTK
K=U
k=U
Exzo ENIT # Ek=o sxats: But then
Ex + Er412r41 = Σ
Exah + E4414
K=U
k=
Σ
Saah =6+1(14441 - Trt1)
k=0
The left hand side is an element of Q(,i,...,&r) However, 8,41 (5/+1 xr+1) & Cls er] by choice of Ey+1, leading contradiction.
45

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We mention main results in the abstract and introduction (see Section 1), and provide proofs for all claims (see Appendix ff.) and code for all experiments (see our GitHub repository). We clearly state the scope of our theoretical results and emphasize that our method provides an expressive architecture suitable for sparse real-world graphs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We describe the computational complexity of our method in separate para- graph (see Section 6). We specifically address its preprocessing complexity dense graphs a separate paragraph (see Section 7). We also mention important future work that would complement our theoretical contributions in the conclusion section (see Section 8).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
46

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems are numbered, and we refer to the formal proof' in the appendix (see Appendix ff.).
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All hyperparameters, hyperparameter ranges, and used resources are given in Appendix Our GitHub repository provides instructions on how to reproduce all experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
47

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All hyperparameters, hyperparameter ranges, and used resources given in the appendix (see Appendix C). Our GitHub repository contains instructions to reproduce all experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
httppsccccpppccccceeeeeeeeessece htt///uudds///ee/ee //e///Cooommsseeeeeee www.iisssooopiiooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Data splits, hyperparameters, hyperparameter grids (if used), optimizer, etc. are detailed in the main paper (see Section 7) and appendix (see Appendix C), with additional instructions provided in the anonymous GitHub link (see our GitHub repository).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
48

---

Justification: We report error bars and confidence intervals for our experimental results (see Section 7), capturing the variabilityy due different random seeds and initialization. Detailed information about statistical significance tests is provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative етror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All information the compute resources is given in the appendix (see Appendix C). For the real-world experiments, we provide run times, and for the synthetic experiments, the run times are negligible.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurips hctpp//cccccpcccccceeeettaaa
Answer: [Yes]
Justification:
We respect the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
49

---

10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: While our work has numerous potential societal consequences, none which feel must be explicitly emphasized here, its impact lies in providing theoretical foundation for improved graph representation learning methodologies.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not release data models with high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All used assets properly cited, and the licenses mentioned.
50

---

Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license ge.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswith thode.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce new assets in the form code. All details about training, datasets, and models given in the submitted paper and/or in GitHub repository, including detailed instructions to run the code. The license is provided under the MIT license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
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.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
51

---

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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing 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 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 the institution conducting the review.
52


Reviews:
[{"review_id": "Y9SAt5EC2L", "reviewer": "Reviewer_pJ5G", "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.", "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": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Strong theoretic results with concrete proof.\n2. The algorithm is local with good expressivity.", "weaknesses": "1. More datasets [1, 2] can be included to evaluate expressivity, especially long range expressivity. \n\n\n[1] Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, Dominique Beaini: Long Range Graph Benchmark. NeurIPS 2022.\n[2] Yanbo Wang, Muhan Zhang. Towards Better Evaluation of GNN Expressiveness with BREC Dataset. arxiv/abs/2304.07702", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review, acknowledging our contributions, and voting to accept our paper. We address each point individually below. “W/Q” numbers the weakness or question, followed by our response.\n\n---\n> **W**: “More datasets [1, 2] can be included to evaluate expressivity, especially long range expressivity.”\n\n**A**:  Thank you for your suggestion. We have already included the BREC dataset in our manuscript, as detailed in Table 4.  \nRegarding [1], we do not expect more expressive local GNNs, such as our proposed $r$-$\\ell$GIN, to outperform state-of-the-art methods on LRGB, as the predictive performance appears to correlate with the GNNs' ability to capture long-range dependencies.  However, we are enthusiastic about testing our algorithm on these tasks. Our first preliminary results without any sweeping or positional encodings suggest improved performance over standard baseline:\n|  | Peptides Structural (MAE $\\downarrow$) | Peptides Functional (AP $\\uparrow$) |\n|---------------|-----------------|---------------------|\n| GCN\t| 0.3496 ± 0.0013 | 59.30 ± 0.23 |\n| GINE\t| 0.3547 ± 0.004 | 54.98 ± 0.79 |\n| GatedGCN\t| 0.3420 ± 0.0013 | 58.64 ± 0.77 |\n|$r$-$\\ell{}$GIN\t| 0.2513 ± 0.0021 | 65.70 ± 0.60 |\n\nWe are happy to follow Reviewer pJ5G’s suggestion and update our manuscript with these experiments.\n\n> **Q**: “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$).”\n\n**A**: Thank you for your insightful question. It is indeed an open question and part of our ongoing research. While it is established that for every $k$, there exists an $r$ such that $r$-$\\ell$WL is not less powerful than $k$-WL (see Corollary 1 in our manuscript), this does not prove that increasing $r$ will enable $r$-$\\ell$WL to solve graph isomorphism universally. We conjecture that $k$-WL and $r$-$\\ell$WL are incomparable, where $r$ is chosen as described in Corollary 1. We acknowledge the complexity of this topic and appreciate the opportunity to explore it further.\n\n---\nThank you again for your insightful review and positive comments, especially regarding our work's strong theoretical contributions. Please let us know if you have any further questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X7GND6oajX", "reviewer": "Reviewer_zkXv", "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.", "questions": "Please comment on **W1**, **W2** and **W3**.", "limitations": "This has been addressed in a satisfactory way by the authors.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1 Interesting Idea:**\nThe inclusion of paths in the neighborhood is an elegant and innovative way of extracting local information around a vertex. This approach allows for rigorous theoretical analysis and captures cactus graphs, which is a significant advantage.\n\n**S2 Experiments:**\nThe authors empirically demonstrate that the neural version of $r$-$l$WL captures crucial information for graph learning tasks.\n\n**S3 Capturing Cacti:** The most technically involved proof shows that cactus graphs, or at least their homomorphism counts, can be captured. This is a noteworthy result.", "weaknesses": "**W1 Capturing Cacti:** \nThe 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.\n\n**W2 Insufficient Comparison with Subgraph GNNs:** \nThe 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.\n\n**W3 Experimental Comparison:**\nThe 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.\n\n**W4 Unlabeled Graphs:**\nThe paper does not address vertex labels. Can the approach be generalized to vertex labels? Additionally, $c^{(0)}$ in section 3.2 is undefined.\n\nMinor Comments: The authors sometimes use obscure references. For instance:\n- line 71: Do you mean Tinhofer or Dvorak?\n- line 96: Why refer to Dimitrov 2023 for the notion of graph invariant, which has existed for ages?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thorough review and valuable suggestions. We include a theoretical and experimental comparison with $k$-OSAN in an updated manuscript and believe the points below address the Reviewers' questions adequately. \n\n---\n> **W1**: “The motivation for focusing on cactus graphs is unclear…”\n\n**A1:**  Our primary focus was on developing a scalable and expressive method. Our analysis revealed a close connection to cactus graphs, a significant class between trees and tree-width 2 graphs. While the class of tree-width 2 graphs is larger, no less than cubic time GNN is known that can count all tree-width 2 graphs. Hence, our method can provably capture a smaller class than 3-WL, but is more scalable and local. This is a trade-off we make. Note that this shows that our method, while being local, is not less expressive than other non-local variants, e.g., k-OSAN. See the next answer.\n\nMoreover, many chemical datasets contain cactus graphs; $58.77\\\\%$ of ZINC250K are cactus graphs. Consider, for instance, rings with hydrogen atoms attached or any other structure (e.g., carboxyl groups). The presence of such structures, while being cactus graphs and not mere cycle graphs, can significantly alter the molecular properties of a more complex graph. The practical significance of being able to count cactus graphs is also shown by the improved predictive performance of our model when applied to chemical datasets. \n\nWe are happy to follow the Reviewer's suggestion and include this discussion on the relevance of cactus graphs in our manuscript. \n\n> **W2**: “Insufficient Comparison with Subgraph GNNs: …”\n\n**A2**: Thank you for highlighting this important direction. We will address this in detail in a potential camera-ready version, referencing Qian et al. (2022). They introduce k-OSAN and vertex-selected k-OSAN (k-VSAN), both bounded by $k+1$-WL but incomparable to $k$-WL. We can make the following simple observation: For every $k$, there exists an $r$ such that $r$-$\\ell{}$WL is not less powerful than $k$-OSAN and $k$-VSAN, following from the fact that both are less expressive than $(k+1)$-WL and Corollary 1 in our manuscript.\n\nMoreover, as a corollary of our Theorem 2, we show that for every $k \\geq 1$, there exist infinitely many graphs that $1$-$\\ell{}$WL can separate but $k$-VSAN cannot distinguish. This shows that the Reviewer’s conjecture that “r-$\\ell{}$WL may be included in k-OSAN” does not hold. \n\nThe proof of this result parallels the proof of Corollary 2 ii) in our manuscript: (B. Zhang et al., 2024) characterized the class of patterns $\\mathcal{F}^{\\mathrm{sub}(k)}$ that $k$-VSAN can homomorphism-count. There exist infinitely many cactus graphs in $\\mathcal{M}^3$ that are not in $\\mathcal{F}^{\\mathrm{sub}(k)}$. A combination of Theorem 3.8 in (B. Zhang et al., 2024) and Theorem 2 in our manuscript shows that there are infinitely many graphs that $1$-$\\ell{}$WL can separate but $k$-VSAN cannot distinguish. We will present this result in the main paper and a detailed proof in the appendix.\n\nThis result demonstrates that even our least expressive algorithm is not less powerful than any $k$-VSAN algorithm, which may be of independent interest, given that the expressive power of $k$-VSAN increases with $k$, along with its computational complexity.\n\nSince there are pairs of graphs that $1$-$\\ell{}$WL cannot distinguish but $k$-VSAN can, this proves that $1$-$\\ell{}$WL and $k$-VSAN are incomparable for any $k$.\n\n> **W3**: “Experimental Comparison: …”\n\n**A3**: We are happy to update our manuscript and include OSAN in the BREC dataset-baseline. To go beyond $3$-WL with $k$-OSAN, we would need to consider at least $2$-OSAN, which has a complexity of $n^2m$, where $n$ is the number of nodes and $m$ the number of edges. This complexity is too high for our computational resources, which is why we did not use $2$-OSAN or higher-order variants as baselines, consistent with other research in this area.\n\nHowever, if the Reviewer can provide a reference with $2$-OSAN baseline results, we are happy to include those in our paper!\n\nWe will also clarify the capabilities of other methods:\n\nTable 1: PPGN has $3$-WL expressivity and can count up to 7-cycles and homomorphism-count all graphs of tree-width 2. Nested GNNs are strictly between $1$-WL and $3$-WL. GSNs include explicit subgraph counts. While GSN is more powerful than $1$-WL, its exact expressive power depends on the chosen pattern to be counted.\n\nTable 2: We have a strict hierarchy in the expressive power of the baselines we chose: 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 in theory. Their homomorphism-expressivity is fully characterized in (B. Zhang et al., 2024).  \n\nWe will add these explanations in more detail and details for other real-world experiments to our appendix.\n\n> **W4**: “Unlabeled Graphs: …“\n\n**A4**: Yes, we can easily account for graphs with vertex labels, both for the patterns we aim to subgraph- or homomorphism-count and for the graphs themselves. Note that in our empirical evaluation, all GNNs use node attributes, if available in the datasets. Our proofs require minimal modifications to accommodate vertex labels. We will follow your suggestion and update our manuscript to include these modifications. Thank you!\n\nMinor Comments:\n\nLine 71: We referred to Tinhofer, who proved that two graphs are fractionally isomorphic if and only if $1$-WL does not distinguish them. This result was used by Dell et al. (2018) to prove that $1$-WL is equivalent to the homomorphism-counts of all trees. We would ask the Reviewer kindly to specify the Dvorak references so that we can add a citation if applicable.\n\nLine 96: We will remove the Dimitrov 2023 reference from this line.\n\n---\n\nThank you again for your valuable feedback, which led to new insights and results. Please let us know if you have any more suggestions or questions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QIWCcjuIAV", "reviewer": "Reviewer_rfpS", "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.", "questions": "1) What is the HASH function? do you have an example of such a function?\n2) Can you add tables concerning the times of your method compared to other methods?\n3)  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": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strengths of the paper are:\n* The ability to count homomorphisms of cactus graphs without any additional explicit substructure counts.\n* Scalability towards large datasets, especially when the graphs are sparse for these datasets.\n* The paper is well-written and easy to understand.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review, acknowledging our contributions, and voting to accept our paper. We address each point individually below. “W/Q” numbers the weakness or question, followed by our response.\n\n---\n> **W**: “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.”\n\n**A**: Thank you for your feedback. We have carefully revised our manuscript to ensure that all important terms, including the HASH function (see below), are clearly defined. \n\n> **Q1**: “What is the HASH function? do you have an example of such a function?”\n\n**A1**: The term HASH function is standard in color refinement algorithms such as $r$-$\\ell{}$WL. It refers to any arbitrary injective function on multisets. In practice, one can use SHA-256 of the sorted multiset as an example. For the neural variant, $r$-$\\ell{}$GIN, the HASH function can be realized by summation followed by an MLP. We have added this clarification to the paper.\n\n> **Q2**: “Can you add tables concerning the times of your method compared to other methods?”\n\n**A2**: We have included tables comparing our methods to other state-of-the-art methods in terms of memory and runtime. Please refer to Table 9 for these comparisons. Please let us know if you are interested in any other specific comparison. We are happy to add more comparisons.\n\n> **Q3**: “What is the motivation behind using $r=5$ in the experiments? would any result in worse results or simply better results by small significance on the expense of might higher time?”\n\n**A3**: We chose $r=5$ because it matches the cycle-counting power of 3-WL. For the second question, please refer to Table 8, which compares predictive performance for ZINC12K when varying $r$. This table demonstrates that $r=5$ provides a good balance between accuracy and computational efficiency. Increasing $r$ enhances the representation power and complexity of the model, which can negatively impact generalization performance. Therefore, it is crucial to strike a balance between expressivity, computational cost, and generalization abilities. \nTo address the Reviewer's question more concretely, we tested a $12$-$\\ell{}$GIN on ZINC12K. This configuration resulted in a test MAE of $0.075\\pm0.003$, which is within the standard deviation of the performance of a $5$-$\\ell{}$GIN. The runtime increased by approximately 20%, which remains more efficient than other higher-order GNNs, such as those based on the $3$-WL test. We will include the results for $r=6,\\ldots,12$ in Tables 8 and 9.\n\n---\nThank you again for your valuable suggestions, which have helped improve the clarity and contribution of our work. Please let us know if you have any more questions or suggestions!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a6h9ZaTuaO", "reviewer": "Reviewer_1SHr", "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.", "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:\n\n1. 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?\n\n2. 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?\n\n3. 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": "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.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper's strengths are rooted in its originality, introducing a novel algorithm ($r$-$l$WL) and corresponding GNNs ($r$-$l$GIN) that significantly enhance the expressivity of graph neural networks. These contributions are supported by rigorous theoretical proofs and empirical validation. Specifically, $r$-$l$WL demonstrates the ability to count cycles up to length $r+2$ and homomorphisms of cactus graphs, substantiated with detailed mathematical proofs. The experiments use several synthetic datasets to validate the counting power and expressiveness of $r$-$l$MPNN effectively. Furthermore, the paper contextualizes its contributions within prior work, highlighting the limitations of existing methods and demonstrating how $r$-$l$WL and $r$-$l$MPNN address these gaps. Overall, the claims are well-supported by theoretical proofs and empirical results, indicating a clear improvement over existing methods.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review, for acknowledging the originality and rigor of our paper, and for voting to accept. We address each point individually below. “W/Q” numbers the weakness or question, followed by our response.\n\n---\n> **W1**: “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.”\n\n**A1**: We agree that some of the mathematical proofs are difficult for readers without a strong background in graph theory and GNNs. To improve accessibility, we have included visualizations of some proofs and counterexamples in the appendix, see, e.g., Figure 10,11,12 or Section H. Following Reviewer 1sHr’s suggestion, we add additional intuitive explanations before every proof in the respective section. Thank you for the suggestion! \n\n> **W2**: “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.”\n\nA2:  Thanks for recognizing our experiments! We expand the experiments by including the peptides-functional and peptides-struct datasets from the LRGB paper [1]. Our first preliminary results without any sweeping or positional encodings suggest improved performance over standard baselines:\n\n|  | Peptides Structural (MAE $\\downarrow$) | Peptides Functional (AP $\\uparrow$) |\n|---------------|-----------------|---------------------|\n| GCN\t| 0.3496 ± 0.0013 | 59.30 ± 0.23 |\n| GINE\t| 0.3547 ± 0.004 | 54.98 ± 0.79 |\n| GatedGCN\t| 0.3420 ± 0.0013 | 58.64 ± 0.77 |\n| $7$-$\\ell{}$GIN\t| 0.2513 ± 0.0021 | 65.70 ± 0.60 |\n\n[1] Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, Dominique Beaini: Long Range Graph Benchmark. NeurIPS 2022.\n\n> **Q1**: “How does the computational complexity of $r$-$\\ell{}$WL compared to existing higher-order $k$-WL variants like $3$-WL in practice, especially when dealing with large and dense graphs?\n\n**A1**: When dealing with dense graphs, i.e., graphs with $n^2$ edges the computational complexity of $r$-$\\ell{}$WL is comparable to the complexity of $k$-WL. In the worst-case scenario, assuming a complete graph, every node has $n$ neighbors. Hence, the preprocessing step requires $n*n^{r+2}$ operations and the number of forward operations is also exponential in $r$. This is a limitation for large and dense graphs. We noted this in our manuscript, see Page 9 under Limitations.  From a practical perspective, our method currently scales well to the Peptides dataset, even when using $r=7$, which contains 15k graphs with on average 151 nodes and 307 edges.\n\n> **Q2**: “What are the limitations of $r$-$\\ell{}$WL in terms of scalability and memory usage, particularly when applied to real-world datasets with varying degrees of sparsity?”\n\n**A2**: Our $r$-$\\ell{}$WL algorithm is particularly well-suited for sparser graphs, as demonstrated in our experiments. This focus allows us to efficiently handle a wide range of real-world datasets that exhibit sparsity. While there are scalability and memory challenges when dealing with denser graphs, we see this as an exciting opportunity for future enhancements. To increase scalability and manage memory usage more effectively, one potential future direction includes random subsampling methods to subsample paths per node. We are actively researching ways to optimize our method to better manage dense graphs, thereby broadening the applicability of our algorithm across diverse datasets.\n\n> **Q3**: “In Table 1, why didn't your method perform well on the Extension (100) and CFI (100) datasets compared to 3-WL and PPGN?”\n\n**A3**: Wang et al. [1] note that 3-WL and PPGN “surpasses most GNNs in CFI graphs due to k-WL’s global receptive field.” Whereas local WL variants like our $r$-$\\ell{}$WL exhibit lower performance due to their limited receptive fields.\nWe also mention that CFI graphs are particularly challenging; specifically, 60 pairs are distinguishable only by 3-WL, 20 by 4-WL, and 20 remain indistinguishable even by 4-WL. To improve performance, we would need to increase $r$. However, this runs into memory issues given our current resources, as CFI graphs contain many paths in the $r$-neighborhoods, often having a high number of edges (up to 742).\n\nOur method successfully distinguished 95 out of 100 pairs of extension graphs, which aligns closely with the performance of the baseline models as detailed in Table 2. This demonstrates that our algorithm is competitive on the extension graphs.\nWe are actively exploring ways to optimize our method to handle such challenging graphs more effectively in future work.\n\n[1] Wang, Yanbo, et al. \"An Empirical Study of Realized GNN Expressiveness.\" International Conference on Machine Learning. PMLR, 2024.\n\n---\n\nThank you again for your valuable feedback, which we will incorporate into a potential camera-ready version, making our work even more accessible!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (oral)