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

现有问题：

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

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

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

主要贡献：

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

Preliminaries

分别给定用户集合 $U=\{u_1, u_2, \cdots,u_U\}$ ， POI 集合 $L=\{l_1, l_2, \cdots, l_L \}$ ，时间集合 $T=\{t_1, t_2, \cdots, t_T \}$ 。

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

$tra(u_i)=\{ r_1, r_2, \cdots, r_n \}$

其中 $r_k=(u_i,l_k,t_k)$ 。

Trajectory Spatio-Temporal Relation Matrix

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

$\Delta_{i,j}^t=\vert t_i-t_j \vert \in \mathbb{R}^{n\times n}$

$\Delta_{i,j}^s=\text{Haversine}(GPS_i, GPS_j) \in \mathbb{R}^{n\times n}$

$\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 \in [1,L]$ 与访问轨迹上的位置 $j \in [1,n]$ 之间的球面距离：

$N_{i,j}^t=\vert t_{m+1}-t_j \vert \in \mathbb{R}^{L\times n}$

$N_{ij}^{s}=\text{Haversine}(GPS_i, GPS_j)\in \mathbb{R}^{L\times n}$

$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。之后再将三者相加：

$e^r=e^u+e^l+e^t \in \mathbb{R}^d$

Spatio-Temporal Embedding Layer

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

$\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}$

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

$\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}$

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

$\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)=\text{Attention}(E(u)W_Q, E(u)W_K, E(u)W_V, E(\Delta), M)$

其中，

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

其中 $M$ 为 mask 矩阵。

Attention Matching Layer

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

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

其中，

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

Balanced Sampler

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

$-\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)$