Bellman-Ford fait généraliser les réseaux cinq fois plus loin

Les réseaux graphiques peuvent apprendre à exécuter des algorithmes classiques, selon un article publié le 19 octobre 2026. Cette approche étudie notamment la recherche de plus courts chemins, le tri et la programmation dynamique. Elle cherche à reproduire certaines propriétés du calcul classique avec des réseaux de neurones profonds. Les algorithmes classiques sont généralement corrects par construction. Ils offrent aussi des garanties sur le temps ou la mémoire nécessaires. Ils généralisent à des entrées plus grandes ou différentes des exemples observés. Leur représentation en pseudo-code facilite enfin l’interprétation et la recomposition par sous-programmes. Ces propriétés répondent à plusieurs limites observées dans les réseaux neuronaux modernes.

L’apprentissage algorithmique sert d’abord de banc d’essai pour mesurer le comportement algorithmique d’un modèle. Les chercheurs peuvent produire une quantité arbitraire d’entrées. Les tâches imposent aussi des manipulations complexes de données et une fonction cible clairement définie. En 2019, les travaux dans ce domaine étaient encore considérés comme un benchmark particulièrement structuré. Une équipe du MIT a ensuite étudié le lien entre architecture et tâches algorithmiques. Son résultat principal affirme qu’un meilleur alignement algorithmique améliore la généralisation. La complexité d’échantillonnage mesure ici le nombre d’exemples nécessaires pour réduire la perte de validation sous un seuil donné.

Les GNN suivent Bellman-Ford

Bellman-Ford fournit un exemple concret de cet alignement. L’algorithme conserve une distance estimée pour chaque nœud d’un graphe. À chaque étape, il propose une nouvelle distance pour chaque voisin. Cette proposition combine la distance connue et le poids de l’arête parcourue. L’algorithme conserve ensuite la meilleure proposition. Un réseau neuronal graphique peut reprendre cette structure. Ses caractéristiques de nœuds représentent les distances. Sa fonction de message ajoute le poids de l’arête. Son agrégation choisit ensuite la meilleure valeur parmi les voisins. Les GNN semblent ainsi particulièrement adaptés à la programmation dynamique, qui décompose un problème avant de recombiner ses solutions.

Les expériences menées montrent toutefois que l’alignement algorithmique ne suffit pas à garantir une bonne généralisation. Un GNN expressif peut mémoriser les caractéristiques des entrées d’entraînement. Il peut alors contourner la procédure recherchée avec des astuces statistiques. Les auteurs ont retenu trois choix pour les problèmes de recherche de chemins. Le premier remplace une succession de couches distinctes par un processeur GNN partagé. Ce processeur est exécuté pendant un nombre variable d’étapes. Le deuxième utilise une agrégation par maximum, adaptée au choix local du meilleur voisin. Le troisième fournit une supervision à chaque étape. Le modèle peut ainsi apprendre des invariants intermédiaires de Bellman-Ford.

Les modèles itératifs étendent la généralisation

Les résultats annoncés indiquent que ces choix permettent de tester des entrées jusqu’à cinq fois plus grandes. L’architecture encode-process-decode répète le même processeur pendant l’entraînement et l’inférence. Cette répétition correspond au fonctionnement itératif de nombreux algorithmes. La supervision étape par étape vérifie notamment qu’après k itérations, le modèle récupère les chemins de longueur maximale k. Cette méthode s’inscrit dans une histoire plus large. Les Neural Turing Machines et les Differentiable Neural Computers avaient déjà tenté d’intégrer des composants de calcul différentiables. L’article juge toutefois ces architectures difficiles à composer et à déboguer. Les travaux récents privilégient donc une conception plus progressive des blocs spécialisés.

Les travaux associés couvrent désormais les algorithmes séquentiels linéarithmiques, les algorithmes itératifs, les structures de données à pointeurs et la mémoire auxiliaire persistante. L’alignement algorithmique a également évolué sur le plan théorique. Des recherches récentes l’associent au raisonnement causal, à la théorie des catégories et au calcul asynchrone. La page Neural algorithmic reasoning présente cette trajectoire et ses résultats. Le dépôt CLRS de DeepMind fournit un autre point d’entrée vers l’apprentissage d’algorithmes. Le site AlgoReasoning rassemble enfin des travaux consacrés à ce domaine.