🤖 machine learning

TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions

L'article présente TN-SHAP-G, un cadre qui utilise des substituts de réseaux de tenseurs alignés sur les graphes pour calculer efficacement les valeurs de Shapley exactes et les interactions d'ordre supérieur pour les entrées structurées en graphes, surmontant ainsi la complexité exponentielle et la variance d'échantillonnage inhérentes aux méthodes traditionnelles.

Auteurs originaux : Farzaneh Heidari, Guillaume Rabusseau

Publié 2026-06-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Farzaneh Heidari, Guillaume Rabusseau

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 possédez une machine complexe, une « boîte noire », qui prend en photo une molécule (un graphe d'atomes et de liaisons) et prédit si elle est dangereuse ou sûre. Vous voulez savoir : quels atomes spécifiques sont responsables de cette prédiction ? Et plus important encore, est-ce que certains groupes d'atomes travaillent ensemble pour créer ce résultat ?

C'est ici que les valeurs de Shapley entrent en jeu. Considérez-les comme un moyen équitable de répartir le « crédit » d'une prédiction entre tous les joueurs (les atomes) du jeu. Cependant, calculer ce crédit est un cauchemar. Pour savoir exactement quelle est la contribution d'un atome, il faut tester toutes les combinaisons possibles d'atomes (en gardant certains, en en cachant d'autres) pour voir comment la prédiction change. Si vous avez 20 atomes, il existe plus d'un million de combinaisons. Si vous en avez 50, le nombre est si gigantesque qu'il faudrait plus longtemps que l'âge de l'univers pour tout vérifier.

Les méthodes actuelles tentent de deviner la réponse en échantillonnant des combinaisons aléatoires, mais cela est lent, bruité et manque souvent de précision sur le travail d'équipe subtil entre les atomes.

TN-SHAP-G est une nouvelle méthode qui résout ce problème en agissant comme un traducteur intelligent et un raccourci. Voici comment cela fonctionne, en utilisant des analogies simples :

1. L'« Ombre Chinoise » (Le Substitut)

Au lieu de demander à la machine boîte noire d'effectuer des millions de tests, TN-SHAP-G lui demande d'en effectuer seulement quelques centaines (comme goûter une soupe avec différents ingrédients pour deviner la recette).

Elle construit ensuite une version simplifiée en « ombre chinoise » de la machine. Il ne s'agit pas d'une supposition aléatoire ; c'est une structure mathématique appelée Réseau de Tenseurs (Tensor Network).

L'Analogie : Imaginez que la molécule est le plan d'une ville. La machine boîte noire est un système de circulation complexe. TN-SHAP-G construit un modèle simplifié de cette ville où les routes (les connexions entre les atomes) sont préservées, mais où les règles de circulation sont simplifiées en une carte compacte et facile à calculer.
La Clé : Cette carte simplifiée est construite pour ressembler exactement à la forme de la molécule. Si la molécule a une forme d'anneau, le modèle mathématique possède également une forme d'anneau. Cela permet de capturer comment les atomes influencent leurs voisins sans avoir besoin de simuler l'univers entier.

2. La « Formule Magique » (Récupération Déterministe)

Une fois que ce « substitut d'ombre chinoise » est entraîné, la magie opère. Parce que le modèle est construit à l'aide d'un type spécifique de mathématiques (des polynômes multilinéaires), les auteurs ont découvert une formule sous forme close pour calculer le crédit exact de chaque atome.

L'Analogie : Habituellement, pour trouver la vitesse moyenne d'une voiture, vous pourriez la chronométrer 1 000 fois et en faire la moyenne (échantillonnage). TN-SHAP-G est comme si vous possédiez le plan parfait du moteur de la voiture. Vous n'avez pas besoin de faire rouler la voiture 1 000 fois ; il vous suffit de brancher le plan dans une calculatrice, et elle vous donne instantanément la vitesse exacte.
Le Résultat : Une fois le modèle entraîné, il peut générer instantanément et parfaitement l'importance de chaque atome et de chaque paire d'atomes, sans aucun tâtonnement ni aléatoire.

3. Pourquoi est-ce meilleur ? (L'avantage du « Travail d'Équipe »)

La plupart des méthodes ont du mal à comprendre comment deux atomes travaillent ensemble (interactions). Elles sont comme si l'on essayait de deviner une poignée de main secrète en regardant des gens se serrer la main de manière aléatoire.

TN-SHAP-G est comme si l'on regardait la poignée de main se produire au ralenti sur un plan technique. Elle peut calculer exactement quelle « synergie » existe entre deux atomes (par exemple : « l'azote et l'oxygène ensemble sont 10 fois plus dangereux que chacun d'eux seul ») sans avoir besoin de tests supplémentaires.
Efficacité : Alors que d'autres méthodes pourraient nécessiter 5 000 ou 50 000 requêtes à la machine boîte noire pour obtenir une réponse décente, TN-SHAP-G obtient souvent une réponse quasi parfaite avec seulement 50 à 100 requêtes.

4. Ce qu'ils ont testé

Les auteurs ont testé cela sur des molécules (comme des médicaments et des protéines).

Petites Molécules : Ils ont comparé la méthode à la « référence absolue » (vérifier chaque combinaison individuelle). TN-SHAP-G correspond presque parfaitement à la référence (99 % de précision ou plus), mais elle est des milliers de fois plus rapide.
Grandes Molécules : Ils l'ont testée sur de grandes structures protéiques où les autres méthodes plantent simplement ou prennent trop de temps. TN-SHAP-G les a gérées sans difficulté, passant à l'échelle supérieure avec des graphes comprenant des centaines de nœuds.

Résumé

TN-SHAP-G est un outil qui apprend une « fiche de triche » compacte et sensible à la forme de la manière dont un modèle boîte noire prend ses décisions. Une fois qu'il possède cette fiche de triche, il peut calculer instantanément et parfaitement quelles parties d'un graphe (comme une molécule) sont importantes et comment elles travaillent ensemble, sans avoir besoin de demander des millions de réponses à la machine boîte noire. Il transforme un problème qui nécessite habituellement un supercalculateur et une vie entière d'attente en quelque chose de soluble sur un ordinateur standard en quelques secondes.

Résumé Technique : TN-SHAP-G

Énoncé du Problème

Expliquer les prédictions des réseaux de neurones sur graphes (GNN) de type "boîte noire" nécessite d'attribuer l'importance aux nœuds individuels et à leurs interactions. Bien que les valeurs de Shapley et les indices d'interaction d'ordre supérieur offrent des attributions fondées sur des axiomes, leur calcul exact est intraitable pour les graphes, avec une complexité de $O(2^n)$ où $n$ est le nombre de nœuds. Les méthodes d'approximation existantes font face à des compromis importants : les expliqueurs spécifiques à l'architecture (par exemple, GNNExpliner) ne s'appliquent pas aux modèles génériques de type boîte noire, tandis que les approches basées sur l'échantillonnage (par exemple, GraphSVX, SHAP-IQ) nécessitent des milliers d'évaluations du modèle et souffrent d'une variance élevée, particulièrement pour les interactions d'ordre supérieur. De plus, ces méthodes d'échantillonnage échouent souvent à passer à l'échelle sur de grands graphes où l'énumération exacte est impossible.

Méthodologie : TN-SHAP-G

Les auteurs proposent TN-SHAP-G, un cadre qui exploite les propriétés structurelles des entrées structurées en graphes pour calculer efficacement et de manière déterministe les valeurs de Shapley et les interactions. L'idée centrale est d'apprendre un substitut (surrogate) de réseau de tenseurs (TN) compact et aligné sur le graphe qui approxime le comportement des entrées masquées du prédicteur.

1. Le Jeu de Graphe Masqué

La méthode formalise l'explication de graphe comme un jeu coopératif induit par le masquage de nœuds. Pour un graphe d'entrée fixé $G=(V, E)$ avec des caractéristiques $X$ et une référence (baseline) $X^0$ , une coalition $S \subseteq V$ définit une matrice de caractéristiques masquée $X_S$ où les nœuds dans $S$ conservent leurs caractéristiques originales et les nœuds hors de $S$ sont remplacés par les caractéristiques de référence. La valeur du jeu est $\nu(S) = f(G, X_S)$ , où $f$ est le prédicteur boîte noire.

2. Extension Multilinéaire et Contraction de Tenseur

Le calcul direct des valeurs de Shapley nécessite de sommer sur $2^n$ coalitions. Les auteurs utilisent l'extension multilinéaire $\hat{\nu}(z)$ , une relaxation continue du jeu discret définie sur $z \in [0, 1]^n$ .

Formulation Tensorielle : L'extension multilinéaire peut être exprimée exactement comme une contraction de tenseur : $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$ , où $T$ est le tenseur de coalition et $b_v(z_v)$ sont les vecteurs sélecteurs de Bernoulli.
Récupération Déterministe : Les valeurs de Shapley et les indices d'interaction correspondent aux intégrales des dérivées partielles de $\hat{\nu}$ le long de la diagonale $z = t\mathbf{1}$ . Comme $\hat{\nu}$ est multilinéaire, ces dérivées sont des polynômes univariés de degré au plus $n-1$ . Ainsi, les attributions exactes peuvent être récupérées via l'interpolation de Vandermonde à partir d'un petit nombre de points de sondage, éliminant ainsi la variance de Monte Carlo.

3. Substitut de Réseau de Tenseurs Aligné sur le Graphe

Puisque le tenseur de coalition complet $T$ possède $2^n$ entrées, TN-SHAP-G apprend un substitut de réseau de tenseurs aligné sur le graphe $\hat{\nu}$ pour approximer l'extension multilinéaire.

Topologie : La topologie du TN reflète le graphe d'entrée $G$ . Chaque nœud $v$ correspond à un tenseur central $A^{(v)}$ possédant un indice physique (encodant l'appartenance à la coalition) et des indices de liaison connectés à ses voisins.
Expressivité : La dimension de liaison $\chi$ contrôle la capacité de flux d'information à travers les séparateurs de graphes. Les auteurs prouvent que pour les jeux présentant un faible rang de coupure (cut-rank) à travers les séparateurs de graphes (une propriété de nombreux schémas de dépendance locale dans les GNN), cette structure alignée sur le graphe atteint une expressivité plus élevée avec moins de paramètres que les factorisations basées sur des chaînes comme les Tensor Trains (TT), qui souffrent d'une inflation de rang sur les graphes cycliques ou complexes.
Entraînement : Le substitut est entraîné via la minimisation du risque empirique sur un petit ensemble de coalitions échantillonnées ( $M \ll 2^n$ ). Les garanties théoriques montrent que le budget de requêtes requis suit une croissance quasi linéaire avec le nombre de nœuds pour les graphes de degré borné.

