Generating Large Semi-Synthetic Graphs of Any Size

Rodrigo Tuna, Carlos Soares · 2025

Read Generating Large Semi-Synthetic Graphs of Any Size by Rodrigo Tuna, Carlos Soares (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-02166.txt.

Introduction

Rodrigo Tuna and Carlos Soares give a way to build large fake networks at any size from one real network, in a 2025 paper. Network study needs test graphs that share traits with real ones. Past deep tools tie graphs to fixed node names, so they cannot grow past the source size.

Their method learns how nodes sit and cluster, then draws fresh graphs of a picked size with no new training. Tests match past tools on standard scores and beat them on cluster scores. Traits stay steady as size grows, which shows the method scales well for later work.

Catalog record

CREATORRodrigo Tuna, Carlos Soares
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-02166

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generating Large Semi-Synthetic Graphs of Any Size Rodrigo Tuna, Carlos Soares Abstract Graph generation is an important area in network science. Traditional approaches focus on replicating specific properties of real-world graphs, such as small diameters or power-law degree distributions. Recent advancements in deep learning, particularly with Graph Neural Networks, have enabled data-driven methods to learn and generate graphs without relying on predefined structural properties. Despite these advances, current models are limited by their reliance on node IDs, which restricts their ability to generate graphs larger than the input graph and ignores node attributes. To address these challenges, we propose Latent Graph Sampling Generation (LGSG), a novel framework that leverages diffusion models and node embeddings to generate graphs of varying sizes without retraining. The framework eliminates the dependency on node IDs and captures the distribution of node embeddings and subgraph structures, enabling scalable and flexible graph generation. Experimental results show that LGSG performs on par with baseline models for standard metrics while outperforming them in overlooked ones, such as the tendency of nodes to form clusters. Additionally, it maintains consistent structural characteristics across graphs of different sizes, demonstrating robustness and scalability. 1 Introduction Graph Generation has been a well-studied topic in the field of Network Science Barabási and Pósfai 2016 . Classic generative algorithms focused on generating synthetic graphs that exhibited some properties of real-world graphs that had been previously observed, such as small diameter or power-law degree distribution Chakrabarti et al. 2004 ; Watts and Strogatz 1998 . The advances in deep learning, specifically in Graph Neural Networks Wu et al. 2022 , extended deep learning to non-euclidean data. This lead to new graph generation approaches that resort to data-driven algorithms that do not focus on graph properties known a priori but rather learn to capture the semantic meaning of a graph or a dataset of graphs to generate new ones. These methods have been applied to code generation Brockschmidt et al. 2019 , molecule generation Cao and Kipf 2022 , and to extract semantic graphs from text Chen et al. 2018 . However, current deep learning methods face limitations in generating graphs larger than the input graph. This constraint arises because models that focus on generating one large graph rely on node IDs You et al. 2018 ; Bojchevski et al. 2018 ; Limnios et al. 2023 to identify and generate nodes within a given input graph. Consequently, it is not feasible to produce graphs with more nodes than the input graph, as each node must be assigned a unique ID, and duplicate IDs are not permissible. Notably, these node IDs do not encode any meaningful information about the graph’s structure or the relationships between nodes; they merely impose a fixed node ordering during the generation process. Additionally, these approaches often disregard potential node attributes, focusing exclusively on the graph’s structural properties, which further limits their expressive capacity. We introduce a novel framework, Latent Graph Sampling Generation (LGSG), that leverages the strengths of diffusion models; which are well-established in image generation Dhariwal and Nichol 2021 and increasingly effective in generating graph-structured data Vignac et al. 2023 . Unlike traditional approaches, our framework enables the generation of graphs with more nodes than the input graph, overcoming the limitations of fixed-size output graphs. Moreover, the presented framework is able to generate graphs with different sizes without the need for retraining, offering unprecedented flexibility in adapting to diverse size constraints in graph generation. By learning node embeddings that encode structural and relational information, the model captures the distribution of embeddings and subgraph structures, enabling scalable and cohesive graph generation. We evaluate our approach against classic graph generative models by comparing graph statistics between input and generated graphs, demonstrating its ability to produce diverse and structurally meaningful graphs while supporting size variability. Results indicate that the presented framework is on par with the baseline models when comparing metrics that these algorithms are designed to capture. The framework also outperforms the baselines in metrics the other algorithms do not encompass in the generation, e.g. Cluster Coefficient. In addition, we provide a study on the scalability of the algorithm by using the same model, trained on an input graph, to generate graphs of different sizes. Concluding that, although the graph metrics of graphs reproduced by some baselines change less with respect to size, our framework maintains consistency and generates graphs with realistic structural characteristics regardless of scale. This paper starts by documenting graph generation. We then present a recent diffusion graph generative model, SaGess Limnios et al. 2023 , that focuses on generating large graphs. Then, in Section 3 , we characterize the proposed framework. Finally, the experimental setup is explained in Section 4 , and the results are discussed in Section 5 . The code used for this work is available at https://github.com/rodrigotuna/LGSG 2 Background In this section, we then present the main concepts related to our work. We start by briefly detailing the problem of graph generation and then present the graph diffusion model SaGess Limnios et al. 2023 , on which we base our architecture. 2.1 Graph Generation A graph \mathcal{G}(\mathcal{V},\mathcal{E}) , with a set of N=|\mathcal{V}| nodes \mathcal{V} and a set of edges \mathcal{E} , where (u,v)\in\mathcal{E} indicates an edge between nodes u,v\in\mathcal{V} . In the context of machine learning, as graph datasets include features from each node, a graph is represented as G(X,E) with adjacency matrix E\in\mathbb{R}^{N\times N} , where E_{i,j}=1 if there is an edge between nodes v_{i} and v_{j} and is 0 otherwise; and node features X\in\mathbb{R}^{N\times d} where x_{i} is a vector of d features \forall 0\leq i\leq N . The problem of graph generation is formally defined as, given a dataset of graphs D\{\mathcal{G}_{i}\} , possibly one, originated from an underlying data distribution p , we want to generate another dataset of graphs D\{\mathcal{G}^{\prime}_{i}\} such that are sampled from the distribution p Cohen-Karlik et al. 2024 . Graph generation is the process of creating new graph-structured data that simulates the structure and properties of real-world graphs. The topic was first studied in the mathematical field of Random Graphs Bollobás 2001 , intersecting probability theory and graph theory. It is also a fundamental topic of Network Science Barabási and Pósfai 2016 ; Wu et al. 2022 . This task is essential for applications that require artificial yet realistic network representations, such as social networks Barabási and Albert 1999 , molecular structures Flam-Shepherd et al. 2021 , knowledge graphs extraction from text Chen et al. 2018 , or code generation Brockschmidt et al. 2019 . The existing solutions for this problem sample from probabilistic models that capture the statistical properties of existing graphs, allowing the generation of synthetic or semi-synthetic graphs with similar characteristics. Classical methods for graph generation focus on creating probabilistic models that capture fundamental properties observed in real-world networks, such as degree distribution, clustering coefficients, and average path lengths. Notable examples include the Erdős–Rényi model Erdos and Renyi 1960 , which assumes edges are formed independently with a fixed probability, and the Barabási–Albert model Barabási and Albert 1999 , which generates scale-free networks using a preferential attachment mechanism. These approaches often fall short of capturing more complex patterns, such as hierarchical structures or overlapping communities,

Read the complete text