网络表示学习算法的研究现状与进展

李 敏，汪 晴，于春红

(淮北师范大学 计算机科学与技术学院，安徽 淮北 235000)

随着网络技术的发展，大规模社交网络、生物信息网络、文献引文网络等网络结构数据的挖掘成为数据挖掘领域的重点。网络结构数据的最大特点是节点之间并非完全独立，因不同关系产生不同类型的边，除此之外，节点因自身特点表现为丰富的内容信息。网络的复杂性、大规模性、不确定性降低了机器学习的效率，网络表示学习成为关键。

节点聚类、分类、链路预测等网络挖掘应用[1]，均以节点的表示信息为输入。传统的网络表示主要为矩阵表示，利用网络结构信息构造网络的权矩阵、邻接矩阵、关联矩阵等矩阵形式。大规模网络的社团现象、冷启动等因素造成网络的高维性、稀疏性使矩阵表示陷入困境，同时矩阵表示无法加入节点信息。节点信息具有标识性，有助于提高网络挖掘效率，网络表示要兼顾网络结构信息和节点信息。向量空间的相似性等定量指标可以直接计算，并且大多机器学习算法以向量为输入，网络表示学习将节点映射到低维向量空间可使用通用的机器学习算法并能够可视化展示节点之间的结构关系。

网络表示学习可以有效地对空间中高维度节点降维，但又不丢失原有网络结构信息，应用于后续其他算法中，网络表示学习流程[1]如图1所示。

图1 网络表示学习流程图

1 基于结构信息的网络表示学习

网络表示学习早期以矩阵表示为主，并基于谱方法对稀疏、高维节点进行降维。代表方法有主成分分析PCA[2]或者奇异值分解SVD、非线性降维算法LLE[3]、拉普拉斯特征映射[4]等。根据结构信息的PCA、SVD方法缺乏节点内在信息，LLE、拉普拉斯特征映射只能处理无向网络，难以直接对网络进行应用并且难以扩展到大型网络。DGE算法[5]基于随机游走思想可扩展到大型网络，有向或无向网络均可处理。从社团检测角度设计的Social Dimensions等网络表示学习算法也只考虑网络的结构信息[6]。以上算法通常网络表示质量较差，并且算法复杂度较高对应用条件要求较为严苛，难以直接应用到网络挖掘任务中。

基于自然语言处理技术的深度学习算法DeepWalk[1]和Node2Vec[7]逐渐被应用到网络表示学习中。为克服邻接矩阵的稀疏性，LINE算法[8]引入二阶相似性。基于深度神经网络的SDNE算法[9]将节点映射到高度非线性空间获取网络的结构信息。

根据截断随机游走的思想，DeepWalk构建等长节点序列。首次引入word2vec中的Skip-gram模型创造性地将词表示学习方法引入网络表示学习中。无向网络节点之间有边即以等概率游走，有向网络中沿“出边”的方向等概率游走。网络中的每个节点v以Φ:v∈VR|V|×d映射到d维向量空间。Φ产生|V|×d个自由参数，根据上下文的信息和节点排列独立性假设，优化条件概率(1)获得参数。

(1)

以vi的截断窗口Wvi内的共现节点为叶子节点构造哈夫曼树，获得截断序列(b0,b1,…,b|log|V||)=uk∈Wvi，b0=boot，b|log|V||=uk。Skip-gram模型根据节点序列uk构造，如公式(2)所示。

(2)

其中：

J(Φ(vj))=-logP(uk|Φ(vj))

Skip-gram模型以α=2.5%的随机梯度下降率不断更新公式(2)，加速条件概率(1)收敛，最终获得vi∈Rd。经实证分析DeepWalk可以用较小的截断随机游走序列有效表示节点。

Node2Vec修改DeepWalk随机游走跳转机制，以条件概率P(vi|vi-1)进行节点访问，不再进行均匀采样。

(3)

其中，α是跳转参数，W(vi,vi-1)是边(vi,vi-1)上的权。游走到节点vi-1，计算其邻居节点vi与上一节点vi-2的距离di,i-2，进而计算α，定义如公式(4)所示。

(4)

参数p和q控制节点向上和向下跳转的概率，节点之间以非等概率跳转。参数p和q其默认值均为1，当p<1且q>1时，游走偏广度优先遍历，着重刻画局部信息；当p>1且q<1时，着重刻画全局信息，深度优先游走。参数设置提高了算法的可扩展性，获取的序列长度不完全相同，更接近真实情况。Node2Vec随机游走跳转机制如图2所示。

