# Les GNN apprennent à exécuter des algorithmes classiques

> Les GNN peuvent apprendre à exécuter des algorithmes classiques, mais leur alignement algorithmique ne suffit pas à éviter le surapprentissage hors distribution.

Type : Actualité IA · Catégorie : Tendances · Publié le 2026-08-15 · Signal IA - Order & Chaos
Source : https://www.orderchaos.eu/signal-ia/actu/les-gnn-apprennent-a-executer-des-algorithmes-classiques
Tags : g nn, mit, bellman-ford, programmation dynamique, réseaux neuronaux

---

## En résumé

- Les algorithmes classiques offrent correction, garanties de ressources, généralisation et interprétabilité, des propriétés difficiles à obtenir avec les réseaux profonds.
- Le MIT relie l'alignement entre architecture et algorithme à une meilleure complexité d'échantillonnage et à une meilleure généralisation.
- Les GNN dépassent d'autres architectures sur des tâches de programmation dynamique, mais peuvent encore surapprendre et généraliser à des entrées cinq fois plus grandes seulement avec des biais adaptés.

**Le signal :** Les auteurs rapportent une généralisation possible à des entrées 5 fois plus grandes lors du test.

Les réseaux de neurones profonds sont généralement associés à une faible capacité de garantie, à des difficultés de généralisation hors distribution et à leur caractère de « boîtes noires ». Une piste de recherche cherche à leur faire reproduire les propriétés de l'informatique classique, notamment la correction démontrable, la maîtrise des ressources, l'interprétabilité et la composition de sous-programmes.

## Pourquoi capturer le calcul classique

Les algorithmes classiques, comme le tri, la recherche de plus court chemin ou la programmation dynamique, peuvent fonctionner sur des entrées bien plus grandes ou différentes de celles observées lors de leur conception. Ces caractéristiques sont particulièrement importantes pour des systèmes d'IA censés enseigner de manière fiable et instructive: leur réponse ne devrait pas dépendre de détails mineurs de l'entrée et devrait pouvoir se généraliser à des situations nouvelles. Selon l'article, ces capacités pourraient aussi constituer une étape vers des agents généralement intelligents.

L'exécution d'algorithmes classiques par des [réseaux neuronaux](/signal-ia/actu/reseau-neuronal-de-1989-de-yann-lecun) offre un banc d'essai précis. Les données peuvent être générées en quantité arbitraire, les tâches imposent des manipulations complexes et leur fonction cible est clairement définie, ce qui facilite les analyses d'interprétabilité.

## Le MIT relie architecture et généralisation

L'article « What Can Neural Networks Reason About? », signé par une équipe du [MIT](/signal-ia/actu/mit-lia-medicale-trompe-les-novices-pas-les-pros), a proposé un cadre mathématique pour étudier ce qui rend une architecture meilleure ou moins adaptée à une tâche algorithmique. Sa thèse centrale est que le degré d'alignement algorithmique d'un modèle influence sa complexité d'échantillonnage, c'est-à-dire le nombre d'exemples d'entraînement nécessaires pour faire baisser la perte de validation sous un seuil donné. Plus cet alignement est fort, meilleure serait la généralisation.

L'exemple présenté repose sur Bellman-Ford, un algorithme de recherche du plus court chemin. Dans un graphe, il conserve une distance estimée pour chaque nœud, propose des mises à jour à partir des voisins, puis retient la meilleure. Un réseau de neurones sur graphes, ou GNN, peut reproduire ce flux: les distances deviennent des caractéristiques de nœuds, l'ajout du poids d'une arête correspond à la fonction de message et la sélection de la meilleure proposition à une agrégation qui ne dépend pas de l'ordre des voisins.

## Les GNN évitent-ils le surapprentissage

Bellman-Ford relève de la programmation dynamique, qui décompose un problème en sous-problèmes avant d'en recombiner les solutions. L'équipe du MIT a observé que les GNN semblent naturellement alignés avec cette stratégie. Des tests d'exécution fondés sur la programmation dynamique ont ensuite montré que les modèles relationnels comme les GNN dépassaient des architectures dotées de biais inductifs plus faibles.

Le travail « Neural Execution of Graph Algorithms » nuance toutefois cette conclusion. L'alignement algorithmique aide à choisir une famille de modèles, mais il ne suffit pas à garantir de bons résultats hors distribution. Un GNN expressif peut encore surapprendre les caractéristiques des données d'entraînement et développer des « astuces » qui contournent la procédure recherchée. Les auteurs identifient ainsi plusieurs biais inductifs à renforcer pour certaines tâches de recherche de chemins, avec la possibilité de généraliser à des entrées cinq fois plus grandes lors du test. La source s'interrompt au moment où elle commence à détailler ces biais, notamment les limites d'une architecture composée de couches aux paramètres non partagés.