图注意力网络融合地理知识图谱的位置预测

Location Prediction with Graph Attention Network and Geographic Knowledge Graph

摘要

针对现有位置预测方法地理语义融合不足和用户地理偏好建模不充分的问题，提出一种地理知识图谱增强的图注意力网络位置预测算法。该方法整合多源地理数据构建层次化地理知识图谱，将用户、兴趣点及多粒度地理实体映射到统一语义空间；在此基础上，设计空间与关系感知图注意力网络学习用户全局地理偏好，并结合时空感知序列编码器建模局部时空转移模式，实现对用户多层次地理偏好的协同建模。在Foursquare-NYC和Foursquare-TKY数据集上的实验结果表明，所提方法的平均倒数秩（MRR）较最优基线分别提升19.52%和4.10%。结果证明，该方法能够有效提升下一位置预测精度。

Abstract

To address the limitations of existing location prediction methods in geographic semantic fusion and users’ geographic preference modeling, a graph attention network method for location prediction enhanced by a geographic knowledge graph is proposed. A hierarchical geographic knowledge graph with multi-source geographical data is constructed to map users, points of interest, and multi-granularity geographic entities into a unified semantic space. On this basis, a spatial and relation-aware graph attention network together with a spatiotemporal-aware sequential encoder is employed to model users’global geographic preferences and local spatiotemporal transition patterns, respectively. Experiments on the Foursquare-NYC and Foursquare-TKY datasets show that the mean reciprocal rank(MRR) of the proposed method are improved by 19.52% and 4.10%, respectively, compared with those of the strongest baseline. Experimental results demonstrate that the proposed method can effectively improve the accuracy of next location prediction.

Graphical abstract

关键词

位置预测 / 地理知识图谱 / 图注意力网络 / 基于位置的社交网络

Key words

location prediction / geographic knowledge graph / graph attention network / location-based social networks

随着移动互联网和定位技术的发展与普及，基于位置的社交网络（Location-Based Social Networks， LBSN）深入人们的生活之中。用户通过签到分享活动轨迹，产生大量时空行为数据。研究表明，人类轨迹具有较高可预测性，这为用户未来位置预测提供了重要基础^[1]。通过对用户历史签到序列进行分析与建模，预测其下一访问位置，在交通规划、个性化推荐等领域具有重要研究价值。

用户位置预测方法主要分为基于序列和基于图的方法。基于序列的方法侧重从用户历史轨迹中挖掘时序依赖与时空转移模式。早期方法多依赖马尔可夫链建模局部转移概率，难以刻画复杂的行为规律^[2-3]。近年来，循环神经网络（Recurrent Neural Network， RNN）因其序列建模能力被广泛应用^[4-5]，通过自适应划分用户签到序列^[6]，或设计基于时空上下文的隐藏状态检索机制^[7]来融入时空信息。然而，RNN类模型在捕获长程依赖上存在固有局限。注意力机制的引入有效缓解了这一问题，例如，将时间动态性融入Transformer框架中^[8]，或利用双层注意力捕捉非连续签到间的复杂时空关联^[9]。然而，此类方法通常仅关注单个用户轨迹，难以利用跨用户、跨轨迹的全局协同信息^[10]。

基于图的方法通过构建全局图结构来挖掘更丰富的关联关系。如利用混合超图卷积网络挖掘用户和兴趣点（Point of Interest, POI）的局部及全局交互^[11]。为克服静态图的局限性，引入自适应图学习，通过端到端优化图结构以更精确地建模地理依赖^[12]。进一步地，通过构建多个自适应图并结合对比学习，可以增强POI表示的多样性以捕获不同类型的依赖关系^[13]。与此同时，知识图谱因具有多实体、多关系和强语义表达能力^[14]，被引入位置预测任务，用于增强稀疏轨迹下的用户与POI表示。李佳等^[15]通过构建融合多源地理信息的知识图谱，增强稀疏轨迹的向量表示。Rao等^[16]通过时空知识图谱，基于知识图谱嵌入表示构建POI图，并集成到序列模型中，从而捕捉POI转移模式。

然而，用户移动行为本质上是地理空间认知与个体偏好共同作用的结果。现有方法在这一过程中仍存在两方面不足：一是多数方法将地理影响简化为点对点距离，难以同时刻画区域功能语义和空间可达性，因而无法有效建模用户在访问过程中形成的稳定地理偏好表征；二是现有方法多将地理信息视为POI的静态属性，缺乏对地理实体间结构语义关系的显式建模与推理，难以充分挖掘地理语义对位置预测的支撑作用。

针对上述问题，本文提出一种融合地理知识图谱和图注意力网络的位置预测算法（Location Prediction Based on Geographic Knowledge Graph and Graph Attention Network, GeoKGAT）。首先，整合多源地理数据与用户签到信息，构建层次化地理知识图谱，将用户、POI及多粒度地理实体纳入统一语义空间，并通过知识表示学习获得结构化地理语义表征。其次，设计空间与关系感知图注意力网络，在知识图谱上聚合高阶地理语义关联与空间邻近信息，建模用户的全局地理偏好。最后，引入时空感知序列编码器，对融合全局地理语义的签到序列进行建模，捕捉用户局部时空转移模式和短期动态偏好。在公开数据集上的实验结果表明，GeoKGAT在位置预测任务上优于多种代表性基线方法，验证了所提方法的有效性。

