Online Learning for Autoregressive Multilayer Stochastic Block Models under Stationarity and Non-Stationarity

1. Enunciato del Problema

Il lavoro affronta la sfida di analizzare reti multistrato dinamiche, in cui un insieme comune di nodi interagisce attraverso molteplici tipi di relazioni (strati) che evolvono nel tempo. I metodi esistenti soffrono spesso di tre limitazioni:

1. Indipendenza Temporale: Assumono che gli snapshot di rete siano indipendenti, ignorando la dipendenza temporale intrinseca nei sistemi reali (ad esempio, reti commerciali, interazioni sociali).
2. Focus su Singolo Strato: Non riescono a catturare le correlazioni strutturali tra diversi strati.
3. Assunzione di Stazionarietà: Assumono che le dinamiche sottostanti della rete siano stazionarie, fallendo nell'adattarsi a derive graduali o cambiamenti strutturali bruschi (ad esempio, cambiamenti di politica, crisi).

Gli autori mirano a sviluppare un quadro che modelli esplicitamente la dipendenza temporale tramite un meccanismo autoregressivo, gestisca strutture multistrato e fornisca procedure di apprendimento online adattivo per ambienti sia stazionari che non stazionari.

2. Metodologia

A. Il Modello: AR(1)-MSBM

Gli autori propongono il Modello Stocastico a Blocchi Multistrato Autoregressivo del Primo Ordine (AR(1)-MSBM).

• Struttura: Una sequenza di tensori di adiacenza $\{A_t\}_{t \geq 0} \in \{0, 1\}^{n \times n \times L}$, dove $n$ è il numero di nodi, $L$ è il numero di strati e $K$ è il numero di comunità.
• Dinamiche degli Archi: A differenza degli SBM statici, gli archi evolvono tramite un meccanismo di "aggiornamento". Tra il tempo $t-1$ e $t$, un arco $(i, j, l)$ può:
  • Formarsi (0 $\to$ 1) con probabilità $\Theta_{i,j,l}$.
  • Dissolversi (1 $\to$ 0) con probabilità $\Delta_{i,j,l}$.
  • Persistere con probabilità $1 - \Theta_{i,j,l} - \Delta_{i,j,l}$.
• Struttura Latente: Le probabilità di transizione sono tensori a rango basso determinati da una matrice di appartenenza alla comunità condivisa $Z$ e tensori di connettività specifici per strato $W$ (formazione) e $M$ (dissoluzione):
  $$\Theta_{i,j,l} = Z_i W_{:,:,l} Z_j^\top, \quad \Delta_{i,j,l} = Z_i M_{:,:,l} Z_j^\top$$
• Non Stazionarietà: Nel setting non stazionario, $W_t$ e $M_t$ variano nel tempo, permettendo sia punti di cambiamento bruschi che derive graduali, mentre $Z$ rimane fissa (sebbene il quadro possa essere esteso a $Z$ variabile nel tempo).

B. Stima Stazionaria (Algoritmo 1)

Per il caso stazionario, gli autori propongono una Procedura di Stima Online:

1. Statistiche Sufficienti Ricorsive: Mantenere conteggi cumulativi delle transizioni di archi (0$\to$1, 1$\to$0) e degli archi attivi. Questi vengono aggiornati in tempo $O(n^2 L)$ per passo senza riesaminare i dati passati.
2. Stimatori Iniziali: Calcolare stimatori di Massima Verosimiglianza (MLE) in forma chiusa per $\Theta$ e $\Delta$ basati su questi conteggi.
3. Raffinamento Spettrale Tensoriale: Per migliorare l'accuratezza, applicare l'Analisi delle Componenti Principali Eteroschedastica Tensoriale (TH-PCA). Questo sfrutta la struttura di Tucker a rango basso dei tensori. Crucialmente, questo raffinamento viene eseguito solo in punti temporali spaziati geometricamente ($t = 2^m$) per minimizzare il costo computazionale.
4. Recupero delle Comunità: Clusterizzare il sottospazio singolare stimato della matricizzazione di modo-1 per recuperare le appartenenze alle comunità.

C. Stima Non Stazionaria (Algoritmo 2)

Per il caso non stazionario, gli autori introducono un Algoritmo Online a Finestra Adattiva:

1. Finestramento Adattivo: Invece di utilizzare una finestra fissa o l'intera storia, l'algoritmo seleziona dinamicamente una dimensione di finestra di retrospettiva $\hat{k}_t$.
2. Criterio di Stabilità: Ispirato da Huang e Wang (2024), l'algoritmo confronta la perdita empirica della finestra corrente con finestre annidate più piccole. Seleziona la finestra più grande che rimane "stabile" (cioè, la differenza di perdita non supera una soglia di tolleranza $\tau(t)$).
3. Griglia Dinamica: Per garantire l'efficienza computazionale, le dimensioni candidate della finestra sono limitate a una griglia geometrica dinamica, riducendo lo storage da $O(t)$ a $O(\log t)$.
4. Segmentazione Quasi-Stazionaria: L'analisi teorica assume che la serie temporale possa essere partizionata in "segmenti quasi-stazionari" dove la deriva è controllata da una funzione $V(t)$ e soddisfa la "monotonia dominante" (prevenendo la cancellazione di derive positive e negative).

