本文已参与「新人创造礼」活动，一起敞开创造之路。

本文首发于CSDN。

诸神沉默不语-个人CSDN博文目录 cs224w（图机器学习）2021冬天课程学习笔记调集 @[toc]

YouTube视频观看地址1 视频观看地址2 视频观看地址3 视频观看地址4

本章首要内容：首要介绍了深度图生成模型的基本情况，然后介绍了直接从图数据集中学习的GraphRNN模型¹，最终介绍了医药生成范畴的GCPN模型²。

1. Deep Generative Models for Graphs

对深度图生成模型，有两种看待问题的视角：

第一种是说，图生成使命很重要，咱们此前现已学习过传统图生成模型³，接下来将介绍在图表明学习框架下怎么用深度学习的办法来完成图生成使命。

另一种视角是将其视为图表明学习使命的反方向使命。课程此前学习过的图表明学习使命⁴ deep graph encoders：输入图数据，经图神经网络输出节点嵌入

cs224w（图机器学习）2021冬季课程学习笔记19 Deep Generative Models for Graphs

而深度图生成模型能够说是deep graph decoders：输入little noise parameter或其他类似东西，输出图结构数据

2. Machine Learning for Graph Generation

图生成使命分为两种：
1. realistic graph generation 生成与给定的一系列图类似的图（本章2、3节要点）
2. goal-directed graph generation 生成优化特定方针或约束的图（举例：生成/优化药物分子）（本章第4节介绍）
图生成模型给定一系列图（抽样自一个冥冥中注定的数据散布 $p_{data}(G)$ ）方针：
1. 学到散布 $p_{model}(G)$
2. 从 $p_{model}(G)$ 中抽样，得到新的图
生成模型基础咱们想从一系列数据点（如图数据） ${xi}\{\mathbf{x}_i\}$ 中学到一个生成模型： $pdata(x)p_{data}(\mathbf{x})$ 是数据散布，不可知，但咱们现已抽样出了 $xi∼pdata(x)\mathbf{x}_i\sim p_{data}(\mathbf{x})$ 。 $pmodel(x;)p_{model}(\mathbf{x};\theta)$ 是模型，以 $\theta$ 为参数，用于近似 $pdata(x)p_{data}(\mathbf{x})$ 。
学习方针：
1. density estimation: 使 $pmodel(x;)p_{model}(\mathbf{x};\theta)$ 近似 $pdata(x)p_{data}(\mathbf{x})$
2. sampling: 从 $pmodel(x;)p_{model}(\mathbf{x};\theta)$ 中抽样，生成数据（图）
density estimation 使 $pmodel(x;)p_{model}(\mathbf{x};\theta)$ 近似 $pdata(x)p_{data}(\mathbf{x})$ 首要原则：极大似然⁵ （建模散布的基本办法） $max⁡Ex∼pdatalog⁡pmodel(x;)\theta^*=\argmax_\theta\mathbb{E}_{x\sim p_{data}}\log{p_{model}(\mathbf{x};\theta)}$ 即找到使被调查到的数据点 $xi∼pdata\mathbf{x}_i\sim p_{data}$ 最有或许在 $p_{model}$ 下生成（即 $∏ipmodel(xi;∗)\prod_i{p_{model}(\mathbf{x}_i;\theta^*)}$ 最大，即 $log⁡∏ipmodel(xi;∗)\log{\prod_i{p_{model}(\mathbf{x}_i;\theta^*)}}$ 最大，即 $∑ilog⁡pmodel(xi;∗)\sum_i\log{p_{model}(\mathbf{x}_i;\theta^*)}$ 最大）的 $p_{model}$ 的参数 $∗\theta^*$
sampling 从 $pmodel(x;)p_{model}(\mathbf{x};\theta)$ 中抽样从杂乱散布中抽样的常用办法：首要从一个简略noise distribution⁶ $N (0, 1)$ 中抽样出 $zi\mathbf{z}_i$ 然后将 $zi\mathbf{z}_i$ expand到图数据上，即将它经过函数 $f(⋅)f(\cdot)$ 进行转化： $xi=f(zi;)\mathbf{x}_i=f(\mathbf{z}_i;\theta)$ ，这样 $xi\mathbf{x}_i$ 就能服从于一个杂乱的散布。 $f(⋅)f(\cdot)$ 经过已知数据，用深度神经网络进行学习。
auto-regressive models $pmodel(x;)p_{model}(\mathbf{x};\theta)$ 一起用于density estimation和sampling。（一些其他模型，如Variational Auto Encoders (VAEs), Generative Adversarial Nets (GANs) 有二至多个模型来分别完成使命）
中心思维：链式法则。联合散布是条件散布的连乘成果： $pmodel(x;)=∏t=1npmodel(xt∣x1,…,xt−1;)p_{model}(\mathbf{x};\theta)=\prod_{t=1}^np_{model}(x_t|x_1,\dots,x_{t-1};\theta)$ 例如：假如 $x\mathbf{x}$ 是向量， $x_t$ 是其第 $t$ 维元素； $x\mathbf{x}$ 是句子， $x_t$ 是其第 $t$ 个单词。在咱们的事例中， $x_t$ 是第 $t$ 个举动（如增加一个节点或增加一条边）

