在加权异构图上的基于元路径个性化推荐——SemRec-装备指南-梦幻私服助手

主要参考论文：《Semantic Path based Personalized Recommendation on Weighted Heterogeneous Information Networks》

概述

1）传统的异构图没有考虑连边上属性的值（连边的权重，比如电影评分1~5），所以一般的元路径不能准确地捕获语义信息。如下面这个异构图为例，考虑元路径“User-Movie-User”，如果不考虑Mary和Bob对电影的具体评分，那么会得出二者爱好很相似的结论，因为他们满足“Mary-The Terminator-Bob”这条元路径，但实际上，Mary对该电影只打了1分，并不喜欢这部电影，而Bob打了5分，喜欢这部电影。所以，我们应该考虑连边上具体的属性值。但这同时意味着需要新的相似度计算方式。

2）如何融合来自多条元路径的信息用于推荐。通过不同的元路径会产生不同类型的相似用户（即不同的元路径计算出的用户相似度不同），进而会产生不同的推荐物品。我们需要为每条路径设计一个权重学习方法以整合这些推荐结果。这些权重最好是个性化的，这样不仅能深度发掘用户的特征，还能为推荐提供可解释性。比如某用户对于“User-Interest Group-User”这条路径有很高的权重，那么可以解释推荐结果来自他同一兴趣组的用户，也可以反映出该用户很容易受到兴趣组用户的影响。

但是，为每个用户都学习一个个性化的权重是很难的，因为评分数据稀疏，大量的参数无法很好地学习。

针对上述挑战，1.提出了带权重的异构图和带权重的元路径；2.使用了新的相似度计算策略，从而可以使用现有的基于路径的相似度计算方法，无需设计特殊的计算方法；3.提出了基于语义元路径的个性化推荐方法（the semantic path based personalized recommendation method）SemRec，采用“相似用户的权重偏好一致性原则”设计了一种新颖的权重正则化项，以捕获用户个性化的权重偏好和缓解评分稀疏的问题。

带权重的元路径（weighted meta path，下称带权元路径）

形式化定义如下：

→

(

)

→

(

)

⋅

→

(

)

∣

A_{1}\overset{\delta _{1}\left ( R_{1}\right )}{\rightarrow}A_{2}\overset{\delta _{2}\left ( R_{2}\right )}{\rightarrow}\cdot \cdot \cdot \overset{\delta _{l}\left ( R_{l}\right )}{\rightarrow}A_{l+1}|C

A1→δ1(R1)A2→δ2(R2)⋅⋅⋅→δl(Rl)Al+1∣C

也可表示为：

(

)

(

)

⋅

(

)

∣

A_{1}\left ( \delta _{1}\left ( R_{1}\right )\right )A_{2}\left ( \delta _{2}\left ( R_{2}\right )\right )\cdot \cdot \cdot \left ( \delta _{l}\left ( R_{l}\right )\right )A_{l+1}|C

A1(δ1(R1))A2(δ2(R2))⋅⋅⋅(δl(Rl))Al+1∣C

其中，

→

(

)

A_{i}\overset{\delta _{i}\left ( R_{i}\right )}{\rightarrow}A_{i+1}

Ai→δi(Ri)Ai+1表示基于属性值

(

)

\delta _{i}\left ( R_{i}\right )

δi(Ri)的

A_{i}

Ai与

A_{i+1}

Ai+1间的关系；

C表示约束。

举例，带权元路径

→

U\overset{1}{\rightarrow}M

U→1M即

(

)

U\left ( 1\right )M

U(1)M，表示用户对电影评分为1；

→

U\overset{1,2}{\rightarrow}M\overset{1,2}{\rightarrow}U

U→1,2M→1,2U即

(

)

(

)

U\left ( 1,2\right )M\left ( 1,2\right )U

U(1,2)M(1,2)U，表示一个用户和另一个用户一样不喜欢这部电影（而无权元路径只能反映出两个用户有共同的观看记录）；

→

∣

