Source-linked AI summary
Efficient Graph Generation with Graph Recurrent Attention Networks
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Duvenaud, Raquel Urtasun, Richard S. Zemel
TL;DR
Graph generative models need to represent complex dependencies while remaining efficient and handling node-ordering variability. GRAN generates node-and-edge blocks with attention-based GNN conditioning, mixture-of-Bernoulli outputs, and canonical-ordering marginalization. It achieves state-of-the-art performance on standard benchmarks and generates graphs up to 5K nodes.
Problem
Existing graph generators face challenges modeling complex dependencies, reducing sequential generation cost, and handling node-ordering permutations as graphs scale.
Method
GRAN generates graph blocks autoregressively using attention-based GNNs, mixture-of-Bernoulli output distributions, and marginalization over canonical node orderings.
Results
GRAN achieves state-of-the-art performance on standard benchmarks and generates graphs with up to 5K nodes.
Takeaways & Limitations
Block size and sampling stride provide a flexible efficiency-quality trade-off, while the framework extends deep graph generation to graphs beyond the scale of existing models.
Abstract
from arXiv · showhide
We propose a new family of efficient and expressive deep generative models of graphs, called Graph Recurrent Attention Networks (GRANs). Our model generates graphs one block of nodes and associated edges at a time. The block size and sampling stride allow us to trade off sample quality for efficiency. Compared to previous RNN-based graph generative models, our framework better captures the auto-regressive conditioning between the already-generated and to-be-generated parts of the graph using Graph Neural Networks (GNNs) with attention. This not only reduces the dependency on node ordering but also bypasses the long-term bottleneck caused by the sequential nature of RNNs. Moreover, we parameterize the output distribution per block using a mixture of Bernoulli, which captures the correlations among generated edges within the block. Finally, we propose to handle node orderings in generation by marginalizing over a family of canonical orderings. On standard benchmarks, we achieve state-of-the-art time efficiency and sample quality compared to previous models. Additionally, we show our model is capable of generating large graphs of up to 5K nodes with good quality. To the best of our knowledge, GRAN is the first deep graph generative model that can scale to this size. Our code is released at: https://github.com/lrjconan/GRAN.
1 Introduction
Graph generative models support applications involving relational and structural data, but existing approaches face limitations in modeling complex dependencies and scaling autoregressive generation. GRAN addresses these challenges with blockwise generation, attention-based GNNs, mixture-of-Bernoulli outputs, and canonical-ordering marginalization, achieving strong benchmark performance and generation of graphs up to 5K nodes.
- Motivation: Graph generation supports applications in drug design, architecture search, and network science because graphs represent relational and structural information.
- Existing limitations: Traditional random graph models have limited capacity to model complex dependencies and typically capture only a few statistical properties.
- Existing limitations: GraphRNN uses sequential adjacency-matrix generation, but requires O(N^2) steps in its best model and can create long-term dependency bottlenecks.
- GRAN: GRAN generates a block of nodes and associated edges per autoregressive step, yielding O(N) decisions while exposing an efficiency-quality trade-off through block size and sampling stride.
- GRAN: An attention-based GNN conditions newly added nodes on the topology of the generated graph, reducing ordering dependence and distinguishing multiple new nodes.
- GRAN: A mixture of Bernoulli distributions captures correlations among multiple edges generated within a block.
- GRAN: GRAN marginalizes over canonical node orderings such as DFS, BFS, and k-core, and achieves state-of-the-art benchmark performance while generating graphs up to 5K nodes.
2 Model
GRAN represents graphs through ordered adjacency matrices and generates lower-triangular rows in node blocks conditioned on the existing graph. Attention-based GNNs, mixture-of-Bernoulli outputs, strided sampling, and canonical-ordering marginalization target efficient, expressive generation.
- Representation and canonical orderings: GRAN models each graph ordering through an adjacency matrix and marginalizes over distinctive canonical orderings rather than a single arbitrary ordering.The likelihood bound becomes tighter as the selected ordering family grows, subject to a trade-off in computational cost.
- Representation and canonical orderings: For undirected graphs, GRAN generates the lower-triangular adjacency matrix one row or block of rows at a time, then reconstructs Aπ as Lπ + Lπ⊤.Rows are padded with zeros and generation continues until the maximum number of time steps is reached.
- Block generation: GRAN generates B rows per step, reducing the number of sequential decisions by O(N), while block size trades model expressiveness for speed.The number of steps is T = ⌈N/B⌉, and larger blocks reduce steps but make block modeling more difficult.
- Graph recurrent attention: An augmented graph containing existing nodes and the new block is processed by an attention-based GNN to encode graph structure for current-block edge generation.The block includes internal edges and edges linking new nodes to previously generated nodes; masks distinguish existing nodes from relative positions in the new block.
- Output distribution: The output distribution uses a mixture of Bernoulli components, allowing dependent edge generation while computing mixture components in parallel.With K = 1, the distribution reduces to independent Bernoulli edges conditioned on the existing graph; K > 1 introduces dependence through latent mixture components.
- Sampling efficiency: Strided sampling lets a trained model use different generation strides without retraining, trading speed for quality through overlapping blocks.Stride S = B maximizes speed, whereas smaller S can improve quality by modeling dependencies across multiple steps.
3 Related Work
Related graph-generation research includes traditional random graph models, non-autoregressive neural models, and autoregressive neural models. GRAN targets efficient generation of large, general graphs beyond prior domain-specific or relatively small settings.
- Traditional approaches: Traditional random graph models provide mathematically understood stochastic processes but generally have limited capacity for complex dependencies and only a few graph statistics.Examples include random and preferential-attachment models, exponential random graphs, and Kronecker graph models.
- Non-autoregressive deep models: Non-autoregressive deep models generate graph components independently or with weak dependencies, including VAE-based adjacency and molecule-graph approaches.Graph VAE methods generate individual adjacency entries independently given latent variables, making them efficient but limiting dependency modeling.
- Autoregressive deep models: Autoregressive models capture complex dependencies by sequentially generating graph entries, nodes, edges, motifs, or domain-specific graph representations.Prior approaches use RNNs, sequential node-and-edge additions, junction trees, constraints, or random-walk encoders.
- Autoregressive deep models: Earlier autoregressive systems often focused on domain-specific and relatively small graphs, whereas GRAN targets efficient generation of larger general graphs.The related-work discussion identifies molecule-focused methods and GraphRNN as prior scalable general frameworks.
4 Experiments
Experiments evaluate GRAN on synthetic and real graph datasets using graph-statistics distributions, visualizations, and efficiency measurements. GRAN achieves state-of-the-art sample quality while exposing an efficiency-quality trade-off through stride and mixture choices.
- Dataset and Evaluation Metrics: GRAN is evaluated on grid, protein, and point-cloud datasets spanning graphs from 100 to over 5K nodes.The point-cloud dataset contains 41 simulated 3D objects, with average graph size above 1K nodes and maximum size above 5K nodes.
- Dataset and Evaluation Metrics: The evaluation compares generated and ground-truth graph-statistic distributions because likelihoods are difficult to measure for ordering-dependent autoregressive models.Metrics include degree, clustering-coefficient, and four-node-orbit distributions, with spectrum also reported in the comparison table.
- Benchmarking Sample Quality: GRAN achieves state-of-the-art sample quality on all benchmarks, while competing GraphVAE and GraphRNN variants cannot scale to the point-cloud dataset.Those competing models encounter out-of-memory issues, and GraphRNN runtimes become prohibitively long for large graphs.
- Efficiency vs. Sample Quality: 6 times faster than GraphRNN with stride 1, while stride 16 exceeds 80x speedup but noticeably worsens model quality.GraphRNN takes around 9.5 seconds per grid graph on average; increasing stride trades quality for speed.
- Efficiency vs. Sample Quality: Figure 3 reports MMD on the left axis and speed ratio on the right axis to show the efficiency-quality trade-off.The models are trained with block size 16 on grid graphs and evaluated on the validation set.
- Ablation Study: Increasing the number of Bernoulli mixtures improves performance, especially on the orbit metric, while DFS ordering performs similarly to using all orderings on grid graphs.The model uses 20 mixtures as a balance between performance and computational cost; the optimal canonical-ordering set is dataset dependent.
5 Conclusion
The conclusion presents GRAN as an efficient graph-generation model that combines blockwise generation, attention-based GNN conditioning, mixture outputs, and canonical-ordering marginalization. It reports state-of-the-art benchmark performance and successful generation of graphs beyond the scale of prior deep graph generative models.
- 5 Conclusion: GRAN generates one adjacency-matrix block at a time through an O(N)-step process.Block size and sampling stride control the efficiency-quality trade-off.
- 5 Conclusion: Attention-based GNNs condition each generated block on the existing graph, while mixtures of Bernoulli capture correlations among edges generated per step.The conclusion identifies both mechanisms as central components of GRAN.
- 5 Conclusion: GRAN achieves state-of-the-art performance on standard benchmarks and produces large graphs beyond the limits of other deep graph generative models.The paper also identifies future applications where graphs are latent or partially observed.
6 Appendix
The appendix describes k-core node ordering and reports supplementary evaluations, ablations, and visual examples for generated graphs.
- 6.1 K-Core Node Ordering: K-core node ordering ranks nodes by descending core number, then by descending degree within each core.The ordering proceeds from the largest core to the second largest and onward.
- 6.2 Lobster Graphs: Random lobster graphs are evaluated with an additional metric measuring the accuracy of generated graphs being lobster graphs.The study generates 100 random lobster graphs with 10 ≤|V | ≤100.
- 6.2 Lobster Graphs: Table 3 compares deep graph generative models on random lobster graphs, with asterisks marking the authors’ own implementation.The accompanying discussion reports that GRAN performs slightly worse on the evaluated comparison.
- 6.3 Full Ablation Study & Visual Examples: Additional visual examples of generated graphs are provided in Figures 4, 5, and 6, including samples on the 3D point cloud dataset.These figures visualize samples from different models and from GRAN.
- 6.3 Full Ablation Study & Visual Examples: Table 4 presents a full ablation study on grid graphs using DFS, BFS, k-core, degree-descent, and default node orderings.Runtime is measured while generating a minibatch of 20 graphs.