用于下一个POI推荐的图闪回网络

摘要

介绍

下一个POI推荐问题的现有解决方案可以分为两类:基于序列的解决方案和基于图的解决方案。

限制与挑战：

  • 图结构

    以前的方法构造定制的同构POI图，只有一种类型的节点和边。此外，图只关注poi之间的连通性，忽略了边的权值。很少有研究提出使用包含多种节点和边的异构图来获得基于学习的加权图。

  • POI表征

    现有的基于图的模型直接在定制图上应用图神经网络(GNNs)，根据邻居采样策略，通过其邻居来改进每个POI的表示，而不需要证明。因此，在GNNs中很难避免一些无用的操作(如特征转换)。此外，它们对每个POI近邻的重要性(即权重系数)的学习过程是不透明的，这可能会降低模型的有效性。

  • 个性化推荐

    大多数现有的方法只是简单地将用户特征向量(即嵌入)和模型输出连接起来，以执行个性化的POI推荐。然而，使用如此简单的操作无法考虑到用户对不同POIs的一般偏好。还有一些研究将用户和POI表示形式串联起来，作为模型的输入来反映个性化的用户偏好。然而，用户偏好可能受到许多因素的影响(例如，时间、地点、POI类别等)。仅仅通过连接用户和POI表示很难获得准确的个性化用户偏好。

为此，我们提出了图-闪回模型来解决上述三个挑战。

针对第一个局限性，我们首先构建了具有较强表示能力的时空知识图(STKG)。基于我们的STKG，我们使用知识图嵌入(KGE)算法来学习每个节点和每个边的表示。其次，我们利用学习到的表示法构造POI过渡图，这是一种基于学习的加权图。我们学习的POI过渡图是由STKG推导而来的，在接下来的学习过程中，权重系数是恒定的。图1显示了我们学习的图和定制的图之间的区别。习得的POI图明确地显示了它的不同邻居(不包括它自己)对每个POI的重要性。然而，以往的基于图的方法将GNN应用于构造的连通性图上，学习每个POI的邻结点的权系数，这些权系数是时变的、非透明的[11,13]。

针对第二个限制，在POI过渡图上应用了简化的GCN (Graph Convolution Network)，丰富了每个POI的表示，然后将其输入到基于rnn的模型中，为用户提供更好的推荐服务。我们的POI转换图能够反映POI之间的转换模式。同时，它可以与其他顺序模型无缝集成，增强顺列转换规律捕获能力。

针对第三个限制，我们设计了一个相似度函数，根据当前位置和时间测量不同用户的偏好，进行个性化的POI推荐。

贡献

  • 提出了一种新的时空知识图(STKG)，可以直接用于学习反映POI之间转换模式的POI图。据我们所知，这是第一个利用异构知识图学习均匀加权POI图的方法。
  • 提出了一种新的基于rnn的模型，图-闪回，将学习到的POI转移图无缝地集成到基于rnn的模型中，以更好地捕获顺序转移模式。此外，为了进一步提高个性化POI推荐的有效性，我们用一个精心设计的新相似函数来增强我们的模型，该相似函数度量不同用户的偏好。
  • 我们在两个真实的数据集上进行了广泛的实验，以评估图闪回的性能。结果表明，图闪回算法在精度方面明显优于现有的求解方法。

相关工作

上述方法都没有考虑从异构图中显式学习加权POI转移图，这在一定程度上反映了转移模式。

知识图嵌入

知识图(KG)是一个异构网络，它在图中包含多种类型的实体(节点)和关系(边)。这样，根据图中不同的边可以得到一个实体的多个属性。此外，通过这些不同的关系还可以发现实体之间的高阶相关性。简而言之，KG具有很强的表示能力。知识图嵌入(Knowledge Graph Embedding, KGE)是将一个知识图嵌入到一个低维空间中，学习每个实体和每个关系的表示。学习到的嵌入仍然可以保持图的固有性质。KGE算法可分为两类:平移距离模型，如TransE、TransH、TransR等;语义匹配模型，如DistMult。在本研究中，我们主要关注翻译距离模型，将关系视为平移操作，根据不同的关系计算不同实体之间的距离(分数)。

image-20221107192739053

问题描述

定义 1：(Check-in) $c=(u,l,t)$

