Comparison with other graph generative models, such as flow-based and discrete diffusion-based models

We acknowledge the reviewer's interest in comparing our proposed method with other graph generative models, such as flow-based and discrete diffusion-based models. We provide a brief overview to highlight the distinctions:

Flow-Based Models: These models, like normalizing flows, transform simple base distributions into complex ones through a series of invertible and differentiable mappings. This approach allows for exact likelihood computation and efficient sampling, making them effective in continuous data domains such as image generation.

Discrete Diffusion-Based Models: These models generate data by learning to reverse a noising process, starting from noise and progressively refining it to match the target data distribution. They have been particularly successful in generating high-quality images and have been extended to other domains.

GFlowNets: In contrast, GFlowNets conceptualize generation as a sequential decision-making process, constructing complex objects like graphs through sequences of actions. They aim to sample structures proportional to a given reward function, facilitating the discovery of diverse high-reward structures. This approach is particularly advantageous in scenarios where the target distribution is unnormalized or difficult to sample from directly.

Please note that our work focuses on addressing the unique challenges of equivalent actions in GFlowNets (rather than improving the performances of other graph generative models), improving the robustness and sampling efficiency of GFlowNets in tasks where such challenges are critical bottlenecks, such as graph generation. We believe this distinction is important and will clarify it further in the revision.

Dear Reviewer mRgy,

We hope this message finds you well. As the author-reviewer discussion period is set to close in two days, we wanted to kindly remind you of the opportunity to share any additional questions, comments, or suggestions regarding our work.

We would like to highlight our key contributions

• Rigorous theoretical analysis of the "equivalent action problem" in GFlowNets, demonstrating that failing to account for equivalent actions introduces a systematic bias, especially in graph generation tasks involving high-symmetry objects.
• Novel Correction Method: Development of an automorphism-based reward-scaling technique to correct the bias, ensuring accurate modeling of the target distribution. This solution applies efficiently to atom- and fragment-based graph generation schemes.
• Unbiased Model Likelihood Estimator: Introduction of an unbiased estimator for model likelihood, allowing for rigorous evaluation of GFlowNet performance in generative tasks.
• Efficient Implementation: Proposed a computationally efficient method for automorphism correction, which requires only one computation per trajectory rather than at each transition, significantly reducing computational overhead.

We sincerely hope that the reviewer takes these contributions into account in their evaluation.

We would deeply appreciate your support in this process and look forward to hearing from you.

Best, Authors

Thanks for appreciating our work and providing valuable questions!

Illustrative Example

Thanks for the suggestion! We included the result of the toy experiment for illustrative purposes, but found that it may be difficult to understand without careful reading. In the revised version, we will include a similar experiment with uniform target distribution.

Computaional Cost

While computing the exact $|\text{Aut}(s)|$ has inherent complexity, as discussed in the paper, this complexity is unavoidable for exact computation. However, irrespective of the computational cost, fixing the sampling bias due to the ignorance of equivalent actions is a fundamental issue that needs to be resolved. This correction introduces an inherent computational cost, but it is necessary to maintain the consistency of sampling. In practice, fast heuristic algorithms often perform well, particularly for relatively smaller graphs, and significantly reduce the computational overhead associated with calculating $|\text{Aut}(s)|$.

Furthermore, our proposed method requires computing automorphisms only once per trajectory. We present additional experimental results measuring compute time below. Note that the scale of the experiments in our paper corresponds to QM9 and ZINC250k.

---

---

*Large: the largest molecules in PubChem, data retrieved from https://github.com/danielflamshep/genmoltasks. This data is used in the paper “Language models can learn complex molecular distributions.”

**Experiments were conducted on an Apple M1 processor.

---

Compared to sampling trajectories, which involves multiple forward passes through a neural network, the compute time for $|\text{Aut}(s)|$ is negligible. For comparison, we report the speed of molecular parsing algorithms measured using ZINC250k: 0.06 ms ± 0.70 (SMILES → molecule) and 0.04 ms ± 0.05 (molecule → SMILES). The combination of two parsing steps is often used to check the validity of a given molecule in various prior works. In words, computing $|\text{Aut}(s)|$ is in an order of magnitude faster than validity checking algorithm.

