Algorithmic Data Science on Graphs

Petra Mutzel is professor of Computational Analytics at the University of Bonn, where she is also the scientific director of the High Performance Computing and Analytics Lab at the Digital Science Center.

She received her Ph.D. in Computer Science at the University of Cologne in 1994, followed by a PostDoc position at the Max Planck Institute for Informatics in Saarbrücken and by professorships at the Vienna University of Technology from 2000 to 2004 and TU Dortmund University from 2004 to 2019.

Her research focuses on algorithm engineering, algorithmic data analysis, and combinatorial optimization for graphs and networks. Currently, the main application areas are in cheminformatics, social and biological network analysis,  statistical physics, brain networks, and geodesy.

She is a member of the Steering Committees of ESA, ALENEX, and WALCOM, and Associate Editor of the ACM Journal on Experimental Algorithmics, Journal of Graph Algorithms and Applications (JGAA), and Mathematical Programming Computation (MPC). She is also a member of the supervisory board of CISPA, the advisory board of the Fraunhofer SCAI, and the scientific advisory board of FRIAS.

Abstract: 

The area of algorithmic data science offers new opportunities for researchers in the algorithmic community. In this talk we will see examples that show that algorithm engineering is the perfect foundation for algorithmic data science.

In the first part of my talk, we will discuss Weisfeiler-Leman based approaches which is an important ingredient for Babai’s quasi-polynomial time algorithm for solving the graph isomorphism problem, and which is increasingly applied for analysis tasks on graph data sets. I will present new local versions for the k-dimensional Weisfeiler-Leman approach, which takes into account the local structure of the graph. We will also discuss their strengths and weaknesses for data analysis. Applications are, e.g., learning tasks in drug design, social network analysis, brain network analysis, and geodesy.

In the second part I will present the results of our experimental evaluation of the quantum processing unit of the D-Wave 2000Q that is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and to maximum cut problems on the associated graphs. In our experiments we compute exact solutions by engineered branch and cut approaches based on integer linear programming and examine how reliably the D-Wave computer can deliver true optimum solutions of the Ising problem. We also compare the annealer’s performance in terms of solution time and solution quality with the performance of a heuristic based on bounded tree width graphs and present some surprising results.