The Weisfeiler-Leman algorithm from a coalgebraic perspective

Activity: Talk or presentation typesTalk or presentation (not at a conference)Academic


This talk is about the Weisfeiler-Leman algorithm. This is an efficient algorithm to colour the vertices (and edges) of a graph in a certain way. It is used as an efficient heuristic to decide graph isomorphism and it was even long thought that it might provide a polynomial algorithm for graph isomorphism (it does not). It was recently observed that this algorithm fits the abstract theory of coalgebraic minimisation. I will explain this connection to coalgebra in detail. However, the real “power” of the WL-algorithm lies in the k-dimensional generalisation and this is harder to relate to coalgebra. We want to understand this from a coalgebraic perspective too, with the hope of bringing results from graph theory to the theory of coalgebra.
The research is work in progress. It is joint work with Tobias Kappé and Thorsten Wißmann.
Period23 Aug 2023
Event titleNetwork Types, Coalgebras, Semantics in NL
Event typeSeminar
Conference number4
LocationUtrecht, NetherlandsShow on map
Degree of RecognitionNational