基于节点嵌入的权重符号社交网络高效链路预测算法

杨 威 王轶彤

(复旦大学计算机科学技术学院 上海201203)

0 引 言

随着在线社交网络的快速发展，许多系统能够建模成WSSN[1]，以便更细粒度地反映节点之间的关系。在一个权重符号社交网络中，每条边上的权值可以同时反映情感的倾向(正或负)以及关系的强弱(具体的数值)。例如，考虑边权重为+3、+2或-2，不仅具有符号以反映情感的倾向：喜欢/不喜欢、信任/猜忌、朋友/敌人、合作/竞争等，还能抓取关系的强度，如喜欢的程度、猜忌的程度等。在一些在线社交媒体中，边的符号和权重值是直接给定的。例如，在比特币的交易平台(Alpha或OTC)中，用户能够使用-10(完全不信任)到10(完全信任)的分数值来评价其他用户，以此来表达对于其他用户的态度。与此同时，现实中也存在一些在线的社交网络，它们给定了边的符号，但边的权重需要隐式抽取。例如，在维基百科管理员申请网络(RfA)中，如果一个维基百科的编辑者想要成为一个管理员，他需要先提交一个申请，而其他的用户使用三个标签(支持、中性或反对)中的一个来对这个申请进行投票，辅之以简短的投票理由。因此，能够使用一些语义分析工具从投票附加的文本中隐式的抽取出边的权重并且形成一个权重符号社交网络[1]。显然，权重符号网络能在更细的粒度上反映社交网络中节点之间的信息。在无权无符号的社交网络中，链路预测问题主要关注于边存在性的预测，可以扩展为对边符号(正或负)的预测(符号网络)。本文专注于权重符号社交网络的链路预测问题，即预测边上的权重信息，包含符号和数值，反映关系的方向和强弱。目前主要的链路预测研究都集中在如何能更好地获取节点的信息及正确度量节点之间的近似性，但这种思想并不完全适用于权重符号网络，需要进一步结合社会学理论和网络结构来提高边上权重的预测性能。

对于许多社交网络应用，如链路预测[2]和节点分类[3]，其网络特征的提取是非常重要的。许多算法的性能极大地取决于对输入网络特征提取的有效性，节点和网络结构重要的特征需要尽可能保存。不同于传统的特征工程方法，网络嵌入为网络中的节点学习一个低维度的潜在特征，从而保存网络的结构信息。网络嵌入是自动的特征提取，许多研究已经证明此方法优于一些特征工程的方法。特别是近几年，网络嵌入方法被广泛地应用于社交网络分析领域。本文将基于节点嵌入对权重符号网络中的边进行权重预测。

目前的网络嵌入方法，主要集中在无符号/无权重社交网络。在无符号社交网络中，边被标记为1或者0(1代表存在，0代表不存在)。大多数无符号网络嵌入的方法基于同构性原理和skip-gram模型[4]。在设计目标函数的过程中，并未考虑边的符号或权重。文献[5,15]已经证明负边具有额外的价值，考虑负边能够提高正边的预测精度。由于负边的存在，同构性原理不再适用。一些基于平衡理论的方法[6]应用随机游走策略生成带有符号的共现对，以此来嵌入符号网络。这些方法并未直接拟合边的权重信息，如果将它们直接用于嵌入权重符号社交网络，将会导致社交链路预测的性能不佳。边的权重在度量节点间关系强度上是一个关键要素，它给出了节点间关系的更细粒度信息，并且能更准确地反映网络结构。同时，在嵌入空间中保存边的权重信息将会取得更优的边权重预测性能。

本文提出一种权重符号社交网络嵌入方法(Weighted Signed Network Embedding，WSNE)，以此来获得更优的边权预测性能。WSNE为网络中的节点学习潜在特征表示，并且在学得的潜在特征空间中尽可能地保存边的权重和符号信息。在一个权重符号社交网络中，一条边eij能够考虑作为从用户i到用户j“主观性”观点/评价的传递。从用户j的视角来看，这个观点/评价是客观的。因此，对于一个节点i去学习它作为一条边起始节点的“主观”潜在特征表示si和作为一条边终止节点的“客观”潜在特征表示oi。参照矩阵分解的方法[7]，对于一条边eij，使用si和oj的点积拟合边的权重信息。同时在一个权重符号社交网络中，边的符号也是非常重要的，因为它反映了不同的情感。例如，如果一条边的权重是1，拟合值-1和3将会产生同样的误差。但是3明显是更优的拟合值，因为它反映了准确的情感倾向。因此，本文基于扩展的结构平衡理论[8]添加对于边的符号约束。

