Mathematics2022-Network Embedding Algorithm Taking in Variational Graph AutoEncoder

唔仄lo咚锵

发布于 2023-03-26 09:35:57

8740

文章被收录于专栏：blog(为什么会重名，真的醉了)blog(为什么会重名，真的醉了)

文章目录

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。

介绍

Chen, Dongming, et al. “Network embedding algorithm taking in variational graph autoencoder.” Mathematics 10.3 (2022): 485.

属性网络在现实世界中被广泛的用于建模实体间的连接，其中节点的联通边表示对象之间的关系以及关于节点本身的描述中节点的属性信息。举了3个例子：

引文网络边表示作者文章之间的引用关系，节点属性信息描述文章的主题、关键词等。
社交网络边表示人与人点之间的人际关系，节点属性还包含用户档案、邮件、发布的文字图片视频等。
蛋白质网络边表示蛋白质相互作用的关系，每个节点还具有生物中蛋白质的属性信息。

总而言之，分析和挖掘属性网络，进行决策和挖掘有用信息是十分具有学术和商业价值的。包括应用于下游任务，如节点分类、链路预测、可视化等。

属性网络嵌入使得网络的拓扑结构信息和节点属性信息得到保留，如图1所示，在只考虑网络结构的基础上，通过利用节点属性信息增强节点向量表示，进一步提高了下游任务的准确性。

文章通过GAE算法，引出了一些问题：

如果词表太大，具有较高的稀疏性和巨大的算法复杂性。
直接利用特征矩阵作为输入，没有充分反映或利用节点属性信息。
GAE采用单一的映射方法生成节点嵌入向量，且没有考虑属性信息的重构损失。

为了解决这些问题，文章提出了一种采用变分图自编码器的网络嵌入算法(NEAT-VGA)。其主要思想是：

对属性特征预处理利用MHRWAE算法学习属性网络中节点的属性特征，将得到的属性特征于邻接矩阵一同作为输入。
变分自编码器学习通过输入生成潜在向量的高斯分布，并对高斯分布进行采样，得到嵌入向量。

最后在链路预测任务上进行了实验，本算法显示出更好的性能。

MHRWAE

基于随机游走得嵌入算法对节点序列将进行随机采样，使得采样后的序列在很大程度上偏向节点，训练过程中没有考虑节点的属性信息。因此提出了MHRWAE算法，它是NEAT-GAT的一个模块，其主要功能是对属性网络中节点属性特征进行预处理。

MHRWAE算法的框架如图3所示，其主要思想是若网络中的某些节点具有相似属性且邻居节点的属性分布相似，则它们在网络中的嵌入也应相似。如图示步骤：

生成固定长度的序列使用MHRW算法执行无偏的随机游走，生成固定长度的序列。采用了MH算法中的转移概率矩阵，表示当前节点采样到其相邻节点的概率。假设MH算法给出的概率分布为：

\pi_v=1/|V|

，选择概率为

Q_{i,j}=1/d_i

，那么从节点

转移到其邻居节点

的概率为：

\begin{equation}p_{i,j}=\frac{1}{d_i}×min(1,\frac{d_i}{d_j}),i\neq j\end{equation}

其中

p_{i,i}=1-p_{i,j}

，

d_i

和

d_j

分别表示节点

和

的度，

p_{i,i}

表示节点

停留在当前节点的概率。

生成语料库(corpus) 利用网络结构信息，使用多组节点和节点邻域属性作为SGNS训练的语料库。语料库是使用邻域节点属性聚合生成的，对于序列中的每个节点，节点及其邻域节点的属性被配对并添加到多集中，序列中的每一个节点完成迭代节点属性聚合操作以形成最终语料库。
生成低维嵌入向量使用Doc2Vec模型来训练语料库，Doc2Vec是一个生成文本向量表示的模型，模型中的PV-DBOW方法使得SGNS可以使用语料库作为输入。使用Doc2Vec模型训练语料库，得到每个节点的向量表示。

NEAT-VGA

NEAT-VGA框架如图2，包括：

Node Attribute Feature Learning
Attribute Network Encoder
Structure Reconstruction Decoder
Attribute Reconstruction Decoder
Loss Function Definition

节点属性特征学习

也就是使用上述的MHRWAE算法对节点属性进行预处理，即由MHRW算法采样、节点序列生成语料库和Doc2Vec模型训练得到节点属性向量。学习到的节点属性中包括其相邻节点的属性，因此，每个节点的属性都是一个属性句子，句子中的单词是节点的属性和相邻节点的属性。最后在Doc2Vec模型上训练，获得每个节点的属性特征向量。

属性网络编码器

将变分自编码器引入图卷积网络GCN中，构建属性网络编码器。 GCN考虑了高阶节点的邻近性，解决了网络稀疏性问题，并通过多层非线性转换捕获数据的非线性信息，GCN每层卷积过程可以用如公式2所示：

\begin{equation}H^{(l+1)}=f(H^{(l)},A|W^{(l)})=\sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})\end{equation}

其中

H^{(l)}

表示第

层卷积层的输入，

H^{(l+1)}

表示第

层卷积层的输出，

\tilde{A}=A+I

，

是邻接矩阵，

\tilde{D}

是

\tilde{A}

的度矩阵，

\sigma

表示非线性激活函数，比如Relu。

在编码这一步，NEAT-VGA算法获得了每个节点的高斯分布，高斯分布有均值

\mu

