During his PhD studies, Konstantinos investigated the problem of identifying vertex correspondences between graphs, a fundamental challenge with broad applications, including user identification, knowledge transfer, fraud pattern detection, biological network analysis, and others.

His work focused on two main formulations: graph alignment and subgraph matching. In graph alignment, he developed algorithms that significantly improve mapping quality for both equal-size and different-size graphs, even under high levels of perturbation. In subgraph matching, he proposed a spectral algorithm that enhances scalability with respect to the query graph size, identified sources of bias in query answering, and introduced a new method that increases the coverage of returned nodes to mitigate this bias.

The PhD study was completed at Department of Computer Science, Faculty of Natural Sciences, Aarhus University.

This summary was prepared by the PhD student.
 

Time: Friday, 9 January 2026  at 15:00
Place: Building 5342, room 333, Ada, Aarhus University, Åbogade 34 , 8200 Aarhus N
Title of PhD thesis: Graph-based Reasoning: Effective Mapping and Planning on Graphs
Contact information: Konstantinos Skitsas, e-mail: skitsas@cs.au.dk, tel.: +45 50348586
Members of the assessment committee:
Ross Family Chair and Associate Professor Vagelis Papalexakis, Computer Science & Engineering Department, University of California Riverside, USA
Associate Professor Tianyi Li, Department of Computer Science, Aalborg University, Denmark
Associate Professor Chris Schwiegelshohn (chair), Department of Computer Science, Aarhus University, Denmark
Main supervisor:
Professor Panagiotis Karras, Department of Computer Science, Aarhus University, Denmark
Co-supervisor:
Associate Professor Davide Mottin, Department of Computer Science
Language: The PhD dissertation will be defended in English

The defence is public.
The PhD thesis is available for reading at the Graduate School of Natural Sciences/GSNS, Ny Munkegade 120, building 1521, 8000 Aarhus C