Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
Authors: Jan Tönshoff
Martin Ritzert
Hinrikus Wolf
Martin Grohe
Venue: Accepted by TMLR ()

Abstract: We propose CRaWl, a novel neural network architecture for graph learning. Like graph neural networks, CRaWl layers update node features on a graph and thus can freely be combined or interleaved with GNN layers. Yet CRaWl operates fundamentally different from message passing graph neural networks. CRaWl layers extract and aggregate information on subgraphs appearing along random walks through a graph using 1D Convolutions. Thereby it detects long range interactions and computes non-local features. As the theoretical basis for our approach, we prove a theorem stating that the expressiveness of CRaWl is incomparable with that of the Weisfeiler Leman algorithm and hence with graph neural networks. That is, there are functions expressible by CRaWl, but not by GNNs and vice versa. This result extends to higher levels of the Weisfeiler Leman hierarchy and thus to higher-order GNNs. Empirically, we show that CRaWl matches state-of-the-art GNN architectures across a multitude of benchmark datasets for classification and regression on graphs.

Published in Transactions on Machine Learning Research (08/2023)
Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
Jan Tönshoff RWTH Aachen University
Martin Ritzert Geory-August- Universität Cöttingen
Hinrikus Wolf
RWTH Aachen University
Martin Grohe RWTH Aachen University
grohesnnfomatt..ruu..cccc..
Reviewed on OpenReview: https: // openreview. net/ forum? id= VgXYByeWVV
Abstract
We propose CLAWL, a novel neural network architecture for graph learning. Like graph neural networks, CRAWL layers update node features on a graph and thus can freely be combined or interleaved with GNN layers. Yet CRAWI. operates fundamentally different from message passing graph neural networks. CRA WL layers extract and aggregate information on subgraphs appearing along random walks through a graph using 1D Convolutions. Thereby, it detects long range interactions and computes non-local features. As the theoretical basis for our approach, we prove a thcorem stating that the expressiveness of CRAWL is incomparable with that of the Weisfeiler Leman algorithm and hence with graph neural networks. That is, there are functions expressible by CRAWL, but not by GNNs and vice versa. This result extends to higher levels of the Weisfeiler Leman hicrarchy and thus higher-order GNNs. Empirically, we show that CRAWL matches state-of-the-at GNN architectures across multitude of benchmark datasets for classification and regression graphs.
1 Introduction
Over the last five-years, graph learning has become dominated by graph neural networks (GNNs), unquestion- ably for good reasons. Yet GNNs do have their well-known limitations, and an important research direction in recent years has been extend the expressiveness of GNNs without sacrificing their efficiency, Instead, we propose novel neural network architecture for graphs called CRAWL (CNNs for Random Walks). While still being fully compatible with GNNs in the sense that, just like GNNs, CRA WL iteratively computes node features and thus can potentially be integrated into a GNN architecture, CRA WL is based on fundamentally different idea, and the features extracts are provably different from those of GNNs. CRAW WL samples a set of random walks and extracts features that fully describe the subgraphs visible within a sliding window over these walks. The walks with the subgraph features are then processed with standard 1D convolutions. The outcome is pooled into the nodes such that each layer updates latent embedding for each node, similar GNNs and graph transformers.

---

Published in Transactions on Machine Learning Research (08/2023)
The CRAWL architecture was originally motivated from the empirical observation that in many application scenarios random walk based methods perform surprisingly well in comparison with graph neural net A notable example is node2vec (Grover & Leskovee 2016) in combination with various classifiers. A second observation is that standard GNNs are not very good at detecting small subgraphs, for example, cycles of length (Morris et al., 2019 Xu et al. 2019). The distribution of such subgraphs in a graph carries relevant, information about the structure of a graph, as witnessed by the extensive research on motif detection and counting (e.g. Alon 2007). CRAW WL detects both the global connectivity structure in a graph by sampling longer random walks well as the full local structure and hence all subgraphs within its window size. We carry out a comprehensive theoretical analysis of the expressiveness of CRA WT. Our main theorem shows that CRAWL is incomparable with GNNs in terms of expressiveness:
(1) there are graphs that can be distinguished by CRAWI, but not by GNNs, and (2) there are graphs that can be distinguished by GNNs, but not by CL. The first result is based on the well-known characterization of the expressiveness of GNNs in terms of the Weisfeiler- can be extended to the full Weisfeiler Leman hierarchy and hence higher-order GNNs: for every k there are graphs that can be distinguished by CRAWL, but not by k-dimensional Weisfeiler Leman. In particular, this means that the result also applies to the variety of GNN-extensions whose expressiveness is situated within the Weisfeiler Leman hicrarchy (e.g. Barceló et al. 2021 Cotta et al. 2021 Maron et al. 2019a).
algorithm (Morris et al. 2019; Xu et al. 2019). Notably, the result
Yet it is not only these theoretical results making CRAWL attractive. We believe that the key to the strength of CRA WL is a favorable combination of engineering and eapressiveness aspects. The parallelism of modern hardware allows us to efficiently sample large numbers of random walks and their feature matrices directly on the GPU. Once the random walks are available, we can rely on existing highly optimized code for 1D CNNs, again allowing us to exploit the strength of modern hardware. Compared to other methods based counting or sampling small subgraphs, for example graphlet kernels (Shervasiizee et al.) 2009b), CRAWLI method of sampling small subgraphs in a sliding window on random walks has the advantage that even in sparse graphs it usually yields meaningful subgraph patterns. Its way of encoding the local graph structure and processing this encoding gives CRA WL an edge over subgraph GNNs (Frasca et al. 2022 and randon-walk-ban based neural networks such as RAW-GNN (Jin et al. 2022).
We carry out comprehensive experimental analysis, demonstrating that empirically CRAWL is on par with advanced message passing GNN architectures and graph transformers major graph learning benchmark datasets and excels when it comes to long-range interactions.
1.1 Related Work
Message passing GNNs (MPGNNs) GGilmer et al. (020), as the currently dominant graph learning architecture, constitute the main basclines in our experiments. Many variants of this architecture exist (soc Wu et al.)
2020), such as GCN (Kipl & Welling 2017). GIN (Xu et al. 2019), GAT (Veličković et al.] 2018), GraphSage (Hamilton et al. 2017), and PNA (Corso et al. 2020). Multiple extensions to the standard message passing framework have been proposed that strengthen the theoretical expressiveness which otherwise is bounded by the 1-dimensional Weisfeller-Lenan algorithm. With 3WLGNN, Maron et al. (2019a) suggested higher- order GNN, which is equivalent to the 3-dimensional Weisfeiler-Temmnn kernel and thus more expressive than standard MPGNNs. In HIMP (Fey et al. 2020), the backbone of a molecule graph is extracted and then two GNNs are run in parallel on the backbone and the full molecule graph. This allows HIMP to detect structural features that are otherwise neglected. Explicit counts of fixed substructures such as cycles or small cliques have been added to the node and edge features by Bouritsas et al. (2020) (GSN). Similarly, Sankar et al. (017]) , Lee et al. (2019), and Peng et al. (2020) added the frequencies of motifs, i.e., common connected induced subgraphs, to improve the predictions of GNNs. Sankar et al. 2020 introduce motif-basee regularization, a framework that improves multiple MPGNNs. In [Jiang et al. 2022 the authors introduce sparse motifs which help to reduce over-smoothing in their architecture called Sparsc-Motif Ensemble Graph Convolutional Network. Another approach with strong empirical performance is GINE+ (Brossard et al., 2020). It is based on GIN and aggregates information from higher-order neighborhoods, allowing it to detect small substructures such as cycles. Beaaini et al. (2021) proposed DGN, which incorporates directional awareness into message passing. Bodnar et al. (2021) propose CW Networks, which incorporate regular Cell Complexes into GNNs to construct architectures that are not less powerful than WT.
2

---

Published in Transactions on Machine Learning Research (08/2023)
A different way to learn on graph data is to use similarity measures graphs with graph kernels (Kriege et al. 2020). Graph kernels often count induced subgraphs such as graphleis, label sequences, or subtrees, which relates them conceptually to our approach. The graphlet kernel (Shervashidze et al.) 2009a) counts the occurrences of all 5-node (or more general k-node) subgraphs. The Phisfeiler-Leman kernel (Shervashidze eet al. 2011) is based on iterated degree sequences and effectively counts occurrences of local subtrees. A slightly more expressive graph kernel based on a. local version of a higher-dimensional Weisfeiler-Leman algorithm was introduced in (Morris et al. 2020b). The Weisfeiler-Leman algorithm is the traditional yardstick for the expressiveness of GNN architectures.
Another line of research studies Graph Transformers Dwivedi & Bresson (2020) based on Transformer networks (Vaswani et al.) 2017). By combining the spectral decomposition of the graph Laplacian with global transformer- based attention, spectral attention networks (SAN) by Kreuzer et al. (2021) focus on global patterns in graphs. Chenn et al. (2022) propose Structure-Aware Transformers (SAT), which embed all k-hop subgraphs in a graph with a GNN and then process the resulting set of subgraph emboddings with a Transformer. In contrast to SAN, SAT thus focuses more on local features, similar to MPGNNs.
A few previous approaches utilize conventional CNNs in the context of end-to-end graph learning. Patchy-SAN (Niepert et al. 2016) normalizes graphs in such a way that they can be interpreted by CNN layers. Zhang lt al. (2018) proposed a pooling strategy based on sorting intermediate node embeddings and presented DGCNN which applies a ID CNN to the sorted embeddings a graph. Yuan & Ji (0211) used a ID CNN layer and attention for neighborhood aggregation to compute node embeddings.
Several architectures based on random walks have been proposed. Nikolentzos & Vazirgiannis 2020) propose differentiable version of the random walk kernel and integrate it into GNN architecture where they learn number of small graph against which the differentiable random walk kernel compares the nodes of the graph. In [Geerts| 2020), the 6-walk MPGNN adds random walks directly as features to the nodes and connects the architecture theoretically to the 2-dimensional Weisfeiler-Lemal algorithm. RAW-GNN (Jin et al. 2022) and pathGCN (Eliasof et al. 2022) aggregate node features along random walks, learning to aggregate information based on the distance to the start of the walk. This aggregation allows RAW-GNN to tackle node predictions in heterophilic clomain. Similar distance-basee based aggregations are also possible in a multi-hop MPGNN by Ma et al. (2020). Note that these approaches do not encode the structure traversod by the walk at all, instead the methods locus solely on proximily. In contrast, CRAW: explicitly extracts and uses local structure.
Ivanov & Burnaev (0188) proposed a structure-aware approach by encoding node identity along anonymous random walks to learn graph representations for SVMs. Wang et al. (2021) extend the concept of anonymous
random walks to temporal graphs. They also use encodings of node identity as features which are processed
by an RNN to solve temporal link prediction tasks. In a related approach, Yin et al. (2022) learn subgraph representations based on random walks sampled around a set of query vertices. Their features are based on histograms of walk distances and are also processed by RNNs. They apply their approach to link prediction tasks and demonstrate performance superior to standard MPGNNs. The previous two methods share conceptual parallels with CL, but there are several core differences: The features of CRA WL encode both the identity and adjacency between vertices (instead of just identity) to provide an explicit and complete encoding of subgraph structure. Furthermore, our approach does not just compute an embedding of a subgraph around query vertices. Instead, we use CRAWL to embed all vertices at once with a more parallclizable CNN in a manner that is compatible with message passing, Virtual Nodes, and other graph-learning layers based on iteratively refining vertex embeddings. These differences enable CRAWL. to tackle tasks where local structural features are of high importance and a bottleneck of standard GNN architectures such as graph classification in the molecular domain.
Through its encoding of the complete local structure around a random walk, CRAWL processes induced subgraphs, and in that regard is similar to Subgraph GNNs (Frasca et al.] 2022) and Structure-Awar Transformers (SAT) (Chen et al.] 2022). Prior work in this framework includes Nested Graph Neural Networks (Zhang& & Li, 2021), , Equivariant Subgraph Aggregation Networks (Bevilacqua et al. 2022), and "GNN As Kernel" (Zhao et al. 2022). The main difference to our model is the way local structure is made available to the model. Both Subgraph GNNs and SAT use a standard MPGNN to process subgraphs, therefore keeping some limitations although they are more expressive than 1-WL In contrast, CRA WL
3

---

