【论文阅读】STAN: Spatio-Temporal Attention Network for Next Location Recommendation

Metadata

authors:: Yingtao Luo, Qiang Liu, Zhaocheng Liu
container:: Proceedings of the Web Conference 2021
year:: 2021
DOI:: 10.1145/3442381.3449998
rating:: ⭐⭐⭐
share:: false
comment:: 通过双层Attention的方式,对Attention公式进行修改,聚合时间以及距离信息。通过线性插值代替 GPS 网格进行空间/时间离散化。


前言

仍然是 POI 推荐的一篇论文。

2021 年 WWW 上的一篇论文:STAN: Spatio-Temporal Attention Network for Next Location Recommendation

Overview

现有问题:

  1. 没有充分考虑非相邻位置和非相邻访问之间的相关性;
  2. 采用空间离散化分层网格对空间距离不敏感;
  3. 忽略了 personalized item frequency (PIF)。

对于第一个问题,论文给出了这样一个例子:下图中,0,1,2 分别代表家,工作单位,商场;3,4,5,6 代表餐厅。在这个例子中,用户实际上已经对非相邻的餐厅进行了两次非连续的访问。也就是所谓的非相邻位置非相邻访问

这篇论文利用,通过双层 Attention,首先聚合了相关的位置,对不同的访问赋予不同的权重,然后通过第二个 Attention 考虑 PIF 从候选位置中召回。

主要贡献:

  1. 结合时空相关性来学习非相邻位置和非相邻访问之间的规律;
  2. 用一种简单的线性插值技术代替 GPS 网格进行空间离散化,它可以恢复空间距离,反映用户的空间偏好,而不仅仅是聚合邻居;
  3. 建立双层注意力网络更好地考虑 PIF 信息。

Preliminaries

分别给定用户集合U={u1,u2,,uU}U=\{u_1, u_2, \cdots,u_U\}, POI 集合L={l1,l2,,lL}L=\{l_1, l_2, \cdots, l_L \},时间集合T={t1,t2,,tT}T=\{t_1, t_2, \cdots, t_T \}

每个用户的 check-in 轨迹可以表示为:

tra(ui)={r1,r2,,rn}tra(u_i)=\{ r_1, r_2, \cdots, r_n \}

其中rk=(ui,lk,tk)r_k=(u_i,l_k,t_k)

Trajectory Spatio-Temporal Relation Matrix

轨迹时空关系矩阵。轨迹时间关系矩阵为访问轨迹上的两个 POI 之间的访问时间间隔,轨迹空间关系矩阵为访问轨迹上的两个 POI 之间的球面距离:

Δi,jt=titjRn×n\Delta_{i,j}^t=\vert t_i-t_j \vert \in \mathbb{R}^{n\times n}

Δi,js=Haversine(GPSi,GPSj)Rn×n\Delta_{i,j}^s=\text{Haversine}(GPS_i, GPS_j) \in \mathbb{R}^{n\times n}

Δt,s=[Δ11t,sΔ12t,sΔ1nt,sΔ21t,sΔ22t,sΔ2nt,sΔn1t,sΔn2t,sΔnnt,s]\Delta^{t,s}=\begin{bmatrix}\Delta_{11}^{t,s} & \Delta_{12}^{t,s} & \cdots & \Delta_{1n}^{t,s} \\ \Delta_{21}^{t,s} & \Delta_{22}^{t,s} & \cdots & \Delta_{2n}^{t,s} \\ \vdots & \vdots & \ddots & \vdots \\ \Delta_{n1}^{t,s} & \Delta_{n2}^{t,s} & \cdots & \Delta_{nn}^{t,s} \end{bmatrix}

论文中将两个矩阵写在一起了,其实是两个矩阵。

Candidate Spatio-Temporal Relation Matrix

候选时空关系矩阵。候选时间关系矩阵为,候选空间关系矩阵为所有候选位置i[1,L]i \in [1,L]与访问轨迹上的位置j[1,n]j \in [1,n]之间的球面距离:

Ni,jt=tm+1tjRL×nN_{i,j}^t=\vert t_{m+1}-t_j \vert \in \mathbb{R}^{L\times n}

Nijs=Haversine(GPSi,GPSj)RL×nN_{ij}^{s}=\text{Haversine}(GPS_i, GPS_j)\in \mathbb{R}^{L\times n}

Nt,s=[N11t,sN12t,sN1nt,sN21t,sN22t,sN2nt,sNn1t,sNn2t,sNnnt,s]N^{t,s}=\begin{bmatrix}N_{11}^{t,s} & N_{12}^{t,s} & \cdots & N_{1n}^{t,s} \\ N_{21}^{t,s} & N_{22}^{t,s} & \cdots & N_{2n}^{t,s} \\ \vdots & \vdots & \ddots & \vdots \\ N_{n1}^{t,s} & N_{n2}^{t,s} & \cdots & N_{nn}^{t,s} \end{bmatrix}

