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

前言

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

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

问题描述

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

check-in)一个 check-in 可以表示为q=u,p,tU×P×Tq=\langle u,p,t \rangle \in U\times P\times T,即用户uutt时刻访问地点pp

对于当前用户uu,他的行动轨迹为Su=(q1,q2,,qm)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)作为最终输入。

主要贡献:

  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}iN,uU\mathcal{S}=\{S_u^i\}_{i\in \mathbb{N},u\in U},Trajectory Flow Map G=(V,E,l,w)\mathcal{G} = (V,E,\mathcal{l},\mathcal{w})为有向带权图,其中:

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

简单总结一下 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)

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

其中D,A\mathbf{D},\mathbf{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}

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

经过ll^{*}层循环之后,模块的输出可以表示为:

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}

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

Transition Attention Map

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

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

Φ2=(X×W2)×a2RN×1\mathbf{\Phi}_2=(\mathbf{X} \times \mathbf{W}_2) \times \mathbf{a}_2 \in \mathbb{R}^{N\times 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}

其中X\mathbf{X}为图中节点包含的信息(经度、纬度、类别以及访问频次);W1,W2,a1,a2\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 活动。

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

ep,u=σ(wp,u[ep;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}

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

Time-Category Embeddings Fusion

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

et[i]={ωit+φi,if i=0sin(ωit+φi)if 1ik\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。

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

ec,t=σ(wc,t[et;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}

经过上面的一系列处理,我们将 check-in q=p,u,tq=\langle p,u,t \rangle转化为了向量eq=[ep,u;ec,t]\mathbf{e}_q=[\mathbf{e}_{p,u};\mathbf{e}_{c,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),我们需要预测下一个活动quk+1q_u^{k+1}。经过上面的 check-in Embedding 之后,对于quiq_u^i可以得到X[0]Rk×d\mathcal{X}^{[0]}\in \mathbb{R}^{k \times d}作为 Transformer 的输入,其中dd为 embedding 维度。

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

S=X[l]Wq(X[l]Wk)TRk×kS=\mathcal{X}^{[l]}\mathbf{W}_q(\mathcal{X}^{[l]}\mathbf{W}_k)^T\in \mathbb{R}^{k\times 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})}

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

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

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

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

XFC[l]=ReLU(W1Xattn[l]+b1)W2+b2Rk×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}

X[l+1]=LayerNorm(Xattn[l]+XFC[l])Rk×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 之后得到了输出X[l]\mathcal{X}^{[l^*]},之后在经过多层感知机将输出分别映射到三个 MLP heads:

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

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

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

其中,WpoiRd×N,WtimeRd×1,WcatRd×Γ\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}分别为可学习权重。

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

y^poi=Y^poi(k)+ΦpkR1×N\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

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

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

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

实验

数据集:

  • FourSquare:NYC,TKY
  • Gowalla:CA

评价指标:

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

MRR=1mi=1m1rank\text{MRR}=\frac1m\sum_{i=1}^m\frac{1}{rank}

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、时间、类别,加强了损失函数。

参考资料