Variational graph auto-encoders (VGAE)

Graph Auto-Encoders (GAE)

Definitions

• 给定一个无向无权图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$，$N=|\mathcal{V}|$ 为顶点数，$\mathbf{A}\in {\mathbb{R}}^{N\times N}$ 为邻接矩阵 (对角线元素为 1)，$\mathbf{X}\in {\mathbb{R}}^{N\times D}$ 为结点的特征向量

---

Graph Auto-Encoders

• GAE 中的 Encoder 为 GCN，它负责由邻接矩阵和结点特征编码得到每个结点的 embedding 向量 $z_i$ ($i=1,...,N$)，它们构成了结点 embedding 矩阵 $\mathbf{Z}\in {\mathbb{R}}^{N\times F}$
• GAE 中的 Decoder 为一个简单的 inner product decoder，它负责由结点的 embedding 向量 $\mathbf{Z}$ 来重构邻接矩阵 $\hat{\mathbf{A}}$。它通过计算 $\sigma (z_i^T{z}_j)$ 来决定 ${\hat{\mathbf{A}}}_{ij}$
  

---

A framework for unsupervised learning on graph-structured data

• GAE 引入自编码器来处理图数据，可以基于图数据进行无监督学习

Variational graph auto-encoders (VGAE)

• VGAE 在 GAE 的基础上进一步引入了 变分自编码器 (VAE) 的思想，对 latent space 施加正则化来保证一个 regular latent space
  

---

• VGAE 假设先验概率服从标准正态分布
  $$p(\mathbf{Z})=\prod _{i}p(z_i)=\prod _i\mathcal{N}(z_i|0,\mathbf{I})$$
• 似然由点积模型得到
  
• 后验概率由变分推理近似得到，概率分布族为协方差矩阵为对角矩阵的正态分布
  其中，$\mu ={\text{GCN}}_{\mu }(\mathbf{X},\mathbf{A})$ 为 GCN 输出的后验概率分布均值向量，$\log \sigma ={\text{GCN}}_{\sigma }(\mathbf{X},\mathbf{A})$ 为 GCN 输出的后验概率分布标准差的对数。$\text{GCN}$ 为一个简单的 2 层 GCN，可以被表示为 $\text{GCN}(\mathbf{X},\mathbf{A})=\tilde{\mathbf{A}}\text{RELU}(\tilde{\mathbf{A}}\mathbf{X}{\mathbf{W}}_0){\mathbf{W}}_1$，其中 ${\mathbf{W}}_i$ 为 MLP 权重矩阵，$\tilde{\mathbf{A}}={\mathbf{D}}^{-\frac{1}{2}}\mathbf{A}{\mathbf{D}}^{-\frac{1}{2}}$ 为归一化的邻接矩阵，$\mathbf{D}$ 为度矩阵 (一个对角矩阵，对角元素为各个顶点的度数)，左乘 ${\mathbf{D}}^{-\frac{1}{2}}$ 会使得 $\mathbf{A}$ 的第 $i$ 行除以结点 $i$ 度数的根号，右乘 ${\mathbf{D}}^{-\frac{1}{2}}$ 会使得 $\mathbf{A}$ 的第 $i$ 列除以结点 $i$ 度数的根号，因此 ${\tilde{\mathbf{A}}}_{ij}={\mathbf{A}}_{ij}/(\sqrt{{\mathbf{D}}_{ii}{\mathbf{D}}_{jj}})$，相当于是给邻接矩阵根据度数做了一个归一化。$\tilde{\mathbf{A}}\mathbf{X}=\left[\begin{array}{c}{\tilde{a}}_1^T\mathbf{X}\\ ...\\ {\tilde{a}}_N^T\mathbf{X}\end{array}\right]$ 是在进行结点的信息聚合。${\text{GCN}}_{\mu }(\mathbf{X},\mathbf{A})$ 和 ${\text{GCN}}_{\sigma }(\mathbf{X},\mathbf{A})$ 共享第一层的权重 ${\mathbf{W}}_0$
• 由变分推理得到的优化问题为最大化下式：
  

References

• Kipf, Thomas N., and Max Welling. “Variational graph auto-encoders.” arXiv preprint arXiv:1611.07308 (2016).
• Wu, Zonghan, et al. “A comprehensive survey on graph neural networks.” IEEE transactions on neural networks and learning systems 32.1 (2020): 4-24.
• code: https://github.com/DaehanKim/vgae_pytorch