Published in Transactions on Machine Learning Research (08/2023)
connectivity
node label
edge label
identity
f(11) 0000000 0000
000
f(u2) g(v., U2)
0000
000
f(v3) ( 03)
0000
100
f(va) g(03, 24)
0000
010
f(us) ((a,, (15)
0000
001
((66) g v6)
0000
110
f(v4) (06, M4
0010
101
random walk
X (W,4)
1D CNN
Pool
Update
W (U1, 02, U3, U4, US, V6, .......
Example of the information flow in a CRAWL, layer for graph with nodes. We sample a walk W and compute the feature matrix X based on node embeddings f. edge emboddings g. and window size of s=4. To this matrix apply 1D CNN with receptive field r=5 and pool the output into the nodes to update their embeddings.
Figure 1:
defines binary encodings of the (fixed-izee) subgraph structure which are then embedded by an MLP which in theory can encode every function. On the other hand, our subgraph representation not deterministic since it depends on the order in which the random walk traverses the subgraph, while always providing complete structural information. Also, the chosen subgraph is random, depending on the concrete random walk. Due to those differences the expressiveness of MPGNNs and CRA WL is incomparable as formally shown in Section 3
2
Method
CRAWL processes random walks with convolutional neural networks to extract information about local and global graph structure. For a given input graph, we initially sample a large set of (relatively long) random walks. For each walk, we construct scquential fcature representation which encodes the structure of all contiguous walk segments up to predetermined size (walklets). These features are well suited for processing with 1D CNN, which maps each walklet to embedding. These walklet embeddings are then used to update latent node states. By repeating this process, we allow long-range information about the graph structure to flow along each random walk.
2.1 Random Walk Features
A walk W length é E in a graph G = EV,E) is a sequence nodes W (vo....,,ee) E V with 01-1% E for all i E [f]. A random walk a graph is obtained by starting at some initial node vp and iteratively sampling the next node U:41 randomly from the neighbors Na(u;) of the current node v;. In our main experiments, we choose the next node uniformly among Na( (e( i.e. following non-backtracking uniform random walk strategy. In general, the applied random walk strategy is hyperparameter of crawl and we perform an ablation study on their effectiveness in Section 5 There, we compare uniform random walks with and without backtracking. Another common random walk strategy are pq- Walks as used in node2vec (Grover & Leskover 2016).
We call contiguous segments W : (w, (w...... w/) of walk W (wo. ... .. we) walklets. The center of a walklet (w....., wy) of even length j is the node w(i+s)/2- For each walklet (w,, ........ wy): we denote by G[w) the subgraph induced by the set (wi,..., w. Note that Glw) connected it contains all
4

---

Published in Transactions on Machine Learning Research (08/2023)
edges wg.h+1 for i S k j, and it may contain additional edges. Also note that the wy not necessarily distinct, especially if backtracking uniform random walks are used.
For a walk W and a local window size we construct a matrix representation that encodes the structure of all walklets of size 8 ++1 in W as well as the node and edge features occurring along the walk. Given a walk W E V of length f-1 in graph G, a d-dimensional node embedding f: - Rd a d' d'-dimensional edge embedding g E -&-R" Rd,, and local window size > 0 define the walk feature matris (W, f, 8) E xxxx with feature dimension dx + d' &sS + (s 1) as
X(W,f.9.8 (fw 9w Iw Aw).
For ease of notation, the first dimensions of each of the matrices fw ,w. Tw AW is indexed from 0 to l - 1. Here, the node feature sequence Jw Réxd and the edge feature sequence gw E Rexd are defined the concatenation of node and edge features, respectively. Formally,
= f(r)) and (gw)s, = -10, (9(0)12))) else. (fw)__=(rr
if==0
We define the local identily relation Iyy E (0, 1xxx and the local adjacency relation Air E (0, (0,1)ex(--1) as
1, if 0 A
(1w)
and
0, else
1,
ifi A G
(Air)ss
0, clsc.
The remaining matrices In and Aiy are binary matrices that contain one row for every node us in the walk W. The bitstring for 02 in Iy encodes which of the s predecessors of o; in W are identical to U, that is, where the random walk looped or backtracked. Micali & Zhu (2016) showed that from the distribution of random walks of bounded length with such identity features, one can reconstruct any graph locally (up to some radius r depending on the length of the walks). Similarly, Ai stores which of the predecessors are adjacent to v, indicating edges the induced subgraph. The immediate predecessor 6;-1 is always adjacent to o and thus omitted in Ay. Note that we do not leverage edge labels of edges not on the walk, only the existence of such edges within the local window is encoded in AWr.
For any walklet description of the induced subgraph G(w)]. Hence, when apply a CNN with receptive field of size at most +1 1 to the walk feature matrix, the CNN filter has full access to the subgraph induced by the walklet within its scope. Figure 1 depicts an example of a walk feature matrix and its use in a CRAW, layer.
Wii: s), the restriction of the walk feature matrix to rows i, + contains full
CRA WL initially samples m random walks Ω (Wi,..., Wm) of length é from the input graph. By stacking the individual feature matrices for each walk, we get the walk feature tensor X(O, f. g. s) E Rmxxxdx defined
X (S,...9,5), -(M....))
This stack of walk feature matrices can then be processed in parallel by a CNN. The values for m and & are not fixed hyperparameters of the model but instead can be chosen at runtime. By default, start one walk at every node, i.e., =VV), We noted that reducing the number of walks during training overfitting and of course is a way to reduce the memory footprint which is important for large graphs. If we choose to use fewer random walks, we sample m starting nodes uniformly at random. We always make sure that mf >>>>> [V), ensuring that with high probability each node appears on multiple paths. We typically choose 2 50 during training. During inference, we choose a larger é of up to 150 which improves the predictions. The window size s has to be least for molecular datasets to capture organic rings. By default we thus = 8 and expand the window size to 16 when handling long-range dependencies.
help against
5

---

Published in Transactions on Machine Learning Research (08/2023)
CRaWl Layer
ht-1 E R Vxd
1D CNN
node pool
MLP U
X(2,1'11 ,F
C²
ht IR Vxd
Ω E Vmxe
CRaW Layer
CRa Layer
CRaWi Layer
global pool
h
MLP +0/1
Ω
Figure Top: Update procedure of latent node embeddings ht in a CRAWL layer. Q is a set of random walks. Bottom: Architecture of 3-layer CRAWL network used in the experiments.
2.2 Architecture
A CRAWL network iteratively updates latent embeddings for each node. Let G (V, E) be graph with initial node and odge feature maps FV V Rdv and F - Rdz, The function h(() V + Rd stores the output of the 1-th layer of CRAWL and the initial node features are stored in h()) FV. In principle, the output dimension d(t) is independent hyperparameter for each layer. In practice, d for the output node embeddings of all layers for simplicity.
the same size
The 1-th layer of a CRAWL. network constructs the walk feature tensor X = (t-11) as its imput node embedding and the graph's edge features FE, This walk feature tensor is then processed by a convolutional network CNN(() based on 1D CNNs. The first dimension of ( of size m is viewed as the batch dimension. The convolutional filters move along the second dimension (and therefore along each walk) while the third dimension contains the feature channels. Each CNN(1)) consists of three convolutional layers combined with ReLU activations and batch normalization. A detailed description is provided in Appendix B. The stack of operations has receptive field of s+1 and effectively applies an MLP to each subsection of this length in the walk feature matrices. In cach CNN()) we use Deptharise Separable Convolutions (Chollet 2017 for efficiency.
using
The output of CN is tensor (+t) E x)) Note that the second dimensson is f-s instead of as no padding used in the convolutions. Through its receptive field, the CNN operates on walklets of size s+1 and produces embeddings for those. We pool those embeddings into the nodes of the graph by averaging for each node e E V all embeddings of walklets centered at w. Let (W1,... W.) be set of walks with W; (v.,.....,
w/-9/2 E Rd is the embedding computed by CNN( for the walklet w Wilj f j + centered at Ui and the pooling operation is given by
Ui.e). Then (i())
(v)= =
mean (R.)).))
f.j-//2
Here, center(R,, 8, s, is the set of walklets of length s+1 in Ω in which occurs center. We restrict to be even such that the center is always well-defindd. The output of the pooling step is a vector (*) (v) E I for each v. This vector is then processed by a trainable MLP U() with a single hidden layer of dimension 2d to compute the next latent vertex embedding
(w) u/0 (p(0))))))
6

---

Published in Transactions on Machine Learning Research (08/2023)
Figure 2 (top) gives overview over the elements of a CRAWL layer. Our architecture stacks multiple CRA WT. layers into one end-to-end trainable neural network, as illustrated in Figure| 2 (bottom). After the final layer we apply batch normalization before performing a global readout step with either sum- or mean-pooling to obtain a graph-level latent embodding. Finally, a simple foedforward ncural network is used to produce a graph-level output which can then be used in classification and regression tasks.
Since CRAWL layers are based on iteratively updating latent node embeddings, they are fully compatible with conventional message passing layers and related techniques such virtual nodes (Gilmer et al., 2017 Li
et al. 2017 Ishiguro et al., 2019). In our experiments, performance. A detailed explanation of our virtual node layer is provided in Appendix A.5 Combining CRA WL with message passing layers is left as future work.
use virtual nodes whenever this increases validation
We implemented CRAWL in PyTorch (Paszke et al. 2019 Fey & Lenssen 2019 Note that for a given graph we sample all m walks in parallel with a GPU-accclerated random walk generator. This process is fast enough to be done on-the-fly for each new batch instead of using precomputed random walks. Roughly 10% of the total runtime during training is spent sampling walks.
Asymptotic Runtime
We now compare the asymptotic runtime of CRAWI. to that of expressive MPGNNs and graph transformers. Neglocting the hidden dimension d, the runtime of applying the CNN in each CRAWL layer is O(m l s²). The window size is squared since it determines both the size of the walk features but also the receptive field of the CNN. The walk feature tensor uses memory in O(m f- (s + d)). Our default choice for training is m [V] and we usually choose such that [V| E > |E]. Therefore, the required time exceeds that of a standard MPGNN layer rumning in O(VV+ + [E)) Let us emphasize that this is a common drawback of architectures which are not bounded by 1-WT. For example, precomputing structural features with GSN Bouritsas et al. 2020) has a worst-case runtime in O( where k is the size of the considered subgraphs. Similarly, higher-order k-GNNs (Morris et al. 2020b have a runtime in ((IV)*) while methods based on usually have time and space requirement. in ((V(2). While random node initialization (Abboud et al. 2021 Sato et al. 2020 also strengthens the expressive power of MPGNNs beyond 1-WL, its empirical advantage is limited. With default values for m, l, and constant s 10, CRAWL scales with O(EE),, such that its complexity is comparable with standard MPGNN layers and smaller than both higher-order k-GNNs and graph transformers. Note though that the quadratic dependence on 8 will make CRAWL slower than standard MPGNNs in practice. We provide runtime measurements Table S in the appendix showing that CRAWL is mostly slower than simple message passing architectures and faster than the graph transformer SAN.
Graph Transformers (Dwivedi & Bresson 2020
3 Expressiveness
In this section, we report on theoretical results comparing the expressiveness of CRAWL with that of message passing graph neural networks. We prove that the expressiveness of the two architectures is incomparable, confirming our intuition that CRAWts detects fundamentally different features of graphs than GNNs. This gives strong theoretical argument for the use of CRAWL an alternative graph learning architecture, idcally in combination with GNNs to get the best of both worlds.
Intuitively, the additional strength of CRAWL has two different roots:
(i) CRAWi detects small subgraphs (of size determined by the window size hyperparameter s), whereas GNNs (at least in their basic form) cannot even detect triangles;
(ii) CRAWL detects long range interactions (determined by the window size and path length hyperpa- rameters), whereas GNNs are local with locality radius determined by the number of layers (which is typically smaller).
7

---

Published in Transactions on Machine Learning Research (08/2023)
While (ii) does play a role in practice, in our theoretical analysis we focus on (i). This has the additional benefit. that our results are independent of the number of GNN layers, making them applicable even to recurrent GNNs where the number of iterations can be chosen at runtime. Let us remark that (i) makes CRAWL similar to network analysis techniques based on motif detection (Alon 2007) and graph kernels based on counting subgraphs, such as the graphlet kernel (Shervashidze et al. 2009a) (even though the implementation of these ideas is very different in CRAWL...
Conversely, the intuitive advantage GNNs have over CRAWL is that locally, GNNs perform breadth-first search, whereas CRAWL searches along independent walks. For example, GNNs immediately detect the degree of every node, and then on subsequent layers, the degree distributions of the neighbors, and their neighbors, et cetera. While in principle, CRA can also detect degrees by walks that are returning to the same node multiple times, it becomes increasingly unlikely and in fact impossible if the degree is larger than the walk length. Interestingly, large degrees are not the only features that GNNs detect, but CRAW does not. We separate GNNs from CRAWE even on graphs of maximum degree 3.
It is known that the expressiveness of GNNs corresponds exactly to that of the 1-dimensional Weisfeiler- algorithm (1-WL) (Morris et al.) 2019 Xu et a.l. 2019). in the sense that two graphs are distinguished by 1-WL if and only if they can be distinguished by a GNN. It is also known that higher-dimensional versions of WT. characterize the expressiveness of higher-order GNNs (Morris et al. 2019h. Our main theorem states that the expressiveness of CRAWL and k- WLLL is incomparable.
Theorem 1.
(1) For every k 2 1 there are graphs of marimum degree 3 that are distinguishable by CRA WL with window size and walk length O(k²), but not by B- (and hence not by k-dimensional GNNs).
(2) There are graphs of maximum degree 3 that are distinguishable by 1- WL (and hence by GNNs), but not by CRAWL with window size and path length O(n), where n is the number of vertices of the graph.
We formally prove this theorem in Sections 3.1 and 3.2 To make the theorem precise, we first need to define what it actually means that CRAWL, as a randomized algorithm, distinguishes two graphs. To this end, we give a formal definition based the total variation distance of the distríbution of walk feature matrices that observe in the graphs. Our proof of assertion (1) assumes that the CNN filters used to process the features within a window a walk can be arbitrary multilayer percept and hence share their universality. Once this is settled, we can prove (1) by using the seminal Cai-Fürer- Cai-FFirer-lmmerma Immerman construction (Cai et al.) 1992) providing families of graphs indistinguishable by the WL algorithm. The proof of (2) is based on an analysis of random walks on a long path based on the gambler's ruin problem. Before we give the proof, let us briefly comment on the necessary window size and simple extensions of the theorem.
In practice, graph neural networks of order at most k = 3 are feasible. Thus, the window size and path length O(k²) required by CRAWL models to exceed the expressiveness of GNNs of that order (according to Assertion (1) of the theorem) is very moderate. It can also be shown that CRAWL, with a window size polynomial in the size of the graphlets is strictly more expressive than graphlet kernels. This can be proved similarly to Assertion (1) of Theorem
Let us remark that the expressiveness of GNNs can be considerably strengthened by adding a random node initialization (Abboud et al.) 2021 Sato et al. 2020). The same can be done for CRAWL, but so far the need for such strengthening (at the cost of a higher variance) did not arise. Besides expressiveness, fundamental aspect of the theory of machine learning on graphs is invariance (Maron et al. 2019b). So let us briefly comment on the invariance of CRAWL computations. A CRAWL model represents a random variable mapping graphs into a feature space Rd, and this random variable is invariant, which means that it only depends on the isomorphism type of the input graph. By independently sampling more walks we can roduce the variance of the random variable and converge to the invariant "truc" function value. Note that this invariance of CRAWL is the same as for other graph learning architectures, in particular GNNs with random node initialization (see Abboud et al. 2021
8

---

Published in Transactions on Machine Learning Research (08/2023)
Notation Let us first recall the setting and introduce some additional notation. Throughout the proofs, we assume that the graphs are undirected, simple (that is, without self-loops and parallel edges) and unlabeled. All results can easily be extended to (vertex and edge) labeled graphs 2 results only become stronger by restricting them to the subclass of unlabeled graphs. We further assume that graphs have no isolated nodes, which enables us to start a random walk from every node. This makes the setup cleaner and avoids tedions case distinctions, but again is no serious restriction.
In fact, the (harder) inexpressivity
We denote the node set of a graph G by V(G) and the edge set by E(G). The order |G] of G is the number of nodes, that is, |G] == [V()). For a set X S (G), the induced subgraph G[X] is the graph with node set X and edge set {ew E E(G) D W E X). A walk of length E in G is sequence W = (wo...., we) E V(G) such that w;-100; E E(G) for 1 S i S E. The walk is non-backtreed non-backkracking if for < i < E we have Wi41 F wi-1 unless the degree of vertex Wy is 1.
Distinguishing Graphs Before we prove the theorem, let us precisely specify what it means that CRAWL distinguishes two graphs. Recall that CRAWL has three (walk related) hyperparameters:
the window size 8;
the walk length E;
the sample size m.
Recall furthermore that with every walk W = (wo...., we) we associate a walk feature matriz X E [((+ (=)--))) For S i issa e, the first d entries of the i-th row of X describe the current em- bedding of the node wi, the next d' entries the embedding of the edge w4-1 (0 for 0), the following entries are indicators for the equalities between w; and the nodes wi-j for j = 1, 1,..,, 8 (1 if w; = Wi-j, 0 if i-j < 0 or w, o W)-s). and the remaining s entries are indicators for the adjacencies between w, and the nodes Wi-j for j == 8 (1 if Wi, Wi-j are adjacent in G, 0 i- 0 or w;, Wi-j are non-adjacent; note that Wi, wi-1 are always be adjacent because W is a walk in G). Since on unlabeled graphs initial node and edge embeddings are the same for all nodes and edges by definition, those embeddings cannot contribute to expressivity. Thus, we can safely ignore these embeddings and focus on the subgraph features encoded in the last 2s 1 1 columns. For simplicity, we regard X as an (E 1) (2s - 1) matrix with only these features in the following. We denote the entries of the matrix X by X,,j and the rows by X,,.. So X, (X., -1229-1)) 10,1)22-1 We denote the walk feature matrix of walk W in graph G by W). The following observation formalizing the conncction between walk-induced subgraphs and rows in the matrix X is immediate from the definitions.
Observation 1. For all wolks W = (wi...., we), W' = (w'...., w/) in graphs G, G' with feature matrices = X(G, W), X' = X(",, W"), we have:
(1) if XI-,,- = =X--j-- for j = O,.... s - then the mapping Wi-j + whi for j = O,..., is on isomorphism from the induced subgraph Gl(w;-; j o,...,s} s]] to the induced subgroph G'
j 8))..,
(2) if the mapping Wi-j - wh_s for j 0,...,22 2s 1 is an isomorphism. from the induced subgraph Cliwi-j j O....,
... 25 1H1 to the induced subgraph G'(w',,, j O...., 2s 1}}, then Xi-i-- x X for j = -
The reason that we need to include the verlices wi-2s+1;--- wi-s and w/-20+11.... w/_. into the sub- graphs in (2) is that row Xi-st1,- of the feature matrix records edges and equalities between wi-s+1 and Wi-28+15-- Wi-sr
For every graph G we denote the distribution of random walks G starting from node chosen uniformly al random by W(G) and (G) for the non-backtracking walks. We let X()) and (G) be the push-forward
2t. possible to simulate directed edges and parallel edges through edge labels and loops through mode labels.
9

---

Published in Transactions on Machine Learning Research (08/2023)
distributions on {0, (2(1)))(((2111 that is, for every X {0, (0.1))++1x((2=-)) we let
Pr (X) Pr ((W) X(G, W) = =x}) ((G) W(G)
A CRAWL run on G takes samples from X(G). So to distinguish two graphs G, CRAWL must detect that the distributions ((G)) are distinct using m samples.
As a warm-up, let. us prove the following simple result.
Theorem 2. Let G be cycle of length n and G' the disjoint union of two cycles of length n/2. Then G and G' connot be distinguished by CRAWC with window size s < n/2 (for any choice of parameters E and m).
Proof. With a window size smaller than the length of the shortest cycle, the graph CRAWL sees in its window is always a path. Thus, for every walk W in either G or G' the feature matrix X(W) only depends on the backtracking pattern W. This means that X(G) x
It worth noting that the graphs G, G" of Theorem can be distinguished by 2-WL (the 2-dimensional Weisfeller-Lemat algorithm), but not by 1-WL.
Proving that two graphs G,G G' have identical featuro-matrix distributions X(G) (G') in Theorem 2 is the ultimate way of proving that they are not distinguishable by CRAWL Yet, for more interesting graphs, we rarely have identical feature-matrix distributions. However, if the distributions are sufficiently close, we will still not be able to distinguish them. This will be the case for Theorem | (2). To quantify closeness, we use the total variation distance of the distributions. Recall that the total variation distance between two probability distributions D, D' on the same finite sample space is
distrv (D, D') = max Pr(S) - Pr(()).
SCQ D
D'
It is known that the total variation distance is half the e didistance between the distributions, that is,
1
distTy(D,D')
D
D111
2
1
Σ
Pr((w]) - -Pr((w))
2
D
D
WER
Let >> O. We say that two graphs G, G' are e-indisslinguisshble by CRAWL with window size 8, walk length L, and sample size if
distrv(X((G, E
(1)
m
The rationale behind this definition that if distry (XG), m matrices that CRA WL may want to use distinguish the graphs, the expected numbers of samples with this property that CRAWL sees in both graphs are close together (assuming is small).
c. then for every property of feature
Often, we want to make asymptotic statements, where we have two families of graphs (Ga)n21 and (G) typically of order |G,l = |G,, = O(n), and classes S, L, M of functions, such as the class O(log n) of logarithmic functions or the class o(1) polynomial functions. We say that (Gn)221 and (G', (22))2 are indistänguushable by CRAWI, with window size S, walk length L., and sample size M for all and all E S. f L, m E M there is an n such that Gn: G", are e-indistinguishable by CRAWL with window size s(n), walk length {(n), and sample size m(n).
We could make similar definitions for distinguishaabiitt, but we omit them here, because there is asy asymmetry between distinguishabilty and indistinguishability. To understand this, note that our notion of indistinguisha- bility only looks at the feat ures that are extracted on the random walks and not on how these features are processed by the ID CNNs. Clearly, this ignores an important aspect of the CRAWL architecture. However, we would like to argue that for the results presented here this simplification is justified; if anything makes the results stronger. Let us first look at the inexpressibility results (Theorem | (2) and Theorems and 5p. A prerequisite for CRA Wt. to distinguish two graphs is that the distributions of urat observed on these
10

---

Published in Transactions on Machine Learning Research (08/2023)
graphs are sufficiently different, so our notion of indistinguishabiliy that just refers to the distributions of features yields stronger notion of indistinguishablli, (indistinguisabbiity in the featureddisributtonn sense implies indistinguishaabiitty in CRAWL). This means that our the indistinguishability results also apply to the actual CRAWi architecture.
For the distinguishability, the implication goes the other way and we need to be more careful. Our proof of Theorem (1) (restated as Theorem 3 in the next section) does take this into account (see the discussion immodiately after the statement of Theorem 3
3.1 Proof of Theorem 1 (1)
Here is a precise quantitative version of the first part of Theorem 1.
Theorem 3. For all k 2 1 there are graphs Gk. H& of order O(k) such that CRAWL with window size Ok2), walk length & = O(k²), and sample size distinguishes G& and Hy with probability at least
1 1 (2)) while k- WL (and hence k-dimensional GNNs) fails to distinguish G5 and Hy.
To prove the theorem we need to be careful with our theoretical model of distinguishability in CRAWI. It turns out that all we ever need to consider in the proof is the features observed within single window of CRAWL. These features can be processed at once by the filter of the CNN. We assume that these filters can be arbitrary multilayer perceptrons (MLP) and hence share the universality property of MLPs that have at least one hidden layer: any continuous function on the compact domain [0, 1] (where d is the number of all features in the feature matrix X within a single window) can be approximated to arbitrary precision. While this is a strong assumption, it is common in expressivity results, e.g. (Xu et al. 2019
In order to find pairs of graphs that WL is unable to distinguish, we do not need to know any details about the Weisfeiler-Leman algorithm (the interested reader is deferred to (Grohe) 2021 can use the following well-known inexpressibilityy result as a black box.
Kieler 2020 ). Instead, we
Thcorem 4 (Cai et al. (1992). ) For all l: there are graphs Gk, H2 such that |G& = |H O(k), the graphs G3 and HA are connected and 3-regular, and k- WL cunnot dislinguish G2 and Hy.
Proof of Theorem 3 We fix k 2. 1. Let Gg, Hy be non-isomorphic graphs of order O(k) that are connected, 3-regular, and not distinguishable by l-WL. Such graphs exist by Theorem 4
Let n = :==]GK] | and nole that the number of edges of G5 and H& is (3/2)m, because they are 3-regular. It is a well-known fact that the cover time of a connected graph of order n with m edges, that is, the expected time it takes a random walk starting from a random node to visit all nodes of the graph, is bounded from above by 4nm (Aleliunas et al. 1979). Thus, in our graphs G2, H2 the cover time is 6n?. Therefore, by Markov's inequality, a walk of length 12n² visits all nodes with probability at least 1/2.
We set the walk length & and the window size to 12n Since is O(k), this is O(k2).
Consider a single walk W = (wo....,,z)) of length e in a graph F E {Ge, Hx), and assume that it visits all nodes, which happens with probability at least 1/2 in either graph. Then the feature matrix X = X(F, W), which we see at once in our window of size 8 = 6, gives us a representation of the graph F. Of course, this representation depends on the specific order in which the walk traverses the graph. What this means is that if for two graphs F, F' and walks W, W visiting all nodes of their respective graphs we have X(F, X(F', W'), then the graphs F, F' are isomorphic. This follows immediately from Observation 1 Note that the converse does not hold.
Since the above will rarely happen, we now define three sets of feature matrices that we may see:
Rg = (X W) W walk G2 visiting every vertex].
RH = (H2, W) W walk on Ha visiting every vertex),
S = (X W) | F E (Gx, H&), W walk on F not visiting every vertex].
Observe that. because we chose the walk length l and the window size s large enough have:
11

---

Published in Transactions on Machine Learning Research (08/2023)
G3
G's
Figure 3: The graphs G3 and G3y in the proof of Theorem 3 with their stable coloring computed by 1-WL
for every walk on a graph F E {Gk, Hx), the feature matrix X that we see belongs to one of the three sets, and with probability at least 1/2 it belongs to Rg or RH;
the three sets RG; Ru,S S are mutually disjoint. For the non-isomorphic graphs Gk, H& we can never have (G,, W) = X (H&,, W") such that walk visiting all nodes will end up in the corresponding set RG or RR Through the equality features one can count the number of nodes visited in W, distinguishing S from both Rg and Rg.
Thus, if we sample walk from Gk, with probability at least 1/2 we see a feature matrix in RG, and if we sample from Hk, we can never see matrix in RG. Let f [0, 1] (2=--)) - [0. 1] be a continuous function that maps every feature matrix X E (0, 10.1)/0 ((((4))((2-11 to 1 if X E Ra and to O if X E Ru U.S
Let us now run CRAWL on a graph F' E {Gk, HxJ. Since the window size s equals the walk length E, CRAWL sees the full feature matrix (FF, W) in a single window. Thus, by the universality of the CNN filters, it can approximate the function that checks whether a given feature matrix belongs to RG up to an additive error of 1/3, allowing us to simply use f as we can distinguish both cases independent of the error due the approximation. We know that if run CRAWL on F Gk, with probability at least 1/2 it holds that X(F, W) Rg and thus f(X (F, W)) =1 1. Otherwise, f(X(F, W)) O with probability 1 as the three sets are disjoint. Hence, CRAW WI. run based on a single random walk W distinguishes the two graphs G₁ and Ha with probability at least 1/2. By exploiting that the error is one-sided and repeating the above argument m times, one can distinguish the two graphs with probability 1 1- (4)" using m independent random walks. By simply relying on the universality of MLPs in this final step, the size of the CNN filter is exponential in k. This is not a limitation in this context, since k- WL also scales exponentially in However, in Appendix C we argue that with more careful analysis the size of the MLP can actually be shown to have polynomial upper bound.
We note that while the proof assumed that the random walk covered the whole graph and in addition the window size is chosen to encompass the complete walk, this is neither feasible nor necessary in practice. Instead, the theorem states that using a window size and path length of O(k²), CRAWL can detect differences in graphs which are inaccessible to k-GNNs. This is applicable to graphs of arbitrary size where the path of fixed size O(k2) (typically 1 < 3 as R-GNNs scale in n²) is no longer able to cover the whole graph. In contrast to the theorem where a single walk (covering the whole graph) could suffice to tell apart two graphs, one needs multiple walks to distinguise inguish the difference in the distributions of walks on real-world graphs as outlined earlier in this section.
3.2 Proof of Theorem 1 (2)
To prove the second part of the theorem, it will be necessary to briefly review the 1-dimensional Weisfeiler- Leman algorithm (1-WL), which is also known as color refinement and as naive node classification. The algorithm iteratively computes a partition of the nodes of its input graph. It is convenient to think of the classes of the partition as colors of the nodes. Initially, all nodes have the same color. Then cach itcration step, for all colors e in the current coloring and all nodes v, w of color e, the nodes and get different colors in the new coloring if there some color such that and w have different. numbers of neighbors of
12

---

Published in Transactions on Machine Learning Research (08/2023)
color d. This refinement process is repeated until the coloring is stable, that is, any two nodes v, of the same color have the same number of neighbors of any color d. We say that 1-WL, distinguishes two graphs G' if, after rumning the algorithm on the disjoint union G s G' of the two graphs, in the stable coloring of G w G' there is a color e such that G and G' have a different number of nodes of color c.
For the results so far, it has not mattered we allowed backtracking or not. Here, makes a big difference. For the non- backtraktgg version, we obtain a stronger result with an easier proof. The following theorem is precise quantitative statement of Theorem 1 (2).
Theorem 5. There are families (Gm)n21, (G))n21 of graphs of order |Gul = |G,, = -3n with the following properties.
(1) For all n 2 1, 1-WL distinguishes Gn and G',.
(2) (Gn)a21; (G" h221 are indistinguushable by the non-backtrucking version of CRA WL with window size s(n) = o(n) (regardless of the walk length and sample size).
(3) (G.)n21 (22) are indistinguishable by CRAWL with walk length f(n) O(n), and samples size m(n)= = n (1)) (regardless of the window size).
Proof. The graphs Gn and G² both consist of three internally disjoint paths with the same endnodes x and y. In Gn the lengths of all three paths is n. In G,,, the length of the paths is n 1, n + 1 (sec Figure
It is easy to see that 1-WL distinguishes the two graphs.
To prove assertion (2), let = 2n - 3 be the window size. Then the length of the shortest cycle in Gn, G is 8 + 2. Now consider a non-backtracking walk W (Wi,..., we) in either Gn or G,, (of arbitrary length f). Intuitively, CRAWi, only sees a simple path within its window size independent of which graph W is sampled from and can thus not distinguish Gn and G²2 Formally, for all and j with i- 8 S j < we have w; * wy, and unless i I, there no edge between wi and wy. Thus, X X(W) X(W) for all walks W of the same length l, and since it does not matter which of the two graphs G2,; G¹, the walks are from, it follows that Xns(Gn) Xns (G)))
To prove assertion (3) use the fact that random walks of length ((n) are very unlikely to traverse a path of length at least - from to y. It is well known that the expected traversal time is O(n²) (this follows from the analysis of the gambler's ruin problem). However, this does not suffice for us. We need to bound the probability that a walk of length ((n) is a traversal. Using a standard, Chernoff type tail bound, it is straightforward to prove that for every constant e 2 0 there is a constant d 2 I such that the probability that random walk of length en in either Gn or G", visits both x and y is at most exp(-n/d). As only walks visiting both x and y can differentiate between the two graphs this gives us an upper bound of exp(-n/d) for the total variation distance between (G... and (CC).).
Let us note that a bound on the walk length in assertion (3) of the previous theorem is necessary because the backtracking version of CRAWL with sufficiently long paths does seem to have the ability to distinguish the graphs Gn, G,, even with constant size windows. The intuitive argument is as follows: we first observe that, by going back and forth between a node and all its neighbors within its window, CRAWL can distinguish the two degree-3 nodes x, from the remaining degree-2 nodes. Thus, the feature matrix reflects traversal times between degroe-3 nodes, and the distribution of traversal times is different in G, and G¹,- With sufficiently many samples, CRA WL can detect this. We leave it future research to work out the quantitative details of this argument.
4 Experiments
We evaluate CRAWL on a range of standard graph learning benchmark datasets obtained from Dwivedi et al. (2020). Hu al. (2020), and Dwivedi et al. (2022). In Appendix B we provide additional experimental results on the TUDataset Morris et al.) (2020a) and a direct comparison to Subgraph GNNs on the task of counting
various substructures in synthetic graphs (Zhao et. al. 2022
13

---

Published in Transactions on Machine Learning Research (08/2023)
4.1 Datasets
From the OGB project (Hu et al., 2020 , we use the molecular property prediction dataset MOLPCBA with more than 400k molecules. Each of its 128 binary targets states whether a molecule is active towards a particular bioassay (a method that quantifies the effect of a substance on a particular kind of living cells or tissues). The dataset is adapted from MoleculeNet. (Wu et al., 2018) and represents molecules as graphs of atoms. It contains multidimensional node and edge features which encode information such as atomic mumber and chirality. Additionally, it provides a train/val/tost split that separates structurally different types of molecules for a more realistic experimental setting. On MOLPCBA, the performance is measured in terms of the average precision (AP). Further, we use four datasets from Dwivedi et al.) (2020). The first dataset ZINC is molecular regression dataset. It is subset of 12k molecules from the larger ZINC database. The aim is to predict the constrained solubility, an important chemical property of molecules. The node label is the atomic number and the edge labels specify the bond type. The datasets CIFARIO and MNIST are graph datasets derived from the corresponding image classification tasks and contain 60k and 70k graphs, respectively. The original images are modeled as networks of super-pixels. Both datasets are 10-class classification problems. The last dataset CSL syuthetic dataset containing 150 Cyclic Skip Link graphs (Murphy et al., 2019.. These are 4-regular graphs obtained by adding cords of fixed length to cycle. The formal definition and example are provided in the appendix. The aim is to classify the graphs by their isomorphism class. Since all graphs are 4-regular and no node or edge features are provided, this task is unsolvable for standard MPGNNs.
We conduct additional experiments on the long-range graph benchmark (wiieedi et al. 2022 which is a collection of datasets where capturing long-range interaction between vertices is crucial for performance. We use three long-range datasets: PASCALVOC-S is an image segmentation dataset where images are represented as graphs of superpixels. The task is a 21-class node classification problem. To apply CRAWL to this task we omit the pooling step and directly feed each vertex embedding into the classifier. PEPTIDES-FUNT and AEPTIEES-STRCCT model 16k peptides as molecular graphs. PEPTIDES-FUNC is a multi-class graph classification problem with 10 binary classes. Each class represents a biological function of the peptide. PEPTIDES-STRUCT aims to regress 11 molecular properties on the same set of graphs.
4.2
Experimental Setting
We adopt the training procedure specified by Dwivedi et al. (2220). In particular, the learning rate is initialized as 10-3 and decays with factor of 0.5 if the performance on the validation set stagnates for 10 epochs. The training stops once the learning rate falls below 10-5, 6, Dwivedi et al. (2020) also specify that networks need to stay within parameter budgels of either 100k or 500k parameters. This ensures fairer comparison between different methods. For MNIST, CIFAR1O, and CSL we train CRAWL models with the smaller budget of 100k since more bascline results are avaílable in the litcrature. The OGB Project (Hu et al.] 2020) does not specify a standardized training procedure or parameter budgets. For MOLPCBA, we train for 60 epochs and decay the learning rate once with a factor of 0.1 after epoch 50. On the long-range datasets PASCALVOC-SP PEPTIDES-PUNC, and PEPTIDES-STRUCT we use the 500k parameter budget and found it helpful to switch to cosine annealing schedule for the learning rate. For all datasets we use a walk length of L = 50 during training. For evaluation we increase this number to f = 150, except for MOLPCBA where we use f = 100 for efficiency. The window size s was chosen to be 8 for all but the long-range datasets where we increased it to 16 to capture further dependencies.
All hyperparameters and the exact number of trainable parameters are listed in the appendix. We observed that our default setting of e 50 and s to be robust initial setting across all datascts. When we observed overfitting, decreasing the number of walks turned out to be simple and effective measure to improve performance. In molecular datasets a window size of at least 6 is required to detect aromatic rings and in our ablation study in Section 5 we observe a clear performance drop on the molecular dataset ZINC when reducing- s below 6.
For each dataset we report the mean and standard deviation across several models trained with different random sceds. We follow the standardized procedure for each dataset and average over 10 models for MOLPCBA, models for ZINC, CIFAR10, and MNIST and 4 models for PASCALVOC-SP, PEPTIDES- FUNC, and PEPTIDES-STRUCT. During inference, the output of each model depends on the sampled
14

---

Published in Transactions on Machine Learning Research (08/2023)
Table 1: Performance achieved on ZINC, MNIST, CIFARIO, and MOLPCBA. A result marked with "f" indicates that the parameter budget was smaller than for CRAWL and "*" marks results where parameter budget was reported. We highlight the best results in bold and consider results with overlapping standard deviations statistically equivalent.
METHOD
ZINC TEST MAE
MNIST
CIFAR1O
MOLPCBA TEST AP
TEST Ace (%6
TEST Ace (%)
GIN
0.526 + 0.051
96.485 + 0.252
55.255 + 1.527
0.2703 + 0.0023
LEADERBOARD
GRAP GRAPESAGE
0.398 1 0,002
97.312 + 0.097
65.767 + 0.308
GA1
0.384 + 0,007
95.535 + 0.205
64.223 + 0.455
GCN
0.367 - 0.011
90.705 + 0.218
35.710 + 0.381
0.2483 + 0.0037
3W LGNN
0.303 - 0.068
95.075 + 0.961
59.175 _ 1.593
GATEDGUN
0.214 _ 0.006
97.340 + 0.143
67.312 + 0.311
PNA
0.142 + 0.010
97.940
0.120
70.350 + 0.630
0.2838 + 0.0035
GINE+
0.2917
0.0015
DGN
fo.168 1 0.003
72.840 + 0.420
ПIMP
*0.151 1 0.006
OTHER
GSN
*0.108 + 0.018
SAT
0.094 - 0.008
SAN
0.139 + 0.006
0.2765
0.0042
CIN
0.079 = 0.006
NISTED CIN
0.2832
0.0041
GIN-AK+
0.080 + 0.001
72.190 + 0.130
0.2930
0.0044
OUR
CRAWL.
0.085 + 0.004
97.944 + 0.050
69.013 + 0.259
0.2986 + 0.0025
random walks. Thus, each model's performance is given by the average performance over 10 evaluations based on different random walks. This internal model deviation, that is, the impact of the random walks on the performance, is substantially lower than the differences between models. We thus focus on the mean and standard deviation between CRAWL models when comparing to other methods. the appendix we provide extended results that additionally specify the internal model deviation.
4.3 Baselines
We compare the results obtained with CRAWL to a wide range of graph learning methods. Our main baselines are mumerous message passing GNN and Graph Transformer architectures that have been proposed in recent years (see Section 1.1 We report values as provided in the litcrature and official leaderboard, For a fair and direct comparison, we exclude results of ensemble methods and models pre-trained on additional data.
4.4 Results
Table 1 provides our results ZINC, MNIST, CIFAR10, and MOLPCBA. On the ZINC dataset, CRA achieves an MAE of 0.085. This is approximately a 40% improvement over the current best standard MPGNN (PNA) on ZINC. The result is on par (within standard deviation) of Cellular GNNs (CIN) (Bodnar et al. p021 and "GNN as Kernel" (GIN-AK+) (Zhao el al., 2022). which are stale of the art on ZINC. CRA WL.' performance on the MNIST dataset on par with PNA (within standard deviation), which is also the state of the art on this dataset. On CIFAR1O, CRAWL achieves the fourth-highest. accuracy among the compared approaches. On MOLPCBA, CRAWL yields state-of-the-an results and improves upon all compared architectures. We note that the baselines include architectures strictly stronger than 1-WL, such as Nested GIN (Zhang & Li 2021). CRAWL yields better results, indicating that the WL-incomparability does not keep our method from outperforming higher-order MPGNNs.
"Leaderboards: http::///..oggo...oooooc.cccocaa http http:////w.aaaaaa/o/////////a//a
http:///eederrrgrprrrooooo www.ggrappppppooo
15

---

Published in Transactions on Machine Learning Research (08/2023)
Table 2: Performance on the PASCALVOC-SP, PEPTIDES-FUNC, and PEPTIDES-STRUS datasets
from the Long-Range Graph Benchmark. Bascline results reported by Dwivedi et al. 2022
METHOD
PASCALVOC-SP
PEPTIDES-FURE TEST AP
PEPTIDES-STRU TEST MAE
TEST F1
GCN
0.1268 + 0.0060
0.5930 + 0.0023
0.3496 + 0.0013
GINE E
0.1265 = 0.0076
0.5498 = 0.0079
0.3547 = 0.0045
GATEDGCN
0.2873 0.0219
0.6069 = 0.0035
0.3357 0.0006
TRANSFORMER
0.2694 = 0.0098
0.6326 = 0.0126
0.2529 + 0.0016
SAN
0.3230 0.0039
0.6439 = 0.0075
0.2545
0.0012
CRAWL
0.4588 + 0.0079
0.7074 + 0.0032
0.2506 + 0.0022
Table 3: Test accuracy achieved on CSL with and without Laplacian eigenvectors (Dwivedi el al. 2020). As these node features already encode the solution, unsurprisingly most models perform well.
METHOD
CSL
CSL+LAP
TEST Acc (%)
TEST Acc (%)
GIN
< 10.0
99.333 + 1.333
GRAPHSAGE
< 10.0
99.933 = 0.467
GAT
S 10.0
99.933 = 0.467
GCN
< 10.0
100.000 = 0.000
3WLGNN
95.700
14.850
30.533 = 9.863
GATEDGCN
I 10.0
99.600 + 1.083
CRAWL
100.000 0.000 100.000 1 0.000
Table 2 provides the results obtained for the long-range graph benchmark datasets. CRAW WL achieves state- of of-the-art performance all three datasets. On PASCALVOC-SP and PEPTIDES-FUNC our architecture is able to improve the previous best result by 13 and 6 percentage points respectively. The margin on PEPTIDES-STRUS
is less significant, but CRAWL is still able to yield the lowest MAE compared to both GNNs and Graph Transformers. These results validate empirically that CRAWL is able to capture long-range interaction between nodes through the use of random walks.
The results on CSL are reported in Table We consider variants of CSL, the pure task and an easier variant in which node features based on Laplacian eigenvectors added as suggested by DDwivedi al. (2020). Already on the pure task, CRAWL achieves accuracy of 100%, none of the CRAWE models misclassified a single graph in the test folds. 3WLGNN is also theoretically capable of solving the pure task and achieves almost 100% accuracy, while MPGNNs cannot distinguish the pure 4-regular CSL graphs and achieve at most 10% accuracy. With Laplacian features that essentially encode the solution, all approaches (except 3WLGNN) achieve results close to 100%. Thus, the CSL dataset showcases the high theoretical expressivity of CRAWL. High expressivity also helps in subgraph counting which is effectively solved by both CRAWI. and subgraph GNNs such as GIN-AK+ shown in Appendix B.4 In contrast, pure MPGNNs are theoretically and practically unable to count anything more complicated than stars and even counting those seems to be challenging in practice.
Overall, CRAWI performs very well on a variety of datasets across several domains.
5
Ablation Study
We perform ablation study to understand how the key aspects of CRAWL. influence the empirical performance. We aim to answer two main questions:
How useful are the identity and adjacency features we construct for the walks?
16

---

Published in Transactions on Machine Learning Research (08/2023)
Table 4: Results of our ablation study. Node features FV, edge features FE, adjacency encoding A, and identity encoding Walk strategics no-backtrack (NB) and uniform (UN).
FEATURES
WALKS
ZINC (MAE)
MOLPCBA (AP)
CSL (Acc)
FV + FV +F
UN
0.19768 0.01159
0.28364 + 0.00201
0.06000 0.04422
NB
0.15475 +: 0.00350
0.29613 1 0.00209
0.06000 + 0.04422
FV *++E++A FV **#**+A
UN
0.10039 + 0.00514
0.97467 + 0.02587
NB
0.08656 + 0.00310
0.99933 + 0.00133
+F
UN
0.10940 + 0.00698
0.70733 + 0.07658
+V+F++1
NB
0.09345 = 0.00219
0.97133 = 0.00859
+*+E++I+A
UN
0.09368 + 0.00232
0.28522 + 0.00317
0.96267 = 0.02037
D'+FE+I+A
NB
0.08456 0.00352
0.29863 1 0.00249
1.00000 0.00000
How do different strategies for sampling random walks impact the performance?
How do window size and the number of walks m influence the performance?
Here, we use the ZINC, MOLPCBA, and CSL datasets to answer these questions empirically. We trained multiple versions of CRAWI, with varying amounts of structural features used in the walk feature matricos. The simplest version only uses the sequences of node and edge features without any structural information. For ZINC and CST, we also train intermediate versions using either the identity the adjacency encoding, but not both. We omit these for MOLPCBA to save computational resources. Finally, measure the performance of the standard CRAWL architecture, where both encodings are incorporated into the walk feature matrices. For each version, we compute the performance with both walk strategies.
On each dataset, the experimental setup and hyperparameters are identical to those used in the previous experiments on both datasets. In particular, we train five models with different seeds and provide the average performance as well as the standard deviation across models. Note that we repeat the experiment independently for each walk strategy. Switching walk strategics between training and evaluation does not yield good results.
Table 4 reports the performance of each studied version of CRAWL. On ZINC, the networks without any structural encoding yield the worst predictions. Adding either the adjaconcy or the identity encoding improves the results substantially. The best results are obtained when both encodings are utilized and non-backtracking walks are used. On MOLPCBA, the best performance also obtained with full structural encodings. However, the improvement over the version without the encodings is only marginal. Again, non-backtracking walks perform significantly better than uniform walks. On CSL, the only version to achieve perfect accuracy of 100% is the one with all structural encodings and non-backtracking walks. Note that the version without any encodings can only guess on CSL since this dataset has no node features (we are not using the Laplacian features here).
Overall, the structural encodings of the walk feature matrices yield measurable performance increase on all three datascts. However, the margin of the improvement varios significantly and depends on the specific dataset. For some tasks such as MOLPCBA, CRA WL yields highly competitive results even when only the sequences of node and edge features are considered in the walk feature matrices.
Finally, the non-backtracking walks consistently outperform the uniform walks. This could be attributed to their ability to traverse sparse substruct ures quickly. On sparse graphs with limited degree such as molecules, uniform walks will backtrack often. Thus, the subgraphs induced by windows a fixed size s on uniform walks tend to be smaller than for non-backtracking walks. This limits the method's power to evaluate local substructures and long-ram longerange dependencies. On all three datasets used in this ablation study, these effects seem to cause a significant. loss in performance.
17

---

Published in Transactions on Machine Learning Research (08/2023)
10
16
MAE -102
MAE -102
9.5
12
9
10
8.5
8
8
6
0.2
0.4
0.6
0.8
Window Size s
m/[V|
(a) Test MAE for different window sizes s.
(b) Test MAE for different numbers walks m.
Figure 4: Ablation on the ZINC dataset. We study the influence of and m on the test MAE.
5.1 Influence of and m
Let us further study how the values of the window size s and the number of sampled walks m influence the empirical performance of CRAWL. Generally, we expect performance to improve as both parameters increase: Larger window sizes s allow the model to view larger structural features as the expected size of the induced subgraph increases, while a larger number of walks ensures a more reliable traversal of important. features. To test this hypothesis, we conduct an additional ablation study on the ZINC dataset.
the model performance. To this end, we train models with varying window sizes of E {0, 2, 4, 6, 8, 10} while all other parameters remain as in our main experiment where we used s = We train 3 models for each s and provide the mean test MAE as function of in Figure 4(a) We observe that the performance improves monotonically as increases. The decrease in MAE is especially significant between s = and s = 6. This jump can explained by the importance of benzene rings in organic molccules and in the ZINC dataset particular. A window of size s these structures, which explains the strong improvement around this threshold. The performance saturates around and is not improved further for 10. Secondly, the trained models from our main experiment and evaluate them the test split of ZINC with different numbers of walks m. We vary the number of walks m p- |V] where p E f0.2, 4. 0.6, 0.8, 1.0} and [V is the number of vertices in a given lest graph. All other parameters are unchanged. Figure [(b] provides the mean test MAE as a function of p. The error decreases monotonically for larger values of m, as predicted. The improvement from m = V. to m = [V] is marginal. We note that the walk length é has a similar effect on the performance the product m l determines how densely a graph is covered in walks. In this ablation study the walk length is fixed é 150 during inference, in our main experiment.
First, evaluate the effect of
insufficient to detect
aim quantify the effect of m. We use
Overall, we conclude that our hypothesis seems to hold as larger values for and m seem to improve performance.
6 Conclusion
We have introduced a novel neural network architecture CRAWi for graph learning that based on random walks and 1D CNNs. We demonstratod the effectiveness of this approach on a varioty of graph level tasks which is able to outperform or at least. match state-of-the-art GNNs. On a theoretical level, the expressiveness of CRAWL is incomparable to the Weisfeiler- hierarchy which bounds standard message passing GNNs. By construction, CRAWI can detect arbitrary substructures up to the size of its local window. Thus CRA WL is able to extract useful features from highly symmetrical graphs such as the 4-regular graphs of CSL on which pure MPGNNs fail due to the lack of expressiveness. This way random walks allow CRA Wi. to escape the Weisfeiler- Leman hierarchy and solve tasks that are impossible for MPGNNs.
CRAWL can be viewed as an attempt to process random walks and the structures they induce with end-to-end neural networks. The strong empirical performance demonstrates the potential of this general approach.
18

---

Published in Transactions on Machine Learning Research (08/2023)
However, many variations remain to be explored, including different walk strategies, variations in the walk features, and alternative pooling functions for pooling walklet embeddings into nodes or edges. Since our CRAWL layer is compatible with MPGNNs and also with Graph Transformers, it raises the question of what would happen we combine all three techniques as all three methods focus on different aspects of the graph structure. Through unified architecture that for example runs all three aggregation methods parallel we would thus anticipate performance gain due to synergies. Beyond plain ID-CNNs, other deep learning architectures for sequential data, such as LSTMs or sequence transformers, could be used to process random walks. Furthermore, extending the experimental framework to node-level tasks and motif counting would open new application areas for walk-based approaches. In both cases, one needs to scale CRA WI. to work on individual large graphs instead of many medium-sized ones, Next to the combination of the full CRA Wt. layer with other techniques, its components such as the adjacency encoding could help improving other existing models based on processing subgraphs or random walks.
References
Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Monttreal Canada, 19-27 August 2021, pp. 2118-2118. ijeai.org, 2021. doi: 10.24963/ /ijcai.200) /221/ URL https //doi :aci.orz otg/10. 10/
/291.
R. Alcliunas, R.M. Karp, R.J. Lipton, L. Lovász, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problem. In FOCS79, pp. 218 223, 1979.
Uri Alon. Network motifs: theory and experimental approaches. Nature Reviews Genetics, 8:450-466 2007. doi: 10.1038/nrg
Pablo Barceló, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (ods.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NearIPS 2021, December 6-14, 2021, virtual, pp. 25280 25293, 2021.
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Lió. Directional graph networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 748-758. PMLR, 2021. URL http://proceedinggi mlr haar.prressv339 beani21a. htmll
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamuru- gan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URI.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Newral Information Processing Systems, volume 34, pp. 2625 2640. Curran Associates, Inc., 2021. URL https://proceeeing.eeeeeeee httprrppps.cpppppe/22/////// 457792444499990077883300224----4 .dff
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006. 09252, 2020.
Rémy Brossard, Oriel Frigo, and David Dehacne. Graph convolutions that can finally model local structure. Xixiv preprint ar arXiv:2011.1506; 2020.
J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinalorica, 12:389-411 -400 1992.
19

---

Published in Transactions on Machine Learning Research (08/2023)
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pp. 1469-3489 PMT.R, 2022.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Adronces in Neural Information Pro- cessing Systems, volume 33, pp. 10383-10395. Curran Associates, Inc., 2020. URL httpps:/ .dff
neurips.cc/papee /etpppppccc/appee...aaa/////aaaa
Francois Chollct. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE Conference on Compuler Vision and Pallern Recognilion (CVPR); July 2017.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velickovic. Principal neigh- bourhood aggregation for graph nets. In Hugo Larochelle, Marc'Aurela Ranzato, Raia Had- scll, Maria-Florina Balcan, and Hsuan-Tien Lin (ods.), Advances in Newral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL 99422661118822221111110700000000 Abstoaate-bbttat.... html
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Newral Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 1713-17281 2021.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'Aehéé-Bu,, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32, pp. 5723 5733. Curran Associates, Inc., 2019. URL https: pdf
ppproceediins..euurtee
Vijay Prakash Dwivedi and Xavier Bresson A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks. arXie preprint arXiw:2003.008 2020.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advonces in Neural Information Processing Systems, 35: 11326-22344 2022.
Moshe Eliasof, Eldad Haber, and Eran Treister. pathgen: paths. In International Conference on Machine Learning, pp.
Learning general graph spatial operators from
PMLR, 2022.
Matthias Fey and Jan F. Lenssen. Fast graph representation learning with PyTorc Geometric. In TCLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Matthias Fey, Jan-Gin Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular
graphs. Xrxiv preprint arXiw:2006.11/ 2020.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and extending subgraph GNNs by rethinking their symmetries. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openrevier http://oorumdddss//bBAAaada
Floris Geerts. Walk message passing neural networks and sccond-order graph neural networks. Xr preprint arXiv:2006.09/99 2020.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the Fourth International Conference on Machine Learning (ICML), pp. 2263-1272 2017.
20

---

Published in Transactions on Machine Learning Research (08/2023)
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Message passing
neural networks. Machine learning meels quandum physics, pp. 199-214, 2020.
Martin Grohe. The logic of graph neural networks. pp. 1-17, 2021. doi: 10. L0.100/LICS22262221..9900 URL htttpp://abi.orr//001/////////// 11w.11111///II12....... 2021. 20w.:/55222222217277000000000000
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Balaji Krishnapuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Son Francisco, CA, USA, August 13-17, 2016, pp. 855 864. ACM, 2016. doi:
29397544.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. pp- 1024 1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Ssuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https://proceedding http://roociiiinoooorsss...ooo neurips. ccppperr www.:estfffof-ttttttttttttta
Katsuhiko Ishiguro, Shin-ichi Maoda, and Masanori Koyama. Graph warp module: an auxiliary module for boosting the power of graph neural networks in molecular graph analysis. arXie preprinl 1rXix:192..00 01000, 2019.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International conference on machine learning, pp. 2186 2195. PMLR, 2018.
Xuan Jiang, Zhiyong Yang, Peisong Wen, Li Su, and Qingming Huang. A sparse-motif ensemble graph convolutional network against over-smoothing. In Ludd De Raedt (ed.), Proceedings of the Thirty-First International Joint Conference Artificial Intelligence, IJCAI-22, pp. 2094 2100. International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10.24963/ijean /at//aaaai.22222 2022 7/doi org/ 001///0..2963////1 24963/ijcai http://aaaai.2////3/ 2912/291 Main Track.
URL https;
Di Jin, Rui Wang, Meng Ge, Dongxiao He, Xiang Li, Wei Lin, and Weixiong Zhang, Raw-gun: Random walk aggregation based graph neural network. In Lud De Raedt (ed.), Proceedings of the Thirty- Thisty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2108-2114 International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 20.2166//jcaii20222 o/doo.org//0..20 (tooi..or//00.2463///je.aa 2032/293 Main Track.
URL https
Sandra Kiefer. The Weisfeiler-Leman algorithm: An exploration of its power. ACM SIGLOG News, 7(3): 5 5-27, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Soheil Kolouri, Navid Naderializadeh, Gustavo K. Rohde, and Heiko Hoffmann. Wasserstein embedding for graph learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.ne net, 2021. URL http:://ppppeeeeeeeeeeeeffrrrroe
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advonces in Neural Information Processing Systems, 34: 21618 21629, 2021.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1):1 42, 2020.
John Boaz Lee, Ryan A Rossi, Xiangnan Kong, Sungchul Kim, Eunyce Koh, and Anup Rao. Graph convolutional networks with motif-based attention. In Proceedings of the 28th ACM International Conference on Information and Knowledge Monagement, pp. 499 499-508, 2019.
21

---

Published in Transactions on Machine Learning Research (08/2023)
Junying Li, Deng Cai, and Xiaofei He. Learning graph-level representation for drug discovery. an preprint 1xXiu:179900990 2017.
Zheng Ma, Junyu Xuan, Yu Guang Wang, Ming Li, and Pictro Liò. Path integral based convolution and pooling for graph neural networks. Aduances in Neural Information Processing Systems, 33:16421-164333, 2020.
Haggai Maron, Heli Ben- Hen,Hamm, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. pp. 2153-2164, 2019a.
Haggai Maron, Heli Ben- Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks In ICLR, 2019b.
Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 200:108- 120, 2016.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Raltan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty- Third AAAI Conference on Artificial Intelligence (AAAT), pp. 4602-4609, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: collection of beuchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020a. URL www www.graphlearnnng... i0
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Newral Information Processing Systems, 13:21824-218400 21840, 2020b.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph reprosentations. In International Conference on Machine Learning, pp. 4663-4673. PMLR, 2019.
M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning, pp. 2014-2023, 2016.
Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Nearal Informa- lion Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL http://papers. itwp:pppppseeuruuppppppep neur ips cc/paper/9015 pc/pppprr001---prrrrraaaa-a---a -nw.torchaa---errriieeeee--eeee- pereerrrnee -earninn-e wiieeriibbrryy.. pdff
Hao Peng, Jianxin Li, Qiran Gong, Yuanxin Ning, Senzhang Wang, and Lifang He. Motif notif--mtthhig based subgraph-level attentional convolutional network for graph classification. In Proceedings of the AAAI Conference on Arlificial Indelligence, volume 34, pp. 5387 5394, 2020.
Aravind Sankar, Xinyang Zhang, and Kevin Chen- Chnan Chang. Motif-basse convolutional neural network on graphs. arXiv preprint 0rXiv:1711.088 2017.
Aravind Sankar, Junting Wang, Adit Krishnan, and Hari Sundaram. Beyond localized graph neural networks: An attributed motif regularization framework. In Claudia Plant, Haixun Wang, Alfredo Cuzzocrea, Carlo Zaniolo, and Xindong Wu (ods.), 20th IEEE International Conference on Data Mining, ICDM 2020, Sorrento, Italy, November 17-20, 2020, pp. 472-481 IEEE, 2020. doi: 1..100//CCDM55008.2000000 URL http:////a...o/11.110000//
00200000550
22

---

Published in Transactions on Machine Learning Research (08/2023)
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. CoRR, abx/2002.03155, 2020.
N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp. 495, 2009a.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient. graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488 495. PMLR, 2009b.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12(9). 2011.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkorcit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. 2018.
Yanbang Wang, Yen- Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint XXi::2001.0597. 2021.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesso, Ancesh S Pappu, Karl Leswing, and Vijay Pande. MoleculeNet: benchmark for molecular machine learning. Chemical science, 9 (2):513-530) 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the Seventh International Conference on Learning Representations (ICLR), 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365 1374, 2015.
Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and system co-design for efficient subgraph-based based graph representation learning. arXiv preprint arXiv:2202. 185558202.1588, 2022.
Hao Yuan and Shuiwang Ji. Node2seq: Towards trainable convolutions in graph neural networks. arXiv preprint ar XrX:221011.01840 2021.
Muhan Zhang and Pan Li. Nested graph neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 15734 15747. Curran Associates, Inc., 2021. URL htttps:/pproceedii: wwapoeiiinngnnnuuipipeeeee nwurine. wttpppppp.cpppppp//21/// file/846288 http://aaecaaaae0tteeeaaaaaaaeea Papeeeeccc-apprr....o. .pf.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. AAAI, pp. 4438 4445, 2018.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022. URL
iit.rrrrieeetttt.ffooooooiiiaio - WYKoEH
23

---

Published in Transactions on Machine Learning Research (08/2023)
A Model Details
In this appendix, we provide additional definitions and details on CRAW1, including the random walks that we sample and the exact architecture of the CNN in each layer.
A.1 Random Walks
A walk of length & E in a graph G EV, a sequence of nodes (vo...., Uz) E v4+1 with 0;-1V; E E for all i E [4]. A random walk in graph obtained by starting at some initial node vo E and then iteratively sampling the next node u/+1 randomly from the neighbors Na(v)) of the current node vs. We consider two different random walk strategies: uniform and non-backtracking. The uniform walks obtained by sampling the next node uniformly from all neighbors:
1i41 ((N(uu)))
On sparse graphs with nodes of small degree (such as molecules) this walk strategy has a tendency to backtrack often. This slows the traversal of the graph and interferes with the discovery of long-range patterns. The non- backtracking walk strategy addresses this issue by excluding the previous node from the sampling (unless the degree is onc):
[ (No(v)))) ((No(()))M ((i-1)), else.
i v deg(w;)=1
U(+1 DNB(U)) with DNB(U.)
The choice of the walk strategy is hyperparameter of CRAWL. In our experiments the non-backtracking strategy usually performs better shown in Section 5
A.2 Convolution Module
Here, we describe the architecture used for the 1D CNN network CNN' in each layer t. Let ConviD(d, d', k)) be standard ID convolution with input feature dimension d, output feature dimension d', kernel size k and no bias. This module has d- d' k trainable parameters. The term scales poorly for larger hidden dimensions d, since the square of this dimension is scaled with an additional factor of k, which we typically set to 9 or more.
To address this issue we leverage Depthwise Seporable Convolutions, as suggested by Chollet (017)). This method is most commonly applied 2D data in Computer Vision, but it can also be utilized for ID convolutions. It decomposes one convolution with kernel size k into two convolutions: The first convolution is standard 1D convolution with kernel size 1. The second convolution is depthwise convolution with kernel size k, which convolves each channel individually and therefore only requires k d' parameters. The second convolution is succoeded by a Batch Norm layer and a ReLU activation function. Note that there is no non-linearity between the two convolutions. These operations effectively simulate a standard convolution with kernel size but require substantially less memory and runtime.
After the ReLU activation, we apply an additional (standard) convolution with kernel size 1, followed by another ReLU non-linearity. This final convolution increases the expressiveness of our convolution module which could otherwise only learn linearly separable functions. This would limit its ability to distinguish the binary patterns that encode identity and adjacency.
The full stack of operations effectively applies a 2-layer MLP to each sliding window posi- tion of the walk feature tensor. Overall, CNN' composed of the following operations: ConvlD(d,d', 1) donvlDd dde ('',d'k)) + BatchNorm + ReLU ConviD(d ('',,'d')))) ReLU
Here, Conv1D is a standard 1D convolution and do is a depthwise convolution. The total number of parameters of one such module (without the affine transformation of the Batch Norm) is equal to dd' kd + d²
24

---

Published in Transactions on Machine Learning Research (08/2023)
Table 5: Hyperparameters used in each experiment.
PASCAL VOC-SP
PEPTIDES -FUNC
PEPTIDES
ZINC
CIFARI0
MNIST
CSL
MOLPCBA
-STRUCT
3
3
5
6
6
d
147
75
75
90
400
100
100
100
8
8
8
16
16
pool
sum
mean
mean
mean
mean
sum
sum
sum
out
mlp
mlp
mlp
mlp
linear
mip
mlp
mlp
train
50
50
50
50
50
50
50
50
leval
150
150
150
100
150
150
150
pe
1
1
1
0.2
0.2
0.2
0.2
walk strat.
nb
nb
nb
nb
nb
nb
nb
nb
Tval
2
2
2
5
2
2
2
Toes
10
10
10
10
10
5
5
dropout
0.0
0.0
0.0
0.0
0.25
0.1
0.1
0.2
learning rate
0.001
0.001
0.001
0.001
0.001
0.001
0.001
0.001
patience
10
10
10
20
epochs
60
300
500
500
batch size
50
50
50
50
100
50
50
50
virtual node
Yes
No
No
No
Yes
Yes
Yes
Yes
# #Params
497,743
109,660
109,360
104,140
6,115,728
495,021
510,910
511,011
A.3 Architecture
The architecture we use in the experiments works as follows. We then stack multiple CRA FLAWL layers with residual connections. In each CRAWL layer, we typically choose s = 8. The update MLP ( has a single hidden layer of dimension 2d with ReLU activation and linear output layer with d units. After the final CRA WL layer, apply batch normalization and a ReLU activation to the latent node embeddings before perform global pooling step. As pooling use either sum-pooling mean-pooling. Finally, a simple feedforward neural network is used to produce graph-level output which can then be used in classification and regression tasks. In our experiments, we use either an MLP with one hidden layer of dimension or a single linear layer.
Since CRAWL layers are based on iteratively updating latent node embeddings, they are fully compatible with conventional message passing layers and related techniques such virtual nodes (Gilmer et al.) 2017 Li
el al. 2017 Ishiguro et al. 2019). In our experiments, performance. A detailed explanation of our virtual node layer is provided in Appendix A.5 Combining CRAWL with message passing layers is left as future work.
use virtual nodes whenever this increases val validation
A.4 Hyperparameters
Table 5 provides the hyperparameters used in each experiment. The number of layers L and dimension d were luned to meet. the parameter budgets for each dataset. The local window size is set to 8 by default and increased to 16 the long-range datasets. As global pooling function we use either mean- The architecture of the final output network is either a 2-layer MLP or simple linear transformation. We denote the repetitions with different random walks to estimate the IMD in Section B.I with Tval and Ttest-
sum- num-pooling.
Hyperparameters for the walks and the training procedure: The number random walk steps during training frain is set and incrcased =150 during evaluation. The probability of starting a walk from each node during training p" is chosen 1 by default. On MOLPCBA and the long-range datasets we set p" 0.2 to reduce overfitting. The walk strategy (either uniform (un) non-backtracking (nb))
25

---

Published in Transactions on Machine Learning Research (08/2023)
10
3
10
skkip (11,
Gakip (11,3)
Figure 5: Two cyclic skip-link graphs (see Murphy et al. 2019 with 11 nodes and a skip distance of 2 and 3 respectively.
A.5 Virtual Node
Gilmer et al. [2017), Li ct al. 2017 and Ishiguro et al. (219 suggested the use of a virtual node to enhance GNNs for chemical datasets. Intuitively, a special node inserted into the graph that is connected to all other nodes. This node aggregates the states of all other nodes and usses this information to update its own state. The virtual node has its own distinct update function which not shared by other nodes. The updatod state is then sent back all nodes in the graph. Effectively, a virtual node allows global information flow after each layer.
Formally, virtual node updates a latent state hen Rd, where hin is computed after the t-th layer and 4 is initialized as zero vector. The update procedure is defined by:
h + Σ h(())) h = U m.
VEV
h((0) = (v) + h
Here, Ut is a trainable MLP and h² is the latent node embedding computed by the f-th CRAWL layer. i is an updated node embedding that used as the input for the next CRAWL layer instead of ht. our experiments, we choose U contain a single hidden layer dimension d. When using virtual node, we perform this update step after every CRAW WL layer, except for the last one.
Note that we view the virtual node intermediate update step that is placed between our CRA WL layers to allow for global communication bet nodes. No additional node is ualually added to the graph and, most importantly, the "virtual node" does not occur in the random walks sampled by CRAWL.
A.6 Cross Validation CSL
Let briefly discuss the experimental protocol used for the CSL dataset. Unlike the other benchmark datasets provided by Dwivedi et al. (2020), CSL is evaluated with 5-fold cross-validation. We use the 5-fold split Dwivedi et al. (2020) provide in their repository. In each training run, three folds are used for training and one is used for validation and model selection. After training, the remaining fold is used for testing.
Finally, Figure provides an example of two skip-link graphs. The task of CSL is classify such graphs by their isomorphism class.
26

---

Published in Transactions on Machine Learning Research (08/2023)
Table 6:
Statistics for our main datasets.
#Graphs
Avg. [V]
Avg. [F]
#Classes # Tasks
ZINC
10000 1000 / 1000
23.1
49.8
1
CIFARIO
45000 / 5000 / 10000
117.6
1129.8
10
MNIST
55000 / 5000 / 10000
80.98
785.39
10
CSL
150
41
82
10
MOLPCBA
350343 / 43793
43793
25.6
55.4
128
PASCALVOC-SP
8498/ (1998/142//// 1429
479.40
2710.48
21
SEPTIDES-FUNG
10873/ /231//2331/ /3311
150.94
307.30
10
PEPTIDES-STRUCT
10873/200 /3371/2331/// 2231
150.94
307.30
11
Table 7: Extended results for CRAWL all datasets. Note that different metrics used measure the performance the datasets. For each experiment we provide the cross model deviation (CMD) and the internal model deviation (IMD).
DATASET MODEL
METRIC
TEST
VALIAATION
TRAIN
SCORE
CMD
IMD
SCoRE
CMD
IMD
SCORE
CMD
ZINC
MAE
0.08456
+ 0.00352
0.00116
0.11398
0.00447
+ 0.00121
0.04913
+ 0.00887
CIFARIO
Acc.
0.69013
4 0.00259
0.00158
0.70032
+ 0.00307
= 0.00060
0.79180
+ 0.01956
MNIST
Acc.
0.97944
+ 0.00050
0.00055
0.98106
0.00110
+ 0.00030
0.99044
+ 0.00090
CSL
Acc. 1.00000
= 0.00000
= 0.00000
1.00000
+ 0.00000
+ 0.00000
1.00000
+ 0.00000
MOLPCBA
AP
0.29863
- 0.002-49
0.00055
0.307-16
+ 0.00195
- 0.00027
0.541889
+ 0.01021
PESCALVOC-SP
F1
0.45878
0.00794
0.00076
0.45326
0.00356
+ 0.00031
0.91138
+ 0.00361
PEPTIDES-FUNC
AP
0.70735
0.00317
= 0.00059
0.72716
0.00272
- 0.00064
0.98034
+ 0.00771
PEPTIDES-TTRUCT
0.25057
0.00224
0.00019
0.24089
0.00150
- 0.00016
0.20705
0.00870
B Extended Results
The dataset statistics of all datasets used in the main paper are given in Table experimental results full detail.
0 In the following, we provide
B.1 Detailed Results
Table 7 provides the full results from our experimental evaluation. It reports the performance on the train, validation, and test data.
Recall that the output of CRAWL, is a random variable. The predictions for a given input graph may vary when different random walks are sampled. To quantify this additional source of randomness, we measure two deviations for each experiment: The cross model deviation (CMD) and the internal model deviation (IMD). For clarity, let us define these terms formally. For cach experiment, we perform E N training runs with different random seeds. Let m, be the model obtained in the i-th training run with E [g]. When evaluating (both on test and validation data), we evaluate each model r e N times, with different random walks each evaluation run. Let Pi.j E IR measure the performance achieved by the model m, its j-th evaluation run. Note that the unit of Pt,j varies between experiments (Accuracy, MAE,...) We formally define the internal model deviation
IMD Σ STD ((pks (15 15:59
where STD(-) is the standard deviation of given distribution. Intuitively, the IMD measures how much the performance of trained model varies when applying it multiple times to the same input. It quantifies how the model performance depends the random walks that are sampled during evaluation.
We formally define the cross model deviation as
[
Σ Pij (
CMD = STD
1515
27

---

Published in Transactions on Machine Learning Research (08/2023)
Table 8: Average time per epoch for CRAWL. The reported times are averaged over a training run and include the time used to perform validation run after each training epoch. We also provide reported training times for several baselines reported in the literature (Dwivedi et al. 2020 2022 Zhao et al. 2022 Note that absolute training times are sparsely reported and depend on implementation details and hardware. We report these values as a rough guideline of how long the training standard MPGNNs and stronger architectures usually takes.
DATASET
CRAWL
GCN
GATEDGON
TRANSFORMER
SAN
GIN-AK
ZINC
10.0s
12.8s
10.78
27.78s
106.0s
9.4s
CIFARIO
265.0
109.7s
154.2s
241.1
MOLPCBA
458.4s
883.0s
PASCALNOC-SP
47.85
8.8s
12.0s
13.0s
179.0s
PEPTIDES-FUNC
18.58
3.0s
3.38
5.8s
49.1s
PEPTIDES-STRUCT
18.4s
2.6s
3.38
5.9s
49.7s
Table 9: Accuracy on Social Datascts.
Method
COLLAB Test Acc
IMDB-MULTI
REDDIT-BIN Test Ace
Test Acc
WL-Kernel
Shervashidze al.
2011
78.9 + 1.9
50.9 = 3,8
81.0 + 3.1 92.0 + 0.8
WEGL
Kolouri et al.
2021
79.8 + 1.5
52.0 = 4.1
GNTK
Du al.
2019
83.6 1.0
52.8 1 4.6
DGCNN
Zhang et al.
2018
73.8 + 0.5
47.8 1 0.9
3WLGNN
Maron et
2019a
80.7 1.7
50.5 + 3.6
GIN
Xu et a
2019
80.2 + 1.9
52.3 + 2.8
92.4 + 2.5
GSN
Bouritsas al.
2020
85.5 1.2
54.3 +
CRAWL
80.40% + 1.50
47.77% 3.87
92.75% 2.16
The CMD measures the deviation of the average model performance between different training runs. It therefore quantifies how the model performance depends on the random initialization of the network parameters before training.
In the main section, only reported the CMD for simplicity. Note that the CMD is significantly larger then the IMD across all experiments. Therefore, trained CRAWL models can reliably produce high quality prodictions, despite their dependence on randomly sampled walks.
B.2 Runtime
Table 8 provides runtime per epoch observed during training. All experiments were 64GB RAM, an Intel Xeon 8160 CPU and Nvidia Tesla V100 GPU with 16GB GPU memory. From the table we observe that the runtime of CRAWL does not differ much from common MPGNNs. While simpler architectures like GCN can run faster on larger datasets, CRA WL has no runtime disadvantage when compared to more advanced architectures like Graph Transformers (SAN) or subgraph GNNs (GIN-AK+).
machine with
B.3 Additional Experiments
In this section we evaluate CRAWL commonly used benchmark datasets from the domain of social networks. We use a subset from the TUDataset (Morris et al. 2020a), a list of typically small graph datasets from different domains e.g. chemistry, bioinformatics. and social networks. We focus on three datasets originally proposed by Yanardag & Vishwanathan (2015): COLLAB, a scientific collaboration dataset, and REDDIT-BIN, a balancod binary classification dataset Reddit users which discussed together in thread. These datasets do not have any node edge features and the tasks have to be solved purely with the structure of the graphs
IMDB-MULTI, multiclass datasct of movie collaboration of
28

---

Published in Transactions on Machine Learning Research (08/2023)
Table 10: Performance on the subgraph counting task.
METHOD
TRIANGLE
TAILED TRIANGLE
3-STAR
4-CYCLE
GCN
0,4186
0.3248
0.1798
0.2822
GIN
0.3569
0.2373
0.0224
0.2185
PNA
0.3532
0.2648
0.1278
0.2430
GCN-AK+
0.0137
0.0134
0.0174
0.0174
+IN-AK+ 0.0137
0.0112
0.0150
0.0150
PNA-AK+
0.0118
0.0138
0.0166
0.0132
CRAWL
0.0208 1: 0.0022
0.0197 1: 0.0019
0.0095 + 0.0015 0.0322 d: 0.0013
We stick to the experimental protocol suggested by Xu et al. 2019 Specifically, we perform 10-fold cross validation. Each dataset is split into 10 stratified folds. We perform 10 training runs where each split is used as test data once, while the remaining 9 are used for training. We then select the epoch with the highest mean test accuracy across all 10 runs. We report this mean test accuracy as the final result. This is not the most realistic setup for simulating real world tasks, since there is no clean split between validation and test. data. But in fact, it the most commonly used experimental setup for these datasets and is mainly justified by the comparatively small number of graphs. Therefore, we adopt the same procedure for the sake of comparability to the previous literature. For COLLAB and IMDB-MULTI we the same 10-fold split. used by Zhang et al. (2018). For REDDIT-BIN computed our own stratified splits. We also computed separate stratified 10-fold splits for hyperparameter tuning.
We adapt the training procedure of CRAWi, lowards this setup. Here, the learning rate decaas with a factor of 0.5 in fixed intervals. These intervals are chosen to 20 epochs on COLLAB and REDDIT-BINARY and as 50 epochs on IMDB-MULTI. We train for 200 epochs on COLLAB and REDDIT-BINARY and for 500 epochs on IMDB-MULTI. This ensures consistent learning rate profile across all 10 runs for each dataset.
Table 9 reports the achieved accuracy of CRAWL and several key baselines those datasets. For the basclines, we provide the results as reported in the literature. For comparability, we only report values for baselines with the same experimental protocol. On IMDB-MULTI, the smallest of the three datasets, CRAWL yields a slightly lower accuracy than most baselines. On COLLAB, our method performs similarly to standard MPGNN architectures such as GIN. CRAWL outperforms all baselines that report values for REDDIT-BIN Note that GSN, the method with the best results on COLLAB and IMDB-MULTI, does not scale as well as CRAWL and is infeasible for REDDIT-BIN which contains graphs with several thousand nodes.
B.4 Counting Substructures
We conduct additional experiments the task of counting various subgraphs in synthetic graphs. To this end we utilize benchmark dataset, proposed by Chen et al. (2020). This dataset constitutes graph-level regression problem that aims to infer how often each of the following subgraphs occurs in given graph: Triangles, Tailed Triangles, 3-Stars, and 4-Cycles. The same dataset was used by Zhao et al. (2022) to evaluate GNN-AK, a state-of-the-at subgraph GNN. This experiment therefore offers a fine- tne-ggained comparison between both approaches.
We train CLAWL with 6 layers, hidden dimension 256 and window size 8 for 500 epochs and average the
results over 4 models trained with different random seeds. Table 10 provides the test results. We report
the MAE for each target subgraph. The bascline results were obtained from Zhao et al. (022) Note that standard deviations were not reported.
As expected, both GNN-AK and CRAWL yield significantly better results on subgraph counting than simple MPGNNs like GCN and GIN. CRAWL yields the best results when counting stars, while GNN-AK achieves the lowest MAE on triangles and 4-cycles. Therefore, the structural information captured by CRAWi WL and subgraph GNNs like GNN-AK seems to capture different in information have different strengths and weaknesses.
29

---

Published in Transactions on Machine Learning Research (08/2023)
h1
h2
31
22
+1
Figure 6: Implementing the XOR function using a neural network with ReLU activations
This overall result aligns with our main experiment in Table 1 where CRA WL outperforms subgraph GNNSs on molecular data while GIN-AK+ yields better results on vision datasets.
C Additional Proof Details
C.1 Detailed construction of the polynomial-size MLP
Finally, let us provide additional thoughts on Theorem The provided proof is based on the assumption that our CNN filters can be an arbitrary MLPs. As MLPs are universal function approximators, they can theoretically memorize all feature matrices of CFI graph Gg. This CNN filter enables CRAWL to distinguish Gk from Hg, which &- fails to do. If we simply rely the universality of MLPs in this simple argument, then the size and runtime of the required MLP grows exponentially in k. This observation has effect the correctness of the proof. It is also no limitation when comparing CRAWI. to k- W-,, since k- also has an exponential runtime for growing k and only values of k < 3 have practical significance.
Nonetheless, with a more careful analysis can shown that the size of the MLP required in the proof has polynomial upper bound. Tt known that CFT graphs can be distinguished in polynomial time Cai et al. (1992). As for all computational problems in P, there do exist logical circuits of polynomial size that distinguish CFI graphs. In particular, for CFI graph Gg there exists Boolean circuit that decides for given adjacency matrix A whether it corresponds to graph that is isomorphic to Gş. It is also well known that Boolcan circuits can be simulated with ReLU activated MLPs with polynomial overhead. For illustration purposes, we included the implementation of an XOR gale in Figure 6 the other Boolean operators can be implemented similarly. Therefore, we can simulate the Boolean circuit that detects Gş with an MLP of a size that is polynomial in
30


Reviews:
[{"review_id": "8XeOMNUOMr", "reviewer": "Reviewer_RF6X", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "On the positive side:\n* I believe it is very important to explore expressivity hierarchies other than WL. I applaud the authors for proposing a simple and elegant method that does exactly this.\n* The proposed method, CRaWl, is certainly capable of extracting additional meaningful structure from the graph, and therefore clearly ticks the \"1-WL outperformance\" box that these papers should all have.\n* The theoretical work is solid and well-motivated.\n\nOn the negative side:\n* The scalability analysis of the model could have been executed better. Specifically, Table 5 is quite uninformative as it stands, with non-CRaWl numbers reported very scarcely. Given the model's very different mode of operation compared to a traditional GNN, It would be very useful to supplement the computational complexity analysis with additional runtime comparisons.\n* When discussing the \"asymptotic runtime\", the authors write _\"Let us emphasize that this [superlinear complexity] is a common drawback of architectures which are not bounded by 1-WL\"_. In my opinion, this claim needs to be better qualified to avoid confusion. For example, even computing very rudimentary structural features, or even purely random node features (Sato et al.), already leads to being able to distinguish more graphs than 1-WL. The complexity of such approaches is linear in the graph size. I invite the authors to better qualify this statement.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces CRaWl, a method that convolves over random walks sampled from an input graph, in order to perform graph representation learning tasks. Importantly, the authors are able to show and prove that their layer is a fundamentally new approach with respect to expressivity ladders: the set of graphs it can and cannot distinguish cannot be reasoned about using the popular Weisfeiler-Leman hierarchy.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weaknesses section above. \n\nTo further specify the first bullet point, if possible, please provide running times for more baseline models, on more datasets, to expand the findings of Table 5. If such numbers are not publicly available, the authors could consider making their own implementation.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WrBBwdEW95", "reviewer": "Reviewer_9Kh9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The work is well written and motivated well. \n2. The explanation on the theory is clear and extensive. I appreciate that the authors transparently show strengths and limitations of the proposed method. \n3. Experiments show the advantages of the proposed approach, e.g., over the datasets MOLPCBA and CSL. \n\nWeaknesses:\n1. Although the explanation on the theory is clear, I have some concerns on the value of the theory. By checking the proof of theorem 3, if I understand correctly, the proof is actually not only suitable for the graphs that k-WL fails to distinguish. It can also be applied to any connected non-isomorphic graph pairs, as long as the walks have length O(n^3) (suppose n many nodes and n^2 many edges). The only condition needed here is that graphs are connected. This poses a concern that how this algorithm can be so powerful. With some further thoughts, I noticed that there are some missing logical components in the proof. \n\na) First, the authors did not prove why the needed sample size m is O(n). The proof asks for sufficiently many sampled walks (\"last sentence in Sec. 3.1\").\n\nb) Second, the proof logic is to leverage the fact (observation 1) that if the structure feature matrix X keeps the same between two graphs, the two graph will be isomorphic. This matches expectation. Essentially, the random walk associated the nodes with an order which determines the row indices in X. Then, the comparison between two unlabeled graphs reduces to comparing two labeled graphs. Of course, if the latter two are isomorphic, the former two are isomorphic. But to surely demonstrate the former two are non-isomorphic, one should enumerate all possible orders of the nodes, i.e., the walk samples in the order O(n!). I am not sure how the authors can prove that only O(n) many walks are sufficient. Moreover, even if O(n) many walks can determine it with high probability, theorem 3 should be claimed rigorously, i.e., with a language in probability instead of surely. \n\n2. The proposed method is kind of complex. As observed above in the theory, essentially, the algorithm uses sampled walks to determine an order of the nodes. Each constructed matrix will be at least of n*n sizes. So now, each walk becomes a n*n matrix that needs a CNN to encode. Also, as suggested by the paper, the number of walks should be at least O(n). So, the overall complexity is much higher than MPNN.   \n\n3. Some missing references: Using sampling walks and encoding walks for graph representation learning are not new. The local identity idea read similar to those adopted by anonymous walks [1], which have been adopted to represent graphs based on neural network encoding [2,3]. Using CNNs on random walks to represent graphs has also been considered before [4].\n\n[1] Anonymous Walk Embeddings \n[2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks\n[3] Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning\n[4] Path Integral Based Convolution and Pooling for Graph Neural Networks\n \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new neural network-based approach to perform graph representation learning. The approach first samples random walks from the graph, and then constructs a feature matrix for each sampled random walk. The work proposes to use CNNs to encode these sampled walks. The authors prove that this method can distinguish connected graphs when the sampled walks are long enough ($O(|V||E|)$) and are sufficiently many ($O(|V|)$). Therefore, it can distinguish graphs that k-WL cannot distinguish. The proposed method also fails to distinguish graphs when the samples walks are short and only a few. Also, the proposed method also fails when the graphs are not connected. Experiments show the proposed method can outperform previous methods in some settings.      ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Address weakness 1 by characterizing the number of walks is needed to surely or with high probability to distinguish non-isomorphic graphs. Make sure the statement is rigorous. \n\n2. Address weakness 3 by Giving sufficient credits to previous works that sample and encode random walks instead of standard graph neural networks for graph representation learning.   ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FU5AGiqjaJ", "reviewer": "Reviewer_P2Wb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well motivated and easy to follow.\n\n2. The paper extends on ideas that allow to utilize efficient 1D operations in cuda, such as [1],[2]. The extension is both theoretical and technical, so the contribution is significant.\n\n3. The paper experiments with several datasets and shows a remarkable improvement over baselines methods.\n\n4. The authors also conduct an ablation study to learn about the influence of the hyperparameters, such as the length of the walk.\n\nOverall, I think that the paper is very solid and should be accepted, after minor changes.\n\nWeaknesses:\n\n1. The authors lack some background material such as a comparison with earlier models that propose a similar approach (although different, and the proposed method significantly extends them), such as [1],[2].\n\n2. There are several typos and broken references throughout the paper - additional passes on the text should clear them out.\n\n3. With respect to the theoretical representation power of the proposed method, I think it would be beneficial if the authors experiment and report the obtained MAE on the substructure counting dataset from GIN-AK (which is already cited and compared with by the authors)\n\n[1] Path Integral Based Convolution and Pooling for Graph Neural Networks\n\n[2] pathGCN: Learning General Graph Spatial Operators from Paths\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a framework to process graph data based on random walks. The advantage of the method is both theoretical and practical. The authors theoretically show that the proposed mechanism goes beyond the WL test and its expressiveness. Also, using the proposed method allows to utilize existing 1D convolution code that is highly optimized by different libraries such as cuda.\n\nThe authors also show the strength of their method on several graph classification and regression tasks, showing significant improvement over baseline methods.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see the authors respond to points 1-3 in my 'weaknesses' report. As stated in my review, I think that after appropriately addressing these points, the paper should be accepted. ", "broader_impact_concerns": "I do not see any potential negative outcomes of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mdrm41lmgu", "reviewer": "Reviewer_3MCo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The proposed model is conceptually very simple, but also novel to the best of my knowledge. In my view, it is a useful addition to the literature of GNNs since it is different from most existing models that are instances of the message passing architecture, while random walks have not been fully explored in this context.\n\n- The empirical results are interesting. The proposed model yields good performance on most datasets. Also the ablation study is interesting since it seems that on most datasets, the adjacency and identity encodings improve significantly the performance of the proposed model.\n\n- The paper is well-written and easy to read, while it also has some nice figures to illustrate the proposed model.\n\nWeaknesses:\n\n- Even though the proposed approach simulates random walks over the graph, it appears that walks themselves cannot capture structural properties of the graph, while they also empirically seem to yield inferior performance when used on their own. This is why the authors introduce the adjacency and identity encodings. But then, one could think of the feature matrices as connected subgraphs sampled from the graph. I would like the authors to comment on that and also discuss how the proposed model is related to subgraph GNNs.\n\n- To apply the proposed model to some dataset, one needs to specify the values of several hyperparameters (e.g., length of walk, window size, etc.). Is there a principle or rule of thumb for selecting the values such that the desired performance is achieved? Did the experiments on the real-world datasets provide any insights? This would be much appreciated by a practitioner who does not have the time to experiment with different combinations of hyperparameter values and does not also have any knowledge about how to choose them.\n\n- The authors claim that the proposed model detects long range interactions between nodes. However, this is shown neither theoretically nor experimentally. There are now available some datasets that require a method to perform long range interaction reasoning in order to achieve strong performance [1]. I would suggest the authors evaluate the proposed model on some of these datasets. \n\n- The proposed model achieves competitive results on ZINC and MOLPCBA, but on the 3 considered TUDatasets (results reported in Table 6) its performance is not that impressive. Is there a specific reason behind that? The number of samples of these datasets is much smaller than the number of samples of ZINC and MOLPCBA. Could this be the reason for the the performance drop?\n\n- The proof of the first part of Theorem 1 makes some assumptions that do not make fully sense and in my view, the authors should provide some explanations.\n\t- First of all, the considered instance of the model is very different from the model one would use in a real-world application. The authors assume that both the walk length and the window size are equal to $12n^2$. That would mean that the number of elements of the feature matrix is in the order of $\\mathcal{O}(n^4)$ which would be prohibitive for real graphs.\n\t- Then, the authors claim that by the universality of the CNN filters, the model can approximate function $f$. However, if I am not wrong, in this case, the CNN is equivalent to a fully-connected layer that maps the feature matrix into a scalar. Two walks that visit the same nodes in the opposite order encode the same information but the emerging feature matrices are very different from each other. This is not captured by a typical CNN which does not exhibit such invariance properties. Moreover, the cardinalities of sets $R_G$, $R_H$ and $S$ are very large (since different walks give rise to different feature matrices) and the components of their elements are not continuous. Thus, I really doubt a fully-connected layer can learn to approximate function $f$. \n\n[1] Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., & Beaini, D. (2022). Long range graph benchmark. Advances in Neural Information Processing Systems, pp. 22326-22340.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes CRAWL, a model for generating graph representations. The model simulates random walks and then applies a CNN to the subgraphs induced by nodes that appear along each walk. The authors study the expressive power of CRAWL and they show that the proposed model is not comparable to standard message passing GNNs in terms of expressiveness. There exist graphs that can be distinguished by CRAWL but not by standard GNNs and there also exist graphs that can be distinguished by standard GNNs but not by CRAWL. The model is evaluated in graph classification and graph regression tasks where it outperforms the baselines in several cases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following adjustments are related to the weaknesses listed above:\n\n- Make clear that the proposed model processes induced subgraphs and provide more details about that. Also, discuss how the proposed model is related to subgraph GNNs.\n\n- Explain how one can choose the values for the different hyperparameters. Is there some relatively cheap heuristic one could employ to select these values?\n\n- Since the model is supposed to capture long range interactions between nodes, experiment with such datasets (e.g., Long range graph benchmark).\n\n- Improve the proof of Theorem 1. For instance, explain why the CNN (which in this case is equivalent to a fully-connected layer in my understanding) can approximate the function that checks whether a feature matrix belongs to $R_G$.\n\nMinor:\n\n- Typos:\\\np.6: \"graph-evel\" => \"graph-level\"\\\np.7: \"edge set\" => \"node set\"\\\np.7: \"node set\" => \"edge set\"\\\np.10: \"length s=\" => \"length l=\"\\\np.10: \"graphs exists\" => \"graphs exist\"\n\n- In many cases throughout the paper \\citeyear is used instead of \\cite (for instance, in second paragraph of Related Work subsection). This should be fixed in the revision.\n\n- I would suggest the proofs of Theorem 1 are moved to the appendix to help improve the paper's readability", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9x0TZKz6Hl", "reviewer": "Reviewer_UkCv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- As opposed to other random-walk-based GNNs, the expressive power of the proposed method is provably beyond the WL hierarchy. \n- Writing is clear. I can easily understand the main point of the paper.\n- Reproducibility of numerical experiments is high.\n\n**Weaknesses**\n- Relation to other random-walk-based GNNs is not discussed in depth.\n- The superiority of the proposed method in terms of implementation is not discussed (See Claim and Evidence)\n- Performance gain of the proposed method empirically on node prediction tasks is moderate.\n\n**Claim and Evidence**\n\nThis paper's main claims are as follows:\n- CRaWl's expressive power for the graph isomorphism problems is incomparable to MPNNs.\n- CRaWl's architecture suits today's computing environments, such as GPUs.\n- CRaWl's empirical prediction performance is comparable to that of SOTA GNNs.\n\nThe first claim corresponds to Theorem 1. As far as I have checked the proof, this claim is correct.\nThe second claim is not numerically verified if I do not miss any information. However, since the architecture consists of random walk samplers and 1D-CNNs, I expect that the architecture is suitable for implementation on GPUs. Nevertheless, I am not sure this feature is a distinguished characteristic of the proposed method because we can implement usual MPNNs efficiently on GPUs for graph prediction problems where we have many small graphs.\nThe third claim has been tested on several types of graph datasets, including molecular datasets (MOLPCBA, ZINC), image datasets (MNIST, CIFAR10), and synthesis datasets (CSL). In addition, this paper compares with MPNN models mentioned in the related work. The code is provided as supplementary material explaining the dataset partitions and hyperparameters. Therefore, their results certainly justify the practical performance on graph prediction tasks. On the other hand, performance gain on node prediction tasks is limited (Appendix B.) \n\nConsidering the above points, I think the evidence generally supports these claims, although some parts are not verified.\n\n**Audience**\nIn graph learning problems, GNNs are known to be a practical approach. Their theoretical and empirical expressive power is one of the central research topics in graph machine learning, especially GNNs beyond the WL algorithm framework. Since this paper proposes a GNN not inside the WL hierarchy, it interests the TMLR audience.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new GNN, CRaWl, whole layers first sample random walkers from the input graph and then apply 1D-CNN to the encoded representations of subgraphs induced by the random walkers.\nThe expressive power of CRaWl is compared with that of the k-WL algorithm (and thus with Message Passing-based GNN). It is shown that these two are incomparable: On the one hand, there exist graph pairs that CRaWl can identify with window size and path length O(k^2) but not by k-WL. On the other hand, there exist graph pairs that can be easily identified by 1-WL but not by CRaWl with window size and path length O(n), where n is the number of nodes in a graph.\nFinally, CRaWl is applied to synthesis and real graph classification problems to elucidate the prediction performance and robustness in terms of hyperparameters and random walk sampling strategies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the following questions are natural. From the perspective of novelty and significance, it would be desirable to answer these questions. However, as stated in TMLR's [acceptance criteria](https://jmlr.org/tmlr/acceptance-criteria.html), answering these questions is not mandatory.\n- Does the representations obtained with CRaWl capture different features of graphs compared with MPNN representations?\n- This paper does not compare the proposed method with the random walk-based GNNs introduced in Related Work. Is CRaWl's performance betternthan them?\n\nRequested Changes\n- P.2, Section 1.1: This paper refers to Wu et al. (2020) as a reference for Message Passing GNN. However, since MPNN was proposed by Gilmer et al. (2017), I think Gilmer et al. (2017) is appropriate.\n- P.2, Section 1.1, Related Work mentioned existing studies on MPNNs, subgraph GNNs, and random walk-based GNNs. However, their relevance to this study needs to be discussed, at least explicitly. In particular, it would be better to discuss how the proposed methods are positioned in the line of research of random walk-based GNNs. For example, what problems can existing methods not solve, and how does the proposed method solve them?\n- P.8, Theorem 2: It is claimed that $G$ and $G'$ cannot be \"distinguished\" by CRaWl of certain parameters. However, this concept is not mathematically defined. Does it means $\\mathcal{X}(G) = \\mathcal{X}(G')$? If so, I think it is clearer and more straightforward to state it directly.\n- P.13, Table 1: What do boldface characters represent?\n- P.13, Section 4.3: I suggest clarifying when and where the leaderboard was obtained.\n- P.21, Appendix A.1: missing reference to a section.", "broader_impact_concerns": "There are no huge concerns about broader impacts.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Five referees recommend accept or lean accept, indicating that the contribution has significant merits as it proposes a different architecture with sufficiently convincing theoretical and empirical results. I particularly commend the authors' efforts addressing the reviewers' concerns in the rebuttal and during the discussion period. 

At the end of the discussion period a few items were identified which could or should still be improved. Hence I am recommending accept with a minor revision. I request that the final version of the manuscript implements any remaining items promised during the discussion period and carefully considers the final reviewers' comments, particularly the items listed below. 
 
* Reviewer 3MCo finds that the proof of Theorem 1 needs more explanations. 
* Reviewer 9Kh9 has a remaining concern about the existence of a polynomially complex f needed in one of the proofs. While the authors provided some arguments on the existence, this was not sufficiently clear and needs to be discussed more clearly in the final version. 
* Reviewer UkCv finds that several points can be improved, particularly the comparison with random-walk-based GNNs https://openreview.net/forum?id=vgXnEyeWVY&noteId=WsQGRytLre. 
Decision: Accept (poster)