TrajGAT: A Graph-based Long-term Dependency Modeling Approach for Trajectory Similarity Computation

文章概述

轨迹相似性计算在许多时空应用中都很重要。传统的相似性度量算法的二次复杂度无法处理大规模数据集，而基于RNN的解决方案在长轨迹上的性能会急剧下降。为此，作者提出了一种新的基于图的方法，即TrajGAT，来显式地建模层次空间结构，提高长轨迹相似度计算的性能。TrajGAT主要包括两个模块：轨迹图构造和轨迹编码。对于图的构造，TrajGAT首先使用PR quadtree构建整个空间区域的层次结构，然后基于原始记录和quadtree的叶节点为每条轨迹构造一个图。对于轨迹编码，作者将Transformer中的自注意替换为图注意力，并设计了一个编码器来表示生成的图轨迹。使用这两个模块，TrajGAT可以捕获轨迹的长期依赖关系，同时减少Transformer的GPU内存使用。最后在两个真实数据集上的实验表明，TrajGAT不仅提高了长轨迹上的性能，而且在混合轨迹上的性能显著优于最先进的方法。

预备知识

给定大小为$N$的轨迹集$\mathcal{T}$和轨迹相似性度量$f(\cdot ,\cdot )$。每条轨迹$T\in \mathcal{T}$为二维元组序列，即 $T=\left[X_1,\dots ,X_t,\dots \right],X_t=(la{t}_t,lo{n}_t)$。对于任意两条轨迹 $T_i,T_j\in \mathcal{T}$，$f\left(T_i,T_j\right)$度量了轨迹$T_i$和$T_j$的相似度。

本文的任务是在相似性函数$f(\cdot ,\cdot )$下计算$\mathcal{T}$中一对临时轨迹的相似性。然后现有大多数流行的相似度度量计算一对轨迹间的相似度会导致二次时间复杂度。而现有的基于DL的方法在长轨迹上会导致严重的性能下降。

为此，本文希望学得一个相似度近似函数$g(.,.)$，使得其计算高效的同时在长轨迹和短轨迹上的差异$\left|f\left(T_i,T_j\right)-g\left(T_i,T_j\right)\right|$被最小化。

TrajGAT

框架概述

TrajGAT的框架如下图所示，它是一个基于图的度量学习框架。TrajGAT包含三大核心组件：

• 层次化结构建模：基于Point-Region (PR) quadtree来构建区域$\mathcal{A}$的层次结构$\mathcal{H}$。
• 基于图的轨迹编码：利用$\mathcal{H}$的树结构将每条轨迹$T$转换为图$T^g$。
• 基于度量学习的优化：利用rank loss来拟合轨迹对之间的相似性，并提出归一化方法使监督信息更容易学习。

度量是指学习一个度量函数（metric function），该函数可用于计算输入数据之间的距离或相似性。该函数可以从训练数据中自动学习，以便在输入空间中更好地捕获数据点之间的语义关系。

层次结构建模

TrajGAT利用PR quadtree来建模层次化的空间信息，具体方法是递归的将区域进行四等分，直至没有区域的叶子节点数超过阈值$\delta$。在下面的示例中$\delta =2$，整个区域被分为3层。

为了整合层次信息进行轨迹编码，作者对$\mathcal{H}$进行了预训练以获取网格单元的嵌入${\mathcal{M}}_{\mathcal{H}}\in d_h\times N_h$。假定$\mathcal{H}$中存在$K$个网格，将$\mathcal{H}$看作图，在其上进行Node2Vec以获得${\mathcal{M}}_{\mathcal{H}}$。

基于图的轨迹编码

对于轨迹编码，首先为每条轨迹构建图，然后利用提出的GAT-based Transformer来生成轨迹图的嵌入。

轨迹图的构造

给定轨迹$T$，构建其对应的轨迹图$T^g=(N,E)$，其中$N$为节点集，$E$为边集。

$T^g$中的节点是从$T$的原始记录以及其在$\mathcal{H}$的不同层所关联的网格单元中提取的，即$N=N_r\cup N_h$。假定轨迹$T$的原始记录节点集为$N_r$，将其作为第0层的节点，TrajGAT递归地将与先前层关联的没有被添加的层次网格单元节点加入$T^g$，$\mathcal{H}$不同层对应的节点集表示为$N_h^1$。

$T^g$中涉及两种不同的边，第一种称之为跨层边$E_c$，其连接了不同层的节点。对于轨迹$T$的原始记录节点集$N_r$会添加$N_r$到$\mathcal{H}$中与其关联的网格单元节点集$N_h^1$间的边，其他层间的边通过$\mathcal{H}$的树结构来添加。第二种称之为同层边，作者仅构建了$N_h$的同层边，具体做法是对于每层$N_h^i$，若其节点在更低层中没有连接，则添加相应的边。

轨迹图的构造示意图见下：

$T^g$中的节点特征$f$由三部分组成：坐标特征$f^h$，区域特征$f^r$和层次结构特征$f^h$，即$\mathbf{f}=\text{concat}(f^l,f^r,f^h)$，具体获取过程略。

