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

A continuación se presenta un resumen técnico detallado del artículo "Ordenación topológica sin optimización para el descubrimiento causal mediante el complemento de Schur de Jacobianos de puntuación".

1. Planteamiento del Problema

El descubrimiento causal continuo busca recuperar el Grafo Acíclico Dirigido (DAG) subyacente a partir de datos observacionales. Los métodos actuales de vanguardia (por ejemplo, NOTEARS, DAGMA) dependen de optimización continua con restricciones, acoplando el aprendizaje de representaciones con la optimización estructural mediante penalizaciones de aciclicidad no convexas (por ejemplo, $tr(e^{W \circ W}) = d$).

Limitaciones Clave:

• Óptimos Locales: La naturaleza no convexa de las penalizaciones de aciclicidad hace que los solucionadores basados en gradientes queden atrapados en mínimos locales, especialmente en regímenes de alta dimensión.
• Escalabilidad: Estos métodos sufren costos computacionales de $O(d^3)$ por paso de gradiente debido a las comprobaciones repetidas de aciclicidad, lo que limita su escalabilidad a conjuntos de datos de alta dimensión ($d \gg 100$).
• Sobrecarga de Reentrenamiento: Los enfoques basados en puntuación existentes a menudo requieren un reentrenamiento recursivo de modelos generativos en subconjuntos marginalizados para identificar el orden de los nodos, creando cuellos de botella computacionales severos.

2. Metodología: Ordenación Topológica Score-Schur (SSTS)

Los autores proponen un paradigma desacoplado que traslada el cuello de botella desde la optimización no convexa hacia la estimación estadística de puntuaciones. La idea central es que la jerarquía causal deja una firma geométrica en la Matriz de Información Jacobiana de Puntuación (SJIM).

A. Fundamento Teórico

• Función de Puntuación y SJIM: Sea $s(x) = \nabla_x \log p(x)$ la función de puntuación. La SJIM, $I$, se define como el Hessiano negativo esperado de la log-densidad: $I = \mathbb{E}[-\nabla^2_x \log p(x)]$.
• Identificabilidad de Hojas (Teorema 3.1): En Modelos Aditivos de Ruido Gaussiano Lineales (ANM), las entradas diagonales de la SJIM codifican la jerarquía topológica. Específicamente, un nodo $l$ es una hoja topológica (sumidero) si y solo si su entrada diagonal $I_{ll}$ es mínima ($1/\sigma^2$).
• Marginalización Exacta vía Complemento de Schur (Teorema 3.2): Una vez identificada una hoja, eliminarla del grafo es matemáticamente equivalente a calcular el complemento de Schur de la SJIM con respecto a dicha hoja. Esto permite una eliminación recursiva sin reentrenar el modelo generativo.
• Extensión No Lineal y Brecha de Esperanza: En ANM no lineales, el operador de esperanza no conmuta con la inversión de matrices ($\text{Schur}(\mathbb{E}[H]) \neq \mathbb{E}[\text{Schur}(H)]$). Los autores derivan una Brecha de Esperanza ($\Delta$) proporcional a la covarianza del gradiente del mecanismo de ruido. Esta brecha introduce error estructural en configuraciones no lineales.

B. Algoritmo: Block-SSTS

Para abordar la brecha de esperanza y la varianza de muestras finitas, los autores introducen Block-SSTS:

1. Modelado Generativo: Entrenar una red de puntuación sin restricciones (por ejemplo, MLP) para estimar $s_\theta(x)$.
2. Prior de Jacobiano Disperso: Aplicar una penalización Group Lasso ($\ell_{1,2}$) a los pesos de la capa de entrada para inducir dispersión en el Jacobiano empírico, reduciendo la varianza de estimación en altas dimensiones.
3. Marginalización por Bloques: En lugar de la eliminación secuencial de nodos individuales, el algoritmo agrupa nodos hoja paralelos (aquellos con energías diagonales similares dentro de una tolerancia $\gamma$) y realiza una inversión de complemento de Schur por bloques.
   • Esto comprime la profundidad de extracción, truncando la acumulación de la brecha de esperanza no lineal.
   • Evita el costo de $O(Nd^3)$ de la parcheado exacto de covarianza muestra a muestra.
4. Poda de Aristas: Una vez extraído el orden topológico, el DAG se recupera mediante regresión dispersa estándar (Lasso) para cada nodo frente a sus antepasados permitidos.

3. Contribuciones Clave

1. Mapeo Algebraico de la Aciclicidad: Demostraron que la marginalización iterativa de nodos hoja es exactamente equivalente al complemento de Schur de la SJIM en ANM Gaussianos Lineales. Para ANM no lineales, caracterizaron el error de aproximación (Brecha de Esperanza).
2. Extracción Desacoplada: Eliminaron por completo el cuello de botella de la optimización no convexa. El descubrimiento causal se reformula como un problema de estimación estadística seguido de operaciones matriciales deterministas ($O(d^3)$ en total, pero solo una vez).
3. Escalabilidad hasta $d=1000$: Introdujeron Block-SSTS para manejar grafos no lineales de alta dimensión, logrando recuperación estructural hasta 1000 variables, un régimen donde los métodos de optimización continua fallan.
4. Corrección de Métricas: Argumentaron en contra del uso de la correlación de rangos (Kendall's $\tau$) para evaluar DAGs paralelos, proponiendo Violaciones de Aristas (EV) como la métrica rigurosa invariante a la ambigüedad topológica.

4. Resultados Experimentales

• Regímenes Lineales: SSTS logra cero violaciones de aristas causales para dimensiones hasta $d=1000$ en ANM lineales, validando la exactitud teórica.
• Regímenes No Lineales:
  • Eficiencia: En $d=50$, SSTS reduce el tiempo de ejecución de ~2700s (DAGMA) a 3.66s mientras logra una Distancia de Hamming Estructural (SHD) significativamente menor (2.6 vs 93.0).
  • Escalabilidad: En $d=1000$, SSTS completa la extracción en menos de 1 segundo, whereas los métodos continuos son computacionalmente intratables.
  • Compensación: Aunque SSTS introduce un pequeño error estructural debido a la brecha de esperanza no lineal, este permanece acotado por la varianza de estimación de muestras finitas de la red de puntuación.
• Datos del Mundo Real: En la red de señalización de proteínas Sachs ($d=12$), SSTS superó a DAGMA y Scalable SCORE tanto en precisión (SHD 13.8 vs 15.0/16.2) como en velocidad (6.62s vs 182s/56s).
• Estudios de Ablación:
  • Dispersión: Los priores Group Lasso son críticos para la estabilidad en regímenes con escasez de datos ($N=500, d=100$).
  • Tolerancia de Bloque: Una tolerancia de bloque moderada ($\gamma \approx 0.05$) truncó óptimamente la acumulación de errores sin violar la jerarquía causal.

5. Significado y Conclusión

Este trabajo reformula fundamentalmente el descubrimiento causal de un problema de optimización con restricciones a un desafío de estimación estadística. Al aprovechar las propiedades geométricas de la función de puntuación y las propiedades algebraicas del complemento de Schur, SSTS elude los óptimos locales y los problemas de escalabilidad inherentes a las penalizaciones de aciclicidad continuas.

Implicaciones:

• Teóricas: Establece un vínculo directo entre el ajuste de puntuación, la geometría de la información y la ordenación topológica.
• Prácticas: Permite el aprendizaje de estructuras causales en conjuntos de datos no lineales de alta dimensión (hasta $d=1000$) que anteriormente eran inaccesibles para los métodos de optimización continua.
• Limitaciones: La fidelidad del método en regímenes no lineales está finalmente limitada por la precisión de la estimación de la función de puntuación (varianza de muestras finitas) y la magnitud de la brecha de esperanza no lineal, en lugar de la convergencia de la optimización.

En resumen, SSTS ofrece una vía determinista y libre de optimización para el descubrimiento causal, demostrando que una vez eliminado el cuello de botella no convexo, el desafío principal se convierte en la estimación estadística de la geometría de la puntuación.