Machine Learning meets Graph Theory

-- a match made in heaven --

MSc Seminar, Summer Semester 2021, Prof. Fred Hamprecht

Graphs, with their rich combinatorial structure, are a perfect representation for complex but discrete phenomena and relationships. Applications range from molecules via biological pathways all the way to social networks and epidemiology.

[Image credit: ]

While they pose intriguing and fascinating analysis problems, they do not trivially lend themselves to standard machine learning methods, making the development of appropriate techniques all the more interesting. In other words, most machine learning methods are designed to operate on "flat" or unstructured inputs, such as a vector of numbers; and they are only expected to create flat output. In contrast, obtaining generic graph-valued predictions is still an open research problem!

In this advanced seminar, we will study methods to

Take a look at some of the papers to get a feeling for the flavor. The references given above are not yet definitive. In any case, participants are expected to conduct their own literature search.


There will be a total of 12 presentations. Participants are expected to attend all presentations. The seminar will take place either in-person or online, depending on your preference and the availability of a suitable room.

Eligibility for your degree

By default, this is a "MSc Pflichtseminar" in the Physics MSc program. Participants are expected to give a presentation and prepare a written report to earn 6CP. Students from other courses or programs who do not want to write a report can earn 2CP with their presentation.


You should have followed a first course in either graph theory or machine learning (or closely related fields).


This is a three step process.

  1. You send me an email expressing your (non-binding) interest in taking part. Please
    • state towards which degree you are studying
    • in which semester you will be in summer semester 2021
    • list your previous courses and / or experience in machine learning or graph theory
    • enclose your transcript of records
  2. We convene (virtually, details follow) for a preparatory meeting in the first week of the teaching term. If there is an excessive number of applications, I will shortlist according to prior experience and performance. In the preparatory meeting, we will also decide on a time slot for the seminar for the rest of the semester. If it works for most of you, the seminar will take place on Thursdays 1130-1300.
  3. In the preparatory meeting, I briefly introduce all twelve topics. If you decide that you do want to participate in the seminar, you let me know which are your three favorite topics. I will try and solve the constraint satisfaction problem as best I can. If, as a result, I offer you a topic, this is binding for both sides: you have committed to taking part in the seminar, and I have committed to offering you a slot.

P.S. Why "a match made in heaven"?

Well, the most rewarding relations are not necessarily the obvious ones. The idea is also to grow in a relation, and graph theory and machine learning, in theirs, certainly do...

I am looking forward to a great seminar with you!