# Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 90 references that are in the map.
- First posted on arXiv 12 Oct 2025.

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

- [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)
- [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)
- [Deep Supervised and Convolutional Generative Stochastic Network for Protein Secondary Structure Prediction](https://mlsanity.com/paper/1403.1347/) (2014)
- [TreeGAN: Syntax-Aware Sequence Generation with Generative Adversarial Networks](https://mlsanity.com/paper/1808.07582/) (2018)
- [Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)](https://mlsanity.com/paper/1703.08940/) (2017)
- [Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance](https://mlsanity.com/paper/2106.02026/) (2021)

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

- [ReLU Networks for Exact Generation of Similar Graphs](https://mlsanity.com/paper/2604.05929/) (2026)

## Abstract (arXiv)

The generation of trees with a specified tree edit distance has significant applications across various fields, including computational biology, structured data analysis, and image processing. Recently, generative networks have been increasingly employed to synthesize new data that closely resembles the original datasets. However, the appropriate size and depth of generative networks required to generate data with a specified tree edit distance remain unclear. In this paper, we theoretically establish the existence and construction of generative networks capable of producing trees similar to a given tree with respect to the tree edit distance. Specifically, for a given rooted, ordered, and vertex-labeled tree T of size n + 1 with labels from an alphabet Sigma, and a non-negative integer d, we prove that all rooted, ordered, and vertex-labeled trees over Sigma with tree edit distance at most d from T can be generated using a ReLU-based generative network with size O(n3 ) and constant depth. The proposed networks were implemented and evaluated for generating trees with up to 21 nodes. Due to their deterministic architecture, the networks successfully generated all valid trees within the specified tree edit distance. In contrast, state-of-the-art graph generative models GraphRNN and GraphGDP, which rely on non-deterministic mechanisms, produced significantly fewer valid trees, achieving validation rates of only up to 35% and 48%, respectively. These findings provide a theoretical foundation towards construction of compact generative models and open new directions for exact and valid tree-structured data generation. An implementation of the proposed networks is available at https://github.com/MGANN-KU/TreeGenReLUNetworks.