🤖 machine learning

Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey

Diese Umfrage bietet einen umfassenden Überblick über Graph-Neuverdrahtungstechniken, die entwickelt wurden, um die Herausforderungen des Über-Squashings und Über-Glättens in Graph-Neuronalen Netzen durch die Modifikation der Graph-Topologie zur Verbesserung der Informationsausbreitung zu mildern, und behandelt deren theoretische Grundlagen, Implementierungen sowie Leistungskompromisse.

Ursprüngliche Autoren: Hugo Attali, Nathalie Pernelle, Davide Buscaldi, Fragkiskos D. Malliaros

Veröffentlicht 2026-05-05

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Hugo Attali, Nathalie Pernelle, Davide Buscaldi, Fragkiskos D. Malliaros

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 versuchen, eine geheime Nachricht durch einen überfüllten Raum voller Menschen zu übermitteln. In der Welt der Künstlichen Intelligenz, speziell bei Graph-Neuronalen Netzen (GNNs), sind die „Menschen" Datenpunkte (wie Knoten in einem Netzwerk), und die „Händedrücke" zwischen ihnen sind die Verbindungen (Kanten), die ihnen den Informationsaustausch ermöglichen.

Dieser Artikel ist eine Übersicht (eine große Zusammenfassung) einer neuen Strategie namens Graph-Neuverdrahtung. Denken Sie daran als einen „Raum-Umgestalter" für KI. Anstatt der KI nur beizubringen, besser zu kommunizieren, verändert diese Methode physisch das Layout des Raums, um die Kommunikation zu erleichtern.

Hier ist die Aufschlüsselung der Probleme, die sie lösen, und der Lösungen, die sie anbieten, unter Verwendung einfacher Analogien.

Die zwei großen Probleme: „Das Quetschen" und „Das Verwischen"

Der Artikel identifiziert zwei Hauptgründe, warum diese KI-Modelle manchmal versagen, Verbindungen über große Distanzen zu lernen:

