Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra

Hendrik Richter; Frank Neumann

cs.NEMar 30, 2026

Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra

Authors: Hendrik Richter, Frank Neumann

Organizations: HTWK Leipzig University of Applied Sciences, Faculty of Engineering, D–04251 Leipzig, Germany · Optimisation and Logistics, Adelaide University, Adelaide, SA 5005, Australia

Abstract

Graphs with diverse structural characteristics play a central role in modelling and optimization tasks. The ability to generate different types of graphs that exhibit shared properties is likewise essential for algorithm selection and configuration. However, constructing graphs that preserve high-level properties across a broad range of graph classes remains a challenging problem. We present a novel evolutionary approach to evolve graphs based on the Laplacian graph spectra descriptor. This descriptor can be used as part of a fitness function to evaluate graphs according to their desired high-level properties. Our evolutionary algorithm evolves graphs towards this descriptor in order to obtain graphs having properties that are consistent with it but are different from each other in terms of non-spectral graph metrics, such as path length, clustering coefficient and betweenness centrality. Our experimental results show that our approach is successful for different classes of graphs and a wide range of Laplacian graph spectra.

Figures & tables

Panel of Figure 1 — Figure 1: Examples of target graphs and target densities for graph size $n=12$ . (a) Star graph $\mathcal{S}_{11}$ . (b) Circulant graph $\mathcal{C}_{12}^{1234}$ . (c) Circulant graph $\mathcal{C}_{12}^{123}$ . (d) Spectral densities of $\varphi_{\mathcal{T}}(x)$ , see Eq. ( 1 ), of the target graphs (a)-(c).

Figure 2: Evolution of the spectral density $\varphi_{\mathcal{G}}(x)$ over generations $\kappa$ for $n=24$ , $12$ -regular initial graphs and the target graph $\mathcal{C}_{24}^{1,2,\ldots,6}$ .

Design parameter	Symbol	Value(s)
Population size	$\ell$	40
Generations	$K$	1000
Tournament size	$s_{t}$	2
Mutation rate	$\alpha$	0.75
Mutation strength	$\beta$	4
Connectivity threshold	$\lambda_{2}^{t}$	0.001

Table 1: Design parameter of the algorithm.

Panel of Figure 3 — Figure 3: Results for target graphs of size $n=24$ . Boxplots for 30 runs and 1000 generations showing the final best fitness measured by the distance $d$ , see Eq. ( 2 ), for eight initial graph populations and three crossover implementations. (a) Star graph $\mathcal{S}_{23}$ (b) Circulant graph $\mathcal{C}_{24}^{1,2,\ldots,8}$ . (c) Circulant graph $\mathcal{C}_{24}^{1,2,\ldots,6}$ .

Panel of Figure 4 — Figure 4: Results for target graphs of varying size. Boxplots showing the final best fitness measured by the logarithmic distance $\log(d)$ for eight initial graph populations and graph size $n=\{64,128,256,512\}$ . (a) Star graph $\mathcal{S}_{n-1}$ (b) Circulant graph $\mathcal{C}_{n}^{1,2,\ldots,\lfloor n/3\rfloor}$ . (c) Circulant graph $\mathcal{C}_{n}^{1,2,\ldots,\lfloor n/4\rfloor}$ .

Panel of Figure 5 — Figure 5: Scatter plots of final best fitness versus graph metrics for the circulant target graph $\mathcal{C}_{24}^{1,2,\ldots,8}$ . The color code indicates different initial populations. (a) Algebraic connectivity (AC). (b) (Average) path length (PL). (c) (Global) clustering coefficient (CC). (d) (Average) betweenness centrality (BC).

Panel of Figure 6 — Figure 6: Boxplots of the diversity contribution, see Eq. ( 3 ). (a) Star graph $\mathcal{S}_{23}$ (b) Circulant graph $\mathcal{C}_{24}^{1,2,\ldots,8}$ . (c) Circulant graph $\mathcal{C}_{24}^{1,2,\ldots,6}$ .

Graph Generation

Graph generation builds models and algorithms that create graphs with desired structures, properties, or distributions.

See all 66 papers

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs
Oct 22, 2026Daniele Micheletti, Federica Zoe Ricci, Erik B. SudderthGraph Generation Variational Autoencoders
University of California, Irvine · Swarthmore College
Multi-Objective Molecular Generation with Frequency-Controlled Evolutionary Dynamics
Jun 25, 2026Elia Colleoni, Paolo Guida, Didier Barradas-Bautista +1Multi-Objective Evolutionary Optimization Molecular Generation
Clean Energy Research Center (CERP) Physical Science and Engineering (PSE) Division King Abdullah University of Science and Technology Thuwal, Saudi Arabia 23955 · Kaust Visualization Lab (KVL) Core Lab Division King Abdullah University of Science and Technology Thuwal, Saudi Arabia 23955
Improved large-scale graph learning through ridge spectral sparsification
Apr 22, 2026Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric +1Graph Sparsification Spectral Methods
SequeL team, INRIA Lille - Nord Europe, France · LCSL, IIT, Italy · New Jersey Institute of Technology, USA +1

Oct 22, 2026J/K move · Enter open · S save

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth

University of California, Irvine · Swarthmore College

Graph Generation Variational Autoencoders

Open paper AskPDF arXiv

Graphs play a crucial role in many applications, ranging from drug discovery to social network modeling and astronomy. Generative models for graphs have substantially advanced in recent years, but we identify relatively simple scenarios where state-of-the-art models struggle to converge within a standard compute budget, or exhibit prohibitively slow generation times. We propose a generative architecture that achieves quality competitive with state-of-the-art models and is orders of magnitude faster at generation. Our approach is inspired by the Aldous-Hoover theorem, a classic representation theorem that characterizes any probability distribution of graphs that is invariant to permutations of node indices or exchangeable. This theorem establishes that three ingredients suffice: a graph-level latent variable, a set of exchangeable node-specific latent variables, and a so-called graphon function that maps graph- and node-level variables to the probability of an edge between any node pair. Given a training set of graphs, our exchangeable Variational Graph AutoEncoder (xVGAE) learns an approximation to their underlying graphons, as well as graph- and node-level latent variables. We show that our xVGAE encodes latent representations that correlate with graph- and node-level properties, and can (quickly, in one shot) generate new graphs that closely match key training set statistics.

Abstract

Graph Generation

Explore similar work

xVGAE: A Hierarchical Variational Graph Autoencoder for Exchangeable Graphs

Multi-Objective Molecular Generation with Frequency-Controlled Evolutionary Dynamics

Improved large-scale graph learning through ridge spectral sparsification