Keeping spectral graph generation within mathematical constraints

A graph generator can work indirectly: rather than choosing connections one by one, it can generate eigenvalues and eigenvectors of a matrix describing the graph. In Constraint-Preserving Flow Matching for Spectral Graph Generation, Anita Yang, Ken-ichi Kawarabayashi and Yohan Jung propose a method for keeping this spectral representation within specified mathematical constraints. Their paper was submitted to arXiv on November 3, 2026, as version 1 and is a preprint.

The method, Laplacian-Constrained Stiefel Flow Matching, or LaSFM, targets a mismatch between continuous spectral generation and discrete graph reconstruction. The authors report better distribution matching and more effective steering toward molecular property targets. Their approach does not, however, eliminate the need to reconstruct graphs or enforce every requirement of a graph Laplacian.

What must the generator preserve?

For an undirected graph with nonnegative edge weights, the combinatorial Laplacian is the degree matrix minus the adjacency matrix. It is symmetric, has nonnegative eigenvalues, and has rows that sum to zero. Its off-diagonal entries must also be nonpositive.

Spectral generators often retain only some eigenpairs, producing a compact, low-rank approximation. LaSFM models retained nonzero eigenvalues and their eigenvectors. The authors identify three constraints for this representation: eigenvectors must be mutually orthogonal and have unit length; retained eigenvalues must be positive; and each retained eigenvector must be orthogonal to the all-ones vector. That final condition makes the reconstructed spectral matrix have zero row sums.

According to the paper, earlier spectral methods that preserve eigenvector orthonormality do not explicitly preserve both the constant-vector nullspace condition and positivity of nonzero eigenvalues. Violating these properties can mean that converting a generated representation into a graph changes the spectral structure it was intended to encode.

Constraining the flow

Flow matching trains a model to move samples from a simple starting distribution toward the data distribution through a learned velocity field. LaSFM jointly models eigenvectors and eigenvalues, allowing information to pass between them through bidirectional cross-attention.

For eigenvectors, the method starts with Gaussian noise, removes its component in the all-ones direction, and orthonormalizes the result. During generation, it projects predicted velocities to satisfy both the nullspace condition and the tangent-space condition needed to maintain orthonormality. The paper develops the constrained geometry and establishes preservation results for the continuous dynamics.

For eigenvalues, the model works in unconstrained transformed coordinates. A cumulative softplus mapping converts these coordinates into positive, strictly increasing eigenvalues. Together, the two mechanisms keep the reconstructed spectral matrix symmetric, positive semidefinite and zero-row-sum throughout the continuous process.

Benchmark results are encouraging, not uniform

The experiments use Planar, stochastic block model, Community-small and QM9 datasets, with 80%/20% training–test splits. Comparisons include SPECTRE, GGSD and SFMG. The authors describe SFMG as a best-effort reproduction because its implementation was not publicly available.

Spectral evaluations compare generated and test distributions using normalized squared maximum mean discrepancy, or MMD ratios; lower is better. On QM9, LaSFM's wavelet ratio was 1.561, compared with 15.39 for SPECTRE, 45.31 for GGSD and 23.16 for SFMG. But LaSFM was not best on every measure: SPECTRE had the lower Planar eigenvalue ratio, for example.

For discrete graph evaluation, a separately trained flow-matching postprocessor converted spectral matrices into adjacency matrices. LaSFM generally achieved competitive distribution matching, but results were again mixed. On stochastic block model graphs, its joint validity–uniqueness–novelty score was 0.20, below SFMG's 0.24.

Steering molecules without abandoning the constraints

The molecular guidance experiments targeted HOMO energy, LUMO energy and their gap. They used nine-heavy-atom QM9 molecules and all eight nontrivial Laplacian eigenpairs. Guidance gradients were projected or passed through the eigenvalue mapping to retain the imposed constraints.

Here, reconstruction used thresholding rather than the learned graph postprocessor. Atom types came from sampled QM9 molecules, while RDKit assigned bond orders and checked molecular validity. Independent message-passing networks evaluated properties on valid reconstructed molecules. The authors report the lowest target errors for LaSFM across the three properties; these are predictor-based evaluations, not direct quantum-chemical calculations.

Ablations removing each constraint worsened reconstruction consistency and molecular validity. Nevertheless, the authors emphasize two remaining limits: LaSFM does not enforce nonpositive off-diagonal entries, and spectral outputs still require reconstruction into discrete graphs. Preserving these three constraints improves consistency, but does not by itself guarantee a valid combinatorial Laplacian or molecule.