On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
Authors: Matthias Lanzinger
Pablo Barcelo
Venue: ICLR 2024 poster (2024)
Keywords: WL test
graph neural networks
graph motif parameters
subgraph counting
Primary area: learning on graphs and other geometries & topologies
TL;DR: We provide a characterization of the expressive power of the WL test in terms of graph motif parameters

Abstract: Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the $k$-dimensional 
Weisfeiler-Leman ($k$WL) test, a widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the $k$WL test.
A central focus of research in this field revolves around determining the least dimensionality $k$, for which $k$WL can discern graphs with different number of occurrences of a pattern graph $p$. We refer to such a least $k$ as the WL-dimension of this pattern counting problem. This inquiry traditionally delves into two distinct counting problems related to patterns: subgraph counting and induced subgraph counting. Intriguingly, despite their initial appearance as separate challenges with seemingly divergent approaches, both of these problems are interconnected components of a more comprehensive problem: "graph motif parameters". In this paper, we provide a precise characterization of the WL-dimension of labeled graph motif parameters. As specific instances of this result, we obtain characterizations of the WL-dimension of the subgraph counting and induced subgraph counting problem for every labeled pattern $p$. Particularly noteworthy is our resolution of a problem left open in previous work 
concerning induced copies.
We additionally demonstrate that in cases where the $k$WL test distinguishes between graphs with varying occurrences of a pattern $p$, the exact number of occurrences of $p$ can be computed uniformly using only local information of the last layer of a corresponding GNN.
We finally delve into the challenge of recognizing the WL-dimension of various graph parameters. We give a polynomial time algorithm for determining the WL-dimension of the subgraph counting problem for given pattern $p$, answering an open question from previous work.
We additionally show how to utilize deep results from the field of graph motif parameters, together with our characterization, to determine the WL-dimension of induced subgraph counting and counting $k$-graphlets.