本文主要贡献如下：

1) 提出了一个权重符号社交网络嵌入方法WSNE来获得更优的边权重预测性能。

2) 设计了一个目标函数来学习网络中节点的“主观”及“客观”潜在特征表示。在学得的潜在特征空间中，保存了边的权重和符号信息。

3) 在三个真实网络数据集上进行社交链路预测任务。使用根均方误差、相关系数、符号预测准确率等多个评价指标，与多个相关且优秀的算法进行比较。实验结果表明，WSNE在上述评价指标上实现了更优的权重预测性能。

1 相关工作

本文使用网络嵌入的方法解决权重符号社交网络中的社交链路预测问题，因此主要关注于网络嵌入方法和权重预测方法。

1.1 社交网络分析中的网络嵌入

大多数网络嵌入方法主要关注于无符号网络[4,9-12]和无权带符号社交网络[13-18]。对于无符号社交网络，许多方法是基于同构性原理并且参考skip-gram模型[4,10]来学习节点的嵌入。Perozzi等[4]通过将截断随机游走生成的节点序列和语料库中的句子等价，来学习节点的潜在特征表示。Tang等[9]设计了一个目标函数来保存局部和全局的网络结构，同时还提出了一个边抽样技术来解决经典随机梯度下降方法的限制。Grover等[10]提出了一个灵活的节点邻居概念，并且设计了一个偏好随机游走程序来获得多样性的邻居。此外，Ou等[11]关注有向无符号网络，提出HOPE方法在学得的嵌入空间中保存边的不对称传递性。Wang等[12]提出一个半监督的深度学习模型来优化一序和二序邻近性。但上述嵌入方法并未考虑到边的符号和权重信息。

对于无权符号网络，文献[13]使用log-bilinear模型，通过最大化在给定路径下生成目标节点的条件概率来学习节点的源嵌入和目标嵌入。文献[14]使用word2vec嵌入方法，并提出一个目标节点抽样策略来维持高序邻居间的结构平衡。文献[15]提出了一个深度学习框架SiNE来学习节点的潜在特征表示，优化一个结构平衡理论指导的目标函数。文献[16]采用多个信息源：情绪信息、社交信息和简历信息，并且使用多个自编码器来训练每一个信息源。文献[17]利用网络结构和节点的属性来学习符号社交网络的嵌入。文献[18]提出一个网络嵌入方法SIDE，完善编码边的符号和方向信息。但上述方法并未直接拟合边的权重信息，如果直接用于解决权重符号社交网络的社交链路预测任务，将不会获得最佳的性能。

1.2 权重预测任务

在边权预测中，大部分的相关工作关注于无符号社交网络。Gilbert[19]提出了一个Twitter应用——We Middle，其核心是Facebook链接强度模型的设计，以此来评估链接的强度。Xiang等[20]使用交互信息(例如社区和标签)和用户的相似性开发了一个无监督模型来获取关系的强度。在权重符号社交网络的边权预测中，Kumar等[1]提出Fairness和Goodness两个特征来预测边的权重。还有多个方法也能够应用于权重符号社交网络中的权重预测，例如：reciprocal，PageRank，signed eigenvector centrality，bias and deserve，EigenTrust和signed-HITS[1]。但文献[1]已经证明Fairness和Goodness(FG)能够取得更优的权重预测性能，因此本文方法主要与FG方法进行比较。

2 问题描述

