cispa_all_3414.pdf (327.51 kB)

SUSAN: The Structural Similarity Random Walk Kernel

Download (327.51 kB)
conference contribution
posted on 2023-11-29, 18:16 authored by Janis KalofoliasJanis Kalofolias, Pascal Welke, Jilles VreekenJilles Vreeken
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:


Preferred Citation

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

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

SIAM International Conference on Data Mining (SDM)

Legacy Posted Date


Open Access Type

  • Green


@inproceedings{cispa_all_3414, title = "SUSAN: The Structural Similarity Random Walk Kernel", author = "Kalofolias, Janis and Welke, Pascal and Vreeken, Jilles", booktitle="{SIAM International Conference on Data Mining (SDM)}", year="2021", }

Usage metrics


    No categories selected


    Ref. manager