Sintesi Tecnica: TN-SHAP-G

Definizione del Problema

Spiegare le predizioni di reti neurali su grafi (GNN) "black-box" richiede l'attribuzione dell'importanza a singoli nodi e alle loro interazioni. Sebbene i valori di Shapley e gli indici di interazione di ordine superiore offrano attribuzioni basate su principi assiomatici, il loro calcolo esatto è intrattabile per i grafi, con una complessità che scala come $O(2^n)$, dove $n$ è il numero di nodi. Gli esistenti metodi di approssimazione affrontano trade-off significativi: gli explainer specifici per l'architettura (ad esempio, GNNExplainer) non sono applicabili a modelli black-box generici, mentre gli approcci basati sul campionamento (ad esempio, GraphSVX, SHAP-IQ) richiedono migliaia di valutazioni del modello e soffrono di un'elevata varianza, specialmente per le interazioni di ordine superiore. Inoltre, questi metodi di campionamento spesso non riescono a scalare su grafi più grandi dove l'enumerazione esatta è impossibile.

Metodologia: TN-SHAP-G

Gli autori propongono TN-SHAP-G, un framework che sfrutta le proprietà strutturali degli input strutturati a grafo per calcolare in modo efficiente e deterministico i valori di Shapley e le interazioni. L'idea centrale è apprendere un surrogato di rete tensoriale (TN) compatto e allineato al grafo che approssimi il comportamento del predittore rispetto agli input mascherati.

1. Il Gioco a Grafo Mascherato

Il metodo formalizza la spiegazione del grafo come un gioco cooperativo indotto dal mascheramento dei nodi. Per un grafo di input fisso $G=(V, E)$ con caratteristiche $X$ e una baseline $X^0$, una coalizione $S \subseteq V$ definisce una matrice di caratteristiche mascherata $X_S$ in cui i nodi in $S$ mantengono le loro caratteristiche originali e i nodi al di fuori di $S$ sono sostituiti dalle caratteristiche baseline. Il valore del gioco è $\nu(S) = f(G, X_S)$, dove $f$ è il predittore black-box.

2. Estensione Multilineare e Contrazione Tensoriale

Il calcolo diretto dei valori di Shapley richiede la somma su $2^n$ coalizioni. Gli autori utilizzano l'estensione multilineare $\hat{\nu}(z)$, una rilassazione continua del gioco discreto definita su $z \in [0, 1]^n$.

• Formulazione Tensoriale: L'estensione multilineare può essere espressa esattamente come una contrazione tensoriale: $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$, dove $T$ è il tensore delle coalizioni e $b_v(z_v)$ sono i vettori selettori di Bernoulli.
• Recupero Deterministico: I valori di Shapley e gli indici di interazione corrispondono agli integrali delle derivate parziali di $\hat{\nu}$ lungo la diagonale $z = t\mathbf{1}$. Poiché $\hat{\nu}$ è multilineare, queste derivate sono polinomi univariati di grado al massimo $n-1$. Pertanto, le attribuzioni esatte possono essere recuperate tramite interpolazione di Vandermonde da un piccolo numero di punti di sonda, eliminando la varianza di Monte Carlo.

3. Surrogato di Rete Tensoriale Allineata al Grafo

Poiché il tensore delle coalizioni completo $T$ ha $2^n$ voci, TN-SHAP-G apprende un surrogato di rete tensoriale allineata al grafo $\hat{\nu}$ per approssimare l'estensione multilineare.

