【论文阅读】Graph-Flashback Network for Next Location Recommendation

Metadata

authors:: Xuan Rao, Lisi Chen, Yong Liu, Shuo Shang, Bin Yao, Peng Han
container:: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
year:: 2022
DOI:: 10.1145/3534678.3539383
rating:: ⭐⭐⭐⭐
share:: true
comment:: 构建 STKG 并设计相似度函数生成 POI 转移矩阵，利用 POI 转移矩阵对 POI 进行加强并获取用户偏好信息，模型主体框架为 RNN，同时在隐藏层更新过程中手动加入额外信息。另外几个相似度函数也是亮点。

前言

依旧是 POI 推荐方向的论文，2022KDD 最新的：Graph-Flashback Network for Next Location Recommendation

主要参考了[[@yang2020location]]中的模型框架：Location prediction over sparse user mobility traces using RNNs: Flashback in hidden states!

问题描述

分别给定用户集合U={u1,u2,⋯ ,u∣U∣}\mathcal{U} = \{ u_1, u_2, \cdots, u_{\vert \mathcal{U} \vert} \}以及 POI 集合L={l1,l2,⋯ ,l∣L∣}\mathcal{L} = \{ l_1, l_2, \cdots, l_{\vert \mathcal{L} \vert} \}，其中每个位置lil_i都有一个对应的(lat,lon)(lat, lon)坐标相关联。

（check-in）一个 check-in 可以表示为c=(u,l,t)c=(u,l,t)，即用户uu在tt时刻访问地点ll。

（user trajectory）用户轨迹是由特定用户的一系列时间顺序的签到记录来定义的，即Tui={c1,c2,⋯ ,cm}T_{u_i} = \{ c_1, c_2, \cdots, c_m \}。

（knowledge graph）知识图定义为G=(V,E,A,B,ϕ,ψ,R)\mathcal{G} = (V,E,\mathcal{A},\mathcal{B},\phi,\psi,\mathcal{R})，其中对于每一个实体v∈Vv\in V有ϕ(v)∈A\phi(v) \in \mathcal{A}，对于每一条边e∈Ee\in E有ψ(e)∈B\psi(e) \in \mathcal{B}。R\mathcal{R}为访问关系三元组集合，r=(h,p,l)r=(h,p,l)，例如(Bob,visit,aquarium)(Bob, visit, aquarium)。

（next POI recommendation）给定知识图G\mathcal{G}，每个用户uiu_i的的活动轨迹TuiT_{u_i}，预测用户uiu_i最可能去的 POI top-kk。

OverView

论文认为现有的方法存在以下一些问题：

  1. 图结构：现有的方法大多只是通过自定义一张同质的 POI 图，即只包含一种类型的节点和边，同时也忽略了边的权重问题；
  2. POI 表征：现有的方法通过 GNN 直接聚合邻居节点的信息，可能会导致一些无用的操作，也没有充分考虑学习过程中邻居节点的重要性；
  3. 个性化推荐：用户的偏好可能会受到许多因素的影响(例如，时间、位置、POI 类别等)，仅仅通过连接用户和 POI 表示难以学习。

为了解决上面这些问题，本文通过构建时空知识图（Spatial-Temporal Knowledge Graph，STKG）学习每个节点和边的特征表示，并以此构造 POI 转移图展现不同邻居的重要性。再使用 GCN 提取特征并输入到 RNN 中进行预测。主要贡献如下：

  1. 提出了一种新的时空知识图(STKG)，可以直接用于学习反映 POI 之间转换模式的 POI 图；
  2. 提出了一种新的基于 RNN 的模型，Graph-Flashback，将学习到的 POI 转换图融入基于 RNN 的模型中，以便更好地捕获序列转换模式；
  3. 提出新的相似性函数来增强模型，度量不同用户的偏好。

Transition Graph Learning

Spatial-Temporal Knowledge Graph

与传统的知识图不同，STKG 将传统的用户-POI 交互图，POI 之间的时空相关性和用户之间的朋友关系结合起来。

对于一幅时空知识图G=(V,E,A,B,ϕ,ψ,R)\mathcal{G} = (V,E,\mathcal{A},\mathcal{B},\phi,\psi,\mathcal{R})，其中VV为用户集合与 POI 集合的交集U∪L\mathcal{U} \cup \mathcal{L}；EE为边集合包含四种关系：visiting，temporal，spatial，social；

  • visiting relation：(u,rv,l)(u,r_v,l)，表示用户uu访问位置ll；
  • temporal relation：(l1,rt,l2)(l_1,r_t,l_2)，表示某个用户顺序访问l1,l2l_1,l_2；
  • spatial relation：(l1,rs,l2)(l_1,r_s,l_2)，表示位置l1l_1和l2l_2的距离接近，这里考虑距离阈值以及距离排名；
  • social relation：(u1,rf,u2)(u_1,r_f,u_2)，表示用户u1u_1和u2u_2是朋友关系。

Objective function

Knowledge Graph Embedding

接着论文使用 Knowledge Graph Embedding(KGE) 算法对 STKG 进行 Embedding。

KGE 算法主要基于 translation distance model（翻译距离模型），包含：TransE，TransH，TransR。

translation distance model 可以理解为使用基于距离的评分函数。

以 TransH 为例，TransH 的基本思想是利用不同的超平面来表示不同的关系空间，并将关系作为超平面上的平移运算。

  1. 给定一个三元组(h,r,t)(h,r,t)，首先将实体h,t\boldsymbol{h}, \boldsymbol{t}投影到超平面wr\boldsymbol{w_r}：

    h⊥=h−wrThwrt⊥=t−wrTtwr\begin{aligned}\boldsymbol{h_\perp}&=\boldsymbol{h-w_r^Thw_r} \\ \boldsymbol{t_\perp}&=\boldsymbol{t-w_r^Ttw_r} \end{aligned}

    其中h⊥,t⊥\boldsymbol{h_\perp},\boldsymbol{t_\perp}分别为h,t\boldsymbol{h},\boldsymbol{t}在超平面的 Embedding。

  2. 给定得分函数：

    gr(h,t)=∥h⊥+dr−t⊥∥22\boldsymbol{g_r(h,t)} = \Vert \boldsymbol{h_\perp + d_r - t_\perp} \Vert_2^2

    其中dr\boldsymbol{d_r}为关系rr在超平面的 Embedding。gr(h,t)\boldsymbol{g_r(h,t)}值越低表示三元组越准确。

到目前为止，已经学习了每个实体和每个关系的表示。

Temporal similarity

另一方面，论文通过定义时间相似性函数s(⋅)\boldsymbol{s}(\cdot)，来计算 POI l1,l2l_1, l_2之间的相似性，以获取两者间的时间关系。以 TransE 为例，相似性函数如下：

s(l1,l2)=e−d(l1,l2)d(l1,l2)=∥l1+rt−l2∥\begin{aligned} \boldsymbol{s(l_1,l_2)} &= e^{-\boldsymbol{d(l_1,l_2)}} \\ \boldsymbol{d(l_1,l_2)} &= \Vert \boldsymbol{l_1+r_t-l_2} \Vert \end{aligned}

其中d(⋅)\boldsymbol{d(\cdot)}为距离函数；l1,l2\boldsymbol{l_1}, \boldsymbol{l_2}分别为 POI l1,l2l_1,l_2的 Embedding 表示；∥⋅∥\Vert\cdot\Vert为 1 范式或 2 范式。

POI Transition Matrix

根据前面计算得到的 POI 之间的时间相似性，可以得到 POI 转移矩阵M∈R∣L∣×∣L∣\boldsymbol{M} \in \mathbb{R}^{\vert\mathcal{L}\vert \times \vert\mathcal{L}\vert}。考虑到内存消耗的问题，论文重新构造了一个稀疏矩阵：

