# A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants

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

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 18 Jan 2022.

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

- [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)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Graph Isomorphism in Quasipolynomial Time](https://mlsanity.com/paper/1512.03547/) (2015)
- [A Novel Higher-order Weisfeiler-Lehman Graph Convolution](https://mlsanity.com/paper/2007.00346/) (2020)
- [Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings](https://mlsanity.com/paper/1904.01543/) (2019)

## Built on by (most cited first, 30 of 52)

- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Group-invariant max filtering](https://mlsanity.com/paper/2205.14039/) (2022)
- [Dimensionless machine learning: Imposing exact units equivariance](https://mlsanity.com/paper/2204.00887/) (2022)
- [1-WL Expressiveness Is (Almost) All You Need](https://mlsanity.com/paper/2202.10156/) (2022)
- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power](https://mlsanity.com/paper/2309.04941/) (2023)
- [From Local to Global: Spectral-Inspired Graph Neural Networks](https://mlsanity.com/paper/2209.12054/) (2022)
- [Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes](https://mlsanity.com/paper/2308.06838/) (2023)
- [Expressivity and Generalization: Fragment-Biases for Molecular GNNs](https://mlsanity.com/paper/2406.08210/) (2024)
- [On the power of graph neural networks and the role of the activation function](https://mlsanity.com/paper/2307.04661/) (2023)
- [Non-backtracking Graph Neural Networks](https://mlsanity.com/paper/2310.07430/) (2023)
- [On dimensionality of feature vectors in MPNNs](https://mlsanity.com/paper/2402.03966/) (2024)
- [Homomorphism Counts as Structural Encodings for Graph Learning](https://mlsanity.com/paper/2410.18676/) (2024)
- [On the H"older Stability of Multiset and Graph Neural Networks](https://mlsanity.com/paper/2406.06984/) (2024)
- [Hyperdimensional Representation Learning for Node Classification and Link Prediction](https://mlsanity.com/paper/2402.17073/) (2024)
- [HOPSE: Scalable Higher-Order Positional and Structural Encoder for Combinatorial Representations](https://mlsanity.com/paper/2505.15405/) (2025)
- [Graph Classification Gaussian Processes via Spectral Features](https://mlsanity.com/paper/2306.03770/) (2023)
- [Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodings](https://mlsanity.com/paper/2412.07407/) (2024)
- [DPHGNN: A Dual Perspective Hypergraph Neural Networks](https://mlsanity.com/paper/2405.16616/) (2024)
- [PDDLFuse: A Tool for Generating Diverse Planning Domains](https://mlsanity.com/paper/2411.19886/) (2024)
- [S'MoRE: Structural Mixture of Residual Experts for Parameter-Efficient LLM Fine-tuning](https://mlsanity.com/paper/2504.06426/) (2025)
- [Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum](https://mlsanity.com/paper/2506.05530/) (2025)
- [Evaluating machine learning models for predicting pesticide toxicity to honey bees](https://mlsanity.com/paper/2503.24305/) (2025)
- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [Benchmarking Toxic Molecule Classification using Graph Neural Networks and Few Shot Learning](https://mlsanity.com/paper/2311.13490/) (2023)
- [Graph Mining under Data scarcity](https://mlsanity.com/paper/2406.04825/) (2024)

## Abstract (arXiv)

Graph neural networks are designed to learn functions on graphs. Typically, the relevant target functions are invariant with respect to actions by permutations. Therefore the design of some graph neural network architectures has been inspired by graph-isomorphism algorithms. The classical Weisfeiler-Lehman algorithm (WL) -- a graph-isomorphism test based on color refinement -- became relevant to the study of graph neural networks. The WL test can be generalized to a hierarchy of higher-order tests, known as k-WL. This hierarchy has been used to characterize the expressive power of graph neural networks, and to inspire the design of graph neural network architectures. A few variants of the WL hierarchy appear in the literature. The goal of this short note is pedagogical and practical: We explain the differences between the WL and folklore-WL formulations, with pointers to existing discussions in the literature. We illuminate the differences between the formulations by visualizing an example.