结构增强的属性网络表示学习

窦 伟，张维玉，翁自强，夏忠秀

齐鲁工业大学（山东省科学院）计算机科学与技术学院，济南250353

在万物互联的信息时代，网络[1]作为日常生活中描述实体之间联系的重要数据形式，其表示学习的研究也受到广泛关注。网络表示学习旨在为网络中的每个节点学习低维、稠密、实值的向量表示，从而解决诸如邻接矩阵等传统网络表示面临的高维、稀疏等问题[2]。通过网络表示学习得到的低维向量具有一定的推理能力，可以直接应用现有的机器学习算法进行多种网络分析任务来挖掘网络数据中的潜在信息，例如节点分类[3]、链路预测[4]、社区发现[5]等。

早期的网络表示学习主要基于网络关系矩阵的计算，通过对关系矩阵进行特征值分解或者奇异值分解从而降低原矩阵的维度得到节点低维表示，关系矩阵是指网络的邻接矩阵或者拉普拉斯矩阵[6]。LLE[7]假设网络中节点的表示是其邻居节点表示的线性组合。Laplace eigenmap[8]假设网络中相连的节点其表示也应该相近，并将距离定义为两个向量的欧氏距离。由于此类方法计算复杂度高，所以难以应用于大规模的网络分析，并且没有结合属性信息。近几年人工神经网络技术蓬勃发展，一些基于神经网络的表示学习方法相继被提出。DeepWalk[9]的提出掀起了网络表示学习的研究热潮，它在网络中实施截断随机游走生成含有邻接信息的节点序列，然后使用Word2Vec中的skip-gram[10]模型学习网络表示。LINE[11]定义了网络中节点的一阶和二阶的相似性，并设计和优化了两个目标函数保存节点的相似性。Node2Vec[12]则拓展了DeepWalk随机游走的方式，结合深度优先搜索和广度优先搜索进一步探索网络的结构信息。SDNE[13]将深度学习技术应用到网络表示学习中，SDNE结合深度自动编码器和拉普拉斯映射保留网络结构一阶和二阶的相似性。然而上述网络表示学习方法都集中于普通网络的表示学习，忽略了节点丰富的属性信息。随着网络中信息的多元化，网络中的节点通常包含有丰富的属性，例如常用的社交软件微信、微博，用户在注册的时候通常都会填写个人基本资料（地址、工作单位等）；学术论文的引用网络，除了论文之间互相的引用关系，每篇论文都会有所属的期刊/会议，研究主题等，这类具有节点属性信息的网络称之为属性网络。

现实生活中大部分网络都可以建模为属性网络，所以最近属性网络的表示学习引起学者广泛研究。TADW[14]证明DeepWalk等价于矩阵分解，在此基础之上，TADW对邻接矩阵进行分解的同时使用文本表示矩阵进行约束，得到刻画结构信息和属性信息的网络表示。TriDNR[15]耦合了DeepWalk和Doc2Vec[16]两个模型，将结构、属性和标签考虑其中。FeatWalk[17]和Gat2Vec[18]的想法类似，都是在设计了一个兼容属性和结构的随机游走方法，后采用浅层神经网络学习网络表示。GraphRNA[19]则在一种属性随机游走的基础之上设计了一种特殊的循环神经网络框架来学习网络表示。自动编码器是无监督深度学习的结构，广泛应用于各种无监督学习的任务。DANE[20]使用两个深度自动编码器通过一致性和互补性约束保留结构信息和属性信息。MVC-DNE[21]也使用两个深度自动编码器，以多视图学习的视角学习结构和属性的网络表示。VGAE[22]将图变分自动编码器迁移到属性网络表示学习领域。ARNL[23]结合自动编码器和skip-gram模型共同学属性和结构的表示并取得了良好的性能。

