Polynormer: Polynomial-Expressive Graph Transformer in Linear Time

Graph-Transformer (GTs) sind als vielversprechende Architektur hervorgetreten, die theoretisch ausdrucksstärker ist als Message-Passing-Graph-Neuronale Netze (GNNs). Allerdings weisen typische GT-Modelle mindestens eine quadratische Komplexität auf und können daher nicht effizient auf großen Graphen skaliert werden. Obwohl in jüngster Zeit mehrere lineare GTs vorgestellt wurden, erreichen diese auf mehreren gängigen Graph-Datensätzen immer noch nicht das Leistungsniveau von GNN-Alternativen, was gravierende Bedenken hinsichtlich ihrer praktischen Ausdruckskraft aufwirft. Um das Spannungsverhältnis zwischen Ausdruckskraft und Skalierbarkeit von GTs zu balancieren, stellen wir Polynormer vor – ein polynomial-ausdrucksstarkes GT-Modell mit linearer Komplexität. Polynormer basiert auf einem neuartigen Grundmodell, das ein Polynom höherer Ordnung über Eingabemerkmale lernt. Um die Permutationsäquivarianz des Grundmodells zu gewährleisten, integrieren wir es getrennt mit der Graphtopologie und den Knotenmerkmalen, wodurch lokale und globale äquivariante Aufmerksamkeitsmodelle entstehen. Dadurch implementiert Polynormer eine lineare Lokal-zu-Globale-Aufmerksamkeitsstrategie, um hochgradige äquivariante Polynome zu lernen, deren Koeffizienten durch Aufmerksamkeitswerte gesteuert werden. Polynormer wurde auf 13 homophilen und heterophilen Datensätzen evaluiert, darunter auch große Graphen mit Millionen von Knoten. Unsere umfangreichen Experimente zeigen, dass Polynormer auf den meisten Datensätzen state-of-the-art GNN- und GT-Baselines übertrifft – selbst ohne Verwendung nichtlinearer Aktivierungsfunktionen.