🤖 machine learning

Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

Dieser Artikel zeigt, dass die Weisfeiler-Leman-Hierarchie und die damit verbundenen Graph Neural Networks inhärent unvollständig sind, um nicht-isomorphe Graphen mit einfachem Spektrum zu unterscheiden, und stellt PRiSM vor, eine nachweisbar vollständige Kanonisierungsmethode, die diese Einschränkung auflöst und eine universelle Approximation auf solchen Graphen ermöglicht.

Ursprüngliche Autoren: Snir Hordan, Nadav Dym, Tim Seppelt

Veröffentlicht 2026-05-25

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Snir Hordan, Nadav Dym, Tim Seppelt

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Das Problem des „Graph-Detektivs"

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht, ein Rätsel zu lösen: Sind diese beiden Zeichnungen von verbundenen Punkten (Graphen) tatsächlich dasselbe Bild, nur mit umbenannten Punkten?

In der Welt der Informatik repräsentieren diese Zeichnungen alles von chemischen Molekülen bis hin zu sozialen Netzwerken. Um dies zu lösen, verwenden Computer eine Reihe von Regeln namens Weisfeiler-Leman (WL)-Test. Betrachten Sie den WL-Test als einen Detektiv, der eine Zeichnung betrachtet, die Punkte basierend auf ihren Nachbarn einfärbt und dann prüft, ob die Farbmuster übereinstimmen.