3. GraphRNN: Generating Realistic Graphs

GraphRNN的优点在于它不需求任何inductive bias assumptions，就能够直接完成图生成使命。
GraphRNN的思维：sequentially增加节点和边，最终生成一张图。如图所示：
将图建模为序列：给定图 $G$ 及其对应的node ordering $\pi$ ，咱们能够将其仅有映射为一个node and edge additions的序列 $SS^\pi$ 如图所示，序列 $SS^\pi$ 的每个元素都是加一个节点和这个节点与之前节点衔接的边：
$SS^\pi$ 是一个sequence的sequence，有两个等级：节点等级每次增加一个节点，边等级每次增加新节点与之前节点之间的边。
节点等级：

节点级其他每一步是一个边级其他序列：每一个元素是是否与该节点增加一条边，即构成一个如图所示的0-1变量序列：

这儿的node ordering是随机选的，随后咱们会讨论这一问题。如图所示，每一次是生成邻接矩阵（黄色部分）中的一个节点（向右），每个节点生成一列边（向下）：

这样咱们就将图生成问题转化为序列生成问题。
咱们需求建模两个进程： (1) 生成一个新节点的state（节点等级序列） (2) 依据新节点state生成它与之前节点相连的边（边等级序列）
办法：用Recurrent Neural Networks (RNNs) 建模这些进程

4. RNN RNNs是为序列数据所规划的，它sequentially输入序列数据以更新其hidden states，其hidden states包括已输入RNN的一切信息。更新进程由RNN cells完成。图示流程：

5. RNN cell

s_t

: RNN在第

t

步之后的state

x_t

: RNN在第

t

步的输入

y_t

: RNN在第

t

步的输出（在咱们的比如中，上述三个值都是标量）
RNN cell: 可练习参数

W, U, V

第一步：依据输入和上一步state更新hidden state:

st=(W⋅xt+U⋅st−1)s_t=\sigma(W\cdot x_t+U\cdot s_{t-1})

第二步：依据state进行输出:

yt=V⋅sty_t=V\cdot s_t

还有更具有体现力的cells：GRU，LSTM等

6. GraphRNN: Two levels of RNN GraphRNN有一个节点等级RNN和一个边等级RNN，节点等级RNN生成边等级RNN的初始state，边等级RNN sequentially猜测这个新节点与每一个之前的节点是否相连。

如图所示，边等级RNN猜测新加入的节点是否与之前各点相连：

接下来将介绍怎么用这个RNN生成序列。

7. (1) 用RNN生成序列：用前一个cell的输出作为下一个cell的输入（

x_{t+1}=y_t

）。 (2) 初始化输入序列：用 start of sequence token (SOS) 作为初始输入。SOS常是一个全0或全1的向量。 (3) 结束生成使命：用 end of sequence token (EOS) 作为RNN额外输出。假如输出EOS=0，则RNN继续生成；假如过输出EOS=1，则RNN中止生成。

模型如图所示：这样的问题在于模型是确认的，但咱们需求生成的是散布，所以需求模型具有随机性。

咱们的方针便是用RNN建模

∏k=1npmodel(xt∣x1,…,xt−1;)\prod_{k=1}^np_{model}(x_t|x_1,\dots,x_{t-1};\theta)

所以咱们让

yt=pmodel(xt∣x1,…,xt−1;)y_t=p_{model}(x_t|x_1,\dots,x_{t-1};\theta)

，然后从

y_t

中抽样

x_{t+1}

，即

xt+1∼ytx_{t+1}\sim y_t

： RNN每一步发生一条边的生成概率，咱们依此抽样并将抽样成果输入下一步。如图所示：

8. RNN at Test Time 咱们假定现已练习好了模型：

y_t

是

x_{t+1}

是否为1这一遵从伯努利散布事情的概率，从而依据模型咱们能够从输入输出

y_{t}

，从而抽样出

x_{t+1}

。如图所示：

9. RNN at Training Time 在练习进程中，咱们已知的数据便是序列

y^*

（该节点与之前每一节点是否相连的0-1元素组成的序列）。咱们运用teacher forcing⁷ 的办法，将每一个输入都从前一个节点的输出换成实在序列值，而用实在序列值与模型输出值来核算丢失函数。如图所示：

这一问题的丢失函数运用binary cross entropy⁸，即最小化下式丢失函数：

L=−[y1∗log⁡(y1)+(1−y1∗)log⁡(1−y1)]L=-\big[y_1^*\log(y_1)+(1-y_1^*)\log(1-y_1)\big]

对每一个输出，上式右式左右两项一起只能存在一个：假如边存在，即

y_1^*=1

，则咱们需求最小化

log(y_1)

，即便

y_1

增大由于

log⁡\log

递加，所以

−log⁡-\log

递减假如边不存在，即

y_1^*=0

，咱们需求最小化

log(1-y_1)

，即便

y_1

减小由于

log⁡\log

递加，

1 - x

递减，所以

log⁡(1−x)\log(1-x)

递减，所以

−log⁡(1−x)-\log(1-x)

递加这样就使

y_1

接近data samples

y_1^*

y_1

是由RNN核算得到的，经过这一丢失函数，运用反向传播就能对应调整RNN参数。

10. Putting Things Together 咱们的方案是： 1. 增加一个新节点：跑节点RNN，用其每一步输出来初始化边RNN 2. 为新节点增加新边：跑边RNN，猜测新节点是否与每一之前节点相连 3. 增加另一个新节点：用边RNN最终的hidden state来跑下一步的节点RNN 4. 中止图生成使命：假如边RNN在第一步输出EOS，则咱们知道新节点上没有任何一条边，即不再与之前的图有衔接，从而中止图生成进程。

11. 练习进程假定节点1已在图中，现在增加节点2：输入SOS到节点RNN中

边RNN猜测节点2是否会与节点1相连：输入SOS到边RNN中，输出节点2是否会与节点1相连的概率0.5

用边RNN的hidden state更新节点RNN：

边RNN猜测节点3是否会与节点1、2相连：输入SOS到边RNN中，输出节点3是否会与节点2相连的概率0.6；输入节点3与节点2不相连的实在值0到下一个cell中，输出节点3是否会与节点2相连的概率0.4：

用边RNN的hidden state更新节点RNN：

咱们已知节点4不与任何之前节点相连，所以中止生成使命：输入SOS到边RNN中，没看懂这儿是不是用teacher forcing强制中止的意思。

每一步咱们都用实在值作为监督，如图所示，就跟右上角的图方法或邻接矩阵方法相同的实在值：

经过时刻反向传播，随time step⁹ 累积梯度，如图所示：

