Symmetry-Aware GFlowNets
Authors: Hohyun Kim
Seunggeun Lee
Min-hwan Oh
Venue: ICML 2025 poster (2025)
Keywords: GFlowNet
graph generation
molecule optimization
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: This paper analyzes the bias inherent in GFlowNets and proposes a reward-scaling method to address the issue.

Abstract: Generative Flow Networks (GFlowNets) offer a powerful framework for sampling graphs in proportion to their rewards. However, existing approaches suffer from systematic biases due to inaccuracies in state transition probability computations. These biases, rooted in the inherent symmetries of graphs, impact both atom-based and fragment-based generation schemes. To address this challenge, we introduce Symmetry-Aware GFlowNets (SA-GFN), a method that incorporates symmetry corrections into the learning process through reward scaling. By integrating bias correction directly into the reward structure, SA-GFN eliminates the need for explicit state transition computations. Empirical results show that SA-GFN enables unbiased sampling while enhancing diversity and consistently generating high-reward graphs that closely match the target distribution.

Symmetry-Aware GFlowNets
Hohyun Kim Seunggeun Lee' Min-hwan Oh
Abstract
Generative Flow Networks (GFlowNets) offer powerful framework for sampling graphs in pro- portion to their rewards. However, existing ap- proaches suffer from systematic biases due to inaccuracies in state transition probability com- putations. These biases, rooted in the inherent symmetries of graphs, impact both atom-based and fragment-based generation schemes. To ad- dress this challenge, we introduce Symmetry- Aware GFlowNets (SA-GFN), method that in- corporates symmetry corrections into the learning process through reward scaling. By integrating bias correction directly into the reward structure, SA-GFN eliminates the need for explicit state transition computations. Empirical results show that SA-GFN enables unbiased sampling while enhancing diversity and consistently generating high-reward graphs that closely match the target distribution.
G4
G1
G3
G2
Figure 1: Illustration of graph transitions from G₁ to various successor graphs. The blue oval highlights graphs G2 and G3 are isomorphic.
becomes particularly challenging in graph-building envi- ronments due the presence of equivalent actions. These actions that, although different, lead to the same graph structure. For instance, consider Figure where connecting new node (node 4) to either of two existing nodes (nodes or 3) results in isomorphic graphs. Although these actions are distinct, they lead to structurally identical graphs, mean- ing their transition probabilities must be summed. More generally, when multiple actions lead the same state, the transition probability must account for all equivalent actions. This issue, referred to as the equivalent action prob- lem, arises because determining whether two actions result in the same state requires computationally expensive graph isomorphism tests (Ma et al. 2024).
1. Introduction
GFlowNets have emerged as powerful framework for learn- ing generative models capable of sampling complex, compo- sitional objects with probabilities proportional to a given re- ward. Inspired by reinforcement learning (RL), GelowNets generate these objects through sequence of actions that it- eratively modify the structure of the object being built. This approach is particularly well-suited for generating compo- sitional objects, such as graphs, where there are multiple paths for constructing an object. A prominent application of GFlowNets molecule generation, where molecules are sequentially constructed as graphs (Bengio al. 2021 Jain
While GFlowNets were initially popularized for their reward-matching capabilities, experiments conducted by Ma et al. (2024) demonstrate that neglecting to account for equivalent actions can introduce bias into GFlowNets. Our analysis further shows that the bias is systematic: it skews the model toward sampling graphs with fewer symme- tries node-by-node generation while favoring symmetric components in fragment generation. This bias is par- ticularly problematic for tasks such molecular generation, molecules inherently possess natural symmetries. For instance, in the ZINC250K dataset, over 50% of molecules exhibit more than one symmetry, with 18% containing four or more symmetries. Ignoring symmetries results in incor- rect modeling and inaccurate molecular structure generation, ultimately reducing the accuracy of the sampled molecules.
al. 2023a)
However, GelowNet training objectives rely the accurate computation of the transition probability of policy, which
'Graduate School of Data Science, Scoul National University, Scoul, Republic of Korea. Correspondence to: Seunggeun Lee <lec7801 snu.ac.kr3 kr>,, Min-hwan Oh <minoh@ ann.ahhsuu...kr..
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Symmetry-Aware GFlowNets
In this paper, we propose simple yet effective modification to the GFlowNet training objectives to resolve the equivalent action problem. Our method adjusts the reward based on the number of symmetries in a graph. requiring only minimal changes to the existing training algorithms. Additionally, we introduce a new unbiased estimator for the model likelihood. Our key contributions are as follows:
are formalized based on state transitions, where multiple isomorphic graphs can represent the next state.
The work most closely related to ours is Ma et al. (2024). which highlighted the importance of accounting for equiva- lent actions to compute exact transition probabilities. Their approach involved an approximate test using positional en- coding (PE) to detect equivalent actions at each transition. However, the bias in GFlowNets was validated only through experiments on synthetic datasets, without any theoretical analysis. Furthermore, their method relies on approximate tests that must be applied at every transition, making it com- putationally expensive. In contrast, our work provides an exact and efficient solution, requiring corrections only once at the end of trajectories rather than at each transition. This simplification not only reduces computational overhead but also makes our method straightforward to implement. Ad- ditionally, we present comprehensive analysis showing that this bias arises in general settings, affecting both atom- and fragment-based generation schemes, and significantly impacts learning, particularly for highly symmetric graphs. Additional comparisons can be found in Appendix B
We present a rigorous formulation of autoregressive graph generation within the GFlowNet framework, ex- plicitly addressing the equivalent action problem.
We propose a simple yet effective method to address the equivalent action problem. Our approach scales the reward based on the automorphism group of the generated graph, enabling GFlowNets to accurately model and sample from the target distribution. Using similar technique, we also derive an unbiased estimator for the model likelihood.
Through experiments, we validate our theoretical re- sults, and demonstrate the effectiveness of our method in generating diverse and high-reward samples.
3. Preliminaries
2. Related Work
3.1. Graph Theory
Autoregressive graph generation. There are two primary formulations of autoregressive models: one based on ad- jacency matrices and the other based on graph sequences (Chen et al. 202I). Methods based on adjacency matrices
Let G = (V, F)) denote a graph, where V = [fi.....,,,) U. is the set of n vertices, and E' C V x V is the set of edges. For heterogeneous graphs, we also define labeling functions 4n Le, and lg. which map nodes, edges, and graphs to their respective attributes. We denote 9 as the set of all such graphs under consideration. A permutation ι is a bijective mapping defined on the vertex set. We extend the permutation to sets as TTV) (x()) : u E VJ and x x(E) {TT():), (1;)) (1;, 1z) E E}, as well as to the graph as (G) = relabels node indices, it maps to a structurally identical graph. This notion is formalized as graph isomorphism. Definition 3.1 (Isomorphism). Two graphs G (V, E) and G' = (V', E') are isomorphic, denoted G = G', if there exists permutation V - V' such that π (B) E'. For heterogeneous graphs, the permutation must also preserve labels: for every v E V. (v()) = V2, (T(), for every (u, E F,, (e,, = (m()), T (v)), and 1g ig (G))..
(You et al. 2018b Popova et al.) 2019: Liao et al. 2019) are unlikely to suffer from the equivalent action problem because they preserve the node order information generated so far, making each pair of (graph, node order) a unique state. In contrast, equivalent actions arise in methods based on graph sequences (You et al. 2018a] Li al. 2018 Shi et al, 2020). This becomes problematic if method requires state transition probabilities, as in GFlowNets. Chen et al. (2021) suggest that, for graph sequence- based methods, the size of node's orbit is related to the number of equivalent transitions, which inspired our work.
Since any permutation simply
GFlowNets. Several learning objectives have been pro- posed for GFlowNets, including flow matching (Bengio et al. 202T), detailed balance (Bengio et al., 2023), trajec- tory balance (Malkin et al. 2022),, sub-trajectory balance (Madan et al. (023), as well as their variants to improve training efficiency (Pan al. 2023 Shen et al. (202). Re- cently, GFlowNets have been found to be equivalent to maximum entropy reinforcement learning (Tiapkin et al.] 2024| Mohammadpour et al.) 2024), which was previously known to be inadequate for directed acyclic graph (DAG) environments (Bengio et al. 202I). However, none of these objectives can avoid the equivalent action problem, as they
An automorphism is a special case of an isomorphism where the graph is mapped to itself.
Definition 3.2 (Automorphism). An automorphism of graph G = (V, E) is a permutation æ on the vertex set V that preserves the edge set, meaning (B)) = E. If labels are present, they must also be preserved under the permutation. The set of all automorphisms of a graph G is called the automorphism group of G, denoted by Aut(G).
2

---

Symmetry-Aware GFlowNets
In Figure [ graph G₁ has two automorphisms: the identity mapping and one that permutes nodes 2 and 3. We denote the order (or size) of the automorphism group as |Aut(G)), which represents the number of symmetries in the graph.
constraint at the state transition level. The objective is de- fined for each transition (s, 8') as:
LDn(s, = loog F(s)pa()((s) F(5)))A())))
Definition 3.3 (Orbit). The orbit of a node u E V in graph G is defined as Orb(G,u) = {v E V : 3r E AG), a(u)= = v). Similarly, the orbit of am edge (u, v) E E in graph G is defined Orb(G, u, = {(h, k) E E Br E Aul(G), (r(1), (T))) = k)). More generally, the orbit of node set U S V in graph G is defined as Orb(G,U) = {U": 3T E Aut(G), A(U) - U"}.
The DB objective requires learning the state flow function F : + RR, which represents the unnormalized probabil- ity that the policy visits state 8.
4. The Equivalent Action Problem
In this section, we formalize the graph generation process in the context of GFlowNets and investigates its properties.
An orbit is a set of nodes or edges that are structurally identical. In Figure [] the orbit of node 2 in graph Gi is (2. Equivalent actions occur because they act on nodes in the same orbit; since nodes? 2 and 3 are in the same orbit, adding a new node to either one is equivalent. This point will be further discussed in Section
4.1. Problem Definition
Consider a sequential graph generation process (G, E) that constructs graphs by modifying the nodes and edges of existing partial graphs, where & C g x 9 represents the set of transitions between graphs. In this section, we clarify the relationship between the two processes, AS) and (9, E),
3.2. Generative Flow Networks
The generation process of GFlowNets is defined by a finite directed acyclic graph (DAG) AS, where S = {si} is the set of states, and A S S x S is the set of state transitions. Let 80 E S denote the special starting point of the process, called the initial state, with no incoming edges in the transition graph. Let X C S be the set of terminal states, for which rewards are given. From the initial state sp, objects are constructed sequentially by the forward transition policy (-1s) until reaching terminal states. A set of complete trajectories, denoted as T, consists of sequences of transitions 7 = (so,.... ,, .n)) starting from the initial state so and terminating at S, E X, such that (st, $141) E A. Let (s)))) be the probability of reaching by following the policy PA- The goal of GFlowNets is to train policy P.4 that generates objects with a probability proportional to their reward. Specifically, the policy satisfies Pa(x)= = RZ for all x E X, where Z is a normalizing constant. This is achieved by training PA using the following objectives.
Since isomorphism is equivalence relation, it partitions the space G into classes, where each graph in class is structurally identical to the others. Let [G] {G' E G
G' = G} denote the equivalence class of G induced by graph isomorphism. The state space S is defined as the set of equivalence classes of graphs, S = -[G] : G E 9). rather than the graph space G itself. This because our goal in using GFlowNets is to sample any graph within the equivalence class transitions A can also be defined by partitioning the graph transitions & by the following equivalence relation:
[G] in proportion to R(s). State
Definition 4.1 (Transition equivalence), Graph transitions (G,, G and (G2, G32) are causitionn-quivallltiii if G2 s G2 and G = G¹2-
In practice, graph generation process (G, E) is constructed by first designing set of allowable actions in a given graph. For example, AddEdge (G, u, v) adds an edge (u, v) to the existing graph G, and AddNodeeGG u) adds a new node to an existing node u. The Stop(G) terminates the process, in which case the graph- attribute flagged as terminated. Through this construction, graph transitions & are ensured to be structured so that any pair of isomorphic graphs have isomorphic successors.
Trajectory Balance (Malkin al. 2022). The Trajectory Balance (TB) objective is based on the flow consistency constraint at the trajectory level. Given complete trajectory T, the TB objective is defindd as follows:
CTB(T) = log Z IT PA (54411185)) )² R(sn.) IT=o ga(Se(se+1))
In this setup, the state transition probability can be expressed in terms of graph transitions as follows: Let ps denote a forward policy over the graph space, and let E(G) (G': (G, G') f} denote the set of next graphs reachable
It introduces backward policy qA that reverses the process. Given qA, the forward policy P. and the normalizing con- stant Z are trained to match the backward flow induced by the reward function and the backward policy.
from G. If pe is parameterized by permutation-equiiariint network, then
Detailed Balance (Bengio et al. 2023). The Detailed Balance (DB) objective is based on the flow consistency
PA(S'1s)=
Σ Pe(G'GG),
(1)
G'EE(GIns'
3

---

Symmetry-Aware GFlowNets
sition probability PA(s'(s): while pa(s'Is) accounts for all transition-equiialenn actions, Pa(aas) aggregates only over orbit-equivalent actions. Formally, for given graph G. let E(G) denote the set of graph actions available from G. Then, for a state-action pair 8 E S and a E A. the state-action probability is defined as:
for any G 8, where E(G) n 8' is the set of next graphs that are in the same equivalence class s' (see Appendix F.I for the derivation). This is an exact formula for computing state transition probabilities, which we use as reference for comparison. However, it requires looking one step ahead and comparing the resulting graphs to identify {G) n s'. This process involves multiple computationally expensive graph isomorphism tests for each transition.
Pa(als)=
E Pe(e|G) EEE(G)no
(2)
As an alternative, Ma et al. (2024) suggested using orbits to identify transition
where pe(elG) denotes Pe(G"IG) for G' being the next graph. Here, { Na represents the set of orbit-equivalent actions from G. By Theorem 4.3 it follows that p.((ass) S PA [s) in general.
actions, which we formalize next. Define graph actions as triples, = {(G, t, u)}, where t denotes the action type and u specifies the nodes or edges affected by the action. Since graph transitions E are constructed by predefined set of graph actions, there is one-to-one correspondence between & and E. However, explicitly distinguish between them to introduce another equivalence relation.
Computing exact state transition probabilities includes ex- pensive graph isomorphism tests as stated. Instead. Ma et al. (024)) proposed using Equation (2). observing that PA 8) = PA(s'(s) )) in most cases. However, computing or- bits for every transition remains computationally intensive, which led them develop approximate solutions. In the next section, present an exact and efficient solution to address this challenge.
Definition 4.2 (Orbit equivalence). Graph actions (G1, t1, u1) and (G2, t2, u2) are orbit-equivalett if t1 = to and there exists a permutation и such that x (G1) G2 and (ui)) u2- When G = G2, orbit equivalence indicates that 11 and U2 belong to the same orbit.
4.2. Properties of Equivalent Actions
In Figure T the transitions (G1, G2) and (G1, Ga) are transition- -quivalon because the resulting graphs are iso- morphic, G2 G3. These transitions are induced by the actions A 2) and AddNode (G1, 3). which are orbit-equivalent since nodes 2 and 3 belong the same orbit in graph G1. Similarly to A, which is induced by transition equivalence relation, we define À as the set of equivalence classes induced by the orbit equivalence relation on E. The notion of orbit equivalence is particularly useful because serves as a replacement for transition equivalence. The next theorem establishes that orbit-equivalent actions induce equivalent transitions.
In fact, accounting for orbit equivalence is sufficient for GFlowNets, as demonstrated by the following theorem.
Theorem 4.4 (Sufficiency of orbit equivalence). Let qı denote the backward state-action policy. State-action flow constraints are defined as F(s)P = (asass'(")ss) If state-action flow constraints are satisfied for all possible state action pairs, then the state transition flow constraints, F (())pu(s'(s) = ((ss))a(ssss)) are also satisfied.
GFlowNets are typically formulated such that each pair of states are connected at most once in a DAG (S, A),, ensuring that every action leads to a unique next state. In contrast, in (), distinct actions can lead to the same next state. This can be interpreted as multiple pathways connecting the same pair of states, enabling parallel flows. Theorem 4.4 essentially states that edge flows can be subdivided into multiple flows within a transition.
Theorem 4.3. Let (G1, t1. u1, G)) and (G2, 12, u2, G%) be two graph transitions induced by actions Ei = (G1, ) and e2 = (Gz, t2, Uz). If en and e2 are orbit equivalev,,,nn,, then (G1, G2) and (G2, Gl)) are transition eeuitillnne
In other words, graph actions operating on the same orbit lead to isomorphic graphs. This is because orbits, rather than individual nodes or edges, are structurally important in determining actions. The theorem implies that, in a given graph G, transition-equivalent to isomorphic graphs- be identified by computing or- bits. However, transition-equivalent actions are not always orbit-equivalent (see Appendix (D), meaning that the orbit equivalence relation provides finer partition of & than the transition equivalence.
Our next goal is to simplify the computation of state-action probabilities. First note that (ala)) can simply be ex- pressed as:
that lead
(((])))|((G)nd))
where (E(G) O al represents the number of orbit-equivalent actions. This is because when actions are parameterized us- ing graph neural networks (GNNs), orbit-cquivalent actions are assigned equal probabilities. In general, permutation- equivariant functions produce identical representations for nodes within the same orbit (as detailed in Appendix E.
Given the distinction between transition-equivaat actions A and orbit-equivalent actions A, we define the state- action probability (a(a)s) differently from the state tran-
4

---

Symmelry-Aware GelowNets
Aut(C 2
Aut(G2) =
[Aut =
G1
G2
G3
Figure 2: Graphs representing transitions (G1, G2, G3), where the first transition is performed by AddNode and the second by AddEdge. The number of forward/backward actions represented as the number of arrows. Symmetries in each graph is related to orbit-cquivalent actions, seen in the ratio [Aut(G))// (ltt)()) |Orb(G,, o)l///rr((22,0)) Nodes in the same orbit are given the same color.
When node representations aggregated to compute edge representations using invariant aggregators such as SUM or MEAN, edges within the same orbit also receive identi- cal representations. Alternative parameterizations, such as the relative edge parameterization proposed by Shen et al. (2023), also assign equal probabilities to orbit-equivalent actions, while enhancing representational power.
The theorem suggests a simple adjustment method when considering the ratio. This simplification leads to the straightforward reward-scaling method presented the next section.
5. Symmetry-Aware GFlowNets
Note that the number of orbit-equivalent actions, (E( Na), corresponds to the size of the orbit of the associated nodes or edges. The following lemma shows that, when consid- ering ratios, counting orbit-equivalent actions simplifies to counting automorphisms.
In this section, we analyze GFlowNet objectives using our previous results. The following theorem shows that a naive implementation of the TB objective, which does not account for equivalent actions, will train model biased toward graphs with fewer symmetries.
Lemma 4.5. Let G' G[E U (u, v)] be graph induced by adding an edge (u, v) to graph G. Then, the following relationship holds:
Corollary 5.1 (TB correction). Assume that Go is the empty graph or a single node, so that [Aut(Go)] = 1. Given the complete graph trajectory T = (Gu, GI...., Gn), con- structed using a node-by-node generation scheme, the tra- jectory balance loss given by:
OOrb(G, w))
[At((G)
Orb(GG,, u. e)
(G'l
We presented Lemma 4.5 in the context of AddEdge for simplicity, but similar lemma holds for other action types such as AddNode, AddNodeeAtributtes and others used in node-by-node generation (See Appendix C for the full list of considered actions). We also consider AddF ragment in our experiments, but discuss its proper- ties separately in Appendix H as the corresponding formula differs in fragment-based schemes.
LTB(T) (108
2 2I Pe G.) Aut (G (G,)) IIFi (Ge
The equation follows from Theorem 4.6 and the application of a telescoping sum.
Implication. Corollary 5.1 shows that we need to multiply the reward by the order of the automorphism group of the terminal state to properly account for equivalent actions. If we do not scale the reward, we are effectively reducing the rewards for highly symmetric graphs by a factor of //,))l As result, even if model is fully trained, the likelihood of reaching the terminal state will not align with the desired distribution; instead, the model is penalized for generating symmetric graphs, following P. ((,,)) x This bias can be easily corrected by evaluating (Aul(G..) and scaling the reward accordingly.
In Figure we observe that the number of equivalent ac- tions changes as the graph evolves. For instance, from G there is only one forward equivalent action, while from G2. there three. The number of backward actions also varies with each transition, making it seem daunting to account for all equivalent actions step-by-step. However, the ratio of forward and backward orbit-equivalent actions can be sim- ply expressed as the ratio of the sizes of their automorphism groups. This the basis for the next theorem.
Theorem 4.6 (Automorphism correction). Let qe denote graph-level policy defined for the buckward process. Let (G, G') be the graph transition, and (s, a, s's responding state transition. If permutationn-qqui equivariant func- tions are used for pe and yg, then the following holds:
We can also adjust the DB objective by multiplying the sym- metry ratio (aat(G"))Aut(((( for each transition, though this requires multiple evaluations of automorphisms per trajectory. The next theorem states that, as in the TB correction, we can simply scale the rewards by (AutGG) without needing to count automorphisms at each transition.
the backward probability
3 denote cor-
Pa(als) [Aut(G)
G))
(,((ass) [
qE (G
5

---

Symmetry-Aware GelowNets
Theorem 5.2 (DB correction). Consider a node-by-node graph generation scheme. We define the graph-level detailed balance condition, opposed to the standard state-level condition, as follows:
Pe [Aut(G,) (l (T|
PA(x) = Er Gn)
(4)
M
(T
F(G)pe(G'GG) F(G)) (GEG))
qe (Ta
If we do not account for equivalent actions during both train- ing and model likelihood estimation, the estimated model likelihood may still correlate with the rewards, but the actual sampling distribution will be biased. This happens because the policy is already biased towards generating samples with low |At((G,) leading to spurious correlation.
where denotes the graph-level flow function. If rewards are given by R(G) = (G) R(G) and the graph-level detailed balance condition is satisfied for all transitions, then the forward policy samples terminal states proportion- ally the given reward R.
Implication. Together with Corollary 5.1 we see that scaling the reward alone is sufficient for both TB and DB objectives. This suggests that other GelowNet objectives, such as subtrajectory balance (Madan al. 2023 and flow-matching (Bengio al., ). also be used with reward scaling (see the discussion on the flow-matching Appendix G). This provides a straightforward approach to implementing GelowNet objectives while reducing the computational burden of counting automorphisms at each transition.
Impact of GNN expressive power. Another source of inexact learning comes from the limited expressive power of GNNs used to parameterize the policy (Silva et al. 2025). The correction formula relies on the parameter-sharing prop- erty of GNNs for nodes within the same orbit. While this property desirable, actions from different orbits may also collapse into identical representations, thereby reducing the network's 's representational power. As result, the policy might assign equal probabilities to actions that lead to dif- ferent rewards. Although this issue is not the primary focus of this paper, we provide additional analysis of its impact in Appendix E.2
Finally, provide the adjustment formula for fragment- based generation and defer the detailed discussion to Ap- pendix H
The main additional computation for re- ward scaling comes from evaluating |Aut (G)), (G)) which is nec- essary for each trajectory in both the TB and DB objectives. For fragment correction, we can pre-compute |Aut (C') in our vocabulary set. While the fastest proven time complexity for computing [Aut(G)] has remained exp(O((/) log n)) for decades (Babai et al., 1983). graphs with bounded de- grees can be handled in polynomial time (Luks) 1982). In our experiments, used the bliss algorithm (Junttila & Kaski 2007), included in the igraph package (Csardi & Nepusz 2006). and did not observe any significant delays in computation. In contrast, computing transition equiva- lent actions and summing their probabilities at each step involves several graph isomorphism tests. This process re- quires K Il more computations compared to the reward scaling, where K is the average number of actions per state, and H is the average trajectory length. We provide further analysis and comparisons on the computation time for each method in Appendix []
Computation.
Theorem 5.3 (Fragment correction). Let G represents ter- minal state ([G) E X) generated by connecting ls fragments (C1...., Cx Then, the scaled rewards to offset the effects of equivalent actions are given by:
(R)())
R(G) = IT AAt(CC))
(3)
Intuitively, highly symmetric fragments contain many sym- metric nodes available for connection, resulting in multiple forward equivalent actions, even though these actions do not lead to distinct outcomes, As a result, without correc- tion, symmetric fragments are more likely to be sampled by the model. Equation (3) corrects this bias by penalizing symmetric fragments.
Estimating model likelihood. To address the intractabil- ity of marginalizing over all trajectories terminating at E X. /Zhang al. (2022) proposed approximating the
Relation to distribution learning While our work fo- cuses on improving the reward-matching capabilities of GFlowNets, many graph generation methods instead aim to leam the data distribution by maximizing variational lower bound (VLB):
model likelihood using importance sampling with qe
variational distribution: (a(=)= EE-gge (r(G.) qe (r (.,)**
pe (T)
where 7 = (Go...., G.). However, Zhang et al. (2022) worked with a restricted class of decision process where the equivalent action problem is not present. Instead, we estimate the probability of the terminal state follows:
log 2 Erag(T x) [logPA(T) log g(//)))
(5)
6

---

Symmelry-Aware GFlowNets
corrects this bias by multiplying the rewards by 1/|a]]
Here, ((T]a)) is variational distribution that samples trajec- tories T = (50....,, S, = z) conditioned on the final state There are two primary ways to parameterize q and sample trajectories T: (1) can be implemented as a backward pol- icy ((51( ). as in GFlowNets; (2) q( (x)) can first sample a node or edge ordering T, which then deterministically defines trajectory т. Our method suggest that when the backward policy is used define q(sr(st=1). the VLB can be computed via automorphism counting. In contrast, when ((</x)) is used to sample orderings, no further correction is required. This is because forward equivalent actions split probabilities across different orderings that induce the same trajectory. Since this result differs from that of Chen et al. (202T), we elaborate on this point Appendix !] where we interpret equivalent actions as those that correspond to different orderings but ultimately lead to the same state sequence.
We trained three policies using the TB objective and com- puted the exact terminating probabilities for all states ((\') 112). As shown in Figure [3 (a). the terminating probabili- ties of the vanilla model are clustered according to |æ]|- In contrast, when state transition probabilities p.a (5'11 [s) are computed exactly by summing over transition- -euiiiileeeivvvenntt actions, the terminating probabilities are uniform as desired. Notably, Reward Scaling achieves the same effect, validat- ing Theorem 4.4 The PE method exhibits approximate bias correction, as indicated by the scatter in its results.
Upon inspecting the trained normalizing constant, we ob- served that with Reward Scaling, the estimated Z is 112, matching the true value. Without correction, however, Z is trained be significantly larger, reaching 26706. This discrepancy arises because, in this example, the correction works by scaling down the rewards by 1 1/|ar] Alternatively, since the 6! term in |x|] is constant, it can be absorbed into the normalizing constant Z. Therefore, the rewards could instead be scaled up by |Aut(z) to achieve the same effect.
6. Experiments
In this section, we conduct experiments to validate our the- oretical results and demonstrate the effectiveness of our method. We use uniform backward policy across all ex- periments. Details on hyperparameters and model contig- urations can be found in Appendix K The experiments compare the following methods: (1) Vanilla GFlowNets, which do not incorporate graph symmetries. (2) Transition Correction, which identifies transition -qquivllene actions by performing multiple isomorphism tests and sums their probabilities accordingly. (3) PE, the method proposed by Ma et al.) ) which approximately identifies orbit- equivalent actions using positional encoding. (4) Reward Scaling, which achieves correction by modifying only the reward signals. (5) Flow Scaling, which multiplies sym- metry ratio (Gt((")/ to backward probability at each transition. Note that methods 3-5 are orbit correction methods. Since Reward Scaling and Flow Scaling have the same effect under the TB objective, we only consider Flow Scaling when using the DB objective
6.2. Synthetic Graphs
Following Ma et al. (2024), we set up a graph-building environment where nodes can be one of two types, and graphs can contain up to 7 nodes (I.²) = 72296). Rewards are assigned based on the number of 4-cliques that contain at least three nodes of the same type. For this relatively small environment, we compute exact terminating probabilities for all states without approximations for evaluation.
The results for the TB objective are presented in Figure (b). The vanilla GFlowNet exhibits limited performance, as measured by L1 errors between the target probabilities and the model's terminating probabilities. In contrast, our method (Reward Scaling) has substantially lower errors, producing results similar to those obtained by explicitly computing state transition probabilities at each step (Transi- tion Correction). Although the PE method is an approximate solution and underperforms compared to ours, still signif- icantly outperforms the vanilla baseline, underscoring the importance of applying correction.
6.1. Illustrative Example
We first conducted illustrative experiment where the initial state consisted of six disconnected nodes, and only AddEdge and Stop actions were allowed. Terminal states correspond to connected graphs, with a uniform reward of assigned to each. Theorem 4. prediess that the terminating probability of the vanilla GFlowNet will exhibit a bias pro- portional to
For the DB objective shown in Figure (c), we observe that Reward Scaling requires more training steps to converge than other correction methods. This is because the Reward Scaling corrects only at the end of trajectories, leaving inter- mediate probabilities remain inaccurate. This hinders train- ing under the DB objective, which relies on intermediate probabilities. On the other hand, the per-transition correc- tion can be interpreted providing intermediate signals for the adjustment, similar to the idea of providing intermediate reward signals, as suggested by Pan et al. (2023). Reward Scaling achieves the same goal, but defers the adjustment
where |Aut(Go] = 6!. This corresponds to the number of graphs isomorphic to the terminal state x, meaning (1) |z]. Our method
'Souree code available at: https: /ttp//gttbbbbb///// com/
bohyun312/5am sagin
7

---

Symmelry-Aware GFlowNets
Vandla
Vanila
Verille
Enror in Modtel Log Liooshoood
Temiratin Protability
Correction
2024)
Trenslion Correction
PE 2024]
32-
ut 2024)
Cornection
x2-
Reward Scaling (Ours]
Reward Scaling (Ours)
Reward Scaling (Ours)
C3-
Flow Scalin (Ours)
Random
(9)
Traincd I5)
2.33
U0c
24 Number of Model Updatess
10
20
Stato Indox
Number of Modal Updates
Number of Sample Trajectories IM)
(a) Illustrative
(b) Synthetic (TB)
(c) Synthetic (DB)
(d) Likelihood estimation
Figure 3: (a) Terminating probabilities of trained models in the uniform-rewart environment. States are sorted according to the number of graphs in the state, |z]. (b), (c) L1 errors between the target probabilities and the model's terminating probabilities during training in the synthetic environment. (d) Errors in the estimated model log- big-liielihodd, defined as the difference between estimated and exact log-likelihood. "Random" denotes the errors of an initial random model, while "Trained" refers that of a trained model. Numbers in brackets indicate the number of edges in the terminal states used for estimation.
signal to the end of the trajectory.
wards are determined by proxy model that predicts the binding energy of a molecule to the sEH target.
To evaluate the effectiveness of the proposed model likeli- hood estimator, we sampled 100 terminal states for each cat- egory (5, 9, and 12 edges), resulting total of 300 states, and estimated their model likelihood using Equation ( The Figure (d) displays the estimation errors (computed as estimates minus exact values) for each category, with shaded bands representing one standard deviation. The esti- mates converge to the exact likelihood as M increases, with notably rapid convergence for small values of M.
For the atom-based task, we simply scale the final rewards by the order of the automorphism group. For the fragment- based task, we additionally correct for fragment automor- phisms described in Equation (3). We also explore an approximate correction scheme that offers computational benefits, as detailed in Appendix K.4 We sampled 5,000 molecules from each method and evaluated them using com- mon metries. The definitions of these metrics are provided in Appendix
However, the estimation error varies significantly depending on the task. For instance, terminal states with 5 edges can be estimated more accurately than those with 12 edges, 12-edge states have substantially more trajectories leading to them in this environment, making the estimation problem more challenging. Additionally, a trained model's 's likelihood can be estimated more accurately than that of a random policy; fact, for fully trained model, a single sampled trajectory would be sufficient for an accurate estimation.
0.85
0.80
Pearson Correlation
0.75
Vanilla
6.3. Molecule Generation
Reward Scaling (Approx.)
Reward Scaling (Exact)
Task description. We investigate whether accurately mod- eling given target distribution helps generate diverse and high-reward samples in practice. We examine the atom-
0.60
10
14
18
26
30
Number of Model Updates
x10>
based generation task from Jain et al. (2023b) and the fragment-based generation task from Bengio et al. (202T). In the atom-based task, the goal is to generate molecules by sequentially adding new atoms, edges, or setting their attributes. Rewards are provided by proxy model, which task,
Figure 4: Correlations between log rewards and model log- likelihoods during training in fragment experiment.
Results. The results summarized Table show that ac- curately modeling the target distribution yields generally the better results in terms of generating diverse and high- reward samples for both molecule tasks. This result is note- worthy, as the vanilla model effectively optimizes for two objectives- the proxy and non-symmetries- which could enhance diversity. However, atom-based task exhibited lim- ited improvement, possibly due to the reward structure of the task, where rewards are negatively correlated with the
predicts the HOMO-LUMO gap. In the fragment- we use predefined set of fragments, each with predefined set of attachment points-nodes on the fragment where edges can connect. The task involves building a tree graph, where each node represents a fragment, and edges specify the attachment points on the two connected fragments. Re-
8

---

Symmetry-Aware GFlowNets
Table I: Results for molecule generation task. Highest scores are highlighted.
Task
Method
Diversity
Top K div.
Top K reward
Div. Top K
Uniq. Frac.
Vanilla
0.929 =0.024
0.077
1.09
1.09
0.93
Atom
Reward Scaling (Exact)
0.959 10.01
0.046
1.091 10.013
1.09110.0
1.0100
Vanilla
0.877 10.001
0.153 1 100003
0.941 10.002
0.941 10.002
1. 1.0100
Fragment
Reward Scaling (Approx.)
0.88
0. +0.008
0.949
0.949
1.040.
Reward Scaling (Exact)
0.879
0.15 20.002
0.952
0.952
1.0
number of symmetries when measured in the QM9 test set.
the reward structure of the given task.
For the fragment-based task, the sampled molecules show higher rewards with our method. We also observe that the approximate correction already enables the generation of high-reward samples, underscoring the effectiveness and importance of the correction. Without correction, the trained model tends to excessively favor components that incur multiple forward equivalent actions during genera- tion. For example, among 5000 sampled molecules, the vanilla GFlowNet produced 5220 instances of cyclohex- ane (C1 CCCCC1) as its fragments, whereas the corrected method produced only 1042.
While our method is general and applicable to both node- by-node and fragment-based generation schemes, our theo- retical guarantees rely on a specific set of predefined graph actions. Therefore, when designing a new set of graph ac- tions, is important to ensure that they share a similar struc- ture, so that the theorems remain applicable. In most cases, however, the graph actions introduced can be readily extended to incorporate additional actions. See Appendix C for further discussion.
A potential limitation of this paper is that the proposed correction method demonstrated primarily on specific objectives (TB and DB) and datasets relevant to molecule discovery. Future work could explore applying the method to tasks with different symmetry patterns and reward struc- tures.
In addition, we measured the Pearson correlation between the estimated model log- lieliii,,,,,,, log (xr), and the log rewards, log R(z), on the test set to validate the proposed fragment correction method. Figure 4 shows an overall high correlation for both exact and approximate corrections, emphasizing the impact of our methods.
A Acknowledgements
7. Discussion and Conclusion
This work was supported by the National Research Foun- dation of Korea (NRF) grant funded by the Korea gov- ernment (MSIT) (No. RS-2022-NR071853 and RS-2023- 00222663), the Global-LAMP Program of the NRF grant funded by the Ministry of Education (No. RS-2023- 00301976), Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RSS-025500226772 Brain Pool Plus (BP+, Brain Pool+) Program through the Na- tional Research Foundation of Korea (NRF) funded by the Ministry of Science and ICT D3A2A0D 100666), Korea Government Grant Program for Education and Re- search in Medical AI through the Korea Health Industry De- velopment Institude (KHIDI) funded by the Korea govern- ment (MOE, MOHW), and AI-Bio Research Grant through Seoul National University.
GFlowNets were first proposed as alternative to previous methods, such as MaxEnt RL (Haarnoja et al. 2017), which are biased toward states with multiple action sequences lead- ing to them. However, incorrect modeling of state transition probabilities introduces another type of bias in graph gener- ation. Although we believe that the previous experimental results remain valid if interpreted carefully with the problem in mind, we recommend being explicit about the correction method used in all future work.
In this paper, we analyzed the properties of equivalent ac- tions and proposed simple correction method that allows for unbiased sampling from the target distribution. Our anal- ysis shows that, without correction, highly symmetric graphs are less likely to be sampled, while symmetric fragments more likely be sampled, which is crucial for molecule discovery. We demonstrated that the reward-scaling tech- nique works for both TB and DB objectives. Experimental results suggest that reward scaling and flow scaling effec- tively removes bias, allowing for accurate modeling of the target distribution, which is essential for sampling high- reward molecules. The exact effect, however, depends on
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

---

Symmelry-Aware GFlowNets
References
Li, Y., Vinyals, O., Dyer, C., Pascanu, R., and Battaglia, P. Learning deep generative models of graphs. arXiv preprint arXiv: 03324,, 2018.
Babai, L., Kantor, W. M., and Luks, E. M. Computational complexity and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science (Sfcs 1983), pp. 162-171 IEEE, 1983.
Liao, R., Li, Y., Song. Y., Wang, S., Hamilton, W., Du- venaud, D. K., Urtasun, R., and Zemel, R. Efficient graph generation with graph recurrent attention networks. Advances in neural information processing systems, 32, 2019.
Bengio, E., Jain, M., Korablyov, M., Precup. D., and Ben- gio, Y. Flow network based generative models for non- iterative diverse candidate generation. Advances in Neu- ral Information Processing Systems, 34:27381-27394, 2021.
Luks, E. M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of computer and system sciences, 25(1):42-65, 1982.
Bengio, Y., Lahlou, S., Deleu, T., Hu, E. J., Tiwari, M., and Bengio, E. Gflownet foundations. Journal of Machine Learning Research, 24(210):155,2005
Ma, G., Bengio, E., Bengio, Y., and Zhang, D. Baking sym- metry into gflownets. arXiv preprint arXiv: 05446, 2024.
Chen, X., Han, X., Hu, J., Ruiz, F. J., and Liu, L. Order mat- ters: Probabilistic modeling of node sequence for graph generation. arXiv preprint arXiv:2106 206.06666.) 2021.
Madan, K., Rector-Brooks, J., Korablyov, M., Bengio, E., Jain, M., Nica, A. C., Bosc, T., Bengio, Y., and Malkin, N. Learning gflownets from partial episodes for improved convergence and stability. In International Conference on Machine Learning, pp. 23467-23433 PMLR, 2023.
Csardi, G. and Nepusz, T. The igraph software package for complex network research. InterJournal, Complex Systems: 1695, 2006. URL https: httggrgapp...o org
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learnable structural and positional representations, arXiv preprint arXiv:2110.0787., 2021.
Malkin, N., Jain, M., Bengio, E., Sun, C., and Bengio, Y. Trajectory balance: Improved credit assignment in gflownets. Advances in Neural Information Processing Systems, 55:5955-5967, 2022.
Flam-Shepherd, D., Zhu, K., and Aspuru-Guzik, A. Lan- guage models can learn complex molecular distributions. Nature Communications, 13(1):3293, 2022.
McKay, B. D. and Piperno, A. Nauty and traces user's s guide (version 2.5). Computer Science Department, Australian National University, Canberra, Australia, 2013.
Haarojja, T., Tang, H., Abbeel, P., and Levine, S. Rein- forcement learning with deep energy-based policies. In International conference on machine learning, pp. 1352- 1361. PMLR, 2017
Mohammadpour, S., Bengio, E., Frejinger, E., and Bacon, P.-L. Maximum entropy gflownets with soft q-learning. International Conference on Artificial Intelligence and Statistics, pp. 2593-2601. PMLR, 2024.
Jain, M., Deleu, T., Hartford, J., Liu, C.-H., Hernandez- Garcia, A., and Bengio, Y. Gflownets for ai-driven scien- tific discovery. Digital Discovery, 2(3):557-577, 2023a.
Pan, L., Malkin, N., Zhang, D., and Bengio, Y. Better training of gflownets with local credit and incomplete trajectories. In International Conference on Machine Learning, pp. 26878-268899 26890. PMLR, 2023.
Jain, M., Raparthy, S. C., Hernández- Hernandez-Garcia, Garcia, A., Rector- Brooks, J., Bengio, Y., Miret, S., and Bengio, Multi- objective gflownets. In International conference on ma- chine learning, pp. 14631-14653 PMLR, 2023b.
Paszke, A., Gross, S., Massa, F,, Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., De Vito. Z.,, Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, I., Bai, J.,, and Chintala, S. Pytorch: An imperative style, high- highhpeeformance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL http://
Junttila, T. and Kaski, P. Engineering an efficient canonical labeling tool for large and sparse graphs. In 2007 Proceed- ings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 135-149. SIAM, 2007.
Kingma, D. P. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1e.. 69800 2014.
papers. pppprrs.nerrrpescccc/pppr//////3 an snr-neerative-stylee-iiie hirrorraaaepe dee--earniig-libraayy.
Kong, L., Cui, J., Sun, H., Zhuang, Y., Prakash, B. A., and Zhang, C. Autoregressive diffusion model for graph gen- eration. In International conference on machine learning, pp. 17391-17408. PMLR, 2023.
Popova, M., Shvets, M., Oliva, J., and Isayev, O. Molecular- mn: Generating realistic molecular graphs with optimized properties. arXiv preprint arXiv: /3372, 2019.
10

---

Symmetry-Aware GelowNets
Rampášek, L., Galkin, M., Dwivedi, V. Lou, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, seal- able graph transformer. Advances in Neural Information Processing Systems, 35:14501-14515, 2022.
Shen, M. W. Bengio, E., Hajiramezanali, E., Loukas, A., Cho, K., and Biancalani, T. Towards understanding and improving gilownet training. In International Conference on Machine Learning, pp.
PMLR, 2023.
Shi, C., Xu, M., Zhu, Z., Zhang, W. Zhang, M., and Tang, Graphaf: flow-based autoregressive model for molec- ular graph generation. arXiv preprint arXiv:2001.09382 2020.
Silva, T., Alves, R. B., da Silva, E. d. S., Souza, H., Garg, V., Kaski, S., and Mesquita, D. When do gflownets learn the right distribution? In The Thirteenth International Conference on Learning Representations, 2025.
Tiapkin, D., Morozov, N., Naumov, A., and Vetrov, D. Generative flow networks as entropy-regularized rl. In International Conference Artificial Intelligence and Statistics, pp. 4213-4221, PMLR, 2024.
Wang. Z., Shi, J., Heess, N., Gretton, A., and Titsias, M. K. Learning-orde autoregressive models with ap- plication molecular graph generation. arXiv preprint arXiv:2503.05977 2025.
Xu, K., Hu, W. Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv preprint arXiv: 18/0. 00.06.000006...... 2018.
You, J., Liu, B., Ying, Z., Pande, V., and Leskovec, J. Graph convolutional policy network for goal-directed molecu- lar graph generation. Advances neural information processing systems, 31, 2018a.
You, J., Ying, R., Ren, X., Hamilton, W., and Leskovec, Graphrnn: Generating realistic graphs with deep auto- regressive models. In International conference on ma- chine learning, pp. 5708-5717, PMLR, 2018b.
Yun, S., Jeong, M., Kim, R., Kang, J., and Kim, H. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
Zhang, D., Malkin, N., Liu, Z., Volokhova, A., Courville, A., and Bengio, Y. Generative flow networks for discrete probabilistic modeling. International Conference on Machine Learning, pp. 12412-26428... PMLR, 2022.
Zhang, M., Li, P., Xia, Y., Wang, K., and Jin, L. Label- ing trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-9073 2021.

---

Symmetry-Aware GelowNets
A. Notations
Table 2: Notation
Set of graphs
Set of graph transitions
3
Set of graph actions
Set vertices
V
Set edges
E
Node labeling function
h
Edge labeling function
le
Graph labeling function
lg
Permutation
Graph
Set of automorphisms of graph G Set graphs isomorphic to graph G Orbit of a node Stabilizer of node u Forward policy Backward policy over graphs Set of next graphs from graph G Set of actions from graph G Graph-action probability
Aut(G)
[G]
Orb(G, u)
Stab(G, u)
graphs
Pe
qe
(G)
{G)
Pg
Graph-level flow function
F
Set of states
S
Set state transitions
A
Set of actions
A
Set of terminal states
X
Set of complete trajectories
T
State
Reward function
R
Forward policy over states
PA
Backward policy over states
Terminating probability induced by following PA
PA
State-action probability
PA
State-level flow function
F
B. Additional Comparison to Prior Work
To the best of our knowledge, Ma al. (2024) the only prior work addressing the equivalent action problem in GFlowNets. Their approach relies on approximate tests using positional encoding (PE) of nodes to identify nodes or edges within the same orbit. Once orbit is identified, the probabilities of orbit-equivalent actions summed. While they identified and partially addressed this issue, their discussion was limited to experimental validation. The primary motivation of Ma et al. (2024) was to highlight the existence of the problem and propose a partial solution. To this end, they conducted experiments in an offline, atomd environment.
In contrast, our work provides the first rigorous theoretical foundation for the correction, demonstrating that this issue not merely an experimental artifact but fundamental and systematic challenge arising from graph symmetries both atom- and fragment- generation. This insight is particularly significant given that GFlowNets were initially popularized for their reward-matching capabilities.
Our approach, based on reward/flow scaling, offers exact and efficient solution. Unlike PE-based methods, which require adaptation for different action types (e.g., incorporating edge types and fragments), our method is straightforward to implement and easily generalizable across various action types. Our motivation is to thoroughly analyze the problem and present an efficient, scalable solution applicable to real-world setups. To validate this, we conducted experiments with online training for both atom- and fragment-based generation.
12

---

Symmelry-Aware GelowNets
C. Definitions of Graph Actions
Here we provide a list of action types considered paper.
AddNode(G; u) adds a new node to the existing node u.
AddEdge (G, u) adds a new edge (u, v).
AddF AddFragment(G.C) adds fragment C.
RemoveNode(G, v) removes node and its connecting edges.
RemoveEdge(G, removes the edge (u, v).
RemoveFragment(G... removes the subgraph C.
SetNodeeAtributte[[] u, sets the node-level attribute for node u.
SetEdgeAtt::iureeGG.u u, u, sets the edge-level attribute for the edge (u, v).
SetGraphAttrributeG.
graph-level attribute L.
The Stop action be interpreted setting terminal flag, making SetGraphAttribute viable replacement. Some actions may overlap in functionality, For instance, AddNode is equivalent to sequence of two actions: adding new node and connecting it to an existing node u. This can be achieved using combination of AddF addFragment and AddEdge.
Likewise, the above graph actions can be easily extended to incorporate additional actions. For example, we can define AddColoreddoodeeC u, f) as an action that adds a new node with node type t to the existing node u. In fact, we used AddColoredNodde instead of using AddNode and SetNodeAttribn
the Synthetic Graphs experiment.
From practical perspective, defining AddColoredNon per trajectory and improves convenience. For theorems, however, proving AddColoredNode distinct case may be redundant.
separate action type reduces the number of transitions
D. Example of Equivalent Actions
AddEdge (2,
In Theorem 4.3 we established that orbit equivalence im- plies transition equivalence. However, the converse is not generally true, though such cases rare. A counterex- ample is illustrated in Figure While the two resulting graphs are isomorphic (by the permutation 1->4, 2-5, 3-1, 4-33, 5-6,, 6-2), they are induced by actions that modify nodes belonging to different orbits. In other words, two actions (2d and AddEdge( (4, 6) are transition censsttion-qquialenntt but not orbit-equivalent. How- ever, accounting for orbit-equivalent actions is sufficient, as the corresponding backward actions belong to two dis- tinct orbits as well.
AddEdge(4,6)
Figure 5: Two actions induce isomorphic graphs, making them transition-equivalent However, they are not orbit-cquivalent. This example was originally presented by (Ma et al. 2024).
E. Properties of Graph Neural Networks
E.1. Permutation Equivariance
The key design principle of GNNs is permutation equivariance, which ensures that the output remains consistent regardless of how the nodes in the input graph are ordered.
Definition E.1 (Permutation Equivariance). function f is permutation -qqiivariani if satisfies f(T(#)) = π Tff(x) for any permutation
13

---

Symmetry-Aware GFlowNets
Specifically, let A Rexxxx be the adjacency tensor of graph G with nodes. The d dimensional node and edge features of G are represented in A, where diagonal elements encode the node features. Let A Ji represent the (f, j) element of the tensor. We define the permutation of the tensor as T (A) [i
( (i), A [ Automorphisms are permutations that preserve adjacency tensor. That is. for π E Aut(G), we have т (A) A. Since GNNs are permuaaion-eqqiivrrann,, we can show that they produce identical node representations for nodes in the same orbit.
Theorem E.2. Let f [Rxxxxd x R=xxxx be cermutaaion-equivaai
function. Then, for any u, v, h, k E V. if there exists a permutation æ E Aut(G) such that π (u) and œ (v) = it follows that [(A) v) [[
Proof.
[(A)(u, o] = = (A) v]
[=( x())] =[(A)[b,
The theorem implics that nodes and edges within the same orbit are represented identically by GNNs.
E.2. Expressive Power
Another source of bias comes from the expressiveness of GNNs used to parameter- ize the policy. If actions from different orbits collapse into identical representations, reducing the network's 's representational power, the policy may be forced to as- sign equal probabilities to actions that produce different rewards. In Figure 6 the two actions AddEdge(G, 2, 4) and AddE,dge(,,2,. representations if they are aggregated from node representations. This occurs because nodes 2, 4 and 5 all belong to the same orbit and, therefore, share identical representations.
will have identical
Figure 6: Two edges (2, 4) and (2, 5) belong to different orbits and will result in non-isomorphic graphs if added to the graph. However, their edge representations will be identical aggregated from node representa- tions.
Significant research has been conducted on techniques to enhance the expressive power of GNNs (Xu al. 2018 Dwivedi et al., 202T). While much of this work has focused on improving graph-level representations, some methods have been proposed to enhance multi-node representations, such as edges (Zhang et al. 2021). In graph generation tasks, actions are often parameterized using all levels of representations wwweiitiionnnnnd-eeeeeee node-level, edge-level, and graph-level. This complexity makes designing expressive GNNs more challenging, emphasizing the need for architectures with enhanced expressive power when the task requires it.
In our synthetic experiments the main text, we augmented edge-level representations from the GNN with shortest path lengths to distinguish edges in different orbits. For example, in Figure 6 shortest path length of the edge (2, 4) is 2, while the length of 52 is 3. We conducted experiments without this feature augmentation, resulting in an inexact policy, as shown
0.025
Vanilla
Terminating Probability
x
Transition Correction
0.020
0.015
in Figure II Compare this to Figure 3 (a). where the terminat- ing probabilities are more accurate. Figure TT terminating probabilities for certain states exhibit significantly larger errors, with those states marked by red circles. These states correspond to successor states derived from the state shown in Figure 6
0.010
0.005
20
80
100
State Index
F. Proofs
F.1. Proof of Equation 6
Figure 7: Terminating probabilities. States are sorted ac- cording to the number of graphs in the state, |.]]. States with large errors are marked with red circles.
While we did not present Equation 6 as a theorem, a formal derivation offers insights into the relationship between AS)
14

---

Symmetry-Aware GetswNets
and 8), Specifically, Equation
states that
Pa(s((s==
E
P=(G'|G).
(6)
G'EE(G)Na'
for any G E 8.
Proof. We expand state transition probability (s(s'(s) ()) in terms of graph transitions as follows:
PA(8'Is) (AA(''s))AA(
PA(s)
EGes Eoresianne Pe Pe (G)
EGEs PG
Eoes Pe (G) Ecres(anna Pe GG'
Eoe: Pe(G)
If Ee Pe GG) is constant for all E 8, we can factor it out, obtaining:
PA(S'(s)=
Pe G'EE(Go)na
E
for any Go E s.
This constantness follows from two assumptions: pe is permutation equivalent, and 2) & is structured, meaning for any isomorphic graphs G, G' E s, the set of next graphs matched by some permutation such that E(G) (EE(")). In other words,
Σ
GG = Σ
(e(G"IT(G))
G'EE(G)n
G'EE(r(G))ne
holds for all æ E Aut(GG).
F.2 Proof of Theorem 4.3
The theorem simplifies to the assertion that, for a given graph G, graph actions of the same type applied within the same orbit are -nuuitioon-quivaleet.. To establish this, we prove the theorem for each action type. The results are straightforward for attribute-level actions, and we provide a proof for the NodeAtt ribute action.
Lemma F.1 (StrbudeAttribute). Let G[L f] denote the graph where the attribute of node in graph G is changed to t. If Orb(GG u) Orb(G, v), then GT(,,()
G(l((v) = t).
Proof. Let us denote the node labeling function of G, Gl],(()) and G(I,(n) t) as In. (n(u=d] and Injv=(] respectively. Since and u are in the same orbit, there exists æ Aut(G) such that TTu) = v. Showing in inju=] for all t E V is sufficient to establish the isomorphism. We prove for two cases. First, let w = u. Then, " satisfies Infu=e](u) (w) = (a( = (v) = (T(U)) = [=(==((((w)) Secondly, let w * u. Then, (n) (w) L. (xw)) (T(w))
= Ln[u=e] ( (w))
The proof for the SetEdgeAAtribut action is nearly identical that for SetNodeAttribute with nodes replaced by edges. We now proceed prove the cases for the AddEdge, AddNode, and their corresponding backward actions. We use the following two properties in proofs.
TEUUE') = (()) (u, EUE}
(()) (u,v) Eor E
=(x(()) (u,v) ((())) (u,v) E.)
-<(E))>(E)),
15

---

Symmetry-Aware GFlowNets
and similarly,
T(B) (())E) (u, EX)E : (u, E Eand (u, $ E ((T()) (u,z) ())(((() (4,))
(()(
=E() (=))),
where E and E' are edge sets. We assume homogeneous graphs for simplicity.
Lemma F:2 (AddEdge). Lei G[E U (u, v)] and G J (h, k)] denote the graphs induced by E. ((u,,) v)} and E. (hh, respectively. If (u, v) and (h, k) are in the same orbit in G. then GLE u (u, v]] and GLE (h, k)] are isomorphic. In other words, Orb(G, u, v) = Orb(G. h, k) implies G|E U (u, v)] = G U (h, k)].
Proof. If (u, and (h, k) are in the same orbit, then there exists л E Aut(G) such that (#))), = (h, Since is an automorphism, it also satisties T TEE) E. Thus, x 7(E U {(u, v)}) = T(E) U ((T()) m())) EU ((h, A)}, indicating that π is an isomorphism between G E U (u. vi] and G[E U (h, k)].
Lemma E.3 (RemoveEdge). Let G[E (u, c)] and G|E \ (h, k)] denote graphs induced by E B\ {(u, w)} and E' \ ((h,k) respectively. Then, G[E \ (u,w)] and G \ (h, k)] are isomorphic if (u, v) and (h, k) are in the same orbit in graph G.
Proof. Let E Orb(G,u, u, v) such that (T(1), (h, k)) Then, x(E \ ((u,))) x(E) \ ((T(u) E [(h, k)}, completing the proof.
Lemma F.4 (AddNode). Let G[EU( (u, w)] and (v, w)] denote the graphs induced by attaching a new node to the existing nodes and v, respectively. Then, Orb(G, u) = Orb(Gr v) implies G[E U (u, w)] = G[E U w)).
Proof. Let x E Orb(G, u) such that T ru)) = and let R VU ( - VU (w) be the extension of π such that ã fiw)) = and म (i) (i) for a w. Then, #EE U (u, w)) (EE) U (f =(w)) = (EE) U (T(U). ((w) = E U (v, w). O
Corollary F.5 (RemoveNode). Let GIV u] and G(V ui] denote the graphs induced by removing nodes and respectively, where edges connected to u or are also removed. Then, Orb(G, u) = Orb(G, v) implies G[V \u) = G[V Ao].
Proof. Let T E Aut(G) be an automorphism of G = (V, E") such that (u) = v. Then:
* <(E) (((u, kVE) : v)) +(E)
(VV)))) k KEV))
E (((c,)) eVju(()e) EV)
where F (f(u, R) : ls E V) U [(k; u) : k)) and E (f(e,k) u ((,,)) v) : W E V}) are edge sets of the induced subgraphs G[V \ u] and G[V \ o]. respectively.. Therefore, म, restricted to {u], is an isomorphism between G[V \ ul and GVV \ v).
F.3. Proof of Theorem 4.4
Proof. Note that orbit equivalence implies transition equivalence by Theorem 4.3 meaning that each of transition equivalent actions be partitioned into subsets of orbit-equivalent actions. State transition probabilities thus be computed by summing over state-action probabillities (als), where each Py is in turn defined by summing over orbit- equivalent graph actions in a.
Formally, let A(s) be the set of actions available from state s, and let a(s) represent the next state obtained by applying action a to s. Define A(s, = {a e A(s): : a(s) = s'} as the set of forward actions from state s that lead to state s'. Then, state transition probability can be expressed as:
16

---

Symmelry-Aware GelowNets
PA(s'(s)= = Σ Pa(als)
aEA(s,,')
(a(51/)) = E eg(als').
aEA(s,s))
From the assumption, state-action flow constraints are satisfied, i...
F(s)p = F(s")ga(a(s)
The assumption be satisfied if the equivariant neural networks parameterizing Pλ and q can distinguish between orbits differently, and the number of orbits (and hence the number of actions) is the same for both the forward and backward transitions.
Summing both side of the equations over A(s, s'), we have state transition flow constraints,
= F(s')
F.4. Proof of Lemma 4.5 and Its Generalization
Lemma 4.5 relates the order of orbits to the order of automorphism group. The proof relies on orbit-stabilizer theorem, hence we introduce the following definition.
Definition F6 (Stabilizer). The stabilizer of a node E V in graph G' is the set of automorphisms that fix node w: Stab(G, u) = fxr E Aut ru)) = u). The stabilizer of an edge (u, v) defined as Stab(G, u, u) = {xx E Aut(G) T(u) = u, (v) = v}. Similarly, the stabilizer of a node set S is defined as Stab(G, S) = {-t E Aut T(S) = S).
We restate Lemma 4.5 and provide its proof.
Lemma F.7 (AddEdge). Let G G'(F'' \ (u, v)) and G' G (u, v)) be successive graphs induced be E' \ (u,w)
and E U v). Then the following equation holds:
OrrbGG, w)
|Aut(G)
Orb(G",u,u
Proof. Using the orbit-stabilizer theorem, we have
jOrb(G, u,)) w)]
[A)
[Aul(G) Orb(G u, v. |rrb(G", u, v) [Stab(G, u, v)) |Stab(G', w))-
Aut(G')
[Orb(G",,, u)] Au)
Hence, we prove the lemma by showing [Stab(G, w) = |Stab(G', v)]. It suffices to prove that Stab v) Stab(G', u, v).
First, we show that Stab(G, u, v) C Stab(G", u, v). Let ग E Stab(G, u, v)v) Then T(u) u, T(U) = v, and T T(E ((u,v))) +(E) [(T(U), (())) = EU [(u, v)}. which implies that æ E Stab(G",
x'(E) U {(u, v), = E (u, v). Suppose for contradiction that (E) + E. Then some edge in E must be mapped to a different edge not in E, and to satisfy the equality (F) U {(,,,)) })} = FU (u, the only possibility is that n' r'EE) F {(,,))} But since n' (1 ()) = {u, e)}. this implies a duplication, contradicting the assumption that n' is a permutation. Therefore, (E)) E, and hence n' E Stab(G, u,
Conversely, let x' E Stab(G', u, v), r'(u) u, (v) u, and r' ((u,
Thus, Stab(G, u, v) Stab(G', u, v). completing the proof.
17

---

Symmetry-Aware GFlowNets
For general statement of Lemma by the action. For example, the orbit of AddEdge(G, (., u, v), denoted Orb(G, e), corresponds Orb(G, u, u,v)) The backward action associated with is RemoveEdge (G', v), and the orbit of this action when applied to the next graph G' is denoted as Orb(G", e), which corresponds to Orb(G', u, v). Definition of orbits for each action type is provided in Table 3
define the orbit of graph action the orbit of set of nodes edges affected
Table 3: Orbit of graph actions
AddNode(G, u) RemoveNode(G. AddEdge(G, u,
Orb(G, u)
Orb(G,
Orb(G,u,
RemoveEdge(G,,, v)
Orb(G,u,
SetModeettrributte...... u) Setuedgeattrribuee((....u SetGrapphAttribttte(....
Orb(G,
Orb(G,
Orb(G.V)
Using these definitions, we generalize Lemma 4.5 as follows.
Lemma F88. Let (G, G') & be graph transition induced by action E & that either adds node, edge, modifies an attribute in the graph G. Then, the following relationship holds:
Number forward arbit-equivalent actions
Orb(GGe) Orb(G',
|Au((G) |Aut(G"]
Number of backward orbit- wiiitequivvlent actions
We already proved Lemma F.8 AddEdge.
For cddNoodeAttributeeee t), the proof is straightforward: the only difference between G and G' is the attribute assigned to node u, it is immediate that Stab(G, u) Stab(G", u.). The argument for AddEdgeAttribute is nearly identical. Next, we prove the corresponding result for the AddNode.
Lemma F.9 (AddNode). Let G' FF') be the graph resulted by adding node to node in graph G (V, F.) Then,
[Orb(G, u)l OrrbG",, w) AAut(G")
[Aut(G)
Proof. Using the orbit-stabilizer theorem, it suffices to show [Stab(G, u)l |Stab(G", We do this by constructing bijective map f Stab(G, u) - Stab(G", e). Define f(T) = मे for E Stab(G, u), where ग is the extension of π defined on V U (v) given by
(ww)
if w E V wf
((w)=
We claim that E Stab(G", v). Since E Au) and ruu) u, it follows that Aut(G') and #(v) v. Thus, maps into Stab(G', v) and is injective by construction.
To show that is surjective, r't e Stab(G", v). Then n' E Aut(G") and <'(v) u, and we have
n' <' (eu = ((=((), Eu [
This implies that T'E) = E and (T' (u), v) = (u, u). so (u) = u. since & (E) cannot contain (u, v). Therefore, the restriction of x' on V, denoted म, belongs to Stab(G, GG, u), and satisfies f(*) = n².
Hence, f is bijective, and [Stab(G, u)l [Stab(G', 2)), as claimed.
18

---

Symmetry-Aware GFlowNets
F.5. Proof of Theorem 4.6
Proof. We first note that state-action probability can be computed by multiplying the number of orbit-equivalent actions when pe is permutation-equivaritni
px(als)
Σ Pg(c|G)
eεB(G)na
=|E(G) nal Pe(e[G)
for any G E s. Since (G) n al represents the number of orbit-equivalent actions from graph G, is equal to [Orb(G, for any E(G) N where defined the orbit of graph actions in Appendix F.4 Thus,
Pa(als) (Or((G, c) ps(elG).
Similarly, for the backward policy, have
(a(als) (Orb(G', .)) (ellG").
We prove Theorem usinn the following sequence of equations.
(a(ass
[Orb(G,e) pe(e|G)
4 (a(s')
Orb(G", e)] (((
Aut(G)] Ge(e]G)
Aut(G") (e
where we used Lemma F.8 for the last equation.
F.6. Proof of Theorem 5.2
Before proving Theorem 5.2
first prove the existence of a policy that satisfies graph-level DB constraints.
Lemma F.10. For any given reward function R, there exist pe, qe, and F that satisfy the graph-level detailed balance constraints for all transitions (G, G') &, defined as follows:
F(G))=(G'IG) F(G')a
Note that this differs from the usual state-level detailed balance condition:
F(s)pa(als) = ((s')a((ass)).
(8)
Proof. By Theorem 4.6 state-level detailed balance constraints can be rewritten graph transition probabilities as follows:
AAtt))))F(C))))(CGGG) [Ant(("")F((""
Defining F(G) = (AI(F)))F(G),, the functions F, pe. and qe satisfy the graph-level detailed balance constraints for given R.
Theorem F.11 (Restatement of Theorem 5.2p. If the rewards are scaled by |Aut(G) and the graph-level detailed balance constraints are satisfied for pe, qe, and F, then the corresponding forward policy will sample proportionally the reward.
19

---

Symmetry-Aware GFlowNets
State Transitions
Terminal state R(s2) =
F(s2 + +82 =2
F(s; 5z))
F(s₂ -g3) =
F(2z) 5
Graph Transitions
Terminal state
F(G2 ~ G2 4
R 4
F(G; G2) =
3
F + Gg) = =3
F(G', - G2)
F(G₂ G', =3
3
F(G2) = 10
Figure 8: Illustration of the effect of reward adjustment. Above: State transitions from and to 82. Below: Graph transitions from and to Gz. Due to the effect of the scaled reward R, state flows are also scaled by |Aut |Aut(G)), leading to (G) Aut))) The edge flows remain unchanged this figure. Note that the graph-level detailed balance condition holds, while the termination probability proportional to R(s).
Proof. For a given complete trajectory Go...., Gn. we have:
F(Go)pe(GG = ((G)))e(GolG..
F(Gn-1)pe (G |n =
Multiplying the left- and right-hand sides of all the equations, get:
n-1
F(Go) II (G (G, II ge GG.
Defining F(Go) Z, this reduces to the state-level trajectory balance condition with corrections as in Corollary 5.1 which ensures (x)x) R(x), as shown by Proposition of Malkin et al. (2022).
G. Discussion on the Flow-Matching Objective
The first GelowNet training objective proposed by Bengio et al. (2021) the Flow-Matching (FM) objective, which requires the flow-matchie matching condition to hold every state s':
Σ (.
F(s -()
Σ F(s' + s")
(10)
where F(s - s') denotes the edge flow. As with the DB and TB objectives, it suffices scale the final rewards to remove the bias introduced by action equivalence.
Corollary G.1 (FM correction). Consider the node-by-nee node generation. Specifically, we restrict the set of graph actions to
20

---

Symmetry-Aware GFlowNets
those defined in Appendix
except for fragment based actions. Define the flommmachig condition as:
E
G()
E GG"),
G:
G":(GrGGEEE
where F(- +) denotes a permulation equivalent graph-level edge-flow function. If the rewards are given by R(G) (att(G))(()) and the graph-level flow-matching condition holds for all states, then the forward policy induced by F samples terminal states proportionally to the original reward R.
Proof. The detailed balance condition is satisfied whenever the flow- fow-matching condition holds, via the relations:
F(G)= = E
('EE(G)
PE GG F(G + G')
F(G)
G' F(G + G')
F(G')
Applying Theorem 5.2 the result follows.
As with the DB objective, FM can be corrected each state without scaling the reward. Consider neural network that parameterizes the edge flow function and outputs all possible outgoing edge flows F(G - G') from given graph G. Outflows, defined as Eg'.(G' LG":(G',")) G")
F(G' + G can be computed easily by summing the outputs of the neural network.
In contrast, computing the inflows for given graph G' involves two considerations: (I) enumerating parents of G', which may include isomorphic duplicates. To account for this, the total inflow should be divided by the number of duplicates; (2) computing edge flows F(G + G") for each parent graph G, which may involve equivalence actions. To account for this, the total inflow should be multiplied by the number of equivalent actions. These considerations lead to the following result.
Theorem G.2. Let G" be the given graph representing the current state. Assuming node-by-node generation, the state-level flow-natching condition can be expressed in terms of the flow flow-matching condition as follows:
Σ
|Au(G)) + G") ||Aut(G") GP: (())E)))))))))))
Σ
i'G' +
GE
where F(- .) denotes a permutation-equivee edge-flow function.
Proof. The inflows are computed as follows:
Number of forward orbit ebbt-equivalent actions from to G" F - G')
Σ F(s s')= =
Σ
Number of backward orbit-equivalet actions from G" to G
a:(,,8))AA
GE
[At) [Aul(G))
Σ
F(G F(G-G") G'),
G:
where the last equality holds in virtue of Lemma F8 The first equality follows from the two considerations mentioned: (1) dividing by the number of backward orbit-equivalen actions to account for duplicate parents; (2) multiplying inflows by the number of forward eibit-qquivalent actions to account for duplicate actions. On the other hand, the outflows are directly computed as:
Σ
F(s' =
Σ
F(G' + G").
JEA
""''G","")E"
Rearranging terms, we have the result.
21

---

Symmetry-Aware GelowNets
Aut(C)
|Aut(G") =
[Orb(G', .V]
G'
(rb((,,))]=
Figure 9: Transition representing the AddF raggent action.
H. Discussion on the Fragment-based Generation
In the case the action AddF r gment (G, C), which adds fragment the existing graph resulting in G' GUC, we must account for the additional symmetries introduced by the fragment. In Figure there is only one way of adding and deleting the fragment from G to G", while the fragment induces 6 symmetries in G".
We begin by defining the notion of orbits for actions AddFragment (G, C) and RemoveF ragment (G', C). The orbit of AddF agment (G, C) is defined as Orb(G, V), whose cardinality is 1. This is because each fragment C' in the vocabulary leads to unique next graph when added to G, so the number of forward transition-equivakle For the corresponding backward action RemoveF r ragment (G', C), however, there may be multiple subgraphs of G' that are isomorphic C. Hence, we define the orbit as RemoveFragment (G', C) is Orb(G', C) {C" 3r Aut(G'), (C) C²). This captures all subgraphs of G' that are automorphic images of C, i.e., all valid candidates for removal that equivalent under the symmetry of G'.
actions is
Next, we extend Lemma 4.5 to accommodate the fragment-level actions, which account for the symmetries of both the existing graph and the fragment.
Lemma H.1. Let G = (Va, Eg) be graph representing the current state. We consider augmenting the graph G by adding a fragment C = (Vc, Ec). Let GUC = (Ve U Vc, Eg U Ec) denote the union of the two graphs (without any edges connecting and C). Then, we have:
Number of forward orbit-equivalent actions
OrrbG V)I
Number of backward orbit-equivalens actions Orb(GGUC,)
[Aut(Gu
Proof. Since [Orb(G, V) = 1, we only need to consider |rr U C, C) The stabilizer Stab U C, C) is the set of automorphisms in (G C) that does not mix the labels of G and C: acts independently on G and C. Therefore, the order Stab(G C, C) is [Aut(G)] [Aut(C)]. Using the orbit-stabilizer theorem, we obtain:
|Aut(G UCI [Stab(GUC,C)) AAt(G
(Orb(GUC,c))
[Aul(C))
Using Lemma H.l we obtain fragment correction formula in Theorem 5.3
Theorem H.2 (Fragment correction). Let G represents terminal state ([G) X) generated by connecting k fragments (Ci...., C.). Then, the scaled rewards offset the effects of equivalent actions given by:
[A
R((G) = 11 AAu((C.)
Proof. Using Lemma H.1 first derive similar results for Theorem 4.6
If pe and ge are permutation-eqquiaaiant functions,
we have
(a(as)
[Aut(G) [Aut(C))
Pe (G(G"v G))
9, (a(a)s))
[Aul(G))
qe (G G')
22

---

Symmetry-Aware GFlowNets
Figure 10: A fragment with attachment points highlighted. Attachment points are designed such that they break symmetries of the fragment. Rightmost graph represent the terminal state where attachment points are removed.
We defined AddF ragment (G, C) as adding a fragment C, resulting in disconnected graph G C.C. To connect between fragments, we use AddEdge and Lemma [77 Then, the results follows from the TB objective written in terms of graph transitions pg and gg, and the telescoping sum, as in Corollary 5.1
Unlike atom-based generation, the fragment terms [Aut(C) do not cancel out through a telescoping sum. Therefore, these terms must be explicitly accounted for in the correction, both for reward scaling and estimating the model likelihood.
We need exercise caution when applying Lemma H.2 the validity of the result depends on the specifies of the action design. A common practice in the GFlowNet literature is to predefine set of attachment points for each fragment, where attachment points refer nodes where new edges can connect to other fragments. These attachment points should be treated as node attributes, even if they are artifacts of the generation process rather than intrinsic properties of the graph. The reason for this treatment is that attachment points constrain the set of allowable actions, including the set of equivalent actions. For example, even if two nodes u and v belong to the same orbit, they should be considered distinct if only one of them is marked as an attachment point.
The complication arises when terminal states are considered. Since attachment points are not intrinsic properties of the graph, conceptually, graph receives its reward after the attachment points removed as shown in Figure [0] However, this removal introduces three distinct backward actions from the terminal state in the figure, which complicates the calculation of the backward probabilities.
This issue does not arise, however, if we arrange attachment points in a fragment such that nodes different orbits (i.e., orbits that consider attachment points as node attributes) remain different even after the attachment points not present. We observe that this holds for the fragments used in Bengio al. (202T).
Relation to Node Orderings
Some previous work on graph generation uses distribution over permutations (or node orderings) R,, treating it as random variable (Chen et al. 2021 Kong et al., 2023 Wang et al. (025). If the node (or edge) ordering π is given, the generation path Su.n = (Sy..... Sn can be determined. However, the converse is not generally true: for each state sequence Sp:n. there can be multiple compatible orderings n, complicating the computation of variational lower bound.
Chen al. 2202 derived an exact formula for the number of node orderings consistent with a given trajectory som is given by the product of the sizes of the orbits encountered during the generative process. I Orb(s,, a.)l. To make this computation tractable, they approximate the orbit sizes using the color refinement algorithm. This estimate is then used to compute the joint probability p(s0.n: x).
However, the joint probability can be computed easily we consider the corresponding graph sequence Gyen as p(Su.n т)) IF= Pe (G [Gt. This holds because the number of different orderings that induce the same state sequence 30m corresponds to the number of distinct paths generated by following cansition-equivalenn actions. this view, different actions that are transition transition-cquivalent can be interpreted as actions that induce different orderings while resulting in the same sequence of graph states. See Chen et al. (02T) for more details on using node orderings as random variable.
23

---

Symmelry-Aware GFlowNets
J. Computational Cost
J.1. Computation Time for Counting Automorphisms
While computing the exact [Aut(G)] has inherent complexity, this complexity is unavoidable for exact GFlowNets. In practice, fast heuristic algorithms computing |Aut(G)] often perform well, particularly for relatively small graphs. We provide computation time of Aut(G)] for several molecular dataset.
Table 4: Computational cost.
"Large" dataset refers the largest molecules in PubChem, which used in the paper Flam-Shepherd et al. 2022). Experiments were conducted Apple MI processor.
Dataset
Sample Size
Num Atoms
Compute time (bliss)
Compute time (nauty)
QM9
133,885
8.8 + 0.5
0.010 ms # 0.008
0.019 ms + 0.079
ZINC250k
249,455
23.2 + 4.5
0,022 ms + 0.010
0,042 ms + 0.032
CEP
29,978
27.7 + 3.4
0.025 ms + 0.014
0.050 ms + 0.076
Large
304,414
140.1 = 49.4
0.483 ms + 12.600
Compared to sampling trajectories, which involves multiple forward passes through neural network, the compute time for [Aut(G)] is negligible. For comparison, we report the speed of molecular parsing algorithms measured using ZINC250k dataset: 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 [Au is in an order of magniudee faster than validity checking algorithm.
We used the bliss algorithm for our experiment. It is easy for our purposes. For large molecules, we can still count automorphisms in few milliseconds using the nauty package (McKay & Piperno 2013) 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. The reported time in the table reflects these preprocessing steps.
it is included in the igraph package and is fast enough
While we believe the computation time is already negligible for current applications, we outline two additional strategies to further reduce runtime:
1. Parallelization. Data processing tasks can be parallelized across multiple CPUs. Since GFlowNet is an off off-policy algorithm, [Aut(G)| can be computed concurrently with the policy learning.
2. Approximate correction for large graphs. For large graphs, fragment- based generation is highly likely to be employed. In such cases, we can apply an approximate correction scheme, as outlined in Appendix H
J.2. Training Time Comparison
To evaluate the training time, we ran three separate training sessions for each method. Table 5 reports the total training time for each method in the synthetic environment.
Method
1000 Steps (s)
3000 Steps (s)
5000 Steps (s)
Transition Correction
1338 + 79
4122 168
6859 + 80
PE (Ma et al., 2024)
1322 - 44
4001 131
6604 = 152
Reward Scaling (Ours)
1178 31
3584
5999 + 146
Flow Scaling (Ours)
1176 + 32
3577 100
5987 + 168
Table 5: Wall-clock runtime (in seconds) for different methods over increasing training steps. Mean and standard deviation are computed over 3 runs.
While PE is faster than Transition Correction-whiin performs multiple isomorphism tests per transition-onn our proposed methods, Reward Scaling and Flow Scaling, are even more efficient. All timing experiments were conducted using a single processor with TITAN RTX GPU (24GB) and an Intel Xeon Silver 4216 CPU. These results demonstrate that our methods incur significantly less computational overhead while preserving correctness.
24

---

Symmetry-Aware GelowNets
J.3. Scalability Comparison
We evaluated the computation time for each method, varying the number of transitions per trajectory. We sampled 100 ran-
05
Transition Correction
PE (Ma et al., 2024)
dom graphs for each horizon length category. We measured the time spent on only the major components of each method. This includes: 1) multiple isomorphism tests for Transition Correction; 2) computing positional encodings and matching encodings to identify isomorphic graphs for PE; 3) comput- ing automorphisms of the final graph for Reward Scaling: 4)
Compute Time (secands)
0.4
Reward Scaling (ours)
Flow Scaling (ours)
0.3
0.2
computing automorphisms of all intermediate graphs for Flow Scaling.
0.3
When computing PEs, we used & = 8. Note that methods I) and 2) must be applied for both forward and backward actions. The table below reports the additional computational cost incurred by each method per trajectory, where Vanilla GelowNets is considered incur zero additional cost.
0.0
20
100
Number Transitions
Figure
Method
10 Transitions (ms)
50 Transitions (ms)
100 Transitions (ms)
Transition Correction
24.32 + 6.28
1148 = 240.3
7354 + 1288
PE (Ma et al., 2024)
5.49 = 0.58
186.7 = 29.87
997.5 # 133.9
Reward Scaling (Ours)
0.024 0.002
0.063 + 0.004
0.111 = 0.008
Flow Scaling (Ours)
0.215 0.025
2.106 + 0.116
6.975 + 0.421
Table 6: Runtime comparison for computing correction terms under different methods.
While the cost increases for all methods as the number of transitions grows, our method clearly scales better. is important note that the time differences accumulate over the entire training duration. Experiments were performed using Intel Xeon Silver 4216 CPU.
K. Experimental Details
K.1. Graphs-building Environments
For graph-building environments, both for illustrative example and synthetic graphs, we stacked GPS layers with 256 embedding dimensions (Rampášek et al., 2022). To increase representation power, we augmented node features to increase representation power. We augmented node features with one-hot node degree, clustering coefficient, and dimensions of uundom-wlll positional encoding (Dwivedi et al. (02T). Importantly, edge features were computed by summing node features outputted from GNN layers, which, in turn, concatenated with shortest path length between nodes connected by the edge. This is to prevent representation collapse between different orbits (see Appendix E.2).
Illustrative Example. For the illustrative experiment, homogeneous graphs were constructed edge by edge, allowing only AddEdge and Stop actions. The initial state consisted of six disconnected nodes, and terminal states corresponded to connected graphs without isolated nodes. The number of terminal states, | is 112.
We trained the models for 30,000 updates using the TB objective. During the first 16,000 steps, each update used batch of 128 trajectories, comprising 32 samples from the current policy and 96 samples drawn from the replay buffer. We used the Adam optimizer (Kingma 2014) with the default parameters from PyTorch (Paszke et al., 2019) settings, except for the learning rates: 0.0001 for GNN layers and 0.01 for the normalizing constant Z. For the remaining steps, we increased batch size 256 and annealed the learning rate 0.00001. To encourage exploration, the policy selected actions uniformly with a probability of 0.9.
Synthetic Graphs. For the Synthetic Graphs experiment, we followed the environment setup described in Ma et al.) 2024). Each node can be one of two types, and graphs can contain up to 7 nodes, resulting in total of 72,296 terminal
25

---

Symmetry-Aware GFlowNets
states. The generation process starts from the empty graph, from which the policy incrementally adds nodes and edges. The reward function also adopted from (Ma et al. 2024).
Models were updated 50,000 times using both the TB and DB objectives. For the TB objective, 64 trajectories were used for updates, with 16 sampled from the behavior policy. For the DB objective, 16 trajectories were sampled per step and converted into transitions, with each update utilizing 512 transitions. We used the Adam optimizer with a learning rate 0.0001 for GNN layers and 0.01 for the normalizing constant Z.
PE Implementation Details. Following Ma et al. (024)) we implemented the positional embedding (PE) method as follows: First, the random walk matrix is computed as (AD-1)*, where the adjacency matrix, and D is the degree matrix with node degrees on the diagonal. Next, we multiply the matrix by a vector c representing node types. We constructed the vector c by setting each element to log(t + 2). where i {0, 1.... } denotes the node type ID. By varying from 0 to 7, we obtained 8-dimensional PEs for each node. Edge-level PEs were then computed by summing the embeddings of the corresponding node pairs. Finally, actions sampled from the policy were compared with other candidate actions based on their PEs to identify equivalence.
K.2. Molecule Generation
We conducted experiments small molecule generation tasks following (Bengio et al. 2021 Jain al. 2023b). More detailed task descriptions can be found in these previous works. We used open-source code for tasks We used graph transformer architecture (Yun et al.) 2019) with the hyperparameters summarized in Table and Table In GFlowNets, the reward exponent 3 is used to focus sampling on high-reward regions in the state space. The correction is applied after rewards are exponentiated: C(z) R(x),, where C(r) is the correction term.
Table 7: Hyperparameters for atom-based experiments
Hyperparameters
Values
Learning Rate (pe, Z)
0.0005
Batch Size (Online)
32
Batch Size (Buffer)
32
Training
Uniform Exploration e
0.1
Gradient Clipping (Layer-wise Norm)
10.0
Reward Exponent 3
Number of Updates
30,000
Architecture
Graph Transformer
Number of Layers
4
Model
Number of Heads
4
Number of Embeddings
128
Number of Final MLP Layers
1
Evaluation Metrics.
Evaluation metrics we presented in Table are defined as follows:
Diversity, The average pairwise Tanimoto distance between molecules sampled from the trained policy.
Top K diverse. Diversity among the top K reward molecules.
Top K reward. The average reward of the top K molecules.
Diverse top K. The average reward of the top K molecules, ensuring that each pair has Tanimoto distance greater than 0.7.
Unique fraction. The fraction of unique molecules in the generated samples.
onpharrm ownet
26

---

Symmetry-Aware GFlowNets
Table 8: Hyperparameters for fragment-based experiments
Hyperparameters
Values
Learning Rate (pg)
0.0001
Learning Rate (Z)
0.001
Batch Size (Online)
32
Batch Size (Buffer)
32
Training
Exploration
0.1
Gradient Clipping (Layer-wise Norm)
10.0
Reward Exponent 3
16
Number of Updates
30,000
Architecture
Graph Transformer
Number of Layers
5
Model
Number of Heads
4
Number of Embeddings
256
Number of Final MLP Layers
2
We selected K = 50, which corresponds to the top 10% of molecules for our evaluation. When reporting rewards, we adjust them to remove the effects of reward scaling and reward exponents.
For the Pearson correlation evaluation presented in Figure terminal states were sampled by uniformly selecting random actions. The model likelihood was computed using Equation (4) with modified correction term in Theorem 5.3 We set M 5 and used 2,048 samples for the test set.
K.3. Fragment Correction Method
For fragment-bart based molecule generation, we used a predefined al. (2021). ). There are total of 72 fragments, each with a varying number of attachment points. Our method requires pre-computing the number of automorphisms for each fragment. In Figure 12, present the number of automorphisms for each fragment used in our experiment. As discussed in Appendix H attachment points were treated as distinct attributes when counting automorphisms.
fragments and attachment points provided by /Bengio
K.4. Approximate Correction Method
Additionally, we experimented with a simplified version where the correction is applied approximately for the fragment- based task. While we can compute exact correction term as in Equation (3), this approximation provides computational benefits, as avoids counting automorphisms. Moreover, similar approximations can be easily implemented even for more complex generation schemes that do not fit into Equation (3.. The approximation works as follows: we assign a number to each fragment based on how many equivalent actions likely to incur during generation. We adjust the final rewards by dividing them by the product of the assigned numbers N for the constituent fragments: R(G) I_=_, N(C.).
assigned the number N each fragment based on how likely is to incur forward equivalent actions. This because fragments that incur multiple forward equivalent actions are more likely to be selected if no adjustment is applied. For example, cyclohexane (C1 cccCC1) has six attachment points, all in the same orbit, it will always incur at least six forward equivalent actions in subsequent steps. In contrast, even if fragment is highly symmetric, if it has only one attachment point, it will incur no equivalent actions. We assigned N = 1 to such fragments.
Assuming backward equivalent actions are relatively rare in fragment- based generation, this approximation should closely match the unbiased correction. These numbers were assigned through visual inspection of the fragments. The full set of fragments and their assigned numbers for the approximate correction is provided Figure
27

---

Symmelry-Aware GelowNets
Figure 12: Predefined fragment set used for the fragment-based task. Attachment points, where a single bond can connect another fragment, are highlighted in red. The numbers indicate the order of the automorphism group each fragment, [Aut(C)).
L. Additional Experimental Results
L.1. Synthetic Graphs
In addition the clique environment presented the main text, conducted similar experiments under different reward structure. We restricted the maximum number of nodes and edges 10, and limited the maximum node degree to 4, therehy constraining the state space to | 2, 999. Rewards were defined as 1 (number of cycles). The hyperparameters are not tuned and remain the same as those explained in Appendix K
For the TB objective shown in Figure (a), the PE method slightly underperforms compared to Reward Scaling, which consistent with the results the clique environment. contrast, for DB objective shown in Figure [4 (b), where intermediate probabilities play a crucial role, the PE method performs comparably Reward Scaling. all cases, Transition Correction and Flow Scaling perform the best.
L.2. Molecule Generation
We investigated which fragments were sampled by each method. We sampled 5,000 terminal states from trained models, resulting in 44,974 and 44,978 fragments sampled from vanilla and corrected model, respectively. Symmetric fragments were found to be sampled more frequently in vanilla model, which aligns with projection, as the fragment correction in Equation (3) penalizes symmetric components. However, the proportions of fragments between the two methods are not exactly proportional to the magnitude of the corrections, as some fragments are more likely to occur together (they are not independent).
28

---

Symmelry-Aware GelowNets
Figure 13: Predefined fragment set used for the fragment-ban based task. Attachment points are highlighted in red. The numbers
below each molecule used for approximate correction.
Vanilla
Vanilla
1.75
1.75
Transition Correction
Transition Correction
1.50
PE (Ma et al., 2024)
1.50
PE (Ma et al., 2024)
Reward Scaling (Ours)
Reward Scaling (Ours)
Error
1.25
L Error
1.25
Flow Scaling (Ours)
1.00
1.00
0.75
0.50
0.25
0.25
10
20
0
10
30
Number Model Updates
x10
Number of Model Updates
x10a
(a) Synthetic (TB)
(b) Synthetic (DB)
Figure 14: Results on synthetic experiments, where rewards are given based on the number of cycles in the graph.
Vanilla
5220
4821
101
531
744
Reward Scaling
1042
1038
63
349
495
Figure 15: The number of sampled fragments from 5,000 terminal states for vanilla model and corrected model. We display the 5 fragments that were sampled most disproportionately, Attachment points are highlighted in red.
29


Reviews:
[{"review_id": "CxDM30h1Js", "reviewer": "Reviewer_Dmkx", "summary": "This paper addresses the equivalent action problem in GFlowNets for graph generation, providing a theoretical foundation and solution to a bias previously identified in Ma et al. (2024). While the paper offers valuable theoretical insights and formal proofs, the core solution (reward scaling based on automorphism counts) appears to be fundamentally the same as what was previously proposed. The paper's novelty is therefore primarily in its theoretical analysis rather than in the proposed method itself, raising questions about sufficient contribution for publication.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thoughtful comments and valuable feedback. In particular, we sincerely hope that our response helps evaluation recognizing our contributions, especially in providing a rigorous theoretical foundation and conducting extensive experiments on the problem.\n\n---\n## **Clarification on the Differences from Ma et al. (2024)**\n\n**Our proposed approach is methodologically different from that of Ma et al. (2024).** Their method explicitly identifies actions that lead to the same next state to compute exact transition probabilities, using positional encoding as an approximate way to find such actions. In contrast, our approach is based on Theorem 4.6 and does not rely on identifying equivalent actions. This brings clear operational advantages over the approach of Ma et al. (2024).\n\n**Exactness:** While our method provides an exact bias correction, the PE method can only approximate the target distribution.\n\n**Faster Computation:** Our method is orders of magnitude faster than the PE method, as PE should be computed for every transition (see Appendix I and the comparison below). \n\n**Broader Applicability:** Our method is applicable to any graph type and can be extended to fragment-based generation with minimal modifications. In contrast, the PE method as proposed in Ma et al. (2024) cannot be applied to graphs with edge types or fragment-based generation.\n\n**Straightforward Implementation:** Our method requires only scaling the final reward, making it straightforward to implement. In contrast, the PE method must identify both forward and backward equivalent actions and sum their probabilities, which may require substantial modifications to existing codebases.\n\nOne of our key theoretical findings is that graph automorphism is central to this problem, and in this sense, all solutions may appear fundamentally similar in hindsight. However, our approach offers clear theoretical and practical advantages, providing exact bias correction while maintaining broad applicability across different graph types. We further validate these arguments in the following comments. \n\n---\n## **Experimental Comparison with Ma et al. (2024)**\n\n**To better position our work, we implemented the PE method to compare with Ma et al. (2024)** and made our best effort to reproduce their approach. Implementation details, as well as plots for additional experiments, can be viewed through the following link: https://docs.google.com/document/d/1GhQgcaxQ32uXM7s6xfteGWsBovdm-JvQNW_m3hAG30Q/edit?usp=sharing\n\n### **Performance Comparison**\n\n**Since PE is an approximate solution, it underperforms compared to ours in terms of $L_1$ error.** We validated this in two synthetic environments: Cliques and Cycles. The results are presented using the Trajectory Balance objective, while the results for the Detailed Balance objective are provided in the linked document.\n\n|  | Cliques (L1 Error) | Cycles (L1 Error) |\n| --- | --- | --- |\n| PE (Ma et al., 2024) | 0.476 ± 0.026 | 0.233 ± 0.005 |\n| Reward Scaling (Ours) | 0.464 ± 0.011 | 0.189 ± 0.002 |\n\n### **Scalability Comparison**\n\n**Since PE must be computed at every transition, its computational cost scales poorly with the trajectory horizon.** We evaluated each method, varying the number of transitions per trajectory. We sampled 100 random graphs for each horizon length category. We measured the time spent on only the major components of each method (e.g., computing automorphisms for Reward Scaling). The table below shows the additional computational cost incurred by each method per trajectory.\n\n| Method | 10 Transitions (ms) | 50 Transitions (ms) | 100 Transitions (ms) |\n| --- | --- | --- | --- |\n| PE (Ma et al., 2024) | 5.49 ± 0.58 | 186.7 ± 29.87 | 997.5 ± 133.9 |\n| Orbit Correction (Ours) | 0.215 ± 0.025 | 2.106 ± 0.116 | 6.975 ± 0.421 |\n| Reward Scaling (Ours) | 0.024 ± 0.002 | 0.063 ± 0.004 | 0.111 ± 0.008 |\n\nWhile the cost increases for all methods as the number of transitions grows, our method clearly scales better. It is important to note that the time differences accumulate over the entire training duration.\n\n### **Training Time Comparison**\n\nWe measured the actual training time with the same setting used for our paper. \n\n|  | 1000 Steps (s) | 3000 Steps (s) | 5000 Steps (s) |\n| --- | --- | --- | --- |\n| PE (Ma et al., 2024) | 1322 ± 44 | 4001 ± 131 | 6604 ± 152 |\n| Orbit Correction (Ours) | 1176 ± 32 | 3577 ± 100 | 5987 ± 168 |\n| Reward Scaling (Ours) | 1178 ± 31 | 3584 ± 97 | 5999 ± 146 |\n\nOur method is faster than the PE method in terms of actual training time.\n\n---\n**Appendix C**: We appreciate the feedback. We will revise it in the revision.\n\n---\n## **Conclusion**\n\nOverall, our method offers clear advantages over Ma et al. (2024), which are validated through additional experiments. This demonstrates the novelty of our solution. We compared our method with Ma et al. (2024) to better position our work, and we will incorporate these results into the revised version.", "claims_and_evidence": "The paper's claims are mathematically proven in the appendix. The authors establish that:\n\n- GFlowNets without correction exhibit systematic bias toward graphs with fewer symmetries in atom-based generation and toward symmetric components in fragment-based generation.\n- This bias can be corrected by scaling rewards based on the automorphism group size.\n- This correction is sufficient for both TB and DB objectives.\n\nThese claims are supported by mathematical proofs and experimental validation.", "methods_and_evaluation_criteria": "The proposed reward scaling method is mathematically sound and the evaluation metrics used are relevant:\n\n- L1 error for synthetic experiments\n- Diversity, Top K diversity, reward metrics for molecule generation\n\nThese are appropriate for measuring both the theoretical correctness and practical utility of the approach.", "theoretical_claims": "These claims are supported by mathematical proofs that seem correct", "experimental_designs_or_analyses": "The illustrative example with uniform reward is particularly effective at visualizing the bias. The experimental settings span synthetic graphs and molecule generation tasks, providing good coverage of potential applications.\n\nOne weakness is the lack of direct experimental comparison with the positional encoding approach from Ma et al. (2024), which would have strengthened the paper's positioning.", "relation_to_broader_scientific_literature": "The paper's relationship to Ma et al. (2024) is the most critical aspect to evaluate. The authors acknowledge that Ma et al. (2024) was the first to identify the equivalent action problem in GFlowNets and propose methods to address it.\n\nHowever, the core solution in both papers appears to be fundamentally the same: accounting for graph automorphisms to correct the sampling bias. While this paper provides a more rigorous theoretical foundation and generalizes to fragment-based generation, the central mechanism of the solution is not novel.\n\nThe paper states: \"our work provides the first rigorous theoretical foundation for the correction,\" which is accurate, but the actual solution method appears to be a formalization of what was already proposed rather than a new approach.", "essential_references_not_discussed": "na", "other_strengths_and_weaknesses": "Appendix C contains an unclear explanation. The statement \"permuting nodes 3 and 4 yields the same graph\" doesn't seem accurate for the example shown. A more complex permutation (e.g., 1→4, 2→5, 3→1, 4→3, 5→6, 6→2) would be needed to map between the two graphs.\n\nOtherwise, the paper is well-written and easy to follow", "other_comments_or_suggestions": "na", "questions_for_authors": "na", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KYkxDD2gEO", "reviewer": "Reviewer_tYaE", "summary": "The authors propose a formal characterization of the equivalent action problem, first outlined by Ma et al. (2014), along with a simple fix by re-scaling the reward to account for automorphisms.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful feedback, and recognizing our work as important.\n\n---\n## **Comparison with Ma et al. (2024)**\n\n### **Implementation of Positional Encoding (PE) method**\n\n**To better position our work, we implemented the PE method to compare with Ma et al. (2024)** and made our best effort to reproduce their approach. We computed 8-dimensional PEs for each node, with edge-level PEs obtained by summing the corresponding node-level PEs. Finally, actions sampled from the policy were compared with other forward/backward actions based on their PEs to identify equivalent actions.\n\n### **Performance Comparison**\n\n**Since PE is an approximate solution, it underperforms compared to our method in terms of $L_1$ error.** We validated this in two synthetic environments: the Cliques and Cycles environment. The table below presents the results for the Trajectory Balance objective.\n\n|  | Cliques (L1 Error) | Cycles (L1 Error) |\n| --- | --- | --- |\n| PE (Ma et al., 2024) | 0.476 ± 0.026 | 0.233 ± 0.005 |\n| Reward Scaling | 0.464 ± 0.011 | 0.189 ± 0.002 |\n\nFor the Detailed Balance objective, however, it is difficult to predict whether Reward Scaling will outperform, as the PE method corrects intermediate probabilities similarly to Orbit Correction. In our experiments, PE performed on par with Orbit Correction.\n\n|  | Cliques (L1 Error) | Cycles (L1 Error) |\n| --- | --- | --- |\n| PE (Ma et al., 2024) | 0.129 ± 0.007 | 0.190 ± 0.009 |\n| Orbit Correction (Ours) | 0.122 ± 0.008 | 0.184 ± 0.005 |\n| Reward Scaling (Ours) | 0.150 ± 0.005 | 0.188 ± 0.025 |\n\nHowever, the PE method, as proposed in Ma et al. (2024), requires task-specific tuning and is not applicable to fragment-based generation. Therefore, we do not recommend using PE. Orbit Correction offers clear advantages over PE: exact correction, faster computation, broader applicability, and ease of implementation.\n\n### **Scalability Comparison**\n\n**Since PE must be computed at every transition, its computational cost scales poorly with the trajectory horizon.** We evaluated each method, varying the number of transitions per trajectory. We sampled 100 random graphs for each horizon length category. The table below shows the additional computational cost (compared to Vanilla GFlowNets) incurred by each method per trajectory. \n\nPlot link: https://drive.google.com/file/d/1hhB0TVyHKmclFJ65O__BlX74fRUvNtrS/view?usp=sharing\n\n| Method | 10 Transitions (ms) | 50 Transitions (ms) | 100 Transitions (ms) |\n| --- | --- | --- | --- |\n| Transition Correction | 24.32 ± 6.28 | 1148 ± 240.3 | 7354 ± 1288 |\n| PE (Ma et al., 2024) | 5.49 ± 0.58 | 186.7 ± 29.87 | 997.5 ± 133.9 |\n| Orbit Correction (Ours) | 0.215 ± 0.025 | 2.106 ± 0.116 | 6.975 ± 0.421 |\n| Reward Scaling (Ours) | 0.024 ± 0.002 | 0.063 ± 0.004 | 0.111 ± 0.008 |\n\nWhile the cost increases for all methods as the number of transitions grows, our method clearly scales better. It is important to note that the time differences accumulate over the entire training duration.\n\n### **Training Time Comparison**\n\n**While PE is faster than Transition Correction (which performs several isomorphism tests), our methods (Orbit Correction, Reward Scaling) are faster.** We present the actual running time of each method on the synthetic environment presented in the paper. \n\n|  | 1000 Steps (s) | 3000 Steps (s) | 5000 Steps (s) |\n| --- | --- | --- | --- |\n| Transition Correction | 1338 ± 79 | 4122 ± 168 | 6859 ± 80 |\n| PE (Ma et al., 2024) | 1322 ± 44 | 4001 ± 131 | 6604 ± 152 |\n| Orbit Correction (Ours) | 1176 ± 32 | 3577 ± 100 | 5987 ± 168 |\n| Reward Scaling (Ours) | 1178 ± 31 | 3584 ± 97 | 5999 ± 146 |\n\nWe used one processor with one GPU (24GB TITAN RTX GPU, Intel Xeon Silver 4216 CPU).\n\n---\n## **Measure of Goodness-of-Fit**\n\n**We emphasize that the purpose of the molecule generation task is to assess whether the correction methods can improve the generation of high-reward samples in realistic reward settings, rather than to demonstrate the correctness of our method.** Therefore, we included the correlation plot only for fragment-based generation (Fig. 4). We obtained improved results with correction for atom-based generation as well, which will be incorporated into the revised version.\n\nWe used correlation as a metric because it is a widely adopted measure of goodness-of-fit in several previous works (Malkin et al., 2022; Malkin et al., 2023; Madan et al., 2023). While we considered your suggestion to use the recently proposed FCS score (Silva et al., 2025), we concluded that further investigation is needed to determine the best practice for its application.\n\n---\n## **On Notations**\n\nWhile we summarized our notations in Appendix A, we acknowledge that some of our notation can be confusing. We are carefully reviewing our notation and theoretical explanations to make the paper more readable in the revised version.\n\nWe hope this addresses your concerns regarding the weaknesses of our paper.", "claims_and_evidence": "To my best judgment, the work is theoretically sound, and the authors provide compelling evidence that their method fixes the pathology they set up to solve—with a few caveats pointed out below.", "methods_and_evaluation_criteria": "The comparison should include Ma et al. (2014)'s approach, including comparisons regarding computing time.", "theoretical_claims": "I didn't check the proofs closely, but I found the notation overcharged and sometimes confusing. For instance, the same $\\pi$ is used for sets, edges, and graphs. Also,  $\\mathcal{E}$ is used is used to denote bot a set of ordered pairs of graph and to denote a function outputting the set of graphs reachable from $G$ in a single transition. There are also things that are not formally defined like $\\mathcal{E}(G) \\cap s'$, which I guess assumes $s'$ is an equivalence class of graphs.", "experimental_designs_or_analyses": "I like the synthetic experiment showcasing the pathology in question. However, I would also like to point out that analyzing the results in Table 1 alone might be misleading, as the quantities presented do not measure sampling correctness. A measure like [1]'s FCS would better proxy distributional correctness.\n\n\n[1] https://openreview.net/forum?id=9GsgCUJtic", "relation_to_broader_scientific_literature": "This work addresses a well-known issue in the GFlowNet literature with an easy and provably correct fix --- which could become a standard when implementing GFlowNets to sample from distributions over anonymous graphs.", "essential_references_not_discussed": "To the best of my knowledge, authors properly recognize the prior art.", "other_strengths_and_weaknesses": "## Strengths\n\n* Proposes a formal treatment to the equivalent actions problem, along with an easy fix by rescaling the reward\n\n* The manuscript is well written, and developments are mostly easy to follow\n\n* Nice illustration in a synthetic experiment, along with experiments in molecule generation\n\n## Weaknesses\n\n* Missing direct comparison with Ma et al.'s (2014) original fix\n\n* Measures of performance for the molecule generation experiments to not reflect goodness-of-fit (i.e., distributional correctness)\n\n* Notation is sometimes confusing (see \"Theoretical Claims\" above)", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3cgR0x4ySg", "reviewer": "Reviewer_uGgD", "summary": "The authors claim that when applying GFlowNets to the graph generation problem, the presence of equivalent actions—where different actions produce the same graph structure—introduces additional bias.\nUnlike previous works that require computationally expensive calculations at each iteration, the authors propose a simple yet effective approach to compute the number of graph automorphisms only in the final iteration. This is achieved by modifying the Trajectory Balance (TB) and Detailed Balance (DB) losses based on their theoretical proof.\nThe authors demonstrate the effectiveness of their proposed loss function using both synthetic data and the benchmark molecular generation task.\n\n## update after rebuttal\n\nMy remaining concerns have been well addressed.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thoughtful feedback and your recognition of our work's potential impact in this area!\n\n---\n## **Impact of Incorrect Automorphism Counting**\n\nWhile we are uncertain about the conditions under which the *bliss* algorithm might fail, we believe it produces exact outputs given the current scale of GFlowNet applications (with fewer than 100 nodes). Moreover, reliance on *bliss* is not essential, as popular alternatives such as *nauty* are available.\n\nThat said, incorrect automorphism calculations can result in slow convergence or an inaccurate policy, with the exact impact depending on the reward landscape. We consider two specific cases separately.\n\n**Random Counting:** We consider a scenario where the software randomly miscounts the size of the automorphism group in 10% of cases—doubling it 5% of the time and halving it 5% of the time. Since the GFlowNet objectives are constructed in the log space, this amounts to the random noise of $\\log 2$, which incurs no bias.\n\n**Systematic Miscounting:** We implemented an approximate automorphism counter using the Weisfeiler-Lehman (WL) algorithm. If the final coloring has $k$ distinct color classes, and class $i$ has size $s_i$, then an approximation is computed as $\\prod_{i=1}^k s_i$. This assumes that nodes within each class can be permuted freely, which is an upper bound of $|\\mathrm{Aut}(G)|$. \n\n**Experimental Results**\n\nWe conducted a simple experiment in relatively small environment ($|\\mathcal X| = 301$) using the TB objective with Reward Scaling. As shown in the plot linked below, Random Counting converges to the exact method but does so slowly. The approximation using the WL algorithm proved too crude for this environment. A more accurate approximation would better align with our method. \n\nhttps://drive.google.com/file/d/12m4uqiZdPxcpsaUYowD7ZWUh3wYCGz99/view?usp=sharing\n\nAdditionally, we implemented the PE method of Ma et al. (2024), which gives an approximate solution to the problem. The experiments were conducted on two synthetic environments: Cliques and Cycles. While it underperformed compared to ours, it proved to be far better than the Vanilla GFlowNets, which highlights the importance of removing bias.\n\n| Method | Cliques (L1 Error) | Cycles (L1 Error) |\n| --- | --- | --- |\n| Vanilla  | 0.693 ± 0.001 | 0.463 ± 0.001 |\n| PE (Ma et al., 2024) | 0.476 ± 0.026 | 0.233 ± 0.005 |\n| Reward Scaling (Ours) | 0.464 ± 0.011 | 0.189 ± 0.002 |\n\nWe obtained similar results in the fragment-based generation task (reported in page 8), where we proposed an approximate solution.\n\nOverall, miscalculating automorphisms can degrade performance. However, as long as we can approximate them well, we should always apply the necessary corrections to eliminate bias.\n\n---\n## **Scalability Comparison**\n\n**Our method scale far better than other correction methods.** We evaluated each method, varying the number of transitions per trajectory. We sampled 100 random graphs for each horizon length category. We measured the time spent on only the major components of each method (e.g., computing automorphisms for Reward Scaling). The table below shows the additional computational cost (compared to Vanilla GFlowNets) incurred by each method per trajectory. \n\nPlot link: https://drive.google.com/file/d/1hhB0TVyHKmclFJ65O__BlX74fRUvNtrS/view?usp=sharing\n\n| Method | 10 Transitions (ms) | 50 Transitions (ms) | 100 Transitions (ms) |\n| --- | --- | --- | --- |\n| Transition Correction | 24.32 ± 6.28 | 1148 ± 240.3 | 7354 ± 1288 |\n| PE (Ma et al., 2024) | 5.49 ± 0.58 | 186.7 ± 29.87 | 997.5 ± 133.9 |\n| Orbit Correction (Ours) | 0.215 ± 0.025 | 2.106 ± 0.116 | 6.975 ± 0.421 |\n| Reward Scaling (Ours) | 0.024 ± 0.002 | 0.063 ± 0.004 | 0.111 ± 0.008 |\n\nWhile the cost increases for all methods as the number of transitions grows, our method clearly scales better. It is important to note that the time differences accumulate over the entire training duration. Our implementation of positional encoding is adapted from `torch_geometric.transforms.AddRandomWalkPE`.\n\n---\n## **Training Time Comparison**\n\nWe report the total training time for each method, including positional encoding (PE) method of Ma et al. (2024). The results for each training step are summarized in the table below.\n\n|  | 1000 Steps (s) | 3000 Steps (s) | 5000 Steps (s) |\n| --- | --- | --- | --- |\n| Transition Correction | 1338 ± 79 | 4122 ± 168 | 6859 ± 80 |\n| PE (Ma et al., 2024) | 1322 ± 44 | 4001 ± 131 | 6604 ± 152 |\n| Orbit Correction (Ours) | 1176 ± 32 | 3577 ± 100 | 5987 ± 168 |\n| Reward Scaling (Ours) | 1178 ± 31 | 3584 ± 97 | 5999 ± 146 |\n\nWhile PE is faster than Transition Correction (which performs several isomorphism tests), our methods (Reward Scaling, Orbit) are faster. We used one processor with one GPU (24GB TITAN RTX GPU, Intel Xeon Silver 4216 CPU).\n\nOverall, our method has lower computational cost compared to other methods and scales better.", "claims_and_evidence": "I agree that the problem identified by the authors is important but has not been well studied. I also find the proposed method to be theoretically sound and a practical approach to addressing graph symmetry.", "methods_and_evaluation_criteria": "The illustrative example and synthetic graphs effectively demonstrate that the proposed Reward Scaling mitigates the bias present in vanilla GFlowNets, which do not account for graph symmetry. Additionally, they show that this strategy performs as well as transition correction while requiring significantly fewer computational resources.", "theoretical_claims": "The theoretical claim that handling only orbit equivalence, instead of transition equivalence, is sufficient, is valid. Additionally, their modified TB and DB loss, derived through automorphism correction based on ratios, is sound.", "experimental_designs_or_analyses": "The experiments using illustrative examples and synthetic graphs validate the proposed reward scaling method, showing competitive results compared to transition correction, which requires high computational cost. Additionally, experiments on molecule generation demonstrate the practicality of this method.", "relation_to_broader_scientific_literature": "Since this work addresses the challenges commonly encountered in graph generation tasks using GFlowNets and successfully solves them with minimal computational cost, I believe it has the potential to make a significant impact in this area.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The presentation of this paper is clear and easy to follow, making it accessible to readers with varying levels of expertise in the field.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1) I have a remaining concern regarding the method's reliance on 'bliss' for calculating the number of automorphisms. I believe it may occasionally produce incorrect outputs. Could you provide a sensitivity analysis to assess the impact of incorrect automorphism calculations and demonstrate the robustness of the proposed method?\n\n2) Could you provide the total training time compared to exact transition correction or prior work using positional encoding to demonstrate the significance of this method?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9JN0ilanCD", "reviewer": "Reviewer_x1XU", "summary": "This paper aims to rectify equivalent actions in the graph generation process of GFlowNet. In GFlowNet’s graph generation, actions that result in identical graphs are considered distinct actions, leading to incorrect learning of their probabilities. The paper presents a theoretical framework for these actions and proposes a solution using reward scaling to correct them. The effectiveness of this approach is validated through both synthetic and real-world experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback and for recognizing our work as a significant contribution to the community!\n\n---\n## **Time Comparison with the Positional Embedding (PE)**\n\n**Since PE must be computed at every transition, its computational cost scales poorly with the trajectory horizon.** To evaluate how each method scales with the number of transitions, we sampled random graphs with varying transition requirement. We measured the time spent on only the major components of each method (e.g., computing automorphisms for Reward Scaling). 8-dimensional PEs were computed for the PE method. The table below shows the additional computational cost incurred by each method. \n\nPlot link: https://drive.google.com/file/d/1hhB0TVyHKmclFJ65O__BlX74fRUvNtrS/view?usp=sharing\n\n| Method | 10 Transitions (ms) | 50 Transitions (ms) | 100 Transitions (ms) |\n| --- | --- | --- | --- |\n| Transition Correction | 24.32 ± 6.28 | 1148 ± 240.3 | 7354 ± 1288 |\n| PE (Ma et al., 2024) | 5.49 ± 0.58 | 186.7 ± 29.87 | 997.5 ± 133.9 |\n| Orbit Correction (Ours) | 0.215 ± 0.025 | 2.106 ± 0.116 | 6.975 ± 0.421 |\n| Reward Scaling (Ours) | 0.024 ± 0.002 | 0.063 ± 0.004 | 0.111 ± 0.008 |\n\n**The experiments clearly show that our methods (Orbit Correction, Reward Scaling) scales much better by significant margins.** Note that the reported time is required for each trajectory and accumulates over the course of training.\n\nThis indicates that exponential complexity of our method is not the current bottleneck in GFlowNets. We can compute the size of automorphisms in just a few milliseconds, even for graphs with thousands of nodes—far beyond the scale of current applications, which involve fewer than a hundred nodes.\n\n---\n## **Clarification of the Theorem 4.4**\n\nYour understanding of the theorem is correct: the flow constraints must be satisfied for all actions and states. Thank you for giving us the opportunity to clarify this, and we will further revise the manuscript in the updated version.\n\n---\n## **On Atom-based Generation Task**\n\nYour conjecture suggests that symmetries are uncommon in large, real-world molecular graphs, explaining the limited improvement in the atom-based task. We observed that the average symmetries in the synthetic environment is 2.6, whereas molecules in the QM9 training dataset have an average symmetry of 1.3. As you pointed out, this partly explains the limited improvement in the atom-based task. However, a few important points are worth noting:\n\n- Our method does not inherently guarantee improved sample diversity, as this depends on the reward landscape.\n- The average symmetry of molecules in the ZINC250k dataset is 2.44, despite containing larger molecules than QM9 (38 atoms vs. 9 atoms). Additionally, the Spearman correlation between the number of atoms and symmetry is 0.08 in ZINC250k, indicating that real-world molecular graphs do not necessarily exhibit fewer symmetries as they grow larger.\n- For larger graphs, where only fragment-based generation is practical, what matters is the symmetry of fragments, as demonstrated in our paper.\n\n---\n## **On the Performance of Reward Scaling in Figure 3(c)**\n\nYou are correct in pointing out that reward scaling only corrects the terminal probabilities, while the intermediate probabilities remain incorrect. In contrast, both transition and orbit correction methods utilize the correct intermediate probabilities. **This explains the performance gap between Reward Scaling and Orbit Correction with detailed balance, as it depends on intermediate probabilities.** As mentioned in the paper, this provides additional signal, leading to faster convergence.\n\n---\n## **On Outliers in Figure 3(a)**\n\nWe are happy to elaborate on this. **It turns out that the previous experiment stopped training too early.** We resumed training from the last checkpoint with a larger batch size and a lower learning rate, obtaining an almost straight line!\n\nSee the plot in link: https://drive.google.com/file/d/1IHdLn5Ht4zlZ_frqeEOk31X-F-rrIKzC/view?usp=sharing\n\n**In addition, outliers in the Fig. 3(a) corresponds to to graphs that are challenging to represent using GNNs**; compare Figure 3(a) with Figure 10. As mentioned in the paper, the expressive power of the GNN is another source of incorrect learning, as it can give the same representation for actions in different orbits. \n\nYour suggestion to use the off-diagonal elements of the random walk matrix is insightful. However, in this simple environment, shortest-path lengths provide sufficient information to distinguish different actions. The main limitation was that the information is processed by a simple MLP with only one hidden layer. We observed similar learning dynamics with the random walk matrix. While other approaches could address this issue, the current setup already serves its illustrative purpose.\n\nWe hope this clarifies our points and addresses your concerns.", "claims_and_evidence": "The theoretical claims presented in this paper are substantiated by detailed proofs presented in the appendix. The experiment settings are outlined in the main text, while the experiment details are further elaborated upon in the appendix.", "methods_and_evaluation_criteria": "Graph generation is a common use case of GFlowNets, and the existence of equivalent actions is a common problem in related tasks like atom-based and fragment-based molecule generation. The authors propose reward scaling as a simple and effective solution to this issue. However, I have a potential concern with this approach: its exponential complexity could limit its scalability to large and symmetric graphs. In contrast, the positional encoding approach proposed by Ma et al. has polynomial time complexity. While Ma et al. didn’t provide their code, it would be helpful for the authors to compare the proposed reward scaling approach with Ma et al.’s approach in different scales. Specifically, the authors could compare the following two methods:\n1. The proposed reward scaling approach, which requires computing the automorphism group of terminal graphs.\n2. Computing the random walk positional encodings of each graph in the trajectory, e.g., using the `torch_geometric.transforms.AddRandomWalkPE` function from the PyG package. Since Ma et al. didn’t provide their code implementation, the authors don’t need to use positional encodings to check for orbit equivalent actions.", "theoretical_claims": "I reviewed the theoretical proofs and didn’t find any errors on my own. By the way, in Theorem 4.4, when you mention that the state-action flow constraints $F(s)p_{\\bar{\\mathcal{A}}}(a|s)=F(s’)p_{\\bar{\\mathcal{A}}}(a|s’)$ are satisfied, do you mean that they should be satisfied for every possible action $a$ that leads from $s$ to $s’$? It would be clearer if you could clarify this in the theorem statement to prevent any confusion.", "experimental_designs_or_analyses": "I’ve thoroughly examined the soundness of all experiment settings. The proposed method appears to be effective in generating synthetic and fragment-based molecules. However, it shows limited improvement in generating atom-based molecules. My understanding is that symmetries are uncommon in real-world molecule graphs, and as the graph size increases, these symmetries become even rarer. Consequently, the proposed method may not scale well to large-scale graphs. The authors could validate this by measuring the ratio of equivalent actions in their tasks. This could potentially restrict the scalability of the proposed approach to large-scale tasks.\n\nAdditionally, I have some concerns regarding the synthetic experiment results:\n- In Figure 3(c), why is the performance of reward scaling consistently lower than transition and orbit correction? I suspect that the reward scaling approach only corrects the terminal probabilities, while the intermediate probabilities remain incorrect. Therefore, for methods that rely on intermediate probabilities, such as detailed balance, the performance would still be negatively impacted. This limitation is particularly significant considering that detailed balance outperforms trajectory balance in your task.\n- In Figure 3(a), why are there some outliers that deviate from the straight line? From your theoretical analysis, both reward scaling and transition correction are expected to yield perfect terminal probabilities. Consequently, I would anticipate the predicted probabilities in Figure 3(a) to form a perfect straight line.", "relation_to_broader_scientific_literature": "This paper makes a significant and broad contribution to the application of GFlowNets in graph generation tasks. In theory, any application of GFlowNets in this domain should incorporate these correction methods to ensure accurate prediction of rewards.", "essential_references_not_discussed": "I couldn’t find any missing essential references.", "other_strengths_and_weaknesses": "The strengths and weaknesses of this paper have been thoroughly discussed in the preceding points, and I have nothing further to contribute.", "other_comments_or_suggestions": "A minor point on Appendix H.2: you mentioned augmenting edge-level representations with shortest-path lengths. However, shortest-path lengths aren’t very expressive, and there are many edge cases where non-equivalent edges in the same graph can have the same shortest-path lengths. I suggest augmenting edge-level representations with the off-diagonal elements of the powers of the random walk matrix. As per results from Ma et al, this approach should yield nearly perfect performance.", "questions_for_authors": "My questions for this paper are listed in the preceding points.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the symmetry-induced bias in GFlowNets by proposing a reward scaling method based on graph automorphisms. While this paper is heavily inspired by a prior work (Ma et al., 2024), the authors clearly demonstrate improved scalability and methodological contributions on being able to correct biases without requiring transition-level equivalence checks. Empirical results on synthetic and molecular tasks support the method’s effectiveness. Overall, I recommend acceptance.
Decision: Accept (poster)