基于稀疏自编码器的属性网络嵌入算法

张志敏,柴变芳,李文斌

(河北地质大学 信息工程学院,石家庄 050031)

0 概述

随着网络信息技术的发展以及文献著作数量的迅速增加,引文网络已经形成了一个超大规模的复杂网络[1]系统,然而此类网络数据[2]的高维性、稀疏性和异质性制约了相关研究的发展[3-5]。近年来,很多学者提出了针对网络分析的网络嵌入算法[6-7],其将网络信息编码为低维稠密的实数向量,并且得到的低维嵌入向量能够保持原有网络的属性和结构[8-9]。由于此类向量在使用前必须做进一步的任务分析,如节点分类、聚类、链接预测等[10-11],因此如何从原始网络中获取有效的网络嵌入向量非常重要。

目前已有多种获取网络嵌入向量的方法,根据使用信息的不同主要分为两类:基于网络结构的嵌入方法,以及基于网络结构和属性信息的嵌入方法。在基于网络结构的嵌入方法中:Deepwalk算法[12]从网络结构的随机游走序列中得到节点的嵌入表示,其改进算法Node2Vec算法[13]又考虑游走深度与游走广度,进一步提高了网络表示学习的性能;LINE算法[14]用直接相连的两个节点刻画第一级相似度(即利用邻接矩阵),用不直接连接的两个节点刻画第二级相似度(作为邻接矩阵的补充)进行概率建模,并通过最小化概率分布和经验分布间的KL散度[15]得到网络节点的嵌入表示。在基于网络结构和属性信息的嵌入方法中:SNE模型[16]融合网络结构信息和节点属性信息作为神经网络输入,在输出层以最大化节点邻居出现概率为优化目标,利用多层感知机制提取节点的低维表示;SDNE模型[17]使用深度自编码器保持两阶邻居之间的邻近节点表示,再通过最小化相邻节点间的欧氏距离来保持相邻节点之间的邻近性;DNGR模型[18]采用随机冲浪策略捕捉图形结构信息,再进一步将这些结构信息转换为PPMI矩阵,使用去噪自编码器获得节点的嵌入表示;WMCNE模型[19-20]将网络拓扑和语义信息统一到图形表示中,并使用局部空间结构增强图形表示,在此基础上使用深层自编码进行网络重建。在上述方法中,WMCNE模型性能较好,其对网络拓扑和语义信息进行图形统一化表示,但该模型构建网络拓扑结构时利用了由邻接矩阵转换的模块度矩阵,未考虑节点间间接链接信息。此外,其在结合模块度矩阵和属性信息时采用直接拼接方式,自编码训练时维度过高并且参数过多制约了算法性能的提升。

本文提出一种深层挖掘网络拓扑信息并融合节点属性信息的网络嵌入算法SAANE。基于网络链接提取二级邻居和节点的共同邻居比,并将其整合到同一图形中,对节点属性进行相似度计算得到基于属性相似度的网络,由此构造属性模块度矩阵。在此基础上,融合网络拓扑信息和属性信息进行稀疏自编码,进而获得最终的网络嵌入向量。

1 相关定义

为更好地描述SAANE算法,给出以下定义及其符号表示。

定义1(属性网络) 给定含有n个节点的无向网络G=(V,E,C,N,R),其中:V={v1,v2,…,vn}是网络中节点的集合;E={eij}(i,j∈{1,2,…,n})是网络中边的集合;C={c1,c2,…,cn}是节点属性集合;N表示前n(n≥2)阶邻居的集合,若vi与vj之间有边,且vj与vk之间有边,则vk称为vi的二阶邻居;R={rij}表示前n(n≥2)阶邻居的共同邻居比矩阵,节点vi的前k(k≥2)阶邻居集合为Ni,k,节点vj的前k(k≥2)阶邻居集合为Nj,k。rij表示为:

(1)

定义2(Node2Vec随机序列) 根据Node2Vec算法设置参数p=2,q=0.5,采用深度优先搜索策略生成随机游走序列。以Washington数据集为例进行说明。图1(a)中第1列为当前节点的序号,第2列为当前节点的一阶邻居,第3列为当前节点二阶邻居……,利用该序列提取节点的二阶邻居集,如图1(b)所示,然后基于节点的二阶邻居计算共同邻居比,如图1(c)所示。

图1 Washington数据集的二级邻居及共同邻居比

2 SAANE算法

2.1 网络特征累加对比

为测试网络拓扑信息深度挖掘的有效性,本文在真实网络中依次引入邻接矩阵、二阶邻居、共同邻居比、节点属性模块度,对得到的向量使用K-means方法进行聚类,并选择NMI作为衡量指标,对比结果如图2所示。可以看出,针对5个真实网络依次引入邻接矩阵、二阶邻居、共同邻居比和属性模块度矩阵,NMI值逐渐增加,说明引入信息的增加有助于进一步挖掘网络特征。

图2 真实数据集上的网络特征聚类结果

2.2 模型框架