一个权重符号社交网络被建模成一个有向的加权图G=(V，E，E+，E-，W)，其中：V是节点集合；E是边集合；E+是正边集合；E-是负边集合；W∈R|V|×|V|是一个边权矩阵。在W中每一个元素Wij表示一条从i到j的有向边的权重。当谈论一条边的权重时，例如-5，它实际上指示着边的符号和关系的强度。本文尝试为网络中的节点学习“主观”潜在特征S和“客观”潜在特征O，以此来拟合边的权重信息。即本文想要学习一个转移函数f(·)，使得：

f(V,E,W)→(S,O)

(1)

式中：S和O的维度是|V|×K(K≪|V|)，|V|是节点的数目，K是潜在特征的维度。问题的关键在于如何设计一个有效目标函数来学习更好的节点嵌入。

3 算法设计

3.1 边权重的拟合

(2)

3.2 添加符号约束

在一个权重符号社交网络中，符号拟合的一致性是非常重要的。对于一条真实权重为1的边，即使有着相同的误差，拟合值为-1或者3是完全不同的结果。显然3是更好的拟合值，因为它准确地拟合了情感的倾向。因此，对于网络中每一条存在的有向边，在拟合其权重时，不仅需要拟合权重的数值，还需要准确拟合符号，本文添加一个局部的符号约束来满足这一点，目标是最小化拟合值和真实值之间误差的同时，保持符号的一致。同时，实验结果表明权重预测中符号和数值之间是相互提高的，既提高拟合值和真实值之间符号的一致性，也能够进一步提高社交链路预测的性能。

符号约束是基于社会学中的扩展的结构平衡理论[8]，即正边端点之间的相似性大于负边端点之间的相似性：

sim(i,j)>sim(h,k)eij∈E+,enk∈E-

(3)

式中：sim(·，·)是一个相似性度量函数。与文献[18]相同，本文使用Sigmoid函数度量两个端点之间的相似性：

(4)

式中：si表示“主观”矩阵S中第i行;oj表示“客观”矩阵中的第j行。

(5)

使用对数运算来简化上式的计算，并且为了与拟合权重中最小化目标函数一致，将转换式(5)为：

(6)

结合式(2)和式(6)，WSNE方法总的目标函数为：

L(S,O)=M+γ×C

(7)

式中：γ为参数，控制着符号约束的贡献。本文使用随机梯度下降算法来获得目标函数的局部最优值。

3.3 算法步骤

将数据集划分为两个部分：当前网络中存在的正边集合和负边集合。对于每一个部分，分别描述其优化过程。

对于集合E+中的边eij，求解si和oj的梯度：

(8)

对于集合E-中的边eij，求解si和oj的梯度：

(9)

基于式(10)迭代地更新si和oj，这里α为学习速率(本文设定α=0.005)。

(10)

当目标函数连续两次平均值之差小于预先定义的阈值(本文设定为0.005)时，则认为算法收敛。WSNE的详细描述如算法1所示，其时间复杂度为：

o(t×|E|×K)

(11)

式中：t是迭代的次数;|E|是边数;K是潜在特征的维度。

算法1WSNE

输入：G、β、γ。

输出：S、O。

随机初始化S、O;

While 不收敛do:

Foreij∈(E+∪E-):

Ifeij∈E+:

根据式(8)计算si和oj的梯度;

Ifeij∈E-:

根据式(9)计算si和oj的梯度;

根据式(10)更新si和oj;

End

4 实 验

本节将验证WSNE算法在权重符号社交网络中的社交链路预测问题上的性能。特别地，算法的验证主要集中在该种网络的边权重预测问题。

4.1 数据集

本文在3个数据集上运行WSNE算法并验证其性能。

1) 比特币Alpha[21]和比特币OTC[22]：它们是来自于两个比特币交易平台Alpha和OTC的信任网络。每一个用户能够使用-10(完全不信任)到10(完全信任)间隔为1的数字，来表达他们对于其他用户的态度。

2) 维基百科管理员申请网络(RfA)：使用文献[1]中提供的RfA数据集，其权重范围是[-1,1]。为了便于比较，离散化数据集的取值范围到[-10, 10]，间隔为1，并且仅考虑正边和负边。

三个数据集的具体统计描述如表1所示。

表1 数据集的统计信息

4.2 评价指标

