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 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]