候选时间关系矩阵没有很懂,看代码里好像是用户访问轨迹上 POI 两两之间的访问时间间隔。这两个矩阵貌似和代码里的都有差别。

Spatio-Temporal Attention Network

Architecture

Multimodal Embedding Module

User Trajectory Embedding Layer

首先对 user,POI,time 进行 Embedding,其中 time 为 hour of week。之后再将三者相加:

er=eu+el+etRde^r=e^u+e^l+e^t \in \mathbb{R}^d

Spatio-Temporal Embedding Layer

以每小时和每一百米作为基本单位,对时空关系矩阵进行嵌入,映射到一个欧氏空间。

{eijΔt=Δijt×eΔteijΔs=Δijs×eΔs\begin{cases}e_{ij}^{\Delta t} &= \Delta_{ij}^t \times e_{\Delta t} \\ e_{ij}^{\Delta s} &= \Delta_{ij}^s \times e_{\Delta s} \end{cases}

此外,论文也提出了一种插值嵌入的方法:

{eijΔt=eΔtsup(Upper(Δt)Δt)+eΔtinf(ΔtLower(Δt))Upper(Δt)Lower(Δt)eijΔs=eΔssup(Upper(Δs)Δs)+eΔsinf(ΔsLower(Δs))Upper(Δs)Lower(Δs)\begin{cases}e_{ij}^{\Delta t} &= \frac{e_{\Delta t}^{sup}(Upper(\Delta t)-\Delta t)+e_{\Delta t}^{inf}(\Delta t-Lower(\Delta t))}{Upper(\Delta t)-Lower(\Delta t)} \\ e_{ij}^{\Delta s} &= \frac{e_{\Delta s}^{sup}(Upper(\Delta s)-\Delta s)+e_{\Delta s}^{inf}(\Delta s-Lower(\Delta s))}{Upper(\Delta s)-Lower(\Delta s)} \end{cases}

经过求和得到最终的嵌入:

{E(Δ)=Sum(E(Δt))+Sum(E(Δs))Rn×nE(N)=Sum(E(Nt))+Sum(E(Ns))RL×n\begin{cases}E(\Delta)=Sum(E(\Delta^t))+Sum(E(\Delta^s)) \in \mathbb{R}^{n\times n} \\ E(N)=Sum(E(N^t))+Sum(E(N^s)) \in \mathbb{R}^{L\times n} \end{cases}

Self-Attention Aggregation Layer

首先是第一个 Attention,主要用用来考虑轨迹中有不同距离和时间间隔的两次 check-in 的关联程度,对轨迹内的访问分配不同的权重,具体来说:

S(u)=Attention(E(u)WQ,E(u)WK,E(u)WV,E(Δ),M)S(u)=\text{Attention}(E(u)W_Q, E(u)W_K, E(u)W_V, E(\Delta), M)

其中,

Attention(Q,K,V,Δ,M)=(Msoftmax(QKT+Δd))V\text{Attention}(Q,K,V,\Delta,M)=\left(M*\text{softmax}(\frac{QK^T+\Delta}{\sqrt{d}}) \right)V

其中MM为 mask 矩阵。

Attention Matching Layer

第二个 Attention 的作用是根据用户轨迹,在候选位置中召回最合适的 POI,并计算概率。

A(u)=Matching(E(l),E(u),E(N))A(u)=\text{Matching}(E(l), E(u), E(N))

其中,

Matching(Q,K,N)=Sum(softmax(QKT+Nd))\text{Matching}(Q,K,N)=\text{Sum}\left( \text{softmax}(\frac{QK^T+N}{\sqrt{d}})\right)

Balanced Sampler

因为正负样本不均衡,优化交叉熵损失不再有用。这篇论文将交叉熵损失中使用的负样本数量设置为超参数ss,在训练的每一步随机采样负样本,称为平衡采样器。

imi(logσ(ak)+(j1,j2,,js)[1,L](j1,j2,,js)k)log(1σ(aj)))-\sum_i \sum_{m_i}\left( \log \sigma(a_k) + \sum_{\begin{aligned}(j_1,j_2,\cdots,j_s)\in [1,L] \\ (j_1,j_2,\cdots,j_s)\neq k) \end{aligned}} \log(1-\sigma(a_j)) \right)

Experiments

Datasets

Recommendation Performance

Ablation Study

总结

总体来说还是比较经典的一个方法吧,在很多其他论文的 Baseline 里都能看到,算是基于 Attention 的方法里比较好的一个模型了。

参考资料