ANRL使用输入和输出不同的自动编码器，将节点自身属性信息作为自动编码器的输入，重构邻居的属性信息。ANRL一定程度结合了结构信息和属性信息，但是如果自身的属性信息与邻居的属性信息差别较大，即中心节点虽然与邻居节点相连，但是它们的属性信息有较大的差异时，则输入与输出差别较大自动编码器在重构过程中会丢失大量信息，从而影响到最终的表示。GCN[24]是谱图卷积的一阶近似，使得处理图像的卷积操作能够简单地被用到网络结构数据中来，但是GCN是半监督的模型，需要依赖节点的标签信息，真实的网络数据的便签是极为稀疏的，并且GCN只是节点分类的模型，没有拓展到另一个网络分析任务链路预测上。这里受GCN聚合思想的启发，结合ANRL的框架结构，本文提出一种结构增强的属性网络表示学习方法SANRL（Structure-enhanced Attributed Network Representation Learning）。SANRL在表示学习前期就将结构信息与属性信息无缝融合，增强了网络中节点属性信息的结构特征，并使用自动编码器无监督地提取节点特征，结合skip-gram模型并通过联合优化框架将结构信息和属性信息映射到同一向量空间完成网络表示学习。

1 相关定义

为了更好地对提出的方法进行阐述，本章对文中出现的字母和符号进行定义和描述。

定义1属性网络。用G=(V,ε,A,Z)表示属性网络，其中V表示网络中所包含节点的集合；ε表示节点之间边的集合；A∈Rn×n是描述网络全局连接关系的邻接矩阵，是n×n的方阵，n表示网络中节点的个数；Z∈ℝn×m是描述节点属性信息的属性矩阵，同样的，n表示节点的个数，m是属性矩阵的维数。Ai表示邻接矩阵A的第i行，是节点i邻接信息的体现。Aij表示A的第i行第j列的元素，如果Aij=1表示节点i和节点j之间有边相连，否则Aij=0。Zi表示属性矩阵Z的第i行，是节点i的属性信息，如果Zix>0则表示节点i与属性x相关联。

定义2属性网络表示学习。属性网络表示学习的目标就在给定属性网络G=(V,ε,A,Z)的情况下，学习一个映射函数f:V↦Rd，将网络中每个节点映射到d维的向量空间中，其中d≪n。映射函数f不仅要保留节点的结构信息，还要保留节点的属性信息。学习到的网络表示向量可以当作特征向量作为后续网络分析任务（例如节点分类、链路预测）的输入。

2 结构增强的属性网络表示学习

SANRL使用统一的框架对网络的结构信息和节点的属性信息进行表示学习，在前期对节点的属性信息进行邻接性的增强，旨在更好地融合两方信息学习最优网络表示，SANRL的框架流程如图1所示。本章将对SANRL进行详细介绍。

图1 SANRL模型框架Fig.1 Model framework of SANRL

2.1 全局结构信息和属性信息的学习

网络的结构信息和节点的属性信息属于异构信息，分开进行表示学习后将向量进行拼接也可以起到结合的作用，但是简单的拼接操作不足以描述节点的结构和属性之间的复杂关系。这里受GCN的启发，通过反映全局结构信息的邻接矩阵和节点属性信息的属性矩阵，对节点邻居的属性进行聚合操作，并且保留节点自身的属性，具体的，数学上表示如式（1）所示：

A的每一行Ai表示了当前节点i的一阶邻接关系，与节点i直接相连的节点在Ai的对应位置为1，其余位置为0。当邻接矩阵A与属性矩阵Z进行乘积时，即节点i邻居的属性在所有维度的加和。因节点自身属性也很重要，所以在A的基础之上加一个单位矩阵In得到A͂，如此在A͂与Z相乘后，节点自身的属性也被考虑进去。再与自身的度矩阵相乘后得到的新的矩阵M,实际上是节点自身属性和邻居属性的加权平均。相比于普通属性矩阵Z,M包含了自身和邻居属性信息，是网络结构信息和属性信息的融合。

