TriSearch: Learning to Optimize Triangulations via Bistellar Flips¶

会议: NeurIPS 2026
arXiv: 2605.30220
论文: arXiv
领域: 其他
关键词: 几何深度学习, 双星翻转, 剖分优化, 强化学习, 卡拉比-丘流形

一句话总结¶

TriSearch 将高维多胞体剖分优化建模为隐式翻转图上的强化学习任务，通过回路支撑的局部子单纯形复形表征动态翻转动作，结合等变图神经网络与单纯形对偶图卷积，在固定计算预算下实现了显著优于传统启发式与枚举法的全局寻优性能，并成功发现更多卡拉比-丘三折流形拓扑类。

研究背景与动机¶

凸多胞体（Polytope）的高维剖分（Triangulation）是将连续几何形体离散化为单纯形集合的基础运算，广泛支撑着网格生成、有限元数值模拟、计算机图形学以及超弦理论中卡拉比-丘（Calabi-Yau）三折流形的构造。然而，在 \(d>2\) 维空间中，剖分优化属于极其棘手的组合几何难题。给定多胞体 \(\mathcal{P}\)，其剖分状态空间 \(\mathcal{T}(\mathcal{P})\) 随着顶点数 \(|\mathcal{V}(\mathcal{P})|\) 和环境维度 \(d\) 呈双重指数爆炸增长，最坏情况下的数量上界可达 \(2^{O(|\mathcal{V}|^{\lceil d/2 \rceil})}\)；同时，判定一个剖分是否具有最少单纯形数量（\(d>2\)）或最小总边长（\(d \ge 2\)）均已被严格证明属于 NP-hard 问题。传统的精确枚举工具（如 TOPCOM）仅在顶点极少的小规模实例上可行，随着规模稍增便面临组合爆炸，而诸如 Gurobi、OR-Tools 等通用数学规划器也因无法高效建模高维单纯形复形的不相交覆盖约束而难以适用。

近年来神经组合优化在路径规划、图划分等问题上取得了显著进展，但主流的构造式自回归生成方法（如 Pointer Network 或自回归 Transformer）在剖分任务上遭遇了根本性的几何拓扑阻碍。在二维以上空间中，一旦在多胞体内部放置若干个 \(d\)-单纯形，剩余待剖分区域通常是非凸多面体，而判定一个三维非凸区域是否存在有效剖分本身就是 NP-hard 判定问题。近期代表性的构造式工作（如 CYTransformer）通过 Transformer 自回归预测单纯形序列，由于缺乏拓扑有效性的刚性约束，在生成高维候选时有效剖分率极低（例如在 Hodge 数 \(h^{1,1}=10\) 时合法率不足 50%）。另一方面，剖分空间内蕴着以双星翻转（Bistellar Flips / Pachner Moves）为局部转移算子的翻转图（Flip Graph）结构，但可翻转回路（Circuit）及其局部子剖分高度依赖当前状态，动作集合在每一步转移中动态变化且受到严苛的几何相容性制约，常规的局部搜索控制器无法直接对其进行参数化打分。

针对构造式生成破坏几何合法性、传统元启发式搜索缺乏长程规划视野的核心矛盾，TriSearch 提出了一种基于隐式翻转图强化学习的全新范式。该方法放弃让神经网络从无到有生成全局单纯形，而是将拓扑有效性交由底层严格的几何例程（TOPCOM）实时暴露局部可行翻转动作，让策略网络专注于在受限的局部动作空间中评估长程优化价值。核心 idea：将多胞体剖分优化建模为隐式翻转图上的强化学习搜索，通过极小仿射相关回路与其实现的局部子单纯形复形来统一表征翻转动作，结合全局等变几何编码与局部单纯形对偶图卷积，实现无须显式展开指数级空间的高维剖分高效寻优。

方法详解¶

整体框架¶

