Graph Kernel Neural Networks
Authors: Luca Cosmo
Giorgia Minello
Michael M. Bronstein
Emanuele Rodolà
Luca Rossi
Andrea Torsello
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neural network
graph kernel
deep learning

Abstract: The convolution operator at the core of many modern neural architectures can effectively be seen as performing a dot product between an input matrix and a filter. While this is readily applicable to data such as images, which can be represented as regular grids in the Euclidean space, extending the convolution operator to work on graphs proves more challenging, due to their irregular structure. In this paper, we propose to use graph kernels, i.e., kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type and number of graph kernels and has the added benefit of providing some interpretability in terms of the structural masks that are learned during the training process, similarly to what happens for convolutional masks in traditional convolutional neural networks. We perform an extensive ablation study to investigate the impact of the model hyper-parameters and we show that our model achieves competitive performance on standard graph classification datasets.

Under review as a conference paper at ICLR 2022
GRAPH KERNEL NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The convolution operator at the core of many modern neural architectures can effectively be seen as performing a dot product between input matrix and filter. While this is readily applicable to data such as images, which can be repre- sented as regular grids in the Euclidean space, extending the convolution operator to work on graphs proves more challenging, due to their irregular structure. In this paper we propose use graph kemelss, i.e., kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type and number of graph kernels and has the added benefit of providing some interpretability in terms of the structural masks that are learned during the training process, similarly to what happens for convolutional masks traditional convo- lutional neural networks. We perform extensive ablation study to investigate the impact of the model competitive performance standard graph classification datasets.
and we show that our model achieves
INTRODUCTION
In recent years, graph neural networks (GNNs) have gained increasing traction in the machine learn- ing community. Graphs have long been used as a powerful abstraction for a wide variety of real- world data where structure plays key role, from collaborations (Lima et al. [2014] Kipf & Welling 2017) to biological (Gilmer et al., 2017 Ye et al. 2015) and physical (Shlomi al. (2020) data, to mention a few. Before the advent of GNNs, graph kernels provided a principled way to deal with graph data the traditional machine learning setting (Shervashidze et al.] 201T Bai et al. 2015] Minello et al. (201)). However, with the attention of machine learning researchers steadily shifting away from hand-crafted features toward end-to-end models where both the features and the model learned together, neural networks have quickly overtaken kernels the framework of choice to deal with graph data, leading to multiple popular architectures such as (Kipf & Welling 2017] Gilmer al. 2017: Veličković et al. 2018
The main obstacle that both traditional and deep learning methods have to overcome when dealing with graph data is also the source of interest for using graphs as data representations. The richness of graphs means that there is no obvious way to embed them into a vector space, a necessary step when the learning method expects vector input. One reason is the lack of a canonical ordering of the nodes in a graph, requiring either permutationninvarian operations or an alignment to a reference structure. Moreover, even if the order or correspondence can be established, the dimension of the embedding space may vary, as result of structural modifications, i.e., changes in the number of nodes and edges.
In traditional machine learning, kernel methods, and particularly graph kernels, provide an elegant way to sidestep this issue by replacing explicit vector representations of the data points with posi- tive semi-definite matrix of their inner products. Thus, any algorithm that can be formulated in terms of scalar products between input vectors, can be applied to a set data (such as graphs) on which a kernel is defined.
GNNs apply a form of generalised convolution operation to graphs, which can be seen as a message passing strategy where the node features are propagated over the graph capture node interactions. In this paper we propose a neural architecture that bridges the two worlds of graph kernels and GNNs. The main idea is analogy between the traditional convolution operator, which can be

---