We used the bliss algorithm in our paper. It is easy to use as it is included in the igraph package and is fast enough for our purposes. If molecular symmetries grow, such as when symmetric fragments are repeated in polymers, we can still count automorphisms in few milliseconds using the nauty package as can be seen in the table. We observed that the pynauty package does not natively support distinguishing between different edge types, requiring us to transform the input graphs by attaching virtual nodes to handle this limitation. The reported time in the table reflects these preprocessing steps.

While we believe the compute time is already minimal considering current applications, we provide two more recipes to even further improve the run time.

• Data processing tasks can be easily parallelized across multiple CPUs. Since GFlowNet is an off-policy algorithm, $|\text{Aut}(s)|$ can be computed concurrently with the policy's learning process.
• For large graphs, fragment-based generation is highly likely to be employed. In such cases, we can utilize an approximate correction formula, as outlined in the paper.

In conclusion, the computational overhead of computing automorphism in practice be minor relative to computation of the entire pipeline.

Effects of Reparameterization

Great question! In our preliminary experiments, we observed no effect of reparameterization on convergence speed. While we are open to further investigation, we offer one possible explanation.

When using a fixed backward policy, we have a unique state flow function, denoted as $F(s)$. This is the function we obtain if corrections are made at every step. On the other hand, if corrections are applied at the end of trajectories, the flow function itself must learn to correct automorphisms. In this case, the flow function becomes $\tilde F(G) = F(s)|\text{Aut}(s)|$ (see figure 6 in the paper).

If we decompose $\tilde F(G)$ into two parts, namely $F(s)$ and $|\text{Aut}(s)|$, it is may happen that the challenging part of the learning process lies in $F(s)$, which is related to reward function $R(s)$. This could explain why intermediate reward signals led to faster learning in previous experiments, whereas intermediate corrections may require further investigation.

We hope this explanation addresses your questions.

Thanks for appreciating our work and providing helpful feedback!

Experiments

Implications of experiments: top-k diversity and reward

The purpose of measuring top-k diversity and reward is not to demonstrate the correctness of the proposed method. Instead, the experiment aims to provide insights into how unbiased distribution benefits downstream tasks, as diverse and high-reward molecules are crucial for drug discovery. To assess the correctness of our method, we used Pearson correlation.

The effects of bias correction depend on the landscape of the given reward function. If many high-reward molecules are also highly symmetric, the proposed method is more likely to identify these molecules compared to methods without correction. Conversely, if only a few high-reward molecules are symmetric, the correction does not guarantee strong performance in terms of top-k diversity and reward. However, regardless of the task, it is essential to recognize the effects of the correction in advance. Without corrections, there is a risk of inadvertently missing candidate molecules.

Datasets

To clarify, GFlowNets are trained based on a given reward function and, in principle, do not require a dataset. We referenced the QM9 dataset because the reward function used in our experiments was trained on QM9, which provides important molecular properties, the HOMO-LUMO gap.

The ZINC dataset, on the other hand, was used to construct the fragment vocabulary. However, it was not directly utilized beyond this, as the purpose of GFlowNet is not to learn a distribution from the data but rather to generate graphs guided by the reward function.

We hope this explanation addresses your concern.

Choice of reward exponent

We found that prior work used wildly different reward exponents $\beta$ for their experiments. For example, the very first GFlowNet paper used $\beta=10$ for sEH experiment, while Multi-objective GFlowNet used 96, and LS-GFN used 6. Our reasoning was that if we use high reward exponent, the training depends more on exploration algorithm and requires longer training, so we chose modest values.

Technical Contributions

The first paper to study the theoretical foundations on equivalent actions

To the best of our knowledge, ours is the first paper to study the theoretical foundations of the equivalent action problem, both within the GFlowNet (to our best knowledge, and graph generation communities). While the problem might seem straightforward in hindsight, we would like to emphasize that this recognition often comes after the issue has been formally identified and analyzed. Such seemingly straightforward findings can have a profound impact, as they address fundamental challenges that, once resolved, open new avenues for research and application—something we strongly believe as a strength of our work, not a limitation.

