深蓝学院-GNN课程笔记07-图上的其他深度学习模型
这个系列是深蓝学院图深度学习理论与实践的同步课程笔记。课程内容涉及图深度学习的基础理论与应用，本节主要介绍图神经网络之外的其它深度学习模型。
图上的循环神经网络
循环神经网络(recurrent neural networks, RNN)是处理序列数据的常用模型，而在LSTM则是RNN中最为常用的变体，它通过引入单元状态(cell state)来解决RNN难以处理长序列的问题。RNN和LSTM的基本流程可参考循环神经网络一节。
接下来我们考虑把LSTM拓展到图结构数据中。假设图数据可以使用表示为一棵树，我们只需要让每个子节点向父节点传递自身的信息即可，此时LSTM的流程为：
\[\tilde{h}^{(k)} = \sum_{v_j \in N_c(v_k)} h^{(j)}\] \[i_k = \sigma(W_i x^{(k)} + U_i \tilde{h}^{(k)} + b_i)\] \[o_k = \sigma(W_o x^{(k)} + U_o \tilde{h}^{(k)} + b_o)\]需要注意的是此时每个子节点\(v_j\)向父节点\(v_k\)传递的信息都有自身对应的遗忘门\(f_{kj}\)：
\[f_{kj} = \sigma(W_f x^{(k)} + U_f h^{(j)} + b_f)\]在更新单元状态时需要将来自每个子节点的信息加权求和：
\[\tilde{C}^{(k)} = \tanh (W_c x^{(k)} + U_c \tilde{h}^{(k)} + b_c)\] \[C^{(k)} = i_k \odot \tilde{C}^{(k)} + \sum_{v_j \in N_c(v_k)} f_{kj} \odot C^{(j)}\] \[h^{(k)} = o_k \odot \tanh (C^{(k)})\]
不难发现Tree-LSTM与标准LSTM没有本质区别，只需要在隐状态以及单元状态的信息传播时需要将子节点传递的信息进行加权求和即可。
图上的自编码器
自编码器(autoencoder)是一种经典的无监督学习方法，通常用来获得输入数据的低维压缩表示。在自编码器中输入数据通过编码器(encoder)转换为一个低维的表示，然后在通过解码器(decoder)来重建原始输入，最后通过最小化原始输入与重建结果之间的差异来实现模型训练。
我们可以通过自编码器来获得图上节点向量的低维表示，首先记编码器和解码器的输出分别为：
\[z_i = f_\text{enc} (a_i, \Theta_\text{enc})\] \[\hat{a}_i = f_\text{dec} (z_i, \Theta_\text{dec})\]因此得到自编码器的重构损失为：
\[L_\text{enc} = \sum_{v_i \in V} \Vert a_i - \hat{a}_i \Vert_2^2\]除此之外，我们希望相邻节点压缩后的节点向量仍然是相似的，为此可以构造相邻节点的正则项损失：
\[L_\text{con} = \sum_{v_i, v_j \in V} A_{ij} \cdot \Vert z_i - z_j \Vert_2^2\]类似地，两个GNN都有各自的正则项：
\[L_\text{reg} = \Vert \Theta_\text{enc} \Vert_2^2 + \Vert \Theta_\text{dec} \Vert_2^2\]最后将这些损失组合到一起就得到了图上自编码器的损失函数：
\[L = L_\text{enc} + \lambda \cdot L_\text{con} + \eta \cdot L_\text{reg}\]
除了对节点特征进行低维重建外我们还可以对图结构进行重建。首先通过一个GNN作为编码器来获得低维的节点表示：
\[Z = f_\text{GNN} (A, F, \Theta)\]然后利用低维节点向量\(Z\)来重建邻接矩阵：
\[\hat{A} = \sigma(Z Z^T)\]进行自编码器的训练时只需要最小化\(A\)与\(\hat{A}\)之间的二分类误差即可：
\[L = -\sum_{v_i, v_j \in V} \bigg( A_{ij} \log \hat{A}_{ij} + (1 - A_{ij}) \log (1 - \hat{A}_{ij}) \bigg)\]
图上的变分自编码器
变分自编码器(variational autoencoder, VAE)是一种生成式模型。在VAE中输入数据\(x\)经过编码器\(q(z \vert x; \Phi)\)得到一个正态分布\(N(\mu, \sigma)\)，然后从这个正态分布中采样出一个样本\(z\)并利用它来重建输入\(p(x \vert z; \Theta)\)。
VAE可以用来学习图上的节点表示，此时编码器将每个节点都编码为一个多元正态分布：
\[\boldsymbol{\mu} = f_\text{GNN} (F, A, \Theta_\mu)\] \[\log \boldsymbol{\sigma} = f_\text{GNN} (F, A, \Theta_\sigma)\]然后类似于自编码器，在解码阶段重建图的邻接矩阵：
\[p(A_{ij} = 1 \vert z_i, z_j) = \sigma(z_i z_j^T)\]其中\(z_i\)、\(z_j\)由编码器计算出的正态分布进行采样来获得。
除了对节点向量进行表示之外VAE还可以进行图生成，此时我们需要对整个图进行编码：
\[\boldsymbol{\mu} = \text{pool} (f_\text{GNN} (F, A, \Theta_\mu))\] \[\log \boldsymbol{\sigma} = \text{pool} (f_\text{GNN} (F, A, \Theta_\sigma))\]然后在解码阶段利用采样后的隐变量来重建图：
\[\tilde{G} = \{ \tilde{A}, \tilde{F}, \tilde{E} \} = f_\text{MLP} (z; \Theta)\]图上的生成对抗网络
生成对抗网络(generative adversarial network, GAN)是目前非常火热的生成式模型。在GAN中模型可以分为生成器(generator)和判别器(discriminator)两部分，其中生成器用来从噪声中生成伪造的数据，而判别器则需要区分真实样本和生成器的结果。整个GAN的模型架构如下图所示：
在训练GAN时首先将真实数据标记为正例、生成器的输出标记为反例，以此来训练判别器：
\[\max \mathbb{E}_{x \sim p_\text{data}(x)} [\log D(x; \Phi)] + \mathbb{E}_{z \sim p(z)} [\log (1 - D(G(z; \Theta)))]\]当判别器收敛时固定判别器的参数来训练生成器：
\[\min \mathbb{E}_{x \sim p_\text{data}(x)} [\log D(x; \Phi)] + \mathbb{E}_{z \sim p(z)} [\log (1 - D(G(z; \Theta)))]\]这样依次交替训练，直到判别器无法区分真实数据和生成的数据为止，此时可以认为生成器已经能够产生以假乱真的数据了。
GAN可以用于节点表示学习。对于给定节点\(v_i\)，生成器试图从\(V\)中选择一个最可能和它连接的节点，而判别器则需要区分\(v_i\)采样出的「邻居」与真实的邻居。此时生成器和判别器可以分别表示为：
\[G(v_j \vert v_i; \Theta) = \frac{\exp (\theta_j^T \theta_i)}{\sum_{v_k \in V} \exp (\theta_k^T \theta_i)}\] \[D(v_j \vert v_i; \Phi) = \frac{1}{1 + \exp (-\phi_j^T \phi_i)}\]GAN同样可以进行图生成，此时生成器从正态分布的噪声中生成节点特征\(\tilde{F}\)和边类型概率矩阵\(\tilde{E}\)，而判别器则是对全图进行二分类。
