Exphormer: Sparse Transformers für Graphen

Graph-Transformer sind als vielversprechende Architektur für eine Vielzahl von Aufgaben im Bereich des Graph-Lernens und der Graph-Darstellung hervorgetreten. Trotz ihrer Erfolge bleibt es herausfordernd, Graph-Transformer auf große Graphen zu skalieren, ohne die Genauigkeit, die mit Nachrichtenübertragungsnetzwerken erreichbar ist, zu verlieren. In diesem Paper stellen wir Exphormer vor, einen Rahmen zur Entwicklung leistungsfähiger und skalierbarer Graph-Transformer. Exphormer basiert auf einem sparsen Aufmerksamkeitsmechanismus, der zwei Mechanismen nutzt: virtuelle globale Knoten und Expander-Graphen. Ihre mathematischen Eigenschaften – wie spektrale Expansion, Pseudozufälligkeit und Sparsamkeit – ermöglichen es, Graph-Transformer mit nur linearer Komplexität in Bezug auf die Größe des Graphen zu konstruieren, während gleichzeitig beweisbare, wünschenswerte theoretische Eigenschaften der resultierenden Transformer-Modelle gewährleistet werden. Wir zeigen, dass die Integration von Exphormer in den kürzlich vorgeschlagenen GraphGPS-Framework Modelle mit konkurrenzfähigen empirischen Ergebnissen auf einer Vielzahl von Graph-Datensätzen liefert, einschließlich state-of-the-art-Ergebnisse auf drei Datensätzen. Zudem demonstrieren wir, dass Exphormer sich besser skalieren lässt als bisherige Architekturen für Graph-Transformer, insbesondere bei größeren Graphen. Der Quellcode ist unter \url{https://github.com/hamed1375/Exphormer} verfügbar.