【论文阅读】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

问题描述

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

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

next POI recommendation)给定每个用户uu的的活动轨迹HH,预测用户下一时刻最可能去的 POI top-kk

OverView

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

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

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

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

例如l3l_3l4l_4作用相同,l4l_4甚至距离l2l_2更近,但或许由于物理因素的影响(例如河流),用户还是选择了l3l_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,A)G=(V,E,\boldsymbol{A}),其中V,EV,E分别表示节点和边,ARn×n\boldsymbol{A}\in\mathbb{R}^{n\times n}为带权重的邻接矩阵。GCN 首先在A\boldsymbol{A}加上单位矩阵I\boldsymbol{I}进行自连接:

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

接着对mm维的节点进行更新操作:

Xupdate=(D+I)1/2A^(D+I)1/2XΘ=A~XΘ\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}为可学习权重矩阵,D\boldsymbol{D}为度矩阵。

Disentangled Representation

POI 的分解表示xRdx\in\mathbb{R}^d由几个独立的部分组成。假定分解为KK部分,则可以将其表示为:

xi=(xi1,xi2,,xiK)x_i = (x_{i_1}, x_{i_2}, \cdots, x_{i_K})

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

DRAN

模型的架构如下图所示:

Graph-based Disentangled Representation Modeling

POI Relation Graph Construction

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

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

Disentangled Representation Propagation

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

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

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

Xupdate(m,n)=i=1NA(m,i)(j=index(xmk(1))index(xmk(fin))X(i,j)Θ(j,n))\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(xmk(1)),index(xmk(fin))index(x_{m_k}(1)), index(x_{m_k}(fin))分别表示xmk\boldsymbol{x}_{m_k}第一个维度和最后一个维度的索引。

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

Xupdate=A~XΘblockΘblock=diag(Θ1,Θ2,,ΘK),ΘiRdK×dK\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}

这保证了在更新xijupdatex_{i_j}^{update}的过程中,只计算xix_i的第jj个部分。

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

{Xd(l+1)=tanh(A~XdlΘblock,dl)Xt(l+1)=tanh(A~XtlΘblock,tl)\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}

其中ll为层数。

Representation Aggregation

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

{Xd=Sum(Xd0,Xd1,,XdL)Xt=Sum(Xt0,Xt1,,XtL)\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 关系矩阵进行适当表示,以模拟KK个部分的分解表示之后,一个简单的想法是这将两个部分串联起来最为最终的表示。但是论文考虑到两个原因并没有这么做:

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

POI lil_i的最终表示xiXfinx_i\in\boldsymbol{X}_{fin}分别对各个分解部分进行加权处理:

{xi=(xi1,xi2,,xiK)xij=ωjxd,ij+(1ωj)xt,ij\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}

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

User Spatial-Temporal Preference Modeling

在得到到了 POI 的分解表示Xfin\boldsymbol{X}_{fin}之后,开始对用户轨迹H(u)={(liu,tliu)i=1,2,,m}H(u) = \{ (l_i^u, t_{l_i^u}) \vert i=1,2,\cdots,m \}进行编码,得到用户uu的访问序列S(u)={x1u,x2u,,xnu},xiuXfinS(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 之间的时间空间关系进行建模,时间间隔矩阵MtuNn×n\boldsymbol{M}_t^u\in\mathbb{N}^{n\times n},以及空间间隔矩阵MsuNn×n\boldsymbol{M}_s^u\in\mathbb{N}^{n\times n}表示如下:

Mtu=[t1,1ut1,2ut1,nut2,1ut2,2ut2,nutn,1utn,2utn,nu]Msu=[s1,1us1,2us1,nus2,1us2,2us2,nusn,1usn,2usn,nu]\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}

其中ti,ju=titjtminut_{i,j}^u = \left\lfloor \frac{\vert t_i -t_j \vert}{t_{min}^u} \right\rfloor表示访问地点iijj的时间间隔;tminut_{min}^u表示用户uu的最小时间间隔;si,ju=haversine(liu,lju)sminus_{i,j}^u = \left\lfloor \frac{haversine(l_i^u, l_j^u)}{s_{min}^u} \right\rfloorti,jut_{i,j}^u类似,表示两个地点之间的空间间隔。

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

ti,ju=min(ti,ju,Δt)si,ju=min(si,ju,Δs)t_{i,j}^u = min(t_{i,j}^u, \Delta t) \quad s_{i,j}^u = min(s_{i,j}^u, \Delta s)

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

Etu=[e1,1u,te1,2u,te1,nu,te2,1u,te2,2u,te2,nu,ten,1u,ten,2u,ten,nu,t]Esu=[e1,1u,se1,2u,se1,nu,se2,1u,se2,2u,se2,nu,sen,1u,sen,2u,sen,nu,s]\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={x1ku,x2ku,,xnku}S(u)_k = \{ x_{1_k}^u, x_{2_k}^u, \cdots, x_{n_k}^u \}

其中1kK,xikuRdK1\leq k\leq K,x_{i_k}^u\in\mathbb{R}^\frac{d}{K}表示xiux_i^u的第kk个部分。同时将boldsymbolEtuboldsymbol{E}_t^u的每个单元分为kk个部分:ei,ju=(ei,j,1u,ei,j,2u,,ei,j,Ku)\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={r1ku,r2ku,,rnku}R(u)_k=\{\boldsymbol{r}_{1_k}^u, \boldsymbol{r}_{2_k}^u, \cdots, \boldsymbol{r}_{n_k}^u\}

riku=j=1iαij(xjkuWV+ei,j,ku,t+ei,j,ku,s+pj)\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)

