一种结合聚集图嵌入的社会化推荐算法

周林娥，游进国

(昆明理工大学 信息工程与自动化学院,昆明 650500)

1 引 言

随着互联网的快速发展，大规模数据的出现，使得用户需花费太多的时间和精力去选择自己需要的信息.基于此，推荐系统作为一种“信息推送”的重要方法进入人们的视野并广泛应用于各种电商及音乐平台.然而，用户的需求是不断变化的且推荐的准确率仍需提升，信息过载问题依然存在.首先，在传统推荐系统中，大多数用户通常只是消费很少的项目且一些用户可能不愿意对消费的商品评价，使得数据稀疏问题更加的突出，其次，由于受利益的驱使，买家可能会对商品进行不真实的打分，比如购买商品时卖家可能会用一些红包来获得买家的好评等等.因此，我们需要借助其他信息为用户提供更加准确的推荐，由于社交网络的发展和各种社交平台的出现，可以利用观察到的社交信息来缓解传统推荐系统的数据稀疏问题，许多基本方法[1,2]融合了社交关系提高了推荐的准确性，显示了社交信息纳入推荐系统非常重要.为了提高推荐表现最近的工作[3,4]把直接观察到的社交信息融入到矩阵分解(MF)和贝叶斯个性化排名(BPR)框架中.目前基于社交网络的推荐仍然存在一些问题：由于垃圾邮件的存在及社交关系的复杂性，使得社交关系带有噪音，现实世界中显式的社会关系非常稀疏.另外，社交网络过大需占据巨大的存储空间.因而，直接使用原图推荐存在一定的局限性.

近来，网络表示学习的出现使得推荐有了进一步的发展，一种利用网络表示学习进行个性化商品推荐的方法PGE[5]，通过分别获取商品和用户的低维向量表示并计算他们的相似度主要解决时间因素对用户购物偏好的影响.另外还有一些方法，使用带有重启模型的广义随机游走来建模用户，并基于贝叶斯个性化排名的学习方法了解网络中链接的权重从而进行推荐.尽管基于网络表示学习的方法已经有一定的改善，但直接使用其来进行推荐存在两个不足.首先，计算复杂度高并且占据太大的存储空间.另外，在网络上的一些链接可能不能传递有意义的语义信息，直接使用表示学习方法进行推荐表现欠佳.其次，这些方法涉及数据矩阵的特征分解这对于大型的现实世界网络而言效率不高.

考虑到网络嵌入方法本身也能抵抗稀疏和嘈杂的数据.具体而言，我们可以考虑节点本身及周围节点之间的特性(即邻近性)；另外，可以基于网络中节点的结构特性(即结构等效性)[6,7].因此，必须允许节点表示遵循两条原则：学习嵌入节点的表示保证来自同一网络的紧密联系即邻近性，以及学习表示相似角色的节点具有相似嵌入的表示即同构性.但大多数存在的网络嵌入方法只侧重于网络的一部分信息且未考虑存储及可拓展性问题，考虑如何把这些信息更合理有效的整合和利用到推荐系统中.因此，本文提出了一种基于聚集图表示学习的推荐方法SGE-BPR(Summarized Graph Embedding Bayesian Personalized Ranking).考虑网络本身所反映的特征和丰富的语义信息，该方法首先考虑结构一致性利用图聚集算法提取聚集图数据，更好的保存原图信息的同时把相似性高的节点聚合到一起，随后使用随机游走策略生成有偏差的节点序列.通过网络嵌入计算相似性并捕获用户偏好信息且融合到贝叶斯个性化排序模型，方法一定程度上减轻了数据稀疏性并缓解了噪音问题，有效弥补了直接使用原图进行推荐的不足.

本文的主要贡献如下：

1)首先，利用图聚集技术把结构相似的节点聚合到一起提取聚集图数据，然后进行有偏的随机游走.并从图聚集和图嵌入、社会化推荐及基于表示学习的推荐等方面进行展开和分析.

2)利用skip-gram学习向量的表示并计算用户的相似性，结合贝叶斯个性化排序模型提出一个新颖的图嵌入推荐模型SGE-BPR来提高推荐性能.

