Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks

Sintesi Tecnica: Ricostruzione di Grafi da Co-visitatio di Random-Walk

Enunciato del Problema
Il documento affronta il problema inverso della ricostruzione di una struttura di grafo ignota a partire dalla traiettoria di un random walk (cammino casuale) che diffonde su di esso. Ciò sorge in contesti in cui i processi dinamici sono osservabili (ad esempio, serie temporali, processi di diffusione o traccianti diffusivi), ma la connettività sottostante (il "cablaggio") non lo è. Una sfida centrale in questo dominio è la ricostruibilità: un random walk può trasmettere informazioni solo sugli archi che effettivamente attraversa; gli archi mai visitati dalla traiettoria campionata sono fondamentalmente irrecuperabili da tale campione, indipendentemente dall'estimatore utilizzato. Una seconda sfida è l'identificabilità: l'osservabile deve preservare sufficienti informazioni strutturali a coppie per distinguere tra grafi che condividono riepiloghi a livello di nodo identici (come le sequenze di grado).

Metodologia
Gli autori propongono una pipeline di ricostruzione che evita il collasso delle informazioni strutturali in statistiche a livello di nodo utilizzando un osservabile a coppie e un modello a coppie.

1. Osservabile (Matrice di Co-visitatio): Invece di utilizzare le probabilità di occupazione marginali (che convergono alla distribuzione stazionaria dei gradi e perdono l'informazione a coppie), il metodo impiega la matrice di co-visitatio $C$. Questa matrice registra le coppie ordinate $(i, j)$ visitate dal camminatore prima che venga calcolata la somma per riga, preservando le transizioni specifiche $i \to j$.
2. Modello (Base di Pesi degli Archi a Coppie): Il modello assume un log-peso a coppie $\beta_{ij}$ per ogni coppia candidata nella base. La matrice di transizione $P$ è derivata da una matrice di pesi $S(\beta)$ tramite normalizzazione per riga. Questo approccio assegna un parametro unico a ogni potenziale arco, permettendo al modello di catturare strutture clusterizzate che i modelli a potenziale di nodo additivo non possono cogliere.
3. Fitter (Levenberg–Marquardt Bilanciato per Frame - fbLM): I parametri $\beta$ vengono adattati alla matrice di co-visitatio osservata utilizzando uno schema Levenberg–Marquardt bilanciato per frame (fbLM).
   • Pesi di Gruppo: Il residuo è raggruppato per vertice. I pesi sono ottimizzati su un frame ortonormale (varietà di Stiefel) per garantire che nessun singolo vertice domini l'adattamento. Questo "bilanciamento per frame" impedisce il collasso dei pesi sui nodi ad alto grado e assicura che i vertici con informazioni uniche ricevano il peso appropriato.
   • Fissaggio del Gauge: La co-visitatio è invariante rispetto a uno spostamento globale di tutti i log-pesi ($\beta \to \beta + c\mathbf{1}$). Il metodo fissa esplicitamente questo gauge centrando i parametri dopo ogni passaggio di proposta.
   • Propagazione dell'Incertezza: Una matrice di covarianza viene derivata dall'informazione di Fisher, con la direzione del gauge esplicitamente proiettata per evitare instabilità numeriche.
4. Readout (Accoppiamento Auto-calibrato): L'insieme finale di archi è determinato da una metrica di accoppiamento auto-calibrata $\rho_{ij} = W_{ij}/\sqrt{s_i s_j}$, dove $W$ sono i pesi adattati e $s_i$ sono le intensità dei vertici. Un arco viene dichiarato tale se $\rho_{ij}$ supera l'accoppiamento medio dei suoi due endpoint. Questa soglia è relativa e basata sui dati, non richiede alcun cut-off assoluto o conoscenza a priori della densità del grafo.

Dataset e Setup Sperimentale
La pipeline viene testata su cinque diversi test-bed:

• Empirico: Un sottografo di comunicazione email (email-eu-core) con dimensioni variabili ($N=20, 100, 240$).
• Geometrico (Astrofisico): Triangolazioni di Delaunay e tassellazioni di Voronoi derivate dal catalogo astronomico COSMOS, ricostruite all'estensione completa ($N=119$ e $N=223$).
• Controllato: Due grafi a 12 vertici (uno uniciclico, uno un albero) utilizzati per controlli di sanità.

Gli esperimenti sono condotti sotto due regimi:

1. Regime di Cammino Finito (Finite-Walk): Ricostruzione da traiettorie campionate di lunghezza $T$.
2. Regime di Rumore Moltiplicativo: Ricostruzione da una matrice di co-visitatio analitica perturbata da rumore gaussiano, isolando la tolleranza dell'estimatore dalla copertura del campionamento.

Risultati Chiave

• Ricostruzione ad Alta Fedeltà: La pipeline raggiunge un'alta qualità di ricostruzione in tutti i test-bed. Sui grafi geometrici a scala completa, recupera le strutture Delaunay e Voronoi con coefficienti di correlazione di Matthews (MCC) rispettivamente di 0,988 e 0,977. Sul grafo email empirico ($N=240$), raggiunge un MCC di 0,967.
• Confronto con i Baseline: La pipeline fbLM supera significativamente il baseline del graphical-lasso. Sul grafo Delaunay completo, il baseline restituisce un MCC di 0,540 rispetto allo 0,988 di fbLM.
• Limite di Copertura: Nel regime di cammino finito, il fattore limitante è la copertura del cammino (walk coverage), non l'algoritmo di adattamento. L'analisi mostra che i falsi negativi corrispondono quasi esclusivamente agli archi che il random walk non ha mai attraversato. Quando il cammino copre il grafo, l'estimatore recupera gli archi con una fedeltà quasi perfetta.
• Robustezza al Rumore: Nel regime di rumore moltiplicativo (dove tutte le coppie sono candidate), il metodo recupera esattamente il grafo a bassi livelli di rumore. Anche al 40% di rumore, il metodo mantiene un ranking perfetto degli archi (AUC = 1,000), con una degradazione delle prestazioni che avviene solo quando gli archi forti scendono sotto la soglia di readout, non a causa di falsi positivi.
• Quantificazione dell'Incertezza: Il metodo fornisce stime di incertezza per ogni arco derivate dall'informazione di Fisher. Queste incertezze sono sostanziali (incertezza relativa mediana $\sim$30–45%) ma sono correttamente localizzate su archi di confine o a bassa copertura, mentre gli archi interni rimangono strettamente vincolati.

Significatività e Rivendicazioni
Il documento sostiene di aver stabilito un estimatore robusto per la ricostruzione di grafi che opera senza conoscenza a priori della dimensione, della densità o dell'adiacenza reale del grafo. Il suo contributo primario è dimostrare che, per grafi geometrici ed empirici, la ricostruibilità è governata dal campionamento del grafo piuttosto che dall'estimatore.

Gli autori sottolineano che:

1. La ricostruibilità è un problema di campionamento: Se un cammino non visita un arco, nessun estimatore può recuperarlo. Il metodo proposto estrae tutta l'informazione disponibile dalla traiettoria.
2. Gli osservabili a coppie sono essenziali: L'uso della co-visitatio invece delle statistiche marginali è necessario per distinguere grafi con sequenze di grado identiche.
3. Auto-calibrazione: Il meccanismo di readout non richiede una sintonizzazione esterna o soglie assolute, rendendolo applicabile a grafi sconosciuti.
4. Applicabilità Astrofisica: Il metodo è applicato con successo a grafi geometrici derivati da dati astrofisici reali (catalogo COSMOS), stabilendo un framework in cui il grafo stesso è l'oggetto dell'inferenza piuttosto che una scelta di modellazione predefinita.

Il documento conclude che, sebbene l'estimatore sia altamente efficace, il limite pratico della ricostruzione in scenari di cammino finito è determinato dalla copertura della rete da parte della traiettoria, un fattore che può essere quantificato e ottimizzato indipendentemente dalla procedura di adattamento.