Efficient Causal Graph Discovery Using Large Language Models

1. Il Problema: Scoperta di Grafi Causali Scalabile

La scoperta causale mira a identificare le relazioni causali tra diverse variabili, rappresentate solitamente come un Grafo Aciclico Diretto (DAG). Tradizionalmente, questo processo si basa su metodi statistici che richiedono grandi quantità di dati osservazionali e tecniche di ottimizzazione continua (es. NOTEARS, PC, GES). Tuttavia, questi metodi possono essere computazionalmente costosi e richiedono dati numerici specifici.

Recentemente, i Large Language Models (LLM) sono stati utilizzati per la scoperta causale basandosi sulla conoscenza interna (metadati e descrizioni delle variabili) senza bisogno di dati osservazionali. Tuttavia, l'approccio esistente si basa su query a coppie (pairwise): per $n$ variabili, l'LLM deve interrogare tutte le possibili coppie per determinare la direzione della causalità. Questo comporta una complessità di $O(n^2)$ query, rendendo il metodo impraticabile per grafi di grandi dimensioni (es. centinaia di nodi), poiché il numero di richieste cresce quadraticamente.

2. Metodologia Proposta

Gli autori propongono un nuovo framework che utilizza gli LLM per la scoperta completa del grafo causale, superando il collo di bottiglia delle query quadratiche attraverso un approccio di Ricerca in Ampiezza (Breadth-First Search - BFS).

Architettura del Framework

Il metodo non interroga l'LLM su ogni coppia di nodi, ma istruisce il modello a identificare tutti i potenziali effetti di una singola variabile in una singola risposta. Il processo si articola in tre fasi:

1. Fase di Inizializzazione:

   • L'LLM viene interrogato per identificare le variabili che non sono causate da nessun'altra variabile nel grafo (nodi radice).
   • Queste variabili vengono inserite in una coda (queue) per avviare la BFS.
   • Prompt: Chiede di selezionare le variabili indipendenti basandosi sulle descrizioni di tutte le variabili.

2. Fase di Espansione:

   • Si estrae il primo nodo dalla coda.
   • L'LLM viene interrogato per elencare tutte le variabili causate dal nodo corrente, fornendo anche la struttura parziale del grafo già scoperta.
   • Questo riduce drasticamente il numero di query necessarie.

3. Fase di Inserimento e Controllo Cicli:

   • Gli archi proposti dall'LLM vengono aggiunti al grafo solo se non violano il vincolo di aciclicità (DAG).
   • Viene eseguita una Depth-First Search (DFS) sul grafo predittivo per verificare se l'aggiunta di un arco crea un ciclo. Se un ciclo viene rilevato, l'arco viene scartato.
   • Le nuove variabili connesse vengono aggiunte alla coda per l'espansione successiva.

Complessità Computazionale

• Metodo Pairwise (Precedente): $O(n^2)$ query.
• Metodo Proposto (BFS): $O(n)$ query, poiché ogni nodo viene visitato ed espanso una sola volta.

Integrazione con Dati Osservazionali

Il framework è flessibile e permette di incorporare dati osservazionali quando disponibili. Gli autori aggiungono i coefficienti di correlazione di Pearson tra le variabili nei prompt di espansione. Questo fornisce all'LLM segnali statistici aggiuntivi per affinare le sue deduzioni quando la conoscenza interna non è sufficiente.

3. Contributi Chiave

• Scalabilità: È il primo metodo basato su LLM applicabile a grafi causali di grandi dimensioni, riducendo la complessità delle query da quadratica a lineare.
• Indipendenza dai Dati: Funziona efficacemente senza dati osservazionali, basandosi solo sulla conoscenza semantica dell'LLM (simulando il ragionamento di un esperto umano).
• Garanzia DAG: Introduce un meccanismo di controllo dei cicli (cycle check) durante l'inserimento degli archi per garantire che il grafo risultante sia sempre aciclico.
• Ibridazione: Dimostra come integrare facilmente statistiche osservazionali (correlazioni) nei prompt per migliorare le prestazioni.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su tre grafi causali di dimensioni diverse utilizzando GPT-4:

1. Asia (8 nodi, 8 archi): Grafo piccolo.
2. Child (20 nodi, 25 archi): Grafo medio.
3. Neuropathic Pain (221 nodi, 770 archi): Grafo molto grande.

Prestazioni:

• Grafi Piccoli e Medi (Asia, Child): Il metodo proposto ottiene risultati State-of-the-Art (SOTA), superando i metodi statistici tradizionali (GES, PC, NOTEARS, DAGMA) e l'approccio pairwise, specialmente nel regime a basso numero di campioni.
  • Su Asia: F-Score di 0.93 (vs 0.67 del migliore metodo statistico).
  • Su Child: Con dati osservazionali (10.000 campioni), raggiunge un F-Score di 0.63, superando tutti i baselines.
• Grafo Grande (Neuropathic Pain):
  • I metodi pairwise e statistici (GES) sono risultati impraticabili o hanno fallito per esaurimento della memoria a causa del numero enorme di possibili archi ($\binom{221}{2} = 24.310$).
  • Il metodo proposto è stato l'unico in grado di elaborare il grafo con prestazioni ragionevoli (F-Score 0.35, NHD Ratio 0.64), mentre gli altri metodi hanno fallito catastroficamente.

5. Significato e Implicazioni

Questo lavoro rappresenta un passo fondamentale nell'applicazione degli LLM alla scienza causale:

• Efficienza: Dimostra che è possibile scoprire strutture causali complesse con un numero di interazioni con l'LLM linearmente scalabile, rendendo fattibile l'analisi di domini reali complessi.
• Accessibilità: Elimina la necessità di grandi dataset numerici e di costosi tempi di addestramento, rendendo la scoperta causale accessibile a domini dove i dati osservazionali sono scarsi o costosi da ottenere.
• Versatilità: Offre un ponte tra il ragionamento semantico degli LLM e la rigida struttura dei grafi causali, aprendo la strada a future ricerche su approcci ibridi (statistica + LLM) e strategie di prompting avanzate (es. Tree of Thoughts).

In sintesi, il paper propone una soluzione efficiente e scalabile che trasforma gli LLM da semplici generatori di ipotesi a coppie in motori potenti per la ricostruzione completa di strutture causali complesse.