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

References

  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
  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. ^ Immerman, Neil; Sengupta, Rik (2019-07-22), The $k$-Dimensional Weisfeiler-Leman Algorithm, arXiv:1907.09582
  4. ^ Bronstein, Michael (2020-12-01). "Expressive Power Of Graph Neural Networks And The Weisfeiler-Lehman Test". Experfy Insights. Retrieved 2023-10-28.
  5. ^ Xu, Keyulu; Hu, Weihua; Leskovec, Jure; Jegelka, Stefanie (2019). How Powerful are Graph Neural Networks?. International Conference on Learning Representations (ICLR). arXiv:1810.00826.
  6. ^ a b Morris, Christopher; Ritzert, Martin; Fey, Matthias; Hamilton, William L.; Lenssen, Jan Eric; Rattan, Gaurav; Grohe, Martin (2019). "Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks". Proceedings of the AAAI Conference on Artificial Intelligence. 33 (1): 4602–4609. arXiv:1810.02244. doi:10.1609/aaai.v33i01.33014602.
  7. ^ Morris, Christopher; Lipman, Yaron; Maron, Haggai; Rieck, Bastian; Kriege, Nils M.; Grohe, Martin; Fey, Matthias; Borgwardt, Karsten (2023). "Weisfeiler and Leman go Machine Learning: The Story so Far". Journal of Machine Learning Research. 24: 1–59. arXiv:2112.09992.
  8. ^ 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.
This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.