Transformers Treffen Gerichtete Graphen

Transformer wurden ursprünglich als sequenzbasierte Modelle für Text vorgeschlagen, sind jedoch inzwischen für eine Vielzahl von Modalitäten unerlässlich geworden, darunter Bilder, Audio, Video und ungerichtete Graphen. Überraschenderweise ist das Thema Transformer für gerichtete Graphen trotz ihrer Anwendbarkeit in allgegenwärtigen Bereichen wie Quellcode und Schaltkreise bisher wenig erforscht. In dieser Arbeit schlagen wir zwei positionelle Codierungen vor, die sowohl Richtung als auch Struktur berücksichtigen: (1) die Eigenvektoren des magnetischen Laplace-Operators – eine richtungsbezogene Verallgemeinerung des kombinatorischen Laplace-Operators; (2) richtungsbezogene Random-Walk-Codierungen. Empirisch zeigen wir, dass die zusätzlichen richtungsbezogenen Informationen in verschiedenen nachgelagerten Aufgaben nützlich sind, darunter die Korrektheitstests von Sortiernetzwerken und das Verständnis von Quellcode. In Kombination mit einer datenflusszentrierten Graphenkonstruktion übertrifft unser Modell den bisherigen Stand der Technik im Open Graph Benchmark Code2 um 14,7 %.