# Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited

arXiv: https://arxiv.org/abs/2205.10914 · HTML: https://mlsanity.com/paper/2205.10914/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 22 May 2022.

## Builds on (most cited first, 23 of 23)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [Convolutional Kernel Networks for Graph-Structured Data](https://mlsanity.com/paper/2003.05189/) (2020)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)
- [Graph Homomorphism Convolution](https://mlsanity.com/paper/2005.01214/) (2020)
- [Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework](https://mlsanity.com/paper/2004.02593/) (2020)
- [Deriving Neural Architectures from Sequence and Graph Kernels](https://mlsanity.com/paper/1705.09037/) (2017)
- [Understanding Isomorphism Bias in Graph Data Sets](https://mlsanity.com/paper/1910.12091/) (2019)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [On the expressive power of linear algebra on graphs](https://mlsanity.com/paper/1812.04379/) (2018)
- [On the Definiteness of Earth Mover's Distance and Its Relation to Set Intersection](https://mlsanity.com/paper/1510.02833/) (2015)
- [A Unifying View of Explicit and Implicit Feature Maps of Graph Kernels](https://mlsanity.com/paper/1703.00676/) (2017)

## Built on by (most cited first, 9 of 9)

- [Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph](https://mlsanity.com/paper/2409.11504/) (2024)
- [Descriptive Kernel Convolution Network with Improved Random Walk Kernel](https://mlsanity.com/paper/2402.06087/) (2024)
- [On the Two Sides of Redundancy in Graph Neural Networks](https://mlsanity.com/paper/2310.04190/) (2023)
- [Normed Spaces for Graph Embedding](https://mlsanity.com/paper/2312.01502/) (2023)
- [Random Search Neural Networks for Efficient and Expressive Graph Learning](https://mlsanity.com/paper/2510.22520/) (2025)
- [Message Detouring: A Simple Yet Effective Cycle Representation for Expressive Graph Learning](https://mlsanity.com/paper/2402.08085/) (2024)
- [A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring](https://mlsanity.com/paper/2505.12437/) (2025)
- [Caterpillar GNN: Replacing Message Passing with Efficient Aggregation](https://mlsanity.com/paper/2506.06784/) (2025)
- [A Node Embedding Framework for Model-Centric Conformance Checking in Process Mining](https://mlsanity.com/paper/2610.17702/) (2026)

## Abstract (arXiv)

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.