Resumo Técnico: TriSearch

Formulação do Problema

O artigo aborda a otimização de triangulações para um poliedro $P$ de dimensão $d$. Uma triangulação decompõe $P$ em $d$-simplices que se encontram apenas em faces compartilhadas. O espaço de todas as triangulações, $\mathcal{T}(P)$, é exponencialmente grande, crescendo como $2^{O(|V(P)|\lceil d/2 \rceil)}$. Muitos objetivos naturais sobre este espaço, como minimizar o número de simplices ou o comprimento total das arestas, são NP-difíceis para $d \geq 2$.

O espaço de busca é estruturado como um grafo de flips $\mathcal{G}(P)$, onde os nós são triangulações e as arestas correspondem a flips bistelares. Um flip bistelar é um movimento local que substitui uma subtriangulação local realizada suportada por um circuito (um conjunto minimalmente afinamente dependente de vértices) por uma triangulação alternativa do mesmo conjunto de vértices. O desafio reside em navegar neste grafo: o conjunto de ações viáveis (circuitos flipáveis) é dependente do estado e muda após cada movimento, tornando a otimização combinatória neural padrão difícil, pois o espaço de ações não é fixo.

Metodologia: TriSearch

Os autores propõem o TriSearch, um framework de aprendizado por reforço (RL) que trata a otimização de triangulações como uma busca em um grafo de flips implícito.

1. Reformulação do Problema

O problema é modelado como um Processo de Decisão de Markov (MDP):

• Estado: Uma triangulação completa $\Delta$.
• Ação: Um flip bistelar viável atual $Z \in \mathcal{F}(\Delta)$.
• Recompensa: A melhoria na função objetivo $f$ induzida pelo flip ($R = f(\Delta) - f(\text{Flip}(\Delta; Z))$).
• Horizonte: Um número fixo de flips por episódio.

Crucialmente, o framework não pede à política que aprenda a validade geométrica. Em vez disso, uma rotina geométrica (baseada no TOPCOM) enumera todos os movimentos locais válidos (circuitos flipáveis) no estado atual. O papel da política aprendida é classificar esses movimentos válidos para identificar qual deles leva a uma otimização de longo alcance.

2. Representação de Ação Suportada por Circuito

Para lidar com o espaço de ações variável e dependente do estado, o TriSearch introduz uma nova representação de ação. Cada ação viável é codificada por:

1. O circuito de suporte $Z$.
2. A subtriangulação local realizada $\Delta^+(Z)$ contida na triangulação atual.

Esta representação codifica tanto o certificado de admissibilidade quanto a geometria local específica sendo substituída. Como os circuitos são definidos intrinsecamente, esta representação é agnóstica à dimensão e suporta diferentes aridades de flip.

3. Arquitetura Neural

A política utiliza uma arquitetura de dois estágios (Figura 2):

• Codificador Global: Uma Rede Neural de Grafos Equivariante (EGNN) processa o 1-esqueleto do grafo de triangulação $G(\Delta)$. Ela produz embeddings em nível de vértice $h^*$ que capturam o contexto geométrico global, respeitando simultaneamente as simetrias de movimento rígido.
• Ator (Classificador de Ação): O ator eleva os embeddings de vértice ao nível dos $d$-simplices maximais. Ele opera no grafo dual da triangulação (onde os nós são simplices) usando camadas de Rede Neural Simplicial (SNN). Para cada circuito viável $Z$, o ator agrega as características refinadas dos simplices sobre a subtriangulação local realizada $\Delta^+(Z)$ e as projeta em uma pontuação escalar.
• Cabeça de Valor: Um MLP leve estima o valor do estado $V(\Delta)$ usando embeddings de vértice agregados, utilizado para o treinamento de gradiente de política.

4. Estratégia de Treinamento

A política é treinada usando Otimização de Política Proximal (PPO) com Estimativa de Vantagem Generalizada (GAE).

• Generalização: O modelo é treinado em uma distribuição de poliedros pequenos e avaliado em poliedros maiores e não vistos.
• Exploração: Para evitar ficar preso em trajetórias subótimas, o treinamento inclui um bônus de expansão baseado em contagem $b_t = \beta N(\Delta_{t+1})^{-1/2}$, incentivando o agente a visitar novos estados no grafo implícito.
• Amostragem de Estado Inicial: Os estados iniciais são amostrados com pesos proporcionais a $N(\Delta_0)^{-1/2}$ para priorizar regiões pouco exploradas.

Contribuições Principais

1. Formulação RL para Triangulação: O artigo identifica a otimização de triangulações como RL em um grafo de flips implícito, utilizando rotinas geométricas para validade e uma política aprendida para seleção de movimentos.
2. Representação de Ação Suportada por Circuito: Uma interface agnóstica à dimensão que codifica ações através de seu circuito de suporte e subtriangulação local, permitindo que a política classifique movimentos com base em características geométricas e combinatórias locais.
3. Generalização Zero-Shot: O framework demonstra forte generalização de instâncias de treinamento pequenas para poliedros maiores com espaços de busca exponencialmente maiores.
4. Aplicação à Amostragem de Variedades Calabi-Yau: O framework é adaptado como um amostrador para triangulações Fine, Regular, Star (FRST) de poliedros reflexivos de 4D, que parametrizam variedades Calabi-Yau tridimensionais.

Resultados Experimentais

Os experimentos foram conduzidos em 3D e 4D em três objetivos: Mínimo de Simplices, Mínimo de Diâmetro e Mínimo de Peso.

• Desempenho de Otimização:

  • Em 3D, o TriSearch alcança uma lacuna relativa média de 0,16% contra o ótimo exato (encontrado por enumeração exaustiva do TOPCOM), superando significativamente linhas de base como NLS (8,97%), GREEDY e Recozimento Simulado.
  • Em 4D, onde a enumeração exaustiva é inviável, o TriSearch supera uma linha de base de enumeração do TOPCOM de $10^9$ passos em Mínimo de Simplices e Mínimo de Peso. Ele alcança uma lacuna relativa média de 1,43%, comparado a 9,09% para a próxima melhor linha de base (NLS).
  • Ablação: Remover informações simpliciais (usando apenas EGNN) ou a estrutura da subtriangulação (usando agregação simples) aumenta drasticamente a lacuna relativa, confirmando a necessidade da representação suportada por circuito.

• Amostragem de Variedades Calabi-Yau Tridimensionais:

  • Na tarefa de descobrir FRSTs distintos para poliedros reflexivos de 4D (lista Kreuzer-Skarke), o TriSearch supera os amostradores existentes do CYTOOLS (FRST Fast Sampler e MCMC).
  • Sob um orçamento fixo, o TriSearch descobre mais classes distintas de variedades Calabi-Yau tridimensionais, particularmente para números de Hodge mais altos ($h^{1,1} = 12, 16$), onde outros métodos sofrem com baixa eficiência de amostragem ou decaimento rápido nas taxas de sucesso.

Significado e Limitações

O artigo afirma que o TriSearch fornece um framework de busca unificado capaz de visar objetivos diversos (otimização de forma, minimização combinatória e descoberta topológica) sem exigir enumeração explícita do espaço de busca. Ele demonstra que políticas aprendidas podem navegar efetivamente em grafos complexos e restritos geometricamente, onde movimentos locais são matematicamente bem definidos, mas o espaço global é intratável.

Os autores reconhecem limitações:

• O método atualmente depende de uma rotina geométrica (TOPCOM) para enumerar flips válidos, o que é difícil de paralelizar.
• Não aborda atualmente casos onde o grafo de flips é desconectado (sabe-se que ocorre em dimensões $d \geq 6$).
• Na aplicação de amostragem CY, as triangulações iniciais são amostradas uniformemente; trabalhos futuros poderiam aprender a distribuição de FRSTs no espaço de altura para uma amostragem mais estratégica.

O trabalho sugere que esta estrutura de alto nível (busca em um grande espaço através de movimentos locais, matematicamente restritos) pode ser aplicável a outros domínios, como busca em árvores filogenéticas, pavimentação por losangos e problemas de desenovelamento de nós.