# Graph Generation with K2-trees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 50 references that are in the map.
- First posted on arXiv 30 May 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [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)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [MoFlow: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/2006.10137/) (2020)
- [GraphDF: A Discrete Flow Model for Molecular Graph Generation](https://mlsanity.com/paper/2102.01189/) (2021)
- [GraphNVP: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/1905.11600/) (2019)
- [Graphite: Iterative Generative Modeling of Graphs](https://mlsanity.com/paper/1803.10459/) (2018)
- [Graph Normalizing Flows](https://mlsanity.com/paper/1905.13177/) (2019)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [GraphEBM: Molecular Graph Generation with Energy-Based Models](https://mlsanity.com/paper/2102.00546/) (2021)
- [Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling](https://mlsanity.com/paper/2305.04111/) (2023)
- [Hit and Lead Discovery with Explorative RL and Fragment-based Molecule Generation](https://mlsanity.com/paper/2110.01219/) (2021)
- [Mol-CycleGAN - a generative model for molecular optimization](https://mlsanity.com/paper/1902.02119/) (2019)
- [GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation](https://mlsanity.com/paper/2001.08184/) (2020)
- [Self-Referencing Embedded Strings (SELFIES): A 100% robust molecular string representation](https://mlsanity.com/paper/1905.13741/) (2019)
- [Improving Graph Generation by Restricting Graph Bandwidth](https://mlsanity.com/paper/2301.10857/) (2023)
- [Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations](https://mlsanity.com/paper/1806.01799/) (2018)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)

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

- [A Simple and Scalable Representation for Graph Generation](https://mlsanity.com/paper/2312.02230/) (2023)
- [Stable Transformers for Graph Generation](https://mlsanity.com/paper/2609.39739/) (2026)
- [Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction](https://mlsanity.com/paper/2610.04056/) (2026)

## Abstract (arXiv)

Generating graphs from a target distribution is a significant challenge across many domains, including drug discovery and social network analysis. In this work, we introduce a novel graph generation method leveraging K2-tree representation, originally designed for lossless graph compression. The K2-tree representation encompasses inherent hierarchy while enabling compact graph generation. In addition, we make contributions by (1) presenting a sequential K2-treerepresentation that incorporates pruning, flattening, and tokenization processes and (2) introducing a Transformer-based architecture designed to generate the sequence by incorporating a specialized tree positional encoding scheme. Finally, we extensively evaluate our algorithm on four general and two molecular graph datasets to confirm its superiority for graph generation.