TY - GEN

T1 - SUSAN

T2 - The Structural Similarity Random Walk Kernel

AU - Kalofolias, Janis

AU - Welke, Pascal

AU - Vreeken, Jilles

PY - 2021/12/31

Y1 - 2021/12/31

N2 - 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.

AB - 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.

U2 - 10.1137/1.9781611976700.34

DO - 10.1137/1.9781611976700.34

M3 - Conference contribution/Paper

SP - 298

EP - 306

BT - Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)

A2 - Demeniconi, Carlotta

A2 - Davidson, Ian

A2 - Akoglu, Leman

A2 - Terzi, Evimaria

PB - SIAM PUBLICATIONS

ER -