2025-11-18T15:28:13.400087

Local Causal Discovery for Statistically Efficient Causal Inference

Schubert, Claassen, Magliacane
Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it then finds the optimal adjustment set by leveraging local causal discovery to infer the mediators and their parents. Otherwise, it returns the locally valid parent adjustment sets based on the learned local structure. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.
academic

Scoperta Causale Locale per l'Inferenza Causale Statisticamente Efficiente

Informazioni Fondamentali

  • ID Articolo: 2510.14582
  • Titolo: Local Causal Discovery for Statistically Efficient Causal Inference
  • Autori: Mátyás Schubert (University of Amsterdam), Tom Claassen (Radboud University Nijmegen), Sara Magliacane (University of Amsterdam)
  • Classificazione: stat.ML cs.AI cs.LG
  • Data di Pubblicazione: 16 ottobre 2025 (preprint arXiv)
  • Link Articolo: https://arxiv.org/abs/2510.14582v1

Riassunto

I metodi di scoperta causale possono identificare insiemi di aggiustamento validi per la stima dell'effetto causale tra una coppia di variabili target, anche quando il grafo causale sottostante è sconosciuto. I metodi di scoperta causale globale si concentrano sull'apprendimento dell'intero grafo causale e quindi possono recuperare insiemi di aggiustamento ottimali (cioè quelli con la varianza asintotica più bassa), ma diventano rapidamente computazionalmente intrattabili con l'aumento del numero di variabili. I metodi di scoperta causale locale offrono alternative più scalabili concentrandosi sul vicinato locale delle variabili target, ma sono limitati a insiemi di aggiustamento statisticamente subottimali. In questo lavoro, gli autori propongono LOAD (Local Optimal Adjustment Discovery), un metodo di scoperta causale affidabile e completo che combina l'efficienza computazionale dei metodi locali con l'ottimalità statistica dei metodi globali.

Contesto di Ricerca e Motivazione

Definizione del Problema