其中WVRdK×dK\boldsymbol{W}^V\in\mathbb{R}^{\frac{d}{K}\times\frac{d}{K}}为可学习矩阵;pjRdK\boldsymbol{p}_j\in\mathbb{R}^\frac{d}{K}为 position embedding;αij\alpha_{ij}表示权重系数,并由下式确定:

{αij=expaijm=1iexpaimaij=xikuWQ(xjkuWK+ei,j,ku,t+ei,j,ku,s+pj)TdK\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}

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

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

接着在 self-attention 层之后使用前馈神经网络(FFN),基于模型非线性特征:

ziku=FFN(riku)=ReLU(rikuW1k+b1k)W2k+b2kz_{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}

其中W1k,W2kRdK×dK,b1k,b2kRdK\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={z1ku,z2ku,,znku}Z(u)_k=\{z_{1_k}^u,z_{2_k}^u,\cdots,z_{n_k}^u\},包含 POI,位置,时间和空间等信息,可以看做是用户对于 POI 第kk个部分的偏好表示。为了完整考虑 POI 每个部分的影响,将所有的KK个输出序列集成到一个整体的序列Z(u)Z(u)中,以表示用户uu的整个签到行为:

Z(u)=Concat(Z(u)1,Z(u)2,,Z(u)K)=(z1u,z2u,,znu)Z(u) = Concat(Z(u)_1, Z(u)_2, \cdots, Z(u)_K) = (z_1^u, z_2^u, \cdots, z_n^u)

其中Concat()Concat(\cdot)表示连接操作,ziu=[zi1u,zi2u,,znKu]z_i^u=[z_{i_1}^u,z_{i_2}^u,\cdots,z_{n_K}^u]

User Preference Estimation

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

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

其中ztuZ(u)z_t^u\in Z(u)表示用户在tt时刻的偏好,xXfinx\in X_{fin}为位置ll的分解表示。此外上面的式子也可以重写为:

exp(ztuxlT)=exp(k=1Ki=1dKztku(i),xk(i))\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

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

J=uUiH(u)j=1Nyi,julog(y^i,ju)+λΘ2\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

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

实验

Datasets

Result

Ablation Study

  • DRANnGDRAN_{nG}:去除 DGCN 层
  • DRANndDRAN_{nd}:去除基于距离的 POI 关系矩阵
  • DRANntDRAN_{nt}:去除基于转移的 POI 关系矩阵

In-depth Study

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

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

总结

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

参考资料