基于位置的社交网络（Location-Based Social Network）快速发展， 用于挖掘用户据被用来挖掘用户的行为模式来实现兴趣点（Point-of-Interest） 推荐。 兴趣点推荐不仅能提高用户体验，增加用户粘性，还能给商家带来潜在的商业利益，已成为推荐系统中最重要的研究方向之一。

2021 年发表在 ICDM 上的一篇论文：DynaPosGNN: Dynamic-Positional GNN for Next POI Recommendation

（next POI recommendation）给定大小为 M M M的用户集合 U = { u 1 , u 2 , ? ? , u M } U=\{u_1, u_2, \cdots,u_M\} U={ u1,u2,?,uM}和大小为 N N N的 POI 集合 V = { v 1 , v 2 , ? ? , v N } V=\{v_1, v_2, \cdots, v_N \} V={ v1​,v2​,⋯,vN​}。

对于每个用户 u m u_m um​都有一个 POI 行动轨迹序列 s u m = { v m 1 , v m 2 , ⋯   , v m i } s_{u_m} = \{v_{m_1}, v_{m_2}, \cdots, v_{m_i} \} sum​​={ vm1​​,vm2​​,⋯,vmi​​}，对应的访问时间序列为 { t 1 , t 2 , ⋯   , t i } \{t_1, t_2, \cdots, t_i \} { t1​,t2​,⋯,ti​}。

当前目标用户 u T u_T uT​，他的行动轨迹为 s u = { v 1 , v 2 , ⋯   , v c } s_u = \{v_1, v_2, \cdots, v_c \} su​={ v1​,v2​,⋯,vc​}，对应的访问时间为 { t 1 , t 2 , ⋯   , t c } \{t_1, t_2, \cdots, t_c \} { t1​,t2​,⋯,tc​}。

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

对于当前目标用户 u T u_T uT​，可知用户 u T u_T uT​在 t c t_c tc​时刻位于地点 v c v_c vc​，我们的任务是预测用户在 t f ( t f > t c ) t_f(t_f > t_c) tf​(tf​>tc​)时刻的下一个访问地点 v f v_f vf​。

一句话概括：节点特征和边特征随着时间而变化的图

一个动态网络可以表示为图 G = ( V , E ) G=(V,E) G=(V,E)，其中集合 V = { ( v , t s , t e ) } V=\{(v,t_s,t_e)\} V={ (v,ts​,te​)}，集合 E = { ( u , v , t s , t e ) } E=\{(u,v,t_s,t_e)\} E={ (u,v,ts​,te​)}，其中 u , v ∈ V u,v\in V u,v∈V为图中的节点， t s , t e t_s,t_e ts​,te​分别表示边出现和消失的时间。

{% note info no-icon %}

注：上面这个定义适用于无向图，并且图中的边没有权重。对于其他网络，可以对该定义进行简单地拓展。

{% endnote %}

在现实世界中更多的数据表示并不是序列或者平面这种简单的排列，而是表现为更为复杂的图结构，如社交网络、人际关系、分子结构等。

Graph Neural Network（GNN）是一种基于图结构的神经网络。

其实传统的神经网络也是可以处理图数据，只需要进行前期合理的 Embedding 即可。GNN 其实是一种特征提取算法，也可以理解为 Embedding 算法，它通过在整张图上传递、聚合信息，从而进行特征提取。

更多关于 GNN 的知识可以看我的另一篇文章：简单理解图神经网络 GNN

模型的主要框架是 GNN，并且构建了两张动态图User-POI Graph和 POI-POI Graph。

Contribute：

1. 考虑用户在特定场合，特定时间的下一个 POI 访问，同时将访问下一个 POI 的时间作为考虑。
2. 使用多重图表示用户访问 POI 的历史记录，将访问时间作为边的权值，构建了 User-POI graph 和 POI-POI graph 用于特征提取。

为了更好地利用用户 POI 的访问信息，论文根据 POI 访问序列构建了两张图： User-POI Graph 和 POI-POI Graph。

• User-POI Graph（UPG）：无向动态多重图。包含所有用户节点和 POI 节点，如果用户 u u u在时间 t t t访问 v v v，那么就会在这两个节点之间添加权值为 t t t的边。 U P G T UPG_T UPGT​表示在时间 T T T之前的 UPG 子图。
• POI-POI Graph（PPG）：有向动态多重图。包含所有 POI 节点，如果用户 u u u之前位于 v a v_a va​，在 t b t_b tb​时刻访问 v b v_b vb​，那么就会在这两个节点之间添加权值为 t b t_b tb​的边。 P P G T PPG_T PPGT​表示在时间 T T T之前的 PPG 子图。

