Martin Ritzert: Learning Definable Relations in Graphs
The topic of Martin Ritzert’s Ph.D. dissertation is, broadly speaking, machine learning for logically concepts over finite graphs. He has obtained both, theoretical results on the complexity of learning in the probabilistically approximately correct (PAC) learning framework and practical/experimental results on learning with graph neural networks (GNNs). Ritzert’s theoretical work addresses algorithmic questions in a logical framework where concepts and hypotheses are described using formulas of first-order or monadic second-order logic over finite structures. Previously, learning in this framework was only studied from an informationtheoretic perspective; instead, Ritzert considered algorithms and a complexity-theoretic angle. He obtained sub-linear (in the structure) and fixed-parameter tractable learning algorithms as well as complexity-theoretic lower bounds. His practical work is concerned with the capabilities of GNNs for learning logically defined concepts. One important result is a characterisation of the expressiveness of GNNs in terms of the Weisfeiler-Leman algorithm. This led to the introduction to higher-order GNNs which have subsequently found applications, e.g., analysing molecules for fuel design. A second result is a generic architecture for solving maximum constraint satisfaction problems such as maximum 2-satisfiability using GNNs.