Natural Graph Diffusion Solver

Existing graph diffusion samplers operate under uniform time discretization, which does not reflect the non-uniform nature of distributional evolution in graph generative processes. In this paper, we establish a fundamental principle for graph diffusion generation: a natural sampler should progress at a constant rate of distributional evolution. We show that this principle admits a geometric characterization, revealing that equal distributional change is equivalent to traversing equal Fisher-Rao arc-length increments along the reverse diffusion trajectory. This connection bridges diffusion sampling and information geometry, providing a principled foundation for information-geometry-aware generation. Inspired by this insight, we introduce the Natural Graph Diffusion Solver (NGD-solver) that enforces constant distributional evolution along the reverse diffusion trajectory. NGD-solver derives an information-geometry-aware correction that can be seamlessly incorporated into the reverse sampling process. By adaptively calibrating reverse transitions according to the local geometric sensitivity of distributions, NGD-solver promotes a constant-rate and stable evolution in distribution space throughout the diffusion. NGD-solver can be seamlessly integrated into pretrained graph diffusion models at inference time. Extensive experiments on graph generation benchmarks demonstrate that NGD-solver consistently and significantly improves structural fidelity and generation quality.