黄 亮 杨春明，2
（1.西南科技大学计算机科学与技术学院 四川绵阳 621010；
2.四川省大数据与智能系统工程技术研究中心 四川绵阳 621010）
网络表示学习（Network representation learning，NRL）又称图表示学习方法，是一种将节点从高维、稀疏的网络空间映射到稠密、低维的向量空间的方法，其基本假设是原始空间中相似的节点在低维嵌入空间中处于相近的位置。基于此假设，NRL得以用低维稠密的向量来表示该节点的特征信息，并用作下游机器学习任务的输入，如节点分类［1］、链接预测［2］、异常检测［3］和个性化推荐［4］等，以减小下游任务的计算量。
NRL主要通过学习节点的网络拓扑结构获取嵌入向量，目前已在链接预测中取得很好的效果，但在节点分类任务中效果不佳。如文献［5］表明多种经典NRL方法在PPI，COOC等网络上的链接预测任务的精度可达90%，而在节点分类任务上的最高精度值只有48%。节点的类别信息除了与网络拓扑结构有关外，还与该节点在网络中的重要程度、网络所属领域有较强的相关性。如社交网络中，拥有相同兴趣爱好的人们通常相互链接在一起。欧洲飞机航线网络中，拥有相同活跃等级的机场却可能在网络的不同位置［6］。社交网络倾向于通过节点局部特征信息得到相似的节点；
航线网络倾向于从节点的全局特征信息中获得相似节点。目前的NRL方法主要采用随机游走或遍历的方式获取节点序列，没有考虑同一网络中不同节点重要性的区别。
针对上述问题，文章提出了一种考虑节点重要性的用于节点分类的图表示学习方法GeNI（Graph embedding based on node importance）。GeNI首先通过度、集聚系数等节点重要性指标对节点预分类以区分复杂网络中不同结构类型的节点，然后将分类结果作为先验知识，对结构类型不同的节点采用不同的带偏游走策略获得节点序列，并基于DeepWalk思想，将NRL问题转化为词嵌入问题。在多个公开数据集上的节点分类任务中对本文提出的方法进行了验证。
网络表示学习（NRL）又称图表示学习方法。图表示学习方法通常可分为基于矩阵分解、随机游走和深度学习的方法。
基于矩阵分解的方法以网络结构信息为基础构建矩阵作为模型输入，通过对矩阵降维，得到低维的节点向量表示。如LLE（Locally linear embedding）［7］通过其邻居节点的线性组合来近似得到节点表示；
LE（Laplace eigenmaps）［8］通过平滑项方式，使原始空间中两个相似节点在低维向量空间中有相近的表示；
Graph factorization［9］通过在均方误差基础上添加一个L2正则项重建图的邻接矩阵，同时将时间复杂度控制在O（｜E｜）。
基于随机游走的方法首先通过遍历网络为节点构建指定长度的节点序列，再通过自然语言处理方法将节点序列看作一个个“句子”进行训练，最终得到节点嵌入向量。DeepWalk从一个顶点出发，随机移动到一个邻居节点，并将邻居节点作为新的起始节点，如此循环若干步，得到一条游走路径，作为该节点的“句子”，再用word2vec得到嵌入结果［10-11］。虽然DeepWalk在获取节点序列过程中采用随机方式获取每一条节点，极大降低了模型复杂度，但随机性较强使模型难以区分不同领域网络之间的差异性，准确做出应对处理。为区分不同领域网络之间的差异性，Node2vec［12］在节点序列采集阶段引入深度优先和广度优先搜索两个概念。对于不同类型网络，Node2vec通过p，q两个参数控制游走方向来获取下一跳节点，得到指定长度的节点序列，再通过skip-gram模型获取节点对应的嵌入向量［13］。
基于深度学习的方法采用复杂神经网络模型，具有强大的学习能力和广泛的适应性。SDNE方法［14］使用深度自动编码器来保持网络一阶和二阶邻近度，利用高度非线性函数获得嵌入；
DNGR方法［15］结合了随机游走和深度自动编码器，使用随机游走模型生成概率共现矩阵，将该矩阵转化为PPMI（Positive pointwise mutual information）矩阵，输入到自动编码器中得到嵌入。其中PPMI矩阵保证了自动编码器模型能够获取更高阶的近似度；
GCN方法［16-17］通过在图上定义卷积算子降低了模型在大型稀疏网络中的计算代价。模型迭代聚合了节点邻域嵌入，使用前一次迭代中的嵌入表示该节点的全局邻域。
除了利用节点的结构特征信息，有学者提出使用节点属性特征信息来学习图嵌入。TADW方法［18］提出一个新的学习节点特征方法，通过加入节点文本特征信息，与结构特征相结合，共同学习图嵌入；
MMDW方法［19］充分利用网络中节点的标签信息，如维基百科网络中，顶点可能被标记成物理、天文、人物等，并在TADW的基础上加入SVM（Support vector machines），增强不同类别顶点向量的差异，提升网络中节点分类效果。
矩阵分解方法简单利用网络的结构信息，定义节点向量表示；
深度学习方法虽然可以更准确地学习节点的特征，但由于模型复杂度增加，导致时间复杂度高的缺点突出，这类方法在大型网络中应用十分耗时；
综合节点结构与属性特征的方法需要为节点定义相应的数据标签，但在实际工作中，大量数据标签往往具有较高的获取条件；
几种经典基于随机游走的图表示方法中，DeepWalk对于所有应用场景，采用完全随机的节点采集策略。实际情况中，不同网络结构特征往往不完全相同，DeepWalk难以实现为不同网络构建其特有的节点采集策略。Node2vec对其进行了优化，对于不同网络可以定义对应的节点采集策略，但在结构复杂的大型网络中，同一网络的局部结构特征也存在较大差异，Node2vec忽略了这种差异，对于网络中所有节点，采用相同节点采集策略对节点进行序列采集。但在节点分类任务中，对于同一网络下不同结构类型的节点，采用对应的节点采集策略有利于更准确获取与源节点紧密相关的序列，从而提升节点分类效果。因此，在节点采样阶段，需要区分网络中不同结构类型的节点。
2.1 GeNI模型定义
给定网络G＝（V，E），网络表示学习方法将网络中每个节点vi分别映射为一个低维的特征向量ϕ（vi）∈Rd，其中，d≪｜V｜，且要求两个相似的节点映射后的向量距离相近；
否则，映射后的向量距离较远。符号定义如表1所示。
表1 符号定义Table 1 Definition of symbols
令G＝（V，E）为给定网络，f：V→Rd是从节点到其特征表示的映射函数。d是一个参数，用于指定特征表示的维数；
f是大小为｜V｜×d的参数矩阵。对于每个源节点vi∈V，将NS（vi）∈V定义为通过邻域采样策略S生成的节点vi的网络邻域。
GeNI模型的优化目标是最大化邻居节点出现的概率，如何定义邻居节点非常重要，节点的采样策略也直接影响邻居节点的获取。GeNI模型最大化节点vi邻域NS（vi）的对数概率，起始目标函数如式（1）所示：
为使目标函数可解，引入条件独立性和特征空间对称性两个标准假设。条件独立性假设认为各个邻居节点之间相互独立，如式（2）所示：
特征空间对称性认为节点与其邻居节点在特征空间中的影响是相互的，故可将每个节点-邻节点建模成一个个softmax单元，并将其特征信息以点乘方式实现参数化，如式（3）所示：
基于以上假设，优化后最终目标函数如式（4）所示：
其中，Zvi如式（5）所示：
对于大型网络而言，Zvi计算成本较高，为降低计算成本，使用负采样对其进行近似。
2.2 GeNI采样策略
给定节点ui，根据设定的采样策略生成（抽样）它的邻节点集合N（ui）。在已有算法中，广度优先采样（BFS：Breadth-first sampling）与深度优先采样（DFS：Depth-first sampling）两种采样方法发挥了重要作用。BFS倾向于对周围节点采样，获取节点的局部结构信息；
DFS倾向于探索网络的更深处，获得网络的全局结构信息。
Node2vec在节点采样阶段定义了一种基于二阶随机游走的采样策略。在不同网络中，该策略结合BFS和DFS捕捉网络的局部和全局结构信息。但同一网络下节点类别分布规律并不唯一。如图1所示的网络，节点颜色表示节点的类别，两种不同颜色的箭头表示节点1、节点2在随机游走阶段中的最优轨迹。从图中可以发现节点1趋向于向周围的节点游走，而节点2趋向于向网络更深处游走，对于网络中完全不同的节点分布情况，现有的图表示学习方法大多难以有效解决这类问题。
图1 节点1、节点2在随机游走中的最优轨迹Fig.1 The optimal routes of nodes 1 and 2 in random walk
在Node2vec中，当模型想要以节点1的特征分布为标准设计游走策略时，节点2的游走路径就可能变为如图2（b）所示；
当模型想要以节点2的特征分布为标准设计游走策略时，节点1的游走路径就可能变为如图2（a）所示。两种情况都会造成网络结构特征极大缺失。
图2 节点1、节点2在随机游走中可能的轨迹Fig.2 The possible routes of nodes 1 and 2 in random walk
由于网络中节点的局部分布规律并不相同，导致单一采样策略难以准确获取与节点紧密联系的节点序列。为丰富节点采样方式，提高模型的灵活性，GeNI在采样前统计节点重要性信息并结合预分类策略P对节点进行预处理：对于网络中每一个节点，GeNI首先统计节点在网络中的重要性特征，根据统计结果实现每一个节点的预分类，再对不同类别节点，设定不同采样策略。以节点重要性指标“度”作为节点预分类标准设计了模型GeNI.De1和GeNI.De2；
以“集聚系数”指标作为节点预分类标准设计了模型GeNI.Cl。3种模型的主要区别如下：（1）节点预处理阶段时节点预分类标准不同。GeNI.De1和GeNI.De2以节点“度”作为预分类标准；
GeNI.Cl以节点“集聚系数”作为预分类标准。（2）节点预分类的类别总数不同。GeNI.De1和GeNI.Cl将网络中节点分为两类，对不同类别节点采用不同的采集策略。为了探究同一网络中更多采样策略对节点序列获取的影响，GeNI.De2将网络中节点分为三类，对不同类别节点采用不同的采集策略。
2.3 节点重要性指标
2.3.1 度
节点度用来表示与该节点直接相邻的邻居数目［20］，网络中任意节点i的度k（i）如式（6）所示：
节点度指标直接反映该节点一阶邻域的密集程度，同时也展示了该节点对邻居节点的直接影响力。例如在社交网络中，度值更大的节点拥有更大的影响力，周围节点往往通过它来获取相关信息。
2.3.2 集聚系数
节点度可以反应节点与周围节点直接建立联系的能力，但不能反应该节点邻居之间的关系。实际上，节点邻居之间建立的联系越密集，节点邻居与该节点同类别的可能性就越大［21］。集聚系数可以很好评估这种可能，它描述了网络中节点邻居之间互为邻居的比例，具体表达如式（7）所示：
其中：k（i）表示节点的度；
ei表示节点i与任意两个邻居之间形成三角形的个数，也就是节点邻居相互连接的个数。通过这种方式，可以直观反映出节点邻居之间的相关程度。
2.4 随机游走与搜索偏差
给定源节点vi，模拟一个长度为l的随机游走。l是源节点vi对应节点序列的长度，是模型参数之一，取值与网络规模、密度有关（通常在［10，20］之间进行选择），恰当的l可提升最终嵌入向量的质量。ci表示在游走中的第i个节点，通过式（8）生成：
其中：τvx是未归一化的节点v和x间的转移概率；
Z是归一化常量。GeNI采用与Node2vec相近的带偏随机游走方法。GeNI定义了多个二阶随机游走。GeNI.De1与GeNI.Cl定义了两种随机游走方式，使用4个参数，p1，p2，q1，q2来指导随机游走；
而GeNI.De2定义了3种随机游走方式，使用6个参数，p1，p2，p3，q1，q2，q3来指导随机游走。GeNI.De1中p1，q1为一组节点的采样策略参数；
p2，q2为另一组节点的采样策略参数，它们有着相同的定义：假设一个节点被分配到p1，q1所对应的组，对该节点进行采样。节点穿过边（t，v），停留在节点v上，下一步节点采集策略会计算该节点在v上的转移概率τvx，设定未归一化转移概率为τ＝αp1q1（t，x）·wvx，其中αp1q1（t，x）的具体表示如式（9）所示：
其中，dtx表示节点t和x上的最短路径距离。同理，对于p2，q2组下节点根据参数p2，q2计算对应的转移概率。
2.5 GeNI.De1算法
如2.2节所述，3种模型的算法实现只存在局部差异，考虑到模型伪代码篇幅过长，本文仅给出具有代表性的GeNI.De1模型的伪代码，GeNI.De1算法如表2所示。
表2 GeNI.De1模型算法Table 2 GeNI.De1 model algorithm
GeNI.De1算法的输入参数中，S1，S2是GeNI.De1模型中两种采样策略对应的转移概率τ1，τ2归一化后的结果。AttributeClassfication（）中J表示对网络中节点“度”的统计汇总结果，用于模型预分类；
预分类策略P在2.2节有详细描述。主函数GetFeatures（）中子函数GeNIWalk（）在伪代码函数2中定义；
StochasticGradientDescent（）在2.1节中定义。
为了验证GeNI方法的实际效果，实验在不同领域的公开数据集上进行验证，并与多个图表示学习方法进行对比。在所有模型上，首先利用无监督的方法学习图嵌入，然后在节点分类任务上进行评估，通过分类效果判断学习嵌入向量的质量。在节点分类任务中，为比较不同比例训练数据对模型性能的影响，实验分别选取30%～80%的数据集训练分类器，然后在测试集上进行测试。实验对每种情况重复10次，取其平均值作为最终的实验结果。
3.1 实验设定
实验采用无监督方法学习图嵌入，然后将嵌入向量应用在节点二分类或多分类任务中。实验采用Logistic regression分类方法训练分类器，并用microF1和macroF1两个评测指标作为算法性能的评测标准。两个评测指标具体表达式如下：
其中：i为类别总数；
TPi表示类别i中样本分类正确的样本总数；
FNi表示不属于类别i的样本被错误预测为类别i的样本总数；
FPi表示类别i中样本分类错误的样本总数；
microF1i表示类别i下的microF1值。
3.1.1 数据集
实验选定图表示学习领域的4个公开数据集进行评测，这些数据集规模大小各异、来自多个不同领域，它们包括Europe-airports，Wiki，Node2vec PPI和Mashup PPI。实验选定这4个数据集旨在验证GeNI在不同领域不同规模网络下节点分类任务的有效性。这些数据集中只包含节点的结构特征，不含属性特征。各个数据集的详细信息如表3所示。
表3 数据集的相关统计信息Table 3 Relevant statistics of dataset
Europe-airports：一个机场流量数据集，节点表示机场，边代表两个机场之间存在航班，标签表示机场对应的活跃等级。
Wiki：一个单词共现词数据集，节点表示词，边代表两个词之间存在联系，标签为每个词对应的词性。数据集来自文献［11］中Wiki数据集的一部分。
Node2vec PPI：一个具有功能注释的蛋白质网络子图，节点代表蛋白质分子，边代表蛋白质分子之间存在相互作用，标签为蛋白质分子对应的功能注释。数据集来自文献［11］。
Mashup PPI：一个具有功能注释的蛋白质网络数据集，节点、边和标签的含义与Node2vec PPI数据集中相同，区别是数据集规模更大。数据集来自文献［5］。
3.1.2 对比方法
实验在节点标签分类任务上进行评测，对于这项任务，采用以下4种方法作为对比方法，用以评价GeNI的有效性。
LINE（Large-scale information network embedding）：该方法研究了如何将结构信息从大型网络嵌入到低维向量，通过学习节点之间的一阶、二阶邻域相似度，可以应用在大型信息网络中。
DeepWalk：该方法对于所有网络场景，直接通过随机采样的策略来学习节点特征。
Node2vec：该方法在DeepWalk基础上进行优化，引入了BFS和DFS两个带偏游走策略，更灵活地采集节点序列，学习节点特征。
SDNE：该方法从空间结构相似度的角度定义节点的相似度，用于捕捉一些场景中两个不是近邻的节点也可能拥有较高的相似性的同类别节点。
3.1.3 参数设定
为了确保实验结果的有效性，每种对比方法参数的设定均按照方法所在论文中提供的最优参数进行设定。词向量维度均为d＝128。由于GeNI也需要参数控制节点采样，为维持实验的公正性，参数设定范围与Node2vec保持一致，均在｛0.25，0.5，1，2，4｝中选取参数设定。
3.2 基于节点“度”的图表示学习方法
在网络分析中，“度”是复杂网络中评判节点重要性最直观的指标。无向图中节点“度”的定义可以简单理解为节点邻居的数目，一个节点度值越大，该节点在网络中越重要。GeNI.De1与GeNI.De2模型正是以节点度作为预分类标准。为更清晰表述不同预分类标准对节点特征学习的影响，本节集中分析以节点“度”为预分类标准时的实验结果，以“集聚系数”为分类标准的GeNI.Cl模型将在3.3节分析总结。
表4-表7报告了在Europe-airports，Mashup PPI，Node2vec PPI和Wiki数据集上的分类microF1值和macroF1（粗体表示所有方法中最好的）。实验结果表明除了在Europe-airports上，GeNI.De1与GeNI.De2比所有基线方法效果要好。证明了在同一数据集中使用“度”作为预处理标准可以更有效地采集节点序列，进而提升下游节点分类效果。
表4 在Europe-airports数据集上的micro F1和macro F1值（待续）Table 4 Micro F 1 and macro F 1 scores in Europe-airports dataset（to be continued）
表7 在Wiki数据集上的micro F1和macro F1值Table 7 Micro F1 and macro F 1 scores in Wiki dataset
续表4 在Europe-airports数据集上的micro F1和macro F1值Table 4 Micro F1 and macro F 1 scores in Europe-airports dataset（continued）
表5 在Mashup PPI数据集上的micro F1和macro F1值Table 5 Micro F1 and macro F 1 scores in Mashup PPI dataset
表6 在Node2vec PPI数据集上的micro F1和macro F1值Table 6 Micro F 1 and macro F 1 scores in Node2vec PPI dataset
从表4-表7中可以观察到：（1）在所有数据集上，GeNI.De2较GeNI.De1整体表现出更好的效果，这是由于复杂网络中节点本身的分布特征更加多样，GeNI.De2可以更准确地捕捉到同类别的节点作为该节点的节点序列，以达到学习节点结构特征的目的。（2）在Europe-airports数据集上，SDNE效果最优，GeNI模型并没有取得最好的分类效果。这与网络本身类别分布相关，Europe-airports网络主要以全局结构特征作为类别区分标准，SDNE更充分捕捉相关特征，因此拥有更好的分类效果。GeNI虽然也能学习节点全局结构特征，但为了保持与对比方法的一致性，将节点序列长度控制在20，使得GeNI主要考虑局部结构特征，但较Node2vec仍能表现出更好的分类效果（表4）。（3）在Wiki和Node2vec PPI数据集上，GeNI.De2和GeNI.De1模型在不同比例训练集上较其他对比模型均表现出更好的分类效果。当训练集比例为80%时，GeNI.De2在Wiki数据集中比最好基线方法的macroF1值提升了1.6%；
在Node2vec PPI数据集中比最好基线方法的macroF1值提升了0.7%。（4）在Mashup PPI数据集上，仅选取训练集比例为80%的情况进行实验，这是由于实验在Europe-airports，Wiki，Node2vec PPI等数据集上已经得出不同比例训练集时所对应的结论。实验结果表明GeNI模型在大规模数据集上的分类效果（节点数量万级，边10万级）较基线模型仍有稳定提升。
3.3 基于集聚系数的图表示学习方法
为了探究更多节点重要性指标对NRL的影响，提出了一种以集聚系数替代节点度的NRL方法GeNI.Cl。集聚系数是一个评判网络中节点集结成团程度的指标。通过计算集聚系数，可以更准确地识别网络中一些关键性节点。通过在Europe-airports，Wiki和Node2vec PPI数据集上进行节点分类任务实验验证GeNI.Cl方法的有效性。图3为GeNI.Cl方法进行节点分类任务的效果图。其中，横坐标代表不同比例训练集，纵坐标代表microF1和macroF1两种评测指标。
图3 GeNI.Cl在不同网络上节点分类任务效果图Fig.3 The comparison of node classification tasks of GeNI.Cl on different networks
从图3所示的分类任务效果图可以看出：（1）在不同数据集、不同训练比例数据下GeNI.Cl的分类效果均优于Node2vec。在Europe-airports数据集中，不同比例训练集下提升明显。在Wiki和Node2vec PPI数据集中，训练比例超过70%后分类效果提升明显。实验表明在节点分类任务中，以集聚系数作为预处理标准能够更有效地学习节点特征信息。（2）3种数据集中，GeNI.Cl的整体分类效果优于GeNI.De1，在Europe-airports数据集中，GeNI.Cl的整体分类效果优于GeNI.De2。实验表明在节点分类任务中，以集聚系数作为预处理标准能够比以度作为预处理标准获得更好的效果。
通过将节点统计特征作为先验知识，为统计特征不同的节点设计相应的游走策略，提出一种融合节点统计特征的图表示学习方法GeNI。实验结果表明，GeNI在不同领域、不同规模的网络下进行节点分类任务的效果优于大部分对比方法，较其他方法表现出更好的适应能力。GeNI的高灵活性使其高效保留节点的网络拓扑信息，从而提升图嵌入质量。
猜你喜欢集上向量分类向量的分解新高考·高一数学(2022年3期)2022-04-28GCD封闭集上的幂矩阵行列式间的整除性四川大学学报（自然科学版）(2021年6期)2021-12-27分类算一算数学小灵通(1-2年级)(2021年4期)2021-06-09聚焦“向量与三角”创新题中学生数理化(高中版.高考数学)(2021年1期)2021-03-19基于互信息的多级特征选择算法计算机应用(2020年12期)2020-12-31分类讨论求坐标中学生数理化·七年级数学人教版(2019年4期)2019-05-20教你一招：数的分类初中生世界·七年级(2017年9期)2017-10-13说说分类那些事少儿科学周刊·儿童版(2017年3期)2017-06-29向量垂直在解析几何中的应用高中生学习·高三版(2016年9期)2016-05-14向量五种“变身” 玩转圆锥曲线新高考·高二数学(2015年11期)2015-12-23