NEG-MF：一种针对推荐系统的矩阵分解图嵌入模型

赵素芬

摘  要： 传统的矩阵分解图嵌入模型由于不对大量未知关系建模，其性能面临着很大的挑战性。为了提升矩阵分解模型的性能，提出了一种基于负采样技术的矩阵分解模型NEG-MF。该模型能够从跳数大于6的邻居节点中进行负采样，以降低模型生成图嵌入时对于负样本的偏差。在DBLP数据集上做的大量实验结果表明，相比其他的基线方法，基于NEG-MF的推荐算法在学术合作关系推荐问题上的性能有明显地提升。

关键词： 矩阵分解; 图嵌入; 推荐系统; 负采样

中图分类号：TP311          文献标识码：A     文章编号：1006-8228（2021）09-06-04

Abstract： The traditional matrix factorization graph embedding model does not consider a large number of unknown relationships， so that its performance faces great challenges. In order to improve the performance of the generated embeddings， NEG-MF， a matrix factorization model based on negative sampling is proposed. When the model generates node embeddings， it can perform negative sampling from the neighbor nodes with hops>6 to reduce the bias of negative samples. A large number of experiment results on DBLP data sets show that， compared with the baseline methods， the performance of the recommendation algorithm based on the proposed NEG-MF has a significant improvement in the recommendation of academic collaborators.

Key words： matrix factorization; graph embedding; recommender system; negative sampling

0 引言

圖是自然界中一种非常重要的数据结构。许多应用都是定义在图的基础上，例如学术合作网络、蛋白质交互网络、社交网络、知识图谱等等。在基于图的众多机器学习问题中，其核心任务就是找到一种将图的结构信息和语义信息融合到机器学习任务的方法，即将网络中的节点、边或子图映射到低维的向量空间，并且使得到的特征向量尽可能地保持原有图结构信息、节点属性信息和语义信息等等，即图嵌入技术[1]。

随着word2vec模型[2-3]在文本嵌入领域的广泛应用，目前已经涌现了大量的图嵌入算法，包括各种基于矩阵分解的模型（GF[4]，LAE[5]，GraRep[6]，HOPE[7]，LINE[8]等等），基于随机游走的方法（Deepwalk[9]，Node2vec[10]等），基于邻居的自编码模型（SDNE[11]，DNGR[12]）以及基于图神经网络的模型（GCN[13]，GraphSage[14]）等等。不过，由于真实世界中网络的复杂性，现有的图嵌入模型通常面临如下挑战。

⑴ 网络的大规模性 真实世界中的网络常常是大规模的，包含成千上万的节点和复杂的关系，这对图嵌入算法的学习效率提出了很大的挑战。一个好的模型应当具有很好的可扩展性，具有更少的时间复杂度和空间复杂度，否则难以在小规模的计算平台上运行。

⑵ 嵌入模型本身需要满足多目标性 图嵌入模型不仅需要考虑网络的结构特征，还需要考虑属性信息、语义信息等。除此以外，嵌入模型在满足通用性的要求之外，还应当能够针对特定的机器学习任务有较好的效果。如何在一个模型中同时满足多个学习目标，对图嵌入算法提出了巨大的挑战。

⑶ 网络的动态性真实世界中的网络是在不断变化的。如果图嵌入模型是直推式的，则每次网络有变化时，都需要重新训练，这是一种巨大的耗费。如何处理动态变化的网络，对图嵌入模型提出了严峻的挑战。

在现有的图嵌入模型中，矩阵分解是其中一种最经典和基础的一种。由于矩阵分解类模型相对简单，针对大图的可扩展性非常好，因此在各类应用中应用十分广泛。然而，基本的矩阵分解模型[4]仅对正例进行建模，给了负样本太多的误差。这会导致生成的嵌入性能非常有限。为了提升矩阵分解模型生成图嵌入的性能，针对挑战问题⑴和⑵，我们提出了一种新的基于负采样技术的矩阵分解模型NEG-MF。NEG-MF模型在原有的GF模型的基础上，加入了对未知关系的建模。具体来说，模型能够从跳数大于6的网络邻居节点中进行负采样，以降低模型生成嵌入时对于负例的偏差。

针对DBLP数据集，我们做了大量的实验。实验结果表明，相比较传统的基线推荐方法（共同邻居法、AA算法、DeepWalk、Node2Vec以及基本的矩阵分解模型等），改进的NEG-MF模型在推荐系统的性能上有较大的提升。

1 研究问题定义

