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

Die rechnergestützte Analyse von Graphen gewinnt zunehmend an Bedeutung im Data Mining und im Machine Learning auf Grund der zahlreichen Anwendungsprobleme in der Bioinformatik und in der Analyse sozialer Netzwerke. Eine unter vielen wichtigen Anwendungen ist die Funktionsvorhersage von Molekülen, deren Struktur als Graph dargestellt wird. Ein zentrales Thema ist dabei der Vergleich und die Klassifikation von Graphen. Existierende Verfahren zum Graphenvergleich leiden unter mindestens einer der folgenden drei Schwächen: a) ihre Laufzeit degeneriert auf großen Graphen mit mehr als Hunderten von Knoten, b) sie ignorieren Knotenlabels oder ihre Laufzeit degeneriert, wenn sie Knotenlabels berücksichtigen, c) sie können nicht partielle Ähnlichkeit zwischen Subgraphen messen, sowohl in Bezug auf die Struktur als auch die Labels des Graphen. Alle drei Probleme stellen ein ungeheures Hindernis dar bei der Klassifikation großer Graphen, die in der Biologie, Medizin und Soziologie in immer größerer Zahl auftreten. Ziel unseres Forschungsvorhabens ist es, in enger Kooperation mit Dr. Koji Tsuda (National Institute of Applied Industrial Science and Technology AIST, Tokyo) effiziente Verfahren, sogenannte Kern-Funktionen, zum Vergleich großer, gelabelter Graphen zu entwickeln.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Japan
• Beteiligte Person: Dr. Koji Tsuda