mlsanityData to 7 Oct 2026

The Weisfeiler-Lehman Distance: Reinterpretation and Connection with GNNs

arXiv 2302.00713 ↗First posted 1 Feb 2023cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

11 of 28 references.

References · 11

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2019Wasserstein Weisfeiler-Lehman Graph Kernelscited by 104
  3. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  4. 2020COT-GAN: Generating Sequential Data via Causal Optimal Transportcited by 70
  5. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 39
  6. 2016Causal transport in discrete time and applicationscited by 21
  7. 2022Weisfeiler-Lehman meets Gromov-Wassersteincited by 14
  8. 2021SPATE-GAN: Improved Generative Modeling of Dynamic Spatio-Temporal Patterns with an Autoregressive Embedding Losscited by 13
  9. 2022Computational methods for adapted optimal transportcited by 12
  10. 2022Capturing Graphs with Hypo-Elliptic Diffusionscited by 12
  11. 2021Conditional COT-GAN for Video Prediction with Kernel Smoothingcited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 4; 2025: 1.

7 papers.

  1. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  2. 2024Comparing Graph Transformers via Positional Encodingscited by 20
  3. 2024Synchronous Diffusion for Unsupervised Smooth Non-Rigid 3D Shape Matchingcited by 7
  4. 2024A Primer on Temporal Graph Learningcited by 4
  5. 2023Distances for Markov Chains, and Their Differentiationcited by 2
  6. 2024Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breakingcited by 2
  7. 2025The Generalized Proximity Forestcited by 0