Bellman-Ford quintuple la portée des réseaux graphiques

Les algorithmes classiques constituent le point de départ de l’article publié le 21 septembre 2026 par The Gradient. Ils couvrent notamment la recherche de plus courts chemins, le tri et la décomposition de problèmes en sous-problèmes. Leur intérêt repose sur trois propriétés précises. Ils peuvent être prouvés corrects. Leurs besoins en temps ou en mémoire peuvent souvent être encadrés. Ils généralisent aussi à des entrées plus grandes ou différentes de leurs exemples de conception. Leur représentation en pseudo-code facilite enfin l’interprétation et la composition par sous-programmes. L’article examine ensuite comment capturer ces propriétés avec des réseaux neuronaux profonds. Lire l’article original.

La question centrale porte sur l’exécution d’algorithmes classiques par des réseaux neuronaux. Ce cadre fournit une source de données potentiellement infinie, puisque les entrées peuvent être générées. Il impose aussi des manipulations complexes de données et une fonction cible clairement définie. Ces caractéristiques facilitent l’évaluation des modèles et l’analyse de leur comportement. Des travaux lancés en 2019 ont étudié cette approche comme un banc d’essai du comportement algorithmique. Une équipe du MIT a ensuite relié l’alignement algorithmique à la complexité d’échantillonnage. Selon son théorème principal, une meilleure correspondance entre architecture et algorithme favorise la généralisation.

Les GNN suivent Bellman-Ford

Le cas Bellman-Ford illustre cette correspondance entre structure logicielle et réseau neuronal graphique. L’algorithme conserve une distance estimée pour chaque nœud. À chaque étape, il propose une nouvelle distance pour chaque voisin. Cette proposition combine la distance courante et le poids de l’arête traversée. Le réseau peut représenter ces distances avec les caractéristiques des nœuds. Sa fonction de message calcule l’ajout du poids d’arête. Son agrégation sélectionne ensuite la meilleure proposition sans dépendre de l’ordre des voisins. Bellman-Ford appartient à la programmation dynamique, qui décompose un problème avant de recombiner les solutions obtenues.

Les résultats empiriques montrent que les modèles relationnels comme les GNN ont dépassé des architectures dotées de biais inductifs plus faibles sur plusieurs tâches de programmation dynamique. L’étude Neural Execution of Graph Algorithms nuance toutefois cette conclusion. Un GNN expressif peut encore mémoriser les caractéristiques des entrées d’entraînement. Il peut alors contourner la procédure algorithmique recherchée. Les auteurs ont identifié trois choix pour renforcer l’alignement sur les problèmes de recherche de chemins. Ils ont utilisé un processeur partagé et itératif. Ils ont privilégié l’agrégation maximale. Ils ont ajouté une supervision à chaque étape du calcul.

Trois choix renforcent la généralisation

Le processeur partagé permet au même GNN d’être exécuté pendant un nombre variable d’étapes. Cette organisation encode-process-decode soutient les calculs itératifs, dont le nombre d’opérations peut augmenter avec la taille de l’entrée. Pour les problèmes de chemins, l’agrégation maximale sélectionne le voisin optimal localement. Ce choix diffère de l’usage fréquent de l’agrégation par somme. La supervision étape par étape ajoute une contrainte supplémentaire. Après k itérations de Bellman-Ford, le modèle doit pouvoir retrouver les plus courts chemins situés à au plus k sauts de la source. Avec ces adaptations, les modèles ont généralisé jusqu’à des entrées cinq fois plus grandes lors du test.

L’alignement algorithmique s’inscrit dans une histoire plus longue. Les Neural Turing Machines et les Differentiable Neural Computers cherchaient déjà à intégrer des mécanismes informatiques différentiables. La Neural Turing Machine a notamment précédé les Transformers dans l’attention fondée sur le contenu, selon l’article. Ces architectures ont toutefois été jugées difficiles à composer et à déboguer. Les travaux récents privilégient donc des composants étudiés séparément. Cette démarche a produit des réseaux spécialisés pour des algorithmes séquentiels en temps linéarithmique, des algorithmes itératifs, des structures de données à pointeurs et une mémoire auxiliaire persistante. Les travaux associés sont regroupés ici.

Les recherches actuelles prolongent cette approche sur le terrain théorique. La théorie de l’alignement algorithmique a été affinée après les résultats de Neural Execution of Graph Algorithms. Cette évolution a notamment apporté une justification à l’agrégation maximale. D’autres travaux étudient le rôle du raisonnement causal, de la théorie des catégories et du calcul asynchrone. L’objectif reste de comprendre quelles architectures reproduisent réellement une procédure algorithmique, plutôt que ses seuls résultats sur une distribution donnée. Le dépôt CLRS de DeepMind fournit par ailleurs un point d’accès à des travaux consacrés au raisonnement algorithmique neuronal.