Lernen effizienter Positionsencodings mit Graph Neural Networks

Positionale Kodierungen (Positional Encodings, PEs) sind für eine effektive Lernung von Graphendarstellungen entscheidend, da sie in ursprünglich positionsunabhängigen Transformer-Architekturen eine Positionsawareness bereitstellen und die Ausdruckskraft von Graph Neural Networks (GNNs) erhöhen. Die Gestaltung leistungsfähiger und effizienter PEs für Graphen stellt jedoch erhebliche Herausforderungen dar, bedingt durch das Fehlen einer kanonischen Knotenordnung und die Skalierung der Graphen. In dieser Arbeit identifizieren wir vier zentrale Eigenschaften, die graphbasierte PEs erfüllen sollten: Stabilität, Ausdruckskraft, Skalierbarkeit und Allgemeingültigkeit. Wir stellen fest, dass bestehende auf Eigenvektoren basierende PE-Methoden oft nicht gleichzeitig alle diese Kriterien erfüllen. Um diese Lücke zu schließen, stellen wir PEARL vor – einen neuartigen Rahmen für lernbare PEs für Graphen. Unser zentraler Einblick ist, dass Nachrichtenübertragungs-GNNs nichtlineare Abbildungen von Eigenvektoren darstellen, was die Gestaltung von GNN-Architekturen zur Erzeugung leistungsfähiger und effizienter PEs ermöglicht. Eine entscheidende Herausforderung besteht darin, die Knotenmerkmale so zu initialisieren, dass sie sowohl ausdrucksstark als auch permutationsäquivariant sind. Hierfür initialisieren wir GNNs mit zufälligen Knoteneingaben oder Standardbasisvektoren, wodurch die Ausdruckskraft der Nachrichtenübertragungsoperationen freigesetzt wird, während statistische Pooling-Funktionen die Permutationsäquivarianz bewahren. Unsere Analyse zeigt, dass PEARL äquivariante Funktionen von Eigenvektoren mit linearer Komplexität approximiert und dabei Stabilität und hohe Ausdruckskraft rigoros nachweist. Experimentelle Evaluierungen belegen, dass PEARL leichtgewichtige Varianten auf Eigenvektoren basierender PEs übertrifft und eine vergleichbare Leistung wie vollständige, auf Eigenvektoren basierende PEs erzielt – jedoch mit einer Komplexität, die um eine oder zwei Größenordnungen geringer ist.