Nous proposons CRaWl, une nouvelle architecture de réseau de neurones pour l'apprentissage sur graphes. Tout comme les réseaux de neurones sur graphes (GNN), les couches de CRaWl mettent à jour les caractéristiques des nœuds sur un graphe, ce qui permet de les combiner librement ou d’intercaler avec des couches GNN. Toutefois, CRaWl fonctionne fondamentalement différemment des GNN basés sur le passage de messages. Les couches de CRaWl extraient et agrègent des informations sur des sous-graphes apparaissant le long de marches aléatoires à travers un graphe, en utilisant des convolutions unidimensionnelles. Ainsi, elles permettent de détecter des interactions à longue portée et de calculer des caractéristiques non locales. À titre fondamental, nous prouvons un théorème établissant que l’expressivité de CRaWl est incomparable à celle de l’algorithme de Weisfeiler-Leman, et donc à celle des GNN. Autrement dit, il existe des fonctions expressibles par CRaWl mais non par les GNN, et réciproquement. Ce résultat s’étend aux niveaux supérieurs de la hiérarchie de Weisfeiler-Leman, et donc aux GNN d’ordre supérieur. Expérimentalement, nous montrons que CRaWl atteint les performances des architectures GNN les plus avancées sur une large variété de jeux de données de référence pour la classification et la régression sur graphes.