SAME : Révéler la boîte noire des GNN grâce à des explications multipièces fondées sur Shapley et sensibles à la structure

Les techniques d'explication post-hoc appliquées aux réseaux de neurones sur graphes (GNN) offrent des solutions économiques pour ouvrir les modèles graphiques « boîtes noires » sans nécessiter une re-entraînement du modèle. Bien que de nombreuses variantes d'explication pour GNN aient atteint des résultats d'explication de pointe sur une diversité de benchmarks, elles restent rarement accompagnées d'une analyse théorique de leurs propriétés fondamentales et de leur capacité explicative. Dans ce travail, nous proposons une méthode, appelée SAME (Structure-Aware Shapley-based Multipiece Explanation), pour relever les défis liés aux interactions structurelles entre caractéristiques dans l'explication des GNN. Plus précisément, SAME utilise une recherche arborescente Monte Carlo basée sur une expansion pour explorer des sous-structures connectées à plusieurs granularités, en tenant compte de la structure du graphe. Ensuite, les résultats d'explication sont optimisés afin de maximiser l'information portée par la combinaison de sous-structures individuelles, garantissant ainsi une représentation fidèle des propriétés du graphe. En intégrant une prise en compte équitable des interactions entre caractéristiques lors de l'analyse de plusieurs sous-structures importantes connectées, l'explication fournie par SAME a le potentiel d’atteindre une explicabilité proche de celle théoriquement optimale obtenue via la valeur de Shapley, tout en restant calculable en temps polynomial. Des expériences étendues sur des benchmarks réels et synthétiques montrent que SAME améliore la performance de fidélité par rapport à l'état de l'art précédent de 12,9 % sur BBBP, 7,01 % sur MUTAG, 42,3 % sur Graph-SST2, 38,9 % sur Graph-SST5, 11,3 % sur BA-2Motifs et 18,2 % sur BA-Shapes, sous les mêmes conditions de test. Le code est disponible à l’adresse suivante : https://github.com/same2023neurips/same. Numéro de soumission : 12143