1 本文方法

1.1 问题定义

设U=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_m\right\}、P=\left\{p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_N\right\}、C=\left\{c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_k\right\}分别表示用户、POI和POI类别的集合，其中m、N、k分别为用户、兴趣点和兴趣点类别的数量。

定义1（用户签到） 用户签到记录Q=\left\{U,t,P,C\right\}表示用户U在时间t访问了类别为C的POI点P，用户U按时间排序的所有签到,构成其签到轨迹序列T_U=\left\{q_{\mathrm{1}},q_{\mathrm{2}},\dots ,q_n\right\}，其中n为轨迹长度。

定义2（知识图谱） 知识图谱是一种结构化的语义知识库^[17-19]，定义为G=(E,R,F)，其中E、R和F分别为实体、关系和事实三元组(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}})的集合，三元组(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}})表示从头实体e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}}到尾实体e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}存在关系r。

定义3（用户位置预测） 给定用户U时间t的签到轨迹T_{\mathrm{U}}=\left\{q_{\mathrm{1}},q_{\mathrm{2}},\dots ,q_n\right\}，目标是预测用户在下一时刻所处的POI。

1.2 GeoKGAT算法框架

针对地理信息利用不足与获取用户多层次地理偏好特征的挑战，本文提出GeoKGAT算法，其框架如图1所示。包含3个核心模块：1）地理知识图谱构建与表示学习；2）空间与关系感知的图注意力网络；3）时空感知的位置预测。

1.3 层次化地理知识图谱构建与表示学习

为解决现有方法将地理信息视为POI静态属性、缺乏对地理实体间结构语义关系显式建模与推理的问题，首先构建层次化地理知识图谱（Hierarchical Geographical Knowledge Graph， HGeoKG）。引入多粒度地理实体及其关系，将离散的地理属性组织到同一异构图结构中，使地理信息转化为可推理的结构化知识，从而为用户全局地理偏好建模提供语义支撑。

1.3.1 地理知识图谱构建

地理学第二定律指出，地理现象具有空间异质性^[20]，在用户签到行为中则表现为：POI的地理语义和功能特征深受其所在区域分布和区域间的空间异质性影响。不同区域间的差异对用户的地理空间偏好具有重要影响。

本文设计“城区—街区—POI”3级地理实体层次结构，对POI所处区域的地理特征和空间异质性进行多粒度建模。在此基础上构建层次化地理知识图谱G=(E,R,F)，如图2所示。其中，实体集合E为用户集合（U）、POI集合（P）、POI类别集合（C）、街区集合（S）与城区集合（D）的并集。关系集合R定义了6类三元组以刻画实体之间的多样化关联。F为知识图谱事实三元组集合。

签到关系r_{\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{c}\mathrm{k}}：表示用户U在P进行了签到，表示为三元组(U,r_{\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{c}\mathrm{k}},P)。

转移关系r_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}}：表示同一轨迹序列中POI之间的连续访问，表示为三元组(P,r_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}},P)。

类别关系r_{\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}}：表示P与其类别的语义关联，表示为三元组(P,r_{\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}},C)。

微观空间包含关系r_{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{e}}：表示P位于街区S，表示为三元组(P,r_{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{d}},S)，用于建立局部地理空间上下文。

宏观空间包含关系r_{\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}}：表示街区S隶属于城区D，表示为三元组(S,r_{\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}},D)，用于刻画城市区域间的层次关系。

空间邻接关系r_{\mathrm{a}\mathrm{d}\mathrm{j}\mathrm{a}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}}：表示街区之间的邻接关系，表示为三元组(S,r_{\mathrm{a}\mathrm{d}\mathrm{j}\mathrm{a}\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}},S)，以建模跨地理单元的空间连续性。

1.3.2 地理知识图谱表示学习

本文采用TransR模型^[21]对HGeoKG进行表示学习。对于三元组\left(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}\right)，通过关系特定投影矩阵\mathit{M}，将实体映射到关系空间，并基于翻译机制计算得分：

f\left(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}\right)=-{‖e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}}\mathit{M}+e_{\mathrm{r}}-e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}\mathit{M}‖}_{\mathrm{2}}^{\mathrm{2}}（1）

式中：e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}}\mathrm{、}{e}_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}\mathrm{、}{e}_{\mathrm{r}}分别为头实体、尾实体和关系的嵌入；{‖·‖}_{\mathrm{2}}^{\mathrm{2}}是L{}_{\mathrm{2}}范数平方。

给定正例三元组及负采样三元组，采用基于BPR（Bayesian Personalized Ranking）的损失函数进行优化，知识图谱嵌入损失计算如下：

