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

CardsList
  1. Stability of Flow Models for Graph Signals

    Jul 8, 2026Martin Schmidt, Gonzalo MateosGraph Signal ProcessingFlow Matching

  2. Hierarchical Discrete Flow Matching for Graph Generation

    Mar 31, 2026Yoann Boget, Pablo Strasser, Alexandros KalousisGraph GenerationFlow-Based Generative Modeling

  3. Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra

    Mar 30, 2026Hendrik Richter, Frank NeumannGraph GenerationEvolutionary Optimization