Weisfeiler Leman graph isomorphism test
From Wikipedia, the free encyclopedia
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 fibrations of graphs / color refinement and a connection to logic.[3]
An example of two non-isomorphic graphs that WLpair cannot distinguish is given here.[4]