Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power
Authors: Junru Zhou
Jiarui Feng
Xiyuan Wang
Muhan Zhang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Cycle counting
graph neural networks

Abstract: The ability of graph neural networks (GNNs) to count certain graph substructures, especially cycles, is important for the success of GNNs on a wide range of tasks. It has been recently used as a popular metric for evaluating the expressive power of GNNs. Many of the proposed GNN models with provable cycle counting power are based on subgraph GNNs, i.e., extracting a bag of subgraphs from the input graph, generating representations for each subgraph, and using them to augment the representation of the input graph. However, those methods require heavy preprocessing, and suffer from high time and memory costs. In this paper, we overcome the aforementioned limitations of subgraph GNNs by proposing a novel class of GNNs---$d$-Distance-Restricted FWL(2) GNNs, or $d$-DRFWL(2) GNNs, based on the well-known FWL(2) algorithm. As a heuristic method for graph isomorphism testing, FWL(2) colors all node pairs in a graph and performs message passing among those node pairs. In order to balance the expressive power and complexity, $d$-DRFWL(2) GNNs simplify FWL(2) by restricting the range of message passing to node pairs whose mutual distances are at most $d$. This way, $d$-DRFWL(2) GNNs exploit graph sparsity while avoiding the expensive subgraph extraction operations in subgraph GNNs, making both the time and space complexity lower. We theoretically investigate both the discriminative power and the cycle counting power of $d$-DRFWL(2) GNNs. Our most important finding is that $d$-DRFWL(2) GNNs have provably strong cycle counting power even with $d=2$: they can count all 3, 4, 5, 6-cycles. Since 6-cycles (e.g., benzene rings) are ubiquitous in organic molecules, being able to detect and count them is crucial for achieving robust and generalizable performance on molecular tasks. Experiments on both synthetic datasets and molecular datasets verify our theory. To the best of our knowledge, 2-DRFWL(2) GNN is the most efficient GNN model to date (both theoretically and empirically) that can count up to 6-cycles.

