Technische Samenvatting: TriSearch

Probleemformulering

Het artikel behandelt de optimalisatie van triangulaties voor een $d$-dimensionaal polytoop $P$. Een triangulatie decomposeert $P$ in $d$-simplicen die uitsluitend op gedeelde vlakken samenkomen. De ruimte van alle triangulaties, $\mathcal{T}(P)$, is exponentieel groot en groeit als $2^{O(|V(P)|\lceil d/2 \rceil)}$. Veel natuurlijke doelstellingen over deze ruimte, zoals het minimaliseren van het aantal simplicen of de totale lengte van de randen, zijn NP-moeilijk voor $d \geq 2$.

De zoekruimte is gestructureerd als een flip-graf $\mathcal{G}(P)$, waarbij knopen triangulaties voorstellen en randen corresponderen met bistellair flips. Een bistellair flip is een lokale beweging die een gerealiseerde lokale subtriangulatie, ondersteund door een circuit (een minimaal affiene-afhankelijke verzameling van hoekpunten), vervangt door een alternatieve triangulatie van dezelfde verzameling hoekpunten. De uitdaging ligt in het navigeren door deze graf: de set van haalbare acties (flipbare circuits) is afhankelijk van de staat en verandert na elke beweging, waardoor standaard neurale combinatorische optimalisatie moeilijk wordt aangezien de actieruimte niet vaststaat.

Methodologie: TriSearch

De auteurs stellen TriSearch voor, een versterkingsleer (RL) raamwerk dat triangulatie-optimalisatie behandelt als een zoektocht op een impliciete flip-graf.

1. Probleemherformulering

Het probleem wordt gemodelleerd als een Markov-beslissingsproces (MDP):

• Staat: Een volledige triangulatie $\Delta$.
• Actie: Een momenteel haalbare bistellair flip $Z \in \mathcal{F}(\Delta)$.
• Beloning: De verbetering in de doelstellingsfunctie $f$ veroorzaakt door de flip ($R = f(\Delta) - f(\text{Flip}(\Delta; Z))$).
• Horizon: Een vast aantal flips per episode.

Cruciaal is dat het raamwerk het beleid niet vraagt om geometrische geldigheid te leren. In plaats daarvan enumereren een geometrische routine (gebaseerd op TOPCOM) alle geldige lokale bewegingen (flipbare circuits) in de huidige staat. De rol van het geleerde beleid is om deze geldige bewegingen te rangen om te bepalen welke leidt tot optimalisatie op lange termijn.

2. Actierepresentatie ondersteund door circuits

Om te handelen met de variabele en staat-afhankelijke actieruimte, introduceert TriSearch een nieuwe actierepresentatie. Elke haalbare actie wordt gecodeerd door:

1. Het ondersteunende circuit $Z$.
2. De geréaliseerde lokale subtriangulatie $\Delta^+(Z)$ die in de huidige triangulatie is opgenomen.

Deze representatie codeert zowel het certificaat van toelaatbaarheid als de specifieke lokale geometrie die wordt vervangen. Omdat circuits intrinsiek zijn gedefinieerd, is deze representatie dimensie-onafhankelijk en ondersteunt het verschillende flip-aryteiten.

3. Neuraal Architectuur

Het beleid maakt gebruik van een tweestapsarchitectuur (Figuur 2):

• Globale Encoder: Een Equivariante Grafische Neuronale Netwerk (EGNN) verwerkt het 1-skelet van de triangulatiegraf $G(\Delta)$. Het produceert embedding op hoekpuntniveau $h^*$ die globale geometrische context vastleggen terwijl het stijve bewegingssymmetrieën respecteert.
• Actor (Actiescorer): De actor tilt hoekpunt-embedding naar het niveau van maximale $d$-simplicen. Het werkt op de duale graf van de triangulatie (waar knopen simplicen zijn) met behulp van Simpliciale Neuronale Netwerk (SNN) lagen. Voor elk haalbaar circuit $Z` poolt de actor de verfijnde simplex-kenmerken over de gerealiseerde lokale subtriangulatie $\Delta^+(Z)$ en projecteert deze naar een scalair score.
• Waardekop: Een lichtgewicht MLP schat de staatwaarde $V(\Delta)$ met behulp van gepoolde hoekpunt-embedding, gebruikt voor policy gradient-training.

4. Trainingsstrategie

Het beleid wordt getraind met Proximal Policy Optimization (PPO) met Generalized Advantage Estimation (GAE).

• Generalisatie: Het model wordt getraind op een verdeling van kleine polytopen en geëvalueerd op grotere, onbekende polytopen.
• Exploratie: Om vastlopen in suboptimale trajecten te voorkomen, omvat de training een op telling gebaseerde expansiebonus $b_t = \beta N(\Delta_{t+1})^{-1/2}$, die de agent aanmoedigt om nieuwe staten in de impliciete graf te bezoeken.
• Steekproefneming van de beginstaat: Beginstaten worden gestoken met gewichten evenredig aan $N(\Delta_0)^{-1/2}$ om onder-ontdekte gebieden te prioriteren.

Belangrijkste Bijdragen

1. RL-formulering voor triangulatie: Het artikel identificeert triangulatie-optimalisatie als RL op een impliciete flip-graf, waarbij geometrische routines worden gebruikt voor geldigheid en een geleerd beleid voor de selectie van bewegingen.
2. Actierepresentatie ondersteund door circuits: Een dimensie-onafhankelijk interface dat acties codeert via hun ondersteunende circuit en lokale subtriangulatie, waardoor het beleid bewegingen kan rangen op basis van lokale geometrische en combinatorische kenmerken.
3. Zero-shot generalisatie: Het raamwerk toont sterke generalisatie aan van kleine trainingsinstanties naar grotere polytopen met exponentieel grotere zoekruimtes.
4. Toepassing op Calabi-Yau-steekproefneming: Het raamwerk wordt aangepast als een steekproefnemer voor Fine, Regular, Star (FRST) triangulaties van 4D reflexieve polytopen, die Calabi-Yau-driedimensionale variëteiten parametriseren.

Experimentele Resultaten

Experimenten werden uitgevoerd in 3D en 4D over drie doelstellingen: Min Simplicen, Min Diameter en Min Gewicht.

• Optimalisatieprestaties:

  • In 3D bereikt TriSearch een gemiddelde relatieve gap van 0,16% tegenover de exacte optimum (gevonden door exhaustieve TOPCOM-enumeratie), wat aanzienlijk beter presteert dan baselines zoals NLS (8,97%), GREEDY en Gesimuleerde Afkoeling.
  • In 4D, waar exhaustieve enumeratie onhaalbaar is, overtreft TriSearch een $10^9$-staps TOPCOM-enumeratie-baseline op Min Simplicen en Min Gewicht. Het bereikt een gemiddelde relatieve gap van 1,43%, vergeleken met 9,09% voor de naaste beste baseline (NLS).
  • Ablatie: Het verwijderen van simpliciale informatie (alleen EGNN gebruiken) of subtriangulatiestructuur (simpele pooling gebruiken) verhoogt de relatieve gap drastisch, wat de noodzaak van de door circuits ondersteunde representatie bevestigt.

• Calabi-Yau-driedimensionale variëteit steekproefneming:

  • Bij de taak om verschillende FRST's te ontdekken voor 4D reflexieve polytopen (Kreuzer-Skarke-lijst), overtreft TriSearch bestaande CYTOOLS-steekproefnemers (FRST Fast Sampler en MCMC).
  • Onder een vast budget ontdekt TriSearch meer verschillende Calabi-Yau-driedimensionale variëteitenklassen, vooral voor hogere Hodge-getallen ($h^{1,1} = 12, 16$), waarbij andere methoden lijden aan lage steekproefnemingsefficiëntie of snelle daling in succespercentages.

Betekenis en Beperkingen

Het artikel beweert dat TriSearch een unificerend zoekraamwerk biedt dat in staat is om diverse doelstellingen te richten (vormoptimalisatie, combinatorische minimalisatie en topologische ontdekking) zonder expliciete enumeratie van de zoekruimte. Het toont aan dat geleerde beleidslijnen effectief kunnen navigeren door complexe, door geometrie beperkte grafen waar lokale bewegingen wiskundig goed gedefinieerd zijn maar de globale ruimte onbeheersbaar is.

De auteurs erkennen beperkingen:

• De methode is momenteel afhankelijk van een geometrische routine (TOPCOM) om geldige flips te enumereren, wat moeilijk te paralleliseren is.
• Het adresseert momenteel geen gevallen waarbij de flip-graf onverbonden is (bekend om voor te komen in dimensies $d \geq 6$).
• In de CY-steekproefnemingtoepassing worden begintriangulaties uniform gestoken; toekomstig werk zou de verdeling van FRST's in de hoogteruimte kunnen leren voor strategischere steekproefneming.

Het werk suggereert dat deze hoog-niveau structuur (zoeken in een grote ruimte via lokale, wiskundig beperkte bewegingen) toepasbaar kan zijn op andere domeinen zoals fylogenetische boomzoektochten, ruitenvloeren en ontknoeiingsproblemen.