3)使用四个真实世界的数据进行实验，验证方法的有效性.

2 相关工作

本文回顾相关工作的研究，并从图聚集、图嵌入和社会化推荐及基于表示学习的推荐进行讨论.

2.1 图聚集和图嵌入

随着数据量的增大，图挖掘逐渐成为热门的研究领域，当前对图聚集的研究工作主要有：文献[8]引入信息增益考虑分组间和分组内的结构对集聚图的影响并提出了两种聚集图构建算法，要寻找高质量的聚集图需要计算重构误差使得原图的邻接矩阵与聚集图的期望邻接矩阵尽可能的相似，从而来衡量原图与聚集图之间的误差.文献[9]提出了图结构查询并采用最小描述长度(MDL)表示图压缩问题，该方法保证了查询的准确性.文献[10]通过研究通常的聚集类型，提出利用多项式时间近似算法来计算给定大小的最可能的聚集方式并生成使重构误差最小的聚集图.

最初提出网络表示学习是为了学习低维潜在因子来保留大多数网络结构.然而，这些方法计算复杂、效率低而不适用于当前的大型信息网络.文献[11]总结了近来出现的网络表示学习方法并验证了这些方法，并对大规模复杂网络表示学习进行了展望.随着skip-gram[12]算法的出现其显示了在建模句子方面的优势.受此想法的启发，DeepWalk[13]被用来从网络中学习一个语言模型，使用随机游走从网络中产生节点序列，然后把它放到skip-gram模型中最终输出表示.紧密的节点倾向于有相似的上下文，因此嵌入后具有更相近的节点序列.LINE[14]在图上定义了一阶相似度和二阶相似度，一阶相似度用来保留两个节点之间的直接联系的紧密程度，二阶相似度用来保留两个节点邻居的相似程度.node2vec[15]是另一种随机游走的代表性方法，它拓展了DeepWalk并同时兼顾深度优先和广度优先的搜索优势从而获得更好的表示效果.GraRep[16]模型从矩阵分解的角度考虑了更高阶的上下文信息，捕获了图的全局结构.对于基于节点和边的预测任务以及现有图的深度网络体系结构的有监督的特征学习的最新成果[17-19].这些方法直接最小化了损失函数使用多层非线性的下游预测任务转换可产生高精度，但训练时间长，可扩展性差.

2.2 社会化推荐

融入社会关系的协同过滤算法称为社会化推荐算法.近年来，国内外学者针对社交关系对推荐的影响展开深入的研究.在早期，研究者们主要考虑显式的社会关系来促进推荐.这些工作如下：文献[20]提出RSTE一种新颖的概率因子分析框架将用户的偏好和他们信任的朋友的兴趣融合在一起.文献[21]提出一种融合用户隐含偏好的推荐算法，用权重矩阵来衡量用户相似度和信任度.文献[3]中提出基于MF的信任，通过考虑隐含邻居的影响获取用户的信任和用户的评级.SBPR[4]算法在BPR模型上融入了社交关系从而得到了更好的推荐效果.文献[22-25]提出BPR及相关的解决项目排名问题的方法.文献[26]基于FM(因子分解机)提出一种通过相似度和信任值来估计社会影响传播并考虑了人群计算来提高推荐的准确性.除上述研究外，Taheri等人[27]提出Hell-Trust SVD方法提取隐含社会关系和评级并结合到活跃用户的项目预测中.

2.3 基于表示学习的推荐

