如何生成“好”的图？【TPAMI2022】面向图生成的深度生成模型系统综述

2022 年 10 月 10 日 专知

图是描述对象及其关系的重要数据表示形式，它们出现在各种各样的现实场景中。图生成是该领域的关键问题之一，它考虑的是学习给定图的分布，生成更多新的图。然而，由于其广泛的应用，具有丰富历史的图的生成模型传统上是手工制作的，并且只能对图的一些统计属性建模。最近在用于图生成的深度生成模型方面的进展是提高生成图的保真度的重要一步，并为新类型的应用铺平了道路。本文对用于图生成的深度生成模型领域的文献进行了广泛的概述。首先，给出了面向图生成的深度生成模型的形式化定义和初步知识;其次，分别提出了用于无条件和条件图生成的深度生成模型的分类;对各自已有的工作进行了比较分析。在此之后，将概述此特定领域中的评估指标。最后，总结了深度图生成的应用，并指出了五个有发展前景的研究方向。

https://www.zhuanzhi.ai/paper/a904f0aa0762e65e1dd0b8b464df7168

引言

图在现实世界中无处不在，表示对象及其关系，如社会网络、引文网络、生物网络、交通网络等。众所周知，图还具有复杂的结构，其中包含丰富的底层值[1]。人们在这方面做出了巨大的努力，产生了丰富的相关文献和处理各种图问题的方法。这些工作可分为两类:1)预测和分析给定图的模式。2)学习给定图的分布，生成更多新颖的图。第一种类型涵盖了许多研究领域，包括节点分类、图分类和链接预测。在过去的几十年里，在这个领域已经做了大量的工作。与第一类问题相比，第二类问题与图生成问题有关，这也是本文的重点。

图生成包括建模和生成真实世界的图的过程，它在几个领域都有应用，例如理解社交网络[2]，[3]，[4]中的交互动态，异常检测[5]，蛋白质结构建模[6]，[7]，源代码生成和翻译[8]，[9]，语义解析[10]。由于其广泛的应用，图的生成模型的发展有着丰富的历史，产生了著名的模型，如随机图、小世界模型、随机块模型和贝叶斯网络模型，这些模型基于先验结构假设[11]生成图。这些图生成模型[12]、[13]、[14]旨在建模预先选择的图族，如随机图[15]、小世界网络[16]和无标度图[12]。然而，由于其简单性和手工制作的性质，这些随机图模型通常对复杂依赖的建模能力有限，只能对图的一些统计属性建模。这些方法通常很适合预定义原则为之量身定制的属性，但通常不能很好地适用于其他属性。例如，接触网络模型可以拟合流感流行，但不能拟合动态功能连接。然而，在许多领域，网络的性质和生成原理在很大程度上是未知的，如那些解释大脑网络中的精神疾病的机制，网络攻击和恶意软件的传播。对于另一个例子，Erdos-Renyi的图没有许多现实世界网络中典型的重尾度分布。此外，先验假设的使用限制了这些传统技术在更大规模的领域中探索更多的应用，在这些领域中，图的先验知识总是不可用。

考虑到传统图生成技术的局限性，一个关键的开放挑战是开发可以从观察到的图集合中直接学习生成模型的方法，这是提高生成图的保真度的重要一步。它为新类型的应用铺平了道路，如发现新的药物[17]，[18]，和蛋白质结构建模[19]，[20]，[21]。深度生成模型的最新进展，如变分自编码器(VAE)[22]和生成对抗网络(GAN)[23]，已被提出用于生成图的许多深度学习模型，这些模型形式化了用于生成图的深度生成模型的有前途的领域，这是本综述的重点。

在深度图生成方面已经开展了各种先进的工作，从一次性图生成到顺序图生成过程，适应了各种深度生成学习策略。这些方法旨在通过不同领域的工作解决上述挑战中的一个或几个，包括机器学习、生物信息学、人工智能、人类健康和社交网络挖掘。但是，不同的研究领域开发的方法往往使用不同的词汇，从不同的角度解决问题。此外，缺乏标准和全面的评估程序来验证所开发的图的深度生成模型。为此，本文对用于图生成的深度生成模型进行了系统的综述。目的是帮助跨学科研究者选择合适的技术来解决其应用领域的问题，更重要的是帮助图生成研究者理解图生成的基本原理，并识别深度图生成领域的开放研究机会。据我们所知，这是第一次对用于图生成的深度生成模型的全面综述。下面，我们总结了这次综述的主要贡献:

本文提出一种用于图生成的深度生成模型分类法，按问题设置和方法进行分类。介绍了不同子类别之间的优缺点和关系。对用于图生成的深度生成模型以及基础的深度生成模型进行了详细的描述、分析和比较。

我们总结和分类现有的评估程序和指标，基准数据集和对应的图生成任务的深度生成模型的结果。
我们介绍了图深度生成模型的现有应用领域，以及它们给这些应用带来的潜在好处和机会。
我们提出了用于图生成的深度生成模型领域的几个开放问题和有前途的未来研究方向。

用于图生成的无条件深度生成模型

无条件深度图生成的目的是通过深度生成模型从真实分布p(G)中抽样的一组观察到的真实图来学习分布pmodel(G)。根据生成过程的风格，我们可以将这些方法分为两个主要分支:(1)顺序生成:按顺序依次生成节点和边;(2)一次生成:根据矩阵表示建立一个概率图模型，一次生成所有节点和边。这两种生成图的方法各有优缺点。顺序生成虽然高效地执行了前一种生成的局部决策，但在保持长期依赖性方面存在困难。因此，图的一些全局属性(如无标度属性)很难包含进去。此外，现有的关于序列生成的工作仅限于预先定义的序列的顺序，从而留下了排列的作用。一次性生成方法可以通过多次迭代同步生成和细化整个图(即节点和边)，从而对图的全局属性进行建模，但由于需要对节点之间的全局关系进行集体建模，其时间复杂度通常超过O(N2)，因此大多数方法难以扩展到大型图。

用于图生成的条件深度生成模型

条件深度图生成的目标是根据观察到的一组现实图G及其对应的辅助信息(即条件y)学习条件分布pmodel(G|y)。辅助信息可以是类别标签、语义上下文、来自其他分布空间的图等。与无条件深度图生成相比，条件生成除了在生成图方面的挑战外，还需要考虑如何从给定条件中提取特征并将其整合到图的生成中。因此，为了系统地介绍现有的条件深度图生成模型，我们主要描述这些方法如何处理条件。由于条件可以是任何形式的辅助信息，因此它们被分为三种类型，包括图、序列和语义上下文，如图1中分类法树的黄色部分所示