0 概述

网络表征学习是当前研究的热门课题之一^[1-3]，网络作为更加泛化的数据形式，其结构的复杂度远高于普通的网格结构。近年来，越来越多的研究人员关注网络或者图中节点的表征学习，其将图中的节点表示成低维的向量并应用到节点分类^[4]、社区发现^[5]、节点聚类^[6]、异常检测^[7]、链接预测^[8]和网络比对^[9]等学习任务中。Skip-Gram^[10]模型在自然语言处理的词向量表示中具有很好的效果。DeepWalk^[2]通过随机游走的方式将Skip-Gram应用到网络表征学习中能较好地表示网络结构。此后，随机游走的网络表征学习方法被广泛使用^{[1, 11]}。Skip-Gram模型实际上是一种近似方法，已被证明等效于矩阵分解^{[10, 12-13]}，该矩阵中的元素是单词对之间的点对互信息（Pairwise Mutual Information，PMI）^[10]。此外，在网络表征学习中通过随机游走的方式将图转换成序列也是一种近似方法，这些方法存在一个潜在的目标矩阵，而对该矩阵进行分解得到的低秩矩阵可以用作网络中的节点表示。同时研究人员也提出基于矩阵分解的网络表征学习方法^[14]，通过矩阵分解^[15]得到的低秩矩阵能够很好地保留潜在信息和消除噪声。

在网络分析中，可以认为网络中的某些节点扮演着相同或相似的角色^[16]，如网络中一些起桥梁作用的节点或者起中心作用的节点，这种角色信息多数是与结构等价有关，或者被弱化认为是规则等价^[17]，而这些具有相似角色的节点分布在整个网络中的各个区域中。针对上述问题，本文构建一个同时考虑局部邻接信息和角色信息的基于角色的矩阵分解（Role-Base Matrix Factorization，Role-MF）模型。根据角色信息提出基于角色的随机游走方法，据此推导出用于矩阵分解的目标矩阵，然后使用奇异值分解得到节点表征向量。

1 网络表征学习

给定网络$ G=\left(\mathcal{V}, \mathcal{E}\right) $，其中，$ \mathcal{V} $为节点集，$ \mathcal{E} $为节点之间的边集，网络表征学习目标是将节点转换为d维向量的映射$ h:\mapsto {\mathbb{R}}^{d} $。

现有网络表征学习的方法只能保留局部区域内节点的相似性。例如，Line^[3]集中于一阶和二阶的局部信息，DeepWalk的隐式目标矩阵是不同阶邻接矩阵的幂的加权平均值，Grarep^[14]的目标矩阵是不同阶邻居矩阵的拼接。虽然这些方法考虑了不同阶的信息或高阶信息，但是节点相似性的保留仍限于局部区域，以图 1（a）中的Karate club网络^[2]为例，任意选中一个节点（图中标三角形的节点），对DeepWalk的节点表征可以保留的相似性进行可视化，具体地，将DeepWalk上下文窗口大小设为10以获取十阶内信息，计算其对应的目标矩阵，然后取出选中节点的该行其他元素，该行元素衡量了选中节点与其他节点之间的相似性，并在图 1（b）中进行可视化（以选中节点为中心，按照与该节点阶数距离排列）。图中节点大小表示与选中节点相似程度，可以看到，虽然窗口大小为10，仅捕捉到三阶内的相似性，基于邻接矩阵或不同阶的邻接矩阵对于距离较远的节点难以捕捉到其相似性（如后面的结构等价）。

定义1（图同构映射）^[18]  给定两个图$ G $和$ H $，对于两个图节点集之间的一一映射$ f:{\mathcal{V}}_{G}\mathrm{\%}{\mathcal{V}}_{H} $，如果图$ G $中任意相邻的两个节点$ u $和$ v $与图$ H $中的节点$ f\left(u\right) $和$ f\left(v\right) $也相邻，则称$ f $是从$ G $到$ H $的同构映射。

定义2（图自同构映射）^[18]  一个图到它自身的同构映射$ f $称为图自同构映射。

定义3（结构等价）  对于图$ G $中两节点$ u $和$ v $，若存在图自同构映射$ f $，令$ u=f\left(v\right) $，则u与v结构等价。

定义4（k阶结构等价）  对于图$ G $中的节点$ u $，令$ {G}_{u}^{k} $表示由与节点$ u $距离小于等于k的节点及节点之间的边组成的子图。如果存在从$ {G}_{u}^{k} $到$ {G}_{v}^{k} $的图同构映射，则节点$ u $和节点$ v $具有k阶结构等价性，如度数相等的节点为一阶结构等价。