Under review as a conference paper at ICLR 2022
seen performing inner product between an imput matrix and filter, and graph kernels, which compute an inner product of graphs. As such, graph kernels provide the natural tool to generalise the concept of convolution to the graph domain, which we term graph kernel convolution (GKC). Given a graph kernel of choice, in each GKC layer the input graph is compared against a series of structural masks (analogous to the convolutional masks in CNNS), which effectively represent learnable sub-graphs. These in turn can offer better intrepretability, in the form of insights into what structural patterns in the input graphs are related to the corresponding output.
Our main contributions are: 1. Our model is fully structural, unlike existing approaches that re- quire embedding the input graph into larger, relaxed space. While the latter allows one seek more complex and arbitrary decision boundaries, it also has the potential of overfitting the problem and creating more local optima, as evidenced by the need to use dropout strategies to avoid over- fitting in Graph Convolutional Networks (GCNs) (Rong et al. 2019 Cong et al.) 2021 2. Our architecture allows to plug-in any number and type of graph kernel (not just a single differentiable kernel as in Nikolentzos & Vazirgiannis () 3. As an added benefit, our model provides some interpretability in terms of the structural masks that are learned during the training process, simi- larly to convolutional masks in traditional CNNs. 4. Finally, we analyse the expressive power of our model and we show that it is greater than that of standard message- pesssag-passing GNNs and the equivalent Weisfeiler-Lchman (WL.) graph isomorphism test.
The fundamental goal of our model is to reconstruct the structural information needed for classifi- cation and is thus particularly suited for problems where the structure plays pivotal role. These are often graph classification problems, where structure provides the most relevant information for classification, while node/edge features take a secondary role. The situation is usually reversed for node classification problems, where the distribution of features across the immediate neighbours of a node holds most of the information needed to classify the node itself. For these reasons in this paper we focus on graph classification problems. However we stress that our model can be indeed extended to tackle node-level tasks.
The remainder of this paper is organised as follows. In Section 2 we review the related work. In Section [3 we present our model, where graph kernels are used to redefine convolution on graph data. In Section 4 we investigate the hyper-parameters of our architecture through an extensive ablation study, provide some insight on the interpretability of the structural masks, and evaluate our architecture on standard graph classification benchmarks. Finally, Section 3 concludes the paper.
2 RELATED WORK
The majority of graph kernels belongs to one of two main categories: 1) information propagation kernels. Stt-ofrss kernels compute the similarity between pair of input graphs by first decomposing them into simpler sub-structures and then counting the number of isomorphic sub-structures between the two input graphs. Depending on the type of sub-structure considered, one can build multitude of different kernels, e.g., sub-trees (Ramon & Gärtner 2003), shortest paths (Borgwardt& & Kriegel| (005), and graphlets (Shervashidze et al. 2009). Information propagation kernels, on the other hand, include methods where pairs of input graphs are compared based on how information diffuses on them. Examples include random walk kernels (Kashimal al. 2003 Bai & Hancock 2013), quantum walk kernels (Bai et al. 2215 Rossi et al. (0055). and kernels based on iterative label refinements (Shervashidze et al.] 201 While some kernels work only on undirected and unattributed graphs, other kernels are designed to handle attributes as well, either discrete- or continuous
and 2)
(Shervashidze et al., 2011 Da San Martino et al., 2017). For a detailed review and historical perspective on graph kernels, we refer the reader to the recent survey of Kriege et al. (2020).
In recent years, with the advent of deep learning and the renewed interest in neural architectures, the focus of graph-based machine learning researchers has quickly moved to extending deep learning approaches to deal with graph data. Fundamentally, the principle underpinning most GNNs that of exploiting the structure of the graph to propagate the node feature information iteratively. One of the first papers to propose the idea of GNNs is that of Scarselli et al. (2008), ) where an information diffusion mechanism is used to learn the nodes' latent representations by exchanging neighbour- hood information. Depending on the form this diffusion takes, Bronstein et al. (202l) distinguish Atwood & Towsley 2016 Levie al.] 2018), atten-
between convolutional (Kipf & Welling 2017
2

---

Under review as a conference paper at ICLR 2022
tional Veličković et al. (2018), or message passing (Gilmer al. 2017) types of GNNs, with the latter being the most general and formally equivalent to the Weisfeiler- Weisteiler-Lehman graph isomorphism test under some technical conditions (Xu et al. 2018 Morris al. 2019). More recently. [Eliasof et al. (202T) proposed a reinterpretation of graph convolution in terms of partial differential equa- tions on graphs, noting that different problems can benefit from different networks dynamics, hence suggesting the need to look beyond diffusion. For a comprehensive survey of GNNs we refer the reader Wu et al. (2020).
In this work, we argue that a natural extension of the convolution operation to the graph domain, and thus an ideal candidate to build graph CNNs, already exists in the form of graph kernels. number of works in the literature have investigated potential synergies between GNNs and kernels. [Lii et al. 2017), introduce a class of deep recurrent neural architectures show that this lies in the reproducing kernel Hilbert space (RKHS) of graph kernels. Nikolentzos et al. (2018) compute continuous em- beddings of graphs using kernels and plug them into neural network. Xu et al. (2018); Morris et al. the WL graph kernel (Shervashidze al. 2011] and propose a new generalised architecture with increased expressive power. Du et al. (2019) take somewhat different approach and exploit neural networks introduce new graph kernel kernel. This in turn is shown to be equivalent to an infinitely-wer wiide GNN initialized with random weights and trained with gradient descent. Chen al. (2020) propose a graph neural architecture where each layer enumerates local sub-structures around each node and then maps them to a RKHS via a Gaussian kernel mapping. In the context of graph compression, Bouritsas et al. (0221) learn how to best decompose the graph into small substructures that are also learned.
(2019) show that GNNs have the same expressiveness
The closest work to ours we are aware of is that of Nikolentzos & Vazirgiannis (2020), who propose a GNN where the first layer consists of a series of hidden graphs that are compared against the input graph using a random walk kernel. However, due to their optimisation strategy, their model only works with a single differentiable kernel, whereas our model allows us to tap into the expressive power of any type and number of kernels. Moreover, in the architecture of Nikolentzos & Vazir- giannis (2020) the learned structural masks are assumed to be complete weighted graphs, whereas we allow for graphs with arbitrary structure.
3 GRAPH NEURAL NETWORKS FROM GRAPH KERNELS
3.1 PRELIMINARIES
Kernel methods are class of algorithms that are capable of learning when presented with particular pairwise similarity measure on the input data, known as a kernel. Consider a set X and a positive semi-definite kernel function K. X X I such that there exists map Φ X H into a Hilbert space H and K(xx, y) = ((x) p(y) for all x, E X. Crucially, X can represent any set of data on which a kernel can be defined, from Rd finite set of graphs. Hence, the field of machine learning is ripe with examples of graph kernels (see Section 2 which are nothing but positive semi-definite pairwise similarity measures on graphs. These can be either implicit (only IC is computed) or explicit (ø is also computed).
Weisneiler-Lehman test. The WL kernel (Shervashidze et al. 2011 is one of the most powerful and commonly used graph kernels and it is based the 1-dimensional Weisfeiler-Lehnnn (1-WL) graph isomorphism test. The idea underpinning the test is that of partitioning the node set by iter- atively propagating the node labels between adjacent nodes. With each iteration, the set of labels accumulated at each node of the graph is then mapped to new label through a hash function. This procedure is repeated until the cardinality of the set of labels stops growing. Two graphs can then be compared in terms of their label sets at convergence, with two graphs being isomorphic only if their label sets coincide.
Learning on graphs. Let = XV,X, E) be undirected graph with [V] nodes and |E| edges, where each node is associated to a label zvv) belonging to a dictionary D. A common goal in graph machine learning problems is to produce vector representation of & that is aware of both the node labels and the structural information of G. Generalizing the convolution operator to graphs, GNNs learn the parameters O of function h that embeds the graph into vector Z by performing
3

---

Under review as a conference paper at ICLR 2022
GKC layer
M,
M
Mm
Pooling
MLP
Vector quantization
Figure 1: The proposed GKNN architecture. The imput graph is fed into more GKC layers, where sub-graphs centered at each node are compared to a series structural masks through kernel function. The output which goes through vector quantization operation. We obtain a graph-level feature vector through pooling on the nodes features, which is then fed to MLP output the final classification label.
of real-valued feature vectors associated the graph nodes,
message passing Gilmer et al. 2017) in the I-hop neighborhood Ni of each node E V, i.e.
=(v)
Σ he (z(v),
wENg(w)
The convolution usually repeated for layers, and the final vectorial representation obtained by applying node-wise permutation invariant aggregation operator D on the node features 2(v).
3.2 PROPOSED ARCHITECTURE
The core feature of the proposed model is the definition of a new approach to perform the convolution operation on graphs. As opposed to the diffusion process performed by message passing techniques, design the Graph Kernel Convolution (GKC) operation in terms of the inner product between graphs computed through a graph kernel function.
Given graph G (V, E) with nodes, extract sub-graphs Ng" (u)(w) of radius centered at each vertex v E V. Each sub-graph consists of the central node v, the nodes at distance at most from v, and the edges between them. Each such sub-graph is then compared to set of structural through
masks
(.(() (G()),
where the resulting feature vector =(v) is non-negative real valued m-dimensional vector collecting the kernel responses, and the ith structural mask M, (LM,, EM,) graph with node L.M, (including node labels) and edge set E,M-
Since in this paper we focus on graph classification, the final part of our architecture, as depicted in Figure I consists of applying node-wise pooling operation on the previously computed feature vectors to obtain global graph descriptor. This then fed a multilayer perceptron (MLP) layer to obtain the final classification.
3.3 MULTI-LAYER ARCHITECTURE
Most graph kernels, including the WL kernel, work with discrete node labels. In our GKNN ar- chitecture, however, equation 2 yields an m-dimensional real valued vector for each graph node. Hence, need to discretize the output feature space before being able to perform a further con- volution operation. Before each convolution layer, except for the first one (unless the input node features continuous), add vector quantization operation the input node features, whereby the feature space is discretized using k-means clustering on the node features the current batch. Nodes then labeled according to the cluster index they belong to. To keep the labeling consistent
4

---

Under review as a conference paper at ICLR 2022
among different mini-batches, the k-means algorithm centroids step t + 1 are initialized using the centroids computed at the previous step t, i.e.,
(w) X(M,, C.M.,NNGVv.aa (XVV)o(()))))))
(3)
where (x) indicates the vector quantization operation described above
Note that in our current implementation we only compute the gradient of the kernel value with respect to the masks of the current layer, and not with respect to the input graph for that layer, which would be required to backpropagate the gradient to the previous layer. This is due to the presence of the vector quantization layer which complicates the backpropagation with respect to node features. To overcome this limitation and allow the optimization of the structural masks each layer, add skip connections between the layers and masks weights updated only along these paths. Empirically we observed this not to be a major problem as longer paths have diminishing weight. The final graph embedding after L layers is thus obtained by (Z*+ 24), where Z are the output features of the éth layer and -|- indicates the concatenation of node-wise features. In particular, in all our experiments we use sum pooling as the aggregation operator D.
3.4 OPTIMIZATION STRATEGY
Our learning problem can be formulated as follows: given set (Gi,..., Gr) of B training input graphs with node labels belonging to the dictionary D and associated class labels y) ... yn, our goal to find the optimal parameters ( and masks M, ) of the model g for the following minimization problem,
min Mm. Crosshntropyaom.......o (G.).
There are two main challenges that we need to consider when optimizing the structural masks. First, the number of nodes of the sub-graphs is not fixed and can in principle vary from (for isolated nodes) to (for fully connected graphs). Second, since graph kernel functions are not in general differentiable, the automatic differentiation mechanism of common neural network optimization libraries cannot be directly applied to our model.
Structural kernels representation When defining the space of graphs on which we want to op- timize the structural masks M. have consider the possible sub-structures present in the input graph that characterize it as belonging to a specific class. Assuming that this knowledge is not known priori, should allow learn structures large as the graph itself. Unfortunately, since the space of graphs grows exponentially with the number of nodes, this would be impractical. More- over, under the assumption of the presence of localized characterizing substructures, we usually need graphs of few nodes to capture their presence. In our implementation, we fix a maximum number of nodes d for each substructure and optimize for structural masks in the space
d M Ü (G)) p=1
(5)
where Go indicates the set of all possible connected graphs of p nodes, and DP the labeling space of p nodes. The impact of this hyper-parametert is studied in the ablation study in Section
Structural kernels optimization Graph kernels, as functions operating on discrete graph struc- tures, in general not differentiable. In order to be able to optimize the structural masks a Discrete Randomized Descent (DRD) strategy. Given an initial structural mask M, we let the graph evolve to M' through edit operations minimizing cost function. These operations consist of adding or removing some edges, and changing node labels. After the editing operation we extract the maximum connected component in M', thus allowing us to consider all the graphs with nodes p S d without explicitly optimizing over p.
We verified the displacement of the centroids induced by the k-means clustering in different models and datasets. With batch size of 16, at convergence, the displacement is always within 0.9% of the average distance between the centroids.
5

