Vertex misalignment and changepoint localization in network time series

1. Il Problema

L'articolo affronta una sfida fondamentale nell'inferenza statistica per le serie temporali di reti (network time series): l'impatto della mancata corrispondenza dei vertici (vertex misalignment) sulla localizzazione dei punti di cambiamento (changepoint localization).

In molti scenari reali (es. reti neurali in sviluppo, reti di trasporto, reti sociali), i vertici delle reti osservate in momenti diversi potrebbero non essere allineati correttamente a causa di errori di tracciamento, rumore o perché l'insieme dei vertici cambia nel tempo. La maggior parte delle metodologie esistenti per il rilevamento dei changepoint presuppone che l'insieme dei vertici sia fisso e che la corrispondenza tra i vertici nei diversi istanti temporali sia nota e corretta. Quando questa corrispondenza è errata o sconosciuta, le tecniche standard possono fallire nel rilevare i cambiamenti strutturali nella dinamica della rete.

Il lavoro si pone la domanda: quanto è robusta la localizzazione dei changepoint rispetto alla perdita di allineamento dei vertici, e dipende questo dalla natura dell'informazione contenuta nella distribuzione dei dati?

2. Metodologia

Gli autori sviluppano un quadro teorico basato sui Processi di Posizione Latente (Latent Position Processes - LPP) e sulle reti a prodotto scalare casuale (Random Dot Product Graphs - RDPG).

• Modelli Teorici: Vengono introdotti due modelli distinti di LPP, denominati London e Atlanta, entrambi caratterizzati da un punto di cambiamento (changepoint) al tempo $t^*$, ma con proprietà statistiche diverse:
  • Modello London: Il cambiamento di distribuzione avviene nelle distribuzioni marginali dei vertici nel tempo. L'informazione sul changepoint è contenuta nella distribuzione individuale di ogni vertice.
  • Modello Atlanta: La distribuzione marginale dei vertici rimane costante nel tempo. Il cambiamento di distribuzione è contenuto esclusivamente nelle distribuzioni congiunte (dipendenze temporali tra i vertici).
• Metriche di Dissimilarità: Vengono analizzate diverse metriche per misurare la distanza tra le reti in istanti temporali diversi:
  • $d_{MV}$ (Maximum Directional Variation): Una metrica che cattura la dipendenza congiunta tra le posizioni latenti, richiedendo la corrispondenza dei vertici.
  • $ind\text{-}d_{MV}$: Una versione "indipendente" che ignora la corrispondenza, trattando le distribuzioni come prodotti di marginali.
  • Wasserstein ($W_p$): Metriche basate sul trasporto ottimo delle distribuzioni marginali.
  • Grado Medio: Una statistica semplice basata sulle proprietà marginali.
• Tecniche di Allineamento: Viene studiato l'uso del Graph Matching (ottimizzazione per allineare le matrici di adiacenza) e del Trasporto Ottimale per tentare di recuperare l'allineamento perso prima di applicare le tecniche di localizzazione.
• Euclidean Mirrors: Viene utilizzata la metodologia degli "specchi euclidei" (Euclidean mirrors), che proiettano le matrici di dissimilarità temporale in uno spazio euclideo a bassa dimensionalità (tramite CMDS - Classical Multidimensional Scaling) per visualizzare e rilevare i cambiamenti strutturali come punti di rottura nella pendenza della traiettoria.

3. Contributi Chiave

