Exact Topological Compliance: Generating Persistence-Equivalent Graphs¶
会议: NeurIPS 2026
arXiv: 2610.18856
代码: https://github.com/Aalto-QuML/ExactCompliance
领域: 学习理论
关键词: 持久同调, 拓扑图生成, 约束满足问题, 极小充分编码, 等价图类
一句话总结¶
首次对严格满足目标持久图（PD）的图生成问题展开首要原理研究，证明了局部迭代采样的内在不可能性极限，并提出了基于约束规划（CP）的极小充分全局可满足性编码，在合成与真实分子基准上实现了 100% 拓扑精准匹配。
研究背景与动机¶
拓扑结构在现实世界的图系统中扮演着主导功能机制的核心角色。无论是分子中决定稳定性和催化活性的环系与高阶空洞，还是脑神经网络中的信息流通道与输电网络中的连通冗余，持续同调（Persistent Homology, TDA）所提取的持久图（Persistence Diagrams, PDs）都已成为表征这些高阶拓扑演化规律的黄金标准。随着图生成模型（如基于自回归、变分自编码器及离散扩散模型）在几何化学与系统网络中的爆发，促使生成图具备指定拓扑特征成为了亟待解决的关键课题。
然而，现存的拓扑感知生成模型（如将离散扩散与 1-Wasserstein 持久图匹配损失结合的软正则化方案）从本质上无法提供拓扑精确性保证。此类软约束优化仅仅将采样分布推向宏观拓扑合理性，单图采样中仍会频繁发生联通分量合并或非预期环路过量生成的结构性漂移。对于环数敏感的药物分子设计（芳香环数直接决定化合物成药性）以及传感器网络覆盖漏洞检测等极度依赖精确拓扑不变量的严苛任务，软正则化生成的“近似相似”完全无法满足可用性要求。
造成这一困境的核心矛盾在于：持久图本身是一个有限的拓扑摘要，它将大量不同连通模式但同构/非同构的图投影到了同一个像空间；从给定的目标 PD 反推图结构本质上是从巨大的组合等价类中寻找满足所有拓扑约束的代表元。现存机器学习框架缺乏一套兼具可靠性（Soundness）与完备性（Completeness）的精确拓扑合规（Exact Topological Compliance）图生成理论。核心 idea：将拓扑合规生成问题建立在第一性原理之上，系统揭示局部贪心步进生成的理论不可行性极限，并基于欧拉示性数与跨阶段生成树连通性构建出针对任意置换等变顶点滤层的全局约束满足（CP）极小充分编码系统。
方法详解¶
整体框架¶
本文的目标是给定任意置换等变图滤层方案 \(\Phi\)（标准设置为度数滤层 \(\Phi=\text{deg}\)）及目标持久图 \((\mathcal{P}_0, \mathcal{P}_1)\)，严格生成满足 \(\mathcal{P}(H_\bullet^\Phi) = (\mathcal{P}_0, \mathcal{P}_1)\) 的简单无向图 \(H\)。作者系统构建了“局部迭代采样”与“全局约束满足求解”两套互补算法路径：局部方法基于步进式节点增删与配对，具备轻量级计算优势但受限于局部状态不可拓展性；全局方法则将持久图在各个滤层阶段所施加的顶点划分、连通性分支、圈环生成及死亡生命周期完全转化为整数与布尔可满足性约束。
整体生成流程与两类生成器决策路径如下所示：
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入目标持久图 (P0, P1) 与滤层方案 Φ"] --> B["预计算拓扑不变量<br/>活跃顶点集 / 存活连通分支数 / 累积环数"]
B --> C{"选择生成机制"}
C -->|局部轻量采样| D["局部迭代采样器 (Alg 1/2/3)<br/>按滤层阶段步进加点、连边、加环"]
C -->|全局精确求解| E["全局约束满足求解器 (CP-SAT)<br/>构建 6 类极小充分组合约束 C1-C6"]
D -->|存在无环死锁| F{"死锁检测"}
F -->|容量耗尽 Fail| D
F -->|成功终止| G["输出严格拓扑合规图 H<br/>P(H) = (P0, P1) 且 W1 = 0"]
E -->|SAT 约束求解| G关键设计¶
1. 局部迭代采样的正向扩展与内在不可能性定理 局部生成方法以归纳形式逐阶段构建子图序列 \(H_{-1} \subseteq H_0 \subseteq \dots \subseteq H_n = H\)。在每个滤层步 \(k\)，算法首先读取出生于 \(k\) 的顶点集，其次根据 0 维死亡配对 \((b,k)\) 在存活分支间添加分支消亡边，最后根据 1 维持久配对 \((k, \infty)\) 在分支内部添加独立环路。作者证明了若算法成功终止，所生成滤层必然具有可靠性与完备性；并在无环图（森林结构）上推导出局部生成必能成功终止的推论。
然而，局部生成的核心缺陷在于路径依赖导致的死锁：过早消耗图的分支环容量（Cycle Capacity \(\text{cap}^{\text{cyc}}(B) = \sum (|V(A)|(|V(A)|-1)/2 - |E(A)|)\)）会导致后续步骤无多余非边可连，产生不可行状态。作者给出了严谨的局部不可能性定理（Theorem 3.10），证明不存在任何仅依赖前序截断持久信息 \(\mathcal{P}^k(G_\bullet)\) 的局部在线算法能够覆盖所有完备等价类且处处保证成功生成。由于持久图对全局拓扑构型施加了不可分割的非局部牵引，必须转向全局联合求解。
2. 极小充分的全局约束满足规划编码（CP Formulation） 为了绕开局部贪心决策造成的死锁，作者将生成重构为一个纯粹的全局约束满足问题（CSP），由现代 CP-SAT 求解器联合求解。设待生成图的邻接矩阵下三角变量为 \(M_{ij} \in \{0,1\}\)，在每个过滤阶段 \(k\)，将活跃顶点 \(V_k = \{i: a_i \le k\}\) 划分为 \(cc_k\) 个抽象分槽（Slots），每个分槽对应子图的一个连通分支。模型系统建立了六大互相正交的约束族 \(\mathcal{C}_1 \sim \mathcal{C}_6\)： - \(\mathcal{C}_1\)（滤层对齐）：对于度数滤层，强制顶点度数严格匹配其出生时间，即 \(\sum_{j \neq i} M_{ij} = a_i\)； - \(\mathcal{C}_2\)（分槽划分）：保证每个活跃顶点在当前阶段恰好属于一个分支分槽 \(\sum_{c} x_{kcv} = 1\)； - \(\mathcal{C}_3\)（边-槽一致性）：禁止跨分槽连边，\(M_{uv} \le 1 - |x_{kcu} - x_{kcv}|\)； - \(\mathcal{C}_4\)（基于生成树的高效分槽连通性保证）：为避免全对最短路检查的 \(O(n^2)\) 复杂度，引入分槽内的生成树父节点指针 \(\pi_{kcij}\) 与深度标记 \(\ell_{kcv}\)，强制根节点出发的有向无环生成树覆盖分槽内所有节点，以线性约束消除局部假连通； - \(\mathcal{C}_5\)（欧拉示性数守恒环约束）：根据代数拓扑欧拉示性数不变量 \(|V| - |E| = \beta_0 - \beta_1\)，将累积环数强绑定到边数与分支数上： $\(\sum_{i<j, \, i,j \in V_k} M_{ij} - |V_k| + cc_k = \mathrm{cy}_k \quad \forall k\)$ - \(\mathcal{C}_6\)（最早出生存活分支计数）：约束每个分槽中最老顶点的出生时间，确保阶段 \(k\) 存活且出生于 \(b\) 的分支总数精确等于理论生存数 \(\alpha(k,b)\)。
作者严格证明了当 \(\Phi=\text{deg}\) 时，该六大约束系统构成了极小充分系统（Theorem 4.2）：缺少任何一个约束族，都能构造出满足其余五条但持久图不合规的伪反例（附录 G 对 6 个约束缺损分别给出了严格的反例证明）。
3. 通用置换等变图滤层函数的代数扩展 全局 CP 框架的另一大突破是完全解耦了拓扑骨架约束（\(\mathcal{C}_2 \sim \mathcal{C}_6\)）与具体的节点属性滤层（\(\mathcal{C}_1\)）。由于拓扑分支演化的判定仅依赖标量值 \(a_i\) 的离散偏序，针对任意置换等变滤层函数，只需替换 \(\mathcal{C}_1\) 的定义即可完成严格拓扑生成。作者形式化给出了多种高阶图不变量的等价代数整数编码： - 三角形与 \(k\)-团滤层：\(\sum_{j<l, j,l \neq i} M_{ij} M_{il} M_{jl} = a_i\)； - 聚类系数滤层：消除浮点除法，乘以标量常数 \(D\) 转化为有理整数约束 \(2 D t_i = p_i \max(1, d_i(d_i-1))\)； - 邻域平均度数滤层：\(\sum_{j \neq i} M_{ij} d_j = a_i \max(1, d_i)\)； - 紧密度中心性（Closeness Centrality）：通过辅助整数变量 \(\delta_{ij}\) 约束最短路差分递推关系，\(n-1 = a_i \sum_{j \neq i} \delta_{ij}\)； - 随机游走中心性（Katz Centrality 与 PageRank）：通过线性不动点方程系统将其转化为唯一解约束。
实验关键数据¶
主实验¶
实验在四套标准图生成基准上展开：Comm-20（密集双社区 SBM）、Planar（固定 64 节点的连通平面图）、SBM（大尺度随机块模型，最大节点数 187、边数达 1129）以及 ENZYMES（真实蛋白质接触图）。对比方法包括局部生成采样器（Alg. 3）、全局约束规划（CP）以及当前引入拓扑感知注意机制（TAM）与 1-Wasserstein 损失（PDM）的最强扩散基线 ConStruct+TAGG 与 DiGress+TAGG。拓扑保真度采用度数滤层下的成对平均 1-Wasserstein 距离 \(\bar{W}_1\)（0 表示完全精确合规）。
| 方法 | 指标 | Comm-20 | Planar | SBM | ENZYMES |
|---|---|---|---|---|---|
| Global (CP, 本文) | \(\bar{W}_1 \ (\downarrow)\) | 0.00 | 0.00 | 0.00 | 0.00 |
| 单图耗时 (s) | 0.30 | 16.35 | 654.8 | 6.85 | |
| 训练开销 (h) | 0 | 0 | 0 | 0 | |
| Local (Alg. 3, 本文) | 成功率 (%) | 100.0 | 100.0 | 15.0 | 99.1 |
| 单图耗时 (s) | 0.17 | 5.88 | 1465.0 | 6.94 | |
| 首次成功尝试次数 | 49.6 | 137.5 | 4583.5 | 431.5 | |
| ConStruct + TAGG | \(\bar{W}_1 \ (\downarrow)\) | 9.35 | 43.23 | 434.48 | 17.35 |
| 单图耗时 (s) | 0.88 | 4.73 | 17.11 | 4.92 | |
| 训练开销 (h) | 9.4 | 24.3 | 59.8 | 61.6 | |
| DiGress + TAGG | \(\bar{W}_1 \ (\downarrow)\) | 4.52 | 38.77 | 464.99 | 17.06 |
| 单图耗时 (s) | 0.90 | 5.30 | 23.16 | 5.94 | |
| 训练开销 (h) | 8.9 | 32.5 | 47.6 | 49.2 |
消融实验：度数滤层编码极小性验证与各约束反例¶
为验证六大约束族 \(\mathcal{C}_1 \sim \mathcal{C}_6\) 构成的极小充分性，作者在小图与随机图搜索空间中禁用了单个约束族，观察求解器产生的伪反例是否破坏了拓扑合规性。
| 禁用约束族 | 约束物理含义 | 破坏的拓扑现象与反例行为 |
|---|---|---|
| w/o \(\mathcal{C}_1\) | 顶点度数对齐 | 图中节点实际度数与分配度数错位（如将度数为 1 的节点连为 0 或 2 度），生成图的出生时序完全崩溃。 |
| w/o \(\mathcal{C}_2\) | 顶点单槽划分 | 节点被排除在分槽之外，欧拉示性数与生存数检查仅在部分子图生效，生成不相交的伪三角形结构。 |
| w/o \(\mathcal{C}_3\) | 跨槽无边一致性 | 两个理论独立的分槽之间出现跨槽边，拓扑上已融为一个大分支，但槽计数虚假满足，导致 0 维 PD 错位。 |
| w/o \(\mathcal{C}_4\) | 分槽生成树连通性 | 单个分槽内部发生非连通解离（如形成两个孤立三角形），缺乏无环生成树约束无法察觉分支断裂。 |
| w/o \(\mathcal{C}_5\) | 欧拉示性数环守恒 | 在 \(\text{ER}(8, 0.4)\) 反例中，各阶段分支数完全吻合，但中间阶段多产生或少产生独立圈，\(\mathcal{P}_1\) 环路出生时间错误。 |
| w/o \(\mathcal{C}_6\) | 最早出生存活数 | 在 \(\text{ER}(7, 0.3)\) 反例中，各层顶点与边总数吻合，但合并时错误吞并了更老的分支，导致 \(\mathcal{P}_0\) 死亡时间提前。 |
关键发现¶
- 软正则化扩散的拓扑漂移是结构性的：即使在推理阶段赋予神经扩散模型单图量身定制的测试图真实持久景观向量 \(\mu_{G_{\text{test}}}\)，神经网络仍会在 ENZYMES 等数据上过量生成 14~17 条边，导致 \(\beta_1\) 翻倍，或将多个不连通分支强行融合为单连通块，产生无法消除的 \(\bar{W}_1\) 结构间隙。
- 局部 vs. 全局互补机制：局部算法在简单稀疏图（Comm-20, Planar, ENZYMES）上极为迅捷（毫秒至数秒完成），但在连通分支长期共存的密集 SBM 图上因无环死锁导致成功率骤降至 15%；而全局 CP-SAT 能直接纵览全局分支拓扑，在 SBM 上达成 82.5% 的成功率且耗时减半。
- 等价类内部具备极高的组合多样性：在保持 \((\beta_0, \beta_1, \text{deg}, \text{density})\) 绝对不变（方差为 0）的前提下，CP 求解器采样的图在聚类系数、三角形计数和拉普拉斯谱范数上展现出了显著差异（如 Comm-20 上平均聚类系数差异达 0.064，三角形差异达 0.190），证实单持久图包含了丰富的结构自由度。
亮点与洞察¶
- 从启发式走向第一性原理：跳出了传统深度生成模型“通过设计损失函数逼近拓扑指标”的软优化范式，首次以数学严谨性定义了拓扑合规图生成的可靠性与完备性，为 TDA 拓扑表征学习设立了无标签噪声的精确基准。
- 欧拉示性数与生成树的极简组合转化：利用代数拓扑经典欧拉公式 \(|V| - |E| = \beta_0 - \beta_1\) 和线性生成树父指针编码，将极其晦涩的动态持续同调生命周期化解为了现代 SAT/CP 求解器高度兼容的多项式级规模约束。
- 混合实战落地策略：理论与实验给出了极具操作价值的实践法则：在稀疏且环较少的图上优先运行轻量级局部采样器（1000 次尝试以内）；当检测到死锁或密集大连通块时无缝回退至 CP 全局求解，兼顾极限效率与百分百精确性。
局限与展望¶
- 高阶复合单纯形扩展受限：当前算法限定在图结构（0 维连通分支与 1 维独立环），对于更高维单纯形复形（\(\ge 2\) 维空洞），由于单纯形边界算子需要高开销的矩阵约化算法（Smith 标准型），直接转化为整数规划会引发变量规模急剧膨胀。
- NP-Hard 求解的计算扩展瓶颈：全局 CP 编码规模虽然是节点的多项式阶 \(O(K \cdot cc_{\max} \cdot n^2)\)，但其底层求解等价于 SAT，在面对超大规模图（\(n > 150\) 且分支并发数高）时可能触发超时，未来亟待引入对称性破缺（Symmetry Breaking）与问题分解技术进行加速。
相关工作与启发¶
- vs TAGG (Park et al., 2025)：TAGG 将离散去噪扩散网络结合注意力偏置与 1-Wasserstein PDM 损失进行软引导，属于概率生成模型，但无法保证单样本拓扑无漂移；本文聚焦于严格组合生成，在 \(\bar{W}_1\) 上达成理论零误差。
- vs ConStruct (Madeira et al., 2024)：ConStruct 通过边吸收前向过程在每步去噪投影中施加平面性或无环性等单调边删除不变约束；本文发现其反向加边过程天然对应广义滤层，但 ConStruct 无法处理持续同调这种非单调分支合并与死亡的复杂全局不变量。
- vs 嵌入空间拓扑重构 (Belton et al., 2020; Curry et al., 2022)：传统持续同调逆问题多依赖欧氏空间坐标或测度变换（PHT）；本文针对纯抽象图，消除了坐标外在依赖，专注于本征置换等变滤层下的图同构等价类构建。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次从第一性原理探索无坐标抽象图的精确持久图合规生成，理论不可能性与极小充分编码均极具突破性。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖 4 种基准、完整极小性反例证明、丰富高阶滤层方案验证以及拓扑等价类多样性分析。
- 写作质量: ⭐⭐⭐⭐⭐ 数学定义严格规范，定理与证明逻辑链严密，算法伪代码与对照反例详实清晰。
- 价值: ⭐⭐⭐⭐⭐ 为拓扑深度学习提供了可控无噪的反例生成与基准检验工具，对严格拓扑敏感场景具有重要应用指导意义。