论文标题
Weisfeiler和Leman Go Walking：随机步行内核重新审视
Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
论文作者
论文摘要
在图形学习的开创性工作中引入了随机步行内核，后来基于Weisfeiler-Leman检验的图形同构的核心将大量取代。我们对两类的图内核提供了统一的看法。我们研究了基于步行的节点细化方法，并将它们正式与几种广泛使用的技术联系起来，包括摩根的分子批量化算法和Weisfeiler-Leman测试。我们在节点上定义了相应的基于步行的内核，这些核可以允许细粒度的参数化邻域比较，到达Weisfeiler-Leman Expressives，并使用内核技巧进行计算。由此，我们表明，关于定义和计算的经典随机步行内核与广泛使用的Weisfeiler-Leman子树内核一样表现力，但支持非图案的邻域比较。我们通过实验验证，基于步行的内核可以达到甚至超过现实世界分类任务中Weisfeiler-Lean内核的准确性。
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.