可以看出，结构等价定义较为严格，k阶结构等价性是本文给出的放松后的定义。两个节点具有结构等价性，那么必然具有k阶结构等价性，反之并不一定成立。本文的Role-MF使用提取角色特征来近似结构等价性，并说明结构等价的节点的角色特征是相同的。

定义5（角色特征）  图中的节点的角色特征为m维向量，m为设定的角色数，角色特征由节点度数等信息抽取得到，对于结构等价的节点u和v，满足其角色特征相等。

2 角色特征提取

本节描述节点角色特征提取的过程，m维向量$ {\boldsymbol{r}}_{i} $用于表示节点i的角色特征，其中m是预先设置的角色数。角色特征向量表明了节点在m个角色上的分布情况，该角色特征向量可以捕捉到网络中距离较远的节点之间的相似性，可以视为全局特征。为获得角色特征，本文根据初始特征对邻居节点的特征进行聚合和迭代得到新的特征，并且每次判断聚合得到的特征是否为新的特征，最终通过非负矩阵分解得到角色特征。初始特征为节点的度数和egonet特征，角色特征提取的整个过程如算法1所示。

算法1  角色特征提取

输入  图$ G=\left(V, E\right) $，节点数N，角色数目m，初始特征矩阵$ \boldsymbol{F}\in \mathbb{R}{}^{N\times 3} $，本文实验中初始特征矩阵的第i行是节点度$ {d}_{i} $以及二维egonet特征$ \mathrm{e}\mathrm{g}{\mathrm{o}}_{i} $的拼接

输出  角色特征矩阵$ \boldsymbol{R}\in \mathbb{R}{}^{N\times m} $

1.$ {\mathrm{F}}_{\mathrm{p}\mathrm{r}\mathrm{e}}=\mathrm{F} $//$ {\mathrm{F}}_{\mathrm{p}\mathrm{r}\mathrm{e}} $是上一次迭代的特征矩阵

2.repeat

3.$ {\mathrm{F}}_{\mathrm{n}\mathrm{e}\mathrm{w}}\leftarrow \left[\right] $//$ {\mathrm{F}}_{\mathrm{n}\mathrm{e}\mathrm{w}} $新一轮的特征矩阵

4.for $ {\mathrm{f}}_{\mathrm{c}}\mathrm{i}\mathrm{n}{\mathrm{F}}_{\mathrm{p}\mathrm{r}\mathrm{e}} $ do//$ {\mathrm{f}}_{\mathrm{c}} $是其N维列向量

5.$ {\mathrm{f}}_{\mathrm{c}}=\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{O}\mathrm{S}\mathrm{E}({\mathrm{f}}_{\mathrm{c}}, \mathrm{G}) $//根据G组合向量

6.if $ \mathrm{I}\mathrm{S}\mathrm{N}\mathrm{E}\mathrm{W}({\mathrm{f}}_{\mathrm{c}}, \mathrm{F}) $ then

7.$ {\mathrm{F}}_{\mathrm{n}\mathrm{e}\mathrm{w}}={\mathrm{F}}_{\mathrm{n}\mathrm{e}\mathrm{w}}\bigcup {\mathrm{f}}_{\mathrm{c}} $//$ \bigcup $代表拼接

8.$ \mathrm{F}=\mathrm{F}\bigcup {\mathrm{f}}_{\mathrm{c}} $//添加新的特征

9.$ {\mathrm{F}}_{\mathrm{p}\mathrm{r}\mathrm{e}}={\mathrm{F}}_{\mathrm{n}\mathrm{e}\mathrm{w}} $

10.unitl $ {\mathrm{F}}_{\mathrm{n}\mathrm{e}\mathrm{w}} $为空

11.非负矩阵分解计算角色信息$ \mathrm{F}\simeq \mathrm{R}{\mathrm{S}}^{\mathrm{T}} $

本文应用非负矩阵分解获得角色特征矩阵$ \boldsymbol{R}\in {\mathbb{R}}^{\mathrm{N}\times \mathrm{m}} $，其中第i行对应于节点i的角色特征向量。非负矩阵分解在KL散度距离下等价于概率潜在语义分析^[19]，故其分解得到的矩阵可作为角色的概率分布。具体来讲，分解的目标是在对两个参数矩阵的非负约束$ \boldsymbol{R}\ge 0, \boldsymbol{S}\ge 0 $下，最小化F和$ \boldsymbol{R}{\boldsymbol{S}}^{\mathrm{T}} $的距离，本文采用平方差距离，如式（1）所示：

$ \mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{s}}_{\mathrm{f}\mathrm{r}\mathrm{o}}\left(F, \boldsymbol{R}{\boldsymbol{S}}^{\mathrm{T}}\right)=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{f}{\left({F}_{ij}-{\left(\boldsymbol{R}{\boldsymbol{S}}^{\mathrm{T}}\right)}_{ij}\right)}^{2} $

(1)

根据网络结构，对特征聚合的过程如算法2所示。

算法2  网络中邻居特征聚合

Function $ \mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{e}(f, G) $

1.$ {\mathrm{f}}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{e}}\leftarrow \left[\right] $

2.for i=1，2，…，N

3.$ {\mathrm{f}}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{e}}\left[\mathrm{i}\right]=\mathrm{M}\mathrm{E}\mathrm{A}{\mathrm{N}}_{\mathrm{j}\in \mathrm{N}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\left(\mathrm{i}\right)}\mathrm{f}\left[j\right] $//邻居均值

4.return $ {\mathrm{f}}_{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{e}} $

当一轮迭代中没有新特征产生后，迭代停止。对于新特征的判断，这里使用线性回归的残差，残差低于阈值说明新特征几乎可以被原始特征完全拟合，于是不再作为新特征加入，具体计算如算法3所示。

算法3  特征判断

Function Isnew$ (f, G) $

1.$ \mathrm{M}=\mathrm{F}{\left({\mathrm{F}}^{\mathrm{T}}\mathrm{F}\right)}^{-1}{\mathrm{F}}^{\mathrm{\top }} $//计算投影矩阵

2.$ \mathrm{r}=\mathrm{f}-\mathrm{M}\mathrm{f} $ //计算残差

3.if $ \mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\left(\mathrm{r}\right)>{10}^{-15} $ then

4.return True

5.return False

本文提出的特征提取算法具有保留网络中结构相似性的能力。在算法1中，该过程是以迭代方式基于邻居节点完成的，根据第1节的基于邻居的结构等价相关定义，可以得到对于k阶结构等价的节点，k次迭代前每次迭代的特征都相同。因为结构等价是k阶结构等价的充分条件，对于结构等价的节点，算法1得到的特征始终相同。

3 基于角色的随机游走

基于随机游走的方法（如DeepWalk和Node2vec）仅考虑邻接信息，如式（2）所示，保留的相似性仅限于局部区域。本文提出基于角色的随机游走考虑全局信息。具体来说，$ {P}_{ij} $考虑表示当前处于节点i处，下一个访问到节点j的概率，由式（3）给出，概率正比于角色特征相似性和邻接矩阵中的元素$ {A}_{ij} $之和。

$ {P}_{ij}\propto {A}_{ij} $

(2)

$ {P}_{ij}\propto {A}_{ij}+\lambda \mathrm{s}\mathrm{i}\mathrm{m}\left({r}_{i}, {r}_{j}\right) $

(3)

$ \mathrm{其}\mathrm{中}，\mathrm{\lambda } $用于衡量角色信息与邻接信息的相对重要性，$ \mathrm{s}\mathrm{i}\mathrm{m} $代表相似性度量，使用基于内积的余弦相似性，$ \propto $代表正比关系，由于归一化常数，$ {P}_{ij} $不等于$ {P}_{ji} $。

4 目标矩阵和损失函数的推导

随机游走的网络表征学习方法基于Skip-Gram模型。文献[10]证明Skip-Gram等价于分解目标矩阵，其矩阵元素为两个单词间的点对互信息（PMI），PMI可以衡量两个变量的相关性，当两个变量独立时PMI等于0。式（4）定义了两个单词的PMI。具体地，将概率密度函数Pr（i）通过单词频率$ \frac{\#\left(i\right)}{\left|\mathcal{D}\right|} $来近似，联合密度函数Pr（i，j）通过两个词出现在相同的上下文中的频率$\frac{\#(i, j)}{|\mathcal{D}|}$来近似得到式（4）：

$ \mathrm{P}\mathrm{M}{\mathrm{I}}_{ij}=\mathrm{l}\mathrm{g}\frac{\mathrm{P}\mathrm{r}\left(i, j\right)}{\mathrm{P}\mathrm{r}\left(i\right)\mathrm{P}\mathrm{r}\left(j\right)}\approx \mathrm{l}\mathrm{g}\frac{\#\left(i, j\right)\cdot \left|\mathcal{D}\right|}{\#\left(i\right)\cdot \#\left(j\right)} $

(4)

其中，$ \mathcal{D} $是所有出现在同一上下文中的单词对集合，$ \# $代表计数。Skip-Gram的目标是使得节点表示向量和节点上下文表示向量的内积$ {\boldsymbol{e}}_{i}^{\mathrm{T}}{c}_{j} $与$ \mathrm{P}\mathrm{M}{\mathrm{I}}_{ij} $的距离最小。

在Skip-Gram的基础上，文献[12]证明了基于Skip-Gram模型的DeepWalk模型的目标矩阵$ \boldsymbol{M} $，如式（5）所示：

$ {M}_{ij}=\mathrm{l}\mathrm{g}\frac{{\left[\sum\limits_{t=1}^{T}{\left({\boldsymbol{D}}^{-1}\boldsymbol{A}\right)}^{t}\right]}_{ij}}{T} $

(5)

其中，$ \boldsymbol{A} $为邻接矩阵，$ \boldsymbol{D} $为度矩阵，T为上下文窗口大小，$ {\boldsymbol{D}}^{-1}\boldsymbol{A} $可以视为概率转移矩阵，该矩阵的t次幂可以视为t步转移概率矩阵。具体来讲，元素$ {\left({\boldsymbol{D}}^{-1}\boldsymbol{A}\right)}_{ij}^{t} $是从节点i刚好经过t步到节点j的概率。以类似的方式，本文使用式（3）中基于角色的转移概率计算方法，推导得到的目标矩阵如式（6）所示：

$ {O}_{ij}=\frac{{\left[\sum\limits_{t=1}^{T}{P}^{t}\right]}_{ij}}{T} $

(6)

根据目标矩阵得到损失函数如式（7）所示：

$ \mathrm{l}\mathrm{o}\mathrm{s}{\mathrm{s}}_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}\left(\boldsymbol{O}, \boldsymbol{E}{\boldsymbol{C}}^{\mathrm{T}}\right)=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}{\left({O}_{ij}-{\left(\boldsymbol{E}{\boldsymbol{C}}^{\mathrm{T}}\right)}_{ij}\right)}^{2} $

(7)

其中$ ，\boldsymbol{E}, \boldsymbol{C}\in {\mathbb{R}}^{N\times d}, \boldsymbol{E} $是节点表示矩阵，$ \boldsymbol{C} $是节点上下文表示矩阵。

本节通过推导基于角色的随机游走的目标矩阵得到Role-MF的损失函数。

5 基于角色的矩阵分解

本节描述基于角色的矩阵分解模型的整体过程。矩阵分解模型过程如算法4所示，首先根据邻接矩阵A和角色特征矩阵R来组合计算并归一化得到转移概率矩阵P，然后计算基于角色的目标矩阵O得到损失函数，之后应用矩阵分解框架^[20]计算节点表征向量。本文使用SVD矩阵分解来获取节点的表征向量，其可以消除噪声并被用于多个网络表征学习的多个工作^[21-23]。

算法4  基于角色的矩阵分解Role-MF

输入  邻接矩阵$ \boldsymbol{A} $，角色特征矩阵R，节点特征维度$ d $

输出  节点表示矩阵E$ \in \mathbb{R}{}^{N\times d} $

1.计算行归一化角色特征矩阵$ {\mathrm{R}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}=\mathrm{r}\mathrm{o}\mathrm{w}\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\left(\mathrm{R}\right) $

2.计算未归一化转移矩阵$ {\mathrm{P}}_{\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}=\mathrm{A}+\mathrm{\lambda }{\mathrm{R}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}{\mathrm{R}}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{\mathrm{T}} $

3.计算概率转移矩阵$ \mathrm{P}=\mathrm{r}\mathrm{o}\mathrm{w}\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{z}\mathrm{e}\left({\mathrm{P}}_{\mathrm{u}\mathrm{n}\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}\right) $

4.计算目标矩阵$ \mathrm{O}=\frac{\sum\limits_{\mathrm{t}=1}^{\mathrm{T}}{\mathrm{P}}^{\mathrm{t}}}{\mathrm{T}} $

5.计算保留前$ \mathrm{d} $奇异值分解$ \mathrm{O}={\mathrm{U}}_{\mathrm{d}}{\mathrm{\Sigma }}_{\mathrm{d}}{\mathrm{V}}_{\mathrm{d}}^{\mathrm{T}} $

6.计算节点表示矩阵$ \mathrm{E}={\mathrm{U}}_{\mathrm{d}}{\mathrm{\Sigma }}_{\mathrm{d}}^{-1/2} $

6 实验结果与分析 6.1 数据集

