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 based on a normal form for graphs first described in an article by Weisfeiler and Leman in 1968.[2] There are several versions of the test, these versions are referred in the literature by various names, which easily leads to confusion.
The basic Weisfeiler Leman graph isomorphism test
The basic version takes a graph as input, produces a partition of the nodes which is invariant under automorphisms and outputs a string certificate encoding the partition. When applied to two graphs G and H we can compare the certificates. If the certificates do not agree the test fails and G and H cannot be isomorphic. If the certificates agree, G and H may or may not be isomorphic.
| Graph G0 | Graph G1 | Graph G2 |
|---|---|---|
|
|
|
|
Applications
The theory behind the Weisfeiler Leman test is applied in graph neural networks.
See also
References
- ^ 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.