The sublevel Flood bifiltration: towards scalable 2-parameter persistent homology¶

会议: NeurIPS 2026
arXiv: 2610.05441
OpenReview: https://openreview.net/forum?id=BJ7STXgkS4
代码: https://github.com/MClemot/SLFlood
领域: 其他
关键词: 双参数持续同调、次水平集过滤、Flood 复形、拓扑数据分析、GPU 加速

一句话总结¶

提出次水平集 Flood 双过滤（sublevel Flood bifiltration），通过将基于紧凑地标 Delaunay 复形的覆盖机制推广至双参数空间，配合局部-极值掩码近似与 GPU 批处理张量计算，在大规模点集上实现了相比 Delaunay 双过滤数个数量级的加速，打破了双参数持续同调的计算扩展瓶颈。

研究背景与动机¶

拓扑数据分析（Topological Data Analysis, TDA）利用代数拓扑工具提取几何与点云数据中的多尺度拓扑特征（如连通分支、环与空洞），在表征学习、流形降维及时间序列分析等领域取得了显著成果。传统单参数持续同调主要依赖几何尺度参数（如 Rips 或 Čech 过滤中的膨胀半径 $r$），但这种基于距离尺度的几何过滤对离群噪点极度敏感——少数噪声点便会催生大量虚假拓扑特征，干扰对数据真实拓扑骨架的刻画。为解决这一痛点，多参数持续同调引入第二个参数（通常为密度或余密度函数 $\gamma$，如核密度估计 KDE 或测度距离 DTM），通过在几何尺度与密度阈值两个维度上协同过滤，极大地增强了拓扑特征对噪声的鲁棒性。

然而，双参数持续同调面临着严峻的计算复杂度诅咒。经典的次水平集偏移过滤在理论上性质优良，但在离散化计算时，次水平集 Rips 双过滤的单纯形数量随点数呈立方乃至指数级爆炸；而计算几何中性质最优的次水平集 Delaunay 双过滤虽然将复形规模压缩至 $O(n^{\lceil d/2 \rceil})$ 且保持拓扑等价，但由于其必须在全量输入点集 $X$ 上构建增量 Delaunay 复形，当点集规模达到数千至数万时，不仅生成复形耗时剧烈攀升，后续的多参数持续模分解（MMA）与极小表示（minimal presentation）算法更会因内存超限（OOM）而彻底崩溃。近期在单参数持续同调中提出的 Flood 复形虽然通过少量地标点的 Delaunay 复形覆盖全集实现了极佳的计算缩放与 GPU 加速，但其理论框架严格局限于单参数尺度，无法直接向双参数非平凡偏序关系泛化。

本文的切入角度是：双参数持续同调中的很多宏观几何拓扑特征并不需要无限细密的复形去解析，关键在于能否让定义在极小规模地标复形上的单纯形，精确感知全量点集在不同密度截断下的覆盖状态。核心 idea：构建次水平集 Flood 双过滤，将复形载体固定在稀疏地标集构筑的 Delaunay 复形上，通过判定单纯形凸包何时被过滤点集 $X_s$ 的欧氏球覆盖来定义双参数出现时间，并结合局部-极值点掩码分解与 GPU 批处理张量运算，将昂贵的代数拓扑约简转化为高并发几何距离计算，在严格保持交错稳定性的同时实现对百万级点云的高效拓扑表征。

方法详解¶

整体框架¶