We also highlight that our findings go beyond correcting GFlowNet’s sampling distribution. We introduce a novel method for estimating model likelihood, which has significant implications for a variety of graph-related tasks. This dual contribution demonstrates the broader relevance and potential influence of our work in the field.

Impact of our findings on graph generation

Although we are not certain how previous works tackled the equivalent action problem, it is highly likely that they employed the approximation $p(s'|s) \approx p(G'|G)$, either intentionally or unintentionally, as evidenced by some open-source GFlowNet implementations. While this approximation leads to an incorrect sampling distribution, we believe that the previous experimental results remain valid, provided the metrics used are consistent and the results are interpreted carefully with the problem in mind. However, we do believe that performance can be improved with the correction we propose, and we recommend that this correction be included in every future work. In addition, we believe our formulation that distinguishes states and graphs is also helpful for clarifying problems in other graph tasks as well; we briefly summarized how our findings can be applied to methods that introduce ‘node ordering’ as a variable in Appendix D.

Presentation

Notation

We will revise the manuscript and include the table of notations to make it clearer and more user-friendly in the updated version, specifically by distinguishing between states/graphs and transitions/terminal states.

Limitations

Thank you for your feedback. We will address the discussion on limitations of our work in the revised version.

Theorem 2 → Corollary

Thank you for your suggestion. We are open to modifying Theorem 2 into a Corollary in the revised version, as it is an implication from Theorem 1.

Computational Cost

While computing the exact $|\text{Aut}(s)|$ has inherent complexity, as discussed in the paper, this complexity is unavoidable for exact computation. However, irrespective of the computational cost, fixing the sampling bias due to the ignorance of equivalent actions is a fundamental issue that needs to be resolved. This correction introduces an inherent computational cost, but it is necessary to maintain the consistency of sampling. In practice, fast heuristic algorithms often perform well, particularly for relatively smaller graphs, and significantly reduce the computational overhead associated with calculating $|\text{Aut}(s)|$.

We present additional experimental results measuring the compute, as shown below. Note that the scale of the experiments in our paper corresponds to QM9 and ZINC250k.

---

---

*Large: the largest molecules in PubChem, data retrieved from https://github.com/danielflamshep/genmoltasks. This data is used in the paper “Language models can learn complex molecular distributions.”

**Experiments were conducted on an Apple M1 processor.

---

When compared to the cost of sampling trajectories, which involves multiple forward passes through a neural network, the compute time for $|\text{Aut}(s)|$ remains still negligible. Also it is important to note that our proposed method requires computing automorphisms only once per trajectory. For comparison, we report the speed of molecular parsing algorithms measured using ZINC250k: 0.06 ms ± 0.70 (SMILES → molecule) and 0.04 ms ± 0.05 (molecule → SMILES). The combination of two parsing steps is often used to check the validity of a given molecule in various prior works. In words, computing $|\text{Aut}(s)|$ is in an order of magnitude faster than validity checking algorithm.

We used the bliss algorithm in our paper. It is easy to use as it is included in the igraph package and is fast enough for our purposes. For large molecules, we can still count automorphisms in few milliseconds using the nauty package as can be seen in the table. We observed that the pynauty package does not natively support distinguishing between different edge types, requiring us to transform the input graphs by attaching virtual nodes to handle this limitation. The reported time in the table reflects these preprocessing steps.

While we believe the compute time is already minimal considering current applications, we provide two more recipes to even further improve the run time.

• Data processing tasks can be easily parallelized across multiple CPUs. Since GFlowNet is an off-policy algorithm, $|\text{Aut}(s)|$ can be computed concurrently with the policy's learning process.
• For large graphs, fragment-based generation is highly likely to be employed. In such cases, we can utilize an approximate correction formula, as outlined in the paper.

In conclusion, the computational overhead of computing automorphism in practice be minor relative to computation of the entire pipeline.

Thanks for appreciating our work and providing a great summary!

Computational Cost

