# Size Matters: Large Graph Generation with HiGGs

arXiv: https://arxiv.org/abs/2306.11412 · HTML: https://mlsanity.com/paper/2306.11412/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 20 Jun 2023.

## Builds on (most cited first, 20 of 20)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [GraphGAN: Graph Representation Learning with Generative Adversarial Nets](https://mlsanity.com/paper/1711.08267/) (2017)
- [Exploring Randomly Wired Neural Networks for Image Recognition](https://mlsanity.com/paper/1904.01569/) (2019)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [A Systematic Survey on Deep Generative Models for Graph Generation](https://mlsanity.com/paper/2007.06686/) (2020)
- [A Survey on Deep Graph Generation: Methods and Applications](https://mlsanity.com/paper/2203.06714/) (2022)
- [GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation](https://mlsanity.com/paper/2212.01842/) (2022)
- [NVDiff: Graph Generation through the Diffusion of Node Vectors](https://mlsanity.com/paper/2211.10794/) (2022)
- [Labeled Graph Generative Adversarial Networks](https://mlsanity.com/paper/1906.03220/) (2019)
- [Realistic Synthetic Social Networks with Graph Neural Networks](https://mlsanity.com/paper/2212.07843/) (2022)

## Built on by (most cited first, 3 of 3)

- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [Diffusion Twigs with Loop Guidance for Conditional Graph Generation](https://mlsanity.com/paper/2410.24012/) (2024)
- [Overcoming Order in Autoregressive Graph Generation](https://mlsanity.com/paper/2402.03387/) (2024)

## Abstract (arXiv)

Large graphs are present in a variety of domains, including social networks, civil infrastructure, and the physical sciences to name a few. Graph generation is similarly widespread, with applications in drug discovery, network analysis and synthetic datasets among others. While GNN (Graph Neural Network) models have been applied in these domains their high in-memory costs restrict them to small graphs. Conversely less costly rule-based methods struggle to reproduce complex structures. We propose HIGGS (Hierarchical Generation of Graphs) as a model-agnostic framework of producing large graphs with realistic local structures. HIGGS uses GNN models with conditional generation capabilities to sample graphs in hierarchies of resolution. As a result HIGGS has the capacity to extend the scale of generated graphs from a given GNN model by quadratic order. As a demonstration we implement HIGGS using DiGress, a recent graph-diffusion model, including a novel edge-predictive-diffusion variant edge-DiGress. We use this implementation to generate categorically attributed graphs with tens of thousands of nodes. These HIGGS generated graphs are far larger than any previously produced using GNNs. Despite this jump in scale we demonstrate that the graphs produced by HIGGS are, on the local scale, more realistic than those from the rule-based model BTER.