图2 Node2Vec跳转机制

LINE算法采用同时保持一阶相似性和二阶相似性的广度优先策略构造邻域表示节点，克服了网络的稀疏性，可扩展到包括有向和无向、赋权和无赋权等任意类型的大规模网络。

网络中相邻节点之间的相似度为一阶相似性，表示为节点的联合概率P1(vi,vj)。

(5)

二阶相似性用于描述网络中具有相同邻接点的节点之间的相似度，两个不直接相连的节点可以使用自身的表示向量和共同邻居的表示向量来度量，用条件概率P2(vj|vi)表示。

(6)

图3 相似性实例

由图3可以看出节点v5,v6不相邻，不具有一阶相似性，但具有二阶相似性，因它们有共同邻居节点v1,v2,v3,v4。节点v6,v7相邻具有一阶相似性，但无共同邻接点没有二阶相似性。LINE遍历节点序列时同时利用具有互补性的一阶相似性和二阶相似性，并使用负采样优化更新节点表示。对于稀疏节点利用邻居的邻居构造样本进行学习，既保留了网络的局部结构又保留了全局结构，但并未利用高阶相似性信息。

2 基于异质网络的表示学习

以上算法不区分节点和边的类型，真实世界中的网络是节点具有差异性、节点之间的链接关系各异的异质网络。例如物联网主要包含用户、商品两类节点，主要应用有推荐系统预测。文献引文网络有4类节点：作者(A)、论文(P)、刊物(V)、主题(O)，论文与其他3个节点之间都存在链接关系，广泛应用在作者影响力排序中，如图4所示。

图4 文献引文网络

同质网络表示学习难以利用异质网络中丰富的语义信息。异质网络因节点间的关联边类型不同所蕴含的语义也不同，节点之间的相似性不能直接量化度量。HINE算法[10]应用Meta math概念区分异质网络中不同类型的边序列构造元路径，引文文献网络中常用的元路径类型有“APA”“APVPA”“OAPVPAO”3种类型。从图4中可以找到一条表示具有相同研究领域的“APVPA”元路径“a1→p1→ACL→p2→a3”。基于元路径量化节点的相似性，使异质网络表示学习成为可能。异质网络是表示现实世界中对象交互的更加通用的建模方式，异质网络表示学习主要有以下3种方式。

(1)基于随机游走的方法

(7)

Nt(v),t∈Tv为异质共现节点，通过极大化目标节点出现的概率，使用Softmax函数加速其收敛速度构造异构Skip-gram模型。

(8)

(9)

