NeurIPS 2016 | VGAE：变分图自编码器

Cyril-KI

发布于 2022-11-10 11:25:25

1.1K0

发布于 2022-11-10 11:25:25

文章被收录于专栏：KI的算法杂记KI的算法杂记

题目：Variational Graph Auto-Encoders

会议：NeurIPS 2016

论文地址：https://arxiv.org/abs/1611.07308

自编码器在图领域有着很多应用，其本质就是编码器获取节点的高级向量表示，然后解码器利用高级向量表示来重建图结构。这篇文章主要介绍Kipf和Welling提出的变分图自编码器模型VGAE，在介绍VGAE之前，首先需要介绍GAE，即图自编码器。

1. GAE

GAE，即Graph Auto-Encoders，图自编码器。

1.1 变量定义

图

\mathcal{G}=(\mathcal{V}, \mathcal{E})

，

N=|\mathcal{V}|

表示节点个数，增加了自环的邻接矩阵

及其度矩阵

，最终得到的节点表示向量为

Z \in R^{N \times f}

，初始时节点特征矩阵为

X \in R^{N \times d}

。

1.2 编码器

GAE中的编码器是一个简单的两层GCN，即：

Z=GCN(A,X)

更具体地讲，两层的GCN在论文中被定义如下：

其中

\tilde{A}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}

，即对称归一化邻接矩阵，

W^0

和

W^1

是GCN的参数，需要学习。

GCN(A,X)=\tilde{A}\mathbf{RELU}(AXW^{0})W^{1}

简单来说，通过编码器，我们得到了节点的向量表示

Z \in R^{N \times f}

，其中

z_i \in R^f

表示节点

的向量表示。

1.3 解码器

编码器得到节点向量表示后，解码器通过表示向量的内积来重构邻接矩阵：

\hat{A}=\sigma(ZZ^T)

其中

Z \in R^{N \times f}

，所以

ZZ^T \in R^{N \times N}

，与邻接矩阵维度一致。

在GAE中，我们需要优化编码器中的

W^0

和

W^1

，进而使得经解码器重构出的邻接矩阵

\hat{A}

与原始的邻接矩阵

尽量相似。因为邻居矩阵决定了图的结构，经节点向量表示重构出的邻接矩阵与原始邻接矩阵越相似，说明节点的向量表示越符合图的结构。

因此，GAE中的损失函数可以定义如下：

\mathcal{L}=-\frac{1}{N}\sum (ylog\hat{y}+(1-y)log(1-\hat{y}))

这里

表示原始邻接矩阵

中的元素，其值为0或1；

\hat{y}

为重构的邻接矩阵

\hat{A}

中的元素。

从上述损失函数可以看出，损失函数的本质就是两个交叉熵损失函数之和。

当然，我们可以对原始论文中的GAE进行扩展，例如编码器可以使用其他的GNN模型。

2. VGAE

VGAE同样包含两部分：编码器和解码器，又被称为推理模型和生成模型。

2.1 编码器

编码器又被称为Inference model，即推理模型。在GAE中，可训练的参数只有

W^0

和

W^1

，训练结束后只要输入邻接矩阵

和节点特征矩阵

，就能得到节点的向量表示

。

与GAE不同，在变分图自编码器VGAE中，节点向量

不是由一个确定的GCN得到，而是从一个多维高斯分布中采样得到。

高斯分布的均值和方差由两个GCN确定：

\mu=GCN_{\mu}(X,A)

以及

log\ \sigma=GCN_{\sigma}(X,A)

在原始论文中，两个GCN都是两层，且第一层的参数

W^0

是共享的。

有了均值和方差后，我们就能唯一地确定一个多维高斯分布，然后从中进行采样以得到节点的向量表示

，也就是说，节点表示向量的后验概率分布为：

q(Z|X,A)=\prod_{i=1}^Nq(z_i|X,A)

这里

q(z_i|X,A)=\mathcal{N}(z_i|\mu_i,diag(\sigma_i^2))

其中

\mu_i

和

\sigma_i^2

分别表示节点向量的均值和方差。

也就是说，通过两个GCN我们得到了所有节点向量的均值和方差，然后再从中采样形成节点向量。具体来讲，编码器得到多维高斯分布的均值向量和协方差矩阵后，我们就可以通过采样来得到节点的向量表示，常见的采样方法有逆变换法(Inverse Transform Method)、拒绝采样法(Rejection Sampling)、重要性采样及其重采样(Importance Sampling, Sampling-Importance-Resampling)、马尔科夫蒙特卡洛采样法(Markov Chain Monte Carlo)等，这里就不细说了。

不过，采样操作无法提供梯度信息，这对神经网络来讲是没有意义的，因此作者做了重采样：

z=\mu+\epsilon \sigma

这里

\epsilon

服从

\mathcal{N}(0,1)

，也就是标准高斯分布，因为

\epsilon

服从标准高斯分布，所以

\mu+\epsilon \sigma

服从

\mathcal{N}(\mu,\sigma^2)

。

2.2 解码器

解码器又被称为Generative model，即生成模型。解码器通过计算图中任意两个节点间存在边的概率来重构图：

P(A,Z)=\prod_{i=1}^N\prod_{j=1}^Np(A_{ij}|z_i,z_j)

这里

p(A_{ij}=1|z_i,z_j)=\sigma(z_i^Tz_j)

也就是说，解码器通过计算任意两个节点向量表示的相似性来重建图结构。

损失函数由两部分组成：

第一部分与GAE中类似，为交叉熵函数，也就是经分布

得到的向量重构出的图与原图的差异，这种差异越小越好；第二部分表示利用GCN得到的分布

与标准高斯分布

p(Z)

间的KL散度，也就是要求分布

尽量与标准高斯分布相似。

其中：

p(Z)=\prod_{i=1}^{N}p(z_i)=\prod_{i=1}^{N}p(z_i|0,I)

为标准高斯分布。

3. 实验

论文实验为链接预测，数据集为几个常见的引用网络数据集，数据集中部分链接被删除，所有节点的特征被保留。实验结果如下表所示：

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-07-13，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自 KI的算法杂记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数据结构

登录后参与评论

0 条评论

热度