🤖 machine learning

Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs

Diese Arbeit präsentiert einen GPU-beschleunigten Ansatz zur Berechnung von Weisfeiler-Leman-stabilen Färbungen für massive Graphen durch die Einführung eines randomisierten Verfeinerungsalgorithmus und eines korrektheitserhaltenden Batching-Schemas, wodurch Beschleunigungen von bis zu zwei Größenordnungen erzielt werden und die Analyse von Web-Scale-Graphen mit über 30 Milliarden Kanten ermöglicht wird, die zuvor unhandlich waren.

Ursprüngliche Autoren: Filippo Biondi, Mirco Tribastone, Max Tschaikowski

Veröffentlicht 2026-07-07

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Filippo Biondi, Mirco Tribastone, Max Tschaikowski

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

Stellen Sie sich vor, Sie haben eine riesige, chaotische Stadt mit Milliarden von Menschen (Knoten) und Billionen von Beziehungen (Kanten). Sie möchten diese Stadt in Nachbarschaften organisieren, basierend auf einer sehr spezifischen Regel: Zwei Menschen gehören nur dann zur selben Nachbarschaft, wenn sie in jeder anderen Nachbarschaft exakt die gleiche Anzahl an Freunden haben.

Dies ist der Kern des Problems, das die Arbeit löst. In der Welt der Informatik wird dies als Weisfeiler-Leman (1-WL)-Test bezeichnet. Es ist eine Methode, um zu sehen, wie „intelligent“ ein Computerprogramm (speziell ein Graph Neural Network) darin ist, verschiedene Teile eines Netzwerks voneinander zu unterscheiden. Wenn das Programm nicht in der Lage ist, zwei Menschen voneinander zu unterscheiden, weil sie demselben Muster entsprechen, erhalten sie dieselbe „Farbe“ oder Kennzeichnung.

Hier ist das Problem: Dies für eine Kleinstadt zu tun, ist einfach. Dies für eine Stadt mit 30 Milliarden Kanten (wie das gesamte Web) zu tun, ist mit aktuellen Werkzeugen unmöglich. Warum?

Der alte Weg ist zu langsam: Traditionelle Methoden sind wie ein einzelner Bibliothekar, der jedes Buch einzeln überprüft. Sie sind sequenziell und können moderne, superschnelle Computer (GPUs) nicht effektiv nutzen.
Das Speicherproblem: Um die Prüfung durchzuführen, müssen die alten Methoden den gesamten Stadtplan gleichzeitig in ihrem Gehirn (RAM) halten können. Kein einzelner Computer verfügt über genug Speicher, um einen Stadtplan mit 30 Milliarden Kanten zu beherbergen.

Die Autoren Filippo Biondi, Mirco Tribastone und Max Tschaikowski haben ein neues System entwickelt, um beide Probleme mithilfe von GPUs (den leistungsstarken Chips in Gaming-Computern und KI-Servern) zu lösen. Dies gelang ihnen mit zwei Haupttricks:

Trick 1: Die „Zufallsraten“-Mathematik (Randomized Refinement)

Anstatt dass der Bibliothekar jede einzelne Regel nacheinander überprüft, nutzt die neue Methode eine mathematische Abkürzung.

Die Analogie: Stellen Sie sich vor, Sie möchten wissen, ob zwei Gruppen von Menschen identisch sind. Anstatt jede einzelne Person zu interviewen, händigen Sie jedem in der Stadt eine zufällige, einzigartige ID-Karte aus. Dann bitten Sie jeden, die ID-Nummern seiner Freunde zusammenzuzählen.
Die Magie: Wenn zwei Menschen exakt die gleichen Freunde haben, erhalten sie exakt die gleiche Gesamtsumme. Wenn sie unterschiedliche Freunde haben, werden die Summen mit an Sicherheit grenzender Wahrscheinlichkeit unterschiedlich sein.
Warum es besser ist: Die alte Methode verwendet „Gleitkomma“-Mathematik (wie ein Taschenrechner mit Dezimalstellen), die bei riesigen Zahlen unordentlich werden und Fehler verursachen kann. Diese neue Methode nutzt Ganzzahl-Mathematik (Ganze Zahlen) innerhalb eines speziellen „Uhren“-Systems (Modulo-Arithmetik). Es ist, als würde man Mathematik auf einem Zifferblatt betreiben, bei dem die Zahlen wieder auf Null zurückspringen. Dies ist auf GPUs unglaublich schnell und, dank einiger kluger Wahrscheinlichkeitsrechnungen, haben sie bewiesen, dass es 9-mal 99,9999999 % genau ist. Es ist eine „randomisierte“ Schätzung, die so intelligent ist, dass sie praktisch eine Garantie darstellt.

Trick 2: Die „Puzzleteil“-Strategie (Batching)

