WWW2021：基于增量时空图学习的POI查询框架

时空实验室 麻志鹏

兴趣点(Point-of-Interest, POI)查询是目前地图服务系统与叫车应用中最重要的功能之一。现有的POI查询方法聚焦在比较查询的上下文信息和POI的地理信息之间的静态相似性来返回结果。但是，在实际应用中，由于POI查询具有动态变化的特点，对于不同时空情景下不同用户的相同查询，系统往往不能很好的返回个性化的查询结果。为此，罗格斯大学与百度的研究人员在WWW2021上发表了论文 《Incremental Spatio-Temporal Graph Learning for Online Query-POI Matching》。该论文提出了一种增量的时空图学习框架（IncreSTGL） 用于解决动态场景下的在线POI查询问题。

一、背景介绍

近年来，随着智能设备的普及，在线导航（如谷歌、百度地图）和叫车应用（如Uber和Lyft）在全球 范围内广泛使用。其中，POI查询服务能够匹配检索与用户搜索关键字最为相关的POI候选。作为最基本的地图服务功能之一，POI查询在帮助用户探索新位置、改善用户服务体验与提升商业价值方面起着关键作用。

现有服务中，系统常匹配查询上下文信息与静态地理信息之间建立语义相关性为用户返回查询结果， 却忽略了历史查询记录对POI查询结果的影响。为了解决这个问题，近来已经有研究者提出了基于二分图学习的方法，通过建模查询关键字与返回结果的交互过程来捕捉用户POI查询时的动态影响，如 STDGAT [1]。然而，该类方法通常需要根据所有历史数据定期重新训练模型，以逐渐适应用户偏好，这在在线环境中的运行成本是非常高的。因此，开发这样一个智能的在线POI查询系统主要面临三个方面的挑战。

动态的时空相关性。POI查询期望的结果与它的时空上下文具有很强的相关性，如图1展示了北京市三个有代表性的位置在19年1月不同时段查询POI的结果结果分布。我们可以看到，在不同的时空背景下，所选POI类别分布存在显著差异，如何在在线POI查询中集成这些动态的时空信息是一项挑战。

不稳定的相关性漂移。查询与结果之间存在变化的相关性，会伴随时间的推移产生漂移。即不同时间段的查询与结果间并不是独立同分布的。为了说明问题，作者提取了连续两周查询关键字 “beihai”的历史记录，并在图2中展示了用户选择的poi的分布情况。用户对相应查询关键字的POI 候选项的偏好随着时间的变化而变化，没有表现出明显的重复模式。如何建模这种动态的相关性是另一个挑战。

在线学习的系统效率限制。虽然合并最近的查询历史用于克服相关性漂移是一个可行的方案，但它 提出了一个挑战，即以在线的方式从大量查询日志中捕获随时间变化的的用户偏好和动态上下文信息。大多数传统的方法将流数据视为一个时间窗序列，需要基于所有历史数据进行周期性的模型重构，这对于在线POI查询交互建模是不可扩展的。

二、框架介绍

为了解决上述挑战，作者提出了一个增量的时空图学习框架 IncreSTGL。该框架通过对按时间窗口切 分的查询-结果交互图进行学习实现对时空上下文的集成与时移漂移的建模，存储在交互图的图结构中 （而非模型参数中），更新过程中框架直接对交互图进行refine，极大增加了系统效率，使其可以适用于在线环境。 图3给出了本文架构的示意图。具体来说，作者首先从宏观和微观两方面将用户的历史查询记录建模 为查询结果交互图，其中宏观图反映了一般POI查询的普遍规律，微观图保留了用户特定的偏好。然 后，为了基于新的用户查询记录增量捕获查询与结果间的相关性转移，我们提出了增量图表示学习模 块，该模块能够整合历史中各个时间戳的宏观与微观图并输出统一的增量聚合图。增量聚合的查询结果 交互图合并了历史中查询与结果间的相关性和最近的用户偏好。最后，我们基于聚合得到的查询结果交互图设计了一个轻量级的语义匹配模块（SemFtn）用于在线POI查询。在一次查询中，框架输入用户、 时间戳、时间片id、位置、与查询关键词，框架通过增量图表示学习模块学习到的参数更新用户的交互 图，输出点击各个POI候选结果的概率。

1、表示初始化

在模型准备阶段，需要对用户历史上的POI查询行为进行建模成查询结果交互图。该交互图是查询关 键词与POI候选间构成的加权图，表示为邻接矩阵，权重为关系对出现的频次。交互图中的两类节点， query节点包含用户信息，时间戳，时间片，查询关键字，POI节点包含POI的类别、名字与位置。在本文中，作者分别建立了两种交互图，宏观图与微观图。宏观图指某时间片（1天）的全量数据构成的邻 接矩阵。微观图则聚焦在某一用户，因此整体较为稀疏。两类图如图4所示。在进入下一个模块前，节点特征与临接矩阵都需要通过全连接与卷积神经网络（针对邻接矩阵）进行嵌入表示。

2、增量图表示学习

增量图表示学习用于学习集成查询的时空上下文信息，并建模查询结果的动态相关性。在该模块中， 对于过去每个时间片，上下文图学习注意力（CxtAttn）包含多因素上下文信息，以更新历史的宏观和 微观图的结构。然后，图辨别器（GraphAE）生成一组通用结构图和特有结构图，分别表示在每个时间 段内偏好转移的共性和差异。最后，一个多级的时间注意力沿着时间轴聚合上述图，并输出最新的查询结果图。

上下文图学习注意力（CxtAttn）。该模块通过历史宏观图与微观图的query节点与当前查询的 query向量通过注意力机制更新宏观图与微观图。

$r_g^{q^{\prime }}=\sum _{i=1}^{N_p^g}\frac{exp\left(\alpha \right(x_g^i,x_g^n\left)\right)}{\sum _{v_p\in N\left(v_q\right)}exp\left(\alpha \right(x_g^i,x_g^n\left)\right)}{r}_g^q$r^{q}_{g}=\sum^{N^{g}_{p}}_{i=1}{\frac{exp(\alpha(x^{i}_{g},x^{n}_{g}))}{\sum_{v_{p}\in N(v_{q})}exp(\alpha(x^{i}_{g},x^{n}_{g}))}}r^{q}_{g}

$r_s^{q^{\prime }}=\sum _{i=1}^{N_q^s}\frac{exp\left(\alpha \right(x_s^i,x_s^n\left)\right)}{\sum _{v_p\in N\left(v_q\right)}exp\left(\alpha \right(x_s^i,x_s^n\left)\right)}{r}_s^q$r^{q}_{s}=\sum^{N^{s}_{q}}_{i=1}{\frac{exp(\alpha(x^{i}_{s},x^{n}_{s}))}{\sum_{v_{p}\in N(v_{q})}exp(\alpha(x^{i}_{s},x^{n}_{s}))}}r^{q}_{s}

其中 $N_g^g$N^{g}_{g} 表示按时间切分后宏观图的个数， $N_q^s$N^{s}_{q} 同理。 $x_g^i$x^{i}_{g} 与 $x_s^i$x^{i}_{s} 分别表示第宏观图与微观图第i个时间片的query节点的特征矩阵。 $x_g^n$x^{n}_{g} 与 $x_s^n$x^{n}_{s} 分别表示宏观图与微观图对应的最新时间片的query节点的特征矩阵。 $\alpha$\alpha 表示非标准化的注意力权重，定义为： $\alpha (x,y)=(W_{x}x+b_x)?(W_{y}y+b_y{)}^T$\alpha (x,y)=(W_{x}x+b_{x})\cdot (W_{y}y+b_{y})^{T}

图辨别器（GraphAE）。基于前文更新后的宏观图 $r_g^q$r^{q}_{g} 与 $r_s^q$r^{q}_{s} 微观图， GraphAE通过捕捉动态时变漂移的用户偏好，融合社会效应和个性化偏好。具体来说，图辨别器 渐进地提取两个连续时间段之间一般偏好转移和用户个性化偏好转移的相似性和差异性，并分别将它们嵌入公共结构和不同结构的图邻接矩阵中。如图5所示，对于邻近的两个交互图，GraphAE 能 够基于他们的共有与不同结构通过encoder-decoder框架重构成新的邻接矩阵。值得一提的是， encoder部分中的隐变量通过多层级方式以注意力的方式得到。损失函数为重构误差。对于宏观图 与微观图，分别重构得到公共图与个性图，一共包含四个组合。

多层次时间注意力。用户的偏好随着时间的推移而逐渐改变。图辨别器学习共同图和不同图来保持偏好转移的过渡。现在，我们通过一个多层次的时间注意力网络来整合从长期视角中提炼出来的偏好。多层次时间注意力由两个部分组成，即用于聚合不同时间段的共同图与不同图的间注意力 （IntraAttn）与在时间上整合图结构的内注意力（InterAttn）。IntraAttn 的示意图如图6，由三层组成：(i) 条件层 （CondAttn）强调相邻时间片中相同类型图的影响，(ii) 同质层（HomoAttn） 在每个时间片中分别结合所有共性图和个性图，(iii) 异质层（HeterAttn）聚合结合的共性结构图和个性结构图，形成一个统一的图结构表示。InterAttn 针对间注意力得到的每个时间片对应的同一图结构表示进行时间通道上的融合。

