Sintesi Tecnica: Filtrazioni di Cicli Senza Corde per la Rilevazione della Dimensionalità in Reti Complesse tramite Analisi Topologica dei Dati

1. Enunciato del Problema

Le reti complesse in diversi domini (biologici, sociali, tecnologici) spesso mostrano pattern strutturali coerenti con una geometria iperbolica latente sottostante. Determinare la dimensionalità efficace ($D$) di questo spazio latente è cruciale per comprendere la complessità strutturale, l'organizzazione delle comunità, la navigazione nella rete e la dinamica dei sistemi. Sebbene esistano varie definizioni di dimensionalità delle reti (ad esempio, frattale, spettrale, metrica) e approcci guidati da modelli (come il modello $S^D/H^{D+1}$) abbiano stimato con successo la dimensionalità proiettando le frequenze dei cicli su spazi di configurazione, questi metodi richiedono spesso la generazione di grandi insiemi di reti surrogate sintetiche per ogni nuova rete target. Questo processo è computazionalmente intensivo e manca di un quadro unificato, guidato dai dati, che integri l'Analisi Topologica dei Dati (TDA) con l'apprendimento automatico per bypassare la generazione di surrogate.

Inoltre, le applicazioni standard della TDA nella scienza delle reti sono state limitate. L'omologia persistente ordinaria è inadatta ai grafi perché i cicli (caratteristiche unidimensionali) hanno persistenza infinita in assenza di simplessi di dimensioni superiori per riempirli. Inoltre, gli schemi di filtrazione esistenti (ad esempio, basati sul grado dei nodi o sulla curvatura di Ricci) potrebbero non catturare le firme geometriche specifiche richieste per la stima della dimensionalità.

2. Metodologia

Gli autori propongono un approccio a due facce che combina topologia algebrica e apprendimento automatico per stimare la dimensionalità della rete.

A. Filtrazioni di Cicli Senza Corde e Persistenza Estesa

L'innovazione topologica centrale è uno schema di pesatura basato sui cicli senza corde (cicli senza corde interne).

1. Pesatura: Per una data rete, vengono costruiti tre grafi con pesi sugli archi. Il peso di un arco è definito dalla densità locale di cicli senza corde di lunghezze specifiche: triangoli ($C_t$), quadrati ($C_s$) e pentagoni ($C_p$).
2. Persistenza Estesa: Poiché i cicli nei grafi non muoiono nelle filtrazioni standard, gli autori calcolano la persistenza estesa. Ciò comporta una tecnica per trasformare il grafo con pesi sugli archi in un grafo con pesi sui nodi topologicamente equivalente tramite "suddivisione per separazione del grado". Ciò consente l'uso di software TDA standard (Gudhi) per calcolare la persistenza estesa dei cicli, definita come la differenza tra il valore di nascita nella filtrazione di sottolivello e il valore di nascita nella filtrazione di sovrolivello.
3. Descrittori: La Persistenza Estesa Totale (la somma dei valori di persistenza per tutti i cicli indipendenti) viene calcolata per ciascuna delle tre filtrazioni, producendo un vettore di caratteristiche $(TP_t, TP_s, TP_p)$.

B. Approcci di Stima della Dimensionalità

Il documento presenta due metodi per stimare $D$:

1. k-Nearest Neighbors (kNN) basato su Surrogate:

   • Per una rete target, viene generato un insieme di surrogate sintetiche utilizzando la procedura $D$-GR (Randomizzazione Geometrica). Questo metodo riconnette la rete per massimizzare la verosimiglianza del modello $S^D/H^{D+1}$ preservando la sequenza esatta dei gradi della target.
   • La rete target e le sue surrogate vengono mappate in uno spazio di configurazione definito da $(TP_t, TP_s, TP_p)$.
   • Un classificatore kNN identifica la dimensione $D$ delle surrogate più vicine alla rete target.

2. Rete Neurale (DimNN):

   • Per evitare di generare surrogate per ogni nuova rete, gli autori addestrano un Perceptron Multistrato Residuale (DimNN).
   • Dati di Addestramento: Un database di 792.000 reti sintetiche (SynNet) generate dal modello $S^D/H^{D+1}$ con dimensioni note ($D \in [1, 10]$) e parametri variabili (eterogeneità del grado $\gamma$, temperatura inversa $\beta$).
   • Caratteristiche di Input: Il modello utilizza un vettore di caratteristiche a 12 dimensioni che include:
     • Statistiche del grafo: Numero di nodi ($N$), grado medio ($\langle k \rangle$), secondo momento normalizzato della distribuzione dei gradi ($\langle k^2 \rangle / \langle k \rangle^2$), gradi minimi/massimi e grado medio dei vicini ($\langle k_{nn} \rangle$).
     • Densità dei cicli: Densità medie di triangoli, quadrati e pentagoni senza corde ($C_t, C_s, C_p$).
     • Descrittori topologici: Persistenze estese totali ($TP_t, TP_s, TP_p$).
   • Architettura: Un MLP profondo con 21 livelli nascosti, attivazioni ReLU, dropout (50%) e connessioni residue, addestrato con AdamW.
   • Validazione: Un modello di regressione secondario (utilizzando la perdita MSE) è stato addestrato per verificare la robustezza, mostrando un alto accordo con il modello di classificazione.