---

Under review as a conference paper at ICLR 2022
The DRD update is performed during the backpropagation phase of the model training step. Through the chain rule mechanism we can estimate the discrete gradient of the final classification loss w.rt. óloss
the structural mask M as 8M = =Ev 8loss 52(0)
6x(w) 6.M The discrete sub- sub-gradient of the kernel response
a(v) w.r.t. MM i.e., the gradient restricted the randomly selected edit operations, can be estimated
as the difference between the kernel responses after and before an edit operation:
5loss 6M
öloss 5r(v)
Σ
KC(M,
(6)
During each backpropagation step, thus sample edit operation from the set of all edit oper- ations on EM, and accept the edit only if the value of equation 6 is lower than or equal to O. This means that we always evolve toward a graph locally minimizing the loss function.
Together with the structural mask M, we also optimize probability distribution over the edit op- erations. The derivative of edit operation probability p(e) is estimated using the same equation 6 and optimized with standard gradient descent optimizers. Further details are in the Appendix 1
Sensen-Shannol divergence loss Depending on the number of structural masks learn, we ex- perimentally observed that different structural masks can give a similar response over the same node. To avoid this behavior and push the model to learn a more descriptive node feature vector, we propose to regularize the structural masks learning process by adding a Jensen-Shannon diver- gence (ISD) loss. The ISD is computed between the feature dimensions considered as probability distributions over the nodes of the graph.
Let P: {a E V} be the probability distribution induced by the ith kernel over the graph nodes. is scaling factor ensuring that >,, Pi(v)) 1. We define the JSD loss as
JSs = - Σ P
+
(P.). i=1
where (P)) is the Shannon entropy. The final loss optimize is then the sum of 1) the CrossEn- tropy loss defined in equation 3.4 and 2) las multiplied by a weighting factor.
3.5 EXPRESSIVE POWER
In this subsection, we study the expressive power of the proposed architecture. Recall from Morris let al. (2019) that the expressive power of standard GNNs (i.e.. GNNs that only consider the immedi- ate neighbours of node when updating the labels) is equivalent to that of the 1-WL test. We argue that GKNN has higher expressive power than the 1-WL test (and thus standard GNNs). To show this, we start by demonstrating that every pair of graphs that can be distinguished by the 1-WL test can also be distinguished by our model. Without loss of generality, in the follow- ing we consider two unlabelled graphs 91 = (V,, F1) and G2- = (V2, E2)) with the same number of nodes = |Vi |V2].
pressage-passingg
Theorem 1. Given two input graphs Gn and Gz, if the 1-WL test can distinguish between them then there exists an instance of GKNN that can also distinguish them.
A sketch of proof of Theorem can be found in Appendix A.2 Next, we show that the GKNN can distinguish between pairs of graphs where the 1-WL test fails. To see that this is the case, consider the standard example of two graphs with 6 nodes, where the first graph is made of two disconnected cycles with nodes, while the second graph is single cycle with nodes. Both graphs are regular, with every node of the graphs being adjacent to two other nodes, i.e., every node has degree 2. As explained in Nikolentzos al.] (202)), despite being non-isomo,,hic, the two graphs are considered identical by the 1-WI. test (in other words, the WI. relabeling procedure converges to the same set of labels for the two graphs). To see why this happens, consider that through the propagation phases each node is only made aware of what degree other nodes in the graph have and not how many such nodes can be reached. As the following lemma shows, this is not an issue for the GKNN:
Lemma 2. The GKNN is able identify graph containing triangles.
A sketch of proof of Lemma 2 can be found in Appendix A.2 From Theorem and Lemma 2 follows that the GKNN has a higher expressive power than the 1-WL. test and thus standard GNNs.

---

Under review as a conference paper at ICLR 2022
Nodes
#Structural masks
Graph kernel
Radius r
# Layers
JSD weight
100
100
100
100
95
95
95-
95
95
95
85
85-
85
85-
80
80
80
80-
70
3
6
70
8
16
32
04
70
prop
91
70
70
70
L.ex03
1.0
1.0e-p
1.04005
Figure 2: Ablation study: bar plots of classification accuracy with standard error. Left to right: number of nodes (i.e., structural mask size), number of structural masks, kernel functions (WL, WL with Optimal Assignment, Graphlet, Propagation, and Pyramid match kernel), subgraph radius, number of GKC layers, and weight of the JSD loss.
4 EXPERIMENTAL EVALUATION
4.1 SENSITIVITY STUDY
We performed an ablation study to investigate how the various components and hyper-parameters of our architecture affect the model performance. To this end, we consider the MUTAG dataset (for more details on the datasets, see Appendix/A.7). We start by setting baseline network configuration (one layer. 16 structural masks of 6 nodes each, subgraphs radius of 3, WL graph kernel and JSD vary. Specifically, we study
weight of 10 4) and then we let the considered the influence of the number of nodes (i.e., the maximum size of the structural masks), number of structural masks, kernel function, subgraph radius, number of GKC layers, and weight of loss
We report accuracy results as bar plots with standard error in Figure 2 (from left to right: number of nodes, number of structural masks, kernel function, subgraph radius, number of GKC layers, and weight of the JSD loss). Both the number of structural masks and the maximum number of their nodes play a crucial role in the classification accuracy and thus need to be carefully chosen. As expected, also the choice of the kernel function is crucial factor, highlighting the advantage of allowing to plug-in any non-differentiable graph kernel function. As for the subgraph radius, the number of neighbors clearly influences the model performance and there seem to be an optimal subgraph size able to catch the structural characteristics of the input graphs. The ablation validates also our multilayer architechture design, even if the model requires just two layers to reach the best accuracy. This is justified by the wider neighborhood involved in our convolution operation compared to the standard message passing formulation. The results also confirm the importance of the JSD loss, as the performance of the GKNN increases once the loss is introduced.
4.2 INTERPRETABILIT ANALYSIS
One of the factors that fostered interpretability in classical CNNs is the possibility to visualize and analyze the learned filters capturing the fundamental structures characterizing the input im- ages (Nikolentzos & Vazirgiannis 2020). This feature is missing in the classical formulation of graph convolution relying on the message passing paradigm. On the other hand, our method learns actual graph masks, potentially increasing the interpretability of the model by allowing us to probe into the explanatory factors of variation behind the input data through the learned structural masks.
To show the potential of our model to capture fundamental structures in the input graphs, we devised simple but effective synthetic experiment. First, we train our model on binary classification task, ie., predicting if a certain graph motif is present or not in the given graph. Then we qualitatively assess the learned structural masks have captured or not the graph motif. Following the setup of Niikllentzos & Vazirgiannis (2020). we created 5 different datasets, one for each of the graph motif depicted in Figure 3 (upper row). A detailed description of the synthetic datasets and training details can be found in the Appendix A.6 The model is then trained end-to-end to predict the graph labels on a 90/10% train/test split.
The results show that the learned structural masks have very similar structures to those of the cor- responding motifs, with only a few missing or misplaced edges (see for instance the columns cor- responding to the ring and the wheel). Moreover, the distribution of the responses in the original graphs clearly highlights the motifs position. Overall, the results demonstrate that our model is able to extract the salient structural patterns, which in turn allows understand what features were
7