测试阶段
1. 依据猜测出来的边散布抽样边
2. 用GraphRNN自己的猜测来代替每一步输入（就类似练习阶段假如不用tearcher forcing的那种作用）如图所示：
GraphRNN总结：经过生成一个2级序列来生成一张图，用RNN来生成序列。如图中所示，节点等级RNN向右猜测，边等级RNN向下猜测。接下来咱们要使RNN tractable，以及对其作用进行评价。
tractability 在此前的模型中，每一个新节点都能够与其前任何一个节点相连，这需求太多步边生成了，需求发生一整个邻接矩阵（如上图所示），也有太多过长的边依靠了（不管现已有了多少个节点，新节点还要考虑是否与最前面的几个节点有边衔接关系）。假如咱们运用随机的node ordering，那咱们对每个新生成的节点便是都要考虑它与之前每一个节点是否有边（图中左下角所示）：
BFS 可是假如咱们换成一种BFS的node ordering，那么在对每个边考虑它或许相连的之前节点的进程如图所示，咱们只需求考虑在BFS时它同层和上一层的节点（由于再之前的节点跟它不会有邻居关系），即只需求考虑2步的节点而非 $n - 1$ 步的节点：
这样的好处有二： (1) 减少了或许存在的node ordering数量（从 $O (n!)$ 减小到不同BFS ordering的数量） (2) 减少了边生成的步数（由于不需求看之前一切节点了，只需求看一部分最近的节点即可）
在运转GraphRNN时仅需考虑该节点及其之前的一部分节点，如图所示¹⁰：
对生成图的评价咱们的数据集是若干图，输出也是若干图，咱们要求评价这两组图之间的类似性。有直接从视觉上调查其类似性和经过图核算方针来衡量其类似性两种衡量方法。
1. visual similarity 就直接看，能明显地发现在grid方法的图上，GraphRNN跟输入数据比传统图生成模型（首要用于生成网络而非这种grid图）要更像许多：
  （图中Kronecker便是上节课讲的那个模型。其他baseline模型详细哪个对应哪个能够在 ¹这篇论文中找。这个图便是原论文中的插图）
  即便在传统图生成模型应用的有社区的交际网络上，GraphRNN也体现很好，如图所示。这体现了GraphRNN的可泛化能力。
2. graph statistics similarity 咱们想找到一些比目测更精确的比较方法，但直接在两张图的结构之间作比较很难（同构性检测是NP的），因而咱们挑选比较图核算方针。典型的图核算方针包括： (1) degree distribution (Deg.) (2) clustering coefficient distribution (Clus.) (3) orbit count statistics ¹¹ 留意：每个图核算方针都是一个概率散布。
  所以咱们一要比较两种图核算方针（两个概率散布），解决办法是earth mover distance (EMD)；二要比较两个图核算方针的调集（两个概率散布的调集），解决办法是根据EMD的maximum mean discrepancy (MMD)。
  1. earth mover distance (EMD) 用于比较两个散布之间的类似性。在直觉上便是衡量需求将一种散布编程另一种散布所需求移动的最小“泥土量”（面积）。总归这儿有个公式，可是我也没细心看详细怎么搞的。或许能够参阅一下EMD的英文维基百科Earth mover’s distance – Wikipedia，今后有缘能够学习：
  2. maximum mean discrepancy (MMD) 根据元素类似性，比较调集类似性：运用L2间隔，对每个元素用EMD核算间隔，然后用L2间隔核算MMD。
    呃可是这个公式我委实是没有看懂：
    ……什么东西啊这是？
3. 对图生成成果的评价：
  核算举例：经过核算原图域生成图之前在clustering coefficient distribution上的差异，咱们发现GraphRNN是体现最好的（即最类似的）。

4. Application of Deep Graph Generative Models

本节首要介绍深度图生成模型在药物发现范畴的应用GCPN²。