本文选择根均方误差(Root Mean Square Error，RMSE)和相关系数(Correlation Coefficient，CC)作为权重预测性能的评价指标。RMSE度量预测值和真实值之间的差异程度，其值越小越好。CC度量两个序列之间的相关性(真实值序列和预测值序列)，该值越高则表明预测序列的改变趋势和真实值序列之间越具有相关性。

在一个权重符号社交网络中，边的符号预测同样重要。因此，还需探讨取得优异权重预测数值时的符号预测性能，即有多少情感倾向被准确地预测。本文使用符号准确率(SignAccuracy, SA)作为符号预测的评价指标(SA=预测正确的符号数/总的预测边数)。

4.3 参数分析

WSNE方法包含3个重要的参数：潜在特征的维度K、控制正则项贡献的参数β和控制符号约束贡献的参数γ。本文选择比特币Alpha数据集、RMSE和CC度量指标作为例子来阐述参数的敏感性问题。根据预实验，参数的分析范围可以大致确定为：K∈[5,30]，间隔为5；β∈[0.5,2.5]，间隔为0.5；γ∈{1,5,10,15,20}。对三个参数使用网格搜索，找寻一组性能相对优异的参数取值。为了便于对单个参数的研究，分析一个参数时，固定另外两个参数。将数据集随机划分为两部分，其中训练集的比例为80%，测试集的比例为20%(本文不考虑冷启动问题，即未被训练过的节点不会参与预测)。对训练集使用五折交叉验证来评估参数的选择。使用范围内的随机值初始化潜在特征矩阵S和O。重复实验5次，取平均值作为最终的结果。

1) 参数K。分析参数K时，固定β=1.5、γ=10，具体的实验结果如图1和图2所示。

图2 参数K的CC值分析结果

可以看出，随着K值的增加，RMSE先减小后增大，CC先增大后减小。当K取[20, 30]范围内时，RMSE和CC都取得最优的结果。权重预测是一种细粒度的问题，过大的K值会损害权重预测的性能。同时K取值越大，需要的存储空间越多。在实际操作中，K的取值不宜过大，对于不同的数据集而言，K的最优取值不同。

2) 参数β。分析参数β时，固定K=25、γ=10，具体的实验结果如图3和图4所示。

图3 参数β的RMSE值分析结果

图4 参数β的CC值分析结果

可以看出，随着β值的增加，RMSE先减小后增大，CC先增大后减小。当β取[1,2]范围内的值时，RMSE取得最优值。当β取[1.5,2.5]范围内的值时，CC取得最优值。β控制着正则项的贡献，用来避免过拟合问题。过大的β值，将会损害权重的拟合，从而导致权重预测性能下降。

3) 参数γ。分析参数γ时，固定K=25、β=1.5，具体的实验结果如图5和图6所示。

图5 参数γ的RMSE值分析结果

图6 参数γ的CC值分析结果

可以看出，随着γ值的增加，RMSE先减小后增大，CC先增大后减小。当γ的取值在范围[5, 15]内时，RMSE和CC都获得了最优的结果。γ控制着符号约束的贡献，适当地添加符号约束能够提高权重预测的性能。但是，过大的符号约束将会引入噪声，导致权重预测性能的降低。

基于上述参数的分析，为了后续实验的便利和各个数据集上的统一，本文实验中设定K=25、β=1.5、γ=10。

4.4 对比算法

本文选取了如下4个算法进行对比：

1) Fairness 和Goodness(FG)[1]。这一算法也用来预测权重符号社交网络中的边权重。该算法提出了两个度量指标：Goodness衡量节点被其他节点喜欢的程度，而Fairness用来衡量节点评价其他节点的公平性。通过迭代计算来获得节点的Fairness和Goodness的值，进而用Fairness和Goodness的积预测边权重。这与WSNE的研究背景最相似。

2) node2vec[10]。这是一个无符号社交网络嵌入的方法。node2vec扩展了节点邻居的概念，并且设计了一个偏好随机游走程序来获取多样性的邻居。通过将其与WSNE进行比较，验证是否可以直接用传统无符号网络嵌入的方法预测WSSN中的权重。

