Dexiong Chen

Laurent Jacob

Julien Mairal

Convolutional Kernel Networks for Graph-Structured Data

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Graph kernels are classical tools for representing graphstructured data (see [START_REF] Kriege | A survey on graph kernels[END_REF], for a survey).

Most successful examples represent graphs as very-highdimensional feature vectors that enumerate and count occurences of local graph sub-structures. In order to perform well, a graph kernel should be as expressive as possible, i.e., able to distinguish graphs with different topological properties [START_REF] Kriege | A property testing framework for the theoretical expressivity of graph kernels[END_REF], while admitting polynomialtime algorithms for its evaluation. Common sub-structures include walks [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF], shortest paths [START_REF] Borgwardt | Protein function prediction via graph kernels[END_REF], subtrees [START_REF] Shervashidze | Weisfeiler-Lehman graph kernels[END_REF], or graphlets [START_REF] Shervashidze | Convolutional Kernel Networks for Graph-Structured Data[END_REF].

Proceedings of the 37 th International Conference on Machine Learning, Vienna, Austria, PMLR 119, 2020. Copyright 2020 by the author(s).

Graph kernels have shown to be expressive enough to yield good empirical results, but decouple data representation and model learning. In order to obtain task-adaptive representations, another line of research based on neural networks has been developed recently [START_REF] Niepert | Learning convolutional neural networks for graphs[END_REF][START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF][START_REF] Xu | How powerful are graph neural networks[END_REF][START_REF] Verma | Feastnet: Featuresteered graph convolutions for 3d shape analysis[END_REF]. The resulting tools, called graph neural networks (GNNs), are conceptually similar to convolutional neural networks (CNNs) for images; they provide graph-structured multilayer models, where each layer operates on the previous layer by aggregating local neighbor information. Even though harder to regularize than kernel methods, these models are trained end-to-end and are able to extract features adapted to a specific task. In a recent work, [START_REF] Xu | How powerful are graph neural networks[END_REF] have shown that the class of GNNs based on neighborhood aggregation is at most as powerful as the Weisfeiler-Lehman (WL) graph isomorphism test, on which the WL kernel is based [START_REF] Shervashidze | Weisfeiler-Lehman graph kernels[END_REF], and other types of network architectures than simple neighborhood aggregation are needed for more powerful features.

Since GNNs and kernel methods seem to benefit from different characteristics, several links have been drawn between both worlds in the context of graph modeling. For instance, [START_REF] Lei | Deriving neural architectures from sequence and graph kernels[END_REF] introduce a class of GNNs whose output lives in the reproducing kernel Hilbert space (RKHS) of a WL kernel. In this line of research, the kernel framework is essentially used to design the architecture of the GNN since the final model is trained as a classical neural network. This is also the approach used by Zhang et al. (2018a) and [START_REF] Morris | go neural: Higher-order graph neural networks[END_REF]. By contrast, [START_REF] Du | Graph neural tangent kernel: Fusing graph neural networks with graph kernels[END_REF] adopt an opposite strategy and leverage a GNN architecture to design new graph kernels, which are equivalent to infinitely-wide GNNs initialized with random weights and trained with gradient descent. Other attempts to merge neural networks and graph kernels involve using the metric induced by graph kernels to initialize a GNN [START_REF] Navarin | Pre-training graph neural networks with kernels[END_REF], or using graph kernels to obtain continuous embeddings that are plugged to neural networks [START_REF] Nikolentzos | Kernel graph convolutional neural networks[END_REF].

In this paper, we go a step further in bridging graph neural networks and kernel methods by proposing an explicit multilayer kernel representation, which can be used either as a traditional kernel method, or trained end-to-end as a GNN when enough labeled data are available. The multilayer construction allows to compute a series of maps which account for local sub-structures ("receptive fields") of increasing size. The graph representation is obtained by pooling the final representations of its nodes. The resulting kernel extends to graph-structured data the concept of convolutional kernel networks (CKNs), which was originally designed for images and sequences [START_REF] Mairal | End-to-end kernel learning with supervised convolutional kernel networks[END_REF]Chen et al., 2019a). As our representation of nodes is built by iteratively aggregating representations of their outgoing paths, our model can also be seen as a multilayer extension of path kernels. Relying on paths rather than neighbors for the aggregation step makes our approach more expressive than the GNNs considered in [START_REF] Xu | How powerful are graph neural networks[END_REF], which implicitly rely on walks and whose power cannot exceed the Weisfeiler-Lehman (WL) graph isomorphism test. Even with medium/small path lengths (which leads to reasonable computational complexity in practice), we show that the resulting representation outperforms walk or WL kernels.

Our model called graph convolutional kernel network (GCKN) relies on the successive uses of the Nyström method [START_REF] Williams | Using the Nyström method to speed up kernel machines[END_REF] to approximate the feature map at each layer, which makes our approach scalable. GCKNs can then be interpreted as a new type of graph neural network whose filters may be learned without supervision, by following kernel approximation principles. Such unsupervised graph representation is known to be particularly effective when small amounts of labeled data are available. Similar to CKNs, our model can also be trained end-to-end, as a GNN, leading to task-adaptive representations, with a computational complexity similar to that of a GNN when the path lengths are small enough.

Notation.

A graph G is defined as a triplet (V, E, a), where V is the set of vertices, E is the set of edges, and a : V → Σ is a function that assigns attributes, either discrete or continous, from a set Σ to nodes in the graph. A path is a sequence of distinct vertices linked by edges and we denote by P(G) and P k (G) the set of paths and paths of length k in G, respectively. In particular, P 0 (G) is reduced to V. We also denote by P k (G, u) ⊂ P k (G) the set of paths of length k starting from u in V. For any path p in P(G), we denote by a(p) in Σ |p|+1 the concatenation of node attributes in this path. We replace P with W to denote the corresponding sets of walks by allowing repeated nodes.

Related Work on Graph Kernels

