属性网络表示学习研究综述

2022-10-31

山东科技大学学报(自然科学版) 2022年5期

(山东科技大学计算机科学与工程学院，山东青岛 266590)

随着互联网、物联网、移动互联网的迅速发展，网络数据资源呈现爆炸式增长。以微博、微信、Twitter、Facebook等为代表的社会化媒体，具有信息实时性、信息开放性、内容全面性、用户自由性、信息传播范围广、信息传播速度快等诸多优点，满足了人们对于信息多样化和沟通个性化的需求，已经成为人们日常交流的重要平台，提供了大量数据资源。社交网络分析与挖掘成为近年来的热门研究课题，包括社区发现[1-2]、链接预测[3-4]、节点分类[5-6]、推荐[7-8]等技术。

由于网络数据中的节点不是孤立存在的，相互之间存在关联，因此难以并行化、分布式处理，直接对原始网络进行分析与挖掘往往具有很高的计算代价，导致网络分析的效率极低。一种有效的解决思路是，将原始网络无损或最小损失地转化到向量空间进行处理。由此，网络表示学习应运而生。

网络表示学习，旨在将原始网络中的节点表示成低维的稠密向量，同时最大程度地保留节点在原网络中的信息和属性。DeepWalk算法[9]充分利用网络的结构信息，利用截断随机游走和神经语言模型获得节点的表示。Tang等[10]认为仅考虑节点之间的一阶近似会丢失许多有用的信息，从节点拥有相同邻居的数量出发，进一步考虑了二阶近似，来保存网络的局部结构和全局结构。Cao等[11]考虑了更高阶的网络结构信息，通过奇异值分解分别学习节点的k阶表示，再将这些表示拼接起来作为节点最终的向量表示。上述算法保留了网络中拓扑结构的特征，但只从拓扑结构的角度对网络进行表示学习，无法获得高质量的节点表示，导致在后续任务上表现不佳。

在实际应用中，越来越多的节点属性信息被记录。如在微博中，每个用户除了拥有自己相对稳定的属性(性别、年龄、血型、星座等)之外，在平台上的一些社交行为，如发表博客、转发、评论等，也产生了大量的文本信息，这些文本信息也可以建模成用户的属性。在微信平台中，既包括好友关系，也包括个人的特征和朋友圈信息，这些都是用户属性的重要体现。此外，引文网络中论文的摘要信息、互联网中网页内容的关键词、维基百科中每个词条所对应的文本描述等也是可用的属性信息。这些都是属性网络模型的典型代表。因此，属性网络已经被广泛应用于社交网络、学术网络、信息系统的建模。

属性网络表示学习旨在将网络中节点的属性信息以及拓扑结构信息，同时映射成联合的低维向量。属性网络的普适性和灵活性，使得属性网络表示学习具有重要的研究意义和应用价值。首先，结合属性信息进行网络表示学习，能够进一步提升模型在网络分析任务上的性能。其次，融合属性信息在某种程度上为节点之间的关系提供一种额外的相似度信息辅助。最后，与异质信息网络相比，属性网络表示学习的信息融合程度更高、普适性更强。

本研究对现有的属性网络表示学习算法进行分类，如图1所示。首先将属性网络表示学习划分为静态属性网络表示学习和动态属性网络表示学习，然后按照网络的类型将静态属性网络表示学习划分为同构属性网络表示学习和异构属性网络表示学习。在此基础上，根据算法的核心技术，进一步分为基于矩阵分解的方法、基于神经网络的方法、基于自编码器的方法、基于随机游走的方法和其他方法。

1 相关定义

定义1属性网络[12]。给定属性网络G=(V,E,X)，其中V表示属性网络中节点的集合，E表示属性网络中边的集合，X表示网络中的属性信息。

定义4同构属性网络[14-15]。给定同构属性网络G=(V,E,X)，其中X是所有节点特征组成的特征矩阵;存在节点类型映射函数φ:V→P，其中P包含所有节点的类型；边关系映射函数φ:E→K，其中K包含所有边的链接关系；若|P|=1并且|K|=1，则是同构属性网络。如图2所示，社交网络即为同构属性网络，该网络中只存在一种类型的节点，节点之间边的链接关系也是单一的。

