Nachrichtenübertragende Graph-Neuronale Netze (GNNs) zeichnen sich durch ihre Fähigkeit aus, lokale Beziehungen zu erfassen, haben jedoch Schwierigkeiten mit langreichweitigen Abhängigkeiten in Graphen. Im Gegensatz dazu ermöglichen Graph-Transformer (GTs) den Austausch von globaler Information, vereinfachen die Graphstruktur aber oft zu sehr, indem sie Graphen als Mengen fester Vektoren darstellen. Diese Arbeit stellt eine neuartige Architektur vor, die die Nachteile beider Ansätze überwindet, indem sie langreichweitige Informationen von Zufallsgehen mit lokaler Nachrichtenübertragung kombiniert. Indem Zufallsgehen als Sequenzen behandelt werden, nutzt unsere Architektur jüngste Fortschritte in der Modellierung von Sequenzen, um langreichweitige Abhängigkeiten innerhalb dieser Gehe effektiv zu erfassen. Auf Basis dieses Konzepts schlagen wir einen Rahmen vor, der (1) durch Zufallsgehen-Sequenzen expressivere Graphdarstellungen bietet, (2) die Möglichkeit eröffnet, beliebige Sequenzmodelle zur Erfassung langreichweitiger Abhängigkeiten zu nutzen, und (3) Flexibilität durch die Integration verschiedener GNN- und GT-Architekturen gewährleistet. Unsere experimentellen Auswertungen zeigen, dass unser Ansatz erhebliche Leistungsverbesserungen auf 19 Benchmarks für Graph- und Knotendatensätze erreicht und bestehende Methoden bei den PascalVoc-SP und COCO-SP Datensätzen um bis zu 13 % übertrifft. Der Code ist unter https://github.com/BorgwardtLab/NeuralWalker verfügbar.