本文使用的数据集是DBLP文献数据集（https：//dblp.uni-trier.de/xml/）。该数据集中包含了计算机类学术论文的元数据信息，包括论文的标题、作者、发表年份、发表期刊/会议名、URL链接等等。通过对文献数据集中作者之间的合作关系进行提取，可以构建一个学术社交网络[G=V，E]。其中，[V=v1，v2，…，vn]表示网络中的学者，[E=eij，1≤i，j≤n]表示两个作者[vi]和[vj]之间具有合作关系。基于已有的合作关系，我们为每一个目标用户推荐潜在最有价值的top-k个新的合作关系。

定义1：基于图嵌入技术的学术合作推荐问题

针对任意一个t时刻之前的学术社交网络[G=（V，E）]，为[G]中每一个节点[vi]生成低维特征表示[zi∈Rd，d?|V|]，使该特征表示能够尽可能的捕获[G]中的网络结构信息和属性信息。同时，针对给定的目标用户s，为其推荐在[t+Δt]时刻最具潜在合作性的top-k个合作关系。

从定义1中可以看出，本文要解决的研究问题是多目标的。也就是说，模型在为网络中的每个节点生成嵌入的同时，需要能够为特定的目标用户推荐新的社交关系。

2 新的基于负采样技术的矩阵分解模型NEG-MF

2.1 经典的矩阵分解模型Graph Factorization（GF）

经典的矩阵分解模型GF[4]的编码函数为直接编码，即：

2.2 NEG-MF矩阵分解模型

为了提升GF模型的性能，我们提出了一个新的矩阵分解模型：NEG-MF，其思路是在损失函数⑶中增加对负样本的建模。我们将公式⑶中的损失函数修改为：

基于计算好的梯度公式，我们在表1中给出了NEG-MF算法的随机梯度下降（SGD）的版本。在实际运行过程中，也可以视系统内存大小将其修改成为批梯度下降的版本。

2.3 关系推荐

基于2.2节抽取的用户节点嵌入，我们可以使用多种推荐模型为特定的目标用户s进行新的关系推荐。首先， 我们定义了多种打分函数对s和候选推荐用户u的交互值进行评分。

⑴ 内积函数：[frs，u=zs?zu]

这是最简单直接的推荐模型。也就是说，基于前面已经求解的嵌入，使用内积函数求解目标用户s和候选推荐用户u之间的关系得分。在这个模型中，求解节点嵌入和合作关系推荐是两个互相独立的组件。

⑵ 非线性神经网络模型：[frs，u=σ（Wzszu+b）]

这里，[σ]是sigmoid函数，W和b是可以训练的模型参数，[zszu]表示向量的拼接。在这个模型中，由于包含可训练的参数，因此可以定义推荐模型阶段的损失函数为：

其中，[VL]是带标记的用户集合;

[pu|s=exp （frs，u）u'∈Vexp （frs，u'）]是用户u和用户s之间的条件概率相似度。

这时，求解节点嵌入和关系推荐既可以是两个相互独立的部分，也可以进行融合。如果将这两个部分放在同一个模型中一起训练，则模型的总损失函数为：

这样，可以在一个模型中同时学习到节点嵌入，以及推荐系统部分的模型参数值。在实际应用中，除了单层的神经网络模型，还可以选择很多其他类型的推荐模型和嵌入模型进行融合。

使用打分函数[frs，u]计算出针对用户s的候选用户得分之后，按照从高到低的次序选择值最大的前k个推荐给用户s即可。

3 实验结果

3.1 数据集和预处理

本文使用的数据集是DBLP數据集（2019-05版本）。我们首先将数据集中全部的期刊论文、会议论文以及全部作者的信息抽取出来，然后将所有论文中发表年份小于1990的全部去除。接着，以2014年为分割线，统计每个作者在1990年至2013年期间（训练阶段）以及2014年至2020年（测试阶段）发表论文的总篇数。考虑到发表论文数较少的学者对整体的网络结构影响较小，我们取4-核作者（在训练阶段和测试阶段发表论文数均不小于4篇的作者）。基于这些4-核作者在训练阶段发表论文建立的合作关系，我们首先生成了训练阶段的邻接矩阵S1，然后得到一个囊括156021个作者的极大联通组件。我们剔除了不在极大连通子图中的作者，以及在测试阶段没有创建任何关系的作者，将剩下的153248个作者作为最终的实验对象。数据集的最终统计信息如表2所示。

3.2 基线方法和评估指标

