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.

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]

Weisfeiler-Leman-based Graph Isomorphism heuristics

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'. This means that if the heuristic is able to tell G and H apart, then they are definitely different, but the other direction does not hold: for every variant of the WL-test (see below) there are non-isomorphic graphs where the difference is not detected. Those graphs are highly symmetric graphs such as regular graphs for 1-WL/color refinement.

Examples

The first three examples are for graphs of order 5.^[4]

Graph G0	Graph G1	Graph G2

WLpair takes 3 rounds on 'G0' and 'G1'. The test succeeds as the certificates agree.

WLpair takes 4 rounds on 'G0' and 'G2'. The test fails as the certificates disagree. Indeed 'G0' has a cycle of length 5, while 'G2' doesn't, thus 'G0' and 'G2' cannot be isomorphic.

WLpair takes 4 rounds on 'G1' and 'G2'. The test fails as the certificates disagree. From the previous two instances we already know $G_{1}\cong G_{0}\not \cong G_{2}$ .

G0 vs. G1	G0 vs. G2	G1 vs. G2

Indeed G0 and G1 are isomorphic. Any isomorphism must respect the components and therefore the labels. This can be used for kernelization of the graph isomorphism problem. Note that not every map of vertices that respects the labels gives an isomorphism. Let $\varphi :G_{0}\rightarrow G_{1}$ and $\psi :G_{0}\rightarrow G_{1}$ be maps given by $\varphi (a)=D,\varphi (b)=C,\varphi (c)=B,\varphi (d)=E,\varphi (e)=A$ resp. $\psi (a)=B,\psi (b)=C,\psi (c)=D,\psi (d)=E,\psi (e)=A$ . While $\varphi$ is not an isomorphism $\psi$ constitutes an isomorphism.

When applying WLpair to G0 and G2 we get for G0 the certificate 7_7_8_9_9. But the isomorphic G1 gets the certificate 7_7_8_8_9 when applying WLpair to G1 and G2. 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. Note that although G1 and G2 can get distinct certificates when WLtest is executed on them separately, they do get the same certificate by WLpair.

The next example is about regular graphs. 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.

All four graphs are pairwise non-isomorphic. G8_00 has two connected components, while the others do not. G8_03 is 5-regular, while the others are 3-regular. G8_01 has no 3-cycle while G8_02 does have 3-cycles.

WLtest applied to four regular graphs of order 8.	WLpair applied to G8_00 and G8_01 of same degree.	WLpair applied to G8_02 and G8_03 of distinct degree.

Another example of two non-isomorphic graphs that WLpair cannot distinguish is given here.^[6]

Applications

Weisfeiler Leman graph kernels

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. 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.^[7] These Weisfeiler Leman graph kernels have attracted considerable research in the decade after their publication.^[1]

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.^{[citation needed]}

References

^ ^a ^b Huang, Ningyuan; Villar, Soledad (2022), "A Short Tutorial on the Weisfeiler-Lehman Test and Its Variants", ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533–8537, arXiv:2201.07083, doi:10.1109/ICASSP39728.2021.9413523, ISBN 978-1-7281-7605-5, S2CID 235780517
^ Weisfeiler, B. Yu.; Leman, A. A. (1968). "A Reduction of a Graph to a Canonical Form and an Algebra Arising during This Reduction" (PDF). Nauchno-Technicheskaya Informatsia. 2 (9): 12–16. Retrieved 2023-10-28.
^ Andrey Leman (1999). "Letter of A. Leman" (PDF). Retrieved 2025-02-17. Germans certainly believe that every Leman is a hidden Lehman.
^ Bieber, David (2019-05-10). "The Weisfeiler-Lehman Isomorphism Test". Retrieved 2023-10-28.
^ Kiefer, Sandra (2020). Power and limits of the Weisfeiler-Leman algorithm (PhD thesis). RWTH Aachen University. Retrieved 2023-10-29.
^ Bronstein, Michael (2020-12-01). "Expressive Power Of Graph Neural Networks And The Weisfeiler-Lehman Test". Retrieved 2023-10-28.
^ Shervashidze, Nino; Schweitzer, Pascal; Van Leeuwen, Erik Jan; Mehlhorn, Kurt; Borgwardt, Karsten M. (2011). "Weisfeiler-lehman graph kernels". Journal of Machine Learning Research. 12 (9): 2539−2561. Retrieved 2023-10-29.

[WLtutorial-1] Huang, Ningyuan; Villar, Soledad (2022), "A Short Tutorial on the Weisfeiler-Lehman Test and Its Variants", ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533–8537, arXiv:2201.07083, doi:10.1109/ICASSP39728.2021.9413523, ISBN 978-1-7281-7605-5, S2CID 235780517

[WL68-2] Weisfeiler, B. Yu.; Leman, A. A. (1968). "A Reduction of a Graph to a Canonical Form and an Algebra Arising during This Reduction" (PDF). Nauchno-Technicheskaya Informatsia. 2 (9): 12–16. Retrieved 2023-10-28.

[3] Andrey Leman (1999). "Letter of A. Leman" (PDF). Retrieved 2025-02-17. Germans certainly believe that every Leman is a hidden Lehman.

[4] Bieber, David (2019-05-10). "The Weisfeiler-Lehman Isomorphism Test". Retrieved 2023-10-28.

[kiefer-5] Kiefer, Sandra (2020). Power and limits of the Weisfeiler-Leman algorithm (PhD thesis). RWTH Aachen University. Retrieved 2023-10-29.

[6] Bronstein, Michael (2020-12-01). "Expressive Power Of Graph Neural Networks And The Weisfeiler-Lehman Test". Retrieved 2023-10-28.

[7] Shervashidze, Nino; Schweitzer, Pascal; Van Leeuwen, Erik Jan; Mehlhorn, Kurt; Borgwardt, Karsten M. (2011). "Weisfeiler-lehman graph kernels". Journal of Machine Learning Research. 12 (9): 2539−2561. Retrieved 2023-10-29.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Weisfeiler-Leman-based Graph Isomorphism heuristics

Examples

Applications

Weisfeiler Leman graph kernels

See also

References