[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.
There are several versions of the test (e.g. k-WL and k-FWL) referred to in the literature by various names, which easily leads to confusion.
Additionally, Andrey Leman is spelled `Lehman' in several older articles.
[3] All variants of color refinement are one-sided heuristics that take as input two graphs G and H and output a certificate that they are different or 'I don't know'.
The 1-dimensional graph isomorphism test is essentially the same as the color refinement algorithm (the difference has to do with non-edges and is irrelevant for all practical purposes as it is trivial to see that graphs with a different number of nodes are non-isomorphic).
In practice this is achieved by running color refinement on the disjoint union graph of G and H. One can then look at the histogram of colors of both graphs (counting the number of nodes after color refinement stabilized) and if they differ, this is a certificate that both graphs are not isomorphic.
Therefore WLtest can be viewed as a message passing algorithm which also connects it to graph neural networks.
Both the k-dimensional Weisfeiler-Leman (k-WL) and the k-dimensional folklore Weisfeiler-Leman algorithm (k-FWL) are extensions of 1-WL from above operating on k-tuples instead of individual nodes.
While their difference looks innocent on the first glance, it can be shown that k-WL and (k-1)-FWL (for k>2) distinguish the same pairs of graphs.
is given by the set of all k-tuples reachable by exchanging the i-th position of
of a tuple encodes the edge information between all pairs of nodes from
For example, a 2-tuple has only two possible atomic types, namely the two nodes may share an edge, or they do not.
Note that if the graph has multiple (different) edge relations or additional node features, membership in those is also represented in
The key idea of k-WL is to expand the neighborhood notion to k-tuples and then effectively run color refinement on the resulting graph.
Note that there is one major difference between k-WL and k-FWL: k-FWL checks what happens if a single node w is placed at any position of the k-tuple (and then computes the multiset of these k-tuples) while k-WL looks at the multisets that you get when changing the i-th component only of the original k-tuple.
Since both algorithms scale exponentially in k (both iterate over all k-tuples), the use of k-FWL is much more efficient than using the equivalent (k+1)-WL.
Here is some actual Python code which includes the description of the first examples.
Note that not every map of vertices that respects the labels gives an isomorphism.
This illustrates the phenomenon about labels depending on the execution order of the WLtest on the nodes.
Either one finds another relabeling method that keeps uniqueness of labels, which becomes rather technical, or one skips the relabeling altogether and keeps the label strings, which blows up the length of the certificate significantly, or one applies WLtest to the union of the two tested graphs, as we did in the variant WLpair.
WLtest cannot distinguish regular graphs of equal order,[5]: 31 but WLpair can distinguish regular graphs of distinct degree even if they have the same order.
In fact WLtest terminates after a single round as seen in these examples of order 8, which are all 3-regular except the last one which is 5-regular.
The theory behind the Weisfeiler Leman test is 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 nonlinear.
Graph kernels are method to preprocess such graph based nonlinear data to simplify subsequent learning methods.
[7] These Weisfeiler Leman graph kernels have attracted considerable research in the decade after their publication.
[1] They are also implemented in dedicated libraries for graph kernels such as GraKeL.
[8] Note that kernels for artificial neural network in the context of machine learning such as graph kernels are not to be confused with kernels applied in heuristic algorithms to reduce the computational cost for solving problems of high complexity such as instances of NP-hard problems in the field of complexity theory.
As stated above the Weisfeiler Leman test can also be applied in the later context.