3) SIGNet[14]。这是一个符号网络嵌入的方法。SIGNet扩展了word2vec嵌入方法，并用于符号社交网络。它为每一个节点构造一个缓存，通过从缓存中抽样来改进负抽样技术。与该算法的比较，将验证在WSSN中进行权重预测时，权重的符号和数值这两个因素之间的关系。实验结果表明，只考虑符号的嵌入，不直接拟合边的权重信息并不能获得满意的预测性能。

4) MF[7]。这是一个矩阵分解的方法，使用潜在特征向量之间的点积来拟合边的权重。通过比较，能够进一步验证添加符号约束是否能够改进权重预测的性能。

本文提出的WSNE算法采用潜在特征向量的点积来拟合边的权重信息，并且将符号约束添加到目标函数中以提高权重预测的性能。

4.5 结果与分析

在一个权重符号社交网络中，主要关注权重预测任务。将数据集划分为两部分：训练集为80%，测试集为20%。由于无符号网络嵌入的方法不能够处理负边，因此，在它嵌入学习的过程中删除负边。在实现对比方法时，本文使用相应文献中提供的默认参数设定。将对比算法[10, 14]中学得的节点潜在特征进行级联为边的特征，作为预测模型的输入(在权重预测中使用线性回归方法，在符号预测中使用逻辑回归方法)。WSNE方法直接使用节点潜在特征向量的点积来进行权重预测和符号预测任务。

1) 权重预测。使用RMSE和CC来评价权重预测的性能。实验结果如表2所示。

表2 权重预测的实验结果

可以看出，在所有的情况下，WSNE算法都取得了最优的表现。其对于node2vec和SIGNet方法的优势表明直接将无符号网络和符号网络嵌入的方法用于权重预测问题，并不能获得优异的预测性能。同时，WSNE算法也优于MF算法，表明添加符号约束到目标函数中能够提高权重预测的性能。

2) 符号预测。符号在权重符号社交网络也是非常重要的，因此在已获得较好的权重预测性能的基础上，本文将进一步验证符号预测的性能。使用SA作为符号预测的评价指标，实验结果如表3所示。

表3 符号预测的实验结果

可以看出，在取得优异的权重数值预测性能的情况下，WSNE算法也取得了优秀的符号预测性能，即WSNE算法准确地拟合了边的符号信息。此外，在RfA数据集上，多个方法的性能都是不佳的。这可能是因为，RfA是一个人工生成的权重符号社交网络，在使用语义分析工具将文本内容转化为边权值时引入了噪音。同时，文献[1]提供的RfA数据集的边权范围为[-1,1]，本文离散化该范围为[-10,10]，间隔为1。即，对于在(0.1,0.2]范围内的值，离散化为2。再者，也可能是由于RfA数据集负边比例相对较大，上述算法不能很好地处理负边。

3) 稀疏性问题。为了探索数据稀疏性问题，本文按照不同的比例来划分比特币Alpha数据集。增加测试集的比例同时减小训练集的比例，实验结果如图7和图8所示。

图7 RMSE值的稀疏性结果

可以看出，随着测试集比例的增加，各个算法的性能都有了不同程度的降低。但WSNE算法依旧取得了最优的权重预测性能，这表明WSNE算法能够更好地适应数据稀疏性问题。

5 结 语

本文提出了一个权重符号社交网络嵌入算法WSNE，来解决权重符号社交网络中的权重预测问题。WSNE算法使用每条边两个端点的潜在特征向量的点积来拟合边的权重。同时该算法考虑到在权重符号社交网络中符号的重要性，提出符号约束并结合到目标函数中。本文在三个真实数据集上实现权重预测，并与其他相关且性能优秀的算法进行了比较，数值和符号预测的实验结果表明WSNE算法取得了更优的社交链路预测性能。

尽管本文算法利用了边的符号信息来提升权重预测的性能，但只考虑了局部的符号约束，在未来的工作中将探索并结合更多的全局符号约束，以进一步提高权重预测性能。同时，尽管在数据稀疏性问题上WSNE算法的表现都最优，但是随着训练集比例的减少，WSNE算法的性能还是受到了明显的影响。在未来的工作中，希望利用更多额外的信息，例如节点的属性信息，来缓解数据稀疏性问题。