次水平集 Flood 双过滤的整体流水线分为四个阶段：首先从输入点集 $X \subset \mathbb{R}^d$（附带余密度函数 $\gamma: X \to \mathbb{R}$）中通过最远点采样（FPS）提取稀疏地标点集 $L \subset X$，并构建紧凑的低维 Delaunay 复形 $\mathrm{Del}(L)$；其次，针对 $\mathrm{Del}(L)$ 中的每个单纯形 $\sigma$，利用极大余面外接球扩张与地标极值点构建候选点掩码子集 $X^\sigma$，将全量点搜索缩减为局部候选点查询；接着，将单纯形凸包均匀离散为重心坐标采样网格，在 GPU 上通过张量广播与累积行极小值、列极大值批处理操作快速提取每个单纯形的双分级（bigrades）Pareto 前沿；最后，将生成的轻量化多临界双过滤输入下游多参数模近似（MMA）工具，输出区间分解与矢量化表征（如 SCDR 或 MPL）供机器学习分类器使用。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：全量点集 X 与余密度函数 γ"] --> B["最远点采样提取地标集 L<br/>构建地标 Delaunay 复形 Del(L)"]
    B --> C["次水平集 Flood 双过滤构建<br/>基于 X_s 球覆盖定义单纯形插入尺度"]
    C --> D["极大余面与地标极值掩码<br/>局部与远端候选点分解构建 X^σ"]
    D --> E["重心网格离散化与 GPU 批处理<br/>张量累积极小值与 Pareto 前沿提取"]
    E --> F["输出：紧凑多参数持续模近似 MMA<br/>下游 SCDR / MPL 矢量化与分类"]

关键设计¶

1. 次水平集 Flood 双过滤构建与交错稳定性理论：以紧凑复形承载全量点覆盖

针对传统双过滤单纯形规模直接随点集大小 $n=|X|$ 爆炸的瓶颈，本文将过滤载体与点集规模解耦。对于输入点集 $X \subset \mathbb{R}^d$、地标集 $L \subset \mathbb{R}^d$ 及余密度函数 $\gamma: X \to \mathbb{R}$，令次水平子集为 $X_s = \gamma^{-1}((-\infty, s])$。次水平集 Flood 双过滤定义为在尺度 $(r,s)$ 下包含所有其凸包被 $X_s$ 的 $r$-球覆盖的地标单纯形： $$\mathcal{F}_{r,s}(X, L, \gamma) = \mathcal{F}_r(X_s, L) = \left\{ \sigma \in \mathrm{Del}(L) \mid \mathrm{conv}(\sigma) \subset \bigcup_{x \in X_s} B_r(x) \right\}$$ 当点集按余密度从小到大排序 $X=(x_1, \dots, x_n)$ 时，记 $X_{\le i} = (x_1, \dots, x_i)$ 且 $\gamma_i = \gamma(x_i)$。单纯形 $\sigma \in \mathrm{Del}(L)$ 对应的支撑双分级集合为： $$\phi(\sigma) = \left\{ \left( \mathrm{fl}(\sigma, X_{\le i}), \gamma_i \right), 1 \le i \le n \right\}, \quad \text{其中} \quad \mathrm{fl}(\sigma, X) = \max_{p \in \mathrm{conv}\sigma} \min_{x \in X} \mathrm{d}(p, x)$$ 其最小双分级集由 $\phi(\sigma)$ 的 Pareto 前沿给出。该双过滤是多临界的（multi-critical），虽然最坏情况下单个单纯形临界度可达 $|X|$，但由于复形整体仅依赖于 $|L|$（在实验中常取 100 至 1000），其实际单纯形数量远小于 Delaunay 双过滤。

在理论保障层面，作者证明了其对输入扰动具备强稳定性。设 $X, Y \subset \mathbb{R}^d$ 且余密度函数 $\gamma_X, \gamma_Y$ 均为 $\ell$-Lipschitz 连续，在固定地标集 $L$ 时，两个次水平集 Flood 持续模之间的交错距离（interleaving distance）满足： $$d_I(\mathbb{F}(X, L, \gamma_X), \mathbb{F}(Y, L, \gamma_Y)) \le \max\left( d_H(X, Y), \, \ell d_H(X, Y) + \|\gamma_X - \gamma_Y\|_\infty \right)$$ 当余密度由核密度估计（KDE，核为 $\ell_K$-Lipschitz，带宽为 $h$）给出时，点集 $\varepsilon$-扰动诱导的交错距离被界定在 $\varepsilon \max(1, 2\ell_K / h^{d+1})$ 内；若由测度距离（DTM，参数 $m \in (0,1]$）给出，交错距离上界为 $\varepsilon (1 + 1/\sqrt{m})$。这证明了该构造在度量扰动下的高度稳健性。