Nell'inferenza causale, la stima dell'effetto causale tra due variabili è un compito centrale. Quando il grafo causale sottostante è sconosciuto, è necessario utilizzare metodi di scoperta causale per identificare insiemi di aggiustamento validi per la stima dell'effetto causale. I metodi esistenti affrontano un compromesso fondamentale:

  1. Il Dilemma dei Metodi Globali: I metodi di scoperta causale globale (come l'algoritmo PC) possono apprendere il grafo causale completo e recuperare insiemi di aggiustamento ottimali, ma la complessità computazionale cresce esponenzialmente con il numero di variabili, rendendoli infattibili per problemi su larga scala.
  2. Le Limitazioni dei Metodi Locali: I metodi di scoperta causale locale (come MB-by-MB, LDECC) sono computazionalmente efficienti, ma possono solo recuperare insiemi di aggiustamento subottimali, risultando in una varianza asintotica più elevata nella stima dell'effetto causale.

Motivazione della Ricerca

Gli autori identificano i seguenti problemi nei metodi locali esistenti:

  • L'algoritmo LocalPC non è sufficientemente affidabile nell'identificazione delle variabili adiacenti e potrebbe identificare erroneamente coniugi non adiacenti come adiacenti
  • L'algoritmo LDECC è incompleto e in alcuni casi non riesce a orientare tutti gli archi orientabili
  • L'algoritmo LDP potrebbe erroneamente segnalare effetti non identificabili quando l'effetto è effettivamente identificabile come zero

Pertanto, è necessario un nuovo metodo che mantenga l'efficienza computazionale dei metodi locali mentre raggiunge l'ottimalità statistica dei metodi globali.

Contributi Principali

  1. Sviluppo di metodi per determinare l'identificabilità dell'effetto causale basati su informazioni locali: Propone condizioni necessarie e sufficienti per determinare se un effetto causale è identificabile utilizzando solo informazioni locali.
  2. Proposizione dell'algoritmo LOAD: Un metodo affidabile e completo che identifica insiemi di aggiustamento ottimali utilizzando solo informazioni locali intorno alle variabili.
  3. Valutazione sperimentale completa: Valuta LOAD su dati sintetici e reali, dimostrando che può recuperare insiemi di aggiustamento di alta qualità con basso costo computazionale.
  4. Garanzie teoriche: Dimostra l'affidabilità e la completezza di LOAD nel determinare l'identificabilità dell'effetto causale e nel trovare insiemi di aggiustamento ottimali.

Spiegazione Dettagliata del Metodo

Definizione del Compito

Data una coppia di variabili target X e Y, l'obiettivo è:

  1. Determinare la relazione causale tra X e Y (antenato esplicito, possibile antenato o non-antenato definito)
  2. Giudicare se l'effetto causale è identificabile
  3. Se identificabile, trovare l'insieme di aggiustamento ottimale; altrimenti, restituire un insieme di aggiustamento padre localmente valido

Architettura dell'Algoritmo LOAD

L'algoritmo LOAD si articola in 5 passaggi principali:

Passaggio 1: Determinazione della Relazione Causale tra Variabili Target

Utilizza l'algoritmo LocalRelate (Algoritmo 1), determinando la relazione attraverso i seguenti teoremi:

  • Relazione di Antenato Esplicito (Teorema 4.1): Per due nodi distinti X e Y in un CPDAG G, X ∈ ExplAn_G(Y) se e solo se X ⊥̸⊥ Y | Pa_G(X) ∪ Sib_G(X)
  • Relazione di Non-Antenato Definito (Teorema 4.2): X è un non-antenato definito di Y se e solo se X ⊥⊥ Y | Pa_G(X)

Passaggio 2: Test dell'Identificabilità dell'Effetto Causale

Propone un test adattativo basato su informazioni locali:

Lemma 4.3: Per X ∈ PossAn_G(Y) in un CPDAG G, G è adattato rispetto a (X,Y) se e solo se:

∀V ∈ Sib_G(X) : V ⊥⊥ Y | Pa_G(V) ∪ {X}

Questa condizione può essere rilevata efficientemente attraverso l'algoritmo LocalAmenTest (Algoritmo 2).

Passaggi 3-5: Costruzione dell'Insieme di Aggiustamento Ottimale

Se l'effetto causale è identificabile, LOAD costruisce l'insieme di aggiustamento ottimale attraverso i seguenti passaggi:

  1. Trovare i Discendenti Espliciti: Identificare tutti i discendenti espliciti di T
  2. Identificare i Nodi Mediatori: Trovare i nodi che sono sia discendenti espliciti di T che antenati espliciti di O
  3. Costruire l'Insieme di Aggiustamento Ottimale: 
    Oset_G(T,O) = Pa_G(Cn_G(T,O)) \ (Cn_G(T,O) ∪ {T})

Punti di Innovazione Tecnica

  1. Test di Adattabilità Locale: Propone per la prima volta condizioni necessarie e sufficienti per testare l'adattabilità utilizzando solo informazioni locali, evitando la necessità di controllare tutti i possibili percorsi diretti.
  2. Meccanismo di Cache: L'algoritmo MB-by-MB migliorato utilizza la cache per riutilizzare le coperte di Markov e le strutture locali identificate nelle esecuzioni precedenti, migliorando significativamente l'efficienza computazionale.
  3. Completezza Teorica: Dimostra che LOAD è affidabile e completo nel determinare le relazioni causali, l'identificabilità e gli insiemi di aggiustamento ottimali.

Configurazione Sperimentale

Dataset

  1. Dati Sintetici:
    • Grafi Erdős–Rényi generati casualmente
    • Numero di variabili: 100-1000
    • Grado atteso: d=2, grado massimo: dmax=10
    • Numero di campioni: nD=10000
  2. Reti Reali:
    • Rete MAGIC-NIAB: 44 nodi, grado medio 3
    • Rete ANDES: 223 nodi, grado medio 3.03

Metriche di Valutazione

  1. Efficienza Computazionale: Numero di test di indipendenza condizionata
  2. Qualità dell'Insieme di Aggiustamento: Punteggio F1 dell'insieme di aggiustamento ottimale
  3. Qualità della Stima dell'Effetto Causale: Distanza di intervento (intervention distance)

Metodi di Confronto

  • Metodi Globali: PC, MARVEL, SNAP(∞)
  • Metodi Locali: MB-by-MB+, LDECC+, LDP+ (versioni estese)

Dettagli di Implementazione

  • Livello di significatività: α = 0.01
  • Tre tipi di test di indipendenza condizionata: d-separazione oracle, test Fisher-Z, test G²
  • Ogni configurazione eseguita 100 volte, escludendo i 5 migliori e i 5 peggiori risultati

Risultati Sperimentali

Risultati Principali

Efficienza Computazionale

Il numero di test di indipendenza condizionata di LOAD rimane costantemente inferiore ai metodi globali in tutte le configurazioni, leggermente superiore ai metodi locali:

  • Con 1000 nodi, LOAD richiede 9.43×10³ test, mentre PC richiede 542.52×10³
  • Rispetto ai 5.64×10³ test di MB-by-MB+, il sovraccarico aggiuntivo di LOAD è ragionevole

Qualità dell'Insieme di Aggiustamento (Punteggio F1)

  • Configurazione Oracle: LOAD raggiunge il perfetto F1=1.0, paragonabile ai metodi globali
  • Test Fisher-Z: LOAD supera i metodi di base su tutti i numeri di nodi, con punteggio F1 circa 0.91-0.95
  • Test G²: LOAD mostra prestazioni subottimali, ma rimane il secondo miglior metodo

Distanza di Intervento

LOAD realizza la distanza di intervento più bassa nella maggior parte delle configurazioni:

  • Configurazione Oracle: 0.003 (paragonabile a PC, SNAP)
  • Test Fisher-Z: 0.014-0.026 (migliore)
  • Test G²: 0.022-0.036 (secondo migliore, solo dopo PC)

Risultati su Dati Reali

Sulla rete MAGIC-NIAB:

  • LOAD raggiunge il miglior punteggio F1 (0.62)
  • Realizza la distanza di intervento più bassa (0.007)
  • Numero di test di indipendenza condizionata (4.35×10³) intermedio tra metodi locali e globali

Esperimenti di Ablazione

  1. Relazione Trattamento-Risultato Nota: Quando fornita conoscenza di background, LOAD* supera PC su dati binari
  2. Coppie Target Identificabili: Quando assicurato che l'effetto causale sia identificabile, i pattern dei risultati rimangono coerenti
  3. Sensibilità ai Parametri: LOAD mostra robustezza rispetto a diversi numeri di campioni e gradi attesi

Lavori Correlati

Metodi di Scoperta Causale Globale

  • Algoritmo PC: Metodo classico basato su vincoli, ma con elevata complessità computazionale
  • MARVEL: Metodo ricorsivo, ancora difficile da scalare a centinaia di variabili
  • SNAP: Identificazione e rimozione progressiva di non-antenati definiti, ma richiede comunque scoperta causale su tutti i possibili antenati

Metodi di Scoperta Causale Locale

  • MB-by-MB: Scoperta sequenziale della coperta di Markov, ma limitata a insiemi di aggiustamento subottimali
  • LDECC: Controllo efficiente dei collider, ma con problemi di affidabilità e completezza
  • LDP: Apprendimento dell'insieme di aggiustamento attraverso partizioni, ma potenzialmente ancora subottimale con assunzioni limitate

Vantaggi di questo Lavoro

LOAD è il primo metodo che raggiunge simultaneamente i seguenti obiettivi:

  1. Utilizzo solo di informazioni locali
  2. Recupero di insiemi di aggiustamento ottimali
  3. Fornitura di garanzie teoriche (affidabilità e completezza)

Conclusioni e Discussione

Conclusioni Principali

  1. LOAD combina con successo l'efficienza computazionale dei metodi locali con l'ottimalità statistica dei metodi globali
  2. Il test di adattabilità locale proposto fornisce un metodo efficiente per giudicare l'identificabilità dell'effetto causale
  3. Su vari tipi di dati e strutture di rete, LOAD mostra prestazioni superiori

Limitazioni

  1. Assunzione di Sufficienza Causale: La versione attuale assume l'assenza di fattori di confondimento latenti o bias di selezione
  2. Collo di Bottiglia Computazionale su Reti su Larga Scala: Su grafi estremamente grandi, la ricerca della coperta di Markov potrebbe ancora diventare un collo di bottiglia computazionale
  3. Prestazioni su Dati Binari: Prestazioni limitate su dati binari utilizzando il test G²

Direzioni Future

  1. Estensione a Impostazioni Causalmente Insufficienti: Gestione di fattori di confondimento latenti
  2. Ottimizzazione della Scoperta della Coperta di Markov: Ulteriore miglioramento dell'efficienza computazionale su reti su larga scala
  3. Miglioramento delle Prestazioni in Campioni Finiti: Particolarmente sulle prestazioni con dati binari

Valutazione Approfondita

Punti di Forza

  1. Contributi Teorici Significativi: Propone per la prima volta un test di adattabilità basato solo su informazioni locali, con importante valore teorico
  2. Forte Praticità: Raggiunge l'ottimalità statistica mantenendo l'efficienza computazionale, risolvendo problemi critici nelle applicazioni pratiche
  3. Esperimenti Completi: Copre vari tipi di dati, scale di rete e metriche di valutazione, con risultati convincenti
  4. Algoritmo Completo: Fornisce garanzie teoriche di affidabilità e completezza, con progettazione algoritmica rigorosa

Insufficienze

  1. Limitazioni delle Assunzioni: L'assunzione di sufficienza causale potrebbe non essere soddisfatta nelle applicazioni pratiche
  2. Problemi di Scalabilità: Sebbene migliore dei metodi globali, presenta ancora sfide computazionali su reti estremamente grandi
  3. Prestazioni in Campioni Finiti: Le prestazioni non sono sufficientemente stabili in alcune configurazioni di campioni finiti

Impatto

  1. Valore Accademico: Fornisce un nuovo quadro teorico e idee di progettazione algoritmica al campo della scoperta causale
  2. Valore Pratico: Ha importanza significativa nelle applicazioni pratiche che richiedono stima dell'effetto causale
  3. Riproducibilità: Fornisce descrizioni dettagliate dell'algoritmo e configurazioni sperimentali, facilitando la riproduzione e l'estensione

Scenari Applicabili

  1. Inferenza Causale su Scala Media: Compiti di stima dell'effetto causale con centinaia o migliaia di variabili
  2. Risorse Computazionali Limitate: Scenari applicativi che richiedono il bilanciamento tra efficienza computazionale e prestazioni statistiche
  3. Ambienti Causalmente Sufficienti: Studi osservazionali senza importanti fattori di confondimento latenti

Bibliografia

L'articolo cita importanti letteratura nel campo dell'inferenza causale, inclusa:

  • Pearl (2009): Causality - Manuale classico di inferenza causale
  • Spirtes et al. (2000): Lavoro fondamentale sulla scoperta causale basata su vincoli
  • Henckel et al. (2022): Criteri grafici per insiemi di aggiustamento ottimali
  • Perković et al. (2015): Definizione e proprietà dell'adattabilità

Valutazione Complessiva: Questo è un articolo di alta qualità nel campo dell'inferenza causale, con importanti contributi sia a livello teorico che pratico. L'algoritmo LOAD risolve elegantemente il compromesso tra efficienza computazionale e ottimalità statistica nella scoperta causale, con importante valore accademico e prospettive di applicazione.