Next POI 推荐是根据用户的当前状态和历史信息，预测用户近期的动向，为用户和服务提供商带来巨大的价值。
2022 年 SIGIR 的一篇论文：GETNext: Trajectory Flow Map Enhanced Transformer for Next POI Recommendation
给定大小为 M M M的用户集合 U = { u 1 , u 2 , ⋯ , u M } U=\{u_1, u_2, \cdots,u_M\} U={u1,u2,⋯,uM}和大小为 N N N的 POI 集合 P = { p 1 , p 2 , ⋯ , p N } P=\{p_1, p_2, \cdots, p_N \} P={p1,p2,⋯,pN}。其中 p = ⟨ l a t i t u d e , l o n g i t u d e , c a t e g o r y , f r e q u e n c y ⟩ p=\langle latitude,longitude,category,frequency \rangle p=⟨latitude,longitude,category,frequency⟩分别表示经度、纬度、类别以及访问频次。
（check-in）一个 check-in 可以表示为 q = ⟨ u , p , t ⟩ ∈ U × P × T q=\langle u,p,t \rangle \in U\times P\times T q=⟨u,p,t⟩∈U×P×T，即用户 u u u在 t t t时刻访问地点 p p p。
对于当前用户 u u u，他的行动轨迹为 S u = ( q 1 , q 2 , ⋯ , q m ) S_u=(q_1,q_2,\cdots,q_m) Su=(q1,q2,⋯,qm)，一般的，我们的任务是预测用户的下一个访问地点，即next POI(Point-of-Interest) recommendation。
论文提出了一个新的模型 Graph Enhanced Transformer model（GETNext）。模型的总体框架仍是 Transformer。另外，构建了全局轨迹流程图（global trajectory flow map）并使用 GCN 来进行 POI Embedding。之后再融合 User Embedding、Category Embedding、Time Embedding（Time2Vec）作为最终输入。
主要贡献：
模型架构如下图所示：
轨迹图的输出主要用于两个部分：
论文也对 Trajectory Flow Map 进行了可视化，还是可以明显的发现几个密集区域的。
论文指出，不同用户可能共享某些相似的轨迹片段，同时同一个人可以多次重复一个轨迹。即利用来自其他用户的集体信息形成连续的轨迹。例如，下图的两个用户访问了同一个餐厅和电影院，并且访问顺序也相同。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kjY4t2Fj-1658547105921)(https://static.emoryhuang.cn/webp/4228286132-GETNext-2.webp)]
这些轨迹流可以为用户的一般运动模式提供关键的信息，帮助解决短轨迹和非活跃用户的问题。
（Trajectory Flow Map）给定历史轨迹集合 S = { S u i } 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)为有向带权图，其中：
- nodes 集合 V = P V=P V=P， P P P为 POI 集合；
- p = ⟨ l a t i t u d e , l o n g i t u d e , c a t e g o r y , f r e q u e n c y ⟩ ∈ P p=\langle latitude,longitude,category,frequency \rangle\in P p=⟨latitude,longitude,category,frequency⟩∈P分别表示经度、纬度、类别以及访问频次；
- 若连续访问 p 1 , p 2 p_1,p_2 p1,p2，则添加边 ( p 1 , p 2 ) (p_1,p_2) (p1,p2)；
- 边 ( p 1 , p 2 ) (p_1,p_2) (p1,p2)上的权重为这条边出现的频次。
简单总结一下 Trajectory Flow Map，这幅图为有向带权图，图上的点为各个 POI，根据用户访问轨迹连接，边上的权重为相同片段轨迹出现的次数，节点（POI）上记录经度、纬度、类别以及访问频次信息。
接下来使用图卷积网络 GCN 正式进行 POI Embeding。关于 GCN 的具体原理这里就不过多介绍了，如果你对 GCN 并不了解，可以看我的另一篇文章：简单理解图神经网络 GNN。
计算拉普拉斯矩阵并给出隐藏层更新方程：
L ~ = ( D + I N ) − 1 ( A + I N ) \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)=σ(L H(l−1)W(l)+b(l))
其中 D , A \mathbf{D},\mathbf{A} D,A分别表示度矩阵和邻接矩阵。
个人感觉这里有些问题，按道理来说应该是对称归一化才对，也就是下面这样：
L ~ = ( D + I N ) − 1 / 2 ( A + I N ) ( D + I N ) − 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∗层循环之后，模块的输出可以表示为：
e p = L ~ H ( l ∗ ) W ( l ∗ + 1 ) + b ( l ∗ + 1 ) ∈ R N × Ω \mathbf{e}_p=\widetilde{\mathbf{L}}\mathbf{H}^{(l^{*})}\mathbf{W}^{(l^{*}+1)}+b^{(l^{*}+1)} \in \mathbb{R}^{N\times \Omega} ep=L H(l∗)W(l∗+1)+b(l∗+1)∈RN×Ω
经过 GCN 之后便得到了 POI 的向量表示。值得注意的是，即使当前的轨迹很短，POI 嵌入仍然为预测模型提供了丰富的信息。
从图 G \mathcal{G} G中学习到的 POI Embedding 只捕获了一般的行为模型，为了进一步放大集体信号的影响，论文提出了转移概率矩阵 Φ \mathbf{\Phi} Φ来明确从一个 POI 到另一个 POI 的转移概率。具体来说：
Φ 1 = ( X × W 1 ) × a 1 ∈ R N × 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 × W 2 ) × a 2 ∈ R N × 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 × 1 T + 1 × Φ 2 T ) ⊙ ( L ~ + J N ) ∈ R N × 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为图中节点包含的信息（经度、纬度、类别以及访问频次）； W 1 , W 2 , a 1 , a 2 \mathbf{W}_1,\mathbf{W}_2,\mathbf{a}_1,\mathbf{a}_2 W1,W2,a1,a2为可训练参数。
这个公式不是特别理解。
POI Embedding 之外，论文中同样引入了时空特征以及用户偏好特征。
论文中，将 User Embedding 和 POI Embedding 进行连接，以此来表示 check-in 活动。
e u = f e m b e d ( u ) ∈ R Ω \mathbf{e}_u=f_{embed}(u)\in \mathbb{R}^{\Omega} eu=fembed(u)∈RΩ
e p , u = σ ( w p , u [ e p ; e u ] + b p , 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
其中 e u , e p \mathbf{e}_u,\mathbf{e}_p eu,ep分别表示 User Embedding 和 POI Embedding。
针对 Time Embedding，论文中采用了 Time2Vec 方法，如果你对 Time2Vec 并不了解，可以看我的另一篇文章：。特别的，论文中将一天分为 48 个时间片，每个时间片 30 分钟，长度为 k + 1 k+1 k+1，具体来说：
e t [ i ] = { ω i t + φ i , if i = 0 sin ( ω i t + φ i ) if 1 ≤ i ≤ k \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} et[i]={ωit+φi,sin(ωit+φi)if i=0if 1≤i≤k
另一方面，由于数据的稀疏性以及噪声，论文将 Category Embedding 和 Time Embedding 进行拼接，探索 POI 类别的时间模式，而不是单个的 POI。
e c = f e m b e d ( c ) ∈ R Ψ \mathbf{e}_c=f_{embed}(c)\in \mathbb{R}^{\Psi} ec=fembed(c)∈RΨ
e c , t = σ ( w c , t [ e t ; e c ] + b c , 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 \rangle q=⟨p,u,t⟩转化为了向量 e q = [ e p , u ; e c , t ] \mathbf{e}_q=[\mathbf{e}_{p,u};\mathbf{e}_{c,t}] eq=[ep,u;ec,t]作为 Transformer 的输入。
主干网络使用的仍然是 Transformer，这里不进行过多的介绍了。对于一个输入序列 S u = ( q u 1 , q u 2 , ⋯ , q u k ) S_u=(q_u^1,q_u^2,\cdots,q_u^k) Su=(qu1,qu2,⋯,quk)，我们需要预测下一个活动 q u k + 1 q_u^{k+1} quk+1。经过上面的 check-in Embedding 之后，对于 q u i q_u^i qui可以得到 X [ 0 ] ∈ R k × d \mathcal{X}^{[0]}\in \mathbb{R}^{k \times d} X[0]∈Rk×d作为 Transformer 的输入，其中 d d d为 embedding 维度。
接着就是一些熟悉的 Attention 操作：
S = X [ l ] W q ( X [ l ] W k ) T ∈ R k × k S=\mathcal{X}^{[l]}\mathbf{W}_q(\mathcal{X}^{[l]}\mathbf{W}_k)^T\in \mathbb{R}^{k\times k} S=X[l]Wq(X[l]Wk)T∈Rk×k
S i , j ′ = exp ( S i , j ) ∑ j = 1 d exp ( S i , j ) S_{i,j}'=\frac{\exp(S_{i,j})}{\sum_{j=1}^d\exp(S_{i,j})} Si,j′=∑j=1dexp(Si,j)exp(Si,j)
head 1 = S ′ X [ l ] W v ∈ R k × d / h \text{head}_1=S'\mathcal{X}^{[l]}\mathbf{W}_v\in \mathbb{R}^{k\times d/h} head1=S′X[l]Wv∈Rk×d/h
Multihead ( X [ l ] ) = [ head 1 ; ⋯ ; head h ] × W o ∈ R k × d \text{Multihead}(\mathcal{X}^{[l]})=[\text{head}_1;\cdots;\text{head}_h]\times \mathbf{W}_o\in\mathbb{R}^{k\times d} Multihead(X[l])=[head1;⋯;headh]×Wo∈Rk×d
之后是残差连接、LayerNorm、FFN：
X attn [ l ] = LayerNorm ( X [ l ] + Multihead ( X [ l ] ) ) \mathcal{X}_{\text{attn}}^{[l]}=\text{LayerNorm}\left(\mathcal{X}^{[l]}+\text{Multihead}(\mathcal{X}^{[l]}) \right) Xattn[l]=LayerNorm(X[l]+Multihead(X[l]))
X F C [ l ] = ReLU ( W 1 X attn [ l ] + b 1 ) W 2 + b 2 ∈ R k × 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} XFC[l]=ReLU(W1Xattn[l]+b1)W2+b2∈Rk×d
X [ l + 1 ] = LayerNorm ( X attn [ l ] + X F C [ l ] ) ∈ R k × d \mathcal{X}^{[l+1]}=\text{LayerNorm}(\mathcal{X}_{\text{attn}}^{[l]}+\mathcal{X}_{FC}^{[l]})\in\mathbb{R}^{k\times d} X[l+1]=LayerNorm(Xattn[l]+XFC[l])∈Rk×d
通过 Transformer Encoder 之后得到了输出 X [ l ∗ ] \mathcal{X}^{[l^*]} X[l∗]，之后在经过多层感知机将输出分别映射到三个 MLP heads：
Y ^ poi = X [ l ∗ ] W poi + b poi \hat{\mathbf{Y}}_{\text{poi}}=\mathcal{X}^{[l^*]}\mathbf{W}_{\text{poi}}+b_{\text{poi}} Y^poi=X[l∗]Wpoi+bpoi
Y ^ time = X [ l ∗ ] W time + b time \hat{\mathbf{Y}}_{\text{time}}=\mathcal{X}^{[l^*]}\mathbf{W}_{\text{time}}+b_{\text{time}} Y^time=X[l∗]Wtime+btime
Y ^ cat = X [ l ∗ ] W cat + b cat \hat{\mathbf{Y}}_{\text{cat}}=\mathcal{X}^{[l^*]}\mathbf{W}_{\text{cat}}+b_{\text{cat}} Y^cat=X[l∗]Wcat+bcat
其中， W poi ∈ R d × N , W time ∈ R d × 1 , W cat ∈ R d × Γ \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 ⋅ ) + Φ p k ⋅ ∈ R 1 × 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 的原因。
由于论文中计算了三个预测结果，因此最终的损失为加权和：
L final = L poi + 10 × L time + L cat \mathcal{L}_{\text{final}}=\mathcal{L}_{\text{poi}}+10\times \mathcal{L}_{\text{time}}+\mathcal{L}_{\text{cat}} Lfinal=Lpoi+10×Ltime+Lcat
其中， L poi , L cat \mathcal{L}_{\text{poi}}, \mathcal{L}_{\text{cat}} Lpoi,Lcat使用交叉熵损失函数计算， L time \mathcal{L}_{\text{time}} Ltime使用均方根损失函数（MSE）计算。由于时间经过标准化之后 ∈ [ 0 , 1 ] \in[0,1] ∈[0,1]，因此最后计算损失的时候乘了 10 倍。
数据集：
评价指标：
Acc @ k = 1 m ∑ i = 1 m 1 ( r a n k ≤ k ) \text{Acc}@k=\frac1m\sum_{i=1}^m\mathbb{1}(rank \leq k) Acc@k=m1i=1∑m1(rank≤k)
MRR = 1 m ∑ i = 1 m 1 r a n k \text{MRR}=\frac1m\sum_{i=1}^m\frac{1}{rank} MRR=m1i=1∑mrank1
论文根据用户的活跃情况，即根据用户 check-in 数量进行排序，分析不同活跃程度的用户对模型带来的影响：
另一方面，论文同时对短轨迹下的挑战进行了实验：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-M9FGg3pl-1658547105922)(https://static.emoryhuang.cn/webp/4228286132-GETNext-6.webp)]
下面是移除 trajectory flow map 的实验结果：
最后做个总结，这篇论文的主干网络仍然是 Transformer，最大的变化在于通过构建 POI 之间的转移权重图（trajectory flow map）并通过 GCN 进行 POI Embedding；最后，又同时预测 POI、时间、类别，加强了损失函数。
