View source for Graphical time warping

{{Short description|Graphical time warping}}
'''Graphical time warping''' ('''GTW''') is a framework for jointly aligning multiple pairs of [[Time series|time series]] or sequences.<ref name="GTW">{{cite journal |last1=Wang |first1=Yizhi |last2=Miller |first2=David J |last3=Poskanzer |first3=Kira |last4=Wang |first4=Yue |last5=Tian |first5=Lin |last6=Yu |first6=Guoqiang |title=Graphical Time Warping for Joint Alignment of Multiple Curves |journal=Advances in Neural Information Processing Systems |date=2016 |volume=29 |url=https://proceedings.neurips.cc/paper/2016/hash/f0bbac6fa079f1e00b2c14c1d3c6ccf0-Abstract.html |publisher=Curran Associates, Inc.}}</ref> GTW considers both the alignment accuracy of each sequence pair and the similarity among pairs. On contrary, alignment with [[Dynamic time warping|dynamic time warping]] (DTW) considers the pairs independently and minimizes only the distance between the two sequences in a given pair. Therefore, GTW generalizes DTW and could achieve a better alignment performance when similarity among pairs is expected. 

One application of GTW is signal propagation analysis in time-lapse [[Biology:Microscopy|bio-imaging]] data, where the propagation patterns in adjacent pixels are generally similar. Other applications include [[Image processing|signature identification]], binocular stereo depth calculation, and [[Physics:Liquid chromatography–mass spectrometry|liquid chromatography–mass spectrometry]] (LC-MS) profile alignment in [[Biology:Proteomics|proteomics]] data analysis.<ref name="ncGTW">{{cite journal |last1=Wu |first1=Chiung-Ting |last2=Wang |first2=Yizhi |last3=Wang |first3=Yinxue |last4=Ebbels |first4=Timothy |last5=Karaman |first5=Ibrahim |last6=Graça |first6=Gonçalo |last7=Pinto |first7=Rui |last8=Herrington |first8=David M |last9=Wang |first9=Yue |last10=Yu |first10=Guoqiang |title=Targeted realignment of LC-MS profiles by neighbor-wise compound-specific graphical time warping with misalignment detection |journal=Bioinformatics |date=1 May 2020 |volume=36 |issue=9 |pages=2862–2871 |doi=10.1093/bioinformatics/btaa037|pmid=31950989 |pmc=7203744 }}</ref> Indeed, as long as the data are structured with inter-dependent time series/sequences, they can be analyzed with GTW.

GTW is able to model constraints or similarities between warping paths by transforming the DTW-equivalent shortest path problem to the [[Maximum flow problem|maximum flow problem]] in the [[Dual graph|dual graph]], which can be solved by most max-flow algorithms. However, when the data is large, these algorithms become time-consuming and the memory usage is high. An efficient algorithm, Bidirectional pushing with Linear Component Operations (BILCO),<ref name="BILCO">{{cite journal |last1=Mi |first1=Xuelong |last2=Wang |first2=Mengfan |last3=Chen |first3=Alex |last4=Lim |first4=Jing-Xuan |last5=Wang |first5=Yizhi |last6=Ahrens |first6=Misha B. |last7=Yu |first7=Guoqiang |title=BILCO: An Efficient Algorithm for Joint Alignment of Time Series |journal=Advances in Neural Information Processing Systems |date=6 December 2022 |volume=35 |pages=36270–36281 |url=https://proceedings.neurips.cc/paper_files/paper/2022/hash/eb5d9195b201ec7ba66c8e20b396d349-Abstract-Conference.html |language=en}}</ref> was developed to solve the GTW problem. It could achieve an average 10-fold improvement in both computational and memory usage compared with the state of art generic maximum flow algorithms in GTW applications.

== Joint alignment and GTW formulation ==
=== Joint alignment ===
Assume there are <math>N</math> pairs of time series <math>\{(x_n,y_n)|n = 1,2,...,N\}</math>, and each pair <math>{x_n,y_n}</math> has a corresponding warping path <math>P_n</math>. Some pairs of warping paths are known to be similar, and the set of all such pairs is denoted as <math>{(m,n)}</math>. For example, if <math>(m,n)</math> is in this set, warping paths <math>P_m</math> and <math>P_n</math> are similar. To optimize both the similarity between the aligned time series and the warping paths distances, the joint alignment problem is formulated as a minimization problem: 

<math>\min_{\{P_n| n = 1,2,...,N\}} \left( \sum_{n=1}^N cost(P_n) + \kappa \sum_{(m,n)\in Neib} dist (P_m,P_n)    \right)</math>

Here <math>cost(P_n)</math> denotes the distance between <math>x_n</math> and <math>y_n</math> after alignment with warping function <math>P_n</math>, <math>dist(P_m,P_n)</math> is the distance between warping paths <math>P_m</math> and <math>P_n</math> defined by the area of the region bounded by <math>P_m</math> and <math>P_n</math>, and <math>\kappa</math> is a hyperparameter balancing the time series alignment cost term and warping function distance term.

Notice that the similarity strength can be application-specific or user-designed. For different related warping paths pair <math>(m,n)</math>, we can set different parameters <math>\kappa_(m,n)</math>. For simplicity, here we use the unified hyperparameter <math>\kappa</math>.

The above minimization problem is intuitively formulated. However, it is not clear how to efficiently solve it in its original form, and a naïve enumeration of the warping paths leads to an [[NP-hardness|NP-hard]] problem. 

=== GTW formulation ===
[[File:Figure for Graphical time warping graph.png|thumb|GTW graph construction. The first row demonstrates the process for constructing GTW subgraph from one time-series pair, where the min-cut of GTW subgraph is dual to the shortest path of DTW graph, as well as the optimal warping path. The second row shows the process of adding cross edges between related time-series pairs, where the cross edges are colored green. The area size between adjacent warping paths is proportional to the number of edges cut among cross edges.]]

This minimization problem can be reformulated into a [[Minimum cut|minimum cut]] problem on a special graph termed GTW graph, where the minimum cut and the warping paths are equivalent.<ref name="GTW" /> The formulation could be described as:
* For the <math>n_th</math> time-series pair, construct its DTW graph. Then convert this DTW graph to its [[Dual graph|dual graph]], termed as GTW subgraph <math>G^n</math>. Set the capacities of reverse edges to be infinite.
* For each pair of similar warping paths <math>P_m</math> and <math>P_n</math>, linking the nodes of the same position in <math>G^m</math> and <math>G^n</math> by bidirected edges with capacity <math>\kappa/2</math>. Such edges are termed as cross edges.
* The constructed GTW graph, as shown in the figure, consists of <math>N</math> GTW subgraphs and cross edges.
* Using maximum flow algorithms to obtain the minimum cut of the constructed graph. The minimum cut within each GTW subgraph corresponds to one warping path.

=== Explanation of the equivalence ===
Each GTW subgraph <math>G^n</math> is the [[Dual graph|dual graph]] of the DTW graph representing the alignment of a single time-series pair. As a result, the cut within a GTW subgraph is dual to a warping path in DTW graph, and the profile alignment cost term can be represented by the cut cost within subgraphs. The infinite capacities of reverse edges are used to guarantee the monotonicity and [[Continuous function|continuity]] of warping paths. 

Cross edges constrain the similarity of warping paths and contribute to the distance term in the objective function. Notice that in a [[Minimum cut|minimum cut]] problem, the nodes would eventually be assigned to the source side or the sink side, and the final cut is defined by the edges between two sides. Each pair of mismatched nodes in <math>G^m</math> and <math>G^n</math> contribute to the distance between <math>P_m</math> and <math>P_n</math> and would result in an extra <math>\kappa/2</math> cost. Thus, the distance term could be represented by the cut cost in cross edges.

Therefore, the cut cost in the GTW graph corresponds to the cost terms in the objective function. Recalling the fact that the cut within each subgraph corresponds to the warping path of one time-series pair, the minimum cut of GTW graph corresponds to the optimal solution of warping paths in the joint alignment.

== Extension ==
=== Neighbor-wise Compound-specific Graphical Time Warping (ncGTW) ===
In [[Multiple sequence alignment|multiple sequence alignment]], the purpose is to align all sequences to a common reference. However, this common reference is usually unknown. In addition, there is also structural information among the sequences. Though GTW cannot be directly applied in these applications, a two-stage framework called ncGTW was built upon GTW to solve this problem. In the first stage, the prior structural knowledge among the sequences is utilized to obtain the warping functions. In the second stage, these warping functions help to jointly align all sequences to a virtual reference, which does not need to be explicitly specified. ncGTW was applied to LC-MS profile alignment problems in proteomics data and performed better than existing approaches.<ref name="ncGTW" />

== Efficient algorithm ==
=== Bidirectional pushing with Linear Component Operations (BILCO) ===
Solving the minimum cut problem on GTW graph through traditional maximum flow algorithms would take a long running time and large memory usage due to the large graph size, which limits the usage of GTW. BILCO algorithm utilizes two important properties of the joint alignment problem and achieves an average 10-fold improvement in both running time and memory usage. The two properties are:
* Joint alignment problem is a generalization of pairwise alignment and there are numerous DTW problems embedded in GTW graph. As each GTW subgraph is dual to a DTW graph, the maximum flow within each GTW subgraph can be solved in linear time through [[Dynamic programming|dynamic programming]].
* In many applications, a rough approximate solution of the warping paths can be estimated, which could serve as the initialization to accelerate the solving process.

[[File:Diagram for BILCO algorithm.png|thumb|The max-flow problem is analogized to pumping water from connected water tanks. Each GTW subgraph is a water tank and the flow is just the water flow. The algorithm iteratively operates ''Drain'' operations (drain water from water tank) and ''Discharge'' operations (exchange water between adjacent water tanks) until reaching the max-flow.]]

According to the first property, BILCO divides the flow exchange into two types: (1) Flow exchange within GTW subgraph; (2) Flow exchange across related GTW subgraphs. The process can be analogized to the process of [[Chemistry:Water pumping|pumping water]] from connected water tanks, and two types of flow exchange are termed ''Drain'' and ''Discharge''. To fully utilize such property, components (each component is a connected subset of GTW subgraph), rather than single nodes, are used as the operation unit. Both ''Drain'' and ''Discharge'' component operations can be implemented in linear time.

The second property inspires the bidirectional-pushing strategy. In this strategy, BILCO first segments the graph into two parts using the initial approximate solution, and then pushes excess/deficit in obtained sink/source parts, respectively. Compared with existing push-relabel-based maximum flow algorithms, BILCO significantly reduces redundant computation. It is worth noting that such a strategy could be also utilized to help accelerate other push-relabel-based algorithms.<ref name="BILCO" />

== Applications ==
=== Signal propagation analysis ===
In time-lapse bio-imaging data, signal propagation is a widely observed phenomenon in many cell types.<ref>{{cite journal |last1=Wang |first1=Yizhi |last2=DelRosso |first2=Nicole V. |last3=Vaidyanathan |first3=Trisha V. |last4=Cahill |first4=Michelle K. |last5=Reitman |first5=Michael E. |last6=Pittolo |first6=Silvia |last7=Mi |first7=Xuelong |last8=Yu |first8=Guoqiang |last9=Poskanzer |first9=Kira E. |title=Accurate quantification of astrocyte and neurotransmitter fluorescence dynamics for single-cell and population-level physiology |journal=Nature Neuroscience |date=November 2019 |volume=22 |issue=11 |pages=1936–1944 |doi=10.1038/s41593-019-0492-2 |pmid=31570865 |pmc=6858541 |language=en |issn=1546-1726}}</ref> Studying signal propagation may help uncover the function of these cells in both normal and pathological conditions. The propagation information could be derived from the warping paths by aligning pixels’ curves with a reference signal. Due to the low [[Physics:Signal-to-noise ratio (imaging)|signal-to-noise ratio]] in bio-imaging data, pairwise alignment methods usually lead to unsatisfactory results. Considering the spatial correlation of the signals, the similarity of warping paths between adjacent pixels can be utilized in GTW to enhance the alignment performance, which may lead to a more accurate calculation of propagation properties.

=== Depth extraction ===
In binocular stereo images, alignment technique can be used to extract depth information.<ref>{{cite book |last1=Ishikawa |first1=Hiroshi |last2=Geiger |first2=Davi |title=Computer Vision — ECCV'98 |chapter=Occlusions, discontinuities, and epipolar lines in stereo |series=Lecture Notes in Computer Science |date=1998 |volume=1406 |pages=232–248 |doi=10.1007/BFb0055670 |chapter-url=https://link.springer.com/chapter/10.1007/BFb0055670 |publisher=Springer |isbn=978-3-540-64569-6 |language=en}}</ref> The depth could be derived by the disparity of the same row between left image and right image. Since the depth of adjacent rows should be similar, GTW could be utilized to enhance the extraction result.

=== Signature identification ===
A signature usually contains multiple feature sequences, such as the x location, the y location, and the pressure.<ref>{{cite journal |last1=Okawa |first1=Manabu |title=Template Matching Using Time-Series Averaging and DTW With Dependent Warping for Online Signature Verification |journal=IEEE Access |date=2019 |volume=7 |pages=81010–81019 |doi=10.1109/ACCESS.2019.2923093|s2cid=195774867 |doi-access=free }}</ref> Those feature sequences are correlated, which indicates that when comparing two signatures, the distance measure obtained by pairwise alignment is not optimal. GTW could take the dependency between features into account and provide a better distance measure. 

=== Biological sequence alignment ===
In a biological sequence data set, it is common that there is some structural information among the sequences. In LC-MS data, the samples of nearby profiles tend to have similar patterns of [[Physics:Distortion (optics)|distortion]] and GTW is extended to jointly align these profiles. The same technique may also be applied to the joint alignment of other sequences. Structural information between sequences also exists in DNA and amino acids data. For example, the sequences between related species are more similar compared with sequences from more remotely related species. This information could be utilized by GTW.

==See also==
* [[Dynamic time warping]]
* [[Elastic matching]]
* [[Sequence alignment]]
* [[Multiple sequence alignment]]

== References ==
{{reflist}}

[[Category:Mathematical concepts]]
[[Category:Dynamic programming]]
[[Category:Machine learning algorithms]]
[[Category:Multivariate time series]]

{{Sourceattribution|Graphical time warping}}