【论文阅读】Learning Graph-based Disentangled Representations for Next POI Recommendation

Metadata

authors:: Zhaobo Wang, Yanmin Zhu, Haobing Liu, Chunyang Wang
container:: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval
year:: 2022
DOI:: 10.1145/3477495.3532012
rating:: ⭐⭐⭐⭐
share:: false
comment:: 将 POI 分解为多个维度进行表示，利用 GCN 进行特征提取，采用多头注意力对各个分解维度进行处理

---

前言

2022 年 SIGIR：Learning Graph-based Disentangled Representations for Next POI Recommendation

问题描述

分别给定用户集合$\mathcal{U} = \{ u_1, u_2, \cdots, u_M \}$以及 POI 集合$\mathcal{L} = \{ l_1, l_2, \cdots, l_N \}$，其中每个位置$l_i$都有一个对应的$(lat, lon)$坐标相关联。

（user trajectory）用户轨迹是由特定用户的一系列时间顺序的签到记录来定义的，即$H(u) = \{ (l_i^u, t_{l_i^u}) \vert i=1,2,\cdots,m \}$，表示用户$u$在$t_{l_i^u}$时刻访问位置$l_i^u$。

（next POI recommendation）给定每个用户$u$的活动轨迹$H$，预测用户下一时刻最可能去的 POI top-$k$。

OverView

论文认为，以前的合并地理信息的方法不能模拟 POI 对用户的复杂影响：

1. 首先，用户到某个 POI 的各种潜在因素没有被有效地分解开。

例如用户$u_1$去$l_3$的主要原因是个人偏好，尽管$l_3$距离他当前的位置$l_1$较远。另外一方面，用户$u_2$更关注$l_3$本身的作用（例如为餐厅），并且更关心距离。然而现有方法大多专注于黑盒模型的训练，将这些因素忽略了。

2. 其次，在以往的大多数方法中，POI 的基于距离的影响也过于简化了。

例如$l_3$和$l_4$作用相同，$l_4$甚至距离$l_2$更近，但或许由于物理因素的影响（例如河流），用户还是选择了$l_3$。因此，POI 之间的距离影响可能包含多种因素，仅仅基于距离的表示并不合理。

为了解决上面这些问题，论文专注于对 POI 进行更好地表征，提出了一个新的 Disentangled Representation-enhanced Attention Network (DRAN)，将 POI 表示分解为多个独立的分量；提出了 Disentangled Graph Convolution Network (DGCN) 学习 POI 表征，并对 self-Attention 进行拓展，以及建模用户偏好。论文主要贡献如下：

1. 明确了 POI 包含的多方面因素并进行分解，并提出 DGCN 进行实现；
2. 提出 DRAN，充分利用 POI 全局信息并学习用户的动态偏好。

准备工作

Graph Convolution

图卷积运算可以看作是一种节点表示学习方法，它通过聚合邻居节点的信息来更新节点表示。

关于 GCN 的内容可以看我的另一篇文章：简单理解图神经网络 GNN，这里只进行简单的说明：对于一幅无向图$G=(V,E,\boldsymbol{A})$，其中$V,E$分别表示节点和边，$\boldsymbol{A}\in\mathbb{R}^{n\times n}$为带权重的邻接矩阵。GCN 首先在$\boldsymbol{A}$加上单位矩阵$\boldsymbol{I}$进行自连接：

$$\hat{\boldsymbol{A}} = \boldsymbol{A + I}$$

接着对$m$维的节点进行更新操作：

$$\boldsymbol{X}^{update} = (\boldsymbol{D} + \boldsymbol{I})^{-1/2}\hat{\boldsymbol{A}}(\boldsymbol{D} + \boldsymbol{I})^{-1/2}\boldsymbol{X\Theta} = \tilde{\boldsymbol{A}}\boldsymbol{X\Theta}$$

其中$\boldsymbol{\Theta}$为可学习权重矩阵，$\boldsymbol{D}$为度矩阵。

Disentangled Representation

