Le succès des réseaux neuronaux sur graphes (GNN) dans la classification de graphes est étroitement lié à l'algorithme de Weisfeiler-Lehman (1-WL). En agrégant itérativement les caractéristiques des nœuds voisins vers un nœud central, tant le 1-WL que les GNN obtiennent une représentation de nœud qui encode un sous-arbre enraciné autour du nœud central. Ces représentations de sous-arbres enracinés sont ensuite combinées en une seule représentation pour représenter l'ensemble du graphe. Cependant, les sous-arbres enracinés ont une expressivité limitée pour représenter un graphe non arboré. Pour remédier à ce problème, nous proposons les réseaux neuronaux sur graphes emboîtés (NGNN). Les NGNN représentent un graphe avec des sous-graphes enracinés plutôt que des sous-arbres enracinés, de sorte que deux graphes partageant de nombreux sous-graphes identiques (plutôt que des sous-arbres) tendent à avoir des représentations similaires. La clé consiste à faire en sorte que chaque représentation de nœud encode un sous-graphe autour d'elle-même plus qu'un sous-arbre. Pour atteindre cet objectif, les NGNN extraient un sous-graphe local autour de chaque nœud et appliquent un GNN de base à chaque sous-graphe pour apprendre une représentation de sous-graphe. La représentation du graphe entier est ensuite obtenue en combinant ces représentations de sous-graphes. Nous fournissons une analyse théorique rigoureuse montrant que les NGNN sont strictement plus puissants que le 1-WL. En particulier, nous avons prouvé que les NGNN peuvent discriminer presque tous les graphes r-réguliers, là où le 1-WL échoue systématiquement. De plus, contrairement à d'autres GNN plus puissants, les NGNN introduisent seulement une complexité temporelle supérieure d'un facteur constant par rapport aux GNN standards. Les NGNN constituent un cadre prêt à l'emploi qui peut être combiné avec divers GNN de base. Nous avons testé les NGNN avec différents GNN de base sur plusieurs jeux de données de référence. Les NGNN améliorent uniformément leurs performances et montrent des performances hautement compétitives sur tous les jeux de données.