信息网络表示学习方法综述
来源:用户上传
作者:鲁军豪 许云峰
摘要：网络表示学习方法将信息网络表示为低维稠密携带网络节点特征信息的实数向量，应用于下游机器学习任务的输入，随着机器学习与深度学习的发展，网络表示学习拥有强大的建模能力且应用广泛。对网络表示学习方法、应用进行了归纳总结。首先，对当前国内外网络表示学习方法进行梳理归类，分为传统方法、基于网络结构的嵌入、融入属性信息的嵌入，以及基于谱域的图卷积、基于空间的图卷积和图attention网络，按类别对各类模型详细阐述，对比模型之间的适用性和方法特点;其次，介绍了网络表示学习的相关应用，包括推荐系统领域、生物医药领域等，整理常用的数据集、开源实现的表示学习模型和强大的图深度学习库供研究者参考调用;最后，对网络表示学习的发展趋势进行了总结与展望。未来可在深层的图神经网络学习、动态和异构网络的表示、网络模型的泛化能力等方面继续开展研究。
关键词：计算机神经网络;网络;表示学习;图神经网络;图卷积;图深度学习库
中图分类号：TP311.13 文献标识码：A doj：10.7535/hbkd.2020yxO2004
网络是表达实体与实体之间联系的一种数据形式，广泛存在于人们的生活中，例如：人们与周边人形成的社交网络;论文作者之间形成的引文网络;生物医药中的蛋白质网络和药物网络;甚至人脸扫描的点云网络等。网络表示学习是衔接网络与原始数据与网络应用任务的桥梁，如图1所示，网络表示学习方法从复杂的信息网络中学习每个实体的特征信息，将其表示为低维稠密的实数向量，以应用于下游的机器学习任务。
网络中蕴含丰富信息，对社会生产中的信息网络进行分析与研究具有非常高的学术与应用价值。例如，在电子商务中，一个基于信息网络的学习系统能够利用用户和产品之间的交互做出准确推荐;在化学研究中，分子被建模为图网络，它们的生物活性需要被识别，以发现药物;在社交网络中，对网络进行社区划分与链路预测，可对客户人群进行分组与推荐。神经网络与深度学习在欧几里德数据上取得了很大成功，但信息网络属于不规则的非欧几里德数据，如何进行有效地信息提取成为一个值得研究的课题。最初的网络表示学习方法受到经典降维技术的影响，主要集中在矩阵分解方法上，随后受到Word2vec技术和DeepWalk的启发，涌现出许多利用随机游走产生节点序列并输人给skip-gram模型生成节点嵌人的表示方法。随着深度学习的兴起，许多研究者将卷积与self-attention机制引入网络表示中，在网络的谱域与空间域进行端到端的网络计算，取得了优异的任务效果。
目前对包括图神经网络的网络表示学习综述数量有限，BRONSTEIN等给出了非欧几里德领域的深度学习方法的概述，包括图和流形，但忽略了几个重要的基于空间的方法。WU等给出图神经网络领域的模型介绍，但缺少了对传统方法以及基于随机游走方法的介绍。涂存超等的综述中仅简单提到谱域的图卷积模型，缺少对基于空间的图卷积以及图atten-tion网络的介绍。本文系统并详细地介绍了网络表示学习相关方法模型，将其分为2大类，分别为网络节点嵌入方法和图神经网络方法，细分为6个类别，分别是传统方法、基于网络结构的嵌人、融人属性信息的嵌入，以及基于谱域的图卷积、基于空间的图卷积和图attention网络，并对比各模型的适用性和优缺点，为网络表示学习领域的学者提供全面的综述参考。同时，本文整理了开源实现的表示学习模型和图深度学习库，以及常用的数据集供研究者参考使用。网络表示学习方法类别如图2所示。
本文给定了表示学习方法公式中常见的符号定义，对网络表示学习方法进行详细的阐述，整理对比了各模型的适用性与优缺点，给出了基础数据集和开源实现的表示学习模型和图深度学习库，对网络表示学习的应用进行了介绍，并对网络表示学习的未来进行了展望。
1网络表示学习的基本定义
网络表示学习公式中常见的符号及其含义如表1所示。
2网络表示学习方法
网络表示学习方法将非欧几里德结构的网络节点表示为低维稠密的特征向量，供下游机器学习任务使用，是一项特征工程任务。随着近年来深度学习的兴起，图神经网络成为网络表示学习领域研究的热点。与网络节点的嵌入表示不同，图神经网络多为端到端的训练框架。
2.1网络节点嵌入方法
2.1.1传统方法
早期的网络表示学习方法被作为降维技术的一部分，将网络节点嵌入到低维空间的思想是让互相连接的节点在嵌入后的低维向量空间中彼此保持更近的距离。LLE（locally linear embedding）算法认为每一个数据点都可以由其近邻点的线性加权组合得到。该方法先寻找每个样本点的是个近邻点，由每个样本点的近邻点计算出该样本点的局部重构权重矩阵，然后用局部权重矩阵和其近邻点计算出该样本点的输出值，LLE算法的目标函数表示为
2.1.2基于网络结构的嵌入方法
Google在2013年推出一个用于获取词向量的工具包Word2vec，它的简单高效引起了很多人的关注，同时也给网络表示学习提供了很好的思路。Word2vec是根據大量语料库中词语的共现关系来得出每个单词的向量嵌入，有CBOW和skip-gram两种模型。前者根据上下文预测中心词，后者是根据中心词预测上下文，这里只介绍skip-gram模型，如图3所示。
用核心词w与其上下文context（w）组成训练样本，skip-gram模型用核心词w预测上下文context（W），通过大量语料库的词语共现关系来不断更新词语的向量表示，用负采样来加快训练速度，最终得到每个词语的向量表示。在Word2vec被提出之后，研究者在其基础上提出了大量基于随机游走的网络表示学习方法，如DeepWalk，Node2vec等，这些方法利用随机游走产生的节点序列作为skip-gram的输入，从而生成节点的低维向量表示。 PEROZZI等观测到节点在短随机游走中的分布和词语在自然语言中的分布都满足幂律分布，并在游走的过程中获取了节点的局部结构信息，从而将Word2vec模型引入网络表示学习，提出DeepWalk算法，利用节点截断随机游走产生的类似语料中句子的序列，借助词向量模型生成节点的嵌入向量，使得效果有了较大的提升。Deep-Walk对Karate数据集的嵌入效果如图4所示。
GROVER等将BFS与DFS融人节点的随机游走，提出了Node2vec算法。相比于DeepWalk算法中节点的随机游走，加入BFS和DFS策略的Node2vec可以更好地挖掘网络中的拓扑信息，如图5所示。
需要注意的是在嵌入向量的更新计算中，DeepWalk采用分层Softmax来计算归一化因子，使用二叉树结构加速计算，而Node2vec算法则采用负采样方法，每个训练样本只更新部分模型权重，从而提高嵌入的训练速度。
DeepWalkEls3和Node2vecEzz]利用随机或有偏随机游走来获得节点的邻域信息，从而生成嵌入向量，使在网络结构中相连和距离较近的节点在对应的低维空间中也具有相近的距离。但是在网络中存在结构一致性（structural identify）节点，如图6所示，顶点u与顶点v的度数分别是5和4，分别连接3个和2个三角形网络结构，并通过2个顶点（d，e;x，w）与外界相连，这样的节点虽然没有直接相连也没有共同邻域，但具有空间结构一致性。RIBERIO等观察到DeepWalk和Node2vec等算法构造的节点序列不能识别相隔较远的具有结构一致性的节点，为了解决此问题，提出Struc2vec算法。
TANG等提出了LINE算法，使得在小时范围内单机学习百万级顶点网络表示成为了可能。LINE算法提出了一阶相似度与二阶相似度，一阶相似度描述了直接相连的节点之间的相似度，如图8中节点6和节点7直接相连，两节点相似度为边的权重;二阶相似度描述为一对节点之间的接近程度和邻居网络结构之间的相似性，如图8中节点5与节点6之间没有直接的边关系，但有共同的网络邻居。
一个网络中的边关系往往是非常稀疏的，所以有必要进一步刻画二阶相似度关系来考虑虽然并不直接相连但是共同邻居较多的节点对，从而对第一阶相似度的信息予以补充。LINE算法适用于大规模网络，并且网络的边不限制是否有向和是否带权，在节点分类等任务中表现出不错的效果。
GraRep算法在LINE定义的一阶和二阶相似性的启发下，将这种相似性推广到更高阶，定义了k阶相似性。GraRep中也使用了像LINE中一样将高阶的图中的相似关系在低维向量空间中用条件概率表示，并且使用了负采样优化的策略。
2.1.3融入属性信息的嵌入方法
上述方法模型只利用了网络中拓扑结构的相似性来生成节点嵌入向量，真实世界的网络通常在节点和边上附属有标签文本等丰富的属性信息，若能充分利用网络中的属性信息，会得到更好的嵌入效果。
TU等提出的CANE算法在兼顾网络结构相似性的同时，利用attention机制自适应计算节点文本内容的相似性。图10为CANE方法的框架示意图，该方法利用卷积神经网络对一条边上2个节点的文本信息进行编码。在文本表示生成的过程中，利用相互注意力机制，选取2个节点彼此最相关的卷积结果构成最后的文本表示向量。
文献[29]中将文本也转化为特殊的节点，形成两种连接的边，即节点一节点和节点一文档，对两种边一起建模嵌入得到节点表示。针对属性网络的表示学习方法有ANRL，SIGNet，TransNet和SANE，它们结合网络结构和节点的属性信息使学习到的嵌入表示具有更多的信息性。BiasedWalk则考虑兼顾有偏随机游走的优势以及网络节点的属性信息，以学习到信息更加丰富的网络嵌入表示。
当信息网络中的节点或边类型数量n≥2时，这种网络被称为异构网络。针对异构网络的表示学习方法也有大量研究者做出很多探索，典型的方法有metapat2vec，HIN2Vec，Tri-DNR，HNEE，HEBE，EOE，以及基于Attention机制的HAN等。
2.2图神经网络方法
2.2.1基于谱域的图卷积
BRUNA等首先提出了在图网络中基于谱域的卷积方法，函数卷积的傅里叶变换等于函数傅里叶变换的乘积，表达式如下：
3应用
网络表示学习在社会生产中有非常广泛的应用。本文给出了网络表示学习模型适用性与特点的比较，以及研究中可能会用到的数据集及其分类统计信息，整理了部分模型的实现链接和已开源的图深度学习库，方便研究者快速复现验证并掌握模型，讨论了网络表示学习的应用方向和实例。
3.1模型对比与数据集及开源实现
表2对比了网络表示学习模型的适用性和方法特点，包括模型是否支持带权图、有向图以及属性图，并给出了模型的时间复杂度和模型特点，可供研究者参考使用。表3给出了众多测试算法性能的数据集，数据集包括3类，分别是引文网络、社交网络和化学生物网络。对应于每个数据集，表中给出了数据集来源，分别统计了该数据集的子图数、节点数、边数、特征数和标签类别数量，方便研究者选择适合模型的数据集。
开源实现的模型总结如表4所示，图深度学习开源库总结如表5所示。在表4与表5中整理出了一些具有代表性模型的开源实现，以及强大的图深度学习库，可供研究者快速学习或复现验证模型效果。其中在表5中列出的Euler，PGL，Plato图深度学习库支持分布式计算，使得更大规模的网络计算成为可能。
3.2实际应用
网络表示學习可以应用到许多实际任务中。可以宽泛地将应用分为4类，即节点分类、社区发现、链接预测和网络可视化。
1）节点分类节点分类是网络节点表示为向量后最常见的任务，一般属于半监督的学习任务，即初始数据中数据标签只占一部分，学习已有标签的数据信息来标记其余数据的标签。常见的半监督学习任务有视频文档网页的类别标记、蛋白质生物功能的学习标记或者社交网络中预测部分用户的标签信息。通常先抽取节点的属性或结构特征来为节点生成嵌入信息，然后应用逻辑回归等分类器为对应节点预测标签。最近的研究评估表明这些模型对节点标签的预测或分类有很高的精度。其中GcN为代表的图卷积神经网络对节点的分类精度要高于传统方法，但它们都是对静态图进行嵌入分类。HAMILTON等提出归纳式学习模型Graphsage，利用邻域信息学习聚合函数，以便对动态网络中的新增节点进行嵌入和分类。 2）社区发现社区发现是在给定网络中，将物理对象或抽象对象的集合分组为类似对象组成的多个社区。社区发现是无监督的聚类，即对大量未知标注的数据集按数据的内在相似性将数据划分成多个类别，使得类别内数据相似度较大而类别间的数据相似度较小。与节点分类不同的是社区发现不需要任何标记信息，可应用范围更广，节省数据标记成本。在实际应用中，社区发现可以为药物网络划分社区，帮助推测相似药物，依据蛋白质网络中节点的联系将蛋白质自动分类。
3）链接预测网络由实体间的交互信息构成，但在实体之间这种交互信息往往会缺失或者会在未来出现，在生物网络分析中验证节点之间是否存在链接需要复杂的实验测试和高昂的代价，因此网络的链接预测显得尤为重要。链接预测在推荐系统中应用广泛，例如WANG等和OU等预测了来自公共协作和社交网络上的节点链接。另外，链接预测在生物网络分析中也非常普遍，利用链接预测方法给出一个可能存在链接的序列是非常经济有效的。
4）网络可视化网络表示学习为节点生成嵌入向量和网络降维可视化提供了新方法。每一个节点都被表示为一个低维稠密的向量，可以方便地利用已有的降维可视化算法如t-SNE，LargeVis等生成网络的二维或三维图形，这对于发现网络社区和其他隐藏结构有很大帮助。例如，Deepwalk的作者利用降维可视化嵌入的空手道俱乐部网络来展現DeepWalk方法的优越之处。Line的作者利用LargeVis可视化DBLP作者网络，表明LINE能够将合作作者聚集在同一个领域。
4总结与展望
本文介绍了现有的网络表示学习方法，将其分为两类并细分为6个类别，分别是传统方法、基于网络结构的嵌入、融人属性信息的嵌入，以及最近非常流行的基于谱域的图卷积、基于空间的图卷积和图attention网络。本文还对比了模型的适用性与算法特点，给出网络表示学习中的经典数据集，整理了常用模型的开源实现项目以及8个开源的图深度学习库。最后还介绍了网络表示学习的应用。网络表示学习发展迅速，不断取得成果，但在以下方面仍面临挑战。
1）深层的图神经网络学习不同于图像分类任务，实验表明，随着网络层数增加，相邻节点的嵌人表示将会逐渐靠近直至收敛到一个点，图神经网络模型性能会急剧下降。
2）动态和异构网络的表示真实世界中存在大量的异构网络并且随时间动态变化，大多方法模型将网络简化为同构的静止不变的网络去处理。现有的解决动态异构网络表示的模型仍有很大的提升空间。
3）网络模型的泛化能力实际场景中的网络往往复杂且差异较大，现有的网络模型设计都是针对某一种简化的网络，设计一个能泛化到大量网络的模型是一个值得深入研究的问题。
转载注明来源:https://www.xzbu.com/1/view-15215624.htm
