Weisfeiler-Lehman (kurz WL) ist eine weit verbreitete Heuristik, um zwei Graphen auf Isomorphie zu testen. Der Algorithmus wurde 1968 von Boris Weisfeiler und Andrey Leman vorgestellt und arbeitet mit einer Farbverfeinerung: Knoten werden schrittweise eingefärbt, und die entstehende Farbverteilung dient als Fingerabdruck des Graphen.
Idee: Knoten immer genauer unterscheiden
Zu Beginn erhalten alle Knoten dieselbe Farbe (oder ihre Ausgangs-Labels). In jeder Runde bekommt ein Knoten eine neue Farbe, die aus seiner bisherigen Farbe und der Menge der Farben seiner Nachbarn berechnet wird. Zwei Knoten, deren Nachbarschaft sich unterscheidet, erhalten dadurch unterschiedliche Farben. Das Verfahren endet, sobald sich keine Farben mehr ändern.
Was der Test aussagt
Nach der Stabilisierung vergleicht man die Multimengen der Endfarben beider Graphen: Unterscheiden sie sich, sind die Graphen sicher nicht isomorph. Stimmen sie überein, sind die Graphen möglicherweise isomorph — WL ist nur eine notwendige Bedingung und kein vollständiger Isomorphie-Test. Regelmäßige Graphen (etwa zwei Kreise gleicher Größe), bei denen alle Knoten denselben Grad haben, bleiben für WL ununterscheidbar.
Varianten und Aufwand
Die 1-dimensionale Variante (Color Refinement) läuft praktisch in O((n+m) log n). Die k-dimensionale Verallgemeinerung unterscheidet mehr nicht-isomorphe Graphen, wird aber mit wachsendem k deutlich teurer. WL lässt sich als iteratives Verfeinern von Partitionen verstehen und ähnelt strukturell einer Tiefen- beziehungsweise Breitensuche, die Nachbarschaften schrittweise auswertet.
Anwendung im maschinellen Lernen
WL ist die Basis vieler Graph-Kernel: Die bei jeder Runde entstehenden Farben dienen als Merkmale für Klassifikation. Auch Graph Neural Networks (GNNs) sind höchstens so ausdrucksstark wie die 1-dimensionale WL-Variante — ein wichtiger Befund der GNN-Forschung. Typische Darstellungen wie Adjazenzliste oder Adjazenzmatrix liefern die Nachbarschaften, die WL benötigt; die Betrachtung beschränkt sich in der Praxis auf ungerichtete Graphen, eine Zusammenhangskomponente nach der anderen.