Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models

Sintesi Tecnica: Colmare il Divario tra Massima Verosimiglianza e Trasporto Ottimo per un'Inferenza Efficiente e la Selezione del Modello nei Modelli a Blocchi Stocastici

Enunciato del Problema
Il lavoro affronta la sfida dell'inferenza e della selezione del modello nei Modelli a Blocchi Stocastici (SBM), un framework generativo per grafi casuali in cui i nodi sono partizionati in cluster nascosti e le probabilità degli archi dipendono dall'appartenenza al cluster. Sebbene gli SBM offrano vantaggi rispetto ad altri metodi di clustering (come la massimizzazione della modularità o il clustering spettrale) recuperando strutture diverse e fornendo strumenti per stimare il numero di cluster, l'inferenza standard si basa spesso sulla Massimizzazione della Verosimiglianza Variazionale (VEM). Una limitazione critica della VEM è la sua dipendenza dalla regolarizzazione entropica per garantire la regolarità dell'ottimizzazione. Tale regolarizzazione impedisce ai piani di trasporto di diventare sparsi, ostacolando così la "selezione intrinseca del modello" — la capacità di disattivare automaticamente i cluster non necessari (assegnando loro massa zero) all'interno di un singolo problema di ottimizzazione. Di conseguenza, gli approcci attuali richiedono spesso ricerche su griglia computazionalmente costose o procedure euristiche per determinare il numero ottimale di cluster ($K$).

Metodologia
Gli autori propongono un nuovo framework che interpreta l'Inferenza Variazionale di Massima Verosimiglianza (MLVI) negli SBM attraverso la lente del Trasporto Ottimo (OT), utilizzando specificamente la divergenza Semi-Rilassata di Gromov-Wasserstein (srGW).

1. Riformulazione come srGW: Il lavoro stabilisce che la massimizzazione del limite inferiore della prova (ELBO) negli SBM è equivalente alla minimizzazione di una divergenza srGW con un termine di regolarizzazione entropica. La funzione di perdita corrisponde al log-verosimiglianza negativo del modello generativo.
2. Stimatori Non Regolarizzati: Riconoscendo che la regolarizzazione entropica impedisce la sparsità, gli autori investigano stimatori srGW non regolarizzati. Definiscono stimatori per la matrice di connettività ($\Theta$) e per il piano di trasporto ($T$, che rappresenta le assegnazioni ai cluster) minimizzando la perdita srGW senza il termine entropico.
3. Regolarizzazione Promotrice di Sparsità per la Selezione del Modello: Per abilitare la selezione automatica del modello (stima di $K$) senza ricerca su griglia, gli autori introducono una penalità con pseudo-norma $\ell_{1/2}$ sul piano di trasporto. Tale penalità incoraggia le proporzioni stimate dei cluster a essere sparse, impostando efficacemente la massa dei cluster non ottimali a zero.
4. Ottimizzazione: I parametri sono stimati utilizzando un algoritmo di Discesa a Coordinate a Blocchi. Questo alterna:
   • L'aggiornamento della matrice di connettività $\Theta$ utilizzando soluzioni in forma chiusa derivate dalle condizioni di ottimalità del primo ordine.
   • L'aggiornamento del piano di trasporto $T$ utilizzando un algoritmo di Majorizzazione-Minimizzazione (MM), che linearizza la penalità di sparsità e risolve il problema quadratico risultante (ad esempio, tramite Frank-Wolfe).

Contributi Chiave

• Collegamento Teorico: Il lavoro dimostra che la MLVI negli SBM può essere interpretata come una proiezione di Gromov-Wasserstein semi-rilassata con regolarizzazione entropica.
• Risultati di Consistenza: Gli autori dimostrano che gli stimatori srGW non regolarizzati recuperano consistentemente sia la vera matrice di connettività SBM sia le assegnazioni ai cluster latenti nel regime asintotico ($N \to \infty$).
• Selezione Automatica del Modello: Incorporando una penalità promotrice di sparsità, il metodo permette il recupero simultaneo dei parametri del modello e la selezione del numero di cluster in un singolo passo di ottimizzazione. Ciò evita la necessità di costose ricerche su griglia o euristiche greedy.
• Efficienza Algoritmica: Il solver proposto è progettato per l'efficienza, con una complessità teorica dominata dal calcolo del gradiente ($O(N^2K + K^2N)$), e risulta significativamente più veloce su CPU rispetto agli stimatori variazionali dello stato dell'arte.

Risultati
Gli autori valutano il loro approccio su dati sintetici generati da SBM Bernoulliani sotto tre regimi di connettività: Assortativo, Hub e Disassortativo.

• Prestazioni di Clustering: Lo stimatore srGW proposto utilizzando una perdita di log-verosimiglianza negativa (srGW-NLL) supera o eguaglia costantemente le linee di base dello stato dell'arte (inclusi Louvain, Infomap, Greed e Stimatori Variazionali) in termini di Indice Rand Aggiustato (ARI), in particolare nei regimi Hub e Disassortativo dove le assunzioni strutturali di altri metodi vengono violate.
• Selezione del Modello: Il metodo recupera con successo il vero numero di cluster ($K^*$) attraverso varie impostazioni di iperparametri, dimostrando un plateau nelle prestazioni quando il parametro di sparsità è tarato appropriatamente.
• Efficienza: Il metodo srGW-NLL risulta essere da 1 a 2 ordini di grandezza più veloce su CPU rispetto agli stimatori Variazionali e ai metodi Greed, principalmente perché bypassa i cicli iterativi di selezione del modello richiesti da tali approcci.

Significato e Affermazioni
Il lavoro afferma di fornire un ponte teorico e pratico unificato tra Trasporto Ottimo e Modelli a Blocchi Stocastici. Il suo significato primario risiede nel dimostrare che gli stimatori basati su OT non sono solo consistenti per il recupero dei parametri, ma possono anche eseguire la selezione intrinseca del modello attraverso la promozione della sparsità. Ciò offre un'alternativa computazionalmente efficiente ai metodi tradizionali basati sulla verosimiglianza che faticano con la complessità combinatoria della selezione del numero di cluster. Gli autori posizionano il loro lavoro come un passo verso una partizione di grafi più robusta ed efficiente, in particolare in scenari in cui il numero di comunità è sconosciuto e la struttura del grafo è complessa (ad esempio, contenente hub o pattern disassortativi). Osservano che, sebbene la consistenza asintotica sia dimostrata, la taratura dell'iperparametro di sparsità rimane un'area per future indagini, e le prestazioni del metodo su reti reali sono oggetto di ulteriori studi.