3、语义匹配模块（SemFtn）。语义匹配模块输入上文得到的上下文图结构表示与基于Gestalt pattern matching algorithm得到的语义匹配图结构，融合两者结果得到最终的图表示结构。 $r_{ult}^{\left(j\right)}=W_{U_i}\left(\alpha \right(W_{U_2}{\tilde{r}}^{\left(j\right)}+b_{U_2}||r_{sem}\left)\right)+b_{U_i}$r^{(j)}_{ult}=W_{U_{i}}(\alpha (W_{U_{2}}\tilde{r}^{(j)}+b_{U_{2}}||r_{sem}))+b_{U_{i}} 其中 $r_{sem}$r_{sem} 表示语义匹配图结构， $r_{ult}^{\left(j\right)}$r^{(j)}_{ult} 表示当前更新过后的上下文图结构表示。基于改 图我们可以得到用户当前查询下候选POI的点击概率。其中 $r_{ult}^{\left(j\right)}\left\{e_{qp}\right\}$r^{(j)}_{ult}\{e_{qp}\} 表示在最终的图结构中的query q与结果p的边权重。整个框架的优化目标为最小化估计的概率与真实概率的交叉熵。作者为了提升效果在这里使用了负采样，即对于每一个查询结果对，都随机生成四个没有点击与语义相似性的结果作为负例。则最终的损失函数为 $L_1=\prod _{q,p+}Pr(p+|q)$L_{1}=\prod_{q,p+}Pr(p+|q) , $Pr\left(p|q\right)=\frac{exp\left(\tilde{y}\right(q,p\left)\right)}{\sum _{p^{\prime }\in \{p+\}\cup \left\{p_j^{?}\right\}}exp\left(\tilde{y}\right(q,p^{\prime }\left)\right)}$Pr(p|q)=\frac{exp(\tilde{y}(q,p))}{\sum_{p\in \{p+\}\cup \{p_{j}^{-}\}}exp(\tilde{y}(q,p))}

图7表示一个训练过程的实例。

三、实验结果

为了验证方法的性能，作者分别在北京与上海的真实数据集上进行了验证。本文比较了两个动态图学习的模型（DySAT，CTDNE）、四个基于语义的深度模型（DPSM, LSTM-DSSM，PLAM, STDGAT）与两个时空推荐模型（STGD、LSTPM）。本文选择Hits@K和NDCG@K作为评估指标，其中Hits中的K选择 1,3,5，NDCG中的K选择3，5, 10。实验结果如图8，IncreSTGL在两个数据集上的所有指标上均取得了 最佳性能。

同时，作者比较了上述方法的在线场景下的模型性能与延时测试，结果如图9。在北京数据集上， IncreSTGL的训练效率与运算速度都显著优于其他方法，且随着数据规模的增大呈现出温和的增长趋势。文中使用图结构直接度量查询结果相关性，而不是引入额外的图神经网络，从而显著提高了训练与计算效率。

除此之外，作者还评估了框架的鲁棒性。文中给出了在这些基线以不同的月度查询频率上的结果。如图 10（a）所示，对于所有模型更高的查询频率会带来更好的性能。与所有基线相比，IncreSTGL更加稳定，在稀疏数据方面仍表现出色。并且，随着用户月度任务的增加，IncreSTGL的性能从0.6781提高到了0.7764，表明其在建模用户动态偏好方面的潜力。最后作者邀请领域专家通过评级的方式实际体验了 推荐结构，结果如图7（b）。结果表明超过82.9%的用户认为推荐质量在G以上，只有3%的用户抱怨推荐结果质量较差(B或B-)。这些结果表明，文中提出的框架能够有效提高推荐质量。

四、总结

本文提出了一种增量时空图学习（IncreSTGL）框架，用于在线POI查询。与现有的考虑文本语义相似性 和简单空间关系的行业方法不同，我们在一个在线场景中中联合建模了动态的上下文信息和用户的历史 顺序行为。作者使用两个真实地图搜索查询数据集进行了大量实验，证明了所提出的IncreSTGL框架在 在线POI查询服务上的有效性。