Graphical time warping (GTW) is a framework for jointly aligning multiple pairs of time series or sequences. Unlike dynamic time warping (DTW), which aligns each pair independently by minimizing only the distance between the two sequences in a given pair, GTW considers both the alignment accuracy of each sequence pair and the similarity among pairs. This joint optimization allows GTW to achieve better alignment performance when similarity among pairs is expected, generalizing DTW as a special case.
The framework is applicable to any data structured with inter-dependent time series or sequences. Applications include signal propagation analysis in time-lapse bio-imaging data, signature identification, binocular stereo depth calculation, and liquid chromatography-mass spectrometry (LC-MS) profile alignment in proteomics data analysis. In these settings, adjacent or related sequences often exhibit similar warping patterns, which GTW exploits to improve alignment quality.
Formulation
GTW formulates the joint alignment problem as a minimization over a set of warping paths. Given \(N\) pairs of time series \((x_n, y_n)\) for \(n = 1, 2, ..., N\), each pair has a corresponding warping path \(P_n\). Some pairs of warping paths are known to be similar, denoted by the set \(Neib\). The objective is to minimize:
\[\min_{\{P_n\}} \left( \sum_{n=1}^{N} cost(P_n) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
Here, \(cost(P_n)\) is the distance between \(x_n\) and \(y_n\) after alignment with warping function \(P_n\). The term \(dist(P_m, P_n)\) measures the distance between two warping paths, defined as the area of the region bounded by \(P_m\) and \(P_n\). The hyperparameter \(\kappa\) balances the alignment cost term and the warping function distance term. The similarity strength can be application-specific; for different related pairs \((m, n)\), different parameters \(\kappa_{(m,n)}\) can be set.
Relationship to Dynamic Time Warping
Dynamic time warping is a classical technique for aligning two time series by finding an optimal warping path that minimizes the cumulative distance. DTW treats each pair independently, solving a shortest path problem in a grid. GTW extends this by coupling multiple warping paths through a penalty on their pairwise distances. When \(\kappa = 0\), GTW reduces to independent DTW for each pair. When \(\kappa > 0\), the warping paths are encouraged to be similar, which is beneficial when the underlying sequences share common temporal distortions.
Solution via Maximum Flow
GTW transforms the DTW-equivalent shortest path problem into a maximum flow problem in the dual graph. The constraints or similarities between warping paths are modeled as additional edges or capacities. This dual graph formulation allows the joint optimization to be solved using standard max-flow algorithms. However, for large datasets, generic max-flow algorithms become time-consuming and memory-intensive.
To address scalability, an efficient algorithm called Bidirectional pushing with Linear Component Operations (BILCO) was developed specifically for GTW. BILCO exploits the structure of the dual graph and achieves an average 10-fold improvement in both computational time and memory usage compared to state-of-the-art generic maximum flow algorithms in GTW applications.
Applications
GTW has been applied in several domains where inter-dependent time series arise:
- Signal propagation analysis in time-lapse bio-imaging: Adjacent pixels often show similar propagation patterns, making GTW suitable for tracking wavefronts or cellular signals.
- Signature identification: Handwritten signatures can be treated as sequences; aligning multiple signatures jointly improves recognition.
- Binocular stereo depth calculation: Disparity maps from left and right images can be aligned with GTW to improve depth estimation.
- LC-MS profile alignment in proteomics: Chromatographic and mass spectrometric profiles from multiple samples benefit from joint alignment to correct retention time shifts.
These applications share the property that the sequences are not independent but exhibit spatial or temporal correlations that GTW exploits.