Lange Zeit glaubten Wissenschaftler, dass, wenn man den Detektiv intelligenter und leistungsfähiger macht (indem man das „k" in k-WL erhöht), er schließlich jeden Unterschied zwischen zwei Zeichnungen erkennen könnte.

Die Überraschung: Der Detektiv hat einen blinden Fleck

Dieses Papier beweist etwas Schockierendes: Selbst der klügste WL-Detektiv hat einen permanenten blinden Fleck.

Die Autoren entdeckten eine bestimmte Art von Zeichnung, die als „Simple Spectrum Graph" (Graph mit einfachem Spektrum) bezeichnet wird. Man kann sich diese als Zeichnungen vorstellen, bei denen jeder Punkt eine völlig einzigartige „Ausstrahlung" oder Frequenz hat, was sie mathematisch theoretisch leicht identifizierbar macht (wie eine Nadel im Heuhaufen zu finden).

Das Papier beweist jedoch, dass der WL-Detektiv, egal wie mächtig er wird, immer scheitern wird, bestimmte Paare dieser spezifischen Zeichnungen zu unterscheiden. Es ist wie bei zwei identischen Zwillingen, die exakt dieselbe Kleidung tragen; egal wie genau der Detektiv ihre unmittelbare Umgebung betrachtet, er kann sie nicht auseinanderhalten.

Warum ist das wichtig?
Die meisten modernen KI-Modelle für Graphen (Graph Neural Networks) funktionieren genau wie dieser WL-Detektiv. Wenn der Detektiv den Unterschied nicht erkennen kann, kann es die KI auch nicht. Das bedeutet, dass aktuelle KI-Modelle bei der Behandlung dieser spezifischen Graphentypen grundlegend begrenzt sind.

Die Lösung: PRiSM (Der neue Sortieralgorithmus)

Da der Detektiv feststeckt, entwickelten die Autoren ein neues Werkzeug namens PRiSM (was für Partition, Refine, Solve, Match steht).

Stellen Sie sich das Problem wie ein gemischtes Kartenspiel vor.

Das Problem: Die Karten (die mathematischen Merkmale des Graphen) sind korrekt, aber sie könnten umgedreht sein (Vorzeichen-Unschärfe) oder in der falschen Reihenfolge (Permutations-Unschärfe). Bisherige Methoden versuchten, sie zu sortieren, blieben jedoch oft stecken oder machten Fehler.
Die PRiSM-Lösung: PRiSM ist eine strenge, schrittweise Sortiermaschine, die garantiert, dass das Deck immer exakt gleich angeordnet ist, egal wie es ursprünglich gemischt oder umgedreht wurde.
- Partition: Sie gruppiert Karten, die ähnlich aussehen.
- Refine: Sie schaut tiefer, um zu sehen, ob diese Gruppen tatsächlich unterschiedlich sind.
- Solve: Sie ermittelt die korrekte „Drehung" (positiv oder negativ) für jede Karte.
- Match: Sie richtet sie in einer perfekten, standardisierten Reihenfolge aus.

Da PRiSM einen perfekten, einzigartigen „Fingerabdruck" für diese Graphen erstellt, ermöglicht es KI-Modellen endlich die Unterschiede zu erkennen, die der alte Detektiv übersehen hat.

Die Ergebnisse: Funktioniert es?

Die Autoren testeten PRiSM an realen Daten, speziell:

Moleküle: Vorhersage von Eigenschaften chemischer Verbindungen (wie Löslichkeit oder Toxizität).
Benchmarks: Standardtests, die darauf ausgelegt sind, zu sehen, wie gut eine KI darin ist, Unterschiede zwischen Graphen zu erkennen.

Das Ergebnis:
PRiSM schnitt genauso gut oder besser als bestehende Methoden ab. Es unterschied erfolgreich Graphenpaare, die andere Methoden nicht auseinanderhalten konnten. Wenn es mit leistungsfähigen KI-Modellen (wie Transformern) verwendet wurde, ermöglichte es der KI, effektiver zu lernen, und bewies, dass die Behebung des „Sortierproblems" hilft, das gesamte System besser funktionieren zu lassen.

Zusammenfassung der Behauptungen (Was das Papier tatsächlich sagt)

Die Einschränkung: Die Standard-Hierarchie der „WL"-Graphentests ist unvollständig. Sie kann nicht alle nicht-identischen Graphen mit einem „einfachen Spektrum" unterscheiden, egal wie komplex der Test ist.
Die Konsequenz: Das bedeutet, dass alle aktuellen Graph Neural Networks (GNNs), die sich auf diese Tests verlassen, für diese spezifischen Graphen ebenfalls unvollständig sind.
Die Innovation: Die Autoren schufen PRiSM, die erste Methode, die mathematisch beweisbar vollständig ist für das Sortieren des mathematischen „Fingerabdrucks" (Eigenwertzerlegung) von Graphen mit einfachem Spektrum.
Der Beweis: Sie bewiesen mathematisch, dass die Kombination von PRiSM mit Standard-KI-Modellen (wie DeepSets oder Transformern) der KI ermöglicht, jede Funktion auf diesen Graphen zu approximieren (Universelle Approximation).
Der Nachweis: In Experimenten übertraf PRiSM frühere Methoden auf molekularen Datensätzen und Expressivitäts-Benchmarks und zeigte, dass es Graphenpaare unterscheiden kann, die andere übersehen.

Was das Papier NICHT behauptet:

Es behauptet nicht, Krankheiten zu heilen oder direkt neue Medikamente zu entdecken (obwohl eine bessere molekulare Modellierung in Zukunft helfen könnte).
Es behauptet nicht, bei jedem Graphentyp perfekt zu funktionieren (insbesondere räumt es Einschränkungen bei Graphen mit wiederholten Eigenwerten ein, bietet jedoch eine heuristische Lösung dafür).
Es behauptet nicht, dass die Methode „kontinuierlich" (glatt) ist; tatsächlich geben sie zu, dass die Methode „diskontinuierlich" ist, was ein mathematischer Kompromiss ist, den sie eingehen mussten, um perfekte Genauigkeit zu erzielen.

Technische Zusammenfassung: Weisfeiler–Leman ist auf Graphen mit einfachem Spektrum unvollständig, daher kanonisieren Sie diese

Problemstellung

Graph-Neuronale Netze (GNN) werden häufig für das Lernen auf graphenstrukturierten Daten eingesetzt, doch ihre Ausdruckskraft ist oft durch die Weisfeiler–Leman (WL)-Hierarchie begrenzt. Es ist ein bekanntes Ergebnis, dass der $k$ -dimensionale WL-Test ( $k$ -WL) nicht alle nicht-isomorphen Graphen unterscheiden kann. Eine bestimmte Klasse von Graphen – jene mit einem einfachen Spektrum (bei denen die Adjazenzmatrix verschiedene Eigenwerte besitzt) – erlaubt jedoch einen Isomorphietest in kubischer Zeit. Trotz dieser theoretischen Handhabbarkeit blieb die Frage offen, ob die WL-Hierarchie, die die Ausdruckskraft vieler GNNs nach oben begrenzt, alle Graphen mit einfachem Spektrum unterscheiden kann.

Darüber hinaus leiden spektrale Positions-Codierungen (z. B. Laplace-Eigenvektoren), die häufig in GNNs integriert werden, um die Ausdruckskraft zu erhöhen, unter inhärenten Mehrdeutigkeiten: Vorzeichenmehrdeutigkeit bei einfachen Spektren und Basis-Mehrdeutigkeit bei wiederholten Eigenwerten. Bestehende Methoden zur Auflösung dieser Mehrdeutigkeiten (wie SignNet, MAP und OAP) sind auf Graphen mit einfachem Spektrum nachweislich unvollständig und scheitern daran, bestimmte nicht-isomorphe Paare zu unterscheiden. Diese Unvollständigkeit begrenzt die Fähigkeit spektraler GNNs, eine universelle Approximation auf dieser Graphklasse zu erreichen.

Methodik

1. Beweis der WL-Unvollständigkeit auf einfachen Spektren

Die Autoren stellen zunächst fest, dass die gesamte WL-Hierarchie auf Graphen mit einfachem Spektrum unvollständig ist.

Konstruktion: Sie nutzen die Cai–Fürer–Immerman (CFI)-Konstruktion, die Paare nicht-isomorpher Graphen erzeugt, die vom $k$ -WL-Test nicht unterscheidbar sind.
Codierung: Da Standard-CFI-Graphen kein einfaches Spektrum besitzen, führen die Autoren einen neuartigen integralen Codierungsmechanismus ein. Sie bilden die CFI-Adjazenzmuster auf eine orthogonale Matrix $\tilde{X}$ mit ganzzahligen Einträgen ab.
Multigraph-Bildung: Unter Verwendung dieser orthogonalen Matrix und einer Diagonalmatrix mit verschiedenen ganzzahligen Eigenwerten konstruieren sie ein Paar symmetrischer Multigraphen ( $A_{G,0}$ und $A_{G,1}$ ) mit einfachem Spektrum.
Ergebnis: Sie beweisen, dass diese konstruierten Multigraphen mit einfachem Spektrum vom $k$ -WL-Test weiterhin nicht unterscheidbar bleiben. Dies zeigt, dass kein Niveau der WL-Hierarchie das Isomorphieproblem für diese Klasse lösen kann, obwohl das Problem in kubischer Zeit lösbar ist.

2. PRiSM: Eine vollständige Kanonisierung

Um die Einschränkungen bestehender spektraler Methoden zu adressieren, schlagen die Autoren PRiSM (Partition, Refine, Solve, Match) vor, ein nachweislich vollständiges Kanonisierungsverfahren für Eigenzerlegungen von Graphen mit einfachem Spektrum.

Eingabe: Eine spaltenweise orthonormale Matrix $U$ von Eigenvektoren.
Mehrdeutigkeitsgruppe: Das Verfahren behandelt die Mehrdeutigkeitsgruppe $S_n \times \{-1, 1\}^k$ (Permutationen und Vorzeichenflipps).
Vier Stufen:
1. Partition: Knoten werden basierend auf ihren vorzeicheninvarianten Signaturen (Betrag der Eigenvektoreinträge) gruppiert.
2. Verfeinerung: Auf die Partition wird eine spektrale Variante des WL-Farbverfeinerungsverfahrens angewendet. Dies verfeinert die Knotenklassen iterativ unter Verwendung der Multimenge von Kanteneigenschaften, die durch elementweise Produkte von Eigenvektoreinträgen definiert sind ( $U_v \odot U_u$ ), bis sich die Partition stabilisiert.
3. Lösen: Die stabile Partition definiert ein System linearer Gleichungen über dem Körper $\mathbb{Z}_2$ . Das System erzwingt, dass jede Partitionsklasse mindestens eine Zeile mit nicht-negativen Einträgen enthält. Die Lösung dieses Systems bestimmt die eindeutigen kanonischen Vorzeichen für die Eigenvektoren (bis auf Graphautomorphismen).
4. Zuordnung: Sobald die Vorzeichen festgelegt sind, werden die Zeilen lexikografisch sortiert, um die Permutationsmehrdeutigkeit aufzulösen, was eine eindeutige kanonische Matrix ergibt.
Erweiterung: Für Graphen mit wiederholten Eigenwerten (kein einfaches Spektrum) wird PRiSM heuristisch erweitert. Es wendet das Basisverfahren auf den Block mit einfachem Spektrum ( $m=1$ ) an und verwendet QR-Zerlegung und Pivot-Auswahl, um Eigenräume höherer Ordnung ( $m > 1$ ) aufzulösen.

3. Theoretische Garantien

Vollständigkeit: PRiSM ist als gültige Kanonisierung bewiesen, was bedeutet, dass es für isomorphe Graphen die gleiche Ausgabe und für nicht-isomorphe Graphen mit einfachem Spektrum unterschiedliche Ausgaben liefert.
Universelle Approximation: Durch die Komposition von PRiSM mit einem universellen Mengen-Netzwerk (z. B. DeepSets oder Transformer) erreicht das resultierende Modell eine universelle Approximation für jede isomorphieinvariante Funktion auf Graphen mit einfachem Spektrum. Dies löst das offene Problem der Erreichung von Vollständigkeit für spektrale GNNs auf dieser Klasse.

Wichtige Ergebnisse

Theoretische Erkenntnisse

Satz 1: Für jede natürliche Zahl $k$ existieren nicht-isomorphe Multigraphen mit einfachem Spektrum mit $\Theta(k)$ Knoten, die vom $k$ -WL-Algorithmus nicht unterschieden werden. Dies impliziert, dass alle $k$ -WL-abgestimmten GNN-Familien (einschließlich PPGN, $k$ -GNNs und Graph Transformer) auf Graphen mit einfachem Spektrum unvollständig sind.
Satz 2: PRiSM liefert eine gültige Kanonisierung für Eigenzerlegungen von Graphen mit einfachem Spektrum.
Satz 3: Modelle, die aus PRiSM und universellen Mengen-Netzwerken bestehen, erreichen eine universelle Approximation auf Graphen mit einfachem Spektrum.

Empirische Leistung

Die Autoren bewerteten PRiSM an drei Benchmarks:

BREC Expressivity Benchmark: PRiSM übertraf konkurrierende Kanonisierungen (MAP, OAP) bei der Unterscheidung nicht-isomorpher Graphenpaare, insbesondere in den Kategorien Regular und Extension. Es unterschied korrekt 212/360 Paare im Vergleich zu 199/360 für MAP/OAP.
Vorhersage molekularer Eigenschaften (ZINC, OGB-Mol): PRiSM erzielte State-of-the-Art- oder gleichbeste Leistung bei molekularer Regression (ZINC) und Klassifikation (MOLTOX21, MOLPCBA) unter Verwendung sowohl von GatedGCN- als auch von PNA-Rückgraten.
Transformer-Rückgrate (OGB, Alchemy): Als Positions-Codierung für Graph Transformer übertraf PRiSM alle Baselines (LPE, MAP, OAP) über alle vier Datensätze hinweg (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). Die Autoren führen dies darauf zurück, dass PRiSM zusätzlich zu vorzeichenkorrigierten Eigenvektoren eine deterministische Knotenreihenfolge liefert, was für Transformer-Aufmerksamkeitsmechanismen entscheidend ist.

Bedeutung und Behauptungen

Die Arbeit behauptet, eine fundamentale Lücke im theoretischen Verständnis der GNN-Ausdruckskraft und spektraler Methoden zu schließen:

Unvollständigkeit von WL: Sie beweist endgültig, dass die WL-Hierarchie trotz ihrer zunehmenden Kraft nicht alle Graphen mit einfachem Spektrum unterscheiden kann, eine Klasse, bei der Isomorphie theoretisch einfach ist.
Erste vollständige Kanonisierung: PRiSM wird als erste nachweislich vollständige Vorzeichen-Kanonisierung für Eigenzerlegungen von Graphen mit einfachem Spektrum vorgestellt und überwindet die Einschränkungen früherer Methoden wie MAP und OAP, die auf dieser Klasse unvollständig sind.
Universelle Approximation: Die Arbeit stellt fest, dass spektrale GNNs eine universelle Approximation auf Graphen mit einfachem Spektrum erreichen können, wenn sie mit einer vollständigen Kanonisierung wie PRiSM kombiniert werden, was die Verwendung kanonisierter Laplace-Positions-Codierungen rechtfertigt.
Praktischer Nutzen: Empirisch zeigt die Methode, dass die vollständige Auflösung spektraler Mehrdeutigkeiten zu greifbaren Verbesserungen in nachgelagerten Aufgaben führt und bestehende vorzeicheninvariante und Kanonisierungsansätze übertrifft.

Die Autoren weisen auf Einschränkungen hin, insbesondere dass die Vollständigkeitsgarantie strikt auf Graphen mit einfachem Spektrum (oder in der Beweiskonstruktion erzeugte Multigraphen) anwendbar ist und dass das Kanonisierungsverfahren unstetig ist, eine Eigenschaft, die sie als mathematisch unvermeidbar für vollständige Vorzeichen-Kanonisierungen betrachten. Sie lassen die Erweiterung des Unvollständigkeitsbeweises auf einfache kombinatorische Graphen (ohne Mehrfachkanten) als zukünftige Arbeit offen.