# Weisfeiler-Lehman meets Gromov-Wasserstein

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 46 references that are in the map.
- First posted on arXiv 5 Feb 2022.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures](https://mlsanity.com/paper/1508.07941/) (2015)
- [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)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [CO-Optimal Transport](https://mlsanity.com/paper/2002.03731/) (2020)
- [Causal transport in discrete time and applications](https://mlsanity.com/paper/1606.04062/) (2016)
- [Optimal Transport for Stationary Markov Chains via Policy Iteration](https://mlsanity.com/paper/2006.07998/) (2020)
- [Entropy-Transport distances between unbalanced metric measure spaces](https://mlsanity.com/paper/2009.10636/) (2020)

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

- [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)
- [Graph Classification via Reference Distribution Learning: Theory and Practice](https://mlsanity.com/paper/2408.11370/) (2024)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs](https://mlsanity.com/paper/2302.00713/) (2023)
- [Synchronous Diffusion for Unsupervised Smooth Non-Rigid 3D Shape Matching](https://mlsanity.com/paper/2407.08244/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)
- [On the H"older Stability of Multiset and Graph Neural Networks](https://mlsanity.com/paper/2406.06984/) (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)
- [What Expressivity Theory Misses: Message Passing Complexity for GNNs](https://mlsanity.com/paper/2509.01254/) (2025)
- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [Exploring Consistency in Graph Representations:from Graph Kernels to Graph Neural Networks](https://mlsanity.com/paper/2410.23748/) (2024)

## Abstract (arXiv)

The Weisfeiler-Lehman (WL) test is a classical procedure for graph isomorphism testing. The WL test has also been widely used both for designing graph kernels and for analyzing graph neural networks. In this paper, we propose the Weisfeiler-Lehman (WL) distance, a notion of distance between labeled measure Markov chains (LMMCs), of which labeled graphs are special cases. The WL distance is polynomial time computable and is also compatible with the WL test in the sense that the former is positive if and only if the WL test can distinguish the two involved graphs. The WL distance captures and compares subtle structures of the underlying LMMCs and, as a consequence of this, it is more discriminating than the distance between graphs used for defining the state-of-the-art Wasserstein Weisfeiler-Lehman graph kernel. Inspired by the structure of the WL distance we identify a neural network architecture on LMMCs which turns out to be universal w.r.t. continuous functions defined on the space of all LMMCs (which includes all graphs) endowed with the WL distance. Finally, the WL distance turns out to be stable w.r.t. a natural variant of the Gromov-Wasserstein (GW) distance for comparing metric Markov chains that we identify. Hence, the WL distance can also be construed as a polynomial time lower bound for the GW distance which is in general NP-hard to compute.