ReLU Networks for Exact Generation of Similar Graphs

Mamoona Ghafoor; Tatsuya Akutsu

cs.LGApr 7, 2026

ReLU Networks for Exact Generation of Similar Graphs

Authors: Mamoona Ghafoor, Tatsuya Akutsu

Organizations: Bioinformatics Center, Institute for Chemical Research, Department of Intelligence Sciences and Technology, Kyoto University, Uji 611-0011, Japan

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 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.

Figures & tables

Figure 1: (a) A vertex-labeled graph

G

with five vertices, an arbitrary sequence

v_{1},v_{2},v_{3},v_{4},v_{5}

of vertices and labels from

\Sigma=\{1,2,3,4,5\}

. (b) The representation of

G

with the label matrix

L

and the adjacency matrix

A

. (c) A graph

G^{1}

obtained from

G

after deleting the edge incident to

v_{2}

and

v_{3}

and then deleting the vertex

v_{3}

. (d) A graph

G^{2}

obtained from

G

after substituting the label of the vertices

v_{3}

and

v_{5}

. (e) A graph

G^{3}

obtained from

G

after inserting a vertex

v_{6}

with label

5

and then an edge connecting the vertices

v_{4}

and

v_{6}

. (f), (g) and (h) are the matrix representations of the graphs obtained in (c), (d) and (e), respectively. Observe that

\text{GED}(G,G^{1})=\text{GED}(G,G^{2})=\text{GED}(G,G^{3})=2

Figure 2: An illustration of simulation of GS d -generative ReLU network for a graph $G$ , $d=3$ and the input layer $x=5,3,3,5,2,3$ . The graph $G$ is represented by a column vector of labels $L$ and an adjacency matrix $A$ , while the output graph $G^{\prime}$ is generated as a column vector of labels $L^{\prime}$ and an adjacency matrix $A^{\prime}$ .

$x_{j}$	Indicates vertex index when $j\leq d$ , and labels to be substituted otherwise (when $j\geq d+1$ )
$e_{j}$	Eliminates repeated entries from $x$ for $j\in\{1,\dots,d\}$ by setting duplicate values to $0$ . In this example, $e_{3}=0$ , while $e_{1}=x_{1}$ and $e_{2}=x_{2}$ .
$f_{i}$	Stores the labels that will not be changed, i.e., $f_{i}=0$ if index $i$ appears in $e$ , otherwise $f_{i}=\ell_{i}$ . In this case, $F=(f_{i})=[3,5,0,2,0]$ , as shown in Fig. 2 , where $f_{1}=3$ (resp., $f_{3}=0$ ) since index $1$ (resp., 3) does not appear (resp., appears) in $x$ .
$g_{i}$	Stores the labels that will be substituted, i.e., $g_{i}=0$ if index $i$ does not appear in $e$ , otherwise $g_{i}=x_{j+d}$ when $e_{j}=i$ . Therefore, $G=(g_{i})=[0,0,2,0,5]$ as shown in Fig. 2 , where $g_{1}=0$ (resp., $g_{3}=2$ ) since index $1$ (resp., 3) does not appear in $e$ (resp., appears at $e_{2}$ and $x_{2+3}=2$ ).
${\ell}^{\prime}_{i}$	The entries of the resultant label column of the output graph $G^{\prime}$ by adding $F$ and $G$ . In this case, $L^{\prime}=({\ell}^{\prime}_{i})=[3,5,2,2,5]$ .

Table 3

Figure 3: An illustration of the simulation of GD d -generative ReLU for a given graph $G$ with an arbitrary vertex sequence $v_{1},\ldots,v_{5}$ , $d=3$ and the input layer $x=5,3,3,5,2,3$ . $U^{\prime}$ and $W$ are obtained from $U$ and $T^{\prime}$ , resp., by row deletion. Graph $G$ is represented by the label matrix $L$ and the adjacency matrix $A$ , whereas the output graph $G^{\prime}$ is represented by the label matrix $L^{\prime}$ and the adjacency matrix $A^{\prime}$ . The entries in red in $T^{\prime}$ indicate the deleted edges, whereas the red ellipses indicate the rows and columns to be deleted to obtain the desired graph $G^{\prime}$ .

$x_{j}$	Identifies the vertices and edges to be deleted. In this case $x=5,3,3,5,2,3$ . The values $x_{2}=3$ and $x_{5}=2$ refer to the deletion of the edge between $v_{3}$ and $v_{2}$ , while $x_{1}=x_{4}=5$ and $x_{3}=x_{6}=3$ refer to the deletion of vertices $v_{5}$ and $v_{3}$ . The row and column corresponding to $x_{3}=x_{6}=3$ are deleted because $v_{3}$ becomes an isolated vertex after edge deletion as shown in the matrix $T^{\prime}$ in Fig. 3 . However, the case $x_{1}=x_{4}=5$ is ignored because $v_{5}$ is not an isolated vertex.
$t_{i{k}}$	A binary variable that equals $1$ when the corresponding entry $v_{ik}$ in the padded adjacency matrix $V$ is set to $0$ , indicating that the edge between vertices $v_{i}$ and $v_{k}$ should be removed. In this case $t_{3,2}=t_{2,3}=1$ . All other values are $0$ .
$t^{\prime}_{i{k}}$	The entries of the modified $V$ after setting indicated entries to zero. In this example, $t^{\prime}_{3,2}=t^{\prime}_{2,3}=0$ . All other values of $t^{\prime}_{i{k}}$ are same as $v_{i{k}}$ . The matrix $T^{\prime}=(t^{\prime}_{i{k}})$ is shown in Fig. 3 , where $t^{\prime}_{3,2}=t^{\prime}_{2,3}=0$ are in red color.
$t^{\prime\prime}_{i}$	After edge deletion, this variable checks if $v_{i}$ is an isolated vertex using $T^{\prime}=(t^{\prime}_{i{k}})$ . More precisely, the $i$ -th vertex is isolated if and only if $t^{\prime\prime}_{i}=0$ . In this example, $t^{\prime\prime}_{1}=t^{\prime\prime}_{4}=2$ , $t^{\prime\prime}_{2}=t^{\prime\prime}_{5}=3$ , $t^{\prime\prime}_{3}=0$ , which shows that only the third vertex is isolated in the matrix $T^{\prime}$ .
$x^{\prime}_{j}$	Sets the input $x_{j}=0$ if it corresponds to a non-isolated vertex. Specifically, when $t^{\prime\prime}_{x_{j}}>0$ , the vertex cannot be deleted, so $x^{\prime}_{j}=0$ . Hence, for this case $x^{\prime}_{1}=0$ .
$e_{ik}$	A binary variable that takes the value $e_{ik}=1$ when the $i$ -th row is retained to keep the vertex $v_{i}$ , otherwise $e_{ik}=0$ for all $k\in\{1,\dots,n+2\}$ . In this example $e_{3k}=0$ for $k\in\{1,\dots,n+2\}$ . All other entries $e_{ik}=1$ for $i\neq 3$ .
$e^{\prime}_{i}$	A binary variable that takes the value $e^{\prime}_{i}=1$ when the $i$ -th label is retained to keep the vertex $v_{i}$ , otherwise $e^{\prime}_{i}=0$ . For instance, $e^{\prime}_{3}=0$ because only the label corresponding to the vertex $v_{3}$ in matrix $U$ needs to be deleted. All other values are $1$ .

Table 5

Sr. no.	Invalid Inputs	Refinements
(i)	$x_{j}\neq x_{j+d},x_{j}=x_{k},x_{j+d}=x_{k+d}$ , $k<j$	$x_{j}:=0$
(ii)	$x_{j}\neq x_{j+d},x_{j}>n+d^{\prime}$	$x_{j}:=0$
(iii)	$x_{j}\neq x_{j+d},x_{j+d}>n+d^{\prime}$	$x_{j+d}:=0$

Table 3: Invalid inputs and their refinements.

Figure 4: A demonstration of obtaining $G^{\prime}$ from $G$ using a GI d -generative ReLU, where $d=3$ and the input layer $x=4,3,7,6,3,2,5,1,2$ .

$x_{j}$	Indicates vertex indices (resp., label of new vertices) when $1\leq j\leq 2d$ (resp., $2d+1\leq j\leq 3d$ ).
$e_{jk}$	An indicator that takes value $1$ whenever there exists an index $k<j$ with $x_{j}=x_{k}$ and $x_{j+d}=x_{k+d}$ , provided $x_{j}\neq x_{j+d}$ for $j,k\in\{1,\dots,d\}$ to avoid invalid inputs. In this example, $e_{jk}=0$ for every $j,k$ .
$e^{\prime}_{j}$	Nullifies the repeated input $x_{j}$ if for any $k<j$ , $e_{jk}=1$ . In this case $e^{\prime}_{j}=x_{j}$ for $j\in\{1,\dots,d\}$ .
$f_{j}$	A binary variable to identify if $e^{\prime}_{j}$ is greater than $n+d^{\prime}$ . In this example, $f_{3}=1$ whereas $f_{1}=f_{2}=0$ .
$x^{1}_{j}$	Sets $e^{\prime}_{j}$ to $0$ if it is greater than $n+d^{\prime}$ . That is, $x^{1}_{j}=0$ if $f_{j}=1$ and $x^{1}_{j}=e^{\prime}_{j}$ otherwise.
$f^{\prime}_{j}$	Identifies whether $x_{j+d}$ , if it is greater than $n+d^{\prime}$ . Here, $f^{\prime}_{j}=0$ for all $j\in\{1,\dots,d\}$ .
$x^{2}_{j}$	Nullifies $x_{j+d}$ if it is greater than $n+d^{\prime}$ . That is, $x^{2}_{j}=0$ if $f^{\prime}_{j}=1$ and $x^{2}_{j}=x_{j+d}$ otherwise. In this case $x^{2}_{j}=x_{j+d}$ for all $j\in\{1,\dots,d\}$ .

Table 8

For positions $x_{j}$ with $1\leq j\leq d~$ and $5d+1\leq j\leq 7d$	For positions $x_{j}$ with $2d+1\leq j\leq 4d$	For values $x_{j}$ with $d+1\leq j\leq 2d$ and $4d+1\leq j\leq 5d$
$~(-1/5,0]\rightarrow 0$	$(-1/7,0]\rightarrow 0$	$[0,1/10]\rightarrow 1$
$~~~(0,1/5]\rightarrow 1$	$(0,1/7]\rightarrow 1$	$(1/10,2/10]\rightarrow 2$
$~~(1/5,2/5]\rightarrow 2~~$	$(1/7,2/7]\rightarrow 2$	$(2/10,3/10]\rightarrow 3$
$~~(2/5,3/5]\rightarrow 3~~$	$(2/7,3/7]\rightarrow 3$	$(3/10,4/10]\rightarrow 4$
$~~(3/5,4/5]\rightarrow 4~~$	$(3/7,4/7]\rightarrow 4$	$(4/10,5/10]\rightarrow 5$
$~~(4/5,5/5]\rightarrow 5~~$	$(4/7,5/7]\rightarrow 5$	$(5/10,6/10]\rightarrow 6$

Table 5: Conversion table from real numbers to integers.

${p}^{j}_{i}$	This variable specifies the interval for the position $x_{j}$ , where $j\in\{1,\ldots,d,5d+1,\ldots,7d\}$ . ${p}^{j}_{i}=1$ means that $x_{j}$ lies in the $i$ -th interval, i.e., the interval $((i-1)/n,i/n]$ . In this case ${p}^{1}_{3}={p}^{2}_{0}={p}^{3}_{3}$ $={p}^{16}_{2}={p}^{17}_{2}={p}^{18}_{5}={p}^{19}_{4}={p}^{20}_{4}={p}^{21}_{5}=1$ . All other values are zero.
${q}^{j}_{i}$	Specifies the interval for each label $x_{j}$ , where $j\in\{2d+1,\ldots,4d\}$ . ${q}^{j}_{i}=1$ means that the $j$ -th input lies in the ${i}$ -th interval, i.e., $x_{j}$ lies in $[(i-1)/(n+d-1),i/(n+d-1)]$ . In this case, ${q}^{7}_{1}={q}^{8}_{1}={q}^{9}_{7}={q}^{10}_{4}={q}^{11}_{4}={q}^{12}_{0}=1$ , and all other values are zero.
${r}^{j}_{i}$	It specifies the interval for each label $x_{j}$ , where $j\in\{d+1,\ldots,2d,4d+1,\ldots,5d\}$ . ${r}^{j}_{i}=1$ means that the $j$ -th input lies in the ${i}$ -th interval, i.e., $((i-1)/m,i/m]$ . In this case, ${r}^{4}_{1}={r}^{5}_{4}={r}^{6}_{2}={r}^{13}_{6}={r}^{14}_{9}={r}^{15}_{1}=1$ , and all other values are zero.
$p^{\prime}_{j}$	This variable assigns each position $x_{j}$ an integer $i$ if $x_{j}$ belongs to the $i$ -th interval, i.e., if ${p}^{j}_{i}=1$ then ${p^{\prime}}_{j}=i$ . Here, $p^{\prime}_{1}=3$ , $p^{\prime}_{2}=0$ , $p^{\prime}_{3}=3$ , $p^{\prime}_{16}=2$ , $p^{\prime}_{17}=2$ , $p^{\prime}_{18}=5$ , $p^{\prime}_{19}=4$ , $p^{\prime}_{20}=4$ , $p^{\prime}_{21}=5$ .
$q^{\prime}_{j}$	It assigns each position $x_{j}$ an integer $i$ if $x_{j}$ belongs to the $i$ -th interval, i.e., if $q_{i}^{j}=1$ then $q^{\prime}_{j}=i$ . In this example, $q^{\prime}_{7}=1$ , $q^{\prime}_{8}=1$ , $q^{\prime}_{9}=7$ , $q^{\prime}_{10}=4$ , $q^{\prime}_{11}=4$ , $q^{\prime}_{12}=0$ .
$r^{\prime}_{j}$	This variable assigns each label $x_{j}$ an integer $i$ if $x_{j}$ belongs to the $i$ -th interval, i.e., if $r_{i}^{j}=1$ then $r^{\prime}_{j}=i$ . In this example, $r^{\prime}_{4}=1$ , $r^{\prime}_{5}=4$ , $r^{\prime}_{6}=2$ , $r^{\prime}_{13}=6$ , $r^{\prime}_{14}=9$ , $r^{\prime}_{15}=1$ .
$x^{\prime}_{j}$	It combines the conversions of all parts of the input. Therefore, $x^{\prime}=[3,0,3,1,4,2,1,1,7,4,4,0,6,9,1,2,2,5,4,4,5]$ .

Table 10

$d\backslash n$	100	200	300	400	500	600	700	800	900	1000	1100	1200	1300	1400
10	6	19	42	74	123	173	245	337	511	697	816	949	1090	1250
20	14	42	87	146	239	333	444	633	946	1288
30	27	73	141	229	376	527	668	953
40	46	112	204	328	528	757	916	1298
50	73	162	283	448	705	1013	1199	1739
60	109	223	373	574	902	1258

Table 7: Computation time (sec.) for different values of

n

and

d

to generate desired graphs with the proposed network GE d .

Figure 5: Log-log plot between

n

and computation time for different edit distance

d

Figure 6: Plots of the number of edges $|E|$ (blue) and the graph edit distances (Dist. in orange) of the graphs with $n$ vertices generated by the proposed network, GraphRNN [ 41 ] and GraphGDP [ 44 ] for different pairs of $n$ and $d$ .

$n$	$\|E\|$	$d$	Proposed GE d			GraphRNN [ 41 ]			GraphGDP [ 44 ]
$n$	$\|E\|$	$d$	$N_{\|E\|}$	$N_{n}$	$N_{d}$	$N_{\|E\|}$	$N_{n}$	$N_{d}$	$N_{\|E\|}$	$N_{n}$	$N_{d}$
10	9	5	500	500	500	441	240	0	498	500	0
20	20	10	500	500	500	500	499	0	498	500	0
30	130	15	500	500	500	500	499	0	369	500	0
40	250	20	500	500	500	270	487	0	491	500	0
50	918	25	500	500	500	0	483	0	394	500	0

