Graph Edit Distance. Best Paper Award für David Blumenthal

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.