Réseaux de neurones graphiques sensibles aux sous-structures

Malgré les progrès remarquables des réseaux de neurones sur les graphes (GNN) dans l’apprentissage sur les graphes, les GNN classiques peinent à dépasser la borne d’expressivité imposée par l’algorithme de test d’isomorphisme de graphes de Weisfeiler-Leman d’ordre un (1-WL), en raison de la cohérence du paradigme de propagation des GNN avec le 1-WL. En s’appuyant sur le fait qu’il est plus facile de distinguer un graphe original à partir de ses sous-graphes, nous proposons un nouveau cadre de réseau de neurones, nommé Substructure Aware Graph Neural Networks (SAGNN), pour surmonter ces limitations. Nous introduisons d’abord une notion de sous-graphe appelé « Cut subgraph », obtenu à partir du graphe original par une suppression itérative et sélective d’arêtes. Ensuite, nous étendons le paradigme d’encodage par marche aléatoire à la probabilité de retour du nœud racine sur le sous-graphe, afin de capturer efficacement les informations structurelles, que nous utilisons ensuite comme caractéristiques de nœuds afin d’améliorer l’expressivité des GNN. Nous prouvons théoriquement que notre cadre est plus puissant que le 1-WL et excelle dans la perception des structures. Nos expérimentations étendues démontrent l’efficacité de notre approche, qui atteint des performances de pointe sur diverses tâches graphes bien établies, et les GNN intégrant notre cadre s’acquittent parfaitement même sur des graphes échouant au test 3-WL. Plus précisément, notre cadre réalise une amélioration maximale de 83 % par rapport aux modèles de base, et de 32 % par rapport aux méthodes précédemment état de l’art.