论文笔记：Variational Graph Auto-Encoders

前言

本文提出了一种基于图数据类型的无监督学习方法，参考自动编码器(AE)和变分自动编码器(VAE)结合图数据结构的特点，提出了图自动编码器(GAE)和变分图自动编码器(VGAE)。先简单描述一下图自编码器的intention 和用途：获取合适的 embedding 来表示图中的节点不是容易的事，而如果能找到合适的 embedding，就能将它们用在其他任务中。VGAE 通过 encoder-decoder 的结构可以获取到图中节点的 embedding，来支持接下来的任务，如链接预测等。
论文链接：https://arxiv.org/abs/1611.07308
github：https://github.com/DaehanKim/vgae_pytorch

1.介绍

GAE是GCN在Auto-Encoders (AE)的应用，非常容易理解，隐变量Z就是图上的N个节点经过GCN后的N*F维特征，Encoder就是两层GCN, Decoder就是向量点积。可以将隐变量Z理解为某种意义上图的节点的相似度，通过向量点积得到的两个图节点的相似度越大，则两个节点之间存在边的概率越大

VGAE是GCN在Variational Graph Auto-Encoders (VAE)的应用。Encoder用两个两层GCN分别得到N个均值和标准差，这两个GCN会共享第一层的参数，从而得到N个正态分布。Decoder仍然是向量点积

变分图自动编码器（variational graph autoencoder，VGAE），它是基于变分自动编码器（variational auto-encoder，VAE）的无监督学习图结构数据的框架 该模型利用了潜在变量，并且有可能学习无向图的可解释潜在表示

损失函数部分：相较于传统AE和VAE进行像素点之间的MSE，以图结构数据来说对于每个边，VAE会生成一个预测值，与真实值(0/1, 0代表无边，1代表有边）之间的交叉熵函数就是损失函数

本文的实验通过在图学习三大经典数据集：Cora, Citeseer, Pubmed上扔掉一些边来构造数据集，然后预测扔掉的边是否存在。评价指标是AUC和Precision. 对比方法是图谱方法和DeepWalk, 都是图学习领域的经典baseline.

2.图自编码器(GAE)

相关变量如下：

• 图用$G=(V,E)$G=(V,E)表示，其中$V$V表示节点的集合，$E$E表示边的集合
• $A$A：邻接矩阵
• $D$D：度矩阵，文中假设对角线上元素均为1
• $N$N：节点数
• $d$d：节点的特征维度
• $X{\epsilon}{\mathbb{R}}^{N*d}$XϵRN∗d：表示节点的特征矩阵
• $f$f：embedding 维度
• $Z{\epsilon}{\mathbb{R}}^{N*f}$ZϵRN∗f：节点的 embedding

2.1 Encoder

GAE 使用 GCN 作为 encoder，来得到节点的 latent representations（或者说 embedding），这个过程可用一行简短的公式表达：
、
将$GCN$GCN视为一个函数，然后将$X$X和$A$A作为输入，输入到$GCN$GCN函数中，输出$Z{\epsilon}{\mathbb{R}}^{N*f}$ZϵRN∗f，$Z$Z代表的就是所有节点的 latent representations，或者说 embedding。$GCN$GCN的函数定义如下
从公式上可以看出，整个encoder只有两层，每一层采用的均是切比雪夫多项式的一阶近似作为卷积核处理数据。从中可以看出除了初始的输入$X$X也就是表示节点的特征矩阵，剩下的参数均是需要学习的对象。简言之，这里$GCN$GCN就相当于一个以节点特征和邻接矩阵为输入、以节点 embedding 为输出的函数，目的只是为了得到 embedding。

2.2 Decoder

GAE 采用 inner-product 作为 decoder 来重构（reconstruct）原始的图：

所得就是重构出来的邻接矩阵，根据此邻接矩阵和原图的信息特征就可以构造损失函数

2.3 GAE的损失函数

邻接矩阵决定了图的结构，应该使重构出的邻接矩阵与原始的邻接矩阵尽可能的相似。因此，GAE 在训练过程中，采用交叉熵作为损失函数：

上式中，$y$y代表邻接矩阵$A$A中某个元素的值（0 或 1），$\hat{y}$y^​代表重构的邻接矩阵$\hat{A}$A^中相应元素的值（0 到 1 之间）。从损失函数可以看出来，希望重构的邻接矩阵（或者说重构的图），与原始的邻接矩阵（或者说原始的图）越接近、越相似越好。

可以看出，在此篇文章中重视的是连接预测

2.4 小结

图自编码器（GAE）的原理简明、清晰，训练起来不麻烦，因为可训练的参数只有$W_1$W1​和$W_2$W2​，kipf 的代码实现中，这两个参数矩阵的维度分别是$d*32$d∗32和$32*16$32∗16，如果 $d=1000$d=1000，也只有 32512 个参数，相当少了。

3. 变分图自编码器(VGAE)

相关变量如下：

• 图用$G=(V,E)$G=(V,E)表示，其中$V$V表示节点的集合，$E$E表示边的集合
• $A$A：邻接矩阵
• $D$D：度矩阵，文中假设对角线上元素均为1
• $N$N：节点数
• $d$d：节点的特征维度
• $X{\epsilon}{\mathbb{R}}^{N*d}$XϵRN∗d：表示节点的特征矩阵
• $f$f：embedding 维度
• $Z{\epsilon}{\mathbb{R}}^{N*f}$ZϵRN∗f：节点的 embedding

在 GAE 中，一旦$GCN$GCN中的$W_0$W0​和$W_1$W1​确定了，那么$GCN$GCN就是一个确定的函数，给定$X$X和$A$A，输出的$Z$Z就是确定的。

而在 VGAE 中，$Z$Z不再由一个确定的函数得到，而是从一个（多维）高斯分布中采样得到，说得更明确些，就是先通过$GCN$GCN确定一个（多维）高斯分布，再从这个分布中采样得到$Z$Z。下面简单描述一下这个过程。

3.1 确定均值和方差

高斯分布可以唯一地由二阶矩确定。因此，想要确定一个高斯分布，只需要知道均值和方差。VGAE 利用$GCN$GCN来分别计算均值和方差：

这里有两个要注意的地方，第一个是$GCN$GCN的下标,$GCN_{\mu}$GCNμ​和$GCN_{\sigma}$GCNσ​中的$W_0$W0​共享但$W_1$W1​是不同的，因此用下标来作区分；第二个是通过$GCN_{\sigma}$GCNσ​得到的是$log_{\sigma}$logσ​，这样可以方便后续的计算。

3.2 采样

既然已经得到了均值和方差（准确来说应该是均值向量和协方差矩阵），就可以通过采样得到$Z$Z了，但是，采样操作无法提供梯度信息，也就是说，反向传播在采样操作无法计算梯度，也就无法更新 $W_0$W0​和$W_1$W1​。解决办法是重参数化（reparameterization）。

重参数化
如果$\epsilon$ϵ服从$N(0,1)$N(0,1)，那么$z=\mu+\epsilon\sigma$z=μ+ϵσ就服从$N(\mu,\sigma^2)$N(μ,σ2)。因此，可以先从标准高斯中采样一个$\epsilon$ϵ，再通过$\mu+\epsilon\sigma$μ+ϵσ计算出$z$z，这样一来，$z$z的表达式清晰可见，梯度信息也就有了。

VGAE 的 decoder 也是一个简单的 inner-product，与 GAE 的 decoder 没有区别。

3.3 损失函数

基本思想与VAE思想相同，这是文中采用的优化目标

这是用变分下界写出的优化目标，第一项是期望，第二项是 KL 散度。

4.实验

VGAE和GAE模型在几种流行的引用网络数据集的链接预测任务上学习有意义的潜在嵌入的能力。 在这些数据集的不完整版本上训练模型，其中部分引用链接（边）已被删除，同时保留了所有节点特征。 我们从先前删除的边缘和相同数量的未连接节点（非边缘）的随机采样对中形成验证和测试集。
  我们根据模型正确分类边缘和非边缘的能力来比较模型。验证集和测试集分别包含5％和10％的引用链接。验证集用于优化超参数。我们与两种流行的基准进行比较：频谱聚类（SC）和DeepWalk（DW）。 SC和DW均提供节点嵌入Z。
  对于VGAE和GAE，初始化权重。使用Adam 以0.01的学习率训练200次迭代。在所有实验中，我们都使用32维隐藏层和16维潜在变量。对于SC，嵌入尺寸为128。对于DW，即嵌入尺寸为128，随机游走10次。每个节点的长度为80，上下文大小为10，针对单个时期进行了训练。
  
Kipf 和 Welling 在三个数据集上进行了效果分析，任务是链接预测，详情见下表：

可见，（变分）图自编码器在三个数据集上的效果都很好，不过，注意带星号的 GAE* 和 VGAE*，这两个模型是不带 input features 的，就是说节点的 features 就是 one-hot 向量，这种情况下，（变分）图自编码器的效果不仅不比 SC 和 DW 好，甚至还有点差。不过，Kipf 和 Welling 在论文中指出，SC 和 DW 不支持 input features，因此能够使用 input features 是 VGAE 的特点之一。

以上是对图自编码器的开山论文 Variational Graph Auto-Encoders 的介绍，接下来看看图自编码器在最近两年的一些应用。