Weisfeiler Leman graph isomorphism test
Heuristic test for graph isomorphism
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]
The one-dimensional version, also known as color refinement, repeatedly updates the color of each vertex according to the multiset of colors of its neighbors until a stable color configuration is reached. If they are different for G and H, they are non-isomorphic; if they receive the same coloring, the test is inconclusive.
An example of two non-isomorphic graphs the Weisfeiler–Leman test cannot distinguish is given here.[4]
Weisfeiler Leman graph kernels
The Weisfeiler Leman test bounds the expressive power of graph neural networks: a standard message-passing graph neural network can distinguish two graphs only if the one-dimensional Weisfeiler Leman (1-WL) test distinguishes them, and architectures attaining this bound have exactly the same power to distinguish non-isomorphic graphs as 1-WL.[5][6] Higher-dimensional (k-WL) tests correspond analogously to higher-order graph neural networks.[6][7]
Relatedly, 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.[8]