Sintesi Tecnica: Segnali con Distribuzione su Grafi in Spazi di Wasserstein

1. Definizione del Problema

L'elaborazione classica dei segnali su grafi (GSP) rappresenta i segnali come vettori indicizzati dai vertici di un grafo, facendo affidamento su operatori lineari come la Trasformata di Fourier su Grafi (GFT) e i filtri grafici. Sebbene efficaci, questi approcci basati su vettori affrontano tre criticità fondamentali nelle applicazioni reali:

1. Assunzione di Osservazioni Complete: La GSP classica richiede dati sincroni e completi su tutti i nodi per applicare operatori come la GFT. Nella pratica, la raccolta dati è spesso asincrona o incompleta (ad esempio, report mancanti dai sensori), rendendo inapplicabili i metodi standard basati su vettori o richiedendo un'imputazione distorta.
2. Requisito di Corrispondenza Rigida del Segnale: I metodi statistici GSP tipicamente apprendono i filtri da campioni di coppie input-output vettoriali $\{(x_i, y_i)\}$. Ciò impone una rigida corrispondenza temporale uno-a-uno. I dati del mondo reale soffrono spesso di sfasamenti temporali, sovrapposizioni o rimescolamenti (shuffling), che interrompono tale allineamento.
3. Assunzione di Topologia Deterministica: La GSP classica assume una topologia di grafo fissa e nota (ad esempio, una specifica matrice di adiacenza). Tuttavia, in molti sistemi, la struttura del grafo è incerta, parzialmente osservata o intrinsecamente dipendente dalla realizzazione stessa del segnale.

Gli approcci GSP statistici esistenti trattano spesso la casualità tramite variabili aleatorie, ma operano ancora su campioni vettoriali, fallendo nel risolvere pienamente queste incertezze strutturali e osservative.

2. Metodologia

Gli autori propongono un quadro unificato in cui i segnali su grafi non sono modellati come vettori, ma come Segnali con Distribuzione su Grafi (GDS) — misure di probabilità che risiedono in uno spazio di Wasserstein ($\mathcal{P}_p(\mathbb{R}^N)$).

Concetti Chiave

• Segnale con Distribuzione su Grafi (GDS): Un segnale è definito come una misura di probabilità di Borel $\mu \in \mathcal{P}_p(\mathbb{R}^N)$. I segnali vettoriali tradizionali $x$ vengono recuperati come casi speciali dove $\mu = \delta_x$ (misura di Dirac).
• Strutture di Grafo Adattive al Segnale (SAGS): Il framework generalizza le topologie di grafo fisse modellando il grafo $G$ come una variabile casuale condizionata al segnale $x$. Formalmente, per un segnale $x$, la struttura del grafo segue una distribuzione condizionale $\nu_x$. Ciò cattura pattern di connettività dipendenti dal segnale.
• Distanza di Wasserstein: Il framework utilizza la distanza $p$-Wasserstein ($W_p$) per misurare le discrepanze tra le distribuzioni dei segnali, fornendo una metrica che tiene conto sia degli spostamenti della media che delle variazioni di covarianza/struttura.

Operazioni Generalizzate

Il documento stabilisce un dizionario sistematico che mappa i concetti classici della GSP ai loro analoghi GDS tramite misure di pushforward:

