Der 29-jährige David Blumenthal hat auf dem Kongress „Graph-based Representations in Pattern Recognition“ für sein Paper zu Graph Edit Distance den Best Paper Award zugesprochen erhalten.

David Blumenthal hat an der TU Berlin seinen Master in Mathematik abgelegt, bevor er nach Bozen gezogen ist, um an der Fakultät für Informatik sein Doktoratsstudium zu beginnen. Voraussichtlich im Frühjahr 2019 will der von Prof. Johann Gamper betreute Doktorand dieses beenden. „Exact computation of graph edit distance for uniform and non-uniform metric edit costs“ lautet der Titel seines ausgezeichneten Papers, das er auf dem internationalen Kongress in diesem Frühjahr auf Capri eingereicht hat; vorgestellt wurden auf der Konferenz 25 Papers. Blumenthals Thema wurde inzwischen bereits bei Springer publiziert.

Um was dreht sich Ihr Paper genau?
Vereinfacht ausgedrückt verbessere ich exakte Algorithmen für die Berechnung der Graph Edit Distance. Die Graph Edit Distance ist ein Distanzbegriff, mit welchem kombinatorische Graphen miteinander verglichen werden. Kombinatorische Graphen modellieren zum Beispiel Straßennetzwerke oder Moleküle. Viele erinnern sich noch an die Darstellung von Molekülen im Chemieunterricht. Dabei bilden die chemischen Elementen die Knoten des kombinatorischen Graphen und die Bindungen zwischen den Elementen dessen Kanten. Ein relativ weit verbreiteter Begriff, um solcherart als Graphen modellierte Moleküle miteinander zu vergleichen, ist die Graph Edit Distance.

Können Sie diese im Detail erläutern?
Es handelt sich um ein engmaschiges Distanzmaß, das eingesetzt wird, um relativ kleine Graphen auf feine Unterschiede hin zu untersuchen. Der Nachteil liegt darin, dass es generell sehr schwierig ist, diese Unterschiede zu berechnen, da man selbst mit den leistungsstärksten Computern noch zu lange benötigt. Mein Paper beschreibt eine Möglichkeit der Beschleunigung, die aufbauend auf bestehende Algorithmen die Berechnungen wesentlich verbessert.

Als Laie fragt man sich, wie lange eine solche Berechnung dauert.
Die exakte Berechnung der Graph Edit Distance dauert in der Tat für einige Anwendungen zu lange. Auch aus diesem Grund arbeite ich im Rahmen meiner Doktorarbeit derzeit an schnelleren Aproximationstechniken. Für deren Evaluation musste ich die Graph Edit Distance jedoch auch exakt berechnen, weshalb ich verschiedene bereits existierende Algorithmen implementiert habe. Dabei kamen mir Ideen, um zwei dieser Algorithmen zu verbessern. Mein Paper ist also sozusagen ein Nebenprodukt einer größeren Forschungsarbeit.

Können Sie noch einige Beispiele nennen, bei denen ihre Algorithmen künftig angewandt werden?
Hautpanwendung ist sicher die Ähnlichkeitssuche in Graphendatenbanken. Man denke zum Beispiel an einen Wirkstoff bei einem Medikament, bei dem sich Resistenzen gebildet haben. Für die Pharmaindustrie bedeutet dies, dass sie ein neues Medikament entwickeln muss. Dazu bietet es sich an, nach einem Wirkstoff Ausschau zu halten, dessen chemische Struktur der des alten Wirkstoffs ähnelt. Es liegt daher aus mathematischer Sicht nahe, zunächst die Struktur des alten und möglicher neuer Wirkstoffe als Graphen zu modellieren und unter Verwendung der Graph Edit Distance nach Kandidaten für einen neuen Wirkstoff zu suchen, bevor die Pharmaindustrie die nächsten Schritte der klinischen Tests beschreitet. Durch meine Algorithmen wird es künftig möglich sein, den ersten Schritt der Kandidatengenerierung deutlich schneller durchzuführen.

Related Articles

Article
Wie man Maschinen das Nachdenken beibringt…

Was existiert? Was ist ein Gegenstand, was ein Lebewesen, was eine Eigenschaft? Die fundamentalen Fragen des Daseins haben in der Antike ganze Philosophenschulen beschäftigt, jetzt erlebt die Ontologie ein Revival. Warum? Weil man die Antworten auf die existenziellen Fragen Maschinen beibringen will – Stichwort: künstliche Intelligenz, Stichwort: intelligentes Internet.

Interview
“We don’t understand ourselves. That’s why we want the computer to do it for us”

Grzegorz J. Nalepa is a professor at the AGH University in Krakow, Poland who recently held a series of lectures at the Faculty of Computer Science. One of them was “Affective Computing, Context and Processing”. We interviewed him on the ethical questions posed by this new development in technology.

Article
Wie sicher sind Ihre Daten?

Hand aufs Herz: Lassen Sie die Türen Ihrer Firma offenstehen, wenn Sie abends nach Hause gehen? Wohl eher nicht, schließlich gibt es darin Werte, die geschützt werden müssen. Aber wie steht es mit dem mitunter Wertvollsten, über das Ihre Firma verfügt: Ihre Daten? Sind da auch alle Türen zu?

Article
Der Computer als Unternehmensberater

Wenn Manager künftig Prozesse in ihren Unternehmen überwachen, wenn sie Flaschenhälse und Schwachstellen ausfindig machen und diese beheben (oder noch besser: sie gar nicht erst entstehen lassen) wollen, werden sie sich auf einen kompetenten Berater verlassen können: ihren Computer. An den Grundlagen für die dafür nötige künstliche Intelligenz arbeiten Forscher der Freien Universität Bozen.