Learning Product Graphs from Two-dimensional Stationary Signals

Sintesi Tecnica: Apprendimento di Grafi da Segnali Stazionari Bidimensionali

Enunciato del Problema
I framework tradizionali di apprendimento di grafi inferiscono tipicamente le strutture di rete da segnali scalari osservati ai nodi, trattando multiple realizzazioni (ad esempio, campioni temporali, ripetizioni sperimentali o dati di popolazione) come un'unica dimensione. Questo approccio spesso ignora le dipendenze strutturate esistenti lungo queste dimensioni aggiuntive. In molte applicazioni, come processi spazio-temporali o sistemi di raccomandazione, i dati sono naturalmente rappresentati come segnali bidimensionali indicizzati sia dal nodo (entità) sia da una dimensione di realizzazione (tempo, utenti o esperimenti). Trattare questi come un'unica dimensione vettorizzata porta a problemi di scalabilità a causa della crescita quadratica delle incognite ($P^2Q^2$ per nodi $P \times Q$) e della difficoltà di stimare accuratamente matrici di covarianza ad alta dimensionalità a partire da campioni limitati. Sebbene metodi recenti tentino di modellare queste dipendenze utilizzando grafi prodotto (ad esempio, prodotti di Kronecker o cartesiani), gli approcci esistenti spesso si basano su ottimizzazioni non convesse o richiedono comunque la stima di grandi matrici di covarianza a dimensionalità completa.

Metodologia
Gli autori propongono un framework di Elaborazione di Segnali su Grafi (GSP) che modella i segnali bidimensionali come output di un processo di filtraggio congiunto che agisce su rumore gaussiano bianco. L'ipotesi di base è che il segnale matriciale osservato $Y \in \mathbb{R}^{P \times Q}$ sia generato da:
$$Y = H_P(S_P) W H_Q(S_Q)$$
dove $S_P$ e $S_Q$ sono gli Operatori di Spostamento del Grafo (GSO) per le due dimensioni, $H_P$ e $H_Q$ sono filtri polinomiali su grafo, e $W$ è una matrice di rumore con voci i.i.d.

Sulla base di questo modello, il documento deriva tre formulazioni distinte per il problema di apprendimento del grafo:

1. Modello Vettorizzato Generale: Tratta il segnale $P \times Q$ come un singolo vettore e apprende un GSO non strutturato. Questo è computazionalmente proibitivo a causa della complessità $O((PQ)^2)$.
2. Modello Strutturato a Grafo Prodotto: Assume che il grafo sottostante sia un prodotto (di Kronecker, cartesiano o forte) di due grafi. Ciò riduce le variabili a $P^2 + Q^2$, ma introduce un vincolo non convesso che coinvolge il prodotto di Kronecker, richiedendo tipicamente un'ottimizzazione alternata senza garanzia di recupero.
3. Formulazione della Covarianza per Dimensione (Proposta): Sfruttando il modello specifico di generazione del segnale, gli autori dimostrano che le matrici di covarianza marginali $C_P = E[YY^\top]$ e $C_Q = E[Y^\top Y]$ sono polinomi in $S_P$ e $S_Q$, rispettivamente. Ciò permette di disaccoppiare il problema di apprendimento in due problemi di ottimizzazione convessa separati:
   $$\min_{S_P, S_Q} \|S_P\|_1 + \beta\|S_Q\|_1 \quad \text{s.t.} \quad C_P S_P = S_P C_P, \quad C_Q S_Q = S_Q C_Q$$
   Questa formulazione evita la stima della matrice di covarianza completa $PQ \times PQ$, riducendo significativamente il costo computazionale e la complessità dei campioni, mantenendo al contempo la struttura del grafo prodotto.

Contributi Chiave

• Estensione della Stazionarietà: Il lavoro estende il concetto di stazionarietà su grafo ai segnali bidimensionali, modellandoli come risultato di un filtraggio congiunto lungo dimensioni indipendenti.
• Ottimizzazione Trattabile: Sfruttando la struttura delle covarianze per dimensione, gli autori riformulano il compito di identificazione della topologia in due problemi convessi separabili e a bassa dimensionalità. Questo aggira la non convessità e l'alta dimensionalità associate ai precedenti metodi di apprendimento di grafi prodotto.
• Garanzie Teoriche: La formulazione proposta permette un recupero dimostrabile dei grafi prodotto di Kronecker, cartesiani o forti ottimali sottostanti, sotto il modello di segnale dichiarato.

Risultati Sperimentali
Gli autori valutano il loro metodo (nello specifico la variante "Separate Kronecker-ST" o SepK-ST) rispetto a template spettrali (ST), Kronecker-ST (K-ST), DNNLasso e TERRALasso utilizzando dati sintetici.

• Accuratezza vs. Complessità: SepK-ST raggiunge un'accuratezza di recupero paragonabile a K-ST ma con un tempo di esecuzione significativamente inferiore. A differenza del metodo ST non strutturato, che fallisce nel catturare la struttura sottostante e scala male, SepK-ST sfrutta efficacemente la struttura 2D.
• Efficienza dei Campioni: In regimi con un numero limitato di realizzazioni del segnale ($R$), SepK-ST supera sia ST che K-ST. Poiché opera su matrici di covarianza più piccole $P \times P$ e $Q \times Q$ invece che sulla matrice completa $PQ \times PQ$, richiede meno campioni per ottenere stime affidabili e una migliore stazionarietà (commutatività).
• Robustezza ai Modelli di Segnale: Quando testato contro segnali generati da modelli diversi (Campi Random di Markov vs. filtri polinomiali), SepK-ST recupera costantemente la struttura del grafo. Al contrario, DNNLasso e TERRALasso mostrano un degrado delle prestazioni quando il modello di generazione del segnale si discosta dalle loro ipotesi specifiche.

Significato
Il documento afferma che il suo contributo principale è fornire un framework che bilancia accuratezza di stima ed efficienza computazionale per l'apprendimento di grafi da segnali stazionari bidimensionali. Disaccoppiando il problema di apprendimento in ottimizzazioni convesse specifiche per dimensione, l'approccio offre un'alternativa scalabile ai metodi esistenti che faticano con la maledizione della dimensionalità o vincoli non convessi. I risultati suggeriscono che modellare esplicitamente la struttura del prodotto e il processo di filtraggio attraverso le dimensioni è essenziale per un'inferenza accurata in scenari in cui esistono dipendenze attraverso multiple modalità.