马 怡,吴丽萍,苏 磊
(昆明理工大学 信息工程与自动化学院,云南 昆明 650500)
随着社交平台在人们日常交往中的作用越来越重要,人们通过社交平台与他人联系,发布和获取信息。社交平台提供个性化的高质量推荐服务来增加用户流量和扩大平台的相应收益。链路预测在社会化网络推荐中有重要应用价值。链路预测旨在利用网络节点和结构信息,预测下一个时间节点中新链接产生的可能性或某一时间节点中链接丢失的情况。这种预测已经应用于各种图形结构,例如蛋白质相互作用、社交网络等。为了处理这种图形结构,许多算法和机器学习模型被提出和应用。图深度学习是一种针对图结构数据的深度学习方法,它已经在链路预测领域取得了一些重要进展。图深度学习模型通常使用基于神经网络的方法来捕获节点之间的关系,从而预测潜在的链接或连接概率。这种方法包括图卷积神经网络(Graph Convolution Neural Networks,GCN)[1]、循环神经网络(Recurrent Neural Network,RNN)[2]、图注意力网络(Graph Attention Networks,GAT)[3]、Graphormer[4]等。这些模型能够从多个角度捕捉节点间的相似性和差异性,从而提升链路预测的准确性。通常,图深度学习链路预测方法将节点映射到低维向量空间,并在该空间中计算节点之间的相似性。这些节点表示可以通过随机游走[5]、自编码器[6]等多种方式获得。其中,变分自编码器模型具有善于挖掘各种高维数据相关特征、能够生成具有多样性和可控性的样本等优点。本文提出一种融合了抗噪机制的图变分自编码器(Denoising Graph Variational Autoencoders,DGVAE)[6]的复杂网络链路预测算法。本文的主要贡献在于以下3 个方面:首先,构建了一种适合于复杂网络链路预测的降噪图变分自编码器训练网络结构;其次,基于降噪图变分自编码器的数据恢复能力,提出了一种复杂网络链路预测模型;最后,在大量不同类型的社交网络上进行了实验比较,结果表明,相较于其他经典的链路预测算法,本文提出的DGVAE 算法在预测准确性和鲁棒性方面具有显著优势。
图是刻画复杂网络的数学模型,可表示为G(V,E),是由多个顶点和顶点之间的连边组成的集合。图由节点集合V={v1,v2,…,vN1}和连边集合E={e1,e2,…,eN2}组成,其中N1为网络中的节点总数,N2为网络中的连边总数。任意一条边对应一个节点的二元组ex=(vi,vj)。与网络相关的几个重要的拓扑结构特征描述如下:
(1)度[7]:复杂网络模型中,一个节点的度是指与该节点相连的边的数量。节点的度定义为:
式中:Γi为i的直接邻居构成的集合。
(2)网络密度[8]:网络密度刻画一个网络中现有连边数目和潜在最大连边数目之间的差异。其数学定义为:
(3)同配系数[9]:同配系数的取值范围在-1到1 之间,其中同配系数为正表示网络中度数相似的节点更容易相连,为负则表示度数差别较大的节点更容易相连,而同配系数为0 则表示网络中度数相互独立。计算公式为:
(1)曲线下面积(Area Under Curve,AUC)[10-11]:属于分类准确性指标,量化的是算法能在多大程度上将相关的边和不相关的边区分开。
式中:n为独立比较的次数;n'为试验聚集边的相似度高于不出现边的相似性值;n"为试验聚集边的相似度低于不出现边的相似性值。
F1-Score[10-11]:是一种用于衡量分类模型性能的指标,它的取值范围从0 到1,其中1 表示建模的正确性,0 表示建模的可靠性。其计算方法为:
式中:Precision为连边正确的比例;Recall为连边正确占测试集的比例。F1-Score的优点是它同时考虑了Precision和Recall,因此可以对分类器的性能进行全面评估。
(3)平均绝对误差(Mean absolute error,MAE)[10-11]:是一种评价回归模型准确度的重要指标,也是通过计算预测值与真实值之间的绝对误差来评价建模的准确度的一种方法。MAE 的计算公式为:
MAE的值越小越好,说明模型的拟合效果较好。
图变分自编码器(Graph Variational Auto-Encoders,GVAE)的基本思路如下:先对图进行编码学习到其节点向量表示的高斯分布,然后从高斯分布中恢复节点的向量表示,重构图结构。模型的输入是不完整的观测图(图中的部分边被移除),所有的节点特征保留。测试集和验证集由移除的边和等量随机抽样的负样本构建。变分自编码器分为编码器和解码器,也就是推断模型和生成模型。推断模型将真实样本编码为低维向量表示(隐变量),学习隐变量的分布;生成模型从隐变量的分布中采样得到对应真实样本的隐变量,生成尽可能接近真实样本的数据。在这个过程中,利用了重参数技巧代替采样过程,保证了模型可训练。GVAE 是一种基于变分自编码器(Variational Auto-Encoders,VAE)的图神经网络模型,主要用于无监督的图节点表征学习和链路预测任务。
图变分自编码器示意图如图1 所示,其由推断模型和生成模型组成。
图1 图变分自编码器
其中,推断模型由两层GCN 构成:
式中:Wi为权重矩阵;为对称标准化邻接矩阵。推断模型需要学习节点向量的分布,通过学习均值和方差来表示。隐变量的后验概率分布为:
其中:
式中:μ=GCNμ(X,A)为节点向量表示的均值μi的矩阵;logσ=GCNσ(X,A)是节点σ(·)向量表示的方差σi的矩阵表示;GCNμ(X,A)和GCNσ(X,A)共享第1 层的参数W0。
生成模型通过计算两个隐变量的内积来重构图结构:
相较于其他图神经网络模型,GVAE 在链路预测任务中具有以下优点:无须标签信息,可扩展性强,能够自动提取特征,有效性和可解释性强。
抗噪图变分自编码器首先对输入数据进行加噪处理,这里的噪声可以是任何类型的噪声,例如高斯噪声或者椒盐噪声。然后,扰乱后的样本被作为GVAE 的输入,GVAE 通过学习数据的潜在分布来重构没有加入噪声之前的样本。噪声对抗机制是通过训练一个额外的分类器来实现的,该分类器的任务是区分加噪后的样本和没有加噪的样本。这个分类器的目标是让加噪的样本更难以被正确分类,从而鼓励编码器学习到更鲁棒的特征表示。下面,针对DGVAE 的有效性进行分析。对于所有样本,希望最大化其对数似然,即
为了优化该目标,可以最大化下式:
式中:L为变分下界,最大化logp(x)可以通过最大化变分下界实现,这里为了区分,L定义为Lvae。在此基础上,对输入x加入噪声,令被噪声破坏后的输入为x',假设噪声的分布qψ(x'|x)是一个已知的分布(可以省去参数ψ,即变为无参分布),这里直接取为无参分布q(x'|x),原始GVAE 模型中的编码器qΦ(x'|x)变为:
代入GVAE 的变分下界,可得:
假设一个近似后验分布有如下形式:
这里,Φ={φ,ψ},对于给定的pθ(x,z)=pθ(x|z)p(z),有如下不等式:
进一步地,得到了DGVAE 的变分下界:
暂且不考虑如何优化该目标,明确一些细节:
(1)式(18)无法进一步变换为类似标准GVAE 的重构误差与KL 散度[12]的形式,因为期望下的分布q'Φ(z|x)与分母q'Φ(z|x')已经不是同一分布。
(2)根据不等式,得到了Ldvae≥Lcvae,但这和Lvae并没有必然的联系,只能说Ldvae很可能是一个比Lvae更紧的下界,但也存在反例。这主要取决于噪声的分布q(x'|x),如果其噪声强度过大,使扰乱后的样本失去了重要信息,那么势必会导致Lcvae≥Lvae。所以一个结论是,DGVAE 是一个对噪声分布敏感的模型。
(3)还需要明确,最大化Ldvae的过程中,实际是在做什么,按照标准的GVAE 框架来看,目标其实是最小化近似后验和真实后验的距离,将此带入DGVAE,即
如果将Lcvae换成Ldvae,这个等式会变成:
如果选择直接优化Lcvae也是可以的,并且只需要基于标准GVAE 框架,在数据读入后、训练前加入噪声,其他不变即可。关于为什么DGVAE 比GVAE效果更好,先结合高斯混合模型[13](Gaussian Mixture Model,GMM)去描述,再通过实验证明。这里先介绍如何计算之前得到的优化目标。优化目标如下:
采用蒙特卡洛采样[14](Monte Carlo sampling)来近似变分下界:
式中:x'm~q(x'|x),z(k|m)~qΦ(z|x'm)。这时,基于梯度优化该式。
DGVAE 能够对略加破坏的样本进行重构并恢复其为破坏的状态,其鲁棒性比GVAE 好,因为其编码部分一定学到了如何排除噪声并提取重要特征的能力,但GVAE 由于没有人为加入噪声的干扰,所以不清楚其是否连带着噪声一并编码到其中。接下来,从公式上分析原因。首先看到qφ(z|x')也是近似标准高斯分布的,之后会结合高斯混合来最终解释。对Ldvae进行变形如下:
可知,在训练过程中,有约束使得q'Φ(z|x)的表达式为:
因为q(x'|x)是一个已知的概率分布,而qφ(z|x')是一个近似标准高斯分布的分布,所以在整体上,可以近似认为qφ(z|x)是一个高斯混合模型。与GVAE 相比,DGVAE 以高斯混合模型对后验概率p(z|x)建模,显然,如果q(x'|x)选择得合适,GVAE可以处理的DGVAE 也可以处理,并且GVAE 不能处理的DGVAE 仍可以处理。
建模的目的是去除输入向量中带有噪声的节点,因此目标是尽可能使输出向量接近未受噪声干扰的原始数据。如图2 所示,它由如下3 个部分构成:首先,为了进行链路预测,需要建立一个适合的降噪自编码器来进行训练和预测;其次,需要确定网络结构,然后使用误差反向传播算法对网络结构的参数进行调整;最后,使用训练好的网络结构来进行链路预测。这个过程需要注意网络结构的合理性和参数的准确性,以保证预测结果的可靠性和精度。
图2 DGVAE 链路预测模型架构
选择来自不同现实社交网络中的6 个作为实验网络,如表1 所示。这些实验网络具有不同的拓扑结构特征。通过对这些社交网络进行实验来评估模型性能。最后,详细列出了各个实验数据集的相关信息,包括网络名称、节点数量、边数量、网络密度、同配系数等。
表1 实验数据集
首先,使用最终的打分矩阵作为计算模型性能的基础。这种方法可以确保评估的结果是最终模型的真实表现,而不是在评估过程中的任意时刻产生的一时结果。其次,为了避免划分数据集时可能出现的偶然误差,对每个数据集进行了100 次独立的实验。这种方法可以减少偶然误差对评估结果的影响,提高评估的准确性。最后,对AUC,F1-Score和MAE值分别取平均值。这种方法可以更全面地评估模型的性能,从而提供更为准确和可靠的数据支持。算法流程图如图3 所示。
图3 结合抗噪机制的图变分自编码器链路预测流程
在噪声对抗机制下,使用图变分自编码器进行节点嵌入(node embedding)。为防止过平滑问题[15-16],该算法的编码器层和解码器层都设置为2 层,学习率设置为5e-4,每一层激活函数均设置为sigmiod。数据经过算法训练一次记为一个周期(epoch),本算法中设定epoch=50。每个epoch周期训练中使用的batch大小设定为 1,即每次训练中输入一个反映任一选定节点与其他节点连接状态的向量。
(1)深度生成概率图神经网络(Deep generative Probabilistic Graph Neural networks,DPGN)[17]:一种新的图神经网络模型,利用生成模型生成节点和边的参数,并将其应用于关系学习和链路预测任务中。
(2)图矩阵分解(Graph Matrix Decomposition,GMD)[18]:将网络表示为矩阵的形式,利用矩阵分解等技术来提取网络中的模式和结构信息,从而进行链路预测。
(3)GGCN[19]:该方法首先使用GCN 来学习节点表示,然后通过引入门控机制(Gating Mechanism)来控制邻居节点的信息流动,从而更好地捕捉节点之间的依赖关系。
(4)SH-GCN[20]:一种半监督的层次化图卷积网络方法来解决链接预测问题。该方法通过使用层次化表示和链接预测损失来提高预测的准确性,同时允许在使用少量标记数据的情况下进行训练。
(5)GVAE:通过将输入的数据编码为潜在向量,并通过解码器将潜在向量转换回原始数据,从而生成新的数据。在链路预测中,可以使用GVAE来学习节点之间的相似性,并据此进行预测。
本实验选取的基线均为近年来图表示学习与图对比学习领域内较为前沿的技术。相较于传统的自监督方法,这些技术不仅在性能表现上更加优异,而且在实际应用中也具有更广泛的适用性和可扩展性。这些技术能够适应不同的场景和数据集,并且可以通过集成不同的特征和模型来进一步提高性能。本次实验均取100 次预测结果,最后取平均值。这些基线技术是链路预测领域的重要研究方向,值得进一步深入探索和应用。
如表2、表3、表4 所示,是本文提出的链路预测模型DGVAE 在6 个具有节点属性的社交网络中与其他5 个基线模型的性能对比。其中,加粗数值表示模型的最优预测性能评估值。其中,每个分数值均为模型预测100 次取平均得到。训练过程中,训练集与测试集按照80%∶20%的比例划分。
表2 与其他对比模型的AUC 性能表现
表3 与其他对比模型F1-Score 性能表现
表4 与其他对比模型的MAE 性能表现
与其他链路预测方法相比,DGVAE 的AUC、F1-Score 分数平均提高了约3.5%和2.1%。在实验网络BlogCatalog 中,本文提出的链路预测模型DGVAE 的AUC 值达到了92.1%,表现非常出色。值得一提的是,在Reddit 实验网络上,本文提出的DGVAE 模型的MAE 值接近0.8,明显低于其他对比算法的MAE 值。其中,与无抗噪机制下的图变分自编码器模型对比发现,结合抗噪机制的图变分自编码器模型在链路预测任务上,AUC 准确率在6个实验网络上,分别提升了1.6%,2.8%,2.6%,3.3%,2.4%,2.1%。因此,有理由相信,在加入抗噪机制下的图变分自编码器模型下,在链路预测任务上可以取得更好的效果。
本文提出的链路预测模型DGVAE 的预测性能优于其他主流无监督链路预测方法。因此,这一模型有望成为社交网络中链路预测强有力的工具。
本文旨在针对不同的训练集占比进行鲁棒性分析,评估DGVAE 模型的鲁棒性。结果显示,在抗噪机制下,DGVAE 模型在各个数据集上的准确率和AUC 值表现很好,但是AUC 值的表现不够稳定,特别是在较大的网络数据集中。这主要是因为随着网络规模的增大,网络结构间的隐含特征增多,导致较小的神经网络结构无法充分表达链路预测中正样本(即两个节点间存在链路)和负样本(即两个节点间不存在链路)之间的差异,从而导致预测准确性存在波动。因此,为了提高DGMAE 模型的鲁棒性,未来的研究可以探究如何优化模型结构,以充分表达正负样本之间的差异,并进一步提高预测性能的稳定性。图4 显示了训练集划分比例为30%,50%,70%和90%的各个网络中所有被测试算法的对比分析结果。
图4 各个网络中所有被测试模型鲁棒性的对比分析结果
DGVAE 模型是一种链路预测模型,其预测性能优于其他经典的链路预测模型,但需要注意AUC值的波动性。此外,随着网络规模增大,需要进一步探究如何优化模型以提高其鲁棒性和预测性能。本文提出的结合抗噪机制的图变分自编码器在预测准确性和鲁棒性分析方面都表现出了明显的优势,这突显了该模型在与其他经典的链路预测模型相比时具有强大的竞争力。因此,未来可以继续探究如何优化DGVAE 模型,并进一步提高链路预测模型的性能,以满足日益增长的网络规模和复杂性的挑战。
由于无监督学习模型能够有效挖掘和分析各种高维数据的潜在特征,本文提出了一种新的链路预测算法,该算法融合了抗噪机制的图变分自编码器。该算法首先通过训练神经网络结构,使其能够对数据进行降噪,然后将完整的训练集输入到已训练好的网络结构中,以实现链路预测功能。本文通过对比实验测试了不同类型的网络,结果表明,该算法在预测准确性和鲁棒性方面均具有优势,同时也为未来链路预测研究提供了新思路。尽管本文的研究存在一些局限性,例如当网络规模较大时,神经网络结构间的隐含特征会增多,从而可能导致预测准确性波动,但是未来的工作将会更深入地研究复杂网络规模和神经网络结构之间的相互影响关系,以进一步提高算法的预测能力。