While computing the exact $|\text{Aut}(s)|$ has inherent complexity, as discussed in the paper, this complexity is unavoidable for exact computation. However, irrespective of the computational cost, fixing the sampling bias due to the ignorance of equivalent actions is a fundamental issue that needs to be resolved. This correction introduces an inherent computational cost, but it is necessary to maintain the consistency of sampling. In practice, fast heuristic algorithms often perform well, particularly for relatively smaller graphs, and significantly reduce the computational overhead associated with calculating $|\text{Aut}(s)|$.

Furthermore, our proposed method requires computing automorphisms only once per trajectory. We present additional experimental results measuring compute time below. Note that the scale of the experiments in our paper corresponds to QM9 and ZINC250k.

---

---

*Large: the largest molecules in PubChem, data retrieved from https://github.com/danielflamshep/genmoltasks. This data is used in the paper “Language models can learn complex molecular distributions.”

**Experiments were conducted on an Apple M1 processor.

---

Compared to sampling trajectories, which involves multiple forward passes through a neural network, the compute time for $|\text{Aut}(s)|$ is negligible. For comparison, we report the speed of molecular parsing algorithms measured using ZINC250k: 0.06 ms ± 0.70 (SMILES → molecule) and 0.04 ms ± 0.05 (molecule → SMILES). The combination of two parsing steps is often used to check the validity of a given molecule in various prior works. In words, computing $|\text{Aut}(s)|$ is in an order of magnitude faster than validity checking algorithm.

Our primary focus in this work is on small molecule generation for drug discovery, where smaller molecular sizes are most relevant. These sizes align with the practical requirements of many real-world drug discovery tasks, making our experiments and methodology well-suited to this domain.

That said, we emphasize that our method is not inherently limited to small molecules and can extend to larger molecules. The scalability of the approach depends on the computational efficiency of the symmetry calculations, and modern graph-processing tools enable handling larger molecular structures effectively. While the specific experiments in our paper focus on small molecules, the underlying principles and methodology remain applicable to larger graphs, provided appropriate computational resources and preprocessing techniques are employed. Furthermore, the compute time for counting automorphisms for large molecules is as small as few milliseconds as reported in the table.

While we believe the compute time is already minimal considering current applications, we provide two more recipes to even further improve the run time.

• Data processing tasks can be easily parallelized across multiple CPUs. Since GFlowNet is an off-policy algorithm, $\text{|Aut(s)|}$ can be computed concurrently with the policy's learning process.
• For large graphs, fragment-based generation is highly likely to be employed. In such cases, we can utilize an approximate correction formula, as outlined in the paper.

In conclusion, the computational overhead of computing automorphism in practice is minor relative to computation of the entire pipeline.

We hope this addresses your concerns.

Thanks for your valuable feedback and suggestions!

Evaluation

On Evaluation

To clarify, in Figure 3 (the results of the toy experiment), we computed state probabilities by enumerating all possible trajectories, rather than using Equation 3. This approach was feasible because we constrained the problem size, making the exact computation of state probabilities tractable. Additionally, we took advantage of the many overlapping sub-trajectories, which allowed us to eliminate redundant computations.

On goodness-of-fit, diversity, and rewards

The purpose of the metrics presented in Table 1 is to show the effects of the correction on downstream tasks, specifically in discovering diverse molecules and high-reward molecules, rather than to demonstrate the goodness-of-fit of the proposed method. To assess the goodness-of-fit, we measured Pearson correlation between $\log R(x)$ and $\log P_F(x)$ as shown in Figure 4. Estimating $\log P_F(x)$ was possible without enumeration using empirical approximation we proposed in Equation 3. Although we understand that Pearson correlation is not a perfect measure as it is scale-invariant, it is considered as a good proxy in practice. While we appreciate your suggestion regarding the FCS metric, we are not entirely certain about its implementation, as the code is unavailable. Since the FCS metric requires estimating the marginal distribution over terminal states, we believe it could be used with our proposed estimation method in the future. We would be more than happy to use FCS if once the code becomes available.

Experiments

Unlike other papers on GFlowNets, the purpose of our paper is not to simply improve the performance of GFlowNets. Rather, the work is focused on identifying the critical bias present in previous work of GFlowNets. That said, we are willing to include more experimental results in revised paper, including illustrative experiments using uniform target.

We excluded the result of uniform target from the paper because the Pearson correlation cannot be computed (as the uniform target has zero variance). However, we are happy to include it in the revised version. The plots are very similar to Figure 3, however, the result based on the number of rings.

Technical contribution

We emphasize that seemingly simple findings often have the potential to be highly impactful. We would like to highlight that our work is the first work to theoretically address the "equivalent action problem," which is particularly critical when using GFlowNets to model target distributions. This problem, previously overlooked, fundamentally affects the correctness of the sampling distribution in GFlowNets.

Beyond correcting this issue, our findings propose a new method to estimate model likelihood, which has significant implications for various graph-related tasks. Moreover, our formulation, which explicitly distinguishes between states and graphs, provides a fresh perspective that we believe can offer valuable insights into other graph-centric applications.

Additionally, as discussed in Appendix D, we briefly outline how our findings can be extended to improve methods that incorporate "node ordering" as a variable. This demonstrates that the implications of our work extend beyond GFlowNets and can influence a broader range of methodologies. We hope these contributions underscore the novelty and potential impact of our research.

Computational Cost

While computing the exact $|\text{Aut}(s)|$ has inherent complexity, as discussed in the paper, this complexity is unavoidable for exact computation. However, irrespective of the computational cost, fixing the sampling bias due to the ignorance of equivalent actions is a fundamental issue that needs to be resolved. This correction introduces an inherent computational cost, but it is necessary to maintain the consistency of sampling. In practice, fast heuristic algorithms often perform well, particularly for relatively smaller graphs, and significantly reduce the computational overhead associated with calculating $|\text{Aut}(s)|$.

Furthermore, when compared to the cost of sampling trajectories, which involves multiple forward passes through a neural network, the compute time for $|\text{Aut}(s)|$ remains still negligible. Also it is important to note that our proposed method requires computing automorphisms only once per trajectory. To address your comment, we provide additional experimental results measuring the compute, as shown below. Note that the scale of the experiments in our paper corresponds to QM9 and ZINC250k.

---

---

*Large: the largest molecules in PubChem, data retrieved from https://github.com/danielflamshep/genmoltasks. This data is used in the paper “Language models can learn complex molecular distributions.”

**Experiments were conducted on an Apple M1 processor.

---

For comparison, we report the speed of molecular parsing algorithms measured using ZINC250k: 0.06 ms ± 0.70 (SMILES → molecule) and 0.04 ms ± 0.05 (molecule → SMILES). The combination of two parsing steps is often used to check the validity of a given molecule in various prior works. In words, computing $|\text{Aut}(s)|$ is in an order of magnitude faster than validity checking algorithm. Even if we compute automorphisms for all intermediate states, this amounts to less than 20x increase for small molecules, which is less than a millisecond.

We used the bliss algorithm in our paper. It is easy to use as it is included in the igraph package and is fast enough for our purposes. For large molecules, we can still count automorphisms in few milliseconds using the nauty package as can be seen in the table. We observed that the pynauty package does not natively support distinguishing between different edge types, requiring us to transform the input graphs by attaching virtual nodes to handle this limitation. The reported time in the table reflects these preprocessing steps.

While we believe the compute time is already minimal considering current applications, we provide two more recipes to even further improve the run time.

• Data processing tasks can be easily parallelized across multiple CPUs. Since GFlowNet is an off-policy algorithm, $|\text{Aut}(s)|$ can be computed concurrently with the policy's learning process.
• For large graphs, fragment-based generation is highly likely to be employed. In such cases, we can utilize an approximate correction formula, as outlined in the paper.

In conclusion, the computational overhead of computing automorphism in practice be minor relative to computation of the entire pipeline.

Dear Dr. Emmanuel Bengio,

Thank you for bringing this to our attention and for your constructive feedback. We sincerely appreciate the opportunity to clarify and address this oversight.

