acceptodds
Under review as a conference paper at ICLR 2027

One-Step Graph Sampling by Belief Flow Maps

Abstract

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.

Primary area:
generative models
Keywords:
One-step graph diffusion

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_f1d4OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper builds a consistency model for graph generation based upon GraphBSI [4] in three steps:

  1. Reparameterize the sampler step from the ODE from Theorem 4 in the GraphBSI paper with γ=0\gamma=0
  2. Add two consistency losses on top of the training loss: BTD based on Lagrangian self-distillation [1] and BCD as consistency target encouraging that multiple Heun result in a similar target as a single step, similar to [2]
  3. Sample with one or two steps

Empirically, the paper shows a slight improvement in molecule + synthetic graph generation tasks, even though baselines for single-evaluation generation are weak.

References:

[1]: Boffi, Nicholas, Michael Albergo, and Eric Vanden-Eijnden. "How to build a consistency model: Learning flow maps via self-distillation." Advances in Neural Information Processing Systems 38 (2026): 33346-33382. [2]: Frans, Kevin, et al. "One step diffusion via shortcut models." International Conference on Learning Representations. Vol. 2025. 2025.

[4]: Petersen, Ole, et al. "Discrete Bayesian Sample Inference for Graph Generation." International Conference on Learning Representations. Vol. 2026. 2026.

Critical strengths
  • Good presentation
  • First to train a consistency model based on GraphBSI
Critical weaknesses
  • The work does not add a lot of novel ideas. GraphBSI already presents on ODE-based sampler. The reparameterization is done similary e.g. in [3], both consistency model losses are at least closely inspired by [1] and [2], respectively
  • The empirical results only improve slightly against weak baselines

[3] Lu, Cheng, et al. "DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps." Advances in Neural Information Processing Systems, vol. 35, 2022.

Questions for authors
  • Synthetic graph benchmarks are very noisy. Would you mind publishing results with variance over multiple random seeds?
  • Results reported for e.g. GraphBSI are substantially worse than in the GraphBSI [4] paper. E.g. GraphBSI with 50 steps (EM) has validity of 99.3 for Moses in table 1 while you report validity of 45.2. Why?
  • Would you mind publishing empirical results on GuacaMol?
Reviewer_zyn3OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies few-step graph generation based on Bayesian Sample Inference (BSI), which generates graphs by iteratively refining continuous categorical beliefs over discrete nodes and edges. While the original BSI objective trains a model to reconstruct clean graph labels from noisy belief states, the authors reformulate its probability flow ODE and introduce Belief Flow Maps (BFM) to learn finite-time transitions along the belief trajectory.

The proposed framework adds two distillation objectives. Belief Chord Distillation (BCD) trains the model to predict the interval-average velocity obtained by integrating the ODE over several local steps, enabling a single large transition to approximate their total displacement. Belief Tangent Distillation (BTD) aligns the derivative of the learned transition with respect to its destination time with the instantaneous ODE velocity at the predicted endpoint, encouraging local consistency with the underlying dynamics.

Experiments on molecular and structural graph benchmarks show that BFM generally improves generation quality with few generation steps. Ablations on QM9 show that BCD provides the larger improvement in one-step distributional fidelity, while adding BTD further improves generation quality, particularly when composing the learned transitions for two-step sampling.

Critical strengths
  • While the objective used in BTD has already been proposed for flow-map self-distillation, BCD substantially improves one-step graph generation by supervising the full-interval displacement, allowing a single transition to better approximate multi-step belief refinement. The QM9 ablations support the contribution of BCD, while combining it with BTD gives the best results at both one and two sampling steps.

  • The paper establishes a clear connection between BSI dynamics and the BCD and BTD loss objectives. By reformulating the BSI probability-flow ODE in normalized coordinates and time, the authors obtain a common basis for BCD to match the interval-average velocity and for BTD to enforce local consistency with the instantaneous velocity.

