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

Interview
Mal eben den Stecker ziehen

Lässt sich Zukunft vorhersagen? Wann wird Künstliche Intelligenz schlauer als wir Menschen sein? Warum braucht es eine menschenkonforme Maschine? Academia hat die beiden Soziologen Andreas Metzner-Szigeth (unibz) und Roland Benedikter (Eurac Research) zum Gespräch geladen.

Interview
Attenti a quei nerd

L’ipotesi che il NOI si profili come la Silicon Valley nostrana c’è. Non per una vasta produzione di microchip a base di silicio, ma per la concentrazione di nerd che potrebbero circolarvi: giovani molto abili con le nuove tecnologie e totalmente assorbiti da esse. L’idea è quella di insediarvi una fabbrica di “dati intelligenti”. Dati, cioè, che servono a prendere decisioni che migliorano la vita delle persone. Academia ne parla con Diego Calvanese, docente ordinario e affermato ricercatore di logica computazionale, referente del progetto Smart Data Factory.

Interview
Connecting computer science to philosophy

If you think of computer science, it’s difficult to make the jump to philosophy and economics. Giancarlo Guizzardi has thrown himself into a truly interdisciplinary enterprise.

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.