随着表示学习的发展，一些利用表示学习推荐的方法随之出现，在生成顶点上下文时，一种基于网络嵌入的社交推荐方法称为CUNE[25]通过构建用户协作网络识别可信的语义朋友融入MF和BPR框架用于推荐.文献[28]基于社交网络属性，提出一个SAEN模型，对不同用户进行多样性和个性化推荐.文献[29]基于商品间的互补性和用户对商品的忠诚度两个维度提出triple2vec一种新的表示学习，进而提出一种考虑忠诚度的推荐算法来计算购买偏好.文献[30]提出了基于图神经网络的协同过滤算法NGCF，将用户-项目的高阶交互编码进嵌入中来提升表示能力进而提升整个推荐效果.文献[31]提出了一种基于生成对抗训练框架的社会化推荐模型，对模型进行端到端的训练，取得了很好的效果.文献[32]基于超图网络模型构建了一种通过节点特征相似度，不断的迭代和挖掘关系属性的图网络进化算法.文献[33]提出一种SLATEQ的强化学习算法，将长期收益加入排序多目标中进行建模优化，优化了推荐系统中同时展示给用户多个项目情况的长期收益.文献[34]提出一种互补性发现模型通过商品价格和商品购买记录来发掘商品间的互补关系.文献[5]提出一种利用网络表示学习进行个性化商品推荐的方法PGE，该方法构建商品网络并通过表示学习获取低维向量表示且通过历史记录及时序性线性计算出动态的用户偏好从而对相似度进行评估.

上述工作的核心思想是基于社交关系进行推荐.然而，大数据时代，空间效率及可拓展性也是必须考虑的重要因素.考虑现有研究的不足，本文的工作主要是采用基于信息增益的图聚集算法[8](GSum_EG)，获取聚集图数据.然后，借鉴node2vec的思想在聚集图上随机游走后学习学习有效的图结构生成节点向量，随后通过聚集图映射表进行节点向量的还原并寻找相似用户.最后，将信息融合到贝叶斯排序模型进行项目推荐.

3 一种结合聚集图嵌入的社会化推荐算法

3.1 问题定义

为了更好的阐述，本文先对相关概念进行描述并形式化聚集图的表示学习问题，具体如下所示：

定义1.聚集图[8]：一个聚集图S=(Vs,Es,P)是输入图G=(V，E)的压缩表达，其中Vs是V中k是中个组的一个划分，Es是相应的超边的集合，P与每条边相关联，表示两个超点之间或者一个超点自身的连接概率.聚集图S的正式定义如下所示：

ES={(Vi,Vj)|∃u∈Vi,v∈Vj,(u,v)∈E}；

p:ES→R=[0,1].

