Graph Generation

在之前的一节课里面我们所讨论的问题是如何对于Graph进行Encode，那么现在所处理的问题就是如何进行Decode，或者说，如何生成一个Graph

生成一个图的任务其实也是非常有意义的任务，比如说可以通过生成图帮助探索某些未知的结构，给科学人员一些启发。但是这个问题也是一个非常难的问题，首先生成式的问题本身即是一个非常困难的问题，这一点在文本和图片的处理之中就可以看出来，其次在GNN之中，我们对于图的结构也同样是有要求的。而在图之中还有一个非常困难的事情就是在节点之中是有顺序这一说的，而由于网络的结构的关系，两个结构一样的图可能他们的表达的方式是截然不同的，比如说

而且在图之中依旧是需要有长距离的依赖的(Long – Range Dependencies)，比如说生成一个Ring Graph

在这里生成第六个点的时候，第六个点是否与第一个点连接是一个需要第一个点的信息的，也就是说第六个点的时候还要第一个点的依赖关系。长度为6还好，但是如果一个极大的图，到了几百步上千步的时候，这个依赖则就有些力不从心了。

ML Basic for Graph Generation

我们先看看普通的机器学习的方式对于图的生成有什么方法。首先明确目标,是通过$P_{data}(G) \to P_{model}(G)$

也就是说假设$p_{data}(x)$是数据的分布，这个分布是我们永远无法得到的分布，我们所可以得到的只有他的一个Sample也就是我们的训练数据集，而$p_{model}(x;\theta)$则是我们用来拟合真实分布的模型的分布。我们的目标也就是很简单，尽量的使得模型的分布接近于数据的分布，并且使得模型的分布是尽可能的简单的被Sample。

那么怎么处理呢？我们使用的方法是MLE来做，也就是极大化似然函数

$$\theta^*  = \arg \max_{\theta} E_{x\sim p_{data}} \log p_{model}(x|\theta)$$

那么怎么从$p_{model}(x;\theta)$之中进行Sample呢?

在VAE之中我们就有一个方法，先从正态分布之中选择一个Sample的值，然后使用一个变换将这个值处理一下，那么这个正态分布就变得复杂了，那么什么样的处理可以使得其变复杂呢？直接上神经网络吧。那么确认完之后，我们就可以着手处理这个函数了，我们使用的基本模型是AutoRegression 模型，那么

$$p_{model}(x;\theta) = \prod_{t=1}^{n} p_{model} (x_t|x_1,\cdots ,x_{t-1};\theta)$$

好了现在完事具备了，就差如何寻找到一个合适的$p_{model}$的表达的形式了。

那么对于序列化的数据，我们的一个很直观的想法就是使用RNN来做，那么这个既然是对于图进行操作，我们就称之为是GraphRNN

生成图的过程如上所示，也就是逐渐生成Node以及其对应的边过程。那么由于图的顺序有任意性，所以在正式的进行处理模型的时候，我们需要对于节点标记一个指定的顺序。按照这个顺序进行处理

那么在上一段说了，生成图有两个过程，分别是Node以及Edge这两个过程，我们也就按照这个思路来分别看看Node-Level以及Edge-Level的过程进行建模

文中使用的方法称为是Graph RNN，先看看模型

这里的有两个过程，Node-Level的RNN生成，其为Edge-Level的RNN的初始状态提供输入，而上一个状态的Edge-Level对于下一个节点的Node的State也会进行Update，有点抽象，我们看看具体的方式，对于每一个RNN

当然这里可以改成GRU或者是LSTM都是OK的。那么如何把这些RNN Cell连接起来呢？

很简单，和普通的RNN一样，将上一个单元的输出作为下一个单元的输入。

但是这里有一个问题就是在这里的模型的鲁棒性不强，也就是不够Robust，那么怎么增强呢？很简单，通过概率分布的形式就行了。

令$y_t = p_{model}(x_t| x_{1},\cdots,x_{t-1}; \theta)$

那么$x_{t+1}$则是从$y_{t}$之中进行Sample的一个结果，也就是以概率为$y_{t}$的伯努利实验，看是1还是0.

那么模型就会变成上面的这个样子。那么我们怎么进行训练呢？在训练的时候的机制有一些奇怪，在这里叫做是Teacher Forcing机制，也就是使用真实的Input 和Output计算Loss，即

$$L = -[y_{1}^* \log (y_1) + (1-y_{1}^{*}) \log (1-y_1)]$$

替代BCE进行处理。然后就是再加Edge Generation的话

可以看看这里的过程，通过Node RNN之后将状态传输到Edge RNN之中，然后Edge RNN吐出一个状态，就是判断是否连接这个边，再与后面的状态连接。

但是这样的方法一个很显然的问题就是在处理长序列的问题的时候要记忆的东西有一些过于复杂了，所以做一些简化的操作也就是使用BFS的方法来对于网络进行连接

通过这样的方式就可以将记忆的空间大幅度的减少，因为只默认其与之前的三个节点进行连接。不过这样的问题倒也是直接的，就是很有可能会漏掉一些边，但是如果看看整个网络的生成过程的话，那么这个问题应该也并不是一个非常严重的问题，因为在这里的话，网络是One by One的生成的，那么生成的再这样的情况之下，相邻很远的节点在生成节点的时候自然不会出很大的力气，也就是说他们之间形成边的概率也不会很高。通俗的话说，就是这个这个孩子不是你亲生的，在他成长的过程之中也并没有出力，那么自然他就不会和你有什么亲密关系。

那么我们这里就写完了关于Graph Generative模型的部分了。

今天的两个Note都是关于GNN的，但是只是给了一个Overall的讲解，关于之中的细节的关于某方面的算法可以应用的。我们在之后的Note之中再进行补充。