• Trasformata di Fourier GDS (GDS-FT): Definita come la pushforward della distribuzione del segnale $\mu$ attraverso la matrice della base di Fourier del grafo $U_G^\top$. Per una distribuzione congiunta di segnale e grafo, la trasformata tiene conto dell'incertezza nella topologia del grafo.
• Filtro Convolutivo GDS: Un filtro $F_G$ (tipicamente un polinomio dell'Operatore di Spostamento del Grafo) agisce sulla distribuzione $\mu$ tramite la mappa di pushforward $(F_G)_*\mu$. Questa operazione trasforma la distribuzione nel dominio dei vertici, la rimodella nel dominio spettrale e la trasforma nuovamente.
• Trasformate Generalizzate: Il framework definisce trasformate generalizzate per gli scenari SAGS, dove la distribuzione di output è derivata dalla distribuzione congiunta del segnale e del grafo dipendente dal segnale.

Garanzie Teoriche

Gli autori stabiliscono le proprietà analitiche per queste trasformate generalizzate:

• Continuità: Le trasformate sono mostrate essere uniformemente continue su domini di segnale compatti e puntualmente continue sotto condizioni Lipschitz sulla distribuzione della trasformata indotta.
• Stabilità: Questi risultati di continuità garantiscono che piccole perturbazioni nella distribuzione di input (dovute a rumore, shift di distribuzione o approssimazioni a campioni finiti) portino a perturbazioni controllate nell'output, garantendo robustezza per l'apprendimento e l'inferenza.

Algoritmi di Applicazione

Sono stati sviluppati due algoritmi specifici per dimostrare il framework:

1. Apprendimento di Filtri su Grafi: L'obiettivo è apprendere un filtro $F_G$ che trasporti una distribuzione di input $\mu_\theta$ verso una distribuzione target $\mu^\star$. Gli autori propongono due approcci parametrici:
   • Basato su Copula: Modella la distribuzione congiunta accoppiando le marginali tramite una copula Gaussiana, permettendo una modellazione flessibile delle dipendenze anche con dati mancanti.
   • Basato su GMM: Rappresenta la distribuzione congiunta come un Modello di Miscela Gaussiana (GMM), utilizzando la distanza Mixture-Wasserstein ($MW_2$) per un'ottimizzazione trattabile.
2. Rilevamento di Anomalie: Inveve di applicare soglie a statistiche scalari (come il coefficiente massimo ad alta frequenza), il metodo caratterizza la distribuzione empirica delle caratteristiche spettrali ad alta frequenza. Le anomalie vengono rilevate misurando la discrepanza (ad esempio, tramite $MW_2$ o distanza della posizione del picco) tra la distribuzione di un batch di test e una distribuzione di riferimento stimata dai dati normali.

3. Contributi Principali

1. Framework Unificato: Sviluppo di un framework GSP in cui i segnali sono misure di probabilità in spazi di Wasserstein e le topologie di grafo sono distribuzioni adattive al segnale, generalizzando strettamente la GSP classica basata su vettori.
2. Corrispondenza Sistematica: Formalizzazione di un dizionario che mappa le operazioni core della GSP (trasformata di Fourier, filtraggio, convoluzione) ai loro corrispondenti a livello di distribuzione, mostrando le formulazioni classiche come casi speciali.
3. Teoria della Stabilità: Stabilimento di risultati di continuità per le trasformate GDS generalizzate, fornendo garanzie teoriche di stabilità per le perturbazioni di input e le approssimazioni di distribuzione.
4. Validazione Empirica: Dimostrazione dell'utilità del framework nell'apprendimento di filtri su grafi e nel rilevamento di anomalie, mostrando prestazioni superiori rispetto ai metodi vettoriali allo stato dell'arte in presenza di osservazioni incomplete e disallineate.

4. Risultati Sperimentali

Gli autori validano il framework utilizzando due dataset:

• Dati COVID-19 (Apprendimento di Filtri): Utilizzando i conteggi giornalieri dei casi in 58 contee, i metodi GDS proposti (GDS-Cop e GDS-GMM) sono stati confrontati con i metodi di filtraggio su grafi Least-Squares (LS), Regularized LS e Covariance-Matching.
  • Robustezza ai Dati Mancanti: Sotto un tasso di mancanza del 20% per nodo, i metodi classici (GSP-LS, GSP-RLS) sono degradati significativamente. I metodi GDS sono rimasti robusti perché modellano distribuzioni piuttosto che richiedere vettori completi.
  • Robustezza al Rimescolamento (Shuffling): Quando i dati di addestramento sono stati rimescolati temporalmente, i metodi classici che dipendono dal rigoroso allineamento temporale sono falliti. I metodi GDS sono rimasti stabili poiché apprendono dalle proprietà distributive piuttosto che da specifici accoppiamenti di campioni.
  • Dimensione della Finestra: I metodi GDS hanno superato i baseline per finestre temporali più ampie dove esistono campioni sufficienti per la stima della distribuzione. Tuttavia, per finestre molto piccole (2-4 giorni), i metodi GDS sono stati meno performanti a causa della difficoltà di stimare accuratamente le distribuzioni da pochi campioni.
• Dati ECoG Cerebrali (Rilevamento di Anomalie): Utilizzando dati pre-ictali (normali) e ictal (anomali) relativi a crisi epilettiche, i rilevatori di anomalie basati su GDS (usando distanze di Peak location e Mixture Wasserstein) sono stati confrontati con i baseline GFT-based, Total Variation (TV) e Variational Autoencoder (ELBO).
  • Prestazioni: I metodi GDS hanno raggiunto la massima accuratezza attraverso tutte le dimensioni dei batch di test.
  • Efficienza dei Campioni: I metodi GDS hanno mantenuto un'alta accuratezza anche con piccoli batch, mentre i baseline puntuali (GSP-GFT) si sono stabilizzati a una bassa accuratezza, e altri (GSP-TV, ELBO) hanno richiesto molti più campioni per avvicinarsi alle prestazioni dei GDS.

5. Significato e Rivendicazioni

Il documento afferma che il framework GDS offre un approccio rigoroso per gestire l'incertezza e la stocasticità sia nei segnali che nelle topologie di grafo. Passando dagli spazi vettoriali agli spazi di Wasserstein, il framework:

• Rilassa i Requisiti dei Dati: Elimina la necessità di osservazioni complete e sincrone e di un rigoroso allineamento temporale, rendendolo adatto a scenari del mondo reale con dati mancanti o irregolari.
• Cattura Strutture più Ricche: Codifica l'incertezza nella topologia del grafo e nelle correlazioni del segnale direttamente nella rappresentazione del segnale, invece di trattarle come rumore o richiedere assunzioni fisse.
• Generalizza la Teoria Esistente: Include strettamente la GSP classica come un caso speciale (misure di Dirac), garantendo la compatibilità retroattiva pur estendendone le capacità.

Gli autori notano che questa flessibilità comporta un compromesso: il framework richiede dati sufficienti per stimare accuratamente le distribuzioni sottostanti. In regimi con pochi campioni, i metodi classici basati su vettori potrebbero rimanere preferibili. Tuttavia, per applicazioni che comportano una sostanziale mancanza di dati, variabilità di campionamento o strutture dipendenti dal segnale, il framework GDS fornisce un'alternativa più flessibile e robusta.