Graph Invariant Kernels

We introduce a novel kernel that up- grades the Weisfeiler-Lehman and other graph kernels to effectively exploit high- dimensional and continuous vertex attributes. Graphs are first decomposed into subgraphs. Vertices of the subgraphs are then compared by a kernel that combines the similarity of their labels and the similarity of their structural role, using a suitable vertex invariant. By changing this invariant we obtain a family of graph kernels which includes generalizations of Weisfeiler-Lehman, NSPKD, and propa- gation kernels. We demonstrate empiri- cally that these kernels obtain state-of- the-art results on relational data sets.