Let the Flows Tell:  Solving Graph Combinatorial Problems with GFlowNets
Authors: Dinghuai Zhang
Hanjun Dai
Nikolay Malkin
Aaron Courville
Yoshua Bengio
Ling Pan
Venue: NeurIPS 2023 spotlight (2023)
Keywords: graph; combinatorial optimization; sampling; gflownets
TL;DR: We propose a GFlowNet-based method to efficiently solve graph combinatorial optimization problems.

Abstract: Combinatorial optimization (CO) problems are often NP-hard and thus out of reach for exact algorithms, making them a tempting domain to apply machine learning methods. The highly structured constraints in these problems can hinder either optimization or sampling directly in the solution space.
On the other hand, GFlowNets have recently emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially and have the potential to amortize such solution-searching processes in CO, as well as generate diverse solution candidates.
In this paper, we design Markov decision processes (MDPs) for different combinatorial problems and propose to train conditional GFlowNets to sample from the solution space. 
Efficient training techniques are also developed to benefit long-range credit assignment.
Through extensive experiments on a variety of different CO tasks with synthetic and realistic data, we demonstrate that GFlowNet policies can efficiently find high-quality solutions.
Our implementation is open-sourced at https://github.com/zdhNarsil/GFlowNet-CombOpt.

Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets
Dinghuai Zhang"
Hanjun Dai Google DeepMind
Mila
Nikolay Malkin, Aaron Courville, Yoshua Bengio, Ling Pan Mila
Abstract
Combinatorial optimization (CO) problems are often NP-hard and thus out of reach for exact algorithms, making them a tempting domain to apply machine learning methods. The highly structured constraints in these problems hinder either optimization or sampling directly in the solution space. On the other hand, GFlowNets have recently emerged as a powerful machinery efficiently sample from composite unnormalized densities sequentially and have the potential to amortize such solution-searching processes in CO, well generate diverse solution candidates. In this paper, we design Markov decision processes (MDPs) for different combinatorial problems and propose train conditional GFlowNets to sample from the solution space. Efficient training techniques are also developed benefit long-range credit assignment. Through extensive experiments a variety of different CO tasks with synthetic and realistic data, we demonstrate that GFlowNet policies can efficiently find high-quality solutions. Our implementation is open-sourced at https://ggthub..om com/ Zarssisi Fll.aassl//loleeeeeeeeleeeeeeeee Combbtt
Introduction
Combinatorial optimization (CO) is a branch of op- timization that studies problems of minimizing or maximizing some cost over a finite feasible set. CO problems usually involve discrete structures, such as graphs, networks, and permutations, and require optimizing an objective function subject to discrete constraints in the solution space, which often NP. hard. CO problems have broad applications, includ- ing in medicine, engineering. operations research, and management (Paschos 2010), and have spurred the development of discrete mathematics and theo- retical computer science for century (Kuhn 1955
Figure 1: Illustration of GFlowNet for a toy MIS problem where all the states form DAG. Every trajectory starts from the same initial state (whose vertices all gray). Each transi- tion denotes adding one vertex to the solution set, i.e., changing vertex black. See Sec- tion 3.2 for details.
Kruskal 1956 Ford Fulkerson 1956).
During the past few decades, researchers have devel- oped numerical solvers such as GUROBI (Gurobi Op- [umization 2023) give approximate solutions integer programming. In recent years, interest in learning- baased methods for solving CO problems has grown significantly. These approaches leverage the power of deep networks to learn the inherent structure of CO problems and provide efficient
"Correspondence to dinghuai. zhangmmila.queeeee......
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and effective solutions. One family of machine learning methods utilizes solver-fount solutions to provide a supervised learning (SL) signal for training neural networks (Selsam al. 2018 Gasse et al. 2019 Nair et al., 2020). This line of algorithms requíres expensive precomputation by the numerical solver to produce supervision labels. On the other hand, unsupervised learning (UL.) methods search for the solution without the help of a solution oracle. One branch of UL methods, called probabilistic methods, decodes the heatmap generated from one pass of a neural network to get solutions (Toenshoff et al. | Karalias & Loukas| (020). These methods can achieve fast inference at the cost of a large optimality gap. Another branch of unsupervised methods is reinforcement learning (RL), which iteratively refines or constructs the problem solution with practitioner-specffie
MDPs [ello et al. 2016 Deudon et al. 2018 Wu et al. 2019).
Despite many recent efforts to apply deep RL to CO problems, such approaches have fundamental limitations. For example, due to the symmetry in problem configurations, there could be multiple optimal solutions to the same CO problem (Li et al. 2018). Standard RI. algorithms such as Fujimoto
et al. (2018) are grounded in the nature of cumu ative reward maximization and fail to promote diversity in the solutions. Although engroiy-regularized RI. (Haarnoja et al. 2017 2018 Zhang et al. 2023b) converges to stochastic policy instead of deterministic one, these methods target trajectory-level entropy rather than solution- entropy. Consequently, the agent may get trapped in solutions that can be reached by many trajectories and lack the ability to generate diverse candidate solutions. In addition, the performance of RL methods largely depends on the designed reward function and relies result, it is challenging to apply RL in our problems if only a terminal reward is provided.
dense per-step reward for learning the value functions and policies. As
Although there are attempts to fix these issues (Kwon et al. 2020 Ahn et al., 2020), they are mostly problem-specific and only achieve marginal improvement. In this work, we turn to more principled framework, namely generative flow networks (Bengio et al. 202T, GFlowNets), to search for high- quality diverse candidates in CO problems. GFlowNet is a novel decision- decision-making framework for learning stochastic policies to sample composite objects with probability proportional to given terminal reward, which is suitable for problems where the solution is only related to the terminal state of generative trajectories. We design MDPs for a variety of NP-hard CO problems, where the intermediate states form a flow network in the latent space, and GFlowNet learns agent to sequentially make decisions in this environment (Figure []. Another challenge of applying GFlowNets is learning from long trajectories. In large-scale graph CO problems, the GFlowNet agent will encounter a very long trajectory before termination, rendering the task of credit assignment challenging. To this end, we develop efficient learning algorithms to train GFlowNets from transitions rather than complete trajectories, which greatly helps the learning process, especially in large-scale setups. Through extensive experiments on different CO tasks, we demonstrate the advantage of our proposed GFlowNet approach. In summary, our contributions are as follows:
We design problem-specifie MDP for Gelow training on four different CO tasks.
We propose efficient GFlowNet learning algorithm to enable fast credit assignment for the GFlowNet agents with long trajectories that emerge in our graph CO problems.
The empirical advantage of GFlowNets is validated through experiments on different CO problems.
2 Preliminaries
2.1
GFlowNets
Generative flow networks, or GFlowNets, are variational inference algorithms that treat sampling from target probability distribution sequential decision-making process (Bengio et al. 2021
2023). We briefly summarize the formulation and the main training algorithms for GFlowNets.
We assume that fully observed, deterministic MDP with set of states S and set of actions A C S is given. The MDP has a designated initial state, denoted Sp. Certain states are designated as terminal and have no outgoing actions; the set of terminal states is denoted X. All states in are assumed to be reachable from So by a (not necessarily unique) sequence of actions (see Figure 2 A complete trujectory sequence of states T = (So - 8) > ... -> sn), where 8, E X and each pair of consecutive states is related by action, i.e., Vi (s,, S(41) A.

---

A policy on the MDP is choice of distribution (s(s'|s for each s E S reachable from in a single action A policy induces distribution over complete trajectories via
\ X' over the states s'
(su - 7 Sn)) = II Pr ss)).
O=
The marginal distribution over the final states of complete trajectories is denoted PT a distribution on X' that may in general be intractable to compute exactly, PF (x) Σ (r(r), with the sum taken over all complete trajectories that end in x.
reward function is a mapping X' - R2 which understood as an unnormalized probability mass on the set terminal states (we will typically make the identification R(x) exp( (x()-))) where : + I is an energy function and T > is a temperature parameter). The learning problem approximately solved by GelowNet is to fit policy Pr(s'|s) such that the induced distribution Pp (x) is proportional to the reward function, i.e.
PF (x) x R(x) = exp((E(x)/T)-
The policy (s(s' is parametrized as neural network with parameters 0 taking as input and producing the logits of transitioning each possible subsequent states s'. This problem is made difficult both by the intractability of computing PF given Pr and by the unknown normalization constant (partition function) the right side of (T). Learning algorithms overcome these difficulties by introducing auxiliary objects into the optimization. Next, we review two relevant objectives.
Detailed balance (DB) The DB objective (Bengio et al. 2023) requires learning two objects in addition to a parametric forward policy (F (s 0) (we omit when it causes no ambiguity):
backward policy, which distribution (s(sss 0) over the parents (predecessors) of any noninitial state in the MDP:
state flow function F(: 0) : Rz0.
The detailed balance loss for a single transition + s' defined as
(D,(s,s':0) log F(s; Prs:ss)
Fis ()ssss))ssss
The DB training theorem states that if (D s'; 0) for all transitions s s', then the policy Pr satisfies [ i.e., samples proportionally to the reward. The manner of selecting transitions - s's on which to minimize (2) is discussed below.
The loss that performs best for the problems in this paper (see 66 in (3.3) is equivalent to DB with particular parametrization of log F(s) that bootstraps learning by expressing the log-state flow as an additive correction partially accumulated negative energy.
Trajectory balance (TB) The TB objective (Malkin al., 2022) features simpler parametrization: in addition to the action policy PF. one learns backward policy PB and only single scalar Ze. an estimator of the partition function corresponding to the initial state flow F(so) the DB parametrization. The TB loss for complete trajectory (so +1
S, x) is
Zo I Pr |s:
(TB(T; 0) log
(3)
R(x) 10-00 (s
The TB training theorem states that if (TB 0) 0 for all complete trajectories т, then the policy Pr satisfies [1). Furthermore, Z then equals the normalization constant of the reward, 2 ExEx R(x). In practice, policies and flows typically output in the log domain, i.e., neural network predicts logits of the distributions Pr (-ls), PB (-Iss) and the log-flows log F(s) and log Z.
Note one can unambiguously write policy distribution over subsequent states not over actions because the MDP is deterministic. Most GFlowNet work uses the equivalent language of directed acyelic graphs. see analysis in Pan et al. (2025b); we use the MDP formalism to be consistent with RL terminology and avoid clashes of notation and language with the graphs that the inputs to CO problems.

---

Training policy and exploration The DB and TB losses depend on individual transitions or trajectories, but leave open the question of how to choose the transitions or trajectories on which they are minimized. A common choice is to train in an on-policy manner, i.e,, rollout trajectories T (r( () and perform gradient descent steps on (T; 0) or on fDB 81+1; for transitions 8,41 in r. In this case, DB and TB have close connections to variational (ELBO maximization) objectives (Malkin et al., (022).
However, an exploratory behaviour policy can also be used, for example, by sampling r from a version of Pr that is tempered or mixed with a uniform distribution (resembles e-greedy exploration in RL).
Note that, unlike policy gradient methods in RL, GFlowNet objectives require no differentiation through the sampling procedure that yields т. The ability to stably learn from off off-policy trajectories a key advantage of GFlowNets over hierarchical variational models (Zimmermann et al. 2022
Malkin et al. 2023). See related study in Section C
Conditional GFlowNets The MDP and the reward function in GFlowNet can depend on some conditioning information. For example, in the tasks we study, a GFlowNet policy sequentially constructs the solution to a CO problem on graph g, and the set of permitted actions depends on g. The conditional GFlowNets we train achieve amortization by sharing the policy model between different g, enabling generalization to g not seen in training.
2.2 Graph combinatorial optimization problems
We focus on the following four NP-hard CO problems on graphs: maximum independent set (MIS), maximum clique (MC), minimum dominating set (MDS), and maximum cut (MCut). A CO problem can be described with an undirected graph g (V, E), where V is the set of vertices and E is the set of edges. Such problems typically require one to optimize over variables in finite composite space to maximize or minimize some particular graph properties, as follows. Without loss of generality, we assume that all the graph weights equal one for simplicity, as our method can be easily extended to weighted graphs.
Maximum independent set In graph theory, an independent is a of vertices S in given graph structure g where any pair of vertices ji C S are not neighbors i.e., Vi,j E S, (i.j) & E. The MIS problem is find such independent set that has the largest possible size |S].
A clique is subset of the vertices S V where all pairs of vertices are adjacent, i.e., Vi,j E S. (i,j) E E. The MC problem is to find a clique that has the largest size. We also remark that MC can be considered as complementary problem of MIS, in the sense that the MC of any graph is actually the MIS of its complementary graph.
Maximum clique
Minimum dominating set A dominating set 5 S V for graph g is a subset of vertices such that, for any vertex in this graph, it is either in S, or it has a neighbor in S. The MDS problem is to find the smallest dominating set for given graph structure.
Maximum cut Given subset of graph vertices S C V, the cut is defined as the number of edges between S and V S. The MCut problem is to find set of vertices S that maximizes the cut.
3 Methodology
3.1
Optimization as probabilistic inference
CO problem can be seen as a constrained energy minimization problem a discrete composite space arg min Exx), where& E is the target energy function and X' is the solution space or feasible set. This optimization problem can be considered roughly as sampling from an energy- -ased model pi (x) exp ( where T is the temperature parameter that controls the smoothness of the density landscape. Sampling from such highly structured space is non-trivial, therefore we propose to use GFlowNets to amortize this inference process. According to the GelowNet theory, perfectly trained GFlowNet with the reward function R(x)) = exp { (-E(x)/T) will be able to accurately sample from (x). In this way, GFlowNets trained with reasonably small temperature T can be used to search for solutions to given CO problems, as stated below.
Proposition 1. Assume that the GFlowNet is perfectly trained for given temperature T, iee, the training loss over a policy with full support equals zero. Then, T + o0, the distribution sampled

---

(a) Independent set
(b) Clique
(c) Dominating set
(d) Cut
Figure 2: Our proposed MDP designs for different CO tasks. All the tasks aim at set of vertices as the problem solution, thus we use 0/1/2 to represent "not in the set" "in the set" "uunspccified" for each vertex, which corresponds to white black / gray in the figures. For each figure, the first arrow denotes conducting one action (marked with hammer), and the second arrow denotes the designed transition guarantee any intermediate state represents a valid independent set clique/ dominating set / cut. The rightmost graph in each figure shows feasible solution for the CO problem, where all vertices are specified (i.e., belongs to the GFlowNet terminal state space X).
by GFlowNet will converge uniform distribution on X; if - the distribution sampled by GFlowNet will converge to the uniform distribution on optimal solutions to the optimization problem.
Notice that each graph corresponds to one unique sampling problem; thus, here we learn graph conditional GetowNet to amortize this condition distribution p(x px) i.e., every learnable GFlowNet component (like the forward backward policy or the flow function) is conditioned on the graph g.
3.2 Designing Markov decision processes for GFlowNets
This section illustrates the design of appropriate Markov decision process (MDP) formulations for GFlowNet learning; see Figure 2 for a summary.
State For all the CO problems studied in this work, the solution x is subset of vertices for a given binary vector x (x! ..... x E X S {0, 1 where x indicates that the i-th vertex belongs to the set and x = O indicates that it does not. Note that the feasible solution space X' a subset of the full space {0, 13IVI, as some binary vectors encode a vertex set outside the feasible set (e.g., non-independent set in the MIS problem). The solution space is also the GelowNet's terminal state space. The design of the GFlowNet state space is inspired by that in Zhang al. 2022b)) We begin by defining
graph, represented
S ((s),...,,
....., vl). s E 10,1, IV]:
where @ represents an unspecified "void" or "yet unspecified" situation for a particular vertex. superset the terminal state space X. The initial state is the all-void vector So (0, O ....., 2). In our MDP design, we only allow transforming vertex values from void (0) to non-void (0 1) according to problem-specific rules. The trajectory terminates when the entries non-void, i.e., every entry is either 1. Notice that do not need to have explicit stop action in the agent's ''s action space.
Notice that
Notice that not all vectors in that have no void entries lie X. Therefore, we must restrict S so that the of terminal states is exactly the set of vectors encoding feasible solutions X. To be precise, define the state space S to be the set of states S such that there exists at least one E X that can be obtained from s by valid transitions.
Care must be taken to modify the set of permitted actions from each state accordingly, so that actions always produce states in S. This turns out to be doable in the problems we study (as, for example, any subset an independent set is independent). As an example, we next describe our action transition / reward design for the MIS problem. Details for other tasks are deferred to the Appendix B
The initial state is all-void, meaning that the partially constructed independent set is initialized with the empty set. The action of the MIS MDP is simply to choose one void vertex and add it to the current solution set by turning the entry value of the chosen vertex from O to 1.
Action
5

---

8(sg)
Algorithm GFlowNet training algorithm
((x)
Require:
Graph dataset, GFlowNet model
(()))
(
with parameters 0, reward function.
repeat
Sample graph g from dataset;
Sample 7 with the GFlowNet forward
policy Pp g, 0);
Randomly choose transitions from 7 to create buffer B;
Figure 3: Illustration of transition- based GelowNet training. We break complete trajectories into transi- tions, and then randomly choose some of the them to form buffer to train the GFlowNet agent. We use denote the terminal state Sn. (-) denotes designed intermediate learning signals.
0 + (s--'' |EB (o
(as Equation 6
Update 0 with some optimizer; until some convergence condition
Transition To ensure that the state can always be completed to an independent set, it is essential to carefully handle the actions taken. When void vertex is chosen and its entry value is modified to we also update the entry values of all its neighboring vertices to O, which excludes the possibility of getting two adjacent vertices the following steps. This proactive approach ensures that the independent set constraint is not violated in subsequent steps.
We remark that the feasible set X' in this problem consists not of all independent sets, but of order- maximal independent sets, i.e., those to which no vertex can be added while keeping them independent. Non-order-maximal maximal independent sets cannot be constructed with such transitions.
Reward We set the log reward to be the resulting independent set size, i.e., E(x) = -|x/1, where [x|1 denotes the & norm, i.e., the number of I's in the binary vector x.
3.3 Factors affecting training efficiency
Transition-based GelowNet training
Most successful GFlowNet implementations (e.g., those in https://github. http:/giituuccoomGii/ com//GNN/ NOrgg require a complete trajectory to compute the training loss and its gradient. Existing implementations with DB also specify the training loss at the trajectory level:
n-1
[(r: 0) = n
Σ DD (st, 81+1;0), T == (So, s1,...,,.... sn);
and calculate the parameter gradient update with (r)) [T 0)] with some potentially off- policy distribution =(7). This is also the case for other GFlowNet algorithms, such as flow matching (Bengio et al. 2021 and subtrajectory balance (Madan et al. 2023
These implementations work well for moderate-scale trajecto- ries, previous GFlowNet works have shown (Malkin et al.] 2022: Madan et al. 2023). However, for very long trajectories, such a design hinders efficient training: for single complete trajectory which contains n transitions, one needs n calls of the neural network forward passes and storing all the intermediate feature maps and parameters in the GPU memory. Fach forward pass contains multiple message passing operations on given graph structures, which is computationally expensive (linearly increasing with rı) in terms of speed and memory storage. In our experiments, we encounter large-scale problems where the trajectory as long as 400 in length; nonetheless, with such graphs, our adopted graph neural networks can only support forward and backward passes with batch size approximately 250 (which is much smaller than 400) on a 40 GB GPU memory device. This prohibits the usage of these trajectory- GFlowNet training objectives on large-scale graph applications. addition, the correlation between consecutive samples may incur stability issues (Mnih et al. 2015).
N Nethod
06 Ba)
TB
10 15
20
Epoch
Figure 4: Comparison between dif- ferent GFlowNet variants.

---

To this end, we turn to use transition based GelowNet training approach wihtout the knowledge of complete trajectories. which is first proposed in Deleu et al. (022) and has shown effective- ness in Nishikawa-Toomenn
et al. (2022); ; Deleu et al. (2023). We randomly sample B transi- 1=== from complete trajectory and construct detailed balance-based loss:
tions B = [(s s )}
Σ B ((0) = 8 A=1 and limited GPU memory, which also converges faster. A corresponding schematic illustration of the algorithm can be found in Figure 3 In Figure 4 we show a comparison of learning efficiency between transition-basee and trajectory- based GFlowNet implementations, where "-traj" denotes the latter variant. Different methods here share similar speed for one epoch training, thus from the figure we can see that transition- approaches learn more efficiently. Besides the improved computation efficiency, our transition-based approach is also more memory efficient - as the memory occupation is proportional to the batch size instead of trajectory lengths (as for trajectory- based implementation), demonstrating its applicability to long-horizon problems.
O). This enables GFlowNets to be efficiently trained with long trajectories
Improving credit assignment with intermediate learning signals For normal GFlowNet training methods, the only learning signal in a trajectory comes from the terminal states and their associated reward values. This results in a relatively slow credit assignment process, and is inefficient to propagate information from near- terminal states to the early states due the difficulty of attributing credits of each action in long trajectory. The ability to learn from incomplete trajectories is especially important in our proposed transition-baat based training. since we are not using all the transitions from the complete trajectories. Therefore, we incorporate intermediate learning signals via the forward- looking (Pan et al.! 2023a
FI.) technique:
(s.s' (-E(s) + log F(s; 0) + log Pr E(s') log F)):0)) log Pn(s)ss:0)) (6)
where : + R a continuation of the reward energy E(-) : X + IR which is only defined in the terminal state space X. For simplicity, here we ignore the conditioning on graph structure This FL method enables dense supervision signals to GFlowNet training. resulting faster credit assignment as can be seen in Figure Notice here that we need to design a handcrafted reward {(s) for all possible latent states to reflect our estimation on intermediate signals. For MIS problems, we naturally define -E(s) to be the number of vertices in the current set, i.e. the number of 1 entries in state s. This semantically coincides with the definition of an MIS terminal reward. We defer the intermediate reward design for other tasks to the Appendix. The effectiveness of FL against the DB or TB algorithms can be seen in Figure We summarize the resulting algorithm in Algorithm
Related work
GFlowNets GFlowNets were intended as diversity-seeking samplers for biological sequence and molecule design, an application area that continues to motivate research (Bengio et al. 2021 Jain ct al., 2022 2023b Shen et al.) 2023 Jain et al. 2023a). However, much recent work has used GFlowNets as samplers for Bayesian posterior distributions, e.g., causal discovery (Deleu et al. 2022;
et al. 2022 Atanackovic et al.) (023), amortized variational EM with discrete latents (Hu et |l.| (023), ), neurosymbolic inference (van Krieken et al., 2022), and feature attribution in classifiers (Li al. 2023). The theory and optimization techniques for GFlowNets have also evolved,
with improved training objectives and exploration techniques (Malkin et al., 2022 Madan et al.) [2023]
Pan al. 2022 2023a Shen al. 2023), better understanding of their connections variational 2022a
methods (Zhang et al.
Malkin et al.) 2023 Zimmermann et al. 2022), and extensions to
stochastic (Zhang al.
2023c
Pan et al. 2023b) and continuous (Lahlou al. 2023) MDPs.
ML for combinatorial optimization The surge of machine learning for CO problems alleviates
the reliance on cand-crafted heuristics while enabling generalization to new instances (Bengio et al. 2018, Cappart et al. 2021). Some methods (Li et al. 2018 Gasse et al. 2019 Gupta et al. 2020
Sun & Yang 2023) rely on supervised information from expert solvers, which can be hard to obtain.
Alternative approaches that leverage reinforcement learning (Dai et al. | [2117] Kool et al., 2019 Chen
& Tian 2019, Yolcu & Póczos, 2019, Ahn et al.) 2020 Delarue et al. 2020; Drori et al. 2020) or other unsupervised learning objectives (Karalias& & Loukas 2020 Sun et al. 2022 Wang et al.) 2022) broaden the applicability of learning for CO problems. However, the code-collapse issue might hinder the diversity and thus the solution coverage. In this regard, GFlowNets are easy to train while also designed for discovering multiple modes. As the first example to show the advantage of
7

---

Table 1: Max independent set experimental results. We report the absolute performance, approxi- mation ratio (relative to KAMIS), and inference time. All algorithms fall into three categories: OR (operations research), SL. (supervised learning), and UL (unsupervised learning). denotes no
reasonable result is achieved by the corresponding algorithm in 10 hours. Time shown H:M:S.
SMALL
LARGE
SATLIB
METHOD
TYPE
SIZE f
DROP L
TIME
SIZE f
DROP +
TIME
SIZE 1
DROP
TIME J
GUROBI KAMIS
OR
19.98
0.01%
47:34
40.90
5.21%
2:10:26
425.95
0.00%
3:43:19
OR
20.10
0.00%
1:24:12
43.15
0.00%
2:03:36
425.96
0.00%
4:15:41
PPO
UL
19.01
5.42%
1:17
32.32
25.10%
7:33
421.49
1.05%
13:12
INTEL
SL
18.47
8.11%
13:04
34.47
20.12%
20:17
DGL
SL
17.36
13.61%
12:47
34.50
20.05%
23:54
OURS
UL
19.18
4.57%
0:32
37.48
13.14%
4:22
423.54
0.57%
23:13
GelowNets in CO problems, Zhang et al. (2023a) tackles the robust job scheduling problem that is central to compiler optimization. In our paper, we formalize CO under the GFlowNet framework with principled MDP design and demonstrate its effectiveness in a wide range of graph CO tasks.
Experiments
We conduct extensive experiments various graph CO tasks to demonstrate the effectiveness of the proposed Get approach. For MIS problems, we follow the setup in the MIS benchmark from Böther et al. (2022), while for other tasks, we follow the experimental setup in [un et al. (0022)
Datasets As Dai et al. 2021) have pointed out that problems in existing synthetic graph data are relatively easy for MIS and MC, we take the more complicated RB graphs (Xu & Li (0000 following Karalias & Loukas (2020). For realistic data, we take the SATLIB dataset (Hoos et a 2000), which reduced from SAT instances in conjunctive normal form. For the other two tasks, namely MDS
and MCut, we adopt BA graphs (Barabási & Albert 1999) following Sun et al. (2022) For all types of synthetic graph data, generate scales of datasets (denoted SMALL and LARGE), which respectively contain around 200 to 300 vertices and 800 to 1200 vertices.
Baselines For MIS problems, compare with the baselines in the MIS benchmark. For classical operation research (OR) methods, we include a general-purpose mixed-integer program solver (GurOBI) and MIS-specific solver (Lamm al.. 2017 KAMIS). For learning-based methods, we compare with a reinforcement learning-based PPO method (Ahn et al. 2020), and supervised learning with tree search refinement, in different implementations (Li al. (2018) INTEL) and BBöhhe et al.) (2022 DGL)). For the non-MIS tasks, we compare with the GUROBI solver, two heuristic methods which are greedy and mean-field annealing (Bilbro et al. 1988] MFA), and two state-of- -fate-of-the-rt -hehhartt probabilistic methods (Karalias & Loukas 2020) and the annealed version (Sun et al.) 2022). We use ERDOS and ANNEAL to denote these two learning-base based methods. For max-cut problems, we also adopt semi- semi-definite programming baseline (coined SDP in the result tables) which aims at relaxation of the MCut task. We set its maximal running time to 10 hours. For the methods already contained in the MIS benchmark, we train them from scratch and report performance with the same protocol; for other algorithms, we write our own implementations and test them in the same way.
Results & analysis We evaluate both the performance and the inference time and report the mean value of the objective (e.g., set size in MIS) and the approximation ratio relative to the best-performing non-ML solver, treated as an oracle 3 The time denotes the total latency of evaluating on the test set. The best results among non-OR methods are marked in bold. MIS results are demonstrated in [able where the problem-specific solver KAMIS is served as the gold standard for calculating the drop. For MIS methods, the larger the size of the independent set found, the better the algorithm. The "UL" (unsupervised learning) refers to the algorithms that do not need labels (i.e., solutions found by solvers) in the training set. For SATLIB, none of the supervised learning baselines can
'The approximation ratio computed on the total cost aggregated over the test set and is defined as the analle
DROP (1 algaidiim for maximization problems and the GAP (1 algorihh for minimization problems.
8

---

Table Max clique, min dominating set, and max cut results on small graphs (V) between 200 and 300). We report absolute performance, approximation ratio, and inference time. All algorithms fall into three categories: OR (operations research), (heuristic), and UL (unsupervised learning). The time latency is shown in the form of hour:minute:second.
MC
MDS
MCUT
METHOD
TYPE
SIZE
DROP
TIME +
SIZE
GAP
TIME
SIZE
DROP J
TIME
GUROBI
OR
19.05
0.00%
1:55
27.89
0.00%
1:47
732.47
0.00%
13:04
SDP
OR
700.36
4.38%
35:47
GREEDY
13.53
28.98%
0:25
37.39
25.41%
2:13
688.31
6.03%
0:13
MFA
14.82
22.15%
0:27
36.36
23.29%
2:56
704.03
3.88%
1:36
ERDOS
UL
12.02
36.90%
0:41
30.68
9.09%
1:00
693.45
5.33%
0:46
ANNEAL
UL
14.10
25.98%
0:41
29.24
4.62%
1:01
696.73
4.88%
0:45
OURS
UL
16.24
14.75%
0:42
28.61
2.52%
2:20
704.30
3.85%
2:57
Table 3: Max clique, min dominating set, and max results large graphs (whose [V] is between 800 and 1200). We use the same format as Table
MC
MDS
MCUT
METHOD
TYPE
SIZE f
DROP +
TIME
SIZE 4
GAP 4
TIME
SiZE
DROP
TIME
GUROBI
OR
33.89
0.00%
16:40
103.80
0.00%
13:48
2915.20
0.00%
1:05:29
SDP
OR
2786.00
4.43%
10:00:00
GREEDY
H
26.71
21.17%
0:25
140.52
26.13%
35:01
2761.06 .06
5.29%
3:07
MFA
11
27.94
17.56%
2:19
126.56
17.98%
36:31
2833.86
2.79%
7:16
ERDOS
UL.
25.43
24.96%
2:16
116.76
11.10%
3:56
2870.34
1.54%
2:49
ANNEAL
UL
27.46
18.97%
2:16
111.50
6.91%
3:55
2863.23
1.79%
2:48
OURS
UL
31.42
7.29%
4:50
110.28
5.88%
32:12
2864.61
1.74%
21:20
achieve meaniningful results (average MIS size < 400) within 10 hours, thus use "_" to mark performance. One can see that GelowNets surpass all the learning-bas -based baselines in the sense of achieving the largest independent set solution.
For the MC & MDS & MCut problems, we exhibit the experimental results on small graphs in Table and results on large graphs Table where GUROBI serves as the gold standard to calculate the performance drop ratio. Notice that for MDS problems, the smaller the vertex size result, the better performance, which is opposite to other tasks. We observe that GFlowNet outperforms other baselines across different tasks and problem scales, with the only exception being the large-scale max-cut problem. This reflects the fairly universal effectiveness the proposed method. We also notice that GFlowNets require longer inference time compared to other methods. This is because the GFlowNet only adds one vertex into the set at each step. thus needs multiple steps to output vertex set solution. In contrast, probabilistic methods such as "Erdōs goes neural" (Karalias & Loukas 2020) only require one neural network forward pass during inference time to give a coarse how this compares with sequential generation approach in GFlowNets, where each decision is taken in the context of the previously already taken decisions, ensuring a better coordinated of decisions.
estimate of the solution. We
Ablation study We now conduct in-depth ablation studies evaluate the key design choices in our method. We first study the difference between series of GFlowNet variants in Figure 4 based on the MIS task with small scale graph data. We compare transition-based FL. trajectory- transition-bes based DB, trajectory-based DB, and TB (which only has trajectory-based implementation). Our result indicates that GFlowNet's transition-bast based FL implementation learns the fastest for CO tasks, which supports our modeling choice in Section 3.3 Figure 5 in Section C summarizes additional ablation studies including the temperature annealing, off-policy exploration strategy, and network architectures. We vary the GFlowNet's temperature coefficient which scales the temperature hyperparameter; we ablate the off-policy exploration during the rollout stage of GFlowNet training: also ablate the GelowNet architecture. Our results indicate that the GelowNet is robust to
FL,

---

wide range of hyperparameters, making it appealing to be applied to different CO problems, which validates the effectiveness of our proposed methodology from another perspective.
Conclusion
Our work focuses on the challenges of solving CO problems using unsupervised learning approaches. This work contributes to this growing field by proposing to apply the principled GFlowNet decision- making framework to CO tasks. By combining the power of probabilistic inference and sequential GFlowNets offer a promising direction for finding a diverse set of high-quality candidate solutions in CO problems. Technically, we have developed problem-specifis MDPs and efficient learning algorithms to address the challenges associated with learning from long trajectories, making approach practical and scalable in large-scale setups. Our extensive numerical results showcase the effectiveness and efficiency of GFlowNets in solving NP-hard level CO problems, highlighting their abillity generate a set of diverse nigh-quaiity solutions. We believe that our work opens up new possibilities for addressing the limitations of existing approaches and paves the way for future research at the intersection of machine learning and combinatorial optimization.
Acknowledgement
The authors are thankful to Yuandong Tian, David Wei Zhang, Haoran Sun, Zhiqing Sun, Taoan Huang, Sophie Xhonneux, and Zhaoyu Li. Yoshua acknowledges funding from CIFAR, NSERC, Intel and Samsung. Aaron is supported by Hitachi, Samsung, Canadian Research Chair and CIFAR. Dinghuai acknowledges Daozhen Lin for being his tour guide during their visit to beautiful Italy,
References
Ahn, Sungsoo, Seo, Younggyo, and Shin, Jinwoo. Learning what to defer for maximum independent sets. International Conference on Machine Learning (ICML), 2020.
Atanackovic, Lazar, Tong, Alexander, Hartford, Jason, Lee, Leo J., Wang, Bo, and Bengio, Yoshua. DynGFN: Bayesian dynamic causal discovery using generative flow networks. arXiv preprint 2302.04178, 2023.
Barabási, Albert-Laszlo and Albert, Reka. Emergence of scaling in random networks. Science, 286 5439:509-12, 1999.
Bello, Irwan, Pham, Hieu, Le, Quoc V., Norouzi, Mohammad, and Bengio, Samy. Neural combinato- rial optimization with reinforcement learning. arXiv preprint 1,09900, 2016.
Bengio, Emmanuel, Jain, Moksh, Korablyov, Maksym, Precup, Doina, and Bengio, Yoshua. Flow network based generative models for non-iterative diverse candidate generation. Neural Information Processing Systems (NeurIPS), 2021.
Bengio, Yoshua, Lodi, Andrea, and Prouvost, Antoine. Machine learning for combinatorial optimiza- tion: methodological tour d' d'horizon. Eur. J. Oper. Res., 290:405-421, 2018.
Bengio, Yoshua, Deleu, Tristan, Hu, Edward J., Lahlou, Salem, Tiwari, Mo, and Bengio, Emmanuel. Gflownet foundations. Journal of Machine Learning Research (JMLR), 2023.
Bilbro, Griff L., Mann, Reinhold, Miller, Thomas K., Snyder, Wesley E., van den Bout, David E., and White, Mark W. Optimization by mean field annealing. Neural Information Processing Systems (NIPS), 1988.
Böther, Maximilian, Kißig, Otto, Taraz, Martin, Cohen, Sarel, Seidel, Karen, and Friedrich, Tobias. What's wrong with deep learning in tree search for combinatorial optimization. International Conference on Learning Representations (ICLR), 2022.
Cappart, Quentin, Chételat, Didier, Khalil, Elias, Lodi, Andrea, Morris, Christopher, and Veličković. Petar. Combinatorial optimization and reasoning with graph neural networks. International Joint Conference on Artificial Intelligence (IJCAI), 2021.
Chen, Xinyun and Tian, Yuandong. Learning to perform local rewriting for combinatorial optimiza- tion. Neural Information Processing Systems (NeurIPS), 2019.
10

---

Dai, Hanjun, Khalil, Elias B., Zhang, Yuyu, Dilkina, Bistra, and Song, Le. Learning combinatorial optimization algorithms over graphs. Neural Information Processing Systems (NIPS), 2017.
Dai, Hanjun, Chen, Xinshi, Li, Yu, Gao, Xin, and Song, Le. A framework for differentiable discovery of graph algorithms. 2021.
Delarue, Arthur, Anderson, Ross, and Tjandraatmadja, Christian. Reinforcement learning with combinatorial actions: An application to vehicle routing. Neural Information Processing Systems (NeurIPS), 2020.
Deleu, Tristan, G'ois, Ant' onio, Emezue, Chris C., Rankawat, Mansi, Lacoste-Julien, Simon, Bauer, Stefan, and Bengio, Yoshua. Bayesian structure learning with generative flow networks. Uncer- tainty in Artificial Intelligence (UAI), 2022.
Deleu, Tristan, Nishikawa-Toomey, Mizu, Subramanian, Jithendaraa, Malkin, Nikolay, Charlin, Laurent, and Bengio, Yoshua. Joint bayesian inference of graphical structure and parameters with a single generative flow network. ArXiv, abs/2305.19366 2023. URL https://api
semanticscholat org/ ( 258987383
Deudon, Michel, Cournut, Pierre, Lacoste, Alexandre, Adulyasak, Yossiri, and Rousseau, Louis- Martin. Learning heuristics for the tsp by policy gradient. In Integration of Al and OR Techniques in Constraint Programming, 2018.
Drori, Iddo, Kharkar, Anant, Sickinger, William R., Kates, Brandon, Ma. Qiang, Ge, Suwen, Dolev, Eden. Dietrich, Brenda L, Williamson, David P., and Udell, Madeleine. Learning to solve combinatorial optimization problems on real-world graphs in linear time. 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 19-24, 2020.
Ford, Lester Randolph and Fulkerson, Delbert Ray. Maximal flow through a network. Canadian Journal of Mathematics, 8:399 - -004, 1956.
Fujimoto, Scott, Hoof, Herke, and Meger, David. Addressing function approximation error in actor-critic methods. International Conference on Machine Learning (ICML), 2018.
Gasse, Maxime, Chételat, Didier, Ferroni, Nicola, Charlin, Laurent, and Lodi, Andrea. Exact combi- natorial optimization with graph convolutional neural networks. Neural Information Processing Systems (NeurIPS), 2019.
Gupta, Prateek, Gasse, Maxime, Khalil, Elias, Mudigonda, Pawan, Lodi, Andrea, and Bengio, Yoshua. Hybrid models for learning to branch. Neural Information Processing Systems (NeurIPS), 2020.
Gurobi Optimization, LLC. Gurobi Optimizer, https:/ httpe///wwww.u.ob.. com
2023.
Haarnoja, Tuomas, Tang, Haoran, Abbeel, Pieter, and Levine, Sergey. Reinforcement learning with deep energy-based policies. International Conference on Machine Learning (ICML), 2017.
Haarnoja, Tuomas, Zhou, Aurick, Abbeel, P., and Levine, Sergey. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. International Conference on Machine Learning (ICML), 2018.
Hoos, Holger H., Stützle, Thomas, Gent, Ian P., van Maaren, Hans, and Walsh, Toby. SATLIB: An online resource for research on SAT. 2000.
Hu, Edward J., Malkin, Nikolay, Jain, Moksh, Everett, Katie, Graikos, Alexandros, and Bengio, Yoshua. GFlowNet-EM for learning compositional latent variable models. International Conference on Machine Learning, 2023.
Jain, Moksh, Bengio, Emmanuel. García, Alex, Rector-Brooks Jarrid, Dossou, Bonaventure F. P.,
Ekbote, Chanakya Ajit, Fu, Jie, Zhang. Tianyu, Kilgour, Micheal, Zhang, Dinghuai, Simine. Lena. Das, Payel, and Bengio, Yoshua. Biological sequence design with GFlowNets. International Conference on Machine Learning (ICML), 2022.
Jain, Moksh, Deleu, Tristan, Hartford, Jason, Liu, Cheng-Hao, Hernández-Garrda, Alex, and Bengio, Yoshua. GFlowNets for Al-driven scientific discovery. Digital Discovery, 2023a.

---

Jain, Moksh, Raparthy, Sharath Chandra, Herrandez-Gariia, Alex, Rector-Brooks, Jarrid, Bengio. Yoshua, Miret, Santiago. and Bengio, Emmanuel. Multi-objective gflownets. International Conference on Machine Learning (ICML), 2023b.
Karalias, Nikolaos and Loukas, Andreas. Erdos goes neural: an unsupervised learnigg framework for combinatorial optimization on graphs. Neural Information Processing Systems (NeurIPS), 2020.
Kool, Wouter, van Hoof, Herke, and Welling, Max. Attention, learn solve routing problems! International Conference on Learning Representations (ICLR), 2019.
Kruskal, Joseph B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48-50) 1956.
Kuhn, Harold W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83-9) 97, 1955.
Kwon, Yeong-Dae, Choo, Jinho, Kim, Byoungjip. Yoon, Iljoo. Min, Seungjai, and Gwon, Youngjune. POMO: Policy optimization with multiple optima for reinforcement learning. Neural Information Processing Systems (NeurIPS), 2020.
Lahlou, Salem, Deleu, Tristan, Lemos, Pablo, Zhang, Dinghuai, Volokhova, Alexandra, Hermández- Gareía, Alex, Ezzine, Léna Néhale, Bengio, Yoshua, and Malkin, Nikolay. A theory of continuous generative flow networks. International Conference on Machine Learning (ICML), 2023.
Lamm, Sebastian. Sanders, Peter, Schulz, Christian, Strash, Darren, and Werneck, Renato F. Finding near-optimal independent sets at scale. J. Heuristics, 23(4):207-229, 2017. doi: 10.1007/ s10732-017-9337-x htt.hhttp://dii.
1007 10701000000000007711100
Li, Wenqian, Li, Yinchuan, Li, Zhigang, Hao, Jianye, and Pang, Yan. DAG Matters! GFlowNets en- hanced explainer for graph neural networks. International Conference on Learning Representations (ICLR), 2023.
Li, Zhuwen, Chen, Qifeng, and Koltun, Vladlen. Combinatorial optimization with graph convolutional networks and guided tree search. Neural Information Processing Systems (NeurIPS), 2018.
Madan, Kanika, Rector- Rector-Brooks, Jarrid, Korablyov, Maksym, Bengio, Emmanuel, Jain, Moksh, Nica. Andrei Cristian, Bosc, Tom, Bengio, Yoshua, and Malkin, Nikolay. Learning GFlowNets from partial episodes for improved convergence and stability. International Conference on Machine Learning (ICML), 2023.
Malkin, Nikolay, Jain, Moksh, Bengio, Emmanuel, Sun, Chen, and Bengio, Yoshua. Trajectory balance: Improved credit assignment in GFlowNets. Neural Information Processing Systems (NeurIPS), 2022.
Malkin, Nikolay, Lahlou, Salem, Deleu, Tristan, Ji, Xu, Hu, Edward J., Everett, Katie Elizabeth, Zhang, Dinghuai, and Bengio, Yoshua. GFlowNets and variational inference. International Conference on Learning Representations (ICLR), 2023.
Mnih, Volodymyr, Kavukcuoglu, Koray, Silver, David, Rusu, Andrei A, Veness, Joel, Bellemare, Mare G. Graves, Alex, Riedmiller, Martin, Fidjeland, Andreas K, Ostrovski, Georg, et al. Human- level control through deep reinforcement learning. nature, 518(7540):529 533,99533333033 2015.
Nair, Vinod, Bartunov, Sergey, Gimeno, Felix, von Glehn, Ingrid, Lichocki, Pawel, Loboy, Ivan, O'Donoghue, Brendan, Sonnerat, Nicolas, Tjandraatmadja, Christian, Wang, Pengming, Addanki, Ravichandra, Hapuarachchi, Tharindi, Keck, Thomas, Keeling, James, Kohli, Pushmeet, Ktena, Ira, Li, Yujia, Vinyals, Oriol, and Zwols, Yori. Solving mixed integer programs using neural networks. arXiv preprint 2012. 13349, 2020.
Nishikawa- Toommy,, Mizu, Deleu, Tristan, Subramanian, Jithendaraa, Bengio, Yoshua, and Charlin, Laurent. Bayesian learning of causal structure and mechanisms with gflownets and variational bayes. ArXiv, abs/2211.00 1,,0763, 2022. URL. http:httt////ttt //api. semanticscholar. wttp::isscccooaooooooooooaeeeeee org/CorpussDD. 253384724
12

---

Pan. Ling, Zhang, Dinghuai, Courville, Aaron C., Huang. Longbo, and Bengio, Yoshua. Generative augmented flow networks. International Conference on Learning Representations (ICLR), 2022.
Pan. Ling, Malkin, Nikolay, Zhang, Dinghuai, and Bengio, Yoshua. Better training of GFlowNets with local credit and incomplete trajectories. International Conference on Machine Learning (ICML), 2023a.
Pan, Ling, Zhang, Dinghuai, Jain, Moksh, Huang, Longbo, and Bengio, Yoshua. Stochastic generative flow networks. arXiv preprint 2302.09465, 2023b.
Paschos, Vangelis Th. Applications of combinatorial optimization. 2010.
Qiu, Ruizhong, Sun, Zhiqing, and Yang, Yiming. Dimes: A differentiable meta solver for combinato- rial optimization problems. ArXiv, abs/2210.04123, 2022.
Selsam, Daniel, Lamm, Matthew, Bünz, Benedikt, Liang, Percy, de Moura, Leonardo Mendonça, and Dill, David L. Learning SAT solver from single-bit supervision. International Conference on Learning Representations (ICLR), 2018.
Shen, Max W., Bengio, Emmanuel, Hajiramezanali, Ehsan, Loukas, Andreas, Cho, Kyunghyun, and Biancalani, Tommaso. Towards understanding and improving GFlowNet training. International Conference on Machine Learning (ICML), 2023.
Sun, Haoran, Guha, Etash K., and Dai, Hanjun. Annealed training for combinatorial optimization graphs. arXiv preprint 2207. 1542, 2022.
Sun, Zhiqing and Yang, Yiming. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. arXiv preprint 2302.08224, 2023.
Toenshoff, Jan, Ritzert, Martin, Wolf, Hinrikus, and Grohe, Martin. Graph neural networks for maximum constraint satisfaction. Frontiers Artificial Intelligence, 3, 2019.
van Krieken, Emile, Thanapalasingam, Thiviyan, Tomczak, Jakub M. van Harmelen, Frank, and ten
Teije, Annette. A-NeSI: A scalable approximate method for probabilistic neurosymbolic inference. arXiv preprint 2212. 12393, 2022.
Wang, Haoyu Peter, Wu, Nan, Yang, Hang, Hao, Cong, and Li, Pan. Unsupervised learning for combinatorial optimization with principled objective relaxation. Neural Information Processing Systems (NeurIPS), 2022.
Wu, Yaoxin, Song, Wen, Cao, Zhiguang, Zhang, Jic, and Lim, Andrew. Learning improvement heuristics for solving routing problems. IEEE Transactions Neural Networks and Learning Systems, 33:5057-5069, 2019.
Xu, K. and Li. W. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12:93-103, Mar 2000, ISSN 1076-9757. doi: 10.1613/jair.696 URL http:://a htttp://dx..o..orgg//1/. 1613/ jaa.r//jir.... 696
Xu, Keyulu, Hu, Weihua, Leskovec, Jure, and Jegelka, Stefanie. How powerful are graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Yoleu, Emre and Póczos, Barnabás. Learning local search heuristics for boolean satisfiability. Neural Information Processing Systems (NeurIPS), 2019.
Zhang, David, Rainone, Corrado, Peschl, Markus, and Bondesan, Roberto. Robust scheduling with GFlowNets. International Conference on Learning Representations (ICLR), 2023a.
Zhang, Dinghuai, Chen, Ricky T. Q., Malkin, Nikolay, and Bengio, Yoshua. Unifying generative models with GFlowNets and beyond. arXiv preprint 2209.02606, 2022a.
Zhang, Dinghuai, Malkin, Nikolay, Liu, Zhen, Volokhova, Alexandra, Courville, Aaron C., and Bengio, Yoshua. Generative flow networks for discrete probabilistic modeling. International Conference Machine Learning (ICML), 2022b.
13

---

Zhang, Dinghuai, Courville, Aaron C., Bengio, Yoshua, Zheng, Qinqing, Zhang, Amy, and Chen, Ricky T. Q. Latent state marginalization as low-cost approach for improving exploration. International Conference Learning Representations (ICIR), 2023b.
Zhang, Dinghuai, Pan, L.,, Chen, Ricky T. Q., Courville, Aaron C., and Bengio, Yoshua. Distributional GFlowNets with quantile flows. arXiv preprint 2302.05793, 2023c.
Zimmermann, Heiko, Lindsten, Fredrik, van de Meent, J.-W., and Naesseth, Christian A. A variational perspective generative flow networks. Transactions of Machine Learning Research (TMLR), 2022.
14

---

A Notations
Symbol
Description
state space
X
object (terminal state) space, subset of S action transition space (edges s') state in S
A
80
initial state, element of terminal state in X' complete trajectory
T
0
learnable parameter of GFlowNets state flow
F:S + R
PF
forward policy (distribution over children)
PB
backward policy (distribution over parents)
R:X + R
reward function (unnormalized target density) scalar, equal to Exex R(x)
E: R
energy function, equal to - log R(x)
E:S-
energy in state space, provide intermediate learning signals
T
scalar, temperature graph configuration
V
vertex set of graph subset of V. solution to some CO problem
E
edge set of graph g
B MDP designs
In all MDPs, the agent maintain set of vertices the state. This is achieved by assign value among (0, 1, } for each of the vertex, which corresponds to "not in the set" "in the set") ""uspecifiedd" At each step, the agent performs an action, which essentially changing the entry value of one vertex from Ø to specified binary value. After that, the designed transition may modify the value of other unspecified vertices ensure the state will represent feasible solution. The agent will receive terminal reward when no action can be taken (i.e., termination). An illustration of the following descriptions can be found in Figure
B.1 Maximum clique MDP
Here we think of the all-void initial state means that have empty set of vertex at the beginning.
Action The action is choose unspecified vertex and include it in the current This is changing the entry value of that vertex in the state vector representation from @ to 1.
Transition We need to ensure that the current set always represents a clique, thus it is crucial to enforce the connectivity between vertices in the If vertex could potentially join the clique the future, then it must connect to all the vertices in the current set. Hence, after performing action, we identify the vertices that fail to meet this requirement and mark them as This ensures that clique constraint is preserved throughout the generation process.
Reward We set the log reward to be the resulting clique size, iee, E(x) - |x|1. For intermediate state s, we define its intermediate signal by setting -E(s) be the number of 1 in s.
B.2 Minimum dominating set MDP
In MDS, we start with an all-void initial state, where all vertices (which are in unspecified state) are considered to the target dominating set. This different from other MDP designs, where we think of unspecified void state as not in the vertex set. In this representation, the entire vertex set V forms trivial dominating set. Starting from this, we perform actions to remove vertices from the current set but keep it to be dominating set all the time.
15

---

Ppace
Exporitaneee load
of
Figure 5: Ablation study on GFlowNet training. These experiments conduct the small scale MIS task. From left to right: ablation on whether to use temperature annealing, inverse temperature, how much percentage of uniform noise used in off-policy exploration, and number of message passing layers in the graph neural network. These results demonstrate the robustness of GFlowNets against different hyperparameter setups.
Action Each action corresponds to selecting vertex and removing it from the current dominating set. This done by changing the entry value of the chosen vertex from Ø to
Transition For vertex the graph, if it is adjacent to the current set and all of its neighbors also connected to the set, removing this vertex from the set will not violate the dominating set requirement. For other isolated vertices, we change their values to 1 to ensure they stay in the set, thus the state consistently representing dominating set. By making these adjustments, we maintain the integrity of the dominating set representation throughout the process.
Reward The log reward is set to be the negative dominating set size, i.e., {(x) = |x For intermediate state s, we define its intermediate signal by setting {(s to be the number of in
B.3 Maximum MDP
We start with an empty solution vertex set, i.e., all the vertices are in value.
Action Same as MIS and MC, the action is to add one vertex to the current solution set of vertices, by changing its entry value from @ to 1.
Transition After each action is carried out, we perform the following check: if involving one void vertex to the solution vertex set would decrease the cut value, then we exclude this vertex by labeling it to 0 from void Ø. This guarantees that when the trajectory terminates (i.e., no void unspecified vertex), the cut locally maximal.
Reward We set the negative energy to be the size the current cut set, i.e., the number of edges between all vertices and all 0 vertices. For intermediate state define its intermediate signal by setting (ss) to be the number of edges between all 1 vertices and other vertices (note that think of void vertices as not in the solution set).
C GFlowNet details
We start with the proof of Proposition and then describe other algorithmic details.
Proof. According to the theory of GFlowNets (Bengio et al. 2023). if GFlowNet's training loss is zero on full support, then the GFlowNet is able to sample correctly from the target distribution (x). When we gradually move temperature from finite to oc, the distribution p*) will gradually become the uniform distribution over X. thus the distribution sampled by GFlowNet will converge to this uniform distribution; when the temperature gradually approaching zero, the distribution (x(x) will gradually become the uniform distribution over all argmax solution of arg maxx E(x), thus the distribution sampled by GelowNet will converge to this uniform distribution.
For the GelowNet architecture, we graph isomorphism network (Xu et al. 2019 GIN) with 5 hidden layers and 256 dimensional hidden size, both the forward policy and the state flow function. We double the number of hidden layers for SATLIB experiment. The input of the GIN is integer
16

---

Table 4: Max independent set experimental results on ER graph data in the same form as Table
ER-700-800
ER-9000-11000
METHOD
TYPE
SIZE 1
DROP 4
TIME 4
SIZE 1 DROP 4
TIME 4
GUROBI KAMIS
OR
43.47
3.33%
2:10:05
OR
44.98
0.00%
2:11:21
374.57
0.00%
7:37:21
PPO
UL
41.11
8.60%
4:30
344.67
7.98%
1:02:29
INTEL
SL
37.34
16.99%
28:32
DGL
SL
38.71
13.94%
29:36
OURS
UL
11.14
8.53%
2:55
319.12
6.98%
1:49:43
vector represented state in the form of {0, 1, 2311 followed by an embedding layer, where we use to denote the unspecified void @. For the forward policy GIN, we set a unidimensional output node feature followed by softmax operation over all vertices, which gives a categorical distribution on all the vertices. For the state flow GIN, we use a graph pooling layer to extract unidimensional graph-level output to serve as the flow value. We fix the backward policy to be uniform distribution over all chosen vertices for simplicity. Theoretically, function and the forward policy, but we find it is much less stable. We hypothesize that the flow function training stability is very important in DB-based GFlowNet methods, and that most previous GFlowNet works underfit the flow function and underestimate the performance of DB.
only use one GIN for both the flow
We use the Adam optimizer with default 10-3 learning rate without hyperparameter tuning. After breaking the complete trajectories into transition pieces, we combine them to many buffer with batchsize equals 64 to calculate forward-looking based detailed balance loss. The training keeps 20 epochs, although most experiments actually converge in the first 5 epochs. For the SATLIB experiment, our proposed method converges within the first epoch. During the inference phase, we simply the same evaluation protocol in Ahn et al. (2020). To be concrete, we sample 20 solutions for each graph configuration and take the best result.
We conduct a series of ablation study with small graph MIS experiments in Figure Each algorithm is repeated with five different random seeds. For the temperature T used in GFlowNet's reward shaping, we try values of the inverse temperature from to 5000 and find values higher or equal than 100 will obtain similar results. We thus simply use an inverse temperature of 500 for all the tasks. We also use temperature annealing, to start with temperature of and terminate with the target temperature level (although the ablation study shows that GFlowNet could reach same performance without the annealing trick). During the training, GFlowNet will need to rollout (i.e., interact with the environment to collect complete trajectories) to collect training data. In this work, we do on- policy exploration, which means the policy used the rollout stage is the current forward policy. Nonetheless, GFlowNet has the ability of doing off off-policy exploration. In the third ablation study, mix the forward policy with different levels of uniform noise distribution, and find that GFlowNet is very robust under this off-policy setups. In this fourth ablation study, we change the number of hidden layer in the GIN architecture and find GelowNet is also robust to this hyperparameter.
D More about experiments
For BA graphs, we use the variants with attaching edges. For small scale datasets, we first sample the number of vertices uniformly from 200 to 300 and generate the graph instances. For large-scale problems, it is uniformly sampled from 800 to 1200. Both the small and large synthetic graph trainsets contain 4000 data points for either RB graph BA graph. For the SATLIB dataset, there are 40000 data points in total, where the largest graph has 1347 vertices. For all datasets, we use validation set and test set, both with 500 data points. We choose the hyperparameters of each algorithm based on the validation performance. Regarding hardware, we use NVIDIA Tesla V100 Volta GPUs We repeat the experiments for five different random seeds.
We also conduct MIS experiments on Renyi (ER) graph data shown in Table 4 We use ER data as large as 700 ~ 800 vertices and 9000 ~ 11000 vertices for a comparison with Qiu et al. (2022) DIMES) and [Snn & Yang (2023, DIFUSCO). The training and evaluation protocols are not exactly the same, but we still present results from these baselines for completeness. DIMES achieves 38.2 38.24/42 24/42.06 and 320.50/ /30...80 (*/" means two variants of their algorithm) respectively
17

---

for these two tasks; DIFUSCO achieves 38. 38.83/41.12 (*/" means two variants of their algorithm) for the ER-700-800 problem, and not scalable for extremely large problems like ER-9000-11000. The difference in protocol includes: GelowNet uses less training data samples; DIFUSCO is supervised learning algorithm (requires solver to provides solution), while DIMES and GFlowNet are unsupervised methods; the test data may not be the same (they generate their own fold). For GFlowNet in the largest task, we use temperature 1000 and a batch size 32. In summary, we can see that GFlowNet also achieves state-of-the-art performance in this setup, especially in large problems.
In MIS benchmark, for the MIS supervised learning baselines (INTEL and DGL), we disable the usage of the graph reduction and 2-opt local search tricks, but only adopt the queue pruning and weighted queue pop technique. This is because even random initialized neural network can be used to find near optimal solutions with graph reduction and local search as pointed out by Böther et al. (2022). Furthermore, these forbidden techniques are very time-consuming, making the inference time exceeding our time limit constraint. For KAMIS, we use the redumis algorithm. For GUROBI, we formulate MIS as quadratic programming problem and then use the pygurobi python package to solve it. We also run ardoos-basee probabilistic methods (ERDOS and ANNEAL) for MIS, but their results are worse than any baselines methods in the MIS benchmark, thus we do not include them in Table T In the max cut task, we use the cvxpy python package to implement the SDP baseline.
18


Reviews:
[{"review_id": "27ZUHWL8B4", "reviewer": "Reviewer_n6CJ", "summary": "The authors propose an approach for using GFlowNets for solving some NP-Hard combinatorial optimization problems on graphs. The GFlowNet approach is designed to better perform credit assignment for fitting a constructive policy that adds nodes on the graph to a currently considered subset. The authors propose slight modifications of GFlowNet that help it perform well on graph optimization tasks which require long trajectories and improved credit assignment. The authors justify their design decisions empirically via ablation studies. Finally, the authors evaluate the proposed approach against supervised learning, unsupervised learning, heuristics, and traditional OR approaches where applicable. They evaluate on a variety of problems considering max independent set, max clique, minimum dominating set, and max cut. They demonstrate improved solution quality over the investigated baselines and mostly improved runtime over OR baselines. Overall, the paper is a promising initial attempt at applying GFlowNets to solve CO problems on graphs.", "questions": "[Paragraph starting at line 44] One listed downside of RL in CO is that RL may not produce diverse solutions. It would be helpful to demonstrate how this approach addresses that for instance by demonstrating that the GFlowNet approach does generate diverse solutions compared to the RL approach. For instance, Gurobi is able to return a pool of solutions. It would be interesting to compare the solution diversity between approaches.\n\nFor the forward looking technique, would it be possible to use the objective value of a “completed solution” which finds the optimal solution given the partial solution as fixed? Does this need to be a differentiable function of the solution?\n\nIt would be helpful to give the variance for the results to determine how close the distribution of results are since they are somewhat close to previous work. Additionally, it would be helpful to give some metrics such as win rate, i.e. the percent of instances for which the given approach was fastest / got the best quality solution. \n\n\nIt would also be helpful to explain the sizes of the train / test datasets and how they were split especially in the case of SATLIB.\n\nIt is unclear how this approach might handle CO problems where feasibility is “difficult”. For instance, for TSP on non-complete graphs it may be hard to find a feasible tour. It would be helpful to explain how this method might approach settings where feasibility is nontrivial via constructive methods. Here it may be difficult to sample feasible solutions in the first place and as such it may be helpful to understand how this method would perform. Similarly, it would be helpful to explain how this method would perform in settings where the decisions are more complex than selecting a subset of vertices. This is somewhat hinted at in the paragraph starting on line 195 but it would be helpful to explain this limitation and how it might be addressed.\n\n\nSmall questions:\n[line 29] Why is gurobi considered as giving approximate solutions? It not only should give optimal solutions given enough runtime but should also give a bound on the solution quality in order to prove optimality.\n\n[line 258] handcraft -> handcrafted\nTable 1, Time of Ours in Large has a leading 0 before the 4:22\n", "limitations": "Relevant limitations are addressed", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strength of the paper is in addressing limitations of previous RL for CO approaches using GFlowNet. In previous RL-based optimization approaches, the issue of credit assignment is a major challenge as often individual choices have limited immediate impact on the overall solution quality while the long-term impact can be quite large. GFlowNet as an approach aims to perform this credit assignment well as it aims to learn a policy based on a long-term reward. \n\nA second strength is that the authors evaluate the given approach against a variety of baselines on a number of settings and present results on all settings. \n\nLastly, the writing is quite clear, and the paper gives a useful introduction of how to use GFlowNet for CO problems which can likely lead to future work of employing GFlowNet for broader types of CO problems.\n", "weaknesses": "The main weakness is that the main contribution of the paper is that it is mainly directly applying GFlowNet to CO on graphs with minor modifications of the GFlowNet approach, and justifying their approach with intuition and empirical results. It might be good to either identify 1) specific ways that the GFlowNet methodology might be adapted to be specially suited to CO problems, or 2) ways in which the particularities of GFlowNet might be especially suited for answering interesting questions in CO problems. \n\nSome ideas for 1) it may be helpful to formulate the architecture used in GFlowNet to encode certain properties that help solvers such as being invariant to permutation of the solution generation procedure, special actions for GFlowNet such as deleting components of the current solution. Other ideas might be to modify GFlowNet to make use of alternative information such as supervision from known solutions on the training dataset, precomputed primal solutions with objective values, or integrating solver components like presolve etc.\n\nFor 2) it might be helpful to showcase the ability to generate diverse solutions by evaluating the diversity of solutions generated by the GFlowNet in terms of how many unique solutions it produces. Alternatively, one could generate a solution pool and using that to warm start solvers or generate solutions for multi-objective optimization problems. \n\nOverall, it would be interesting to see how the GFlowNet approach could be used outside of improving solve time.\n\n\nWhile the empirical results are promising, it is somewhat unfair to compare the given heuristic methods only against gurobi as an exact solver, since gurobi may be spending a lot of time proving optimality in addition to finding the optimal solution. It would be more reasonable to compare against gurobi which is tuned for quickly finding primal solutions and which is set at a very strict time limit, since gurobi may be finding the optimal solution quickly and taking most of its time proving optimality. Additionally, gurobi seems to be solving faster than the proposed approach in the MDS setting. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> directly apply GFlowNet to CO with minor modifications\n\nSee the general response.\n\n> formulate architecture to encode certain properties… modify GFlowNet to make use of alternative information\n\nWe appreciate the reviewer's insightful suggestions about interesting future directions. Indeed, we use a standard architecture and don't exploit the geometric properties, and the standard scenarios as in previous GFlowNets works that don't allow deleting actions. We acknowledge that these are valuable future directions which could further boost the GFlowNet performance. This indicates that there is still huge potential of GFlowNet in CO problems. Furthermore, our approach is purely unsupervised (without the knowledge of precomputed solutions). On the other hand, this can be an interesting future direction: e.g., we can start from a given solution, and then use the GFlowNet's backward policy to generate trajectories which we know would lead to informative high-reward regions. These high-quality trajectories could be very useful in training as they save a lot of exploration effort.\n\n> diversity of GFlowNet and other methods\n\nWe compute the diversity of RL and GFlowNet. For each graph in testset, we let each algorithm generate 30 solutions and compute their mean pairwise distance. The diversity is the mean distance across testset. The distance is computed as the Jaccard distance between two solution vertex sets. In the MIS small task RL and GFlowNet got $0.428$ and $0.618$, respectively. As for Gurobi, it obtains a diversity of $0.312$ when being used with pool solution feature to give multiple solutions. This indicates that GFlowNet produces more diverse samples than PPO; notice that GFlowNet also achieves better performance than PPO on this benchmark in the sense of a larger solution set.\n\n> unfair to compare given methods only against Gurobi… Gurobi faster than GFlowNet on MDS on large task\n\nIndeed, the configuration of using Gurobi to solve combinatorial optimization problems could be flexible and using different formulations might cause different performance. However, we do involve KaMIS, which is a highly specialized solver for MIS problems, in our experiments; we believe KaMIS will achieve at least similar performance to the best tuned Gurobi if not better. What’s more, our Gurobi results are from [1], which has been adopted by many other CO related machine learning papers. Furthermore, our method does use heuristics in algorithmic design, thus it would be unfair to be compared with Gurobi with specialized heuristics. Lastly, we try two different formulations of Gurobi in MIS large scale tasks, and they got average size of $40.14$ in $2:15:07$,  and average size of $40.90$ in $2:10:36$, respectively. \n\nWhile it's true that our method didn't outperform Gurobi on MDS with a large scale dataset, it's important to consider the overall performance. Due to Occam's razor, different methods have different strengths and weaknesses, and their performance vary depending on the characteristics of dataset. The dataset in question may have certain unique characteristics that particularly favor the baseline method. Our method demonstrated superior or competitive performance on almost all datasets, which we believe is a strong indication of its effectiveness and robustness.\n\n[1] https://github.com/MaxiBoether/mis-benchmark-framework\n\n> For forward looking, would it be possible to use... optimal solution? Does this need to be differentiable?\n\nIt would be a great and feasible idea to use known optimal solutions. For example, in MIS if we know the optimal solution is of size $a$ and the current set has $b$ nodes, then we can use $b/a\\in [0, 1]$ to serve as the negative partial energy $\\mathcal{\\tilde E}$. We will need to accordingly use $c/a\\in [0, 1]$ as the terminating reward where $c$ is the solution set size of the terminating state. In this example, we do not require differentiability.\n\n> variance for the results… other metrics\n\nWe repeat 5 runs of GFlowNet, which achieve $19.20\\pm 0.08$ on the MIS small scale task and $37.89\\pm 0.36$ on the large scale task. This indicates that the performance of GFlowNet is stable and the improvement upon other baselines is statistically significant. Due to limited time, we only calculate the win rate of GFlowNet against Gurobi, which is $0.326$. Notice that this is a nontrivial result as Gurobi is almost perfect on this benchmark, which indicates the advantage of GFlowNets.\n\n> train/test split\n\nAs described in Appendix D, for tasks with RB/BA graph we use a training set of size 4000, a validation set of size 500, and a test set of size 500; for SATLIB we use a training set of size 39000, a validation set of size 500, and a test set of size 500. For RB and BA graphs we do uniformly splitting as the data are simulated in the same way for train/valid/test; for SATLIB, we obtained the split from the authors of [1].\n\n[1] DIFUSCO:Graph-based Diffusion Solvers for Combinatorial Optimization\n\n> when feasibility is “difficult”\n\nIndeed, we ensure all obtained solutions are feasible through specific MDP design. For more general CO problems it could be hard to get a feasible solution, let alone to achieve a solution that maximizes some target property. That being said, this poses a significant challenge not only to our method but to all ML approaches in general. To address this issue, one potential approach could be to use a very negative reward when getting infeasible results. This could encourage the model to avoid infeasible solutions. Alternatively, we could consider a soft penalty approach, where the reward is a monotonic function of the number of constraints satisfied. This would allow the model to learn to improve feasibility over time when we gradually use a temperature to make the soft constraint harder.\n\n> Why is Gurobi considered as approximate?\n\nYou are right. We originally wanted to say “give approximate solutions with limited time” and will correct this in revision."}, {"review_id": "QPG4uDhgOY", "reviewer": "Reviewer_gYzR", "summary": "This paper leverages generative flow networks (GFlowNets) to obtain diverse solution candidates for combinatorial optimization problems on graphs without expert supervision.\n\nGFlowNets were recently introduced as a way to sample structured objects $\\mathbf{x}$ with a likelihood $P(\\mathbf{x}) \\propto R(\\mathbf{x})$ that is proportional to a terminal reward function (see _Flow Network based Generative Models for Non-Iterative Diverse Candidate Generation_, Bengio et al. 2021).\nThis is done by casting the sampling as a Markov Decision Process, whose policy is defined by neural networks and trained with a suitable loss to enforce flow balance conditions.\n\nIn the study at hand, the reward is chosen as a Gibbs probability distribution $R(\\mathbf{x}) = \\exp(\\mathcal{E}(\\mathbf{x}) / T)$, whose temperature controls solution diversity by specifying the acceptable deviation from the global optimum.\nParametric policies are constructed conditionally on the graph, to allow for generalization.\nMDPs are designed in a problem-specific manner, by iteratively constructing sets of vertices that satisfy certain constraints.\nSince the MDP trajectories can be quite long, two tricks are suggested to improve training efficiency and credit assignment:\n- sample random subsets of transitions instead of a full trajectory\n- incorporate intermediate reward signals based on partial solutions\n\nThese strategies are implemented and benchmarked against exact solvers, as well as recent ML-based approaches.", "questions": "L61: What is new in your MDP design compared to existing formulations?\n\nL105: Where do the final rewards appear?\n\nL242: I thought the whole point was to make epochs faster?\n\nL255: Are there cases where this reward continuation is not applicable? \n\nL640: Why not use a linear formulation? What formulation did you use for the three non-MIS problems?", "limitations": "The authors do not really discuss the limitations of their approach, and more reflection on that would be welcome.\n\nSocietal impact is not relevant in this case. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "### Originality\n\nThis paper mixes several existing ideas into a coherent whole:\n\n- GFlowNets and their loss functions\n- viewing optimization as probabilistic inference\n- MDPs for combinatorial problems\n- strategies for credit assignment\n\nThis unseen combination, along with extensive numerical experiments, is sufficient novelty in my view.\n\n### Quality\n\nThe authors demonstrate deep knowledge of the literature on GFlowNets, and the theoretical part is well supported.\nThorough benchmarks suggest their method performs better than its counterparts, although some comparisons may be biased (see below).\nI especially appreciated the care given to make the benchmarks transparent and fair (aligning with recent papers, avoiding easy instances, reimplementing and retraining algorithms from scratch to compare them on the same basis). \nAdditionally, a very welcome ablation study shows the limited impact of hyperparameter settings.\nIn a nutshell, this is good, serious science.\n\n### Clarity\n\nThe writing style is clear and nicely complemented by explanatory pictures.\nA lot of time is devoted to the prerequisites on GFlowNets and combinatorial problems, as well as a thorough literature review. \n\n### Significance\n\nI believe this contribution can inspire further developments, since the use of GFlowNets for combinatorial optimization seems well-justified and practically successful.", "weaknesses": "### Originality\n\nTo me, it appears that the main novel idea in the paper is the application of GFlowNets to learning combinatorial problems (which is already a worthy one).\nThe idea of training from subsampled transitions instead of a full trajectory is also new.\n\nHowever, I would be very surprised if the MDPs presented by the authors were absent from the previous literature, especially given the standard nature of problems such as Maximum Independent Set.\nPerhaps there are some necessary adjustments that are necessary for these MDPs to work with GFlowNets, in which case I will welcome clarification! \n\n### Quality\n\nI am not confident enough to comment on the choice of algorithms in the MIS benchmark, but I have an issue with the 3 non-MIS benchmarks, which seem a bit unfair to me.\nA major asset of GFlowNets is their sequential construction of the solution, which the authors mention as the reason for their success.\nOn the other hand, the benchmarked competitors ERDOS and ANNEAL rely on a hypothesis of independence between vertices of the graph, which explains their fast inference.\nIn light of this, I argue that it would make sense to benchmark GFlowNets against other methods (typically from the RL literature) that also adopt a sequential perspective, to see if the advantage still holds.\n\n### Clarity\n\nn.a.\n\n### Significance\n\nTo underline the impact of the paper, it would be helpful to explain why a diverse set of solution candidates is important in practice.\nAs a combinatorial optimizer myself, it is not obvious to me: when should I settle for a set of diverse, but possibly suboptimal solutions?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> To me, it appears that the main novel idea in the paper is the application of GFlowNets to learning combinatorial problems (which is already a worthy one). The idea of training from subsampled transitions instead of a full trajectory is also new. … However, I would be very surprised if the MDPs presented by the authors were absent from the previous literature, especially given the standard nature of problems such as MIS. Perhaps there are some necessary adjustments that are necessary for these MDPs to work with GFlowNets, in which case I will welcome clarification!\n\n> L61: What is new in your MDP design compared to existing formulations?\n\nWe do not aim to claim that we “invent” the MDPs, but only want to find efficient algorithms to solve these MDPs. We acknowledge that the design of our MDPs, which is simple yet effective, is very straightforward. In fact, [1] uses similar MDPs as ours; they design MDPs that “add one vertex at each step”, but on minimum vertex covering, maximum cut, and traveling salesman problem. That said, they do this on slightly different CO problems, and they also use different reward designs from ours. Other MDP designs include [2] where each action is to “edit” the current solution, and [3] where each action is to add multiple vertices into the solution set. We will include this discussion to the final version.\n\n[1] Learning Combinatorial Optimization Algorithms over Graphs\n[2] Learning to Perform Local Rewriting for Combinatorial Optimization\n[3] Learning What to Defer for Maximum Independent Sets\n\n> I am not confident enough to comment on the choice of algorithms in the MIS benchmark, but I have an issue with the 3 non-MIS benchmarks, which seem a bit unfair to me. A major asset of GFlowNets is their sequential construction of the solution, which the authors mention as the reason for their success. On the other hand, the benchmarked competitors ERDOS and ANNEAL rely on a hypothesis of independence between vertices of the graph, which explains their fast inference. In light of this, I argue that it would make sense to benchmark GFlowNets against other methods (typically from the RL literature) that also adopt a sequential perspective, to see if the advantage still holds.\n\nA large part of research in combinatorial optimization is about trading-off the performance and efficiency. One of the advantages of Erdos-based methods including Anneal is the efficiency; on the other hand, even given a large enough time budget (like what we do in the experiments), it will not obtain tremendous improvement. Please note that we have compared with the PPO baseline (from a recent related work [4]) in MIS comparison, which is close to GFlowNet in the sense of sequential generation (but fails to encourage diversity in the solutions -- please find our detailed explanation as below), and we will incorporate more comparison of RL baselines with sequential generation behavior in the final version.\n\n[4] Learning What to Defer for Maximum Independent Sets\n\n> To underline the impact of the paper, it would be helpful to explain why a diverse set of solution candidates is important in practice. As a combinatorial optimizer myself, it is not obvious to me: when should I settle for a set of diverse, but possibly suboptimal solutions?\n\nAs discussed in the paragraph starting at line 44, there could be several cases where we want to emphasize diversity. For example, there could be multiple different optimal solutions in combinatorial optimization problems due to the symmetry of problem configurations, as pointed out in [1]. In addition, diversity in the solutions holds great importance across several dimensions, while solely looking for an optimal solution for the current problem could fail:: **Robustness** Multiple solutions can provide a form of robustness. If one solution fails or is not feasible due to changes in the problem environment or constraints, having alternative solutions can be very useful; **Exploration of the Solution Space** A diverse set of solutions allows for a broader exploration of the solution space. This can provide more insight into the structure of the problem and could serve as warm starts for numerical solvers; **Stakeholder Preferences** In many real-world problems, there may be multiple stakeholders with different preferences or objectives. A diverse set of solutions can provide a range of options that cater to these different preferences; **Dynamic Environments** In dynamic environments where the problem parameters can change over time, having a diverse set of solutions can allow for quick adaptation and better generalization to these changes.\n\n[1] Combinatorial optimization with graph convolutional networks and guided tree search\n\n> L105: Where do the final rewards appear?\n\nThanks for the question. When a state is terminal, then its flow value would be the reward value, which is the source of learning signal grounded by the environment.\n\n> L242: I thought the whole point was to make epochs faster?\n\nThe point is to show that our proposed novel GFlowNet variant is better within the same training time. Since different variants consume similar wall clock time for one epoch, we could roughly think of epoch as a measure of training time.\n\n> L255: Are there cases where this reward continuation is not applicable?\n\nTo the best of our knowledge, this has demonstrated applicability across the problems we have studied, particularly those where all states belong to the same space. \n\n> L640: Why not use a linear formulation? What formulation did you use for the three non-MIS problems?\n\nWe follow what is provided in the MIS benchmark [1]. We thus try two different Gurobi formulations, which achieve average size of $40.14$ in $2:15:07$,  and average size of $40.90$ in $2:10:36$, respectively. For other problems we use linear formulations. \n\n[1] https://github.com/MaxiBoether/mis-benchmark-framework"}, {"review_id": "CYD3c7X88Q", "reviewer": "Reviewer_VHLn", "summary": "This paper presents a new approach for learning to solve graph combinatorial optimization by GFlowNets. The GFlowNets (or broadly, the generative models) own the advantage of discovering multiple (near)-optimal solutions, which is better than standard RL or SL. The authors modify GFlowNets to work with larger-scale problems in CO and provide extensive experiments on 4 different problems.\n\n---------------------\n\nPost-rebuttal: I appreciate the authors for the feedback and I am now more positive about this paper.", "questions": "Please see the questions in the \"weaknesses\" part.", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* This paper is well-written. \n* The motivation for introducing GFlowNets to CO is sound and interesting.\n* The authors made modifications to GFlowNetw to fit larger-scale CO problems.", "weaknesses": "* My major concern of this paper is about the selection of baselines and the implementations in experiments.\n  * The authors mentioned in L55 that \"there are attempts to fix these issues (Kwon et al., 2020; Ahn et al., 2020)\" from the RL literature, but these methods are not implemented and compared in experiments.\n  * Why the selection of baselines are different for MIS and the other 3 problems, especially considering that MIS and Max clique are complement?\n  * What will the performance be like if we let Gurobi run the same amount of time compared to your GFlowNet solvers?\n  * During inference, do you implement a search algorithm after the GFlowNets? What about the other neural solver baselines?\n  * How do you implement, configure and tune the baselines? Do you implement the same GIN as your implementation of GFlowNets? For example, from my knowledge, PPO's performance is strongly dependent on hyperparameter tuning and the configuration of tricks. Besides, the probabilistic method (Karalias & Loukas, 2020) has two types of configurations (fast/accurate) and which one do you choose?\n  * I also notice you follow some recent neural CO solvers such as Qiu et al. (2022, DIMES) and Sun & Yang (2023, DIFUSCO) but do not consider them in main experiments. Can you offer any justifications? \n* The training process does not seem clear to me. Is the training objective to minimize $l_{DB}+l_{TB}$? How is the reward being used? Seeing that GFlowNet is quite a new framework, we should not expect the readers to be that familiar with the domain knowledge. \n* Some details seem to be missing: \n  * What is the meaning of \"MIS size\" in Fig 4? On which dataset did you get the numbers in Fig 4?\n* Other minor issues:\n  * The notation of $P_F^\\top$ is improper. As I understand, $\\top$ does not mean \"transpose\" here and causes confusion to readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The authors mentioned that \"there are attempts to fix these issues (Kwon et al; Ahn et al.)\" but these are not compared in experiments.\n\nPlease note that we have compared with Ahn et al, which is the “PPO” in Table 1. The Kwon et al. work is designed for routing problems (e.g., TSP)  which are different from the problems we study in this work, thus we don't include it. That said, we will definitely take routing problems as one of the future directions where we hope to see the advantage of GFlowNets on this family of combinatorial optimization problems. \n\n> different baselines between MIS and others\n\nOur choice of baselines was guided by a desire to provide a comprehensive comparison across a diverse set of methods. For the MIS problem, we have already included a substantial number of baselines in our benchmark. Notice that most baselines are specialized for MIS and not applicable for other tasks. For the other problems, we follow the benchmark that is used by [1], aiming to include a broader range of baselines, particularly those from the unsupervised learning domain.\n\nRegarding the complementarity of the MIS and Max Clique problems, we agree with your point. To cover a diverse set of baselines on max clique, we add an experiment on the twitter dataset following Sec. 4 of [2] and [3]. In this benchmark, the methods of [2], [3], [4], and GFlowNet achieve average results of $0.926$, $0.924$, $0.987$, and $0.992$. This demonstrates the excellence of GFlowNet performance. Our goal was to cover a diverse set of baselines within our limited time. By comparing these, we provide a more comprehensive evaluation. \n\n[1] Annealed Training for Combinatorial Optimization on Graphs\n[2] Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation\n[3] Erdos Goes Neural:an Unsupervised Learning Framework for Combinatorial Optimization on Graphs\n[4] Graph Neural Networks for Maximum Constraint Satisfaction\n\n> run Gurobi in limited time\n\nWe do experiments on running Gurobi on large scale MIS task with limited time budget. We give a time budget that is slightly larger than GFlowNet to Gurobi, and it obtains the average size of $34.81$, smaller than $37.48$ of GFlowNet. Therefore, Gurobi obtains worse performance compared to GFlowNets under the same time budget constraint.\n\n> a search algorithm during inference?\n\nWe do not implement any search algorithm based on GFlowNets (see the evaluation part of Appendix C). That being said, it will be a very promising future direction to explore to further boost the performance of GFlowNet solvers. The Intel and DGL baselines are built on a tree search algorithm, while other baselines do not use search algorithms. Thus it's fair to say that GFlowNet achieves better performance.\n\n> How do you implement, configure and tune the baselines?\n\nFor different methods, we use the same evaluation and hyperparameter selection protocols to make sure the comparison is fair (see Appendix D). For RL baseline we stick to configurations in [1] to ensure that we are not “creating” a worse baseline that is different from the original previous work. \n\n[1] Learning What to Defer for Maximum Independent Sets\n\n> probabilistic method has two configurations... which one do you choose?\n\nWe implement the conditional sequential decoding proposed in Erdos [1], which is slower but more accurate than directly doing monte-carlo sampling (see Sec. 3.3 in [1]). Therefore, it is fair to say that our comparison is reasonable.\n\n[1] Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs\n\n> ... some recent neural CO solvers but do not include them\n\nThat isn't true. We do include their methods in Appendix D to show the advantage of GFlowNets especially on large scale tasks. In the main text we don't include them as they don't use the same graph simulation protocol as ours and we also got bugs when trying to reproduce their results on our data. During the week after main text submission deadline, we did experiments on ER graphs with GFlowNets and thus could compare with them, so we put these results into Appendix D. The results show the advantage of GFlowNet. Further, our approach is a purely unsupervised method while theirs rely on precomputed solutions by the solver. Thus it is not fair to compare unsupervised methods with supervised methods. On the other hand, this means GFlowNet uses less information but still achieves better results.\n\n> Is objective $\\ell_{TB} + \\ell_{DB}$? How is the reward used?\n\nNo; in fact, the forward-looking (FL) objective in Eq. 6 is a modification of the detailed balance objective with (one can see the similarity between Eq. 2 and Eq. 6) that uses cumulative reward information in the parametrization of the state flow. For DB-based methods, the reward is used as the state flow of the last state in a complete trajectory. We will make sure to specify the usage of reward information in the final version of the paper.\n\n> What is \"MIS size\" in Fig 4? On which dataset to get Fig 4? \n\n\"MIS size\" is the size of the vertex set that an algorithm obtains for a maximum independent set task. The larger the size, the better the method. More details about evaluation metrics are written in the paragraph starting from line 313. As specified in line 338, we conduct experiments on a small scale simulated RB graph dataset to produce Fig. 4.\n\n> The notation of $P_F^{\\top}$ is improper. As I understand, $\\top$ does not mean \"transpose\" here and causes confusion to readers.\n\nHere $\\top$ is for “terminating” and $P_F^{\\top}$ is the distribution of terminating states induced by GFlowNet’s forward policy $P_F$ (line 88). This notation is borrowed from past work on GFlowNets and we will replace the improper notation."}, {"review_id": "q2ANVaShAX", "reviewer": "Reviewer_PEdA", "summary": "This paper suggests a new graph combinatorial optimization method by leveraging a generative flow network (GFlowNet) and other novel technics to improve it. Maximum independent sets (MIS) and their variants are very important problems as they can be applied to several high-impact tasks such as network communication. As these problems are, NP-hard exact method cannot solve them within a reasonable time, so that approximated solver such as a deep learning policy can support the production of near-optimal solutions quickly. This work follows this research trends and makes state-of-the-art over the deep learning baselines. \n\nA major contribution is the usage of GFlowNet rather than PPO because exploration of GFlowNet can cover the symmetric nature lies in combinatorial solution space using DAG-based MDP construction. The novelty of this work is the improvement of GFlowNet for long trajectory generation of combinatorial optimization, so this work proposed (1) transition-based training and (2) intermediate learning signal training, which is a simple yet intuitive idea. \n\nWhile this work is concrete and interesting, I have several questions and concerns; please address these concerns in the rebuttal discussion phase. \n\nI just wrote the questions below. ", "questions": "1. How does diversity (e.g., the edit distance between sampled solution) changes when your new techniques are applied? (to compare with another method, including the trajectory balance method)?\n\n2. What kinds of post-processing methods are used for solution generation? Did you samples multiple samples from the learned sampler? Then what is the actual sampling width? How about applying local search just as learning what to defer (LwD) [1] ?\n\n3. To compare with LwD, did you put 2opt for LwD following their original paper?\n\n4. Can this method extend to other combinatorial optimization, such as the traveling salesman problem (TSP)?\n\n[1] Ahn, Sungsoo, Younggyo Seo, and Jinwoo Shin. \"Learning what to defer for maximum independent sets.\" International Conference on Machine Learning. PMLR, 2020.\n", "limitations": "GFlowNet is an on-going framework having a lot of limitations. Please make explicit limitations on the main paper for future researchers. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This work is novel, and its performance seems to be promising. First, they cleverly leverage existing Markov decision process formulation of learning what to defer (LwD), as the state is described as $s \\in \\{0,1,2\\}$ where 0 is included, one is excluded, and two is deferred; please make clear spotlight that this MDP idea is from prior work of LwD [1]. \n\nSecond, they leveraged GFlowNet rather than PPO so that it could consider the symmetric nature of combinatorial solution space. \n\nThird, their additional techniques are widely studied things in GFlowNet research (e.g., the intermediate reward is similar to Generative Augmented Flow Network [2], and the transition-based method is identical to sub-trajectory balance [3]) but made intuitive variations for combinatorial optimization. \n\n[1] Ahn, Sungsoo, Younggyo Seo, and Jinwoo Shin. \"Learning what to defer for maximum independent sets.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Pan, Ling, et al. \"Generative augmented flow networks.\" arXiv preprint arXiv:2210.03308 (2022).\n\n[3] Madan, Kanika, et al. \"Learning GFlowNets from partial episodes for improved convergence and stability.\" arXiv preprint arXiv:2209.12782 (2022).", "weaknesses": "One can be said that technical novelty is limited as every technique are already actively explored; I think making the novel combination of existing technics is also significant. \n\nI think the description of many ideas follows existing trends of GFlowNet; I enjoyed reading this paper, but maybe some who don't know about GFlowNet work can miss many detailed parts of this technique. Please make an explicit description of each technique and give a reference idea of where you are inspired by and what is the major difference, e.g., sub-trajectory balance vs. transition-based learning (assume that reader also not familiar with the sub-trajectory balance). \n\nFinally, there are several neural combinatorial optimizations works [1,2] that study the symmetric nature of combinatorial optimization. I humbly suggest to include as a reference paper. \n\n[1] Kim, Minsu, Junyoung Park, and Jinkyoo Park. \"Sym-nco: Leveraging symmetricity for neural combinatorial optimization.\" Advances in Neural Information Processing Systems 35 (2022): 1936-1949.\n\n[2] Kim, Hyeonah, et al. \"Symmetric Exploration in Combinatorial Optimization is Free!.\" arXiv preprint arXiv:2306.01276 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Please make an explicit description of each technique and give a reference idea of where you are inspired by and what is the major difference, e.g., sub-trajectory balance vs. transition-based learning (assume that reader is also not familiar with the sub-trajectory balance).\n\nWe do not use the sub-trajectory balance objective in this work. Sub-trajectory balance is to take sub-trajectory (could be longer than a single transition but also could be shorter than a complete trajectory) to construct training losses. On the other hand, transition-based learning is only applicable to detailed balance based methods (including detailed balance and forward-looking detailed balance). It has the same expected gradient as trajectory-level detailed balance training, but just use the formula in line 238 rather than Eq. 5 to make the optimization more efficient. We will include the discussion into the final version.\n\n> Finally, there are several neural combinatorial optimizations works [1,2] that study the symmetric nature of combinatorial optimization. I humbly suggest to include as a reference paper.\n[1] Kim, Minsu, Junyoung Park, and Jinkyoo Park. \"Sym-nco: Leveraging symmetricity for neural combinatorial optimization.\" Advances in Neural Information Processing Systems 35 (2022): 1936-1949.\n[2] Kim, Hyeonah, et al. \"Symmetric Exploration in Combinatorial Optimization is Free!.\" arXiv preprint arXiv:2306.01276 (2023).\n\nThanks for the references! We will make sure to include them in the final version.\n\n> How does diversity (e.g., the edit distance between sampled solution) changes when your new techniques are applied? (to compare with another method, including the trajectory balance method)?\n\nIn the MIS small scale benchmark, we test the diversity of different GFlowNet variants. For each graph configuration in the test set, we let each algorithm generate thirty solutions and compute their average pairwise distance. The diversity is the mean distance averaged across the test set. The distance is computed as the Jaccard distance between two solution vertex sets. The diversity of trajectory balance, detailed balance (trajectory level), detailed balance (transition level), forward-looking detailed balance (trajectory level), and forward-looking detailed balance (transition level) is $0.714$, $0.572$, $0.637$, $0.505$, and $0.618$, respectively. \n\n> What kinds of post-processing methods are used for solution generation? Did you samples multiple samples from the learned sampler? Then what is the actual sampling width? How about applying local search just as learning what to defer (LwD)?\n\nYes, we sample multiple times from the learned sampler and do not use any further post-processing technique; see Appendix C for details. We also agree that applying local search with GFlowNet solutions will definitely be a promising future direction for this. \n\n> To compare with LwD, did you put 2opt for LwD following their original paper?\n\nLwD does not provide code for local search; also in the LwD paper, only part of the experiments are done with 2opt. To ensure a fair comparison, we also do not put 2opt after GFlowNet and compare it with other baselines including LwD without 2opt.\n\n> Can this method extend to other combinatorial optimization, such as the traveling salesman problem (TSP)?\n\nTSP problems are one of the future directions where we hope to see the advantage of GFlowNets on this family of combinatorial optimization problems. For example, the action of GFlowNet could be to choose the next vertex to visit (for the traveling salesman). The architecture of policy and flow could be a transformer like in previous approaches [1].\n\n[1] Attention, Learn to Solve Routing Problems!"}]

Author rebuttal:
## General Response

We sincerely thank all the reviewers for your insightful comments and suggestions. 

> About the contribution and novelty of our work

While our approach builds upon the general GFlowNet framework, we have made significant designs and innovations to ensure its scalability and effectiveness in tackling complex CO problems which cannot be achieved with direct application. First, our MDP formulations are specially designed for different CO problems and have never been studied in previous GFlowNet works. These designs are crucial to ensure the solution satisfying the feasibility requirement (this is related to another question raised by the same reviewer related to “difficult” feasibility CO). Second, the GFlowNet training scale in this work is much larger in the sense of GPU occupation than any previous ones, and we would like to emphasize that our work pushes the boundaries of GFlowNet's training scale. To cope with this challenge, we develop novel training techniques to enable efficient learning (Sec. 3.3) which serve as a remedy to issues about training efficiency and memory consumption for previous approaches [1]. These techniques are not only applicable in CO tasks but can also be extended to any GFlowNet applications such as molecule design. On the other hand, there are a large number of papers [2] on using RL to solve CO problems and people do not consider them as “direct application”, let alone for GFlowNets which we have discussed to be more appropriate than RL for these tasks.

[1] Trajectory balance: Improved credit assignment in GFlowNets
[2] Reinforcement Learning for Combinatorial Optimization: A Survey

Meta-review: The paper has obtained reviewer consensus in favor of acceptance and the AC follows it. The scores and positive reception merit spotlight. Overall the paper is a good combination of GFlowNets and a number of other augmentations with nice results. The rebuttals have been noted as well as their positive influence on the review scores.
Decision: Accept (spotlight)