Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Authors: Nils Morten Kriege
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph kernels
Weisfeiler-Leman
random walks

Abstract: Random walk kernels have been introduced in seminal work on graph learning and were later largely superseded by kernels based on the Weisfeiler-Leman test for graph isomorphism. We give a unified view on both classes of graph kernels. We study walk-based node refinement methods and formally relate them to several widely-used techniques, including Morgan's algorithm for molecule canonization and the Weisfeiler-Leman test. We define corresponding walk-based kernels on nodes that allow fine-grained parameterized neighborhood comparison, reach Weisfeiler-Leman expressiveness, and are computed using the kernel trick. From this we show that classical random walk kernels with only minor modifications regarding definition and computation are as expressive as the widely-used Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison. We verify experimentally that walk-based kernels reach or even surpass the accuracy of Weisfeiler-Leman kernels in real-world classification tasks.

Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Nils M. Kriege
Faculty of Computer Science, University of Vienna, Währinger Straße 29, 1090 Vienna, Austria Research Network Data Science @ Uni Vienna, Kolingasse 14-16, 1090 Vienna, Austria nils. f.l..krieeeeunive ac
Abstract
Random walk kernels have been introduced in seminal work on graph learning and were later largely superseded by kernels based on the Weiseeiler-Leman test for graph isomorphism. We give a unified view on both classes of graph kernels. We study walk-based node refinement methods and formally relate them to several widely- used techniques, including Morgan's algorithm for molecule canonization and the SoafeilerrLemann test. We define corresponding walk-based kernels nodes that allow fine-grained parameterized neighborhood comparison, reach Weisfeiler-Lenne expressiveness, and computed using the kernel trick. From this show that classical random walk kernels with only minor modifications regarding definition and computation are as expressive as the widely-used Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison. We verify experimentally that walk-based kernels reach or even surpass the accuracy of Weisfeiler-Leman kernels in real-world classification tasks.
Introduction
Machine learning with graph-structured data has various applications, from bioinformatics to social network analysis drug discovery and has become established research field. Graph kernels [26] 5 and graph neural networks (GNNs) 4 are two widely-used techniques for learning with graphs, the latter of which has recently received significant research interest. Technically, various methods of both categories exploit the link between graph data and linear algebra by representing graphs by their (normalized) adjacency matrix. Such methods are often defined or be interpreted in terms of walks. On the other hand, the Weisfeiler- Leman heuristic for graph isomorphism testing has attracted great interest in machine learning 33 34 This classical graph algorithm has been studied extensively in structural graph theory and logic, and its expressive power, i.e., its ability to distinguish non-isomorphic graphs, is well understood (3]. The Weisfeiler-Leman method turned to be suitable to derive powerful and efficient graph kernels [40]. Moreover, it is closely related to GNNs 45 14 allowing establish links, e.g., results from logic 15]
Several results have paved the way for these insights. The seminal work by Kersting et al. 22 links algebraic methods and the combinatorial Weisfeiler-Leman algorithm showing that it can be understood in terms of walks and simulated by iterated matrix products. comprehensive view the expressive power of linear algebra graphs recently given by Geerts [13]. GNNs are closely related to algebraic methods but involve activation functions and learnable weights. Morris et al. (31 has shown that (i) the expressive power of GNNs is limited by the Weisfeiler-Leman algorithm, and (ii) that GNN architectures exist that reach this expressive power for suitable weights. Independently. Xu et al. [45]
obtained the same result by using injective set functions computable by multilayer perceptrons [46
Most recently, Geerts et al. [14] has proven that already the early GCN layer-based architectures
23
achieve the expressive power of the Weisfeiler-Leman test with only minor modification already mentioned in the original publication.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Random walk kernels [2 21 have been the starting point of long line of research in graph kernels, see (26 [S] for details. An extension of random walk kemelss is based on so-called tree patterns, which may contain repeated nodes just like walks [37 28 A cornerstone in the development of graph kernels is the Weisfeiler-Lemaa graph kernel [40] which in contrast to tree pattern kernels, relies on entire node neighborhoods instead of all subsets. This restriction allowed manageable feature vectors and led to a significant improvement in terms of both running time and classification accuracy, Several other kernels based on the Weisfeiler-Leman test have been proposed, e.g., combining it with optimal assignments [24] or the Wasserstein distance 42]. Graph kernels inspired the development of neural modules based random walks and Weisfeiler-Leman labels 27.. Chen et al. (7) introduced multilayer- kernels conceptually similar to GNN layers and relates random walk and Weisfeiler- Seneller-Lemman Leman kernels in this framework for graphs, where the node labels induce unique bijection between neighbors. Dell et al. 8 recently established the equivalence in expressive power between tree patterns formalized tree homomorphism counts and the Seisseiler-Lemaae method. On this basis, homomorphism counts were quickly adapted for graph classification 35 The classical Weisfeiler-Lenee
kernel [40 as
well as the works (27 (35] enumerate graph features and generate (approximate) feature vectors. In contrast, the classical random walk kernel is computed using the kernel trick and thus operates implicitly in high dimensional features space. The advantages and disadvantages of fixed-size graph embeddings are subject to recent research [25] (). Nowadays, random walk kernels are widely abandoned, while Weisfeiler- Leman kernels remain an important baseline method performing competitively on many real-world datasets 26 55.
Our contribution. We formally relate random walks in labeled graphs and the Weisfeiler-Leman method and link random walk kernels and the Weisfeiler-Lente subtree kernel. Starting from combinatorial perspective, we consider walk-based label refinement and relate it to the Weisfeiler- Leman method. We extend the concept to fine-grained pairwise node similarities that satisfy the kernel properties and are computed via algebraic techniques using the kernel trick similarly to random walk kernels. From the node similarities, we derive a node-centric walk kernel on graphs. This kernel generalizes the classical random walk kernel [2] and allows grouping of walks by their start node. We show that grouping significantly improves the expressive power of random walk kernels and, with a minor modification, reaches the expressive power of the Weisfeiler-Lene Leman method, Kernel parameters control the grouping of walks and allow to interpolate between random walk and Weisfeiler- Leman type kernels. We verify our theoretical results on real-world graphs for which our approach reaches high accuracies, surpassing the Weisfeiler-Lenn subtree kernel in some cases.
2 Fundamentals
We aim at establishing formal links between random walks, Weisfeiler-L refinement, and corresponding kernels. We review the basics of these methods and refer the reader recent surveys for further details (26 34). We proceed by introducing the notation used.
2.1 Definitions and notation
An (undirected) graph G is a pair (V, F) with nodes V and edges E C V2, where (u, v) E E +> (v,u) u) E E. A graph may be endowed with (node) labeling a: V E. The labels E can be arbitrary structures such as (multi)sets but are typically represented by or mapped to integers. We denote sets by {-} and multisets allowing multiple instances of the same element by {.B. We refer to the neighbors of a node u by N(u) = {o= E (u,u) E EJ. Two graphs G = (V, E) and H (V', .E') are isomorphic, written G ~ H. if there is a bijection vb: V + V' such that (u, v) E E + (1b(4), ((v)) E E' for all u, v in V. For labeled graphs, additionally a = or (v)( must hold for all v V; for two graphs with roots r e V and r' V'. (rr) = r' must be satisfied. The map & is called isomorphism. An isomorphism of a graph to itself is called antomorphism. A labeling a is said to refine labeling 17. denoted by a [ 7) for all nodes u and u, (u) (v) implies 7())= = nt): we write o = 17 if _ 17 and E a. A label refinement is sequence of labelings (a(9). ())....) such that g()) refines (1-1) for all i > 0. A function k: X' x X + R is a kernel on X, if there is Hilbert space (H, (()) and map 6: X - H. such that k(æ, y) = (d(x)) d(y)) for all a. E X. A kernel on the set of graphs is graph kernel. We denote by kis the Dirac kernel with ks(a,y) v) = 1 if x = y and 0 otherwise. We write vectors and matrices bold, using capital letters for the latter, and denote the column vector of ones by 1.

---

2.2 Random walk kernels
The classical random walk kemee proposed by Gärtner et compares two graphs with discrete labels by counting their common walks, i.e. the pairs of walks with the same label sequence. Let W(G be the set of all walks of length i in a graph G. For walk w (U1, ......) let (wx) (a(v)), o(v2)....) denote its label sequence.
Definition 2.1 (f-step random walk kernel). Let X iR2ofori {0.... E} be a sequence of weights, the f-step random walk kernel is
8 GG, H) = Σ Σ
E kalo(w),
1=0 (EW,(G) ('EW((H)
Random walk kernels can be computed based on product graph using the kernel trick. Definition 2.2 (Direct product graph). For two labeled graphs G (V, E) and H (V', E') the direct product graph G x H is the graph (V,8) E) with V = ((0,)') E V [(()) = o(v')} and
& = {[uu, w'), (v,,))) E V2 (u, E E A (u', v') ")E E E.}.
Lemma 2.3. There a bijection between W,(G x H) and ((w, w') e W:(G) x Wi(H) ((w) = (w))), Vi 2 0.
Using Lemma 2.3 the é-step random walk kernel is computed from the adjacency matrix Ax of G x by matrix products or iterated matrix-vector vector multiplication as
M
[
(G, H)
Σ
(k))
8
ij
L==
with ((b) A w and (0) 1. The random walk kernel Kx is defined as the limit
Kg, where = (Ao: )1....) is chosen such that the sum converges 12 41. A well-studied instantiation is the geometric random walk kernel using weights X; = =-, M. where y < ! with
and A the maximum in- and outdegree of G x H guarantees convergence [12). For this choice, the kernel can be computed in polynomial-time applying an analytical expression based on matrix inversion. Efficient methods of computation have been studied extensively 43 20
2 A
However, theoretical and empirical results suggest that the benefit of using walks of infinite length as in the geometric random walk kernel is limited [4] 225. Random walk kernels can be extended to score the similarity of walks instead of requiring their labels to match exactly, making them suitable for graphs with arbitrary node and edge attributes compared by dedicated kernels [17] 43 25 The
accuracy and running time of random walk kernels can be improved by refining vertex labels in a
preprocessing step leading to sparse product graphs 29 25 19
2.3 Weisteiler-Leman refinement and graph kernels
The Weisfeiler-Lent Leman method, often referred to as color refinement, initially assigns labels (h (v) all nodes (or uniform labels if graphs are unlabeled) and then iteratively computes new labels for all v in V as
wI(++) = (wl (v), (w) (w) E ((()))
Convergence is reached when (l (u) w/ ())
(1)) (u) (1( holds for all
u, V and we denote the corresponding stable labeling by w)())) In practice, nested multisets are avoided by applying an injective mapping to integers after every iteration. For all j 2 i, w(()) wi holds. The stable partition (/ is refined by the orbit labeling assigning two nodes u, v the same label if and only if there is automorphism with (u) (b()).
In graph isomorphism testing, only the final stable labeling w| is of interest, while in graph kernels, only the first few iterations are used. The peisfeiler-Lemaae subtree kernel [40] K computes the first l iterations and maps graphs to feature vectors counting the number of nodes in the graph for every label, which is equal to
KW H)
Σ
Σ
Σ
ks(wl(0 (())
1=0
(G)(())
3

---

single cell
a
d é deggeihit
G
d
w/(0) rw rw
rw (1)
w/(
rw rw
rw (2)
(2)
w/
rw
w/
w/(oo)
O
w/
orbits
[]
T
w|
singletons
(a) Graph and unfolding trees
(b) Node labelings
(c) Partition lattice
Figure 1: Label refinement using walks and the Weisfeiler-Leman method. (a) shows unlabeled graph G and two unfolding trees of depth two rooted at node f and c, respectively. Since the trees are not isomorphic. (f) (f)= * (e) However, rw ( (f) rw: (2) (e), since the trees have the same number of nodes with uniform labels on each level. (b) shows the corresponding node partitions after
one and two steps and at convergence (labels are represented by colors and reused in each iterations for
simplicity) illustrating that (/ rw! holds for G. (c) shows part of the lattice associated with
label refinement relating both methods, where an arrow from to a denotes a E 1/.
Comparing nodes by walks
Wc propose to compare the nodes of one multiple graphs according to the walks originating at them. We start with discrete walk labelings and characterize their ability to distinguish nodes relating the approach classical methods and results for unlabeled graphs, namely Morgan's algorithm, walk partitions and Weisfeiler- refinement. Then we focus on the pairwise node comparison and propose walk kernels nodes, which are extended to reach the expressiveness of the Weiseeiler-Leman method.
3.1 Walk labelings and their properties
We consider graphs with discrete labels. For node v in a graph G, we define W,(v) as the set of walks of length in G starting in e. We associate with every node a label rw()) (v) representing the label sequences of length walks originating at v, i.e., rw() (c) {o(w) w (.) B. This does not yield a label refinement, since (=+1) not necessarily refines rw For a counterexample consider nodes f and of the graph G in Figure ((a) for which (w)))(() 3f rw(2)(g) but rw = rw( (g). To guarantee that two nodes once labeled different will obtain different labels in all subsequent
iterations, we consider all walks up to given length and define Wt (w) - Wi(v).
Definition 3.1 (L-walk label). The f-walk label of a node is rw (2)
[w(w) w WT (v)
(v) for all V and walks of different length have different label sequences, it immediately follows that rw (++1) (w((+1) [ rw(") We say that two nodes u and E-walk indistinguishable if rw (8) (u) rw (v). We call and walk indistinguishable if they are co-walk indistinguishable.
Since rw (x((()) C rw ((++)))
3.1.1 Relation to Morgan's algorithm
Morgan (30 proposed a method to generate canonical representations for molecular graphs. To reduce ambiguities each node v is endowed with its extended connectivity ec(v). Let G = (V. E) be (molecular) graph, initially we assign (v)) deg(v) to every node in V, where deg(v) is the degree of v. Then, the values (6 are computed iteratively for 2 2 and all nodes in V as
ec () (v) = Σ (t()-))(u),
uEA(T)
until (w) v E VJJ- < (ec(++)) VJI. Then, ec( is the final extended connectivity of the node For all i > the extended connectivity values (*) are equivalent to the row (or column)

---

sums of the ith power of the adjaceney matrix, i.e., A'1, which gives the number of walks of length i starting at each node [8 10]. We relate the extended connectivity to walk labelings.
Proposition 3.2. For i Z 1 and all graphs, rw( [ ec( holds with rw! = ec(() in the case of unlabeled graphs.
( (u) for all in V. Hence, rw!)) (u) rw (v) ec(*) (u) ec (v). Vice versa, ecl)) ec() is necessary condition for rw (u) (w((()) For unlabeled graphs, all walks have the same label sequence and rw
Proof. From the definition of walk labelings conclude (ww(
contains multiple instance of a single lahel sequence for all nodes, proving the equivalence.
3.1.2 Relation to walk partitions
Powers and Sulaiman [36] studied the walk partition of graph with adjacency matrix A, which is obtained from the matrix ( [1, A1, A A'1]. We define node labeling wp,
where the ith node assigned its row vector, i.e., wp(() w:( With Proposition 3.2 we directly obtain the following result.
Proposition 3.3. For i 2 0 and all graphs, rw wp holds with rw wp in the case of unlabeled graphs.
For unlabeled graphs, it is known that (xo) (e) and both coincide for many graphs [36].
3.1.3 Relation to the Weiseeiler-Leman method
The Weisfeiler-Leman labels encode neighborhood patterns. The unfolding tree 1 T[n, v] of depth n at the node v is defined recursively as the tree with root and children (hildren.WVt). Each child w e (v) is the root of the unfolding tree T[n - 1, w| and T(O, w| = (fw). 0). The labels of the original graph are preserved in the unfolding tree.
Lemma 3.4 (Folklore). For l 2 0 and nodes and ( (u) w/ - T(K Tie, v].
As unfolding trees also encode walks unfolding tree [(,, v), let PL(T(E, u)) denote the set of unique paths from the root v to a leaf. Lemma 3.5. Let f 2 0 and a node, then PL((TE, v)) = We(w).
relate Weisfeiler- Leman and walk labelings. For an
Proof. For a walk (r to. 2g) we have 2/41 E (N;))) for 0 S i < l and hence path in PL(T vi) exists. Vice versa, every path in PL(TT(, ul) is walk of length & starting at v.
Since T(e, u] ~ T(e, v) implies PL u|) PL v)) for all (O...., E} we conclude.
Proposition 3.6. Let E No. then ! [ _w C mw(
Vice versa, for é = 0 or é 1, PL(TTE, u]) PL(TTE, e)) implies T[e, u] = T[e, v). since the unfolding tree consists of single node or is star graph, respectively. Proposition 3.7. holds () rw(
(w and () rw (w))
Figure [ illusttrate the relations and shows an example, where the refinement relation is strict. The nodes and are walk indistinguishable but obtain different Weisfeiler-Lemaa labels after only two refinement steps. this sense the walk labeling is weaker than the Weisfeiler-Leman labeling. This does not necessarily mean that it is less suitable for learning tasks, We study the difference of the two techniques on common benchmark datasets Section
3.2 Pairwise node comparison
In the previous section, two walks were considered equal if they exhibit the same label sequence and two nodes have the same walk label if the multisets of walks originating them equal. We define the functions ky and ktt between nodes that measure the similarity based on walks in a more fine-grained manner
ktf (u, v) Σ u), with ke(u,v)=
Σ
Σ
II
ky (us, vi);
(1)
WE we(a( w/ (w))
5

---

where w = (w=tio, ui....,, we), w' = (w=Uy Ui...., 0t) and ky is a user-defined function measuring the similarity of nodes, e.g., by taking continuous attributes into account. Assuming that by a kernel on nodes, it follows from the concept of convolution kernels and basic closure properties [39] that k again is kernel. We denote its feature map by o and refer the reader to 25 for the tools to construct feature vectors. If we assume that kv (u, v) ks (ur),, (t)), then a possible feature map of takes to a vector having a component for every possible label sequence of length at most & and counts the number of walks starting at v with a (w) i.c., it is the characteristic vector of the multiset (6) rw" + (u). We obtain a new parameterized kernel that allows controlling the strictness of neighborhood companison.
Definition 3.8 (Generalized f-walk node kernel). Let a E Rz0 the generalized 6-walk node keree is
ktt (u, aa = exp (-a (-allot (u) oz (v))1
(2)
= exp (-a (kg (u, u) + k2 (v, 2 (u, ol))
(3)
This is Gaussian kernel, where the Euclidean distance is substituted by the kernel distance associated
with k,t which yields a valid kernel [16]. The kernel distance can be computed using the kernel trick
according to Equation 3
We proceed by relating the generalized f-walk node kernel to walk labelings.
Proposition 3.9. For a > O and kv = kg. the equality & (u, o; a) = 1 holds if and only if u and v are t-walk indistinguishable, i.e., rw (w)(()) (u) rw (2((()) (v).
Proof. For o O, the Gaussian kernel is one if and only if the Euclidean distance is zero, i.e., of (u) = $7 (v). With the feature map of k that maps the characteristic vector of the multiset (1) rw + (v) the result follows immediately.
Other normalized kernels & satisfying k(x, y) if and only if y are known 1 but cannot be controlled with a parameter a a similar way. For a O, we have k7 (u, v) = 1. For a - oc, we have he(u, v) 0 unless and are E-walk indistinguishable. In particular, we can relate the generalized f-walk node kernel to walk labelings.
Corollary 3.10. For + co, the image of bot is 1) and htt (u, v) = = rw ( (u) rw (v).
3.2.1 Computation
Computing walk labelings for labeled graphs by enumerating walks is prohibitive. We employ technique based on direct product graphs introduced for the computation of random walk kernels, see Section 2.2 Using Lemma 2.3 we can compute the generalized ε-walk node kernel by counting the walks in the direct product graph with the techniques described above. Algorithm T realizes this approach and computes the kernel for all pairs of nodes having a non-zero value. The vectors w and - each have one entry for each node (u, v) in the direct product graph, which after the ith iteration stores the value of (u, v) and ktt (u. v), respectively. In Line & the generalized é-walk node kernel is computed according to Definition 3.8 based on the three values k. (u, e), ktft (u, u) and k (c. v) using the kernel trick. The symmetry of kernels is reflected by symmetries in the direct product graph G x G which can be exploited to speed-up up computation. Line is optional and increases expressivity as discussed in Section 3.2.2] The method of computation can extended to incorporate vertex and edge kernels by using a weighted adjacency matrix and initializing ( according to the vertex kernel, see (55 for details. Moreover, the limit é + oo can be computed by introducing suitable weights and well-known techniques proposed for random walk kernels, see Section 2.2
3.2.2
Weisfeiler- expressiveness
We can modify Algorithm to perform a re-encoding in every iteration to achieve Weisfeiler-Leman expressiveness for a + oo by adding Line (highlighted in blue).
Proposition 3.11. For é > and a + oo, Algorithm including Line 9 computes k-W {0, 1) and k Wl, v) 1 + w/ (u) (1 (z).
WL with image

---

Input: Graph G = (V, E). parameters & and Output: Kernel matrices K and K ( storing lu and k. for S e, respectively.
0.24
0.73
0.53
0.02
0.03
RW1
0.27
0.88
0.89
0.65
0.99
0.89
0.93
0.69
0.9
RW2
0.31
0.34
0.95
0.98
1.00
1.30
1.00
0.99
0.8
Ax adjacency matrix of G' x G
0.7
RW4
20 + 1; w² + for to do Axw
NCW1
0.31
0.94
0:95
0.93
1.00
1.00
1.00
1.00
0.6
NCW₂ 0.31
0.38
0.90
1.00
1.00
1.50
1.00
1.00
0.5
NCW,
0.35
1.00
1.00
1.00
1.00
1.50
1.00
1.00
0.4
w
w +
NCW4
1.00
forall (u, v) E V(G G) do
WL1
0.3
Kuv Wav
WL2
0.91
0.99
0:99
1.00
1.00
1.00
1.00
1.00
8
R f- e aa( tort mw))
Eq.
WL3
WL.
0.95
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.1
War Rud
WL expresssiieenss
MUTAG
NC11
NC1109
PTC-FM
ENZYMES PROTEINS
COLLAB IMDBBIN
Algorithm 1: Generalized 8-walk node kernel
Figure 2: Expressiveness
Proof. The construction of the direct product graph and Corollary 3.10 with Proposition 3.7 guarantee that the statement is satisfied initially for i 1. For 0o, K 1 if and only if w w w in iteration i, and zero otherwise. Assume that the equivalence holds in iteration i, then the vector wo contains ones for the node pairs (u, v) with (w)) = wl( and w = w w Hence, in iteration + after Line w counts for each node pair the number of matching neighbors regarding (( After adding these values w++ it directly follows that, if w1 (u) ())
then t Wey w and k16+1)
in Line 8 Vice versa, ((++1) 1 if and only if ass w... wee. which implies Wan = Whp = Wan- In combination with ou)) = a()) from
Definition 2.2 we conclude (1(++) (u) wi(+))())
4 Comparing graphs by walks
We define a graph kernel based on the generalized é-walk node kernel obtained from the Cartesian product of the node sets of the two input graphs. Its parameters allow controlling the strictness of neighborhood comparison and the importance of walk counts.
Definition 4.1 (Node-centric (-walk graph kernel), Given B R2o the node-centric é-walk graph kernel defined as
K (,,
Σ Σ Σ
(u, o,a)kf
(4)
1=0 WEV(G) DEV(H)
The node-centric Ê-walk graph kernel combines the generalized f-walk node kernel of Definition 3.8 with polynomial of the kernel kg It can incorporate continuous attributes via dedicated node kernel ky, cf. Equation (T). We show the following that Definition 4.1 resembles two widely-used graph kernels from the literature for certain parameter choices.
4.1 Relation random walk and Weisfeiler-Lemaa subtree kernels
Random walk kernels, see Section 2.2 are closely related the node-centric é-walk graph kernel. Proposition 4.2. The node-centric f-walk gruph kernel for and B = 1 is equal to the t-step random walk kernel with X, = f E (O, i.e., K2² (G, H; 1) Kt H).
Proof. The parameter choice guarantees that RJt (u, a) (u, v) = ki(u, Hence, this ker- nel sums over all pairs walks (w, w') of length less or equal to Since ((((ww))((w)) [=]')== = II, (s(o( (v,)), where ur (No, u1,...). w/ (ta, U2....) this corresponds to Defini- tion 2

---

This result also holds for the limit & + 3o if we assume that walks are adequately down-weiigtt by their length to guarantee convergence.
In random walk kernels a pair of vertices, that both have a large neighborhood, have a great ability contribute strongly the total kernel value, since large number of walks originates them. In the Weisfeiler-Leman subtree kernel the same pair contributes a value bounded by é depending on whether their neighborhood matches exactly. We hypothesize that this conceptional difference is crucial and allows the Weisfeiler-Lenie kernel to outperform previous walk-based kernels. By setting sufficiently high and 0, it follows from Corollary 3.10 that the node-centric f-walk graph kernel resembles the Weisfeiler-Leman kernel in this respect, but uses walk labelings instead. Our discussion of walk labelings and their relation to Weisfeiler- expressive. We verify our hypothesis experimentally in Section [ Moreover, by applying the iterated re-encoding described subtree kernel for - oo and / = O. Other parameter choices allow for a less strict comparison, which is not possible with the Weisfeiler-Lemaa subtree kernel.
labels suggest that these are only slightly less
Section 3.2.2, we obtain exactly the same value as the Weisfeiler- Leman
4.2 Computation
We can compute the node-centric Ê-walk graph kernel for two graphs G and H by applying Algorithm 1 to their union G' U H and plugging the results stored in the two kernel matrices K(O) and K())
into Equation 4 This can be optimized by exploiting the structural properties of the direct product graph.
Proposition 4.3, Let G and H be two graphs, then the direct product graph of their union P = GUU i (G G) (G H) u (H G) (H x H).
Proof. The result follows from Definition 2.2 with the fact that the vertex and edge sets of G and H are disjoint.
As there are no walks between disconnected components, we can run Algorithm I separately on the product graphs G H, G x G and H x H, ignoring H x G due symmetry. Moreover, if we compute the kernel for all pairs of graphs in dataset D of graphs, we can compute all node self-similarities from product graphs G G for all G D once in a preprocessing step. In this case, the overhead compared to the standard ê-step random walk kernel is only minor and is mainly attributed exponentiation. Direct computation via the directed product graph is not suitable for large-scale graphs [25]. However, existing acceleration techniques
[43 20 19 remain applicable. In particular, for unlabeled graphs (or ky (u, v) for all nodes u, v) the result can be obtained from the walk counts of the input graphs without generating product graph.
5 Experimental evaluation
We experimentally verify the hypotheses that have originated from our theoretical results. In particular, we aim to answer the following research questions.
Q1 Is the Weisteiler-Leman subtree kernel more expressive than walk-based kernels regarding their ability to distinguish non-isomorphic graphs on common benchmark datasets?
Q2 Are our walk-based kernels competitive to the state-of-the-art regarding classification accuracy?
Q3 Which level of strictness walk-based neighborhood comparison most suitable?
5.1
Experimental setup
We describe the kernels under comparison, their parameters and the used datasets. All experiments were performed on an Intel Xeon E5 25-2690v4 machine at 2.6GHz with 384 GB of RAM.
5.1.1
Kernels
We implemented the node-centric E-walk kernel (NCW) of Definition 4.1 with k and k; computed by Algorithm D without the blue Line the variant with WI expressiveness including the blue line (NCWWL). For unlabeled graphs computed NCW without creating the direct product graph.

---

Table 1: Average classification accuracies in percent and standard deviations. The highest accuracy of each dataset is marked bold; OOM denotes an out of memory error.
DATASETS
METHOD
MUTAG
Nc11
Nc1109
PTC-FM
ENZYMES
PROTEINS
IMDBBIN
COLLAB
VL
85.4
64.8#0.1
63.6+0.2
58.0=0.7
23.6+0.9
72.1
46.7+1.1
56.2+000
EL
85.5+0.6
66.4+0.1
64.9+0.1
57.8+0.7
27.7+0.7
73.5+0.3
45,9+0.8
61.7+0.2
SP
83.3+1.4
74.3+0.3
73.3+0.1
60.4+1.7
39.2+1.4
73.8+0.4
48.0+0.8
68, 68.2
GH
85
72.8:0.2
71.740.3
57.811.2
33.9
68. 18..5
52.640.88
65.940.
GL33
85.2
70.5
69.3+0.2
57.9
30.1
72.9+0.4
50.7+0.8
66.7+0.1
WT
87.0
85.340.3
85.940.3
63.7.11.
53.8+1.2
75.1
71.640.8
79.0+0.1
RW
87.8+0.9
75.4:10.2
74.5+0.1
57.3+1.7
33.940.9
73.44:0.6
68.410..5
56,2+0.0
NCW
86.9
85.5+0.2
85.940.2
63.41:.2
$4.8
74.8+0.5
70.410.88
79.4
NCWWL
87.1
85.5+0.2
86.3+0.2
62.3+1.0
55.2+112
74.840.5
71.620.6
OOM
As a baseline we used the node label kernel (VL) and edge label kernel (EL), which are the dot products on node and edge label histograms, respectively, see [41 (6). For the Weisfeiler-
subtree kernel (WL), the f-step random walk kernel (RW) as well as NCW and NCWWL we chose the iteration number and walk length from {o..... 5) by cross-validation. For RW, X 1 for i E {0, (0..... LJ was used. For NCW and NCWWL, we selected a from {0.01, 0.1, 1, 1000} and 3 from {0. 0.5, 1). We have not included extensions of the WL such [24 42). which could also be applied similarly to the node-centric Ê-walk graph kernel. addition we used a graphlet kernel (GL3), the shortest-patt path kernel (SP) [4) and the Graph Hopper kernel (GH) 9 GL33 is based connected subgraphs with three nodes taking labels into account similar to the approach used by Shervashidze et al. 44). For SP and GH used the Dirac kernel to compare path lengths and node labels. We implemented the node-centric (-walk graph kernel as well as all baselines in Java We performed classification experiments with the C-SVM implementation LIBSVM (6). We report mean prediction accuracies and standard deviations obtained by 10-fold nested cross- validavni repeated 10 times with random fold assignment. Within each fold all necessary parameters were selected by cross-validation based on the training set. This includes the regularization parameter C' and kernel parameters.
We
5.1.2 Datasets
We tested on widely-used graph classification benchmarks datasets of the TUDATASETS repository 32 representing graphs from different domains. MUTAG, NCI1, NC1109 and PTс-FM represent small molecules, ENZYMES and PROTEINS are derived from macromolecules, and COLLAB and IMDBBIN are social networks. The datasets define binary graph classification experiments with exception of ENZYMES and COLLAB, which are divided into six and three classes, respectively. All graphs have node labels with exception of the social network graphs We removed edge labels, if present, since they are not supported by all graph kernel implementations.
5.2 Results
We discuss our results and research questions.
Q1: Expressiveness. We investigate the expressiveness of the f-step random walk kernel (RWz), 2). the node-centric f-walk graph kernel (NCW,) with a = 1000 and B = O, and the Weisfeiler-Lemme subtree kernel (WL.). Since the used graph datasets contain duplicates (8), we filtered them such that for each isomorphism class a single representative remains. We computed the completeness ratio introduced by Kriege et al. 26), i.e., the fraction of graphs that can be distinguished from all other graphs in the dataset. Figure 2 confirms that with increasing parameter all methods become more expressive. For all datasets we observe that NCW; & clearly more expressive than RW; showing that grouping the walks according to their start node increases the expressive power. Moreover, NCW; achieves the same values as WL, for all é. Although we have shown that walk labelings are weaker than Weisfeiler-Lemme labelings, cf. Figure T this does not affect the ability to distinguish the considered real-world graphs. This confirms that walks provide expressive features when grouped at a node level.
OOur code is publicly available at httpps:: / h/tp://ggtttttt////// http://tttt.uu...meeeeeeeeeeeeee
kernels

---

0.01
07
15
0.1
32
15
0
0
0
2
0
13
15
37
14
1
0
0
0
1.0
230
43
24
99
1000.0
35
8
0.0
0.5
100
0.5
1.0
0.0
0.5
1.
0.0
0.5
1.0
0.D
0.5
1.0
Total
MUTAG
NC11
Nc1109 PTC-FM ENZYMES PROTEINS IMDBBIN COLLAB
Figure 3: Selection of the parameters (y-axis) and / (x-axis) of the node-centric æ-walk graph kernel on different datasets. Note that the combination at the bottom left resembles Weisfeiler-Leman type kernels and the combination at the top right the Ê-step random walk kernel.
Q2: Accuracy. TableI the resulting accuracies and standard deviations. For several datasets WL outperforms RW as expected, c.g., Nc11, Nc1109 and ENZYMES. In these cases NCW provides an accuracy close to WL and outperforms RW by large margin, although both are based walks and NCW is obtained with only a minor modification RW. This clearly shows that node-centric walks suitable for obtaining high accuracies. For ENZYMES, NCW reaches accuracy higher than WL indicating that a higher expressiveness does not necessarily lead to better generalization. This suggests that less strict comparison of neighborhoods can be beneficial for some of the datasets. NCWWL overall performs comparable to NCW but reaches slight improvements for several datasets.
Q3: Striet neighhorhood comparison. NCW supports non-strict neighborhood comparison by tuning the parameter a and incorporates walk counts for increasing 3 leading to a kernel similar to WL and the f-step random walk kernel for the extreme cases. We investigate the selection of these parameters in the above classification experiments. For each dataset 10-fold cross-validation was repeated 10 times leading 100 classification experiments in total, for each of which the hyperparameters were optimized. The distribution of the selected values for a and /3 is shown in Figure 3 We observe that the choices vary between datasets. For the social network datasets there is a clear preference for / = O, which explains the worse performance of the Ł-step random walk kernels on these datasets. For Nc1l and Nc1109, a 2 1 and 3 < 0.5 were preferred leading kernel values closer to WI., which is in accordance with the accuracy reached. Of particular interest is the dataset ENZYMES for which NCW and NCWWL. provide the highest accuracies. Figure shows that for this dataset, in most cases non-strict neighborhood comparison (a < 1) with only minor influence of walk counts (3 S 0.5) was selected, choice not possible with previous kernels. Further investigation shows that the parameter & = 2 was selected in the majority of the cases for WL, while for NCW, = 4 with a = 0.1 or a = 0.01 was selected most frequently. This indicates that for this dataset is preferable to take larger neighborhoods into account but to compare them less strictly.
6 Conclusion and future work
We have contributed to the understanding of walk and Weisfeiler-Leman based methods showing that classical random walk kernels can be lifted to obtain the expressive power of the Weifeiler-Lennn subtree kernel, drastically increasing classification accuracy. While the direct product graph based approach is less efficient than the Weisfeiler-Lemaa method, its advantage is that we can control the strictness of neighborhood comparison and incorporate node and edge similarities for attributed graphs. Improving the running time and the application attributed graphs remains future work.
Our results have implications beyond graphs kernels. In graph neural networks, the bottleneck problem [2] refers to the observation that node neighborhoods grow exponentially with increasing radius and thus cannot be represented accurately by fixed-sized feature vector. This is a possible explanation for the weakness of GNNs in long-range tasks. The product graph based approach works with infiniteddimensionall node embeddings using the kernel trick. Investigating the bottleneck problem in product graph based GNNs might shed more light into this phenomenon.
Acknowledgements
I would like to thank Floris Geerts for pointing me to the paper on walk partitions by Powers and Sulaiman (36). am grateful the Vienna Science and Technology Fund (WWTF) for supporting me through project VRG19-009.
10

---

References
[1] Julien Ah-Pine. Normalized kernels as similarity indices. In Advances in Knowledge Discovery and Data Mining, volume 6119 of LNCS, pages 362-373. Springer Berlin Heidelberg, 2010. ISBN 978-3-642-13677
100100..007778-33-661111
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference Learning Representations, ICLR. OpenReview.net, 2021.
[3] Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. Graph isomorphism. color refinement, and compactness. Comput. Complex., 26(3):627-68 2017. doi 10.1007/s00037 016-0147-6
[4] Karsten M. Borgwardt and Hans-Peter Kriegel. Shortest-patt kernels graphs. In Proceedings of the Fifth IEEE International Conference on Data Mining, ICDM '05, pages 74-81, Washington, DC. USA, 2005, IEEE Computer Society. ISBN 0-7695-2278-- doi 10. 109/CCD..200..15
[5] Karsten M. Borgwardt, M. Elisabetta Ghisu, Felipe Llinares-López, Leslie O' Bray, and Bastian Rieck. Graph kernels: State-of-the-art and future challenges. Found. Trends Mach. Learn., 13 (5-6), 2020. doi TO. 101/220000000
[6] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, May 2011. ISSN 2157-6904. hti www.
http:////...111/1111119999999990 199
Software available http:
//www.csie ntu. edu. tw/ wtwp/jjiin/ill 1ibssm
[7] Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph- structured data. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 1576-1586, PMLR, 2020. URL http:://proceeednngggg mlr. pptpss/v19//heeeeeeeeeeeee html
[8] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40: 10:144 Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2018. doi [00422/0LLIIsS.CCALPPP01.
[9] Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen D. Bruijne, and Karsten Borgwardt. Scalable kernels for graphs with continuous attributes. In Advances in Neural Information Processing Systems 26, pages 216-224, 2013. Erratum available at hhtp::/ /ttmage/mmmeee diku. dk/ hasa//pppess/graaikeenn.... s_t_s__nnp__________eee wwwpmniipsssttieeee erratum. pdf
[10] John Figueras. Morgan revisited. Journal of Chemical Information and Computer Sciences, 33 (5):717-718, 1993.
[11] Andrew Gardner, Christian A. Duncan, Jinko Kanno, and Rastko R. Selmic. On the definiteness of earth mover's distance and its relation intersection. IEEE Trans. Cybern., 48(11): 3184-3196, 2018. T00.0//C.CY...1...27611
[12] Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines, volume 2777 of LNCS, pages 129-143. Springer Berlin Heidelberg, 2003. doi 111.11099788835544456566
[13] Floris Geerts, On the expressive power of linear algebra on graphs. Theory Comput. Syst., 65(1): 279, 2021. 0001110..00777002224000000099999
[14] Floris Geerts, Filip Mazowiecki, and Guillermo Pérez. Let's agree to degree: Comparing graph convolutional networks in the message-passing framework. In 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, pages 3640-3644 PMLR, 2021.
[15] Martin Grohe. The logic of graph neural networks. In 36th Annual ACM/IEEE Symposium on Logic Computer Science, LJCS 2021, Rome, Italy, June 29 July 2, 2021, pages 1-17. IEEF, 2021. doi 10. 10001109/1 2022 19970677

---

[16] Bernard Haasdonk and Claus Bahlmann. Learning with distance substitution kemels. In Pattern Recognition, volume 3175 of LNCS, pages 978-3-540-22945-2 doi 10.10077978-3-54022220 28649-3
Springer Berlin Heidelberg, 2004. ISBN
[17] Z. Harchaoui and F. Bach. Image classification with segmentation graph kernels. In FEEE Conference on Computer Vision and Pattern Recognition, pages 1-8, 2007.
[18) Sergei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding isomorphism bias in graph data sets. CoRR, abs/1910. 12091, 2019.
[19] Janis Kalofolias, Pascal Welke, and Jilles Vreeken. SUSAN: the structural similarity ran- dom walk kernel. In Proceedings of the 2021 SIAM International Conference on Data Mining, SDM 2021, Virtual Event, April 29 May I, 2021, pages 298-306. SIAM, 2021.
[20] Kang, Hanghang Tong, and Jimeng Sun. Fast random walk graph kernel. Proceed- ings of the 2012 SIAM International Conference Data Mining, pages 828-838, 2012. doi 97119771777811119282555
[21] Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Machine Learning, Proceedings of the Twentieth International Conference (ICMI. 2003), August 21 2003, Washington, DC, USA, pages 321-328. AAAI Press, 2003.
[22] Kristian Kersting, Martin Mladenov, Roman Garnett, and Martin Grohe Power iterated color refinement, In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 1904-1910. AAAI Press, 2014.
[23] Thomas N. Kipf and Max Welling. Semi- semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR. OpenReview.net, 2017.
[24] Nils M. Kriege, Pierre-Louis Giscard, and Richard C. Wilson. On valid optimal assignment kernels and applications to graph classification. In Advances in Neural Information Processing Systems 29, NIPS 2016, pages 1615-1623, 2016.
[25] Nils M. Kriege, Marion Neumann, Christopher Morris, Kristian Kersting, and Petra Mutzel. A unifying view of explicit and implicit feature maps of graph kernels. Data Mining and Knowledge Discovery, (3366):5555-1555 1547, 2019. doi 100010000/11011101990066666
[26] Nils M. Kriege, Fredrik Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1):6, 2020.
[27] Tao Lei. Wengong Jin, Regina Barzilay, and Tommi S. Jaakkola. Deriving neural architectures from sequence and graph kernels. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 I August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2024-2033. PMLR, 2017. http:
//proceedings.o mlr, cxres/v77//eeilie html
[28] Mahé and J.-P. Vert. Graph kernels based on tree patterns for molecules. Machine Learning, 75 (1):3-35, 2009.
[29] Pierre Mahé, Nobuhisa Ueda, Tatsuya Akutsu, Lean-Luc Perret, and Jean- Phin-Philippe Vert. Extensions of marginalized graph kernels. In Proceedings of the twenty-first international conference on Machine learning, ICML '04, pages 70-, New York, NY, USA, 2004. ACM. ISBN 1-88113-838-5. htpph/tt///ooi..mmm.rrg 1ttt://000..11111111111011011110
[30] H. L. Morgan. The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service. Journal of Chemical Documentation, 1(7)
1965. doi 10.
[31] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 February 2019, pages 4602-4609. AAAI Press, 2019. 10.6099.aaaaa v33101.3301400
12

---

[32] Christopher Morris, Nils M. Kriege. Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[33] Christopher Morris, Matthias Fey, and Nils M. Kriege. The power of the Peisfeiler-Lemae algorithm for machine learning with graphs. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence. IJCAI 2021, Virtual Event Montreal, Canada, 19-27 August 2021, pages 4543-4550. ijcai.org, 2021. doi 100.24963/ica..2221666.
[34] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt. Weisfeiler and Leman go machine learning: The story so far. CoRR, abs/21 12.09992, 2021.
[35] Hoang Nguyen and Takanori Maehara. Graph homomorphism convolution. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7306-73111 PMLR, 2020.
[36] David L. Powers and Mohammad M. Sulaiman. The walk partition and colorations of a graph. Linear Algebra and its Applications, doi/hhtpss//doii.org IO.. 101101660002243395553 (9000444
48:145-159, 1982. ISSN 0024-3795.
[37] J. Ramon and T. Gärtner. Expressivity versus efficiency of graph kemelss. In International Workshop on Mining Graphs, Trees and Sequences, pages 65-74, 2003.
[38] M. Razinger. Extended connectivity in chemical graphs. Theoretica chimica acta, 61(6)5881-886
1982.
[39] John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, New York, NY, USA, 2004. ISBN 0521813972.
[40] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. J. Mach. Learn. Res., 12:2539-2561, 2011.
[41] Mahito Sugiyama and Karsten M. Borgwardt. Halting in random walk kernels. In Advances in Neural Information Processing Systems 28, pages 1639-1647, 2015.
[42] Matteo Togninalli, M. Elisabetta Ghisu, Felipe Llinares-L.ópez, Bastian Rieck, and Karsten M. Borgwardt. Wasserstein Weisfeiler-lehman graph kernels. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 6436-6446, 2019.
[43] S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Imre Kondor, and Karsten M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010.
[44] Zonghan Wu. Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 32 (1):4 24, 2021. doi I0. IO9//NNLS..0002222222222
[45] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR. OpenReview.net, 2019.
[46] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. In Advances Neural Information Processing Systems 30: Annual Conference on Neural Informaionn Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3391-3401, 2017.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] The running time prevents direct
application to large-scale graphs which is briefly discussed in Section (42
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work
is mainly theoretical and has no specific societal impacts beyond that of graph learning
general.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] All used datasets are publicly available. The URL the repository with the code is included in the manuscript.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report enror bars (e.g.. with respect to the random seed after running experiments multiple times)? [Yes] Standard deviations of accuracy values are reported Table [] (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] The hardware is mentioned in Section 5.1
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Datasets from publicly available repositories were used, which are referenced or linked.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "PS-Su4xWnW", "reviewer": "Reviewer_cwFz", "summary": "\n\nThe paper formally relates finite length node centered random walks to the Weisfeiler Lehman method.  \nThe Weisfeiler Lehman vertex relabeling algorithm produces a hierarchy of vertex labels, which is shown to be related to a vertex label hierarchy that can be obtained from multisets of vertex centered walks, which correspond to root-leaf paths in the unfolding trees of various depths.\nThe paper subsequently develops variants of a vertex kernel that is based on multisets of labeled walks, relates them to the random walk, as well as the weisfeiler lehman subtree kernel, and empirically shows that it performs well in practice.", "questions": "Proposition 3.9 is correct if the base kernel used for vertex comparison within the walks is $k_V$ as defined in Line 202. However, it seems that using a different base kernel, such as $k(u,v) = 0 \\ \\forall u,v \\in V(G)$ should yield $\\hat{k}^+_\\ell(u,v,a) = 1 \\  \\forall u,v \\in V(G) \\ \\forall \\alpha\\geq 0$. Therefore, for this (obviously useless) base kernel, Proposition 3.9 would not hold. It hence seems that Line 202 'w.l.o.g' might be misleading. Furthermore, it should be stressed that Prop. 3.9 is somewhat specific to the base kernel $k_V$ (as it is also used in the proof). \nIn fact, any kernel that identifies two or more vertex labels will result similar issues.\nIs my assessment correct?\n\n\nIn the experimental section, I am a bit lost. I am assuming that NCW is the kernel as of Definition 4.1 with $\\hat{k}^+_i$ and $k_i$ computed by Algorithm 1 _without the blue Line 9_, while NCWWL is _the same, with Line 9_? \nIt might reduce (at least my) potential confusion if you could clearify this a bit more.\n\nIn the experimental evaluation of the expressivity, it seems that $\\alpha = 1000$ is a rather large parameter for the rbf part of Def 4.1. It seems to be the largest parameter that you consider in the experiments. Why do you choose $\\alpha=1000$ and $\\beta=0$ here? How does the expressiveness change if the parameters are changed? Also, how does NCWWL behave? \n\n\nThe paper is very nicely and cleanly written. It has been a real pleasure reading it! Minor typos and issues that I have found are listed below:\n\n- l58: Our Contribution -> Our contribution\n- l143/Fig.1: It seems that Fig(1a) shows the unfolding trees of nodes $f$ and $e$, not $f$ and $g$, as mentioned in line 143. The text is correct for $f$ and $g$. I was confused for a while. \n- l223: a techniques\n- l228: line -> Line\n- l300: TuDatsets (also in appendix somewhere)\n- Fig2: the Label kernel is not described in the experimental section. Is it VL, EL, or a combination of the two?\n", "limitations": "\nThe authors don't report runtimes of the kernel computation and mention runtime improvements as future work. Another mentioned limitation is the current restriction to node label information and to discretely labeled graphs. It seems that these limitations are not inherent to the node centric $\\ell$-walk graph kernel, but merely due to implementation and/or scope of the experiments. \n", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written and technically very precise. It was a pleasure to read and easy to follow. \nEvery step is very clearly presented and seems to follow naturally. However, in the almost twenty (resp. fifteen) years since the introduction of random walk (resp. WL subtree) kernels, nobody (as of my knowledge) has yet drawn this connection this rigorously. This insight deserves to be published at a very good conference. \n\nA generalized $\\ell$-walk node kernel is proposed as a result of the insights on the connection between WL and RW refinement hierarchies.\nIt can be seen as a soft (a little bit weaker) version of the discrete WL vertex kernel. It is hence related to recent approaches which try to weaken the strict dirac-delta comparison of node labels/unfolding trees of the WL subtree kernel. The resulting node centric $\\ell$-walk graph kernel is then shown to generalize the random walk kernel, as well as the Weisfeiler Lehman subtree kernel in the limit $\\alpha \\to \\infty$. \nAs a result of the comprehensive view that the authors have, it can be readily computed using the machinery that was developed over the last decades.\nEmpirical evaluation suggests that the theoretical results on expressiveness translate to comparable predictive performance and expressiveness in practice. \n\nThe only 'weakness' that I want to briefly mention is that now that this connection is made, there is an open field of practical questions that could be addressed, regarding the application of 'Weisfeiler-Lehman-like' kernels to attributed graphs, which can now potentially be addressed by choice of suitable base kernels. \nWhile certainly out of scope of this article, I am eager to see more. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7p26j--UAuc", "reviewer": "Reviewer_58fn", "summary": "This paper gives a unified view on random walk kernels and Weisfeiler-Leman subtree kernel and relate walk-based label refinement to the Weisfeiler-Leman method. They derive a node-centric walk kernel on graphs which generalizes the classical random walk kernel and allows grouping of walks by their start node. They verify the theoretical results on real-world graphs and show that their method has higher accuracies, surpassing the Weisfeiler-Leman subtree kernel in some cases.", "questions": "We do not have questions. ", "limitations": "They address it adequately.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality and Significance: This work is the first that relate random walks in labeled graphs and the Weisfeiler-Leman method formally and show that classical random walk kernels with only minor modifications regarding definition and computation are as expressive as the widely-used Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison. The contributions play well into previous work as a helpful summary as well as extension and also bring inspiration to future research.\nQuality: The paper is well done with sufficiently proved theoretical results and the detailed experiments which verified the key problems the paper concerned(Q1-Q3).\nClarity: Clear writing and structure. \n\n**Weaknesses:** Some notations are recommended to be mentioned like $  \\Delta $ in line 109.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7XADe9WBLQq", "reviewer": "Reviewer_kGem", "summary": "The paper proposes a walk-based kernels for graphs with nodes being labeled with WL labeling scheme. It is supposed to improve expressiveness of random walk kernels and can be as good as WL subtree kernels. \n\n--------------------\nAfter looking at responses, other reviews and the paper again, I do find the paper does offer a new way to compute kernels, even though not strictly solving the expressiveness problem of previous work, may offer a new view and future development. I think I can raise my evaluation a bit.", "questions": "What is the benefit of the proposed kernels? What does controlling the strictness of neighborhood comparison help classifying graphs in practice? What's the benefit of node/edge similarities?\n", "limitations": "The paper is clear about its limitations.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper's originality is in its combination of walk-based kernels with WL labeling scheme. This is proved to be an improvement on random walk kernels, but not on WL-based kernels.\n\nThe paper show many properties of the proposed methods, which I could not check in details, can be interesting. The paper's writing is clear. \n\nHowever, all of these do not seem to solve any problem of graph kernels. The approach is shown that can be as good as WL kernels with more computation. I cannot see the benefit of the paper in practice.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "7UAC7pWil7B", "reviewer": "Reviewer_rmAL", "summary": "The paper presents a novel framework to describe random walk kernels. First, a unified view is provided to integrate and relate random walk kernels with the popular Weisfeler-Lehman (WL) framework. The paper also introduces a modification of the classical random walk kernel, which allows to improve the expressivity to match the performance of the WL kernel. Experimental analysis is showed to compare the proposed framework with existing graph kernels. ", "questions": "Have the authors compared to the GraphHopper kernel? The kernel formulation seem quite similar, in terms of adding a label-based similarity. I guess one can see the current kernel as an extension of the RW kernel, as the GraphHopper kernel is an extension of the classical shortest path. \n\nI believe that a stronger experimental section might help to show the actual benefit of the approach. The impact of the paper in the current status is moderated. In particular, I would suggest:\n\n- Extensive runtime evaluation: this is especially important given that he RW kernels are computationally expensive\n- Application on attributed graphs: given that the performance superiority to WL is limited, this additional use case would be beneficial  to improve the experimental comparison and show the benefit of the approach. \n- Potentially, find simulated or real case graphs where the kernel can capture information missed by WL", "limitations": "No negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n- The paper is well written and properly structured, with good notation and clarity of presentation\n- Both the experimental evaluation and theoretical framework are solid and robust\n\nWeaknesses:\n\n- The originality is limited. While the integration of these kernel approaches in a unified view is innovative, the methodological changes in the kernel are incremental\n- The experimental results are also limited. The actual benefit of the modified RW kernel is not reflected in the results. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept