NeurIPS 2022 | 用变分编码器生成周期图，时间、空间复杂度最低

2022 年 10 月 22 日 机器之心

机器之心专栏

机器之心编辑部

本文提出了一个可以实现周期图生成的深度生成模型。该模型可以自动识别并解耦周期图的局部和全局结构，不仅可以保证生成图的周期性，还能实现较低的时间、空间复杂度用以保障生成过程的高效。该研究已被 NeurIPS 2022 接收。

图是描述物体及其之间相互关系的一类无处不在的数据结构。作为一种特殊的图结构，周期图（periodic graph）由重复的基本单元组成，因此可以自然而然地表征许多真实世界中的结构，例如包含重复晶胞的晶体网络，包含重复网格的多边形网络数据等等（图 1）。因此，探索、拟合并且生成周期图结构在真实世界的应用中有着极大的潜力。这些应用包括材料设计，图形结构合成等。

图 1：周期图示例，基本单元被标出：(a) 鳞石英结构；(b) 石墨烯结构；(c) 三角形网格结构。

和广义上的图生成不同，周期性图生成需要保证生成的图结构的周期性。周期性图生成有着很长的历史。传统的方法可以被分为两类：面向特定领域的方法和基于几何学的方法。顾名思义，面向特定领域的方法基于特定的领域专业知识生成周期图；基于几何学的方法或者借助于预先定义的几何原理来修饰目标图结构，或者简单地将最初的结构片段粘连成周期图。这两种方式均需要预先得知并且将图生成限定于特定的领域专业知识或者几何原理，因此他们并不能很好地生成这些已知原理限定范围外的图。除此之外，很多领域的专业知识是很匮乏的，因此导致现有的方法无法实现有效的周期图生成。

深度图生成模型旨在通过图神经网络学习广义上图结构的表征分布，由于生成图需要满足周期性，这些模型无法被直接用于生成周期图。扩展现有的深度图生成模型也面临着以下挑战：

保证生成图具有周期性。现有的用于实现广义图生成的模型通常不能够识别或者生成周期图的可重复单元（或者可重复的局部子图）。传统的图生成目标函数，如重构误差，只能够评估生成图的整体质量，并不能评估这些局部结构以及他们之间如何连接。
学习局部和全局结构。周期图有两个关键的组成部分，即刻画可重复单元的局部结构和刻画这些可重复单元在全局上如何连接的全局结构。因此，能够区分并且控制这两种结构对于生成模型来说尤其重要，即使现有的方法并不能对局部和全局结构的表征实现解耦。
大型周期图的学习效率。由于周期图包含重复的单元，它的结构充满了多余的信息，因此现有的图生成模型非常低效。因此在周期图生成过程中实现去重复化也至关重要。

为了解决这些挑战，作者开发了周期图解耦变分编码器（Periodic-Graph Disentangled Variational Auto-encoder, PGD-VAE）。PGD-VAE 能够自动学习，解耦并且生成周期图的局部和全局结构。特别地，PGD-VAE 包含一个局部结构编码器以及一个全局结构编码器用来从周期图的表征中解耦局部和全局的语义。除此之外，PGD-VAE 的解码器包含一个局部结构解码器、一个全局结构解码器、一个邻域解码器以及一个组装算法用来组装局部和全局结构并且保证图的周期性。为了实现局部和全局表征的解耦，作者设计了一个全新的目标函数。该目标函数可以保证具有相同可重复单元的周期图的局部表征相同。本文的贡献可总结为如下几个方面：

作者提出了一个全新的变分编码器，PGD-VAE。PGD-VAE 可以通过学习周期图的局部结构，全局结构以及局部结构之间的邻域链接来分解并合成周期图。
作者设计了一个全新的目标函数来实现周期图局部和全局表征语义的解耦。该目标函数可以确保拥有相同局部结构的周期图的局部表征相同。
作者利用多个真实数据和合成数据进行了丰富的对比实验来展示 PGD-VAE 的有效性。

论文地址：https://web7.arxiv.org/pdf/2201.11932v2.pdf

周期图定义

定义周期图为，其中代表图的节点，代表图的边。图的局部结构被定义为大小为 n 的基本单元，即该基本单元包含的节点数量为 n 。假设 G 图包含 m 个这样的基本单元以及它们之间的连接，因此是所有基本单元中节点的集合，是基本单元内以及基本单元之间所有边的结合。代表图的邻接矩阵，其中如果，此外。另外定义三个组成的矩阵：(1)是基本单元的邻接矩阵；(2)是定义这些重复单元之间相互链接的邻接矩阵；(3)是定义相邻基本单元内的节点如何链接的关联矩阵。

下面展示 A 是可以由唯一得到。定义为一二元矩阵，，其中 J 为分块对角矩阵并且其对角块内的元素均为1。此外，定义为将 m 个大小为 n 的单位矩阵拼接起来的矩阵。定义两个掩码矩阵，其中对角块内的元素均为 1，大小为 n 的非对角块内元素为0，内大小为 n 的分块上三角矩阵内元素为 1，其他分块内的元素为 0。因此，A 可由按如下形式表示：

该矩阵运算构成了 PGD-VAE 最后的组装算法。

周期图生成模型的目标是学习条件概率分布。这里定义为模型基于图结构学到的图表征，其中代表图重复单元（局部结构）的表征语义，代表图全局结构的表征语义。

目标函数

基于 VAE 框架的 PGD-VAE 首先具有 VAE 的目标函数：

假设相互独立，只由决定，同时控制，在上式基础上得到：

为了促进局部和全局结构的解耦，强制拥有相同基本单元的图的相同：

其中分表代表拥有第 i 种基本单元的第 j 个周期图的局部和全局表征。是拉格朗日因子。此外为了优化上述目标函数，在 KKT 条件下，将两个限制条件转化为:

除此之外，还需要强制拥有相同基本单元的图的相同，拥有不同基本单元的图的不同。通过最小化如下对比损失函数来实现这个目的：

其中是温度参数，是用来计算对比损失函数的余弦相似函数。

目标函数的最后一块拼图则是重构误差：

因此目标函数 L 可以写作：

PGD-VAE 模型结构

图 2：周期图解耦变分编码器（PGD-VAE）。分别代表由局部结构编码器和全局结构编码器学到的局部和全局表征语义。由局部结构解码器、邻域解码器和全局结构解码器分别生成。A 最终由通过组装算法生成。

总的来说，PGD-VAE 是一个端到端的模型，通过 A 作为模型输入，通过不同模块以及目标函数自动识别。

PGD-VAE 包含两个编码器：局部结构编码器（local-pattern encoder）和全局结构编码器（global-pattern encoder）。局部结构编码器用以学习周期图的局部表征。为了计算图的局部表征，特别地，局部结构编码器通过节点表征聚类（node embedding clustering）来识别周期图可重复单元内的代表性节点，因此学到的局部表征可以排除周期图的全局性信息（比如周期图的大小）。此外，为了使图的全局表征包括全局信息，作者利用 Graph Isomorphism Network（GIN）和加和池化确保编码器的表达能力。