Weisfeiler-Lehman Graph Kernels

In this article, we address the problem of defining scalable kernels on large graphs with discrete node labels. Key to our approach is the Weisfeiler-Lehman test of isomorphism, which allows us to compute a sequence of graphs which capture the topological and label information of the original graph in a runtime which is linear in the number of edges. We can apply existing graph kernels on this graph sequence and make them take into account the structural information which they ignored before. We can also define new, efficient graph kernels: In particular, a subtree kernel whose runtime is linear in the number of edges in the input graphs and in the maximum height of the subtrees considered.