Geometric Random Walk Graph Neural Networks via Implicit Layers
Authors: Giannis Nikolentzos
Michalis Vazirgiannis
Venue: ICLR 2022 Submitted (2022)

Abstract: Graph neural networks have recently attracted a lot of attention and have been applied with great success to several important graph problems. The Random Walk Graph Neural Network model was recently proposed as a more intuitive alternative to the well-studied family of message passing neural networks. This model compares each input graph against a set of latent ``hidden graphs'' using a kernel that counts common random walks up to some length. In this paper, we propose a new architecture, called Geometric Random Walk Graph Neural Network (GRWNN), that generalizes the above model such that it can count common walks of infinite length in two graphs. The proposed model retains the transparency of Random Walk Graph Neural Networks since its first layer also consists of a number of trainable ``hidden graphs'' which are compared against the input graphs using the geometric random walk kernel. To compute the kernel, we employ a fixed-point iteration approach involving implicitly defined operations. Then, we capitalize on implicit differentiation to derive an efficient training scheme which requires only constant memory, regardless of the number of fixed-point iterations. The employed random walk kernel is differentiable, and therefore, the proposed model is end-to-end trainable. Experiments on standard graph classification datasets demonstrate the effectiveness of the proposed approach in comparison with state-of-the-art methods.

Under review as a conference paper at ICLR 2022
GEOMETRIC RANDOM WALK GRAPH NEURAL NET- WORKS VIA IMPLICIT LAYERS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have recently attracted lot of attention and have been ap- plied with great success to several important graph problems. The Random Walk Graph Neural Network model was recently proposed as a more intuitive alterna- tive to the well-studied family of message passing neural networks. This model compares each input graph against a set of latent "hidden graphs" using a kernel that counts common random walks up to some length. In this paper, we propose a new architecture, called Geometric Random Walk Graph Neural Network (GR- WNN), that generalizes the above model such that it can count common walks of infinite length in two graphs. The proposed model retains the transparency of Ran- dom Walk Graph Neural Networks since its first layer also consists of a number of trainable "hidden graphs" which are compared against the input graphs using the geometric random walk kernel. To compute the kernel, we employ a fixed-point iteration approach involving implicitly defined operations. Then, we capitalize on implicit differentiation derive an efficient training scheme which requires only constant memory, regardless of the number of fixed-point iterations. The em- ployed random walk kernel is differentiable, and therefore, the proposed model is end-to-end trainable. Experiments on standard graph classification datasets demonstrate the effectiveness of the proposed approach in comparison with state- of-the-art methods.
INTRODUCTION
Recent years have witnessed an enormous growth in the amount of data represented as graphs. In- deed, graphs emerge naturally in several domains, including social networks, bioinformatics, and neuroscience, just to name a few. Besides the increase in the amount of graph-structured data, there is also growing interest in applying machine learning techniques to data modeled as graphs. Among others, the graph classification and graph regression tasks have attracted great deal of attention in the past years. These tasks have served as the fundamental building block within ap- plications that deal with problems ranging from drug design Kearnes et al. (2016) session-basee recommendation Wu et al. (2019).
Graph Neural Networks (GNNs) provide a powerful tool for machine learning graphs, So far, the field of GNNs has been largely dominated by message passing architectures. Indeed, most of them share the same basic idea, and be reformulated into a single common framework, called message passing neural networks (MPNNs) Gilmer et al. (2017). These models employ message passing procedure to aggregate local information of vertices. For graph-related tasks, MPNNs usually apply some permutation invariant readout function to the vertex representations to produce representation for the entire graph. The family of MPNNs has been heavily studied in the past few years, and there are now available very expressive models which have achieved state-of- the-art results in several tasks Xu et al. (2019); Morris al., (2019). Although the family of MPNNs is perhaps the most successful story in the field of graph representation learning, there exist models that follow different design paradigms and do not fall into this family. An example of such a model is the recently proposed Random Walk Graph Neural Network (RWNN) Nikolentzos & Vazirgiannis (220)). This model contains a number of trainable "hidden graphs", and compares the input graphs against these graphs using random walk kernel which counts the number of common walks in two graphs. The emerging kernel values are fed into a conneccddd neural network which acts as the classifier or regressor. The employed random walk kernel is differentiable, and thus RWNN is end-

---

Under review as a conference paper at ICLR 2022
to-end trainable. However, this kernel considers only random walks of small length. Such local patterns may fail to capture the overall large-scale shape of the graphs, while several interesting properties of graphs depend on the graph's global structure. Furthermore, increasing the length of the walks has a direct impact on the model's computational complexity.
In this paper, we propose novel approach tackle these challenges. Specifically, we propose new architecture, called Geometric Random Walk Graph Neural Network (GRWNN), that general- izes the RWNN model such that can count common walks of infinite length in two graphs. The model contains a number of trainable "hidden graphs", and it compares the input graphs against these graphs using the geometric random walk kernel. Thus, instead of walks of small length, the proposed model considers walks of infinite length. To compute the kernel. GRWNN uses a fixed- point iteration approach. The kernel values are then passed on to a fully-connected neural network which produces the output. The proposed neural network is end-to-end trainable since we can di- rectly differentiate through the fixed-point equations via implicit differentation, which leads to a very efficient implementation in terms of memory requirements. Hence, we can still update the "hidden graphs" during training with backpropagation. We compare the performance of the proposed model to of-teoofthhe-rt graph kernels and recently-proposed neural architectures several graph clas- sification datasets. Results show that in most cases, the GRWNN model matches or outperforms competing methods. Our main contributions are summarized as follows:
We propose a novel neural network model, Geometric Random Walk Graph Neural Net- work, which employs the geometrie random walk kernel to produce graph representations. The model counts common walks of infinite length in the input graph and a set of randomly initialized "hidden graphs".
We employ an efficient scheme to compute the random walk graph kemel using fixed-poin iterations. We show that we can directly differentiate through the fixed exed-point equations via implicit differentation, which leads to an efficient implementation.
We evaluate the model's performance on several standard graph classification datasets and show that it achieves results similar and in some cases superior to those obtained by recent GNNs and graph kernels.
2 RELATED WORK
Graph kernels have a long history in the field of graph representation learning Kriege et al. (2020). A graph kernel is a kernel function between graphs, i. c., symmetric positive semidefinite function defined on the space of graphs. These methods generate implicitly (or explicitly) graph representa- tions and enable the application of kernel methods such as the SVM classifier to graphs. Most graph kernels are instances of the R-convolution framework Haussler (1999), and they compare substruc- tures extracted from the graphs to each other. Such substructures include shortest paths Borgwardt & Kriegel| (2005), random walks Gärtner et al. (2003;; ); Kashima et al. (2003), small subgraphs Sher- vashidze et al. (2009), and others. Our work is related to random walk kernels, i.c kernels that compare random walks to each other. The first such kernels were proposed by Gärtner et al. Gärtner let al. (2003) and by Kashima et al. Kashima et al. (2003). The work of Kashima et al. was later refined by Mahé et al. Mahé et al. (2004). Vishwanathan et al. Vishwanathan et al. (2010) and Kang et al. Kang al. (2012) proposed new algorithms for efficiently computing random walk kernels. These algorithms improve the time complexity of kernel computation. Sugiyama and Borgwardt studied the problem of halting ei. longer walks are downweighted
much that the kernel value is completely dominated by the comparison of walks of length 1) that occurs in random walk ker- nels, and showed that its extent depends on properties of the graphs being compared [Sugiyama & Borgwardt (2015). Zhang el al. defined different kernel which does not compare random walks to each other, but instead, compares the return probabilities of random walks Zhhng et al. (20T8h). Finally, Kalofolias et al. proposed a variant of the random walk kernel where structurally dissimilar vertices are not just down- weighee,,, but are not allowed to be visited during the simultancous walk Kalofolias et al. (0021).
Although the first GNNs were proposed several years ago Sperduti & Starita (997]. Scarselli et al. 2009);; Micheli (2009), until recently, these models had attracted limited attention. In recent years, with the rise of deep learning, a lot of models started to emerge Bruna et al. (2014); Li et al. (2013);
Duvenaud al. 2205);; Atwood & Towsley (2016): Defferrard et al. (2016): Lei al. (017). Most
2

---