本文在4个数据集上进行了实验，包括可视化结构等价的Barbell数据集和3个节点分类的数据集。Barbell数据集由两个团和一条路径组成。BlogCatalog数据集为BlogCatalog网站数据，边代表博主的关注关系，节点类别为博主的兴趣类别，兴趣相似的博主倾向于互相关注使得局部邻接信息较为重要。Flight Network为两个机场网络数据，边代表机场之间存在航班，节点类别为机场的航班频繁程度，航班频繁程度与邻接信息关系较弱且机场可能较为分散，使得具有一定全局信息，网络的具体描述如表 1所示。

6.2 结构等价可视化实验

在如图 2（a）所示的Barbell图中，根据第1节的定义对结构等价的节点用相同的颜色表示。目标是希望算法学习的节点表征向量可以保存这种结构等价性，将向量维度设置为2以便展示在二维平面上。对于本文提出的基于角色信息的矩阵分解（Role-MF），如图 2（d）所示，结构等价的节点近似被映射到相同的二维空间（在图中重合），因此Role-MF可以很好地保留结构等价性。从图 2（b）可以看出，在DWMF（DeepWalk所对应的矩阵分解）中，两团深圆色节点在网络中距离较远，其在表征空间中距离也较远，而正方形节点在图中比较接近，在表征空间中也较为接近，故其保留了局部邻域信息，但是无法捕获结构等价性性。如前所述，与DWMF相比，DeepWalk是一种近似方法，由图 2（c）中可见，其节点相似性的保留可以看作DWMF的近似。

6.3 节点多标签分类

本文节点多标签分类任务使用BlogCatalog数据集，所有对比方法表征维度设置为128，对于多标签分类任务，这里使用Scikit-learn实现的逻辑回归模型。分类训练比例设置为90%和10%，重复10次实验取平均值，选取Macro-F1和Micro-F1作为评价标准，评价结果如表 2所示。对比算法的实验采用原论文中的设定。从表 2可以看出，Role-MF同时考虑局部信息和全局信息，具有更好的性能。其中，DWMF、DeepWalk、Node2Vec和Line主要关注于一阶及二阶信息^[1-3]等局部信息。如上所述，该数据集中局部邻接信息较为重要，可取得较好效果，而GraphWave仅考虑结构等价^[24]，Struct2Vec关注于度信息^[11]，缺少局部信息使得其表现不佳。此外，可以看出DWMF^[13]比DeepWalk^[2]效果更好，因为DeepWalk通过随机游走来近似目标矩阵，而DWMF通过分解目标矩阵得到节点表征，从另一方面验证了矩阵分解的有效性。

6.4 节点多类别分类

节点多类别分类任务使用Flight Network的两个数据集，在所有对比方法中，表征维度设置为16，分类训练比例为10%~90%，重复10次实验将准确率的平均值作为评价标准，结果如图 3所示。如前所述，这两个数据集上具有一定全局信息，从图 3可以看出，通过同时考虑全局信息与局部信息，Role-MF取得了更优的结果且准确率有较大提升。同样地，因为DeepWalk是DWMF的近似，DWMF通过矩阵分解取得比DeepWalk更优的结果，Node2Vec和Line未考虑到Flight Network中具有的全局信息，实验结果与DWMF和DeepWalk较为接近，而GraphWave则完全考虑结构等价，过于严格，在真实网络中效果不佳。

6.5 链路预测

链路预测任务使用BlogCatalog数据集，对于数据原图去除30%的连边，剩下的图来获取节点表征。所有去除的边作为正样本，每条正样本随机选取5条不存在的边作为负样本合为链路预测的数据集。节点表征维度设置为64，节点特征拼接后采用逻辑回归分类器，训练比例设置为10%和90%，采用AUC和F1值作为评价指标，重复10次实验将平均值记录在表 3中。从表 3可以看出，Role-MF同时考虑局部信息和全局信息具有最好的性能。在链路预测实验中，度数信息也起到作用，例如两个度数都较高的节点倾向于相连，故可以看到Struct2vec取得较好的效果。同样地，DWMF比近似方法DeepWalk取得了更优的结果，考虑二阶信息的Node2Vec和Line未考虑到全局信息效果较为接近，Graphwave则完全考虑结构等价效果不佳。

7 结束语

当前的网络表征学习方法忽略了全局结构等价信息，本文基于角色的随机游走方法，推导出其目标矩阵，构建基于角色的矩阵分解（Role-MF）模型，利用奇异值分解获取节点表示矩阵。该模型可以同时捕捉到局部信息和全局信息，并有效地进行融合。实验结果表明，在不同训练比例下，Role-MF模型AUC和F1值在真实数据集上均取得了更优的分类与预测效果。下一步将通过计算梯度等方式并基于全局信息和局部信息进行可视化研究。