Graph kernels were originally introduced by [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF] and [START_REF] Kashima | Marginalized kernels between labeled graphs[END_REF], and have been the subject of intense research during the last twenty years (see the reviews of [START_REF] Vishwanathan | Graph kernels[END_REF][START_REF] Kriege | A survey on graph kernels[END_REF].

In this paper, we consider graph kernels that represent a graph as a feature vector counting the number of occurrences of some local connected sub-structure. Enumerat-ing common local sub-structures between two graphs is unfortunately often intractable; for instance, enumerating common subgraphs or common paths is known to be NPhard [START_REF] Gärtner | On graph kernels: Hardness results and efficient alternatives[END_REF]. For this reason, the literature on graph kernels has focused on alternative structures allowing for polynomial-time algorithms, e.g., walks.

More specifically, we consider graph kernels that perform pairwise comparisons between local sub-structures centered at every node. Given two graphs G = (V, E, a) and G = (V , E , a ), we consider the kernel

K(G, G ) = u∈V u ∈V κ base (l G (u), l G (u )), (1)
where the base kernel κ base compares a set of local patterns centered at nodes u and u , denoted by l G (u) and l G (u ), respectively. For simplicity, we will omit the notation l G (u) in the rest of the paper, and the base kernel will be simply written κ base (u, u ) with an abuse of notation. As noted by [START_REF] Lei | Deriving neural architectures from sequence and graph kernels[END_REF]; [START_REF] Kriege | A survey on graph kernels[END_REF], this class of kernels covers most of the examples mentioned in the introduction.

Walks and path kernels. Since computing all path cooccurences between graphs is NP-hard, it is possible instead to consider paths of length k, which can be reasonably enumerated if k is small enough, or the graphs are sparse. Then, we may define the kernel

K (k)
path as (1) with

κ base (u, u ) = p∈P k (G,u) p ∈P k (G ,u ) δ(a(p), a (p )), (2)
where a(p) represents the attributes for path p in G, and δ is the Dirac kernel such that δ(a(p), a (p )) = 1 if a(p) = a (p ) and 0 otherwise.

It is also possible to define a variant that enumerates all paths up to length k, by simply adding the kernels

K (i) path : K path (G, G ) = k i=0 K (i) path (G, G ). (3)
Similarly, one may also consider using walks by simply replacing the notation P by W in the previous definitions.

Weisfeiler-Lehman subtree kernels. A subtree is a subgraph with a tree structure. It can be extended to subtree patterns [START_REF] Shervashidze | Weisfeiler-Lehman graph kernels[END_REF][START_REF] Bach | Graph kernels between point clouds[END_REF] by allowing nodes to be repeated, just as the notion of walks extends that of paths. All previous subtree kernels compare subtree patterns instead of subtrees. Among them, the Weisfeiler-Lehman (WL) subtree kernel is one of the most widely used graph kernels to capture such patterns. It is essentially based on a mechanism to augment node attributes by iteratively aggregating and hashing the attributes of each node's neighborhoods. After i iterations, we denote by a i the new node attributes for graph G = (V, E, a), which is defined in Algorithm 1 of [START_REF] Shervashidze | Weisfeiler-Lehman graph kernels[END_REF] and then the WL subtree kernel after k iterations is defined, for two graphs G = (V, E, a) and G = (V , E , a ), as

K W L (G, G ) = k i=0 K (i) subtree (G, G ), (4)
where

K (i) subtree (G, G ) = u∈V u ∈V κ (i) subtree (u, u ), (5)
with

κ (i) subtree (u, u ) = δ(a i (u), a i (u ))
and the attributes a i (u) capture subtree patterns of depth i rooted at node u.

Graph Convolutional Kernel Networks

In this section, we introduce our model, which builds upon the concept of graph-structured feature maps, following the terminology of convolutional neural networks.

Definition 1 (Graph feature map). Given a graph G = (V, E, a) and a RKHS H, a graph feature map is a mapping ϕ : V → H, which associates to every node a point in H representing information about local graph substructures.

We note that the definition matches that of convolutional kernel networks [START_REF] Mairal | End-to-end kernel learning with supervised convolutional kernel networks[END_REF] when the graph is a twodimensional grid. Generally, the map ϕ depends on the graph G, and can be seen as a collection of |V| elements of H describing its nodes. The kernel associated to the feature maps ϕ, ϕ for two graphs G, G , is defined as

K(G, G ) = u∈V u ∈V ϕ(u), ϕ (u ) H = Φ(G), Φ(G ) H , (6) with Φ(G) = u∈V ϕ(u) and Φ(G ) = u∈V ϕ (u). (7)
The RKHS of K can be characterized by using Theorem 2 in Appendix A. It is the space of functions f z : G → z, Φ(G) H for all z in H endowed with a particular norm.

Note that even though graph feature maps ϕ, ϕ are graphdependent, learning with K is possible as long as they all map nodes to the same RKHS H-as Φ will then also map all graphs to the same space H. We now detail the full construction of the kernel, starting with a single layer.

Single-Layer Construction of the Feature Map

We propose a single-layer model corresponding to a continuous relaxation of the path kernel. We assume that the input attributes a(u) live in R q0 , such that a graph G = (V, E, a) admits a graph feature map ϕ 0 : V → H 0 with H 0 = R q0 and ϕ 0 (u) = a(u). Note that this assumption also allows us to handle discrete labels by using a one-hot encoding strategy-that is e.g., four labels {A, B, C, D} are represented by four-dimensional vectors (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), respectively.

Continuous relaxation of the path kernel. We rely on paths of length k, and introduce the kernel K 1 for graphs G, G with feature maps ϕ 0 , ϕ 0 of the form (1) with

κ base (u, u ) = p∈P k (G,u) p ∈P k (G ,u ) κ 1 (ϕ 0 (p), ϕ 0 (p )), (8) where ϕ 0 (p) = [ϕ 0 (p i )] k
i=0 denotes the concatenation of k + 1 attributes along path p, which is an element of H k+1 0 , p i is the i-th node on path p starting from index 0, and κ 1 is a Gaussian kernel comparing such attributes:

κ 1 (ϕ 0 (p), ϕ 0 (p )) = e -α 1 2 k i=0 ϕ0(pi)-ϕ 0 (p i ) 2 H 0 . (9)
This is an extension of the path kernel, obtained by replacing the hard matching function δ in (2) by κ 1 , as done for instance by [START_REF] Togninalli | Wasserstein Weisfeiler-Lehman graph kernels[END_REF] for the WL kernel. This replacement not only allows us to use continuous attributes, but also has important consequences in the discrete case since it allows to perform inexact matching between paths. For instance, when the graph is a chain with discrete attributes-in other words, a string-then, paths are simply k-mers, and the path kernel (with matching function δ) becomes the spectrum kernel for sequences [START_REF] Leslie | The spectrum kernel: A string kernel for svm protein classification[END_REF]. By using κ 1 instead, we obtain the single-layer CKN kernel of Chen et al. (2019a), which performs inexact matching, as the mismatch kernel does [START_REF] Leslie | Mismatch string kernels for discriminative protein classification[END_REF], and leads to better performances in many tasks involving biological sequences.

From graph feature map ϕ 0 to graph feature map ϕ 1 . The kernel κ 1 acts on pairs of paths in potentially different graphs, but only through their mappings to the same space H k+1 0 . Since κ 1 is positive definite, we denote by H 1 its RKHS and consider its mapping φ path

1 : H k+1 0 → H 1 such that κ 1 (ϕ 0 (p), ϕ 0 (p )) = φ path 1 (ϕ 0 (p)) , φ path 1 (ϕ 0 (p )) H1 .
For any graph G, we can now define a graph feature map

ϕ 1 : V → H 1 , operating on nodes u in V, as ϕ 1 (u) = p∈P k (G,u) φ path 1 (ϕ 0 (p)) . (10)
Then, the continuous relaxation of the path kernel, denoted by K 1 (G, G ), can also be written as ( 6) with ϕ = ϕ 1 , and its underlying kernel representation Φ 1 is given by ( 7). The construction of ϕ 1 from ϕ 0 is illustrated in Figure 1.

u ϕ j (u) ∈ H j (V, E, ϕ j : V → H j ) path extraction kernel mapping path aggregation u u ϕ j+1 (u) ∈ H j+1 u u u p 1 p 2 p 3 φ path j+1 (ϕ j (p 1 )) φ path j+1 (ϕ j (p 2 )) φ path j+1 (ϕ j (p 3 ))
kernel mapping

H j+1 path aggregation ϕ j+1 (u) := φ path j+1 (ϕ j (p 1 )) + φ path j+1 (ϕ j (p 2 )) + φ path j+1 (ϕ j (p 3 )) (V, E, ϕ j+1 : V → H j+1 )
Figure 1. Construction of the graph feature map ϕj+1 from ϕj given a graph (V, E). The first step extracts paths of length k (here colored by red, blue and green) from node u, then (on the right panel) maps them to a RKHS Hj+1 via the Gaussian kernel mapping. The new map ϕj+1 at u is obtained by local path aggregation (pooling) of their representations in Hj+1. The representations for other nodes can be obtained in the same way. In practice, such a model is implemented by using finite-dimensional embeddings approximating the feature maps, see Section 3.2.

The graph feature map ϕ 0 maps a node (resp a path) to H 0 (resp H k+1 0

) which is typically a Euclidean space describing its attributes. By contrast, φ path 1 is the kernel mapping of the Gaussian kernel κ 1 , and maps each path p to a Gaussian function centered at ϕ 0 (p)-remember indeed that for kernel function K : X ×X → R with RKHS H, the kernel mapping is of a data point x is the function K(x, .) : X → R. Finally, ϕ 1 maps each node u to a mixture of Gaussians, each Gaussian function corresponding to a path starting at u.

Concrete Implementation and GCKNs

We now discuss algorithmic aspects, leading to the graph convolutional kernel network (GCKN) model, which consists in building a finite-dimensional embedding Ψ(G) that may be used in various learning tasks without scalability issues. We start here with the single-layer case.

The Nyström method and the single-layer model. A naive computation of the path kernel K 1 requires comparing all pairs of paths in each pair of graphs. To gain scalability, a key component of the CKN model is the Nyström method [START_REF] Williams | Using the Nyström method to speed up kernel machines[END_REF], which computes finitedimensional approximate kernel embeddings. We discuss here the use of such a technique to define finite-dimensional maps ψ 1 : V → R q1 and ψ 1 : V → R q1 for graphs G, G such that for all pairs of nodes u, u in V, V , respectively,

ϕ 1 (u), ϕ 1 (u ) H1 ≈ ψ 1 (u), ψ 1 (u ) R q 1 .
The consequence of such an approximation is that it provides a finite-dimensional approximation Ψ 1 of Φ 1 :

K 1 (G, G ) ≈ Ψ 1 (G), Ψ 1 (G ) R q 1 with Ψ 1 (G) = u∈V ψ 1 (u).
Then, a supervised learning problem with kernel K 1 on a dataset (G i , y i ) i=1,...,n , where y i are labels in R, can be solved by minimizing the regularized empirical risk

min w∈R q 1 n i=1 L(y i , Ψ 1 (G i ), w ) + λ w 2 , ( 11
)
where L is a convex loss function. Next, we show that using the Nyström method to approximate the kernel κ 1 yields a new type of GNN, represented by Ψ 1 (G), whose filters can be obtained without supervision, or, as discussed later, with back-propagation in a task-adaptive manner.

Specifically, the Nyström method projects points from a given RKHS onto a finite-dimensional subspace and performs all subsequent operations within that subspace. In the context of κ 1 , whose RKHS is H 1 with mapping function φ path 1 , we consider a collection Z = {z 1 , . . . , z q1 } of q 1 prototype paths represented by attributes in H k+1 0 , and we define the subspace E 1 = Span(φ path 1 (z 1 ), . . . , φ path 1 (z q1 )). Given a new path with attributes z, it is then possible to show (see Chen et al., 2019a) that the projection of path attributes z onto E 1 leads to the q 1 -dimensional mapping

ψ path 1 (z) = [κ 1 (z i , z j )] -1 2 ij [κ 1 (z 1 , z), . . . , κ 1 (z q1 , z)] ,
where [κ 1 (z i , z j )] ij is a q 1 × q 1 Gram matrix. Then, the approximate graph feature map ψ 1 is obtained by pooling

ψ 1 (u) = p∈P k (G,u) ψ path 1 (ψ 0 (p)) for all u ∈ V,
where

ψ 0 = ϕ 0 and ψ 0 (p) = [ψ 0 (p i )] i=0,...,k in R q0(k+1)
represents the attributes of path p, with an abuse of notation.

Interpretation as a GNN. When input attributes ψ 0 (u) have unit-norm, which is the case if we use one-hot encoding on discrete attributes, the Gaussian kernel κ 1 between two path attributes z, z in R q0(k+1) may be written

κ 1 (z, z ) = e -α 1 2 z-z 2 = e α1(z z -k-1) = σ 1 (z z ), (12)
which is a dot-product kernel with a non-linear function σ 1 . Then, calling Z in R q0(k+1)×q1 the matrix of prototype path attributes, we have

ψ 1 (u) = p∈P k (G,u) σ 1 (Z Z) -1 2 σ 1 (Z ψ 0 (p)), (13)
where, with an abuse of notation, the non-linear function σ 1 is applied pointwise. Then, the map ψ 1 is build from ψ 0 with the following steps (i) feature aggregation along the paths, (ii) encoding of the paths with a linear operation followed by point-wise non-linearity, (iii) multiplication by the q 1 × q 1 matrix σ 1 (Z Z) -1 2 , and (iv) linear pooling. The major difference with a classical GNN is that the "filtering" operation may be interpreted as an orthogonal projection onto a linear subspace, due to the matrix σ 1 (Z Z) -1 2 . Unlike the Dirac function, the exponential function σ 1 is differentiable. A useful consequence is the possibility of optimizing the filters Z with back-propagation as detailed below. Note that in practice we add a small regularization term to the diagonal for stability reason:

(σ 1 (Z Z) + εI) -1 2 with ε = 0.01.
Learning without supervision. Learning the "filters" Z with Nyström can be achieved by simply running a Kmeans algorithm on path attributes extracted from training data [START_REF] Zhang | Improved Nyström low-rank approximation and error analysis[END_REF]. This is the approach adopted for CKNs by [START_REF] Mairal | End-to-end kernel learning with supervised convolutional kernel networks[END_REF]; Chen et al. (2019a), which proved to be very effective as shown in the experimental section.

End-to-end learning with back-propagation. While the previous unsupervised learning strategy consists in finding a good kernel approximation that is independent of labels, it is also possible to learn the parameters Z end-to-end, by minimizing (11) jointly with respect to Z and w. The main observations from Chen et al. (2019a) in the context of biological Algorithm 1 Forward pass for multilayer GCKN

1: Input: graph G = (V, E, ψ 0 : V → R q0
), set of anchor points (filters) Z j ∈ R (k+1)qj-1×qj for j = 1, . . . , J. 2: for j = 1, . . . , J do 3:

for u in V do 4: ψ j (u) = p∈P k (G,u) ψ path j (ψ j-1 (p)); 5:
end for 6: end for 7: Global pooling:

Ψ(G) = u∈V ψ J (u);
sequences is that such a supervised learning approach may yield good models with much fewer filters q 1 than with the unsupervised learning strategy. We refer the reader to Chen et al. (2019a;b) for how to perform back-propagation with the inverse square root matrix σ 1 (Z Z) -1 2 .

Complexity. The complexity for computing the feature map ψ 1 is dominated by the complexity of finding all the paths of length k from each node. This can be done by simply using a depth first search algorithm, whose worstcase complexity for each graph is O(|V|d k ), where d is the maximum degree of each node, meaning that large k may be used only for sparse graphs. Then, each path is encoded in O(q 1 q 0 (k + 1)) operations; When learning with back-propagation, each gradient step requires computing the eigenvalue decomposition of σ 1 (Z Z) -1 2 whose complexity is O(q 3 1 ), which is not a computational bottleneck when using mini-batches of order O(q 1 ), where typical practical values for q 1 are reasonably small, e.g., less than 128.

Multilayer Extensions

The mechanism to build the feature map ϕ 1 from ϕ 0 can be iterated, as illustrated in Figure 1 which shows how to build a feature map ϕ j+1 from a previous one ϕ j . As discussed by [START_REF] Mairal | End-to-end kernel learning with supervised convolutional kernel networks[END_REF] for CKNs, the Nyström method may then be extended to build a sequence of finite-dimensional maps ψ 0 , . . . , ψ J , and the final graph representation is given by

Ψ J (G) = u∈V ψ J (u). ( 14
)
The computation of Ψ J (G) is illustrated in Algorithm 1.

Here we discuss two possible uses for these additional layers, either to account for more complex structures than paths, or to extend the receptive field of the representation without resorting to the enumeration of long paths.We will denote by k j the path length used at layer j.

A simple two-layer model to account for subtrees. As emphasized in (7), GCKN relies on a representation Φ(G) of graphs, which is a sum of node-level representations provided by a graph feature map ϕ. If ϕ is a sum over paths starting at the represented node, Φ(G) can simply be written as a sum over all paths in G, consistently with our observation that (6) recovers the path kernel when using a Dirac kernel to compare paths in κ 1 . The path kernel often leads to good performances, but it is also blind to more complex structures. Figure 2 provides a simple example of this phenomenon, using k = 1: G 1 and G 3 differ by a single edge, while G 4 has a different set of nodes and a rather different structure.

Yet P 1 (G 3 ) = P 1 (G 4 ), making K 1 (G 1 , G 3 ) = K 1 (G 1 , G 4 ) for the path kernel. 1 2 3 4 (G 1 ) 1 2 3 4 (G 2 ) 1 2 3 4 (G 3 ) 1 2 3 4 1 3 (G 4 ) K 2 (G 1 , G 2 ) = 0 K 1 (G 1 , G 2 ) > 0 K 2 (G 1 , G 3 ) > K 2 (G 1 , G 4 ) K 1 (G 1 , G 3 ) = K 1 (G 1 , G 4 ) Figure 2.
Example cases using κ1 = κ2 = δ, with path lengths k1 = 1 and k2 = 0; The one-layer kernel K1 counts the number of common edges while the two-layer K2 counts the number of nodes with the same set of outgoing edges. The figure suggests using K1 + K2 to gain expressiveness.

Expressing more complex structures requires breaking the succession of linearities introduced in ( 7) and (10)-much like pointwise nonlinearities are used in neural networks. Concretely, this effect can simply be obtained by using a second layer with path length k 2 = 0-paths are then identified to vertices-which produces the feature map ϕ 2 (u) = φ path 2 (ϕ 1 (u)), where φ path 2 : H 1 → H 2 is a nonlinear kernel mapping. The resulting kernel is then

K 2 (G, G ) = u∈V u ∈V ϕ 2 (u), ϕ 2 (u ) H2 = u∈V u ∈V κ 2 (ϕ 1 (u), ϕ 1 (u )). ( 15
)
When κ 1 and κ 2 are both Dirac kernels, K 2 counts the number of nodes in G and G with the exact same set of outgoing paths P(G, u), as illustrated in Figure 2.

Theorem 1 further illustrates the effect of using a nonlinear φ path 2 on the feature map ϕ 1 , by formally linking the walk and WL subtree kernel through our framework. Theorem 1. Let G = (V, E), G = (V , E ), M be the set of exact matchings of subsets of the neighborhoods of two nodes, as defined in [START_REF] Shervashidze | Weisfeiler-Lehman graph kernels[END_REF], and ϕ defined as in (10) with κ 1 = δ and replacing paths by walks. For any u ∈ V and u ∈ V such that |M(u, u

)| = 1, δ(ϕ 1 (u), ϕ 1 (u )) = κ (k) subtree (u, u ). ( 16
)
Recall that when using (8) with walks instead of paths and a Dirac kernel for κ 1 , the kernel (6) with ϕ = ϕ 1 is the walk kernel. The condition |M(u, u )| = 1 indicates that u and u have the same degrees and each of them has distinct neighbors. This can be always ensured by including degree information and adding noise to node attributes. For a large class of graphs, both the walk and WL subtree kernels can therefore be written as ( 6) with the same first layer ϕ 1 representing nodes by their walk histogram. While walk kernels use a single layer, WL subtree kernels rely on a second layer ϕ 2 mapping nodes to the indicator function of ϕ 1 (u).

Theorem 1 also shows that the kernel built in ( 15) is a pathbased version of WL subtree kernels, therefore more expressive as it captures subtrees rather than subtree patterns. However, the Dirac kernel lacks flexibility, as it only accounts for pairs of nodes with identical P(G, u). For example, in Figure 2, K 2 (G 1 , G 2 ) = 0 even though G 1 only differs from G 2 by two edges, because these two edges belong to the set P(G, u) of all nodes in the graph. In order to retain the stratification by node of (15) while allowing for a softer comparison between sets of outgoing paths, we replace δ by the kernel κ 2 (ϕ 1 (u), ϕ 1 (u )) = e -α2 ϕ1(u)-ϕ 1 (u ) 2 H 1 . Large values of α 2 recover the behavior of the Dirac, while smaller values gives non-zero values for similar P(G, u).

A multilayer model to account for longer paths. In the previous paragraph, we have seen that adding a second layer could bring some benefits in terms of expressiveness, even when using path lengths k 2 = 0. Yet, a major limitation of this model is the exponential complexity of path enumeration, which is required to compute the feature map ϕ 1 , preventing us to use large values of k as soon as the graph is dense. Representing large receptive fields while relying on path enumerations with small k, e.g., k ≤ 3, is nevertheless possible with a multilayer model. To account for a receptive field of size k, the previous model requires a path enumeration with complexity O(|V|d k ), whereas the complexity of a multilayer model is linear in k.

Practical Variants

Summing the kernels for different k and different scales. As noted in Section 2, summing the kernels corresponding to different values of k provides a richer representation. We also adopt such a strategy, which corresponds to concatenating the feature vectors Ψ(G) obtained for various path lengths k. When considering a multilayer model, it is also possible to concatenate the feature representations obtained at every layer j, allowing to obtain a multi-scale feature representation of the graph and gain expressiveness.

Use of homogeneous dot-product kernel. Instead of the Gaussian kernel (9), it is possible to use a homogeneous dot-product kernel, as suggested by [START_REF] Mairal | End-to-end kernel learning with supervised convolutional kernel networks[END_REF] for CKNs:

κ 1 (z, z ) = z z σ 1 z, z z z ,
where σ 1 is defined in (12). Note that when z, z have unitnorm, we recover the Gaussian kernel (9). In our paper, we use such a kernel for upper layers, or for continuous input attributes when they do not have unit norm. For multilayer models, this homogenization is useful for preventing vanishing or exponentially growing representations. Note that ReLU is also a homogeneous non-linear mapping.

Other types of pooling operations. Another variant consists in replacing the sum pooling operation in ( 13) and ( 14) by a mean or a max pooling. While using max pooling as a heuristic seems to be effective on some datasets, it is hard to justify from a RKHS point of view since max operations typically do not yield positive definite kernels. Yet, such a heuristic is widely adopted in the kernel literature, e.g., for string alignment kernels [START_REF] Saigo | Protein homology detection using string alignment kernels[END_REF]. In order to solve such a discrepancy between theory and practice, Chen et al. (2019b) propose to use the generalized max pooling operator of [START_REF] Murray | Generalized max pooling[END_REF], which is compatible with the RKHS point of view. Applying the same ideas to GCKNs is straightforward.

Using walk kernel instead of path kernel. One can use a relaxed walk kernel instead of the path kernel in (8), at the cost of losing some expressiveness but gaining some time complexity. Indeed, there exists a very efficient recursive way to enumerate walks and thus to compute the resulting approximate feature map in (13) for the walk kernel. Specifically, if we denote the k-walk kernel by κ

(k)
walk , then its value between two nodes can be decomposed as the product of the 0-walk kernel between the nodes and the sum of the (k -1)-walk kernel between their neighbors

κ (k) walk (u, u ) = κ (0) walk (u, u ) v∈N (u) v ∈N (u ) κ (k-1) walk (v, v ),
where κ (0) walk (u, u ) = κ 1 (ϕ 0 (u), ϕ 0 (u )). After applying the Nyström method, the approximate feature map of the walk kernel is written, similar to (13), as

ψ 1 (u) = σ 1 (Z Z) -1 2 p∈W k (G,u) σ 1 (Z ψ 0 (p)) c k (u):= .
Based on the above observation and following similar induction arguments as Chen et al. (2019b), it is not hard to show that (c j (u)) j=1,...,k obeys the following recursion

c j (u) = b j (u) v∈N (u) c j-1 (v), 1 ≤ j ≤ k,
where denotes the element-wise product and b j (u) is a vector in R q1 whose entry i in {1, . . . , q 1 } is κ 1 (u, z (k+1-j) i

) and z (k+1-j) i denotes the k + 1j-th column vector of z i in R q0 . More details can be found in Appendix C.

Model Interpretation

Ying et al. ( 2019) introduced an approach to interpret trained GNN models, by finding a subgraph of an input graph G maximizing the mutual information with its predicted label (note that this approach depends on a specific input graph). We show here how to adapt similar ideas to our framework.

Interpreting GCKN-path and GCKN-subtree. We call GCKN-path our model Ψ 1 with a single layer, and GCKNsubtree our model Ψ 2 with two layers but with k 2 = 0, which is the first model presented in Section 3.3 that accounts for subtree structures. As these models are built upon path enumeration, we extend the method of [START_REF] Ying | Generating explanations for graph neural networks[END_REF] by identifying a small subset of paths in an input graph G preserving the prediction. We then reconstruct a subgraph by merging the selected paths. For simplicity, let us consider a one-layer model. As Ψ 1 (G) only depends on G through its set of paths P k (G), we note Ψ 1 (P) with an abuse of notation for any subset of P of paths in G, to emphasize the dependency in this set of paths. For a trained model (Ψ 1 , w) and a graph G, our objective is to solve

min P ⊆P k (G) L(ŷ, Ψ 1 (P ), w ) + µ|P |, ( 17
)
where ŷ is the predicted label of G and µ a regularization parameter controlling the number of paths to select. This problem is combinatorial and can be computationally intractable when P(G) is large. Following [START_REF] Ying | Generating explanations for graph neural networks[END_REF], we relax it by using a mask M with values in [0; 1] over the set of paths, and replace the number of paths |P | by the 1 -norm of M , which is known to have a sparsity-inducing effect [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]. The problem then becomes

min M ∈[0;1] |P k (G)| L(ŷ, Ψ 1 (P k (G) M ), w )+µ M 1 , ( 18
)
where P k (G) M denotes the use of M (p)a(p) instead of a(p) in the computation of Ψ 1 for all p in P k (G). Even though the problem is non-convex due to the non-linear mapping Ψ 1 , it may still be solved approximately by using projected gradient-based optimization techniques.

Interpreting multilayer models. By noting that Ψ j (G) only depends on the union of the set of paths P k l (G), for all layers l ≤ j, we introduce a collection of masks M l at each layer, and then optimize the same objective as ( 18) over all masks (M l ) l=1,...,j , with the regularization j l=1 M l 1 .

Experiments

We evaluate GCKN and compare its variants to state-ofthe-art methods, including GNNs and graph kernels, on several real-world graph classification datasets, involving either discrete or continuous attributes.

Implementation Details

We follow the same protocols as [START_REF] Du | Graph neural tangent kernel: Fusing graph neural networks with graph kernels[END_REF][START_REF] Xu | How powerful are graph neural networks[END_REF], and report the average accuracy and standard deviation over a 10-fold cross validation on each dataset. We use the same data splits as [START_REF] Xu | How powerful are graph neural networks[END_REF], using their code. Note that performing nested 10-fold cross validation would have provided better estimates of test accuracy for all models, but it would have unfortunately required 10 times more computation, which we could not afford for many of the baselines we considered.

Considered models. We consider two single-layer models called GCKN-walk and GCKN-path, corresponding to the continuous relaxation of the walk and path kernels respectively. We also consider the two-layer model GCKNsubtree introduced in Section 3.3 with path length k 2 = 0, which accounts for subtrees. Finally, we consider a 3-layer model GCKN-3layers with path length k 2 = 2 (which enumerates paths with three vertices for the second layer), and k 3 = 0, which introduces a non-linear mapping before global pooling, as in GCKN-subtree. We use the same parameters α j and q j (number of filters) across layers. Our comparisons include state-of-the-art graph kernels such as WL kernel [START_REF] Shervashidze | Weisfeiler-Lehman graph kernels[END_REF], AWL [START_REF] Ivanov | Anonymous walk embeddings[END_REF], RetGK (Zhang et al., 2018b), GNTK [START_REF] Du | Graph neural tangent kernel: Fusing graph neural networks with graph kernels[END_REF], WWL [START_REF] Togninalli | Wasserstein Weisfeiler-Lehman graph kernels[END_REF] and recent GNNs including GCN [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF], PatchySAN [START_REF] Niepert | Learning convolutional neural networks for graphs[END_REF] and GIN [START_REF] Xu | How powerful are graph neural networks[END_REF]. We also include a simple baseline method LDP [START_REF] Cai | A simple yet effective baseline for non-attributed graph classification[END_REF] based on node degree information and a Gaussian SVM.

Learning unsupervised models. Following [START_REF] Mairal | End-to-end kernel learning with supervised convolutional kernel networks[END_REF], we learn the anchor points Z j for each layer by K-means over 300000 extracted paths from each training fold. The resulting graph representations are then mean-centered, standardized, and used within a linear SVM classifier (11) with squared hinge loss. In practice, we use the SVM implementation of the Cyanure toolbox (Mairal, 2019).1 For each 10-fold cross validation, we tune the bandwidth of the Gaussian kernel (identical for all layers), pooling operation (local (13) or global ( 14)), path size k 1 at the first layer, number of filters (identical for all layers) and regularization parameter λ in (11). More details are provided in Appendix B, as well as a study of the model robustness to hyperparameters.

Learning supervised models. Following [START_REF] Xu | How powerful are graph neural networks[END_REF], we use an Adam optimizer [START_REF] Kingma | A method for stochastic optimization[END_REF] with the initial learning rate equal to 0.01 and halved every 50 epochs, and fix the batch size to 32. We use the unsupervised model based described above for initialization. We select the best model based on the same hyperparameters as for unsupervised models, with the number of epochs as an additional hyperparameter as used in [START_REF] Xu | How powerful are graph neural networks[END_REF]. Note that we do not use DropOut or batch normalization, which are typically used in GNNs such as [START_REF] Xu | How powerful are graph neural networks[END_REF]. Importantly, the number of filters needed for supervised models is always much smaller (e.g., 32 vs 512) than that for unsupervised models to achieve comparable performance.

Results

Graphs with categorical node labels We use the same benchmark datasets as in [START_REF] Du | Graph neural tangent kernel: Fusing graph neural networks with graph kernels[END_REF], including 4 biochemical datasets MUTAG, PROTEINS, PTC and NCI1 and 3 social network datasets IMDB-B, IMDB-MULTI and COLLAB. All the biochemical datasets have categorical node labels while none of the social network datasets has node features. We use degrees as node labels for these datasets, following the protocols of previous works [START_REF] Du | Graph neural tangent kernel: Fusing graph neural networks with graph kernels[END_REF][START_REF] Xu | How powerful are graph neural networks[END_REF][START_REF] Togninalli | Wasserstein Weisfeiler-Lehman graph kernels[END_REF]. Similarly, we also transform all the categorical node labels to one-hot representations. The results are reported in Table 1. With a few exceptions, GCKN-walk has a small edge on graph kernels and GNNs-both implicitly relying on walks too-probably because of the soft structure comparison allowed by the Gaussian kernel. GCKN-path often brings some further improvement, which can be explained by its increasing the expressivity. Both multilayer GCKNs bring a stronger increase, whereas supervising the filter learning of GCKN-subtree does not help. Yet, the number of filters selected by GCKN-subtree-sup is smaller than GCKN-subtreeunsup (see Appendix B), allowing for faster classification at test time. GCKN-3layers-unsup performs in the same ballpark as GCKN-subtree-unsup, but benefits from lower complexity due to smaller path length k 1 .

Graphs with continuous node attributes We use 4 realworld graph classification datasets with continuous node attributes: ENZYMES, PROTEINS full, BZR, COX2. All datasets and size information about the graphs can be found in [START_REF] Kersting | Benchmark data sets for graph kernels[END_REF]. The node attributes are preprocessed with standardization as in [START_REF] Togninalli | Wasserstein Weisfeiler-Lehman graph kernels[END_REF]. To make a fair comparison, we follow the same protocol as used in [START_REF] Togninalli | Wasserstein Weisfeiler-Lehman graph kernels[END_REF]. Specifically, we perform 10 different 10-fold cross validations, using the same hyperparameters that give the best average validation accuracy. The hyperparameter search grids remain the same as for training graphs with categorical node labels. The results are shown in Table 2. They are comparable to the Table 1. Classification accuracies on graphs with discrete node attributes. The accuracies of other models are taken from [START_REF] Du | Graph neural tangent kernel: Fusing graph neural networks with graph kernels[END_REF] except LDP, which we evaluate on our splits and for which we tune bin size, the regularization parameter in the SVM and Gaussian kernel bandwidth. Note that RetGK uses a different protocol, performing 10-fold cross-validation 10 times and reporting the average accuracy. WL subtree 90.4 ± 5.7 75.0 ± 3.1 59.9 ± 4.3 86.0 ± 1.8 73.8 ± 3.9 50.9 ± 3.8 78.9 ± 1.9 AWL 87.9 ± 9.8 ---74.5 ± 5.9 51.5 ± 3.6 73.9 ± 1.9 RetGK 90. ones obtained with categorical attributes, except that in 2/4 datasets, the multilayer versions of GCKN underperform compared to GCKN-path, but they achieve lower computational complexity. Paths were indeed presumably predictive enough for these datasets. Besides, the supervised version of GCKN-subtree outperforms its unsupervised counterpart in 2/4 datasets.

Dataset

Model Interpretation

We train a supervised GCKN-subtree model on the Mutagenicity dataset [START_REF] Kersting | Benchmark data sets for graph kernels[END_REF], and use our method described in Section 4 to identify important subgraphs. of filters q. The accuracies for NCI1, PROTEINS and IMDBMULTI are given in Figure 4, by varying respectively the number of filters, the path size, the bandwidth parameter and regularization parameter when fixing other parameters which give the best accuracy. Supervised models generally require fewer number of filters to achieve similar performance to its unsupervised counterpart. In particular on the NCI1 dataset, the supervised GCKN outperforms its unsupervised counterpart by a significant margin when using a small number of filters.

B.3. Model Interpretation

Implementation details. We use a similar experimental setting as [START_REF] Ying | Generating explanations for graph neural networks[END_REF] to train a supervised GCKN-subtree model on Mutagenicity dataset, consisting of 4337 molecule graphs labeled according to their mutagenic effect. Specifically, we use the same split for train and validation set and train a GCKN-subtree model with k 1 = 3, which is similar to a 3-layer GNN model. The number of filters is fixed to 20, the same as [START_REF] Ying | Generating explanations for graph neural networks[END_REF]. The bandwidth parameter σ is fixed to 0.4, local and global pooling are fixed to mean pooling, the regularization parameter λ is fixed to 1e-05. We use an Adam optimizer with initial learning equal to 0.01 and halved every 50 epochs, the same as previously. The accuracy of the trained model is assured to be more than 80% on the test set as [START_REF] Ying | Generating explanations for graph neural networks[END_REF]. Then we use the procedure described in Section 4 to interpret our trained model. We use an LBFGS optimizer and fixed µ to 0.01. The final subgraph for each given graph is obtained by extracting the maximal connected component formed by the selected paths. A contribution score for each edge can also be obtained by gathering the weights M of all the selected paths that pass through this edge.

More results. More motifs extracted by GCKN are shown in Figure 5 for the Mutagenicity dataset. We recovered some benzene ring or polycyclic aromatic groups which are known to be mutagenic. We also found some groups whose mutagenicity is not known, such as polyphenylene sulfide in the fourth subgraph and 2-chloroethyl-in the last subgraph.

C. Fast Computation of GCKN with Walks

Here we discuss an efficient computational variant using walk kernel instead of path kernel, at the cost of losing some expressive power. Let us consider a relaxed walk kernel by analogy to (8) with

κ (k) base (u, u ) = p∈W k (G,u) p ∈W k (G ,u ) κ 1 (ϕ 0 (p), ϕ 0 (p )), (19)
using walks instead of paths and with κ 1 the Gaussian kernel defined in (9). As Gaussian kernel can be decomposed as a product of the Gaussian kernel on pair of nodes at each position

κ 1 (ϕ 0 (p), ϕ 0 (p )) = k j=1 κ 1 (ϕ 0 (p j ), ϕ 0 (p j )),
We can obtain similar recursive relation as for the original walk kernel in Lemma 2

κ (k) base (u, u ) = κ 1 (ϕ 0 (u), ϕ 0 (u )) v∈N (u) v ∈N (u ) κ (k-1) base (v, v ). (20)
After applying the Nyström method, the approximate feature map in (13) becomes First and third rows are original graphs; second and fourth rows are corresponding motifs. Some benzene ring or polycyclic aromatic groups are identified, which are known to be mutagenic. In addition, Some chemical groups whose mutagenicity is not known are also identified, such as polyphenylene sulfide in the fourth subgraph and 2-chloroethyl-in the last subgraph.

ψ 1 (u) = σ 1 (Z Z) -1 2 c k (u),
where for any 0 ≤ j ≤ k, c j (u) := p∈Wj (G,u) σ 1 (Z j ψ 0 (p)) and Z j in R q0(j+1)×q1 denotes the matrix consisting of the j + 1 last columns of q 1 anchor points. Using the above recursive relation (20) and similar arguments in e.g. (Chen et al., 2019b), we can show c j obeys the following recursive relation

c j (u) = b j (u) v∈N (u) c j-1 (v), 1 ≤ j ≤ k, (21)
where denotes the element-wise product and b j (u) is a vector in R q1 whose entry i in {1, . . . , q 1 } is κ 1 (u, z (k+1-j) i

) and z (k+1-j) i denotes the k + 1j-th column vector of z i in R q0 . In practice, v∈N (u) c j-1 (v) can be computed efficiently by multiplying the adjacency matrix with the |V|-dimensional vector with entries c j-1 (v) for v ∈ V.

D. Proof of Theorem 1

Before presenting and proving the link between the WL subtree kernel and the walk kernel, we start by reminding and showing some useful results about the WL subtree kernel and the walk kernel. Proof. We prove this by induction on k ≥ 0. For k = 0, this is true by the definition of κ (0) subtree . For k ≥ 1, we suppose that κ Since the only values can take for κ (k-1)

subtree is 0 and 1, the only values that max R∈M(u,u ) (v,v )∈R κ (k-1) subtree (v, v ) can take is also 0 and 1. Then we can split the proof on these two conditions. It is obvious if this term is equal to 1. If this term is equal to 0, then max

D.2. Recursive relation for the walk kernel

We recall that the k-walk kernel is defined as The feature map of this kernel is given by

K(G, G ) =
ϕ (k) walk (u) = p∈W k (G,u) ϕ δ (a(p)),
where ϕ δ is the feature map associated with δ. We give here a recursive relation for the walk kernel on the size of walks, thanks to its allowance of nodes to repeat.

Lemma 2. For any k ≥ 0, we have

κ (k+1)
walk (u, u ) = δ(a(u), a (u ))

v∈N (u) v ∈N (u ) κ (k) walk (v, v ). (24)
Proof. Noticing that we can always decompose a path p ∈ W k+1 (G, u), with (u, v) the first edge that it passes and v ∈ N (u), into (u, q) with q ∈ W k (G, v), then we have κ

Figure 3 .

 3 Figure 3. Motifs extracted by GCKN on the Mutagenicity dataset.

Figure 4 .

 4 Figure 4. Hyperparamter study: sensibility to different hyperparameters for unsupervised and supervised GCKN-subtree models. The row from top to bottom respectively corresponds to number of filters q1, path size k1, bandwidth parameter σ and regularization parameter λ. The column from left to right corresponds to different datasets: NC11, PROTEINS and IMDBMULTI.

Figure 5 .

 5 Figure5. More motifs extracted by GCKN on Mutagenicity dataset. First and third rows are original graphs; second and fourth rows are corresponding motifs. Some benzene ring or polycyclic aromatic groups are identified, which are known to be mutagenic. In addition, Some chemical groups whose mutagenicity is not known are also identified, such as polyphenylene sulfide in the fourth subgraph and 2-chloroethyl-in the last subgraph.

D. 1 .

 1 Useful results for the WL subtree kernelWe first recall a recursive relation of the WL subtree kernel, given in the Theorem 8 of[START_REF] Shervashidze | Weisfeiler-Lehman graph kernels[END_REF]. Let us denote by M(u, u ) the set of exact matchings of subsets of the neighbors of u and u , formally given byM(u, u ) = R ⊆ N (u) × N (u ) |R| = |N (u)| = |N (u )|∧ (∀(v, v ), (w, w ) ∈ R : u = w ⇔ u = w ) ∧ (∀(u, u ) ∈ R : a(u) = a (u )) . (22)Then we have the following recursive relation for κ(k) subtree (u, u ) := δ(a k (u), a k (u )) subtree (v, v ), if M(u, u ) = ∅,simply the above recursion using the following Lemma Lemma 1. If M(u, u ) = ∅, we have κ (k+1) subtree (u, u ) = δ(a(u), a (u )) max R∈M(u,u ) (v,v )∈R κ (k) subtree (v, v ).

  subtree (u, u ) = δ(a(u), a (u )) max R∈M(u,u ) (v,v )∈R κ (k-1)subtree(v, v ). We have κ

  R∈M(u,u ) (v,v )∈R κ (k) subtree (v, v ) ≤ max R∈M(u,u ) (v,v )∈R κ (k-1) subtree (v, v ) = 0,as all terms are not negative and κ(k) subtree (v, v ) is not creasing on k. Then max R∈M(u,u ) (v,v )∈R κ (k)subtree (v, v ) = 0 and we have 0 for both sides.

  u ) = p∈W k (G,u) p ∈W k (G ,u ) δ(a(p), a (p )).

  u ) = p∈W k+1 (G,u) p ∈W k+1 (G ,u ) δ(a(p), a (p )) = v∈N (u) p∈W k (G,v) v ∈N (u ) p ∈W k (G,v ) δ(a(u), a (u ))δ(a(p), a (p )) = δ(a(u), a (u )) v∈N (u) v ∈N (u ) p∈W k (G,v) p ∈W k (G ,v ) δ(a(p), a (p )) = δ(a(u), a (u )) v∈N (u) v ∈N (u ) κ (k) walk (v, v ).This relation also provides us a recursive relation for the feature maps of the walk kernel ϕ power between walk kernel and WL subtree kernel Before proving the Theorem 1, let us first show that the WL subtree kernel is always more discriminative than the walk kernel. Proposition 1. For any node u in graph G and u in graph G and any k ≥ 0, then d κ (k) subtree (u, u ) = 0 =⇒ d κ (k) walk (u, u ) = 0.