---

Under review as a conference paper at ICLR 2022
Ring
Wheel
Grid
Ladder
Cliques
Figure 3: Interpretability analysis results. Each column refers to a graph motif. Upper row: original motif. Mid row: structural mask with the strongest response. Bottom sample graph including the motif. Colors indicate the node response to the filter, with lighter colours (yellow) indicating high response and darker colors (blue) indicating a low response.
M1-
M2
M4
My
M12
M16
Loss
Figure 4: Top significant structural masks (top) learned by our model on the MUTAG dataset and their response over input graph nodes (bottom). The left bar plot shows the impact of each structural mask on the classification loss.
detected for given input graph. We would like stress that even though this aspect is not the final goal of this work, the interpretability of our model definitely helps to foster trust in our approach.
To further investigate the ability of our model capture salient structural features, we show in Figure [|somm of the structural masks learned on the MUTAG dataset. In particular, we trained model with the hyper-parane saper-parameters of the baseline architecture used in the ablation study of Section [. To select the most significant filters, we manually set to zero the response of the ith filter M; and evaluate again the classification loss. In the bar plot (Figure 4 left) we report the loss increase after zeroing each filter response. Below each mask also show the input graph of the training set that gave the highest kernel response among all nodes together with the per-node response as node colors (yellow indicating high response, dark blue indicating a low response).
4.3 GRAPH CLASSIFICATION RESULTS
Datasets We evaluate the performance of the proposed model the graph classification task. We make use of publicly available datasets frequently employed in the GNNs literature (Kersting et al, 2016). In particular, NCIT, PROTEINS, and PTC) and a social dataset (IMDB-BINARY BiodChemoo-nnfrraaiic graphs differ from social graphs as the former nodes have categorical input features. whereas in the latter there are no features. More details on these datasets can be found in Appendix A.7
4 bio/chemo-informateee
datasets collecting molecular graphs (MUTAG.
Experimental setup et al. 2018), DifiPool (Ying et al. 2018), GIN (Xu et al. 2018), and (s)GIN (Di al. 2020): two
We compare our model against: state-of of-the--rtttttt GNNs: DGCNN Zhhang
8

---

Under review as a conference paper at ICLR 2022
Table 1: Classification results chemo/bio-inforraties and social datasets. Mean accuracy and
standard eπror are reported. The best performance (per dataset) is highlighted in bold.
MUTAG
PTC
NC11
PROTEINS
IMDB
Baseline
78.57 = 4.00
58.34 2.02
68.50 = 0.87
73.05 + 0.90
49.50 = 0.79
WL
82.67 2.22
55.39 1.27
79.32 + 1.48
7.31
71.80 = 1.03
DifiPool
81.35 + 1.86
7..72 2.77
73.13 1.49
67.80 = 1.44
GIN
78.13
78.63 2.66
70.98 1.61
71.10 = 1.65
DGCNN
85.06 + 2.50
2.75
7.95
74.31 1.03
53.00 # 1.32
GraphSAGE
77.57 + 4.22
59.87 = 1.91
0.99
73.11 1.27
68.80 = 2.26
SGIN
84.09 + 1.72
2.227
7..54
73.59 1.47
71.30 = 1.75
RWGNN
82.51 + 2.47
55.47 2.70
72.94
73,95 1.32
69.90 # 1.32
Ours
85.73 + 2.70
58.39 =
71.52 = 1.12
74.48 1.10
69.70 = 2.20
distinct baselines, depending on the dataset type (see below): Molecular Fingerprint (Ralaivola et al., Luzhnica et al. 2019) and Deep Multisets (Zaheer et al. 2017): the WI. kernel (Shervashidze 1): RWNN, a GNN model employing a differentiable graph kernel (Nikolentzos & Vazir-
2005
et al.
giannis 2020), the closest existing neural architecture to ours. For the WL. subtree kernel we use a
C-SVM (Chang & Lin 2 classifier. For the baselines, we follow Emricaa et al. (2020) and use the Molecular Fingerprint technique (Ralaivola et al. 2005 Luzhnica et al. 2019) for chemical datasets.
For the social dataset rely the permutation invariant model of Zaheer al. (2017).
To ensure a fair comparison, for each of these methods we follow the same experimental proto- coL. We perform 10-fold cross validation where in each fold the training set is further subdivided in training and validation with a ratio of 9:1. The validation set is used for both early stopping and to select the best model within each fold. Importantly, folds and train/validation/test splits are consistent among all the methods. For all the methods we perform grid search to optimize the hyper- parameters. In particular, for the WL method we optimize the value of C' and the number of WL iterations h E {4, 5, 6, 7). For the RWGNN we investigate the hyper-parameter ranges used by the authors (Nikolentzos & Vazirgiannis 2020), while for all the other GNNs we follow Errica et al. 2020) and we perform a full search over the hyper-parameters grid. For our model, we explore the tollowing syper-parameters: number structural masks in {8,16,32), maximum number of nodes of a structural mask in {6,8), subgraph radius in (1,2,3). number of layers in (1,2.3) and always use WL as graph kernel. all our experiments, we train the model for 1000 epochs, using the Adam optimizer with learning rate of 0.001 for MLP weights and of 0.01 for the edit operation probabil- ities, and a batch size of 32. The MLP takes as input the sum pooling of the node features and is composed by two layers of output dimension and e (# classes) with ReLU activation in between.
The accuracy for each method and dataset is reported in Table 1 For the bio/chemo- informatics datasets, the performance of our approach is on par with the best ones, as we can see for MUTAG, PROTEINS, and PTC. This holds as long as the number of node labels is low. Indeed, in the case of high-ddmenssioal node labels (e.g.. NCII), the classification accuracy tends to decrease as the optimization becomes harder. As for the social dataset, the performance of our approach is satisfactory, particularly considering the lack of diseriminative substructures in social networks.
Results
CONCLUSION
We introduced new convolution operation on graphs based on graph kernels. We proposed the graph kernel convolution layer and an architecture that makes use of this layer for graph classifi- cation purposes. The benefits of this architecture include the definition of fully structural model that can exploit the vast collection of existing graph kernels, a provably superior expressive power when compared to standard GNNs, and the possibility to visualize the learned substructures a way that is reminiscent of the convolutional filters of standard CNNs. Future work will attempt to address the limitations of the current approach. For example, the optimization strategy we employed in this work prefers low-dimensional discrete input labels over high-dimensional continuous ones. Our model is also not well suited for social graphs, where structure plays a minor role and small- worldness implies that the sub- graphs will span the majority of the input graph even at small radii. Finally, the lack of widely available GPU implementations of graph kernels implies that our model cannot presently tap into the computational power of these units.
9

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
To maximize reproducibility of our results by the academic community, we provide an extensive discussion of the model, its hyper-paramettrs, the training and the experimental setup. We also make use of widely used publicly available datasets. Finally, we include the source code in the supplementary material and we will make it publicly available upon acceptance.
REFERENCES
James Atwood and Don Towsley. Diffusion-convolutionaa neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Lu Bai and Edwin R Hancock. Graph kernels from the jensen-shannon divergence. Journal of mathematical imaging and vision, 47(1):00-69, 2013.
Lu Bai, Luca Rossi, Andrea Torsello, and Edwin R Hancock. A quantum jensen shannon graph kernel for unattributed graphs. Pattern Recognition, 48(2):344-3555 2015.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels graphs. In Fifth IEEE international conference on data mining (ICDM'SS) pp. 8-pp. IEEE, 2005.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Mlans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl_1 I): i47-i56, 2005.
Giorgos Bouritsas, Andreas Loukas, Nikolaos Karalias, and Michael M Bronstein. Partition and code: learning how to compress graphs. arXiv:2107.01952, 2021.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges. arXiv preprint WrXiv:2104.13478 2021.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM trans- actions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kemel networks for graph- structured data. International Conference on Machine Learning, pp. 1576-1586. PMLR, 2020.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34, 2021.
Giovanni Da San Martino, Nicolò Navarin, and Alessandro Sperduti. Tree-based kernel for graphs with continuous attributes. IEEE transactions on neural networks and learning systems, 29(7): 3270-3276, 2017.
Asim Kumar Debnath, Rosa Lopez de Compadre, Gargi Debnath, Alan Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
Xinhan Di, Pengqian Yu, Rui Bu, and Mingchao Sun. Mutual information maximization in graph neural networks. In 2020 International Joint Conference on Neural Networks (IJCNN), pp- 1-7. IEEE, 2020.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels, Advances in Neural Information Processing Systems, 32:5723-5733 2019.
Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations. Advances in Neural Information Processing Systems, 34, 2021.
10

---

Under review as a conference paper at ICLR 2022
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning. pp- 1263-1272. PMLR, 2017.
Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformaties, 17(1):107-108, 2001.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th international conference on machine learning (ICML-03), pp. 321- 328, 2003.
Kristian Kersting, Nils M Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels. URL http://graphherrets. cs. tu-dortmund. de, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the 5th International Conference on Learning Representations, ICLR $17, 2017.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint 12066620066483, 2012.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris, A survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.
Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Deriving neural architectures from sequence and graph kernels. In International Conference on Machine Learning, pp. 2024-2033. PMLR, 2017.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):97-109, 2018.
Antonio Lima, Luca Rossi, and Mirco Musolesi. Coding together scale: Github collaborative social network. In Eighth international AAAI conference on weblogs and social media, 2014.
Enxhell Luzhnica, Ben Day, and Pietro Liò. On graph classification networks, datasets and baselines. arXiv preprint arXiv: 190.0468900068., 2019.
Giorgia Minello, Luca Rossi, and Andrea Torsello. Can a quantum walk tell which which? study of quantum walk-based graph similarity. Entropy, 21(3):328, 2019.
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 Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4602-4609, 2019.
Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. Advances in Neural Information Processing Systems, 33:16211-16222 2020.
Giannis Nikolentzos, Polykarpos Meladianos, Antoine fean-Piern Tixier, Konstantinos Skianis, and Michalis Vazirgiannis. Kernel graph convolutional neural networks. In International conference artificial neural networks, pp. 22 22-32. Springer, 2018.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 1 130: 195-205,, 2020.
Liva Ralaivola, Sanjay J Swamidass, Hiroto Saigo, and Pierre Baldi. Graph kernels for chemical informatics. Neural networks, 1898):093311110, 2005.
Motakuri V Ramana, Edward R Scheinerman, and Daniel Ullman. Fractional isomorphism of graphs. Discrete Mathematics, 132(1-3):247-255, 1994.

---

Under review as a conference paper at ICLR 2022
Jan Ramon and Thomas Gärtner. Expressivity versus efficiency of graph kernels. In Proceedings of the first international workshop on mining graphs, trees and sequences, pp. 35-74, 2003.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. arXiv preprint vrXiv:/907.0 10903, 2019.
Luca Rossi, Andrea Torsello, and Edwin R Hancock. Measuring graph similarity through continuous-time quantum walks and the quantum jensen-shannon divergence. Physical Review E, 91(2)022815, 2015.
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-80, 2008.
Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 32(suppl 1):D431-D433 2004.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Ef- ficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp- 488-495, PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Nikil Wale, lan A Watson, and George Karypis. Comparison of descriptor spaces for chemical com- pound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1))4-24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 11X10:1810.00826, 2018.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. pp. 1365-1374, 2015.
Cheng Ye, César H Comin, Thomas K DM Peron, Filipi N Silva, Francisco A Rodrigues, Luciano da F Costa, Andrea Torsello, and Edwin R Hancock. Thermodynamic characterization of net- works using graph polynomials. Physical Review E, 92(3):032810, 2015.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. arXiv preprint arXiv:1806.08800 2018.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. Proceedings of the st International Conference on Neural Information Processing Systems, pp. 3394 3404, 2017.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirld AAAI Conference on Artificial Intelligence, 2018.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A. EDIT OPERATIONS PROBABILITY OPTIMIZATION
Together with the structural mask M, we optimize also the probabilities p(e,,)Vi.j 1 I...p of each edge to belong to the structural mask, and the probability p(4; = djvi = p...p,dd E D of each node to assume the label value d. Given a structural mask . (LM, ÆM) with node labels
L -= 11..... Ip and edge set E, the probability distribution of edit operations can be derived from the previous edge and label probabilities as
if cty E otherwise
P(E' = EUee))=
ple,)) LEe Ex plec)))
(8)
Eij $ otherwise
p(E' E -
1 1-p(es))
(9)
E.,,tEE Ple, plea, , (leppp(s
for edge edit operations consisting in either add or remove and edge cij, while for changing the label I of the ith node to dl as
if = d otherwise
-d,
p(h=d) D.dc P x()=
(10)
To keep the optimization simpler, we keep two separate distributions for edge and node label editing operations and alternate between the two. The derivatives of edge and node label probabilities are computed according to equation 6 and used as input to standard gradient descent based optimizers (e.g.. Adam).
A.2 EXPRESSIVE POWER
Sketch of proof of Theorem This is trivially the case when we adopt the WL kernel in the GCK layer and the radius r is such that the sub-graphs Ng, (v) span the entire graph Gi (similarly for G2). Under this assumption, the set of labels computed against any one mask will be the same for every node in graph G1 (G2), since all the sub-graphs are identically equal to the graph itself. Assuming that we have set of structural masks M = {M1..... Mm,) } that span the space of graphs over n nodes, then, under the hypothesis that the 1-WI. test can distinguish between G1 and G2. the set of labels computed by the GCK layer (i.e., the responses of the masks) while identical on all the nodes of each graph, will differ between the two graphs. In particular, the response will peak for any mask
fractionally equivalent to the graph itself (Ramana et al. 1994). Therefore, under any reasonable pooling strategy, the GKNN will be able to distinguish between the two graphs.
We now prove that the same holds for an arbitrary sub-graph radius r, under the assumption of a 1. but as shown in the previous
sufficient number of layers. For simplicity, will assume argument, increasing r increases the descriptive power of the GCK layer. The prove derives from the fact that the full GCK Layer step. The label propagation is given by the computation of the WI. kernel against a structural mask, due to the 1-WL iterations on the sub-graphs.
be seen 1) label propagation step followed by 2) hashing
The hashing, on the other hand, comes from the implicit dot product against the structural masks. This is in essence projection onto the space spanned by them and forces hashing where the adopted masks form a representation space for the hashing itself. Note that, under the assumption of a sufficiently large (possibly complete) set of structural masks M {M,,... MM } spanning the space of graphs over n nodes, the dot product induced hashing will not introduce conflicts between nodes with different labels. other words, labels that are distinct under the 1-WL iterations will eventually be mapped to distinct labels at some GCK layer. Note, however, that under these assumptions the expressive power is greater or equal than that of 1-WL and labels that are equivalent under 1-WL iteration can indeed be mapped to distinct labels by some GCK layer. In fact, the propagation for I-WL uses only the star of radius around a particular node, while our scheme uses the full 1-hop sub- -raph which includes connections between neighbors Therefore, given a sufficient number of GCK layers and a reasonable pooling strategy, the GKNN will be able to distinguish between the two input graphs.
13

