Simultaneous global and local clustering in multiplex networks with covariate information

Sintesi Tecnica: Clustering Simultaneo Globale e Locale in Reti Multiplex con Informazioni di Covariata

Enunciato del Problema
I moderni dati di rete spesso coinvolgono molteplici tipi di interazioni tra lo stesso insieme di entità, rappresentati come reti multiplex. Una sfida critica nell'analisi di tali dati è la rilevazione simultanea di due distinti tipi di strutture di comunità:

1. Clustering Locale (specifico per livello): Identificare gruppi di nodi che interagiscono densamente all'interno di uno specifico livello (tipo di interazione).
2. Clustering Globale: Identificare un raggruppamento unificato di nodi che persiste attraverso tutti i livelli, riflettendo un ruolo strutturale sovraordinato.

La letteratura esistente ha affrontato ampiamente o il clustering di livello o il clustering globale in isolamento, oppure ha assunto un numero noto e finito di comunità. Inoltre, pochi metodi integrano le informazioni sulle covariate nodali (metadati) per guidare il processo di clustering, operando contemporaneamente su un numero di comunità potenzialmente infinito e sconosciuto. Questo articolo affronta il vuoto metodologico relativo a modelli capaci di eseguire il clustering gerarchico (globale e locale) in reti multiplex, incorporando al contempo le covariate e gestendo un numero di gruppi sconosciuto.

Metodologia: Il Modello a Blocchi Stocastici Gerarchico per Reti Multiplex (HMPSBM)
Gli autori propongono l'HMPSBM (Hierarchical Multiplex Stochastic Blockmodel), un modello bayesiano non parametrico progettato per inferire simultaneamente le appartenenze globali dei nodi e le appartenenze specifiche per livello.

• Struttura del Modello:

  • Assegnazione Globale: Ogni nodo $i$ è assegnato a un gruppo globale $w_i$. La probabilità di questa assegnazione, $\tau_i$, è costruita utilizzando un processo di stick-breaking probit guidato dalle covariate nodali $x_i$. Ciò consente al modello di apprendere come le caratteristiche influenzino l'appartenenza al gruppo globale.
  • Assegnazione Locale: Condizionatamente al gruppo globale $w_i$, ogni nodo è assegnato a un gruppo specifico per livello $z_{\ell i}$ per ogni livello $\ell$. Queste assegnazioni sono governate da proporzioni di miscelazione specifiche per i nodi derivate da distribuzioni condivise di tipo Griffiths-Engen-McCloskey (GEM).
  • Connettività: All'interno di ogni livello, le connessioni seguono un Modello a Blocchi Stocastici (SBM). La probabilità di una connessione tra i nodi $i$ e $j$ nel livello $\ell$ dipende dalle loro appartenenze ai gruppi specifici del livello.
  • Prior Non Parametrici: Il modello impiega un framework non parametrico (specificamente utilizzando distribuzioni GEM e rappresentazioni di stick-breaking) per consentire che il numero di comunità globali e di livello sia sconosciuto e inferito dai dati, anziché fissato a priori.

• Procedura di Inferenza:

  • Data la complessità della distribuzione a posteriori, gli autori propongono una procedura di inferenza Bayesiana Variazionale (VB) utilizzando la Coordinate Ascent Variational Inference (CAVIA).
  • L'approccio utilizza un'approssimazione mean-field in cui la distribuzione a posteriori è fattorizzata sui parametri del modello.
  • Per gestire la natura infinito-dimensionale del problema, gli autori introducono parametri di troncamento ($M_w$ per i gruppi globali e $M_z$ per i gruppi di livello).
  • L'algoritmo include aggiornamenti specifici per le variabili di stick-breaking e utilizza l'ascesa del gradiente (algoritmo Adam) per i parametri che non possiedono distribuzioni condizionali in forma chiusa (specificamente i coefficienti di regressione che collegano le covariate alle probabilità dei gruppi globali).
  • Inizializzazione: Il metodo impiega uno schema di inizializzazione informato tramite embedding spettrale (SVD) e HDBSCAN per seminare i gruppi a livello di livello, seguito da un passaggio di re-enumerazione per garantire la coerenza tra i livelli.

Contributi Chiave

