cs.LGNov 3, 2026

Constraint-Preserving Flow Matching for Spectral Graph Generation

Authors: Anita Yang, Ken-ichi Kawarabayashi, Yohan Jung

Abstract

Spectral graph generation models graphs through the eigenvalues and eigenvectors of their Laplacians, providing a compact and continuous alternative to direct graph construction. However, these eigensystems must retain the structural properties of graph Laplacians. Existing approaches preserve eigenvector orthonormality but do not enforce the Laplacian nullspace constraint, potentially producing eigensystems inconsistent with Laplacian structure. To address this, we introduce Laplacian-Constrained Stiefel Flow Matching (LaSFM), which preserves the nullspace condition alongside eigenvector orthonormality and positive eigenvalues during generation. We characterize the underlying constrained Stiefel manifold and formulate flow matching on it. We further extend LaSFM to property-guided generation, steering samples toward desired graph properties while maintaining these constraints. Experiments demonstrate improved performance on both spectral and graph-level metrics, along with better alignment with target properties.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jul 8, 2026

Stability of Flow Models for Graph Signals

Generating signals on graphs requires permutation-equivariant models that exhibit stability with respect to relative structural perturbations. While favorable stability properties of Graph Neural Networks (GNNs) have been well documented, it is unclear how structural errors propagate through the dynamics of continuous generative flow models that are gaining traction for graph signal generation. In this paper, we analyze continuous normalized flow models parameterized by GNNs and show that permutation equivariance is preserved for both the resulting continuous-time ordinary differential equations and their discrete numerical approximations used as graph signal samplers. Our primary contribution is to derive explicit stability bounds on the generated probability distributions, which quantify how relative graph perturbations affect the final sampled signals. Motivated by these theoretical bounds, we introduce a stability-promoting regularized flow matching strategy that actively penalizes the spatial Lipschitz constant of the vector field during model training. Experiments using synthetic smooth signals on stochastic block model graphs and real-world fMRI signals on brain connectomes demonstrate that this bound-oriented approach yields generative models that are more robust to structural noise, without sacrificing output quality.
Mar 31, 2026

Hierarchical Discrete Flow Matching for Graph Generation

Denoising-based models, including diffusion and flow matching, have led to substantial advances in graph generation. Despite this progress, such models remain constrained by two fundamental limitations: a computational cost that scales quadratically with the number of nodes and a large number of function evaluations required during generation. In this work, we introduce a novel hierarchical generative framework that reduces the number of node pairs that must be evaluated and adopts discrete flow matching to significantly decrease the number of denoising iterations. We empirically demonstrate that our approach more effectively captures graph distributions while substantially reducing generation time.
Mar 30, 2026

Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra

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.