Resumen Técnico: TriSearch

Formulación del Problema

El artículo aborda la optimización de triangulaciones para un polítopo $P$ de dimensión $d$. Una triangulación descompone $P$ en $d$-simplices que se intersecan únicamente en caras compartidas. El espacio de todas las triangulaciones, $\mathcal{T}(P)$, es exponencialmente grande, creciendo como $2^{O(|V(P)|\lceil d/2 \rceil)}$. Muchos objetivos naturales sobre este espacio, como minimizar el número de simplices o la longitud total de las aristas, son NP-difíciles para $d \geq 2$.

El espacio de búsqueda está estructurado como un grafo de flips $\mathcal{G}(P)$, donde los nodos son triangulaciones y las aristas corresponden a flips bistelares. Un flip bistelar es un movimiento local que reemplaza una subtriangulación local realizada soportada por un circuito (un conjunto mínimamente afínmente dependiente de vértices) con una triangulación alternativa del mismo conjunto de vértices. El desafío radica en navegar este grafo: el conjunto de acciones factibles (circuitos flipables) depende del estado y cambia después de cada movimiento, lo que dificulta la optimización combinatoria neuronal estándar ya que el espacio de acciones no es fijo.

Metodología: TriSearch

Los autores proponen TriSearch, un marco de aprendizaje por refuerzo (RL) que trata la optimización de triangulaciones como una búsqueda en un grafo de flips implícito.

1. Reformulación del Problema

El problema se modela como un Proceso de Decisión de Markov (MDP):

• Estado: Una triangulación completa $\Delta$.
• Acción: Un flip bistelar factible actual $Z \in \mathcal{F}(\Delta)$.
• Recompensa: La mejora en la función objetivo $f$ inducida por el flip ($R = f(\Delta) - f(\text{Flip}(\Delta; Z))$).
• Horizonte: Un número fijo de flips por episodio.

Crucialmente, el marco no pide a la política que aprenda la validez geométrica. En su lugar, una rutina geométrica (basada en TOPCOM) enumera todos los movimientos locales válidos (circuitos flipables) en el estado actual. El papel de la política aprendida es clasificar estos movimientos válidos para identificar cuál conduce a una optimización a largo plazo.

2. Representación de Acciones Soportada por Circuitos

Para manejar el espacio de acciones variable y dependiente del estado, TriSearch introduce una representación de acción novedosa. Cada acción factible se codifica mediante:

1. El circuito soporte $Z$.
2. La subtriangulación local realizada $\Delta^+(Z)$ contenida en la triangulación actual.

Esta representación codifica tanto el certificado de admisibilidad como la geometría local específica que se está reemplazando. Dado que los circuitos se definen intrínsecamente, esta representación es agnóstica a la dimensión y soporta diferentes aridades de flips.

3. Arquitectura Neuronal

La política utiliza una arquitectura de dos etapas (Figura 2):

• Codificador Global: Una Red Neuronal de Grafos Equivariante (EGNN) procesa el 1-esqueleto del grafo de triangulación $G(\Delta)$. Produce incrustaciones a nivel de vértice $h^*$ que capturan el contexto geométrico global mientras respetan las simetrías de movimiento rígido.
• Actor (Calificador de Acciones): El actor eleva las incrustaciones de vértices al nivel de los $d$-simplices maximales. Opera sobre el grafo dual de la triangulación (donde los nodos son simplices) utilizando capas de Red Neuronal Simplicial (SNN). Para cada circuito factible $Z$, el actor agrupa las características de simplex refinadas sobre la subtriangulación local realizada $\Delta^+(Z)$ y las proyecta a una puntuación escalar.
• Cabeza de Valor: Una MLP ligera estima el valor del estado $V(\Delta)$ utilizando incrustaciones de vértices agrupadas, utilizada para el entrenamiento del gradiente de política.

4. Estrategia de Entrenamiento

La política se entrena utilizando Optimización de Política Próxima (PPO) con Estimación de Ventaja Generalizada (GAE).

• Generalización: El modelo se entrena sobre una distribución de polítopos pequeños y se evalúa en polítopos más grandes y no vistos.
• Exploración: Para evitar quedar atrapado en trayectorias subóptimas, el entrenamiento incluye una bonificación de expansión basada en conteo $b_t = \beta N(\Delta_{t+1})^{-1/2}$, que alienta al agente a visitar nuevos estados en el grafo implícito.
• Muestreo de Estado Inicial: Los estados iniciales se muestrean con pesos proporcionales a $N(\Delta_0)^{-1/2}$ para priorizar regiones poco exploradas.

Contribuciones Clave

1. Formulación RL para Triangulación: El artículo identifica la optimización de triangulaciones como RL en un grafo de flips implícito, utilizando rutinas geométricas para la validez y una política aprendida para la selección de movimientos.
2. Representación de Acciones Soportada por Circuitos: Una interfaz agnóstica a la dimensión que codifica las acciones a través de su circuito soporte y su subtriangulación local, permitiendo a la política clasificar movimientos basándose en características geométricas y combinatorias locales.
3. Generalización Zero-Shot: El marco demuestra una fuerte generalización desde instancias pequeñas de entrenamiento hasta polítopos más grandes con espacios de búsqueda exponencialmente mayores.
4. Aplicación al Muestreo de Calabi-Yau: El marco se adapta como un muestreador para triangulaciones Fina, Regular, Estrella (FRST) de polítopos reflexivos 4D, que parametrizan tresfoldos de Calabi-Yau.

Resultados Experimentales

Se realizaron experimentos en 3D y 4D a través de tres objetivos: Mínimo de Simplices, Mínimo Diámetro y Mínimo Peso.

• Rendimiento de Optimización:

  • En 3D, TriSearch logra una brecha relativa promedio del 0.16% frente al óptimo exacto (encontrado por enumeración exhaustiva de TOPCOM), superando significativamente a líneas base como NLS (8.97%), GREEDY y Recocido Simulado.
  • En 4D, donde la enumeración exhaustiva es inviable, TriSearch supera a una línea base de enumeración de TOPCOM de $10^9$ pasos en Mínimo de Simplices y Mínimo Peso. Logra una brecha relativa promedio del 1.43%, en comparación con el 9.09% de la siguiente mejor línea base (NLS).
  • Ablación: Eliminar la información simplicial (usando solo EGNN) o la estructura de subtriangulación (usando agrupación simple) aumenta drásticamente la brecha relativa, confirmando la necesidad de la representación soportada por circuitos.

• Muestreo de Tresfoldos de Calabi-Yau:

  • En la tarea de descubrir FRSTs distintos para polítopos reflexivos 4D (lista de Kreuzer-Skarke), TriSearch supera a los muestreadores existentes de CYTOOLS (Muestreador Rápido FRST y MCMC).
  • Bajo un presupuesto fijo, TriSearch descubre más clases distintas de tresfoldos de Calabi-Yau, particularmente para números de Hodge más altos ($h^{1,1} = 12, 16$), donde otros métodos sufren de baja eficiencia de muestreo o un rápido decaimiento en las tasas de éxito.

Significado y Limitaciones

El artículo afirma que TriSearch proporciona un marco de búsqueda unificado capaz de apuntar a objetivos diversos (optimización de forma, minimización combinatoria y descubrimiento topológico) sin requerir la enumeración explícita del espacio de búsqueda. Demuestra que las políticas aprendidas pueden navegar eficazmente grafos complejos restringidos por geometría donde los movimientos locales están matemáticamente bien definidos pero el espacio global es intratable.

Los autores reconocen limitaciones:

• El método depende actualmente de una rutina geométrica (TOPCOM) para enumerar flips válidos, lo cual es difícil de paralelizar.
• Actualmente no aborda casos donde el grafo de flips es desconectado (sabido que ocurre en dimensiones $d \geq 6$).
• En la aplicación de muestreo CY, las triangulaciones iniciales se muestrean uniformemente; trabajos futuros podrían aprender la distribución de FRSTs en el espacio de altura para un muestreo más estratégico.

El trabajo sugiere que esta estructura de alto nivel (buscar un espacio grande a través de movimientos locales, matemáticamente restringidos) puede ser aplicable a otros dominios como la búsqueda de árboles filogenéticos, teselado de rombos y problemas de desenredo.