# A Generalized Weisfeiler-Lehman Graph Kernel

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 20 Jan 2021.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [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)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [GraKeL: A Graph Kernel Library in Python](https://mlsanity.com/paper/1806.02193/) (2018)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [Lov'asz Meets Weisfeiler and Leman](https://mlsanity.com/paper/1802.08876/) (2018)
- [DDGK: Learning Graph Representations for Deep Divergence Graph Kernels](https://mlsanity.com/paper/1904.09671/) (2019)
- [Theoretically Expressive and Edge-aware Graph Learning](https://mlsanity.com/paper/2001.09005/) (2020)

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

- [Gradual Weisfeiler-Leman: Slow and Steady Wins the Race](https://mlsanity.com/paper/2209.09048/) (2022)
- [Wasserstein Graph Distance Based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees](https://mlsanity.com/paper/2207.04216/) (2022)
- [A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs](https://mlsanity.com/paper/2310.04598/) (2023)
- [CityGPT: Towards Urban IoT Learning, Analysis and Interaction with Multi-Agent System](https://mlsanity.com/paper/2405.14691/) (2024)
- [On the Relationship Between Robustness and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2504.13786/) (2025)
- [Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent](https://mlsanity.com/paper/2311.01205/) (2023)
- [Towards Subgraph Isomorphism Counting with Graph Kernels](https://mlsanity.com/paper/2405.07497/) (2024)
- [Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win](https://mlsanity.com/paper/2506.03919/) (2025)
- [Rethinking Generative Reconstruction Attacks against Graph Neural Network Models](https://mlsanity.com/paper/2606.29748/) (2026)

## Abstract (arXiv)

The Weisfeiler-Lehman graph kernels are among the most prevalent graph kernels due to their remarkable time complexity and predictive performance. Their key concept is based on an implicit comparison of neighborhood representing trees with respect to equality (i.e., isomorphism). This binary valued comparison is, however, arguably too rigid for defining suitable similarity measures over graphs. To overcome this limitation, we propose a generalization of Weisfeiler-Lehman graph kernels which takes into account the similarity between trees rather than equality. We achieve this using a specifically fitted variation of the well-known tree edit distance which can efficiently be calculated. We empirically show that our approach significantly outperforms state-of-the-art methods in terms of predictive performance on datasets containing structurally more complex graphs beyond the typically considered molecular graphs.