Extending the Design Space of Graph Neural Networks by Rethinking
  Folklore Weisfeiler-Lehman
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.
Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, Yixin Chen
# Towards Arbitrarily Expressive GNNs in \(O(n^{2})\) Space by Rethinking Folklore Weisfeiler-Lehman

###### 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^{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, 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 superior performance on almost all tasks, with record-breaking results on ZINC-Subset **(0.059)** and ZINC-Full **(0.013)**, outperforming previous state-of-the-art results by \(10.6\)% and \(40.9\)%, respectively.

## 1 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; 2; 3; 4]. However, the expressive power of message passing GNNs is bounded by the one-dimensional Weisfeiler-Lehman (1-WL) test [5; 6]. As a result, numerous efforts have been made to design GNNs with higher expressive power. We provide a more detailed discussion in Section 5.

Several works have drawn inspiration from the \(k\)-dimensional Weisfeiler-Lehman (\(k\)-WL) or Folklore Weisfeiler-Lehman (\(k\)-FWL) test [7] and developed corresponding neural versions [6; 8; 9; 10]. However, \(k\)-WL/FWL has two inherent limitations. First, while the expressive power increases with higher values of \(k\), the space and time complexity also grows exponentially, requiring \(O(n^{k})\)
space complexity and \(O(n^{k+1})\) 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 hyper-parameter being \(k\). However, there is a significant gap in expressive power even between consecutive values of \(k\), making it hard to fine-tune the tradeoffs. Moreover, increasing the expressive power does not necessarily translate into better real-world 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 \(k\)-FWL and \(k\)-WL have the same space complexity but \(k\)-FWL can achieve the same expressive power as (\(k\)+1)-WL. We found the key component that allows \(k\)-FWL to have stronger power is the tuple aggregation style. Enlightened by this observation, we propose \((k,t)\)-FWL, which extends the tuple aggregation style in \(k\)-FWL. Specifically, in the original \(k\)-FWL, a neighbor of a \(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,t)\)-FWL, we extend \(u\) to be a \(t\)-tuple, and allow flexible replacement schemes to insert the \(t\)-tuple into a \(k\)-tuple to define its neighbor. We demonstrate that even with a space complexity of \(O(n^{2})\), \((k,t)\)-FWL 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\)-FWL. 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 \(u\) are used to construct a \(k\)-tuple's neighbors) can actually be extended to any equivariant set of the \(k\)-tuple, resulting in \(k\)-FWL+. Combining the two modifications leads to a 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 \((k,t)\)-FWL+.

Finally, we propose an instance of \((2,2)\)-FWL+ that is both theoretically expressive and practically powerful. It considers the local neighbors of both two nodes in the 2-tuple. Despite having a space complexity of \(O(n^{2})\), which is lower than 3-WL's \(O(n^{3})\) space complexity, this instance can still partially outperform 3-WL and is able to count many substructures. We implement a neural version named **Neighborhood\({}^{2}\)-GNN (N\({}^{2}\)-GNN)** and evaluate its performance on various synthetic and real-world datasets. Our results demonstrate that N\({}^{2}\)-GNN outperforms existing SOTA methods across most tasks. Particularly, it achieves **0.059** in ZINC-Subset and **0.013** in ZINC-Full, surpassing existing state-of-the-art models by significant margins.

## 2 Preliminaries

