Verbesserung von Graph Transformers durch hierarchische Distanz-Strukturkodierung

Graph-Transformers benötigen starke induktive Voreingenommenheiten, um sinnvolle Aufmerksamkeitswerte zu erzeugen. Derzeitige Methoden fallen jedoch oft in der Erfassung längerer Reichweiten, hierarchischer Strukturen oder Gemeinschaftsstrukturen hinterher, die in verschiedenen Graphen – wie Molekülen, sozialen Netzwerken oder Zitierungsnetzwerken – häufig vorkommen. In diesem Artikel präsentieren wir eine Hierarchische Distanz-Struktur-Encoding-Methode (HDSE), die Distanzen zwischen Knoten in einem Graphen modelliert und dabei deren mehrstufige, hierarchische Natur berücksichtigt. Wir stellen einen neuartigen Rahmen vor, um HDSE nahtlos in die Aufmerksamkeitsmechanik bestehender Graph-Transformers zu integrieren, wodurch eine gleichzeitige Anwendung mit anderen Positions-Encodings möglich wird. Um Graph-Transformers mit HDSE auf großskalige Graphen anwenden zu können, schlagen wir außerdem eine hochstufige Variante von HDSE vor, die lineare Transformer gezielt in Richtung graphischer Hierarchien ausrichtet. Theoretisch beweisen wir die Überlegenheit von HDSE gegenüber kürzesten Pfad-Distanzen hinsichtlich Ausdruckskraft und Generalisierbarkeit. Empirisch zeigen wir, dass Graph-Transformers mit HDSE bei der Graph-Klassifikation und Regressionsaufgaben auf sieben graphenbasierten Datensätzen sowie bei der Knotenklassifikation auf elf großskaligen Graphen – einschließlich solcher mit bis zu einer Milliarde Knoten – herausragende Leistungen erzielen.