---

Under review as a conference paper at ICLR 2022
MUTAG
PTC
Model
Model
Figure 5: Top 4 significant structural masks learned by our model on the MUTAG (left) and PTC
(right) datasets starting from two different random initializations of the model weights (rows).
Sketch of proof of Lemma Assume we have a GCK layer with radius r = that adopts a WL kernel and set of structural masks M [....... .M } representing all stars up to nodes, where n denotes the number of nodes of the input graph. The presence of a triangle in the graph induces the existence of at least three sub-graphs of radius with connections between neighbors, i.e., not stars On these sub-graphs, no star masks will achieve maximum similarity under the WI. kernel. Having pooling process that normalizes the masks responses w.r.t. size and maximizes over the masks on the same node, implies that each node will have the same maximal response if it does not contain triangles and lower response otherwise. min- min-ppoling process over the node features will then be able to discriminate between graphs with and without triangles.
Let the radius of the sub- aub-graphs in equation be r Then the sub- sub-graphs built around the nodes of 91 and G2 will be structurally different, i.e., triangles in &1 and 3 nodes path graphs in G2. As consequence, the feature vectors srv)) over the nodes of the two graphs will be different, allowing the GKNN to distinguish between them.
A.3 CONVERGENCE ANALYSIS
To experimentally assess the convergence of our optimization strategy we investigated the behav- ior of the structural masks both at convergence and during the optimization. Figure 5 we show the most significant (see 2 for the definition) structural masks learned by two different training instances of the same architecture. Both models end up learning similar structural masks, indicating that optimization is able to reach stable local optimum. This is also supported by the inter- pretability analysis of Section 4.2 showing that the learned masks resemble the local substructures of the input graphs.
In 6 also investigate the evolution of different initializations of the structural mask weights leading the same final structure in two different models. As we can see, labels have faster convergence than the connectivity, this is probably due to the bigger impact that they have on the similarity score computed by graph kernels (WL in this specific case). On the right we report also the decreasing curves of the JSD and cross- cross-entropy losses during the training of a model on MUTAG together with the cross-entropy loss computed on the validation-set.
A.4 COMPUTATIONAL COMPLEXITY AND RUNTIME ANALYSIS
The computational complexity of our model linear with respect to the number of input graph nodes and polynomial with respect to the sub-graph radius r, where the exact complexity depends on the choice of kernel.
In terms of runtime, for the datasets considered in this paper, this translates to the results shown in Table 2 where we report the average training time per dataset (both total and per epoch) of the models trained during the grid search and the average inference time of the best model. Both training and testing of each model were performed using just a single core of an Intel(R) Xeon(R) CPU E5-4627 v3 @ 2.60GHz processor. Note that training and test speed of a single model could be significantly improved by parallelizing the computation over the batch samples or by using multi- thread implementations of graph kernels.
14

