Sampling Triangulations and Calabi-Yau Threefolds with Autoregressive GNNs

The paper introduces `dualGNN`, a compact and efficient autoregressive graph neural network that leverages signed circuits from oriented matroid theory to uniformly sample fine, regular triangulations of convex polytopes, enabling the unprecedented generation of Calabi-Yau threefolds at high Hodge numbers with significantly reduced computational resources compared to prior methods.

The Gist

The Big Picture: Tiling a Floor Perfectly

Imagine you have a weirdly shaped floor (a polygon) made of a grid of tiles. Your job is to cover this entire floor with triangular tiles (triangulation) using only the grid points as corners.

But there are two strict rules:

1. No Gaps or Overlaps: Every single grid point must be a corner of a triangle, and the triangles must fit together perfectly. This is called being "fine."
2. The "Lift" Rule: Imagine you can lift each grid point up into the air to a different height. If you stretch a rubber sheet over the highest points and look at the shadow it casts back down on the floor, the pattern of triangles must match your floor plan. If your pattern can be made this way, it is called "regular."

The problem is that for complex shapes, there are astronomical numbers of ways to do this (sometimes more than the number of atoms in the universe). The goal of this paper is to create a computer program that can pick one of these valid patterns completely at random, without accidentally favoring some patterns over others.

The Problem with Old Methods

Previous methods were like trying to find a specific needle in a haystack by:

• Guessing randomly: Often hitting invalid shapes (gaps or overlaps).
• Walking step-by-step: Starting with one valid shape and making tiny changes (flips) to get a new one. This is slow, and the computer often gets "stuck" in one corner of the haystack, never seeing the rest.
• Being biased: Some methods were fast but only found the "easy" shapes, missing the rare, complex ones.

The Solution: dualGNN (The Smart Architect)

The author, Nate MacFadden, created a new AI model called dualGNN. Think of it as a Smart Architect that learns the rules of geometry so well it can build a perfect floor plan from scratch, every time.

Here is how it works, using an analogy:

1. The Blueprint (The Graph)
Instead of looking at the whole floor at once, the AI looks at a "dual graph." Imagine every triangle on the floor is a room, and if two triangles share a wall, there is a door between the rooms.

• The AI doesn't just see the doors; it sees a special label on every door called a "signed circuit."
• Analogy: Think of these labels as the "physics" of the wall. They tell the AI exactly how the triangles on either side relate to each other mathematically. This is the secret sauce that allows the AI to know if a shape is "regular" (can be lifted) or not.

2. Building Room by Room (Autoregressive)
The AI builds the floor one triangle at a time, like a game of Tetris.

• It picks a spot to place a new triangle.
• It checks the "physics labels" on the doors to make sure the new triangle fits perfectly with its neighbors.
• It "locks" that triangle in place and moves to the next.
• The Magic: Because it understands the "physics labels," it never makes a mistake that creates a gap or an overlap. It guarantees a valid floor plan every single time.

3. Learning to be Fair (Uniformity)
The biggest challenge is fairness. If you ask a human to draw random triangles, they usually draw simple ones. The AI needs to pick any valid triangle with equal probability.

• The author trained the AI on a few simple shapes first.
• Then, they tested it on huge, complex shapes it had never seen before.
• The Result: The AI was incredibly fair. It didn't just pick the easy shapes; it explored the whole "universe" of possibilities just as well as a perfect random number generator, but much faster than previous methods.

Why Does This Matter? (The String Theory Connection)

The paper applies this to String Theory, a branch of physics that tries to explain the universe.

• Physicists need to study Calabi-Yau threefolds. These are complex, multi-dimensional shapes that determine how particles behave in our universe.
• To find these shapes, physicists have to build them out of the triangular floor plans (triangulations) described above.
• The Problem: There are so many possible shapes that physicists can't check them all. They have to sample them. If their sampling method is biased (picking the same types of shapes over and over), they might miss a shape that explains a new particle or a new universe.
• The Breakthrough: The author used dualGNN to generate these shapes for very complex universes (specifically at a complexity level called $h^{1,1} = 86$ and even $128$).
  • Previous AI methods could only handle small, simple universes ($h^{1,1} \le 10$).
  • This new model is 1,000 times smaller and much faster to train than the previous best AI, yet it works on universes 10 times more complex.

Key Takeaways in Plain English

• Small but Mighty: The AI model is tiny (about the size of a small mobile app) and can run on a regular laptop.
• Zero-Shot Learning: You can train it on a square, and it will instantly know how to build perfect floors for a weird star-shaped polygon it has never seen. It learned the rules of geometry, not just memorized shapes.
• The "Lift" Test: The model uses a clever mathematical trick (oriented matroids) to instantly know if a shape is "regular" without having to do the heavy lifting calculation every time.
• No More Bias: It is the first method tested that can sample these complex shapes truly at random, ensuring physicists don't miss any potential realities.

In short, the author built a tiny, super-smart robot that learns the rules of tiling so well that it can explore the vast, infinite library of possible universes in string theory without getting lost or skipping pages.

Technical Summary

Technical Summary: Sampling Triangulations and Calabi-Yau Threefolds with Autoregressive GNNs

Problem Statement
The paper addresses the challenge of sampling fine, regular triangulations (FRTs) of lattice polytopes. This is a discrete, combinatorial problem characterized by four key difficulties:

1. Scale: The number of possible triangulations is astronomical (e.g., up to $10^{180}$ for polygons relevant to string theory applications).
2. Constraints: Sampling must satisfy local constraints (fineness/validity) and global constraints (regularity).
3. Symmetry: Polytopes possess $GL(d, \mathbb{Z}) \ltimes \mathbb{Z}^d$ invariance, requiring samplers to be robust against point relabeling and unimodular transformations.
4. Bias: Existing methods, including classical algorithms (e.g., random triangulations fast, flip walk) and learned approaches (e.g., CYTransformer), struggle with scale, generality, or uniformity. Specifically, previous learned methods often fail to generalize to unseen polytopes or produce biased samples that cluster in specific regions of the triangulation space.

In the context of string theory, this problem is critical for enumerating Calabi-Yau (CY) threefolds. The standard Batyrev construction maps Fine, Regular, Star Triangulations (FRSTs) of 4D reflexive polytopes to CYs. However, this map is many-to-one due to redundancy in 2-face restrictions. The authors' prior work established that generating uniform FRTs of 2D polygons (the "DNA" of the triangulation) allows for the direct construction of homotopy-inequivalent CYs, bypassing the exponentially redundant FRST space.

Methodology: dualGNN
The authors introduce dualGNN, an autoregressive message-passing Graph Neural Network designed to sample FRTs.

• Graph Representation: Instead of operating on the triangulation directly, dualGNN operates on a generalized dual graph $G$. Nodes represent candidate simplices (triangles in 2D), and edges connect simplices that share a facet with no overlapping interior.
• Edge Features (Signed Circuits): The core innovation is labeling edges with "signed circuits" ($\lambda$). These are combinatorial invariants from oriented matroid theory representing linear dependencies among the lattice points of adjacent simplices.
  • Mathematically, for a matrix $A$ of lattice points, $\lambda$ satisfies $A\lambda = 0$ and $\sum \lambda_i = 0$.
  • Crucially, these vectors encode the "secondary cone" constraints. A triangulation is regular if and only if its secondary cone is full-dimensional; thus, the signed circuits directly expose the regularity signal to the model.
  • The encoding is invariant under the orientation-preserving symmetry group $SL(d, \mathbb{Z}) \ltimes \mathbb{Z}^d$.
• Architecture:
  • Autoregressive Sampling: The model processes the graph in stages. At each step, it predicts a probability distribution over candidate simplices to add to a partial triangulation.
  • Masking: Once a simplex is sampled, incompatible simplices (those causing overlaps) are masked. This design guarantees that the output is always a fine triangulation (in 2D), as any uncovered region in 2D admits a valid completion.
  • Training: The model is trained on random prefixes of triangulations using cross-entropy loss. To optimize for uniformity, the authors employ a two-stage process: supervised pre-training followed by fine-tuning using REINFORCE with an entropy-maximizing reward.
• Generalization: The model is independent of the number of points ($N_{pts}$) in the polytope and has no fixed vocabulary, allowing it to generalize zero-shot to unseen polygons of different sizes and shapes.

Key Contributions

1. Novel Architecture: The introduction of a GNN that utilizes signed circuits as edge features to encode both the combinatorial structure (oriented matroid) and the regularity constraints of triangulations.
2. Uniformity and Generalization: The model achieves the most uniform sampling among tested methods, including classical baselines and transformer-based approaches. It generalizes zero-shot across different polygons, a capability lacking in previous learned methods like CYTransformer.
3. Efficiency: The model is small ($\sim92$k parameters), trains in $\sim7.5$ hours on a single consumer GPU, and runs on standard hardware (e.g., M1 MacBook Pro).
4. String Theory Application: The authors apply dualGNN to sample Calabi-Yau threefolds at significantly higher Hodge numbers ($h^{1,1}$) than previously possible with learned methods.

Results

• Regularity Classification: As a classifier, dualGNN achieves $>99\%$ accuracy in distinguishing regular from irregular triangulations, confirming that the circuit features successfully encode regularity.
• Sampling Uniformity (2D):
  • On a polygon with $\sim4 \times 10^5$ FRTs, dualGNN achieves lower KL divergence to the uniform distribution than all baselines (including flip walk and grow2d) after $10^6$ samples.
  • On a larger polygon ($[0,4]^2$) with $\sim7 \times 10^8$ FRTs, a model trained zero-shot on a different polygon achieves collision counts and KL divergence nearly indistinguishable from a true uniform sampler and flip walk, despite having no prior exposure to the target polygon.
  • Autocorrelation tests show dualGNN samples are consistent with a uniform distribution, whereas Markov-chain methods (flip walk) show significant correlation at low lags.
• High-$h^{1,1}$ Sampling:
  • $h^{1,1} = 86$: The model samples 2-face triangulations uniformly, enabling the generation of 10,000 distinct CYs. These samples show a mean "flop distance" (a metric of geometric diversity) of 130.2, significantly higher than the 45.7 observed with the biased random triangulations fast method.
  • $h^{1,1} = 128$: The model successfully samples 2-face triangulations for polygons with up to 35 points ($N_{pts}$), passing all available uniformity diagnostics (zero collisions, low KL divergence for smaller faces). This represents an order of magnitude improvement over previous learned methods (which were limited to $h^{1,1} \le 10$).
  • The resulting CY samples are demonstrably more diverse (higher flop distances) than those generated by standard biased methods.

Significance and Claims
The paper claims that dualGNN represents a significant advancement in sampling constrained combinatorial structures. By leveraging the mathematical structure of oriented matroids (via signed circuits), the model respects the problem's symmetries and learns the global regularity constraints directly from local edge features.

The authors emphasize that this approach allows for:

• Zero-shot generalization: A single model trained on a subset of polygons can sample FRTs for unseen, larger polygons.
• Scalability: The method scales to the largest polygons relevant to string theory applications (up to $N_{pts} \approx 40$ in the tested regime, with architecture supporting larger).
• Uniformity: It provides the first demonstration of uniform CY sampling at Hodge numbers significantly above $h^{1,1}=10$, validated at $h^{1,1}=86$ and passing diagnostics at $h^{1,1}=128$.

The authors modestly note that while the model is empirically uniform and passes all tested diagnostics, there are no theoretical guarantees of uniformity. Furthermore, the guarantee of generating fine triangulations is specific to 2D; while the architecture generalizes to higher dimensions, the fineness guarantee relies on a geometric property unique to 2D. The work suggests that this matroid-based encoding strategy could be applicable to other domains involving oriented matroids, such as linear programming and hyperplane arrangements, though the immediate application remains in string theory.