Exact Graph Learning via Integer Programming

1. Problema Abordado

El aprendizaje de la estructura de dependencia entre variables en sistemas complejos (conocido como aprendizaje de grafos o descubrimiento causal) es un problema central en ciencias médicas, naturales y sociales. El objetivo es inferir un grafo que represente las relaciones causales o de dependencia a partir de datos observacionales.

Los desafíos principales identificados en el estado del arte son:

• Suposiciones restrictivas: Muchos métodos requieren suposiciones fuertes sobre el proceso generador de datos (ej. distribuciones gaussianas o formas funcionales específicas).
• Algoritmos voraces (Greedy): Métodos basados en puntuación (score-based) como GES a menudo utilizan búsquedas voraces que no garantizan soluciones óptimas globales, quedando atrapados en óptimos locales.
• Sensibilidad a pruebas de independencia: Los métodos basados en restricciones (constraint-based) como PC o FCI dependen de la eliminación de aristas basada en pruebas de independencia condicional. Esto los hace sensibles a errores en el tamaño finito de la muestra y a violaciones de la "fidelidad" (near-faithfulness), donde correlaciones altas pueden llevar a la eliminación incorrecta de aristas.
• Escalabilidad de métodos exactos: Los métodos exactos existentes (como los basados en Programación de Respuesta de Conjuntos - ASP) sufren de una complejidad computacional factorial, limitándose a grafos muy pequeños (generalmente $d \le 6$ nodos).

2. Metodología Propuesta: GLIP

Los autores proponen GLIP (Graph Learning via Integer Programming), un marco de aprendizaje de grafos no paramétrico y exacto basado en programación entera mixta (MIP).

Enfoque Fundamental

En lugar de buscar un grafo mediante búsqueda voraz o satisfacción de restricciones paso a paso, GLIP reformula el problema como un problema de optimización global:
$$\min_{G \in \mathcal{G}_d} f(G, D_n)$$
Donde $f$ mide la discrepancia entre las separaciones gráficas del grafo candidato y las pruebas de independencia condicional (p-valores) obtenidas de los datos.

Innovación Clave: Codificación de Longitud Mínima

La contribución técnica más importante es una nueva forma de codificar las restricciones de separación gráfica (como $d$-separación o $m$-separación) dentro del programa entero:

• Codificación Tradicional (Eberhardt et al., 2025): Representa cada posible camino en el grafo con una variable. Esto genera un número de variables que escala factorialmente ($d!$), haciendo el problema intratable para $d > 6$.
• Codificación GLIP (Longitud Mínima): En lugar de rastrear caminos individuales, el método introduce variables enteras que representan la longitud del camino conector más corto entre dos nodos dado un conjunto de condicionamiento.
  • Si no existe un camino conector, la longitud se define como un valor máximo ($a_G + 1$).
  • Se utilizan restricciones lógicas (basadas en la concatenación de caminos y la estructura de los nodos) para asegurar que estas variables de longitud sean consistentes con la estructura de aristas del grafo.
  • Ventaja: El número de variables en el programa entero crece linealmente con el número de p-valores de entrada, en lugar de factorialmente. Esto permite escalar a grafos mucho más grandes.

Tipos de Grafos Soportados

El marco es versátil y soporta:

• Grafos Dirigidos Acíclicos (DAGs).
• Grafos Dirigidos Mixtos Acíclicos (ADMGs) y Grafos Dirigidos Mixtos (DMGs) con ciclos (bajo suposición lineal gaussiana).
• Grafos de Cadena (Chain Graphs).
• Permite el aprendizaje de clases de equivalencia de Markov y clases de equivalencia débil (weak equivalence).

3. Contribuciones Clave

1. Optimalidad Global Garantizada: GLIP proporciona una solución globalmente óptima para el problema de aprendizaje de grafos definido, a diferencia de los métodos voraces que solo ofrecen aproximaciones.
2. Enfoque No Paramétrico: No asume una distribución específica de los datos (como la normalidad), basándose únicamente en pruebas de independencia condicional.
3. Escalabilidad Mejorada: Gracias a la codificación de longitud mínima, GLIP puede manejar grafos con hasta 9-10 nodos para aprendizaje completo y hasta 14 nodos para aprendizaje débil, superando significativamente el límite de 6 nodos de los métodos anteriores basados en IP.
4. Flexibilidad y Modularidad: El objetivo de la función de puntuación puede ser cualquier función lineal en las variables del programa entero, permitiendo incorporar conocimiento de dominio (ej. "el nodo $v$ es un sumidero") o diferentes funciones de pérdida.
5. Herramienta de Software: Se libera el paquete R glip de código abierto, que implementa el método y soporta el aprendizaje de DAGs, ADMGs y grafos de cadena.

4. Resultados Empíricos

Los autores evaluaron GLIP comparándolo con métodos exactos (ASP) y aproximados (PC, FCI, NOTEARS, R2SORT) en datos simulados y conjuntos de datos de referencia (benchmarks).

• Rendimiento Computacional:
  • GLIP es aproximadamente un orden de magnitud más rápido que ASP para grafos pequeños ($d \in \{3, 4\}$).
  • Para grafos más grandes ($d \ge 6$), GLIP resuelve un 20-40% de las instancias dentro de un límite de tiempo de 600 segundos, mientras que ASP falla en resolver la mayoría de las instancias grandes ($d \ge 13$).
  • En el 50% de los casos, GLIP es más rápido; en el otro 50%, ASP es más rápido, sugiriendo que ejecutar ambos en paralelo es una estrategia práctica.
• Calidad del Aprendizaje:
  • GLIP iguala o supera el rendimiento de los métodos aproximados (PC, FCI, NOTEARS) en métricas como la Distancia Hamming Estructural (SHD) y la distancia de separación (SEP).
  • En datos simulados, GLIP demuestra una propiedad de corrección de errores: el grafo aprendido está más cerca de la verdad (ground truth) que los p-valores de entrada, lo que indica que el método puede corregir inconsistencias en las pruebas de independencia condicional debidas al ruido muestral.
  • En datos de referencia (ALARM, ASIA, CHILD, HEPAR2, SACHS), GLIP logra los mejores resultados en SHD para la mayoría de los conjuntos de datos, especialmente en configuraciones de aprendizaje débil ($k=1$).

5. Significado e Impacto

Este trabajo representa un avance significativo en el campo del descubrimiento causal y el aprendizaje de grafos:

• Puente entre Exactitud y Escalabilidad: Demuestra que es posible obtener soluciones óptimas globales para problemas de aprendizaje de grafos en tamaños de datos que antes se consideraban intratables para métodos exactos, sin sacrificar la generalidad (no paramétrico).
• Robustez: Al evitar la eliminación iterativa de aristas basada en umbrales fijos, GLIP es más robusto frente a violaciones de fidelidad y multicolinealidad, problemas comunes en sistemas reales.
• Marco General: La técnica de codificación de longitud mínima no está limitada a DAGs; es aplicable a una amplia clase de modelos gráficos (grafos mixtos, cadenas, separaciones $\delta, \mu, \sigma$), abriendo la puerta a futuras investigaciones en optimización exacta para estructuras causales más complejas.
• Aplicabilidad Práctica: La disponibilidad del paquete glip y la estrategia de "warm-start" (usar un grafo inicial rápido para mejorar con GLIP) hacen que el método sea viable para aplicaciones reales donde el presupuesto computacional es limitado pero se requiere la mejor solución posible.

En resumen, GLIP establece un nuevo estado del arte para el aprendizaje exacto de grafos, ofreciendo una alternativa robusta, escalable y teóricamente fundamentada a los métodos heurísticos y aproximados dominantes.