Table 2 .

 2 Classification accuracies on graphs with continuous attributes. The accuracies of other models except GNTK are taken from Togninalli et al. (2019). The accuracies of GNTK are obtained by running the code of Du et al. (2019) on a similar setting.

	Dataset	ENZYMES PROTEINS	BZR	COX2
	size	600	1113	405	467
	classes	6	2	2	2
	attr. dim.	18	29	3	3
	avg nodes	32.6	39.0	35.8	41.2
	avg edges	62.1	72.8	38.3	43.5
	RBF-WL HGK-WL HGK-SP WWL GNTK GCKN-walk-unsup GCKN-path-unsup GCKN-subtree-unsup 74.8 ± 0.7 68.4 ± 1.5 63.0 ± 0.7 66.4 ± 0.4 73.3 ± 0.9 77.9 ± 0.8 84.4 ± 2.0 75.4 ± 0.3 81.0 ± 1.7 75.9 ± 0.2 78.6 ± 0.6 75.8 ± 0.2 76.4 ± 0.7 69.6 ± 0.9 75.7 ± 0.2 85.5 ± 0.8 73.5 ± 0.5 76.5 ± 0.3 85.3 ± 0.5 75.7 ± 1.1 76.3 ± 0.5 85.9 ± 0.5 77.5 ± 0.3 85.8 ± 0.9 GCKN-3layer-unsup 74.6 ± 0.8 77.5 ± 0.4 84.7 ± 1.0 82.0 ± 0.6 75.5 ± 1.5 78.1 ± 0.5 72.6 ± 1.2 78.3 ± 0.5 79.6 ± 0.4 80.6 ± 1.2 81.2 ± 0.8 81.8 ± 0.8 GCKN-subtree-sup 72.8 ± 1.0 77.6 ± 0.4 86.4 ± 0.5 81.7 ± 0.7

