License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.2
URN: urn:nbn:de:0030-drops-118634
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11863/
Go to the corresponding LIPIcs Volume Portal

Grohe, Martin

Weisfeiler and Leman’s Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk)

pdf-format:
LIPIcs-STACS-2020-2.pdf (0.2 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 the first part of my talk, I will give an introduction to the Weisfeiler-Leman algorithm and its various characterisations. In the second part I will speak about its applications, in particular about recent work relating the algorithm to graph neural networks.

BibTeX - Entry

@InProceedings{grohe:LIPIcs:2020:11863,
  author =	{Martin Grohe},
  title =	{{Weisfeiler and Leman’s Unlikely Journey from Graph Isomorphism to Neural Networks (Invited Talk)}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11863},
  URN =		{urn:nbn:de:0030-drops-118634},
  doi =		{10.4230/LIPIcs.STACS.2020.2},
  annote =	{Keywords: Weisfeiler adn Leman algorithm, Graph isomorphism, Neural network, logic, algebra, linear and semi-definite programming}
}

Keywords: Weisfeiler adn Leman algorithm, Graph isomorphism, Neural network, logic, algebra, linear and semi-definite programming
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

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