得到聚合有自身属性与邻接属性的矩阵M不是最终目标，而是对其降维并保留其中的全局结构信息和属性信息。为了发挥深度学习自动提取特征的优势，本文采用无监督的学习结构—自动编码器进行表示学习。自动编码器是进行表示学习典型的深度学习模型，它的思路很简单：将输入数据通过编码器映射到某个特征空间，再通过解码器将编码器压缩后的特征空间映射回输入空间，对输入数据进行重构，这样神经网络的中间层就保存了输入数据的特征达到降维效果。对应本文的任务，将增强结构信息的属性聚合矩阵M作为自动编码器的输入，数据经过编码部分被映射到一个低维的向量空间中，然后在解码部分对输入的数据进行重构，“强迫”隐含层尽可能多地将输入数据即结合有全局结构信息和属性信息的聚合矩阵M的特征保存下来。因此，自动编码器每一层的隐含表示如下：

其中，L表示自动编码器的层数；σ(⋅)是每层网络的激活函数，例如Tanh、ReLU等；W(l)和b(l)分别是神经网络第l层的权重矩阵和偏置。自动编码器不需要额外的监督信息，它通过不断最小化输入和输出之间的重构误差进行训练，对应于文本的任务是最小化重构聚合矩阵M的损失，定义为：

2.2 局部结构信息的学习

在上一节中将网络的全局结构信息和属性信息可以通过自动编码器合成到低维向量空间中，但是局部的结构信息需要进一步加强。skip-gram模型已被广泛应用于网络结构的表示学习。基于skip-gram模型网络表示学习的基本假设是如果网络中的节点拥有相同或者相似上下文节点其网络表示应该相近，所以它的基本思想是通过网络中节点之间的共现关系学习节点的向量表示。应用于本文，将自动编码器提取到的结合有全局结构信息和属性信息的低维表示通过skip-gram模型使在网络中具有共现关系的节点的表示向量更加相似。skip-gram模型对局部窗口内的节点对进行概率建模，并最小化公式（7）所表示的对数似然概率：

其中，Ci={vi-w,…,vi+w}指的是随机游走序列中心节点vi以w为窗口的上下文，条件概率Pr(vj|Mi)是指中心节点vi在结合全局结构信息和属性信息后与上下文节点共现的可能性，将其定义为：

f(Mi)是中心节点vi的全局结构信息和属性信息经过自动编码器得到的低维表示，vj是节点vi上下文的低维表示。注意到公式（8）的分母部分，每一次迭代都需要遍历网络中所有的节点来完成计算，对于规模大一些的网络这个计算是相当昂贵的。为了降低庞大的计算量并且保持结果的有效性，参考文献[23，27]，本文采用Word2Vec[10]提出的负采样策略，根据噪声分布采样一定数量的负样本简化训练目标：

通过最小化Ls，则有相同的上下文的节点的网络表示在向量空间中距离更近，数据及其邻居在输入空间中的邻接关系在特征空间中仍然保留下来，使网络表示的局部结构性得到加强。

2.3 联合优化

前两节介绍了如何通过自动编码器和skip-gram模型捕捉网络的全局、局部结构信息和属性信息，因为本文的任务是将结构信息和属性信息在同一个向量空间进行融合表示，所以结合在公式（6）和公式（10）定义的损失函数La和Ls，得到SANRL最终的损失函数：

本文使用随机梯度下降来对L进行优化直至模型收敛，优化学习过程在算法1中展示，其中第7行和第9行是对SANRL中参数进行更新的过程。最后通过优化这个联合损失，SANRL将网络结构信息、节点属性信息无缝的嵌入到同一表示空间中，学习最优网络表示。

算法1SANRL的联合优化框架

2.4 算法复杂度分析

