【论文阅读】DynaPosGNN:Dynamic-Positional GNN for Next POI Recommendation
【论文阅读】DynaPosGNN:Dynamic-Positional GNN for Next POI Recommendation
【论文阅读】DynaPosGNN: Dynamic-Positional GNN for Next POI Recommendation
Metadata
authors:: Junbeom Kim, Sihyun Jeong, Goeon Park, Kihoon Cha, Ilhyun Suh, Byungkook Oh container:: 2021 International Conference on Data Mining Workshops (ICDMW) year:: 2021 DOI:: 10.1109/ICDMW53433.2021.00012 rating:: ⭐⭐ share:: true comment:: 模型完全采用GNN进行Embedding，同时待预测POI的访问时间也作为参数进行输入，与传统的POI预测问题有些出入。
前言
随着基于位置的社交网络（Location-Based Social Network）的快速发展， 海量的签到数据被用于挖掘用户的行为模式以实现兴趣点（Point-of-Interest） 推荐。 兴趣点推荐不但可以提高用户体验，增加用户粘性，还能为商家带来潜在的商业利益，已成为推荐系统中最重要的研究方向之一。
2021 年发表在 ICDM 上的一篇论文：DynaPosGNN: Dynamic-Positional GNN for Next POI Recommendation
问题描述
（next POI recommendation）给定大小为MMM的用户集合U={u1,u2,⋯ ,uM}U=\{u_1, u_2, \cdots,u_M\}U={u1,u2,⋯,uM}和大小为NNN的 POI 集合V={v1,v2,⋯ ,vN}V=\{v_1, v_2, \cdots, v_N \}V={v1,v2,⋯,vN}。
对于每个用户umu_mum都有一个 POI 行动轨迹序列sum={vm1,vm2,⋯ ,vmi}s_{u_m} = \{v_{m_1}, v_{m_2}, \cdots, v_{m_i} \}sum={vm1,vm2,⋯,vmi}，对应的访问时间序列为{t1,t2,⋯ ,ti}\{t_1, t_2, \cdots, t_i \}{t1,t2,⋯,ti}。
当前目标用户uTu_TuT，他的行动轨迹为su={v1,v2,⋯ ,vc}s_u = \{v_1, v_2, \cdots, v_c \}su={v1,v2,⋯,vc}，对应的访问时间为{t1,t2,⋯ ,tc}\{t_1, t_2, \cdots, t_c \}{t1,t2,⋯,tc}。
一般的，我们的任务是预测用户的下一个访问地点，即_next POI(Point-of-Interest) recommendation_。
对于当前目标用户uTu_TuT，可知用户uTu_TuT在tct_ctc时刻位于地点vcv_cvc，我们的任务是预测用户在tf(tf>tc)t_f(t_f > t_c)tf(tf>tc)时刻的下一个访问地点vfv_fvf。
预备知识
动态图
一句话概括：节点特征和边特征随着时间而变化的图
一个动态网络可以表示为图G=(V,E)G=(V,E)G=(V,E)，其中集合V={(v,ts,te)}V=\{(v,t_s,t_e)\}V={(v,ts,te)}，集合E={(u,v,ts,te)}E=\{(u,v,t_s,t_e)\}E={(u,v,ts,te)}，其中u,v∈Vu,v\in Vu,v∈V为图中的节点，ts,tet_s,t_ets,te分别表示边出现和消失的时间。
注：上面这个定义适用于无向图，并且图中的边没有权重。对于其他网络，可以对该定义进行简单地拓展。
GNN
在现实世界中更多的数据表示并不是序列或者平面这种简单的排列，而是表现为更为复杂的图结构，如社交网络、人际关系、分子结构等。
Graph Neural Network（GNN）是一种基于图结构的神经网络。
其实传统的神经网络也是可以处理图数据，只需要进行前期合理的 Embedding 即可。GNN 其实是一种特征提取算法，也可以理解为 Embedding 算法，它通过在整张图上传递、聚合信息，从而进行特征提取。
更多关于 GNN 的知识可以看我的另一篇文章：简单理解图神经网络 GNN
Overview
模型的主要框架是 GNN，并且构建了两张动态图_User-POI Graph_和 POI-POI Graph。
Contribute：
- 考虑用户在特定场合，特定时间的下一个 POI 访问，同时将访问下一个 POI 的时间作为考虑。
- 使用多重图表示用户访问 POI 的历史记录，将访问时间作为边的权值，构建了 User-POI graph 和 POI-POI graph 用于特征提取。
DynaPosGNN
Dynamic Graphs
为了更好地利用用户 POI 的访问信息，论文根据 POI 访问序列构建了两张图： User-POI Graph 和 POI-POI Graph。
- User-POI Graph（UPG）：无向动态多重图。包含所有用户节点和 POI 节点，如果用户uuu在时间ttt访问vvv，那么就会在这两个节点之间添加权值为ttt的边。UPGTUPG_TUPGT表示在时间TTT之前的 UPG 子图。
- POI-POI Graph（PPG）：有向动态多重图。包含所有 POI 节点，如果用户uuu之前位于vav_ava，在tbt_btb时刻访问vbv_bvb，那么就会在这两个节点之间添加权值为tbt_btb的边。PPGTPPG_TPPGT表示在时间TTT之前的 PPG 子图。
Factors
在_User-POI Graph_和 _POI-POI Graph_中，记录了所有的信息，论文中提出了 4 个因子，来更好地提取历史记录的特征。
- Time interval between current and prediction time 当前时间和预测时间的时间差。 Δtcf=tf−tc\Delta t_{cf} = t_f - t_cΔtcf=tf−tc 由于Δtcf\Delta t_{cf}Δtcf可能非常大，因此处理为1/exp(Δtcf)1/\exp(\Delta t_{cf})1/exp(Δtcf)。
- Time interval between current and past record 当前时间和过去记录的时间差。 Δtcpk=tc−tpk\Delta t_{cp_k} = t_c - t_{p_k}Δtcpk=tc−tpk 由于Δtcpk\Delta t_{cp_k}Δtcpk可能非常大，因此处理为1/exp(Δtcpk)1/\exp(\Delta t_{cp_k})1/exp(Δtcpk)。
- Hour time difference between prediction time and past record 小时差。由于用户在一天内的活动可能是非常规律的，很可能在相似的时间访问相同的地点。对于两个不同的 Hour time，hf,hpk∈[0,24)h_f,h_{p_k}\in [0,24)hf,hpk∈[0,24)，定义： dh(hf,hpk)=min(∣hf−hpk−24∣,∣hf−hpk∣,∣hf−hpk+24∣)d_h(h_f, h_{p_k}) = \min(\vert h_f - h_{p_k} - 24 \vert, \vert h_f - h_{p_k} \vert, \vert h_f - h_{p_k} + 24 \vert)dh(hf,hpk)=min(∣hf−hpk−24∣,∣hf−hpk∣,∣hf−hpk+24∣)
- Geographical distance 地理距离。 dhav(vc,vpk)=Haversine(vc,vpk)d_{hav}(v_c, v_{p_k}) = Haversine(v_c, v_{p_k})dhav(vc,vpk)=Haversine(vc,vpk) 由于dhavd_{hav}dhav可能非常大，因此处理为1/exp(dhav)1/\exp(d_{hav})1/exp(dhav)。 半正矢公式（Haversine）是一种根据两点的_经度_和_纬度_来确定_大圆上两点之间距离_的计算方法。
Architecture
DynaPosGNN Layer
整体模型架构并不复杂，这里简单进行说明。就像前面说的，你可以把 DynaPosGNN Layer 理解为一个 Embedding 的过程。输入为{uT,vc,tc,tf}\{u_T, v_c, t_c, t_f\}{uT,vc,tc,tf}，UPG/PPG，POI Embedding。
首先是利用之前提到的 4 个因子计算当前节点与邻居节点的关系：
wk=f(Δtcf,Δtck,dh(tf−tk),dhav(vc,vk))w_k = f(\Delta t_{cf}, \Delta t_{ck}, d_h(t_f-t_k), d_{hav}(v_c,v_k))wk=f(Δtcf,Δtck,dh(tf−tk),dhav(vc,vk))
使用多层感知机 Multi-Layered Perceptron(MLP)进行训练：
Embedding(vc,tc,tf)=MLP(∑i∈NcαiEmbi)\text{Embedding}(v_c,t_c,t_f)=\text{MLP}(\sum_{i\in \mathcal{N_c}} \alpha_i \text{Emb}_i)Embedding(vc,tc,tf)=MLP(∑i∈NcαiEmbi)
其中αi\alpha_iαi为：
αk=Softmax(wk)=exp(wk)∑i∈Ncexp(wi)\alpha_k=\text{Softmax}(w_k) = \frac{\exp(w_k)}{\sum_{i\in \mathcal{N_c}} \exp(w_i)}αk=Softmax(wk)=∑i∈Ncexp(wi)exp(wk)
GNN Aggregate
在 GNN 聚合时，由于 User-POI Graph 和 POI-POI Graph 存在差异，因此略有不同。具体来说，User-POI Graph 使用全部的边；而 POI-POI Graph 使用出边。
Output
经过 DynaPosGNN Layer 之后，我们得到了hupg\mathbf{h_{upg}}hupg和hppg\mathbf{h_{ppg}}hppg，即 UPG 和 PPG 的向量表示。为了加强时间学习，论文又添加了时间信息，得到最终的 POI 预测结果：
p=Softmax(Ws(wupghupg+wppghppg))\mathbf{p}=\text{Softmax}\left(\mathbf{W_s}(w_{upg}\mathbf{h_{upg}} + w_{ppg}\mathbf{h_{ppg}})\right)p=Softmax(Ws(wupghupg+wppghppg))
EXPERIMENT
数据集
- Foursquare：New York City (FS-NYC), Tokyo (FS-TKY)
- Gowalla： San Francisco (GW-SF), Austin (GW-AUS)
评价指标
HR@K: 目标 POI 是否在前 k 个推荐列表中
NDCG@K: 根据目标 POI 在前 k 个推荐中的排名来衡量推荐的质量。
对比实验
消融实验
总结
总体看下来，一些细节的地方没怎么讲，感觉亮点还是在vc,tc,tfv_c,t_c,t_fvc,tc,tf上。我们一般总是将 POI 访问序列看做一个整体，直观的根据序列预测下一个访问地点。这篇论文感觉就是进一步强调了用户的当前访问点以及当前访问时间vc,tcv_c,t_cvc,tc；同时也将待访问时间tft_ftf纳入考虑，其实也就是不同时间范围的预测。