Improving Graph Generation with Flow Matching and Optimal Transport

Authors: Xiaoyang Hou, Tian Zhu, Milong Ren, Dongbo Bu, Xin Gao, Chunming Zhang, Shiwei Sun
Primary area: generative models
Keywords: Flow matching generative model, graph generation

Abstract:
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.

Decision: reject
Reviewer scores: 8, 6, 6, 1

Reviews and discussion:
<thread>
creation date:
1730303250031

thread_type:
official_review

<thread_object>
creator: reviewer_pzdl

<content>
summary:
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.

strengths:
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.

weaknesses:
Weaknesses after rebuttal:

### 1. OT is Not Permutation-Invariant

One of the claimed main contributions of the paper is the use of Optimal Transport (OT) for graphs. However, the OT employed is not permutation-invariant, making it an OT on adjacency matrices under specific permutations, rather than on graphs.

The OT relies on the Hamming distance, which aggregates element-wise differences between adjacency (and annotation) matrices. This element-wise computation is dependent on node ordering, meaning that permuting one matrix changes the distance: \( H(G_0, G_1) \neq H(G_0, \pi G_1) \).

While the lack of permutation invariance would not be a problem if directly acknowledged, the paper obscures this limitation, and some formulations are misleading.

---

### 2. Misleading Claims

Theorem 1 states: "the optimal transport map exhibits invariance under identical permutations." While this is technically true, it is misleading because it implies that the OT is invariant under all permutations, which is not the case. Specifically, if one matrix is permuted independently, the Hamming distance is not preserved: \( H(G_0, G_1) \neq H(G_0, \pi G_1) \).

This leads to other misleading claims:

- Lines 54–55: "The model preserves graph sparsity and permutation invariance, which is essential for realistic graph generation."  
  - This is true without OT but incorrect with OT.  

- Line 272: "Graphs are invariant to random node permutations, and GGFlow preserves this property."  
  - Similarly, this is true without OT but incorrect with OT.

- Lines 275–277: "Since the source and target distributions are permutation invariant, the independent coupling also exhibits this invariance. Our optimal transport map, derived from Equation 7, similarly demonstrates invariance to identical permutations."  
  - The use of "similarly" is misleading, as "invariance to identical permutations" is fundamentally different from true permutation invariance.

The paper does not address how this non-invariant OT relates to truly invariant graph distances, leaving a significant gap in the discussion.

---

### 3. Inconsistent Results and Interpretation

The authors claim that OT improves generative performance. However, the ablation study (Table 4) shows the model without OT performing better on 3 out of 8 metrics. With metrics being close and no standard deviations provided, there is no evidence of a significant effect of OT.

Additionally, in the enzyme dataset, the paper reports MMD distances between generated and test sets that outperform the MMD between training and test sets. The explanation provided is incorrect, as MMD, being a distance between distributions, does not directly depend on sample size.

---

### Summary

The paper's claims around OT, permutation invariance, and the effectiveness of OT lack clarity and accuracy. Furthermore, the experimental results do not convincingly support the proposed benefits of OT. These issues should be addressed to ensure transparency and scientific rigor.



___ Version before rebuttal ____

The paper raise some concerns:
- Some claims in the paper are misleading.
- Some results are questionable (generated graph distribution measured closer to the test set than the training set distribution?)


**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?

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730548800294

thread_type:
official_review

<thread_object>
creator: reviewer_ayqj

<content>
summary:
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.

strengths:
1. Clear illustration of graph flow matching method.
2. Strong performance on generation tasks. Clear ablation study.

weaknesses:
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.

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730627912595

thread_type:
official_review

<thread_object>
creator: reviewer_nffn

<content>
summary:
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.

strengths:
- 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.

weaknesses:
- 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

questions:
Please address the weakness above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730723036212

thread_type:
official_review

<thread_object>
creator: reviewer_exo3

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732806515380

thread_type:
official_comment

<thread_object>
creator: area_chair_dcvc

<content>
title:
AC's suggestion