首先，聚合矩阵的计算复杂度为O(||ε)，因为A͂Z能够被高效地以稀疏矩阵和稠密矩阵相乘的形式实现。其次SANRL以mini-batch的方式训练神经网络，其计算复杂度与mini-batch的样本数和迭代次数相关，所以SANRL是可拓展的。

3 实验与结果分析

为了验证所提出的属性网络表示学习方法SANRL的有效性，本文在三个公开的真实的属性网络数据集上进行实验。本章介绍了实验所使用的数据集以及对比方法，通过节点分类和链路预测对SANRL进行评估。

3.1 数据集及对比方法介绍

本文使用的数据集是三个真实公开属性网络数据集：Cora（https：//snap.stanford.edu/data.）、Citeseer和Pubmed（https：//linqs.soe.ucsc.edu/data.），它们的大致情况如表1所示。链接表示论文的引用关系，属性是对应论文的词带模型表示。

表1 三个真实数据集的统计信息Table 1 Statistics of three real-world datasets

为了评估本文提出的SANRL的性能，本文将其与7个具有代表性的网络表示学习方法进行对比验证，其中包括3个普通网络表示学习方法和4个属性网络表示学习方法。

（1）DeepWalk[9]在网络中进行随机游走得到若干节点序列，将它们送入skip-gram模型中学习网络表示。

（2）Node2Vec[12]使用偏置随机游走结合深度优先搜索和广度优先搜索来捕捉网络结构信息生成节点序列，并通过skip-gram模型完成网络中所有节点的表示学习。

（3）SDNE[13]结合深度自动编码器和拉普拉斯映射同时学习网络的一阶和二阶结构信息。

（4）TriDNR[15]耦合skip-gram和Doc2Vec同时学习网络结构、节点属性和节点的标签信息，可以看作是一个半监督的方法。

（5）VGAE[22]是一个基于图卷积神经网络的变分自动编码器模型，同时学习网络的结构信息和属性信息。

（6）ANRL[23]通过输入和输出不同的自动编码器和skip-gram模型学习属性网络中的节点表示。这里使用它性能最好的一个方法：ANRL-WAN。

（7）DANE[20]通过两个自动编码器分别建模结构和属性信息，设置约束条件在两种信息之间保持一致性和互补性。

前三个对比方法是普通网络的表示学习，后四个是属性网络表示学习方法。本文对比方法的代码都是作者提供，并且参数也是按照作者在报告中所指出的进行设定。为了公平起见，最后学习的网络表示的维度d都设定为128。对于SANRL，将上下文窗口的大小w设置为10，每个节点随机游走的次数r设置为10，随机游走的长度l设置为80，负采样的数量设置为5。SANRL中自动编码器的结构如表2所示。

表2 神经网络结构Table 2 Neural network structures

本文实验采用Python3.6版本，基于Tensorflow1.15.2实现，在Intel Core i7-7700，16.00 GB内存的操作系统为Windows 10（64位）计算机上运行。

3.2 节点分类任务实验结果分析

在本节中进行常用的网络分析任务：节点分类来评价SANRL的性能。具体的，首先使用SANRL以及其他对比方法对所给网络进行表示学习，然后随机选取30%的节点的表示向量作为节点特征以及对应的标签作为训练集来训练SVM分类器，剩余节点作为测试集，最后计算Macro-F1和Micro-F1值作为测试结果。此过程重复10次取平均值作为最后节点分类的结果。

所有数据集的节点分类的结果如表3所示，最优值以粗体突出显示。从表中可以观察出：本文提出的结构增强的属性网络表示学习方法SANRL在Cora、Citeseer和Pubmed数据集上均表现出了最佳的性能。在只考虑链接的网络表示学习方法中，Node2Vec相比较其他两个同类方法表现出较好的性能，但是融合了属性信息的SANRL在三个数据集中Macro-F1和Micro-F1相比于Node2Vec高出0.065到0.185不等。这表明节点属性在网络表示学习中的重要性，融合属性信息可以很大程度上提高网络表示学习方法的性能。

