  Most state-of-the-art graph kernels only take local graph properties into
account, i.e., the kernel is computed with regard to properties of the
neighborhood of vertices or other small substructures. On the other hand,
kernels that do take global graph propertiesinto account may not scale well to
large graph databases. Here we propose to start exploring the space between
local and global graph kernels, striking the balance between both worlds.
Specifically, we introduce a novel graph kernel based on the $k$-dimensional
Weisfeiler-Lehman algorithm. Unfortunately, the $k$-dimensional
Weisfeiler-Lehman algorithm scales exponentially in $k$. Consequently, we
devise a stochastic version of the kernel with provable approximation
guarantees using conditional Rademacher averages. On bounded-degree graphs, it
can even be computed in constant time. We support our theoretical results with
experiments on several graph classification benchmarks, showing that our
kernels often outperform the state-of-the-art in terms of classification
accuracies.
