Estimate Collapsibility of Causal Effects in Completed Partial DAGs via Strong d-Convex Hulls

Resumen Técnico: Estimación de la Colapsabilidad de Efectos Causales en CPDAGs Completados mediante Envolventes d-Convexas Fuertes

Planteamiento del Problema
La estimación de efectos causales a partir de datos observacionales depende típicamente de modelos gráficos causales. Si bien el criterio de la puerta trasera (back-door criterion) y el cálculo do permiten una estimación precisa en Grafos Acíclicos Dirigidos (DAGs), el descubrimiento causal a partir de datos suele arrojar solo una clase de equivalencia de Markov de los DAGs, representada por un Grafo Parcialmente Dirigido Acíclico Completado (CPDAG). Estimar efectos causales en CPDAGs, por ejemplo, mediante el algoritmo IDA (Cálculo de Intervención cuando el DAG está Ausente), requiere enumerar posibles conjuntos de padres o conjuntos de ajuste válidos a través de todos los DAGs consistentes. Este proceso se vuelve computacionalmente prohibitivo en entornos de alta dimensionalidad. Además, los métodos existentes para reducir los conjuntos de ajuste suelen depender de la poda local o de conocimiento previo adicional, dejando variables redundantes en el grafo que deberían ser eliminadas para simplificar el modelo. Un desafío crítico es identificar un subconjunto mínimo de variables que preserve las estimaciones de los efectos causales tras marginalizar sobre variables irrelevantes, una propiedad conocida como colapsabilidad. Aunque la colapsabilidad ha sido estudiada en grafos no dirigidos y para propiedades distribucionales, su aplicación a la estimación de efectos causales en CPDAGs sigue siendo poco explorada.

Metodología
El artículo propone un marco para estimar efectos causales en CPDAGs mediante la identificación de "conjuntos colapsables mínimos" a través de un nuevo concepto de teoría de grafos: la Envolvente d-Convexa Fuerte (Strong d-Convex Hull).

1. Estimación de la Colapsabilidad en CBNs: Los autores definen la colapsabilidad de la estimación para Redes Bayesianas Causales (CBNs). Un conjunto $R$ es colapsable de estimación si las Estimaciones de Máxima Verosimilitud (MLEs) de la distribución marginal sobre $R$ permanecen consistentes ya sea que se computen en el grafo completo o en el subgrafo inducido.
2. Envolventes d-Convexas Fuertes: Para caracterizar los conjuntos colapsables mínimos, el artículo introduce la Envolvente d-Convexa Fuerte. Un subconjunto $R$ es fuertemente d-convexo si:
   • No hay caminos inductores para $R$ dentro del subgrafo inducido.
   • El conjunto de hijos del complemento de $R$ que también son ancestros de $R$ está linealmente ordenado con respecto a $R$.
     El artículo demuestra (Teorema 1) que un conjunto es un conjunto colapsable mínimo si y solo si es la envolvente d-convexa fuerte de las variables objetivo.
3. Algoritmos (ISCHA): Los autores desarrollan el Algoritmo de Identificación de la Envolvente d-Convexa Fuerte (ISCHA). Este algoritmo opera en dos fases:
   • Primero computa la envolvente d-convexa absorbiendo iterativamente vértices en los caminos inductores más cortos entre nodos no adyacentes en el conjunto objetivo.
   • Luego impone la condición de orden lineal absorbiendo a los padres de los nodos que violan la restricción de orden.
     El algoritmo se ejecuta en tiempo polinomial ($O(k^2 \times |V|^4)$, donde $k$ es el tamaño del conjunto objetivo y $|V|$ es el total de variables).
4. Integración con IDA para CPDAGs: El método se extiende a CPDAGs aprovechando el hecho de que la envolvente d-convexa fuerte es invariante en todos los DAGs de una clase de equivalencia de Markov (Teorema 5). El algoritmo propuesto Subgraph IDA:
   • Selecciona un DAG arbitrario de la clase de equivalencia del CPDAG.
   • Computa la envolvente d-convexa fuerte para las variables de tratamiento y resultado.
   • Realiza la estimación del efecto causal (usando el ajuste de puerta trasera) en este subgrafo local reducido.
   • Esto reduce el espacio de enumeración de DAGs y el tamaño de los conjuntos de ajuste requeridos para la estimación.

Contribuciones Clave

• Caracterización Teórica: El artículo introduce el concepto de colapsabilidad de la estimación para efectos causales en CPDAGs y establece que los conjuntos colapsables mínimos corresponden exactamente a envolventes d-convexas fuertes.
• Innovación Algorítmica: Propone el algoritmo ISCHA para identificar eficientemente estos conjuntos mínimos en DAGs y generaliza el enfoque a CPDAGs.
• Eficiencia en la Estimación Causal: Al combinar la reducción de grafos con el marco IDA, el método reduce significativamente la carga computacional de enumerar DAGs y conjuntos de ajuste sin sacrificar la precisión de la estimación.

Resultados Experimentales
Los autores evaluaron el método a través de simulaciones numéricas y análisis empírico en redes bayesianas del mundo real (ej. Hailfinder, Pathfinder, Munin1) y grafos aleatorios sintéticos.

• Razonamiento Probabilístico: El enfoque de subgrafo local preservó la distribución de probabilidad del grafo completo con una divergencia de Kullback-Leibler insignificante (orden de $10^{-17}$ a $10^{-18}$). Logró ratios de reducción de nodos sustanciales (hasta un 96%) y aceleraciones significativas en el tiempo de consulta.
• Estimación de Efectos Causales: Las comparaciones entre Subgraph IDA y el IDA estándar mostraron:
  • Precisión: Recall y Precisión perfectos o casi perfectos (frecuentemente 1.0) a través de diversos tamaños de red (20 a 100 nodos) y densidades. Las estimaciones de los efectos causales fueron idénticas al método del grafo completo.
  • Eficiencia: El método demostró factores de aceleración consistentes, que van desde ~1.1x en redes pequeñas hasta más de 30x en redes grandes (ej. Munin1). La aceleración aumentó con el tamaño y la densidad de la red.

Significancia y Reivindicaciones
El artículo afirma que su método proporciona una solución rigurosa y eficiente para la estimación de efectos causales en CPDAGs de alta dimensionalidad. Al reducir el problema a un subgrafo local definido por la envolvente d-convexa fuerte, el enfoque mantiene la consistencia de los estimadores antes y después de la marginalización. Esto permite a los investigadores realizar inferencia causal precisa mientras reducen significativamente los costos computacionales y la complejidad del espacio del modelo. Los autores señalan que el método es particularmente efectivo para pares tratamiento-resultado no adyacentes y actualmente asume datos totalmente observados, dejando los grafos con variables latentes como una dirección para trabajos futuros.