4. Inférence

Une fois entraîné, le substitut permet le calcul déterministe de :

Valeurs de Shapley de premier ordre : Via l'intégration 1D de la dérivée diagonale.
Interactions d'ordre supérieur : Via les dérivées partielles mixtes et l'intégration.
Toutes les quantités sont calculées à partir du seul substitut entraîné sans requêtes supplémentaires au modèle boîte noire.

Contributions Clés

Représentation Fondée sur le Graphe : Introduction d'un substitut de réseau de tenseurs qui compresse la table des valeurs de coalition exponentielle en une représentation multilinéaire de bas rang et alignée sur le graphe. Cela aligne le biais inductif du substitut avec les schémas de dépendance locale des prédicteurs de graphes.
Calcul Déterministe Amorti : Utilisation de la structure multilinéaire pour calculer les valeurs de Shapley et les interactions via l'interpolation de Vandermonde en forme fermée. Cela nécessite seulement $O(n)$ évaluations du substitut et n'introduit aucune variance de Monte Carlo. Un seul substitut permet d'amortir le calcul de tous les indices de premier et d'ordre supérieur.
Garanties Théoriques :
- Preuve que le substitut appris détermine de manière unique l'extension multilinéaire, assurant une récupération exacte des attributions sur le substitut.
- Caractérisation de l'expressivité via des arguments de rang de coupure, prouvant que les TN alignés sur le graphe surpassent les factorisations en chaîne (comme TT) pour les jeux structurés en graphes.
- Bornes de complexité de requête "enseignant" quasi linéaires pour les graphes de degré borné.
- Garanties de stabilité liant l'erreur d'approximation du jeu à l'erreur de Shapley.
Performance Empirique : Démontré une haute précision sur des benchmarks moléculaires, atteignant une similitude cosinus $>0,99$ avec les valeurs de Shapley exactes avec seulement 50 évaluations de modèle (10 à 100 fois moins que les bases de référence) et se développant sur des graphes là où les méthodes d'échantillonnage sont irréalisables.

