Abstract
We propose a novel and trainable graph unpooling layer for effective graph generation. The unpooling layer receives an input graph with features and outputs an enlarged graph with desired structure. This approach mimics the coarse-to-fine upsampling process found in computer vision, allowing for hierarchical graph generation that maintains global context while scaling to complex topologies.
Introduction
In computer vision, generating high-resolution images is typically achieved through a "coarse-to-fine" process. Models start with a low-resolution feature map and use unpooling or transpose-convolution layers to iteratively increase resolution and add detail. In contrast, graph generation has historically lacked a natural "upsampling" mechanism.
Existing graph generative models generally fall into two categories: one-shot generators that predict an entire adjacency matrix at once, and sequential generators that add nodes one by one. One-shot methods struggle to scale and often produce disconnected graphs, while sequential methods are slow and can lose global structural context. This research introduces a trainable Graph Unpooling Layer (UL) to bridge this gap, enabling graphs to be "grown" hierarchically.
The Graph Unpooling Layer
The core innovation is a layer that takes an existing graph and "expands" it through a three-step probabilistic process. Unlike standard Graph Neural Networks (GNNs) that only update node features, the UL modifies the graph's topology:
- Node Expansion: The layer identifies specific nodes to "unpool," replacing each selected node with two "children" nodes.
- Structure Building: The model determines connectivity in two ways: intra-links (connecting the two new children to each other) and inter-links (connecting children to the neighbors of their parent node).
- Feature Generation: Multi-Layer Perceptrons (MLPs) generate features for the new nodes and edges.
Because structural decisions (adding an edge) are discrete and non-differentiable, the authors employ the REINFORCE algorithm for structural parameters, while standard backpropagation handles feature learning. This allows the entire generation pipeline to be trained end-to-end within GAN or VAE frameworks.
Theoretical Properties
The proposed unpooling layer offers two significant mathematical advantages:
- Connectivity Guarantee: The authors prove that if the input graph to an unpooling layer is connected, the output graph is guaranteed to remain connected. This solves a major issue in molecule generation, where models often produce fragmented "bags of parts."
- Universal Expressivity: A "Corollary of Expressivity" demonstrates that any connected graph can be generated from a simple 3-node triangle through a finite series of these unpooling steps. This suggests that the model can theoretically capture any complex network topology.
Experimental Results
The researchers evaluated the UL GAN and UL VAE architectures across synthetic and real-world datasets, including Waxman random graphs, protein structures, and molecular datasets (QM9 and ZINC).
Structural Accuracy
On the Waxman and Protein datasets, the unpooling models demonstrated superior performance in capturing mathematical properties like link density and clustering. As shown in the distribution plots, the UL-based models closely track the source dataset's characteristics compared to traditional baselines.
Molecule Generation
In molecular benchmarks, the UL GAN achieved a Validity of 90.7% and a Uniqueness of 82.6% on the QM9 dataset. More impressively, when scaled to the larger ZINC dataset (up to 38 heavy atoms), the model maintained 100% uniqueness and novelty. This robustness on larger graphs highlights the efficiency of the hierarchical approach, which reaches target sizes much faster than sequential node-by-node generators.
Conclusion
The Graph Unpooling Layer provides a scalable, trainable, and theoretically grounded method for graph generation. By mimicking the hierarchical upsampling of image generators, it ensures connectivity and structural integrity in complex domains like drug discovery. Future work will focus on optimizing the computational cost of the edge-probability calculations and refining reward functions for specific chemical properties.
Summary updated