Graph Generation with Spectral Geodesic Flow Matching

Xikun Huang, Tianyu Ruan, Chihao Zhang, Shihua Zhang

Generating realistic graphs—from social networks to molecular structures—is a notoriously difficult task. Graphs are discrete, irregular, and their representation changes depending on how you order the nodes. While diffusion models have recently set the bar for quality, they are often slow and struggle to respect the complex geometric constraints of graph structures.

In their latest paper, "Graph Generation with Spectral Geodesic Flow Matching," Xikun Huang and colleagues introduce SFMG, a framework that shifts the generative process from raw adjacency matrices to the "spectral" domain. By modeling the geometry of eigenvectors on curved manifolds, they’ve created a method that is not only more structurally aware but also up to 30 times faster than leading diffusion models.

TL;DR

SFMG is a novel graph generation framework that models eigenvalues in Euclidean space and eigenvectors on Stiefel manifolds using geodesic flow matching. By capturing the geometric "shape" of a graph through its spectral components, it produces high-fidelity graphs with a 30× speedup over diffusion-based approaches.

What Problem Does This Paper Address?

Most deep learning models for graph generation fall into two camps: autoregressive (building a graph node-by-node) or one-shot (generating the whole matrix at once). One-shot models often use diffusion, which works by slowly removing noise from a random matrix.

However, two major hurdles remain:

  1. Geometric Blindness: Many models focus on eigenvalues (the "spectrum") but ignore eigenvectors. Eigenvectors carry the actual "map" of the graph—how nodes cluster and connect globally.
  2. Constraint Violations: Eigenvectors must be orthogonal (perpendicular to each other). Standard diffusion adds Gaussian noise, which breaks this orthogonality. Forcing the model to stay within these "geometric rails" is mathematically taxing.

Methods

SFMG moves the generative task into the spectral domain using a three-stage pipeline:

  1. Spectral Decomposition: The model represents a graph by its Laplacian matrix's top $k$ eigenvalues and eigenvectors.
  2. Geodesic Flow Matching (The Core Innovation):
    • Instead of diffusion, the authors use Flow Matching, which learns a vector field that pushes noise toward the data distribution along straight paths.
  3. For eigenvalues, they use standard Euclidean flow matching.
  4. For eigenvectors, they operate on the Stiefel manifold—the mathematical space of all orthogonal matrices. They define "geodesic flows" (the shortest paths on a curved surface) to ensure the generated eigenvectors always remain valid and orthogonal.
  5. Adjacency Reconstruction: A final "post-processing" flow matching model takes the generated spectral components and reconstructs the discrete adjacency matrix and node features.

By working on the Stiefel manifold, the model respects the intrinsic geometry of the graph's structure rather than treating it as a flat collection of numbers.

Datasets

The authors evaluated SFMG on seven diverse benchmarks to test different structural properties:

  • General Graphs: Ego-Small (citation networks), Community-Small, Planar (graphs that can be drawn without crossing edges), SBM (Stochastic Block Model), and Grid.
  • Biological/Chemical: Enzymes (protein structures) and QM9 (a standard molecular dataset containing ~130k small molecules).

Key Insights and Ideas

  • Eigenvectors are the "Secret Sauce": The paper demonstrates that modeling eigenvectors is crucial for capturing global topology. Previous spectral models that only learned eigenvalues (like GSDM) suffered from low diversity and "redundant" outputs.
  • Manifolds over Euclidean Space: Treating eigenvectors as points in a flat space leads to "invalid" geometry. By using the Stiefel manifold, the model naturally "understands" the constraints of the data, leading to much higher structural validity.
  • Flow Matching > Diffusion: Diffusion requires complex noise schedules and hundreds of iterative steps. Flow matching simplifies this into a regression problem on vector fields, making training more stable and inference significantly faster.

Key Results

  • Massive Speedup: SFMG achieved up to a 30× speedup in generation time compared to GDSS (a top-tier diffusion model). For example, on the "Grid" dataset, GDSS took ~102 seconds to generate 10 graphs, while SFMG took only ~0.9 seconds.
  • Superior Fidelity: On the SBM dataset (which tests community detection), SFMG achieved 75% validity, dwarfing the 52.5% of the GAN-based SPECTRE and the 0% of diffusion-based GDSS.
  • Spectral Accuracy: The model consistently outperformed baselines in "Spectral MMD," a metric that measures how closely the generated graph's eigenvalues match the ground truth.

Limitations and Future Work

Despite the impressive speed and quality, the authors note a few challenges:

  • Scalability to Massive Graphs: While $k$ (the number of spectral components) can be kept small, the underlying manifold optimization still scales with the number of nodes ($n$). Generating graphs with tens of thousands of nodes remains computationally expensive.
  • Manifold Architectures: The current neural networks used (MLPs with residual blocks) are standard. The authors suggest that developing specialized architectures designed specifically for manifold-valued data could further boost performance.
  • High-Dimensional Regimes: Extending this to very high-dimensional spectral embeddings is non-trivial and may require more efficient ways to compute the "logarithm map" on the Stiefel manifold.

Summary updated

Abstract

Graph generation is a fundamental task with wide applications in modeling complex systems. Although existing methods align the spectrum or degree profile of the target graph, they often ignore the geometry induced by eigenvectors and the global structure of the graph. In this work, we propose Spectral Geodesic Flow Matching (SFMG), a novel framework that uses spectral eigenmaps to embed both input and target graphs into continuous Riemannian manifolds. We then define geodesic flows between embeddings and match distributions along these flows to generate output graphs. Our method yields several advantages: (i) captures geometric structure beyond eigenvalues, (ii) supports flexible generation of diverse graphs, and (iii) scales efficiently. Empirically, SFMG matches the performance of state-of-the-art approaches on graphlet, degree, and spectral metrics across diverse benchmarks. In particular, it achieves up to 30$\times$ speedup over diffusion-based models, offering a substantial advantage in scalability and training efficiency. We also demonstrate its ability to generalize to unseen graph scales. Overall, SFMG provides a new approach to graph synthesis by integrating spectral geometry with flow matching.
BibTeX
@misc{huang2025graph,
  author = {Xikun Huang and Tianyu Ruan and Chihao Zhang and Shihua Zhang},
  title = {{Graph Generation with Spectral Geodesic Flow Matching}},
  year = {2025},
  eprint = {2510.02520},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.02520},
}
Figure