TriSearch 的整体执行流程涵盖“几何例程验证”、“两阶段分层图编码”、“回路支撑动作打分”与“环境状态转移与策略更新”四个紧密协同的阶段。输入为一个 \(d\) 维多胞体 \(\mathcal{P}\) 的几何顶点集 \(\mathcal{V}(\mathcal{P})\) 以及当前的一个合法初始剖分 \(\triangle\)。在每个决策步，系统首先通过几何内核严格枚举出当前剖分所包含的全部合法可翻转回路集合 \(F(\triangle)\)；随后，共享的等变图神经网络（EGNN）在多胞体的 1-骨架图上提取保持欧氏对称性的几何节点嵌入；接着，Actor 网络将顶点特征池化为各最高阶 \(d\)-单纯形特征，并在单纯形对偶图上通过高阶拉普拉斯算子完成特征传播；最后，策略网络聚合各可行回路所对应的局部子剖分特征，输出对所有候选双星翻转动作的概率分布并执行翻转，生成新的全局合法剖分 \(\triangle'\)。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：多胞体几何顶点集与初始剖分"] --> B["几何例程：TOPCOM 枚举可行回路动作集"]
    B --> C["两阶段分层图编码<br/>EGNN 顶点几何提取与单纯形对偶卷积"]
    C --> D["回路支撑动作表征<br/>聚合局部子剖分特征并打分动作分布"]
    D --> E["执行双星翻转更新剖分状态"]
    E --> F["探索增强策略优化<br/>状态访问计数奖赏与 PPO 轨迹更新"]
    F -->|未达翻转预算步数| B
    F -->|完成预算| G["输出：目标最优剖分或 FRST 集合"]

关键设计¶

1. 回路支撑动作表征：基于极小仿射相关集与局部子剖分参数化翻转空间 传统图强化学习通常假设动作空间固定映射到固定的节点或边集合，但在多胞体剖分中，原始动作是局部的双星翻转，其合法性依赖于动态拓扑结构。多胞体顶点集 \(\mathcal{V}(\mathcal{P})\) 的一个回路（Circuit）\(Z\) 是极小仿射相关子集，满足 \(\sum_{p_i \in Z} \lambda_i p_i = 0\) 且 \(\sum_{p_i \in Z} \lambda_i = 0\)。根据 Radon 分割定理，系数符号自然诱导了顶点的二划分 \(Z^+ = \{p_i \in Z: \lambda_i > 0\}\) 和 \(Z^- = \{p_i \in Z: \lambda_i < 0\}\)，进而唯一定义了凸包 \(\operatorname{ConvHull}(Z)\) 内部的两个互补核心子剖分 \(\triangle_{\mathrm{core}}^+(Z) = \{Z \setminus \{p\}: p \in Z^+\}\) 与 \(\triangle_{\mathrm{core}}^-(Z) = \{Z \setminus \{p\}: p \in Z^-\}\)。当回路凸包维度 \(r = \dim \operatorname{ConvHull}(Z) < d\) 时，回路核心必须借助当前剖分环境中的共同外连（Common Link）提升至全维单纯形：

\[ L_{\triangle}(Z) = \bigcap_{p \in Z^+} \operatorname{Lk}_{\triangle}(Z \setminus \{p\}), \quad \triangle^+(Z) = \triangle_{\mathrm{core}}^+(Z) * L_{\triangle}(Z), \quad \triangle^-(Z) = \triangle_{\mathrm{core}}^-(Z) * L_{\triangle}(Z) \]

由此，一个可翻转回路动作直接与其在当前剖分中具体实现的局部全维子剖分 \(\triangle^+(Z)\) 绑定。论文在数学上严格证明了给定剖分 \(\triangle\) 与回路 \(Z\) 下翻转后继状态的唯一性（命题 A.1），并保证翻转操作 \(\triangle' = (\triangle \setminus \triangle^+(Z)) \cup \triangle^-(Z)\) 在每一步均严格保持为合法几何剖分。这种表征使策略网络能够将注意力完全聚焦在局部被替换的单纯形块及其拓扑邻域上，摆脱了对全局单纯形排列顺序的依赖。

2. 两阶段分层图编码：EGNN 坐标几何感知与单纯形对偶图卷积 多胞体剖分在刚体旋转平移变换下具有不变性，且顶点索引的排列不改变内在几何结构。然而，单个顶点的特征无法直接判断高阶面之间的连通性与局部翻转代价。为此，TriSearch 设计了两阶段的分层图神经架构。第一阶段由共享编码器 \(\mathrm{Enc}_\kappa\) 构成，采用 \(E(n)\) 等变图神经网络（EGNN）处理多胞体 1-骨架图 \(G(\triangle) = (\mathcal{V}(\mathcal{P}), \mathcal{E}(\triangle))\)，在保留欧氏对称性的同时自适应融合空间绝对坐标差与拓扑边结构，为每个顶点生成兼具全局几何上下文的特征向量 \(\mathbf{h}_i^\star\)。第二阶段由 Actor 网络 \(\pi_\theta\) 专门处理高阶单纯形，首先通过最大池化将顶点特征提升至 \(d\)-单纯形级：\(\mathbf{g}_a^{(0)} = \operatorname{MaxPool}(\{\mathbf{h}_i^\star: p_i \in \mathcal{V}(\sigma_a)\})\)。随后，模型在剖分的对偶图 \(\hat{\mathcal{G}}(\triangle)\)（以 \(d\)-单纯形为节点、共享 \((d-1)\)-维共同面的单纯形为相邻边）上构建最高阶下对偶拉普拉斯算子 \(L_d = B_d^\top B_d\)（其中 \(B_d\) 为单纯形到其边界面的有向关联矩阵），并采用归一化的切比雪夫多项式进行单纯形卷积传播：

\[ \mathbf{G}^{(\ell+1)} = \sigma \left( \sum_{k=0}^{K_{\mathrm{act}}-1} T_k(\widetilde{L}_d) \mathbf{G}^{(\ell)} \Theta_k^{(\ell)} + \mathbf{b}^{(\ell)} \right) \]

经过 \(L_\pi\) 层对偶卷积后，单纯形嵌入 \(\mathbf{g}_a^{(L_\pi)}\) 充分捕获了局部空间拓扑配置。对于任意可行翻转回路 \(Z \in F(\triangle)\)，Actor 聚合该回路所实现的局部子剖分 \(\triangle^+(Z)\) 内的所有单纯形特征得到向量 \(\mathbf{z}_Z = \operatorname{MaxPool}(\{\mathbf{g}_a^{(L_\pi)}: \sigma_a \in \triangle^+(Z)\})\)，并通过线性投影打分 \(s_\theta(\triangle, Z) = W^\top \mathbf{z}_Z\)。该分层机制确保了模型能够精确敏感到替换 \(\triangle^+(Z)\) 所带来的局部曲率与结构重组冲击。

3. 探索增强策略优化：计数扩展奖励与欠探索初始状态重加权 在隐式翻转图上，由于局部极小值众多且目标函数（如最小单纯形数量或双对偶图直径）地形起伏剧烈，智能体极易在少数局部状态之间反复徘徊陷入次优。为此，TriSearch 引入了内在探索驱动机制与加权初始采样策略。首先，环境引入基于剖分状态历史访问计数的扩展奖励 \(b_t = \beta N(\triangle_{t+1})^{-1/2}\)，将单步总回报调整为 \(\tilde{r}_t = r_t + b_t\)（其中 \(r_t = f(\triangle_t) - f(\operatorname{Flip}(\triangle_t; Z_t))\) 为目标函数优化增益），以此激励策略主动探索翻转图中未曾触及的新拓扑区域。其次，针对训练集中预存的种子剖分集合 \(\hat{V}_\mathcal{D}\)，算法采用基于初始状态未充分探索度的加权采样，以概率正比于 \(N_\mathcal{P}(\triangle_0)^{-1/2}\) 抽取轨迹起始剖分，有效避免了策略在密集采样区域过度拟合。

一个完整示例¶

以三维空间（\(d=3\)）中 5 个处于一般位置的点构成的回路 \(Z = \{p_1, p_2, p_3, p_4, p_5\}\) 为例。根据仿射相关性，假设计算得到的 Radon 分割为正部 \(Z^+ = \{p_1, p_2, p_3\}\) 与负部 \(Z^- = \{p_4, p_5\}\)。几何上，三角形 \(p_1 p_2 p_3\) 与线段 \(p_4 p_5\) 在其内部交于唯一的 Radon 点。此时，核心子剖分呈现经典的三维 2-to-3 双星翻转结构：\(\triangle_{\mathrm{core}}^+(Z)\) 由 2 个共享公共三角形面 \(p_1 p_2 p_3\) 的四面体构成，而 \(\triangle_{\mathrm{core}}^-(Z)\) 则由 3 个围绕新内边 \(p_4 p_5\) 拼接的四面体构成。TOPCOM 检测到当前剖分中确实完整包含了这 2 个四面体，因而判定该回路可翻转。TriSearch 的 Actor 网络针对该回路，提取这 2 个四面体在对偶图卷积后的高维隐状态并进行最大池化，预测出该动作的得分 logit。一旦该动作被策略采样执行，系统仅需在局部删除这 2 个四面体并填入 3 个互补的新四面体，无需变动多胞体中其余数十甚至数百个四面体，以 \(O(1)\) 的局部修改完成了高维剖分状态的安全跃迁。

损失函数 / 训练策略¶

TriSearch 采用 PPO（近端策略优化）与 GAE（广义优势估计）对编码器参数 \(\kappa\)、Actor 参数 \(\theta\) 以及 Critic 参数 \(\psi\) 进行端到端联合训练。Critic 价值网络通过对全图顶点嵌入池化后接入 3 层 MLP，输出状态基准价值估计 \(V_\psi(\triangle_t) = \phi_V(\operatorname{MaxPool}(\mathbf{h}^\star))\)。训练总损失定义为：

\[ \mathcal{L} = \mathcal{L}_{\mathrm{policy}}(\theta, \kappa) + \alpha_{\mathrm{val}} \mathcal{L}_{\mathrm{value}}(\psi, \kappa) + \alpha_{\mathrm{ent}} \mathcal{L}_{\mathrm{entropy}}(\theta, \kappa) \]

其中，策略裁剪损失基于概率比率 \(\rho_t(\theta) = \frac{\pi_\theta(Z_t \mid \triangle_t)}{\pi_{\theta_{\mathrm{old}}}(Z_t \mid \triangle_t)}\) 和 GAE 优势估计 \(\hat{A}_t\)：

\[ \mathcal{L}_{\mathrm{policy}}(\theta, \kappa) = - \mathbb{E}_t \left[ \min \left( \rho_t(\theta) \hat{A}_t, \, \operatorname{clip}(\rho_t(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_t \right) \right] \]

价值函数损失为经验回报 \(\hat{R}_t\) 的均方误差 \(\mathcal{L}_{\mathrm{value}} = \mathbb{E}_t [(V_\psi(\triangle_t) - \hat{R}_t)^2]\)，超参数设定为裁剪因子 \(\epsilon=0.1\)、价值系数 \(\alpha_{\mathrm{val}}=0.5\)、熵正则系数 \(\alpha_{\mathrm{ent}}=0.001\)、折扣因子 \(\gamma=0.99\)、GAE 参数 \(\lambda=0.95\)，采用 Adam 优化器以学习率 \(10^{-4}\) 进行更新。

实验关键数据¶

主实验¶

论文在三维与四维未见多胞体上系统评估了 TriSearch 的优化能力。训练在小规模多胞体（顶点数 \(|\mathcal{V}| \in [8, 11]\)）上进行，并在翻转图规模呈指数扩大的全新测试多胞体（\(|\mathcal{V}| \in \{13, 14\}\)）上测试零样本泛化能力。实验对比了四种经典启发式算法（Greedy、DFS、BeFS、SA）、学习型元搜索控制器 NLS，以及基于 TOPCOM 的枚举基线。所有在线搜索方法均被严格限制在 500 步翻转预算内。在 3D 中基准值为完全遍历得到的精确全局最优，在 4D 中基准值为 \(10^9\) 步（100M 节点）TOPCOM 枚举与所有 500 步搜索算法中发现的最优解之组合基准。下表汇总了 500 步翻转后的平均相对误差（Relative Gap %, \(\downarrow\)）。

| 维度 \(d\) | 顶点数 \(|\mathcal{V}|\) | 优化目标 | 100M TOPCOM | Greedy | DFS | BeFS | SA | NLS | TriSearch (本文) | |---|---|---|---|---|---|---|---|---|---| | 3D | 13 | Min Simplices | — | 23.11±2.69 | 6.41±0.95 | 2.14±0.62 | 6.64±0.86 | 13.00±2.35 | 0.13±0.13 | | 3D | 13 | Min Diameter | — | 14.30±2.20 | 11.50±2.12 | 16.70±2.19 | 12.30±2.11 | 3.90±1.27 | 0.50±0.49 | | 3D | 13 | Min Weight | — | 10.56±0.85 | 7.18±0.69 | 3.54±0.58 | 11.42±0.92 | 8.12±0.99 | 0.13±0.05 | | 3D | 14 | Min Simplices | — | 23.51±2.50 | 12.07±2.05 | 6.17±1.30 | 12.60±1.51 | 14.25±2.18 | 0.00±0.00 | | 3D | 14 | Min Diameter | — | 15.40±1.82 | 16.50±1.10 | 20.60±1.71 | 18.20±1.12 | 6.10±1.32 | 0.00±0.00 | | 3D | 14 | Min Weight | — | 11.78±0.89 | 8.87±0.79 | 6.21±0.76 | 11.87±0.98 | 8.43±0.92 | 0.19±0.08 | | 3D | 综合平均 | 所有目标 | — | 16.44±0.85 | 10.42±0.61 | 9.23±0.67 | 12.17±0.57 | 8.97±0.69 | 0.16±0.09 | | 4D | 13 | Min Simplices | 2.41±0.94 | 17.25±4.68 | 20.01±6.30 | 19.24±5.17 | 6.93±2.14 | 11.29±3.12 | 0.00±0.00 | | 4D | 13 | Min Diameter | 1.00±0.97 | 20.00±0.00 | 20.00±0.00 | 20.00±0.00 | 19.00±0.97 | 13.00±2.13 | 3.00±1.60 | | 4D | 13 | Min Weight | 3.18±0.61 | 4.98±1.24 | 5.44±1.47 | 4.49±1.20 | 3.10±0.82 | 2.50±0.70 | 0.13±0.07 | | 4D | 14 | Min Simplices | 14.50±2.60 | 55.14±7.56 | 22.74±4.62 | 22.55±4.92 | 14.24±3.32 | 10.89±2.79 | 0.37±0.36 | | 4D | 14 | Min Diameter | 4.00±1.79 | 28.67±2.80 | 23.00±3.02 | 20.33±3.02 | 16.67±2.92 | 14.67±2.37 | 5.00±1.94 | | 4D | 14 | Min Weight | 4.49±0.60 | 13.10±1.67 | 5.42±1.04 | 5.25±1.04 | 2.10±0.64 | 2.22±0.60 | 0.10±0.07 | | 4D | 综合平均 | 所有目标 | 4.93±0.72 | 23.19±2.16 | 16.10±1.59 | 15.31±1.48 | 10.34±1.04 | 9.09±1.00 | 1.43±0.46 |

消融实验¶

为验证单纯形拓扑信息与局部子剖分表征对翻转决策的关键作用，论文在 4D 测试集（包含 \(|\mathcal{V}|=13\) 与 \(|\mathcal{V}|=14\) 的共 40 个多胞体）上进行了控制变量消融。对比变体包括：完整 TriSearch（基于单纯形对偶图卷积 SNN）、移除单纯形拓扑信息仅保留顶点 EGNN 编码的变体、以及彻底移除子剖分特征仅用全局平均池化与 MLP 决策的基准。结果如下表所示（500 步翻转后的相对误差 %, \(\downarrow\)）：

模型配置	最小单纯形数 (Min Simp.)	最小对偶直径 (Min Diameter)	最小总权重 (Min Weight)	说明
TriSearch 完整模型 (SNN)	0.185 ± 0.183	4.000 ± 1.265	0.137 ± 0.052	包含 EGNN 全局几何与单纯形对偶卷积
去除单纯形信息 (仅保留 EGNN)	8.977 ± 2.213	12.500 ± 1.531	3.112 ± 0.660	无法感知面共享的高阶拓扑连接，各目标显著恶化
去除子剖分结构 (Pooling + MLP)	15.121 ± 2.780	14.167 ± 1.558	6.992 ± 0.655	彻底丧失翻转动作的局部拓扑替换感知，性能垫底

关键发现¶

显著超越百万级传统枚举：在 4D 规模为 13 和 14 个顶点的最小单纯形数和最小总边长任务中，TriSearch 仅用 500 次翻转决策，就找到了优于 TOPCOM 进行 \(10^9\) 次（100M 节点）暴力枚举所发现的解，总体相对误差从枚举基线的 4.93% 压缩至 1.43%。
强大的跨尺度零样本泛化能力：模型仅在 \(8 \sim 11\) 个顶点的微型多胞体上训练，就能直接部署到搜索空间指数级激增的 13 和 14 顶点多胞体上，在 3D 上的综合相对误差仅为 0.16%，大幅领先所有启发式与元搜索基线。
Calabi-Yau 物理采样的实用突破：在来自 Kreuzer-Skarke 分类的 4D 反射多胞体微细正则星形剖分（FRST）寻找任务中，TriSearch 在 \(h^{1,1}\) 从 4 增至 16 的范围内均保持 100% 的 50 步命中率（而 TOPCOM BFS 和随机游走随维度增加骤降至接近 0%）。在实际卡拉比-丘三折流形采样中，TriSearch 的独立流形类发现速度呈现稳健的线性增长，在 \(h^{1,1}=16\) 时捕获了 97.4% 的已知拓扑类，显著击败了物理学界通用工具 CYTools 的 Fast Sampler（36.8%）与 MCMC（45.3%）。

亮点与洞察¶

严格几何解耦的动作设计：将复杂的连续拓扑有效性交由离线与实时的几何算子（Radon 划分与 Link 算子）保证，智能体绝不产生非法几何体，将学习负担纯粹集中于“可行操作的长程优劣判断”上，从数学源头消除了构造式深度模型频现的非法几何幻觉。
单纯形对偶图卷积的拓扑敏感性：将图神经网络从一阶骨架图推广到以 \(d\)-单纯形为节点、\((d-1)\)-维共享面为边的对偶图，使得回路局部的子剖分替换代价能够被精准捕捉。消融实验证明，缺少单纯形对偶连接将导致最小单纯形优化误差恶化近 50 倍。
内在探索奖励解决极值陷阱：在翻转图这一具有大量局部极值和死胡同的高离散空间中，结合访问频次倒数平方根的主动探索奖励能够有效防止策略陷入局部震荡，展现了强化学习探索机制在离散几何优化中的巨大威力。

局限与展望¶

底层回路枚举的串行瓶颈：方法依赖于外部几何例程（TOPCOM）枚举瞬时可行回路集合，该过程在超高维度或密集点集下难以大规模 GPU 并行化，构成了整体时间开销的主要瓶颈。
翻转图非连通性的理论约束：在 6 维及以上空间中，数学上已知存在非连通的翻转图案例（Santos 2005），基于单步翻转的局部连通搜索从理论上无法跨越孤立图分支，未来需探索更高阶或多步复合移动算子。
卡拉比-丘采样起始点的无偏优化：当前物理采样仍依赖于随机高斯高度向量均匀生成初始剖分，未来若能通过深度生成模型直接拟合目标 FRST 在高维高度空间中的概率分布，将进一步提升罕见拓扑结构的挖掘效率。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次将多胞体剖分优化严密重构为隐式翻转图上的强化学习任务，提出了基于回路与局部子剖分的通用动作表征]
实验充分度: ⭐⭐⭐⭐⭐ [覆盖 3D/4D 多重度量目标、跨尺度零样本外推、细粒度架构消融以及真实的卡拉比-丘超弦物理应用]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严密自洽，Radon 分割与外连上升表述极为清晰，动机与架构逻辑连贯]
价值: ⭐⭐⭐⭐⭐ [为高维计算几何、网格优化与数学物理中的指数级复杂离散构型搜索开辟了极具前景的深度强化学习新途径]