Low-Complexity and Consistent Graphon Estimation from Multiple Networks

1. Il Problema

Il lavoro affronta la sfida di stimare un graphon (una funzione simmetrica misurabile $W: [0,1]^2 \to [0,1]$ che parametrizza un modello di grafo casuale non parametrico) a partire da una collezione di multiple reti (grafi).
Le difficoltà specifiche di questo scenario sono:

• Assenza di corrispondenza dei nodi: Le reti non condividono lo stesso insieme di nodi e possono avere dimensioni variabili.
• Non-identificabilità: Diverse funzioni graphon possono generare la stessa distribuzione di grafi osservati a causa di riordinamenti (permutazioni) dello spazio latente.
• Limitazioni dei metodi esistenti: I metodi attuali per l'analisi multi-rete soffrono di due estremi: o sono poco accurati (es. media di stime singole), o hanno un'alta complessità computazionale (es. metodi basati su reti neurali o barycenter di Gromov-Wasserstein), rendendoli impraticabili per grandi collezioni di grafi.

L'obiettivo è sviluppare un stimatore che sia statisticamente consistente (accurato all'aumentare dei dati) e computazionalmente efficiente (bassa complessità algoritmica).

2. Metodologia: Joint Graph Sorting (JGS)

Gli autori introducono un nuovo stimatore chiamato Joint Graph Sorting (JGS). A differenza dei metodi convenzionali che ordinano i nodi rete per rete, JGS allinea simultaneamente tutti i nodi di tutte le reti per costruire un'unica istogramma globale.

Fasi dell'algoritmo:

1. Calcolo dei gradi normalizzati: Per ogni nodo in ogni rete, si calcola il grado empirico normalizzato. Sotto l'ipotesi che la funzione di grado normalizzato $g(u) = \int W(u,v)dv$ sia strettamente monotona, questo grado è una stima coerente della posizione latente del nodo.
2. Ordinamento Globale (Joint Sorting): Tutti i nodi dell'insieme unione di tutte le reti ($N = \sum n^{(m)}$ nodi totali) vengono ordinati in base ai loro gradi normalizzati empirici. Questo crea una permutazione globale che allinea i nodi attraverso le diverse reti.
3. Stima delle Posizioni Latenti: La posizione latente stimata per un nodo è data dalla sua posizione normalizzata nell'ordine globale: $\hat{U}_{i,(m)} = \frac{\text{rank}(i,m)}{N} - \frac{1}{2N}$.
4. Costruzione dell'Istogramma: L'area $[0,1]^2$ è suddivisa in $k^2$ blocchi. La frequenza degli spigoli osservati all'interno di ciascun blocco (considerando solo le coppie di nodi che appartengono alla stessa rete originale, poiché le inter-rete sono mancanti) viene calcolata per stimare la probabilità di connessione.
5. Selezione di $k$: Viene proposto un criterio euristico per scegliere il numero di blocchi $k$ bilanciando bias e varianza e garantendo che non ci siano blocchi vuoti: $k \approx \min\{S^{1/4}, \frac{N}{c(M + \log N)}\}$, dove $S$ è il numero totale di coppie osservate.

Complessità Computazionale:
La complessità totale è $O(N \log N + S)$, dove $N$ è il numero totale di nodi e $S$ il numero totale di spigoli osservati. Questo è significativamente più veloce dei metodi iterativi basati su ottimizzazione o reti neurali.

3. Contributi Chiave

1. Algoritmo Deterministico e Non Iterativo: JGS è un algoritmo di ordinamento congiunto che inferisce le posizioni latenti e produce una stima unificata del graphon senza bisogno di cicli di ottimizzazione complessi.
2. Garanzie Teoriche: Gli autori dimostrano la consistenza dello stimatore.
   • Le stime delle posizioni latenti convergono alle verità nascoste quando le dimensioni delle reti crescono.
   • L'errore quadratico medio integrato (MISE) dello stimatore del graphon tende a zero quando il numero di reti $M$ è fisso e le dimensioni delle reti $n^{(m)}$ tendono all'infinito.
   • Viene evidenziato un limite: la consistenza non è garantita se il numero di reti $M \to \infty$ mentre le dimensioni delle reti rimangono limitate (problema intrinseco alla stima delle posizioni con reti piccole).
3. Efficienza e Accuratezza: Sperimentalmente, JGS supera gli stati dell'arte (SBA, SAS, USVT, SGWB, SIGL) in termini di accuratezza, specialmente per reti piccole e di dimensioni eterogenee, con tempi di esecuzione di ordini di grandezza inferiori rispetto ai metodi consistenti più complessi.
4. Applicazione al Data Augmentation: JGS è stato integrato nel framework G-Mixup per l'aumento dei dati nelle reti neurali grafiche (GNN), migliorando le prestazioni di classificazione su dataset reali.

4. Risultati Sperimentali

• Dati Sintetici: Su 13 diversi graphon (inclusi casi non monotoni e non identificabili), JGS ha ottenuto il MISE più basso o tra i più bassi in quasi tutti i casi, superando metodi come SIGL (basato su reti neurali) e SGWB (basato su Gromov-Wasserstein).
• Tempo di Esecuzione: JGS è estremamente veloce. Mentre SIGL e SGWB richiedono minuti o ore per collezioni grandi, JGS completa l'analisi in secondi, rendendolo scalabile.
• Comportamento Asintotico:
  • Quando le dimensioni delle reti aumentano ($n \to \infty$), l'errore di stima diminuisce verso zero (consistenza confermata).
  • Quando il numero di reti aumenta ma le dimensioni restano fisse ($M \to \infty, n$ fisso), l'errore converge a un valore non nullo, confermando la limitazione teorica discussa.
• Classificazione Reale: Su dataset IMDB-BINARY e IMDB-MULTI, l'uso di JGS per generare grafi sintetici tramite G-Mixup ha portato a una maggiore accuratezza di classificazione rispetto all'uso di altri stimatori di graphon.

5. Significato e Implicazioni

Questo lavoro è significativo perché risolve il compromesso storico tra accuratezza statistica ed efficienza computazionale nell'analisi di collezioni di reti eterogenee.

• Praticità: Fornisce uno strumento utilizzabile per applicazioni reali su larga scala (es. neuroscienze, ecologia, bioinformatica) dove i metodi precedenti erano troppo lenti o poco precisi.
• Teoria: Chiarisce le condizioni di consistenza per la stima congiunta di graphon, identificando che la crescita delle dimensioni delle singole reti è cruciale per la consistenza, più della semplice aggiunta di nuove reti piccole.
• Versatilità: La capacità di JGS di funzionare bene anche su reti piccole e di dimensioni variabili lo rende ideale per scenari reali dove i dati sono spesso frammentati e disomogenei.

In sintesi, JGS rappresenta un avanzamento fondamentale verso l'analisi statistica scalabile e robusta di collezioni di reti complesse, offrendo un metodo "low-complexity" che non sacrifica la qualità della stima.