药物发现范畴的问题是：咱们怎么学习一个模型，使其生成valid、实在的分子，且具有优化过的某一特点得分（如drug-likeness或可溶性等）？
这种生成使命便是goal-directed graph generation： ① 优化一个特定方针得分（high scores），如drug-likeness ② 遵从内蕴规矩（valid），如chemical validity rules ③ 从示例中学习（realistic），如仿照一个分子图数据集
这一使命的难点在于需求在机器学习中引入黑盒：像drug-likeness这种受物理定律决议的方针是咱们不可知的。¹²
咱们的解决思路是运用强化学习的思维强化学习是一个机器学习agent调查环境environment，采取举动action来与环境互动interact，收到正向或负面的反应reward，依据反应从这一回环之中进行学习。回环如图所示。其中心思维在于agent是直接从环境这一对agent的黑盒中进行学习的。
咱们的解决办法是GCPN：graph convolutional policy network 结合了图表明学习和强化学习中心思维：
1. GNN捕获图结构信息
2. 强化学习辅导导向预期方针的图生成进程
3. 有监督练习仿照给定数据集的样例
GCPN vs GraphRNN
1. 共同点： sequentially生成图仿照给定的图数据集
2. 首要差异：
  1. GCPN用GNN来猜测图生成行为优势：GNN比RNN更具有体现力下风：GNN比RNN更耗时（可是分子一般都是小图，所以咱们负担得起这个时刻价值）
  2. GCPN运用RL来直接生成符合咱们方针的图。RL使goal-directed graph generation成为或许。
sequential graph generation GraphRNN：根据RNN hidden states（捕获至此已生成图部分的信息）猜测图生成行为。
GCPN：根据GNN节点嵌入，用链接猜测使命来猜测图生成行为。这种方法更具有体现力、更有鲁棒性，但更不scalable。回忆链接猜测使命的prediction head¹³，concatenation+linear这种方法便是： $Headedge(hu(L),hv(L))=Linear(Concat(hu(L),hv(L)))\text{Head}_\text{{edge}}(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)})=\text{Linear}\big(\text{Concat}(\mathbf{h}_u^{(L)},\mathbf{h}_v^{(L)})\big)$
GCPN概览如图所示，首要刺进节点5，然后用GNN猜测节点5会与哪些节点相连，抽样边（action），查验其化学validity，核算reward。这个详细流程其实我也妹搞理解，强化学习这部分我就不太懂。今后有缘再细心研讨。
咱们怎么设置reward？咱们设置两种reward：一种是step reward，学习履行valid action：每一步对valid action分配小的正反应。一种是final reward，优化预期特点：在最终对高预期特点分配正反应。 reward=final reward + step reward
练习进程分两部分：
1. 有监督练习：经过仿照给定被观测图的行为练习policy，用穿插熵梯度下降。（跟GraphRNN中的相同）
2. 强化学习练习：练习policy以优化反应，运用standard policy gradient algorithm。这一步我也不明白，它反正说能够参阅CS234等强化学习课程来了解这部分。今后有缘再了解吧。
GCPN实验成果在logP和QED这些医药上要优化的方针上都体现很好：
constrained optimization / complete使命：编辑给定分子，在几步之后就能达到高特点得分（如在以logP作为罚项的基础上，提升辛醇的可溶性）：

5. 本章总结

杂乱图能够用深度学习经过sequential generation成功生成。
图生成决议计划的每一步都根据hidden state。 hidden state能够是隐式的向量表明（由于RNN的中心进程都在hidden state里边，所以说是隐式的），由RNN解码；也能够是显式的中心生成图，由GCN解码。
能够完成的使命包括仿照给定的图数据集和往给定方针优化图。

GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models. J. You, R. Ying, X. Ren, W. L. Hamilton, J. Leskovec. International Conference on Machine Learning (ICML), 2018. ↩ ↩²
Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation. J. You, B. Liu, R. Ying, V. Pande, J. Leskovec. Neural Information Processing Systems (NeurIPS), 2018 ↩ ↩²
可参阅我之前写过的笔记：cs224w（图机器学习）2021冬天课程学习笔记17 Traditional Generative Models for Graphs_诸神沉默不语的博客-CSDN博客 ↩
我写过的cs224w笔记系列合集：cs224w（图机器学习）2021冬天课程学习笔记调集_诸神沉默不语的博客-CSDN博客 ↩
可参阅我之前写过的这篇笔记的第5个脚注：cs224w（图机器学习）2021冬天课程学习笔记3: Node Embeddings_诸神沉默不语的博客-CSDN博客 ↩
noise distribution应该值得便是Gaussian noise（由于我谷歌搜索noise distribution出来的第一个链接便是Gaussian noise的英文维基百科页面） ↩
只简略看了一下：What is Teacher Forcing for Recurrent Neural Networks? 总归意思便是如课程中所说，用实在值而非上一cell的输出值作为下一cell的输入，作用会更好。至于详细为什么好的能够今后再研讨吧。 ↩
就这个我也查了一下……能够参阅这篇文章：Understanding binary cross-entropy / log loss: a visual explanation | by Daniel Godoy | Towards Data Science 可是我写这玩意的时分有点困了，并且我懒得学这种基础知识了，所以我懒得看了，今后有缘再研讨这些熵啊丢失函数啊穿插熵啊二元穿插熵啊这种高级东西吧。 ↩
其实我没看懂这个RNN中的time step是什么意思，总归把参阅资料也列出来，今后有缘再研讨：对循环神经网络（RNN）中time step的理解_Microstrong-CSDN博客 ↩
可是我没搞懂这儿为什么写是3个？我寻思这应该是它之前同层及前一层的节点数吧？为什么能是3？至于图中提到的BFS frontier，我检查一下好像是个专有名词，是同一层已知但未访问节点调集的意思……然后我就：？关于这个意思的参阅资料（都没细心看，今后有空能够研讨研讨）： ① www.cs.dartmouth.edu/~scot/cs10/… ② Breadth First Search and Depth First Search | by Tyler Elliot Bettilyon | Teb’s Lab | Medium ③ 思考(9)BFS,DFS,A* and Dijkstra’s的差异与联系 – 知乎 ④ Graph Search Algorithms 我看了原论文¹ 里的插图（没看内容），看说这个M确实能够是一个常数。便是我寻思啊，当然你能够手动约束M是一个常数，就卡死边RNN的cell数就能够了嘛。可是为什么会这样啊？它应该是这样吗？我觉得对这一问题假如需求进行更深一步的了解，或许需求去深层阅读原论文及相关文献，所以我就……今后再说吧。 ↩
这个orbit在原论文中是这样写的：
文中提及的参阅文献便是这篇：Hocevar, T. and Demsar, J. A combinatorial approach to graphlet counting. Bioinformatics, 30(4):559–565, 2014. 一个orbit便是说在图上等价/自同构（graph automorphism）的一切节点所组成的一个调集这种东西。而这儿的orbit count statistics应该便是同一节点数的orbit数的意思。当然我也不太确认，能够看看GraphRNN和上一段这个参阅文献确认一下。 ↩
其实我没搞懂这个问题的难点在哪，机器学习的一切有监督学习不都是默认方针的决议机制不知道么，假如已知谁还用什么机器学习啊…… ↩
prediction head大约便是分类层前最终一层利用节点嵌入进行猜测的这种感觉。可参阅我之前写的笔记：cs224w（图机器学习）2021冬天课程学习笔记10 Applications of Graph Neural Networks_诸神沉默不语的博客-CSDN博客 ↩

cs224w（图机器学习）2021冬季课程学习笔记19 Deep Generative Models for Graphs

1. Deep Generative Models for Graphs

2. Machine Learning for Graph Generation

3. GraphRNN: Generating Realistic Graphs

4. Application of Deep Graph Generative Models

5. 本章总结

Footnotes

相关文章

[深度应用]·主流深度学习硬件速度对比（CPU，GPU，TPU）

Keras深度学习——交通标志识别

Transformer导论之GPT

Flutter 动画详解（一）

作者信息