定义5异构属性网络[14-15]。给定异构属性网络G=(V,E,X)，其中X表示异构属性网络的属性信息，存在节点类型映射函数φ:V→O以及边关系映射函数φ:E→R，网络中的每个节点vi∈V和每条边ei∈E能够通过映射函数φ和φ找到对应的节点类型oi∈O和边关系ri∈R；若|O|<1或者|R|>1，则是异构属性网络。如图3所示，电子商务网络即为异构属性网络，该网络中存在用户和商品这两种类型的节点，用户节点与商品节点之间存在购买、收藏以及添加到购物车等链接关系。

图1 属性网络表示学习方法分类Fig. 1 Classification of attributed network representation learning methods

图2 社交网络示例Fig. 2 An example of social networking

图3 电子商务网络示例Fig. 3 An example of electronic commerce network

问题定义属性网络表示学习[12,16]。给定属性网络，属性网络表示学习的目的是学习节点或边的向量表示。表1给出了论文中主要的符号及其解释。

2 静态属性网络表示学习

静态属性网络表示学习可分为同构属性网络表示学习和异构属性网络表示学习，根据使用的技术，如矩阵分解、自编码器、神经网络、随机游走等，将代表性算法作如下划分。

表1 论文中的常用符号Tab. 1 Notations used in this paper

2.1 同构属性网络表示学习

1) 基于矩阵分解的方法

传统的网络表示学习方法缺乏对网络结构信息和属性信息的融合，使学习到的向量表示在后续任务上表现不佳。因此，一些算法尝试结合属性信息,如文本信息、标签信息等，来学习节点的表示。如TADW(text-associated DeepWalk)算法[17]基于矩阵分解的思想将节点的文本特征融合到网络表示学习中，首先证明DeepWalk[9]是一种矩阵分解，将矩阵M分解为矩阵W与H的乘积；然后TADW在此基础上将节点的文本特征引入到矩阵分解过程中，如图4所示，将矩阵M分解为W、H和T三部分的乘积，其中T表示节点的文本特征，相对应的损失函数如式(1)所示，该算法交替优化W和H矩阵以最小化损失函数。

(1)

图4 TADW算法的主要思想[17]Fig. 4 Main idea of TADW algorithm

AANE(accelerated attributed network embedding)算法[18]将上述矩阵分解的过程进行分布式处理，以提升表示学习的效率。但该算法仅适用于处理网络中的文本属性，不能利用节点的标签信息，学得的表示向量缺少区分能力。Tu等[19]基于最大间隔思想优化了DeepWalk算法，将节点的标签信息加入到节点的表示学习过程中，并设计了半监督的网络表示学习模型MMDW(max-margin DeepWalk)。MMDW首先将DeepWalk转化为矩阵分解的形式，即M=XTY，其中X是节点的向量表示矩阵，Y是节点的内容表示矩阵，然后利用SVM[20]训练向量表示X，并且在分类过程中引入Biased Gradient，使向量表示朝着准确的预测方向更新，以此提高节点表示的区分能力。

2) 基于神经网络的方法

图卷积网络主要包括基于谱域上的图卷积和基于空间域上的图卷积。基于谱域上的图卷积网络算法主要利用傅立叶变换将图数据变换到谱域上进行图卷积，GCN(graph convolutional network)[21]为此类方法中的代表性算法，如图5所示。多层图卷积网络通过输入层、隐藏层以及输出层学习特征向量，但该算法需要花费较多计算成本。基于空间域上的图卷积网络算法是直接对图数据进行图卷积，此类方法中的代表性算法有GraphSAGE(graph sample and aggregate)[22]，该算法通过训练一组聚合函数，从节点局部邻域中聚合特征信息，经过训练后能够为新加入网络的节点生成嵌入。GAT(graph attention networks)算法[23]在此基础上结合注意力机制为相同邻域内的节点分配不同的权重系数，且不需要事先了解整个图结构，解决了以往基于谱方法的理论问题。

图5 多层图卷积网络(GCN)[21]Fig. 5 Multi-layer graph convolutional network(GCN)

3) 基于自编码器的方法