Distance-Restrictee Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power
Junru Zhou'
Jiarui Feng² Xiyuan Wang' Muhan Zhang' Institute for Artificial Intelligence, Peking University 2 Department of CSE, Washington University in St. Louis zml mel112262stu....mm pku. edu.. en, feng- jiarui@wuse @wsstl. edu, (wangxiyuan, (rangxiyuannmuuan)a munhan)@pku edu. cn
Abstract
The ability of graph neural networks (GNNs) to count certain graph substructures, especially cycles, is important for the success of GNNs on wide range of tasks. It has been recently used as a popular metric for evaluating the expressive power of GNNs. Many of the proposed GNN models with provable cycle counting power are based on subgraph GNNs, i.e., extracting bag of subgraphs from the input graph, generating representations for each subgraph, and using them augment the representation of the input graph. However, those methods require heavy preprocessing, and suffer from high time and memory costs. this paper, we overcome the aforementioned limitations of subgraph GNNs by proposing a novel class of GNNs D--Diitance-Restricttt FWI.(2) GNNs, d-DRFWI((2) GNNs, based the well-known FWL(2) algorithm. As heuristic method for graph isomorphism testing, FWL(2) colors node pairs in a graph and performs message passing among those node pairs. In order to balance the expressive power and complexity, d-DRFWL((2) GNNs simplify FWL(2) by restricting the range of message passing node pairs whose mutual distances way, d-DRFWL((2) GNNs exploit graph sparsity while avoiding the expensive subgraph extraction operations in subgraph GNNs, making both the time and space complexity lower. We theoretically investigate both the discriminative power and the cycle counting power of d-DRFWI((2) GNNs. Our most important finding is that d-DRFWL(2) GNNs have provably strong cycle counting power even with d = 2: they can count all 3, 4, 6-cycles. Since 6-cycles (e.g., benzene rings) are ubiquitous in organic molecules, being able to detect and count them is crucial for achieving robust and generalizable performance on molecular tasks. Experiments on both synthetic datasets and molecular datasets verify our theory. To the best of our knowledge, 2-DRFWL(2) GNN the most efficient GNN model to date (both theoretically and empirically) that can count to 6-cycles.
at most d. This
1 Introduction
Graphs are important data structures suitable for representing relational or structural data. As
powerful tool to learn node-level. link-level graph-level representations for graph-structured data, graph neural networks (GNNs) have achieved remarkable successes on a wide range of tasks [54] 61). Among the various GNN models, Message Passing Neural Networks (MPNNs) [27 36 50 55
widely adopted class of GNNs. However, the expressive power of MPNNs has been shown to be bounded by the Weisfeiler-Leman test [55]. More importantly, MPNNs even fail detect
some simple substructures (e.g., 3, 4-cycles) 33 thus losing great structural information in graphs.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The weak expressive power of MPNNS has aroused a search for more powerful GNN models. To evaluate the expressive power of these GNN models, there are usually two perspectives. One is to characterize their discriminative power, i.e., the ability to distinguish between non-isomorphic graphs. is shown [14] that an equivalence exists between distinguishing all non-isomorphic graph pairs and approximating any intmuutttionnnnvarinn functions on graphs. Although the discriminative power partially reveals the function approximation ability of a GNN model, it fails to tell what specific functions model is able to approximate. Another perspective is to directly characterize what specific function classes a model can approximate. In particular, we can study the expressive power of a GNN model by asking what graph substructures it can count. This perspective is often more practical since the task of counting substructures (especially cycles) is closely related to a variety of domains such as chemistry 18 351, biology 337. and social network analysis (4).
Despite the importance of counting cycles, the task gets increasingly difficult as the length of cycle increases [2. To have an intuitive understanding of this difficulty, we first discuss why MPNNs fail to count any cycles. The reason is clear: MPNNS only keep track of the rooted subtree around each node [55] and without node identity, any neighboring node of u has no idea which of its neighbors are also neighbors of u. Therefore, MPNNs cannot count even the simplest 3-cycles. In contrast, the 2-dimensional Folklore Weisfeiler-Leman, or FWL(2) test 12], uses 2-tuples of nodes instead of nodes as the basic units for message passing, and thus natually encodes closed walks. For example, when a 2-tuple (u, v) receives messages from 2-tuples (w, b) and (u, w) in FWL((). (u, v) gets aware of the walk u + w + V - u, whose length is d(u, w) + d(w, v) + d(u, v) =: As long the intermediate nodes do not overlap, we immediately get an l-cycle passing both and v. In fact, FWL(2) can provably count up to 7-cycles 55] 25
However, F2 has a space and time complexity of O(n²) and O(n²), which makes it impractical for large graphs and limits its real-world applications. Inspired by the above discussion, we naturally raise question: to what extent can we retain the cycle counting power of FWL(2) while reducing the time and space complexity? Answering this question requires another observation: cycle counting tasks are intrinsically local. For example, the number of 6-cycles that pass given node has nothing to do with the nodes that have a moortest-path distance > 4 to u. Therefore, if we only record the embeddings of node pairs with mutual distance & d in FWL(2), where d is a fixed positive integer, then the ability of FWL(2) to count substructures with diameter & d should be retained. Moreover, given that most real-world graphs are sufficiently sparse, this simplified algorithm runs with complexities much lower than FWL(2), since we only need to store and update a small portion of the n² embeddings for all 2-tuples We call this simplified version d- d-Distance-Be Restrrcced FWL(2). or d- d-DRFWL((2, reflecting that only 2-tuples with restricted distances get updated.
Main contributions. Our main contributions are summarized as follows:
We propose d-DRFWL(() tests as well as their neural versions, d-DRFWL(2) GNNs. We study how the hyperparameter d affects the discriminative power of d-DRFWL(()) and show that a strict expressiveness hierarchy exists for d-DRFWL(2) GNNs with increasing d, both theoretically and experimentally.
2. We study the cycle counting power of d-DRFWL(2) GNNs. Our major results include:
2-DRFWL(2) GNNs can already count up to 6-cycles, covering common structures like benzene rings in organic chemistry. The time and space complexities of 2 2-DRFWL(2) are O(n deg") and O(n deg") respectively, making it the most efficient one to date among other models with 6-cycle counting power such as I2-GNN
With > 3, d-DRFWL(2) GNNs can count up to 7-cycles, fully retaining the cycle counting power of F2L(2) but with complexities strictly lower than FWL(2). This finding also confirms the existence of GNNs with the same cycle counting power as FWL(2), but strictly weaker discriminative power.
3. We compare the performance and empirical efficiency of d-DRFWL(() GNNs (especially for d = 2) with other state-of-the-aa GNNs on both synthetic and real-world datasets. The results verify our theory on the counting power of d-DRFWL((2 GNNs. Additionally, for the case of d = 2, the amount of GPU memory required for training 2- 2-DRFWL((2) GNNs is greatly reduced compared with subgraph GNNs like ID-GNN [57), NGNN (59] and 12- (3): the preprocessing time and training time of 2-DRFWL(2) GNNs are also much less than I-NNN

---

2 Preliminaries
2.1 Notations
For a simple, undirected graph G. we use Va and &G to denote its node set and edge set respectively. For every node E Vg. we define its k-th hop neighbors as NN(()) = {u E Ve d(u, v) k]. where d(u, v) is the shortest-path distance between nodes and We further introduce the symbols Neg(v)= = Ni(e) and ((v) = (N)).. For any n E N, we denote [n]] (I.
An E-cycle (L 3 3) in the (simple, undirected) graph G is a sequence of l edges (21, (22, vah..... fur, said to pass a node v if v is among the nodes {u; E [(]]. An E-path is a sequence of edges {uz, 22), foz, ua)...., fog 2141]
Eg with v; * v for any o j and i,j [e]. The E-cycle is
Eg with v & by for any + j and i, E [e 11, and it is said to start at node in and end at node V441. An l-walk from U1 to ue+1 is sequence of edges (2), {o2, (a), vah..... {uz, 1 E &a but the nodes vI, U2,.... Ug+1 can coincide. An E-clique is i nodes 01,..., Ue such that ey) E &g for all i + and i, E [e].
Let G be the set of all simple, undirected graphs. If S is graph substructure on G, and G E G is graph, we use C(S, G) to denote the number of inequivalent substructures S that occur as subgraphs of G. Similarly, if u is node of G. we use C(S, G) to denote the number of inequivalent substructures that pass node u and occur as subgraphs G.
Following 15 33 we give the definition of whether function class F on graphs can count certain substructure S.
Definition 2.1 (Graph-level count). Let Fgaaph be a function class on G. i.e., fgraph : G + R
for all fgraph E F ggraph- F ggraph is said to be able to graph-level count a substructure S on G if for vG1, G2 E 9 such that C1) * C(S, G2), there exists fgraph E Fgraph such that ggraph (G1) # fgraph (G2).
Definition 2.2 (Node-level count). Let G = ((G,u) : G G,u VaJ. Let Fnode be function class G V, i.e., Snnde G V R for all Snode Frade- Fnode is said to be able to node-level count a substructure S on G if for v(1,, U1), (),, U2) E G x V such that C(S, u1, G1) # C(S, u2 G2). there exists fnode E Fnode such that fnode (G1, u1) # Fnode(G2 u2).
Notice that CSS, G) can be calculated by Enery C(S, G) divided by factor only depending on S, for any given substructure S. (For example, for triangles the factor is 3.) Therefore, counting substructure at node level is harder than counting at graph level.
2.2 FWL(k) graph isomorphism tests
WL(1) test. The 1 1-dimensional Weisfeiler-Leman test, or WL(1) test, is heuristic algorithm for the graph isomorphism problem [52]. For a graph G, the WL(1) test iteratively assigns a color W(v) (v) to every node v E Va. At the 0-th iteration, the color W (v) is identical for every node v. At the (-th iteration with / >> 1,
(w) (ASH (V) (WW(L-)))) u N(O)B))
(I)
where (ASH() and ( are injective hashing functions, and {-} means a multiset (set with potentially identical elements). The algorithm stops when the node colors become stable, i.e., Ve, Va, ((++)(()) w(++)((v) < (v) (u). We denote the stable coloring of node (o): then the representation for graph G is
W(G) READOUT (qW()(()) : Vell).
(2)
where READOUT an arbitrary injective multiset function.
FWL(K) tests. For k > 2, the k-dimensional Folklore Weisfeiler- tests, or FWL(k) tests.
define a hierarchy of algorithms for graph isomorphism testing, as described in [12 32
42
For
graph G, the FWL(K) test assigns color W(v) for every k-luple (Vi...., vk VA At
the O-th iteration, the color (v) is the atomic type of denoted atp(v). If we denote the
3

---

subgraphs of G induced by v and v' as G(v) and G(v') respectively. then the function atp(-) can be any function on Ve that satisfies the following condition: atp(v) = atp(v') iff the mapping ey v/, i E [k] (i.e., the mapping that maps each is to its corresponding u/y for [k) induces an isomorphism from G(v) to G(v').
At the f-th iteration with > FWL(k) updates the color of v E Vig as
(v) (A)H (v) ((sift(W((t)) v, : E vVaB))
(3)
where si v, w) is defined
sift v, w) = ( [(v[2 + wi).... J(v(k: - wi))
(4)
Here use vij + w| to denote (v), 1 we U/+1 :....... uk) for j E [A]] and E Va.
(ASH and POOL are again injective hashing functions. The algorithm stops when all k-tuples receive stable colorings. The stable coloring of V is denoted (v)) We then calculate the representation for graph G as
W(G) READOUT (M) vgD)
(5)
where READOUT is an arbitrary injective multiset function.
3 d-Distance-Restrictee FWL(2) GNNs
In this section, propose the d-Distance Restricted FWL(2) tests/GNNs. They use 2-tuples like FWL(2), but restrict the distance between nodes in each 2-tuple to be & d, which effectively reduces the number of 2-tuples to store and aggregate while still retaining great cycle counting power.
3.1 d-DRFWL(2) tests
We call a 2-tuple (u, v) E V& distance-k tuple if the shortest- patt distance between u and v l in the following. d-Distance Restricted FWL(2) tests, or d-DRFWL(2) tests, assign a color W (u, v) for every distance-k tuple (u, v) with 0 & & d. Initially, the color W (u, v) only depends d(u, v). For the 1-th iteration with > 1, d-DRFWI.(2) updates the colors using the following rule,
For each k 10,1,...54
(0 (u.v) HASH! (wit-n v), (M (u, (u. D if d(u v) = k, (6)
where HASH(") is an injective hashing function for distance k and iteration I, and M/( (u, is k
defined as
M (u,v) = PPOLL k(t))
(H (W((e)))) v), w(t w)) : w E Ni((u) N(( (7)
The symbol (Mr)) (u, w)
stands for (Mbb)) (1, v), b(t) (u, .).... Mk10 (u, v),...
ogiiged
Mh(()) (u, v)). Each of the POOL
k(t) with & i,j,k k & d an injective multiset hashing function. bi
Briefly speaking, the rules (6) and update the color of distance-k tuple (u, v) using colors of distance-i and distance-ji tuples.
When every distance-k tuple (u, v) with & k < d receives its stable coloring, denoted as w (u, v), the representation of G' is calculated
W(G) READOUT ((Wlo) (u, v): (w,w) E vg and 0 & d(u,v) < dz)
(8)

---

Figure I Iillustrates how 2-DRFWL(2) updates the color of a 2 tuple (u, v). Since only distance-k tuples with 0 & k & 2 are colored in 2-DRFWI((2) tests, there are 7 terms of the form (W(ww, v), (", w)) (with w E {u, v, U. 2, L, ()r contributing to the update of W(u, v). The nodes u, U, H. y, t, r are filled with different colors, according to their distances to u. and to For example, the violet node u has distance to u and distance to v, thus contributing to M (u, 2); the green nodes and y have distance 1 to either u or U, thus contributing to Mf (u, v). Analogously, nodes with red, blue, orange and pink colors contribute to M20 (u, v), Mf, v), M21 (u, v) and W222,, u), respectively. Finally, the uncolored nodes q and 8 do not contribute to the update of W(u, v), since they have distance 3 (which is greater than 2)
2
Figure 1: Neighbor aggregation in 2- DRFWL(() for 2-tuple (u, v).
From the figure, we can observe that by redefining neighbors and sparsifying 2-tuples of FWL(2), d-DRFWL(2) significantly reduces the complexity and focuses only on local structures, especially on sparse graphs.
Now we study the expressive power of d- d-DRFWL(2) tests by comparing them with the WL hierarchy, First, we can prove that d- d-DRFWL(2) tests strictly more powerful than WL(I), for every d. Theorem 3.1. In terms of the ability to distinguish between non-isomorphic graphs, the d-DRFWL(2) test is strictly more powerful than WL(1), I), for any d >
Next, we compare d-DRFWL(2) tests with FWL(2). Actually, since it is easy for the FWL(2) test to compute distance between every pair of nodes (we initialize W u) as 0, 1 and oc for u u,
v) E Eg and all other cases, and iteratively update W(u,0 v) with min W (u, v), min, { { (u, w)
(ww, H), the FWL((2) test can its update rule simulate 6 and 7 by applying different HASH &
(0) and POOL; k(t) functions to different (i,j, k) values. This implies that d-DRFWL(2) tests are at most as powerful as the FWL(2) test. Actually, this hierarchy in expressiveness is strict, due
to the following theorem.
Theorem 3.2. In terms of the ability to distinguish between non-isomorphic graphs, FWL(2) is strictly more powerful than d-DRFWL(2), any d 2 1. Moreover, (d + 1)-DRFWL(2) is strictly more powerful than d-DRFWL((2)
The proofs of all theorems within this section are included in Appendix B
3.2 d-DRFWL(2) GNNs
Based on the d-DRFWL(2) tests, we now propose d-DRFWL((2) GNNs. Let G be a graph which can have node features fo E R&r, Ve and (or) edge features Euv E Rde {u, v} E Eg. A d-DRFWL(2) GNN is defined as function of the form
f R oor-oo.
oT
(9)
The imput of f the initial labeling h 0 < d(u, v) & Each L, with t 1,2, .... T in 9 is
called d-DRFWL(() GNN layer, which transforms (t-1) into hao using rules
For each k- 0.1,..,,
For each (u,v) E V with d(w, u) = k, (1)
awv (gR(1)
(1(1-1), 11(1)1)))
(10)
Pigk
WENG(u))INN(o))
h (4)
(1)
(((tt))
(a
(1((()))
(11)
UEI
where (t) migk and ((t) are arbitrary learnable functions: ① denotes a permutation invariant aggregation
operator (e.g., sum, mean or max). (0O) and [II are simply counterparts of (7) and (6) with POOL k(t) and (ASH replaced with continuous functions. o,, t 1...., T 1 are entry-wise activation functions. R is permutation invariinn readout function, whose input is the multiset
5

---

(1e0 vu,v) E V and 0 & d(u,v) & dB. Finally, M is MLP that acts on the graph representation output by R.
We can prove that (i) the representation power of any d-DRFWL(2) GNN is upper-bounded by the d-DRFWL((2) test, and (ii) there exists a d-DRFWL(2) GNN instance that has equal representation power to the d-DRFWL(2) test. We leave the formal statement and proof to Appendix B
The cycle counting power of d-DRFWL(2) GNNs
By Theorem 3.2 the expressive power of d-DRFWI.(2) tests (or d-DRFWL(2) GNNs) strictly increases with d. However, the space and time complexities of d-DRFWWL(22 GNNs also increase with d. On one hand, since there are On deg") distance-k tuples in graph G, at least O(n deg space is necessary to store the representations for all distance-k tuples. For d-DRFWL(2) GNNs, this results in space complexity of On deg"). On the other hand, since there are most Oddeg"in(to)) nodes in (G) (&) vO i,j d, there are at most Oddeg") terms the RHS of TO Therefore, it takes Od deg") time to update single representation vector hav using (10) and This implies the time complexity of d-DRFWL(2) GNNs is O deg2d).
For scalability, d-DRFWL(2) GNNs with a relatively small value of d used in practice. But how to find the d value that best strikes balance between expressive power and efficiency? To answer this question, we need practical, quantitative metric of expressive power. In the following. we characterize the cycle counting power of d-DRFWL(()) GNNs. We find that 2-DRFWL(() GNNs are powerful enough node-level count up to 6-cycles, as well many other useful graph substructures. Since for d 2, the time and space complexities of d-DRFWL(2) GNNs are On deg*) and O(n deg²) respectively, our model is much more efficient than 12-GNN which requires On deg") ) time and O deg") space space to count up 6-cycles [33] Moreover, with d > 3. d-DRFWL(2) GNNs are able to node-level count up to 7-cycles, already matching the cycle counting power of FWL(2).
Before we present the theorems, need to give revised definitions of C(S, G) for some certain substructures S. This is because in those substructures all nodes structurally equal.
Our main results are stated in Theorems 4.3 4.8
Definition 4.1. is an Ê-path with é > 2, C(S, u, G) defined to be the number é-paths in G starting from node u.
Figure 2a Illustrates Definition 4.1 for the { = 4 case.
Definition 4.2. The substructures in Figures 2b 2c and 2d are called tailed triangles, chordal cycles and cettongle-eectanlle
respectively. If S is tailed triangle (or chordal cycle or riangle-rectangle C(S, u, G') is defined to be the number of tailed triangles (or chordal cycles or that occur as subgraphs of G and include node u at position shown in the figures.
11
(a) 4-path that starts node u
(b) A tailed triangle that passes node u
(c) chordal cycle that passes node u
(d)
that passes node u
Figure Illustrations of node-level counts of certain substructures.
Now we state our main theorems. In the following, the definition for "node-level counting" is the same Definition 2.2 but one should treat C(S, u, G)) differently (following Definitions 4. and when S is path, a tailed triangle, a chordal cycle, or triangle-rectangle. To define the output d- DRFWL(22 GNN on domain G x V. we denote
f(G, u) = (T)
E VG.
(12)

---

Le., we treat the embedding of (u, u) as the representation of node For I-DRFWL(2) GNNs, we have
Theorem 4.3. I-DRFWL(2) GNNs can node-level count 3-cycles, but cannot graph-level count any longer cycles.
For 2-DRFWL(2) GNNs, investigate not only their cycle counting power, but also their ability to count many other graph substructures. Our results include
Theorem 4.4. 2-DRFWL(2) GNNs can node-level count 2, 3. 4-paths.
Theorem 4.5. 2-DRFWL(2) GNNs can node-level count 5, 6-cycles.
Theorem 4.6. 2-DRFWL(2) GNNs can node-level count tailed triangles, chordal cycles and triangle- rectangles.
Theorem 4.7. 2-DRFWL(2) GNNs cannot graph-level count k-cycles with k 3 7 or k-cliques with k >> 4.
For d-DRFWL(2) GNNs with d 3, we have
Theorem 4.8. For any d > 3, d-DRFWL(2) GNNs can node-level count 3, 4, 5, 6, 7-cycles, but cannot graph-level count any longer cycles.
The proofs of all theorems within this section are included in Appendix C To give an intuitive explanation for the cycle counting power of d-DRFWL(2) GNNs, let us consider, e.g., why 2- DRFWL(2) GNNs can count up 6-cycles. The key reason is that they allow distance-2 tuple (u, u) to receive messages from other two distance-2 tuples (u, w) and (w, v), and are thus aware of closed 6-walks (since 6 2 2). Indeed, if we forbid such kind of message passing, the modified 2-DRFWL(2) GNNs can no longer count 6-cycles, as experimentally verified in Appendix F.2
5 Related works
The cycle counting power GNNs, is proposed in 33 use GNNs' ability to count given-length cycles as metric for their expressiveness. Prior to this work, Arvind et al. [5] and Fürer (25) have discussed the cycle counting power of the FWL(2) test: FWL(2) can and only can graph-level count up to 7-cycles. Huang et al. [33] also characterizes the node-level cycle counting power of subgraph MPNNs and 12-GNN. Apart from counting cycles, there are also some works analyzing the general substructure counting power of GNNs. Chen et al. [15] discusses the ability of WL(k) tests to count general subgraphs or induced subgraphs, but the result loose. Tahmasebi et al. [48] analyzes the substructure counting power of Recursive Neighborhood Pooling, which can be seen as a subgraph GNN with recursive subgraph extraction procedures.
The trade-off between expressive power and efficiency of GNNs. Numerous methods have been proposed to boost the expressive power of MPNNs. Many of the provably powerful GNN models have direct correspondence to the Weisfeiler-Leman hierarchy [2] 28), such as higher-order GNNs 44 and IGNs 4 Despite their simplicity in theory, those models require O(r*+1) time and (nn²) space in order to achieve equal expressive power to FWL(K) tests, and thus do not scale to large graphs even for h: = 2.
Recent works try to strike a balance between the expressive power of GNNs and their efficiency. Among the state-of-the-art GNN models with sub-O time complexity, subgraph GNNs have gained much research interest [8] 17
46 60] Subgraph GNNs process a graph G by 1) extracting bag of subgraphs {G, :1 1,2,..., from G, 2) generating representations for every subgraph G i = 1, 1,2..... p (often using weak GNN such as MPNN), and 3) combining the representations of all subgraphs into a representation of G. Most commonly, the number p of subgraphs extracted is equal to the number of nodes (called a node-based subgraph extraction policy (24). In this case, the time complexity of subgraph GNNs is upper-bounded by O(nm), where m is the number of edges. If we further adopt the K K-hop ego-network policy, i.e., extracting K- -h-hp subgraph G. around each node u. the time complexity becomes O(n deg*+1), Frasca et al. 24 and Zhang et al. (58) theoretically characterize the expressive power of subgraph GNNs, and prove that subgraph GNNs with node-based subgraph extraction policies lie strictly between WL(1) and FWI(2) in the Weisfeiler-Lennt hierarchy. Despite the lower complexity, in practice subgraph GNNs still suffer from heavy preprocessing and a high GPU memory usage.
24
33
39
7

---

Apart from subgraph GNNs, there are also attempts to add sparsity to higher-order GNNs. Morris et al.
45 proposes 6-k-LWL, variant of the WL(k) test that updates a k-tuple u only from the k-tuples with a component connected to the corresponding component in Zhang et al. (58) proposes L.FWI(2) and SLFWL(2), which are variants of FWL.(2 that update a 2-tuple (u, v) from nodes in
either (+) or (u) (v). Our model can also be classified into this type of approaches, yet we not only sparsify neighbors of 2-tuple, but also 2-tuples used in message passing, which results in much lower space complexity. A detailed comparison between our method and LFWLQ2SLFFLL2 is included Appendix D
Experiments
In this section, we empirically evaluate the performance of d-DRFWL(2) GNNs (especially for the case of d = 2) and verify our theoretical results. To be specific, we focus on the following questions:
QI: Can d-DRFWL(2) GNNs reach their theoretical counting power as stated in Theorems 4.3 4.8)
Q2: How do d- d-DRFWL(2) GNNs perform compared with other state-of-the-an GNN models on open benchmarks for graphs?
Q3: What are the time and memory costs of d-DRRFWL(2) GNNs on various datasets?
Q4: Do d-DRFWL(2) GNNs with increasing d values construct hierarchy in discriminative power (as shown in Theorem 3.2 Further, does this hierarchy lie between WL(I) and FWL(2) empirically?
We answer Q1-Q3 in 6. 6.3 as well as in Appendix F The answer to Q4 is included in Appendix F.I The details of our implementation of d-DRFWL(2) GNNs, along with the experimental settings, are included in Appendix E Our code for all experiments, including those in Section of the main paper and in Appendix is available at https: /gthhbb..tttt..../ com/
DD--VL-22 -
6.1 Substructure counting
Datasets.
To answer Q1, we perform node-level substructure counting tasks on the synthetic dataset
in B3 60 The synthetic dataset contains 5,000 random graphs, and the raaiiig/validationn/f split- ting is 0.3/0.2/0.5. The task is to perform regression on the node-level counts of certain substructures. Normalized MAE used as the evaluation metric.
Tasks and baselines. To verify Theorems 4.6 we use 2-DRFWL(() GNN to perform node- level counting task on different substructures: 3-cycles, 4-cycles, 5-cycles, 6-cycles, tailed triangles, chordal cycles, 4-cliques, 4-paths and triangle-rectangles. We choose MPNN, node-based subgraph GNNs (ID-GN) IN-GNN, NGNN, GNNAK+), PPGN, and I2-GNN as our baselines. Results for all baselines are from 33
To verify Theorem 4
compare the performances of 2- 2-DRFWL(2) GNN and 3-DREWL(() GNN on node-level cycle counting tasks, with the cycle length ranging from 3 to 7.
We also conduct ablation studies investigate what kinds of message passing are essential (among those depicted in Figure [] for 2-DRFWL(() GNNs to successfully count up to 6-cycles and other substructures. The experimental details and results are given in Appendix F.2 The studies also serve as a verification of Theorem
Table 1: Normalized MAE results of node-level counting cycles and other substructures on synthetic dataset. The colored cell means error less than 0.01.
Synthetic (norm. MAE)
Method
3-Cyc.
4-Cyc.
5-Cye.
6-Cye.
Tail. Tri.
Chor. Cyc.
4-Clig.
4-Path
Tri.-Rect.
MPNN
0.3515
0.2742
0.2088
0.1555
0.3631
0.31
0.1645
0.1592
0.2979
ID-GNN
0.0006
0.0022
0.0490
0.0495
0.1053
0.0454
0.0026
0.0273
0.0628
NGNN
0.0003
0.0013
0.0402
0.0439
0.1044
0.0392
0.0045
0.0244
0,0729
GNNAK+
0.0004
0.0041
0.0133
0.0238
0.0043
0.0112
0.0049
0.0075
0.1311
PPGN
0.0003
0.0009
0.0036
0.0071
0.0026
0.0015
0.1646
0.0041
0.0144
P-GNN
0.0003
0.0016
0.0028
0.0082
0.0011
0.0010
0.0003
0.0041
0.0013
2- DRRFWL(2) GNN
0.0004
0.0015
0.0034
0.0087
0.0030
0.0026
0.0009
0.0081
0.0070
8

---

Results. From Table I we see that 2-DRFWL(2) GNN achieves less-than-0.00 normalized MAE on all 3, 4, 5 and 6-cycles, verifying Theorem 4.5 2-DRFWL(2) GNN also achieves less-than- 0.01 normalized MAF on tailed triangles, chordal cycles, 4-paths and triangle-rectangles, verifying
Theorems 4.4 and 4.6
It is interesting that 2-DREWL(2) GNN has a very good performance on the task of node-level counting 4-cliques, which by Theorem 4.7 it cannot count in theory. A similar phenomenon happens for subgraph GNNs. This may be because 2-DRFWL(2) GNN and subgraph GNNs still learn some local structural biases that have strong correlation with the number of 4-cliques.
From Table we see that 3-DRFWL(2) GNN achieves a comparable performance to the
Table 2: Normalized MAE results of node-level counting k-cycles (3 < k 7) on synthetic dataset.
2-DRFWI-(2) GNN tasks of counting 3, 4, 5 and 6-cycles. Yet when comes to counting 7-cycles, 3-DRFWL(2)
Synthetic (norm. MAE)
Method
3-Cyc.
4-Cyc.
5-Cye.
6-Cye.
7-Cyc.
2-DRFWL(2) GNN
0.0004
0.0015
0.0034
0.0087
0.0362
GNN greatly outperforms
3-DRFWL(() GNN
0.0006
0,0020
0.0047
0.0099
0.0176
2-DREWL(2) GNN, verifying
Theorems 4.7 and 4.8
Finally, from the last row of Table 7 we see that 1-DRFWL(2) GNN achieves less-than-0.01 normal- ized MAE on 3-cycles, but performs badly 4, 5 and 6-cycles. This result verifies Theorem 4.3
6.2 Molecular property prediction
Datasets. To answer Q2, we evaluate the performance of d-DRFWL(2) GNNs on four popular molecular graph datasets QM,, ZINC, ogbg-molhiv and ogbg-molpcba. QM9 contains 130k small molecules, and the task regression on 12 targets. One can refer to the page for the meaning of those 12 targets. ZINC [20). including smaller version (ZINC- 12K) and full version (ZINC-250K) is a dataset of chemical compounds and the task is graph regression. The ogbg-molhiv (containing 41k molecules) and ogbg-molpcbe (containing 438k molecules) datasets belong to the Open Graph Benchmark (OGB) 31: ; the task on both datasets is binary classification. Details the four datasets given in Appendix E.2.2
Table 3: MAE results on QM9 (smaller the better).
The top two are highlighted as First, Second.
Target
I-GNN
1-2-3-GNN
DINN
Deep LRP
LRP
PPGN
NGNN
I--GNN
2-DRFWL(2) GNN
0,493
0.476
0.244
0.364
0.231
0.428
0.428
0.346
a:
0.78
0.27
0.95
0.298
0.382
0.29
0.230
0,222
Chomo
0.00321
0.00337
0.00388
0.00254
0.00276
0.00265
0.00261
0.00226
Fumo
0.00355
0.00351
0.00512
0.00277
0.00287
0.00297
0.00267
0.00225
0.0049
0.0048
0.0112
0.00353
0,00406
0.0038
0,0038
0,00324
34.1
22.9
17.0
19.3
16.07
20.5
18.64
15.04
ZPVE
0.00124
0.00019
0.00172
0.00055
0.0064
0.0002
0.00014
0,00017
Up
2.32
0.0427
2.43
0.413
0.234
0,295
0.211
0.156
2.08
0.111
2.43
0.413
0.234
0.361
0,206
0.153
II
2.23
0.0419
2.43
0.413
0,229
0.305
0.269
0.145
1.94
0.0469
2.43
0.413
0.238
0,489
0.261
0.156
C.
0.27
0.0944
2.43
0.129
0.184
0.174
0.0730
0.0901
Baselines. For QM9, the baselines are chosen as 1-GNN, 1-2-3- GNN
44 DTNN 53 Deep
LRP [5], PPGN, NGNN [59] and 12-GNN [33]. Methods [3] 26 40, 47) utilizing geometric features or quantum mechanic theory are omitted fairly compare the graph representation power of the models. For ZINC and ogbg-molhiv, we adopt GIN, PNA [6]. DGN 77) HIMP 23 GSN 10 Deep IRP 15) CIN 99, NGNN, GNNAK+, SUN 24 and 12-GNN as our baselines. For ogbg-molpcha, the baselines are GIN, PNA, DGN, NGNN and GNNAK+. The experimental details are given in We leave the results on ZINC, ogbg-molhiv and oglg-molpcha Appendix F3
Appendix H.2.2
Results. On QM9, Table 3 shows that 2-DRFWL((2 GNN attains top two results on most (11 out of 12) targets. Moreover, 2-DRFWL(2) GNN shows a good performance on targets Un, U, and G. where subgraph GNNs like NGNN or 12-GNN have a poor performance. The latter fact actually reveals that our method has a stronger ability to capture long- long-range inteructions on graphs than subgraph GNNs, since the targets Uo, U, H and G are macroscopic thermodynamic properties of

---

molecules and heavily depend on such long-range interactions. We leave the detailed analysis to Appendix F.4 Apart from QM9, Table FF that d-DRFWL(2) GNN outperforms CIN 9 on ZINC-12K; the performance on ogbg-molhiv is also comparable to baseline methods. These results show that although designed for cycle counting, d-DRPWI.(2) GNN is also highly competitive on general molecular tasks.
is interesting to notice that d-DRFWL(2) GNN shows an inferior performance on ogbg-molpcba, compared with baseline methods. We conjecture that the results on ogbg-molpeba might be insensitive the gain in cycle counting power, and might prefer simple model architectures rather than highly expressive ones.
6.3 Empirical efficiency
To answer Q3, we compare the time and memory costs of 2-DRFWL(2) GNN with MPNN. NGNN and 12-GNN on two datasets-QMM and ogbg-molhiv. We use three metrics to evaluate the em- pirical efficiency of 2-DRFWI.(2) GNNs: the maximal GPU memory usage during training, the preprocessing time, and the training time per epoch.
To make fair comparison, we fix the number of 2-DRFWL(2) GNN layers and the number of message passing layers in all baseline methods to 5; we also fix the size of hidden dimension to 64 for QM9 and 300 for ogbg-molhiv. The subgraph heights for NGNN and I2-GNN are both 3. The batch size is always 64.
Table 4: Empirical efficiency of 2-DRFW((2) GNN.
QM9
ogbg-molhin molhiv
Method
Memory (GB)
Pre. (s)
Train (slepoch)
Memory (GB)
Pre. (s)
Train (slepoch)
MPNN
2.28
64
45.3
2.00
2.4
18.8
NGNN
13.72
2354
107.8
5.23
1003
42.7
P.GNN
19.69
5287
209.9
11.07
2301
84.3
2-DRFWL(2) GNN
2.31
430
141.9
4.44
201
44.3
Results. From Table 4 we see that the preprocessing time of 2-DRFWL((2 GNN much shorter than subgraph GNNs like NGNN or I2-GNN. Moreover, 2-DRFWL(2) GNN requires much less GPU memory while training, compared with subgraph GNNs. The training time of 2-DRFWL(2) GNN is comparable to NGNN (which can only count up to 4-cycles), and much shorter than I2-GNN.
We also evaluate the empirical efficiency of 2-DRFWL(22 GNN on graphs of larger sizes. The results, along with details of the datasets we use, are given in Appendix [.5] From Table 14]in in Appendix F5 we see that 2-DRFWL(2) GNN easily scales to graphs with 500 nodes, as long as the average degree is small.
7 Conclusion and limitations
Motivated by the analysis of why FWL(2) has a stronger eycle counting power than WL(1), propose d-DRFWIL(2) tests and d-DRFWL((2) GNNs. It is then proved that with d = 2, d-DRFWI((2) GNNs can already count up to 6-cycles, retaining most of the cycle counting power of FWL(2). Because d- d-DRFWL(2) GNNs explicitly leverage the local nature of cycle counting, they are much more efficient than other existing GNN models that have comparable cycle counting power. Besides, d-DRFWL(() GNNs also have an outstanding performance on various real-world tasks. Finally, we have to point out that our current implementation of d-DRFWL(2) GNNs, though being efficient most of the time, still has difficulty scaling to datasets with a large average degree such as ogbg-ppa, ppa, since the preprocessing time is too long (~~40 seconds per graph on ogbg-ppa). This also makes our method unsuitable for node classification tasks, since these tasks typically involve graphs with large average degrees. We leave the exploration of more efficient d-DRFWI((2) implementation future work.
10

---

Acknowledgement
The work supported in part by the National Natural Science Foundation China (62276003), the National Key Research and Development Program of China (No. 20212D01147022 and Alibaba Innovative Research Program.
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.011 179,, 2020.
[2] Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algo- rithmica, 17(3):209-233 223,, 1997.
[3] Brandon Anderson, Truong Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. Advances neural information processing systems, 32, 2019.
[4] V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman
invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113:42-33 59, 2020. ISSN 0022-0000. doi: https///bb..ogg//...06fff.ssssss scissciienn http:///a.aacrrrrraae//////////0
URL httpstts::/// /ww. scienccdieect.....cecccccccicece
[5] Vikraman Arvind, Frank Fuhlbrücc, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 1 113:42-59, 2020.
[6] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pages 599-608. PMLR, 2021.
[7] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pages 748-758, PMLR, 2021.
[8] 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.
[9] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances Neural Information Processing Systems, 34:2625-2640, 2021.
[10] Giorgos Bouritsas, Fabrizio Frasca. Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-66) 2022.
[11] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint 1rXiv:1711.07553, 2017.
[12] Jin- Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-44 410, 1992.
[13] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735. PMLR, 2020.
[14] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
[15] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-1033 10395, 2020.
11

---

[16] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Veličković. Principal neighbourhood aggregation for graph nets, Advances in Neural Information Processing Systems, 53:13260-13277 2020.
[17] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems, 34:1713-1726, 2021.
[18] Mukund Deshpande, Michihiro Kuramochi, and George Karypis. Automated approaches for classifying structures. Technical report, MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE, 2002.
[19] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
[20] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. 2020.
[21] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326-22344 2022.
[22] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903. 1903.02428, 2019.
02428,
[23] Matthias Fey. Jan-Gin Yuen, and Frank Weichert. Hicrarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006. 12179, 2020.
[24] Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. In Advances in Neural Information Processing Systems, 2022.
[25] Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. International Conference Algorithms and Complexity, pages 260-271. Springer, 2017.
[26] Johannes Gasteiger, Janek GroB, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03122 2020.
[27] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263- 1272. PMLR, 2017.
[28] Martin Grohe and Martin Otto. Pebble games and linear equations. The Journal of Symbolic Logic, 80(3):9978844, 2015.
[29] Pedro Hermosilla, Marco Schäfer, Matëj Lang, Gloria Fackelmann, Pere Pau Vázquez, Barbora Kozlíková, Michael Krone, Tobias Ritschel, and Timo Ropinski. Intrinsic-extrinsic convolution and pooling for learning on 3d protein structures. arXiv preprint urXiv:2007.06252. 2020.
[30] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitiik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 1905. 12265, 2019.
[31] Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:22118-22111 2020.
[32] Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the meisfeiler-lehmaad test and its variants. In /CASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages $533-8537, 2021. doi: 10. 1 1091119999939922222211 202.9911333.........
[33] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang Boosting the cycle counting power of graph neural networks with i--gnns 2023.
12

---

[34] Chuntao Jiang, Frans Coenen, and Michele Zito. Finding frequent subgraphs in longitudinal social network data using a weighted graph mining approach. In Advanced Data Mining and Applications: 6th International Conference, ADMA 2010, Chongqing, China, November 19-21, 2010, Proceedings, Part I 6, pages 405-416. Springer, 2010.
[35] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pages 2323-2332. PMLR, 2018.
[36] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint
2016.
[37] Mehmet Koyutürk, Ananth Grama, and Wojeiech Szpankowski. An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics, 201suppL 2004.
[38] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances Neural Information Pro- cessing Systems, 34:21618-21629, 2021.
[39] Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-44788 2020.
[40] Yi Liu, Limei Wang, Meng Liu, Xuan Zhang, Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3d graph networks. arXiv preprint arXiv:2102.05013, 2021.
[41] Haggai Maron, Heli HamuH Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv: 2018.
[42] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[43] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. International conference on machine learning, pages 4363 4371. PMLR, 2019.
[44] Christopher Morris, Martin Ritzert, Matthias Fey, William 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.
[45] Christopher Morris, Gauray Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order order graph embeddings. Advances in Neural Information Processing Systems, 33:21824-21848 1840, 2020.
[46] Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. In Advances in Neural Information Processing Systems, 2022.
[47] Zhuoran Qiao, Matthew Welborn, Animashree Anandkumar, Frederick R Manby, and Thomas F Miller III. Orbnet: Deep learning for quantum chemistry using symmetry-adapted atomic-orbital features. The Journal of chemical physics, 153(12):124111. 2020.
[48] Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:20/2.03174, 2020.
[49] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[50] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
[51] Yanbo Wang and Muhan Zhang. Towards better evaluation of gnn expressiveness with brec dataset. arXiv preprint
2023.
13

---

[52] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI. Series, 2(9):12-16, 1968.
[53] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9(2):513-533 530, 2018.
[54] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 32( 32(1):4-26 2:422,, 2020.
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
[56) Zuoyu Yan, Junru Zhou, Liangcai Gao, Zhi Tang, and Muhan Zhang. Efficiently count- ing substructures by subgraph gnns without running gnn on subgraphs. arXiv preprint arXiv:2303. /0576, 2023.
[57] Jiaxuan You, Jonathan M SomeesSellan, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, pages 10737-10745, 2021.
[58] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expres- siveness hierarchy for subgraph gnns via subgraph weisfeiler-lemman tests. arXiv preprini arXiv:2302.07099 2023.
[59] Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15734 15747, 2021.
[60] 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.
[61] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
14

---

A Message passing neural networks
Message passing neural networks (MPNNs) 22 36 50 55 are a class of GNNs that iteratively updates node representations hu, E Ve by aggregating information from neighbors. At the t-th (t 1) iteration, the update rule for MPNNs is
ml() (1 (iu-",n 1 Cav) ))
f(()
1 11-1)
(13)
eEN(u)
where 1/ is the representation node at the t-th iteration and Eur is the edge feature of (u, v} E Eg. (( and (+) are learnable functions, and + a permutation-invarian aggregation operator, such as sum, mean or max. The representation of graph G' is obtained by
hg R(
Ve l).
(14)
where R is a permutation-invarian function of multisets.
is known [55] that the ability of MPNNs to discriminate between non-isomorphic graphs is upper- bounded by the WL(1) test. When comes to counting cycles, MPNNs cannot graph-level count any cycles, stated in [33]
B Proofs of theorems in Section 3
B.1 Proof of Theorem 3.1
We restate Theorem as following.
Theorem B.1. In terms of the ability to distinguish between non-isomorphic graphs, the d-DRFWL(2) test is strictly more powerful than WL(1), for any d >
Proof. In Theorem 3.2 we will prove that (d + 1)-DRFWL(2) is strictly more powerful than d- DRFWL(2), for any d > 1. Therefore, we only need show that I-DRFWL(2) strictly more powerful than WL(1). We will first prove that I-DRFWL(2) can give an implementation of the WL(I) test. Actually, let
w (u), d(u, v) = 0, NULL
(u, =
(15)
d(u,v) = 1,
be the initial I-DRFWL(2) colors of (u, v& with 0 < d(u, v) < 1. Here W (0) WW.DD (u) is the initial
WL(1) color of node u (which is identical for all u E Vc). It obvious that W(O)) (u, v) does only
depend on d(u, v). As for the update rule, at the (2t 1)-th iteration with t 1, we ask
POOL 1(2(-1) ((( 2) (1, v), (2t 2), w))B (2 (2,
(16)
and
POOL 1(2-1) ((W(2)2)) v), w(= (1,
(u, u)) ((2 (00022)(., (v.
(17)
for those (u, 2) with distance 1. Here, both No(u) n (1)) and (1 n No((v) have only one element, POOL 12t--1) (2t-1) and POOL102 1(20))(2-1)
1(2r-1) simply select the second and the first component from
the unique 2 2-tuple in the corresponding multisets, respectively. The HASH (2t-1 functions for k = 0
or are chosen as
HASH((?')) (2
(u, (M
CONCAT (M (2 .M 1112t11) (18)
DEIJEI
for d(u, v) = 1, 1 2) (u, u),
HASH 21-1) 1) (w(21-2) (m, (M DEi.EE1
(19)
for d(u, v) = 0.
15

---

What we did is to ask the (2t - 1)-th iteration of 1-DRFWL((2 to record the WL(1) colors Word (u), Word (v) in the 1-DREWL(2) color of node pair (u, In the 2/-th iteration, I-DREWL(2) then uses this record to update the colors of (u, u) and u);
HASH (1)
(w(2z-3) (u,v), (M
(7(2011(,,1))
(20)
0EijEl)
for ((rd(u,)) 1,
HASH?20 (wi (M
-M11
(21)
0gi
for d(u, v) = O.
And ask 0(20) M11 vu HASHWI. (wr(2 (u, u), POOLIIO) (0) (EW (1, (v,o): (v,)):
(22)
Here (2) (u, u) and ((2+-2) (u, v) are stored in W(2 (u, v) in the last iteration (in the first
and the second components respectively). HASH and POOT -W(11) are the hashing functions
(c)
used by WL(1) test, as in (1. It is easy to see the above implementation uses 2 iterations of 1-
DRFWL(2) update to simulate iteration of WI.(1) update. Therefore, I-DRFWI.(2) is at least as powerful as WL(I) in terms of the ability to distinguish between non-isomorphic graphs.
To see why I-DRFWL(2) is strictly more powerful than WL(I), we only need find out a pair of graphs G and H such that WL(1) cannot distinguish between them while I-DRFWL((2) can. Let G be two 3-cycles and H be one 6-cycle. Of course WL(1) cannot distinguish between G and H. However, 1 1-DRFWL(2) can distinguish between them because there are no triangles in H but two in G, as is made clear in the following. In the first iteration of I-DRFWL(2), the M1 term collects common neighbors of every node pair (u, v) with distance 1. In G this results in non-empty common neighbor multisets for all distance-1 tuples (u, v). while in H all such multisets are empty. I-DRFWL(() then
makes use of this discrepancy by properly choosing the HASH, function that assigns different colors for distance-] tuples in G and in H. Therefore, 1-DRFWL(2) can distinguish between G and H.
B.2 Proof of Theorem 3.2
We restate Theorem 3 3.2 as following,
Theorem B.2. In terms of the ability distinguish between non-isomorphic graphs, FWL(2) is strictly more powerful than d-DRFWL(2), for any d > 1. Moreover, (d+ + 1)-DRFWL(2) is strictly more powerful than d-DRFWL(22.
Proof. First we show that FWL(2) can give an implementation of d-DRFWL(2) for any d d> 1. The implementation is in three steps:
Distance calculation. For any 2-tuple (u, v) E Vg. let its FWL(2) color (( (u, v) be 0 if u = v, 1 if {u, v) E &g, and oc otherwise. In the first (n 1) iterations, FWL(2) can use the following update rule to calculate distance between any pair of nodes,
(w, + W(+ w (u, v) min (w(t- (u, v), min wEVa
(u, ( (u,))) m())
(23)
When t n 1, the FWL(2) color for any (u, v) E Vi gets stable and becomes d(u, v).
Initial color generation. At the n-th iteration, FWL(2) transforms ((n (u, u)
d(u, v) into
W (1, v) CONCAT (d(u, v), (:( (y (u, ot), 0 & d(u, < d, otherwise.
(24)
CONCAT (d(u, NULL),,
(0(00) Here WEDRRFWL (u. v) is the initial d-DRFWL(2) color of 2-tuple (u, v). Because W (0) d-DREWWL (u, v)
only depends on d(u, v). the RHS in (44 is a function of ((n-1)(u,, v) = d(u, v), and thus complies with the general form of F2L(2) as
16

---

(a) When running 4-DRFWL(2)) in 10-cycle, there are (marked as colored, with 3 on the inferior are and 3 on the superior are) nodes contributing to the update of any distance-4 tuple (u,
(b) When running 3-DRFWL(2) in 10-cycle (or any cycle with length e 10), there are only 4 (marked as colored) nodes contribut- ing to the update of any distance- tuple (u,
Figure 3: Illustration on the counterexample used the proof of the separation result in Theorem
3.2
Here take and (3d + 1y-cyl,, or 10-cycle, is shown. is clear that for distance-
d + 1) tuple there are nodes on both the inferior are and the superior arc that contribute to its update. Contrarily, for distance-d tuple only nodes the inferior are contribute.
d-DRFWL(2) Update. For the (n t)-th iteration with t 1, the FWL(2) test uses the following POOT, (n+1) and HASH(*+)) functions to simulate the 1-th iteration of d-DRFWL((2):
HASH (+++))) reads the first field of ((ntt-1) v) to get d(u, v) = k, and decides whether to update the color for (u,e) v) (if
d) or not (otherwise).
For every E Vo. POOL reads the first field of ((++t11) (w, v) and ((++t- (u, w) to find that d(w, v) = i and d(u, w) j. and then either seleets w WDDREWLe (w, v) and w WaDRFwEL (u, w) from the second field of W(++t=1)(u) v) and W(*+t-1) (u, w), and
applies 7 to get M (u,,), v), if it finds 0 < i,j < d, or ignores the contribution from (Win+e-)) (w,, v), W W(n+t-1) w)) otherwise.
HASH calculates W (t( (2, if it has decided that the color for (u, v) should be updated.
d-DRFWLoyyu, v) using (6) and assigns it to the second field of
For the READOUT part, FWL(2) simply ignores the tuples (u, v) with d(u, v) d. It is easy to the above construction does provide an implementation for d-DRFWL(2).
Similarly, one can prove that (d + 1) DRFFL((2) also gives an implementation of d-DRFWL(2)) for any d > 1. by only executing the "initial color generation" and "d-DRFWL(2) update" steps stated above. Since the colors for (w, v) with d(u, v) > d never update, it is sufficient only keeping track of pairs with mutual distance & + which (d + 1) 1)-DRFWI.(2) capable of.
Now we will turn to prove the separation result: for any d > 1, there exist graphs G and H that FWL(2) (or (d + 1)-DRFWL((2) can distinguish, but d-DRFWL(2) cannot. We ask G to be two (3d 1+-1yyycee,, and /l a single (6d + 2yccle... FWL(2) can distinguish between G and H by (i) calculating distance between every pair of nodes in and H: (ii) check if there is (u, v) E y2 such that d(u, 2 = oc at the READOUT step. The above procedure will give G true label and H false label.
To see why (d+1)_DRFWL.2) can also distinguish between G and H, we designate that POOT d+1(1) be a multiset function that counts the elements in the multiset, for all 0 < i,j & d + 1, and that Briefly speaking,
(ASH(L) d+1 be the of all items in (M@+11) (u, ogijEdt1
asking the first iteration of (d + 1)-DRFWL(2) to count how many nodes w contribute to the update of a distance-(d + 1) tuple (u, v). via the form (w) (w, w), W7O) (u, w)). For any distance-(d + 1) tuple in G. the count is for and d 5 for d (actually when 1, distance-(d 1) tuple (u, v) splits (3d 1)-cycle into an inferior are of length (d + 1) and superior are of length 2d; d
17

---

nodes on the inferior are and 3 nodes on the superior arc, along with u and v, sum up to the number; Figure Ba illustrates the case of d = 3). For distance- (d + 1) tuple in H, the count becomes d + which is always different from the count in G. The (d+ 1 1)-DR)WF.C22
test then uses this discrepancy to render different colors for distance- (d + 1) tuple in G and in H. thus telling G from H.
The above proof also reveals why d-DRFWL(2) fails to distinguish between G and H. Actually, let (u, u) be a distance-k: tuple in V2 or V with O < k & d. In the following we use W (u, v) to denote the d-DRFWL(2) color of (u, u) at the t-th iteration, both for (u, v) E VV and (u, v) VH. We will now use induction prove that for all I, W(O v) only depends on d(u, v), and does not depend on whether (u, v) is in G or H. This implies that for (u, E V& and (d',z') E Vi W( (u, v) = (w', b') holds for all iterations & as long as d(uu, v) = d(u',
Base case. Since the initial d- d-DRFWL(2) color of a distance-k tuple (0 < k < d) only depends on k. the f = 0 case is trivial.
Induction step. Now we assume ((t-1)(u,,)) v) only depends on d(u,v) no matter which graph k(())
(u, u) is in, for some t > 1. We will then prove that no matter what HASH and POOL. we choose, W v) only depends on d(u, v) no matter which graph (u, v) is in. Actually, it is sufficient to prove that the multisets
k(t) functions
(i.j) : E (N) 0s. < <d
(25)
are equal, for any (u, v) E V UV with d(u, v) = k and 0 < k & d. This is because the inductive hypothesis leads us the fact that
Mij k(t) (u, (u, k(1)) (H (W(()) (w, wit w)) w Ni((u) (N)())
can only depend on the number of elements of the multiset on the RHS, because all elements in the RHS multiset must be equal. Therefore, the aforementioned condition guarantees that M (u, v) are all the same for any distance-k tuple (u, v) E v& U 13, with any fixed i.j,k k and any L. This, along with the update rule (6). makes the induction step.
Now we prove that multisets defined by (25 are equal for all (u,v) E V2 U V2 with any given d(u, v) = k.0 & k < d. The intuition of the proof can be obtained from Figure 3b which shows that for any distance-d tuple (u, v) in a cycle not shorter than (3d + 1). the nodes that contribute to (25) are exactly those nodes on the inferior are cut out by (u, v), plus u and This means that the distance-d tuple is completely agnostic about the length of the cycle in which it lies, as long as the cycle length is b 3d + 1. Therefore, any distance-d tuple cannot tell whether it is in G or in H, resulting in the conclusion that the multisets in (25) are equal for all distance-d tuples (u,, v). Similar arguments apply all distance-k tuples in G and H, long
k d. Therefore, we assert that w'(t (u, v) does only depend on d(u, v),, matter which graph (u, v) is in, at the t-th iteration. This finishes the inductive proof.
Notice that there are (6d + 2) distance-k k tuples in either G or H, for any 0 < k < d: moreover, each of those distance-k tuples have identical colors. We then assert that G and H must get identical representations after running d-DRFWL(2) on them. Therefore, d-DRFWL(2) fails to distinguish between G and H.
We remark that for any d > 1, d-DRFWL(() tests cannot distinguish between two k-cycles and 2k-cycle, as long as a > 3d + 1. The proof for this fact is similar to the one elaborated above.
B.3 Proof of the equivalence in representation power between d-DRFWL.22) tests and d-DRFWL(2) GNNs
At the end of 3.2, we informally state the fact that d-DRFWL(22 GNNs have equal representation power to d-DRFWL(2) tests under certain assumptions. We now restate the fact as the following
Proposition B.3. Let q : G + colors be a d-DRFWL(2) test whose HASH POOL READOUT functions are injective, v0 & i,j, k & and VI > 1; in addition, q assigns different initial colors to 2-tuples (u, v) with different u, distances. Let f : G + R2 be d- (-DRFWL(2) GNN
k(t) and
18

---

with T d-DRFWI12) GNN layers; the initial representations haa assumed to depend only on d(u, v).
If two graphs G and H. get different representations under f. i.e. f(G) # f(H), then q assigns different colors for G and H. Moreover, if G and are graphs such that q assigns different colors for G and H, there exists d-DRFFL((2) GNN f such that f(G) & f(H).
Proof. For simplicity, we denote
Varga {(u, v) E V2 :0 & d(u, v) & d}.
(26)
We prove the first part by proving that, if two tuples (u, v) and (u', v²) get different representations l and (T)) after applying LT o or-1 .... o 01 o Lr, then
(u, + W (u',0')
(27)
after we apply q for T iterations. Since W( (u, v) is a refinement of W(T) (u, v). (27) implies that W(rr) r) & (( v'). Now, f(G) * fH) means for all bijections from Ga to Vi. there exists a pair (u, v) Va such that 1 * ha'd with (u', v') = b(u, v). the above statement holds true, this means for (u, v) and (u', v') we have (u,)),, o Wroo) (u', o'). Since this is the case for any bijection b, we assert
READOUT (w(l))(,)) v): (u,v) E V2 V2
* READOUT (EWio) v) (u, E VH
or simply W(G) * WHH), and the first part is proved.
Proof for the above statement can be conducted inductively. When T = 0, 1: * (0) means
d(u, v) # d(u', e²), since the initial representation h: of (u, v) only depends on the distance d( (u, v). By the second condition of g, the above fact further implies W (u, v) & w0 (u', v'), and the base case is proved.
Now, assuming that the above statement is true for T 6- with > 1, now prove the T= = l case. Given ( * hu'e' there are two possibilities: (a) (f-1)) * har (c-1); (b) for some i, (i((F) # izk(t) where k d(u, v) d(u', e") (we can safely assume dl d(u, v) d(u', v'), since auv
otherwise (27) trivially holds).
For possibility (a), the inductive hypothesis tells ((e v) # w v'), thus i5k(() w(0 (u, # (1' For possibility (b), notice that aun is function of the multiset
(h((e>)) ((((=")) E NN() (N5)))
(ek(C) Therefore, aue # a'''' means that for all bijection b' from NG(u) from
izk(E)
(v) to Nulwn)
there exists w E (N(u) (v) such that (h _ift=") + ((( n ((--)), where w/ = ((w). Without loss of generality, let us discuss the case where (il-1) A (h(ee)) In this case, the induc- tive hypothesis tells us W(e-1) (w,, v) * wle-1)(w', v²), thus (wle-1) vw,, W(e-)) w)) + (w(e))((u v²), W(( w')). The other case h (e-1) * (e-1) also leads to this result. Since the bijection b' arbitrary, we assert that the multisets
| ((w(e-)) (w, v), ((e-)((u, w)) (w,
and
((w(t-))(u v'),')) ((( (u', (u', w' E (N(d))
are not equal. Since the functions POOL, M() and (ASH w(0 w) * (( (u', v²). So far, we have finished the induction step. Therefore, the first part of the theorem is true.
&. are injective, the above result implies
19

---

For the second part of the theorem, we quote the well-known result of Xu et al. [55] (Lemma of the paper), that there exists function f & I= on a countable imput space X' such that any multiser
function can be written
g(X) = Σ f(x) X
(28)
for some function O where X is arbitrary multiset whose elements are in X.
Now, let G and H be graphs that both obtain their d-DRFWL(2) stable colorings under after T' iterations, and that q assigns different colors for them. We will now prove that there exists d-DRFWL(2) GNN with T d-DRFWL(2) GNN layers that gives G and H different representations.
Since the set of d-DRFWL(2) colors generated by g is countable, v: colors - N that assigns a unique integer for every kind of d-DRFWL(2) color. Under mapping all & POOL, k<()) and READOUT functions can be seen as functions with codomain N. Then, the initial representation for (u, with 0 < d(u,v) < d is hur (w, For
designate mapping
(e) the update rules, the lemma in 55 tells us that by choosing proper mijk and ofj functions, the following equality can hold,
R(A) (X) =0) POOL.
Σ min millv())) WEX
Digh
(0) with X being any multiset of 2-tuples of d-DRFW142) colors. Therefore, we can choose misk in (T) following the instructions of the above lemma, and choose + as Σ. We then choose the functions
(B) k as
fk
(jk(tt) d
HASH! (M-1 (1'1 (-((t())))))
( (0igh (oth((t)
DEAJEN)
(29)
DELjEd
It is now easy to iteratively prove that fue is exactly (wl v)). For the pooling layer, we again leverage the lemma [55] to assert that there exist functions and M' such that
READOUT(X) -M' (Erola))
(30)
where X is any multiset of d-DRFWI((2) colors. We then choose
R(X) = Σ r(((x)),
(31)
TEX
and choose M = vo M'. Now the d-DRFWL(2) GNN constructed above with d-DRFWL(2) GNN layers produces exactly the same output as q (except that the output converted integers via v). Because assigns G and H/ different colors, the d-DRFWL(2) GNN gives different representations for G and H.
C Proofs of theorems in Section 4
We first give a few definitions that will be useful in the proofs.
Definition C.1 (Pair-wise cycle counts). Let u, v E Vc. we denote Cx, v) as the number of (I + l)-cycles S that satisfy:
S passes u and v.
There exists a k-path and an 1-path (distinct from one another) from u to v, such that every edge in either path is an edge included in S.
For instance, the substructures counted by C2.(u, v) and Ca,a v) are depicted in Figures and 4b respectively.
20

---

Definition C.2 (Tailed triangle counts). Let E Vc, T(u. v) is defined as the number of tailed triangles which u and are at positions shown Figure 4c
Definition C.3 (Chordal cycle counts). Let u, v E Va. CCi v) and CC2 v) are defined as the numbers chordal cycles which u and v are at positions shown in Figures 4d and 44] respectively, Moreover, we use CC1 (u) and (C2(u) denote the node-level chordal cycle counts with the node u located at positions shown in Figures 4f and 4g respectively.
The notations CC1 and CC2 are overloaded in the above definition, which shall not cause ambiguities with check on the number of arguments.
Definition C.4 (Triangle-rectangle counts). Let u, V Va. TRi v) and (R, v) are defined as the numbers of triangle-rectangles
which and are at positions shown in Figures 44h and respectively. We also define three types of node-level triangle- TR2(u) and T Rg (u). They are the numbers of triangle-rectangles where node u is located at positions shown in Figures 41 4k and respectively.
counts, namely T Rı (u),
(a) (as v)
(b) Cs,a(u, v)
(c) T(u, v)
(d) (u,
(e) (U, v)
(u)
(g) CC2(u)
(h) T' (u, v)
ii (R,
(R)
kk) T (u)
(1) (R)
Figure 4: Illustrations of certain substructure counts.
There are relations between the above-defined counts. For chordal cycle counts we have
CCi(u)= = Σ (v, CC2(u) = Σ
(u,
(32)
vEN((M)
vENI(1)
and
CC2(u)= = Σ CC2(u,v).
(33)
eENi(u)
For triangle-rectangle counts we have
(Ri(u) = Σ (Ri(u,), TRe(u)= Σ
TRi(
(34)
VEAi(u))
wENi(
and
TRa(u) Σ TRa(u,)), (Rs(u)
E
TR2(U,
(35)
(ENG(a))LAs(1)
21

---

We also denote (2 u) as the number of k- k-paths starting at node and ending at node (u, v) as the number of l-wwalss from u to v, and C5(u (u) as the number of k-cycles that pass node u.
The following lemma will be used throughout this section.
Lemma C.5. Let S be a graph substructure. If there exists a d-DRFWI((2) test q such that for any graph G E 9,
W u) C(S, G), Vu VG
(36)
after running 9 g.oor T iterations on G, then d-DRFWL122 GNNs can node-level count S.
Proof. Let uI), (G2, u2) E 9 x V. and C(S, u1, Gi) C(S, u2, G2). Then by assumption, ((T)(u, u1) + W (u2, u2)
(37)
after running for T iterations G1 and G2. From the proof of Proposition B.3 (which is in
Appendix B we see that there exists a d-DRFWL(2) GNN f with T d-DRFW (2) GNN layers such that tuple (u,v) v) with 0 & d(u,v)
gets its representation Iuee (W (u, v)), where
is an injective mapping from the color space of q to N. Therefore, 37 implies has in * hugag or f(G1, u1) # f(G2, u2). This means that d-DRFWL(2) GNNs can node-level count
C.1 Proof of Theorem
We restate Theorem 4.3 as following,
Theorem C.6. I-DRFWL(2) GNNs can node-level count 3-cycles, but cannot graph-level count any longer cycles.
Proof. To prove that I-DRFWL((2 GNNs can node-level count 3-cycles, suffices to find DRFWL(2) test such that after running for T iterations on graph G,
WT)
Cz(u), Vu Vg.
Below we explicitly construct q. Notice that if ((,,)) = 1, M (u, can know the count C(u, v) = (u) NG (x)) in the first I-DRFWL(2) iteration. This is essentially the number of triangles in which {u, w) Eg is included as an edge. In the second iteration, can ask
(w, 2
Σ VENI(u)
C(u,
(38)
and we have W12) (u, u) Ca(u). Therefore, the positive result is proved.
To prove that 1-DRFWL((2 GNNs cannot graph-level count k-cycles with 1: > 4, we make use of the fact mentioned at the end of Appendix B.2 that I-DRFWL((2) tests (and thus GNNs) cannot distinguish between two k-cycles and one 2k-cycle, as long as & > 4. This set of counterexamples leads to the negative result.
C.2 Proofs of Theorems
Before proving the theorems, we state and prove series of lemmas.
Lemma C.7. There exists a 2-DFFWL(2 test such that for any graph e G and for any 2-tuple vu, V2 with d(u, = 1 or d(u, v) 2, q assigns
W(D) v) = Pa(u, v),
(39)
for some integer T >> 1.
Proof. Let q be a 2-DRFWI((2) test that satisfies: at the first iteration, M( (u, v) and M (u, v)
both count the number of nodes in (1) n (v)),, and HASH() of simply selects the M component, for 1, 2: g stops updating colors for any tuple from the second iteration. It easy to that q satisfies the condition stated in the lemma.
22

---

Lemma C.8. There exists 2-DRFWL(2) test q such that for any graph G E G and for any node E Va, q assigns
W (u, u) = deg(u),
(40)
for some integer T > 1. Here deg(u) is the degree of node VG-
Proof. Let q be a 2-DREWL(2) test that satisfies: at the first iteration, Mff (u, u) counts [ (N) =
deg(u), and HASH (1) of q selects the M component, then W u) deg(u). q then stops
updating colors for any tuple from the second iteration. is obvious that satisfies the condition stated in the lemma.
Lemma C.9. There exists a 2-DRFWL(2) test q such that for any graph G 9 and for any 2-tuple (u,v) E V& with d(u,v) v) = or d(u, v) 2, assigns
W (u, u) deg(u) + dog(u),
(41)
for some integer T >> 2.
Proof. By Lemma
C.8 there exists 2-DRFWL((2) test g that assigns WLT) u) = deg(u) for
distance-O tuples (u 4)
with u E Va. where T > 1. Now, for the (T + 1)-th iteration of q, we ask
(u, v) = W(T uu, 1(++1)
(42)
0k
M (u, r) (v,
(43)
where k = 1 or 2: q then assigns
(2/22+))(u, for d(u, v) 1e and 1,2. Now W(T+1)(u, u) deg(u) + deg(u) for T 2.
W(T+ v) = MMx +2) (u, v) + M
x(T+1) (u, v),
(44)
Lemma C.10. There exists a 2-DRFWI((2) lest q such that for any graph G E 9 and for any 2-tuple (u,v) E V& with d(u, = 1 or d(u, v) = 2, assigns
w(T) w(TT = P)(u,o),
(45)
for some integer T > 2.
Proof. A 3-path starting at and ending is a 3-walk + + y + with u # y and æ + v. Therefore.
Pa(u, v) = Wa(u, v) #(u zz #(u
+ (u,
(46)
Here #(u + + u + v) is the number of different ways to walk from u to neighboring node x, then back to u, and finally to which is also a neighbor of u (æ can coincide with v). The term #(u - e + y + v) can be interpreted analogously. The l(u,)eee takes value (u, v) &c. and 0 otherwise. This term accounts for the count #(u + u au- v) which subtracted twice. is easy to see that
#(u -uu+x - u > 0) = 1(.vjes deg(u): # uu--- v) = (u,n)eE deg(v).
(47)
(48)
Now construct g as following: at the first iteration, q chooses proper POOL, and HASH (1) functions (0 & i, k < 2) such that
k()
(w, {
arbitrary, (Pz(u, v), dog(u) + deg(v)), P)(u,)).
if d(1 v) = 0. if d(d v)
(49)
if df v) = 2.
23

---

(a) Setting
(b) Setting x (c) Setting 2
(d) Setting a and I
Figure 5: The four types of redundant 4-walks requiring subtraction in the proof of Lemma C.12 Each of the 4 situations is obtained by coalescing one or more node pairs from (u, (x, z) and (ar, v) in 4-walk
-
v, while subject to constraints # y and y # v.
this is possible. At the second iteration, we ask M Mn M and Mn k(2)
k(2)
k(2)
From Lemmas to be
C.7 and C.9
M (u, v)
E
(P2(u, w) P2(w,)))
(50)
(ENG(v)(NN(())
kk2) (u,
Σ
Pa(w,V),
(51)
((N((M)WW((0)
M212) k(2) (u, (111)(u,,))
Σ
Pa(u, w),
(52)
wENg(v)nN1(e)
respectively. Here & takes 1 or 2. We notice that if d(u, k with k 1,2,
Wa(u, v) = ] ( (1 (u, + M (u, v) + M2 (u, v) + Idlu.)) + deg(v)))
(53)
because the RHS of 53 is exactly 1 Emexsia)) W2(u, + EmeNi(a) W2(w,u)) Therefore, for distance-k tuple (u, v) where = or
2
Ps(u,v) W)( Id(un)= deg(v)
(54)
function of M2) M M2 and (()) v). and thus can be assigned (12) v) by
choosing proper HASH (2) functions. After g assigns ((2) (u, v) (u v) for those (u, v) with d(u, v) = or d(u, v) 2, then stops updating colors for any tuple from the third iteration. is now clear that y satisfies the condition stated in the lemma.
n
Lemma C.11. There exists a 2-DRFWL(2) test q such that for any graph G E G and for any node VG, q assigns
(v,
(55)
for some integer T >> 2.
Proof. This lemma follows from Theorem encompasses that of I-DRFWL(2) tests.
4.3 and the fact that the update rule 2-DREW((2) tests
Lemma C.12. There exists 2-DRFWL(2) test such that for any graph G E G and for any 2-tuple vu E V& with d(u, v) = 1 or d(u, v) = 2, assigns
W(T v) P)(
(56)
for some integer T >> 3.
Proof. A 4-path starting and ending at is 4-walk
with y, u +
2 # x, + and * v. We will calculate Pa (u, v) as following: first define
(2,((u,) v)
Σ
Pz(u, v) Pzl,,.)
(57)
24

---

It is easy to see that (2, 2) gives the number of 4-walks u - + + - v with only constraints u # y and y & Therefore,
(u u) = (2,((,,) #(a) #(b) - (c) + #d),
(58)
where # # (b). #c)) and #(d) are the numbers of four types of 4-walks illustrated in Figure 5a
5b 5c and 5d respectively. They correspond to setting u = 2, i v, and both setting and x = u in the 4-walk + x + y - - respectively, while keeping u # and # c.
Now, it is not hard get the following results,
#(a) (u,v)E&c (2Ca(u) - Pa(u, v)),
(59)
#(b) (U,))EE (2Cs(1) Pe(u, v)),
(60)
#(c) E (deg(x)) 2),
(61)
=ENG(
# (d) ((c.))Ee,PP(u,0))
(62)
We will briefly explain (59
62 in the following. The contribution from (59)
60 and 62 only
exists when u and v are neighbors, which accounts for the [(,,)eEE factor. For # (a), if we allow
v = y, then the count is simply Ca(u) times (because two directions of 3-cycle that passes u are counted as two different walks); the contribution of counts from the additional #(d), and is P2(u, v), as long as (u, v) E Eg. A similar argument applies to #(b). Determining #(c) and (d) is easier and the calculation will not be elaborated here.
case is exactly
Combining the above results, we can give formula for Pa (u,v).
Pi(u,v) = u2, -
E
(deg(æ) - 2) (a, (2Cg(u) + 2C3(v) 3P2(u, v)).
(63)
Given the explicit formula 663). we now construct y as follows: at the first iteration, y chooses proper POOL k(1) and H (1) functions (0 < i,j,k & 2) such that
arbitrary,
if d(u, e) = 0, if d(u v) 1, if d(u v) = 2.
(u,0),
(1, P2 v) deg(u) deg(v)), (2, Pu v),, deg(u) + deg(v)),
(64)
From Lemmas C.7 and C.9
this is possible. At the second iteration, we let
Σ
(65)
wEAG(W)
where 1 & i & and
Dı1(u,
Σ
((de((u) + deg(w)) + (deg(w) + deg(v))),
(66)
(ENI(W)
(u, v) = (N)(4) (VN)
(67)
for every (u, v) with d(u. u) d(u, u) 2. Notice that 665 66 and 67 can be calculated by an iteration of 2-DRFWL(2) with proper POOL A(2) functions, where < i,j, h < 2. Therefore, we assert that
1 - Du, -(2 deg(u) + deg(r)
Σ (v)
(deg(x)- 2)
Nu( v)
(68)
2
can be calculated by an iteration of 2-DRFWL((), with proper POOL, k(2) and HASH (2) functions,
1 < i < 2. We now ask g to assign
(1 (u, - {
Ca(u),
if if v) 0, if if v) = 1, if d(, v) = 2, (69)
Pz(u,u), (ee(()V)oo - 2), Eisise Pij (u, (de - 2), EisiJez P,, 1)
25

---

at the second iteration. From the above discussion and Lemma C.11 this is possible. At the third iteration, gathers information from (69) and assigns W = (u, v) for those (u, u) with d(u, v) d( u, v) 2, using formula (63): since we already have all the terms of (63) prepared in (69) (notice that Eig. (2, - 22,2(u. u, v)), is easy to see that Pa(u, v) can be calculated
by an iteration of 2-DREWL(2) with proper POOL, k(3) and HASH functions, & i, k & 2. We then ask to stop updating colors for any tuple from the fourth iteration. Now q satisfies the condition stated in the lemma.
by
Lemma C.13. There exists a 2-DRFWL(2) test q such that for any graph G E 9 and for any 2-tuple (u, E V with d(u,v) = or d(u, v) 2, assigns
W() v) o)(
(70)
for some integer T > 3.
Proof. Following the notations in the proof of Lemma C.12
we have
Wa(u, v) = W2 (2,( 2) + #(u x -
+ # + -- --
(71)
where ((u + x +
+ v) is the number of different ways to walk from u to a neighboring node v, then back to u, and, through another neighboring node 2, finally to (x, 2, v can coincide with each other). The number #(u + +- v) can be interpreted analogously. It is easy to
see that
# + r + v) = deg (u) P2(,)) v), #(u x x + v) = deg v)) P2 v),
(72)
(73)
for d(u, v) = or d(u, v) = 2. Therefore,
W Wi(u, v) W2,(n, v) (deg(u) + Pa v).
(74)
From Lemma C.12 there exists 2-DRFWL(() test 9 such that g assigns (2 (u. P2. (u, v) for (u, v) with di u. v) = 1 or d(u, = 2. Moreover, from Lemmas C.7 and C.9 there exists another 2-DRFWL((2) test g' such that q' assigns ( v) = (deg(u) + deg P2 u), for d(u, v) = or d(u, (., 2)
Synthesizing the colors that g and g assign to (u, v) respectively, it is easy construct 2- 2-DRFWL(2) test that assigns W3)) (u, v) = Wa (u. v), where d(u, v) 1 or d(u, v) = 2. We then let it stop updating colors for any tuple from the fourth iteration to make it satisfy the condition stated in the lemma.
In the following, we denote (u( as the number of k-paths that starts at a node u, and (x) as the number of k-walks that starts at a node u.
Lemma C.14. There exists 2-DRFWL(22) test for any k 2 such that for any graph G G and for any node u E Vg. q assigns
Wl,),,, = Wk(u),
(75)
for some integer T.
Proof. We prove by induction. When == =1 1, (u) = deg(u), and by Lemma C.8 the conclusion is obvious. Now we assume that for le there exists 2-DRFWL(2) test such that q assigns
W(T) (u, u) We(u), Vu E Va,
(76)
for some integer T. Then, at the (T + 1) iteration, we ask
(dog(u), (w,) w(T) u) W(T) (e, arbitrary,
if d(u, v) O, if d(u, v) 1, if d(du,)) = 2.
W(T+1((u,)) (u.
(77)
At the (T + 2)-th iteration, we ask
W(T+2) (u, u)
Σ
W(T+1) deg(u) (u,
(78)
(a))(a)
26

---

for every distance-O tuple (u, u) E Vg It is easy to see that
w(T+)(u,
E We(o). vENI(a)
(79)
Therefore, W(T+2) (u, u) u) = We+1(u), and the induction step is finished. We then assert that the lemma is true.
Lemma C.15. There exists a 2-DRFWL(2) test 9 such that for any graph G E 9 and for any node Va, q assigns
( CC(
(80)
for some integer T >> 3.
Proof. From Lemma C.10 there exists a 2-DRFWL(2) test such that q assigns W(T) v) = (1, u) for some integer T > 2, for any graph G g and any 2-tuple (u,v) Va with d(u, 0) = 1. Cu(u) can be calculated from C,,(U, u) another iteration.
Lemma C.16. There exists a 2-DRFWL(2) test q such that for any graph G 9 and for any node E VG, assigns
= (4,
(81)
for some integer T 2 4.
Proof. From Lemma C.12 there exists 2-DRFWL(2) test such that q assigns W (u, v) C1,( v) for some integer T > 3, for any graph d(u,v) = 1. (u( can be calculated from C,, 2) in another iteration.
9 and any 2-tuple (u, Vi with
O
Lemma C.17. There exists a 2-DRFWL(2) test 9 such that for any graph G E 9 and for any node E VG, q assigns
(w (C)
(82)
for some integer T > 3.
Proof. By the first equation (2).
CCi(u)=
1
Σ
(C)(e,u)
2 eENi(u)
1
Σ
Σ
(P2(2,0-1 -1)
2
vENi(u) (NN
1
Σ
Σ
(P2(z + Pa(u,x) -1)
2
(E)
(w)N
Σ
Σ
P2(u,z)
2
(u) DEN (w)
1
Σ
Σ
(Pa(z,v) + Pa(u, - 1)
2
vENi(u)
1)
Σ
P2(u,x)
Σ
(83)
(M)
(M
Now, using Lemma C.7 CC (u) can assigned by a 2-DRFWI.(2) test to W(T) u), for some integer T > 3 and for all nodes VG.
D
27

---

(t)
(a) 6-cycle with and u on meta-positions. The number of such 6-cycles is exactly C2,(uu,)) v). We require t x,, v
(b) Setting ir, the count the substructure is (b)
(c) Setting y, the count of substructure is #(c)
(d) Setting the count the substructure is #())
Figure 6: Illustrations accompanying the proof of Lemma C.19 In all subfigures, it is assumed that W x + y > is 4-path and - - 2-path.
Lemma C.18. There exists 2-DRFWL(2) test g such that for any graph G 9 and any node u E Va, assigns
W (T),
(84)
for some integer T 4.
Proof. We first calculate TRi (u, v) as following,
(u, Σ
P3(2,u)
Σ
(P2(u,2) 1) Pa(u, ()2,,,) -1).
(NNi(
(85)
Therefore, by the first equation of 34
(u) = 2
Σ
(u,
vENi(a)
1
Σ
Σ
(Ps(u,2) + Ps(z, v))
vENilu) (uNi(u))M
1
Σ
Ps(u,2)
Σ
2
zENi(u)
(ENI(W))
E1 1
Σ
(Pa(u2) 11)
E
2
*ENi(u)
(ENG(
1
Σ
P2(u, v) (P2(U,)) 1).
(86)
vENi(u)
By Lemmas C.7 and 10 TR, (u) can be assigned by a 2-DRFWL(2) test W(T) (u, u), for some integer T and for all nodes E VG.
Lemma C.19. There exists a 2-DRFWL(2) test 9 such that for any graph G 9 and for any node E VG, assigns
((T) -C(u),
(87)
for some integer T > 5.
Proof. We first try to calculate (u, v), which is shown in Figure 6a (If the 6-cycle is thought to be a benzene ring in organic chemistry, then u and a are on meta- pestapposiiions) It is easy see that
Co(u)
1
Σ (EV)(()))
C2a(u,e) Σ C2,((,,)) vENi(M)
(88)
28

---

We calculate C2,a(u, v) as following,
C2, Pa(u, P),, u) #()) #(c) #(d),
(89)
where #(b), (c) and #(d) are the numbers of substructures illustrated in Figure 6b 6c and 6d respectively. In those figures, we always assume that + + + + + v is a 2-path. Since every 4-path + I + + - v and every 2-path u + { + with + z, t + y and + contribute one count C2, v). is clear that (89) gives the correct
is 4-path and
number C2 v).
We now calculate #(b), # (c) and # For #(b). we have
#(b)
Σ
Pa(x, v) # u y) (b, u
(90)
Here, # (b, = 3) #(b, 2) is the count of substructure obtained by coalescing nodes u, y U, in Figure 6b while keeping y + v and x + 2. It is easy to see that
#(b, y) Pa(u, u) (P2 v) 1),
(91)
#(b, u = 2) = -d(
Σ
(1)(ux)) - 1)).
(92)
xEM(())
The count (d) can be calculated analogously, and we summarize the results below.
#(b) + #(d) =
Σ
(Pa(z, + Pa(u, - 2P, (P((,,,))) -1)
[d(x,))=1
Σ
(P2(u, + P2 2).
(93)
By Lemmas C.7
C.10 and C.12 there exist 2-DRFWL(2) tests that assign the numbers P2(u, u)) Pa v) and #(b) + ((d) to W(T) (u, v) respectively, for some integer T 4 and for all pairs (u, v) with d(u, v) = or d(u, v) = 2. Therefore, both
Pa(u, P), (w)
Σ
Ps(u, P((u, vENs(u)
Σ
and
Σ VE
(#(b) + #()) +
Σ (#(b) #()) (EN2(u)
can be assigned by a specific 2-DRFWL(2) test q to W(T) (u, u) for some T > 5 and for all nodes To prove the lemma it now suffices to show that
Σ #(c)
#(c)
(M)
(
can be assigned by 2-DRFWL(() test to (T) u) for some T > and for all nodes u. We calculate #(c) as following.
#(c)= Σ DEN((W)NN10
P2(2,)))((2,0) - #(c, =) -(c x = v) #(c, x = 2)
2, = v)). #
(94)
Here #(c, 2) is the count of substructure obtained by coalescing nodes in Figure 6c while keeping x * v. The counts #(c, x = v). #(c, x = 2) and #(c, = 2, x v) can be understood analogously, but one needs to notice that when counting #(c, x = u) we keep * z. We have
#(c.u 2) Ld(u.))=1
Σ
(P2(u,2) 1),
(95)
#(c, v) = +Cd,.))=1CC(((,,
(96)
#(c, u = 2, v) -I((,,)==1 (2(
(97)
29

---

and
Σ
=
E vEAa(w)
=) 2)
(98)
VEAT (w)
By Lemmas C.7
C.17
C.18 after summing over all nodes (u) (V) each of the terms
in (94) can be assigned by 2-DRFWL(2) test W u). for some > 5 and for all nodes Therefore, we have finally reached the end of the proof.
We are now in a position to give the proofs for Theorems 4.4 4.5 4.6 and 4.7
We restate Theorem 4.4 as following.
Theorem C.20. 2 2-DRFWL(2) GNNs node-level count 2, 3, 4-paths.
Proof. By Lemma C.5 it suffices to prove that for each k: 2, 4, there exists a 2-DRFW1.(2) test q such that for any graph G and for any node u E Vc. assigns
W(T) u) Px(u),
(99)
for some integer T.
In the following proofs, we no longer care the exact value of T; instead, we are only interested in whether graph property can be calculated by 2-DRFWI.(2) test, i.e. there exists finite integer T and subset of 2-DRFWL(2) colors (for example, W(T) (u, u), Ve for node-level properties, or W(T) (u, v), d(u, v) & 2 for pair-level properties) that the subset of 2-DRFWL(() colors gives exactly the values the graph property, at the T-th iteration.
For h: 2,
P2(u)
Σ P((u,)+ vENI(u)
Σ P2(u,v). vEN2(u)
(100)
But by Lemma C.7 there exists 2-DRFWL(() test q and an integer T such that (39) holds for all pairs (u, v) with d(u, v) or d(u, v) Therefore, at the (T + 1)-th iteration, q can assign W(T+1) (u,u) (2( using (T0)).
For = =3
Ps(u)= = Σ P)(u,v)+
Σ Pa(u,o)+ Σ Pa(u,v). .ENa(u)
(101)
vENI(u)
vENs(w)
Using Lemma C.10 and a similar argument to above, the first two terms of (101) can calculated by 2-DRFWL((2) test. For the last term of (10I), notice that
Σ Ps(u,))=
Σ W)(u,v)
vENa(N)
veNs(w)
-W(u)) Ws(u,u)
E Ws(uv))
Σ Wa(u,v). vENs(u)
(102)
(ENi(u)
Wz(u) can be calculated by 2-DRFWL(2) test. From the proof of Lemma C.10 one can see that W3(u, v) can calculated by a 2-DRFWL(22) test, for d(u, v) = or d(u, v) = 2. Therefore, the last two terms of (122 can also be calculated by a 2-DRFWL((2) test. Since Wa (u, u) 2C²(u), ( it can be seen from Lemma C.11 that this term can also be calculated by 2-DRFWL(2) test. Therefore, conclude that EoeNs()) Pa v), thus Pa(u), can be calculated by 2-DRFWI((2) test.
By Lemma C.14
For 4,
Pa(u) Σ Pa(u,)) Σ Pa(u,v)+ Σ
Pa(u, Σ Pa(u,)). (103)
(EN vENs(a)
vEN((w)
vEN((1)
30

---

Using Lemma C.12 and a similar argument to above, the first two terms of (033 can be calculated by a 2-DRFWL((2) test. Like in the le 3 case, we treat the last two terms of [03 as following.
E P)(u,v)+ + E vEAS(u)
P)(u,))=
E
Wa(u,0) +
Σ
Wi(u,v)
PENa(u)
vENS(M)
vEN((a)
Wa(u)
Wa(u,u)
Σ
W4(u,
E
Wa(u,
(104)
(EN((M)
(EN2(N)
By Lemmas C.13 and 14 the terms (u))), EveNi(M) W4
( (u, v) and EveNa(a) W4(u, v) can be
calculated by 2-DRFWL((2) tests. Moreover, is easy to verify that
Wa(u, u) (C) (deg(u))² + P2(u).
(105)
Therefore, by Lemmas C.7
and C.15 (a( u) also be calculated by 2-DRFWL((2) test. Summarizing the results above, we have proved that Pa (u(u) can be calculated by a 2-DRFWI((2) test.
C.8
We restate Theorem 4.5 as following.
Theorem C.21. 2-DRFWL(2) CNNs can node-level count 3,4, 4, 5, 6-cycles.
Proof. By Lemma C.5 it suffices to prove that for each 3,4, 5, 6, C&(u) can be calculated by
2-DRFWL(2) From Lemmas
C.1I C.15 C.16 and C.19 the above statement is true.
We restate Theorem 4.6 following.
Theorem C.22. 2-DRFWL(2) GNNs can node-level count tailed triangles, chordal cycles and triangle-rectangles.
Proof. By Lemmas C.17 and C.18 and using similar argument above, is easy to prove that 2-DRFWL(2) GNNS can node-level count chordal cycles and triangle-rectangles. To see why 2- DRFWL(() GNNs node-level count tailed triangles, only need give 2-DRFWI((2) test that assigns
(T, u) C'tailed triangle, u, G), Yu E VG.
(106)
for some integer T. Actually, we have
C'tailed triangle, G) = Σ
(Ca(u) P2(u,))).
(107)
vENi(u)
or in a symmetric form, C(tailed triangle, u. G)
Σ (Cs(u)+Cs(0 Pa(u, C3(u)deg(u).
(108)
(E)
Using this formula, along with Lemmas C.7
C.8 and C.1 it is straightforward to construct the
2-DRFWI(2) test & that satisfies (10)). as long as > Therefore, 2-DRFWL(2) GNNs can also node-level count tailed triangles.
We restate Theorem 4.7 as following.
Theorem C.23. 2-DRFWL(2) GNNs cannot graph-level count more than 7-cycles or more than 4-cliques.
Proof. The theorem is direct corollary of Theorem 3.2 In the remark at the end of Appendix B.2 we have shown that no d-DRFWL(2) test can distinguish between two k-cycles and a single 2k-cycle, as long as l: > 3d + 1. For d = 2, we assert that no 2-DR test (thus no 2-DRFWI((2) GNN) can distinguish between two k-cycles and a 2k-cyele, as long k 2 Therefore, 2-DRFWI(22) GNNs cannot graph-level count more than 7-cycles.
31

---

Moreover, Theorem 4.2 of [56] states that for any k > 2, there exists pair of graphs with different numbers of + 1)-cliques that FWL(k - 1) fails to distinguish between. Therefore, we assert that FWI.(2) cannot graph-level count more than 4-cliques. By Theorem 3.2 the 2-DRFWI.(2) tests (thus 2-DRFWI((2) GNNs) are strictly less powerful than FWI(2) terms of the ability to distinguish between non non-isomorphic graphs. Therefore, 2-DRFWL(2) GNNs cannot graph-level count more than 4-cliques.
C.3 Proof of Theorem 4.8
Before proving the theorem, we state and prove series of lemmas. Lemma C.24. There exists a 3-DRFWL(2) test q such that for any graph G E G and for any 2-tuple b,, V with d(u, v) & 3, 9 assigns
(w,) P)(u,0),
(109)
for some integer? T.
Proof. If & v) & 2, the result follows from Lemma C.10
since 2-DRFWL(2) tests constitute
subset of 3-DRFWL(2) tests. If d(u, v) = 3, then equations (50) 54) still hold (with the value of k changed to 3), giving rise to
Ps(u, v) u)
Σ
P2(w, v) +
E
Pa(u, w) d(u, v) 3.
(ENi(u))Wa(v))
#ENa(M)rWi()))
(110)
The RHS (10 obviously calculable by 3-DREWL(2) tests. Therefore, the lemma holds.
Lemma C.25. There exists a 3-DRFWL(2) test q such that for any graph G E G and for any 2-tuple
vu,v) V2 with & d(u, v) & 3, q assigns
(u, = Pa(u,e),
(111)
for some integer T.
Proof. If & d(u, v) & the result follows from Lemma C.12 If d(u, v) 3, then equation (63 still holds, giving rise to
Pa(u, (2, Σ (u, d(u,v) 3.
(112)
161JE2
The definitions of v), and (2, v) are given in 57 and 65 point out that
respectively. In particular,
ptj (2)(
Σ
Pa(u, w) P2 v)
is calculable by 3-DRFWL(22 tests, for any 1 & i,j < 2 and for d(u, v) = 3. Therefore, the lemma holds.
Lemma C.26. There exists 2-DRFWL((2 lest q such that for any graph G E 9 and for any 2-tuple vu V& with & d(u, v) & 2, q assigns
W(To) T(u,u).
(113)
for some integer To-
Proof. The lemma follows from
T T(u, v)
Σ
Pa(w, v) - Id(u,))=1 Pa(u, v),
(114)
(aNT(a)
and Lemma C.7
32

---

Lemma C.27. There exist two 2-DRFWL(2) rests q1, 92 such that for any graph G & G and for any 2-tuple (u, v) V with & d(u,v) < q1 92 assign
W W CC1 (C, W. CC2(u,
(115)
respectively, for some integers T1 and T2.
Proof. The existence of follows from the proof of Lemma C.17 can count CC,(U, v), notice that
To see why 2-DRFWL(2) tests
1
CC2(u,
Pa(u, P=((u,))P2((u.))) 1),
(116)
and the result follows from Lemma C.7
Due to the relations (32) and (33 we assert that 2-DRFWIL(2) tests can also node-level count CC1 (u)
and (u)
Lemma C.28. There exist three 2-DRFWL(2) tests q1, 92 and such that for any graph G E G and for any node VG. Q1. 92 and q3 assign
(u, TRi (u),
W (T)) W (u,u) TR2(u), ( TRs(u),
(117)
respectively, for some integers Tı. T2 and Ty.
Proof. From the proof of Lemma C.18 we see that 2-DRFWL(2) tests can count TR, (u, v). By 34 2-DRFWL(2) tests can count T R, (u) and (R). We only need to prove that 2-DRFWL(2) tests can count T (u)).
Notice that
TRy(u)=
E
TR2(v,
vENi(a)L(2(44)
Σ
(P((u.))1))(uub)))
(c).
(118)
(a)
Therefore, by Lemmas C.7 C.26 and
C.27 the lemma is true.
Lemma C.29. There exists a 2-DRFWI(() test such that for any graph G E G and for any 2 2-tuple vu,v) V& with d(u, v) < 2, q assigns
(u,) C2,3lu.
(119)
for some integer T.
Proof. Notice that
C2.( Pa(u, Pa(u, v) T(u, v) T(u, u).
(120)
Therefore, the lemma follows from Lemmas
C.7
C.10 and C.26
Now, we turn to proving Theorem 4.8 We restate the theorem following.
Theorem C.30. For any d > 3, d d-DRFWL(() GNNs can node-level count 3, 4, 5, 6, 7-cycles, but cannot graph-level count any longer cycles.
Proof. We first prove the negative result: for any d > 3, d-DRFWL(2) GNNs cannot graph-level count k-cycles, with > 8. This is because in terms of the ability to distinguish between non- isomorphic graphs, d-DRFWL(2) tests (and thus GNNs) strictly less powerful than FWL(2), for any d, as shown in Theorem 3.2 Nevertheless, even the more powerful FWL(2) tests fail to graph-level count k-cycles with A 8.
Next, we will prove the positive result. Notice that the update rule of + 1)DFFFLI(( GNNs always encompasses that of d-DRFWL(2) GNNs. Therefore, for any d > 3, the node-level cycle
33

---

counting power of d-DRFWL(2)) GNNs is at least strong as that of 2-DRFWL(2) GNNs. This implies that d-DRFWL(2) GNNs can node-level count 4, 5, 6-cycles for any >
For the same reason, to prove that d-DRFWL(22 GNNs can node-level count 7-cycles for any d > 3, it suffices to prove that 3-DRFWI.(2) GNNs do By Lemma C.5 this reduces proving the existence of a 3-DRFWL(2) test such that for any graph G E G and for any node E Ve, assigns
(w,) C7()),
(121)
for some integer T. We try to calculate (7)) via
Cr()= Σ Ca,alu,
(122)
v:lEd(u,vEG3
We assert that
C3, P3(u, v)
# =((()))))((( ((a)
#(1).
(123)
where # (a), #b)..... #()) refer to numbers of the substructures depicted in (a), (b), .... ()) of
Figure respectively. Since Ps(u, v) and Pa (u v) are calculable by 3-DRFWL(2) tests (by Lem-
mas C.24 and ).25), it now suffices show that 3-DRFWL(2) tests can calculate the counts #(a) ......... #()), summed over all v with & d(u, v) <
(c)
(h)
(k)
(I)
Figure 7: The twelve substructures whose counts should be subtracted from Ps(u, v) Pa v) to get (u,
For the rest of the proof, we express each of the counts # #(), (1) (after summing over {u E Va & d(u, v) & 3}) in terms of numbers already known calculable by 3-DRFWL((2) tests. Since the enumeration procedure rather tedious, we directly provide the results below.
#(a)
Σ
Σ
C2s(w,
wi w.gdd 22 (wWN
Σ
Σ
C2s(w,r)
we
34

---

-Cs(u))
(R),
(124)
Σ
#(b)
Σ
Σ
P2(u, P)W,)
E
E
P2(u, w) (P2(U, w)
vEN)(w) (
Σ
E
Pa(w, (P:((u, v) - -1)
vEVi(u) WE (
CCi(u)
(CC2(u)
4T
(u) TR)(
(125)
E
#(c)
E
E
P2(u, w/u,w)P2(ur e) (P,
2. WEN (NM
Σ
Σ
Pa(u, u) (P2( v) v) -1)
(NN) Rg
#: (d(((,,)) -CCC(())CCC((
(126)
Σ
#(d)
Σ
Σ
81 $3
1: wl ((NN())
Σ
Σ
Pa(u,
1)
e md 33 (EN2(v)
Σ
E
(P
VEN.(W) (v) (
4CCi(u) - (T),
(127)
Σ
#(e) E
E
Ps(u, (.)
o: 33
vn vdl 62 we WE (ENi(W)
2 Σ
Σ
Pa(u, v)(P((w v) - 1)
(w)(()) (CC)(u) 2CC2(u) - TR2(u) 27 Rs(),
(128)
Σ
#(f)
2 (W))(i) C2,(u,
Σ
Σ
Σ
Σ
C2)(u,
wl (a
4Cs(u) - (u)
(129)
Σ
#(g)
Σ
Σ
P2(u, w) P2(,))
vi 2 (WNN
Σ
Σ
Pa(u, w) (wW,w,))
wl<d(a,)) (2N 20C2(w)
Ctailedd triangle, u, G),
(130)
Σ
#(h)
Σ
Σ
T(,
vl
(wor (w)
Σ
Σ
T(u,w)
# oi 33 (())) 4C(iieled triangle, u, G),
(131)
Σ
#(i) (R)
(132)
Σ
#()= = Σ Σ
Pa(w, u)(((), v) -1) - (w),
(133)
(u) WEA, (w))
35

---

Σ
#(k)=
Σ
E
Pa(u, P2
vl WEN (w)N
Σ
E
Pu(u, w) P2(,,)
" (i 33 WENi
Σ
T(u,u) (Cs( 2),
(134)
:led(u.re2
Σ
#(1)= = TRa(u).
(135)
#: (
Combining the above results, we conclude that the theorem holds.
D Comparison between d-DRFWL(2) and localized FWL(()
As mentioned in Section 5 of the main paper, d-DRFFW.(2) can be seen as sparse version of FWL(2).
Another representative of this class of methods (adding sparsity to FWL(2)) is the localized F2L(2).
proposed by Zhang al. [58]. In (58), two instances of localized FWL(2) are provided. i..., LFWL(2)
and SLFWL(2). Different from d-DRFWL(2), both LFWL(2) and SLFWL(2) assign a color (u, v) to every 2-tuple (u, v) V2- for any given graph G. Therefore, their space complexity is equal to that of FWL(2), namely ((n²). The major difference between LFWL(2)SLFWL(2) and FWL(2) is in their update rules. Similar to FWL(2). both LFWL(2) and SLFWL(2) update W (u, v) using multiset of the form (WW,, v), W (u, w)) However, for LFWL(2), we restrict w to be in (()); for SLFWL(2),
be in (( (u). Since restricting the range of reduces the multiset size from (n)) (as in FWL(2)) to Oddgg, the time complexity of LFWI(() and SLFWI(() is On2 deg), which is usually much lower than the ( time complexity of FWL(2).
restrict
We now compare d-DRFWL(2) with LFWL())SLFWL()) in terms of discriminative power. We have the following results:
No d-DRFWL(2) with fixed d value can be more powerful than LFWL(2) or S2FWL(2). This is because for any finite d, we can construct graph pairs that are separable by LFWL(2) and SLFWL(2) but not separable by d-DRFWL(2). One of such graph pairs can be two (3d + 1)-cycles and one (6d + 2)-cycle, between which d-DRFWI((2) cannot discriminate (as shown in the proof of Theorem 3.2p. However, since both LFWIL(2) and SLFFL((2) can calculate distance between every pair of nodes (following a procedure con- structed in the proof Theorem (.2). it easy for LFWL(2) or SLFWL(2) to distinguish between the aforementioned pair of graphs, since they have different diameters.
With sufficiently large d, d-DRFWL(2) is not less powerful than LFWL(2) or S2FWL(2). This is because for graphs with diameter & d, d-DRFWL(2) has equal power to FWL(2). Since it is shown in (58) that there exist graph pairs separable by FWL(2) but not separable by LFWL(2) or SLFWL(2), once the value of d grows larger than the diameters of such graph pairs, those graph pairs can separated by d-DRFWL((2) but not LFFI.(() or SIFFWL(2).
Therefore, for sufficiently large d, the discriminative power of d-DRFWL(2) is neither stronger nor weaker than LFWL(2) or SLFWL(2). However, it remains unknown the relation in discriminative power between LFWL(2)SLFWLL2) and d-DRFWL(2) with practical d value, such as d = 2 or d = 3. Are d-DRFWL with those smaller d values less powerful than LFWLQ2SLFFL.)) or are they incomparable? We leave this question open for future research.
E Experimental details
E.1 Model implementation
Let G be graph with node features fu, u E VG and edge features euv, {u, Eg. In most of our experiments, implement d- d-DRFWL(2) GNNs following: we generate (110) as
36

---

(fN LINI (Fu + Sur Gao), LIN fe);
if d(u v) 0, if d((u v) = 1, if d(uu v) k 2,
h A0
(136)
where LIN,, i 0, d are linear functions. When node and edge features absent, we assign identical values to hwo with the same d(u, u).
The migk and _ functions in 10 and 11] are chosen
migh
(t) (t-1),
hl ReLU (LINO)) (nle + n)
(137)
[n(o=1,
(2 (2b(()) Oogise//
(our
(t-1) + MMP
&
(1+
Σ K
LIN His.83
aue (15800)
(138)
0E
where LIN(() in (137 is a linear module whose parameters are shared among all i, ls combi- nations; LIN (1)
Kij.& in (138) is a linear module whose parameters are shared among all i, that form the same multiset ji.j, kB (for example, the contributions a , and a are all linearly transformed by an identical LIN(!) 81,2.23 ); MLP(() is multilayer perceptron, and can depend on k; can be a constant or a learnable parameter. After the d-DRFWL(2) GNN layers, we apply a sum-pooling layer
R 1 (u,v) v& and 0 < v) < d3)
Σ
(139)
DEd(u,o)
and then a final MLP.
We point out that our implementation d-DRFWL(2) GNNs has the property 1 1100 for any
u, E Vo with 0 & d(u, v) & d, and for any / = 0, 1,....77 T. We call an instance of d-DRFWL(2) GNN symmetrized, if it preserves the above property. is obvious that symmetrized d-DRFWL((2) GNNs only constitute a subspace of the function space of all d-DRFWL.2) GNNs.
Nevertheless, remark that for the case of 2, symmetrized 2-DREWL(2) GNNs have equal node-level cycle counting power to 2-DRFWL(2) GNNs. Actually, in the proofs of Lemmas C.7-
C.19 and Theorems 4.4 4.6 (see Appendix - details), all the 2-DRFWL((2) tests we constructed have the property ( (u, v) W (v, u), for any u, Va with 0 & d(u, v) and any I; on the other hand, it is easy to establish the equivalence between such kind of 2-DRFWL(2) tests and symmetrized 2-DRFWL((2) GNNs. Similar facts be verified for d-DRFWLC2 GNNs with d = or d = 3. Therefore, at least for all our experiments (where d & 3), our symmetrized implementation of d-DRFWL(2) GNNs does no harm to their theoretical cycle counting power, although the model is greatly simplified.
E.2 Experimental settings
E.2.1 Substructure counting
Datasets.
The synthetic dataset is provided by open-source code of GNNAK on github The
node-level substructure counts calculated by simple DFS algorithms, which implement in C language. (This part of code is also available in our repository
Models. Implementations of baseline methods (MPNN, ID-GNN, NGNN, GNNAK+, PPGN
and (2-GNN) follow (33. For d-DRFWL(2) GNN (d = 1,2,3), we use 5 d-DRFWL(2) GNN layers. In each layer (numbered by 1, ... ., 5), MLP k is 2-layer MLP, for k 0, l,..,,.d d. (Sec (38)
for the definition of MLP(() ,) The embedding size is 64.
37

---

Training settings. settings, with patience 10. decay factor 0.9 and minimum learning rate 10-5 We train our model for 2,000 epochs. The batch size is 256.
We use Adam optimizer with initial learning rate 0.001, and use plateau scheduler
E.2.2 Molecular property prediction
Datasets. The QM9 and ZINC datasets are provided by PyTorch Geometric package
[22] The
ogbg-molhiv and ogbg-molpcba datasets are provided by Open Graph Benchmark (OGB) rewrite preprocessing code for all four datasets.
31 We
The raining/validation//ee splitting for QM9 is 0.8/0.1/0 The training/validatiioneest splittings for ZINC, egbg-molhiv and ogbg-molpeba are provided in the original releases.
Models. For QM9, we adopt a 2-DRFWL(2) GNN with 5 2-DREWL(2) GNN layers. In each layer (numbered by t = .................... 5), M is 2-layer MLP, for k = 0, 2. The embedding size is 64.
For ZINC, we adopt a simplified version of 3-DRFWL(2) GNN, which only adds terms 313 aur and 2231 to the update rules (TO) and (11) of 2-DRFWL(2) GNN. Notice that the adopted model architecture is slightly different from the one described in Appendix E. This is because we observe that including other kinds of message passing in 3-DRFWL(2) GNN does not improve the performance on ZINC. The adopted 3-DRFWL(2) GNN has 6 3-DRFWL(2) GNN layers. In each & is 2-layer MLP, for 6 0, 1, 2, 3. The embedding size
layer (numbered by t 1,.... 6). (LP is 64. We apply batch normalization between every two 3-DRFWL(2) GNN layers.
For agbg-molhiv, we also adopt simplified version of 2-DRFWL(2) GNN; namely, we remove the term 2222 in the update rules of the original 2-DREWL(2) GNN. The adopted 2- 2-DRFWL(2) GNN
has 5 2-DRFWL((2) GNN layers. In each layer (numbered by t 1...., 5), MLP is 2-layer MLP, for 1 = 0, 1,2. The embedding size is 300. We apply a dropout layer with p = 0.2 after every 2-DRFWL((2 GNN layer.
k
For ogbg-molpeba, we adopt a 2-DRFWL(2) GNN with 2-DRFWL(2) GNN layers. In each layer (numbered by i = 1, 2, 3). MLP is a 2-layer MLP, with layer normalization applied after every MLP layer, for A: = O, 1, 2. The embedding size is 256. We apply layer normalization between every two 2-DRFWL(2) GNN layers, and also apply a dropout layer with p = 0.2 after every 2-DRFWL((2)
&
GNN layer.
Training settings. For QM9, we use the Adam optimizer, and use plateau scheduler with patience 10, decay factor 0.9 and minimum learning rate 10-5 For each of the 12 targets on QM9, we search hyperparameters from the following space: (i) initial learning rate E (0.001, 0.002, 0.005): (ii) whether to apply layer normalization between every two 2-DRFWL(() GNN layers (yes/no). We train our model for 400 epochs. The batch size 64.
For both ZINC-12K and ZINC-250K, we use Adam optimizer with initial learning rate 0.001. For ZINC-I2K, we use plateau scheduler with patience 20, decay factor 0.5 and minimum learning rate 10-5; for ZINC-250K, we use plateau scheduler with patience 25, decay factor 0.5 and minimum learning rate 10-5 We train our model for 500 epochs on 12K and 800 epochs on ZINC-250K. The batch size is 128.
For both ogbg-molhiv and ogbg-molpcha, For ogbg-molhiv, we use step scheduler with step size 20 and decay factor 0.5. We train our model for 100 epochs and the batch size is 64. For ggbg-molpcba, we use step scheduler with step size 10 and decay factor 0.8. We train our model for 150 epochs and the batch size is 256.
use Adam optimizer with initial learning rate 0.0005.
Additional experiments
In Appendix we present
Experiments that answer Q4 in Section of the main paper;
Ablation studies on the substructure counting power of 2- 2-DRFWL(2) GNNs;
38

---

Additional experiments that study the performance of d-DRFWL(2) GNNs on molecular datasets;
Experiments that study the ability of d-DRFWL(22 GNNs to capture long-range interactions;
Additional experiments that study the cycle counting power and empirical efficiency of 2-DRFWL(2) GNNs on larger graphs.
F. Discriminative power
Datasets. To answer Q4, we evaluate the discriminative power on three synthetic datasets: (I) EXP [ containing 600 pairs of non-isomorphic graphs that cannot be distinguished by the WI.(1)
test; (2) SR25 [6) containing 15 non-isomorphic strongly regular graphs that the FWL((2) test fails to
distinguish; (3) BREC [11 containing 400 pairs of non-isomorphic graphs generated from a variety
of sources.
For EXP, follow the evaluation process in [59] use 10-fold cross validation, and report the average binary classification accuracy; for SR25, we follow [60], treat the task as a 15-way classification, and report the accuracy. Raw data for both EXP and SR25 datasets are provided by open-source code of
GNNAK on github
For BREC, use Reliable Paired Comparison (RPC) as the evaluation method, following 511 For every graph pair (G, H), the RPC procedure consists of two stages: major procedure and reliability check.
q. The copies G, and H; (i =. 1=.....9 ②) are obtained by randomly relabeling nodes in G and H, respectively. We then apply Hotelling's s 7 test to check whether we should reject the null hypothesis Ho (rrlaael[[(G) - [(H)] = O, meaning that the model f cannot distinguish between G and H.
In the major procedure, we generate q 32 copies H.) of
In the reliability check, we replace H, in each copy (G,, H.) with GT which is obtained by randomly relabeling nodes in G,, for == 1, 1.....9.. We then apply a second T test to check whether should reject the null hypothesis H/ Fe f(GT) O, meaning that the representations of two isomorphic graphs will not deviate too much from one another due numerical errors.
Finally, G and H are considered separable by f iff we should reject Ho but should not reject Hy- The detailed description of the RPC procedure is provided in (1
Baselines. For EXP and SR25, baseline methods are chosen from: (1) Basic MPNNs. These methods have discriminative power upper-bounded by the WL(1) test, and we choose GIN (55), which can achieve WI.(1) expressive power theoretically.
Table 5: Accuracy on EXP/SR25.
Method
EXP
SR25
(2) Subgraph MPNNs. These methods are strictly more powerful than WL(1) but strictly upper- bounded by the FWL(2) test [58]. We choose Nested GIN (59 and GIN-AK+ [60]. (3) Higher-
GIN
50%
6.67%
Nested GIN
99.9%
6.67%
GIN-AK+
100%
6.67%
order GNNs with expressive power equal to FWL(2). We
PPGN
100%
6.67%
choose PPGN 42 and 3-GCN M. (4) Methods with discriminative power partially stronger than FWL(2), e.g.
3-GCN
99.7%
6.67%
P.GNN
100%
100%
I2-GNN [33].
2-DREWL(2) GNN
99.8%
6.67%
For BREC, the complete list of baseline results is given in Table of [51]. We select 3-WL. NGNN, NGNN with distance encoding (DE), SUN (24]. SSWL_P [58] GNN-
3- 3-DRFWL(2) GNN
100%
6.67%
AK, 1-G and PPGN as our baselines.
Models. We evaluate both 2-DRFWL(2) GNN and 3-DRFWL(2) GNN on the three datasets. On all three datasets, adopt d- d-DRFWL(2) GNN with 5 d-DRFWL(2) GNN layers (d = 2 or 3). In each layer (numbered by = 1,..., 5), MT.P(!) & 2-layer MI.P, for k = 0, ...... d. The embedding size is 64 for EXP/SR25, and 32 for BREC.
39

---

Training settings. For both EXP and SR25 datasets, we use Adam optimizer with learning rate 0.001. We train our model for 10 epochs on EXP and 100 epochs on SR25. The batch size is 20 on EXP and 64 on SR25. For BREC, we use Adam optimizer with learning rate 0.0001. We train for 10 epochs and the batch size is 32.
Results. We can see from Table 5 that 2-DRFWL(2) GNN already achieves 99.8% accuracy on the EXP dataset, while 3-DRFWL(2 GNN achieves 100% accuracy. This complies with our theoretical result (Theorem 3.1 that d-DRFWL((2) GNNs are strictly more powerful than WL(1); moreover, 3-DRFWL(2) GNN achieves higher accuracy than 2-DRFWL(22) GNN, verifying the expressiveness hierarchy we obtain in Theorem [.2] Table 5 also shows that both 2-DRFWL(2) GNN and 3-DRFWL(2) GNN fail on SR25 with 1/15 accuracy. This verifies our assertion that d-DRFWL(2) GNNs are strictly less powerful than FWL(2).
Table Numbers of distinguishable graph pairs on BREC.
Method
Basic (60)
Regular (140)
Extension (100)
CFI (100)
Total (400)
3-WL
60
50
100
60
270
NGNN
59
48
59
0
166
NGNN+DE
60
50
100
21
231
SUN
60
50
100
13
223
SSWL P
60
50
100
38
248
GNN-AK
60
50
97
15
222
P-GNN
60
100
100
21
281
PPGN
60
50
100
23
233
2-DREWL(() GNN
60
50
99
0
209
3-DRFWI((2) GNN
60
50
100
13
223
The experimental results on BREC are shown in Table Since the 400 graph pairs in BREC are categorized into four classes-base basic graphs (60 pairs). regular graphs (140 pairs), extension graphs (100 pairs) and CFI graphs (100 pairs), report the number of distinguishable graph pairs in each class, and also the total number. From Table 6] it is easy to observe the expressiveness gap between d-DRFWL(2) and 3-WL (which has equal discriminative power to FWL(2)), and the gap between 2-DRFWL(2) and 3-DRFWL((). This again verifies Theorem 3.2
F.2 Ablation studies on substructure counting
We study the impact of different kinds of message passing in 2-DRFWI((2) GNNs their substructure (especially, cycle) counting power, by comparing the full 2-DRFWI((2) GNN with modified versions in which some kinds of message passing are forbidden. The dataset, model hyperparameters and training settings are the same as those in Appendix E.2.
Table 7: Ablation studies of node-level counting substructures on synthetic dataset. The colored cell means an error less than 0.01.
Synthetic (norm. MAF)
Method
3-Cyc.
4-Cye.
5-Cyc.
6-Cye.
Tail.
Chor. Cye.
Tri.-Rect.
2-DREWL(2) GNN
0.0004
0.0015
0.0034
0.0087
0.0030
0.0026
0.0070
2-DRFWL(2) GNN
0.0006
0.0017
0.0035
0.0092
0.0030
0.0030
0.0070
(w/o distance-O tuples)
2-DRFWI((2) GNN
0.0006
0.0013
0.0033
0.0448
0.0029
0.0029
0.0067
(w/o 222) 2-DRFWL(2) GNN (w/o 2 u 2,12 2211
0.0004
0.0009
0.0852
0.0735
0.0020
0,0020
0.0051
I-DRFWI.() GNN
0.0002
0.0379
0.1078
0.0948
0.0037
0.0013
0.0650
40

---

Results. From Table 7 we see that by removing the term aur in (II (i.c., by forbidding a distance- 2 tuple (u, v) to receive messages from other two distance-2 tuples (u, w) and (w, v)). we make 2 2-DRFWIL(2) GNN unable to node-level count 6-cycles. This complies with our intuitive discussion at the end of Section[athe that such kind of message passing essential for identifying closed 6- 6-walks, and thus for counting 6-cycles.
Similarly, if we further remove au auv and due then 2-DRFWL(2) GNN will be unable count 5-cycles. If a our), due and awv are also removed, the 2-DREWL(2) GNN actually degenerates into 1-DRFWL(2) GNN, and becomes unable to count 4-cycles and criangle-rectanlee (the latter also containing 4-cycle as its subgraph). Finally, we can see from Table 7 that even I-DRFWL(2) GNN can count 3-cycles, tailed triangles and chordal cycles, since the numbers of these substructures only depend on the number of closed 3-walks.
We also study the effect of distance-O tuples in 2-DRFWI.(2) GNN. Removing embeddings for those tuples does not affect the theoretical counting power of 2-DRFWL((2) GNN, but we observe that the empirical performance on counting tasks slightly drops, possibly due to optimization issues.
F,3 Additional experiments molecular datasets
In the following, we present the results on ZINC, ogbg-molhin and
datasets.
Table 8: Ten-runs MAE results on ZINC-12K (smaller the better), four-runs MAE results on ZINC-
250K (smaller the better), ten-runs ROC-AUC results on ogbg-molhiv (larger the better), and four- runs AP results ogbg-molpcba (larger the better). The * indicates the model uses virtual node on ogbg-molhiv and ogbg-molpcba.
Method
ZINC-12K (MAF)
ZINC-250K (MAE)
oghg-molhiy (AUC)
ogbg-molpcha (AP)
GIN
0,103410.004
0.00020.002
77.07 1.49
20.03
PNA
0.088=000011
79.05=1132
28.38
DGN
0.168=00003
79.70=0.97
28.85
HIMP
0.151+0.006
0.036+0.002
78.80+
GSN
0.115+00.012
Deep LRP
77.19 1.40
CIN-small
0.094
0.04410.003
80.05=1.04
CIN
0.079
0.022
0..74
Nested GIN'
0.000
0.029+0.001
78.34 1.86
0..3
GNNAK+
0.000+0.001
79.61 1.19
29.30+0.44
SUN (EGO)
0.003
80.03+0.555
F-GNN
0.083
0.023-10001
0.98
2-DRFWL(2)GNN
0..002
0.005
78.1812.19
20.
F.4 Long-range interactions
In 6.2 of the main paper, we mention that 2-DRFWL(2) GNN greatly outperforms subgraph GNNs like NGNN or I2-GNN on the targets Uo. U, H and of the QM9 dataset, a phenomenon we ascribe to the stronger ability of 2-DRFWL(2) GNN to capture long-range interactions. Actually, a bit knowledge from physical chemistry tells us that the targets Uo, U, H and G not only depend on the chemical bonds between atoms, but also the intermolecular forces (such as hydrogen bonds). Such intermolecular forces can exist between atoms that are distant from each other on the molecular graph (since the two atoms belong to different molecules). However, most subgraph GNNs process the input graphs by extracting k-hop subgraphs around each node, usually with a small k. This operation thus prevents information from propagating between nodes that are more than k-hop away from one another, and makes subgraph GNNs fail to learn the long-range interactions that are vital for achieving good performance on the targets Uo, U, H and G. In contrast, 2-DRFWL(2) GNN directly performs message passing between capability to capture such long-range interactions.
2-tuples on the raw graph, resulting in its
So far, remains an interesting question whether 2-DRFWL(2) GNNs' ability to capture long-range interactions is comparable with that of globally expressive models, such as k-GNNs 44] or GNNs based on SSWL, LFWL((2) or SLFWL(() 588 Those models keep embeddings for all possible k-tuples v E yo (instead of only distance-restriche as fully-connected ones, and presumably have stronger capability to learn long-range dependencies than 2-DRFWL(2) GNNs. We verify this assertion by comparing the performance of 2-DRFWL(2)
ones). In this sense, they treat the input graphs
41

---

Table 9: MAE results on QM9
(smaller the better).
Target
I-GNN
I-2-GNN
I-2-3-GNN
SSWL+
LFWL(2)
SLFWL(2)
2-DRFWL(2)
GNN GNN
0.493
0.493
0.476
0,418
0,439
0.435
0,346
0.78
0.27
0.27
0.271
0.315
0.289
0.222
Shomo
0.00321
0.00331
0,00337
0.00298
0.00332
0.00308
0.00226
Eumoo
0.00355
0.00350
0.00351
0.00291
0,00332
0.00322
0.00225
A
0.0049
0.0047
0.0048
0.00414
0.00455
0.00447
0.00324
R
34.1
21.5
22.9
18.36
19.10
18.80
15.04
ZPVE
0.00124
0.00018
0.00019
0.00020
0.00022
0.00020
0.00017
Up
2.32
0.0357
0.0427
0.110
0.144
0.083
0.156
U
0.107
0.111
0.106
0.143
0.121
0.153
2.23
0,070
0.0419
0.120
0.164
0.124
0,145
G
1.94
0.140
0.0469
0.115
0.164
0.103
0.156
C
0.27
0.0989
0.0944
0.1083
0.1192
0.1167
0.0901
Table 10: Four-runs results Long Range Graph Benchmark. Methods categorized into: MPNNs, Transformer-basee methods, our method.
Method
Peptides-fure (AP 1)
Peptides-struct (MAE J)
GCN
0.5930 0.0023
0.3496 0.0013
GCNII
0.5543 = 0.0078
0.3471 = 0.0010
GINE
0.5498 = 0.0079
0.3547 0.0045
GatedGCN
0.5864 + 0.0077
0.3420 + 0.0013
GatedGCN+RWSE
0.6069 = 0.0035
0.3357 + 0.0006
Transformer+LapPE
0.6326 = 0.0126
0.2529 = 0.0016
SAN+LapPE
0.6384 + 0.0121
0.2683 + 0.0043
SAN+RWSE
0.6439 0.0075
0.2545 0.0012
2-DRFWL(2) GNN
0.5953 + 0.0048
0.2594 + 0.0038
GNN on QM9 with that of 1-2-GNN. 1-2-3-GNN, SSWL+ GNN, LFWL(2) GNN and SLFWL(2)
GNN, among which the first two are proposed by Morris et al. 44 and the others by Zhang et al. We also include the result of 1-GNN for reference.
58
We present the results Table The baseline results for 1-GNN, 1-2-GNN and 1-2-3-GNN are from [44]. For experiments on SSW SSWL+ GNN, LFWL(2) GNN and SLFWL(2) GNN, we implement the three models following the style of PPGN 42]; namely, we use a B x d X 1max X maxax matrix store the embeddings of all 2-tuples within batch, with B being the batch size, d being the size of the embedding dimension, and mmax being the maximal number of nodes among all graphs in the batch.
For each of SSWL+, LFWL(() and SLFWL(2), we use 5 layers with embedding size 64, and apply layer normalization after each layer. We train for 400 epochs using Adam optimizer with initial learning rate searched from (0.001, 0.002]. and plateau scheduler with patience 10, decay factor 0.9 and minimum learning rate 10-5 The batch size is 64. We report the best MAE (mean absolute error) for each target. The experimental details for 2-DRFWL(2) GNN follow Appendix E.2.2
From Table we see that although 2-DRFWL (2)) GNN outperforms all baseline methods on 8 out of the 12 targets, its performance inferior to globally expressive models on the targets Uo. U, H and G. This result implies that the ability of 2- 2-DRFWL(22 GNN to capture long-range interactions is weaker than globally expressive models.
We also evaluate the performance of 2-DRFWL((2 GNN on the Long Range Graph Benchmark (LRGB) (2I). LRGB a collection of graph datasets suitable for testing GNN models' power to learn from long-range interactions. We select the two graph-level property prediction datasets, Peptides-func and Peptides-struct, from LRGB. The task of Peptides-fure label binary classification, and the average precision (AP) is adopted as the metric. The task of Peptides-struct multi-label regression, and the mean absolute error (MAF) adopted as the metric.
multi-
42

---

For experiments on both datasets, we use 5 2-DRFWL(2) GNN layers with hidden size 120. We train 200 epochs using Adam optimizer with initial learning rate 0.001, and plateau scheduler with
patience 10, decay factor 0.5, and minimal learning rate 10-5. _ The batch size is 64. We also list
all baseline results given in [21], including MPNNs like GCN 36) GCNII [33, GINE [30 55 and
GatedGCN [1] well as Transformer-basee
models like fully connected Transformer
49 with
Laplacian PE (LapPE) [9 20 and SAN [38]. The results are shown in Table I0
From Table 10 we see that 2-DREWL(2) GNN outperforms almost all MPNNs. Surprisingly, on Peptides struct the performance of 2-DRFWL(22 GNN even comparable Transformer- based methods (which inherently capture long-range information by treating the graph as fully connected). Therefore, we conclude that although designed capture local structural information, our model still possesses the ability to learn Longrrange dependencies.
F.5 Additional experiments on cycle counting power and scalability
Datasets. To further compare the cycle counting power and scalability of d-DRFWL(2) GNNs (especially for the case of d = with other powerful GNNs, we perform node-level cycle counting tasks on two protein datasets, ProteinsDB and Homology TAPE, collected from [29]. We evaluate the performance and empirical efficiency of 2-DRFWL(2) GNN as well as baseline models such as MPNN, NGNN, I2-GNN and PPGN, on both datasets.
The official code of (29] provides raw data for three protein datasets-""nzyymes vs Non-Enzymes", "Scope 1,75" and "Protein Function". All three datasets contain graphs that represent protein molecules, in which nodes represent amino acids, and edges represent the peptide bonds hy- drogen bonds between amino acids. Each of the three datasets contains a number of directed graphs, which only small portion edges are directed.
We collect the first two datasets from the three and convert all graphs to undirected graphs by adding inverse edges for the directed edges. Since node features (e.g., amino acid types, spatial positions of amino acids) and edge features (e.g.. whether the bond is peptide bond hydrogen bond). The node-level cycle counts are generated by the same method as the one described in Appendix [..21 We then rename the two processed datasets as ProteinsDB and HomologyTAPPI respectively. (The names of the datasets correspond their original .zip file names.)
only interested in cycle counting tasks, remove
Some statistics of the two processed datasets shown in Table I1 We also show the statistics of some other datasets we use in Table 12 From Table IT and Table 12 we can see that the graphs in ProteinsDB and Homology TAPE TAPE datasets much larger than those in QM9, ZINC, ogbg- molhiv, ogbg-molpeba or the synthetic dataset, thus suitable for evaluating the scalability of GNN models.
ogbg-molhiv,
Table 11: Statistics of two protein datasets.
Dataset
Number of graphs Average number of nodes
Average number of edges
ProteinsDB
1,178
475.9
714.8
HomologyTAPE TAPE
16,292
167.3
256.7
Table 12: Statistics of other datasets we use.
Dataset
Number graphs
Average number nodes
Average number of edges
Synthetic
5,000
18.8
31.3
QM9
130,831
18.0
18.7
ZINC-12K
12,000
23.2
24.9
ZINC-250K
249,456
23.2
24.9
ogbg-molhiv
41,127
25.5
27.5
ogbg-molpcba
437,929
26.0
28.1
43

---

Table 13: Average normalized MAE results of node-level counting cycles on ProteinsDB and HomologyTAPP datasets. The colored cell means an enror less than 0.002 (for ProteinsDB) or 0.0002 (for HomologyTAPe TAPE). "Out of GPU Memory" means the method takes an amount of GPU memory more than 24 GB.
ProteinsDB
Homology TAPE
Method
3-Cycle
4-Cycle
5-Cycle
6-Cyele
3-Cyele
4-Cycle
5-Cycle
6-Cycle
MPNN
0.422208
0.223064
0,254188
0.203454
0.185634
0.162396
0.211261
0.158633
NGNN
0.000070
0.000189
0.003395
0.009955
0,000003
0,000016
0.003706
0.002541
1--GNN
Out of GPU Memory
0.000002
0.000010
0.000069
0.000177
PPGN
Out of GPU Memory
Out of GPU Memory
2-DRFWL(2) GNN
0.000077
0.000192
0.000317
0.001875
0.000001
0.000007
0.000021
0.000178
Table 14: Empirical efficiency on ProteinsDB and HomologyTAPH datasets.
"OOM" means the
method takes an amount of GPU memory more than 24 GB.
ProteinsDB
Homology TAPE
Method
Memory (GB)
Pre. (s)
Train (s/epoch)
Memory (GB)
Pre. (s)
Train (s/epoch)
MPNN
2.60
235.7
0.597
1.99
243.8
5.599
NGNN
16.94
941.8
2.763
8.44
1480.7
15.249
F-GNN
OOM
1293.4
OOM
21.97
3173.6
38.201
PPGN
OOM
235.7
OOM
OOM
243.8
OOM
2-DRFWL(2) GNN
8.11
1843.7
3.809
3.82
2909.3
30.687
For ProteinsDB, we 10-fold cross validation and report the average normalized MAE for each counting task. We use the splitting provided in the raw data.
For HomologyTAPER there three test splits in the raw data, called "test_ fold", "test fasily" and "test_suupp" "isss_supeffamil"" respectively. The training/validan haapii//vaaiaatto/eessffooe fateeess_fammiyyttt_ssss splitting is 12,312/736/7188 1ttp//11/1,,2//1.111 ,544. We report the weighted average normalized MAE on the three test splits for each counting task.
Models. We adopt MPNN, NGNN, 12 IN-GNN and PPGN as our baselines. The implementation details of 2-DRFWL(2) GNN as well as all baseline methods follow Appendix [..21 except that (i) for NGNN and I2-GNN, the subgraph height is 3 for all tasks, and (ii) for PPGN, the number of PPGN layers is 5 and the embedding size is 64.
Training settings. We use Adam optimizer with initial learning rate 0.001, and use plateau scheduler with patience 10, decay factor 0.9 and minimum learning rate 10-5, We train all models for 1,500 epochs on ProteinsDB and 2,000 epochs on HomologyTAPE. The batch size is 32.
that 2-DRFWL(() GNN achieves relatively low errors (average normalized MAE < 0.002 for ProteinsDB, and < 0.0002 for Homology TAPE) for counting all 3, 4, 5 and 6-cycles on both datasets. This again verifies our theoretical result (Theorem 4.5). Although P--GNN and PPGN are also provably capable of counting up to 6-cycles, PPGN fails to scale to either PBoteinsDB HomologyTAL PA dataset, while 12-GNN fails scale to ProteinsDB. Therefore, 2-DRFWI((2) GNN maintains good scalability compared with other existing GNNs that can count up to 6-cycles.
Results. From Table 13
We also measure (i) the maximal GPU memory usage during training, (ii) the preprocessing time, and (iii) the training time per epoch, for all models both datasets. The result is shown in Table [4] We again see that 2-DRFWL(2) GNN uses much less GPU memory while training, compared with subgraph GNNs. Besides, the training time of 2-DRFWL(2) GNN is shorter than that of GNNNN, while the preprocessing time is comparable.
we also see one limitation of our implementation of 2-DRFWL(2) GNN, which we have mentioned in Section 7 the preprocessing of 2-DRFWI((2) GNN is not efficient enough on larger graphs graphs with a larger average degree. We believe this limitation can be addressed by
From Table 14
44

---

developing more efficient, parallelized operators for the preprocessing of 2-DRFWL(22) GNN, and we leave the exploration of such implementations to future work.
45


Reviews:
[{"review_id": "L6dXrBkTkT", "reviewer": "Reviewer_8bs4", "summary": "This work explores the ability of graph neural network to count certain graph substructures, especially cycles. While past works counts by collecting subgraphs, the work avoids such burdensome procedure and construct a local method. Theoretical analysis are presented to show that Folklore Weisfeiler-Lehman test. Accordingly, the work proposes d-Distance-Restricted FWL(2) GNNs (FWL(2) being 2-dimensional Folklore Weisfeiler-Lehman), which incorporates the Folklore Weisfeiler-Lehman test algorithm into the aggregation steps of a GNN. Subsequent theoretical analysis and experiemental evaluations of d-Distance-Restricted FWL(2) GNNs are provided. In particular, experiment results show that the proposed GNN shows superior results on counting cycles or other structures (in synthetic datasets) and better performance graph regression task on chemical datasets, as well as being empirically more efficient.", "questions": "Can experiments be provided for comparison between the proposed method with [35] and [46] for performance and empirical efficiency?\n\nCan experiments and analysis be provided for $d\\geq 2$?\n\nCan intuitive explanations be provided for each proof and concepts (currently, only 6-cyle is provided with an intuition)?\n- For example, it seems that the expressivity of up to 4-path and 6-cycle is correlated, as the furtherest node from a certain node in a 6-cycle requires a 4-path back get back to the certain node. Besides, is the 4-path attained by a pair of 2-tuples?\n\n\n", "limitations": "It is provided.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem of analyzing the ability of GNN to count substructures on a graph is interesting. Intuitively, counting cycles in a graph is non-intuitive for node-centric algorithm, where the operations solely performed on each node which only receives information from its neighbors at each iteration.\n- In light of above, the observation that counting cycles remains intrinsically \\emph{local} is a good and noteworthy observation.\n- The technical content is good and supported by the experiments.", "weaknesses": "### Neglected baseline comparisons with other higher-order GNNs\nAs explained by the author, [35] and [46] presents GNNs utilizing node tuples for better expressivity. As the adaptation of FWL(2) is the main component of this work, it is concerning that [35] and [46] are not included in the baseline comparisons. Since FWL is adopted into GNN to improve over sugraph GNNs, other (representative) works on higher-order GNNs should also be compared.\n\nAs it stands, there is no information in the paper on how this work compares to other higher-order GNNs. Does the proposed work have better performance and better efficiency? Does the proposed work trade-off performance for efficiency and space? We do not know.\n\nIn continuation of above, as [35] is a highly cited paper, further searching founds [a, b, c] that also mentions cycle counting in their paper, but is not discussed or mentioned in this work.\n- [a] A New Perspective on \"How Graph Neural Networks Go Beyond Weisfeiler-Lehman?\" ICLR 2022\n- [b] A Practical, Progressively-Expressive GNN. NeurIPS 2022\n- [c] Graph Neural Networks with Local Graph Parameters. NeurIPS 2021\n\n\n### Unanswered questions: ablation and trade-off for larger d\nWhile the work presents d-DRFWL(2) GNNs, the theoretical analysis and experiments are all limited to d=2. Furthermore, Q4 is not satisfyingly answered, as the experiment results are very close. Why not use a sufficiently large d to represent the FWL(2) test?\n\n### There are some places that are unclear and could be improved by providing more explanation:\n- FWL is left unexplained in the abstract. The paper may improve its readability by briefly stating FWL is a 2-tuple coloring scheme that solves graph isomorphism tests, whereas this work proposes to limit the scope of 2-tuples from all node pairs to only those within d-distance.\n- (line 108), \"divided by a factor only depending on S.\" Isn't the factor simply the number of nodes in S?\n- The syntax of using double curly brakets {{ }} for multisets should be noted when first appeared in Equation (1)\n- (line 125) the meaning of rightarrow with a bar ($\\mapsto$) is not clear. \n- The meaning (or depiction) of the twelve targets of QM9 dataset is not provided in the main paper or the appendix\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and thorough investigation of additional related works. We respond to all the weaknesses and questions below.\n\n**Reply to W1.**\n\nThanks for introducing the related works and offering the suggestion. To compare the performance and efficiency of our model with the ones proposed in [35], we implement GNNs based on **SSWL, SSWL+, LFWL(2) and SLFWL(2)** (all of which are proposed in [35]), and run them on four real-world datasets (in the order of increasing graph size): (i) QM9, (ii) ogbg-molhiv, (iii) HomologyTAPE and (iv) ProteinsDB. Details of the datasets are already present in our paper.\n\nFor all experiments, we use a dense $B\\times d\\times n\\times n$ matrix to store the embeddings of all 2-tuples within a batch, where $B$ is the batch size, $d$ is the size of the embedding dimension, and $n$ is the maximal number of nodes among all graphs in the batch.\n\nOn QM9 dataset, we use 5 layers with hidden size 64 for each model. We train for 400 epochs using Adam optimizer with initial learning rate 0.001, and plateau scheduler with patience 10, decay factor 0.9 and minimum learning rate 1e-5. The batch size is 64.\n\nDue to time and resource limitation, we compare the four methods with ours only on the first target (i.e., dipole moment $\\mu$). The result is shown below.\n\n|Method| QM9 ( $\\mathrm{MAE}_\\mu$ ) |\n|:---:|:---:|\n|SSWL|0.438|\n|SSWL+|0.421|\n|LFWL(2)|0.439|\n|SLFWL(2)|0.435 |\n|2-DRFWL(2) (ours)|**0.346**| \n\nWe see that on target $\\mu$, our model outperforms all four methods proposed in [35]. We also compare the efficiency of our model with the four methods. The used metrics follow our paper. The results are shown below. \n\n|Method | Memory (GB) | Preprocess (s) | Train (s/epoch)|\n|:---:|:---:|:---:|:---:|\n|SSWL|3.97|  64|88.5|\n|SSWL+|4.39|64|86.4|\n|LFWL(2)|3.17|64|58.0|\n|SLFWL(2)|3.97|64|82.8|\n|2-DRFWL(2) (ours)|2.31|430|141.9|\n\nOur method has the best memory efficiency compared with all four methods proposed in [35]. However, both the preprocessing time and training time of our model are longer. This is because \n* The four methods proposed in [35] do not need preprocessing, but instead build dense representation matrices on the fly.\n* The graphs in QM9 are rather small (~18 nodes per graph). On graphs of such small scale, the advantage of our model's lower time complexity are greatly offset by the constant overhead brought about by scatter operation on sparse matrices; in contrast, the four methods proposed in [35] use dense matrix multiplication and `1*1` convolution, which are more optimized operations on GPU\n\nOn ogbg-molhiv, HomologyTAPE and ProteinsDB, with the same hyperparameters as those chosen in Appendix E.3 & E.4, all of the four methods run out of GPU memory, indicating their inferior memory efficiency on large graphs.\n\nIn summary, our experimental studies show that 2-DRFWL(2) GNNs usually have better efficiency and scalability than GNNs based on SSWL, SSWL+, LFWL(2) or SLFWL(2) except on fairly small graphs. Additionally, it is often easier for 2-DRFWL(2) GNNs to capture the inductive bias suitable for molecular tasks.\n\nNext, we analyze the methods proposed in [46]. [46] proposes $\\delta$-$k$-GNN and $\\delta$-$k$-LGNN, which are also among the class of sparsified higher-order GNNs. For the case of $k=2$, both $\\delta$-2-GNN and $\\delta$-2-LGNN are encompassed by the framework of SSWL-GNN in [35]. This is because $\\delta$-2-GNN uses aggregation schemes $agg_{uv}^P$, $agg_u^L$, $agg_v^L$, $agg_u^G$ and $agg_v^G$, while $\\delta$-2-LGNN uses $agg_{uv}^P$, $agg_u^L$ and $agg_v^L$. Therefore, **the study of $\\delta$-2-GNN and $\\delta$-2-LGNN can be subsumed into our above study of SSWL-GNN**. We do not discuss the case of larger k since both $\\delta$-k-GNN and $\\delta$-k-LGNN would be overly expensive.\n\nThe above experiments and analysis should address the questions concerning a comparison with other higher-order GNNs, since [35] and [46] are among the most popular methods within this framework. \n\nAs for [a, b, c], we include a discussion below.\n\n* [a] proposes GraphSNN, which uses heuristics based on 1-hop subgraphs around nodes as well as their overlap subgraphs to enhance message passing. By its construction, GraphSNN can count 3-cycles, but fails to capture cycles longer than 4.\n\n* [b] proposes ($k$,$c$)($\\leqslant$)-SetGNNs, which greatly reduce the effective number of $k$-tuples in WL($k$) by (i) removing node order, (ii) removing duplicate nodes, and (iii) restricting the number of connected components. Like $d$-DRFWL(2), this work leverages **locality** to reduce storage. Nevertheless, there is **currently no theoretical guarantee** on their cycle counting power.\n\n* [c] proposes $\\mathcal{F}$-MPNNs, augmenting message passing GNNs with homomorphism counts. This method resembles GSN [ref1], and inherently encodes substructure counts. However, it is rather different from our method since it uses hand-crafted features. \n\n[ref1] G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2022.\n\n**Reply for W2.**\n\nThanks for the constructive advice. We have included a comprehensive study on larger d in the 2nd point of our general response.\n\nDue to space limit, we have to defer our response to the other weaknesses/questions in the author-reviewer discussion phase. We are sorry for the inconvenience, and will add the remaining response immediately when the discussion period begins.\n"}, {"review_id": "jt1A3ROrJn", "reviewer": "Reviewer_4wqe", "summary": "In this paper, the authors introduce the d-DRFWL(2) GNNs to count certain graph substructures, including cycles, cliques, and paths, which is essential for various graph-mining tasks. The authors prove that with d = 2, d-DRFWL(2) GNNs can already count up to 6 cycles, retaining most of the cycle counting power of FWL(2). Since the d-DRFWL(2) GNNs restrict the distance of message propagation, they are much more efficient than other GNN models. Experiments on both synthetic datasets and real molecular datasets are consistent with the theoretical results.", "questions": "Q1. There are other essential subgraph structure such as k-plex and k-core. I wonder whether the proposed framework can count this structures.\n\nQ2. The authors propose the existence of a clear hierarchy of expressiveness for d-DRFWL(2) GNNs as the value of $d$ increases. However, no experiments have been conducted to verify this claim across different values of $d$. Therefore, I would like to suggest the authors include a sensitivity test to support their theoretical findings.\n\n \n\n", "limitations": "Please check the weaknesses and questions.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1. The experiment is conducted on both real and synthetic datasets, where the results are convincing.\n\nS2. The theoretical results are sound and easy to follow.\n\nS3. The paper is clear and easy to follow.", "weaknesses": "W1. In my opinion, the scope of this particular line of research, which examines the expressive capabilities of GNNs by quantifying subgraph structures, appears to be rather limited. As stated in [1], GNNs are Turing complete (LOCAL algorithm) under certain conditions, indicating that they can effectively address any graph mining task with the same power as traditional algorithms. Consequently, this line of research primarily relies on observations made in previous graph mining algorithms and attempts to reinterpret them in the framework of GNNs, albeit within specific model designs, i.e., data structure for processing the graph. It would be beneficial if the authors could provide a comprehensive explanation detailing how their approach represents an advancement in utilizing GNNs to solve the subgraph counting problem, surpassing conventional algorithms [2].\n\nW2. Although the authors demonstrate that 2-DRFWL(2) can count 6-cycles, I am curious about the ability of 3-DRFWL(2) (or even larger $d$) to solve the cycle counting problem with larger subgraph sizes. If possible, it would be essential to understand the relationship between the minimal distance and the subgraph size. Additionally, exploring the impact of different values of K in the K-FWL test on the expressive power of GNNs would be interesting.\n\n[1] Loukas, A. (2019, September). What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations.\\\n[2] Ribeiro, P., Paredes, P., Silva, M. E., Aparicio, D., & Silva, F. (2021). A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 54(2), 1-36.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and suggestions. We respond to all the weaknesses and questions below.\n\n**Reply to W1.** \n\nWe thank the reviewer for providing relevant works [1][2]. Although [1] claims that message passing GNNs (MP-GNNs) can be Turing complete, the assertion is made under fairly strong assumptions, such as requiring **a unique identity labeling given to each node**, which explicitly breaks the permutation symmetry. As explained in Appendix D of [1], once we remove the node identity labeling, MP-GNNs are no longer Turing universal. Actually, MP-GNNs without node identity labeling are no more powerful than the WL(1) test (as stated in [a]), and cannot count any cycles. This fact indicates that they fail to **causally** recognize graph substructures.\n\nIn many real-world tasks, such as molecular property prediction, it is impossible to assign unique labels to nodes (for example, it is hard to consistently determine which node should be labeled as \"0\"-th in a benzene ring); instead, only models that respect permutation symmetry are considered. As is verified by our theory and experiments, with $d=2$, $d$-DRFWL(2) GNNs do have an outstanding substructure counting power compared with other permutation-symmetric models. There exist works [b, c] that assign unique random features/labels to nodes (breaking permutation symmetry), but they all have bad generalization performance on large real-world datasets since even two isomorphic graphs may have different representations using random features. \n\n[2] surveys traditional algorithms addressing the substructure counting problem. Different from our method, they are generally not data-driven. As we are to point out below, these traditional methods are **not directly comparable** with our method. This is because the ultimate goal of designing more powerful GNNs is to **tackle the traditionally intractable tasks in a data-driven manner**. Therefore, those GNN models (including ours) are not tailored to **solely** solving the substructure counting problem. Indeed, if certain substructure counts (or known functions of them) are the only targets, one should always apply traditional approaches instead of training a GNN, since traditional approaches avoid expensive training and have better accuracy and explainability. However, if the task is intractable by traditional approaches (e.g. molecular property prediction), then GNNs with strong cycle counting power (like ours) can work well. Therefore, the traditional methods and our model **differ in their domains of application**, and should not be directly compared.\n\nDespite the above discussion, substructure counting power remains a practical metric to evaluate a GNN's expressiveness, as stated in the 1st point in our general response. It is from this perspective should our main contribution (proposing efficient GNNs with provable cycle counting power) be understood.\n\n[a] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In ICLR, 2018.\n\n[b] Abboud, Ralph, et al. \"The surprising power of graph neural networks with random node initialization.\" arXiv preprint arXiv:2010.01179 (2020).\n\n[c] Sato, Ryoma, Makoto Yamada, and Hisashi Kashima. \"Random features strengthen graph neural networks.\" SDM 2021.\n\n**Reply to W2.**\n\nThanks for suggestion. As stated in the 2nd point of our general response, we have proved that increasing d from 2 to 3 makes d-DRFWL(2) able to count 7-cycles. However, further increasing d to $d\\geqslant 4$ does not bring about stronger cycle counting power since even FWL(2) cannot graph-level count more-than-8-cycles.\n\nAs for the distance-restricted version of FWL(k) with k>2, the meaning of \"mutual distance\" within k-tuples (k>2) is somewhat opaque. If the \"mutual distance\" within a k-tuple is defined as the maximal distance between nodes in it, then we believe that the resulting d-DRFWL(k) will form a similar expressiveness hierarchy with increasing d; moreover, their expressive power is similarly upper-bounded by FWL(k). However, since the cycle counting power of FWL(k) with k>2 is still open, the cycle counting power of d-DRFWL(k) defined above remains open.\n\n**Reply to Q1.**\n\nThanks for raising the valuable questions. We first clarify the definitions of k-plexes and k-cores as following:\n\n* A k-plex in G is an induced subgraph of G in which every node has degree at least $|S|-k$, where S is the node set of the subgraph\n* A k-core in G is an induced subgraph of G in which every node has degree at least k\n\nFor k-plexes, it is an NP-complete problem even to find the maximal k-plex of a graph G. [a] Therefore, it is generally impossible for our model to count k-plexes. Indeed, if k=1, as 1-plexes are simply cliques, our model fails to count 1-plexes with size larger than 4. \n\nFor k-cores, notice that a k-core can have arbitrarily large diameter, which may make it \"beyond the reach\" of d-DRFWL(2) GNN. For example, if k=2, then any induced cycle of G is a 2-core in G. Taking the example of **G being two $(3d+1)$-cycles and H being a single $(6d+2)$-cycle** (between which d-DRFWL(2) GNNs fail to discriminate), we see that G has two 2-cores while H has one. Therefore, d-DRFWL(2) GNNs cannot count 2-cores for any d. We believe that counterexamples for larger k can be similarly constructed, by considering other regular graph pairs with large diameters. \n\nSummarizing the above discussion, the answer to **Q1** is generally negative.\n\n[a] Balasundaram, Balabhaskar & Butenko, Sergiy & Hicks, Illya V. Hicks. (2011) Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem. Operations Research. 59. 133-142. 10.1287/opre.1100.0851. \n\n**Reply to Q2.**\n\nThanks for the constructive suggestion. We have included in the 2nd point of the \"general response to all reviewers\" a thorough experimental study of $d$-DRFWL(2) GNNs with two $d$ values: $d=2$ and $d=3$. The experimental results should have provided strong support to our theory."}, {"review_id": "vsZ6e4lyjb", "reviewer": "Reviewer_9V2p", "summary": "The paper focuses on the task of counting or detecting substructures such as cycles or small cliques in graphs. This task is (theoretically and practically) impossible for standard GNNs. While higher-order GNNs are able to count such substructures, they are slow, using $n^2$ space and $n^3$ time which is infeasible for large graphs. The paper suggests to make such higher-order GNNs practical by only considering \"local\" pairs of nodes (in the case of a 2-GNN) as substructures such as cycles are inherently local too. The paper proves that such distance-restricted higher-order GNNs are able to count substructures and in particular distance 2 and a 2-GNN suffice to count 6-cycles. Experiments underline the strong substructure counting power of the suggested method while still achieving reasonable runtimes (in contrast to full 2-GNN).", "questions": "- There seems to be a subtle difference between equations 3,4 and equations 6,7. In particular 6,7 explicitly create $M_{i,j}$ for every distance pair $i,j$ while equation 3,4 just create a single multiset of sift operations (colors). Would you like to comment on that small difference? I have the feeling that this change may make the distance-restricted method (with d>diameter) stronger than pure FWL, although your theorem states that this is not the case - effectively the DR variant seems to individualizes one node.\n\n- is 2-DRFWL(2) well suited for long-range dependencies? https://arxiv.org/abs/2206.08164\n- How does it perform on molpcba (which is more commonly evaluated against than molhiv)?\n- Is there a simple intuitive reason why FWL(2) cannot count more than 7-cycles? ", "limitations": "The authors addressed the main limitation of the work, namely that it becomes a lot slower when the degree in a graph increases, limiting the applicability to mostly the molecular domain and keeping it from working in the context of node classification.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strong cycle counting power without being extremely slow: finally we have an efficient GNN that can not only count triangles (i have seen a few of that) but the much more complicated (and possibly interesting) 6-cycles. This holds both in theory and in practice. The authors provide a clear theory (I have to admit that I did not check the proofs in the appendix) and extensive experiments focusing on the main claim, namely the strong cycle and in general substructure counting power. In terms of efficiency I was surprised that the practical memory consumption is not far from what a standard MPGNN uses (even though in the molecular domain the maximum degree in each graph is typically 3 or 4 and thus not extremely large). Overall a very nice paper!", "weaknesses": "I don't have strong criticisms about the paper (but please see the questions below). Here is a list of things I noted while reading the paper, roughly in the order of appearance:\n- 14: How is subgraph extraction avoided when using DRFWL? The DR-k-FWL procedure somehow needs to operate on small induced subgraphs. \n- 48: I would say it is not obvious why 2-FWL encodes closed walks. It would be nice to have some additional intuition there\n- 62: Many graphs have small diameter, for those the distance restriction does not help too much. And in particular, on the complete graph the distance restriction trivially is useless. The \"deg\" dependency is only introduced in the next paragraph such that the statement that DRFWL(2) should have a lower complexity than 2-FWL is unclear as this obviously does not hold for the worst-case complexity.\n- the related work might also include methods that break the 1-WL barrier by aggregating from multiple distances at once (those methods often call themselves \"higher-order\" in the sense that they use a \"higher-order neighborhood\", often 2 or 3 hops)\n- At Q4: please make explicit that this is a question to be answered empirically (the theory result is already there)\n- How about long-range dependencies? (https://arxiv.org/abs/2206.08164)\n- It would be nice to mention that the model is not suitable for node classification as the corresponding graphs typically have relatively large degrees (at least compared to molecules).\n\n\nTypography:\n- Leman asked to be written without the h. This is why some older papers still use the additional h while most newer ones do not.\n- It might look nicer to use \\bm for the $d$ in section headings\n- I personally prefer it when equations are referenced as Eq. (6) instead of just (6). One way is to use \\cref throughout the document\n- 173: the \"one the other hand\" seems out of context\n- It would be nice to have author names in addition to a citation [99] when [99] acts as the subject of that sentence. This happens several times in the related work section\n- 51: := \\ell -> =: \\ell (as \\ell is to be defined)\n- 296: Similar -> A similar\n- Thanks a lot for proper proofreading!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging our contributions as well as providing the insightful suggestions.\n\n**Reply to W1.**\n\n$d$-DRFWL(2) GNNs process a graph G in two steps: (i) extract all 2-tuples $(u,v)\\in\\mathcal{V}_G^2$ that satisfy $d(u,v)\\leqslant d$; (ii) initialize and update the embeddings of all such 2-tuples using the update rules (equations 10 and 11 of the paper).\n\nIn the above procedure, the message passing between 2-tuples takes place directly on the entire graph G, without the need to extract subgraphs from G and view G as a \"bag of subgraphs\". Moreover, messages from any 2-tuple (u, v) will be propagated to the entire graph after a sufficiently large number of iterations. In both senses DRFWL(2) GNNs avoid extracting subgraphs.\n\n**Reply to W2.**\n\nBriefly speaking, the update rule of FWL(2) allows each 2-tuple (u,v) to be aware of the information from another two 2-tuples (u,w) and (w,v), for an arbitrary w. Now, let us assume that we have *somehow* trained an FWL(2) GNN such that for every 2-tuple (u,v), its embedding contains $\\left(W_{d_1}(u,v), W_{d_2}(u,v), W_{d_3}(u,v)\\right)$, where $W_k(u,v)$ means the number of k-walks starting from u and ending at v. Then, the update rule of FWL(2) would allow the following value to be calculated:\n\n$$W_{d_1}(u,v)\\cdot\\sum_{w\\in\\mathcal{V}_ G} W_{d_2}(u,w)W_{d_3}(w,v)$$\n\nIf further summed over different $(d_1, d_2, d_3)$ combinations with fixed $l=d_1+d_2+d_3$, this yields the number of closed $l$-walks that pass u and v. In this sense, FWL(2) can encode closed walks, as long as information of shorter walks can be obtained. Since shorter walks are easy to capture by a few FWL(2) updates, our claim holds.\n\n**Reply to W3.**\n\nWe acknowledge that for graphs with small diameters (i.e., diameter $\\lesssim d$), the distance restriction of $d$-DRFWL(2) helps little in reducing computational cost. However, such graphs either have few nodes or are very dense (e.g. complete graphs). For the first case, the efficiency is usually not a major concern. The second case hardly happens since real-world graphs are usually sparse. We will explicitly state our assumption on sparsity in our revision, making the \"deg\" dependency clearer.\n\n**Reply to W4.**\n\nThanks for the suggestion. We include a discussion on those methods here. As proposed in [a], such methods are often called K-hop message passing GNNs (K-hop MPNNs). Like our method, K-hop MPNNs also explicitly leverage distances to control message passing, thus making use of the sparsity of the graphs. Their discriminating power is also between WL(1) and FWL(2). \n\nHowever, a major deficiency of K-hop MPNNs is that messages are passed between **nodes** instead of **node pairs**. As is discussed in our paper, such kind of message passing is **incapable of detecting substructures, especially cycles**. Indeed, as shown in Figure 1 of [a], the pair of graphs in either Example 1 or Example 2 contain different numbers of 3-cycles; however, K-hop MPNNs with either shortest path distance kernel or graph diffusion kernel fails to distinguish between both graph pairs, implying that vanilla K-hop MPNNs **fail to graph-level count even the simplest 3-cycles**. In contrast, with d=2, d-DRFWL(2) GNNs can already node-level count up to 6-cycles.\n\n[a] Feng, J. & Chen, Y. & Li, F. & Sarkar, A. & Zhang, M. (2022). How Powerful are K-hop Message Passing Graph Neural Networks. 10.48550/arXiv.2205.13328. \n\n**Reply to W5 & W7.**\n\nThanks for the suggestions. We will clarify both points in our revision.\n\n**Reply to W6.**\n\nThanks for the question. We evaluate 2-DRFWL(2) GNN on the two graph-level property prediction datasets, `Peptides-func` and `Peptides-struct` of Long Range Graph Benchmarks (LRGB). For experiments on both datasets, we use 5 2-DRFWL(2) GNN layers with hidden size 120. We train 200 epochs using Adam optimizer with initial learning rate 0.001, and plateau scheduler with patience 10, decay rate 0.5, and minimal learning rate 1e-5. The batch size is 64. The results are shown in Table 4 of the PDF.\n\nFrom the table, we see that our method outperforms almost all message passing GNNs. Surprisingly, on `Peptides-struct` the performance of our model is **even comparable to Transformer-based models** (which inherently capture long-range information). Therefore, we conclude that although designed to capture local structural information, our model still learns long-range dependencies well.\n\n**Reply to Typography.**\n\nThanks a lot for the meticulous checking! We will update them all in the revision.\n\n**Reply to Questions.** \n\nDue to space limit, we only provide brief responses to your questions. We are willing to append the full responses during the author-reviewer discussion.\n\n*Q1:* The fact is that with d > diameter, d-DRFWL(2) is **as powerful as** the FWL(2) test. The key is that FWL(2) can also calculate the distance between every node pair $(u,v)$, after which it can store the distance as an additional marking for the 2-tuple. Now it is easier to see the equivalence with equations 6,7, as long as d > diameter.\n\n*Q2:* Please see **W6**.\n\n*Q3:* The result of 2-DRFWL(2) GNN on molpcba is as follows.\n\n|Method | ogbg-molpcba (AP)|\n|:---:| :---:|\n| GIN+virtual node | 0.2703 $\\pm$ 0.0023|\n| Nested GIN+virtual node | **0.2832** $\\pm$ 0.0041 |\n| 2-DRFWL(2) GNN (ours) | 0.2076 $\\pm$ 0.0026 |\n\nWe see that our model performs poorly on ogbg-molpcba, which we have no proper explanation currently. While we will keep on fine-tuning the hyperparameters. We point out that none of the known higher-order GNNs (or their sparsified variants) have ever appeared on the leaderboard of ogbg-molpcba, indicating that ogbg-molpcba might be particularly hard to optimize or generalize for higher-order GNNs (including ours). \n\n*Q4:* The simplest answer is that Shrikhande graph and `4*4` Rook's graph (a well-known pair of FWL(2) inseparable graphs) have different numbers of 8~16 cycles. The intuitive explanation is deferred to author-reviewer discussion.\n"}, {"review_id": "H4UJyJ3Uv3", "reviewer": "Reviewer_pvsr", "summary": "The paper deals with constructing expressive GNNs (i.e., more expressive than 1-WL) with low complexity. The authors focus on cycle count ability, motivated by their importance in real life chemical datasets. With this problem and motivation at hand, the authors propose a family of algorithms possessing a strict hierarchy property called $d$-distcne restricted FWL or $d$-DRFWL(2).  They identify the ability to count cycles in the tuple based coloring and aggregation of the $2$-FWL algorithm compared to MPNNs which are bounded by $1$-WL and cannot even count a 3-cycle, but aim to avoid the $O(n^2)$ and $O(n^3)$ memory and time complexity respectively of $2$-FWL. To that end, they propose only coloring 2-tuples $(u,v)$ which are far from each other by ad most $d$ and propose a distance-dependent aggregation, this algorithm is named $d$-DRFWL(2). They then show that already for $d=2$ the proposed algorithm can count up to 6-cycles and that increasing $d$ strictly increases discriminative power. The proposed algorithm is the most efficient known model that can count 6-cycles, with time and memory complexities of $O(n\\mathrm{deg}^4)$ and $O(n\\mathrm{deg}^2)$, respectively. \n\n", "questions": "- Have the authors considered a baseline model where they add the cycle/substructure counts as features? Is the proposed method indeed better then the naive approach?\n- An ablation that I find missing is to see the empirical effect of $d$. Have the authors experimented with larger $d$ values?\n- How does the proposed hierarchy compare to LFWL(2) and SLFWL(2)? Due to this approaches being closely related, coloring 2-tuples in lower complexity, a more elaborate discussion would add to the work. Also, either theoretical or experimental comparison would be good. ", "limitations": "The authors discuss the limitations of their work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors clearly present the problem, goal, and motivation for their work. \n\nOn the originality and novelty side, the authors design the most efficient model to this date that can count 6-cycles and show a thorough analysis of one of its instances, the $2$-DRFWL(2).\n\nDue to the importance of cycle counts in chemical and biological structures, I think that this work is valuable to that community. \n\n", "weaknesses": "- Although taking a step towards more efficient and expressive GNNs, the efficiency of the method is only when graphs are sparse enough. To my understanding, the proposed method still did not break the limit of running on graphs of sizes $O(100)$ (e.g, ogbg-ppa dataset).\n- Do the authors have any explanation for the large performance gap between their method and $I^2$-GNN on the QM9 dataset? Theoretically, they both can count the same sizes of cycles, so this clouds the motivation for the paper in my opinion, since cycle counting may not be what makes this method more successful.   \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and thorough comments. We respond to all points below.\n\n**Reply to W1.**\n\nWe do agree with your comment that the efficiency of our model is only guaranteed when graphs are sparse. Still, our model can handle graphs with even $n\\approx 500$ nodes, as long as the average degree $\\mathrm{deg}\\sim O(1)$, as is verified by our experiments on ProteinsDB and HomologyTAPE datasets.\n\nOn graphs with $n$ nodes and average degree $\\mathrm{deg}$, $d$-DRFWL(2) GNN uses $O(n\\ \\mathrm{deg}^d)$ space and $O(nd\\ \\mathrm{deg}^{2d})$ time to store and update the embeddings for distance-restricted 2-tuples. Therefore, it is in general $\\mathrm{deg}$ instead of $n$ that has a larger impact on our model's efficiency. This fact accounts for the failure of $d$-DRFWL(2) GNN on ogbg-ppa, where the average degree is about 10. The search for efficient and powerful methods pertaining to dense graphs remains open. However, we also notice that practical molecule datasets (where cycle counting matters most) only have an average degree between 2 and 3, making our model feasible in most cases.\n\n**Reply to W2.**\n\nThanks for the valuable question. Below we list the relative performance gain, computed by\n$$\\frac{\\text{I}^2\\text{-GNN MAE}-\\text{2-DRFWL(2) GNN MAE}}{\\text{I}^2\\text{-GNN MAE}}$$\n\n|Target | Relative Performance Gain|\n|:---:|:---:|\n|$\\mu$|0.192|\n|$\\alpha$|0.035\n|$\\varepsilon_\\text{homo}$|0.134|\n|$\\varepsilon_\\text{lumo}$|0.157|\n|$\\Delta\\varepsilon$|0.147|\n|$R^2$|0.193|\n|$\\text{ZPVE}$|-0.214|\n|$U_0$|0.261|\n|$U$|0.257|\n|$H$|0.461|\n|$G$|0.402|\n|$C_v$|-0.234|\n\nWe see that the largest relative performance gains of 2-DRFWL(2) GNN compared with I$^2$-GNN occur on targets $U_0,U,H,G$ (each with gain $\\geqslant$ 25%). These targets are macroscopic thermodynamic properties of molecules. For such properties, inter-molecular interactions (such as hydrogen bonds), as well as interactions between molecules and the environment can be as important as interactions within molecules. Such interactions may occur between two atoms that are graph-theoretically distant (for example, between the “head” of a molecule and the “tail” of a nearby molecule). Therefore, subgraph extraction operation inhibits information from propagating between such atom pairs. Although our models are also local, they still allow long-range message passing by running for multiple iterations. Therefore, we suspect that it is our model's stronger ability to capture long-range interactions that leads to the observed performance gap with I$^2$-GNN.\n\n**Reply to Q1.**\n\nWe have included \"Graph Substructure Networks\" (GSN) [a] as a baseline model on ZINC-12k and ogbg-molhiv datasets. GSN augments the graph with node-level and edge-level induced substructure counts, and then runs a message passing GNN. As is shown in the following tables, the performance of our model is either better than or comparable with GSN on the two benchmarks.\n\n| Method |   ZINC-12k (MAE) | \n| :---:  |   :---:          |  \n|GSN| 0.115 $\\pm$ 0.012 | \n|$d$-DRFWL(2) GNN |  **0.077** $\\pm$ 0.002 | \n\n| Method | ogbg-molhiv (ROC-AUC) |\n| :---: |:---:|\n|GSN (GIN+VN base)| 0.7799 $\\pm$ 0.0100 |\n|GSN (DGN+substructures)| **0.8039** $\\pm$ 0.0090|\n|$d$-DRFWL(2) GNN | 0.7818 $\\pm$ 0.0219 |\n\n[a] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2022.\n\n**Reply to Q2.**\n\nThanks for the question. We have included a comprehensive study of the effect of larger d values in the 2nd point of our general response.\n\n**Reply to Q3.**\n\nThanks for the in-depth question. For any finite d, we can construct graph pairs that are separable by LFWL(2)/SLFWL(2) but not d-DRFWL(2). One of such graph pairs can be two $(3d+1)$-cycles and one $(6d+2)$-cycle, between which d-DRFWL(2) cannot discriminate. However, both LFWL(2) and SLFWL(2) can calculate distance between every pair of nodes, e.g. by simulating the Bellman-Ford shortest path algorithm. Therefore, it is easy for LFWL(2)/SLFWL(2) to distinguish between the aforementioned pair of graphs, since they have different diameters. This shows that **no d-DRFWL(2) with a fixed d value can be more powerful than LFWL(2)/SLFWL(2)**.\n\nOn the other hand, for graphs with diameter $\\leqslant d$, d-DRFWL(2) has equal power to FWL(2). Since it is shown in [a] that there exist graph pairs separable by FWL(2) but not LFWL(2)/SLFWL(2), once the value of $d$ grows larger than the diameter of such graph pairs, those graph pairs can be separated by d-DRFWL(2). This shows that **with sufficiently large d, the power of d-DRFWL(2) is neither stronger nor weaker than LFWL(2)/SLFWL(2)**.\n\nHowever, it remains underinvestigated the relation in discriminating power between LFWL(2)/SLFWL(2) and d-DRFWL(2) **with a practical d value**, such as d=2 or d=3. **Are d-DRFWL(2) with those smaller d values less powerful than LFWL(2)/SLFWL(2), or are they incomparable?** In an attempt to tackle this problem computationally, we implement in Python programs the construction procedure of the generalized Furer graph pairs described in [a]. It is claimed in [a] that the generalized Furer graph pairs constructed from Figure 9, 10, 11 of [a] cannot be separated by LFWL(2), while generalized Furer graph pairs constructed from Figure 10 of [a] cannot be separated by SLFWL(2). However, our experiments show that none of the mentioned generalized Furer graph pairs can be separated by d-DRFWL(2), with d=2 or d=3. Therefore, the question raised above remains open for future research.\n\n[a] B. Zhang, G. Feng, Y. Du, D. He, and L. Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. arXiv preprint arXiv:2302.07090, 2023."}, {"review_id": "zdmf4AsiKF", "reviewer": "Reviewer_TSJX", "summary": "The paper proposes a version of the 2-dimensional Weisfeiler-Leman algorithm that restricts the distance between nodes in the node tuples processed. A GNN based on this restriction is also proposed and investigated regarding its ability to count cycles and other substructures.", "questions": "**Q1** Is the approach as expressive as FWL(2) theoretically?\n\n**Q2** How does the proposed approach fit into the k-WL/ $\\delta$-k-LWL hierarchy?\n\n**Q3** Can you state the differences and connections to $\\delta$-k-LWL more clearly?\n\n**Q4** In d-DRFWL(k) what happens for larger values of d and k for theoretical expressiveness, running time and classification accuracy?\n\n### Other remarks:\nThe spacing between the lines is off at some places (for example l108/109 where characters from different lines overlap).", "limitations": "To me the theoretical expressiveness did not get discussed to the right extend (see Q2).", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "**S1** In general, the paper is well written and clearly structured.\n\n**S2** The idea to restrict the distance is interesting and seems to work reasonably well for counting substructures.", "weaknesses": "**W1** The description of the main contribution d-DRFWL(2) could be improved, making the illustration clearer. The general concept behind d-DRFWL(2) could be explained better. What exactly is updated with what information? The formula represents it, but the corresponding text and the example (Figure 1) could be more precise. It does not help that the figure is colored and the colors are referenced. I cannot distinguish red/violet/pink here.\n\n**W2** The theoretical investigation can be extended to show how the approach relates to k-WL and $\\delta$-k-LWL.\n\n**W3** More benchmark datasets should be used for evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and suggestions. We respond to all weaknesses and questions below.\n\n**Reply to W1.**\n\nThanks for the valuable suggestion. To understand the concept behind $d$-DRFWL(2), one has to first understand FWL(2). FWL(2) works by (i) assigning each 2-tuple $(u,v)\\in\\mathcal{V}_G^2$ a representation $W(u,v)$; (ii) updating the representation $W(u,v)$ iteratively. The update of $W(u,v)$ relies on an additional node $w$, and information is collected from both $(u,w)$ and $(w,v)$; afterwards, the above-collected information from all $w\\in\\mathcal{V}_G$ is gathered into a multiset, and the multiset is hashed into value $W(u,v)$ as the updated representation of $(u,v)$.\n\n$d$-DRFWL(2) differs from FWL(2) in two points: (i) only $(u,v)$ with a limited distance $d(u,v)\\leqslant d$ are given a representation; (ii) when updating $W(u,v)$, only information from $w$ with both $d(u,w)\\leqslant d$ and $d(w,v)\\leqslant d$ is gathered into the multiset. From the above description, one can see $d$-DRFWL(2) as a pruned version of FWL(2), in which representations for node pairs $(u,v)$ with $d(u,v)>d$ are deleted.\n\nSo far we have explained how $d$-DRFWL(2) works, what information is collected and what is updated in $d$-DRFWL(2). Now let us explain Figure 1, which illustrates 2-DRFWL(2). As explained above, 2-DRFWL(2) first assigns a representation to all pair of nodes with mutual distance $\\leqslant 2$. Then, these representations will be updated. Since in Figure 1 we have $d(u,v)=2$, $(u,v)$ is among the 2-tuples which will be assigned a representation. We exclusively focus on the update procedure of $W(u,v)$ in Figure 1. From point (ii), only those nodes $w$ with $d(u,w)\\leqslant 2$ and $d(w,v)\\leqslant 2$ play a role in the update procedure. Therefore, $w$ can be any of $u,v,x,y,z,t,r$ in Figure 1. We further classify the seven nodes based on their distances to $u$ and to $v$:\n\n|Nodes|Distance to $u$|Distance to $v$|Color|\n|:-:|:-:|:-:|:-:|\n|u|0|2|violet|\n|v|2|0|red|\n|x, y|1|1|green|\n|z|1|2|blue|\n|t|2|1|yellow|\n|r|2|2|pink|\n\nEach of these nodes contributes a piece of information like $(W(u,w), W(w,v))$, and they are then gathered to update $W(u,v)$. The colored lines in Figure 1 are simply depictions for node pairs $(u,w)$ and $(w,v)$, with $w\\in\\{u,v,x,y,z,t,r\\}$.\n\nWe will further clarify the text describing $d$-DRFWL(2), and change the colors in Figure 1 to more easily distinguishable ones in our revision.\n\n**Reply to W2.**\n\nThanks for the suggestion. Since 2-WL is equally expressive as WL(1), and 3-WL is equally expressive as FWL(2) [a], our methods strictly lie between 2-WL and 3-WL.\n\nAs for the $\\delta$-$k$-LWL hierarchy, it is known from [b] that for $k=2$, $\\delta$-2-LWL is as expressive as SSWL proposed in [b]. However, the relation in expressiveness between SSWL (or $\\delta$-2-LWL) and $d$-DRFWL(2) is unknown for arbitrary $d$. \n\nActually, for any finite $d$, two $(3d+1)$-cycles and one $(6d+2)$-cycle can be separated by SSWL($\\delta$-2-LWL) but not $d$-DRFWL(2). This shows that **no $d$-DRFWL(2) with a fixed $d$ value can be more powerful than SSWL($\\delta$-2-LWL)**. On the other hand, for graphs with diameter $\\leqslant d$, $d$-DRFWL(2) has equal power to FWL(2). Since it is shown in [a] that there exist graph pairs separable by FWL(2) but not SSWL, with d becoming larger than the diameter of such graph pairs, $d$-DRFWL(2) can separate that pair of graphs. This shows that **with sufficiently large $d$, the power of $d$-DRFWL(2) is neither stronger nor weaker than SSWL($\\delta$-2-LWL)**. Nevertheless, it remains an open question the relation in discriminating power between SSWL($\\delta$-2-LWL) and $d$-DRFWL(2) **with a smaller $d$ value**, such as $d=2$ or $d=3$. \n\nFinally, since for larger $k$ values, the precise relationship in expressiveness between $\\delta$-k-LWL and $k$-WL has not been established, the relation between $d$-DRFWL(2) and $\\delta$-k-LWL also remains an open problem. \n\n[a] N. T. Huang and S. Villar. A short tutorial on the weisfeiler-lehman test and its variants. In ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)\n[b] B. Zhang, G. Feng, Y. Du, D. He, and L. Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. arXiv preprint arXiv:2302.07090, 2023.\n\n**Reply to W3.**\n\nThanks for the suggestion. We further evaluate 2-DRFWL(2) GNN on the two graph-level property prediction datasets, `Peptides-func` and `Peptides-struct` of Long Range Graph Benchmarks (LRGB) [a]. For experiments on both datasets, we use 5 2-DRFWL(2) GNN layers with hidden size 120. We train 200 epochs using Adam optimizer with initial learning rate 0.001, and plateau scheduler with patience 10, decay rate 0.5, and minimal learning rate 1e-5. The batch size is 64. The results are shown in Table 4 of the PDF.\n\nFrom the table, we see that our method outperforms almost all message passing GNNs, and even achieves comparable performance to transformer-based models on `Peptides-struct`. Therefore, we conclude that although designed to capture local structural information, our model still learns long-range dependencies well.\n\n[a] V. P. Dwivedi, L. Rampášek, M. Galkin, A. Parviz, G. Wolf, A. T. Luu, D. Beaini, Long Range Graph Benchmark\n\n**Reply to Questions**\n\nDue to space limit, we only provide brief responses to your questions. We are willing to append the full responses during the author-reviewer discussion.\n\n*Q1.* No, our method is strictly less powerful than FWL(2)\n\n*Q2.* Our method lies strictly between WL(2) and WL(3), while the comparison with $\\delta$-k-LWL is left open\n\nDue to space limit, we have to defer our response to the other questions in the author-reviewer discussion phase. We are sorry for the inconvenience, and will add the remaining response immediately when the discussion period begins."}]

Author rebuttal:
We thank all the reviewers for their insightful feedbacks and constructive suggestions. All the comments have been scrupulously considered, and we will integrate the suggestions into our revised version of the paper. To address the common concerns of the reviewers, below we restate the focus of our paper by answering a related question, and present our additional results obtained during the rebuttal period.

**1. Why to use cycle counting power as a metric for expressiveness of GNNs?**

Many reviewers raise the questions about how $d$-DRFWL(2) GNNs fit into other expressiveness hierarchies, such as $k$-WL [a], $\delta$-$k$-WL [b] and LFWL(2)/SLFWL(2) [c]. Although these questions are meaningful themselves, they deviate from our focus. The major concern of our paper is **to propose efficient GNNs with provably strong cycle counting power**. Therefore, cycle counting power is chosen as a metric to evaluate the expressiveness of GNNs. There are two practical reasons to use this metric instead of (the more widely used) discriminating power: 

* Many real-world tasks (such as molecular property prediction) rely heavily on cycle counts. Therefore, GNNs with provable cycle counting power can capture important inductive bias closely related to such tasks, while GNNs that are incapable of counting cycles inevitably fail to make causal predictions on such tasks

* For many of the known expressiveness hierarchies such the WL hierarchy [a], the separation in expressiveness is often based on delicately crafted counterexamples, which provide little insight into the expressiveness exhibited in practical tasks. In contrast, cycle counting power remains a useful metric when we need to evaluate the practical expressiveness of a model on given datasets.

**2. Additional studies on $d$-DRFWL(2) GNNs with $d>2$.**

As pointed out by many reviewers, currently our paper only contains extensive studies on the cycle counting power of 2-DRFWL(2) GNNs. There is no investigation on the cycle counting power of $d$-DRFWL(2) GNNs with larger $d$, nor any experimental comparison between 2-DRFWL(2) GNNs and $d$-DRFWL(2) GNNs with larger $d$ values. During the rebuttal period, we have thoroughly studied, both theoretically and empirically, the discriminating power (related to **Q4** of our paper) and node-level cycle counting power of $d$-DRFWL(2) GNNs, with $d>2$. 

Regarding the discriminating power of $d$-DRFWL(2) GNNs with larger $d$ values, we run 3-DRFWL(2) GNN on two synthetic datasets: (i) EXP and (ii) SR25. The result is shown in Table 1 of the PDF. We can see that (i) 3-DRFWL(2) GNN discriminates between **all graph pairs on EXP**, including those not separable by 2-DRFWL(2) GNN, verifying **the strict expressiveness gap between 2-DRFWL(2) GNN and 3-DRFWL(2) GNN**; (ii) 3-DRFWL(2) GNN fails on SR25 dataset with accuracy 6.67%.

Regarding the node-level cycle counting power, we have **fully unveiled** the theoretical cycle counting power for $d$-DRFWL(2) with **arbitrary** $d\geqslant 2$:

* 2-DRFWL(2) GNNs can node-level count 3, 4, 5, 6-cycles but cannot graph-level count 7-cycles (already proved in our paper)
* $d$-DRFWL(2) GNNs with arbitrary $d\geqslant 3$ can node-level count 3, 4, 5, 6, 7-cycles but cannot graph-level count 8-cycles (**newly added**)

A proof sketch of the second bullet point is given below. The negative result follows from the fact that $d$-DRFWL(2) GNNs are less powerful than FWL(2) and that FWL(2) cannot graph-level count 8-cycles [e]. For the positive result, it suffices to prove that 3-DRFWL(2) GNNs can node-level count 7-cycles. To calculate the count of 7-cycles, we first decompose a 7-cycle into a 3-path and a 4-path, both of which can be counted by 3-DRFWL(2) GNNs. Then, we enumerate all possible cases in which some of the nodes in the 3-path and the 4-path coincide. There are 12 cases in total, all of them shown in Figure 1 of the PDF. By examining each kind of substructure, we confirm that all of them can be counted by 3-DRFWL(2) GNNs, leading to the positive result.

To verify our theory, we conduct node-level cycle counting experiments on the Substructure Counting dataset, for both 2-DRFWL(2) GNN and 3-DRFWL(2) GNN. Particularly, we add the task of node-level counting 7-cycles. The result is shown in Table 3 of the PDF. We see that on the task of counting 3, 4, 5 and 6-cycles, 3-DRFWL(2) GNN achieves comparable performance with 2-DRFWL(2) GNN; on the task of counting 7-cycles, 3-DRFWL(2) GNN greatly outperforms 2-DRFWL(2) GNN, validating our theory.

We point out that the fact that 3-DRFWL(2) GNNs can node-level count 7-cycles **confirms the existence of GNNs with the same cycle-counting power as FWL(2) but strictly lower complexity**.

We further investigate the real-world performance of 3-DRFWL(2) GNNs by conducting ablation studies on the ZINC-12K dataset. The result is shown in Table 2 of the PDF. It is worth noticing that by only introducing part of the aggregations related to distance-3 tuples, a great performance gain can be observed.

[a] J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389–410, 1992.

[b] C. Morris, G. Rattan, and P. Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33:21824–21840, 2020.

[c] B. Zhang, G. Feng, Y. Du, D. He, and L. Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. arXiv preprint arXiv:2302.07090, 2023.

[d] Ribeiro, P., Paredes, P., Silva, M. E., Aparicio, D., & Silva, F. (2021). A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 54(2), 1-36.

[e] V. Arvind, F. Fuhlbrück, J. Köbler, and O. Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113:42–59, 2020.

Meta-review: The reviewers first raised a few questions, including the methodology and the experimental work., on this paper. The authors properly addressed them during the rebuttal/discussion phase, and the reviewers were finally all positive about the work.
In light of the reviews, discussions, and scores, I am hence recommending this paper be accepted as a spotlight.
Decision: Accept (spotlight)