2. 极大余面与地标极值掩码策略：消除全量点扫描的局部化截断

在单参数 Flood 中，单纯形 $\sigma$ 的过滤值仅受其最小外接球（meb）在 $\sqrt{2}$ 膨胀范围内的点影响。然而在双参数设置下，距离单纯形非常遥远但余密度值极低的点可能会主导较大半径 $r$ 下的 Pareto 前沿，导致传统的局部几何邻域截断失效。若对每个单纯形全量扫描 $X$，计算量仍为 $O(|\mathrm{Del}(L)| \cdot |X|)$，难以承受。

本文提出了双路掩码分解机制，为每个单纯形 $\sigma$ 构造紧凑候选点子集 $X^\sigma$： $$X^\sigma = \bigcup_{\tau \in C(\sigma)} \mathrm{meb}_{\sqrt{2}}(\tau) \cup \bigcup_{l \in V(\sigma)} X^{\{l\}}$$ 其中左侧项结合了 $\sigma$ 的所有极大余面（maximal cofaces）$C(\sigma)$ 的 $\sqrt{2}$-膨胀外接球所包含的近邻点，专门捕获低半径、高余密度区域的紧密覆盖；右侧项收集了出现在 $\sigma$ 的余面中的所有地标顶点 $V(\sigma)$ 对应的极值贡献点集 $X^{\{l\}}$，其中 $X^{\{l\}} = \{x \in X \mid \nexists y \in X \text{ s.t. } y \neq x, \gamma(y) \le \gamma(x), \mathrm{d}(y,l) \le \mathrm{d}(x,l)\}$，专门承载大半径、低余密度区域的长程拓扑覆盖。

理论上，掩码逼近产生的双过滤 $\widetilde{\mathcal{F}}$ 保证为合法的双过滤，且与未截断的理想双过滤之间的交错距离满足 $d_I(\mathbb{F}, \widetilde{\mathbb{F}}) \le 2\Delta(L)$（其中 $\Delta(L)$ 为地标复形的最大单纯形直径）。实验证明，该掩码策略在将计算速度提升数十倍的同时，逼近误差几乎可忽略不计。

3. 重心网格离散化与 GPU 批处理张量计算：几何代数算子硬件加速

为了将连续单纯形凸包上的双参数覆盖判定转化为高通量并行计算，本文采用重心坐标采样将每个单纯形 $\sigma \in \mathrm{Del}(L)$ 的凸包离散化为规则网格点集 $P_\sigma \subset \mathrm{conv}(\sigma)$（每条边取 20 个等间距采样点，面取 210 点，四面体取 1540 点）。对于已按余密度升序排列的候选点集 $X^\sigma$，单纯形上的双分级对直接通过距离矩阵 $D_\sigma = \mathrm{d}(P_\sigma, X^\sigma) \in \mathbb{R}^{|P_\sigma| \times |X^\sigma|}$ 计算。

具体的 GPU 批处理张量操作包含两步核心算子： 1. 行内累积极小值：沿 $D_\sigma$ 的行方向（样本网格点对各点的距离）执行前缀最小值扫描 cummin，即求出 $\min_{x \in X_{\le i}^\sigma} \mathrm{d}(p, x)$，对应于子集逐步扩张时网格点到点集的最短距离衰减曲线； 2. 列间全局极大值与 Pareto 提取：在每列上取所有网格点的最大值 $\max_{p \in P_\sigma}$，得到当前前缀子集 $X_{\le i}^\sigma$ 完全覆盖该单纯形网格所需的最小半径 $r_i$。随后通过高效的 2D 比较算子滤除非支配点，提取出最终的 Pareto 最小双分级集 $\phi(\sigma)$。

