2026-07-21T14:16:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14442 2024-03-06T10:54:01Z ddc:004 open_access

A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk) Grohe, Martin Weisfeiler-Leman algorithm graph isomorphism counting homomorphisms finite variable logics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Grohe 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.2 urn:nbn:de:0030-drops-144429 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.2 eng https://creativecommons.org/licenses/by/4.0/legalcode