Sintesi Tecnica: Modello di Segnale Graph-Dictionary per la Rappresentazione Sparsa di Dati Multivariati

1. Definizione del Problema

I segnali multivariati, come l'attività cerebrale, i mercati finanziari o i flussi di traffico, spesso esibiscono dinamiche complesse e istantanee che variano tra i diversi campioni di dati. Sebbene questi sistemi siano governati da strutture relazionali sottostanti (grafi), tali strutture sono tipicamente nascoste e devono essere inferite dai segnali osservati nei nodi. Gli approcci esistenti affrontano diverse limitazioni:

• Apprendimento della Struttura del Grafo: Molti metodi assumono un singolo grafo statico o richiedono osservazioni di grafi allineati, fallendo nel catturare relazioni variabili per campione.
• Apprendimento del Dizionario (Dictionary Learning): Il tradizionale apprendimento del dizionario opera su spazi vettoriali, non su topologie di grafi.
• Clustering: Metodi come K-means o i Modelli a Miscela Gaussiana (Gaussian Mixtures) impongono assegnazioni rigide o "soft" a cluster statici, faticando a modellare cambiamenti continui o sistemi in cui molteplici strutture sottostanti si sovrappongono per generare un'unica osservazione.

La sfida centrale è sviluppare un modello che possa apprendere congiuntamente un insieme finito di strutture di grafo elementari (atomi) e i loro coefficienti di miscelazione sparsi e variabili nel tempo per spiegare le distribuzioni dei segnali multivariati, senza una conoscenza a priori della topologia del grafo.

2. Metodologia

A. Il Modello di Segnale Graph-Dictionary (GraphDict)

Gli autori propongono GraphDict, un framework probabilistico in cui un segnale multivariato $x_t \in \mathbb{R}^N$ al campione $t$ è generato da un grafo istantaneo $G_t$. Questo grafo non viene appreso isolatamente, ma è definito come una combinazione lineare di $K$ atomi di grafo $\{G_1, \dots, G_K\}$ provenienti da un dizionario.

• Processo Generativo:

  1. Atomi: Un dizionario di $K$ atomi di grafo è rappresentato da matrici di pesi degli archi $W = [w_1, \dots, w_K]$.
  2. Coefficienti: Per ogni campione $t$, un vettore di coefficienti $\delta_t \in [0, 1]^K$ determina il contributo di ciascun atomo.
  3. Grafo Istantaneo: Il Laplaciano del grafo istantaneo $L_t$ è una forma bilineare: $L_t = \sum_{k} \delta_{tk} L_{w_k}$.
  4. Generazione del Segnale: Il segnale è modellato come l'output di un filtro di grafo $k(L_t)$ applicato a un vettore casuale $\eta_t$. Nello specifico, gli autori utilizzano un Campo Aleatorio di Markov Gaussiano con vincolo Laplaciano (LGMRF), dove $x_t \sim \mathcal{N}(0, k^2(L_t))$.

• Obiettivo di Apprendimento:
  Il problema è formulato come una stima della Massima A Posteriori (MAP) per trovare il peso del dizionario $W$ e la matrice dei coefficienti $\Delta$. L'obiettivo minimizza la log-verosimiglianza negativa, incorporando dei prior per:

  • Sparsità: Regolarizzazione $L_1$ sia sui pesi degli atomi che sui coefficienti di miscelazione.
  • Ortogonalità: Una penalità sui prodotti scalari tra i pesi degli atomi per incoraggiare ruoli strutturali distinti.
  • Vincoli di Dominio: Non negatività dei pesi e dei coefficienti.

B. Ottimizzazione: Bilinear Primal-Dual Splitting (BiPDS)

Gli algoritmi standard di Primal-Dual Splitting (PDS) assumono un operatore lineare $A$ nel termine $h(Ax)$. Tuttavia, in GraphDict, l'operatore che mappa i coefficienti e i pesi al Laplaciano è bilineare.

Per risolvere questo problema, gli autori introducono BiPDS, una generalizzazione dell'algoritmo PDS:

• Operatore Bilineare: L'operatore $L(\Delta, W)$ mappa il prodotto di coefficienti e pesi nello spazio dei Laplaciani.
• Derivazione dell'Aggiunto: Gli autori derivano gli operatori aggiunti parziali $L^*$ e $L^{**}$ necessari per gli aggiornamenti delle variabili duali. Questi aggiunti mappano la variabile duale (relativa al tensore Laplaciano) nuovamente negli spazi dei pesi e dei coefficienti, rispettivamente.
• Algoritmo: L'algoritmo aggiorna iterativamente le variabili primali ($W, \Delta$) e la variabile duale ($Y$) utilizzando operatori prossimali e gli aggiunti derivati, gestendo la non-separabilità del termine bilineare.

C. Varianti Pratiche

Il documento dettaglia due specifiche istanze del modello:

