License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.2
URN: urn:nbn:de:0030-drops-144429
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14442/
Go to the corresponding LIPIcs Volume Portal

Grohe, Martin

A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)

pdf-format:
LIPIcs-MFCS-2021-2.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{grohe:LIPIcs.MFCS.2021.2,
  author =	{Grohe, Martin},
  title =	{{A Deep Dive into the Weisfeiler-Leman Algorithm}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14442},
  URN =		{urn:nbn:de:0030-drops-144429},
  doi =		{10.4230/LIPIcs.MFCS.2021.2},
  annote =	{Keywords: Weisfeiler-Leman algorithm, graph isomorphism, counting homomorphisms, finite variable logics}
}

Keywords: Weisfeiler-Leman algorithm, graph isomorphism, counting homomorphisms, finite variable logics
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI