mlsanityData to 7 Oct 2026

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

arXiv 2201.07083 ↗First posted 18 Jan 2022stat.ML cs.LGcited by 52

Not on the map. Why?

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.

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

Builds on

15 of 26 references.

References · 15

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  3. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  4. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2017Representation Learning on Graphs: Methods and Applicationscited by 456
  7. 2019Provably Powerful Graph Networkscited by 385
  8. 2018Invariant and Equivariant Graph Networkscited by 339
  9. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  10. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  11. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  12. 2019Wasserstein Weisfeiler-Lehman Graph Kernelscited by 104
3 more
  1. 2015Graph Isomorphism in Quasipolynomial Timecited by 19
  2. 2020A Novel Higher-order Weisfeiler-Lehman Graph Convolutioncited by 10
  3. 2019Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddingscited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 9; 2024: 13; 2025: 14; 2026: 8.

52 papers.

Sort:

By area:

  1. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  2. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  3. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
  4. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 20
  5. 2024Comparing Graph Transformers via Positional Encodingscited by 20
  6. 2022Group-invariant max filteringcited by 18
  7. 2022Dimensionless machine learning: Imposing exact units equivariancecited by 16
  8. 20221-WL Expressiveness Is (Almost) All You Needcited by 15
  9. 2022Agent-based Graph Neural Networkscited by 13
  10. 2022From Local to Global: Spectral-Inspired Graph Neural Networkscited by 11
  11. 2023Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Powercited by 11
  12. 2023Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexescited by 10
38 more
  1. 2024Expressivity and Generalization: Fragment-Biases for Molecular GNNscited by 8
  2. 2023On the power of graph neural networks and the role of the activation functioncited by 7
  3. 2023Non-backtracking Graph Neural Networkscited by 7
  4. 2024On dimensionality of feature vectors in MPNNscited by 6
  5. 2024On the H"older Stability of Multiset and Graph Neural Networkscited by 6
  6. 2024Homomorphism Counts as Structural Encodings for Graph Learningcited by 6
  7. 2024Hyperdimensional Representation Learning for Node Classification and Link Predictioncited by 5
  8. 2025HOPSE: Scalable Higher-Order Positional and Structural Encoder for Combinatorial Representationscited by 5
  9. 2023Graph Classification Gaussian Processes via Spectral Featurescited by 4
  10. 2024Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodingscited by 4
  11. 2024DPHGNN: A Dual Perspective Hypergraph Neural Networkscited by 3
  12. 2024PDDLFuse: A Tool for Generating Diverse Planning Domainscited by 3
  13. 2025S'MoRE: Structural Mixture of Residual Experts for Parameter-Efficient LLM Fine-tuningcited by 3
  14. 2025Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrumcited by 3
  15. 2025Evaluating machine learning models for predicting pesticide toxicity to honey beescited by 2
  16. 2023Benchmarking Toxic Molecule Classification using Graph Neural Networks and Few Shot Learningcited by 1
  17. 2024Graph Mining under Data scarcitycited by 1
  18. 2024Software Model Evolution with Large Language Models: Experiments on Simulated, Public, and Industrial Datasetscited by 1
  19. 2025A Methodological Framework for Measuring Spatial Labeling Similaritycited by 1
  20. 2025Positional Encoding meets Persistent Homology on Graphscited by 1
  21. 2025Finite-Agent Stochastic Differential Games on Large Graphs: II. Graph-Based Architecturescited by 1
  22. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 1
  23. 2026On the Expressive Power of GNNs for Boolean Satisfiabilitycited by 1
  24. 2026Detecting Differences Is Not Understanding Structure: Large Language Models Fail at Graph Isomorphismcited by 1
  25. 2022EDEN: A Plug-in Equivariant Distance Encoding to Beyond the 1-WL Testcited by 0
  26. 2023Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNScited by 0
  27. 2023Towards Automatic Support of Software Model Evolution with Large Language~Modelscited by 0
  28. 2024Enhancing GNNs with Architecture-Agnostic Graph Transformations: A Systematic Analysiscited by 0
  29. 2024Towards characterizing the value of edge embeddings in Graph Neural Networkscited by 0
  30. 2025Schreier-Coset Graph Propagationcited by 0
  31. 2025SpaPool: Soft Partition Assignment Pooling for__Graph Neural Networkscited by 0
  32. 2025On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Modelcited by 0
  33. 2025Explainable Graph Representation Learning via Graph Pattern Analysiscited by 0
  34. 2025Edged Weisfeiler-Lehman Algorithmcited by 0
  35. 2026Invariant-Stratified Propagation for Expressive Graph Neural Networkscited by 0
  36. 2026Learning Minimally Rigid Graphs with High Realization Countscited by 0
  37. 2026Scaling Higher-Order Graph Learning with Maximal Clique Complexescited by 0
  38. 2026Understanding Truncated Positional Encodings for Graph Neural Networkscited by 0

50 most cited of 52 All 52 (JSON)