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.

翻译：在图形学习的开创性工作中引入了随机行进内核, 后来大部分被基于 Weisfeiler-Leman 的图形异形测试的内核所取代。 我们对两种类型的图形内核都有一个统一的视图。 我们研究以行走为基础的节点改进方法, 并正式将其与多种广泛使用的技术联系起来, 包括摩根的分子罐化算法和Weisfeiler- Leman 测试。 我们定义了结点上相应的行进内核, 从而可以进行精细的参数社区比对, 达到 Weisfeiler- Leman 直观度, 并且使用内核法计算。 我们从中可以看出, 经典的随机行进内核( 仅对定义和计算略作修改) 和 广泛使用的 Weisfeiler- Leman 亚型树内核内核( 支持非限制性社区比较 ) 一样, 我们通过实验来验证在现实世界分类任务中行走内核达到甚至超过 Weisfeiler- Leman 内核精度的精度。