～P(ut)[logσ(-Xutm·Xv]

(10)

Metapath2vec++受PTE[12]启发，根据节点类型构造异构负采样，加速函数归一化时也充分考虑了节点类型。经实证分析Metapath2vec++在多标签分类、节点聚类、相似性搜索等任务中具有更高的精度和可靠性。

(2)分解网络的方法

根据节点类型将大规模异质网络分解成若干个子网络，进行同质网络表示学习，有效融合不同类型的节点是关键。代表算法有PTE[12]和HERec[13]等，需要更少的调整参数。PTE算法结合有限的标签实例和大量未标签实例，解决了无监督表示学习算法不能适应特定目标的机器学习任务。PTE首次根据共现词的不同层次将文本网络分解成“词-词”网络、“词-文件”网络和“词-标签”网络，向低维向量空间映射时保持词的二阶相似性。HERec基于不同元路径提取同类型节点序列构造同质网络，进行Node2vec同质表示学习，并融合不同类型节点的向量表示，基于矩阵分解构造评分预测模型，联合融合函数进行模型优化。

PTE定义3个二部网络，分别为上下文词共现“词-词”网络Gww=(V,Eww)，词与文件共现的“词-文件”网络Gwl=(V∪L,Ewl)，词与某类文件共现的“词-标签”网络Gwl=(V∪L,Ewl)。利用节点的二阶相似性修改LINE模型适应二部网络嵌入。

首先定义二部网络G=(VA∪VB,E)，VA∩VB=φ，vi∈VA,vj∈VB。极小化二阶相似性P(vi|vj)。

(11)

直接利用公式(12)加总极小化3个子网络的词节点相似性。

Opte=Oww+Owd+Owl

(12)

其中：

PTE算法对于具有丰富类标号实例的长文本数据的预测是有效的，但词节点表示学习只是简单融合3个子网络，还有改善的空间。

HERec算法首先基于元路径提取多个同质网络并独立表示学习。给定元路径ρ，基于Node2vec思想，目标函数(13)经随机梯度下降优化得到节点的低维向量表示e。

(13)

(14)

α,β为调整参数，节点的不同向量表示使用线性公式(15)和非线性公式(16)所示的融合函数表示。

(15)

(16)

(3)基于深度神经网络的方法

深度神经网络模型容易对非线性关系建模，一些学者尝试利用深度神经网络模型对异质网络中不同类型的节点分别进行建模，并抽取节点语义信息。

BL-MNE[14]采用无监督神经网络模型自动编码器在不同元路径下对节点进行低维编码，再对这些信息通过meta邻近性度量进行联合编码学习得到异质网络的低维空间表示。共用已编码的成熟异质网络节点构造一致属性增广网络，不同网络之间通过转移矩阵进行融合，对于网络稀疏性有很好的效果。SHINE[15]针对情感网络构造3个不同的网络，对3个网络的节点分别进行多重深度自动编码并压缩编码得到低维向量表示，构造聚合函数融合子网的节点表示用于情感链路预测。针对文本和图像并存的异质网络，HNE[16]训练卷积神经网络学习文本，同时训练深度神经网络学习图像，构建转移矩阵投影文本和图像的向量表示到同一空间，使跨模态数据之间的相似性可以度量。

学习异质网络的嵌入表示能够较好地刻画网络中不同类型节点之间的复杂关联，便于和其他模态信息的融合，广泛应用于各类任务场景，一些结合任务的方法也被提出。例如PTE、Metapath2vec、GERI[17]等用于异质网络节点分类，SHINE、HIN2vec[18]等用于异质网络链路预测，JRL[19]、HERec等用于异质网络推荐系统，APE[20]是一个学术合作异质网络双盲评审的作者识别问题。除此之外，RANCH[21]利用图注意网络和卷积神经网络构建半监督学习模型，采用边缘约束截断随机游走产生节点序列，并融合节点标签信息，在节点分类中效果显著。MHGan[22]受生成对抗网络和元路径的启发，充分考虑节点和边的异质性提高关系感知能力，实现对异质网络表示学习，在链路预测和节点分类中性能表现较好。

3 节点信息融合的网络表示方法

社交网络、文献引文网络等现实世界网络中的节点并不完全相同，节点含有丰富的信息，节点的类标签、属性、语义描述等文本信息有助于网络挖掘任务。主要依赖结构信息忽略节点特征信息的传统网络表示学习，网络挖掘效果不佳。有效融合结构和文本信息提高节点表示的质量并增强机器学习输入的效果是网络表示学习的关键。网络结构融合节点信息的表示方法主要有以下3种方式。

(1)结合文本信息的方法

关系矩阵M的内在结构近似等价于一个低秩矩阵，基于这一假设，M是可分解的，但这是NP困难的。TADW在前人工作的基础上通过DeepWalk构建矩阵M=(A+A2)/2，将文本特征矩阵T融入到DeepWalk矩阵分解M=WT×HT，通过共轭梯度下降法优化公式(17)所示的目标函数获得W，H，拼接W和HT。

(17)

HOPE算法[27]也基于矩阵分解框架，这类算法的最大缺点就是存储、计算成本高，伸缩性不好，不适合大规模网络表示学习。

(2)半监督学习

网络节点分类任务需提取节点的分类信息，无监督网络表示学习在节点分类中往往效果不佳。利用节点类标签信息的半监督网络表示学习有针对性地提升节点的区分性，在分类任务中效果较好。MMDW[28]是和TADW类似的半监督网络表示学习方法，该方法先学习基于DeepWalk的矩阵分解形式的网络表示模型M=XTY，同时基于SVM学习一个X的最大间距分类器。MMDW通过目标函数(18)优化分类器。

(18)

(19)

MMDW通过固定X，将Y转化为对偶问题，W和ζ的优化借助随机梯度下降方法。固定W和ζ，计算分类器边界，并设置倾向于正确类别的偏置向量，达到提高表示向量区分能力的目的。在SVM的影响下，MMDW既获得了网络结构信息，也获得了类标签信息，提高了节点的区分性。受最大间距分类器影响，DDRW[29]也采用了类似的方法，DeepWalk矩阵分解模型和最大间距分类器同时训练，提高网络节点的分类效果。

网络中的节点往往只有部分含有类标签信息，为了更好地利用节点信息和节点标签信息，Pan等[30]提出了耦合深度神经网络的TriDNR模型，该模型耦合两个神经网络融合节点的结构、文本和标签信息获得节点的向量表示。模型上层生成的节点序列S与DeepWalk的随机游走相似；节点的文本信息词向量{Wi}作为模型的底层；中间层基于文本信息利用深度神经网络融合S和{Wi}获得节点的向量表示。另一个神经网络融合标签向量{Ci}和词向量{Wi}。最大化目标函数公式(20)耦合两个神经网络。

(20)

其中，α是平衡结构信息、文本信息、标签信息的权，b是随机游走窗口大小，Wj是窗口内第j个词。

网络中节点的标签信息可能不完整、包含噪声，很难学习一个统一的表示形式将标签信息融合到结构信息中。针对以上问题，Huang等[31]提出了LANE模型。该模型由两部分组成，第一部分基于谱聚类将节点相似性映射为结构表示矩阵U(G)和节点属性表示矩阵U(A)，并将U(A)融合进U(G)称为属性网络嵌入；第二部分基于同质性假设融合标签信息光滑U(G)为矩阵U(Y)，同时融合U(G)和U(Y)获得节点的表示矩阵H称为标签嵌入。U(G)和U(A)的获得方式相同，U(G)根据模型(21)获得。

(21)

(22)

根据局部特征分解方程不断更新4个变量矩阵，直到目标函数收敛，完成网络到向量空间的映射。

(3)扩展网络

随着对网络认识的不断深入，网络表示学习方法又出现了扩展网络的方法。CENE[32]将网络扩展为包含两类节点和两类边的网络Gavg(Vn,Vc,Enn,Enc)，其中，Vn为原始网络的节点，Vc为扩展节点信息的特殊节点，Enn为连接原始节点的边，连接Vn与Vc的边为Enc。分别使用逻辑回归函数学习Vn和Vc的向量表示，使用负采样的方法优化目标函数：

(23)

其中，SP是随机游走序列，SN是负采样节点。使用拼接函数公式(24)拼接两类节点。

L=α×Lnn+(1-α)×Lnc

(24)

其中，Lnn为通过由Enn形成的序列Vn，Lnc为通过由Enc形成的序列Vc，参数α∈[0,1]平衡结构信息和文本信息之间的重要性，随机梯度下降优化拼接函数。

TENR[33]和CENE相似，将节点信息视为节点并根据节点信息的相似性构建文本网络，融合原网络扩展成异质网络，如图5所示，圆圈外是文本节点保留了文本相似性，内是原始节点保持了结构相似性。

图5 文本异质网络

受CBOW[34]启发，TENR基于负采样构建拓扑结构模型学习原始节点的结构向量表示，同时构建文本模型学习受文本信息影响的节点向量表示，最终节点的向量表示共享两个模型的学习。

4 基于动态网络的表示学习方法

真实世界中的很多网络是动态的，随时间的推移会出现节点和边的添加或删除，静态网络表示学习方法不能满足动态网络表示学习的需求。更新现有静态网络表示方法[35]以适应动态网络挖掘任务是最简单的方法，现有大多方法将动态网络按时间片应用静态网络表示方法并增加动态变化识别机制。网络分解方法[35]试图通过对连续时间片上的网络表示进行光滑来学习动态网络表示[36]。动态属性网络表示框架DANE[37]首先提出离线表示方法，然后根据属性演化网络的变化更新表示结果。Know-Evolve[38]提出基于多元事件检测的实体嵌入知识图谱的演化网络表示法。CTDN[39]是基于随机游走的连续时间动态网络表示方法，随机游走非在线，网络表示前需要知道所有随机游走的信息。HTNE[40]尝试建模动态网络为自激励系统并利用Hawkes过程模型对网络中的邻域形成进行建模，基于时间点过程优化网络表示。HTNE是在线动态网络表示学习框架，优化过程中使用历史数据，在每个步骤中都要针对历史数据进行调整。基于社团嵌入的Netwalk[41]，利用内存中的存储数据更新随机游走序列。Du等[42]提出动态skip-gram框架，Rudolph等[43]提出基于高斯随机游走的动态词嵌入算法，在时间序列上定义基于向量表示的随机游走。

链路预测是最广泛的动态网络分析应用，而现有时间模式大多简化网络的动态变化，只根据上一时间步长网络预测新链接，有的还假设网络动态变化是光滑的，并使用规则化降低快速变化的影响。在每个时间片上dyngraph2vec[44]进行多重非线性学习结构信息，采用循环神经网络更新表示，循环层设置回顾参数控制周期变动长度。t'=t+1时刻的网络表示以t时刻一系列节点表示为基础，极小化公式(25)表示的损失函数。

(25)

静态网络表示学习的方法具有不稳定性[45]，又由于网络结构的变动通常是局部的，随机游走序列只有少部分受到影响，Heidari[45]提出基于随机游走的增量网络表示学习算法EvoNRL。增量地更新备用随机游走集，并提出支持随机游走集合的有效存储和更新的索引机制用于网络的动态表示。采用静态随机游走方法获得t时刻Gt的每个节点的有效随机游走集RWt并存储为二维numpy矩阵。时刻t'=t+i(i=1,2,…)，因节点的增删或边的增删导致网络结构发生变化，采用不同的方法单独更新G't的RW't使在t'时刻仍有效，并将节点的增删看作特殊的边的增删。增量更新随机游走需要大量的存储和计算开销，为克服这一缺点，提出基于流行的开源索引和搜索技术的索引机制能够有效地索引和检索大量文档，每个随机游走看作由词节点组成的文档，将所有随机游走建立反向随机游走索引IRW表示节点到RWt的映射，RWt的增量更新依赖IRW。EvoNRL讨论的是连通、无权、无向网络，网络结构中发生的任何变化按重要性进行量化，在最佳时间或真正需要时获得新的网络表示，消除随机过程的影响，尽可能保存原始随机游走序列，通过使用上一次运行的数据来初始化模型。

DCTNE[46]是基于随机游走的动态连续时间网络表示学习算法，根据历史数据对当前节点的影响不同建立有偏随机游走过程获得节点时序邻居节点序列，学习网络表示，在节点分类任务上效果显著。DynGraphGAN[47]构建对抗网络，获取节点、边变动引起的网络局部结构信息变化信息，嵌入结构特征和动态演化趋势。基于随机游走的动态网络表示学习还有Sajjad等[48]提出的增量随机游走算法和半监督学习算法tNodeEmbed[49]。TensorGCN[50]、OCAN[51]和AddGraph[52]都是基于深度学习的动态网络表示学习算法，目前也有学者提出利用霍克斯点过程的动态网络表示学习方法[53]，也取得了一定的成果。HIN_DRL[54]利用网络异质信息学习动态网络，基于元路径和时间戳信息动态随机游走生成节点序列。

5 结语

网络表示学习旨在将网络节点映射到便于机器学习处理的低维向量空间，消除网络的高维性和稀疏性。静态网络的表示方法主要分为矩阵分解法和随机游走法，矩阵分解法存储、计算成本高，伸缩性不好，只适用于小型网络；利用网络的局部信息构造节点序列的随机游走方法，能扩展到大型网络。网络表示学习不仅要表征网络结构信息还要结合节点文本信息以及节点之间的不同关联关系，还要注意节点的差异性。现实世界中，大规模网络往往随时间的推移会出现节点及边的变动，具有不确定性，静态网络表示学习方法很难适应网络的动态变化。网络的演变特征学习是现有大多动态网络表示学习的核心，但对网络的高度动态性建模不够，适应性不高。网络表示学习在未来还有巨大发展空间，尤其是具体应用场景下融合多模态信息动态大规模网络表示学习。

(1)融合多模态信息的网络表示学习。现阶段只保存网络自身的信息网络表示学习，忽略了知识图谱等外部知识信息，异质网络因节点信息不同形成多样化的链接关系，从而包含丰富的多模态信息，如何将这些信息融合进网络表示学习是亟待解决的难点。

(2)融合节点信息的大规模动态网络表示学习。现有动态网络表示学习仅学习网络的结构信息，试图捕捉动态变化信息。融合节点信息快速获取新增节点信息，并高效地表示节点，以增量或在线计算的方式表示网络仍是一个难点。

(3)基于具体应用任务特点的网络表示学习。目前网络表示学习算法主要集中在通用的表示学习以适用所有网络分析任务，很少分析具体应用任务特点。通用表示学习在异常检测、社区发现等具体应用中效果往往不佳。如何将网络表示学习技术根据不同应用场景设计更加合理的节点表示模型提高应用效果是值得关注的问题。