GraphK: Variable-Size Graph Generation with Efficient Edge Construction

Resul Tugay; Eren Oluğ; Elif Ak; Sule Gunduz Oguducu

cs.LGAug 19, 2026

GraphK: Variable-Size Graph Generation with Efficient Edge Construction

Authors: Resul Tugay, Eren Oluğ, Elif Ak, Sule Gunduz Oguducu

Organizations: 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

Abstract

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.

Figures & tables

Method	Core Approach	Focus	Node Order Invariance	Computational Complexity (per graph)	Up- scaling
ER Erdos and Renyi (1959)	Random graph generation based on edge probability	General	No	Low. $\Rightarrow$ Generates edges by one Bernoulli draw per pair	No
BA Barabasi and Albert (1999)	Preferential attachment	Scale-free networks	No	Low. $\Rightarrow$ Adds one node with $\mathcal{O}(1)$ preferential links	No
SBM Holland et al. (1983)	Community structure with probabilistic edge connections	Community	No	Low. $\Rightarrow$ Samples block‐wise probabilities.	No
GraphRNN You et al. (2018)	Autoregressive node and edge sequence generation	General	No	High. $\Rightarrow$ Sequential edge writing: worst-case $\mathcal{O}(N^{2})$ decisions; BFS ordering shortens average run-time but still quadratic on dense graphs. Up to $\approx 80$ nodes.	No
GRAN Liao et al. (2020)	Recurrent attention over graph structure	General	Partial	Low. $\Rightarrow$ Adds $b-node$ blocks; $\approx$ $\left\lceil N/b\right\rceil$ GNN passes. With small constant $b$ the cost grows roughly $\mathcal{O}(N)$ . Shown to $\approx 5000$ nodes.	No
BiGG Dai et al. (2020)	Autoregressive generation via binary indexing trees	General	No	Low. $\Rightarrow$ $\mathcal{O}((N+E)\log N)$ using recursive tree factorization. Scales to $\mathcal{O}(10^{5})$ nodes.	No

Table 1: Overview of related works and their limitations.

Figure 1: Overview of the GraphK architecture.

	2-Block Community			Protein			CiteSeer
	Spectral	Orbit	Motif	Spectral	Orbit	Motif	Spectral	Orbit	Motif
ER	0.051	1.117	1.131	0.102	1.684	1.450	0.056	1.993	1.951
BA	0.044	1.214	1.420	0.100	1.139	1.284	0.048	1.127	1.383
GraphVAE	0.106	1.416	1.402	0.082	1.266	1.266	0.245	1.416	1.422
GraphRNN	0.061	1.151	1.116	0.301	0.752	0.804		OOM
NetGAN	0.021	0.298	0.398	0.075	1.112	1.172	0.024	1.351	1.184

Table 2: Comparison of graph generation quality across models on synthetic and real-world datasets. MMD scores for spectral, orbit, and motif statistics (lower is better).

Panel of Figure 2 — Figure 2: Visual comparison of graphs generated by different models on synthetic community and real-world protein datasets.

Panel of Figure 3 — Figure 3: Input graph shown in (a) has $10,000$ nodes and approximately $21,000$ edges. One of the generated graphs (b) has $15,000$ nodes and approximately $32,000$ edges. The parameter $k$ is selected as $12$ . Subfigure (c) shows the decoding (inference) time in seconds with respect to the graph size.

Panel of Figure 4 — Figure 4: Directed graph generation with HOPE encoder. Darker nodes have higher in-degree.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X})$	Input graph with node set $\mathcal{V}$ and edge set $\mathcal{E}$ and features of nodes $\mathcal{X}$
$n=\|\mathcal{V}\|$	Number of nodes in the graph
$d$	Dimensionality of the latent space
$z_{v}\in\mathbb{R}^{d}$	Latent representation of node $v\in\mathcal{V}$
$Z=\{z_{v}\mid v\in\mathcal{V}\}$	Set of latent embeddings for all nodes
$\\|z_{v}-z_{u}\\|_{2}$	Euclidean distance between node embeddings $z_{v}$ and $z_{u}$

Appendix

Table 3: Summary of Notations

Panel of Figure 5 — Figure 5: GraphK vs GRAN in protein dataset. Group 1: (100-200 nodes), Group 2: (200-300 nodes), Group 3: (300-400 nodes), Group 4: (400-500 nodes)

Panel of Figure 6 — Figure 6: Figure (a) shows a graph with three communities generated using the Stochastic Block Model. After upscaling, we obtain Figure (b). Then, we downscale it back, resulting in Figure (c).

Panel of Figure 8 — Figure 8: Augmentation effect on node classification task (Dashed line is the accuracy without augmentation.)

Panel of Figure 9 — Figure 9: Comparison of two histograms

Figure 10: Comparison of spectral scores on the Protein dataset, highlighting the impact of permutation invariance (a), and decoder time calculation to show scale (b)

Explore similar work

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models
Jun 2, 2026Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha +1Graph Generation Generative Modeling
Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA
FLAGG: Flexible Autoregressive Graph Generation
Jun 3, 2026Samuel Cognolato, Alessandro Sperduti, Luciano SerafiniGraph Generation Autoregressive Generation
Department of Mathematics, University of Padova, Padova, VE, 35121 Italy · Fondazione Bruno Kessler (FBK), Trento, TN, 38123 Italy · Department of Information Engineering and Computer Science, University of Trento, Trento, TN, 38123 Italy
DiPhon: Diffusion on Graphons for Scalable Graph Generation
Jul 8, 2026Sergio Rozada, Yiming Qin, Manuel Madeira +2Graph Generation Graph Diffusion
King Juan Carlos University · EPFL, Lausanne, Switzerland · University of Pennsylvania

Jun 2, 2026J/K move · Enter open · S save

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha, Edoardo Serra

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

Graph Generation Generative Modeling Autoregressive Generation

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

FLAGG: Flexible Autoregressive Graph Generation

DiPhon: Diffusion on Graphons for Scalable Graph Generation