comment:
There were notable disagreements about whether the paper meets the acceptance criteria. On the positive side, the results appear promising. However, concerns were raised about the source of the performance improvements. Are these gains genuinely due to the use of flow matching and OT, as suggested in the title, or are they influenced by other factors, such as a better network architecture or the inclusion of additional features? The authors should prioritize addressing these concerns to facilitate constructive discussions between the reviewers and area chairs.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733281552891

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Rebuttal Summary to Reviewers' Feedback

comment:
Dear Reviewers/Area Chairs/Senior Area Chairs,

We sincerely appreciate all reviewers' constructive feedback. We have carefully addressed each comment and made the necessary revisions accordingly. Here are the main revisions in our rebuttal phase:

1. **Optimal Transport:**
   - We revised Theorem 1 to avoid any misleading.
   - We added detailed explanations and rationales about our optimal transport in Appendix C.4 to introduce the plausibility of our proposed OT.
   - We provided a theoretical proof of Lemma 1 in Appendix C.4 to show that our optimal transport preserves the permutation property of generated graphs.
   - We included a time analysis of OT in Appendix E to demonstrate its efficiency.

2. **Ablation Studies:**
   - We added Planar datasets to our ablation studies in Table 4 to further demonstrate the effectiveness of our proposed flow matching method and optimal transport.
   - We provided training and inference analysis of using optimal transport in Appendix J.2 to show that our OT significantly improves the training stability and efficiency of our model.

3. **Experiments:**
   - We provided results on the Enzymes dataset in Appendix H to further demonstrate the effectiveness of our model on large graph datasets.

We appreciate the reviewers' valuable feedback and suggestions, which have significantly improved the quality of our manuscript.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces a discrete flow matching framework for graph generation, incorporating optimal transport (OT), an edge-augmented transformer architecture (GraphEvo), and goal-conditioned generation. While the integration of discrete flow matching with OT and GraphEvo represents a new development, the submission received mixed reviews. Promising results were noted, but significant concerns were also raised by reviewers.

### Key Concerns:

1. **Fundamental Differences with Diffusion Models:**  
   The paper does not clearly articulate the fundamental differences between the proposed discrete flow matching framework and existing discrete diffusion/flow-matching models. It remains unclear why the proposed method outperforms existing graph generation algorithms based on diffusion or flow-matching approaches.

2. **Unclear Novelty and Component Contributions:**  
   The submission integrates multiple components, but the specific novelty of each element is ambiguous. If the contribution lies in a particular component, that component should be evaluated within both flow and diffusion models to isolate its impact. Alternatively, if the novelty is in the combination of these components, a detailed theoretical explanation is necessary to justify why this specific combination outperforms alternatives (e.g., substituting flow with diffusion or avoiding pre-ordering the nodes of training and prior graphs).

3. **Permutation-Invariance and Node Ordering Assumptions:**  
   The paper’s use of permutation invariance under the assumption of a fixed node order has been a central point of contention. The authors argue that a fixed node order ensures permutation invariance, while a reviewer challenges this claim, questioning how a fixed order can be assumed in permutation-invariant graphs. Despite extensive discussion during the review phase, this critical issue remains unresolved.

4. **Potential Hidden Heuristics Influencing Performance:**  
  After synthesizing the reviews and carefully evaluating the paper, the Area Chair has concerns about potential hidden heuristics that may underlie the observed performance gains. Specifically, unanswered questions remain regarding the influence of training data on the prior distribution of nodes and the method by which generated nodes are ordered to align with the training graphs. These aspects are critical for understanding the meaningful application of OT in the context of fixed node orders, as opposed to truly permutation-invariant graphs.

### Summary and Recommendation:
While the paper demonstrates empirical promise, unresolved issues regarding its theoretical foundations, experimental design, and the validity of claims related to OT and permutation invariance undermine its contribution. Additionally, the reliance on pre-existing architectures and features, without substantial advancement in graph generation methodology, renders the novelty incremental rather than transformative. These limitations outweigh the paper's strengths. The authors are encouraged to address these concerns in a revised submission.