One-Step Graph Sampling by Belief Flow Maps

Diffusion-like graph generation typically relies on iterative sampling, where the generated state is progressively refined toward the data distribution. For graph generation, we adopt a categorical Bayesian flow that naturally accommodates graph structures. Our key insight is to derive a particularly simple probability-flow ODE that linearly links the belief dynamics to data prediction. This ODE provides a principled foundation that allows one-step sampling and facilitates trajectory-based distillation. The resulting continuous trajectory allows one-step generation to be formulated as learning a finite-time transition along the Bayesian flow. Distilling graph generation into a single step, however, is challenging. We argue that effective one-step graph generation should preserve not only the endpoints of the sampling process, but also its underlying trajectory. Based on this observation, we propose Belief Flow Maps (BFM), a trajectory-aware distillation framework. In BFM, belief chord distillation performs local transitions along the probability-flow trajectory and distills their refined endpoint into a single large transition, while belief tangent distillation provides complementary local supervision by aligning the learned transition with the belief-flow velocity at the reached belief state. Together, they capture both long-range transport and local trajectory dynamics. Experiments on molecular and structural graph generation benchmarks demonstrate that BFM substantially improves one-step generation quality over existing methods.