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

【论文阅读】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

问题描述

给定大小为MMM的用户集合U={u1,u2,⋯ ,uM}U={u_1, u_2, \cdots,u_M}U={u1​,u2​,⋯,uM​}和大小为NNN的 POI 集合P={p1,p2,⋯ ,pN}P={p_1, p_2, \cdots, p_N }P={p1​,p2​,⋯,pN​}。其中p=⟨latitude,longitude,category,frequency⟩p=\langle latitude,longitude,category,frequency \ranglep=⟨latitude,longitude,category,frequency⟩分别表示经度、纬度、类别以及访问频次。

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

对于当前用户uuu，他的行动轨迹为Su=(q1,q2,⋯ ,qm)S_u=(q_1,q_2,\cdots,q_m)Su​=(q1​,q2​,⋯,qm​)，一般的，我们的任务是预测用户的下一个访问地点，即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）作为最终输入。

主要贡献：

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

GETNext

模型架构如下图所示：

Trajectory Flow Map

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

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

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

POI Embedding

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

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

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

1. nodes 集合V=PV=PV=P，PPP为 POI 集合；
2. p=⟨latitude,longitude,category,frequency⟩∈Pp=\langle latitude,longitude,category,frequency \rangle\in Pp=⟨latitude,longitude,category,frequency⟩∈P分别表示经度、纬度、类别以及访问频次；
3. 若连续访问p1,p2p_1,p_2p1​,p2​，则添加边(p1,p2)(p_1,p_2)(p1​,p2​)；
4. 边(p1,p2)(p_1,p_2)(p1​,p2​)上的权重为这条边出现的频次。

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

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

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

L~=(D+IN)−1(A+IN)\widetilde{\mathbf{L}}=(\mathbf{D}+\mathbf{I}_N)^{-1}(\mathbf{A}+\mathbf{I}_N) L=(D+IN​)−1(A+IN​)

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

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

个人感觉这里有些问题，按道理来说应该是对称归一化才对，也就是下面这样： L~=(D+IN)−1/2(A+IN)(D+IN)−1/2\widetilde{\mathbf{L}}=(\mathbf{D}+\mathbf{I}_N)^{-1/2}(\mathbf{A}+\mathbf{I}_N)(\mathbf{D}+\mathbf{I}_N)^{-1/2} L=(D+IN​)−1/2(A+IN​)(D+IN​)−1/2

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

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

ep=L~H(l∗)W(l∗+1)+b(l∗+1)∈RN×Ω\mathbf{e}_p=\widetilde{\mathbf{L}}\mathbf{H}^{(l^{*})}\mathbf{W}^{(l^{*}+1)}+b^{(l^{*}+1)} \in \mathbb{R}^{N\times \Omega} ep​=LH(l∗)W(l∗+1)+b(l∗+1)∈RN×Ω

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

Transition Attention Map

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

Φ1=(X×W1)×a1∈RN×1\mathbf{\Phi}_1=(\mathbf{X} \times \mathbf{W}_1) \times \mathbf{a}_1 \in \mathbb{R}^{N\times 1} Φ1​=(X×W1​)×a1​∈RN×1

Φ2=(X×W2)×a2∈RN×1\mathbf{\Phi}_2=(\mathbf{X} \times \mathbf{W}_2) \times \mathbf{a}_2 \in \mathbb{R}^{N\times 1} Φ2​=(X×W2​)×a2​∈RN×1

Φ=(Φ1×1T+1×Φ2T)⊙(L~+JN)∈RN×N\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} Φ=(Φ1​×1T+1×Φ2T​)⊙(L+JN​)∈RN×N

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

这个公式不是特别理解。

Contextual Embedding Module

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

POI-User Embeddings Fusion

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

eu=fembed(u)∈RΩ\mathbf{e}_u=f_{embed}(u)\in \mathbb{R}^{\Omega} eu​=fembed​(u)∈RΩ

ep,u=σ(wp,uep;eu+bp,u)∈RΩ×2\mathbf{e}_{p,u}=\sigma(\mathbf{w}_{p,u}\mathbf{e}_p;\mathbf{e}_u+b_{p,u})\in \mathbb{R}^{\Omega \times 2} ep,u​=σ(wp,u​ep​;eu​+bp,u​)∈RΩ×2

其中eu,ep\mathbf{e}_u,\mathbf{e}_peu​,ep​分别表示 User Embedding 和 POI Embedding。

Time-Category Embeddings Fusion

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

