Foundations of Supervised Machine Learning with Graphs

Graph-structured data is ubiquitous across application domains ranging from chemo- and bioinformatics to image and social network analysis. To develop successful machine learning algorithms, we need techniques that map the rich information inherent in the graph structure to a vectorial representation in a meaningful way—so-called graph embeddings. Designing such embeddings comes with unique challenges. The embedding has to account for the complex structure of (real-world) networks and additional high-dimensional continuous vectors attached to nodes and edges in a (permutation) invariant way while being scalable to massive graphs or sets of graphs. Moreover, when used in supervised machine learning, the model trained with such embeddings must generalize well to new or previously unseen (graph) instances. Hence, more abstractly, designing graph embeddings results in a trade-off between (1) expressivity, (2) scalability, and (3) generalization. In this seminar, we want to discuss the current progress on the theoretical foundations of machine learning on graphs, penetrating the above-listed three challenges.</p>

Requirements for Passing

To pass the seminar, you need to fulfill the following:
  1. Give a 30-minute-long talk about your assigned paper.
  2. Write a 12- to 15-page (excluding title page) detailed report about your assigned paper.
  3. Peer-review your fellow students' reports.
  4. Attend all meetings and actively participate; see below for dates.


At the end of the semester, each student will give a 30-minute-long talk about their assigned paper. You should provide an overview of your choosen/assigned paper and highlight the most important concepts and ideas. Ideally, your presentation should give the audience (i.e., your fellow students) a good understanding of your assigned paper.


The report gives a detailed overview of the choosen/assigned paper. The required report length is 12 to 15 pages, using the provided LaTeX template. This means that after you get your paper assigned, you write your report and submit it for "peer review" by your fellow students. You will receive constructive feedback to improve the paper; afterward, you will receive additional feedback from the seminar organizers. You can then submit an updated, final version, which will be graded. Note that this means that you will also have to write some short reviews on the reports by your fellow students.


  1. More details are given during the mandatory kick-off meeting.
  2. Papers will be assigned after the kick-off meeting.
  3. The long talks will be presented in day-long block seminar.
  4. All meetings (kick-off, peer-review, and final talks) will take place in Room 228, Theaterstraße 35 - 39.


14.10.2022, 10:00   Kick-off meeting (in person), slides
10.11.2022, 24:00 Submission of report drafts
01.12.2022, 24:00 Submission of reports for peer review
14.12.2022, 24:00 Submission of peer reviews
20.12.2022, 10:00 Discussion of peer reviews (in person)
09.01.2023, 24:00 Submission of reports
16.01.2023, 24:00 Feedback by the organizers
31.01.2023, 24:00 Submission of final reports
10.02.2023, 24:00 Submission of of presentation slides
16.02.2023, 10:00 Talks (in person)


The papers can be chosen from the following list.
  1. Equivariant Subgraph Aggregation Networks (Supreet Sharma)
  2. Provably Powerful Graph Networks (Timothy Borrell)
  3. Weisfeiler and Leman Go Sparse: Towards Scalable Higher-order Graph Embeddings (Henrik Thillmann)
  4. Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited (Kristin Gnadt)
  5. Graph Neural Networks with Local Graph Parameters
  6. Generalization and Representational Limits of Graph Neural Networks (Ömer Hökelekli)
  7. Agent-based Graph Neural Networks (Timo Stoll)
  8. What Functions Can Graph Neural Networks Generate?
  9. Affinity-Aware Graph Networks