提出连续编辑距离,用于时间变化的拓扑图谱对齐与分析
Continuous Edit Distance, Geodesics and Barycenters of Time-varying Persistence Diagrams
- 基于编辑距离思想,结合替换与增删惩罚,定义可解释的测地线距离
- 实验证明对时间与空间扰动鲁棒,能恢复时间偏移并支持模式搜索
- 适合拓扑数据分析、时间序列对比与聚类任务的研究者使用
我们引入连续编辑距离(CED),一种用于时间变化持久性图谱(TVPDs)的测地线和弹性距离。CED通过将局部替换代价与受控的删除/插入惩罚相结合,扩展了编辑距离思想,由两个参数控制:α(时间错位与图谱差异之间的权衡)和β(间隙惩罚)。我们还提供了CED测地线的显式构造。在此基础上,提出了两种单调下降CED-Fréchet能量的实用中位数求解器,分别为随机型和贪心型。实验表明,CED对加性扰动(时间与空间)具有鲁棒性,可恢复时间偏移,并支持时间模式搜索。在真实数据集上,其聚类性能优于或相当于标准弹性相异度;基于CED中位数的聚类实现了更优分类结果。总体而言,CED为TVPD分析提供了原则性距离、可解释测地线与实用中位数,使直接在TVPD空间中实现对齐、比较、平均与聚类成为可能。项目提供C++实现以供复现:https://github.com/sebastien-tchitchek/ContinuousEditDistance。
原文摘要 · Abstract (English)
We introduce the Continuous Edit Distance (CED), a geodesic and elastic distance for time-varying persistence diagrams (TVPDs). The CED extends edit-distance ideas to TVPDs by combining local substitution costs with penalized deletions/insertions, controlled by two parameters: \(α\) (trade-off between temporal misalignment and diagram discrepancy) and \(β\) (gap penalty). We also provide an explicit construction of CED-geodesics. Building on these ingredients, we present two practical barycenter solvers, one stochastic and one greedy, that monotonically decrease the CED Frechet energy. Empirically, the CED is robust to additive perturbations (both temporal and spatial), recovers temporal shifts, and supports temporal pattern search. On real-life datasets, the CED achieves clustering performance comparable or better than standard elastic dissimilarities, while our clustering based on CED-barycenters yields superior classification results. Overall, the CED equips TVPD analysis with a principled distance, interpretable geodesics, and practical barycenters, enabling alignment, comparison, averaging, and clustering directly in the space of TVPDs. A C++ implementation is provided for reproducibility at the following address https://github.com/sebastien-tchitchek/ContinuousEditDistance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。