Selbst mit der schnellen Mathematik können Sie einen Stadtplan mit 30 Milliarden Kanten immer noch nicht in den Speicher eines einzelnen Computers laden.

Die Analogie: Stellen Sie sich vor, Sie versuchen, ein riesiges Puzzle zu lösen, aber Sie haben nur einen kleinen Tisch zur Verfügung. Sie können nicht das ganze Puzzle ausbreiten. Also schneiden Sie das Puzzle in kleinere, handhabbare Stücke (Batches).
Der Haken: Wenn Sie jedes Stück allein lösen, könnten Sie an den Rändern, wo die Stücke aufeinandertreffen, Fehler machen.
Die Lösung: Die Autoren entwickelten eine strikte Regel dafür, wie man das Puzzle schneidet und wieder zusammensetzt.
1. Sie schneiden die Kanten in Batches (Chargen) ein.
2. Sie identifizieren „innere“ Menschen (die nur Freunde innerhalb dieses spezifischen Stücks haben) und „Rand“-Menschen (die Freunde in anderen Stücken haben).
3. Sie lösen zuerst die „inneren“ Menschen. Die „Rand“-Mensen werden vorerst unbeachtet gelassen und wie einzigartige Individuen behandelt.
4. Sobald ein Stück gelöst wurde, verkleinern sie es zu einer kleineren, vereinfachten Version seiner selbst (einem „Quotienten-Graphen“).
5. Sie wiederholen diesen Prozess und schrumpfen das Puzzle immer wieder, bis das Ganze auf den Tisch passt.

Dies stellt sicher, dass sie – auch wenn sie nur an kleinen Teilen arbeiten – am Ende ein mathematisch garantiert korrektes Ergebnis für die gesamte Stadt erhalten.

Die Ergebnisse: Geschwindigkeit und Skalierbarkeit

Das Paper testete dies an realen Daten, einschließlich massiver Web-Graphen.

Geschwindigkeit: Ihr GPU-System war bis zu 138-mal schneller als die besten traditionellen CPU-Methoden. Auf einigen Graphen war es fast 450-mal schneller als Multi-Core-CPU-Versuche.
Skalierbarkeit: Sie konnten diese Muster erfolgreich auf Graphen mit über 30 Milliarden Kanten berechnen.
- Der Realitätscheck: Jede andere Methode (die auf leistungsstarken Servern mit riesigem Speicher lief) stürzte einfach ab oder zeitete aus, als sie mit diesen Graphen konfrontiert wurde. Die Methode der Autoren war die einzige, die den Job abschloss.
Genauigkeit: Wenn sie die „Puzzleteil“-Methode anwenden mussten (weil der Graph zu groß für einen Durchgang war), war das Endergebnis dennoch unglaublich nah am perfekten Ergebnis – in der Regel innerhalb von 5 % der idealen Gruppierung.

Zusammenfassung

Kurz gesagt: Die Autoren haben ein Problem genommen, das zu groß und zu langsam für heutige Computer war. Sie ersetzten die langsame, fehleranfällige „Checklisten“-Methode durch eine schnelle, auf Zufallszahlen basierende Mathematik, die perfekt auf GPUs läuft. Dann erfanden sie einen Weg, das massive Problem in mundgerechte Stücke zu schneiden, die unabhängig voneinander gelöst und wieder zusammengesetzt werden können, ohne an Genauigkeit zu verlieren.

Das Ergebnis? Zum ersten Mal können wir die Struktur des gesamten Webs (oder ähnlich massiver Netzwerke) analysieren, um zu sehen, wie „intelligent“ unsere KI-Modelle sind – etwas, das zuvor unmöglich war.

Technische Zusammenfassung: Skalierung der Weisfeiler–Leman-Expressivitätsanalyse auf massive Graphen mittels GPUs

Problemstellung
Der Weisfeiler–Leman-Test (1-WL) und die damit verbundene stabile Färbung sind grundlegend für das Verständnis der Ausdrucksstärke von Graph Neural Networks (GNNs). Die 1-WL-stabile Färbung liefert eine obere Schranke für die Fähigkeit von Message-Passing-GNNs, zwischen Graphstrukturen zu unterscheiden; Knoten, die dieselbe stabile Farbe erhalten, sind für solche Netzwerke ununterscheidbar. Die Berechnung dieser stabilen Färbung für reale, massive Graphen stößt jedoch auf zwei kritische Engpässe:

Sequenzielle Ausführung: Klassische Algorithmen, die auf Partitionenverfeinerung basieren (z. B. der $O(m \log n)$ Splitter-basierte Ansatz), sind inhärent sequenziell und können die massive Parallelität moderner GPU-Architekturen nicht ausnutzen.
Globale Speicheranforderungen: Diese Algorithmen erfordern, dass der gesamte Graph gleichzeitig im Speicher resident ist. Diese „globale“ Natur verhindert die Analyse von Web-Scale-Graphen (z. B. mit Zehntausenden von Milliarden Kanten), die die Kapazität eines einzelnen Geräts oder sogar großer CPU-Cluster übersteigen.

