Power and limits of the Weisfeiler-Leman algorithm

• Stärken und Grenzen des Weisfeiler-Leman-Algorithmus

Kiefer, Sandra; Grohe, Martin (Thesis advisor); Schweitzer, Pascal (Thesis advisor); Immerman, Neil (Thesis advisor)

Aachen (2020)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

Der Weisfeiler-Leman (WL) Algorithmus ist eine wichtige kombinatorische Technik, die in den 1960er Jahren entwickelt wurde und vorrangig zur Klassifizierung von Graphen und anderen relationalen Strukturen verwendet wird. Er findet in zahlreichen Bereichen der theoretischen und praktischen Informatik Anwendung, darunter Modelltheorie, deskriptive Komplexitätstheorie, Beweiskomplexität und maschinelles Lernen. Der Algorithmus ist vor allem für seine zentrale Rolle in Graphisomorphie-Algorithmen bekannt. Besonders erwähnenswert ist Babais bahnbrechender Quasipolynomialzeit-Isomorphietest aus dem Jahr 2016, der als ein Kernstück eine hochdimensionale Version des WL Algorithmus beinhaltet. Für jede natürliche Zahl k berechnet die k-dimensionale Version (k-WL) iterativ eine Färbung der k-Tupel von Knoten des Eingabegraphen. Je größer k, desto ausdrucksstärker ist k-WL. Dennoch gibt es keine Dimension k, die Graphisomorphie im Allgemeinen korrekt entscheidet. Andererseits ist es oft schwierig zu entscheiden, ob und wann k-WL zwei konkrete Graphen unterscheidet. Diese Arbeit untersucht diese Wissensgrenze und zielt darauf, das Verständnis der Funktionsweise, der Ausdrucksstärke und der Grenzen des WL Algorithmus zu verbessern. Durch seine Verbindungen zu vielen Forschungsbereichen sind elegante und überraschende Charakterisierungen von k-WL entdeckt worden. Beispielsweise entspricht die Ausdrucksstärke von k-WL jener der Zähllogik C^(k+1) und lässt sich mit Gewinnstrategien in einem Ehrenfeucht-Fraïssé-Spiel beschreiben. Diese Arbeit kombiniert die drei Charakterisierungen des Algorithmus zu effektiven Beweistechniken. Zunächst untersuchen wir die Iterationenzahl des Algorithmus, welche einen direkten Bezug zur Quantorentiefe von C^k-Formeln hat. Mittels einer Konstruktion von unendlichen Graphfamilien zeigen wir, dass die triviale obere Schranke von n-1 an die Iterationszahl von 1-WL auf Graphen mit n Knoten (bis auf eine additive Konstante von 1) scharf ist. Dies verbessert die bisherige untere Schranke von n-sqrt(n). Für 2-WL sieht die Situation komplett anders aus: Wir zeigen, dass die triviale obere Schranke an die Iterationszahl nicht einmal asymptotisch scharf ist. Selbst wenn k-WL wenige Iterationen zur Berechnung seiner Ausgabe benötigt, gilt keinesfalls, dass er den gegebenen Graphen von allen anderen unterscheidet. Bezüglich seiner Ausdrucksstärke ist viel eher die Dimension des Algorithmus zu betrachten. Hierzu präsentieren wir eine vollständige Charakterisierung der Graphen und aller relationalen Strukturen, für die 1-WL Isomorphie korrekt entscheidet. Am Übergang zu höheren Dimensionen studieren wir die Fähigkeit des Algorithmus, Graphen zu zerlegen. Wir wenden die Ergebnisse an, um zu zeigen, dass 3-WL jeden planaren Graphen identifiziert, was eine drastische Verbesserung gegenüber allen bisherigen bekannten Schranken darstellt. Planare Graphen stellen den Basisfall in unserer weiteren Betrachtung von Graphklassen dar, die durch ihren Euler-Genus parametrisiert sind. Wir zeigen, dass die WL Dimension jedes Graphen höchstens linear in seinem Euler-Genus ist. Dieses Resultat ist die erste explizite Parametrisierung der WL Dimension durch den Euler-Genus des Eingabegraphen.