【论文阅读】DisenPOI Disentangling sequential and geographical influence for point-of-interest recommendat
【论文阅读】DisenPOI Disentangling sequential and geographical influence for point-of-interest recommendat
【论文阅读】DisenPOI: Disentangling sequential and geographical influence for point-of-interest recommendation
前言
2023 年，WSDM 的一篇论文：DisenPOI: Disentangling sequential and geographical influence for point-of-interest recommendation
问题描述
分别给定用户集合U={u1,u2,⋯ ,u∣U∣}\mathcal{U} = \{ u_1, u_2, \cdots, u_{\vert \mathcal{U} \vert} \}U={u1,u2,⋯,u∣U∣}以及 POI 集合V={v1,v2,⋯ ,v∣V∣}\mathcal{V} = \{ v_1, v_2, \cdots, v_{\vert \mathcal{V} \vert} \}V={v1,v2,⋯,v∣V∣}，其中每个位置viv_ivi都有一个对应的(lat,lon)(lat, lon)(lat,lon)坐标相关联。
（check-in）一个 check-in 可以表示为c=(u,v,t)c=(u,v,t)c=(u,v,t)，即用户uuu在ttt时刻访问地点vvv。
（user trajectory）用户轨迹是由特定用户的一系列时间顺序的签到记录来定义的，即Tui={c1,c2,⋯ ,cm}T_{u_i} = \{ c_1, c_2, \cdots, c_m \}Tui={c1,c2,⋯,cm}。
（next POI recommendation）给定知识图G\mathcal{G}G，每个用户uiu_iui的的活动轨迹TuiT_{u_i}Tui，预测用户uiu_iui最可能去的 POI top-kkk。
OverView
论文认为「序列影响」和「地理影响」这两个在 POI 推荐中非常重要的因素应该是平等的，是 POI 推荐的两个主要驱动力。以前的研究并没有对这两种因素进行区分，没有明确捕获用户偏好中的序列影响和地理影响。
面对用户偏好的双重影响，论文想要通过解耦的方式对两种因素进行更精细粒度的描述。论文提出了 DisenPOI，对顺序关系和地理位置进行建模，并构建了两个解耦的 POI 图：「基于空间亲和力的地理图」和「基于交互历史的序列图」，通过距离感知和序列感知的 GNN 进行特征提取，以自监督的方式进行图的解构。
论文的主要贡献如下：
- 根据用户的访问交互构造对偶图，以联合利用序列和地理关系，分别为两个图设计序列和地理感知传播方案，以提高 embedding 质量。
- 提出提取序列和地理影响的解耦表示。这是第一个基于图的 POI 推荐框架，可以得到解耦的序列和地理表示。
主要内容
模型整体结构如下图所示：
简单说一下模型的整体思路：经过 Embedding 层之后，分别建立序列图和地理图，并使用两个聚合模块进行聚合，在 Target Attention 层中提取偏好信息，同时引入了一个辅助损失函数来帮助获取解构的信息。
Two Disentangled Graphs
Geographical Graph
地理位置图是根据 POI 建立的一张无向图Gg={V,εg,Ag}\mathcal{G}_g = \{ \mathcal{V}, \varepsilon_g, A_g \}Gg={V,εg,Ag}，若viv_ivi和vjv_jvj之间的距离小于阈值Δ\DeltaΔ，那么则用边eg=(vi,vj)∈εge_g = (v_i, v_j) \in \varepsilon_geg=(vi,vj)∈εg表示。边权重矩阵Ag(i,j)A_g(i,j)Ag(i,j)记录 POI viv_ivi和vjv_jvj之间的距离。建立图Gg\mathcal{G}_gGg是基于用户通常会访问距离较近的 POI。
Sequential Graph
根据访问序列建立序列图Gs,u={Vs,u,εs,u}\mathcal{G}_{s,u} = \{ \mathcal{V}_{s,u}, \varepsilon_{s,u} \}Gs,u={Vs,u,εs,u}，其中sus_usu为用户历史访问轨迹，边es=⟨vi,vj⟩∈Gse_s = \langle v_i, v_j \rangle \in \mathcal{G_s}es=⟨vi,vj⟩∈Gs表示存在viv_ivi到vjv_jvj的转移关系。
Propagation on Disentangled Graphs
Geographical Graph Propagation Layer
论文使用 GNN 对地理图Gg\mathcal{G}_gGg进行聚合：
mj←i(l)=fd(hi(l−1),hj(l−1))m_{j\leftarrow i}^{(l)} = f_d(h_i^{(l-1)}, h_j^{(l-1)}) mj←i(l)=fd(hi(l−1),hj(l−1))
其中fd(⋅)f_d(\cdot)fd(⋅)为消息传播函数，lll为循环层数。为了更好地表现地理位置信息，论文的传播函数中加入了距离信息：
mj←i(l)=1∣Ni∣∣Nj∣(W1(l)hi(l−1)+w(dij)W2(l)hi(l−1)⊙hj(l−1))m_{j \leftarrow i}^{(l)} = \frac{1}{\sqrt{\vert \mathcal{N}_i \vert \vert \mathcal{N}_j \vert}}(W_1^{(l)}h_i^{(l-1)} + w(d_{ij})W_2^{(l)}h_{i}^{(l-1)} \odot h_{j}^{(l-1)}) mj←i(l)=∣Ni∣∣Nj∣1(W1(l)hi(l−1)+w(dij)W2(l)hi(l−1)⊙hj(l−1))
其中W1,W2∈RD×DW_1, W_2 \in \mathbb{R}^{D\times D}W1,W2∈RD×D为可学习参数矩阵，w(dij)=e−di,j2w(d_{ij}) = e^{-d_{i,j}^2}w(dij)=e−di,j2表示viv_ivi和vjv_jvj的距离信息。最终的消息传播函数为：
hj(l)=LeakyReLU(mj←i+∑i∈Numj←i)h_{j}^{(l)} = \text{LeakyReLU}(m_{j \leftarrow i} + \sum_{i\in\mathcal{N}_u} m_{j \leftarrow i}) hj(l)=LeakyReLU(mj←i+i∈Nu∑mj←i)
经过LLL层传播之后，得到地理位置编码的 POI 表示：
Hg=[h1(L);h2(L);⋯ ;h∣V∣(L)]H_g = [h_1^{(L)}; h_2^{(L)}; \cdots; h_{\vert\mathcal{V}\vert}^{(L)}] Hg=[h1(L);h2(L);⋯;h∣V∣(L)]
对于具有签到历史sus_usu的用户uuu，论文假设他/她的地理偏好可以通过聚合他/她的签到历史中 POIs 的高级地理邻居来捕获。
Sequential Graph Propagation Layer
另一方面，用户访问序列不仅包含了用户对 POI 的偏好，还包含了用户的兴趣的演变历史，这暗示了用户对下一个 POI 访问的倾向。根据顺序关系图Gs,u\mathcal{G}_{s,u}Gs,u，论文使用Gated Graph Neural Networks (GGNNs)进行聚合：
hv(1)=[xi⊤,0]⊤avt=Av⊤[h1(t−1)⊤,⋯ ,h∣V∣(t−1)⊤]⊤+bzvt=σ(Wzav(t)+Uzhv(t−1))rvt=σ(Wrav(t)+Urhv(t−1))hv(t)~=tanh(Woav(t)+Uo(rvt⊙hv(t−1)))hv(t)=(1−zvt)⊙hv(t−1)+zvt⊙hv(t)~\begin{aligned} h_v^{(1)} &= [x_i^\top, 0]^\top \\ a_v^t &= A_v^\top [h_1^{(t-1)\top}, \cdots, h_{\vert\mathcal{V}\vert}^{(t-1)\top}]^\top + b \\ z_v^t &= \sigma(W^z a_v^{(t)} + U^z h_v^{(t-1)}) \\ r_v^t &= \sigma(W^r a_v^{(t)} + U^r h_v^{(t-1)}) \\ \widetilde{h_v^{(t)}} &= \tanh(W_o a_v^{(t)} + U_o(r_v^t \odot h_v^{(t-1)})) \\ h_v^{(t)} &= (1 - z_v^t) \odot h_v^{(t-1)} + z_v^t \odot \widetilde{h_v^{(t)}} \end{aligned} hv(1)avtzvtrvthv(t)hv(t)=[xi⊤,0]⊤=Av⊤[h1(t−1)⊤,⋯,h∣V∣(t−1)⊤]⊤+b=σ(Wzav(t)+Uzhv(t−1))=σ(Wrav(t)+Urhv(t−1))=tanh(Woav(t)+Uo(rvt⊙hv(t−1)))=(1−zvt)⊙hv(t−1)+zvt⊙hv(t)
简单去了解了一下 GGNN，主要特点在于使用 GRU 单元，并且将循环展开层数固定为TTT，上面的公式中，zvtz_v^tzvt和rvtr_v^trvt可以理解为 update gate 和 reset gate。
最后得到顺序关系编码的 POI 表示：
Hs,u=[hu,1(t),hu,2(t),⋯ ,hu,∣su∣(t)]H_{s,u} = [h_{u,1}^{(t)}, h_{u,2}^{(t)}, \cdots, h_{u, \vert s_u\vert}^{(t)}] Hs,u=[hu,1(t),hu,2(t),⋯,hu,∣su∣(t)]
Soft-attention Mechanism
在对用户访问序列中构建的两个图进行编码后，论文引入了一种软注意机制，根据当前目标 POI vtv_tvt更好地聚合编码。对于地理图表示Hg,u=[h1,h2,⋯ ,h∣su∣]H_{g,u} = [h_1, h_2, \cdots, h_{\vert s_u\vert}]Hg,u=[h1,h2,⋯,h∣su∣]，使用vtv_tvt对应的隐藏层表示hth_tht作为 query：
wi=αg⊤σ(Qght+Kghi)eg,u=∑i=1∣su∣wihi\begin{aligned} w_i &= \alpha_g^\top \sigma(Q_gh_t + K_gh_i) \\ e_{g,u} &= \sum_{i=1}^{\vert s_u \vert} w_ih_i \end{aligned} wieg,u=αg⊤σ(Qght+Kghi)=i=1∑∣su∣wihi
其中α\alphaα表示 sigmoid 函数，Qg,Kg∈RD×DQ_g,K_g\in\mathbb{R}^{D\times D}Qg,Kg∈RD×D分别为 query 和 key。类似地，对于Hs,u=[h1′,h2′,⋯ ,h∣su∣′]H_{s,u} = [h'_1, h'_2, \cdots, h'_{\vert s_u\vert}]Hs,u=[h1′,h2′,⋯,h∣su∣′]，使用vtv_tvt对应的初始化 Embedding 表示xtx_txt作为 query：
wi′=αs⊤σ(Qsxt+Kshi′)es,u=∑i=1∣su∣wi′hi′\begin{aligned} w'_i &= \alpha_s^\top \sigma(Q_sx_t + K_sh'_i) \\ e_{s,u} &= \sum_{i=1}^{\vert s_u \vert} w'_ih'_i \end{aligned} wi′es,u=αs⊤σ(Qsxt+Kshi′)=i=1∑∣su∣wi′hi′
Self-supervised Disentanglement
由于序列效应和地理效应对相邻访问的 POI 有不同的影响，因此必须将eg,ue_{g,u}eg,u和es,ue_{s,u}es,u这两种表示相互分离。具体来说，论文使用两个 readout 函数处理图传播层的输出。论文选择均值池作为 readout 函数，分别得到带有地理位置偏好的pg,up_{g,u}pg,u和带有用户历史兴趣偏好的ps,up_{s,u}ps,u。
pg,u=READOUT({xj∣vj∈Nsu})=1∑vi∈su∣Ni∣∑vi∈su∑vj∈Nixjps,u=READOUT({xi∣vi∈su})=1∣su∣∑vi∈suxi\begin{aligned} p_{g,u} &= \text{READOUT}(\{ x_j \vert v_j \in \mathcal{N}_{s_u} \}) = \frac{1}{\sum_{v_i\in s_u}\vert\mathcal{N}_i\vert} \sum_{v_i\in s_u} \sum_{v_j \in \mathcal{N}_i} x_j \\ p_{s,u} &= \text{READOUT}(\{ x_i \vert v_i \in s_u \}) = \frac{1}{\vert s_u \vert} \sum_{v_i \in s_u} x_i \end{aligned} pg,ups,u=READOUT({xj∣vj∈Nsu})=∑vi∈su∣Ni∣1vi∈su∑vj∈Ni∑xj=READOUT({xi∣vi∈su})=∣su∣1vi∈su∑xi
接着为每个解构表示设计投影头，映射到另一个空间，获得不同方面的信息：
eg,u′=projg(eg,u),pg,u′=projg(pg,u)es,u′=projs(es,u),ps,u′=projg(ps,u)\begin{aligned} e'_{g,u} &= \text{proj}_g(e_{g,u}), p'_{g,u} = \text{proj}_g(p_{g,u}) \\ e'_{s,u} &= \text{proj}_s(e_{s,u}), p'_{s,u} = \text{proj}_g(p_{s,u}) \end{aligned} eg,u′es,u′=projg(eg,u),pg,u′=projg(pg,u)=projs(es,u),ps,u′=projg(ps,u)
其中projg,projs:RD→RD\text{proj}_g,\text{proj}_s: \mathbb{R}^D \rightarrow \mathbb{R}^Dprojg,projs:RD→RD为线性变换。
接着论文引入了如下对比损失：
Lcon=f(eg,u′,pg,u′,ps,u′)+f(es,u′,ps,u′,pg,u′)\mathcal{L}_{con} = f(e'_{g,u},p'_{g,u},p'_{s,u}) + f(e'_{s,u},p'_{s,u},p'_{g,u}) Lcon=f(eg,u′,pg,u′,ps,u′)+f(es,u′,ps,u′,pg,u′)
其中f(⋅)f(\cdot)f(⋅)表示贝叶斯个性化排序损失（Bayesian Personalized Ranking, BPR）：
f(a,p,q)=Softplus(⟨a,q⟩−⟨a,p⟩)f(a,p,q) = \text{Softplus}(\langle a,q \rangle - \langle a,p \rangle) f(a,p,q)=Softplus(⟨a,q⟩−⟨a,p⟩)
BPR Loss 的主要思想就是让正样本和负样本的得分之差尽可能达到最大。
Location-based CTR Prediction Layer
在获得用户历史访问的解构表示eg,u,es,ue_{g,u},e_{s,u}eg,u,es,u后，将其与 embedding xtx_txt和地理位置表示hth_tht拼接并送入 MLP，得到预测结果：
y^=σ(MLP(CONTAT(eg,u,es,u,xt,ht)))\hat{y} = \sigma(\text{MLP}(\text{CONTAT}(e_{g,u},e_{s,u},x_t,h_t))) y^=σ(MLP(CONTAT(eg,u,es,u,xt,ht)))
仔细看了一下代码，才反应过来，预测结果并不是去每个 POI 的概率，而是去 target POI 的概率，感觉好奇怪，这一下子也变得太简单了吧？真实场景是不可能知道 next POI 的吧。
使用交叉熵损失函数计算损失预测损失：
Lrec=−∑(u,v)ylogy^+(1−y)log(1−y^)\mathcal{L}_rec = - \sum_{(u,v)} y\log\hat{y} + (1-y)\log(1-\hat{y}) Lrec=−(u,v)∑ylogy^+(1−y)log(1−y^)
最终的损失函数为：
L=Lrec+β∗Lcon\mathcal{L} = \mathcal{L}_rec + \beta*\mathcal{L}_{con} L=Lrec+β∗Lcon
为了优化模型，论文提出了一种课程学习方法，使训练过程遵循一个简单到难的过程。具体来说，使用动态增长对比损失权重作为 warm-up 来训练模型：
β=max{α,γ∗k}\beta = \max\{ \alpha, \gamma * k \} β=max{α,γ∗k}
其中α\alphaα和γ\gammaγ均为超参数，kkk表示当前课程数量。
实验
RQ1：与目前最好的基于位置的 CTR 预测相比，DisenPOI 的表现如何？DisenPOI 如何使用解构信息来缓解数据稀疏性问题？
RQ2：解构地理和顺序影响是影响模型性能的关键吗？不同的超参数的影响是什么？
RQ3：DisenPOI 如何有效地解构 POI 信息？DisenPOI 是否如预期对 POI 信息进行了解构？
CTR：click-through rate
Dataset
Result
不知道为什么，对比实验的模型大多都不是专门 POI 的推荐模型，而且评价指标也没有 Recall 之类的。
Performance on Cold-start Recommendation
为了研究顺序和地理影响是否有助于缓解冷启动问题，论文随机将每个用户的访问序列划分为 5 份，对应 20%、40%、60%、80%、全列组。实验结果如下图所示：
Effectiveness of Dual Graphs
两张图的消融实验，以及探究距离阈值Δd\Delta dΔd的影响
Difference Between Graph Propagation Methods
聚合方式的消融实验，以及 GNN 层数关系
Influence of Disentanglement And Curriculum Learning
Visualization and Case Study
总结
论文的主要想法是将顺序关系和地理位置关系进行解构，但实际上来看就是通过两个 GNN 进行单独处理，最后预测的时候拼接进行预测，以及一个辅助的对比损失，感觉并不是很有「解构」的味道？最后实验部分的内容感觉相当完善。