Graph Transformer (GT) ist kürzlich als eine neue Paradigmenbildung in Graph-Lernalgorithmen hervorgetreten und übertrifft auf mehreren Benchmarks die zuvor populären Message-Passing-Neural-Networks (MPNN). Frühere Arbeiten (Kim et al., 2022) zeigen, dass GT bei geeigneter Positionsembedding beliebig gut MPNN approximieren kann, was impliziert, dass GT mindestens so leistungsfähig wie MPNN ist. In dieser Arbeit untersuchen wir die umgekehrte Beziehung und zeigen, dass MPNN mit virtuellem Knoten (VN), einem häufig verwendeten Heuristikansatz mit geringer theoretischer Fundierung, ausreichend mächtig ist, um die Self-Attention-Schicht von GT beliebig genau zu approximieren.Insbesondere zeigen wir zunächst, dass sich bei Betrachtung einer speziellen Klasse linearer Transformer – der sogenannten Performer/Linear Transformer (Choromanski et al., 2020; Katharopoulos et al., 2020) – bereits ein MPNN + VN mit lediglich O(1) Tiefe und O(1) Breite zur Approximation einer Self-Attention-Schicht im Performer/Linear Transformer eignet. Anschließend nutzen wir eine Verbindung zwischen MPNN + VN und DeepSets, um zu beweisen, dass MPNN + VN mit O(n^d) Breite und O(1) Tiefe die Self-Attention-Schicht beliebig genau approximieren kann, wobei d die Dimension der Eingabeprojektion bezeichnet. Schließlich stellen wir unter gewissen Annahmen eine explizite Konstruktion von MPNN + VN mit O(1) Breite und O(n) Tiefe vor, die die Self-Attention-Schicht in GT beliebig genau approximiert.Empirisch demonstrieren wir, dass 1) MPNN + VN eine überraschend starke Baseline darstellt und GT auf dem kürzlich vorgeschlagenen Long Range Graph Benchmark (LRGB)-Datensatz übertrifft, 2) unser MPNN + VN eine Verbesserung gegenüber früheren Implementierungen auf einer Vielzahl von OGB-Datensätzen erzielt und 3) MPNN + VN sowohl den Linear Transformer als auch das herkömmliche MPNN bei der Klimamodellierung übertrifft.