L_{\mathrm{K}\mathrm{G}\mathrm{E}}=-\sum \mathrm{l}\mathrm{n}\sigma \left(f\left(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}\right)-f\left(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}^{\text{'}}\right)\right)（2）

式中：\left(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}\right)、\left(e_{\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}},r,e_{\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{l}}^{\text{'}}\right)为正负样本对；\sigma为Sigmoid函数。

学习得到的实体嵌入融合了地理语义和图谱结构信息，作为后续图注意力网络的初始输入。

1.4 空间和关系感知的图注意力网络

用户移动行为受其全局地理偏好影响，即用户在较长时间、跨区域访问过程中形成的对区域层级、空间邻近结构与功能语义组合的相对稳定偏好。但现有方法将地理影响简化为点对点距离、难以同时表征区域功能语义与空间可达性，难以建模用户的全局地理偏好特征。本文提出空间与关系感知图注意力网络。在传播过程中联合建模关系语义差异与空间距离约束，以学习更具地理语义的用户全局偏好表征。

1.4.1 距离和关系感知的图注意力机制

传统图注意力机制通常仅利用节点特征，忽略关系类型差异。为此，本文引入关系感知注意力机制。对于通过关系r连接的实体对(v_i,v_j)，其注意力得分a_{i,j}计算如下：

a_{i,j}=({\mathit{M}}_r{\mathit{e}}_j{)}^{\mathrm{{\rm T}}}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}({\mathit{M}}_r{\mathit{e}}_i+{\mathit{e}}_r)（3）

式中：{\mathit{e}}_i,{\mathit{e}}_j\in {\mathbf{R}}^d为实体特征向量；{\mathit{e}}_r\in {\mathbf{R}}^k是关系r嵌入；d、k为特征向量维度；{\mathit{M}}_r\in {\mathbf{R}}^{k\times d}为关系r特定的投影矩阵；tanh\left(·\right)为激活函数。

用户移动还受到空间邻近性的显著约束。大量研究表明，在城市尺度下，用户的出行距离分布符合指数衰减规律^[22]，反映用户日常活动受时间、成本等约束而表现出的空间局限性。

本文进一步在POI转移关系中引入指数形式的距离衰减因子：

{\tilde{a}}_{i,j}=a_{i,j}\cdot \mathrm{e}\mathrm{x}\mathrm{p}(-\alpha \cdot \mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{\Delta }{d}_{i,j},d_{\mathrm{m}\mathrm{a}\mathrm{x}}))（4）

式中:\mathrm{\Delta }{d}_{i,j}为POI间的球面距离;d_{\mathrm{m}\mathrm{a}\mathrm{x}}为最大距离阈值;\alpha >\mathrm{0}为距离衰减系数。

综合上述关系与空间感知机制，注意力计算函数如下：

f_{\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{n}}({\mathit{e}}_i,{\mathit{e}}_j,{\mathit{e}}_r,r)=\left\{\begin{array}{ll}{\tilde{a}}_{i,j},& r=r_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}};\\ a_{i,j},& \mathrm{其他}.\end{array}\right.（5）

式中；{\mathit{e}}_i,{\mathit{e}}_j,{\mathit{e}}_r为三元组(h_i,r,t_j)的嵌入向量；r为关系类型；r_{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{e}\mathrm{r}}表示POI转移关系。

通过Softmax函数进行归一化，得到最终的注意力权重：

a_{i,j}=\frac{\mathrm{e}\mathrm{x}\mathrm{p}(\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{k}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}(a_{i,j}))}{\sum _{v_k\in N_{v_i}}\mathrm{e}\mathrm{x}\mathrm{p}(\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{k}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}(a_{i,k}))}（6）

式中:LeakReLU\left(·\right)为激活函数;N_{v_i}为实体v_i的邻居集合。

1.4.2 信息传播与聚合

图注意力网络基于空间和关系感知的注意力机制，在知识图谱中传播和聚合节点特征信息，更新节点特征向量，挖掘知识图谱中实体的高阶连通性，从而有效捕捉隐式的用户地理偏好和POI空间关联。例如，当用户U访问过的P位于街区S，则可通过路径U\stackrel{r_{\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{c}\mathrm{k}}}{\to }P\stackrel{r_{\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}}}{\to }S建立用户和地理区域之间的依赖关系，推断用户潜在地理偏好。

在得到注意力权重后，节点从其一阶邻居聚合信息，形成邻域表示：

{\mathit{e}}_{N_{v_i}}^l=\sum _{j\in N_{v_i}}{a}_{i,j}^l{\mathit{e}}_j^l（7）

a_{i,j}^l=\mathrm{S}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}(f_{\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{n}}({\mathit{e}}_i^l,{\mathit{e}}_j^l,{\mathit{e}}_r^l,r_{i,j}))（8）

式中：{\mathit{e}}_i^l\mathrm{、}{\mathit{e}}_j^l为第l层网络中节点v_i和其邻居节点v_j的向量表示；N_{v_i}为节点v_i的邻居集合；r_{i,j}为节点v_i和v_j连边的关系类型；{\mathit{e}}_r^l为关系r_{i,j}的向量表示。

随后，将邻域信息与节点自身表示进行融合，更新节点表示：

{\mathit{e}}_i^{l+\mathrm{1}}=\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{k}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}({\mathit{W}}_{\mathrm{1}}^l({\mathit{e}}_{N_{v_i}}^l+{\mathit{e}}_i^l))+\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{k}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}({\mathit{W}}_{\mathrm{2}}^l({\mathit{e}}_{N_{v_i}}^l\odot {\mathit{e}}_i^l))（9）

式中：\odot为逐元素相乘；{\mathit{W}}_{\mathrm{1}}^l和{\mathit{W}}_{\mathrm{2}}^l为可学习的参数矩阵。

最后，为集成不同层的表示并提高训练稳定性，将各层输出与初始嵌入进行拼接和残差融合，得到节点最终表示：

{\mathit{e}}_i=\mathit{W}\left({\mathit{e}}_i^{\mathrm{0}}‖{\mathit{e}}_i^{\mathrm{1}}‖...‖{\mathit{e}}_i^L\right)+\mathit{b}（10）

式中：(\cdot ‖\cdot )表示向量拼接操作；{\mathit{e}}_i^{\mathrm{0}}为第1.3.2节中地理知识图谱表示学习得到的初始嵌入；\mathit{W}\mathrm{、}\mathit{b}为可学习参数。

1.5 时空感知的序列编码器

用户下一位置的选择不仅受全局地理偏好的影响，还受到当前轨迹上下文中局部时空动态偏好的驱动。用户在选择访问位置时受到轨迹上下文、签到时间间隔与空间转移共同作用而表现出短期行为倾向。然而，现有方法多将地理信息视为静态属性，缺乏与用户时序行为的联合建模。为此，本文设计时空感知序列编码器，将全局地理语义表征注入签到序列，并通过时空间隔编码与时空偏置注意力建模局部转移规律，从而提升下一位置预测能力。

1.5.1 上下文感知的嵌入表征

为统一建模用户签到行为中的语义信息、时间上下文与空间约束，首先构建签到记录的上下文感知表征。对于签到时间戳t,采用Time2Vec模型^[23]进行编码，以刻画绝对时间及其周期性特征：

{\mathit{e}}_t[i]=\left\{\begin{array}{ll}{\omega }_{i}t+{\phi }_i,& i=\mathrm{0};\\ \mathrm{s}\mathrm{i}\mathrm{n}({\omega }_{i}t+{\phi }_i),& \mathrm{1}\le i\le k.\end{array}\right.（11）

式中：{\mathit{e}}_t[i]为时间向量表示的第i个位置；{\omega }_i\mathrm{、}{\phi }_i为可学习参数；k为向量长度。

随后，将用户增强表征、POI增强表征与类别表征、时间表征分别融合，并进一步拼接得到签到记录q的上下文向量表示:

{\mathit{e}}_{U,P}=\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{k}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}({\mathit{W}}_{U,P}({\mathit{e}}_U‖{\mathit{e}}_P)+{\mathit{b}}_{U,P})（12）

{\mathit{e}}_{t,C}=\mathrm{L}\mathrm{e}\mathrm{a}\mathrm{k}\mathrm{y}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}({\mathit{W}}_{t,C}({\mathit{e}}_t‖{\mathit{e}}_C)+{\mathit{b}}_{t,C})（13）

{\mathit{e}}^q={\mathit{e}}_{U,P}‖{\mathit{e}}_{t,C}（14）

式中：{\mathit{W}}_{U,P}\mathrm{、}{\mathit{W}}_{t,C}\mathrm{、}{\mathit{b}}_{U,P}\mathrm{、}{\mathit{b}}_{t,C}为可学习参数。

用户的轨迹序列T_U=\left\{q_{\mathrm{1}},q_{\mathrm{2}},\dots ,q_n\right\}被表示为向量序列{\mathit{E}}_{\mathit{U}}=({\mathit{e}}_{\mathrm{1}}^q,{\mathit{e}}_{\mathrm{2}}^q,\dots ,{\mathit{e}}_n^q)，作为序列编码器的输入。

1.5.2 时空感知Transformer编码器

为显式刻画用户轨迹中的局部时空转移规律，进一步引入个性化时空间隔编码。考虑到用户对时间间隔和移动距离的敏感程度存在差异，本文对轨迹中任意两个签到之间的时间距离与空间距离分别进行建模。

对于用户U轨迹中的第i、j个签到，其归一化的时间距离t_{i,j}和空间距离s_{i,j}计算方式如下：

t_{i,j}=\mathrm{m}\mathrm{i}\mathrm{n}\left(\mathrm{\Delta }t,⌊\frac{t_i-t_j}{t_{\mathrm{m}\mathrm{i}\mathrm{n}}^U}⌋\right)（15）

s_{i,j}=\mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{\Delta }d,\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{i}\mathrm{n}(p_i,p_j))（16）

时间距离t_{i,j}根据用户轨迹中最小时间间隔t_{\mathrm{m}\mathrm{i}\mathrm{n}}^U进行个性化归一化，空间距离s_{i,j}则为签到POI间的harversin距离（球面距离），二者均通过截断阈值\mathrm{\Delta }t与\mathrm{\Delta }d处理异常值。

