💻 computer science

A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks

Cet article propose un nouveau cadre agnostique au modèle pour générer des explications contrefactuelles de haute qualité dans les réseaux de neurones sur graphes en intégrant l'explicabilité factuelle à des modèles de prédiction d'arêtes manquantes, démontrant une performance supérieure par rapport aux bases de référence de l'état de l'art sur divers benchmarks de classification de graphes.

Auteurs originaux : Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, Panos Trahanias

Publié 2026-06-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, Panos Trahanias

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez un robot super intelligent (un Réseau de Neurones sur Graphes) qui observe un réseau de connexions complexes — comme un réseau social, une molécule ou une carte d'amitiés — et prend une décision, telle que « Cette molécule est toxique » ou « Ce tweet est en colère ».

Le problème est que le robot est une « boîte noire ». Il donne la réponse, mais il ne vous dit pas pourquoi. Vous voulez savoir : « Quel petit changement ferait changer d'avis le robot ? » C'est ce qu'on appelle une Explication Contrefactuelle. C'est comme demander : « Si je n'avais pas dit cette chose précise, l'issue aurait-elle été différente ? »

Cet article présente un nouvel outil appelé DR-CFGNN pour répondre à cette question mieux que les outils précédents. Voici comment il fonctionne, en utilisant des analogies simples :

Le problème des anciens outils

Les outils précédents tentaient d'expliquer la décision du robot en faisant soit :

Retirant des éléments : Comme un sculpteur qui dégaje la pierre pour voir quelle forme subsiste. Ils ne pouvaient que supprimer des connexions (arêtes) du graphe.
Devinant au hasard : En essayant d'ajouter ou de supprimer des connexions en lançant des fléchettes dans le noir.

Les auteurs affirment que ces méthodes sont limitées. Parfois, pour changer l'avis du robot, il ne suffit pas de simplement supprimer une mauvaise connexion ; il peut être nécessaire d'en ajouter une qui manquait. C'est comme essayer de réparer un puzzle cassé : parfois, vous devez retirer une mauvaise pièce, mais d'autres fois, vous devez trouver la pièce manquante qui complète l'image.

La nouvelle solution : Le cadre « Sensible à la Complétion » (Completion-Aware)

Les auteurs ont construit un cadre qui traite le graphe comme un puzzle avec des pièces manquantes. Ils l'appellent « sensible à la complétion » car il sait comment combler les vides.

Le processus se déroule en quatre étapes, comme un atelier à quatre étapes :

1. Le filtre à bruit (Débruitage)

Les données du monde réel sont désordonnées. Imaginez un réseau social où certaines amitiés ont été ajoutées par erreur (spam).

Ce que l'outil fait : Avant d'analyser le graphe, il utilise un « filtre à bruit » pour nettoyer le désordre. Il supprime les connexions faibles ou improbables qui n'ont probablement pas d'importance. Cela rend le puzzle plus clair avant de commencer le travail.

2. La déconstruction (Trouver le coupable)

L'outil examine maintenant le graphe nettoyé pour trouver la partie spécifique qui a convaincu le robot de prendre sa décision initiale.

L'analogie : Imaginez que le robot ait décidé qu'un film était « Effrayant » à cause d'une scène spécifique. Cette étape isole cette scène. Elle ne regarde pas tout le film ; elle se concentre uniquement sur la partie effrayante. Elle tente ensuite de « briser » cette scène spécifique en supprimant quelques connexions clés pour voir si le robot cesse d'avoir peur.

3. La reconstruction (La magie de la prédiction de liens)

C'est la grande innovation de cet article. Au lieu de simplement briser des choses, l'outil demande : « Et si nous ajoutions quelque chose pour changer l'histoire ? »

L'analogie : Pensez à un détective qui connaît les « règles du quartier ». Si le robot pense qu'une molécule est toxique, cette étape demande : « Et si nous ajoutions une liaison chimique spécifique qui rend habituellement les choses sûres ? »
L'outil utilise une technique de Prédiction de Liens (généralement utilisée pour deviner qui sera ami avec qui à l'avenir) pour suggérer intelligemment de nouvelles connexions. Il ne devine pas au hasard ; il cherche des motifs qui mèneraient logiquement le robot à une autre conclusion (par exemple, de « Toxique » à « Sûr »).

4. Le tri (Optimisation Post-Hoc)

L'outil peut générer de nombreuses façons de modifier le graphe. Certaines modifications sont minuscules et précises ; d'autres sont énormes et désordonnées.

Ce que l'outil fait : Il classe ces options. Il privilégie les changements « minimaux » — les modifications les plus petites et les plus logiques qui inversent la décision du robot. C'est comme un éditeur qui préfère changer un seul mot plutôt que de réécrire tout le paragraphe.

Pourquoi est-ce meilleur ?

Les auteurs ont testé leur outil sur de nombreux types de graphes (allant de puzzles synthétiques fictifs à des données réelles comme des molécules ou des tweets) et l'ont comparé aux meilleurs outils existants.

Éditions plus intelligentes : Leur outil a bien mieux trouvé les « pièces manquantes » que les autres. Il ne s'est pas contenté de supprimer des éléments ; il savait exactement quoi ajouter pour changer le résultat.
Changements plus réduits : Les explications étaient « compactes ». Au lieu de suggérer de changer 50 connexions, il a souvent trouvé que changer seulement 2 ou 3 suffisait. Cela rend l'explication plus facile à comprendre pour les humains.
Plus précis : Les changements suggérés étaient très proches de la « vérité terrain » (la raison réelle pour laquelle le robot prenait sa décision).
Plus rapide : Parce qu'il utilise un échantillonnage intelligent (en regardant aux bons endroits) plutôt que de vérifier chaque possibilité, il s'exécute beaucoup plus rapidement que les outils lourds et lents qui tentent d'explorer toutes les possibilités.

L'essentiel

Cet article présente une nouvelle façon d'expliquer les décisions de l'IA sur les graphes. Au lieu de simplement dégager les données ou de deviner au hasard, il agit comme un expert en résolution de puzzles : il nettoie le plateau, trouve la pièce critique, puis ajoute intelligemment la pièce manquante pour changer l'image finale. Cela donne des explications plus courtes, plus précises et plus faciles à rendre crédibles pour les humains.

Résumé technique : Un cadre de complétion pour une explicabilité contrefactuelle percutante dans les réseaux de neurones sur graphes

Énoncé du problème

Les réseaux de neurones sur graphes (GNN) sont de plus en plus déployés dans divers domaines, pourtant leur nature de « boîte noire » pose des défis importants en matière d'interprétabilité. Bien que les expliqueurs factuels (identifiant les sous-graphes cruciaux pour une prédiction) soient bien établis, les Explications Contrefactuelles (CfX) — qui suggèrent des modifications minimales à un graphe d'entrée pour altérer la prédiction du modèle — restent sous-développées.

Les méthodes de CfX existantes font face à plusieurs limitations :

Suppression d'arêtes uniquement : De nombreuses approches précoces (par exemple, CF-GNNExplainer, CFExplainer) limitent les explications à la suppression d'arêtes, ce qui limite leur pouvoir expressif et aboutit souvent à des suggestions hors distribution (OOD).
Efficacité et généralisabilité : Les méthodes capables d'ajouter et de supprimer des arêtes (par exemple, LEGIT, MEG, D4Explainer) souffrent souvent d'une complexité computationnelle élevée, nécessitent des connaissances approfondies sur le domaine ou reposent sur des modèles causaux spécifiques qui ne sont pas toujours disponibles.
Absence d'analyse comparative : Il existe une rareté d'évaluations exhaustives comparant les cadres de pointe qui supportent à la fois l'ajout et la suppression d'arêtes.

