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
Figure 1: Spectral generation can produce distorted structure when eigenvector orthonormality, the Laplacian nullspace constraint, and positive nonzero eigenvalues are not preserved. LaSFM enforces these constraints throughout generation.
Figure 2: Overview of LaSFM. Beyond eigenvector orthogonality, LaSFM preserves the Laplacian nullspace constraint and eigenvalue positivity throughout generation.
(VΛt,VUt)←Fθ(t,Ut,Λt)
Algorithm 1 LaSFM Training
Planar
SBM
Community-Small
QM9
Method
Eigenvalue ↓
Wavelet ↓
Eigenvalue ↓
Wavelet ↓
Eigenvalue ↓
Wavelet ↓
Eigenvalue ↓
Wavelet ↓
SPECTRE
3.092
26.87
14.21
1.612
1.051
2.378
2.974
15.39
GGSD
25.21
397.1
3.405
82.64
2.106
30.66
19.35
45.31
SFMG
21.35
14.95
1.811
11.83
2.101
5.695
25.92
23.16
LaSFM (ours)
3.839
4.562
1.814
2.333
1.000
1.023
1.827
1.561
Table 1: MMD2 ratios for eigenvalue and wavelet statistics, measuring agreement between generated and test spectral distributions (lower is better). LaSFM achieves the most consistent performance across datasets.
Planar
SBM
Community-Small
Method
Deg. ↓
Clust. ↓
Orbit ↓
V.U.N ↑
Deg. ↓
Clust. ↓
Orbit ↓
V.U.N ↑
Deg. ↓
Clust. ↓
Orbit ↓
V.U.N ↑
SPECTRE
2.500
2.850
2.400
0.1400
3.000
1.670
1.680
0.1000
5.910
10.87
18.97
0.9900
GGSD
8.500
2.800
2.800
0.1500
2.630
1.660
2.650
0.1000
1.040
2.190
10.98
0.9500
SFMG
127.0
26.30
33.60
0.1800
32.75
2.080
3.440
0.2400
1.790
4.860
2.910
0.9000
LaSFM
2.500
2.730
1.400
0.1800
1.250
1.780
1.880
0.2000
1.037
1.952
9.720
0.9700
Table 2: MMD2 ratios for graph statistics (lower is better) and the joint validity–uniqueness–novelty (VUN) score (higher is better). LaSFM achieves the most consistent performance across datasets.
Figure 3: Property-guided QM9 generation evaluated on reconstructed molecules. LaSFM achieves the lowest target MAE across all properties while maintaining competitive molecular validity.
Figure 4: Ablation of the Laplacian constraints on QM9 generation. LaSFM achieves the lowest reconstruction error and highest validity, showing the importance of all three constraints.
Method
Eorth↓
Enull↓
Eλ↓
GGSD
0.1062
0.0124
0.0003
SFMG
0.0000
0.2493
0.0146
LaSFM
0.0000
0.0000
0.0000
Table 3: Spectral constraint errors under LUMO guidance. LaSFM preserves all three constraints.
Figure 5: Compared with variant without nullspace constraint, LaSFM generates Laplacians that require smaller corrections, thereby producing graphs that are more consistent with the generated Laplacians.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Illustration of exponential and logarithmic maps.
QR←(In−U0U0⊤)Δ,
Appendix
Table 11
Figure 7: Overview of LaSFM architecture.
Hyperparameter
Planar
SBM
Community-small
QM9
Spectral representation
Retained eigenpairs k
16
4
8
8
Spectral Transformer
Hidden dimension
128
128
96
128
Number of layers
4
8
3
4
Attention heads
4
4
4
4
Appendix
Table 4: Hyperparameters used to train LaSFM on each dataset.
Hyperparameter
Planar
Community-small
SBM
Batch size
8
16
16
Learning rate
2×10−4
1×10−3
5×10−5
Hidden dimension
256
512
256
Weight decay
1×10−4
1×10−3
5×10−3
Number of blocks
8
4
4
Appendix
Table 5: Hyperparameters used to train the flow-matching graph predictor for each dataset.
ϵHOMO
ϵLUMO
Δϵ
Method
MAE ↓
Gain ↑
MAE ↓
Gain ↑
MAE ↓
Gain ↑
GGSD
1.3720
12%
0.9835
6.2%
1.9680
2.6%
SFMG
0.1532
85%
0.4065
81%
0.3267
84%
LaSFM
0.0277
97%
0.0885
96%
0.1046
95%
Appendix
Table 6: Property-guided QM9 generation in spectral space. LaSFM achieves lower MAE with greater reduction compared to unguided generation.
ϵHOMO
ϵLUMO
Δϵ
Method
Eorth↓
Enull↓
Eλ↓
Eorth↓
Enull↓
Eλ↓
Eorth↓
Enull↓
Eλ↓
GGSD
0.1080
0.0137
0.0003
0.1080
0.0137
0.0003
0.1080
0.0137
0.0003
guided
↑ 0.1133
↑ 0.0155
0.0003
0.1062
0.0124
0.0003
↑ 0.1082
↑ 0.0138
0.0003
SFMG
0.000
0.2114
0.000
0.000
0.2114
0.000
0.000
0.2114
0.000
guided
0.000
↑ 0.2444
↑ 0.0423
0.000
↑ 0.2493
↑ 0.0146
0.000
↑ 0.2501
0.000
LaSFM
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
Appendix
Table 7: Spectral constraint errors before and after gradient-based guidance on QM9 across molecular property targets (lower is better). LaSFM consistently ensures no error with and without guidance.
Figure 8: Reconstructed QM9 molecules from unguided and property-guided LaSFM. Guidance steers the generated molecules toward the target HOMO, LUMO, and HOMO–LUMO gap values.
ϵHOMO
ϵLUMO
Δϵ
Method
MAE ↓
Gain ↑
MAE ↓
Gain ↑
MAE ↓
Gain ↑
LaSFM
0.0277
97%
0.0885
96%
0.1046
95%
w/o orth.
0.0849
91%
0.2654
87%
0.2486
87%
w/o null.
0.0872
91%
0.2270
89%
0.2675
86%
w/o pos. λ
0.0294
97%
0.1041
95%
0.1511
92%
Appendix
Table 8: Guidance ablation on QM9. Removing any Laplacian constraint degrades performance (higher MAE and lower gain over unguided), especially orthonormality and the null-space constraint.
Figure 9: Ablation errors over generation process for ϵLUMO . Guidance increases constraint violations, although the eigenvalue-positivity error vanishes by t=0.15 .
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.
Martin Schmidt, Gonzalo Mateos
Dept. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA
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.
Yoann Boget, Pablo Strasser, Alexandros Kalousis
Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland
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.
Hendrik Richter, Frank Neumann
HTWK Leipzig University of Applied Sciences, Faculty of Engineering, D–04251 Leipzig, Germany · Optimisation and Logistics, Adelaide University, Adelaide, SA 5005, Australia