Under review as a conference paper at ICLR 2022
models update the representation of each vertex by aggregating the feature vectors of its neighbors. This update procedure can be viewed as a form of message passing algorithm and thus, these models are known as message passing neural networks (MPNNs) Gilmer al. (2017). To compute a feature vector for the entire graph, MPNNs apply some permutation invariant readout function to all the ver- tices of the graph. The family of MPNNs has been heavily studied in the past few years, and there are now available several sophisticated models which can produce expressive graph representations Xu et al. (2019); Morris et al. (2019); Dehhmamy al. (211)); Morris et al. (2020). Despite the gen- eral recent focus on MPNNs, some works have proposed architectures that are not variants of this family of models Niepert et al. (2016); Maron et al. (2019bla), Niikolnnzzos & Vazirgiannis (2020). The work closest to ours is the one reported in Nikolentzos & Vazirgiannis (2020) which presents the Random Walk Graph Neural Network (RWNN model. fact, in this paper, we generalize the RWNN model to compare random walks of infinite length in two graphs. Recently, another method that uses random walks to extract features which are then processed by a standard convolutional neu- ral network was proposed Toenshoff al. (02TT) However, the proposed approach decouples data representation from learning since random walks are sampled in a preprocessing stage. Our work is also related to implicit models which have been applied successfully many problems de Avila Belbute-Peres et al. (2018); Chen et al. (2018); AAmss et al. (2018); Bai et al. (2019). The outputs of these models are determined implicitly by solution of some underlying sub-problem. Implicit models have also been defined in the context of graph representation learning. For instance, Gu et al. proposed IGNN, a model that seeks the fixed peedtppinttoo of some equation which is equivalent to run- ning an infinite number of message passing iterations Gu et al. (2020). Thus, the final representation potentially contains information from all neighbors in the graph capturing long-range dependencies. Gallicchio and Micheli proposed a similar model which generates graph representations based on the fixed point of a recursive/dynamical system, but is actually only partially trained Gallicchio & Micheli (2020). In contrast to these approaches whose objective is to apply a large (or infinite) number of message passing layers implicitly, in our setting, we employ a fixed-poii point iteration ap- proach to compute the random walk kernel and then directly differentiate through the fixed point equations via implicit differentation.
3 PRELIMINARIES
3.1 NOTATION
Let [n] (1......1) n) C N for n 2 1. Let G = EV) be an undirected graph, where V is the vertex set and E is the edge set. We will denote by the number of vertices and by the number of edges. The adjacency matrix A E Raxa of a graph G symmetric (typically sparse) matrix used to encode edge information in the graph. The element of the 7th row and jth column is equal to the weight of the edge between vertices i and by if such an edge exists, and 0 otherwise. The degree d(v) of vertex v is equal to the sum of the weights of the edges that are adjacent to the vertex. For vertex-attributed graphs, every vertex in the graph is associated with a feature vector. We use X Ra to denote the vertex features where d is the feature dimensionality. The feature of a given vertex U; corresponds to the jth row of X.
The direct (tensor) product Gx =Vxx Ex) of two graphs G (V, E) and G' (V', E') is defined as follows:
Vx= =(1,,0) E V
Ex = (((r, (u, E Vv x Vx (v,u) E E, and (V. w!) E E'}
We denote by Ax the adjacency matrix of Gx, and denote by Ax and dx the maximum and average of the vertex degrees of Gx, respectively. Thus, dx 1/a EvEv, d(v). A walk in graph is a sequence of vertices such that consecutive vertices are linked by an edge. Performing a random walk on the direct product Gx of two graphs G and G" is equivalent to performing a simultaneous random walk on the two graphs G and G'.
We use @ to represent the Kronecker product, and use O to represent elementwise multiplication between two matrices or vectors of the same dimension. For p X g matrix V, vec(V) E R represents the vectorized form of V. obtained by stacking its columns. Let also vec denote the inverse vectorization operator which transforms vector into a matrix. e., for pq vector v, V = vee (v) where V E IRxx (see the appendix for the exact definition of the vec and vec operators).
3

---

Under review as a conference paper at ICLR 2022
3.2 RANDOM WALK KERNEL
Given two graphs G and G", the random walk kernel counts all pairs of matching walks on and G" Gärtner al. (2003). There different variants of the kernel. For instance, the p-step random walk kernel (where & N) counts all pairs of matching walks up to length on two graphs. The number of matching walks can be obtained through the adjacency matrix Ax of the product graph Gx Vishwanathan et al. (2010) since random walk on Gx is equivalent to a simultaneous random walk on the two graphs. Assuming a uniform distribution for the starting and stopping probabilities over the vertices of two graphs, the p-step random walk kernel is defined as:
VVx
Vx
xP <G, = -
A
|=0
where An A1, Az,................. ......... .2....... Ap are positive, vallee weights, and A the identity matrix, i. e., A I. For - 50, we obtain N (G, G") which is known as the random walk kernel.
turns out that if the sequence of weights Ag. A1 A2.... coresponds to the geometric sequence defined as x = X, then the limit xxx (G, can be computed analytically as follows:
IV |V
A. (=
== EAA
= -1 AAx) (I)
if
is well-known that the geometric series of matrices I+ xAx + (AAx)*++.... converges the maggntuee eigenvalue of Ax (which is also the maximum eigenvalue if Gx is graph with non-negative edge weights), denoted by y is strictly smaller than L/A. Therefore, the geometric random walk kernel & is well-defined only if X < 1/2gar. Interestingly, the maximum eigenvalue of y is sandwiched between the average and the maximum the vertex degrees of Gx Brouwer & Haemers 2. We thus have that dx I 1 uga geometric senes of matrices is guaranteed to converge.
e only if the
Ax, and by setting À 1/Ax, the
the vertices of G' and G', we can obtain a probabilistic variant of the geometric random walk kernel. Let p and p' be two vectors that represent the initial probability distributions denote stopping probability distributions over the vertices of G and G'. For uniform distributions for the initial and stopping probabilities over the vertices of the two graphs, we have p; q: = 1/1V and P = q 1/1v"). Then, Px pp' and qx = qq" and the variant of the geometric random walk kernel can be computed as 0: (G, G') = vec(qx) T(I
By defining initial and stopping probability distributions
the vertices of G and G'. Likewise, let q and q'
(I- -vxx)>>ee((p))
4 GEOMETRIC RANDOM WALK GRAPH NEURAL NETWORKS
The proposed GRWNN model maps input graphs to vectors by comparing them against a number of "hidden graphs", c., graphs whose adjacency and attribute matrices are trainable. The function that we employ to compare the input graphs against the "hidden graphs" is the geometric random walk graph kernel, of the most well-studied kernels between graphs Gärtner et al. (2003); Mahé al. 2004); Vishwanathan et al. 2010). The proposed GRWNN model contains "hidden graphs" in total. The graphs may differ from each other in terms of size (i. number of vertices). Further- more, the vertices and/or edges of those graphs can be annotated with continuous multi-dimennsionll features. As mentioned above, both the structure and the vertex attributes (if any) of these "hidden graphs" are trainable. Thus, the adjacency matrix of a "hidden graph" G; of size n is described by trainable matrix W; Rax=, while the vertex attributes are contained the rows of another train- able matrix Q: E Raxdd Note that the "hidden graphs" correspond to weighted graphs, which can be directed or undirected graphs with or without self-loops. In our implementation, we constraint them to be undirected graphs without self-loops (n(n-1)/2 trainable parameters in total).
To compare an input graph G against a "hidden graph" G, the model uses the geometric random walk kernel that was introduced in the previous section:
Vv V Σ
IVx
|V
k. GG,
Σ
XA
(a- AAx) 11 xAx) (2)

---

Under review as a conference paper at ICLR 2022
where Ax A and A, is the adjaceney matrix of "hidden graph" G, obtained as A, f(W). Here, f(-) is a function whose output is non-neganee non-negative and potentially bounded, i.c., f(W.) = ReLU(W.)) or f(W.) = (W,) where ar-)) denotes the sigmoid activation function. Then, given the set On = [G1, G2...., Gr) where G1, G2,...... ,G denote the N "hidden graphs", we can compute N kernel values in total. These kernel values can be thought of features of the input graph, and can be concatenated to form a vector representation of the input graph. This vector can then be fed into a fully-connected neural network to produce the output.
Following Vishwanathan et al. (2010), to compute the geometric random walk graph kernel shown in Equation equation 2 above, we employ a two-step approach. We first need to solve the following linear system for z:
(I- x=Ax))z=1
Then, given z, we can compute the kernel value as h (G, G.) = 1 To solve the above linear system, we capitalize on fixed point methods. We first rewrite the above system as:
z -=1+AA, z
(3)
Now, solving for z is equivalent to finding a fixed point of Equation equation 3 Nocedal & Wright (2066) Such a fixed point can be obtained by simply iterating the first part of the forward pass. Letting (²)) denote the value of at iteration we set (0) 1, and then compute the following:
z (++1) 1+ AA
<, where |||| denotes the Euclidean norm and e some predefined tolerance or until specific number of iterations has been reached. As mentioned in the previous section, the above problem is guaranteed to converge if the maximum eigenvalue of Ax is strictly smaller than 1/A, thus if all the eigenvalues of XAx lie inside the unit disk. the values of the elements of A; are bounded, we can compute upper bound on the maximum degree of Gx and set the parameter À to some value smaller than the inverse of the upper bound.
repeatedly until [|z((+1)- |1 -
Efficient implementation. If the input graph G consists of vertices and a "hidden graph" G, consists of e vertices, then Ax is an nc x ne matrix. Thus, multiplying Ax by some vector inside the fixed-point algorithm requires (()²c²) operations in total. Fortunately, compute the kernel, it is not necessary to explicitly compute matrix Ax. Specifically, the Kronecker product and vec operator are linked by the well-known property [ernstein (2009):
vec(ABC) = (CT @ (B)
(4)
Then, let Z E R be a matrix such that Z = vee (z). Recall also that Ax A & Aq. Based on the above and Equation equation 4
write:
Ax z = (A & Ae) = vec(A, ZA T) = vec (())
(5)
The above matrix-vector product can be computed in O(n'c) time in case > c. If A sparse, then it can be computed yet more efficiently. Furthermore, we do not need to compute and store matrix Ax which might not be feasible due high memory requirements. Then, instead of solving the system of Equation equation
we solve the following equivalent system:
1 + À vee (A, vec Az)
Node attributes. In many real-world problems, vertices of the input graphs are annotated with real-valued multi-dimennional vertex attributes. We next generalize the proposed model to graphs that contain such vertex attributes. Let X E Ra denote the matrix that contains the vertex at- tributes of the input graph G. As already mentioned, we also associate a trainable matrix Q₁ E Rexd to each "hidden graph" G; where cis the number of vertices of G, Then, let S o( Q E Rex= where ar (.) denotes the sigmoid function. The (j, 4h element of matrix S is equal to the inner prod- uct (followed by a sigmoid) between the attributes of the jth vertex of the input graph and the th vertex of the "hidden graph" G, Roughly speaking, this matrix encodes the similarity between the attributes of the vertices of the two graphs. Note that instead of directly using matrix X, we can first transform it into matrix X using a single- or a multi Mayli-llyyrrree perceptron. Let s = vec(S) where Rae. Each element of corresponds to vertex of Gx and quantifies the similarity between
5

---

Under review as a conference paper at ICLR 2022
the attributes of the pair of vertices (i. e., one from G and one from G,) it represents. Then, compute the geometric random walk kernel as follows:
&
k GG
-
Σ
X ((ss "olss")AAA )OAx)
i=
L=
1/
M&
(I- o
=1 -I A(ss )x
Note that since the elements of take values between 0 and the same applies to the elements of the output of the outer product ss'. Therefore, the maximum degree of the vertices of the graph derived from the matrix ss' o Ax is not greater than that of the graph derived from matrix A Ax, and we do not thus need to set À to new value. Then, to compute the kemnl,, we first need to solve the following system:
z = 1 + A(ss o Ax)z
(8)
Again, naively computing the right part of the above Equation is expensive and requires Onn operations in total. The following result shows that in fact we can compute the above in a more time and memory efficient manner.
Proposition 1. Let A1 e R and A2 E Rm be two real matrices. Let also s, E Im be two real vectors. Then, we have that:
(ss o (A1 & Az))y @ vec (Ac
vec ' OS)A,)
Based on the above result (the proof is left to the appendix), the system that needs to solved is:
z 1 X vec(A, vec (z(s)
Since store matrix A sparse matrix, if there O(m) non-zero entries in A, then com- puting one iteration of the above equation for all N "hidden graphs" takes O(Ne(n(d + c) + m)) computational time where the size of the vertex attributes.
Implicit differentiation. Clearly, iteratively computing Equation equation or Equation equa- tion g to find the fixed point corresponds to a differentiable module. However, to train the model, need to backpropagate the error through the fixed point solver in the backward pass. That would require storing all the intermediate terms, which could be prohibitive in practice. Fortunately, thanks recent advances in implicit layers and equilibrium models Bai al. (2019), this can be performed in simple and efficient manner which requires constant memory, and assumes no knowledge of the fixed point solver. Specifically, based on ideas from Bai et al.) (2019), we derive the form of implicit backpropagation specific to the employed fixed point iteration layer.
Let fe be the system of Equation equation Equation equation & and z" E Rac be a solution to that linear system. Let also go (z" ; A, X) = To(zz; : A, -z =z" Since z" is fixed point, we have that < A, X) - O and zº is thus the root of ga- Lei E R denote the ground-truth target of the input sample, loss function that computes:
Theorem 1.
IR be any differentiable function and let L
R + R be
i L 2)),2) = C(1(11 (all(11Findal FindRoot(ge; A, A,X)),
(9)
Then, the gradient of the loss w.r.t. (-) (e. g., O. or X) is:
Oe ae (J (x.) ;
0e ah Th Oz (J=1l 1z
0fo(z"; A,
(10)
0(.)
Oz
a(.)
0(-)
where J-1l| | the inverse Jacobian of go evaluated at z".
The above formula gives form for the necessary Jacobian without needing to backpropagate through the method used to obtain the fixed point. Thus, as mentioned above, we only need to find the fixed point, and above analytical form. No intermediate terms of the iterative method used to compute the fixed point need to be stored in memory, while there is also need unroll the forward computations
compute the necessary Jacobians at this specific point using the

---

Under review as a conference paper at ICLR 2022
within an automatic differentiation layer. Still, compute the analytical backward gradient the solution of the fixed point equation, is necessary to first compute the exact inverse Jacobian J which has a cubic cost. As shown in Bai et al. (201)), we can instead compute the ae (Jm) oz
term by solving the following linear system:
(Diolet:A Oz
Oe
x =
Oz
which in fact is also a fixed point equation and can be solved via some iterative procedure. Note that the first term of the above Equation is cector-Jacobian product which can be efficiently computed via autograd packages (c. g., PyTorch [Pszke et al. (2017) for any x, without explicitly writing out the Jacobian matrix. Finally, we can compute
oT 8(] follows:
de 0())
0fo @fo(zz; T x
0(-)
where again this product is itself vector-Jacobian product, computable via normal automatic dif- ferentiation packages.
5 EXPERIMENTAL EVALUATION
We next evaluate the proposed GRWNN model on standard graph elassification datasets.
Datasets. We evaluate the proposed model on 10 publicly available graph elassification datasets including 5 sro/chemm-informmties datasets: MUTAG, D&D, NCII, PROTEINS, ENZYMES, and social interaction datasets: -IDB-B,,,RY, IMDB-M MULTI,
BEDDIT-BINARY REDDIT-MULTI- 5K, COLLAB Kersting al. (016)) To show that the proposed model also scales to larger datasets, we additionally use two Open Graph Benchmark (OGB) datasets Hu et al. (020). Specifically, we use molecular property prediction dataset: ogbg mo molhiv, and code summarization dataset: oode- More details about the datasets are given in the appendix.
Experimental Setup. In the case of the 10 standard benchmark datasets, we compare the proposed model against the following three graph kernels: (1) graphlet kernel (GR))/hervashizze et al. (2009).
(2) shortest path kernel ( Borgwardt & Kriegel (2005). and (3) Weisfeiler-Lehman subtree kernel
WherSShervssiidee et al. 2011), and against the following six neural network models: (1) DGCNN
Zhang et al. (201 8a), (2) DifiPool Ying et al. 2018), (3) ECC [Simonovsky & Komodakis (017))
(4) GIN Xu et al. 2019), (5) GraphSAGE] Hamilton et al. (2017). and (6) RWNN Nikolentzos & Vazirgiannis (020)). We also compare the proposed model against GRWNN-
variant of the model whose "hidden graphs" are randomly initialized and kept fixed during training. To evaluate the proposed model, we employ the experimental protocol proposed in Emrica et al.) (2020). There- fore, we perform 10-fold cross-vall validation obtain estimate of the generalization performance of each method, while within each fold model is selected based on a 90% split of the training set. We exactly the same splits as in Emrica al. (2020) and in Nikolentzos. & Vazirgiannis (2020), hence, for the different datasets, we use the results reported in these two papers.
For all datasets, we set the batch size 64 and the number epochs 300. We use the Adam opti- mizer with initial learning rate 0.001 and applied an adaptive learning rate decay based on validation results. We use 1-layer perceptron transform the vertex attributes. We apply layer normalization et al. (2016) on the generated graph representations (i. e., vector consisting of kernel values). The hyper-parameters we tune for each dataset are: (1) the number of "hidden graphs" E {32, 64), (2) the number of vertices of the "hidden graphs" E (5, 10), (3) the diddenddimension size of the vertex features E {32, 64) for the mooechemo-ifformaan datasets, and (4) the dropout ratio {0, 0.13.
datasets and E {8, 16) for the social interaction
For both OGB datasets, we used the available predefined splits. We compare the proposed model against the following neural network models: GCN Kipf & Welling (2017). GIN Xu et al.) (019)) GCN-FLAG Kong et al. (2020), GIN-FLAG Kong et al. (2020), PNA Corso et al. (2020), GSN Bouritsas et al. (2020), HIMP Fey et al. (2020), and DGN Beaini al. (020). For all models,
use the results that are reported in the respective papers. For ogbg-cooded codeZ, we did not add the
inverse edges to the graphs. All reported results averaged over 10 runs.
7

---

Under review as a conference paper at ICLR 2022
Table 1: Classification accuracy (#t standard deviation) of the proposed model and the baselines on the 5 of Resources, either time (> 72 hours for single training) or GPU memory. Best performance per dataset in bold, among the neural network architectures underlined.
and on the 5 social interaction benchmark datasets. OOR means Out
MUTAG
D&D
NCII
PROTEINS
ENZYMES
SP
80.2 6.5)
78.1 4.1)
72.7 1.4)
75 3.8)
38 8.0)
GR
6.4)
75.4 (.:))
618(2 1.7)
71.
25.1
WL
84.6
8488 2.5)
738 4.4)
50.3
DGCNN
84.0 6.7)
(1.44)
76.4 1.7)
(2.9
DifiPool
(4: 7.1)
75.0 3.5)
76.9 1.9)
71.7 3.5)
59.5 5.6)
ECC
(2:4
(2:6
76.2 1.4)
72.3 3.4)
29.5 8.2)
GIN
(.:
71. 2.9)
80.0 1.4)
73.3 4.0)
59.6 4.5)
GraphSAGE
83.6 9.6)
(2
76.0 1.8)
73.0 4.5)
58.2 6.0)
1-step RWNN
89.2 4.3)
72.6 4.7)
71 1.8
3.3)
$6.7 (d)
2 step RWNN
88.1 CLL 4.8)
76.9 (1. 4.6)
73.0 2.0)
74.1 (1: 2.8)
$7.4
GRWNN fixed
81.9 6.4)
(1. 3.5)
66.9 2.4)
74.6
4.0)
56.8 (1L 3.7)
GRWNN
83.4 (# 5.6)
75.6 4.6)
67.7 2.2)
74.9 3.5)
62.7 (# 5.2)
IMDB
REDDIT BINARY
REDDIT
COLLAB
BINARY
MULTI
MULTI-5K
SP
57.7 4.1)
(9.8 3.7)
(9.0 1.0)
SLT
79.9 2.7)
GR
63.3 (:: 2.7)
39.6 3.0)
76.6 3.3)
38.1 2.3)
711 1.4)
WL
72.8 (1: 4.5)
(1.2
74.9 1.8)
49.6 2.0)
78:0 2.0)
DOCNN
69.2 3.0)
(5
87.8 (#: 2.5)
(9.2 1.2)
712 1.9)
DiAPooal
68.4 3.3)
45.6 3.4)
89.1 ( 1.6)
53.8 1.4)
68.9 (2: 2.0)
BCC
67.7 (1 2.8)
43.5 3.1)
OOR
OOR
OOR
GIN
71.2
(
89.9 1.9)
$6.1 1.7)
(5.6 2.3)
GraphSAGE:
68.8 (1: 4.5)
47.6
84.3 1.9)
50.0 1.3)
(3.9 1.7)
1-step RWNN
70.8 (+: 4.8)
47.8 3.8)
90.4 1,9)
51.7 1.5)
71.7 2.1)
2-step RWNN
70.6 (+:: 4.4)
48.8 (# 2.9)
90.3 (+: 1.8)
$1.7 1.4)
7133 2.1)
GRWNN-fixed
72.1 (2 4.1)
48.1
(#6 3.6)
82.2 2.4)
$3.1 1.80
713 1.9)
GRWNN
72.8 CE: 4.2)
49.0 2.9)
90:0 1.8)
54.4 1.7)
72.1 1.9)
For both OGB datasets, we set the batch size to 128. For the ogb-molhiv dataset, we set the number of epochs to 300, the number of "hidden graphs" to 200, the number of vertices of the "hidden graphs" to 5, the hidden-dimension size of the vertex features 128 and the dropout ratio to 0.1. Furthermore, we employ the probabilistic variant of the geometric random walk kernel and use uniform distributions for the initial and stopping probabilities over the vertices the two compared graphs. For the ogb coode2 dataset, we set the number of epochs to 100, the number of "hidden graphs" to 200, the number of vertices of the "hidden graphs" to 5, the diiden--immnsoon size of the vertex features to 128 and the dropout ratio to 0.2. For both datasets, we apply layer normalization Ba et al. (2016) on the generated graph representations.
Implementation Details. To set the value of parameter X, assume transductive setting, where we are given a collection of graphs beforehand. Therefore, we can find the vertex of highest degree across all graphs and set the value of À accordingly. In the inductive learning setting, since do not know a priori target graphs that the model may receive in the future, X should be small enough so that À 1/pmnaz for any pair of unseen graph and "hidden graph". This is limitation of the proposed model since in case the model receives at test time a graph whose largest eigenvalue is higher than expected, we need set À to a smaller value and retrain the model.
To compute the fixed point of Equation equation S or equation 8 we followed the naive approach where we simply performed multiple times the forward iteration. In practice, there are more efficient fixed point iteration methods, such as Anderson Acceleration Walker & Ni (201T). that converge faster than the naive forward iteration at the cost of some additional memory complexity. However, as shown next, we found that in our setting, the naive forward iteration converges in small number of steps, while the additional cost introduced by more efficient methods associated with the gener- ation and manipulation of new tensors made them overall slower than the naive forward iteration even though they required fewer iterations to converge.
The model was implemented with Py Torch Paszke et al. (2019). and all experiments were run single machine equipped with an NVidia Titan Xp GPU card.
Table iillsttrate average prediction accuracies and standard deviations for the 10 standard graph classification datasets. We observe that the proposed GRWNN model is the best pert-performing
Results.
method on 2 out of the 10 datasets, while it provides the second best and third best accuracy on
8

