Optimization-Free Topological Sort for Causal Discovery via the Schur Complement of Score Jacobians

1. Enunciato del Problema

La scoperta causale continua mira a recuperare il Grafo Aciclico Diretto (DAG) sottostante da dati osservazionali. I metodi all'avanguardia attuali (ad esempio, NOTEARS, DAGMA) si basano su ottimizzazione vincolata continua, accoppiando l'apprendimento della rappresentazione con l'ottimizzazione strutturale tramite penalità di aciclicità non convesse (ad esempio, $tr(e^{W \circ W}) = d$).

Limitazioni Chiave:

• Ottimi Locali: La natura non convessa delle penalità di aciclicità causa l'intrappolamento dei solver basati su gradienti in minimi locali, specialmente in regimi ad alta dimensionalità.
• Scalabilità: Questi metodi soffrono di costi computazionali di $O(d^3)$ per ogni passo del gradiente a causa dei controlli ripetuti di aciclicità, limitando la scalabilità a dataset ad alta dimensionalità ($d \gg 100$).
• Sovraccarico di Riaddestramento: Gli approcci basati sul punteggio esistenti richiedono spesso un riaddestramento ricorsivo di modelli generativi su sottoinsiemi marginalizzati per identificare l'ordine dei nodi, creando colli di bottiglia computazionali severi.

2. Metodologia: Ordinamento Topologico Punteggio-Schur (SSTS)

Gli autori propongono un paradigma disaccoppiato che sposta il collo di bottiglia dall'ottimizzazione non convessa alla stima statistica del punteggio. L'idea centrale è che la gerarchia causale lasci una firma geometrica nella Matrice di Informazione Jacobiana del Punteggio (SJIM).

A. Fondamento Teorico

• Funzione di Punteggio e SJIM: Sia $s(x) = \nabla_x \log p(x)$ la funzione di punteggio. La SJIM, $I$, è definita come l'attesa negativa dell'Hessiano della densità logaritmica: $I = \mathbb{E}[-\nabla^2_x \log p(x)]$.
• Identificabilità delle Foglie (Teorema 3.1): Nei Modelli a Rumore Additivo Gaussiani Lineari (ANM), le voci diagonali della SJIM codificano la gerarchia topologica. Nello specifico, un nodo $l$ è una foglia topologica (pozzo) se e solo se la sua voce diagonale $I_{ll}$ è minima ($1/\sigma^2$).
• Marginalizzazione Esatta tramite Complemento di Schur (Teorema 3.2): Una volta identificata una foglia, la sua rimozione dal grafo è matematicamente equivalente al calcolo del complemento di Schur della SJIM rispetto a quella foglia. Ciò consente un'eliminazione ricorsiva senza riaddestrare il modello generativo.
• Estensione Non Lineare e Gap di Attesa: Nei modelli ANM non lineari, l'operatore di attesa non commuta con l'inversione della matrice ($\text{Schur}(\mathbb{E}[H]) \neq \mathbb{E}[\text{Schur}(H)]$). Gli autori derivano un Gap di Attesa ($\Delta$) proporzionale alla covarianza del gradiente del meccanismo di rumore. Questo gap introduce un errore strutturale in contesti non lineari.

B. Algoritmo: Block-SSTS

Per affrontare il gap di attesa e la varianza del campione finito, gli autori introducono Block-SSTS:

1. Modellazione Generativa: Addestrare una rete di punteggio senza vincoli (ad esempio, MLP) per stimare $s_\theta(x)$.
2. Priorità Jacobiana Sparsa: Applicare una penalità Group Lasso ($\ell_{1,2}$) ai pesi dello strato di ingresso per indurre sparsità nel Jacobiano empirico, riducendo la varianza di stima in dimensioni elevate.
3. Marginalizzazione a Blocchi: Invece della rimozione sequenziale di singoli nodi, l'algoritmo raggruppa nodi foglia paralleli (quelli con energie diagonali simili entro una tolleranza $\gamma$) ed esegue un'inversione del complemento di Schur a blocchi.
   • Ciò comprime la profondità di estrazione, troncando l'accumulo del gap di attesa non lineare.
   • Evita il costo $O(Nd^3)$ della correzione esatta della covarianza campione per campione.