该设计彻底规避了复杂的组合几何求交，将几何拓扑计算完全重构为稠密矩阵距离查询与规约操作，使得在高端 GPU（如 NVIDIA H100）上能够实现极高显存吞吐与张量并行加速。

实验关键数据¶

主实验¶

论文在两组经典基准上测试了所提方法的效率与分类性能：其一是用于评估多参数拓扑对低密度孔洞敏感度的合成“带噪瑞士奶酪”（Noisy Swiss Cheese, NSC）点集分类；其二是用于模拟含噪多孔介质的微观孔隙结构（rocks64）分类。在所有实验中，双过滤生成的 MMA 均被矢量化为 SCDR 并由 LightGBM 进行分类评估。

下表给出了在不同规模数据集上构建 MMA 的全集耗时（左侧）与从 MMA 进行下游分类的耗时（右侧，单位为秒），对比了不同地标数量下的 Flood 双过滤与基准 Delaunay 双过滤：

数据集	指标	Flood100	Flood300	Flood500	Flood1000	Delaunay（基线）	相比基线提速 / 突破
NSC-2D-5k	MMA / 分类耗时 (s)	38.3 / 17.4	85.3 / 32.3	142.7 / 49.1	312.6 / 57.8	1484.6 / 91.8	MMA 提速 38.8×
NSC-2D-20k	MMA / 分类耗时 (s)	91.3 / 11.5	150.2 / 12.9	219.3 / 19.4	416.4 / 38.3	OOM（显存溢出）	基线无法计算，本文保持秒级响应
NSC-3D-5k	MMA / 分类耗时 (s)	183.9 / 24.8	800.7 / 43.6	2309.3 / 53.0	13990.6 / 130.3	OOM（显存溢出）	解决 3D 拓扑组合爆炸
rocks64	MMA / 分类耗时 (s)	602.7 / 11.3	1086.7 / 16.1	1815.3 / 41.8	5925.6 / 70.3	OOM（显存溢出）	支持平均 13 万点高噪复杂体系

在真实世界 UCR 时间序列基准（采用 Takens 延迟嵌入映射至 $\mathbb{R}^3$ 并使用 DTM 作为余密度）的分类准确率如下所示：

数据集	序列长度	类别数	欧氏距离 (ED)	DTWc	单参数 Čech	Delaunay/SCDR	Flood/SCDR (本文)	结论
DPOC	80	2	0.717	0.717	0.699	0.659	0.732	优于 Delaunay 与单参数
DPTW	80	6	0.633	0.590	0.647	0.597	0.640	保持高水准
ACSF1	1460	10	0.540	0.640	0.740	0.400	0.750	相比 Delaunay 提升 +35.0%
KLC	4767	7	0.278	0.815	0.835	OOM	0.802	Delaunay 内存崩溃，本文稳定运行
CD	14773	2	0.445	0.610	0.555	OOM	0.640	支持万级超长时序嵌入
BH	18530	2	0.746	0.610	0.737	OOM	0.737	突破时序 TDA 规模天花板

消融实验¶

为了验证第 3.3 节提出的候选点掩码策略（Masked, M）相比全量点计算（Exact, E）在运行时间与逼近精度上的综合收益，作者在不同点集规模 $|X|$ 与地标数 $|L|$ 下评估了匹配距离 $d_{\mathrm{match}}(H_k)$ 与双过滤运行时间（见下表）：

| 点集规模 $|X|$ | 地标数 $|L|$ | 掩码运行时间 M (s) | 全量运行时间 E (s) | 运行时间加速比 | $d_{\mathrm{match}}(H_0)$ (M / E) | $d_{\mathrm{match}}(H_1)$ (M / E) | $d_{\mathrm{match}}(H_2)$ (M / E) | |---|---|---|---|---|---|---|---| | 1,000 | 100 | 0.14 | 0.39 | 2.8× | 0.17 / 0.12 | 0.04 / 0.05 | 0.05 / 0.02 | | 1,000 | 1,000 | 1.70 | 5.07 | 3.0× | 0.01 / 0.01 | 0.03 / 0.03 | 0.02 / 0.01 | | 20,000 | 100 | 0.55 | 5.03 | 9.1× | 0.05 / 0.05 | 0.08 / 0.10 | 0.10 / 0.11 | | 20,000 | 1,000 | 2.99 | 70.52 | 23.6× | 0.03 / 0.03 | 0.05 / 0.05 | 0.05 / 0.05 |

