Abstract
Graph generation remains a significant challenge due to the non-Euclidean nature of graph data. While image generation benefits from hierarchical upsampling, graph models often lack a corresponding "unpooling" operation. This paper proposes a novel graph unpooling layer (UL) that expands a graph by splitting nodes and learning connectivity through probabilistic multi-layer perceptrons. We prove that this layer preserves connectivity and possesses universal expressivity for connected graphs. Our UL-based GAN and VAE architectures outperform traditional one-shot generators on synthetic and molecular benchmarks, achieving high validity and uniqueness in generated structures.
Introduction
In computer vision, generating high-resolution images typically involves starting with a small feature map and using unpooling or transpose-convolutional layers to grow it into a detailed output. However, applying this "upsampling" logic to graphs—such as molecules, social networks, or protein structures—is non-trivial due to the lack of a fixed grid. This paper introduces a trainable graph unpooling layer that allows generative models (like GANs and VAEs) to "grow" a graph from a tiny seed into a complex, detailed structure.
The Challenge of Graph Generation
Generating graphs is difficult because they possess an arbitrary number of nodes and complex connectivity patterns. Current approaches generally fall into two categories:
- One-shot generators: These output an entire adjacency matrix at once. While fast, they often produce disconnected graphs and struggle to scale.
- Sequential generators: These add nodes or edges one by one. While they respect structure, they are computationally slow and fail to leverage the hierarchical "coarse-to-fine" logic that has made image-based GANs successful.
The proposed Unpooling Layer (UL) bridges this gap by providing a way to take a coarse graph and expand it while maintaining structural integrity.
Methodology: The Unpooling Layer
The core innovation is the Unpooling Layer (UL), which performs three primary functions:
- Node Expansion: The layer selects specific nodes in the input graph and replaces each "parent" node with two "children" nodes.
- Structure Learning: The model learns where edges should be placed using a suite of seven Multi-Layer Perceptrons (MLPs). These MLPs make probabilistic decisions regarding intra-links (edges between the two new children) and inter-links (how children connect to the neighbors of their parent).
- Feature Generation: Simultaneously, the layer learns the features for the newly created nodes and edges.
Because edge addition is a discrete choice, the authors utilize the REINFORCE algorithm to train structural parameters, while standard backpropagation handles feature learning.
Generative Architecture
By stacking these unpooling layers with Message Passing Neural Networks (MPNNs), the authors create a hierarchical generative pipeline. This allows the model to generate intermediate graphs of increasing complexity, similar to the stages of image synthesis in a Progressive GAN.
Theoretical Guarantees
- Connectivity: The authors provide a mathematical proof that if the input graph is connected, the unpooling layer is guaranteed to produce a connected output. This is critical for domains like chemistry, where disconnected components often represent invalid results.
- Universal Expressivity: They further prove that any connected graph can be generated by a sequence of these unpooling layers starting from a simple 3-node triangle.
Experimental Results
The researchers evaluated UL-based GANs and VAEs across four datasets: Waxman Random Graphs, Protein structures, QM9, and ZINC.
- Structural Fidelity: On Waxman and Protein datasets, the UL models significantly outperformed standard adjacency-matrix generators in capturing properties like edge density and clustering coefficients.
- Molecular Generation: On the ZINC dataset (larger drug-like molecules), the UL GAN achieved 100% uniqueness and novelty. While specialized chemical models might offer higher validity, the UL GAN proved far more competitive than other general-purpose graph generators.
- Latent Space Interpolation: The model demonstrated a smooth latent space, capable of transitioning between different molecular topologies (e.g., from string-like to ring-like structures) through simple vector arithmetic.
Conclusion
This work provides a powerful new primitive for graph generation. By introducing a trainable unpooling operation with connectivity guarantees, the authors enable hierarchical, coarse-to-fine generation for non-Euclidean data. Future work will focus on reducing the computational cost of the MLP-heavy structure learning and refining reward functions for specific chemical property optimization.
Summary updated