表3 三个数据集的节点分类结果Table 3 Node classification results of three datasets

其中在Cora数据集的实验中，相比较ANRL，Macro-F1值高出约0.077，Micro-F1值也高出约0.085。这说明SANRL在将自身属性与邻居属性聚合后，相比于ANRL输入和输出端不同的自动编码器更容易捕捉到节点之间复杂的非线性的关系，更完整地保留数据中的信息，对最终表示产生积极影响。

综合表3的实验结果和上述分析，表明SANRL在节点分类任务中性能最优，能够更加准确地预测网络中未知节点的标签，从而更加有效地从原始属性网络中提取更多信息。

3.3 链接预测任务实验结果分析

链接预测也是网络分析中一项非常重要的任务。本文使用三个数据集的链路预测任务来评测SANRL的表示学习的能力。链接预测的目的是预测网络中缺失的链接，或者预测在未来可能出现的链接，常用于一些推荐任务。具体的，首先从网络中移除10%已有的链接，移除链接的节点成为正样本，然后随机采样相同数量没有链接的节点作为负样本，正样本和负样本构成测试集。基于剩余的网络使用对比方法和SANRL进行网络表示学习。给定测试集中的节点对，根据学得的网络表示学习向量计算余弦相似度得分，采用AUC值作为评价预测结果的指标。图2展示了在三个数据集上链接预测任务的表现。

图2 三个数据集的链接预测结果Fig.2 Linkprediction results of three datasets

从柱状图可以看出本文提出的SANRL表现出最佳性能，其中在三个数据集中SANRL的AUC值高出前三个普通网络表示学习0.09~0.15不等。结果再次印证只考虑结构信息的网络表示学习方法的性能有限，将节点属性信息考虑其中进行表示学习得到的网络表示向量质量的提高是可观的，很大程度上弥补了因链接稀疏给网络表示学习造成的阻碍。

SANRL在三个数据集上的实验结果也均高于其他属性网络表示学习方法方法，其中在Pubmed数据集上SANRL的实验结果的ACU值高出使用两个自动编码器的属性网络表示学习方法DANE约0.07。SANRL仅使用一个自动编码器学习网络表示结果优于两个自动编码器的方法，一个重要原因就是网络的结构信息和属性信息在进行表示学习时是密不可分的，若分开建模对最终表示影响很大。SANRL在表示学习前期就将属性信息进行结构信息的增强，从而融合的特征在经过提取之后更大程度地保留了节点在网络中的所包含的信息，使得学习得到的表示向量对节点相似度的判断更加准确。

综合图2以及上述分析，使用SANRL进行表示学习，其得到的网络表示对网络中丢失或者隐含的链接地预测更加精准。

4 结束语

本文提出一种邻居增强的属性网络表示学习方法SANRL，该方法可以有效结合网络的结构信息和节点的属性信息学习质量更高的网络表示。在网络表示学习初期，SANRL首先通过聚合操作使节点的属性信息得到结构方面的增强，有效避免因结构信息和属性信息的异构性给网络表示学习带来的阻碍。SANRL使用自动编码器无监督地对结构增强的属性信息进行特征提取，然后通过skip-gram模型最大化局部窗口内节点对的似然概率，增强网络局部的邻接关系使原网络中距离相近节点的表示向量更加相似。最后SANRL通过一个联合损失函数使结构和属性信息得以在同一向量空间获得最佳表示。在多个真实的网络进行大量的实验，SANRL的表现均优于目前流行的网络表示学习方法，证明了SANRL学习得到的网络表示质量更高。

异质信息网络由多种类型的节点和链接构成，在现实生活中也比较常见，而异质信息网络中节点的异质性给未来网络表示学习带来更大挑战。如何在保持结构增强的属性信息基础之上将节点的异质性考虑在内，设计出适合异构信息网络的表示学习方法将成为下一步的研究目标。