关键发现¶

规模可扩展性出现质的飞跃：传统 Delaunay 双过滤在点数达到 20,000 或 3D 网格点数达 69,000~130,000 时必定遭遇 OOM；而 Flood 双过滤耗时随点数增长极为平缓，由于复形拓扑大小仅由 $|L|$ 决定，成功将点云处理能力提升一个数量级以上。
掩码策略在超大点集下收益显著：在 $|X|=20,000, |L|=1,000$ 条件下，掩码近似将过滤生成时间从 70.52 秒大幅缩减至 2.99 秒（23.6 倍加速），同时高阶同调群的匹配距离与全量精确版完全一致（误差均为 0.05），证实了局部极大余面与极值点分解的完备性。
长序列时序拓扑表征实现零的突破：在 UCR 经典超长时序（如 BH 达 18,530 点，CD 达 14,773 点）的 Takens 嵌入上，Delaunay 双过滤完全无法运行，而 Flood 双过滤不仅能高效抽取双参数拓扑特征，还取得了与专业时序模型相媲美的分类准确率。

亮点与洞察¶

将复形组合爆炸转化为张量规约：传统 TDA 长期受制于 CPU 上的离散代数约简算子，本文通过“稀疏地标复形 + 全量点云球覆盖”思想，巧妙将计算重负转移为适合 GPU 大规模并行化的欧氏距离矩阵与前缀扫描，工程与理论结合精妙。
理论完备的局部-极值双路掩码：针对双参数下远距离低密度点破坏局部性的难题，创造性地将候选点划分为“几何邻域”与“地标极值集”，以 $2\Delta(L)$ 的紧致交错误差界换取了数十倍的实际提速。
对几何深度学习领域的强迁移价值：该算法可即插即用作为 3D 点云网络、图神经网络及科学计算中高阶多尺度拓扑特征的快速特征抽取器，且已开源提供 PyPI sublevel-flood 库，实用壁垒低。

局限与展望¶

受制于地标分辨率与维数灾难：复形分辨率严格受地标集合采样密度限制，小于地标间距的微细拓扑空洞可能被遗漏；同时，由于底层依赖 $\mathrm{Del}(L)$ 构建，当环境空间维度 $d > 10$ 时计算几何构网仍会遇到维度诅咒。
地标采样的动态自适应机制不足：当前主要依赖与密度解耦的贪心最远点采样（FPS），未来可探索密度自适应采样（如 DA-FPS），在低密度与复杂拓扑过渡区动态布设更多地标。
理论逼近界的紧致性仍有提升空间：定理 3 证明的 $2\Delta(L)$ 交错距离界在实际中显得过于悲观，未来可引入点集分布假设推导更贴合实际表现的严密理论上界。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将 Flood 覆盖思想拓展至双参数持续同调，提出极富创见的双路掩码理论与 GPU 张量流水线。
理论完备性: ⭐⭐⭐⭐⭐ 严格给出了度量扰动下的交错稳定性定理、KDE/DTM 稳定性特化以及掩码逼近误差上界。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖合成低维几何点云、多孔岩石微观结构、20 余个真实 UCR 时序数据集以及详尽的消融与 GPU 对比。
写作质量: ⭐⭐⭐⭐⭐ 结构清晰严谨，从几何直觉、代数定理到硬件张量实现过渡自然流畅。
价值: ⭐⭐⭐⭐⭐ 打破了多参数 TDA 走向工业级大规模点云与时序数据应用的性能瓶颈，开源工具链完善。