图深度生成模型 deep generative models for graph
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231550030-2077424415.png)
回顾上一节课中的图编码,图卷积等
今天,来学习图深度解码,也就是反编码,最终输出一个图结构
Problem of Graph Generation图生成需要解决的问题
给定一个真实图,生成一个合成图
那么,什么才是好的生成模型?
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231551276-1845820672.png)
图生成的意义
生成→深入探索图行程的过程
异常检测
预测——从过去预测未来
新网络的仿真
图填充
如果。。。场景??
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231551664-668065453.png)
图生成的任务:
真实图的生成
目标导向图的生成,例如分子生成
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231551946-893786666.png)
为什么如此吸引人?
药物分子发现
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231552282-1297006803.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231552567-268517538.png)
发现一个全新的结构
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231552877-610109608.png)
网络科学:真实网络的空模型?
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231553222-1305002457.png)
图生成为什么如此有难度:
大的且多变的输出空间 n^2
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231553542-1871486741.png)
非唯一的表达,因为如果输出是邻接矩阵,那么根据节点的顺序不同,矩阵也是不同的
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231553868-1969672514.png)
复杂的依赖→边的形成有远程的依赖关系
ML Basics for Graph Generation
图生成的机器学习基础
输入与输出:
输入:G
目标:学习G的分布;生成G?
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231554508-1154361992.png)
起初:假设我们有图的数据集{xi}
p_data(x):数据分布,是未知的,但是我们可以抽样知道一些
p_model(x;θ) :参数为θ的模型,用于近似p_data(x)
目标:
让p_model(x;θ) 趋近于 p_data(x)
可以从p_model(x;θ)中抽样,形成新图
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231554913-1120468101.png)
核心思想:最大似然
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231555369-1644435660.png)
从p_model(x;θ)中抽样,也就是,输入一个噪声,输出一个近似的网络。采用神经网络的方式
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231555798-1735153835.png)
深度生成模型的分类,本节采用的是自动回归模型,该模型是基于过去预测未来
自动回归模型:
p_model(x;θ)用于密度估计和抽样
应用链式规则:联合分布是条件分布的积
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231556620-1808940254.png)
GraphRNN 生成真实图谱
与RNN的思想同源,通过节点和边序列的迭代输入生成一个图
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231556940-951548443.png)
那么,首先,需要将图看做序列
一个图,当顺序固定时,可唯一通过序列标识?
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231557294-163084837.png)
那么,序列有两个层次:节点层次(添加节点,一个一次);边层次(从现有节点中添加边)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231557661-649824429.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231557944-1716578972.png)
总结:一个图+节点顺序=一个序列
节点顺序是虚机选择的
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231558216-749769586.png)
因此,将图生成,转变为序列的生成
因此,需要两个步骤的模型:
生成新节点,生成新边
方法:使用RNN
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231558563-1075370178.png)
GraphRNN:两个层次的RNN
node-level rnn生成初始状态,可应用于edge-level rnn
edge-level rnn为新节点生成边,探后更新node-level rnn的状态
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231558888-1812761127.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231559311-1645134258.png)
rnn的基础
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231559661-1287281278.png)
用于序列生成的RNN
如何初始化s0,x1?什么时候停止生成?→使用开始符和结束符
yt=前面t-1个的生成
rnn的每一步都输出一个概率向量
从该向量中抽样,并喂入下一步
训练时:y是边,采用教师模式,即输入是真实的数据用于修正模型![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231601055-318510527.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231601055-318510527.png)
损失函数:交叉式
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231601433-2107594628.png)
训练的过程
节点1已经在网络中了,现在添加节点2
edge rnn预测节点1是否与节点2关联;
edge rnn得到监督结果,并输入修正;
新的边用来更新node rnn;
预测节点3与节点2是否关联
edge rnn得到监督结果,并输入修正;
新的边用来更新node rnn;
节点4与其他点不相连,停止生成
回传,梯度更新
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231601740-1499625355.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231602001-1770499829.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231602355-1124085794.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231602922-938426568.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231603223-1439675151.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231603516-1871338093.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231603861-874807413.png)
测试
小结:
让graphrnn更易于管控
每个节点可以跟前面的任一节点相连
边生成的步骤太多:需生成一个全的邻接矩阵;负责的过长的边依赖关系
如何限制复杂度?
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231605365-595235042.png)
解决方案:使用广度优先,只需要两步而不是n-1步
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231605710-1988223553.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231606118-1964842909.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231606482-1426218102.png)
如何评估生成的网络?
定义网络的相似度量,但没有有效的网络同构测试
解决方案:视觉相似度;图的统计相似度
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231606851-1074628403.png)
视觉相似度
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231607273-1270946274.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231607681-121350967.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231608082-78313760.png)
Applications and Open Questions
应用于开放问题
药物发现
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231608473-2142973478.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231608789-935839297.png)
基于规则的图卷积网络:将图卷积与强化学习相结合,同时还有对抗训练
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231609122-744013857.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231609450-201016795.png)
![](https://img2018.cnblogs.com/blog/985935/202002/985935-20200206231609729-1689592919.png)