k-MIP Attention: Graph-Transformer mit linearer Speicherkomplexität

Graph-Transformer haben das Potenzial, klassische Graph-Neuronale Netze zu übertreffen, indem sie Probleme wie Oversquashing und die Modellierung langer Abhängigkeiten lösen. Ihre breite Anwendung bleibt jedoch durch die quadratische Speicher- und Rechenkomplexität des All‑to‑All‑Attention-Mechanismus eingeschränkt.

Die Autoren stellen k‑Maximum Inner Product (k‑MIP) Attention vor, die für jede Anfrage die wichtigsten Schlüsselknoten mittels einer Top‑k‑Operation auswählt. Dadurch entsteht ein sparsames, aber flexibles Aufmerksamkeitsmuster, das die Speicherkomplexität linear hält und bis zu einem Zehnerfachen der Geschwindigkeit gegenüber dem klassischen Ansatz ermöglicht. Auf einem einzelnen A100‑GPU können damit Graphen mit mehr als 500 000 Knoten verarbeitet werden.

Eine theoretische Analyse zeigt, dass k‑MIP Attention die Ausdruckskraft von Graph‑Transformern nicht einschränkt: k‑MIP‑Transformer können jeden Full‑Attention‑Transformer mit beliebiger Genauigkeit approximieren. Zusätzlich wird die Ausdruckskraft des GraphGPS‑Frameworks, das k‑MIP integriert, untersucht und ein Obergrenze in Bezug auf den S‑SEG‑WL-Test bestimmt.

Die vorgestellte Methode wird auf großen Graphen validiert und demonstriert signifikante Leistungsverbesserungen, ohne die Modellkomplexität zu erhöhen. Damit eröffnet k‑MIP Attention neue Möglichkeiten für effiziente und leistungsstarke Graph‑Transformer‑Anwendungen.