Sample entropy for graph signals: An approach to nonlinear analysis of graph signals

Titolo: Entropia Campionaria per Segnali su Grafo: Un Approccio all'Analisi Non Lineare di Segnali su Grafo

1. Il Problema

L'elaborazione dei segnali su grafo (Graph Signal Processing - GSP) ha visto l'adozione di metodi basati sull'entropia, come l'Entropia di Permutazione, l'Entropia di Dispersione e l'Entropia a Bolle. Tuttavia, questi metodi presentano una limitazione fondamentale: operano attraverso la discretizzazione dei segnali in dinamiche simboliche per calcolare l'entropia di Shannon. Di conseguenza, perdono informazioni preziose contenute nello spazio degli stati continui.
L'obiettivo di questo lavoro è colmare questa lacuna generalizzando l'Entropia Campionaria (Sample Entropy - SampEn), un metodo classico per misurare l'irregolarità e la complessità delle serie temporali in uno spazio continuo, applicandolo ai segnali definiti su grafi. L'obiettivo è creare un framework di entropia condizionata continua che non richieda la discretizzazione simbolica.

2. Metodologia: SampEnG

Gli autori propongono SampEnG, una generalizzazione dell'Entropia Campionaria per segnali su grafo. La metodologia sostituisce il concetto di "ritardo temporale" (temporal delay embedding) utilizzato nelle serie temporali 1D con un embedding basato su grafi multi-hop.

• Costruzione dei Pattern:

  • Per ogni nodo $i$ del grafo $G$, viene costruito un vettore (pattern) che cattura il profilo radiale del segnale attorno al nodo.
  • Invece di concatenare osservazioni temporali successive, i componenti del vettore sono aggregati locali calcolati su hop successivi ($L = 0, 1, 2, \dots, m$).
  • L'aggregazione avviene tramite le potenze dell'operatore di spostamento del grafo (matrice di adiacenza $A$ o matrice pesata $W$).
  • Il valore $x^L_i$ rappresenta la media pesata per cammino (walk-weighted mean) dei nodi raggiungibili esattamente in $L$ hop dal nodo $i$:
    $$x^L_i = \frac{1}{\text{deg}_L(i)} \sum_{j \in N_L(i)} (A^L)_{ij} x_j$$
    dove $\text{deg}_L(i)$ è il grado di $L$-hop (somma della riga $i$ di $A^L$).

• Calcolo dell'Entropia:

  • Si definiscono pattern di dimensione $m$ ($x^m(i)$) e $m+1$ ($x^{m+1}(i)$).
  • Si calcola la probabilità condizionata che due pattern di lunghezza $m$ siano simili (distanza di Chebyshev $\le \epsilon$) e che rimangano simili quando estesi a lunghezza $m+1$.
  • La distanza $\epsilon$ è definita come $r \times \text{SD}$ (deviazione standard del segnale), dove $r$ è un parametro di tolleranza.
  • L'entropia finale è data da:
    $$\text{SampEn}(m, r, N) = -\ln \left( \frac{A_m(r)}{B_m(r)} \right)$$
    dove $A_m$ e $B_m$ sono i conteggi normalizzati delle corrispondenze per pattern di lunghezza $m+1$ e $m$ rispettivamente.

3. Contributi Chiave

1. Generalizzazione Continua: Introduzione di un metodo di entropia condizionata che opera direttamente nello spazio degli stati continui dei segnali su grafo, evitando la perdita di informazione dovuta alla discretizzazione simbolica.
2. Embedding Multi-hop: Sostituzione del ritardo temporale con un'aggregazione spaziale basata sulla struttura del grafo (potenze della matrice di adiacenza), permettendo di catturare la dipendenza strutturale tra nodi.
3. Validazione Teorica e Pratica: Dimostrazione che SampEnG si riduce alla SampEn classica 1D su grafi a percorso diretto (directed path graphs) e validazione della sua sensibilità ai sistemi dinamici non lineari.
4. Efficienza Computazionale: Il metodo è stato testato su grafi con migliaia di nodi, dimostrando tempi di esecuzione pratici (nell'ordine di secondi per grafi con 2700 nodi).

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su due scenari principali:

• Mappa Logistica (Logistic Map):

  • Il segnale è stato generato su grafi a percorso diretto e non diretto.
  • Risultato: Su grafi a percorso diretto, SampEnG replica perfettamente l'andamento della SampEn classica 1D al variare del parametro di biforcazione $\rho$, identificando correttamente le transizioni ordine-caos.
  • Su grafi non diretti, il metodo segue la tendenza generale ma mostra lievi differenze quantitative dovute alla struttura simmetrica e non causale del vicinato.

• Grafo di Erdős–Rényi (ER) Diretto:

  • Sono stati analizzati grafi casuali con $N=2700$ nodi e diversi livelli di connettività (grado medio in uscita $K$).
  • Relazione Connettività-Entropia:
    • Per reti sparse (bassa probabilità di connessione $p$, basso $K$), l'entropia diminuisce all'aumentare della connettività, riflettendo una maggiore regolarità topologica.
    • Man mano che il grafo diventa più denso, SampEnG tende a zero. Questo è dovuto all'omogeneizzazione dei pattern locali causata dalla sovrapposizione crescente dei vicinati (specialmente per valori alti di $m$), che riduce la variabilità effettiva che l'entropia può misurare.
  • Prestazioni: Su un processore Apple M3, l'elaborazione di un grafo con 2700 nodi richiede circa 295 ms per $m=1$ e fino a 1400 ms per $m=3$, rendendo il metodo applicabile a dataset di grandi dimensioni.

5. Significato e Implicazioni

Il lavoro di Lei et al. apre nuove prospettive per l'analisi dei dati di rete:

• Estensione dell'Analisi Non Lineare: Permette di applicare concetti di entropia condizionata e complessità a una vasta gamma di dati di rete (sensori distribuiti, reti sociali, biologiche) senza dover forzare i dati in modelli simbolici.
• Sensibilità Strutturale: SampEnG non misura solo la complessità del segnale, ma anche come questa complessità interagisce con la topologia del grafo sottostante.
• Fondamento per Futuri Sviluppi: Il metodo fornisce una base solida per futuri studi sulla robustezza al rumore, l'uso di embedding alternativi e l'applicazione in domini reali di sensing di rete.

In sintesi, SampEnG rappresenta un passo significativo verso l'unificazione dell'analisi di complessità temporale e strutturale, offrendo uno strumento potente per quantificare l'irregolarità in sistemi complessi interconnessi.