1. Clustering Gerarchico Simultaneo: Il documento introduce la prima metodologia per inferire simultaneamente un clustering globale dei nodi e i clustering specifici per livello all'interno di una rete multiplex, permettendo pattern di clustering eterogenei tra i livelli.
2. Integrazione delle Covariate: Il modello incorpora le informazioni sulle covariate nodali direttamente nel meccanismo di clustering globale tramite un processo di stick-breaking probit, guidando la formazione dei gruppi globali basata sulle caratteristiche dei nodi.
3. Flessibilità Non Parametrica: A differenza di molti SBM multiplex esistenti che richiedono un numero pre-specificato di comunità, l'HMPSBM consente un numero sconosciuto (effettivamente infinito) di gruppi globali e di livello, selezionando automaticamente la complessità appropriata.
4. Inferenza Scalabile: Gli autori sviluppano un algoritmo di inferenza variazionale scalabile con aggiornamenti parallelizzabili, rendendo l'approccio applicabile a reti di grandi dimensioni dove i metodi Markov Chain Monte Carlo (MCMC) potrebbero essere computazionalmente proibitivi.

Risultati
Le prestazioni dell'HMPSBM sono state valutate attraverso estesi studi di simulazione e un'applicazione nel mondo reale:

• Studi di Simulazione:

  • Recupero del Numero di Gruppi: Il modello ha recuperato con successo il numero reale di gruppi globali e di livello quando i parametri di troncamento erano sufficientemente grandi.
  • Covariata vs Struttura di Rete: In contesti in cui le covariate nodali diventavano non informative (diminuendo la separazione), il modello recuperava comunque accuratamente i gruppi globali, dimostrando che la struttura della rete è il driver primario del clustering, con le covariate che fungono da segnale ausiliario.
  • Robustezza all'Inizializzazione: Sebbene un'inizializzazione informata abbia prodotto una convergenza leggermente migliore, il modello ha dimostrato robustezza, convergendo verso soluzioni simili anche con inizializzazione casuale nella maggior parte dei casi.
  • Scalabilità: Le prestazioni (misurate tramite l'Informazione Mutua Normalizzata, NMI) sono migliorate con l'aumentare del numero di livelli e della dimensione della rete, particolarmente in contesti con debole separazione di connettività.

• Applicazione nel Mondo Reale (Rete Commerciale FAO):

  • Il modello è stato applicato a una rete multiplex di commercio alimentare globale (214 paesi, 314 tipi di alimenti), ridotta a 177 nodi e 20 livelli.
  • Utilizzando le covariate come PIL e superficie terrestre, il modello ha identificato 11 gruppi globali e 6 gruppi a livello di livello.
  • Interpretabilità: I gruppi globali inferiti si allineavano con l'intuizione economica. Ad esempio, un gruppo comprendeva le grandi potenze commerciali globali (USA, Cina, Regno Unito, Germania, ecc.), mentre un altro raggruppava economie emergenti e potenze regionali. È stato identificato un cluster distinto di Siria e Iran, riflettendo le loro specifiche relazioni commerciali prima della rivoluzione siriana del 2011.
  • Impatto delle Covariate: L'aggiunta di ulteriori covariate (superficie urbana, lunghezza della costa) ha raffinato la periferia dei cluster (ad esempio, spostando gli stati costieri/insulari) ma ha lasciato invariata la struttura centrale delle principali economie, confermando il dato secondo cui la struttura della rete è il fattore dominante.

Significatività e Rivendicazioni
Il documento afferma che l'HMPSBM colma una lacuna metodologica critica fornendo un framework unificato per il clustering gerarchico in reti multiplex che accoglie sia dimensioni di comunità sconosciute che covariate nodali. Gli autori sostengono che il loro approccio di inferenza variazionale offre un'alternativa computazionalmente efficiente all'MCMC per reti su larga scala.

La significatività del lavoro risiede nella sua capacità di svelare strutture latenti che non sono evidenti analizzando i livelli isolatamente o ignorando i metadati. L'applicazione alla rete commerciale FAO dimostra che il modello può rivelare raggruppamenti economicamente significativi che riflettono sia i pattern commerciali sia le caratteristiche geopolitiche ed economiche. Gli autori notano con modestia che, sebbene il modello assuma che i nodi siano presenti in tutti i livelli e che le covariate siano completamente osservate, l'attuale framework riesce a bilanciare con successo le informazioni strutturali e quelle basate sulle caratteristiche per produrre risultati di clustering interpretabili e accurati.