# On the Combinatorial Power of the Weisfeiler-Lehman Algorithm

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2017.

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

- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [Cometh: A continuous-time discrete-state graph diffusion model](https://mlsanity.com/paper/2406.06449/) (2024)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [An Efficient Subgraph GNN with Provable Substructure Counting Power](https://mlsanity.com/paper/2303.10576/) (2023)
- [Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power](https://mlsanity.com/paper/2309.04941/) (2023)
- [On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters](https://mlsanity.com/paper/2309.17053/) (2023)
- [GEFL: Extended Filtration Learning for Graph Classification](https://mlsanity.com/paper/2406.02732/) (2024)
- [Graph as Point Set](https://mlsanity.com/paper/2405.02795/) (2024)
- [Homomorphism Expressivity of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2503.00485/) (2025)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Technical report: Graph Neural Networks go Grammatical](https://mlsanity.com/paper/2303.01590/) (2023)
- [Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks](https://mlsanity.com/paper/2305.19659/) (2023)
- [Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning](https://mlsanity.com/paper/2410.01661/) (2024)

## Abstract (arXiv)

The classical Weisfeiler-Lehman method WL[2] uses edge colors to produce a powerful graph invariant. It is at least as powerful in its ability to distinguish non-isomorphic graphs as the most prominent algebraic graph invariants. It determines not only the spectrum of a graph, and the angles between standard basis vectors and the eigenspaces, but even the angles between projections of standard basis vectors into the eigenspaces. Here, we investigate the combinatorial power of WL[2]. For sufficiently large k, WL[k] determines all combinatorial properties of a graph. Many traditionally used combinatorial invariants are determined by WL[k] for small k. We focus on two fundamental invariants, the num- ber of cycles Cp of length p, and the number of cliques Kp of size p. We show that WL[2] determines the number of cycles of lengths up to 6, but not those of length 8. Also, WL[2] does not determine the number of 4-cliques.