POI 的分解表示$x\in\mathbb{R}^d$由几个独立的部分组成。假定分解为$K$部分，则可以将其表示为：

$$x_i = (x_{i_1}, x_{i_2}, \cdots, x_{i_K})$$

其中$x_{i_j}\in\mathbb{R}^{\frac{d}{K}}$表示 POI 的第$j$个部分

DRAN

模型的架构如下图所示：

Graph-based Disentangled Representation Modeling

POI Relation Graph Construction

为了更好地学习 POI 的内在特征，论文提出了两个 POI 全局关系图来更好地进行特征学习：距离矩阵和转移矩阵。

• Distance-based relation graph：$G_d=(V_d,E_d,\boldsymbol{A}_d)$是一个无向图，分别表示 POI 节点、边以及邻接矩阵。若两个 POI 之间的距离小于$\Delta d=2km$，那么$\boldsymbol{A}_d(i,j)=1$，否则$\boldsymbol{A}_d(i,j)=0$。
• Transition-based relation graph：$G_t=(V_t,E_t,\boldsymbol{A}_t)$是一个带权图，其中$\boldsymbol{A}_t(i,j)=freq(l_i,l_j)$，表示两个 POI 之间有直接的转移关系，$freq(l_i,l_j)$为转移频次。

Disentangled Representation Propagation

论文希望利用 GCN 从 POI 关系矩阵中学习其分解表示，同时保持不同部分的独立。计算如下：

$$\boldsymbol{X}^{update}(m,n) = \sum_{i=1}^{N}\boldsymbol{A}(m,i)(\sum_{j=1}^N \boldsymbol{X}(i,j)\Theta(j,n))$$

在上面的公式中，$\boldsymbol{x}_m$的每个维度与其他维度都具有非常强的关联，这限制了 POI 分解表示的能力。因此，论文只将同个 POI 内的不同维度相互关联：

$$\boldsymbol{X}^{update}(m,n) = \sum_{i=1}^{N}\boldsymbol{A}(m,i)(\sum_{j=index(x_{m_k}(1))}^{index(x_{m_k}(fin))} \boldsymbol{X}(i,j)\Theta(j,n))$$

其中$index(x_{m_k}(1)), index(x_{m_k}(fin))$分别表示$\boldsymbol{x}_{m_k}$第一个维度和最后一个维度的索引。

此外，论文将全局权重矩阵$\boldsymbol{\Theta}$推广到了块对角权重矩阵$\boldsymbol{\Theta}_{block}$，论文提出的 DGCN 可以表示为：

$$\begin{aligned} \boldsymbol{X}^{update} &= \tilde{\boldsymbol{A}}\boldsymbol{X\Theta}_{block} \\ \boldsymbol{\Theta}_{block} &= diag(\boldsymbol{\Theta}_1, \boldsymbol{\Theta}_2, \cdots, \boldsymbol{\Theta}_{K}), \boldsymbol{\Theta}_i\in\mathbb{R}^{\frac{d}{K}\times\frac{d}{K}} \end{aligned}$$

这保证了在更新$x_{i_j}^{update}$的过程中，只计算$x_i$的第$j$个部分。

接着，论文使用 DGCN 分别计算之前提到的两个 POI 关系矩阵：基于距离的分解表示$x_d\in\boldsymbol{X}_d$和基于转移的分解表示$x_t\in\boldsymbol{X}_t$。论文同时对 DGCN 进行了多次堆叠，具体来说：

$$\begin{cases} \boldsymbol{X}_d^{(l+1)} &= \tanh(\tilde{\boldsymbol{A}}\boldsymbol{X}_d^l\boldsymbol{\Theta}_{block,d}^l) \\ \boldsymbol{X}_t^{(l+1)} &= \tanh(\tilde{\boldsymbol{A}}\boldsymbol{X}_t^l\boldsymbol{\Theta}_{block,t}^l) \end{cases}$$

其中$l$为层数。

Representation Aggregation

在 POI 关系矩阵上应用了$L$层的 DGCN 之后，使用聚合策略将多层表示进行聚合，论文中直接相加：

