SUSAN: The Structural Similarity Random Walk Kernel

Random walk kernels are a very flexible family of graph kernels, in which we can incorporate edge and vertex similarities through a positive definite kernel. In this work we study the particular case within this family when the vertex kernel has bounded support. We motivate this choice as a configurable degree of vertex alignment and study several fast and intuitive ways to derive structurally aware labels for this kernel. We provide a fast algorithm to compute the resulting random walk kernel and give bounds on its computational complexity. We show that our algorithm always remains upper bounded by the methods in the literature and study conditions under which it can be significantly lower. We evaluate the resulting configurations on their predictive performance on several families of graphs and show significant improvement against the vanilla random walk kernel and other competing algorithms on several datasets.