Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Random walk kernels have been introduced in seminal work on graph learning
and were later largely superseded by kernels based on the Weisfeiler-Leman test
for graph isomorphism. We give a unified view on both classes of graph kernels.
We study walk-based node refinement methods and formally relate them to several
widely-used techniques, including Morgan's algorithm for molecule canonization
and the Weisfeiler-Leman test. We define corresponding walk-based kernels on
nodes that allow fine-grained parameterized neighborhood comparison, reach
Weisfeiler-Leman expressiveness, and are computed using the kernel trick. From
this we show that classical random walk kernels with only minor modifications
regarding definition and computation are as expressive as the widely-used
Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison.
We verify experimentally that walk-based kernels reach or even surpass the
accuracy of Weisfeiler-Leman kernels in real-world classification tasks.