Réseaux de neurones path : des réseaux de neurones graphes expressifs et précis

Les réseaux de neurones sur graphes (GNN) sont devenus récemment la méthode de référence pour l’apprentissage à partir de données structurées en graphes. Des travaux antérieurs ont mis en lumière leur potentiel, tout en révélant leurs limites. Malheureusement, il a été démontré que les GNN classiques sont limités en puissance expressive : ils ne sont pas plus puissants que l’algorithme 1-WL (Weisfeiler-Leman unidimensionnel) pour distinguer des graphes non isomorphes. Dans cet article, nous proposons Path Neural Networks (PathNN), un modèle qui met à jour les représentations des nœuds en agrégeant des chemins partant de ces nœuds. Nous dérivons trois variantes distinctes du modèle PathNN, qui respectivement agrègent des chemins les plus courts simples, tous les chemins les plus courts, et tous les chemins simples de longueur inférieure ou égale à K. Nous démontrons que deux de ces variantes sont strictement plus puissantes que l’algorithme 1-WL, et nous validons expérimentalement nos résultats théoriques. Nous constatons que PathNN peut distinguer des paires de graphes non isomorphes indiscernables par 1-WL, et que la variante la plus expressive de PathNN parvient même à distinguer des graphes indiscernables par 3-WL. Les différentes variantes de PathNN sont également évaluées sur des jeux de données de classification et de régression de graphes, où elles surpassent, dans la plupart des cas, les méthodes de référence.