Die Logik der Farbverfeinerung als Rahmenwerk zur Analyse von dynamischen Systemen auf Graphen

• Antragstellerin: Professorin Dr. Nicole Schweikardt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2026
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 572124308

Ein zentrales Ziel dieses Projekts ist die Entwicklung eines allgemeinen logischen Rahmenwerks zur Spezifikation und Analyse dynamischer Systeme auf Graphen. Dazu zählen beispielsweise Boolesche Netzwerke, synchrone Hopfield-Netzwerke sowie verteilte Systeme, die lokale Algorithmen ausführen. Die Aktualisierungsregeln solcher Systeme lassen sich häufig mit Hilfe logischer Operatoren formulieren - insbesondere in Varianten der Logik erster Stufe mit Zählmechanismen sowie deren Erweiterungen auf gewichteten Strukturen. Auch Systeme mit kontinuierlicher Zeit und kontinuierlichen Zuständen, so genannte gekoppelte Zellnetzwerke, können aus Sicht der formalen Logik untersucht werden. Ihre Synchronisationsmuster lassen sich durch Eigenschaften der Interaktionsgraphen beschreiben, die in der 2-Variablen-Logik mit Zählquantoren formalisiert werden können. Viele dynamische Eigenschaften solcher logisch spezifizierten Systeme lassen sich kombinatorisch gut verstehen - zum Beispiel mit dem Farbverfeinerungs-Verfahren (engl.: Color Refinement; auch bekannt als 1-dimensionaler Weisfeiler-Leman Algorithmus) sowie verwandten Konzepten wie Überdeckungsabbildungen und so genannten gerechten (engl.: equitable) Partitionen. Diese Methoden stammen ursprünglich aus der Forschung zum Graphenisomorphie-Problem. Ein wesentliches Ziel dieses Projekts ist es, diese Techniken auf die Analyse dynamischer Systeme auf Graphen zu übertragen und zu erweitern. Im Rahmen dieses Ansatzes wollen wir untersuchen, wie die dynamischen Eigenschaften eines Systems mit der Komplexität seiner logischen Spezifikation zusammenhängen. Außerdem möchten wir das durchschnittliche Verhalten solcher Netzwerke erforschen und die Leistungsfähigkeit lokaler verteilter Algorithmen mit logischen Methoden abschätzen. Inspiriert von aktuellen Anwendungen der Farbverfeinerung beim sogenannten Alignment-Problem für korrelierte Zufallsgraphen wollen wir schließlich auch deren Potenzial zur Lösung von Datenabgleichsproblemen bei relationalen Strukturen ausloten.

• DFG-Verfahren: Sachbeihilfen