Graph-Transformer zeigen skalierbare Transferbarkeit dank Positionskodierung

Transformers haben in den letzten Jahren in vielen Bereichen beeindruckende Erfolge erzielt. Diese Entwicklung hat die Entstehung von Graph-Transformern (GTs) gefördert, die auf der Attention-Architektur basieren und speziell für graphstrukturierte Daten entwickelt wurden. Ein entscheidendes Designmerkmal von GTs ist die Verwendung von Positionskodierungen, die auf Graph Neural Networks (GNNs) basieren und so die strukturelle Information des Graphen einbeziehen.

In der vorliegenden Arbeit wird die Funktionsweise von GTs aus der Perspektive von Mannigfaltigkeitslimitmodellen für Graphsequenzen untersucht. Dabei wird eine theoretische Verbindung zwischen GTs mit GNN-basierten Positionskodierungen und Manifold Neural Networks (MNNs) hergestellt. Aufbauend auf bestehenden Transferabilitätsresultaten für GNNs unter Mannigfaltigkeitskonvergenz zeigen die Autoren, dass GTs die Transferabilitätsgarantien ihrer Positionskodierungen übernehmen.

Insbesondere wird bewiesen, dass GTs, die auf kleinen Graphen trainiert wurden, unter milden Annahmen auch auf größere Graphen verallgemeinern können. Diese theoretische Erkenntnis wird durch umfangreiche Experimente auf Standard-Graphbenchmarks untermauert, die zeigen, dass GTs ein skalierbares Verhalten aufweisen, das mit dem von GNNs vergleichbar ist.

Um die Effizienz in einer realen Anwendung zu demonstrieren, implementieren die Forscher GTs zur Schätzung kürzester Pfadlängen über Gelände. Diese Fallstudie verdeutlicht die Leistungsfähigkeit der übertragbaren GTs in praktischen Szenarien.

Die Ergebnisse liefern neue Einblicke in das Verständnis von Graph-Transformern und legen praktische Richtungen für das effiziente Training von GTs in groß angelegten Umgebungen nahe.