Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman
Authors: Jiarui Feng
Lecheng Kong
Hao Liu
Dacheng Tao
Fuhai Li
Muhan Zhang
Yixin Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph neural network
expressive power
Folklore Weisfeiler-Lehman test.
TL;DR: In this work, we propose a new $k$-Folklore WL based algorithm which hugely extend the original version and it achieve SOTA results across multiple real-world tasks.

Abstract: Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. Some works are inspired by $k$-WL/FWL (Folklore WL) and design the corresponding neural versions. Despite the high expressive power, there are serious limitations in this line of research. In particular, (1) $k$-WL/FWL requires at least $O(n^k)$ space complexity, which is impractical for large graphs even when $k=3$; (2) The design space of $k$-WL/FWL is rigid, with the only adjustable hyper-parameter being $k$. To tackle the first limitation, we propose an extension, $(k, t)$-FWL. We theoretically prove that even if we fix the space complexity to $O(n^k)$ (for any $k \geq 2$) in $(k, t)$-FWL, we can construct an expressiveness hierarchy up to solving the graph isomorphism problem. To tackle the second problem, we propose $k$-FWL+, which considers any equivariant set as neighbors instead of all nodes, thereby greatly expanding the design space of $k$-FWL. Combining these two modifications results in a flexible and powerful framework $(k, t)$-FWL+. We demonstrate $(k, t)$-FWL+ can implement most existing models with matching expressiveness. We then introduce an instance of $(k,t)$-FWL+ called Neighborhood$^2$-FWL (N$^2$-FWL), which is practically and theoretically sound. We prove that N$^2$-FWL is no less powerful than 3-WL, and can encode many substructures while only requiring $O(n^2)$ space. Finally, we design its neural version named **N$^2$-GNN** and evaluate its performance on various tasks. N$^2$-GNN achieves record-breaking results on ZINC-Subset (**0.059**), outperforming previous SOTA results by 10.6\%. Moreover, N$^2$-GNN achieves new SOTA results on the BREC dataset (**71.8\%**) among all existing high-expressive GNN methods.

Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lhmaan
Jiarui Feng'
Lecheng Kong' Hao Liu'
Dacheng Tao² Fuhai Li'
Muhan Zhang Yixin Chen
(feng jiarui, kong, liuhao, fuhai. 1i, ychen25)@wustl.ccm
dacheng. tao@gmail com, muhanōpku edu. Washington University in St. Louis 2JD Explore Academy "Peking University
Abstract
Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their ex- pressive power is limited by the 1 1-dimensional Weisfeiler-Lehman (1-WL. test. Some works are inspired by k-WII/FWL (Folklore WI.) and design the correspond- ing neural versions. Despite the high expressive power, there are serious limitations in this line research. In particular, (1) k-WL/FWL requires at least (nn") space complexity, which is impractical for large graphs even when & 3; (2) The design space k-WL/FWL rigid, with the only adjustable hyper-parameter being k. To tackle the first limitation, ically prove that even if we fix the space complexity to Onn²) (for any k 2 2) in (k: FFI, we can construct an expressiveness hierarchy up to solving the graph isomorphism problem. To tackle the second problem, we propose k-FWL+ which considers any equivariant set as neighbors instead all nodes, thereby greatly expanding the design space of k-FWL. Combining these modifications results in a flexible and powerful framework (A: F)-FWL+ We demonstrate (A: t)- FWL+ can implement most existing models with matching expressiveness. We then introduce an instance of (k, t)-FWL+ called Neighborhood which is practically and theoretically sound. We prove that N2-FWL is no less powerful than WLW, and can encode many substructures while only requiring O(n²) space. Finally, we design its neural version named N2-GNN and evaluate its performance on various tasks. N2-GNN achieves record-breaking results on ZINC-Subset (0.059) outperforming previous SOTA results by 10.6%. Moreover, N2-GNN achieves new SOTA results on the BREC dataset (7188% )) among all existing high-expressive GNN methods.
propose extension, (A:, FFWL We theoret-
(N2-FWL),
Introduction
In recent years, graph neural networks (GNNs) have become one of the most popular and powerful methods for graph representation learning, following a message passing framework [1-4]. However, the expressive power of message passing GNNs is bounded by the one-dimensional Weisfeiler- Lehman (1-WI.) test [5, 6]. As a result, numerous efforts have been made to design GNNs with higher expressive power. We provide
detailed discussion in Section 5.
Several works have drawn inspiration from the k-dimensional Weisfeiler-Lhhmen (k- WL) or Folk- lore Weisfeiler-Lehmman (k-FWL) test [7] and developed corresponding neural versions [6, 8-10]. However, k:- WLLFWWL has two inherent limitations. First, while the expressive power increases
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

with higher values of k. the space and time complexity also grows exponentially, requiring Onn*) space complexity and ( time complexity, which makes it impractical even when k: = 3. Thus, the question arises: Can we retain high expressiveness without exploding both time and space complexities? Second, the design space of WL-based algorithms is rigid, with the only adjustable nyper-parameter being k. However, there is a significant gap in expressive power even between consecutive values of k. making it hard to fune-tune the tradeoffs. Moreover, increasing the expressive power does not necessarily translate into better
performance, as it may lead to overfitting [8, 11]. Although some works try to tackle this problem [8. 10], there is still limited understanding of how to expand the design space of the original k-FWL to a broader space that enables us to identify the most appropriate instance to match the complexity of real-world tasks.
To tackle the first limitation, we notice that F-FWL and k-WL have the same space complexity but k-FWL can achieve the same expressive power as (k+I)-WL. We found the key component that allows F-FWL to have stronger power the tuple aggregation style. Enlightened by this observation, we propose (A:, F)-F which extends the tuple aggregation style in k-FWL. Specifically, in the original k-FWL,, a neighbor of k-tuple is defined by iteratively replacing its i-th element with a node u, and u traverses all nodes in the graph. In (k, F)-F we extend single node u to t-tuple of nodes and carefully design replacement scheme insert the t-tuple into a k-tuple to define its neighbor. We demonstrate that even with a fixed space complexity of ((n") (for any k 2 2). (k: F)-F can construct an expressive hierarchy capable of solving the graph isomorphism problem. To deal with the second limitation, we revisit the definition of neighborhood in k-FWI Inspired by previous works [8, 12] which consider only local neighbors (i.e., u must be connected to the k-tuple) instead of global neighbors in k-WL/FWL, we find that the neighborhood (i.e., which are used to construct a k-tuple's neighbors) can actually be extended to any equivariant set related to the k-tuple, resulting in k-FWL+. Combining the two modifications leads to novel and powerful FWL-based algorithm (k, t) FWL+. (k, t)-FWL+ is highly flexible and can be used to design different versions to fit the complexity of real-world tasks. Based on the proposed (k,, t)-FWL+ framework, we implement many different instances that are closely related to existing powerful GNN/WL models, further demonstrating the flexibility of (Ie, F.
Finally, we propose an instance of (2, FFWL++ named Neighborhood 2- that is both theoret- ically expressive and practically powerful. It considers the local neighbors of both two nodes in 2-tuple. Despite having a space complexity of O(?²), which is lower than 3-WL's (n²)) space com- plexity, this instance can still partially outperform 3-WL and is able to count many substructures. We implement a neural version named Neighborhoodd-GNN on various synthetic and real-world datasets. Our results demonstrate that N outperforms existing SOTA methods across most tasks. Particularly, it achieves 0.059 in ZINC-Subsed surpassing existing state-of the-art art models by significant margins. Mcanwhile, it achieves 71.8 % on the BREC dataset, the new SOTA among all existing high- righexxpressive GNN methods.
(N"-GNN) and evaluate its performance
2 Preliminaries
Notations. Let {.} denote a set, {.} denote a multiset (a set that allows repetition), and (.) denote a tuple. As usual, let [m] = (I.,2...., n]. Let G (V(G), F(G),, IG) be an undirected, colored graph, where V(G) = [n] is the node set with n nodes, E(G) C V(G) x VVG) is the edge set, and lo: V(G) - C is the graph coloring function with C fci....,cal denote a set of d distinct colors. Let (x())) denote a set of nodes within & hops of node and (x(v) denote the k-th hop neighbors of node and we have (u(v)) = -U%_ Qt(v). Let SPD(u, v) denote the shortest path distance between u and v. We use Ty E Rdd to denote attributes of node v V(G) and euv E ddde to denote attributes of edge (u, v) E E(G). They
usually the one-hot encoding of the node and edge color respectively. We say that two graphs G and H are isomorphic (denoted as G = H) if there exists a bijection yp: V(G) V(H) such that Vu, v E V(G), (u, v) F(G) <> (p((), (p()) E E(H)) and Vv E (G)) = (y(v))). Denote (G)) the set of k-tuples of vertices and v = (VI,..., 24) E V() k-tuple of vertices. Let S, denote the permutation group of [n] and g E S, [n] + [n] be a particular permutation. When a permutation g E S, operates on any target X, we denote it by g X. Particularly, permutation operating on an edge set FG) is g. F(G)= = (()()) v) E F(G)). A permutation operating on k-tuple v is = (g(v1), .(.)),,...,,,).. A permutation operating on graph is g G (g. VG),, g. E(G), g lc)).

---

k-dimensional Weisfeiler- test. The k-dimensional Weisfeiler-Lehmale (k-WL) test is family of algorithms used to test graph isomorphism. There are two variants of the k-WL test: k-WL and k-FWIL (Folklore WI.). We first describe the procedure of 1-WI., which is also called the color refinement algorithm [7]. Let Ca (v) (v( be the initial color of node v E V(G). At the 1-th
iteration, 1-WL updates the color of each node using the following equation:
(w) HASH (Ci=) (u) E Qi
(1)
After the algorithm converges, color histogram is constructed using the colors assigned to all nodes. the color histogram is different for two graphs, then the two graphs are non-isomorphic. However, if the color histogram is the same for two graphs, they can still be non-isomorphic.
The k- WL and k-FWL, for k 2 2, are generalizations of the I-WL, which do not color individual nodes but node tuples v E V(G)*. Let Vw/j be a k-tuple obtained by replacing the j-th element of v with w. That is Varj = (UI,-.., , w, fj+1,-... 42). The main difference between k-WL and k-FWL. lies in their aggregation way. For k-WL, the set of j-th neighbors of tuple is denoted as (v(v) = {Vw/sllw ww E V(G),, E Tk]. Instead, the w-neighbor of tuple v for k-FWL is denoted as (v) = W/n/1,Vw/2..-
Ww/k). Let Clwi (v) = (v)r((v) be the initial color for k-WL and k-FWL, respectively. They are usually the isomorphism types of tuple v. At the (-th iteration, k-WL and k-FWL update the color of each tuple according to the following equations:
WI.: Clewe HASH (v), ((C) E Q2(v) [k])):
(2)
FWL:
Ckfmi(() = HASH (c--1 (V)ua(V), &f cl-1 (u (.(()) ml E V())))
(3)
The procedure described above is repeated until convergence, resulting in a color histogram of the graph that can be compared with the histograms of other graphs. Prior research has shown that (k++ I-- and (k+1)-FFIL. are strictly more powerful than k- and k-FWI,, respectively, except in the case where 1-WL is equivalent to 2-WL. Additionally, it has been shown that k-FWL is equivalent (k+1)-WL [13, 14, 6]. We leave the additional discussion on k-WL/FWL in Appendix A.
Message passing neural networks. Message Passing Neural Networks (MPNNs) are a type of GNNs that update node representations by iteratively aggregating information from their direct neighbors. Let he be the output of MPNNs of node v E V(G) after / layers and we let ho = Ty. At l-th layer, the representation is updated by:
h U (hi-1 Um /u E (v)))) m = M' (N. (h/-1, A/ evu))
where U and M' are learnable update and message functions, usually parameterized by multi- layer perceptrons (MLPs). After L layers, MPNNs output the final representation h for all nodes e E VGG). The graph-level representation is obtained by:
hGg R( E V(G))),
(5)
where R is a readout function. The expressive power of MPNNs is at most as powerful as 1-WL [5, 6].
3
Rethinking and extending the Folklore Weisfeiler-Lehman test
3.1 Rethinking and extending the aggregation style in k-FWL
Increasing & can increase the expressive power of k-FWL for distinguishing graph structures. How- ever, increasing brings significant memory costs, k-FWL requires O(n²) memory. It becomes impractical even when k = 3 [9]. Therefore, it is natural to ask:
Can we achieve higher expressive power without exploding the memory cost?
To achieve this goal, we first notice that k-FWL has a higher expressive power than k- WL but only requires the same Onn*) memory cost. To understand why, let's use 2-WI. and 2-FWI as examples and rewrite Equation (2) and Equation (3):
2-WL: Chur(U1, U2) = HASH (Coul (V1, 22). C/ (vi, w)lw V(G) &C w v(G))), v2), 2-FWL: Caru(Ui, U2) HASH (h--1 (V), El C (Vi, w), Ct (w, u2)) w T (((())))
3

---