U\overset{i}{\rightarrow}M\overset{j}{\rightarrow}U|i=j

U→iM→jU∣i=j表示两个用户对电影有相同的评分。

带权元路径的相似度计算方法

原子元路径（atomic meta path）

举例来说，

(

)

(

)

U\left ( 1\right )M\left ( 1\right )U

U(1)M(1)U、

(

)

(

)

U\left ( 1\right )M\left ( 2\right )U

U(1)M(2)U等都是原子元路径；

(

)

(

)

∣

U\left ( i\right )M\left ( j\right )U|i=j

U(i)M(j)U∣i=j包含了5个原子元路径（即

(

)

(

)

U\left ( 1\right )M\left ( 1\right )U

U(1)M(1)U到

(

)

(

)

U\left ( 5\right )M\left ( 5\right )U

U(5)M(5)U）。

1）首先是将带权元路径按照具体的权值分解为多个原子元路径（atomic meta path），用现有的基于元路径的相似度计算方法，计算出每条原子元路径上的相似度；2）然后将该带权元路径的所有原子元路径的相似度求和。

如下图所示，有3个用户对2部电影进行了评分，以PathSim（即数两个节点有多少条某类型元路径）为例，计算用户间的相似度。图的上半部分是使用传统的元路径，其没有考虑具体的评分（权重），用“UMU”路径得到的用户间的相似度是一样的；图的下半部分是先计算各原子元路径上用户的相似度，然后再求和，最后得到

u_1

u1和

u_3

u3的偏好是一致的，由此可见这种计算方法更能准确捕获用户间的相似度。

SemRec

基本思想是，使用带权或不带权元路径计算用户间的相似度，然后根据相似用户的评分预测目标用户对物品的评分。

不同的元路径会得到不同的推荐结果（评分），如何有效地整合这些推荐结果是一个挑战。我们需要为每条元路径分配一个偏好权重（preference weight）。在学习这些权重时有两个方面的困难：（1）优先级权重（Prioritized weights）不同元路径得到的相似度可能存在很大的偏差（bias），所以很难反映出路径的重要程度。比如，由基于稠密的关系构成的元路径得到的相似度可能普遍偏高，而由基于稀疏的关系构成的元路径得到的相似度可能普遍偏低。为此，SemRec设计了一个归一化评分强度运算（normalized rating intensity operation）消除相似度偏差，使偏好权重更好地反映元路径的重要性。

（2）个性化权重（Personalized weights）即为每个用户学习权重。但存在数据稀疏性问题。为此，SemRec提出“相似用户的权重偏好一致性原则”，即假设两个相似的用户对元路径有相同的权重。两个用户基于一条路径是相似的，表明这条路径对这两个用户有相似的影响，也就是说这些用户对这条路径有一致的偏好。根据这个理论，设计了一个新颖的权重正则化项，有效缓解了权重学习过程中评分稀疏问题。

作者首先设计了基于一条元路径的推荐方法，然后提出三个级别的基于多条元路径的推荐方法：1.所有用户对元路径采用同一权重；2.每个用户对元路径都有个性化的权重；3.带有权重正则化项的个性化权重。

基于单条元路径推荐

设

∈

∣

R\in \mathbf{R}^{\left | U\right |\times \left | I\right |}

R∈R∣U∣×∣I∣为评分矩阵，其元素

R_{u,i}

Ru,i表示用户

u对物品

i的评分；

∈

∣

S\in \mathbf{R}^{\left | U\right |\times \left | U\right |}

S∈R∣U∣×∣U∣表示用户相似度矩阵，元素

(

)

S_{u,v}^{\left ( l\right )}

Su,v(l)表示元路径

l下，用户

u和

v的相似度；

另外定义一个评分强度：

∈

∣

Q\in \mathbf{R}^{\left | U\right |\times \left | I\right |\times N}

Q∈R∣U∣×∣I∣×N，元素

(

)

Q_{u,i,r}^{\left ( l\right )}

Qu,i,r(l)表示在元路径

