【论文阅读】Spatio-Temporal Hypergraph Learning for Next POI Recommendation

Metadata

authors:: Xiaodong Yan, Tengwei Song, Yifeng Jiao, Jianshan He, Jiaotuan Wang, Ruopeng Li, Wei Chu
container:: Proceedings of the 46th international ACM SIGIR conference on research and development in information retrieval
year:: 2023
DOI:: 10.1145/3539618.3591770
rating:: ⭐⭐⭐⭐
share:: true
comment:: 超图聚合，关注用户间和用户内的 POI 重叠访问信息

---

前言

今年 SIGIR 最新的论文：Spatio-Temporal Hypergraph Learning for Next POI Recommendation

问题描述

给定用户集合$U=\{u_1, u_2, \cdots,u_{\vert U\vert}\}$，POI 集合$P=\{p_1, p_2, \cdots, p_{\vert P\vert} \}$以及类别集合$C=\{c_1,c_2,\cdots, c_{\vert C\vert} \}$。

（check-in）check-in 记录表示为$Q=\{ q_1, q_2, \cdots, q_{\vert Q\vert} \}$，其中$q=\langle u,p,c,g,t \rangle$，即用户$u$在$t$时刻访问地点$p$，POI 的类别为$c$，位置为$g=\langle latitude,longitude \rangle$。

（trajectories）$S=\{ s_1, s_2, \cdots, s_{\vert S\vert} \}$表示轨迹集合，根据某个时间间隔进行划分，本文为 24 小时。

（intra-user correlated）若同一个用户的两条轨迹访问过同一个 POI，则称这两条轨迹是用户内部相关的，记为$s_m \sim s_n$

（inter-user collaborated）若不同用户的两条轨迹访问过同一个 POI 并且$Jaccard(s_m, s_n) \ge \eta$，则称这两条轨迹是用户间相关的，记为$s_m \approx s_n$

$$Jaccard(s,s') = \frac{\vert s \cap s' \vert}{\vert s \cup s' \vert}$$

即，重叠的访问数量 / 访问总量

（Hypergraph）超图可以表示为$\mathcal{G}=(\mathcal{V},\mathcal{E})$，其中$\mathcal{V}$和$\mathcal{E}$分别表示点集和超边集。每条超边$e \in \mathcal{E}$都包含两个或以上的顶点$v\in\mathcal{V}$

对于当前用户$u$，我们的任务是预测用户的下一个访问地点，即next POI(Point-of-Interest) recommendation。

Hypergraph Construction

关于论文中超图的一些说明。

超图的定义

论文使用$\mathcal{H}^{(1)} \in \mathbb{R}^{\vert Q\vert\times\vert S\vert}$和$\mathcal{H}^{(2)} \in \mathbb{R}^{\vert S\vert\times\vert S\vert}$分别表示$\mathcal{V} \rightarrow \mathcal{E}$关系矩阵和$\mathcal{E} \rightarrow \mathcal{E}$超边邻接矩阵。

由于关系$\mathcal{E} \rightarrow \mathcal{E}$是异构的，因此使用$\mathbf{r}_{mn}$表示 intra-user 和 inter-user 关系。

$\mathcal{H}^{(1)}$很好理解，就是点和边的关系矩阵，每一个签到节点唯一对应一个轨迹节点

$\mathcal{H}^{(2)}$为满足$s_m \sim s_n$和$s_m \approx s_n$的边，即用户内和用户间被重复访问的 POI。

时空信息

论文使用$\Delta t_{\mathcal{V} \rightarrow \mathcal{E}}$和$\Delta s_{\mathcal{V} \rightarrow \mathcal{E}}$分别表示签到和轨迹之间的时间间隔以及空间距离，使用$\Delta t_{\mathcal{E} \rightarrow \mathcal{E}}$和$\Delta s_{\mathcal{E} \rightarrow \mathcal{E}}$分别表示轨迹之间的时间间隔以及空间距离。

对于轨迹节点的时间戳和位置信息，使用其对应的签到节点的均值来表示。

$$\begin{aligned} \Delta t_{\mathcal{V} \rightarrow \mathcal{E}} &= \{ q_{\vert s_m \vert}^t - q_k^t \vert \mathcal{H}_{km}^{(1)} = 1 \} \\ \Delta t_{\mathcal{E} \rightarrow \mathcal{E}} &= \{ s_m^t - s_n^t \vert \mathcal{H}_{mn}^{(2)} = 1 \} \\ \Delta s_{\mathcal{V} \rightarrow \mathcal{E}} &= \{ d(q_{\vert s_m \vert}^l - q_k^l) \vert \mathcal{H}_{km}^{(1)} = 1 \} \\ \Delta s_{\mathcal{E} \rightarrow \mathcal{E}} &= \{ d(s_m^l - s_n^l \vert \mathcal{H}_{mn}^{(2)} = 1 \} \\ \end{aligned}$$

其中$q_k=\langle u,p,c,g,t \rangle$，$q_k^t = t, q_k^l = g$，$d(\cdot, \cdot)$表示 Haversine 距离。

Overview

现有方法大多只关注 POI 之间的关系，而忽略了包括用户轨迹在内的高阶信息以及轨迹之间的协作关系。

为了有效捕捉从细粒度签到到粗粒度轨迹的用户运动模式之间的高阶关系，论文通过引入超图，提出了时空超图卷积网络（STHGCN）。STHGCN 对轨迹内签到之间的高阶关系以及轨迹之间的相关性进行建模，同时考虑到时空背景。

论文主要贡献：

1. 提出了一种时空超图卷积网络，它整合了复杂的高阶信息和轨迹之间的全局协作关系。
2. 利用基于相似性的范式来识别轨迹之间的相关性。此外，还引入了超图转换器，将用户间和用户内的协作信息以及时空背景信息同时结合起来。

STHGCN

Neighbor Sampler

首先，邻居采样器会获取中心轨迹的子超图，其中包含中心轨迹的协作轨迹以及属于每个轨迹的签到节点。

最下面的轨迹节点为什么只包含了 2 个签到节点？不应该是 3 个吗？$\mathcal{H}^{(1)}$ 应该没什么约束才对，不知道是不是画错了。

由于每跳邻居都涉及到轨迹和 check-ins，因此论文采用了两阶段的邻居采样流程，分别获取轨迹和 check-ins 邻居。

个人理解，论文应该是将超边都抽象成了轨迹节点。

论文将 trajectory 和 check-in 都看作是独立的节点，根据前面的定义，每一个轨迹节点以 24 小时为单位进行分割。

由于签到节点都是包含时间信息的，因此每个签到节点都是唯一的，整体类似树结构。轨迹节点主要的作用应该就是聚合每个签到节点的信息。
但这样是不是就忽略了每个轨迹节点内的顺序关系？

简单来说就是，先选择当前轨迹节点的多跳邻居，同时考虑约束条件$Jaccard(s_m, s_n) \ge \eta$，接着选择每个轨迹节点的1 跳签到节点。

Spatio-Temporal Encoder

其次，使用时空编码器对时间差和空间距离进行编码，并在超图卷积阶段合并这些信息。

对于时间信息，论文利用相对时间编码器^[1]，将连续的时间映射到$d_t$维向量空间：

$$\begin{aligned} \Phi(\Delta t)_i &= \cos(\Delta t/10^{\frac{i}{d_t}}) \\ \mathbf{t} &= \mathbf{W}_t \Phi(\Delta t) \end{aligned}$$

其中$\mathbf{t}$ 表示时间向量，$\mathbf{W}_t\in\mathbb{R}^{d_t\times d_t}$为可训练参数。

对于空间信息，利用单元嵌入层和插值嵌入层^[2]，分别对应论文的 simple linear 和 linear interpolation。

simple linear 只利用一个单位向量$\mathbf{w}_s$：

$$\mathbf{s} = \Delta s \times \mathbf{w}_s$$

linear interpolation 初始化可学习的上界$s_u$和下界$s_l$，计算公式如下：

$$\mathbf{s} = \frac{\mathbf{s}_u(\Delta s^u - \Delta s) + \mathbf{s}_l(\Delta s - \Delta s^l)}{\Delta s^u - \Delta s^l}$$

其中$\Delta s^u$和$\Delta s^\mathcal{l}$分别表示空间距离的上界和下界。

Hypergraph Transformer

最后，论文提出了一种基于消息传递神经网络（MPNN）的 hypergraph transformer，它能够在忽略时空背景信息的情况下，学习不同邻居的注意力权重。

消息传递函数可以表示为：

$$\mathbf{h}_i^{(l+1)} = \underset{\forall j \in \mathcal{N}(i)}{\mathbf{Propagate}} \{ \mathbf{Message}(\mathbf{h}_j^{(l)}), \mathbf{r}_{ij}, \mathbf{t}_{ij}, \mathbf{s}_{ij} \}$$

其中$i$和$j$分别为目标节点和源节点的索引，$\mathcal{N}(i)$为节点$i$的邻居集合，$\mathbf{h}_i^{(l+1)}$为目标节点第$(l+1)$层的隐藏层。

论文利用四种 “translation” 的组合算子来组合节点隐藏表示和边类型向量：

$$\begin{aligned} &\mathbf{Addition (Add)}: \phi(\mathbf{h}_j, \mathbf{r}_{ij}) = \mathbf{h}_j + \mathbf{r}_{ij} \\ &\mathbf{Subtraction (Sub)}: \phi(\mathbf{h}_j, \mathbf{r}_{ij}) = \mathbf{h}_j - \mathbf{r}_{ij} \\ &\mathbf{Multiplication (Mult)}: \phi(\mathbf{h}_j, \mathbf{r}_{ij}) = \mathbf{h}_j * \mathbf{r}_{ij} \\ &\mathbf{Circular\text{-}correlation (Corr)}: \phi(\mathbf{h}_j, \mathbf{r}_{ij}) = \mathbf{h}_j \star \mathbf{r}_{ij} \end{aligned}$$

然后将时间向量和距离向量相加，得到消息向量$\mathbf{m}_{ij}\in\mathbb{R}^{d_h}$：

$$\mathbf{m}_{ij}^{(l)} = \phi(\mathbf{h}_j^{(l)}, \mathbf{r}_{ij}) + \mathbf{t}_{ij} + \mathbf{s}_{ij}$$

接着进行 Attention，以$\mathbf{h}_i^{(l+1)}$作为$Q$，$\mathbf{m}_{ij}^{(l)}$作为$K, V$

$$\begin{aligned} \mathbf{Q}^{(k,l)} &= \mathbf{W}_Q^{(k,l)}\mathbf{h}_i^{(k,l)}, \mathbf{K}^{(k,l)} = \mathbf{W}_K^{(k,l)}\mathbf{m}_{ij}^{(k,l)}, \mathbf{V}^{(k,l)} = \mathbf{W}_V^{(k,l)}\mathbf{m}_{ij}^{(k,l)} \\ \mathbf{h}_i^{(l+1)} &= \Vert_{k=1}^h \mathbf{Softmax} \left ( \frac{\mathbf{Q}^{(k,l)}(\mathbf{K}^{(k,l)})^T}{\sqrt{d_h}} \right) \mathbf{V}^{(k,l)} \end{aligned}$$

其中$\Vert$表示连接操作，$k$表示 Attention 头号。

Hyperedge Learning and Prediction

超边缘（轨迹）表征学习由三部分组成：原始签到特征、
通过聚合来自邻近签到的轨迹特征，通过协作轨迹的信息传递更新轨迹隐藏特征。

原始签到特征：除了时间戳信息之外，论文引入 hour 信息以及 day-of-week 信息进行拼接：

$$\mathbf{x} = \Vert_{\forall i\in \{ u,p,c,t_h,t_d\}} f_{embed}(i)$$

由于轨迹节点一开始并没有原始的特征，因此$\theta \triangleq \Vert_{k=1}^h \theta^{(k)}$表示所有的轨迹在聚合邻居消息之前都共享相同的初始嵌入：

$$\begin{aligned} \mathbf{m}_{ij}^{(0)} &= \phi(\mathbf{x}_j, \mathbf{r}_{ij}) + \mathbf{t}_{ij} + \mathbf{s}_{ij} \\ \mathbf{Q}^{(k,0)} &= \theta^{(k)}, \mathbf{K}^{(k,0)} = \mathbf{W}_K^{(k,0)}\mathbf{m}_{ij}^{(0)}, \mathbf{V}^{(k,0)} = \mathbf{W}_V^{(k,0)}\mathbf{m}_{ij}^{(0)} \\ \mathbf{h}_i^{(1)} &= \Vert_{k=1}^h \mathbf{Softmax} \left( \frac{\mathbf{Q}^{(k,0)}(\mathbf{K}^{(k,0)})^T}{\sqrt{d_h}} \right) \mathbf{V}^{(k,0)} \end{aligned}$$

论文使用残差连接和层归一化技能来避免初始信息的丢失，然后使用多层感知器（MLP）嵌入到$d_h$特征空间：

$$\begin{aligned} \mathbf{h}_i^{(1)} &= \mathbf{LN}(\theta + \mathbf{h}_i^{(1)}) \\ \mathbf{h}_i^{(1)} &= \mathbf{Norm} (\sigma(\mathbf{h}_i^{(1)} \mathbf{W}_0^{(0)} + \mathbf{b}_0^{(0)})\mathbf{W}_1^{(0)} + \mathbf{b}_1^{(0)} ) \end{aligned}$$

其中$\mathbf{LN}$和${Norm}$分别表示 layer normalization 和 L2 normalization，$\sigma$为 ReLU 激活函数

除了在第一层使用 “Add & LayerNorm” 用来平衡信息之外，其他层使用 “linear + gated residual”：

$$\begin{aligned} \mathbf{g}_i^{(l+1)} &= \mathbf{Hypergraph\text{ }Transformer}(\mathbf{h}_i^{(l)}, \mathbf{h}_j^{(l)}, \mathbf{r}_{ij}, \mathbf{s}_{ij}) \\ \mathbf{h}_i^{(l+1)} &= \beta(\mathbf{h}_i^{(l)}\mathbf{W}_2^{(l)} + \mathbf{b}_2^{(l)}) + (1-\beta)\mathbf{g}_i^{(l+1)} \\ \mathbf{h}_i^{(l+1)} &= \mathbf{Norm}(\sigma(\mathbf{h}_i^{(l+1)}\mathbf{W}_0^{(l)} + \mathbf{b}_0^{(l)})\mathbf{W}_1^{(l)} + \mathbf{b}_1^{(l)}) \end{aligned}$$

其中$\beta$为超参数，表示残差权重。

最后将隐藏层表示映射到 POI ID 空间得到预测结果：

$$\hat{\mathbf{y}}_i = \mathbf{Softmax}(\mathbf{h}_i^{(L)}\mathbf{W}_o + \mathbf{b}_o)$$

交叉熵损失函数计算损失：

$$\mathcal{L} = -\frac{1}{N}\sum_{i=1}^N \sum_{p=1}^{\vert P\vert} \mathbf{y}_i \log \hat{\mathbf{y}}_i$$

实验

Results

Global Collaborative Effect

Spatio-temporal Encoder Variants

User cold-start Analysis

Behavior Diversity Analysis

Hyperparameter Sensitivity Study

Ablation Study

总结

论文将主要的关注点放在用户间和用户内的 POI 重叠访问信息，并使用超图进行表示、聚合。此外，在超图构建时，将轨迹节点和签到节点独立表示，轨迹节点用来抽象其内部签到节点总体信息，但这样是不是也损失了轨迹内的顺序信息，个人感觉说不好吧。

参考资料

• [1] Heterogeneous Graph Transformer
• [2] STAN: Spatio-Temporal Attention Network for Next Location Recommendation
• [3] Spatio-Temporal Hypergraph Learning for Next POI Recommendation