定义2.聚集图的表示学习[11]：给定聚集图G=(V，E)，其表示学习是：G对应的顶点特征X是一个高度稀疏的矩阵，其维数通常为|V|×m(m(是顶点属性的特征空间大小)，对每个顶点v∈V,低维向量表示学习rv∈Rk,k实质上远小于|V|,rv表示为一个稠密的实数向量表示.

3.2 总体框架

图1为本文提出的总体框架.如图1(a)在社交网络中，顶点表示节点，边表示节点之间的社交关系.图1(b)为图1(a)的聚集图，其中每个顶点代表一个超点，边代表超边，边上的值代表权重，超点1对应的节点集合为{x,d,e},超点2对应的节点集合为{a,b,c},超点3对应的节点集合为{g,f},超点4对应的节点集合为{y,i,j},超点5对应的节点集合为{h}.图1(c)为在聚集图上产生的随机游走节点序列.图1(d)输入为聚集图的节点，当预测节点1时，使用skip-gram嵌入，输出为其他节点出现在中心节点1周围的概率.图1(e)计算节点的表示向量的相似度将其输入到贝叶斯排序模型，最终输出推荐列表.

3.3 聚集图及随机游走

在社交网络中，采用基于信息增益的图聚集算法[8](GSum_EG)保留原图关键的结构关系并去除带有噪音的数据获取聚集图，由于信息熵越小包含的原图信息越多，因此寻找信息增益最大的分组即信息熵最小的分组，依次调整直至所有节点调整完，最终得到聚集图.

考虑到聚集图的邻近性及同构性，即聚集图上距离越近的节点及结构相近的节点相似的可能性更大.相连比较紧密的节点应该有相似的嵌入.在图1中假设(a)为聚集图，超点x和超点y属于同构性节点，超点x和超点d属于邻近性节点，因而采用同时兼顾两种特性的方法进行有偏的随机游走，捕获相似节点.

设f(u)是将顶点u映射为嵌入向量的映射函数,对于图中顶点u的近邻顶点集合.通过以下公式计算近邻顶点出现的概率：

(1)

为使上述问题得到最优化解，进行如下两方面的假设：条件独立性假设：假设给定起始顶点下，其近邻顶点出现的概率与近邻集合中其余顶点无关.用如下公式表示：

(2)

图1 SGE-BPR方法说明Fig.1 Illustration of summarized graph embedding bayesian personalized ranking method

特征空间对称性假设：一个顶点作为起始顶点和作为近邻顶点的时候共用同一嵌入向量.(与LINE[13]中的2阶相似度，一个顶点作为起始点和近邻点的时候是拥有不同的嵌入向量不一样)在这个假设下，上述条件概率公式可表示为:

(3)

由上述假设可得最终的目标函数如下：

(4)

其中Zu代表每个节点的函数，表示为：

(5)

为了减少计算量的同时更好的保留聚集图的原始信息并获得潜在的信息，采用有偏的随机游走获取顶点的近邻序列.受node2vec[14]启发，给定当前顶点v，访问下一个顶点x的概率为:

(6)

其中πvx是顶点v和顶点x之间未归一化的转移概率，z是归一化常数.

引入两个超参数p和q来控制游走的策略，假设当前随机游走经过边(t,v)到达顶点v时,πvx=αpq(t,x).wvx设，其中wvx是顶点v和x之间的权值.

(7)

其中dtx为顶点v到x的最短路径的距离.超参数p和q对游走策略均有影响.其中p决定再访问节点的可能性，为返回参数.若p值调高(p>max(q，1))，这样可以保证在两步内采样已访问过的节点的可能性比较低；若p调低(p1游走会选择离t近的节点，以此达到接近广度优先遍历的效果；q<1游走会选择离t较远的节点，达到类似深度优先遍历的效果.

3.4 聚集图的表示学习

对于每种类型的游走方案，我们可以获得基于聚集图的随机游走步行序列，这是一个旨在学习的skip-gram模型通过预测节点上下文的节点嵌入向量.通常，目标是使上下文出现的概率最大化，在给定的中心节点下Sw0=(w0,w1,….,wM)即：形式上，给定一系列单词，目标函数是：

(8)

其中b是上下文的窗口大小,p(wt′|wt)定义为Softmax函数.同样，我们最大化每个节点共现的概率随机行走Wv固定长度L：

(9)

其中τ是vt′上下文的窗口大小，即vt′-τ…vt+τ.因此，skip-gram学习了一个嵌入E的特征，其中包含|V|×l个自由参数(V是聚集图上所有节点的集合和E的每一行表示特定用户的特征向量大小l.真实世界网络规模庞大，为了高效的计算，分层Softmax应用于近似p(vt′|E(vt)为了避免在Softmax中归一化函数的复杂性计算.我们模拟以每个节点为根的行走生成语义社会语料库并使用随机梯度下降训练.

3.5 项目推荐

表示学习后可直接通过计算相似性进行推荐但这种方式效果并不理想，因此考虑把获得的用户信息融合到贝叶斯排序模型.结合实际，通常为用户推荐项目是以一个有序的列表呈现的，用Pu表示用户消费的项目(喜欢或购买的项目)，Nu表示没有消费的项目(没有兴趣或没有访问过的项目).

受SBPR[4]的启发，其充分利用了社交关系的优势，并拓展了排序算法BPR[21]，如下：

xua≥xub,xub≥xuc,a∈Pu,b∈SPu,b∈Nu

(10)

其中xu.表示用户u对其中一个项目的偏好.SPu表示对项目集I至少有一个确定的朋友，但没有任何积极的反馈.

根据上述拓展并结合模型需要进行如下修改，给定Pu，IPu，Nu项目排名如下：

xui≥xuk≥xuj,i∈Pu,k∈IPu,j∈Nu

(11)

其中IPu表示用户没有过正反馈但是至少有一个语义朋友，因此自然可以想到u喜欢k超过j,u更喜欢k.这种假设可以很好的解释朋友信任朋友的推荐并且其项目排名高于观察到的消极项目.每个用户的优化标准表示如下：

(12)

其中Tu=Pu∪IPu，Hu=IPu∪Nu.如果i∈Pu并且k∈IPu时，σ(u,i,k)=1,反之σ(u,i,k)=0.以此类推，如果k∈IPu并且j∈Nu时，σ(u,k,j)=1,反之σ(u,k,j)=0.因此，后验概率如下：

(13)

(14)

本文使用随机梯度下降进行训练，SGE-BPR使用如下的梯度方程对每个观察到的结构进行参数更新.

(15)

3.6 SGE-BPR算法

算法.SGE-BPR算法

输入:The summarized graphG=(V,E), walk lengthn,embedding dimensionX, context sizeb, negative samplesM, returnp, in-outq.

输出：Recommendation list.

/*计算转移概率并初始化*/

1.π=MW(G,P,q);

2.G′=(V,E,π);

3.Initialize walks to Empty，initialize node embeddingsX;

/*聚集图上随机游走并嵌入*/

4. forl=1 tordo

5. for all nodesu∈V

6. RW=node2vecWalk(G′,u,n);

7. add walk to walks;

8.X=skip-gram(X,RW,b);

/*计算相似度并进行推荐*/

9. for useriinV

10. for userjinV

11. sim=cos(X[i],X[j]);

12. add sim to user similarity list;

13. Integrate sim into BPR model and generate the recommendation list.

如上给出了SGE-BPR算法的主要步骤.其中1-3行表示聚集图上转移概率的计算及初始化.第6行表示聚集图上的随机游走，第8行表示skip-gram嵌入，9-12行表示相似度的计算并加入到相似列表.

通过分析SGE-BPR算法可知，算法的可靠性主要由聚集图的质量来决定，即聚集图是否能保证原图信息的完整性和准确性.下面通过理论分析和实验来进行简要的证明.

证明：由聚集图的相关研究可知，信息熵可以衡量原图信息的完整性[8].假设聚集图包含k个超点，当k=n(n为原图的顶点数)时，信息熵H(Gn)=0；当k=1(一个超点)时，此时的信息熵最大.综上信息熵为0≤H(Gk)≤H(G1).进一步推论可知，k越大，信息熵越小，原图信息越完整，而k值可由用户自己控制，因而输入图为聚集图不影响算法的可靠性.最后通过karate数据集的具体例子来验证该算法在原图和聚集图的表现，进一步说明算法的可靠性.该数据集有34个用户U={ui|i=1,2,…,34},若k=20其聚集图包含20个超点，在嵌入后对其向量进行还原(根据聚集图映射表最终得到34个用户的向量表示)，这样处理能降低信息的损失，最后融入到BPR算法中，其结果如表1所示，从中可以观察到聚集图和原图在推荐的表现方面很相似.综上所述，该方法是可靠的.

表1 算法可靠性验证Table 1 Algorithm reliability verification

与最初的带有社会关系的个性化排序模型[23]及其他基于社会化BPR改进的方法相比，SGE-BPR使用图聚集技术捕获了结构相似的节点并丰富了社交排名的假设，且考虑了表示学习的拓展性及空间存储等更符合大规模图的实际情况，因而不仅保护了用户的信息且获得较好的推荐效果，另外通过相关实验证明其更好的提高了社会化推荐的表现.

4 实验结果与分析

在这一部分，我们将进行实验来验证方法的有效性.

4.1 实验设计

根据第3节所述设计实现融合聚集图表示学习的推荐方法，并对数据进行验证.实验环境为PC机Windows 10系统、Intel Core i5处理器、8GB内存，开发环境为PyCharm，采用Python 3.6进行算法的实现.采用4个常见的社交推荐数据集FilmTrust(1)http://www.librec.net/datasets.html,LastFM(2)https://grouplens.org/datasets/hetrec-2011/,Ciao(3)https://www.librec.net/datasets.html,Epinions(4)http://www.librec.net/datasets.html.对于每一个数据集本文使用80%作为训练集，10%作为交叉验证集，10%作为测试集，使用五折交叉验证，对比平均表现.数据集如表2所示.

表2 数据集Table 2 Datasets

4.2 效果比较

为了证明本文方法的有效性，与显式的社会信息相关的贝叶斯排名模型进行比较.基线方法如下：BPR[21]是一种假设用户购买过的物品的偏好排序优于用户未购买过的物品，利用用户对物品反馈情况进行个性化排序的方法.SBPR[4]是一种利用显式的社会信息拓展BPR模型的方法.CUNE[25]提出利用网络嵌入技术获得top-k隐性朋友.为了评估本文模型的性能，本文选择3种评价指标：准确率(Precision)和召回率(Recall)和排序指标平均精度均值MAP(Mean average precision)进行度量.

图2 4个数据集上算法效果比较Fig.2 Comparison of algorithm effects on four datasets

参数设置：对于所有的基线方法，基于先前工作的建议及实验，设置如下：正则化系数λX=0.01，潜在特征维数d=20，对两种网络嵌入方法，CUNE和SGE-BPR步数n=20,每一步的长度l=20，窗口大小b=5,负样本数量M=5.

如图2所示，不同的推荐方法推荐表现不一样，从图中可以观察到：首先，4个数据集上显示本文方法优于其他基线方法同时我们对本文中的方法在原图(GE-BPR)和聚集图上的效果做了比较，在聚集图上的效果优于原图.其次，3种网络嵌入方法推荐表现优于其他普通的排序方法，可能的原因是网络拓扑结构可以帮助更好的获得潜在的社会关系通过网络嵌入能缓解数据稀疏因而提高了在推荐上的表现.最后，使用隐式关系最终的推荐结果好于直接使用显式关系的结果，我们的方法加强了显式关系且降低了计算复杂度从而推荐效果好于直接使用隐式或显式关系的方法.

为了证明SGE-BPR算法的效率，我们同时对比同一算法下原图和聚集图的表现，进行实验验证了在3种指标下，本文的算法在原图和聚集图上进行时间的对比(见表3).

表3 算法运行时间对比Table 3 Algorithm running time comparison

从表3中可以看出，聚集图上的算法效率更高，特别是当数据量增大的时候，聚集图上表现了明显的优势，可能的原因是聚集图上的噪音少于原图且聚集图的节点表示得到的向量更高效.另外有研究表明，基于随机游走的采样策略所占内存少于其他方式，比如矩阵分解的方法[16]，一般而言对于无监督的图嵌入来说，使用skip-gram模型本身也存在一定的优势且聚集图是对原图的聚集，因而节省空间.

图3 4个数据集上维度的影响Fig.3 Effect of dimensions on four datasets

在方法SGE-BPR上我们主要对比了维度为10，20，40，60，80这5种不同维度下，准确率(Pre@10)、召回率(Rec@10)和平均精度均值(Map@10)的变化.从图3左图我们可以看到刚开始时小幅度的上升，随后平稳之后小幅度的下降，当维度达到一定阈值时所反映的信息比较完全，因此呈现稳定而后再增加维度不利于信息的获取.而右图波动幅度较大但变化趋势类似，因此综合而言本文维度值取20是合理且有效的，便于达到更好的推荐效果.

图4 4个数据集上负样本数目的影响Fig.4 Effect of negative sample numbers on four datasets

在方法SGE-BPR上我们主要对比了负采样数为1，2，3，4，5这5种不同负样本数，准确率(Pre@10)、召回率(Rec@10)和平均精度均值(Map@10)的变化.从图4中我们可以看到刚开始时小幅度的上升，随后平稳之后小幅度的下降，当负样本达到一定阈值时所反映的信息比较完全，因此呈现稳定而后再增加负采样时不利于信息的获取.因此本文负采样本数取5是合理且有效的.

5 结 语

本文主要利用聚集图上的表示学习挖掘潜在的信息从而加强显式关系提高推荐，受网络嵌入的启发，本文设计了一种新颖的SGE-BPR项目排名方法，使用聚集图表示学习并融合贝叶斯个性化排名模型.实验结果显示我们的方法优于传统的基于模型的方法及显式的社会推荐模型.

下一步工作将进一步考虑时间因素对推荐的影响，优化聚集图上随机游走方案，将模型拓展并结合到异构图中进行推荐.