• Topologia: La topologia della TN rispecchia il grafo di input $G$. Ogni nodo $v$ corrisponde a un tensore core $A^{(v)}$ con un indice fisico (che codifica l'appartenenza alla coalizione) e indici di legame (bond indices) che si connettono ai vicini.
• Espressività: La dimensione di legame $\chi$ controlla la capacità di flusso di informazioni attraverso i separatori del grafo. Gli autori dimostrano che per giochi con basso cut-rank attraverso i separatori del grafo (una proprietà di molti pattern di dipendenza locale nelle GNN), questa struttura allineata al grafo raggiunge un'espressività maggiore con meno parametri rispetto alle fattorizzazioni basate su catene come i Tensor Trains (TT), che soffrono di inflazione del rango su grafi ciclici o complessi.
• Addestramento: Il surrogato è addestrato tramite minimizzazione del rischio empirico su un piccolo set di coalizioni campionate ($M \ll 2^n$). Le garanzie teoriche mostrano che il budget di query richiesto scala quasi linearmente con il numero di nodi per grafi a grado limitato.

4. Inferenza

Una volta addestrato, il surrogato consente il calcolo deterministico di:

• Valori di Shapley del primo ordine: Tramite l'integrazione 1D della derivata diagonale.
• Interazioni di ordine superiore: Tramite derivate parziali miste e integrazione.
  Tutte le quantità sono calcolate dal singolo surrogato addestrato senza ulteriori query al modello black-box.

Contributi Chiave

1. Rappresentazione Principata Allineata al Grafo: Introduzione di un surrogato di rete tensoriale che comprime la tabella dei valori delle coalizioni esponenziale in una rappresentazione multilineare a basso rango e allineata al grafo. Ciò allinea il bias induttivo del surrogato con i pattern di dipendenza locale nei predittori grafici.
2. Calcolo Deterministico Ammortizzato: Sfruttamento della struttura multilineare per calcolare i valori di Shapley e le interazioni tramite interpolazione di Vandermonde a chiusura analitica. Ciò richiede solo $O(n)$ valutazioni del surrogato e non introduce alcuna varianza di Monte Carlo. Un singolo surrogato ammortizza il calcolo di tutti gli indici di primo e ordine superiore.
3. Garanzie Teoriche:
   • Dimostrazione che il surrogato appreso determina univocamente l'estensione multilineare, garantendo il recupero esatto delle attribuzioni sul surrogato.
   • Caratterizzazione dell'espressività tramite argomenti di cut-rank, provando che le TN allineate al grafo superano le fattorizzazioni a catena (come TT) in termini di prestazioni.
   • Limiti di complessità delle query del "teacher" quasi lineari per grafi a grado limitato.
   • Garanzie di stabilità che collegano l'errore di approssimazione del gioco all'errore di Shapley.
4. Prestazioni Empiriche: Dimostrata l'alta accuratezza e scalabilità su benchmark molecolari, raggiungendo una similarità del coseno $>0.99$ con i valori di Shapley esatti con appena 50 valutazioni del modello (10–100$\times$ meno rispetto ai baseline).

Risultati Sperimentali

Gli autori hanno valutato TN-SHAP-G su benchmark molecolari (Mutagenicity, Benzene) e grafi proteici (PROTEINS).

• Correttezza: Su grafi piccoli ($n \le 20$), TN-SHAP-G corrisponde strettamente ai valori di Shapley esatti (O1) e agli indici di interazione (O2), superando significativamente GraphSVX e il campionamento per permutazione sia in accuratezza che in varianza.
• Efficienza di Query: TN-SHAP-G raggiunge un'elevata accuratezza di attribuzione con 10–100$\times$ meno query al modello rispetto agli stimatori basati sul campionamento (SHAP-IQ, GraphSVX).
• Scalabilità: Il metodo scala efficientemente a grafi con fino a 600 nodi utilizzando un'architettura di surrogato basata su raggruppamento (coarsening), mentre i metodi di enumerazione esatta e basati sul campionamento diventano impraticabili.
• Ablazione della Struttura: Le TN allineate al grafo superano costantemente i surrogati Tensor Train (TT) a parità di parametri, confermando il vantaggio teorico delle fattorizzazioni allineate alla topologia.
• Proxy di Fedeltà: È stata osservata una forte correlazione tra l' $R^2$ di test del surrogato e la similarità del coseno dei valori di Shapley recuperati, validando l' $R^2$ come un proxy pratico per l'accuratezza dell'attribuzione.

Significato e Rivendicazioni

L'articolo afferma che TN-SHAP-G fa avanzare lo stato dell'arte nella spiegabilità dei grafi fornendo un framework rigoroso e model-agnostic che supera la complessità esponenziale del calcolo di Shapley. Sfruttando la struttura a basso rango intrinseca nei giochi cooperativi strutturati su grafi, il metodo consente un'attribuzione deterministica e priva di varianza con una complessità di query quasi lineare.

Gli autori sottolineano che questo approccio democratizza l'accesso a metodi di spiegazione rigorosi per i professionisti con risorse computazionali limitate, in particolare in domini ad alto rischio come la scoperta di farmaci e la previsione delle proprietà molecolari. Il framework è flessibile, supporta varie semantiche di gioco (ad esempio, mascheramento dei nodi, rimozione dei nodi, valori di Myerson) e tipi di caratteristiche, ed è estendibile oltre le classiche GNN a messaggi passanti verso altri predittori grafici. Il lavoro posiziona le reti tensoriali non solo come strumenti di compressione, ma come un meccanismo fondamentale per l'analisi trattabile dei giochi su dati strutturati.