G(i,j)={M(i,j),if POI lj∈Nk(li)0,otherwise\boldsymbol{G}(i,j) = \begin{cases} \boldsymbol{M}(i,j), &\text{if POI }l_j\in\mathcal{N}_k(l_i) \\ 0, &\text{otherwise} \end{cases}

其中i,j=1,2,⋯ ,∣L∣i,j=1,2,\cdots,\vert\mathcal{L}\vert。最后，为了对稀疏图G\boldsymbol{G}进行归一化，选取G\boldsymbol{G}的每一行中的最大值来构造一个对角矩阵D\boldsymbol{D}：

A=D−1G\boldsymbol{A=D^{-1}G}

此外论文发现，同时使用空间和时间关系时的模型性能并不比只使用时间关系时的性能好。因此，论文只选择考虑时间关系来构造 POI 转移图。

上面的这些步骤，简而言之就是通过 STKG 得到 POI 转移矩阵。

Model Framework

模型整体结构如下图所示：

看论文的时候感觉有点乱，这幅图感觉不怎么好看，简单说一下大概的流程：首先将 POI 进行 one-hot 编码得到 POI Embedding（Embedding Layer），然后利用之前得到的 POI 转移图并通过 GCN 对其进行更新，得到 updated POI embedding（GCN Layer）；另一方面根据用户的历史轨迹以及 updated POI embedding 得到用户偏好信息 user preference；接着将用户轨迹输入到 RNN，并使用时间、空间信息以及 user preference 更新隐藏层，得到最后的输出。

Embedding Layer

User and POI information contained in each check-in record is initially represented as one-hot vectors. However, it is difficult for a model to capture user preferences by using one-hot vector due to its sparsity. To this end, we propose to learn low dimensional dense representation for each user and each POI.

论文里说的头头是道的，但仔细一看不还是 one-hot 编码么。特别强调了将每个用户的轨迹序列TuiT_{u_i}分割为多个等长的子序列，这难道就是 low dimensional dense representation？好吧。

GCN Layer

之后，论文使用 GCN 更好地对 POI 进行特征表示，关于 GCN 的内容可以看我的另一篇文章：简单理解图神经网络 GNN，这里只进行简单的说明：首先在 POI 转移矩阵A\boldsymbol{A}加上单位矩阵I\boldsymbol{I}进行自连接：

A^=A+I\hat{\boldsymbol{A}} = \boldsymbol{A + I}

之后通过度矩阵进行归一化：

A^=D^−1A^\hat{\boldsymbol{A}} = \hat{\boldsymbol{D}}^{-1}\hat{\boldsymbol{A}}

其中D^=diag(A^)\hat{\boldsymbol{D}}=\text{diag}(\hat{\boldsymbol{A}})

不知道为什么好多论文都只是归一化，不弄对称归一化，又不麻烦，按道理来说还是对称归一化好一点，虽说应该影响不大。

最后使用新的 POI 转移矩阵对 Embedding Layer 得到的 POI 进行 refine：

X^=A^X\hat{\boldsymbol{X}} = \hat{\boldsymbol{A}}\boldsymbol{X}

其中X∈R∣L∣×d,X^∈R∣L∣×d\boldsymbol{X}\in\mathbb{R}^{\vert\mathcal{L}\vert\times d}, \hat{\boldsymbol{X}}\in\mathbb{R}^{\vert\mathcal{L}\vert\times d}分别表示更新前后的 POI Embedding。

简单来说这里的 GCN 的作用就是将 POI 转移矩阵融入到原本的 POI Embeding 中。

Aggregation Layer

聚合层主要由两个模块组成：recurrent module 和 aggregation module。

将 GCN 层的输出 updated POI embedding 和用户偏好输入到聚合层中。论文使用 RNN 获取隐藏层信息，然而，直接使用这些隐藏状态进行推荐，并不能充分利用用户签到轨迹中所包含的时间周期性和空间上下文。特别是，用户有可能规律地访问一些 POI（例如，家、办公室等），也可能访问距离较近的 POI。

因此论文根据时空上下文信息设计了一个相似度函数w(⋅)\boldsymbol{w(\cdot)}，它反应历史隐藏状态hj\boldsymbol{h_j}和当前状态hi\boldsymbol{h_i}的相关性：

w(ΔTi,j,ΔDi,j)=hvc(2πΔTi,j)e−αΔTi,je−βΔDi,j\boldsymbol{w}(\Delta T_{i,j}, \Delta D_{i,j}) = hvc(2\pi\Delta T_{i,j})e^{-\alpha\Delta T_{i,j}}e^{-\beta\Delta D_{i,j}}

其中hvc(x)=1+cos⁡x2hvc(x)=\frac{1+\cos{x}}{2}反映了时间上的周期性，ΔDi,j\Delta D_{i,j}和ΔTi,j\Delta T_{i,j}表示两个 POI 之间的空间/时间间隔，α,β\alpha,\beta表示时间/空间上的衰减权重。需要注意的是，相似度函数w(⋅)\boldsymbol{w(\cdot)}只关注 POI 之间的相关性，并没有考虑用户对 POI 的偏好。

因此接着考虑考虑用户对 POI 的偏好问题。根据_visiting_ 关系可以得到一个稀疏的用户-POI 偏好图G∈R∣U∣×∣L∣\mathcal{G}\in\mathbb{R}^{\vert\mathcal{U}\vert\times\vert\mathcal{L}\vert}，并将其和 POI Embedding 计算得到用户的 POI 偏好：

P=GpX^\boldsymbol{P} = \boldsymbol{\mathcal{G}_p}\hat{\boldsymbol{X}}

其中P∈R∣U∣×d\boldsymbol{P}\in\mathbb{R}^{\vert\mathcal{U}\vert\times d}为用户偏好矩阵。

最后，将用户偏好融入相似度函数，得到新的相似度函数w^(⋅)\boldsymbol{\hat{w}(\cdot)}，同时考虑了用户的偏好权重和时空权重：

w^(ΔTi,j,ΔDi,j)=w(ΔTi,j,ΔDi,j)e−∥Pu−elj∥\boldsymbol{\hat{w}}(\Delta T_{i,j}, \Delta D_{i,j}) = \boldsymbol{w}(\Delta T_{i,j}, \Delta D_{i,j})e^{-\Vert\boldsymbol{P_u-e^{l_j}}\Vert}

该聚合模块在每个时间步长ii上，将相似度函数w^(⋅)\boldsymbol{\hat{w}(\cdot)}和历史隐藏状态合并到当前的隐藏状态中，有：

h^i=∑j=0iw^j∗hj∑j=0iw^j\boldsymbol{\hat{h}_i} = \frac{\sum_{j=0}^i \hat{w}_j*\boldsymbol{h_j}}{\sum_{j=0}^i \hat{w}_j}

使用时间、空间信息以及用户偏好信息更新 RNN 隐藏层。

Prediction Layer

将聚合层每个时间步tt的输出h^t\boldsymbol{\hat{h}_t}以及用户 Embedding eu\boldsymbol{e^u}合并，进入全连接得到最终的输出：

y^tu=Wf[h^t∥eu]\boldsymbol{\hat{y}_t^u} = \boldsymbol{W}_f[\boldsymbol{\hat{h}_t} \Vert \boldsymbol{e^u}]

其中Wf∈R∣L∣×2d\boldsymbol{W}_f\in\mathcal{R}^{\vert\mathcal{L}\vert\times 2d}为可学习矩阵，∥\Vert表示连接操作。

使用交叉熵损失函数：

−∑u=1∣U∣∑i=1m(log⁡σ(yku)+∑j=1,j≠k∣L∣log⁡(1−σ(y^ju)))-\sum_{u=1}^{\vert\mathcal{U}\vert}\sum_{i=1}^m\left(\log\sigma(\boldsymbol{y_k^u})+\sum_{j=1,j\neq k}^{\vert\mathcal{L}\vert}\log(1-\sigma(\boldsymbol{\hat{y}_j^u}))\right)

其中mm为 check-in 序列的长度，σ\sigma为 softmax 函数。

实验

Datasets

Evaluation Metrices

评估指标为常用的 average Accuracy@K (Acc@K)以及 Mean Reciprocal Rank (MRR)：

Acc@k=1∣U∣∑u∈U∣SuK∩SuL∣∣SuL∣Acc@k=\frac{1}{\vert U \vert}\sum_{u\in U}\frac{\vert S_u^K \cap S_u^L \vert}{\vert S_u^L \vert}

MRR=1∣U∣∑u∈U1rankuMRR=\frac{1}{\vert U \vert}\sum_{u\in U}\frac{1}{rank_u}

Result

Ablation Study

通过消融实验，论文发现：

  1. 在 GCN 层中使用的 POI 转移图有助于提高模型的性能。学习到的图可以丰富每个 POI 的表示，从而进一步帮助顺序模型捕获 POI 之间的转换模式；
  2. 正确地使用用户偏好可以提高模型的性能。将学习到的用户-POI 偏好图整合到时空上下文中时，POI 推荐可以得到提高；

Contrast Study

另外这两个实验感觉不是那么清晰，第一个主要是POI筛选涉及的问题，也就是POI之间的绝对距离还是距离排名，第二个就是图的比较。

总结

看完论文别的不说，感觉乱七八糟的东西确实是有点多，但理清楚的话还是清晰的。另外知识图谱似乎在 POI 论文中看到的越来越多了，想来也是为了聚合更多的信息。使用 GCN 以及 POI 转移矩阵加强 POI Embedding 的想法似乎也有些东西；另外还有在 RNN 的隐藏层加时间空间用户偏好这些东西也是一种方法。另外几个相似度函数也值得思考。

参考资料