Table of Contents

Fachprojekt Algorithm Engineering for Graph Data Mining (WS 2016/2017)

Titel Algorithm Engineering for Graph Data Mining
Algorithm Engineering für das Data Mining in Graphen
Veranstalter Dr. Nils Kriege
Veranstaltungsart Fachprojekt (Modul INF-BSc-267)
Veranstaltungsnummer 040267
SWS 4

Termine

Motivation

Graphen sind elementare mathematische Strukturen, die eine Menge von Objekten und die zwischen ihnen bestehenden Verbindungen beschreiben. Soziale Netzwerke, Moleküle sowie Straßen- und Rechnernetze sind nur einige anschauliche Beispiele für strukturierte Daten, die sich durch Graphen repräsentieren lassen. Derartige Daten sind zunehmend in großen Mengen verfügbar und ihre Nutzung erfordert die automatisierte Extraktion von Informationen, die für eine spezielle Fragestellung relevant sind. Ein aktuelles Forschungsgebiet, das z.B. in der Chemie- und Bioinformatik zunehmend an Bedeutung gewinnt, befasst sich daher mit der Anwendung von Methoden des Data Mining auf Graphen. Hierbei verwendete Graphenalgorithmen sind häufig theoretisch gut untersucht und dennoch können diese Resultate oft nicht direkt auf praktische Anwendungen übertragen werden: Die konkrete Problemstellung kann sich beispielsweise durch zusätzliche Nebenbedingungen von dem theoretisch untersuchten Problem unterscheiden oder Algorithmen können spezielle Eigenschaften wie die Knotenannotationen der auftretenden Graphen ausnutzten. Algorithm Engineering beinhaltet das Design von Algorithmen, ihre theoretische Analyse, die Implementierung, sowie die experimentelle Evaluation am Rechner, wobei der Schwerpunkt auf anwendungsrelevanten Problemen liegt.

Koffein Moleküldatenbank
Strukturformel von Koffein Moleküldatenbank
Molekülgraphen wie sie z.B. in der Wirkstoffentwicklung auftreten

Aufgabe

Im Rahmen des Fachprojekts “Algorithm Engineering for Graph Data Mining” sollen graphentheoretische Probleme behandelt werden, die im vergleichsweise jungen Gebiet des Data Mining in Graphen auftreten. Mit Hilfe von Methoden des Algorithm Engineering sollen hierfür effiziente Algorithmen für die praktische Anwendung entworfen werden. Die Studierenden arbeiten dabei in Teams mit Gruppengröße 3-4 an einem anwendungsnahen Problem aus der Praxis. Hierauf wenden die Studierenden die typischen Schritte des Algorithm Engineering Kreislaufs an. Neben der Modellierung des Problems und eines Algorithmus zur Problemlösung spielt hierbei auch die Realisierung und die Evaluierung anhand praktischer Benchmarkprobleme eine wichtige Rolle.

Teilprojekte

Eine Vielzahl von klassischen Data-Mining-Verfahren ist für Vektordaten konzipiert und daher nicht direkt auf Graphen anwendbar. Ein Vorgehen, um dennoch auf diese Methoden zurückgreifen zu können, bestehen darin Graphen durch Vektoren zu repräsentieren. Hierbei entspricht z.B. jede Komponente eines Vektors der Anzahl der Vorkommen einer speziellen Substruktur. In den Teilprojekten sollen hierzu notwendige Algorithmen entwickelt, implementiert und einzeln wie im Vergleich zu anderen evaluiert werden.

Nr. Thema Betreuer Teilnehmer
A. Enumeration von Subgraphen Nils Kriege Franka Bause, Martin Rentz, Nina Runde
B. Zählen von Subgraphen Nils Kriege David Feininger, Jan Wienbrack, Andreas Plewnia
C. Sampling von Subgraphen Nils Kriege Jan Fischer, Reza Nirumand, Robert Gehde
D. Invarianten und Kanonisierung Christopher Morris Franz Nentwich, Moritz Sliwinski, Julian Meise
E. Netzwerk-Statistiken Christopher Morris Richard Treier, Alnis Murtovi, Alex Schmulbach

