第3期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·439· 要条件是：网络中的节点能够被划分为两个子集， 同时矩阵填充的运算速度较慢，因此矩阵填充也经 每个子集内的所有边均为正，子集间的边均为负。 常用低秩矩阵分解来近似。 ⑧+ (B B + (a)关系模式1(b)关系模式2(c)关系模式3(d关系模式4 图1符号网中4种三角形关系模式 Fig.1 Four relationship patterns of triads in signed net- work 平衡网络的判别条件比较严苛，现实中很难找 到平衡网络的情形，因此Davis⑧放宽结构平衡的约 束提出了弱结构平衡理论，弱结构平衡理论规定： (a)符号网络示例 只要三角形模体中不存在两正一负的关系就构成弱 /011-10000 平衡，在该条件下，图l(a)、(b)、(d)代表的情形均可 1010-10-10 看作平衡的结构。当网络满足弱平衡结构时，节点 110-10-100 可以被分成k个子集，且子集内节点间的边全为正， -10-10 1-100 A= 子集间节点的边全为负。这类符号网也被称为K平 0-101000-1 衡网。 00-1-1.0011 1.3矩阵的秩与结构平衡 0-100010 1 根据弱结构平衡的定义，当符号网络满足k-平 0000-1110 (b)图2(a)对应的邻接矩阵 衡条件时，网络节点可以被分成k个子集，当对网络 节点按编号排序，邻接矩阵将是块对角矩阵。 0 11-1-1-1-1-1 图2(a)给出了一个满足弱平衡网的示例，图中 101-1-1-1-1-1 8个节点被分成3个子集，图2(b)为图2(a)对应的 110:-1-1-1-1-1 邻接矩阵A,若补齐图2(a)中缺失的边，使其成为完 -1-1-101-1-1-1 X= 全图，该图对应的邻接矩阵为块对角矩阵X,块内很 -1-1-1:10:-1-1-1 明显矩阵的秩Rank(X)=3小于矩阵的行列数8。根 -1-1-1-1-1011 据以上分析可知符号网络添加相应具有固定符号的 1 -1-1-1-1101 -1 边将使符号网络向完全K平衡网靠近。 -1-1-1-1110 因此可以把符号预测问题看作矩阵填充问题： (c)图2(a)对应的完全图邻接矩阵 已知被部分观测到的矩阵A,采用矩阵填充的方法 图2弱平衡结构与矩阵的低秩特性 找到矩阵X。此时符号预测问题可被看作优化问 Fig.2 Weakly balanced network and low-rank structure 题：填充矩阵中零值使得目标矩阵X的秩最小。该 2符号预测 问题可形式化描述为 min Rank(X) 当符号预测被近似为低秩矩阵分解问题时，邻 S.t. Xy=A,Ye(i,)∈O, (1) 接矩阵A可被分解为两个κ行列的矩阵P和Q,优 Xe{±1}，He(i,)年O 化目标是使PQ与A之间的误差最小，原矩阵可以 式(1)的目标函数是x矩阵的秩，即其奇异值构 被=(PQ,值填充，就是预测到的用户对用户 成向量的稀疏性，通常上述优化问题是NP难的，而 函数Rank()在矩阵谱范数单位球上的凸包络是矩 的评价。矩阵分解模型可被形式化地描述为 阵的核范数（即矩阵所有奇异值的和），因此可以用 (2) 凸的核范数最小化来近似秩最小化问题，文献[21] 表明：当被观测矩阵均匀抽样且O≥Cμnog2n)'成 式(2)中1为损失函数用于评价预测值与原矩 立时，矩阵X可以以1-n3的概率被恢复。但是对 阵间的误差，后两项为正则化项，用来防止过拟合 于符号网络来说，均匀抽样不容易做到，因为通过 损失函数，可根据具体问题进行选择。虽然上式是 4.1节数据描述可以看到符号网络80%的边为正， 非凸的，但是实践证明该方法在很多矩阵填充问题要条件是：网络中的节点能够被划分为两个子集， 每个子集内的所有边均为正，子集间的边均为负。 κ κ 平衡网络的判别条件比较严苛，现实中很难找 到平衡网络的情形，因此 Davis[8]放宽结构平衡的约 束提出了弱结构平衡理论，弱结构平衡理论规定： 只要三角形模体中不存在两正一负的关系就构成弱 平衡，在该条件下，图 1(a)、(b)、(d) 代表的情形均可 看作平衡的结构。当网络满足弱平衡结构时，节点 可以被分成 个子集，且子集内节点间的边全为正， 子集间节点的边全为负。这类符号网也被称为 -平 衡网。 1.3 矩阵的秩与结构平衡 κ κ 根据弱结构平衡的定义，当符号网络满足 -平 衡条件时，网络节点可以被分成 个子集，当对网络 节点按编号排序，邻接矩阵将是块对角矩阵。 Rank(X) = 3 κ 图 2(a) 给出了一个满足弱平衡网的示例，图中 8 个节点被分成 3 个子集，图 2(b) 为图 2(a) 对应的 邻接矩阵 A，若补齐图 2(a) 中缺失的边，使其成为完 全图，该图对应的邻接矩阵为块对角矩阵 X，块内很 明显矩阵的秩 小于矩阵的行列数 8。根 据以上分析可知符号网络添加相应具有固定符号的 边将使符号网络向完全 -平衡网靠近。 A X X 因此可以把符号预测问题看作矩阵填充问题： 已知被部分观测到的矩阵 ，采用矩阵填充的方法 找到矩阵 。此时符号预测问题可被看作优化问 题：填充矩阵中零值使得目标矩阵 的秩最小。该 问题可形式化描述为 min Rank(X) s.t. Xi j = Ai j,∀e(i, j) ∈ O, Xi j ∈ {±1},∀e(i, j) < O (1) X Rank(X) |O| ⩾ Cµ 4n ( log2n )2 1−n −3 式 (1) 的目标函数是 矩阵的秩，即其奇异值构 成向量的稀疏性，通常上述优化问题是 NP 难的，而 函数 在矩阵谱范数单位球上的凸包络是矩 阵的核范数 (即矩阵所有奇异值的和)，因此可以用 凸的核范数最小化来近似秩最小化问题，文献[21] 表明：当被观测矩阵均匀抽样且 成 立时，矩阵 X 可以以 的概率被恢复。但是对 于符号网络来说，均匀抽样不容易做到，因为通过 4.1 节数据描述可以看到符号网络 80% 的边为正， 同时矩阵填充的运算速度较慢，因此矩阵填充也经 常用低秩矩阵分解来近似。 2 符号预测 A κ n P TQ rˆi j = (P TQ)i j rˆi j i j 当符号预测被近似为低秩矩阵分解问题时，邻 接矩阵 可被分解为两个 行 列的矩阵 P T 和 Q，优 化目标是使 与 A 之间的误差最小，原矩阵可以 被 值填充， 就是预测到的用户 对用户 的评价。矩阵分解模型可被形式化地描述为 min PT,Q∈Rk×n C = ∑ e(i, j)∈O l(Ai j, ∑κ k=1 PikQk j)+λ∥P∥ 2 +λ∥Q∥ 2 (2) 式 (2) 中 l 为损失函数用于评价预测值与原矩 阵间的误差，后两项为正则化项，用来防止过拟合 损失函数，可根据具体问题进行选择。虽然上式是 非凸的，但是实践证明该方法在很多矩阵填充问题 A B C + + + A B C − − + A B C + + − A B C − − − (a) ڟ㈧Ὅᐻ1 (b) ڟ㈧Ὅᐻ2 (c) ڟ㈧Ὅᐻ3 (d) ڟ㈧Ὅᐻ4 图 1 符号网中 4 种三角形关系模式 Fig. 1 Four relationship patterns of triads in signed net￾work + + + + + + + 1 2 3 4 5 6 7 8 − − − − − − − (a) 符号网络示例 0 1 1 -1 0 0 0 0 1 0 1 0 -1 0 -1 0 1 1 0 -1 0 -1 0 0 -1 0 -1 0 1 -1 0 0 0 -1 0 1 0 0 0 -1 0 0 -1 -1 0 0 1 1 0 -1 0 0 0 1 0 1 =       0 0 0 0 -1 1 1 0 A 0 1 1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 1 1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 1 1 0 =       X (b) 图2(a)对应的邻接矩阵 (c) 图2(a)对应的完全图邻接矩阵 图 2 弱平衡结构与矩阵的低秩特性 Fig. 2 Weakly balanced network and low-rank structure 第 3 期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·439·