Table 3 .

 3 Hyperparameter search range

	Hyperparameter	Search range
	σ (α = 1/σ 2 )	[0.3; 0.4; 0.5; 0.6; 1.0; 1.5; 2.0]
	local/global pooling	[sum, mean, max]
	path size k 1	integers between 2 and 12
	number of filters (unsup)	[32; 128; 512; 1024]
	number of filters (sup)	[32; 64] and 256 for ENZYMES
	λ (unsup) λ (sup)	1/n × np.logspace(-3, 4, 60) [0.01; 0.001; 0.0001; 1e-05; 1e-06; 1e-07]

http://julien.mairal.org/cyanure/

Acknowledgements

This work has been supported by the grants from ANR (FAST-BIG project ANR-17 CE23-0011-01), by the ERC grant number 714381 (SOLARIS), and by ANR 3IA MIAI@Grenoble Alpes, (ANR-19-P3IA-0003).

Appendix

This appendix provides both theoretical and experimental material and is organized as follows: Appendix A presents a classical result, allowing us to characterize the RKHS of the graph kernels we introduce. Appendix B provides additional experimental details that are useful to reproduce our results and additional experimental results. Then, Appendix C explains how to accelerate the computation of GCKN when using walks instead of paths (at the cost of lower expressiveness), and