Bestehende Versuche, das Problem zu parallelisieren oder zu linearisieren, verlassen sich oft auf Gleitkommaarithmetik, was bei großen Skalen zu numerischer Instabilität führt, oder versagen dabei, die Speicherbeschränkung für Graphen zu adressieren, die größer als der Grafikspeicher sind.

Methodik
Die Autoren schlagen einen zweigleisigen Ansatz vor, der die Rechenskalierbarkeit von der Speicherskalierbarkeit entkoppelt, indem eine linear-algebraische Interpretation der 1-WL-stabilen Färbung genutzt wird.

1. Randomisierte linear-algebraische Verfeinerung (Rechenskalierbarkeit)
Anstatt einer sequenziellen Partitionenverfeinerung formulieren die Autoren das Problem unter Verwendung der Invarianz-Eigenschaft äquivalenter Partitionen neu: Eine Partition ist stabil, wenn und nur wenn das Bild eines blockkonstanten Vektors unter der Adjazenzmatrix ebenfalls blockkonstant bleibt.

Algorithmus: Die Methode iteriert durch das Sampling zufälliger Vektoren, die auf der aktuellen Partition symmetrisch sind, multipliziert diese mit der Adjazenzmatrix ($z = Aw$) und verfeinert die Partition basierend auf der Symmetrie des resultierenden Vektors.
Arithmetik-Domäne: Um die numerische Instabilität durch Gleitkomma-Potenziteration zu vermeiden (die bei großen Graphen zu fehlerhaften Zusammenführungen führen kann), operiert der Algorithmus vollständig innerhalb des modularen Rings $\mathbb{Z}/2^{64}\mathbb{Z}$ unter Verwendung von vorzeichenloser 64-Bit-Ganzzahlarithmetik.
Theoretische Garantie: Durch Nutzung der strukturellen Beschränkung, dass die Zeilensummen der Adjazenzmatrix durch $2^{64}/2$ beschränkt sind, leiten die Autoren eine probabilistische Korrektheitsgarantie ab. Ein zufälliges Probe-Verfahren erkennt jede fehlende Verfeinerung mit einer Fehlerrate von höchstens $10^{-9}$ und umgeht so die Notwendigkeit des klassischen Schwartz–Zippel-Lemmas, welches eine Körperstruktur (Field) erfordert.
GPU-Mapping: Die Kernoperation reduziert sich auf eine einzige dünnbesetzte Matrix-Vektor-Multiplikation (SpMV) gefolgt von einer lexikographischen Sortierung, beides hochgradig effiziente Operationen auf GPU-Hardware.

2. Korrektheitswahrende Batching-Strategie (Speicherskalierbarkeit)
Um Graphen zu handhaben, die nicht in den Grafikspeicher passen, führen die Autoren ein Batching-Schema ein, das den Kanten-Datensatz in disjunkte Teilmengen zerlegt und dabei die Korrektheit der globalen stabilen Färbung bewahrt.

Innere vs. Randknoten: Für einen gegebenen Batch werden Knoten als „innere Knoten“ (alle ausgehenden Kanten liegen innerhalb des Batches) oder „Randknoten“ (ausgehende Kanten kreuzen Batch-Grenzen) klassifiziert.
Lokale Verfeinerung: Der Algorithmus verarbeitet jeden Batch unabhängig. Entscheidend ist, dass die initiale Partition für jeden Batch alle inneren Knoten in einem einzigen Block und alle Randknoten in Singleton-Blöcken zusammenfasst. Dies stellt sicher, dass die Verfeinerung nur Knoten zusammenführt, deren vollständige Nachbarschaftsinformationen innerhalb dieses Batches verfügbar sind.
Iterative Kontraktion: Lokale Verfeinerungen werden in eine globale Partition zusammengeführt. Der Algorithmus konstruiert dann einen Quotienten-Graphen (wobei die Knoten die Blöcke der aktuellen Partition repräsentieren) und wiederholt diesen Prozess.
Terminierung: Der Prozess iteriert, bis der reduzierte Graph in einen einzelnen Batch passt (was die beweisbar gröbste stabile Färbung ergibt) oder ein Fixpunkt erreicht wird. Falls ein Fixpunkt erreicht wird, bevor der Graph in den Speicher passt, ist das Ergebnis eine gültige stabile Färung, die eine Verfeinerung der gröbsten Färung darstellt.

Wesentliche Beiträge