---

Under review as a conference paper at ICLR 2022
Forward Pass
Backwaard Pass
Method
Datasel
oghg-mo hii
ogbg-oode2
GCN
7600 + 0.97
15.07 0.18
GIN
75.58 + 1.40
14:05 + 0.23
10P
GCN+
76.83 4: 1.02
FLAG
2011
10)
50
76.54 4: 1.14
Accuracy
Accuracy
FLAG
1,00
GSN
77 1.00
HIMP
78.30 4: 0.82
Aconncy
0.75
0.6
PNA
79.05 +: 1.32
15.70 + 0.32
79.70 0.97
0.50
GRWNN
78.38 4: 0.99
15:03 + 0.31
0.58
(a) Performance of the proposed model and the haselines on the OGB datasets. Reported values correspond to ROC- AUC scores for ogbg-moliie and
Epoch
Epoch A-1/40
2-175
1-1/10
A-1/20
A-3/30
A-2 150
(b) Numher of fixed point iterations during the forward and back- ward pass (top), and training and validation accuracy (bottom) on the ENZYMES datasct for different values of A.
Fl-scores for ogbg- code2.
Performance on the OGB datasets and impact of the value of parameter À on running time and performance of the model.
Figure 1:
and 1 out of the remaining 8 datasets, respectively. The most successful method is the WL kernel which performs best 4 of the 10 datasets, while it outperforms the other approaches with quite wide margins in most cases. Among the neural network models, the proposed GRWNN model outperforms the baseline models on 4 out of the 10 datasets. On the remaining datasets, GIN is the best-performing model on half of them, and RWNN on the other half. On the ENZYMES and IMDB-BING -IDBRY datasets, our model offers respective absolute improvements of 3. 3.1%, and 1.6% in accuracy over GIN. Overall, the model exhibits highly competitive performance on the graph classification datasets, while the achieved accuracies follow different patterns from all the baseline methods. Furthermore, the proposed model outperforms GRWNN-fixed on all datasets, demonstrating that the set of trainable "hidden graphs" an indispensable component of the model.
The Table shown in Figure Ia illustrates the performance on the two OGB datasets. Note that the proposed model does not utilize the edge features that are provided for the different datasets. Still, we see that it managed to outperform several of the baselines on the ogbg mo lniv dataset, where it achieved the fourth best ROC-AUC. On the ogbg-code2 dataset, GRWNN outperformed GIN, while it achieved Fi-score similar that of GCN. However, all these three models achieved a much smaller F1-score than the one achieved by PNA which is the best-performing model.
As already diseussed, the running time of the model depends on the number of fixed point iterations that need to be performed until convergence. Figure Tb (top) illustrates the average number of iterations (across all batches) for the forward and backward pass for different values of X and for each epoch. The model was trained on a single split of the ENZYMES dataset. The maximum eigenvalue of all graphs of the dataset is equal to 5.47, while the highest degree is equal 9. The number of nodes of the "hidden graphs" was set to 5. If the elements of the adjacency matrices of the "hidden graphs" take values no greater than one, then no vertex of Gx can have a degree greater than 9+ = 36. Thus, setting À < 1/36 guarantees convergence. In practice, as shown in the Figure, we found that even À takes larger values, we only need small number of iterations. For À = 1/5, that the fixed point equation fails to converge since the average number of iterations is close to 100 (which is the upper limit we have set). For À = 1/10 and for smaller values of X, the system converges in small number of iterations. In terms of performance, as shown in Figure Tb (bottom), the model achieves the highest levels of validation accuracy for À = 1/20 and > = 1/30, while for À 1/5, the model yields much worse performance compared to the other values of X. Similar behavior was observed on the other datasets.
6 CONCLUSION
In this paper, we introduced the GRWNN model, a new architecture which generates graph repre- sentations by comparing the input graphs against "hidden graphs" using the geometric random walk kernel. To compute the kernel, the proposed model uses a fixed point iteration algorithm, and to update the "hidden graphs" during backpropagation, the model capitalizes on implicit differenta- tion. The model was evaluated on several graph classification datasets where it achieved competitive performance.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Brandon Amos, Ivan Dario Jimenez Rodriguez, Jacob Sacks, Byron Boots, and J Zico Kolter. Dif- ferentiable MPC for End-to-end Planning and Control. Advances in Neural Information Pro- cessing Systems, volume 31, pp. 8299-8310, 10, 2018.
James Atwood and Don Towsley. DiffusionnConvolutionn Neural Networks. In Advances in Neural Information Processing Systems, volume 29, pp. 1993-2001, 2016.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv: 1607.0660, 2016.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep Equilibrium Models. In Advances in Neural Information Processing Systems, volume 32, pp. 690-701, 2019.
Dominique Beaini, Saro Passaro, Vincent Létournau, William L. Hamilton, Gabriele Corso, and Pietro Liò. Directional Graph Networks. arXiv preprint arXiv:2010.02863, 2020.
Dennis S Bernstein. Matrix mathematics; theory, facts, and formulas. Princeton University Press, 2009.
K. Borgwardt, C. Ong, S. Schönauer, Vishwanathan, A. Smola, and H. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(Suppl. 1):147-i56, 2005.
K. M. Borgwardt and H. Kriegel. Shortest-path kernels on graphs. In Proceedings of the 5th Inter- national Conference on Data Mining, pp. 74-81, 2005.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252 2020.
Andries E Brouwer and Willem Haemers. Spectra of graphs. Springer Science & Business Media, 2011.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral Networks and Locally connected networks on Graphs. In 2nd International Conference on Learning Representations, 2014.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural Ordinary Dif- ferential Equations. In Advances in Neural Information Processing Systems, volume 31, pp- 6572-6583, 2018.
Gabriele Corso. Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. Advances in Neural Information Processing Systems, volume 33, 2020.
Filipe de Avila Belbute-Peres Kevin Smith, Kelsey Allen, Josh Tenenbaum, and J Zico Kolter. End-to-End Differentiable Physics for Learning and Control. Advances in neural information processing systems, 31:7178-7189, 2018
A. Debnath, R. Lopez de Compadre, G. Debnath, A. Shusterman, and C. Hansch. Structure-Activity Relationship of Mutagenic Aromatic and Heteroaromatic Nitro Compounds. Correlation with Molecular Orbital Energies and Hydrophobicity. Journal of Medicinal Chemistry, 34(2):786- 797, 1991.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems, volume 29, pp. 3837-3845, 2016.
Nima Dehmamy, Alsert-Laszlo Barabasi, and Rose Yu. Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology. In Advances in Neural Information Processing Systems, volume 32, 2019.
Dobson and A. Doig. Distinguishing Enzyme Structures from Non-enzymes Without Alignments. Journal of Molecular Biology, 330(4):771-783, 2003.
10

---

Under review as a conference paper at ICLR 2022
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzz Guzik, and Ryan P Adams. Convolutional Networks on Graphs for Learning Molecular Fingerprints. In Advances in Neural Information Processing Systems, volume 28, 2015.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A Fair Comparison of Graph Neural Networks for Graph Classification. In Proceedings of the International Conference on Learning Representations, 2020.
Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical Inter- Mese-Message Passing for Learning on Molecular Graphs. arXiv preprint 1rXiv:2006.12179, 2020.
Claudio Gallicchio and Alessio Micheli. Fast and Deep Graph Neural Networks. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 3898-3905, 2020.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On Graph Kernels: Hardness Results and Efficient Alternativss. In Learning Theory and Kernel Machines, pp. 129-143. 2003.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural Message Passing for Quantum Chemistry. In Proceedings of the 34th International Conference on Machine Learning, pp.
2017.
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent EI Ghaoui. Implicit Graph Neural Networks. In Advances in Neural Information Processing Systems, volume 33, pp. 11984- 11995, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
David Haussler. Convolution kernlls on discrete structures. Technical report, Technical report, Department of Computer Science, University of California at Santa Cruz, 1999.
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. arXiv preprint arXiv:2005.00687 2020.
Janis Kalofolias, Pascal Welke, and Jilles Vreeken. SUSAN: The Structural Similarity Random Walk Kernel. I Proceedings of the 2021 SIAM International Conference Data Mining, 2021.
U Kang, Hanghang Tong, and Jimeng Sun. Fast Random Walk Graph Kernel. In Proceedings the 2012 SIAM International Conference on Data Mining, pp. 828 838, 2012.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized Kernels Between Labeled Graphs. In Proceedings of the 20th International Conference on Machine Learning, pp. 321- 328, 2003.
Steven Kearnes, Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of Computer-Aided Molecular Design, 30(8): 595-608, 2016.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. htttp://grapkkee s. tu do www.rddd.... de
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In In 5th International Conference on Learning Representations, 2017.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Flag: Adversarial Data Augmentation for Graph Neural Networks. arXiv preprint arXiv:2010.09891, 2020.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1): 2020.
Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Deriving Neural Architectures from Sequence and Graph Kernels. In Proceedings of the 34th International Conference on Machine Learning, pp. 2024-2033 2017.
11