Le défi central abordé est la génération de CfX génériques, agnostiques au modèle et au niveau local qui soient efficaces, robustes et intuitivement significatives (c'est-à-dire suggérant des changements structurels plausibles plutôt que des éditions arbitraires).

Méthodologie : Le cadre DR-CFGNN

Les auteurs proposent DR-CFGNN (De/Re-construction-driven Counterfactual GNN), un pipeline qui intègre des enseignements de la prédiction de liens pour améliorer la qualité et la robustesse de la génération de CfX. Le cadre opère en quatre phases distinctes :

1. Débruitage (Phase I)

Les graphes du monde réel contiennent souvent du bruit (liens non pertinents). Le cadre utilise un modèle de prédiction de liens entraîné (sans conditionnement de classe) pour estimer les probabilités d'arêtes. Les arêtes ayant la probabilité la plus faible sont supprimées, à condition que leur suppression n'altère pas la prédiction originale de l'oracle. Cette étape affine le graphe d'entrée ( $G_{DeN}$ ) avant la génération de l'explication.

2. Déconstruction (Phase II)

Au lieu de chercher dans l'ensemble du graphe les arêtes à supprimer, le cadre extrait d'abord un sous-graphe factuel ( $G_F$ ) en utilisant un expliqueur factuel existant (par exemple, SubgraphX). Il supprime ensuite sélectivement des arêtes uniquement de ce sous-graphe factuel. Cette stratégie affaiblit le support de la prédiction originale sans nécessairement la renverser immédiatement, concentrant la recherche sur les motifs spécifiques qui pilotent la décision de l'oracle.

3. Reconstruction (Phase III)

Il s'agit du composant central « sensible à la complétion ». Le cadre entraîne un modèle d'expansion de graphe (une architecture encodeur-décodeur) pour prédire les arêtes manquantes qui mèneraient à une classe contrefactuelle cible ( $y_{CF}$ ).

Architecture : Un encodeur de type GCN (Graph Convolutional Network) génère des plongements de nœuds. Un plongement spécifique à la classe (dérivé d'un vecteur one-hot de la classe cible) est concaténé avec les plongements de nœuds. Un décodeur MLP (Multi-Layer Perceptron) prédit ensuite la probabilité d'arêtes entre les paires de nœuds.
Apprentissage inductif : Contraٌirement à la prédiction de liens transductive traditionnelle, ce modèle est entraîné de manière inductive sur une collection de graphes pour se généraliser à des graphes de test et des motifs inédits.
Contraintes de domaine : Le processus d'entraînement peut incorporer des connaissances métier en fixant certaines arêtes (par exemple, des liaisons chimiques) comme étant toujours présentes ou impossibles, garantissant ainsi des explications plausibles.
Inférence : Le modèle estime la probabilité des arêtes inexistantes dans le graphe déconstruit. Les arêtes dépassant un seuil sont ajoutées pour générer des contrefactuels candidats.

4. Optimisation Post-hoc (Phase IV)

Pour gérer l'ensemble potentiellement large de CfX générés, une fonction de score équilibre la fidélité (chute de confiance dans la classe originale) et la taille de l'explication (nombre d'éditions). Une fonction de décroissance lisse pénalise les ensembles d'éditions plus larges, privilégiant les explications compactes et de haute confiance sans ajouter de contraintes complexes à la boucle d'optimisation elle-même.

Stratégie d'échantillonnage

Pour garantir l'efficacité, le cadre utilise un schéma d'échantillonnage probabiliste (basé sur une fonction de décroissance de type gaussienne) pour déterminer le nombre d'arêtes à supprimer ( $r$ ) et à ajouter ( $k$ ). Cela permet un réglage spécifique au domaine, favorisant généralement moins de suppressions (car la suppression d'une seule arête critique peut être impactante) et plus de flexibilité dans le nombre d'ajouts.

Contributions clés

Méthodologie de Déconstruction/Reconstruction : Un pipeline novateur qui sépare les tâches d'affaiblissement de la prédiction originale et de renforcement de la prédiction cible. Cette approche améliore les performances pour la génération de CfX in-distribution et améliore considérablement la compacité et la pertinence des motifs des explications.
Intégration de la prédiction de liens : La première étude à coupler explicitement la recherche sur la prédiction de liens avec l'explicabilité contrefactuelle des GNN, en tirant parti de la capacité des prédicteurs de liens à suggérer des placements d'arêtes bien ciblés sur des graphes complexes.
Efficacité et Contrôlabilité : Le cadre permet un réglage via des paramètres d'échantillonnage et l'assertion de connaissances de domaine, atteignant une haute efficacité sans sacrifier la performance.
Évaluation complète : L'article présente la première étude comparative multi-facettes des principaux expliqueurs CF locaux (incluant ceux supportant l'ajout d'arêtes) sur des tâches de classification binaire et multi-labels sur des jeux de données synthétiques et réels.

Résultats expérimentaux

Le cadre a été évalué sur des jeux de données synthétiques (BA-Motifs), des jeux de données de sentiment (Graph-Twitter, Graph-SST5) et des jeux de données moléculaires (BBBP).

Validité et Compacité : Les variantes de DR-CFGNN ont obtenu des scores de validité élevés (souvent comparables aux baselines globales) tout en générant des explications nettement plus petites. Par exemple, sur le jeu de données BBBP, il a atteint une validité de 0,81 avec une moyenne de seulement 3 éditions, alors que les baselines nécessitaient 3,5x à 5,6x plus d'arêtes.
Proximité des motifs : Le cadre a nettement surpassé les baselines en termes de proximité des motifs, ce qui signifie que les éditions suggérées étaient concentrées autour des motifs de vérité terrain responsables de la prédiction originale, plutôt que d'être des éditions distantes et arbitraires.
Minimalité : DR-CFGNN a obtenu des scores de minimalité exceptionnellement élevés (proches de 1,0), indiquant que les explications générées ne contiennent que les éditions nécessaires et peu d'éditions redondantes.
Robustesse : Sous l'effet de bruit d'entrée (perturbations de nœuds/arêtes), DR-CFGNN a démontré la performance la plus cohérente parmi les expliqueurs locaux, maintenant une validité élevée et une stabilité structurelle (mesurée par la cohérence des arêtes après bruit).
Efficacité : Le cadre a présenté des temps d'entraînement et d'inférence faibles par rapport aux méthodes basées sur la diffusion (D4Explainer) ou de recherche exhaustive. L'étape de débruitage seule a réduit le temps d'exécution jusqu'à 50 % dans certains cas.

Signification et Revendications

L'article soutient que la perspective de complétion (intégration de la prédiction de liens) est cruciale pour générer des contrefactuels percutants. En découplant la déconstruction de la reconstruction, le cadre évite les pièges de l'optimisation de bout en bout qui mène souvent à des éditions OOD ou à une complexité excessive.

Les auteurs soulignent que leur approche atteint un compromis supérieur entre couverture (validité), qualité (fidélité, proximité des motifs, minimalité) et efficacité. Ils affirment que bien qu'une approche universellement supérieure soit difficile à obtenir en raison de la nature multi-facettes du problème, DR-CFGNN produit systématiquement des explications hautement qualitatives, compactes et robustes sans nécessiter d'ingénierie complexe de fonctions de perte. L'étude souligne l'importance d'évaluer diverses métriques de qualité au-delà de la simple validité et suggère que les travaux futurs pourraient étendre cette approche aux graphes temporels et à l'IA neuro-symbolique pour la vérification formelle.