Randomisierter Verfeinerungsalgorithmus: Ein Monte-Carlo-Framework für die 1-WL-stabile Färung, der in Ganzzahlarithmetik mit engen probabilistischen Garantien ( $<10^{-9}$ Fehler) arbeitet und so den Präzisionsverlust durch Gleitkomma-Methoden vermeidet.
Batching-Schema: Eine Dekompositionsstrategie, die die 1-WL-Berechnung auf Graphen ermöglicht, die den Grafikspeicher überschreiten, indem unabhängige Kanten-Teilmengen verarbeitet und die Ergebnisse über Quotienten-Graphen zusammengeführt werden, wobei die Eigenschaft der stabilen Färung nachweislich gewahrt bleibt.
GPU-Implementierung: Eine CUDA-basierte Implementierung, die diese Algorithmen direkt auf GPU-Primitiven (SpMV, Sortierung, Reduktion) abbildet und massive Beschleunigungen gegenüber CPU-Baselines erzielt.

Experimentelle Ergebnisse
Die Autoren evaluierten ihren Ansatz an elf Graphen mittlerer Größe und drei Web-Scale-Graphen (33–48 Milliarden Kanten).

Korrektheit: Auf Graphen mittlerer Größe, bei denen der volle Graph in den Speicher passt ( $N_b=1$ ), stellte der randomisierte Algorithmus exakt die gröbste stabile Färung wieder her und entsprach damit deterministischen Baselines.
Numerische Stabilität: Die vorgeschlagene Methode mit Ganzzahlarithmetik konnte erfolgreich Knoten unterscheiden, die von einer vorherigen Gleitkomma-Potenziterationsmethode auf großen Graphen fälschlicherweise zusammengeführt wurden (z. B. zeigte der Datensatz it-2004 eine Diskrepanz von über 800.000 Blöcken).
Batching-Qualität: Wenn mehrere Batches ( $N_b=2, 4$ ) verwendet wurden, um Speicherbeschränkungen zu simulieren, lagen die resultierenden Partitionen empirisch innerhalb von 5 % der gröbsten stabilen Färung. Für mehrere Datensätze war die Differenz null.
Performance:
- Geschwindigkeit: Die Single-GPU-Implementierung erreichte Beschleunigungen von bis zu 138× gegenüber der klassischen Single-Threaded CPU-Partitionenverfeinerung und bis zu 449× gegenüber Multicore-CPU-Baselines.
- Skalierbarkeit: Auf Web-Scale-Graphen mit über 30 Milliarden Kanten liefen alle CPU-Baselines (einschließlich der Multicore-symbolischen Reduktion) entweder in einen Timeout oder liefen in den Speicherüberlauf. Die vorgeschlagene Methode berechnete erfolgreich die stabilen Färbungen für diese Instanzen und erreichte Reduktionen von ca. 39–46 % in der Anzahl der Blöcke.

Bedeutung und Ansprüche
Das Paper behauptet, dass diese Arbeit die erste ist, die erfolgreich 1-WL-stabile Färbungen auf Web-Scale-Graphen mit über 30 Milliarden Kanten berechnet – eine Aufgabe, die zuvor aufgrund von Speicher- und Rechenbeschränkungen unmöglich war. Die Bedeutung liegt in:

Ermöglichung der Expressivitätsanalyse: Die empirische Analyse der GNN-Expressivität auf realen, massiven Datensätzen statt auf kleine oder mittlere Graphen zu beschränken.
Architektonische Passgenauigkeit: Der Nachweis, dass das 1-WL-Problem, das traditionell als sequenziell und global betrachtet wird, effektiv mittels linear-algebraischer Formulierungen und Batching-Strategien parallelisiert und verteilt werden kann, die auf GPU-Architekturen zugeschnitten sind.
Robustheit: Bereitstellung einer Methode, die sowohl numerisch stabil (durch Ganzzahlarithmetik) als auch speicherskalierbar (durch Batching) ist und somit die spezifischen Fehlermodi früherer Ansätze überwindet.

Die Autoren kommen zu dem Schluss, dass ihre Methode die 1-WL-Expressivitätsanalyse auf Skalen ermöglicht, die zuvor unerreichbar waren, und weisen darauf hin, dass die Korrespondenz zwischen stabiler Färbung und äquivalenten Partitionen potenzielle zukünftige Wege für die Anwendung dieser Techniken auf nachgelagerte Graph-ML-Aufgaben und Modellreduktionen für nichtlineare dynamische Systeme eröffnet.

Trick 1: Die „Zufallsraten“-Mathematik (Randomized Refinement)

Trick 2: Die „Puzzleteil“-Strategie (Batching)

Die Ergebnisse: Geschwindigkeit und Skalierbarkeit

Zusammenfassung

Technische Zusammenfassung: Skalierung der Weisfeiler–Leman-Expressivitätsanalyse auf massive Graphen mittels GPUs

Mehr davon