核心思想是将图生成问题转变成序列生成问题。
Recap: 回顾
在上节课中GNN的学习中，我们从空域的角度理解GNN的基本思想就是邻居聚合：
邻居聚合的优点在于结合了Feature和Graph Structure
用数学公式来表示一次邻居聚合就是：
经典的GNN算法有GCN和GraphSAGE两种，GraphSAGE相比于GCN的优点之一在于其有更多的不同的Aggregation Function。
今天讲解的内容是如何生成图，即：
input：a set of obeserved graphs
output：new graphs generated by model
Problem of Graph Generation
图生成算法的重要性
图生成算法有两大任务
- Realistic graph generation
Generate graphs that are similar to a given set of graphs（本节课的重点） - Goal-directed graph generation
Generate graphs that optimize given objectives/constraints（Drug molecule generation/optimization）
图生成算法的难点
- Large and variable output space
- Non-unique representations
即存在图同构这种性质
- Complex dependencies
以下图的例子来看，在边的生成的过程中，存在着前后依赖关系：
Recap: ML Basics for Graph Generation
基于上面讨论的图生成算法的难点，我们可以通过下面讲解的机器学习知识将其成功解决。
首先，从机器学习的角度明确Graph Generative Model的输入和输出：
我们假设现实生活中的图，是由“上帝之手”锻造的，它有一个潜在的概率分布$p_{data}(G)$，而这个概率分布正是我们需要去学习的。
回顾一下，传统的 生成模型（Generative Models） 的含义：
我们的目标有两个：得到一个近似的distribution（由参数$\theta$确定） 以及 能够从这个distribution里面采样出新的数据（终极目标）。
需要理解的是，这里的distribution是概率分布的意思，讲得实际一点，比如数据服从正态分布、数据服从伯努利分布等等。只有有了概率分布之后，我们才能在这个概率分布中采样出无穷无尽的数据，这也是为什么第一个目标是构造概率分布的原因。
定义了两个目标之后，我们就来看看怎么实现这两个目标：
Goal 1：Make $p_{model}(x; \theta)$ close to $p_{data}(x)$
关键技术：极大似然估计
简单回顾一下概率论中关于极大似然估计的基本思想：使当前被发现的样本的概率最大化。
Goal 2：Sample from $p_{model}(x;\theta)$
这里不太理解，据说是生成模型的常用做法。
关于生成模型的种类，老师给出了下面这张图：
本节课使用的生成模型叫做：Auto-regressive models，它的核心思想是predicts future behavior based on past behavior.
Auto-regressive models
Auto-regressive models具有这样一种特征：$p_{model}(x;\theta)$ is used for both density estimation and sampling (from the probability density)
而对于Variational Auto Encoders（VAEs），Generative Adversarial Nets（GATs）等模型，它们是分2个或者多个模型来分别完成上面两个Goals的。
Auto-regressive model里面用到了概率论中的Chain Relu：
- Chain Rule揭示了一个简单的事实：后面的状态由前面的状态决定。
- 后面讲的GraphRNN的思想就源于Chain Rule，学习的时候记得将GraphRNN类比到Chain Rule~
GraphRNN：Generating Realistic Graphs
Model Graph as Sequences 将图的生成问题转换成序列生成问题
网络的生成是通过不断地增加节点和边来实现的。
对应一个确定的节点顺序$\pi$，图$G$可以表示为节点和边的序列$S^{\pi}$：
$S^{\pi}$实际上是序列的序列，里面包含了序列$S_{i}^{\pi}$，它有两个层次的操作：
- 节点操作——增加节点，每个$S_{i}^{\pi}$对应一个；
- 边的操作——序列 $S_i^{\pi}$中的每一步表示是否要与已有的节点增加一条边：
那么，我们就可以将图的生成问题转换成一个序列的生成问题。这样一来，（对于无向图来说），我们只需要保存邻接矩阵的一半就行了。
综上所述：
A graph + a node ordering = A sequence of sequences!
那么接下来，我们需要解决的就是两个过程：
- 新的节点的生成——节点序列的生成
- 对于新生成的节点，生成其相关联的边——边序列的生成
而解决序列问题，我们自然而然地就能想到利用RNN来实现。
GraphRNN
GraphRNN包括两个部分：
node-level RNN——生成edge-level RNN的初始状态
edge-level RNN——为新节点创建相关的边，并将结果更新到node-level RNN的状态中。
其实从上面的图中可以看出，每一步是先求解边，然后再加入点的。
那么，我们怎样利用RNN来生成序列呢？
首先来看看RNN的定义，对于一个RNN单元来说，有状态$s_t$，输入$x_t$，输出$y_t$。
对于序列的表示，可以将RNN单元重复连接。序列的开始和结束都定义为特殊的标识符，开始的标示符$s_0 = SOS$，结束的标识符$y_T = EOS$（此时序列$S^{\pi}$的被定义成了$\lbrace SOS，S_1^{\pi}，….，EOS \rbrace$）。而上一个状态的输出就是下一个状态的输入，即$x_{t+1} = y_{t}$。如下图所示：
在上述模型的基础上，我们需要给RNN模型增加随机性。首先，我们要明确的是，我们的目标是使用RNN来估计 $\prod_{t=1}^n p_{model}(x_t|x_1, \cdots, x_{t-1}; \theta)$。我们定义$y_{t} = p_{model}(x_{t}|x_1,\cdots,x_{t-1}|\theta)$，那么$x_{t+1}$是在$y_{t}$上采样的结果，即$x_{t+1} \sim y_{t}$。
RNN每一步的输出是一个概率向量，下一个状态的输入时基于该概率向量的一个取样。
模型的测试
假设我们有一个已经训练好的模型，$y$服从伯努利分布，$y_1=0.9$表示有0.9的概率生成1，即有边连接；有 $1-0.9=0.1$的概率生成0，即没有边连接。
模型训练
那么怎么去训练模型呢？我们知道训练模型肯定是需要定义损失函数的，那么怎么定义随时函数呢？
在进行模型训练的时候，有一个原则——Teacher Forcing，也就是加入我们检测到真实的边的序列为 [1,0,…]，在训练时我们用真实的这个序列作为输出。
损失函数定义为$y^{}$和$y$之间的Binary cross entropy，训练目标是使损失函数最小化：
$$L=-[y_1^ \log(y_1)+(1-y_1^*)\log (1-y_1)]$$
公式的解释如下图：
下图是一个小例子：
从上面这个例子可以很清晰地看到，我们是分了两个维度来进行RNN，因此在Node Level上，我们有$SOS$，在每个Edge Level上，我们也有对应的$SOS$和$EOS$。
模型优化——图节点的编号策略
然而，我们还是面临一个问题，因为每一个新生成的点都有可能和之前的点进行关联，也就是说，当图的节点数量很大时，我需要记住很长的依赖关系来实现边的生成。
我们的解决方案，就是在数据预处理阶段利用BFS（广度优先搜索）来给图的节点编号。
使用广度优先搜索进行编号，有两个优点：
- Reduce possible node orderings
- Reduce steps for edge generation
Application and Open Question
前面讲的是Graph Generation的Task 1：Generating Realistic Graphs，这一小节通过一个药物发现的例子讲解Task 2：Goal-directed graph generation。
这里我就也不看了。
