Linked data arise in various domains, e.g., in chem- and bioinformatics, social network analysis and computer vision, and can be naturally represented as graphs. Therefore, machine learning and data analytics with graphs have become an active research area of increasing importance.

A prominent method used for data analytics on graphs, like, e.g., supervised graph classification with support vector machines, are graph kernels, which compute a similarity score between pairs of graphs. In the last fifteen years, a plethora of graph kernels has been published. An important class of graph kernels are Weisfeiler–Leman subtree kernels. They are based on the well-known color refinement algorithm for isomorphism testing. Our lab will explore, evaluate and extend various variants of the WL-kernels. Furthermore, we will take a look at connections to other research areas like deep learning, pebble games or linear programming.

We will design efficient exact and approximate algorithms and data structures for computational analytics problems. Our focus will be on data analytics and graph algorithms. The LAB also includes experimental evaluation and documentation of the implemented software.

In this lab we will focus on (spatio-)temporal graphs. Many real-world graphs are temporal, e.g., in a social network persons only interact at specific points in time. Additionally the graphs can be enriched with spatial information, i.e., the GPS location data of members of the network. The temporal information directs possible dissemination processes on the graph, such as the spread of rumors, fake news, or diseases. Most current state-of-the-art methods for supervised graph classification are designed mainly for static graphs and may not be able to capture temporal information. Therefore, our goal is to design and evaluate classification approaches for temporal graphs.

No prior knowledge of graph classification or kernels is required.

Keywords: Data analytics, Graph algorithms, Temporal graphs, Machine learning, Graph kernels, Deep learning, Combinatorial optimization

If you are interested in joining this lab, write an email to lutz.oettershagen [add] cs.uni-bonn.de.

The lab will be hold completely in digital manner. We will use a webconference system (Zoom or similar). Contact Lutz Oettershagen to get the invitation to the conference.

Attending the initial meeting on Wed. 22.04.20 16:00 o'clock is mandatory for joining the lab.

The weekly meetings will be Wednesday 16:00 o'clock.

In the first meeting we will give a short introduction to temporal graphs and graph classification with a focus on the Weisfeiler-Leman graph kernel. Furthermore, all organizational questions will be answered. Official registration of the students to the lab can be done in the following weeks. The exact date until when the students need to be registered will also be announced during the initial meeting.

Goal of the lab is to design new models for temporal graph classification based on existing conventional static graph kernels or graph neural networks. The models are implemented and evaluated on real-world data. We start off with a mini-seminar phase in which each participant presents a beforehand assigned paper or topic. A final presentation of the work and the results, as well as a written report is expected at the end of the lab.

The following plan will be updated regularly.

For preparation, we suggest reading the following papers.

Graph Kernels

• Shervashidze, Nino, et al. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 12.Sep (2011): 2539-2561.
• Lutz Oettershagen, et al. Temporal Graph Kernels for Classifying Dissemination Processes. SIAM International Conference on Data Mining (SDM) 2020.
• Kriege, Nils M., et al. A survey on graph kernels. Applied Network Science 5, 2020.
• Morris, Christopher, et al. Weisfeiler and Leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 2019.

Temporal Graphs

• Holme, Petter, et al. Temporal Networks. Holme, P., & Saramäki, J. (2012). Temporal networks. Physics reports, 519(3), 97-125.

Gitlab

_{DozentInnen: Mutzel, Oettershagen}