导语

在过去的几年中，深度生成模型在图像、语音和自然语言处理等领域已经取得了巨大的成功。得益于基于图的深度学习技术的进步，图生成模型有了发现新颖的分子结构、建模社交网络等在图上的新应用。近日arXiv的一篇综述文章对基于深度学习的图生成模型进行了全面的调查，将现有模型划分为五大类，并分别进行了详尽的描述，本文是对该文章内容的整体介绍。


扫码获取论文PDF陈昊 | 作者
邓一雪 | 编辑
 

图生成模型是复杂网络领域研究的经典问题，Endos-Renyi（ER）模型、Barabasi-Albert（BA）模型等经典图生成模型可以很好地揭示真实图的性质，但这类模型仍存在着结构固定、表示能力有限等问题。近年来随着深度学习技术尤其是图表示学习的发展，越来越多基于深度学习的图生成模型被提出。
最近挂上arXiv的综述文章《Deep Graph Generators: A Survey》将这些模型划分为五大类，分别是： 自回归（autoregressive）模型、基于自编码器（autoencoder-based）的模型、基于强化学习（RL-based）的模型、生成对抗网络（GAN）模型，以及基于流（flow-based）的模型。并针对每个类别中的重要模型提供了详细的描述。 论文题目：Deep Graph Generators: A Survey论文地址：https://arxiv.org/abs/2012.15544v1


1. 模型目标定义

给定一个满足潜在数据分布的图数据集，深度图生成模型的目的是利用深度神经网络从数据集中估计其满足的分布，然后从估计的分布中获取新的图样本。与传统图生成模型不同，深度图生成模型不需要对分布进行显式的建模。

2. 自回归深度图生成模型



自回归深度图生成模型逐步顺序地生成完整的图结构，每个时间步的预测结果都会受到已有图结构的影响。这类模型还可以进一步划分为有循环单元和无循环单元两类，前者使用循环单元捕获历史信息，而后者则直接依照最近的生成策略做出决策。

有循环单元的自回归深度图生成模型使用RNN捕获当前时刻之前所有时刻的信息。代表工作有Jiaxuan You[1]等人提出的GraphRNN模型（如图1）所示。该模型将不同节点顺序下的图表示为序列，并在这些序列上构建一个自回归的生成模型。
图1 GraphRNN模型的图生成过程，绿色箭头表示连表层面的RNN、蓝色箭头表示节点层面的RNN

与有循环单元的图生成模型不同，无循环单元的图神经网络只关注最近时刻的信息。以 GRANs模型（Graph Recurrent Attention Networks）[2]为例，该模型将图生成过程划分成多个时间块（如图2），采用注意力机制计算新加入图结构的节点与已存在节点间产生连边的概率。
图2 GRANs模型 相同颜色的节点属于同一时间块 (块大小为2)

3. 基于自编码器的深度图生成模型



该类模型通常使用图神经网络或其变体将训练图编码至隐空间，而后再解码生成图。GraphVAE[3]在该类模型中十分具有代表性。如图3所示，该模型使用临界矩阵、连边属性张量及节点属性矩阵表示对图进行表示。采用encoder-decoder结构进行学习。2020年的最新工作NED-VAE[4]则使用三个编码器以及两个解码器将连边属性和节点属性的学习部分分离（图4）。

图3 GraphVAE模型 A为邻接矩阵、E为连边属性张量、F为节点属性矩阵
 图4 NED-VAE模型的结构 包含三个子编码器与两个子解码器


4. 生成对抗网络深度图生成模型

该类模型将图结构与生成对抗网络（GAN）相结合。以MolGAN为例[5]，从先验样本中采样得到向量z并传递给通过MLP实现的生成器，生成器输出图表示。以图神经网络实现的判别器对图来自于生成器还是数据集进行分类。reward网络则利用外部软件提供的特定结构对生成器进行奖励。
图5 MolGAN模型示意图 生成器负责生成与图数据集中的真实图相似的图，判别器负责判别图是否为数据集中的真实图


5. 总结



深度图生成模型将深度学习技术尤其是图表示学习与传统图生成模型相结合，在分子结构发现、建立知识图谱、建模物理、社会和生物网络等领域有了广泛的应用。并可能在基于语言的（language-based）图生成问题以及场景（sence）图生成等领域发挥其巨大作用。本篇综述将主要的深度图生成模型分为五大类进行了详细的介绍，可以使读者获得对该领域的全面了解。除以上提到的三类模型外，基于强化学习（RL-based）与基于流（flow-based）的模型也在文章中有详细的介绍，欢迎下载原文进一步了解。
参考文献[1] You J, Ying R, Ren X, et al. Graphrnn: Generating realistic graphs with deep auto-regressive models[J]. arXiv preprint arXiv:1802.08773, 2018.[2] Liao R, Li Y, Song Y, et al. Efficient graph generation with graph recurrent attention networks[C]//Advances in Neural Information Processing Systems. 2019: 4255-4265.[3] Simonovsky M, Komodakis N. Graphvae: Towards generation of small graphs using variational autoencoders[C]//International Conference on Artificial Neural Networks. Springer, Cham, 2018: 412-422.[4] Guo X, Zhao L, Qin Z, et al. Node-Edge Co-disentangled Representation Learning for Attributed Graph Generation[C]//International Conference on Knowledge Discovery and Data Mining (SIGKDD). 2020.[5] De Cao N, Kipf T. MolGAN: An implicit generative model for small molecular graphs[J]. arXiv preprint arXiv:1805.11973, 2018.

复杂科学最新论文


集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「集智斑图」推送论文信息。扫描下方二维码即可一键订阅：

推荐阅读

使用Chung-Lu随机图模型生成大规模无标度网络 | 网络科学论文速递20篇增长图的生成图卷积网络 | 网络科学论文速递15篇图网络入门路径：从网络科学视角出发，上手深度学习前沿技术
加入集智，一起复杂！

点击“阅读原文”，追踪复杂科学顶刊论文