Come si scopre un grafo diretto senza cicli da serie temporali?

Immagina di avere a disposizione una serie di misurazioni, come la temperatura, il traffico internet o i battiti cardiaci, registrate nel tempo. Ognuna di queste variabili può influenzare le altre, ma a volte l’effetto è istantaneo, altre volte si manifesta con un ritardo. Gli scienziati vogliono capire quali variabili hanno un legame diretto e in che direzione, cioè chi “influenza” chi. Per rappresentare questi legami usano un grafo diretto aciclico (DAG), una rete dove le frecce non formano cicli.

Fino a poco tempo fa, i metodi più diffusi per ricavare il DAG da dati temporali si basavano su vincoli “soft” che, pur garantendo l’assenza di cicli, rendevano l’ottimizzazione molto complessa e non garantivano soluzioni globali. Il nuovo approccio, invece, parte da un’ipotesi più semplice: tutti i pesi delle frecce sono non‑negativi, cioè le influenze non possono essere “negative”. Questa restrizione permette di trasformare il problema in un’ottimizzazione convessa, più facile da risolvere e con garanzia di trovare la soluzione migliore.

Il metodo utilizza la “method of multipliers”, una tecnica matematica che gestisce i vincoli in modo efficiente. I risultati su dati sintetici mostrano che il nuovo algoritmo supera le alternative esistenti, recuperando correttamente la struttura del DAG e identificando le dipendenze istantanee e ritardate. In pratica, questo significa che, con meno ipotesi e più robustezza, possiamo ricostruire le reti di causa‑effetto nascoste nei dati temporali, aprendo la porta a nuove scoperte in economia, biologia e ingegneria.

Il modello di base è un Vector Autoregressive Model (VAR) esteso con componenti strutturali (SVARM). La parte istantanea è rappresentata da una matrice di adiacenza A, soggetta al vincolo di non‑negatività (A_{ij} ≥ 0) e di aciclicità. Tradizionalmente, l’aciclicità è imposta tramite la funzione h(A)=tr(e^{A∘A})−d, dove ∘ è il prodotto di Hadamard; questa è non convessa e porta a ottimizzazioni locali. Qui, sfruttando A ≥ 0, si può dimostrare che la condizione A^k = 0 per qualche k ≤ d (d numero di nodi) è equivalente a richiedere che la matrice sia nilpotente, condizione convessa quando A è non‑negativa. Il problema diventa: minimizzare ‖X−∑_{τ=0}^{p}B_{τ}X_{t−τ}−AX_t‖_F^2 soggetto a A ≥ 0, A^k = 0. Si applica il metodo dei moltiplicatori di Lagrange (ADMM) per separare il termine di penalità quadratica dal vincolo di nilpotenza, introducendo variabili ausiliarie Z con Z = A e aggiungendo termini di penalità ρ/2‖A−Z‖_F^2. L’aggiornamento di A risolve un problema quadratico chiuso, mentre l’aggiornamento di Z richiede la proiezione su
{A ≥ 0, A^k = 0}, ottenibile tramite decomposizione spettrale e soglia dei valori propri. La convergenza globale è garantita dalla convessità congiunta del problema. Nei test su dati sintetici, con d=20 nodi e p=2 ritardi, il nuovo metodo ha raggiunto un F1‑score medio del 0.92, rispetto a 0.78 dei metodi basati su h(A). Inoltre, la complessità computazionale è O(d^3) per iterazione, simile ai metodi esistenti ma con tempi di convergenza più rapidi grazie alla struttura convessa. Questo approccio apre la strada a estensioni con regolarizzazioni sparsenza (L1) o a modelli non lineari, mantenendo la garanzia di ottimalità globale.