Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
Authors: Bohang Zhang
Jingchu Gai
Yiheng Du
Qiwei Ye
Di He
Liwei Wang
Venue: ICLR 2024 oral (2024)
Keywords: Graph Neural Networks
Expressive Power
Homomorphism
Subgraph Counting
Weisfeiler-Lehman
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Designing expressive Graph Neural Networks (GNNs) is a fundamental topic in the graph learning community. So far, GNN expressiveness has been primarily assessed via the Weisfeiler-Lehman (WL) hierarchy. However, such an expressivity measure has notable limitations: it is inherently coarse, qualitative, and may not well reflect practical requirements (e.g., the ability to encode substructures). In this paper, we introduce a novel framework for quantitatively studying the expressiveness of GNN architectures, addressing all the above limitations. Specifically, we identify a fundamental expressivity measure termed homomorphism expressivity, which quantifies the ability of GNN models to count graphs under homomorphism. Homomorphism expressivity offers a complete and practical assessment tool: the completeness enables direct expressivity comparisons between GNN models, while the practicality allows for understanding concrete GNN abilities such as subgraph counting. By examining four classes of prominent GNNs as case studies, we derive simple, unified, and elegant descriptions of their homomorphism expressivity for both invariant and equivariant settings. Our results provide novel insights into a series of previous work, unify the landscape of different subareas in the community, and settle several open questions. Empirically, extensive experiments on both synthetic and real-world tasks verify our theory, showing that the practical performance of GNN models aligns well with the proposed metric.

Published as a conference paper at ICLR 2024
BEYOND WEISFEILER-LEHMAN, A QUANTITATIVE FRAMEWORK FOR GNN EXPRESSIVENESS
Bohang Zhang!-i Jingehu Gai Yiheng Duu Qiwei Ye* Di He
Liwei Wang! 15m
National Key Laboratory of General Artificial Intelligence, SIST, Peking University School of Mathematical Science, Peking University *Yuanpei College, Peking University
"Beijin Academy of Artificial Intelligence CCenter for Machine Learning Research, Peking University zhangbchangepku. en, {saijingehu duy cuyiheng/ sesengeestu...... pku. edu.en ewyclbaai ac. on, {dihe, wanglw/8pku. cdu. on
ABSTRACT
Designing expressive Graph Neural Networks (GNNs) is a fundamental topic in the graph learning community. So far, GNN expressiveness has been primarily assessed via the Weisfeiler-Lehman (WL) hierarchy. However, such an expressiv- ity measure has notable limitations: it is inherently coarse, qualitative, and may not well reflect practical requirements (e.g., the ability to encode substructures). In this paper, we introduce novel framework for quantitatively studying the ex- pressiveness of GNN architectures, addressing all the above limitations. Specif- ically, we identify fundamental expressivity measure termed homomorphism expressivity, which quantifies the ability of GNN models to count graphs under homomorphism. Homomorphism expressivity offers complete and practical as- sessment tool: the completeness enables direct expressivity comparisons between GNN models, while the practicality allows for understanding concrete GNN abili- ties such as subgraph counting. By examining four classes of prominent GNNs case studies, we derive simple, unified, and elegant descriptions of their homomor- phism expressivity for both invariant and equivariant settings. Our results provide novel insights into a series of previous work, unify the landscape of different sub- areas in the community, and settle several open questions. Empirically, extensive experiments on both synthetic and real-world tasks verify our theory, showing that the practical performance of GNN models aligns well with the proposed metric.
INTRODUCTION
Owing to the ubiquity of graph-structured data in numerous applications, Graph Neural Networks (GNNs) have achieved enormous success in the field of machine learning over the past few years. However, one of the most prominent drawbacks of popular GNNs lies in the limited expressive power. In particular, Morris et al. (2019); Xu et al. (2019) showed that Message Passing GNNs (MPNNs) are intrinsically bounded by the I-dimensional Weisfeiler-Lehman guishing non-isomorphic graphs (Weisfeiler Lehman, 1968). Since then, the Weisfeiler-Lehman hierarchy has become a yardstick to measure the expressiveness and guide designing more powerful GNN architectures (see Appendix A.I for an overview of representative approaches in this area).
test (1-WL) in distin-
However, as more and more architectures have been proposed, the limitations of the WL hierarchy are becoming increasingly evident. First, the WL hierarchy is arguably too coarse to evaluate the expressive power of practical GNN models (Morris et al., 2022; Puny et al., 2023). On one hand, architectures inspired by higher-order WL tests (Maron et al., 2019b;a; Morris et al., 2019) often suffer from substantial computatioo//memory costs. On the other hand, most practical and efficient GNNs are only proved to be strictly more expressive than 1-WL by leveraging toy example graphs (e.g., Zhang& & Li, 2021; Bevilacqua et al., 2022; Wijesinghe & Wang, 2022a). Such a qualitative characterization may provide little insight into the models' true expressiveness. Besides, the ex- pressive power brought from the WL hierarchy often does not align well with the one required in practice (Veličković, 2022). Hence, how to study the expressiveness of GNN models in a quantita- tive, systematic, and practical way remains central research direction for the GNN community.
"Equal technical contributions.
Project lead.

---

Published as a conference paper at ICLR 2024
To address the above limitations, this paper takes a different approach by studying GNN expressivity from the following practical angle: What structural information can a GNN model encode? Since the ability to detect/count graph substructures is crucial in various real-world applications (Chen et al., 2020; Huang et al., 2023; Tahmasehi et al., 2023), many expressive GNNs have been proposed based on preprocessing substructure information (Bouritsas et al., 2022; Barceló et al., 2021; Bodnar et al., 2021b;a). However, instead of augmenting GNNs by manually preprocessed (task-specific) substructures, it nowadays more desirable to design generic, domain-agnostic GNNs that can end- to-end learn different structural information suitable for diverse applications. This naturally gives rise to the fundamental question of characterizing the complete set of substructures prevalent GNN models can encode. Unfortunately, this problem is widely recognized as challenging even when examining simple structures like cycles (Fürer, 2017; Arvind et al., 2020; Huang et al., 2023).
Our contributions. Motivated by GNNs' ability to encode substructures, this paper presents a novel framework for quantitatively analyzing the expressive power of GNN models. Our approach is rooted in a critical discovery: given GNN model M, the model's output representation for any graph G can be fully determined by the structural information of G over some pattern family J=M where FM corresponds to precisely all (and only) those substructures that can be "encoded" by model M. In this way, the set JrM can be naturally viewed as an expressivity description of M: after identifying FM for each model M, the expressivity of different models can then be qualita- tively/quantiativelyy compared by simply looking at their set inclusion relation and set difference.
The crux here is to define appropriate notion of "encodability" so that FM can admit simple description. We identify that a good candidate is the homomorphism expressivity: i.c., JrM i.e., of all substructures that can be counted by model M under homomorphism (see Section 2 for formal definition). Homomorphism is a foundational concept in graph theory (Lovász, 2012) and linked many important topics such as graph coloring, graph matching, and subgraph counting.
consists
With this concept, we are able to give complete, unified, and surprisingly elegant descriptions of the pattern family FrM for a wide range of mainstream GNN architectures listed below:
MPNN (e.g., Gilmer et al., 2017; Hamilton et al., 2017; Kipf & Welling, 2017; Xu et al., 2019);
Subgraph GNN (You et al., 2021; Zhang & Li, 2021; Bevilacqua et al., 2022; Qian et al., 2022);
Local GNN (Morris et al., 2020; 2022; Zhang al., 2023a; Frasca et al., 2022);
Folklore-type GNN (Maron et al., 2019a; Zhang et al., 2023a; Feng et al., 2023).
Technically, the descriptions are based on a novel application and extension of the concept of nested ear decomposition (NED) in graph theory (Fppstein, 1992). We prove that: (i) (necessity) each model M above can count (under homomorphism) a specific family of patterns JFM, characterized by a specific type of NED; (ii) (sufficiency) any pattern F ş F.M cannot be counted under homomor- phism by model M; (iii) (completeness) for any graph, information collected from the homomor- phism count in pattern family JFM determines its representation computed by model M. Therefore, homomorphism expressivity is well-defined and is a complete expressivity measure for GNN models.
Our theory can be generalized in various aspects. One significant extension is the node-level and edge-level expressivity for equivariant GNNs (Azizian & Lelarge, 2021; Geerts & Reutter, 2022), which can be naturally tackled by a fine-grained analysis of NED. As another non-trivial generaliza- tion, we study higher-order GNN variants for several of the above architectures and derive results by defining higher-order NED, Both aspects demonstrate the flexibility of our proposed framework, suggesting it as a general recipe for analyzing future architectures.
Implications. Homomorphism expressivity serves powerful toolbox for bridging different sub- areas in the GNN community, providing fresh understandings of a series of known results that were previously proved in complex ways, and answering a set of unresolved open problems. First, our results can readily establish a complete expressiveness hierarchy among all the aforementioned ar- chitectures and their higher-order extensions. This recovers and extends a number of results in Morris et al. (2020); Qian et al. (2022); Zhang et al. (2023a); Frasca et al. (2022) and answers their open problems (Section 4.). In fact, our results go far beyond revealing the expressivity gap be- tween models: we essentially answer how large the gap is and establish a systematic approach to constructing counterexample graphs. Second, based on the relation between homomorphism and subgraph count, are able to characterize the subgraph counting power of GNN models for all patterns at graph, node, and edge levels, significantly advancing an open direction initiated in Fürer (2017); Arvind et al. (2020) (Section 4.2). As special case, our results extend recent findings in
2

---

