# ReLU Networks for Exact Generation of Similar Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 83 references that are in the map.
- First posted on arXiv 7 Apr 2026.

## Builds on (most cited first, 30 of 31)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [WaveNet: A Generative Model for Raw Audio](https://mlsanity.com/paper/1609.03499/) (2016)
- [Diffusion Models: A Comprehensive Survey of Methods and Applications](https://mlsanity.com/paper/2209.00796/) (2022)
- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [Conditional Image Generation with PixelCNN Decoders](https://mlsanity.com/paper/1606.05328/) (2016)
- [Pixel Recurrent Neural Networks](https://mlsanity.com/paper/1601.06759/) (2016)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [DRAW: A Recurrent Neural Network For Image Generation](https://mlsanity.com/paper/1502.04623/) (2015)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Generalized Denoising Auto-Encoders as Generative Models](https://mlsanity.com/paper/1305.6663/) (2013)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Molecular generative model based on conditional variational autoencoder for de novo molecular design](https://mlsanity.com/paper/1806.05805/) (2018)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation](https://mlsanity.com/paper/2212.01842/) (2022)
- [Video Generative Adversarial Networks: A Review](https://mlsanity.com/paper/2011.02250/) (2020)
- [Generating and designing DNA with deep generative models](https://mlsanity.com/paper/1712.06148/) (2017)
- [Learning-Order Autoregressive Models with Application to Molecular Graph Generation](https://mlsanity.com/paper/2503.05979/) (2025)
- [Neural Random Forests](https://mlsanity.com/paper/1604.07143/) (2016)
- [Towards Audio to Scene Image Synthesis using Generative Adversarial Network](https://mlsanity.com/paper/1808.04108/) (2018)
- [Generative Models for Automatic Chemical Design](https://mlsanity.com/paper/1907.01632/) (2019)
- [Generative Modelling of Structurally Constrained Graphs](https://mlsanity.com/paper/2406.17341/) (2024)
- [Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem](https://mlsanity.com/paper/1912.04378/) (2019)
- [Advancing Graph Generation through Beta Diffusion](https://mlsanity.com/paper/2406.09357/) (2024)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code](https://mlsanity.com/paper/2505.02124/) (2025)
- [Deep Supervised and Convolutional Generative Stochastic Network for Protein Secondary Structure Prediction](https://mlsanity.com/paper/1403.1347/) (2014)
- [A Quadratic Assignment Formulation of the Graph Edit Distance](https://mlsanity.com/paper/1512.07494/) (2015)

## Abstract (arXiv)

Generation of graphs constrained by a specified graph edit distance from a source graph is important in applications such as cheminformatics, network anomaly synthesis, and structured data augmentation. Despite the growing demand for such constrained generative models in areas including molecule design and network perturbation analysis, the neural architectures required to provably generate graphs within a bounded graph edit distance remain largely unexplored. In addition, existing graph generative models are predominantly data-driven and depend heavily on the availability and quality of training data, which may result in generated graphs that do not satisfy the desired edit distance constraints. In this paper, we address these challenges by theoretically characterizing ReLU neural networks capable of generating graphs within a prescribed graph edit distance from a given graph. In particular, we show the existence of constant depth and O(n^2 d) size ReLU networks that deterministically generate graphs within edit distance d from a given input graph with n vertices, eliminating reliance on training data while guaranteeing validity of the generated graphs. Experimental evaluations demonstrate that the proposed network successfully generates valid graphs for instances with up to 1400 vertices and edit distance bounds up to 140, whereas baseline generative models fail to generate graphs with the desired edit distance. These results provide a theoretical foundation for constructing compact generative models with guaranteed validity.