Continuous Edit Distance between Time-varying Persistence Diagrams

Authors

sebastien Tchitchek (CNRS), Mohamed KISSI (CNRS), Julien Tierny (CNRS)

Keywords

Topological data analysis, persistent homology, time-varying data, elastic metrics

Abstract

We introduce the Continuous Edit Distance (CED), an elastic and geodesic metric for time-varying persistence diagrams (TVPDs). Being elastic, the CED goes beyond existing strategies for comparing temporal sequences of persistence diagrams based on Wasserstein distance integration (e.g., [61]), which require a perfect temporal alignment of the input sequences and which are therefore sensitive to temporal shifts or stretches. Being geodesic, in contrast to standard elastic metrics for time series, the CED brings the perspective of being amenable to the computation of geodesics and barycenters of TVPDs for future work. We describe how input temporal sequences of persistence diagrams can be converted into a TVPD and how to compute our metric via dynamic programming, yielding interpretable alignments between the input sequences. Empirically, the CED is robust to additive perturbations (both in time and birth-death values), recovers temporal shifts, supports temporal pattern search, and achieves MDS-based clustering performance comparable to or better than standard elastic distances on real datasets. A C++ implementation of our algorithms is available at https://github.com/sebastien-tchitchek/ContinuousEditDistance.