# The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 1 Feb 2023.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [COT-GAN: Generating Sequential Data via Causal Optimal Transport](https://mlsanity.com/paper/2006.08571/) (2020)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Causal transport in discrete time and applications](https://mlsanity.com/paper/1606.04062/) (2016)
- [Weisfeiler-Lehman meets Gromov-Wasserstein](https://mlsanity.com/paper/2202.02495/) (2022)
- [SPATE-GAN: Improved Generative Modeling of Dynamic Spatio-Temporal Patterns with an Autoregressive Embedding Loss](https://mlsanity.com/paper/2109.15044/) (2021)
- [Computational methods for adapted optimal transport](https://mlsanity.com/paper/2203.05005/) (2022)
- [Capturing Graphs with Hypo-Elliptic Diffusions](https://mlsanity.com/paper/2205.14092/) (2022)
- [Conditional COT-GAN for Video Prediction with Kernel Smoothing](https://mlsanity.com/paper/2106.05658/) (2021)

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

- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Synchronous Diffusion for Unsupervised Smooth Non-Rigid 3D Shape Matching](https://mlsanity.com/paper/2407.08244/) (2024)
- [A Primer on Temporal Graph Learning](https://mlsanity.com/paper/2401.03988/) (2024)
- [Distances for Markov Chains, and Their Differentiation](https://mlsanity.com/paper/2302.08621/) (2023)
- [Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking](https://mlsanity.com/paper/2402.11339/) (2024)
- [The Generalized Proximity Forest](https://mlsanity.com/paper/2511.19487/) (2025)

## Abstract (arXiv)

In this paper, we present a novel interpretation of the so-called Weisfeiler-Lehman (WL) distance, introduced by Chen et al. (2022), using concepts from stochastic processes. The WL distance aims at comparing graphs with node features, has the same discriminative power as the classic Weisfeiler-Lehman graph isomorphism test and has deep connections to the Gromov-Wasserstein distance. This new interpretation connects the WL distance to the literature on distances for stochastic processes, which also makes the interpretation of the distance more accessible and intuitive. We further explore the connections between the WL distance and certain Message Passing Neural Networks, and discuss the implications of the WL distance for understanding the Lipschitz property and the universal approximation results for these networks.