Graph-Transformer ohne positionale Codierung

Kürzlich sind Transformer für das Lernen von Graphrepräsentationen zunehmend populär geworden und haben auf einer Vielzahl von Graphdatensätzen, sei es allein oder in Kombination mit nachrichtenbasierten Graph-Neuralen Netzen (MP-GNNs), den Stand der Technik erreicht. Die Einbindung von induktiven Verzerrungen (inductive biases) im ursprünglich strukturunabhängigen Transformer-Architektur durch strukturelle oder positionale Kodierungen (PEs) ist entscheidend für diese beeindruckenden Ergebnisse. Allerdings ist die Gestaltung solcher Kodierungen schwierig, und verschiedene Ansätze wurden unternommen, um sie zu entwickeln, darunter Laplace-Eigenvektoren, relative Zufallsgehwahrscheinlichkeiten (RRWP), räumliche Kodierungen, Zentralitätskodierungen, Kantenkodierungen usw. In dieser Arbeit argumentieren wir, dass solche Kodierungen überhaupt nicht erforderlich sein könnten, vorausgesetzt, der Aufmerksamheitsmechanismus selbst integriert Informationen über die Graphstruktur. Wir stellen den Eigenformer vor, einen Graph-Transformer mit einem neuartigen spektrumbewussten Aufmerksamheitsmechanismus, der sich des Laplace-Spektrums des Graphen bewusst ist, und zeigen empirisch, dass er auf mehreren Standard-Benchmarks für GNNs eine Leistung erzielt, die mit den besten aktuellen Graph-Transformern konkurrieren kann. Darüber hinaus beweisen wir theoretisch, dass der Eigenformer verschiedene graphstrukturelle Verbindungs-Matrizen ausdrücken kann, was insbesondere bei kleineren Graphen lernprozessbezogen besonders wichtig ist.