# The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 106 references that are in the map.
- First posted on arXiv 12 May 2021.

## Builds on (most cited first, 30 of 62)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Directional Message Passing for Molecular Graphs](https://mlsanity.com/paper/2003.03123/) (2020)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Neural Relational Inference for Interacting Systems](https://mlsanity.com/paper/1802.04687/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)

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

- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [Graph Filtration Kernels](https://mlsanity.com/paper/2110.11862/) (2021)
- [Sparse Covariance Neural Networks](https://mlsanity.com/paper/2410.01669/) (2024)
- [Gradual Weisfeiler-Leman: Slow and Steady Wins the Race](https://mlsanity.com/paper/2209.09048/) (2022)
- [Graph Neural Networks and Arithmetic Circuits](https://mlsanity.com/paper/2402.17805/) (2024)
- [On the Relationship Between Robustness and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2504.13786/) (2025)
- [Literature Review: Graph Kernels in Chemoinformatics](https://mlsanity.com/paper/2208.04929/) (2022)
- [Explaining the Power of Topological Data Analysis in Graph Machine Learning](https://mlsanity.com/paper/2401.04250/) (2024)
- [MILP-SAT-GNN: Yet Another Neural SAT Solver](https://mlsanity.com/paper/2507.01825/) (2025)
- [A systematic approach to random data augmentation on graph neural networks](https://mlsanity.com/paper/2112.04314/) (2021)
- [Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent](https://mlsanity.com/paper/2311.01205/) (2023)
- [Concept Prerequisite Relation Prediction by Using Permutation-Equivariant Directed Graph Neural Networks](https://mlsanity.com/paper/2312.09802/) (2023)
- [The μG Language for Programming Graph Neural Networks](https://mlsanity.com/paper/2407.09441/) (2024)
- [Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win](https://mlsanity.com/paper/2506.03919/) (2025)
- [GoMS: Graph of Molecule Substructure Network for Molecule Property Prediction](https://mlsanity.com/paper/2512.12489/) (2025)
- [A Unifying Relational Perspective on Expressive Lottery Tickets](https://mlsanity.com/paper/2608.18819/) (2026)

## Abstract (arXiv)

In recent years, algorithms and neural architectures based on the Weisfeiler-Leman algorithm, a well-known heuristic for the graph isomorphism problem, emerged as a powerful tool for (supervised) machine learning with graphs and relational data. Here, we give a comprehensive overview of the algorithm's use in a machine learning setting. We discuss the theoretical background, show how to use it for supervised graph- and node classification, discuss recent extensions, and its connection to neural architectures. Moreover, we give an overview of current applications and future directions to stimulate research.