技術的概要：TriSearch

問題定式化

本論文は、$d$ 次元多面体 $P$ の三角分割の最適化を取り扱います。三角分割は、$P$ を共有面のみで接する $d$-単体へと分解します。すべての三角分割の空間 $\mathcal{T}(P)$ は、$2^{O(|V(P)|\lceil d/2 \rceil)}$ として成長する指数関数的に巨大な空間です。この空間における多くの自然な目的関数（単体の数や全辺長の最小化など）は、$d \geq 2$ に対して NP 困難です。

探索空間は、ノードが三角分割であり、エッジがバイステラリ・フリップに対応するフリップグラフ $\mathcal{G}(P)$ として構造化されています。バイステラリ・フリップとは、サーキット（頂点の最小アフィン従属集合）によって支えられた実現された局所部分三角分割を、同じ頂点集合に対する別の三角分割に置き換える局所的な移動です。課題はこのグラフをナビゲートすることにあります。実行可能な行動（フリップ可能なサーキット）の集合は状態に依存し、移動のたびに変化するため、行動空間が固定されていないため、標準的なニューラル組合せ最適化を困難にします。

手法：TriSearch

著者らは、三角分割の最適化を暗黙的なフリップグラフ上での探索として扱う強化学習（RL）フレームワークであるTriSearchを提案します。

1. 問題の再定式化

本問題はマルコフ決定過程（MDP）としてモデル化されます：

• 状態：完全な三角分割 $\Delta$。
• 行動：現在実行可能なバイステラリ・フリップ $Z \in \mathcal{F}(\Delta)$。
• 報酬：フリップによって誘発される目的関数 $f$ の改善度（$R = f(\Delta) - f(\text{Flip}(\Delta; Z))$）。
• ホライズン：エピソードあたりの固定されたフリップ数。

重要なのは、このフレームワークが方策に幾何学的妥当性の学習を求めない点です。代わりに、幾何学的ルーチン（TOPCOM に基づく）が、現在の状態におけるすべての有効な局所移動（フリップ可能なサーキット）を列挙します。学習された方策の役割は、これらの有効な移動をランク付けし、どの移動が長期的な最適化につながるかを特定することです。

2. サーキット支援型行動表現

可変かつ状態依存の行動空間を処理するために、TriSearch は新しい行動表現を導入します。各実行可能な行動は以下の要素で符号化されます：

1. 支援サーキット $Z$。
2. 現在の三角分割に含まれる実現された局所部分三角分割 $\Delta^+(Z)$。

この表現は、許容性の証明と、置換される特定の局所幾何学の両方を符号化します。サーキットは本質的に定義されるため、この表現は次元に依存せず、異なるフリップ次数をサポートします。

3. ニューラルアーキテクチャ

方策は 2 段階のアーキテクチャ（図 2）を使用します：

• グローバルエンコーダ：等変グラフニューラルネットワーク（EGNN）が、三角分割グラフ $G(\Delta)$ の 1-骨格を処理します。これは剛体運動対称性を尊重しつつ、大域的な幾何学的文脈を捉える頂点レベルの埋め込み $h^*$ を生成します。
• アクタ（行動スコアリング）：アクタは頂点埋め込みを最大 $d$-単体のレベルに持ち上げます。これは（ノードが単体である）三角分割の双対グラフ上で動作し、**単体ニューラルネットワーク（SNN）**レイヤを使用します。各実行可能なサーキット $Z$ に対して、アクタは実現された局所部分三角分割 $\Delta^+(Z)$ 全体にわたって洗練された単体特徴をプーリングし、スカラースコアに射影します。
• バリューヘッド：軽量な MLP が、プーリングされた頂点埋め込みを用いて状態価値 $V(\Delta)$ を推定し、方策勾配学習に使用されます。

4. 学習戦略

方策は、一般化アドバンテージ推定（GAE）を用いた**近接方策最適化（PPO）**で学習されます。

