·440· 智能系统学报 第13卷 中均取得了很好的预测效果。 模型得到的符号预测结果为=(PQ)。因此，以 基本矩阵分解模型充分利用了邻接矩阵的全局 式(4)为目标函数的优化方法，不但考虑了符号网 低秩特性，但是，在被符号网络所代表的社会关系 的全局低秩特性还考虑了待预测边两端节点的局部 网中，不同节点的标注行为常常具有偏置现象：网 标注特征，与基本模型相似，添加了关于局部特征 络“喷子”也被称为Tro”的节点，该类节点为引起 项的正则化项Ui2+Ujm防止过拟合。 别人的注意会故意攻击其他人，“Troll'"节点会发出 损失函数I可以有多种选择，本文选择Square 比其余节点更多的负边；与此相对应的，有些节点 1oss为损失函数，于是优化目标函数可写成： 会收到低于平均水平的评价，它们可能受到网络欺 2 凌”，这一现象的社会心理学根源是“认知失调”，人 与-(b+∑P (5) 们通常为保持与他人态度的一致而调整自己的行为 (P++Uioor+Ujn2) 因此而攻击收到过负面评价的人。从真实符号网络 对式（⑤）给出的优化问题可以采用随机梯度下 的统计特征发现，这两类节点在符号网中确实存 降法进行求解，令=A-,+∑PQ通过求梯 在，虽然数量不多但其作用巨大。在符号预测问题 =1 中仅考虑平均后的全局特征并不能完全反映网络结 度以确定优化函数下降方向：那=-24,0+2P.。 ac 构特征，节点的局部标注特征需要在预测模型中得 ac 80: =-2eP:+2Q,同理也可求得目标函数对 以体现。现定义待预测边的局部标注特征为 b=μ+Uiout+Ujim (3) Ui、Ujim的偏导数，由于沿梯度方向相反的方向下 式中：μ为符号网络的平均标注倾向，当μ为负时说 降最快，于是得到如下迭代公式： 明网络用户更倾向于给其他用户以负面评价；μ为正 P:←-P:+a(eQj-AP) (6) Qi←Q1+a(eP:-Qi) (7) 时，则表示网络用户有给其他邻居以正面评价的倾 Uiout Uioat+a(eij-aUiou) (8) 向。设待预测边e(i,)两端的节点为i和j,Uio表示 Ujin -Ujin+a(eij-al jin) (9) 节点i发出的边符号的均值，Ui的值能够反映节 通过反复迭代并不断优化参数，使观测矩阵 点i对相邻节点的局部标注特征：若节点发出的负 A与分解后矩阵B+PQ间的误差小于设定的误差 边数大于正边数，表示节点i给邻居以负面评价的 值即最终收敛。其中α为学习速度，α越大下降就越 可能性大，e(i,)被预测为负的可能性就增加。同 快。随机梯度下降的时间复杂度为O(mk),t为迭代 理，Uj为j收到的边符号的均值，当Uj为负时表示 并收敛次数，m为节点个数，k为秩数。由于符号网 节点j收到了更多的负面评价，因此(i,)被预测为 络满足低秩特性，通常<值很小，且收敛较快，因此 负的可能性就增加。图3给出了符号网络标注的局 采用随机梯度下降法求解最小化问题速度较快。 部偏置示例，设μ=0.2，即符号网络全局有正面评价 的倾向，经计算可得：Uim=[(-1)+(-1)+1]/4=-1/4, 3实验结果与分析 Ujim=-1/4,于是b=-3/10,此时边e(,)的符号预 3.1数据集描述 测结果将向负偏斜。 实验中的3个真实大型社会网络数据来自于斯 坦福大学的SNAP2项目，Epinions给出了用户间 “who-trust-whom”的关系，Slashdot是一个技术相关 的新闻网站，允许用户根据自身观点标记其他用户 图3标注行为的偏置现象 为friend/foe,Wikipedia是维基百科申请管理员身 Fig.3 Bias behavior of signed edges 份的投票关系网，若一个用户被大多数其他用户同 b,的值能够很好地反映待预测边两端节点的局 意则当选为某一学科的管理员负责百科词条的维 部标注行为和行为偏好，将标注偏好反映在预测的 护，若该用户未受到大多数其他用户的赞成票则选 目标函数，得到较基本模型更为精细的预测模型： 举失败。表1给出了3个网络的统计特征。 rC=∑4y-b,+∑P.0u》t 表1的统计结果显示：3个符号网络中正边占 (4) 比均在75%以上，而负边占比较少，互惠边(recip a(lIP+lll+Uioor+Uj2) rocal edges)是指两用户间持有相同态度，这样的互 根据式(4)可知：节点i对节点j的符号可被预 惠边在网络中占有一定比例，且互惠边中正边居 测为=b+(PQ),而式(2)表示的基本矩阵分解 多，这与人们社会心理有关，当一个人讨厌另一个中均取得了很好的预测效果。 基本矩阵分解模型充分利用了邻接矩阵的全局 低秩特性，但是，在被符号网络所代表的社会关系 网中，不同节点的标注行为常常具有偏置现象：网 络“喷子”也被称为“Troll”的节点，该类节点为引起 别人的注意会故意攻击其他人，“Troll”节点会发出 比其余节点更多的负边；与此相对应的，有些节点 会收到低于平均水平的评价，它们可能受到“网络欺 凌”，这一现象的社会心理学根源是“认知失调”，人 们通常为保持与他人态度的一致而调整自己的行为 因此而攻击收到过负面评价的人。从真实符号网络 的统计特征发现，这两类节点在符号网中确实存 在，虽然数量不多但其作用巨大。在符号预测问题 中仅考虑平均后的全局特征并不能完全反映网络结 构特征，节点的局部标注特征需要在预测模型中得 以体现。现定义待预测边的局部标注特征为 bi j = µ+Uiout +U jin (3) µ µ µ e(i, j) Uiout Uiout e(i, j) U jin j U jin j e(i, j) µ = 0.2 Uiout = [(−1)+(−1)+1] /4 = −1/4 U jin = −1/4 bi j = −3/10 e(i, j) 式中： 为符号网络的平均标注倾向，当 为负时说 明网络用户更倾向于给其他用户以负面评价； 为正 时，则表示网络用户有给其他邻居以正面评价的倾 向。设待预测边 两端的节点为 i 和 j， 表示 节点 i 发出的边符号的均值， 的值能够反映节 点 i 对相邻节点的局部标注特征：若节点发出的负 边数大于正边数，表示节点 i 给邻居以负面评价的 可能性大， 被预测为负的可能性就增加。同 理， 为 收到的边符号的均值，当 为负时表示 节点 收到了更多的负面评价，因此 被预测为 负的可能性就增加。图 3 给出了符号网络标注的局 部偏置示例，设 ，即符号网络全局有正面评价 的倾向，经计算可得： ， ，于是 ，此时边 的符号预 测结果将向负偏斜。 bi j 的值能够很好地反映待预测边两端节点的局 部标注行为和行为偏好，将标注偏好反映在预测的 目标函数，得到较基本模型更为精细的预测模型： min PT,Q∈Rk×n C = ∑ e(i, j)∈O l(Ai j −(bi j + ∑κ k=1 PikQk j))+ λ(∥P∥ 2 1 +∥Q∥ 2 1 +Uiout 2 +U jin 2 ) (4) rˆi j = bi j +(P TQ)i j 根据式 (4) 可知：节点 i 对节点 j 的符号可被预 测为 ，而式 (2) 表示的基本矩阵分解 rˆi j = (P TQ)i j Uiout 2 +U jin 2 模型得到的符号预测结果为 。因此，以 式 (4) 为目标函数的优化方法，不但考虑了符号网 的全局低秩特性还考虑了待预测边两端节点的局部 标注特征，与基本模型相似，添加了关于局部特征 项的正则化项 防止过拟合。 损失函数 l 可以有多种选择，本文选择 Square_ loss 为损失函数，于是优化目标函数可写成： min PT,Q∈Rk×n C = ∑ e(i, j)∈O Ai j −(bi j + ∑κ k=1 PikQk j) 2 + λ(∥P∥ 2 1 +∥Q∥ 2 1 +Uiout 2 +U jin 2 ) (5) ei j = Ai j −(bi j + ∑κ k=1 PikQk j) ∂C ∂Pi = −2ei jQj +2λPi ∂C ∂Qj = −2ei jPi +2λQj Uiout U jin 对式 (5) 给出的优化问题可以采用随机梯度下 降法进行求解，令 ，通过求梯 度以确定优化函数下降方向： ， ，同理也可求得目标函数对 、 的偏导数，由于沿梯度方向相反的方向下 降最快，于是得到如下迭代公式： Pi ← Pi +α(ei jQj −λPi) (6) Qj ← Qj +α(ei jPi −λQj) (7) Uiout ← Uiout +α(ei j −λUiout) (8) U jin ← U jin +α(ei j −λU jin) (9) B+ P TQ α α O(tmκ) t m κ κ 通过反复迭代并不断优化参数，使观测矩阵 A 与分解后矩阵 间的误差小于设定的误差 值即最终收敛。其中 为学习速度， 越大下降就越 快。随机梯度下降的时间复杂度为 ， 为迭代 并收敛次数， 为节点个数， 为秩数。由于符号网 络满足低秩特性，通常 值很小，且收敛较快，因此 采用随机梯度下降法求解最小化问题速度较快。 3 实验结果与分析 3.1 数据集描述 实验中的 3 个真实大型社会网络数据来自于斯 坦福大学的 SNAP2 项目，Epinions 给出了用户间 “who-trust-whom”的关系，Slashdot 是一个技术相关 的新闻网站，允许用户根据自身观点标记其他用户 为 friend/foe，Wikipedia 是维基百科申请管理员身 份的投票关系网，若一个用户被大多数其他用户同 意则当选为某一学科的管理员负责百科词条的维 护，若该用户未受到大多数其他用户的赞成票则选 举失败。表 1 给出了 3 个网络的统计特征。 表 1 的统计结果显示：3 个符号网络中正边占 比均在 75% 以上，而负边占比较少，互惠边 (recip￾rocal edges) 是指两用户间持有相同态度，这样的互 惠边在网络中占有一定比例，且互惠边中正边居 多，这与人们社会心理有关，当一个人讨厌另一个 i j ? + + − − − − e(i, j) 图 3 标注行为的偏置现象 Fig. 3 Bias behavior of signed edges ·440· 智 能 系 统 学 报 第 13 卷