Rezept für einen allgemeinen, leistungsfähigen, skalierbaren Graphentransformer

Wir schlagen ein Rezept vor, wie man einen allgemeinen, leistungsfähigen und skalierbaren (GPS) Graphen-Transformer mit linearer Komplexität und Stand-der-Technik-Ergebnissen auf einer Vielzahl von Benchmarks erstellen kann. Graphen-Transformers (GTs) haben in der Graphendarstellungslernung an Popularität gewonnen, wobei eine Reihe von jüngsten Veröffentlichungen erschienen sind. Allerdings fehlt es ihnen an einer gemeinsamen Grundlage darüber, was eine gute positionale oder strukturelle Kodierung ausmacht und worin sie sich voneinander unterscheiden. In diesem Artikel fassen wir die verschiedenen Arten von Kodierungen mit einer klareren Definition zusammen und klassifizieren sie als $\textit{lokal}$, $\textit{global}$ oder $\textit{relativ}$. Frühere GTs waren auf kleine Graphen mit wenigen hundert Knoten beschränkt; hier präsentieren wir die erste Architektur mit einer Komplexität, die linear in der Anzahl der Knoten und Kanten $O(N+E)$ ist, indem wir die lokale Real-Kante-Aggregation vom vollständig verbundenen Transformer trennen. Wir argumentieren, dass diese Trennung die Ausdrucksfähigkeit nicht negativ beeinflusst und unsere Architektur ein universeller Funktionenapproximator für Graphen ist. Unser GPS-Rezept besteht aus der Auswahl von drei Hauptzutaten: (i) positionale/strukturelle Kodierung, (ii) lokaler Nachrichtenaustauschmechanismus und (iii) globaler Aufmerksamkeitsmechanismus. Wir stellen ein modulares Framework $\textit{GraphGPS}$ vor, das verschiedene Arten von Kodierungen unterstützt und sowohl in kleinen als auch in großen Graphen Effizienz und Skalierbarkeit bietet. Wir testen unsere Architektur auf 16 Benchmarks und zeigen hochwettbewerbsfähige Ergebnisse in allen von ihnen, wodurch wir die empirischen Vorteile der Modularität und der Kombination verschiedener Strategien unter Beweis stellen.