Kernels for Large, Labeled Graphs (LaLa)

• Antragsteller: Professor Dr. Karsten Borgwardt
• Fachliche Zuordnung: Theoretische Informatik ; Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2010 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 164930347

• Erstellungsjahr: 2015

Zusammenfassung der Projektergebnisse

Graphen sind in der modernen, datenreichen Gesellschaft allgegenwärtig: Sie werden zum Beispiel eingesetzt, um Moleküle, Verkehrsflüsse oder soziale Netzwerke darzustellen. Von der Untersuchung dieser umfangreichen Graphendaten erhofft sich die Wissenschaft neue Einblicke in den Aufbau und die Funktionsweise der zugrundeliegenden Systeme, von den Natur- bis zu den Sozialwissenschaften. Die Analyse von Graphen ist jedoch aus informatischer Sicht sehr schwierig. Selbst scheinbar simple Rechenoperationen sind auf Graphen extrem aufwendig, wie zum Beispiel die Frage, ob zwei Graphen identisch (isomorph) sind oder ob ein Graph in einem anderen enthalten ist. Für keines dieser beiden Probleme gibt es eine Lösung, deren Rechenbedarf im Worst-Case nicht exponentiell mit der Anzahl der Knoten der Graphen wachsen würde. Graph-Kerne wurden im vergangenen Jahrzehnt als attraktiver neuer Ansatz vorgestellt, um Graphen effizient vergleichen zu können. Sie litten jedoch bis zu Beginn unseres Projektes unter drei fundamentalen Einschränkungen, die eine Vielzahl von möglichen Anwendungen verhinderten: 1. Sie waren nicht effizient genug, um Graphen mit Tausenden von Knoten vergleichen zu können. 2. Sie waren nicht mehr effizient berechenbar, wenn man fehlende oder falsche Kanten in den Graphen berücksichtigen wollte. 3. Sie waren nicht mehr effizient berechenbar, wenn die Attribute der Knoten nicht diskret, sondern kontinuierlich oder gar hochdimensional waren. Im Rahmen dieses Projektes wurden Lösungen für die drei obenstehenden Probleme erarbeitet und veröffentlicht. Insbesondere wurden mehrere neue Algorithmen zum Vergleich großer Graphen entwickelt, deren Laufzeit nur linear mit der Anzahl der Kanten in den Graphen wächst. Die hier erzielten Ergebnisse wurden mehrfach mit Preisen ausgezeichnet: Dr. Nino Shervashizde wurde mit dem NIPS Outstanding Student Paper Award geehrt, Prof. Dr. Karsten Borgwardt erhielt den Alfried-Krupp-Förderpreis für junge Hochschullehrer 2013 und wurde vom Wirtschaftsmagazin Capital 2014 zu den “Top 40 unter 40” in der Wissenschaft in Deutschland gezählt. Über diese Erfolge wurde vielfach in den Medien berichtet, unter anderem: Im Schwäbischen Tagblatt (http://goo.gl/1qs16I), in der Augsburger Allgemeine (http://goo.gl/NLQ5cB), im Handelsblatt Online (http://goo.gl/zZr0CV), auf N24 Online (http://goo.gl/MF5Y8R).

Projektbezogene Publikationen (Auswahl)

• Fast subtree kernels on graphs. In Advances in Neural Information Processing Systems, pages 1660–1668, 2009
  Nino Shervashidze and Karsten M Borgwardt
  
• Weisfeiler-Lehman graph kernels. The Journal of Machine Learning Research, 12:2539–2561, 2011
  Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt
  
• Scalable graph kernels. PhD thesis, Universität Tübingen, 2012
  Nino Shervashidze
  
• Efficient network-guided multi-locus association mapping with graph cuts. Bioinformatics, 29(13):i171–i179, 2013
  Chloé-Agathe Azencott, Dominik Grimm, Mahito Sugiyama, Yoshinobu Kawahara, and Karsten M. Borgwardt
  
• Geometric tree kernels: Classification of COPD from airway tree geometry. In IPMI 2013, 2013
  A. Feragen, J. Petersen, D. Grimm, A. Dirksen, J.H. Pedersen, K. Borgwardt, and M. de Bruijne
  
• Scalable kernels for graphs with continuous attributes. In C.J.C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 216–224. Curran Associates, Inc., 2013
  Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt