Weisfeiler Leman graph isomorphism test

The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "Weisfeiler Leman graph isomorphism test" – news · newspapers · books · scholar · JSTOR (June 2025) (Learn how and when to remove this message)

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]

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]