Seminar: Graph Kernels

• Course codes: B-AUK-S→ATTI-BS ·M-AuK-S-K→ATTI-MS
• External links: qis

Inhalt

Das Seminar deckt die gesamte Bandbreite von theoretischen Grundlagen bis zur praktischen Umsetzung des maschinellen Lernens auf Graphen an, insbesondere wird es um graph similarity und graph kernels gehen. Das Thema liegt an der Schnittstelle zwischen Graphentheorie, Theorie der Algorithmen, und maschinellem Lernen. Das Seminar bietet einen Einblick in aktuelle Forschungsfragen und ist für Master- und fortgeschrittene Bachelorstudent:innen der Informatik und der Mathematik geeignet.

Manche Themen sind rein theoretischer Natur (Graphentheorie, Graphalgorithmen, Komplexität) und manche Themen sind praktischer Natur (Implementierung, Evaluation). Sie können sich zu Beginn des Seminars für ein Thema und damit einen Fokus entscheiden.

Dozent:in

• Holger Dell
• Hilde Kuehne
• Anselm Haak
• Leo Krull

Ablauf

• Die Vorbesprechung findet am Mittwoch, dem 6.4., um 14:00-14:45 statt und dient der Themenvergabe.
• Das Seminar findet während der Vorlesungszeit voraussichtlich jede Woche Dienstag 8:30-10:00 Uhr in Bockenheim H9 statt.
• Vorläufige Planung:
  • Woche 1: “Wie hält man einen Vortrag?”
  • Woche 2-6: Abschnittsweises gemeinsames Lesen von Morris et al. (2021)
  • Woche 7: Pause
  • Woche 8-9: Abschnittsweises gemeinsames Lesen von Morris et al. (2021)
  • Woche 10-12: Pause
  • Woche 13-14: Zehn Vorträge an 4 Terminen:
    • Dienstag, 5. Juli 8:30 - 10:00 Uhr
      • Melvin: An optimal lower bound on the number of variables for graph identification
      • Jonas: The Iteration Number of Colour Refinement
    • Freitag, 8. Juli 13:15 - 16:00 Uhr
      • Jad: The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
      • Alex: Deep Weisfeiler-Leman
    • Dienstag, 12. Juli 8:30 - 10:00 Uhr
      • Stephan: The Exact Class of Graph Functions Generated by Graph Neural Networks
      • Jasper: ?
    • Mittwoch, 13. Juli 13:15 - 16:00 Uhr
      • Maike: TUDataset: A collection of benchmark datasets for learning with graphs
      • Theresa: Graphonomy: Universal Image Parsing via Graph Reasoning and Transfer

Literaturliste

Übersichtsartikel.

• Morris et al. (2021): Weisfeiler and Leman go Machine Learning: The Story so far

Theoretische Ergebnisse und Experimente zur Mächtigkeit von GNNs.

• Keyulu Xu et al. (2019): How Powerful Are Graph Neural Networks?
  GNNs für ungewichtete, ungelabelte Graphen sind bestenfalls genauso mächtig wie 1-WL.

• Fereydounian et al. (2022): The Exact Class of Graph Functions Generated by Graph Neural Networks
  Eine Charakterisierung der Mächtigkeit von GNNs für Graphen mit Gewichten.

• Morris et al. (2019): Weisfeiler and Leman go neural: Higher-order graph neural networks
  Höherstufige GNNs als Analogon zu k-WL.

Anwendungen in Machine Learning.

• Lin et al. (2021): Graphonomy: Universal Image Parsing via Graph Reasoning and Transfer

• Shervashidze et al. (2011): Weisfeiler-Lehman Graph Kernels
  Eines der ersten Publikationen, die WL als Graph Kernels benutzt.

Theoretische Ergebnisse zur Mächtigkeit von Weisfeiler-Leman.

• Cai, Fürer, Immerman: An optimal lower bound on the number of variables for graph identification
  Ein klassisches Ergebnis, in dem Graphen konstruiert werden, die von k-WL unterschieden werden aber von (k-1)-WL nicht.

• Kiefer and McKay (2020): The Iteration Number of Colour Refinement
  Ein spannendes Ergebnis, das zeigt, dass es unendlich viele Graphen gibt, für die Colour Refinement n-1 Runden braucht.

• Grohe, Schweitzer, Wiebking (2021): Deep Weisfeiler Leman
  Eine Variante von Weisfeiler Leman, die noch mehr Graphen unterscheidet

• Kiefer, Ponomarenko, Schweitzer (2019): The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
  Ein fantastischer Durchbruch, der zeigt, dass man alle planaren Graphen mit 3-WL identifizieren kann.

• Grohe and Kiefer (2021): Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
  Ein erstaunliches Ergebnis, das zeigt, dass k-WL planare Graphen schon nach O(log n) Runden identifiziert, sofern k groß genug ist.

• Dvorák (2006): On recognizing graphs by numbers of homomorphisms und Dell, Grohe, Rattan (2018): Lovász Meets Weisfeiler and Leman.
  Eine Charakterisierung von k-WL durch Homomorphismenzahlen von Graphen beschränkter Baumweite.

• Grohe, Rattan, Seppelt (2021): Homomorphism Tensors and Linear Equations
  Eine schöne Charakterisierung von k-WL durch Homomorphismentensoren und Lineare Gleichungssysteme.