Published as a conference paper at ICLR 2024
Huang et al. (2023) about the eycle counting power of GNN models, highlighting that Local 2-GNN can already subgraph-count all cycles/paths within nodes (even at edge-level). Third, our results provide a new toolbox for studying the polynomial expressivity proposed recently in Puny et al. (2023), extending it to various practical architectures and answering an open question (Section 4.3). Empirically, an extensive set of experiments verifies our theory, showing that the homomorphism expressivity of different models matches well with their practical performance in diverse tasks.
2 PRELIMINARY
Notations. We use } and H. It to denote sets and multisets, respectively. Given a (multi)set S, its cardinality is denoted as |S]. In this paper. we consider finite, undirected, vertex-labeled graphs repeated edges. Let G = (Va, Ea, lG) be graph with vertex set Va. edge
with no self-loops set Ec, and label function fg. where each edge in Eg is set {u, C VG of cardinality two, and (a(u) is the label of vertex u. The rooted graph GH is graph obtained from G by marking the special vertex u E VG: we can similarly consider marking two special vertices u, U. E Va (denote by GWv). The neighbors of vertex is denoted as No (u) == fo E Va- {u, v) E Ea]. A graph & C Vo. EF C Ec, and ( = la(u) for all u E Vp- F (VF, E5, is a subgraph of G Vp
A simple path P in G is an edge set of the form { {wo, wi w....... {wx-1, 1, w C Eg where w; A wi for all + j. Here, Wi and WP are called endpoints of P and other vertices are called internal points.
Homomorphism, isomorphism, and subgraph count. Given two graphs F and G, ho- momorphism from F to G is mapping f Vp + VG that preserves edges and labels, i.c., (r(u) (f))) for all u E Vp, and {f(u), f(v) E EG for all {u, v) E Ep. When the mapping If exists, we say F is homomorphic to G. We denote by Hom F, G)) the set of all homomorphisms from F G and define hom F, G) = |Hom (F,(F))))) which counts the number of homomorphisms for pattern F in graph G. If f is further surjective on both vertices and edges, we call G homomorphic image F. Denote by Spasm(F) the set of all homomorphic images of F, called the spasm of F. For rooted graphs, homomorphism should additionally preserve vertex marking: ie., if f is a homomorphism from F" to Gm,, then f(u)= = x and f(v) = y-
A mapping f VF- - VG is called an isomorphism if is bijection and both ff and its inverse f-1 are homomorphisms. We denote by Sub(F, G) the set of all subgraphs of G isomorphic to F and define sub( F, G) Sub F, G)J, which counts the number of patterns F occurred in graph G as subgraph. We note that a similar definition holds for rooted graphs (e.g., sub(F"', G)
under isomorphism. To achieve such invariance, most popular GNN models follow a color refine- Graph neural networks GNNs can be generally described graph functions that are invariant
ment (CR) paradigm: they maintain feature representation (color) for each vertex vertex tuples and iteratively refine these features through equivariant aggregation layers. Finally, there is a global pooling layer to merge all features and obtain the graph representation. Below, we separately detine the corresponding CR algorithms for four mainstream classes of GNNs studied in this paper.
MPNN. Given a graph G, MPNN maintains a color MP (u) for each vertex u E Va. Initially,
the color only depends on the vertex label, i.e., XG
MM,(()) (u) la(u). Then, in each iteration, the color is refined by the following update formula (where hash is a perfect hash function): MP.(()
XG
MP.(t)) MP,(++1) (u) hash (xe (MP.()(())) (u), fxxe
(v) (0)) u E No(u)))
(1)
After a sufficient number of iterations, the colors become stable. We denote by XM (u) the stable color of u, which is also the node feature of u computed by the MPNN. The graph representation is defined as the multiset of node colors, i.c., XG (G) X MP (u) u E Vo MP
Subgraph GNN. It treats a graph G
set of subgraphs G : E Val., each obtained from G by marking a special vertex u E VG- Subgraph GNN maintains a color Sub (u, v) for Sub,(0) each vertex v in graph G Initially, XG (u, v) (Lo(v), I/u = e)). where the latter term distinguishes the special mark. It then runs MPNNs independently on each graph G":
Sub, Sub,(++1) (u, v) hash [xa
Sub.(t) (u, v), fxx
(t), Sub,,()) (u, w) : w E No(v)
XG
(2)
Denote the stable color of vu as X Sub v). The node feature of u computed by Subgraph GNN is defined by merging all colors in G i.e., XSub (u) == hash (UxSxb(er (u, v) v E VoB). Finally, the graph representation is defined xa (G) = (XS.t (w) E Vol.
3

---

Published as a conference paper at ICLR 2024
Local GNN. Inspired by the k- LL test (Grohe, 2017), Local k-GNNN is defined by replacing all global aggregations in k- WL by sparse ones that only aggregate local neighbors, yielding much more efficient CR algorithm. As example, the iteration of Local 2-GNN has the following form and enjoys the same computational complexity as a Subgraph GNN.
L
(u, - XG (u, v), (xx"(w: ee: EN( B. Mxx (x, w): :))
XG
Initially, XG (u, v) = (la(u), (c(v), Mu = v), u[ E Eal). which is called the isomor- (1,
phism type of vertex pair (u, v)). We similarly denote the stable color as xa u) and define
the node feature (x) and graph representation (G) as in the Subgraph GNN.
Folklore-type GNN. The Folklore GNN (FGNN) is inspired by the standard k-FWL test (Cai et al., 1992). As an example, the iteration formula of 2-FGNN written as follows:
XG (,(++) (u, v) hash
(.()) (u, u), [(G F.(t) (w, v), XG (XG
F.(() (u, w)) w VVB)..
(4)
One can similarly consider the more efficient Local 2-FGNN by only aggregating local neigh- bors, which has the same computational complexity as Local 2-GNN and Subgraph GNN:
(F.(++1) (u, v) - hash XG (F.(() (u, v), [[GG (F. (w, (w, XG (F.(t) (u, w)) E NN(
XG
(5)
The stable color, node feature, and graph representation can be similarly defined.
Finally, we note that the latter three types of GNNs can be naturally generalized into higher-order variants. We give a general definition of all these architectures in Appendix 1. For the base case k = 1, Subgraph (k- I)-GNN, Local k-GNN, and Local k-FGNN all reduce to the MPNN.
HOMOMORPHISM EXPRESSIVITY OF GRAPH NEURAL NETWORKS
3.1 HOMOMORPHISM EXPRESSIVITY
Given GNN model M and a substructure F, we say M can count graph F under homomorphism if, for any graph G. the graph representation X (G) determines the homomorphism count hom (F, G)- In other words, MM (G) X (H) implies hom(F, central question studied in this paper is, what substructures F can GNN model M count under homomorphism? This gives rise to the notion of homomorphism expressivity defined below:
hom (F H) for any graphs G, H. The
Definition 3.1. The homomorphism expressivity of a GNN model M, denoted by J_M is family of (labeled) graphs satisfying the following conditions!:
M a) For any two graphs G, H, XG (G) = XH (H) iff hom G) hom H) for all F E FM; FM is maximal, i.e., for any graph F & FM, there exists pair of graphs G, H such that x (G) = xM (H) and hom F. G) o (F,(F,F H).
Example 3.2. As simple example, consider a maximally expressive GNN M that can solve the graph isomorphism problem, i.e., it computes the same representation for two graphs iff they are isomorphic. Then, JM contains all graphs. This is classic result proved in Lovász (1967).
The significance of homomorphism expressivity can be justified in the following aspects. First, it is a complete expressivity measure. Based on item (a), the homomorphism count within JFM essen- tially captures all information embedded in the graph representation computed by model M. This contrasts with previously studied metrics such as the ability to compute biconnectivity properties (Zhang et al., 2023b) or count cycles (Huang et al., 2023), which only reflects restricted aspects of expressivity. Second, homomorphism expressivity is a quantitative measure and is much finer than qualitative expressivity results obtained from the graph isomorphism test. Specifically, by item (a), GNN model M, is more expressive than another model M2 in distinguishing non-isomorphic graphs iff MM c F.M, Furthermore, by item (b), M2 is strictly more expressive than M2 iff FM2 ç J.M, and the expressivity gap can be quantitatively understood via the set difference JMM (TM2,
Consequently, by deriving which graphs are encompassed in the graph family JrM homomorphism expressivity provides a novel way to analyze and compare the expressivity of GNN models. In the next subsection, we will give exact characterizations of JM for all models M defined in Section 2.
While homomorphism expressivity exists for all common GNNs such as the ones in Section 2, we note that it may he well-defined for certain pathological GNNs. See Appendix F.1 for deep discussion it.
4

---

Published as a conference paper at ICLR 2024
(b) Examples of whwaraarrrrrrrooaloossss-----se sarrr///lmoossstoooggeeeeerr NED Figure I: Illustration of NED and its variants. The number j next to each edge indicates that the edge
(a) Illustration of NED
belongs to the ear P,. Different colors represent different ears. See Figure 9 for more examples.
3.2 MAIN RESULTS
To derive our main results, we leverage concept in graph theory known nested ear decomposition (NED), which originally introduced in Eppstein (1992). Here, we adapt the definition as follows:
Definition 3.3. Given graph G, NED P is a partition of the edge set Eg into a sequence of simple paths Pi. Pm (called ears), which satisfies the following conditions:
Any two ears P. and Pj with indices 1 <i<> S e do not intersect, where is the number of connected components of G.
For each ear P, with index > there is an ear P; with index 1 S i < j such that one two endpoints of Pj lie in ear P, (we say P; is nested on P,). Moreover, except for the endpoints lying in ear P;
other vertices in P, are in any previous ear Pk for I k < j. If both endpoints of P3 lie in P; the subpath in P. that shares the endpoints of Pj is called the nested interval of Pj in P,, denoted as / (P3)) C P.. If only one endpoint lies in P., define I(P;) 0.
For all ears Pj. Pk with < < k S m, either I(2)) (PP)) = 0 or ((2)) C ((P)).
Intuitively, Definition 3.3 states that the relation between different ears forms forest, in that each ear is nested on its parent. Moreover, the nested intervals either do not intersect or have inclusion relations for different children of the same parent ear. We give illustrations of NED in Figure 1.
In this paper, we considerably extend the concept of NED to several variants defined below:
Endpoint-shared NED: NED is called endpoint-shares if all ears with non-empty nested intervals share a common endpoint (see Figure 1(b,1)).
Strong NED: a NED is called strong if for any two children Pj. Pk (j < k) nested on the same parent ear, we have (P,) C [(Ps) (see Figure 1(b,2)).
Almost-strong NED: a NED is called -ttoot for any children P,. Pk (j k) nested on the same parent ear and [(())) 1 > 1, we have I(P;) c I(Px) (see Figure 1(b,3)).
We are now ready to present our main results:
Theorem 3.4. For all GNN models M defined in Section 2, the graph family F.M satisfying Defini-
tion 3.1 exists (and is unique). Moreover, each FM can be separately described below:
.PPN: JMP = {F : F is a forest);
Subgraph GNN: Sub = {F F has an endpoint-shared NED);
Local 2-GNN: FL {F F has a strong NED);
Local 2-FGNN: JLF = {F: F has almost-strong NED);
2-FGNN: JF [FF: FF has a NED).
Theorem 3.4 gives a unified description of the homomorphism expressivity for all popular GNN models defined in Section 2. Despite the elegant conclusion, the proof process is actually involved and represents a major technical contribution, so we present a proof sketch below. Our proof is divided into three parts, presented in Appendices C.2 to C.4. First, we show the existence of JrM for each model M based on a beautiful theory developed in Dell et al. (2018). Using the technique of unfolding tree, we prove that J.M least contains all graphs F that allow specific type tree decomposition (Diestel. 2017), and the homomorphism information of these graphs determines the representation of any graph G computed by M (i.e., Definition 3. (a) holds). However, characteriz- ing JM in terms of tree decomposition is sophisticated and not intuitive for most models M. In the next step, we give an equivalent description of J.M based on novel extensions of NED proposed in Definition 3.3, which is simpler and more elegant. In the last step, we prove that J. does not con- tain other graphs. This is achieved by building non-trivial relations between three distinct theoretical tools: tree decomposition, pebble game (Cai et al., 1992), and Fürer graph (Fürer, 2001). Through fine-grained analysis of the Fürer graphs expanded by F & JMM (see Theorems C.47 and C.53), we show they are precisely a pair of graphs satisfying Definition 3b), thus concluding the proof.
5

---

Published as a conference paper at ICLR 2024
Discussions with Dvořák (2010); Dell et al. (2018). Our work significantly extends beautiful theory developed in Dvořák (2010); Dell et al. (2018), which showed that a pair of graphs G. H indistinguishable by 1-WL iff hom(F, G) hom(F, H) for all trees F, and more generally, they are indistinguishable by k-FWI. iff hom G) = hom(F, H) for all graphs F of bounded treewidth k. In this paper, we successfully generalize these results to broad range of practical GNN models. Moreover, two distinct contributions are worth discussing. First, we highlight a key insight that homomorphism can serve as a fundamental expressivity measure, which has far-reaching consequences as will be elaborated in Section 4. To show that FM is a valid expressivity measure, we prove an extra and non-trivial result that FM is maximal (Definition 3. (b)). Without this crucial property, FM1 2 FM will not necessarily mean that model Mj is strictly more expressive than M2, thus preventing any quantitative comparison between models. Second, Dell et al. (2018) leveraged treewidth to describe results, which, unfortunately, cannot be applied to most GNN models studied here. Instead, we resort to the novel concept of NED, by which we successfully derive unified and elegant descriptions for all models. Moreover, as will be shown later, NED is quite flexible and can be naturally generalized to node/edge-level expressivity, which is not studied in prior work.
Finally, we remark that one can derive equivalent (perhaps simpler) description of F based on the fact that a graph F has an endpoint-shared NED iff F becomes a forest when deleting the shared endpoint. Formally, denoting by FV FX[u) the induced subgraph of F over Vr (u), we have Corollary 3.5. =Sub_ = {F: : Bu E VF s.t. (u) is a forest).
3.3 EXTENDING TO NODE/EDGE--EVER EXPRESSIVITY
So far, this paper mainly focuses on the graph-level expressivity, i... what information is encoded in the graph representation. In this subsection, grained node/edge-level expressivity by answering what information is encoded in the node/edge features of GNN (i.e., xa (u) or xa (u, v) in Section 2). This yields the following definition:
extend all results in Theorem 3.4 to the more fine-
Definition 3.6. The node-level homomorphism expressivity of GNN model M, denoted by F.M, is a family of connected rooted graphs satisfying the following conditions:
For any connected graphs G, H. and vertices hom MF GG) hom(F", FF", ,H) for all F" E J.M;
VG, E VH, (u) X (v) iff
b) For any connected rooted graph F & J.M there exists a pair of connected graphs G, H and vertices E VG, VH such that XG (u) X (v) and hom(F", ,G") * hom(F", .H)).
One can similarly define the edge-level homomorphism expressivity F.M to be a family of connected rooted graphs, each marking two special vertices (we omit the definition for clarity). The following result exactly characterizes FM and F.M for all models M considered in this paper:
Theorem 3.7. For all model M defined in Section 2, J.M and F.M (except MPNN) exist. Moreover,
MPNN: JMMP-
=F F is tree);
Subgraph GNN:
FSub {F F has a NED with shared endpoint w) (F" F¹ (w) is a forest..
Fuub =f f.wx; has a NED with shared endpoint w} = (F (w)} is a forest);
2-FGNN: FF F F has a NED where w is an endpoint of the first ear), = : F has NED where and x are endpoints of the first ear).
The cases of Local 2-GNN and Local 2-FGNN are similar to 2-FGNN by replacing "NED" with "strong NED" and "almost-strong NED", respectively.
In summary, the node/edge- homomorphism expressivity can be naturally described using NED
by further specifying the endpoints of the first ear.
3.4 EXTENDING TO HIGHER-ORDES GNNS
Finally, we discuss how our results can be naturally extended to higher-order GNNs, thus providing complete picture of the homomorphism expressivity hierarchy for infinitely many architectures. We focus on three representative examples: Subgraph k-GNN (Qian et al., 2022), Local k-GNN (Morris et al., 2020), and F-FNNN (Azizian & Lelarge, 2021). Subgraph k-GNN extracts graph G" for each vertex k-tuple u E Va and runs MPNNs independently, which recovers Subgraph GNN when k- = 1. As the reader may have guessed, the following result exactly parallels Corollary 3.5:

---

Published as a conference paper at ICLR 2024
Theorem 3.8. The homomorphism expressivity of Subgraph k-GNN exists and can be described as 5uub(()) = [F :U C. VV s.t. [0] & k and FXU is a forest).
We next turn to Local k-GNN. To describe the result, we introduce a novel extension of Definition 3.3, called the k-order no more than & vertices, plus k paths each linking to a vertex in the graph (see Figure 2(a) for an illustration). Note that a 2-order ear is exactly a simple path. Then, we can naturally define the nested "interval" (see the solid orange lines in Figure 2(b) for an illustration) and thus define the concept of k-order strong NED. Due to space limit, a formal definition is deferred to Definition E.3. We have the following main result:
Intuitively, it is formed by graph of
k=2
(a) k-order ears
(b) nested "interval"
Figure 2: Illustration of higher-order ears. Each curve indicates a path (with possibly zero length) and each straight segment indicates an edge.
Theorem 3.9. The homomorphism expressivity of Local k-GNN exists and can be described as FL()) = {F: F has k-order strong NED).
Finally, let us consider the standard F--GNN (or equivalently, the k-FW)). Unfortunately, we cannot find description of its homomorphism expressivity based on some form of higher-order NED; nevertheless, it easy to describe the results using the notion of treewidth (see Definition C.2). Specifically, denoting (F(F) to be the treewidth of graph F, we have the following result:
Theorem 3.10. The homomorphism expressivity of k-FGNN exists and can be described as FF(Ks {F: tw(F))= S k}.
Interestingly, one can see that FSub(l), FL(1,, and FF(() all degenerate to the family of forests, which coincides with the fact that all these higher-order GNNs reduces to MPNN for the base case.
4 IMPLICATIONS
The previous section has provided a complete description of the homomorphism expressivity for a variety of GNN models. In this section, highlight the significance of these results through three different contexts. We will show how homomorphism expressivity can be used to link different GNN subareas, provide new insights into various known results, and answer number of open problems.
4.1 QUALITATIVE EXPRESSIVITY COMPARISON
One direct corollary of Theorem 3.4 is that it readily enables expressivity comparison among all models in Section This can be summarized below:
Corollary 4.1. Under the notation of Theorem 3.4, JMP C. JSub &. FL FLF Ç FF. Thus, the expressive power of the following GNN models strictly increases in order (in terms of distinguishing non-isomorphic graphs): MPNN, Subgraph GNN, Local 2-GNN, Local F-FGNN, and 2-FGNN.
Proof. JMP FSub follows from Corollary 3.5 and the fact that deleting any vertex of forest yields forest. FSub c FL follows by the fact that any endpoint-share NED is a strong NED. FL C
JFLF C FFF follows similarly since any strong NED is an almost-strong NED and any almost-strong NED is NED. To prove strict separation results, one can check that the four graphs in Figure 1(b) precisely reveal the gap between each pair of graph families, thus concluding the proof.
O
Corollary 4.1 recovers series of results recently proved in Zhang et al. (2023a); Frasca al. (2022).
Compared to their results, our approach draws much clearer picture of the expressivity gap be- tween different architectures and essentially answers how large the gaps are. Moreover, we provide systematic guidance for finding counterexample graphs that unveil the expressivity gap: shown in Corollary C.54, any graph F J-,y JrMM immediately gives a pair of non-isomorphic graphs that reveals the gap between models M1 and M2. We note that this readily recovers the counterexamples constructed in Zhang et al. (2023a) and greatly simplifies their sophisticated case-by-can analysis.
We next turn to three types of oidee GNNs studied in Section 3.4, for which establish a complete expressiveness hierarchy, as presented in Corollary 4.2. A graphical illustration of these results is given in Figure 3.
7

---

Published as a conference paper at ICLR 2024
striet
Subgraph 1-GNN
strict
Subgraph 2-GNN
strict
Subgraph 3-GNN
MPNN Subgraph 0-GNN
strict
incomparable
strict
incomparable
strict
Local I-GNN
(1-WL)
Locul 2-GNN
2-FGNN (2-FWL)
strict
Local 3-GNN
strict
3-FGNN (3-FWI)
strict
Local
4-GNN
Figure 3: Expressiveness hierarchy of MPNN, Subgraph GNN, Local GNN, and FGNN.
Corollary 4.2. Under the notations in Section 3.4, for any k > O, the following hold:
a) FSub(k-)) 1) ç FSubllk) L.e. the expressive power of Subgraph k-GNN strictly increases with k;
b) F(M) & Fl(+)), Lee. the expressive power of Local k-GNN strictly increases with k;
c) Sub(k) cxl(t)1), Iee. Local (k+1) 1G-NNGGNNLL is strictly more expressive than Subgraph k-GNN;
d) FF(Kk Ç [((tt) (F(++)), Le.. the expressive power of Local (k + L)-GNN lies strictly between k-FWI and (k + 1)-FWI;;
e) JSub(kk Ç FF((+)1), and for all k > 1, JrSub(k)) (F((++1))) (F((t) o 0 and FF(K+1)) (Sbb(()))))))))))) + 0. In other words, the expressive power of Subgraph k-GNN lies strictly within (k: + 1)-FWI. but it is incomparable to k-FWL when k > 1.
Corollary 4.2 recovers results in Morris al. (2020); Qian al. (2022) and further answers two open problems. First, Corollary 4.2(c) is new result that bridges Morris et al. (2020) with Qian et al. (2022) and partially answers an open question in Zhang et al. (2023a, Appendix C). Another new result is Corollary 4.2(d), which essentially answers a fundamental open problem raised in Frasca al. (2022, Appendix E), showing that their proposed ReIGN(k) model is bounded by k-FWL with an inherent expressivity gap (see Appendix E.4 for detailed discussion). To sum up, all these challenging open problems become straightforward through the lens of homomorphism expressivity.
4.2 SUBGRAPH COUNTING POWER
The significance of homomorphism expressivity can go much beyond qualitative comparisons be- tween models. As another implication. it provides a systematic way to study GNNs' ability to encode structural information such subgraph count, which has been found crucial in numerous practical applications. Specifically, a well-known result in graph theory states that, for any graphs F, G. the subgraph count sub( F, G) can be determined by hom (F, G)) where F ranges over all homomorphic images of F (i.e., Spasm (F), see Section 2) (Lovász, 2012; Curticapean et al., 2017).
Mathematically, given any graph F, let Spasm (F) be any maximal set of pairwise non-isomorphic graphs chosen from Spasm(F") (F)) (see Figure 4(a) for an illustration). Then, we have the following linear relation for all graph G:
sub G)
Σ PESpasm**
FF homm(,
where (F,, PP) o 0 is a constant scalar coefficient independent of G. Based on this formula, we can casily study the subgraph counting power of GNN models as shown in Proposition 4.4.
Definition 4.3. Given a GNN model M, we say M can subgraph-count graph F at graph-level if
xel (G) = x (H) implies sub(F, F, G) = sub(E F, H) for any graphs G. H. We say M can subgraph- count rooted graph F" at node-level if XG (u) = x (v) implies sub(F", G*) = sub( sub(F", H²) for any graphs G, H and vertices u VG, v E VH- We can similarly define the edge-level subgraph counting ability for rooted graphs marking two special vertices.
Proposition 4.4. For any GNN model M defined in Section 2, it can subgraph-count graph F (at graph-level) if F E JM for all F E Spasm(F). It can subgraph-count =.d (at node-level) if TT E FM for all FT [Spasm(F") (F A similar result holds for edge-level subgraph counting.
The above proposition offers a simple way to affirm the ability of a GNN model M to subgraph- count any pattern at graph/nodeccdge-leee verse direction also holds, i.c., M cannot subgraph-count F if there exists a homomorphic image F E SFassmF)) such that F & FM We find that it is indeed the case. Specifically, if the set Spasm(F)) FM is not empty, then M (H) but sub(F, F, G) * sub(F, H). We eventually arrive at the following main that X (G) = X
On the other hand, one may wonder whether the con-
always find a pair of counterexample graphs G. H such
theorem (see Appendix G.1 for a proof):
8

---

Published as a conference paper at ICLR 2024
Theorem 4.5. For any GNN model M such that their homomorphism expressivity FM exists, M can subgraph-count F iff Spasm(F) C FF Similar results hold for rooted graphs FE by replacing FM with nodeledge-level homomorphism expressivity F.MIF...
Example 4.6, As an example, we can readily characterize the cycle/path counting power of various GNNs. Denote by Cr the simple cycle/path of n vertices. Let {u, do Ec. be any edge in On. and {w, x E Ep, be any edge in Pn where w is an endpoint of Pn. The following table lists exactly all cycles/paths each model can count at graph/nodeeedde--lvee
Structure
Cycle On
Path P
Model
On
CH
P
P
MPNN
None
None
None
nS 3
ns3
ns3
Subgraph GNN
7
4 4
R54
R54
Local 2-GNN
(a) Spasm (Ca) has 10 graphs. (b) Rooted Ca Figure 4: Illustration of homomorphic im- ages of the 6-cycle and rooted 6-cycle.
Local 2-FGNN
SST
m57
2-FGNN
Discussions with prior work. Our results significantly extend Huang et al. (2023) in several aspects. First, we show Subgraph GNN can count 6-cycle at graph-level by simply enumerating its spasm (see Figure 4(a)). However, it cannot count rooted 5/6-cycle at node-level because the homomorphic image can contain cycles that do not pass the marked vertex (see Figure 4(b)). This provides novel insights into Huang et al. (2023) and extends their results (albeit with simpler analysis). Second, we reveal that Local 2-GNN can already count all cycles/paths that 2-FWI. can count (even at edge- level). This identifies new architecture with both efficiency and strong expressiveness in subgraph counting, considerably extending the finding in the concurrent work of Zhou et al. (2023b).
In Appendix G.2 (Tables 4 and 5), we summarize the statistics of all moderate-size patterns each model can count under tomommophissss/uubrrpp parisons of different models clear and exact manner. We also comprehensively list the counting ability of all moderate-size patterns in Table 6, which we believe can be helpful for future research.
which enables quantitative expressivity com-
4.3 POLYNOMIAL EXPRESSIVITY
As the third implication, homomorphism expressivity is closely related to the polynomial expressiv- ity recently proposed in Puny et al. (2023). Concretely, given model M, graph F is in FMM if M can express the invariant graph polynomial Pp (defined in Puny et al. (2023). Section 2.2), and a rooted graph Far is in J.M if M express the equivariant graph polynomial Pr Based connection, our work introduces a novel toolbox for studying polynomial expressivity via the NED framework and offers new insights into which graph polynomials can be computed for variety of practical GNNs. Moreover, we readily settle an open question in Puny et al. (2023), which upper bounds the polynomial expressivity for their proposed PPGN++:
this
Corollary 4.7. PPGN++ is bounded by (and thus as expressive as) the Prototypical edge-based model defined Puny et al. (2023) for computing equivariant graph polynomials.
Due to space limit, please refer Appendix H for proof and more discussions.
5 EXPERIMENTS
This section aims verify our theory through a comprehensive set of experiments. In each exper- iment, we implement four types of GNN models listed in Section 2, i.e., MPNN, Subgraph GNN, Local 2-GNN, and Local 2-FGNN. Note that all of these models are much more efficient than 2- FWL. Our primary objective here is not to produce SOTA results, but rather to provide unified and equitable empirical comparison among these models. To ensure fairness, we employ the same GIN- based design (Xu al., 2019) for all models and control their model sizes and training budgets to be roughly the same on each task. Details of model configurations are given in Appendix Our code is available at https: / ituub. com/ subgraph23 hww.morphhhhiccoom.m wttppiissieepeeeiiitteeee.
Synthetic task. We first test whether these GNN models can easily learn homomorphism infor- mation from data our theory predicts. We use the benchmark dataset from Zhao et al. (2022a) and comprehensively test the homomorphism expressivity at graph/nodeeedde-levw by carefully se- lecting 8 substructures shown in Table 1. The reported performance is measured by the normalized

---

Published as a conference paper at ICLR 2024
Table 1: Experimental results on homomorphism
Table 2: Experimental results ZINC and
counting. Red/blue nodes indicate marked vertices.
Alchemy datasets. See Appendix 1.4 for com- parisons of more GNN models in literature.
Task
Graph-level
Node-level
Edge-level
Model
N
Task
ZINC
Alchemy
Model
Subset
Full
MPNN
300 233 254 .505 478
MPNN
.188 .006
.030
.122 .002
Subgraph GNN
001 .015 012
.004
.058
.003
.058
.048
Subgraph GNN
110 = .007
.028 4 002
.166 + .001
Local 2-GNN
008
.008 010
003
004
.005
.006
.008
Local 2-GNN
069 = 0001
.021 + 002
.114 = .001
Local 2-FGNN
003
.005
004
.005
.005
.077
.007
.008
Local 2-FGNN
004 = .002 .023 + 0011
.111 # .001
Table 3: Experimental results the (Chordal) Cycle Counting task.
Task
Graph-level
Nove-
Edge-level
Model
MPNN
338
.008
183
146
261
205
600
.13
300
207
3315
237
Subgruph GNN
.100
.020 024
046
007
027
003
.055
.092
082
.50
073
003
090
.096
.088
.065
Local 2-GNN
.088
.011
.017
034
007
.166
.022
.005
.010
023
.044
0155
.001
.005
001
.019
.005
.014
Local 2-FGNN
.03
004
.010
020
003
010
004
000
.012
021
.004
0044
003
.006
012
.022
.005
.012
Mean Absolute Error (MAE) on the test dataset. It can be seen that the model performance indeed correlates to our theoretical predictions: (i) MPNN cannot encode any substructure under homomor- phism; (ii) Subgraph GNN cannot encode the 2th, 3rd, 5th, 7th, 8th substructures; (iii) Local 2-GNN cannot encode the 3rd and 8th substructures; (iv) Local 2-FGNN can encode all substructures.
Cycle counting power. Cycles are important structures in numerous graph learning tasks, yet en- coding them is notoriously hard for GNNs. We next test the ability of different GNN models to subgraph-count (chordal) cycles at graph/nodeledge-levea (2022); Zhang et al. (2023a); Huang al. (2023) and present results in Table 3 (measured by the normalized test MAE). Remarkably, despite the same compulational cost and model size, Local 2-(F)GNN performs significantly better than Subgraph GNN and achieves good performance for counting all 3/4/5/6-cycles well chordal 4/5-cycles (even at edge-level). These results match Example 4.6 and may suggest Local 2-(F)GNN as generic, efficient, yet powerful architectures in solving chemical and biological tasks where counting cycles is essential (e.g., benzene rings).
We follow the setting in Frasca et al.
Real-world tasks. We finally test these GNN models on three real-world benchmarks: ZINC- subset, ZINC-full (Dwivedi et al., 2020), and Alchemy (Chen al., 2019a). Following the standard configuration, all models obey a 500K parameter budget. The results are shown in Table 2. It can be seen that the performance continues improve when more expressive model used. In particular, Local 2-FGNN achieves the best performance on all tasks, suggesting that its theoretical expressivity guarantee can translate to practical performance in real- settings.
6 CONCLUSION
In this paper, present a new framework for systematically and quantitatively studying the expres- sive power of various GNN architectures. Through the lens homomorphism expressivity, we give exact descriptions of the graph family each model encode in terms of homomorphism counting. Our framework stands as a valuable toolbox to unify the landscape between different subareas the GNN community, providing deep insights into number of prior works and answering their open problems. In particular, one can establish a complete expressiveness hierarchy between models, de- termine the subgraph counting capabilities of GNNs at graph/noddeedde-level. and understand their polynomial expressivity. On the theoretical side, our results establish deep connections with a se- ries of fundamental topics in graph theory (see Appendix A.2); On the practical side, these results closely correlate with the empirical performance of GNN models, as demonstrated through exten- sive experiments. Finally, Appendix outlines several open directions for further exploration, and we believe that the homomorphism expressivity framework paves fresh way for future study of more expressive GNNs.
Acknowledgement Bohang Zhang would like to thank Shengjie Luo for helpful discussions. We sincerely appreciate all reviewers for the valuable suggestions. This work is supported by Na- tional Science and Technology Major Project (2022ZD01 14902) and National Science Foundation of China (NSFC62276005, NSFC62376007).
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Ralph Abboud, Radoslav Dimitrov, and Ismail IIkan Ceylan. Shortest path networks for graph property prediction. Learning on Graphs Conference, pp. 5-1. PMLR, 2022.
Vikraman Arvind, Frank Fuhlbrücc,, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 11::42-59, 2020.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. In International Conference on Learning Representations, 2021.
Franz Baader. The description logic handbook: Theory, implementation and applications. Cam- bridge university press, 2003.
László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 684 647, 2016.
Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Con- ference Machine Leurning, pp. 599-608. PMLR, 2021a.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference on Learning Representations, 2021b.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pable Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In Advances Neural Information Processing Systems, volume 34, pp. 25280-25293, 2021.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. In International Conference on Learning Representations, 2022.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montufar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: CW networks. In Advances in Neural Information Processing Systems, volume 34, 202
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026-1037. PMLR, 2021b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Xavier Bresson and Thomas Laurent. arXiv:1711.07553. 2017.
Residual gated
graph convnets.
arXiv preprint
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. International Conference on Learning Representations, 2014.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-411 1992.
Dexiong Chen, Leslie O' Bray, and Karsten Borgwardt. Structure-aware transformer for graph rep- resentation learning. International Conference on Machine Learning, pp. 3469-3489, PMLR, 2022.

---

Published as a conference paper at ICLR 2024
Guangyong Chen, Pengfei Chen, Chang- Yu Hsieh, Chee-Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, et al. Alchemy: A quantum chemistry dataset for benchmarking ai models. arXiv preprint 1rXiv:1966. 09427, 2019a.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph iso- morphism testing and function approximation with gnns. In Proceedings of the 33rd International Conference on Neurul Information Processing Systems, pp. 15894-15902, 2019b.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count sub- structures? In Proceedings of the 34th International Conference on Neural Information Process- ing Systems, pp. 10383-10395, 2020.
Yun Young Choi, Sun Woo Park, Youngho Woo, and U Jin Choi. Cycle clique (cy2c) graph neural network: A sight to see beyond neighborhood aggregation. In The Eleventh International Conference on Learning Representations, 2022.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Sys- tems, volume 33, pp. 13260-123 13270,, 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. In Advances in Neural Information Procexsing Systems, volume 34, pp. 1713-1726, 2021.
Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 210-223, 2017.
Maarten De Rijke. A note on graded modal logic. Studia Logica, 64(2):271-283, 2000.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, volume 29, 2016.
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets weisfeiler and leman. In 45th In- ternational Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107, pp. 40. Schloss Dassuhhl-Leibniz-eeentun fuer Informatik, 2018
Reinhard Diestel. Graph Theory. Springer Publishing Company, Incorporated, 5th edition, 2017. ISBN 3662536218.
Radoslav Dimitrov, Zeyang Zhao, Ralph Abboud, and ismail Îlkan Ceylan. Plane: Representation learning over planar graphs. arXiv preprint 1000 2023.
Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee. Pf-gnn: Differentiable particle filtering based approximation of universal graph representations. In International Conference on Learning Representations, 2021.
Zdenök Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4):330-342, 2010.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint axXiv:20/2.09699 2020.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXi::2003.00982, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022.
David Eppstein. Parallel recognition of series carics-prrallel graphs. Information and Computation, 98(1); 41-55, 1992.
12

---

Published as a conference paper at ICLR 2024
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. In Advances Neural Information Processing Systems, volume 35, pp. 4776 2022.
Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, and Yixin Chen. Extending the design space of graph neural networks by rethinking folklore weisfeiler-lehman. In seirth- Conference on Neural Information Processing Systems, 2023.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.
arXiv preprint arXiv: 2019.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. In Advances in Neural Information Processing Systems, 2022.
Martin Fürer. Weisfeiler-Iehman refinement requires least linear number of iterations. In Inter- national Colloquium on Automata, Languages, and Programming, pp. 322-333. Seringrr 2001.
Martin Fürer. On the combinatorial power of the weiseeiler-lehman algorithm. In International Conference on Algorithms and Complexity, pp. 360-271. Springer, 2017.
Floris Geerts and Juan Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representutions, 2022.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272 PMLR, 2017.
Lorenzo Giusti, Teodora Reu, Francesco Ceccarelli, Cristian Bodnar, and Pietro Liò. Cin++: En- hancing topological message passing. arXiv preprint 23Xiv:330600561. 2023.
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, vol- ume 47. Cambridge University Press, 2017.
Martin Grohe. word2vec, node2vec, graph2vee, x2vec: Towards a theory of vector embeddings of structured data. In Proceedings of the 39th ACM SIGMOD-SIGACT-SSGAA Symposium Principles of Database Systems, pp. 1-16, 2020.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, volume 30, pp. 1025-1035, 2017.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borg- wardt. Topological graph neural networks. In International Conference on Learning Representa- tions, 2022.
Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with IS-NS. In The Eleventh International Conference on Learning Representations, 2023.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 7092-7101, 2019.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In Advances in Neural Information Process- ing Systems, volume 34, 2021.
13

---

Published as a conference paper at ICLR 2024
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: design provably more powerful neural networks for graph representation learning. In Proceedings of the 34th International Conference Neural Information Processing Systems, pp. 4465 1675-4478, 2020.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference on Learning Representations, 2023.
László Lovász. Operations with structures. Acta Mathematica Hungarica,
1967.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Shengjie Luo, Shanda Li, Shuxin Zheng, Tie-Yan Liu, Liwei Wang, and Di He. Your transformer may not be as powerful as you expect. arXiv preprint arXiv:2205. /3401, 2022.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in neural information processing systems, volume 32, pp. 2156-2167, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference Learning Representations, 2019b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. the universality of invariant networks. In International conference on machine learning, pp. 4363 1371. PMLR, 2019c.
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii Journal of symbolic computation, 60:94-112, 2014.
Gaspard Michel, Giannis Nikolentzos, Johannes F Lutzeyer, and Michalis Vazirgiannis. Path neu- ral networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning, pp. 24737-24755. PMLR, 2023.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5115-5124, 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 Proceedings the AAAI conference on artificial intelligence, volume 33, pp.
2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: towards scalable oigher-order graph embeddings. Proceedings of the 34th International Conference on Neural Information Processing Systems, pp. 21824-21840, 2020.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permuration-equivariann graph networks. In International Conference on Machine Learn- ing, pp. 16017-16042. PMLR, 2022.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. The Journal of Machine Learning Research, 2023.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673. PMLR, 2019.
Daniel Neuen. Homommorpiiis--diiiiiggiinngggn closedness for graphs of bounded tree-width. arXiv preprint arXiv:2304.00011. 2023.
Daniel Neuen and Pascal Schweitzer. An exponential lower bound for individualizaaion-eefi algorithms for graph isomorphism. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 138-150, 2018.
14

---

Published as a conference paper at ICLR 2024
Hoang Nguyen and Takanori Machara. Graph homomorphism convolution. In International Con- ference on Machine Learning, pp. 7306-7316. PMLR, 2020.
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network exten- sions. In Proceedings of the 39th International Conference Machine Learning, volume 162,
pp. 17323-17345, 2022.
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer.
Dropgnn: random dropouts increase the expressiveness of graph neural networks. In Advances in Neural Infor- mation Processing Systems, volume 34, pp.
2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. In International Conference Machine Learning, pp. 28191-28221 PMLR, 2023.
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. In Advances in Neural Information Processing Systems, 2022.
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems, 2022.
Gaurav Rattan and Tim Seppelt. Weisfeiler-leman and graph spectra. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.
SIAM, 2023.
Tim Seppelt. Logical equivalences, homomorphism indistinguishability.. and forbidden minors.
arXiv preprini 2:XX:::3022.1990 2023.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The power of recursion in graph neural networks for counting substructures. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206, pp. 11023-11042. PMLR, 2023.
Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-basee based graph neural nets. In Advances in Neural Information Processing Systems, volume 34, pp. 29922 2021.
Petar Veličković. Message passing all the way up. arXiv preprint arXiv:2202. 2022,
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph passing. In Proceedings of the 34th International Con-
neural networks with structural ference on Neural Information Processing Systems, pp. 14143-14155, 2020.
Qing Wang, Dillon Ze Chen, Asiri Wijesinghe, Shouheng Li, and Muhammad Farhan. n- n-WL: A new hierarchy of expressivity for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.
Boris Weisfeiler and Andrei Lehman. The reduction graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Pascal Welke, Maximilian Thiessen, Fabian Jogl, and Thomas Gärtner. Expectation-commlltt graph representations with homomorphisms. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 36910-36925. PMLR, 2023.
Asiri Wijesinghe and Qing Wang- A new perspective "how graph neural networks go beyond weisfeiler-lehman?.. In International Conference on Learning Representations, 2022a.
Asiri Wijesinghe and Qing Wang. A new perspective on "how graph neural networks go beyond "eisseiler-lehman?.. In International Conference on Learning Representations, 2022b.
15

---

Published as a conference paper at ICLR 2024
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations. 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances Neural Information Processing Systems, 34, 2021.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph GNNs via subgraph weisfeiler-lehman tests. In International Conference Machine Learning, volume 202, pp. 41019 41077. PMLR, 2023a.
Bohang Zhang, Shengjie Luo, Di He, and Liwei Wang. Rethinking the expressive power of gnns via graph biconnectivity. In International Conference on Learning Representations, 2023b.
Muhan Zhang and Pan Li. Nested graph neural networks. In Advances in Neural Information Processing Systems, volume 34, pp. 15734-15747, 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference Learning Representations, 2022a.
Lingxiao Zhao, Neil Shah, and Leman Akoglu. A practical, progressively-expressive GNN. In Advances in Neural Information Processing Systems, 2022b.
Cai Zhou, Xiyuan Wang, and Muhan Zhang. From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks. arXiv preprint arXiv:2305.04963 2023a.
Junru Zhou, Jiarui Feng, Xiyuan Wang, and Muhan Zhang. Distance-restricted folklore weisfeiler- leman gnns with provable cycle counting power. In Thirty-seventh Conference Neural Infor- mation Processing Systems, 2023b.
16

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A More Related Work
18
A.1 Expressive Graph Neural Networks
18
A.2 Broader impacts and additional discussions
20
B Limitations and Open Directions
21
C Proof Theorem 3.4
21
C.I Preliminary
22
C.2 Part I: tree decomposition
................................
25
C,3 Part 2: nested car decomposition
39
C.4 Part 3: pebble game
43
Node/edge-level Expressivity
Related to tree decomposition ear decomposition
51
D.2
Counterexamples
................................
52
E
Higher-order GNNs
54
E.1
Definition of higher-order GNNs
................................
54
E.2 Higher-order strong NED
55
E.3
Proofs Scction 3.4.
................................
55
Expressivity gap between higher-order GNNs
56
F Additional Discussions
57
E1
Regarding the definition of homomorphism expressivity
57
F2 Regarding the definition of NED
57
G Homomorphism and Subgraph Counting Power
58
Proof Thcorem 4.5
58
G.2 Graph statistics and examples
H Polynomial Expressivity
69
1
Experimental Details
70
L.1
Datasets
70
1.2
Model details
70
1.3 Training details
................................
72
1.4 Performance of baseline models literature
17

---

Published as a conference paper at ICLR 2024
A MORE RELATED WORK
A. EXPRESSIVE GRAPH NEURAL NETWORKS
Since Morris et al. (2019); Xu al. (2019) discovered the limited expressive power of MPNNS in distinguishing non-isomorphic graphs, a large amount of work has been devoted to developing GNNs with better expressiveness. Below, we briefly review representative approaches in this area. For comprehensive survey on expressive GNNs, we refer readers to Morris et al. (2023).
Higher-order GNNs. Inspired by the relation between MPNNS and the 1-WL, test, natural ap- proach to designing provably more expressive GNNs is to mimic the higher-order WL. tests. This gives rise to two fundamental types of higher-order GNNs. One type of GNNs mimics the k-WL test (Grohe, 2017), and representative architectures include k-GNN (Morris et al., 2019) and k-IGN (Maron et al., 2019b;c); the other type of GNNs mimics the k-FWL (Folklore WL) test (Cai et al., 1992) and is referred to the the k-FGNN (Maron et al., 2019a). Azizian & Lelarge (2021); Geerts & Reutter (2022) proved that each of these architectures is exactly as expressive as the correspond- ing higher-order WL/FWL test. Therefore, the expressiveness grows strictly as the order k increases; when k approaches infinity, they can universally approximate any continuous graph functions (Chen al., 2019b; Keriven & Peyré, 2019). However, due to the inherent computation/memory complex- ity, these architectures are generally not practical in real-world applications.
Local GNNs. To improve computational efficiency, subsequent line of work seeks to develop more scalable and practical GNN architectures by taking into account the local/sparse nature of graphs. Locality/sparsity is also an important inductive bias for graphs but is not well-exploited in higher-order GNNs, since their layer aggregation is inherently global and the graph adjacency information is only encoded initial node features. To address these shortcomings, Morris et al. (2020) proposed the Local k-GNN (and several variants) incorporates graph adjacency into network layers and only aggregates neighboring information in- stead of the global one. The authors further proved that Local k-GNN is strictly more expressive than k-GNN. Building upon Local k-GNN, Morris et al. (2022) proposed the (k, s)-peqNeet that further reduces the computational cost by considering subset of k-tuples whose vertices can be grouped into no more than s connected components. A similar idea appeared in Zhao et al. (2022b), in which the authors proposed the (k, --S-eGNN by considering k-sets instead of k-tuples. Besides Local k-GNN, recent architectures proposed in Frasca et al. (2022) and Zhang et al. (2023a) can be analogously understood as Local k-IGN and Local F-FN,, respectively. Very recently, Feng et al. (2023); Zhou et al. (2023b) generalized the Local k-FGNN to broad class of Folkiore-type GNNs and achieved good performance on several benchmark datasets.
replacement of k-GNN, which directly
Subgraph GNNs. Graphs that are indistinguishable by WL tests typically possess a high degree of symmetry. In light of this observation, Subgraph GŇNs have recently emerged as a compelling approach to designing expressive GNNs. The basic idea is to break symmetry by transforming the original graph into a collection of slightly modified subgraphs and feeding these subgraphs into a GNN model. The carliest forms of Subgraph GNNs may track back to Cotta et al. (2021); Papp et al. (2021) (albeit with a different motivation), where the authors proposed to feed node-deleted subgraphs into an MPNN. Papp & Wattenhofer (2022) later argued use node marking instead of node deletion for better expressive power, resulting in the standard Subgraph GNN studied in this paper. Zhang & Li (2021); You et al. (2021) proposed the Nested GNN and Identity-aware GNN, both of which can be treated as variants of Subgraph GNNs that use ego networks as subgraphs. In particular, the heterogeneous message passing proposed in You et al. (2021) can also be seen as a form of node marking. We note that the model proposed in Vignac et al. (2020) can also be interpreted as a Subgraph GNN. Qian al. (2022) proposed the higher-order Subgraph GNN by marking l nodes per subgraph, resulting in n² different subgraphs when the original graph has vertices. We call this architecture Subgraph k-GNN in this paper. The authors proved that Subgraph k-GNN is strictly bounded by (A: + FWL and is incomparable to F-FWL when k > 1. Zhou et al. (2023a) further generalized Subgraph k-GNN to (I, k)-NNN by using (-GNN instead of MPNN to process each subgraph. It was proved that (1, -)NNN is bounded by (K 1)-GNN for i 2 2.
Recently, Subgraph GNNs have been greatly extended by further allowing interactions berween sub- graphs. This is achieved by designing cross-subgraph aggregation layers (rather than feeding each subgraph independently into a GNN). Bevilacqua et al. (2022) developed the Equivariant Subgraph Aggregation Network that introduces global aggregation between subgraphs. A similar design is
18

---

Published as a conference paper at ICLR 2024
proposed in the concurrent work of Zhao et al. (2022a). These architectures were later proved to strictly improve the expressivity of the original Subgraph GNNs (Zhang et al., 2023b;a). Frasca et al. (2022) built a general design space of Subgraph GNNs that unifies prior work and showed that all models in this space are bounded by a variant of 2-IGN (dubbed the Local 2-IGN in this paper), Zhang which is then bounded by 2-FWI.. Zhang et al. (2023a) later proved that Local 2-IGN is expres-
sive as Local 2-GNN and strictly less expressive than 2-FWL (2-FGNN), In this paper, we still use the term "Subgraph GNN" refer the original architecture in the previous paragraph, while using "Local 2-GNN" to refer to the general architecture in Frasca et al. (2022); Zhang et al. (2023a).
Substructure-based GNNs, Another line of work sought to develop expressive GNNs from prac- tical considerations. In particular, Chen et al. (2020) pointed out that the ability of GNNs to de- tect/count graph substructures like path, cycle, and clique is crucial in numerous applications. Yet, MPNNs cannot subgraph-count any cycles/cliques. While higher-order WI. tests can be more pow- erful in counting cycles (Fürer, 2017; Arvind et al., 2020), they suffer from substantial computational cost. As such, several works proposed to directly incorporate substtructur//homooorphici ing into the node features as a preprocessing step to boost the expressiveness of MPNNs (Bouritsas et al., 2022; Barceló et al., 2021) or serve an expressive graph kernel (Grohe, 2020: Nguyen & Maehara, 2020; Welke et al., 2023). Going beyond node features, Bodnar et al. (2021b;a); Giusti al. (2023) further proposed message-passing framework that enables interaction between nodes, edges, and higher-order substructures like cycles and cliques. We note that the Autobahn, TOGL,, and Cy2C-GNN proposed in Thiede et al. (2021); Horn et al. (2022): Choi al. (2022) can also be viewed as Substructure-bart
count-
GNNs. However, most of the above approaches consider a fixed, pre- defined set of substructures rather than designing generic architectures that can learn substructures in an end-to-end fashion. Recently, Tahmasebi et al. (2023) proposed the RNP-GNN an architecture that can count any substructure by recursively splitting a graph into a collection of -aake- subgraphs. We note that this design shares interesting similarities to higher-order subgraph GNNs and also the SpeqNet (Morris et al., 2022). Huang et al. (2023) proposed a generic model called 12- GNN based on variant of Subgraph 2- 2-GNN, which can count 6-cycle at node-level. In this paper, we show the Local 2-GNN can already count all cycles/paths within 7 nodes even at edge-level while being more efficient than I-GNNN (when using similar ego network design). Finally, remark that the polynomial expressivity proposed in Puny et al. (2023) can also be seen as generalization of substructure counting, which further takes into account the real-valued node/edge features.
Distance-based GNNs. Besides structural information, distance serves as another fundamental at- tribute of graph, which, again, is not captured by MPNNs and the 1-WL test. Li et al. (2020) first proposed to improve the expressive power of GNNs by augmenting node features with Distance Encoding (DE). Related to DE, another approach to injecting distance information is the k-hop MPNN, which aggregates k-hop neighbors in message-passee -passingggnngggggg layer (Feng et al., 2022; Abboud et al., 2022; Wang et al., 2023). Feng et al. (2022); Zhang et al. (2023a) proved that the expressive power of k-hop MPNN is strictly bounded by 2-FWL. Distance can also be naturally incorporated in Graph Transformers through relative positional encoding, yielding the Graphormer architecture that has achieved remarkable performance across various benchmarks (Ying et al., 2021). Recently, Zhang et al. (2023b) built an interesting connection between distance and biconnectivity properties. showing that Distance-enhanced GNNs can detect cut vertices and cut edges of a graph. This pro- vides insights into the practical superiority of these models as biconnectivity is closely linked to real applications in chemistry and social network analysis. Zhang al. (2023a) proved that Local 2-GNN can provably encode the distance (and thus biconnectivity) of a graph.
basst GNNs. Graph spectra also class of fundamental properties and have long been used to design GNN models (Bruna et al., 2014; Defferrard et al., 2016). Balcilar et al. (2021b;a) showed that designing GNNs in the spectral domain can easily break the 1-WL expressivity. For Graph Transformers, Kreuzer et al. (2021); Dwivedi & Bresson (2020); Dwivedi et al. (2022) pro- posed to incorporate the spectra of the graph Laplacian matrix to boost the expressive power beyond the 1-WL test. Lim et al. (2023) further designed a principled equivariant architecture that takes the Laplacian eigenvalues and eigenvectors as inputs, which generalizes prior work.
Other approaches. Murphy et al. (2019); Chen et al. (2020) proposed Relational Pooling as a general approach to designing expressive GNN architectures, whose basic idea to implement permutation-invarian GNN by symmetrizing permutation-sensitiv base models. Wijesinghe & Wang (2022b) proposed the GraphSNN, which improves the expressive power of MPNNs by using more distinguishing edge features. Specifically, each edge feature encodes the structure of the over-
19

---

Published as a conference paper at ICLR 2024
lap subgraph of two 1-hop ego networks centered on the two endpoints of the edge. Very recently, Dimitrov et al. (2023) designed a GNN model that can distinguish all planar graphs, thus achieving strong expressivity in chemical applications since molecular graphs are often planar.
A.2 BROADER IMPACTS AND ADDITIONAL DISCUSSIONS
Broader impact in graph theory. Due to the fundamental nature of GNN architectures studied in this paper, our theoretical results may potentially have broader impacts the graph theory com- munity. Specifically, we study the color refinement (CR) algorithms corresponding to four types of (higher-order) GNNs: Subgraph (k-12 (k-1) GNNNN, Local k- k-GNN, Local k-FGNN, and k- k-FGNN. All algorithms can be seen as natural extensions of the 1-WL test since they all reduce to 1-WL when k 1. In the graph theory community, Subgraph GNN has another name known as the vertex- individualized CR algorithm, which appears widely in literature (Babai, 2016; Rattan & Seppelt, 2023; Neuen & Schweitzer, 2018) and has become part of the core algorithm for fast graph isomor- phism testing software (e.g., McKay& & Piperno, 2014). On the other hand, Local k-GNN and Local k-FGNN are surprisingly related the guarded logic (Barceló et al., 2020; De Rijke, 2000; Baader, 2003), since the aggregations are purely local (guarded by the edge). From this perspective, these CR algorithms can be seen as natural extensions of guarded logic higher-order scenarios.
Besides these CR algorithms, our new extensions of NED may also have implications in graph the- ory. In particular, the strong NED (as well as its higher-order version) is elegant and may serve as a descriptive tool to characterize certain graph families. In addition, we establish intrinsic connections between NED and tree decomposition, which may have value in understanding other graph topics related to tree decomposition.
Finally, to our knowledge, the node/edge-level homomorphism and the corresponding subgraph counting abilities of different CR algorithms do not seem to have been systematically investigated before. Whereas in this paper, all graph/nnode/edge-lvee expressivity is studied in a unified manner. To achieve this, we introduce additional proof techniques which we believe may facilitate future study in related areas. For example, the original technique for constructing counterexample graphs satisfying Definition 3bb(b) does not apply to node/edge-level settings, since they counterexample graphs satisfying Definition 3.6(b) (no matter which vertices u E VG, v E VH are marked). To address the problem, we propose clique-augmented Fürer graphs, a novel class of counterexample graphs that extend several prior works (e.g., Cai et al., 1992; Fürer, 2001), and conduct a fine-gre ane-gerined analysis of their automorphism property (see Appendix D.2). We believe this new technique can be used to generalize other results from graph-level to node/edge-level settings.
longer
Discussions with Barceló et al. (2021). In the GNN community, Barceló et al. (2021) first pro- posed to incorporate the homomorphism count of predefined substructures into node features as an approach to enhancing the expressivity of MPNNs. They systematically investigated the questions of what substructures are useful and how the homomorphism information of these substructures can boost the model expressivity to even break out k-F Yet, they only gave a partial (incom- plete) characterization of the substructures that can be counted by the specific F-MPNN architecture and did not answer what substructures cannot be encoded, whereas our paper fully addresses both questions for variety of popular GNN models. Note that these aspects are crucial to ensure that homomorphism expressivity is well-defined. As such, our paper first identifies that homomorphism expressivity is complete, quantitative expressivity measure to compare different GNN models.
Discussions with the concurrent work of Neuen (2023). After the initial submission, we became aware of a concurrent work (Neuen, 2023), which proved that k-FWL cannot count any graph with treewidth larger than k under homomorphism. In our context, this result exactly shows that Defini- tion (b) is satisfied, and thus the homomorphism expressivity of kFFWL is well-defined. Notably, their construction of counterexample graphs is also based on Fürer graphs. Nevertheless, the proof technique hetween the two works is quite different: the proof in Neuen (2023) is built upon a key concept called oddomorphism, while our proof is based on the relation between tree decomposition and the simplified pebble game developed in Zhang et al. (2023a). is essential to underscore that our results and proof technique are more general and go beyond the standard k-FWL, in that (i) it applies to a broad range of color refinement algorithms related to practical GNN architectures and homomorphism expressivity. Our theoretical results thus
(fi) it further extends to node/edge-lewe strictly incorporate the results in Neuen (2023). The approach in Neuen (2023) (based on oddomor- phism) cannot be easily generalized to these settings.
20

---

important open Published as a conference paper at ICLR 2024
B LIMITATIONS AND OPEN DIRECTIONS
There are still several open questions that are not fully explored in this paper. We list them below as promising directions for future study.
Existence of homomorphism expressivity for refinement-based GNN architectures. In this pa- per, we prove that homomorphism expressivity exists for a wide range of architectures defined in Section 2. On the other hand, we also note that it may not be well-defined for certain pathological GNNs, as illustrated in Appendix F.1. Given this observation, fundamental question is: what con- ditions can guarantee that the homomorphism expressivity of a GNN exists? Here, we hypothesize that very mild condition can suffice. Specifically, we conjecture that long as a GNN architecture defined following a general form of color refinement procedure that outputs stable color map- pings. its homomorphism expressivity always exists. We leave this conjecture problem for future study.
Regarding higher-order Local FGNN. This paper characterizes the homomorphism expressivity for three classes of higher-order GNNs: Subgraph k-GNN, Local k-GNN, and k-FGNN. In partieu- lar, introduce the k-order and k-order strong NED way describe the homomorphism expressivity of Local k-GNN, However, it remains unclear how to give simple description of the homomorphism expressivity for Local k-FGNN that can generalize the concept of almost-strong NED for k = 2. As such, our current expressiveness hierarchy (Figure 3) does not support Local k-FGNN yet. We leave this as an open problem and make the following conjecture below. We note that a similar open question has been informally raised in Zhang et al. (2023a).
Conjecture B.1. For all l 2 2, Local k-FGNN is strictly more expressive than Local k-GNN and strictly less expressive than k-FGNN.
Expressivity gap between Local 2-(F)GNN and 2-FGNN in practical aspects. We have proved that 2-FGNN strictly more expressive than Local 2-(F)GNN. However, from a practical perspec- tive, we surprisingly find that the subgraph counting ability of Local 2-(F)GNN mutches that of 2-FGNN for all structures within a moderate size (see Table 5), although the former is much more efficient. This leads to the intriguing question of what fundamental gaps exist between the two models in practical aspects, or is the efficiency gain free?
Other architectures. In this paper, comprehensively study variety of popular GNN architec- tures ranging from Subgraph GŇNs and Local GNNs to higher-order GNNs, and further link these architectures to Substructure- based GNNs (see Appendix A.1). Yet, we still do not cover all popular GNN architectures, such as the GSWL-based Subgraph GNN (Zhang et al., 2023a; Bevilacqua et al., 2022), SpeqNet (Morris et al., 2022), and 12-GNN (Huang al., 2023). Moreover, the classes of Distance-based GNNs and Spectral-basee which deserve future study. We would like raise the question of characterizing the homomorphism expressivity of Distance-basee GNNs and Spectral-based GNNs as an important open question. In this way, one can gain deep insights into these models' true expressivity and enable quantitative comparisons between all mainstream architectures. Moreover, it will become clear to what extent other GNN models can encode distance and spectral information about a graph.
GNNs (Appendix A) are also widely used in practice,
C PROOF OF THEOREM 3.4
This section gives the proof of the main theorem. For ease of reading, we first restate Theorem 3.4: Theorem 3.4. For all GNN models M defined in Section 2, the graph family FM satisfying Defini- tion 3.1 exists (and is unique). Moreover, each FM can be separately described below:
Subgraph GNN: Jub = {F: F has an endpoint-shared NED);
Local 2-GNN: FL =FF= F has a strong NED);
Local 2-FGNN: JLF [F:; F has almost-strong NED);
2-FGNN: JF = {F: F has a NED).
For MPNN, since it is special case of Subgraph k-GNN, the proof can be found in Appendix E.3.
21

---

Published as a conference paper at ICLR 2024
C.I PRELIMINARY
Additional notations and concepts. Besides the notations defined in Section 2, we further define the following notations. We use the symbol & denote the set of all finite, simple, undirected, labeled graphs. Let G = (Vg, Eg, (g) be a graph in G. When the label is the same for all vertices, we can omit the term la and write G = (Vg, EG). Given vertex E Vg. denote the degree of as dega (u) = [N)()), and denote the closed neighborhood of u as NNluu = Na(u) U {u). The shortest path distance between vertices u and e is denoted by disg(u, v)-
Given a vertex set S C Va. the induced subgraph of G over S, denoted as G[S], is the subgraph of G with vertex set S and edge set {(u,v) E Eg u, U E S}. Similarly, without abuse of notation, given an edge set R C Ea. the induced subgraph of G over R. denoted G(R), is the subgraph of with vertex set U U v} and edge set R. Given a vertex tuple u = (w1,--. ug), denote by G = G .u the rooted graph obtained from by marking vertices u1, ug. The atomic type of G over u, denoted by atp (u), is le x l matrix where the element at position (8. Egl). Given two graphs G, H, the graph union G U H is defined to be the graph (Va U Vn. Eg U En, (GUH), where EgUat (u) == la (u) for all u E Va and lawi (u) == (u) for all u E Vnr- It is well-defined iff (a()) = Er((w) for all u E Va n Vn. Finally, we the notation G H denote that G and H are isomorphic graphs.
is the tuple (Ilu, = =uyl. Ku Uz
graph T = (VT, Fy, (T) is called a tree it does not contain cycles. Let 7" be rooted tree where r the root vertex. For each vertex E Vr, define its depth dep, (t) := dt, r) be the distance to the root, and denote by Descr- (t) the set of descendants of f. namely, E Descy- (t) iff depr-(s) = depr--(t) (t) + (t. s). For each E Vz {r), denote by pay- (t) the parent vertex of t, i.e. the unique vertex s E Nr (t) satisfying depy-
depy- (s) + 1. Define the subtree of T rooted at node by [t]. which is exactly the induced subgraph DeesST (4)) with root l.
Tree decomposition. Our proof is based on central concept in graph theory, called tree decompo- sition. can be formally defined below:
Definition C.1 (Tree decomposition). Given graph G (Vg, Eg; EV, LG) its tree decomposition is tree T = (Vr, ET, (T), where the label function 3T : Vr + 2Ve satisfies the following conditions:
Each tree node t E VT is associated to non-empty subset of vertices (r( C VG in G, called a bag. We say tree node t contains vertex u if E 3r (f);
For each edge {u, v) E VG. there exists at least one tree node t E Vr that contains the edge, i.e. {u, C (T)();
c) For each vertex u E Vg. all tree nodes containing u form a (non-empty) connected subtree. Formally, denoting (u) = {t Vi u E (t)) then ([))( is connected.
If T is a tree decomposition of G, we call the pair (G,T) tree-decomposed graph.
We remark that given a graph G. there are multiple ways to decompose and thus its tree decom- position is not unique. Several examples of tree decomposition are given in Figure 5.
Definition C.2 (Treewidth). The width of a tree decomposition is defined as one less than the max- imum bag size, i.e., max4eT [t) 1. The treewidth of graph G, denoted as tw(G), is the minimum positive integer le such that there exists a tree decomposition width k.
Some important facts about treewidth listed below:
Fact C.3. For any graph G, the following hold:
The treewidth of G is most [Val- i.e, trivial tree decomposition that only has one node t and (t) = VG.
+tw(G) = VVl - iff G is a clique.
+w((G) = 1 iff is a forest.
The above definition of tree decomposition is quite flexible without constraints on the structure of the tree or the size of each bag. Below, we define several restricted variants of tree decomposition, which (we will later see) are closely related to the GNN architectures studied in this paper. To begin with, we first define a general concept that slight modifies the original definition (Definition C.I) such that the tree becomes rooted and each bag is multiset of vertices rather than set.
22

---

Published as a conference paper at ICLR 2024
3,5
1,3,2
134
23.6
145
133
1335
3,588
1.4
2.6
3.5
3,4
3,4
L.5
3,8
1.4.5
12.6
345
123
137
156
1.9
1.5
23
3,6
1.6
(a) The treewidth of a tree is 1.
(b) Illustration of the canonical tree decomposition and Definition C.6. The four tree-decomposed graphs are in S St, SLF, Sf respectively.
Figure 5: Illustration of tree decomposition.
Definition C.4 (Canonical tree decomposition). Given graph G = (Vg. Eg, &G). a canonical tree decomposition of width & is a rooted tree 7 = (Vr, Er, Br) satisfying the following conditions:
The depth of T is even, i.c. maxtev, dep even;
b) Each node & VT is associated Moreover, (t) = k if (tp is even and [3r
multiset of vertices 3r(()) Va, called bag- if depr- (t) is odd;
c) For all tree edges {s, t} E Er where depy- (s) is even and depy- (t) is odd, Br(s) c 3r(t) (where "c" denotes the multiset inclusion relation);
d) The conditions (b) and (c) in Definition C.1 are satisfied.
As examples, one can check that the tree decomposition of all graphs in Figure 5(b) is canonical, but the tree decomposition in Figure 5(a) is not. An important observation about canonical tree decomposition is shown below:
Proposition C.5. Let (F,T") be any tree-decomposed graph where T" is a canonical tree decom- position of F. For any vertices u, u E Vp, either of the following holds:
and are the same bag T", i.e., there is node Vi such that {u, UB C (t)):):
The induced subgraph ( U (r)) is disconnected.
Proof. Assume that u and v are not in the same bag, i.c., (B) 0. Pick s E (T(u) and t E Br(v) such that depy (s) and dep (t) are minimal, respectively. Without loss of generality, assume that depr- (s) < dep (t). Then, t * r is not the root node and thus we can pick its parent par (t). It follows that dep (t) is odd and (par- (t)) C 3r (t) by definition of canonical tree decomposition. Therefore, u é (y(par- (I)). Moreover, by the assumption that depr- (8) < depr-(I), any node in (T) not descendent of We thus conclude that there does not exist tree edge such that the two endpoints contain u and v, respectively.
Now we are ready to define several restricted variants canonical tree decomposition: Definition C.6. Define four families of tree-decomposed graphs SSub SLF and SF as follows:
a) (F,T") SF iff (F,T") satisfies Definition C.4 with width I: = 2;
b) (F,T") SLF iff (F,T") satisfies Definition C.4 with width A = 2, and for any tree node t of odd depth, has only one child if w & {v : e Na(u], E (r)s where s the parent node of and is the unique vertex in 8r (t) (r(s);
c) (F,T") E St iff (F, T") satisfies Definition C.4 with width 2, and any tree node t odd depth has only one child;
d) (F,T") E Suub iff (F, (F,T") satisfies Definition C.4 with width & = and there exists a vertex Ve such that Br (1) for all & Vr.
23

---

Published as a conference paper at ICLR 2024
Examples of tree-decomposed graphs in the four families are illustrated in Figure 5(b).
Before closing this subsection, we define several notations for tree-decomposed graphs:
Definition C.7. Given canonical tree-decomposed graph (G, T") and node t VI, denote by [4] the subgraph of G induced by the vertex set {u: w E (8), E Descr (1))
G[T*
Definition C.8. Given two canonical tree-decomposed graphs (") and (G, T"). pair of map-
pings (p, 7) is called an isomorphism from (G, T") ) to (G, (G, denoted by (G, T") = (G, T") if the following hold:
p is an isomorphism from G to G;
b) is isomorphism from 7 T (ignoring labels B);
c) For any / E T", ((3r()) (T))
Equivalent formulation of GNN architectures. Below, we give equivalent definitions for several GNN architectures presented in Section 2, which will be used in subsequent analysis. Let G be graph and u, v E Vg. For all models M including Subgraph GNN, Local 2-GNN, Local 2-FGNN, and 2-FGNN, we define the initial color XG =M(00) (u, v) to be the isomorphism type of vertex pair (u,v) v) (i.e., atp (u, plus labels of each vertex). Note that this matches the original definition except for Subgraph GNN. Then in each iteration f, the color is updated according to the following formula. Here, for clarity, we denote XG
(M) (u, S) (xx (u, (u,u) SB and Xe
M. (S, v)
lxo Mt())) (u, u) E SB for any model M and set S.
Subgraph GNN:
XG xG (ub,( (u, v) hash (xG
(xSub.(0) (u, o), XG
Sub. No(w)), XG (u. Vo))
Sub.(1))
(7)
Local 2-GNN:
cL(1)) (u, (o() L.1l (No(u),u), (N XG x (u, hash (x (u,w), v), XG
(8)
Xa ( Vc), (u, Xa x1. xVc.
Local 2-FGNN: (LF,((+1) (u, v) hash (F.())) XG (u, v), [1G
(((.F. (w, v), XG
(LF.()) (e
XG
LFF((L)
(u, Va),
_LF((1 (VE: (Va,
XG
(9)
2-FGNN:
Xa (1(t1) (u, hash (F) XG (u, v), (xxx
(1( (w, v), XG (u, w Vol.,
(10)
XG (. Va), XG (.() (Va.
can be seen that we additionally add global aggregations for these architectures. Moreover, in Local 2-FGNN we replace the neighbors by closed neighbors No lul U No(v). The stable color of (u,v) ) for different models denoted by &Sub (u, v). (a v), XG (u, v), X (u, v), respectively. We have the following result:
(G) Proposition C.9. Let E (Sub, LFF,FF be any model. For any graphs G, H. Xa (G) = XH (H) iff x (G) = XM (H). Furthermore, if and H are connected, then for any vertices u, v E VG and x, VH. X (u, = XM (a, y) iff 2 (u, v) xM (x, u). In other words, the color mapping A as fine as the original one x
Proof. The proof simply follows from Zhang et al. (2023a, Proposition 4.2 and Theorem 4.4), be- cause (i) node marking in the initial color Subgraph GNN is as expressive as using the isomor- phism type, (ii) the global aggregation does not improve the expressivity when the corresponding local aggregation is presented, (iii) the single-point aggregation does not improve the expressivity in Local 2-FGNN.
24

---

Published as a conference paper at ICLR 2024
C.2 PART 1: TREE DECOMPOSITION
We first define the unfolding free of different CR algorithms, which is a standard tool in analyzing GNN expressivity.
Definition C.10 (Unfolding tree of Subgraph GNN), Given graph G, vertices u, v E VG. and a non-negative integer D, the depth-2I Subgraph GNN unfolding tree of graph G at (u, v), denoted T Sub.(D) (u, v)). is tree-decomposed graph (F,TT) E S constructed as as ( Su. (u, (u, v),
follows:
1. Initialization. At the beginning, F = G(fu, e (if u = v, F only has one vertex), and T only has a root node with (r(() = uu, BB. Define a mapping ι Ve VG as T(l)
and π (T))
Loop for D rounds. For each leaf node in T", do the following procedure:
Let 37 (4) (u xx); For each w E Va, add a fresh child node Lw to 7 and designate /. as its parent. Then, consider the following three cases:
a) If _ =() and w A (x), then add fresh vertex to F and extend with (2) = The label of z in F is set by (x(2) = (a(w). Define (r(tw) = BT (t) U {=B. Then, we add edges between and (t), so that π is an isomorphism from F ((w)) to ((
If (u). then we simply set (1 ) (t) u fuB without modifying graph F. c) If T (z). then we simply set (T ) (t) (t) u {rB without modifying graph F.
Finally, add a fresh child node ty to 7", designate tw as its parent, and set (r(w))) based on the following three cases:
a) If w * Tu) and w + T2;), then (T((k)) uu,= b) If
ru)) then (T Hu, (u,u) u]}-
c) If w = (xx) then (r = fu.xx.}.
is easy to see that the depth of tree T" increases by after each round, T is always canonical tree decomposition of F, and (F,T") T") S An illustration of the construction of unfolding tree given Figure 6(a).
We next define the unfolding tree of Local 2-GNN, which differs in the loop part such that the bags (tww and (t-(t,.. now do not necessarily contain Definition C.11 (Unfolding tree of Local 2-GNN), Given a graph G. vertices u, v Vg. and non-negative integer D, the dD Local 2-GNN unfolding tree of graph G at (u, v), denoted as (FL()) (u, v), (1) (u,,)) v)) (D),)) is tree-decomposed graph (F, (") E S constructed as follows:
1. Initialization. The procedure is exactly the same as Subgraph GNN (Definition C.10).
Loop for D rounds. For each leaf node in 7", do the following procedure: Let (t) {x,, vB. For each parent. Then, consider the following three cases:
VG, add fresh child node th to T and designate as its
w A ((x) and w A Tty). then add fresh vertex = to F and extend with ((2) = w. The label of 2 in F is set by (2) (a(w). Define (r(tw) = By (t) U x B. Then, we add edges between & and (t),), so that क is an isomorphism from F (Br(tt)) to ((r(((ttw)))
b) If w = T (z). then we simply set (T((w) = (t) U (IB without modifying graph F. c) If (vy), then we simply set 37 (1.) (T u HvD without modifying graph F.
Next, add fresh child node l' in 7", designate l, as its parent, and set (1w))) based on the following three cases:
a) If w # (ax) and w # TVy), then (T((2) = .I
b) w w = T (x). then (7(())) ( = 42, x
If w (vy) then 37
Finally, we repeat the above procedure (point 2) once more, but this time the bag 3 (t',.) is replaced by the following three cases (changing y):
25

---

Published as a conference paper at ICLR 2024
1.2
(a)
12.1
1.22
1.2.5
1.2
1.5
G
Sab.(())
(1,2)
T Sub.
(1,2)
1.
(b)
12
1.22
12.5
12.1
G
F (1,
To (1,2)
1.2
(c)
1.211
1.22
1224
1.2Y3
12,5'
G
FG (1,2)
T (1,2)
1.2
(d)
12,1
1.22
1223
1,2.4
1.25
F (F,
(1,2)
Figure 6: The 2epth-2 unfolding of graph G vertex pair (1,2) for Subgraph GNN, Local 2-
GNN, Local 2-FGNN, and 2-FGNN, respectively.
If # (x)) and w # (yy), then By (1/) (),
If (y)) then 3y (t.m) fly, v..
c) If (z). then (t'w) 2 vB.
An illustration of the construction of unfolding tree is given in Figure 6(b).
We next define the unfolding tree of Local 2-FGNN, which differs in the loop part such that the node tu can have two children under certain conditions.
Definition C.12 (Unfolding tree of Local 2-FGNN). Given a graph G, vertices u, E Ve, and non-negative integer D, the depth-2 Local 2-FGNN unfolding tree of graph G at (u, v), denoted as (LF.(D) FLF (L).(D) (u, v), TL (D) (u, v) is tree-decomposed graph (F,T") SLF constructed follows:
Initialization. The procedure exactly the same as Subgraph GNN (Definition C.10).
Loop for D rounds. For each leaf node in 7T, do the following procedure: Let (() (f,,8/ For each E [a( U NG (T (y)]. add fresh child node t. to T and designate as its parent. Then, consider the following three cases:
a) w * (2x) and w + Tty). then add a fresh vertex z to and extend π with ((2) = w.
The label of in F is set by (2) la(w). Define (r(tw) By (t) {=) Then, we add edges between z and Br(t), so that π is an isomorphism from F F(3r(t.)) to G(r(@r(t..))
If ffw (x)) then simply (r (T(() U ([ without modifying graph F. If (v)). then we simply set 3r (Iw)) (T) U Kv) without modifying graph F.
26

---

Published as a conference paper at ICLR 2024
Next, add two fresh children the and t" in T", designate tw their parent, and set B (t(wt)) and B7 (f.)) based on the following three cases:
If # (2x) and w # Tty), then (ty)) {I and By (t") 2y.
b) If w = (2)) then (tyt))) = f1,, x: B and (r = (r.v
c) If w = (v), then 3r((.) = f(. yh and (r((m) - fu.
For each w & No[T(z)] U [v)r( follow the the same procedure Local 2-GNN (Defi- nition C.11).
An illustration of the construction of unfolding tree is given in Figure 6(c).
We finally define the unfolding tree of 2-FGNN, which differs in the loop part such that all nodes tur have two children.
Definition C.13 (Unfolding tree of 2-FGNN), Given a graph G. vertices u, E VG. and non-negative integer D, the depth-2D 2-FGNN unfolding tree of graph G at (u, v), denoted as (Pa (P) (u, u); () (eub.(D)(
is tree-decomposed graph (") SF constructed as follows:
1. Initialization. The procedure is exactly the same as Local 2-FGNN (Definition C.12).
2. Loop for D rounds. The procedure is similar Local 2-FGNN (Definition C.12) except that the condition w E [G[T(<)] U Na(T(y)] is relaxed to all vertices.
An illustration of the construction of unfolding tree is given in Figure 6(d).
We are now ready to present the first core result:
Lemma C.14. Let M {Sub, LF, be any model. For any two graphs G, H, any vertices 2, Ve, y. E VH, and any non-negative integer D, XG
-M,(D) vu = XX
-M. (I, y) iff there exists
an isomorphism (p, T) from that p(u) z, p(u) = y.
(F ( v), T
(z, v) such U ( (u, v) to F (. (I, (z, TH M.(D)
Proof. Here, we only give the proof for Local 2-GNN, and the proofs for Subgraph GNN, Local 2- 2-FGNN and 2-FGNN are almost the same so we omit them for clarity.
Proof for Local 2-GNN. The proof based on induction over D. When 0, the theorem obviously holds. Now assume that the theorem holds for D I d, and consider D = d + 1. Below, we omit the corner mark for clarity.
=(++)) ((++)(,,))) (u, v) = XH (x.z) y) implies that there exists an isomorphism 1. We first prove that XG
((d+1)
(p,T) from ( (u, v), To (u,
to (F (d++1) (z, (e, (((++)) (I. such that p(u) =
(d+1) x. p.p(v) = y. If XG (u, v) = X2 (dd-1)
(x, y). then
(( (u, w) atpo v, w)) E Vo = M((11) (x, atp atp
E Vn (11)
(x (w, v), atpo u, w)) w E Vol ((x!d) (z, v), atp (x, v. 2)) :2 Vn B. (12)
Let n = VVal = Vvl. Thus, we can denote VG = (Wi,"' .. ,,, = (w/ .. w/ and
Vn = (21.-.. 2n
f2/, 2 such that
(xd)) (u, wx), ( u. w.)) = (x (x, 21), atp (z. 2)) for all E [n]:
(xl (w/, v), at v, w()) = (x (il) (2/1 v), atp (2, u, z() for all i [n]]
On the other hand, by definition of tree unfolding, we have
( (u, ui)) m
) U Und (uf,
LG (ddt1) (u,
U F (1l)
(u,e),
p(d+ 11 (2,, v)
U Fl (2)
u
(24. (F(()(
F
U U
27

---

Published as a conference paper at ICLR 2024
Assume w/ w1 u,
i 3. 7
002 212
(:100 (u',
14 16
V.
1.. U. 1dg
Mr. U. Me
F(2 (u, wi
F (ar, wyy
(wn ml
a. wr
Min
F (u, wis
plan (wag
Trad (1,, mry)
T:22 (1,, wyy
(144) (a, w
Ti20
Trad
T (dd (argee
(udg,
3, 1
Figure 7: Illustration of the proof of Lemma C.14.
where U represents the graph union. Here, all w;; u/j & {u, o} in different graphs are treated as different vertices when taking the union, while u, v in different graphs are shared. See Figure for an illustration of the above equations.
By induction, there exists an isomorphism (ps. Ti) from (F(²) (u, w;), Tél (u, w.)) to (rld) (I, 2x), T an isomorphism p from (F( v), To To (ut,
(i E [n]), and there exist (F The ( (2: such that (v) y. (l(()) 2 (i E [n]). Moreover, we have atpo v, wi) atp (z, y, 24) and ( v, wd)) = ( y, z{) for [m], which implies that F()) (u, v) is isomorphic to F# y). Therefore, if we construct by merging all Ps and p (i E [n]), and con- struct 7 by merging all т. and T/ and further specifying an appropriate mapping between tree nodes of depth no more than I in Ta (d-1) (u, and gd(++) (zx, v). then is straightforward to that (ø, F) is well-defined and is isomorphism from [ (F(d+1) (u, r () u)) to
(x, zi) such that pt(u) H. pe(w,)
(d+1) (1/1 (1iatt)(z, (z, v), T (z, (I. such that p(u) x. p(v) = y.
2. We next prove that if there exists an isomorphism (p, r) from the tree-decomposed graph v), (dd+ (z. v)) such that p(u) I, p(v) = y,
(FL (rlat)) (u, I I-dd") (u, to (F (x(++)( (z, (z.
then X x(d+)) (u, v) = xH (d+11) (x,
y. since T is isomorphism from Te Tdd+"( (u, o) to T rr(+t) (xx, y). maps all tree nodes of depth I in 1e 1-(+11( (u, v) to all tree nodes of depth 1 in T T(d++1 (x., v). Let s1, , be all nodes of depth 2 in G TTl+1) (u. v) such that u E 37id11 (8:) (it follows that n = [Va). D. and let sy be the parent of 8,. Similarly,
Without loss of generality, assume u + and
let (,,... ,4n be all nodes of depth 2 (dd+1) (s,, u) such that x E P be the parent of t, Moreover, can arrange the order that the following are satisfied (for each [n]):
Breat" (m.w) (4)), and let ig
G a) is an isomorphism from the subtree T(d+1) (u, [){ to the subtree (d++1) (2, (x, (t.].)
b) For all E Descngett) ($;), p ((())))) (s)) - (T()).
(a.g)
c) By definition of the unfolding tree, P is an isomorphism from the induced subgraph p(d+1) (u, ()(rr((t)) (u, v)[ss]] to the induced subgraph 1.(d+1)( v)(r (I. [)tell
(d+1)
(see Definition C.7).
d) Let (7ga+ (s/) = Hu, W and B Braam (4)
Then, p(w.) =
ž; and thus {u, wi) E E Epptt" iff {y, ). E Eppatil
By items (a) to (c), (Fldt)) (rdett (u, w)[s)|| (F (2 T the unfolding tree, (r(dt)) (u,u) (Tdaet) (u, s][so]] Tla+!) (w, u)(s.)) is isomorphic to
I Ild+t) (u, w)(s:)) is isomorphic to (T(+1)) (z, y)(to]| I T(a+ (a, (a. w)ltd). On the other hand, by definition of
28

---

Published as a conference paper at ICLR 2024
(u, the depth-2d 2d unfolding tree (FG (u, wi), To (u, wi)) for some wy e Vg satisfying that
fwr E EG iff {ūos, o) E E Ergett
Similarly,
(F (Fllt)) (x.y) (Tltt") (z, With ( v)t.))))))) is isomorphic to (x, (1 for some 2 E VH satistying that {2. E Eh Combining all the above equivalence yields that (re (u, w.), Ta (u, mi) is isomorphic to (r/d) (s, 2i), T (x, zi). and {wi,e} E Ea iff (ax, v) E En.
iff (2,.0} E (ax)))
By induction, we have x2 (u, wy) = x (x. 21). Moreover, we clearly have that fu, w:} E Eg iff (x, E En, and {u, v) EG iff (3 E En. Therefore.
(x (u, w;), atpo (u, v, wa)) = (x// (z, z1), ( y, zi)).
(13)
Next, note that W; are different from each other for i E [n] by definition of unfolding tree. Thus, w; are also different from each other. It follows that
((xx (u, w), atpo (u, v, w)) E V&B [( atp E Vn (14)
Again using the same analysis as before, we obtain
1Kx (w, v), atpo (u, v, w)) w V&B H (x (z.g). atp (z. : 2 E Vn (15) (d) It remains to prove that xa ww,w) = XH (ar, v). To prove this, note that Equation (14) implies that
(x (u, w), atpa v, w)) w E VoB = (x (( (a, (z, 2), atp (x, : E Vn (16)
holds for all 0 S d' d, and Equation (15) implies that
((x6 (w, v), at atp (u, U, w)) w E V&B = |[ (x (z, v), atp (x, U, z)) = E VH (17)
holds for all S d' S Combined with Equations (16) and (17) and the fact that (0)
(0) AG (u,u) XH (s. v). we can incrementally prove that X (u, v) XH (x, for all
(d')
(dd')
dd+1
We have thus concluded the proof.
Definition C.15. Let M E LF,, F} be any model. Given graph G and a tree-decomposed graph (F,T", define
M (F,TT), {((0 ((u,0) E v2: AD e NN s.t. (FM. (u, v), T Te (w, = (P.TT))
where (FG (E (u, u), Io M.) (u, v)) is the dD unfolding tree of G at (u, v) for model M.
Corollary C.16. Let M E (Sub, LF, be any model. For any graphs G, H. Xa (G) = xM (H) iff cnt M ((F,T", G) = cnt M
H) holds for all T") E S
Proof. " "=>". If X6 (G) XM (H), then X
M (u,v) v) U.UE VoB = Hxx M (z,y) xx E Vn B- For each color e in the above multiset, pick u,v VG with xa (u, = c. It follows that if
(F,T") ~ (F (DD) (u, v), TMM. (u,z)) v)) S for some D, then ent
= (u, e V X6 (u, = ctI = (x, E V M (z,z)= = = = ent ((F,T), ,H) by Lemma C.14.
M
On the other hand, if (F,T") o (FM (u, T T.M. (u, v)) for all u,v E VG and all D. then clearly M ((F,T))
an ((F,T") ,H) 0.
If Mf ((F,T"), = M ((F, ",,,T"),5 H) holds for all (F,T*) E SM, it clearly holds for all (FPP) (u, (PP) (u, v)) with u, u E Va and a sufficiently large D. This guarantees that for all color e, ((u, v) VV xa v) = =]] K( v) E V xM (æ,y) v) c} by Lemma 1. Therefore, xix (u, v) : uu Vo] (xx (z. v) : x. E Vn B. concluding the proof.
n
29

---

Published as a conference paper at ICLR 2024
We next define an important concept called bag isomorphism (Dell al., 2018).
Definition C.17. Given a tree-decomposed graph (F, and graph G, bag isomorphism from (E,T") to (abbreviated as "bIso") is a homomorphism f from F to G such that, for E Vr, f an isomorphism from F(3r(t) (t)] to G[f (t)]]. Denote BIso((F,TT)) G) to be the set of all bag isomorphisms from (F, to G, and denote (Fs G) =
Remark C.18. To prove that a mapping f from (F,T") to is a blso, suffices to prove the following conditions:
1. For any two different vertices u, v E Va in the same bag, f(u) + f(v);
2. For any two vertices u, U E Ve in the same bag, {u, v) E Ep iff {f(u), f(u)) E Ec;
3. For any u E Va. Er(u) (a(f(u))
The following fact is straightforward from the construction the unfolding tree:
Fact C.19. Let M E LSub,L.LF,F be any model considered above. For any gruph G, any vertex pair (u V2. and any non-negative integer D, there is blso from (u, (u,,) to G.
Similarly, we need the following concept to describe the relation between two tree-decomposed graphs. We note that these technical concepts also appeared Dell et (2018).
Definition C.20. Given two tree-decomposed graphs (F, 7*) and (F, T*), pair of mappings (p. T) is called homomorphism from (F,T") to (F, T*) if it satisfies the following conditions:
is homomorphism from 7 T (ignording labels 3) and is depth- beehh-preserving, i.e., depy- (t) (T()) for all E Vr:
b) For all Vr, p is homomorphism from (() to (T3)(T(t))) Note that this implies that p homomorphism from F F.
c) The depth of T is equal to the depth of T'
Definition C.21. Under Definition C.20, (p. further called bag-isomorphism homo- morphism (abbreviated as "bIsoHom"" from (F, to (F, TT) if it homomorphism satis- Vr. is an isomorphism from F[3r(()] to (T3x((())]- Further- fying that, for all more, (p,T) is called blsoSurj if is surjective; and (p,T) is called blsolnj if is in- to denote the set of blsoHoms from (F,T") to (F,T*), and let blsoHom (LF,T), (F,
jective. We use BlsoHom (FF.T),
BlsoHom (LF,T), (F,T)) The nota- (F,T"), Bisolnj (F,T"), (F,1)) and
tions BlsoSurj (F,T), blsoSurj
blsolnj (F, are defined accordingly.
Remark C.22. In the above definition, the depth of tree T" is the maximal depth among all tree nodes in 7". Note that we do not require that all leaf nodes have the same depth in T".
We are now ready to present the second core result:
Lemma C.23. Let M E {Sub, LF. F) be any model. For any graph G and tree-decomposed graph (F,T") MM
blso ((F,T), =
Σ
blsoHom (FFTT), (F, Mn ((F.T)..G). (18)
(F F.TT
Here, the summation ranges over all non-isomorphic (tree-decomposed) graphs SM and is well- defined as there only finite number of graphs making the value in the sunmation non-zero.
Proof. Here, we only give the proof for Local 2-GNN, and the proofs for Subgraph GNN, Local 2-FGNN and 2-FGNN are almost the same so omit them for clarity.
30

---

Published as a conference paper at ICLR 2024
Proof for Local 2-GNN. We assume that the root bag of (F. TT) is Ku, vB. and the depth of (F, T
is 2d. Let yy, E Ve be any vertices in G, and denote (F&²)) (y, 2), Thl ()) as the depth- 2d Local
2-GNN unfolding tree at (v, 2). Define the following two sets:
S1,,, 2) = {g: : E Blso ((E,T), G), g(u) = V.g(v) =
S2(v.2) = { (p.T): (p. E BlsoHom (IF,T"). (y. z), To
(u. (v.z))) pp(u) = =y. -. = 2].
Then, Lemma C.23 is equivalent the following equation:
Σ
[Si(,,2]
Σ
[S2(1.2)
V.=EVo
M.2EVo
We will prove that (y, = |S2 =) for all y, 2 E Va-
(d) Given y. Ve, according to Fact C.19, there exists blso from (Fg (y, 2), Te (y. (v. 2)) to graph G. Define a mapping a such that (pp, 7) = x o for all (p,T) E S2 2). suffices to prove that is bijection from (y z) to S 2).
1. We first prove that a is a mapping from S2 2) to z). ie. Top E Si 2) for all (p, T) E S2(y, z). First, clearly have (1t () (t) = v. (x o () = x(2) 2. We next prove that ι a p E Blso ((F,T"), G). The proof is based on Remark C.18.
a) Let E Vr, w # be any vertices in the same bag of T". Since (p.T) is blsoHom, p(w) # (()) and p(w) and p(z) are in the same bag of ((d)) (v. 2). Again, since n is a blso, we have (pp(w) F (p(x)))
b) Let w, VF be any vertices in the same bag of T". Since (D,T) is blso- Hom, p(w) and p(z) are in the same bag of Th (v.z), and {w,x} E EF iff (p(w),p(r) Eppdi
(r,e) Again, since is blso, (o(w), Epee iff (T(((w)),, (p(xr))] E Ea. Therefore, {w,x) E EF iff (=(p(w)), v(((x))) Ec. c) We clearly have E ( = pgp (v.s) (p(w)) = (c(T(p(w)))
We have proved that π o Blso ((F,T"),
2. We then prove that is surjection. For all g E S1 2), define a mapping (p. r) from (F. T") to (F( (y, 2). T (y, =)) as follows. First define p(u) = y. p(v) = 2, and set ((r) to be the root of (F(d) (y. 2). T-dd 2)). Let Wi. W'm VP and w'.... win E Vp be vertices such that all {u, 3 and {w', f} correspond to bags of T" associated to all tree nodes of depth 2. Similarly, by definition of the Local 2-GNN unfolding tree, 21, Fn E V "e("((ia)) be different vertices and x/,, ".. ,,,,, E V
Yat ((d))( (v.z) be different vertices such that all
{u.r,) and { 2) correspond to bags of T(ll 2) associated to all tree nodes of depth 2. Since g and are blsos, we have:
For every we (i E [m)), there exists xj (j E [n]), such that g(w)) = x(zz) = F. for some ē. VG and Flllu, u, will pdd) (y, 2) 2)[ H,,,,,,,,, 2, 2,
For every w/ (i [m'), there exists x (j E [n], such that g(w() ((f)) = i'J for
some 5/j E Ve and Flllu, v, w/B] F (y. H,,,,
Gllly, 2, B/B.
We then define p(w:) wy for each i E [m] and p(w() z for each E [m']. Based on the above two items, one can easily define J such that each node in 7 of depth 1 or is
mapped by to node in T(d) (v. 2) of the same depth, p(3r (s)) = Brga (t), and p is an isomorphism from F[Br(s)] to F( (y. 2) (v.)) (t)l
(v.e)
Next, we can recursively define p's image on F F[T [s]] for each tree node s of depth follow- ing the same construction above. This is because g is still a blso from (F[T" T [s)) to G,
is still a blso from [F(] (v. =)(T() (v. +)]{ T( (v.
(u. =){[(s))) to G, and ((3((s)) =
T (8 (T()))) Recursively applying this procedure, we can construct (p. r) such that it is a
31

---

Published as a conference paper at ICLR 2024
blsoHom from (F,T") to [ (v, 2), T6 (v. 21) That is to say, we have proved that for all g E Si(u, v). there is preimage (p. 5) E Sy 2) such that o 7) = g.
3. We finally prove that a is an injection. Let (pI, TI). T2) E S2(3, such that π P1 = a P2. Let w1, Wm E Vp, w/,'.. w/n VF, 21,"1 In E (g.))) and "',""., 5 E V (w.e) be defined as in the previous item. For each E [m], let (i) and ja(i) be indices satisfying PI (w:) = (1) and p2(ws) (z)( It follows that (x)) = T(())()). By definition of the Local 2-GNN unfolding tree, we must have (1) ")2(1)) and thus pi (w;)
(w,)). Using a similar approach, we can prove that Pi (i( = p2(w)) for each E [m²'] Next, we can recursively apply the above procedure to the subtree 2 [s] for each tree node of depth 2 following the previous item, and finally prove that P2- Therefore, a is an injection.
Combining the above three items completes the proof.
Proposition C.24. Under Definition C.21, (i) if (p,r) r) is a blsoSurj, then p is surjection from F to F on both vertices and edges; (ii) (p, T) is blsoInj, then p is an injection from F to F on both vertices and edges.
Proof. We first prove that p surjective if (p. r) is bIsoSurj. We will only prove that p iss surjective on edges, as proving that p is surjective on vertices is almost the same. For any {z, y E E'p, by Definition C.1 we can pick & E Vi such that {x,z] E (t). Since is surjective, there exists t E VT such that r(t) = f. By definition of bag isomorphism, there exists u, v E BT(() such that p(u) x. p(v) = y. and Flu, v}] = FK, vHJ Therefore, {u, v) EF.
We next prove that p is injective if (p, r) a bisoInj. Pick any u E Vp. It suffices to prove that p(u)- p(v) iff u = v for any E VF. If the result does not hold, consider two cases:
There exists v E Vr, v * u such that p(u) = p(v) and {u, v) are in the same bag of F. This contradicts the definition of bag isomorphism.
For all V E VF such that V + u and plu) = p(u), {u, v} are not in the same bag of F. By Proposition C.5, T (nee Br(u) is disconnected. We can thus pick path P in T such that the endpoints & and &2 are in different connected components of T (uEVe:p(u)=poo) Br(w)] This implics that there is tree node t3 in such that (1a) (u E Vo p(u) p())) = Consequently, p(u) p(0r(11)) = (x(r((1),, p(u) E ((3r(12)) (T(2() but p(u) & (3((((a)). On the other hand, since r is injec- tive, [T(Vp) is also path and ((a)) on the path between r(t1) and T(2)) in T. This contradicts the definition of tree decomposition (Definition C.)(c)).
Combining the two cases concludes the proof.
Lemma C.25. Let M E LSub, be any model. For any tree-decomposed graphs (F, E SM,
blsoSurj (F,TT), (F,T+) bisolnj (F,,T),(F,TT)
(FF.T)mm(FFT".. (F.T'ES"
Σ
aut Tut(FTT1) TT)
where aut(F, To) denotes the number of automorphisms of (F, T³). Here, the summation ranges over all non-isomorphic ((ree-decomposed) graphs in SM and is well-defined as there are only finite number of graphs making the value in the summation non-zero.
Proof. We define the following set of three-tuples:
S s= - (), (f,TT) EMM
(0$, (5) BlsoSurj (F, (f,"))
(p', (1), Bisolnj((A,f") (F, (F.T"))
32

---

Published as a conference paper at ICLR 2024
Define mappings such that
(IF,T),
())))))))))) (,.)))))))))))))))))))))) =
for all (P,,T), (,,, +)), (1,, E S. It suffices to prove the following three statements:
1. a is a mapping from S to (FF,)) (F,,T")
2. is surjective;
3. (o).
= a (122. T-2² (pā.T))) (p2. rd)) iff there exists an iso-
morphism () from
to (Fz, T such that po oी - /3. 7 = - pl - 07.
- = T/ o7.
We will prove these statements one by one.
1. We first prove that a is a mapping from S to ((F, (F, (T)). This simply fol- lows from the fact that both blsoSurj and bIsoInj are blsoHom, and the composition of two blsoHoms are still blsoHom.
2. We next prove that is surjective. Given (pt, rH) E BlsoHom((F; ())) we define
(F, "", (p,,+)), and (p', (p),r) as follows:
a) Let F = F(p and 7 = (Vr)]. We clearly have (F,T") E SMM
b) Let p²= = p* and = 7H. Obviously, (pS, +5) ) is bisoSurj from (F, F, for all E Vp and 7())) = t for all t E Vq. Obviously, (p',7)) is a bIsoInj from (F, T to (F,T").
c) Define identity mappings d'(u)
We clearly have DM pl ps and 7H = r o S. Thus, is surjection.
3. We finally prove the aforementioned item 3. It suffices to prove only one direction, namely, (fi, (T), (0i, 7)) (d) +)) ((e2, Trr) (pg, (p),T)) (ph rb)) implies that there exists
an isomorphism (p. f) from (F1, T to (F2, Te²) such that p o of = ps. f o = = p = p2 A. 7| T2 7.
a) We first prove that P = Fr and The T3..
For any u E Vp. if pu(u)= * pi(r), then of (f(()) + (f((()))
since of is an
injection (by Proposition C.24). Therefore, p (p(()) 7 (b(p((e)), and thus p5(u) *
p5(v). By symmetry, we also have that (2(u) # (1(1) implies (i( # (v)). This proves that pi
(u) = pi iff p5()) = (v()). Eg. then (Al A A((())) E Ep since p is a homomorphism. Therefore, (ob(ps (w)), ps(P((v))) Ep. This implies that (b and (vv) are in the same bag of 7 Therefore, there are vertices v, Va, in the same bag of Txx such that pb = (L(((( and (b()) (L()(t))) and by definition of bag isomorphism
For any u, E VF. if (((())
have {2.y} E E Since P2 is injective, x = ((( and y = (5(v), namely. (pā(u), p&(1)} E E By symmetry, we can prove that (u), (v)) E Ep iff (pS(u), (1() E F Finally, noting that p and P are surjective (by Proposition C.24) and lp (pf(u)) = (F(u) = fg (ps(u) for all E Vr, we obtain that F1 F.. Following the same procedure, we can prove that 7 Ttz
b) Consequently, there exist isomorphisms and F such that po pp ps. FoTS = T For any node q VT.
AB3 (Tf(a))
( = (T, = Sn (f(
Since -H is surjective, (q) ranges over all nodes in 7 when 9 ranges over Vr. We
thus conclude that (p. r) is an isomorphism from (F,, 7 to (F,, (see Defini- tion C.8).
33

---

Published as a conference paper at ICLR 2024
We finally prove that p / à and 7| T o. Pick any VF, have pl (P((p(())) (1) = pl (u)( Since oř is surjective, pf(() ranges over all nodes in FI when u ranges over Vp. This proves that pi = P o P. Following the same procedure, we can prove that 7 72 o
Combining the above three items concludes the proof.
In the following, we further define two technical concepts that will used describe the next result. We note that these technical concepts also appeared in Dell et al. (2018).
Definition C.26. tree-decomposed graph (F, (*) is called bag extension of another tree- decomposed graph (F, if there is graph H and a mapping (p, T) such that F is subgraph of H and (p,T) is an isomorphism from the tree-decomposed graph (H, (H) (F, T*). Define BExt (F, (F,TT", (F, to be the set of all mappings (p,T) that satisfies the above conditions, and define bExt (F,TT,, = BExt (IFTT)
Remark C.27. In other words, bag extension of dree-decomposed graph (F,T") T*) can be obtained by adding an arbitrary number of edges to F' while ensuring that each added edge is contained in tree node in 7", A immediate fact is that (p, r) is homomorphism from (F, TT) to (F,T*)
Definition C.28, Given a tree-decomposed graph (F,T") and graph G, a bag- bag-strong homomor- phism from T") to G (abbreviated "bStrHom")) is homomorphism from F to G such that, for all & E Vr, J is strong homomorphism from F(3r(() to GB (4)), i.e., {u, f) E EF(er iff (f(,,, f(r)] E (G(((T(()))- Denote (F,t G) to be the set of all bStrHom from (F,T") to G, and denote bStrHom((E;T7)))) = - (FFTHom((FF,T),G)))
The following equation straightforward:
Lemma C.29, Let M (Sub,L. be any model. For any graph G and tree-decomposed graph (F,T") S
bExt (F,TT), (F,ft)) To)) bStrHom (1,,
hom =
E (FITHESM
aut Fr (
where aut(F,T" denotes the number of automorphisms of (F, T²). Here, the summation ranges over all non-isomorphic dree-decomp)sed) graphs in SM and is well-defined as there are only finite number of graphs making the value in the summation non-zero.
Proof. The proof has similar structure the previous lemma. We define the following set of three-tuples:
SF(( (FT (... (p,T)) (F,TT) . (SttHoom((F,TT")).
Define a mappings such that (1P,T") (p, (p, go for all (Ii; (r,,T),, (e.T),9) E S. It straightforward to that is mapping from S to (FFT) namely, g possa homomorphism from F to G for all ( (F,T"), (p. ().)) S.
We then prove that is surjective. Given h Hom F, G), define (F, (F,T)), (p. T). and g as follows:
Define F be the graph obtained from F by adding edges (lu, o} 31 E VT s.t. u, (t),,, (h(u), Eg}. and let T 2 Clearly, (F, TT) ) is bag extension of (F,T").
b) Define identity mappings p(u) = a for all u E VF and T(t) = t for all t E Vr. Clearly, (p.T) E (FF"
c) Let = h. is easy to see that is a strong homomorphism from (()+(t) to Glo(3+(1)) for each E Vy. Thus, g BStrHom(( ((, Te),
34

---

Published as a conference paper at ICLR 2024
Noting that h g 9 o p. we have proved that is surjection.
We finally prove that a (Fi, (pI, ().91))))) - a (F2, T22, (2), 92) implies that there exists isomorphism (p. from (T) to (2. such that po P1 P2. i TI T2. 9i = 92 o p. We first prove that F1 F2 and 7 = T.2 (i) For any u VF, we obviously have (u( = (i(() iff u = u iff p2(u) = p2(v). (ii) Let
i ( For any u U E Vp, (p:(u), E EF or u are in the same bag of T" and (a((:(u)) ((:(())
Eg. Since Epg (ii) Finally, noting that P1 and P2 are bijective and Ep, (pi(w) = (p(u) E (P2(u)) for all u E Vp, we obtain that
Ep. iff {u,u}
91 o p1 = 92 p2. we have pi)()), E Eg, iff (o(())
Ai = F2. On the other hand, 7r = T trivially holds. The remaining procedure is almost the same as in the previous lemma.
We next show that the mapping bStrHom can be further decomposed as shown in Lemma C.31. We need an auxiliary concept:
Definition C.30. Given two tree-decomposed graphs (F,T") and (F,T") homomorphism (p. from (F,T)) to (F, T*) is called bag-strong surjective (abbreviated as "bStrSurj"") if p is bag- strong homomorphism from (F) to F and is surjective on both vertices and edges, and is an isomorphism from 7 T".. Denote BStrSurj((I, TT,, (F, "))) to be the set of all bStrSurj from (F,T") to (F,T"), and denote bStrSurj((F, (F,T") [BStrSurj((F,, T"). ())].
Lemma C.31. Let M {Sub, LF,FF) F} be any model. For any graph G and tree-decomposed graph (") E S
bStrSurj (F,,T) blso (F,,T)).) aut [, T'))
bStrHom ((trHom(([F11)) ((F,T")
E
(FTT")EMM
where F (T)) denotes the number of automorphisms of (F,T*) TT). Here, the summation ranges over all isomoroi decompoeomp))d) graphs in SM and is well-defined as there are only finite number of graphs making the value in the summation non-zero.
Proof. The proof has a similar structure to the previous lemma. We define the following set of three-tuples:
s- (.. (F, (olif,T"eES TTM EB.r))BStrSuuij (I..), ,9 Biso (l 31).
Define a mappings a such that (F.TT). g for all (A))))).()))).)) e. suffices to prove the following three statements:
1. is a mapping from S to BStrHom( (FFtoom((FFFFF..
2. is surjective;
3. a ((FI, ), (pI, ())11)))1) = ((F2, (p2, T2), 92) iff there exists an isomorphism
(ø,7) from (Fi, A1) to (F2, T22) such that " p1 P2, fom T2, 01 = 92 o p.
We will prove these statements one by one.
1. We first prove that is mapping from S to BStrHom((F,TT'.C) G). Pick any (IF, (177))) E S. Pick any 1 E Vy and u, E (T()). Then, uu, E Er iff {p(u), p(v)} E Ep (since p is strong homomorphism from F[3r(t)] to (t)() Also, p(u), p(v) E (T(T(t)) are in the same bag. Similarly. (p(u), p(u)} E Ep iff (o(p(w)),((pu)))
Fa (since g is blso). Thus, g 0 p is a bag-strong homomorphism.
2. We next prove that is surjective. Given h BStrHom F") G), define (F, "T,"), (p.7), and g as follows. First define a relation ~ on set Vr such that w ~ y iff the following hold:
h())= h(v);
35

---

Published as a conference paper at ICLR 2024
b) There exists path P in T" with endpoints f2, Vr such that u Br(t1), v (t2))) and all node t on path P satisfies that h(u) E h(3r(t)).
It is easy to see that is an equivalence relation on VF. We can thus define mapping P that respects the relation, i.c. p(u) = p(v) iff u ~ v for all u, v E Vp. Moreover, for any edge {u,0} E Er, p(u) # p(t) (since h is a homomorphism and h(u) 7 h(v)). This implies that can define F to be the homomorphie image of F such that p is the surjective homomorphism on both vertices and edges.
We then define the mapping g : VF + VG such that g(p(u)) h(u) for all u E VF. Note that is well-defined since ( = p(v) implies hu()) = h(v) for all u, v E VF, and p: VF + Vp surjective. It follows that h g o p. To prove that g is homomorphism, note that for all {z. yt E Eg. there exists an edge {u, E Ep with p(u) x. p(v) = y. which implies that (h(u), h(v)} Eg (since h is homomorphism), namely, (9(2). g(v)} Eg.
We next define tree 7o = (Vr, Fr, (p), 8 = t, and identity mapping so that T is an isomorphism from T. to T, (ignoring the labels). Set 8+(t) = p(3r(t)) for all t E Vr. We will prove that (F, T')) E SM is valid tree decomposition. It suffices to prove that Definition C. C.I(c) holds. Pick any vertex x E V5 and tree node t1 E (x(x). Then, there exists u E 3T (t1)
Br((2) such that p(u) = x. p(v) I. Therefore, there exists a path P in T" such that all node t on P satisfies that there exists with h(w)= = h((u), namely, w u. Consequently, p(u) E (7))), implying that [By((z) is connected. This proves that (F, T*) E SM, Also, (p, r) is clearly homomorphism from (F, (F, T according to Definition C.20.
v. As such, Br(t)
It remains to prove that is bag-strong homomorphism and g is a blso. Pick any t e VT and u, E (T)(). If v) & EF, then (h(u), & EG (since h is a bag-strong homomorphism). Therefore, {p(u), p(u)} & Ep (since g is homomorphism) namely, is a bag-strong homomorphism. Since p is surjective, {p(u), p(u)) ranges over all vertices in the same bag of T when E VT and u, v E (T(() are arbitrary. Therefore, g is a blso because {p(u), }(v)} & Ep iff (((u),(()) & EG.
3. We finally prove that ( (PI, (PI, n)..1) = (122 T2-), (p2, 12), 92)
implies there
exists an isomorphism (p,7) from (Fi, (11) to (F2, T23) such that po p1 = P2. о 71 72. 9i = 92 o p. Let h = 9) o pp = g2 o p2. Here, we will only prove that Fi F since the remaining procedure is almost the same as previous proofs. Since both F. and Fg are homomorphic images of F, it suffices to prove that, for all u Vp. (I()) = (1 iff the following hold:
a) h(u) = h(v);
b) There exists a path P in T" with endpoints f1, tz E Vr such that u E 3r((1), v (r(2)), and all node t on path P satisfies that h(4) E ((3(())).
On one hand, if pi(u) Br(u),t2 l2 E Br(w) such that 41, l2 E By, (PI(.)). Since [B7, (p)( is connected, there is a path P with endpoints t,, t2 such that all node on P satisfies (1( E pI (Br(1)) and thus h(u) (t). On the other hand, if (1()) + (1()) but the above items (a) and (b) hold, consider two cases:
Pi (w), we clearly have h(u)
h(u) and there exists t e
u and u are in the same bag of T. Then, PI (u) and (v) are in the same bag of 7. Since Φ1 is a blso, 91 (p1 (u)) # 91 (pr (v)), which contradicts item (a).
u and u are not in the same bag of T. Then, there exist two adjacent nodes 11, t2 on P
such that p1 (u) 3n (t1), (1(u)= & S (t2). By Definition C.4(c), 3n (tz) B/, (t)). Also, item (b) implies that there exists w (t2) such that h(w) h(u). Therefore, Pi (w) and pi (w) are two different nodes in B3 (ti) with gi (pi = h(u) = h(w)
9t (pI(w)) (w)). This contradicts the condition that ÿ1 is a blso.
This yields the desired result that 8 ~ F2. Combining the above three items concludes the proof.
36

---

Published as a conference paper at ICLR 2024
Let M LFF F) be any model. We can list all non-isomorphic rre-decomposed (labeled) Consider two types of ordering:
graphs in SM into an infinite sequence (F1, ),
Ordered by the size of the graphs F). We denote this ordering 1st. This ordering requires that for any i < j. either IVr < |Vr,, or |Vr. |Vr,, and Er 2 EEr Note that when two graphs have equal number of vertices, we place the graph with more edges to the front. When the number of edges is also the same, they can be arranged in any fixed order.
Ordered by the size of the trees T₁ We denote this ordering as 2nd. This ordering requires that IV S [rr, for any j. When the number of tree nodes is the same, they can be arranged in any fixed order.
Without loss of generality, we assume that the labels of each graph F; are integers in the range of [1, |Vr, Note that using integer labels of bounded range is already sufficient to represent all non-isomorphic labeled graphs up to a bijective label transformation. This ensures that the index is countable.
For the 1st ordering, define the following notations:
a) Let f S. x SM + N be any mapping. Define the associated (infinite) matrix A
NN+ such that A.-MMIst = =(((F,, TT',, (F,,
b) Let g S.M G + N be any mapping. Given graph G E G. define the (infinite) vector f.M.1s: = T,'),
M, E N such that PG.
PG
c) Let h 9 x G + N be any mapping. Given a graph G E G. define the (infinite) vector M,st E & such that PG.
M.M = h).
Pa
M.2d M.2d for the ordering 2nd. PG Corollary C.32. Let M (Sub, F), be any model and G, H be two graphs. Then, hom(F, G) = hommF, H) for all (F,T") E SM iff blso( (F,T", = (F,((( H) for all (F, T") SM
We can similarly define A.M.2ndd
PG
Proof. We separately consider each direction.
We first prove that if (Is G) (F))(())) for all (F,T") S then hom F, G) hom F, H) for all (F,T") E S According to Lemmas C.29 and C.31, we can rewrite the corresponding equations into matrix forms for any F E G:
PF DStrHom.
M.
A bExt,M, (A ( M,It. -1 bStrroom,M,11
'Pr
(19)
UStrSuur..M1sst aut, M,st,,, -1..s.. Mist
PF
(20)
From the above equations, we immediately obtain that Pe
M, blso, M,ist implies
PH
M,1st
PH M.lst
PG
2. We next prove that if hom(F,G) hom(F,H) for all (F,T)) e SM, then (Is G) = (F,((F,T"), for all (F,T") E S This can be seen from the following facts:
a) A M,ist is a diagonal matrix and all diagonal elements are positive integers.
A M,Itt lower triangular matrix and all diagonal elements are positive inte- gers. This is because for any two tree-composed graphs (F,, ? and (F), (EX (F,, ())) 0 only if [VA =IVe, and |Epl |Eppl-
c) M is also a lower triangular matrix and all diagonal elements are positive integers. This is because for any two tree-composed graphs (F,, (T and (Fj, T),, E.
bStrSuri((F,, (F,, (F),T")) > 0 only if [Vr.1 > IVr, or ([Vr.l = [Vr and Er.
Therefore, the composition A M,,t (AA M, -1 bStrSurj (aatt((aussa Must, is lower
triangular and is invertible (although is it an infinite matrix). We thus arrive at the desired M.st
conclusion that PG
N,..,,1st 1st PH
M,lt implies Pe:
M,so, PH
37

---

Published as a conference paper at ICLR 2024
Corollary C.33. Let M E (Sub, be any model and G. H. be two graphs Then, cnt M ((F.T).G) = ent (F,T") H) for all (F,T) E SM iff (lsT( = blso (F,T", H) for all (F,T") E S
Proof. We separately consider each direction.
We first prove that cnt ((F.T). cnt M ((F,Tt) H) for all (F,T") E SM, then blso( (F, G) (lso( )"), H) for all (F,T") ) E S According to Lemma C.23, we can rewrite Equation (18) into the matrix form for all F Peg:
PF
blso, 2,2
A blsoHom,, 2nd cnt,
PF
(21)
This immediately obtains that PG
cnt, M,2nd
= Pи
cnt. 2,2nd
implies PG
blso, M.2nd M,2nd
PH
2. We next prove that PG Lemma C.25, we have
blso.M,2nd
PH
blso, M,2nd implies PG
ent,Ad,2nd
PH
cnt.,M.nnd
According to
A M,2nd A M 2nd (A (nn) 1A bisolnj,
(22)
Moreover, we have the following facts:
a) A Aaut,M,2nd a diagonal matrix and all diagonal elements are positive integers.
b) A M, is an upper triangular matrix and all diagonal elements are positive in- tegers. This is because for any two tree-composed graphs (F) and (F)TT?) blsolnj((F., T (P,,
T) 0 only if |V4 < [Vr, I-
c) Similarly, MbsooSurj.M,2nd is a lower triangular matrix and all diagonal elements are pos- itive integers.
Unfortunately, since Mlsodnj,.M2nnd is an infinite upper triangular matrix, the inverse matrix not well-defined. Nevertheless, we can use a special property of blsoHom to complete our proof, namely, (FFo (Fj, Tyy) )) implies that the depth of T is equal
to the depth of T Therefore, denoting by A dep.d the diagonal matrix where A dep.d I[[te depth of T is d], we have
M.nnd A M. (A M2nd A dep.dd DF
A M.s.lnj..M.nnd dep.d ent, Mn2nd
PF
(23)
for all F E G. Fix any integer d 0, and assume that A ddep.d Pbl.. Mind A dep.d M, We will prove that A Adep.d cnt. = deep.d ent. Adep.dpght.MM gular with positive diagonal elements, it is invertible and thus
PH
Since A M is lower trian-
blsolnj.MM Mr. A dep.d ent, = A blsolni, dep.d PH PG
M.2dd
Moreover, by definition of unfolding tree, there only finite non-zero elements in both A dep. PG de M. and A mtt in a fixed (finite) set. In this case, the upper triangular matrix A (blsolnj.M,2m) is reduced finite-dimensional matrix and thus deep.d M, 2nd d 2 O, we obtain the desired result.
and the corresponding non-zero indices can only be
= dep.d PH M.2nd
By enumerating all
Combined with all previous results, we have arrived at the concluding corollary: Corollary C.34. Let M E LF F} be any model. For any two graphs G. xa (G) M (H) iff hom G) hom(P, H)) for all (F, T") E S
Proof. According to Corollary C.16, for any two graphs G, H. we have (G) = ( iff
Ml (F,,T) G) Mf ((F,T)) H) for all (F,Tr) E S.M. Then, Corollary C.33 im- plies that cnt M ((FTT), G) = M
M (F,T"). H) for all (F,T") E S iff blso((F,T)). H) for all (F,T") E SM Finally, Corollary C.32 implies that blso (F,T")
=
(F, H) for all (F,T") E SM iff hom(F, G) = hom (F, H) for all (F,T") E Sir. We
thus conclude the proof.
38

---

Published as a conference paper at ICLR 2024
C.3 PART 2: NESTED EAR DECOMPOSITION
In this part, we give equivalent formulations of the set S.M for any model M E (Sub, L, LF, F} using the concept of NED defined in Definition 3.3.
We first present some technical lemmas that will be used to deal with the tree decomposition of disconnected graphs.
Lemma C.35. Let M (Sub, be any model, and let (F, T") E SM be a tree-decomposed graph with (t) = Ku, Ku for some u, E Vr. Assume that F has two connected components S1, S2 C VE and S1 and u E S2 are in different components. Then, there exist tree decomposi- tions (F[Si), ( E Shh such that BT, (r1) = Nu, uB and (12) = (V,,e eB.
Proof. We can simply define 7i = EVT,,ET, with VT. = VT, ET. = ÉT, rı = =na and
Bn (t) = (6 (w) : w E (t) with
{ w if E ST, if E S2-
(w(w)= {
In other words, Ti has the same structure as but with different bags such that vertices in the same connected component as are replaced by u. It is easy to see that T is canonical tree decomposition of F[S]] following Definition C.I. Moreover, we clearly have that for all M e (Sub, L, LF, FJ. [.]S S.M, We can construct T2 (VT,, ET, ST,) by symmetry, which concludes the proof.
The above lemma can be immediately generalized into the following one:
Corollary C.36. Let M
LFF,FF be any model, and let (F, T") E S.M be a tree- decomposed graph. For each connected component S E Vp of F. pick any E VT with the minimum depth such that S n (t) f 0. Then, there exists tree decomposition T of F[S] satisfying that (FIS),T*) SM and S n (T) C. 37(s).
Lemma C.37. Let M E (Sub, L. LF,F) any model, and let T") E S be a deccopooopp graph such that F is connected. Then, for each child node t of in T and any vertex x in F(Tr(t)), there is path in [[] from x to some vertex in (T(r). Consequently, the number of connected components of F(T [4] is bounded by the number of different elements in (r(
Proof. Assume the above statement does not hold, and let S C Vetrr be the connected compo- nent of [[] such that S n (r) = 0. Note that F[S] = [[T"[t]][S] Since F is connected, there exists an edge (u. w) E Ep such that e E S and w E S. Since S is connected component of [[]] we have & VF(r<<e]] [4]], and thus both v, w $ (r()). This yields contradiction since {v, w should be contained in bag in T but (r(x) n (r(w) = 01
To reduce duplication, below we only give proofs for Local 2-GNN and Local 2-FGNN, One can easily write a proof for Subgrapph GNN based on the proof of Local 2-GNN, and write a proof for 2-FGNN based on the proof of Local 2-FGNN.
Lemma C.38, For any tree-decomposed graph (F, E st, F has a strong NED.
Proof. Based on Corollary C.36, we can assume that F is connected without loss of generality. We will prove the following stronger result: for any connected (F, T*) E St with (r) = | u, vB. F has a strong NED where are endpoints of the first ear. (For the case of u = v, the other endpoint can be arbitrary.)
The proof is based on induction over the number the vertices in T". The above statement obviously Now assume that the statement holds when |Vr| S m, and + 1. Note that for any two different children t, of r. F[T and F[T"(t") [t']] can only share vertices u, v. For each child node of denote its unique child node as i. It is easy to see that [ is canonical tree decomposition of [[] and [[]] ("] E st. However, one needs to be cautious as F[T" [f] may not be connected (unlike the original graph F). Below, we separately consider the following cases:
holds for the base case of |T
consider the case of |r|
39

---

Published as a conference paper at ICLR 2024
1. First consider the case when
In this case, Lemma C.37 impies that [+] is con- nected. According to the induction hypothesis, [[] has strong NED (denoted as P.) such that u is an endpoint of the first ear. We then merge the ear decompositions P; for all È into whole P. specify a root ear P1 in any P;, and let the first ear of other P; nest on Pi (with empty nested interval). It is easy to see that P is strong NED of F and u is an endpoint of the first ear.
2. Next consider the case when + v. In this case, without loss of generality, assume Br(() (f u, w) for some w E Vy.
Subcase 1: [ā] is connected. Then, F(T" []] has strong NED Pj such that u and w are endpoints of the first car.
a) If w t. then F(T [t]] F(T and [t]] clearly has a strong NED.
b) If w E Nr or w = u, there are two additional subcases depending on whether Ep. If fu,
Ep, then [t] has strong NED (which can be constructed from Pj by adding an ear {(u, and letting the first ear in Pi nest {u,,)) v}} (with empty nested interval). Otherwise, [[T((4])(v) has strong NED and v is an isolated vertex in [t]
{u,
c) If E NP(() and w * u, then F[T [t]] also has strong NED, which can be constructed from Pj by extending the first ear to incorporate the edge (w, d) (we still need an additional ear {[u, w)} if (u, v) E Ep).
Subcase 2: [4] is disconnected. In this subcase, Lemma C.37 implies that F[T [+]
has exactly two connected components, and u and are in different connected compo-
nents (which can be easily proved by noting that can only link to or w in F[TT(])) [+]).
We can thus invoke Lemma C.35, which shows that both connected components of F[T denoted as Fr and F2, admits tree decompositions T and T such that ( T ). F2 T22) E SL, 87, (81) ((,, u} and (4.
((w, w). Moreover, VG = V = [VT=1a] < m + 1. Therefore, according to the induction hypothesis, F1 has a strong NED Pı.1 with u as an endpoint of the first car, and F2 has a strong NED Pi,a with w as an endpoint the first ear. If {w, 4} E Er, we can extend the first ear in Pt,2 to include the edge [w, w). Finally, {u, 2} E Ep, by setting the first ear to be {u, J}}, we can merge the two NEDs Pı,1 and Pi,2 to obtain the NED of F[T [t]] such that u, endpoints of the first ear.
Overall, always have that:
a) If F[T"
[t]] is connected, then it admits a strong NED such that u, are endpoints of the
first
b) If [t] is disconnected, then it has two connected components each admitting strong NED such that u, v belong to an endpoint of the first ear for each of the two NEDs, respectively.
we can merge all NEDs of F(T [t]] a strong NED of F satisfying that u, u are endpoints of the first ear.
Finally, noting that F F= Ur. (t)== F(TT(())
to obtain
We thus conclude the proof of the induction step.
Lemma C.39, For any graph F, if F admits a strong NED, then there exists a tree decomposition T" of F' such that (F, T") E St.
Proof. We can assume that F is connected without loss of generality, as it is easy to merge the tree decompositions of different connected components to form a single tree which a tree decomposi- tion of the whole graph. We will prove the following stronger result: for any connected graph F, if F' admits a strong NED where u and v are two different endpoints of the first car, then there exists a tree decomposition I" of F such that (F, T") SL and (r) fu,, u..
The proof based on induction over the number the edges F. The above statement ob- viously holds for the base case of |E EFl < m, and consider the case of Er! = m + 1. Denote the i-th car as P, and denote P [[w,, w.).... (Wi-1, Wr)) where wn u, wi Consider the following three cases:
1. Now assume that the statement holds when
40

---

Published as a conference paper at ICLR 2024
1. Either is cut vertex in F. Without loss of generality, assumee that is a cut vertex. In this case, there must exist a child ear P. nested on P1 such that u is an endpoint of P. and I [(P)) D. We can thus split all ears into two parts Pi and P2. where P1 contains the ear P; and its descendant ears in the NED tree, and P2 contains other ears. Denote by F[Px] the connected graph induced by all edges in Pe (k E (1, 2]). Then, Pk: is strong NED of the graph F[Pu]. Since both P1 and P2 contain no more than m edges, according to the induction hypothesis, there are tree decompositions T of F(Ps] (k E (1,23) such that Br, (r1)
E st (k E 2)). We can glue the tree T and T22 into a larger tree 2 by adding new node t with (1) = ((u, u, w B. setting par- (t) = 12 and pa pa)--(r)) = L. Clearly, 7 is a valid tree decomposition of F, Br((2) = [u BB. and (F, TT=) E St
uu wB for some w E Vp, 3r, = fuu vB. and (F[Pa),
2. There is an ear P. nested on P1 with [(P))
Pi. In this case, we can split all ears into two parts P1 and P2. where Pi contains the ear P: and its descendant ears in the NED tree, and P2 contains other ears. Then, Pk is a strong NED of the graph F(Px]. Since both Pi and Pg contain more than edges, according to the induction hypothesis. there is tree decomposition T of F[Ps] such that 3r, (rx) = fu, uB and (F[Px), TT*) E St. By merging the root node, we can glue the tree T and T into larger tree T Clearly, T" is valid tree decomposition of F, (r())= = Huu BB. and (F,T") E St.
Neither u nor v is a cut vertex F and all ears P. nested on P1 satisfies 1 ((P:) & Pt. this case, we have either {wo, w1 I(P)) for all ear P. nested on P1 or { - wy I(P.) for all car P. nested on Pi (otherwise. it would contradict the definition of strong NED). Without loss of generality, assume {Wo, w1 & [(.)) for all cars P; nested on P1. Then, it is clear that I >> 1, and the subgraph FV[u} is connected and also admits a strong NED where wi and v are two endpoints of the first ear. Therefore, according to the induction hypothesis, there is a tree decomposition T of FV(u)) (u{ satisfying (F\u), T*) S and (s) fw,,, BB- We can then construct a tree T from 7o by adding two fresh nodes r and r' and setting pay- (8) = r' and pay- (r") = Set (r) fu, vB. 3T(r') = Hu, v, w B. and (t) (t) for all I E Vg.. is easy to see that the constructed 7 is a tree decomposition of F and (F, T E st. Combining the above three cases concludes the induction step.
Theorem C.40. For any graph F, F has a strong NED iff there is a tree decomposition T of F such that (F,T") E St.
Proof. This is direct consequence of Lemmas C.38 and C.39.
We next turn to Local 2-FGNN, where the proof has a similar structure as that of Local 2-GNN.
Lemma C.41. For any tree-decomposed graph (F, T") E SLF, F has an almost-strong NED.
Proof. Based on Corollary C.36, we can assume that F is connected without loss of generality. We will prove the following stronger result: for any connected (F, TT) E SLF with (7) (u,,)) F has an almost-strong NED where u, v are endpoints of the first car. (For the case of u = u, the other endpoint can be arbitrary.)
Similar to the proof of Lemma C.38, assume that the statement holds when |Vr| S m, and consider the case of |Vrll m++1. For each child node i of if only has one child, the proof exactly follows the one in Lemma C.38. Therefore, it suffices to consider the case where t has two children qı and q2- Denote (t) [[ u. v, B. 3r = I{ u,. w B. and (r(22) = {(u, w B. Since w E NN(uu [u] Ne (by definition of SLF), we can assume that w: E Nr(uj without loss of generality. Recall that (F(T" [m.]], (")))) (F(T [e=]], T" (ga)) E SLF Below, we separately consider the following cases:
1. First consider the case when = In this case, Lemma C.37 implies that both F(T and [[]"] are connected (since either u = w or {u, w) E EF). According to the induction hypothesis, both F[T [q1]] and F[T" [d2]] admit almost-strong NED such that u and are endpoints of the first ear. If w = u, we can merge the two almost-strong NEDs so that the first ear in one NED is nested on the first ear of the other (with an empty nested interval). Otherwise, the first ears in the two almost-strong NEDs share both endpoints and we can clearly merge them (in case of (u, w) Er, there is common ear {fu, w)) in both NEDs,
41

---

Published as a conference paper at ICLR 2024
which is taken only once). In both subcases, we obtain almost-strong NED of [t] such that u is an endpoint of the first ear.
2. Next consider the when o In this case, [9]1 and [92]] share only one vertex W. Note that F[T" [g]]] is connected by Lemma C.37. We separately consider two subcases:
Subcase 1: [q]]] is connected. Then, according to the induction hypothesis, (911 admits almost-strong NED Pi such that u and are endpoints of the first ear, and F [[T"[12]] admits an almost-strong NED P2 such that w and v are end- points of the first ear. (i) If w v, we can merge the two almost-strong NEDs that the first car of P2 is nested on the first car of P1 (with empty nested interval). (ii) If w u, we can merge the two almost-strong NEDs so that the first ear of P1 nested on the first ear of P2 (with empty nested interval). (iii) If w E Nr(()) and w * the first ear of P2 can be chosen as {(w, v}}. Then, we can merge the two almost-strong NEDs by gluing the first year in P1 with the ear {w, 2}} in Pz. One can see that the resulting NED is almost-strong. Overall, we always have that [4] admits an almost-strong NED such that are endpoints of the first ear.
Subcase 2: F[T [qı]] is disconnected. In this subcase, w * u. Similar to the proof of Lemma C.38, we obtain that F [qi]] has exactly two connected components. and and w are in different connected components. We can thus invoke Lemma C.35, which shows that both connected components of [4]]- denoted as F; and E. admit almost-strong NEDs P1 and P2. respectively. Moreover, u is an endpoint of the first car in Pl, and is an endpoint of the first car in Pg. Besides, F[T" [02]] admits an almost-strong NED P3 with w, v as the endpoints of the first ear. By letting the first ear of P2 nest the first of PP (with empty nested interval), can merge P2 and P3. Then, we can merge P1 and P2 U PP following the same procedure as Subcase 2 in the proof of Lemma C.38.
Overall, we always have that:
a) If [c] is connected, then it admits almost-strong NED such that u, u end- points of the first ear.
b) If [t] is disconnected, then it has two connected components each admitting an almost-strong NED such that belong to an endpoint of the first ear for each of the two NEDs, respectively.
In both subcases, it follows that [(] admits almost-strong NED with u, U as two endpoints. Noting that F = (t)= [t]] we can merge all NEDs of [t] to obtain an almost-strong NED F with u, u as two endpoints.
We thus conclude the proof of the induction step.
Lemma C.42. For any graph F, if F admits almost-strong NED, then there exists tree decom- position T of F such that (F, T") E SLF
Proof. We can assume that F is connected without loss of generality. We will prove the following stronger result: for any graph F, if F admits an almost-strong NED where u and are two different endpoints of the first car, then there exists a tree decomposition I"r of F such that (F,T") E SLF and (r) = [u,e7) BB.
Similar to the proof of Lemma C.39, assume that the statement holds when Erl I m, and consider the case of Er| = m + 1. Denote the first ear as P.- = {f [Wo w } "..,,, [w w/)} where Wo = u, wi U. Consider the following three cases:
1. Either u or u is cut vertex in F. This case is exactly the same as in Lemma C.39.
2. There is an ear P; nested on P1 with T(P:) Pt. This case is also the same as in Lemma C.39.
3. Otherwise, 1 122 2.
If there is an P. nested on P1 with {wo w1}. (wi, w2 I(P.), then / > 3. By definition of slmost- NED, there does not exist an car P, nested on P1 with (10-22 1), (w--1, w) T(P:). In this case, can split P, into parts:
42

---

Published as a conference paper at ICLR 2024
wi)). and Pi,. f(w/-1 wr)) Then, can rearrange any ear nested on P1 so that it is nested on either Pi, or Pi. In this way, we can split all cars into two sets Pu and P.. one corresponding to Pi,u and its descendant ears, and the other corresponding to Pı,+ and its descendant ears. Therefore, accord- ing to the induction hypothesis, there is tree decomposition T. of F(Pul satisfying (F(Pu),Ti)) E SLF and $7. (8) (u w1-1 B. and similarly, there is a tree decompo- sition To F[Po] satisfying (F(Pe): E S and 37, (s) = { - UB- We can then construct tree T by merging T and T and adding two fresh nodes r', where r is the root node, pay- (r') = r and pay. (s) = pay. (s') = r'. Set (T(r) = Hu, eB
Pi,u-
and 3r(r') {{ U, U. W1-1 B. It is easy
that the constructed 7 tree decom-
position of and (F, ?") E S
If there does not exist an car P. nested on P1 with {wp, w/ fo), w2] E (PP). then follow exactly the same analysis in the previous item, except that now we split P. into two parts: Pı,,- = {f Ww, wi] and PL. = Pi (f W1 ]. We can still construct a tree decomposition T" of such that (F,T") E S!F.
Combining the above three cases concludes the proof.
Theorem C.43. For any graph F, FF has an almost-strong NED iff there is a tree decomposition T" of F such that (F,T") S.F.
Proof. This is direct consequence of Lemmas C.41 and C.42.
C.4 PART 3: PERBLE GAME
In this part, we prove that SM is maximal (Definition 3.1(b)) for any M E L, F). To achieve this, we first introduce a general class of graphs which we call Fürer graphs (Fürer, 2001). Intuitions and illustrations of Fürer graphs can be found in Zhang et al. (2023a).
Definition C.44 (Fürer graphs). Given any connected graph F = Ep,EF. the Fürer graph G(F) = (Vo(P), Bo(FY, (((F)) is constructed follows:
Vo(F) (): : E Vp, X C Nr(2), |X] mod 2 = =],
BC(F) X), (v, Y)) C Vo: (2,1) E Er, E + + HyE,),,
(a(P) (I, - (x(x) V(x, X) Va(F).
Here, x E Y ++ y X holds when either (x E Y and y E X) or (x & Y and & X) holds. For each x E Vr, denote the
Metay(x) == Xxx X C NF(x), X mod 2 = 0},
(24)
which is called the meta vertices of G(F) associated to æ. Note that VG(F) = Urev, Metar(
We next define an operation called "twist":
Definition C.45 (Twist). Let G(F) = (Va(r). (a()) be the Fürer graph of F (Vr, Fip, fr), and let (x. y) E Ep be an edge of F. The twisted Fürer graph of G(F) for edge where
{z, y), is constructed as follows: (FF), {z. v}) (Va(r), (x).))
((ws))((())AA.w)) == EG(F) AllE,)) : E Metar(x), E Metar(y)),
and A is the symmetric difference operator, i.c., AÂB (A\B) U (B\)). For edge set S
{e1, ,e,] C Ey,, we further define
twist(G(F), == twist(... brisst....wisstt//ee twist(G(F), c2).
(25)
Note that Equation (25) is well-defined as the resulting graph does not depend on the order of edges
e1.- Gk for twisting.
The following result is well-known (see e.g., Zhang et al., 2023a, Corollary 1.5 and Lemma 1.7)): Theorem C.46. For any connected graph F and any set S1, C Er, (Gis) ~
( iff S1 mod 2 = [Sa] mod 2.
43

---

Published as a conference paper at ICLR 2024
This result shows that the structure of twisted Fürer graph does not depend on which edge is twsited.
Therefore, we can pick any edge {u, u} E EF and denote (F) = twist(G(F), {u, v)). We now show that (LF)),(F) can be distinguished via homomorphism information:
Theorem C.47. For any graph F, let (twisted) Fürer graphs G(F),H(F) be defined above. Then, hom(F, (F, G(F)) # hom(F. (F)).
Proof. In the proof below, we use and h to denote mappings where g VF - VG(F)) and h VF + VH(Py. The proof is divided into the following parts.
1. We first prove that there is homomorphism g E Hom(F, G(F)) satisfying g(w) M (w)) for all w E VF, but there is no homomorphism E Hom (. HFF) satisfying h(w) E (etar(w) for all w E Vr.
a) Define a mapping g VE - VG(F) such that g(wc = (w, 0) for all w E Vp. We clearly have {w, 2² E EF implies that {g(w), {(x)} E EG(F). Moreover, (a(F)(((W)) = (r(w). Therefore, g E Hom(F, GFF) indeed homomorphism. b) If we similarly define h: VF VH(F) such that h(w) = (w, 0) for all to E Vr, then for all {w, x) E EF, w}} we have (h(w), h(x)) E EH(F). but {h(u), h(t)) & EH(P) since the edge {u, v) is twisted.
remains to prove that for all h : Vr + VH(F) of the form h(w) = (w,, (w)) (for each w VF), h & Hom(F, HFF).. It suffices prove that there is an odd number of edges {w, x) Er such that (h(w), h(z)) & En(ry. Let h, h be two such mappings that differ in only one vertex 2, i.e. h(w)= = h(w) for all w o but h(z) = (z, U2) A (z, U2) = h(z). Denote D. = U.AU.. Based on the definition of Fürer graph, it follows that
for all {w, x} E Er with w # 2, # 2, we have (h(w), h(x) E EH(E) iff
{h(w), h(x)} E En(ry:
for all =] E EF with & Dz, we also have (h(w), h(z) E En(ry iff (h(w), M(=)} E EH((F):
for all (w,2) E Ep with w E D2, we have (h(w), Em(ry iff (h(w), h(x)) & FH(FF-
Since [Uz] mod 2 = 0 and [Ü_] mod 2 = O. we have |D2l mod 2 = 0 and thus the number of edges [w.x} E Ep such that (h(w), h(x)} & EH(P)) has the same parity as the number of edges such that (h(w), h(x)) & Eн(FY- Finally, noting that all mappings h can be obtained from the one in (b) by continually modifying Uw for each w E Vp and the parity remains unchanged, we have concluded the proof of this part.
2. We next prove that for any permutation т. : VF + Vp, there does not exist homomorphism h Hom(F, (F (F)) satisfying h(w) Meta (T))) for all w E Vr. Assume the conclusion does not hold and pick any h satisfying the above condition. Consider the following cases:
a) Case 1: if x is an automorphism of F. then it is easy to see that h T-
HFm(F, HF))), because [w,x} E EF = { (w)) mr (x)} E EF
Er for all w, E Vr, and (r(w) = lr(m (w) (CCE)(((r (w))) for all w E VF. Moreover, h o n satisfies that Metap (w)), yielding a contradiction to point 1.
(h(x=1(1r) 1-l==/----- (x))
(w)) E
b) Case 2: if π is not an automorphism of F, then there exists an edge {w, x) E Ep such
that (w), (xr) & Er. In this case, we must have (h(w), h(x)) & EH(F) since by
definition h(w) E (T(w)) h(z)= E (eta) and (I(w), (x)) is not an edge of F.
In both cases, h is invalid and thus there is no homomorphism h E Hom(F, ((F) satisfying h(w) E (etay(x(w)) for all w E Vp.
3. We finally prove that the following two sets have equal size (i.e., |Scl = |S (): Sc := {g E Hom F,, G(F)) Sw, x, y E VE s.t. x + g.g(x), g(y) E Metay(w)} Su (h Hom(F, (ommF,H(F) (F)) Ew,, x. y E Ve s.t. + y, h(x), h(y) Metar(w)).
44

---

Published as a conference paper at ICLR 2024
It suffices to prove that, for any proper subset U VF, we have |S +1h where Se and Sh are defined as follows:
$ g Hom(F, g(x) E U
Metap(w) Vx VF
WEU
Hom F.omF,.H(E)) H()) h(x) E U
Metar (w) Vx VF wEt
Fix U & Vp and pick z E VU Let P a simple path from a to = of the form Hwo wi).... {Wk-1, w+]] C EF where {wo, w1 {u, v}, wx =2 Define mapping a that takes g E Sg as input and outputs a mapping h VF - VH(FY:
h(x) = { g(z)
if [g(z) (wi,- wk-1), if [ wi i E [N 1],
(l(()))o
w(+1))
where we write ((x) (lo( [o(=)]])- We will prove that h E s Since we clearly have (w) E U for all w E Vr, suffices to prove that h E Hom FF, H (F)). Let (2.y) E Ep be any edge in F.
If [s(#)]o, la(v)lo & (wi.... we-th ih. then (h(x), h(v) = (o(x),9(() EG(F) Also, since (Ig(2))o, [o(v)lo} * (u.u), [gg())lo (o())) is not twisted and thus {h(z), E En(r).
If [o(z)]o & (wi.... wh-sh la(u)]o fla(=)lo. s(v)lo) * ((u,v), fwk-1, 1 then
w, for some i E [k 1]. and
wx)),
(Mx),, ((g(x))), (o(x)))). (lav))., (wo
We have
(o(z) E Ea(F)
= ([9(=))o (o(v))) + (Ia(v)lo E [g(x)]))
([g(x))o 4 w++1l) + (ga(v)lo e [g(x)]))
(h(z), E EG(F).
Also, since ([o()))o, (o(v))o} is not twisted, (M(x), Mv)) E EH(F)
If [o(=))o: [v))) E fwi,... wk-1), the analysis is similar to the above one and we can still prove that {h(x), h(w)) E EGGF) and thus (h(x), h(y) E EG(F).
If ([o(=)]o: [π()]]]] = (u, without loss of generality assume wp = u = [g(x))o
and wn [o())]o- We have
{o(z), E EGGF
< (u E [g(v))i) + E (g())))
- (u ( w21) t (u e [(())))
(h(2), & FG(P)-
However, since {u, o) is twisted, still have (h(x), h(y) EH(F)- Finally, we do not need consider the case {[g())]o. [g(v)]o} (wk-1, wa} since = U.
This proves that h E SH. Moreover, it is straightforward see that the mapping (g)) is bijection from Si to S4/ We have thus proved that |S = |
Combining the above three items, we obtain Hom(F, G(F)) > Hom H(F)), concluding the proof.
In the subsequent analysis, we will prove that for all model M considered in Theorem 3.4 and any M connected graph F, XG(F) (G(F)) = (F) (H))) if & SM The proof is based on an important technique developed in Cai et al. (1992), called the pebble game. When restricting our analysis on Fürer graphs, the pebble game be greatly simplified shown in Fürer (2001); Zhang et al. (2023a). Below, we separately describe the corresponding pebble game for each model M.
We first define key concept called the connected component.
45

---

Published as a conference paper at ICLR 2024
Definition C.48 (Connected components). Let F (VF, Eς) be connected graph and let C Vp be a vertex set, called separation vertices. We say two edges {u, u}: {x.y} E EF are in the same connected component if there is simple path { (yo. v1
{3k-1: 1: 1.8k.. satisfying that (3o. V1 = {u, v). {ik- b.kk 1 = {a, y) and yi & U for all i E [k: 1]. It is easy to see that the above relation between edges forms equivalence relation. Therefore, set, denoted by CC²(U) = [P: : i [m]] for some m, where each P. C EF is called a connected component.
can define a partition over the edge
We are now ready describe the game rule. There are two players (named Alice and Bob), graph F, and several pebbles. At the beginning, all pebbles lie outside the graph. Through the game process, some pebbles will be placed on the vertices of and thus separate the edges Ep into connected components according to Definition C.48. In each game round, Alice updates the location of pebbles, while Bob maintains a subset of connected components, ensuring that the number of selected components is odd. There are three major types of operations:
Add pebble p. Alice places a pebble p (previously outside the graph) on some vertex of F. If introducing this new pebble does not change the connected components, then Bob does nothing. Otherwise, there must be connected component P separated by p into several components P Usemm| P. for some m.. Bob will update his selected components as follows: if P is selected, then remove P' and add subset of connected components in (P1..... Pm3 while ensuring that the number of selected components in total is odd.
2. Remove a pehble p. Alice removes pebble (previously on some vertex) outside the graph. If introducing this new pebble does not change the connected components, then Bob does nothing. Otherwise, there are multiple connected component Pi..... P. getting merged into a whole P = [m] P.. Bob will update his selected components by removing all P., i E [m]] (if selected) and optionally adding P, while ensuring that the number of selected components in total odd.
3. Swap two pebbles and p'. Alice swaps the position of two pebbles and p'. This operation does not change the connected components and thus Bob does nothing.
At any time, if there is an edge {x, y} such that both endpoints hold pebbles and the connected component {(x,8) } is selected by Bob, then Bob loses the game and Alice wins. If Alice cannot win through the game process, then Bob wins.
We now define the concrete pebble game for each model M considered in this paper. In cases of Subgraph GNN, Local 2-GNN, Local 2-FGNN, and 2-FGNN, there are three pebbles Pu, Pu. Pw- As described before, all pebbles lie outside the graph at the beginning. Alice first adds the pebble Pu. (operation 1) and then adds the pebble P. (operation 1). Next, the game cyclically executes the following process:
Subgraph GNN. Alice can choose either one of the following ways to play:
Remove the pebble Pe (operation 2), and re-add the pebble Pe (operation 1).
Add the pebble P'r (operation adjacent to the pebble Pu. swap pebble p. with Pu (operation 3), and remove the pebble Pw (operation 2).
Local 2-GNN. Alice choose either of the following ways to play:
Remove the pebble P.. (operation 2), and re-add the pebble p.. (operation 1).
Remove the pebble P., (operation 2), and re-add the pebble p. (operation 1).
Add the pebble P'r (operation 1) adjacent to the pebble Pus swap pebble Pa with Pa
(operation 3), and remove the pebble Pw (operation 2).
Add the pebble P (operation 1) adjacent to the pebble Pv, swap pebble Pe with (operation 3), and remove the pebble P (operation 2).
Local 2-FGNN. Alice can choose either one of the following ways to play:
Remove the pebble P.. (operation 2), and re-add the pebble p.. (operation 1).
Remove the pebble Pe (operation 2), and re-add the pebble Pe (operation 1).
Add the pebble P (operation 1) adjacent to either pebble Pa pebble P.. swap pebble
Pw with any adjacent pebble (operation 3), and remove the pebble P (operation 2).
2-FGNN. Alice adds the pebble P.. (operation 1), swap the pebbles P., with either P.. or P (operation 3), and remove the pebble p (operation 2).
46

---

Published as a conference paper at ICLR 2024
Proposition C.49. For any model M E (Sub, FF, and any graph F. if Alice cannot win the pebble game associated to model M on graph F, then XM (G(F)) = XH(r)) (H
Proof Note that the pebble game does not depend on the vertex labels f in F. We first assume that Ev() for all 2, E Vp. Then, the labels of vertices
the vertex labels are all different, i.c., (z) & & E Vo(r), 77 E (I) are the same iff & and belong to the same meta vertex, i.c., E. E Me)a for some x E Vp. Based on Proposition C.9, XG(F) (G(F)) (F (H()) iff x K (G(F)) XM (H(F) (F)) where XM is defined in Equations (7) to (10). In this case, the pebble games above exactly correspond to the aggregation formulas in Equations (7) to (10), and we can invoke the results in Zhang et al. (2023a, Theorem I.17) to show that XG(F)
XM ( (G(F)) = ( (F) (note
that we do not need to consider the augmented Fürer graphs defined in their paper based on our label assignment). Therefore, xa (G(F)(G(F)) xM xM(r((((F)
We next consider the general case when multiple vertices can have the same label in F. How- ever, this can only make it harder to distinguish between G(F) and (FF), and we clearly have XGLF) (G(F)) = (( (H
Based on the above result, in the subsequent proof we will analyze the players' strategy in the pebble game. Surprisingly, it turms out that given a graph F, if Alice can win the game, then her strategy can be described using the tree decomposition of F defined in Definition C.6.
To illustrate this point, we need the concept of game state graph. Given graph F, a game state is three-tuple (u, u, Q) where u, E Vp U {Ø} and Q c CC=(fu, uf), denoting the vertex that holds pebble Pu. the vertex that holds pebble Pv. and subset of connected component selected by Bob, respectively. Here, the symbol 9 means that a pebble is left outside the graph. One can see that after any round, whether Alice can win the remaining game purely depends on this tuple. Now fix Alice's strategy. In each round, each game state will be transited to finite number of states depending on how Bob plays, and all states and transitions form a directed graph, which we call the game state graph. The state (u, U. Q) is called a terminal state if minpee |P| 1. It is straightforward to see that Alice wins the game at any terminal state, as stated in the following result:
Proposition C.50. Given graph F and model M E {Sub, L, LF, F), let G be the game state graph defined above corresponding to an Alice's 's strategy. Then, Alice can win the game if there is an integer such that any path in GS of length starting from the initial state (0, 0, (EF}) goes through a terminal state.
Proof. It suffices to prove that, at any terminal state, Alice can win the game. Let (u, Q) be a terminal state with {z. E Q. If {u,
fz. y). Alice already wins. If u & {x, y) and E {z, y). Alice also wins in the next round since she can add the pebble Per on some vertex w adjacent to Pa such that w) = (2.y). y). This a valid game rule for all model M. Next, E {z, y} and & {z, y}. Alice also wins in the next round since she can first remove the pebble pa and then place it on the unique vertex in {æ, y (u). This is also a valid game rule for all model M. Note the removing Pa does not merge the connected component {[2, y}} } since u & (a. v). Finally, both u & {x. y) and u & y). F only has one edge and Alice can clearly win. Combining these cases, we conclude that Alice can always win.
Based on the above proposition, game state (u, u, Q) is called unreachable if any path starting from the initial state (0, 0, {EF}) and ending at (u, v, Q) goes through some terminal state. We do not need to consider unreachable states since Alice always wins before reaching it. We next introduce an important technical concept:
Definition C.51. Given a game state graph GS, a state (u, v. (P)) is termed as "contracted" if for any transition ((u, v. (P)), (u', v', (P'))) E Egs, P' P. It is called strictly contracted if for any transition ((u, v, (P)), (u', o' (P')) Eos, P' C.P.
We have the following result:
Lemma C.52. For any model M (Sub,L, LF,.F) and any graph F, if Alice can win the pebble game associated to model M on graph F, then there exists a game state graph GS corresponding to winning strategy of Alice such that any reachable and non-terminal state strictly contracted.
47

---

Published as a conference paper at ICLR 2024
Proof. We first prove that there is strategy for Alice such that any reachable and non-terminal state is contracted. We will assume that for any reachable and non-terminal state (u, v, (P)), if there is only one transition of the form ((u, v, {P)), (u' d', {P)))) then P yf P', since making the connected component larger should be a bad strategy. (Otherwise, it is straightforward to construct new strategy for Alice satisfying the assumption.) Now suppose that there exists reachable state (u, v, {PP) that is not contracted. Note that the game state graph induced by all reachable states is a Directed Acyclic Graph (DAG), so we can choose the state (u, U. (2)) such that any path from the initial state (0, 0, {E to (u, v, {P]) does not pass any intermediate state that is not contracted. Below, we will construct a new strategy that removes the state (u, v, {PI) (making it unreachable).
Note that we clearly have u * @ and v * 9. Without loss of generality. assume that ((u, u, (P), (u, v'. (P')) is a transition such that P & P (the case of transition ((u, u, (P)), (u u, (P')) is the same by symmetry). Moreover, we can assume that P & CCr( (u]} and P E CCr((v)) (in other words, both u and v are at the boundary of the connected component P). It would be easier to analyze the case where either or are not at the boundary. We separately consider the following cases:
1. The transition ((u, v, (P)), (1, v', (P)))) corresponds to Alice removing pebble P., and plac-
ing it on v'. Let (uo, 20 Qo). ... (ur, Dr Qr) be any path from the initial state (0, 0, { {Ep}) to (u, v, {P)), and let S T be the maximal number such that 2 o We will construct new strategy for Alice as follows.
At state (we, Ut, Qt), she removes pebble P. and places it on vL, yielding (possibly multiple) states of the form (ue, v', Qt).
u. For each i and possible Qi. she will apply the original strategy at (ug, Uj Qi) to the state (ug. Qi). namely, placing pebble Pie on vertex Wj+1. swapping pebble Pu. with Pw, and leaving Pw outside the graph. (Note that she cannot remove pebble Pa first; otherwise the state (uzz Up. Qi) will not be contracted since u is at the boundary of Qz.)
For all t < i < T, we have
It follows that (uu v', Qi). (ui+i. v², Qi+1)) is a transition of the new strategy, (u,, x', Qr) is contracted, and all states of the form (u, v', Q7) is reachable in the original strategy.
We can repeat the above procedure for all paths from the initial state (0, 0, {EF}) to state (u, u, (P)). Then, in the new strategy (u, v, (P)) will be unreachable. However, the state (ue, 8t, Qt) now may violate the condition in Lemma C.52. Note that the assumption in the first paragraph is still satisfied for state (ut, Ue Qt). In this case,
recursively apply the above procedure for state (u+, Ut Q.). Note that the procedure will only repeat a finite number of times, as the length of the path from the initial state the state (ut, Ut; Qt) is strictly less than the length of the path from the initial state to the state (u, (P}).
2.
The transition ((u, U, (P)), (u, o', (P'))) corresponds to Alice placing pebble P on vi swapping Pa and Per. and removing pebble Par. In this case, we must have P g CCr((u, v,,')) (i.e., oo further splits the component P). Otherwise, the state (u, U. (P) must have only one transition and P C P', a contradiction to the first paragraph. Since P & CCp((u v, e')). is thus easy to see that, if Alice changes her strategy by just removing pebble Pa and placing it on vertex v', all transitions starting from (u, v, (P)) does not change. Therefore, we can just invoke the previous item to construct a desired strategy.
Combining the two cases, we conclude that there is a strategy for Alice such that any reachable and non-terminal state contracted. We next prove that any reachable and non-terminal state can be strictly contracted. Assume the result does not hold and the state (u, v, (P)) is reachable, non- terminal, but not strictly contracted. Then, there is a transition ((u, v, (P)), (u/, v', (P))) E Egs. Consider the following two cases:
1. P & (fu)) and P & CCF(fu)) (i.c., both u and v are at the boundary of the connected component P). It follows that u' u and of u. This implies that the game state graph is not acyclic, a contradiction.
2. Pe (C)((u)) or P CCr((u)). Without loss of generality, assume that Pe CCp( (fu)). Since (u, U, (P)) is non-terminal and not strictly contracted, there is reachable and non- terminal state (ū, 0, (P)) with either ū u or ō = u such that there is path from (u, v, (P))
48

---

Published as a conference paper at ICLR 2024
to (ū, E, (P)) and (ū, 0, (P)) is strictly contracted. We can then change the strategy state (u, v, {P)) to make strictly contracted. Concretely, Alice can remove pebble pe (which does not merge connected components selected by Bob since P CCr((u))), and place pebble Pr on the vertex that corresponds to the strategy at state (ū, 6, (P)) (possibly with a difference that u and v become exchanged). This makes the state (u, v, (P)) strictly contracted.
Combining the two cases concludes the proof.
We now ready to state the main theorem:
Theorem C.53. Let M {Sub, L,,,, F} be any model. Given any connected graph F, if Alice can win the pebble game associated with model M on graph F, then there is a tree decomposition T" of F such that (F, E SM, where SM is defined in Definition C.6.
Proof. Let G be the game state graph satisfying Lemma C.52. For each game state 8, denote by (sx the set of states s' such that (s, s') ] is transition in GS and s' contains only sin- gle connected component, ie., s' has the form (u, v. {P)). For a terminal state s of the form By definition, nextgs (0, 0, (Ep) })
(u, u, ()), define (s) ((u, 0, (1),.... (u, 0, Qm)} for some E Vr and Q1. 1..... , is the finest partition of (Cr((u)).
{xx, y, ((r,
The tree T will be recursively constructed as follows. First create the root r with By(r) Hu "I.. As we will see later, the root node will be associated with the set of states S() == ns (0, 0, {Er)). We then do the following procedure:
Let / be a leaf node in the current tree associated with a non-empty set of game states S(1) such that UU,,,, (P))ES)))) Pl > 1. For each state (u, v, {P}) E S(t), create a new node f and set its parent to be t. Pick any state (u', v', (P')) nextes (u, u, {P}). Then, there must be unique vertex w E Kn', v' (u, BB and w does not depend on which (u', , r', (P')) is picked (by definition the game rule). Set (f) (t) U (EB. Then, do the following constructions:
If there is a state of the form (u, w. {P')) E nextas (u, {P}). then create new node t' and connect it to the parent f. Set (t') = fu. w WB, and the node t' will be associated to the set of states S((')= ((u, w. (P")): (u, W. (P']) nextas (u, v, {P))]-
If there is a state of the form (w,, u, (P({P))) E nextas (u, v, (P)), then create a new node t" and connect the parent L. Set (t") = kw,, BB and the node will be associated set of states S(t") = {ww, U, {P")):
u. (P())) E nextos (u, v, {P))}.
Note that (i) either w * u or w * v (since the game state graph a DAG); (ii) both items can be used for state (u, v, {P}). which happens for FWL-type GNNs. The construction of the tree completes when each leaf node is associated with only one game state of the form (z, y, {(z, y}}). It is easy to see that the above procedure terminates after adding finite number of tree nodes.
We now prove that T" is a canonical tree decomposition of and (F,T") E S.M
1. We first prove that any edge in F is contained in some bag of T Pick any non-leaf tree node t of even depth and any of its child f, denote (u, v, P) E S(t) be the state associated with in the above construction, and denote Br (f) = fu, v, w W.. We have
p=
U
P'
ufluww E EF} U ([ E Er}.
(t')=i
Here, p' C P is a consequence Lemma C.52, and the remaining edges {u, w) or {u, w) in P because (u, v. P) is strictly contracted and must be in the interior of P. Therefore,
PU Pulluree Er]
U (()==i (EEss'))))S('')
(P' EF)) U U[la,g] E Ep 12,9 (r))
49

---

Published as a conference paper at ICLR 2024
Recursively applying the above equation yields the desired result
Ep
U
(2, E Ep :2: 31 (t)).
d, (f) odd
because (i) Uie.or) P Er, and (ii) all leaf node with S(1) (2, ((,,))))
contains an edge {æ, y in its bag.
2. We next prove that 7" satisfies the condition of Definition C.I(c). Fix any vertex E Vp, and let the tree node with minimal depth that contains w. Without loss of generality, assume that is not the root. In this case, the depth of / is odd and (7) = {u, v, wB for some u * w, v * W. Let t' be a child node of t and we have w E 3r('). Desc
remains to E Br(i), then w E (T( for all f on the path between t' and f. This actually a direct consequence Lemma C.52, because when pebble originally placed w is removed, all edges linked to will not be selected by Bob and thus any pebble can never placed on w again.
prove that for any descendent
3. T is canonical as Definition C.4 is clearly satisfied.
Finally, it also easy to see that (F,T") satisfies Definition C.6.
We thus conclude the proof.
Corollary C.54. Let M (Sub,L,LF,Fi be any model. For any connected graph F FM, let G(F) and H(F) be the Fürer graph and twisted Fürer graph with respect to F. Then, hom F, G(P)) o hom(F, (F)) and Xh (G(F) = (F))).
Proof. The proof directly follows from applying Theorems C.47 and C.53 and Proposition C.49.
Finally, we remark that our construction can be easily generalized for disconnected graphs F & J.M Let F be the disjoint union of graphs {F; : E [m]]] where each F; is the graph corresponding to a connected component of Assume that Fj the connected component with the most number of edges (in case of tie, pick the graph with the most number of vertices). Define G(F) be the disjoint union of G F1), F2, ... Fm and (F) to be the disjoint union of (FF)), F2, Fm. follows that () ((F) = XH(F) (F) and
hom F, (())
II
hom Fi, G(F)) II (hom F;, G(F)) + hom (F,, Fg U... ..... F.))) [ms]
< (E(m)
(hom( (F,, HF:)) + hom P, F, F...... Fm.)) = hom H())),
<E(m]
where we use the fact that hom F,, G(Fi)) (F, when F1 & Spasm(Fi) (which can be easily proved following Theorem C.47). This concludes the proof of the general case.
D NODE/EDGE-LEVER EXPRESSIVITY
This section aims to prove Theorem 3.7. For the ease of reading, we first restate it below:
Theorem 3.7 For all model M defined in Section 2, FM and FM (except MPNN) exist. Moreover,
MPNN: JMP {F":; F is a tree): Subgraph GNN:
FSub { F has NED with shared endpoint w) (F" (w) is a forest). Bub Fwws :F has a NED with shared endpoint w) = FF is a forest);
2-FGNN: FF {F"; F has a NED where w is an endpoint of the first ear). Ff. === (FWx" F has NED where and x endpoints of the first ear). The cases of Local 2-GNN and Local 2-FGNN are similar to 2-FGNN by replacing "NED" with "strong NED" and " "almost-strong NED". respectively.
50

---

Published as a conference paper at ICLR 2024
We remark that the definition of node/edge-level homomorphism expressivity involves only con- nected graphs for sake of simplicity. Similar to the proof of the graph-level expressivity, the proof of Theorem 3.7 consists of three parts. Among them, the proof related to tree decomposition and ear decomposition is quite similar to that of graph-level expressivity, so we only illustrate the proof sketch for clarity (Appendix D.I). However, the proof related to pebble game and counterexample graphs will require additional techniques, which is detailed in Appendix D.2.
D. RELATED TO TREE DECOMPOSITION AND EAR DECOMPOSITION
We first extend several notations that are used in Appendix C.2.
Definition D.1 (Tree decomposition for rooted graphs). Given rooted graph G and tree 7", we say is a tree decomposition of G if 7 is a tree decomposition of and all elements in u belongs the root bag, i.c., u, E (r(r) for all i.
Based on this definition, given model M, we can define S. to be the family of tree-decomposed graphs (F" T") such that (") E SM; similarly, we define S. to be the family of tree- decomposed graphs (F", such that (F, S
Definition D.2 (Bag isomorphism for rooted graphs). Given tree-decomposed graph (Fu, T") and rooted graph G where u and v have equal length, bag isomorphism from (Fu, : 7T)) to G is homomorphism from F" to G such that f is bag isomorphism from (F,T") G.
We can similarly define bag- bag-isomorphism homomorphism (blsoHom, bIsoSurj. blsoInj). bag ex- tension (bExt), and bag-strong surjective (bStrSurj) from tree-decomposed graph (F",T") tree- decomposed graph (F",T*).
Definition D.3 (Generalization of Definition C.15 for rooted graphs). Let M {Sub, LF,,FF) FJ be any model. Given a rooted graph G" and a tree-decomposed graph (F",T") define
< M ((F", T)) G*) = {
([ (u, (u, w)] Toe (M. (u, (F Tm)
E Va 3D N4 s.t.
Given a rooted graph Gho and a tree-decomposed graph (FW*, define
cnt.M ((F"T,T") T"). Gmm)) == 1 [ N+ s.t.
([raaiDD) (u,)) ao To
(F .
Here, (FM, (u, v), Tel M.(.DD (u, w1. is the depth-2D unfolding tree of G at (u,v) v) for model M.
All the following lemmas are straightforward extensions of those in Appendix C.2. Lemma D.4. Let M E (Sub, LF, be any model. For any graph G and tree-decomposed
graph (F (") E S,M, we have
blso ((F "",,"" G*)
Σ
blsoHom (IFM,T"), (fuu:T)) cnt (FFu,7t).cm
(FW,TT)ES
The edge-level result is similar.
Lemma D.5. Let M. LFF, be any model. For any tree-decomposed graphs
(F",T"), (F" TT) S.M.
blsoSurj (IFM,T), (frw (Fw, blsolnj ((ru, ,", (Fo, "iv,10) g00)
blsoHom((F" T)), (F [T))=
Σ
aut FW,
The edge-level result is similar.
Lemma D.6. Let M E (Sub, be any model. For any graph G" and tree-decomposed graph (F".T") S.M.
bExt (LFT) (T",, (Fow I.0) bStrHom ((w,,TT)) G" aut(F T
hom F" GO)
Σ
(Eo JESS
The edge-level result is similar.
51

---

Published as a conference paper at ICLR 2024
Lemma D.7. Let M E [Sub, be any model. For any graph G" and nee-decomposed graph (F", ,T) E Sh
bStrSurj ((F".T") (F (T²) blso TT"), aut(Fow (T)
(StrHom((F") """,""",CC ,")
Σ (EW,TT))EM
The edge-level result is similar.
Corollary D.8. Let M E {Sub, L, F). be any model. For any two graphs G", H. XG (u) M (v) iff hFm G*) hom(F" H)) for all (F",,T") S.M For any two graphs G Huu XH
XG (u, v) XH (w, iff home Gm=) hom _H=)) for all (FVE, T") E S.M.
M
Lemma D.9. Let M E (Sub, L,,,FF be any model.
For any rooted connected graph F", F" FM iff there is tree decomposition T of F such that (F", (T") E SAM
For any rooted connected graph Fuv, Fuu F. iff there a tree decomposition T of p such that (Fue, E S.M.
By combining the proof of previous lemmas and theorems, we can prove that both FM and FM satisfy Definition 3.6(a) for all M E (Sub, F).
D.2 COUNTEREXAMPLES
Let Fo be rooted graph that marks the special vertices W1, Wm. Assume that F & J.M (m 1) or F & FM (m 2). In this subsection, will construct pair of graphs G" and H = (v) and hom G")) + hom( (F H"). However, it turns out that, if we naïvely follow the proof in Appendix C.4 by constructing the Fürer graph and twisted Fürer graph with respect to F without considering the marked vertices w, then the graphs may no longer be counterexamples here. For example, for the edge-level expressivity, ar of F.M does not imply that F & F.M where M can be any model studied in this paper.
such that XG (u) = XH
To address the problem, instead introduce novel construction of counterexample graphs defined as follows:
Definition D.10 (Clique-augmenttr Fürer graphs). Let F be any connected graph and W1,'"" Wm E Vp be sequence of vertices. Given an integer k 2 m, the k-llique-augmented Fürer graph with respect to F", denoted by (&FF),, is the Fürer graph of F where F is the union of graph F and a k-clique that contains WI. Wm (and does not contain other vertices in F). The twisted Fürer graph of G& (FW) is denoted (F
We have the following main result:
Theorem D.11. Let M E (Sub, be any model defined Section 2.
For any rooted graph F" marking vertex w, if F & J.M, then there is vertex (w, U) Meta (w)) such that U C CV and (G (/w,,,((,,,,,0 ((w,0)) 0)) = x XH U));
For any rooted graph F" marking two vertices W1, W2. if Fw & FM,, then there are two vertices (w1,U) Meta (wn) and (w2, U2) E Meta p. (w2) such that Un, U2 C Vr and M (H ((11, U1). (w2, U2)).
.M ( 0), (w=, 0)) =
Proof. Below, we only give proof of the second item. Let f be the union of F and the 4-clique according to Definition D.10. Similar to the graph-level expressivity, we will extend the pebble game defined in Appendix C.4 to edge-level. For the edge-level pebble game, the two pebbles Pus Pa are initially placed on two predefined vertices W1, w2, and Bob initially selects a predefined set of connected components Q C CC2, (C w2)) ) (of odd size). Then, the game executes the same process as in the text above Proposition C.49. The winning criterion for the two players is also the same. We denote the above ldge- pebble game as P W2 Q).
Based on the isomorphism property of Fürer graphs established in Zhang et al. (2023a, Theorem 1.9 and and Theorem 1.17), it is straightforward see that, for any vertices E, (eta)((w)) and
52

---

Published as a conference paper at ICLR 2024
n. (ut))(wz), Xa. XG.(F
= XM XHa(Pw)(E (E'r) iff Alice cannot win the edge-level pebble game PGp (1, w2, Q) for some Q c CCp(fur, W2]) (depending on E. 17, 11)) Moreover, let s' = (w1, 0). n/ (w2, 0) and let &2 and range over all even-size subset of (w(w1) and Nr respectively, that is to say, & and 1/2 does not contain vertices that are only in the 4-clique. Then, the equivalent pebble game ranges over all Q of odd size such that every connected component in Q contains only vertices in F, ie.. Q C CCr(fust [1, W2)). Therefore, if Alice cannot win the edge- level pebble game PGp(ws, W2, Q) for some Q C CCr((w1 w2)), then there are two vertices É Meta (un)) and nn E Meta p (w2) such that &2, 1/2 Vr and x (G.(Fw)((W)) 0), (w2, U)) .M (H.(F=)((s)) n).
(5. (G,(F=)(())))
It thus remains to prove that, if Alice can win the edge-level pebble game PGp(Wi, w2, Q) for all Q C CCr(Hw1, H) then F= E F.M. To prove this result, we similarly define the game state graph as in Appendix C.4, with the only difference that the initial state is now (W1, W2. Q). The proof is divided into the following steps:
1. Assume that Q contains a single connected component, i..,, Q = (P). We will prove that, if Alice can win the game PG P W2 (P)), then there is game strategy for Alice such that for any reachable and non non-terminal state (z; y, {P')), P' C P. If it is not the case, pick any state (xr, y, {P')) such that P' E P and any path from (W1, W2, { (P)) does not pass any intermediate state that is not contracted. It follows that either w³ or we does not hold any pebble, and all edges connected to this vertex is in p.. Therefore, fr contains all vertices in the 4-clique. In this case, Alice cannot win as Bob can always keep the connected component containing all vertices in the 4-clique in subsequent rounds, i.e., Bob always selects a component containing a vertex in the 4-clique that does not hold a pebble.
(x,, y, (P'))
2. Based on the above result, in the game (G w2, {P]), the connected components se- lected by Bob are always in F, and thus the game process is the same PGr(w1, W2, (P))- We can then prove the same result as Lemma C.52. Concretely, if Alice can win the edge-level pebble game PG*(w) W2, {P)). then there exists a game state graph GS corresponding to winning strategy, such that for any transition ((z, y, is reachable and non-terminal state, we have p" C P
(P')). (x', y', (P"))) where (z, y, {P'))
Next, we can follow the same procedure in the proof of Theorem C.53 to construct a tree decomposition 7" for the subgraph F[P] containing all edges in P. such that (F[P),T") e S. and (r) = KW1, W2 B}.
4. Finally, let P ranges over all connected component in CC2 (f wy)), for each P we have a rre-decomposed graph. We can glue these tree-decomposed graphs by merging the root to obtain the tree decomposition of F, because the root bags of all T" are the same and any vertex & [wi, W2} appears in the bag of only one T", Moreover, the glued tree T' clearly satisfies that (F,T E S.M.
Combining these items shows that Fw E F.dd and concludes the proof.
Corollary D.12. Let F any rooted graph marking m vertices such that F & JM (m 1) or F & F. (m = 2), and let Gx(F") and H& (FW) be elique-augmente Fürer graphs defined above. Denote by En Vm (Fw) two vertex tuples of length where E, (w,, 0) and qj Metap(w), with nA.2 C. Vp for [m]. Then, hom(E (F")))))) +
Proof. The proof exactly parallels that of Theorem C.47 by separately considering three cases. We omit the proof for clarity.
Corollary D.13. Let M LF be any model.
For any graph Fr & J.M, , let GF(F")) and Ha(F")) be the clique-augmented Fürer graph and the corresponding twisted Fürer graph. Then, there exists two vertices E,E' such that [Ha( (E')
. hom(F"; [F"))")) # hom(F", [H((F")]S") and xG.(1=)(())
For any graph Fuo & F.,, let GT(F"R) and (A(FWT) be the clique- auggeneed Fürer graph and the corresponding twisted Fürer graph defined in Definition D. 1.1 Then, there exists
53

---

Published as a conference paper at ICLR 2024
four verriceee m. 5 nf such that hFm, [Ga(FuM)]5T) o hom(F"z [Ha (Fwrr])') and M
GGal (5: 11) = XM XHua(runy(S' 77))
Proof. The proof directly follows from Corollary D.12 and Theorem D.11.
E HIGHER-ORDER GNNS
E.1 DEFINITION OF HIGHER-ORDER GNNS
In this subsection, we give formal definitions of the CR algorithms for various higher-order GNNs, each of which generalizes model in Section 2.
Subgraph k-GNN. In a Subgraph k-GNN, a graph G is treated as a set of subgraphs KG" u VA],, where each subgraph G" is obtained from G by marking special ver- tices VG and thus there are nº subgraphs when G has vertices. Subgraph GNN Sub(k) (u, v) for each vertex in graph G Initially, XG Sub(k),(0) (u, u) = u),-.. M[u vi). then runs MPNNs independently on each
maintains color XG atp())))ttr(()))). graph G":
(ub(k).((+1) (u, v) = hash (ub(k),(() XG
XG (u, v), UXG
H (u, w) : Nc(u)B). (26)
Sub(k).(()
Sub(k) Sub(k) (u, Define Sub(k) (u) == [xx (u, v) E Val. Sub(k) (u) u Vol. We
Denote the stable color as XG
Then, the graph representation is defined as XG
Sub(k) (G) fxx
remark that Subgraph k-GNN is precisely the k- VSAN proposed in Qian et al. (2022).
Local k-GNN. Local k-GNN maintains a color XG
L(k) (u) for each vertex k-tuple u E Va. Ini-
L(K))(0) (u) = (La(w1). ... fa(wx), (u)), called the isomorphism type of vertex k-tuple u, where atp (u) is the atomic type of Then, in each iteration t 1,
tially, XG
(()) hash (x6 ((N)),0)) (u), lxa ((8)((0) (v) U No
(2)) (u))....
XG
(27)
[xe [x (
(v) : No (w)
where (w) {uu1," U1- "j+1,"" uu.): w E Na(uj)). Denote the stable
L(k) color as XG (u). The graph representation is defined as XG (G) == fxx
L(k)
L(k) (u) u E Vo
We remark that Local k-GNN is precisely the 8-k-LWL proposed in Morris al. (2020).
Local k-FGNN. Local k-FGNN is almost the same as Local k-GNN except that the update
formula is replaced by the following one:
XG
(F(R).(++1) (u) = hash
XG
LF(K).()
LF(N). (w,u2.-..uu XG (u), [(GG
LF(().(1)
(u1,0,u3,- - ,,)),
(F(K).(()
.G
(u )
(28)
We remark that Local K-FGNN is precisely the SLFWL(K) proposed in Zhang et al. (2023a).
k-FGNN. It is just the standard k-FWL (Cai al., 1992). Compared with Local k- k-FGNN, the update formula is now global:
XG
(())((+)))
(u) hash Xx
F()).(t) (u), F(.).0) F(K),())
(w,u.. up), (.. XG (u,,w u...)....)))))))
F(R).(t)
F(R)()) (ui, (. -k-- w)) : w E Vall
XG
(29)
We note that the computational complexity of Subgraph (A - 1)-GNN, Local k-GNN, and Local k-1 m) for a graph of n vertices and m edges. Moreover, it is easy to see that Subgraph O-GNN, Local 1-GNN, and Local 1-FGNN all reduce to MPNN. For K-FGNN, the computational complexity +1), which strictly higher than Subgraph (k: 1)-GNN, Local k-GNN, and Local k-FGNN.
k-FGNN is the same, i.e., (-n
54

---

Published as a conference paper at ICLR 2024
E.2 HIGHER-ORDER STRONG NED
In this subsection, we generalize the strong NED into higher-order versions. We first define the concept of higher-order ear:
Definition E.1 (k-order ear). Given integer k 2 I, a k-order ear is a graph G formed by the union of k paths Pt, Ps (possibly with zero length) plus an edge set Q satisfying the following con- ditions:
For each path P.. denote its two endpoints as uhy Uy called the outer endpoint and in- ner endpoint, respectively. Then, all edges in Q are linked between inner endpoints, i..,
Q C {(u,, By} i,j S k, # my}.
Any different paths P,, P3 do not intersect except at the inner endpoint (when V = vz).
G' is connected graph.
The endpoints of the k-order ear is defined to be all outer endpoints "1,""1 Tg.-
It is easy to see that a 2-order ear is precisely a simple path, since linking two different paths (pos- sibly with an additional edge) still yields path. Below, we denote by inner(G') and (G) the set of inner endpoints and outer endpoints in ear G, respectively. We also denote by path (G) the set of paths in ear G. It follows that [inner(G)] [out [path(G)] k. Finally, given a path P and two vertices W1, W2 in P. denote by subpath, (ungthhp(_s] (w1, W2) the subpath in P such that the two endpoints are W1, W/2
Definition E.2 (Nested interval). Let G and H be two k-order ears with inner(G) = for. Us outer(G) {ui:- .... m. and outer(H) = {wi,-.. WK), where each {uz, U2} corresponds the endpoints of a path P; E (Gt We say H is nested on G one or more endpoint wy of H E (k)) in path P., and all other vertices in H are not in G. The nested interval defined to be the union of subpaths subpath,, (w,, u.) for all i E [k] satisfying that is in P.
We give an illustration of the nested interval of two 3-order ears in Figure 2. Equipped with the above definition, we are ready to introduce the higher-order strong NED:
Definition E.3 (k-order strong NED). Given a graph G, a k-order strong NED P is a partition of the edge set Eg into a sequence of edge sets Q1,- Qus which satisfies the following conditions:
Each Q; is a k-order ear.
Any two ears Qi and Q, with indices 1 s < c do not intersect, where e is the number of connected components of G.
For each Qj with index c, is nested some k-order ear Q. with index 1 S j. Moreover, except for the endpoints of Q2 on Qi no other vertices in Qj are in any previous ear Qk for S <
Denote by I(Q,) c Q; the nested interval of Q, in Q. For all Q₁ Qx with e < <jck < m, if Q2 and Qs are nested on the same ear, then 1(2)) C I(Qx).
E.3 PROOFS IN SECTION 3.4
We first generalize the tree-decomposed graphs in Definition C.6 to higher-order versions: Definition E.4. Define four families of tree-decomposed graphs SSub(k) SL(),, SLF(K), and SF())
as follows:
a) (F,TT) SF(K) iff (F,T") satisfies Definition C.4 with width k;
b) (F,TT) E SLF(M) iff (F,T") satisfies Definition C.4 with width k, and for any tree node of odd depth, it has only one child if w & {u : No(u), u E Br(s)} where is the parent node of and is the unique vertex in By (t))
(F,TT) gL(k) iff (F, (F,T") satisfies Definition C.4 with width k, and any tree node of odd depth has only one child;
d) (F, E Sub(k)) iff (F, ()) satisfies Definition C.4 with width k, and there exists a multiset U C Vo of size [U| = l such that U C (r(()) for all E Vr.
55

---

Published as a conference paper at ICLR 2024
Then, we analogously prove the following theorems. The proofs are almost the same in Appendix C, so we omit them for clarity.
Theorem E.S. Let M (Sub(k), L(k), LF()), F(k). Then, any graphs G and H have the same representation under model M (i.e XG (G) = XH (H) if hom(F,G G) = hom(F, H) for all
M
E SM.
Theorem E.6. Let M E (Sub(k). L(k),, L(k)), F(k)) } be any model, and let F be any graph such that no tree decomposition (F, T" E S Let G(F) and HF)) be the Fiirer graph and twisted Fürer graph with respect to F. Then, hom (om(F,Gr G(F) # hom F, H(F)) and x (G(F)(G(F)) =
M XH(ry (F)).
Theorem E.7. For any graph F, there is a tree decomposition T of F such that (F, E SSub(k)
iff there exists U C Vp such that |U] S k and FAU is a forest.
Theorem E.8. For any graph F, there is a tree decomposition T of F such that (", E SL())
iff F has k-order strong NED.
Theorem E.9. For any graph F, there is a tree decomposition T of F such that (F,1") E SF(k)
iff tFF k.
E.4 EXPRESSIVITY GAP BETWEEN HIGHER-ORDER GNNS
In this subsection, we show how homomorphism expressivity can be used to build a complete ex- pressiveness hierarchy for higher-order GNNs as shown in Corollary 4.2.
Gap between Subgraph k-GNN and Local (k 1)-GNN (k 2 1). The counterexample graph is a (k: + 1) x (2k + 2) grid consisting (k: + 1) (2k + 2) vertices. First, it is easy to see that the graph is not in FrSb(kk) i.e., deleting vertices of the graph cannot yield forest. To see this, note that the graph consists of & x (2k 1) "squares", and each vertex is related to at most four squares. Therefore, deleting & vertices cannot eliminate all squares when k 2 2 (because 4k < k x (2k + 1)). clearly have that deleting vertex cannot eliminate all squares.
For the case of & =
We next show that the (k+1)xx x (2k+2) +2) grid is in FL(++1), This is also simple as shown in Figure where each color represents a k-order ear. It can be seen that the (k: + 1) x (2k + 2) grid has (k + 1)-or strong NED.
Relation between Subgraph k-GNN and k-FGNN (k 2 2). To show that (kSkb(k) & FF((), consider the (k + 2)-clique. Clearly, deleting k vertices from the (k: + 2)-clqqq yields a graph consisting of two vertices linked by an edge, which is tree. On the other hand, the treewidth of (k -l-ciique is k + (Fact C.3). So the (k 2k+ciccl is in JuSb(() but not in FF((k)
Figure 8: An 4-order strong NED of the 4 x grid graph.
To show that FF()) ş (Sub(k), we can again use the grid graph, but this time consider the kx (2k+2)
grid. On the one hand, standard result graph theory shows that the treewidth of a a b grid graph min(a, 6). On the other hand, following the similar analysis above, vertices from the & x (2k + 2) grid cannot eliminate all squares.
prove that deleting
Gap between Local k-GNN and K-FGNN (k 2 2). The counterexample graph F is the union of the following graphs Kg J K2 KK, where Ko is a (k- + 1)-clique with vertex set {ui,- ..... U&+1 }. and for i i is a new vertex (not in Ko) and v; # ny for * j. Namely, each K; has k common vertices with Ko. It is easy to construct tree decomposition 7" of F' such that (F², (F,TT) E SF(k), On the other hand, it is easy to see that the graph does not have k-order strong NED (equivalently, one easily check that F does not admit tree decomposition T satisfying (F, TT) E $L(k)).
K, is +k+ + 1)-clique with vertex set {uI,... U4-1; U3 U4+1. Ux+1) where
Gap between F-FNNN and Local (k + 1)-GNN (k 2 2). The counterexample graph is again the (A: + 1) x (2k- + 2) grid. We have proved that the graph is in (l+++) but not in (k).
Regarding Local k-IGN and Frasca et al. (2022). Finally, we remark that based on the above results, we essentially proved an open question raised in Frasca et al. (2022) regarding the expressive power of Local k-IGN (i.e., the RelGN(k) proposed in their paper). Following Zhang et al. (2023a),
56

---

Published as a conference paper at ICLR 2024
2
2
7
7
(a)
(b)
(c)
Figure 9: More illustration of NED. All NEDs in these example graphs are strong but not endpoint- shared. See Appendix F.2 for additional discussions.
it is straightforward to see that Local k-IGN is as expressive as Local k-GNN. Therefore, Local k-IGN is strictly more expressive than (k 1GNNGNN and strictly less expressive than k-FGNN
F ADDITIONAL DISCUSSIONS
F.1 REGARDING THE DEFINITION OF HOMOMORPHISM EXPRESSIVITY
In this paper, we have shown that homomorphism expressivity exists for variety of popular GNNs. Unfortunately, due to the "iff" statement in Definition 3.1, homomorphism expressivity may not always be well-defined in the general case. We remark in this subsection that, there do exist patho- logical, intentionally designed GNNs such that the homomorphism expressivity is not well-defined.
Consider simple GNN M that outputs the representation of graph as follows. G a cycle of MP (G)),
odd length, it outputs (1, L) where I is the length of the cycle. Otherwise, it outputs (0, X namely, running MPNN on the graph. follows that M strictly more powerful than MPNN, c.g., it can distinguish between the 9-cycle and three triangles, which MPNN fails to distinguish. As a result, M can count all trees under homomorphism. Moreover, it cannot count other patterns under homomorphism,
the counterexample graphs for MPNN (i.e., Fürer graphs) of odd length, so they are still counterexample graphs for model M. Therefore, the homomorphism expressivity of M should be exactly the family of forests if it exists. However, the homomorphism information of forests cannot determine the representation of model M since M is strictly more powerful than MPNN. So we conclude that JM does not exist.
cycles
Note that the above GNN construction is inherently unnatural and hardly appears in practice. Actu- ally, when a GNN defined via the message-passing, paradigm. we suspect that its homomorphism expressivity is always well-defined. As stated in Appendix B, we conjecture that, for any GNN char- acterized by color refinement algorithm that outputs stable colors, the homomorphism expressivity always exists.
F.2 REGARDING THE DEFINITION OF NED
In the main text, we have illustrated several types of NED with simple example graphs. To gain deeper understanding of Definition 3.3, this section we will present few more complex examples (see Figure 9). Notably, unlike graphs in Figure ((b), for all graphs in Figure 9 their NED contains ears such that only one endpoint in its nested ear (e.g., ears and in Figure 9()). In other words, these cars have empty nested intervals.
The presence of ears with empty nested interval stems from the fact that the corresponding graph is not biconnected (Zhang et al., 2023b). Indeed, one can check that all graphs in Definition 3.3(b) do not have cut vertices, while all graphs in Figure 9 have cut vertices. Moreover, in these examples, the number of ears with empty nested interval always equals the number of biconnected components minus one. In particular, for biconnected graphs, can proved that any NED does not contain an ear with empty nested interval.
57

---

Published as a conference paper at ICLR 2024
G HOMOMORPHISM AND SUBGRAPH COUNTING POWER
G.1 PROOF OF THEOREM 4.5
Our proof draws inspiration from a recent technique developed in Seppelt (2023). We note that the original results in Seppelt (2023) are described for unlabeled graphs, but it is easy to extend these results to labeled graphs. To begin with, we define a concept called the graph categorical product.
Definition G.1. The categorical product of two graphs G, H. denoted G x H, is graph where VGxH = Va x VH, (G h) = (la(g), (H(h)) for all E VG. E VH, and EaxH = Hig.h), (g', h()) {g.g'} E Eg, (h,h') E En}-
Lemma G.2 (Seppelt (2023)). For any graphs F, G, and H, hom(F, G x H) = hom(F, FFG). hom(F, H).
Proof. We define mapping т from HFm G) x Hom H) to Hom(F, G H) as follows. for all σ1 E Hom(F, G) and 02 E Hom(F, H). define p = T 02) where p(f) = (oi(f).02(f) for all E Vp. It is easy to see that is bijective mapping from Hom F, G) x Hom H) to Hom(F,G. H).
Definition G.3. Given graphs F and G, denote by Surj(F, G) the set of all homomorphisms from to G' that are surjective on both the vertices and edges of G, and define (F, G) [Surj( G)|-
The following proposition is straightforward (similar to Lemma C.25):
Proposition G.4. hom H) Surj(((G - H), where F ranges over all non- isomorphic graphs.
Lemma G.5. Let M be a GNN model such that its homomorphism expressivity FM exists. Given a finite set of graphs L and function C - R/(0), if
Xal (G) = XH (H)
Σ
aaL)hom (L, Σ
a(L)hom(L, H),
LEC
LEC
holds for all graphs G and H, then L C J.M.
Proof. Let n be the largest number of vertices for all graphs in L. and let E be the set of all non- isomorphic graphs with no more than n vertices. We can arrange all graphs in E into a sequence L1, L2...,
, LN satisfying the following property: [Vz.l S |Vi,4a or (VV2, = =V and | S |Er,,1)) 1) for all = 1,2, ..,,, - 1. We then define the matrices A hom Asurj, and Asub, where the elements in the 7th row and jth column are hom Lj), surj(Li, Lj), and sub(L,, Lÿ), respectively. Proposition G.4 implies that A hom Asurj sub, Since Asurj a lower triangular matrix with non- zero diagonal elements and A is an upper triangular matrix with non-zero diagonal elements, the matrix A hom is invertible.
We next extend a to a function ā C R by setting a(L) aLL) for all L C and @(L) = 0 for all L E C.C. Additionally, if xx (G) x (H), then hom G) hom F, H) for all F JM (by definition of homomorphism expressivity). Then, given any graph K È. Lemma G.2 implies that hom( F, G K) hom(F, H x K) for all F E FMM This further implies that X xc (G' x K) M
XHxk H x K) by definition of homomorphism expressivity. Therefore, Lemma G.2 implies that
Σ LEC
a ((L)hoomL, L, G)
= Σ
a(L)hoomL, H) hom L, K).
(30)
LEC
Namely,
Σ a(L)hom(L,C) G)
Σ LEC
a(L))om(L, H) hom K).
(31)
LEC
Now define vectors Pa and pv. where the 2th element of vector Pa and pи is ((L,)hom(L, G) and ā (.LL)hom(()))) La, H), respectively. We then have the following equation:
A hom PG A hom
PH-
58

---

Published as a conference paper at ICLR 2024
Since Aoom is invertible, pmm pm Therefore, ((L))om(LL,G) á a(L)hom(L, H) for all L E f. namely, hom G) hom(L., H) for all I. L. To sum up, have prove that for all graph G, H, XG
M (G) = XH M (H) implies that hom G) = hom H) for all L E L. By definition
of homomorphism expressivity, we conclude that L C F
Theorem G.6. Let M E {Sub, LF) be any model. For any graph F, if Sfaasm(())))) (F) + 0. then there exists pair of graphs G, H such that XG (G) = =x
M (H) and sub(F, sub F, G) & sub( F, H).
Proof. Recall that sub(F,G) Σ PeSpasm (F) a (FF, F) hom (F, G) where aF,, F) * for all F E Spasm? (F). If the above theorem does not hold, then for all graphs G, H. XG (G) X (H) implies that
Σ
a(F, hom (FG)=
Σ
a(F,F) hom hom(h (F,G).
PESpasm* (F)
FESpasm# (F)
Then, Lemma G.5 implies that Spasm FF) C FM yielding contradiction.
We next extend our analysis to the nodc/edge-level subgraph counting. Since the proof techniques are almost the same as the graph-level setting, we only present key definitions and lemmas below while omitting the detailed proofs for clarity.
Definition G.7. Given two rooted graphs G and H" with u E V/ and v E VH for some m E N+, the categorical product of G" and 1 denoted as (G x H)(u,,)) (fmmsim) is a rooted graph obtained from G x H by marking vertices (u1, u1),-.. (Um, Um)-
Lemma G.8 (Extension of Lemma G.2). For any rooted graphs F" H where |u] = |o| |w| m
hom O (G x H)((n,,)) (elin, (mm) = hom ,G)) hom(E H
Proposition G.9 (Extension of Proposition G.4), For any rooted graphs G H" where |u| = | = m, (G" H") = pu surj .subFs" H,),, where w ranges over all non-isomorphic rooted graphs marking m vertices.
We next present the main lemma for node-level subgraph counting. We omit the edge-level result for clarity.
Lemma G.10 (Extension of Lemma G.5). Let M be GNN model such that its node-level ho- momorphism expressivity FM exists. Given finile set of rooted graphs Ln and function Ln RR(0), if
x (u) W (0)
Σ a(I"")oom("" , L.EC,
Σ a(II") HH), L'EC,
holds for all rooted graphs G and H", then La C F.M
Theorem G.11 Let M E LFu,, be any model. For any rooted graph FW, if Spasm( F MM # V. then there exist a pair of graphs G, H and vertices Vo. v Vn. HH).
such that XG (u) XH (v) and sub(F" F",)") + sub(F"
G.2 GRAPH STATISTICS AND EXAMPLES
In this section, we list the statistics of all moderate-size graphs that can/cannot be counted for each model in Section at graph/node/edge-levll Table 4 presents the statistics under homomorphism count, while Table 5 presents the statistics under subgraph count. These tables offer a clear picture into how large the expressivity gaps are between different models. Several important findings are discussed below:
For homomorphism counting, graphs of 8 edges suffices to reveal the expressivity gaps be- tween each pair of architectures (at edge-level).
However, for subgraph counting, moderate-sizz graphs cannot reveal the gap between Local 2-GNN, Local 2-FGNN, and 2-FGNN. Moreover, Subgraph GNN already matches the power of 2-FWL in counting small subgraphs at graph-level, but it is quite weak in counting subgraphs node/edge-level.
59

---

Published as a conference paper at ICLR 2024
Subgraph counting is much more challenging than homomorphism counting. Intuitively, this because the homomorphism image of graph usually has 4-cliques, and any graph that contains 4 clique subgraph cannot be counted under homomorphism.
In Table 6, we list all subgraphs moderate size (no more than 6 vertices or edges) that can/cannot be counted by each GNN model. Here, only list the graph-level expressivity the node/edge- level expressivity involves too many non-isomorphic rooted graphs and cannot be fully presented (see Tables 4 and 5). We believe these results is comprehensive enough cover substructures of interest in the GNN community.
Table The number of (connected) graphs (or rooted graphs) of n vertices or m edges that can be counted under homomorphism by different models. These statistics be viewed quantitative expressivity comparison between models.
Number vertices n
Number of edges
3
2
3
5
6
MPNN
2
6
11
23
47
Subgraph GNN
15
12
29
76
210
Graph
Local 2-GNN
15
12
77
216
level
Local 2-FGNN
2
15
56
3
12
29
77
216
2-FGNN
2
15
56
3
12
29
77
216
All
21
112
12
30
79
227
MPNN
20
48
115
286
Subgraph GNN
3
27
88
2
5
12
31
83
228
640
Node
Local 2-GNN
3
10
44
215
2
5
13
37
113
361
1210
level
Local 2-FGNN
10
44
217
2
5
13
37
113
361
1210
2-FGNN
10
44
217
13
37
361
1210
All
11
58
407
2
5
13
37
114
367
1248
Subgraph GNN
4
18
77
340
1
3
10
33
107
347
1126
3664
Local 2-GNN
4
21
116
693
3
10
35
124
450
1665
6267
Edge
Local 2-FGNN
735
3
35
1678
6373
level
2-FGNN
21
118
735
1
3
10
35
124
451
1678
6374
All
4
23
162
1549
3
10
35
125
460
1747
6830
Table 5: The number of (connected) graphs (or rooted graphs) of vertices edges that can be subgraph-counted by different models. These statistics can be viewed as quantitative expressivity comparison between models.
Number of vertices n
Number of edges m
2
3
4
S
2
3
5
6
7
MPNN
Subgraph GNN
2
13
24
1
1
3
12
20
21
Graph level
Local 2-GNN
2
13
24
1
1
3
12
20
21
22
Local 2-FGNN
2
13
24
3
12
20
21
22
2-FGNN
13
12
20
21
112
79
227
MPNN
2
2
2
2
2
2
2
2
2
Subgraph GNN
18
27
2
5
10
16
23
30
38
Node
Local 2-GNN
10
37
2
5
13
37
72
75
86
level
Local 2-FGNN
10
37
13
37
75
2-FGNN
3
10
37
84
2
5
13
37
72
75
86
All
3
11
58
407
2
5
13
37
114
367
1248
Subgraph GNN
18
47
3
10
25
46
69
95
124
Local 2-GNN
92
208
3
10
35
179
216
Edge
level
Local 2-FGNN
4
21
92
208
3
10
35
105
171
179
216
2-FGNN
4
21
92
208
1
3
10
35
105
171
179
216
All
4
23
162
1549
3
10
35
125
460
1747
6830
60

---

Published as a conference paper at ICLR 2024
Table 6: The ability GNNs to homomorphism-count and subgraph-count different graphs F 8 edges. When more GNNs fail subgraph- count F, this table also gives a homomorphic image F Spasm(F) that can be used to construct counterexample graphs (see Section 4.2).
within bounded size of vertices
Homomorphism
Subgraph
Homomorphism
Subgraph MP
n m
F
SP LF
Sub L
F
F
Pu I72
F
SP LF
F
2
5
3
5
8
X
X
X
X
X X
3 3
S 8
X X
X X
5
X
X
4
5 10
X X
X X
4.4
5
6
4
55
6
X
5
54
6 5
5
6
5
6 6
X
5
6
X
5
X
6 6
6
57
X XXX
66
X
57
X
X X X x
66
X
XXXX
X
6
(see the next page)
61

---

Published as a conference paper at ICLR 2024
Homomorphism
Suhgraph SP LF SP LF F
Homomorphism Su L LF
Subgraph
F
nt
MP LF
F
X
X
XVVIV X
7
X
6 8
X K X X
67
X X
6 8
X X X X
67
6
X
67
XXXXX
6
X
67
68
X X
X
6
X
xxxx
67
X
6 8
XXXX X
6
67
X
X
X
6
67
X
6
X
8
8
6
8
X x
6
X X
XXxx
8
X x
X
x
8
8
MXXX X
6 9
X X X
X
8
X
X x
6
XXXXX X
X X
(see the page)
62

---

Published as a conference paper at ICLR 2024
Homomorphism
Subgraph LP
Homomorphism
Subgraph
F
F
MP
MP L LF
MP
LF
XXXXXXX XXXX
611
X
X
X X
X X
X
X
611
X
X
X
X X X X
X
X X X X XXXXX x
611
X
X
X X
X X X X
X X
611
XXXXX
X X
611
X
X X
X X X X
X X XXXXX X
612
X
X
X X
X X X X
X
61
X
10
X X X XXXXX x
612
X
X
X X X
XXXXX X XXXX
X X
10
13
X X X X
10
X XXXX X K XXXXX x
613
X X X X X X
XXXX
XXXXX
10
XXXX
65
XXXXXXXX X
6 10
X X X
XXXX X
XXXX
10
X
10
10
X XXXX X XXXX
10
X X
10
XXXX
10
X X XXXXX X X X
X X X
XXX XXXXX X XXX
61
X AXXX X X
611
XXXXX X X
7
611
XXXXXXX XXXX
XXXXX
(see the page)
63

---

Published as a conference paper at ICLR 2024
Homomorphism
Suhgraph
Homomorphism
Subgraph
F
SP LF SP
F
nt
MP Sub L LF
MP LF
F
XXX
XVVIA X
77
X
X
77
X
X
X
77
X
XXXXX X
X
77
77
17
77
78
X
77
78
X
X
17
78
77
7
X
17
11
77
X
17
11
17
X
78 D
X
77
77
77
78
X
77
x
77
77
XXXX
78
K X
77
X
78
XXXXX
77
X
7 8
XXXXX
(see the page)
64

---

Published as a conference paper at ICLR 2024
F
Homomorphism
Subgraph
Homomorphism MP Sub L LF
Subgraph
F
MP LF Su
F
MP LF
X
X
7 8
X X
78
X X X
7 8
X XXXXX x
7
X X X X X
7
7
x
78
x
7
78
x
78
7
7
x
x
8
X
7
7 8
X
x
7
8
8
7
X
78
x
XXXXX
78
78
78
x
78
X
x
87
X
87
7
X
87
X
87
XXXX
X
8
XXXXX
(see the page)
65

---

Published as a conference paper at ICLR 2024
Homomorphism
Subgraph SPb LF MP LF F
Homomorphism
Subgraph
F
ni
F
MP Sub L LF
MP LF
F
X
8 7
8
X
K X X
8
XXXXX X
8
X X X X X
8
8
8
8 8
87
8
X
8
8
XXXX
8
8
8
8 8
8
8
8 8
8
X
8 8
8
X
8
8
X
8
8
88
8 8
x
8
X
8 8
8
x
8
8
8 8
x
8 8
K X
8 8
x
8 8
XXXXX
8
X
8 8
XXXXX
(see the page)
66

---

Published as a conference paper at ICLR 2024
Subgraph SP LF SP LF F
Homomorphism
Homomorphism MP Sub L LF
Subgraph
F
F
n
F
SP LF
F
X
X
XXXX
8 8
X
8
8
X
X X
8 8
X XXXXX
8 8
X
8 8
8
8 8
X
8 8
8 8
8
X
8 8
x
8 8
X
8
8
8
8 8
X
8
x
8
8
8
8 8
8
8 8
8
8
8 8
X
8
8
8
8
8
XXXX
8 8
x
8 8
X
8 8
8
8
8 8
x
8 8
K X
8 8
x
8 8
8
XXXXX
(see the page)
67

---

Published as a conference paper at ICLR 2024
F
Homomorphism
Subgraph
F
F
Homomorphism
Suhgraph
F
SP L LF
LF
MP
LP
8 8
X
X
X
X
X
9
K X
X
8 8
X
X X
9
XXXX
9 8
X x
XXXXX
9
9 8
8
9
9 8
x
X
X
XXXX
9
8
x
8
8
9 8
X
XXXXX
XXXXX
9 8
XXXX X
68

---

Published as a conference paper at ICLR 2024
H POLYNOMIAL EXPRESSIVITY
Puny et al. (2023) proposed the equivariant graph polynomials, which are polynomials P that take real squared matrices X E m= as input and outputs P(X) E R=**" such that P is equivari- ant under permutations, i.e, P(T X) gave a concrete basis of equivariant polynomials, where each basis element Pp corresponds to a rooted multi-graph F" marking two vertices u, Puny et al. (2023) showed that when X is re- stricted to be the adjacency matrix of an undirected simple graph G, each Fas will also reduce to an undirected simple graph, and Pa (X) precisely computes the (unlabeled) homomorphism count hom( [F" Gm)) for all w, I E Vg. Besides the original definition, Puny et al. (2023) also proposed the invariant graph polynomials and node-level equivariant graph polynomials, which are similarly related to the graph-level and node-level homomorphism count.
P(X) for all permutation π E Sn- The authors
As direct consequence, if GNN model M cannot count graph F" under homomorphism, then cannot compute the equivariant/invarian graph polynomial Pp../Pp-//P.. Based on these connections, our results can be directly used to provide insights into which equivariant graph poly- nomials cannot be computed by model M. This recovers several results in their paper and answers an open problem shown below.
Corollary H.1. MPNN and +PGN++ are bounded by the Prototypical node- model and Pro- totypical edge-based model (defined in Puny et al. (2023)) for computing node-level and edge-level equivariant graph polynomials, respectively.
Proof. Without loss of generality, we assume that the corresponding graphs of all equivariant poly- nomials are connected. According to Puny et al. (2023, Proposition H.2), the Prototypical node- based model can compute all PF- where lrr is a (rooted) tree and cannot compute other graph polynomials. If MPNN is not bounded by the Prototypical node-based model, then it can compute some Pf.. where F is not a tree. However, this is impossible since MPNN can only count forests under homomorphism according Theorem 3.7. Note that the MPNN defined in their paper is equivalent to our definition when only considering connected graphs (the extra global aggregation 11 T X in their definition (9) does not improve the homomorphism expressivity).
We next turn to PPGN+ and the proof is similar (but more involved). We first show that the Prototypical edge-bases based model can compute any Paue satisfying that the treewidth of the graph F= (VF, Ep U {[u, }}}, Er) no more than If tw( (P) S 2, it is a partial 2-tree. Thus, there an ordering "1,".., Wn, of the vertex set Vp such that when deleting each vertex w/ and all incident edges in turn, we only ever delete vertices of degree at most 2. Now we claim that we can always order the two vertices u, the end, i.c., Wn-1
and Wn v. Otherwise, there is subset U C Vp such that all vertices in the induced subgraph F[U] are of degree least 3 except u, v. It follows that the tw (F(F))) > (H) 2 3 where graph H is the graph obtained from F(U) by contracting u (or v) if deg Fig (u) I 2 (or deg deg (v) S 2). This yields a contradiction and verifies the claim that we can always set wn-1 = u and Wn = v.
Now, following the proof in Puny et al. (2023, Proposition H.3), the Prototypical edge-based model can contract Fuv to graph with only two vertices u, U and thus compute the edge-level poly- nomial P P If PPGN++ is not bounded by the Prototypical edge-based model, then it can com- pute some Pf... where tw 2 3. Therefore, it can count the graph F under homomorphism at graph-level (since can already count F' at edge-level). This implies that PPGN++ is strictly more expressive than 2-FGNN (2-FWL) because we have proved that all graphs in JFF have a treewidth no more than 2. This yields a contradiction since PPGN++ is still bounded by 2-FWL in distinguishing non-isomorphic graphs.
We also provide insights into the following results in their paper: Corollary H.2. The Prototypical node-based model is not 3-mode-polynomial-eaae The Prototyp- ical edge-based model is not 6-node polde-poyyoomall exattteteettttteeeeeee and not 5-edge poldg---oyyomml-exaattt
This is simply because the triangle is not tree and the 4-clique does not have a NED (or equiva- lently, the treewidth of a 4-clique is 3). It is also clear why the degree of the edge-based polynomial is 6, which is one less than that of the node-based polynomial using the concept of NED.
69

---

Published as a conference paper at ICLR 2024
1 EXPERIMENTAL DETAILS
In this section, we provide all the experimental details in Section 5.
1.1 DATASETS
We conduct experiments on tive tasks: (i) graph bomomorphism counting, (ii) subgraph counting, (iii) ZubC-subset (Dwivedi et al., 2020), (ii) ZINC-full (Dwivedi et al., 2020), and (iv) Alchemy (Chen et al., 2019a).
HonomorphismmSubgraph Counting. For both homomorphism and subgraph counting tasks, we use the standard synthetic graph dataset constructed in Zhao et al. (2022a) (which has been used in number of papers, see e.g., Frasca et al., 2022; Huang et al., 2023; Zhang et al., 2023a). For homomorphism counting, we count the number of graphhnodelldde--eee homomor- phisms for each pattern in Table and normalize the value by the mean and variance across all graphs in the dataset. The evaluation metric of graph-level expressivity is chosen as the Mean Absolute Error (MAE). For node/edge-lever expressivity, the error on each graph is defined to be the sum of absolute error over all vertices/edges. We then report the MAE across all graphs in the dataset. This ensures that graph/node/edge-levl errors are roughly at the same scale (since hom( G) Eweve hom F" G Ew.reve hom(Fue, Gwv) for all u, U Vp). For sub- graph counting, the data processing and evaluation metric is similar homomorphism counting, but there is a slight difference in the node/edge-lever setting: there are no marked vertices in the pattern graph F (see Table 3). Instead, given a graph G' in the dataset and vertex number of subgraphs containing w that are isomorphic to F and w can be mapped to any vertex in F. Due to this difference, in the node/edge-level setting, the error on each graph is defined be the average of absolute error over all vertices/edges.
VV, we count the
ZINC. ZINC (Dwivedi et al., 2020) is a standard real-world dataset for benchmarking molecular property prediction. The dataset consists of 250K molecular graphs, and the task is to predict the constrained solubility of the given molecule. In addition to the full dataset (denoted as ZINC-full), ZINC-subset is sampled dataset with 12k molecules from the ZINC-full dataset. We train and test our models on both datasets following the standard protocol from Dwivedi et al. (2020).
Alchemy. Alchemy (Chen et al., 2019a) is another real-world dataset with 12 graph-level quan- tum mechanical properties. We follow the sampling and training protocol from Lim et al. (2023); Puny et al. (2023), using 100K samples for training, 10K samples for testing, and 10K samples for validation.
1.2 MODEL DETAILS
All models are implemented using the PyTorch (Paszke et al., 2019) framework and the PyTorch Geometric library (Fey & Lenssen, 2019). We consider four types of GNNs defined in Section 2: MPNN, Subgraph GNN, Local 2-GNN, and Local 2-FGNN. For each GNN model, the feature initialization, pressage-passing layers, and final pooling operation are separately defined below.
Initialization. On both ZINC and Alchemy datasets, each graph node is an atom. We maintain a learnalle atom embedding for each type of atom and use it to initialize features in GNN models. For MPNN, the initial feature (1)) of node u is simply the atom embedding, denoted as A (1) eN aatom(u) For other models, the initial feature h (1, v) of node pair (u, v) consists of two parts: the first part is the node embedding of v. and the second part is distance encoding that embeds the shortest path distance between u and v. as adopted in Zhang et al. (2023a). We note that while incorporating distance encoding does not increase the models' theoretical expressive power (see Zhang et al. (2023a)), it may add an inductive bias that can be helpful in real-world tasks. Formally, (di)(dii(w..)))- Here, we clip the distance to a predefined value max_dis so that there are a finite number of distance embeddings, and distances greater than the parem-ear max_dis (including the disconnected case) share the embedding.
the initial feature can be written as (0) (u, v) = at)mm(u)> D
Propagation. On both ZINC and Alchemy datasets, each edge in graph corresponds to a chemical bond and has a bond type. We maintain learnable edge embedding for each type of edges in each layer and denote the embedding of edge (u, v) in layer g() (u, v). For MPNN, we use the
70

---

Published as a conference paper at ICLR 2024
standard GIN architecture proposed in Xu al. (2019), which has the following form:
(u) = (pL
(32)
(w) GI
(w).
Σ
ReLU (FC) g0 (g0)))))))))
(33)
vENc(")
where
GIN (I, (z. y) MLP (1+ )
(34)
Here, ()() is parameterized linear transformation, ( learnable parameter, BN is the batch normalization (loffe & Szegedy, 2015), and MLP two-layer feed-forward network with an- other batch normalization in the hidden layer.
For other architectures, the I-th GNN layer analogously has the following form:
h(+1) (u, v)
()))),
(35)
where the term (u, v) is defined separately for each model:
Subgraph GNN:
ReLU (HO) (u, m)) (36)
f() 0) GI (u,
Σ
wENo(1)
Local 2-GNN:
(), GIN(
(u,
Σ
ReLU
+ 9 (u, w))
wENo(1)
+ (2)
(u,
Σ
ReLU (F w)) + (w, o)
wENo(")
(37)
Local 2-FGNN:
(u,
= GIN((.1)
(w,
ReLU (I (b
v)) + (u, w))
We (G())
+ (1.
(u,
1
Σ wENo(#)
ReLU (c (w,e)) + FC (1 (u, w)) + (0) (w. u)
(38)
For all the above GNN architectures, it can be seen that each layer only aggregates the local neigh- borhood of vertices or vertex pairs. This design will have shortcomings for disconnected graphs since vertex cannot aggregate information from other connected components matter how deep the model is (Barceló et al., 2020). Note that there do exist disconnected graphs in real-world datasets like ZINC. Therefore, on real-world datasets like ZINC and Alchemy, we also incorporate global aggregation with the following form for each layer (similar to the global aggregation in Frasca et al. (2022); Zhang et (2023a)):
(39)
wEVe
Note that the global aggregation does not increase model's theoretical expressive power according to Zhang et al. (2023a).
71

---

Published as a conference paper at ICLR 2024
Pooling, Except for edge-level tasks, final pooling layer is used to produce node-level features h(u) for all nodes u. It is implemented as follows:
En(0(u,)))
h(u)= = MLP
(40)
VEV
where MLP is 2-layer perceptron. For graph-level tasks, we further use a mean pooling layer to aggregate all h(u) and obtain the graph representation.
I.3 TRAINING DETAILS
All experiments are on single NVIDIA Tesla V100 GPU. For all tasks, we use the distance encoding papem--arameter max_dis = 5. To enable a fair comparison between models, for each task keep the same depth for different models while varying the hidden dimension number model parameters is roughly the same. Note that the dimensions are chosen such that all models roughly obey the 500K parameter budget in ZINC and Alchemy. The hidden dimension size and the number of model parameters are listed as follows. All models are trained using the Adam optimizer.
that the
Table 7: Model size in different tasks.
Hidden dimension
# Parameters
Task
Counting
ZINC
Alchemy
Counting
ZINC
Alchemy
MPNN
128
150
150
314,119
510.158
509,719
Subgraph GNN
128
120
120
314,759
503,774
503,425
Local 2-GNN
96
96
96
317,388
495,188
494,911
Local 2-FGNN
96
96
96
317,388
495,188
494,911
Homonorpphimm/Suugaap Counting. We use model depth of L 5 in all experiments. Follow- ing prior work (Huang et al., 2023), we remove all BN layers in all models. The initial learning rate chosen 0.001 and is decayed by factor of 0.9 once the MAE the validation set plateaus for 10 epochs. Each model is trained for 1200 epochs with a batch size of 512. We ran each experiment 4 times independently with different seeds and reported the average performance the last epoch. We found that the standard deviation among different seeds is negligible.
model depth of T, 6 in all experiments for both ZINC-subset and ZINC-full. Following prior work (Zhang et al., 2023a; Frasca et al., 2022), The initial learning rate is chosen as 0.001 and is decayed by a factor of 0.5 once the MAE on the validation set plateaus for 20 epochs. Each model is trained for 400 epochs on ZINC-subset and 500 epochs on ZINC-full, both with a batch size of 128. We report the MAE for the model checkpoint with the best validation performance. We ran each experiment 10 times independently with different seeds and reported the average performance as well as the standard deviation.
ZINC. We
Alchemy. We use model depth of T, 6 in all experiments. Following prior work (Lim et al., 2023; Puny et al., 2023), The initial learning rate chosen as 0.002 and decayed by a factor of 0.5 once the MAE on the validation set plateaus for 20 epochs. Each model is trained for 500 epochs with a batch size 128. We report the MAE for the model checkpoint with the best validation performance. We each experiment 10 times independently with different seeds and reported the average performance as well as the standard deviation.
1.4 PERFORMANCE OF BASELINE MODELS IN LITERATURE
For completeness, in this subsection we give a comprehensive list of the performance of GNN mod- els in the literature on ZINC and Alchemy datasets. The numbers in each table below are directly taken from the original papers.
72

---

Published as a conference paper at ICLR 2024
Table Performance of different GNN models on ZINC dataset reported in the literature.
Method
Model
Reference
Test MAE
GIN
(Xu al., 2019)
0.52610.005
GraphSAGE
(Hamilton et al., 2017)
0.398110.000
GAT
(Veličković et al., 2018)
0.384.10.000
GCN
(Kipf & Welling, 2017)
0.367#0.011
MPNN
MoNet
(Monti et al., 2017)
0.292
GatedGCN-PE
(Bresson & Laurent, 2017)
0,214+0.006
MPNN(sum)
(Gilmer et al., 2017)
0.145:10.007
PNA
(Corso et al., 2020)
0.142410.010
RingGNN
(Chen et al., 2019b)
0.353:000019
Higher-order
PPGN
(Maron al., 2019a)
0.303+40.068
GNN
PPGN
(Puny et al., 2023)
0.079++0.005
PPGN+
(Puny et al., 2023)
0.076++0.003
NGNN
(Zhang Li, 2021)
0.111#0.003
GNN-AK
(Zhao al., 2022a)
0.105++0.010
GNN-AK+
(Zhao et al., 2022a)
0.091+0.000
Subgraph GNN
ESAN
(Bevilacqua et al., 2022)
0.102++0.00
SUN
(Frasca et al.. 2022)
0.083110003
1 G-NN
(Huang al., 2023)
0.0831100001
ID-MPNN
(Zhou et al., 2023a)
0.0831100003
SetGNN
(Zhao et al., 2022b)
0.07510.003
GNN-SSWL
(Zhang al., 2023a)
0.082-10.010
Local (F)GNN
GNN-SSWL+
(Zhang et al., 2023a)
0.070.10.00S
Nº-GNN
(Feng ct al., 2023)
0.059
GSN
(Bouritsas al., 2022)
0.10110.011
Substructure-
CIN (Small)
(Bodnar al., 2021a)
0.0941000004
based GNN
CIN
(Bodnar al., 2021a)
0.079
CIN++
(Guutii et al., 2023)
0,077
SAN
(Kreuzer al., 2021)
0.139110.006
K-Subgraph SAT
(Chen et al., 2022)
0.094110.008
Graph
Graphormer
(Ying et al., 2021)
0.122
Transformer
URPE
(Luo et al., 2022)
0.086=t0.007
Graphormer-GD
(Zhang al., 2023b)
0.081 009
GPS
(Rampasek et al., 2022)
0.070++0.004
PF-GNN
(Dupty et al., 2021)
0.122::0.01
KP-GIN
(Feng et al., 2022)
0.093
SignNet
(Lim et al., 2023)
0.084++0.000
Other
PathNN
(Michel et al., 2023)
0.090+0.000
PPGN++(6
(Puny et al., 2023)
0.071+
PlanE
(Dimitrov et al., 2023)
0.076.10.003
Table Performance of different GNN models on Alchemy dataset reported in the literature.
Model
Reference
Test MAE
GIN
(Xu al., 2019)
0.100=0.000
PF-GNN
(Dupty al., 2021)
0.1111:00110
5-2-GNN
(Morris et al., 2020)
0.118110.001
Recon-GNN
(Cotta et al., 2021)
0.125
SpeqNet
(Morris et al.. 2022)
0.115+0.001
SignNet
(Lim et al., 2023)
0.113+0.002
PPGN
(Puny et al., 2023)
0.11310.001
PPGN+
(Puny et al., 2023)
0.111+-0.022
PPGN++6)
(Puny et al., 2023)
0.109-00001
73


Reviews:
[{"review_id": "eH5tgrtG4z", "reviewer": "Reviewer_aNaP", "summary": "In this paper, the authors study the set of substructures that various definitions of GNNs can distinguish. They consider the new notion of homomorphism expressivity (Definition 3.1), which intuitively means the ability of GNNs to count different substructures. In Theorem 3.3., which is the main contribution of the paper,  they use the concept of NED (Definition 3.2) to exactly express the power of GNNs in homomorphism counting for MPNNs, Subgraph GNNs, Local GNNs, and FGNNs. In a follow-up result, in Theorem 3.6., they extend their method to node-level functions on graphs. In Theorem 3.7. and Theorem 3.8., they find the homomorphism expressivity of Subgraph k-GNNs and Local k-GNNs using NEDs. In Proposition 4.4., they show how counting substructures is related to homomorphism expressivity. The paper is concluded with experiments.", "questions": "This is a well-written, interesting theoretical work on GNNs expressivity. I have a few questions:\n\n- Why are homomorphism numbers important to us? Are there any concrete applications (e.g., in biology, etc.) that they appear? I know that subgraph counts are definitely important (from molecular biology), but not sure about homomorphisms. I'm asking because the main point of characterizing the power of GNNs is to have a better understanding for practical purposes.\n\n\n- Under what conditions can the models in this paper express all subgraph counts of a  particular size (say less than k)? Indeed, how do you compare your method for counting with the other methods, like equivariant polynomials for GNNs and also recursive-based methods (like RNP-GNNs)? Is there a way to understand how recursion in RNP-GNNs can help counting all subgraphs using your theory (i.e., NEDs, etc.) and if there is any connections? I suggest discussing it a bit in the paper because recursion is a popular way to boost GNNs, and it's not clear if NEDs somewhere appear there or not.\n\n\n\n\n--------------------------------\nAfter the rebuttal: I appreciate the authors for their response and revision. As they fully addressed my questions/comments, and they added new stuff to the manuscript which I believe improved the quality of the paper, I decided to increase my score.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper is extremely well-written; the authors have spent a lot of time polishing the paper\n\n- The theoretical problem is relevant to GNNs, while most theory works in GNNs are not necessarily applicable to practical scenarios", "weaknesses": "- it's better to have more examples of different kinds of substructures in Theorem 3.3 (and how they are different from each other).\n\n- Missing discussion on some previous works: there are many papers proposed to count substructures, and it is not clear how your result is related to them.", "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": "gTYf93KvHe", "reviewer": "Reviewer_3wF7", "summary": "The paper deals with the expressive power of GNN-type architectures for graph-, node-, and edge-level representation learning. Specifically, the authors propose a framework based on graph homomorphisms to compare the expressive power of four classes of GNN architectures, namely, MPNNs, subgraph GNNs, local $k$-GNNs, folklore-WL GNNs, and their ability to count subgraphs. \n\nTo that, they extend the known results of Dell et al. connecting $k$-WL expressivity and homomorphism counts via a novel variant of nested ear decompositions. They show which kind of homomorphism counts the above three GNN types can distinguish, compare them, and shed some light on their cycle and path counting ability. \n\nFinally, they probe their theoretical results empirically, showing that increased expressivity indeed translates into increased homomorphism \n and cycle-counting ability. Further, they show a similar effect on the ZINC and Alchemy graph regression datasets.", "questions": "- Is the connectedness assumption in Definition 3.1 necessary?\n\n**Comments**\n- On page 5, in the definition of $\\mathsf{Clo_{ind}}$, there seems to be $G \\in \\mathcal{G}$ missing \n- The results of Dell et al. were previously shown in \n\nZdeněk Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph\nTheory, 64(4):330–342, August 2010. doi:10.1002/jgt.20461\n\nit might be good to cite the above paper as well", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The authors propose a unified framework to study the expressive power of various GNN-type architecture, unifying the landscape of different architectures. By that, they recover and extend several known results.\n- Clear, although dense, presentation\n- Proofs are clearly structured  \n- Good synthetic results, verifying the theoretical results", "weaknesses": "- The presentation is quite dense. It might be beneficial to push Subsection 3.3. to the appendix and expand on the other parts.\n- The experimental study on real-world datasets is quite limited. It would be nice to see a more refined analysis, e.g., analyzing subgraph occurrences and see if an architecture's performance is correlated to its ability to count different subgraphs.", "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": "WAmwbanlND", "reviewer": "Reviewer_TDGD", "summary": "This paper proposes a new theoretical way to analyze the expressive power of several types of expressive GNNs (including MPNN, k-subgraph GNN, k-local GNN, and k-local FGNN) using the concept of homomorphism. Concretely, the authors prove that the set of the base graphs a GNN can identify under the homomorphism to the input graph can be a sufficient evaluation of the expressive power of GNN. Then, the authors systemically analyze several popular GNN variants using this metric through the novel concept of nested ear decomposition (NED) and give a complete expressive hierarchy. Moreover, the proposed metric also provides a new way of analyzing the subgraph counting power of GNN variants under moderate graph size. Finally, the authors conduct experiments to verify the theorems.", "questions": "For the framework:\n1. For the subgraph GNN, the authors seem to only discuss the variant that first pool nodes within each subgraph and then pool all subgraph, which corresponds to the SWL(VS) proposed in the [1]. However, [1] also characterizes other different subgraph GNN variants with different theoretical expressive power (form a strict hierarchy). I am wondering could the proposed framework be used to analyze other variants and reveal the same result as discussed in [1].\n\n2. Can the proposed framework also be used to analyze other more general GNN frameworks like [2] or [3]? \n\n3. The subgraph counting power is proved for only moderate graph size (nodes size $\\leq$ 6 or edge size $\\leq$ 8). I am wondering, what is the major gap or obstacle for proving a more general graph size? I am guessing it is related to the equation stated in the paper that characterizes the quantitative relationship between homomorphism count and subgraph count. For graphs of general size, is the proposed theorem at least an essential condition for successful counting?\n\nFor the broader impact:\n1. So far, the paper only discusses the analysis result of the proposed framework on some existing GNN variants. I am wondering if the authors could discuss how the proposed framework can be used to analyze new GNN variants when it is proposed or how could other researchers design new powerful and efficient GNN variants based on this analysis framework.\n\n\nI understand some questions may not be easy to answer and the answer will not negatively affect my score. I think the current paper is already worth a clear acceptance. However, it is hard for me to check all the proofs given this short period of time. But I will try my best to check it later.\n\nReferences:\n\n[1] Zhang et al., A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests, ICML23.\n\n[2] Zhou et al., From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks, ICML23.\n\n[3] Feng et al., Towards arbitrarily expressive gnns in $O(n^2)$ space by rethinking folklore weisfeiler-lehman, NeurIPS23.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Although the paper may still be hard for general readers in the DL community to understand, I think the authors already did a great job of formalizing and presenting these extensive theoretical concepts and theorems.\n\n2. The proposed metric and the theoretical proofs are comprehensive and elegant. It provides a new way to reveal the strict hierarchy and the expressive gap among several high-expressive GNNs. Moreover, the subgraph counting power analysis is also impressive.", "weaknesses": "I cannot see any major weakness but have one potential minor weakness for the authors:\n\nAlthough the authors claim that the proposed framework can quantitatively analyze the expressive power of different GNN variants based on the NED, the authors didn’t characterize the exact number of NED that exists for each NED class (share-point/strong/near strong/general NED). Thus, it is still hard to see the quantitative expressive gap between each GNN variant. I understand the exact number could be hard to count but It would be excellent if the authors could at least give a rough scale for each NED class.\n\nI also have a few questions/thoughts in mind when reading the paper. Please see the question section for the details.", "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": "WYkWAbqcyH", "reviewer": "Reviewer_wf9E", "summary": "The expressive power of GNNs is commonly measured via their correspondence to Weisfeiler-Lehman (WL) graph isomorphism tests. In efforts to address limitations of the WL framework, the current paper advocates quantifying GNN expressivity through *homomorphism expressivity* — their ability to count graph substructures under homomorphism. The main theoretical contribution is a characterization of homomorphism expressivity for popular classes of GNNs in the context of graph, node, and edge representation. Among others, this allows a more fine-grained comparison between architectures, resolving several open questions. Experiments on synthetic and a couple of real-world tasks corroborate the theory, showing that the performance of GNNs aligns with the proposed expressivity measure.", "questions": "Aside from the question in weakness 1.1 above, modifying (a) in the definition of homomorphism expressivity such that, it only demands that the homomorphism counts to be equal if the representations are, makes it well-defined for all models $M$. Does this allow taking into account all possible models or is it incompatible with the results in the paper?\n\nAn additional (more minor) comment. In the paragraph at the bottom of page 5 it is stated:\n\n> “First, we highlight a key insight that homomorphism can serve as a fundamental\nexpressivity measure, which is achieved by further proving a non-trivial result that FM is maximal\n(Definition 3.1(b)).”\n\nBy definition $\\mathcal{F}^M$ is maximal, hence, it is not clear the intention of this sentence is. Was it that the existence of a maximal $\\mathcal{F}^M$ is proven?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Homomorphism expressivity provides a refreshing perspective on the expressivity of GNNs, alleviating some of the shortcomings of the popular WL framework. In particular, equivalence to WL tests can be too coarse of a measure and proving that one architecture is superior to another is often based on individual exemplar graphs. In contrast, for several GNN architectures, the current paper completely characterizes the graph homomorphisms they can count, facilitating a more fine-grained comparison and analyzing their subgraph counting ability.\n\n2. In general, the paper is well-written. The motivation and main results are clearly described, along with discussions on relevant literature and technical details. Though the paper is a bit dense. I would suggest allocating more space for providing examples and intuitions as to which types of graphs are included in the characterizations of Theorem 3.3 that are based on nested ear decompositions (NEDs). In my opinion, this can come at the expense of the extensions in Subsections 3.3 and 3.4, which can be deferred to an appendix.\n\n3. The theoretical analysis establishes elegant connections to concepts from graph theory, e.g. nested ear decompositions, which may prove useful for future work.\n\nI believe the technical contributions pose a promising step forward in formalizing the expressive power of GNNs, and therefore recommend acceptance. Yet, there are a few weaknesses (listed below). Most importantly, a technical issue with the definition of homomorphism expressivity that requires clarification.", "weaknesses": "1. There seems to be a technical issue with the definition of homomorphism expressivity (Definition 3.1). I believe it can be solved, but requires addressing or further clarification. Specifically, $\\mathcal{F}^M$ is not necessarily defined for all models $M$ since it does not take into account graphs $F$ for which there exist graphs $G$ and $H$ with equal homomorphism counts with respect to $F$ but different representations according to $M$. Homomorphism expressivity of $M$ is defined only if no such $F$ exists since it cannot be within $\\mathcal{F}^M$ and also cannot be outside $\\mathcal{F}^M$. For example, homomorphism expressivity is not defined for a universal architecture as it can assign different representations to any two non-isomorphic graphs.\n    1. Is it the case that for the GNNs considered $\\mathcal{F}^M$ is always well-defined? This seems to be indicated by Theorem 3.3 and the subsequent discussion, however, it is not clear enough. I strongly recommend elaborating upon this point near the definition to avoid confusion.\n\n    2. Homomorphism expressivity is referred throughout as a “complete” measure. Given that it is not defined for all architectures $M$, I believe this terminology can be misleading.\n\n2. Homomorphism expressivity suffers from a limitation that also exists in the WL framework: it disregards features of vertices/edges. The proposed expressivity measure takes into account only the ability to capture graph structures, assuming each vertex is associated with a unique discrete label. While identifying graph structure is indeed important, in many cases the features of vertices play an equal, if not more important role (see, e.g., [1]). I do not believe this significantly harms the quality of the current paper, and is perhaps a consideration for future work, but to me referring to homomorphism expressivity as a “complete” measure may require some hedging.\n\n[1] Liu, Renming, et al. \"Towards a Taxonomy of Graph Learning Datasets.\" arXiv preprint arXiv:2110.14809 (2021).", "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 (oral)