随后，通过嵌入层将离散的时空间隔映射为连续向量表{\mathit{e}}_{i,j}^t,{\mathit{e}}_{i,j}^d\in {\mathbf{R}}^d，作为显式的时空偏置信号。

编码器在标准Transformer^[24-25]中注入上述时空嵌入，以协同建模序列的语义、时间与空间依赖。其核心是时空感知的多头自注意力机制^[12,26-27]。

给定签到序列的嵌入表示{\mathit{E}}_{\mathit{U}}=({\mathit{e}}_{\mathrm{1}}^q,{\mathit{e}}_{\mathrm{2}}^q,\dots ,{\mathit{e}}_n^q)，对于其中一个签到向量{\mathit{e}}_i^q，首先使用自注意力机制聚合历史签到向量的信息，计算如下：

\left\{\begin{array}{l}{h}_i={\displaystyle \sum _{j=\mathrm{1}}^i}{a}_{i,j}^{\text{'}}({\mathit{e}}_j^q{\mathit{W}}_{value}+{\mathit{e}}_{i,j}^t+{\mathit{e}}_{i,j}^d+{\mathit{e}}_j^{pos});\\ a_{i,j}^{\text{'}}=\frac{\mathrm{e}\mathrm{x}\mathrm{p}(a_{i,j})}{{\displaystyle \sum _{k=\mathrm{1}}^n}\mathrm{e}\mathrm{x}\mathrm{p}(a_{i,k})};\\ a_{i,j}=\frac{{\mathit{e}}_i^q{\mathit{W}}_{\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}}({\mathit{e}}_j^q{\mathit{W}}_{\mathrm{k}\mathrm{e}\mathrm{y}}+{\mathit{e}}_{i,j}^t+{\mathit{e}}_{i,j}^d+{\mathit{e}}_j^{\mathrm{p}\mathrm{o}\mathrm{s}}{)}^{\mathrm{T}}}{\sqrt[]{d}}.\end{array}\right.（17）

式中：以避免更新后的签到向量受到未来签到的影响；{\mathit{W}}_{\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{r}\mathrm{y}}\mathrm{、}{\mathit{W}}_{\mathrm{k}\mathrm{e}\mathrm{y}}\mathrm{、}{\mathit{W}}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}}为参数矩阵；a_{i,j}和a_{i,j}^{\text{'}}为签到q_i和q_j间的注意力分数;{\mathit{e}}_j^{\mathrm{p}\mathrm{o}\mathrm{s}}为第j个签到的相对位置嵌入;d为嵌入维度。

将多注意力头的输出进行拼接，然后输入到前馈神经网络中，并加入层归一化和残差连接。最后通过堆叠多层编码器，逐步融合序列的复杂时空语义，最终输出{\mathit{z}}_i作为第i个签到，含有用户多层次地理偏好特征的深度表征。

1.6 位置预测与模型优化

为充分利用语义与时空上下文中的监督信号，采用多任务学习范式，通过3个独立的MLP（Multi-Layer Perceptron）解码头同步预测用户下一个访问的位置、时间和类别：

y_{\mathrm{P}\mathrm{O}\mathrm{I}}^{i+\mathrm{1}}=\mathrm{S}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}({\mathit{z}}_i{\mathit{W}}_{\mathrm{P}\mathrm{O}\mathrm{I}}+{\mathit{b}}_{\mathrm{P}\mathrm{O}\mathrm{I}})（18）

y_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}^{i+\mathrm{1}}={\mathit{z}}_i{\mathit{W}}_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}+{\mathit{b}}_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}（19）

y_{\mathrm{c}\mathrm{a}\mathrm{t}}^{i+\mathrm{1}}=\mathrm{S}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}({\mathit{z}}_i{\mathit{W}}_{\mathrm{c}\mathrm{a}\mathrm{t}}+{\mathit{b}}_{\mathrm{c}\mathrm{a}\mathrm{t}})（20）

式中：{\mathit{W}}_{\mathrm{P}\mathrm{O}\mathrm{I}}\in {\mathbf{R}}^{d\times N}\mathrm{、}{\mathit{W}}_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}\in {\mathbf{R}}^{d\times \mathrm{1}}\mathrm{、}{\mathit{W}}_{\mathrm{c}\mathrm{a}\mathrm{t}}\in {\mathbf{R}}^{d\times k}为权重矩阵；{\mathit{b}}_{\mathrm{P}\mathrm{O}\mathrm{I}}\mathrm{、}{\mathit{b}}_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}\mathrm{、}{\mathit{b}}_{\mathrm{c}\mathrm{a}\mathrm{t}}为偏置；y_{\mathrm{P}\mathrm{O}\mathrm{I}}^{i+\mathrm{1}}\mathrm{、}{y}_{\mathrm{c}\mathrm{a}\mathrm{t}}^{i+\mathrm{1}}是候选POI和类别的概率分布；y_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}^{i+\mathrm{1}}为访问时间的预测值。

使用交叉熵损失作为POI预测和类别预测的损失函数，均方误差损失作为时间预测的损失函数，并使用系数\phi作为平衡系数，计算总预测损失：

L_{\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{t}}=L_{\mathrm{P}\mathrm{O}\mathrm{I}}+\phi L_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}+L_{\mathrm{c}\mathrm{a}\mathrm{t}}（21）

训练采用交替优化策略，依次更新预测模型参数与知识图谱嵌入参数。

GeoKGAT算法包括3个部分。1）知识图谱表示学习，时间复杂度为O(N_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}}\times d^{\mathrm{2}})，N_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}}为三元组数量，d为嵌入维度。空间复杂度为O(N_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{y}}\times d)，N_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{y}}为实体数量，用于节点嵌入；2）空间与关系感知的图注意力模块，当信息传播层数为N_{\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}}时，时间复杂度为O(N_{\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}}\times (N_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}}\times d+N_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{y}}\times d^{\mathrm{2}}))，空间复杂度为O(N_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{y}}\times d+N_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}})；3）时空感知的序列编码，时间复杂度为O(Q\times N_{\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}}\times S\times d^{\mathrm{2}})，其中：Q为轨迹数量；S为固定的轨迹长度；N_{\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}}为编码器层数。空间复杂度为O(B\times S\times d+S^{\mathrm{2}})，B为批次大小。

可得，GeoKGAT算法的总体时间复杂度为：O(N_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}}\times d^{\mathrm{2}}+N_{\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}}\times N_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{l}\mathrm{e}}\times d+N_{\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}}\times N_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{y}}\times d^{\mathrm{2}}+Q\times N_{\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}}\times S\times d^{\mathrm{2}})。

2 实验与分析

2.1 研究范围与实验数据

实验在Foursquare-NYC和Foursquare-TKY这两个公开的真实世界LBSN签到数据集上进行^[28]。数据涵盖2012年4月至2013年2月纽约和东京地区的LBSN用户签到数据。原始签到数据包括用户ID、POI ID、POI类别、经纬度及时间戳等8个字段。外部地理数据来自OpenStreetMap平台^[29]，包括路网、行政区域数据等。

对原始数据进行预处理。首先，过滤签到数量少于10的用户以及被访问次数小于10的POI，随后将用户签到记录按时间戳升序进行排列，然后按第1.3.1节定义的规则，从签到数据和地理数据中抽取实体和关系，构建地理知识图谱。预处理后数据统计信息如表1所示。将每个用户的轨迹序列划分为等长子序列，前80%签到作为训练集，剩余20%作为测试集。

2.2 评价指标与实验设置

2.2.1 评价指标

采用两种评价指标：准确率R_accuracy为预测列表中前K个预测值里正确预测值所占的比例；平均倒数秩R_MRR为真实POI排名的倒数的平均值。计算方法如下：

R_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}}=\frac{\mathrm{1}}{m}{\displaystyle \sum _{i=\mathrm{1}}^m}{f}_{index}(R_{rank}^i\le K)（22）

R_{\mathrm{M}\mathrm{R}\mathrm{R}}=\frac{\mathrm{1}}{m}{\displaystyle \sum _{i=\mathrm{1}}^m}\frac{\mathrm{1}}{R_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}^i}（23）

式中：m为测试样本数量；R_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}^i表示第i个样本中真实POI的预测排名；f_{\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}}(\cdot )为指示函数，当条件为真时返回1，否则返回0；K为截断阈值，代表预测列表的窗口大小，为全面评估模型在不同推荐列表长度下的性能，分别取K=1,3,5,10计算准确率。

2.2.2 实验环境与参数设置

模型基于PyTorch实现，使用AdamW优化器（\beta =(\mathrm{0.9,0.999})，权重衰减为{\mathrm{10}}^{-\mathrm{4}}）。关键参数设置如下：实体、关系嵌入为256维，时间嵌入为32维。时空感知Transformer为3层编码器，4个注意力头。Dropout率设为0.4；时间损失权重\phi =\mathrm{10}；正则化损失权重\lambda ={\mathrm{10}}^{-\mathrm{5}}。批量大小为128，训练轮数为100。TransR与预测模型学习率分别设为\mathrm{5}\times {\mathrm{10}}^{-\mathrm{4}}与1×{\mathrm{10}}^{-\mathrm{4}}。

2.3 实验结果与分析

2.3.1 基线模型对比试验

本文选取两类基线模型进行对比：1）基于序列的模型：Flashback^[7]、PLSPL^[5]、STAN^[9]；2）基于图的模型：GETNext^[30]、AGRAN^[12]、AGCL^[13]。表2展示了GeoKGAT与基线模型在数据集上的性能对比。

实验结果表明，GeoKGAT模型在绝大多数指标上均取得最优性能，在Foursquare-NYC数据集上，GeoKGAT模型在K=1时，准确率和平均倒数秩相较次优模型提升了约32.64%与19.52%。在Foursquare-TKY数据集上，除在K=1时准确率指标略低于AGRAN方法，其余指标均保持领先。这充分验证了GeoKGAT算法的整体有效性。