3. Contributi Chiave

1. Nuovo Quadro Modellistico: Introduzione dell'AR(1)-MSBM, che unifica la struttura multistrato con la dipendenza temporale esplicita tramite probabilità di formazione/dissoluzione degli archi.
2. Stima Minimax Ottimale (Stazionaria):
   • Derivazione di limiti di stima non asintotici per i tensori di transizione $\Theta$ e $\Delta$.
   • Dimostrazione dell'ottimalità minimax (stabilendo il primo limite inferiore minimax per modelli di reti multistrato dinamiche).
   • Dimostrazione che sfruttare la struttura multistrato riduce il tasso di errore stocastico da $O(1/\sqrt{t})$ a $O(1/\sqrt{tL})$.
3. Apprendimento Adattivo Non Stazionario:
   • Sviluppo di un algoritmo che si adatta automaticamente a cambiamenti strutturali sconosciuti (bruschi o graduali) senza conoscenza preliminare dei punti di cambiamento.
   • Garanzie teoriche che mostrano come l'errore di stima corrisponda al tasso stazionario quando applicato segmento per segmento, con la dimensione del campione efficace determinata dalla lunghezza locale del segmento.
4. Garanzie di Recupero delle Comunità:
   • Stabilimento di condizioni per il recupero delle comunità sia Hamming-consistente (l'errore frazionario svanisce) che esatto (errore zero).
   • Miglioramento rispetto ai risultati esistenti su singolo strato evitando termini di bias associati alla normalizzazione diagonale nei metodi basati su Laplaciano.

4. Risultati Teorici

• Tassi di Stima:
  • Nel setting stazionario, l'errore di Frobenius per la stima di $\Theta$ e $\Delta$ scala come:
    $$\|\hat{\Theta}_t - \Theta\|_F \lesssim \sqrt{\frac{nK + Lr + K^2r}{t}} + \frac{n\sqrt{L}}{t}$$
    dove il primo termine è l'errore stocastico e il secondo è il bias.
  • Il termine di bias ($O(1/t)$) è un artefatto noto degli MLE autoregressivi ma diventa trascurabile man mano che $t$ cresce rispetto alla dimensione della rete.
• Limite Inferiore Minimax: Il lavoro dimostra che il tasso $O(\sqrt{(rK^2 + n\log K + Lr)/T})$ è ottimale, corrispondendo al limite superiore fino a fattori logaritmici e a un divario computazionale ($K$ vs $\log K$).
• Tassi Non Stazionari: Nel quadro di segmentazione quasi-stazionaria, l'errore dipende dalla lunghezza locale del segmento $t - T_{g-1}$ e dall'involucro di deriva $V(\cdot)$. Se $V(t) = t^{-1/2}$, il tasso corrisponde al tasso stazionario applicato localmente.

5. Risultati Sperimentali

• Simulazioni:
  • Stazionaria: Il metodo proposto ha superato gli stimatori cumulativi statici (che ignorano la dipendenza temporale) e gli stimatori aggregati per strato (che perdono la struttura specifica per strato), in particolare in scenari con segnali deboli o strutture di strato opposte.
  • Non Stazionaria: L'algoritmo adattivo ha rilevato con successo cambiamenti bruschi e tracciato derive graduali. Ha costantemente superato le linee di base basate su storia completa (alto bias dopo i cambiamenti) e finestra fissa (alta varianza o bias a seconda della scelta della finestra).
• Dati Reali (Trasporto Aereo USA):
  • Analisi di dati mensili sui voli (2015–2025) su 4 principali compagnie aeree.
  • L'algoritmo ha rilevato una significativa rottura strutturale a metà del 2020 (pandemia di COVID-19), evidenziata da un picco nei tassi di commutazione delle comunità e da una contrazione della finestra di retrospettiva selezionata.
  • Dopo il 2022, la dimensione della finestra si è espansa, indicando una stabilizzazione della rete, e il modello ha catturato il declino graduale nella connettività di rete (persistenza) e l'aumento del turnover delle rotte.

6. Significato

Questo lavoro colma un divario critico nella scienza delle reti fornendo un quadro teorico e algoritmico rigoroso per reti dinamiche, multistrato e non stazionarie.

• Impatto Pratico: Offre uno strumento per il monitoraggio in tempo reale di sistemi complessi (ad esempio, mercati finanziari, catene di approvvigionamento, reti sociali) in cui le relazioni evolvono e i punti di cambiamento sono sconosciuti.
• Avanzamento Teorico: Stabilisce i primi limiti inferiori minimax per modelli multistrato dinamici e dimostra come i metodi spettrali basati su tensori possano ridurre efficacemente dimensionalità e varianza nei dati di reti temporali ad alta dimensionalità.
• Robustezza: Il meccanismo di finestramento adattivo fornisce una soluzione robusta al compromesso bias-varianza in ambienti non stazionari, eliminando la necessità di un'ottimizzazione manuale delle dimensioni della finestra.