Les réseaux neuronaux à graphes par passage de messages (GNNs) excellent dans la capture des relations locales mais peinent à gérer les dépendances à longue portée dans les graphes. En revanche, les transformateurs de graphes (GTs) permettent un échange d'informations global mais simplifient souvent excessivement la structure du graphe en le représentant comme un ensemble de vecteurs de longueur fixe. Cette étude introduit une nouvelle architecture qui surmonte les limites des deux approches en combinant l'information à longue portée des marches aléatoires avec le passage de messages locaux. En traitant les marches aléatoires comme des séquences, notre architecture tire parti des récents progrès dans les modèles de séquence pour capturer efficacement les dépendances à longue portée au sein de ces marches. Sur la base de ce concept, nous proposons un cadre qui offre : (1) des représentations de graphe plus expressives grâce aux séquences de marches aléatoires, (2) la possibilité d'utiliser tout modèle de séquence pour capturer les dépendances à longue portée, et (3) une flexibilité en intégrant diverses architectures GNN et GT. Nos évaluations expérimentales montrent que notre approche réalise des améliorations significatives des performances sur 19 jeux de données de référence pour les graphes et les nœuds, surpassant nettement les méthodes existantes jusqu'à 13 % sur les jeux de données PascalVoc-SP et COCO-SP. Le code est disponible sur https://github.com/BorgwardtLab/NeuralWalker.