与Flashback、STAN等序列方法相比，基于图的方法能够利用POI间的高阶关联，缓解数据稀疏问题，因此整体表现更优；而GETNext、AGRAN和AGCL虽然能够建模全局依赖，但对地理语义信息的利用仍不充分。

GeoKGAT通过构建层次化地理知识图谱，并结合空间与关系感知图注意力网络及时空感知序列编码器，实现了对用户全局地理偏好和局部时空转移模式的协同建模，从而提升了位置预测的精度。

2.3.2 消融试验

在Foursquare-NYC和Foursquare-TKY数据集上进行以下消融实验。

1）w/o Geo，表示移除知识图谱中的外部地理实体和关系；2）w/o KG，表示移除知识图谱；3）w/o distance，表示移除了图注意力模块中距离衰减因子；4）w/o ST，表示移除序列建模中的时空依赖。消融实验结果如表3、表4所示。结果表明，完整模型在各项指标上均取得最优性能，各模块能够协同提升位置预测精度。

具体来看，移除外部地理知识（w/o Geo）后，模型性能整体下降，表明仅依赖轨迹内部共现关系难以充分刻画用户移动行为，结构化地理知识有助于建模用户全局地理偏好。移除知识图谱（w/o KG）后，K=1时准确率和平均倒数秩下降最为明显，说明知识图谱预训练得到的高质量初始嵌入对提升精确预测能力具有重要作用。移除距离衰减约束（w/o distance）或时空依赖矩阵（w/o ST-Transformer）后，性能进一步下降，表明空间邻近性和个性化时空上下文对捕捉用户移动规律具有关键作用。

2.3.3 超参数分析试验

通过实验分析距离衰减因子、图神经网络隐藏层数和实体嵌入维度对GeoKGAT性能的影响。实验结果如图3~图5所示。

由图3~图5分析可得，当距离衰减因子取0.1时，模型在两个数据集上综合性能最佳，说明适当的空间衰减强度更有利于刻画用户移动中的距离影响。随着图神经网络隐藏层数增加，模型能够聚合更高阶邻居信息，提升实体表示能力；但层数过多会导致过平滑，从而降低预测效果。实体嵌入维度增大能够增强模型对地理语义和用户偏好的表征能力，但维度过低会限制模型容量，过高则增加计算开销；综合来看，适中的嵌入维度能够在预测精度和计算效率之间取得较好平衡。

2.3.4 模型效率分析

为评估本文模型计算效率，将其与STAN、GETNext两种经典算法对比，结果见表5。为保证公平，实验在数据集上使用相同的配置，本文模型和GETNext模型批处理大小均设置为128。STAN模型因自身计算复杂度限制，采用文献[9]推荐配置。

结果表明，GeoKGAT模型在训练耗时、模型大小方面均高于基于图的GETNext模型，主要源于地理知识图谱与图注意力网络带来的额外计算。然而，GeoKGAT通过采用稀疏矩阵计算策略，使得在提高约18%时间消耗的代价下，降低了约16%的内存占用。

STAN模型为建模时空影响，需在注意力匹配中进行全候选匹配，使其无法批量训练，实验中仅能以逐用户方式采用少量轨迹，其表现的低耗时和低内存为数据吞吐量严重受限的表现。而本文模型通过全局嵌入将时空感知的预测计算简化，实现了更优的计算效率。

综上，虽然GeoKGAT单轮训练耗时较高，但其架构实现了对额外地理数据的高效利用，模型以可控的计算开销增长，换取了精度的显著提升，证明了引入结构化地理知识在效率与精度权衡上的有效性。

3 总结与展望

本文提出了一种融合地理知识图谱和图神经网络的用户位置预测算法GeoKGAT。该方法通过构建层次化地理知识图谱增强实体地理语义表示，利用空间与关系感知图注意力网络建模用户全局地理偏好，并结合时空Transformer编码器刻画用户局部时空转移模式，从而实现多层次用户偏好的协同建模。公开数据集上的实验结果表明，GeoKGAT在两个指标上整体优于现有方法，验证了所提模型的有效性。未来可进一步构建更细粒度的地理本体，并融合交通可达性、区域活跃度等更丰富的地理上下文，以提升模型对复杂场景和冷启动用户的位置预测能力。

参考文献

[1] 李静，刘海砚，郭文月，等.基于深度学习的人群活动流量时空预测模型［J］.测绘学报，2021，50（4）：522-531.

[2] SHI H Z， LI Y， CAO H C， et al. Semantics-aware hidden Markov model for human mobility［J］. IEEE Transactions on Knowledge and Data Engineering， 2021，33（3）：1183-1194.

[3] DING J H， LIU H Z， YANG L T， et al. Multiuser multivariate multiorder Markov-based multimodal user mobility pattern prediction［J］.IEEE Internet of Things Journal， 2020，7（5）：4519-4531.

[4] 纪开松，马宏，王庚润，等.基于双向长短期记忆网络的用户轨迹停留点提取［J］.信息工程大学学报，2021，22（6）：641-646.

