From Simple to Composite Perturbations: A Unified Decomposition Framework for Stochastic Block Models

1. Il Problema

L'articolo affronta le sfide dell'inferenza statistica nei Modelli a Blocchi Stocastici (SBM), in particolare quando si utilizzano statistiche spettrali basate sulla matrice di adiacenza normalizzata.

• Contesto: In teoria, se la matrice delle probabilità $B$ è nota, la matrice di adiacenza normalizzata $A^*$ appartiene alla classe delle matrici di Wigner generalizzate, permettendo di derivare leggi limite precise (es. legge di Tracy-Widom per l'autovalore massimo, normalità asintotica per le statistiche spettrali lineari).
• Sfida Pratica: Nella realtà, $B$ è sconosciuta e deve essere stimata tramite un stimatore plug-in $\hat{B}$. Sostituendo $B$ con $\hat{B}$ nella costruzione della matrice normalizzata, si introducono errori di stima.
• Distinzione Critica: L'articolo identifica due tipi di perturbazione distinti derivanti da questa sostituzione:
  1. Perturbazione Semplice ($\Delta$): Si verifica quando $\hat{B}$ sostituisce $B$ solo nel numeratore della matrice normalizzata.
  2. Perturbazione Composita ($\tilde{\Delta}$): Si verifica quando $\hat{B}$ sostituisce $B$ sia nel numeratore che nel denominatore (caso più realistico e comune).

Il problema centrale è che le analisi esistenti spesso trattano queste perturbazioni in modo indifferenziato o non riescono a controllare rigorosamente gli errori indotti dalla perturbazione composita, portando a condizioni di validità subottimali o a teorie asintotiche incomplete.

2. Metodologia

Gli autori sviluppano un approccio analitico basato sulla decomposizione della somma totale dei quadrati e sulla struttura spettrale delle matrici di errore.

• Decomposizione della Somma dei Quadrati: Analizzano la traccia del quadrato della matrice perturbata, $tr((A^* + \text{perturbazione})^2)$, scomponendola in tre termini:

  1. $tr((A^*)^2)$: Termine principale.
  2. $2tr(A^* \cdot \text{perturbazione})$: Termine incrociato.
  3. $tr(\text{perturbazione}^2)$: Termine di errore quadratico.

• Analisi Asintotica Comparativa: Dimostrano che mentre per la perturbazione semplice il termine incrociato $tr(A^*\Delta)$ è asintoticamente trascurabile ($o_p(1)$), per la perturbazione composita il termine $tr(A^*\tilde{\Delta})$ non è trascurabile e converge a una distribuzione normale. Questo è dovuto al fatto che $\tilde{\Delta}$ ha una struttura a rango pieno (full-rank) dovuta al fattore di ridimensionamento nel denominatore, a differenza di $\Delta$ che è a rango basso.

• Framework di Decomposizione Unificata: Per gestire la perturbazione composita, gli autori propongono una nuova scomposizione strutturale:
  $$\tilde{\Delta} = \check{A} + \Delta + \check{\Delta}$$
  Dove:

  • $\check{A}$: Una matrice di bias a rango pieno introdotta dal fattore di ridimensionamento (scaling factor).
  • $\Delta$: La perturbazione semplice (a rango basso).
  • $\check{\Delta}$: Un bias aggiuntivo derivante da $\Delta$.
    Questa decomposizione permette di isolare il termine dominante $\check{A}$, che è la fonte principale della non-trascurabilità del termine incrociato.

3. Contributi Chiave

Il paper apporta quattro contributi fondamentali alla teoria delle matrici casuali e all'inferenza sulle reti:

1. Rivelazione delle Differenze Strutturali: Dimostrano che la perturbazione composita non è una semplice ridimensionamento di quella semplice. Il termine incrociato $tr(A^*\tilde{\Delta})$ è asintoticamente significativo e converge a una distribuzione normale, mentre $tr(A^*\Delta)$ è trascurabile. Inoltre, i termini quadratici $tr(\Delta^2)$ e $tr(\tilde{\Delta}^2)$, pur avendo lo stesso ordine di grandezza, convergono a distribuzioni limite diverse.
2. Framework di Decomposizione Unificata: Sviluppano la decomposizione $\tilde{\Delta} = \check{A} + \Delta + \check{\Delta}$, che fornisce un meccanismo matematico rigoroso per isolare e controllare l'errore di bias a rango pieno introdotto dalla stima del denominatore.
3. Miglioramento del Tasso di Convergenza per l'Autovalore Massimo: Per la statistica dell'autovalore massimo ($\lambda_1$), migliorano la condizione esistente da $K = O(n^{1/6-\tau})$ al tasso ottimale $K = o(n^{1/6})$ per la perturbazione semplice. Per il caso composito, richiedono una condizione aggiuntiva di bilanciamento delle comunità (Assunzione 3) per controllare la matrice di bias $\check{A}$, permettendo comunque di raggiungere il tasso ottimale $K = o(n^{1/6})$.
4. Prova di Normalità Asintotica per Statistiche Spettrali Lineari: Forniscono una prova rigorosa della normalità asintotica per la statistica spettrale lineare (es. $tr(\hat{A}^3)$) nel caso di stimatore plug-in. Risolvono la sfida tecnica di dimostrare che tutti i termini di errore indotti dalla perturbazione (sia semplice che composita) sono asintoticamente trascurabili, validando l'uso pratico di queste statistiche anche quando $B$ è stimata.

4. Risultati Principali

• Comportamento del Termine Incrociato:
  • Semplice: $tr(A^*\Delta) = o_p(1)$ (trascurabile).
  • Composita: $tr(A^*\tilde{\Delta}) \xrightarrow{d} N(0, 1)$ (dominante e non trascurabile).
• Autovalore Massimo:
  • Sotto perturbazione semplice, la distribuzione limite di $\lambda_1(\bar{A})$ segue la legge di Tracy-Widom ($TW_1$) con $K = o(n^{1/6})$.
  • Sotto perturbazione composita, la stessa legge vale per $\lambda_1(\hat{A})$ a condizione che le dimensioni delle comunità siano bilanciate (nessuna comunità troppo grande rispetto a $n/\log K$).
• Statistiche Spettrali Lineari:
  • La statistica $tr(\hat{A}^3)$ è asintoticamente normale ($N(0,1)$ dopo opportuna normalizzazione) sia nel caso semplice che composito, sotto la condizione $K = o(n^{1/2})$.
• Simulazioni: Gli studi simulativi confermano che le distribuzioni empiriche dei termini incrociati e dei termini quadratici corrispondono alle previsioni teoriche (distribuzione Chi-quadro per la perturbazione semplice, Normale per quella composita).

5. Significato e Implicazioni

Questo lavoro è significativo per diversi motivi:

• Rafforzamento Teorico: Colma un divario teorico importante fornendo garanzie rigorose per l'inferenza basata su stimatori plug-in negli SBM, che sono onnipresenti nell'analisi delle reti reali.
• Nuovo Paradigma Analitico: Il framework di decomposizione unificata offre un nuovo strumento per analizzare errori di stima in modelli a variabili latenti. Dimostra che le perturbazioni "composite" (dove l'errore appare sia nel numeratore che nel denominatore) introducono bias strutturali a rango pieno che devono essere trattati separatamente.
• Estendibilità: Il metodo proposto non è limitato ai test a un campione in SBM non diretti. Gli autori suggeriscono che questo approccio può essere esteso a problemi di test a due campioni, reti dirette, e altri contesti di stima della covarianza ad alta dimensione che si basano su matrici normalizzate.
• Ottimizzazione dei Parametri: La capacità di raggiungere il tasso ottimale $K = o(n^{1/6})$ per l'autovalore massimo permette di validare modelli con un numero di comunità più elevato rispetto ai risultati precedenti, ampliando l'applicabilità pratica degli algoritmi di rilevamento delle comunità.

In sintesi, il paper trasforma la comprensione degli errori di stima nelle reti da un ostacolo tecnico a una struttura analizzabile, fornendo le basi teoriche necessarie per l'uso affidabile di metodi spettrali in scenari realistici dove i parametri del modello sono sconosciuti.