Kernels for Large, Labeled Graphs (LaLa)

• Applicant: Professor Dr. Karsten Borgwardt
• Subject Area: Theoretical Computer Science ; Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2010 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants
• International Connection: Japan
• Participating Person: Dr. Koji Tsuda