mlsanityData to 7 Oct 2026

ReLU Networks for Exact Generation of Similar Graphs

arXiv 2604.05929 ↗First posted 7 Apr 2026cs.LG cs.AI cs.DMcited by 0

Not on the map. Why?

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.

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

Builds on

31 of 83 references.

References · 31

  1. 2020Denoising Diffusion Probabilistic Modelscited by 20,851
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2016WaveNet: A Generative Model for Raw Audiocited by 1,710
  4. 2022Diffusion Models: A Comprehensive Survey of Methods and Applicationscited by 1,107
  5. 2019An Introduction to Variational Autoencoderscited by 997
  6. 2016Conditional Image Generation with PixelCNN Decoderscited by 859
  7. 2016Pixel Recurrent Neural Networkscited by 814
  8. 2018GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Modelscited by 406
  9. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  10. 2016On the Expressive Power of Deep Neural Networkscited by 302
  11. 2015DRAW: A Recurrent Neural Network For Image Generationcited by 190
  12. 2019Complexity of Linear Regions in Deep Networkscited by 166
19 more
  1. 2013Generalized Denoising Auto-Encoders as Generative Modelscited by 113
  2. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  3. 2018Molecular generative model based on conditional variational autoencoder for de novo molecular designcited by 73
  4. 2018Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matchingcited by 45
  5. 2022GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generationcited by 43
  6. 2020Video Generative Adversarial Networks: A Reviewcited by 33
  7. 2017Generating and designing DNA with deep generative modelscited by 30
  8. 2025Learning-Order Autoregressive Models with Application to Molecular Graph Generationcited by 29
  9. 2016Neural Random Forestscited by 25
  10. 2018Towards Audio to Scene Image Synthesis using Generative Adversarial Networkcited by 23
  11. 2019Generative Models for Automatic Chemical Designcited by 23
  12. 2024Generative Modelling of Structurally Constrained Graphscited by 17
  13. 2019Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theoremcited by 15
  14. 2024Advancing Graph Generation through Beta Diffusioncited by 13
  15. 2025Flatten Graphs as Sequences: Transformers are Scalable Graph Generatorscited by 12
  16. 2014Deep Supervised and Convolutional Generative Stochastic Network for Protein Secondary Structure Predictioncited by 8
  17. 2025GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Codecited by 8
  18. 2015A Quadratic Assignment Formulation of the Graph Edit Distancecited by 4
  19. 2025Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distancecited by 1

Built on by

Not cited yet.