First, we regret that we were unaware of NeurIPS 2023 AI for Science Workshop paper, "Baking Symmetry into GFlowNets." Your work on addressing isomorphic (or "equivalent") actions and integrating symmetry considerations into GFlowNets is directly relevant to our research. Had we been aware of your paper, we would have cited and compared it to our work to better position our research within the existing literature.

As you have noted, we utilized the open-source gflownet repository, which we referenced in our paper. While we were aware of the option to correct for “idempotent actions,” we found that the implementation enumerates isomorphic actions by performing several isomorphism tests to identify exact isomorphic actions at each transition (get_idempotent_actions function). As noted in the "Baking Symmetry into GFlowNets" paper and in the comments within the function implementation, while this is one of the straightforward methods for correction, it appears to be slow. We question its scalability for real world scenarios. This led us to the mistaken belief (before your comment) that no prior work addressing this issue existed.

Once again, we appreciate your thoughtful feedback and your acknowledgment of our contributions to the additional formalization and testing. In the remaining time, we will update our paper to include comparisons with your work. Thank you for your understanding and for creating GFlowNet.

We provide additional comparisons, focusing specifically on the runtime.

The table below summarizes the runtime for different configurations of atom-based and fragment-based generation methods. To ensure fairness, we re-run all experiments to disable parallel computation, using single processor and GPU. Training steps were limited to 1,000, with all other settings kept consistent with the original paper. We report (mean ± std) with three runs.

---

---

*Atom: atom-based generation, with rewards given by a proxy trained on QM9 dataset.

**Fragment: fragment-based generation, with rewards given by a proxy that predicts binding energy to the sEH target.

[1] Ma et al., “Baking Symmetry into GFlowNets,” 2024.

---

When no corrections are applied, the fragment-based method is faster due to its shorter trajectories. However, when exact isomorphism tests are introduced, the computational cost increases significantly. Specifically, the fragment-based method with exact isomorphism tests incurs the highest computational cost (385 min), reflecting the impact of handling larger molecules.

On the other hand, our method introduces minimal additional overhead, making it a practical alternative for both atom-based and fragment-based generation tasks, as the differences in runtime are within the standard deviations. Additionally, we used open-source code for the experiments, making only minor changes to the original implementation. Consequently, there is some additional overhead due to the conversion of data types. We believe this overhead could be eliminated if our method were seamlessly integrated into the pipeline.

We hope this provides additional context regarding prior work and our contributions.

Thank you for your interest in our paper and for your insightful question!

Equation (1) is correct, and your reasoning aligns with our findings, assuming that the generation process permits sampling of any graph in $\mathcal{G}$.

For illustration, let us assume that constant rewards are assigned to terminal states, and we start with a fixed number of isolated nodes in the initial state. In this process, we are only allowed to add new edges. Your reasoning suggests that we should scale the reward by a factor of $1 / |[G]|$. For example, if the terminal graph is “①-②-③”, we should divide the final reward by 3, which corresponds to the number of configurations of different adjacency matrices (that corresponds to “①-②-③”, “②-①-③” and “①-③-②”).

In general, the number of different configurations equals $|[G]| = N!/|\mathrm{Aut}(G)|$, so that $1 /|[G]| = |\mathrm{Aut}(G)|/N!$. Since the initial state has $N$ disconnected nodes, we have $|\mathrm{Aut}(G_0)| = N!$, resulting in $1 /|[G]| = |\mathrm{Aut}(G)|/|\mathrm{Aut}(G_0)|$. This is precisely the scaling term we proposed in the paper!

In practice, however, some graphs are not allowed to be sampled by design. For instance, if we sample graphs node-by-node, the next graph after “①-②” will be either “①-②-③” or “③-①-②”, but there is no way to sample “①-③-②”. To sample “①-③-②”, we would need to allow the policy to sample “③” even from the initial state. This would enlarge the action space and effectively treat node IDs as distinct node types.

In this context, even when using graph-level transitions to model flows, we do not "allow individual graphs to represent states" in such a way that each state is reachable from the initial state. However, when computing graph-level transitions, there is a risk of mistakenly treating graphs as states. The purpose of the statement was to explicitly distinguish between states and graphs, and it does not imply vanilla GFlowNets were in fact modeling graphs with node IDs.