A. Enumeration von Subgraphen

Im Rahmen dieses Teilprojekts sollen effiziente Algorithmen zur Enumeration von Subgraphen implementiert werden. Die Größe der aufzuzählenden Lösungsmenge ist hier ein entscheide Faktor für die Laufzeit, weshalb typischerweise nur spezielle Subgraphen (z.B. zusammenhängend mit maximal 4 Knoten) aufgelistet werden sollen.

Literatur

B. Zählen von Subgraphen

Dieses Teilprojekt beschäftigt sich mit effizienten Verfahren, um die Anzahl der Vorkommen von Subgraphen zu zählen. Hierfür sind Verfahren bekannt, die eine bessere Worst-Case-Laufzeit garantieren als für die Enumeration benötigt wird.

Literatur

C. Sampling von Subgraphen

Für sehr große Graphen ist bereits das exakte Zählen von Subgraphen für praktische Anwendungen zu langsam. Hier bietet es sich an, randomisierte Verfahren zu verwenden, um eine Teilmenge aller Subgraphen zu erhalten, die für die Gesamtmenge repräsentativ ist. Hierzu sollen einerseits Verfahren genutzt werden, die (zusammenhängende) Subgraphen zufällig mit gleicher Wahrscheinlichkeit generieren, und andererseits Subgraphen, die die Umgebung von Knoten beinhalten (sogenannte k-Discs oder k-Nachbarschaftsgraphen).

Literatur

D. Invarianten und Kanonisierung

Hier sollen verschiedene Invarianten und Kanonisierungs-Verfahren für gelabelte (Sub-)Graphen entwickelt werden. Auf der einen Seite sollen einfache Invarianten wie Color-Refinement implementiert werden. Auf der anderen Seite sollen komplexere Algorithmen angepasst werden, damit sie mit Knoten-Labeln umgehen können.

Literatur

E. Netzwerk-Statistiken

Um wichtige Informationen von sehr großen Netzwerken oder Graphen darzustellen, werden oft Netzwerk-Statistiken verwendet. Üblicherweise bilden diese einen Graphen auf eine Zahl oder einen Vektor ab. Im Rahmen dieses Teilprojektes sollen einige dieser Netzwerk-Statistiken implementiert werden.

Literatur

Ablauf

In einer ersten Phase sollen grundlegende Techniken aus der ausgegebenen Literatur durch jede Gruppe implementiert werden.

In der zweiten Phase wird der Austausch zwischen den Gruppen zunehmend an Bedeutung gewinnen. Hier soll beispielsweise ein Laufzeitvergleich zwischen Algorithmen zur Enumeration und zum Zählen von Subgraphen erfolgen, wobei gleichzeitig die Korrektheit der Implementierungen überprüft wird. Indem generierte Subgraphen (Gruppen A und C) in kanonische Form gebracht werden (Gruppe D), können Graphen durch Vektoren repräsentiert werden. Parallel dazu sollen Verfahren zum Zählen von Subgraphen (Gruppe B) so angepasst werden, dass Label beachtet werden. Hierdurch können äquivalente Vektorrepräsentationen erzielt werden.

In der dritten Phase sollen die entwickelten Verfahren nicht mehr nur anhand ihrer Laufzeit bewertet werden, sondern auch ihre Eignung im Zusammenhang mit Verfahren zur Klassifikation von Graphen getestet werden. Hierzu sollen beispielsweise Datensätze mit Molekülgraphen herangezogen werden, die sich in die Klasse biologisch aktiver und inaktiver Moleküle einteilen lassen.

Literatur

Zu den einzelnen Themen wird spezielle Literatur ausgegeben. Einen Überblick über das Gebiet des Graph Data Mining bietet z.B. das folgende Buch:

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Nils Kriege.