MMDW算法主要利用节点的标签信息，忽略了边上的标签信息。Tu等[24]提出TransNet算法，该算法基于边上的标签信息学习节点的表示，将边上的多个标签形式化地表示为节点之间的关系。该算法利用深度自编码器以及转换机制[25-26]对节点之间进行交互建模，在社会关系网络中验证了模型提取节点之间关系的强大能力。GAE(graph auto-encoder)与VGAE(variational graph auto-encoder)算法[27]利用GCN[21]构建编码器来学习节点的向量表示，通过解码器重构图结构数据，学得的向量表示融合了结构信息与属性信息，在后续的链接预测任务中表现出色。两者学习网络的方法稍有不同，GAE结合自编码器对网络进行表示学习，而VGAE为变分自编码器[28-29]。

不同于GAE和VGAE仅重构图结构，Salehi等[30]提出的GATE算法重构图结构以及节点属性，基于自编码器和自注意力机制[23]学习节点的嵌入，能够应用于直推式以及归纳式学习。Pan等[31]提出ARGA(adversarially regularized graph autoencoder)和ARVGA(adversarially regularized variational graph autoencoder)算法，利用编码器和生成对抗网络[32]来学习节点的向量表示，这两个算法对节点的属性信息和结构信息进行编码，并且通过生成训练模块使节点的表示更具有鲁棒性。ARGA与ARVGA的区别在于，前者使用图自编码器[26]，后者采用变分图自编码器[26]。在下游任务性能中，两者在不同数据集上的应用效果差距不明显。

4) 基于随机游走的方法

现有的嵌入方法大多忽略了将节点的属性信息编码到表示学习过程中，Li等[33]为解决此问题提出PPNE算法，该算法将网络拓扑结构和节点的属性信息融合到网络嵌入过程中，共同优化属性驱动目标函数和结构驱动目标函数学得节点的向量表示。与上述方法不同，Pan等[34]提出的TriDNR方法将节点的结构、内容和标签信息融合到节点的向量表示中，将网络中的关系划分为“节点-节点”“节点-内容”和“标签-相关内容”，该算法对这三种关系分别建模来学习节点的表示。

标签信息有时不易获取，Wang等[35]提出了无监督的稀疏属性网络嵌入算法SANE(sparse attributed network embedding)，该算法利用截断随机游走产生节点序列，对节点和属性之间的关系进行建模，借助CBOW(continuous bag of words)[25,36]和注意力机制[37-38]学习节点的向量表示。Guo等[39]认为现有的大部分算法都是直推式，并且未同时考虑局部和全局的结构信息，基于RPR(rooted page rank)[40]提出了SPINE(structural identity preserved inductive network embedding)算法以解决该问题，该算法通过合并网络的结构和内容信息学习节点的嵌入，并且利用Skip-Gram 负采样方法和正采样策略增强节点间的结构相似性，在节点分类任务上表现出色。

5) 其他方法

现有的聚合器忽略了节点之间的交互，Zhu等[41]提出了BGNN(bilinear graph neural network)算法以解决此问题。该算法结合FM(factorization machines)方法[42-43]编码节点之间的交互，实现增强传统的线性聚合器的目的。Cheng等[44]提出了AFN(adaptive factorization network)算法，该算法的主要思想是将特征嵌入转换为对数空间，并且将特征组合中每个特征的幂作为要学习的系数，在模型训练过程中逐渐优化此系数，从而实现从数据中自适应学习任意阶特征交互。Xu等[45]提出了图推理学习算法GIL(graph inference learning)，该算法同时考虑节点属性、节点间路径和图拓扑结构来构建结构关系，从已标记的节点中推断未标记节点的标签，提高了半监督节点分类的性能。

对同构属性网络学习算法，在核心技术、数据集、时间复杂度、评测任务等方面进行对比，如表2所示。

表2 同构属性网络学习算法对比Tab. 2 Comparison of learning algorithms for attributed homogeneous networks

2.2 异构属性网络表示学习

1) 基于矩阵分解的方法

维基百科是著名的异构网络数据来源之一，在以前的语义分析大多局限于单一类型的关系。Zhao等[50]基于此问题提出坐标矩阵分解(coordinate matrix factorization，CMF)算法，该算法认为维基实体之间存在“实体-实体”“类别-实体”和“词-实体”三种关系，在语义空间学习实体、词与类别的表示，通过矩阵分解实体与实体的系数矩阵X、类别-实体系数矩阵Y和词-实体系数矩阵Z获得向量表示，如图6所示。

图6 CMF算法的主要思想[50]Fig. 6 Main idea of CMF algorithm

2) 基于神经网络的方法

