Training Probabilistic Graph Predictors without Graph Matching via Flow Matching

Supervised graph prediction (SGP) maps any kind of input, such as images or molecular fingerprints, to graph outputs. The main challenge is that graphs do not have an intrinsic node ordering, making many different tensor representations valid and thus complicating coordinate-wise supervision. Existing SGP methods often handle this issue by matching predicted and target graphs. However, matching typically introduces a cubic-time alignment step and is hard to extend to settings with multiple valid, non-isomorphic outputs. We instead cast SGP as conditional generation over graph isomorphism classes and introduce pSGP (*probabilistic supervised graph predictor*), which instantiates this formulation using permutation-equivariant conditional flow matching. pSGP supports graph outputs with discrete and continuous graph features, and its training using standard coordinate-wise losses without graph matching scales quadratically. We prove that its empirical risk is invariant to the arbitrary indexing of each target graph. On six established SGP benchmarks, a single sample from pSGP outperforms the strongest baseline on graph-isomorphism accuracy, and modal decoding from multiple samples improves these results further. We also introduce a probabilistic graph prediction benchmark from genotype data with ambiguous targets, where pSGP achieves lower discrepancy from the target distribution over graph isomorphism classes. These results support conditional flow matching as a scalable, probabilistic approach to SGP.