Weisfeiler Leman graph isomorphism test
 | The topic of this article may not meet Wikipedia's general notability guideline. (June 2025) |
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.[citation needed]
An example of two non-isomorphic graphs that WLpair cannot distinguish is given here.[3]
Weisfeiler Leman graph kernels
The theory behind the Weisfeiler Leman test may be applied in graph neural networks.
In machine learning of nonlinear data one uses kernels to represent the data in a high dimensional feature space after which linear techniques such as support vector machines can be applied. Data represented as graphs often behave nonlinearly. Graph kernels are a method to preprocess such graph based nonlinear data to simplify subsequent learning methods. Such graph kernels can be constructed by partially executing a Weisfeiler Leman test and processing the partition that has been constructed up to that point.[4] These Weisfeiler Leman graph kernels have attracted considerable research in the decade after their publication.[1]
References
- ^ a b 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.
- ^ Bronstein, Michael (2020-12-01). "Expressive Power Of Graph Neural Networks And The Weisfeiler-Lehman Test". Retrieved 2023-10-28.
- ^ Shervashidze, Nino; Schweitzer, Pascal; Van Leeuwen, Erik Jan; Mehlhorn, Kurt; Borgwardt, Karsten M. (2011). "Weisfeiler-lehman graph kernels". Journal of Machine Learning Research. 12 (9): 2539−2561. Retrieved 2023-10-29.