Weisfeiler Leman graph isomorphism test

The Weisfeiler Leman graph isomorphism test is a heuristic procedure for deciding whether two graphs G and H might be isomorphic, that is, whether one can be turned into the other by renaming its vertices. It generalizes the color refinement algorithm and was first described by Weisfeiler and Leman in 1968. The original formulation rests on graph canonization, a normal form for graphs, and there is also a combinatorial reading in terms of fibrations of graphs and a connection to logic. In its one-dimensional form, known as color refinement, the test repeatedly updates the color of each vertex according to the multiset of colors of its neighbors until the coloring stops changing. If the stable colorings of G and H differ, the graphs are not isomorphic; if they match, the test is inconclusive, and there are pairs of non-isomorphic graphs it cannot tell apart. The test also bounds the expressive power of message-passing graph neural networks and is the basis of Weisfeiler Leman graph kernels used in machine learning on graph data.