Graphen sind überall. In der diskreten Mathematik sind sie Strukturen, die die Verbindungen zwischen Punkten darstellen, ähnlich wie ein öffentliches Verkehrsnetz. Mathematiker:innen versuchen seit langem, Algorithmen zu entwickeln, mit denen sich zwei beliebige Graphen vergleichen lassen. Praktisch scheinen viele Algorithmen immer effizient zu sein, was theoretisch nicht garantiert ist. In einem neuen arXiv-Preprint entwickeln Forscher der Kwan Gruppe am Institute of Science and Technology Austria (ISTA) eine Methode, um zu verstehen, warum das so ist.

Manche mathematische Probleme sind gefinkelt. Oft weiß man nicht genau, wie schwer sie wirklich sind. Das ist der Fall beim Testen für Graph-Isomorphismen, einem wichtigen Problem in den Computerwissenschaften, bei dem Wissenschafter:innen Algorithmen verwenden, um zu prüfen, ob zwei Graphen strukturell gleich sind. Theoretisch könnten diese Algorithmen länger laufen als das Alter des Universums. Doch in der Praxis scheinen viele Algorithmen gut zu funktionieren. Fast immer. Warum scheinen diese Algorithmen so effektiv zu sein?

Mit dieser Thematik auseinandergesetzt haben sich am Institute of Science and Technology Austria (ISTA) in Klosterneuburg die Postdoktoranden Michael Anastos und Benjamin Moore, sowie Assistenzprofessor Matthew Kwan - welcher dieses Jahr auch den Förderpreis der Österreichischen Mathematische Gesellschaft (ÖMG) erhalten hat. Anastos erklärt: "Die Komplexität des Graphisomorphie-Problems ist eine der faszinierendsten Fragen der Computerwissenschaften". Kwan fügt hinzu: "Das Graphisomorphie-Problem scheint nicht schwer zu sein, aber wir können irgendwie noch nicht beweisen, dass es einfach ist."

Die Komplexität der Netzwerk-Modellierung

Graphen werden verwendet, um eine Vielzahl von Systemen zu modellieren, wie soziale Netzwerke, Kommunikationswege oder Computernetzwerke. Dies gilt auch für chemische Verbindungen. "Chemiker:innen verwenden Graphisomorphie-Algorithmen, um Moleküle zu vergleichen und Datenbanken mit Chemikalien aufzubauen", so Kwan. Dadurch können sie festlegen, ob ihre neu synthetisierten Verbindungen tatsächlich neu sind. Jedoch stellen Graphen Netzwerke dar, die im Gegensatz zu geometrischen Formen mit bestimmten Winkeln und Abmessungen stehen. Daher können Graphen äußerst komplex sein und ihre Knoten - die Verbindungspunkte - können frei positioniert werden, was sie visuell unkenntlich macht. Der Vergleich solcher komplexen Graphen unter allen möglichen Bedingungen stellt Mathematiker:innen vor ein Rätsel.

Verfeinerung mit Farben

Im Laufe der Zeit haben Mathematiker:innen verschiedene Strategien entwickelt, um Graphen zu vergleichen. Seit den 1970er Jahren sind Algorithmen in der Lage, die Isomorphie von Graphen zu testen, allerdings in exponentieller Zeit. Das bedeutet, dass die zunehmende Komplexität der Diagramme die Laufzeit des Algorithmus überproportional erhöhte und ihn erheblich verlangsamte. 2015 gelang dem Informatiker und Mathematiker László Babai ein Durchbruch, indem er einen Algorithmus entwickelte, der in "Quasi-Polynomialzeit" läuft. Dies kommt dem "Polynomialzeit"-Maßstab, der effiziente Algorithmen von ineffizienten trennt, recht nahe. Aber bereits 1980 zeigte ein anderes klassisches Theorem - der Babai-Erdős-Selkow-Satz -, dass fast alle Graphen 'umetikettiert' werden können, um eine einfache Isomorphieprüfung zu ermöglichen. Dies ist auf eine Art der Verfeinerung zurückzuführen, die "Farbverfeinerung" genannt wird (Englisch, color refinement). Hier untersucht der Algorithmus alle Knoten-Verbindungen und weist ihnen eine Farbe zu. Anhand der so zugewiesenen verschiedenen Farben kann der Algorithmus leicht erkennen, wie viele andere Knoten ein bestimmter Knoten 'sieht'.