[5] WU Y X， LI K， ZHAO G S， et al. Personalized long-and short-term preference learning for next POI recommendation［J］. IEEE Transactions on Knowledge and Data Engineering， 2022，34（4）：1944-1957.

[6] SI Y L， LI F， ZHONG S， et al. Adaptive successive POI recommendation via trajectory sequences processing and long short-term preference learning［J］. Computers， Materials & Continua， 2024，81（1）：685-706.

[7] YANG D Q， FANKHAUSER B， ROSSO P， et al. Location prediction over sparse user mobility traces using RNNs： flashback in hidden states［C］// Proceedings of the 29th International Joint Conference on Artificial Intelligence. California， USA： IJCAI， 2020：2184-2190.

[8] HASAN A A， ANWAR M M. SEAGET： seasonal and active hours guided graph enhanced transformer for the next POI recommendation［J］. Array， 2025，26：No.100385.

[9] LUO Y T， LIU Q， LIU Z C. STAN： spatio-temporal attention network for next location recommendation［C］// Proceedings of the Web Conference 2021. New York， USA： ACM， 2021：2177-2185.

[10] LI Y， CHEN T， LUO Y D， et al. Discovering collaborative signals for next POI recommendation with iterative Seq2Graph augmentation［C］// Proceedings of the 30th International Joint Conference on Artificial Intelligence. California， USA： IJCAI， 2021：1491-1497.

[11] WANG X F， FUKUMOTO F， CUI J， et al. EEDN： enhanced encoder-decoder network with local and global context learning for POI recommendation［C］// Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York， USA： ACM， 2023：383-392.

[12] WANG Z B， ZHU Y M， WANG C Y， et al. Adaptive graph representation learning for next POI recommendation［C］// Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York， USA： ACM， 2023：393-402.

[13] RAO X， JIANG R H， SHANG S， et al. Next point-of-interest recommendation with adaptive graph contrastive learning［J］.IEEE Transactions on Knowledge and Data Engineering， 2025，37（3）：1366-1379.

[14] PAN Q H， ZHENG H， ZHAO Z Z， et al. CTKGRec： a context-aware temporal knowledge graph reasoning model for next POI recommendation［J］. Expert Systems with Applications， 2026，297：No.129224.

[15] 李佳，李静，刘海砚，等.地理知识图谱增强与多时空条件约束的轨迹预测［J］.测绘学报，2024，53（10）：2021-2033.

[16] RAO X， CHEN L S， LIU Y， et al. Graph-flashback network for next location recommendation［C］// Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York， USA： ACM， 2022：1463-1471.

[17] LI T L， CHEN R Y， DUAN Y L， et al. Spatial context-enhanced temporal knowledge graph reasoning［J］. Information Processing & Management， 2026，63（2）：No.104456.

[18] JI S X， PAN S R， CAMBRIA E， et al. A survey on knowledge graphs： representation， acquisition， and applications［J］.IEEE Transactions on Neural Networks and Learning Systems， 2022，33（2）：494-514.

[19] 杨大伟，周刚，卢记仓，等.基于知识表示学习的知识图谱补全研究综述［J］.信息工程大学学报，2021，22（5）：558-565.

[20] ZHU A X， LU G N， LIU J， et al. Spatial prediction based on third law of geography［J］. Annals of GIS， 2018，24（4）：225-240.

[21] 张天成，田雪，孙相会，等.知识图谱嵌入技术研究综述［J］.软件学报，2023，34（1）：277-311.

[22] YANG X P， FANG Z X， XU Y， et al. Spatial heterogeneity in spatial interaction of human movements： insights from large-scale mobile positioning data［J］.Journal of Transport Geography， 2019，78：29-40.

[23] KAZEMI S M， GOEL R， EGHBALI S， et al. Time2Vec： learning a vector representation of time［DB/OL］. （2019-07-11）［2026-04-14］.

[24] SHAW P， USZKOREIT J， VASWANI A. Self-attention with relative position representations［C］// Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg， USA： ACL， 2018：464-468.

[25] VASWANI A， SHAZEER N， PARMAR N， et al. Attention is all you need［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. New York， USA： ACM， 2017：6000-6010.

[26] QIN Y J， FANG Y C， LUO H Y， et al. Next point-of-interest recommendation with auto-correlation enhanced multi-modal transformer network［C］// Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York，USA： ACM， 2022：2612-2616.

[27] LI J C， WANG Y J， MCAULEY J. Time interval aware self-attention for sequential recommendation［C］// Proceedings of the 13th International Conference on Web Search and Data Mining. New York，USA： ACM， 2020：322-330.

[28] YANG D Q， ZHANG D Q， ZHENG V W， et al. Modeling user activity preference by leveraging user spatial temporal characteristics in LBSNs［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2015，45（1）：129-142.

[29] HAKLAY M， WEBER P. OpenStreetMap： user-generated street maps［J］. IEEE Pervasive Computing， 2008，7（4）：12-18.

[30] YANG S， LIU J M， ZHAO K Q. GETNext： trajectory flow map enhanced transformer for next POI recommendation［C］// Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York， USA： ACM， 2022：1144-1153.

基金资助

河南省自然科学基金项目(252300420301)