【论文阅读】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={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 \},表示用户uiu_itit_i时刻访问了lil_i。我们的任务是预测用户可能访问的地点,模型的输入是带GPS信息的用户历史访问序列YY,以及时间知识图TKG G\mathcal{G}。模型的输出是位置概率矩阵PP

Temporal Knowledge Graph)时间知识图TKG G\mathcal{G}是一个四元组,G={(eu,r,el,t)euEu,rR,elEl,tT}\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)定义HU/L,U(D)H_{U/L,U}^{(D)}DD层用户/POI接受域;eu/le_{u'/l'}为用户/POI邻居实体;Nu/lN^{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。

EURN×E,ELRL×E,ETRK×EE_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上的一个四元组(eu,r,el,t)(e_u,r,e_l,t),我们可以找到用户eue_u的邻居四元组(eu,r,el,t)(t<t)(e_{u'}, r, e_l, t') (t' < t)邻居节点eue_{u'}eue_u都访问过场所ele_l。根据访问时间找到最近的K个邻居,即Ntu={etu,1,etu,2,,etu,K}N_t^u = \{ e_t^{u',1}, e_t^{u',2}, \cdots, e_t^{u',K} \}。如下图所示:

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

然后,为了区分KK个邻居实体与目标用户的相关性,用时空评分函数II进行评分:

λstu,u=I=Is+It=It{(eu,r,el,t),(eu,r,el,t)}=exp(γtt)\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为超参数。

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

αstu,i=exp(λstu,i)i=1Kexp(λstu,i)\alpha_{st}^{u,i} = \frac{\exp(\lambda_{st}^{u,i})}{\sum_{i=1}^K \exp(\lambda_{st}^{u,i})}

etuetu+σ(i=1Kαstu,ietu,i)e_t^u \leftarrow e_t^u + \sigma(\sum_{i=1}^K \alpha_{st}^{u,i} \cdot e_t^{u',i})

在每一层接受域中,更新方程如下:

etu[h+1]=etu+σ(i=1Kαstu,ietu,i[h])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上的邻居实体来进行位置表示。

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

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

{Is=Is(GPSl,GPSlu)=1θ+H(GPSl,GPSlu)It=It{(eu,r,el,t),(eu,r,el,t)}=1θ+tt\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}

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

αstl,lu=exp(λstl,lu)i=1Kexp(λstl,lu)\alpha_{st}^{l,l'_u} = \frac{\exp(\lambda_{st}^{l,l'_u})}{\sum_{i=1}^K \exp(\lambda_{st}^{l,l'_u})}

etl,uetl,u+σ(i=1Kαstl,luetlu)e_t^{l,u} \leftarrow e_t^{l,u} + \sigma(\sum_{i=1}^K \alpha_{st}^{l,l'_u} \cdot e_t^{l'_u})

etl,u[h+1]=etl,u+σ(i=1Kαstl,luetlu[h])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]]比较像。

{ds=[vsl(ΔsmaxΔs)+vsu(ΔsΔsmin)]inv_s(ΔsmaxΔsmin)+θdt=[vtl(ΔtmaxΔt)+vtu(ΔtΔtmin)]inv_t(ΔtmaxΔtmin)+θ\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,vtuREvsl,vsu,vtl,vtu \in \mathbb{R}^E以及inv_s,inv_tRN×Einv\_s,inv\_t \in \mathbb{R}^{N\times E}均为可训练参数,分别表示最小/最大的时间/空间间隔以及用户的相对时空比例权重。

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

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

再次加入时间信息:

UAtt=Wd(EU+EL+ET)+bU_{Att} = W_d \cdot (E_U + E_L + E_T) + b

LAtt=WQ[Wd(EL+ET)]T+bL_{Att} = W_Q[W_d \cdot (E_L + E_T)]^T + b

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

P=(LAtt)T×UAttP=(L_{Att})^T \times U_{Att}

Neural Network Training

整体算法如下:

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

L=jL(logσ(pj)+jLslogσ(1pjN))λΘ\mathcal{L} = -\sum_{j\in L}(\log \sigma(p_j) + \sum_{j'\in L}^s \log \sigma(1-p_{j'}^N)) -\lambda\Theta

其中Θ={vsu,vsl,vtu,vtl,inv_t,inv_s,WQ,}\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。

参考资料