【论文阅读】Modeling Spatio-temporal Neighbourhood for Personalized Point-of-interest Recommendation

Metadata

authors:: Xiaolin Wang, Guohao Sun, Xiu Fang, Jian Yang, Shoujin Wang
container:: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
year:: 2022
DOI:: 10.24963/ijcai.2022/490
rating:: ⭐⭐⭐
share:: false
comment:: 强调用户偏好，通过构建 TKG 图，以时间片的形式聚合 K 个用户/场所的邻居信息并打分，以此作为抽象表示。亮点主要在于聚合用户/场所邻居的方法。

---

前言

刚出炉的 IJCAI 2022 的一篇论文：Modeling Spatio-temporal Neighbourhood for Personalized Point-of-interest Recommendation

问题描述

（next POI recommendation）分别给定用户集合$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 \}$，表示用户$u_i$在$t_i$时刻访问了$l_i$。我们的任务是预测用户可能访问的地点，模型的输入是带 GPS 信息的用户历史访问序列$Y$，以及时间知识图 TKG $\mathcal{G}$。模型的输出是位置概率矩阵$P$。

（Temporal Knowledge Graph）时间知识图 TKG $\mathcal{G}$是一个四元组，$\mathcal{G}=\{(e_u,r,e_l,t)\vert e_u \in E_u, r\in R, e_l\in E_l, t\in T\}$，分别表示用户，访问关系，地点以及时间。

（Receptive Field）定义$H_{U/L,U}^{(D)}$为$D$层用户/POI 接受域；$e_{u'/l'}$为用户/POI 邻居实体；$N^{u/l}$为邻居实体集合。

Overview

论文根据实际生活，提出了 3 个点以强调用户偏好：

1. Personal preference：不同用户对于同个场所存在偏好。例如在 12:00，用户 A 将 cafe 当做 dining palce，因为根据历史序列发现他在这个时刻经常访问 sushi bar，pizzeria 等场所；而用户 B 则将 cafe 当做 social place，因为根据历史序列发现他在这个时刻经常访问 go club，card room 等场所。

2. Dynamic preference：同一用户对于同一场所的偏好经常会发生变化。例如用户 B 在 12:00 将 cafe 当做 social place，而在 17:00 则作为 dining palce。

   

3. Personal acceptance to distance/time：用户的选择会受到距离和时间的影响。例如，用户 B 相比于用户 A 有更高的概率访问位置 L，因为根据用户 B 之前的轨迹比用户 A 有更长的距离/时间间隔。

   

在以前的方法中，并没有捕捉到用户的动态偏好。同时以前的方法大多将用户到 POI 的距离/时间视为客观的因素，这忽略了个人对距离/时间的接受程度，从而限制了他们的推荐性能。

本论文为了克服现有的基于序列和基于 Knowledge Graph (KG)的推荐方法的局限性，在 POI 推荐中引入了带有时间信息的知识图谱（称为 TKG），包括用户和带有时间戳的位置。在 TKG 中，考虑了用户对位置的个人偏好，并使用了注意机制来衡量每个用户对距离和时间的接受程度。论文的主要贡献如下：

1. 提出了一个时空图卷积注意力网络，通过学习 TKG 更好地学习用户偏好；
2. 考虑了用户对地点的个人偏好；
3. 使用注意力机制衡量每个用户对距离和时间的接受程度。

STGCAN

模型总体框架如下图所示：

Embedding Layer

在 Embedding 层，将 user U，location L，timestamps T分别进行 Embedding。

$$E_U \in \mathbb{R}^{N\times E}, E_L \in \mathbb{R}^{L\times E}, E_T \in \mathbb{R}^{K\times E}$$

其中 timestamps 为 hour of week。

Neighbour Aggregation Layer

User Neighbour Aggregation Layer

用户接受域（User-receptive-feld）是用来在 TKG 上聚合用户邻居实体以进行用户表示的。

具体来说，对于 TKG 上的一个四元组$(e_u,r,e_l,t)$，我们可以找到用户$e_u$的邻居四元组$(e_{u'}, r, e_l, t') (t' < t)$，邻居节点$e_{u'}$与$e_u$都访问过场所$e_l$。根据访问时间找到最近的 K 个邻居，即$N_t^u = \{ e_t^{u',1}, e_t^{u',2}, \cdots, e_t^{u',K} \}$。如下图所示：

上面提到的接受域也就是寻找$K$个邻居的范围域。上图为 3 层的用户接受域。

然后，为了计算$K$个邻居实体与目标用户的相关性，用时空评分函数$I$进行评分：

$$\begin{aligned}\lambda_{st}^{u,u'} &= I = I_s + I_t = I_t\{(e_u, r, e_l, t), (e_{u'}, r, e_l, t') \} \\ &= \exp(-\gamma\vert t-t' \vert) \end{aligned}$$

其中$\gamma$为超参数。

最后，将计算的得到的$K$个时空评分通过 softmax 进行归一化。将这$K$个评分经过一个线性变换，最后的输出作为目标用户的表示。

$$\alpha_{st}^{u,i} = \frac{\exp(\lambda_{st}^{u,i})}{\sum_{i=1}^K \exp(\lambda_{st}^{u,i})}$$

$$e_t^u \leftarrow e_t^u + \sigma(\sum_{i=1}^K \alpha_{st}^{u,i} \cdot e_t^{u',i})$$

在每一层接受域中，更新方程如下：

$$e_t^u[h+1] = e_t^u + \sigma(\sum_{i=1}^K \alpha_{st}^{u,i} \cdot e_t^{u',i}[h])$$

Location Neighbour Aggregation Layer

位置接受域（Location-receptive-feld）是为了聚合 TKG 上的邻居实体来进行位置表示。

类似地，找到目标位置$e_l$的$K$个邻居四元组$(e_{u'}, r, e_{l'}, t') (t' < t)$，根据用户的访问不同位置的时间进行排序，即$N_t^{l,u} = \{ e_t^{l_1',u}, e_t^{l_2',u}, \cdots, e_t^{l_K',u} \}$。如下图所示：

与聚合用户邻居实体不同的是，聚合位置邻居实体时的时空评分函数$I$还通过 GPS 计算了不同位置之间的 Haversine 距离：

$$\begin{cases} I_s = I_s(GPS_l, GPS_{l'_u}) = \frac{1}{\theta + H(GPS_l, GPS_{l'_u})} \\ I_t = I_t\{(e_u, r, e_l, t), (e_{u'}, r, e_{l'}, t')\} = \frac{1}{\theta + \vert t-t' \vert} \end{cases}$$

最后仍是与聚合用户实体类似的更新方程：

$$\alpha_{st}^{l,l'_u} = \frac{\exp(\lambda_{st}^{l,l'_u})}{\sum_{i=1}^K \exp(\lambda_{st}^{l,l'_u})}$$

$$e_t^{l,u} \leftarrow e_t^{l,u} + \sigma(\sum_{i=1}^K \alpha_{st}^{l,l'_u} \cdot e_t^{l'_u})$$

$$e_t^{l,u}[h+1] = e_t^{l,u} + \sigma(\sum_{i=1}^K \alpha_{st}^{l,l'_u} \cdot e_t^{l'_u}[h])$$

Spatial-Temporal Interval Aware Attention Layer

在邻居聚合之后，用户和位置的表示被输入到时空间隔感知注意层，这是一个测量空间距离和时间的注意层。

采用插值嵌入的方式，将时空间隔嵌入用户和位置的表示。

这里采用的方法和[[@luo2021stan]]比较像。

$$\begin{cases}d_s = \frac{[vsl \cdot (\Delta s_{max} - \Delta s) + vsu \cdot (\Delta s - \Delta s_{min})] \cdot inv\_s}{(\Delta s_{max} - \Delta s_{min}) + \theta} \\ d_t = \frac{[vtl \cdot (\Delta t_{max} - \Delta t) + vtu \cdot (\Delta t - \Delta t_{min})] \cdot inv\_t}{(\Delta t_{max} - \Delta t_{min}) + \theta} \end{cases}$$

其中$vsl,vsu,vtl,vtu \in \mathbb{R}^E$以及$inv\_s,inv\_t \in \mathbb{R}^{N\times E}$均为可训练参数，分别表示最小/最大的时间/空间间隔以及用户的相对时空比例权重。

然后通过 self attention 将得到的时空间隔嵌入用户和位置的表示。

这里感觉说的不清不楚的，差值后如何使用，还有 self attention 也只是文字提了一嘴。还是说这里的 attention 只是下面的那两个全连接，没搞明白。

再次加入时间信息：

$$U_{Att} = W_d \cdot (E_U + E_L + E_T) + b$$

$$L_{Att} = W_Q[W_d \cdot (E_L + E_T)]^T + b$$

最后计算得到用户访问概率：

$$P=(L_{Att})^T \times U_{Att}$$

Neural Network Training

整体算法如下：

使用交叉熵损失函数计算损失，负样本为随机采样：

$$\mathcal{L} = -\sum_{j\in L}(\log \sigma(p_j) + \sum_{j'\in L}^s \log \sigma(1-p_{j'}^N)) -\lambda\Theta$$

其中$\Theta=\{ vsu,vsl,vtu,vtl,inv\_t,inv\_s,W^Q,\cdots \}$为可学习参数，$\sigma$为激活函数。

Experiments

Datasets

Result

Impact of embedding dimension

Impact of depth of receptive feld

Impact of neighbour entity size

总结

总的来说感觉模型本身并不复杂，但有些细节没搞明白，想去看代码结果代码也写得不清不楚，就只是把框架代码放了上来。感觉主要的亮点还是在聚合邻居节点的时候采用的方法，在时间维度上选取当前用户/POI 的邻居，并且聚合也不是硬套 GNN，而是简单的采用一个打分函数。另外就是 attention 层只看他描述的话感觉并不 attention。

参考资料

• [1] Modeling Spatio-temporal Neighbourhood for Personalized Point-of-interest Recommendation