定义 2：(User trajectory) $T_{u_i}={c_1,c_2,…,c_m}$

定义 3：(Knowledge graph)image-20221107193408653

V表示实体，即用户集和POI集的并集

E表示边，代表关系类别，visiting, temporal, spatial, and social

A代表实体类别集合

B代表关系类别集合

实体类别函数

关系类别函数

R表示主题-属性-对象三元组的集合 $r=(h,p,l)$

定义 4：(Next POI recommendation) 给定知识图G，用户$u_i$，用户访问轨迹，目标是输出用户最想访问的前k个POI点

转换图学习

时空知识图(STKG)

我们的目标是充分利用所有用户记录的签入来学习poi之间的转换模式。

  • 访问关系的构建 $(u,r_v,l)$

  • 时间关系的构建 $(l_1,r_t,l_2)$

  • 空间关系的构建

    基于阈值的方法：

    设定了一个预先定义的距离阈值，所有具有空间关系的POI点与l的距离小于设定的阈值

    基于排名的方法：
    取距离l最近的top-k个POI

  • 社交关系的构建 $(u_1,r_f,u_2)$

目标函数

给定G，目标是找到一个嵌入函数image-20221107201100194将实体间的关系构建成一个维的特征向量。

使用了基于平移距离模型的知识图嵌入算法，transsE、TransH和TransR来学习知识图中每个实体和每个关系的表示。

TransH的基本思想是用不同的超平面表示不同的关系空间，将关系视为超平面上的平移操作。

对于一个三元组(h,r,t)，相应的实体嵌入h和t首先被投影到超平面上，

image-20221108110217005

接下来使用评分函数g（.）衡量三元组不正确的可能性。值越低表示正确的可能性越大

image-20221108110245533

到目前为止，已经学习了每个实体和每个关系的表示。下一个目标是设计一个时间相似性函数 s（.）用于捕获poi之间的转换模式，受KGE算法的启发，我们计算两个POI之间的相似度

image-20221107203118717

d(.)是距离函数，l1 l2是学习到的嵌入，rt是时间关系嵌入

接下来构造POI转换矩阵M ，为了减少空间成本，我们构造了一个稀疏过渡图G

image-20221108111507755

接下来对G归一化，得到POI转移图A

image-20221108111734775

选择单纯考虑时间关系来构造POI转移图。

模型框架

本节介绍了Graph-Flashback网络框架,包括:(i)嵌入层学习用户和POIs的密度表示,(ii)GCN丰富POIs的表示我们学会了POI过渡图,(3)聚合层学习聚合加权隐状态的时空和用户偏好效应作为输出,和(iv)预测层,建议下个POI的输出和用户嵌入聚合。

image-20221107200930417

嵌入层

对用户和POI信息进行了编码，稍后将与其他模块进行组合以进行推荐。先将用户轨迹分割为多个等长度的子序列，接下来，将每个子序列送入嵌入层。每个POI由一个独热编码向量$e^l$表示，不同的用户有不同的偏好，每个用户也由一个独热编码向量$e^u$表示。嵌入层将用户和POIs的单热向量转换为相应的低维密集表示。

GCN层

使用图卷积网络(GCN)来改进表示，在LightGCN成功的激励下，我们只关注GCN的核心功能:在我们的GCN层中邻居聚合。

转移图A不能反映它对每一个POI的影响，为了解决这个问题，我们添加了单位矩阵$I$得到新的转移矩阵，并归一化

image-20221108112401909

image-20221108112419953

用新的过渡矩阵来丰富每个POI的表示

image-20221108112604879

聚合层

聚合层由一个捕获顺序模式的循环模块和一个考虑历史隐藏状态对当前隐藏状态影响的聚合模块组成。将GCN层的输出，即更新的POIs嵌入和用户偏好嵌入反馈到聚合层。具体来说，我们使用基本rnn作为循环模块来获取所有隐藏状态。但是，直接使用这些隐藏状态进行推荐，不能充分利用用户签到轨迹所包含的时间周期性和空间上下文。特别是，用户最有可能定期访问一些poi(如家、办公室等)和那些距离较近的poi。

我们利用时空上下文设计相似函数w(.)来反映历史隐含状态和当前隐含状态的相关性

image-20221108112907109

