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

• 前言
• 1. GAE
• • 1.1 变量定义
  • 1.2 编码器
  • 1.3 解码器
• 2. VGAE
• • 2.1 编码器
  • 2.2 解码器
• 3. 实验

题目： Variational Graph Auto-Encoders
会议： NeurIPS 2016
论文地址：Variational Graph Auto-Encoders

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

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

图 G = ( V , E ) mathcal{G}=(mathcal{V}, mathcal{E}) G=(V,E)， N = ∣ V ∣ N=|mathcal{V}| N=∣V∣表示节点个数，增加了自环的邻接矩阵 A A A及其度矩阵 D D D，最终得到的节点表示向量为 Z ∈ R N × f Z in R^{N times f} Z∈RN×f，初始时节点特征矩阵为 X ∈ R N × d X in R^{N times d} X∈RN×d。

GAE中的编码器是一个简单的两层GCN，即：
Z = G C N ( A , X ) Z=GCN(A,X) Z=GCN(A,X)
更具体地讲，两层的GCN在论文中被定义如下：
G C N ( A , X ) = A ~ R E L U ( A ~ X W 0 ) W 1 GCN(A,X)=tilde{A}mathbf{RELU}(tilde{A}XW^{0})W^{1} GCN(A,X)=A~RELU(A~XW0)W1
其中 A ~ = D − 1 2 A D − 1 2 tilde{A}=D^{-frac{1}{2}}AD^{-frac{1}{2}} A~=D−21​AD−21​，即对称归一化邻接矩阵， W 0 W^0 W0和 W 1 W^1 W1是GCN的参数，需要学习。

简单来说，通过编码器，我们得到了节点的嵌入向量 Z ∈ R N × f Z in R^{N times f} Z∈RN×f，其中 z i ∈ R f z_i in R^f zi​∈Rf表示节点 i i i的表示向量。

编码器得到节点表示向量后，解码器通过表示向量的内积来重构邻接矩阵：
A ^ = σ ( Z Z T ) hat{A}=sigma(ZZ^T) A^=σ(ZZT)
其中 Z ∈ R N × f Z in R^{N times f} Z∈RN×f，所以 Z Z T ∈ R N × N ZZ^T in R^{N times N} ZZT∈RN×N，与邻接矩阵维度一致。

在GAE中，我们需要优化编码器中的 W 0 W^0 W0和 W 1 W^1 W1，进而使得经解码器重构出的邻接矩阵 A ^ hat{A} A^与原始的邻接矩阵 A A A尽量相似。因为邻居矩阵决定了图的结构，经节点向量表示重构出的邻接矩阵与原始邻接矩阵越相似，说明节点的向量表示越符合图的结构。

因此，GAE中的损失函数可以定义如下：
L = − 1 N ∑ ( y l o g y ^ + ( 1 − y ) l o g ( 1 − y ^ ) ) mathcal{L}=-frac{1}{N}sum (yloghat{y}+(1-y)log(1-hat{y})) L=−N1​∑(ylogy^​+(1−y)log(1−y^​))
这里 y y y表示原始邻接矩阵 A A A中的元素，其值为0或1； y ^ hat{y} y^​为重构的邻接矩阵 A ^ hat{A} A^中的元素。

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

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

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

编码器又被称为Inference model，即推理模型。在GAE中，可训练的参数只有 W 0 W^0 W0和 W 1 W^1 W1，训练结束后只要输入邻接矩阵 A A A和节点特征矩阵 X X X，就能得到节点的向量表示 Z Z Z。

与GAE不同，在变分图自编码器VGAE中，节点向量 Z Z Z不是由一个确定的GCN得到，而是从一个多维高斯分布中采样得到。

多维高斯分布的均值和方差由两个GCN确定：
μ = G C N μ ( X , A ) mu=GCN_{mu}(X,A) μ=GCNμ​(X,A)
以及
l o g   σ = G C N σ ( X , A ) log sigma=GCN_{sigma}(X,A) log σ=GCNσ​(X,A)
在原始论文中，两个GCN都是两层，且第一层的参数 W 0 W^0 W0是共享的。

有了均值和方差后，我们就能唯一地确定一个多维高斯分布，然后从中进行采样以得到节点的向量表示 Z Z Z，也就是说，向量表示的后验概率分布为：
q ( Z ∣ X , A ) = ∏ i = 1 N q ( z i ∣ X , A ) q(Z|X,A)=prod_{i=1}^Nq(z_i|X,A) q(Z∣X,A)=i=1∏N​q(zi​∣X,A)
这里
q ( z i ∣ X , A ) = N ( z i ∣ μ i , d i a g ( σ i 2 ) ) q(z_i|X,A)=mathcal{N}(z_i|mu_i,diag(sigma_i^2)) q(zi​∣X,A)=N(zi​∣μi​,diag(σi2​))
其中 μ i mu_i μi​和 σ i 2 sigma_i^2 σi2​分别表示节点向量的均值和方差。

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

不过，采样操作无法提供梯度信息，这对神经网络来讲是没有意义的，因此作者做了重采样：
z = μ + ϵ σ z=mu+epsilon sigma z=μ+ϵσ
这里 ϵ epsilon ϵ服从 N ( 0 , 1 ) mathcal{N}(0,1) N(0,1)，也就是标准高斯分布，因为 ϵ epsilon ϵ服从标准高斯分布，所以 μ + ϵ σ mu+epsilon sigma μ+ϵσ服从 N ( μ , σ 2 ) mathcal{N}(mu,sigma^2) N(μ,σ2)。

解码器又被称为Generative model，即生成模型。解码器通过计算图中任意两个节点间存在边的概率来重构图：
P ( A , Z ) = ∏ i = 1 N ∏ j = 1 N p ( A i j ∣ z i , z j ) P(A,Z)=prod_{i=1}^Nprod_{j=1}^Np(A_{ij}|z_i,z_j) P(A,Z)=i=1∏N​j=1∏N​p(Aij​∣zi​,zj​)
这里
p ( A i j = 1 ∣ z i , z j ) = σ ( z i T z j ) p(A_{ij}=1|z_i,z_j)=sigma(z_i^Tz_j) p(Aij​=1∣zi​,zj​)=σ(ziT​zj​)
也就是说，解码器通过计算任意两个节点向量表示的相似性来重建图结构。

损失函数由两部分组成：

第一部分与GAE中类似，为交叉熵函数，也就是经分布 q q q得到的向量重构出的图与原图的差异，这种差异越小越好；第二部分表示利用GCN得到的分布 q q q与标准高斯分布 p ( Z ) p(Z) p(Z)间的KL散度，也就是要求分布 q q q尽量与标准高斯分布相似。

其中：
p ( Z ) = ∏ i = 1 N p ( z i ) = ∏ i = 1 N p ( z i ∣ 0 , I ) p(Z)=prod_{i=1}^{N}p(z_i)=prod_{i=1}^{N}p(z_i|0,I) p(Z)=i=1∏N​p(zi​)=i=1∏N​p(zi​∣0,I)
为标准高斯分布。

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