Klein Flow Matching in Hyperbolic Latent Space

Generating realistic graphs requires capturing both local connectivity and large-scale organization, including hierarchical and tree-like patterns. Hyperbolic space is naturally suited to representing these patterns, making it a promising latent geometry for graph generation. We introduce Klein Flow Matching (KFM), a two-stage latent graph generation model that exploits a simple geometric property: hyperbolic geodesics appear as straight line segments in Klein coordinates. Specifically, KFM represents each conditional velocity using a fixed direction and a time-dependent scalar factor. This gives explicit positions and velocity targets for simulation-free flow-matching training. A graph autoencoder provides deterministic latent targets and condition codes; a conditional transformer learns their transport from a wrapped Gaussian base using the Klein metric. Sampling combines Riemannian Heun integration with graph decoding, including structural constraints. Across five main benchmarks, KFM shows competitive results in degree and clustering statistics. On additional benchmarks for generating planar graphs and trees, constrained decoding and candidate selection yield 100% jointly valid, unique, and novel outputs, with the lowest aggregate structural-discrepancy ratio among the compared models on trees. These results demonstrate the practical promise of KFM for generating graphs across diverse structural regimes.