Abstract
Generating graph structures is a challenging problem due to the diverse representations and complex dependencies among nodes. In this paper, we introduce Graph Variational Recurrent Neural Network (GraphVRNN), a probabilistic autoregressive model for graph generation. Through modeling the latent variables of graph data, GraphVRNN can capture the joint distributions of graph structures and the underlying node attributes. We conduct experiments on the proposed GraphVRNN in both graph structure learning and attribute generation tasks. The evaluation results show that the variational component allows our network to model complicated distributions, as well as generate plausible structures and node attributes.
Introduction
Generating graphs—mathematical structures representing objects (nodes) and their relationships (edges)—is notoriously difficult. Unlike images or text, graphs lack a fixed grid or sequence; they are permutation-invariant and can exhibit complex, long-range dependencies. Existing generative models typically fall into two categories: global models like GraphVAE, which struggle with scalability beyond small graphs, and sequential models like GraphRNN, which scale better but often fail to capture the diversity of node attributes, often predicting the "average" attribute rather than the true distribution.
GraphVRNN addresses these challenges by combining the scalability of autoregressive sequences with the expressive power of Variational Autoencoders (VAEs). This hybrid approach allows the model to learn the joint distribution of both complex graph structures and diverse node attributes.
Methods: The GraphVRNN Architecture
GraphVRNN builds upon the sequential framework of GraphRNN but incorporates a Conditional Variational Autoencoder (CVAE) to model uncertainty and diversity.
The generation process follows several key steps:
- Linearization: Graphs are converted into a sequence of nodes and edge vectors using a Breadth-First Search (BFS) strategy.
- Node-level RNN: This component maintains the "memory" of the generated graph history.
- Variational Component: Instead of deterministic prediction, the RNN hidden state feeds into a Prior Network and a Posterior Network. These networks manage a latent variable ($z$). During training, the model learns to map graph history to a distribution in latent space.
- Decoders: A sample from the latent space, concatenated with the RNN's hidden state $[z_i, h_{i-1}]$, is passed to an Edge-level RNN for structure generation and an Attribute Decoder (MLP) for node feature generation.
By utilizing a learned prior conditioned on the graph's history, GraphVRNN can capture intricate structural dependencies that fixed-prior models might miss.
Experimental Setup
The model was evaluated on several synthetic and real-world-inspired datasets:
- Ego-small: A small-scale 1-hop citation network.
- Com-small & Com-mix: Community-based datasets with varying connection probabilities to test structural complexity and scalability.
- Com-attr: A dataset where nodes in different communities have distinct attribute distributions (e.g., means at 1.5 and -0.5), specifically designed to test attribute generation.
Results and Discussion
Overcoming the "Averaging Trap"
A primary insight of this work is that deterministic models like GraphRNN suffer from "mode collapse" in attribute generation. They tend to predict the mean of the data, resulting in a single-peaked distribution that fails to represent multi-modal data.
As shown in the density plots, GraphVRNN successfully recovers the distinct "humps" corresponding to different communities, whereas GraphRNN produces an inaccurate single peak. Quantitatively, GraphVRNN achieved an Earth Mover’s Distance (EMD) of 0.113 on the Com-attr dataset, significantly better than GraphRNN’s 0.460.
Structural Fidelity
In terms of structural metrics like degree distribution and clustering coefficients (measured via Maximum Mean Discrepancy), GraphVRNN consistently matched or outperformed existing baselines. It showed particular strength in the "Com-mix" dataset, effectively modeling complex intra-connection probabilities.
Conclusion
GraphVRNN demonstrates that joint probabilistic modeling of structure and attributes is essential for high-fidelity graph generation. By incorporating a variational component, the model avoids the "averaging trap" of deterministic sequences. Future work will focus on applying this architecture to more irregular real-world domains, such as molecular generation and social network simulation, while exploring more sophisticated prior-learning mechanisms to further enhance expressivity.
Summary updated