---

Under review as a conference paper at ICLR 2022
Modell 1
-23
Triin cross-entropy
Initialization
Upoch
Epoch 160
Final
Model 2
4.1
cross-entropy
2.1
Initialization
Ejocc 5
Ppoch 110
Ejnch 150
Final
opochs
Figure 6: Left: Evolution the learned structural masks during the training epochs showing two different initializations (belonging to two different models) that led to the same structural mask on the MUTAG dataset. Right: Sample of training curves model trained on MUTAG.
Table 2: Average training time (both total and per epoch) and inference time for the datasets con-
sidered in the present work. The two rightmost columns show some relevant datasets statistics that influence the running time. The standard deviation is reported with the symbol +.
Total training
Training time
Test time per sample (s)
# Graphs
Avg Nodes
time (h)
per epoch
PROTEINS
12.27 8.27
71.82 53.60
0.10 0.06
1113
39.06
MUTAG
1.43 0.72
6,58 # 3.35
0.11 + 0.02
188
17.93
PTC
+
22.61 = 19.91
0.08 0.06
344
14.69
NCII
21.35 # 14.47
217.35+156.70
0.04
4110
29.87
IMDB
6.65 + 1.98
35.46 7.89
0.11
1000
19.77
A.5 RANDOM GRID SEARCH TRAINING STRATEGY
In Scction we reported the results after full search on the considered hyper-parametery grid. Although this the most commonly adopted protocol for the considered datasets ( |Erria et al. 2020 Nikolentzos & Vazirgiannis (2020): Xu et al. (018)), in practical settings it may not be always feasible to explore the full hyper-parameters space. straightforward strategy to reduce the number of models to test is through random grid search, where the best model is determined based on a subset of randomly chosen report in Table[]th mean and standard error of the average accuracy over all folds of 30 runs of random grid-search considering different numbers of tested models (5, 10, 20, 30, all). This is compared against the perfomance of GraphSAGE, sGIN, and RWNN.
combinations. To assess the behavior of our
architecture on this setting
Our model shows a similar behavior to that of most of our competitors, with a benefit when including more models in the evaluation. The average drop in performance from randomly selecting models in contrast to performing full grid search is around 2% and decreases with the number of models considered. The only exception seems to be sGIN, whose performance slightly decreases consider- ing more models, probably due to a lower sensitivity of the model to the explored papeer-prrmeters as suggested also by the lower standard error.
A.6 SYNTHETIC EXPERIMENTS
Datasets For the interpretability analysis experiments we built dataset for each of the graph motifs. Each dataset is composed of 2,000 graphs, equally divided into positive and negative sam- ples, with a varying number of nodes between 30 and 50. Each sample pair is generated starting from the same Erdos-Rényi graph, with an edge observation probability of 0.1. Next, for each Erdös-Rénn Rényi graph, two new graphs are built. The first one, labeled as 1, is created by connecting each node of the Erdōs Rényi to the nodes of the structural motif with probability 0.02. The second one, labeled as O, obtained in a similar manner, however instead motif we insert a random graph with the same number of nodes and edges of the motif structure.
15

---

Under review as a conference paper at ICLR 2022
Table 3: Mean accuracy and standard error when performing random search with increasing num- ber of tested models.
10
20
30
ALL
MUTAG
GraphSAGE
75.52 0.62
75.54 # 0.96
75.66 # 1.12
74.48 = 0.72
77.57
SGIN
84.56 + 0.46
84.51 0.38
84.45 + 0.27
84.11 0.13
84.09
RWNN
84.62 0.59
84.22 0.61
83.77 0.64
83.87 = 0.58
82.51
Ours
84.72 0.66
85.15 - 0.61
85.08 0.64
84.81 = 0.52
85.73
NCI1
GraphSAGE
69.79 0.98
68.67 = 0.88
#1.49
73,49 = 0.34
75.89
sGIN
76.68 + 0.25
77.05
77.41 0.11
77.54
RWNN
70.92 0.68
72.11 0.33
72.62 + 0.32
73.02 = 0.23
73.82
Ours
68.21 0.25
68.45 # 0.18
69.16 # 0.22
69.51 # 0.18
70.12
PTC
GraphSAGE
58.22 0.72
57.48 0.67
58.21 0.44
57.3
59.87
SGIN
58.37 = 0.58
$7.3
57.05 0.42
56.63 + 0.36
56.38
RWNN
57.69 0.72
58.53 0.52
97.60
57.93 0.61
55.47
Ours
56.87 0.85
57.65 # 0.60
$7.74
58.22 # 0.51
58.41
PROTEINS
GraphSAGE
70.86 0.39
70.73 + 0.42
71.62 # 0.56
7
74.31
sGIN
73.50
73.89 + 0.14
73.61
0.14
0.10
73.59
RWNN
72.80 2 0.30
73.46 0.15
73.50
+ 0.18
73.37
73.95
Ours
74.36 0.19
74.35 # 0.19
74.37 0.16
74.49 # 0.11
74.48
IMDB
GraphSAGE
55,90 2: 1.06
57.56 1.00
59.96 0.98
64.96 # 0.35
68.80
sGIN
71.99 + 0.20
71.90
0.179
71.48 = 0.08
71.40
RWNN
69.63 1.22
70.33 - 0.30
69.87 + 0.28
69.92 = 0.29
69.90
Ours
66.94 0.46
67.71 # 0.41
68.72 + 0.27
68.72 # 0.27
68.70
Training details
We trained the network with the same hyper-parametten as in ablation base- line in section 4.1 with the exception of the number of structural masks, which is set to 8. Moreover, we replaced the ReLU activation of the final MLP with a Sigmoid activation.
A.7 DATASETS
We validated our approach on graph classification experiment on the following wealwwrldd datasets.
MUTAG (Debnath et al. 1991) is dataset consisting of 188 mutagenic aromatic and heteroaromatic nitro compounds (with? discrete labels) assayed for mutagenicity Salmonella typhimurium. The goal is predicting whether each compound possesses mutagenicity effect on the Gram Gram-negative bac- terium Salmonella typhimurium.
NCI1 (the anti-cancer activity prediction dataset) is balanced subset of datasets of chemical com- pounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines (Wale et al. 2008). It has 37 discrete labels.
PROTEINS (Borgwardt et al., 2005 Dobson & Doig 2003) dataset consists of proteins represented graphs. Nodes represent the amino acids and edge occurs between two vertices if they neighbors in the amino-acid sequence or in 3D space. It has 3 discrete labels, representing helix, sheet turn. The aim is to distinguish proteins into enzymes and non-enzymes.
PTC (Predictive Toxicology Challenge) dataset (Helma et al., 2001: Kriege & Mutzel 2012) is a collection of chemical compounds reporting the carcinogemicity for Male Rats (MR). Female Rats (FR), Male Mice (MM) and Female Mice (FM), We selected graphs of Male Rats (MR) for evalua- tion, consisting of 344 graphs very small and sparse with 19 discrete labels.
16

