Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes

Il paper propone un test di ipotesi non parametrico basato sulla discrepanza massima del mezzo (MMD) applicata a incastonamenti di grafi ruotati tramite trasporto ottimale per verificare l'uguaglianza di distribuzione tra due reti casuali a rango basso di dimensioni diverse.

L'essenziale

Immagina di essere un detective che deve capire se due città, anche se di dimensioni diverse, hanno lo stesso "stile di vita" o la stessa "personalità".

In questo articolo, gli autori (Joshua Agterberg, Minh Tang e Carey Priebe) affrontano proprio questo problema, ma invece di città, studiano reti (come i social network, le connessioni tra neuroni nel cervello o le amicizie in una scuola).

Ecco la spiegazione semplice, passo dopo passo, usando delle metafore.

1. Il Problema: Due Città, Due Dimensioni

Immagina di avere due mappe di città:

• La Città A ha 1.000 abitanti.
• La Città B ha 5.000 abitanti.

Vuoi sapere: Queste due città seguono le stesse regole sociali? Forse in entrambe le persone tendono a fare amicizia con chi ha gli stessi hobby, anche se una città è più grande dell'altra.

Il problema è che le città sono diverse per dimensione e non sai esattamente chi corrisponde a chi (non sai quale abitante di A è "l'equivalente" di quale abitante di B). Inoltre, le regole per fare amicizia potrebbero essere nascoste e non visibili direttamente.

2. La Soluzione: La "Fotografia" Nascosta (Embedding)

Per capire la personalità di una città, gli autori usano una tecnica chiamata incorporamento spettrale (spectral embedding).
Immagina di prendere la mappa complessa di ogni città e di trasformarla in una fotografia semplificata in 3D.

• Ogni persona nella città diventa un punto in questa fotografia.
• La posizione del punto non è casuale: riflette il "carattere" di quella persona (quanto è popolare, a quale gruppo appartiene, ecc.).

Ora, invece di confrontare le mappe complesse, confrontiamo queste fotografie di punti. Se le due città hanno lo stesso "stile", i punti nelle due fotografie dovrebbero essere distribuiti nello stesso modo, anche se una foto ha più punti dell'altra.

3. L'Ostacolo: La Rotazione e lo Specchio

C'è un piccolo problema: quando crei la fotografia 3D, potresti averla ruotata o riflessa.

• Immagina di avere due foto dello stesso oggetto: una è dritta, l'altra è ruotata di 90 gradi o specchiata.
• Se le metti una sopra l'altra senza allinearle, sembreranno diverse, anche se rappresentano la stessa cosa.

In matematica, questo si chiama non-identificabilità. Le reti possono essere ruotate in modi strani (specialmente se ci sono "eigenvalori negativi", che sono come regole sociali che funzionano al contrario, tipo "più sei popolare, meno ti piaci").

4. Il Trucco Magico: Il Trasporto Ottimale (Optimal Transport)

Qui entra in gioco l'idea geniale degli autori. Per allineare le due fotografie, usano un algoritmo chiamato Trasporto Ottimale.

Immagina di dover spostare dei sacchi di sabbia (i punti della foto) dalla Città A alla Città B per farli combaciare perfettamente.

• L'algoritmo calcola il modo più efficiente per "spostare" i punti della prima foto sopra quelli della seconda, come se stessi allineando due puzzle.
• Una volta allineate (rotazione inclusa), le due immagini dovrebbero sovrapporsi perfettamente se le città hanno lo stesso stile.

5. La Misura della Differenza: La "Distanza di Gusto"

Una volta allineate le foto, usano una misura chiamata Maximum Mean Discrepancy (MMD).
Pensa a questa misura come a un assaggiatore di vini.

• L'assaggiatore prende un campione di persone dalla Città A e uno dalla Città B.
• Chiede: "Il gusto (la distribuzione delle amicizie) è lo stesso?"
• Se le due città hanno lo stesso stile, l'assaggiatore dirà: "Sembra lo stesso vino".
• Se sono diverse, dirà: "No, qui c'è qualcosa di diverso".

6. Perché è Importante? (I Risultati)

Gli autori dimostrano che il loro metodo funziona anche quando:

• Le città sono molto piccole o molto grandi.
• Le reti sono "sparse" (pochi collegamenti, come in un villaggio isolato) o "dense" (tutti connessi, come in una metropoli).
• Ci sono regole sociali strane (quelle con i "valori negativi" di cui parlavamo prima).

