10-graph-gen 图机器学习之图生成模型
图深度生成模型 deep generative models for graph
回顾上一节课中的图编码，图卷积等
今天，来学习图深度解码，也就是反编码，最终输出一个图结构
Problem of Graph Generation图生成需要解决的问题
给定一个真实图，生成一个合成图
那么，什么才是好的生成模型？
图生成的意义
生成→深入探索图行程的过程
异常检测
预测——从过去预测未来
新网络的仿真
图填充
如果。。。场景？？
图生成的任务：
真实图的生成
目标导向图的生成，例如分子生成
为什么如此吸引人？
药物分子发现
发现一个全新的结构
网络科学：真实网络的空模型？
图生成为什么如此有难度：
大的且多变的输出空间 n^2
非唯一的表达，因为如果输出是邻接矩阵，那么根据节点的顺序不同，矩阵也是不同的
复杂的依赖→边的形成有远程的依赖关系
ML Basics for Graph Generation
图生成的机器学习基础
输入与输出：
输入：G
目标：学习G的分布；生成G？
起初：假设我们有图的数据集{xi}
p_data（x）：数据分布，是未知的，但是我们可以抽样知道一些
p_model(x;θ) ：参数为θ的模型，用于近似p_data（x）
目标：
让p_model(x;θ) 趋近于 p_data（x）
可以从p_model(x;θ)中抽样，形成新图
核心思想：最大似然
从p_model(x;θ)中抽样，也就是，输入一个噪声，输出一个近似的网络。采用神经网络的方式
深度生成模型的分类，本节采用的是自动回归模型，该模型是基于过去预测未来
自动回归模型：
p_model(x;θ)用于密度估计和抽样
应用链式规则：联合分布是条件分布的积
GraphRNN 生成真实图谱
与RNN的思想同源，通过节点和边序列的迭代输入生成一个图
那么，首先，需要将图看做序列
一个图，当顺序固定时，可唯一通过序列标识？
那么，序列有两个层次：节点层次（添加节点，一个一次）；边层次（从现有节点中添加边）
总结：一个图+节点顺序=一个序列
节点顺序是虚机选择的
因此，将图生成，转变为序列的生成
因此，需要两个步骤的模型：
生成新节点，生成新边
方法：使用RNN
GraphRNN：两个层次的RNN
node-level rnn生成初始状态，可应用于edge-level rnn
edge-level rnn为新节点生成边，探后更新node-level rnn的状态
rnn的基础
用于序列生成的RNN
如何初始化s0，x1？什么时候停止生成？→使用开始符和结束符
yt=前面t-1个的生成
rnn的每一步都输出一个概率向量
从该向量中抽样，并喂入下一步
测试时，
训练时：y是边，采用教师模式，即输入是真实的数据用于修正模型
损失函数：交叉式
训练的过程
节点1已经在网络中了，现在添加节点2
edge rnn预测节点1是否与节点2关联；
edge rnn得到监督结果，并输入修正；
新的边用来更新node rnn；
预测节点3与节点2是否关联
edge rnn得到监督结果，并输入修正；
新的边用来更新node rnn；
节点4与其他点不相连，停止生成
回传，梯度更新
测试
小结：
让graphrnn更易于管控
每个节点可以跟前面的任一节点相连
边生成的步骤太多：需生成一个全的邻接矩阵；负责的过长的边依赖关系
如何限制复杂度？
解决方案：使用广度优先，只需要两步而不是n-1步
如何评估生成的网络？
定义网络的相似度量，但没有有效的网络同构测试
解决方案：视觉相似度；图的统计相似度
视觉相似度
Applications and Open Questions
应用于开放问题
药物发现
基于规则的图卷积网络：将图卷积与强化学习相结合，同时还有对抗训练