Lernziele

Nach dem Seminar kann der:die Student:in:

• Wissenschaftlichen Vorträgen aktiv zuhören und sich an Diskussionen beteiligen,
• Fachliteratur auf fortgeschrittenem Forschungsniveau eigenständig lesen und dabei Verständnisfragen identifizieren,
• wissenschaftliche Inhalte auf didaktisch geeignete Weise in einem Vortrag vermitteln und reflektiert einordnen,
• Forschungsinhalte den wissenschaftlichen Konventionen folgend schriftlich darstellen und reflektiert einordnen,
• didaktische Aspekte eines Vortrags und eines wissenschaftlichen Schriftstücks bewerten und diskutieren.

Formale Anforderungen

Um das Seminar zu bestehen, werden folgende Aktivitäten erwartet:

• Einen kurzen (~15 Minuten) Vortrag über einführende Grundlagen halten,
• einen längeren (~40 Minuten) Vortrag über ein fortgeschrittenes Thema halten,
• sich aktiv an der Diskussion beteiligen,
• eigenständig offene Fragen identifizieren und das Lehrpersonal vor dem Vortrag hierzu befragen,
• 7 Tage vor jedem Vortrag: einen Entwurf der Folien oder des geplanten Tafelanschriebs an das Lehrpersonal senden. Darauf erhalten Sie dann in einem persönlichen Gespräch Feedback, das Sie in den Vortrag einarbeiten.
• 7 Tage nach dem langen Vortrag: eine Ausarbeitung (maximal vier Seiten) an zwei andere Studierende senden. Der Vortrag fasst das Material in eigenen Worten zusammen, nennt Referenzen, und stellt Zusammenhänge zu anderen Themen des Buchs her.
• 14 Tage nach dem langen Vortrag: Sie erhalten Feedback von den anderen Studierenden,
• 21 Tage nach dem langen Vortrag: die endgültige Version der Ausarbeitung zur Bewertung an das Lehrpersonal senden.

Bewertung

Nach jedem Vortrag gibt es eine offene Feedbackrunde im Plenum und eine geschlossene Feedbackrunde im Einzelgespräch. Die vorläufige Benotung erfolgt direkt nach dem Vortrag. Bewertet werden:

• Inwiefern haben Sie inhaltliche Fragen vor dem Vortrag geklärt?
• Wie haben Sie sich an die zeitliche Vorgabe gehalten?
• Wie effektiv haben Sie während des Vortrags Fragen beantwortet?
• Wie intensiv haben Sie sich an Diskussionen beteiligt? (hierbei zählen sowohl aktive Fragen als auch hilfreiche Antworten)
• Wie gut haben Sie die Inhalte des Vortrags selbst durchdrungen?
• Wie nützlich waren die im Vortrag gezeigten Visualisierungen?
• Wie verständlich konnten Sie die Inhalte des Vortrags an die anderen Studierenden vermitteln?
• Wie unterhaltsam war Ihr Vortrag?
• Je kürzer oder einfacher das Paper ist, desto mehr Wert wird auf den Vortragsstil, das selbstständige Arbeiten, die Darstellung der umliegenden Literatur, und die Motivation gelegt (also z.B. warum ist das Paper interessant und auf welche Forschungsfragen hat das Ergebnis einen Einfluss?). Alternativ können Sie auch zwei kurze Paper bearbeiten.

Allgemeine Tipps

• Zeit für die Vorbereitung. Lesen kann sehr viel Zeit in Anspruch nehmen. Fangen Sie so früh wie möglich an.
• Nicht verzweifeln. Es ist ganz natürlich, dass Sie die Hälfte der Begriffe nicht verstehen werden. Das geht mir oft genauso. Gehen Sie systematisch Begriff für Begriff vor, und klären Sie für jeden einzelnen Begriff, was er bedeutet. Schreiben Sie sich auf, was sie gelernt haben.
• Zeit für den Vortrag. Die vorgegebene Zeit geht viel schneller vorbei, als Sie zunächst denken. Ich rechne mit ca. 1-2 Minuten pro Folie.
• Stellen Sie Fragen. Nichts ist langweiliger, als ein Vortrag, bei dem Sie auf Folie 2 die Definition eines Hinzlipunzli nicht verstanden haben, weil der Vortragende darüber etwas zu schnell hinwegging. Übernehmen Sie Verantwortung und fragen Sie aktiv! Unwissenheit ist keine Peinlichkeit, sondern eine spannende Gelegenheit, etwas zu lernen.
• Seien Sie ehrlich. Es wird nicht erwartet, dass Sie alles wissen oder jede Frage beantworten können. Wenn Sie verwirrt sind, etwas nicht verstehen, oder einen Teil des Inhalts aus Zeitgründen nicht detailliert lesen konnten, stehen Sie dazu. Das ist wissenschaftliches Arbeiten.
• Seien Sie witzig. Bauen Sie einen Witz oder einen Spaß in den Vortrag ein (aber auf keinen Fall mehr als zwei Witze).
• Weniger ist mehr. Gehen Sie lieber bei wenigen Unterthemen in die Tiefe, als alles nur halbgar und halbverständlich anzureißen.