Hanno anche creato un codice (un algoritmo) che fa tutto questo lavoro automaticamente. Lo hanno testato con simulazioni al computer e ha funzionato bene: riesce a dire se due reti sono "gemelle" o meno, anche se sembrano diverse a prima vista.

In Sintesi

Questo articolo ci dice come confrontare due gruppi di persone (reti) di dimensioni diverse per capire se seguono le stesse regole sociali, anche se non sappiamo chi corrisponde a chi.

1. Semplifichiamo le reti in punti 3D.
2. Allineiamo i punti usando un algoritmo intelligente (Trasporto Ottimale) che ruota le immagini per farle combaciare.
3. Misuriamo la differenza. Se la differenza è zero, le reti sono "uguali" nella loro essenza.

È come se avessimo un traduttore universale che ci permette di confrontare la "personalità" di due gruppi di persone, indipendentemente da quanto sono grandi o da come sono organizzati.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento "Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes" di Agterberg, Tang e Priebe, redatta in italiano.

1. Il Problema

L'articolo affronta il problema statistico di testare l'uguaglianza delle distribuzioni tra due reti (grafi) di dimensioni diverse ($n$ e $m$ vertici).

• Contesto: In molte applicazioni (neuroscienze, reti sociali), si osservano due grafi senza una corrispondenza a priori tra i loro vertici. L'obiettivo è determinare se i due grafi provengono dalla stessa distribuzione sottostante, permettendo variazioni nella dimensione dei vertici e nella struttura della rete.
• Sfide principali:
  • Non-identificabilità: I modelli a spazio latente (come i Random Dot Product Graphs - RDPG) sono invarianti rispetto a trasformazioni ortogonali.
  • Geometria indefinita: Molti modelli di rete realistici (es. Stochastic Block Models bilanciati) producono matrici di probabilità degli archi con autovalori negativi, richiedendo un trattamento geometrico diverso rispetto ai classici RDPG (che hanno solo autovalori positivi).
  • Sparsità: Le reti reali sono spesso sparse (la densità degli archi tende a zero all'aumentare di $n$), rendendo difficile la stima delle posizioni latenti.
  • Dimensioni diverse: I grafi possono avere un numero diverso di vertici, rendendo inapplicabili i metodi standard basati su coppie appaiate.

2. Metodologia e Quadro Teorico

Modello di Riferimento: GRDPG

Gli autori utilizzano il framework del Generalized Random Dot Product Graph (GRDPG).

• Ogni vertice $i$ è associato a un vettore latente $X_i \in \mathbb{R}^d$.
• La probabilità di un arco tra $i$ e $j$ è data da $P(A_{ij}=1) = \alpha_n X_i^\top I_{p,q} X_j$, dove $I_{p,q} = \text{diag}(1, \dots, 1, -1, \dots, -1)$ è una matrice di firma che gestisce gli autovalori negativi ($p$ positivi, $q$ negativi).
• Questo modello include come casi speciali: Stochastic Block Models (SBM), Degree-Corrected SBM, Mixed-Membership SBM e Graphons a rango finito.

Ipotesi di Test

Si testano le seguenti ipotesi:

• $H_0$: Le distribuzioni dei due grafi sono equivalenti a meno di una trasformazione ortogonale indefinita ($F_Y \simeq F_X \circ Q$, con $Q \in O(p,q)$).
• $H_A$: Le distribuzioni non sono equivalenti.

Statistica di Test Proposta

La statistica di test si basa sulla Maximum Mean Discrepancy (MMD) applicata alle righe delle embedding spettrali dei grafi.

1. Embedding Spettrale (ASE): Si calcola l'embedding spettrale delle matrici di adiacenza $\hat{X}$ e $\hat{Y}$ utilizzando la decomposizione spettrale della matrice di adiacenza.
2. Allineamento (Rotazione): Poiché le embedding sono definite a meno di una trasformazione ortogonale, è necessario allineare $\hat{X}$ e $\hat{Y}$ prima di calcolare la distanza.
   • Viene proposto un algoritmo basato sul Trasporto Ottimale (Optimal Transport) combinato con il problema di Procrustes.
   • Si cerca una matrice ortogonale $\hat{W}$ che minimizzi la distanza di Wasserstein tra le distribuzioni empiriche delle embedding allineate.
   • Per gestire la complessità computazionale, si utilizza una regolarizzazione entropica (algoritmo di Sinkhorn).
3. Calcolo della Statistica: Una volta allineati i grafi, si calcola una statistica U-statistica (due-campione) basata su un kernel caratteristico radiale $\kappa$:
   $$U_{n,m}(\hat{X}, \hat{Y}\hat{W}) = \frac{1}{n(n-1)}\sum \kappa(\hat{X}_i, \hat{X}_j) - \frac{2}{mn}\sum \kappa(\hat{X}_i, \hat{Y}_k\hat{W}) + \frac{1}{m(m-1)}\sum \kappa(\hat{Y}_k, \hat{Y}_l)$$

3. Contributi Chiave

1. Generalizzazione ai Grafi Indefiniti: A differenza di lavori precedenti (es. Tang et al., 2017b) che si limitavano a grafi con autovalori positivi, questo lavoro estende la teoria ai GRDPG con autovalori negativi e ripetuti, gestendo la geometria indefinita ($O(p,q)$).
2. Consistenza in Regimi di Sparsità:
   • Dimostrano la consistenza del test anche per grafi sparsi, dove la densità media degli archi cresce più lentamente di $n$ (ma sufficientemente veloce, es. $\gg \log^4 n$).
   • Forniscono risultati di consistenza uniforme sotto ipotesi alternative fisse.
3. Gestione della Non-Identificabilità: Dimostrano che, sebbene la non-identificabilità richieda trasformazioni ortogonali indefinite, è possibile allineare le embedding utilizzando solo trasformazioni ortogonali standard (blocchi-ortogonali) per ottenere risultati asintotici validi, bypassando la complessità numerica dell'ottimizzazione su $O(p,q)$.
4. Algoritmo di Allineamento: Propongono un algoritmo iterativo (Sinkhorn + Procrustes) per stimare la matrice di rotazione ottimale, dimostrando la convergenza dell'algoritmo se inizializzato vicino all'ottimo globale.
5. Indipendenza dalla Conoscenza dei Parametri: Mostrano che il test rimane consistente anche quando i fattori di sparsità ($\alpha_n, \beta_m$) sono stimati dai dati, piuttosto che essere noti a priori.

4. Risultati Teorici e Simulazioni

Risultati Teorici

• Teorema 3.1 & 3.2: Sotto l'ipotesi nulla, la statistica test, opportunamente scalata (con fattore $m\beta_m + n\alpha_n$ per grafi sparsi), converge a zero quasi certamente. Sotto l'ipotesi alternativa, converge a una costante positiva.
• Corollario 3.3: Per grafi sufficientemente densi (grado atteso medio $> \sqrt{n} \log n$), la scalatura necessaria è $(m+n)$, simile ai risultati classici per dati euclidei (Gretton et al., 2012).
• Convergenza dell'Algoritmo: L'algoritmo di trasporto ottimo proposto converge a un punto fisso con un tasso geometrico, assumendo che il valore singolare minimo di una matrice correlata sia limitato inferiormente.

Simulazioni

Le simulazioni confermano la teoria:

• Il test mantiene un livello di significatività corretto (conservativo) sotto l'ipotesi nulla.
• La potenza del test (capacità di rifiutare $H_0$ quando falsa) aumenta con la dimensione del grafo ($n$) e la densità.
• Per reti molto sparse o con piccole deviazioni locali dall'ipotesi nulla, la potenza aumenta più lentamente, come previsto dalla teoria.
• Il metodo è efficace nel rilevare differenze tra modelli SBM e DCSBM (Degree-Corrected SBM), anche quando le dimensioni dei grafi sono diverse.

5. Significato e Implicazioni

Questo lavoro rappresenta un avanzamento significativo nella statistica delle reti per diversi motivi:

• Universalità: Offre un metodo non parametrico universale per testare l'uguaglianza di distribuzione su una vasta classe di modelli di rete a basso rango, superando le limitazioni dei modelli specifici (come solo SBM).
• Robustezza alla Sparsità: Estende la validità dei test di due campioni a scenari di rete realistici (sparsi), dove i metodi precedenti fallivano o richiedevano assunzioni di densità irrealistiche.
• Gestione della Complessità Geometrica: Risolve il problema tecnico della non-identificabilità nei modelli con autovalori negativi, fornendo una procedura pratica (allineamento tramite trasporto ottimo) che è teoricamente giustificata.
• Applicabilità Pratica: L'uso di algoritmi di trasporto ottimo regolarizzati rende il metodo computazionalmente fattibile per reti di dimensioni moderate, offrendo un'alternativa robusta ai test basati su statistiche specifiche o su grafi con vertici corrispondenti.

In sintesi, il paper fornisce un framework teorico solido e un algoritmo pratico per il confronto statistico di reti eterogenee, colmando il divario tra la teoria dei grafi casuali a basso rango e le esigenze di analisi dei dati reali.