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

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

comment:: 构建 STKG 并设计相似度函数生成 POI 转移矩阵，利用 POI 转移矩阵对 POI 进行加强并获取用户偏好信息，模型主体框架为 RNN，同时在隐藏层更新过程中手动加入额外信息。另外几个相似度函数也是亮点。

前言

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

问题描述

​

​

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 之间的时空相关性和用户之间的朋友关系结合起来。

​

Objective function

Knowledge Graph Embedding

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

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

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

​

​

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

Temporal similarity

​

​

POI Transition Matrix

​

​

此外论文发现，同时使用空间和时间关系时的模型性能并不比只使用时间关系时的性能好。因此，论文只选择考虑时间关系来构造 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}Tui​​分割为多个等长的子序列，这难道就是 low dimensional dense representation？好吧。

GCN Layer

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

​

​

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

​

​

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

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

​

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

Aggregation Layer

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

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

​

​

​

​

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

Prediction Layer

​

​

实验

Datasets

Evaluation Metrices

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

​

Result

Ablation Study

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

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

Contrast Study

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

总结

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

参考资料

• 1(https://dl.acm.org/doi/abs/10.1145/3534678.3539383)