1. Teorizzazione dell'Impatto del Misallineamento: Gli autori dimostrano teoricamente come lo shuffling (mescolamento) dei vertici indebolisca la correlazione tra le posizioni latenti nel tempo. Dimostrano che questo effetto è trascurabile se il segnale risiede nelle distribuzioni marginali, ma catastrofico se risiede nelle distribuzioni congiunte.
2. Relazione tra Graph Matching e Trasporto Ottimale: Viene stabilita una connessione teorica tra il problema del graph matching sulle matrici di adiacenza e il calcolo delle distanze di Wasserstein sulle distribuzioni delle posizioni latenti stimate.
3. Analisi di Due Casi Limite:
   • Dimostrano che nel Modello London, la perdita di allineamento non degrada l'inferenza: statistiche semplici come il grado medio o metriche marginali (Wasserstein) sono sufficienti per localizzare il changepoint, indipendentemente dall'allineamento.
   • Dimostrano che nel Modello Atlanta, la perdita di allineamento rende il changepoint irrecuperabile. Le metriche congiunte ($d_{MV}$) falliscono completamente se i vertici sono mescolati, e tentativi di recupero tramite graph matching non riescono a ripristinare il segnale.
4. Analisi Empirica su Dati Simulati e Reali: Vengono presentati esperimenti su dati simulati e su una serie temporale di dati reali derivati da uno sciame di agenti (swarm), confermando le previsioni teoriche.

4. Risultati Principali

• Robustezza del Modello London: Nel modello London, anche con un mescolamento del 100% dei vertici, gli specchi euclidei costruiti su metriche marginali (come il grado medio o $W_1$) mantengono la struttura a tratti lineari con un cambio di pendenza in $t^*$. L'errore quadratico medio (MSE) nella localizzazione rimane basso e inferiore al livello casuale.
• Fragilità del Modello Atlanta: Nel modello Atlanta, appena una frazione significativa di vertici viene mescolata (es. >15%), l'informazione sul changepoint viene persa. Gli specchi euclidei basati su $d_{MV}$ diventano piatti o rumorosi, e il changepoint non è più rilevabile.
• Inefficacia del Graph Matching nel Caso Atlanta: Gli esperimenti mostrano che tentare di correggere l'allineamento tramite graph matching (sia "all-to-one" che "consecutive") non riesce a recuperare l'informazione persa nel modello Atlanta. Il MSE rimane superiore al livello casuale, indicando che l'informazione congiunta è irrecuperabile una volta distrutta la corrispondenza.
• Dati Reali (Swarm): Nell'analisi dei dati dello sciame, l'allineamento corretto permette di rilevare chiaramente i cambiamenti strutturali. Lo shuffling totale distrugge il segnale, mentre il graph matching permette un recupero parziale, suggerendo che i dati reali si collocano in uno spettro intermedio tra i due modelli estremi.

5. Significato e Implicazioni

Il lavoro fornisce un quadro fondamentale per la pratica dell'inferenza su reti dinamiche:

• Diagnosi del Segnale: Prima di applicare tecniche complesse di allineamento, è cruciale determinare se il segnale di interesse risiede nelle distribuzioni marginali o congiunte.
• Scelta della Metrica: Se il segnale è marginale (come nel modello London), l'allineamento dei vertici non è essenziale e metriche robuste come il grado medio o le distanze di Wasserstein sono preferibili. Se il segnale è congiunto (come nel modello Atlanta), l'allineamento è critico e, se perso, l'inferenza può essere impossibile.
• Avvertenza sul Graph Matching: Gli autori avvertono che l'uso del graph matching su dati con allineamento sconosciuto può essere ingannevole: potrebbe restituire risultati che sembrano validi ma che catturano solo informazioni marginali, dando un falso senso di sicurezza sulla capacità di rilevare cambiamenti strutturali complessi.
• Direzioni Future: Il paper suggerisce di esplorare metriche di dissimilarità ibride e di sviluppare metodi per determinare se un segnale è marginale o congiunto nei dati reali, oltre a studiare casi intermedi tra i due modelli estremi presentati.

In sintesi, il paper dimostra che la robustezza della localizzazione dei changepoint nelle serie temporali di reti non è una proprietà universale, ma dipende intrinsecamente dalla struttura statistica del processo generatore dei dati e dalla natura dell'informazione (marginale vs congiunta) su cui il cambiamento si basa.