Skip to main content

Graph Learning: Embeddings, Matchings and Expressivity

Nils M. Kriege
Wednesday, January 25, 2023, 12:00 pm – 1:00 pm

ABSTRACT / Data mining and machine learning for structured data is becoming increasingly important in domains such as social network analysis, computer vision, recommender engines, or chem- and bioinformatics. In this talk, I give an overview of my work in this area. The talk is divided into three closely connected parts.

(i) Graph kernels are specific similarity measures for graphs, which enable the application of established machine learning approaches such as support vector machines to graphs. I will present kernels based on Walks and Weisfeiler-Lehman refinement and their relation in terms of expressivity.

(i) The maximum common subgraph problem asks for a largest substructure that is contained in two given graphs. The problem is NP-hard in general. I introduce polynomial-time algorithms for trees and tree-like graphs. Motivated by constraints relevant in cheminformatics a variation of the problem is formalized and solved efficiently in series-parallel graphs.

(iii) Graph neural networks extend deep learning techniques, which have been proven to be extremely successful for data such as images, to directly operate on graphs. I will present a technique for deep graph matching, which learns and refines feature representations to reach a consensus mapping.

BIO / Nils M. Kriege is assistant professor and leader of the work group "Machine Learning with Graphs" at the Faculty of Computer Science at the University of Vienna. He received his PhD from the TU Dortmund University in 2015, was a visiting researcher at the University of York, and held an interim professorship for Algorithm Engineering at the TU Dortmund University. In 2019 he was awarded a WWTF Vienna Research Group for the project "Algorithmic Data Science for Computational Drug Discovery" and joined the University of Vienna in 2020. His research focuses on developing methods for data mining and machine learning with graphs by solving problems at the boundaries of machine learning, graph theory, and algorithmics. He contributes techniques to the broad topics of graph embedding, graph matching, and graph search in large databases. His ambition is to develop methods that are useful for solving concrete problems in real-world applications, especially in computational drug discovery. His research has been published in top-tier machine learning and data mining venues, including the International Conference on Machine Learning (ICML), the Conference on Neural Information Processing Systems (NeurIPS), and the IEEE International Conference on Data Mining (ICDM).