1. GraphDictLog: Impone gradi dei nodi positivi utilizzando una barriera logaritmica sulla diagonale del Laplaciano. Questo è computazionalmente efficiente ed evita problemi numerici associati ai pseudo-determinanti.
2. GraphDictSpectral: Assume che tutti i grafi istantanei condividano gli stessi autovettori (base spettrale fissa), ottimizzando solo gli autovalori e i coefficienti. Ciò riduce la complessità evitando ripetute decomposizioni in autovalori ed autovettori.

3. Contributi Chiave

1. Nuovo Modello di Segnale: Introduzione di GraphDict, un modello probabilistico che definisce le distribuzioni dei segnali multivariati tramite un dizionario di grafi, permettendo la decomposizione di relazioni complesse e variabili per campione in combinazioni sparse di atomi di grafo elementari.
2. Algoritmo di Ottimizzazione: Sviluppo dell'algoritmo Bilinear Primal-Dual Splitting (BiPDS), una nuova generalizzazione del PDS capace di apprendere congiuntamente gli atomi del dizionario di grafi e i loro coefficienti di miscelazione.
3. Implementazione Pratica: Derivazione di funzioni di perdita specifiche e operatori prossimali che incorporano ipotesi comuni nell'apprendimento della struttura dei grafi (ad esempio, sparsità, smoothnes, ortogonalità).
4. Valutazione delle Prestazioni: Dimostrazione dell'efficacia del modello nella ricostruzione di grafi istantanei dai segnali e della sua utilità in compiti di classificazione downstream.

4. Risultati Sperimentali

A. Dati Sintetici: Grafi Sovrapposti

• Configurazione: I segnali sono stati generati da un dizionario di 5 grafi Erdős-Rényi con diversi livelli di "sovrapposizione" (da 1 a 5 atomi attivi per campione).
• Baseline: Confronto con Gaussian Mixtures, KGraphs e GLMM.
• Risultati: GraphDictLog ha superato costantemente le baseline nel recupero degli archi (misurato tramite il Coefficiente di Correlazione di Matthews - MCC), specialmente all'aumentare del livello di sovrapposizione. Mentre altri metodi faticavano con molteplici strutture sovrapposte, GraphDict è riuscito a disaggregarle con successo.

B. Dati Sintetici: Grafi Variabili nel Tempo

• Configurazione: Dati sequenziali generati da Edge-Markovian Evolving Graphs (EMEG) e Switching Behavior Graphs (SBG).
• Baseline: Confronto con WindowLogModel, TGFA e un modello gerarchico (GraphDictHier).
• Risultati: GraphDictLog ha raggiunto la massima precisione nel recupero degli archi in tutte le configurazioni. Ha catturato efficacemente sia l'evoluzione graduale (EMEG) che gli stati ricorrenti (SBG). Gli autori attribuiscono questo successo alla flessibilità del modello nel apprendere quando gli atomi contribuiscono, piuttosto che affidarsi a strutture gerarchiche fisse.

C. Applicazione nel Mondo Reale: Decodifica dell'Imagery Motoria

• Configurazione: Classificazione dell'imagery motoria della mano sinistra rispetto alla destra utilizzando dati EEG (15 soggetti). Il compito consisteva nell'apprendere "stati cerebrali" (atomi di grafo) e utilizzare i loro coefficienti come feature per un classificatore Random Forest.
• Baseline: KMeans, Gaussian Mixtures e GLMM.
• Risultati:
  • Prestazioni: GraphDictLog con soli 3 atomi (9 feature) ha ottenuto l'Area Sotto la Curva ROC (AUROC) più elevata, superando KMeans con 16 cluster (48 feature).
  • Interpretabilità: Gli atomi appresi hanno rivelato pattern di connettività funzionale (ad esempio, attività del lobo frontale, connettività occipitale) coerenti con la letteratura neuroscientifica.
  • Efficienza: Il modello ha dimostato che rappresentazioni sparse e spiegabili del dizionario di grafi possono superare i metodi standard utilizzando significativamente meno feature.

5. Significato e Rivendicazioni

Il documento afferma che GraphDict colma il divario tra la rappresentazione sparsa dei dati multivariati e la decomposizione strutturata delle relazioni variabili per campione. La sua importanza primaria risiede in:

• Spiegabilità: A differenza del deep learning "black-box" o del clustering statico, i coefficienti in GraphDict descrivono esplicitamente l'influenza di specifici atomi di grafo sul processo di generazione dei dati.
• Flessibilità: Il framework permette di incorporare prior specifici del dominio (ad esempio, sparsità, ortogonalità) direttamente nell'obiettivo di apprendimento.
• Utilità Downstream: I coefficienti sparsi fungono da feature efficaci e a bassa dimensionalità per i compiti di classificazione, come dimostrato dal compito di decodifica dell'imagery motoria.

Gli autori riconoscono alcune limitazioni, tra cui la complessità computazionale dell'attuale implementazione e la necessità di una sintonizzazione euristica degli iperparametri. Notano che, sebbene l'algoritmo BiPDS funzioni bene empiricamente, una prova formale di convergenza rimane una questione teorica aperta. Il lavoro futuro suggerisce di esplorare regolarizzatori più efficienti ed estensioni a set di nodi non allineati tramite il trasporto ottimale.