异构网络中的内容信息和关系信息是非常重要的，HNE(heterogeneous network embedding)算法[51]将异构内容和关系融合到表示学习过程中。以文本-图片异构网络为例，HNE将网络中的链接关系划分为“图片-图片”“文本-文本”和“图片-文本”三种关系，然后对其进行相似性建模，该算法捕获了异构组件之间的复杂交互。Zhang等[52]指出很少有算法能同时有效地考虑异构结构信息和节点的异构内容信息，为此提出HetGNN(heterogeneous graph neural network)算法以同时捕获结构异质性和非结构化内容异质性。该算法首先基于重启随机游走的方法来采样节点的邻居序列，然后结合神经网络编码节点的异构内容，最后引入注意力机制[23]来学习不同类型的邻居对节点表示的影响。

3) 基于自编码器的方法

Liu等[53]提出一种归纳式网络表示学习模型，利用神经网络将节点的属性信息、不同类型的节点信息和边的信息融合到表示学习过程中。该算法可嵌入以前未看到的节点或孤立节点，且不需要额外的训练。为了解决基于查询的数据集推荐问题，HVGAE(heterogeneous variational graph autoencoder)算法[54]结合变分图自编码器[27]学习论文和数据集的表示，在此基础上根据所查询的论文与数据集之间的相关性将前若干个相关数据集进行推荐。

4) 其他方法

Li等[55]针对异构属性信息网络的半监督聚类问题提出SCHAIN(semi-supervised clustering in heterogeneous attributed information networks)算法，该算法结合属性的相似性和基于链接的相似性实现半监督聚类，其中利用必须链接集和不可链接集作为监督约束以促进聚类效果。Zhang等[56]认为元图是捕获异质网络中的丰富语义以及潜在关系的强大工具，但现有方法没有充分利用元图，所以设计了mg2vec算法以解决此问题，该算法融合一阶以及二阶元图嵌入以获得最终的节点嵌入。

针对不同的评测任务，对异构属性网络表示学习算法的核心技术、评价指标以及性能等方面进行对比，如表3所示。

表3 异构属性网络学习算法对比Tab. 3 Comparison of learning algorithms for attributed heterogeneous networks

3 动态属性网络表示学习

尽管动态属性网络在生活中的应用非常广泛，但是相关研究比较少。DANE(dynamic attributed network embedding)算法[58]是基于动态属性网络表示学习的方法，将模型分成离线模型和线上模型两部分，其中离线模型能够学习节点在时刻t的嵌入，线上模型基于矩阵摄动理论[59]更新节点的嵌入。但该算法不能应用到大规模网络场景中，否则时间复杂度会很高。Liu等[60]提出适合大规模属性网络表示学习的DRLAN(dynamic representation learning framework for large-scale attributed networks)算法，能捕捉网络中高层非线性并保存拓扑结构和节点属性的高阶相似度。

现有的链路预测算法绝大多数都是为静态网络设计的，忽略了网络的动态变化。为此，Li等[61]提出SLIDE(streaming link prediction for dynamic attributed networks)算法，能有效地研究网络的结构和节点属性的动态变化对链接预测的影响。不同于传统的时序链接预测技术忽略了动态网络中潜在的非线性特性以及链接权重，Lei等[62]提出GCN-GAN(GCN-generative adversarial network)算法，将动态图定义为一系列的图快照，然后利用GCN提取每张图快照的结构特征，并且采用LSTM[63]捕捉动态图中的演变模式，利用全连接层预测下一个时间切片的拓扑结构，最后训练鉴别器以判断输入的数据是否是真实数据，从而使预测的带有权重的链接更有代表性。

超图保存了高阶结构的信息，广泛应用在分类、检索等任务上。Zhang等[64]提出基于动态环境的DHSL算法，从标签空间以及特征空间更新超图结构。但是该算法仅在初始特征嵌入时更新超图结构，忽略了特征之间的高阶关系。为解决此问题，Jiang等[65]设计了DHGNN(dynamic hypergraph neural networks)算法，该算法利用K-NN(K-nerual neighbor)方法以及K-means聚类方法基于全局和局部的特征更新超图结构，并结合自注意力机制聚合邻接超边的特征。

针对不同的评测任务，对动态属性网络表示学习算法的核心技术、评价指标以及性能等方面进行对比，如表4所示。