---

Under review as a conference paper at ICLR 2022
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated Graph Sequence Neural Networks. In 3rd International Conference on Learning Representations, 2015.
Pierre Mahé, Nobuhisa Ueda, Tatsuya Akutsu, Jean-Luc Perret, and Lean-Philipppe Vert. Extensions of Marginalized Graph Kernels, In Proceedings of the 21 International Conference on Machine Learning, 2004.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems, 2019a.
Haggai Maron, Heli Ben- Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In 7th International Conference on Learning Representations, 2019b.
Alessio Micheli. Neural Network for Graphs: A Contextual Constructive Approachs. IEEE Trans- actions on Neural Networks, 20(3):498-55 2009.
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 Net- works. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 4602 4609, 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems, volume 33, pp. 21824-21840, 2020.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning Convolutional Neural Net- works for Graphs. In Proceedings of the 33rd International Conference on Machine Learning,
pp. 2014-2023, 2016.
Giannis Nikolentzos and Michalis Vazirgiannis. Random Walk Graph Neural Networks. Advances in Neural Information Processing Systems, 33:16211-16222, 2020.
Jorge Nocedal and Stephen Wright. Numerical Optimization. Springer Science & Business Media, 2006.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Sys- tems, volume 32, pp. 8026 (006-8037,41 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1):61 2009.
N. Shervashidze, P. Schweitzer, F. J. Van Leeuwen, K. Mehlhom, and K. M. Borgwardt. Weisfeiler- Lehman Graph Kernels. The Journal of Machine Learning Research, 12:2539-2561,2011
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M Borgwardt. Efficient graphlet kernels for large graph comparison. In The 12th International Conference on Artificial Intelligence and Statistics, pp. 498, 2009.
Martin Simonovsky and Nikos Komodakis. Dynamic Fdge-Conditioned Filters in Convolutional Neural Networks on Graphs. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pp. 3693-3702, 2017.
Alessandro Sperduti and Antonina Starita. Supervised Neural Networks for the Classification of Structures. IEEE Transactions on Neural Networks, 8(3):714-733 1997.
Mahito Sugiyama and Karsten Borgwardt. Halting in Random Walk Kernels. Advances in Neural Information Processing Systems, 28: 1639-16477, 2015.
12