SAANE模型框架如图3所示,其中包含3个模块:1)网络特征提取模块,由网络拓扑提取二级邻居及共同邻居比并进行整合;2)属性模块度计算模块,由节点属性矩阵获取属性模块度矩阵;3)深度稀疏自编码器,加权融合处理后的拓扑向量和语义模块度进行深度稀疏自编码,同时引入局部增强约束和稀疏损失约束。

图3 SAANE模型框架

2.2.1 网络特征提取

M1=sign(A+N)

(2)

为确保由链接获取的信息与共同邻居比同等重要,采用2-范数对M1做标准化处理,定义如下:

(3)

从而得到:

M2=n(M1)

(4)

对标准化后的特征向量与共同邻居比求和,即得到由网络拓扑结构提取出的网络特征M:

M=M3+R

(5)

2.2.2 语义属性模块度

对于节点上的文本属性,计算两个节点间的相似性得到相似图S=[sij]=[cos(wi,wj)],其中wi是节点vi的内容向量。由于模块度能够转好地衡量网络社区结构强度,因此用模块度矩阵B代替S作为属性信息的最终表示,定义如下:

B=[bij]=[sij-(ξiξj)/2m]

(6)

将从拓扑中提取的网络特征和从属性信息中提取的网络特征直接加权求和作为深度自编码的输入,计算公式如下:

X=[xij]=[mij+αbij]

(7)

其中,α表示内容向量在提取的网络特征中所占权重。

2.2.3 稀疏自编码器

自编码器由编码器和解码器组成,其中,编码器将输入空间中的数据映射到潜在空间,解码器将潜在空间的数据映射到重构空间。形式上,编码器将输入数据zi映射到潜在空间的hi,解码器将表示空间的对象hi映射到重建空间中的yi,公式如下:

hi=f(W(H)xi+b(H))

yi=f(W(Y)hi+b(Y))

(8)

其中,W(H)和b(H)是编码参数,f(·)是编码/解码激活函数,如tanhx=(ex-e-x)/(ex+e-x),W(Y)和b(Y)是学习的解码参数。

自编码器的损失函数为:

(9)

其中,β为权衡参数,H为自编码训练过程中获得的隐层表示,Lreg表示WMCNE模型[19]中局部增强约束部分。

当自编码器收敛时,最中间的隐层即为网络的最终嵌入。为获得更好的表示,堆叠多个自编码器,构建一个完整的深度自编码器学习网络嵌入向量。首先训练第一个自编码器来重建输入矩阵X,并且获得第一个隐层H(1)以及第一个重建层Y(1)。然后使用H(1)训练第2个自编码器的隐层,……,以此逐层构造模型,然后获得最终的隐层表示作为最终嵌入。

由于网络特征提取过程中多次使用拓扑结构,因此降低了原拓扑结构的稀疏性,使所得特征中非零元素减少,但同时也导致了模型参数训练时间的增加。针对该问题,本文通过向隐层神经元添加稀疏约束减少编码层中活动神经元的数量。采用KL散度计算每个神经元稀疏损失,定义如下:

Pij=Kkl(pij‖qij)=

(10)

最后,将神经元的稀疏损失添加到目标函数中,得到新的目标损失函数,如式(11)所示,并且迭代计算其最小值。

(11)

2.2.4 算法描述

SAANE算法描述如下:

算法1SAANE算法

输入网络G=(V,E,C),迭代次数r,表示向量维度d,随机游走参数p、q,二阶邻居所占权重α,局部增强权重β,稀疏损失权重γ

输出节点嵌入向量矩阵H,其中每行表示一个节点对应的嵌入向量

//整合输入向量

1.对于给定网络,使用Node2Vec算法获得随机游走序列;

2.根据随机游走序列,获得二阶邻居矩阵N和共同邻居比矩阵R;

3.计算属性模块度矩阵B;

4.根据式(7)整合输入向量;

//使用自编码进行迭代训练

5.初始化权重参数W和偏置b;

6.for i=1 to r

7.根据式(8)获得隐藏层嵌入向量H;

8.根据Y=f(WTH+b2)获得输出层嵌入向量;

9.根据式(9)的左半部分计算重建损失loss_a;

10.根据式(9)的右半部分计算局部增强损失loss_b;

11.根据式(10)计算稀疏损失loss_c;

12.loss=loss_a+loss_b+loss_c;//总的损失函数

13.使用RMSprop算法最优化loss值;

14.end

3 实验

为评估本文算法的有效性,在聚类和分类任务上进行实验测试。使用5个具有不同大小和特征的公开数据集Washington、Wisconsin、Texas、Cornell和CiteSeer,对比方法为基于拓扑的算法Deepwalk、Node2Vec、LINE、SDNE和基于属性网络的嵌入算法TADW[21]、SNE、DNGR、WMCNE。

为确保对比的公平性,将所有算法的最终维度设置为64,参数采用默认值。对于本文算法,文本属性权重占比根据网络中每个节点平均边数的不同进行设置,以便更大程度提取不同网络的内在特征。自编码器中激活函数选择tanh(·)。实验取10次运行结果的平均值进行比较。

3.1 数据集比较

CiteSeer数据集是一个由3 312个科学出版物组成的引文网络,其中包含6个类别;WebKB数据集包含4个子数据集Washington、Wisconsin、Texas、Cornell,分别收集了4个不同大学的网页数据。各数据集详情如表1所示。