$hvc(x)=\frac{1+cosx}{2}$反映了时间周期，$ΔD{i,j}, ΔT{i,j}$代表时间间隔和空间间隔，$α,β$代表时空衰减权重

为了将用户偏好融入到函数w(.)中，构建了一个稀疏的用户-偏好图$G_p$

image-20221108123810478

P为用户偏好矩阵，同时考虑了用户偏好权重和时空权重：

image-20221108131836459

每一步的历史隐藏状态转换为当前隐藏状态：

image-20221108131926041

预测层

将每个时间步聚合层的输出和用户嵌入输入到一个全连接层：

image-20221108132146218

最后使用交叉熵损失函数：

image-20221108132236957

实验

数据集

我们在两个广泛使用的真实世界数据集(Gowalla 3和Foursquare 4)上评估了我们的图-闪回模型。Gowalla包含了从2009年2月到2010年10月的签入。Foursquare[30]收集于2012年4月至2014年1月。每次签入都由userID、POIID、纬度、经度和时间戳组成。按照[29]中的预处理技术，我们丢弃签入次数少于100的不活动用户，并按时间戳升序对每个用户的签入进行排序。每个用户的前80% check-in被分成多个长度相等的序列(如20个)，作为训练集。同样，剩下的20%作为测试集。此外，我们还利用训练集构建了我们的时空知识图谱。

image-20221107204919904

基线

image-20221107204939775

评价矩阵

我们使用两个广泛使用的评估指标:平均Accuracy@K (Acc@K)和平均倒数秩(MRR)跟随[29]来评估图闪回的性能。

image-20221107205138909

image-20221107205149401

设置

我们使用第二种方案(即基于排名的方案)来构建知识图，并选择TransE[1]来构建我们的POI转移图。在构造POI过渡图A，User-POI偏好图时，$k_t,k_p={10,20,30,50,100}$。将隐藏状态和用户(POI)嵌入维数设为10。

结果与分析

image-20221107210058780

在Gowalla和Foursquare数据集上的结果表明，我们提出的图形闪回在所有评估指标下显著优于所有其他最先进的基线方法。具体而言，在Gowalla数据集的Acc@1、Acc@5、Acc@10和MRR上，Graph-Flashback的性能优于Flashback方法，分别为30.57%、24.36%、22.33%和25.82%。此外，与Foursquare数据集上的Flashback相比，Graph-Flashback获得了8.04%的平均改进。综上所述，上述发现清楚地显示了Graph-Flashback的优越性。

与闪回相比，我们的图闪回总体上有很大的改进。原因是POI转换图A可以通过改进POI嵌入来帮助更好地捕获POI之间的转换模式。此外，在充分考虑用户偏好的前提下，个性化的POI推荐可能会显著受益。同样，STAN是一个基于注意力的最新模型，考虑了过去历史签入的影响。然而，根据我们的实验结果，它的性能很差。其原因是其训练方案可能使模型的性能依赖于所选择的用户。

比较Foursquare数据集上的性能改进，我们发现Graph-Flashback在Gowalla数据集上的性能更好。很明显，我们提出的图-闪回模型具有很强的处理稀疏数据的能力

消融实验

我们观察到在GCN层中使用的POI过渡图有助于提高模型的性能。学习到的图可以丰富每个POI的表示，进一步帮助顺序模型捕获POI之间的转换模式。

我们发现适当使用用户偏好可以提高模型的性能。当我们将学习到的用户-POI偏好图集成到时空上下文中时，个性化POI推荐的性能可以得到提高。

我们注意到，图形闪回比图形闪回w/o的性能略好，究其原因，用户偏好的影响已经部分体现在GCN上。这有助于更好地隐式表示每个POI。另外，更简单的TransE算法可能更适合我们的知识图。

image-20221107210021988

对比实验

从图4可以看出，由第二种方案(即基于秩的)和TransE算法构造的时空知识图学习而来的POI过渡图在Gowalla数据集上可以获得更好的模型性能。原因可能是第二种方案构建的时空知识图谱包含的内容较多空间边。

如图5所示，使用POI图的结果明显好于在Foursquare数据集中不使用任何图的结果。此外，我们可以发现，通过不同的KGE算法学习到的POI转移图优于定制图。这说明我们所学习的POI图能够更准确地反映POI之间的相关性。

image-20221107210000272

总结