1. Over-Squashing (Das „Quetschen")
Stellen Sie sich einen engen Flur vor, in dem 100 Personen versuchen, einem einzelnen Menschen am Ende ein Geheimnis zu flüstern. Während die Nachricht die Reihe entlangwandert, wird sie zu einem winzigen, komprimierten Flüstern gequetscht. Bis sie das Ende erreicht, sind die Details verloren.

In KI-Terminologie: Wenn Informationen von weit entfernten Knoten versuchen, einen zentralen Knoten zu erreichen, werden sie in einen Speicherplatz fester Größe komprimiert. Die KI vergisst die spezifischen Details des entfernten Knotens, weil auf den wenigen Pfaden, die sie verbinden, zu viel „Verkehr" herrscht.

2. Over-Smoothing (Das „Verwischen")
Stellen Sie sich eine Gruppe von Menschen vor, die in einem Kreis stehen und ständig ihre Farbeimer mit ihren Nachbarn mischen. Wenn sie dies zu lange tun, wird schließlich die Farbe aller genau zum gleichen schlammigen Braun. Man kann nicht mehr erkennen, wer ursprünglich rot, blau oder grün war.

In KI-Terminologie: Während die KI Informationen hin und her zwischen Nachbarn weitergibt, wird die einzigartige „Identität" jedes Knotens ausgewaschen. Sie sehen alle gleich aus, was es der KI unmöglich macht, sie zu unterscheiden.

Die Lösung: Graph-Neuverdrahtung

Anstatt die KI zu zwingen, mit einem kaputten Raumlayout zu arbeiten, verändert die Graph-Neuverdrahtung den Raum selbst. Sie fügt neue Abkürzungen hinzu oder entfernt verwirrende Sackgassen, um den Fluss der Nachricht zu verbessern.

Der Artikel kategorisiert diese „Raum-Umgestalter" in drei Hauptstile:

1. Die strukturelle Lösung (Der Architekt)

Dieser Ansatz betrachtet nur die Form der Verbindungen und ignoriert, was die Menschen tragen (ihre Datenmerkmale). Er verwendet Mathematik, um die „Engpässe" (enge Flure) und die „Sackgassen" zu finden.

Wie es funktioniert: Es werden Werkzeuge wie Krümmung (Misst, wie „uneben" eine Verbindung ist) oder Widerstand (Misst, wie schwer es ist, von A nach B zu gelangen) verwendet.
Die Analogie: Wenn der Architekt einen Flur sieht, der zu schmal ist (hoher Widerstand), reißt er eine Wand ein, um eine neue Tür zu schaffen. Wenn er einen Raum sieht, der zu voll mit Menschen ist, die Farbe mischen (hohe positive Krümmung), entfernt er einige Verbindungen, um das Mischen zu stoppen.
Vor-/Nachteile: Es ist sehr logisch und leicht zu verstehen, kann aber rechenintensiv (langsam) sein und benötigt manchmal viel „Feinabstimmung" (Hyperparameter), um die Platzierung der Tür genau richtig zu bekommen.

2. Die feature-bewusste Lösung (Der Matchmaker)

Dieser Ansatz betrachtet wer die Menschen sind (ihre Datenmerkmale), bevor er den Raum umgestaltet.

Wie es funktioniert: Es wird gefragt: „Haben diese beiden Menschen wirklich etwas gemeinsam?" Wenn zwei weit entfernte Knoten sehr ähnliche Daten haben (wie zwei Personen, die das gleiche farbige Hemd tragen), könnte die KI eine neue Linie zwischen ihnen ziehen, auch wenn sie ursprünglich nicht verbunden waren.
Die Analogie: Anstatt nur auf den Flur zu schauen, betrachtet der Matchmaker die Gäste. Wenn zwei Gäste passende Outfits tragen, aber auf gegenüberliegenden Seiten des Raums stehen, schafft der Matchmaker eine direkte Brücke zwischen ihnen, damit sie sofort sprechen können.
Vor-/Nachteile: Dies funktioniert oft besser, da es mehr Informationen nutzt, aber es ist schwieriger zu erklären, warum die KI eine bestimmte Änderung vorgenommen hat. Es ist wie zu sagen: „Ich habe die Wand verschoben, weil die Farben passten", was etwas abstrakter ist als „Ich habe die Wand verschoben, weil der Flur zu schmal war."

3. Der virtuelle Knoten (Die zentrale Hub)

Manchmal ist der Raum einfach zu groß.

Wie es funktioniert: Diese Methode fügt einen „Super-Knoten" hinzu (wie ein zentrales Megafon oder einen Hauptschalter), der mit allen verbunden ist.
Die Analogie: Anstatt eine Nachricht von Person zu Person über ein riesiges Stadion zu übermitteln, flüstert jeder einem zentralen Ansager zu, der die Nachricht dann allen anderen zuschreit. Dies verkürzt die Distanz, die die Information zurücklegen muss, drastisch.

Wie wissen wir, dass es funktioniert?

Der Artikel argumentiert, dass wir nicht nur auf die Endpunktzahl schauen sollten (hat die KI die richtige Antwort bekommen?). Wir müssen die „Gesundheit" des Raums selbst überprüfen:

Haben wir die Engpässe behoben? (Sind die Flure breiter?)
Haben wir verhindert, dass sich die Farbe mischt? (Sind die Farben noch unterscheidbar?)
Ist die Nachricht schneller unterwegs? (Ist die „Pendelzeit" kürzer?)

Das Fazit

Diese Übersicht kommt zu dem Schluss, dass Graph-Neuverdrahtung ein mächtiges Werkzeug ist, aber kein „Ein-für-alles"-Zauberstab.

Wenn Ihre Daten verrauscht sind oder die Verbindungen schwach, hilft es, auf die Merkmale zu schauen (wer die Knoten sind).
Wenn Ihre Daten sauber sind, aber die Struktur schlecht, hilft es, auf die Geometrie zu schauen (die Form der Verbindungen).
Die Autoren warnen davor, die Einstellungen nur so zu „tunen", dass man bei einem bestimmten Datensatz ein glückliches Ergebnis erzielt. Wir müssen verstehen, warum das neue Layout der KI beim Lernen hilft.

Kurz gesagt: Bringen Sie der KI nicht nur bei, besser zu sprechen; reparieren Sie den Raum, damit das Gespräch tatsächlich stattfinden kann.

Technische Zusammenfassung: Graph-Rewiring in GNNs zur Minderung von Over-Squashing und Over-Smoothing

1. Problemstellung

Graph Neural Networks (GNNs) sind zwar leistungsstark beim Lernen aus graphstrukturierten Daten, stoßen jedoch auf zwei kritische Einschränkungen, die die Leistung beeinträchtigen, insbesondere in heterophilen Graphen und bei Aufgaben, die langreichweitige Abhängigkeiten betreffen:

Over-Squashing: Dieses Phänomen tritt auf, wenn Informationen von entfernten Knoten übermäßig in Repräsentationen fester Größe für Knoten komprimiert werden. Es entsteht, wenn die Graph-Topologie viele verschiedene langreichweitige Signale zwingt, durch eine kleine Menge von Pfaden (strukturelle Engpässe) zu laufen, wodurch die Jacobian-Sensitivität entfernter Knoten mit zunehmender Distanz schnell abfällt.
Over-Smoothing: Dies tritt auf, wenn wiederholter Nachrichtenaustausch dazu führt, dass Knotenrepräsentationen ununterscheidbar werden. Mit zunehmender Tiefe der Schichten wirkt der Aggregationsprozess wie ein Diffusionsprozess, der die Variation über Knoten-Embeddings hinweg progressiv reduziert, bis sie in einen homogenen Zustand kollabieren.

Beide Probleme resultieren aus der Interaktion zwischen dem Nachrichtenaustausch-Operator und der Eingabe-Graph-Topologie. Während bestehende Lösungen das Gewichten von Kanten umfassen (was jedoch durch den ursprünglichen Graph-Support eingeschränkt bleibt) und Multi-Hop-Aggregation (die aufgrund der Graph-Verdichtung Over-Squashing verschärfen und Over-Smoothing beschleunigen kann), versagen diese Ansätze oft darin, die Konnektivitätsstruktur grundlegend zu verändern, um einen effizienten langreichweitigen Informationsfluss zu ermöglichen.

2. Methodik: Graph-Rewiring

Der Artikel untersucht Graph-Rewiring, eine Klasse von Methoden, die die Graph-Topologie explizit modifizieren ( $G \to G^+$ ), um die Informationsausbreitung zu fördern und gleichzeitig strukturelle Muster zu dämpfen, die übermäßige Mischung oder Kompression hervorrufen.

2.1 Kern-Definition

Eine Rewiring-Operation wird als Abbildung $R: G \to G^+$ definiert, wobei $G^+ = (V^+, E^+)$ ein modifizierter Graph ist. Dies kann sein:

Statisch: Einmalig vor dem Training angewendet.
Dynamisch: Entwickelt sich während des Trainings basierend auf lernbaren Parametern ( $G^+ = R_\theta(G)$ ).
Das Ziel ist es, eine Topologie zu erhalten, die für Message Passing Neural Networks (MPNNs) günstiger ist als der ursprüngliche Graph.

2.2 Topologische und Konnektivitätsmaße

Rewiring-Strategien stützen sich auf spezifische Metriken, um Engpässe zu identifizieren und strukturelle Modifikationen zu steuern:

Diskrete Krümmung: Misst die lokale strukturelle Dispersion.
- Ollivier-Krümmung: Basierend auf optimaler Transportierung (Wasserstein-Distanz) zwischen Wahrscheinlichkeitsmaßen auf Nachbarschaften.
- Forman-Krümmungen (Augmented/Balanced): Kombinatorische Maße, die Dreiecke und Zyklen verschiedener Längen einbeziehen.
- Jost-Liu-Krümmung: Verfeinert kantenbasierte Maße unter Verwendung lokaler Clustering (Dreiecke).
- Rolle: Stark negative Krümmung weist oft auf Engpässe (Over-Squashing) hin, während stark positive Krümmung redundante lokale Mischung (Over-Smoothing) anzeigen kann.
Effektiver Widerstand: Ein globales Maß für die Konnektivität zwischen zwei Knoten unter Berücksichtigung aller disjunkten Pfade. Hoher Widerstand deutet auf einen Engpass hin; niedriger Widerstand deutet auf einfache Kommunikation hin.
Auf Zufallspfaden basierende Maße: Quantifiziert die Konnektivität über Pendelzeiten (erwartete Schritte für einen Zufallspfad, um zwischen Knoten hin und zurück zu reisen) oder Pfadanzahlen. Weniger verbindende Pfade korrelieren mit einem höheren Over-Squashing-Risiko.
Spektrale Lücke: Bezieht sich auf die Cheeger-Konstante und den zweitkleinsten Eigenwert ( $\lambda_2$ ) des Laplace-Operators. Eine kleine spektrale Lücke deutet auf fast unverbundene Komponenten (Engpässe) hin.

2.3 Rewiring-Strategien

Der Artikel kategorisiert Methoden basierend auf struktureller Modifikation, Signalquelle und Effizienz:

A. Strukturell-fixiertes Rewiring

Diese Methoden modifizieren den Graphen ausschließlich basierend auf topologischen Deskriptoren ( $S_G$ ), ohne Knotenmerkmale oder Labels zu verwenden.

Krümmungsbasiert: Kanten werden basierend auf Krümmungsschwellenwerten hinzugefügt oder entfernt. Kanten mit stark negativer Krümmung (Engpässe) werden durch Hinzufügen von Abkürzungen überbrückt; Kanten mit stark positiver Krümmung (redundante Clique) werden entfernt, um Over-Smoothing zu verhindern.
Widerstandsbasiert: Fügt iterativ Kanten zwischen Knotenpaaren mit hohem effektivem Widerstand hinzu, um den globalen Widerstand zu minimieren.
Pfadbasiert: Fügt Kanten zwischen Paaren mit wenigen verbindenden Pfaden (niedriges $\Omega_k$ ) hinzu, um die Pfadvielfalt zu erhöhen.
Spektral-Lücken-Methoden: Konstruiert Graphen (z. B. Expander) mit maximierten spektralen Lücken, um schnelle Mischung ohne Engpässe sicherzustellen.
Virtuelle Knoten: Erweitert den Graphen um Hilfsknoten (z. B. einen „Master-Knoten" oder fraktale Knoten), die mit Teilmengen der ursprünglichen Knoten verbunden sind, um multi-skalige Abkürzungen zu schaffen, wodurch Durchmesser und effektiver Widerstand reduziert werden.

B. Merkmalsbewusstes Rewiring

Diese Methoden nutzen Knotenattribute, um das Rewiring zu steuern, was entscheidend ist, wenn die beobachtete Topologie verrauscht ist oder nicht mit der Aufgabe übereinstimmt.

Geometrische Ansätze: Rekonstruiert den Graphen unter Verwendung der Delaunay-Triangulierung im Merkmalsraum (z. B. DR, TRIGON), um aufgabenrelevante Konnektivität durchzusetzen und negative Krümmung zu vermeiden.
Merkmalsähnlichkeit: Rangiert das Hinzufügen/Löschen von Kanten basierend auf Merkmalsaffinität (z. B. Kosinus-Ähnlichkeit), oft eingeschränkt durch Community-Strukturen (z. B. ComFy).
Spektrale Ausrichtung: Erzwingt Konsistenz zwischen der Graph-Topologie und der Merkmalsgeometrie, indem Eigenvektoren der Adjazenzmatrix mit Singulärvektoren der Knotenmerkmale ausgerichtet werden (z. B. JDR).

3. Hauptbeiträge und Umfang der Übersicht

Dieser Artikel bietet eine methodenzentrierte Übersicht über state-of-the-art Rewiring-Ansätze, die sich von früheren Übersichten (z. B. solchen, die sich ausschließlich auf Over-Squashing konzentrieren) durch Folgendes unterscheidet:

Umfassende Kategorisierung: Systematische Organisation von Methoden nach strukturellem Operator, Informationsquelle (Struktur vs. Merkmale) und rechnerischen Kompromissen.
Theoretische Grundlagen: Explizite Verknüpfung von Rewiring-Techniken mit der mathematischen Formalisierung von Over-Squashing (Abfall der Jacobian-Sensitivität) und Over-Smoothing (asymptotischer Kollaps).
Kritische Analyse von Kompromissen:
- Zuordnung: Strukturell-fixierte Methoden bieten eine klarere kausale Zuordnung von Leistungssteigerungen zu Topologieänderungen, während merkmalsbewusste Methoden topologische Verbesserungen möglicherweise mit Merkmalsmodellierung vermischen.
- Hyperparameter-Empfindlichkeit: Viele strukturelle Methoden (z. B. krümmungsbasierte) sind stark empfindlich gegenüber Editier-Budgets und Schwellenwerten und erfordern oft günstige Konfigurationen, um Verbesserungen zu zeigen.
- Rechnerische Komplexität: Berechnungen von Krümmung und effektivem Widerstand können quadratisch oder kubisch skalieren, während pfadbasierte oder spektrale Approximationen eine bessere Skalierbarkeit für große Graphen bieten.

4. Evaluation und Ergebnisse

Der Artikel betont, dass Rewiring nicht ausschließlich anhand der nachgelagerten Genauigkeit bewertet werden sollte. Stattdessen wird ein mehrdimensionales Evaluierungsprotokoll befürwortet:

Strukturebene-Diagnostik: Überprüfung, ob der rewired Graph $G^+$ tatsächlich den effektiven Widerstand, die Pendelzeiten reduziert oder die Krümmungsverteilungen von werten wegbewegt, die Engpässe hervorrufen.
Modellebene-Diagnostik: Messung von Verbesserungen der langreichweitigen Sensitivität (z. B. durch Jacobian-basierte Maße).
Benchmark: Die Leistung wird typischerweise auf heterophilen Datensätzen und Benchmarks für langreichweitige Interaktionen validiert, bei denen Standard-GNNs Schwierigkeiten haben.
Baselines: Vergleiche sollten graph-unabhängige Baselines (z. B. DeepSets) einschließen, um relationale Vorteile von reinen Merkmalseffekten zu unterscheiden, sowie budgetangepasste Kontrollen (z. B. zufälliges Rewiring), um sicherzustellen, dass Gewinne nicht lediglich auf eine erhöhte Kantenzahl zurückzuführen sind.

5. Bedeutung und zukünftige Richtungen

Der Artikel argumentiert, dass Graph-Rewiring einen prinzipiellen Weg darstellt, in die Graph-Struktur einzugreifen, um das Lernen zu verbessern. Seine Bedeutung liegt darin, den Fokus von rein architektonischen Änderungen auf die Modifikation des Propagations-Substrats selbst zu verlagern.

Identifizierte zukünftige Richtungen:

Interplay zwischen Struktur und Merkmalen: Klärung, wann Rewiring notwendig ist versus wann Merkmalsseiten-Mechanismen für langreichweitiges Lernen ausreichen, und wie diese unter angepassten Einschränkungen kombiniert werden können.
Generalisierung und Stabilität: Nutzung struktureller Proxy-Maße (z. B. Heterogenität des Grades, spektrale Eigenschaften), um vorherzusagen, wann die Topologie die Generalisierung verschlechtert, und Steuerung des Rewiring zur Kontrolle der Propagationsverstärkung statt nur zur Optimierung der Genauigkeit.
Rigorose Evaluation: Hin zu klareren Problemformulierungen und Evaluierungsprotokollen, die Behauptungen robust, vergleichbar und interpretierbar über verschiedene Settings hinweg machen.

Die Autoren schließen, dass der Fortschritt in diesem Bereich von expliziteren Annahmen und Evaluierungsprotokollen abhängen wird, die Leistungsverbesserungen robust spezifischen topologischen Interventionen zuordnen können.