基于GAT的轨迹编码器

下图展示的是该轨迹编码器的结构：

该框架包含两个新奇的设计：

• 位置编码同时保留轨迹的顺序和位置信息
• 基于GAT的Transformer通过图注意力操作来建模长序列

位置编码：需要获取$T^g$的节点顺序遍历，对于第0层，直接follow轨迹$T$中的轨迹点顺序，对于其他层，按其在$N_{i-1}^h$中连接节点的出现顺序将其添加到遍历序列$L$中（不重复）。然后，对获取到的$L$采用正弦值来编码位置信息${\lambda }_i^s$。此外，为了建模$T^g$的图关系，作者采用了拉普拉斯位置编码来编码相对距离信息${\lambda }_i^g$，即邻近节点位置特征相似，距离较远节点位置特征不同。在获取到两个位置编码后将其凭借起来然后加到节点特征向$f_i$上，即：
$$\begin{array}{rl}{\lambda }_i& =\mathrm{concat}\left({\lambda }_{\mathrm{i}}^{\mathrm{s}},{\lambda }_{\mathrm{i}}^{\mathrm{g}},\right)\\ {\mathbf{i}}_i& ={\lambda }_i+{\mathbf{f}}_i\end{array}$$
其中${\mathbf{f}}_i$表示节点$i$对应的特征。

基于GAT的Transformer层：对于每个节点$i$，对轨迹图$T^g$利用GAT层进行图卷积，然后套用Transformer层，具体参加上图。对GAT层，作者对self-attention的计算方式进行了改变，不再使用pair-wise注意力，作者改变后的GAT对应的卷积公式如下：
$$\begin{array}{r}{\mathbf{h}}_i^{\prime \ell +1}={\mathbf{O}}_h^{\ell }{\mathrm{concat}}_{k=1}^H\left({\sum }_{j\in {\mathcal{N}}_i}{\mathbf{w}}_{ij}^{k,\ell }{\mathbf{V}}^{k,\ell }{\mathbf{h}}_j^{\ell }\right)\\ \text{ where, }{\mathbf{w}}_{i,j}^{k,\ell }={\mathrm{softmax}}_j\left(\frac{{\mathrm{Q}}^{k,\ell }{\mathbf{h}}_i^{\ell }\cdot {\mathrm{K}}^{k,\ell }{\mathbf{h}}_j^{\ell }}{\sqrt{d_k}}\right)\end{array}$$
其中$Q,K,V$都是可学习的参数矩阵。在经过$P$个基于GAT的Transformer层后，可以获取到的$P$个隐藏层表示$\left[{\mathbf{h}}_1^P,\dots ,{\mathbf{h}}_i^P,\dots ,{\mathbf{h}}_M^P\right]$，最终轨迹图的嵌入表示$\mathbf{e}$作者采用的mean readout来计算，即
$$\mathbf{e}=\sum _{i=1}^M{\mathbf{h}}_i^P/M$$
基于图的轨迹编码的输出可以作为轨迹其纳入来计算轨迹相似性。

基于度量学习的优化

TrajGAT采用度量学习的框架来优化模型参数。给定距离矩阵$\mathcal{D}$ ，其中包含$\mathcal{T}$中轨迹对的逐对距离。作者先将其转换为相似度矩阵$\mathcal{S}$，即${\mathcal{S}}_{ij}=\frac{\exp \left(-\theta {\mathcal{D}}_{i,h}\right)}{\max (\exp (-\theta \mathcal{D}))}$，其中$\theta$是控制相似值分布的可调参数，$\mathcal{S}$ 被用作监督信号。

然而上述监督信号中的大部分相似性$T_a$都聚集在一个很小的区域，这不能提供明确的监督信息，为此作者还对其进行了Gaussian正则化：
$$\begin{array}{c}{\mu }_a=\frac{{\sum }_{i\in [1,\dots ,N]/a}{\mathcal{S}}_{ai}}{N-1};{\sigma }_a=\sqrt{\frac{{\sum }_{i\in [1,\dots ,N]/a}{\left({\mathcal{S}}_{ai}-{\mu }_a\right)}^2}{N-1}}\\ f\left(T_a,T_j\right)=\left({\mathcal{S}}_{aj}-{\mu }_a\right)/{\sigma }_a\end{array}$$
正则化后$T_a$的相似度分布符合标注高斯分布，然后用它来计算关于$T_a$是损失：
$$L_a=\sum _{i=1}^n{r}_i{\left(g\left(T_a,T_i\right)-f\left(T_a,T_i\right)\right)}^2$$
其中$g\left(T_i,T_j\right)=\exp \left(-\mathrm{Euclidean}\left({\mathbf{e}}_i,{\mathbf{e}}_j\right)\right)$ 计算两个轨迹嵌入之间的相似度。 $r$ 是根据weighted rank loss计算的采样权重。最终轨迹集$\mathcal{T}$上的总损失为：
$$L_{\mathcal{T}}=\sum _{a\in \mathcal{T}}{L}_a$$