【论文阅读】GETNext: Trajectory Flow Map Enhanced Transformer for Next POI Recommendation

Metadata

authors:: Song Yang, Jiamou Liu, Kaiqi Zhao
container:: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval
year:: 2022
DOI:: 10.1145/3477495.3531983
rating:: ⭐⭐️⭐️
share:: false
comment:: 论文的主干网络仍然是 Transformer，通过构建 POI 之间的转移权重图（trajectory flow map）并通过 GCN 进行 POI Embedding；最后，又同时预测 POI、时间、类别，加强了损失函数。

前言

Next POI 推荐是根据用户的当前状态和历史信息，预测用户近期的动向，为用户和服务提供商带来巨大的价值。

2022 年 SIGIR 的一篇论文：GETNext: Trajectory Flow Map Enhanced Transformer for Next POI Recommendation

问题描述

给定大小为 $M$ 的用户集合 $U=\{u_1, u_2, \cdots,u_M\}$ 和大小为 $N$ 的 POI 集合 $P=\{p_1, p_2, \cdots, p_N \}$ 。其中 $p=\langle latitude,longitude,category,frequency \rangle$ 分别表示经度、纬度、类别以及访问频次。

（check-in）一个 check-in 可以表示为 $q=\langle u,p,t \rangle \in U\times P\times T$ ，即用户 $u$ 在 $t$ 时刻访问地点 $p$ 。

对于当前用户 $u$ ，他的行动轨迹为 $S_u=(q_1,q_2,\cdots,q_m)$ ，一般的，我们的任务是预测用户的下一个访问地点，即next POI(Point-of-Interest) recommendation。

Overview

论文提出了一个新的模型 Graph Enhanced Transformer model（GETNext）。模型的总体框架仍是 Transformer。另外，构建了全局轨迹流程图（global trajectory flow map）并使用 GCN 来进行 POI Embedding。之后再融合 User Embedding、Category Embedding、Time Embedding（Time2Vec）作为最终输入。

主要贡献：

提出了一个全局轨迹流图（global trajectory flow map）来表示 POI 访问顺序信息，并利用图卷积网络（GCN）进行 POI 嵌入。
提出了一种新的时间感知类别嵌入（time-aware category embedding），来更好地表示时间信息。
提出了一个基于 Transformer 的框架，将全局移动模式（global transition patterns）、用户偏好（user general tastes）、用户近期轨迹（user short term trajectory）和时空信息进行整合，进行 POI 推荐。

GETNext

模型架构如下图所示：

Trajectory Flow Map

轨迹图的输出主要用于两个部分：

使用图卷积网络 GCN 进行 POI Embedding。
使用注意力模块 Attention 生成一个转移概率矩阵（transition attention map）

论文也对 Trajectory Flow Map 进行了可视化，还是可以明显的发现几个密集区域的。

POI Embedding

论文指出，不同用户可能共享某些相似的轨迹片段，同时同一个人可以多次重复一个轨迹。即利用来自其他用户的集体信息形成连续的轨迹。例如，下图的两个用户访问了同一个餐厅和电影院，并且访问顺序也相同。

这些轨迹流可以为用户的一般运动模式提供关键的信息，帮助解决短轨迹和非活跃用户的问题。

（Trajectory Flow Map）给定历史轨迹集合 $\mathcal{S}=\{S_u^i\}_{i\in \mathbb{N},u\in U}$ ，Trajectory Flow Map $\mathcal{G} = (V,E,\mathcal{l},\mathcal{w})$ 为有向带权图，其中：

nodes 集合 $V=P$ ， $P$ 为 POI 集合；

$p=\langle latitude,longitude,category,frequency \rangle\in P$ 分别表示经度、纬度、类别以及访问频次；

若连续访问 $p_1,p_2$ ，则添加边 $(p_1,p_2)$ ；

边 $(p_1,p_2)$ 上的权重为这条边出现的频次。

简单总结一下 Trajectory Flow Map，这幅图为有向带权图，图上的点为各个 POI，根据用户访问轨迹连接，边上的权重为相同片段轨迹出现的次数，节点（POI）上记录经度、纬度、类别以及访问频次信息。

接下来使用图卷积网络 GCN 正式进行 POI Embeding。关于 GCN 的具体原理这里就不过多介绍了，如果你对 GCN 并不了解，可以看我的另一篇文章：简单理解图神经网络 GNN。

计算拉普拉斯矩阵并给出隐藏层更新方程：

$\widetilde{\mathbf{L}}=(\mathbf{D}+\mathbf{I}_N)^{-1}(\mathbf{A}+\mathbf{I}_N)$

$\mathbf{H}^{(l)}=\sigma \left( \widetilde{\mathbf{L}}\mathbf{H}^{(l-1)}\mathbf{W}^{(l)}+b^{(l)} \right)$

其中 $\mathbf{D},\mathbf{A}$ 分别表示度矩阵和邻接矩阵。

个人感觉这里有些问题，按道理来说应该是对称归一化才对，也就是下面这样：

$\widetilde{\mathbf{L}}=(\mathbf{D}+\mathbf{I}_N)^{-1/2}(\mathbf{A}+\mathbf{I}_N)(\mathbf{D}+\mathbf{I}_N)^{-1/2}$

在每次迭代中，GCN 层通过聚合节点的邻居信息和节点自己的嵌入来更新节点的嵌入。

经过 $l^{*}$ 层循环之后，模块的输出可以表示为：

$\mathbf{e}_p=\widetilde{\mathbf{L}}\mathbf{H}^{(l^{*})}\mathbf{W}^{(l^{*}+1)}+b^{(l^{*}+1)} \in \mathbb{R}^{N\times \Omega}$

经过 GCN 之后便得到了 POI 的向量表示。值得注意的是，即使当前的轨迹很短，POI 嵌入仍然为预测模型提供了丰富的信息。

Transition Attention Map

从图 $\mathcal{G}$ 中学习到的 POI Embedding 只捕获了一般的行为模型，为了进一步放大集体信号的影响，论文提出了转移概率矩阵 $\mathbf{\Phi}$ 来明确从一个 POI 到另一个 POI 的转移概率。具体来说：

$\mathbf{\Phi}_1=(\mathbf{X} \times \mathbf{W}_1) \times \mathbf{a}_1 \in \mathbb{R}^{N\times 1}$

$\mathbf{\Phi}_2=(\mathbf{X} \times \mathbf{W}_2) \times \mathbf{a}_2 \in \mathbb{R}^{N\times 1}$

$\mathbf{\Phi}=(\mathbf{\Phi}_1 \times \mathbf{1}^T + \mathbf{1} \times \mathbf{\Phi}_2^T) \odot (\widetilde{\mathbf{L}}+J_N) \in \mathbb{R}^{N\times N}$

其中 $\mathbf{X}$ 为图中节点包含的信息（经度、纬度、类别以及访问频次）； $\mathbf{W}_1,\mathbf{W}_2,\mathbf{a}_1,\mathbf{a}_2$ 为可训练参数。

这个公式不是特别理解。

Contextual Embedding Module

POI Embedding 之外，论文中同样引入了时空特征以及用户偏好特征。

POI-User Embeddings Fusion

论文中，将 User Embedding 和 POI Embedding 进行连接，以此来表示 check-in 活动。

$\mathbf{e}_u=f_{embed}(u)\in \mathbb{R}^{\Omega}$

$\mathbf{e}_{p,u}=\sigma(\mathbf{w}_{p,u}[\mathbf{e}_p;\mathbf{e}_u]+b_{p,u})\in \mathbb{R}^{\Omega \times 2}$

其中 $\mathbf{e}_u,\mathbf{e}_p$ 分别表示 User Embedding 和 POI Embedding。

Time-Category Embeddings Fusion

针对 Time Embedding，论文中采用了 Time2Vec 方法，如果你对 Time2Vec 并不了解，可以看我的另一篇文章：。特别的，论文中将一天分为 48 个时间片，每个时间片 30 分钟，长度为 $k+1$ ，具体来说：

$\mathbf{e}_t[i]=\begin{cases} \omega_it+\varphi_i, &\text{if } i=0 \\ \sin(\omega_it+\varphi_i) &\text{if } 1\leq i\leq k \end{cases}$

另一方面，由于数据的稀疏性以及噪声，论文将 Category Embedding 和 Time Embedding 进行拼接，探索 POI 类别的时间模式，而不是单个的 POI。

$\mathbf{e}_c=f_{embed}(c)\in \mathbb{R}^{\Psi}$

$\mathbf{e}_{c,t}=\sigma(\mathbf{w}_{c,t}[\mathbf{e}_t;\mathbf{e}_c]+b_{c,t})\in \mathbb{R}^{\Psi \times 2}$

经过上面的一系列处理，我们将 check-in $q=\langle p,u,t \rangle$ 转化为了向量 $\mathbf{e}_q=[\mathbf{e}_{p,u};\mathbf{e}_{c,t}]$ 作为 Transformer 的输入。

Transformer Encoder and MLP Decoders

Transformer Encoder

主干网络使用的仍然是 Transformer，这里不进行过多的介绍了。对于一个输入序列 $S_u=(q_u^1,q_u^2,\cdots,q_u^k)$ ，我们需要预测下一个活动 $q_u^{k+1}$ 。经过上面的 check-in Embedding 之后，对于 $q_u^i$ 可以得到 $\mathcal{X}^{[0]}\in \mathbb{R}^{k \times d}$ 作为 Transformer 的输入，其中 $d$ 为 embedding 维度。

接着就是一些熟悉的 Attention 操作：

$S=\mathcal{X}^{[l]}\mathbf{W}_q(\mathcal{X}^{[l]}\mathbf{W}_k)^T\in \mathbb{R}^{k\times k}$

$S_{i,j}'=\frac{\exp(S_{i,j})}{\sum_{j=1}^d\exp(S_{i,j})}$

$\text{head}_1=S'\mathcal{X}^{[l]}\mathbf{W}_v\in \mathbb{R}^{k\times d/h}$

$\text{Multihead}(\mathcal{X}^{[l]})=[\text{head}_1;\cdots;\text{head}_h]\times \mathbf{W}_o\in\mathbb{R}^{k\times d}$

之后是残差连接、LayerNorm、FFN：

$\mathcal{X}_{\text{attn}}^{[l]}=\text{LayerNorm}\left(\mathcal{X}^{[l]}+\text{Multihead}(\mathcal{X}^{[l]}) \right)$

$\mathcal{X}_{FC}^{[l]}=\text{ReLU}(\mathbf{W}_1\mathcal{X}_{\text{attn}}^{[l]}+b_1)\mathbf{W}_2+b_2\in\mathbb{R}^{k\times d}$

$\mathcal{X}^{[l+1]}=\text{LayerNorm}(\mathcal{X}_{\text{attn}}^{[l]}+\mathcal{X}_{FC}^{[l]})\in\mathbb{R}^{k\times d}$

MLP Decoders

通过 Transformer Encoder 之后得到了输出 $\mathcal{X}^{[l^*]}$ ，之后在经过多层感知机将输出分别映射到三个 MLP heads：

$\hat{\mathbf{Y}}_{\text{poi}}=\mathcal{X}^{[l^*]}\mathbf{W}_{\text{poi}}+b_{\text{poi}}$

$\hat{\mathbf{Y}}_{\text{time}}=\mathcal{X}^{[l^*]}\mathbf{W}_{\text{time}}+b_{\text{time}}$

$\hat{\mathbf{Y}}_{\text{cat}}=\mathcal{X}^{[l^*]}\mathbf{W}_{\text{cat}}+b_{\text{cat}}$

其中， $\mathbf{W}_{\text{poi}}\in\mathbb{R}^{d\times N},\mathbf{W}_{\text{time}}\in\mathbb{R}^{d\times 1},\mathbf{W}_{\text{cat}}\in\mathbb{R}^{d\times \Gamma}$ 分别为可学习权重。

特别的，对于 $\hat{\mathbf{Y}}_{\text{poi}}$ 论文同时将上文得到的概率转移矩阵（Transition Attention Map）与其结合：

$\hat{\mathbf{y}}_{\text{poi}}=\hat{\mathbf{Y}}_{\text{poi}}^{(k\cdot)}+\Phi^{p_k\cdot}\in\mathbb{R}^{1\times N}$

论文认为两次 check-in 之间的时间间隔波动可能很大，对应的 POI 类别也可能不同，用户应该在接下来的 1 小时和 5 小时收到不同的建议。因此在预测下一个 POI 的同时也预测下一次 check-in 时间、类型。也就是论文中使用三个 MLP heads 的原因。

Loss

由于论文中计算了三个预测结果，因此最终的损失为加权和：

$\mathcal{L}_{\text{final}}=\mathcal{L}_{\text{poi}}+10\times \mathcal{L}_{\text{time}}+\mathcal{L}_{\text{cat}}$

其中， $\mathcal{L}_{\text{poi}}, \mathcal{L}_{\text{cat}}$ 使用交叉熵损失函数计算， $\mathcal{L}_{\text{time}}$ 使用均方根损失函数（MSE）计算。由于时间经过标准化之后 $\in[0,1]$ ，因此最后计算损失的时候乘了 10 倍。