A. Useful Result about RKHSs

The following result characterizes the RKHS of a kernel function when an explicit mapping to a Hilbert space is available. It may be found in classical textbooks (see, e.g., Saitoh, 1997, §2.1). Theorem 2. Let Φ : X → F be a mapping from a data space X to a Hilbert space F, and let K(x, x ) := Φ(x), ψ(x ) F for x, x in X . Consider the Hilbert space

Then, H is the reproducing kernel Hilbert space associated to kernel K.

B. Details on Experimental Setup and Additional Experiments

In this section, we provide additional details and more experimental results. In Section B.1, we provide additional experimental details; in Section ??, we present a benchmark on graph classification with continuous attributes by using the protocol of [START_REF] Togninalli | Wasserstein Weisfeiler-Lehman graph kernels[END_REF]; in Section B.2, we perform a hyperparameter study for unsupervised GCKN on three datasets, showing that our approach is relatively robust to the choice of hyperparameters. In particular, the number of filters controls the quality of Nyström's kernel approximation: more filters means a better approximation and better results, at the cost of more computation. This is in contrast with a traditional (supervised) GNN, where more filters may lead to overfitting. Finally, Section B.3 provides motif discovery results.

B.1. Experimental Setup and Reproducibility

Hyperparameter search grids. In our experiments for supervised models, we use an Adam optimizer [START_REF] Kingma | A method for stochastic optimization[END_REF] for at most 350 epochs with an initial learning rate equal to 0.01 and halved every 50 epochs with a batch size fixed to 32 throughout all datasets; the number of epochs is selected using cross validation following [START_REF] Xu | How powerful are graph neural networks[END_REF]. The full hyperparameter search range is given in Table 3 for both unsupervised and supervised models on all tasks. Note that we include some large values (1.5 and 2.0) for σ to simulate the linear kernel as we discussed in Section 3.3. In fact, the function σ 1 (x) = e α(x-1) defined in ( 12) is upper bounded by e -α + (1e -α )x and lower bounded by 1 + α(x -1) by its convexity at 0 and 1. Their difference is increasing with α and converges to zero when α tends to 0. Hence, when α is small, σ 1 behaves as an affine kernel with a small slope.