eti={ωit+φi,if i=0sin⁡(ωit+φi)if 1≤i≤k\mathbf{e}_ti=\begin{cases} \omega_it+\varphi_i, &\text{if } i=0 \ \sin(\omega_it+\varphi_i) &\text{if } 1\leq i\leq k \end{cases} et​i={ωi​t+φi​,sin(ωi​t+φi​)​if i=0if 1≤i≤k​

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

ec=fembed(c)∈RΨ\mathbf{e}_c=f_{embed}(c)\in \mathbb{R}^{\Psi} ec​=fembed​(c)∈RΨ

ec,t=σ(wc,tet;ec+bc,t)∈RΨ×2\mathbf{e}_{c,t}=\sigma(\mathbf{w}_{c,t}\mathbf{e}_t;\mathbf{e}_c+b_{c,t})\in \mathbb{R}^{\Psi \times 2} ec,t​=σ(wc,t​et​;ec​+bc,t​)∈RΨ×2

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

Transformer Encoder and MLP Decoders

Transformer Encoder

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

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

S=XlWq(XlWk)T∈Rk×kS=\mathcal{X}^{l}\mathbf{W}_q(\mathcal{X}^{l}\mathbf{W}_k)^T\in \mathbb{R}^{k\times k} S=XlWq​(XlWk​)T∈Rk×k

Si,j′=exp⁡(Si,j)∑j=1dexp⁡(Si,j)S_{i,j}'=\frac{\exp(S_{i,j})}{\sum_{j=1}^d\exp(S_{i,j})} Si,j′​=∑j=1d​exp(Si,j​)exp(Si,j​)​

head1=S′XlWv∈Rk×d/h\text{head}_1=S'\mathcal{X}^{l}\mathbf{W}_v\in \mathbb{R}^{k\times d/h} head1​=S′XlWv​∈Rk×d/h

Multihead(Xl)=head1;⋯ ;headh×Wo∈Rk×d\text{Multihead}(\mathcal{X}^{l})=\text{head}_1;\cdots;\text{head}_h\times \mathbf{W}_o\in\mathbb{R}^{k\times d} Multihead(Xl)=head1​;⋯;headh​×Wo​∈Rk×d

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

Xattnl=LayerNorm(Xl+Multihead(Xl))\mathcal{X}_{\text{attn}}^{l}=\text{LayerNorm}\left(\mathcal{X}^{l}+\text{Multihead}(\mathcal{X}^{l}) \right) Xattnl​=LayerNorm(Xl+Multihead(Xl))

XFCl=ReLU(W1Xattnl+b1)W2+b2∈Rk×d\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} XFCl​=ReLU(W1​Xattnl​+b1​)W2​+b2​∈Rk×d

Xl+1=LayerNorm(Xattnl+XFCl)∈Rk×d\mathcal{X}^{l+1}=\text{LayerNorm}(\mathcal{X}_{\text{attn}}^{l}+\mathcal{X}_{FC}^{l})\in\mathbb{R}^{k\times d} Xl+1=LayerNorm(Xattnl​+XFCl​)∈Rk×d

MLP Decoders

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

Y^poi=Xl∗Wpoi+bpoi\hat{\mathbf{Y}}_{\text{poi}}=\mathcal{X}^{l^*}\mathbf{W}_{\text{poi}}+b_{\text{poi}} Y^poi​=Xl∗Wpoi​+bpoi​

Y^time=Xl∗Wtime+btime\hat{\mathbf{Y}}_{\text{time}}=\mathcal{X}^{l^*}\mathbf{W}_{\text{time}}+b_{\text{time}} Y^time​=Xl∗Wtime​+btime​

Y^cat=Xl∗Wcat+bcat\hat{\mathbf{Y}}_{\text{cat}}=\mathcal{X}^{l^*}\mathbf{W}_{\text{cat}}+b_{\text{cat}} Y^cat​=Xl∗Wcat​+bcat​

其中，Wpoi∈Rd×N,Wtime∈Rd×1,Wcat∈Rd×Γ\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}Wpoi​∈Rd×N,Wtime​∈Rd×1,Wcat​∈Rd×Γ分别为可学习权重。

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

y^poi=Y^poi(k⋅)+Φpk⋅∈R1×N\hat{\mathbf{y}}_{\text{poi}}=\hat{\mathbf{Y}}_{\text{poi}}^{(k\cdot)}+\Phi^{p_k\cdot}\in\mathbb{R}^{1\times N} y^​poi​=Y^poi(k⋅)​+Φpk​⋅∈R1×N

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

Loss

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

Lfinal=Lpoi+10×Ltime+Lcat\mathcal{L}_{\text{final}}=\mathcal{L}_{\text{poi}}+10\times \mathcal{L}_{\text{time}}+\mathcal{L}_{\text{cat}} Lfinal​=Lpoi​+10×Ltime​+Lcat​

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

实验

数据集：

• FourSquare：NYC，TKY
• Gowalla：CA

评价指标：

Acc@k=1m∑i=1m1(rank≤k)\text{Acc}@k=\frac1m\sum_{i=1}^m\mathbb{1}(rank \leq k) Acc@k=m1​i=1∑m​1(rank≤k)

MRR=1m∑i=1m1rank\text{MRR}=\frac1m\sum_{i=1}^m\frac{1}{rank} MRR=m1​i=1∑m​rank1​

Results

Inactive users and active users

论文根据用户的活跃情况，即根据用户 check-in 数量进行排序，分析不同活跃程度的用户对模型带来的影响：

Short trajectories and long trajectories

另一方面，论文同时对短轨迹下的挑战进行了实验：

下面是移除 trajectory flow map 的实验结果：

消融实验

总结

最后做个总结，这篇论文的主干网络仍然是 Transformer，最大的变化在于通过构建 POI 之间的转移权重图（trajectory flow map）并通过 GCN 进行 POI Embedding；最后，又同时预测 POI、时间、类别，加强了损失函数。

参考资料

• 1(https://dl.acm.org/doi/abs/10.1145/3477495.3531983)
• 2(https://arxiv.org/abs/1907.05321)