**Notations.** Let \(\{\cdot\}\) denote a set, \(\{\!\!\{\cdot\}\!\!\}\) denote a multiset (set that allows repetition), and \((\cdot)\) denote a tuple. As usual, let \([n]=\{1,2,\ldots,n\}\). Let \(G=(V(G),E(G),l_{G})\) be an undirected, colored graph, where \(V(G)=[n]\) is the node set with \(n\) nodes, \(E(G)\subseteq V(G)\times V(G)\) is the edge set, and \(l_{G}\colon V(G)\to C\) is the graph coloring function with \(C=\{c_{1},\ldots,c_{d}\}\) denote a set of \(d\) distinct colors. Let \(\mathcal{N}_{k}(v)\) denote a set of nodes within \(k\) hops of node \(v\) and \(Q_{k}(v)\) denote the \(k\)-th hop neighbors of node \(v\) and we have \(\mathcal{N}_{k}(v)=\bigcup_{i=0}^{k}Q_{i}(v)\). Let SPD\((u,v)\) denote the shortest path distance between \(u\) and \(v\). We use \(x_{v}\in\mathbb{R}^{d_{n}}\) to denote attributes of node \(v\in V(G)\) and \(e_{uv}\in\mathbb{R}^{d_{n}}\) to denote attributes of edge \((u,v)\in E(G)\). They are 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\simeq H\)) if there exists a bijection \(\varphi\colon V(G)\to V(H)\) such that \(\forall u,v\in V(G),(u,v)\in E(G)\Leftrightarrow(\varphi(u),\varphi(v))\in E (H)\) and \(\forall v\in V(G),l_{G}(v)=l_{H}(\varphi(v))\). Denote \(V(G)^{k}\) the set of \(k\)-tuples of vertices and \(\mathbf{v}=(v_{1},\ldots,v_{k})\in V(G)^{k}\) a \(k\)-tuple of vertices. Let \(S_{n}\) denote the permutation group of \([n]\) and \(g\in S_{n}:[n]\rightarrow[n]\) be a particular permutation. When a permutation \(g\in S_{n}\) operates on any target \(X\), we denote it by \(g\cdot X\). Particularly, a permutation operating on an edge set \(E(G)\) is \(g\cdot E(G)=\{(g(u),g(v))|(u,v)\in E(G)\}\). A permutation operating on a \(k\)-tuple \(\mathbf{v}\) is \(g\cdot\mathbf{v}=(g(v_{1}),\ldots,g(v_{k}))\). A permutation operating on a graph is \(g\cdot G=(g\cdot V(G),g\cdot E(G),g\cdot l_{G})\). \(k\)**-dimensional Weisfeiler-Lehman test.** The \(k\)-dimensional Weisfeiler-Lehman (\(k\)-WL) test is a family of algorithms used to test graph isomorphism. There are two variants of the \(k\)-WL test: \(k\)-WL and \(k\)-FWL (Folklore WL). We first describe the procedure of 1-WL, which is also called the color
refinement algorithm [7]. Let \(\mathcal{C}^{0}_{1wl}(v)=l_{G}(v)\) be the initial color of node \(v\in V(G)\). At the \(l\)-th iteration, 1-WL updates the color of each node using the following equation:

\[\mathcal{C}^{l}_{1wl}(v)=\text{HASH}\left(\mathcal{C}^{l-1}_{1wl}(v),\{\!\!\{ \mathcal{C}^{l-1}_{1wl}(u)|u\in Q_{1}(v)\}\!\}\right). \tag{1}\]

After the algorithm converges, a color histogram is constructed using the colors assigned to all nodes. If 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\geq 2\), are generalizations of the 1-WL, which do not color individual nodes but node tuples \(\mathbf{v}\in V(G)^{k}\). Let \(\mathbf{v}_{w/j}\) be a \(k\)-tuple obtained by replacing the \(j\)-th element of \(\mathbf{v}\) with \(w\). That is \(\mathbf{v}_{w/j}=(v_{1},\ldots,v_{j-1},w,v_{j+1},\ldots,v_{k})\). The main difference between \(k\)-WL and \(k\)-FWL lies in their definition of neighbors. For \(k\)-WL, the set of \(j\)-th neighbors of tuple \(\mathbf{v}\) is denoted as \(Q_{j}(\mathbf{v})=\{\mathbf{v}_{w/j}|w\in V(G)\}\), \(j\in[k]\). Instead, the \(w\)-neighbor of tuple \(\mathbf{v}\) for \(k\)-FWL is denoted as \(Q^{F}_{w}(\mathbf{v})=\left(\mathbf{v}_{w/1},\mathbf{v}_{w/2},\ldots,\mathbf{ v}_{w/k}\right)\). Let \(\mathcal{C}^{0}_{kwl}(\mathbf{v})=\mathcal{C}^{0}_{kful}(\mathbf{v})\) be the initial color for \(k\)-WL and \(k\)-FWL, respectively. They are usually the isomorphism types of tuple \(\mathbf{v}\). At the \(l\)-th iteration, \(k\)-WL and \(k\)-FWL update the color of each tuple according to the following equations:

**WL:** \[\mathcal{C}^{l}_{kwl}(\mathbf{v})=\text{HASH}\left(\mathcal{C}^{l -1}_{kwl}(\mathbf{v}),\left(\{\!\!\{\mathcal{C}^{l-1}_{kwl}(\mathbf{u})| \mathbf{u}\in Q_{j}(\mathbf{v})\}\!\}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
a tuple of color \((\mathcal{C}^{l-1}_{2fwl}(v_{1},w),\mathcal{C}^{l-1}_{2fwl}(w,v_{2}))\) is aggregated. While in 2-WL, the colors of nodes are considered in separate multisets. To understand why this aggregation is more powerful, we can reformulate the color of the root tuple \(\mathcal{C}^{l-1}_{2fwl}(v_{1},v_{2})\) and further rewrite the update equation of 2-FWL as follows:

\[\mathcal{C}^{l}_{2fwl}(v_{1},v_{2})=\text{HASH}\left(\left\{\mathbb{f}\left( \mathcal{C}^{l-1}_{2fwl}(v_{1},v_{2}),\mathcal{C}^{l-1}_{2fwl}(v_{1},w), \mathcal{C}^{l-1}_{2fwl}(w,v_{2})\right)|w\in V(G)\right\}\right).\]

It is easy to verify that the above equation is equivalent to the original one. This means that 2-FWL updates the color of tuple \((v_{1},v_{2})\) by aggregating different tuples of \(((v_{1},v_{2}),(v_{1},w),(w,v_{2}))\), which can be viewed as aggregating information of 3-tuples \((v_{1},v_{2},w)\). For example, \(\text{HASH}(\mathcal{C}^{0}_{2fwl}(v_{1},v_{2}),\mathcal{C}^{0}_{2fwl}(v_{1},w),\mathcal{C}^{0}_{2fwl}(w,v_{2}))\) can fully recover the isomorphism type of tuple \((v_{1},v_{2},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 \(k\)-FWL.** Since aggregating \(k\)-tuple can boost the expressive power of \(k\)-FWL to be equivalent to (\(k\)+1)-WL, we may wonder, what if we continue to extend the size of the tuple?

Let \(Q^{F}_{\mathbf{w}}(\mathbf{v})\) denote a neighborhood tuple related to \(k\)-tuple \(\mathbf{v}\) and \(t\)-tuple \(\mathbf{w}\). The neighborhood tuple contains all possible results such that we sequentially select \(m\in[0,1,...,min(k,t)]\) elements from \(\mathbf{w}\) to replace \(m\) elements in \(\mathbf{v}\). Note that the selection and replacement procedure must follow a predefined order such that the result is invariant. For example, a possible \(Q^{F}_{(w_{1},w_{2})}(v_{1},v_{2})\) could be \(((v_{1},v_{2}),(v_{1},w_{1}),(v_{1},w_{2}),(w_{1},v_{2}),(w_{2},v_{2}),(w_{1},w_{2}))\), and the procedure of the construction is shown in Figure 1. We leave further discussion of the neighborhood tuple in Appendix A. By default, we adopt the above \(Q^{F}_{\mathbf{w}}(\mathbf{v})\) definition in the rest of the paper if \(k=t=2\). Then, we introduce \((k,t)\)-**FWL**, which extends \(k\)-FWL by extending the tuple size in the update function. Let \(\mathcal{C}^{l}_{ktfwl}(\mathbf{v})\) be the color of tuple \(\mathbf{v}\) at iteration \(l\) for \((k,t)\)-FWL, the update function of \((k,t)\)-FWL is:

\[(k,t)\text{-FWL:}\quad\mathcal{C}^{l}_{ktfwl}(\mathbf{v})=\text{HASH}( \mathcal{C}^{l-1}_{ktfwl}(\mathbf{v}),\mathbb{f}\left(\mathcal{C}^{l-1}_{ktfwl }(\mathbf{u})|\mathbf{u}\in Q^{F}_{\mathbf{w}}(\mathbf{v})\right)|\mathbf{w} \in V^{t}(G)\backslash\mathbb{f}_{t}), \tag{6}\]

where \(\{\!\{\cdot\}\!\}_{k}\) is hierarchical multiset over \(k\)-tuples such that elements in the set are grouped hierarchically given the order of the tuple. For example, \(\{\!\{(v_{1},v_{2})|(v_{1},v_{2})\in V^{2}(G)\}\!\}_{2}=\{\!\{\!\{(v_{1},v_{2})| v_{1}\in V(G)\}\!\}\!\}_{2}=\{\!\{\!\{(v_{1},v_{2})|v_{1}\in V(G)\}\!\}\!\}_{1}\). It is easy to see \((k,1)\)-FWL is equivalent to \(k\)-FWL under our definition of \(Q^{F}_{\mathbf{w}}(\mathbf{v})\). Further, as we only need to maintain representations of all \(k\)-tuples. \((k,t)\)-FWL has a fixed space complexity of \(O(n^{k})\). Here we show the expressive power of \((k,t)\)-FWL.

**Proposition 3.1**.: _For \(k\geq 2\) and \(t\geq 1\), if \(t\geq n-k\), \((k,t)\)-FWL can solve the graph isomorphism problems with the size of the graph less than or equal to \(n\)._

**Theorem 3.2**.: _For \(k\geq 2\), \(t\geq 1\), \((k,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\geq 2\), \(t\geq 1\), \((k,t+1)\)-FWL is strictly more powerful than \((k,t)\)-FWL; \((k+1,t)\)-FWL is strictly more powerful than \((k,t)\)-FWL._

We leave all formal proofs in Appendix B. Briefly speaking, even if we fix the size of \(k\), \((k,t)\)-FWL can still construct an expressive hierarchy by varying \(t\). Further, if \(t\) is large enough, \((k,t)\)-FWL can actually enumerate all possible combinations of tuples with the size of the graph, and thus

Figure 1: Illustration of the construction of neighborhood tuple \(Q^{F}_{(w_{1},w_{2})}(v_{1},v_{2})\) in \((2,2)\)-FWL. We sequentially select 0, 1, 2 elements from \((w_{1},w_{2})\) to replace 0, 1, 2 elements in \((v_{1},v_{2})\), resulting in three sub-tuple of length 1, 4, 1, respectively. The final neighborhood tuple is the concatenation of three sub-tuples. We can easily recover high-order graph structures from constructed neighborhood tuple.
equivalent to the relational pooling on graph [15]. It is worth noting that the size of \(Q_{\mathbf{w}}^{F}(\mathbf{v})\) will grow exponentially with an increase in the size of \(t\). However, the key contribution of \((k,t)\)-FWL is that even when \(k=2\), \((k,t)\)-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 \((k,t)\)-FWL is also different from subgraph GNNs such as \(k,l\)-WL [16] and \(l\)-OSAN [17], where \(l\)-tuples are labeled independently to enable learning \(k\)-tuple representations in all \(l\)-tuples' subgraphs, resulting in \(O(n^{k+l})\) space complexity.

### Rethinking and extending the aggregation scope of \(k\)-FWL

Another problem of \(k\)-FWL is its limited design space, as the only adjustable hyperparameter is \(k\). It is well known that there is a huge gap in expressive power even if we increase from \(k\) to \(k+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; 19; 20]. Moreover, increasing the expressive power does not always bring better performance when designing the corresponding neural version as it quickly leads to overfitting [11; 6; 9]. 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 \(|V(G)|\) global neighbors to update the color of each tuple \(\mathbf{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 \(\mathbf{v}\) in graph \(G\), we define equivariant set \(ES(\mathbf{v})\) to be the neighbors set of tuple \(\mathbf{v}\) and propose \(k\)**-FWL+**. An equivariant set \(ES(\mathbf{v})\) is a set of nodes related to \(\mathbf{v}\) and equivariant given the permutation \(g\in S_{n}\). That is, \(\forall w\in ES(\mathbf{v})\) in graph \(G\) implies \(g(w)\in ES(g\cdot\mathbf{v})\) in graph \(g\cdot G\). Some nature equivariant sets \(ES(v)\) including \(V(G)\), \(\mathcal{N}_{k}(v)\), and \(Q_{k}(v)\), etc. Let \(\mathcal{C}^{l}_{kfwl+}(\mathbf{v})\) be the color of tuple \(\mathbf{v}\) at iteration \(l\) for \(k\)-FWL+, we have:

\[k\text{-FWL+:}\quad\mathcal{C}^{l}_{kfwl+}(\mathbf{v})=\text{HASH}(\mathcal{ C}^{l-1}_{kfwl+}(\mathbf{v}),\complement\left(\mathcal{C}^{l-1}_{kfwl+}( \mathbf{u})|\mathbf{u}\in Q^{F}_{w}(\mathbf{v})\right)|w\in ES(\mathbf{v}) \complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right) \complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right) \complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left( \mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v} \right)\complement\left(\mathbf{v}\right)\complement\left(\mathbf{v}\right)\complement \left(\
### Gallery of \((k,t)\)-FWL+ instances

In this section, we provide some practical designs of \(ES^{t}(\mathbf{v})\) 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)\)-FWL+ as \((k,t)\)-FWL+ also includes the original \(k\)-FWL. We specify that \(k\)-tuple \(\mathbf{v}=(v_{1},v_{2},\ldots,v_{k})\) to avoid any confusion.

**Proposition 3.4**.: _Let \(t=1\), \(k=2\), and \(ES(\mathbf{v})=\mathcal{N}_{1}(v_{1})\cup\mathcal{N}_{1}(v_{2})\), the corresponding \((k,t)\)-FWL+ instance is equivalent to SLFWL(2) [12] and strictly more powerful than any existing node-based subgraph GNNs._

**Proposition 3.5**.: _Let \(t=1\), \(k=k\), and \(ES(\mathbf{v})=\bigcup_{i=1}^{k}Q_{1}(v_{i})\), the corresponding \((k,t)\)-FWL+ instance is more powerful than \(\delta\)-k-LWL [8]._

**Proposition 3.6**.: _Let \(t=2\), \(k=2\), and \(ES^{2}(\mathbf{v})=(Q_{1}(v_{1})\cap Q_{1}(v_{2}))\times(Q_{1}(v_{1})\cap Q_{ 1}(v_{2}))\), the corresponding \((k,t)\)-FWL+ instance is more powerful than GraphSNN [21]._

**Proposition 3.7**.: _Let \(t=2\), \(k=2\), and \(ES^{2}(\mathbf{v})=Q_{1}(v_{2})\times Q_{1}(v_{1})\), the corresponding \((k,t)\)-FWL+ instance is more powerful than edge-based subgraph GNNs like \(\text{I}^{2}\)-GNN [19]._

**Proposition 3.8**.: _Let \(t=1\), \(k=2\), and \(ES(\mathbf{v})=Q_{\text{SPD}(v_{1},v_{2})}(v_{1})\cap Q_{1}(v_{2})\), 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.9**.: _Let \(t=2\), \(k=2\), and \(ES^{2}(\mathbf{v})=Q_{1}(v_{2})\times\mathcal{SP}(v_{1},v_{2})\), the corresponding \((k,t)\)-FWL+ is more powerful than GDGNN [23]._

We leave all formal proofs in Appendix C. Significantly, Proposition 3.7 indicates that \((k,t)\)-FWL+ can be more powerful than edge-based subgraph GNNs but only require \(O(n^{2})\) space, strictly lower than \(O(nm)\) 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,t)\)-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,t)\)-FWL+ instances and corresponding existing works based on MPNNs and leave the detailed proof in our future works.

## 4 Neighborhood\({}^{2}\)-GNN: a practical and powerful \((2,2)\)-FWL+ implementation

Due to the extremely flexible and broad design space of \((k,t)\)-FWL+, it is hard to evaluate all possible instances. Therefore, we focus on a particular instance that is both theoretically and practically sound.

### Neighborhood\({}^{2}\)-Fwl

In this section, we propose a practical and powerful implementation of \((2,2)\)-FWL+ named Neighborhood\({}^{2}\)-FWL (N\({}^{2}\)-FWL). Let \(\mathcal{C}_{n^{2}fwl}^{l}(\mathbf{v})\) denote the color of tuple \(\mathbf{v}\) at iteration \(l\) for N\({}^{2}\)-FWL, the color is updated by:

\[\text{N}^{2}\text{-FWL:}\quad\mathcal{C}_{n^{2}fwl}^{l}(\mathbf{v})=\text{ HASH}(\mathcal{C}_{n^{2}fwl}^{l-1}(\mathbf{v}),\big{\{}\!\big{\}}\Big{(} \mathcal{C}_{n^{2}fwl}^{l-1}(\mathbf{u})|\mathbf{u}\in Q_{\mathbf{w}}^{F}( \mathbf{v})\Big{)}\,|\mathbf{w}\in N^{2}(\mathbf{v})\big{\}}_{2}), \tag{9}\]

where \(N^{2}(\mathbf{v})=(\mathcal{N}_{1}(v_{2})\times\mathcal{N}_{1}(v_{1}))\cap( \mathcal{N}_{h}(v_{1})\cap\mathcal{N}_{h}(v_{2}))^{2}\) and \(h\) is the number of hop. Briefly speaking, N\({}^{2}\)-FWL considers neighbors of both node \(v_{1}\) and \(v_{2}\) within the overlapping \(h\)-hop subgraph between \(v_{1}\) and \(v_{2}\). In the following, we show the expressive power and counting power of N\({}^{2}\)-FWL.

**Theorem 4.1**.: _Given \(h\) is large enough, N\({}^{2}\)-FWL is more powerful than SLFWL(2) [12] and edge-based subgraph GNNs._

**Corollary 4.2**.: _N\({}^{2}\)-FWL is strictly more powerful than all existing node-based subgraph GNNs and no less powerful than 3-WL._

**Theorem 4.3**.: _N\({}^{2}\)-FWL can count up to (1) 6-cycles; (2) all connected graphlets with size 4; (3) 4-paths at node level._
### Neighborhood\({}^{2}\)-Gnn

In this section, we provide a neural version of N\({}^{2}\)-FWL called Neighborhood\({}^{2}\)-GNN (N\({}^{2}\)-GNN). Let \(h_{\mathbf{v}}^{l}\) be the output of N\({}^{2}\)-GNN of tuple \(\mathbf{v}\) at layer \(l\) and \(h_{\mathbf{v}}^{0}\) encode the isomorphism type of tuple \(\mathbf{v}\). At the \(l\)-th layer, the representation of each tuple is updated by:

\[h_{\mathbf{v}}^{l}=\mathbf{U}^{l}(h_{\mathbf{v}}^{l-1},\{\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
[43] computes graph polynomial features and injects them into PPGN to achieve greater expressive power than 3-WL within \(O(n^{2})\) space. Although feature-based methods are highly efficient, they often suffer from overfitting in 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 N\({}^{2}\)-GNN. The details of all experiments can be found in Appendix E. We include additional experimental results and ablation studies in Appendix F. Our code is available at [https://github.com/JiaruiFeng/N2GNN](https://github.com/JiaruiFeng/N2GNN) for reproducing all results.

### Expressive power

SR25 [44], which contains 15 non-isomorphic strongly regular graphs, each has 25 nodes. Even 3-WL is unable to distinguish between these graphs.

**Models**. As we are solely evaluating the expressive power of N\({}^{2}\)-GNN, we only report results for N\({}^{2}\)-GNN. We vary the hop \(h\) for different datasets and report the best result.

**Results**. We report results in Table 1. For EXP and CSL, we report the average accuracy for 10-time cross-validation; For SR25, we report single-time accuracy. We can see N\({}^{2}\)-GNN achieves perfect results on all three datasets, empirically verifying its expressive power. Notably, N\({}^{2}\)-GNN is able to distinguish strongly regular graphs that even 3-WL are unable to differentiate. This empirically verified Corollary 4.2. Despite this improved performance, N\({}^{2}\)-GNN only requires at most \(O(n^{2})\) space complexity, which is less than 3-WL. This further demonstrates the superiority of N\({}^{2}\)-GNN.

### Substructure counting

**Datasets**. To verify the substructure counting power of N\({}^{2}\)-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-triangle, chordal cycles, 4-cliques, 4-paths, triangle-rectangle, 3-cycles, 4-cycles, 5-cycles, and 6-cycles as target substructures.

**Models**. We compare N\({}^{2}\)-GNN with the following baselines: Identity-aware GNN (ID-GNN) [28], Nested GNN (NGNN) [24], GNN-AK+ [25], PPGN [9], I\({}^{2}\)-GNN [19]. Results for all baselines are reported from [19].

**Results**. We report the results for counting substructures in Table 2. 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 of successful counting, the same as in [19]. We can see that N\({}^{2}\)-GNN achieves MAE less than 0.01 among all different substructures/cycles, which empirically verified

\begin{table}
\begin{tabular}{l|c c c} \hline Datasets & EXP & CSL & SR25 \\ \hline N\({}^{2}\)-GNN & 100 & 100 & 100 \\ \hline \end{tabular}
\end{table}
Table 1: Expressive power verification (Accuracy).

\begin{table}
\begin{tabular}{l|c c c c|c} \hline Target & ID-GNN [28] & NGNN [24] & GIN-AK+ [25] & PPGN [9] & I\({}^{2}\)-GNN [19] & N\({}^{2}\)-GNN \\ \hline Tailed Triangle & 0.1053 & 0.1044 & 0.0043 & 0.0026 & 0.0011 & 0.0033 \\ Chordal Cycle & 0.0454 & 0.0392 & 0.0112 & 0.0015 & 0.0010 & 0.0024 \\
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.0038 \\ 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.0004 \\
4-Cycles & 0.0022 & 0.0013 & 0.0041 & 0.0009 & 0.0016 & 0.0031 \\
5-Cycles & 0.0490 & 0.0402 & 0.0133 & 0.0036 & 0.0028 & 0.0043 \\
6-Cycles & 0.0495 & 0.0439 & 0.0238 & 0.0071 & 0.0082 & 0.0077 \\ \hline \end{tabular}
\end{table}
Table 2: Evaluation on Counting Substructures (norm MAE), cells with MAE less than 0.01 are colored.
Theorem 4.3. Specifically, N\({}^{2}\)-GNN achieves the best result on 4-path counting and comparable performance to I\({}^{2}\)-GNN on most substructures. Moreover, N\({}^{2}\)-GNN can count 4-clique extremely well, which is theoretically and empirically infeasible for 3-WL [42] and PPGN [\(\diamond\)].

### Molecular properties prediction

**Datasets**. To evaluate the performance of N\({}^{2}\)-GNN on real-world tasks, we select two popular molecular graphs datasets: QM9 [45; 46] and ZINC [47]. QM9 dataset contains over 130K molecules with 12 different molecular properties as the target regression task. The dataset is split into training, validation, and test sets with a ratio of 0.8/0.1/0.1. ZINC dataset has two variants: ZINC-subset (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.

**Models**. For QM9, we report baseline results of DTNN and MPNN from [45]. We further adopt PPGN [9], NGNNs [24], KP-GIN\(\prime\)[22], I\({}^{2}\)-GNN [19]. We report results of PPGN, NGNN, and KP-GIN\(\prime\) from [22] and results of I\({}^{2}\)-GNN from [19]. For ZINC, the baseline including CIN [48], \(\delta\)-2-GNN [8], KC-SetGNN [10], PPGN [9], Graphmer-GD [41], GPS [49], Specformer [50], NGNN [24], GNN-AK-ctx [25], ESAN [34], SUN [27], KP-GIN\(\prime\)[22], I\({}^{2}\)-GNN [19], SSWL+ [12]. We report results of all baselines from [12; 22; 43; 10; 49; 50; 19].

**Results**. For QM9, we report the single-time final test MAE in Table 3. We can see that N\({}^{2}\)-GNN outperforms all other methods in almost all targets with a large margin. Particularly, we achieve \(63.8\%\), \(54.7\%\), \(71.6\%\), and \(63.2\%\) improvement comparing to the second-best results on target \(U_{0}\), \(U\), \(H\), and \(G\) respectively. For ZINC-Subset and ZINC-Full, we report the average test MAE and standard deviation of 10 runs with different random seeds in Table 4. We can see N\({}^{2}\)-GNN still surpass all previous methods and achieve \(10.6\%\) and \(40.9\%\) improvement over the second-best methods. All these results demonstrate the superiority of N\({}^{2}\)-GNN on real-world tasks.

\begin{table}
\begin{tabular}{l|c|c c c|c} \hline \multirow{2}{*}{Model} & \multirow{2}{*}{\# Param} & \multicolumn{2}{c}{ZINC-Subset} & \multicolumn{2}{c}{ZINC-Full} \\ \cline{3-6}  & & \multicolumn{2}{c}{Test MAE} & \multicolumn{2}{c}{Test MAE} \\ \hline CIN [48] & \(\sim\)100k & 0.079 \(\pm\) 0.006 & 0.022 \(\pm\) 0.002 \\ \hline \(\delta\)-\(2\)-GNN [8] & - & - & 0.042 \(\pm\) 0.003 \\ KC-SetGNN [10] & - & 0.075 \(\pm\) 0.003 & - \\ PPGN [\(\diamond\)] & - & 0.079 \(\pm\) 0.005 & 0.022 \(\pm\) 0.003 \\ \hline Graphmer-GD [41] & 503k & 0.081 \(\pm\) 0.009 & 0.025 \(\pm\) 0.004 \\ GPS [49] & 424k & 0.070 \(\pm\) 0.004 & - \\ Specformer [50] & \(\sim\)500k & 0.066 \(\pm\) 0.003 & - \\ \hline NGNN [24] & \(\sim\)500k & 0.111 \(\pm\) 0.003 & 0.029 \(\pm\) 0.001 \\ GNN-AK-ctx [25] & \(\sim\)500k & 0.093 \(\pm\) 0.002 & - \\ ESAN [34] & 446k & 0.097 \(\pm\) 0.006 & 0.025 \(\pm\) 0.003 \\ SUN [27] & 526k & 0.083 \(\pm\) 0.003 & 0.024 \(\pm\) 0.003 \\ KP-GIN [22] & 489k & 0.093 \(\pm\) 0.007 & - \\ I\({}^{2}\)-GNN [19] & - & 0.083 \(\pm\) 0.001 & 0.023 \(\pm\) 0.001 \\ SSWL+ [12] & 387k & 0.070 \(\pm\) 0.005 & 0.022 \(\pm\) 0.002 \\ \hline N\({}^{2}\)-GNN & 306k & **0.059 \(\pm\) 0.002** & **0.013 \(\pm\) 0.0005** \\ \hline \end{tabular}
\end{table}
Table 4: MAE results on ZINC (smaller the better).

\begin{table}
\begin{tabular}{l|c c c c c|c|c} \hline Target & DTNN [45] & MPNN [45] & PPGN [9] & NGNN [24] & KP-GIN\(\prime\)[22] & I\({}^{2}\)-GNN [19] & N\({}^{2}\)-GNN \\ \hline \(\mu\) & 0.244 & 0.358 & **0.231** & 0.433 & 0.358 & 0.428 & 0.333 \\ \(\alpha\) & 0.95 & 0.89 & 0.382 & 0.265 & 0.233 & 0.230 & **0.193** \\ \(\varepsilon_{\text{HOMO}}\) & 0.00388 & 0.00541 & 0.00276 & 0.00279 & 0.00240 & 0.00261 & **0.00217** \\ \(\varepsilon_{\text{LUMO}}\) & 0.00512 & 0.00623 & 0.00287 & 0.00276 & 0.00236 & 0.00267 & **0.00210** \\ \(\Delta_{E}\) & 0.0112 & 0.0066 & 0.00406 & 0.00390 & 0.00333 & 0.00380 & **0.00304** \\ \(\langle R^{2}\rangle\) & 17.0 & 28.5 & 16.7 & 20.1 & 16.51 & 18.64 & **14.47** \\ ZPVE & 0.00172 & 0.00216 & 0.00064 & 0.00015 & 0.00017 & 0.00014 & **0.00013** \\ \(U_{0}\) & 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** \\ \(C_{v}\) & 0.27 & 0.42 & 0.184 & 0.0811 & 0.0869 & **0.0730** & 0.0760 \\ \hline \end{tabular}
\end{table}
Table 3: MAE results on QM9 (smaller the better).
Conclusion

In this work, we propose \((k,t)\)-FWL+, a flexible and powerful extension of \(k\)-FWL. First, \((k,t)\)-FWL+ expands the tuple aggregation style in \(k\)-FWL. We theoretically prove that even with a space complexity of \(O(n^{2})\), \((k,t)\)-FWL+ can still construct an expressiveness hierarchy up to solving the graph isomorphism problem. Second, \((k,t)\)-FWL+ extends the global neighborhood definition in \(k\)-FWL to any equivariant set, which enable a finer-grained design space. We show that the \((k,t)\)-FWL+ framework can implement many existing powerful GNN models with matching expressiveness. We further implement an instance named N\({}^{2}\)-GNN which is both practically powerful and theoretically expressive. Theoretically, it partially outperforms 3-WL but only requires \(O(n^{2})\) space. Empirically, it achieves new SOTA on both ZINC-Subset and ZINC-Full. However, the practical complexity of N\({}^{2}\)-GNN can still be unbearable especially for dense graphs. Nevertheless, there still exists a vast unexplored landscape within \((k,t)\)-FWL+ that is worth further investigation. We envision \((k,t)\)-FWL+ can serve as a promising general framework for designing highly effective GNNs tailored to real-world problems.