在User-POI Graph和 POI-POI Graph中，记录了所有的信息，论文中提出了 4 个因子，来更好地提取历史记录的特征。

1. Time interval between current and prediction time

   当前时间和预测时间的时间差。

   Δ t c f = t f − t c \Delta t_{cf} = t_f - t_c Δtcf​=tf​−tc​

   由于 Δ t c f \Delta t_{cf} Δtcf​可能非常大，因此处理为 1 / exp ⁡ ( Δ t c f ) 1/\exp(\Delta t_{cf}) 1/exp(Δtcf​)。

2. Time interval between current and past record

   当前时间和过去记录的时间差。

   Δ t c p k = t c − t p k \Delta t_{cp_k} = t_c - t_{p_k} Δtcpk​​=tc​−tpk​​

   由于 Δ t c p k \Delta t_{cp_k} Δtcpk​​可能非常大，因此处理为 1 / exp ⁡ ( Δ t c p k ) 1/\exp(\Delta t_{cp_k}) 1/exp(Δtcpk​​)。

3. Hour time difference between prediction time and past record

   小时差。由于用户在一天内的活动可能是非常规律的，很可能在相似的时间访问相同的地点。对于两个不同的 Hour time， h f , h p k ∈ [ 0 , 24 ) h_f,h_{p_k}\in [0,24) hf​,hpk​​∈[0,24)，定义：

   d h ( h f , h p k ) = min ⁡ ( ∣ h f − h p k − 24 ∣ , ∣ h f − h p k ∣ , ∣ h f − h p k + 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∣)

4. Geographical distance

   地理距离。

   d h a v ( v c , v p k ) = H a v e r s i n e ( v c , v p k ) d_{hav}(v_c, v_{p_k}) = Haversine(v_c, v_{p_k}) dhav​(vc​,vpk​​)=Haversine(vc​,vpk​​)

   由于 d h a v d_{hav} dhav​可能非常大，因此处理为 1 / exp ⁡ ( d h a v ) 1/\exp(d_{hav}) 1/exp(dhav​)。

   半正矢公式（Haversine）是一种根据两点的经度和纬度来确定大圆上两点之间距离的计算方法。

整体模型架构并不复杂，这里简单进行说明。就像前面说的，你可以把 DynaPosGNN Layer 理解为一个 Embedding 的过程。输入为 { u T , v c , t c , t f } \{u_T, v_c, t_c, t_f\} { uT​,vc​,tc​,tf​}，UPG/PPG，POI Embedding。

首先是利用之前提到的 4 个因子计算当前节点与邻居节点的关系：

w k = f ( Δ t c f , Δ t c k , d h ( t f − t k ) , d h a v ( v c , v k ) ) 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 ( v c , t c , t f ) = MLP ( ∑ i ∈ N c α i Emb i ) \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​∑​αi​Embi​)

其中 α i \alpha_i αi​为：

α k = Softmax ( w k ) = exp ⁡ ( w k ) ∑ i ∈ N c exp ⁡ ( w i ) \alpha_k=\text{Softmax}(w_k) = \frac{\exp(w_k)}{\sum_{i\in \mathcal{N_c}} \exp(w_i)} αk​=Softmax(wk​)=∑i∈Nc​​exp(wi​)exp(wk​)​

在 GNN 聚合时，由于 User-POI Graph 和 POI-POI Graph 存在差异，因此略有不同。具体来说，User-POI Graph 使用全部的边；而 POI-POI Graph 使用出边。

经过 DynaPosGNN Layer 之后，我们得到了 h u p g \mathbf{h_{upg}} hupg​和 h p p g \mathbf{h_{ppg}} hppg​，即 UPG 和 PPG 的向量表示。为了加强时间学习，论文又添加了时间信息，得到最终的 POI 预测结果：

p = Softmax ( W s ( w u p g h u p g + w p p g h p p g ) ) \mathbf{p}=\text{Softmax}\left(\mathbf{W_s}(w_{upg}\mathbf{h_{upg}} + w_{ppg}\mathbf{h_{ppg}})\right) p=Softmax(Ws​(wupg​hupg​+wppg​hppg​))

• 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 个推荐中的排名来衡量推荐的质量。

总体看下来，一些细节的地方没怎么讲，感觉亮点还是在 v c , t c , t f v_c,t_c,t_f vc​,tc​,tf​上。我们一般总是将 POI 访问序列看做一个整体，直观的根据序列预测下一个访问地点。这篇论文感觉就是进一步强调了用户的当前访问点以及当前访问时间 v c , t c v_c,t_c vc​,tc​；同时也将待访问时间 t f t_f tf​纳入考虑，其实也就是不同时间范围的预测。

• [1] DynaPosGNN: Dynamic-Positional GNN for Next POI Recommendation
• [2] The Graph Neural Network Model