为了评估NEG-MF图嵌入算法在学术合作关系推荐问题上的性能，我们将NEG-MF方法的推荐性能和以下基线方法进行了比较，包括无监督推荐算法：共同邻居（CNs）、Academic/Ada（AA）以及最短距离（SP），以及图嵌入算法：基本的矩阵分解（GF）、DeepWalk（DW）以及node2vec （N2V）模型。模型的评估指标为top-k关系推荐的准确率precision@k以及召回率recall@k。

3.3 实验结果和分析

表3中给出了各个算法的整体的性能的比较（其中，所有图嵌入算法DW，N2V，GF，NEG-GF的节点嵌入维度均设置为256维）。从表3中可以看出，与经典的各种基线方法相比，NEG-MF方法在精确率和召回率上均取得了最好的效果。即使相对于能够对高阶邻居关系建模的DeepWalk算法和Node2vec算法来说，新提出的NEG-MF算法也毫不逊色。除此以外，我们还探讨了当节点嵌入维度从64变化到512时矩阵分解嵌入算法的推荐效果的比较，结果显示在表4中。从表4可以看出，当生成的节点嵌入维度增加时，模型的推荐性能会变的更好。但是，当嵌入维度较低时，维度增加会使推荐性能增加的幅度更大;当维度增加到一定程度的时候（比如超过256维），靠增加维度的方式能够提升的性能非常有限。考虑到模型的性能与复杂度之间的平衡，我们认为128～256维是一个较合适的维度区间。

4 结束语

本文中，针对学术合作者推荐问题，我们设计了一种基于负采样技术的矩阵分解嵌入模型NEG-MF，并将该模型生成的嵌入用于学术合作推荐问题。实验结果表明，相比较传统的基线推荐算法，NEG-MF由于引入了有策略性的负采样技术，而使生成的嵌入质量有很大的提升，其推荐性能超越了已有的基线方法。

未来，我们的研究方向主要有三个方面：①将模型扩大到异质网络嵌入的范畴;②在矩阵分解嵌入模型中引入对属性信息的考虑，增强模型的建模能力;③考虑将模型扩展到动态网络的范畴，设计出归纳式模型。

參考文献（References）：

[1] William L. Hamilton， Rex Ying， Jure Leskovec. Represen-tation Learning on Graphs： Methods and Applications. IEEE Data Engineering Bulletin，2017.40（3）：52-74

[2] Tomas Mikolov， IlyaSutskever， Chen Kai， et.al. Neural Information Processing Systems， Lake Tahoe， Nevada， United States，2013.

[3] Omer Levy， YoavColdberg. Neural Word Embedding as Implicit Matrix Factorization.NIPS， 2014.

[4] Amr Ahmed， Nino Shervashidze， Shravan Narayanamur-thy.Distributed Large-scale Natural Graph Factorization.WWW， Rio de Janeiro， Brazil，2003.

[5] MikhaiBelkin， ParthaNiyogi. LaplacianEigenmaps and Spectral Techniques for Embedding and Clustering.NIPS，2001：585-591

[6] Cao Shaosheng， Lu Wei， XuQiongkai. GraRep： Learning Graph Representations with Global Structural Information. CIKM， Melbourne， Australia， 2015.

[7] MingdongOu， Peng Cui， Jian Pei， etc.Asymmetric Transitivity Preserving Graph Embedding. KDD，2016.

[8] Jian Tang， MengQu， Minzhe Wang， etc. LINE： Large-scale Information Network Embedding. WWW，2015.

[9] Bryan Perozzi， Rami AI-Rfou， Steven Skiena.DeepWalk：Online Learning of Social Representations. KDD， New York， NY， USA，2014.

[10] Aditya Grover，Jure Leskovec.Node2vec：Scalable Feature Learning for Networks. KDD， San Francisco， CA， USA，2016.

[11] Wang Daixin， Cui Peng， Zhu Wenwu. Structural Deep Network Embedding. KDD， San Francisco， CA， USA，2016.

[12] Shaosheng Cao， Wei Lu， QiongkaiXu. Deep Neural Networks for Learning Graph Representations. AAAI，2016：1145-1152

[13] Thomas N. Kips， Max Welling.Semi-Supervised Classification with Graph Convolutional Networks.5th International Conference on Learning Representations， ICLR 2017， Toulon， France，2017.

[14] William L. Hamilton， Rex Ying， Jure Leskovec. Inductive Representation Learning on Large Graphs.NIPS， Long Beach， CA， USA， 2017.