4. Potatura degli Archi: Una volta estratto l'ordine topologico, il DAG viene recuperato tramite regressione sparsa standard (Lasso) per ogni nodo rispetto ai suoi antenati permessi.

3. Contributi Chiave

1. Mappatura Algebrica dell'Aciclicità: Dimostrato che la marginalizzazione iterativa dei nodi foglia è esattamente equivalente al complemento di Schur della SJIM nei modelli ANM Gaussiani Lineari. Per gli ANM non lineari, hanno caratterizzato l'errore di approssimazione (Gap di Attesa).
2. Estrazione Disaccoppiata: Eliminato completamente il collo di bottiglia dell'ottimizzazione non convessa. La scoperta causale è riformulata come un problema di stima statistica seguito da operazioni matriciali deterministiche ($O(d^3)$ totali, ma eseguite una sola volta).
3. Scalabilità fino a $d=1000$: Introdotto Block-SSTS per gestire grafi non lineari ad alta dimensionalità, ottenendo un recupero strutturale fino a 1000 variabili, un regime in cui i metodi di ottimizzazione continua falliscono.
4. Correzione della Metrica: Argomentato contro l'uso della correlazione di rango (Kendall's $\tau$) per valutare DAG paralleli, proponendo le Violazioni di Arco (EV) come metrica rigorosa invariante all'ambiguità topologica.

4. Risultati Sperimentali

• Regimi Lineari: SSTS ottiene zero violazioni di archi causali per dimensioni fino a $d=1000$ su ANM lineari, validando l'esattezza teorica.
• Regimi Non Lineari:
  • Efficienza: A $d=50$, SSTS riduce il tempo di esecuzione da ~2700s (DAGMA) a 3.66s ottenendo al contempo una Distanza di Hamming Strutturale (SHD) significativamente inferiore (2.6 vs 93.0).
  • Scalabilità: A $d=1000$, SSTS completa l'estrazione in meno di 1 secondo, mentre i metodi continui sono computazionalmente intrattabili.
  • Trade-off: Sebbene SSTS introduca un piccolo errore strutturale a causa del gap di attesa non lineare, questo rimane limitato dalla varianza di stima del campione finito della rete di punteggio.
• Dati Reali: Sulla rete di segnalazione proteica Sachs ($d=12$), SSTS ha superato DAGMA e Scalable SCORE sia in accuratezza (SHD 13.8 vs 15.0/16.2) che in velocità (6.62s vs 182s/56s).
• Studi di Ablazione:
  • Sparsità: I prior Group Lasso sono critici per la stabilità in regimi privi di dati ($N=500, d=100$).
  • Tolleranza del Blocco: Una tolleranza di blocco moderata ($\gamma \approx 0.05$) tronca ottimalmente l'accumulo di errori senza violare la gerarchia causale.

5. Significato e Conclusione

Questo lavoro riformula fondamentalmente la scoperta causale da un problema di ottimizzazione vincolata a una sfida di stima statistica. Sfruttando le proprietà geometriche della funzione di punteggio e le proprietà algebriche del complemento di Schur, SSTS aggira gli ottimi locali e i problemi di scalabilità intrinseci alle penalità di aciclicità continue.

Implicazioni:

• Teoriche: Stabilisce un collegamento diretto tra matching del punteggio, geometria dell'informazione e ordinamento topologico.
• Pratiche: Consente l'apprendimento della struttura causale su dataset non lineari ad alta dimensionalità (fino a $d=1000$) precedentemente inaccessibili ai metodi di ottimizzazione continua.
• Limitazioni: La fedeltà del metodo nei regimi non lineari è infine limitata dall'accuratezza della stima della funzione di punteggio (varianza del campione finito) e dall'entità del gap di attesa non lineare, piuttosto che dalla convergenza dell'ottimizzazione.

In sintesi, SSTS offre un percorso deterministico e senza ottimizzazione verso la scoperta causale, dimostrando che una volta rimosso il collo di bottiglia non convesso, la sfida principale diventa la stima statistica della geometria del punteggio.