Technische Samenvatting: TN-SHAP-G

Probleemstelling

Het verklaren van voorspellingen van black-box graph neural networks (GNN's) vereist het toeschrijven van belang aan individuele knopen en hun interacties. Hoewel Shapley-waarden en hogere-orde interactie-indices principiële, axiomatische attributies bieden, is hun exacte berekening onhandelbaar voor grafen, waarbij de complexiteit schaalt als $O(2^n)$ waarbij $n$ het aantal knopen is. Bestaande benaderingsmethoden kampen met significante afruil: architectuurspecifieke explainers (bijv. GNNExplainer) zijn niet toepasbaar op algemene black-box modellen, terwijl op sampling gebaseerde benaderingen (bijv. GraphSVX, SHAP-IQ) duizenden modelevaluaties vereisen en lijden onder een hoge variantie, met name voor hogere-orde interacties. Bovale falen deze sampling-methoden vaak bij het schalen naar grotere grafen waar exacte enumeratie onmogelijk is.

Methodologie: TN-SHAP-G

De auteurs stellen TN-SHAP-G voor, een framework dat de structurele eigenschappen van graafgestructureerde inputs exploiteert om Shapley-waarden en interacties efficiënt en deterministisch te berekenen. Het kernidee is het leren van een compacte, graaf-gealigneerde tensor netwerk (TN) surrogaat die het gedrag van de gemaskeerde input van de predictor benadert.

1. De Gemaskeerde Graaf-game

De methode formaliseert graaf-uitleg als een coöperatieve game geïnduceerd door knoop-maskering. Voor een vaste input-graaf $G=(V, E)$ met features $X$ en een baseline $X^0$, definieert een coalitie $S \subseteq V$ een gemaskeerde feature-matrix $X_S$ waarbij knopen in $S$ hun originele features behouden en knopen buiten $S$ worden vervangen door baseline-features. De game-waarde is $\nu(S) = f(G, X_S)$, waarbij $f$ de black-box predictor is.

2. Multilineaire Extensie en Tensor Contractie

Directe berekening van Shapley-waarden vereist het sommeren over $2^n$ coalities. De auteurs maken gebruik van de multilineaire extensie $\hat{\nu}(z)$, een continue relaxatie van de discrete game gedefinieerd op $z \in [0, 1]^n$.

• Tensor Formulering: De multilineaire extensie kan exact worden uitgedrukt als een tensor contractie: $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$, waarbij $T$ de coalitie-tensor is en $b_v(z_v)$ Bernoulli-selector vectoren zijn.
• Deterministisch Herstel: Shapley-waarden en interactie-indices komen overeen met integralen van partiële afgeleiden van $\hat{\nu}$ langs de diagonaal $z = t\mathbf{1}$. Omdat $\hat{\nu}$ multilineair is, zijn deze afgeleiden univariante polynomen van graad maximaal $n-1$. Hierdoor kunnen exacte attributies worden hersteld via Vandermonde-interpolatie vanaf een klein aantal probeerpunten, wat de Monte Carlo-variantie elimineert.

3. Graaf-Gealigneerde Tensor Netwerk Surrogaat

Aangezien de volledige coalitie-tensor $T$ $2^n$ entries heeft, leert TN-SHAP-G een graaf-gealigneerde tensor netwerk surrogaat $\hat{\nu}$ om de multilineaire extensie te benaderen.

• Topologie: De TN-topologie weerspiegelt de input-graaf $G$. Elke knoop $v$ komt overeen met een core-tensor $A^{(v)}$ met één fysieke index (die coalitie-lidmaatschap codeert) en bond-indices die verbinding maken met buren.
• Expressiviteit: De bond-dimensie $\chi$ controleert de capaciteit van informatiestroom over graaf-separatoren. De auteurs bewijzen dat voor games met een lage cut-rank over graaf-separatoren (een eigenschap van veel lokale afhankelijkheidspatronen in GNN's), deze graaf-gealigneerde structuur een hogere expressiviteit bereikt met minder parameters dan keten-gebaseerde factorisaties zoals Tensor Trains (TT), die lijden onder rank-inflatie op cyclische of complexe grafen.
• Training: De surrogaat wordt getraind via empirische risicominimalisatie op een kleine set gesamplede coalities ($M \ll 2^n$). Theoretische garanties tonen aan dat de vereiste query-budget schaalt nabij-lineair met het aantal knopen voor grafen met een begrensde graad.

4. Inferentie

Eenmaal getraind, maakt de surrogaat de deterministische berekening mogelijk van:

• Eerste-orde Shapley-waarden: Via 1D-integratie van de diagonaal-afgeleide.
• Hogere-orde interacties: Via gemengde partiële afgeleiden en integratie.
  Alle hoeveelheden worden berekend vanuit de enkele getrainde surrogaat zonder aanvullende queries naar het black-box model.

Belangrijkste Bijdragen

1. Geprincipeerde Graaf-Gealigneerde Representatie: Introductie van een tensor-netwerk surrogaat die de exponentiële coalitie-waarde tabel comprimeert tot een laag-rang, graaf-gealigneerde multilineaire representatie. Dit stemt de inductieve bias van de surrogaat af op lokale afhankelijkheidspatronen in graaf-predictors.
2. Geamortiseerde Deterministische Berekening: Het benutten van de multilineaire structuur om Shapley-waarden en interacties te berekenen via closed-form Vandermonde-interpolatie. Dit vereist slechts $O(n)$ surrogaat-evaluaties en introduceert geen Monte Carlo-variantie. Een enkele surrogaat amorteert de berekening van alle eerste- en hogere-orde indices.
3. Theoretische Garanties:
   • Bewijs dat de geleerde surrogaat de multilineaire extensie uniek bepaalt, wat zorgt voor exact herstel van attributies op de surrogaat.
   • Karakterisering van expressiviteit via cut-rank argumenten, waarmee wordt bewezen dat graaf-gealigneerde TN's beter presteren dan keten-factorisaties (zoals TT) voor graaf-gestructureerde games.
   • Nabij-lineaire teacher-query complexiteit bounds voor grafen met een begrensde graad.
   • Stabiliteitsgaranties die de game-benaderingsfout koppelen aan de Shapley-fout.
4. Empirische Prestaties: Gedemonstreerd hoge nauwkeurigheid en schaalbaarheid op moleculaire benchmarks, waarbij $>0,99$ cosine similarity wordt bereikt ten opzichte van exacte Shapley-waarden met slechts 50 model-evaluaties (10–100$\times$ minder dan baselines).

Experimentele Resultaten

De auteurs evalueerden TN-SHAP-G op moleculaire benchmarks (Mutagenicity, Benzene) en proteïne-grafen (PROTEINS).

• Correctheid: Op kleine grafen ($n \le 20$) komt TN-SHAP-G nauw overeen met exacte Shapley-waarden (O1) en interactie-indices (O2), waarbij het significant beter presteert dan GraphSVX en permutatie-sampling in zowel nauwkeurigheid als variantie.
• Query Efficiëntie: TN-SHAP-G bereikt een hoge attributie-nauwkeurigheid met 10–100$\times$ minder model-queries dan sampling-gebaseerde estimators (SHAP-IQ, GraphSVX).
• Schaalbaarheid: De methode schaalt efficiënt naar grafen met tot 600 knopen met behulp van een coarsening-gebaseerde surrogaat-architectuur, terwijl exacte enumeratie en sampling-gebaseerde methoden onpraktisch worden.
• Structuur Ablatie: Graaf-gealigneerde TN's presteren consistent beter dan Tensor Train (TT) surrogaten onder parameter-gegelijke condities, wat het theoretische voordeel van topologie-gealigneerde factorisaties bevestigt.
• Fidelity Proxy: Er werd een sterke correlatie waargenomen tussen de test $R^2$ van de surrogaat en de cosine similarity van de herstelde Shapley-waarden, wat de validatie vormt van $R^2$ als een praktische proxy voor attributie-nauwkeurigheid.

Betekenis en Claims

Het artikel claimt dat TN-SHAP-G de state-of-the-art in graaf-uitlegbaarheid vooruit helpt door een geprincieerd, model-agnostisch framework te bieden dat de exponentiële complexiteit van Shapley-berekening overwint. Door gebruik te maken van de laag-rang structuur die inherent is aan graaf-gestructureerde coöperatieve games, maakt de methode deterministische, variantievrije attributie mogelijk met een nabij-lineaire query-complexiteit.

De auteurs benadrukken dat deze aanpak de toegang tot rigoureuze uitlegmethoden democratiseert voor practitioners met beperkte computationele middelen, met name in hoog-risico domeinen zoals drug discovery en moleculaire eigenschappenvatting. Het framework is flexibel, ondersteunt diverse game-semantiek (bijv. knoop-maskering, knoop-verwijdering, Myerson-waarden) en feature-types, en breidt zich uit voorbij standaard message-passing GNN's naar andere graaf-predictors. Het werk positioneert tensor netwerken niet alleen als compressie-instrumenten, maar als een fundamenteel mechanisme voor tractabele game-theoretische analyse op gestructureerde data.