$$\begin{cases} \boldsymbol{X}_d &= Sum(\boldsymbol{X}_d^0, \boldsymbol{X}_d^1, \cdots, \boldsymbol{X}_d^L) \\ \boldsymbol{X}_t &= Sum(\boldsymbol{X}_t^0, \boldsymbol{X}_t^1, \cdots, \boldsymbol{X}_t^L) \end{cases}$$

在对两个 POI 关系矩阵进行适当表示，以模拟$K$个部分的分解表示之后，一个简单的想法是这将两个部分串联起来最为最终的表示。但是论文考虑到两个原因并没有这么做：

1. 需要引入超参数来平衡两者之间的比例，可能无法保持不同类型的影响；
2. POI 本身就包含不同因素的影响，只表示为一种特殊类型可能会限制其能力。

POI $l_i$的最终表示$x_i\in\boldsymbol{X}_{fin}$分别对各个分解部分进行加权处理：

$$\begin{cases} x_i &= (x_{i_1}, x_{i_2}, \cdots, x_{i_K}) \\ x_{i_j} &= \omega_j x_{d,i_j} + (1-\omega_j)x_{t,i_j} \end{cases}$$

其中$\omega_j$为可学习参数，控制两个部分的权重。

User Spatial-Temporal Preference Modeling

在得到到了 POI 的分解表示$\boldsymbol{X}_{fin}$之后，开始对用户轨迹$H(u) = \{ (l_i^u, t_{l_i^u}) \vert i=1,2,\cdots,m \}$进行编码，得到用户$u$的访问序列$S(u)=\{x_1^u, x_2^u,\cdots,x_n^u\}, x_i^u\in\boldsymbol{X}_{fin}$。

Personalized Spatial-Temporal Interval Encoding

通常来说，用户对 POI 的偏好很大程度上受空间距离的限制，用户更愿意访问附近的 POI。此外，用户的历史轨迹也在一定程度上反映出了用户偏好。因此论文明确了 POI 之间的时间空间关系进行建模，时间间隔矩阵$\boldsymbol{M}_t^u\in\mathbb{N}^{n\times n}$，以及空间间隔矩阵$\boldsymbol{M}_s^u\in\mathbb{N}^{n\times n}$表示如下：

$$\boldsymbol{M}_t^u = \begin{bmatrix} t_{1,1}^u & t_{1,2}^u & \cdots & t_{1,n}^u \\ t_{2,1}^u & t_{2,2}^u & \cdots & t_{2,n}^u \\ \cdots & \cdots & \cdots & \cdots \\ t_{n,1}^u & t_{n,2}^u & \cdots & t_{n,n}^u \end{bmatrix} \quad \boldsymbol{M}_s^u = \begin{bmatrix} s_{1,1}^u & s_{1,2}^u & \cdots & s_{1,n}^u \\ s_{2,1}^u & s_{2,2}^u & \cdots & s_{2,n}^u \\ \cdots & \cdots & \cdots & \cdots \\ s_{n,1}^u & s_{n,2}^u & \cdots & s_{n,n}^u \end{bmatrix}$$

其中$t_{i,j}^u = \left\lfloor \frac{\vert t_i -t_j \vert}{t_{min}^u} \right\rfloor$表示访问地点$i$和$j$的时间间隔；$t_{min}^u$表示用户$u$的最小时间间隔；$s_{i,j}^u = \left\lfloor \frac{haversine(l_i^u, l_j^u)}{s_{min}^u} \right\rfloor$与$t_{i,j}^u$类似，表示两个地点之间的空间间隔。

假设在较大的时间间隔内的访问可能是冗余的，论文也规定了最大时间/空间间隔：

$$t_{i,j}^u = min(t_{i,j}^u, \Delta t) \quad s_{i,j}^u = min(s_{i,j}^u, \Delta s)$$

之后将$\boldsymbol{M}_t^u,\boldsymbol{M}_s^u$分别转化为嵌入矩阵$\boldsymbol{E}_t^u\in\mathbb{R}^{n\times n\times d},\boldsymbol{E}_s^u\in\mathbb{R}^{n\times n\times d}$：

$$\boldsymbol{E}_t^u = \begin{bmatrix} \boldsymbol{e}_{1,1}^{u,t} & \boldsymbol{e}_{1,2}^{u,t} & \cdots & \boldsymbol{e}_{1,n}^{u,t} \\ \boldsymbol{e}_{2,1}^{u,t} & \boldsymbol{e}_{2,2}^{u,t} & \cdots & \boldsymbol{e}_{2,n}^{u,t} \\ \cdots & \cdots & \cdots & \cdots \\ \boldsymbol{e}_{n,1}^{u,t} & \boldsymbol{e}_{n,2}^{u,t} & \cdots & \boldsymbol{e}_{n,n}^{u,t} \end{bmatrix} \quad \boldsymbol{E}_s^u = \begin{bmatrix} \boldsymbol{e}_{1,1}^{u,s} & \boldsymbol{e}_{1,2}^{u,s} & \cdots & \boldsymbol{e}_{1,n}^{u,s} \\ \boldsymbol{e}_{2,1}^{u,s} & \boldsymbol{e}_{2,2}^{u,s} & \cdots & \boldsymbol{e}_{2,n}^{u,s} \\ \cdots & \cdots & \cdots & \cdots \\ \boldsymbol{e}_{n,1}^{u,s} & \boldsymbol{e}_{n,2}^{u,s} & \cdots & \boldsymbol{e}_{n,n}^{u,s} \end{bmatrix}$$

Disentangled Self-Attention Aggregation

为了捕获签到序列的多层次规律，论文提出了一种拓展的 self-attention。具体来说，将每个部分分为一个单独的注意力头：

$$S(u)_k = \{ x_{1_k}^u, x_{2_k}^u, \cdots, x_{n_k}^u \}$$

其中$1\leq k\leq K,x_{i_k}^u\in\mathbb{R}^\frac{d}{K}$表示$x_i^u$的第$k$个部分。同时将$boldsymbol{E}_t^u$的每个单元分为$k$个部分：$\boldsymbol{e}_{i,j}^u=(\boldsymbol{e}_{i,j,1}^u, \boldsymbol{e}_{i,j,2}^u, \cdots, \boldsymbol{e}_{i,j,K}^u)$，并根据下面的公式计算新序列$R(u)_k=\{\boldsymbol{r}_{1_k}^u, \boldsymbol{r}_{2_k}^u, \cdots, \boldsymbol{r}_{n_k}^u\}$：

$$\boldsymbol{r}_{i_k}^u = \sum_{j=1}^i \alpha_{ij}(x_{j_k}^u\boldsymbol{W}^V + \boldsymbol{e}_{i,j,k}^{u,t} + \boldsymbol{e}_{i,j,k}^{u,s} + \boldsymbol{p}_j)$$

其中$\boldsymbol{W}^V\in\mathbb{R}^{\frac{d}{K}\times\frac{d}{K}}$为可学习矩阵；$\boldsymbol{p}_j\in\mathbb{R}^\frac{d}{K}$为 position embedding；$\alpha_{ij}$表示权重系数，并由下式确定：

$$\begin{cases} \alpha_{ij} = \frac{\exp a_{ij}}{\sum_{m=1}^{i}\exp a_{im}} \\ a_{ij} = \frac{x_{i_k}^u\boldsymbol{W}^Q (x_{j_k}^u\boldsymbol{W}^K + \boldsymbol{e}_{i,j,k}^{u,t} + \boldsymbol{e}_{i,j,k}^{u,s} + \boldsymbol{p}_j)^T}{\sqrt{\frac{d}{K}}} \end{cases}$$

其中$\boldsymbol{W}^Q, \boldsymbol{W}^K\in\mathbb{R}^{\frac{d}{K}\times\frac{d}{K}}$为可学习矩阵

