LIPIcs.MFCS.2021.2.pdf
- Filesize: 372 kB
- 1 pages
Document
A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)
Author
Martin Grohe 
-
Part of:
Volume:
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-18
File
Document Identifiers
Author Details
Cite As Get BibTex
Martin Grohe. A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.2
Abstract
The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In my talk, I will introduce the Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph theory
- Theory of computation → Logic
Keywords
- Weisfeiler-Leman algorithm
- graph isomorphism
- counting homomorphisms
- finite variable logics
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Martin Grohe. word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 1-16, 2020. URL: https://doi.org/10.1145/3375395.3387641.
-
Martin Grohe. The logic of graph neural networks. In Proceedings of the 36th ACM-IEEE Symposium on Logic in Computer Science, 2021.
- Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color refinement and its applications. In G. Van den Broeck, K. Kersting, S. Natarajan, and D. Poole, editors, An Introduction to Lifted Probabilistic Inference. Cambridge University Press, 2021. To appear. URL: https://www.lics.rwth-aachen.de/global/show_document.asp?id=aaaaaaaaabbtcqu.
- Martin Grohe, Pascal Schweitzer, and Daniel Wiebking. Deep Weisfeiler Leman. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 2600-2614, 2021. URL: https://doi.org/10.1137/1.9781611976465.154.
-
Sandra Kiefer. The Weisfeiler-Leman algorithm: An exploration of its power. ACM SIGLOG News, 7(3):5-27, 2020.
- Christopher Morris, Matthias Fey, and Nils M. Kriege. The power of the Weisfeiler-Leman algorithm for machine learning with graphs. ArXiv, 2105.05911, 2021. URL: http://arxiv.org/abs/2105.05911.
- B.Y. Weisfeiler and A.A. Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series 2, 1968. English translation by G. Ryabov available at URL: https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.