GeNI：一种面向节点分类的网络表示学习方法.docx

? ? GeNI 一种面向节点分类的网络表示学习方法 ? ? 黄 亮 杨春明，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问题转化为词嵌入问题。在多个公开数据集上的节点分类任务中对本文提出的方法进行了验证。 1 网络表示学习方法 网络表示学习（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］充分利用网络中节点的标签信息，如维基