Improving Graph Generation with Flow Matching and Optimal Transport
Flow matching generative model;graph generation
Yes
No ethics review needed.
Although the performance is promising, the optimal transport is quite time-consuming. It is better to provide the complexity analysis or train/inference time compared with other methods.
1. This paper is well-written and easy to read.
2. The authors introduced the first discrete flow matching generative model tailored for graph data, leveraging optimal transport for improved efficiency and stability.
3. The performance of the proposed method is quite promising.
The paper introduces GGFlow, a novel generative model aimed at improving the generation of graph-structured data. The author proposed a discrete flow matching framework combined with optimal transport (OT) and an edge-augmented graph transformer. It is the first discrete flow matching generative model with optimal transport for graph data. Additionally, GGFlow introduces a novel goal-guided generation
framework to control the generative trajectory of our model towards desired properties. The experiments show that GGFlow achieves state-of-the-art results in both unconditional and conditional graph and molecule generation tasks.
This paper introduces a novel technique that combines discrete flow matching with optimal transport to enhance the efficiency of graph generation. While innovative, borrowing flow matching concepts from diffusion models used in image generation, several aspects could be further clarified:

1. Reward Function Definition: The method relies on a well-defined reward function, which is critical in reinforcement learning (RL) algorithms. However, the paper lacks a discussion on how the choice of reward function impacts the algorithm's performance and outcome.

2. Stability Claims: Although the authors assert that this approach offers greater stability in training and sampling, the experimental results do not provide direct comparisons with other diffusion-based generation algorithms to substantiate this claim.

3. Optimal Transport Justification: The use of optimal transport is presented as an improvement over other flow-matching techniques, yet there is no theoretical evidence provided to explain why optimal transport is preferable in this context. A rationale for this choice would strengthen the paper.
Yes
No ethics review needed.
Please address the weakness above.
- The discrete flow matching for graph generation seems to be novel, although there is existing work on flow matching framework for graph generation.

- The edge-augmented graph transformer seems to be an improvement of the previous graph transformer architecture.

- The motivation for using optimal transport to improve sampling efficiency for graph generation is reasonable but lacks experimental results.
This work introduces a discrete flow matching model for graph generation that uses optimal transport and edge-augmented graph transformer. The authors also introduce RL-based conditional graph generation. The proposed approach yields stable training and improves sampling efficiency.
- CatFlow (Eijkelboom et al., 2024) is a graph generation method based on variational flow matching, which is highly related to this work. Although there is a comparison in Appendix B.3, there should be an experimental comparison and explanation of why GGFlow is better. 

- Experiments for generic graph generation should use larger datasets like Planar or SBM instead of Ego-small and Community-small datasets which consist of very small graphs. Additionally, validity metrics such as V.U.N. (valid, unique, and novel) should also be used to evaluate models as MMDs are not a reliable metric, especially for small graphs. In particular, for the Grid dataset, the validity metric should be used to show that the generative model can actually produce a grid structure. 

- Ablation study should be also conducted using datasets where validity or similar metrics can be measured, e.g., Planar or SBM datasets.  Relying only on MMD does not give much information on how the performance is improved.

- Comparison on molecule graph generation is not fair. It is not clear whether the new graph transformer architecture or the flow matching framework provides the performance improvement. In order to show this, there should be an ablation study on using the same architecture.

- The ablation study on sampling efficiency improvement based on optimal transport is not clear. Which experiments support this claim? Figure 3 only shows that GGFlow outperforms DiGress or GDSS, not the OT ablation.


[1] Eijkelboom et al., Variational Flow Matching for Graph Generation, 2024
Yes
No ethics review needed.
See weakness.
1. Clear illustration of graph flow matching method.
2. Strong performance on generation tasks. Clear ablation study.
This work proposes a discrete flow matching generative model incorporating optimal transport for graph structures with improved training stablility and efficient sampling compared with diffusion model. It achieves outstanding performance on both unconditional and conditional molecule graph generation tasks.
1. Incomplete ablation study. Ablation of OF and GraphEvo is only conducted on one synthetic datasets.
2. Training stablility, as one of the benefits this work claims, is not compared in experiments.
Yes
No ethics review needed.
My evaluation relies primarily on the accuracy of Theorem 1 and the experimental design. The current rating assumes that Theorem 1 is incorrect. Naturally, if further clarification or evidence proves this theorem valid the rating would be significantly revised.
Similarly, clarification and/or improvement to the experimental section would change my evaluation.
The paper is well-written and thoroughly documented. The appendix provides useful additional insights.

The proposed model introduces a novel graph generative approach based on discrete flow matching, which is a novel approach for graph generation. 

The method demonstrates competitive generative performance on small graph datasets, showing its effectiveness and relevance.