Published as a conference paper at ICLR 2024
ON THE POWER OF THE WEISFEILER-LEMAN TEST FOR GRAPH MOTIF PARAMETERS
Matthias Lanzinger
Pablo Barceló
TU Wien & University of Oxford matthias. Janthigr www.errrwwiiinn.c...
PUC Chile & IMFD & CENIA mharcelo@uc.c.
ABSTRACT
Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the i-dimensional Weisfeiler-Leman (kWL) test, widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the &WL test. A central focus of research in this field revolves around determining the least dimensionality k, for which AWL can discern graphs with different number of occurrences of pattern graph P. We refer to such a least as the WL-dimension of this pattern counting problem. This inquiry traditionally delves into two distinct counting problems related to patterns: subgraph counting and induced subgraph counting. Intriguingly, despite their initial appearance as separate challenges with seemingly divergent approaches, both of these problems are interconnected components of a more comprehensive problem: "graph motif parameters", In this paper, we provide a pre- cise characterization of the WL-dimension of labeled graph motif parameters. As specific instances of this result, we obtain characterizations of the WL-dimension of the subgraph counting and induced subgraph counting problem for every labeled pattern P. Particularly noteworthy our resolution of a problem left open in previ- work concerning induced copies. We additionally demonstrate that in cases where the &WL lest distinguishes between graphs with varying occurrences of a pattern P. the exact number of occurrences of P can be computed uniformly using only local information of the last layer of a corresponding GNN. We finally delve into the challenge of recognizing the WI--dimension of various graph parameters. We give a polynomial time algorithm for determining the WI-dimension of the subgraph counting problem for given pattern P. answering an open question from previous work. We additionally show how to utilize deep results from the field of graph motif parameters, together with our characterization, WL-dimension of induced subgraph counting and counting k- k-graphlets.
determine the
INTRODUCTION
Context. Graph neural networks (GNNs) have gained increasing importance over the last decade due their ability to process and operate over graph-structured data (Wu al., 2021 Zhou al. 2020; Joshi et al. 2020). Tasks in which GNNs excel include node classification (iiao et al. 2022)
graph classification (Errica et al. 2020), link prediction (Teru et al., 2020 Zhu et al. 202 I, and
query answering over know knowledge graphs (Daza & Cochez 2020 Galkin et al. 2022). Based on these,
GNNs have found applications in many fields, including social network ana mnilysis (Kipf & Welling
2018), recommender systems (Ying et al.) 2018), chemistry (Gilmer et al. (017). semantic web
(Hogan et al., 2022; Schlichtkrull al. 2018), natural language processing (Marcheggiani & Titov
2017). and combinatorial optimization DDai al. 2021).
The practical importance GNNs has spurred the community to study their expressive power. This refers to the ability of GNNs to distinguish pairs of non-isomorphic graphs. As it was early observed in two landmark articles (Morris et al., 2019 Xu et al. 2019), the expressive power of so-called message-passing GNNs (MPGNNs) is precisely that of the Weisfeiler- & Leman 1968), ) one of the most renowned methods for checking graph isomorphism. As recently observed, this correspondence holds even in cases where graphs are node- and edge-labeled, naturally
(WL) test (Weisfeiler

---

Published as a conference paper at ICLR 2024
representing the rich structure present in knowledge graphs (Barceló et al. 2022
The above has
ignited significant interest among experts in exploring which graph properties can be distinguished
by the WL test, especially those that are crucial for the applications of MPGNNs (Arvind et al. 20200)
Chen et al., 2020 Morris et al. 2020 Barceló et al. 2021 Huang et al.
2023
Bouritsas et al. 2023).
A class of graph properties that have received special attention in this context is the number of times a given "pattern" appears as a subgraph in a graph. The relevance of this class emanates from the fact that subgraph counts are used in several graph-related tasks, such as constructing graph kernels (Shervashidze et al. 2009 Kriege et al. (0188) and computing spectral graph information (Preciado & Jadbabaie 2010). Subgraph counts also lie the basis of some methods that measure the similarity between graphs (Alon et al. (2008) Therefore, it is crucial to comprehend the extent to which these methods align with the expressive capabilities of the WL. test (or equivalently, MPGNNs)
In its more general version, the WL test is characterized by parameterized dimension, k 22 (Cai et al. 1992, Morris al. 2019). The k-dimenssonal WL test, or &WL test for short, iteratively colors the k-tuples of nodes in a graph until a fixpoint is reached. Two graphs are said to be distinguishable by kWL, if the multisets of colors of all k-tuples reached at this fixpoint are different. A graph property ʃ can be distinguished by &WL if for any two graphs G, H where S(G) S(H) only if G and H are distinguishable by &WL. We are then interested in the least k for which a parameter can be distinguished by &WL. We refer to this ie as the WL-dimension of the parameter.
Several important results have been obtained over the last few years regarding the WL-dimension of counting the number of copies of graph P (the pattern). We summarize some of such results next, by distinguishing the case in which we count copies of P (subgraphs) from the one in which we count induced copies of P (induced subgraphs). For the sake of clarity, we call the former the subgraph WL-dimension of P and the latter the induced subgruph WI-dimension of P.
Counting subgraphs: An important notion in graph theory is the treewidth of graph, which intuitively measures its degree of acyclicity (Diestel 2012). The hereditary treewidth of a pattern is, in broad terms, the largest treewidth any of the homomorphic images of P. P.Arrind et al. (020)) initiated the study of the ability of the WL. test to count subgraphs in terms of the notion of hereditary treewidth. They established that if the pattern P has hereditary treewidth k, then P has subgraph WL-dimension at most k. Nevertheless, the sole instance in which they were able to demonstrate the validity of the converse was for k= 1, i.e., they showed that P has subgraph WL-dimension one iff P has hereditary treewidth one. In the meantime, some partial results were obtained for the case when k = 2 over particular classes of graphs. For instance, by combining results in Arvind et al. (2020) and Fürer (2017). one obtains that the largest cycle (respectively, path) with a subgraph WL-dimension of two is that of length seven. Very recently, however, this gap has been closed. In fact, Neuen (2023) proves the following for each k 2 1: if P is pattern, then has subgraph WI--dmmnsionn & iff P has hereditary treewidth k. This also provides an alternative explanation for the aforementioned result on cycles (resp., paths), as one can observe that a cycle (resp., path) has hereditary treewidth two iff it is of length at most seven.
Counting induced subgraphs: Most of the existing results on counting induced subgraphs were obtained in Chen et al. (2020). The authors show that all patterns with k 1 nodes have an induced subgraph WL WL-dimension bounded by k. Moreover, this is optimal for k 1; i.e., no pattern with three or more nodes has induced subgraph WL-dimension one. It is not known if this correspondence continues to hold for k > 1, i.c., whether there are patterns with le + 2 or more nodes with induced subgraph WL-dimension k. for ke > 1.
It is noteworthy that the previously mentioned results regarding counting induced subgraphs were achieved in a broader context compared to the results concerning counting subgraphs. Specifically, the former apply even to labeled graphs, where each node and edge is assigned label, whereas the latter were derived for non-labeled graphs.
Therefore, we have different levels of understanding of the capabilities of the &WL test for counting subgraphs and induced subgraphs. Furthermore, these two issues have been addressed separately and employing distinct techniques, which enhances the perception that there is no inherent structural linkage between the two. However, evidenced by research in the field of counting complexity, there exists a cohesive approach through which these types of problems can be examined. In fact, the counting of subgraphs and induced subgraphs are fundamentally interconnected, akin to opposite
2

---

Published as a conference paper at ICLR 2024
faces of coin, as they can be represented as linear combinations of one another (Lovász 1967, Thus, we can achieve insight into either of them by exploring the linear combinations of the other.
Expanding upon this idea, Curticapean et al. (2017) introduced comprchensive framework for graph motif parameters, which are defined as linear combinations of subgraph counts. In this paper, we study the ability of the WL test to count graph motifs, which provides with general approach for studying problems related to subgraph counting in this setting. Our main contributions are summarized below. It is worth noting that all such results are derived within the framework established in Chen et al. (2020), which focuses on labeled graphs. This introduces an additional level of intricacy into all the proofs presented in this paper.
By building on tools developed by Neuen 2023) and Seppeli (2023), we establish a precise characterization for the class of labeled graph motifss with WL-dimension k; for k 2 1. Specifically, for subgraph counting, this class precisely corresponds to the patterns of hereditary treewidth k, aligning with the characterization presented by Neuen] (2023) for the case of unlabeled graphs. For induced subgraph counting, this class contains precisely the patterns featuring k nodes, thus resolving the open issue posed by Chen et al. (2020).
The previous result characterizes for which graph motifs I' the kWL test is able to distinguish between graphs with different numbers of occurrences of r. A natural question arises: Is possible obtain the number of occurrences of a graph motif T in a graph G' by computing a function over the multiset of colors of k-tuples of vertices obtained from the &WL test? We answer this question affirmatively. This result can be of interest researchers working on MPGNN applications, as it suggests that by designing a suitable MPGNN architecture, one might be able to count the number of subgraphs that appear in a given graph.
We finally move into the problem of determining the WL-dimension for the problem of counting the occurrences of a given graph patter/ P. Our characterization shows that for counting induced subgraphs this problem is trivial as the WL-dimension is precisely the number of vertices in P minus 1. For subgraph counting, in turn, the problem is nontrivial, as we have to check for each homomorphic image of P whether its treewidth is at most k. Since the number of homomorphic images of P is potentially exponential, this yields naive exponential time algorithm for the problem. We show that, in spite of this, the problem admits polynomial time algorithm. The existence of such algorithm was left open in Arvind et al. (020) even for the case k = 2.
Since many of the proofs in the paper are extensive and complex, we have opted to place technical details in the appendix and offer proof sketches in the main body of the paper to conserve space.
2 PRELIMINARIES
Labeled graphs. We work with graphs that contain no self-loops and are node- and edge-labeled. Let Σ and A be finite alphabets containing node and edge labels, respectively. A labelled graph is tuple G = (V. E, X, k)). where V is a finite set of nodes, E is a set of undirected edges, i.e., unordered pairs of nodes, À V + E is function such that X(x) represents the label of node for each V, and k: E ~ A is a function such that s((e) represents the label of edge e, for each e e E.
Given labeled graphs G (V, E, k) and G' (V', E' X R.)., ). a homomorphism from G to G" is function f: V - VV such that: (1) (u, v) E - (())) E E', for each u. U E (2) A(v)= = X((()), for each e V, and (3) for each edge (u,v) E E, holds that k(u,v)= (f),) If, in addition, f is a bijection and the first condition is satisfied by the stronger statement that (u,v) ε E <> (J(u), f(x) e E', for each u, e V. then we say that is isomorphism. We write Hom(G, G¹) for the set of all homomorphisms from G to G" and homs(G, G') for the number of homomorphisms in Hom( (ommG,Com (G,G). G').
For k-tuple ū (Ui,..., 2k) V(G)*, k we write G[ø] as shorteut for G[ e }. The atomic type Gt, 6) of a k-tule of vertices in a labeled graph G is some function such that, for T (G)* and i E V(H)* k. it holds that atp(G, v) = atp( H, ū) if and only if the mapping i + w; is an isomorphism from G[ū] into H [w).
3

---

Published as a conference paper at ICLR 2024
Weisfeiler-Lemaae test. Let G be a labeled graph. The kWL test, for k: 0, iteratively colors the elements in VGG), that is, all tuples of k nodes from V(G). The color of tuple UE ((G)* after iterations, for i 2 O, is denoted of (t). This coloring is defined inductively, and its definition depends on whether A = or k > 1.
For k= = 1, we have that
(a (1) == (V) (()((,,),,
if 0 (v, V(G)))
if 1
In other words, of (v) consists of the color of vertex in the previous iteration, along with multiset that includes, for each neighbor w of v in G, an ordered pair consisting of the color of in the previous iteration and the label of the edge connecting and w.
For k 1, we have that
(atp(G, (b) := [(tt (t), f[et(w, i 1,,11 w V(G))) if
i
Here, ct(w, i, 6) denotes the color tuple for w E V(G) and öe V(G)*, and is defined as:
ct(w,i, (cl (T[w/&])
where o[w/j] denotes the tuple that is obtained from e by replacing its jth component with the element In other words, <f (ō) is formed by the color of e in the previous iteration, along with a multisct that includes, for each node w G, a tuple containing the color in the previous iteration for each tuple that can be derived from E by substituting one of its components with the element w.
The &WL test stabilizes after finitely many steps. That is, for every labeled graph G there exists t 2 O such that, for each U, w E V(G)* & holds that
(0) et (w)
(0) cin
We then define the color of tuple e in G as (1)==
We say that two labeled graphs G and H are indistinguishable by kWL (or G = H), the k-WL algorithm yields the same coloring both graphs, i.e.,
(c)()) DE BB = -lc (w) / (
The version of the WL test used this paper is also known as the folklore kWL test (as defined, for instance, by Cai et al. (1992)). It is essential to note that an alternative version of this test, known as the oblivious kWL test, has also been explored in the machine learning field (Morris et al. 2019). Notably, it established that for each k the folklore &WL test possesses the same distinguishing capability as the oblivious (k + WL test (Grohe & Otto 2015).
Graph motif parameters. labeled graph parameter is a function that maps labeled graphs into Q. A labeled graph motif parameter (Curticapean et al., 2017) is a labeled graph parameter such that, for a labeled graph G, its value in is equivalent to (finite) linear combination of homomorphism counts into G. More formally, function I' is a labeled graph motif parameter, if there fixed labeled graphs Fi,..., , Fe and constants U1.... 1lg Q > (0), such that for every labeled graph G:
T(G) Σ (F.,
(I)
We refer the set (Fi...., Fe} the support STp of
It is often not easy to see whether function graphs is a graph motif parameter. Fortunately, we know that certain model counting problems for large fragments of first-order logic are indeed labeled graph motif parameters. In the following, we view labeled graphs as structures. Logical formulas can then be defined over a signature that contains a unary relation symbol U., for each label Σ, and binary relation symbol Eg. for each label 5 A. Let be formula with free variables T of the form
By (g. A (x))
4

---

Published as a conference paper at ICLR 2024
where 1 is formula consisting of positive atoms, conjunction and disjunction, and &² is conjunction of inequalities and possibly negated atoms. We call such formulas positive formulas with free constraints. We write #G(G) for the number of assignments to F for which the formula is satisfied in labeled graph G. It is known that the function #y for such formulas can be expressed as a finite linear combination of homomorphism counts with projection. Göbel al. (2024) have recently initiated the study of how homomorphism counts with projection relate to the AWL test. In this paper, we are content with a more restricted fragment for which no projection in the homomorphism counts is required.
Proposition (Chen & Mengel (016)) Dell et al. (2019), Let ip be quantifier-Fie free positive formula with free constraints. Then the function #G labeled graph motif parameter
Example 1. We start by showing that counting subgraphs and counting induced subgraphs are examples of graph motif parameters (for each fixed pattern). Suppose for simplicity that we consider graphs without node labels and with single edge label, and let E be the corresponding relation symbol. Consider a graph (V, E) for which we want to count occurrences as a subgraph. We can do this via the following positive formula with free constraints:
ØH :=
E(Iu:Iz) A
A
Tu # Ty.
(u.0)eF
Notice that this formula has freee variable Tu, for each node E V. If now we want to count the number of occurrences of H as an induced subgraph, we can simply extend Φи with the following conjunction: A(u.))E - R.). graph motif parameter by ind
Consider the following formula with free variables T2....,
dis
Isinjsk
The satisfying assignments to øIs in graph G are precisely its independent sets of size at most k. We see then that counting l- k-independent sets is a graph motif parameter.
Counting graph motifs parameters and the WL test. Take > O. Consider graph parameter T. We state that the &&L test can distinguish I if, for any pair of labeled graphs G and H where T(G) T(H), follows that G #xw1. H. The WL-dimension of a graph parameter is the minimal k > such that the &WL test can distinguish r.
CHARACTERIZING THE WL-DIMENSION OF GRAPH MOTIF PATTERNS
In this section, provide characterization of the WL-dimension of labeled graph motif parameters. To grasp the results presented in this section, is crucial to first define the concept of the treewidth of graph G. This concept, well-known in graph theory, aims to quantify the degree of acyclicity G.
Let G = (V, E, x)) be a labeled graph. A tree decomposition of G is a tuple (T, ax, where T is tree and is function that maps each node of the tree T subset of the nodes in V, that satisfies the following:
For each (u, e E, there exists a node / T with {u, v) e a())
For each node V. the set (1 T v e a())) is subtree of T. In other words, the nodes / of T for which (1) contains v are connected in T.
The width of tree decomposition (T, of G is defined as maxte (a(1)] - 1. The treewidth of G is then defined as the minimum width of any of its tree decompositions. It is easy to see that G has treewidth one if and only its underlying graph is a tree.
The following is the main result in this section. It characterizes the WL-dimension of graph motif parameter in terms of the treewidth of its support set.
Theorem 2. Let I' be a labeled graph motif parameter. The WL-dimension I' is the maximum treewidth of any labeled graph in Supp(I').
Dell et al. (2019) additionally require v to be in CNF/DNE. For our purposes the potential blowup incurred by transformation into CNF is of consequence.
5

---

Published as a conference paper at ICLR 2024
Before providing proof sketch of this result, we show some examples of how the theorem can be applied to concrete instances of labeled graph motif patterns used in this paper.
Example 2. Let us consider first the case of counting subgraphs for a labeled graph H. We denote the corresponding labeled graph motif pattern by Sub We assume that H does not have self-loops. We call a labeled graph H' a homomorphic image of H, if there exists a surjective homomorphism from H into H' Notice that the set of homomorphic images of H contains a finite number of labeled graphs up to isomorphism. Following Curticapean et al. 2017). we denote by spasm (H) the set of all labeled graphs that are obtained from the homomorphic images of И by removing self-loops. As shown in Curticapean et al. (0117), the support of Suby is precisely the set spasm H). It follows from Theorem 2 that the Hs for which AWL can distinguish subgraph counting for Sub f! are precisely those for which the maximum treewidth of a labeled graph in spasm( Hf) is at most k. This result has been established for unlabeled graphs in Neuen (2023). Here, we extend this result to labeled graphs.
Consider now the case of counting induced subgraphs for H. We write Indæ for the corresponding labeled graph motif pattern It can be shown that, in this case, the support for Indæ is the set of all labeled graphs H' that can be obtained from H by adding edges among its nodes. If H has nodes, then the support for H contains the clique of size lo which is known to have treewidth & 1. Furthermore, this is the labeled graph with the largest treewidth in the support of H. It follows from Theorem 2 that the Hs for which I-LL can distinguish induced subgraph counting for Ind,r precisely those with at most k + nodes. This solves an open question from Chen et al. (020). D
We now discuss our proof of Theorem 2 The full argument requires us to extend various existing results in the field to the setting of labeled graphs. We defer those proofs the appendix. Let JF be class of labeled graphs. We write G = H if for every F & F it holds that homs F", G) = homs F. H). sistrorpiiimmiiiiinissiiiiiii
Following Roberson (2022), we define the labeled
closure of F. denoted homclosure( F), as the set of all labeled graphs L for which the following holds for every labeled graphs G, H:
G H = homs( G) homs(T. H).
We say that F is labeled homomorppismm-diiiinggittii paper by Neuen establishes that the class of all (unlabeled) graphs of treewidth most is labeled homnomophiinn-dssingguuiin closed (Neuen, (023). As we establish next, this extends to the labeled setting. Here we denote by LT & the class of all labeled graphs of treewidth at most k. closed.
closed, if homclosure(FF) F. A recent
Lemma 3. Fix k > O. The class LTx, k. labeled aaatamooppiimmddittigggiii
Proof Sketch. For our proof we show that a recent breakthrough result by Roberson (022) holds also in the labeled case. The result depends on the notion of weak oddomorphisms which, roughly speaking, are a particular kind of homomorphism that satisfies additional constraints (see Appendix [B] for details). To simplify the presentation, we actually only show that Roberson's 's result holds for edge-labeled graphs, i.e., those labeled graphs where all vertices have the same label. We then closedness from the
show that this is enough and that we can lift the fommomorhiisn-distinggiiss edge-labeled case to the general labeled case.
Formally, we show the labeled analogue of (Roberson) 2022 Theorem 6.2). Namely, that every class of labeled graphs F that satisfies the following two closure properties is also labeled homomorphism- distinguishing closed. (1) If F F, and F has a weak oddomorphism into G. then G E F. (2) F is closed under restriction to connected components and disjoint union. Once we have established that show that both properties are satisfied by LT k- For the first, in particular,
the theorem still holds, we can build on parts of Neuen's 's argument for the unlabeled graph case. The second property is a well known property of treewidth and requires further insights.
The second intermediate result that need is the following lemma, proved recently by Seppelt. Lemma 4 (Lemma 4 in (Seppelt 2023)). Let F and L be classes of labeled graphs. Suppose F is finite and its elements are pairwise ton-isomorphic. For each F F, let pt. be element of R. Then F g homclosure( L), for all labeled graphs G, H we have that:
G H.
Σ uF. homs(F. FEF
Σ eee-homs(FFF) FEF

---

Published as a conference paper at ICLR 2024
We also need the following result which establishes that two labeled graphs G and H are indistin- guishable by &WL if and only homs( (F, G) = homs( F, H), , for every labeled graph F of treewidth k. The unlabeled analogue of this result is due to Dvorák (210)) (rediscovered by Dell et al. (2018)).
Lemma 5. For all labeled graphs G, H. we have G =wwL H if and only if G ECT, H.
Proof of Theoremm 2 Let F be the support of T and k be the maximum treewidth labeled graph in F, for k O. We first show that &WL can distinguish I. Take two labeled graphs G, H with G = H. By Lemma5) we also have that G ECT, H. In particular, homs F, G) = homs( for every F e F, and therefore:
T(G) Σ us-hhoomsEP PEF
EF pup--hom((F..) () I(H).
Suppose now, for the sake of contradiction, that the 2WL test can distinguish I, for l k. Let G, be arbitrary labeled graphs. Notice that we have the following:
GELT, H G Gew H T(G)==(() I(H) Σ uu-shoms(FF (F,G)= Σ hap--hos((F)) H).
The first implication follows from Lemma and the second one since the ZWL test can distinguish But then Lemma tells that F c homclosure (CT+). and Lemma that homclosure (CT LT This is contradiction since FF contains at least one labeled graph of treewidth h: l.
4 COUNTING OCCURRENCES OF GRAPH MOTIF PATTERNS
In this section, establish that if graph motif parameter I' has WL-dimension k. then one can actually obtain the number of occurrences of T in a graph G by looking independently only at the colors of the individual k-tuples, rather than the full multiset of stable colors for all k-tuples. This is of particular interest when looking at the &WL test from the perspective of MPGNNs. The natural expression of the WWL test in MPGNNs leads to final layer that assigns color each k-tuple of vertices. So, r is a labeled graph motif parameter, and we want to compute T(G) over labeled graph G. then Theorem 6 shows that it not necessary to combine the information of the final layer in a global way. but that there is some uniform function that can map each individual color to rational number, the sum of which will exactly be I'(G).
More formally, we show the following result.
Theorem Let I be labeled graph motif parameter and suppose that the maximum treewidth of labeled graph in STpp(T) is most k. Also, let Ck denote the of possible colors produced by the kWL test. Then there exists a function Cp Q such that T(G)- EEev Or(c' (6)), for every labeled graph G.
Theorem is obtained by using the following lemma, whose proof can be found in the appendix.
Lemma 7. Let F be a labeled graph with treewidth at most k and let C denote the set of possible colors produced by the kWL test. There exists a function Tp: N such that homs F, G) Evev uF (c (6)), for each labeled graph G.
Theorem is then obtained from Lemma follows. Let assume that Supp, (Fi, ........ Fe) and I(G) is defined as in Equation (T). We define 0r:Ck as @r(c) Σl H4 17, (c), for each ce C* We then have that
T(G)= = Σ p4 homs Gi
(Equation
= Σ
Σ
P4 (F:
(Lemma
(G)
Σ
Σ
ue TE (+E)
Σ (r(c)) BEV(O)&
#G)

---

Published as a conference paper at ICLR 2024
5 DETERMINING THE WL-DIMENSION FOR SUBGRAPH COUNTING
We finally move on the recognizability problem for WL-dimension. That is, for given graph motif parameter I, we want to know the WL-dimension of T. Arvind al. (2200) previously raised the question for which labeled graph patterns H, the graph parameter Sub can be expressed by 2WL. Here, we give polynomial time algorithm that decides the WL-dimension for all subgraph counting problems, thus also resolving this question as a special case. For the analogous problem Ind we have already seen in Example 2 that the recognition problem is, in fact, trivial. In addition, we determine the WL-dimension of counting k k-graphlets, i.c., all connected induced subgraphs on k vertices, as illustrative examples of how further such results can be derived from the deep body of work in graph motif parameters.
We will begin with the case of subgraph counting. Recall that minor of labeled graph H is a labeled graph H' that can be obtained from H by removing nodes or edges, or contracting edges (that is, removing an edge and simultaneously merging its endpoints). By Theorem [ and the following discussion on spasm H). recognising the WL-dimension of Sub is precisely the problem of recognising the maximum treewidth of the homomorphic images of H. We can use classic results in the field of graph minors express this as a property checkable in monadic second-order logic (MSO), for which model checking is tractable in our setting. We give a more detailed sketch of the argument below, full details are provided in the appendix.
Theorem 8. Fix k > O. There is a polynomial time algorithm for the following problem: given a labeled graph H, checking if the WL-dimension of Subh at most k.
Proof Sketch. The algorithm first checks whether the treewidth of H is at most k. It is well known that this can be decided in linear time for fixed k Bodlaender (1996). Obviously, H e spasm H), and thus if the treewidth of H is strictly larger than k. we are done and the algorithm rejects. By the Robertson- -eymmuur Theorem (Robertson & Seymour 2004), there is a finite set of graphs Fk. such that there is F E Fy that is minor of graph G if and only if the treewidth of H is at most k. We then show that there is an MSO formula for such that
H - OF =
F is a minor of some homomorphic image of H
Clearly then 3 FE fPk is an MSO formula such that H F &p if and only if the maximum treewidth in the spasm is at most k. By a standard algorithmic metatheorem of Courcelle (Courcelle) [990). deciding H == yp is possible in time [H) where is the treewidth of H. As & k by our initial check, and yp depends only on k, the problem in O(Hl) for fixed
We now move to study the WL-dimension of counting k-graphlets, popular problem in graph mining and analysis of social networks [Bressan et al. (2017); y; Jin et al. (2118). Here, no dedicated algorithm necessary as the WL-dimension will be immediate from observations about the respective support when viewed as graph motif parameters. While the problem of counting k-graphlets is itself popular, its analysis in our context serves as example of how the recently established theory of graph motif parameters can answer these types of recognizability questions.
The logical view, via positive formulas with free constraints, is not the only natural way see that graph parameter is indeed also a graph motif parameter. An alternative notion that is known to correspond to graph motif parameters is the problem of counting all induced subgraphs of size that satisfy some arbitrary (computable) property á (Roth & Schmitt, 2020). Thus, with o being the property the graph being connected, this immediately tells us that counting k-graphlets is graph motif parameter. In fact, Roth & Schmitt (2020) not only shows that every such property is graph motif parameter, but they also determine precisely when the k-clique is in the support (i.c., has a coefficient 0). Moreover, in the case of properties that are closed under the removal of edges, there is a strong connection to combinatorial topology that can be leveraged to make this determination.
Proposition 9. For l: 1, counting the number of k-graphlets has WL-dimension k: 1.
Proof Sketch. Let Sndi be graph parameter that counts the number of induced subgraphs on l vertices that are connected, i.e., the number of k-graphlets. For graph property Φ, let E, be the set of all
A Iternatively it is also possible to show that the maximal treewidth in spasm is minor-closed and obtain different set of forbidden minors for H itself.
8

---

Published as a conference paper at ICLR 2024
edge-subsets of the complete graph on A vertices, such that the corresponding subgraph satisfies property Φ. Roth Schmitt (2020) showed that the problem of counting all induced subgraphs on k vertices that satisfy ó is graph motif parameter, and that the k-clique is in the support of the parameter precisely when
Σ (-1) O. A
Furthermore, they show that if & is closed under removal of edges, then Ex {0) forms so-called simplical graph complex and the reduced Euler characteristic of this simplical complex is also non- zero exactly when the k-clique is in the support of the parameter (see (Jonsson 2008) for details regarding these notions).
C for the property of being connected and NC for its complement, i.e., disconnected- ness. Property NC is closed under removal of edges and its simplical complexes are well understood (cf., [Jonsson 2008)). In particular, their reduced Buler characteristic is known be =(k- 1)!, which is non-zero for natural k. Now, it is enough to observe that
Now, let
(-1) AEE
E-1) -0 AEEE
as the properties are complementary and the sums thus form alternating sum of binomials. Since the left-hand sum is non-zero, so is the right-hand sum for property C. We can therefore conclude that the k-clique is in the support of Ind ( demonstrating that the maximal treewidth in the support is least k 1. The argument of Roth & Schmiut (2020) also implicitly shows by construction that the support contains no graphs with more than & vertices, thus also confirming that the treewidth in Supp(Ind is no higher than k 1. Applying Theorem completes the argument.
Moreover, Proposition is constructive and many cases is feasible to determine the support from logical formulations of parameters as in Example For example, following the construction of Dell jtt al. 2019) for the formula ΦIs reveals that counting k-independent sets also has WI--dimension 1-1. What is particularly noteworthy in this context, is that we can use the exact same methods that have been used to study the parameterized complexity of these problems. Just as the WL-dimension, the complexity of computing graph motif parameter I' depends precisely in (T) (Curticapean et al. 2017). That is, analysis of the complexity of computing a graph motif' parameter and analysis of the WL-dimension of the parameter revolve around the same question of how high the treewidth of the basis can become.
the maximum treewidth
6 CONCLUSIONS AND LIMITATIONS
We have shown that recent developments in graph theory and counting complexity can be brought together to provide a precise characterization of the WL-dimension of labeled graph motif parameters. We have also shown that if graph motif parameter I' belongs to such class, then the number of "appearances" of T in a given labeled graph G can be computed uniformly only from local information about the individual k-tuples from the output of the &WL test. Based on known results this suggests that k-dimensional MPGNNs are capable of computing this number, if equipped with the right pooling functions (Morris al. 2019 Xu al. 2019). Some work this direction has already been carried out in Chen et al. (2020) by using local relational polling. Finally. we have used our characterization show that both the classes of patterns for which the &WL test can distinguish labeled subgraph counting and labeled induced subgraph counting can be recognized in polynomial time.
The main limitation of our work is that it only concerns the worst-case behavior of the algorithms considered. In fact, the counterexamples our proof constructs for cases in which the 1WLL test is not capable of counting the number of occurrences of graph motif I are rather complicated and do not necessarily resemble the cases encountered practice. Therefore, it would be interesting to understand to what extent these results relate to average-case scenarios, how well they align with practical applications. We leave this for future work.
Thii observation was already made implicitly but without details in Roth 2019
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We are very grateful to Marc Roth for many valuable and enjoyable discussions that have influ- enced this work. Matthias Lanzinger acknowledges support by the Royal Society "RAISON DATA" project (Reference No. RPRR1/201077 and by the Vienna Science and Technology Fund (WWTF) [10.47379/IC2200]] Pablo Barceló has been funded by the National Center for Artificial Intelli- gence CENIA FB210017, Basal ANID, and by ANID Millennium Science Initiative Program Code ICN17002.
REFERENCES
Noga Alon, Dao P. Hajirasouliha I, Hormozdiari and Sahinalp SC. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 13:1-24, 2008.
Vikraman Arvind, Frank Fuhlbrücck, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman
invariance: Subgraph counts and related graph properties. J. Comput. Syst. Sci., 113:42-55 59, 2020.
Pablo Barceló, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In NeurIPS 2021, pp. 25280-25293, 2021.
Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel A. Romero Orth. Weisfeiler and leman go relational. In LoG, volume 198 of Proceedings of Machine Learning Research, pp. 46. PMLR, 2022.
Hans Bodlaender. linear-time algorithm for finding tree-decomppositonns of small treewidth. SIAM J. Comput., 2566):1005-1317, 1996. doi: 10.1177/900953339992512111
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. JEEE Trans. Puttern Anal. Mach. Intell., 45(1) 2023.
2023.
Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Count- ing graphlets: Space vs time. In WSDM, pp. 557-566. ACM, 2017. doi: 10. (0.1145/3118611300187777
Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Comb,, 12(4):389-410, 1992.
Hubie Chen and Stefan Mengel. Counting answers to existential positive queries: A complexity classification. In Proc. PODS, pp. 315-326 326. ACM, 2016. doi: 10.1145/902251..22227 URL
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In NeurIPS, 2020.
Bruno Courcelle. The monadic second-order logic of graphs. recognizable sets of finite graphs. Inf. Comput, 85(1): 1990.
Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms a good basis for counting small subgraphs. In STOC, pp. 210-223. ACM, 2017.
Hanjun Dai, Artem Kozachenko, Mark Schmidt, Ioannis Tsochantaridis, and Petar Veličković. Learning combinatorial optimization algorithms over graphs. In ICML, 2021.
Daniel Daza and Michael Cochez. Message passing for query answering over knowledge graphs. 02406
CoRR, abs/2002.024066. 2020. htttps::/aaxi...rtttttt
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets weisfeiler and leman. In Proc. ICALP. volume 107 of L.Plcss pp. 40:1-40:14 Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2018 doi: 1230/LIP1cc.ICALP..000
Holger Dell, Mare Roth, and Philip Wellnitz. Counting answers to existential questions. In Proc. ICALP 2019, volume 132 of L/Plcs, pp. 113:1-113:15. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019.
10

---

Published as a conference paper at ICLR 2024
Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
Zdenek Dvorák. On recognizing graphs by numbers of homomorphisms. Graph Theory, 64(4): 330-342, 2010. doi: 10. 10.1002/jgt.20461.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. In ICLR, 2020.
Martin Fürer. On the combinatorial power of the ceassfeillr-eehhmal algorithm. CoRR, abs/ 100.00034,,, 2017.
01023
Michael Galkin, Zhaocheng Zhu, Hongyu Ren, and Jian Tang. Inductive logical query answering in knowledge graphs. In NeurIPS, 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In JCML, 2017.
Andreas Göbel, Leslie Ann Goldberg, and Mare Roth. The weisfeiler-leman dimension of existential conjunctive queries. 2024.
Martin Grohe and Martin Otto. Pebble games and linear equations. Symb. Log., 80(3):997-844 2015.
Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d' Amato, Gerard de Melo, Claudio Gutier- rez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel- Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan E. Sequeda, Steffen Staab, and Antoine Zimmermann. Knowledge graphs. ACM Comput. Surv, 54 (4):71:1-71:37, 2022.
Xingyue Huang, Miguel A. Romero Orth, ismail ilkan Ceylan, and Pablo Barceló. A theory of link prediction via relational weisfeiler-leman CoRR, abs/2302.02209, 2023.
Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Network global testing by counting graphlets. In ICML, volume 80, pp. 2338-23444 PMLR, 2018. URL /ttptttt///proeed.ngs mlr press/
v880/jin1b..hrr html
Jakob Jonsson. Simplicial complexes of graphs, volume 3. Springer, 2008.
Chaitanya K. Joshi, Yujia Li, and Bryan Perozzi. A comprehensive survey on graph neural networks. IEFE Communications Surveys & Tutorials, 2020.
Thomas Kipf and Max Welling, Community detection in graphs with graphsage. ICLR, 2018.
URL http:tttt///xiv..ooo http://rgggbbbb/bbbeebs 02216
Nils M. Kriege, Christopher Morris, Anja Rey, and Christian Sohler. A property testing framework ijcai.org. 2018.
for the theoretical expressivity of graph kernels. In IJCAI, pp.
László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-)):311-235 1967.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In EMNLP, 2017.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, pp. 4602 0002-469,,40 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In NeurIPS 2020, 2020.
Daniel Neuen. Homomorppissmmiisiiggiihhi closedness for graphs of bounded tree-width. CoRR, abs/2304.07011 2023.
OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2023. Published electroni- cally at hhttp://ceis.om
11

---

Published as a conference paper at ICLR 2024
Victor M. Preciado and Ali Jadbabaie. From local measurements network spectral properties: Beyond degree distributions. In CDC, pp.
IEEE, 2010.
David E. Roberson. Oddomorphisms and homomorphism indistinguishabiiity over graphs of bounded degree. CoRR, abs/2206.1033 2022.
Neil Robertson and Paul D. Seymour. Graph minors. XX. wagner's conjecture. J. Comb. Theory, Ser. B, 92(())325-335 2004. doi: 10. 10.1016/j.jctb.. 2004.000440000
Mare Roth. Counting problems quantum graphs: Parameterized and exact complexity classifica- tions, 2019.
Marc Roth and Johannes Schmitt. Counting induced subgraphs: A topological approach to #w[1]- hardness. Algorithmica, 82(8):2267-2291, 2020.
Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, 2018.
Tim Seppelt. Logical equivalences, homomorphism indistinguishability. and forbidden minors. CoRR, abs/2302. 1290, 2023.
Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTAYS, volume 5 of JMLR Proceedings, 2009.
Komal K. Teru, Etienne G. Denis, and William L. Hamilton. Inductive relation prediction by subgraph reasoning. ICMI., pp. 9448 9448-9457, 2020.
Boris Weisfeiler and A.A. Leman. The reduction of graph canonical form and the algebra which appears therein, 1968.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Mach. Vis. Appl., 33(1):4, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDDD, 2018
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Maosong Sun, and Jie Tang. Graph neural networks: A review of methods and applications. Al Open, 2020.
Zhaocheng Zhu, Zuobai Zhang. Louis-Pascal A. C. Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. NeurIPS 2021, pp. 19476-29490 2021.
12

---

Published as a conference paper at ICLR 2024
A PROOF OF LEMMA 7
This section focuses on the proof of Lemma] 7 While is well known that the &WL test of a graph G determines the homomorphism counts from every graph H with tw k. we are interested in slightly stronger statement. In particular, let H be a graph and let a be some tuple of k distinct vertices in H. We show that any two k-tuples of vertices 6, tü possibly from different graphs, that obtain the same stable color by the kWL test, there are the same number of homonorphisms extending ā + 0 and ā + ö to the respective graphs of ö and W. As a consequence, we see that it is not necessary to know the full multiset of stable colors to determine the homomorphism count from some pattern F, but rather homs( F) can be computed by computing partial count for each k-tuple independently and simply summing them up.
This is of particular interest when looking at the WLL test from the perspective of GNNs. The natural expression of the kWL test in MPGNNs leads to final layer that assigns color to each k-tuple of vertices. If we want to compute homs(F.)) with a GNN, Lemma 7 shows that it is not necessary to combine the information of the final layer in some global way. but that there is some uniform function that can map each individual color to a rational number, the sum of which will exactly be homs(F,.).
We proceed with some technical definitions. For tree decomposition (T,B) and subtree T" of T will write B(T)) to mean V B(u). It will be convenient to consider nice tree decompositions. A nice TD of labeled graph G is rooted TD where the bags of all leaves are singletons and all non-root nodes are only of three types:
An introduce node u is the only child of parent p. and has B(u)= B(p) u {a} for some a E (G) x By)).
forget node u is the only child of parent p, and has B(u) B(p) > {a} for some a B(p). Split nodes u, u are the only two children of parent p. and have Buu) = B(v) = B(p).
It is well known that if a graph has treewidth k then it also has a nice TD of width it.
For labeled graphs F, G with ā E V(F)*, E V(G)* we write Hom(F, G) + 6] for the set of all homomorphisms from F into G that extend the mapping + E. For a vertex v of labeled graph F we write F v to mean F[V(F) x {u}].
Proposition 10. Let (T, B) be a tree decomposition of labeled graph F. Let T be a subtree of and let be a node adjacent to T in T. For any 2 E B(a) B(T') and y E B(T') it holds that if {y,2}e E E(F), then y B(a).
Proof. Suppose the statement were false. Then there is an edge {y, 2} with = in B(x) but not in B(T"), and y f B(a). Let 7* be the subtree of T x T"' that contains a. By connectedness, occurs only in bags of T", whereas y occurs in none of them. Hence, the edge {y, 2} cannot be subset of any bag. contradicting that BB is a tree decomposition.
Our plan in the proof of Lemma will be to connect nice tree decompositions to &WL colors. Intuitively, just as the &WL test moves "outward" one vertex at a time each step, a nice tree decomposition changes only one vertex at a time from parent to child. It is known that Hom(F..) is determined by the local homomorphisms from F [B) for each node u of tree decomposition, together with the overlap of bags in neighboring nodes in the tree decomposition. Roughly speaking, we show that a color produced by the &WL test has enough information to determine these two facets.
Our formalization of this idea will require significant technical overhead for bookkeeping. To this end we introduce the following notioons. Let F, G, H be labeled graphs, let e e V (G)), w V(H)* and let p: V(F) V(G), v: V(F)= (8, 1) -strict S d-ggremment if μ maps vertices in S only to vertices in i and (xx) = 02 = v(x) wi for all x S.. For tree T with node labels Tuu) 5 V(F) of F we say that two homomorphisms in colorful strict T leaf agreement if for every leaf E of there exist ō e V (G)) we V (HH)* such that μt, are in (6, -striitt L(t) aggreemen and for some i I either (0) of (w) if [[))] & k or ct(a, i, ( = cb i, w where i = 8 a, w b otherwise.
V (H). For set S s V(F) with |S] S l we say that u., are in
Lemma 11. Let F, G and H be labeled graphs, let O V(G)*, We V(H) with of (T) = di (w) for some 1, and let S (F) with |S| & k. Let μ Hom (F, G) v Hom F, H) such that they are in
13

---

Published as a conference paper at ICLR 2024
(6, w) -strict S-agreement. Let F' be labeled graph with vertex such that F F and is only adjacent to vertices in S. Then there is a bijection between Hom( (F [G][ and Hom( [v] such that
1. for all p' E Hom F", [u] and ((')) there are d' = ua, w'b a VV(G)bb such that pl (((()) are in (i', u6 J-strict Su ( -agremmet, and
2. ct( a, 1 1, = ct(b, -
Proof. Let = =
Suppose n² n u a} is Hom (F.m(F",,).... G). Since cf (0)= =c; (w) there
must be some be V(H) such that ct(a, i 1, ct(bb i 1, 1,w). Let v' - {r + b). Observe that because of the equal color tuples we have in particular, atp(G,ua) = atp H, wb). As x is only adjacent to vertices in S' we have that for {y.z} E(F) that
(u(()) E(G) = au E(G)
{wz, E E(H) = (z)) E(H).
The middle equivalence follows from alp(G, ūa)= alp H. wb). Similarly, it follows immediately from equivalence of the atomic types, that the vertex labels of a and 6 must be the same, and that ka((,, a}) KH ((w,,)))) Additionally, clearly have that p v/ are in (va, -trictt S" S'-agreement.
This concludes the argument for the individual homomorphisms. To see that this is indeed always one-to-one correspondence it is enough to observe that because of (8) = ct (w), for every distinct choice of a there must be an appropriate distinct choice of b as above.
Lemma 12. Let G and H be labeled graphs, let F be labeled graph with nice TD (T" ,B) of width k let à be a tuple made up of k vertices that match a bag of the (T B). Let 8 e V(G)*, w E V ( with et (T) = = Then [Hom( G) + e]] |Hom F, H) + w]]
Proof. Let r be a node in T with B(u) = {a. E [R]]] and assume, w.L.o.g,, that it is the root of subtrees T of I that contain the node that there is bijection from Hom( [F[].. [a ū] to Hom( [F[T], H)[ ( + w) such that for every p in the domain of i, it and (11) are in colorful strict 7 leaf agreement. Recall that colorful strict agreement requires agreement on colors (or color tuples) on some round i 2 1 of the kWL algorithm. We will not explicitly argue these indexes in the following but instead note that because c* (T) e² (w). which forms our base case in the following induction, we can start from assuming agreement at an arbitrarily high i. It will be clear from our induction that starting from an higher than the longest path from to a leaf will be sufficient.
T We argue inductively
In the base case T contains only r. Since (0) (w) we have that (u, + wihse]k] is an isomorphism from G[ö] to H[w]. Thus, + BE Hom(F[TT, Gf iff H)m(F[T).HH.
For the step, assume the statement holds for a tree T". Suppose we extend T" be node that is adjacent in T, giving priority to split nodes (i.e., suppose we always extend first by all adjacent split nodes).
If split node then the leaf bags remain unchanged. The only change that needs to be discussed is the special case that a new leaf is introduced. In that case, by definition the new leaf has the same bag as an existing leaf and the same witnesses for colorful strict T' leaf agreement apply to the new bag as well, that is satisfies the desired property also for T.
If a is not a split node, then let 33 be the leaf of T that is adjacent (in T*) to a. Suppose a is a forget node. By assumption any μ Hom Hom(F[T'), ()) o] and ((μ) are in colorful strict T" leaf agreement. Since B(T)= B(T",, the sets of homomorphisms do not change T" and T. It therefore sufficient to check that the colorful strict lcaf agreement constraints are also satisfied for leaf B(a). In that case, satisfies the desired properties also for T. Since B(a) S B(B). any μ.v that are in (d, -sstiitt aggreaent,,, are also in (d, -dtricstriet B(a))-areemmen It remains verify the color constraint d, E. BB3) S k, then we already have (d) (e) by assumption and are done. Otherwise, we only know that ct(t, dd) = ct(u, i, 2) for d d = E vertex from B(3) that is forgotten by a. Let be the index such that su()) dj. We distinguish two cases: first, suppose that there is only one such index and there is at least one other y e B(a) such that (vy) dy- Then there must be some index j' such that dy is not in y (B(a)). By striet
u. Let a be the
14

---

Published as a conference paper at ICLR 2024
agreement the same must hold for ey and (B(()). Hence, f., are also in (a(t/j'], (tt//"),[[///"]] strict B(a) aagreemeen,,,, and we have ci_ (é[t//()) &i (d[ujj") by equality of the color tuples. for the other case, if is the only vertex in (())) that μ maps to dy or there is more than one index that equals p(=), then simply take j' = and proceed as in the other case. This concludes the case where is a forget node.
Suppose that is an introduce node that introduces vertex z and is adjacent (in T* leaf B of T". By Proposition 10 we have that all vertices of F[T) adjacent (in F) to 2 are in B(a). By + l] to Hom
[a ū that maps every homomorphism to one that is in colorful strict T leaf agreement. Thus, in particular all homomorphisms are in (d, -sttrict (33)aarremment with of (d) c (because we assume width k, an introduce node can only follow nodes with at most E vertices in the bag). We can therefore apply Lemma 11 every pair Js. (()) to see that there is bijection i, from (on(F[T).G) [p] to Hom (F[T), HT]( such that every μ' e Hom [[T], [u), is in colorful strict T leaf agreement with d(xx). If [B(a)) s k we can apply the same reasoning as for forget nodes above to observe that the appropriate constraint on the color follows from the lemma.
assumption there is a bijection c' from Hom (F[T", G) Hom(F(T')
Let L' be the disjoint union of all the individual Ey for all E Hom(F( G) - Bj. To see that the '/2 are in fact disjoint it is enough to observe that the sets Hom(F[T) [u] are disjoint for different choices of ju as dom(u) _ V( V(F[T)). Since all ly, are injective, so is v. To see that i' is also surjective, suppose a E Hom [[T]] H) + w not in the image of z'. This means that cannot be in any set Hom(F[T) [())] for μ e Hom(F[T). G) - u). But 1 is surjective and therefore this would mean that the projection of y to ]( is not a homomorphism from F[T'] to H (extending ā + T). But homomorphisms are closed under projection to induced subgraphs, so this is impossible. It follows that e' is also surjective and therefore is the desired bijection.
As an alternative proof strategy, the main ideas from above can be used to define an algorithm that computes Hom(E F, [ā + 8] from c² (ō). An argument along this direction also demonstrate computability of the functions in Theorem and Lemmal 7 in the general case (in the uniform case where C* is finite, it suffices to enumerate graphs until all colors in C* are observed). However, in practice the colors in the &WL test are not maintained in their explicit form as nestings of tuples and multisets but rather by compactly representing the ct tuples via some hash function. In that setting, the viability of such an algorithm would be limited.
V(G)* we have that the sets of homomorphisms Hom(F, F, [ā + o] and Hom(F. F. G) + w] are disjoint. It is then straightforward to see that Hom( G) Dev Hom(F, G) ā + ū] and hence homs(
Proof of Lemmal 7 Observe that for any two distinct tuples
Eeev |Hom(F, [ā - é] By Lemma 12 we have that Hom( F, G.G)(a w] depends only on (b). This naturally induces a function 7F that map the possible colorings of the &WL test C to the respective number of homomorphisms, i.e., such that
Σ (Cra(c())) (EV
Σ (VV(
|Hmm(F, (F.G((a + r] = homs G)
Another proof detail of Lemma that we would like to emphasize is that it is not strictly necessary for the stable color of e and w to be equal. Inspection of the proof reveals that it is sufficient for them to be equal for cf. where i is greater than the maximal number of introduce nodes on a path from to a leaf. Building on this observation, Lemmal 12 actually also shows that especially for small patterns (the number of introduce nodes is of course no greater than the number of vertices) it is sufficient for the graphs to be equivalent under a limited number of steps of the kWL test, rather than equivalent in the stable color, to deduce that hom(F,, (..) the same in both graphs
Theorem 13. Let F, G. and H be labeled graphs and let n= n (FF). Suppose that G and H have the same color multiset after n steps of the kWl test. Then homs F, G) homs(F., F, H).
15

---

Published as a conference paper at ICLR 2024
B TECHNICAL DETAILS FOR SECTION 3
The goal of this section to show that for any labeled graph F that has treewidth greater than k. there are labeled graphs G and H such that G E H but homs(F, G) homs( F. H). Thus, G and H are witnesses to the fact that the kWL test cannot express the function homs(F..).
To do so, we show that two important results on the functions homs for unlabeled graphs still hold in the labeled setting. To distinguish more clearly between the labeled and unlabeled case we will use the term plain graphs to be those labeled graphs where the vertex- and edge-label alphabets singletons. For technical reasons we will initially focus on edge-labeled graphs, which are labeled graphs where the vertex-label alphabet is singleton. For labeled graph G, we write plain(G) G) for the plain graph obtained by making all edge and vertex labels of G the same (without changing the vertices or edges of G).
The main property of homs that we are interested in is equivalence for fixed classes of graphs. Formally, let F be a class of labeled graphs. We write G Ey H if for every F F holds that homs F, G) homs( F, H). Two families of graph classes will be particularly important in the following. We write Ts for the class of plain graphs with treewidth at most k let LT& be the class of
labeled graphs of treewidth at most k; and let ET& k for the class of edge-labeled graphs with treewidth at most k.
The first result that we need is the labeled version of classic result due to Dvorák (2010) and later rediscovered by Dell et al. (2018). We recall the lemma as stated in the main body. Lemma 5. For all labeled graphs G, H we have G =WWL H if and only if G ECT, H.
We wish warn the reader about an unfortunate confluence of terminology at this point. Some of the literature that we build on also refers to labeled graphs. Unfortunately, our use and the uses in the immediately related literature are pairwise distinct and thus require extra care of the reader. We will add further clarification at points where this becomes directly relevant in this section.
For the second key result we need to recall what it means for class of plain graphs to be aamnommrhhimmnddiiiiggsiiiniin
closed. A class of plain graphs F is homomorphism distinguish- ing closed if for every graph F & F,, there are graphs G, H such that G = H and homs( F, GF homs(F, F, H). The notion naturally extends to the setting of (edge-)labeled graphs by taking F, as class of llabeled graphs and every mention of G, and H as (edge-)labeled graphs. To clearly distinguish the property in text going forward we will refer to the case where all involved graphs are labeled as labeled nomomorphiim-ddiiinngggu
closed, and analogously we use edge- labeled homomorphism-distieee distinguishing closed when all graphs are edge-labeled. For plain graphs the following was very recently shown by Neuen (2023)
Theorem 14 NNeen 2023 ). The class Tk is dunoomophismmddiiinnuuiiiiig closed.
Our second key ingredient will be to show the same holds in the labeled setting. That is, that LTx is labeled
closed.
For our setting where every edge has exactly one label, we are not aware of any clear way to build directly on Theorem 14 to show the labeled versions. Our plan will therefore be to show that the machinery underlying the proof of Theorem 14 still works in our labeled setting.
The necessary machinery is due to Roberson (022), who introduced the theory of oddomorphisms and showed their deep connection to homomorphism distinguishability. We recall the definition here for the labeled setting, note however that the definition does not respect labels, except implicitly through the definition of homomorphism of labeled graphs. The neighborhood (N(v) of vertex in labeled graph G is the set of adjacent vertices (ignoring any labels). Let F and G be labeled graphs and let be homomorphism from F to G. A vertex of F is odd/even (w.rt. Φ) if (f is odd/even for every V E No(o(a)). An oddomorphism from F to G is homomorphism & such that:
1. every vertex a of F either odd or even with respect to Φ, and
2. for every V(G), (v) contains an odd number of odd vertices.
homomorphism is a weak oddomorphism if there is subgraph F' of F. such that olv(F) an oddomorphism from F' to G.
16

---

Published as a conference paper at ICLR 2024
For plain graphs, Roberson showed that any class of graphs that is closed under weak oddomorphisms, disjoint unions, and restriction to connected components is homomorphism haaatooppiisnddiiinnuuhhiiig closed. one main goal of this section show that the same also holds for labeled graphs.
Theorem 15 (Labeled Version of Theorem 6.2 (Roberson 2022)) ) Let F be a class of labeled graphs such that
1. if F e F and there is weak oddomorphism from F to G, then G F,, and
2. IF is closed under disjoint unions and restrictions to connected components.
Then F is labeled
closed.
first observe that the class LTR satisfies the conditions of the theorem. Indeed, Condition 15 is trivially satisfied as the treewidth of a graph is the maximum treewidth over the graph's s connected components (and labels do not influence treewidth). For Condition
Before move to the proof of Theorem 15
D we can reuse the following key part of the proof of Theorem
14
Proposition 16 (Neuen 2023)). Let F be a plain graph Tk- If there a weak oddomorphism from F to G, then G 7k.
Recall that labels serve no explicit role the definition of an oddomorphism beyond restricting the set of homomorphisms overall. Formalizing this observation we can show the same also for labeled graphs.
Lemma 17.
Let CTx l. and G be a labeled graph. If there is a weak oddomorphism from F to G, then G CT k-
Proof. First, observe that for labeled graphs F, G. if di is an oddomorphism from to G, then is also an oddomorphism from plain(F) to plain(G), Now, if there is only weak oddomorphism from F to G, there is some subgraph F" such that Ølv(F) is an oddomorphism from F" to G. Hence, it is also oddomorphism from plain(F") plain(G),, meaning that where is weak oddomorphism from plain(F)) F)) to pla
We have that tw [)) (ouppain(1))) s k, and therefore by Proposition 16 plain(G) E The And therefore also tw( ()) tw (plainn G)) S k, i.e., Ge LT
we then immediately obtain the key technical result for homomorphism distinguishing closedness in labeled graphs. Theorem 18. LT t labeled homomorphism distinguishing closed.
Assuming Theorem 15.
The rest of this section is organized as follows. We first verify that Theorem 15 holds in Appendix B.
We then argue Lemma 5 in Appendix B.2 Finally, in Appendix B.3 we briefly note why Lemma also holds in the labeled setting.
B.1 PROOF OF THEOREM 15
We will closely follow the proof of Theorem 6.2 in (Roberson] 2022). We will see that adapting the initial definitions in the right way will actually leave most of the framework for plain graphs intact. In many situations the effect of the labels is on the argument is very subtle. For the sake of verifiability we therefore repeat the modified arguments for the critical path in the unlabeled setting here. We wish to emphasize that, if not stated otherwise, all proofs are effectively due to Roberson.
We first recall the construction of Roberson for the case of plain graphs, roughly following the presentation of Neuen (2023). Let G be a plain graph and U s V(G). Define J. as 1 if u U and otherwise. The graph CFI(G, U) is the graph with vertices
V(CFI(G,U) ((v, S) E (G), S E (v),, |S| 80,u mod 2}.
The graph has edge ((v, S), (u, Т)} in E(CFI(G,U) if and only if (v, u) E(G) and e, / SAT.
The definition can be naturally adapted to the labeled setting by simply inheriting the labels of the original edges and vertices in G. To this end, let G now be labeled graph. We will define the labeled
17

---

Published as a conference paper at ICLR 2024
graph U) with V(CCFI(G,,)) =(CF((G)))) For vertex (t.S) V(G,U), U) we set the label A(t). For the edge- lage-lab function & edges we simply say that K0 (((( S), (u, x((v, u)). That is, k(((v,S), (u, }) if and only if (((v, u})) = and u SAT.
We will show that this definition preserves the key properties of CFI graphs in the labeled setting. This might seem unintuitive in U. However, the key arguments are relative to homomorphisms on the graphs from which the CCFI construction is obtained. That is, these homomorphisms already follow the constraints imposed by the labelings. We will say that two vertices u, are adjacent via label if there is an edge {u, v) with label é.
ignores the labels on the sets S = T(v) well as the label of vertices
Lemma 19. Let G be connected labeled graph and let U,U' V(G). Then CCFI(G,U) CCFI(G,U" (') 1/ = [U'| mod 2.
Proof. Let {u,0) E EGG) and U" UA. We show that Gu = Gyy Let o: V(CCFI(G.U) + V(CCFI(G,U")) be
((a, (a)) a a=wora=F" S)
otherwise
As in the plain graph case, it is straightforward to verify that this is bijection. Suppose that (a. S) and (b, T)) are adjacent via label in CCFI(G, U) ie.. {a.b) E (G) and {a, b) & SAT. Let S', T T).
such that ((.a))) .)) (a. S"), (((b T)) (b, If (a. =e, then S' SA(c) and T' = Te),), hence SAT = SAT. Thus, {a, b) is also not in S AT and ((a, is adjacent to (bb In the other case that {a, b) + e, then S and 1 will both, individually, contain {a, bj exactly if S and T, respectively, did. So again {a, b3 & AT"... In both cases, the labels of the edge in CCFI(G,)) and CCFI(G, U*) is simply inherited from {a, Thus, e preserves labeled adjacency.
If S) and (b. T) are not adjacent via label in CC),(G,U), then either {a, b) & GG) or {a,b) (G) (SAT). In the first case. clearly a(aa, S)) and label i either. In the latter case, we have shown in our argument above that {a,b) e S' AT" if and only if {a. b) SAT. Since {a, b] E SAT, S)) and ((b, T)) will not be adjacent via any label in CCFI(G.U').
cannot be adjacent via
We have shown that Gy = Gly for U Ue. This implies the lemma via the same final argument as in (Roberson) 2022 Lemma 3.2).
As consequence we can focus our investigation on two specific graphs CCFI(G) : CCFIIG and its nwist CCFI (G): CCFI(G. (v)) for some arbitrary V E VG)).
As a next step we adapt (Roberson) 2022 Lemma 3.4) to the labeled setting. We first recall definition from Roberson (2022) that carries over unchanged from the plain graph setting. For any U g VG),, the mapping Sv + v is a homomorphism from CCFI(G,U) to G. We will refer to this mapping as p in the following. For a homomorphism @ e Hom(F, G) define
Homa( CCFI(G,U) = { é Hom (F, CCFI(G, U)) po -
and observe that the sets Hom& CCFI(G, for & E Hom(P, G) partition Hom(I", CC))
The following statement is subtle in our context. Except for qualifying graphs G and F to be labeled, the statement is verbatim the same as Lemma 3.4 in (Roberson) 2022). That is, the labels are not explicitly considered in the system of equations. Note however that the equations are relative to some homomorphism from F to G, which makes the second set of equations implicitly follow the labeling. The fact that this system of equations does not change is the key to requiring only few changes in the later lemmas, as the argument proceeds mainly algebraically via this system of equations.
Lemma 20 (Labeled version of Lemma 3.4 (Roberson ) Let G be a connected labeled graph. let U s VG),, and let F' be any labeled graph. For a given @ E Hom F, G), define variables xf for all a E (F)) and e E I(á(a)). Then the elements of Hom (F, CCFI(G,U)) are in bijection with solutions of the following equations over Zz;
Σ
Je = SM
for all a V(F)
cEl()(a))
r/ x/ =
for all (a, F((F), where e= (d(a), E F((G)
(3)
18

---

Published as a conference paper at ICLR 2024
Proof. Suppose xa that a solution of the system of equations in the statement of the lemma. For a (F),,, let S(a) - E be the edges incident to Φ(a) (regardless of label) for which the variable Fr" ie., the set {e [(G 1 1]. Let be the mapping
(é(a),,(a))
We first show that & Hom (F, CCFI(G, U)). By Equation 2 va(a) is guaranteed to be a vertex
of CCFI(G,U) U) for all a (FF). To see that vs preserves labeled adjacency, suppose {a, b) Ex(F)
Then {o(a), ((6)) & (G) since & Hom F, G). From Equation (3) it follows that x2 2
Then, by construction CCFI(G, U), (a)) is adjacent via label to (b(6) exactly if {d(a), ((b)
((a)) Meaning that (a)) is adjacent via label i to (b) if is either in both S(a) and S(b)
or in neither, which is true because 2 ze Vertex labels are directly preserved via Ø.
The arguments for injectivity and surjectivity from the original proof (Roberson 2022 Lemma 3.4)
apply verbatim.
Since
the same system of equations (which does not explicitly consider labels) used
in Roberson (022), the development from Section 3 of (Roberson) 2022) holds almost unchanged repeat the relevant parts for the proof of Theorem [5
from here. For the sake of completeness
here, including discussion on why the proofs are unaffected by the labels where relevant.
Let G' be connected labeled graph, F labeled graph, and let Hom G). Let R be the set of pairs (a, e) such that a E V(F) and e e E()(a)). We define the matrices A e Zng (F)))R and Bd Z.2 7.(())= (
[1 if
(aac))
F10 otherwise
(4)
{1 i (b,c) and e (b(b),((c)
B (hho).(a.e)
(5)
10 otherwise
Let XU be the characteristic vector of Φ (U), i... the vector where the element corresponding to vertex a é (FF) is 1 a o (U) and otherwise (i.e., the vector (osta))t)aeV(()) The system of
equations from Lemma 20 can then be expressed
A R
= (60)
Xt
(6)
Theorem 21 (Labeled version of Theorem 3.6 (Roberson 2022) Let G be connected labeled graph, let U s (G), and let & Hom(F, G) for some labeled graph F. Then homs (F, CCFI(G)) > 0 and
homs&(F, CCFI(G,U) homs, (FFCCF))))
if Equation 6 has solution if Equation has no solution
0
Proof Sketch. The original proof (Roberson) 2022, Theorem 3.6) is a straightforward application of Lemma 20 The equations are exactly the same as the unlabeled case and the argument works without modification in our setting.
Theorem 22 (Labeled Version of Theorem 3.13 RRbeerson 2022 Let G be a connected labeled graph and F be a labeled graph. Then homs( F, CCFI(G)) z homs(F, CCFI (G)). Furthermore, the inequality is strict if and only if there exists weak oddomorphism from F to G. If such a weak oddomorphism & exists, there is a connected subgraph F' of F such that Φlv(Fy is an oddomorphism from F' G.
Proof Sketch. The original proof of (Roberson) 2022, Theorem 3.13) works unchanged, although might not be considered straightforward to observe that this is the case. We therefore repeat the key steps here with emphasis on the points where it needs to be observed that edge labels do not affect the argument. We wish to stress again that this proof is due to Roberson. We repeat here to allow for more targeted discussion of why labels have minimal effect on the argument, and to note necessary subtle differences.
19

---

Published as a conference paper at ICLR 2024
If homs(F, (CF) homs(F, CCFI (G)), then by Theorem 21 that Equation O6) over Zg does not have a solution. The non- non-existence of such a solution is equivalent to the existence of solution to the system (the Fredholm Alternative)
there is a Ø Hom (F, G) such
(A
(
(Bo)
: 4
(i)
(xx)T
where U- = {ū) contains the vertex such that CCFI" (G) CCFI(G, {ū}), y is indexed by vertices of F, and = is indexed by edges of F.
Since the argument creates certificate for the non-equivalence of the homomorphism counts, it might be unintuitive that constructing a weak oddomorphism from this certificate still works in the presence of the additional constraints of the edge labels. However, the certificate is still relative to ó é Hom( F, G) that respects the edge labeling and as we will see, this is sufficient for the argument to still hold.
Observe that a solution (y.z) ²)" to this system satisfies (A*)"yy= ( Let O= (= ya }} and let F' be the subgraph of F with all vertices and edges E(F") {e ((F) 2. 1}. The goal of the argument now is to show that ø is an oddomorphism from F" to G (and thus a weak oddomorphism w.r.t F). Since F" is a subgraph of F, it is clear that e is still a homomorphism from F' to G. regardless of labels. The arguments for the properties of the oddomorphism themselves are parity arguments on the number of adjacent edges between & (1) and (- for adjacent v, u e (G).. These arguments also hold unchanged in the labeled setting the labeled homomorphism 6 still preserves all adjacencies. Finally. F' as constructed above may not be connected. As in the unlabeled case is a weak oddomorphism @lv(F") for some subgraph F', then we can assume w.l.o.g., that F' is connected (Roberson 2022 Lemma 3.12).
then replace F' be a connected component by showing that if there
Lemma 23. Let F, G be labeled graphs. Then homs(E: F. CCFI(G)) homs(F, CCFI CCFI
Proof. It is known that the identity id on V(G) is an oddomorphism from G to G in the plain graph case (Roberson [202]] Lemma3.144 The definition of oddomorphism does not take the labels of edges into account (only the neighborhoods of vertices, which are unaffected by labels), and id is still a homomorphism the labeled setting. Hence, id must also be an oddomorphism from G to G in the
labeled setting. The statement then follows immediately from Theorem 22
The lemma also demonstrates that CCFI(G) & CCFI (G) for any G.
This concludes our replication of the key statements of (Roberson) 2022, Section 3). We will require one additional statement that is not necessary in Roberson's 's original argument for the proof of Theorem 15) For technical reasons we will require an labeled graph G such that for some F we can guarantee that homs( F, G) > O. For plain graphs this is straightforward by taking large enough clique for G. In the labeled case we need an alternative gadget.
Lemma 24. Let E, A be finite label alphabets and n 2 1. There is a connected labeled graph G such that for every labeled graph F with vertexledge-label alphabets E, A and n. vertices, homs( F, G) > 0.
Proof. Let C be the set of all (up to isomorphism) labelings of the n vertex clique with labels from Σ and A. Let G* be the disjoint union of all graphs in C. To get the desired graph G, add a fresh vertex with arbitrary label to G that is adjacent to an arbitrary vertex of each connected component (via an arbitrary edge label). Any n vertex graph F with labels from Σ, A is a subgraph of some element of G' C, and hence homs F, G') O. Since G' is subgraph of G, also homs( G) > 0.
We are now finally ready to prove Theorem 15
Again we can follow the original proof of Theorem 6.2 in (Roberson, 2022) very closely. We give the proof in full as some changes are made due to our streamlined presentation of the preceding statements.
Proof of Theorem 15
Let G be a graph not in F. Let GI......i G. be the number of connected components in G and let J be the connected graph from Lemma 24 such that homs(G:, 0 for
20

---

Published as a conference paper at ICLR 2024
all i [e]. By Condition (2), there is at least one connected component of G that is not in F, thus assume w.l.og.. that G1 F.
Let H be the disjoint union of CCFI(G1) and J, and let H' be the disjoint union of CCFI (C+) and J. We will show that H Ey H' and homs G, H) * homs( H'). For the former, suppose F F and connected. By Condition (1), there is weak oddomorphism from F to G, and thus homs(F, (CFF(G)) cause F is connected each homomorphism into H is either a homomorphism into J into CCFI(GI). i.e., homs( F, H) = homs F, CCFI(G,)) + homs(P,,) The same holds for H', i.e., homs( F, H') hF CCFI (G1)) + homs( JJ... Since both terms in both sums are equal we see that homs F, H) = homs( F, H'). Since this holds for all connected F E F, by Condition (2), it holds for all F E.F.
homs(F, CCFII
according to Theorem 22 Be-
We move on to show that homs(G, H) + homs(G, Fist, observe that homs(G, H) I Noms(G;;)) H) and similarly for H' our goal will be to show that homs(G;, H) 2 homs(G,, G,, H') > for all i e [C]. with at least one inequality being strict. For each i [{] we have
homs (G., H) homs CCF)( (ommsG;;:). hoomso G,, (CF) + homs(Gi J) homs G., H') >
The equalities are by connectedness, as already argued above. The first inequality follows from Theo- rem 21 By Lemma 23 first inequality is strict for 1 and thus homs(G, H) homs(G, H'). 0
B.2
LEMMA 5
In this section we will discuss why Lemma in the labeled setting. From Lemma 7 we directly see that for labeled graphs G, H, G L H implics homs( G) homs(F. H) for every F e LT We thus focus our attention on showing that G $ H implies the existence an F' CTxx k such that homs( F", G) homs( F", H).
As first step, we consider the logic C of first-order formulas with k variables and counting quantifiery over the signature that contains unary relation symbols U, for each label a in the vertex label alphabet M, and binary relation symbols E's for each label 8 in the edge label alphabet A. We add the superscript L here to distinguish from the usual use of Ck-1 for unlabeled graphs. Cai et al. (1992) famously showed that for graphs G, H we have G P = H = yp for all y Cx-1 if and only if G L L H. It is folklore that this also holds in the setting of labeled graphs. We in fact only need one direction here, namely if G ławr. H. then there a yp E C such that t= s and H y yp It is straightforward to verify that the original argument for this direction is unaffected by labels Cai et al. 1992 Theorem 5.4, case
-2).
In the rest of this section we will show that the existence of such formula & implies the existence of a labeled graph F' for which the homomorphism count into G and H differs. For this purpose we can adapt an argument by Dvorák (211)).
We first recall the key definitions from Dvoráá 2010). A k-marked labeled graph G a graph with a partial function marko [k] V(G). The set of active markings Mc is the subset of [k] for which mark is defined. Suppose that G, H are k-marked labeled graphs with MH s MH, we define homs( G, H) the number of those homomorphisms & that also preserve markings, i.e., where oi (i)) = mark;; (1) for each active marking i ε MG. A k-marked labeled quantum graph G is finite linear combination with real coefficients of k-marked labeled quantum graphs. We require all graphs in the linear combination to have the same set of active markings, which we refer as Mg. The function homs extended to the case where the first argument is k-marked labeled
*For a detailed definition of first-order logic with counting quantifiers refer to Cai ct al. 1992
'What we call k-marked here is referred to as k-labeled in (Dvorák (2010) and much of the literature. Unfortunately, this would clash with the other with our (also common) terminology for graphs with vertex and edge labels.
21

---

Published as a conference paper at ICLR 2024
quantum graph G aj as homs(G.H) Σf HH, The treewidth of quantum graph Σ, o,G is max (tw(G:) aq # 0
k-marked labeled quantum graph models a formula yp for graphs of size n if Mc consists of the indices of the free variables of (p, and for each labeled graph H on vertices with Mg = MH:
if H yp then homs(G, H) = 1, and
* if H # then homs(G, H) = O.
From here on we follow the same strategy as Dvorák, but require some changes correctly handle labeled graphs.
A product G2G₂ of two k-marked labeled graphs G1, G2 is constructed by taking the disjoint union of G1 and Gg. identifying the vertices with the same marking, and suppressing parallel edges with the same edge label. That is, we allow the product have self-loops and to have parallel edges with distinct labels. If there are vertices v é V (G1,, e V(22) with the same marking but different vertex labels (we say that G1, G2 are incompatible), the product is a single vertex with a self-loop (and arbitrary labels).
For quantum k-marked labeled quantum graphs G = E; ai, and G2 = =E; ag, G2.5 the product G G2 is defined as Σi,; Br,, The coefficient B., equals 0 is G1,,G2.5 is the empty graph, contains a loop or parallel edges with distinet labels, otherwise Brg = al, i022.- The motivation for this distinction in the coefficients 3rg is that if H is a labeled graph, then by definition it has no self-loops and any two vertices are connected only by one edge with one label, hence there can be no homomorphisms into H from product G1.G22. that produces such situations. Note that in the situation where G1.a; G2.j are incompatible at least one of G1.i, G2,5 must have 0 homomorphisms into H which is why we (ab)use the self-loop a failure state in this case. In particular, we have homs( G2, H) = homs (G1, H) homs (G2, H) for every labeled graph H. We write O for k-marked labeled quantum graph where all coefficients are zero
Lemma 25 (Labeled version of Lemma 6. (Dvorák, 2010). For each formula in to E C..1. and for each positive integer n, there exists labeled quantum graph G of treh-width at most k such that G models for labeled graphs of size n.
Proof. We construct inductively on the structure of sp The base cases significantly differ from those in the proof of (Dvorák] 2010 Lemma 6). However, once we have established the fact for the base cases, the inductive steps remain the same as they rely only on the property that homs(Gi G2, H) homs(G1, FC)mm(()) H), as discussed above, and technical lemma for quantum graphs (Dvorá 2010, Lemma 5) that is not affected by labels.
If o true, let G be the empty graph, if 4 false let G = 0. If = (x:)), let G be the graph with single vertex e with (i) = v and A(b)= =0.
If y x; Tij let G Eoer G. (the sum ranges over the elements of the vertex label alphabet) where G, is the k-marked labeled graph with a single vertex v. markg u and ((1)= a. For any specific k-marked H, the vertex marked as i and will have only one vertex label. Hence, there will be a homomorphism from exactly one Gs (where matches the label in H!) and there are 0 homomorphisms for all other germs of G.
maths (j)
If o Es J.)) there are two cases: if j. then let G == 0 as the predicate cannot be satisfied in a self-loop free H. If # j, let G E.,ore Go where G., is the graph with adjacent vertices and u, marked as i, and labeled with a, a', respectively, and x (v, u)) 5. As above, for any given H, one term of G will have 1 homomorphism into H, and the others will all have 0.
That is, for every base case we have shown that the appropriate k-marked labeled quantum graph exists. It is clear that in all the base cases the treewidth is 1. The rest of the induction proceeds exactly as in Dvorák] 2010
Lemma 6).
'Homomopphisms from quantum graphs can be seen as an alternative representation of graph motif parame- ters. Because of the two distinct natures of their uses in this paper and the disjoint connections to prior work we have decided not unify the presentation of these two concepts here.
22

---

Published as a conference paper at ICLR 2024
Proof of Lemmal 5 As discussed above, we have that for labeled graphs G.H. G F&WL H implies the existence of a Φ Ck+1 such that G &p and H # yp By Lemma 25 there is a k-marked labeled quantum graph F with treewidth at most k that models sp Hence, Σ, a, G) 0= = Σ: Oi h F; H), which means there must be some such that homs F; H) homs F; H) (recall that the linear combination is always finite). Since F has treewidth at most k, F; E LT and therefore G #CT H.
B.3 ON LEMMA FOR LABELED GRAPHS
Seppelt 2023) originally showed Lemma for unlabeled graphs. Here we briefly note why the lemma holds unchanged in the labeled case. particular, the lemma relies on three facts.
First, that homs F, G2 x Go) homs G1),ooo)sms Gz). Where is the direct product defined in (Lovász 1967).
2. Second, that the matrix (homs( K, L)) K,LEC invertible, where C, is the class of all graphs with at most vertices.
3. And finally, that if G= H, then also G K =F H x K for all graphs K.
The first two points are classic results Lovászz 1967). which were originally shown for all relational structures. They thus hold unchanged also for labeled graphs. For the final point, recall that G = H means that for every F e F we have homs( F; G) homs(F, H). Then by the first point also homs(F, F, G x K) = homs( F, G)homs(FF K) = homs(F, H) Hommss(HF F, K) = homs F, H K).
C PROOF OF THEOREM g
This section will make some slight departures from the terminology used in the main body of the paper. For more focused presentation, we will first discuss the case for unlabeled graphs and afterwards show how to additionally handle labels afterwards. In the main body, the Spasm of graph was defined as the set of all homomorphic images, but here it will be simpler to take an alternative (equivalent) perspective.
quotient G/T of a graph G is obtained by taking a partition 7 of ((G) and constructing the graph like G but with all vertices in the same block of r identified. That is, the vertices of are the blocks of т, and the incidence of a vertex in G/a is the incidence of all vertices in the corresponding block of the partition. It is standard observation that the set of all quotients of G without self-loops is precisely Spasm(G) (G) (see, e.g.. e.g..( Curtticapan et al. (2017)) will be convenient to also consider the set of all quotients of G, i.e., including those with self-loops, which we will refer to as Spasm".
The arguments of this section will revolve around formulas of monadic recond-order logic (MSO). That is, formulas of first-order logic that additionally allow for quantification over unary predicates. For formal definition see, e.g., (Courcelle) 1990).
We will decide the treewidth of graphs by deciding whether they contain certain other graphs as minors. To that end first define the notion of minors formally.
Definition 1. A minor model from H into G, is a mapping f: (H) + (G) such that:
Vu VEH)) f(u) n f(v)=
2. Vue V(H) G[f(v)] is connected, and
3. (u,v) (HH) there is edge (in G) between some vertex in f(u) and some vertex in f(v).
We say that is minor of G is there a minor model from H into G.
Checking whether graph H a minor of graph G via an MSO formula is a standard construction. Interestingly, to check whether H is minor of some quotient of G is simpler, at least in terms of formulating the question in MSO. The key insight here that the second condition minor models effectively be ignored, since there will always be quotient where all vertices of G[[(v) are
23

---

For the other direction now assume that the formula holds. Let 7x be the partition of V(G) induced by some satisfying choices of ,,,,..,,, (any vertex e not in any of these sets corresponds to a singleton {v} in the partition). Consider the graph G/Tx and let us refer to the vertex corresponding Published as a conference paper at ICLR 2024
identified. Instead, it is enough to guarantee that the image is non-empty. In concrete terms, to check whether H is a minor of a graph in Spasm" e (G) we will use the following MSO formula.
QuotMinor H EXI, X. (V)) (AIX) -
E X, By
E(G)))
Intuitively, the sets X, correspond to the image of the minor model for vertex vs in H. The minor is of the quotient T where т extends the disjoint sets X ,,,...,,, by the singletons {v} for all v V(G) but not in any X, for i [c].
Lemma 26. Let G and H be graphs. Then H is a minor of a quotient G/T Spasm² if and only if G= QuotMmor 11-
Proof. Suppose H is a minor of G/T and let h be the respective minor map from H into G/T. Let be the edge surjective endomorphism (i.e., the homomorphic image) from G into G/T induced by the quotient (i.e., every vertex maps to the block in that contains the vertex). Let refer to the vertices of H as U1,..., Cc. The formula is satisfied when for every i <[c]. the second-order variable X; is assigned {w e V(G) j(w))& [(;)), that is, all vertices in G that are mapped by je to vertices in f(u)). Clearly, the sets X; are disjoint, as the images of f are disjoint. Furthermore, we know by assumption that of is a minor model that for every Uy, E (HH), there least one edge {a. b) with a E f(v)), be f(u;). Since is edge surjective, there are a', b' X, such that {a', b) E(G) and p(aa) = a, (()) =
to the block defined by X; as u, We claim that f:u; +> {ur} is a minor model of H into G/Tx- Condition 1 and 2 of minor model are trivially satisfied. For Condition 3, observe that if there is an edge (,, 8y) E EH)) but no edge (u, u E(G/Tx)) then there can be no x E X2, y E X3 that have edge between them in F.G)), hence contradicting the satisfaction of the final block of conjuncts in QuotMinor
L
We can resolve the possibility of self-loops with a simple observation about minors of quotient graphs. A self-loop occurs in quotient G/T if there is block B of that contains adjacent vertices W.l.o.g., assume for now that v, u are the only adjacent vertices B. If H is minor of G/r, is also a minor of G/T' where r' is like T but with as singleton rather than in B. The vertex for {u} in G/7' will be adjacent to the vertex for block B' = B < {u). Contracting the vertices for B' and {u} will produce exactly G/T without the self-loop B. Iterating this idea shows that G/T without self-loops is a minor of some loop-fres free quotient of G.
Proposition 27. Let be a graph and let H be a loop-free graph. Suppose H is a minor of some graph in Spasm (G). Then H is minor of some graph in Spasm.
Robertson and Seymour famously showed that the graph minor relation is a well- ordering.... Together with the classic observation that any well-quasi-ordering has finite set of minimal elements this leads to the following standard result.
Theorem 28 (Robertson & Seymour (2004)). For every minor closed class of graphs P, there exists finite set of graphs F such that G P if and only if no F F is a minor of G.
Theorem 29. Deciding max(tw(F) | F Spasm (G)} {pasm(G)} 2 k is feasible in Exed-parameter linear time when parameterised by and linear time for fixed kt
Proof. We first check whether tw (G) k 1. It is well known that this can be decided in linear time for fixed i (Bodlaender 1996). If not, then tw( ()) 2 l and the algorithm returns true.
The property of having treewidth at most & 1 is closed under graph minors. By Theorem 28 there exists a finite set F of forbidden minors for class of graphs with treewidth at most & - 1. Furthermore, the set F depends only on the parameter k. Thus, have that graph H has treewidth 2 A iff it does
24

---

Published as a conference paper at ICLR 2024
not have treewidth k 1 iff it has some graph of IF minor. Combining with Proposition 27 can therefore decide whether the treewidth the spasm at least k. by checking for every E whether F is minor of any quotient of G. According to Lemma 26 this is equivalent checking whether the formula
V QuotMinor
satisfied by G. By Courcelle's Theorem (Courcelle 1990) we can decide G @ in time f(k, ()) where & is the treewidth of G. Since yp depends only on k this is equivalent to f(k) |G] and hence polynomial for fixed k.
As final note we wish to point out that this result primarily of theoretical interest. For most practical pattern sizes, naive enumeration of Spasm and checking the treewidth individually with state-of-the-art systems for treewidth computation feasible. The bottleneck practice the size of the pattern, as enumerating the contents of Spasm via naive methods, e.g., enumerating all partitions, becomes challenging above vertices (see Sequence A000110 the On-Line Encyclopedia of Integer Sequences (OEIS Foundation Inc. (203)).
Adding Labels We finally discuss the necessary changes for labeled graphs in the above argument, from which Theorem 8 then follows immediately. By definition, treewidth of labeled graphs is unaffected by the labels. As such we can simply ignore labels in checking for minors. Where the labels make a difference however, is in the set Spasm itself. Not all loop-free quotients are homomorphic images in the labeled case, but rather we require an additional restriction.
quotient G/T will not be homomorphic image labeled graphs in two cases. First, if block of contains two vertices with different vertex labels, and second, if the quotient would create parallel edges with different labels. To lift the previous argument to the labeled case is therefore enough to enforce these two extra conditions in the QuolMinorp formulas. To this end, recall that in satisfying interpretation of the formula, the sets X, correspond precisely to the non-trivial blocks of the quotient for which F is minor. The two extra restrictions then be enforced simply by conjunction with the following two formulas formula inside the scope second order quantification (where Σ, A the vertex- and edge-label alphabets, respectively).
A V Vz X; (1)
(8)
3r 32 E X; By1, U/2 E Xj ' E=j
V
V (x1,01) EE(G)) A U2) ( E (G)
(9)
8,8'ca
The term in is easy to interpret, every block X, of the partition must have uniform vertex labels. The term states that there are no two blocks X,, X, such that there are edges with two different edge labels between the blocks, i.e., it is not the case that the quotient will have parallel edges with different labels. Relation E in the original definition of QuolMinor can trivially be replaced by the disjunction over all edge-label relations. Thus can easily adapt our argument above to also decide the existence of minor models in Spasm of a labeled graph.
25


Reviews:
[{"review_id": "lWCLxX6puA", "reviewer": "Reviewer_kH24", "summary": "The connection between the WL algorithm and the expressive power of GNNs is well-established in GNN literature. The paper conducts a theoretical study of the power and limitations of k-WL algorithm in context of counting patterns in graphs, more generally graph motif parameters. The authors provide a precise characterization of which labeled graph motif parameters are determined by the k-WL type of a graph. Some of these results concern induced versions of subgraph counting. Finally, the authors give a polynomial time algorithm that given a pattern P finds the minimum k such that k-WL determines P-counts.", "questions": "1) Comment: Typically in homomorphism literature, a \"labeled graph\" refers to a graph with certain vertices marked with labels 1,...,k. That is, a k-labeled graph comes along with a mapping $\\ell:[k] \\to V(G)$. This is different from the more general notion considered in the paper. It would be advisable to make this distinction somewhere in the paper for readability across communities.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper is a neat collection of results on pattern counting, which should be useful to the GNN community. The paper is extremely well-written and the exposition is very structured.", "weaknesses": "I am not convinced so much with the novelty of results, especially in light of the recent results such as Neuen (2023). The contributions are kind of incremental in my opinion. It would have been useful to have some experimental work to accompany the paper: e.g. Is it harder to compute labeled patterns using GNNs, instead of unlabeled patterns? Or perhaps, the performance of models using random node initialization could be explained by the ability of GNNs to count labeled patterns?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "IyEVNXUudY", "reviewer": "Reviewer_p7nS", "summary": "This work studies the Weisfeiler-Leman dimension of graph motif parameters for labeled graphs, i.e. the size of $k$ needed for $k$WL to distinguish these parameters. They show that this is exactly the maximum treewidth of the graphs in the support of the parameter. This solves several problems left open or unaddressed in recent work.", "questions": "Perhaps results from permutation-invariant function representation can be used to give a simpler proof of Theorem 6? It is known that multiset functions $f$ can be sum-decomposed in certain situations. For instance, [Zaheer et al. 2017] show that continuous permutation invariant functions $f$ from $[0, 1]^n \\to \\mathbb{R}$ (which can be viewed as functions on multisets of $n$ elements) can be written as $f(X) = \\rho( \\sum_{i=1}^n \\phi(X_i))$ for some continuous functions $\\rho$ and $\\phi$. This motivates the common form of \"readout\" functions in GNNs, i.e. permutation invariant functions mapping from $k$-tuple representations to a single representation for the graph. In fact, from previous work I would already expect to see a result like yours; it is unclear whether your result is useful for practical GNNs, since one would already build a readout function in this form.\n\n\nNotes:\n1. Typo: \"graph motif parameter by $ind_H$\" on page 5\n2. Typo: \"counting counting\", \"of of\" on page 8", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Uses results from, extends, and solves unsolved problems from very recent work on kWL and graph motif parameters.\n2. Strong, elegant, general result on graph motif parameters, which allows application to many graph problems of interest, such as induced subgraph counting.\n\nDue to these nice and timely theoretical results, I recommend acceptance of the paper.", "weaknesses": "1. Hard to understand introduction of first-order logic concepts\n2. Unclear utility of results in machine learning: see questions section for notes on Section 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "5i2UDvNjns", "reviewer": "Reviewer_2nvm", "summary": "This paper studies the power of the k-Weisfeiler-Lehman (k-WL) algorithm for the natural and fundamental task of computing graph motif parameters (a weighted combination of subgraph counts). The motivation for studying the k-WL test is the connection to the expressive power of graph neural networks (GNNs).\n\nBuilding on recent results for unlabeled graphs, this paper characterizes the class of graph motifs that can be computed by the k-WL test for labeled graphs (i.e., with edge and vertex labels). A central quantity is the WL-dimension of the graph motif parameter $\\Gamma$, which is the smallest $k$ for which a k-WL test returns distinct outputs for graphs which induce distinct values of $\\Gamma$. In Theorem 2, the authors show that the WL-dimension of $\\Gamma$ is equal to the maximum treewidth of any of the subgraphs in the support of $\\Gamma$. In Theorem 6, the authors show that the result of the WL test can be used to compute the value of $\\Gamma$ as well (alone, the $k$-WL can only distinguish between different values of $\\Gamma$). In their final set of results, the authors turn to the more specific question of subgraph counting. Theorem 8 shows that it can be determined whether a labeled graph has WL-dimension at most $k$ in polynomial time. Proposition 9 examines the popular task of counting graphlets, and shows that counting k-graphlets has WL-dimension k - 1.", "questions": "- Is $homs(F_i, G)$ defined somewhere?\n- In the definition of tree decomposition on page 5, do you mean to write $\\{u,v \\} \\subseteq \\alpha(t)$?\n- Is there any quick intuition for why treewidth is the right determinant of the WL-dimension?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This work extends recent results on the $k$-WL algorithm to the setting of labeled graphs. This is an important conceptual extension, as many graphs do have additional information that can be taken into account for learning tasks. Technical details are clear and seem correct. \n\nThe authors' results have clear implications for the ability of GNNs to compute subgraph counts. Together, Theorems 2, 6 and 8 show that one can determine an appropriate value of $k$ in polynomial time for the motif-counting task at hand, and can then compute it using a modification of the k-WL test. This is quite useful and may impact how one designs GNNs for these kinds of tasks.", "weaknesses": "- The novelty of this work isn't clear to me. While the extension to labeled graphs is well-motivated, the results and techniques seem to be obtained by simple / straightforward extensions of recent work for unlabeled graphs. Can you describe what the key roadblocks and innovations are in this setting? This would make it easier to judge the contributions of this work.\n- No numerical experiments, but given that this is a theoretical paper, this is only a mild weakness. \n- What are the implications for GNN design for various tasks, based on the results in your paper? These are only hinted at, but given the audience of this paper, it would be worthwhile to have some discussion about it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "H9Pifugl21", "reviewer": "Reviewer_Jgdr", "summary": "The WL test for graph isomorphism is an iterative message-passing-like process on a graph, where in each round the nodes share structural information accumulated in previous rounds with their adjacent nodes. In recent years it has been studied in connection to the expressibility of graph neural networks. This paper studies the higher dimensional variant k-WL, where instead of nodes the information is passed between k-tuples of nodes. This variant has been associated with \"higher-order GNNs\", a generalization GNNs where correspondingly, messages are passed between sets of nodes. The paper is theoretical and proves some results about the \"WL dimension\" of graph substructures, which is the smallest k such the k-WL test can distinguish between graphs that have a different number of copies of that substructure. The results concern to variants like induced versus non-induced substructures, whether the number of copies can be computed, and whether the WL dimension of a substructures can be computed efficiently.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The WL test has gotten a lot of focus in the DL community due to its connections to GNN, and this line of literature is by now standard in the ICLR community, and this paper furthers this line of research by proving additional new results.", "weaknesses": "This seems generally like a combinatorics paper and it corresponds mostly with the combinatorics and not the ML literature. The connection between WL and GNNs is well-established by now, but the direction taken in this paper does not seem directly relevant to GNNs, but rather related mostly indirectly just due to generally being about WL. There is only fleeting reference to why any of the questions studied here bear on GNNs (and even then they concern the rather niche \"higher-order\" k-GNNs and not standard GNNs). Even though it is in scope for GNN-related venues and particularly ICLR, it is not all that clear that ICLR is where this paper would actually find its interested readership.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)