---

Under review as a conference paper at ICLR 2022
ENZYMES consists of protein tertiary structures obtained from Borgwardt al. (2005), in particular 600 enzymes from the BRENDA enzyme database (Schomburg et al. (004). The task for this dataset is assigning each enzyme one of the EC top-level classes. For our experiments considered only discrete labels.
collects graphs about movie collabora- tion. Each graph consists of nodes representing actors/actress who played roles movies in IMDB and edge between vertices takes place if they appear in the same movie. Graphs are derived from the Action and Romance genres. The task is to identify which genre an ego-network graph belongs to.
MNDB-BINARY dataset (Yanardag & Vishwanathan 2015)
17


Reviews:
[{"review_id": "pEJwxcuxKCR", "reviewer": "Reviewer_55BS", "summary": "", "questions": "", "limitations": "", "rating": 6, "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:\n- The paper presents a novel and interesting class of learning algorithms for processing graph-based data. This is is a particularly relevant area in machine learning which contributes to raising the significance of this work.\n- The model is somewhat more interpretable than competitors and seems to be well apt to settings where the topological structure of the graphs plays a major role \n- The paper is generally well written and easy to follow, although some parts of the presentation could be improved as in the detailed comment 1. \n\nWeaknesses:\n- The model has some limitations. First, it seems limited to graph classification/regression problems. Could it be used also for node-level tasks? Furthermore, it is suitable to settings in which nodes have either no or only a discrete set of labels (with low cardinality). The authors should be more clear about these limitations from the introduction.\n- The optimization problem involves optimizing over discrete structures. I believe the part regarding the learning technique could be clearer, more formal and with more details. Please see detailed comments. For this reason, I have some doubts about how much of the performance is driven by learning and how much by engineering. \n- The experimental section is improbable, see detailed comments 4.\n\nDetailed comments:\n1. Clarity: \na) in *To keep the labelling consistent among different batches, the k-means algorithm centroids at step $\\ell + 1$ are initialized using the centroids\ncomputed at the previous step* (pag 4) does batch mean layer? Or is it about batched (stochastic?) processing of the nodes or of graphs in a mini-batch of graphs?\nb) On page 3, it is not entirely clear to me what $g$ is and what $\\theta$ and $\\Theta$ refer to (specifically, do they represent the same sets of parameters?). Does (1) implements $g_{\\theta}$?I think this passage could be written much more clearly. \nb2) This confusion is carried forward also to eq (4). What is $\\theta$ there precisely? Only the parameters of the last classification layer?\nc)  The $h$ in (4) seems to be quite different from the $h$ in (1), probably it would be better to change notation there to avoid confusion.\nd) The proofs are only sketched, with little details and not particularly easy to follow. Just to give an example, in *the presence of a triangle in the graph induces the existence of at least three sub-graphs of radius 1 with *cross-neighbor* connections.* what does cross-neighbor specifically mean?\n\n2. I never heard of the discrete randomized descent method and the authors seem not to make any reference. Can the authors comment on this? If this is a (well-known) approach, please add a reference, otherwise, I think there should be more explanation about the method. For instance, in P(6) there is an equality sign which seems misplaced (also the authors talk about \"estimation\"). On the same line, I think also the concept of discrete sub-gradient is non-standard and needs to be defined or linked to some relevant literature. For instance, it seems that it differs from the concept in [1].\n\n3. The authors argue that in order to backpropagate the error in a multi-layer version of the architecture they need to add skip connections since they do not propagate the gradient through the vector quantization operation. However \"discrete gradients\" are used to learn both the mask structures and the edit distributions. Can't they (or similar strategies) be used also to propagate the gradients throw the quantization operations?\n\n 4. Regarding experimental validation: a) I would like to see a training curve. How much does the model improve with iterative optimization? How many iterations are needed and how many passes through the training data? b) I wonder what's the effect of the initialization. I would ideally like to see a set of experiments to ascertain how much the (random) initialization impacts the performances and convergence/training time. c) I believe that grid search makes it really difficult to understand what is it the tuning effort of the proposed model (learning algorithm)  with respect to the other competitors. This is because the total allocated computational budget can vary extensively. In my opinion, random search would have been a better and equally simple alternative, as it allows to have an \"anytime solution\" which makes it easier to compare methods (i.e. at each timestep, one could compare the best model found so far. \n\nMinor points:\n\n5. The authors make the point that GKN can leverage the presence of many graph kernels that have been proposed in the literature. However, most of the experiments have been done with the WL kernel. Would it be possible to have a GKN that uses multiple graph kernels? If so, how would it fare on the benchmark datasets?\n\n6. A discussion of the computational complexity is entirely missing, as well as reports of runtime measurements.\n\n7. I would call section 4.1*Sensitivity study* rather than *Ablation study*. Ablation usually refers to the practice of removing components of the learning algorithm that is being proposed. Instead, section 4.1 is about seeing what is the relative effect of each of the model hyperparameters.\n\n8. Missing sensitivity analysis of the number of clusters to use during the quantization step.\n\n[1] Bagirov, Adil M., Bülent Karasözen, and Meral Sezer. \"Discrete gradient method: derivative-free method for nonsmooth optimization.\" Journal of Optimization Theory and Applications 137.2 (2008): 317-334.\n", "summary_of_the_paper": "This paper proposes a novel architecture for graph processing that uses graph kernels with learnable structural masks.\nThe core feature of this novel architecture is the graph kernel convolution (GKC) layer. \nThe GKC layer consists of computing for each node $v$ a subgraph centred in $v$ of radius $r$, then the subgraph is compared with a series of structural masks through a graph kernel. The resulting kernel responses are collected into a vector, which is then quantized using k-means clustering, and the cluster label is used as the new node label. \nMultiple layers can be stacked, although they require adding skip connections because of the quantization operation.\nThe authors propose also ", "summary_of_the_review": "This paper is a potentially significant contribution to the area of graph ML.\nAt the moment, however, I have some concerns regarding the training mechanism proposed, specifically regarding the utilization of \"discrete gradients\". Moreover, the experimental section could be improved.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "d6BgARD627A", "reviewer": "Reviewer_6pRJ", "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": "- In summary, the approach proposed in this paper is interesting and deals with a topic that has not been thoroughly studied yet. The paper generalizes the model presented in [1] and allows the use of any graph kernel as a component of graph neural networks. However, the paper in its current form does not appear ready for publication and there are several concerns that the authors need to address (see comments below). Furthermore, the empirical results are okay, it seems that the model is competitive with the baselines, but they are not impressive.\n\n- One of the main limitations of the proposed model is its computational complexity, but the authors do not discuss it in the paper. Since the authors extract subgraphs of radius r centered at each node, I would expect the complexity of the model to be high especially when r is set to large values (e.g., 3, 4, etc). I also guess that the high complexity of the model is the reason why the authors do not evaluate it on any of the REDDIT datasets or on COLLAB since these datasets contain very large graphs. I would suggest the authors also report the running time of the proposed model on the different datasets such that one can compare them against those of other baselines. The authors mention in the conclusion that there are no widely available GPU implementations of graph kernels, thus it is likely that the running time of the proposed model would be prohibitive for real-world applications. This is a key weakness of the paper, but still reporting those running times would strengthen the paper.\n\n- It is not clear to me why the input graph is not directly compared against the structural masks as in [1], but instead the authors extract a subraph centered around each node and compare those subgraphs against the masks. I guess that this can lead to higher expressive power (the model is more expressive than 1-WL), however, as discussed above, it also increases the computational complexity of the model.\n\n- In the literature of graph kernels, there exist some kernels that can handle graphs whose nodes are annotated with feature vectors such as the GraphHopper kernel [2] or the multiscale laplacian kernel [3]. I wonder why the authors do not employ those kernels and instead resort to vector quantization techniques which lead to loss of information. Perhaps this is due to the computational complexity of those kernels. I would like the authors to comment on that and it would also be nice if the authors could present some experimental results of the proposed model using one of the above kernels on some dataset that contains small graphs.\n\n- The k-means algorithm is run multiple time at each epoch (once per batch). I am not thus sure whether the clustering result of the k-means algorithm is consistent across different batches. The authors initialize the centroids of the algorithm using the centroids of the previous batch. I would suggest the authors perform an experiment and measure the average distance of each centroid from one batch to the next. If those distances are large, this might indicate that the model is unstable.\n\n- The learning process employed in this paper is different from a traditional learning setting since the model samples an edit operation, and it does not directly learn which operation is the best. I feel that such an approach can easily get stuck in local optima. In such a scenario, the masks could be of no practical interest. I would suggest the authors investigate how much the structure of the masks changes during training. The authors could also borrow ideas from the field of discrete optimization, and design some more sophisticated approach for updating the masks.\n\n- The authors perform their ablation study on the MUTAG dataset. This dataset is very small (188 graph in total) and in general, obtained results are very sensitive to fold assignments and potentially to weight initialization. I am not thus sure whether the results of the ablation study are significant and whether they would also apply to other datasets. The authors should consider to use another dataset that contains a larger number of graphs such that the obtained results are more valid.\n\n- Please specify how the representation of the entire graph is produced. Do the authors use a sum aggregator?\n\n- Typos:\n\t- p.2: \"includes methods where\" -> \"include methods where\"\n\t- p.3: \"are assumes\" -> \"are assumed\"\n\t- p.6: \"G_1 = (V_2, E_2)\" -> \"G_2 = (V_2, E_2)\"\n\n[1] Nikolentzos G. and Vazirgiannis M., \"Random Walk Graph Neural Networks\". Advances in Neural Information Processing Systems, pp. 16211-16222, 2020.\\\n[2] Feragen A., Kasenburg N., Petersen J., de Bruijne M. and Borgwardt K.M., \"Scalable kernels for graphs with continuous attributes\". Advances in Neural Information Processing Systems, pp. 216-224, 2013.\\\n[3] Kondor R. and Pan H., \"The multiscale laplacian graph kernel\". Advances in Neural Information Processing Systems, pp. 2990-2998, 2016.", "summary_of_the_paper": "In this paper, the authors propose a model that uses graph kernels to extend the convolution operator to the graph domain. Given a graph, the model extracts a subgraph centered around each node of the graph and generates a representation for that node by comparing its subgraph against a number of structural masks using graph kernels. Since graph kernels are not in general differentiable functions, the authors use a discrete randomized descent strategy to optimize the structural masks. The authors also add a Jensen-Shannon divergence loss term to force the masks provide dissimilar responses from each other. The proposed model was evaluated on standard graph classification datasets where it was found to be competitive with the baselines.", "summary_of_the_review": "Overall, this is an interesting paper which studies a topic that has not been fully explored yet.  Even though the originality of the paper is not stellar, the paper introduces some new ideas. However, there are several issues that the authors need to address (e.g., running time, investigate whether clustering is consistent, ablation study on some other dataset, etc). Furthermore, the empirical results are not bad, but they are also not impressive. Thus, the paper does not seem ready for publication in its current state. ", "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": "W1Gnt4MYiPt", "reviewer": "Reviewer_ovv9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper is well motivated and easy to follow. The authors provide a detailed description of the problem and related works and background.\n\n\nRegarding contribution #1 \"Unlike existing approaches that require embedding the input graph\ninto a larger, relaxed space with a higher likelihood of ending up in a local minimum, our model\nis fully structural\". -- Why is this true? Usually, we would like to have a high dimensional feature space, to capture more abstract features of the input. I am not convinced that remaining in a smaller dimension is more beneficial. Perhaps the authors can elaborate on this point ?\n\nRegarding the second paragraph in the related works section, where diffusion in GNNs is discussed - while the statement is correct, it was also recently shown in \"PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations\" (https://arxiv.org/abs/2108.01938) that not all kind of applications and datasets indeed benefit from diffusion, and at times propagation is favored. I believe that discussion that in the paper will contribute to its content.\n\nAll the experiments consider graph classification, which is indeed an important task. However, it would be interesting to know how the proposed method would work, for instance, for node classification (e.g., Cora, Citeseer). Also, it would be interesting to know if the method can be used for geometric datasets, where a more learned masks may be easier to explain.\n\nIn all experiments, a rather shallow network is considered to my understanding. Either 1,2,3 kernel layers are used, following a classifier. Since oversmoothing is a known phenomenon in typical GCNs, it would be interesting to know if the proposed method can prevent this problem. It may be, that learning the correct masks can aid in feature preservation and distinguishability (this is also related to the diffusion/propagation discussion above and the works cited by the authors).\n\nOverall, the results presented in Table 1 show that in some cases the proposed method outperforms other by quite a small margin, but in most cases it is not better methods.\n\nThe authors state that graph kernels are limited by implementation. While this may be fine, I think that the authors can strengthen their claims by adding some information regarding the run times of their work compared to others.\n\n\n\n\n\n", "summary_of_the_paper": "The authors propose a method that is based on graph kernels to perform graph convolution, which add to the interpretability of GNNs.\nA framework for learning graph kernels is introduced and studied on multiple datasets. The results show improvement in some datasets.", "summary_of_the_review": "The paper is clearly written and motivated but lacks on the experimental side, both in results of current experiments, and also the scope of the experiments is rather limited.", "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": {}}]

Author rebuttal:

Meta-review: The paper uses graph kernels to perform local convolutions and achieve better expressiveness than classical GNNs. The paper received three borderline reviews. The area chair found the feedback to be consistent and constructive and agrees with most statements made by the reviewers. Overall, the idea has some interest (even though there are other works who also propose hybrid approaches between graph kernels and GNNs, as noted in the paper). Nevertheless, there is a lot of room for improvement regarding the experimental validation and the results are not very convincing (yet?). The datasets used in the paper have been traditionally used for evaluating GNNs but they have strong limitations due to their small size and it is often hard to draw conclusions from them. If the method does not suffer from scalablity issues, it is likely that more interesting results could be obtained by using ZINC or MOLHIV datasets, which are larger and often provide statistically significant results.

Overall, these issues may require a major revision and unfortunately, the area chair believes that the paper is not ready for publication.
Decision: Reject