These are concise but significant strengths.
The paper introduces GGFlow, a graph generative model based on discrete flow matching and optimal transport. GGFlow aims to improve upon current graph generation methods, particularly diffusion-based models, by addressing two challenges: training stability and sampling efficiency. Additionally, GGFlow introduces a goal-guided generation framework using reinforcement learning, enabling conditional generation.

GGFlow generates graphs by transforming an initial noise distribution to a target data distribution through a smooth probability path, defined by a probability velocity field. This approach  the complexities associated with stochastic processes as in diffusion models.
To reduce the variance in training and sampling, GGFlow incorporates optimal transport to construct the joint distribution of the source and target graphs. The model integrates an edge-augmented transformer architecture (GraphEvo), which uses a triangle attention mechanism.

Using reinforcement learning, GGFlow can guide the graph generation process to meet predefined objectives, allowing for conditional generation where desired properties are targeted directly. 
GGFlow demonstrates high performance on small graph generation tasks. 

The article evaluates the model on synthetic and real-world datasets of small graphs, demonstrating effectiveness of the method. The experimental section includes an ablation study to assess the impact of both GraphEvo and Optimal Transport on model performance.
**Theorem 1 Validity**

The claim in Theorem 1 is problematic because the proof relies on the invariance of the Hamming distance under arbitrary permutations. However, the proof should show that the distance is invariant to independent permutations, i.e., $H(G^0, G^1) = H(\pi^0G^0, \pi^1G^1)$ instead of identical permutations (as exposed in appendix C.4: $H(G^0, G^1) = H(\pi G^0, \pi G^1)$). Therefore, the invariance does not hold. Consequently, if this assumption is indeed incorrect, then the Optimal Transport (OT) mechanism does not operate directly on graphs, but rather on specific graph representations, undermining a key contribution of the paper.

If Theorem 1 indeed fails, this calls into question the effectiveness of OT as applied in this context, and a significant part of the article should be reviewed.

**Experiments**

The experimental section has several limitations, and addressing these would significantly strengthen the work's impact. The main experimental limitations are as follows:

- Small Datasets: Except for the 'grid' dataset, which is a peculiar synthetic dataset, the model has only been tested on small graphs (up to 64 nodes for Planar, which is only reported in the appendix, and up to 38 nodes for Zinc). Testing on larger datasets such as SBM, Enzymes, Ego, or Proteins would improve the evaluation.

- Overfitting Concerns on Small Datasets: Evaluations on larger datasets are especially important given that generic datasets, often containing few instances, can easily be overfit. For instance, the lower novelty and uniqueness score on Ego-Small suggests some degree of overfitting on that dataset.

- Incomplete Ablation Study: While the model introduces several additional components, a more systematic ablation study on multiple dataset would clarify each element’s contribution. Moreover, a comparison between discrete flow matching and discrete diffusion would highlight the advantages of the flow matching framework. To ensure fairness, it would be beneficial to use a discrete diffusion model with identical architecture, extra features, and hyperparameters as a baseline. For molecular generation, presenting results without additional molecular features (which are not used in most baseline models and has been improved significantly the molecular metrics) would also be insightful.

- Scalability: While scalability is briefly mentioned as model limitation in the conclusion, it would be beneficial to include indicators of this issue in the experimental section. For instance, reporting generation times would provide insight about the model scalability.

**Lack of Novelty/Originality**

The paper represents an application of discrete flow matching to graph generation. This type of approach was expected; indeed, another paper submitted paper proposes a similar contribution (https://openreview.net/forum?id=ZGRRC514rI). 

**Missing Explicit References in Method Presentation**

Section 3 would benefit from more explicit references to foundational works. For instance, it would be useful to specify which discrete flow matching frameworks, as cited in Section 2, the authors drew inspiration from and how GGFlow differs from these.

**Minor Comments**

Line 51: This sentence lacks a main verb.

Line 44: Could you clarify the instability issues encountered in training diffusion models or provide relevant references?
@inproceedings{
anonymous2024improving,
title={Improving Graph Generation with Flow Matching and Optimal Transport},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=rMyfMS5nMt},
note={under review}
}
Generating graph-structured data is crucial in various domains but remains challenging due to the complex interdependencies between nodes and edges. While diffusion models have demonstrated their superior generative capabilities, they often suffer from unstable training and inefficient sampling. To enhance generation performance and training stability, we propose GGFlow, a discrete flow matching generative model incorporating optimal transport for graph structures and it incorporates an edge-augmented graph transformer to enable the direct communications among edges. Additionally, GGFlow introduces a novel goal-guided generation framework to control the generative trajectory of our model towards desired properties. GGFlow demonstrates superior performance on both unconditional and conditional generation tasks, outperforming existing baselines and underscoring its effectiveness and potential for wider application.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Flow matching generative model graph generation
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/1378054b490474a8771901197fbeac331145fd12.pdf
generative models
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Improving Graph Generation with Flow Matching and Optimal Transport
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission