Ordering Stochastic Block Models via prior transitivity

Sintesi Tecnica: Ordinamento di Modelli Stochastici a Blocchi tramite Trascitività Prior

Definizione del Problema
Le reti dirette spesso esibiscono due caratteristiche strutturali simultanee: la struttura a comunità (nodi che formano gruppi con schemi di interazione simili) e la struttura gerarchica (i gruppi interagiscono in modo ordinato, dove i collegamenti fluiscono prevalentemente dai gruppi di rango superiore a quelli di rango inferiore). Le metodologie esistenti affrontano tipicamente queste caratteristiche isolatamente. I modelli SBM (Stochastic Block Models) standard recuperano i gruppi ma non impongono un ordine coerente tra i blocchi, mentre i modelli di ranking ordinano i singoli nodi ma non riescono a identificare gruppi strutturalmente equivalenti. Questa separazione rischia di imporre ordinamenti rigorosi a livello di nodo laddove esistono solo gerarchie a livello di gruppo, o di non rilevare schemi gerarchici all'interno di dati clusterizzati. Il documento affronta la necessità di un quadro unificato che inferisca congiuntamente blocchi ordinati e valuti se una struttura di blocchi trasitiva sia supportata dai dati.

Metodologia: Il Modello Stochastic Block Transitivo (TSBM)
Gli autori introducono il Modello Stochastic Block Transitivo (TSBM), un modello bayesiano per reti dirette pesate. La metodologia si basa su cinque pilastri chiave:

1. Decomposizione Volume/Direzione: Il modello decompone i conteggi degli archi diretti in due componenti:

   • Volume: Il volume totale di interazione non diretta tra i nodi, modellato tramite una matrice di intensità simmetrica e propensioni di grado specifiche per ogni nodo (seguendo il framework del Degree-Corrected SBM).
   • Direzione: La probabilità della direzione dell'interazione condizionata al verificarsi di un'interazione. Questa separazione permette al modello di imporre la gerarchia sul disequilibrio direzionale piuttosto che sulla frequenza di interazione.

2. Prior che inducono la Trascitività: Il modello impone un ordine sui blocchi attraverso dei prior sulle log-odds direzionali ($\psi$). Sono proposte due specifiche:

   • Debole Trascitività Stocastica (WST): Un prior flessibile che esclude schemi di dominanza ciclica (ad esempio, $A \succ B \succ C \succ A$) assicurando che se il blocco $k$ domina $\ell$ e $\ell$ domina $m$, allora $k$ domina $m$. Ciò è ottenuto tramite prior gaussiani troncati indipendenti sulle log-odds della parte superiore della matrice.
   • Forte Trascitività Stocastica (SST): Un prior più restrittivo, specificamente una versione Toeplitz SST. Essa assume che il vantaggio direzionale aumenti con la separazione di rango (ovvero, il vantaggio di un blocco ad alto rango su uno a basso rango è maggiore del suo vantaggio su un blocco di rango intermedio). Ciò è modellato assumendo che le log-odds dipendano solo dalla distanza tra i blocchi, con incrementi monotoni imposti tramite una somma cumulativa di incrementi positivi.

3. Prior di Partizione Ordinata: Poiché le etichette dei blocchi ordinati non sono scambiabili (permutare le etichette cambia la gerarchia e quindi la verosimiglianza), i comuni prior di partizione scambiabile non sono adatti. Gli autori utilizzano un prior di partizione ordinato per età (Donnelly e Tavaré, 1986; Donnelly e Joyce, 1991). Questo prior, originariamente derivato dalla genetica delle popolazioni, tratta i blocchi come se apparissero sequenzialmente nel tempo (o per età), permettendo l'inferenza congiunta del numero di blocchi e dell'allocazione dei nodi senza richiedere un MCMC reversible-jump.

4. Inferenza a Posteriori: L'inferenza è eseguita tramite un campionatore di Gibbs parzialmente collassato. Per gestire la non-coniugazione tra la verosimiglianza logistica delle probabilità direzionali e i prior gaussiani, gli autori utilizzano l'aumento dei dati Pólya-Gamma. Ciò consente aggiornamenti condizionali trattabili per i parametri direzionali, i parametri di volume e le allocazioni dei nodi.

5. Selezione del Modello: Il framework utilizza la Cross-Validazione Leave-One-Out (LOO-CV) tramite campionamento di importanza con smoothing di Pareto per confrontare le varianti del TSBM rispetto al DC-SBM (Degree-Corrected SBM) standard.

Contributi Chiave

• Nuova Formulazione del Modello: Il TSBM è il primo modello bayesiano che inferisce congiuntamente l'equivalenza stocastica e l'ordinamento stocastico in reti dirette utilizzando vincoli di trascitività sulle probabilità a livello di blocco.
• Trattabilità Computazionale: Combinando l'aumento dei dati Pólya-Gamma con i prior di partizione ordinati per età, gli autori derivano un campionatore di Gibbs completo che evita metodi trans-dimensionali computazionalmente costosi (come il reversible-jump) per stimare il numero di blocchi ordinati.
• Trascitività Flessibile: L'introduzione di sia WST che Toeplitz SST permette al modello di adattarsi a diversi livelli di rigore gerarchico, dalla semplice aciclicità alla dominanza dipendente dal rango.
• Capacità Diagnostica: Il framework identifica esplicitamente gli scenari in cui imporre un ordine è deleterio (ad esempio, reti di citazioni non transitive), fornendo un meccanismo probabilistico per valutare la validità dell'assunzione di trascitività.

Risultati

• Studi di Simulazione: In reti sparse con segnali direzionali deboli, il TSBM (sia la variante WST che quella SST) supera significativamente il DC-SBM standard sia in termini di accuratezza predittiva (LOOIC) che di recupero della partizione (Variazione di Informazione). In reti dense con segnali forti, tutti i modelli si comportano in modo simile. Fondamentalmente, in scenari errati (misspecified) in cui i dati contengono cicli (non trasitivi), il DC-SBM supera il TSBM, dimostrando la capacità del modello di rilevare quando l'assunzione di trascitività è inappropriata.
• Applicazioni Empiriche: Il modello è stato applicato a sei reti pesate dirette (dominanza animale, citazioni di riviste, amicizie scolastiche):
  • Dominanza Animale: Nelle reti di bighorn sheep, mountain goats e spotted hyenas, il TSBM generalmente ha migliorato le prestazioni predittive e ha prodotto partizioni con strutture gerarchiche più chiare e coerenti (meno archi retrogradi) rispetto al DC-SBM.
  • Citazioni: Nella rete di citazioni della rivista di statistica, il DC-SBM ha performato meglio. Gli autori notano che, sebbene esistano gradienti di prestigio, i pattern di citazione non sono strettamente transitivi; pertanto, il prior ordinato ha vincolato il modello inutilmente.
  • Macaques: Nella rete di dominanza dei macachi, la gerarchia era già quasi perfetta (quasi un ordinamento quasi rigoroso a livello di nodo). In questo caso, il DC-SBM ha superato leggermente il TSBM, poiché la regolarizzazione del prior offriva poco beneficio rispetto al segnale già forte presente nei dati.
  • Amicizie: Nella rete di amicizie di una scuola superiore, il TSBM ha recuperato un ordinamento a livello di blocco coerente con una gerarchia globale, mentre il DC-SBM ha prodotto una partizione che rifletteva la struttura di comunità piuttosto che la gerarchia.

Significatività e Rivendicazioni
Il documento sostiene che il TSBM fornisce un quadro probabilistico per stimare gruppi ordinati e, cosa importante, per valutare quando una struttura di blocchi trasitiva è supportata dai dati. Gli autori sottolineano che il valore del modello non risiede solo nell'imporre l'ordine, ma nel modellare congiuntamente raggruppamento e gerarchia, il che può migliorare l'inferenza e la predizione specificamente quando il segnale direzionale è debole o la rete è sparsa. Il lavoro contribuisce inoltre alla statistica bayesiana non parametrica dimostrando l'utilità dei prior di partizione ordinati per età in modelli a blocchi latenti con etichette non scambiabili, una combinazione precedentemente non utilizzata in questo contesto. Gli autori notano con modestia che le prestazioni del modello sono contingenti ai dati; in casi in cui la struttura sottostante è non trasitiva o la gerarchia è già estremamente netta, il DC-SBM non vincolato può rimanere preferibile.