论文提到，将$\boldsymbol{e}_{i,j}^u$拆分的主要目的在于降维；与另一种方法相比，将$\boldsymbol{e}_{i,j}^u$映射到一个维度为$\mathbb{R}^\frac{d}{K}$的向量，两者的性能接近，为了避免过多参数，论文选择了前一种方法。

接着在 self-attention 层之后使用前馈神经网络（FFN），基于模型非线性特征：

$$z_{i_k}^u = FFN(\boldsymbol{r}_{i_k}^u) = ReLU(\boldsymbol{r}_{i_k}^u\boldsymbol{W}_{1_k} + \boldsymbol{b}_{1_k})\boldsymbol{W}_{2_k} + \boldsymbol{b}_{2_k}$$

其中$\boldsymbol{W}_{1_k}, \boldsymbol{W}_{2_k}\in\mathbb{R}^{\frac{d}{K}\times\frac{d}{K}}, \boldsymbol{b}_{1_k}, \boldsymbol{b}_{2_k}\in\mathbb{R}^\frac{d}{K}$为可学习矩阵。同时使用 dropout，normalization 和残差连接缓解过拟合问题，加快模型训练。

在叠加了几个注意块后，得到了输出序列$Z(u)_k=\{z_{1_k}^u,z_{2_k}^u,\cdots,z_{n_k}^u\}$，包含 POI，位置，时间和空间等信息，可以看做是用户对于 POI 第$k$个部分的偏好表示。为了完整考虑 POI 每个部分的影响，将所有的$K$个输出序列集成到一个整体的序列$Z(u)$中，以表示用户$u$的整个签到行为：

$$Z(u) = Concat(Z(u)_1, Z(u)_2, \cdots, Z(u)_K) = (z_1^u, z_2^u, \cdots, z_n^u)$$

其中$Concat(\cdot)$表示连接操作，$z_i^u=[z_{i_1}^u,z_{i_2}^u,\cdots,z_{n_K}^u]$。

User Preference Estimation

得到了用户$u$的偏好序列$Z(u)$之后，为了估计用户对下一次访问的 POI 的偏好，使用 softmax 函数计算每个候选位置的偏好得分：

$$\hat{y}_{t+1,l}^u = \frac{\exp(z_t^ux_l^T)}{\sum_{i=1}^\mathbb{L}\exp(z_t^ux_i^T)}$$

其中$z_t^u\in Z(u)$表示用户在$t$时刻的偏好，$x\in X_{fin}$为位置$l$的分解表示。此外上面的式子也可以重写为：

$$\exp(z_t^ux_l^T) = \exp(\sum_{k=1}^K\sum_{i=1}^{\frac{d}{K}} z_{t_k}^u(i) \cdot, x_k(i))$$

将偏好得分看作是通过和操作对不同成分的综合偏好。

Model Optimization

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

$$\mathbb{J} = - \sum_{u\in\mathcal{U}} \sum_{i\in H(u)}\sum_{j=1}^N y_{i,j}^u \log(\hat{y}_{i,j}^u) + \lambda \Vert\Theta\Vert_2$$

其中$y_{i,j}^u$为预测概率，$\Vert\Theta\Vert_2$表示对所有参数计算二范式。

实验

Datasets

Result

Ablation Study

• $DRAN_{nG}$：去除 DGCN 层
• $DRAN_{nd}$：去除基于距离的 POI 关系矩阵
• $DRAN_{nt}$：去除基于转移的 POI 关系矩阵

In-depth Study

进一步地，论文展示了不同 GCN 模型下的效果比较：

另一方面，为了证明 DRAN 可以有效地用 DGCN 学习 POI 的分解表示，论文计算了两个数据集上，维数的相关性，并进行了可视化展示。可以看出，结果显示了四个明显的对角线块，这表明模型具有很强的区分潜在成分的能力：

总结

论文的内容挺多，最主要的想法就是将 POI 进行分解，从不同部分对其进行表示，从最后的可视化效果图来看确实有一定作用。

参考资料

• [1] Learning Graph-based Disentangled Representations for Next POI Recommendation