和方差

\sigma

唯一确定，通过对高斯分布采样获得嵌入向量，而GCN编码就是获得

\mu

和

\sigma

的过程。

具体来说，GCN的前两层共享参数

W^{(0)}

和

W^{(1)}

来提前特征，前两层被用作属性网络编码器。第三层权重参数

W^{(2)}

及

W^{(3)}

，获得

\mu

和

log\sigma

，每层的激活函数使用的是Relu，具体如下公式：

\begin{equation}H^{(1)}=f_{relu}(F,A|W^{(0)}),\end{equation}

\begin{equation}H^{(2)}=f_{relu}(H^{(1)},A|W^{(1)}),\end{equation}

\begin{equation}\mu=H^{(3)}=f_{relu}(H^{(2)},A|W^{(2)}),\end{equation}

\begin{equation}log\sigma=H^{(4)}=f_{relu}(H^{(2)},A|W^{(3)}),\end{equation}

根据

\mu

和KaTeX parse error: Undefined control sequence: \siama at position 1: \̲s̲i̲a̲m̲a̲确定每个节点的高斯分布后，进行采样得到嵌入向量矩阵

Z=\in R^{|V|×n}

，如式7：

\begin{equation}Z=\mu+\epsilon\sigma\end{equation}

其中，

\epsilon

服从标准分布

N(0,1)

，

服从分布

N(\mu,\sigma^2)

也就是先从标准分布中随机采样一个

\epsilon

，然后根据公式计算

，最后根据梯度下降和反向传播迭代获得新的

\mu

和

\sigma

。

（~~插播反爬信息~~ ）博主CSDN地址：https://wzlodq.blog.csdn.net/

结构重建解码器

编码得到嵌入向量矩阵

后，便可根据式8求得重建后的邻接矩阵

：

\begin{equation}B=sigmoid(Z×Z^T)\end{equation}

得到学习到的重建后的新邻接矩阵

后，下面是损失函数的定义，预测两个节点间是否存在一条边，文章将其看作一个二分类问题，然后使用原矩阵

进行监督：

\begin{equation}\mathcal{L}_s=d_s(A,B)=-(\sum ylog\hat{y}+(1-y)log(1-\hat{y}))/N\end{equation}

其中，

表示原邻接矩阵

中第

行

列的值，值域0到1之间，表示原图中节点

是否有一条边到节点

，同理

\hat{y}

是重建后矩阵

的。

表示预测连接边的数量。最后套入交叉熵损失函数中。

属性重建解码器

使用GCN作为属性解码器，也就是在原来三层GCN编码器获得

之后，再连接一层GCN，输出重建后的属性矩阵

\Gamma

，预测原网络中每个节点的属性信息：

\begin{equation}\Gamma=f_{relu}(Z,A|W^{(4)})\end{equation}

然后通过矩阵范数，计算原属性矩阵

和重建后属性矩阵

\Gamma

的误差，损失函数定义如式11：

\begin{equation}\mathcal{L}_a=d_a(F,\Gamma)={||F-\Gamma||}_F\end{equation}

损失函数

使用

散度来计算相对熵，如式12：

\begin{equation}\mathcal{L}_{KL}=KL[q(Z|X,A)||p(Z)]\end{equation}

散度用来描述两个概率分布之间的差异。其中，

q(Z|X,A)

是由先前的GCN编码器计算的概率分布，

p(z)

是先验分布和标准高斯分布。

最终的损失函数如式13，结合了结构重建损失、属性重建损失和KL损失。

\begin{equation}\mathcal{L}=(1-\alpha)\mathcal{L}_s+\alpha\mathcal{L}_a+\mathcal{L}_{KL}\end{equation}

通过最小化损失函数，使得重建后的邻接矩阵及属性矩阵与重建前的相近，并且使GCN嵌入向量的概率分布接近标准高斯分布。

实验

下表是使用数据集的情况：

进行了链路预测实验，随机删除了5%-10%的边作为测试集，使用逻辑回归作为分类器，也就是是否有边的二分类问题，然后使用AUC曲线下面积作为评价指标。还使用了AP指标，也就是precision@k，预测前k条边中多少是真实存在的边，然后取均值得到AP。

然后交代了一些实验参数细节，迭代200轮学习属性特征，属性维度是128维，变分自编码器迭代400轮，嵌入64维，学习率分别是0.05和0.01，超参

\alpha=0.5

。

以下是实验结果：

所以比较的算法都是属性网络嵌入的算法，可以看出本算法NEAT-VGA（图中红色）在链路预测实验中，在这三个数据集上，AUC和AP指标都比其他算法效果更好。

NEAT-VGA算法为什么有所提升，作者总结为以下2点原因：

使用节点属性特征。
图神经网络能更好捕捉图结构和属性特征，有效提前高度非线性信息。

总结

这篇文章提出了一种NEAT-VGA算法，以解决属性网络嵌入高维和稀疏性问题，这些问题会导致算法复杂度增加，且不能很好反映节点属性特征。此外，GAE算法再编码器部分使用了一个简单的映射，并没有考虑节点属性特征。NEAT-VGA算法使用了MHRWAE算法对节点属性预处理，提前节点属性特征。在链路预测实验中取得了更好效果。

但是，NEAT-VGA主要适用于静态网络，缺乏对网络动态变化特征的挖掘，这是未来的研究方向。

个人角度研读，水平有限，更多细节请移步原文。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-03-24，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm