Mathematical Ideas for Graph Generation

Other Talks
Thursday, March 3, 2022 - 11:00am for 1 hour (actually 50 minutes)
Gilad Lerman – School of Math, University of Minnesota – lerman@umn.edu
Sung Ha Kang

Generative networks have made it possible to generate meaningful signals such as images and texts. They were also extended to graphs and applied, for example, to generate molecules. However, the mathematical properties of generative methods are unclear, and training good generative models is difficult. Moreover, some basic and intuitive ideas of generative networks for signals and images do not apply to graphs and we thus focus on this talk on graph generation. An earlier joint work of the speaker generalized Mallat's scattering transform to graphs and later used it as an encoder within an autoencoder for graph generation (while applying a simple Gaussianization procedure to the output of the encoder) . For the graph scattering component, this work proved asymptotic invariance to permutations and stability to graph manipulations. The issue is that the decoder of this graph generation component used two fully connected networks and was not adapted to the graph structure. In fact, many other graph generation methods do not sufficiently utilize the graph structure. In order to address this issue, I will present a new recent joint work that develops a novel and trainable graph unpooling layer for effective graph generation. Given a graph with features, the unpooling layer enlarges this graph and learns its desired new structure and features. Since this unpooling layer is trainable, it can be applied to graph generation either in the decoder of a variational autoencoder or in the generator of a generative adversarial network (GAN). We establish connectivity and expressivity. That is, we prove that the unpooled graph remains connected and any connected graph can be sequentially unpooled from a 3-nodes graph. We apply the unpooling layer within the GAN generator and address the specific task of molecular generation. This is a joint work with Yinglong Guo and Dongmian Zou.