Learning with Graphs: Graph Neural Networks and the Weisfeiler-Leman algorithm

Graph-structured data is ubiquitous across domains ranging from chemo- and bioinformatics to image and social network analysis. 
To develop successful machine learning models in these domains, we need techniques mapping the graph's structure to a vectorial 
representation in a meaningful way---so-called graph embeddings. Starting from the 1960s in chemoinformatics, different research 
communities have worked in the area under various guises, often leading to recurring ideas. Moreover, triggered by the resurgence 
of (deep) neural networks, there is an ongoing trend in the machine learning community to design permutation-invariant or -equivariant 
neural architectures capable of dealing with graph input, often denoted as neural graph networks (GNNs). However, although often successful 
in practice, GNN's capabilities and limits are understood to a lesser extend. In this talk, we overview some results shedding some light on the 
limitations and capabilities of GNNs by leveraging tools from graph theory and related areas.