Towards the Explainability of Temporal Graph Networks via Memory Backtracking and Topological Attribution

Sintesi Tecnica: Verso la Spiegabilità delle Reti di Grafi Temporali tramite il Backtracking della Memoria e l'Attribuzione Topologica

Definizione del Problema
Le Reti di Grafi Temporali (TGN) hanno raggiunto una precisione predittiva superiore in applicazioni del mondo reale come il rilevamento delle frodi e la previsione in ambito sanitario. Tuttavia, esse operano come modelli "black-box", offrendo scarsa trasparenza su come gli eventi storici guidino le predizioni. I metodi di spiegazione esistenti per le TGN (ad esempio, TGNNExplainer, TempME) si concentrano principalmente sulla struttura topologica del grafo, trascurando però il modulo di memoria, un componente fondamentale responsabile della registrazione e dell'aggiornamento della cronologia dei nodi. Fissando i vettori di memoria finali, questi metodi ignorano l'evoluzione temporale degli stati dei nodi, portando a spiegazioni non fedeli che non riescono a catturare come le interazioni passate si accumulino per plasmare le predizioni future.

Metodologia
Gli autori propongono MemExplainer, un framework che attribuisce le predizioni delle TGN sia agli eventi vicini (spaziale) che agli eventi storici (temporale), modellando esplicitamente il modulo di memoria. La metodologia si compone di tre fasi principali:

1. Albero di Attribuzione Topologica (Decomposizione Spaziale):
   Il framework costruisce un albero di attribuzione topologica per quantificare il contributo degli eventi vicini e dei vettori di memoria dei nodi rispetto all'embedding del nodo target. Utilizzando la Propagazione della Rilevanza per Livelli (LRP), il metodo decompone l'embedding del nodo target ($z^t_u$) nei contributi derivanti dalla memoria del nodo, dalle memorie dei vicini e dalle caratteristiche degli eventi. Un contributo teorico chiave è la dimostrazione di una proprietà di conservazione, che assicura che la somma dei contributi di tutti gli eventi vicini e delle memorie dei nodi sia uguale ai logit originali.

2. Albero di Backtracking della Memoria (Decomposizione Temporale):
   Per affrontare il limite dei vettori di memoria fissi, gli autori costruiscono un albero di backtracking della memoria. Questo albero traccia ricorsivamente l'influenza degli eventi storici sui vettori di memoria attuali dei nodi. Applicando la LRP alla funzione di aggiornamento della memoria (ad esempio, GRU o RNN), il metodo attribuisce il contributo dello stato di memoria attuale ai processi di memoria specifici che hanno innescato gli aggiornamenti storici. Questo processo assicura che il contributo totale di tutti gli eventi storici sia uguale al contributo totale della memoria, mantenendo la proprietà di conservazione lungo la dimensione temporale.

3. Selezione degli Eventi tramite Ottimizzazione:
   A causa della mappatura non lineare dai logit alle probabilità, una semplice selezione top-$k$ degli eventi può non essere fedele. Per affrontare questo problema, gli autori derivano la divergenza KL tra la predizione originale e la predizione effettuata utilizzando solo un sottoinsieme di eventi selezionati. Formulano un problema di ottimizzazione per selezionare un sottoinsieme di eventi importanti ($E^*$) che minimizzi tale divergenza, garantendo che la spiegazione riproduca fedelmente il comportamento del modello.

Contributi Chiave

• Spiegazione Consapevole della Memoria: A differenza dei lavori precedenti che fissano i vetti di memoria, questo metodo traccia esplicitamente come gli eventi storici aggiornano le memorie dei nodi, fornendo un'attribuzione più fedele delle predizioni.
• Proprietà di Conservazione: Il framework assicura che la somma dei contributi di tutti gli eventi (sia vicini che storici) sia uguale ai logit finali del modello, una proprietà critica per una spiegazione rigorosa.
• Architettura a Doppio Albero: La combinazione di un albero di attribuzione topologica (spaziale) e di un albero di backtracking della memoria (temporale) consente una decomposizione completa delle predizioni delle TGN.
• Selezione Basata sull'Ottimizzazione: L'uso della minimizzazione della divergenza KL per la selezione degli eventi evita le criticità della selezione euristica top-$k$ nei modelli non lineari.

Risultati Sperimentali
Il metodo è stato valutato su nove dataset di grafi temporali che coprono compiti di link prediction, predizione di proprietà dei nodi e classificazione di grafi (inclusi dataset Wikipedia, Reddit, Enron, UCI e dataset di riconoscimento di azioni umane).

• Performance: MemExplainer ha superato costantemente i baseline allo stato dell'arte (TGNNExplainer, TempME, GNNExpleler, PGExplainer) in termini di Fedeltà (misurata come $Fidelity_{KL}$ e $Fidelity_{prob}$) in tutti i dataset.
• Significatività Statistica: Un t-test tra MemExplainer e il secondo miglior baseline ha mostrato una significatività statistica nel 77% dei casi per $Fidelity_{KL}$ e nel 74% per $Fidelity_{prob}$.
• Casi di Studio: Nella classificazione delle azioni basata sulla posa umana, MemExplainer ha selezionato sottoinsiemi di archi più piccoli e focalizzati che si allineavano con le catene biomeccaniche chiave (ad esempio, anca-ginocchio-caviglia per la corsa), mentre i baseline spesso selezionavano un numero eccessivo di archi non informativi.
• Efficienza: Il metodo rimane computazionalmente fattibile, con tempi di esecuzione totali inferiori a 6 secondi anche con un profondo backtracking della memoria (profondità 10) su grandi dataset.

Significatività e Rivendicazioni
Il documento sostiene che, integrando il backtracking della memoria con l'attribuzione topologica, MemExplainer fornisce spiegazioni fedeli che rivelano il ruolo critico del modulo di memoria nelle TGN. Gli autori affermano che il loro metodo migliora l'affidabilità delle TGN, elemento essenziale per il loro impiego sicuro in domini ad alto rischio. Il lavoro evidenzia come ignorare l'evoluzione temporale delle memorie dei nodi porti ad attribuzioni imprecise, e il loro approccio basato sulla conservazione offre una soluzione robusta per comprendere le complesse dipendenze temporali. Gli autori notano con modestia un limite relativo ai costi computazionali su grafi molto grandi con backtracking della memoria profondo, suggerendo ricerche future su potatura o limitazione della profondità.