• Zeit: Freitag, 10:15–11:45 Uhr
• Ort: Raum 202, OH14
• Beginn: Freitag, 21.10.2016
• Abschlusspräsentationen: Freitag, 24.02.2017, 9:00 Uhr

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.

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

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.

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.

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.

• Reverse search for enumeration, Abschnitt 3.4
  Avis, D. & Fukuda, K.
  Discrete Applied Mathematics, 1996, 65, 21 - 46
• Efficient Graphlet Kernels for Large Graph Comparison, Abschnitt 4.1
  Shervashidze, N.; Vishwanathan, S.; Petri, T. H.; Mehlhorn, K. & Borgwardt, K. M.
  International Conference on Artificial Intelligence and Statistics (AISTATS), 2009
• Triangle Listing Algorithms: Back from the Diversion
  Ortmann, M. & Brandes, U.
  Workshop on Algorithm Engineering and Experiments (ALENEX), 2014
• A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality
  Khaled M. Elbassioni
  J. Graph Algorithms Appl. 19(1): 273-280 (2015); arXiv:1411.2262

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.

• Efficient Graphlet Kernels for Large Graph Comparison, Abschnitt 4.2
  Shervashidze, N.; Vishwanathan, S.; Petri, T. H.; Mehlhorn, K. & Borgwardt, K. M.
  International Conference on Artificial Intelligence and Statistics (AISTATS), 2009
• Efficient Graphlet Counting for Large Networks
  Ahmed, N. K.; Neville, J.; Rossi, R. A. & Duffield, N.
  IEEE International Conference on Data Mining (ICDM), 2015
• Quad Census Computation: Simple, Efficient, and Orbit-Aware
  Ortmann, M.; Brandes, U.
  Advances in Network Science (NetSci-X), 2016

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).

• Efficient Graphlet Kernels for Large Graph Comparison, Abschnitt 3
  Shervashidze, N.; Vishwanathan, S.; Petri, T. H.; Mehlhorn, K. & Borgwardt, K. M.
  International Conference on Artificial Intelligence and Statistics (AISTATS), 2009
• Sampling Connected Induced Subgraphs Uniformly at Random
  Lu, X. & Bressan, S.
  International Conference on Scientific and Statistical Database Management (SSDBM), 2012

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.

• On the Power of Color Refinement, Abschnitt 2
  Arvind, V.; Köbler, J.; Rattan, G; & Verbitsky, O.
  Fundamentals of Computation Theory (FCT), 2015
• Network Analysis: Methodological Foundations, Kapitel 12
  Brandes, U.; Erlebach, T.
  Springer, 2005

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.

• Network Analysis: Methodological Foundations, Kapitel 11
  Brandes, U.; Erlebach, T.
  Springer, 2005

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.

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

• Managing and Mining Graph Data
  Advances in Database Systems, Volume 40, 2010
  Aggarwal, Charu C.; Wang, Haixun (Eds.)

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