Critical weaknesses
  • Although this paper improves generation efficiency, my main question is whether reducing the number of sampling steps is critical for the graph generation tasks considered. Compared with computationally demanding applications such as video generation, small molecule graph generation is relatively inexpensive, so the practical importance of reducing sampling to one or two steps could be better established. The authors should make the efficiency-quality trade-off explicit by relating the reported wall-clock savings to changes in validity and distributional fidelity relative to multi-step sampling. This would clarify whether the speed gains justify any loss in generation quality for the tasks considered.

  • While the QM9 ablations show that BCD improves one-step generation more than BTD, the reason for this difference is not sufficiently established. The authors attribute this advantage to supervision of the full-interval displacement, but do not directly demonstrate how it benefits the structural refinement required for graph generation. I would appreciate a more explicit analysis of whether and how BCD improves coordination among node and edge predictions, beyond the reported aggregate generation metrics.

  • While BFM improves over the few-step baselines, its absolute generation quality remains limited on the more challenging datasets as validity on MOSES and Tree is relatively low. An analysis of connectivity and cycle-related errors would help clarify the limitations of the proposed method.

  • The additional training cost of the proposed distillation objectives is not measured. BCD constructs its targets using four Heun substeps in the default setting, requiring multiple network evaluations, while BTD requires differentiation with respect to time. Although the paper reports sampling times, it does not report the resulting training time or memory overhead relative to the baselines. Reporting training GPU-hours and peak memory usage would help assess the overall computational trade-off.

Questions for authors
  • How many valid and unique graphs can BFM generate per second compared with multi-step samplers? It would be helpful to see these numbers alongside FCD to judge the trade-off between speed and quality.

  • Does BCD still outperform BTD on datasets beyond QM9? Also, can the authors show how it helps the model make more consistent node and edge predictions?

  • Why is validity still low on MOSES and Tree? For Tree in particular, do most invalid samples contain cycles, disconnected components, or both? What makes these errors difficult to fix within one or two sampling steps?

  • How much training time and memory does BFM require compared with the baselines? Please report GPU-hours and peak memory on comparable hardware, and explain how much overhead BCD and BTD each add.

Reviewer_kBxVOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes Belief Flow Maps (BFM), a framework to speed up graph generation by distilling multi-step generation into one or a few sampling steps. It introduces two objectives: Belief Chord Distillation (BCD), which supervises long-range transitions, and Belief Tangent Distillation (BTD), which encourages consistency with the local belief-flow dynamics. The paper also derives a simplified probability-flow ODE for categorical Bayesian Sample Inference (BSI).

Critical strengths

The paper addresses an important challenge in graph generation by proposing a trajectory-aware distillation framework that combines long-range transition supervision with local dynamics supervision to improve sampling efficiency.

Critical weaknesses
  1. The motivation for the proposed approach is not sufficiently clear. While the task is well motivated, it is unclear why combining long-range endpoint supervision with local velocity supervision is necessary. The authors should better explain the limitations of existing methods and why both objectives are needed. Also, the claimed computational bottleneck is not supported by concrete evidence, such as sampling time or resources. The benefit of one-step generation over few-step generation also needs better justification.

  2. The design choices need better justification. It is unclear why both BCD and BTD are necessary or how they complement each other. The authors should explain what each objective contributes and why their combination should outperform existing approaches.

  3. The connection to prior work is unclear. Since the method is based on BSI, it is not clear whether the derived ODE is mathematically novel or follows from a standard reparameterization of existing dynamics. The authors should clarify how their formulation differs from prior work on BSI and related discrete generative models.

  4. The experimental evaluation is limited. The experiments focus mainly on molecular datasets, making it difficult to assess generalization to other graph-generation tasks. The authors should report variance across multiple runs. Figure 7 in the appendix would also be more useful if it included ground-truth test graphs for comparison. In addition, MMD results should be reported consistently across datasets in Tables 1 and 2.

  5. The presentation of results is inconsistent. The use of boldface, underlining, and arrows is not always clear. For example, if an upward arrow for VUN indicates that higher values are better, it is unclear why the lowest value is boldfaced. The authors should check the tables for consistency.

  6. The results raise concerns about the method's effectiveness. In Tables 1 and 2, the proposed approach performs worse than some baselines on certain metrics. This raises questions about whether BFM consistently improves over existing methods. The authors should clarify these results and provide stronger evidence of its benefits in terms of generation quality and sampling efficiency.

Questions for authors

see above

1 comment

I have read the author’s response and have revised my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.