• 一般化：モデルは小さな多面体の分布上で学習され、より大きく未見の多面体上で評価されます。
• 探索：最適ではない軌道に陥るのを防ぐため、トレーニングにはカウントベースの拡張ボーナス $b_t = \beta N(\Delta_{t+1})^{-1/2}$ が含まれ、エージェントが暗黙的なグラフ内の新しい状態を訪問することを促します。
• 初期状態サンプリング：初期状態は、$N(\Delta_0)^{-1/2}$ に比例する重みでサンプリングされ、未探索領域を優先します。

主要な貢献

1. 三角分割のための RL 定式化：本論文は、三角分割最適化を暗黙的なフリップグラフ上での RL として特定し、有効性には幾何学的ルーチンを、移動選択には学習された方策を利用します。
2. サーキット支援型行動表現：行動をその支援サーキットと局所部分三角分割を通じて符号化する次元非依存インターフェースであり、方策が局所的な幾何学的および組合せ的特徴に基づいて移動をランク付けすることを可能にします。
3. ゼロショット一般化：このフレームワークは、指数関数的に大きな探索空間を持つより大きな多面体への、小さなトレーニングインスタンスからの強力な一般化を実証します。
4. カラビ・ヤウ多様体サンプリングへの応用：このフレームワークは、カラビ・ヤウ 3 多様体をパラメータ化する 4 次元反射多面体の Fine, Regular, Star (FRST) 三角分割のためのサンプリャとして適応されています。

実験結果

実験は、3 次元および 4 次元において、3 つの目的関数（最小単体数、最小直径、最小重み）に対して行われました。

• 最適化パフォーマンス：

  • 3 次元において、TriSearch は完全な TOPCOM 列挙によって見つかった正確な最適値に対して平均相対ギャップ**0.16%**を達成し、NLS（8.97%）、GREEDY、シミュレーテッド・アニーリングなどのベースラインを大幅に上回りました。
  • 4 次元では、完全な列挙が不可能なため、TriSearch は最小単体数および最小重みにおいて $10^9$ ステップの TOPCOM 列挙ベースラインを上回りました。平均相対ギャップは**1.43%**であり、次点のベースライン（NLS）の 9.09% と比較して優れています。
  • アブレーション：単体情報（EGNN のみを使用）または部分三角分割構造（単純なプーリングを使用）を除去すると、相対ギャップが劇的に増加し、サーキット支援型表現の必要性が確認されました。

• カラビ・ヤウ 3 多様体サンプリング：

  • 4 次元反射多面体（Kreuzer-Skarke リスト）に対する異なる FRST を発見するタスクにおいて、TriSearch は既存の CYTOOLS サンプリャ（FRST Fast Sampler および MCMC）を上回りました。
  • 固定された予算下で、TriSearch はより多くの異なるカラビ・ヤウ 3 多様体クラスを発見し、特にホッジ数が高い場合（$h^{1,1} = 12, 16$）において顕著でした。他の手法は低いサンプリング効率または成功率の急速な低下に苦しんでいました。

意義と限界

本論文は、TriSearch が明示的な探索空間の列挙を必要とせず、多様な目的（形状最適化、組合せ的最小化、トポロジカルな発見）をターゲットにできる統合された探索フレームワークを提供すると主張しています。これは、局所的な移動が数学的に明確に定義されているが、大域的な空間が扱いにくい、複雑で幾何学的に制約されたグラフにおいて、学習された方策が効果的にナビゲートできることを実証しています。

著者らは以下の限界を認めています：

• この手法は現在、有効なフリップを列挙するために幾何学的ルーチン（TOPCOM）に依存しており、並列化が困難です。
• 現在、フリップグラフが非連結である場合（$d \geq 6$ の次元で発生することが知られている）には対応していません。
• CY サンプリング応用において、初期三角分割は均一にサンプリングされます。今後の研究では、より戦略的なサンプリングのために、高さ空間における FRST の分布を学習することが考えられます。

この研究は、局所的かつ数学的に制約された移動を通じて大規模な空間を探索するという高レベルの構造が、系統樹探索、菱形タイリング、結び目の解消問題などの他の領域にも適用可能であることを示唆しています。