Computing infrastructure. Experiments for unsupervised models were conducted by using a shared CPU cluster composed of 2 Intel Xeon E5-2470v2 @2.4GHz CPUs with 16 cores and 192GB of RAM. Supervised models were trained by using a shared GPU cluster, in large parts built with Nvidia gamer cards (Titan X, GTX1080TI). About 20 of these CPUs and 10 of these GPUs were used simultaneously to perform the experiments of this paper.

B.2. Hyperparameter Study

We show here that both unsupervised and supervised models are generally robust to different hyperparameters, including path size k 1 , bandwidth parameter σ, regularization parameter λ and their performance grows increasingly with the number This proposition suggests that though both of their feature maps are not injective (see e.g. [START_REF] Kriege | A property testing framework for the theoretical expressivity of graph kernels[END_REF]), the feature map of κ

subtree is more injective in the sense that for a node u, its collision set {u ∈

subtree , with ϕ the corresponding feature map, is included in that for κ (k) walk . Furthermore, if we denote by κ the normalized kernel of κ such that κ(u, u ) = κ(u, u )/ κ(u, u)κ(u , u ), then we have Corolary 1. For any node u in graph G and u in graph G and any k ≥ 0,

Proof. We prove by induction on k. It is clear for k = 0 as both kernels are equal to the Dirac kernel on the node attributes. Let us suppose this is true for k ≥ 0, we will show this is also true for k + 1. We suppose d κ (k+1) subtree (u, u ) = 0. Since κ (k+1) subtree (u, u) = 1, by equality (23) we have

On the other hand, by Lemma 2 we have

which suggest that the feature map of κ (k+1) walk can be written as ϕ

We conclude that d κ

D.4. Proof of Theorem 1

Note that using our notation here, ϕ 1 = ϕ (k) walk Proof. We prove by induction on k. For k = 0, we have for any u ∈ V and u ∈ V

Assume that ( 16) is true for k ≥ 0. We want to show this is also true for k + 1. As the only values that the δ kernel can take is 0 and 1, it suffices to show the equality between κ

By Lemma 1, it suffices to show that max

The condition |M(u, u )| = 1 suggests that there exists exactly one matching of the neighbors of u and u . Let us denote this matching by R. The left equality implies that there exists a non-empty subset of neighbor pairs S ⊆ R such that κ