SUSAN: The Structural Similarity Random Walk Kernel

Kalofolias, Janis and Welke, Pascal and Vreeken, Jilles
(2021) SUSAN: The Structural Similarity Random Walk Kernel.
In: Proceedings of the 2021 SIAM International Conference on Data Mining (SDM).
Conference: SDM SIAM International Conference on Data Mining


Download (335kB) | Preview


Random walk kernels are a very flexible family of graph kernels, in which we can incorporate edge and vertex similarities through positive definite kernels. In this work we study the particular case within this family in which the vertex kernel has bounded support. We motivate this property as the configurable flexibility in terms of vertex alignment between the two graphs on which the walk is performed. We study several fast and intuitive ways to derive structurally aware labels and combine them with such a vertex kernel, which in turn is incorporated in the random walk kernel. We provide a fast algorithm to compute the resulting random walk kernel and we give precise bounds on its computational complexity. We show that this complexity always remains upper bounded by that of alternative methods in the literature and study conditions under which this advantage can be significantly higher. We evaluate the resulting configurations on their predictive performance on several families of graphs and show significant improvements against the vanilla random walk kernel and other competing algorithms. Read More:


Actions (login required)

View Item View Item