Dieser Ansatz erleichtert den Vergleich über einen großen Pool von Graphen. "Algorithmen, die auf Farbverfeinerung basieren, scheinen in den meisten Fällen in der Praxis zu funktionieren. Aber wie kann das sein, wenn die Theorie besagt, dass es exponentiell lange dauern kann?", fragt Anastos. "Unsere Arbeit zielt nicht darauf ab, Algorithmen zu entwerfen, die für Worst-Case-Szenarien garantiert zum Einsatz kommen. Stattdessen versuchen wir eine theoretische Begründung zu liefern und einen Einblick zu geben, warum Algorithmen, die auf Farbverfeinerung basieren, so effektiv sind."

Zufällige Datenstörungen und geglättete Analyse

Um besser zu verstehen, warum die Farbverfeinerung zu funktionieren scheint - zumindest in den meisten Fällen in der Praxis - kombinierten Anastos, Kwan und Moore sie mit einem anderen Konzept namens "geglättete Analyse" (Englisch, smoothed analysis). Dieses allgemeine Paradigma wurde Anfang der 2000er Jahre von den Informatikern Daniel Spielman und Shang-Hua Teng eingeführt, um die Lücke zwischen der durchschnittlichen und der Worst-Case-Leistung von Algorithmen zu schließen. Für die geglättete Analyse erhielten Spielman und Teng 2008 den Gödel-Preis, einen jährlichen Preis für herausragende Publikationen in der theoretischen Informatik.

Einfach ausgedrückt, führt die geglättete Analyse kleine zufällige Störungen in die Verbindungen eines Graphen ein, anstatt sich nur auf Worst-Case-Szenarien zu konzentrieren. "Wenn ein Algorithmus nach einer zufälligen Störung einer Eingabe gut abschneidet, sagt uns das, dass die schlechten Eingaben 'selten', 'fragil' oder 'instabil' sind, was darauf hindeutet, dass wir sie in der Praxis eher nicht sehen", erklärt Kwan. "Unabhängig davon, mit welchem Graphen wir beginnen, zeigen wir, dass Algorithmen, die auf Farbverfeinerung basieren, sehr effizient werden, indem wir einige Kanten oder Verbindungen zwischen den Knoten umdrehen." Dies erklärt, warum Algorithmen, die auf Farbverfeinerung basieren, in der Praxis nicht dazu neigen, in einer exponentiellen Laufzeit 'stecken zu bleiben'.

Von einem rätselhaften Problem zu "kein Problem"?

Den ISTA-Forschern ging es nicht darum, einen magischen Algorithmus zu finden, der jeden Graphen selbst im kompliziertesten Fall vergleichen kann, sondern sie wollten die Philosophie verstehen, warum bestimmte Algorithmen in der Praxis überraschend gut funktionieren. Sie versuchten also, ein rechnerisch schwieriges Problem auf mathematische Weise zu lösen. Durch die Kombination von Farbverfeinerung und geglätteter Analyse zeigten Anastos und seine Kollegen, dass die Graphen, die für die bestehenden Algorithmen problematisch sind, eine äußerst fragile Struktur aufweisen. Sobald sie von dieser Struktur abweichen, arbeiten die Algorithmen wesentlich effizienter. "Wir kommen dem Beweis, dass das Graphisomorphie-Problem in der Tat einfach zu lösen ist, einen Schritt näher", schließt Anastos.

Publikation:

Michael Anastos, Matthew Kwan & Benjamin Moore. 2024. Smoothed analysis for graph isomorphism. arXiv. DOI: 10.48550/arXiv.2410.06095

Projektförderung:

Dieses Projekt wurde durch Mittel aus dem Europäischen Forschungsrat ERC Starting Grant "RANDSTRUCT" Nr. 101076777, dem Österreichischen Wissenschaftsfond (FWF) Grant 10.55776/ESP3863424 und dem Horizon 2020 Forschungs- und Innovationsprogramm der Europäischen Union unter der Marie Skłodowska-Curie Finanzhilfevereinbarung Nr. 101034413 finanziert.

Medienkontakt:
Andreas Rothe
andreas.rothe@ista.ac.at
+43 664 8832 6510