表1 实验数据集

3.2 实验环境

本文采用Python3.6实现各算法,在Intel Core i7-3770 CPU®3.40 GHz,8.00 GB内存的Windows10(64位)计算机上运行程序。

3.3 聚类实验

得到网络嵌入向量后,本文使用K-means算法进行聚类,评估指标选用NMI值,表2所示的结果表明,使用SAANE算法获得的嵌入向量进行聚类任务时,NMI值在最佳基线上平均提高了5.83%。

表2 9种算法的NMI值对比

3.4 分类实验

得到网络嵌入向量后,使用Logistic、支持向量机SVC、线性判别分析LDA、K-近邻算法4种方法对这些节点进行正确标注分类,并采用精度平均值作为度量指标评估所有方法的性能,如表3所示。可以看出,使用SAANE算法进行分类可使准确率平均提高4.53%。

表3 9种算法的分类准确率对比

3.5 实验结果分析

表2和表3的实验结果显示,本文算法性能优于其他算法。具体分析如下:

1)基于随机游走的Node2Vec算法和DeepWalk算法较依赖局部信息,而TADW、SNE、DNGR、WMCNE算法既考虑了拓扑结构,又考虑了语义信息,其中性能较好的是WMCNE算法,但该算法将处理过的拓扑信息和语义信息进行拼接,导致训练前维度过高,训练过程缓慢。本文算法对拓扑结构、二阶邻居、共同邻居比进行整合,并将这些特征标准化,使其能直接进行运算,再与语义信息加权整合,既提高了训练速度,又避免了网络中拓扑信息和属性信息的权重占比对目标嵌入向量造成影响。表4显示了2个模型在不同数据集上迭代1 000次并运行10次的平均时间,可以看出,相较于其他8种算法中性能最好的WMCNE算法,本文算法运行时间较短。

表4 WMCNE和SAANE算法的运行时间对比

2)获取嵌入向量时,需要根据情况设置网络拓扑信息和节点属性的权重,SAANE从边/节点比值入手,对网络中每个节点平均边数多的网络减少节点属性权重(Washington、Wisconsin、Texas数据集节点属性权重为2时性能较好),而对网络中每个节点平均边数少的网络则增加节点属性的权重(Cornell和Citeseer数据集节点权重设置为4时性能较好)。

4 算法参数敏感度分析

SAANE算法包含3个超参数,即前n阶邻居、节点属性所占权重比值α和稀疏损失参数γ,本文通过改变参数取值得到不同的节点嵌入,并用K-means方法对得到的表示进行聚类操作,再使用NMI评估方法进行结果评估。

4.1 邻居阶数影响分析

在实验过程中,分别测试选择二阶邻居、三阶邻居、四阶邻居和五阶邻居在最终实验结果NMI值上的影响,如图4所示,可以看出,本文算法在选择二阶邻居时效果较好。

图4 n阶邻居实验结果(n=2,3,4,5)

4.2 属性特征所占权重影响分析

图5显示了融合拓扑特征和语义特征时语义特征所占权重的影响,α取值0.0～6.0,间隔0.5进行一次实验。可以看出,α取值的最佳效果与网中每个节点拥有的平均边数有关,如Washington、Wisconsin、Texas数据集的平均边数大于1.5,则语义权重值为2.0时NMI值较稳定且效果较好,而对于Cornell和Cite数据集则平均边数小于1.5,语义权重设置为4.0性能更好,说明使用网络拓扑结构和节点属性捕获网络特征时,两者各自所占权重与网络中各节点的平均边数有关,节点平均边数越大,属性所占权重值应越小。

图5 语义特征权重实验结果

4.3 稀疏损失参数影响分析

图6显示了设置权重参数相同情况下稀疏损失参数取值对实验结果的影响,γ取值0.0～1.0,间隔0.1进行一次实验。可以看出,γ取值的最佳效果与网络中每个节点拥有的平均边数有关,如Washington、Wisconsin、Texas数据集的平均边数大于1.5,则稀疏损失设置为0.1时NMI值较稳定且效果较好,而对于Cornell和Cite数据集则稀疏损失权重设置为0.3性能更好,说明使用网络拓扑结构和节点属性捕获网络特征时,稀疏损失约束与网络中各节点的平均边数有关,节点平均边数越多,稀疏损失约束设置的值应越小。

图6 稀疏损失实验结果

5 结束语

本文提出基于稀疏自编码器的SAANE算法。根据节点的拓扑结构获得随机游走序列,利用此序列分别得到二阶邻居和共同邻居比,并将邻接矩阵、二阶邻居、共同邻居比相互整合融入语义信息,在此基础上进行深度稀疏自编码训练,得到最终嵌入向量。该算法在5个真实数据集上执行聚类和分类任务时均获得了较好的效果。然而,本文假设只要节点间有链接(直接链接或间接链接)就表示两个节点有一定关系,但在真实网络中不同类别的两个节点间也可能存在链接关系。如何在网络结构中保留正向链接并消除多余的链接,获得更贴合真实网络的嵌入向量,将是下一步的研究方向。