Construction Neighborhood tuple (M, P²)
mny ( v2)
High-order structures
Solect element
Select index
x
Select element
Select indiex
W
Recover
Wi
P2
wy
Select elements
Select Indians
x
W
Figure Illustration of the construction neighborhood tuple (iw,, (vi, 02) in (2, 2WFLL We sequentially select 0, 2 clements from (W1, w2) replace 0, 1, elements in (v1, v2), resulting in three sub-tuple of length 1,4, 4, I, respectively. The final neighborhood tuple the concatenation of three sub-tuples. We can easily recover high-order graph structures from the constructed neighborhood tuple with the isomorphism type of 2-tuples.
where Cu (v1, v2) and C2f (v1, v2) are the color of tuple (11, (2) at iteration / for 2-WL and 2-FWL, respectively. We can see the key difference between 2-WL and 2-FWL is that: in 2-FWL, a tuple of color (C2fur(1) (21, w), Cr (we, 02)) is aggregated. While in 2-WL, the colors of nodes are considered separate multisets. To understand why the first aggregation is more powerful, we can further rewrite the update equation of 2-FWII as follows:
C2fue U2) HASH (I (2 v2), C2 (v2, w) 22 u2)) |w E v(G)B)
is easy to verify that the above equation is equivalent to the original one. This means that 2-FWL updates the color of tuple (v1, 02) by aggregating different tuples of ((V1, 22); (01, w), (w, 22)), which can be viewed as aggregating information of 3-tuples (V1, 02, w). For example, HASH(C2)/e (v1, 12), CD ww w), C2 12)) can fully recover the isomorphism type of tu- ple (vi, U2, w) used in 3-WL. The above observations can be easily extended to k-FWL. The key insight here is that tuple-style aggregation is the key to lifting the expressive power of KLF.L Since aggregating k-tuple can boost the expressive power of k-FWL be equivalent to (k+1) WL without the increase of space complexity, we may wonder, can we further extend the size of the tuple?
We first introduce the neighborhood tuple to extend the original w-neighbor used in k-FWL. Let (<(v) (v) denote a neighborhood tuple related to k-tuple v and t-tuple w. The neighborhood tuple contains all possible results such that we sequentially select m E [0, 1. ... min(k, t)] elements from w to replace m elements in V. For each m, we first select all possible combinations of m-tuples (no repeated elements) from tuple w with pre-defined order form new tuple, denoted as P... (w). At the same time, we select all possible combinations of m indices from i (1, 11,2,...RR k) with a pre-defined order form another new tuple Pm. (1). Finally,
iterate all (w',1") E (w) x Pm to get a I. [w][ Pm (iul-suubtuple where for each (w', I') we replace the elements with indices i' in the original v with w'. The final neighborhood tuple the concatenation of all sub-tuples. Note that the pre-defined orders can be flexible as long as they are consistent for any k and t.
Here is example of possible construction of neighborhood tuple when k = 2. Let Q (um (V1, 02) denote the neighborhood tuple. In this case, we need to enumerate m in [0, 1, 1,2). First, when = O, we select 0 elements from (wi, w2) to replace (v1, v2). result- ing in a sub-tuple with only one element ((r), 82)). Next, when m = 1. we sequentially se- lect wi and w2, resulting in Pi(w) = (wi, W2). Similarly, can get (i) the final sub-tuple is ((0), w1), (U1, W2), (Wi, 02), (w2, U2)). The case m = is simple and have the result sub-tuple be ([w), W2))- By concatenating all three sub-tuples, we have P (mm ao2) (01, 12) = ((0), 02), (11, ) (V1, W2), (Wi, 22), (w2, U2), (wi, W2)). The construction pro- cedure is shown in Figure By default, we adopt the above order in QW in the rest of the paper if k = f = 2. We leave a more formal definition of the neighborhood tuple ( in Appendix A.
(2, 1). Thus,
With the neighborhood tuple, we are ready to introduce (k: F)-FWL, which extends k-FWL by extending the tuple size in the update function. Let (e)) be the color of tuple at iteration for (k,, FFLL the update function of (k, F)-FWL is:
(k, F)FL: Cver = HASH C1-1 Cn (v), Hl C ( (EV'(())). 66)

---

where H-Bt is hierarchical multiset over t-tuples. In a hierarchical multiset fvvv E Be) elements are grouped hierarchically according to the node order of the tuple. For example, to construct (11, 02, (2), 03) E (3) 3' from {(1,, 12, (r), 02, va) E (*))) H, we first group together all elements with the same v2 and 13- That is, Vuz, i3 E V(G), we denote f(22, v3) = [0). 12, 23)|e1 E V as the grouped result. Next, use the similar procedure, we have Veg E VG), t(eg) = f v3
( 02 E B.) J. Finally, we group all possible 0g E ((G) to
get (11, U2, 23) 03) U2, 23) E V (G) = [t(vv)]v3 E V(G)
It is easy to see (k. 1)-FWL is equivalent to k-FWL under our definition of Q (v). Further, as we only need to maintain representations of all k-tuples. (k, t)-FL has a fixed space complexity of (n**). Here we show the expressive power of (k:, ()-FWI
Proposition 3.1. For l 2 2 and t 2 1, ift 2 n k. (k, t)-FFL can solve the graph isomorphism problems with the size of the graph less than or equal to n.
Theorem 3.2. For k 2 2, 2 1, (kc t)-FWL is at most as powerful as (k + t)-WL In particular, (k, 1)-FWL is as powerful as (k + 1)-WL
Proposition 3.3. For k 2 2, t 2 1, (kt, f. 1)-FWI. is strictly more powerful than (k. (K-L)) (k + FFWL is strictly more powerful than (k, t)FFWL
We leave all formal proofs and complexity analysis in Appendix B. Briefly speaking, even if we fix the size of k. (ks, ()-FWI. can still construct expressive hierarchy by varying f. Further, if t is large enough, (k:, F)-FWL can actually enumerate all possible combinations of tuples with the size of the graph, and thus equivalent the relational pooling on graph [15]. It is worth noting that the size of Q (v) will grow exponentially with an increase in the size of t. However, the key contribution of (k, FFLL is that even when 2, (k, f)-FWL can still construct an expressive hierarchy for solving graph isomorphism problems. Therefore, high-order embedding may not be necessary for building high-expressivity WL algorithms. Note that our (ks, FFLL is also different from subgraph GNNs such as k, I-WL [16] and I-OSAN [17], where l-tuples are labeled independently to enable learning k-tuple representations all I-tuple'' subgraphs, resulting in ((n++)) space complexity.
3.2 Rethinking and extending the aggregation scope of k-FWL
Another problem of kFFWL is its limited design space, as the only adjustable hyperparameter is k. is well known that there is a huge gap in expressive power even if we increase from & to h: + 1. For example, 1-WL cannot count any cycle even with a length of 3, but 2-FWL can already count up to 7-cycle [18-20]. Moreover, increasing the expressive power does not always bring better performance when designing the corresponding neural version as it quickly leads to overfitting [6, 9, 11] I1]. Therefore, we ask another question:
Can we extend the k-FWL to a more flexible and fine-grained design space?
To address this issue, we identify that the inflexibility of k-FWL's design space arises from the definition of the neighbor used in the aggregation step. Unlike 1-WL, k-FWL lacks the concept of local neighbors and instead requires the aggregation of all IV global neighbors to update the color of each tuple v. Recently, some works have extended k-WL by incorporating local information [8, 12]. Inspired by previous works, we find that the definition of neighbor can actually be much more flexible than just considering local neighbors or global neighbors. Specifically, for each k-tuple v in graph G, we define equivariant set E.5(v) to be the neighbors set of tuple and propose k-FWL+
Definition 3.4. An equivariant set ES(() is a set of nodes related to v and equivariant given the permutation g E Sn. That is, Vu ES( in graph G implies g(w) ES(g v) in graph g G.
Some nature equivariant sets ES(u) including N(G)), and Qx(v), Let LetCk, fu (v) be the color of tuple v at iteration for k-FWL+, we have:
k- F-FWL+: Ckfuet (v) = ( (v), &l CCi (u)lu E Q[(v)) lw E ES()) (7)
The key of k-FWL+ is that the equivariant set ES(v) can be any set of nodes as long as it is equivariant any permutation g E S,, For example, if ES((v) V(G), the k-FWL+ will reduce to the original k-FWL. Instead, if ES(v) = (c.). it becomes the localized k-FWL [12]. We can also design other more innovative equivariant sets F.S(v). For example, denote SP(v) to be set that contains all nodes in the shortest paths between any U2 vy E v. It is still a valid equivariant set of tuple v. We can see that the design space of k- FFFW++ is much broader than k-FWL
5

---

3.3 (AWL):FWL+: A flexible and powerful extension of k-FWL
In this section, we propose (ke, F)L++ which combines both (k, (kF,)) in Equation (6) and k-FWL+ in Equation (7). Let Ckef+ + (v) be the color of tuple iteration I for (Ri, ()-FWL+ the color update equation of (k: (FFLL+ is:
(k, ()FWL+:: (v) H1/H (v), 1 (Cae)+ (u)lu QU(V) ES (8)
x.... x...X x (v) and (vS(v)) can be any ES(().. (k: ()-FWL+ where (v) (v) x ES2(v)
integrates advantages from both (k, ()-FWI and k-F First, by extending (GG) to (v),,)), we can hugely reduce the time complexity of (k, FWLF as (v) usually contains much less elements than V V') Second, by extending the tuple size in aggregation,
only require small k (even with & = 2) to achieve high expressive power instead of being bounded by k-FWL. Finally, the most important advantage is that the design space of (k, FF-F is much more flexible than k-FWL and we can design the most suitable instance for different tasks. However, as the expressive power of (kt, ()FLL)+ highly relies on the choice of ES' (v), it is hard to analyze the expressive power of (k: ()-FWL+ in systematic way. Instead, in the next section, we provide some practical implementations of (k,L))FWL++ that can cover many existing powerful models.
3.4 Gallery of (k. FFFF instances
In this section, we provide some practical designs of Ev) that are closely correlated to many existing powerful GNN/WL models. Note that any model directly follows the original k-FWL like PPGN [9] can obviously be implemented by (k, t)-FL++ as (kt F)-FFL+ also includes the original k-FWL. We specify that k-tuple
(V1, 2/2 . vk) to avoid any confusion.
Proposition 3.5. Lett = 1, k = 2, and ES(v) (1 (N2)) the corresponding (k, FFL+ instance is equivalent to SLFWL(2) [12] and strictly more powerful than any existing node-based subgraph GNNs.
Proposition 3.6. Let 1. 1, == k, and F.S(v) - Qu(vs), the corresponding (k.I)-FFI++ instance is more powerful than 5-k-LWL. [8].
Proposition 3.7. Let f. = 2, k- = 2, and F.S² = (Q)) n Q1 (12)) x
the
corresponding (k:, f)-FWI++ instance is more powerful than GraphSNN [2/].
Proposition 3.8. Lert = 2, k = 2, and (v) Q1 (1(v)) the corresponding (k,t)-FWL+ instance is more powerful than edge-based subgraph GNNs like P-GNN [19].
Proposition 3.9. Let t k 2. and ES(v) QSPD( o0) (V1) n (u())) the corresponding (k, t)-FWL+ instance is at most as powerful as KP-GNN [22] with the peripheral subgraph encoder as powerful as 1-WL.
Proposition 3.10. Let t = 2, k = 2, and (V) = Q1 x SP((1, 12). the corresponding (k, ()FFL++ is more powerful than GDGNN [23].
We leave all formal proofs and discussion on complexity in Appendix C. Significantly, Proposition 3.8 indicates that (ks, F)-FWL+ can be more powerful than edge-based subgraph GNNs but only require Onn)) space, strictly lower than ((m)) space used in edge- based subgraph GNNs, where m is the number of edges in the graph. However, most existing works employ MPNNs as their basic encoder, which differs from the tuple aggregation in (k, L)-FWL+. Thus it is still non-trivial to find an instance that can exactly fit many existing works. Nevertheless, given the strict hierarchy between node-based subgraph GNNs and SLFWL(2) [12], we conjecture there also exists a strict hierarchy between the (k, F)L+FL++ instances and corresponding existing works based on MPNNs and leave the detailed proof in our future works.
4 Neighborhodf-GNN: a practical and powerful (2,2)-FWL+ implementation
Due to the extremely flexible and broad design space of (k, ()-FWL+, is hard to evaluate all possible instances. Therefore, we focus on particular instance that both theoretically and practically sound. All detailed proof and complexity analysis related to this section can be found in Appendix D.

---

4.1
Neighborhood -FWL
In this section, we propose practical and powerful implementation of (2, 2) named Neighborhoood--FWW (N2-FII Let C S denote the color of tuple iteration I for N2-FWI. the color is updated by:
-WW: (v) HASH(C jw (C (a (u)lu Qu(v)) (v))) E (9)
where (2 (N2( x (i n (v) O (x(2)) and the number of hop. Briefty speaking, N--FWI.considen, neighbors of both node and 12 within the overlapping h-hop subgraph between U1 and 1/2. In the following, we show the expressive power and counting power N2-FWL.
Theorem 4.1. Given h is large enough, N--FWL more powerful than SLFWL(2) [12] and edge- based subgraph GNNs.
Corollary 4.2. NW-FWI is strictly more powerful than all existing node-hased subgraph GNNs and no less powerful than 3-WL.
Theorem 4.3. -WL can count up to (1) 6-cycles; (2) all connected graphlets with size 4; (3) 4- 4-paths at node level.
4.2 Neighborhood -GNN
In this section, we provide neural version N2-FWI. called Neighhorhood -GNN (N²-GNN). Let My be the output of Nº-GNN of tuple at layer I and N2 encode the isomorphism type of tuple v. At the 1-th layer, the representation of each tuple is updated by:
144 = U' (N {m w E (v) mkw =
(10)
After L layers of message passing, the final graph representation is obtained by:
hG R( E (G)
(11)
We leave the detailed implementation in Appendix D. Finally, we show the expressive power of N follows:
Proposition 4.4. Uf M', and R are finctionn,, there exist N--NNN instance that can be as powerful as FF-
Related works
After the expressive power of MPNNs has been demonstrated be limited by the 1-WL, test [5, 6]. significant research efforts have focused breaking the limitations of MPNNs.
jubgraph-based methods. Subgraph-bard leveraging the fact that although some graphs may be difficult to distinguish, they contain distinct substructures that can be easily differentiated by MPNNS. To this end, various subgraph selection policies and aggregation strategies have been proposed to enhance the expressive power of MPNNs. These include K-ego subgraphs of nodes [24-28]. distance labeling [29], graph elements deletion [30, 31]. edge-based subgraph selection [19, 32, 331, etc. ESAN [34] summarizes different subgraph selection policies and proposes a general framework for subgraph-
methods aim to address the limitation MPNNs by
GNNs. I-OSAN [17] further
extends the subgraph-based model to 1-tuples and k. I-WL. [16] considers running k-WL on 1-tuples subgraphs. KP-GNN [22] takes a slightly different view by considering the peripheral subgraph at each hop of nodes. Recently, Frasca et al. [27] proved that all node-based subgraph GNNs bounded by 3- 3-L test. Zhang et al. [12] further show that they are even strictly less powerful than localized 2-FWL, highlighting the inherent limitations of neighbor aggregation-bass methods compared to tuple-based aggregation.
WL-based methods. WL-based methods try to simulate k- WL/FWWW test. In particular, Morris et al. [6] proposed k-GNNs to approximate k-WL test. To reduce the complexity of k-GNNs, Morris et al. [8] considered only local neighbors. Similarly, PPGN [9] adopted k-FWL instead of k-WL and proposed tensor-based model with 3-WL power but requiring only O(n²) space. To further reduce complexity, KC-SeIGNN [10] leveraged node sets rather than tuples and considered only
7

---

connected node sets. However, these approaches can still be impractical despite careful design. Our work hugely extends the design space of FWL-based methods and demonstrates that the resulting model can be expressive even with lower space complexity cost.
Permutation equivariant and invariant networks. This line of research aims to leverage the permutation equivariant and invariant properties of graphs and devise corresponding architectures. For example, Maron al. [35] proposed k-IGNs, which employ permutational equivariant linear layers with point-wise activation functions to the adjacency matrix. k-IGNs have been proven to have the same expressive power as k- k- [9, 36, 37]. Another approach utilizes the Reynold operator to consider all possible permutations on either global [15] or local [20] levels. However, they consider all possible permutations in order to achieve universality, which may lead to overfitting in real- world tasks and are more valuable from theoretical perspective. In contrast, our framework is highly flexible and can be tailored to fit the complexity of real-world tasks.
Feature-based methods. Feature-based methods aim to incorporate graph-related features that cannot be computed by MPNNs. For instance, some methods add random features nodes to break the symmetry [38, 39J. GSN [40] introduces substructure counting features into MPNNs. GD-WL [41] applies general distance features to enhance the expressiveness MPNNs and shows it can solve the graph biconnectivity problem. GDGNN [23] integrates the geodesic information between node pairs and achieves a great balance between performance and efficiency. ESC-GNN [42] employs subgraph features to simulate subgraph GNNs without running them explicitly. Puny et al. [43] computes graph polynomial features and injects them into PPGN achieve greater expressive power than 3-WL. within O(n²) space. Although nature-bbsed methods are highly efficient, they often suffer from overfitting real-world tasks and produce suboptimal results.
6 Experiments
In this section, we conduct various experiments on synthetic and real-world tasks to verify the effectiveness of N2-GNN. The details of all experiments can be found in Appendix E. Additional experimental results and ablation studies are included in Appendix F. The source code is provided in https://githei com/ aiaarrFFenn Feng/N2GN./.. N2GNN.
6.1
Expressive power
Table 1: Expressive power ver- ification (Accuracy).
Datasets. To verify the expressive power of N²-GNN, we select four synthetic datasets, all containing graphs that cannot be distinguished by I-WL/MPNNS. The datasets we selected are (1) EXP [38], which consists of 600 pairs of non-isomorphic graphs that 1-WL fails to distinguish: (2) CSL [15], which contains 150 4-regular graphs
Datasets
EXP
CSL
SR25
N²-GNN
100
100
100
divided into 10 isomorphism classes; and (3) SR25 [44], which
contains 15 non-isomorphic strongly regular graphs, each has 25 nodes. Even 3-WL is unable to
distinguish between these graphs. (4) BREC [45], which contains 400 non-isomorphic graph pairs
that range from -WL-indistinuuishable to 4- WL-indistinguishable
Models. For EXP, CSL, and SR25, we only report results for N2-GNN. For BREC, we compare N with I2-GNN [19] is the current SOTA on BREC among all GNN methods.
Results. We report results in Table and Table 2. For EXP and CSL, we report the average accuracy for 10-time cross-vaile voossaaali:t For SR25, report single-time accuracy. We can see N2-GNN achieves perfect results on all three datasets, empirically verifying its expressive power. Notably, Nº-GNN is able to distinguish strongly regular graphs. This empirically verified Corollary 4.2. Moreover, N2-GNN achieves the best result on the BREC dataset among all GNNs methods, surpassing the previous SOTA, 12-GNN (See the complete comparison and further discussion in Appendix F). Despite this improved performance, N2-GNN only requires at most (n²) space complexity, which less than 3- WL. This further demonstrates the superiority of GN-N
Table 2: Pair distinguishing accuracies on BREC
Basic Graphs (60)
Regular Graphs (140)
Extension Graphs (100)
CFI Graphs (100)
Total (400)
Model
Number
Accuracy
Number
Accuracy
Number
Accuracy
Number
Accuracy
Number
Accuracy
P-GNN
60
100%
100
71.4%
100
100%
21
21%
281
70.2%
NN-
60
100%
100
71.4%
100
100%
27
27%
287
71.8%
8

---

Table 3: Evaluation on Counting Substructures (norm MAE), cells with MAE less than 0.01 are
colored.
Target
ID-GNN [28]
NGNN [24]
GIN-AK+ [25]
PPGN 191
12-GNN [19]
N2-GNN
Tailed Triangle
0.1053
0,1044
0.0043
0.0026
0.0011
0.0025
Chordal Cycle
0.0454
0,0392
0.0112
0.0015
0.0010
0.0019
4-Clique
0,0026
0.0045
0.0049
0.1646
0.0003
0,0005
4-Path
0.0273
0.0244
0.0075
0.0041
0.0041
0.0042
Tri.-Rec.
0.0628
0.0729
0.1311
0.0144
0.0013
0.0055
3-Cycles
0.0006
0,0003
0.0004
0.0003
0.0003
0.0002
4 4-Cylles
0.0022
0,0013
0.0041
0.0009
0.0016
0.0024
5-Cycles
0.0490
0,0402
0.0133
0.0036
0.0028
0.0039
6-Cycles
0.0495
0.0439
0.0238
0.0071
0.0082
0.0075
6.2 Substructure counting
Datasets. To verify the substructure counting power of N²-GNN, we select the synthetic dataset from [25, 19]. The dataset consists of 5000 randomly generated graphs from different distributions, which are split into training, validation, and test sets with a ratio of 0.3/0.2/0.5. The task is to perform node-level counting regression. Specifically, we choose tailed -tiinngle, chordal cycles, 4-cliques, 4-paths, trianglc-rectangle. 3-cycles, 4 4-cycles, 5-cycles, and 6-cycles as target substructures.
Models. We compare N2-GNN with the following basclines: Identity-aweer aware GNN (ID-GNN) [28], Nested GNN (NGNN) [24], GNN-AK+ [25], PPGN [9), P-GNN [19]. Results for all baselines are reported from [19].
Results. We report the results for counting substructures in Table All results are the average normalized test MAE of three runs with different random seeds. We colored all results that are less than 0.01, which is an indication successful counting, the same as [19]. We can see that N²-GNN achieves MAE less than 0.01 among all different substructtrres/cycles, which empirically verified Theorem 4.3. Specifically, N2-GNN achieves the best result on 4-path counting and comparable performance to IN-GNN most substructures. Moreover, N2-GNN can count 4-clique extremely well, which is theoretically and empirically infcasible for 3-WL [42] and PPGN [9].
Table 4: MAE results on QM9 (smaller the better).
Target
DTNN [46]
MPNN [46]
PPGN NGNN [24]
KP-GIN' [22]
P-GNN [19]
Nº-GNN
0.244
0.358
0.231
0.433
0.358
0.428
0.333
0.95
0.89
0.382
0.265
0.233
0.230
0.193
FHOMO
0.00388
0.00541
0.00276
0,00279
0.00240
0.00261
0.00217
ELUMO
0.00512
0.00623
0.00287
0.00276
0.00236
0.00267
0.00210
Ae
0,0112
0.0066
0.00406
0.00390
0.00333
0.00380
0.00304
(
17.0
28.5
16.7
20.1
16.51
18.64
14.47
ZPVE
0.00172
0.002116
0.00064
0.00015
0.00017
0.00014
0.00013
Up
2.43
2.05
0.234
0.205
0.0682
0.211
0.0247
U
2.43
2.00
0.234
0.200
0.0696
0.206
0.0315
H
2.43
2.02
0.229
0.249
0.0641
0.269
0.0182
G
2.43
2.02
0.238
0.253
0.0484
0.261
0.0178
0.27
0.184
0.0811
0.0869
0.0730
0.0760
6.3 Molecular properties prediction
Datasets. To evaluate the performance of N2-GNN on real-world tasks, we select two popular molecular graphs datasets: QM9 [46, 50] and ZINC [5]]. QM9 dataset contains over 130K molecules with 12 different molecular properties as the target regression task. The dataset is split into training, validation, and sets with ratio of (12k graphs) and ZINC-full (250k graphs), and the task is graph regression. The training, validation, and test splits for the ZINC datasets are provided.
The ZINC dataset has two variants: ZINC-subset
Models. For QM9, we report baseline results of DTNN and MPNN from [46]. We further adopt
PPGN [9], NGNNs [24], KP-GIN/ [22], 12-GNN [19]. We report results of PPGN, NGNN, and
KP-GIN/ from [22] and results of 12-GNN from [19]. For ZINC, the baseline including CIN [47].
8-2-GNN [8], KC-SetGNN [10], PPGN [9], Graphormer-GD [41], GPS [48], Specformer [49].
NGNN [24], GNN-AK-etx [25], ESAN [34], SUN [27], KP-GIN/ [22], 1--NNN [19], SSWL+ [12].
We report results of all baselines from [12, 22, 43, 10, 48, 49, 19].

---

Table 5: MAE results on ZINC (smaller the better).
Results. For QM9, we report the single- time final test MAE in Table We can see that N2-GNN outperforms all other methods in almost all targets with a large margin. Par- ticularly, we achieve 63.8%, 54.7%, 71.6%, and 63.2% improvement comparing to the second-best results target Uo. U. H, and G respectively. For SubS-Subset and ZINC- Full, we report the average test MAE and standard deviation of 10 runs with differ- ent random seeds in Table 5. We can see N2-GNN still surpasses all previous meth- ods with only the smallest model parameter size among all baselines. It achieves 10.6% improvement over the second-best methods on ZINC-Subset and the same performance over the previous SOTA on ZINC-full. All these results demonstrate the superiority of
7INC-Subset Test MAE
ZINC-Full Test MAE
Model
Param
CIN [47]
-100k
0.079 0.006 0.022 0.002
6-2-GNN LSJ
0.042 + 0.003
KC-SeIGNN [10]
0.075
0.003
PPGN [9]
0.079 + 0.005
0.022 + 0.003
GD-WL [41]
503k
0.081 + 0.009
0.025 + 0.004
GPS [48]
424k
0.070 +0.004
Specformer [49]
-500k
0.066 + 0.003
NGNN [24]
-500k
0.111 + 0.003
0.029 0.001
GNN-AK [25]
-500k
0.093 = 0.002
ESAN [34]
446k
0.097 1 0.006
0.025
+: 0.003
SUN [27]
526k
0.083 + 0.003
0.024
0.003
KP-GIN [22]
489k
0.093 + 0.0U7
1 p-GGNN [1]]
0.083 + 0.001
0.023
0.001
SSWL+ [12]
387k
0.070 1 0.005
0.022 1 0.002
N--GNN
311k/414K
0.059 + 0.002 0.022 0.002
N N²-GNN on real-world tasks.
7 Limitations, future works, and conclusions
Limitations: For (k, F)-FWL, although we can control the space complexity by fixing the k, the time complexity of (k, F)-FWL will grow exponentially with the increase of (as discussed in Appendix B). Therefore, the resulting model can still be impractical when is large. We believe this result is evidence of the "no free lunch" in developing more expressive GNN model. For (k; 4)- FWI.+, although we demonstrate its capability by implementing many instances corresponding to different existing GNN models, is still unclear what is the whole space of (k: F)-FFL+ especially the space of (v). Moreover, the quantitative expressiveness analysis of (k, F)-FL++ is still unexplored. Finally, for N²-GNN, the practical complexity can still be unbearable, especially for dense graphs if the aggregation is implemented in parallel way, neighbors for each tuple than normal MPNN. It also introduces the optimization issue on N²-GNN, which makes it hard to achieve its theoretical expressiveness. In Appendix B, C, and D, we provide more detailed discussion on the limitation of (k: F)-FWL, (k, F)-FWL+ and 22- respectively.
need to aggregate many more
Future works: There are several directions that are worth further exploration. First, can we characterize the whole space of F.5(v) and thus can theoretically and quantitatively analyze the expressive power of (k, FFWL.. Further, how to design advanced model architecture to achieve the theoretical power of (k, FW-F..+ Finally, can we provide a systematic implementation code package and practical usage of different downstream tasks such that researchers can easily develop an instance of (k, F)FF that can best fit their downstream tasks? We leave these to our future work.
Conclusions: In this work, we propose (k, FFL++ flexible and powerful extension of FWFL. First, (k. FWL+ expands the tuple aggregation style F-FWL. We theoretically prove that given any fixed pace complexity of O(n*), (k: F--F can still construct expressiveness hierarchy up to solving the graph isomorphism problem. Second, (k: FW-F extends the global neighborhood definition in k-FWL to any equivariant set, which enables finer-grained design space. We show that the (k: F)F+ framework can implement many existing powerful GNN models with matching expressiveness. We further implement an instance named N2-GNN which is both practically powerful and theoretically expressive. Theoretically. it partially outperforms 3- but only requires O(z²) space. Empirically, it achieves new SOTA on BREC, ZINC-Subset, and ZINC-Full datasets. We envision (ks F)-F can serve as promising general framework for designing highly effective GNNs tailored to real-world problems.
8 Acknowledgments
Jiarui Feng, Lecheng Kong, Hao Liu, and Yixin Chen are supported by NSF grant CBE-2225809. Muhan Zhang is partially supported by the National Natural Science Foundation of China (62276003) and Alibaba Innovative Research Program.
10

---

References
[1] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017. URL https: //openreview. Stttt/oouummdd-Suua/llaa
/
[2] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1025-1035, 2017.
[3] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL https::///// http:::///eeeeeeeeeeeeeee http://ppeeeeeeeeeeeeeeeoooraiaa net/foorum/iderr
[4] 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, pages 1263-1272. PMLR, 2017.
[5] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
[6] 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 of the AAAI conference on artificial intelligence, pages 4602-4609, 2019.
[7] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NT7, Series, 2(9): 12-112, 1968.
[8] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in neural information processing systems, 33:21824-21 2400, 2020.
[9] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[10] Lingxiao Zhao, Neil Shah, and Leman Akoglu. A practical, pperressivell-cxpesssiii GNN. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: http:::s///ppeeeveeeeee net wetefoorummiii WBv926qpA8x.
[11] Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe WL meet VC. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 Proceedings of Machine Learning Research, pages 25275-25303 PMLR, 23-29 Jul 2023. URL https:
mlr. press aetess/v202/
html.
[12] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph GNNs via subgraph weisfeiler-lehman tests. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Pre- ceedings of Machine Learning Research, pages 41019-41077. PMLR, 23-29 Jul 2023. URL https:/ https://proceedingss mlr grrss//202/zhanggge html.
[13] 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 410, 1992.
[14] Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, 2017. doi: 10. 10.1017/9781 139028868.
[15] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pages 4663-4673, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http: http:::://ooceeeeeeeeeeee mlr, press/ v97 /0/p/m/ppy19.aaba html.

---

[16]
Cai Zhou, Xiyuan Wang, and Muhan Zhang. From relational pooling to subgraph GNNs: A universal framework for more expressive graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Pro- ceedings of Machine Learning Research, pages 42742-4211 42768.. PMLR, 23-29 Jul 2023. URL https: http:://prooeedingg. mlr ppess/v202) /200/22022222 zhou23n html.
[17] Chendi Qian, Gaurav Rattan, Floris Geerts. Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL fetpp:://ppnreviist net/ tttp:ffrdddddd
[18] V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler-Lemal invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 1 113:42-59, -9, November 2020. ISSN 0022-0000. doi: fes.0066).esss.2222.... attps://wwy sci wcceennedirett.ccm wttp://ttccoocc/c/ccceececcceeee http:///ac..arraaa//////////0000
URL
[19] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with i$<2S-GNNs, In The Eleventh International Conference on Learn- ing Representations, 2023. URL http::// http::/:///ppeeeeieieeee
net/ htthm/ormm??/ SaarummmdddDDSnxxppss.....
[20] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-103333 2020.
[21] Asiri Wijesinghe and Qing Wang. A new perspective "how graph neural networks go beyond weisfeiler-lehman?.. In International Conference on Learning Representations, 2022. URL
https://oppnrrevier
[22] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://openreviex: http:://oppaeeeeiieeeee////rrett
[23] Lecheng Kong, Yixin Chen, and Muhan Zhang. Geodesic graph neural network for effi- cient graph representation learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances Neural Information Processing Systems, 2022. URL https://openrevier
[24] Muhan Zhang and Pan Li. Nested graph neural networks. Advances Neural Information Processing Systems, 14:15734-157477 2021.
[25] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022. URL https: http////ppeeeeeeee//eee/ee/eeee/ net/forrmmiddleeeee.
WWKoEH.
[26] Dylan Sandfelder, Priyesh Vijayan, and William L. Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8523-8527, 2021. doi: 10. 10.1109/ ICASSP39728.200 2002222..21.999 10021.9914011 9414015.
[27] Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and extending subgraph GNNs by rethinking their symmetries. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL /
[28] Jiaxuan You, Jonathan M Gomes-Selman Rex Ying, and Jure Leskovec. Identity-awarr graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, pages 10737-10745, 2021.
[29] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances Neural Information Processing Systems, 33, 2020.
12

---

[30] Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. DropGNN: Random dropouts increase the expressiveness of graph neural networks. In A. Beygelzimer. Y. Dauphin. P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL htttt::///ppeeeeeeeeeeeee
[31] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https: pertts://oppe /ttpr///e/e///eee/e///ee / net/ forum71d-2K6224meb11..
[32] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https: http///ppeeeeveeeeeeeeee wwt.:eeettottiteem oormmiid=-ccr9mm3G66e
[33] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pages 5165-5175, 2018.
[34] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL https://openreeiies http:///pppppeeeeeeeeeeerrrrrree
[35] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019. URL https:
/ //openreview... meet/forumiidd-SyX2222
[36] Waiss Azizian and mare lelarge. Expressive power invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. URL https: /oopenrvvew. tentt/forumidddlxgeeee
[37] Floris Geerts. The expressive power of kth-order invariant graph networks ArXiv, abs/2007. 12035, 2020.
[38] Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference Artifical Intelligence (IJCAI), 2021.
[39] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference Data Mining, SDM, 2021.
[40] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting, 2021. URL https:
/ //openreview //opearerieerr.eefooortredeeee nee//forumrie--TTToosnhhh
[41] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference Learning Representations, 2023. URL httpps:///peeeeiiiisssst wttp:ieew..eeeeooorr//eretttoeee
[42] Zuoyu Yan, Junru Zhou, Liangeai Gao, Zhi Tang, and Muhan Zhang. Efficiently counting substructures by subgraph gnns without running gnn on subgraphs, 2023.
[43] Omri Puny, Derek Lim, Bobak T. Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks, 2023.
[44] Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. Proceedings of the 38th International Conference Machine Learning (ICML), 2021.
[45] Yanbo Wang and Muhan Zhang. Towards better evaluation of gnn expressiveness with brec dataset, 2023.
13

---

[46] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 92):513--330, 2018.
[47] 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 A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https::/
[48] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022.
[49] Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations. 2023. URL //tperev///peeevie net/ forummidd /topmmmmaddooppptttyy..a....
[50] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1::1-7, 2014.
[51] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.000 00982, 2020.
[52] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PoTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
14

---

Appendix
Table of Contents
A Additional preliminaries
16
A.1 Additional definitions
16
A.2 More on Weisteiler-Lehman test and Folklore Weisfeiler-Lehman test
16
B Additional discussion on (k, ()-FWL
B.I
Detailed proofs for (k; F)-FWI
17
B.2 Complexity analysis
22
B.3 Limitations
22
C Additional discussion on (k, F)-FWL+
22
C.I Detailed proofs for (k, L)-FWL+
................................
22
Discussion on the complexity
................................
28
Limitations
D Additional discussion --FF and -NNN
29
D.1 Detailed proofs for N2-FWL
29
D.2 Complexity analysis
30
D.3 Model implementation details
30
D.4
Limitations
31
E
Experimental details
32
F.1
Dataset statistics
32
E.2
Experimental details
................................
32
F
Additional experimental results
34
F.1
Ablation studies for (A:, ()-FWL+
34
F2
Practical complexity of 22 -NNN
................................
34
F3
Additional discussion on BREC experiment
35
F4
Ablation studies for N2-GNN
35
15

---

A Additional preliminaries
In this section, we provide additional preliminaries.
A.1 Additional definitions
Definition A.1. When we say we select a I-tuple w' = (wi, w/y wx) from a p-tuple v = (vi,"2," yUp) (p I), it means that select / unique indices (11, 22, . from [p] such that i < < ... < ip. Next, to construct w', we let w/ = Vig...... Wi = vi,- When we say we select all possible t-tuple w' from a p-tuple v, we enumerate all possible t indices and construct t-tuples
different selection results and we denote P.(v) as the set of all correspondingly. There are P
possible selections. Finally, when we say select all possible 1-tuple w' from y-tuple v with order, we further assume that the selection process is taken with a predefined order such that the sequence of selected indices will be the same if we repeat the selection. For example, we can always assume we start from indices (1, 2, ...,..... t). Next, fix other indices and enumerate all possible in in ascending order. Then, increase it-1 by 1 and repeat the procedure. If we select all possible 2-tuple from (V1, 12,, Uy), the result is ((11, v2), (11, v3); (02, vs)). We denote Pv(v) as the tuple of the selection result.
Definition A.2. Neighborhood tuple (v) is a generalization of neighbor set Q in k-FWL. Briefly speaking, the neighborhood tuple enumerates all possible combinations of elements in v and w follows a pre-defined order. Suppose the length of the tuple is k and / for v and w, respectively. To construct the neighborhood tuple (v), we enumerate m from 0 to min(k; l). For each m, we construct a sub-tuple, and the final neighborhood tuple Q (v) is the concatenation of all sub-tuples. Given particular m, the sub-tuple is constructed by selecting all possible m-tuple (w',.... =[w
w'= = select all possible m indices i' .i'....: (m,) from = 21,2,.... k) with order to construct another tuple Pm (i). Finally, for each (w', f') E (w) x Pm (i), we add tuple to the resulted sub-tuple by replacing 2y with W/ for 1, 2, .............................. ... The neighborhood tuple is constructed by concatenating
w from t-tuple w with order to construct a tuple Pm (w). ). At the same time, we
all sub-tuples. The length of the neighborhood tuple is Emin(R
(m))(M)
k
m
Definition A.3. Let F1 and F2 be two color refinement algorithms, and denote (,),, 2 E {1,2] as the color histogram computed by F; for graph G after convergence. We say:
Fj is more powerful than F2, denoted as Fg A FJ, if for any pair of graph G and H, C, (G) =
C (l) also implies C2(G) = (H).
Fj is powerful F2, denoted as Fi = F2, if we have F1 < F2 and F2 Fi.
Fj is strictly more powerful than F2, denoted as Fg Fi, if we have F3 F1 and there exist graphs G and H such that (G) * (H) and (G) = C2(H).
Fi and F22 are incomparable, denoted as Fi de F2, if neither Fi = F2 nor F2 - Fi holds.
Remark A.4. To prove that Fi is more powerful than F2. one way is to show that the color of node/tuple cannot be further refined by F2 if the color output from F; is already stable (convergence). This was also indicated in Remark B.2 in [12]. Note that the initial color of F1 should be at least as powerful as the initial color of Fz. Namely, if we use the initial color to compute the color histogram, we have F22 F..
A.2 More on Weisfeiler-Lehmall test and Folklore Weisteiler-Lehmall test
First, we restate the color update equation of both k-WL and k-FWL.
WL: Cv = HASH (Chrl(v), ((C Q5(v) (k]))
FWL: (v)mi(v)= HASH (cl (Cl (v), (f (Cl ( wl V(G)
The first step of both l- WL and k-FWL is to encoder the isomorphic type of tuple v (E1, U2, ..., Uk) as initial color such that for any two tuples u, v E (G), (v) Ch (u) and Cham (v)
16

---

Ceut (u) if and only if the ordered subgraphs induced by two tuples have the same isomorphism type. Namely, V E [k] (1) (t((;) = (u;4)) and (2) U;) E(G) = (u;, u,) E E Another thing is that the HSAH here is an injective function. As long as the input is different, the output of HASH is different. This will serve as a basic concept in the later proof. The algorithm
converge means that Vv E (G), we have Ckel = (v) or Cl+1 (v) = C Ckf Denote the convergent iteration as oo. After the algorithm convergence, the color histogram can be computed by another injective function: CG) HASH( E (²))))
(12)
Here we use k-FWL as an example, but the procedure for other color refinement algorithms is the same.
B Additional discussion on (k. FFFL
B.1 Detailed proof's for (k, t)-FWL
In this section, we provide all detailed proofs related to (k.,))FWLL Let = (v,w) be a new tuple that is the concatenation of a k-tuple v and a t-tuple w. Let C ((++ejui (p) be the isomorphic type of tuple p. We start to prove the expressive power of (k;,))FFW with the first lemma:
Lemma B.1. Suppose k. 2 and I 2 1. Given two graphs G. H, two tuples vi V (G). E (H), and another two tuples W1 E VV(G), E V*(H). Let P1 = (V1, P2 = (V2, W2). We have C Ciktojur(P)) = Co C((ts)uc(P2) = (CResu((zz) un E Qu, (vi)) =
(ueefu((2))ee E (vo)).
(P2), we have (Crffmiuu))lu E Om, (vi)) = (CRefur(uz)luu E Q (v2)). Recall the definition of the ini- tial color, if eD C(k+t)ur((P)) = cD (k+e))ul (P2). we must have the ordered subgraph induced by P is isomorphic to the ordered subgraph induced by P2. Namely, Vi,j E [k + 4), (pii, E F(G)) - (p2,,P2;) E F.(H) and (a(p))) = (G(2)). Next, given Definition A.2, we know that for any neighborhood tuple, there exists single indices mapping function O that given p = (v, w). for any u E Q (v), we have Olu, Q (v)) = (o),...,.0) ox) such that (u....., 4+) (Po.s..... Por)) Further, the construction of the neighborhood tuple follows the same ordering rule no matter the input. This means that, for both un E Q (V1) and u2 E Q (v2), as long uj and u2 are in the same position of neighborhood tuple Q (V1) and Q (v2), must have O(u Q (v1))= O(uz, Q (v2)) (oi,.... ox). Finally, as for any o, and oj. have (Pro: P1oy)) E ((G) = (P2o; (P2o; E E(H), (p(10;) = (o(2o,)). ). and (o(Pro;) = la (P20g)) conclude that Chefui (u,) = Co Chesuc As it is the same for any u1 _W,((1) (V1) and u2 Qf, (vi) = (Ckefm((u>)lur E Q (va)). The
Proof. First, we prove the forward direction. That is, if CO ((44)))((P))) ) = CD (P2),, (k+te)w
Q (V2), it must holds that (Crffmn(u))) proof of the backward direction similar to the forward direction. As for any i. [l=+t], we can find Pii.P Pıy exist in some i₁ E QF, (v1) and P2i. in the corresponding U2 E Q (V2). Since we have CD Catfui (u,) = Carfuat (12), (12)) we can easily conclude that (Pis,P)) E F(G)) < (p2i,12j) (.()). (p())) = to (P2.) and la (Pis)) = lo This concludes the proof.
Lemma B. indicates that (k, ()-FWI. can recover the isomorphism type of high-order tuple, which is impossible in the original k-FWI. Therefore, as long as f. is large enough, we recover the isomorphism type of the whole graph. Further, Lemma B. also implies that we can resort to high- order tuples to prove the expressive power of (k, FWLL Define the Hz(v) = [(v, w)]w E V*))), we slightly rewrite Equation (6):
Chefue (p) = HASH ((Chelur Qu(v)))
(13)
Chefui (v) HASH (Clef (v), &leess E H. H.(v)
(14)
17

---

It is easy to verify the rewritten will not affect the expressive power of (k, t)-LF. Now, we are ready to prove the Proposition 3.1 in the main paper. We restate it here:
Proposition B.2. For k 2 and 2 ift 2 n k. (k. t)-FWL can solve the graph isomorphism problems with the size of the graph less than or equal to n.
Proof. Here we show that with only 1 iteration, (k, FWF can solve the graph isomorphism problem with the size of graph n S ++ k. Given Lemma B.I, for any v E V* we have Ckefud (P1) = Ckefue (22) $ C ((ta)ur(P1) = Co (k+ (P2) for any P1, P2 E Hilv). H.(v) which essen-
Therefore ( E Hv(v) is equivalent to (((++))ur tially the multiset of isomorphism type of p E Hv(v). According to Equation (14), (v) can injectively encode this information. Next, the color histogram of a graph is computed by CRafui (G) HASH( (Chefur E ())))). It is easy to verify that Crefwi(G) can encode the isomorphism type of all (k + t)-tle E VG+ Then, if the graph has size n & k + 4, Crefwi(G) can give different color histograms for any non-isomorphic graph pairs. This concludes the proof.
Before we prove the relationship between (k: FWL and (k + tt)WL, we first show some properties of (k + ()-WL. Let C ((k-r)u (p) be the stable color of tuple p E (G+ output from (A: + WL-
We first show that:
Lemma B.3. Suppose 2 t 1. Given a graph for any V1, V2 E V*),,, WI, We (G)).,
Pi = (V1, w1). P2 = (V2. W2), Coo (k-r))o (P1) = C
(k+r)mm (P2) implies that &CG (k+rjom (q:) q
H.(vi)B. (CCk+rruul (g2) E (v Br-
= (P21....,PP(a... P2(k++)) As we have C.0 ((Rto)u((Pi) = C (R+))w((D2) given it the stable color, we PPik, W. (1842))...... P((ke))))))))))
Proof. Let P1 =
must have KGB=-oju((P211.- P2k, W. P2(k++)) (.0c))))---PP(-0))) P2(1+))))
E V(G) V(G))- Otherwise, by doing one (k+t) (Pt) ) o Cott1 (k+t) (P2), which is a contradiction. Further, we can more iteration, we will have cott1
do another unrolling have & (CCC+tew (PP....PPP.......... Pik, W1, W2..... Piak+))) E V(G) wi V(G) = If HHCR (0 Pak, W1, W2 P2(k+)))) 102 E V(G) E V(G)). This implies that (C(t+o)u((PI)) (C@=)))(((211... P28, , (w), w2) E (²) Therefore, by iteratively P.e,,,
Plk: W1, W2, ................................ PI (I(k+)))) (ww,, W2) V²(G)B2
doing the unrolling. we must have [C (PPII..... PIk, Wi...., w)))((w..... wy)
V'()), = CC (P21, P2k. W1...., we (w), 10 (G(+)))a(l1)))) E H.(v1) = (C (92) 42 (. This concludes the proof. O
E V'(G),,, which is exactly
qa
Lemma B.3 indicates that if the (k, tL converges, the hierarchical set will not increase the expressive power of (k + WL. Based on this observation, we can slightly rewrite the equation for computing the graph color histogram of (k WLL
C20 CiR+t)et (v) = HASH (G E H.(v)Bt), C.00 (k+t)pot (G) HASH( (CCHH E v*)))),
(15)
(16)
where Cae (k+()we (v) is the stable color of k-tuple v. Here we change the computation of graph color histogram by first hierarchically pooling all tuples in (v) to get color for v and then pooling all tuples v E V* (G). It is straightforward that the rewritten will not change the expressive power of
(k + tL given Lemma B.3. Equation (15) and Equation (16) will be used in the latter proofs. Not surprisingly, we have similar result for (k, FWL:
Lemma B.4. Suppose &o 2 2, 2 1. Given a graph G, for any VI, V2 E (*), W1, We e
V'()). Pi- = (v,,wi), P2 = (V2, W2), CRi (Pi) = Coo Chf (P2) implies that ( e Hz(v1) HCij (q2)) (2 }.
18

---

Proof. Given the definition of the neighborhood tuple, we must have VI E Q (v1) and v2 E Qwn (v2). This means we also have fit (v1) f (V2). Otherwise, by doing more itera- tion of (k,t)-FWLL, we will get different colors for P1 and P2, which is a contradiction. CR (er Coo fi (V2) directly implies that &C (q:)gq E Hx(vi)B (C E He(v2) given Equation (14) and thus conclude the proof.
Next, we show another property of (A: + ()-WI. Denote T+++ as a permutation group operates on the indices of a k f-tuple. For Tk+t, denote it operates on a k 1-tuple p (p1,- ........ -.Pk++) as 0 = (Po(1)...... (ktkk()))))) ). For example, for a a E 13 with o() = 2, (2) = 1,) = 3, we have σ (P1.P2, = (p2.P1.PL
P1, Ps).
Lemma B.5. Given two graphs G and H, for any Pi = (pit,...,PP((ttto) E (k+ P2 (P21..... P2(k+t)) (H) and a permutation a E Tatt operates on the indices of uples, C (k++)uml (Pi) C (kk+t) (P2) implies that C (i (o Pi) = (k+tt)alo P2).
Proof. We prove it by induction on I. At iteration 0, CO (k++ (P1) Co (k+t)am (P2) means the ordered subgraph induced by Pı is isomorphic to the ordered subgraph induced by P2. As the permutation is operating on the indices, will not change the nodes in the tuple but only change the order of the tuple. As we use the same permutation a for both Lı and p2. it is easy to verify Cl ((+tewu (ar PP)
CD (k++))on (a P22). Suppose it follows for 1, 1,....I - 1. At iteration 1, if Ct (k4e)mn = C (k44))u(
we have:
( (PI,;;))) e V(G) = (P E V(H)B,
Then, since the statement follows at iteration - 1, we must have
[C CCittenul(( p11)//;) e V(G)) (C(tt))aa(lo Pa)m//)l E V(H),, Vi lk
The above equation directly implies that C/ Ck+ojwll -P1) = Glettnalo P2). This concludes the proof.
L
With all conclusions at hand, we can start to prove the main proposition in this section.
Proposition B.6. Suppose & 2 2 1. Given any two graphs G and H. If Co0
(k+ (G)
(G)
C (k+t)uu (H), then for any V1 V* V2 E VHH), W1 E V'GG), W2 E V'HH), P1 (V),
W1).
P2 (V2, W2) with C.e (k+t)wo (P1) = Coc (k+r)w (P2). we also have Chifur (Pi) = C:00
fll (P2)-
Proof. As indicated in Remark A.4, this can be proved by doing one iteration of (k: t) FWL using the stable color computed by the k + t. LL as the initial color. If the color is not refined anymore, we can conclude it. However, since there is no stable color of low dimensional tuples in original (Ie + f)-WL. we resort to Equation (15) for help:
C.0 C(k+t)ue(V)) (v:) HASH( (C(K+))aa (9)g H.(v:))(), i= 1,2.
(17)
Using Lemma B.3, we must have:
Ci++ejui = C20 C(k
(18)
Further, given the definition of the neighborhood tuple, any u₁ Q (v1) is sub-tuple of P which means that we can find a permutation a E 4[K+s]. such that the first & position of a Pi is exactly un- As the order of the neighborhood tuple is predefined and the same for both Q (vi) and Qhe (V2), the first l position of P2 will be U22 as long as Un and u2 is at the same position in the neighborhood tuple. Therefore, for any u E Q (v1) and u2 Q (Va) at the same position in the neighborhood tuple, we can find a permutation a E I[-+4J to achieve it. Then, given Lemma B.5, we have Coe (k++ (a. Pı)= = Coe C(Etojur(a P2), which indicates Cao (k+s) (u1) = Coc
C(r+e)uo (u2) by
using Lemma B.3. This means:
(G E Q (vi)) = -C ((u)t))urrue)llu E (o()))
(19)
19

---

Now, suppose we use the stable color generated from (A + f)-wl as the initial color to perform one
more iteration of (k, F)-FWL. First, Equation (19)indicates that we have Cktful (Pi) = Coc+t ft (P2)
by doing one iteration of Equation (13). Next, Equation (18) further indicates we have f (Vi)
CRe Cktru (V2) by doing one iteration of Equation (14). This means the color of p1 and p2 cannot be further refined by (k, FWLL This concludes the proof.
Now, we can prove Theorem 3.2 in the main paper. We restate it here:
Theorem B.7. For k 2 2, t 2 1, (k. t)-FWL is at most as powerful as (I: + t)- In particular, (ke 1)-FWL is as powerfid as (k + 1)-WL.
Proof. Based on Proposition B.6, given two graphs G, H with C (k+t)wl (G) = C (k= (f). For any V1 E (G), V2 E (H), WI E VV)G), Wa E (H); P1 = (V1, W1), P2 = (V2, W2), we have Gifful (P1) = CRo Coe (P2) if Ch (k+ (pi))))(P)))))))) C (k+t) (P2). This further indicate that CRt Cetseel (V1) C
C.e. (k+t))ot (H), , for any VI E (G), we can find corresponding v2 E V*H such that C (k+ (v1) = C (V+)))
kef (v2) if CDo (k+t))m (V1)
C
(k+e)and (V2). As we have Cip ((++t)ue
E V* (H))) Cr (H). Based Definition A.3, complete the proof of the first part. As (k, 1)-FWL is exactly k-FWL, we have (As, 1)-FWL is as powerful as (I: + 1)-WL.
This means Cho CRifui = HASH( (ACH(((CEeaa fur fur (vi)lv E () = HASH( (
Finally, we prove the strict hierarchy of (k, FFWL First, we provide the following lemma. Lemma B.8. For h 2 2, t > 1, (k, - (k, + 1)-FWL; (k: t)- < (k + 1,W)-FWI.
Proof. First, we prove (k: t) F-FFF 3 (k, 1)--LL Actually, we can prove a strong result: given two graphs G and H, V1 V (G) and v2 E (H), Chec (V1) Ck (V2) also implies Cl (aafu((v)) = (V2) for any 1 1 O. We prove it by induction. For base case, it is easy to verify that if CO (((++1)fml (V1) Co fwt (v2), we have (V1) CRe fe as both (k, FFWL and
(k:, t + 1)-FWL use the isomorphism type of k-tuples. Suppose it follows for I 1...., 1. At iteration 1, if C (((tt))e C ((((t)) (V2). according Equation (14), we have:
cl-1 litt+)fful (v1) = ct-1 C (V2),
(20)
(p (v1) = (C H1-1(v2
(21)
This means, for any P1 (V1, wi) E (v we can find a P2 (v2, w2) E 14441(22) such that Ch (((+1))(((P)) (Pı) = ci 1(t+)) (P2). According to Equation (13), we further obtain:
E efh,
(Clot (C (u2) u2 E (v2)
(22)
Therefore, we have el-1 (( (ui) = cl-1 -l- Chett)ssu( (uz) for u and at the same position. As the statement follows for 1 = 1 1-1, we have Ckifa(())) (u,) = cl-1 (u2) for u and U2 at the same position. Now, suppose we select t-tuple w from W1 and let the selection indices be (11, (2..2,...d)) it). That is, w/ (Wii...... WIa... Based on the definition A.2, for any u' E Q (V1). it must exists in QF, (v1). Further, let w'2 (W2i..... W2,,), ), for any u' Q (V1), we can find a corresponding uly E 0. (V2) at the same position and they must be the same position in Q (v1) and Q=, (v2), respectively. This means, let pi = w1) and p = (V2, w²)). we have Ckefus(pi = Che fun (pz). Let selection indices be (1, (1,2....,4) (). which is the first elements in the tuple, for any P1 = (V1, w1) E He(()), we can find at least one P1- (V1, wi) E H1+1(v)) that the first elements of W1 is w(. For the corresponding P2- (V2, W2) E H442(V2) with
Ct Che (pi) ct h (P2), we have Chef (Pi) Cleyua (P2). where P'2 = (V2, w/)) and
w/ is the first clements of w2. Based on Equation (21), we have:
(Che E Hc(v:) (Cunsurpp)) E Hc(v2)
(23)
20

---

(v2), Finally, given Equation (20), we also have C!-1 (v)) = Cl-1 kt (V2), which implies Ck (V2). This concludes the proof.
f fwl (v1)
For the second part, the procedure is similar, as for any v E (*)),, we can find at least one v' (G) that contains all nodes and persevere the order of v. Further, given E (*) for any E Qw (v), we can find at least one u' Qw that contains all nodes and persevere the order of u. Then, an induction on I can be performed and we omit the details.
Next, we show a useful property of (k: ()FW), Lemma B.9. For k 2 1 1, given graph G, for any V1, V2 E (G), (ifffi(v)) kefiwll (V2) only Vi, [K]. SPD(U16; U1y) SPD(U2i, U25).
Proof. Based on Lemma B.8, we only need to show it is true for (k. 1)-FWL, which the original
(v2) ) if and only if the induced subgraph of v and V2 are isomorphic. Therefore, Vi,j E [k]. if SPD(U1): Uty)
k-FWL. At the iteration O, CRI (v1) for for
0 or SPD(e14, Uzy) = 1, we must have SPD( 022)) = 0 or (2g,, B2y) = 1, respectively. After the first iteration, Vi.j E [A], there exist at least wi VVG) such that (v1s, w1), (w1, F(G) but no such w2 E V(G) exist with (125, W2), (W2, v25) E (GG), (k, 1)-FWI. will output different color for V1 and V2, given the color update equation of (k, 1)-FWL. This means f = ( implies that for vi,j E [k)., if SPD U1s Ø1y) = 2. we must have SPD(U2) U25) = 2. Similarly, after the second iteration, (k, 1)FFIL will output different color for Vı and V2 if there exist at least wi E VV)) with SPD(U1s, w1) = 2 and SPD(w), 015)
but no such W2 E V(G) exists for V2. Therefore, conclude that iteration of (k, 1)-FLL can generate different color for V1 and Va if there exist some i E [k] with SPD( U1j) = but SPD( U22)) * (d S + 1). Therefore, by performing enough iterations, (k, 1)-FWL can compute the shortest path distance between any pair of nodes in a k-tuple and it is easy to verify Coo Chefut (v1) = ( only if Vi, E [K].
SPD(U1,, 012) SPD(u2, o22). This concludes the proof.
Next, we introduce Cai-Furer- Immermman (CFI) graphs [13]. CFI graphs are family of graphs that k - 1-WL can differentiate while k- WL cannot. Here we first state the construction of CFI graphs [8]. Construction. Let K&+1 denote complete graph on k + nodes (without self-loop). Nodes in Ke+1 are labeled from to k. Let E(v) denote the set of edges incident to e in Kg+1- We have [E(r]] i for all E ((K+-1). Then, define the graph Gj as follows:
1. For the node set V (Gx), ) we add
(a) (u, S) for each v in V (KK+11) and for each even subset S S E(v);
(b) two nodes el and e for each edge e E E(K+41).
2. For the edge set E(Gx), we add
(a) an edge (e",et) for each e E(K++1);
(b) an edge between (v, 5) and el if u E and E S;
(c) an edge between (v, S) and e if u E and & S.
Further, we construct companion graph H₃ in similar way Gg, except that: in Step ( for the vertex 0 E V(K,-)). 1), we choose all odd subsets of E()). is easy to verify that both G2 and H3
have (I + 1) 2b (
nodes.
We say a set S of nodes forms distance-two--lique if the distance between any two vertices in S is exactly two.
Lemma B.10. The following holds for the graphs Ga and Hy defined above.
There exists distance-two-clique of size (k 1) in Gg.
There does not exist a distance-two-cline of size (k + 1) inside Hy-
21

---

Proof.
Please see the Lemma 8 in [8] for detailed proof.
Next, we show that (k, t)-FWL cannot distinguish Gl+t and Hote but 1,t-FWWL and (k, t 1)- FWL can.
Lemma B.11. For 2, (k,L)-FWL cannot distinguish Gk+c and Hk++-
Proof. Given Theorem 3.2, (k, t)-FWL is at most as powerful as (k++)-WWL. As we know (k++)-WWL cannot distinguish Gk+t and H&+1 we conclude that (k,, t)-FWL cannot distinguish between them neither.
Lemma B.12. For 2 2, 2 1, (k: +-+1,,1 1,t)-FWL and (ki, + 1)-FWL can distinguish Gk+t and H
Proof. The proof idea is to show both (I: + FWLL and (k, 1)-FWL are powerful enough to detect two-liquss of size (A: 1), which is sufficient to show that (I: + 1, F)WL and (k,, t 1)-FWL can distinguish between GK+e and Ha+z- Given Lemma B.9, know that both (k+ 1, ()FFL and (k, L 1)-FWL can compute the distance between any two nodes in a k + 1-tuple and k-tuple, respectively. We first discuss (k + 1, ()-FWL In Gg. there exist
1-tuple (v, w) with v E V (Gxs) and E (*x)) that exactly form a distance-two--liquee Based on Equation 13, there exists one E V*+++1(Gx) such that C/ (k++ fot (P) encodes the distance between any pair of nodes in p is 2. However, there is such p in Hg. This is sufficient to 1)-FWL is similar, as (k, + 1)-FWL can also encode pairwise distance information for any k + t + 1-tuple, thus detecting tistence-two-eliquee with the size of l + +t 1. This concludes the proof.
show that (A + 1, FW-F can distinguish G3 and H3. The proof for (k, t +
Now, we are ready to prove Proposition 3.3 in the main paper. We restate it here: Proposition B.13. For & 2 2, 2 1, (k, + 1)-FWL is strictly more powerful than (k, ().W: (Ie + 1.tL)-FWL is strictly more powerful than (K,L
Proof. It is clear the proposition holds given Lemma B.8, Lemma B.12, and Definition A.3.
B.2 Complexity analysis
For (ks F),L,, the space complexity O(n*) as we only need to store representations of all k-tuples. For time complexity, if k and are relatively small, update the color of each k-tuple, (k, F)-FWL needs to aggregate all (G) possible neighborhood tuples, resulting in (n**+) time complexity. If both & and are large enough (related n), the time complexity further increases to O( gl )²), where m min(k, t) and q max(k, t).
B.3 Limitations
As discussed in the above section, although (ks FWL can have fixed space complexity of (n")) the time complexity will grow exponentially if we increase the t. Further, the increase of the will also make the length of the neighborhood tuple increase. This makes the practical usage of (k:, FWL limited (This will be hugely alleviated by (k:, FWL+). This is evidence of the "no free lunch" issue in developing an expressive GNN model. However, we do believe there are many repeat computations the (k: -LL that can be safely removed without the hurt the expressive power. We leave it to our future work.
C Additional discussion on FFWLL
C.1 Detailed proofs for (k, F)-F
In this section, we provide all detailed proofs for (k, FW-+..+ Specifically, we will use (k, FFFL++ to implement many existing powerful GNN/WL models with the best matching expressive power. To simplify notations and make it more clear, let Ć denote the color output by (k, F)-FWL+ Č denote the
22

---

color output by any existing model we want to compare. Further, denote C¹ (v1, 02) as the color of tuple (1), 02) iteration if 2.
SLFWL(2) [12]: We prove Proposition 3.5 in the main paper. We restate it here:
Proposition C.1. Lest = 1, == 2, and ES(v) = (o1) the corresponding (k, F)-FFL++ instance is equivalent to SI.FWI(2) [2] and strictly more powerful than any existing node-based subgraph GNNs.
Proof. Given = 1, k 2, and ES(v) (((( U. (12), FWL+ can be written as:
the color update equation of (k, t)-
02) HASH((*-1(1) v2), H ( ()) (w. (w,, m2)) |w E N (N
(24)
We can see Equation (24) exactly matches SLFWL(() stated in [12] and trivially this instance is as powerful as SLFWL(2). Further, given Theorem 7.1 in [12], we conclude that this instance is strictly more powerful than all existing node-based subgraph GNNs.
5-k-LWL: The aggregation scheme of 6-k-LWL can be written as:
(v())
e (z(r) E [a)),,
(25)
where (v(v) (Ve/j w E Qi(v;)). Next, we prove Proposition 3.6 in the main paper. We restate it here:
Proposition C.2. Lett = 1, k = k and ES(v) = - Qi(v;), the corresponding (k, FWWL+++ instance is more powerful than 6-k-LWL [8].
Proof. Given / = 1, k k. and ES(v) = - Qi (v:), the color update equation of (k, ()WLL+ can be written as:
A (vv)) = (IASH(('-(()) (CC'+(u)) u (v))) e (o))))))
(26)
i=1
Given two k-tuple V1, V2 E V* (G), it is easy to see that for any node w E V(G), e (v1,w/))) will be different to (V2,m//)) long there exist any U1s and ua such that U1s is neighbor of node w but U2 is not for any E [k), i + j. This means that for any u E (F)v,, (u) can injectively encode whether w is neighbor to all other nodes in tuples. Further, as U (1()) includes neighbors of all nodes in tuple v, can injectively encode (VC/(vww))le E Qi (v;) (k)) for any by ((C--(u))u E (V())) E U Qı(e:) H. Now, given any two graphs G, H with Coo (G) = 600 (H). For any V1 E (*( and v2 E V*(H) with Co (v1)
C (v2). we must } } for any j E [k] given the above
have (v1. statement. Then, it is easy verify that we cannot further refine the color of tuple v and v2 if we use the stable color of (k, ()FL+ as initial color to perform another iteration of d-k-LWL, so as the final graph color histogram. Therefore, we conclude that (k, ()FF+++L+++ is more powerful than 5-k-LWL.
Qi(11) J (V=,(v)))))
E Q1(2)))
GraphSNN [21]: The GNN aggregation scheme of GraphSNN can be written as:
(w), =
a1 (C (w1, ( w), ( Ci, (ww,w)) Jao E Qi()).
(27)
E Vore2
Ed (01, = HASH(
(28)
0102
where Evyus vz J. IV va are the number of edges and nodes in the overlapping 1-hop subgraph between node U1 and 02 X is a constant. Next, we prove Proposition 3.7 in the main paper. We restate it here:
Proposition C.3. Let = 2, = 2, and (v)2(v) (Qi(1) n (v2)) x (Qi( (122), the corresponding (k, t) FWL+ instance is more powerfull than GraphSNN [21]..
23

---

Proof. Here we prove slightly stronger one: even without a hierarchical multiset but only plain multiset, the resulted (k. F)-F already powerful enough to match GraphSNN. Given (v1) n Q1((2)) x (Q1(1) n QiQQi(() (v2)), the color update equation of (FFW) can be written as:
k = 2, and (v)
C'(1,, 02) = HHSHHCC (v1, 02). &f ((' (u (2), u2) E uo (1), 12))) (( w2) E (QI(v1) n (1())) x (Qi(v1) n (1
(29)
First, we show that Ca (11,, v2) is already powerful recover all the information in Equation (28). For any (w1, w2) E (Q1 ( (Q1 (Q (v2)), wi and wy must all be common neighbors of node in and v2. Therefore
(Q1(11) n (e2)) will contain all node pairs in the l-hop overlapping subgraph of (21,02). Thus we have the size of (Q1(e1) n (e2)) x (Qi(1i n QI (12)) equal to |Vorell 1 and this information will be definitely encoded in C² (11,v2)
02).
by aggregating all possible tuple (E (2)1((1, w2) E of (mm (0)) v2)). Further, we have U2), which means C' (11, 02) will also encode {C w2) wy) E (11(1)) (122)) (Qi(v)) ( As CO (wi, W2) encode whether there is an edge between W1 and W2, is easy to see (C (wr, w2) (wi, wz) E (1)) n Q (v2)) x encode e. Thus we can conclude that C¹ (11, 02) can encode Equation (28). Namely, for any two tuples (111, U12), (121, U22) E (2)G), we have: C' (111, 012) = (121, (22) = C² (111, 012) = Ei (121. U22), for any 1 2 1.
(wi, E
(v2)) can
Second, for any tuple (11,w)) E VV) the neighbor in (),L) is (v1)). For any (wi, w2) (v1). ). it is easy to see that 8² (w1, w2) will be different between tuples with wi # w2 and w1 = W2. This implies that (ke F)-FWL+ can injectively encode ((((w, w) E Q1(11) B for any I
as (w1, w22) E Qf (v1, Namely, for any two nodes 11 02 E V(G), we have: (11,), =
(12,, v2) = (Cr, w1) luc E (v:)) = (CC-((w (w2, w2) m02 E (1((2)) B.
Third, since w1) E ( (V), 01), it is easy to verify that (k: f) f)FFWL+ can injectively encode (V wi lue E Qi(1)) / for any 1. Namely, for any two nodes v 222 E VVG), we have: C'(11 v1) (12, 02) = (C'-1(e1, w1) wi)lur E Qi(e1))
w2)) Q1 }.
(H). For any (U11, E V²(G) and (121, u22) E (²( with (* v12) -000 122), if u1 # U12, we must have U21 # U22 and we have (o00 (111, 012) = -0 U22) if ex 012) = Co00 (U21, U22) given the first state- ment. If U11 = V12 and U21 = U22. we further denote it by (e11, and (122, 022). We have (CC w1)) wnn E (u(en)) H1C=0 (W21, W21 ) 12211 E Qi (121) }} given the second statement and [ W11) ()n)|m wnn E {i()n) = 80000 (121, Wen) ) |w21 Q1 (121) given the third statemtn. Now, given the stable color output by (ke, FW-F, we can verify that performing another iteration using Equation (27) and Equation (28) will not further refine the color of (U11. u11) and (U22, U22).
Now, given any two graphs G, Hl with (xx(G)
resulting in the same final graph color histogram. This concludes the proof.
Edge-based subgraph GNNs The GNN aggregation scheme of edge-based subgraph GNNs like G-G [19] can be written as: Č¹ (111, 02, w2) = (AAH(C"" (11, U2, W2), ( Wi, w2) E {Qi(t))))
Vuz E (v(i),
(30)
8o (G) = HASH A ( (V1, U2 w2 E V(G) wy E Qi(r))Hlo E V(G))).
(31)
where we assume that the initial color of 2o (v) U2, W2) is (v if 02 # [11, w2] or (ASH((c(V))..) 1) if D2 = en or HASH((a(v2) (V2), 2) if U2 = Wy. Equation (30) can be described as in the subgraph rooted at edge (UI, w2). we do the 1-WL color update on all node U2. Meanwhile, the initial color is the node marking of and w2, which is the most powerful subgraph selection policy [19]. First, we show some useful lemma for edge- based subgraph GNNs.
Lemma C.4. Given two graphs G. H, for any two tuples (U11, V12) E VV),,,, (U21, (22) E VHH),, W12 E Q1(11)). and w22 E Qi we have Co (E11, U11, W12) = ( (U21, U21, W22) and Co0 (U11, W21, Wa1)= 6o0 (121, W22, W22) 8x8 (V11, U12 W12) (22 U22, w2z).
24

---

Proof. We prove it by contradiction. First, if U12 = Ui1 or U1 W12 we must have U22 = 221 or 122 W22. respectively, as the initial color of (U), U1, W2) and (V), W2, W2) are differ- ent from other nodes in the subgraph. Further it is easy to show that C (U11. V11, W12) = (121, U21, W22) = C (111. W12, W12) = C (121, W22, W22) as they are uniquely labeled. Second, if U12 & U11, W12 and 122 # 221, W22, we can leverage the fact that the informa- tion of tuple (V,, U1. W2) and (2), W2 W2) can be passed to other nodes injectively through mes- sage passing. Suppose we have Co (011; U12, W12) = (o0 (U21, U22, W22). if É (V11, U11, W12) of (121, U21, W22). by doing another m iterations (m is large enough), this discrepancy must be reflected by C (111, 12. W12) and (121, U22, W2z), respectively. Therefore, we must have C (V11, V12, w12) j Coc-m (121, 022, W22), which is contradiction to the stable color. The case of (V1, W2; wy) is similar to the first one. This concludes the proof.
Lemma C.S. Given two graphs G, H, for any two tuples (U11, E (²)G), (021, una) e (HH,,, Wia E Qi(en). and W22 E (1(22)) we have (0 W11, w12)(un e V(G)) {C W21, 122) V(HB if C (11 - (121, U21 W22)) and C (U11, W12, w12) = C00 (021, 122, W22)..
Proof. This lemma is an extension of Lemma B.6 in [12]. First, iven Lemma B.6 in [12]. it is casy to conclude that we have {( (011, W11, w12) Wi1 E Qu (Vn) n Qka (w12) } = {c (121, W21, w22) (wen E Qa, (12) n Qs (w22) B for any ki, h2 E N. This directly implies ((= (111, wi1, (12) E V(G)) = 1C (021, W21, W22) W22 E V(H)B. This concludes the proof.
Lemma C.6. Given two graphs G. H, for any two tuples (011,02) E V²(G), (021, 022) E (2HH,, w12 E Qi(vn), and W22 E Qi (v21), we have {(=00 W11, w12) E V(G)) = (C (121, W21, W22) (22) E (H)) R (111, U12, w12) = C (121, U22, W22).
Proof. Given Lemma C.4, if 6 (un1, V12, w12) = Eoc (021, 022, W22). we have 8oo (U11, U11, w1) = Eo (121, V21, W22) and C (111, W21, W21) = (021, W22, W22). Next, given Lemma C.5, we have ( (M11, Wi1, w12)(un E B = (121, W21. W22) W21 V(H)B. This concludes the proof.
Lemma C.7. For any two graphs G. H and two nodes vn E V(G) and v21 E V(I).. we have ( (011, Wn1, w1)) V(G) w112 Q1(en)} [[C W21, W22) w2n
V(H) } Juz2 Qi(ea)B if ( Wn1, w12) E Qi(1n))(un E V(G)
C (221, W21, w22) w22 E (v21 ) w21 E VV())
Proof. If we have H (e11, Wn,, (12)(w12 E Qi(en)Hen
V(G)
([C"0(02 W21, W22) 1222 E Qi (w2) B w2n E V(H)B. for any wn E V(G), we can find W21 gd W21, w22) E (vai) Next, as the color stable, based on Lemma C.6, we can conclude that &l ( Wn. (12]|un e V(G) 2 E (vn)) = d c(c= (U21, W21, w22) E VVH)) Ju E (v21))
V(H) such that &0 (vi,, WT1, w12) W12 (
Now, given t = 2, k = 2, and (v* = (12) x (v)). the corresponding (k, F)-F instance
can be written as:
8d (vi, U2) = HASH(("- 02), E1 ( -- (wi, (2) u2) E Qf (U1, v2))
(32)
[w] E (12) Hun E Q (v)))))
25

---

However, edge-based subgraph GNNs use 3-tuple representations instead of 2-tuples in the (k, t)-
FWL+, which makes the comparison not trivial. Therefore, we slightly rewrite the above equation:
(11, 22, w1, w2) HASH(C"-1(11 W2,
w1, w2). (o (u,, u2) u2) E (f (01, 12)
),
(33)
(11, 02, w2) = HASH(C 22, w2). [C U2, wn, w2) E (1(1))))
(34)
C'(11, = HASH((*- (11, v2), H.CH (V1, U2, w2)) E Qi(e))
(35)
where we let CO (2, (12),, and w2 E Qi(e1)) (e1). It is easy to verify that the above equations the equivalent to the original one. Now, we prove a strong lemma:
U2, m22) and (h 22 w1, w2) be the same for any (01, v2) E V²) w1
Lemma C.8. For any two graphs G. H, given two tuples (U11, 212) E V²(G) and (U21, 022) e (²(H), for any (wil, (1)) E (1(12) x Qi(v1) and (W21, W22) E Q1 (U22) x (v21), we have
Cl-1( (011: W11, W12) = (V21,, W21, w22) if C (' (011; U12; W11, W12) = (121, U22, W21, W22) for any 12
Proof. We prove by induction on l. The base case is easy to verify given Lemma B.1 and the definition of initial color in edge-based subgraph GNNs.
Now suppose it is true for 1 = ,,..., 1. At iteration I, if C' (011, 112 W11, w12) =
(121, U22, W21, W22), given Equation 33, we must have:
8 (v11; V12, W11, W12) = - (121, U22, W21,, W22),
(36)
C² (u11, U12) = C0 (00-1uu1. U22),
(37)
for any (M11, M12) E O (111))012) (v11, 112) and (u21, U22) E Qfuer (121, (22) at the same position.
Particularly, we have (V11, W11) E ff (U11, V12) and (121, W21) E Of (12)) (121, U22) and
they are in the same position. Given Equation (35), we have:
(v11, W11, 912)1912 E (vnn) = (121,, W21, y22) 1y22 E (Q21)))
(38)
Equation (38) further indicates that for any y12 E Q (111). we can find y22 E (121) such that c' (U11, Wn1, y12) = CL- (u21, W21, y22)- Next, given Equation (34), we can conclude that: (111) Wi1, 11 912) E QI(wn)) = -(C--1(( (121, 121 221 112) E Qi B- (40)
(39)
Since the statement follows at iteration 1 1- 1, we have -C I11 (21) E (w(w) = ( F21, 222,)12) 222 E (w2r)) We also have C² wi1, w119912 given Equation (39). This means that we must have (1-1(111, W11, 912) = C² (121, w21, 1/22) based on Equation (30). Finally, as W12 is one of y12 and W22 is one of 1/22 and it is one such pair that holds the statement at iteration I - 1. It must be the case that they are also the pair at iteration Z. This means we have Ci W11, W12) Ci- (V21, W21, W22). which concludes the proof.
(122, 121, U22)
Now we prove Proposition 3.8 in the main paper. We restate it here:
Proposition C.9. Lett 2, and (V) = (v2) x Q (v1), the corresponding (kLL)-FWL+ instance is more powerful than edge-based subgraph GNNs like P-GNN [19].
Proof. Note that the initial color of edge-based subgraph GNNs is weaker than (k, F)L+ given Lemma C.8, but is still sufficient to show that the stable color from (ks F)-F cannot be further re- fined by edge-based subgraph GNNs. For any two graphs G and Hf with do (G) dos (H), it is easy to see that for any (U11, U12) E VG) and W12 E Q1(1))), we can find a (U21, U22) E (H) and W22 E (112)) with 6o (V11, R2 W12) = e~ (121, 122, W22). Then, given Equation (34), we have ((0= (011, 212, Wn1 wr)) E Q1(11)) = (C=0002 222, W21, W22) Jun E Q2 (222)) B. Further, given Lemma C.S, we have ( (E11, W11, w12)(w11 Q1(v12) = C0 (021, W21, W22) W221
26

---

Q1(22) B Now, if we use the stable color from (k, FW-F as the initial color to do one more iteration of edge-based subgraph GNNs, it easy to see that the color of (1) W11, W12 and (121, W21, W22) cannot get further refined and we have Č (111. V1, W12) = C (U21. 822, W22) Note that the graph color histogram of edge-based subgraph GNNs is slightly different than (k, t)- FWL+ as in edge-based subgraph GNNs, the order of multiset is V/ - w2 + V1. In (k; ()-FWL+ the order of multiset is w2 - 12 + t1- However, based Lemma C.7, the first order is less powerful than the second order. Therefore we can conclude that the final graph color histogram of edge-based subgraph GNNs will also be the same. This concludes the proof.
The GNN aggregation scheme of KP-GNN with the shortest path distance kernel and peripheral subgraph encoder as 1-WL can be written as:
KP-GNN [22]:
(11, 01) HASH(C v1), 0 (C"" w), (1 w)) e V(G))),
(41)
('(11 02) = ( (11,))) 02), - w)|w E QSPD( (11) n (v2))))
(42)
where the initial color of C (v1, 02) is the isomorphism type of (vi, 02) and SPD(11, 02). Before we prove Proposition 3.9, we first show that a slightly stronger version of (k, ()-FWL+ is still bounded by KP-GNN.
,,,) ,2) (v1) n Q (v2). Further let the initial color (v1, 12) encode SPD(U1, 02), the corresponding (k, t)-FWL+ instance is at most as powerful as KP-GNN [22] with the peripheral subgraph encoder as powerful as 1-WL.
Lemma C.10. Lett = = K, == 2, and ES QSPD(
Proof. Given t = 1, k = 2, and ES = QSPp(( (11) n (12)), the color update equation of (k, F)-LL+ can be written as:
(11 02) = HASH(C" (01, 12). ( w) E (g) (Q)
(43)
C' We can see Equation (43) exactly match Equation (42). However, the update of C² (01, 01) is not equal to Equation (41) as the neighbor of (01, 01) in (Is, F)FLL+ only contain itself. Therefore it is easy to see that for any given two nodes U1 1/ E V(G), must have el ('(11, 01) (12, u2) (2)) Given two graphs G and H such that (G)
C (H), for any (U11, v12) E (G) and (U21, 9222) E (H) with (o00 (111, (12) = Cx2 822), we must have (C= w)) /w E QSPD(en.ee))) (v1) n (v12) = ((cx(22) w)) w E QS)D( (121) n Qi B. Thus, it is easy to verify that if we use the stable color output by KP-GNN as initial color to perform iteration of (k:, ()-FWL+ we have &o V12) = 6:0 (121, U22). Further, given Equa- tion (41), for any (W11, vn) E V2(G), we can find a (122, 022) E (H) such that Čo0 (M11, mn) = Eoe (122, U22), which means (000 (211, w1m)[ E V(G) = { (122, W22), /1222 E V(H) and thus HC"" W12)l (W11, W12) E (² = -000 (w21, W22) (22))(wer w22) E (H) This indicates that even if (ke FWLL+ use the shortest path distance as the initial color, we still have d00 (Wi1, w12) (wi, w12) E (G = (w2i, W22)] (w21,
if (11, 21)
(12), W22) E V²(H) } and thus the final graph color histogram cannot be refined. This concludes the proof.
Now, it is easy to prove Proposition 3.9 in the main paper. We restate it here:
Proposition C.11. Lert = 1, k 2, and ES(v) QSPD( (v1) ) Qi(2)z), (k, t)-FWL+ instance is at most as powerful as KP-GNN [22] with the peripheral subgraph encoder as powerful as 1-WL.
the corresponding
Proof. is easy to see that the corresponding (k, t)-FF)+ is weaker than Equation (43) with the initial color as the shortest path distance, we omit the detailed proof. Then, given Lemma C.10, we can directly conclude the proof.
We conjecture that if we further equip (k, f)-FWL+ with Equation (41), tk,+)-FWL+ can be as powerful as KP-GNN. We also conjecture that if we let / = p and k = 2, ES(v) (Qpp v2) n (v2))² with initial color as the shortest path distance, the resulting (k, 1)- FWL+ has a close relationship with KP-GNN with the peripheral subgraph encoder as powerful as LF) [12] and leave the detailed proof in the future.
27

---

GDGNN [23]] Before we give the formal update equation of GDGNN, we first formally de- fine (P U2) as a set of nodes that are in the shortest distance path between node is and v2.
Namely, SP (r1, 12) = [w[SPD(m, w) + SPD(w, 02) SPD(01, (11, U2), Ve E V(G)) if en o u2 and SP(11, v1) = {21)- Then, the color update equation of GDGNN can be written as:
(11, 122) = HASH(C"- 02), ( (01,'(e, w)lw E Qi(22) B. (01 w)lw E SP(C1, () (44)
Note that Equation (44) is slightly different from the original version of GDGNN [23] stated in their paper. In the original paper, the author use MPNNs in O(n) space. Meanwhile, they only consider the direct neighbor of node en and 02 in SP 02), and they only add it in the last layer. However, it is easy to verify that Equation (44) is least as powerful as the original version and show that the (k. t)-FL++ can be more powerful than this version. Now we prove Proposition 3.10. We restate it here:
Proposition C.12. Let to = 2, 2, and (S* = Qi(v2) x SP((1, v2), the corresponding (ke, t)-FL) more powerful than GDGNN [23].
Proof. Given t = 2, k = 2, and (v = Qi((2) x SP((1, 02), the color update equation of (ke, t)-FW++ can be written as:
(11, U2) = HASH(C" (v), 02), I1ll ( (
(m1, (1,,, u2) E w.) (U1, ("), u2))
(45)
[w E Q1 (62) B lw2 E SP(U),u2)])
First, as (v1, w1) E (11,, 12), we can directly conclude that ()-F))+ can injectively encode (11, lun E (r2) B for any I. Second, we also have (11, w2) E ((m),y)) (V1, 02). Further, as in the inner multiset, each element has the same W2. This means that the result of the inner multiset will not affect the information in the outer multiset and it easy to verify (e:, F)-F can injectively encode |( C (v1, w2) W2 E SSP(11, U2) D-
Now, given any two graphs G, H with (C2 -C²(H) For any (111, U12) E V²(G) and (22) E (HI) with (111, v12) = C (121, U22) we must have (C ww)luw e Qi (v12)B = {/= (121, (222),21))ee (21)|W21 E (i(v2) and (vn, w12)[u12 E SP(wn, v12) = (C (121, W22) Juzz E SP('2, 822) } based on two statements. Then, it is easy to verify that we use the stable color from (k, F)-L as the initial color to do one more iteration of GDGNN, the color of (111. (12) and (221, U22) cannot be further refined so as the final graph color histogram. This concludes the proof.
C.2 Discussion on the complexity
The space complexity of (k:, f)-FWL+ is still O(n²). However, the time complexity of (k, F)-F is dependent on the choice of ES()) and it is hard to give a formal analysis.
C,3 Limitations
In the paper, we implement several different instances of (k: ()-FWL+ which expressive power is closely related to existing expressive GNNs. However, the whole space of (k, ()-FWL++ is less explored. Especially, how many different FS((V) exists? Moreover, how do theoretically and quantitatively analyze the expressive power of (k: FWL+++ Finally, although (k: FWLL can be p arbitrarily powerful even within O(n²) space from the theoretical side, we observe it is sometimes hard to optimize the model achieve its theoretical power by using fewer embedding. Specifically, how to ensure the injectiveness of the multiset function? For example, if we use large and small k for (ks FWLL+ conduct graph isomorphism test, for each k-tuple, the hierarchical multiset The contains exponentially increased elements. So far, we only use the summation as the function to encode this hierarchical multiset. Although it is an injective function from a theoretical view, we find it works badly with information loss when the number of elements is too large. It is worth investigating how to design model architecture that can unleash the full power of (k, (FFL). We leave all these to our future work.
28

---

D Additional discussion on -2- and Nº-GNN
D.1 Detailed proofs for N2-FWL
In this section, we provide all detailed proofs for N2-FWL. To make it clear, we denote (11, U2) as the color of tuple (v1, #2) at iteration I for N2-FWL. We rewrite Equation 9 as:
e¹ (v1, 02) -HASH(C 02), {f (c- u2)((,,, E Pi (01,
(46)
(W1, W22 E (V2) (1(11)) (NV((1))
We start with the first lemma:
Lemma D.I. Given h large enough, N--FWL is more powerful than SLFWL(2) 122
Proof. Given large enough, is clearly that the neighbor N2- becomes Ni (v2) Ni (01). For any (wi, W2) E (12) x Ni (v1), it is easy to verify that Q ((er,ay)) ( (V1, U2) contains all tuples in the aggregation of SLFWLL(2). Further, the elements in NG (12) x N (v1) includes all elements in Qi (12) U Q1 (. Therefore, it is easy to prove that N2-FWL is more powerful than SIFWL(() by doing induction on Here omit the detailed proof.
L
Lemma D.2. Given h large enough, N--FWL is more powerful than edge-based subgraph GNNs.
Proof. Given h large enough, it is clear that the neighbor of N2-FWL becomes (12) x Ni (vr). The N2- exactly matches the instance in Proposition 3.8 with additional root nodes. As the initial feature root tuples( (11, U2), (02, 02)) are different from other tuples, its information will not affect other neighbors. This concludes the proof.
It is intuitive to conjecture that N2-FWL with the number of h is more powerful than edge-based subgraph GNNs with h-hop subgraph and we leave the detailed proof in the future. Now, we can prove Theorem 4.1 in the main paper. We restate it here:
Theorem D.3. Given is large enough, N2-FWL is more powerful than SLFWL(2) [12] and edge- based subgraph GNNs.
Proof. Lemma D.1 and Lemma D.2 directly implies the theorem. This concludes the proof.
Next, we prove Theorem 4.3 in the main paper. We restate here:
Theorem D.4. -2-FWL can count up (1) 6-cycles; (2) all connected graphlets with size 4; (3) 4-paths at node level.
Proof. Given Theorem 4.1, FW- more powerful than I2-GNN [19]. Given Theorem 4.1, 4.2. 4.3 in [19]. I2-GNN [19] is able to count to (1) 6-cycles; (2) all connected graphlets with size 4: (3) 4-paths node level. This concludes the proof.
Then, we prove Corollary 4.2 in the main paper. We restate it here: Corollary D.5. N2-FWL is strictly more powerful than all existing node-based subgraph GNNs and no less powerful than 3-WL.
Proof. Given Theorem 4.1, this corollary can be directly concluded given Theorem 7.1 in [12] and Proposition 4.1 in [19]. But we further give an example to show that even with = 1, N FWL is already powerful enough to distinguish some non-isomorphic strongly regular graph pairs that 3-WL cannot distinguish. When
1. the neighbors of N JFLL is (N1 (o1) (A (v:) O Ni (2 Consider the Shrikhande graph and 4x4 Rook's graph in Figure 2. It is well known this pair of graphs cannot be distinguished by 3-WL. First, look at node in and v2 in Shrikhande graph, (1 ( (T2 includes two green nodes, U1, and 02. This means that (w), W2) E (N1())) x No (x1)) n (N1()) (12))))))) contains pair of (W1, w2) such that wi is one green node and wy is the other. Given Definition A.2, (W1, W2) Q (2) U2). This means
that the information of 6 (w), W2) will be encoded into Č' (V1, 02) and we have (W1, w2) is not an
29

---

V2
11
22
Shrikhande Graph
4x4 Rook's Graph
Figure 2: The Shrikhande graph and 4 x Rook's graph.
edge. Similarly, in x Rook's graph, Ni n (w2) includes two green nodes, U1 and 02- Thus, (w1, W2) will be encoded into é¹ (v1, 22). However, (w1, w2) here is an edge, which will have a different isomorphism type than (w), W2) in the Shrikhande graph, thus resulting in different Ca (V1, U2) and further graph color histogram. This concludes the proof.
Finally, we prove Proposition 4.4 in the main paper. We restate it here: Proposition D.6. If Uf M', and R are injective functions, there exist a N2-GNN instance that can be as powerful N--FWL.
Proof. If U M and R are injective, they are exactly the same as HASH used in N2-FWL. Therefore, it is easy to prove it by doing induction on / to show that if N outputs the same color for two tuples, N2-FWL also does for any 2 and vice versa. We omit the detailed proof here.
D.2 Complexity analysis
In this section, we provide a complexity analysis of N²-GNN, Let m denote the number of edges in the graph and d denote the average degree of the graph. First, we consider is large enough, where the neighbor of N2-GNN becomes (1 ) (G As N2-GNN is instance of (2, -FWL, it straightforward that the space complexity of 2 GNN is upper-bounded by On?²). Further, each tuple needs to aggregate (d + 1)² different neighbors, which results in a total time complexity of dnn2d? = Omm²). Notes that the time complexity of N2-GNN the same as edge-based subgraph GNNs. However, the space complexity of N2-GNN is O(n²), which is far less than adge-based subgraph GNNs with (nm) space complexity.
If we consider a pratical h, the neighbors of N2-GNN is (N2 ) x (er()) (N This means, only (w1, W2) that within the overlapping h-hop subgraph of Uj and U2 can send message to U1, U2. Therefore, the time complexity is bounded by + which is still the same edge- based subgraph GNNs with h-hop subgraph selection policy. Further, is easy to verify that only tuple (wi, 02) with SPD(v), v2) S h can update its representation. Thus, in memory-sensitiv tasks, we can only keep representation for tuples that can be updated, resulting space complexity of O(nd").
D.3 Model implementation details
Here we provide the details about model implementation. As Nº-GNN is instance of (2, F)FLIA, we are dealing with a tuple of size 6 in the aggregation process. Note that for any tuple (V1, U2). f (01, 122) will also include itself. However, it does not increase the expressive power as
30

---

we already encode its information. Therefore, in the implementation, we remove it from the tuple. Thus, we implement the neighbor tuple as follows: for any 2-tuple (V,, U2). the message from each neighbor (w1, w22 E (21, 02) is defined as ((11, wn), ), (v1, W2), (w1, 02): (w2, 22), (w1, W2)). Note the order of tuples flexible as long as uniform across different neighbors, according to Definition A.2. We implement N2-GNN in memory way. To make it more clear, we slightly redefine some notations. Let h (v1. 02) be the representation of tuple (0), 02), ((o.,v>) (wi, W2) be
the message from the neighbor (w1, w2), _N2 2 22) be the set of all neighborhoods of (U1,82) in Nº-GNN with the output embedding hidden size of hs. We let the initial feature of tuple h (" U2) =
MLP((c(w>) + SPD(U1, v2)). The message function is implemented as:
uf(u1, 02) LIN (h' - (01, v2)) Tanh(W;))
(47)
(01, (Wi, w2) = LIN2 (11, wi), ut (11, w2), (w1, 02). ut (w2,, U2), (wn, W2)));
(48)
where LIN, is a linear layer project the embedding from hidden size h to a lower value d, named as inner size, W. Rdd E [5] are learnable weight vector with size and is element wise product, CON is the concatenation, and LIN, is another linear layer project the concatenated embedding from size 5 d back to hidden size h. is easy to validate that this implementation injective to tuple input. Next, the update function U is implemented as:
(011,02) MMLP' (1+t))Nh v2) +
Σ N
meer, v2) (W),,, (wI,
(49)
where e is a learnable scalar and MIP is one-hidden-layer MLP with hidden size and output size equal to h and activation function be Rel.u. Note that in the implementation we do not consider the hicrarchical multiset but directly pooling all neighbors together. We observe it already achieves superior results in all real-world tasks and is more parameter-saving:
As discussed in [12, 27], for each ( U2), add the representation of (u2, 02) can boost the performance in real-world tasks. Therefore, we adopt a similar way for all real-world experiments:
a' (U1, 02) = -MLP', ((1 + (.) h h U2) h² (12,
(50)
h' v2) h (v1, 02) + a' d'(1, 12)).
(51)
If add this additional aggregation, we will use the h'(1,, U2) instead of h (2(2), 02) as the output representation. We conjecture this works as virtual nodes in real-work tasks, which allows better mixture of node features and structure information. As indicated by [12], adding this term will not increase the expressive power from the theoretical side. Finally, the readout function is implemented in hicrarchical way: h(v1) = MLP (POOL ww) E v(G)))
(52)
hg = POOL2 (fh(w))w E V(G))),
(53)
where POOL, and POOL2 are two different pooling function.
In addition, we adopted two implementation strategies for N²-GNN. The first strategy is to keep all O(n²) tuples even if has a distance greater than h. Notes that will not aggregate information from other tuples but is only updated in Equation (50) and Equation (51). We observe it has great performance real-world tasks combined with Equation (52) and Equation (53). The second implementation is used for memory sensitivee tasks. We remove all tuples that have a distance greater than h. We refer to the first strategy as the dense version and the second strategy as the sparse version. We will specify which version we used in our experiments later on. The code is implemented using PyG [52]. We provide open-sourced code in attps://githhb com/ Ji Fiaruife Fenuu/een///nn Feng/N2GNI N2GNN for reproducing all results reported in the main paper.
D.4 Limitations
Although N2-GNN has efficient theoretical space complexity, the empirical space complexity can still be high as we need to keep neighbors index for all tuple (u1, U2) Q2 (11, 12). This introduces (11,
31

---

constant factor (5 in the implementation) on the saving edge index and corresponding gradients during training (see Table and Table 10 for the practical time and memory comparison). It still worth studying how to improve the empirical space complexity of N2-GNN. Further, in the current implementation, we didn't t consider the hierarchical set but directly pooled all elements together to save the parameters and computational cost. Additionally, each tuple needs to aggregate many more neighbors than normal MPNNs, which makes the sum aggregation hard to achieve injectiveness during the aggregation, introducing the optimization issue. These hinder the model from achieving its theoretical power. Finally, although N2-GNN has (nd"++2 time complexity, which is practical for most real-world tasks, the complexity still goes exponentially if the graph is dense (like strongly regular graph). But as the design space (k, t)-FF)+ is extremely flexible, it easy to design more practical and expressive instances suitable for dense graphs.
E
Experimental details
This section presents additional information the experimental settings.
E.1
Dataset statistics
Table 6: Dataset statistics.
Dataset
#Graphs
Avg. #Nodes
Avg. #Edges
Task type
EXP
1200
44.4
110.2
Graph classification
CSL
150
41.0
164.0
Graph classification
SR25
15
25.0
300.0
Graph classification
BREC
800
34.8
143.4
Pair distinguishment
Counting
5,000
18.8
31.3
Node regression
QM9
130,831
18.0
18.7
Graph regression
12k
12,000
23.2
24.9
Graph regression
ZINC-250K
249,456
23.1
24.9
Graph regression
E.2 Experimental details
In this section, we provide all the experimental details. First, we discuss some general experimental settings that, if not specified further, are consistent across all experiments.
Model. We adopt POOL, summation and POOL. as mean pooling in Equation (52) and Equa- tion (53), We set the e' in Equation (49), é in Equation (50) to be 0.0 and fix it during training and inference. At each MIP, we add batch normalization.
Training. For all experiments, we use Adam as the optimizer and rate scheduler. We set 12 weight decay to 0.0 across all experiments. All experiments are conducted on a single NVIDIA A100 80GB GPU.
as the learning
E.2.1 Graph structures counting
Model. For the substructure counting dataset, we adopt a similar setting as 12-GNN [19]. Specifically, set the number of hop h to be 1, 2. 3, 2, 2, 1, 4, for 3-cycles, 4-cycles, 5-cycles, 6-cycles, tailed triangles, chordal cycles, 4-cliques, 4-paths, and triangle-rectangle respectively. For all substructures, set the number of layers to 5, the hidden size h to 96, and the inner size d to 32. In the substructure count dataset, we remove all normalization layers. Finally, we use the sparse version of data preprocessing.
Training. The training/validationnnes splitting ratio 0.3/0.2/0.5. The initial learning rate 0.001 and the minimum learning rate is le-5. The patience and factor of the scheduler are 10 and 0.9 respectively. The batch size set to 256 and the number epochs is 2000. For all substructures, we run the experiments times and report the mean results on the test dataset.
32

---

E.2.2 ZINC
Model. The setting is the same for both ZINC-Subset and ZINC-Full except for the inner size. We set the number of hop be We set the number of layers to and the hidden size h 96. The inner size d is 20 for the ZINC-subset and 48 for the ZINC-full.
Training. The initial learning rate is 0.001 and the minimum learning rate is 1e-6. The patience and factor of the scheduler are 20 and 0.5 respectively. The batch size is set to 128 and the number of epochs 500. For both ZINC-Subset and ZINC-Full, we rum experiments 10 times and report the mean results and standard deviation on the test dataset.
E.2.3
QM9
Model. For all targets, we adopt the same setting. We set the number of hop h to be 3. We set the number of layers to 6, the hidden size h to 120, and the inner size to 32. We further add the resistance distance feature into the model, similar to the implementation in Feng et al. [22], Huang et al. [19].
Training. The initial learning rate is 0.001. The patience and factor of the scheduler are 5 and 0.9 respectively. The batch size is set 128 and the number of epochs 350. we rum experiments time and report the test result with the model of the best validation result.
E.2.4 CSL
We set the number of hop h to be 4, the number of layers to be 4, the hidden size h 48, and the inner size d to 16. We use the sparse version of data preprocessing and we do not add root aggregation (Equation (50)-(51)).
Model:
Training. The initial learning rate is 0.001 and the minimum learning rate is 1c-6. The patience and factor of the scheduler are 20 and 0.5 respectively. The batch size is set to 32 and the number of epochs is 80. We use 10-fold cross-validation and report the average results.
E.2.5
SR25
Model: We set the number of hop to be 1, the number of layers to be 6, the hidden size h to 64, and the inner size d to 16. We use the sparse version of data preprocessing and we do not add root aggregation (Equation (50)-(51)). Further, the normalization layer in SR25 is set to Layer normalization avoid test/training mismatch.
Training. The initial learning rate is 0.001 and the minimum learning rate is 1e-6. The patience and factor of the scheduler are 200 and 0.5 respectively. The batch size is set to 15 and the number of epochs is 800. We report the single-time results.
E.2.6 EXP
Model: We set the number of hop h to be 3, the number of layers to be 4, the hidden size to 48, and the inner size d to 24. We use the sparse version of data preprocessing and we do not add root aggregation (Equation (50)-(51)).
Training. The initial learning rate is 0.001 and the minimum learning rate is le-6. The patience and factor of the scheduler are 20 and 0.5 respectively. The batch size is set to 32 and the number of epochs is 200. We use 10-fold cross-validation and report the average results.
E.2.7 BREC
Model: We set the number of hop h to be 8, the number of layers to be 4, the hidden size to 64, and the inner size d to 32. Mcanwhile, the output channel is set 16 for computing the similarity. We use the sparse version of data preprocessing and we do not add root aggregation (Equation (50)-(51)).
Training. We follow the same training and evaluation procedure as described by BREC [45]. The initial learning rate is 0.001 and the weight decay is set to 0.0001. The batch size is set and the number of epochs is 20. Due to the resource limitation, we only ran the experiment on 340 graph pairs (removed 20 4-vertex-condiin the reported result for IN-
graphs and 40 CFT graphs), which follow the same protocol as
33

---

F Additional experimental results
E.1
Ablation studies for (k: I-FFI+++++
In this section, we provide an additional ablation study on (2,1)-FWL++ by varying different and E.S. We select two important F.S mentioned in our paper-Q1(t) and SP(11, 02). We conduct experiments on both Expressiveness verification datasets and counting datasets. The experiment setup is the same as what is discussed in the above section. The results can be seen in Table 7 and Table 8. Notes that we find the performance of SP or SP x SP on counting dataset is similar to MPNN and thus omit it in Table 8.
We can see that as long as t = 2, we can have a perfect performance on SR25 no matter we use SP Q1 (v1). this aligns with theoretical results. Further, SP(U1, U2) x Q1 (v1) achieve great results on all counting tasks and expressiveness verification. This indicates the SP can also be great choice in the practical scenario.
Table 7: Expressive power verification (Accuracy) for different (2, (2.W)....+
Datasets
((()) t= 1, UQ,(()) t= (g) 2.SP(n, Qi(ni) t= 2, og) SP()))))
EXP
100
100
100
100
100
CSI.
100
100
100
100
100
SR25
6.67
100
100
Table 8: Evaluation of different (2, FFFL++ variants on Counting Substructures (norm MAE), cells with MAE greater than 0.01 are colored.
Target
/ 1, (1n)
1, Q1 (vi) U (vz)
t= SP(,,, v2) x (wi)
Nº-GNN
Tailed Triangle
0.0033
0.0031
0.0022
0.0025
Chordal Cycle
0,0019
0.0017
0.0021
0.0019
4- I-Ciqque
0.0013
0.0014
0.0016
0.0005
4-Path
0.0046
0.0043
0,0076
0.0042
Tri.-Rec.
0.0043
0,0053
0.0081
0.0055
3- 3-Cycles
0.0005
0.0006
0.0004
0.0002
4- Cyclee
0.0027
0.0022
0.0037
0.0024
5- Cycles
0.0051
0.0042
0.0037
0.0039
6- 6-Cycles
0,0113
0.0097
0.0097
0.0075
F22
Practical complexity of N2-GNN
In this section, we provide practical complexity analysis for N²-GNN, Here we use the cycle counting datasets with similar parameter size for all models and a batch size of 256. To ensure a fair comparison, in N2-GNN, we use the sparse version for data preprocessing (which is true for all compared models), and set the number of workers as 0 and random seed as for all models. The experiments are run on a single Tesla 1000 32GB GPU, We report the training time, maximum training memory, inference time, and maximum inference memory usage during inference for both h = and h = 2 for an average of 20 epochs. The results is shown in Table 9 and Table 10.
We that the empirical memory usage of 2 GNNN is much less than I2N when h and comparable when = 2. We conjecture the reason why N2-GNN require more training memory than 1NGNNN when h is that when h increase, each tuple will need aggregate much more neighbors than each node in 12-GNN and each aggregation require a constant size (5 in N2-GNN) of more memory for saving the gradients. Meanwhile, As mentioned in limitations (Appendix D), to enjoy some extent of parallelism, the current implementation of N2-GNN needs to save all neighbor indices, which introduces constant factor more memory on saving. But the inference memory N is less than 12- in both h = 1 and h 2. The training time and inference time of N²-GNN are also more efficient than I2- However, currently, the time and memory cost by subgraph GNNs. We do want to highlight several points: (1) By changing the way of implementation, 22-GNN can be implemented strictly within O(n²) space. Therefore, the merit of 2N- still holds. (2) The experiment is conducted on the same parameter real-world tasks, N2-GNN needs much fewer parameters to achieve SOTA results (Table 5). (3) In this work, we not only aim to propose new model but also mean to introduce a new flexible framework, (k: FWL+ The empirical success of 22-GNN demonstrates the great potential of this framework for designing expressive GNN variants.
N2-GNN are higher than
budget level. However,
34

---

Table 9: Practical usage comparison for / =
Params
Truining time (ms/epoch) Training memory (GB)
Inference time (ms/epoch)
Inference Memory (GB)
NGNN
186k
478.1
0.398
463.4
0.089
ID-GNN
135k
455.5
0.375
432.8
0,094
GNN-AK+
251K
546.5
0.479
490.1
0.090
R-GNN
194K
666.9
1.326
613.5
0,292
N F-NNN
202K
368.3
0.744
0.140
Table 10: Practical usage comparison for h = 2.
2
Params
Truining time (ms/epoch) Training memory (GB)
Inference time (ms/epoch)
Inference Memory (GB)
NGNN
186k
516.5
0.916
470.7
0.198
ID-GNN
135k
521.7
0,858
471.5
0.211
GNN-AK+
251k
617.4
1.082
556.1
0,200
P-ONN
194K
926.8
3.012
770.1
0.675
Nº-GNN
202k
892.9
4.026
709.
0,660
F.3
Additional discussion on BREC experiment
In Table 11, we provide a complete comparison of baseline methods on the BREC dataset. Please the detailed description of all bascline methods in BREC [45]. We can see that N2-GNN achieve the best result among all GNN baselines and the second best result among all baselines, even if we only test on 340 pair of graphs. Particularly, we surpass I2-GNN all parts. This result empirically verified Theorem 4. that the theoretical power of N .NN more powerful than P--NNN. Meanwhile, we notice that SSWL can distinguish more CFI graph pairs than ours, which may contradict Theorem 4.1. This may be due to the fact that we remove 40 CFI graph pairs in the experiments given the resource limitation and SSWL_P uses layers in the experiment and only use 4 layers. Meanwhile, we don't implement the hierarchical multiset in the current version of NN-GNN, which slightly compromises the expressive power.
Table 11: Complete comparison on BREC dataset
Basic Graphs (60)
Regular Graphs (140)
Extension Graphs (100)
CFI Graphs (100)
Total (400)
Model
Number
Accuracy
Number
Accuracy
Number
Accuracy
Number
Accuracy
Number
Accuracy
3.WL.
60
100%
50
35.7%
100
100%
60
60.0%
270
67.5%
SPD-WL
41%
20.8%
83
52
86.7%
48
34.3%
5
5%
0%
105
26.2%
84%
60.8%
Ni
60
100%
99
85%
93
93%
0%
252
63%
98.6
100
M)
60
100%
50
35.7%
100
100%
41
41%
251
62.8%
NGNN
98.3%
48
34.3%
59
59%
0%
166
41.5%
DE+NGNN
100%
50
35.7%
100
100%
21%
231
57.8%
DS-GNN
96.7%
48
34.3%
100
100%
16%
222
55.5%
DSS-GNN
58
96.7%
48
34.3%
100
100%
15%
221
55.2%
SUN
100%
50
35.7%
100
100%
13%
223
55.8%
SSWL_P
60
100%
50
35.7%
100
100%
38%
248
62%
GNN-AK
100%
50
35.7%
97
97%
15%
222
$5.5%
KP-GNN
60
100%
106
75.7%
98
98%
11%
275
68.8%
P-GNN
100%
100
71 1%%
100
100%
21%
281
70.2%
PPGN
100%
35.7%
100
100%
23%
233
58.2%
6-k-GGNN
100%
50
35.7%
100
100%
6%
216
54%
SeGGNN
100%
35.7%
100
100%
1%
211
$2.8%
GSN
60
100%
99
70.7%
95
95%
0%
254
63.5%
DropGNN
52
86.7%
41
29.3%
82
82%
2%
177
44.2%
OSAN
93.3%
5.7%
79
79%
5%
148
37%
Graphormer
16
26.7%
10%
41
41%
10%
79
19.8%
N7-GNN
60
100%
100
71.4%
100
100%
27
27%
287
71.8%
F44
Ablation studies for N2-GNN
In this subsection, we perform ablation studies to investigate each component in N²-GNN. All ablation studies are performed ZINC-Subset and target C, in QM9, Except hyper-parameter mentioned later, all other setting is exactly the same as what is described in Section E.2.
In the first ablation study, we investigate different components of the model. Specifically, we analyze two components. The first component aggregation h (v1, v2) described Equation (50)-(51). The second component is the dense/sparse embedding described in Section D.3. In the ablation study, we verify different combinations of two components. For the model without Equation (50)-(51), to ensure that the size of the model is comparable, we increase the model hidden size to 120 and 136 for
35

---

ZINC-Subset and QM9, respectively. The results are shown in Table 12. First, we can see adding Equation (50)-(51) indeed improve the performance across different tasks. Second, by explicitly keeping ((n²) embedding the performance, of Nº-GNN on ZINC-Subset improved from 0.079 to 0.059. This may indicate that even though the two models have the same expressive power from the theoretical side, adding additional feature embedding can still boost the performance significantly in real-world tasks as allows a better mixture of both feature and structure information. Note that these two components were used in many previous models like ESAN [43], SUN [27], and SSWL+ [12], etc. However, our model still outperforms them by a large margin. This indicates that the expressive power of the model is still the most critical ingredient, adding these additional components is just way to unleash all the potential the model for real-world tasks.
Table 12: Ablation study of model components.
Table 13: Ablation study of h.
Model design
ZINC-Subset, 4 QM9 (C.)
h in NN- ZINC-Subset | QM9 (C.) J
Full
0.059 0.002
0.0760
h=1
0.150 = 0.009
0.0823
(122,, 22) sparse
0.064 + 0.003
0.0811
h=2
0.127 = 0.005
0.0808
0.079 + 0.003
0.0876
h=3
0.059 + 0.002
0.0760
w/o h (v2, 02) sparse
0.084 0.003
0.0847
h=4
0.063 + 0.004 0.0826
In the second ablation study, evaluate the effect of the number of hop h. We vary h from 1 4 and results are shown in Table 13. We can see an increase of h can boost the performance of the model, which has already been verified in previous subgraph- based methods. Particularly, for ZINC-Subset, we find that the third hop is critical to the performance. However, if we continue to increase the number of hops, the performance drops, which sign of overfitting.
36


Reviews:
[{"review_id": "p5SCbeSIHl", "reviewer": "Reviewer_X7wK", "summary": "The authors start by considering the k-dim Weisfeiler-Lehman test (WL). To solve the well-known problems of k-WL/FWL (high space complexity $O(n^k)$ and rigid design space), the authors propose two extensions of the k-FWL, named (k, t)-FWL and k-FWL+.\nThe first extension is based on the simple observation that k-WL aggregates each color separately while k-FWL aggregates the tuple of colors. Expressive results of (k,t)-FWL are provided (3.1 - 3.3). The second extension is based on the simple modification of k-FWL; instead of considering the whole vertex set, consider only a particular neighbor. These two extensions are then combined to (k, t)-FWL+, of which expressiveness results are provided compared to the previous gallery of GNN/WL models (3.5 - 3.9). Lastly, the authors then propose N2-GNN, an implementation of (2, 2)-FWL+ as well as empirical results showing the efficacy of N2-GNN.", "questions": "1. It states on pg. 4 lines 159-160, that \"size of Q_wF(w) will grow exponentially with an increase in the size of t\". Then does that mean that requiring O(n^2) is equivalent to confining t=2 (or at least small t)? Also, throughout the paper, the only time t is not 2 is in the theories when the authors prove a hierarchy w.r.t. t. Are there situations in which t should be set to 3 or higher?\n\n2. Is there any way of comparing the expressiveness of (k, t)-FWL and (k', t')-FWL with k+t = k'+t'? For instance, can one compare the expressiveness of (2, 3)-FWL and (3, 2)-FWL?\n\n3. Before combining (k,t)-FWL and FWL+, is it possible to also obtain expressiveness hierarchy results on FLW+ depending on the choice of ES? For instance, with fixed t=1 and k=2, can you say anything about the expressiveness across the choices of ES(v) as considered in Proposition 3.4 - 3.9?\n\n4. It is mentioned in the conclusions that the practical complexity of N2-GNN can still be unbearable, especially for dense graphs. Thus I'm curious about the running times of all the algorithms in comparison. Is there a trade-off if one sets the training budget approximately the same for all the algorithms?\n\n5. There was a mention of Puny et al. [43] that performs O(n^2) space 3-WL via graph polynomial features. Although the authors mentioned that they suffer from overfitting, I'm still curious. Are there any theoretical results (e.g., expressiveness hierarchy) or empirical results that compare [43] to (k, t)-FWL+?\n\n(minor suggestion: it would be nice to have a table of contents, maybe at the start of the appendix, to make it easier to navigate)", "limitations": "Although this work needs not address any societal impact, the work has no mention of its limitations and possible future works. I would like to ask the authors to include some of the possible limitations of their work (possibly with possible solutions, but I won't be negative if there are none for now, which by the way is also quite natural in my eyes.)", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Despite the complex nature of the concepts, the exposition of their main algorithm and the conceptual design was very well done (especially Figure 1)\n\n- I very much appreciate the simplicity of the idea that leads to space-efficient variants of (F)WL tests which are still quite powerful.\n\n- Although I did not check the proofs in detail, the authors provide an impressive list of theoretical results regarding their proposed (k, t)-FWL+, all of which provide solid theoretical superiority over previous works.\n\n- The experimental results seem promising.", "weaknesses": "- Although the concepts are well delivered, all technical details, especially the proofs, are entirely relegated to the Appendix. Are there any notable technical novelties in the proofs of the myriad of theoretical results, or are they somewhat standard?\n\n- It is expected that the expressive power of (k, t)-FWL+ depends heavily on the definition of ES, which the authors addressed via a myriad of propositions (3.4 - 3.9) for specific instances. However, if possible, it would be great to have some intuitions on the interplay of the choices of (k, t) and ES. Maybe the authors could choose a single proposition and try to explain the intuition behind it further (e.g., Proposition 3.4) via additional figures or discussions.\n\n- Some of the references are in poor condition (e.g., [11], [12], [16]).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and insightful comments! We revise all references and add contents for Appendix in our revision and reply to all other concerns below.\n\n### Weaknesses:\n>1. The novelties in the proofs. \n\n**Answer:**\nThanks for your mention. For all proofs, we mainly follow the previous strategies used in [1, 2]. However, we do want to highlight that most of our proof involving represent high-dimensional tuples using low-dimensional tuples, which is, to our best knowledge, not exists in any previous works and not trivial to prove. For example, in Proposition 3.7, we match the expressiveness of edge-based subgraph GNNs using $(k, t)$-FWL+ with $k=2$ (2-tuple based). However, it is well-known that edge-based subgraph GNNs are intrinsically 3-tuple-based. How to align each element in a 3-tuple to a 2-tuple-based method is non-trivial. \n\n>2. The interplay between $k$, $t$, and $ES$ and design principles.\n\n**Answer:**\nThis is a great question and we would like to answer it from two parts. \n\n**Interplay between $(k, t)$ and $ES$:** In general, this is a hard question to tackle. The introduction of $(k, t)$-FWL allows us to fine-tune between the time and space complexity to achieve the desire expressive power. Increasing either $k$ or $t$ can increase the expressive power (As indicated in Proposition 3.3). The introduction of $ES$ makes the expressive power not bounded by either $k$ or $t$. For example, we can let $k=2$, $t=1$, and $ES(\\mathbf{v})$ be all nodes in $4$-clique pass nodes $v_1$. This will give the model a better ability on counting this particular substructure. However, it is well-known this cannot be counted by 2-FWL or 3-WL [3]. \n\n**Intuitions behind Proposition 3.4-3.9:** We think the most important principle in our mind when proving Proposition 3.4-3.9 is to find a variant that can best match the expressiveness of the existing one. Therefore, the choice of $k$, $t$, and $ES$ all serve this purpose. We do believe there exist multiple solutions for some methods and leave it to our future works. \n\n\n\n\n\n### Questions:\n>1. Further clarification on the space complexity. \n\n**Answer:**\nThe space complexity of the $(k, t)$-FWL only depends on $k$ (the size of the tuple and thus the number of tuple $|V^k(G)|=O(n^k)$). If we fix $k=2$, the space complexity should be $O(n^2)$ no matter which $t$ we use. In the situation where we only have a limited memory budget and we still want a high-expressive GNN, a large $t$ is a great solution here. \n\n>2. The comparison on the expressiveness of $(k, t)$-FWL and $(k', t')$-FWL with $k+t = k'+t'$.\n>\n**Answer:**\nThanks for your insightful comment! We do believe there exists a further relationship between $(k, t)$-FWL and $(k', t')$-FWL with $k+t = k'+t'$ and had some attempts to prove that. However, we find it non-trivial to give formal theoretical proof and leave it to our future works.\n\n>3. The expressiveness of $ES$.\n\n**Answer:**\nThanks for your great question! As we mentioned in the answer to weakness 2, the choice of $ES$ is the key to the final expressive power of the model and its power will not be limited by either $k$ or $t$. In general response point 3, we further provide additional ablation study and show the practical power of different choices of $ES$. However, currently, it is hard to provide a canonical characterization of the expressive power of different $ES$. \n\n>4. Practical usage of $N^2$-GNN.\n\n**Answer:**\nIn general response point 2, we provide further analysis and discussion on both time and memory complexity of $(k, t)$-FWL and $N^2$-GNN.\n\n\n>5. Discussion on Puny et al [4].\n\n**Answer:**\nThanks for your insightful comment, [4] Introduce a new way to evaluate the expressive power of the graph model---the ability of the model to compute the equivariant polynomials up to a certain degree. However, as mentioned in [4], the equivariant polynomial is highly related to subgraph counting. Theoretically, we think equivariant polynomial is more suitable to compare with models like CIN [5]. It is hard to directly connect $(k, t)$-FWL+ with equivariant polynomials. Empirically, The comparison depends on the implementation of $(k, t)$-FWL+ and the choice of equivariant polynomial. Puny et al [4] do introduce PPGN++, which adds additional polynomial features up to 6 degrees that cannot be computed by PPGN and test its performance on ZINC-subset (0.071) and ZINC-full (0.020), which is lower than $N^2$-GNN.\n\n### Limitations:\nThanks for your great question! Due to the page limitation, we mainly discuss the limitation of $N^2$-GNN in Appendix D.3. Specifically, (1) although $N^2$-GNN holds its theoretical space complexity, it could still be memory-costly in dense graph due to the way of implementation. This can be solved by changing the way of implementation. (2) The model become hard to optimize with large $t$ and dense graph. The key reason is how to realize the injectiveness of multiset pooling function in neural version. So far, we only test the summation. We will investiage more powerful multiset pooling function like DeepSet [6] in the future. These are all future topic in this work. Meanwhile, as you mentioned, the in-depth theoretical analysis on different $ES$ is also very interesting and worth further investigation! We will provide complete discussion on the limitation and future work in the revision.\n\n**References:**\n\n[1] Morris et al., Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings, NeurIPS20.\n\n[2] Zhang et al., A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests, ICML23.\n\n[3] Arvind et al., On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 2020.\n\n[4] Puny et al., Equivariant polynomials for graph neural networks, ICML23.\n\n[5] Bodnar et al., Weisfeiler and Lehman Go Cellular: CW Networks, Neurips21.\n\n[6] Zaheer et al., Deep Sets, NeurIPS17.\n"}, {"review_id": "o1pkJxAcz9", "reviewer": "Reviewer_3qR2", "summary": "The paper deals with supervised learning on graphs. Specifically, it proposes a more fine-grained version of the (folklore) k-WL (k-FWL) hierarchy. In turn, these variants are neuralized via standard techniques. \n\nSpecifically, the authors propose the $(k,t)$-FWL, which extends the $k$-FWL by the parameter $t$, which controls which tuples are used for refining the color of a tuple. That is, following Eq. (6), the authors consider $t$-tuples to control the cardinality of the neighborhood of a given $k$-tuple. Subsequently, building on **standard constructions** from the $k$-WL literature, they investigate how, for a fixed $k$, varying $t$ controls the expressivity in terms of distinguishing non-isomorphic graphs (Prop. 3.1 to 3.3).\n\nThey further propose a simple extension of the above, the $k$-FWL, which uses a relaxed version of the neighborhood between a given $k$-tuple and a vertex in the underlying graph. Furthermore, they show that some recent GNN enhancements are subsumed by their framework.\n\nThe theory is complemented by an experimental study showing that the neuralized variants exhibit SOTA predictive performance on two common benchmark datasets.\n\n\n", "questions": "- What is the definition of \"hierarchical multiset\" (line 145)?\n- Can you quantify the h in Theorem 4.1?\n- What is required h for the statement of Theorem 4.3\n", "limitations": "See weaknesses. ", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The authors report good experimental results on established benchmark datasets. The experimental protocol looks meaningful. ", "weaknesses": "- The paper lacks clarity. For example, the exact definition of $Q^F_w(v)$ (line 136ff) is unclear.  It is a central concept introduced in the paper, and it should be properly formalized. Moreover, the definitions in Section 3.3 are not entirely clear and make it hard to verify the formal proofs. \n\n- The authors seem to **oversell their contribution**, e.g.,\n\n  - The discussion on the benefits of the k-FWL over the k-WL (lines 119 to 135) is folklore. There is no new insight. This also **holds for the \n  quadratic complexity of their algorithm** (e.g., lines 60 to 67). Note that big O notation is wrongly used here. Big Omega should be appropriate here.\n  - Subsection 3.1 just contains a simple extension of established ideas, e.g., from [8,12].\n  - Results in Section 4.2 are obvious by standard results from the GNN literature\n  - ...\n\n- The running time and memory complexity of the algorithms are **not formally proved**. This seems crucial for the present work. Also the authors seem to confuse big O with big Omega notation. \n- Relevant related work such as https://arxiv.org/abs/2203.13913 seems missing. \n\nComments:\n- It is not correct saying that the $k$-WL requires $\\mathcal{O}(n^k)$ space, it is a **lower** bound not an upper bound.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments! We will add corresponding references in the revision and reply to all other concerns below.\n### Weaknesses:\n>1. Further clarification of the definitions.\n \n**Answer:**\nWe are sorry for the confusion. Briefly speaking, $Q^F_{\\mathbf{w}}(\\mathbf{v})$ contains all possible tuples that pick up $m=0, \\ldots, min(k, t)$ elements from a $t$-tuple $\\mathbf{w}$ to replace elements in $k$-tuple $\\mathbf{v}$. Due to the page limitation, we provide the formal definition of neighborhood tuple $Q^F_{\\mathbf{w}}(\\mathbf{v})$ in Appendix A (as indicated in line 141). To further clarify it, we also provide an example in lines 140-141 and its construction procedure in Figure 1. For definitions in Section 3.3, we assume you are confused about the definition of equivariant set $ES$ as all other notations are standard notations. We provide the formal definition of $ES$ in lines 179-181. Please let us know if there are still confusions and we are more than glad to explain them all.\n\n>2. Further clarification on the novelties and big O notation.\n\n**Answer:**\nIn section 3.1, the discussion on folklore is mainly for showing the advantage of $k$-FWL over $k$-WL, i.e., we can achieve higher expressiveness with the same space complexity by redesigning the neighborhood aggregation, which is the insight and motivation behind our proposed $(k, t)$-FWL. There is no previous work, to our best knowledge, that leverages this insight further to propose similar methods as ours. In our general response point 1, contribution (1), we further clarify the contribution of the proposed $(k, t)$-FWL.\n\nThe big Omega notation $\\Omega(n^k)$ means the function is no less complex than $n^k$. It is usually used when we cannot prove the upper bound of a function is $n^k$. However, it is well-known that for $k$-WL, we have implementations whose complexity is exactly $n^k$, which obviously belongs to $O(n^k)$. If you are right, we believe there is no algoritm that can use the big O notation, since there definitely exists some inefficient implementation that requires larger complexity than its known lower bound.\n \n \n>3. Subsection 3.1 just contains a simple extension of established ideas, e.g., from [1,2].\n\n**Answer:**\nIn subsection 3.1, we introduce the $(k, t)$-FWL, which is totally different from the idea in [1, 2]. In subsection 3.2, we introduce equivariant set $ES$ to replace the $V(G)$ used in the original $k$-WL/FWL. Methods in [1, 2] are only special cases of our proposed method. Further, as discussed in the general response point 1, contribution (2-3), this extension allows us to design high-expressiveness GNNs in a fine-grained design space. It also allows the proposed framework to unify the majority of existing high-expressiveness GNNs (**Proposition 3.4-3.9**), which is hard to achieve and new to the community. These obviously cannot be done by the methods proposed in [1, 2].\n\n\n>4. Discussion on results in Section 4.2.\n\n**Answer:**\nThe reuslt in Section 4.2 (**Proposition 4.4**) is necessary for the completeness of our work. It shows that $N^2$-GNN can be as powerful as $N^2$-FWL.\n\n\n>5. further discussion on the complexity.\n\n\n**Answer:**\nIn the general response point 2, we provide further analysis and discussion on both the time and memory complexity of $(k, t)$-FWL and $N^2$-GNN.\n\n\n### Questions:\n\n>1. What is the definition of \"hierarchical multiset\" (line 145)?\n\n**Answer:**\nWe provide the definition and an example of hierarchical multiset in line 145-147. In a hierarchical multiset $\\{\\{\\mathbf{v} | \\mathbf{v}\\in V^t(G)\\}\\}_t$ over a $t$-tuple, elements are grouped hierarchically according to the node order of the tuple. For example, to construct $\\{\\{(v_1, v_2, v_3)|(v_1, v_2, v_3)\\in V^3(G) \\}\\}_3$ from $\\{\\{(v_1, v_2, v_3)|(v_1, v_2, v_3)\\in V^3(G) \\}\\}$, we first group together all elements with the same $v_2$ and $v_3$. That is,  $\\forall v_2, v_3 \\in V(G)$, we denote $t(v_2, v_3)=\\{\\{(v_1, v_2, v_3)|v_1 \\in V(G)\\}\\}$ as the grouped result. Next, use the similar procedure, we have $\\forall v_3 \\in V(G)$, $t(v_3) = \\{\\{t(v_2, v_3)|v_2 \\in V(G)\\}\\}$. Finally, we group all possible $v_3 \\in V(G)$ to get $\\{\\{(v_1, v_2, v_3)|(v_1, v_2, v_3)\\in V^3(G) \\}\\}_3 = \\{\\{t(v_3)|v_3 \\in V(G)\\}\\}$.\n\n\n>2. Can you quantify the h in Theorem 4.1?\n\n**Answer:**\n$h$ is a subgraph hop hyperparameter to restrict the subgraph scope to find neighbor tuples (thus the name subgraph GNN), as also used in previous work such as $I^2$-GNN [3]. From an implementation point, it can be understood as the radius of the subgraph to extract for each tuple. It does not affect the expressive power analysis, since we can simply set $h$ to be large enough to cover the whole graph so as to match the theoretical full-graph-view setting. For SLFWL(2) [2], as they don't have the $h$ hyper-parameter and operate on the whole graph (the full-graph-view setting), Theorem 4.1 need $h$ to be large enough to cover the whole graph.\n\n>3. What is required h for the statement of Theorem 4.3.\n\n**Answer:**\nThe required $h$ is the same as stated in [3] as the model need to see upon such hop to have the full picture of a particular substructure. That is, 1, 2, 2, 3, 2, 2, 1, 4, 2 for 3-cycles, 4-cycles, 5-cycles, 6-cycles, tailed triangles, chordal cycles, 4-cliques, 4-paths, and triangle-rectangles, respectively. We also use this setting in our experiments. We will include all the discussion in our revision. \n\n**References:**\n\n[1] Morris et al., Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings, NeurIPS20.\n\n[2] Zhang et al., A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests, ICML23.\n\n[3] Huang et al., Boosting the cycle counting power of graph neural networks with i$^2$-GNNs, ICLR23.\n"}, {"review_id": "0r7KFSFEhu", "reviewer": "Reviewer_E38T", "summary": "The authors propose generalizations of k-WL and k-FWL to (k, t)-FWL, and k-FWL+, which when combined, is notated as (k, t)-FWL+. They argue that (k, t)-FWL+ allow a more \"flexible and fine-grained\" space for exploring the graph expressiveness hierarchy, which is helpful in designing new GNN architectures. As a practical application, the authors propose Neighborhood^2-GNN which is based off a version of (2, 2)-FWL+, and outperforms state-of-the-art models on standard and synthetic tasks alike.", "questions": "1. How was N^2-FWL motivated? Why was it chosen over other possible (k, t)-WFL+ configurations? It seems as if it is not the only configuration that gives such properties.\n2. How does the runtime and memory consumption compare to node-based GNN models? And to traditional edge-based subgraph models? ", "limitations": "Some limitations are addressed, but only in the Appendix. Most points are addressed in the section in the appendix, but would prefer if it were in the main paper.\n\nNo potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper's strengths lie in the authors' extensions of FWL, Neighborhood^2-FWL (N^2-FWL), and its strong empirical performance with regards to baselines.\n\nThe new formulation of (k, t)-FWL+ allows researchers to easily derive new extensions of FWL algorithms (and lead to new GNN models as a result). N^2-FWL is an empirical demonstration of the power of (k, t)-FWL+, showing that even with O(n^2) space complexity, these algorithms can be highly expressive, which is supported with multiple experiments.", "weaknesses": "The paper's weaknesses lie in its lack of clarity. Especially as a rather technical paper, there seems to be a lack of intuition-based explanations and motivations for a large portion of the paper, which makes it hard to follow at points. More figures may help as well.\n\nIn addition, the authors' do not mention any details about time in the main paper (only in the Appendix), with a time complexity of $O(nd^{h+2})$, which they claim to be practical for real-world tasks. It would be nice to see empirical run-time, as well as memory consumption charts/tables which would help solidify the empirical contribution. \n\nTypo on line 181.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and constructive comments! We fix typo in revision and reply to all other concerns below.\n\n### Weaknesses:\n>1. Lack of clarity. \n\n**Answer:**\nWe apologize for the confusion regarding the intuitions and motivations as we want to ensure the correctness and completeness of all theoretical results in the paper. To make it easy to follow, we also provide further explanations (e.g. discussion at the beginning of Section 3.1, 3.2), examples (e.g. many definitions), and figures (Figure 1). In the general response point 1, we further clarified the main motivations and contributions of our paper. We will try our best to further improve the readability of our paper in the revision.\n\n\n>2. Further analysis on the complexity and practical usage.\n\n**Answer:**\nIn general response point 2, we provide further analysis and discussion on both time and memory complexity of $(k, t)$-FWL and $N^2$-GNN.\n\n\n### Questions:\n\n>1. The motivation  behind the $N^2$-FWL.\n\n**Answer:**\nThanks for your great comment! The motivation behind the $N^2$-FWL is that we want to demonstrate $(k, t)$-FWL+ can be used to design a model that can fit the complexity of real-world tasks. Since most current works evaluate the model on molecular tasks, we also target on it. The success of molecular tasks highly depends on the substructure counting ability [1] and we choose $N^2$-FWL because of its provable power on substructure counting (Theorem 4.3).\n\n>2. Practical usage of $N^2$-GNN.\n\n**Answer:**\nIn general response point 2, we provide further analysis and discussion on both time and memory complexity of $(k, t)$-FWL and $N^2$-GNN.\n\n**References**\n\n[1] Huang et al., Boosting the cycle counting power of graph neural networks with i$^2$-GNNs, ICLR23.\n"}, {"review_id": "0ojCewAyJq", "reviewer": "Reviewer_eNLB", "summary": "The Weisfeiler-Leman algorithm has been established as the formal tool of choice for measuring the expressivity of GNNs. The paper tackles the problem of designing \"higher-order\" GNNs, which has been previously considered by several papers. \n\nThe authors propose and combine two new ideas to supplement k-WL: (1) add in further subgraph information in a space-efficient manner via a hyperparameter $t$, and (2) allow neighbor selection in folklore-k-WL from any equivariant fashion, instead of the standard sets such as the set of all vertices or the set of all neighbors.  \n\nCombining these two ideas yields the (k,t)-FWL+ algorithm. The version for k=2 and t=2, i.e. (2,2)-FWL+, is thoroughly evaluated on several datasets, and it yields very good experimental results, esp. on the ZINC dataset. \n", "questions": "-", "limitations": "Yes.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The (2,2)-FWL+ performs very well on several datasets. On the ZINC datasets, they report 10.6% and 40.9% improvement over the second-best methods. \n\n2) The authors identify the problem of space limitations for higher-order GNNs and they seek to address them in their model. \n", "weaknesses": "1) The proposed algorithm lacks novelty: the claimed theoretical contributions are superficial. Graph Isomorphism can be obviously solved in quadratic space, if we were to allow iteration over all possible mappings between the two vertex sets. Such an algorithm might be space-efficient on paper but does not indicate any tractability since it brute-force tries all possible mappings. The proofs outlining the power and limitations of (k,t)-FWL are mild generalizations of known results, and lack any novel insights. \n\n2) Allowing equivariant sets for vertex choice in k-FWL is a reasonable idea: however, I would expect the authors to compare several \"equivariant set strategies\" and demonstrate the relative gains over non-classic equivariant sets such as V(G) or N(v,G), keeping other things equal (an ablation study). \n\nOverall, I feel that the paper is not much different from a multitude of papers on designing higher order GNNs using subgraph enhancement. Given the work that had already been done on this problem, the proposed model is incremental. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments! We reply all concerns below.\n### Weaknesses:\n>1. Further clarification on the novelties.\n\n**Answer:**\nWe agree that the Graph Isomorphism problem can be solved by brute-force enumerating all possible mappings in quadratic space. However, our $(k, t)$-FWL does not aim to do this but aims to provide a flexible and theoretically-guaranteed way to balance the expressive power and space complexity. $(k, t)$-FWL also brings a new view on how to trade-off the memory and time complexity of WL-based algorithms, which was not mentioned in any previous literature (previous $k$-FWL-based algorithms' time and space complexity **need to increase simultaneously**). In our general response point 1, contribution (1), we further clarified the contribution of $(k, t)$-FWL.\n\n>2. Further study on the $ES$.\n\n**Answer:**\nIn our general response point 3, we provide further ablation study on testing different $ES$ and $t$ using the expressiveness and counting datasets. \n\nWe kindly refer the reviewer to take the time to go through the general response and let us know if there are any further concern. We are more than glad to discuss them all!\n\n"}, {"review_id": "He2l9Pxut2", "reviewer": "Reviewer_vTyW", "summary": "The paper builds an extension to the $k$-FWL isomorphism test algorithms called $(k,t)$-FWL+. The proposed extended family subsumes the existing $k$-FWL and adds finer variants to the expressivity landscape of isomorphism testing algorithms. The $(k,t)$-FWL+ algorithm is a combination of two modified schemes to the original $k$-FWL algorithm. \n\nThe first one, called $(k,t)$-FWL, which also colors $k$ tuples, and draws insparation from the tuple based aggregation of the $k$-FWL algorithm vs. $k$-WL. The proposed algorithm changes the construction of neighborhood multi-stets used in the encoding step of the $k$-FWL algorithm. Briefly explained, instead of consisting of $n$ tuples of size $k$ , $(k,t)$-FWL aggregates a multi-sets consisting of $n^t$ tuples of size $\\sum_{i=0}^{\\min (k,t)}{ k \\choose i} {t \\choose i}$. Where each tuple in the new proposed algorithm holds more information than in the original $k$-FWL algorithm. The authors prove that for a fixed $k$, increasing $t$ induces a strict hierarchy where there exist a large enough $t$ for which the algorithm solves the isomorphism problem. \n\nThe second modification, called $k$-FWL+, unifies many previously introduced approaches, and suggests modifying the neighborhoods of tuples to be equivariant sets of nodes instead of the entire node set of the graph. Which can reduce time complexity of the algorithm. \n\nThe main contributions of the paper are (i) introducing a novel finer hierarchy of isomorphism testing algorithms; (ii) showing that it is possible to construct a strict hierarchy at fixed memory complexity that can achieve solving the isomorphism problem; (iii) coming up with a practical neural instantiation; and (iv) achieving state of the art results on common benchmarks. \n\n\n\n", "questions": "- A neural counterpart is suggested only for a single instance in the hierarchy. An interesting realm to explore would be to find a neural analog to the proposed hierarchy (similar to [1])\n- There seems to be a mismatch in the units for the QM9 experiment between your code and the code in the $I^2$-GNN repository [2]. They seem to convert back to previously used units to be consistent with previous works while your code uses the new conversion. Can the authors please clarify this issue? To my understanding, for example, the value that should be reported for $\\tilde{U}_0=U_0/0.04336414=0.5744$, where $U_0$ is the value reported in this paper. \n- Can the authors report runtimes of their GNN training and how it compares to other approaches? Since their approach trades space complexity for runtime complexity, I think it is necessary to show that the method remains scalable where the authors hinted that runtimes might increase when graphs are dense.\n\n- In the appendix, the authors say (l1094): \"...we observe it some time hard to optimize\n1095 the model to achieve its theoretical power by using fewer embedding\". Can the authors clarify this statement? \n\n\n[1] Provably Powerful Graph Neural Networks. Maron et. al. (NuerIPS 2019)\n\n[2] [$I^2$-GNN GitHub](https://github.com/GraphPKU/I2GNN/blob/master/run_qm9.py#L37)\n\n\n", "limitations": "- The authors describe the limitations of the method mainly in the appendix, I think some of the discussion should be moved to the main body (see questions section)\n\n**General comment:** I lean towards raising my score upon clarification of the experimental results. I think the proposed framework is a natural extension of the $k$-FWL family that elegantly formulates the trade-off between time and space complexity.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and successfully introduces the limitations of the $k$-WL hierarchy for the evaluation and design of more expressive GNNs. It is part of a body of works that refine the WL hierarchy aiming for more efficient algorithms with higher expressive power. \n\n- The paper introduces a general framework that is also shown to unify several recent approaches and can provide a canonical design space for previous and future GNNs. \n- The construction of the $(k,t)$-FWL hierarchy naturally arises from the original $k$-FWL algorithms and elegantly shifts memory complexity to runtime complexity in the fixed $k$ scenario. \n- The experimental evaluation is extensive and the proposed method seems to achieve SOTA performance. \n\n\n\n", "weaknesses": "- The paper does not properly discuss the \"no free lunch\" that hides in the proposed method. Indeed, the authors came up with a fixed space complexity hierarchy which, for large enough parameter $t$, can solve the isomorphism problem. But, this comes at the cost of time complexity - having to aggregate an exponentially growing number of tuples ($O(n^t)$). The authors deferred most of this discussion to the appendix, while I believe it should be placed in the main body of the paper.\n- A valuable ablation study lacking in the paper is an experiment showing the performance of several variants of the new proposed hierarchy on the substructure counting benchmark. Since it is unclear what each variant gains in expressiveness, I believe such an evaluation will contribute to the paper's intuition and wholeness.\n- Questionable results in the QM9 dataset. See the questions section.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your acknowledgment of our contribution and constructive comments! We reply to all your concerns below.\n\n### Weaknesses:\n\n>1. Further discussion on $(k, t)$-FWL in the main paper.\n\n\n**Answer:**\nThanks for the helpful comment! We mentioned the exponentially growing on the time complexity when increase the $t$ in $(k, t)$-FWL in line 159-160. However, due to the space limitation, we can only give more discussion in Appendix. We will provide in-depth discussion on the \"no-free lunch\" in the main paper in the revision. \n\n>2. Experiment on different variant of $(k, t)$-FWL+ hierarchy.\n\n**Answer:**\nThanks for the insightful comment! In general response point 3, we provide further ablation study on testing different $ES$ and $t$ on counting substructure dataset. In the experiment, we can observe clear expressive power difference on different variants.\n\n### Questions:\n>1. Neural analog to the proposed hierarchy.\n\n**Answer:**\nAlthough we didn't mention the neural analog of $(k, t)$-FWL+ but only $N^2$-FWL. It is straightforward to obtain neural analog for any variant of $(k, t)$-FWL+ by replacing $HASH$ with MLP, multiset pooling with injective multiset function like DeepSet [1], or summation. We will add detailed discussion in the revision.\n\n>2. Issue on the QM9 experiment.\n \n **Answer:**\nWe check our code and the code provided in $I^2$-GNN Github again. We believe we are following the same evaluation standard as previous works including $I^2$-GNN [2], KP-GNN [3], NGNN [4]. For all methods including ours, we train the model using the unconverted but normalized target value. After training, we first un-normalize it by multiplying the standard deviation and then use the conversion to convert the value and report the converted one. The only difference between ours and $I^2$-GNN is that they use a slightly different constant for **HAR2EV** in the conversion, where we use 27.211386246 and $I^2$-GNN use 27.2113825435. However, the value we used is consistent with the original code in PyG [5], KP-GNN [3], and NGNN [4]. Additionally, the constant factor for $U_0$ is HAR2EV=27.211386246 but not KCALMOL2EV=0.04336414. Therefore, we believe the comparison of the QM9 dataset is fair.\n\n>3. Practical usage of $N^2$-GNN.\n\n**Answer:**\nIn general response point 2, we provide further analysis and discussion on both time and memory complexity of $(k, t)$-FWL and $N^2$-GNN.\n\n>4. Optimization issue on the $(k, t)$-FWL+.\n\n**Answer:**\nThanks for mentioning that! The key point here is the injectiveness of the multiset function. For example, if we use large $t$ and small $k$ for $(k, t)$-FWL+ to conduct graph isomorphism test, for each $k$-tuple, the hierarchical multiset $\\{\\{\\}\\}_t$ will contains exponentially increased elements. So far, we only use the summation as the function to encode this hierarchical multiset. Although it is an injective function from a theoretical view, we find it works badly with information loss when the number of elements is too large. A similar issue can be founded in over-squashing [6]. However, we believe this issue can be alleviated by more powerful injective multiset functions like DeepSet [1] or increase the width of the embedding.\n\n\n**References**\n\n[1] Zaheer et al., Deep Sets, NeurIPS17.\n\n[2] Huang et al., Boosting the cycle counting power of graph neural networks with i$^2$-GNNs, ICLR23.\n\n[3] Feng et al., How powerful are k-hop message passing graph neural network, NeurIPS22.\n\n[4] Zhang and Li, Nested graph neural networks, NeurIPS21.\n\n[5] Fey and Lenssen, Fast Graph Representation Learning with PyTorch Geometric, ICLR19 workshops.\n\n[6] Topping et al., Understanding over-squashing and bottlenecks on graphs via curvature, ICLR22. "}]

Author rebuttal:
We thank all the reviewers for their constructive and insightful comments. Here we respond to some general concerns mentioned by the reviewers. **All tables mentioned in the response are provided in the PDF**.

### 1. Further clarify the motivations and contributions.

**Motivations:** We try to tackle two intrinsic limitations of $k$-WL/FWL. Namely, (1) the concurrent growth of both the time and space complexity when increasing $k$ and (2) the huge expressiveness gap between two consecutive values of $k$. 

**Contributions:**
(1) To tackle the first limitation, we propose $(k, t)$-FWL, which replaces the nodes to traverse (used for defining a $k$-tuple's neighbors) with $t$-tuples. We theoretically show that by varying $t$, we can construct an expressiveness hierarchy with a fixed $k$ (fixed space complexity) (**Proposition 3.1; 3.3, Theorem 3.2**). Although it is true we can solve the graph isomorphism problem by permuting all possible mappings between two graphs ($O(n^2)$ space complexity), there is no previous work theoretically establish an expressiveness hierarchy on a fixed space complexity---this hierarchy enables **flexibly tuning the expressive power** (with theoretical guarantee) in a fixed space budget, which is **not feasible** by brute-force methods. 


(2) To tackle the second limitation, we propose $k$-FWL+. In $k$-FWL+, we introduce the equivariant set $ES$ to replace the $V(G)$ used in the original $k$-WL/FWL. Although previous works [1, 2] also modified the $V(G)$, they only introduce a particular case, like 1-hop neighboring nodes of the $k$-tuple. Instead, we **generalize it to a much broader space**. This brings two advantages, (1) a new insight into how to design GNNs based on $k$-WL/FWL using fine-grained ES definitions and (2) unification of a wide range of previous GNNs. These cannot be achieved by any previous work like [1, 2].

(3) Combining (1-2) results in a new framework named $(k, t)$-FWL+. $(k, t)$-FWL+ is a very flexible framework that can unify the majority of previously proposed high-expressive GNNs (**Propositions 3.4-3.9**). Based on the $(k, t)$-FWL+ framework, we propose $N^2$-FWL and its neural version $N^2$-GNN, which is provably more powerful than all node-based subgraph GNN and SLFWL(2)[2], as well as existing edge-based subgraph GNNs [3] (**Theorems 4.1-4.2**). We also prove its strong substructure counting power in **Theorem 4.3**.

(4) We evaluate $N^2$-GNN on many benchmark datasets. $N^2$-GNN achieves **new SOTA results** on ZINC-subset/full datasets with the **smallest parameter size** (306k in ZINC-subset/ZINC-full compared to ~500k of other models). Specifically, on ZINC-subset, we improve the previous SOTA MAE **from 0.066 (Specformer) to 0.059**, which is the first time a model can reach below 0.06 MAE. On ZINC-full, the advantage is even huger, **with 0.013 new SOTA MAE** compared to the previous 0.022. These results are **significant enough** for the community, and further demonstrate the power and flexibility of $(k, t)$-FWL+ on designing GNNs fitting the complexity of real-world tasks.


### 2. Analysis of time and space complexity of the proposed methods.

**Theoretical analysis**: For $N^2$-GNN, we provide complexity analysis in Appendix D.2. For $(k, t)$-FWL, the space complexity is $O(n^k)$ as we only need to store representations of all $k$-tuples. For time complexity, if $k$ and $t$ are relatively small, to update the color of each $k$-tuple, $(k, t)$-FWL needs to aggregate all $V^t(G)$ possible neighborhood tuples, resulting in $O(n^{k+t})$ time complexity. If both $k$ and $t$ are large enough (related to $n$), the time complexity further increases to $O(n^{k+t}\cdot m\cdot(\frac{q!}{m!})^2)$, where $m=min(k, t)$ and $q=max(k, t)$.  For $k$-FWL+ and $(k, t)$-FWL+, the space complexity is $O(n^k)$. However, since the time complexity highly depends on the choice of $ES$, it is hard to provide a formal analysis for it.

**Empirical study**: Here we show the practical usage of $N^2$-GNN (Table 1, 2) using the cycle counting datasets with a similar parameter size for all models and a batch size of 256. We report the training time, inference time, and maximum memory usage during inference for both $h=1$ and $h=2$ for an average of 20 epochs. 

We can see that the empirical memory usage of $N^2$-GNN is almost the same as $I^2$-GNN and the time is worse. As we mentioned in limitations (Appendix D.3), to enjoy some extent of parallelism, the current implementation of $N^2$-GNN needs to save all neighbor indices, which introduces a constant factor of more memory. However, we do want to highlight several points: (1) By changing the way of implementation, $N^2$-GNN can be implemented strictly within $O(n^2)$ space. Therefore, the merit of $N^2$-GNN still holds. (2) The experiment is conducted on the same parameter budget level. However, in real-world tasks, $N^2$-GNN needs much fewer parameters to achieve SOTA results. (3) In this work, we not only aim to propose a new model but also mean to introduce a new flexible framework, $(k, t)$-FWL+. The empirical success of $N^2$-GNN demonstrates the great potential of this framework for designing new expressive GNN variants.


### 3. Additional ablation study.

We provide additional ablation study on $(2, t)$-FWL+ by varying different $t$ and $ES$ (Table 3 and 4). We select two important $ES$ mentioned in our paper---$Q_1(v)$ and $\mathcal{SP}(v_1, v_2)$. Notes that we find the performance of $\mathcal{SP}$ or $\mathcal{SP} \times \mathcal{SP}$ on counting dataset is similar to MPNN and thus omit it in Table 4.

**References:**

[1] Morris et al., Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings, NeurIPS20.

[2] Zhang et al., A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests, ICML23.

[3] Huang et al., Boosting the cycle counting power of graph neural networks with i$^2$-GNNs, ICLR23.


Meta-review: This paper is an attempt to address two limitations in the existing expressiveness hierarchy $k$-WL/FWL: 1) they require both the time and space complexity to grow simultaneously, 2) the only adjustable parameter is $k$ and there is no other fine-grained knob. To address the first limitation, the authors propose $(k,t)$-FWL, a novel hierarchy that allows one to increase expressive power while fixing space complexity (by fixing $k$ and increasing $t$). The second limitation is addressed by $k$-FWL+, where the authors replace the vertex set with "equivariant set" to allow for more flexibility. The paper then proceeds to combine the two variations to yield $(k,t)$-FWL+, and show that many existing works can be subsumed by the new framework. The authors then proceed to propose and examine a specific example of $(2,2)$-FWL+ named $N^2$-FWL and its GNN version. The proposed architecture shows promising performance, achieving the SOTA for the ZINC dataset.

There were active and extensive discussions between the authors and reviewers, and unfortunately, even after the discussion phase, the evaluations stayed divergent. After carefully reading the reviews, rebuttals, and the follow-up discussions, my conclusion is that the merits of this paper outweigh the shortcomings. 

As pointed out by the reviewers, the paper has some downsides, such as overselling the space complexity and limited novelty. For example, it was pointed out that solving the graph isomorphism problem in $O(n^2)$ space is possible in a brute-force way (if time is not a problem). However, I am convinced by the authors' response that the paper's key contribution is in the novel hierarchy with fixed space complexity (which could be any $n^k$, not just $n^2$) rather than achieving the narrow goal of solving the graph isomorphism problem in $n^2$ space. As for proof novelty, too, I believe that the novelty lies in the new framework, so the fact that the proofs follow from standard known results does not look like a major problem to me. Reviewer eNLB questioned the paper's novelty due to connection to subgraph enhancement GNNs, but I am more or less convinced by the authors' detailed responses that the proposed framework contains novel elements.

That said, there is certainly room for improvement that the authors should address in the revision. As pointed out by multiple reviewers, the main body does not discuss the time complexity in detail and defers discussions of limitations to the appendix; such limitations ("no free lunch") should be better highlighted/discussed in the main text. Two reviewers commented that clarity needs to be improved, and I also found it quite hard to read the paper; for example, I would advise against deferring key mathematical definitions such as $Q^F_w$ to appendices. Please also make sure to include ablation studies and runtime analysis in the revision, as they were also brought up in the reviews.
Decision: Accept (poster)