图形时间规整（GTW）是一种用于联合对齐多对时间序列或序列的框架。与动态时间规整（DTW）不同，后者通过仅最小化给定对中两条序列之间的距离来独立对齐每一对，GTW同时考虑每对序列的对齐精度以及各对之间的相似性。这种联合优化使得GTW在预期存在对间相似性时能够实现更好的对齐性能，并将DTW作为特例加以推广。
该框架适用于任何具有相互依赖的时间序列或序列结构的数据。应用包括延时生物成像数据中的信号传播分析、签名识别、双目立体深度计算，以及蛋白质组学数据分析中的液相色谱-质谱（LC-MS）谱图对齐。在这些场景中，相邻或相关的序列通常表现出相似的规整模式，GTW利用这一点来提高对齐质量。
公式化
GTW将联合对齐问题表述为对一组规整路径的最小化。给定\(N\)对时间序列\((x_n, y_n)\)，其中\(n = 1, 2, ..., N\)，每对对应一条规整路径\(P_n\)。某些规整路径对已知是相似的，用集合\(Neib\)表示。目标是最小化：
\[\min_{\{P_n\}} \left( \sum_{n=1}^{N} cost(P_n) + \kappa \sum_{(m,n) \in Neib} dist(P_m, P_n) \right)\]
这里，\(cost(P_n)\)是使用规整函数\(P_n\)对齐后\(x_n\)和\(y_n\)之间的距离。项\(dist(P_m, P_n)\)衡量两条规整路径之间的距离，定义为由\(P_m\)和\(P_n\)所围成区域的面积。超参数\(\kappa\)平衡对齐成本项与规整函数距离项。相似性强度可以是特定于应用的；对于不同的相关对\((m, n)\)，可以设置不同的参数\(\kappa_{(m,n)}\)。
与动态时间规整的关系
动态时间规整是一种经典技术，通过寻找最小化累积距离的最优规整路径来对齐两条时间序列。DTW独立处理每一对，在网格中求解最短路径问题。GTW通过成对距离的惩罚来耦合多条规整路径，从而扩展了DTW。当\(\kappa = 0\)时，GTW退化为每对的独立DTW。当\(\kappa > 0\)时，规整路径被鼓励保持相似，这在底层序列共享共同的时间畸变时是有益的。
通过最大流求解
GTW将等价于DTW的最短路径问题转化为对偶图中的最大流问题。规整路径之间的约束或相似性被建模为额外的边或容量。这种对偶图公式允许使用标准最大流算法求解联合优化问题。然而，对于大型数据集，通用最大流算法会变得耗时且占用大量内存。
为了解决可扩展性问题，专门为GTW开发了一种高效算法，称为双向推送与线性分量操作（BILCO）。BILCO利用对偶图的结构，在GTW应用中，与最先进的通用最大流算法相比，平均在计算时间和内存使用上实现了10倍的改进。
应用
GTW已应用于多个出现相互依赖时间序列的领域：
- 延时生物成像中的信号传播分析：相邻像素通常表现出相似的传播模式，使得GTW适用于跟踪波前或细胞信号。
- 签名识别：手写签名可以被视为序列；联合对齐多个签名可以提高识别率。
- 双目立体深度计算：左右图像的视差图可以使用GTW进行对齐，以改善深度估计。
- 蛋白质组学中的LC-MS谱图对齐：来自多个样本的色谱和质谱谱图受益于联合对齐，以校正保留时间偏移。
这些应用的共同特点是序列并非独立，而是表现出空间或时间相关性，GTW正是利用这些相关性。