3. Contributi Chiave

• Schema di Filtrazione Innovativo: Introduzione di uno schema di filtrazione basato sulla densità di cicli senza corde per grafi, specificamente progettato per catturare proprietà geometriche rilevanti per la dimensionalità.
• Persistenza Estesa per Grafi: Adattamento della persistenza estesa a grafi con pesi sugli archi tramite suddivisione per separazione del grado, consentendo il calcolo di durate finite dei cicli in contesti di rete dove la persistenza standard fallisce.
• Stima della Dimensionalità Guidata dai Dati: Sviluppo di DimNN, una rete neurale addestrata su un vasto database sintetico in grado di stimare la dimensionalità della rete direttamente da una singola rete reale senza generare surrogate.
• Integrazione di TDA e ML: Dimostrazione che le caratteristiche TDA (persistenza totale) migliorano significativamente l'accuratezza dei modelli di apprendimento automatico per la stima della dimensionalità, superando i modelli che utilizzano solo densità di cicli o statistiche dei gradi.

4. Risultati

• Correlazione: È stata osservata una correlazione negativa tra la dimensionalità della rete e i valori di persistenza estesa totale, in particolare per quadrati e pentagoni (coefficienti di Pearson $\rho_s \approx -0.31$, $\rho_p \approx -0.24$).
• Validazione Sintetica:
  • Il metodo kNN basato su surrogate ha raggiunto un'accuratezza ragionevole su target sintetici, con matrici di confusione che mostrano alta fedeltà per la maggior parte delle dimensioni, sebbene si sia verificata una certa confusione tra dimensioni adiacenti in reti altamente eterogenee.
  • DimNN ha raggiunto un'accuratezza di classificazione del 83,00% sul set di validazione utilizzando il vettore di caratteristiche completo.
  • Gli studi di ablazione hanno confermato che combinare la persistenza totale con le densità medie dei cicli e le caratteristiche legate ai gradi massimizza le prestazioni. La rimozione delle caratteristiche TDA ha comportato un calo significativo dell'accuratezza.
• Applicazione nel Mondo Reale:
  • Il metodo è stato applicato a 10 reti reali ben note (ad esempio, Connectoma Umano, collaborazione Jazz, reti Email). Le dimensioni inferite erano coerenti con la letteratura precedente (ad esempio, i connectomi cerebrali vicini a $D=3$, le reti sociali che richiedono dimensioni leggermente superiori).
  • Quando applicato a un dataset più ampio di 53 reti reali, il modello ha previsto dimensioni comprese tra 1 (Software, grafi Web) e 10 (alcune reti sociali).
  • Robustezza: Due modelli addestrati indipendentemente (classificazione e regressione) hanno mostrato un alto accordo (fino all'88,86% su dati sintetici), suggerendo che i modelli catturano relazioni sottostanti piuttosto che overfitting.
  • Validazione: Le reti surrogate generate utilizzando le dimensioni previste e gli embedding D-Mercator hanno riprodotto con successo le proprietà topologiche chiave delle reti originali, inclusa la distribuzione dei gradi, lo spettro di clustering e le soglie di percolazione.

5. Significato e Affermazioni

Il documento afferma che questo lavoro colma il divario tra la teoria delle reti complesse e l'Analisi Topologica dei Dati fornendo un metodo robusto ed efficace per scoprire la geometria nascosta delle reti complesse.

• Efficienza: L'approccio basato su reti neurali offre un vantaggio computazionale significativo rispetto ai precedenti metodi basati su surrogate, poiché non richiede riaddestramento o generazione di surrogate per nuove reti.
• Espressività: Lo studio dimostra che le filtrazioni consapevoli dei cicli e i descrittori di persistenza estesa sono caratteristiche altamente espressive per il rilevamento della dimensionalità, complementari ai descrittori geometrici tradizionali.
• Generalizzazione: Il modello trasferisce con successo dai dati di addestramento sintetici alle reti reali, suggerendo che le strutture geometriche latenti delle reti reali sono ben rappresentate dal modello $S^D/H^{D+1}$ entro i regimi di parametri testati.

Gli autori notano modestamente che il quadro mira principalmente alle reti geometriche ($\beta > D$) e che estendere l'approccio a regimi debolmente geometrici o ottimizzare l'architettura neurale per cambiamenti di distribuzione più ampi rimane una direzione per il lavoro futuro. Il documento si posiziona come una prova di concetto per l'utilità delle filtrazioni basate sui cicli nella TDA e per la fattibilità della stima della dimensionalità assistita dal deep learning.