====== Graph Data Mining (SoSe 2016) ====== | Titel | Graph Data Mining | | Veranstalter | [[staff:kriege|Dr. Nils Kriege]] | | Veranstaltungsart | Seminar (Diplom, Master [[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Master_Inf/Pflichtveranstaltungen/INF-MSc-102.pdf|INF-MSc-102]]) | | Veranstaltungsnummer | [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=174836&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|041410]] | | SWS | 2 | | Max. Teilnehmer | 12 | ===== Inhalt ===== 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. Hierzu werden Techniken aus dem Bereich des Data Minings mit Graphenalgorithmen kombiniert und es ergeben sich neue graphentheoretische Probleme, deren effiziente Lösung sowohl von hohem theoretischem wie auch praktischem Interesse ist. Im Rahmen des Seminars möchten wir uns mit ausgewählten aktuellen Veröffentlichungen aus dem Bereich des //Graph Data Minings// befassen, die auf internationalen Konferenzen oder in Zeitschriften erschienen sind. ===== Themen ===== /* * **Die Themenvergabe erfolgt im Rahmen der Vorbesprechung.** * **Die Themenliste ist vorläufig und kann sich noch ändern.** */ ^ Nr. ^ Thema ^ Teilnehmer ^ Betreuer ^ |**Enumeration maximaler Cliquen** ||| | 1.| [[http://dx.doi.org/10.1007/978-3-642-17517-6_36|Listing All Maximal Cliques in Near-Optimal Time]], D. Eppstein, M. Löffler, D. Strash, ISAAC 2010.\\ [[http://dx.doi.org/10.1007/978-3-642-20662-7_31|Listing All Maximal Cliques in Large Sparse Real-World Graphs]], D. Eppstein, D. Strash, SEA 2011. | Abdurrahman Abodahab | [[staff:kriege|Nils Kriege]] | |**Metriken für Graphen** |||| | 2.| [[http://arxiv.org/abs/1501.06774|Maximum Common Subelement Metrics and its Applications to Graphs]], L. Lins, N. Ferreira, J. Freire, C. Silva, arXiv:1501.06774, 2015. | Uwe Jentsch | [[staff:kriege|Nils Kriege]] | |**Kernfunktionen für Graphen** |||| | 4.| [[http://dx.doi.org/10.1145/2783258.2783417|Deep Graph Kernels]], P. Yanardag, S.V.N. Vishwanathan, KDD 2015. | Tolgay Usul | [[staff:morris|Christopher Morris]] | | 6.| [[http://epubs.siam.org/doi/10.1137/1.9781611974010.32|Cheetah: Fast Graph Kernel Tracking on Dynamic Graphs]], L. Li,H. Tong, Y. Xiao, W. Fan, SDM 2015. | Kevin Nikiel | [[staff:kriege|Nils Kriege]] | |**Subgraph Mining** |||| | 7.| [[http://doi.acm.org/10.1145/1376616.1376662|Mining significant graph patterns by leap search]], X. Yan, H. Cheng, J. Han, P.S. Yu, SIGMOD 2008. | Peter Schottky | [[staff:schaefer|Till Schäfer]] | | 8.| [[http://dx.doi.org/10.1109/ICDE.2009.133|GraphSig: A Scalable Approach to Mining Significant Subgraphs in Large Graph Databases]], S. Ranu, A.K. Singh, ICDE 2009. | Dennis Gaidel | [[staff:kriege|Nils Kriege]] | | 9.| [[http://dx.doi.org/10.1002/sam.10084|Discriminative frequent subgraph mining with optimality guarantees]], M. Thoma, H. Cheng, A. Gretton, J. Han, H.-P. Kriegel, A.J. Smola, L. Song, P.S. Yu, X. Yan, K.M. Borgwardt, Statistical Analysis and Data Mining 3(5): 302-318, 2010. | Joe Volmer | [[staff:schaefer|Till Schäfer]] | | 10.| [[http://dx.doi.org/10.1145/1835804.1835905|Semi-supervised feature selection for graph classification]], X. Kong, P.S. Yu, KDD 2010. | Xiaoting Shao | [[staff:kriege|Nils Kriege]] | |**Partitionierung von Molekülgraphen** |||| | 12.| [[http://dx.doi.org/10.1007/978-3-642-29627-7_3|Charge Group Partitioning in Biomolecular Simulation]], S. Canzar, M. El-Kebir, R. Pool, K. Elbassioni, A.K. Malde, A.E. Mark, D.P. Geerke, L. Stougie, G.W. Klau, RECOMB 2012. | Lutz Oettershagen | [[staff:kriege|Nils Kriege]] | /* |**Colour Refinement** |||| | 13.| [[http://dx.doi.org/10.1007/978-3-642-40450-4_13|Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement]], C. Berkholz, P.S. Bonsma, M. Grohe, ESA 2013. | | [[staff:kriege|Nils Kriege]] | | 14.| [[http://dx.doi.org/10.1007/978-3-662-44777-2_42|Dimension Reduction via Colour Refinement]], M. Grohe, K. Kersting, M. Mladenov, E. Selman, ESA 2014. | | [[staff:kriege|Nils Kriege]] | */ /* | 3.| [[https://papers.nips.cc/paper/5880-a-structural-smoothing-framework-for-robust-graph-comparison.pdf|A Structural Smoothing Framework For Robust Graph Comparison]], P. Yanardag, S.V.N. Vishwanathan, NIPS 2015. | Sebastian Humann | [[staff:morris|Christopher Morris]] | | 5.| [[http://cs.ucsb.edu/~fhan/paper/dmk.pdf|A Fast Kernel for Attributed Graphs]], Y. Su, F. Han, R. E. Harang, X. Yan, SDM 2016. | Annika Nehrke | [[staff:kriege|Nils Kriege]] | */ ===== Zeitplan ===== | ^ Montag, 01.08.2016 ^ Dienstag, 02.08.2016 ^ ^ 10:15 -- 11:15 | **Enumeration maximaler Cliquen** \\ Abdurrahman Abodahab | **Mining significant graph patterns by leap search** \\ Peter Schottky | ^ 11:15 -- 12:15 | **Partitionierung von Molekülgraphen** \\ Lutz Oettershagen | **GraphSig: A Scalable Approach to Mining Significant Subgraphs in Large Graph Databases** \\ Dennis Gaidel | ^ 12:15 -- 13:30 | **Mittagspause** | **Mittagspause** | ^ 13:30 -- 14:30 | **Metriken für Graphen** \\ Uwe Jentsch | **Discriminative frequent subgraph mining with optimality guarantees** \\ Joe Volmer | ^ 14:30 -- 15:30 | **Deep Graph Kernels** \\ Tolgay Usul | **Semi-supervised feature selection for graph classification** \\ Xiaoting Shao | ^ 15:30 -- 16:30 | **Cheetah: Fast Graph Kernel Tracking on Dynamic Graphs** \\ Kevin Nikiel | **Abschlussrunde** | ^ ::: | ::: | | ===== Ablauf & Termine ===== Die Themenverteilung erfolgt während der Vorbesprechung. Im weiteren Verlauf des Semesters haben die Teilnehmer Zeit, die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben, jedoch ggf. Einzelgespräch zum zugeordneten Thema. Es handelt sich um ein Blockseminar. Alle Teilnehmer halten kurz nach Ende der Vorlesungszeit einen **45-minütigen** Vortrag über das festgelegte Thema. Im Anschluss folgt eine ca. 15-minütige Diskussion über Thema und Vortrag. Es herrscht Anwesenheitspflicht bei allen Vorträgen. Bitte beachten Sie auch die [[http://ls11-www.cs.tu-dortmund.de/people/chimani/seminarfolien.html|Hinweise]] zur Foliengestaltung! Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen **Ausarbeitung**, welche **14-18 Seiten** umfasst und mit **LaTeX** erstellt wird ({{:teaching:ausarbeitung-ae2013.zip|Vorlage}}). Nach der Abgabe der Ausarbeitung besteht einmalig die Gelegenheit, die Ausarbeitung auf Grundlage der Rückmeldung des Betreuers zu überarbeiten. Mangelhafte Ausarbeitungen und 1:1-Übersetzungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Seminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen. ^ Termin ^ Datum ^ Zeit ^ Ort ^ | **Vorbesprechung** | **14.04.2016** | **14:15 -- 15:45** | R202, OH14 | | Abgabe des Ausarbeitungskonzepts | 29.05.2016 | 23:59 | --- | | Abgabe der Ausarbeitung | 12.06.2016 | 23:59 | --- | | Abgabe der Ausarbeitung (Überarbeitete Version) | 03.07.2016 | 23:59 | --- | | Abgabe der Präsentationsfolien (Konzept) | 10.07.2016 | 23:59 | --- | | Abgabe der Präsentationsfolien | 17.07.2016 | 23:59 | --- | | **Vorträge** | **01.08.2016** | **10:15 -- 16:30** | R202, OH14 | | | **02.08.2016** | **10:15 -- 16:00** | R202, OH14 | ===== Anmeldung ===== Eine Anmeldung zum Seminar ist nicht mehr möglich, da bereits die maximale Teilnehmerzahl erreicht wurde. /* Die Anmeldung erfolgt per E-Mail an [[staff:kriege|Nils Kriege]] bis zum Mittwoch, den **13.04.2015**. Da die Teilnehmerzahl beschränkt ist, können nur die ersten 12 Anfragen berücksichtigt werden. Eine erfolgreiche Anmeldung wird durch eine E-Mail bestätigt. */ Die Themenverteilung erfolgt im Rahmen der Vorbesprechung (Termin siehe [[#ablauf_termine|unten]]).