---

Under review as a conference paper at ICLR 2022
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with 1d convolu- tions on random walks. arXiv preprint arXiv:2102.08786, 2021.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph Kernels. Journal of Machine Learning Research, 11:1201-1244 2010.
N. Wale, Watson, and G. Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
Homer F Walker and Peng Ni. Anderson acceleration for fixed-point iterations. SIAM Journal on Numerical Analysis, 49(4):1715-1735, 2011.
Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. Session-Based Rec- ommendation with Graph Neural Networks. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 346-33 353, 2019.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical Science, 9()): 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In 7th International Conference Learning Representations, 2019.
P. Yanardag and S. Vishwanathan. Deep Graph Kernls. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical Graph Representation Learning with Differentiable Pooling. In Advances in Neural Information Processing Systems, pp. 4801-481 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An End-to-End Deep Learning Architecture for Graph Classification. In Proceedings of the 32nd AAAI Conference Artificial
Intelligence, pp. 4438-4445, 2018a.
Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. RetGK: based on Return Probabilities of Random Walks, Advances in Neural Information Processing Systems, 11:3964-39744 2018b.
Graph Kernels
A APPENDIX
The appendix is organized as follows. In section B algebra. In section C. we prove the Proposition 1. In section D we give more details about the direct differentiation through the fixed point, while section provides a detailed description of the graph classification datasets. Section F gives details about the parameter A, while section G about the running time of the model. Finally, section
define some basic concepts from linear
we perform a sensitivity analysis.
B LINEAR ALGEBRA CONCEPTS
In this Section, provide definitions for concepts of linear algebra, namely the vectorization oper- ator, the inverse vectorization operator and the Kronecker product, which we use heavily in the main paper.
Definition 1. Given real matrix A m the vectorization operator vec g - pm is defined as:
A
A
vec(A) (A)
A mn_
where Aug is the tth column of A.
13

---