l下，用户

u以分数

r评分物品

i的强度，其由两方面决定：1）以分数

r评分物品

i的用户数；2）用户相似度。具体计算公式如下：

(

)

∑

(

)

Q_{u,i,r}^{\left ( l\right )}=\sum_{v}^{}S_{u,v}^{\left ( l\right )}\times E_{v,i,r}

Qu,i,r(l)=∑vSu,v(l)×Ev,i,r

{

E_{v,i,r}=\begin{cases} 1& \text{if} \ R_{v,i}=r \\ 0& \text{} \ others \end{cases}

Ev,i,r={10if Rv,i=r others

最后对分数用归一化评分强度加权求和，得到最终用户

u对物品

i的评分：

(

)

∑

(

)

∑

(

)

∑

(

)

∑

(

)

\hat{R}_{u,i}^{\left ( l\right )}=\sum_{r=1}^{N}r\times \frac{Q_{u,i,r}^{\left ( l\right )}}{\sum_{k=1}^{N}Q_{u,i,k}^{\left ( l\right )}}=\sum_{r=1}^{N}r\times \frac{\sum_{v}^{}S_{u,v}^{\left ( l\right )}\times E_{v,i,r}}{\sum_{k=1}^{N}\sum_{v}^{}S_{u,v}^{\left ( l\right )}\times E_{v,i,k}}

R^u,i(l)=∑r=1Nr×∑k=1NQu,i,k(l)Qu,i,r(l)=∑r=1Nr×∑k=1N∑vSu,v(l)×Ev,i,k∑vSu,v(l)×Ev,i,r

由于归一化评分强度的存在，消除了不同元路径间存在的相似度偏差（scale差异）。

基于多条元路径的推荐

1.所有用户对元路径采用同一权重

所有用户都有相同的元路径权重向量

∈

∣

\mathbf{w}\in \mathbf{R}^{1\times \left | P\right |}

w∈R1×∣P∣，

(

)

\mathbf{w}^{\left ( l\right )}

w(l)表示元路径

P_l

Pl的权重。最终的预测分数为每条元路径的加权和：

∑

∣

(

)

(

)

\hat{R}_{u,i}=\sum_{l=1}^{\left | P\right |}\mathbf{w}^{\left ( l\right )}\times \hat{R}_{u,i}^{\left ( l\right )}

R^u,i=∑l=1∣P∣w(l)×R^u,i(l)，对应的损失函数为：

min

⁡

(

)

∥

⊙

(

−

∑

∣

(

)

(

)

∥

⩾

\min_{\mathbf{w}}L_{1}\left ( \mathbf{w}\right )=\frac{1}{2}\left \| Y\odot \left ( R-\sum_{l=1}^{\left | P\right |}\mathbf{w}^{\left ( l\right )}\times \hat{R}_{u,i}^{\left ( l\right )}\right )\right \|_{2}^{2}+\frac{\lambda _{0}}{2}\left \| \mathbf{w}\right \|_{2}^{2}\\s.t. \ \mathbf{w}\geqslant 0

minwL1(w)=21∥∥∥Y⊙(R−∑l=1∣P∣w(l)×R^u,i(l))∥∥∥22+2λ0∥w∥22s.t. w⩾0

其中，

Y为指示矩阵，当用户

u评分过物品

i时，元素

Y_{u,i}=1

Yu,i=1；否则为0

2.每个用户对元路径都有个性化的权重

此时，元路径权重变为了一个矩阵

∈

∣

W\in \mathbf{R}^{\left | U\right |\times \left | P\right |}

W∈R∣U∣×∣P∣，元素

(

)

W_{u}^{\left ( l\right )}

Wu(l)表示用户

u对路径

P_l

Pl的权重，列向量

(

)

∈

∣

W^{\left ( l\right )}\in \mathbf{R}^{\left | U\right |\times 1}

W(l)∈R∣U∣×1表示所有用户对路径

P_l

Pl的权重。所以预测分数为：

∑

∣

(

)

(

)

\hat{R}_{u,i}=\sum_{l=1}^{\left | P\right |}W_{u}^{\left ( l\right )}\times \hat{R}_{u,i}^{\left ( l\right )}

R^u,i=∑l=1∣P∣Wu(l)×R^u,i(l) 损失函数为：

min

⁡

(

)

∥

⊙

(

−

∑

∣

(

)

(

)

∥

⩾

\min_{\mathbf{W}}L_{2}\left ( \mathbf{W}\right )=\frac{1}{2}\left \| Y\odot \left ( R-\sum_{l=1}^{\left | P\right |}diag\left ( W^{\left ( l\right )}\right )\hat{R}^{\left ( l\right )}\right )\right \|_{2}^{2}+\frac{\lambda _{0}}{2}\left \| W\right \|_{2}^{2} \\ s.t. \ W\geqslant 0

minWL2(W)=21∥∥∥Y⊙(R−∑l=1∣P∣diag(W(l))R^(l))∥∥∥22+2λ0∥W∥22s.t. W⩾0

3.带有权重正则化项的个性化权重

如果对每个用户都学习个性化的元路径权重，需要学习

∣

\left | U\right |\times \left | P\right |

∣U∣×∣P∣个权重参数，在数据稀疏的情况下是很困难的。所以根据“相似用户的权重偏好一致性原则”，设计了一个权重正则化项，强制用户的权重逼近其相似用户权重的（加权）平均值：

∑

∣

∑

∣

(

)

−

∑

∣

(

)

(

)

\sum_{u=1}^{\left | U\right |}\sum_{l=1}^{\left | P\right |}\left ( W_{u}^{\left ( l\right )}-\sum_{v=1}^{\left | U\right |}\bar{S}_{u,v}^{\left ( l\right )}W_{v}^{\left ( l\right )}\right )^{2}

∑u=1∣U∣∑l=1∣P∣(Wu(l)−∑v=1∣U∣Sˉu,v(l)Wv(l))2

其中，

(

)

(

)

∑

(

)

\bar{S}_{u,v}^{\left ( l\right )}=\frac{S_{u,v}^{\left ( l\right )}}{\sum_{v}^{}S_{u,v}^{\left ( l\right )}}

Sˉu,v(l)=∑vSu,v(l)Su,v(l)是元路径

P_l

Pl下归一化的用户相似度。矩阵形式为：

∑

∣

∥

(

)

−

(

)

(

)

∥

\sum_{l=1}^{\left | P\right |}\left \| W^{\left ( l\right )}-\bar{S}^{\left ( l\right )}W^{\left ( l\right )}\right \|_{2}^{2}

∑l=1∣P∣∥∥W(l)−Sˉ(l)W(l)∥∥22

最终的损失函数为：

min

⁡

(

)

∥

⊙

(

−

∑

∣

(

)

(

)

∥

∑

∣

∥

(

)

−

(

)

(

)

∥

⩾

\min_{W}L_{3}\left ( W\right )=\frac{1}{2}\left \| Y\odot \left ( R-\sum_{l=1}^{\left | P\right |}diag\left ( W^{\left ( l\right )}\right )\hat{R}^{\left ( l\right )}\right )\right \|_{2}^{2}+\frac{\lambda _{1}}{2}\sum_{l=1}^{\left | P\right |}\left \| W^{\left ( l\right )}-\bar{S}^{\left ( l\right )}W^{\left ( l\right )}\right \|_{2}^{2}+\frac{\lambda _{0}}{2}\left \| W\right \|_{2}^{2} \\ s.t. \ W\geqslant 0

minWL3(W)=21∥∥∥Y⊙(R−∑l=1∣P∣diag(W(l))R^(l))∥∥∥22+2λ1∑l=1∣P∣∥∥W(l)−Sˉ(l)W(l)∥∥22+2λ0∥W∥22s.t. W⩾0

论文链接

《Semantic Path based Personalized Recommendation on Weighted Heterogeneous Information Networks》