+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************

Zeit: Montag, 16. März 2020, 10:45 Uhr Ort: Raum 9222, Gebäude E3, Ahornstr. 55

Referentin: Sandra Kiefer, M.Sc. Lehrstuhl Informatik 7

Thema: Power and Limits of the Weisfeiler-Leman Algorithm

Abstract:

The Weisfeiler-Leman (WL) algorithm is a fundamental combinatorial procedure used to classify graphs and other relational structures. Through its connections to many research areas such as logics and machine learning, surprising characterisations of the algorithm have been discovered. We combine some of these to obtain powerful proof techniques. For every k, the k-dimensional version of the algorithm (k-WL) iteratively computes a stable colouring of the vertex k-tuples of the input graph. The larger k, the more powerful k-WL becomes with respect to the distinguishability of graphs. We have studied two central parameters of the algorithm, its number of iterations until stabilisation and its dimension. The results enable a precise understanding of 1-WL, namely we have determined its iteration number and have developed a complete characterisation of the graphs for which 1-WL correctly decides isomorphism. In higher dimensions, however, the situation is different. For example, it is often not clear at all how to decide if k-WL distinguishes two particular graphs. By our results, 3-WL identifies every planar graph, which drastically improves upon all previously known bounds. Generalising this insight, we obtain the first explicit parametrisation of the WL dimension by the Euler genus of the input graph.

Es laden ein: die Dozentinnen und Dozenten der Informatik