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

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), pp. 1

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.

Authors 1

1. Martin Grohe corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany

   RWTH Aachen University, Aachen, Germany