The Combinatorics of Graph Comparison

Deciding graph isomorphism is one of the most fundamental computational problems whose complexity is still open. All competitive approaches to it make use of a combinatorial procedure known as the Weisfeiler—Leman algorithm, which works by computing, counting, and comparing colour occurrences in the input.

The algorithm has links to numerous other areas. For example, via its connection to logic and games, we can draw conclusions about the descriptive complexity of the structures at hand, and we can find canonical decompositions, which may be used for a comparison. Also, due to a close link to machine learning, we can deduce further insights about the general learnability of graph properties. Still, after decades of research and with all the connections that have been found, we lack a precise understanding of the expressiveness of the algorithm.

In my talk, I will shed light on the power of the algorithm to detect graph structure. I will analyse its central parameters, the dimension and the number of iterations, in the context of related disciplines and illustrate how these connections yield new canonical graph representations as well as logical and algorithmic complexity bounds.