Graphical Time Warping for Joint Alignment of Multiple Curves
Dynamic time warping (DTW) is a fundamental technique in time series analysis for comparing one curve to another using a flexible time-warping function. However, it was designed to compare a single pair of curves. In many applications, such as in metabolomics and image series analysis, alignment is simultaneously needed for multiple pairs. Because the underlying warping functions are often related, independent application of DTW to each pair is a sub-optimal solution. Yet, it is largely unknown how to efficiently conduct a joint alignment with all warping functions simultaneously considered, since any given warping function is constrained by the others and dynamic programming cannot be applied. In this paper, we show that the joint alignment problem can be transformed into a network flow problem and thus can be exactly and efficiently solved by the max flow algorithm, with a guarantee of global optimality. We name the proposed approach graphical time warping (GTW), emphasizing the graphical nature of the solution and that the dependency structure of the warping functions can be represented by a graph. Modifications of DTW, such as windowing and weighting, are readily derivable within GTW. We also discuss optimal tuning of parameters and hyperparameters in GTW. We illustrate the power of GTW using both synthetic data and a real case study of an astrocyte calcium movie.
This paper presents the problem of simultaneously aligning multiple pairs of related time series using dynamic time warping. The input to the problem consists of a set of pairs of time series, and a graph encoding a neighborhood structure on the pairs. The objective is to minimize the sum of the warping distances for each pair of time series and the sum of distances between the warping paths of neighboring pairs. The proposed solution starts from a min cut/max flow algorithm to solve standard DTW, and extends it to solve the simultaneous multiple alignment problem. An extension to learn DTW hyper-parameters using penalized likelihood-like criteria is also introduced. Results are provided for one simulated data set and one real data set.
Technical quality: The discussion of the proofs in the paper is very brief, making the technical sections quite dense. The supplemental material fills in the details and the proofs appear to be correct. One issue that could be addressed more clearly in the paper and the supplemental is the need for infinite weight reverse edges in the dual graph. This is currently not explained at all in the main paper other than stating these edges are important and later empirically demonstrating that not including them leads to violations of DTW warping constraints.   The hyper-parameter tuning section was very brief and the algorithm is not clear. As the authors are using pseudolikelihood for some of the parameters the overall approach is certainly not proper maximum likelihood estimation. The supplemental material also describes additional ad hoc modifications introduced to help with convergence of the learning approach. This section of the paper could be cleaned up substantially.  The empirical evaluation is one of the weaker aspects of the paper. The evaluation lacks depth as it relies on only one type of synthetic data set and one real data set. For the synthetic data set, a quantitative error evaluation is performed relative to independent DTW alignments in terms of comparing the estimated and true warping paths. This evaluation shows that the proposed method outperforms DTW in terms of mean error, but no standard errors or other statistics are reported to allow assessment of statistical significance of the results.   The other experiment involves and application to cell imaging data. First, this application domain needs to be described as it may not be familiar to readers. Second, the analysis of this experiment is purely qualitative. It is clear that GTW shows increased spatial coherence relative to independent DTW, but beyond this, it is not clear that anything can be concluded from the results.   Novelty/originality: The GTW problem dealt with in this paper has not been well studied in the literature. There is significant work on jointly aligning multiple curves, or alignment to a common reference, but this problem is distinct in that it concerns simultaneous alignment of multiple pairs of curves with warping functions that are allowed to be related in complex ways through the GTW graph. The use of max flow-based methods for DTW is not novel, but the authors build on it significantly to yield exact solutions to the proposed GTW problem, which is a novel contribution.  Impact: This work could have a significant impact on application areas that make use of DTW. The ability to model interactions between warping paths using arbitrary graphs is quite powerful and allows for applications to spatiotemporal domains that could only be addressed using independent DTW previously. The authors might spend some more time in the paper describing more such application domains.        Clarity and presentation: Another weakness of the paper is that the writing is not particularly clear in terms of grammar and the technical sections are quite dense. Some of the figure including 1(c) and 2(a) showing primal and dual graphs are quite hard to interpret at first.