Weisfeiler Leman graph isomorphism test

In graph theory, the Weisfeiler Leman graph isomorphism test is a heuristic test for the existence of an isomorphism between two graphs G and H.^[1] It is a generalization of the color refinement algorithm and has been first described by Weisfeiler and Leman in 1968.^[2] The original formulation is based on graph canonization, a normal form for graphs, while there is also a combinatorial interpretation in the spirit of color refinement and a connection to logic.

There are several versions of the test (e.g. k-WL and k-FWL) referred to in the literature by various names, which easily leads to confusion. Additionally, Andrey Leman is spelled `Lehman' in several older articles.

^ Huang, Ningyuan; Villar, Soledad (2022), "A Short Tutorial on the Weisfeiler-Lehman Test and Its Variants", ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533–8537, arXiv:2201.07083, doi:10.1109/ICASSP39728.2021.9413523, ISBN 978-1-7281-7605-5, S2CID 235780517
^ Weisfeiler, B. Yu.; Leman, A. A. (1968). "A Reduction of a Graph to a Canonical Form and an Algebra Arising during This Reduction" (PDF). Nauchno-Technicheskaya Informatsia. 2 (9): 12–16. Retrieved 2023-10-28.

[WLtutorial-1] Huang, Ningyuan; Villar, Soledad (2022), "A Short Tutorial on the Weisfeiler-Lehman Test and Its Variants", ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533–8537, arXiv:2201.07083, doi:10.1109/ICASSP39728.2021.9413523, ISBN 978-1-7281-7605-5, S2CID 235780517

[WL68-2] Weisfeiler, B. Yu.; Leman, A. A. (1968). "A Reduction of a Graph to a Canonical Form and an Algebra Arising during This Reduction" (PDF). Nauchno-Technicheskaya Informatsia. 2 (9): 12–16. Retrieved 2023-10-28.

[1]

[2]