Under review as a conference paper at ICLR 2022
Definition 2. Given real vector b R" the inverse vectorization operator vec Raxm is defined as:
bi bu+1
Dn(m (1(m-1)++ 1)+1
b
bat2
b mm 1)+2
vec vec-l(b
(b)
:
ba
b
b
Definition 3. Given real matrices A Re and B Rapxma defined as:
Roxq, the Kronecker product A & B
A1 B
A12 B
Aim B
A21 B
A22 B
A2m
A B B
A B
A B
A B
C PROOF OF PROPOSITION 1
For convenience, we restate the Proposition below.
Proposition Let A E Raxx and A2 E IR be two real matrices. Let also s, E IRum be two real vectors. Then, we have that:
(ss" ② (A1 @ A2) = vec (A, vec (s Os)))AT)
Proof. Let D3 denote diagonal matrix with the vector its main diagonal. Then, have:
(ss) (A1 A2))y (Da (Ai A2) Da)y
The Hadamard product of two vectors s and y is the same as matrix multiplication of vector y by the corresponding diagonal matrix D, of vector s, e., D y = s y. Thus, it follows that:
(D& (A1 & A2) D.yy D2 (A1 A2) (s
Note that the Kronecker product and vec operator are linked by the well nell-known property Bernstein 2009 (Proposiiinn 7.1.9):
vec vec(A (C @ A)vec((B)
Therefore, we have that:
(Dx (A1 @
D& vec vec ( (()O))A]] = = vec(A2 vec (sO
which concludes the proof.
D IMPLICIT DIFFERENTIATION
Clearly, iteratively computing Equation (3) or Equation (8) (main paper) to find the fixed point corre- sponds to differentiable module. However, to train the model, we need to backpropagate the error through the fixed point solver the backward pass. That would require storing all the intermediate terms, which could be prohibitive in practice. Fortunately, thanks to recent advances in implicit lay- ers and equilibrium models Bai et al. (2019), this can be performed a simple and efficient manner which requires constant memory, and assumes knowledge of the fixed point solver. Specifically, based on ideas from Bai et al. (2019), we derive the form implicit backpropagation specific to the employed fixed point iteration layer.
Let So be the system of Equation (3) Equation (8) (main paper), and x² E Rune be solution to that linear system. Let also ge (z"; A. X) = = A, x z- Since z" is a fixed point, have that gz A, X) - 0 and z" is thus the root of ge. Let R denote the ground-truth target of the input sample, loss function that computes:
Theorem 2.
+ TR. be any differentiable function and let
R. be
{ 2(((1 (T())T2))v)) 2*).)) 1 FindRoot(go; [ A, A,X)),1)
(11)
14

---

Under review as a conference paper at ICLR 2022
Then, the gradient of the loss w.r.t. (-) (e. g., 6, A or X) is:
de de 0(-) dz (J ) 0fo(z" ;A,
0e 0h
0 :A
(J
(12)
a(-)
Oh dz no 2
0(-)
where Jgol go x. is the inverse Jacobian of go evaluated at z"
The above Theorem gives a form for the necessary Jacobian without needing to backpropagate through the method used to obtain the fixed point. We can thus treat the fixed point algorithm black box, and we do not need to store intermediate terms associated with the fixed point algorithm into memory. We only need to apply some algorithm that will produce a solution to the system (i. e.,
it will compute the fixed point).
Following Bai et al. (2019), we differentiate the two sides of the fixed point equation z² fo(z;; A, X) wih respect to (-):
dz
d if, + 0folz": A x) dz
d(.)
d(.)
0(.)
Or
d(-)
0f A, X
dz*
0fe(z* AA
Oz
d())
8(.)
Since sz(2)) = A
A, X) 2², we have:
Ofo(z":A, A,
Jaol
Oz
which implies the following:
ae Oe dz
Oz 90 x (J=1 0so(2"; A)
Ol
a(-)
Oz d(.)
O(-)
Unfortunately, computing the exact inverse Jacobian J-1 has a cubic cost. As shown in Bai et al. 2019), instead compute the De (J=ll, l.)) term of the gradient (which contains the Jaco- bran) by solving the following linear system:
di
dl
x = In (J
Oz
Ou
0fo(z"; A, x)
OL
=
Oz
Oz*
0sa(zt;A
Oe
Oz
Oz
T
-
x
+
Oz"
Oz
which in fact is also fixed point equation and can be solved via some iterative procedure. Note that the first term of the above Equation is a vector-Jacobian product which can be efficiently computed via autograd packages g.. PyTorch Paszke al. (2017) for any x, without explicitly writing out the Jacobian matrix. Finally, we can compute
or as follows:
8(-)
ō 0ff(zz;A, 0(-)
a(-)
where again this product itself vector-Jacobian product, computable via normal automatic dif- ferentiation packages.
E DATASETS
We evaluated the proposed model on 10 publicly available graph classification datasets including bio/chemo-informatiin datasets: MUTAG, D&D, NCT1, PROTEINS and ENZYMES, well
15

---

Under review as a conference paper at ICLR 2022
Table 2: Summary of the 10 datasets that were used in our experiments.
Dataset
MUTAG
D&D
NCI1
PROTEINS
ENZYMES
IMDB BINARY
IMDB MULTI
REDDIT BINARY
REDDIT MULTI-SK
COLLAB
Max it vertices
28
5,748
111
620
126
136
89
3,782
3,648
492
Min vertices
10
30
2
12
7
6
22
32
Average vertices
17.93
284.32
29.87
39.05
32.63
19.77
13.00
429.61
508.50
74.49
Max i edges
33
14,267
119
1,049
149
1,249
1,467
4,071
4,783
40,119
Min edges
10
63
5
1
26
12
21
60
Average odges
19.79
715.66
32.30
72.81
62.14
96.53
65.93
497.75
594.87
2,457.34
lahels
82
37
3
attributes
18
graphs
188
1,178 2
4.110
1,113
600
1,000
1,500
2,000
4,999
5,000
classes
2
2
3
2
5
3
social interaction datasets: IMDB-BINARY. IMDB-MULTI, REDDIT-BINARY, MEDDIT-MULTI- 5K and COLLAB Kersting et al. (0016). A summary of the 10 datasets is given in Table 2 MU- TAG consists of 188 mutagenic aromatic and heteroaromatic nitro compounds. The task is to pre- dict whether not each chemical compound has mutagenic effect the Gram-negative bacterium Salmonella ryphimurium Debnntt et al. (99T). ENZYMESS contains 600 protein tertiary structures represented graphs obtained from the BRENDA enzyme database. Each enzyme is member of one of the Enzyme Commission top level enzyme classes (EC classes) and the task is to correctly assign the enzymes to their classes Borgwardt et al. (2005). NCII contains more than four thousand chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines Wale al. (2008). PROTEINS contains proteins represented as graphs where vertices are secondary structure elements and there is an edge between two vertices if they are neighbors in the amino-acid sequence or in 3D space. The task to classify proteins into enzymes and non-enzymes Borgwardt et al.] (2005). D&D contains over a thousand protein structures. Each protein is graph whose nodes correspond to amino acids and a pair of amino acids are connected by an edge if they are less than 6 Angstroms apart. The task is predict if protein is enzyme not Dobson & Doig (2003). IMDB-BINARY and IMDB-MULTI were created from IMDb, an online database of information related to movies and television programs. The graphs contained in the two datasets cor- respond to movie collaborations. The vertices of each graph represent actors/actresser and two ver- tices are connected by an edge if the corresponding actors/actresses appear in the same movie. Each graph is the ego-network of an actor/actress, and the task is to predict which genre an ego-network belongs to Yanardag & Vishwanathan (2015). DEDDIT-BINARY and REDDIT-MULTI-SK contain graphs that model the social interactions between users of Reddit. Each graph represents an online discussion thread. Specifically, each vertex corresponds to user, and two users are connected by an edge if one of them responded to at least one of the other's ss comments. The task is to classify graphs into either communities or subreddits Yanardag & Vishwanathan (2015). COLLAB is a scientific collaboration dataset that consists of the ego-networks of several researchers from three subfields of Physics (High Energy Physics, Condensed Matter Physics and Astro Physics). The task is to determine the subfield of Physics to which the ego-network of each researcher belongs Yanardag & Vishwanathan (2015).
We also evaluated the proposed model on two datasets from the Open Graph Benchmark (OGB) Hu et al. 22000), a collection of large-scale and diverse benchmark datasets for machine learning on graphs. A summary of the two datasets is given in Table 33 The ogbg-molhiv dataset is a molecular property prediction dataset that is adopted from the MoleculeNet [w et al. (2018). The dataset consists of 41, 127 molecules and corresponds to a binary classification dataset where the task is to predict whether a molecule inhibits HIV virus replication or not. The molecules in the training, validation and test sets are divided using a scaffold splitting procedure that splits the molecules based on their two-dimensional structural frameworks. The scaffold splitting attempts to separate structurally different molecules into different subsets. The egbg-cood22 dataset contains large number of Abstract Syntax Trees (ASTs) that are extracted from approximately 450, 000 Python method definitions. For each method, the AST edges, the AST nodes, and the tokenized method name are retrieved. Given the body of a method represented by the AST and its node features, the task (which is known as code summarization) is to predict the sub-tokens forming the name of the method. The ASTs for the training set obtained from GitHub projects that do not appear in the validation and test sets. We refer the reader to Hu et al. (2020) for more details about the OGB datasets.
16

---

Under review as a conference paper at ICLR 2022
Table 3: Statistics of the 2 OGB datasets that used in our experiments.
Dataset
ogbg-molhiv
ogbg-code2
Average # vertices
25.5
125.2
Average # edges
27.5
124.2
Node features
/
Edge features
/
Directed
# graphs
41,127
452,741
# tasks
1
Split scheme
Scaffold
Project
Split ratio
80/10/10
90/5/5
Task type
Binary class. ROC-AUC
Sub-token prediction
Metric
F1-score
Table 4: Values of that we used in our experiments.
IMDB BINARY
IMDB MULTI
REDDIT BINARY
REDDIT MULTI-SK COLLAB
MUTAG
D&D
NCTI
PROTEINS
ENZYMES
1/5
1/20
1/30
1/20
1/300
1/300
1/500
1/100
1/2000
F PARAMETER X
Given an input graph G and "hidden graph" G,, since the "hidden graph" is trainable, the maximum vertex degree of the product graph Gx is not known beforehand. However, in case the weights of the edges of the "hidden graph" are bounded, we can compute an upper bound to that. the maximum vertex degree of G, denote the number of vertices of the "hidden graph" G₁, and b the maximum edge weight the "hidden graph". Then, we have that Ax S Acb, and therefore, guarantee convergence,
A denote
need to set X S 1/acb. In practice, empirically found that even if takes higher values, the geometric series converges within small number of iterations. Table shows the value of À that used for each dataset.
G RUNTIME ANALYSIS
The proposed model is indeed computationally more expensive than the RWNN model due to the fixed point iteration which is parallelizable. However, as already discussed, empirically observed that the forward iteration converges in small number of steps, thus incurring a relatively small overhead in the model's running time. We have computed the average running time per epoch of the proposed model, and 3 of the baselines (2-RWNN, 3-RWNN and GIN) on the 10 graph classification datasets. We use the same values for the common hyperparameters (e. g., number and size of hidden graphs for GRWNN and RWNN, and hidden dimension size, batch size, etc for all models). The results are shown Table (in seconds). As we can see, proposed model not much more expensive than the baselines. In fact, in most cases, its average running time per epoch times higher than that of the basclines, which is by no means prohibitive for real-world scenarios.
Table 5: Average running time per epoch (in seconds) of the proposed model and 3 baselines on the 10 graph classification datasets.
IMDB BINARY
IMDB MULTI
REDDIT BINARY
REDDIT MULTI-SK
MUTAG
D&D
NCII
PROTEINS
ENZYMES
COLLAB
GIN
0.03
0.34
0.50
0.14
0.07
0.13
0.19
0.81
2.43
0.98
2-RWNN
0,03
0.19
0.57
0.16
0.08
0.14
0.20
0.43
1.13
0.89
3-RWNN
0.04
0.23
0.76
0.21
0.11
0.18
0.28
0.55
1.42
1.04
GRWNN
0.07
0.77
0.94
0.32
0.17
0.34
0.34
2.93
6.19
2.69
17

---

Under review as a conference paper at ICLR 2022
Figure 2: Performance on the ENZYMES dataset function of the number of "hidden graphs" (left) and the number of vertices of the "hidden graphs" (right).
H SENSITIVITY ANALYSIS
The proposed GRWNN model involves two main parameters: (1) the number of "hidden graphs", and (2) the number of vertices of "hidden graphs". We next investigate how these two parameters influence the performance of the GRWNN model. Specifically, in Figure 2 we examine how the different values of these parameters affect the performance of GRWNN on the ENZYMES dataset. We observe that the accuracy on test set increases as number "hidden graphs" increases. The number of "hidden graphs" seems to have significant impact the performance of the model. When the number graphs set equal to 5, the model achieves an accuracy smaller than 50%, while when the number of graphs is set equal 100, it yields accuracy greater than 65%. On the other hand, the number of vertices of the "hidden graphs" " does not affect that much the performance of the model.
18


Reviews:
[{"review_id": "idt8YeINctm", "reviewer": "Reviewer_rSPG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Strengths**\n1. Simple architecture that give good empirical results \n2. Well-written and easy to follow\n\n**Weaknesses**\n1. Incremental work, building on known work \n2. No clear performance gain over fixed-length RW models, see Table 1 \n3. Comparision to fixed-length RW models only done on small-scale datasets, compare Table 1 and Figure 1(a)\n\n\n**Questions**\n1. You state that \"Such local patterns may fail to capture the overall large-scale shape of the graphs, while several interesting\nproperties of graphs depend on the graph’s global structure.\"\n\nCan you quantify exactly for which kind of graph structures this is the case? \nE.g., by quantifiying the graph structures captured by the infinite-length RW models but not by finite-length RW models.\n\n2. Why did you not evaluate the fixed-length RW models on the OBG datasets?\n\n3. Does your architecture offer any insights on how to design deep GNNs?\n\n**Suggestions**\nTo show a clear performance gain, especially over the fixed-length RW models, one should compare the model on more large-scale datasets, e.g., from OGB and graphlearning.io. The small-scale datasets from Table 1 exhibit large standard deviations which make comparisons in terms of accuracy often not meaningful. \n\n**Minor comments**\n1. You seem to use \\citet{} when citep{} would be more appropriate\n2. First page, second paragraph:  \"graphs, So far, ...\" -> \"graphs. So far, ...\n", "summary_of_the_paper": "The paper deals with learning with graphs, specifically graph-level classification. Given a graph G, the main idea of the paper is to compare the graph G to a set of N graphs using the (infinite-length) random walk kernel (Vishwanathan et al. 2010), resulting in a vector with N components. The resulting vector is fed into an MLP performing the classification tasks. Crucially, the N graphs are learned using end-to-end learning.\n\nFurther, the authors show how to compute the RW kernel efficiently, building on previous work  (Vishwanathan et al. 2010), and how to do differentiate through the architecture efficiently, building on (Bai et al. 2016). The paper can be seen as an extension of the RWNN model (Nikolentzos et al. 2020), which uses a finite-length random kernel. \n\nThe methodology is complemented with an experimental study showing promising performance on standard benchmarks datasets. \n\n\n\n\n", "summary_of_the_review": "The paper is well-written and easy to follow. However, the idea is incremental, building largely on previous work. Moreover, the gain in expressiveness is not quantified, e.g., by showing that the infinite-length RW models can expressive more permutation-invariant functions compared to the fixed-length RW models. Morever, the emperical results are not convincing, i.e., they do not clearly win over  the fixed-length RW models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZEPG9FYGHlG", "reviewer": "Reviewer_Nev5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "strengths: \n\nThe main contribution, which I believe is their solution to allowing an ‘infinite step’ geometric random walk to be efficiently differentiated and thus the hidden graphs trained, is thoroughly detailed in section 4. Also, they thoroughly justify and demonstrate settings for their main hyper-parameter lambda. Assuming correctness of the implementation itself, which I am not very confident in my ability to critique, I believe this is an idea worth exploring regardless of the outcome. \n\nAlthough the results aren’t clearly superior, it seems that none of the competitors listed are in a significant lead, and instead each has strengths and weaknesses in the diverse pool of graph datasets. I would say this method proved itself to be a good choice for some kinds of graph classification problems. \n\n\nweaknesses: \n\nA major problem of this work is numbers reported the experimental study. In table 1, many results are far lower than that in their original papers. For example, GIN achieves 75.1 and 52.3 on IMDB-B and IMDB-M but was reported 71.2 and 48.5 (https://arxiv.org/pdf/1810.00826.pdf). The state-of-the-art performances on these datasets have been greatly improved and far better than the performances achieved by GRWNN. The authors need to address this issue. Otherwise, I would have concern that the reported numbers are misleading the audiences and reviewers.\n\nThe conclusion seems rushed and doesn’t analyze the results very well, such as the fact that allowing longer random walks is, in some cases but not others, an advantage over the 1-step random walks on all datasets. I’m naive to the true implications in this case, but I assume there is knowledge to be gleaned from the results even if they aren’t a large improvement over competitors. ", "summary_of_the_paper": "The paper discusses random walk graph kernels for graph neural network feature generation in other works. They work by generating features for graphs by comparing random walks present in each graph compared to a set of trainable hidden graphs. It is stated in this paper that an advantage of random walk kernels is that they are end to end differentiable, but current implementations have the weakness of only being efficient for walks of very short length. They introduce a way to efficiently extend walks to ‘infinite length’, theoretically making features generated by the kernel more informative. They compare their results with top GNNs and with other graph kernel approaches such as the mentioned random walk kernels on graph classification datasets. Out of 10 datasets they achieve best performance on 2 (1 of the 2 is tied for best), second best on 3, and third best on 1, It should be noted that many placements are well within the margin of error. ", "summary_of_the_review": "Although the authors make great contribution to the technical part, the experimental results have big flaw, which needs to be addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "T397_cOIfv9", "reviewer": "Reviewer_iyPk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros:\n1. The idea of this work is interesting and has sufficient novelty. An efficient computational method is designed to simplify the computation associated with the “graph product”.\n\n2. The experiments are sufficient and representative graph datasets and baselines are considered.\n\n3. The paper is well-written and thus easy to follow. \n\n\nCons:\n1. Although the authors make efforts to reduce the complexity of the proposed method. Compared with message passing neural networks (MPNN), the proposed method involves inevitable dense matrix multiplication — in Eq.(6) and Proposition 1, A_i is a dense learnable matrix. As a result, when there are many large hidden graph A_i’s, the proposed method will be much worse than MPNN.\n\n2. The experimental results in Table 1 and Figure 1 do not show the superiority of the proposed method. Considering the potential high complexity of the method, what is the main advantage of the proposed GRWNN method?\n\n3. Besides RWNN, the factorization-based methods in [a, b] also leverage several learnable hidden graphs to learn graph representations, and they are applicable in unsupervised learning cases. The authors should consider these works and the corresponding learning strategy in the related work and discuss them in-depth.\n\n[a] Xu, Hongteng. \"Gromov-Wasserstein factorization models for graph clustering.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.\n[b] Vincent-Cuaz, Cédric, et al. \"Online Graph Dictionary Learning.\" arXiv preprint arXiv:2102.06555 (2021).\n\nMinors:\n1. Although the authors provide an empirical method to determine “\\lambda”, I wonder if it is possible to learn lambda automatically. \n", "summary_of_the_paper": "In this paper, the authors proposed an interesting geometric random walk neural network for graph representation. The proposed method can be viewed as an improvement of the random walk neural network in [Nikolentzos & Vazirgiannis, 2020], which learns graph representations by modeling the geometric series of the “product” between observed graphs and some hidden and learnable graphs. \nAs a result, the graph representations are learned by finding fixed points of linear systems. ", "summary_of_the_review": "The idea proposed in this paper is interesting indeed, which provides a new way to learn graph representations. However, the superiority of the proposed method to existing work is verified neither on classification accuracy nor runtime. Additionally, some related graph representation strategies are not considered or discussed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0Pw8h97bp2j", "reviewer": "Reviewer_bEUY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This is a well-written and well-executed paper with encouraging and thorough experimental results.\n\nThe only real question in my mind is whether it meets the bar for novelty and significance: It falls under the large number of papers that take an iterative process and use implicit differentiation to efficiently include it in a neural network for training. With this formula in mind, the derivations are relatively straightforward. Moreover, the experimental results are not particularly surprising and don't show very significant improvements over other methods. With that in mind, perhaps this paper is more appropriate for a workshop? Or perhaps there is a way that this work could be extended?\n\nThe authors refer repeatedly to Bai et al. (2019) for the implicit differentiation. Although this might be the correct reference for the recent rediscovery of implicit differentiation in deep learning, I believe that \"Automatic Differentiation and Iterative Processes\" (Gilbert, 1992) should probably be cited as one of the papers that originally introduced the idea.\n\n", "summary_of_the_paper": "This paper shows that the geometric random walk kernel is differentiable using implicit differentiation and can hence be used in a graph neural network to match an input graph to a set of learned graphs. The experimental results show that this method is competitive with a variety of other methods.", "summary_of_the_review": "A well-written and decent paper that struggles to meet the bar for novelty and significance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows how to back-propagate through a kernel between graphs that counts common random walks of infinite length between the graphs. Reviewers tend to agree that the paper is well-written and the technical contributions are sound. However, there are concerns about the significance and novelty of the method relative to related work, alongside mixed experimental results. Overall that puts it as a very borderline paper. In the rebuttals, the authors argued for the significance of the contribution, but reviewers were generally unconvinced.
Decision: Reject