Graph Generation with Spectral Geodesic Flow Matching
This addresses graph synthesis for modeling complex systems, offering a novel integration of spectral geometry with flow matching, though it appears incremental as it builds on existing spectral and flow-based approaches.
The paper tackles graph generation by proposing Spectral Geodesic Flow Matching (SFMG), which embeds graphs into Riemannian manifolds using spectral eigenmaps and matches distributions along geodesic flows, achieving performance comparable to state-of-the-art methods with up to 30x speedup over diffusion-based models.
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.