Résultats Expérimentaux

Les auteurs ont évalué TN-SHAP-G sur des benchmarks moléculaires (Mutagenicity, Benzene) et des graphes de protéines (PROTEINS).

Exactitude : Sur de petits graphes ( $n \le 20$ ), TN-SHAP-G correspond étroitement aux valeurs de Shapley exactes (O1) et aux indices d'interaction (O2), surpassant significativement GraphSVX et l'échantillonnage par permutation tant en précision qu'en variance.
Efficacité des Requêtes : TN-SHAP-G atteint une haute précision d'attribution avec 10 à 100 fois moins de requêtes de modèle que les estimateurs basés sur l'échantillonnage (SHAP-IQ, GraphSVX).
Scalabilité : La méthode passe efficacement à l'échelle sur des graphes allant jusqu'à 600 nœuds en utilisant une architecture de substitut basée sur le coarsening (affinement), là où l'énumération exacte et les méthodes d'échantillonnage deviennent impraticables.
Ablation de Structure : Les TN alignés sur le graphe surpassent systématiquement les substituts Tensor Train (TT) sous des conditions de paramètres équivalents, confirmant l'avantage théorique des factorisations alignées sur la topologie.
Proxy de Fidélité : Une forte corrélation a été observée entre le $R^2$ de test du substitut et la similitude cosinus des valeurs de Shapley récupérées, validant le $R^2$ comme un proxy pratique de la précision d'attribution.

Signification et Revendications

L'article affirme que TN-SHAP-G fait progresser l'état de l'art de l'explicabilité des graphes en fournissant un cadre fondé sur des principes et agnostique au modèle qui surmonte la complexité exponentielle du calcul de Shapley. En exploitant la structure de bas rang inhérente aux jeux coopératifs structurés en graphes, la méthode permet une attribution déterministe et sans variance avec une complexité de requête quasi linéaire.

Les auteurs soulignent que cette approche démocratise l'accès aux méthodes d'explication rigoureuses pour les praticiens disposant de ressources computationnelles limitées, particulièrement dans des domaines à enjeux élevés comme la découverte de médicaments et la prédiction de propriétés moléculaires. Le cadre est flexible, supportant diverses sémantiques de jeu (par exemple, masquage de nœuds, suppression de nœuds, valeurs de Myerson) et de types de caractéristiques, et s'étend au-delà des GNN standards de passage de messages vers d'autres prédicteurs de graphes. Ce travail positionne les réseaux de tenseurs non seulement comme des outils de compression, mais comme un mécanisme fondamental pour l'analyse de jeux tractable sur des données structurées.