Sketched Random Features stärken Langstreckenabhängigkeiten in GNNs

Graph Neural Networks (GNNs) verarbeiten graphstrukturierte Daten, indem sie Informationen aus benachbarten Knoten iterativ aggregieren. Dieses lokale Nachrichtenübertragungsmodell bringt zwar einen starken induktiven Bias und nutzt die Graphsparsität aus, führt aber gleichzeitig zu drei wesentlichen Problemen: dem „Oversquashing“ langer Abhängigkeiten, dem „Oversmoothing“ von Knotendarstellungen und einer begrenzten Ausdruckskraft.

In der neuen Studie wird ein innovativer Ansatz vorgestellt, bei dem zufällige globale Einbettungen der Knoteneigenschaften – die sogenannten Sketched Random Features – in Standard-GNNs eingefügt werden. Diese Einbettungen sind einzigartig, distanzsensitiv und topologieagnostisch, wodurch sie die genannten Schwächen gezielt mildern.

Die Autoren zeigen sowohl analytisch als auch experimentell, dass die Integration von Sketched Random Features die Fähigkeit der Netzwerke verbessert, Langstreckenabhängigkeiten zu erfassen. Auf realen Graphlernaufgaben erzielen die modifizierten GNNs konsistent bessere Ergebnisse als die Basismodelle. Der Ansatz kann sowohl eigenständig als auch als Ergänzung zu bestehenden Techniken wie graphbasierten Positionskodierungen eingesetzt werden.

Der komplette Quellcode ist öffentlich zugänglich unter https://github.com/ryienh/sketched-random-features.