[2604.05929] ReLU Networks for Exact Generation of Similar Graphs

Computer Science > Machine Learning arXiv:2604.05929 (cs) [Submitted on 7 Apr 2026] Title:ReLU Networks for Exact Generation of Similar Graphs Authors:Mamoona Ghafoor, Tatsuya Akutsu View a PDF of the paper titled ReLU Networks for Exact Generation of Similar Graphs, by Mamoona Ghafoor and Tatsuya Akutsu View PDF HTML (experimental) Abstract: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 th...