Table 8: Comparison of the proposed network GE d with GraphRNN [ 41 ] and GraphGDP [ 44 ] models to generate valid graphs with the desired edit distance.

Explore similar work

Jun 2, 2026

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

Generating realistic and diverse graphs is a key problem in machine learning, with applications in molecular discovery, circuit design, cybersecurity, and beyond. However, current graph generative models remain limited by scalability and novelty. Diffusion-based methods often require costly full-adjacency operations and long denoising chains, while many autoregressive and hybrid models have at least quadratic complexity. In addition, these models often imitate training graphs rather than generalize beyond them. We propose a lightweight autoregressive framework to address these issues. It uses a structure-guided topological ordering to serialize graphs into regular edge sequences, enabling near log-linear generation, and a two-phase training strategy that combines exploration-oriented augmentation with iterative refinement to reduce overfitting and promote controlled novelty. Experiments on molecular and non-molecular benchmarks show that our approach improves novelty while preserving high validity and uniqueness. The framework also supports both LSTM and Mamba-style causal sequence backbones, with large-memory accelerators enabling longer graph-sequence experiments beyond typical GPU limits.

Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha +1

Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA

Graph Generation Generative Modeling Autoregressive Generation

Ask PDF

Aug 19, 2026

GraphK: Variable-Size Graph Generation with Efficient Edge Construction

Graph generation models have advanced significantly with deep learning, yet they remain limited in scalability, flexibility, and ability to model underlying structures. We present GraphK, a novel encoder-sampler-decoder framework for graph generation that overcomes these challenges through structural flexibility and computational efficiency. Unlike autoregressive approaches constrained by vocabulary size (i.e. number of nodes in graph generation), GraphK allows for both upscaling (generating graphs with more nodes than the input) and downscaling, providing a flexible control over output graph size. By learning permutation-invariant latent representations and sampling new node embeddings via maximum likelihood estimation, GraphK generalizes across graph sizes and structures. For edge generation, we employ edge prediction with a KDTree-based top-k neighbor search in the latent space, reducing computational cost. Based on the manifold smoothness assumption, our method effectively captures graph properties. Experiments on synthetic and real-world datasets show that GraphK outperforms existing methods, accurately learns graph structures, and generates synthetic graphs without explicit definitions.

Resul Tugay, Eren Oluğ, Elif Ak +1

Department of Artificial Intelligence and Data Engineering Ataturk University, Turkey · Department of Artificial Intelligence and Data Engineering ITU AI Research and Application Center Istanbul Technical University, Turkey · Faculty of Engineering and Applied Science Memorial University, Canada

Graph Generation Generative Modeling Graph Representation Learning

Ask PDF

Mar 9, 2026

Local Message-Passing for Discrete Graph Generation

Discrete graph generation has emerged as a powerful paradigm for modeling graph-structured data, yet state of the art models often rely on Graph Transformers or higher order architectures. We revisit this design assumption by introducing GenGNN, a modular message passing backbone for graph generation. GenGNN enables powerful generation by persisting edge fields through latent refinement of coupled node edge graph states, all without requiring global attention. Diffusion models integrating GenGNN achieve over 90 percent validity on standard benchmark datasets, performing within margins of Graph Transformer backbones and achieving up to 2x or even 5x faster inference. Systematic ablations isolate how GenGNN is resilient to oversmoothing during generative denoising, indicating each GenGNN component is necessary for downstream generation quality. Finally, representation-space analysis suggests GenGNN learns functionally similar representations to more theoretically-expressive architectures; even at deeper layers. As such, GenGNN uplifts local message-passing to challenge prevailing assumptions that performant discrete graph generation requires global attention or higher-order representations. Source Code Available Here

Jay Revolinsky, Harry Shomer, Jiliang Tang

Michigan State University East Lansing, Michigan, USA · University of Texas - Arlington Arlington, Texas, USA

Graph Neural Networks Graph Generation Message Passing Neural Networks

Ask PDF